Published on

SGNSの目的関数について

Authors

Negative Samplingについて忘れかけていたことを復習しました。

Skip-gram

Skip-gramモデルは入力層、中間層、出力層の3層からなる単純なニューラルネットワークで、 単語(入力)から文脈(出力)を予測するモデルである。 隠れ層はNN次元のベクトルとなっており、word2vec{\tt word2vec}が獲得している概念ベクトルはこれに相当する。 単語wtw_t(入力)が与えられたときに、周辺の単語wt+jw_{t+j}(出力)が出現する確率の総乗の対数、

1Tlog⁡∏t=1T∏−c≤j≤c,j≠0p(wt+j∣wt)=1T∑t=1T∑−c≤j≤c,j≠0log⁡p(wt+j∣wt)\begin{aligned} & \frac{1}{T} \log \prod_{t=1}^{T} \prod_{-c \leq j \leq c, j \neq 0} p\left(w_{t+j} | w_{t}\right) \\ =& \frac{1}{T} \sum_{t=1}^{T} \sum_{-c \leq j \leq c, j \neq 0} \log p\left(w_{t+j} | w_{t}\right) \end{aligned}

の最大化を目的としている。ここで、TT は学習に用いる単語列 w1,w2,w3,...,wTw_1, w_2, w_3, ..., w_T の長さ、cc はコンテキストの長さを表している。 単語 wIw_I (入力)が与えられたときに、周辺の単語 wOw_O (出力)が出現する確率を、以下に示すソフトマックス関数でモデル化している。

p(wO∣wI)=exp⁡(vwO′T⋅vwI)∑wi∈Vexp⁡(vwi′T⋅vwI)\begin{aligned} p(w_O|w_I) = \frac{\exp(\boldsymbol{v}_{w_O}^{\prime\mathrm{T}} \cdot \boldsymbol{v}_{w_I})}{\sum_{w_i \in V} \exp(\boldsymbol{v}_{w_i}^{\prime\mathrm{T}} \cdot \boldsymbol{v}_{w_I})} \end{aligned}

ここで、VVはボキャブラリ、vwI\boldsymbol{v}_{w_I} と vwO′\boldsymbol{v}^{\prime}_{w_O} はそれぞれ入力の単語ベクトルと出力の単語ベクトルを意味する。 従って、入力の単語ベクトル vwI\boldsymbol{v}_{w_I} と実際に出現している出力の単語ベクトル vwO′\boldsymbol{v}^{\prime}_{w_O} の内積が大きくなるように学習を行う。

見ての通り、分母の計算量が膨大なため、次のNegative Samplingと呼ばれる方法が提案されている。

Negative Sampling

新たに、ある単語のペア (wI,wO)(w_I, w_O) が出現する確率を考え、p(D=1∣wI,wO)p(D=1 | w_I, w_O) とする。 出現しない確率を p(D=0∣wI,wO)p(D=0 | w_I, w_O) とし、出現する確率を単語のベクトル同士の内積値を用いたシグモイド関数 σ\sigma とすると、

p(D=1∣wI,wO)=σ(vwIT⋅vwO′)p(D=0∣wI,wO)=1−p(D=1∣wI,wO)\begin{aligned} p(D=1|w_I, w_O) = & \sigma(\boldsymbol{v}_{w_I}^T \cdot \boldsymbol{v}^{\prime}_{w_O})\\ p(D=0|w_I, w_O) = & 1 - p(D=1|w_I, w_O) \end{aligned}

と表すことができ、新たな目的関数、

log⁡(p(D=1∣wI,wO)∏wi∈Vp(D=0∣wI,wi))\begin{aligned} \log \biggl( p(D=1|w_I, w_O) \prod_{w_i \in V}^{} p(D=0|w_I, w_i) \biggr) \end{aligned}

の最大化を考える。この時、全てのボキャブラリについて総乗を計算するのが大変なため、 kk 個だけサンプリングしたVnegV_{\rm neg}を考えると、

log⁡(p(D=1∣wI,wO)∏wi∈Vnegp(D=0∣wI,wi))=log⁡p(D=1∣wI,wO)+∑wi∈Vneglog⁡p(D=0∣wI,wi)=log⁡σ(vwIT⋅vwO′)+∑wi∈Vneglog⁡(1−p(D=1∣wI,wi))=log⁡σ(vwIT⋅vwO′)+∑wi∈Vneglog⁡(1−σ(vwIT⋅vwi′))=log⁡σ(vwIT⋅vwO′)+∑wi∈Vneglog⁡σ(−vwIT⋅vwi′)\begin{aligned} & & \log & \biggl( p(D=1|w_I, w_O) \prod_{w_i \in V_{\rm neg}}^{} p(D=0|w_I, w_i) \biggr) \\ & = & \log & p(D=1|w_I, w_O) + \sum_{w_i \in V_{\rm neg}}^{} \log p(D=0|w_I, w_i) \\ & = & \log & \sigma(\boldsymbol{v}_{w_I}^T \cdot \boldsymbol{v}^{\prime}_{w_O}) + \sum_{w_i \in V_{\rm neg}}^{} \log \biggl( 1-p(D=1|w_I, w_i) \biggr)\\ & = & \log & \sigma(\boldsymbol{v}_{w_I}^T \cdot \boldsymbol{v}^{\prime}_{w_O}) + \sum_{w_i \in V_{\rm neg}}^{} \log \biggl( 1-\sigma(\boldsymbol{v}_{w_I}^T \cdot \boldsymbol{v}^{\prime}_{w_i}) \biggr) \\ & = & \log & \sigma(\boldsymbol{v}_{w_I}^T \cdot \boldsymbol{v}^{\prime}_{w_O}) + \sum_{w_i \in V_{\rm neg}}^{} \log \sigma(-\boldsymbol{v}_{w_I}^T \cdot \boldsymbol{v}^{\prime}_{w_i}) \end{aligned}

もともとの目的関数の分母について、∣V∣|V| 回の計算が必要であったが、わずか kk 回に抑えることができ、計算量が大幅に削減できていることがわかる。kk は一般に5から15程度が用いられるらしい。

参考

  • Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado and Jeff Dean, Distributed Representations of Words and Phrases and their Compositionality, NIPS2013