이 포스트는 “Blei, D. M., Ng, A. Y., & Jordan, M. I. (2003). Latent dirichlet allocation. Journal of machine Learning research”를 공부하고, 요약 정리한 것이다.

1. Introduction

이 paper는 text corpora 혹은 다른 discrete data를 모델링하는 문제를 해결하고자 한다. 좀 더 구체적으로는, classification, novelty detection, summarization 등의 분석을 수행하기 위해 필요한 자료의 통계적 구조를 유지하면서, 자료의 어떤 collection 내의 멤버들에 대한 짧은 요약 및 설명을 찾아내는 것이 목표이다.

Latent Dirichlet Allocation, LDA는 “Bag-of-words” 가정에 기반한 분석 기법이다.

• Bag-of-words assumption : The order of the words in a document can be neglected. 즉, document 내의 단어들의 순서는 무시 가능하다.

확률론의 관점에서 보면 이는 document 내의 단어들에 대해 exchangeability 가정을 한 것이다. 또한 이에 더하여, document들 사이의 exchangeability, 즉 corpus 내 document의 특정 배열도 무시 가능하다는 점을 가정한다. De Finetti’s theorem에 의해, infinite exchangeable random variable들의 joint distribution은 어떤 iid sequence들의 distribution의 (infinite) mixture로 표현이 가능하다.

Let $(\mathfrak X, \mathcal X)$ be a Polish space and $\mu$ be a probability measure on $\mathfrak X^\infty$. Then $X_1, X_2, \cdots$ is exchangeable if and only if there is a unique probability measure $\Pi$ on $M(\mathfrak X)$ such that for all $n \in \mathbb N$ and for any Borel sets $B_1, B_2, \cdots , B_n$,

\[\mu( \{ X_1 \in B_1, \cdots X_n \in B_n \}) = \int_{M(\mathbb R)} \prod_{i=1}^{n} P(B_i) d \Pi(P)\]

따라서, 우리가 document들과 단어들의 exchangeable representation을 고려하고 싶다면, 우리의 모형은 document와 단어들의 exchangeability를 포착하는 mixture model을 담고 있어야 한다. 이 점을 반영한 모형이 Latent Dirichlet Allocation이다.

2. Notation and Terminology

Topic modeling이 LDA의 가장 주요한 적용분야이기 때문에, 이해의 편의를 위해 이 paper에서는 단어(words), 문서(documents), 말뭉치(corpora) 등과 같은 text collection의 용어들을 사용한다. 하지만 LDA는 collaborative filtering, content-based image retrieval, bioinformatics 등과 같은 다른 domain의 collections of data를 분석하는 데도 적용될 수 있다. 주요 용어 및 개념을 정의하면 다음과 같다.

• Word ($w$) : discrete data의 기본 단위. $V$개의 단어를 갖는 vocabulary의 한 원소로 정의된다. 또한 이 paper에서는 다음과 같은 $V$-vector로 단어를 나타낸다. Vocabulary의 $v$번째 단어, $w$는 다음과 같이 정의된다.

\[w = [w^1, \cdots , w^{v-1} , w^v , w^{v+1} ,\cdots, w^V] = [0, \cdots , 0 , 1 , 0 ,\cdots, 0]\]

• Document ($\mathbf w$) : word의 sequence.

\[\mathbf w = [w_1, w_2, \cdots, w_N]\]

• Corpus ($D$) : document의 collection.

\[D = \{ \mathbf w_1, \mathbf w_2, \cdots, \mathbf w_M \}\]

우리는 corpus의 member document, 그리고 member가 아니더라도 “유사한” 주제를 갖는 document에 높은 확률을 부여하는, corpus에 대한 probabilistic model을 만들고자 한다.

3. Latent Dirichlet Allocation

Latent Dirichlet Allocation(LDA)은 corpus에 대한 generative probabilistic model이다. 중심 idea는 다음과 같다.

• Topic이란 word들 위의 distribution(induced probability measure)로 정의된다. Document들은 이러한 latent topic들의 random mixture로 나타낼 수 있다.

LDA는 corpus $D$ 내의 각 document $\mathbf w$에 대해 다음과 같은 generative process를 가정한다.

1. Choose $N \sim \text{Poisson}(\xi)$.
2. Choose $\theta \sim \text{Dirichlet}(\alpha)$.
3. For each of the $N$ words $w_n$:
   • Choose a topic $z_n \sim \text{Multinomial}(\theta)$
   • Choose a word $w_n$ from $p(w_n \vert z_n, \beta)$, a multinomial probability conditioned on the topic $z_n$.

이 기본적인 모형은 자료에 대한 몇 가지 가정에 기반한 것이며, 그 가정 중 몇 가지는 이 paper의 후반부에서 완화한다.

• Dirichlet distribution의 차원 $k$, 즉 topic variable $z$가 가질 수 있는 값의 갯수는 알고 있으며 고정된 상수라고 가정한다.

\[z \in \Big\{ [1, 0 , \cdots, 0]^T, [0, 1 , \cdots, 0]^T, \cdots , [0, 0 , \cdots, 1]^T \Big\} \subset \mathbb R^k\]

• Word probability들은 $k \times V$ 행렬 $\beta$로 parametrize되며, 추정해야할 상수로 가정한다. $\beta_{ij}$는 $i$번째 topic일 때 $j$번째 word가 나올 확률을 의미한다.

\[\beta_{ij} = \text{Pr}(w^j = 1 \vert z^i = 1), \quad i = 1, \cdots, k, \text{ } j=1, \cdots, V\]

• Document의 길이를 나타내는 Poisson random variable $N$은 다른 data generating variable들($\theta, z$)과는 독립인 ancillary variable이다. 따라서 모형에 큰 영향을 끼치지 않으며, 상황에 따라 필요하다면 다른 더 현실적인 document length 분포를 사용할 수 있다. 그러므로 이후의 논리 전개를 소개할 때는 $N$의 randomness를 무시할 것이다.

$k$-dimensional Dirichlet random variable $\theta$는 다음과 같은 probability density를 갖는다.

\[p(\theta \vert \alpha) = \frac{\Gamma(\sum_{i=1}^{k} \alpha_i)}{\prod_{i=1}^{k} \Gamma(\alpha_i)} \theta_1^{\alpha_1-1} \cdots \theta_k^{\alpha_k-1}.\]

$\alpha, \beta$가 주어졌을 때, 위 generative process를 따르는 $\theta, \mathbf z, \mathbf w$의 joint distribution은 다음과 같다.

\[p(\theta, \mathbf z, \mathbf w \vert \alpha, \beta) = p(\theta \vert \alpha) \prod_{n=1}^{N} p(z_n \vert \theta) p(w_n \vert z_n , \beta).\]

여기서 $z_n$은 $k$차원 one-hot vector이므로, 그 중 $z_n^i = 1$이라면 $p(z_n \vert \theta)=\theta_i$이다. $\theta, \mathbf z$를 marginalize하면 다음과 같다.

