Particle Filter による文脈の動的ベイズ推定
持橋 大地 1,2 松本 裕治 1
1
奈良先端科学技術大学院大学 情報科学研究科
2
ATR 音声言語コミュニケーション研究所 音声言語処理研究室{daiti-m,matsu}@is.naist.jp
概要
文脈をとらえる長距離言語モデルの研究において, これまで, 必要な文脈長の問題はあまり議論されることがなく, 単純に文書の先頭から用いるなどの方法が行われてきた. 本論文はこれに対し, 文脈の変化に対する明示的な確率的生成モデルを与え, 話題の変化とその速度をとらえ, 必要な文脈長を自動的に選択することのできるベイズ言語モデルを提案する. 提案法は TextTilingの確率化ともとらえることができ, 非線型フィルタである Particle Filter によって解かれる.
BNC コーパスでの実験により, 単純な履歴を用いる従来のベイズ言語モデルに対して, 高い性能を示した.
キーワード: Particle Filter, Mean shift model, 変化点検出, 時系列モデル, 長距離言語モデル

A Particle Filter approach to dynamic Bayesian context
estimation
1,2

Daichi Mochihashi 2 Yuji Matsumoto
Graduate School of Information Science, NAIST2ATR Spoken Language Translation Research Laboratories{daiti-m,matsu}@is.naist.jp
1

Abstract
This paper proposes a novel Bayesian long-distance language model that can capture
subtopic shifts within a document. To model these subtopic flows, we introduce a latent mean shift model of natural language, and estimate its state space by a Particle Filter.
Experiments on BNC corpus showed consistent improvements over the naı̈ve context modelthat has been used so far.
Key words: Particle Filter, Mean shift model, Change point analysis, Time series analysis,Long-distance language model

1

はじめに

「文脈」をとらえることは言語活動の基本的な要素であり, われわれはその場の文脈を判断し, 適切にモデ
ルを切り替えてゆくことで, 適応的に言語理解や発話を行っている. たとえ句読点の一切ない小説 [18] であっても, そこには明確に話の文脈が存在し, むしろ
文脈の流れをとらえていくこと自体が, テキストを読むということの大きな要素の一つだと言ってよい.
工学的にみても, 単一の文脈に適応するだけでな
く, 複数の文脈や状況の変化をとらえ, 動的に適応してゆくことは, 実時間の連続音声認識やロボティクスなどにおいて特に重要であると考えられる.
自然言語処理においては, これは n-グラムより高次の関係をとらえる, 長距離言語モデルの適応化の問題と考えることができる. 短距離の文法的な確率は文脈の影響を受けにくいが, 単語のユニグラム出現確率のような意味的な確率は文脈の影響をきわめて大きく受けるため, 文脈への適応化は大きな課題である.

長距離文脈をとらえる問題は, キャッシュやトリガのような古典的なモデル [14] から始まり, LSI を用いて直接共起しない関係を考慮することのできる言語
モデル [2] を経て, 近年では隠れ変数を用いた混合モデルの推定問題として定式化され, 確率的言語モデルとの相性がよく, 従来法より高い予測性能をもつことが報告されている. [10, 21, 22, 23]
しかしながら, それらのモデルにおいて, 必要な適切な文脈長の問題はほとんど議論されてこなかった.
これらのモデルは基本的にテキストモデルの応用であり, 履歴の時間的な順序を考慮せず, Bag of Words
として捉えるものである. このため, 履歴としては文書の最初から全てを用いるか [10, 21, 22], 1000 単語
前までなどの単純な閾値を用いる [15] ことが行われてきた.
しなし, これはあくまでも近似であり, 実際のテキストがそうなっているわけではない. TextTiling[12] はこのような不均質性に従ってテキストをサブト

ピックに分割するアルゴリズムであるし, Beeferman
ら [1] は同様に言語の時間的な非定常性に着目し, セ
ルフトリガ (同じ語の再出現) の分布から, テキスト
中での語の意味的な関係がテキスト中での間隔に従って指数的に減少することを見出している.
別の言葉で言えば, 今までの確率的なテキストモデ
ル, およびそれに基づく言語モデルは, テキストがどれほど長くても, 1 つの定常情報源から生まれたと仮
定し, そのパラメータを順次精密に求めるアプローチ
であることを意味する.1
本論文ではこれに対し, 文脈の変化に対する明示的な確率モデルを与え, そのパラメータをオンラインで時系列に従って推定することにより, 話題の変化とその速度をとらえ, 適切な文脈長を自動的に選択することのできるベイズ言語モデルを提案する.
このモデルは非線型な HMM であり, 従来の BaumWelch 法やカルマンフィルタ等では解くことができな
いが, 近年計算量的に利用可能となってきた, モンテ
カルロ法を用いたベイジアンフィルタである Particle
Filter を用いることで解くことができる.
2 章で, Mean Shift Model と呼ばれるこのためのモデルについて述べ, 3 章で Particle Filter について説明する. 4 章で Mean Shift Model を自然言語に拡張し, 確率的なテキストモデルである DM および
LDA を用いた MSM-DM, MSM-LDA を導入する.
5 章で BNC を用いた実験結果と考察を示し, 6 章でまとめとこれからの展望について述べる.

