Pitman-Yor 過程に基づく可変長 n-gram 言語モデル
持橋大地  隅田英一郎
ATR 音声言語コミュニケーション研究所 /情報通信研究機構
daichi.mochihashi@atr.jp
IPSJ SIGNL 2007-NL-178
2007/3/29 (Thu)2007 年 4 月より, NTT コミュニケーション科学基礎研究所 PD
Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.1/30

Overviewislanguageofstates
iswillhe sheoforderlanguage

willstates

これまでの n グラム言語モデル• 深さ (n−1) の決まった Suffix Tree···unitedinfinite⇓
深さ無限の, 確率的な Suffix Tree

• Suffix Tree の事前 −→ 事後確率分布◦ 木をどうやって推定するか?

theベイズ可変長 ∞-グラム言語モデル• 無限可変長 Markov モデルの一般理論
Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.2/30

n グラムモデルとその問題 (1)• n グラムモデル · · · 言語の予測モデル◦ p(話す | 彼女 が) = 0.2, p(処理 | 自然 言語) = 0.7,p(見る | 彼女 が) = 0.1 . . .
◦ 文の確率を, 予測確率の積に分解 [マルコフ過程]
p(彼女 が 見る 夢) =p(彼女) × p(が | 彼女) × p(見る | 彼女 が) × p(夢 | が 見る)

Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.3/30

n グラムモデルとその問題 (1)• n グラムモデル · · · 言語の予測モデル◦ p(話す | 彼女 が) = 0.2, p(処理 | 自然 言語) = 0.7,p(見る | 彼女 が) = 0.1 . . .
◦ 文の確率を, 予測確率の積に分解 [マルコフ過程]
p(彼女 が 見る 夢) =p(彼女) × p(が | 彼女) × p(見る | 彼女 が) × p(夢 | が 見る)• 各単語は, 前の (n−1) 語の単語のみに依存する

p(w1 . . . wT ) =T

p(wt |wt−1 wt−2 · · · w1 )

(2)

t=1
T


p(wt | wt−1 · · · wt−(n−1) )
(2)


t=1
n−1 語
◦ n グラムモデル = 前の (n−1) 語を状態としたマルコフモデル
Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.3/30

n グラムモデルとその問題 (2)p(w1 . . . wT ) Tp(wt | wt−1 · · · wt−(n−1) )
t=1n−1 語(2)• n グラムモデル = 単語の総数 V に対して, V n−1 個の状態数◦ 指数的に爆発する◦ V = 10000 のとき, V 2 = 100000000 (3 グラム),V 3 = 1000000000000 (4 グラム), · · ·• 通常, n = 3 ∼ 5 程度が限界◦ Google 5 グラムは gzipped 24GB, V = 13653070− V 2 = 186406320424900 (3 グラム)− V 3 = (天文学的な数) (4 グラム)◦ しかし, そもそも…

Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.4/30

n グラムモデルとその問題 (3)• n グラムモデルは, 単純な (n−1) 次のマルコフ過程＝直前 (n−1) 語を丸覚え◦ 3 グラム, 4 グラム, 5 グラム, ... のデータはノイズだらけ− に 英語 が− の が # #− は 修了 宮本 益
− が あり 独自 に 法医学− は ゼネラル・モーターズ GM や
◦ 空間計算量・時間計算量の点でも, 非常に無駄が大きい• 言語的に意味がある n グラムは何か?

Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.5/30

n グラムモデルとその問題 (4)• 現実の言語データには, 3 グラム, 5 グラムを超えるような長い系列が頻繁に現れる◦ the united states of america◦ 京都 大学 大学院 情報 学 研究科◦ 東京 地検 特捜 部 の 調べ に よる と◦ そんな 事 より 1 よ 、 ちょいと 聞い て くれ よ 。…
• チャンク (句) とみなして一単語にする方法もあるが…
◦ 人間の主観的な “正解” に依存◦ どこまでを句とすればよいか [境界は 1/0 か?]◦ 上のような, 慣用句などのフレーズを全て列挙するのは不可能• バイオインフォマティクス等とも共通する問題◦ DNA, アミノ酸, タンパク質などの系列− “正解” が自明ではない

Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.6/30

可変長 n グラム言語モデル• n グラムの n を文脈に応じて可変長にできないか?
◦ “可変長 n グラム言語モデル” … 音声言語分野を中心に提案◦ 踊堂, 中村, 鹿野 (1999), Stolcke (1998), Siu and Ostendorf(2000), Pereira et al. (1995) など◦ しかし,⇓• これまでの “可変長 n グラム言語モデル”=巨大な n グラムモデルの枝刈りによる方法◦ 指数的に爆発する最大モデルを, 事前に作っておく必要− 可変長モデルの意図と矛盾− n グラムを減らすことはできても, 増やすことはできない◦ MDL, KL ダイバージェンスなどによる枝刈り− 性能があまり悪化しないように, 余分な n グラムを減らす− 基準はモデルとは別で, 後付け
Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.7/30

