『ゼロから作るDeep Learning❷』2.4 カウントベースの手法の改善　資料

# 2.4 カウントベースの手法の改善

本節の概要

* 分散表現を改善する
    * 正の相互情報量(PPMI)を使う（難易度：中）
    * 次元削減のために特異値分解(SVD)を使う（難易度：高）
* もっと大きなデータに適用してみる（計算時間：大）

----
### 分散表現の改善

* そもそも、なんで共起行列を作ったか？→単語の分散表現のため
* その意味では、単語の共起行列は「単語の（ある種の）分散表現」といえる
* とはいえ、ただの共起行列では微妙なので、改良する

----
## 2.4.1　相互情報量

* 微妙な点その１：高頻度な単語を適切に扱えない
* 「the」「car」「drive」では、「car」と「drive」の関連性が高そうだが、「the」と「car」の関連の方が強く出る
  * そもそも「the」はたくさん出現するため共起することが多い
  * でも、出現回数が小さいのに共起する方が重要では？
* それを考慮する指標として、「相互情報量」を使う

----

### 自己相互情報量

* 相互情報量(Pointwise Mutual Information)
    * 「自己相互情報量」「点相互情報量」という訳語も使われる。
    * Wikipediaの https://ja.wikipedia.org/wiki/相互情報量 は意味が微妙に違うのに注意。
        * こちらの方は情報理論の方で出てくる用語っぽい。
        * 自然言語処理では自己相互情報量のことを「相互情報量」と呼ぶ（らしい）ので要注意。PMIと呼べばよい？

----

### PMIの定義


```math
\begin{align}
PMI(x,y) &= log_2 \frac{P(x\cdot y)}{P(x)P(y)} \\
 &= log_2 \frac{\frac{C(x,y)}{N}}{\frac{C(x)}{N}\cdot\frac{C(y)}{N}} = log_2 \frac{C(x,y)\cdot N}{C(x)\cdot C(y)}
\end{align}
```

$P(x)$ : xが起こる確率
$P(y)$ : yが起こる確率
$P(x\cdot y)$ : xとyが同時に起こる確率
$C(x)$ : xの出現回数
$N$ : 全語彙数

$ y = log_2(x)$ のグラフ

![PMI.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/4293/1c9a446b-4281-7d48-905d-b263dc666c44.png)

----

### PPMIの定義

* xとyが共起しない場合、$P(x,y)=0$ なので、 $log_2(0)=-\infty$となり、こまる
* そのため、正の相互情報量(Positive PMI)を使う

```math
\begin{align}
PPMI(x,y) &= max(0, PMI(x,y)) \\
 &= max(0, log_2 \frac{C(x,y)\cdot N}{C(x)\cdot C(y)})
\end{align}
```

$y=max(0, log_2(x))$ のグラフ

![PPMI.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/4293/1b665858-8fd5-a021-a56c-d0710e541319.png)

----
### 式2.6のバグ（？）

`total < 100`の場合、`Verbose=true`にすると落ちるのでは??

```python
import sys
sys.path.append('..')
import numpy as np
from common.util import preprocess, create_co_matrix, cos_similarity, ppmi

text = 'You say goodbye and I say hello.'
corpus, word_to_id, id_to_word = preprocess(text)
vocab_size = len(word_to_id)
C = create_co_matrix(corpus, vocab_size)
W = ppmi(C, True)
```

実行結果:

```console
$ python3 ppmi2.py 
Traceback (most recent call last):
  File "ppmi2.py", line 11, in <module>
    W = ppmi(C, True)
  File "../common/util.py", line 144, in ppmi
    if cnt % (total//100) == 0:
ZeroDivisionError: integer division or modulo by zero
```

----
#### 普通に実行

ppmi()の定義

