とある童話の統計科学(3)言語モデルとn-gram

Toaru_Logo

そういえば、この辺の話は基本的に、C. Manning, “Foundation of Statistical Natural Language Processing”に詳しい。ぜひご参考に。

言語モデル

言語研究は統計に限らないので、定義はまちまちだろうけども、ここでの言語モデルとは、語の有限列である文書$W = \{w_1, w_2, \cdots, w_N \}$に対して、確率$p(W)$を与える関数を指す。ただし、語はボキャブラリ数をVとして、自然数にコーディングされているものとする、すなわち、$w_i \in \{1, \cdots, V \}$である。

例えば、次のような2つの英文があったとしよう。

  • an apple is red
  • in are take me

1つ目は、単に「りんごは赤い」と言っているだけである。一方で、2つ目の文章は何を言いたいのかさっぱりわからない。「英語」という言語モデルにとって、p(an apple is red)はある程度の確率を持つが、p(in are take me)の確率は極めて小さいとも言える。

統計的言語処理の1つの目的は、膨大に蓄積された言語リソースから、この言語モデルを統計的に推定することと言える。今回のテーマであるn-gramとは、その言語モデルの1つである。

n-gram

n-gramが推定するモデルは、 p(w_i | w_{i-1}, \cdots, w_{i-n+1}) である。すなわち、直近のn-1語によって、次に出現する語の確率を与える。例えば、次の2つの文章を考えてみる。

  • this is ***
  • he eats ***

***に何が入るか、予測できるだろうか?1文目は、これは〜です、と言っているため、候補は非常に多い。一方、2文目は彼は〜を食べます、なので〜に入るものは食べ物と予測できる、かつ「彼」という言葉からは男性に一般的に好かれるような食べ物が入る可能性が高い。この我々の中に内在する「直前の語からなんとなく予測できる」が、n-gramで抽出したい言語の特性である。

この問題は形式的には、「直前2語を所与とした場合の、次に出現する語の条件つき確率を求めよ」、ということである。

  • p(*** | this is)
  • p(*** | he eats)

この例は、直近の2語から次に出る1語を予測する問題なので、3-gram(trigram)と呼ぶ。

n-gramに対して、文書Wの確率は、次のように与えられる。

(1)    \begin{align*} p(W) = \prod_i p(w_i | w_{i-1}, \cdots, w_{i-n+1}) \end{align*}

また、特殊な形として、1-gram(unigram)がある。これは、直前の語による影響を受けないモデルである。この場合の文書の確率は以下である。

(2)    \begin{align*} p(W) = \prod_i p(w_i) \end{align*}

そのうち紹介するLDAなどのトピックモデルは、この1-gramの発展系である。

n-gramの推定

簡単のために、2-gramを例とする。ベイズの定理より、次が成り立つ。

(3)    \begin{align*} p(w_n | w_{n-1}) = \frac{p(w_n, w_{n-1})}{\sum_{w_n} p(w_n, w_{n-1})} \end{align*}

ここで、$p(w_n, w_{n-1})$として、パラメータ$\{ \theta_{i,j} \}$、観測数1回の多項分布を考える。すなわち、

(4)    \begin{align*} p(w_n=i, w_{n-1}=j) = \theta_{i,j}, \sum_{i,j} \theta_{i,j} = 1, \theta{i,j} > 0  \end{align*}

文書Wに対して、パラメータ$\{ \theta_{i,j} \}$の最尤推定量は、

(5)    \begin{align*} \theta_{i,j} = n_{i,j} / N \end{align*}

$n_{i,j}$は、語列{i,j}の出現回数、Nはドキュメント内の総語数である。ここで、Eq.(3)の2-gramモデルによる条件つき確率は、次のように計算できる。

(6)    \begin{align*} p(w_n=i | w_{n-1}=j) = \frac{\theta_{i,j}}{\sum_{\tilde{i}} \theta_{\tilde{i},j}} = \frac{n_{i,j}}{\sum_{\tilde{i}} n_{\tilde{i},j}} \end{align*}

適用例

以下が、2-gramのパラメータ推定をしたのちに、各文書についてp(*|she), p(*|red), p(*|look)の確率が高い上位5語をそれぞれ抽出した結果である。

ngram_ex

主語となるsheの後には動詞が続いていること、形容詞redの次には赤いもの、動詞lookの次にはatなどの前置詞が続き、我々の英語知識に沿った結果が得られているのではないだろうか。

