言語処理100本ノック-84(pandas使用):単語文脈行列の作成

[言語処理100本ノック 2015](http://www.cl.ecei.tohoku.ac.jp/nlp100/)の84本目「単語文脈行列の作成」の記録です。
40万×40万で1600億要素ある行列を作ります。一般的に1600億要素もあると超巨大サイズって感じですが、ほとんど0のスカスカな疎行列なので、行列をファイル保存しても7MBくらいです。疎行列を扱うパッケージの`scipy`はすごいですね。

# 参考リンク

|リンク|備考|
|:--|:--|
|[084.単語文脈行列の作成.ipynb](https://github.com/YoheiFukuhara/nlp100/blob/master/09.%E3%83%99%E3%82%AF%E3%83%88%E3%83%AB%E7%A9%BA%E9%96%93%E6%B3%95%20(I)/084.%E5%8D%98%E8%AA%9E%E6%96%87%E8%84%88%E8%A1%8C%E5%88%97%E3%81%AE%E4%BD%9C%E6%88%90.ipynb)|回答プログラムのGitHubリンク|
|[素人の言語処理100本ノック:84](http://qiita.com/segavvy/items/21455b802e34a9e49f92)|言語処理100本ノックで常にお世話になっています|
|[言語処理100本ノック 2015年版 (83,84)](http://kenichia.hatenablog.com/entry/2016/03/03/173146)|第9章では参考にしました|

# 環境

|種類|バージョン|内容|
|:--|:--|:--|
|OS|Ubuntu18.04.01 LTS|仮想で動かしています|
|pyenv|1.2.15|複数Python環境を使うことがあるのでpyenv使っています|
|Python|3.6.9|pyenv上でpython3.6.9を使っています<br>3.7や3.8系を使っていないことに深い理由はありません<br>パッケージはvenvを使って管理しています|

上記環境で、以下のPython追加パッケージを使っています。通常のpipでインストールするだけです。

|種類|バージョン|
|:--|:--|
|pandas|0.25.3|
|scipy|1.4.1|

# 課題
## [第9章: ベクトル空間法 (I)](http://www.cl.ecei.tohoku.ac.jp/nlp100/#ch9)
>[enwiki-20150112-400-r10-105752.txt.bz2](http://www.cl.ecei.tohoku.ac.jp/nlp100/data/enwiki-20150112-400-r10-105752.txt.bz2)は，2015年1月12日時点の英語のWikipedia記事のうち，約400語以上で構成される記事の中から，ランダムに1/10サンプリングした105,752記事のテキストをbzip2形式で圧縮したものである．このテキストをコーパスとして，単語の意味を表すベクトル（分散表現）を学習したい．第9章の前半では，コーパスから作成した単語文脈共起行列に主成分分析を適用し，単語ベクトルを学習する過程を，いくつかの処理に分けて実装する．第9章の後半では，学習で得られた単語ベクトル（300次元）を用い，単語の類似度計算やアナロジー（類推）を行う．
>
>なお，問題83を素直に実装すると，大量（約7GB）の主記憶が必要になる． メモリが不足する場合は，処理を工夫するか，1/100サンプリングのコーパス[enwiki-20150112-400-r100-10576.txt.bz2](http://www.cl.ecei.tohoku.ac.jp/nlp100/data/enwiki-20150112-400-r100-10576.txt.bz2)を用いよ．

今回は*「1/100サンプリングのコーパス[enwiki-20150112-400-r100-10576.txt.bz2](http://www.cl.ecei.tohoku.ac.jp/nlp100/data/enwiki-20150112-400-r100-10576.txt.bz2)」*を使っています。

### 84. 単語文脈行列の作成
>83の出力を利用し，単語文脈行列$ X $を作成せよ．ただし，行列$ X $の各要素$ X_{tc} $は次のように定義する．
>
> - $ f(t,c)≥10 $ならば，$ X_{tc}  = $ PPMI($ t $,$ c $) $ = $ max{log$ \frac{N×f(t,c)}{f(t,∗)×f(∗,c)} $,0}
> - $ f(t,c)<10 $ならば，$ X_{tc}=0 $
>
> ここで，PPMI($ t $,$ c $)はPositive Pointwise Mutual Information（正の相互情報量）と呼ばれる統計量である．なお，行列$ X $の行数・列数は数百万オーダとなり，行列のすべての要素を主記憶上に載せることは無理なので注意すること．幸い，行列$ X $のほとんどの要素は0になるので，非0の要素だけを書き出せばよい．

### 課題補足

例えば"I am a boy"という文に対して前回のノックの要領で、以下のファイルを作ったとします。

```
I	am
I	a
am	I
am	a
a	am
a	boy
boy	am
boy	a
```

上記に対して、イメージとしては以下のような行列を作ります。この例だと4列×4行なので疎ではない行列ですが、これが今回は約40万列×40万行なので、スカスカ状態の疎行列となります。

||I|am|a|boy|
|:-:|:-:|:-:|:-:|:-:|
|I||1|1||
|am|1||1||
|a||1||1|
|boy||1|1||

上記の行列は単純に行列の要素を1としていますが、ここに以下の値を設定します。PPMIに関しては[記事「自然言語処理における自己相互情報量 (Pointwise Mutual Information, PMI)」](https://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/)がわかりやすいです。

> - $ f(t,c)≥10 $ならば，$ X_{tc}  = $ PPMI($ t $,$ c $) $ = $ max{log$ \frac{N×f(t,c)}{f(t,∗)×f(∗,c)} $,0}
> - $ f(t,c)<10 $ならば，$ X_{tc}=0 $

# 回答

## 回答プログラム [084.単語文脈行列の作成.ipynb](https://github.com/YoheiFukuhara/nlp100/blob/master/09.%E3%83%99%E3%82%AF%E3%83%88%E3%83%AB%E7%A9%BA%E9%96%93%E6%B3%95%20(I)/084.%E5%8D%98%E8%AA%9E%E6%96%87%E8%84%88%E8%A1%8C%E5%88%97%E3%81%AE%E4%BD%9C%E6%88%90.ipynb)

```python
import math

import pandas as pd
from scipy import sparse, io

# 単語tと文脈語cの共起回数を読み込み、9回以下の共起回数の組み合わせは除去
def read_tc():
    group_tc = pd.read_pickle('./083_group_tc.zip')
    return group_tc[group_tc > 9]

group_tc = read_tc()

group_t = pd.read_pickle('./083_group_t.zip')
group_c = pd.read_pickle('./083_group_c.zip')

matrix_x = sparse.lil_matrix((len(group_t), len(group_c)))


for ind ,v in group_tc.iteritems():
    ppmi = max(math.log((68000317 * v) / (group_t[ind[0]] * group_c[ind[1]])), 0)
    matrix_x[group_t.index.get_loc(ind[0]), group_c.index.get_loc(ind[1])] = ppmi

# 疎行列を確認
print('matrix_x Shape:', matrix_x.shape)
print('matrix_x Number of non-zero entries:', matrix_x.nnz)
print('matrix_x Format:', matrix_x.getformat())

io.savemat('084.matrix_x.mat', {'x': matrix_x})
```

## 回答解説
pandasの`read_pickle`関数を使って前回のノックで保存したファイルを読んでいます。zip形式もそのまま読むだけで大丈夫です。ただ、解凍している分、処理時間がプラスされます(関数全体で13秒程度かかっています)。
読んだ後に共起回数が10回未満のレコードを捨てています。捨てる前のファイル全体をメモリに残したくなかったので、わざわざ関数`read_tc`を作りました。

```python
# 単語tと文脈語cの共起回数を読み込み、9回以下の共起回数の組み合わせは除去
def read_tc():
    group_tc = pd.read_pickle('./083_group_tc.zip')
    return group_tc[group_tc > 9]
```

残りの2ファイルはX回以下の切り捨てなどないので、そのまま読み込んでいます。

```python
group_t = pd.read_pickle('./083_group_t.zip')
group_c = pd.read_pickle('./083_group_c.zip')
```

ここでscipyを使って疎行列の変数`matrix_x`を作っています。対象語(Target Word)と文脈語(Context Word)の数を掛け合わせます。疎行列を扱うにはいくつか種類があるのですが、入力はlilというフォーマットを使うので`lil_matrix`関数で行列を作っています。

```python
matrix_x = sparse.lil_matrix((len(group_t), len(group_c)))
```

以下が今回のノックのメイン部分です。PPMIを計算し、疎行列に設定していきます。`68000317`としている部分は前回ノックで得た値を設定しています。

```python
for ind ,v in group_tc.iteritems():
    ppmi = max(math.log((68000317 * v) / (group_t[ind[0]] * group_c[ind[1]])), 0)
    matrix_x[group_t.index.get_loc(ind[0]), group_c.index.get_loc(ind[1])] = ppmi
```

上記のPPMI計算式を[記事「言語処理100本ノック 2015年版 第9章再訪(1)」](http://kenichia.hatenablog.com/entry/2016/03/05/201304)を参考に展開式でもやってみたのですが、速くならなかったので不採用としました(`LOG_N`は事前に計算済)。むしろ遅くなっています(私のやり方が間違っている？)。

```python
ppmi = max(LOG_N + math.log(v) - math.log ( group_t[ind[0]] ) - math.log( group_c[ind[1]] ), 0)
```

作成した疎行列について確認します。

```python
print('matrix_x Shape:', matrix_x.shape)
print('matrix_x Number of non-zero entries:', matrix_x.nnz)
print('matrix_x Format:', matrix_x.getformat())
```

以下の情報が出力されます。2行目は入力されているエントリの数なのですが、40万×40万で1600億要素のうちの45万要素なので0.1%にも満たない密度であることがわかります。

```bash
matrix_x Shape: (388836, 388836)
matrix_x Number of non-zero entries: 447875
matrix_x Format: lil
```

最後に保存です。拡張子は"mat"でMATLAB/Octaveで使えるフォーマットのようです。有名なCoursera 機械学習入門のオンラインコースの演習で使うやつです。興味がある方は[「Coursera機械学習入門オンライン講座虎の巻(文系社会人にオススメ)」](https://qiita.com/FukuharaYohei/items/b2143413063376e97948)を参照ください。

```python
io.savemat('084.matrix_x.mat', {'x': matrix_x})
```

# Tips: 変数使用メモリ
各変数の使用メモリはこんなでした。

|変数|メモリ|圧縮保存したファイルサイズ|
|:-:|:-:|:-:|
|                  group_c|  40MB|3MB|
|                  group_t|  40MB|3MB|
|                 group_tc|  64MB|104MB|

使用メモリは以下のコードを入れて調べています。完全に[記事「[Jupyter(IPython)上でメモリ食っている変数を探し出して削除する]」](https://qiita.com/AnchorBlues/items/883790e43417640140aa)からのコピペです。

```python
print("{}{: >25}{}{: >10}{}".format('|','Variable Name','|','Memory','|'))
print(" ------------------------------------ ")
for var_name in dir():
    if not var_name.startswith("_") and sys.getsizeof(eval(var_name)) > 10000: #ここだけアレンジ
        print("{}{: >25}{}{: >10}{}".format('|',var_name,'|',sys.getsizeof(eval(var_name)),'|'))
```