Feature Hashing
典型的な文書分類のタスクにおいて、機械学習アルゴリズムには(学習と分類の両方において)自由な形式のテキストが入力される。このテキストからBag of words(英語版)(BOW)表現が作られる。つまり、トークンが抽出・カウントされ、訓練データ中のそれぞれのトークンが、訓練データ・テストデータ両方におけるそれぞれの文書の特徴量(独立変数)として定義される。
ところが、ほとんどの場合機械学習アルゴリズムは数値型のベクトルを扱うように定義されている。それゆえ文書集合に対するBag of wordsはDocument-term matrix(英語版)と見なされる。ここでそれぞれの行は文書を表し、列は特徴量(単語)を表している。つまり、行列の(i, j)成分は文書iのj番目の単語の頻度(または重み)を表す(行列の行と列の役割を逆にする見方もあるが、この違いは重要ではない)。 このような行列は一般的に非常にスパースである。
訓練あるいはその前段階にいて、訓練データの単語集合に対して辞書表現を作り、単語をインデックスに射影するという方法がよく使われる。しばしばハッシュテーブルやトライ木を使って辞書が作られる。例えば、次のような3つの文書
John likes to watch movies.
Mary likes movies too.
John also likes football.
は辞書を使って次のように変換される。
そして次のようなDocument-term行列ができる。
ハッシュ関数hを訓練・予測対象のアイテムの特徴集合(例えば単語集合)に適用して、そのハッシュ値を特徴量のインデックスとして使う。そしてこのインデックスで特徴ベクトルを更新する。このようにして、辞書を使うことなくあらかじめ定義した長さの特徴ベクトルを作ることができる:
ハッシュ値の衝突を避けるために、1ビット出力の関数ξを使って更新値の符号を決定する方法が提案されている。アルゴリズムは次のようになる:
上の擬似コードは実際にサンプルをベクトルに変換する。処理の最適化としては、(h,ξ)のペアの列だけを生成し、その列を処理して学習や予測を行うというものが考えられる。線形モデル(英語版)は係数ベクトルを表す1つのハッシュテーブルで表現することができる。