Golangで言語処理100本ノック2015 第9章: ベクトル空間法 (I)

言語処理100本ノック 2015の第9章: ベクトル空間法 (I)の10問です。

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を用いよ.

※コード中ではr100コーパスで実装している箇所もありますが、難関と評判のQ85でハマりr10コーパスにしています。

80. コーパスの整形

文を単語列に変換する最も単純な方法は,空白文字で単語に区切ることである. ただ,この方法では文末のピリオドや括弧などの記号が単語に含まれてしまう. そこで,コーパスの各行のテキストを空白文字でトークンのリストに分割した後,各トークンに以下の処理を施し,単語から記号を除去せよ.

  • トークンの先頭と末尾に出現する次の文字を削除: .,!?;:()[]'"
  • 空文字列となったトークンは削除

以上の処理を適用した後,トークンをスペースで連結してファイルに保存せよ.

gist4ea9f91550e8b265f80751d8bd005e6b

❯ go run q80.go
❯ head -3 ../data/q80.out.txt
Anarchism
Anarchism is political philosophy that advocates stateless societies often defined as self-governed voluntary institutions but that several authors have defined as more specific institutions based on non-hierarchical free associations Anarchism holds the state to be undesirable unnecessary or harmful While anti-statism is central anarchism entails opposing authority or hierarchical organisation in the conduct of human relations including but not limited to the state system
As subtle and anti-dogmatic philosophy anarchism draws on many currents of thought and strategy Anarchism does not offer fixed body of doctrine from single particular world view instead fluxing and flowing as philosophy There are many types and traditions of anarchism not all of which are mutually exclusive Anarchist schools of thought can differ fundamentally supporting anything from extreme individualism to complete collectivism Strains of anarchism have often been divided into the categories of social and individualist anarchism or similar dual classifications Anarchism is usually considered radical left-wing ideology and much of anarchist economics and anarchist legal philosophy reflect anti-authoritarian interpretations of communism collectivism syndicalism mutualism or participatory economics

トークンの先頭末尾と書いてありますが、"-izein").のようなトークンで不要な記号の除去ができないので、一つの記号を除去したあと再帰的にremoveSymbol()を呼び出すことで、きちんと不要な記号を削除できるようにしました。

81. 複合語からなる国名への対処

英語では,複数の語の連接が意味を成すことがある.例えば,アメリカ合衆国は"United States",イギリスは"United Kingdom"と表現されるが,"United"や"States","Kingdom"という単語だけでは,指し示している概念・実体が曖昧である.そこで,コーパス中に含まれる複合語を認識し,複合語を1語として扱うことで,複合語の意味を推定したい.しかしながら,複合語を正確に認定するのは大変むずかしいので,ここでは複合語からなる国名を認定したい.

インターネット上から国名リストを各自で入手し,80のコーパス中に出現する複合語の国名に関して,スペースをアンダーバーに置換せよ.例えば,"United States"は"United_States","Isle of Man"は"Isle_of_Man"になるはずである.

gistcfab66b743e9507879fb63a272086782

❯ go run q81.go
❯  head -10 ../data/q81.out.txt | grep United
The term anarchism isma compound word composed from the word anarchy and the suffix -ism themselves derived respectively from the Greek i.e anarchy from anarchos meaning one without rulers from the privative prefix ἀν- an- i.e without and archos i.e leader ruler cf archon or arkhē i.e authority sovereignty realm magistracy and the suffix or -ismos -isma from the verbal infinitive suffix -ίζειν -izein The first known use of this word was in 1539."Anarchist was the term adopted by Maximilien de Robespierre to attack those on the left whom he had used for his own ends during the French Revolution but was determined to get rid of though among these anarchists there were few who exhibited the social revolt characteristics of later anarchists There would be many revolutionaries of the early nineteenth century who contributed to the anarchist doctrines of the next generation such as William Godwin and Wilhelm Weitling but they did not use the word anarchist or anarchism in describing themselves or their beliefs Pierre-Joseph Proudhon was the first political philosopher to call himself an anarchist marking the formal birth of anarchism in the mid-nineteenth century Since the 1890s from France the term libertarianism has often been used as synonym for anarchism and was used almost exclusively in this sense until the 1950s in the United_States its use as synonym is still common outside the United_States On the other hand some use libertarianism to refer to individualistic free-market philosophy only referring to free-market anarchism as libertarian anarchism

