SLC Internal tutorial

自然言語処理のための変分ベイズ法
Daichi Mochihashi
daichi.mochihashi@atr.jp
ATR SLC2005.6.21 (Tue)13:15–15:00@Meeting Room 1

Variational Bayesian methods for Natural Language Processing – p.1/30

変分ベイズ法とは?
• 確率モデルのベイズ推定を行うための近似解法◦ 最尤推定 (EM) と違い, 過学習を自動的に防ぐ◦ 最尤推定が不可能な, 複雑な確率モデル◦ 通常の EM アルゴリズムの自然な拡張• どこで使われているか?
◦ 音声認識 (實廣, 中村 2004/渡辺他 2002)◦ 混合 von Mises-Fisher 分布 (田辺他 2004)◦ HMM (MacKay 1997)◦ LDA (Blei et al. 2001)◦ PCFG (栗原他 2004)◦ ...

Variational Bayesian methods for Natural Language Processing – p.2/30

アウトライン• ベイズ推定と最尤推定• 最尤推定と EM アルゴリズム• 変分ベイズ推定と VB-EM アルゴリズム• 変分ベイズ推定の性質• 自然言語処理への応用◦ LDA◦ VB-HMM• ベイズ推定のためのその他の解法

Variational Bayesian methods for Natural Language Processing – p.3/30

準備: 不等式• Jensen の不等式
◦ 上に凸な関数 f (x) について,f (E[x]) ≥ E[f (x)](1)

◦ log(x) は上に凸なので, x = f (x) として

log

p(x)f (x)dx ≥p(x) log f (x)dx .

(2)• KL ダイバージェンスD(p||q) =p(x)dx ≥ 0 .
p(x) logq(x)(3)◦ p = q のときに等号成立.

Variational Bayesian methods for Natural Language Processing – p.4/30

準備: 確率モデル• D をデータとすると,

p(D) =p(D, θ)dθ(4)p(D|θ)p(θ)dθ.

(5)

=

θDp(D|θ), p(θ) : 確率モデル (生成モデル)
θ : 確率モデルのパラメータ• 目標: データ D が与えられたとき, p(θ|D) を推定すること.

p(θ|D) ∝ p(θ, D) = p(D|θ)p(θ) .

(6)

Variational Bayesian methods for Natural Language Processing – p.5/30

ベイズ推定と最尤推定
p(θ|D) がわかれば, 新しいデータ d の予測は
• ベイズ推定p(d|D) =p(d|θ)p(θ|D)dθ .

(7)◦ p(d|θ) : 確率モデルの適用◦ p(θ|D) : パラメータ θ の確率分布で期待値をとる.
• 最尤推定p(d|D) = p(d|θ̂).

(8)◦ θ = θ̂ と点推定した確率モデル◦ p(θ|D) = δ(θ̂) と δ 関数で近似してしまう◦ p(θ|D) が実際はなだらかな時, 偏った推定になる

Variational Bayesian methods for Natural Language Processing – p.6/30

最尤推定• データ D と隠れ変数 z があるとき,

p(D|θ) =p(D, z|θ)dz → 最大化.

(9)zD(6) を最大化する θ = θ̂ と隠れ変数 z を求める.
• これを解く方法→ EM アルゴリズム.

Variational Bayesian methods for Natural Language Processing – p.7/30

EM アルゴリズム (1)• Jensen の不等式を用いると,

log p(D|θ) = log

p(D, z|θ)dz


= log

q(z|D, θ̂)≥q(z|D, θ̂) log(10)p(D, z|θ)q(z|D, θ̂)p(D, z|θ)q(z|D, θ̂)

dz

(11)

dz = F (q(z), θ)(12)• よって, 下限 F (q(z), θ) を交互に最大化すればよい.
E step:q(z) = arg max F (q(z), θ) ,(13)θ̂ = arg max F (q(z), θ) .

(14)

q(z)

M step:θ

Variational Bayesian methods for Natural Language Processing – p.8/30

EM アルゴリズム (2)• E stepF (q(z), θ) =q(z|D, θ̂) log
=q(z|D, θ̂) log
=−はp(D, z|θ)dz

q(z|D, θ̂)p(z|D, θ)p(D|θ)
q(z|D, θ̂)

(15)

dz

(16)

q(z|D, θ̂)
dz + log p(D|θ) (17)q(z|D, θ̂) log
p(z|D, θ)= −D(q(z|D, θ̂)||p(z|D, θ)) + log p(D|θ)(18)

q(z|D, θ̂) = p(z|D, θ)(19)で最大 (E ステップ).

Variational Bayesian methods for Natural Language Processing – p.9/30

EM アルゴリズム (3)• M stepF (q(z), θ) =q(z|D, θ̂) log
p(D, z|θ)q(z|D, θ̂)dz
= log p(D, z|θ) q(z|D,θ̂) + H(q(z|D, θ̂))