して多項分布の分布 (ディリクレ分布または混合ディリクレ分布) を得ることになる.
離散変数上への分布自体を状態とする HMM という意味で, これは Ghahramani らの Factorial HMM(Ghahramani 1995) に似ているが, FHMM のようにダイナミクスのパターンを固定するのではなく, テ
キストによってパターンの一つ一つ異なるランダム
ウォークを追跡することを目的としている.
Blei らは, PLSI[13] の事後多項分布を, 確率の最も高い一点で近似することで離散 HMM を構成し, 異なるテキストの境界を検出する Aspect Hidden Markov
Model を提案している [3]. しかし, 違ったテキストの境界ではなく, テキスト内部のサブトピックの変化をとらえるためには, 2 番目以降3 の山の変化が重要であり, 多項分布の変化を直接モデル化する必要がある. この意味で, 本研究は [3] の厳密化であるともいえる.
以下で, 多項分布の Mean shift model について説
明する.

2.1

Multinomial Mean shift model

Mean shift model (MSM) とは, 隠れ状態の間欠的な変化を記述する生成モデルであり, 正規分布について導入されたものを [7][19], 近年 Chen and Lai [6] により, Particle Filter を用いることで変化率をも動的に推定する拡張がなされたが, 紙面の都合上省略し,[6] での, DNA 分析における多項分布に対する拡張についてのみ以下で説明する.
多項分布の MSM では, 観測されたアルファベット
2 Mean Shift Model
系列 y = (y1 y2 . . . yT ) (yt ∈ A は離散アルファベッ
はじめに述べた確率的文脈モデルはいずれも, 文脈に ト集合) を出力した真の多項分布 θ が複数存在し, 時は隠れたユニグラム分布, あるいは確率的トピック分 間的に変化していると考え, 次のような生成モデルを布という多項分布が存在すると仮定し, 入力履歴に 仮定する.

従ってその推定値を更新することで, 次の語の予測をwith probability ρ θt ∼ Dir(α)
行うモデルである.
= θt−1
with probability (1 − ρ) (1)
したがって, 文脈追跡のためには, 隠れた多項分布yt ∼ Mult(θt )自体の変化をとらえるモデルが必要になる. このた
ここで Dir(α), Mult(θ) はそれぞれ, α, θ をパラめのモデルの一つ2 が Mean shift model (MSM) でメータにもつディリクレ分布および多項分布である.
ある.
このモデルでは,最初に多項パラメータθをDir(α)
これは HMM の一種であるが, 通常の離散 HMMとは違うことに注意したい. 通常の HMM では, 真の からサンプルし, しばらくの間 θ から y を出力する.
状態は M 個の離散状態のどれか一つであり, その確 確率 ρ で文脈の変化が起こると, また新しい θ が率的な推定値として多項分布を得るが, ここでは, 真 Dir(α) からサンプルされ, 以後の y はそこから出力の状態自体が多項分布であり, その確率的な推定値と する. このプロセスを繰り返す. 以上において, θ はもちろん, 変化点の場所もわれわれには未知であり,
1 これは従来のテキストモデルが, 新聞記事のような比較的均観測されるのは出力系列
y のみである.
質で短いテキストを学習データとして用いていたことにも依っていると思われる. 長い, 構造的なテキストの標準的なコーパスは例として, 図 1 の T = 100 の系列を考える. ここ
驚くほど少ない. [12]では, アルファベットは A = {a, b, c} である. この2 本研究に先立ち, 文脈に対して一様なブラウン運動を仮定し,Power steady model (Smith 1979) に基づいて事前分布を確率 系列において, 次の出力 y は何であろうか.
γ ∼ Be(a, b) で忘却し, γ のもつベータ分布のハイパーパラメー
タをオンラインのカーネル密度推定 [9] で求めるアプローチを行ったが, あまり良い結果を得られなかった.

3 トピックは一般に数百存在するため, 点推定による近似は, 非
常に粗い近似となる可能性が高い.

αaaaaaabaacbaabaaaaabbbbbabababaaba\
babbabbbbabcaccccbcacacccccccccccc\
ccaccccaccccccccccccacaaaacbbbbb

θt−1

θc

図 1: 観測された時系列データ.

