앞서 LDA 모델에 대해 설명했던 포스팅에 이어 이번 포스팅에서는 LDA 모델에 대한 parameter 추정 방법에 대해 이야기하고자 한다. LDA는 Gaussian Mixture 모델과 마찬가지로 latent variable을 이용해서 문서의 토픽(topic)을 결정짓는다. 토픽이 곧 하나의 군집(Cluster)와 같다고 보면 된다.

그림과 같이 LDA 모델은 3가지 parameter에 대한 값을 구해야한다. 따라서 Target Posterior Distribution은 3가지 paarameter \((z,\phi,\theta)\) 에 대한 내용을 담고 있어야할 것이다.

LDA

앞선 포스팅에서 정리한 Target Posterior Distribution에 대한 Factorization 결과를 가져온다.

\[\begin{align} p(z,\phi,\theta \vert w) &\propto p(z,\phi,\theta,w) \propto p(w\vert z,\phi)p(z\vert\theta)p(\phi)p(\theta) \nonumber \\ &\propto \prod_{d=1}^{D}\prod_{n=1}^{N_{d}}p(w_{n}^{(d)}\vert z_{n}^{(d)},\phi)\prod_{d=1}^{D}\prod_{n=1}^{N_{d}}p(z_{n}^{(d)}\vert\theta)\prod_{t=1}^{T}p(\phi^{(t)})\prod_{d=1}^{D}p(\theta^{(d)}) \nonumber \\ &\propto \prod_{d=1}^{D}\prod_{n=1}^{N_{d}}\prod_{t=1}^{T}\left(\prod_{m=1}^{M}(\phi_{m}^{(t)})^{I(w_{n}^{(d)}=m)}\right)^{I(z_{n}^{(d)}=t)} \nonumber \\ &\quad\prod_{d=1}^{D}\prod_{n=1}^{N_{d}}\prod_{t=1}^{T}(\theta^{(d)}_{t})^{I(z_{n}^{(d)}=t)}\prod_{t=1}^{T}\prod_{m=1}^{M}(\phi_{m}^{(t)})^{\beta-1}\prod_{d=1}^{D}\prod_{t=1}^{T}(\theta_{t}^{(d)})^{\alpha-1} \nonumber \end{align}\]

Target Posterior Distribution에 대한 parameter 추정을 위한 방법이 대표적으로 2가지 존재한다. 하나는 Gibbs Sampler이고 다른 하나는 Variational Inference이다. 이번 포스팅에서는 Gibbs Sampler, 그 중에서도 특히 Collapsed Gibbs Sampler를 이용해 parameter에 대한 추정을 진행해보도록 하겠다.

Concept of Collapsed Gibbs Sampler

Full-Conditional Gibbs Sampler 보다 효율적인 Gibbs Sampler를 진행하기 위해 Collapsing에 대해 알아두면 좋다. Sampling을 목표하는 parameter가 \((x_{1},x_{2},x_{3})\) 라면 다음의 Step으로 Gibbs Sampler를 진행했다.

\[p(x_{1}\vert x_{2},x{3})\quad\rightarrow\quad p(x_{2}\vert x_{1},x_{3})\quad\rightarrow\quad p(x_{3}\vert x_{1},x_{2})\]

Collasped Gibbs Sampler는 1,3번째 Sampling Step을 \(x_{2}\)에 대해 Marginalized하여 Sampling을 간결하게 바꾸어준다. 혹은 Marginalized의 결과 \(x_{2}\)에 대한 Sampling 자체가 필요 없어지는 상황이 발생할 수도 있게 된다.

\[p(x_{1}\vert x{3})\quad\rightarrow\quad p(x_{2}\vert x_{1},x_{3})\quad\rightarrow\quad p(x_{3}\vert x_{1})\]

LDA에서는 Collapsed Gibbs Sampler를 수식을 간결하게 만들기 위해 사용한다.

Collapsed Gibbs Sampler for LDA

