Negative Samplingについて忘れかけていたことを復習しました。
Skip-gramモデルは入力層、中間層、出力層の3層からなる単純なニューラルネットワークで、
単語(入力)から文脈(出力)を予測するモデルである。
隠れ層はN N N w o r d 2 v e c {\tt word2vec} w o r d 2 v e c w t w_t w t w t + j w_{t+j} w t + j
1 T log ∏ t = 1 T ∏ − c ≤ j ≤ c , j ≠ 0 p ( w t + j ∣ w t ) = 1 T ∑ t = 1 T ∑ − c ≤ j ≤ c , j ≠ 0 log p ( w t + j ∣ w t ) \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} = T 1 log t = 1 ∏ T − c ≤ j ≤ c , j = 0 ∏ p ( w t + j ∣ w t ) T 1 t = 1 ∑ T − c ≤ j ≤ c , j = 0 ∑ log p ( w t + j ∣ w t ) の最大化を目的としている。ここで、T T T w 1 , w 2 , w 3 , . . . , w T w_1, w_2, w_3, ..., w_T w 1 , w 2 , w 3 , . . . , w T c c c w I w_I w I w O w_O w O
p ( w O ∣ w I ) = exp ( v w O ′ T ⋅ v w I ) ∑ w i ∈ V exp ( v w i ′ T ⋅ v w I ) \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} p ( w O ∣ w I ) = ∑ w i ∈ V exp ( v w i ′ T ⋅ v w I ) exp ( v w O ′ T ⋅ v w I ) ここで、V V V v w I \boldsymbol{v}_{w_I} v w I v w O ′ \boldsymbol{v}^{\prime}_{w_O} v w O ′ v w I \boldsymbol{v}_{w_I} v w I v w O ′ \boldsymbol{v}^{\prime}_{w_O} v w O ′
見ての通り、分母の計算量が膨大なため、次のNegative Samplingと呼ばれる方法が提案されている。
新たに、ある単語のペア ( w I , w O ) (w_I, w_O) ( w I , w O ) p ( D = 1 ∣ w I , w O ) p(D=1 | w_I, w_O) p ( D = 1 ∣ w I , w O ) p ( D = 0 ∣ w I , w O ) p(D=0 | w_I, w_O) p ( D = 0 ∣ w I , w O ) σ \sigma σ
p ( D = 1 ∣ w I , w O ) = σ ( v w I T ⋅ v w O ′ ) p ( D = 0 ∣ w I , w O ) = 1 − p ( D = 1 ∣ w I , w O ) \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} p ( D = 1 ∣ w I , w O ) = p ( D = 0 ∣ w I , w O ) = σ ( v w I T ⋅ v w O ′ ) 1 − p ( D = 1 ∣ w I , w O ) と表すことができ、新たな目的関数、
log ( p ( D = 1 ∣ w I , w O ) ∏ w i ∈ V p ( D = 0 ∣ w I , w i ) ) \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} log ( p ( D = 1 ∣ w I , w O ) w i ∈ V ∏ p ( D = 0 ∣ w I , w i ) ) の最大化を考える。この時、全てのボキャブラリについて総乗を計算するのが大変なため、
k k k V n e g V_{\rm neg} V n e g
log ( p ( D = 1 ∣ w I , w O ) ∏ w i ∈ V n e g p ( D = 0 ∣ w I , w i ) ) = log p ( D = 1 ∣ w I , w O ) + ∑ w i ∈ V n e g log p ( D = 0 ∣ w I , w i ) = log σ ( v w I T ⋅ v w O ′ ) + ∑ w i ∈ V n e g log ( 1 − p ( D = 1 ∣ w I , w i ) ) = log σ ( v w I T ⋅ v w O ′ ) + ∑ w i ∈ V n e g log ( 1 − σ ( v w I T ⋅ v w i ′ ) ) = log σ ( v w I T ⋅ v w O ′ ) + ∑ w i ∈ V n e g log σ ( − v w I T ⋅ v w i ′ ) \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} = = = = log log log log log ( p ( D = 1 ∣ w I , w O ) w i ∈ V n e g ∏ p ( D = 0 ∣ w I , w i ) ) p ( D = 1 ∣ w I , w O ) + w i ∈ V n e g ∑ log p ( D = 0 ∣ w I , w i ) σ ( v w I T ⋅ v w O ′ ) + w i ∈ V n e g ∑ log ( 1 − p ( D = 1 ∣ w I , w i ) ) σ ( v w I T ⋅ v w O ′ ) + w i ∈ V n e g ∑ log ( 1 − σ ( v w I T ⋅ v w i ′ ) ) σ ( v w I T ⋅ v w O ′ ) + w i ∈ V n e g ∑ log σ ( − v w I T ⋅ v w i ′ ) もともとの目的関数の分母について、∣ V ∣ |V| ∣ V ∣ k k k k k k
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado and Jeff Dean, Distributed Representations of Words and Phrases and their Compositionality, NIPS2013