\[\begin{align*} p(\mathbf w \vert \alpha, \beta) &= \int \sum_{z_1} \cdots \sum_{z_N} p(\theta, \mathbf z, \mathbf w \vert \alpha, \beta) d\theta\\ &= \int \sum_{z_1} \cdots \sum_{z_N}\left( p(\theta \vert \alpha) \prod_{n=1}^{N} p(z_n \vert \theta) p(w_n \vert z_n , \beta) \right) d\theta \\ &= \int p(\theta \vert \alpha) \sum_{z_1} \cdots \sum_{z_N}\left( \prod_{n=1}^{N} p(z_n \vert \theta) p(w_n \vert z_n , \beta) \right) d\theta \\ &= \int p(\theta \vert \alpha) \left( \prod_{n=1}^{N} \sum_{z_n} p(z_n \vert \theta) p(w_n \vert z_n , \beta) \right) d\theta \end{align*}\]

Corpus $D$는 document들의 collection이고, 각 document들은 서로 독립이므로,

\[\begin{align*} p(D \vert \alpha, \beta) &= \prod_{d=1}^{M} p(\mathbf w_d \vert \alpha, \beta) \\ &=\prod_{d=1}^{M} \int p(\theta_d \vert \alpha) \left( \prod_{n=1}^{N_d} \sum_{z_{dn}} p(z_{dn} \vert \theta) p(w_{dn} \vert z_{dn} , \beta) \right) d\theta_d \end{align*}\]

이와 같은 LDA의 model을 graphical model 그림으로 나타내면 다음과 같다.

위의 그림에서 볼 수 있듯이 LDA의 모형에는 세 level이 있다.

• $\alpha, \beta$는 corpus-level parameter이므로, corpus를 generate할 때 한 번 sample된다.
• $\theta_d$는 document-level parameter이며, document당 한 번 sample된다.
• $z_{dn}, w_{dn}$은 word-level parameter이며, word 당 한 번 sample된다.

LDA와 일반적인 Bayesian Dirichlet-multinomial mixture model 간의 차이는 무엇일까? 일반적인 mixture model에서는 Dirichlet distribution을 이용해 각 mixture component에 대한 확률벡터를 생성하고, 그 확률벡터를 parameter로 갖는 multinomial distribution을 통해 관측치를 각 mixture component(cluster)로 나눈다. 이렇게 하면 document는 각각 하나의 topic(cluster assignment)을 갖는다. 하지만 LDA에서는 topic variable이 문서 내의 word 하나하나마다 계속 sample이 되므로, 한 document 내에 여러 topic이 존재할 수 있는 것이다.

3.1 LDA and Exchangeability

Exchangeability, infinite exchangeability의 정의는 다음과 같다.

A finite set of random variables ${ z_1, \cdots, z_N }$ is said to be exchangeable if the joint distribution is invariant to permutation. If $\pi$ is a permutation of the integers from $1$ to $N$:

\[p(z_1, \cdots, z_N) = p(z_{\pi(1)}, \cdots, z_{\pi(N)}).\]

An infinite sequence of random variables is infinitely exchangeable if every finite subsequence is exchangeable.

De Finetti 정리에 따르면 infinitely exchangeable한 sequence of random variable의 joint distribution은 그 parameter가 어떤 분포를 따르고, 그 parameter가 주어졌을 때, random variable들이 서로 conditionally independent and identically distributed하다. 자세한 내용은 이 포스트에서 소개했다.

LDA에서는 topic이 서로 infinitely exchangeable하다고 가정한다. 또한, word는 topic에 의해, 즉 고정된 conditional distribution$($topic $i$ : $\beta_{i1}, \cdots, \beta_{iV})$ 생성된다. 따라서, ${ y_n = (w_n,z_n) }$는 서로 exchangeable하다고 볼 수 있으므로,

\[\begin{align*} p(\mathbf{w} , \mathbf{z} ) &= \int \left( \prod_{n=1}^{N} p(w_n, z_n \vert \theta)\right) p(\theta) d\theta \\ &= \int \left( \prod_{n=1}^{N} p(w_n \vert z_n) p(z_n \vert \theta)\right) p(\theta) d\theta \end{align*}\]

여기서 $\theta$는 위의 graphical model 그림과 같이 topic이 생성되는 multinomial distribution의 (document-level) parameter이다. 이 식에서 topic variable $\mathbf z$를 marginalize하고 $\theta$에 Dirichlet distribution을 부여하면, 위에서 보았던 $p(\mathbf w \vert \alpha, \beta)$의 식을 얻을 수 있다.

3.2 A Continuous Mixture of Unigrams

위 graphical model 그림에 나타난 LDA는 hierarchical Bayesian two-level보다 더 정교하다. 그런데 만약 topic variable $\mathbf z$를 marginalize한다면 우리는 LDA를 two-level model로 이해할 수 있다. 다음과 같은 word distribution $p(w \vert \theta, \beta)$를 생각해보자.

\[p(w \vert \theta, \beta) = \sum_z p(w ,z \vert \theta, \beta) = \sum_z p(w \vert z, \theta, \beta) p(z \vert \theta, \beta)= \sum_z p(w \vert z, \beta) p(z \vert \theta)\]

이는 Dirichlet random variable인 $\theta$에 depend하기 때문에 random quantity이다. 이제 다음과 같은 generative process를 생각해보자.

1. Choose $\theta \sim \text{Dirichlet}(\alpha).$
2. For each of the $N$ words $w_n$, choose a word $w_n$ from $p(w_n \vert \theta, \beta)$

이 process는 document $\mathbf w$의 marginal distribution을 continuous mixture distribution으로 정의한다. 이게 무슨 뜻인지 생각해보면, 위에서 우리는 $p(\mathbf w \vert \alpha, \beta)$를 다음과 같이 도출하였다. 그런데 $z$를 marginalize한 $p(w \vert \theta, \beta)$의 식을 여기에 대입하면 다음과 같다.

\[\begin{align*} p(\mathbf w \vert \alpha, \beta) &= \int p(\theta \vert \alpha) \left( \prod_{n=1}^{N} \sum_{z_n} p(z_n \vert \theta) p(w_n \vert z_n , \beta) \right) d\theta \\ &= \int p(\theta \vert \alpha) \left( \prod_{n=1}^{N} p(w_n \vert \theta, \beta) \right) d\theta \end{align*}\]

즉 $p(\theta \vert \alpha)$가 mixture weight고 $ \prod_{n=1}^{N} p(w_n \vert \theta, \beta)$가 mixture component인 continuous mixture의 형태가 된다.

그림을 통해 LDA의 해석에 대해 더 알아보자. 다음과 같은 예시 상황을 가정한다. Word는 A, B, C 세 가지 중 한 값을 갖고, topic이 총 네 개 있다고 하자. Topic은 가능한 word들에 대한 분포이므로, 이 상황에서 topic은 다음과 같은 형태를 갖는다.

\[(P_A, P_B, P_C), \text{ where }P_A + P_B + P_C =1\]

아래 그림 상의 삼각형은 이 $(P_A, P_B, P_C)$가 이루는 $2$-simplex를 선형변환하여 정삼각형으로 나타낸 것이다. 따라서 삼각형의 각 꼭짓점은 한 단어에 $1$의 확률을 부여하는 경우를 나타내며, 삼각형의 무게중심에 해당하는 점은 세 단어 A, B, C에 동일한 확률을 부여하는 경우를 나타낸다. 즉 이 simplex 삼각형 위의 각 점은 “word에 대한 multinomial distribution”, 즉 $p(w \vert \theta, \beta)$에 일대일 대응된다. 위에서 $p(w \vert \theta, \beta)$가 random quantity라고 했던 것은 이를 의미한 것이다. 아래 그림의 simplex 위의 surface는 $p(w \vert \theta, \beta)$에 대한 density의 예시를 나타내며, surface가 위로 솟아오른 부분의 simplex 상 점은, 가능한 topic 네 가지에 해당한다.