Gibbs Sampler 수행을 위해 가장 먼저 Target Distribution \(p(z,\phi,\theta \vert w)\) 에 대한 Factorization을 수행한다.

\[p(\mathbf{z},\phi,\theta \vert \mathbf{w},\alpha,\beta) \propto \prod_{d=1}^{D}\prod_{n=1}^{N_{d}}p(w_{n}^{(d)}\vert z_{n}^{(d)},\phi^{(t)})\prod_{d=1}^{D}\prod_{n=1}^{N_{d}}p(z_{n}^{(d)}\vert\theta^{(d)})\prod_{t=1}^{T}p(\phi^{(t)}\vert \beta)\prod_{d=1}^{D}p(\theta^{(d)}\vert \alpha)\]

수식에서 \(\alpha,\beta\)는 Prior로 부여되는 값이고 단어 \(\mathbf{w}\)는 관측치이다. 여기서 \(\mathbf{\theta},\mathbf{\phi}\)에 대한 Marginalized를 시도하면 수식을 보다 간단하게 변형시킬 수 있으며, 이 결과 Collapsed Gibbs Sampler를 수행할 수 있게 된다.

\(\mathbf{\theta},\mathbf{\phi}\) 를 Marginalized한 수식은 다음과 같이 구할 수 있을 것이다. 이 수식은 target random variable \(\mathbf{z}\)에 대한 conditional distribution을 의미한다.

\[p(\mathbf{z} \vert \mathbf{w} \mathbf{\alpha},\mathbf{\beta}) = \int_{\mathbf{\theta}}\int_{\mathbf{\phi}}p(\mathbf{z},\mathbf{\phi},\mathbf{\theta}\vert \mathbf{w},\mathbf{\alpha},\mathbf{\beta})d\theta d\phi\]

이 수식에서 적분 기호 두의 수식에 Factorization 결과를 넣고 \(\theta\) 파트와 \(\phi\) 파트로 수식을 분리한다.

\[p(\mathbf{z} \vert \mathbf{w} \mathbf{\alpha},\mathbf{\beta}) = \int_{\phi} \prod_{t=1}^{T}p(\phi^{(t)}\vert \beta) \prod_{d=1}^{D}\prod_{n=1}^{N_{d}}p(w_{n}^{(d)}\vert z_{n}^{(d)},\phi^{(t)})d\phi \int_{\theta} \prod_{d=1}^{D}p(\theta^{(d)}\vert \alpha) \prod_{d=1}^{D}\prod_{n=1}^{N_{d}}p(z_{n}^{(d)}\vert\theta^{(d)})d\theta\]

이제 이 수식에서 적분을 직접 계산하지 않고 수식을 간단히 변형시킬 수 있는 방법을 고민해보자.

먼저 \(\phi\) 파트에 대한 적분을 처리하면 다음과 같다.

\[\int_{\phi} \prod_{t=1}^{T}p(\phi^{(t)}\vert \beta) \prod_{d=1}^{D}\prod_{n=1}^{N_{d}}p(w_{n}^{(d)}\vert z_{n}^{(d)},\phi^{(t)})d\phi = \prod_{t=1}^{T}\int_{\phi^{(t)}} \frac{\Gamma\left(\sum_{m=1}^{M}\beta_{m} \right)}{\prod_{m=1}^{M}\Gamma(\beta_{m})}\prod_{m=1}^{M}\left[\phi_{m}^{(t)}\right]^{\beta_{m}-1} \prod_{m=1}^{M}\left[\phi_{m}^{(t)}\right]^{\sum_{d=1}^{D}\sum_{n=1}^{N_{d}} I(w_{n}^{(d)}=n)I(z_{n}^{(d)}=t)}d\phi^{(t)}\]

이 수식에서 \(\phi_{m}^{(t)}\) 는 m번재 단어가 토픽 t에 할당된 횟수를 문서의 종류 관계 없이 집계하며 이러한 의도를 담은 수식은 \(\sum_{d=1}^{D}\sum_{n=1}^{N_{d}} I(w_{n}^{(d)}=n)I(z_{n}^{(d)}=t)\) 이다.