(20)
(21)

よって, F (q(z), θ) を θ について最大化するには,Q(θ) = log p(D, z|θ) q(z|D,θ̂)
に対して,(Q 関数)

∂Q(θ)
=0
∂θ

(22)

(23)

を解いた θ を新しい θ̂ とすればよい. (M ステップ)

Variational Bayesian methods for Natural Language Processing – p.10/30

EM アルゴリズム (まとめ)log p(D|θ) ≥ F (q(z), θ) =q(z|D, θ̂) logp(D, z|θ)q(z|D, θ̂)

dz

(24)

として, 下限 F (q(z), θ) を q(z), θ について順に最大化する(EM アルゴリズム).
ここで左辺と右辺の差は,log p(D|θ) − F (q(z), θ)p(D, z|θ)= q(z|D, θ̂) log p(D|θ)dz − q(z|D, θ̂) log
dzq(z|D, θ̂)q(z|D, θ̂)dz= q(z|D, θ̂) logp(z|D, θ)(25)= D(q(z|D, θ̂)||p(z|D, θ)) ≥ 0 .

(28)

(26)
(27)

この KL ダイバージェンスを最小化していることに相当.
Variational Bayesian methods for Natural Language Processing – p.11/30

Example: PLSI (1/3)• ある単語 w が文書 d で生起したとき, 隠れ変数 z があってp(d, w, z) = p(z)p(d|z)p(w|z)と分解できたと仮定する.

(29)

p(z)
p(d|z) p(w|z)

dz• 文書 w = w1 w2 · · · wn の集合 W = {w1 , w2 , . . . , wD },文書のインデックス集合 D = {1, 2, . . . , D} について,
p(D, W, Z) =p(d, wd , zd )d =p(d, wdn , zdn )nd =p(zdn )p(d|zdn )p(wdn |zdn )nd∴ log p(D, W, Z) = dw

(30)
(31)
(32)

log p(zdn )+log p(d|zdn )+log p(wdn |zdn ) .

n(33)Variational Bayesian methods for Natural Language Processing – p.12/30

Example: PLSI (2/3)
• Q 関数 log p(D, z|θ)を計算すると,p(z|D,θ)
Q(z) = log p(D, W, Z) p(Z|D,W ) =p(z|d, wdn ) log p(zdn )nzd
p(z|d, wdn ) log p(d|zdn )+z+p(z|d, wdn ) log p(wdn |zdn ) .
• δQ/δθ を計算すると,

δQ=δp(z)∴ p(z) ∝dn(35)zn p(z|d, wdn )d(34)p(z)+λ=0p(z|d, wdn ) ∝d(36)n(d, w)p(z|d, w) (37)w
Variational Bayesian methods for Natural Language Processing – p.13/30

Example: PLSI (3/3)• 同様にして,p(d|z) ∝p(z|d, wdn ) ∝np(w|z) ∝
• ここで

d
w

p(z|d, wdn ) ∝n(d, w)p(z|d, w)
nn(d, w)p(z|d, w) .

(38)

d(39)

p(z|d, w) ∝ p(z, d, w) = p(z)p(d|z)p(w|z) .

(40)• この場合, 文書 d ごとにパラメータθ(d) = p(z|d)(41)∝ p(z)p(d|z)(42)

を点推定していることに相当する.
Variational Bayesian methods for Natural Language Processing – p.14/30

EM アルゴリズムの欠点• θ は given, 点推定• 隠れ変数 z が 1 層だけある場合にしか適用不可能• 過学習してしまう (z はバラバラ).

↓ベイズ推定.

Variational Bayesian methods for Natural Language Processing – p.15/30

ベイズ推定p(D) =p(D, z, θ)dzdθ → 最大化. (43)zD(26) を最大化する z, θ の確率分布 p(z|D), p(θ|D) を求める
ことが目標.
p(D, z, θ)dzdθ
log p(D) = log
q(z, θ|D)q(z, θ|D)p(D, z, θ)dzdθ
≥q(z, θ|D) log
q(z, θ|D)

(44)θ

(45)

この下限はそのままでは z, θ のそれぞれに対して最大化できないので,q(z, θ|D) = q(z)q(θ)(46)という因子分解を仮定すると,
Variational Bayesian methods for Natural Language Processing – p.16/30

変分ベイズ推定
p(D, z, θ)dzdθ
log p(D) ≥q(z, θ|D) log
q(z, θ|D)p(D, zθ)dzdθ=q(z)q(θ) log
q(z)q(θ)= F (q).

(変分自由エネルギー)

(47)

(48)
(49)

この下限 (変分下限, variational lower bound) F (q) は q(z), q(θ) について逐次最大化できる.

Variational Bayesian methods for Natural Language Processing – p.17/30

