松本研究室 Doctor Lecture 2004

言語モデル
Daichi Mochihashi

daiti-m@is.naist.jp
daichi.mochihashi@atr.jp
NAIST 松本研究室 / ATR SLT Dept.2 (SLR)
2004.07.16

Language models D-lec 2004 in cl-lab – p.1/39

Overview
What is the Language Model?
N-gram models (including various smoothing)
Variable N-grams
N-gram Language Model evaluation
Whole sentence maximum entropy
Long distance models(Old) cache/trigger models
Latent variable models

Language models D-lec 2004 in cl-lab – p.2/39

What is the Language Model?

確率的言語モデルとは?
単語列 w = w1 w2 w3 · · · wn の結合確率 p(w)を与えるモデル．

w の定義は任意
フレーズ，文, 文書, 動詞句, . . .
生成モデル
サイコロをふることで，p(w) に従う任意の新しいフレーズ，文, 文書, . . . を生成できる．
自然の言語現象のモデル ⇔ より適切な符号化.
(dual problem)
Language models D-lec 2004 in cl-lab – p.3/39

Why Language Models?

音声認識 (Speech recognition)
機械翻訳 (Brown et al. 1990)

p(J|E) ∝ p(E|J)p(J) (翻訳モデル × 言語モデル)
情報検索 (Zhai & Lafferty 2001, Berger & Lafferty 1999)
テキスト入力 (HCI), OCR/スペル訂正 (基礎技術)

Shannon ゲーム, 情報理論/圧縮, テキスト生成

Language models D-lec 2004 in cl-lab – p.4/39

How to model p(w)?
p(w) = p(w1n ) をどのようにモデル化するか?
Conditional method (N-gram)Tp(w) =p(wt |w1t−1 )

(1)

t=1

“Whole sentence” method
p(w) ∝ p0 (w) · exp(λi fi (w))(2)i

注: (2) は (1) を含む (p0 (w) = pcond (w))

Language models D-lec 2004 in cl-lab – p.5/39

N-gram approximation modelp(w1n ) =Tp(wt |wt−1 wt−2 · · · w1 )

(3)

t=1

T


p(wt | wt−1 · · · wt−(n−1) )(4)

t=1n−1 語 T t=1 p(wt |wt−1 , wt−2 ) : トライグラム (n = 3)
T=: バイグラム (n = 2)t=1 p(wt |wt−1 ) T: ユニグラム (n = 1)t=1 p(wt )(5)

注: ベイズの公式 p(X, Y |Z) = p(X|Y, Z)p(Y |Z) を式 (3) で再帰的に適用している
Language models D-lec 2004 in cl-lab – p.6/39

Language Model Smoothing

以下，説明のためにバイグラムの推定を考える．

fi|j , fj をそれぞれ wj → wi , wj の生起頻度とすると,最尤推定:

fi|jp̂(i|j) =.
fj(6)ほとんどの n-gram が確率 0 (データスパースネス)⇓1. n-gram のスムージング
2. より短い文脈長での推定を使う (バックオフ)
3. クラスベース n-gram

Language models D-lec 2004 in cl-lab – p.7/39

Katz’s Backing-Off

fi|j = 0 (または k 以下) の場合にどうするか?
p(i|j) =(1 − α(j)) · p̂(i|j) when fi|j > 0α(j) · p(i)when fi|j = 0(7)fi|j > 0 の場合は, 最尤推定値を少し減らして,そのまま使う
fi|j = 0 の場合は, 上で減らした分をもらって,ユニグラム p(i) に従って分配する
バックオフ (Back-off):
推定の際に，より短い文脈での推定値を用いること.
(トライグラム以上でも同じ)
Language models D-lec 2004 in cl-lab – p.8/39

Class-based n-gram

単語の連接確率をそのまま用いるとスパースネスの問題→ クラスの連接確率で置き換える (like HMM)

w1 , w2 , . . . に対応するクラスを (確率 1 で) c1 , c2 , . . . とおTくと，p(w1T ) =p(wt |ct )p(ct |ct−1 )
(8)
ここで,

t=1

1(9)
[log p(wt |ct ) + log p(ct |ct−1 )]Tp(c1 , c2 )→p(c1 , c2 ) logp(w) log p(w)+T →∞p(c1 )p(c2 )c1 ,c2w
=I(c1 , c2 ) − H(w). (相互情報量最大化)

log p(w1T ) =c1 ,c2Language models D-lec 2004 in cl-lab – p.9/39

Langage Model Smoothing

Simple Smoothing Methods
Laplace smoothing, Lidstone’s law
古典的な統計的手法
Extended Smoothing Methods
Good-Turing smoothing, Kneser-Ney Smoothing,
Bayes smoothing
NLP 向けに考案されたスムージング手法
他にも色々あるが，最初の 2 つは基礎知識として重要