List of countries of the world in alphabetical orderから国名リストを拝借しました。ただし、一語からなる国名の場合は、_で繋げてあげる必要もないので複数語からなる国名のみをターゲットとしています。

82. 文脈の抽出

81で作成したコーパス中に出現するすべての単語tに関して,単語tと文脈語cのペアをタブ区切り形式ですべて書き出せ.ただし,文脈語の定義は次の通りとする.

  • ある単語tの前後d単語を文脈語cとして抽出する(ただし,文脈語に単語tそのものは含まない)
  • 単語tを選ぶ度に,文脈幅dは{1,2,3,4,5}の範囲でランダムに決める.

gist5d8c3571da29019ef73a187ab1f77edb

❯ go run q82.go
❯ head -20 ../data/q82.out.txt
Anarchism   Anarchism
Anarchism   is
Anarchism   political
Anarchism   philosophy
Anarchism   Anarchism
Anarchism   is
Anarchism   political
Anarchism   philosophy
is  Anarchism
is  Anarchism
is  political
is  philosophy
is  that
is  advocates
is  stateless
political   is
political   Anarchism
political   Anarchism
political   philosophy
political   that

あるトークンの前後d単語を抜き出すだけなので簡単ですね。

83. 単語/文脈の頻度の計測

82の出力を利用し,以下の出現分布,および定数を求めよ.

  • f(t,c): 単語tと文脈語cの共起回数
  • f(t,∗): 単語tの出現回数
  • f(∗,c): 文脈語cの出現回数
  • N: 単語と文脈語のペアの総出現回数

gist817e4f2f21365f6871e98e1f25dfc2a5

go run q83.go
N:  22760703

結果は表示しきれないため、総出現回数Nのみを表示しています。

84. 単語文脈行列の作成

83の出力を利用し,単語文脈行列 Xを作成せよ.ただし,行列Xの各要素 X_{tc}は次のように定義する.

  •  f(t,c) \geq 10ならば, X_{tc}=PPMI(t,c)=max \bigl\{ log \frac{ {N} \times f(t,c) } { f(t,∗) \times f(∗,c) },0 \bigr\}

  •  f(t,c) \lt 10ならば, X_{tc}=0

ここで, PPMI(t,c)はPositive Pointwise Mutual Information(正の相互情報量)と呼ばれる統計量である.なお,行列 Xの行数・列数は数百万オーダとなり,行列のすべての要素を主記憶上に載せることは無理なので注意すること.幸い,行列 Xのほとんどの要素は0になるので,非0の要素だけを書き出せばよい.

gista18d59730627de797661466de14525ab

// PPMIの大きい上位10個のみを表示
❯ go run q84.go
the number of the word:  390101
the number of contex word:  390101
length of X:  22760703
n(X)/(n(t) * n(c)):  0.0001495655404405392
------------------
{{<br>MONSIEUR LECOQ} 13.30823695164182}
{{Gols Gols} 13.02055487919004}
{{nah nah} 12.979732884669785}
{{LECOQ <br>MONSIEUR} 12.929583100984313}
{{Kimmage Kimmage} 12.915194363532214}
{{Terenure Terenure} 12.822248251022769}
{{Priorswood Priorswood} 12.792134270774987}
{{ου for} 12.728418456388878}
{{molalities as} 12.5192987064402}
{{Snana Made} 12.513398984313012}

何やらhtmlタグが入っていますが、先に進むことにします。。。 このあとの問題が次元削減なので、この時点での要素がどれくらいの規模になるのか表示させました。 また同時にどのくらいスパースなのかも見ておくことにしました。0.01%くらいの充填率のようです。

85. 主成分分析による次元圧縮

84で得られた単語文脈行列に対して,主成分分析を適用し,単語の意味ベクトルを300次元に圧縮せよ.

全量の確認

まず最初に述べておきますが、全量は実装できていません。

インプットとなるQ82の出力は以下のように6930万行となっています。

❯ wc ../data/q82.out.txt
 69306584 138756729 852050914 ../data/q82.out.txt

本問題では、PCAを行う必要があるため、Golangで主成分分析する - 逆さまにしたでも紹介したpackage stat - gonumを利用しています。 ところがこの方法でPCAをしようとするとpanic: runtime error: makeslice: len out of rangeのエラーが発生します。 Sparse matrix formatsを用いて、Sparseに行列を持つところまでは実装していますが、statパッケージでは、データの格納以前に初期化として、runtimemakesliceを行うため上記エラーで失敗します。 どうしてもPCAできず、トレーニングデータのサイズを小さくすることで対処しています。