여기서 주목할만한 부분은 이 multinomial distribution이 이루는 simplex 위의 분포는 총 $k+kV = 4+4\cdot 3 = 16$개의 적은 수의 parameter를 갖는데도($\alpha$가 $k$차원, $\beta$가 $k \times V$차원), 위의 그림과 같이 multimodal structure를 포착해낸다는 점이다.

4. Relationship with Other Latent Variable Models

보충 要

5. Inference and Parameter Estimation

지금까지 LDA에 대한 motivation, 다른 latent topic model과 비교했을 때의 이점에 대해 알아보았다. 이제 어떻게 LDA에 대해 inference와 parameter estimation을 수행하는지 소개하겠다.

5.1 Inference

LDA에서 우리가 해결해야할 inferential problem은 document가 주어졌을 때, hidden variable의 posterior distribution을 구하는 것이다. 여기서 hidden variable은 topic의 multinomial 확률인 $\theta$와 그에 따라 생성된 topic $\mathbf z$이다.

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

그런데 위 posterior 식의 분모 $p(\mathbf w \vert \alpha, \beta)$를 model parameter에 대해 정리하면 다음과 같다.

\[\begin{align*} p(\mathbf w \vert \alpha, \beta) &= \int p(\theta \vert \alpha) \left( \prod_{n=1}^{N} \sum_{z_n} p(z_n \vert \theta) p(w_n \vert z_n , \beta) \right) d\theta \\ &=\int \left( \frac{\Gamma(\sum_i \alpha_i)}{\prod_i \Gamma(\alpha_i)} \prod_{i=1}^{k} \theta_i^{\alpha_i -1 } \right) \left( \prod_{n=1}^{N} \sum_{z_n} \prod_{j=1}^{V} \theta_i^{w_n^j} \beta_{ij}^{w_n^j} \right) d\theta , \end{align*}\] \[\left( \because \quad p(\theta \vert \alpha) = \frac{\Gamma(\sum_i \alpha_i)}{\prod_i \Gamma(\alpha_i)} \prod_{i=1}^{k} \theta_i^{\alpha_i -1 } , \enspace p(z_n \vert \theta) = \prod_{j=1}^{V} \theta_i^{w_n^j}, \enspace p(w_n \vert z_n , \beta) = \prod_{j=1}^{V} \beta_{ij}^{w_n^j} . \right)\]

이는 합 기호 안에 $\theta$와 $\beta$가 섞여있기 때문에 직접 다루기 힘들다. 따라서 우리는 posterior를 직접 inference하지 않고, variational inference를 이용해 간접적으로 inference하는 방법을 소개한다.

5.2 Variational Inference

Variational inference는 직접 posterior를 추정하는 것이 어려울 때, 우리가 정한 function class $\mathcal Q$내에서 true posterior와 “가장 가까운” 함수를 이용하여 posterior를 간접적으로 추정하는 방법이다. Posterior를 근사하는 분포를 variational distribution $q \in \mathcal Q$라고 하며, variational distribution은 우리가 설정한 class 내에서 variational parameter로 parametrize된다.

먼저 variational distribution이 속하는 class를 특정해야 한다. 위의 graphical model 그림의 왼쪽 그림에서 볼 수 있듯이, $\theta$와 $\beta$가 식에서 서로 엉켜있던 것은 $\theta, \mathbf z, \mathbf w$를 잇는 edge들과 $\mathbf w$ node 때문이다. 다루기 쉬운 distribution class $\mathcal Q $를 설정하는 방법은 이 edge들과 node를 없애주는 것이다. 오른쪽 그림에서와 같이 $\theta, \mathbf z$ 사이의 edge를 끊고, 각각 별개의 parameter로 parametrize되는 model을 생각해볼 수 있다. 따라서 다음과 같이 variational distribution의 class $\mathcal Q$를 특정한다.

\[\mathcal Q = \left\{ q: q(\theta, \mathbf z \vert \gamma, \phi) = q(\theta \vert \gamma) \prod_{n=1}^{N} q(z_n \vert \phi_n) \right\}\]

이제 $\mathcal Q$ 내에서 true posterior $p(\theta, \mathbf z \vert \mathbf w, \alpha, \beta) $와 “가장 가까운” $q^\ast$를 찾고자 한다. 그를 위해서 KL divergence를 기준으로, $\mathcal Q$ 내에서 true posterior와 가장 가까운 variational distribution을 찾는다. 이는 variational parameter $\gamma, \phi$에 대한 다음 최적화 문제를 해결하는 것과 같다.

\[(\gamma^\ast, \phi^\ast) = \arg \min_{(\gamma, \phi)} KL[q(\theta, \mathbf z \vert \gamma, \phi) \text{ } \vert \vert \text{ } p(\theta, \mathbf z \vert \alpha, \beta, \mathbf w )]\]

Why do we minimize the KL divergence?

왜 우리는 variational posterior probability와 true posterior probability의 KL divergence를 최소화하는 $\gamma, \phi$를 고르는 것일까? 그 이유는 다음과 같다. Log-likelihood $p(\mathbf w \vert \alpha, \beta)$는 Jensen’s inequality를 이용하여 다음과 같이 bound시킬 수 있다.

\[\begin{align*} \log p(\mathbf w \vert \alpha, \beta) &= \log \int \sum_{\mathbf z} p(\theta, \mathbf z, \mathbf w \vert \alpha, \beta) d\theta \\ &= \log \int \sum_{\mathbf z} \frac{p(\theta, \mathbf z, \mathbf w \vert \alpha, \beta) }{q(\theta, \mathbf z \vert \gamma, \phi)}q(\theta, \mathbf z \vert \gamma, \phi)d\theta \\ &= \log \mathbb E_q \left[\frac{p(\theta, \mathbf z, \mathbf w \vert \alpha, \beta) }{q(\theta, \mathbf z \vert \gamma, \phi)}\right] \\ &\geq \mathbb E_q \left[ \log \frac{p(\theta, \mathbf z, \mathbf w \vert \alpha, \beta) }{q(\theta, \mathbf z \vert \gamma, \phi)}\right] \\ &=\mathbb E_q \left[\log p(\theta, \mathbf z, \mathbf w \vert \alpha, \beta) \right]-\mathbb E_q \left[\log q(\theta, \mathbf z \vert \gamma, \phi)\right] \\ &:= L(\gamma, \phi ; \alpha, \beta) \end{align*}\]

따라서 log-likelihood $p(\mathbf w \vert \alpha, \beta)$를 $L(\gamma, \phi ; \alpha, \beta)=\mathbb E_q \left[\log p(\theta, \mathbf z, \mathbf w \vert \alpha, \beta) \right]-\mathbb E_q \left[\log q(\theta, \mathbf z \vert \gamma, \phi)\right]$로 아래에서 bound시킬 수 있다. 또한, 그 lower bound $L(\gamma, \phi ; \alpha, \beta)$와 log-likelihood $p(\mathbf w \vert \alpha, \beta)$의 차이를 구하면 다음과 같다.

