ngram言語モデルについてまとめる (ヘルドアウト推定・Good-Turing)

前回に続いて、古典的な言語モデルについてpythonで実装して比較していきます。

eieito.hatenablog.com

add-one や ELE は下の式をベースに、対象の単語の ngram と (n-1)gramの頻度を使って確率を求めていた。

$\displaystyle{ P(w_{i} |w_{i-1})= \frac{C(w_{i-1},w_{i})}{C(w_{i-1}) } }$

今回は頻度 r に注目した手法です。

未出現の単語に対して頻度を振り分けるため、学習データ内での出現回数 r を調整する方法がある。ここで、同じ出現回数であれば出現確率も同じとみなします。例えば、dog も pencil も互いに5回出現していたら、どちらも同じ確率を割り当てる。

前回と同様、詳細なコードは下記gistに記載しています。

torchtext_pentreebank_gt.ipynb

ヘルドアウト推定

ヘルドアウト推定は学習データとは別のヘルドアウトデータを使って確率推定値を求める。ヘルドアウトデータにより、学習データに未出現のデータに対しても確率を割り当てることができる。

学習データにおける頻度 $C_1(w1, ..., wn)$
ヘルドアウトデータにおける頻度 $C_2(w1, ..., wn)$
学習データにおける頻度 r の n-gramのタイプ数 $N_r$
学習データ中のn-gramの頻度がr回のn-gramがヘルドアウトデータで出現した数 $T_r$

とする。

今回は PenTreebankのデータを使ってみる。

ヘルドアウトデータは学習データとは別のデータであれば良いので、train を半分に分割して訓練データとヘルドアウトデータとする。

tmp = [data.strip() for data in torchtext.datasets.PennTreebank(split='train')]

