情報論的学習理論テクニカルレポート 2009
Technical Report on Information-Based Induction
Sciences 2009 (IBIS2009)

ベイズ確率文脈自由文法のための高速構文木サンプリング法
Split Position Slice Sampler
武井俊祐*
Shunsuke Takei*

牧野貴樹 †
Takaki Makino†

高木利久*†‡
Toshihisa Takagi*†‡

Abstract: We propose a new tree sampling algorithm for Bayesian probabilistic context-free grammar (PCFG) called Split Position Slice Sampler. Split Position Slice
Sampler is developed based on Beam Sampling method that is a fast MCMC sampling algorithm for Bayesian Hidden Markov Model, and adapted to Bayesian
PCFG. This tree sampling method can be combined with Metropolis-Hastings sampler to constitute an efficient grammar sampling algorithm for Bayesian PCFG. Because this algorithm does not involve any approximation, more efficient inference isachieved without losing accuracy. We evaluate our approach by comparing with anexisting method in a small artificial corpus.
Keywords: Bayesian inference, PCFG, MCMC

1 Introduction

PCFG で利用される内側確率表に直接対応付けることができずアルゴリズムが構築できない．本論文では内側確率表における終端位置と分割位置に補助変数を対応付ける形式として Split Position Slice Sampler という手法を新たに提案することで Beam Sampler の枠組みを拡張し，これを Johnson らの手法へ組み込むことによって高精度かつ高速な Bayesian
PCFG モデルのパラメータ推定法を構築する．

本研究は，ベイズ拡張された確率文脈自由文法(Bayesian PCFG)に対する効率的なサンプリングアル
ゴリズムを構築することで，高速かつ高精度な文法学習を可能にすることを目的とする．Bayesian PCFG
モデルに対する精度の高いパラメータ推定手法としては，Johnson らの動的計画法を利用したマルコフ連
鎖モンテカルロ法（MCMC）による手法 [1]が知られているが，モデルが複雑になるにつれて増大する計算コストが問題となる．そこで我々は，ベイズ拡 1.1. Motivation
ベイズモデルとは，統計的機械学習分野において張された隠れマルコフモデル（Bayesian HMM）のた
学習モデルにベイズ統計の手法を導入するもので，めの高速な MCMC 法として知られている Beam
ベイズ化された学習モデルは，与えられたデータにSampling[2]を PCFG に応用することで Johnson らの対するモデルパラメータの推定値と不確実性の範囲
手法を高速化する．Beam Sampling は，動的計画法
を確率分布として表現する．結果としてベイズ統計と Slice Sampling[3]を利用することにより，Bayesian
における学習は，従来の最尤法による点推定に比べHMM の高速なパラメータ推定を可能にする手法で汎化性能に優れ，過学習の問題も生じにくい．また，
あるが，これをそのままの形式でベイズ PCFG の枠
あらかじめ推定したい対象に何らかの知識がある場
組みへ応用しようとするとき，HMM において各時合，それを事前確率分布という形式でモデルに導入
刻において割り当てられている補助変数をベイズすることでより良い推定が可能であるという利点も*東京大学大学院 新領域創成科学研究科 情報生命科学専ある．さらに，近年注目を集めているベイズモデル
攻, 〒277-8568 千葉県柏市柏の葉 5-1-5 総合研究棟 609,
tel. 04-7136-3973,の拡張であるノンパラメトリックベイズモデルでは，e-mail: takei_shunsuke@cb.k.u-tokyo.ac.jp, Department of Con無限次元のパラメータ空間を仮定し，データを表現
putational Biology, Graduate School of Frontier Science, The
University of Tokyo, General Research Building 609, 5-1-5 Kaする最適なモデルを推定することでモデル選択の問
shiwa-no-ha, Kashiwa, Chiba, 277-8568 JAPAN
題を解決することができるため，様々な統計学習モ†東京大学 総括プロジェクト機構‡情報・システム研究機構ライフサイエンス統合データベースセンター