\[\begin{align*}\log p(\mathbf w \vert \alpha, \beta) &= \mathbb E_q [ \log p(w \vert \alpha, \beta)]\\&=\mathbb E_q \left[ \log \frac{p(\theta, \mathbf z , \mathbf w \vert \alpha, \beta)}{p(\theta, \mathbf z \vert \alpha, \beta, \mathbf w )} \right] \\&= \mathbb E_q \left[ \log \frac{p(\theta, \mathbf z, \mathbf w \vert \alpha, \beta) }{q(\theta, \mathbf z \vert\gamma, \phi)} \frac{q(\theta, \mathbf z \vert \gamma, \phi)}{p(\theta, \mathbf z \vert \alpha, \beta, \mathbf w )} \right]\\&=\mathbb E_q \left[ \log \frac{p(\theta, \mathbf z, \mathbf w \vert \alpha, \beta) }{q(\theta, \mathbf z \vert \gamma, \phi)} \right] + \mathbb E_q \left[ \frac{q(\theta, \mathbf z \vert \gamma, \phi)}{p(\theta, \mathbf z \vert \alpha, \beta, \mathbf w )} \right] \\&= L(\gamma, \phi ; \alpha, \beta) + KL[q(\theta, \mathbf z \vert \gamma, \phi) \text{ } \vert \vert \text{ } p(\theta, \mathbf z \vert \alpha, \beta, \mathbf w )]\end{align*}\]

즉, log-likelihood $p(\mathbf w \vert \alpha, \beta)$와 lower bound $L(\gamma, \phi ; \alpha, \beta)$는 variational distribution와 true posterior probability의 차이, $KL[q(\theta, \mathbf z \vert \gamma, \phi) \text{ } \vert \vert \text{ } p(\theta, \mathbf z \vert \alpha, \beta, \mathbf w )]$만큼 차이가 난다는 것을 알 수 있다. 따라서,

\[\text{maximize } L(\gamma, \phi ; \alpha, \beta) \iff \text{minimize }KL[q(\theta, \mathbf z \vert \gamma, \phi) \text{ } \vert \vert \text{ } p(\theta, \mathbf z \vert \alpha, \beta, \mathbf w )]\]

Variational distribution과 true posterior probability 간의 KL divergence를 최소화함으로써, Log-likelihood $p(\mathbf w \vert \alpha, \beta)$의 lower bound를 최대한 ‘위로 쳐올리고자’ 하는 것이다.

Representing lower bound with respect to $\gamma, \phi$

먼저 variational parameter에 대한 의미를 생각해보면, $\gamma$는 topic variable $\mathbf z $를 생성하는 multinomial distribution의 parameter $\theta$에 영향을 주는 variational parameter이다.

\[\gamma \in \mathbb R^k, \quad \theta \sim \text{Dirichlet}(\gamma) \text{ under variational distribution }q.\]

$\phi$는 topic variable $\mathbf z$에 영향을 주는 variational parameter로, 다음과 같다.

\[\phi \in \mathbb R^{N \times k }, \quad \phi_{ni} : \text{the probability that }n^{th} \text{ word is topic }i. \\z_n \sim \text{Multinomial}(\phi_{n1} , \cdots , \phi_{nk}) \text{ under variational distribution }q.\]

Lower bound $L(\gamma, \phi ; \alpha, \beta)$를 $\gamma, \phi$에 대해 최대화 하기 위해서, 다음과 같이 $\gamma, \phi$에 대한 함수로 $L(\gamma, \phi ; \alpha, \beta)$를 나타내자.

\[\begin{align*} \mathbb E_q \left[\log p(\theta, \mathbf z, \mathbf w \vert \alpha, \beta) \right] &= \mathbb E_q \left[\log p(\mathbf w \vert \theta, \mathbf z, \alpha, \beta) p(\mathbf z \vert \theta,\alpha, \beta) p(\theta \vert \alpha, \beta)\right] \\ &= \mathbb E_q \left[\log p(\mathbf w \vert \mathbf z, \beta) p(\mathbf z \vert \theta) p(\theta \vert \alpha)\right] \\ &= \mathbb E_q \left[\log p(\mathbf w \vert \mathbf z, \beta)\right] + \mathbb E_q \left[\log p(\mathbf z \vert \theta)\right] + \mathbb E_q \left[\log p(\theta \vert \alpha)\right]\\ \mathbb E_q \left[\log q(\theta, \mathbf z \vert \gamma, \phi)\right] &= \mathbb E_q \left[\log q(\theta \vert \gamma)\right] + \mathbb E_q \left[\log q(\mathbf z \vert \phi)\right] \end{align*}\] \[\begin{align*} L(\gamma, \phi ; \alpha, \beta) &= \mathbb E_q \left[\log p(\theta, \mathbf z, \mathbf w \vert \alpha, \beta) \right]-\mathbb E_q \left[\log q(\theta, \mathbf z \vert \alpha, \beta)\right] \\ &=\mathbb E_q \left[\log p(\mathbf w \vert \mathbf z, \beta)\right] + \mathbb E_q \left[\log p(\mathbf z \vert \theta)\right] + \mathbb E_q \left[\log p(\theta \vert \alpha)\right] - \mathbb E_q \left[\log q(\theta \vert \gamma)\right] - \mathbb E_q \left[\log q(\mathbf z \vert \phi)\right] \\ \end{align*}\]

이 다섯 개의 항은 다음과 같이 $\gamma, \phi$에 대해 나타낼 수 있다.

\[\begin{align*} \text{1. }\enspace p(\mathbf w \vert \mathbf z, \beta) &= \prod_{n=1}^{N} p(w_n \vert z_n, \beta) = \prod_{n=1}^{N} \prod_{i=1}^{k} \left( \prod_{j=1}^{V}\beta_{ij}^{w_n^j}\right)^{z_n^i} \\ \log p(\mathbf w \vert \mathbf z, \beta) &= \sum_{n=1}^{N} \sum_{i=1}^{k} \sum_{j=1}^{V} z_n^i w_n^j \log \beta_{ij} \\ \mathbb E_q \left[\log p(\mathbf w \vert \mathbf z, \beta)\right] &= \sum_{n=1}^{N} \sum_{i=1}^{k} \sum_{j=1}^{V} \mathbb E_q [z_n^i] w_n^j \log \beta_{ij} = \sum_{n=1}^{N} \sum_{i=1}^{k} \sum_{j=1}^{V} \phi_{ni} w_n^j \log \beta_{ij} \end{align*}\]

$2.$의 함수 $\Psi$는 digamma function, 즉 log-gamma function의 일차도함수를 의미한다.

