Gibbs Sampling による確率的テキスト分割と複数観測への拡張
持橋大地 菊井玄一郎
ATR 音声言語コミュニケーション研究所

daichi.mochihashi@atr.jp, genichiro.kikui@atr.jp
1

はじめに

10000

pDM/pMSM

1000
文書分類や情報検索などで用いられる文書モデルで100
は多くの場合, bag-of-words 表現が使われ, 単語の10
時系列情報が落ちていることが多いが, 実際には文
1
書の内部は均質ではなく, 様々な話題が順に呈示さ0.1れることで構造化されている.
0.01
このような文書内部の意味的遷移をモデル化する
0.001
ために, われわれは文書内部に隠れた意味的変化点
0 200 400 600 800 1000 1200 1400 1600 1800 2000
Timeがあると仮定し, 確率的テキストモデルである LDA
図 1: DM/MSM-DM の予測確率比と文脈長.
および DM[4] と組み合わせることで, 逐次モンテカ
ルロ法を用いて変化点をオンライン推定し文脈を追ズムを適用することはできない. このため, 変化点跡する方法を示した [1][2].
を次々とサンプリングしていく Gibbs Sampler に
しかしながら, この方法は隠れた変化点を単語ごよる解法を示し, 解析例を考察する. 最後に Textとに計算するためにノイズに弱く, 現在の文脈にあTiling 法 [7] との比較など今後の課題について述
まり関係ない語が偶然現れた場合にそこを変化点とべ, 文書に対する言語モデルとしてソフト分かち書して検出してしまい, 時として予測が著しく悪化す
き [5] との関連についてふれる.
るという欠点があった. 図 1 に, ある文書 (1,910 語)における提案法と, 文脈として過去の履歴をすべて 2 MSM-DM と意味的変化点確率用いる従来法との予測確率の比を, 文書の先頭からの位置を横軸にとって示す. 全体として予測が良く 変化点を持つ確率的テキストモデルとして提案したはなっているものの (y 軸 < 1), 縦軸の対数比でみ ものに, LDA を用いた MSM-LDA と DM を用いたると予測確率がかなり悪くなってしまう場合もある MSM-DM を提案した [1, 2] が, 後者の方が単語単体をすべてモデル化できるため柔軟であり, 計算もことがわかる.
もう一つの欠点として, 提案した方法は予測モデル 高速で文脈モデルとして高性能であることがわかっであるため, 変化点確率の計算は最近の観測語およ ているため, 以下では MSM-DM について考える.
び過去の履歴のみに基づいて行われている (いわゆる Forward モデル) という点が挙げられる. 音声 2.1 MSM-DM の予測モデル
認識等における応用ではこの方法が必要であるが, 逐次モンテカルロ法 (SMC) を用いた MSM-DM の文書全体が先に与えられており, それをモデル化す 解法では, 各モンテカルロサンプル (粒子とよばれる際には, 後ろの情報も用いることで文脈の変化を る) が変化点を実際に 0/1 でサンプリングし, 粒子より正確にとらえ, 変化点確率を計算することがで ごとに異なる最近の変化点からの履歴を用いて予測きると考えられる (いわゆる Forward-Backward モ を行う. この予測分布を, 各粒子について適切に更新される重みに基づいて混合することで最適な予測デル).
そこで本稿では, まず変化点を複数の観測値を持 分布を生成する, というアルゴリズムになっている.
つブロック毎に計算し, 推定をロバスト化すること 図 2 に, この予測アルゴリズムの動作を示す.
を試み, その結果を報告する. ただし, ブロック長があまり大きくなるとテキストの潜在的なダイナミ 2.2 変化点確率の拡張クスが捉えられず, 推定がかえって悪くなることが 上記の SMC における解法では, 各粒子は時間 t で予想される. 実際に, 数単語程度のブロックに取る の変化点 It = {0, 1} を, 次の二項確率に従ってサことが予測を最良にすることがわかった.
ンプリングする. ここで, wt は観測値 (単語または提案法は非線形な HMM であるため, Forward- 単語ブロック) w1 w2 · · · wt , It は過去の It の履歴
Backward 計算には通常の Baum-Welch アルゴリ It = {I1 , I2 , . . . , It } であるとする.

z粒子 #1
粒子 #2粒子 #3粒子 #4:粒子 #Nd1}|d2 · · · dc

