【自然言語処理】1-gram言語モデル

■ やること

NAISTの授業資料を自分なりに勉強してみる。
http://www.phontron.com/teaching.php

今回の内容は チュートリアル1: 1-gram言語モデル

■ 言語モデルとは

いくつかの候補から「もっともらしい」文を選んでくれるもの。
言語モデル(確率的言語モデル )は候補の各文に確率をあたえ、どの候補が確からしいのか判断できるようにしてくれる。

■ 文の確率計算

例えば W = speech recognition system の確率は以下の式で表せる。

# 単語数が3, 1単語目がspeech, 2単語目がrecognition, 3単語目がsystem の同時確率 という意味
P(|W| = 3, w_1="speech", w_2="recognition", w_3="system")

ただし、この同時確率はそのまま計算できないので、条件付き確率の積に変換する必要がある。

同時確率 -> 条件付き確率の積

条件付き確率の公式

\begin{align}
P(X|Y) &= \frac{P(X,Y)}{P(X)} \\
P(X,Y) &= P(X|Y)P(X)\\
P(X,Y) &= P(Y|X)P(Y)\\
\end{align}

連鎖の法則

条件付き確率の公式を利用して、同時確率を条件付き確率の積に変換できる
参考: http://makotomurakami.com/blog/2018/09/11/223/

\begin{align}
P(w_1, w_2, w_3) 
&= P(w_2, w_3 | w_1) * P(w_1) \\
&= P(w_3|w_2,w_1) * P(w_2|w_1) * P(w_1) \\
\end{align}

※ メモ
$P(w_2, w_3)$ は $P(w_3 | w_2) * P(w_2)$ であり、それぞれ $w_1$ を条件に持つため、 $P(w_3|w_2,w_1) * P(w_2|w_1)$ となる

実際に変換してみる

先程の W = speech recognition system の確率を変換してみる。
※ <s> を文頭、</s> を文末とする。
※ P(w_0="<s>") = 1

P(|W| = 3, w_1="speech", w_2="recognition", w_3="system")
= P(w_0="<s>", w_1="speech", w_2="recognition", w_3="system", w_4="</s>")
= P(w_0="<s>")
* P(w_1="speech"      | w_0="<s>")
* P(w_2="recognition" | w_0="<s>", w_1="speech")
* P(w_3="system"      | w_0="<s>", w_1="speech", w_2="recognition")
* P(w_4="</s>"        | w_0="<s>", w_1="speech", w_2="recognition", w_3="system")

一般化

条件付き確率の積に変換した式を一般化するとこんなかんじ。

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

※ $P(w_i|w_0...w_{i-1})$ はどうやって求めるのか

■ 最尤推定による確率計算

$P(w_i|w_0...w_{i-1})$ を求めるには、コーパスの単語を数えて割り算する。

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

例

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

というコーパスがあったとして、<s> i の次に live が来る確率は 「<s> i live」の個数 / 「<s> i」の個数 となる。

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

問題点

出現頻度の低い現象に弱い。
コーパスに存在しない文章の確率がすべて0になってしまう。特に長い文章ほど起こりやすい。
例えば、例に上げたコーパスにおいて <s>i libve in nara.</s> の確率は0である。

■ 1-gram言語モデル

最尤推定の問題点は、コーパスに出現しない文章の確率がすべて0になってしまうことであった。
そこで1-gram言語モデルでは、着目単語の出現確率のみに着目することで確率が0になってしまう問題の解消を図る(前方の単語を考慮しないことで、低頻度の現象を減らすということ)
つまり$P(w_i|w_0...w_{i-1})$ を 単純な単語の発生頻度(対象の単語数 / 学習データ全体の単語数) とみなす。

P(w_i|w_0...w_{i-1}) \approx P(w_i) =  \frac{c(w_1..w_i)}{c(w_1...w_{i-1})}

例

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

このコーパスにおける W = i live in nara.</s> の確率は

P(nara) = 1 / 20 = 0.05
P(i) = 2 / 20 = 0.1
P(</s>) = 3 / 20 = 0.15

P(W=i live in nara.</s>)
= P(i) * P(live) * P(in) * P(nara) * P(.) * P(</s>)
= 0.1 * 0.05 * 0.1 * 0.05 * 0.15 * 0.15 
= 5.625 * 10^-7

◎ 未知語の対応

1-gram言語モデルでも、対象の文に未知語が含まれる場合、文章全体の確率が0になってしまう。

P(nara) = 1 / 20 = 0.05
P(i) = 2 / 20 = 0.1
P(kyoto) = 0 / 20 = 0

P(W="i live in kyoto.</s>")
= P(i) * P(live) * P(in) * P(kyoto) * P(.) * P(</s>)
= 0.1 * 0.05 * 0.1 * 0 * 0.15 * 0.15 
= 0

未知語を含む語彙数を N とし、少しの確率($\lambda_{unk} = 1 - \lambda_1$)を未知語に割り当てることで解決する。
※ 一般的に $\lambda_1 = 0.95$
Nは例えば英語全体の単語数。つまり未知語は英語全体の中からランダムに選択するという意味になる
そうすると下記のような式になる。

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

例

• 未知語を含む語彙数: $N = 10^6$
• 未知語に割り当てるウェイト: $\lambda_{unk} = 0.05 (\lambda_1 = 0.95)$

P(nara) = 0.95 * 0.05 + 0.05 * (1 / 10^6) = 0.04750005
P(i) = 0.95 * 0.10 + 0.05 * (1 / 10^6) = 0.09500005
P(kyoto) = 0.95 * 0 + 0.05 * (1 / 10^6) = 0.00000005

