Pitman-Yor 過程に基づく可変長 n-gram 言語モデル
持橋 大地 隅田 英一郎
ATR 音声言語コミュニケーション研究所 自然言語処理研究室 /独立行政法人 情報通信研究機構
daichi.mochihashi@atr.jp
eiichiro.sumita@atr.jp
概要
本論文では, n-gram 分布の階層的生成モデルである階層 Pitman-Yor 過程を拡張することで, 各単語の生まれた隠れた文脈を推定することのできるベイズ言語モデルを提案する. 無限の深さをもつ
Suﬃx Tree 上の確率過程を考えることにより, 句を確率的に発見し, 適切な文脈長を学習することができ, 従来不可能だった高次 n グラムの学習を可能にする. 本手法は言語モデルだけでなく, マ
ルコフモデル一般について, そのオーダーをデータから推定できる可変長生成モデルとなっている.
英語および日本語の標準的なコーパスでの実験により, 提案法の有効性を確認した.
キーワード: ノンパラメトリックベイズ, Pitman-Yor 過程, トピック適応, マルコフモデル, 言語モデル

Bayesian Variable Order n-gram Language Model
based on Pitman-Yor Processes
Daichi Mochihashi Eiichiro Sumita
ATR Spoken Language Communication Research Laboratories /National Institute of Communications Technology
daichi.mochihashi@atr.jp
eiichiro.sumita@atr.jp
Abstract
This paper proposes a variable order n-gram language model by extending a recently proposedmodel based on the hierarchical Pitman-Yor processes. Introducing a stochastic process on an
inﬁnite depth 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 of the proposedmodel. Our architecture is also applicable to general Markov models to estimate their variable
orders of generation.
Keywords: Nonparametric Bayes, Pitman-Yor process, Topic adaptation, Markov models,
Language Modeling

はじめに

しかしながら, 現実の言語データには “The UnitedStates of America” のように, トライグラムを超える
単語間のマルコフ過程によって文の確率を計算する n
長いフレーズや固有名詞が頻出する. これらをチャン
グラムモデルは, Shannon [1] の歴史的な論文で最初にクとして分類し, 一単語とみなす方法もあるが, これに導入されて以来, 自然言語処理の様々な場面に適用さは教師データが必要なために主観に依存する上, 慣用
れ, その有効性が示されてきた, 基礎的で重要な方法で句のような系列を全てカバーすることは難しいというある.
問題がある.1 特に, 日本語や中国語のように単語境界
n グラムモデルは, 直前の (n−1) 個の単語列を状態が曖昧な言語の場合, 品詞体系によっては短い助詞のとした (n−1) 次のマルコフモデルにより, 次の単語の連続などによる長い n グラムが頻出する可能性があり,
条件つき確率を計算していく. このとき, 状態数は単語「単語分割の粒度に依存しない言語モデル」が特に重要の総数を V とすると V n−1 のオーダーとなり, n を 1だと考えられる.
増やすと総パラメータ数は通常数万倍となり, 指数的また逆に, “longer than” のように短い n グラムで充に爆発する. このため, 様々なスムージング法を用い分な文法的関係も多いことを考えると, n を常に 3 など
た場合でも, 通常 n = 3 (トライグラム) から最大でも
1 何が句であるかには正解はなく, 確率的にしかとらえられない
n = 4, 5 程度が限界であり, それ以上の長い相関は実際 と考えている[2]. さらに, この区切りは固定ではなく, 一般に文脈上取り扱えないという問題があった.
にも依存する.

1

1

の固定値とするのではなく, 文脈に応じて必要なだけの長さを用いる「可変長 n グラム言語モデル」の意義
は, 言語学的にみても高いと考えられる.
しかしながら, これまで提案されてきた “可変長 n グ
ラムモデル” はいずれも, 実際には最大オーダーの n グ
ラムを最初に作り, それを枝刈りするか [3][4], または
頻度閾値でカットオフを行うもの [5] であった.2 この際の閾値や MDL などの基準はモデルとは別に外部から与えるものであり, さらに, 指数的に大きくなる最大モデルを事前に作る必要がある点で, 可変長モデルの構成意図と矛盾していた. 可変長マルコフモデルはバイオインフォマティクス [6] および統計学 [7] の分野でも最近提案されているが, これらも同じ問題点を持っている.
これまで, この問題に理論的な解決が存在しなかった理由は, n グラム分布を階層的に生成する確率モデ
ルが存在しなかったためだと考えられる. しかし, 最近[8][9] により, 階層 Pitman-Yor 過程とよばれるノンパ
ラメトリックな確率過程によって, 適切にスムージング
された n グラム分布を 0-gram→1-gram→2-gram→ · · ·とベイズ統計の枠組から階層的に生成および推定できることが明らかになった.
そこで本論文では, この階層 Pitman-Yor 過程によるn グラムモデルを拡張し, データ中の各単語が生成された n グラム長を隠れ変数とみなしてベイズ推定を行う
ことで, 文脈により様々に長さの異なる可変長 n グラムの生成モデルを提案する. この方法により, n グラムモ
デルの n を指定せず, 原理的には無限長とすることができ, 従来不可能だった高次 n グラムの推定が可能となる. また, 言語モデルの副産物として, 上で述べた可変長の「句」を教師なし学習の枠組から, 確率的に推定することができる.

