Vol. 0

No. 0

情報処理学会論文誌

2007

階層 Pitman-Yor 過程に基づく可変長 n-gram 言語モデル
持 橋 大 地 †,☆ 隅 田

英一郎 †本論文では, n-gram 分布の階層的生成モデルである階層 Pitman-Yor 過程を拡張することで, 各単語の生まれた隠れたマルコフ過程のオーダーを自動的に推定し, 適切な文脈を用いる可変長 n-gram
言語モデルを提案する．無限の深さをもつ予測接尾辞木上の確率過程を考えることにより, 句を確率的に発見し, 適切な文脈長を学習することができる．これにより, 従来不可能だった高次 n グラムの学習が可能になる．本手法は言語モデルだけでなく, マルコフモデル一般について, そのオーダーをデータから推定できる可変長生成モデルとなっている．英語および日本語の標準的なコーパスでの実験により, 提案法の有効性を確認した．

Bayesian Variable Order n-gram Language Model based on
Hierarchical Pitman-Yor Processes
Daichi Mochihashi ? and Eiichiro Sumita ?
This paper proposes a variable order n-gram language model by extending a recently proposed model based on the hierarchical Pitman-Yor processes. Introducing a stochastic process
on an inﬁnite depth prediction suﬃx tree, we can infer the hidden n-gram context from which
each word originated. Experiments on standard large corpora showed validity and eﬃciency ofthe proposed model. Our architecture is also applicable to general Markov models to estimate
their variable orders of generation.

は実際上取り扱えないという問題があった．

1. は じ め にしかしながら, 現実の言語データには “The United

単語間のマルコフ過程によって文の確率を計算する

States of America” のように, トライグラムを超える

nグラムモデルは, Shannon の歴史的な論文1) で最初

長いフレーズや固有名詞が頻出する．これらをチャンに導入されて以来, 自然言語処理の様々な場面に適用

クとして分類し, 一単語とみなす方法もあるが, これされ, その有効性が示されてきた, 基礎的で重要な方には教師データが必要なために主観に依存する上, 慣法である．

用句のような系列を全てカバーすることは難しいといn グラムモデルは, 直前の (n−1) 個の単語列を状う問題がある．☆☆ 特に, 日本語や中国語のように単語態とした (n−1) 次のマルコフモデルにより, 次の単語

境界が曖昧な言語の場合, 品詞体系によっては短い助の条件つき確率を計算していく．このとき, 状態数は詞の連続などによる長い n グラムが頻出する可能性が単語の総数を V とすると V n−1 のオーダーとなり, nあり, 「単語分割の粒度に依存しない言語モデル」がを 1 増やすと総パラメータ数は通常数万倍となり, 指特に重要だと考えられる．

数的に爆発する．このため, 様々なスムージング法をまた逆に, “longer than” のように短い n グラムで用いた場合でも, 通常 n = 3 (トライグラム) から最大充分な文法的関係も多いことを考えると, n を常に 3

でも n = 4, 5 程度が限界であり, それ以上の長い相関などの固定値とするのではなく, 文脈に応じて必要なだけの長さを用いる「可変長 n グラム言語モデル」の† ATR 音声言語コミュニケーション研究所 / （独）情報通信研
究機構
ATR Spoken Language Communication Research Laboratories / National Institute of Communications Technology☆
現在， NTT コミュニケーション科学基礎研究所
Presently with NTT Communication Science Laboratories

意義は, 言語学的にみても高いと考えられる．
しかしながら, これまで提案されてきた “可変長 n グ
ラムモデル” はいずれも, 実際には最大オーダーの n グ☆☆

1

何が句であるかには正解はなく, 確率的にしかとらえられないと考えている2) ．さらに, この区切りは固定ではなく, 一般に文脈にも依存する．

情報処理学会論文誌

2

ラムを最初に作り, それを枝刈りするか3)4) , または頻5)度閾値でカットオフを行うもの

2007
²

深さ

0

であった．☆ この際の閾値や MDL などの基準はモデルとは別に外部から

1

sing like

will

and

model

与えるものであり, さらに, 指数的に大きくなる最大she

モデルを事前に作る必要がある点で, 可変長モデルのhe

2

構成意図と矛盾していた．可変長マルコフモデルはバcryイオインフォマティクス6) および統計学7) の分野でも

sing

like

it

bread

languagebutteris=客=代理客 (コピー)

最近提案されているが, これらも同じ問題点を持っている．
これまで, この問題に理論的な解決が存在しなかった理由は, n グラム分布を階層的に生成する確率モデ
ルが一般的でなかったためだと考えられる．☆☆ しかし, 最近 10)，11) により, 階層 Pitman-Yor 過程とよばれるノンパラメトリックな確率過程によって, 高精
度にスムージングされた n グラム分布を 0-gram→1-gram→2-gram→ · · · とベイズ統計の枠組から階層的に生成および推定できることが明らかになった．
そこで本論文では, この階層 Pitman-Yor 過程による n グラムモデルを拡張し, データ中の各単語が生成された n グラム長を隠れ変数とみなしてベイズ推定を行うことで, 文脈により様々にオーダーの異なる可変長 n グラムの生成モデルを提案する．この方法により,n グラムモデルの n を指定せず, 原理的には無限長とすることができ, 従来不可能だった高次 n グラムの推定が可能となる．また, 言語モデルの副産物として, 上で述べた可変長の「句」を教師なし学習の枠組から,確率的に推定することができる．

図 1 階層的 CRP の Suﬃx Tree 上の表現．客一人一人が, モデ
ル上のカウントを表している．
Fig. 1 Suﬃx tree representation of a hierarchical Chinese
Restaurant Process. Each customer corresponds toa count in the model.

