[KOOC] 인공지능 및 기계학습 개론 10주차 - Sampling Based Inference

Chapter 10. Sampling Based Inference

• 목차

1. basic sampling method
   • Markov chain Monte Carlo
   • apply MCMC to the parameter inference of Bayesian Networks
   • mechanism of rejection sampling
   • mechanism of importance sampling
2. sampling based inference
   • concept of Metropolis-Hastings algorithm
   • mechanism of Gibbs sampling
3. case study of sampling based inference
   • Latent Dirichlet Allocation model
   • collapsed Gibbs Sampling
   • derive Gibbs sampling formula for LDA

 

 

10-1. Basic Sampling methods

 

Forward Sampling

간단한 Baysian network를 살펴보기 위해 이전에 봤던, Alarm/Call 문제를 살펴보자. 이 때, $ P(E = T|MC = T) $ 의 확률을 구하기 위해 E=T와 MC=T의 경우를 카운트하고, MC=T인 경우를 카운트한다. 반복을 엄청 많이 하여 오차를 줄인다.

Gaussian Mixture Model에 대해 forward sampling, 즉 직접 테스트를 통해 카운트하여 확률을 계산하는 방법을 사용하여 확률 그래프를 그려볼 수 있다. GMM에서는 latent factor인 z가 존재하고, 이 z는 π에 의해 mixture distribution을 따르는 지표로서 샘플링된다.

따라서 샘플 x는 $ N(\mu_z,\sum_z) $ 의 정규분포를 따른다. (=$ P(x|z) = N(x|\mu_z, \sum_k) $)

 

 

Rejection Sampling

Rejection sampling이란 많은 반복을 통해 P(E=T|MC=T,A=F) 를 구할 때, 이에 해당하지 않는 샘플들 즉, MC=T이지만, A=F인 경우는 버리고(reject), 다시 반복 샘플링하여 MC=T,A=F인 경우는 카운트한다.

그 후, 최종적인 확률은 카운트한 값에서 전체 샘플의 개수를 나눠주면 된다.

 

rejection sampling을 수치적으로 살펴보자. 먼저 x_i 를 샘플링한다. q(x)는 $ N(\mu_z,\sum_z) $의 정규분포에서 x_i가 샘플링될 확률을 나타낸다. 즉, target distribution이라 할 수 있다.

그 다음, 이 q(x)를 둘러쌀 수 있는 p(x)를 생성하고, p(x)와 q(x)에 상수 m을 곱한 것을 비교하여 상수 u보다 크다면 카운트하고, 그렇지 않다면 카운트하지 않고, 다시 샘플링한다.

 

Q Mixture 부분에서 1/3, 3 부분이 M에 해당하고, 그래프에서 빨간색 선 아래 부분이 rejection region을 나타낸다.

첫번째 그래프의 경우는 p(x) 또한 Mixture distribution으로 모델링하여 target distribution과 거의 유사하게 그려진다. 그러나 두번째 Q mixture 그래프의 경우 단순한 p(x)를 normal distribution으로 생성했기 때문에 target distribution과 다소 다른 모습을 볼 수 있다.

 

 

Importance Sampling

random variable에 의해 생성될 함수에 대한 기대값을 게산해보자.

$ E(f) = \int f(z)p(z) dz = \int f(z)\frac{p(z)}{q(z)}q(z) dz = \frac{1}{L}\sum_{l=1}^L \frac{p(z^l)}{q(z^l)} f(z^l) $

f함수의 기대값 E(f)는 z가 샘플링될 확률 분포 p(z)와 true function인 f(z)를 z에 대해 적분한 것과 같다. 기대값을 정확하게 계산하기 위해서는 true function을 알고 있어야 하므로, f(z)를 알고 있다는 가정이 필요하다.

여기에서 q(z) 라는 계산의 편의를 위해 생성한 정규분포를 따르는 q(z) 를 분모, 분자에 각각 곱해준다. 샘플 z에 대해 무한대가 아닌 1부터 샘플의 개수인 L까지로 범위를 정해서 적분을 하게 되면

$ \sum_{l=1}^L \frac{p(z^l)}{q(z^l)} f(z^l) q(z^l) $

인데, $ \sum_{l=1}^L q(z^l) $ 을 상수 1/L로 근사시키면, 정규화 상수가 된다.