```python
def ppmi(C, verbose=False, eps = 1e-8):
    '''PPMI（正の相互情報量）の作成

    :param C: 共起行列
    :param verbose: 進行状況を出力するかどうか
    :return:
    '''
    M = np.zeros_like(C, dtype=np.float32)
    N = np.sum(C)
    S = np.sum(C, axis=0)
    total = C.shape[0] * C.shape[1]
    cnt = 0

    for i in range(C.shape[0]):
        for j in range(C.shape[1]):
            pmi = np.log2(C[i, j] * N / (S[j]*S[i]) + eps)
            M[i, j] = max(0, pmi)

            if verbose:
                cnt += 1
                if cnt % (total//100) == 0:
                    print('%.1f%% done' % (100*cnt/total))
    return M
```

ポイント：　小さい数 $eps$ を加えることで、$log_2(0)$になるのを防いでいる

----
#### 普通に実行

```python
# coding: utf-8
import sys
sys.path.append('..')
import numpy as np
from common.util import preprocess, create_co_matrix, cos_similarity, ppmi

text = 'You say goodbye and I say hello.'
corpus, word_to_id, id_to_word = preprocess(text)
vocab_size = len(word_to_id)
C = create_co_matrix(corpus, vocab_size)
W = ppmi(C)

np.set_printoptions(precision=3)  # 有効桁３桁で表示
print('covariance matrix')
print(C)
print('-'*50)
print('PPMI')
print(W)
```
実行結果：

```console
$ python3 ppmi.py 
covariance matrix
[[0 1 0 0 0 0 0]
 [1 0 1 0 1 1 0]
 [0 1 0 1 0 0 0]
 [0 0 1 0 1 0 0]
 [0 1 0 1 0 0 0]
 [0 1 0 0 0 0 1]
 [0 0 0 0 0 1 0]]
--------------------------------------------------
PPMI
[[0.    1.807 0.    0.    0.    0.    0.   ]
 [1.807 0.    0.807 0.    0.807 0.807 0.   ]
 [0.    0.807 0.    1.807 0.    0.    0.   ]
 [0.    0.    1.807 0.    1.807 0.    0.   ]
 [0.    0.807 0.    1.807 0.    0.    0.   ]
 [0.    0.807 0.    0.    0.    0.    2.807]
 [0.    0.    0.    0.    0.    2.807 0.   ]]
````

---
## 2.4.3 次元削減

現状の問題点（微妙な点その２）

* この方法だと、語彙数が増えると次元も増える
* 10万語だと10万次元？！
    * そんなに次元があってもうれしくない（計算資源の問題）
    * 0が多いのは無駄（疎な行列,sparse）
    * 本質的に近いものも別々に表現されてしまう
* そこで次元削減

----
### 次元削減(dimension reduction)

* 次元削減: 次元を減らすこと（そのまま）
* 本書では特異値分解を使うが、他にも主成分分析とかいろいろある（らしい）
* 「本質的な情報はあまり減らさないようにする」ことが重要

----

### 特異値分解

（この辺は行列用語というか数学用語が頻出してつらい…）

行列の変形。M x Nの行列Cは以下のように分解できる。

$$C = U\Sigma V^T$$

$U$はM x M、$V$はN x Nの正方行列（＝行と列のサイズが同じ行列）。

$U$ と $V$ は「直交行列」になる。直交行列とは、転置行列 $A^T$と逆行列$A^{-1}$が等しくなる行列（転置行列は行と列をひっくり返した行列）。

```math
\begin{align}
U^T \cdot U &= U \cdot U^T = I \\
V^T \cdot V &= V \cdot V^T = I
\end{align}
```
（$I$ は単位行列）

直感的には、直交行列は回転とか反転とかのような、距離を変えない変換と考えると良さそう。「本質的な情報」を分かりやすく$\Sigma$で表せられるようにする。

$\Sigma$ は対角行列成分のみ、大きい順に並んでいて、それ以外は0。むしろ、そういう並びに $\Sigma$ が並ぶように、$U$と$V$を決めるイメージ、で良さそう。与えられた$C$に対して$\Sigma$は一意に決まるが、$U$と$V$は一意ではない（らしい）。

----
### 特異値分解の Σ の例

```math
\left(
\begin{matrix}
\sigma_1 & 0 & 0 \\
0 & \sigma_2 & 0 \\
0 & 0 & \sigma_3 \\
0 & 0 & 0 \\
0 & 0 & 0 
\end{matrix}
\right)
```

ちなみに、特異値をそれぞれ２乗した値の合計（＝特異値の２乗和）は、元の行列の全要素の２乗和に等しくなる（らしい）。これをフロベニウスノルムと呼ぶ([Wikipedia:行列ノルム#フロベニウスノルム](https://ja.wikipedia.org/wiki/%E8%A1%8C%E5%88%97%E3%83%8E%E3%83%AB%E3%83%A0#%E3%83%95%E3%83%AD%E3%83%99%E3%83%8B%E3%82%A6%E3%82%B9%E3%83%8E%E3%83%AB%E3%83%A0))。

----

### 特異値分解を使った次元削減

ここまでの特異値分解は値を変えない（＝等価な）変換。ここからは、（等価ではない）近似した行列 $C' ( \fallingdotseq C)$ を求める。

$\Sigma$ は左上から右下へ大きい順に数が並んでいるため、下の方から削る（＝０にする）と次元が削減できる。べんり！　というか、この便利さのために特異値分解を使ってるという理解。

直感的には、値が小さいやつを0にするので影響が小さい（らしい）。

----

## 2.4.3 SVDによる次元削減

Pythonで実行する。numpyのlinalg.svdを使う。

```python
W = ppmi(C)