i=1
となる.
It = 0 の場合:
この場合, 最近の変化点を t = c とすれば (Ic =1, Ic+1 = · · · = It−1 = 0), 図 2(b) のように, 時刻
c において θc ∼ Dir(α) がサンプルされ, yc · · · yt−1を出力した後に y が出力されたのだから, その推定値は
p(y|Yt−1 , It = 0) = p(y|θt )p(θt |yc · · ·yt−1 )dθt (4)=θy ·Dir(α +t−1δ(yt ))dθt (5)

t=c

=

αy +
α+

t−1
t=c δ(y)t−1t=c δ(yt )θt−2 θt−1 θt

θt
yt

θc
yt−1 yt

明らかに, この推定値は直前の変化点がどこであるかに依存する. いま, 時間 t において変化が起こったかどうかを表す二値変数を It としよう. It = 1 は時間 t において変化が起こった (θt = θt−1 ) ことを,It = 0 は変化が起こらなかった (θt = θt−1 ) ことを意味する.
It = 1 の場合:
この場合, 図 2(a) のように, 時刻 t において変化が起こり, θt ∼ Dir(α) が新しくサンプルされ, そこから y が出力されたのであるから, その確率は
p(y|Yt−1 , It = 1) = p(y|θt )p(θt |α)dθt (2)


|A|

αi 
= αy / (3)α(a) It = 1 の場合(b) It = 0 の場合

図 2: Mean shift のグラフィカルモデル.

3

Particle Filter

3.1

Particle Filter と重点サンプリング

Particle Filter [9] とは, モンテカルロ法をオンラインで行うアルゴリズムであり, 近年の計算資源の増大に伴い, 主に実ベクトル空間を対象として, 信号
処理やロボティクスなどの分野で使用されてきた.
重点サンプリング法 [11] を時系列的に行うものと考えられるため, SISR(Sequential Importance Sampling/Resampling) とも呼ばれている.
従来のカルマンフィルタやその拡張などと異なり,線形モデルや正規分布だけでなく, 任意の非線型な分布を追跡することができる. そのため, 本論文のように, 自然言語のような離散データにも原理的に適用可能である.
重点サンプリング (IS) とは, ベイズ推定の期待値計算において, 積分をサンプリングにより近似する方法であり, 確率変数 x の関数 f (x) の期待値を以下のように近似する.

I = p(x)f (x)dx
(7)

p(x)
f (x)dx(8)= q(x)q(x)N(6)と求まる. ここで, δ(y) は y に確率密度が集中する
Dirac の δ 関数.
このように, 直前の文脈の変化点がわかっていた場合, 予測分布は閉じた形で求まるため, 変化点を求めることがこの問題の本質であることがわかる. これは統計学において, 変化点検出問題 [17] として知られている問題の一種である. 下に述べるように, 直前の変化点の位置は, その 1 つ前の変化点の位置に依存する. 同様にして再帰的な依存関係があるため, この問題を解くには, 少なくとも非線型な動的計画法が必要となる.
上式において, 変化点 t = c は計算上確定されなけ
ればならないため, 安定した推定を行う方法として,オンラインのモンテカルロ法である Particle Filterが有用である. 次節で Particle Filter について簡単に説明し, 上の問題のオンライン推定法を述べる.

1  p(x(i) )(9)f (x(i) ) x(i) ∼ q(x)N i=1 q(x(i) )N
1 p(x(i) )=w(x(i) )f (x(i) )w(x(i) ) =N q(x(i) )
i=1



(10)
ここで, q(x) は p(x) よりサンプリングが容易な分布であり, 提案分布と呼ばれる. 式 (10) から, これはx(i) ∼ q(x) に対し, f (x(i) ) を w(x(i) ) で重みづけて和をとることで, f (x) の期待値 E[f (x)] が求まることを意味する.
IS は静的に積分を求めるものであるが, これを時系
列データ x1 · · · xT について拡張したものが Particle
Filter (SMC とも呼ばれるが, 以下 PF) である.
紙面の都合上, 導出の詳細は割愛するが (導出については [8] がわかりやすい), PF では N 個のモンテ
カルロサンプル (パーティクルと呼ぶ) を準備し, その重み wt (x(i) ) (i = 1 . . . N ) を 1/N で初期化し, 観
測データ yt がえられるごとに以下のように更新する.

(i)(i) p(yt |xt )p(xt |xt−1 )wt ∝ wt−1
q(xt |Xt−1 , Yt )(11)

