Probabilistic graphical models: Assignment 3 Seung-Hoon Na June 7, 207 Gibbs sampler for Beta-Binomial Binomial및 beta분포는 다음과 같이 정의된다. k Bin(n, θ): binomial distribution은 성공확률이 θ인 시도에서, n번 시행 중 k번 성공할 확률 분포로 을 따르는 랜덤 변수 (random variable)로 pmf (probability mass function)는 다음과 같다. Bin(k n, θ), n k θ ( θ)n k k () θ Beta(a, b): Beta distribution는 도메인이 구간 [0, ]인 분포로 다음과 같이 정의된다. Beta(θ a, b), θa ( θ)b B(a, b) (2) 여기서 θ는 구간 [0, ]에 속하는 원소이고, B(a, b)는 beta함수로 다음과 같이 정의된다. B(a, b) = Γ(a)Γ(b) Γ(a + b) (3) Beta-binomial는 binomial 분포의 parameter θ에 대한 prior로 beta분포를 취 하는 directed graphical model모델로 sampling 과정은 다음과 같다. θ Beta(a, b) k Bin(n, θ). Joint distribution for Beta-Binomial Beta-binomial의 joint distribution P (k, θ a, b, n) = Beta(θ a, b)bin(n, θ) 을 간 단히 정리하시오. P (k, θ a, b, n) = k는 어느 랜덤 변수 (random variable)의 값이며, 단순화를 위해 랜덤 변수는 생략하였다. 보다 엄 밀하게 random variable X가 주어질때, X Bin(n, θ)이면, 이에 대한 확률 분포는 Bin(X = k n, θ) 로 표기된다.
.2 Full conditionals for Beta-Binomial 위의 P (k, θ a, b, n)을 이용하여 Beta-Binomial의 full conditionals인 P (θ k, a, b, n) 과 P (k θ, a, b, n)을 유도하시오. P (θ k, a, b, n) = P (k θ, a, b, n) = (4).3 Gibbs sampling for Beta-Binomial 위의 full conditional distribution을 이용하여 marginal probability P (k a, b, n) = R P (k θ, a, b, n)p (θ a, b)dθ를 근사화시키는 Gibbs sampling algorithm 을 작성 0 하시오..4 Exact inference: Margin probability for Beta-Binomial θ에 해당되는 variable을 제거하여 P (k a, b, n) = 간략히 하시오..5 R 0 P (k θ, a, b, n)p (θ a, b)dθ를 Implementation: Gibbs sampling for Beta-Binomial (python code제출) 위에서 작성된 Gibbs sampling for Beta-Binomial을 python으로 구현하고 sample size를 500,n = 6으로 놓고, 다음의 a, b에 대해서 Exact inference결과와 Gibbs sampling으로 approximation된 결과를 비교하는 histograms을 보이시오. a = 2, b = 2일때 a = 2, b = 5일때 a =, b = 0일때 2 Gibbs sampler for Dirichlet-Multinomial Multimomial, Multimoulli, 및 Dirichlet분포는 다음과 같이 정의된다. x Mu(n, θ): color balls로 구성된 임의의 박스에서 2, θ = (θ,, θ ) 에서 θj 는 j번째 color ball를 추출할 확률을 의미할때, multinomial distribution은 n번의 시행 중, x = (x,, x )에서 xj 는 j번째 color ball이 추출된 횟수로 다음과 같이 정의된다. Mu(x n, θ), 2 는 n x x x θj j j= ball의 color종류의 수이고 박스에 있는 공의 갯수는 unknown이라 가정한다. 2 (5)
x Mu(, θ): Multimomial 분포에서 n = 인 특수한 경우로 categorical 또는 discrete distribution이라고도 하고, 다음과 같이 정의된다. Cat(x θ) = Mu(x, θ), x θj j (6) j= n P o θ Dir(α): 도메인이 probability simplex S = θ k= xk =, 0 θk 일때 Dirichlet distribution은 다음과 같이 정의된다. Dir(θ α), αk θk B(α) (7) k= 여기서 B(α)는 벡터로 일반화된 beta함수로 다음과 같이 정의된다. B(α) = Γ(α ) Γ(α ) Γ(α + + α ) (8) Dirichlet-multinomial (또는 Dirichlet Compound Multinomial)는 multinomial 분포의 parameter인 θ에 대한 prior로 Dirichlet분포를 취하는 directed graphical model모델로 sampling 과정은 다음과 같다. θ Dir(α) x Mu(n, θ) 2. Joint distribution for Dirichlet-Multinomial Dirichlet-Multinomial의 joint distribution P (x, θ α, n) = Dir(θ α)m u(x n, θ) 을 간단히 정리하시오. P (x, θ α, n) = 2.2 Full conditionals for Dirichlet-Multinomial 위의 P (x, θ α, n)을 이용하여 Dirichlet-Multinomial의 full conditionals인 P (θ x, α, n) 과 P (x θ, n)을 유도하시오. P (θ x, α, n) = P (x θ, n) = (9) 2.3 Gibbs sampling for Dirichlet-Multinomial 위의 full conditional distribution을 이용하여 marginal probability P (x α, n)를 근사화시키는 Gibbs sampling algorithm 을 작성하시오 (block sampling을 이용). 2.4 Exact inference: Margin probability for Dirichlet-Multinomial θ에 해당되는 variable을 제거하여 P (x α, n)에 대한 간략식을 유도하시오. 3
2.5 Implementation: Gibbs sampling for Dirichlet-Multinomial (python code제출) 위에서 작성된 Gibbs sampling for Dirichlet-Multinomial을 python으로 구현하고 sample size를 500, n = 6으로 놓고, 다음의 a에 대해서 Exact inference결과와 Gibbs sampling으로 approximation된 결과를 비교하시오. =3, α = (3, 3, 5) =3, α = (3, 0, 5) =5, α = (3, 5, 5, 8, 0) 3 Collapsed Gibbs sampler for Latent Dirichlet Allocation (LDA) Figure : A graphical model for LDA Figure 은 LDA에 대한 graphical model로, 토픽의 갯수가 이고, Nd 의 단어 로 구성된 문서 d를 generation하는 과정은 다음과 같다 3.. For i [,, ]: φi Dir(β) (i번째 토픽에 대한 Multinoulli parameter 를 생성한다.) 2. θ Dir(α) 3. For j [,, Nd ]: z j Cat(θ) wj Cat(φzj ) 표기를 간단히 하기 위해서, Φ = (φ,, φ )로 Φ를 -topic multinomial 파라미터로 사용하기로 한다. 주어진 문서 d에 대해, 단어열이 w로 주어지고, 이들 단어열에 대한 topic assignments가 z, topic mixture parameter가 θ, -topic multinomial 파라미터 Φ 에 대한, LDA의 joint distribution은 다음과 같다. 3 LDA에 대한 상세한 내용은 다음을 참고하시오. Blei, David M.; Ng, Andrew.; Jordan, Michael I. Latent Dirichlet Allocation. Journal of Machine Learning Research. 3 (4 5): pp. 993 022 4
P (w, z, θ, Φ α, β) = P (w, z, θ, φ α, β) = Dir(φi β)dir(θ α) i= Nd Cat(zj θ)cat(wj φzj ) j= M 개의 문서 전체 집합 C에 대해 단어열이 W = w wm, topic assignments 가 Z = z z M, topic mixture가 Θ = θ θ M 일때, C에 대한 LDA의 joint distribution는 다음과 같다. P (W, Z, Θ, Φ α, β) = P (w, z, θ M, φ α, β) = Dir(φi β) i= 3. M j= Ndj Dir(θ j α) Cat(zjk θ j )Cat(wjk φzjk ) k= Marginal distribution for Latent Dirichlet Allocation (LDA) LDA의 joint probability에서 θ, Φ를 elimination하여 다음 marginal probabilty P (w, z α, β)을 간결히 정리하시오. P (w, z α, β) = P (z α)p (w x, α, β) 여기서 P (z α)와 P (w x, α, β)는 다음과 같이 정의된다. Z P (z α) = P (θ α)p (z θ)dθ Z P (w z, β) = P (Φ β)p (w z, Φ)dΦ (0) 위를 이용하여, M 개의 문서 전체 집합 C에 대해 LDA의 marginal probabilty P (W, Z α, β)을 간결히 정리하시오. P (W, Z α, β) = P (Z α)p (W X, α, β) 3.2 Conditional probabliity on topic assignment for Latent Dirichlet Allocation (LDA) 위의 marginal probability P (w, z α, β)로부터 다음의 conditional probablity를 유도하시오. P (zj = i z j, w, α, β) = P (z j, zj = i, w, α, β) P (z j, w, α, β) () 여기서 z j 는 주어진 문서에서 j번째 단어를 제외한 다른 모든 단어들에 대한 topic assignment를 의미한다. 5
위의 하나의 문서에 대한 conditional probability식을 확장하여, M 개의 문서 전체 집합 C에 대한 다음 LDA의 conditional probabilty P (zjk = i W, Z jk α, β) 을 간결히 정리하시오. P (zjk = i Z jk, W, α, β) = P (Z jk, zjk = i, W, α, β) P (Z jk, W, α, β) (2) 여기서 Z jk 는 j번째 문서의 k번째 단어를 다른 모든 문서들과 단어들에 대한 topic assignment를 의미한다. 3.3 Collapsed Gibbs sampler for Latent Dirichlet Allocation (LDA) 위의 conditional probabliity 를 이용하여 모든 문서에 대해 topic assignment sampling을 수행한 후,θ j, φi 를 estimation하는 식을 유도하시오. 이를 이용하여 LDA에 대한 Gibbs sampler알고리즘을 유도하시오. 3.4 Implementation: Gibbs sampling for LDA (python code 제출) 유도된 Gibbs sampler를 python으로 작성하여 LDA 모델에 대한 학습을 수행하고, perplexity를 통해 LDA모델을 평가하시오. q(x) = Cat(x θ)가 학습된 Multinoulli 모델이고, 주어진 test 집합 T 은 총 M 개로 문서들로 구성되며, 이때 Ndi 를 문서 di 의 길이, wij 가 i번째 문서의 j번째 단어라고 할때, T 에 대한 model q의 perplexity는 다음과 같이 정의된다. Ndi M X X log q(wij ) perplexity(q) = exp M i= Ndi j= 6