word2vec その1

はじめに

　word2vecについてまとめます（その2を書きました）。

やりたいこと

　ある程度まとまった量の文章$A$を考える。これに出現する単語を重複を許さずに取り出すと、長さ$T$の単語列が出来上がる。 \begin{equation} W = \{w_1, \cdots, w_T\} \end{equation} いま、この単語列に含まれる単語$w_t$を含む文を$A$から取り出し、$w_t$の前後$b$個の範囲にある単語の集合$\Xi_{w_t}$を考える。 \begin{equation} \Xi_{w_t} = \{\xi_1^t, \cdots, \xi_C^t\} \end{equation} これは文脈を反映した集合である。たとえば、

Linux was originally developed as a free operating system for personal computers based on the Intel x86 architecture.

という文からは、$w_t={\rm developed}$、$b=1$のとき \begin{equation} \Xi_{{\rm developed}} = \{{\rm originally}, {\rm as}\} \end{equation} を、$w_t={\rm free}$のとき \begin{equation} \Xi_{{\rm free}} = \{{\rm a}, {\rm operating}\} \end{equation} を得る。$w_t$を指定したとき$\Xi_{w_t}$が実現する確率 \begin{equation} p(\Xi_{w_t}|w_t) \end{equation} を最大化するような単語の表現（ベクトル）を求めることがword2vec（Skip-Gram model）の目的である。

対数尤度の最大化

\begin{eqnarray} p(\Xi_t|w_t) &=& p(\xi_1^t, \cdots, \xi_C^t|w_t) \\ &=& \prod_{c=1}^{C}p(\xi_c^t|w_t) \end{eqnarray} 対数をとり、全ての単語について足し合わせたもの \begin{equation} L=\sum_{t=1}^T \sum_{c=1}^{C}\log{p(\xi_c^t|w_t)} \label{obj} \end{equation} を最大化する。

Softmax関数による計算

　$p(\xi_c^t|w_t)$としてSoftmax関数を仮定する。 \begin{equation} p(\xi_c^t|w_t)=\frac{\exp{\vec{u}^T_{\xi_c^{\;t}} \cdot \vec{v}_{w_t}}}{\sum_{w \in W} \exp{\vec{u}^T_w \cdot \vec{v}_{w_t}}} \end{equation} ここで、$\vec{v}$は入力単語を表現するベクトル、$\vec{u}$は出力単語を表現するベクトルである。$\sum_{w \in W}$は全単語について足し合わすことを意味する。モデルに入力する単語とモデルが出力する単語は区別されることに注意する。式(\ref{obj})に代入すると \begin{equation} L = \sum_{t=1}^T \sum_{c=1}^{C} \left\{ s(\xi_c^t, w_t) - \log{\sum_{w \in W} \exp{s(w, w_t)}} \right\} \end{equation} を得る。ただし、$s(a,b) = \vec{u}^T_a \cdot \vec{v}_b$とした。$W$の要素数が少なければ総和（$\sum_{w \in W}$）を取ることは可能であるが、現実の問題では$10^5\sim10^7$のオーダーであるため計算は困難である。

1次元ロジスティック回帰による計算（2分類問題への置き換え）

　単語$a$と$b$が与えられたとき、これらが同じ文脈上に存在する確率を$p(D=1|a, b)$、同じ文脈上に存在しない確率を$p(D=0|a, b)$とする。 このとき、次式のように書くことができる。 \begin{equation} p(D|a,b)=p(D=1|a, b)^{D}\; p(D=0|a, b)^{1-D} \end{equation} ここで以下を考える。

1. $w_t$が与えられた時の集合$\Xi_{w_t}$の各要素は、$w_t$と同じ文脈上に存在する。
2. $w_t$が与えられた時の集合$\Xi_{w_t}$に属さない要素は、$w_t$と同じ文脈上に存在しない。

これらを実現するには、次の対数尤度を最大化すればよい。 \begin{equation} L = \sum_{t=1}^T \sum_{c=1}^{C} \biggl\{ D_t \log{p(D_t=1|\xi^t_c, w_t)}+\sum_{w \not\in \Xi_{w_t}}(1-D_t)\log{p(D_t=0|w, w_t)} \biggr\} \label{f1} \end{equation} さらに \begin{eqnarray} p(D_t=1|a, b) &=& \sigma(s(a,b)) \\ p(D_t=0|a, b) &=& 1- \sigma(s(a,b)) = \sigma(-s(a,b)) \end{eqnarray} を仮定すれば（$\sigma(x)$はシグモイド関数）、1次元ロジスティック回帰の問題に帰着する。 式(\ref{f1})を最大にすることにより

1. 同じ文脈上にある2語の確率を高くし（第1項からの寄与）
2. 同じ文脈上にない2語の確率を高くする（第2項からの寄与）

ことが実現される。上記とほとんど同じことであるが次式を最大化する手法が存在する。 \begin{equation} L = \sum_{t=1}^T \sum_{c=1}^{C} \biggl\{ \log{p(D_t=1|\xi^t_c, w_t)}+\sum_{w \in {\rm Ng}}\log{p(D_t=0|w, w_t)} \biggr\} \end{equation} ${\rm Ng}$は、分布 \begin{equation} p(w) = \frac{U(w)^{0.75}}{\sum_{t=1}^{T}U(w_t)^{0.75}} \end{equation} に従ってサンプリングした$k$個の単語の集合である。$U(w)$は単語の頻度である。人為的に外れ(negative)データを導入することから、本手法をNegative Samplingと呼ぶ（その2を書きました）。