Language models D-lec 2004 in cl-lab – p.10/39

Simple Smoothing Methods

Laplace smoothingp(i|j) =fi|j + 1

fi|j + 1=W
fj + Wi (fi|j + 1)

(10)

Lidstone’s law パラメータ: λ (特に, λ = 1/2)
p(i|j) =fi|j + λfi|j + λ=Wfj + W λi (fi|j + λ)fi|j
1=µ·+ (1 − µ) ·fjW(11)fj(µ =)
fj + W λ(12)均一なユニグラム確率 との線形補間になっている(不適切!)
Language models D-lec 2004 in cl-lab – p.11/39

Extended Smoothing methods

Good-Turing smoothing
よく使われる(Modified) Kneser-Ney smooothing
Chen and Goodman (1998) の有名な比較によれば，(下のものを除いて) 精度が現在最良
Hierarchical Bayes optimal smoothing (MacKay 1994)

Language models D-lec 2004 in cl-lab – p.12/39

Good-Turing smoothingp(i|j) =N (fi|j +1)(fi|j + 1) · N (fi|j )fj

if fi|j < θ.

(13)

N (x) : x 回現れた n-gram の総数
fi|jcf. 最尤推定値 p̂(i|j) =fj
閾値 θ の最適値は一意に決まらない
出なかった n-gram には均等の確率 (バックオフが必要)
p(well|quite) = p(epistemological|quite)?
単語全体にわたって正規化する必要がある
Language models D-lec 2004 in cl-lab – p.13/39

(Modified) Kneser-Ney smoothing

Absolute discounting (頻度から一定数を引く)
fi|j − D(fi|j )+ γ(j)p(i)p(i|j) =fj(14)

D(n) : ディスカウント関数
N (1)
N (2)
n = 1 の場合: D(1) = 1 − 2 · N (1)+2N·(2) N (1)
N (1)
N (3)
n = 2 の場合: D(2) = 2 − 3 · N (1)+2N·(2) N (2)
N (1)
N (4)
n ≥ 3 の場合: D(3+) = 3 − 4 · N (1)+2N·(2) N (3)γ(j) は単語 j に後続する単語の種類数から決まる
Language models D-lec 2004 in cl-lab – p.14/39

Hierarchical Bayes Optimal
Smoothing (MacKay 1994)

fi|j + αi
E[p(i|j)] =i (fi|j + αi )fjα0=· p̂(i|j) +· ᾱifj + α 0
fj + α 0
where α0 =(15)(16)αik αk and ᾱi =α0α = (α1 , α2 , . . . , αW ) : ハイパーパラメータ.
バックオフと線形補間の両方の性質を持つ適応的補間
ただし，ᾱi = p(i) (Unigram)(α はどうやって計算?)
Language models D-lec 2004 in cl-lab – p.15/39

Hierarchical Bayes Optimal
Smoothing (2)p(F |α) =WΓ(α0 )

j=1W
i=1 Γ(αi )·W
i=1 Γ(fi|j + αi )Γ(fj + α0 )(17)

これは α に関して上に凸で, 大域的最適解が存在.
次の iteration で解くことができる (Minka 2003).
(t+1)
(t)
= αi ·αij Ψ(fi|j + αj ) − Ψ(αj )j Ψ(fj +k αk ) − Ψ(k αk )(18)

MATLAB で 45 行
詳細は SVM2004 でLanguage models D-lec 2004 in cl-lab – p.16/39

Variable Order n-grams (1)

いつも同じ文脈長 (ex. 2 words) を用いる → 不適．
助詞/助動詞の連続, typical なフレーズ(牛鮭定食 で も 食っ て なさいっ て こっ た)
単語の切り方に依存する多くの単語からなる Named Entity.
文脈長を適応的に変えられないか?

Language models D-lec 2004 in cl-lab – p.17/39

Variable Order n-grams (2)Pereira et al. (1995) “Beyond Word N-Grams”
基礎となる研究:
Ron, Singer, Tishby (1994) “The Power of Amnesia”
Prediction Suffix Tree (PST)
確率オートマトンと等価.
Willems at al. (1995) (情報理論/情報圧縮)
Context Tree Weighting method (CTW)
情報理論，圧縮の分野で注目されている圧縮方法の一つ (ex. Sadakane 2000)
以下，基本的なアイデアを紹介

Language models D-lec 2004 in cl-lab – p.18/39

Ron, Singer, Tishby (1994)

Prediction Suffix Tree (PST)1eg(0)=0.5g(1)=0.5110
100g(0)=0.3g(1)=0.7g(0)=0.6g(1)=0.4010
g(0)=0.8g(1)=0.2g(0)=0.6g(1)=0.400g(0)=0.9g(1)=0.1↑ マッチ
入力列 h = 00100101110 → p(0|h) = 0.6, p(1|h) = 0.4
Language models D-lec 2004 in cl-lab – p.19/39