デルに導入されており[4][5][6]，今後より広範な問題 に動作する Bayesian PCFG のための MCMC 法を構築することを目指す．
に応用されることが期待されている．
ベイズ学習モデルにおいて学習の対象である個々のパラメータは確率変数で表現されているため，従2 Background
来の最尤法とは異なりしばしば計算コストの高い高2.1. PCFG
次元の期待値計算を伴う方法でパラメータ推定を行
文脈自由文法(CFG)は文の生成過程を明らかにすう．特に高い精度が要求されるような場合においてるモデルであり G = (V N , VT , S , R ) の 4-タプルで定義は高精度なパラメータ推定手法として知られるされる． V T は終端記号集合， VN は非終端記号集合，
MCMC 法が利用されるが，膨大なサンプルを必要と
R は生成規則の集合， S ∈ V N は開始記号である．
するため計算コストが高く，ベイズモデルの応用に
ここでは生成規則についてチョムスキー標準形，すおける問題となっている．
なわち A → BC または A → s の形式の生成規則のPCFG[9]は計算機科学分野だけでなくバイオイン
みを考える．ここで A, B, C ∈ V N ， s ∈ VT である．
フォマティクス分野など[10]幅広い分野で活用され確率文脈自由文法(PCFG)は，CFGの各々のルールている一般性の高い確率モデルであり，そのベイズに対して確率値を割り振ったものであり， (G , θ ) とモデルである Bayesian PCFG についても期待が高い．
定義される． θ は R 次元の実数ベクトルであり， θ
近年，変分ベイズ法[7][8]のような近似に基づく高速のそれぞれの要素は θ r で表され，これは r ∈ R の生パラメータ推定手法が提案され，さかんに研究され成規則の確率値であることを表す．たとえば，ているものの，高精度な推定を必要とする場合は依θ A→BC ならば A → BC の規則の確率， θ A→s ならば然として計算コストの高い MCMC のような手法がA → s の規則の確率を表す．ここで，確率の定義か用いられている．
θ A→a = 1である必要がある．
ら θ r ≥ 0 かつ
Bayesian PCFG に対する MCMC 法を構成する場合，a∈VT ∪VN ×VN
単純には Gibbs Sampler のような手法の適用が考えら
2.2. Bayesian PCFGれるが， PCFG のパラメータ間に強い相互依存があ
Bayesian PCFG では，生成規則のパラメータ θ をりパラメータ空間も大きいことから Gibbs Sampler で確率変数 P(θ) として扱う．ベイズアプローチにおいは収束が遅く効率が悪い．これに対し Johnson らはて離散パラメータは，その扱いやすさから Dirichlet
構文木のみのサンプリングによる Metropolis-Hastings
分布のような共役な確率分布によって表され，本論
Sampler を構築し，より効率的なサンプリング手法
文における Bayesian PCFG についても Dirichlet 分布を提案している[1]．しかし Johnson らの手法は依然を導入した PCFG を仮定している．ここで Dirichletとして計算コストが大きく，大規模データに適用す
分布を PD (⋅) ， Γ をガンマ関数， A → ∗ の形式の文るのには困難を伴う．
法規則を R A ， θ における A → ∗ の形式の文法規則
近年 Bayesian HMM のための高速なサンプリングについてのパラメータベクトル θ A ，Dirichlet 分布の手法として Beam Sampler が提案された．この手法はハイパーパラメータベクトルを α ， α におけるSlice Sampling の手法を応用し，隠れ状態間の遷移確
A → ∗ の形式の文法規則についてのサブベクトルを
率分布を補助変数(スライサー)で“間引く”ことでα A で表すと， θ の事前分布 PD (θ | α ) は計算の高速化を図っている．この“間引き”の処理
は近似等の処理ではなくサンプリングの処理の一部(1)
PD (θ | α ) = ∏ PD (θ A | α A )であるため，Beam Sampler は精度を損なわず BayesA∈VN
ian HMM のパラメータ推定を高速に行うことができる．HMM における遷移確率分布は PCFG におけるのような Dirichlet 分布で表現される．ここで，書き換え規則の確率分布に対応するため，正しいス
ライス手法が与えられれば，同様な高速化を達成で1
PD (θ A | α A ) =∏θ rα r −1 (2)
きることが期待される．
C (α A ) r∈RA
そこで我々は，Johnson らの手法に Beam Sampler∏r∈RA Γ(α A )(3)C (α A ) =の枠組みを導入することで，精度を保ったまま高速Γ ( ∑ r ∈R α A )∑Aである．一般にモデルパラメータは未知でありデー
タから推定する必要がある．ベイズアプローチにおける推定の対象はデータ観測後の事後確率分布であ
り，

