特徴ハッシュ

Vectorizing features using a hash function

機械学習において、特徴ハッシュ法（カーネルトリックに類似してハッシングトリックとも呼ばれる）は、特徴をベクトル化する高速かつ空間効率の高い方法である。つまり、任意の特徴をベクトルまたは行列のインデックスに変換するのである。^{[1] [2]}これは、連想配列でインデックスを参照するのではなく、特徴にハッシュ関数を適用し、そのハッシュ値を直接インデックスとして使用することで機能する（モジュロ演算後）。数値以外の値をエンコードするだけでなく、特徴ハッシュ法は次元削減にも使用できる。^[2]

このトリックは、Weinbergerら（2009）^[2]に帰属することが多いが、この方法については、1989年にJohn Moodyによって発表されたはるかに古い記述が存在する。^[1]

モチベーション

動機付けの例

典型的な文書分類タスクでは、機械学習アルゴリズムへの入力（学習時と分類時の両方）はフリーテキストです。この入力から、 BOW（ Bag of Words）表現が構築されます。個々のトークンが抽出・カウントされ、トレーニングセット内の各トークンが、トレーニングセットとテストセットの両方に含まれる各文書の特徴（独立変数）を定義します。

しかし、機械学習アルゴリズムは通常、数値ベクトルで定義されます。したがって、文書集合のバッグ・オブ・ワードは、各行が単一の文書、各列が単一の特徴量/単語である用語-文書行列とみなされます。このような行列のエントリi , j は、文書iにおける語彙のj番目の用語の頻度（または重み）を表します。（別の規則として、行列の行と列を入れ替える場合もありますが、この違いは重要ではありません。）通常、これらのベクトルはジップの法則に従って非常にスパースです。

一般的なアプローチは、学習時またはそれ以前に、訓練セットの語彙の辞書表現を構築し、それを用いて単語をインデックスにマッピングすることです。辞書の実装には、ハッシュテーブルやトライがよく用いられます。例えば、以下の3つの文書は、

• ジョンは映画を見るのが好きです。
• メアリーも映画が好きです。
• ジョンはサッカーも好きです。

辞書を使って変換できる

学期	索引
ジョン	1
いいね	2
に	3
時計	4
映画	5
メアリー	6
あまりにも	7
また	8
フットボール	9

用語-文書マトリックスへ

${\displaystyle {\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}}}$

(ドキュメントの分類とクラスタリングでは通常どおり、句読点は削除されています。)

このプロセスの問題は、このような辞書が大量のストレージスペースを占有し、トレーニングセットが大きくなるにつれてサイズが大きくなることです。^[3] 逆に、語彙が固定され、トレーニングセットの増加に合わせて増加しない場合、攻撃者は機械学習フィルターを回避するために、保存された語彙にない新しい単語やスペルミスをでっち上げようとする可能性があります。この課題に対処するため、Yahoo! Researchはスパムフィルターに特徴ハッシュ法を採用しようと試みました。^[4]

ハッシュ トリックは、ドキュメント レベルでのテキスト分類や同様のタスクに限定されず、多数の (おそらく無制限の) 機能を含むあらゆる問題に適用できることに注意してください。

数学的な動機

数学的には、トークンとは有限（あるいは可算無限）集合 の要素です。有限のコーパスのみを処理する必要がある場合、コーパスに出現するすべてのトークンを にまとめることができます。つまり、 は有限です。しかし、英語の文字で構成されるすべての単語を処理したい場合、 は可算無限です。 ${\displaystyle t}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle T}$

ほとんどのニューラル ネットワークは実数ベクトル入力でのみ動作できるため、「辞書」関数を構築する必要があります。 ${\displaystyle \phi :T\to \mathbb {R} ^{n}}$

が有限でサイズが のとき、ワンホットエンコーディングを用いて にマッピングできます。まず を任意に列挙し、次に を定義します。言い換えれば、各トークンに一意のインデックスを割り当て、次にインデックスを持つトークンを単位基底ベクトル にマッピングします。 ${\displaystyle T}$ ${\displaystyle |T|=m\leq n}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle T=\{t_{1},t_{2},..,t_{m}\}}$ ${\displaystyle \phi (t_{i})=e_{i}}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle e_{i}}$