적분이 시그마가 되는 이유는 간단하다. 예를 들어, f(x)=a 이라는 함수에 대해 1부터 L까지 적분을 하면, L x f(x) 가 된다. 이는 풀어쓰면 f(x=1) + f(x=2) + … + f(x=L) 이다.

 

이 때, p(z)/q(z)를 빼고 생각을 해보면, 모든 z값들에 대한 f(z)의 평균을 구하는 식이 되므로, p(z)/q(z)는 중요도 가중치 역할을 수행하게 된다.

 

만약 p와 q가 normalize하지 않다면, 우리가 직접 정규 분포로 만들어주면 된다. 그 방법으로 p(z)에서 z에 대해 1/z_p 를 하고, q에 대해서도 마찬가지로 1/z_q 해주면 된다.

 

만약, Z가 1보다 클 때의 확률을 구하고자 한다면, f(z)를 1보다 클 때는 1, 1보다 작을 때를 0으로 하는 indentity function으로 만들어주면 된다.

 

 

likelihood weight를 적용한 알고리즘의 동작방식은 다음과 같다. 전체 샘플은 오른쪽의 Baysian network를 따르고 있다고 가정한다.

• 목적 : P(E=T|MC=T,A=F) 를 구하고자 함.
• 초기 세팅
  • SumSW = NormSW = 0
• 반복 과정
  1. SW = SampleWeight = 1
  2. sample 생성
  3. if, sample == (A=F|B=F,E=F), JC|A=T, MC=T|A=F : - P(A=F|B=F,E=F) = 0.999 - SW = 1 * 0.999 - P(MC=T|A=F) = 0.01 - SW = 1 * 0.999 * 0.01
  4. if, sample in E=T : - SumSW += SW
  5. NormSW += SW
• Return SumSW/NormSW

 

 

10-2. Sampling Based Inference

Sampling method에서 가장 많이 사용되는 기법이 Gibbs sampling이다. 이 Gibbs sampling은 Metropolis-hastings 알고리즘의 특별한 케이스이다.

이전에 배웠던 EM 알고리즘에서 Expectation step에서는 optimization을 통해 Z를 할당했다. 이제는 sampling 기반으로 Z를 할당해도 잘 수행되는지 살펴보고자 한다.

 

Markov Chain

그리고, 이전에 배웠던 Forward, rejection, importance sampling에서는 현재의 z와 다음 시간에서의 z는 연관이 없었다. metropolis hastings 알고리즘에서는 버련던 instance(sample)들을 활용하여 다음 z를 샘플링하고자 한다. 이 알고리즘을 위해서는 markov chain 개념을 알아야 한다.

 

markov chain에서 각 노드는 state의 확률 분포를 가진다. z_t가 어느 정도의 확률로 할당이 될 것인지에 대한 확률이다.

한 시스템이 3개의 state를 가진다고 가정할 때, 특정 시간 t에서의 확률 P(z_t)는 [a b c] (a,b,c는 확률) 을 가진다.

이 a,b,c는 정확한 관찰이라 생각하면 True=1 또는 False=0으로 할당될텐데, 확률론적으로 생각한다면 각각 0~1의 값을 가진다.

예를 들어, 앞서 살펴봤던 알람과 콜에 대한 baysian network에서 발생할 수 있는 P(z)는 [P(A=T,JC=T) P(A=T,JC=F) P(A=F,JC=T) P(A=F, JC=F)] 라는 4개의 state를 가진다. 각 state는 확률로서 표현된다.

 

현재 시간 t에서의의 P(z_t)와 다음 시간 t+1에서의 P(z_t+1) 을 연결하는 matrix인 transition matrix, $ T_{i,j} $ 가 존재하여, P(z_t) 와 transition matrix를 가지고 있다면, 이후 시간에서의 P를 계산할 수 있다.

 

 

Markov chain의 특성은 접근 가능성(Accessible), 축소/환원성(Reducibility), 주기성(Periodicity), 일시성(Transience), Ergodicity이 있다.

• Accessible
  • i ⇢ j : 샘플링할 때, i state에서 j state로 전의(이동)가 될 확률이 0보다 크다.
  • i ⇹ j : i에서 j로도, j에서 i로도 이동이 가능하다면 i와 j는 양방향(communicate)성을 가진다.

 