n

A
i ,k

=

(7)

∑ ∑θ

A→ BC∈R i ≤ j < k

A→ BC

B
i, j

p p

C
j +1, k

(8)

(4)
A

i =1

の左項を求めることである． w = ( w1 ,..., wn ) は終端記号列からなるデータ集合であり， wi が個別の終端記号列を意味する．

2.3. Gibbs Sampler
Bayesian PCFG の事後分布は解析的積分が不可能

であり，その推定には MCMC 法や変分ベイズ法などの手法が用いられる． MCMC 法のもっとも単純な手法の 1 つである Gibbs Sampler を Bayesian PCFGのパラメータ推定法として用いる場合，パラメータ
θ と構文木 t を交互にサンプリングすることでアルゴリズムが構築される．ここで， t = (t1 ,..., t n ) であり，それぞれの t i は終端記号列 wi に対する構文木を意味する．詳しい導出は Johnson らの論文に譲り，
ここでは具体的な Gibbs Sampler のアルゴリズムを直接示す．
構文木 t において文法規則 r ∈ R が使われた回数
を f r (t ) ， t における A → ∗ の形式の文法規則が使われた回数のベクトルを f A (t ) とすると，Bayesian
PCFG の Gibbs Sampler は， t を固定して θ についてのサンプリング，P(θ | t, w, α) = ∏ PD (θ A | f A (t ) + α A )pkA, k = θ A→skp

P(θ | w ) ∝ P( w | θ) P(θ | α )= ∏ P( wi | θ) P(θ | α )ある終端記号列 s = ( s1 ,..., s n ) が与えられたとき，その内側確率を(5)のように計算する．ここで， pi , k は非終端記号 A が終端記号列 si ,..., sk を生成する確率を意味する．次に，作られた内側確率表の確率にしたがい構文木を再帰的にサンプリングする．これを疑似コードで示すと，Function SAMPLE( A, i, k )If i = kreturn TREE( A, sk )Else

( j , B, C ) = MULTI(A, i, k )return TREE(A, SAMPLE(B, i, j),SAMPLE(C, j, k ))となる．ここで，関数 SAMPLE( A, i, k ) はある構文
木のノードにおいて非終端記号 A が最終的に終端記
号列 si ,..., sk を生成するとき，そのノード以下の構文
木を確率的にサンプリングする関数である．また，
関数 MULTI(A, i, k ) はどの分割点で構文木が枝分かれするのか，その分割位置 j と子ノードの非終端記
号 B,C を確率的に返す関数であり，その確率はP( j , B, C ) =θ A→ BC p iB, j p Cj +1,kp iA, k(9)と表すことが出来る．

2.4. Metropolis-Hastings Sampler

PCFG における各々のパラメータ間には強い依存があるため，パラメータ θ を個別にサンプリングす
る Gibbs Sampler は十分なサンプルを得るために多大θ を固定して t についてのサンプリング，な時間が必要になる．この問題に対し Johnson らは
Bayesian PCFG のパラメータ θ を積分消去し，構文n(6)P(t | θ, w, α ) = ∏ P(t i | wi , θ)
木のサンプリングと Metropolis-Hastings の枠組みに
i =1
よるサンプルの確率的な受理から構成されるサンプを交互に繰り返すことになる．パラメータ θ についリングアルゴリズムを提案している．この手法では，てのサンプリングは，構文木 t における各文法規則
依存の強い θ のサンプリングは回避されるため，の使用回数から容易に計算できるが，構文木 t の具Gibbs Sampler に比べ速い収束が見込まれる．さらに体的なサンプリングについては自明ではない．
θ のサンプリングにかかる計算コストも不要である
Johnson らは構文木のサンプリングについて，動的ため，効率的な Bayesian PCFG のサンプリングアル計画法を用いた効率的な手法を提案している．まず，ゴリズムであるといえる．
A∈VN