12

sing like
she

will
he

does
sing

like

and
it

bread

model

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

図 1: 階層的 CRP の Suﬃx Tree 上の表現. 客一人一人が, モデル上のカウントを表している.
在最高性能といわれる言語モデルの Kneser-Ney スムー
ジング [10] は, この確率過程の近似となっている.
階層 Pitman-Yor 過程は, 確率論の分野では 2-パラ
メータポアソン=ディリクレ過程 [11] とよばれている
Pitman-Yor 過程を階層化したものであり, 階層ディリ
クレ過程 [12] の拡張と考えることができるが, ここでは直接 Lebesgue 測度に基づく式ではなく, それと等価な階層的な CRP (中華料理店過程) [13] を使って, 直
感的に説明する.
例として, トライグラムの言語モデルを考えよう. これは図 1 のように, 深さ 2 の Suﬃx Tree (接尾辞木) で表すことができる. いま, 文脈 ‘she will’ に続いて ‘sing’を予測したいとき, この木をユニグラムに対応する根 から,  → will → she の順に枝をたどり, 到達した ‘shewill’ に対応するノードの持つカウント分布を用いて,
p(sing |she will) を計算する.

HPYLM の学習を行う際には, 根だけの初期状態の木から始め, 学習データのトライグラムについて, その1 つ 1 つのカウント (CRP では, 可算無限個のテーブ
ル=語彙数を持つ中華料理店のメタファーから, このカ
ウントを「客」と呼ぶ) を図 1 のように, 深さ 2 の対応するノードに, 必要に応じて新しくノードを作りながら追加してゆく.
ここで一般には, どのノードにも全ての種類の単語のカウントがあるわけではない. そこで, 客をノードに追加する時, ある確率で4 その客のコピー (代理人) が親ノードに客として送られる. たとえば, ノード ‘shewill’ に客 ‘like’ がいなくても, 姉妹ノード ‘he will’ に‘like’ がいれば, そのコピーが共通の親ノード ‘will’ に送られているため, 確率 p(like|she will) は 3-gram 確率p(like|she will) (これは 0) と, 親ノードの持つ 2-gram
確率 p(like|will) を適切に補間して計算される. この過程は再帰的に行われ, 親ノードに客 ‘like’ が追加される際にもコピーがその親ノードに送られ, 2-gram 確率は
1-gram 確率との補間で計算されるため5 , 直接親ノードにない語についても, 必ず確率を求めることができる.

以下ではまず 2 節で, 階層 Pitman-Yor 過程によるn グラム言語モデルについて説明し, 3 節で Suﬃx Tree
上に確率過程を考えることにより, これを原理的に無限長に拡張する. 4 節で LDA を用いたそのトピック適
応化について述べ, 5 節で実験結果を示す. 6 節で考察
および関連研究について述べ, 7 節で全体のまとめと将来の展望についてふれる.

2



Depth 0

階層 Pitman-Yor 過程と n-gram 言語モデル

階 層 Pitman-Yor 過 程 に よ る n グ ラ ム 言 語 モ デ ル(HPYLM) [8][9] は, 初めて提案された n グラム分布の階層的生成モデルであり3 , 後に説明するように, 現
2 頻度による一様なカットオフは, 性能がきわめて悪いことが示されている [4].
3 これまでの n グラムの確率モデルは各文脈での頻度をディスカウントした後, 和を 1 に正規化して確率とするものであり, その頻度の由来を問うものではなかった. また, 各 1-グラム, 2-グラム,· · · のカウントとその確率は, 基本的に独立に計算されていた.

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

2

1 − qi
1 − qj1 − qkである. 図 3 に, ハイパーパラメータ (α, β) の違いによるベータ分布の例をいくつか示す.
文脈 h = wt−∞ · · · wt−2 wt−1 に続いて単語 wt が観測されたとき, 我々は Suﬃx Tree を根  から始めて, → wt−1 → wt−2 → · · · の順にノードをたどって降りていくが, この時, 必ず深さ (n−1) で止まるのではなく,
このパス上の qi をそれぞれ q0 , q1 , q2 , . . . として, 確率ijkp(n = l|h) = ql