• Reducibility
  • 만약, i와 j가 양방향이고, i와 j가 모두 전체 state인 S에 포함된다면, markov chain은 더이상 줄일 수 없는 상태, 즉 irreducible하다.

 

• Periodicity
  • 특정 state i에 방문하는 주기(period)가 4,8,12… 라고 한다면, period d는 전체 period의 최대공약수인 4로 간주한다.
  • 만약 주기가 1,3,4,11,13 이라고 한다면 d=1이 되므로, 이 경우를 aperiodic, 즉 주기가 없다고 정의한다.

 

• Transience
  • X_0 일 때, j state가 할당되었는데, 이후 특정시간에서 다시 j state를 방문한다면 이를 재방문(recurrent)이라 정의한다.
  • 만약 이후 다시는 방문하지 않는 경우를 반대로 transient라 한다.

 

• Ergodicity
  • 한 state가 재방문을 하나, 그게 언제인지는 모를 때, 즉 aeriodic할 때, ergodic이라 한다.
  • 모든 state가 ergodic하다면 markov chain은 ergodic하다.

 

 

Stationary Distribution

markov chain의 특수 케이스인 Stationary Distribution이 metropolis-hastings를 동작시키는 핵심 개념이라 할 수 있다.

$ RT_i $ 는 state i에 방문한 이후 다시 state i에 방문하는 시간 t1,t2,t3 중 가장 작은 값을 의미한다.

 

만약 markov chain이 irreducible 하고 ergodic하다면 즉, 특정 state에 대해 재방문을 하고 state i와 j가 양방향인 상황이라 할 수 있다. 이런 상황에서 stationary distribution, π_i를 정의한다.

$ \pi_i = lim_{n⇢\inf} T_{i,j}^{(n)} = \frac{1}{E[RT_i]}$

이 때, π_i에 대한 조건은 다음과 같다.

$ \pi_i \geq 0,: \sum_{i \in S} π_i = 1, \pi_j = \sum_{i \ in S} \pi_iT_{i,j} $

이 때, S는 state의 개수를 의미하고, 특정 시간 t에서의 π_t 는 latent variable인 z_t와 동일한 역할을 하고, S가 3일 때 π_t = [a, b, c] 의 형태를 가진다.

 

만약 T를 가지고 있는 상황에서 π를 계산할 수 있다. π와 T를 matrix로 생각을 해보면 다음과 같이 구성할 수 있다.

$ \pi(I_{|S|,|S|} - T + 1{|S|,|S|}) = 1{1, |S|} $

이 때, I는 identity matrix, 1은 1로 구성되어 있는 matrix를 의미한다. 이는 위의 조건 두,세번째를 활용하여 구성한 것이다.

 

Reversible Markov chain 또는 balance Equation 이라는 개념이 있다. 오른쪽 위의 코드와 같이 transition matrix(T)가 있을 때 stationary distribution의 특성을 활용하여 π(pi)를 쉽게 구할 수 있다. stationary distribution의 특성 상 πT = π 이므로, 성립되는 것을 볼 수 있다.

state i와 j가 있을 때, i에서 j로 transition 하는 확률과 j에서 i로 transition 하는 확률이 같으면 reversible하다 할 수 있고, 같지 않으면 irreversible하다고 할 수 있다.

$ \pi_i T_{i,j} = \pi_j T_{j,i} $

 

 

이 이론을 활용하여 MCMC(Markov Chain Monte Carlo)를 정의한다. 즉, 원래의 Markov Chain은 stationary distribution, π를 찾는 것이었으나, MCMC에서는 π가 주어진 상태에서 transition matrix를 찾는다.

state i에서의 z_i에서 z_j로 이동하기 위한 transition matrix를 잘 정의하여 stationary distribution을 잘 생성할 수 있게 샘플링해야 한다. 이 때의 z는 state마다 이어져 있는 형태이다.

$ z^{(1)} -> z^{(2)} -> \dots -> z^{(m)} -> \dots -> z^{(m+n)} $

 

예를 들어, 이전의 baysian network Alarm과 JC,MC에 대해 살펴보자. Alarm과 MC가 Evidence, 관측된 값이라 하고, 나머지 3개를 latent variable, Z라 하자. 이 Z를 모두 반복적으로 샘플링하여 True/False를 정한다.

 

 