# SVD
U, S, V = np.linalg.svd(W)
```

高速化のため、Truncated SVDという手法もある

https://scikit-learn.org/stable/modules/generated/sklearn.decomposition.TruncatedSVD.html

----
## 2.4.4　PTBデータセット

本格的なデータとして、PTBを扱ってみる。

* Penn Treebank (PTB) https://web.archive.org/web/20131109202842/http://www.cis.upenn.edu/~treebank/
* Treebank: コーパスの一種で、構文的・意味的なアノテーションが付与されているもの。Seed bank(種子銀行)やBlood bankのアナロジーだそう（Wikipediaより）。
* コーパス: 言語学・自然言語処理などで使われる、大規模かつ構造化されたテキストデータセット。

ここのPTBコーパスはタグや構文解析木のデータがすっぱり落とされた、ただのテキストになっている。Treeとは一体…。

オリジナルのPTBは[NLTK Corpora](http://www.nltk.org/nltk_data/)よりダウンロードできるぽい（元サイトが消滅しているのでほんとにオリジナルかどうかは不明）。

----
### Penn Treebank（NLTK Corporaより）

rawデータ

```wsj_0002
Rudolph Agnew, 55 years old and former chairman of Consolidated Gold Fields PLC, was named a nonexecutive director of this British industrial conglomerate. 
```

parsedデータ

```wsj_0002.prd
( (S (NP-SBJ-1 (NP Rudolph Agnew)
               ,
               (UCP (ADJP (NP 55 years)
			  old)
		    and
		    (NP (NP former chairman)
			(PP of
			    (NP Consolidated Gold Fields PLC))))
               ,)
     (VP was
         (VP named
             (S (NP-SBJ *-1)
		(NP-PRD (NP a nonexecutive director)
			(PP of
			    (NP this British industrial conglomerate))))))
     .))
```

taggedデータ

```wsj_0002.pos
[ Rudolph/NNP Agnew/NNP ]
,/, 
[ 55/CD years/NNS ]
old/JJ and/CC 
[ former/JJ chairman/NN ]
of/IN 
[ Consolidated/NNP Gold/NNP Fields/NNP PLC/NNP ]
,/, was/VBD named/VBN 
[ a/DT nonexecutive/JJ director/NN ]
of/IN 
[ this/DT British/JJ industrial/JJ conglomerate/NN ]
./. 
```

----
## 2.4.5　PTBデータセットでの評価

SVDの高速化のため、sklearnの`randomized_svd()`を使う。

https://scikit-learn.org/stable/modules/generated/sklearn.utils.extmath.randomized_svd.html#sklearn.utils.extmath.randomized_svd

```python
print('calculating SVD ...')
try:
    # truncated SVD (fast!)
    from sklearn.utils.extmath import randomized_svd
    U, S, V = randomized_svd(W, n_components=wordvec_size, n_iter=5,
                             random_state=None)