수식을 잘 살펴보면, \(\phi_{m}^{(t)}\) 에 대하여 다시 Dirichlet 형태의 Form으로 수식을 수정하는 것이 가능해보인다.

\[\begin{align} & \prod_{t=1}^{T}\int_{\phi^{(t)}} \frac{\Gamma\left(\sum_{m=1}^{M}\beta_{m} \right)}{\prod_{m=1}^{M}\Gamma(\beta_{m})}\prod_{m=1}^{M}\left[\phi_{m}^{(t)}\right]^{\beta_{m}-1} \prod_{m=1}^{M}\left[\phi_{m}^{(t)}\right]^{\sum_{d=1}^{D}\sum_{n=1}^{N_{d}} I(w_{n}^{(d)}=n)I(z_{n}^{(d)}=t)}d\phi^{(t)} \nonumber \\ &= \prod_{t=1}^{T}\frac{\Gamma\left(\sum_{m=1}^{M}\beta_{m}\right) \prod_{m=1}^{M}\Gamma\left(\beta_{m}+ \sum_{d=1}^{D}\sum_{n=1}^{N_{d}}I(w_{n}^{(d)}=m)I(z_{n}^{(d)}=t) \right)}{ \prod_{m=1}^{M}\Gamma(\beta_{m})\Gamma\left( \sum_{m=1}^{M} \left(\beta_{m}+ \sum_{d=1}^{D}\sum_{n=1}^{N_{d}}I(w_{n}^{(d)}=m)I(z_{n}^{(d)}=t) \right) \right) } \int_{\phi^{(t)}} \frac{\Gamma\left( \sum_{m=1}^{M} \left( \beta_{m}+ \sum_{d=1}^{D}\sum_{n=1}^{N_{d}}I(w_{n}^{(d)}=m)I(z_{n}^{(d)}=t) \right) \right) }{\prod_{m=1}^{M}\Gamma\left(\beta_{m}+ \sum_{d=1}^{D}\sum_{n=1}^{N_{d}}I(w_{n}^{(d)}=m)I(z_{n}^{(d)}=t) \right)} \left[\phi_{m}^{(t)} \right]^{\beta_{m}+\sum_{d=1}^{D}\sum_{n=1}^{N_{d}} I(w_{n}^{(d)}=n)I(z_{n}^{(d)}=t)-1} \nonumber \\ &= \prod_{t=1}^{T}\frac{\Gamma\left(\sum_{m=1}^{M}\beta_{m}\right) \prod_{m=1}^{M}\Gamma\left(\beta_{m}+ \sum_{d=1}^{D}\sum_{n=1}^{N_{d}}I(w_{n}^{(d)}=m)I(z_{n}^{(d)}=t) \right)}{ \prod_{m=1}^{M}\Gamma(\beta_{m})\Gamma\left( \sum_{m=1}^{M} \left( \beta_{m}+ \sum_{d=1}^{D}\sum_{n=1}^{N_{d}}I(w_{n}^{(d)}=m)I(z_{n}^{(d)}=t) \right) \right) } \nonumber \end{align}\]

\(\theta\)에 대해서도 동일한 방식으로 계산이 가능하다.

\[\int_{\theta} \prod_{d=1}^{D}p(\theta^{(d)}\vert \alpha) \prod_{d=1}^{D}\prod_{n=1}^{N_{d}}p(z_{n}^{(d)}\vert\theta^{(d)})d\theta = \prod_{d=1}^{D}\int_{\theta^{(d)}}\frac{ \Gamma \left( \sum_{t=1}^{T}\alpha_{t} \right) }{ \prod_{t=11}^{T}\Gamma(\alpha_{t}) } \prod_{t=1}^{T}\left[\theta_{t}^{(d)}\right]^{\alpha_{t}-1} \prod_{n=1}^{N_{d}}\left[\theta_{t}^{(d)} \right]^{\sum_{n=1}^{N_{d}}I(z_{n}^{(d)}=t)}\]