\[\begin{align*} \text{2. }\enspace p(\mathbf z \vert \theta) &= \prod_{n=1}^{N} p(z_n \vert \theta) = \prod_{n=1}^{N} \prod_{i=1}^{k} \theta_i^{z_n^i} \\ \log p(\mathbf z \vert \theta) &= \sum_{n=1}^{N} \sum_{i=1}^{k} z_n^i \log \theta_i \\ \mathbb E_q \log p(\mathbf z \vert \theta) &= \sum_{n=1}^{N} \sum_{i=1}^{k} \mathbb E_q [ z_n^i \log \theta_i ] \stackrel{ind}{=} \sum_{n=1}^{N} \sum_{i=1}^{k} \mathbb E_q [ z_n^i] \mathbb E_q [\log \theta_i ] \\ &= \sum_{n=1}^{N} \phi_{ni} \left[ \Psi(\gamma_i) - \Psi \Big(\sum_{i=1}^{k} \gamma_i \Big) \right] \end{align*}\] \[\begin{align*} \text{3. }\enspace p(\theta \vert \alpha) &= \frac{\Gamma(\sum_{i=1}^{k} \alpha_i)}{\prod_{i=1}^{k} \Gamma(\alpha_i)} \prod_{i=1}^{k} \theta_i^{\alpha_i -1} \\ &= \exp\left( \sum_{i=1}^{k}(\alpha_i -1)\log \theta_i - \left[ \sum_{i=1}^{k} \log \Gamma (\alpha_i) - \log \Gamma \Big( \sum_{i=1}^{k} \alpha_i \Big)\right] \right) \\ &= h(\theta) \exp(\eta(\alpha)^T T(\theta) - A(\eta(\alpha)) )\\ &\left( \text{where }\enspace A(\eta(\alpha)) = \sum_{i=1}^{k} \log \Gamma (\alpha_i) - \log \Gamma \Big( \sum_{i=1}^{k} \alpha_i \Big), \enspace \eta(\alpha)_i = \alpha_i-1, \enspace T(\theta)_i = \log \theta_i.\right)\\ \mathbb E[\log \theta_i \vert \alpha] &= \frac{\partial}{\partial \eta_i} A(\eta) = \Psi(\alpha_i) - \Psi \Big(\sum_{i=1}^{k} \alpha_i\Big)\\ \\ \log p(\theta \vert \alpha) &= \sum_{i=1}^{k}(\alpha_i -1)\log \theta_i - \sum_{i=1}^{k} \log \Gamma (\alpha_i) + \log \Gamma \Big( \sum_{i=1}^{k} \alpha_i \Big) \\ \mathbb E_q [\log p(\theta \vert \alpha)] &= \sum_{i=1}^{k}(\alpha_i -1) \mathbb E_q [\log \theta_i ]- \sum_{i=1}^{k} \log \Gamma (\alpha_i) + \log \Gamma \Big( \sum_{i=1}^{k} \alpha_i \Big) \\ &= \sum_{i=1}^{k}(\alpha_i -1) \left[ \Psi(\gamma_i) - \Psi \Big(\sum_{i=1}^{k} \gamma_i \Big) \right] - \sum_{i=1}^{k} \log \Gamma (\alpha_i) + \log \Gamma \Big( \sum_{i=1}^{k} \alpha_i \Big) \end{align*}\] \[\begin{align*} \text{4. }\enspace q(\theta \vert \gamma ) &= \frac{\Gamma(\sum_{i=1}^{k} \gamma_i)}{\prod_{i=1}^{k} \Gamma(\gamma_i)} \prod_{i=1}^{k} \theta_i^{\alpha_i -1} \\ \log q(\theta \vert \gamma ) &= \sum_{i=1}^{k}(\gamma_i -1)\log \theta_i - \sum_{i=1}^{k} \log \Gamma (\gamma_i) + \log \Gamma \Big( \sum_{i=1}^{k} \gamma_i \Big) \\ \mathbb E_q [\log q(\theta \vert\gamma)] &= \sum_{i=1}^{k}(\gamma_i -1) \mathbb E_q [\log \theta_i ]- \sum_{i=1}^{k} \log \Gamma (\gamma_i) + \log \Gamma \Big( \sum_{i=1}^{k} \gamma_i \Big) \\ &= \sum_{i=1}^{k}(\gamma_i -1) \left[ \Psi(\gamma_i) - \Psi \Big(\sum_{i=1}^{k} \gamma_i \Big) \right] - \sum_{i=1}^{k} \log \Gamma (\gamma_i) + \log \Gamma \Big( \sum_{i=1}^{k} \gamma_i \Big) \end{align*}\] \[\begin{align*} \text{5. }\enspace q(\mathbf z \vert \phi ) &= \prod_{n=1}^{N} q(z_n \vert \phi) = \prod_{n=1}^{N} \prod_{i=1}^{k} \phi_{ni}^{z^i_n} \\ \log q(\mathbf z \vert \phi ) &= \sum_{n=1}^{N} \sum_{i=1}^{k} z^i_n \log \phi_{ni} \\ \mathbb E_q [ \log q(\mathbf z \vert \phi ) ] &= \sum_{n=1}^{N} \sum_{i=1}^{k} \mathbb E_q [z^i_n] \log \phi_{ni} = \sum_{n=1}^{N} \sum_{i=1}^{k} \phi_{ni} \log \phi_{ni}\\ \end{align*}\]

이제 $1. \sim 5.$의 결과를 이용해, $L(\gamma, \phi ; \alpha, \beta)$를 $\gamma, \phi$에 대한 함수로 나타내면 다음과 같다.

\[\begin{align*} L(\gamma, \phi ; \alpha, \beta) &=\sum_{n=1}^{N} \sum_{i=1}^{k} \sum_{j=1}^{V} \phi_{ni} w_n^j \log \beta_{ij} \\ &+ \sum_{n=1}^{N} \phi_{ni} \left[ \Psi(\gamma_i) - \Psi \Big(\sum_{i=1}^{k} \gamma_i \Big) \right] \\ &+ \sum_{i=1}^{k}(\alpha_i -1) \left[ \Psi(\gamma_i) - \Psi \Big(\sum_{i=1}^{k} \gamma_i \Big) \right] - \sum_{i=1}^{k} \log \Gamma (\alpha_i) + \log \Gamma \Big( \sum_{i=1}^{k} \alpha_i \Big) \\ &- \sum_{i=1}^{k}(\gamma_i -1) \left[ \Psi(\gamma_i) + \Psi \Big(\sum_{i=1}^{k} \gamma_i \Big) \right] + \sum_{i=1}^{k} \log \Gamma (\gamma_i) - \log \Gamma \Big( \sum_{i=1}^{k} \gamma_i \Big) \\ &- \sum_{n=1}^{N} \sum_{i=1}^{k} \phi_{ni} \log \phi_. \end{align*}\]

이제 이를 $\gamma, \phi$에 대해 최대화하고자 한다. 그를 위해서 수렴할 때까지 $\gamma$와 $\phi$를 번갈아가며 최대화한다.

Multinomial update : Optimization with respect to $\phi_{ni}$

$\phi_{n1}, \cdots, \phi_{nk}$는 multinomial distribution의 parameter가 되는 확률벡터이므로, $\sum_{i=1}^k \phi_{ni}=1$의 제약 하에서 최적화를 수행한다. 위 목적 식에서 $\phi_{ni}$에 depend하는 항들만 모은 후, 제약식을 붙인 $L_{[\phi_{ni}]}$는 다음과 같다.

\[L_{[\phi_{ni}]} = \phi_{ni} \left[ \Psi(\gamma_i) - \Psi \Big(\sum_{i=1}^{k} \gamma_i \Big) \right] + \sum_{j=1}^{V} \phi_{ni} w_n^j \log \beta_{ij} -\phi_{ni} \log \phi_ + \lambda_n \Big(\sum_{l=1}^k \phi_{nl}-1 \Big)\]