Ron, Singer, Tishby (1994)(2)

PST は確率オートマトンと等価
ノード s (例: 010) について，子ノード σs (σ ∈ {0, 1}) の追加 (例: 010 → 0010) は, 追加した時のエントロピー差p(σs) · D(p(·|σs)||p(·|s))(19)が大きいときのみ (= Yodo (1998))
聖書のテキスト
エントロピー差の閾値  = 0.001
N = 30 gram (文字ベース)⇓状態数 ≤ 3000, 状態の例: ‘shall be’, ‘there was’
Language models D-lec 2004 in cl-lab – p.20/39

Pereira et al. (1995)

PST の Mixture (CTW (Willems et al. (1995)) をベース)
オンラインベイズ推定になっている
訓練単語列を w = w1 w2 w3 · · · wN (N very large) とすると，PST T についてN
p(w1 · · · wN |T ) =γCT (w1 ···wi−1 ) (wi )(20)
このとき,i=1

p(w1 · · · wN +1 )p(wN +1 |w1 · · · wN ) =p(w1 · · · wN )T ∈T p(T )p(w1 · · · wN +1 |T )=T ∈T p(T )p(w1 · · · wN |T )

(21)

(22)

p(T ) : PST T の prior.
Language models D-lec 2004 in cl-lab – p.21/39

Pereira et al. (1995) (2)Tree Mixture:p(T )p(w1 · · · wN |T ) = Lmix ()(23)T ∈Tは再帰的に計算できる.

Lmix (s) = α Ln (s) +(1 − α)  
自ノードのemission 確率

σ∈W



Lmix (σs)
(24)



子ノードの emission 確率

α : Tree prior. (0 ≤ α ≤ 1)

Language models D-lec 2004 in cl-lab – p.22/39

Pereira et al. (1995) (3)

実際には,p(wn |w1 · · · wn−1 ) = γ̃ (wn )(25)

ここで，PST のノード s での単語 wn の出力確率γ̃s (wn ) は,γ̃s (wn ) =γs (wn )qn γs (wn ) + (1 − qn )γ̃wn−|s| s (wn ): s が葉: s が枝(26)補間比 qn をオンラインでアップデートできることと，γ̃(w) の推定が再帰的になっているところがミソ.

Language models D-lec 2004 in cl-lab – p.23/39

Language Model evaluation

言語モデルをどのように評価するか?
パープレキシティ (Perplexity)
クロスエントロピー (Cross Entropy)
その前に..

Language models D-lec 2004 in cl-lab – p.24/39

Basic of Basics
11
確率 p =∴ 分岐数 =分岐数pShannon 符号長 (自己情報量)
1log= − log(p(x))
p(x)

(27)

エントロピー = 平均 Shannon 符号長H(p) = −p(x) log p(x)(28)

x=  − log p p(29)Language models D-lec 2004 in cl-lab – p.25/39

Perplexity

パープレキシティ (Perplexity) = 平均分岐数

T

1/T

1(幾何平均)t−1p(wt |w1 )
t=1
 
1/TT

1

= exp logt−1p(wt |w1 )
t=1


T1
= exp
− log p(wt |w1t−1 ) .
T t=1

PPL(w1T ) =(30)

(31)

(32)

Language models D-lec 2004 in cl-lab – p.26/39

Cross Entropy (1)Kullback-Leibler ダイバージェンス
p(x)D(p||q) =p(x) logq(x)x(33)= log p(x) − log q(x)p(34)= (− log q(x)) − (− log p(x))p(35)∴ p(x) のかわりに q(x) で情報源を符号化したときの符号長の差 (の平均).
→ 自然の持つ確率 p をモデル q で近似するとき，D(p||q) を最小化すればよい.
Language models D-lec 2004 in cl-lab – p.27/39

Cross Entropy (2)D(p||q) ==pp logq(36)

p log p −p log q= −H(p) −p log q → 最小化.
ゆえに, クロスエントロピー H(p, q) をH(p, q) = −p(x) log q(x) (= − log q(x)p )

(37)
(38)

(39)xと定義すれば, KL ダイバージェンス最小化はクロスエントロピー最小化と同値.
(パープレキシティは, 形式的に p(x) が Uniform な場合に相当)
Language models D-lec 2004 in cl-lab – p.28/39

Whole sentence maximum entropy (1)p(s) ∝ p0 (s) · exp(Λ · F (s))(40)

p0 (s) : 文 s のデフォルト確率Λ = (λ1 λ2 . . . λn ) : ME パラメータ
F (s) = (f1 (s) f2 (s) . . . fn (s)) : 素性ベクトル
注意:

p0 (s) を n-gram 確率にとれば，Whole sentence ME は
常に n-gram に対する改良となる
Random Field のセルの数 (= 文の長さ) が大きいため，効率的な素性を設定することはやや難しい

Language models D-lec 2004 in cl-lab – p.29/39Whole sentence maximum entropy (2)パラメータ推定/制約:
p(s)fi (s) = fi p̂ − (正則化項).

(41)

s

可能な文全体について和をとるのは不可能⇒ 左辺はモンテカルロサンプリングで近似.
式 (40) の p(s) に従って「文」を次々と生成する
Gibbs sampling (シンプル) (Pietra, Lafferty 1995)
Independent Metropolis sampler
Importance Sampling from n-gram

Language models D-lec 2004 in cl-lab – p.30/39

Whole sentence maximum entropy (3)生成された文の例 (Rosenfeld et al. 2000)
 What do you have to live los angeles 

 A. B. C. N. N. business news tokyo 

 Be of says I’m not at this it 

 Bill Dorman been well I think the most 


(Pietra, Lafferty 1995) 英単語のスペルのサンプリング
was, reaser, in, there, to, will, ,, was, by, homes,
thing, be, reloverated, ther, which, conists, at,fores, anditing, with, Mr., proveral, the, ***, ...

Gibbs sampling で生成

Language models D-lec 2004 in cl-lab – p.31/39

Whole sentence maximum entropy (4)しかし...
ベースライン (n-gram) モデル p0 : PPL = 81.37
Whole Sentence ME : PPL = 80.49 ± .02
なぜ??
素性 f の効果: KL ダイバージェンス D(p̂(f )||p(f ))p̂(f )
1 − p̂(f )D(p̂(f )||p(f )) = p̂(f ) log+ (1 − p̂(f )) logp(f )1 − p(f )p̂(f ) p̂(f ) log
p(f )log(p̂(f ))−log(p(f )) は大きいが, p̂(f ) が非常に小さい
ME+隠れ変数モデル? (eg. ME=HMM (Goodman2002/2004), LME (Wang 2003))
Language models D-lec 2004 in cl-lab – p.32/39

Long Distance Models

意味的な “文脈” を考慮するモデル(Old) キャッシュ/トリガモデル
潜在変数モデルLanguage models D-lec 2004 in cl-lab – p.33/39

Cache/trigger models

Cache model「一度出た単語は再び表れやすい」ため，k 語前の履歴に出てきた単語を “キャッシュ” して, 確率を上げる
k はいくつに取ればよい?
同じ単語は直後は繰り返されない (Beeferman1997a)
Trigger model‘hospital’ が出てくると，‘nurse’ や ‘disease’ が出やすくなる
訓練データに存在する有意な単語の組み合わせとその距離効果を ME で学習 (Beeferman 1997b)
可能な組み合わせ ∼ W × W  1 億 !
Language models D-lec 2004 in cl-lab – p.34/39

Latent Variable Models

テキストの生成モデルの応用
テキストや現在の文脈に対して，隠れトピックのMixture Model を考える
→ 隠れたトピックの混合比がわかれば，次の単語を予測できる!
PLSI 言語モデル (Gildea & Hofmann 1998)
LDA 言語モデル (三品 2002, 高橋 2003)

Language models D-lec 2004 in cl-lab – p.35/39

PLSI Language model

PLSI によって, K 個のトピック別ユニグラム
p(w|z1 ), p(w|z2 ), . . . , p(w|zK ) が EM で計算できる
このとき，w = w1 w2 · · · wn がこれらのユニグラムの混K合として
p(w|λ) =λi p(wj |zi )
(42)
ji=1

→ 混合比 λ = (λ1 , . . . , λK ) がわかれば,K
p(w|w1 · · · wn ) =λi p(w|zi )(43)i=1として計算できる.

Language models D-lec 2004 in cl-lab – p.36/39

LDA Language model

PLSI LM では, 混合比 λ が最尤推定だった→ オーバーフィットの危険性.
λ 自体に確率分布を与え，積分除去 (ベイズ推定)
p(w|w) =p(w|λ)p(λ|w)dλ(44)= K
 i=1

λi p(w|zi ) · p(λ|w)dλK
=λi |wp(w|zi )

(45)

(46)

i=1

Language models D-lec 2004 in cl-lab – p.37/39

Future of Long distance models

文脈の時間順序を考慮したモデル. (今の自分の研究)

Hierarchical Mixture (NIPS 2003) のオンラインアップ
デート?
Maxent モデルとの混合
文法的要素 (Long distance dependencies).

Language models D-lec 2004 in cl-lab – p.38/39

Conclusion
Let’s model a language!
Generative model and Bayesian method make us
happy.. :-)お疲れさまでした．

Language models D-lec 2004 in cl-lab – p.39/39