すなわち, ρ がベータ事前分布 Be(α, β) に従う確率変数であるとすると, It−1 中の 1 の回数を nt−1 (1)とすれば, ベータ事後分布の期待値として,q(xt |Xt−1 , Yt ) が 提 案 分 布 で あ り, こ こ か ら
α + nt−1 (1)
(1)
(N )
(i)
E[ρt ] =(20)
xt . . . xt をサンプルし, (11) 式に従って重み wt
α+β+t−1を更新する.
提案分布 q に制約がなく, 非線型な任意の分布を と ρt の推定値が求まる. 以下の実験では, すべてこ
追跡することができるのが大きな特徴である. ここ のオンライン推定値を用いた.
次 に, (12) 式 に お け る 粒 子 の 重 み の 更 新 係
で, q が近似ではなく,
数 p(yt |xt−1 ) ≡ p(yt |Yt−1 , It−1 ) について考えると,q(xt |Xt−1 , Yt ) = p(xt |Xt−1 , Yt )(21)
p(yt |Yt−1 , It−1 )と解析的に正確に求まる場合には, (11) 式は簡単に=
p(yt , It |Yt−1 , It−1 )(22)次式となる.
It ∈{0,1}
(i)
(i)

(12)
wt ∝ wt−1 · p(yt |xt−1 )=p(yt |It , It−1 , Yt−1 )p(It |It−1 )(23)
It ∈{0,1}
2.1 で述べたように, われわれの問題の場合, 変化
点が与えられれば p(xt |Xt−1 , Yt ) はディリクレ分布= p(yt |It = 1, It−1 , Yt−1 )p(It = 0|It−1 )として正確に求まることに注意されたい. このとき,(24)+ p(yt |It = 0, It−1 , Yt−1 )p(It = 1|It−1 )PF による期待値は
= a+b
(25)
N

(i) (i)E[yt |y1 . . . yt−1 ] =wt E [yt |y1 . . . yt−1 ] (13)と, (17) 式の a, b を用いて書けることがわかる.
i=1
以上により, Particle Filter により変化点を確率的である. すなわち, われわれの問題では, Particle Fil- に検出し, 予測を行うには,ter による事後分布は混合ディリクレ分布となる.
1. 各粒子 i = 1 . . . N について,
3.2 文脈の変化点検出問題(a) a, b を (17) 式に従って求める.
そこで次の問題は, 時間 t までの観測値 Yt と, (t − 1)(b) It ∼ Bernoulli (a/(a + b)) をサンプルしてまでの変化点系列 It−1 が与えられたとき, 時間 t で記録する.
変化が起こった確率 p(It = 1|It−1 , Yt ) を求めること(i)(i)(c) 重み wt = wt−1 · (a + b) と更新する.
である.
ベイズの定理から,(1)

p(It |It−1 , Yt )(14)

∝ p(It , yt |It−1 , Yt−1 )(15)= p(yt |Yt−1 , It , It−1 )p(It |It−1 )p(yt |Yt−1 , It−1 , It = 1)p(It = 1|It−1 )=p(yt |Yt−1 , It−1 , It = 0)p(It = 0|It−1 )(16)[≡ a ][≡ b ](17)となるから, (17) 式をそれぞれ a, b とおけば,
ap(It = 1|It−1 , Yt ) =
(18)
a+b
b
p(It = 0|It−1 , Yt ) =(19)a+bと計算することができる.
(17) 式において, 第 1 項は変化/非変化が確定した
後の出力 y の尤度であり, (3) 式および (6) 式から求まる. 第 2 項は変化の事前確率である. これは定数 ρ
としてもよいが, PF においては各粒子が文脈の変化
履歴 It−1 を持つために, それを利用してオンラインで ρ の推定値を求めることができる.

(N )2. wt . . . wt および変化履歴 It から, (13) 式により予測確率を求める.
というアルゴリズムとなることがわかる.
現在の文脈からみて「変な」語 yt が観測されると, 文脈予測確率 b よりもデフォルトの予測確率 a の方が高くなるため, 1(b) のベルヌーイ試行
Bernoulli (a/(a + b)) において, 変化点 It = 1 がサンプルされやすくなる.
この変化点の検出は確率的に行うものであり, さらに N 個の粒子によって平均化されるために, 一回で文脈がすべて変わってしまう危険はないが, 続けてこれまでの文脈と違った語が現れた場合, そのどこかで文脈のシフトが起こることになる.
なお, 上記のステップ 1(c) において, 更新された重みに大きなばらつきが生じた場合, それに適応する(i)
ために粒子を wt (i = 1 . . . N ) に従って再サンプル
し, 重みの小さな粒子を消し, 重みの大きいサンプルから「子供」を作る. この操作はリサンプリングとよばれているが, この際の基準として, 重みの変動係
数 (CV) を用いるとよいことが知られている [9].

1

d1

0.9

0.8

d2

···

dc

0.7

t−1

0.6

?
t

0.5

図 4: 変化点で仮想的な「文書」に区切られた履歴.

0.4