Maximize w.r.t. q(z)L = F (q) + λ=δL=δq(z)

q(z)dz − 1p(D, z, θ)dzdθ + λq(z)q(θ) logq(z)q(θ)(50)

q(z)dz − 1とおくと,q(θ) log p(D, z, θ) − log q(θ) − log q(z) − 1 dzdθ + λ=q(θ) log p(D, z|θ) + log p(θ) − log q(θ) − log q(z) − 1 dzdθ + λ
(51)= log p(D, z|θ) q(θ) − log q(z) + (const.) + λ = 0∴ q(z) ∝ exp log p(D, z|θ) q(θ) .

(52)

Variational Bayesian methods for Natural Language Processing – p.18/30

Maximize w.r.t. q(θ)
L = F (q) + λ

=δL
=
δq(θ)

q(θ)dθ − 1p(D, z, θ)dzdθ + λq(z)q(θ) logq(z)q(θ)(53)

q(θ)dθ − 1(54)q(z) log p(D, z, θ) − log q(θ) − log q(z) − 1 dzdθ + λ=q(z) log p(D, z|θ) + log p(θ) − log q(θ) − log q(z) − 1 dzdθ + λ= log p(D, z|θ) q(z) + log p(θ) − log q(θ) + (const.) + λ = 0
∴ q(θ) ∝ p(θ) exp log p(D, z|θ) q(z) .

(55)
(56)

Variational Bayesian methods for Natural Language Processing – p.19/30

変分ベイズ推定のまとめ• 観測データ D に対して, 隠れ変数 z , パラメータ θ をすべて確率変数とみて, その確率分布を求める.
log p(D) = log
p(D, z, θ)dzdθ
p(D, z, θ)dzdθ = F (q).
≥q(z)q(θ) log
q(z)q(θ)

(57)
(58)

• F (q) を q(z), q(θ) に関して最大化すると,

 q(z) ∝ exp log p(D, z|θ) q(θ)

 q(θ) ∝ p(θ) exp log p(D, z|θ)q(z)(VB-E step) (59)
(VB-M step) (60)

· · · VB-EM アルゴリズム.

Variational Bayesian methods for Natural Language Processing – p.20/30

変分ベイズ法について (1)• VB-EM アルゴリズム: q(z) ∝ exp log p(D, z|θ) q(θ)

 q(θ) ∝ p(θ) exp log p(D, z|θ)q(z)(VB-E step) (61)
(VB-M step) (62)q(θ) = δ(θ̂) のとき, (44) 式はq(z) ∝ p(D, z|θ̂) ∝ p(z|D, θ̂)(63)· · · EM アルゴリズムの E-step と同じ.

Variational Bayesian methods for Natural Language Processing – p.21/30

変分ベイズ法について (2)log p(D) ≥ F (q) .

(64)

ここで,log p(D) − F (q)
(65)

p(D, z, θ)dzdθ (66)=q(z, θ) log p(D)dzdθ −q(z, θ) logq(z, θ)=q(z, θ) log p(D) − log p(z, θ|D) − log p(D) + log q(z, θ) dzdθ(67)
q(z, θ)dzdθ
=q(z, θ) log(68)p(z, θ|D)= D(q(z, θ)||p(z, θ|D)) ≥ 0 .
(69)
この近似誤差をできるだけ小さくするように, q(z, θ) = q(z)q(θ) を最適化している.
Variational Bayesian methods for Natural Language Processing – p.22/30

変分ベイズ法について (3)p(D, z, θ)dzdθ
q(z)q(θ)
p(D, z|θ) p(θ)dzdθ=q(z)q(θ) log
q(z) q(θ)
p(D, z|θ)
q(θ)
dθ
= log
− q(θ) log
q(z)
p(θ)
q(z)q(θ)
p(D, z|θ)= log−D(q(θ|D)||p(θ))
q(z)q(z)q(θ)

F (q) =q(z)q(θ) log

→p(D, z|θ)
log
q(z)

(70)

(71)

(72)

(73)

過学習を防ぐ (正則化項)|θ̂|− log N + log p(θ̂)
q(z)q(θ) 2    MDL, BIC(74)(const.)• パラメータ事前分布と事後分布の KL ダイバージェンスで,自動的に正則化が行われる.
Variational Bayesian methods for Natural Language Processing – p.23/30

変分ベイズ法のまとめ (2)• 学習データの尤度の下限を, 変分近似して最大化する

log p(D) ≥ F (q) → 最大化.

(75)

◦ 左辺と右辺の差は KL ダイバージェンス (→ 最小化).
• δF/δq(z), δF/δq(θ) → VB-EM アルゴリズム.
◦ パラメータの確率分布 q(z), q(θ) が求まる (= 点推定)
◦ q(θ) が δ 関数のとき, 通常の EM アルゴリズムと一致• パラメータの過学習を防ぐ · · · パラメータの事前分布 p(θ) と事後分布 q(θ|D) との KL-ダイバージェンスで自動的に正則化• データ数 N → ∞ の極限で MDL/BIC と一致

