チュートリアル1: 1-gram言語モデル - 自然言語処理の分別奮闘記

とりあえず１回目は、前に言っていたNLP Programing TutorialのCapter01(pdf)、1-gram言語モデルの勉強です。
では、スライドに沿って話を進めようと思います。

言語モデルって何？

具体例で説明すると。
音声認識システムにて、認識した結果の出力候補としていくつかの単語列があったとしましょう。

W₁ = speech recognition system

W₂ = speech cognition system

W₃ = speck podcast histamine

W₄ = スピーチが救出ストン

言語モデルは、これらの単語列に「もっともらしさ」を与えてくれるのです。一般的には、各単語列に確率を与えてくれます。

上の各単語列は、ある言語モデルに基づくと

P(W₁) = 4.021*10^-2

P(W₂) = 8.932*10^-4

P(W₃) = 2.432*10^-7

P(W₄) = 9.124*10^-23

のように単語列の生起確率としてとらえることができるようになります。使う言語モデルによってこの生起確率の値は変わってきます。
この1〜4の単語列の場合、人が見たなら1, 2, 3, 4の順でそれらしい(ありそうな)単語列だと思えるはずです。
つまり、

P(W₁) > P(W₂) > P(W₃) > P(W₄)

という確率を出してくれる上の例のような言語モデルは、それっぽい(良い)といえるってことですね。(言語モデルにも善し悪しがあります。)
つまり
言語モデルとは、より自然な、より頻出する文(や単語列)に高い確率を与えてくれるものなのです。

単語列の確率

実際にはどうやって単語列の確率を出してるの？という話

まずは、各単語の同時確率で考えましょう。

P(W=speech recognition system) = P(|W|=3, w₁="speech", w₂="recoginition", w₃="system")

同時確率は条件付き確率で考えられるので

P(|W|=3, w₁="speech", w₂="recoginition", w₃="system") =
　　　P(w₁="speech") | w₀="<s>")
　　　* P(w₂="recognition" | w₀="<s>", w₁="speech")
　　　* P(w₃="system" | w₀="<s>", w₁="speech" , w₂="recognition")
　　　* P(w₄="</s>" | w₀="<s>", w₁="speech" , w₂="recognition", w₃="system")

と表せる。*1
(<s>, </s>はそれぞれ文頭記号,文末記号で、1-gramではあまり意味は無いが2-gram以上のN-gramや遷移モデルなどを考えた時には必要になる) ここで文頭,文末記号が入ってるってことは単語列じゃなくて文だったのかよっていう突っ込みは考えないでおこう
これを一般化すると

${ \displaystyle P(W) = \prod_{i=1}^{|W|+1} P(w_i\ |\ w_0...w_{i-1}) }$

これで単語列の確率は表せそうです。じゃあ、それぞれのP(w_i | w₀...w_i-1)はどうやって求めるのか。
一つの方法として、最尤推定があります。

母集団分布の形が分かっているがその母数が未知であるときに，n個の標本値 x₁,x₂,...,x_nを母集団分布に従う確率変数 X₁,X₂,...,X_nがとることは最も起こりやすい(maximum likelihood)という条件を用いてその母数を決めようとするものである．
(最尤推定)

起きた現象を、「最も引き起こす確率が高い」場合を考えるのが最尤法です。
(最尤法を言葉で簡潔に説明するには、どのように説明すればいいですか？)

要するに(たぶん)、
起きた事象から、きっとこういう確率だったんだろうなと推測する
ってことだと思います。
で、今回の場合はコーパス *2の単語列を数え上げればいいわけです。(たぶんコーパスが事象で、この世の全ての文章などなどが母集団ってことになるんだと思う。たぶん。いやこの世の文章もサンプルにすぎないのかな、、そしたら母集団は文章を生み出してる言語自体なのかな、よくわからんけどニュアンスは伝わったと思う。。)

で、式はどうなるかというと(c(W) : 単語列Wの総数)

${ \displaystyle P(w_i|w_0\ldots w_{i-1}) = \frac{c(w_0...w_i)}{c(w_0...w_{i-1})} }$

具体的には、

<s> i live in osaka . </s>
<s> i am a graduate student . </s>
<s> my school is in nara . </s>

というコーパスがあった時に<s> i live, <s> i amそれぞれの確率は