0.3

0.2

0.1

0

0

10

20

30

40

50

60

70

80

90

100

図 3: 図 1 に隠れた多項分布の, Particle Filter によるオンライン推定. 横線が真の θt である.

3.3

Multinomial Filtering

以上のアルゴリズムに従って, 図 1 の観測データから, 隠れた多項分布 θt を PF により推定したものが
図 3 である. ただし, これは Forward 推定であり, 各
θt の推定において, 未来のデータは全く用いていないことに注意. ここでは粒子の数は N = 50, ベータ事
前分布は (α, β) = (1, 10), CV の閾値 = 1.0 とした.

4

Mean shift model of Natural
Language

Chen ら [6] はこの方法を, DNA 系列の推定に用いているが, これを自然言語の単語列にそのまま応用するにはいくつかの課題が残っている.
一つは, アルファベットの大きさが全く異なることである. ATGC の 4 種類しかアルファベットを持たない DNA と異なり, 自然言語には数万から数十万の単語が存在し, それらは独立ではなく, 互いに強い相関を持っている. たとえば, 「病院」という単語の後に「看護婦」という別の単語が多く出現しても, それらは関係が深く, 潜在的な変化は起こっていないと考えられるが, やはり別の記号である「大学」がその後に多く出現すれば, それは別の話題に移った (この場合, 「大学病院」というサブトピックに移った) と解すべきである. アルファベットを独立に扱う上記のMSM では, この関係はとらえることができない.
この関係をモデル化するために, テキストと単語の意味的な確率モデルである DM [22] と LDA [4] を用いて, MSM を自然言語に拡張した. この拡張により, 事前分布自体も [6] と異なり, 動的に更新することができる.
以下, DM と LDA について必要な解説を行いつつ,MSM-DM と MSM-LDA について述べる.
4.1

MSM-DM

Dirichlet Mixture (DM)[22] は, 文脈推定のために山本らによって近年提案された, 確率的なテキストモデ
ルである. DM では, テキストのもつ多項分布の事前分布としてディリクレ分布ではなく, 混合ディリクレ
分布を仮定し, その M 個の混合比 λ = λ1 . . . λM と対応するディリクレ分布のハイパーパラメータ α =α1 . . . αM を, EM 法と Newton 法 (高速化のため, 実
際には近似) を組み合わせることでコーパスから推定する.4
DM では, 履歴単語列 h = (w1 w2 . . . wt ) が与えられたとき, これを仮想的な (順序のない) 文書とみなし, 次式によって次の語 y を予測する. 詳細については, [22] を参照.
M
αmy + n(y)(26)
p(y|h, α, λ) ∝Cm ·αm + hm=1

ここで n(y) は h 中の y の生起回数, h は履歴の長さであり, Cm は次式である.

Cm = λm

Γ(αm )  Γ(αmv +n(v))Γ(αm +h)Γ(αmv )

(27)v∈h

紙幅の都合で詳細は省略するが, [22] とは違った導出により, この方法は, 履歴から事前分布自体を適応的に選択し, Cm により適切に重みづけることで, 最適な予測を行うモデルであるとみなせる.
この DM を多項分布の MSM に用いるには, (3) 式
および (6) 式において, y の予測確率を DM のものと置き換えればよい. [6] では多項分布の事前分布に
ディリクレ分布を仮定しているのに対し, この方法は混合ディリクレ分布を用いることで, そのきわめて自然な拡張になっていることがわかる.
ただし, (3) 式において, y の予測値は履歴 Yt−1 に全く依存しないため, 変化点が起こった後の予測はDM の事前分布からとられることになり, 精度の悪化を招きやすい. いま, 1 つの粒子についてみると, これまでの変化点によって履歴は仮想的な「文書」に区切られており (図 4), この情報を用いて事前分布を更新できる.
すなわち, DM のパラメータ推定において, λm は

λm ∝
pim
(28)
i

(pim は文書 i が m 番目の事前分布から生まれた確率) として求めるが, この方法を動的に適用し, pim
を履歴中の仮想的な「文書」に対して計算して和をとることで, λm の事後分布を求めることができる.
ここで (28) 式において, λm の事前分布が右辺の pimの計算に間接的に含まれていることに注意.
4 http://cl.naist.jp/~daiti-m/dist/dm/ でパッケージを公開している.

この計算のためには pim (i = 1 . . . c) だけが必要なため, 履歴をすべて保存する必要はない. 変化点がサンプルされた時に, 最近の変化点からの pim を新しく計算して追加し, 以後 pim だけを保存すればよい. これはフィルタリングアルゴリズムとして重要な点である. 5

4.2

MSM-LDA