高精度な階層的生成モデルであり☆☆☆ , 後に説明するように, 現在最高性能といわれる言語モデルの Kneser-

Ney スムージング12) は, この確率過程の近似となっている．
階層 Pitman-Yor 過程は, 確率論の分野では 2-パラ
メータポアソン=ディリクレ過程13) とよばれている

Pitman-Yor 過程を階層化したものであり, 階層ディ
リクレ過程14) の拡張と考えることができるが, ここでは直接測度論に基づく式ではなく, それと等価な階層的な CRP (中華料理店過程)15) を使って, 直感的に説明する．
例として, トライグラムの言語モデルを考えよう．これは図 1 のように, 深さ 2 の Prediction Suﬃx Tree

(予測接尾辞木)25) で表すことができる．いま, 文脈‘she will’ に続いて ‘sing’ を予測したいとき, この木を以下ではまず 2 節で, 階層 Pitman-Yor 過程によるユニグラムに対応する根 ² から, ² → will → she の順

n グラム言語モデルについて説明し, 3 節で Suﬃx Treeに枝をたどり, 到達した ‘she will’ に対応するノード

上に確率過程を考えることにより, これを可変長に拡の持つカウント分布を用いて, p (sing | she will) を計

張する．4 節で LDA を用いたそのトピック適応化に算する．予測接尾辞木はコーパス上の接尾辞に対するついて述べ, 5 節で実験結果を示す．6 節で考察および木であるが, 通常の接尾辞木 (² → she → will) と異な関連研究について述べ, 7 節で全体のまとめと将来のり, シンボルを後ろからたどるために, ラベルの順番が展望についてふれる．

逆になっていることに注意されたい．簡単のため, 以
下では Prediction Suﬃx Tree のことをすべて Suﬃx

2. 階層 Pitman-Yor 過程と n-gram 言語モデルTree と表記する．

階層 Pitman-Yor 過程による n グラム言語モデル

木から始め, 学習データのトライグラムについて, そ(HPYLM)10)11) は, 最近提案された n グラム分布のの 1 つ 1 つのカウント ( CRP では, 可算無限個のテー

HPYLM の学習を行う際には, 根だけの初期状態の

ブル=語彙数を持つ中華料理店のメタファーから, こ☆

頻度による一様なカットオフは, 性能がきわめて悪いことが示されている4) ．
☆☆
先行研究として, n グラムの事前分布に階層的なベータ分布を考える研究8) や, 階層ディリクレ過程を用いる研究9) があったが, これらによって得られる加法的なスムージングは 10) で示されているように, 他の高精度なスムージング法に比べて精度が低いという実用上の問題を持っていた．

のカウントを「客」と呼ぶ) を図 1 のように, 深さ 2☆☆☆

これまでの n グラムの確率モデルは各文脈での頻度をディスカウントした後, 和を 1 に正規化して確率とするものであり, その頻度の由来を問うものではなかった．また, 各 1-グラム, 2-グラ
ム,· · · のカウントとその確率は, 基本的に独立に計算されていた．

Vol. 0No. 0

階層 Pitman-Yor 過程に基づく可変長 n-gram 言語モデルの対応するノードに, 必要に応じて新しくノードを作

3

1 − qii

りながら追加してゆく．
1 − qj

ここで一般には, どのノードにも全ての種類の単語のカウントがあるわけではない．そこで, 客をノードに

k

1 − qk追加する時, ある確率で☆ その客のコピー (代理客) がj

親ノードに客として送られる．たとえば, ノード ‘shewill’ に客 ‘like’ がいなくても, 姉妹ノード ‘he will’ に‘like’ がいれば, そのコピーが共通の親ノード ‘will’ に送られているため, 確率 p (like|she will) は 3-gram 確
率 p (like|she will) (これは 0) と, 親ノードの持つ 2-gram 確率 p (like|will) を適切に補間して計算される．
この過程は再帰的に行われ, 親ノードに客 ‘like’ が追加

図 2 Suﬃx Tree に客を追加する確率過程．(1−qi ) はノード iの持つ「通過確率」を表す．
Fig. 2 A stochastic process to add a customer to the suﬃx
tree. (1 − qi ) means a “penetration probability” ofnode i.

の確率過程のヒューリスティックな近似であることがわかる．

される際にもコピーがその親ノードに送られ, 2-gram

さて, ここでの問題は, 図 1 において客がすべて, 深

確率は 1-gram 確率との補間で計算されるため☆☆ , 直
接親ノードにない語についても, 必ず確率を求めるこさ (n−1) のノードに到着するとしていることである．
実際には, 自然言語の持つ Suﬃx Tree はある所で浅とができる．
結果として HPYLM では, 文脈 h = wt−n · · · wt−1に続く単語 w の確率は,く, ある所は非常に深い, 図 2 のような形をしており,
言語はさまざまに長さの違う n グラム文脈から生成されていると考えられる．それでは, 自然言語の持つこc(w|h)−d·thw
θ+d·th·+p(w|h0 )p(w|h) =θ+c(h)
θ+c(h)(1)のような木をどのようにして推定すればよいのだろうか．

として, 再帰的に計算される．

3. 可変長階層 Pitman-Yor 過程

ここで c(w|h) はノード h での w のカウント, c(h) =

P

w

0

c(w|h) はその総和であり, h = wt−n+1 · · · wt−1

3.1 Suﬃx Tree 上の確率過程

は 1 つオーダーを落とした文脈である．

thw は w が p(w|h) からではなく, 親ノード p(w|h0 )から生成されたと推定された回数であり,

P

t =
w hw

th· と書いた．d, θ は Pitman-Yor 過程のパラメータであり, Suﬃx Tree 上のすべての客の分布から, それ