P( live | <s> i ) = c(<s> i live) / c(<s> i) = 1/2 = 0.5
P( am | <s> i ) = c(<s> i am) / c(<s> i) = 1/2 = 0.5

となるわけである。

これで、P(w_i | w₀...w_i-1)が求められたわけですが、最尤推定には問題があります。
頻度の低い現象に弱いのです。どういうことかというと、 <s> i live in nara . </s>の文の確率を計算したいときに、

P(nara | <s> i live in) = 0/1 = 0
∴ P(W = <s> i live in nara . </s>) = 0

となってしまうのです。
<s> i live in nara . </s>という文は、ありえない文ではないのですが、このように最尤推定による言語モデルでは確率が0になってしまいます。
これはコーパスに<s> i live in naraという単語列が存在しないのが原因です。
zero frequency problemとかsparseness problemとかゼロ頻度問題とか言われてる問題ですね。読んで字のごとくコーパスに存在しない単語や単語列の頻度・確率が(実際には起こりうるのに)0になってしまうという問題です。

1-gramモデル

今日の本題「1-gramモデル」です。先ほどの低頻度の問題を少し解消してくれます。 1-gram(unigram)モデルは、N-gramモデルのN=1のときのモデルです。(次回N-gramモデルをやります)
1-gramとは1単語ずつの頻度で考えるモデルのことです。*3
このように前後の単語の並びに関係なく(つまり順番を考慮せずに)考えることをbag of wordsと言ったりします。最尤推定では履歴を考えていましたが、1-gramではその履歴を用いないことで低頻度の単語列を減らしています。
つまり、分子をその単語の頻度、分母を全語彙の頻度の和(コーパスの単語数)

${ \displaystyle P(w_i | w_1...w_{i-1}) \approx \frac {c(w_i)}{\sum_{\tilde{w}\in W}^{} c(\tilde{w})} }$

というように計算することで1単語の頻度として考えています。あとはこれを掛けあわせて単語列の確率を算出します。
例えば、P(<s>) = 3/22 ≈ 0.14, P(i) = 2/22 ≈ 0.09, P(live) = 1/22 ≈ 0.05, ...
のように各単語の確率を計算すると

P(W = <s> i live in nara . </s>) = 0.14 * 0.09 * 0.05 * 0.09 * 0.05 * 0.14 * 0.14 = 5.556 * 10^-8

のように、最尤推定では確率が0になってしまった文の確率が算出できました。

が、まだダメです。まだゼロ頻度問題があります。
これまでは頻度の少ない単語列(や文)に対して、履歴を用いない(単語列として考えずに単語のみで考える)ことによってゼロ頻度問題を解決しようとしました。これである程度はゼロ頻度問題を解消できたのですが、単語そのものがゼロ頻度の場合、つまり未知語が存在する場合は確率が0になってしまうのです。
例えばP(kyoto)はP(kyoto) = 0/22 = 0となってしまいますよね。
なので、P(<s> i live in kyoto . </s>) = 0になってしまいます。

未知語の対応

未知語が含まれると1-gramでさえもゼロ頻度問題が起きることがわかりました。これを解決するために、未知語の確率を補間します。

${ \displaystyle P(w_i) = \lambda_1P_{ML}(w_i)+(1-\lambda_1)\frac{1}{N} }$

Nは未知語を含む語彙数として設定します。
P_ML(w_i)はさっきまでの1-gramモデルの考え方で算出する単語w_iの確率です。
λ₁は補間係数と呼びます、添字の1は1-gramの補間という意味です。

例えば、N=10⁶, λ_unk=0.05 (λ₁=0.95)とすると

P(<s>) = 0.95*0.14 + 0.05*(1/10⁶) = 0.13300005
P(i) = 0.95*0.09 + 0.05*(1/10⁶) = 0.08550005
P(live) = 0.95*0.05 + 0.05*(1/10⁶) = 0.04750005
P(in) = 0.95*0.09 + 0.05*(1/10⁶) = 0.08550005
P(kyoto) = 0.95*0 + 0.05*(1/10⁶) = 0.00000005
P(.) = 0.95*0.14 + 0.05*(1/10⁶) = 0.13300005
P(</s>) = 0.95*0.14 + 0.05*(1/10⁶) = 0.13300005