可変長 n グラム生成モデル• なぜ, 正しい可変長生成モデルが存在しなかったか?

⇓◦ n グラム分布は, n が大きくなるほどスパース◦ n グラム分布は, (n−1) グラム分布に依存◦ これを階層的に生成する理論的なモデルは存在しなかった• しかし..

Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.8/30

ベイズ n グラム言語モデル• Hierarchical Pitman-Yor Language Model (HPYLM)(Yee Whye Teh, 2006)◦ 階層ベイズの考えに基づく, n グラム言語モデルの完全なベイズ生成モデル◦ Kneser-Ney スムージングと同等以上の性能 (K-N はその近似)◦ 階層ディリクレ過程 (HDP) の拡張• Pitman-Yor 過程 (=2-パラメータポアソン=ディリクレ過程 PD(α, θ)(Pitman and Yor 1997)) を階層化◦

Marc Yor (Université Paris VI, France)◦

Jim Pitman (Dept. of Statistics, Berkeley)◦ 測度論に基づく数学的な詳細については,
http://chasen.org/˜daiti-m/paper/svm2006-hpylm.pdf を参照のこと.
Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.9/30

HPYLM (1)• n グラム分布は, 深さ (n−1) の Suffix Tree で表せる
• 例として, トライグラムを考える

Depth 02

andsing like will

1

shego
sing

helike

it

bread

model
languagebutteris=客 =代理客 (コピー)◦ ‘she will’→‘sing’ を予測…木を  → will → she の順にたどる◦ 止まった, 深さ 2 のノード (トライグラム) から, sing の確率を計算
Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.10/30

HPYLM (2)

Depth 012

andsing like will
shego
sing

helikeit

breadmodel
languagebutteris=客 =代理客 (コピー)• ノードの持つ客 (単語カウント) の分布から, p(sing|she will) を計算 → p(like|she will) はどうする?
◦ ‘like’ のカウントがない• 客のコピー (代理客) を上のノードに確率的に送る◦ ‘he will like’ から送られた上のノードの客 ‘like’ を使って,バイグラムと補間して確率を計算
Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.11/30

HPYLM から可変長モデルへ

Depth 012

andsing like will
shego
singhelikeitbreadmodellanguage

butteris=客 =代理客 (コピー)• HPYLM の問題…客 = データのカウントがみな, 深さ 2 のノードに集まるのでいいか?
◦ ‘will like’ は本当は深さ 1 (バイグラム) で十分◦ ‘the united states of america‘はもっと深いノードが必要⇓• 客を違った深さに追加する確率過程.
Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.12/30

Variable-order Pitman-Yor Language Model (VPYLM)
1 − qi1 − qj1 − qkijk• 客 (カウント) を, 木のルートから確率的にたどって追加• ノード i に, そこで止まる確率 qi (1−qi :「通過確率」) がある◦ qi は, ランダムにベータ事前分布から生成されるqi ∼ Be(α, β)(2)◦ ゆえに, 深さ n のノードで止まる確率はp(n|h) = qnn−1(1 − qi ) .

(2)

i=0
Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.13/30

Variable-order Pitman-Yor Language Model (2)0.95

isoforderlanguage

will
0.95 × 0.7
states
0.95 × 0.7 × 0.6···

unitedinfinite

0.95 × 0.7 × 0.6 × 0.4
the• 「通過確率」 1 − qi が大きい … 客が深いノードに到達できる◦ 長い n グラムに対応する• 「通過確率」が小さい … ‘will’ など, 浅いノードで充分な文法的関係
Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.14/30

Inference of VPYLM• もちろん, われわれは自然言語の Suffix Tree がもつ真の qi の値は知らない◦ どうやって推定したらいい?
• VPYLM の生成モデル: 訓練データ w = w1 w2 w3 · · · wT に,隠れた n-gram オーダー n = n1 n2 n3 · · · nT が存在

p(w) =

np(w, n, s)(2)

ss: 代理客を含む客全体の配置• Gibbs サンプリングにより, この n は推定できる

Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.15/30

Inference of VPYLM (2)• Gibbs サンプリング: マルコフ連鎖モンテカルロ法 (MCMC)の一種◦ ある隠れ変数を, それ以外を条件にして順番にサンプリング◦ 充分サンプリングを繰り返すと, 真の分布に収束する• 単語 wt の生成された n-gram オーダー nt を,nt ∼ p(nt |w, n−t , s−t )(2)のようにサンプリング• ベイズの定理より, nt = 0, 1, 2, · · · , ∞ についてp(nt |w, n−t , s−t )∝ p(wt |nt , w, n−t , s−t ) · p(nt |w−t , n−t , s−t )