そこで我々は, Suﬃx Tree の各ノード i に, 木を根からたどる時にそこで止まる確率 qi (すなわち, (1 − qi )はノード i の「通過確率」を表す) があると考え, 各 qi
は [0, 1] 上の最も自然な確率分布として, 共通のベー
タ事前分布

qi ∼ Be(α, β)

ぞれベータ事後分布, ガンマ事後分布によって推定できる10) ．これらの統計量はすべて, 末端ノードに追加(2)から生成されていると仮定する．

されるカウント (客) から, 再帰的に親ノードに送られここで, Be(α, β) = Γ(α+β)/(Γ(α)+Γ(β))·q α−1 (1−る代理客の数とその配置に依存するが, それらは相互β−1

依存関係にあるため, 推定には MCMC 法16) の一種であるギブスサンプリングを用いる．ランダムに選んだ客をその代理客を含めていったん削除し, 新しく追加し直してその代理客の配置を再サンプリングすることを繰り返すことで, 代理客の配置が真の分布からのq)は二項確率 q の確率分布であるベータ分布の確率密度関数であり, 期待値は E[q] = α/(α+β) である．図 3 に, ハイパーパラメータ (α, β) の違いによるベータ分布の例をいくつか示す．
文脈 h = wt−∞ · · · wt−2 wt−1 に続いて単語 wt が観測されたとき, 我々は Suﬃx Tree を根 ² から始めて,サンプルに収束する．図 4 を参照されたい．
式 (1) は, カウント c(w|h) をディスカウントした分

4
3.5

布を 1 つ低いオーダーの分布と補間した確率になっているが, thw ≡ 1 とすると, この式は Kneser-Ney ス

3
2.5(0.5,0.5): Jeffrey’s(1,1): Uniform
(4,1)
(2,4)

2
1.5

ムージングと一致し, Kneser-Ney スムージングはこ

1
0.5

☆

(1) 式において, 単語が親ノードである第二項から生成されたと判断された場合．
☆☆
1-gram 確率はさらに, 0-gram 確率 (全ての確率が 1/V ) と補間される．

0
0

0.2

0.4

0.6

0.8

1

図 3 ベータ分布の例とハイパーパラメータ．
Fig. 3 Examples of Beta distributions with diﬀerent
hyperparameters.

情報処理学会論文誌

4

2007

² → wt−1 → wt−2 → · · · の順にノードをたどって降り

とおくと, qi の期待値は, ベータ事後分布の期待値とていくが, この時, 必ず深さ (n−1) で止まるのではな

してE[qi ] =く, このパス上の qi をそれぞれ q0 , q1 , q2 , . . . として,確率p(n = l|h) = ql

l−1Y

(1 − qi )

(3)

ai +α
ai +bi +α+β(6)と推定される．また, 式 (5) はベイズの定理からに従って深さ l で停止し, そこに客を追加する (図 2)．

p(nt |w, n−t , s−t )∝ p(wt |w−t , n, s−t ) p(nt |w−t , n−t , s−t )

i=0

(7)

この式からわかるように, 非常に深いノードであっと展開できるが, この第一項は n グラムオーダーが ntても, そのパスに沿った qi が小さければ (すなわち,と決まったときの wt の n グラム確率であり, 式 (1) か「通過確率」が高ければ) 深い n グラムが使われ, 逆にら求められる．第二項は, この文脈で深さ nt のノード

浅いノードでも, qi が大きければ (「通過確率」が低に到達する事前確率であり, 式 (3) および式 (6) から,ければ) そこで止まる確率が大きくなる．式 (3) より,

p(nt = l|w−t , n−t , s−t )深さ n のノードに到達する確率は n に従っておおよそ指数的に減少するが, その度合は木の枝によって異=なり, 高頻度の長い系列に対応する深いノードを許す

l−1
Y
al +α
bi +β
al +bl +α+β
ai +bi +α+β

(8)

i=0

のように計算することができる．

ことのできるモデルとなっている．☆

これらの確率を用いて, 各単語の持つ隠れた n グラ

3.2 可変長ベイズ n-gram 言語モデル
もちろん, われわれは言語の Suﬃx Tree のノード

ムオーダーをサンプリングする, 可変長階層 Pitman-が持つ真の qi の値は知らない．それでは, どうやって

Yor 言語モデル (VPYLM) のギブスサンプラを構成

qi を推定すればよいだろうか．

することができる (図 4)．

ここで, 上の可変長生成モデルでは, データ w =このアルゴリズムは HPYLM のギブスサンプリンw1 w2 · · · wT について, それぞれの単語が生成されたグの拡張であり, 単語 wt に対応して Suﬃx Tree の

隠れた n グラム長 n = n1 n2 · · · nT が存在しているとorder[t] の深さにいる客を一人, 根からノードをたどっ仮定していることに注意したい．したがって, われわて削除し, ai または bi をパスに沿って 1 ずつ減らす．

れのモデルでは, データ w の確率は新しい n グラムオーダーをサンプリングした後, 客をp(w) =

XXnp(w, n, s)(4)

新しい深さに追加し直して ai または bi を 1 ずつ増やし, この深さを order[t] に記録する．以上を繰り返す．

sと表すことができる．

☆☆

ここで s = s1 s2 · · · sT であり, st はそれぞれ, 単語 wt から送られた代理客の配置を表す隠れ変数であorder[t] をサンプリングせず, 常に定数 (n−1) である場合が, n グラムの HPYLM のギブスサンプリン
グに相当している．

る10) ．この n, s は, 代理客の配置を確率的に最適化す

式 (7) から nt をサンプリングする際, 計算量的なる, HPYLM のギブスサンプリングを拡張することで問題から, 実際にはある最大値 nmax を設定してその推定することができる．

中でサンプリングを行うか, または nt の事前確率 (8)具体的には, 単語 wt の持つ隠れた n グラムオーダー