このアルゴリズムでは，Gibbs Sampler とは違いパラメータ θ のサンプリングを行わず，構文木をサン
プリングしたのち，そのサンプルを確率的に受諾もしくは拒否する．いま， w = ( w1 ,..., wn ) を終端記号
列の s の集合とし，それぞれの終端記号列 wi に対応する構文木を t = (t1 ,..., tn ) で表す． t' i が新しくサンプルされた構文木， t −i が t i を除いた構文木サンプル群とすると，そのサンプルの受理確率は⎧⎪ P (t ' i wi , t −i , α ) P (t i wi , θ' ) ⎫⎪A(t i , t ' i ) = min ⎨1,⎬⎪⎩ P (t i wi , t −i , α ) P (t ' i wi , θ' ) ⎪⎭⎧⎪ P (t ' i t −i , α ) P (t i wi , θ' ) ⎫⎪= min ⎨1,⎬⎪⎩ P (t i t −i , α ) P (t ' i wi , θ' ) ⎪⎭(7)C (α A + f A (t )) (9)A∈VN C (α A + f A (t −i ))P(t i | t −i , α ) = ∏である． θ' は θ r ' を要素に持つベクトルである．
θ r ' は t −i と α が与えられたときの θ r の期待値で，

f r (t − i ) + α r∑r '∈R f r ' (t −i ) + α r '

1.
2.
3.

となる．ここで，θr '=メータ間の依存の問題が解決される．また Slice
Sampling に基づく補助変数（スライサー）を各時刻について導入し，(10)

A

前回サンプルされた状態遷移列に従いスライ
サーをサンプリング
状態遷移分布をスライスすることで，各時刻における可能な状態遷移を間引き間引かれた分布に従い隠れ状態列をサンプルという手順でサンプリングを行う．ここでスライスとは，対象となる確率分布においてスライサーの値以上のもののみを考慮するよう分布を“間引く”操作であり，スライスされた分布は等確率でサンプリングされる．この手順により各時刻で考慮すべき状態遷移数が減るために計算が高速に行われる．Beam Sampler における分布のス
ライスおよびスライスされた分布のサンプリングという処理は近似処理ではなく，Slice Sampling を援用したもので，それ自体がサンプリングの手続きである．そのため Beam Sampler は高精度なパラメータ推定というマルコフ連鎖モンテカルロ法の性質を維持したまま高速化に成功した手法であるといえる．

3 Method
3.1. PCFG へのスライスサンプリングの導入

我々のアプローチは Johnson らの手法に Beamとして計算される．
Sampler の枠組みを導入することで高速化を図るも以上が Johnson らの Bayesian PCFG のための構文のである． Beam Sampler でサンプルとする隠れ状態
木サンプリングの枠組みである．この手法はパラメ
列は PCFG における構文木にあたり，Beam Sampler
ータ θ と構文木 t を交互にサンプリングする Gibbs
で用いている動的計画法は Johnson らの手法では内Sampler に比べ効率的ではあるが，パラメータ空間
側確率を計算し，構文木をサンプリングすることとが大きい場合，内側確率の計算に多大な計算コスト等価である．ここから Slice Sampling を内側確率のがかかり依然として大規模データには不向きである．
計算に利用すれば Beam Sampler が PCFG へと適用可能である．Johnson らのアルゴリズムが2.5. Beam Sampler
Beam Sampler は，Bayesian HMM のための高速
MCMC アルゴリズムであり，HMM のパラメータ推定にしばしば用いられる動的計画法(この場合Forward-Backward)と Slice Sampling の手法を応用することで高速化をしている．HMM のための Gibbs
Sampler は，各時刻の隠れ状態を交互にサンプリン
グする形式で行われるが，Beam Sampler は各時刻の隠れ状態を個別にサンプリングするのではなく，動的計画法を利用し隠れ状態列をひとつのサンプルとする形式で行われるため，Johnson らの手法同様パラ