nt -グラムの予測確率 深さnt に到達する確率(2)◦ 2 つの確率のトレードオフ (nt が深すぎるとペナルティ)◦ 第 1 項: HPYLM の nt -グラム予測確率; 第 2 項は?
Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.16/30

Inference of VPYLM (3)w(a, b) = (100, 900)
900+β1000+α+β· · · wt−2 wt−1 wt wt+1 · · ·n···

wt−1

←→
2324···

70+β80+α+β20+β50+α+β• 他の客の到達した深さから,

β5+α+β(a, b) = (10, 70)
wt−2(a, b) = (30, 20)

wt−3(a, b) = (5, 0)

ノードの持つ qi が推定できる···• ノード i で他の客が止まった回数を ai , 通過した回数を bi とすると,p(nt = n|w−t , n−t , s−t ) = qn=n−1
(1 − qi )(2)i=0
an +αn−1

an +bn +α+β

i=0bi +β.
ai +bi +α+β(2)Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.17/30

Implementationstruct ngram {ngram *parent;
splay *children;
splay *words;
int ncounts;
int ntables;
int stop;
int through;int id;};

node

...
...

...

• 子ノード/予測語の検索にスプレー木 (Sleator and Tarjan 1985)

を使用◦ ならしオーダー O(log n) の二分順序木◦ アクセスの際に, 木を自己組織的に最適化して高速化• splay *children = (ngram **),

splay *words = (restaurant **)• Gibbs サンプリングの大幅な高速化 (100 倍以上)
Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.18/30

実験• 英語: 標準的な, NAB(North American Business News) コーパスの Wall Street Journal セットから 10M 語を訓練データ, 1 万文をテストデータ◦ Chen and Goodman (1996), Goodman (2001) などと同じ
データ◦ 総語彙数 =26,497 語• 日本語: 毎日新聞データ 2000 年度から, 10M 語 (52 万文) を訓練

データ, 1 万文をテストデータ◦ 総語彙数 =32,783 語• nmax = 3, 5, 7, 8, ∞ で実験◦ パープレキシティ自体は, n = 7 程度で飽和 (Goodman 2001)

Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.19/30

テストセットパープテキシティとノード数n

SRILM HPYLM VPYLM Nodes(H) Nodes(V)3578∞

118.91
107.99107.24107.21—113.60101.08
N/A
N/A—

113.74101.69100.68100.58161.681,417K
12,699K
N/A
N/A—

1,344K
7,466K
10,182K
10,434K
6,837K() NAB コーパス (英語)nSRILM HPYLM VPYLM Nodes(H) Nodes(V)

35
78
∞

84.74
77.88
77.51
77.50
—

78.06
68.36
N/A
N/A
—

78.22
69.35
68.63
68.60
141.81

1,341K
12,140K
N/A
N/A—() 毎日新聞コーパス (日本語)

1,243K
6,705K
9,134K
9,490K
5,396K

Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.20/30

Suffix Tree と確率的フレーズ

wn−1
wn−2
wnw1

• 木の根 (ユニグラム) から単語を生成するかわりに,子ノードを確率的にたどってからフレーズを生成◦ VPYLM の確率オートマトン表現 (初期状態が )• フレーズ w = w1 · · · wn−2 wn−1 wn が Suffix Tree から生成される確率は,

p(w) =qn−1n−2(1−qi )

· p(wn |w1 · · · wn−1 ) .

(2)

i=0
Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.21/30

8-gram VPYLM から得られた確率的フレーズ [WSJ]p
0.9784
0.9726
0.9556
0.95120.93940.8896
0.88310.86960.7566
0.7134
0.6617:

Stochastic phrases in the suffix tree
primary new issues
ˆ at the same timeamerican telephone &is a unit of
to # % from # %in a number ofin new york stock exchange composite tradinga merrill lynch & co.
mechanism of the european monetary
increase as a result oftiffany & co.

Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.22/30

8-gram VPYLM から得られた確率的フレーズ [毎日新聞]
p0.97250.96780.95920.95840.91850.88770.86760.80680.78700.76610.72420.64720.50190.5000:Stochastic phrases in the suffix tree
早けれ ば
日 発表 し た
来 年 # 月
官房 審議 官いる に も かかわら
震度 は 次 の 通り
フェルメール と その 時代ある と し て いる 。
こと が # 日 明らか に なっ
記録 # 分 # 秒 #全豪オープン 第 # 日 は # 日
ˆ 国際 オリンピック 委員 会 IOC
ロッテ # 勝 # 敗 # 分 。
行う こと を 明らか に し た
Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.23/30