nt を,

nt ∼ p(nt |w, n−t , s−t )(5)のようにサンプリングして更新していく．(st も, このがある小さな値 ² 以下になるまで計算を行う．このとき, n グラムモデルにおいて ‘n’ は必要なくなり, われ
われは原理的に, n をベイズ的に積分消去した「∞-グ
ラム言語モデル」を得ることができる．

後同時にサンプリングを行う．) ここで n−t , s−t は

3.3 予測と文脈長確率分布

それぞれ, n, s から nt , st を除いたベクトルである．

予測の際にも, われわれは従来のように n グラム長式 (5) から nt をサンプリングする際, われわれは他を固定していないため, n を隠れ変数とみなして, 文の客 (単語) が Suﬃx Tree をたどった深さ n−t を全脈 h = w−∞ · · · w−2 w−1 に対してて知っていることに注意されたい．したがって, 他のp(w|h) =客がノード i で止まった回数を ai , 通過した回数を bi☆

式 (2)(3) の形からわかるように, これは Suﬃx Tree 上で定義された, Beta two-parameter process の Stick-breaking
process 15) である．

=

☆☆

P
p(w, n|h)Pnnp(w|n, h)p(n|h)

(9)
(10)

このとき, 同時に親ノードの代理客が再帰的に, 確率的に削除/追加される．(st のサンプリングに相当する．)

Vol. 0No. 0

階層 Pitman-Yor 過程に基づく可変長 n-gram 言語モデル

5

struct ngram {ngram *parent;
splay *children;
splay *words;
int stop;
int through;int ncounts;
int ntables;
int id;};/* n-gram node *//* parent node *//* = (ngram **) *//* = (restaurant **) *//* ah *//* bh *//* c(h) *//* th· *//* word id */For j = 1 · · · N {For t = randperm(1 · · · T ) {if (j > 1) thenremove customer (order[t], wt , w1:t−1 );order[t] = add customer (wt , w1:t−1 );}}図 4 VPYLM のギブスサンプラ．
Fig. 4 The Gibbs sampler of VPYLM.

図 5 n グラムノードのデータ構造．
Fig. 5 Data structure of a n-gram node.

のように予測を行う．ここで第二項は文脈 h の持つn グラム文脈長分布であり, 式 (8) で与えられる．第一θd = (θ1 , θ2 , . . . , θM ) があり, θ がディリクレ事前

項はオーダーを n とした HPYLM の予測確率であり,分布

Γ(M γ) Y γ−1
θt
Γ(γ)M
M

θ ∼ Dir(γ) =(1) 式で求められるが, この確率はすでに Kneser-Ney

(11)

t=1

スムージングと同等に階層的にスムージングされていることに注意されたい．すなわち, VPYLM の予測確率から生成されていると仮定する．簡単のため, 上ではは, HPYLM の n グラム確率をさらに n = 0, 1, · · · , ∞ディリクレ分布のハイパーパラメータは全て同じ値 γの文脈事後分布で混合したものになっている．実際にとした．このとき, 文書 d = w1 w2 · · · wN の各単語

は (10) をさらに, 訓練データ w からの n, s の N 個

は, 次のようにして生成される．

の Gibbs 事後サンプルで平均化して予測を行う．☆

(1)

θd ∼ Dir(γ) をサンプル．

(2)

For n = 1 . . . N ,

3.4 実

装

a. t ∼ Mult(θd ) をサンプル．

ギブスサンプリングの際, Suﬃx Tree 上で数千から

b. wn ∼ p(w|t) をサンプル．

数万にのぼることがある子ノードをたどる操作を高速化するため, われわれは 5) と同様に, 子ノードの管理

ここで, トピック言語モデル p(w|t) として 19) ではを使用した．スプレー木は O(log n)

ユニグラム分布が使われているが, LDA は混合モデル

で子ノードを探索可能な二分順序木である．アクセスであるから, これは任意の分布に置き換えることがでの際に木を自己組織的に最適化することで, 高頻度な

き, ここではトピックごとの VPYLM とすることがでアイテムを高速に探索できるため, 自然言語のようにきる．しかし予備実験の結果, トピック毎の VPYLM

18)にスプレー木Power Law を持つ系列での動的なデータ構造としてを混合する方法では, トピックを考慮しない時に比べ特に適している．

て予測精度が悪化することがわかった．

われわれはこのスプレー木を子ノードだけでなく,

この理由は, LDA のギブスサンプリングによりデー

各ノードの持つ予測単語☆☆ の管理にも用いた．図 5

タを分割し, トピック別の n グラム言語モデルを構築に, Suﬃx Tree の各 n グラムノードに使用したデータ

すると, n グラムのスパース性がより深刻になるため構造を示す．

だと考えられる．トピックを動的に推定することによる精度上昇より, 選択されたトピック言語モデルのカ4. 可変長ベイズ n-gram 言語モデルのトピッ
ク適応
可変長 n グラムモデルについて, そのベイズ生成モデルが得られたので, 次にそのトピック適応化を自然に考えることができる．

バレージ不足による精度悪化の方が問題となるからである．

4.2 ギブスサンプリングによるモデル推定
そこでわれわれは, VPYLM において, データの多いユニグラム分布のみを混合分布 (混合 Pitman-Yor

4.1 Latent Dirichlet Allocation (LDA)測度) とすることとした．LDA によって決まるトピッ

このためのモデルとして, 我々は LDA19) を使用し

ク分布 θd に従い, 単語ごとに異なるユニグラム分布

た．LDA では, 各文書に, 隠れたトピック混合分布を用いた可変長 n グラム分布から単語が生成される．
このとき, 階層 Pitman-Yor 過程によって生成され☆