今回の2-gramのパラメータ総数はV*V=121,396,324個である。しかし、グリム童話の場合、そのうちの実に99.97%のパラメータが値は0のまま、つまりその組み合わせが本文中に観測できなかった。このスパースさが、n-gramの難しい所である。概念的には同じようなものを指していても、最尤推定されたパラメータによる文書の確率推定は度々0になり(Eq.(1)のうち1つでも0になれば、総積によって全体が0となる)、モデルとして役に立たない。文書の量を増やしていくというのは1つの手段ではあるが、3-gram, 4-gramを考えていったとき、パラメータの数は指数的に増大していくため、本質的な解決にはならない。

次回は、その緩和としてスムージングと呼ばれる手法の紹介をする。

とある童話の統計科学(2)

Toaru_Logo

今回は、語の基本的な統計情報についての紹介。


語の統計

まずは各文書の語数とボキャブラリ数(ユニークな語の数)。

Toaru2_1

4文書合わせての総ボキャブラリ数は、11017語であった。

不思議の国のアリスは、完全に子供向けなのか(個人的にはあまりそうは思えないけれど。。。)、ボキャブラリ・語数共に控えめである。クリスマスキャロルは、語数は同程度だが、利用しているボキャブラリは1000語以上多い。low teen手前くらいだろうか。

次に、文書ごとの語の出現確率を示す。横軸は、各文書ごとに出現確率の高い順から語をソートし、その結果のランクを示している。縦軸は、各ランクの出現頻度のlog10である。文書ごとに、各ランクに対応する語は異なることに注意。

Toaru2_2

実はこのプロットから、「出現確率がランクの逆数に比例する」というZip則が概ね成立していることがわかる。適当にチューニングしてみると、出現確率=0.09/ランク、程度になる。どの文書でもあまり変わらない。

Zip則はロングテールの存在を表しており、ランクに対する累積確率を下図のように計算していくと、後ろのランクまで1.0に収束することがない。文書における語の生成は、基本的に疎と言える。

Toaru2_3

ちなみに、累積確率の最初の立ち上がりが非常に早いが、これらは主に情報の少ない機能語(冠詞, 前置詞, etc)が占めている。不思議の国のアリスの場合、語の頻出トップ10は以下である。

  • $(終端記号) 20.2%
  • the 4.8%
  • and 2.5%
  • to 2.1%
  • a 1.8%
  • it 1.7%
  • she 1.6%
  • i 1.6%
  • of 1.5%
  • said 1.3%

文書を特徴づける情報はロングテールに含まれており、連続データと同じ感覚で少数派をネグると痛い目をみる。


次回は、統計モデルn-gramのお話。

とある童話の統計科学(1)

Toaru_Logo

TeXでとある魔術のロゴ作成 というページを見つけたのがきっかけで、今回のネタをやってみようと思った(texソースお借りしました。ありがとうございます。素晴らしい出来ですね)。

何がしたいかというと、童話を対象に統計的自然言語処理をしてみようというお話。n-gram, LDA, HMMとフォローしていく予定だけど、長くなりそうなので、少しずつ。どこまでいけるかな。

今回はイントロダクションとして、何を対象にしたのかと文字の統計についての紹介。


準備

対象とする童話は、

  • Alice’s Adventures in Wonderland
  • A Christmas Carol
  • The Adventures of Tom Sawyer
  • Grimms’ Fairy Tales

いずれも、Project Gutenbergから入手した英語版。英語の方が、単語の切れ目がはっきりしていて扱いやすい。選択に特に意味はない。

前処理

今回はあまり関係ないけれど、主な前処理は以下。

  • Project Gutenbergのヘッダ・フッタの除去
  • 小文字化
  • [a-z0-9,.!?’]以外の文字を空白で置換
  • 数字列の置換 (e.g. 123 -> #)
  • ‘,.!?’を終端文字’$’として置換

文字(アルファベット)の統計

まず、各文書の総文字数を表したグラフを示す。

Toaru1_1

不思議の国のアリスが最も少なく、グリム童話が最も多い。その差は、300k文字程度である。

次に、各文字の出現確率(各文字の出現回数を総文字数で割ったもの)を表したグラフを示す。

Toaru1_2

自然言語処理を勉強したときに、一番最初に衝撃を受けたのは、文書が異なっても文字の頻度分布にそれほど大きな差がないということだった。文書のサイズが大きく違っているにもかからず、上図の結果はそれを良く表している。


今回は、ここまで。統計的自然言語処理は、このような言語に潜むパターンをモデル化して、利用する研究分野である。

一通り勉強はしたけれど、忘れかけているので、少しずつ更新していってリマインダにする予定。