図 2: Suﬃx Tree に客を追加する確率過程. (1−qi ) は
ノード i の持つ「通過確率」を表す.

c(w|h)−d·thw
θ+d·th·+p(w|h )θ+c(h)
θ+c(h)

に従って深さ l で停止し, そこに客を追加する (図 2).
この式からわかるように, 非常に深いノードであっても, そのパスに沿った qi が小さければ (すなわち,「通過確率」が高ければ) 深い n グラムが使われ, 逆に浅いノードでも, qi が大きければ (「通過確率」が低ければ)そこで止まる確率が大きくなる. 式 (3) より, 深さ n のノードに到達する確率は n に従っておおよそ指数的に減少するが, その度合は木の枝によって異なり, 高頻度の長い系列に対応する深いノードを許すことのできる
モデルとなっている. 6(1)として, 再帰的に計算される.
ここで c(w|h) はノード h での w のカウント, c(h) =w c(w|h) はその総和であり, h = wt−n+1 · · · wt−1 は
1 つオーダーを落とした文脈である.
thw は w が p(w|h) からではなく, 親ノード p(w|h )から生成されたと推定された回数であり, w thw = th·と書いた. d, θ は Pitman-Yor 過程のパラメータであり,
Suﬃx Tree 上のすべての客の分布から, それぞれベー
タ事後分布, ガンマ事後分布によって推定できる. 詳し
くは [8] を参照されたい.
式 (1) は, カウント c(w|h) をディスカウントした分
布を 1 つ低いオーダーの分布と補間した確率になっているが, thw ≡ 1 とすると, この式は Kneser-Ney スムー
ジングと一致し, Kneser-Ney スムージングはこの確率過程のヒューリスティックな近似であることがわかる.

3.2

可変長階層 Pitman-Yor 過程

3.1

Suﬃx Tree 上の確率過程nsと表すことができる. ここで, s は代理客を含む客全体の配置を表す隠れ変数である [8]. この n, s は, ギブス
サンプリングにより推定することができる.
具体的には, 単語 wt の持つ隠れた n グラムオーダー
n t を,n ∼ p(n |w, n , s )
(5)
t

−t

t

−t

のようにサンプリングして更新していく. (st も, この時同時にサンプリングされる.) ここで n−t , s−t はそれぞれ, n, s から nt , st を除いたベクトルである.

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

qi ∼ Be(α, β)

可変長ベイズ n-gram 言語モデル

もちろん, われわれは言語の Suﬃx Tree のノードが持
つ真の qi の値は知らない. それでは, どうやって qi を推定すればよいだろうか.
ここで, 上の可変長生成モデルでは, データ w =w1 w2 · · · wT について, それぞれの単語が生成された
隠れた n グラム長 n = n1 n2 · · · nT が存在していると仮定していることに注意したい. したがって, われわれのモデルでは, データ w の確率は
p(w) =
p(w, n, s)(4)

さて, ここでの問題は, 図 1 において客がすべて, 深さ (n−1) のノードに到着するとしていることである.
実際には, 自然言語の持つ Suﬃx Tree はある所で浅く,ある所は非常に深い, 図 2 のような形をしており, 言語はさまざまに長さの違う n グラム文脈から生成されていると考えられる. それでは, 自然言語の持つこのような木をどのようにして推定すればよいのだろうか.

3

(3)

i=0

結果として HPYLM では, 文脈 h = wt−n · · · wt−1 に続く単語 w の確率は,p(w|h) =l−1

(1 − qi )

4
3.5
3
2.5

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

2
1.5
1

(2)

0.5
0
0

から生成されていると仮定する.
ここで, Be(α, β) = Γ(α+β)/(Γ(α)+Γ(β)) ×q α−1 (1 − q)β−1 は二項確率 q の確率分布であるベータ
分布の確率密度関数であり, 期待値は E[q] = α/(α+β)

0.2

0.4

0.6

0.8

1

図 3: ベータ分布の例とハイパーパラメータ.
6 式 (2)(3) の形からわかるように, これは Suﬃx Tree 上で定義された, Beta two-parameter process の Stick-breaking process [13]である.

3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 のギブスサンプラ.

struct ngram {ngram *parent;
splay *children;
splay *words;
int ncounts;
int ntables;
int stop;
int through;int id;};ai +α
ai +bi +α+β

3.3

(6)