これは, Gibbs サンプリングが事後分布からの正確なサンプリン
グであり, 事後確率最大化を行うものではないからである．ディ
リクレ過程混合モデルに対して最近提案されたモデル探索法17)は, この意味で興味深い．
☆☆
CRP においては, 「レストラン」と呼ばれている．

る n グラムカウントは, テーブル☆☆☆ ごとに生成され☆☆☆

各 n グラムノード h でのカウントは, 単語ごとのテーブルの一つに加算される．このテーブルは, 単語 w ごとに thw 個存在する．

情報処理学会論文誌

6

たユニグラム分布が異なるため, ギブスサンプリングの際, カウントがどのテーブルに追加され, その親テー
ブルは何かを明示的に追跡する必要がある．
この情報を用いて, VPYLM の LDA 化 (VPYLDA)のギブスサンプリングは, 図 6 のように行うことがで

2007

表1

英語および日本語のコーパスでのテストセットパープレキシ
ティとモデルの持つノード数．N/A はメモリオーバーフロー
を表す．
Table 1 Test-set perplexities with the number of nodes in
the model in English and Japanese corpora. N/Ameans a memory overﬂow.

(a) 英語 (NAB コーパス)

きる．ここで draw topic は, 単語 wt がトピック k に属する事後確率p(k|wt , w1:t−1 ) ∝ p(wt |w1:t−1 , k) · p(t|θd )(12)∝ p(wt |w1:t−1 , k) · (nd−t,k +γ)
(13)

n
3
5
7
8
∞

HPYLM
113.60101.08
N/A
N/A
—

n
3
5
7
8
∞

HPYLM
78.06
68.36
N/A
N/A
—

VPYLM
113.74101.69100.68100.58117.65

Nodes(H)1,417K
12,699K
N/A
N/A—

Nodes(V)1,344K
7,466K
10,182K
10,434K
10,392K(b) 日本語 (毎日新聞コーパス)から k をサンプルする関数であるが, 各単語のもつ n グ
ラムオーダー order[t] (テーブル table[t] が Suﬃx Treeの中で存在する深さによって, 陰に表現されている) に加え, その属するトピック topic[t] を同時に隠れ変数として持ち, サンプリングを行う点が VPYLM のギブ

VPYLM
78.22
69.35
68.63
68.60
80.38

Nodes(H)1,341K
12,140K
N/A
N/A—

Nodes(V)1,243K
6,705K
9,134K
9,490K
9,561K

スサンプリングと異なっている．上式で, p(w|h, k) はユニグラム分布 k を用いた VPYLM の予測確率 (10),

総語彙数は 26,497 語である．日本語については毎日

nd−t,k は文書 d 中でトピック k に割り当てられた単語

新聞 2000 年度のテキスト (約 150 万文) からランダ

数 (wt を除く) を表す．

ムに選んだ 520,000 文, 10,079,410 語を訓練データ,

10,000 文を評価データとした．MeCab 23) で分かち

5. 実

験

5.1 VPYLM on Text Corpora
英語および日本語の標準的な大規模コーパスを用いて実験を行った．

☆

書きを行い, 頻度 10 未満の語をまとめて, 総語彙は32,783 語となった．
5.1.0.2 学 習 設 定
予備実験の結果と計算量的制約から, HPYLM,

5.1.0.1 デ ー タ

VPYLM のそれぞれのモデルについて N = 200 回のギ

英語については, 21)，22) 等で使われている NAB

ブスサンプリングを行い, さらに 50 回の事後サンプル(North American Business News) コーパスの WSJを用いて評価を行った．Suﬃx Tree の形を決めるベーセットよりランダムに選択した 409,246 文, 10,007,108

タ事前分布のハイパーパラメータは (α, β) = (4, 1) と語を訓練データ, さらに 10,000 文を評価データとししたが, これはより深い木が得られる (1, 1) の一様分た．単語はすべて小文字とし, ノイズの可能性の高い,布を用いた場合等とほとんど性能差がなかったためで全体で頻度 10 未満の単語は特別な未知語とみなした．

ある．(α, β) の値による性能差とその最適化について

For j = 1 · · · N {For t = randperm(1 · · · T ) {d = document(wt );k = topic[t];if (j > 1) thenremove customer (table[t]);k = draw topic (wt ,w1:t−1 ,d);table[t] = add customer (wt ,w1:t−1 ,k);topic[t] = k;}}
図 6 VPYLDA のギブスサンプラ．
Fig. 6 The Gibbs sampler of VPYLDA.
☆

中国語についても, Sinica バランスドコーパス20) を用いて漢字単位の言語モデルを構築して実験を行い, 同様の結果を確認している．(n = 5 のときパープレキシティ43.39.)

は, 6 節を参照されたい．実験はすべて Xeon 3.2GHz,
メモリ 4GB の Linux 上で行った．

5.1.0.3 結果

表 1 に, HPYLM と VPYLM のパープレキシティ
をモデル中の n グラムノード数とともに示す．モデル
次数 n は前者では固定, 後者では最大値 nmax を意味する．☆☆
この結果から, VPYLM は HPYLM とほぼ同等の性能を40 %以上少ないノード数で達成し, HPYLM では推定できない n = 7, 8 のような高次 n グラムにつ☆☆

表 1 には示されていないが, Modiﬁed Kneser-Ney スムー
ジングを用いた SRILM 24) による英語のパープレキシティ
は, n = 3, 5, 7, 8 についてそれぞれ 118.91, 107.99, 107.24,
107.21 であり, HPYLM および VPYLM はこれより優れた性能を達成している．

Vol. 0

階層 Pitman-Yor 過程に基づく可変長 n-gram 言語モデル

No. 0