Metropolis-Hastings Algorithm

stationary distribution을 알고 있는 상황에서 어떻게 transition matrix를 잘 만들어 낼 수 있는지에 대한 알고리즘이 Metropolis-Hastings 알고리즘이다.

MCMC(Markov Chain Mento Carlo)의 일반적인 알고리즘은 현재의 latent variable, z^t가 있고, 현재의 z^t에서 z*로 이동하고자 하며 이 때 z*에 대한 후보로서 q(z*|z^t)를 생성하고, 이 q_t를 proposal distribution 이라 한다.

또한, acceptance probability, α를 정의한다. α에 따라 샘플링한 z*을 받아들일지 버릴지를 결정한다. 받아들인다면 다음 z^t+1은 z*이 되고 버린다면 다시 z^t가 된다.

 

여기서 중요한 것은, 우리가 얻고자 하는 것은 stationary distribution이므로, 우리가 정의한 q를 잘 설정해주어야 한다. 따라서 Metropolis-Hastings 알고리즘에서는 ratio, r(z*|z^t)를 정의하여 q를 잘 설정하고자 했다.

$ r(z|z^t) = \cfrac{q(z^t|z)P(z)}{q(z|z^t)P(z^t)} $

이 때, stationary distribution의 reversible markov chain의 특성을 통해 ratio는 1이 되어야 한다. 만약 ratio가 1보다 작으면 분모가 큰 것이고 이를 잘 생각해보면 z* -> z^t로의 확률은 낮고, z^t -> z*로의 확률이 크다는 것을 알 수 있다. 따라서 ratio를 1로 만들어주기 위해 acceptance probability를 잘 조정해야 한다. 지금은 z^t -> z*에 대한 샘플을 줄이거나 반대를 키워야 하므로 *->t는 1로, t->*는 ratio로 지정한다.

반대로 1보다 크다면 t->*은 1로, *->t는 ratio로 설정한다.

 

결론적으로 acceptance probability는 다음과 같이 정의된다.

$ \alpha(z|z^t) = min{1, r(z|z^t)} $

 

 

t에서 *로의 Transition probability는 $ T_{t,}^{MH} = q(z|z^t) \alpha(z*|z^t) $ 를 만족한다.

우리는 이미 P(z)를 알고 있다고 가정했기에 q(z)에 대해서만 정의해주면 된다. q(z)를 샘플링하는 방법으로 Random walk M-H algorithm 이 있다. 그에 대한 과정은 다음과 같다.

z*을 normal distribution, N(z^t, σ^2)에 대해 랜덤 위치로 샘플링한다. 그러면 q(z*|z^t)는 normal distribution식을 따르게 되고, z*을 받아들일지 말지를 결정한 후, 받아들이면 z^t+1 의 위치는 z*가 되고, 그 후 다시 z^t=z*에 대해 무작위로 z*을 샘플링한다.

 

z*의 normal distribution을 생각해봤을 때, σ가 클수록 큰 폭으로 이동되고, σ가 작을수록 이동하는 폭이 작아진다는 것을 알 수 있다. 그 결과가 위의 그래프이다. Gaussian Mixture model에 대해 샘플링하고 있으며, 맨 위가 true distribution이고, 중간이 latent, z^t를 나타내고 있다. 그래프에서 볼 수 있듯이 σ가 작으면 샘플링되는 폭도 작아서 변화하는 폭이 작다.

 

 

Gibbs Sampling

Gibbs sampling이란 Metropolis Hastings의 특별 케이스라 할 수 있다. z^t는 state의 개수만큼 vector형태로 존재하는데, 이에 대해 각 샘플링마다 1개의 state만을 업데이트하고자 했다. 업데이트하는 것을 $ z_k^t $라 했을 때, 나머지 업데이트되지 않는 것은 $ z_{-k}^t $ 로 표현한다. 그렇다면 z*으로 업데이트를 하고 난 후에는 z*과 변화하지 않은 z_{-k}^t가 있을 것이다.

이런 과정을 MH 알고리즘에 적용하면

$ q(z|z^t) = P(z_k,z_{-k}^t|z_{-k}^t) = P(z_k*|z_{-k}^t) $

reversible markov chain을 만족시켜야 하므로 $ P(z^t)q(z|z^t) = P(z)q(z^t|z*) $ 가 되어야 한다. 따라서

