特徴ハッシュ

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

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

一般的なドキュメント分類タスクでは、機械学習アルゴリズムへの入力 (学習中と分類中の両方) はフリーテキストです。この入力から、単語のバッグ(BOW) 表現が構築されます。個々のトークンが抽出されてカウントされ、トレーニング セット内の各トークンがトレーニング セットとテスト セットの両方の各ドキュメントの特徴(独立変数) を定義します。

ただし、機械学習アルゴリズムは通常、数値ベクトルで定義されます。したがって、ドキュメント セットの単語のバッグは、各行が 1 つのドキュメント、各列が 1 つの特徴/単語である用語ドキュメント マトリックスと見なされます。このようなマトリックスのエントリi、j は、ドキュメントiの語彙のj番目の用語の頻度 (または重み) を取得します。(別の規則では、マトリックスの行と列を入れ替えますが、この違いは重要ではありません。) 通常、これらのベクトルは、ジップの法則に従って、非常にスパースです。

一般的なアプローチは、学習時またはそれ以前に、トレーニングセットの語彙の辞書表現を構築し、それを使用して単語をインデックスにマッピングすることです。ハッシュテーブルとトライは、辞書の実装の一般的な候補です。たとえば、次の3つのドキュメント

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

辞書を使って変換できる

用語文書マトリックスに

${\displaystyle {\begin{pmatrix}{\textrm {ジョン}}&{\textrm {好き}}&{\textrm {に}}&{\textrm {見る}}&{\textrm {映画}}&{\textrm {メアリー}}&{\textrm {も}}&{\textrm {また}}&{\textrm {サッカー}}\\1&1&1&1&1&0&0&0&0\\0&1&0&0&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) [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 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 (特徴:文字列の配列、N :整数) : x :=新しいベクトル[ N ] for f in features : h := hash ( f ) x [ h mod N ] += 1 return x        
        
        
           
             
      

したがって、特徴ベクトルが["cat","dog","cat"]で、ハッシュ関数がが"cat"の場合は、が"dog"の場合はである。出力特徴ベクトルの次元( 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 (特徴:文字列の配列、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]

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

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

Chen ら (2015) は、特徴ハッシュと疎行列の考え方を組み合わせて、「仮想行列」を構築しました。これは、小さなストレージ要件で大きな行列です。この考え方は、行列を辞書として扱い、キーを、値を とします。すると、ハッシュされた辞書では通常、ハッシュ関数 を使用できるため、がどれだけ大きくても、行列を のベクトルとして表すことができます。仮想行列を使用して、彼らはHashedNets を構築しました。これは、小さなストレージしか必要としない大規模なニューラル ネットワークです。^[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  – データマイニング技術

• John Langford の Web サイトにある機械学習のためのハッシュ表現
• 「ハッシュトリック」とは何ですか? - MetaOptimize Q+A