reading and coding ...

メモ: CBOW, Skip-Gram, NS

5/20/2020, 2:11:43 PM - 47 days ago

https://cs224d.stanford.edu/lecture_notes/notes1.pdf と eisenstein-nlp-notes.pdf から主にとってる.
何か間違えてたら Issue でお願いします


CBOW

The cat jumped over the puddle.

について, {"The", "cat", "over", "the", "puddle"} から "jumped" 推測したい.

記号

  • 語彙 VV における単語 wiw_i
  • 入力の行列 WinRn×VW_{in} \in R^{n \times |V|}, この ii 列目が wiw_i の分散表現となるべきもの
  • 出力の行列 WoutRV×nW_{out} \in R^{|V| \times n}, この ii 行目が wiw_i の分散表現となるべきもの

推測の仕組み

  1. ある cc 番目の単語について周囲 mm 個の単語の one-hot 表現 x(cm),...,x(c1),x(c+1),...,x(c+m)x^{(c-m)}, ..., x^{(c-1)}, x^{(c+1)}, ..., x^{(c+m)} がある
  2. それぞれ左から WinW_{in} をかける(vi=Winx(i)v_i = W_{in} x^{(i)})と, それぞれの単語の分散表現 vcm,...,vc1,vc+1,...,vc+mv_{c-m}, ..., v_{c-1}, v_{c+1}, ..., v_{c+m} が得られる (one-hot表現なので特定の列ベクトルを切り出しているだけ)
  3. これら 2m2m 個のベクトルの平均を取る: v^\hat{v}
  4. z=Woutv^z = W_{out} \hat{v} を計算
  5. softmax で正規化する: y^=softmax(z)\hat{y} = softmax(z)
  6. こうして得られた y^\hat{y}cc 番目の単語の one-hot 表現 x(c)=yx^{(c)} = y に近いベクトルであってほしい

この推測の学習をすることで, Win,WoutW_{in}, W_{out} がいい感じになって, 分散表現を格納した行列になる(ゼロから作る本によると, この2つの結果物のうち実際には WinW_{in} のみを分散表現として使う).
学習では, y^\hat{y}yy に近づいて欲しいので, クロスエントロピー誤差

H(y^,y)=j=1Vyjlog(y^j)H(\hat{y}, y) = - \sum_{j=1}^{|V|} y_j \log(\hat{y}_j)

を小さくするように学習する. クロスエントロピーは勾配が綺麗なので逆伝播の式が書きやすく, ディープラーニングだと使うことが多い.
そして, yjy_j は one-hot 表現なのでほぼ要素が0で, yy が 1 の要素の部分で log\log の部分が大きくなってほしい, つまり y^\hat{y} もできるだけその部分で 1 になってほしいというのがこの式の意味になる.

結局, そういう計算で何をするかというと

m=1Mlogexp(uwmTv^m)j=1Vexp(ujTv^m)\sum_{m=1}^{M} \log \dfrac{\exp(u_{w_m}^T \hat{v}_m)}{\sum_{j=1}^{|V|} \exp(u_j^T \hat{v}_m)}

を最大化(あるいはこれにマイナスをつけたものを最小化するとも言える)して, その過程で, 入力行列や出力行列をいい感じにしていくということになる

Skip-Gram

The cat jumped over the puddle.

について, {"The", "cat", "over", "the", "puddle"} "jumped" から推測したい.

CBOW とそんなに変わらなくて, CBOW では周囲 mm 個のベクトルの平均をとって, それを使って自身 11 個の推測をして, 誤差を考えていたが, Skip-Gram は自身 11 個を使って周囲 mm 個の推測をして, 誤差の和を考える.

式にすると,

m=1Mn=1hmlogexp(uwmnTvwm)j=1Vexp(ujTvwm)+logexp(uwm+nTvwm)j=1Vexp(ujTvwm)\sum_{m=1}^{M} \sum_{n=1}^{h_m} \log \dfrac{\exp(u_{w_{m-n}}^T v_{w_m})}{\sum_{j=1}^{|V|} \exp(u_j^T v_{w_m})} + \log \dfrac{\exp(u_{w_{m+n}}^T v_{w_m})}{\sum_{j=1}^{|V|} \exp(u_j^T v_{w_m})}

を最大化して, その過程で, 入力行列や出力行列をいい感じにしていく

Negative Sampling

どちらのモデルにしても, Softmax 関数の分母 j=1Vexp(ujTvwm)\sum_{j=1}^{|V|} \exp(u_j^T v_{w_m}) が大変なことになってしまっていて計算が苦しい. Word2Vec の論文では Hierarchical softmax と Negative Sampling という2つの工夫が提案されている. そのうち Negative Sampling について述べる.

ゼロから作る本の表現によると「多値分類ではなく二値分類」ということ.
{"The", "cat", "over", "the", "puddle"} から考えるべきなのは正解 "jumped" であるかどうかであり, 間違いのバリエーションは割とどうでもいい.

二値分類ではソフトマックス関数ではなくシグモイド関数を使う. したがって, ii を単語, jj をその文脈とすると, 学習で大きくすべきスコアは

log11+exp(uiTvj)+iWneglog(111+exp(uiTvj))\log \dfrac{1}{1 + \exp(- u_i^T v_j)} + \sum_{i' \in W_{neg}} \log \left(1 - \dfrac{1}{1 + \exp(- u_{i'}^T v_j)} \right)

みたいな形になる. WnegW_{neg} を抑えることで, 必要計算量は大きく減った. あとは, CBOW や Skip-Gram それぞれの中にあるソフトマックスを, この形に置き換えてあげれば良い. 誤差評価はやはりクロスエントロピーである.

負例 WnegW_{neg} のサンプリングは単語の使用頻度にもとづいた確率分布から行うが, 確率の値をそのまま使うのではなく 0.750.75 乗(して正規化)するとなんかいいらしい. あまりに確率の低い単語を見捨てない効果があるらしいが, 非常にヒューリスティックですね

今後

Negative Sampling が PMI の分解と等価という話について調べたい