P(<s> i live in kyoto . </s>) = 0.13300005 * 0.08550005 * 0.04750005 * 0.08550005 * 0.00000005 * 0.13300005 * 0.13300005
　　= 4.08 * 10^-14

と、未知語 "kyoto" があっても確率が出せました。

これは、常に(1-λ)の割合で未知語の確率を入れているので、Interpolation(線形補間)といいます。
これでゼロ頻度問題を解決できました。
他にも、add-one, good-turing, Kneser-Neyなどのdiscounting*4と呼ばれる方法や、back-offなど様々なスムージングの方法があります。気になる人は、こちらのページにある程度書いてあったので参考までに。(「Ngram言語モデルメモ」)

言語モデルの評価

最尤推定, 1-gramモデル, 未知語の対応とやってきてようやく言語モデルを作ることができました。
次はその言語モデルがどれだけ使えるものなのか、評価方法についてです。
最初のほうで「言語モデルにも良し悪しがあります」と言ったと思いますが、それを定量的に測ることができます。
モデルの評価尺度にはいくつかの方法があり、ここでは、尤度, 対数尤度, エントロピー, パープレキシティ、カバレージの5つを勉強します。
一般的には、パープレキシティとカバレージが使われるようです。というか、尤度、対数尤度、エントロピーはパープレキシティまでの道のりみたいなものですね。

さて、言語モデルの構築には、学習データを用いて単語をカウントしました。
言語モデルの評価には、学習データとは別の評価データを用います。
練習問題と期末テストが全く同じだったら、期末テストで高得点が取れるのはあたりまえですよね。それと同じで、学習データと評価データは別に用意する必要があるのです。
ただ、学習データと評価データに同じものを使って、その評価結果が低い場合は学習自体がうまくいっていない(学習にバグがある)という推測をすることができます。

f:id:uorijuram:20140818181509p:plain

尤度

尤度は、モデルMが与えられた時の観測されたデータ(評価データW_test)の確率です。

${ \displaystyle P(w_{test}|M) = \prod_{w \in W_{test}}P(w|M) }$

つまり、さっきまで計算していた文の確率そのものですね。テストデータの文章の確率を計算するだけです。

P(w="i live in nara" | M) = 2.52*10^-21
P(w="i am a student" | M) = 3.48*10^-19
P(w="my classes arre hard" | M) = 2.15*10^-34
P(W_test | M) = 2.52*10^-21 * 3.48*10^-19 * 2.15*10^-34 = 1.89*10^-73

確率と尤度は式こそ同じですが、意味は違います。この場合尤度は、評価データの元でのモデルMの尤もらしさを意味しています。 (「尤度とは何者なのか？」)

対数尤度

尤度は確率値を掛けあわせているので、しばしばアンダーフローを起こしてしまいます。尤度に対数をとることでこの問題を解決したのが対数尤度です。対数をとっても大小関係は変わりません。

${ \displaystyle log(P(w_{test}|M)) = \sum_{w \in W_{test}}log(P(w|M)) }$

P(w="i live in nara" | M) = -20.58
P(w="i am a student" | M) = -18.45
P(w="my classes arre hard" | M) = -33.67
P(W_test | M) = -20.58 -18.45 -33.67 = 72.60

エントロピー

エントロピーHは底2の負の対数尤度を単語数で割った値です。

${ \displaystyle H(W_{test}|M) = \frac{1}{|W_{test}|}\sum_{w \in W_{test}}-log(P(w|M)) }$

情報理論において情報量として利用されています。

エントロピーは３つの意味を持つ：
情報の量 (Amount of Information)
不確実性 (Uncertainty)
圧縮の出来なさ (Incompressibility)
即ち、エントロピーが高い場合、情報量が増え不確実性が増し、圧縮ができにくくなる。例として、表しか出ないコインが持つ不確実性は0である（確実に表になる）。したがって、このコインに最低限の情報しか持たない。
(エントロピーとは)

この場合、エントロピーは言語モデルの複雑さを表しています。エントロピーが高いほど複雑で、次へ続く単語の予測が難しいことを表しています。(エントロピーが高い、すなわち確率の低い単語は本当にこの単語が生起するのかが曖昧)つまり、不確実性のことだと思います。

パープレキシティ