여기서 \(\theta_{t}^{(t)}\) 는 d번째 문서가 토픽 t에 할당될 확률을 의미한다. 이 수식에서는 문서 d에 존재하는 단어들이 토픽 t에 얼마나 할당되어있는가를 집계하고 이는 \(\sum_{n=1}^{N_{d}}I(z_{n}^{(d)}=t)\) 로 표현이 가능하다.

마찬가지로 이 수식도 \(\theta_{t}^{(d)}\) 에 대한 Dirichlet 형태의 Form으로 변형 가능하며 적분 기호 뒤의 파트는 1의 값을 갖게되어 사라진다.

\[\prod_{d=1}^{D}\int_{\theta^{(d)}}\frac{ \Gamma \left( \sum_{t=1}^{T}\alpha_{t} \right) }{ \prod_{t=11}^{T}\Gamma(\alpha_{t}) } \prod_{t=1}^{T}\left[\theta_{t}^{(d)}\right]^{\alpha_{t}-1} \prod_{n=1}^{N_{d}}\left[\theta_{t}^{(d)} \right]^{\sum_{n=1}^{N_{d}}I(z_{n}^{(d)}=t)} \nonumber \\ = \prod_{d=1}^{D}\frac{ \Gamma\left(\sum_{t=1}^{T}\alpha_{t} \right) \prod_{t=1}^{T}\Gamma\left( \alpha_{t}+\sum_{n=1}^{N_{d}}I(z_{n}^{(d)}=t) \right) }{ \prod_{t=1}^{T}\Gamma(\alpha_{t}) \Gamma \left( \sum_{t=1}^{T}\left(\alpha_{t}+\sum_{n=1}^{N_{d}}I(z_{n}^{(d)}=t)\right) \right)}\]

이 결과로 target Random Variable \(\mathbf{z}\)에 대한 conditional 분포는 \(p(\mathbf{z}\vert\mathbf{w},\alpha,\beta)\) 는 다음과 같이 다소 간단해진(?) 수식으로 표현이 가능하다.

\[p(\mathbf{z}\vert\mathbf{w},\alpha,\beta) = \prod_{t=1}^{T}\frac{\Gamma\left(\sum_{m=1}^{M}\beta_{m}\right) \prod_{m=1}^{M}\Gamma\left(\beta_{m}+ \sum_{d=1}^{D}\sum_{n=1}^{N_{d}}I(w_{n}^{(d)}=m)I(z_{n}^{(d)}=t) \right)}{ \prod_{m=1}^{M}\Gamma(\beta_{m})\Gamma\left( \sum_{m=1}^{M} \left( \beta_{m}+ \sum_{d=1}^{D}\sum_{n=1}^{N_{d}}I(w_{n}^{(d)}=m)I(z_{n}^{(d)}=t) \right) \right) } \times \prod_{d=1}^{D}\frac{ \Gamma\left(\sum_{t=1}^{T}\alpha_{t} \right) \prod_{t=1}^{T}\Gamma\left( \alpha_{t}+\sum_{n=1}^{N_{d}}I(z_{n}^{(d)}=t) \right) }{ \prod_{t=1}^{T}\Gamma(\alpha_{t}) \Gamma \left( \sum_{t=1}^{T}\left(\alpha_{t}+\sum_{n=1}^{N_{d}}I(z_{n}^{(d)}=t)\right) \right)}\]

수식에서 \(\mathbf{z}\)와 무관한 부분을 제외하면 보다 더 간단한 수식을 만들어낼 수 있다.