これに対し, LDA を用いて拡張する MSM-LDA では, 単語の出現確率の多項分布ではなく, 潜在的なトピック空間の多項分布を追跡する.
Latent Dirichlet Allocation (LDA)[4] とは, Blei ら
によって提案されたテキスト集合の確率モデルであり, 潜在意味モデルとして知られる PLSI [13] のベイ
ズ的な発展形である.
LDA はパラメータとして, M 個のトピックに関するディリクレ事前分布のパラメータ α と, トピック
毎のユニグラム確率 β = { p(v|m) } (v = 1 .. L, m =1 .. M ) をもつ. 6
履歴 h が与えられたとき, LDA を用いた文脈モデル [21] では, 同様に h を仮想的な文書とみなし, 次の変分ベイズ EM アルゴリズムによって履歴のもつ潜在的なトピック分布 q(λ|h) を求める.

VB-E step:q(zit = 1|h) ∝ p(wi |t) exp(Ψ(α + nt ))(29)

VB-M step:q(λ|h) ∝nt =K

α+nt −1t=1 λthti=1 q(zi = 1|h)

(30)
(31)

q(λ|h) はトピックの M 次元空間におけるディリク
レ分布であり, トピックから単語への写像 β を用いて, 下のように次の語を予測する.
p(y|h) = p(y|λ)q(λ|h)dλ
(32)
=

M


p(y|m)Eq [λm |h].

(33)

m=1

LDA を用いた MSM では, 単語の出現確率 p ではなく, 潜在的なトピック分布 λ を履歴から求めて追跡する. 具体的には, (2) 式と (4) 式において, 予測分
布 p(θt |yc · · ·yt−1 ) がトピック分布 q(λt |yc · · ·yt−1 ) になる. 各粒子について, 上記変分ベイズ法により, 履
歴から q(λt |yc · · ·yt−1 ) を求め, (33) 式による語の予測を粒子全体について混合し, 最終的な予測を得る.
粒子の持つ各トピック分布はディリクレ分布である
5 さらに各 p
im は条件付き独立なため, 必要に応じて古い pimを破棄しても, 他には影響を及ぼさない.
6 http://cl.naist.jp/~daiti-m/dist/lda/ でパッケージを公開している.

から, この場合もトピックの事後分布は混合ディリク
レ分布となる.
MSM-LDA においても, (30) 式の事前分布パラメー
タ α を履歴から更新できる. すなわち, 図 4 のように仮想的に「文書」に区切られた履歴において, 各「文書」d1 .. dc にはトピック事後分布 q(λ|di ) (i = 1 .. c)が存在し, これらに共通するディリクレ事前分布を線形オーダーの Newton 法により求めることができる.
詳細については [4] 参照. 変化点がサンプルされるごとにこの計算を行うことで, 各粒子の持つ事前分布を更新することができる.
最初の事前パラメータ α は Newton 法では使われないが, q(λ|d) を求める際に間接的に使われていることに注意. この Newton 法の計算にも全ての履歴を保存する必要はなく, 変化点ごとに q(λ|d) を計算
し, 保存しておけばよく, オンラインアルゴリズムと
なる.

5

実験と考察

British National Corpus (BNC) [5] を使って実験を行った. BNC はトピックが限定される WSJ 等と異なり, 様々なトピックが含まれるバランスドコーパス
であり, このような実験に適している.
実験には BNC の Written テキスト 3,043 ファイルのうち, ランダムに選んだ 100 ファイルを評価デー
タ, 残りを LDA/DM のパラメータ推定のための訓練データとした.
5.1

訓練データ

ただし, BNC のテキストは非常に長く (平均約 55,000語), そのままの長さでは LDA および DM のパラメータを求めることができない.7 提案手法は一文書に関するモデルであるものの, 原理的には文書集合にも対しても拡張可能と考えられるが8 , 本稿の範囲を超えるため, ここでは近似として, 予備実験により, モデ
ルの性能が低下しない最小のユニットとして 10 文9を採用し, 訓練セットの各テキストを 10 文毎に分割して文書としたものを訓練文書群とした.
ただし, BNC のデータは膨大であるため, 計算量の問題から, 訓練データのそれぞれのファイルを上記に従って分割し, 1 ファイルあたり最大 20 文書をランダムに抽出したものを最終的な訓練データとした. 最終的に, LDA/DM のパラメータ推定のための文書数は 56,939 文書, 11,032,233 語のデータとなっ
7 実際には, 50 文以上を 1 つのテキストとした場合にモデルが収束しなかった. これはテキストを 1 つの BOW とみなすテキス
トモデルが, 通常みられる, ある程度長い文書の集合に対しては無力という限界をもつことを示している.
8 この場合, ベータ分布のハイパーパラメータ (α, β) を経験ベ
イズ法により推定できると考えられる.
9 以下, 
..
 で区切られる BNC のセグメント (ほぼ 1
文に対応する) を「文」と呼ぶ.