のように予測を行う. ここで第二項は文脈 h の持つ n グ
ラム文脈長分布であり, 式 (8) で与えられる. 第一項はオーダーを n とした HPYLM の予測確率であり, (1)式で求められるが, この確率はすでに Kneser-Ney ス
ムージングと同等に階層的にスムージングされていることに注意されたい. すなわち, VPYLM の予測確率
は, HPYLM の n グラム確率をさらに n = 0, 1, · · · , ∞の文脈事後分布で混合したものになっている. 実際には (10) をさらに, 訓練データ w からの n, s の N 個の
Gibbs 事後サンプルで平均化して予測を行う. 8(7)と展開できるが, この第一項は n グラムオーダーが ntと決まったときの wt の n グラム確率であり, 式 (1) から求められる. 第二項は, この文脈で深さ nt のノードに到達する事前確率であり, 式 (3) および式 (6) から,

p(nt = l|w−t , n−t , s−t )
l−1

bi +β
al +α
=
al +bl +α+β i=0 ai +bi +α+β

予測と文脈長確率分布

予測の際にも, われわれは従来のように n グラム長を固定していないため, n を隠れ変数とみなして, 文脈 h に対してp(w|h) = n p(w, n|h)
(9)

(10)
= n p(w|n, h)p(n|h)と推定される. また, 式 (5) はベイズの定理から

p(nt |w, n−t , s−t )∝ p(wt |w−t , n, s−t ) p(nt |w−t , n−t , s−t )/* = (ngram **) *//* = (restaurant **) *//* c(h) *//* th· *//* ah *//* bh *//* word id */図 5: n グラムノードのデータ構造.

式 (5) で nt をサンプリングする際, われわれは他の客 (単語) が Suﬃx Tree をたどった深さ n−t を全て知っていることに注意されたい. したがって, 他の客がノード i で止まった回数を ai , 通過した回数を bi とおくと,qi の期待値は, ベータ事後分布の期待値としてE[qi ] =/* n-gram node */

(8)

3.4

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

実装

ギブスサンプリングの際, Suﬃx Tree 上で数千から数万にのぼることがある子ノードをたどる操作を高速化するため, われわれは [5] と同様に, 子ノードの管理に
スプレー木 [15] を使用した. スプレー木は O(log n) で子ノードを探索可能な二分順序木である. アクセスの際に木を自己組織的に最適化することで, 高頻度なアイ
テムを高速に探索できるため, 自然言語のように PowerLaw を持つ系列での動的なデータ構造として特に適している.
われわれはこのスプレー木を子ノードだけでなく,各ノードの持つ予測単語9 の管理にも用いた. 図 5 に,Suﬃx Tree の各 n グラムノードに使用したデータ構造を示す.

これらの確率を用いて, 各単語の持つ隠れた n グラム
オーダーをサンプリングする, 可変長 Pitman-Yor 言語
モデル (VPYLM) のギブスサンプラを構成することができる (図 4).
このアルゴリズムは HPYLM のギブスサンプリングの拡張であり, 単語 wt に対応して Suﬃx Tree の order[t]の深さにいる客を一人, 根からノードをたどって削除
し, ai または bi をパスに沿って 1 ずつ減らす. 新しいn グラムオーダーをサンプリングした後, 客を新しい深さに追加し直して ai または bi を 1 ずつ増やし, この深さを order[t] に記録する. 以上を繰り返す. 7
式 (7) から nt をサンプリングする際, 計算量的な問題から, 実際にはある最大値 nmax を設定してその中でサンプリングを行うか, または nt の事前確率 (8) がある小さな値  以下になるまで計算を行う. このとき,
n グラムモデルにおいて ‘n’ は必要なくなり, われわれは原理的に, n をベイズ的に積分消去した「∞-グラム
言語モデル」を得ることができる.

4

可変長ベイズ n-gram 言語モデルのト
ピック適応

可変長 n グラムモデルについて, そのベイズ生成モデルが得られたので, 次にそのトピック適応化を自然に考えることができる.
8 これは, Gibbs サンプリングが事後分布からの正確なサンプリ
ングであり, 事後確率最大化を行うものではないからである. ディリ
クレ過程混合モデルに対して最近提案されたモデル探索法 [14] は,この意味で興味深い.
9 CRP においては, 「レストラン」と呼ばれている.

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

4

4.1

Latent Dirichlet Allocation (LDA)