{ 事前分布重みwt+1:wt−1wt

1 I = {I1 , I2 , . . . , IN } をランダムに 0/1 で初期化. (Bernoulli(p) からの乱数)
2 For t = 1..T {For n = randperm(N ) {(t)Sample In ∼ p(In |I(t) \n, w, λ, α).
}}

図 2: MSM-DM の予測モデル.
p(It |It−1 , wt ) ∝ p(wt |wt−1 , It−1 , It )p(It |It−1 ) (1)
図 3: Gibbs Sampler of MSM-DM.
(p(wt |wt−1 , It−1 , It = 1)p(It = 1|It−1 ) = f (t) 3.1 Gibbs Sampler of MSM-DM=p(wt |wt−1 , It−1 , It = 0)p(It = 0|It−1 ) = g(t) ギブスサンプリングとは, マルコフ連鎖モンテカル
wt のそれぞれが複数の観測値 (ブロック長 l) か ロ法 (MCMC) の単純な場合であり, 隠れ変数を一つずつサンプリングして更新してゆくことで, 真のらなるとき, この確率は以下のように展開できる.
隠れ変数の分布に従ったサンプルを得る方法である
Case It = 1:
M[6]. われわれの場合, テキスト w = w1 w2 · · · wN にX
Γ(αm ) Y Γ(αmv +nv (wt ))λmf (t) = ρ ·(2) 対して, 隠れた変化点ベクトル I = {I1 , I2 , . . . , IN }Γ(αm +l) v∈w
Γ(αmv )
m=1tをサンプリングする, 図 3 のアルゴリズムとなる.
Case It = 0: M
ここで randperm(N ) は 1 . . . N のランダムな並X
Γ(αm +h)(t)g(t) = (1−ρ)·λm
び換えを返す関数であり, I(t) \n は I(t) から In をΓ(αm +h+l)
m=1除いた集合. 初期化にかかわらず, 繰り返し回数Y Γ(αmv +nv (h)+nv (wt ))(3) T → ∞ の極限で, 図 3 のアルゴリズムから得られ
Γ(αmv +nv (h))
v∈wtる変化点ベクトル I(t) は隠れた真の分布からのサンここで h は各粒子ごとに異なる, wt−1 の中で プルに収束し,T
1 X (t)
最近の変化点以後の観測値, h はその長さであり,
In(6)
In =T
nv (x) は x 中の v の出現回数を表す.
t=1
Γ 関数の性質 Γ(x+1) = xΓ(x) から, l = 1 のとき上とすることで時刻 n での変化点確率 p(In = 1) が式は [1, 2] における式と一致し, その自然な拡張と 計算できる.1なっている.
3.2 条件つき確率の計算
この確率に従い, 各粒子はベルヌーイ試行¶µ
図 3 のアルゴリズムの中で, 変化点を実際にサンプ
f (t)(4) ルする確率分布 p(In |I\n, w, λ, α) は以下のようにIt ∼ Bernoulli
f (t) + g(t)変形できる.
を行って変化点をサンプルし, 次の観測を予測, 粒p(In |I\n, w, λ, α) ∝ p(In , I\n, w|λ, α) (7)子の重みを更新する. 変化点の事前確率 ρ は It−1
∝ p(w|In , I\n, λ, α) p(In , I\n|λ, α)(8)から, ベータ事後分布の期待値∝ p(w|In , I\n, λ, α) p(In |I\n).
(9)
α + nt−1 (1)(5)
hρt i =α+β+t−1(9) 式において第 2 項は (5) と同様にして求まる.
第1 項は n より前の最近の変化点を B, 後の最近として求まる. ここで nt−1 (1) は It−1 中の 1 の回F として,数. この事前分布として何が適切かはブロック長 l の変化点をによって異なるため, 実験ではすべてハイパーパラ p(w|In = 1, λ, α) ∝ p(wB . . . wn−1 |λ, α)メータ (α, β) = (1, 1) とし, 一様事前分布を用いた.
× p(wn . . . wF |λ, α) (10)
 p(w|I = 0, λ, α) ∝ p(w . . . w |λ, α)nBF3 意味的変化点の Gibbs Samplingによって DM の文書確率から求めることができ文脈から次の語を次々に予測し, 実際に観測された る. すなわち, (9)(10) 式は変化点 B と F で挟まれ語に従って予測分布を更新していく SMC アルゴリ たテキストが, n を挟んでズムの他に, 文書全体が与えられた下での変化点を
1
実際には, 小さい t に対する I(t) は初期値に依存するたサンプリングしていく Gibbs Sampler を構成する め, 最初の方の値 (burn-in) は捨てて計算することで, 精度のことができる.
よいサンプルが得られる.

3.3

周辺化パープレキシティと変化点

このアルゴリズムは p(I|w) に従って変化点系列 Iをサンプルする方法であるが, p(I|w) ∝ p(I, w) であるから, この方法で変化点を求めることは, 文書と変化点の結合確率 p(w, I) において, 変化点 I を周辺化した文書確率X
p(w) =p(w, I)(11)
Iの和に含まれる各サンプルを得ていることに相当している. I の可能な組み合わせは 2N 個と厖大になるが, ギブスサンプリングによりその中で確率の高いものを確率的に取り出し, (11) 式を以下で近似することができる.
T1X
p(w, I(t) )(12)p(w) 'T
t=1670650630
PPL• wB · · · wn−1 , wn · · · wF が別に生成された確率(変化点あり)• wB · · · wF が同時に生成された確率(変化点なし)を変化点の事前確率で重みづけて比べ, 前者の確率が高ければ時間 n での変化点確率が高まる, という式になっている. ここで, 同じ内容語が前と後に同時に出現していた場合, DM の下ではこの場所の変化点確率は非常に低くなることに注意したい.
DM は混合 Polya 分布を持つが, Polya 分布の下では同じ語の 2 回以上の出現回数がダンピングされ,独立な場合より高い確率を持つようになるため [8],前後を分割しない方がずっと高い確率を与えるからである.
なお, この方法は, Steyvers and Brown [3] の方法と ρ を動的に更新する部分を除いて同じである.
[3] は認知過程のモデルとして, 比較的低次元な二項分布が用いられているが, 提案法は DM を用いて,それを意味的相関を持つ数万次元の記号列に拡張したものになっている.

590570550
144.1

実験および考察
実験設定

2345102050s

Block Length

図 4: ブロック長 l での予測パープレキシティ. “s”
は文単位の変化点を表す.
を Smoothed DM のパラメータ推定のための訓練データとした. 語彙は頻度 5 以上の 65,313 語である. DM の混合数は 200 とした.2
MeCab-0.8.1 を用いて分かち書きを行い, 文についての実験では句点を文の境界とした.34.2

複数観測での MSM-DM

図 4 に, ブロック長 l = 1 ∼ 5, 10, 20, 50 および文単位とした各場合におけるテストセットの予測パープ
レキシティを示す. l = 1 が単語ベースのモデルである. 文を単位とすることが特別良いということはなく, むしろ数語を単位としてダイナミクスを柔軟にモデル化した方が, 全体として高い予測確率を与えることがわかる.
図 5 に, 文脈長を横軸に, 単純な DM との予測確率の比 pDM /pMSM を縦軸に取ったプロットを示す.
ブロック長 l が増えるに従い, 予測が大きく悪化する (y 軸 À 1) ことは少なくなるものの, 単純な DMの予測に近づいてしまい, 大きく改善する (¿ 1) ことも少なくなる, というトレードオフがあることがわかる.
1e+06

1e+06

10000

10000

100

100

110.010.010.0001

0.0001

1e-06

文書 w のパープレキシティは p(w)−1/N であるから, 各変化点サンプルに対して, そこで w が区切られた文書確率を計算し幾何平均を取ることで, 隠れた確率的な変化点を考慮した “周辺化パープレキシティ” を求めることができる.

6100500

1000 1500 2000 2500 3000
Time1e-060(a) l = 1
1e+06

10000

10000

100

100

110.010.01

1e-061000 1500 2000 2500 3000
Time(b) l = 21e+06

0.0001500

0.0001
0500

1000 1500 2000 2500 3000
Time(c) l = 51e-06

0500

1000 1500 2000 2500 3000
Time(d) l = 10

図 5: 各ブロック長 l における予測確率比.

実験には 2001 年度版毎日新聞記事のうち, テスト
2Smoothed DM [4] のパッケージを http://chasen.org/データとして, 1,000 語以上の記事 3,250 記事から~daiti-m/dist/dm/ で公開している.
ランダムに選択した 100 記事 (平均 1454.4 語) を用
3
これ以外の形態素情報は, 本論文全体を通じ全く用いていい, 1,000 語を超えない 97,131 記事, 22,912,999 語 ないことに注意.

cosine 距離に何ら明確な意味がなく, モデル的な裏付けのない TextTiling と異なり, 提案手法は生80成モデルから導かれる変化点確率として明確な意味60を持っており, 閾値を用いて変化点を決定すること40なしに, 確率のまま ‘ソフトな’ 取り扱いが可能にな20るという利点を持っている. 今後, 比較実験を行う
0ことでこの利点を検証していきたい.
050150Time 100
工藤 [5] は, マルコフ確率場に逆温度パラメータ
図 6: Gibbs sweep とテキストの変化点.
θ を導入し動的計画法を用いることで, 形態素解析1における区切りを同様に確率化できることを示した. これは形態素が確率的に区切られる言語モデル
0.5につながると考えられるが, その際, 本稿で提案したようにパラメータ自体が言語ストリームの中で変0化し, 形態素解析結果が文脈によって異なるモデル
050150Time 100
図 7: Gibbs による変化点確率 (図 6 を正規化した が考えられる. 意味的に確率的に区切られ, さらに形態素も確率的に区切られ相互作用を持つような,もの).
そんな新しい言語モデルを構築していきたい.
4.3 変化点の Gibbs SamplingP

Gibbs Sweep100

図 6 に, 1,311 語のテキストに対する変化点のギブス
サンプリングの例と, それを正規化することで (6)式から得られる変化点確率を示す. ブロック長を 10とし, p = 0.5 の確率で変化点をランダムに初期化,100 回の burn-in の後に図 6 の 100 個のサンプルを得た. 4
図 8 の SMC による前向き変化点確率と比べると,前後の情報を用いることでノイズが減り, 推定がより正確になっていることがわかる.
この文書に対する DM の文書パープレキシティは700.03, SMC による予測パープレキシティは 657.43,周辺化パープレキシティは 644.91 であった.

5

まとめと今後の課題

先に提案した文脈の推定法をブロック単位の観測に拡張し, あわせて文書全体を考慮してテキストの意味的な変化点を Gibbs Sampling により求める方法を示した.
Gibbs Sampling により意味的変化点を求める手法は, TextTiling[7] のヒューリスティックなアルゴリズムを確率モデルの観点からとらえ直したようなものになっている. しかしながら, ブロック間の0.80.60.40.2005Particle

10Time1520050100150

図 8: 図 7 のテキストの, SMC による変化点確率.
4MATLAB による実装では, このサンプリングには 7 時間24 分を要した. (Xeon 2.8GHz)

謝辞: 本研究は独立行政法人 情報通信研究機構の研究委託「大規模コーパスベース音声対話翻訳技術の研究開発」により実施したものである。

参考文献[1] 持橋大地, 松本裕治. Particle Filter による文脈の動的ベイズ推定. 情報処理学会研究報告 自然
言語処理研究会 2005-NL-165, 2005.
[2] Daichi Mochihashi and Yuji Matsumoto. Context as Filtering. In Advances in Neural Information Processing Systems 18, 2005.
[3] Mark Steyvers and Scott Brown. Prediction
and Change Detection. In Advances in Neural
Information Processing Systems 18, 2005.
[4] 貞光 九月, 待鳥 裕介, 山本 幹雄. 混合ディリク
レ分布パラメータの階層ベイズモデルを用いたスムージング法. 情報処理学会研究報告 2004SLP-53, pages 1–6, 2004.
[5] 工藤拓. 形態素周辺確率を用いた分かち書きの一般化とその応用. In 言語処理学会全国大会論
文集 NLP-2005, 2005.
[6] Andrew Gelman, John B. Carlin, Hal S. Stern,and Donald B. Rubin. Bayesian Data Analysis, 2nd Edition. Chapman & Hall/CRC, 2003.
[7] Marti Hearst. Multi-paragraph segmentationof expository text. In 32nd. Annual Meeting ofthe Association for Computational Linguistics,
pages 9–16, 1994.
[8] Thomas P. Minka. Estimating a Dirichlet
distribution, 2000. http://www.stat.cmu.edu/
˜minka/papers/dirichlet/.