$ P(z^t)q(z|z^t) = P(z_k^t,z_{-k}^t)P(z_k|z_{-k}^t) = P(z_k^t|z_{-k}^t)P(z_{-k}^t)P(z_k*|z_{-k}^t) $

joint probability를 condition probability형태로 변환한 후 이를 다시 joint probability로 변환한다. P(z_k, z_{-k}^t) 는 어차피 z^t만 업데이트했으므로 P(z)와 같으므로 변환하고, *에서 t로 오는 것은 P(z_k^t|z_{-k}^t) 와 같으므로 변환하면 원래의 balance equation을 만족하게 된다.

따라서 항상 balance equation을 만족하므로, acceptance probability를 사용하지 않아도 된다. gibbs sampling에서는 acceptance probability를 사용하지 않으므로 받아들일지 말지를 판단하지 않고 무조건 수용한다.

 

Alarm/Call에 대한 baysian network에 Gibbs sampling을 적용해보자. Alarm, Marycall이 관찰되 상황에서 buglary, johncall, earthquake를 latent variable이라 생각했을 때 먼저 Buglary만을 업데이트하고자 한다면 Markov blanket을 통해 alarm과 earthquake만 알고 있다면 나머지는 연관이 없다.

또한, johncall을 업데이트할 때, Alarm만 알고 있다면 나머지의 variable에 대해서는 연관성이 없다. Alarm은 이미 알고 있는 값이므로 JC만 true/false를 선택하여 적용하면 업데이트할 수 있다.

 

 

gibbs sampling의 개념을 좀 더 자세히 살펴보자. 1번의 step마다 1개의 variable만을 변경시키는 기법으로서 최종적인 과정과 그림은 위 사진의 하단과 같다.

 

 

Gibbs sampling의 과정을 자세히 살펴보자.

1. i=1에서의 z_i를 초기화한다.
2. step을 T번 반복한다.
3. 각 step마다 1개의 state만 변경시킨다.

 

 

이러한 gibbs sampling의 과정을 그래프화하면 위와 같다. Gaussian Mixture Model에 gibbs sampling을 적용하게 되면, EM(expectation, maximiation step)보다 수렴이 다소 느리다. 그러나 EM은 local optima에 빠지기 쉽지만, Gibbs sampling은 local에 빠질 확률이 EM보다 적다.

 

 

10-3. Latent Dirichlet Allocation

Topic Modeling

자연어처리에서 가장 많이 사용되는 기법이다. 여러 개의 단어들을 주고, 이에 대한 latent variable을 추론하여 각 단어의 의미를 분석한다.

 

 

Latent Dirichlet Allocation

Latent Dirichlet Allocation은 텍스트 데이터에 대해 soft clustering하고 baysian model을 따른다.

오른쪽 baysian network에서 α는 prior에 해당한다. 이 α는 dirichlet distribution을 따르는 형태를 지니고 있다. 이 distribution에서 문저에 대한 assignment인 θ가 존재한다. z는 latent variable을 의미하여 단어별 topic assignment, 즉 어떤 의미를 지니는지에 대한 숨은 의미에 대한 할당이다. β도 prior 정보를 의미하고, φ는 topic별 등장할 단어의 확률로 gaussian mixture model에서 개별 cluster에 대한 gaussian distribution으로 모델링하는 부분이다. K는 topic의 개수를 의미한다. M은 문서의 개수, N는 한 문서에서의 단어의 개수이다. w는 evidence 즉 문서에서의 실제 단어를 의미한다.

 

특정 문장을 생성하는 프로세스는 다음과 같다.

• Dir : dirichlet distribution
• Multi : multinomial distribution
• α : dirichlet distribution prior, 전체 corpus의 topic distribution에 대한 값이다.
• θ : 문서 레벨의 topic assignment, 특정 문서에 대한 topic assignment들의 비율을 나타낸다.
• β : dirichlet distribution prior, 개별 단어들마다 어떤 토픽에 어떤 단어가 얼마나 사용될지에 대한 확률의 사전 지식
• φ : 어떤 토픽이 어느 정도의 확률로 등장할지에 대한 값
• z : 특정 cluster에 대해 선택되는 latent variable, topic별 assignment를 나타낸다.
• w : 어떤 주제에서 어떤 단어를 선택할지에 대한 pi를 인자로 받아 하나의 단어를 선정한다.

 

