学術っぽくなるので、Qiitaで書いて良いか迷ったけど、とりあえず。
目的
P. Bojanowski*, E. Grave*, A. Joulin, T. Mikolov, Enriching Word Vectors with Subword Information (Facebook FastTextでReferenceに上がっている有名な論文)を理解すること。
ただし、理解の過程の試行錯誤も書く予定。
Model
General model
定義がわかりにくかったのと、多少気になることもあったので定式化し直す。
まず、vocabulary(つまりcorpusに出てくるwordの集合)を$W$で表すこととする。ここで紛らわしいが、vocabulary sizeも$W$で表し、$W = \{1,...,W\}$とする。
次にcorpus sizeを$T$とする。ここでも、1から$T$までのindex集合を同様に$T$で表す。つまり、$T=\{1,...,T\}$とする。corpusを finite sequenceとして、$w_\cdot:T \to W$とする。ここで、$w_j$はcorpus上のj番目の単語を意味する。
さらにj番目の単語$w_j$に関するcontextを$C_j$で表すこととする。これは一般に$C_\cdot: T \to 2^T$で定義される。$2^T$は$T$のpower setである。
また、j番目の単語$w_j$に関するcontextの重みを$m: T^2 \to [0, \infty)$で表すこととする。ただし、$m(c, j) = 0$ if $c \notin C_j$とする。
これらを用いskip gramのmodelの目的関数$J_\theta$は次のように与えられる。
J_\theta := \sum_{j \in T}\sum_{c \in T}m(c, j)\log p_\theta(w_c|w_j)
ここで、$m(c, j) = 1$ if $c \in C_j$とすると論文の設定となる。
脱線1 (目的関数の最適値と達成条件)
目的関数$J_\theta$は次のように書き換えられる。
\begin{align}
J_\theta &= \sum_{j \in T}\sum_{c \in T}m(c, j)\log p_\theta(w_c|w_j)\\
&= \sum_{\omega \in W}\sum_{j : w_j = \omega}\sum_{\tilde{\omega} \in W}\sum_{c: w_c = \tilde{\omega}}m(c, j)\log p_\theta(\tilde{\omega}|\omega)\\
&= \sum_{\omega \in W}\sum_{\tilde{\omega} \in W}\sum_{j : w_j = \omega}\sum_{c: w_c = \tilde{\omega}}m(c, j)\log p_\theta(\tilde{\omega}|\omega)\\
&= \sum_{\omega \in W}\sum_{\tilde{\omega} \in W}m(\tilde{\omega}, \omega)\log p_\theta(\tilde{\omega}|\omega)\\
&= \sum_{\omega \in W}M_\omega\sum_{\tilde{\omega} \in W}\frac{m(\tilde{\omega}, \omega)}{M_\omega}\log p_\theta(\tilde{\omega}|\omega)\\
&= \sum_{\omega \in W}M_\omega\sum_{\tilde{\omega} \in W}q(\tilde{\omega}|\omega)\log p_\theta(\tilde{\omega}|\omega)
\end{align}
ここで、
\begin{align}
m(\tilde{\omega}, \omega) &:=\sum_{c: w_c = \tilde{\omega}}\sum_{j : w_j = \omega}m(c, j)\\
M_\omega &:= \sum_{\tilde{\omega} \in W}m(\tilde{\omega}, \omega)\\
&=\sum_{c \in T}\sum_{j : w_j = \omega}m(c, j)\\
q(\tilde{\omega}|\omega) &:=\frac{m(\tilde{\omega}, \omega)}{M_\omega}
\end{align}
$q$は確率分布の性質を満たすことに注意。また$q(\cdot|\omega)$は論文の状況では単語$\omega$のcontext上の経験分布となる。
この時以下が成り立つ。
もしstatistical model $p_\theta$の表現能力が十分ならば、
\begin{align}
\max_\theta J_\theta &= -\sum_{\omega \in W}M_\omega H_q(\tilde{\Omega}|\omega)\\
&= \sum_{\omega \in W}M_\omega\sum_{\tilde{\omega} \in W}q(\tilde{\omega}|\omega)\log q(\tilde{\omega}|\omega)
\end{align}
証明
任意の$\theta$と$\omega$に対して、Kullback–Leibler divergenceの非負性から、
\begin{align}
0 &\leq D(q(\cdot|\omega)|| p_\theta(\cdot|\omega))\\
&= \sum_{\tilde{\omega} \in W}q(\tilde{\omega}|\omega)\log \frac{q(\tilde{\omega}|\omega)}{p_\theta(\tilde{\omega}|\omega)}\\
&= \sum_{\tilde{\omega} \in W}q(\tilde{\omega}|\omega)\log q(\tilde{\omega}|\omega) - \sum_{\tilde{\omega} \in W}q(\tilde{\omega}|\omega)\log p_\theta(\tilde{\omega}|\omega)
\end{align}
よって
\begin{align}
\sum_{\tilde{\omega} \in W}q(\tilde{\omega}|\omega)\log p_\theta(\tilde{\omega}|\omega) &\leq \sum_{\tilde{\omega} \in W}q(\tilde{\omega}|\omega)\log q(\tilde{\omega}|\omega)
\end{align}
また、等号成立は$q=p_\theta$のときでありそのときに限る。(QED)
モデルの表現能力が十分でない時には射影っぽくなるが、その考察はTODO
skip gramに置ける統計モデル
skip gramにおいて、統計モデル$p_\theta$はscoring function $s_\theta: W^2 \to \mathbb{R}$を用いて、
p_\theta(w_c|w_j) = \frac{1}{Z_{\theta, w_j}}\exp{s_\theta(w_j, w_c)}
と表すこととする。ここで$Z_{\theta, w_j}$は規格化定数であり、
Z_{\theta, w_j} := \sum_{\omega \in W}\exp{s_\theta(w_j, \omega)}
と定義される。つまり、scoring function $s_\theta(w_j, \cdot): W \to \mathbb{R}$に対するsoftmax functionとなっている。
なお、ほとんどの分散表現の定義において、scoring function $s_\theta$として
s_\theta(w_j, w_c) = \mathbf{u}^t_{w_j} \mathbf{v}_{w_c}
と内積で定義される。ここで、$\mathbf{u}_\cdot: W \to \mathbb{R}^d$であるとする。
$\mathbf{v}_\cdot$も同様。重要なのは、wordとcontextで別々の埋め込みがされることである。
機械学習では
実際の機械学習においては、このモデルに対して勾配法が適用されることがほとんどだと思うが、その計算つまり$\nabla_\theta J_\theta$を求めようとすると計算量が大変なことになる。
それゆえ、様々な工夫（近似）がなされるが、その工夫は大別して、
- Softmax-based Approach
- Sampling-based Approach
がある。前者はsoftmax関数を近似することを考えたもので、Hierarchical softmax等がそれにあたる。後者は
$p_\theta(w_c|w_j) = \frac{1}{Z_{\theta, w_j}}\exp{s_\theta(w_j, w_c)}$の時に、
\begin{align}
\nabla_\theta J_\theta &= \nabla_\theta\sum_{j \in T}\sum_{c \in T}m(c, j)\log p_\theta(w_c|w_j)\\
&= \sum_{j \in T}\sum_{c \in T}m(c, j)\nabla_\theta \log p_\theta(w_c|w_j)\\
&= \sum_{j \in T}\sum_{c \in T}m(c, j)\nabla_\theta\{s_\theta(w_j, w_c) - \log Z_{\theta, w_j} \}\\
&= \sum_{j \in T}\sum_{c \in T}m(c, j) \{\nabla_\theta s_\theta(w_j, w_c) - \nabla_\theta \log Z_{\theta, w_j} \}\\
&= \sum_{j \in T}\sum_{c \in T}m(c, j) \{\nabla_\theta s_\theta(w_j, w_c) - \nabla_\theta \log \sum_{\omega \in W}\exp{s_\theta(w_j, \omega)} \}\\
&= \sum_{j \in T}\sum_{c \in T}m(c, j) \{\nabla_\theta s_\theta(w_j, w_c) - \frac{1}{\sum_{\omega' \in W}\exp{s_\theta(w_j, \omega')}} \nabla_\theta \sum_{\omega \in W}\exp{s_\theta(w_j, \omega)}\}\\
&= \sum_{j \in T}\sum_{c \in T}m(c, j) \{\nabla_\theta s_\theta(w_j, w_c) - \sum_{\omega \in W}\frac{\exp{s_\theta(w_j, \omega)}}{\sum_{\omega' \in W}\exp{s_\theta(w_j, \omega')}} \nabla_\theta s_\theta(w_j, \omega)\}\\
&= \sum_{j \in T}\sum_{c \in T}m(c, j) \{\nabla_\theta s_\theta(w_j, w_c) - \sum_{\omega \in W}p_\theta(\omega|w_j) \nabla_\theta s_\theta(w_j, \omega)\}\\
&= \sum_{j \in T}\sum_{c \in T}m(c, j) \{\nabla_\theta s_\theta(w_j, w_c) - \mathbb{E}_{\Omega \sim p_\theta(\cdot|w_j)}[\nabla_\theta s_\theta(w_j, \Omega)]\}
\end{align}
であることを利用して、期待値の推定をsamplingによって近似する方法や、そもそも問題のフレームワークをあるwordがcontextに入るか否かの二値判別問題に焼き直すことによって行うNoise Contrastive EstimationやNegative Sampling等がある。
詳しくは、
Sebastian Ruder. On word embeddings - Part 2: Approximating the Softmax. http://sebastianruder.com/word-embeddings-softmax, 2016.
を参照。これに関しての解説記事も書く予定。(特にNegative samplingの数学的な捉え方についてはそちらで考察する予定）
なお、論文ではNegative samplingを採用している。
Subword model
ここまでみてわかる通り、分散表現の学習では単語のsyntacticな面のみを扱っておりmorphologicalな面は一切相手にしていない。Fast textではこのmorphologicalな面をvectorに反映させようとしている。
具体的には、単語をcharacterの列と捉え、その部分列をベクトル化する。そして、それらを足し合わせたものをword vectorとする（context vectorはそのまま)。部分列としては長さ3以上6以下を採用している。
例えば、morphologicalという単語があったとするこれから
<bow>mo, mor, orp, rph, pho, hol, olo, log, ogi, gic, ica, cal, al<eow>,
<bow>mor, morp, orph, rpho, phol, holo, olog, logi, ogic, gica, ical, cal<eow>,
<bow>morp, morph, orpho, rphol, pholo, holog, ologi, logic, ogica, gical, ical<eow>,
<bow>morph, morpho, orphol, rpholo, pholog, hologi, ologic, logica, ogical, gical<eow>
という列を構成し、それぞれにベクトルを付与する。なお、<bow>と<eow>はそれぞれ語頭と語尾を示す記号。
ここで、出現しうる列全体を$G$とおき、その要素を$g$で表す。また、単語$w$に関連する列を$\mathcal{G}_w \subset G$とする。Fast testでは、
scoring function $s_\theta$として
s_\theta(w, v) = \sum_{g \in \mathcal{G}_w}\mathbf{z}^t_{g} \mathbf{v}_{w}
も用いる。$\mathbf{z}_{g}$は$g$に対するベクトルである。
「も用いる」と上で書いたが、全ての単語をこのように部分列を用いて表現しているわけではない。出現頻度の高い上位$P$個の単語にはword vectorをそのまま適用している。Pが大きければ大きいほど元のモデルとの一致率は高くなり、$P=W$の時元のモデルとなる。当然、$P$が小さいほど、計算コストは大きくなる。