いても, 必要なもののみを選択的にモデルに加えることで推定が可能であり, より高い性能を持つことがわ
かる．
また, 同じ (最大) オーダーnの場合でも, VPYLM
は HPYLM より 20%程度学習が高速である．これは,VPYLM において n グラムオーダーをサンプリングする計算コストよりも, 不必要に深いノードを追加しな

p(w, n)0.9784
0.9726
0.9556
0.95120.93940.90260.8896
0.88310.86960.7566
0.7134
0.6617:

7

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

いことによる計算量の削減が大きいからだと考えられる．図 7 に, 8-グラム VPYLM において推定された

n グラムオーダーの, データ全体での分布を示す．文脈長を長くするメリットと, 深いノードに到達するコストの間で適切なトレードオフが行われ, n = 3, 4 程度
をピークに指数的な減衰が起きていることがわかる．

5.2 Suﬃx Tree と確率的句提 案法に お いて, 式 (9) の p(w, n|h) は h =w−∞ · · · w−2 w−1 の中で最後の n 語である w−n · · · w−1を文脈として単語 w が生成された確率であり, すなわ
ち, w−n · · · w−1 w が「句」をなす確率と考えることができる．たとえば, “america” が文脈 “the unitedstates of” から生成されたとき, “the united states ofamerica” は句をなし, これに (必ずしも, 経験確率のように長さに従って減衰しない) 確率を割り当てることができる．

図8

NAB コーパスで学習した 8 グラム VPYLM の Suﬃx
Tree から得られた, 確率的フレーズ．
Fig. 8 Stochastic phrases computed from the suﬃx tree of
8-gram VPYLM that is trained on the NAB corpus.

5.3 VPYLDA on 20news-18828
5.3.0.4 データと学習設定
可変長 n グラム LDA(VPYLDA) の評価データとして, われわれは 20news-18828 データセット26) を用いた．このうち, 20 個のニュースグループを同等にカバーするように 4,000 文書を訓練データ, 400 文書を評価データとした．
訓練データは NAB コーパスと同様に前処理し,801,580 語, 語彙数 10,477 語のデータとなった．N =250 回のギブスサンプリングを行った後の単一サンプ
ルを用い, 文脈 h = w1 · · · wn−1 での単語 wn の予測確率を, 順に以下のように求めた．

これは木の根からユニグラムで単語 w を生成する代
わりに, 子ノードを確率的に w−1 → w−2 → · · · → w−np(wn |h) =することで, すべての句とその確率を効率的に計算することができる．図 8 に, 8-グラム VPYLM から得られた「確率的句」の例を, 上の確率でソートして示す．
# of occurrences

3.5×106(n = 1 . . . N )(14)

ここで p(wn |h, t) はトピック t のユニグラムを用い­®

た可変長 n グラムの予測確率 (10) であり, p(t|h) は
仮想的な文書と考えた h のもつトピック t の事後期待値である．言語モデルは固定であるから, 高速化のた
ム19) を用いた．

2.5×106
6

5.3.0.5 実 験 結 果

2.0×10

1.5×106

表 2 に, ト ピック 混 合 数 M を 変 え た と き の

1.0×106

VPYLDA のテストセットパープレキシティを示す．

5

5.0×10

0

1

2

3

4

5

6

7

n
図7

®

め, この計算には LDA の変分ベイズ EM アルゴリズ

3.0×106

0.0×100­p(wn |h, t) p(t|h)

tとたどった後で w を出力し, 句 w−n · · · w−1 w が生成されたと考えてもよく, Suﬃx Tree を深さ優先で探索X

8 グラム VPYLM で推定されたnグラム文脈長のデータ全体での分布．n = 0 がユニグラム, n = 1 がバイグラム,. . . である．実際にはさらに式 (1) により, 低次の n グラムと階層的にスムージングされることに注意．
Fig. 7 Global n-gram context length distribution inferred
by a 8-gram VPYLM. n = 0 is a unigram, n = 1 isa bigram, and so on. Each n-gram is further interpolated by lower-order n-grams recursively throughthe equation (1).

M = 1 のとき, これは VPYLM と等価であり, 最下段に示した．
予測は改善しているが, その差はわずかであることがわかる．学習されたモデルを観察したところ, この理由は, 高頻度の単語が各トピックユニグラムに均等に分配されないためであることがわかった．図 1 の階
層的 CRP において, トピック t をもつ客のコピーが親ノードに送られるのは, その客が現在のノードではな
く親ノードから生成されたと確率的に判断された場合であるが, 高頻度の語は多くのノードで既に存在する

情報処理学会論文誌

8

2007

ため, カウントが再利用されて単に 1 増やされ, トピッ

PPL
136
134
132
130
128
126
124
0.1

ク別ユニグラムまで確率的に到達しないことが多い．
トピックはユニグラムに限られるものではなく, バ
イグラムやトライグラム以上にも別の混合数で存在す
る☆ ことを考えると, このような階層的な混合モデルの推定には, また新しい方法を必要とすると思われる．

6. 考察および関連研究

134
132
130
128
126
124
122

0.5 1
α

2

0.5
5 10

1

2

5

10

β

0.1

図9

VPYLM のハイパーパラメータ (α, β) とテストセットパー
プレキシティの関係．
Fig. 9 Relationship between the VPYLM
hyperparameters (α, β) and test-set perplexities.

本 研 究 は, デ ー タ 圧 縮 に お け る Context Tree

Weighting 法27) を自然言語に応用した, Pereira らの興味深い研究5) をその動機としている．彼らの手法も様々な深さの木の事後確率を考え, それらを混合するものであるが, n グラム分布を階層的に推定するモデルは存在しなかったため, 最終的に各ノードでのWitten-Bell スムージングと頻度によるカットオフに頼っており, 性能面でのアドバンテージがないという結果になっていた．これに対し提案手法では, 彼らの手法で定数だった木の生成確率をベイズ化し, 階層

