ハッシュとカーネル - KAZ log TechMemo

最近Spark使ってて特徴量減らしたいよねってなった時に、
Future Hashingを漠然と使ってたけど、気になったかた勉強。

Hash Trickの前にKernel Trick

どっか違う空間に写像するってことで似てるけど、若干用途が違うカーネルトリックから。
線形空間では分離できないデータを高次元特徴空間に写像して分離可能にしたいと。けど、次元が増えると計算大変。
じゃあ、高次元に写像した時と同じような結果を導き出せる関数使って、楽に計算しようってのがカーネルトリック。

入力空間 $R^m$ から特徴空間 $F$ への写像 $\Phi$ を、
$\Phi:R^m → F$ , $x → K(・,x)$
とすると、
$\langle \Phi (x), \Phi (y)\rangle = \langle K(・,x), K(・,y)\rangle = K(x,y)$
となって、特徴空間 $F$ への写像した後の内積がカーネル関数 $K()$ を使って入力空間 $R^m$ で楽に計算できる。
このカーネル関数を上手いこと選びましょうってのはまた別の話で。

Hash Trick

で、本題のハッシュトリック。
カーネル関数が線形分離可能にするために高次元に写像することを目指したのに対して、ハッシュ関数はその特徴行列の性質を損なわずに次元を小さくするために使われます。
次元が大きい疎ベクトルを上手いことぎゅっと凝縮して比較的密なベクトルに変換できれば、計算のためのリソースが少なくて済むよねってのがアイデア。

じゃあどうやるかっていうと、7つの特徴カテゴリがある下記のようなデータセットがあるとします。

A1 =[‘mouse’,’black’,-]
A2 =[‘cat’,’tabby’,’mouse’]

で、でもってインデックスの数を4とし、
ハッシュ関数を

H(Animal,’mouse’)=3
H(Color,’black’)=2
H(Animal,’cat’)=0
H(Color,’tabby’)=0
H(Diet,’mouse’)=2

と定義しておくと、
A1は、ハッシュ値1が0個、2が0個、3が1個、4が1個、
同様にA2はハッシュ値1が2個、2が0個、3が1個、4が0個となり、

A1=[0,0,1,1]
A2=[2,0,1,0]

と変換することができます。
ハッシュ値の衝突を避けるために、特徴値の符号を変えたりなどなど工夫がされます。