1.
2.
3.

内側確率表を計算
構文木をサンプリング
構文木を Accept/Rejectという手順で構成されていたのに対し，提案手法は
1.
2.
3.
4.

スライサーをサンプリング
生成確率をスライスして，内側確率表の各セルにおける文法規則適用分布を間引き
構文木をサンプリング
構文木を Accept/Reject

を提案する．この形式におけるスライサーは内側確という手順で構成されることになる．しかし PCFGと HMM のモデルの違いから Beam Sampler をそのま 率表において，最終的に終端記号を出力する“終端ま適用しようとしてもアルゴリズムは構築できない． セル”を担当するスライサー u と，構文木の“分割点”を担当するスライサー v の 2 種類に分けて扱わ問題となるのは，Beam Sampler における前回のサンプルにおける各時刻の状態遷移確率からスライサれる(Figure 3)．終端セルに対応する構文木上のノー
ーの値をサンプリングするという手続きである．
ドは常に存在するため， u については Beam Sampler
HMM では各時刻についてスライサーがそれぞれ割同様に，前回の構文木サンプル中の対応するノード
り当てられており（Figure 1），これを PCFG にその において用いられた文法規則の確率値をもとに値を決める．一方，それぞれの終端記号の間を“分割まま適用しようとすると内側確率表の各セル，つま点”と定めると，構文木の終端ノード以外のノード，
り考えうる全ての構文木のノード位置についてスラ
すなわち分岐ノードは必ず 1 つの“分割点”を担当
イサーを導入するという形式となる．この場合前回のサンプルにあたるのが構文木であり，スライサー
することがわかる．ここから，“分割点”を担当すのサンプルに必要なのは，構文木の各ノードで用いるスライサー v は，構文木中の“分割点”を担当すられた文法規則の確率値である．しかしこの場合，
る分岐ノードの文法規則の確率値から作られる
前回のサンプル，すなわちひとつの構文木からすべ(Figure 4)．この手法では内側確率計算の際，終端セてのセルのスライサーを作ることができない．なぜル以外のセルにおける計算に複数の v が利用される
なら，サンプルとして得られた構文木は，内側確率ことになるが，サンプルされた構文木における各ノ
表全てのセルに一対一対応するだけノード数を保持
ードでは，そのいずれかのスライサーにより作られしておらず，従ってこのような配置でスライサーをた文法規則が用いられ，構文木全体で見たときにス導入しようとした場合，全てのスライサーをサンプ
ライサーの重複はない．また，導入すべきスライサリングするには情報が足りないからである(Figure 2)． ーは最下列セル数 n，分割点数 n-1 であり，構文木
これは n を文中の単語数とした場合，構文木は 2n-1の持つノード数と一致するため，必ず一対一対応が出来る．この手法を我々は Split Position Slice Sam個のノードしか持たず，一方内側確率表にはpler と呼ぶ．以下では Split Position Slice Sampler を利n(n+1)/2 個のセルがあるということからも分かる．
用した構文木のサンプリングアルゴリズムの具体的な手順を示す．
3.2. Split Position Slice Sampler
終端記号列 s に対する前回の構文木サンプルにおそのため我々はスライサーの配置に関する新たなルールとして，Split Position Slice Sampler という形式 いて， s k を導出した文法規則の確率値を π k ，構文木の分割点 j における文法規則の確率値を ρ j と定義する．関数 I(C ) は，条件 C が真のとき I(C ) = 1 ，
偽の時 I(C ) = 0 となる関数である．

Time … 6

7

8

9 …

S3

S1

S2

S3
S

u1,3

A

u6→7
Figure 1.

u7→8

u8→9

u1,2

C

A

B

w1

w2

w3

Figure 2.

PCFG へ Beam Sampler を単純に適用した場合

u1,1

u2,2

u3,3

HMM のための Beam Sampler におけるスライサー

上段が 1 つの隠れ状態列サンプル，下段が動的計画法に導入されるスライサー列を表し，破線がその対応を示している．各