❯ head -1000000 ../data/q82.out.txt > ../data/q82_tmp.out.txt

gist002868aaa7d7abfa20365039735c192a

実は上記でも3500万行くらいであればメモリの確保はできるのですが、スワップが発生して計算が終わらないので、100万行まで落としています。 それでも1日以上掛かりました。。。

❯ go run q85.go
// 出力はgobで行っておりバイナリフォーマットのため省略

86. 単語ベクトルの表示

85で得た単語の意味ベクトルを読み込み,"United States"のベクトルを表示せよ.ただし,"United States"は内部的には"United_States"と表現されていることに注意せよ.

gistffdac9cafb3d1efad815290df09730a1

❯ go run q86.go
United_States : &{{1 [-0.014999052638340955 -0.06666512410686669 0.002520661466195838 
(中略)
-6.730425781930617e-15 -1.0561597069590151e-14]} 300}

問題文をそのまま実装してあげればOKです。もはやスパースではなくなっていますね。 goのmapは順番を保存しないので(一般的に保存しないため、以前改修されました)、rowの位置はQ85のdicttで保存しておいたものを使います。

87. 単語の類似度

85で得た単語の意味ベクトルを読み込み,"United States"と"U.S."のコサイン類似度を計算せよ.ただし,"U.S."は内部的に"U.S"と表現されていることに注意せよ.

gistc5505e492f63667d5fe9e84e746ba955

❯ go run q87.go
0.4862803570718515

Q86で表示したベクトルのコサイン類似度を計算します。 matパッケージにはDot関数があるので、そちらで内積とノルムを計算します。 最初に実装したときは、ノルムの平方根を取るのを忘れてしまいました。。。

データ数が少ないからか、コサイン類似度は0.486でした。

88. 類似度の高い単語10件

85で得た単語の意味ベクトルを読み込み,"England"とコサイン類似度が高い10語と,その類似度を出力せよ.

gistc699a2323bcbc81fda3f93df14b922a5

※コード中にも記載していますが、Englandが零ベクトルとなったため、United_Statesで代用しています。 トレーニングデータを増やす必要があります。。。

❯ go run q88.go
1   case : 0.9548240697912775
2   2005 : 0.9108531345148447
3   2008 : 0.9019300375926617
4   addition : 0.8825165206539555
5   2012 : 0.8660833551129663
6   2001 : 0.8660833551129661
7   highest : 0.4998879708231505
8   turn : 0.4994728313281741
9   UK : 0.49755475904637503
10   event : 0.49489020770038084

Q87の拡張版みたいな問題です。 sortするためにCosineSimilarity型を定義しています。 United_Statesは西暦に関することが多いですね。caseも類似度が高いので各年で起きた事件などでしょうか。

89. 加法構成性によるアナロジー

85で得た単語の意味ベクトルを読み込み,vec("Spain") - vec("Madrid") + vec("Athens")を計算し,そのベクトルと類似度の高い10語とその類似度を出力せよ.

gista29690d4cf9fe2c6deac6c8cad633092

❯ go run q89.go
1   Spain : 1.0000000000000002
2   terms : 0.9997587662737554
3   languages : 0.9990898124310773
4   cases : 0.9967353219953207
5   small : 0.9960712723292813
6   Germany : 0.9843980937275112
7   areas : 0.9791005134719385
8   church : 0.9774278193367258
9   Rome : 0.9751437717985347
10   2000 : 0.9482871637356568

実装自体は、Q88をほとんど使いまわせます。分散表現することで、単語が意味ベクトルとなったため、加算減算ができるようになりました。 ただし、上記では、Q88と同様にMadridAthensが零ベクトルとなってしまっているため、Spainだけで類似度を計算しているのと同じです。 結果を見ると実装自体は間違っていないので、トレーニングデータが不足していますね。

感想

解答中にも記載していますが、Q85,88,89は十分な結果が得られていません。 分散表現を実装することで単語の加法減法ができるようになったことと、どのように分散表現を作るのかは勉強になりましたが、Sparseな行列に対するPCAをうまく実装するのは改めて戻ってきたいと思います。

いつも通りコードはGithubにも置いてあります。

Reference