特徴ハッシュ

幾何学的性質について何か言いたいのですが${\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}}$$そこには無限和があり、すぐに処理しなければなりません。無限を扱う方法は基本的に2つしかありません。1つは、適切な無限和を許容するために、計量を課し、その完備化を取る方法、もう1つは、実際には何も無限ではなく、潜在的に無限であるだけであると要求する方法です。ここでは、潜在的無限の方法を採用し、制限します。${\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を特徴量（単語など）に適用し、ハッシュ値を直接特徴量インデックスとして使用して、結果のベクトルをそのインデックスで更新することにより、あらかじめ定義された長さのベクトルを構築できます。ここで、特徴量とは実際には特徴量ベクトルを意味するものとします。

function hashing_vectorizer ( features :文字列の配列, N :整数) : x := new vector [ N ] for f in features : h := hash ( f ) x [ h mod N ] += 1 return x

したがって、特徴ベクトルが ["cat","dog","cat"] でハッシュ関数が${\displaystyle h(x_{f})=1}$もし${\displaystyle x_{f}}$「猫」であり、${\displaystyle 2}$もし${\displaystyle x_{f}}$は「dog」です。出力特徴ベクトルの次元（N）を4とします。すると出力xは[0,2,1,0]になります。ハッシュ衝突の影響を打ち消すために、更新値の符号を決定するために2番目の1ビット出力ハッシュ関数ξを使用することが提案されています。^{[ 2 ]}このようなハッシュ関数を使用すると、アルゴリズムは次のようになります。

function hashing_vectorizer ( features :文字列の配列, N :整数) : 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

上記の擬似コードは、実際には各サンプルをベクトルに変換します。最適化されたバージョンでは、代わりにストリームのみを生成します。${\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 ]}