左が 1 つの構文木サンプル，右が内側確率表に導入さ時刻間の状態遷移確率を用い，動的計画法の各セルに対応する

れるスライサーを表し，破線がその対応を示している．

スライサーuiをサンプリングする．観測列は省略している．

情報が足りずスライサーを導入できないセルが存在する

1. Sampling u, v stepu k ~ Uniform(0, π k )v j ~ Uniform( 0, ρ j )

(11)
(12)

2. Inside-Filtering Step

p kA, k = I(u k < θ A→ wk )p iA,k =(13)∑ ∑ I(v < θj

A→ BC∈R i ≤ j < k

A→ BC) p iB, j p Cj +1,k(14)

3. Tree-Sampling Step
Function SAMPLE( A, i, k )If i = kreturn TREE( A, sk )Else

4 Experiments( j , B, C ) = MULTI(A, i, k )return TREE(A, SAMPLE(B, i, j),SAMPLE(C, j, k ))関数 MULTI における確率計算はP( j , B, C ) =文木のサンプリングステップについての置き換えであり，その他の変更は無い．つまり本手法は Gibbs
Sampler に組み込んで θ のサンプリングと組みあわせるか，Metropolis-Hastings Sampler と組み合わせてサンプリングされた構文木の確率的な受理をすることで PCFG のサンプラーとして機能する．
以上で Beam Sampling 法の枠組みを PCFG へと適用した高速な MCMC 法である Split Position Slice
Sampler が構築された．この手法は，単純に考えた場合に対応のつかない，形の違う構文木同士に対応をつけることで Beam Sampler の枠組みを拡張した．
これにより，Beam Sampler の枠組みは Bayesian
PCFG のためのサンプリングアルゴリズムに導入可能となり，高速なサンプラーが構築された．

I(θ A→ BC ) p iB, j p Cj +1, k
p iA, k(15)と置き換えられる．
このアルゴリズムは Johnson らの手法における構

人工的な CFG 文法から小規模なコーパスを生成し，ノンパラメトリック PCFG モデル[11]による教師無し文法学習により，本手法と従来手法の比較を行った．コーパスは文法規則 S→xSy，S→zSw，S→SS，S→εから生成され，平均文長 9 単語の 100 文を訓練
データ，平均文長 13 単語の 20 文をテストデータとして用い，従来の Johnson の手法と提案手法についてそれぞれ 50 回の実験を行い，計算速度とテストデータの対数尤度について評価を行った．

v1

u2

u1
v1
Figure 3.

v2

v1

v2

v1

v2

u3
v2

終端セルにスライサーu，

分割点にスライサーv を導入．結果として導入するスライサーの総数は構文木のノード数になる．

v1
Figure 4.

v2

分割点と分岐ノード，スライサーの関係

丸が分岐ノード，四角が終端ノードを表し，3 文字の終端記号列に対応する 2
種類の構文木を上下に配し，黒いノードが担当する分割点を実線矢印で示している．どのような形の構文木でも必ず分割点を担当する分岐ノードが 1 つ存在し，分割点を担当するスライサーを作ることができる．

Time (second)

0

100

200

300

400

500

600

Loglikelihood

-300

-500

-700
Figure5.

時間ごとの対数尤度上昇

従来手法
提案手法

-900

従来手法
提案手法

1200

Time (second)

1000
800
600
400
200
0
0

10

20
Figure6.

0

20

30

40

50

Sampling Step

1 回の Sampling Step ごとにかかる時間

40

60

60

80

Sampling Step
100

Loglikelihood

-300

-500

-700

Figure7.

-900

サンプリングステップごとの対数尤度上昇

従来手法
提案手法

Figure5 は時間ごとに見たコーパスの対数尤度，参考文献