\[p(\mathbf{z}\vert\mathbf{w},\alpha,\beta) \propto \prod_{t=1}^{T} \frac{ \prod_{m=1}^{M}\Gamma\left(\beta_{m}+ \sum_{d=1}^{D}\sum_{n=1}^{N_{d}}I(w_{n}^{(d)}=m)I(z_{n}^{(d)}=t) \right) }{ \Gamma\left( \sum_{m=1}^{M} \left( \beta_{m}+ \sum_{d=1}^{D}\sum_{n=1}^{N_{d}}I(w_{n}^{(d)}=m)I(z_{n}^{(d)}=t) \right) \right) } \prod_{d=1}^{D}\frac{ \prod_{t=1}^{T}\Gamma\left( \alpha_{t}+\sum_{n=1}^{N_{d}}I(z_{n}^{(d)}=t) \right) }{ \Gamma \left( \sum_{t=1}^{T}\left(\alpha_{t}+\sum_{n=1}^{N_{d}}I(z_{n}^{(d)}=t)\right) \right) }\]

Gibbs Sampler는 \(\mathbf{z}\)의 elements를 하나씩 업데이트하는 과정이 되겠다. \(\mathbf{z}\)는 문서\((d)\) 별로 문서 안에서의 단어 별로 계속 값이 업데이트 되어야 할 것이다. 이러한 element 단위로 값을 업데이트 하기 위해서는 다른 모든 문서의 \(\mathbf{z}\)값이 동일한 상황에서 특정 d번째 문서, n번째 단어 \(z_{n}^{(d)}\) 의 토픽값 만이 sampling 되는 상황이 만들어져야 할 것이다.

\[p(z_{n}^{(d)}=t \vert z_{-n}^{(d)},\mathbf{w},\alpha,\beta) \propto p(z_{n}^{(d)}=t, z_{-n}^{(d)},\mathbf{w},\alpha,\beta)\]

\(n,d\)에 의해 \(t\)가 변화하는 것이 핵심이다. 따라서 \(n,d\)와 무관하면서 constant인 것을 제외시킬 수 있다. 여기서 n은 특정 문서 \(d\)에서의 n번째 단어이지만, 전체 문서 집합 \(M\) 관점에서는 \(m\)번째 unique 단어이다.

\[\begin{align} p(z_{n}^{(d)}=t, z_{-n}^{(d)},\mathbf{w},\alpha,\beta) &\propto \prod_{t=1}^{T} \frac{ \prod_{m=1}^{M}\Gamma\left(\beta_{m}+ \sum_{d=1}^{D}\sum_{n=1}^{N_{d}}I(w_{n}^{(d)}=m)I(z_{n}^{(d)}=t) \right) }{ \Gamma\left( \sum_{m=1}^{M} \left( \beta_{m}+ \sum_{d=1}^{D}\sum_{n=1}^{N_{d}}I(w_{n}^{(d)}=m)I(z_{n}^{(d)}=t) \right) \right) } \times \frac{ \prod_{t=1}^{T}\Gamma\left( \alpha_{t}+\sum_{n=1}^{N_{d}}I(z_{n}^{(d)}=t) \right) }{ \Gamma \left( \sum_{t=1}^{T}\left(\alpha_{t}+\sum_{n=1}^{N_{d}}I(z_{n}^{(d)}=t)\right) \right) }\quad \text{문서 d로 고정} \nonumber \\ &\propto \prod_{t=1}^{T} \frac{ \Gamma\left(\beta_{m}+ \sum_{d=1}^{D}\sum_{n=1}^{N_{d}}I(w_{n}^{(d)}=m)I(z_{n}^{(d)}=t) \right) }{ \Gamma\left( \sum_{m=1}^{M} \left( \beta_{m}+ \sum_{d=1}^{D}\sum_{n=1}^{N_{d}}I(w_{n}^{(d)}=m)I(z_{n}^{(d)}=t) \right) \right) } \times \frac{ \prod_{t=1}^{T}\Gamma\left( \alpha_{t}+\sum_{n=1}^{N_{d}}I(z_{n}^{(d)}=t) \right) }{ \Gamma \left( \sum_{t=1}^{T}\left(\alpha_{t}+\sum_{n=1}^{N_{d}}I(z_{n}^{(d)}=t)\right) \right) } \quad \text{단어 n 고정} \nonumber \\ &\propto \prod_{t=1}^{T} \frac{ \Gamma\left(\beta_{m}+ \sum_{d=1}^{D}\sum_{n=1}^{N_{d}}I(w_{n}^{(d)}=m)I(z_{n}^{(d)}=t) \right) }{ \Gamma\left( \sum_{m=1}^{M} \left( \beta_{m}+ \sum_{d=1}^{D}\sum_{n=1}^{N_{d}}I(w_{n}^{(d)}=m)I(z_{n}^{(d)}=t) \right) \right) } \times \prod_{t=1}^{T}\Gamma\left( \alpha_{t}+\sum_{n=1}^{N_{d}}I(z_{n}^{(d)}=t) \right) \nonumber \quad \text{Constant Term 제거} \end{align}\]