パープレキシティは2のエントロピー乗で表します。

${ \displaystyle PPL = 2^{H} }$

パープレキシティもエントロピーと同じくモデルの複雑さを表していますが、パープレキシティは情報理論においての平均分岐数です。つまり2^H個の等出現確率の単語の中から一つの単語を決定することになります。パープレキシティの値が大きいほどモデルが複雑で平均分岐数(次に続く可能性のある単語の数)が多いです。
一般的にはパープレキシティが低い(より複雑でない)ほど良いモデルであると言えますが、単純過ぎても良くない(らしい)ので、どの程度の複雑さが良いのかは場合によるようです。

カバレージ

カバレージは、評価データに現れたn-gram(今回は1-gramなので単語)の中で、モデルにも含まれている割合のことです。言語モデルがテストデータ内のどれだけの語彙をカバーできているか、文字通りですね。

${ \displaystyle \frac{単語数-未知語の数}{単語数} }$

実装

やっと説明部分が終わりました。長かったです。
では、言語モデルの学習と評価を実装してみましょう。私の研究室ではpythonを使っているのでpythonで実装します。やっていることは単純で単語を数え上げているだけです。学習,評価用のデータ等はNLP Programing Tutorialのページで配布されています。
埋め込みができるのでgistを使っていますが、コードはすべてgithubのRepositoryにあります。gistではなくgithubにあるコードを埋め込む方法ってないのですかね。調べるとgistの埋め込みばかり出てきます。。

まずは言語モデルを学習するためのtrain_lm.py

次に言語モデルを評価するためのtest_unigram.py
Tutorialのスライドにはないですが、せっかくなのでパープレキシティも出力しています。

テスト用のデータで実行してみた結果はこんな感じ。

python train_unigram.py -f 01-train-input.txt -o lm
学習データ(01-train-input.txt)

a b c
a b d

言語モデル(lm)

</s> 0.250000
a 0.250000
b 0.250000
c 0.125000
d 0.125000

python test_unigram.py -f 01-test-input -l lm -o evaluation
評価データ(01-test-input.txt)

a c
e

評価結果(evaluation)

entropy : 6.709899
perplexity : 104.684170
coverage : 0.800000

データが大きいので中身は書きませんが、演習用データ(wiki-en-train.word, wiki-en-test.word)で学習,評価した結果は以下のようになりました。

entropy : 10.526656
perplexity : 1475.160635
coverage : 0.895226

なんかパープレキシティが大きいですけど、どうなんですかね、数字を見てもいまいちよくわかっていないです。平均分岐数だと思うとかなり大きすぎるような気がしますが。。1-gramだからとかそういうことなんですかね。
まぁその辺はいろいろなタスクをやっていく中でわかるようになるでしょう。

最後に少し気になったので調べてみたことを書いてみます。

モデルとは

今回は1-gram言語モデルと言語モデルの評価について勉強しました。
しかし言語モデルに限らず、「モデル」とは一体なんなのか。
自然言語処理においてもよく使われている単語ですが、なかなかその意味を掴みにくいです。
私も曖昧な解釈のままなのですが、現時点では

複雑な現象を説明するために用いられる単純化した理論や仮設
(モデルとはなにか？)

という説明が一番しっくりきています。
今回勉強した1-gram言語モデルも、文の生起という複雑な現象を説明するために、「ある単語の生起確率は他の単語に依存しない」という仮説のもとに単純化して考えられています。

この仮説が正しいかどうかはさておき、仮説を立てて捨象することで理論を単純化し現象を捉えやすくしています。

仮設を行い、大勢に影響しない要素を捨象することこそ「モデル」の本質
(いまさら聞けないモデルの話)

抽象的な概念を捉えるのはなかなか難しいですが、これから勉強していく中でも理解を深められたらと思います。

とりあえず、今回のChapter01「1-gram言語モデル」はここまでです。なにか間違っていることや補足などあれば教えていただけると助かります。

*1: 文の始めには必ずあるので、P(w₀="<s>") = 1

*2:自然言語の文章を構造化し大規模に集積したもの。wikipedia

*3:これは単語1-gram, 1文字ずつで考えるものを文字1-gramという

*4:既知語からある割合だけ未知語に割り当てるためdiscountingと呼ばれる