SLC Internal tutorial Daichi Mochihashi daichi.mochihashi@atr.jp ATR SLC 2005.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)logf(x)dx. (2) KL D(p q) = p(x)log p(x) dx 0. (3) q(x) p = q. Variational Bayesian methods for Natural Language Processing p.4/30
: D, p(d) = p(d, θ)dθ (4) = p(d θ)p(θ)dθ. (5) p(d θ),p(θ) : ( ) θ : : D, p(θ D). p(θ D) p(θ, D) =p(d θ)p(θ). (6) θ D 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) (6) θ = ˆθ z. EM. z D Variational Bayesian methods for Natural Language Processing p.7/30
EM (1) Jensen, log p(d θ) = log p(d, z θ)dz (10) p(d, z θ) =log q(z D, ˆθ) dz (11) q(z D, ˆθ) p(d, z θ) q(z D, ˆθ)log dz = F (q(z),θ) (12) q(z D, ˆθ), F (q(z),θ). E step: M step: q(z) = arg max q(z) ˆθ =argmax θ F (q(z),θ), (13) F (q(z),θ). (14) Variational Bayesian methods for Natural Language Processing p.8/30
EM (2) E step F (q(z),θ)= = = q(z D, q(z D, q(z D, p(d, z θ) ˆθ)log dz (15) q(z D, ˆθ) ˆθ)log p(z D, θ)p(d θ) q(z D, ˆθ) dz (16) q(z D, ˆθ) ˆθ)log dz +logp(d θ) (17) p(z D, θ) = D(q(z D, ˆθ) p(z D, θ)) +logp(d θ) (18) q(z D, ˆθ) =p(z D, θ) (19) (E ). Variational Bayesian methods for Natural Language Processing p.9/30
EM (3) M step F (q(z),θ)= q(z D, p(d, z θ) ˆθ)log dz (20) q(z D, ˆθ) = log p(d, z θ) q(z D,ˆθ) + H(q(z D, ˆθ)) (21), F (q(z),θ) θ,, Q(θ) = log p(d, z θ) q(z D,ˆθ) (Q ) (22) Q(θ) θ =0 (23) θ ˆθ. (M ) Variational Bayesian methods for Natural Language Processing p.10/30
EM ( ) log p(d θ) F (q(z),θ)= q(z D, p(d, z θ) ˆθ)log dz (24) q(z D, ˆθ), F (q(z),θ) q(z),θ (EM )., log p(d θ) F (q(z),θ) (25) = q(z D, ˆθ)logp(D θ)dz p(d, z θ) q(z D, ˆθ)log dz (26) q(z D, ˆθ) q(z D, ˆθ) = q(z D, ˆθ)log dz (27) p(z D, θ) = D(q(z D, ˆθ) p(z D, θ)) 0. (28) 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(d z). d z w = w 1 w 2 w n W = {w 1, w 2,...,w D }, D = {1, 2,...,D}, p(z) p(w z) p(d,w,z)= p(d, w d, z d ) (30) d = p(d, w dn,z dn ) (31) d n = p(z dn )p(d z dn )p(w dn z dn ) (32) d n [ log p(zdn )+log p(d z dn )+log p(w dn z dn ) ]. w log p(d,w,z)= d 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 ) (34) = d [ p(z d, w dn )logp(z dn ) n z + z + z p(z d, w dn )logp(d z dn ) ] p(z d, w dn )logp(w dn z dn ). (35) δq/δθ, δq δp(z) = d p(z) d n p(z d, w dn) p(z) p(z d, w dn ) n d + λ =0 (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) n p(z d, w dn ) w n(d, w)p(z d, w) (38) p(w z) d p(z d, w dn ) n d n(d, w)p(z d, w). (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) (26) z,θ p(z D),p(θ D). p(d, z, θ) log p(d) = log q(z,θ D) q(z,θ D) p(d, z, θ) q(z,θ D)log q(z,θ D) θ z D dzdθ (44) dzdθ (45) z,θ, q(z,θ D) =q(z)q(θ) (46), Variational Bayesian methods for Natural Language Processing p.16/30
log p(d) = q(z,θ D)log q(z)q(θ)log p(d, z, θ) q(z,θ D) dzdθ (47) p(d, zθ) dzdθ (48) q(z)q(θ) = F (q). ( ) (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)q(θ)log ) q(z)dz 1 ( p(d, z, θ) q(z)q(θ) dzdθ + λ ) q(z)dz 1 q(θ) [ log p(d, z, θ) log q(θ) log q(z) 1 ] dzdθ + λ (50), q(θ) [ log p(d, z θ)+logp(θ) log q(θ) log q(z) 1 ] dzdθ + λ = log p(d, z θ) q(θ) log q(z)+(const.)+λ =0 (51) 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(z)q(θ)log ) q(θ)dθ 1 ( p(d, z, θ) q(z)q(θ) dzdθ + λ ) q(θ)dθ 1 q(z) [ log p(d, z, θ) log q(θ) log q(z) 1 ] dzdθ + λ (53) (54) q(z) [ log p(d, z θ)+logp(θ) log q(θ) log q(z) 1 ] dzdθ + λ = log p(d, z θ) +logp(θ) log q(θ)+(const.)+λ =0 q(z) (55) q(θ) p(θ)exp log p(d, z θ) q(z). (56) Variational Bayesian methods for Natural Language Processing p.19/30
D, z, θ,. log p(d) = log p(d, z, θ)dzdθ (57) p(d, z, θ) q(z)q(θ)log dzdθ = F (q). q(z)q(θ) (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) = q(z,θ)logp(d)dzdθ = = log p(d) F (q). (64) q(z,θ)log p(d, z, θ) q(z,θ) (65) dzdθ (66) q(z,θ) [ log p(d) log p(z,θ D) log p(d)+logq(z,θ) ] dzdθ q(z,θ)log q(z,θ) p(z,θ D) (67) dzdθ (68) = D(q(z,θ) p(z,θ D)) 0. (69), q(z,θ) =q(z)q(θ). Variational Bayesian methods for Natural Language Processing p.22/30
(3) F (q) = ( = = = log log log q(z)q(θ)log p(d, z, θ) q(z)q(θ) p(d, z θ) p(θ) q(z)q(θ)log q(z) q(θ) p(d, z θ) q(z) p(d, z θ) q(z) p(d, z θ) q(z) q(z)q(θ) dzdθ (70) dzdθ (71) q(θ)log q(θ) dθ (72) p(θ) D(q(θ D) p(θ)) q(z)q(θ) }{{} ( ) q(z)q(θ) ˆθ 2 log N }{{} MDL, BIC +logp(ˆθ) }{{} (const.) KL,. ) (73) (74) 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 w N, D θ ( ) : β = p(w z), p(w α, β) = p(θ α) n p(θ) Dir(θ α) (76) p(w n θ, β)dθ (77) = Γ( k α k) k Γ(α k). k θ α k 1 k (θ z β zv ) wv n dθ n z v (78) Variational Bayesian methods for Natural Language Processing p.25/30
: LDA (2) log p(w α, β) = log p(w,z,θ α, β)dθ (79) z =log z p(w,z,θ α, β) q(z,θ γ,ψ) dθ (80) q(z,θ γ,ψ) q(z,θ γ,ψ)log z p(w,z,θ α, β) q(z,θ γ,ψ) q(z,θ w,γ,ψ)=q(θ γ) n q(z n w n,ψ), dθ (81) log p(w α, β) log p(θ α) q(θ γ) + n log p(zn θ) q(θ γ),q(z n w n,ψ) log p(wn z n,β) q(z n w n,ψ) + n log q(θ γ) q(θ γ) n log q(zn w n,ψ) q(z n w n,ψ). (82) Variational Bayesian methods for Natural Language Processing p.26/30
VB-HMM y = y 1 y 2 y T, s = s 1 s 2 s T, HMM π (1 K) C (K K) A (K W ) log p(y) =log dπ dπ da da dc s dc s p(π, A, C)p(y, s π, A, C) (83) q(π, A, C, s) log p(π, A, C)p(y, s π, A, C) 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 α k )) (85) A ij exp ( Ψ(β ij) Ψ( j β ij) ) (86) C ij exp ( Ψ(γij) Ψ( γij) ) (87) j VB-Mstep: α, β, γ α,β,γ 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 for Graphical Models. In NIPS 1999, 1999. Thomas Minka. Expectation-Maximization as lower bound maximization, 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 other Variants. 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