グラム分布が異なるため, ギブスサンプリングの際, カ
ウントがどのテーブルに追加され, その親テーブルは何かを明示的に追跡する必要がある.
この情報を用いて, VPYLM の LDA 化 (VPYLDA)のギブスサンプリングは, 図 6 のように行うことができる. ここで draw topic は, 単語 wt がトピック k に属する事後確率このためのモデルとして, 我々は LDA[16] を使用した.
LDA では, 各文書に, 隠れたトピック混合分布 θd =(θ1 , θ2 , . . . , θM ) があり, θ がディリクレ事前分布
M
Γ(M γ)  γ−1
θ ∼ Dir(γ) =θΓ(γ)M t=1 t(11)から生成されていると仮定する. 簡単のため, 上ではディリクレ分布のハイパーパラメータは全て同じ値 γとした. このとき, 文書 d = w1 w2 · · · wN の各単語は次のようにして生成される.

p(k|wt , w1:t−1 ) ∝ p(wt |w1:t−1 , k) · p(t|θd )∝ p(wt |w1:t−1 , k) · (nd−t,k +γ)(13)から k をサンプルする関数である. p(w|h, k) はユニグ
ラム分布 k を用いた VPYLM の予測確率 (10), nd−t,kは文書 d 中でトピック k に割り当てられた単語数 (wtを除く) を表す.

1. θd ∼ Dir(γ) をサンプル.
2. For n = 1 . . . N ,a. t ∼ Mult(θd ) をサンプル.
b. wn ∼ p(w|t) をサンプル.
ここで, トピック言語モデル p(w|t) として [16] ではユ
ニグラム分布が使われているが, LDA は混合モデルであるから, これは任意の分布に置き換えることができ,
ここではトピックごとの VPYLM とすることができる.
しかし予備実験の結果, トピック毎の VPYLM を混合する方法では, トピックを考慮しない時に比べて予測精度が悪化することがわかった.
この理由は, LDA のギブスサンプリングによりデータを分割し, トピック別の n グラム言語モデルを構築す
ると, n グラムのスパース性がより深刻になるためだと考えられる. トピックを動的に推定することによる精度上昇より, 選択されたトピック言語モデルのカバレー
ジ不足による精度悪化の方が問題となるからである.

4.2

(12)

5

実験

5.1

VPYLM on Text Corpora

英語および日本語の標準的な大規模コーパスを用いて実験を行った.11
データ 英語については, [18][19] 等で使われている NAB (North American Business News) コーパスの WSJ セットよりランダムに選択した 409,246 文,
10,007,108 語を訓練データ, さらに 10,000 文を評価データとした. 単語はすべて小文字とし, 全体で頻度 10 未満の単語は同じ特別な語にまとめた. 総語彙数は 26,497語である. 日本語については毎日新聞 2000 年度のテキスト (約 150 万文) からランダムに選んだ 520,000 文,
10,079,410 語を訓練データ, 10,000 文を評価データとした. MeCab [20] で分かち書きを行い, 頻度 10 未満の語をまとめて, 総語彙は 32,783 語となった.

ギブスサンプリングによるモデル推定

そこでわれわれは, VPYLM において, データの多いユ
ニグラム分布のみを混合分布 (混合 Pitman-Yor 測度)とすることとした. LDA によって決まるトピック分布
θd に従い, 単語ごとに異なるユニグラム分布を用いた
可変長 n グラム分布から単語が生成される.
このとき, 階層 Pitman-Yor 過程によって生成される
n グラムカウントは, テーブル10 ごとに生成されたユニ

学 習 設 定 予 備 実 験 の 結 果 と 計 算 量 的 制 約 か ら,
HPYLM, VPYLM のそれぞれのモデルについて N =200 回のギブスサンプリングを行い, さらに 50 回の事後サンプルを用いて評価を行った. Suﬃx Tree の形を決めるベータ事前分布のハイパーパラメータは(α, β) = (4, 1) としたが, これはより深い木が得られる (1, 1) の一様分布を用いた場合等とほとんど性能差がなかったためである. (α, β) の値による性能差とその最適化については, 6 節を参照されたい. 実験はすべて Xeon 3.2GHz, メモリ 4GB の Linux 上で行った.

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 のギブスサンプラ.

結果 表 1 に, HPYLM と VPYLM のパープレキシ
ティをモデル中の n グラムノード数とともに示す. モ
デル次数 n は前者では固定, 後者では最大値 nmax を意
味する. 1211 中国語についても, Sinica バランスドコーパス [17] を用いて漢字単位の言語モデルを構築して実験を行い, 同様の結果を確認している. (n = 5 のときパープレキシティ43.39.)
12 表 1 には示されていないが, Modiﬁed Kneser-Ney スムージングを用いた SRILM [21] による英語のパープレキシティは, n = 3, 5, 7, 8についてそれぞれ 118.91, 107.99, 107.24, 107.21 であり, HPYLMおよび VPYLM はこれより優れた性能を達成している.

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