두 번째 항에서 $w_n^j$를 보면, $w_n^j$는 어떤 한 $j$에 대해서만 $1$의 값을 갖고 나머지의 $j$에서는 $0$의 값을 갖는다. $w_n^j$가 $1$의 값을 갖는 index를 $v$라고 하고 식을 다시 표현하면 다음과 같다.

\[L_{[\phi_{ni}]} = \phi_{ni} \left[ \Psi(\gamma_i) - \Psi \Big(\sum_{i=1}^{k} \gamma_i \Big) \right] + \phi_{ni} \log \beta_{iv} -\phi_{ni} \log \phi_ + \lambda_n \Big(\sum_{l=1}^k \phi_{nl}-1 \Big)\]

이를 $\phi_{ni}, \text{ } i= 1, \cdots, k$에 대해 미분하여 일계조건을 구하면,

\[\frac{\partial L}{\partial \phi_{ni}} = \Psi(\gamma_i) - \Psi \Big(\sum_{i=1}^{k} \gamma_i \Big) + \log \beta_{iv} - \log \phi_ -1 + \lambda_n \stackrel{let}{=} 0, \quad i= 1, \cdots, k\] \[\begin{align*}\implies \quad \phi_{ni}^\ast &= \beta_{iv} \exp \Big( \Psi(\gamma_i) - \Psi \Big(\sum_{i=1}^{k} \gamma_i \Big) \Big) \exp(-1 + \lambda_n)\\&\propto \beta_{iv} \exp \Big( \Psi(\gamma_i) - \Psi \Big(\sum_{i=1}^{k} \gamma_i \Big) \Big) = \beta_{iv} \exp \Big( \mathbb E_q[\log \theta_i \vert \gamma ] \Big) , \quad i= 1, \cdots, k\end{align*}\]

여기서 상수를 무시하고 어떤 식에 비례하는지만 특정해도 되는 이유는, $\sum_{i=1}^k \phi^\ast_{ni}=1$의 성질을 이용해서 normalize를 쉽게 할 수 있기 때문이다.

Dirichlet update : Optimization with respect to $\gamma_i$

위 목적 식에서 $\gamma$에 depend하는 항만 모은 $L_{[\gamma]}$는 다음과 같다.

\[\begin{align*}L_{[\gamma]} &= \sum_{\ell=1}^{k} \Big( \sum_{n=1}^{N} \phi_{n\ell} + \alpha_\ell -\gamma_\ell \Big) \left[ \Psi(\gamma_\ell) + \Psi \Big(\sum_{t=1}^{k} \gamma_t \Big) \right] + \sum_{\ell=1}^{k} \log \Gamma (\gamma_\ell) - \log \Gamma \Big( \sum_{\ell=1}^{k} \gamma_\ell \Big) , \quad i= 1, \cdots, k\end{align*}\]

$\gamma_i $에 대해 미분하여 일계조건을 구하면,

\[\frac{\partial L}{\partial \gamma_i} = \Psi^\prime (\gamma_i) \Big( \alpha_i + \sum_{n=1}^{N} \phi_{ni} - \gamma_i \Big) - \Psi^\prime \Big(\sum_{\ell=1}^{k} \gamma_\ell \Big) \sum_{\ell = 1}^{k} \Big( \alpha_\ell + \sum_{n=1}^{N} \phi_{n \ell} -\gamma_\ell \Big)\stackrel{let}{=} 0 , \quad i= 1, \cdots, k\]

여기서 알아보기 쉽게 다음과 같이 식을 치환한다.

\[X_i = \alpha_i + \sum_{n=1}^{N} \phi_{ni} - \gamma_i , \enspace a_i =\Psi^\prime (\gamma_i), \enspace c= \Psi^\prime \Big(\sum_{\ell=1}^{k} \gamma_\ell \Big).\]

이를 이용해 정리하면 다음과 같다.

\[a_iK_i - c \sum_{\ell=1}^{k} K_\ell = 0 , \quad i= 1, \cdots, k\] \[\begin{bmatrix} a_1 -c & -c & -c & & -c\\ -c & a_2-c & -c & \cdots & -c \\ -c & -c & a_3-c & & -c \\ & \vdots & & \ddots & \\ -c & -c & -c & & a_k -c\\ \end{bmatrix} \begin{bmatrix} K_1 \\ K_2 \\ K_3 \\ \vdots \\ K_k \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ \vdots \\ 0 \\ \end{bmatrix}\]

계수행렬의 determinant는 다음과 같이 구할 수 있다.

\[\left\vert\begin{matrix} a_1 -c & -c & -c & & -c\\ -c & a_2-c & -c & \cdots & -c \\ -c & -c & a_3-c & & -c \\ & \vdots & & \ddots & \\ -c & -c & -c & & a_k -c\\ \end{matrix} \right\vert = \left\vert\begin{matrix} a_1 -c & -c & -c & & -c\\ -a_1 & a_2 & -c & \cdots & 0 \\ -a_1 & 0 & a_3 & & 0 \\ & \vdots & & \ddots & \\ -a_1 & 0 & 0 & & a_k\\ \end{matrix} \right\vert = -ca_1 a_2\cdots a_k\sum_{i=1}^{k} \frac{1}{a_i}\]

Digamma function의 도함수 $\Psi^\prime(x)$는 $x>0$일 때 항상 양수이므로, 계수행렬의 determinant는 $0$이 아니다. 따라서 위 system of equation을 만족하는 해는 다음과 같다.

\[K_1= \cdots = K_k = 0 \\\implies \gamma_i^\ast = \alpha_i + \sum_{n=1}^{N} \phi_{ni} , \quad i= 1, \cdots, k \\\]

Summary

우리는 log-likelihood의 lower bound $L(\gamma, \phi \vert \alpha, \beta)$를 가장 tight하게 쳐올리는 variational parameter $\gamma, \phi$를 찾고자 했다. 또한 이 문제가 variational distribution $q(\theta, \mathbf z \vert \gamma, \phi)$와 true posterior distribution $p(\theta, \mathbf z \vert \mathbf w, \alpha, \beta)$의 KL divergence를 최소화하는 것과 같다는 것을 보였다. 그 후 lower bound $L(\gamma, \phi \vert \alpha, \beta)$를 $\gamma, \phi$에 대한 함수로 나타내고, $\gamma$와 $\phi$에 대해 각각 따로 최적화했을 때 solution이 다음과 같다는 것을 보였다.

\[\begin{align*}\phi_{ni}^\ast &\propto \beta_{iv} \exp \Big( \Psi(\gamma_i) - \Psi \Big(\sum_{i=1}^{k} \gamma_i \Big) \Big) , \quad n=1, \cdots, N, \text{ } i= 1, \cdots, k \\\gamma_i^\ast &= \alpha_i + \sum_{n=1}^{N} \phi_{ni} , \quad i= 1, \cdots, k \\\end{align*}\]

Lower bound의 값이 수렴할 때까지, 이를 $\phi$와 $\gamma$에 대해 번갈아가며 충분히 최적화를 시켜주면 된다. 이를 나타낸 알고리즘은 다음과 같다.

