Skip gramからGloVe(WIP)

最近、[Stanfordの講義](http://web.stanford.edu/class/cs224n/syllabus.html)を勉強している。分散表現の部分がとりあえず終わったので、自分の理解を記述する。

## corpusの定義

単語の分散表現を学習するのに当たって、どうしても必要なものがcorpusである。corpusとは、文章の集まりである。通常corpusは大規模であり、構造化され、何か情報が付与されているが、ここでは単純に文章をシリアルに収容したものを考える。これを数学的に次のように定義する。
corpus $\mathcal{C}$は三つ組$(V, T, w)$によって、定義される。ここで、$V$はVocabulary集合、すなわちcorpus $\mathcal{C}$に出現する単語の集合、$T$はcorpusの長さ、 $w$は関数$w:\\{1,\ldots, T\\} \to V$つまり、corpusの何番目にどの単語が出てくるのかを意味する関数であり、$j$番目の単語を$w_j$と表記することとする。

## contextの定義

単語の分散表現の学習では単語をその単語の前後に現れる単語の関係として理解する。

John Rupert Firthの

> You shall know a word by the company it keeps (Firth, J. R. 1957:11)

をそのままやることになる。このある単語の「前後に現れる単語」のことをある単語のcontextと呼ぶが、これは次のように拡張される。

$j$番目の単語$w_j$のcontext $C_j$はcorpus $\mathcal{C}$のindex集合$\\{1,...,T\\}$の部分集合である。すなわちcontextは関数$C : \\{1,...,T\\}\to 2^{\\{1,...,T\\}}$である。ここで、$2^{\\{1,...,T\\}}$はpower setである。

通常は、window size $l$を導入して、$C_j = \\{j-l, ..., j-1, j+1, ..., j+l \\}$となることが多い（これは両側の例だが、片側のこともある）。

## skip gramの目的関数

skip gramとはある種のn-gramの拡張である。n-gramとは文章をn-1次のMarkov chainとみなすものである。
(最も簡単な）skip gramは文章を

```math
P(W_{j+k}|W_j),\;k \neq 0
```

でモデル化する。
さて、skip gramで最尤推定を行うと目的関数は次のようになる。

```math
J(\theta|\mathcal{C}, C) = \prod_{i=1}^T\prod_{j \in C_i}p_{\theta}(w_j|w_i)
```

ここで$p_\theta$は統計モデルである。この目的関数を最大化するパラメータ$\theta$を得るのが学習となる。なお、この目的関数は対数をとっても同等であるので、

```math
\begin{align}
\hat{J}(\theta|\mathcal{C}, C) &=　\log J(\theta|\mathcal{C}, C) \\
&= \sum_{i=1}^T\sum_{j \in C_i}\log p_{\theta}(w_j|w_i)
\end{align}
```

ともかける。

## A slight generalization of the objective function

前項の目的関数は、contextに入るかどうかを同列に扱っている。しかし、ある単語が形容詞だとして、形容詞として掛かる名詞と同時に現れてはいるが、直接の文法的な関係のない名詞が同列に扱われるのは、直感的にはあまり精度が出ないように思われる。
このように、関係性によって、もしくは別の指標によって重要度を変更できるようにcontextをweightに拡張する。
重み$m$を$m: \\{1,...,T\\}^2 \to [0, \infty)$で定義する。ここで、$m(i, j)$はcenter word $i$番目の単語から$j$番目の単語への関係性に対する重みである。
この重みを用いて目的関数を次のように拡張する。

```math
\begin{align}
J(\theta|\mathcal{C}, m)
&= \sum_{i=1}^T\sum_{j=1}^T m(i,j) \log p_{\theta}(w_j|w_i)
\end{align}
```

ここで

```math
m(i, j) = \left\{
\begin{array}{ll}
1 & (j \in C_i) \\
0 & (j \notin C_i)
\end{array}
\right.
```

とすると、元の目的関数と一致する。[前記事](http://qiita.com/takuyakubo/items/82cf44d274b3d9dae180)にも書いた通り、この目的関数は、

```math
J(\theta|\mathcal{C}, m) = \sum_{\omega \in V}M_\omega\sum_{\tilde{\omega} \in V}q(\tilde{\omega}|\omega)\log p_\theta(\tilde{\omega}|\omega),
```
where

```math
\begin{align}
m(\omega, \tilde{\omega})　&:=\sum_{i: w_i = \omega}\sum_{j : w_j = \tilde{\omega}}m(i, j),\\
M_\omega &:= \sum_{\tilde{\omega} \in V}m(\omega, \tilde{\omega})\\
&=\sum_{j=1}^T\sum_{i : w_i = \omega}m(i, j),\\
q(\tilde{\omega}|\omega) &:=\frac{m(\omega, \tilde{\omega})}{M_\omega}.
\end{align}
```

と書け、ここから、


```math
\tilde{J}(\theta|\mathcal{C}, m) = \sum_{\omega \in V}M_\omega D(q(\cdot|\omega)|| p_\theta(\cdot|\omega)),
```

というコスト関数が得られる。ここで、$D(q||p)$はKullback–Leibler divergenceである。このコスト関数の最小化問題と$J(\theta|\mathcal{C}, m)$の最大化は同値である。

## 考察１
上記$q(\tilde{\omega}|\omega)$だが、元々のcontextを使ったものではこれは、$\omega$のcontext上のempirical distributionとなる。これを$P_{\omega, \tilde{\omega}}$という行列表示をすることがある。また、$m(\omega, \tilde{\omega}) = X_{\omega, \tilde{\omega}}$, $M_\omega = X_\omega$という表示をすることがある。(indexは異なるが、GloVeの論文PDF[Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014.](https://nlp.stanford.edu/pubs/glove.pdf)ではこの表示が使われている)

## 考察2
KL divergenceなのでf-divergenceに一般化できる。

## 最適化の方向性と GloVe
$\tilde{J}(\theta|\mathcal{C}, m)$の表現で分かる通り、基本的に分布$p_\theta$を分布$q$に近似するというのが最適化の方向である。この近似精度の評価をdivergenceでやったのがskip gram,　概ね$\log P - \log Q$のフロベニウスノルムでやったのがGloveである。ただし、ここでの$\log$は成分毎に対数をとったものである。
TBD