만약 Z를 안다면, α prior을 활용하여 θ를 구할 수 있고, β prior,z,w들을 통해 pi도 구할 수 있다.

따라서 Z를 구하는 것이 topic modeling에 가장 중요한 부분을 차지한다.

 

그렇다면 Z에 대해 어떻게 잘 할당(allocation)하는지에 대해 알아야 할 것이고, 이것이 Gibbs sampling을 하는 이유이다.

확률을 구하기 위해 가장 먼저해야 할 부분은 factorization이다. 모든 변수와 prior를 표현하여 확률을 나타낸다. 이 때, ;는 뒤의 내용이 사전 정보(prior)라는 것을 나타낸다. 앞서 정의했던 texture modeling에 대한 baysian network을 활용하여 factorization한다.

$ P(W,Z,\theta, \phi; \alpha, \beta) = \prod_{i=1}^K P(\phi_i;\beta) \prod_{j=1}^M P(\theta_j;\alpha) \prod_{l=1}^N P(Z_{j,i}|\theta_j) P(W_{j,l}|\phi_{Z_{j,l}}) $

먼저 베타는 φ에 영향을 주고, φ는 K개만큼 존재한다. 따라서 P(φ_i;β)를 i=1~K에 대해 곱셈한다. 이는 P(φ|β)P(β)와 같고, α에 대해서도 동일하게 만들어 줄 수 있다. 그리고 나서 Z는 θ에 의해 생성되고, M 공간 안에서 N공간에도 포함되므로 M과 N이라는 값에 대해 꽤 많은 곱셈이 진행된다. 그 후 마지막으로 W에 대해서도 작성해주어야 하므로, W에 대해 작성하는데, φ에 대한 k는 토픽의 개수를 의미하고, 토픽의 할당값은 Z에 의해 결정되므로 φ의 아래첨자는 Z가 된다.

 

위의 식에서 우리가 최종적으로 계산하기 위해서는 θ와 φ를 제거해야 한다. 그 이유는 θ와 φ 이외의 파라미터는 W,Z,α,β 인데, W는 관측지, Z는 최종적으로 구해야 할 값, α,β는 사전 정보이므로 이것들을 제거하는 것은 옳지 않다. 또한, 추후 Z를 구하고 나면 자연스럽게 θ와 φ를 구할 수 있다. 따라서 식을 간편화하기 위해 θ와 φ를 제거하고, 이러한 방식을 Collapsed Gibbs sampling이라 한다.

θ,φ를 제거하기 위해 Marginalization을 수행한다. 전체 joint 확률에 대해 적분을 수행하여 marginalize한다. 이를 위에서 구했던 식을 활용하여 간편화할 수 있다. 4개의 값들은 각각 θ에만 연관되어 있는 것과 φ에만 연관되어 있는 것들이 나뉘어져 있다.

