Feature Hashing

機械学習において、Feature Hashing（フィーチャーハッシング）は、高速かつ省メモリな特徴量をベクトルに変換する手法であり、任意の特徴をベクトルあるいは行列のインデックスに変換する。kernel trick(カーネルトリック)に似せてHashing Trick（ハッシュトリック）とも呼ばれる^[1]。連想配列を走査するのではなく、ハッシュ関数を特徴量に適用し、その値をインデックスとして直接使用する。

使用例

典型的な文書分類のタスクにおいて、機械学習アルゴリズムには(学習と分類の両方において)自由な形式のテキストが入力される。このテキストから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.

は辞書を使って次のように変換される。

Term	Index
John	1
likes	2
to	3
watch	4
movies	5
Mary	6
too	7
also	8
football	9

そして次のようなDocument-term行列ができる。

{\begin{pmatrix}{\textrm {John}}&{\textrm {likes}}&{\textrm {to}}&{\textrm {watch}}&{\textrm {movies}}&{\textrm {Mary}}&{\textrm {too}}&{\textrm {also}}&{\textrm {football}}\\1&1&1&1&1&0&0&0&0\\0&1&0&0&1&1&1&0&0\\1&1&0&0&0&0&0&1&1\end{pmatrix}}

(文書の分類やクラスタリングでよくされるように、時制は無視している)

このプロセスでの問題なのが辞書を保存するために多くのスペースが必要で、訓練データのサイズが大きくなるにつれてその必要スペースが増加することである(Heapsの法則（英語版）)^[2]。そのうえ、単語集合の大きさが一定数で固定されているときには、その単語集合に含まれない新しい単語や綴りの正しくない単語を使うことで、学習した分類フィルターをすり抜けることができてしまう。これはYahoo! Research（英語版）のスパムフィルタリングでFeature Hashingが使われる理由である^[3]。

もちろんHashing Trickの利用は文書分類やその他文書レベルの類似タスクに限られるわけではなく、多くの(あるいは上限が存在しない)数の特徴量を持つあらゆる問題に適用できる。

Hashing trickを使用した特徴量のベクトル化

ハッシュ関数 $h$ を訓練・予測対象のアイテムの特徴集合(例えば単語集合)に適用して、そのハッシュ値を特徴量のインデックスとして使う。そしてこのインデックスで特徴ベクトルを更新する。このようにして、辞書を使うことなくあらかじめ定義した長さの特徴ベクトルを作ることができる:

 function hashing_vectorizer(features : array of string, N : integer):
     x := new vector[N]
     for f in features:
         h := hash(f)
         x[h mod N] += 1
     return x

ハッシュ値の衝突を避けるために、1ビット出力の関数 $ξ$ を使って更新値の符号を決定する方法が提案されている^[1]。アルゴリズムは次のようになる:

 function hashing_vectorizer(features : array of string, N : integer):
     x := new vector[N]
     for f in features:
         h := hash(f)
         idx := h mod N
         if ξ(f) == 1:
             x[idx] += 1
         else:
             x[idx] -= 1
     return x

上の擬似コードは実際にサンプルをベクトルに変換する。処理の最適化としては、( $h$ , $ξ$ )のペアの列だけを生成し、その列を処理して学習や予測を行うというものが考えられる。線形モデル（英語版）は係数ベクトルを表す1つのハッシュテーブルで表現することができる。

性質

ξ(f₁)	ξ(f₂)	最終的な値: ξ(f₁) + ξ(f₂)
-1	-1	-2
-1	1	0
1	-1	0
1	1	2

2番目のハッシュ関数であるξを使って特徴値の符号を決定するとき、出力の配列のそれぞれの列の平均の期待値は0になる。なぜなら、ξはいくつかの衝突を回避するからある^[1]。例えば2つの符号特徴量f₁とf₂が互いに衝突し、それ以外の特徴量とは衝突していないとする。このときξに対して何も前提条件が無いとすると、右の表で示すような同じ確率を持つ4つの場合がある。

この例では、衝突が回避される確率は50%である。多値ハッシュ関数を使えばより衝突のリスクを回避することができる^[4]。

さらに、もしφがハッシュ関数 ξのHashing Trickによって実現された変換だとすると(つまり、φ(x)が標本xに対して作られた特徴ベクトルだとすると)、ハッシュ後の空間におけるベクトルの内積は不偏である:

\mathbb {E} [\langle \varphi (x),\varphi (x')\rangle ]=\langle x,x'\rangle

ここで期待値はハッシュ関数φについて計算されている^[1]。 $\langle \varphi (x),\varphi (x')\rangle$ が半正定値のカーネルであることが確かめられる^[1]^[5]。

拡張

最近の研究ではHashing Trickは単語からインデックスへの教師ありの射影に拡張された^[6]。この方法では重要な単語の衝突を避けるよう明示的に学習が行われる。

応用と実用面での性能

GanchevとDredzeはランダムなハッシュ関数を使って特徴量をもともとの1000分の数10程度に落としてテキスト分類を行い、符号に関するハッシュ関数を使わない場合でさえ、Feature Hashingは分類精度に悪影響を及ぼさないことを示している。^[2]

Weinbergerらはアレンジしたハッシュ関数をスパムフィルタリングの問題に応用し、これをマルチタスク学習（英語版）の問題に定式化した。ここで入力特徴量はユーザーと特徴量のペアになっており、パラメータベクトルが数10万人のユーザーに対するグローバルなフィルターであると共にユーザーごとのフィルターとして機能する。これによってフィルターの精度が上がることを確かめられた^[1]。

実装

Hashing Trickの実装は以下で提供されている:

脚注

[脚注の使い方]

^ ^a ^b ^c ^d ^e ^f Kilian Weinberger; Anirban Dasgupta; John Langford; Alex Smola; Josh Attenberg (2009). Feature Hashing for Large Scale Multitask Learning (PDF). Proc. ICML.
^ ^a ^b K. Ganchev; M. Dredze (2008). Small statistical models by random feature mixing (PDF). Proc. ACL08 HLT Workshop on Mobile Language Processing.
^ Josh Attenberg; Kilian Weinberger; Alex Smola; Anirban Dasgupta; Martin Zinkevich (2009). “Collaborative spam filtering with the hashing trick”. Virus Bulletin.
^ ^a ^b Owen, Sean; Anil, Robin; Dunning, Ted; Friedman, Ellen (2012). Mahout in Action. Manning. pp. 261–265
^ Shi, Q.; Petterson J.; Dror G.; Langford J.; Smola A.; Strehl A.; Vishwanathan V. (2009). Hash Kernels. AISTATS.
^ Bai, B.; Weston J.; Grangier D.; Collobert R.; Sadamasa K.; Qi Y.; Chapelle O.; Weinberger K. (2009). Supervised semantic indexing (PDF). CIKM. pp. 187–196.
^ “gensim: corpora.hashdictionary – Construct word<->id mappings”. Radimrehurek.com. 2014年2月13日閲覧。
^ “4.1. Feature extraction — scikit-learn 0.14 documentation”. Scikit-learn.org. 2014年2月13日閲覧。
^ “sofia-ml - Suite of Fast Incremental Algorithms for Machine Learning. Includes methods for learning classification and ranking models, using Pegasos SVM, SGD-SVM, ROMMA, Passive-Aggressive Perceptron, Perceptron with Margins, and Logistic Regression”. Code.google.com. 2014年2月13日閲覧。

外部リンク

Hashing Representations for Machine Learning on John Langford's website
What is the "hashing trick"? - MetaOptimize Q+A

[Weinberger-1] ^ ^a ^b ^c ^d ^e ^f Kilian Weinberger; Anirban Dasgupta; John Langford; Alex Smola; Josh Attenberg (2009). Feature Hashing for Large Scale Multitask Learning (PDF). Proc. ICML.

[mobilenlp-2] K. Ganchev; M. Dredze (2008). Small statistical models by random feature mixing (PDF). Proc. ACL08 HLT Workshop on Mobile Language Processing.

[3] Josh Attenberg; Kilian Weinberger; Alex Smola; Anirban Dasgupta; Martin Zinkevich (2009). “Collaborative spam filtering with the hashing trick”. Virus Bulletin.

[mahout-4] Owen, Sean; Anil, Robin; Dunning, Ted; Friedman, Ellen (2012). Mahout in Action. Manning. pp. 261–265

[5] Shi, Q.; Petterson J.; Dror G.; Langford J.; Smola A.; Strehl A.; Vishwanathan V. (2009). Hash Kernels. AISTATS.

[6] Bai, B.; Weston J.; Grangier D.; Collobert R.; Sadamasa K.; Qi Y.; Chapelle O.; Weinberger K. (2009). Supervised semantic indexing (PDF). CIKM. pp. 187–196.

[7] “gensim: corpora.hashdictionary – Construct word<->id mappings”. Radimrehurek.com. 2014年2月13日閲覧。

[8] “4.1. Feature extraction — scikit-learn 0.14 documentation”. Scikit-learn.org. 2014年2月13日閲覧。

[9] “sofia-ml - Suite of Fast Incremental Algorithms for Machine Learning. Includes methods for learning classification and ranking models, using Pegasos SVM, SGD-SVM, ROMMA, Passive-Aggressive Perceptron, Perceptron with Margins, and Logistic Regression”. Code.google.com. 2014年2月13日閲覧。

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

使用例

Hashing trickを使用した特徴量のベクトル化

性質

拡張

応用と実用面での性能

実装

脚注

関連項目

外部リンク