5

n
3
5
7
8
∞

HPYLM VPYLM Nodes(H)113.60113.74
1,417K
101.08101.6912,699K
N/A
100.68
N/A
N/A
100.58N/A—
161.68—p
0.9784
0.9726
0.9556
0.95120.93940.8896
0.88310.86960.7566
0.7134
0.6617:

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

n
3
5
7
8
∞

HPYLM VPYLM Nodes(H) Nodes(V)
78.06
78.22
1,341K
1,243K
68.36
69.35
12,140K
6,705K
N/A
68.63
N/A
9,134K
N/A
68.60
N/A
9,490K—
141.81—
5,396K

図 8: NAB コーパスで学習した 8 グラム VPYLM のSuﬃx Tree から得られた, 確率的フレーズ.
からユニグラムで単語を生成する代わりに, 確率的に子ノードをたどってからフレーズ w = w1 w2 · · · wn がモデルから生成される事前確率は,(b) 日本語 (毎日新聞コーパス)

表 1: 英語および日本語のコーパスでのテストセット
パープレキシティとモデルの持つノード数. N/A はメ
モリオーバーフローを表す.

p(w) = qn−1 

5.3

訓練デ ータは NAB コー パスと同 様に前 処理し,801,580 語, 語彙数 10,477 語のデータとなった. N = 250
回のギブスサンプリングを行った後の単一サンプルを用い, 文脈 h = w1 · · · wn−1 での単語 wn の予測確率を,順に以下のように求めた.

p(wn |h, t) p(t|h) (n = 1 . . . N ) (15)p(wn |h) =# of occurrencest

ここで p(wn |h, t) はトピック t のユニグラムを用いた
可変長 n グラムの予測確率 (10) であり, p(t|h) は仮想的な文書と考えた h のもつトピック t の事後期待値である. 言語モデルは固定であるから, 高速化のため,この計算には LDA の変分ベイズ EM アルゴリズム [16]
を用いた.

6

3.0×106
2.5×106
2.0×106
1.5×106
1.0×106
5.0×105
0

1

2

3

4

5

6

VPYLDA on 20news-18828

データと学習設定 可変長 n グラム LDA(VPYLDA)の評価データとして, われわれは 20news-18828 データ
セット [23] を用いた. このうち, 20 個のニュースグルー
プを同等にカバーするように 4,000 文書を訓練データ,
400 文書を評価データとした.

提案法は, Ron ら [22] における Suﬃx Tree と等価な確率オートマトンに, さらに入力を可変長とする状態遷移確率を加えたものとも考えることができる. 木の根

0.0×100(1 − qi ) · p(wn |w1 · · · wn−1 ) (14)として計算することができる. ここで, qi  = E[qi ] は(6) 式で与えられる, パス wn−1 → · · · → w1 に沿った確率である. これは, われわれの可変長モデルで初めて可能な式となっている. 図 8 に, 8-グラム VPYLM から得られた「確率的フレーズ」の例を, 上の確率でソート
して示す.

Suﬃx Tree と確率的フレーズ

3.5×10n−2
i=1

この結果から, VPYLM は HPYLM とほぼ同等の性能を40 %以上少ないノード数で達成し, HPYLM では
推定できない n = 7, 8 のような高次 n グラムについても, 必要なもののみを選択的にモデルに加えることで推定が可能であり, より高い性能を持つことがわかる.
また, 同じ (最大) オーダーnの場合でも, VPYLM
は HPYLM より 20%程度学習が高速である. これは,
VPYLM において n グラムオーダーをサンプリングする計算コストよりも, 不必要に深いノードを追加しないことによる計算量の削減が大きいからだと考えられる. 図 7 に, 8-グラム VPYLM において推定された n グ
ラムオーダーの, データ全体での分布を示す. 文脈長を長くするメリットと, 深いノードに到達するコストの間で適切なトレードオフが行われ, n = 3, 4 程度をピー
クに指数的な減衰が起きていることがわかる.

5.2

Stochastic phrases in the suﬃx tree
primary new issues
BOS at the same timeamerican telephone &is a unit of
to NUM % from NUM %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.

実験結果 表 2 に, トピック混合数 M を変えたときの VPYLDA のテストセットパープレキシティを示す.
M = 1 のとき, これは VPYLM と等価であり, 最下段に示した.
予測は改善しているが, その差はわずかであることがわかる. 学習されたモデルを観察したところ, この理

7n図 7: 8 グラム VPYLM で推定されたnグラム文脈長のデータ全体での分布. n = 0 がユニグラム, n = 1 がバイ
グラム,. . . である. 実際にはさらに, 式 (1) により低次の n グラムと階層的にスムージングされることに注意.