エリスは打笑ひ玉へ。産れん子の生れむることの我を力になし果てつ。
「カイゼルホオフ」へ通ふことの少きをもかくは心の奥に凝り固まりて、一は親族なる某省の官長き猶こゝまで導きつゞきだに事なく済みたらま
しかば、何事をか叙すべき。わが心はかの合歓といふ
木の葉に似たり。余との間にて、余がねの額に印せし面に、鬢の毛の解けてかゝりて、灼くが如く、政治家になるべき。わが心はこの時戸口に入りてこそ紅粉をも粧ひ、折に触れては、故らに知りて、大臣に聞え上げし一諾を知り、言葉にて、その為し難きに、若し真なりせば、詩に詠じ歌によめる後は心地すが／＼しく
もなりなむ。

Pitman-Yor 過程でスムージングされた n グラムをさ図 10『舞姫』からランダムに生成したテキスト．
VPYLM, n = 5.
Fig. 10 Random walk generation from the language
model trained on “Maihime.”

らに混合し, 生成モデルの立場からカウント毎に確率的なプルーニングを行うという点で, その後継となっていると考えることができる．

後分布から最適化することもできる．28) の Newton「無限長」の文脈を表現する方法としては, データ圧
縮で用いられる PPM*法が知られているが, PPM*はデータに存在するすべての接尾辞を記憶し, それらの中で文脈に最長一致するノードを用いて, Witten-Bell
スムージングとバックオフにより確率を求めるものである．これに対し, 提案法は信頼性の低い最長一致を用いるのではなく, ノードを予測性能によってベイズ
的に重みづけ, 確率的なプルーニングを行うことで, 指数的に増加する接尾辞を全て記憶することを避け, 空間計算量を大きく効率化している．

5 節の実験では, Suﬃx Tree の形を決める事前分
布として (α, β) = (4, 1) を用いたが, このパラメータは経験ベイズ法により, (6) 式で各 qi がもつベータ事
表 2 20news-18828 データセットにおける VPYLDA のテスト
セットパープレキシティ．
Table 2 VPYLDA test-set perplexities on the 20news18828 dataset.

☆

Model

PPL

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

104.69103.57103.28105.30

たとえば, ‘mixture of Gaussians’ と ‘mixture of ﬂour’ の出現は, 文脈に応じてほぼ排他的だと考えられる．

法を用いると, 1M 語の NAB コーパスのサブセットの場合, この値は各繰り返しですべて (0.85, 0.57) に収束した．しかしながら, VPY 言語モデルの性能はハイパーパラメータにはあまり依存しない．図 9 に,(α, β) ∈ (0.1 ∼ 10)×(0.1 ∼ 10) の範囲で変えたときのパープレキシティを示す．β À α となる場合を除いて, 性能はほぼ一定であることがわかる．
最後に, 図 10 に森鴎外『舞姫』で学習した 5-gram

VPYLM から, ランダムに生成した文の例を示す．☆☆
従来のように文脈と最長一致するモデルのノードを使用すると, オーバーフィットのために n = 5 では
ほぼ学習データがそのまま再現されてしまうが, ここでは式 (8) にしたがって後ろから確率的に文脈をたどり, 止まったノードから単語を生成することで, 学習
データの特徴をとらえたテキストが生成されていることがわかる．モデルには確率的句として, 「エリ ス」(0.856), 「嗚呼 、」(0.803), 「似 たり 。」(0.398),「二 人 の 間」(0.199) などがあり, 図 10 のテキストを生んでいた．

☆☆

生成の際にバックオフは行っていないため, 正確なサンプリングとは少し異なる．

Vol.0

階層 Pitman-Yor 過程に基づく可変長 n-gram 言語モデル

No.0

7. まとめと展望
本論文では, 最近提案された n グラム分布に対する高精度なノンパラメトリック確率過程である階層

Pitman-Yor 過程をさらに拡張することで, 単語の生まれた n グラム文脈長を適切に推定する可変長 n グラ
ム言語モデルを示した．無限の深さをもつ確率的なSuﬃx Tree を考え, それをベイズ推定することで, これまで固定だった n を原理的に不要とし, 可変長とすることができる．
提案法は最大オーダーの従来法と同等の性能を, より少ない空間的および時間的計算量で達成し, 従来不可能だった高次 n グラムの推定も可能にする．また,言語モデルの副産物として, 学習された Suﬃx Tree から特徴的な系列を確率つきで取り出せることを明らかにした．
また, 本研究の手法は言語モデルに限られることな
く, 可変長マルコフモデルを実現する一般的なベイズ的方法であることに注意されたい．プルーニングに基づく従来の “可変長モデル” と異なり, 提案手法は可変長時系列の完全な生成モデルとなっている．
本研究では Suﬃx Tree の事前分布として, 柔軟だが単純な共通のベータ分布を用いたが, 29) にみられるような事前分布を考えることで, モデルをより精密にすることができると考えている．また, トピック適
応化についても, 階層的な混合モデルのよりよい推定法を考えていきたい．
謝辞 本研究は独立行政法人 情報通信研究機構の研究委託「大規模コーパスベース音声対話翻訳技術の研究開発」により実施したものである．

参 考 文 献1) Shannon, C. E.: A mathematical theory ofcommunication, Bell System Technical Journal, Vol.27, pp.379–423, 623–656 (1948).
2) 工藤拓：形態素周辺確率を用いた分かち書きの一般化とその応用，言語処理学会全国大会論文集
NLP-2005 (2005).
3) Siu, M. and Ostendorf, M.: Variable n-gramsand extensions for conversational speech language modeling, IEEE Trans. on Speech andAudio Processing, Vol.8, pp.63–75 (2000).
4) Stolcke, A.: Entropy-based Pruning of Backoﬀ
Language Models, Proc. of DARPA Broadcast
News Transcription and Understanding Workshop, pp.270–274 (1998).
5) Pereira, F., Singer, Y. and Tishby, N.: Beyond
Word N-grams, Proc. of the Third Workshop on