Variational Bayesian methods for Natural Language Processing – p.24/30

応用: LDAβ• PLSI では文書 d について対応するパラメータ θ = p(z|d) を点推定αしたが, これは過学習する恐れがある

z

θwN

D

• θ 自体に確率を与える (ディリクレ分布) :p(θ) ∼ Dir(θ|α)(76)• β = p(w|z) とおくと,

p(w|α, β) =p(θ|α)

p(wn |θ, β)dθnΓ(= k αk )k Γ(αk )→ 最大化.

 kθkαk −1(77)nzvwn(θz βzv )

dθv

(78)

Variational Bayesian methods for Natural Language Processing – p.25/30

応用: LDA (2)log p(w|α, β) = log p(w, z, θ|α, β)dθ(79)p(w, z, θ|α, β)dθq(z, θ|γ, ψ)q(z, θ|γ, ψ)(80)p(w, z, θ|α, β)dθq(z, θ|γ, ψ) log
q(z, θ|γ, ψ)(81)

z= log≥  zz• q(z, θ|w, γ, ψ) = q(θ|γ)

n q(zn |wn , ψ) と近似すると,
log p(w|α, β) ≥ log p(θ|α) q(θ|γ) +log p(zn |θ) q(θ|γ),q(zn |wn ,ψ)n+log p(wn |zn , β) q(zn |wn ,ψ)n− log q(θ|γ) q(θ|γ) −log q(zn |wn , ψ) q(zn |wn ,ψ) .
n(82)
Variational Bayesian methods for Natural Language Processing – p.26/30

VB-HMM• 観測系列 y = y1 y2 · · · yT に対して, 隠れた真の状態系列

s = s1 s2 · · · sT があって,• HMM のパラメータ◦ 初期状態確率 π(1 × K)◦ 状態遷移行列 C (K × K)
◦ 出力確率行列 A (K × W ) についてlog p(y)p(π, A, C)p(y, s|π, A, C)= log dπ dA dC≥dπdAdC

s(83)

sp(π, A, C)p(y, s|π, A, C).
q(π, A, C, s) log
q(π, A, C, s)(84)

Variational Bayesian methods for Natural Language Processing – p.27/30

VB-HMM (2)• π ,C の各列, A の各列にそれぞれディリクレ事前分布

Dir(α), Dir(β), Dir(γ) を考えると,• VB-Estep:

πk
∗∗
∝ exp Ψ(αk ) − Ψ(αk )(85)kAij∗∗∝ exp Ψ(βij ) − Ψ(βij )(86)jCij∗∗∝ exp Ψ(γij ) − Ψ(γij )• VB-Mstep:(87)j◦ パラメータ α, β, γ の事後分布 α∗ , β ∗ , γ ∗ をForward-Backward から更新.
• 詳細は Beal, M.J. (2003) Variational Algorithms for

Approximate Bayesian Inference. PhD thesis, Gatsby UCL.
http://www.cse.buffalo.edu/faculty/mbeal/thesis/ Chapter.3.
Variational Bayesian methods for Natural Language Processing – p.28/30

ベイズ推定のための解法• 変分ベイズ法は, グラフィカルモデル (or, ベイジアンネットワーク) を解くための方法の一つ• Gibbs sampling, MCMC
◦ モデルから実際にサンプリングして, 平均を取る◦ 近似のない, 正確な推定が可能◦ 複雑なモデルでも, 多くの場合適用できる◦ 計算時間が長い (LDA の場合, 3 倍くらい (らしい))• EP (Expectation Propagation) (Minka 2001),

Power EP (Minka 2004)◦ VB とは別の解析的近似◦ EP … KL-ダイバージェンス最小◦ Power EP … α-ダイバージェンス最小

Variational Bayesian methods for Natural Language Processing – p.29/30

Readings• Hagai Attias. A Variational Bayesian Framework forGraphical Models. In NIPS 1999, 1999.
• Thomas Minka. Expectation-Maximization as lower boundmaximization, 1998.
http://research.microsoft.com/˜minka/papers/em.html.
• Radford M. Neal and Geoffrey E. Hinton. A View of the EM

Algorithm that Justifies Incremental, Sparse, and otherVariants. in Learning in Graphical Models, pages 355–368.
Dordrecht: Kluwer Academic Publishers, 1998.
• Zoubin Ghahramani. Unsupervised Learning. in Advanced

Lectures on Machine Learning LNAI 3176. Springer-Verlag,
Berlin, 2004.
http://www.gatsby.ucl.ac.uk/˜zoubin/course04/ul.pdf.

Variational Bayesian methods for Natural Language Processing – p.30/30