Sampling Step에서 d번째 문서의 n번째 단어에 대해 토픽 t를 할당하기 위해서 나머지 단어의 토픽 할당은 그대로 유지한 상태여야 한다. 이러한 관점까지 반영하여 수식을 한 번 더 깔끔하게 정리한다면, 다음과 같은 수식을 얻을 수 있다. 이 수식이 Gibbs Sampling을 위해 사용되는 간단한(?) 형태의 수식이다.

\[p(z_{n}^{(d)}=t \vert z_{-n}^{(d)},\mathbf{w},\alpha,\beta) \propto \frac{ \beta_{m}+ \sum_{d=1}^{D}\sum_{n=1}^{N_{d}}I(w_{-n}^{(d)}=m)I(z_{-n}^{(d)}=t) }{ \sum_{m=1}^{M} \left( \beta_{m}+ \sum_{d=1}^{D}\sum_{n=1}^{N_{d}}I(w_{-n}^{(d)}=m)I(z_{-n}^{(d)}=t) \right) } \times \left( \alpha_{t}+\sum_{n=1}^{N_{d}}I(z_{-n}^{(d)}=t) \right)\]

Gibbs Sampling 수행 과정에서 사용되는 이 수식의 의미는 현재 추출하고자 하는 문서 d의 n번째 단어 \(z_{n}^{(d)}\) 의 기존 토픽 할당 정보를 제외한 상태의 데이터를 바탕으로 추론을 하겠다는 것이다. Sampling을 진행하고자 하는 시점의 Sampling 대상 데이터 외 다른 데이터 값을 고정시키는 Gibbs Sampling의 아이디어가 여기에 활용되는 것이다.

Sampling 대상이 되는 \(z_{n}^{(d)}\) 의 기존 토픽 할당 정보를 제외한 나머지 데이터를 바탕으로 \(z_{n}^{(d)}\)가 어떤 토픽에 할당될지에 대한 확률을 계산할 수 있다. 토픽의 개수 T-dimensional의 벡터가 산출될 것이고 이 확률을 바탕으로 Multinomial 분포를 통해 토픽을 할당한다.

\[\text{np.random.multinomial}(1, p(z_{n}^{(d)}=t \vert z_{-n}^{(d)},\mathbf{w},\alpha,\beta))\]

이 결과를 통해 \(z_{n}^{(d)}\) 의 토픽 정보를 업데이트하고 이제 다음 \(z_{n+1}^{(d)}\) 의 토픽을 할당하기 위한 단계에선 \(z_{n}^{(d)}\) 의 바뀐 토픽 정보가 Gibbs Sampling Step에서 주어진 데이터 값으로 활용된다.

상기 내용에 대한 간략한 코드는 다음의 링크에서 확인 가능합니다.

참조 문헌

  1. Gibbs Sampling for LDA
  2. 단단한 머신러닝
  3. Collapsed Gibbs Sampler for LDA
  4. 토픽 모델링, LDA Python 코드