$ P(W, Z;\alpha, \beta) = \int_\theta \int_\phi P(W,Z,\theta,\phi;\alpha,\beta) d\phi d\theta = \int_{\phi} \prod_{i=1}^K P(\phi_i;\beta) \prod_{j=1}^M \prod_{l=1}^N P(W_{j,l;\phi_{Z_{j,l}}} d\phi : \times : \int_\theta \prod_{j=1}^M P(\theta_j;\alpha) \prod_{l=1}^N P(Z_{j,l}| \theta_j) d\theta $

이렇게 나눌 수 있는 이유는 원래의 식에서 모든 연산은 곱셈이고, θ와φ는 서로 독립적이기 때문에 가능하다.

 

이러한 2개의 변수에 대한 식을 나눠서 θ에 대한 식을 1번, φ에 대한 식을 2번으로 생각하여 각각을 풀어본다. 먼저 1번에 대한 과정이 위와 같다.

φ는 간단하게 3x4 행렬이라 치면 열 방향으로는 topic의 구분, 행방향으로는 단어의 구분으로 구성되어 있다. 즉 하나의 행에는 같은 topic에 대한 확률이고, 하나의 열에는 다양한 topic별 단어들에 대한 확률이 포함되어 있다. 이 때, 하나의 행을 모두 더하면 1이 된다.

그래서 φ_i 은 i번째 행에 대한 값들을 의미하고, φ_Z 는 특정 토픽에서의 하나의 단어를 가리키고 있다.

φ의 각 원소들은 서로 독립적이므로 계산된 값에서 곱셈을 하고 적분을 하는 것과, 적분을 하고 곱셈을 하는 것은 같으므로 곱셈을 밖으로 내보낼 수 있다.

 

β로 인해 만들어지는 φ는 dirichlet distribution에서 추출되는 확률이고, φ에 의해 만들어지는 W는 multinomial distribution이므로 이 둘을 동일하게 맞춰줘야 한다. 그래서 두 distribution의 정의를 알고 이를 풀어줘야만 한다.

α에 대한 dirichlet distribution x에 대한 확률은 다음과 같다.

이 때의 K는 dirichlet 의 dimension이고, 이 경우는 세 개의 dimension이 있으므로 k=3이다. φ_i의 dimension은 단어의 크기에 해당한다.

 

여기서 추가 트릭이 더 필요하다. $ n_{j,r}^i $ 의 개수를 세는 것으로, 이는 j번째 문서에서 전체 단어 R idx 중 r idx의 특정 단어가 i번째 토픽에 할당된 단어의 수 이다. 예를 들어, 100개의 문서에서 kaist라는 단어가 3번 나왔다고 한다면, 5(j)번째 문서에서 kaist가 토픽들에 대해 각각 몇 개의 kaist가 할당되었는지에 대한 개수이다. 따라서 만약 전체 토픽들중 kaist가 17(r)번째 단어이고, 토픽 1(i)에 2번이 할당되었다면, $ n_{j,17}^1 $ = 2 가 된다.

 

$ φ_{i,v} $는 특정 i번쨰 topic에 v번째 단어, 즉 i열 v행 단어의 등장 확률인데, 이 값이 몇번 등장했는지를 세다면 $ φ_{i,v}^{n_{(.),v}^i} $ 가 되고, 이는 모든 문서(M)에 대해 i번째 토픽에 v번째 단어가 등장하는 횟수에 대해 곱셈을 하는 것을 의미한다. 전체 문서의 단어 별로 등장 확률을 등장 횟수를 자승하여 곱해준다. 이는 단어 W_i,j에 대해 한 문서의 단어 갯수만큼 곱한 것에 전체 문서의 수만큼 곱해주는 것과 동일하다.

 

이렇게 변형하고 나면, 곱셈을 하는 차원이 앞부분과 같아지게 되고, 이를 합쳐준다. 합쳐주고 나면, 이 형태를 다시 $ \alpha = n_{(.),v}^i + \beta_v $ 인 dirichlet distribution 형태로 만들어 줄 수 있어 보인다. 이를 위해 분모 분자에 각각 형태에 맞게 곱해준다.

dirichlet distribution에 대해 적분하는 형태인데, 이는 즉 확률을 모두 더한다는 것과 같고, 그러면 1이 되어 적분 부분이 사라지게 된다.

 

 

이번에는 2번에 대해 식을 풀어주자. 이번에도 theta들은 각각 독립적이므로 θ_j로 다 적분을 한 후 곱셈을 해도 상관없다. 이번에도 동일하게 dirichlet distribution의 식과 n을 통해 식을 간편화한다. 이 때, theta_i는 어떤 문서의 토픽 distribution을 의미하므로 dirichlet distribution에서의 K=dimension은 토픽의 개수가 된다. 그리고 n에서의 단어는 상관하지 않으므로 (.) 가 된다.

 

이렇게 n에 대해서 적용을 하면 dirichlet distribution에서의 α 를 $ n_{j,(.)}^i + α_i $로 치환하여 식을 간편화할 수 있다. $ {\color{DarkRed} (이 때, α_k가 아닌 α_i 가 맞음)} $

1번식에서와 동일하게 치환을 위해 분모 분자에 각각 알맞게 곱해주고 나면, 적분 부분이 1이 되어 사라진다.

 

 

이렇게 θ와 φ를 제거할 수 있게 되었는데, 제거할 수 있었던 가장 큰 이유는 dirichlet distribution과 multinomial distribution의 곱셈이 다시 dirichlet distribution의 형태가 되었음에 있다.

이를 간단하게 작성해보면 P(X|θ) x P(θ) 이고, 이 likelihood와 prior의 곱셈이 prior distribution을 만들어내는 과정을 Conjugate prior관계라고 한다. 이 관계를 통해 Collapse Gibbs sampling을 수행할 수 있게 되었다.

 

 

이러한 상황에서 target인 Z에 대해 한번의 반복마다 하나의 state에 대해서만 업데이트하는 Gibbs sampling을 수행한다. 그렇기에 m번째 문서의 l번째 토픽 할당에 대한 식으로 변형해주어야 한다. $ P(Z_{(m,l)} = k | Z_{-(m,l)},W;\alpha, \beta) $

이를 joint로 변형을 해주면 분모에 있는 값은 k에 영향을 받지 않으므로 normalizing constant로 간주할 수 있다.

 

그 후, prior에 대해서만 변수로 존재하는 것들은 모두 곱셈 밖으로 꺼낼 수 있으며, 이는 상수로 간주할 수 있어 비례 형태로 치환할 수 있다. 그런 다음, 우리는 Gibbs sampling을 적용하므로 m번째 문서의 l번째 토픽에만 관심이 있으므로, 곱셈에서 M=m으로, V=l로 고정시켜본다. 또한, m번째 문서로 고정한 상태에서 단어들에 대해 덧셈을 하는 과정이고, 토픽 할당에 대해 이전의 값에서 현재의 값으로 변화하는 것이므로 이전의 값은 -1, 현재의 값은 1로 할당하게 되어 결국은 상수로 존재하게 된다.

 

그 후, z에 대해 m번째의 l번째 단어를 제외한 나머지들의 n을 구한다. 그리고는 K에 대한 곱셈을 K=k를 분리하여 식을 세운다. 이 때, k를 분리했을 때는 K=k를 제외한 값에서 K=k에 대한 할당 값이 1개 늘어나는 것이므로 K=k를 제외한 계산식에서 개수를 +1해주면 된다.

그 다음, $ \gamma $ 식의 정의를 활용하고자 한다. $ \gamma(x) = (x - 1)! $ 이고, 따라서 $ \gamma(x+1) = x! = (x-1)! \times x = \gamma(x) \times x $ 이므로, 아까 더해주었던 +1을 분리시켜 줄 수 있다.

 

+1에 대한 값을 분리해주고 나면, 결국 K=k를 제외한 계산식과 다시 결합을 할 수 있게 된다. $ {\color{DarkRed} (이 때도 α_k가 아닌 α_i 가 맞음)} $

이러고 나면, 4개의 값들의 곱셈 중 앞의 2개의 값들은 k와 아무런 연관이 없으므로 상수이기에 비례식으로 제거해줄 수 있다.

 

최종적으로 Z를 샘플링하는 데 n을 사용함으로서 각 단어가 어디에 할당되는지 개수를 세어 특정 l번째 단어가 k에 할당될 확률을 구할 수 있다.

 

 

최종적으로 LDA를 프로그래밍적 관점에서 살펴보면, 간단해진다. LDA의 과정은 다음과 같다.

• 입력 : TextCorpus T, prior α, prior β
  1. 무작위로 Z를 초기화한다.
  2. 무작위로 할당된 Z를 통해 간 문서별 토픽별 단어별로 n을 계산한다.
  3. 아래 과정을 수렴 할 때까지 반복한다.
  4. m=1부터 문서의 개수만큼 아래 과정을 반복
  1. l=1부터 m번째 문서에서의 단어의 개수만큼 아래 과정을 만복
     1. $ P(Z_{(m,l) = K}|Z_{-(m,l)},W;\alpha, \beta) $ 식을 통해 K를 샘플링한다.
     2. Z_(m,l) = k 로 할당되어 있는 단어들에 대해 n을 계산한다.
     3. Perplexity 기법을 통해 성능을 평가한다.
     4. θ와 φ를 계산한다. - φ : 각 word 별 topic의 probability - θ : 특정 문서에서 단어들의 토픽 할당을 평균내어 생성
     5. θ와 φ 반환

 

perplexity란 두 개의 모델이 있을 때 비교하는 기법으로 자연어처리에 많이 사용된다. 이를 줄여 PPL이라고도 하는데, PPL 수치가 낮을수록 성능이 좋다.