Figure6 はサンプリング 1 ステップごとにかかる時間，[1] Johnson, M., Griffiths, T. L. & Goldwater, S. (2007).
Figure7 はサンプリング 1 ステップごとに見たテスト
Bayesian Inference for PCFGs via Markov Chain
データの対数尤度である．グラフは 50 回の実験によMonte Carlo. In Proceedings of North American
る結果の平均値であり，誤差棒は 95％の信頼区間を
Chapter of Association for Computational Linguis示している．Figure5 より，提案手法は時間ごとの対
tics – Human Language Technologies.
数尤度が急速に上昇しており，従来手法に比べより[2] Gael, J. V., Saatci, Y. Teh, Y. W. & Gharamani. Z.

高速に学習していることがわかる．Figure5 とFigure7 においてサンプリングの初期に対数尤度が低いのは，スライサーという，新たに推定すべきパラメータが加わったため，つまりモデルが複雑になっ[3]たためであると考えられる．しかし，Figure6 からは，
1 ステップの計算速度が従来手法に比べて提案手法[4]が大幅に高速化されているために，その影響を補って余りある高速化効果が得られ，その結果，従来手法に比べ計算速度の向上がなされていることがわか
[5]
った．

5 まとめ

[6]
本論文では Beam Sampler の枠組みを Split Position
Slice Sampler へと拡張し，従来手法に組み込むことで Bayesian PCFG のための高速なパラメータ推定手法を構築し，それを小規模な実験によって評価した．
我々の手法では一切の近似をせず，高い精度でのパ[7]ラメータ推定が可能であるという MCMC 法の性質を保っているため，高速かつ高精度な手法であるといえる．このアルゴリズムは CKY アルゴリズムを[8]
伴えばどのような問題にも適用可能であり，ベイズ(2008) Beam Sampling for the Infinite Hidden
Markov Model. In Proceedings of the 25th International Conference on Machine Learning.
Neal, R. M. (2003). Slice sampling. The annals of
Statistics..
Teh, Y. W., Jodan, M. I., Beal, M. & Blei, D. (2006).
Hierarchical Dirichlet processes. Journal of theAmerican Statistical Association..
Blei, M., Gharamani, Z. & Rasmussen, C. (2002).
The infinite hidden Markov model. In Advances in
Neural Information Proceeding Systems.
Liang, P., Petrov. S., Jordan., M. I. & Klein. D.
(2007) The infinite PCFG using hierarchical
Dirichlet processes. In Proceedings of the 2007 joint
Conference on Empirical Methods in Natural language Processing and Computational Natural Language Learning.
Attias, H. (1999). Inferring Parameters and Structureof Latent Variable Models by Variational Bayes. In
Proceedings of Uncertainty in Artificial Intelligence.
Kenichi, K., Yoshitaka, K., Taisuke, S. (2004).
Variational Bayesian Approach to Probabilistic Context-Free Grammar based on Dynamic Programing.
Journal of Information Processing Society, Japan.

拡張された PCFG のスーパーセットのようなモデルにも適用可能であることが期待できる．
また，Beam Sampler は元々ノンパラメトリック拡[9] Chaniak, E. (1996). Treebank grammars. Association
張された HMM において提案されたものであるといfor the Advancement of Artificial Intelligence .
うことから，実験でも示したとおり，ノンパラメト
リック拡張された PCFG のためのサンプリング法と[10] Sakakibara, Y.; Brown, M.; Hughey, R.; Mian, I. S.;
Sjölander, K.; Underwood, R. C.; and Haussler, D.
しても用いることができる．ただし，PCFG ではノ(1994). Stochastic Context-Free Grammars for tRNA
ンパラメトリック HMM と動的計画法の向きが逆でModeling. Nuc. Acids Res.
あることなどが原因で，いくつかの変更が必要とな[11] Liang, P., Petrov. S., Jordan., M. I. & Klein. D.
る．しかしそれらは提案手法とは直接関係が無く，(2007) The infinite PCFG using hierarchical
性能評価にも影響しないため，本論文では省略した．
Dirichlet processes. In Proceedings of the 2007 joint
今後は PCFG のスーパーセットのためのサンプリ
Conference on Empirical Methods in Natural lanングアルゴリズムへの拡張といったアルゴリズム的guage Processing and Computational Natural Lanな応用，実際の大規模データへの適用などの実用面
guage Learning.
での応用の可能性を探るつもりである．