6

由は, 高頻度の単語が各トピックユニグラムに均等に分配されないためであることがわかった. 図 1 の階層的
CRP において, トピック t をもつ客のコピーが親ノードに送られるのは, その客が現在のノードではなく親ノードから生成されたと確率的に判断された場合であるが, 高頻度の語は多くのノードで既に存在するため,カウントが再利用されて単に 1 増やされ, トピック別
ユニグラムまで確率的に到達しないことが多い.
トピックはユニグラムに限られるものではなく, バ
イグラムやトライグラム以上にも別の混合数で存在す
る13 ことを考えると, このような階層的な混合モデルの推定には, また新しい方法を必要とすると思われる.

6

PPL
136
134
132
130
128
126
124
0.1

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

104.69103.57103.28105.30

2

0.5
5 10

2

5

10

β

0.1

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

本研究は, データ圧縮における Context Tree Weighting
法 [24] を自然言語に応用した, Pereira らの興味深い研究 [5] をその動機としている. 彼らの手法も様々な深さの木の事後確率を考え, それらを混合するものである
が, n グラム分布を階層的に推定するモデルは存在しなかったため, 最終的に各ノードでの Witten-Bell ス
ムージングと頻度によるカットオフに頼っており, 性能
面でのアドバンテージがないという結果になっていた.
これに対し提案手法では, 彼らの手法で定数だった木の生成確率をベイズ化し, 階層 Pitman-Yor 過程でスムージングされた n グラムをさらに混合し, 生成モデルの立場からカウント毎に確率的なプルーニングを行うという点で, その後継となっていると考えることができる.
5 節の実験では, Suﬃx Tree の形を決める事前分布として (α, β) = (4, 1) を用いたが, このパラメータは経験
ベイズ法により, (6) 式で各 qi がもつベータ事後分布から最適化することもできる. [25] の Newton 法を用いると, 1M 語の NAB コーパスのサブセットの場合, この値は各繰り返しですべて (0.85, 0.57) に収束した.
しかしながら, VPY 言語モデルの性能はハイパーパラメータにはあまり依存しない. 図 9 に, (α, β) ∈(0.1 ∼ 10)×(0.1 ∼ 10) の範囲で変えたときのパープレ
キシティを示す. β α となる場合を除いて, 性能はほぼ一定であることがわかる.
最後に, 図 10 に森鴎外『舞姫』で学習した 5-gram

PPL

0.5 1
α

1

図 9: VPYLM のハイパーパラメータ (α, β) とテスト
セットパープレキシティの関係.

考察および関連研究

Model

134
132
130
128
126
124
122

図 10: 『舞姫』からランダムに生成したテキスト.
VPYLM, n = 5.

VPYLM から, ランダムに生成した文の例を示す. 14
従来のように文脈と最長一致するモデルのノードを使用すると, オーバーフィットのために n = 5 ではほぼ学習データがそのまま再現されてしまうが, ここでは
式 (8) にしたがって後ろから確率的に文脈をたどり, 止
まったノードから単語を生成することで, 学習データの特徴をとらえたテキストが生成されていることがわかる.

7

まとめと展望

本論文では, 最近提案された n グラム分布に対するノンパラメトリックな確率過程である階層 Pitman-Yor 過程を拡張することで, 単語の生まれた n グラム文脈長を適切に推定する可変長 n グラム言語モデルを示した.
無限の深さをもつ確率的な Suﬃx Tree を考え, それをベイズ推定することで, これまで固定だった n を原理的に不要とし, 可変長とすることができる.
提案法は最大オーダーの従来法と同等の性能を, より少ない空間的および時間的計算量で達成し, 従来不可能だった高次 n グラムの推定も可能にする. また, 言語モデルの副産物として, 学習された Suﬃx Tree から特徴的な系列を確率つきで取り出せることを明らかにした.
また, 本研究の手法は言語モデルに限られることな
く, 可変長マルコフモデルを実現する一般的なベイズ的方法であることに注意されたい. プルーニングに基づくこれまでの “可変長モデル” と異なり, 提案手法は

表 2: 20news-18828 データセットにおける VPYLDAのテストセットパープレキシティ.
13 たとえば, ‘mixture of Gaussians’ と ‘mixture of ﬂour’ の出
現は文脈に応じてほぼ排他的だと考えられる.

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

7

可変長系列の完全な生成モデルとなっている.
本研究では Suﬃx Tree の事前分布として, 柔軟だが単純な共通のベータ分布を用いたが, [26] にみられるような事前分布を考えることで, モデルをより精密にすることができると考えている. また, トピック適応化についても, 階層的な混合モデルのよりよい推定法を考えていきたい.