表 3: 各テキストセットに対するパープレキシティ
表 1: LDA/DM 訓練データの詳細

BNC 文書ファイル
文書分割単位
文書総数
総語数
語彙数

2,943 ファイル
10 ≤ |d| < 20 文
56,939 文書
11,032,233 語
52,846 語 (頻度 ≥ 5)

Text
Raw
Slow
Fast
VFast

MSM
MSM
DM
LDA
–DM
–LDA
870.06 925.83 1028.04 1037.42
893.06 974.04 1047.08 1060.56
898.34 988.26 1044.56 1061.01
960.26 1038.89 1065.15 1050.83

表 2: 評価用テキストの性質

Property
X = 100, Y = 0
1 ≤ X ≤ 10, 1 ≤ Y ≤ 3
1 ≤ X ≤ 10, 1 ≤ Y ≤ 10
X = 1, 1 ≤ Y ≤ 10

た. これは BNC 全体の約 1/10 に相当する. 語彙は
頻度 5 以上の 52,846 語である. 以上のデータを表 1にまとめる.

40
Documents

Name
Raw
Slow
Fast
VeryFast

30
20
10
0
-400 -300 -200 -100 0 100 200 300
Perplexity reduction

図 5: Dirichlet Mixture に対する, 評価データの各文
書のパープレキシティ減少 (PPLMSM − PPLDM ).

MSM-LDA においては精度上昇はわずかであるが,MSM-DM においては常にパープレキシティが減少
提案手法は, 文書内の文脈の動的な変化をとらえるモ しており, 文脈長を適応的に選択する効果があること
デルであり, 変化の速度自体も事後分布としてオンラ がわかる.
図 5 に MSM-DM の, ‘Raw’ セットの各文書に対インで求めつつ, 予測語の推定を行うものである.
するパープレキシティ減少のプロットを示す. ほと
この評価のためには, 様々な速度で変化するテキス
トが必要となるが, ここでは [20] にならい, 長いテキ んどの文書で効果があり, DM に比較して最大 400 程
ストから間隔を変化させてサンプリングを行うこと 度パープレキシティが減少していることがわかる.
ただし実際には, 単語ごとに変化点をサンプルしてで 4 種類の評価テキストを作成した. 手順は [20] といるために, 提案法はノイズに比較的弱く, 時によっほぼ同様であり, 以下のように行う.
(1) 各テキストに対し, 最初の文をランダムに選ぶ. て単語のパープレキシティが著しく (1000 倍程度) 増
加する場合がある. これが図 5 にみえるほどの全体(2) その文から, 連続する X 文を採取する.
の精度上昇を生まない原因となっている.
(3) Y 文だけスキップする.
この問題を解決するためには, 変化点を単語ごと(4) 求める文数のテキストが得られるまで, (2)(3) をではなく, 文ごとなどに取ることが考えられるが10 ,繰り返す.
上記手順において, X, Y は表 2 に従う乱数である. テキストの生成モデルとしての単位は単語単位であ
この手順にしたがい, 種類毎に評価セットの各文書に り, PF において複数の観測値をまとめて扱うことのついて 100 文をサンプルし, 評価用テキストとした. できる方法は見つかっていない. [16]最後に, 評価テキストの一つの最初の 1000 語に対
5.3 実験設定
する, MSM-DM の文脈変化確率 It のプロットを図
LDA および DM のパラメータ推定においては, そ に示す. 横軸が時間, 縦軸が粒子である. これからわ
れぞれクラス数を DM=50, LDA=200 とした. これ かるように, 本手法は補助的に, TextTiling[12] のは, 現在の Dirichlet Mixture の実装がハイパーパラ 確率化を行うものともとらえることができる.
メータに関して最尤推定になっているため, 混合数が6 まとめ
少ない方が高い性能を持つからである [22].
文脈変化率を表すベータ分布の事前パラメータは,
本論文では, Mean Shift Model を DM および LDA
原理的には一様分布 (α, β) = (1, 1) としてよいが, こによって拡張し, 文脈の変化点を動的にとらえる言語
こでは予備実験の結果から, (α, β) = (1, 50) とした.
モデルを提案した. 各粒子によってサンプルされた
5.2

評価データ

5.4

実験結果

様々な長さの履歴からの予測を混合することで, 文脈をとらえた安定した予測が行われる. 提案モデルは

表 3 に, 各評価テキストセットに対する MSM-LDA,
10 単純に文の各語の確率の積を用いると, 式 (17) において二つMSM-DM, LDA, DM のユニグラムパープレキシティ の確率の差がきわめて大きくなってしまい, 変化点として 0 またを示す.
は 1 がほぼ確定的にサンプルされてしまう.