ワンホットエンコーディングは解釈が容易ですが、 の任意の列挙を維持する必要があります。トークン が与えられた場合、 を計算するには、トークン のインデックスを見つける必要があります。したがって、 を効率的に実装するには、高速に計算できる一対一表現 が必要であり、 が得られます。 ${\displaystyle T}$ ${\displaystyle t\in T}$ ${\displaystyle \phi (t)}$ ${\displaystyle i}$ ${\displaystyle t}$ ${\displaystyle \phi }$ ${\displaystyle h:T\to \{1,...,m\}}$ ${\displaystyle \phi (t)=e_{h(t)}}$

実際、要件を少し緩和することができます。つまり、計算が高速な注入 を 用意して、 を使用すれば十分です。 ${\displaystyle h:T\to \{1,...,n\}}$ ${\displaystyle \phi (t)=e_{h(t)}}$

実際には、効率的な単射 を構築する簡単な方法はありません。しかし、厳密な単射ではなく、近似的な単射で十分です。つまり、 のとき、おそらく となり、おそらく となるはずです。 ${\displaystyle h:T\to \{1,...,n\}}$ ${\displaystyle t\neq t'}$ ${\displaystyle h(t)\neq h(t')}$ ${\displaystyle \phi (t)\neq \phi (t')}$

この時点で、 はハッシュ関数であるべきだと指定しました。こうして、特徴ハッシュという考え方に到達します。 ${\displaystyle h}$

アルゴリズム

特徴ハッシュ（Weinberger et al. 2009）

^{(Weinberger et al. 2009) [2]}で提示された基本的な特徴ハッシュアルゴリズムは次のように定義されます。

まず、2つのハッシュ関数、すなわちカーネルハッシュ と符号ハッシュを指定します。次に、特徴ハッシュ関数 を定義します。最後に、この特徴ハッシュ関数を によってトークンの文字列に拡張します。ここで、 は内のトークンで構成されるすべての有限文字列の集合です。 ${\displaystyle h:T\to \{1,2,...,n\}}$ ${\displaystyle \zeta :T\to \{-1,+1\}}$ $${\displaystyle \phi :T\to \mathbb {R} ^{n},\quad \phi (t)=\zeta (t)e_{h(t)}}$$ $${\displaystyle \phi :T^{*}\to \mathbb {R} ^{n},\quad \phi (t_{1},...,t_{k})=\sum _{j=1}^{k}\phi (t_{j})}$$ ${\displaystyle T^{*}}$ ${\displaystyle T}$

同様に、 $${\displaystyle \phi (t_{1},...,t_{k})=\sum _{j=1}^{k}\zeta (t_{j})e_{h(t_{j})}=\sum _{i=1}^{n}\left(\sum _{j:h(t_{j})=i}\zeta (t_{j})\right)e_{i}}$$

幾何学的特性

の幾何学的特性について述べたいと思いますが、は、単独では単なるトークンの集合であり、離散計量によって生成される離散位相を除いて、幾何学的構造を に課すことはできません。 より適切にするために、 を に持ち上げ、線形拡張によってからに持ち上げます。そこには無限和があり、これを一度に処理する必要があります。 無限大を処理する方法は基本的に 2 つしかありません。 1 つは、計量値を課してからその完備化 を取って、行儀の良い無限和を許可するか、実際には無限なものはなく、潜在的に無限であるだけであることを要求する方法です。 ここでは、 を有限サポートのベクトルのみを含むように制限することによって、潜在的無限大の方法を採用します。では、 の有限個の要素のみが非ゼロです。 ${\displaystyle \phi }$ ${\displaystyle T}$ ${\displaystyle T\to \mathbb {R} ^{T}}$ ${\displaystyle \phi }$ ${\displaystyle \phi :T\to \mathbb {R} ^{n}}$ ${\displaystyle \phi :\mathbb {R} ^{T}\to \mathbb {R} ^{n}}$ $${\displaystyle \phi ((x_{t})_{t\in T})=\sum _{t\in T}x_{t}\zeta (t)e_{h(t)}=\sum _{i=1}^{n}\left(\sum _{t:h(t)=i}x_{t}\zeta (t)\right)e_{i}}$$ ${\displaystyle \mathbb {R} ^{T}}$ ${\displaystyle \forall (x_{t})_{t\in T}\in \mathbb {R} ^{T}}$ ${\displaystyle (x_{t})_{t\in T}}$

上の内積を明白な方法で定義します。ちなみに、が無限大の場合、内積空間は完備ではありません。完備化をとるとヒルベルト空間となり、そこでは振る舞いの良い無限和が許容されます。 ${\displaystyle \mathbb {R} ^{T}}$ $${\displaystyle \langle e_{t},e_{t'}\rangle ={\begin{cases}1,{\text{ if }}t=t',\\0,{\text{ else.}}\end{cases}}\quad \langle x,x'\rangle =\sum _{t,t'\in T}x_{t}x_{t'}\langle e_{t},e_{t'}\rangle }$$ ${\displaystyle T}$ ${\displaystyle \mathbb {R} ^{T}}$

これで、特徴ハッシュ関数の幾何学を記述するのに十分な構造を持つ内積空間が得られました。 ${\displaystyle \phi :\mathbb {R} ^{T}\to \mathbb {R} ^{n}}$

まず、が「カーネル ハッシュ」と呼ばれる理由がわかります。これにより、 によってカーネルを定義できます。「カーネル トリック」の用語では、は「機能マップ」によって生成されたカーネルです。これは、 である使用していた機能マップではないことに注意してください。実際、 によって定義される別のカーネルを使用していました。カーネル ハッシュをバイナリ ハッシュで拡張する利点は、 が「平均して」等長変換であることを示す次の定理です。 ${\displaystyle h}$ ${\displaystyle K:T\times T\to \mathbb {R} }$ $${\displaystyle K(t,t')=\langle e_{h(t)},e_{h(t')}\rangle }$$ ${\displaystyle K}$ $${\displaystyle \varphi :T\to \mathbb {R} ^{n},\quad \varphi (t)=e_{h(t)}}$$ ${\displaystyle \phi (t)=\zeta (t)e_{h(t)}}$ ${\displaystyle K_{\zeta }:T\times T\to \mathbb {R} }$ $${\displaystyle K_{\zeta }(t,t')=\langle \zeta (t)e_{h(t)},\zeta (t')e_{h(t')}\rangle }$$ ${\displaystyle h}$ ${\displaystyle \zeta }$ ${\displaystyle \phi }$

定理（直感的に言うと）—バイナリハッシュが偏りがない場合（つまり、等しい確率で値を取る場合）、期待値は等長になります。 ${\displaystyle \zeta }$ ${\displaystyle -1,+1}$ ${\displaystyle \phi :\mathbb {R} ^{T}\to \mathbb {R} ^{n}}$ $${\displaystyle \mathbb {E} [\langle \phi (x),\phi (x')\rangle ]=\langle x,x'\rangle .}$$

証拠

期待値の線形性により、は不偏であると仮定したので、となる。したがって、 $${\displaystyle \mathbb {E} [\langle \phi (x),\phi (x')\rangle ]=\sum _{t,t'\in T}(x_{t}x'_{t'})\cdot \mathbb {E} [\zeta (t)\zeta (t')]\cdot \langle e_{h(t)},e_{h(t')}\rangle }$$ ${\displaystyle \mathbb {E} [\zeta (t)\zeta (t')]={\begin{cases}1\quad {\text{ if }}t=t'\\0\quad {\text{ if }}t\neq t'\\\end{cases}}}$ ${\displaystyle \zeta }$ $${\displaystyle \mathbb {E} [\langle \phi (x),\phi (x')\rangle ]=\sum _{t\in T}(x_{t}x'_{t})\langle e_{h(t)},e_{h(t)}\rangle =\langle x,x'\rangle }$$

上記の記述と証明は、バイナリ ハッシュ関数を型の決定論的関数としてではなく、バイアスのないエントリを持つランダム バイナリ ベクトルとして解釈します。つまり、任意の に対してとなります。 ${\displaystyle \zeta }$ ${\displaystyle T\to \{-1,+1\}}$ ${\displaystyle \{-1,+1\}^{T}}$ ${\displaystyle Pr(\zeta (t)=+1)=Pr(\zeta (t)=-1)={\frac {1}{2}}}$ ${\displaystyle t\in T}$

これは直感的には良い図ですが、厳密ではありません。厳密な記述と証明については^{[2]を参照してください。}

擬似コードの実装

ハッシュトリックを用いる特徴ベクトル化器は、辞書を維持する代わりに、特徴（例えば単語）にハッシュ関数hを適用し、そのハッシュ値を特徴インデックスとして直接用い、得られたベクトルのインデックスを更新することで、定義済みの長さのベクトルを構築できます。ここでは、特徴は実際には特徴ベクトルを意味するものとします。

 関数hashing_vectorizer ( features :文字列の配列、N :整数) : x :=新しいベクトル[ N ] for f in features : h := hash ( f ) x [ h mod N ] += 1 return x                          

例えば、特徴ベクトルが["cat","dog","cat"]で、ハッシュ関数が"cat"の場合は"dog"、"dog"の場合は"cat"となる。出力特徴ベクトルの次元( N )を4とすると、出力xは[0,2,1,0]となる。ハッシュ衝突の影響を抑えるため、更新値の符号を決定するために、2つ目の1ビット出力ハッシュ関数ξを用いることが提案されている^[2]。このようなハッシュ関数を用いると、アルゴリズムは以下のようになる。 ${\displaystyle h(x_{f})=1}$ ${\displaystyle x_{f}}$ ${\displaystyle 2}$ ${\displaystyle x_{f}}$

 関数hashing_vectorizer ( features :文字列の配列、N :整数) : x :=新しいベクトル[ N ] for f in features : h := hash ( f ) idx := h mod N if ξ ( f ) == 1 : x [ idx ] += 1 else : x [ idx ] -= 1 return x                                     

上記の擬似コードは実際には各サンプルをベクトルに変換します。最適化されたバージョンでは、代わりにペアのストリームのみを生成し、学習アルゴリズムと予測アルゴリズムはそれらのストリームを消費します。こうすることで、線形モデルは係数ベクトルを表す単一のハッシュテーブルとして実装できます。 ${\displaystyle (h,\zeta )}$

拡張とバリエーション

学習済み特徴ハッシュ

特徴ハッシュ法は一般的にハッシュ衝突の問題を抱えており、これは異なるトークンが同じハッシュを持つペアが存在することを意味します：。特徴ハッシュ法でハッシュされた単語で訓練された機械学習モデルは、 が多義的であるため、とを区別することが困難になります。 ${\displaystyle t\neq t',\phi (t)=\phi (t')=v}$ ${\displaystyle t}$ ${\displaystyle t'}$ ${\displaystyle v}$

がまれなケースであれば、モデルは常にまれなケースを無視し、すべてがを意味すると仮定できるため、パフォーマンスの低下は小さくなります。しかし、両方が一般的なケースであれば、パフォーマンスの低下は深刻になる可能性があります。 ${\displaystyle t'}$ ${\displaystyle v}$ ${\displaystyle t}$

これに対処するために、共通のトークンが同じ特徴ベクトルにマッピングされることを回避する教師ありハッシュ関数を訓練することができる。^[5]

アプリケーションと実用性能

ガンチェフとドレッゼは、ランダムハッシュ関数と出力ベクトルの数万列を持つテキスト分類アプリケーションでは、符号付きハッシュ関数がなくても、特徴ハッシュが分類パフォーマンスに悪影響を与えることはないことを示しました。^[3]

ワインバーガーら（2009）は、特徴ハッシュの独自のバージョンをマルチタスク学習、特にスパムフィルタリングに適用しました。入力特徴は（ユーザー、特徴）のペアであるため、単一のパラメータベクトルでユーザーごとのスパムフィルターと数十万ユーザーのグローバルフィルターを捕捉でき、フィルターの精度が向上することを発見しました。^[2]

Chenら（2015）は、特徴ハッシュと疎行列の概念を組み合わせ、「仮想行列」を構築した。これは、記憶容量が小さく、大きな行列である。この概念は、行列を辞書として扱い、キーを、値を に格納するというものである。そして、ハッシュ辞書では通常通り、ハッシュ関数 を用いることで、行列を の大きさに関わらずのベクトルとして表すことができる。彼らは仮想行列を用いて、小さな記憶容量しか必要としない大規模なニューラルネットワークであるHashedNetを構築した。 ^[6] ${\displaystyle M\in \mathbb {R} ^{n\times n}}$ ${\displaystyle n\times n}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle h:\mathbb {N} \times \mathbb {N} \to m}$ ${\displaystyle \mathbb {R} ^{m}}$ ${\displaystyle n}$

実装

ハッシュトリックの実装は次の場所に存在します。

• アパッチマハウト^[7]
• ゲンシム^[8]
• サイキットラーン^[9]
• ソフィア-ML ^[10]
• ヴォウパル・ウビット
• アパッチスパーク^[11]
• R ^[12]
• テンソルフロー^[13]
• ダスクML ^[14]

参照

• ブルームフィルタ – 近似集合メンバーシップのデータ構造
• カウント・ミニマムスケッチ – コンピュータサイエンスにおける確率的データ構造
• ヒープの法則 – 文書内の異なる単語のヒューリスティック
• 局所性に敏感なハッシュ – ハッシュを用いたアルゴリズム技術
• MinHash  – データマイニング技術

参考文献

1. Moody, John (1989). 「多重解像度階層における高速学習」(PDF) . Advances in Neural Information Processing Systems . 2016年4月11日時点のオリジナル(PDF)からアーカイブ。 2018年12月14日閲覧。
2. Kilian Weinberger; Anirban Dasgupta; John Langford; Alex Smola; Josh Attenberg (2009). 大規模マルチタスク学習のための特徴ハッシュ(PDF) . Proc. ICML.
3. K. Ganchev; M. Dredze (2008). ランダム特徴混合による小規模統計モデル(PDF) . Proc. ACL08 HLT Workshop on Mobile Language Processing.
4. Josh Attenberg、Kilian Weinberger、Alex Smola、Anirban Dasgupta、Martin Zinkevich (2009). 「ハッシュトリックを用いた協調型スパムフィルタリング」Virus Bulletin .
5. バイ、B.ウェストン J.グランジェ D.コロベール R.貞正 K. Qi Y.シャペル O.ワインバーガー K. (2009)。監視付きセマンティック インデックス作成(PDF)。 CIKM。187～ 196ページ 。
6. Chen, Wenlin; Wilson, James; Tyree, Stephen; Weinberger, Kilian; Chen, Yixin (2015-06-01). 「ハッシュトリックによるニューラルネットワークの圧縮」.国際機械学習会議. PMLR: 2285– 2294. arXiv : 1504.04788 .
7. オーウェン、ショーン;アニル、ロビン。ダニング、テッド。フリードマン、エレン (2012)。象使いの活躍。マニング。261～ 265ページ 。
8. "gensim: corpora.hashdictionary – 単語<->IDマッピングの構築". Radimrehurek.com . 2014年2月13日閲覧。
9. “4.1. 特徴抽出 — scikit-learn 0.14 ドキュメント”. Scikit-learn.org . 2014年2月13日閲覧。
10. 「sofia-ml - 機械学習のための高速増分アルゴリズムスイート。Pegasos SVM、SGD-SVM、ROMMA、パッシブ・アグレッシブ・パーセプトロン、マージン付きパーセプトロン、ロジスティック回帰を用いた分類モデルとランキングモデルの学習手法が含まれています。」2014年2月13日閲覧。
11. 「Hashing TF」 。 2015年9月4日閲覧。ハッシュトリックを用いて、一連の用語をその用語頻度にマッピングします。
12. 「FeatureHashing: 数式インターフェースを使用した特徴ハッシュによるモデルマトリックスの作成」。2024年1月10日。
13. "tf.keras.preprocessing.text.hashing_trick — TensorFlow Core v2.0.1" . 2020年4月29日閲覧。テキストを固定サイズのハッシュ空間内のインデックスのシーケンスに変換します。
14. “dask_ml.feature_extraction.text.HashingVectorizer — dask-ml 2021.11.17 ドキュメント”. ml.dask.org . 2021年11月22日閲覧。

外部リンク

• John Langford のウェブサイトの「機械学習のためのハッシュ表現」
• 「ハッシュトリック」とは何ですか？ - MetaOptimize Q+A

Retrieved from "https://en.wikipedia.org/w/index.php?title=Feature_hashing&oldid=1314772715"