LDA によるトピック適応化 [1/2]• LDA (Blei et al. 2003)· · · 文書のトピック混合モデル◦ 各文書に, 隠れたトピック混合比 θ がある◦ 文書の単語は, θ から確率的にトピックを選んで生成◦ 例: θ = (p(t1 ), p(t2 ), p(t3 ), p(t4 )) = (0.2, 0.4, 0.1, 0.3)

文書 = w1 w2 w3 w4 w5 w6 w7 · · ·(単語ごとにトピックが異なる)• トピック別の VPYLM を考えることができる◦ 単語ごとに違った可変長 n-gram から生成される◦ 複数の VPYLM の混合による予測− 性能悪化!
• データをトピック毎に分割すると, n グラムのスパースネスが深刻◦ 分割しない方が, カウントがヒットする◦ どうしたらいい?

Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.24/30

LDA によるトピック適応化 [2/2]• 解決…ユニグラム分布のみを混合分布にする (混合 Pitman-Yor測度)◦ Suffix Tree のルートで, 客がトピック別のレストランに入る

Depth 0
12

she

he

does likesingmodel

andsing like will
it

bread

languagebutteris=customer =proxy customer

Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.25/30

実験結果 (VPYLDA)
Model

PPL

VPYLDA (M = 5)
(M = 10)(M = 20)VPYLM

104.69103.57103.28105.30• 20news-18828 コーパスを使用 (4,000 training documents, 400test documents), lexicon=10,477• 性能は改善しているが, その差はわずか• なぜか?
◦ 木の枝に客を追加/削除しても, 木のルートにあるトピック別客分布に反映されないことが多い◦ カウントの追加/削除が, 枝のレベルで吸収されてしまう◦ 階層的混合モデルの, 新しい推定法が必要.
Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.26/30

VPYLM からの生成「レンタ・カーは空のグラスを手にとり、蛇腹はすっかり暗くなっていた。それはまるで獲物を咀嚼しているようだった。彼は僕と同じようなものですね」と私は言った。
「でもあなたはよく女の子に爪切りを買った。そしてその何かを振り払おうとしたが、今では誰にもできやしないのよ。私は長靴を棚の上を乗り越えるようにした。...
• 村上春樹「世界の終りとハードボイルド・ワンダーランド」

からのランダムウォーク生成 (VPYLM, n = 5)

• 普通の 5-gram LM では, オーバーフィットのため学習データがそのまま生成されてしまう• 確率的に適切な長さの文脈を用いることで, 特徴をとらえた

言語モデル◦ 確率的フレーズ: 『なるほど 」 と 私 は 言っ』(0.6560),『やれやれ 」 と』(0.7953), 『、 と 私 は』(0.8424), . . .
Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.27/30

本研究のまとめ• 階層 Pitman-Yor 過程を拡張することで, 可変長 n グラムの完全な生成モデルを示した◦ 深さの様々に異なる確率的な Suffix Tree を考え, ベイズ推定◦ Markov モデル全てに適用できる, 一般的な理論◦ 無駄な n グラムを覚えず, 効率的• 各単語の生まれた, 隠れた n グラム文脈長を推定できる◦ 原理的に, n は ∞ まで可能
• 言語モデルの副産物として, 「確率的な句」を取り出すことができる◦ 「Named Entity (NE)」の完全な教師なし学習による獲得◦ NE に限らず, 慣用句などのフレーズも取り出せる◦ 単語分割の粒度に影響されない

Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.28/30

展望と課題• 提案法は, 確率的な Suffix Tree を用いたベイズ正則化◦ Suffix Tree の事前分布には, 共通の一つのベータ分布を用いた◦ どの深さのノードでも, qi の事前分布が同じでよいか?
◦ qi を生成する, もっと精密な確率モデル (eg. Pitman (2002))• トピック適応化にはさらに理論が必要◦ トピック毎の n グラムを作ると, スパースネス増大◦ 1-gram,2-gram,.. の階層ごとに混合数が異なるはず◦ 階層的な混合モデルと, その推定方法• 空間的・時間的計算量のさらなる削減◦ ギブスサンプリングは, 確率最大の点推定ではない→ 確率を最大化するモデル探索 (cf. Hal Daume III (2007))◦ Suffix Tree および Splay Tree の, メモリ使用量の効率化

Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.29/30

Thank you
ご清聴ありがとうございました。

Pitman-Yor 過程に基づく可変長 n-gram 言語モデル – p.30/30