0.4
0.35
0.3
0.25

20

0.2
15
0.15
0.1

10

0.05
5

0
1000

900

800

700

600

500

400

300

200

100

0
0

Forward モデルであり, これを Forward-Backward
および文書集合へ適用することは今後の課題である.
謝辞: 本研究は独立行政法人 情報通信研究機構の研究委託により実施したものである。

参考文献[1] Doug Beeferman, Adam Berger, and John Lafferty. A Model of Lexical Attraction and Repulsion. In Proc. of ACL-EACL ’97, pages
373–380, 1997.
[2] Jerome R. Bellegarda. A Multispan Language Modeling Framework for Large Vocabulary Speech Recognition. IEEE Transactions
on Speech and Audio Processing, 6(5):468–475,
1998.
[3] David Blei and Pedro Moreno. Topic Segmentation with an Aspect Hidden Markov Model.
In Proc. of SIGIR 2001, pages 343–348. ACM
Press, 2001.
[4] David M. Blei, Andrew Y. Ng, and Michael I.
Jordan. Latent Dirichlet Allocation. Journal of
Machine Learning Research, 3:993–1022, 2003.
[5] Gavin Burnage and Dominic Dunlop. Encoding the British National Corpus. English Language Corpora: Design, Analysis and Exploitation, pages 79–95, 1992.
[6] Yuguo Chen and Tze Leung Lai. Sequential Monte Carlo Methods for Filtering andSmoothing in Hidden Markov Models. Discussion Paper 03-19, Institute of Statistics andDecision Sciences, Duke University, 2003.
[7] H. Chernoﬀ and S. Zacks. Estimating the Current Mean of a Normal Distribution Which is
Subject to Changes in Time. Annals of Mathematical Statistics, 35:999–1018, 1964.
[8] Arnaud Doucet. On Sequential SimulationBased Methods for Bayesian Filtering. Technical Report CUED/F-INFENG/TR 310, Department of Engineering, Cambridge University, 1998.
[9] Arnaud Doucet, Nando de Freitas, and Neil
Gordon. Sequential Monte Carlo Methods inPractice. Statistics for Engineering and Information Science. Springer-Verlag, 2001.
[10] Daniel Gildea and Thomas Hofmann. Topicbased Language Models Using EM. In Proc. of
EUROSPEECH ’99, pages 2167–2170, 1999.
[11] W. R. Gilks, S. Richardson, and D. J. Spiegelhalter. Markov Chain Monte Carlo in Practice.
Chapman & Hall / CRC, 1996.
[12] Marti Hearst. Multi-paragraph segmentationof expository text. In 32nd. Annual Meeting of
the Association for Computational Linguistics,
pages 9–16, 1994.
[13] Thomas Hofmann. Probabilistic Latent Semantic Indexing. In Proc. of SIGIR ’99, pages
50–57, 1999.
[14] Frederick Jelinek.
Statistical Methods for
Speech Recognition. Language, Speech, andCommunication Series. MIT Press, 1998.
[15] Sadao Kurohashi and Manabu Ori. Nonlocal Language Modeling based on Co-occurence
Vectors. In Proc. of EMNLP/VLC ’00, pages
80–86, 2000.
[16] Cody Kwok, Dieter Fox, and Marina Meilǎ.
Real-time Particle Filters. In Advances in Neural Information Processing Systems 15, 2002.
[17] Peter M. Lee. Bayesian Statistics: An Introduction. Arnold Publishers, Second edition,
1997.
[18] Philippe Sollers. H. Seuil (1 mars 1973) edition, 1973.
[19] Yi-Chin Yao. Estimation of a noisy discretetime step function: Bayes and empirical Bayes
approaches. Annals of Statistics, 12:1434–
1447, 1984.
[20] 高橋 力矢, 峯松 信明, 広瀬 啓吉. 文脈適応による複数 N-gram の動的補間を用いた言語モデ
ル. 情報処理学会研究報告 2003-NL-155, pages
107–112, 2003.
[21] 三品 拓也, 山本 幹雄. 確率的 LSA に基づくngram モデルの変分ベイズ学習を利用した文脈適応化. 信学技報 NLC2002-73, pages 13–18,
2002.
[22] 山本 幹雄, 貞光 九月, 三品 拓也. 混合ディリ
クレ分布を用いた文脈のモデル化と言語モデルへの応用. 情報処理学会研究報告 2003-SLP-48,
pages 29–34, 2003.
[23] 貞光 九月, 待鳥 裕介, 山本 幹雄. 混合ディリク
レ分布パラメータの階層ベイズモデルを用いた
スムージング法. 情報処理学会研究報告 2004SLP-53, pages 1–6, 2004.