여기서 눈여겨볼 부분은 variational distribution $q(\theta, \mathbf z \vert \gamma, \phi)$가 관측된 $\mathbf w$가 주어졌을 때의 조건부 분포라는 점이다. 따라서 $\mathbf w$가 달라지면 위 최적화문제의 목적함수가 달라지고, 그에 따라 최적화의 결과인 $\gamma^\ast, \phi^\ast$도 달라지게 될 것이다. 따라서 $\gamma^\ast, \phi^\ast$는 $\mathbf w$에 대한 함수이고, 우리는 최적화의 결과로 얻은 variational distribution을 다음과 같이 적을 수 있다.

\[q(\theta, \mathbf z \vert \gamma^\ast(\mathbf w), \phi^\ast (\mathbf w))\]

그렇기 때문에 variational distribution을 ‘$\mathbf w$가 관측되었을 때의 모수 $\theta, \mathbf z$의 분포’, 즉 true posterior $p(\theta, \mathbf z \vert \mathbf w, \alpha, \beta)$의 approximation으로 볼 수 있는 것이다. 매우 중요하다. 이 사실을 알아야 variational inference를 이해한 것이라고 생각한다.

5.3 Parameter Estimation

이 장에서는 LDA의 model parameter $\alpha, \beta $를 추정하기 위한 empirical Bayes 방법을 소개한다. 복수의 document들로 이루어진 corpus $D = { \mathbf w_1 , \mathbf w_2 , \cdots , \mathbf w_M }$이 주어졌을 때, 우리는 (marginal) log likelihood를 최대화하는 parameter $\alpha, \beta$를 찾고자 한다.

\[\ell(\alpha, \beta) = \sum_{d=1}^{M} \log p(\mathbf w_d \vert \alpha, \beta)\]

5.1에서 소개했듯이 $p(\mathbf w \vert \alpha, \beta)$는 계산을 다루기 힘든 quantity이다. 그러나 5.2에서 확인했듯이 variational inference는 log-likelihood에 대한 계산 가능한 lower bound를 제공한다. 우리는 lower bound $L(\gamma, \phi \vert \alpha, \beta)$를 최대화하는 $\gamma^\ast, \phi^\ast$를 찾은 뒤 (E-step), $\gamma^\ast, \phi^\ast$가 주어졌을 때의 lower bound를 $\alpha, \beta$에 대해 최대화함으로써 (M-step), LDA의 model parameter $\alpha, \beta$에 대한 근사적인 empirical Bayes 추정량을 찾는다.

이는 variational inference를 통해 구한 lower bound $L(\gamma, \phi \vert \alpha, \beta)$를 계산이 불가능한 marginal log-likelihood $\ell(\alpha, \beta)$의 surrogate으로 보고 EM 알고리즘을 수행하는 것과 같다. 따라서 이와 같은 방법의 log-likelihood maximization을 variational EM이라고 부른다. EM 알고리즘에 대한 설명은 이 포스트를 참고하면 좋다.

또한 지금까지는 하나의 document에 대한 log-likelihood를 고려했지만, 이제는 여러 document로 이루어진 corpus의 likelihood를 고려할 것이다. LDA는 document들 간의 exchangeability를 가정했기 때문에, corpus $D = { \mathbf w_1 , \cdots, \mathbf w_M }$의 log-likelihood와 그 lower bound는 각 document들의 log-likelihood와 lower bound의 합으로 나타낼 수 있다.

• (E-step) 각 document에 대해, variational parameter의 optimal value ${ \gamma^\ast_d, \phi^\ast_d : d \in D }$를 찾는다.
• (M-step) Variational parameter의 값을 ${ \gamma^\ast_d, \phi^\ast_d : d \in D }$로 고정시키고, model parameter $\alpha, \beta$에 대해 각 document에 대한 lower bound의 합 $\sum_{d=1}^{M} L_d(\gamma^\ast_d, \phi^\ast_d ; \alpha, \beta)$를 최대화 시키는 $\alpha^\ast, \beta^\ast$를 찾는다.
• 이 두 과정을 corpus의 log-likelihood의 lower bound가 수렴할 때까지 반복한다.

E-step을 수행하는 방법과 그 증명은 5.3에 소개되었다. E-step을 거친 후의 variational parameter가 최적화된 lower bound는 다음과 같다.

• Abuse of notation : 위에서는 한 document의 log-likelihood의 lower bound를 $L$로 적었지만, 이제는 corpus의 lower bound를 $L$로 적겠다.

\[\begin{align*} L(\gamma^\ast, \phi^\ast ; \alpha, \beta) &=\sum_{d=1}^M \sum_{n=1}^{N_d} \sum_{i=1}^{k} \sum_{j=1}^{V} \phi_{dni}^\ast w_{dn}^j \log \beta_{ij} \\ &+ \sum_{d=1}^M \sum_{n=1}^{N_d} \phi_{dni}^\ast \left[ \Psi(\gamma_{di}^\ast) - \Psi \Big(\sum_{i=1}^{k} \gamma_{di}^\ast \Big) \right] \\ &+ \sum_{d=1}^M\sum_{i=1}^{k}(\alpha_i -1) \left[ \Psi(\gamma_{di}^\ast) - \Psi \Big(\sum_{i=1}^{k} \gamma_{di}^\ast \Big) \right] - M\sum_{i=1}^{k} \log \Gamma (\alpha_i) + M \log \Gamma \Big( \sum_{i=1}^{k} \alpha_i \Big) \\ &- \sum_{d=1}^M \sum_{i=1}^{k}(\gamma_{di}^\ast -1) \left[ \Psi(\gamma_{di}^\ast) + \Psi \Big(\sum_{i=1}^{k} \gamma_{di}^\ast \Big) \right] + \sum_{d=1}^{M} \sum_{i=1}^{k} \log \Gamma (\gamma^\ast_{di}) - \sum_{d=1}^{M} \log \Gamma \Big( \sum_{i=1}^{k} \gamma_{di}^\ast \Big) \\ &- \sum_{d=1}^M \sum_{n=1}^{N_d} \sum_{i=1}^{k} \phi_{dni}^\ast \log \phi_{dni}^\ast. \end{align*}\]

복잡하다. M-step을 수행하기 위해서는 $\alpha, \beta$에 대해 이 식을 최대화를 해야하는데, 다행히 여기서는 $\beta, \alpha$가 엉켜있는 항이 없기 때문에 $\beta$와 $\alpha$를 따로 maximize해도 된다.

Multinomial update : Optimization with respect to $\beta_{ij} $

위 식에서 $\beta$를 포함하고 있는 항만 고른 후, $\sum_{j=1}^{V} \beta_{ij} = 1, \forall i$의 제약식을 포함한 라그랑지 목적함수는 다음과 같다.

\[L_{[\beta]} = \sum_{d=1}^M \sum_{n=1}^{N_d} \sum_{i=1}^{k} \sum_{j=1}^{V} \phi_{dni}^\ast w_{dn}^j \log \beta_{ij} + \sum_{i=1}^{k} \lambda_i \left( \sum_{j=1}^{V} \beta_{ij} - 1 \right)\]

이를 $\beta_{ij} $에 대해 미분하고 $0$으로 둬 얻은 일계조건은 다음과 같다.