[17] Chu-Ren Huang and Keh-jiann Chen. A Chinese
Corpus for Linguistics Research. In Proc. of COLING 1992, pages 1214–1217, 1992.
[18] Stanley F. Chen and Joshua Goodman. An Empirical
Study of Smoothing Techniques for Language Modeling. In Proc. of ACL 1996, pages 310–318, 1996.
[19] Joshua T. Goodman. A Bit of Progress in Language Modeling, Extended Version. Technical Report
MSR–TR–2001–72, Microsoft Research, 2001.

参考文献[20] Taku Kudo. MeCab: Yet Another Part-of-Speechand Morphological Analyzer.
http://mecab.sourceforge.net/.

[1] C. E. Shannon. A mathematical theory of communication. Bell System Technical Journal, 27:379–423,
623–656, 1948.

[21] Andreas Stolcke. SRILM – An Extensible Language
Modeling Toolkit. In Proc. of ICSLP, volume 2,
pages 901–904, 2002.

[2] 工藤拓. 形態素周辺確率を用いた分かち書きの一般化とその応用. 言語処理学会全国大会論文集 NLP-2005,2005.

[22] Dana Ron, Yoram Singer, and Naftali Tishby. The
Power of Amnesia. In Advances in Neural Information Processing Systems, volume 6, pages 176–183,
1994.

[3] Manhung Siu and Mari Ostendorf. Variable n-gramsand extensions for conversational speech language
modeling. IEEE Trans. on Speech and Audio Processing, 8:63–75, 2000.

[23] Ken Lang. Newsweeder: Learning to ﬁlter netnews.
In Proceedings of the Twelfth International Conference on Machine Learning, pages 331–339, 1995.

[4] Andreas Stolcke. Entropy-based Pruning of Backoﬀ Language Models. In Proc. of DARPA Broadcast News Transcription and Understanding Workshop, pages 270–274, 1998.

[24] F.M.J. Willems, Y.M. Shtarkov, and T.J. Tjalkens.
The Context-Tree Weighting Method: Basic Properties. IEEE Trans. on Information Theory, 41:653–
664, 1995.

[5] Fernando Pereira, Yoram Singer, and Naftali Tishby.
Beyond Word N-grams. In Proc. of the Third Workshop on Very Large Corpora, pages 95–106, 1995.

[25] Thomas P. Minka. Estimating a Dirichlet distribution, 2000. http://research.microsoft.com/˜minka/
papers/dirichlet/.

[6] Florencia G. Leonardi. A generalization of the PST
algorithm: modeling the sparse nature of protein sequences. Bioinformatics, 22(11):1302–1307, 2006.

[26] Jim Pitman. Combinatorial Stochastic Processes.
Technical Report 621, Department of Statistics, University of California, Berkeley, 2002.

[7] Peter Buhlmann and Abraham J. Wyner. Variable
Length Markov Chains. The Annals of Statistics,
27(2):480–513, 1999.
[8] Yee Whye Teh. A Bayesian Interpretation of Interpolated Kneser-Ney. Technical Report TRA2/06,
School of Computing, NUS, 2006.
[9] Yee Whye Teh. A Hierarchical Bayesian Language
Model based on Pitman-Yor Processes. In Proc. of
COLING/ACL 2006, pages 985–992, 2006.
[10] Reinhard Kneser and Hermann Ney. Improved
backing-oﬀ for m-gram language modeling. In Proceedings of ICASSP, volume 1, pages 181–184, 1995.
[11] Jim Pitman and Mark Yor. The Two-Parameter
Poisson-Dirichlet Distribution Derived from a Stable
Subordinator. Annals of Probability, 25(2):855–900,
1997.
[12] Y. W. Teh, M. I. Jordan, M. J. Beal, and D. M. Blei.
Hierarchical Dirichlet Processes. Technical Report
653, Department of Statistics, University of California at Berkeley, 2004.
[13] Zoubin Ghahramani.
Non-parametric Bayesian
Methods. UAI 2005 Tutorial, 2005. http://learning.
eng.cam.ac.uk/zoubin/talks/uai05tutorial-b.pdf.
[14] Hal Daumé III. Fast search for Dirichlet process mixture models. In AISTATS 2007, 2007.
[15] Daniel Sleator and Robert Tarjan. Self-Adjusting Binary Search Trees. JACM, 32(3):652–686, 1985.
[16] David M. Blei, Andrew Y. Ng, and Michael I. Jordan. Latent Dirichlet Allocation. Journal of Machine
Learning Research, 3:993–1022, 2003.

8