except ImportError:
    # SVD (slow)
    U, S, V = np.linalg.svd(W)
```

```console
$ cd ch02
$ python3 count_method_big.py
counting  co-occurrence ...
calculating PPMI ...
1.0% done
2.0% done
3.0% done

92.0% done
93.0% done
94.0% done
95.0% done
96.0% done
97.0% done
98.0% done
99.0% done
100.0% done
calculating SVD ...

[query] you
 i: 0.700317919254303
 we: 0.6367185115814209
 anybody: 0.565764307975769
 do: 0.563567042350769
 'll: 0.5127798318862915

[query] year
 month: 0.6961644291877747
 quarter: 0.6884941458702087
 earlier: 0.6663320660591125
 last: 0.6281364560127258
 next: 0.6175755858421326

[query] car
 luxury: 0.6728832125663757
 auto: 0.6452109813690186
 vehicle: 0.6097723245620728
 cars: 0.6032834053039551
 corsica: 0.5698372721672058

[query] toyota
 motor: 0.7585658431053162
 nissan: 0.7148030996322632
 motors: 0.6926157474517822
 lexus: 0.6583304405212402
 honda: 0.6350275278091431
```

----
### 分布表現(distributional representation)と分散表現(distributed representation)

使い分ける場合があるぽい

* [What's the difference between distributed and distributional (semantic) representations?](https://www.quora.com/Whats-the-difference-between-distributed-and-distributional-semantic-representations)
* 『ウェブデータの機械学習』も分けてるよう。

* 分布表現: 分布仮説に基づく高次元・疎な表現（本書の第２章）
* 分散表現: 低次元・密な表現（本書の第３章）

----
### 参考文献

* [言語処理のための機械学習入門（コロナ社の自然言語処理シリーズ）](http://www.coronasha.co.jp/np/isbn/9784339027518/) 相互情報量について参考になる
* [ウェブデータの機械学習（講談社の機械学習プロフェッショナルシリーズ）](http://bookclub.kodansha.co.jp/product?item=0000147669) SVDについて大変詳しい（けどちょっと難しい）
* [朱鷺の杜Wiki 特異値分解](http://ibisforest.org/index.php?%E7%89%B9%E7%95%B0%E5%80%A4%E5%88%86%E8%A7%A3)
* [直交行列の５つの定義と性質の証明](https://mathtrain.jp/orthogonal)
* [自然言語処理における自己相互情報量 (Pointwise Mutual Information, PMI)](http://camberbridge.github.io/2016/07/08/%E8%87%AA%E5%B7%B1%E7%9B%B8%E4%BA%92%E6%83%85%E5%A0%B1%E9%87%8F-Pointwise-Mutual-Information-PMI-%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6/)
* [朱鷺の杜Wiki 次元削減](http://ibisforest.org/index.php?%E6%AC%A1%E5%85%83%E5%89%8A%E6%B8%9B)
* [Wikipedia:直交行列](https://ja.wikipedia.org/wiki/%E7%9B%B4%E4%BA%A4%E8%A1%8C%E5%88%97)
* [Wikipedia:特異値分解](https://ja.wikipedia.org/wiki/%E7%89%B9%E7%95%B0%E5%80%A4%E5%88%86%E8%A7%A3)
* [特異値分解の定義，性質，具体例](https://mathtrain.jp/svd)
* [Wikipedia:Treebank](https://en.wikipedia.org/wiki/Treebank)
* [Pythonで特異値分解(SVD)を理解する](https://ohke.hateblo.jp/entry/2017/12/14/230500)
* [NLTK Corpora
](http://www.nltk.org/nltk_data/)