train_data = tmp[:len(tmp)//2]
heldout_data = tmp[len(tmp)//2:]
len(train_data), len(heldout_data)
>> (21034, 21034)

PennTreebank はスペースで区切ってあり、ピリオドの削除など前処理済みデータのようなので tokenizerはシンプルな split を利用した。

train_data でvocabクラスを作ってヘルドアウトデータの頻度もカウントする。

tokenizer = get_tokenizer(None)

def get_vocab(data_iter):
  vocab = build_vocab_from_iterator(map(tokenizer, data_iter), specials=['<unk>'])
  # 未知語は全部 `<unk>` 扱いにする
  vocab.set_default_index(vocab['<unk>'])
  return vocab


# ngramの頻度辞書を作る関数 get_ngram_count は省略。gist参照。
# 訓練データにおける頻度 c1
c1_vocab = get_vocab(train_data)
c1_bigram = get_ngram_count(train_data, c1_vocab, 2)
print(len(c1_bigram))
>> 157629

# ヘルドアウトデータにおける頻度 c2
c2_bigram = get_ngram_count(heldout_data, c1_vocab, 2)
print(len(c2_bigram))
>> 150070

頻度を計算したところで、実際にbigramでNr と Tr を計算する。

# 頻度 r の n-gramのタイプ数 Nr
nr_types = defaultdict(int)
for freq in c1_bigram.values():
  nr_types[freq] += 1

# r=0 は存在しないので vocab_sizeと定義する
nr_types[0] = len(c1_vocab) * len(c1_vocab)

ヘルドアウトデータについて、学習データでの出現回数を取得する。よって Tr[0] には「ヘルドアウトデータで1回以上出現しているが学習データで出現していないデータの総出現回数」が入る。

# 訓練テキスト中のn-gramの頻度がr回のn-gramがヘルドアウトデータで出現した数 Tr

tr_num = defaultdict(int)
t_sum = 0

for ngram, r in c2_bigram.items():
  c1_r = c1_bigram.get(ngram, 0)
  tr_num[c1_r] += r
  t_sum += r

print(t_sum)

Tr と Nr から学習データで r 回出現するngramについて、ヘルドアウトデータで合計 Tr 回出現することがわかる。よって、学習データでr回出現する任意のngramは Tr/Nr 回出現するとみなせる。

つまりsmoothingした頻度を $r^* = T_r / N_r$ として推定できる。

下の表のように、r* は実際のrより小さくなる。

r	Nr	Tr	Tr / Nr (r*)	log2(Tr/ Nr T)
0	93334921	114926	0.001231	28.343
1	111266	38323	0.344427	20.215
2	20831	23052	1.106620	18.531
3	8446	16426	1.944826	17.718
4	4404	12254	2.782470	17.201
5	2769	10315	3.725172	16.780
6	2010	9390	4.671642	16.453
7	1304	7274	5.578221	16.197
8	911	5967	6.549945	15.966
9	710	5315	7.485915	15.773

確率推定値を求める。

$\displaystyle{ P_{ho}(w_1,...,w_n) = \frac{T_r}{N_r T} }$

ただし、

$w_1,...,w_n$ の学習データでの頻度が r
T は T_r の総和

つまり、smoothingした頻度をヘルドアウトデータの数で割った値。

この方法で確率を算出してみる。

sample_text = "this wikipedia is written in english"
tokens = text2index(sample_text, c1_vocab)

for t in iter_ngram(tokens, 2):
  r = c1_bigram.get(tuple(t),0)
  nr = nr_types[r]
  tr = tr_num.get(r, 0)
  print(t, [vocab_itos[i] for i in t], r, -math.log2(tr/(nr*t_sum)))

>>
[36, 0] ['this', '<unk>'] 51 13.057139984969156
[0, 11] ['<unk>', 'is'] 212 10.867692956269513
[11, 1932] ['is', 'written'] 0 28.342761082872915
[1932, 6] ['written', 'in'] 4 17.200826767745713
[6, 2404] ['in', 'english'] 5 16.779886287751758

頻度0回の ['is', 'written'] にも確率が割り当てられている。

交差検証 (削除推定)

大きい学習コーパスにおいて、ヘルドアウト推定では未知語 (r=0) に割り当てられる確率が大きくなってしまう問題がある。

解決方法として、いわゆる交差検証 (cross-validation)もしくは削除推定 (deleted estimate)を使ったヘルドアウト推定が考えられる。

データを2つに分割し、aとbとする。データaとデータbにおいて、それぞれ値を求める。

学習データをa、ヘルドアウトデータをbとしたとき
- aの頻度のタイプ数 $N^{a}_{r}$
- aの頻度のタイプ数を使ったbの出現回数 $T^{ab}_{r}$
学習データをa、ヘルドアウトデータをbとしたとき
- bの頻度のタイプ数 $N^{b}_{r}$
- bの頻度のタイプ数を使ったaの出現回数 $T^{ba}_{r}$

確率推定値は分割して推定した値を足して求める。

$\displaystyle{ P_{del}(w_1,..,w_n) = \frac{T_r^{ab}+T_r^{ba}}{N(N_r^a + N_r^b)} }$

参考： https://www.cl.uni-heidelberg.de/courses/ss15/smt/scribe5.pdf の 1.4.2

Good-Turing推定

Good-Turing推定も頻度 r を補正する手法。

Good-Turing推定自体は (NLP関係なく) 未知のデータの出現確率を求める手法。これを単語の頻度に適用することで、頻度を補正する。

Nr : 頻度rのサンプル数 (タイプ数)
N : データのサンプル数 $\displaystyle{ N = \sum _ {r} r N _ {r} }$

とした時、補正した r* は

$\displaystyle{ r^* = (r+1) \frac{N_{r+1}}{N_r} }$

であり、確率推定値は以下のように定義できる。

$\displaystyle{ P_{GT} = \frac{r^{*}}{N} = \frac{1}{N} (r+1) \frac{N_{r+1}}{N_r} }$

この式の詳しい導出過程は以下を参考に。

引き続きPennTreebankを使って bigramの r* を導出する。

# train で vocab作成
train_iter = torchtext.datasets.PennTreebank(split='train')
train_vocab = get_vocab(train_iter)

train_iter = torchtext.datasets.PennTreebank(split='train')
gt_unigram = get_ngram_count(train_iter, train_vocab)

# good-turing用の Nr
gt_nr = defaultdict(int)
for r in gt_unigram.values():
  gt_nr[r] += 1

# データサンプル数N
gt_n_sum = sum([r*nr for r, nr in gt_nr.items()])

補正した r* を計算する。 r=0の時は N_0 が0になってしまうので $r^{ * } = N_1 / N$ とした。

print(f"{0}\t{1*gt_nr[1]/ gt_n_sum:.4f}")
for i in range(1, 10):
  print(f"{i}\t{(i+1)*gt_nr[i+1]/gt_nr[i]:.4f}")

>>
0  0.2050
1  0.4020
2  1.2747
3  2.1785
4  3.1855
5  4.0148
6  5.3132
7  5.6534
8  7.1004
9  8.5488

0以外はrよりも小さくなっていることがわかる。

これでヘルドアウト推定と同様に未知語に対応でき、確率推定値まで算出できそうな気がする。

しかし、この方法には問題がある。 r が非常に大きい時に Nr もしくは Nr+1 が 0 になってしまう点。

下の実行だと r = 125 の時点で Nr は 0になっている。

print("r, N_r, N_r+1")
for r in range(1, 300):
  if gt_nr.get(r) is not None:
    continue
  else:
    print(f"{r}, {gt_nr.get(r)}, {gt_nr.get(r+1)}")
>> 
r, N_r, N_r+1
125, None, 4
136, None, 2
163, None, 5
171, None, 3
185, None, 2
189, None, 2
200, None, 1
208, None, None
209, None, 4
212, None, 1
(省略)