素人の言語処理100本ノック:84

[言語処理100本ノック 2015](http://www.cl.ecei.tohoku.ac.jp/nlp100/)の挑戦記録です。環境はUbuntu 16.04 LTS ＋ Python 3.5.2 \:\: Anaconda 4.1.1 (64-bit)です。過去のノックの一覧は[こちら](http://qiita.com/segavvy/items/fb50ba8097d59475f760)からどうぞ。

## 第9章: ベクトル空間法 (I)
>[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)を用いよ．

### 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の要素だけを書き出せばよい．

#### 出来上がったコード：

```python:main.py
# coding: utf-8
import math
import pickle
from collections import Counter
from collections import OrderedDict
from scipy import sparse, io

fname_counter_tc = 'counter_tc'
fname_counter_t = 'counter_t'
fname_counter_c = 'counter_c'
fname_matrix_x = 'matrix_x'
fname_dict_index_t = 'dict_index_t'
N = 68031841		# 問題83で求めた定数

# Counter読み込み
with open(fname_counter_tc, 'rb') as data_file:
	counter_tc = pickle.load(data_file)
with open(fname_counter_t, 'rb') as data_file:
	counter_t = pickle.load(data_file)
with open(fname_counter_c, 'rb') as data_file:
	counter_c = pickle.load(data_file)

# {単語, インデックス}の辞書作成
dict_index_t = OrderedDict((key, i) for i, key in enumerate(counter_t.keys()))
dict_index_c = OrderedDict((key, i) for i, key in enumerate(counter_c.keys()))

# 行列作成
size_t = len(dict_index_t)
size_c = len(dict_index_c)
matrix_x = sparse.lil_matrix((size_t, size_c))

# f(t, c)を列挙して処理
for k, f_tc in counter_tc.items():
	if f_tc >= 10:
		tokens = k.split('\t')
		t = tokens[0]
		c = tokens[1]
		ppmi = max(math.log((N * f_tc) / (counter_t[t] * counter_c[c])), 0)
		matrix_x[dict_index_t[t], dict_index_c[c]] = ppmi

# 結果の書き出し
io.savemat(fname_matrix_x, {'matrix_x': matrix_x})
with open(fname_dict_index_t, 'wb') as data_file:
	pickle.dump(dict_index_t, data_file)
```

#### 実行結果：

行列$ X $はファイル「matrix_x.mat」に、各行に対応する単語一覧はファイル「dict_index_t」に出力します。
処理時間は手元のマシンで8分ほどでした。

### 単語をベクトルに変換

いよいよ単語のベクトル変換ですが、やることは単純です。
例えば仮に[問題82](http://qiita.com/segavvy/items/a8e269294f2c834cff08)で作った「context.txt」が次の17行だけだったとします。

```console:context.txtの例
Anarchism	is
Anarchism	a
Anarchism	political
Anarchism	philosophy
is	Anarchism
is	a
is	political
a	is
a	political
Anarchism	classifications
Anarchism	is
is	dual
is	classifications
is	Anarchism
is	usually
is	considered
is	a
```

この1カラム目が変換対象の単語$ t $で、これに対して2カラム目の文脈語$ c $の出現頻度を集計し、次のような行列を作ります。

| 単語$ t $↓＼文脈語$ c $→ |　is　|　a　|political|philosophy|Anarchism|classifications|dual|usually| considered|
|:-------:|:--------:|:--------:|:--------:|:--------:|:--------:|:--------:|:--------:|:--------:|:--------:|
| Anarchism |2|1|1|1|0|1|0|0|0|
| is |0|2|1|0|2|1|1|1|1|
| a |1|0|1|0|0|0|0|0|0|

これで1カラム目の単語$ t $を、その周辺で使われている文脈語のベクトルに変換できました。上の例では文脈語が9種類なので、9次元のベクトルに変換できたことになります。

なお、この例では単純にその単語$ t $と文脈語$ c $の出現頻度（＝$ f(t,c) $）を要素の値にしていますが、これだと精度に問題があります。そこで問題文にあるように出現頻度が10未満のものは無視し、10以上のものはPPMIを求めて値とします。

### PPMI（正の相互情報量）

上の例では$ f(t,c) $をそのまま使っていますが、これだと「a」や「the」などの高頻出単語との組み合わせ数が大きくなってしまい、本来知りたい単語同士の関連の強さを正しく示すことができません。

そこで$ f(t,c) $の代わりにPPMIを使います。分子に$ f(t,c) $があるので、その単語$ t $と文脈語$ c $が同時に出現すればするほど大きな値にはなりますが、高頻出の単語の影響を排除するため、その単語単独の出現頻度である$ f(t,* ) $と$ f(*,c) $を分母に持ってきてそれを相殺し、高頻出の単語に左右されずに単語$ t $と文脈語$ c $の関連の強さを値で示そうとしたものです。

詳しくは「PMI 相互情報量」などでググってみてください。

### SciPyのインストール

ほとんどの要素が0の行列を疎行列とかスパース行列とか呼びます。このような行列を効率良く扱う仕組みがSciPyというライブラリに備わっていることが分かったので、今回はそれを利用しました。

[問題73](http://qiita.com/segavvy/items/5ad0d5742a674bdf56cc)で高速な行列演算ができるNumPyを使い始めましたが、SciPyはそれを使った科学技術計算のライブラリです。Anacondaでインストールされていたようで、何もせずにそのまま使うことができました。オフィシャルサイトは[こちら](https://scipy.org)です。「SciPy」でググるとたくさん解説がヒットします。

### 疎行列の扱い
SciPyの[`scipy.sparse`](https://docs.scipy.org/doc/scipy/reference/sparse.html)が疎行列を扱うモジュールで、疎行列の実装アルゴリズムが何種類も用意されています。今回はその中の[`scipy.sparse.lil_matrix`](https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.lil_matrix.html#scipy.sparse.lil_matrix)を使いました。サイズを指定して行列を作成すると、全ての要素が0の行列ができあがりますので、あとは0ではない部分の要素を設定していくだけです。0ではない要素の数に応じて使用メモリが増えていく仕組みになっています。

### 行列の直列化
行列は[`scipy.io.savemat()`](https://docs.scipy.org/doc/scipy/reference/generated/scipy.io.savemat.html)で直列化でき、[`scipy.io.loadmat()`](https://docs.scipy.org/doc/scipy/reference/generated/scipy.io.loadmat.html)で戻せます。保存の際は辞書のようにキーを指定して保存します。読み込みの時もこのキーを指定して取り出す形になります。できあがるファイルはMATLABという数値解析ライブラリと互換のあるフォーマットで、拡張子を指定しないと「.mat」が自動的に付くようです。

余談ですが、MATLABはCourseraの[Machine Learning](https://www.coursera.org/learn/machine-learning)で演習に使う環境として出てきます。ただ少々お高いので、私は無償のOctaveを使っていました。互換があるはずなので、今回の出力ファイルはOctaveでも読めるのではないかと思います。

### 行列の各行と単語の対応表
行列$ X $の各行と各列に対応する単語一覧は、[問題04](http://qiita.com/segavvy/items/4e592dea2f828e5385ff)のコメントでsuzuki-hogeさんに教えていただいた[`collections.OrderedDict`](http://docs.python.jp/3/library/collections.html#collections.OrderedDict)を使い作成しました。単語と行列におけるインデックスの相互変換を高速にできるようにしています。通常の辞書を使わなかった理由は、通常の辞書だと格納順が維持されないためです。単語からインデックスへの変換は格納順に左右されないので良いのですが、インデックスから単語への変換は格納順が維持されないとできません。

なお、ファイルへの保存は、各行に対応する単語一覧のみです。各列に対応する単語一覧は、次の問題で次元を削減した際に不要になります。

　
85本目のノックは以上です。誤りなどありましたら、ご指摘いただけますと幸いです。
<hr>

*実行結果には、[100本ノックで用いるコーパス・データ](http://www.cl.ecei.tohoku.ac.jp/nlp100/#data)で配布されているデータの一部が含まれます。この第9章で用いているデータのライセンスは[クリエイティブ・コモンズ 表示-継承 3.0 非移植](https://creativecommons.org/licenses/by-sa/3.0/legalcode)（[日本語訳](https://creativecommons.org/licenses/by-sa/3.0/deed.ja)）です。*