\[\frac{\partial L}{\partial \beta_{ij}}= \sum_{d=1}^M \sum_{n=1}^{N_d} \phi_{dni}^\ast w_{dn}^j \frac{1}{\beta_{ij}} + \lambda_i \stackrel{let}{=} 0 , \quad i=1, \cdots, k , \enspace j=1, \cdots ,V. \\ \implies \enspace \beta_{ij} \propto \sum_{d=1}^M \sum_{n=1}^{N_d} \phi_{dni}^\ast w_{dn}^j , \quad i=1, \cdots, k , \enspace j=1, \cdots ,V.\]

위에서 $\phi$를 최적화할 때와 마찬가지로, 합이 $1$이라는 제약이 있기 때문에 비례상수는 무시하고 $\tilde \beta_{ij}$를 모두 구한 후, 나중에 한 번에 normalize를 시켜주면 된다.

Newton-Raphson algorithm for a Hessian with special structure

Newton-Raphson 알고리즘은 다음과 같은 update rule로 함수의 stationary point를 찾는다. 이 때 $H$와 $g$는 목적함수의 Hessian matrix와 gradient이다.

\[\alpha_{new} = \alpha_{old} - H(\alpha_{old})^{-1}g(\alpha_{old})\]

Matrix inversion을 포함하고 있기 때문에, 일반적으로 이 알고리즘은 $O(N^3)$의 계산양을 갖는다. 이 파트에서는 Hessian matrix가 특수한 꼴일 때의 Newton-Raphson 방법에 대하여 소개한다.

Hessian matrix가 다음과 같은 모양이라고 하자.

\[H = \text{diag}(\mathbf h) + z \mathbf{11}^T = \text{diag}(\mathbf h) + (\sqrt z \mathbf 1)( \sqrt z \mathbf{1})^T\]

이 때 Hessian의 inverse는 다음과 같다.

\[\begin{align*} H^{-1} &= diag(\mathbf h)^{-1} - \frac{diag(\mathbf h)^{-1}(z\mathbf{11}^T)diag(\mathbf h)^{-1}}{1 + z \mathbf 1^T diag(\mathbf h)^{-1} \mathbf 1} \\ &= diag(\mathbf h)^{-1} - \frac{diag(\mathbf h)^{-1}(z\mathbf{11}^T)diag(\mathbf h)^{-1}}{1 + z \sum_{j=1}^{k}(1/h_j)} \end{align*}\]

Newton-Raphson update에 쓰일 $H^{-1} g$는 다음과 같다.

\[[H^{-1} g]_i = \frac{1}{h_i}\left[g_i-\frac{z\sum_{j=1}^{k} (g_j/h_j)}{1+z\sum_{j=1}^{k}(1/h_j)} \right] , \quad i=1, \cdots , k.\]

$H^{-1} g$는 $2k$ 개의 값만 알면 계산할 수 있으므로 ($h_1, \cdots, h_k ,g_1, \cdots, g_k$), Hessian이 위에 주어진 꼴과 같을 때는 Newton-Raphson method가 linear time complexity를 갖는다.

Dirichlet update : Optimization with respect to $\alpha_i $

$\alpha$를 포함하고 있는 항만 고른 식은 아래와 같다.

\[L_{[\alpha]} = \sum_{d=1}^M\sum_{i=1}^{k}(\alpha_i -1) \left[ \Psi(\gamma_{di}^\ast) - \Psi \Big(\sum_{i=1}^{k} \gamma_{di}^\ast \Big) \right] - M\sum_{i=1}^{k} \log \Gamma (\alpha_i) + M \log \Gamma \Big( \sum_{i=1}^{k} \alpha_i \Big)\]

이를 $\alpha_i$에 대해 미분하면 다음과 같다.

\[\frac{\partial L}{\partial \alpha_i}=\sum_{d=1}^M\left[ \Psi(\gamma_{di}^\ast) - \Psi \Big(\sum_{i=1}^{k} \gamma_{di}^\ast \Big) \right] + M \left[\Psi \Big( \sum_{i=1}^{k} \alpha_i \Big)-\Psi (\alpha_i) \right] \stackrel{let}{=} 0 , \quad i=1,\cdots, k.\]

이 system of equations는 closed form의 해를 바로 찾을 수 없기 때문에, 해를 찾기 위해서는 iterative method를 사용해야한다. 여기서는 linear-time Newton-Raphson 알고리즘을 이용하면 다음과 같다.

Hessian을 구해보면 다음과 같으므로, 위에서 소개한 linear-time Newton-Raphson 방법을 적용하여 $\alpha$의 해를 찾을 수 있다.

\[\frac{\partial^2 L}{\partial \alpha_i \partial \alpha_j}= M \Psi^\prime \Big( \sum_{i=1}^{k} \alpha_i \Big)- \delta(i,j)M \Psi^\prime (\alpha_i) \stackrel{let}{=} 0 , \quad i,j=1,\cdots, k.\]

5.4 Smoothing

실제로 많은 corpora는 포함하고 있는 단어들의 모임(vocabulary)이 매우 크다는 특징이 있어, sparsity와 관련하여 문제가 발생하기 쉽다. 즉 새 document는 기존의 어느 corpus에도 나오지 않은 단어를 포함하고 있을 가능성이 높다는 것이다. Maximum likelihood estimate은 그러한 새로운 단어에 대해 zero probability를 부여하게 된다. 이러한 문제를 해결하기 위한 방법으로는 multinomial parameter를 “smoothing”(부드럽게)하여, vocabulary 내의 모든 가능한 단어들에 대해 positive 확률값을 부여하는 방법이 있다.

위 그림은 Smoothing을 LDA 모형에 적용한 것이다. 이는 topic 별 word probability를 나타내는 $k\times V$ matrix $\beta$를 모수로 보지 않고, $k\times V$ random matrix로 보고, $\eta$를 $\beta$에 대한 모수로 본 것이다. 구체적으로는 다음과 같다.

\[\beta_i = [\beta_{i1}, \beta_{i2}, \cdots, \beta_{iV}]^T \stackrel{iid}{\sim} \text{Dirichlet}(\eta, \eta, \cdots, \eta)\]

이제 $\beta$는 hyperparameter가 아니라 posterior 분포를 갖는 parameter이므로, 5.2-5.3에서 소개한 식들에 약간의 수정이 가해져야 한다. $\beta$의 free variational parameter를 $\lambda$라고 할 때, 새로운 variational distribution은 다음과 같다. 여기서 $q_d(\theta_d, \mathbf z_d \vert \phi_d, \gamma_d)$는 5.2-5.3에서 소개한 것과 같은 variational distribution이다.

\[q(\beta, \theta, \mathbf z \vert \lambda, \phi, \gamma) = \prod_{i=1}^{k} \text{Dirichlet}(\beta_i \vert \lambda_i)\prod_{d=1}^{M} q_d(\theta_d, \mathbf z_d \vert \phi_d, \gamma_d).\]

마찬가지로 variational parameter $\lambda, \phi, \gamma$에 대한 최적화를 한 후, $\lambda^\ast, \phi^\ast, \gamma^\ast$가 주어졌을 때, log-likelihood의 lower bound를 최대화하는 model parameter $\alpha, \eta$를 찾아주면 된다. $\eta$는 $\beta$가 따르는 Dirichlet 분포의 parameter이므로, $\eta$의 estimate을 구하는 방법은 앞의 Dirichlet update에서 소개한 것과 같다.