P(W="i live in kyoto.</s>")
= P(i) * P(live) * P(in) * P(kyoto) * P(.) * P(</s>)
= 0.09500005 * ...

■ 言語モデルの評価

学習と評価のためのデータをそれぞれ別で用意。
学習データで作ったモデルを評価データに適用して 尤度、対数尤度、エントロピー、パープレキシティといったモデル評価の尺度を計算する。

尤度

モデルを利用して計算した文章確率の積

$P(W_{test}|M) = \prod_{Wi \in W_{test}}P(W_i|M)$

$p(W_i|M) = \prod_{w \in W_i}{0.95 * モデルの確率 + 0.05 * \frac{1}{10^6}}$

例

テストデータ

i live in nara
i am a student
my classes ar hard

テストデータそれぞれの確率を計算する

# Mはモデル

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

計算した確率を元に尤度を求める

\begin{align}
P(W_{test}|M) &= (2.52 * 10^-21) * (3.48 * 10^-19) * (2.15 * 10^-34)\\
&= 1.89 * 10^-73\\
\end{align}

対数尤度

桁あふれが起こらないように対数をとった尤度

logP(P(W_{test}|M)) = \sum_{w \in W_{test}}logP(w|M)

※ メモ: 対数計算
$log_aMN = log_aM + log_aN$
$log_a\frac{M}{N} = log_aM - log_aN$

テストケースごとの確率を計算して対数を取る。

log P(w="i live in nara"      | M) = log P(i|M) + log P(live|M) + log P(in|M) + log P(nara|M)
                                   = -20.58
log P(w="i am a student"      | M) = -18.45
log P(w="my classes are hard" | M) = -33.67

対数尤度を求める

\begin{align}
log P(W_{test}|M) &= (-20.58) + (-18.45) + (-33.67) \\
&= -72.60
\end{align}

エントロピー

エントロピー(H)は負の、底2の対数尤度を単語数で割った値。
単語数で割るので値の大きさが単語数に依存しない

H(W_{test}|M) = \frac{1}{|W_{test}|} \sum_{w \in W_{test}} - log_2P(w|M)

テストケースごとの確率を計算して底2の対数を取る。

log_2 P(w="i live in nara" | M) = 68.43
log_2 P(w="i am a student" | M) = 61.32
log_2 P(w="my classes are hard" | M) = 111.84

エントロピーを求める

\begin{align}
H(W_{test}|M) &= (68.43 + 61.32 + 111.84) / 12 \\
&= 20.13
\end{align}

パープレキシティ

2のエントロピー乗

PPL = 2^H

カバレージ

評価データに現れた単語の中でモデルに含まれている割合

■ 演習問題

import math

class UnigramModel:
    def __init__(self):
        self.probs = {};

    def struct(self, input_file, model_file):
        """モデルを構築してファイルに書き込む
        """
        word_count = {}
        total_count = 0
        for line in UnigramModel._read_lines(input_file):
            words = line.split(" ")
            words.append("</s>")
            for word in words:
                if word in word_count:
                    word_count[word] += 1
                else:
                    word_count[word] = 1
                total_count += 1
        with open(model_file, "w") as writer:
            for word in word_count:
                count = word_count[word]
                prob = count / total_count
                writer.write("{} {}\n".format(word, prob))

    def load(self, model_file):
        """ファイルからモデルを読み込む
        """
        for line in UnigramModel._read_lines(model_file):
            (word, prob) = line.split(" ")
            self.probs[word] = float(prob);

    def evaluate(self, test_file):
        """モデルの評価を行う
        """
        lambda_1 = 0.95 # 単語の出現確率に割り当てるウェイト
        lambda_unk = 1 - lambda_1 # 未知語に割り当てるウェイト
        V = 1000000 # 英単語の語彙数
        W = 0 # 単語数
        H = 0 # 負の底2の対数尤度
        unk = 0 # 未知語数
        for line in UnigramModel._read_lines(test_file):
            words = line.split(" ")
            words.append("</s>")
            for word in words:
                W += 1
                prob = lambda_unk / V # 未知語の確率
                if word in self.probs:
                    prob += lambda_1 * self.probs[word] # 単語の出現確率
                else:
                    unk += 1
                H -= math.log2(prob)
        return {
            "entropy": H / W,
            "coverage": (W - unk) / W
        }

    def _read_lines(file):
        with open(file) as fh:
            while True:
                line = fh.readline().rstrip("\n\r")
                if not line:
                    break
                yield line

演習1

• 01-train-input.txt で1-gramモデルを学習
• 01-test-input.txt 作成したモデルでエントロピーとカバレッジを計算

input_file = "01-train-input.txt"
test_file = "01-test-input.txt"
model_file = "model_sample.txt"

model = UnigramModel()
model.struct(input_file, model_file)
model.load(model_file)
model.evaluate(test_file) # {'entropy': 6.709899494272102, 'coverage': 0.8}

演習2

• wiki-en-train.word で1-gramモデルを学習
• wiki-en-test.word 作成したモデルでエントロピーとカバレッジを計算

input_file = "wiki-en-train.word"
test_file = "wiki-en-test.word"
model_file = "model_wiki.txt"

model = UnigramModel()
model.struct(input_file, model_file)
model.load(model_file)
model.evaluate(test_file) # {'entropy': 10.527337238682652, 'coverage': 0.895226024503591}