9

Very Large Corpora, pp.95–106 (1995).
6) Leonardi, F.G.: A generalization of the PST
algorithm: modeling the sparse nature of protein sequences, Bioinformatics, Vol.22, No.11,
pp.1302–1307 (2006).
7) Buhlmann, P. and Wyner, A. J.: Variable
Length Markov Chains, The Annals of Statistics, Vol.27, No.2, pp.480–513 (1999).
8) Kawabata, T. and Tamoto, M.: Back-oﬀ
Method for N-gram Smoothing based on Binomial Posteriori Distribution, ICASSP-96, Vol.I,
pp.192–195 (1996).
9) Cowans, P.: Probabilistic Document Modelling, PhD Thesis, University of Cambridge(2006). http://www.inference.phy.cam.ac.uk/
pjc51/thesis/index.html.
10) Teh, Y. W.: A Bayesian Interpretation ofInterpolated Kneser-Ney, Technical Report
TRA2/06, School of Computing, NUS (2006).
11) Teh, Y.W.: A Hierarchical Bayesian Language
Model based on Pitman-Yor Processes, Proc. of
COLING/ACL 2006, pp.985–992 (2006).
12) Kneser, R. and Ney, H.: Improved backing-oﬀ
for m-gram language modeling, Proceedings of
ICASSP, Vol.1, pp.181–184 (1995).
13) Pitman, J. and Yor, M.: The Two-Parameter
Poisson-Dirichlet Distribution Derived from a
Stable Subordinator, Annals of Probability,
Vol.25, No.2, pp.855–900 (1997).
14) Teh, Y.W., Jordan, M.I., Beal, M.J. and Blei,
D.M.: Hierarchical Dirichlet Processes, Technical Report 653, Department of Statistics, University of California at Berkeley (2004).
15) Ghahramani, Z.: Non-parametric Bayesian
Methods, UAI 2005 Tutorial (2005).
http://learning.eng.cam.ac.uk/zoubin/talks/uai05tutorial-b.pdf.
16) Gilks, W.R., Richardson, S. and Spiegelhalter,
D.J.: Markov Chain Monte Carlo in Practice,
Chapman & Hall / CRC (1996).
17) Daumé III, H.: Fast search for Dirichlet process mixture models, AISTATS 2007 (2007).
18) Sleator, D. and Tarjan, R.: Self-Adjusting Binary Search Trees, JACM, Vol. 32, No. 3, pp.
652–686 (1985).
19) Blei, D.M., Ng, A.Y. and Jordan, M.I.: Latent Dirichlet Allocation, Journal of Machine
Learning Research, Vol.3, pp.993–1022 (2003).
20) Huang, C.-R. and Chen, K.-j.: A Chinese Corpus for Linguistics Research, Proc. of COLING
1992, pp.1214–1217 (1992).
21) Chen, S. F. and Goodman, J.: An Empirical Study of Smoothing Techniques for Language Modeling, Proc. of ACL 1996, pp.310–

10

情報処理学会論文誌

318 (1996).
22) Goodman, J.T.: A Bit of Progress in Language
Modeling, Extended Version, Technical Report
MSR–TR–2001–72, Microsoft Research (2001).
23) Kudo, T.: MeCab: Yet Another Part-ofSpeech and Morphological Analyzer.
http://mecab.sourceforge.net/.
24) Stolcke, A.: SRILM – An Extensible Language
Modeling Toolkit, Proc. of ICSLP, Vol.2, pp.
901–904 (2002).
25) Ron, D., Singer, Y. and Tishby, N.: The Powerof Amnesia, Advances in Neural Information
Processing Systems, Vol.6, pp.176–183 (1994).
26) Lang, K.: Newsweeder: Learning to ﬁlter netnews, Proceedings of the Twelfth International
Conference on Machine Learning, pp.331–339(1995).
27) Willems, F., Shtarkov, Y. and Tjalkens, T.:
The Context-Tree Weighting Method: Basic
Properties, IEEE Trans. on Information Theory, Vol.41, pp.653–664 (1995).
28) Minka, T. P.: Estimating a Dirichlet distribution (2000). http://research.microsoft.com/
˜minka/papers/dirichlet/.
29) Pitman, J.: Combinatorial Stochastic Processes, Technical Report 621, Department of
Statistics, University of California, Berkeley(2002).

2007(平成 ? 年 ? 月 ? 日受付)
(平成 ? 年 ? 月 ? 日採録)
持橋 大地（正会員）

1973 年生．1998 年東京大学教養
学部基礎科学科第二卒業．2005 年奈
良先端科学技術大学院大学情報科学研究科博士後期課程修了．博士 (理学)．2003 年 ATR 音声言語コミュ
ニケーション研究所研修研究員/専任研究員．2007 年
より, NTT コミュニケーション科学基礎研究所 リサー
チアソシエイト．自然言語処理, 機械学習の研究に従事．
隅田英一郎（正会員）

1982 年電気通信大学大学院修士課
程修了. 1999 年京都大学工学博士.
現在,ATR 音声言語コミュニケーショ
ン研究所室長.

NiCT 知識創成コ

ミュニケーション研究センター研究
マネージャ, 神戸大学大学院自然科学研究科連携教授,

ATR-Langue 取締役副社長兼務. 機械翻訳, e ラーニ
ングの研究に従事. IEICE, NLP, ASJ, ACL, IEEEの会員, ACM/TSLP の Associate Editor.