잠재 디리클레 할당

자연어 처리에서 잠재 디리클레 할당(Latent Dirichlet allocation, LDA)은 주어진 문서에 대하여 각 문서에 어떤 주제들이 존재하는지를 서술하는 대한 확률적 토픽 모델 기법 중 하나이다. 미리 알고 있는 주제별 단어수 분포를 바탕으로, 주어진 문서에서 발견된 단어수 분포를 분석함으로써 해당 문서가 어떤 주제들을 함께 다루고 있을지를 예측할 수 있다.

개요

LDA는 이산 자료들에 대한 확률적 생성 모형이다. 문자 기반의 자료들에 대해 쓰일 수 있으며 사진 등의 다른 이산 자료들에 대해서도 쓰일 수 있다. 기존의 정보 검색분야에서 LDA와 유사하게 문헌 내의 잠재적인 의미구조를 파악하려는 시도들은 계속 이루어져 왔다. TF-IDF를 필두로 하여 잠재 의미 분석(Latent semantic indexing, LSI), 확률 잠재 의미 분석(Probabilistic latent semantic analysis, pLSA)등을 거쳐 LDA로 도달하게 되었고, 이는 토픽 모델링이라 불리는 분야를 탄생시켰다. 확률 잠재 의미 분석은 확률 잠재 의미 인덱싱(probabilistic latent semantic indexing, pLSI) 라고도 한다.

LDA에는 몇 가지 가정이 있는데 그 중 중요한 것은 단어의 교환성(exchangeability)이다. 이는 '단어 주머니(bag of words)'라고 표현하기도 한다. 교환성은 단어들의 순서는 상관하지 않고 오로지 단어들의 유무만이 중요하다는 가정이다. 예를 들어, 'Apple is red'와 'Red is apple' 간에 차이가 없다고 생각하는 것이다. 단어의 순서를 무시할 경우 문헌은 단순히 그 안에 포함되는 단어들의 빈도수만을 가지고 표현이 가능하게 된다. 이 가정을 기반으로 단어와 문서들의 교환성을 포함하는 혼합 모형을 제시한 것이 바로 LDA이다. 하지만 단순히 단어 하나를 단위로 생각하는 것이 아니라 특정 단어들의 묶음을 한 단위로 생각하는 방식(n-gram)으로 LDA의 교환성 가정을 확장시킬 수도 있다.

LDA는 문헌의 주제를 찾기 위한 방법으로 고안되었지만, 이미지, 소리 등 텍스트 처리 이외의 다양한 분야에 쓰일 수 있고 이산 자료들, 즉 불연속적인 자료들뿐만 아니라 연속적인 자료들에 대해서 적용할 수 있고 또한 다항 분포가 아닌 자료들에 대해서도 적용할 수 있는 가능성이 있다.

역사

데이비드 블라이(David M. Blei), 앤드류 응(Andrew Y. Ng), 마이클 어윈 조던(Michael I. Jordan)은 기존 pLSI가 문서 수준에서 확률 모형이 없었던 점을 보완하여 2003년 잠재 디리클레 할당(Latent Dirichlet Allocation)을 제시하였다. 이후 2009년 병렬 잠재 디리클레 할당(PLDA: Parallel Latent Dirichlet Allocation)을 Yi Wang 이 MPI와 맵리듀스(MapReduce)를 이용하여 병렬분산처리가 가능하도록 구현하였다. 2010년에는 온라인 변분 베이즈 알고리즘(online varational Bayes algorithm)을 매튜 호프만(Matthew Hoffman), 프랜시스 바흐(Francis R. Bach), 데이비드 블라이(David M. Blei)가 고안하여, 잠재 디리클레 할당의 온라인 기계 학습 방법을 제시하였다.

LDA에서의 주제

LDA에서 각각의 문서는 여러개의 주제를 가지고 있다. 확률 잠재 의미 분석 (Probabilistic latent semantic analysis, pLSA) 와 비슷하지만 주제들이 디리클레 분포를 따른다고 가정한다.

예를 들어 [양자역학, 힉스 입자, 맥스웰 방정식, 상대성 이론, 불확정성 원리]등의 단어들이 많이 쓰인 문서와 [셰익스피어, 톨스토이, 파우스트, 1984]등의 단어들이 많이 쓰인 문서가 있다고 해보자. 우리는 첫번째 문서가 물리학에 관련된 내용이고, 두번째 문서가 문학에 관련된 내용으로 추측할 수 있다. 그 이유는 우리는 문서에 들어가 있는 단어들이 해당 해당 주제들을 표현하고 있음을 알기 때문이다. 이러한 사전 정보가 없다면 주제를 예측할 수 없다. 하지만 사전정보가 없어도 단어들과 주제들은 연관성이 있다. 주제는 의미나 인식으로 결정되는 것이 아니고, 지도 학습으로 라벨링된 단어들의 가능도로 결정된다.

모형

LDA의 그래프 도식

$M$개의 문서가 주어져 있고, 모든 문서는 각각 $k$개의 주제 중 하나에 속할 때,

• 단어는 이산 자료의 기본 단위로 단어집(vocabulary)의 인덱스로 나타낼 수 있다. 단어집의 크기를 $V$라 하면, 각각의 단어는 인덱스 $v\in \{1,\dots ,V\}$로 대응된다. 단어 벡터 $w$는 $V$-벡터로 표기하며 $w^{v}=1,w^{u}=0,u\neq v$를 만족한다.
• 문서는 $N$개의 단어의 연속으로 나타내며, $\mathbf {w} =(w_{1},w_{2},\dots ,w_{N})$으로 표기한다.
• 전집은 $M$개의 문서의 집합으로 나타내며, $D=\{\mathbf {w_{1}} ,\mathbf {w_{2}} ,\dots ,\mathbf {w_{M}} \}$으로 표기한다.

LDA는 각각의 문서 $\mathbf {w} \in D$에 대해 다음과 같은 생성 과정을 가정한다.

1. $N\sim \mathrm {Poisson} (\xi )$ 을 선택한다.

2. $\theta \sim \mathrm {Dir} (\alpha )$를 선택한다.

3. 문서 내의 단어 $w_{n}\in \mathbf {w}$ 에 대해서

(a) $z_{n}\sim \mathrm {Multinomial} (\theta )$를 선택한다.

(b) $z_{n}$이 주어졌을 때 $w_{n}$는 $p(w_{n}|z_{n},\beta )$ 로부터 선택한다.

생성 과정에서 각각의 변수는 다음과 같은 의미를 가진다.

• $\alpha$는 $k$ 차원 디리클레 분포의 매개변수이다.
• $\theta$는 $k$ 차원 벡터이며, $\theta ^{i}$는 문서가 $i$번째 주제에 속할 확률 분포를 나타낸다.
• $z_{n}$는 $k$ 차원 벡터이며, $z_{n}^{i}$는 단어 $w_{n}$이 $i$번째 주제에 속할 확률 분포를 나타낸다.
• $\beta$는 $k\times V$ 크기의 행렬 매개변수로, $\beta _{ij}$는 $i$번째 주제가 단어집의 $j$번째 단어를 생성할 확률을 나타낸다.

여기에서 $w_{n}$는 실제 문서를 통해 주어지며, 다른 변수는 관측할 수 없는 잠재 변수이다.

이 모형은 다음과 같이 해석될 수 있다. 각 문서에 대해 $k$개의 주제에 대한 가중치 $\theta$가 존재한다. 문서 내의 각 단어 $w_{n}$은 $k$개의 주제에 대한 가중치 $z_{n}$을 가지는데, $z_{n}$은 $\theta$에 의한 다항 분포로 선택된다. 마지막으로 실제 단어 $w_{n}$이 $z_{n}$에 기반하여 선택된다.

잠재 변수 $\alpha$, $\beta$가 주어졌을 때 $\theta$, $\mathbf {z} =\{z_{1},\dots ,z_{N}\}$, $\mathbf {w}$에 대한 결합 분포는 다음과 같이 구해진다.

$p(\theta ,\mathbf {z} ,\mathbf {w} |\alpha ,\beta )=p(\theta |\alpha )\prod _{n=1}^{N}p(z_{n}|\theta )p(w_{n}|z_{n},\beta ),$

여기서 $z_{n}$과 $\theta$를 모두 더하여 문서의 주변 분포 (marginal distribution)를 구할 수 있다. 이 때 디 피네치의 정리 (de Finetti's theorem)에 의해 단어가 문서 안에서 교환성을 가지는 것을 확인할 수 있다.

$p(\mathbf {w} |\alpha ,\beta )=\int p(\theta |\alpha )\left(\prod _{n=1}^{N}\sum _{z_{n}}p(z_{n}|\theta )p(w_{n}|z_{n},\beta )\right)d\theta$

마지막으로 각각의 문서에 대한 주변 분포를 모두 곱하여 전집의 확률을 구할 수 있다.

$p(D|\alpha ,\beta )=\prod _{d=1}^{M}\int p(\theta _{d}|\alpha )\left(\prod _{n=1}^{N_{d}}\sum _{z_{dn}}p(z_{dn}|\theta _{d})p(w_{dn}|z_{dn},\beta )\right)d\theta _{d}$

기존의 잠재 변수 모형과의 차이점

LDA 이전에도 다양한 잠재 변수 모형(latent variable model)이 제시되어 왔다. 아래에서는 그 중 대표적인 유니그램 혼합(mixture of uni-grams) 모형, pLSI 모형과의 차이점을 서술한다.

유니그램 혼합 모형

유니그램 혼합 모형은 다음과 같은 생성 과정을 가정한다.

1. $z$로부터 문서의 주제를 선택한다.

2. 문서의 주제가 주어졌을 때 $w_{n}$은 $p(w_{n}|z)$ 로부터 선택한다.

위 과정으로부터 문서의 확률을 구하면 다음과 같다.

$p(\mathbf {w} )=\sum _{z}p(z)\prod _{n=1}^{N}p(w_{n}|z)$

유니그램 혼합 모형의 생성 과정은 각각의 문서가 정확히 하나의 주제를 가진다는 것을 가정한다. 따라서 문서의 개수가 많아질 때 전집을 효율적으로 모형화할 수 없다는 단점이 있다. 반면, LDA는 하나의 문서에 대해 여러 개의 주제가 서로 다른 가중치로 혼합되는 것을 허용한다.

pLSI 모형

pLSI 모형은 다음과 같은 생성 과정을 가정한다.

1. 문서의 주제 분포 $d$로부터 주제 $z$를 선택한다.

2. 주제 $z$가 주어졌을 때 $w_{n}$은 $p(w_{n}|z)$ 로부터 선택한다.

위 과정으로부터 문서와 단어가 나올 결합 확률을 구하면 다음과 같다.

$p(d,w_{n})=p(d)\sum _{z}p(w_{n}|z)p(z|d)$

pLSI 모형은 $p(z|d)$를 통해 하나의 문서가 여러개의 주제를 가질 수 있도록 허용한다. 그러나 $d$는 트레이닝 셋에 속한 문서들에 대한 인덱스이기 때문에 $p(z|d)$는 트레이닝 셋에 포함된 문서에 대해서만 정의된다. 따라서 pLSI 새로운 문서에 대한 확률을 계산할 수 없으며, 이 때문에 잘 정의된(well-defined) 생성 모형이 아니다.

또한 pLSI에서 각각의 주제는 $V\times M$ 크기의 혼합(mixture)으로 정의된다. 따라서 $k$개의 주제에 대해 $kV+kM$ 개의 매개변수를 필요로 하며, 이는 전집의 크기 $M$에 대해 선형적으로 증가한다. 따라서 트레이닝 셋의 크기가 커질 때 모형이 과적합(overfitting)되기 쉽다.

반면, LDA는 잘 정의된 생성 모형이기 때문에 새로운 문서에 대해서도 쉽게 일반화될 수 있다. 또한 각각의 주제가 $V$ 크기의 혼합으로 정의되기 때문에, $k$개의 주제에 대해 전집의 크기와 무관하게 $k+kV$ 개의 매개변수를 필요로 한다. 따라서 pLSI와 같은 과적합 문제를 겪지 않는다.

추론

LDA를 사용하기 위해서는 문서가 주어졌을 때 잠재 변수에 대한 사후 확률을 구할 수 있어야 한다.

$p(\theta ,\mathbf {z} |\mathbf {w} ,\alpha ,\beta )={\frac {p(\theta ,\mathbf {z} ,\mathbf {w} |\alpha ,\beta )}{p(\mathbf {w} |\alpha ,\beta )}}$

$p(\mathbf {w} |\alpha ,\beta )={\frac {\Gamma (\sum _{i}\alpha _{i})}{\prod _{i}\Gamma (\alpha _{i})}}\int \left(\prod _{i=1}^{k}\theta _{i}^{\alpha _{i}-1}\right)\left(\prod _{n=1}^{N}\sum _{i=1}^{k}\prod _{j=1}^{V}(\theta _{i}\beta _{ij})^{w_{n}^{j}}\right)d\theta$

그러나 이 분포는 잠재 변수인 $\theta$와 $\beta$의 결합 형태를 더하기 때문에 일반적으로 계산하기 어렵다. 따라서 사후 확률을 구하기 위한 다양한 근사 알고리즘이 사용된다. 처음 제시된 LDA에서는 볼록 기반 변분 알고리즘(convexity-based variational algorithm)을 사용하였으며, 다른 접근 방법으로는 기브스 표집과 기대 전파법(expectation propagation)을 사용할 수도 있다.

볼록 기반 변분 알고리즘

볼록 기반 변분 알고리즘의 기본 아이디어는 옌센 부등식을 기반으로 로그 가능도(log likelihood)의 하한값을 계산하는 것이다. 로그 가능도의 하한값은 변분 매개 변수(varional paremeter)로 나타내지며, 이 매개변수는 최적화 과정을 통해 가장 좋은 하한값을 가지도록 정해진다.

이 알고리즘을 LDA에 적용하기 위해서는 LDA의 그래프 도식을 간단화시켜야 한다. $p(\mathbf {w} |\alpha ,\beta )$에서 $\theta$와 $\beta$의 결합을 제거해야 하므로, 기존의 그래프 도식에서 $\theta$, $\mathbf {z}$, $\mathbf {w}$ 사이의 간선을 제거한 뒤 변분 매개변수 $\gamma$와 $\phi =(\phi _{1},\dots ,\phi _{N})$을 추가한다. $\gamma$는 디리클레 분포의 매개변수이며, $\phi$는 다항 분포의 매개변수이다. 이 때 변분 매개 변수에 대한 $\theta$와 $\mathbf {z}$의 조건부 확률은 다음과 같다.

$q(\theta ,\mathbf {z} |\gamma ,\phi )=q(\theta |\gamma )\prod _{n=1}^{N}q(z_{n}|\phi _{n})$

이것을 바탕으로 임의의 $q(\theta ,\mathbf {z} |\alpha ,\beta )$에 대해 문서의 로그 가능도의 하한값을 구할 수 있다.

${\begin{aligned}\log p(\mathbf {w} |\alpha ,\beta )&=\log \int \sum _{\mathbf {z} }p(\theta ,\mathbf {z} ,\mathbf {w} |\alpha ,\beta )d\theta \\&=\log \int \sum _{\mathbf {z} }{\frac {p(\theta ,\mathbf {z} ,\mathbf {w} |\alpha ,\beta )q(\theta ,\mathbf {z} )}{q(\theta ,\mathbf {z} )}}d\theta \\&\geq \int \sum _{\mathbf {z} }q(\theta ,\mathbf {z} )\log p(\theta ,\mathbf {z} ,\mathbf {w} |\alpha ,\beta )d\theta -\int \sum _{\mathbf {z} }q(\theta ,\mathbf {z} )\log q(\theta ,\mathbf {z} )d\theta \\&=\mathrm {E} _{q}[\log p(\theta ,\mathbf {z} ,\mathbf {w} |\alpha ,\beta )]-\mathrm {E} _{q}[\log q(\theta ,\mathbf {z} )]\end{aligned}}$

위의 식에서 우변을 $L(\gamma ,\phi ;\alpha ,\beta )$라 표기하자. 그러면 좌변과 우변의 차이가 쿨백-라이블러 발산임을 이용하여 다음과 같이 나타낼 수 있다.

$\log p(\mathbf {w} |\alpha ,\beta )=L(\gamma ,\phi ;\alpha ,\beta )+D(q(\theta ,\mathbf {z} |\gamma ,\phi )||p(\theta ,\mathbf {z} |\mathbf {w} ,\alpha ,\beta ))$

따라서 문서의 로그 가능도의 하한값인 $L(\gamma ,\phi ;\alpha ,\beta )$을 최대화 하는 것은 변분 사후 확률과 기존의 사후 확률간의 쿨백-라이블러 발산값을 최소화하는 것과 동치이다.

$(\gamma ^{*},\phi ^{*})=\arg \min _{(\gamma ,\phi )}D(q(\theta ,\mathbf {z} |\gamma ,\phi )||p(\theta ,\mathbf {z} |\mathbf {w} ,\alpha ,\beta ))$

최적화 과정을 유도하기 위해 $L(\gamma ,\phi ;\alpha ,\beta )$을 모델 매개 변수 $(\alpha ,\beta )$와 변분 매개 변수 $(\gamma ,\phi )$에 관한 식으로 나타내면 다음과 같다.

${\begin{aligned}L(\gamma ,\phi ;\alpha ,\beta )&=\mathrm {E} _{q}[\log p(\theta |\alpha )]+\mathrm {E} _{q}[\log p(\mathbf {z} |\theta )]+\mathrm {E} _{q}[\log p(\mathbf {w} |\mathbf {z} ,\beta )]-\mathrm {E} _{q}[\log q(\theta )]-\mathrm {E} _{q}[\log q(\mathbf {z} )]\\&=\log \Gamma (\sum _{j=1}^{k}\alpha _{j})-\sum _{i=1}^{k}\log \Gamma (\alpha _{i})+\sum _{i=1}^{k}(\alpha _{i}-1)(\Psi (\gamma _{i})-\Psi (\sum _{j=1}^{k}\gamma _{j}))\\&+\sum _{n=1}^{N}\sum _{i=1}^{k}\phi _{ni}(\Psi (\gamma _{i})-\Psi (\sum _{j=1}^{k}\gamma _{j}))\\&+\sum _{n=1}^{N}\sum _{i=1}^{k}\sum _{j=1}^{V}\phi _{ni}w_{n}^{j}\log \beta _{ij}\\&-\log \Gamma (\sum _{j=1}^{k}\gamma _{j})+\sum _{i=1}^{k}\log \Gamma (\gamma _{i})-\sum _{i=1}^{k}(\gamma _{i}-1)(\Psi (\gamma _{i})-\Psi (\sum _{j=1}^{k}\gamma _{j}))\\&-\sum _{n=1}^{N}\sum _{i=1}^{k}\phi _{ni}\log \phi _{ni}\end{aligned}}$

여기서 $\Psi$는 다이감마 함수(digamma function)이다.

변분 다항 분포 매개 변수의 최적화

우선 $L(\gamma ,\phi ;\alpha ,\beta )$을 $\phi _{ni}$에 대해 최대화 한다. $\phi _{ni}$는 $n$번째 단어가 $i$번째 주제로부터 생성될 확률을 의미하며, $\sum _{i=1}^{k}\phi _{ni}=1$을 만족한다.

$\phi _{ni}$가 들어간 항을 분리하고, 적당한 상수를 더하여 라그랑지언을 구하면 다음과 같다. 여기서 $v\in \{1,\dots ,V\}$는 주어진 $w_{n}$에 대해 $w_{n}^{v}=1$를 만족하는 값이다.

$L_{[\phi _{ni}]}=\phi _{ni}(\Psi (\gamma _{i})-\Psi (\sum _{j=1}^{k}\gamma _{j}))+\phi _{ni}\log \beta _{iv}-\phi _{ni}\log \phi _{ni}+\lambda _{n}(\sum _{j=1}^{k}\phi _{nj}-1)$

위 식을 $\phi _{ni}$에 대해 편미분하면 다음과 같은 식을 얻을 수 있다.

${\frac {\partial L}{\partial \phi _{ni}}}=\Psi (\gamma _{i})-\Psi (\sum _{j=1}^{k}\gamma _{j})+\log \beta _{iv}-\log \phi _{ni}-1+\lambda$

$L_{[\phi _{ni}]}$를 최대화 하기 위해 위의 식이 0이 되어야 하므로, $\phi _{ni}$에 대해 다음과 같은 결론을 얻을 수 있다.

$\phi _{ni}\propto \beta _{iv}\exp(\Psi (\gamma _{i})-\Psi (\sum _{j=1}^{k}\gamma _{j}))$

변분 디리클레 매개 변수의 최적화

마찬가지로 $\gamma$에 대해서 $L(\gamma ,\phi ;\alpha ,\beta )$를 최대화 한다.

${\begin{aligned}L_{[\gamma ]}&=\sum _{i=1}^{k}(\alpha _{i}-1)(\Psi (\gamma _{i})-\Psi (\sum _{j=1}^{k}\gamma _{j}))+\sum _{n=1}^{N}\phi _{ni}(\Psi (\gamma _{i})-\Psi (\sum _{j=1}^{k}\gamma _{j}))\\&-\log \Gamma (\sum _{j=1}^{k}\gamma _{j})+\log \Gamma (\gamma _{i})-\sum _{i=1}^{k}(\gamma _{i}-1)(\Psi (\gamma _{i})-\Psi (\sum _{j=1}^{k}\gamma _{j}))\\&=\sum _{i=1}^{k}(\Psi (\gamma _{i})-\Psi (\sum _{j=1}^{k}\gamma _{j}))(\alpha _{i}+\sum _{n=1}^{N}\phi _{ni}-\gamma _{i})-\log \Gamma (\sum _{j=1}^{k}\gamma _{j})+\log \Gamma (\gamma _{i})\end{aligned}}$

위 식을 $\gamma _{i}$에 대해 편미분하면 다음과 같은 식을 얻을 수 있다.

${\frac {\partial L_{[\gamma ]}}{\partial \gamma _{i}}}=\Psi '(\gamma _{i})(\alpha _{i}+\sum _{n=1}^{N}\phi _{ni}-\gamma _{i})-\Psi '(\sum _{j=1}^{k}\gamma _{j})\sum _{j=1}^{k}(\alpha _{j}+\sum _{n=1}^{N}\phi _{nj}-\gamma _{j})$

$L_{[\phi _{ni}]}$를 최대화 하기 위해 위의 식이 0이 되어야 하므로, $\gamma _{i}$에 대해 다음과 같은 결론을 얻을 수 있다.

$\gamma _{i}=\alpha _{i}+\sum _{n=1}^{N}\phi _{ni}$

이 때 변분 매개 변수 $\phi$와 $\gamma$는 서로 의존하므로 두 값은 수렴할 때까지 번갈아가면서 계산되어야 한다.

매개 변수 추정

매개 변수 추정의 목적은 전집 $D=\{\mathbf {w} _{1},\dots ,\mathbf {w} _{M}\}$가 주어졌을 때, 주어진 전집에 대한 로그 가능도를 최대화하는 매개 변수 $\alpha$와 $\beta$를 찾는 것이다.

$l(\alpha ,\beta )=\sum _{d=1}^{M}\log p(\mathbf {w} _{d}|\alpha ,\beta )$

변분 매개 변수 $\gamma$, $\phi$를 통해 $l(\alpha ,\beta )$의 하한값을 구할 수 있으므로 기댓값 최대화 알고리즘을 통하여 $l(\alpha ,\beta )$를 최대화하는 $\alpha$와 $\beta$를 구할 수 있다.

1. (기댓값 단계) 각각의 문서에 대해 최적 변분 매개 변수 $\{\gamma _{d}^{*},\phi _{d}^{*}:d\in D\}$를 계산한다.

2. (최대화 단계) 기댓값 단계에서 구한 변분 매개 변수를 바탕으로 로그 가능도의 하한값을 최대화 하도록 $\alpha$, $\beta$를 갱신한다.

최대화 단계에서 로그 가능도의 하한값을 증가시키는 $\beta$는 다음과 같이 구할 수 있다.

$L_{[\beta ]}=\sum _{d=1}^{M}\sum _{n=1}^{N_{d}}\sum _{i=1}^{k}\sum _{j=1}^{V}\phi _{dni}w_{dn}^{j}\log \beta _{ij}+\sum _{i=1}^{k}\lambda _{i}(\sum _{j=1}^{V}\beta _{ij}-1)$

$L_{[\beta ]}$를 $\beta _{ij}$에 대해 편미분하여 최대화 시키는 값을 구하면 다음과 같다.

$\beta _{ij}\propto \sum _{d=1}^{M}\sum _{n=1}^{N_{d}}\phi _{dni}w_{dn}^{j}$

마찬가지로 로그 가능도의 하한값을 증가시키는 $\alpha$는 다음과 같이 구할 수 있다.

$L_{[\alpha ]}=\sum _{d=1}^{M}\left(\log \Gamma (\sum _{j=1}^{k}\alpha _{j})-\sum _{i=1}^{k}\log \Gamma (\alpha _{i})+\sum _{i=1}^{k}(\alpha _{i}-1)(\Psi (\gamma _{di})-\Psi (\sum _{j=1}^{k}\gamma _{dj})\right)$

${\frac {\partial L_{[\alpha ]}}{\partial \alpha _{i}}}=M(\Psi (\sum _{j=1}^{k}\alpha _{j})-\Psi (\alpha _{i}))+\sum _{d=1}^{M}(\Psi (\gamma _{di})-\Psi (\sum _{j=1}^{k}\gamma _{dj})$

${\frac {\partial L_{[\alpha ]}}{\partial \alpha _{i}\partial \alpha _{j}}}=\sigma (i,j)M\Psi '(\alpha _{i})-\Psi '(\sum _{j=1}^{k}\alpha _{j})$

뉴턴의 방법을 사용하여 새로운 $\alpha$를 기존의 $\alpha$와 ${\frac {\partial L_{[\alpha ]}}{\partial \alpha _{i}}}$, ${\frac {\partial L_{[\alpha ]}}{\partial \alpha _{i}\partial \alpha _{j}}}$에 대한 식으로 구할 수 있다.

붕괴 기브스 표집 알고리즘

아래의 유도 과정은 평활화(smoothed)된 LDA에 대해 $\varphi$와 $\theta$를 소거하는 붕괴 기브스 표집을 사용한다. 유도 과정을 간략화하기 위해 모든 문서의 길이가 $N$으로 같다고 가정한다. 물론 아래의 유도는 문서의 길이가 서로 달라도 유효하다.

모형에 대한 전체 결합 분포는 다음과 같다.

$P(\mathbf {w} ,\mathbf {z} ,\theta ,\mathbf {\varphi } |\alpha ,\beta )=\prod _{i=1}^{k}P(\varphi _{i}|\beta )\prod _{d=1}^{M}P(\theta _{d}|\alpha )\prod _{n=1}^{N}P(z_{dn}|\theta _{d})P(w_{dn}|\varphi _{z_{dn}}),$

여기서 $\varphi$와 $\theta$를 모두 더하여 주변 분포를 구할 수 있다.

${\begin{aligned}&P(\mathbf {z} ,\mathbf {w} |\alpha ,\beta )=\int _{\theta }\int _{\mathbf {\varphi } }P(\mathbf {w} ,\mathbf {z} ,\theta ,\mathbf {\varphi } |\alpha ,\beta )\,d\mathbf {\varphi } \,d\theta \\=&\int _{\mathbf {\varphi } }\prod _{i=1}^{k}P(\varphi _{i}|\beta )\prod _{d=1}^{M}\prod _{n=1}^{N}P(w_{dn}|\varphi _{z_{dn}})\,d\mathbf {\varphi } \int _{\theta }\prod _{d=1}^{M}P(\theta _{d}|\alpha )\prod _{n=1}^{N}P(z_{dn}|\theta _{d})\,d\theta .\end{aligned}}$

모든 $\theta$는 $\varphi$에 대해 독립적이다. 따라서 $\theta$와 $\varphi$를 분리할 수 있다. 우선 $\theta$가 포함된 식을 정리하면,

$\int _{\theta }\prod _{d=1}^{M}P(\theta _{d}|\alpha )\prod _{n=1}^{N}P(z_{dn}|\theta _{d})d\theta =\prod _{d=1}^{M}\int _{\theta _{d}}P(\theta _{d}|\alpha )\prod _{n=1}^{N}P(z_{dn}|\theta _{d})\,d\theta _{d}.$

이 때 각각의 $\theta _{d}$에 대해 식을 풀어 쓰면 다음과 같다.

${\begin{aligned}&\int _{\theta _{d}}P(\theta _{d}|\alpha )\prod _{n=1}^{N}P(z_{dn}|\theta _{d})\,d\theta _{d}=&\int _{\theta _{d}}{\frac {\Gamma {\bigl (}\sum _{i=1}^{k}\alpha _{i}{\bigr )}}{\prod _{i=1}^{k}\Gamma (\alpha _{i})}}\prod _{i=1}^{k}\theta _{di}^{\alpha _{i}-1}\prod _{n=1}^{N}P(z_{dn}|\theta _{d})\,d\theta _{d}.\end{aligned}}$

이제 $c_{dv}^{i}$를 $d$번째 문서의 단어 중 단어집의 $v$번째 단어이면서 $i$번째 주제에 포함된 것의 개수라 정의하자. 그러면 $c$는 3차원 행렬로 정의될 수 있다. 이 때 값이 정확하게 정해지지 않은 성분은 $(\cdot )$으로 표기하기로 한다. 가령 $c_{d,(\cdot )}^{i}$은 $d$번째 문서의 단어 중 $i$번째 주제에 포함된 것의 개수를 나타낸다. $c$을 이용하면 위의 식의 마지막 항은 다음과 같이 다시 쓰일 수 있다.

$\prod _{n=1}^{N}P(z_{dn}|\theta _{d})=\prod _{i=1}^{k}\theta _{di}^{c_{d,(\cdot )}^{i}}.$

마찬가지로 식 전체를 다시 쓰면,

${\begin{aligned}&\int _{\theta _{d}}{\frac {\Gamma {\bigl (}\sum _{i=1}^{k}\alpha _{i}{\bigr )}}{\prod _{i=1}^{k}\Gamma (\alpha _{i})}}\prod _{i=1}^{k}\theta _{di}^{\alpha _{i}-1}\prod _{i=1}^{k}\theta _{di}^{c_{d,(\cdot )}^{i}}\,d\theta _{d}\\=&\int _{\theta _{d}}{\frac {\Gamma {\bigl (}\sum _{i=1}^{k}\alpha _{i}{\bigr )}}{\prod _{i=1}^{k}\Gamma (\alpha _{i})}}\prod _{i=1}^{k}\theta _{di}^{c_{d,(\cdot )}^{i}+\alpha _{i}-1}\,d\theta _{d}.\end{aligned}}$

위 식에서 적분하는 식은 디리클레 분포 확률 밀도 함수와 같다. 따라서 확률 밀도 함수의 정의에 의해 다음을 만족한다.

$\int _{\theta _{d}}{\frac {\Gamma {\bigl (}\sum _{i=1}^{k}c_{d,(\cdot )}^{i}+\alpha _{i}{\bigr )}}{\prod _{i=1}^{k}\Gamma (c_{d,(\cdot )}^{i}+\alpha _{i})}}\prod _{i=1}^{k}\theta _{di}^{c_{d,(\cdot )}^{i}+\alpha _{i}-1}\,d\theta _{d}=1.$

따라서 처음의 주변 분포에서 $\theta$가 포함된 식은 다음과 같이 정리된다.

${\begin{aligned}&\int _{\theta _{d}}P(\theta _{d}|\alpha )\prod _{n=1}^{N}P(z_{dn}|\theta _{d})\,d\theta _{d}\\&=\int _{\theta _{d}}{\frac {\Gamma {\bigl (}\sum _{i=1}^{k}\alpha _{i}{\bigr )}}{\prod _{i=1}^{k}\Gamma (\alpha _{i})}}\prod _{i=1}^{k}\theta _{di}^{c_{d,(\cdot )}^{i}+\alpha _{i}-1}\,d\theta _{d}\\=&{\frac {\Gamma {\bigl (}\sum _{i=1}^{k}\alpha _{i}{\bigr )}}{\prod _{i=1}^{k}\Gamma (\alpha _{i})}}{\frac {\prod _{i=1}^{k}\Gamma (c_{d,(\cdot )}^{i}+\alpha _{i})}{\Gamma {\bigl (}\sum _{i=1}^{k}c_{d,(\cdot )}^{i}+\alpha _{i}{\bigr )}}}\int _{\theta _{d}}{\frac {\Gamma {\bigl (}\sum _{i=1}^{k}c_{d,(\cdot )}^{i}+\alpha _{i}{\bigr )}}{\prod _{i=1}^{k}\Gamma (c_{d,(\cdot )}^{i}+\alpha _{i})}}\prod _{i=1}^{k}\theta _{di}^{c_{d,(\cdot )}^{i}+\alpha _{i}-1}\,d\theta _{d}\\=&{\frac {\Gamma {\bigl (}\sum _{i=1}^{k}\alpha _{i}{\bigr )}}{\prod _{i=1}^{k}\Gamma (\alpha _{i})}}{\frac {\prod _{i=1}^{k}\Gamma (c_{d,(\cdot )}^{i}+\alpha _{i})}{\Gamma {\bigl (}\sum _{i=1}^{k}c_{d,(\cdot )}^{i}+\alpha _{i}{\bigr )}}}.\end{aligned}}$

이제 주변 분포에서 $\mathbf {\varphi }$가 포함된 식을 정리하자. 이 식은 $\theta$과 포함된 식과 유사한 방법에 의해 정리될 수 있다.

${\begin{aligned}&\int _{\mathbf {\varphi } }\prod _{i=1}^{k}P(\varphi _{i}|\beta )\prod _{d=1}^{M}\prod _{n=1}^{N}P(w_{dn}|\varphi _{z_{dn}})\,d\mathbf {\varphi } \\=&\prod _{i=1}^{k}\int _{\varphi _{i}}P(\varphi _{i}|\beta )\prod _{d=1}^{M}\prod _{n=1}^{N}P(w_{dn}|\varphi _{z_{dn}})\,d\varphi _{i}\\=&\prod _{i=1}^{k}\int _{\varphi _{i}}{\frac {\Gamma {\bigl (}\sum _{r=1}^{V}\beta _{r}{\bigr )}}{\prod _{r=1}^{V}\Gamma (\beta _{r})}}\prod _{r=1}^{V}\varphi _{ir}^{\beta _{r}-1}\prod _{r=1}^{V}\varphi _{ir}^{c_{(\cdot ),r}^{i}}\,d\varphi _{i}\\=&\prod _{i=1}^{k}\int _{\varphi _{i}}{\frac {\Gamma {\bigl (}\sum _{r=1}^{V}\beta _{r}{\bigr )}}{\prod _{r=1}^{V}\Gamma (\beta _{r})}}\prod _{r=1}^{V}\varphi _{ir}^{c_{(\cdot ),r}^{i}+\beta _{r}-1}\,d\varphi _{i}\\=&\prod _{i=1}^{k}{\frac {\Gamma {\bigl (}\sum _{r=1}^{V}\beta _{r}{\bigr )}}{\prod _{r=1}^{V}\Gamma (\beta _{r})}}{\frac {\prod _{r=1}^{V}\Gamma (c_{(\cdot ),r}^{i}+\beta _{r})}{\Gamma {\bigl (}\sum _{r=1}^{V}c_{(\cdot ),r}^{i}+\beta _{r}{\bigr )}}}.\end{aligned}}$

위의 결과들을 종합하여 $P(\mathbf {z} ,\mathbf {w} |\alpha ,\beta )$를 정리하면 다음과 같다.

${\begin{aligned}&P(\mathbf {z} ,\mathbf {w} |\alpha ,\beta )\\=&\prod _{d=1}^{M}{\frac {\Gamma {\bigl (}\sum _{i=1}^{k}\alpha _{i}{\bigr )}}{\prod _{i=1}^{k}\Gamma (\alpha _{i})}}{\frac {\prod _{i=1}^{k}\Gamma (c_{d,(\cdot )}^{i}+\alpha _{i})}{\Gamma {\bigl (}\sum _{i=1}^{k}c_{d,(\cdot )}^{i}+\alpha _{i}{\bigr )}}}\times \prod _{i=1}^{k}{\frac {\Gamma {\bigl (}\sum _{r=1}^{V}\beta _{r}{\bigr )}}{\prod _{r=1}^{V}\Gamma (\beta _{r})}}{\frac {\prod _{r=1}^{V}\Gamma (c_{(\cdot ),r}^{i}+\beta _{r})}{\Gamma {\bigl (}\sum _{r=1}^{V}c_{(\cdot ),r}^{i}+\beta _{r}{\bigr )}}}.\end{aligned}}$

기브스 표집의 목표는 $P(\mathbf {z} |\mathbf {w} ,\alpha ,\beta )$의 분포를 근사(approximate)하는 것이다. 이를 위해 다음과 같은 식을 사용하도록 한다.

$P(z_{pq}|\mathbf {z_{-pq}} ,\mathbf {w} ,\alpha ,\beta )={\frac {P(z_{pq},\mathbf {z_{-pq}} ,\mathbf {w} ,\alpha ,\beta )}{P(\mathbf {z_{-pq}} ,\mathbf {w} ,\alpha ,\beta )}},$

여기서부터 $z_{pq}$를 나타낼 때 $p$번째 문서의 $q$번째 단어는 단어집에서 $v$의 인덱스를 가진다고 가정한다. 또한 $\mathbf {z_{-pq}}$는 $z_{pq}$를 제외한 모든 $z$를 의미한다. 이 때 기브스 표집은 $z_{pq}$만을 고려하기 때문에 위의 식의 정확한 값은 필요가 없으며, 모든 $z$에 대한 $z_{pq}$의 비율만 구하면 된다. 따라서 위의 식을 다음과 같이 정리할 수 있다.

${\begin{aligned}&P(z_{pq}=a|\mathbf {z_{-pq}} ,\mathbf {w} ,\alpha ,\beta )\\\propto &P(z_{pq}=a,\mathbf {z_{-pq}} ,\mathbf {w} |\alpha ,\beta )\\=&\left({\frac {\Gamma \left(\sum _{i=1}^{k}\alpha _{i}\right)}{\prod _{i=1}^{k}\Gamma (\alpha _{i})}}\right)^{M}\prod _{j\neq m}{\frac {\prod _{i=1}^{k}\Gamma (c_{d,(\cdot )}^{i}+\alpha _{i})}{\Gamma {\bigl (}\sum _{i=1}^{k}c_{d,(\cdot )}^{i}+\alpha _{i}{\bigr )}}}\\&\times \left({\frac {\Gamma {\bigl (}\sum _{r=1}^{V}\beta _{r}{\bigr )}}{\prod _{r=1}^{V}\Gamma (\beta _{r})}}\right)^{k}\prod _{i=1}^{k}\prod _{r\neq v}\Gamma (c_{(\cdot ),r}^{i}+\beta _{r})\\&\times {\frac {\prod _{i=1}^{k}\Gamma (c_{p,(\cdot )}^{i}+\alpha _{i})}{\Gamma {\bigl (}\sum _{i=1}^{k}c_{p,(\cdot )}^{i}+\alpha _{i}{\bigr )}}}\prod _{i=1}^{k}{\frac {\Gamma (c_{(\cdot ),v}^{i}+\beta _{v})}{\Gamma {\bigl (}\sum _{r=1}^{V}c_{(\cdot ),r}^{i}+\beta _{r}{\bigr )}}}\\\propto &{\frac {\prod _{i=1}^{k}\Gamma (c_{p,(\cdot )}^{i}+\alpha _{i})}{\Gamma {\bigl (}\sum _{i=1}^{k}c_{p,(\cdot )}^{i}+\alpha _{i}{\bigr )}}}\prod _{i=1}^{k}{\frac {\Gamma (c_{(\cdot ),v}^{i}+\beta _{v})}{\Gamma {\bigl (}\sum _{r=1}^{V}c_{(\cdot ),r}^{i}+\beta _{r}{\bigr )}}}\\\propto &\prod _{i=1}^{k}\Gamma (c_{p,(\cdot )}^{i}+\alpha _{i})\prod _{i=1}^{k}{\frac {\Gamma (c_{(\cdot ),v}^{i}+\beta _{v})}{\Gamma {\bigl (}\sum _{r=1}^{V}c_{(\cdot ),r}^{i}+\beta _{r}{\bigr )}}}..\end{aligned}}$

위의 유도 과정은 디리클레 다항 분포나 디리클레 분포를 사전 확률 분포로 사용하는 베이즈 네트워크에서 사전 확률을 모두 더한 주변 확률을 구할 때에도 사용된다.

변형 모형

LDA 모형은 모듈형 구조여서 쉽게 확장될 수 있다. 여러 주제들 사이의 관계를 알아내는 연구가 주요 관심 목적이다. 이 목적을 달성하기 위해 디리클레 분포 대신 다른 분포를 사용해서 다양한 변형 모형을 만들 수 있다. 상관 주제 모형은 디리클레 분포 대신 로지스틱 정규분포를 이용하여 주제들간의 상관관계를 알아낸다. 또 다른 확장모형으로는 계층적 잠재 디리클레 할당(hierarchical LDA, hLDA)가 있다. hLDA는 중첩된 중국집 프로세스(Chinese Restaurant Process)를 이용하여 주제들간의 계층 구조를 만든다. LDA를 확장한 또 다른 모형인 이중 잠재 디리클레 모형(LDA-dual model)은 각각의 문서가 두 가지 종류의 정보를 가지고 있는 전집에도 적용할 수 있다. 또 다른 예로 LDA의 비모수적 확장 모형인 계층적 디리클레 프로세스(Hierarchical Dirichlet process)모형은 주제의 개수를 모르는 상황에서 사용될 수 있다. 계층적 디리클레 프로세스는 정보를 계층적 구조로 만들 수 있는 중첩된 중국집 프로세스를 이용하여 주제의 개수를 알아낼 수 있다.

응용

문서 모형화

문서 모형화는 LDA가 가장 많이 쓰이는 분야 중 하나이다.

• 웹 마이닝
• 협업 필터링
• 스팸 탐지

생물정보학

유전자 온톨로지는 유전자와 관련된 정보들을 담고 있는 지식베이스이다. 유전자 기능 분석을 효율적으로 진행하기 위해서는 방대하고 신뢰성이 보장된 유전자 온톨로지가 필수적이다. 때문에 생물학 문헌에서 정보를 자동으로 추출하여 유전자 온톨로지를 자동으로 확장하는 연구가 진행되고 있다. 이러한 유전자 온톨로지 연구에 LDA가 사용될 수 있다. 유전자 온톨로지에서 LDA는 문서 대신에 유전자를 사용하고, 단어 대신에 유전자 특징을 사용하고, 주제 대신 유전자 기능을 사용한다.

화상 분류

LDA를 이용하면 이미지에 나타난 물체가 어떤 종류인지 알아낼 수 있다. Sivic의 방식에 따르면 문서 대신 이미지를 사용하고, 단어 대신 부호단어를 사용하고, 주제 대신 화상 분류를 사용한다. 하나의 이미지는 여러 종류의 혼합으로 모형화 될 수 있다. LDA를 화상 분류에 적용할 때 사용되는 변수들을 다음과 같이 설명할 수 있다.

화상 분류에서의 LDA

변수	문서 모형화에 대응되는 변수	의미
부호단어(codeword)	단어(word)	LDA 모형의 가장 기본적인 이산 데이터 단위 $x\in \{1,\dots ,V\}$
패치(patch)	없음	이미지의 가장 기본적인 단위. 패치에 특징 검출 알고리즘(e.g. SIFT)을 적용하면 부호단어가 된다.
부호책(codebook)	없음	V개의 부호단어의 집합이다. 이미지에서 패치들을 추출한 후 부호단어로 변환시키면 부호책을 얻을 수 있다.
이미지	문서(document)	N개의 패치들의 집합이다. $\mathbf {x} \in \{x_{1},\dots ,x_{N}\}$
화상 분류(object category)	주제(topic)	V 개의 부호단어들이 등장할 확률 분포이다. $z\in \{1,\dots ,K\}$

자동 화성 분석

음악에서도 LDA을 이용한 연구들이 진행되고 있다. 음악에서 LDA를 사용하기가 쉽지 않은 이유는 단어와 같이 "단위"가 되는 정보가 없기 때문이다. 그래서 화성 분석과 같이 음의 조합으로부터 특징을 추출할 수 있는 문제에 대해서만 LDA를 적용할 수 있다. LDA를 화성 분석에 적용할 때 사용되는 변수들을 다음과 같이 설명할 수 있다.

자동 화성 분석에서의 LDA

변수	문서 모형화에 대응되는 변수	의미
음(note)	없음	가장 기본적인 이산 데이터 단위. 12 음계를 사용하기 때문에 V는 12로 고정된다. $u\in \{1,\dots ,12\}$
마디(segment)	단어(word)	곡의 가장 기본적인 단위. 한 마디는 음의 집합이다. $\mathbf {u} \in \{u_{1},\dots ,u_{L}\}$
곡(song)	문서(document)	N개 마디의 집합이다. $\mathbf {s} \in \{\mathbf {u} _{1},\dots ,\mathbf {u} _{N}\}$
화성(harmonics)	주제(topic)	V 개의 음들이 등장할 확률 분포이다. 장조 화성 12개와 단조 화성 12개가 사용되기 때문에 K는 24로 고정된다. $z\in \{1,\dots ,24\}$

한국어와 LDA

LDA를 사용할 때 단어의 집합이 필요하다. 영어에서는 공백문자 단위로 나누어서 집합에 넣은 후 'and', 'in', 'to'와 같은 불용어(stop word)를 제거함으로써 단어의 집합을 생성할 수 있다. 하지만 한국어는 단어에 조사와 동사 활용으로 인해 추가적인 처리가 필요하다. 보통 한국어 형태소 분석기를 이용하여 문서에서 명사와 동사 원형만 걸러낸 후에 LDA에 사용한다.

구현

Python

• lda (https://pypi.python.org/pypi/lda)

붕괴 깁스 표집을 이용한 잠재 디리클레 할당 구현이다. 모질라 공용 허가서 2.0으로 배포하고 있다.

• gensim (https://radimrehurek.com/gensim/)

다양한 토픽 모델링을 지원하는 라이브러리이다. 잠재 디리클레 할당과 모든 CPU의 코어를 병렬적으로 사용하는 병렬 잠재 디리클레 할당 구현을 포함하고 있다. GNU 약소 일반 공중 사용 허가서로 배포하고 있다.

Java

• JGibbLDA (http://jgibblda.sourceforge.net/)

매개 변수 추정과 추론을 위해 깁스 표집을 이용한 잠재 디리클레 할당구현이다. GNU 일반 공중 사용 허가서로 배포하고 있다.

• MALLET (http://mallet.cs.umass.edu/)

통계적 자연어 처리, 문서 분류, 클러스터링, 토픽 모델링, 정보 추출 등의 문서 머신 러닝을 지원하는 패키지이다. MALLET 토픽 모델링 툴킷은 잠재 디리클레 할당, 파친코 할당, 계층 잠재 디리클레 할당을 지원한다. 커먼 퍼블릭 라이선스로 배포하고 있다.

C, C++

• Yahoo LDA (https://github.com/shravanmn/Yahoo_LDA)

야후의 토픽 모델링을 위한 잠재 디리클레 할당의 구현이다. 아파치 라이선스 2.0으로 배포하고 있다.

• PLDA (https://code.google.com/p/plda/)

빠른 깁스 표집을 이용한 잠재 디리클레 할당의 구현이다. 아파치 라이선스 2.0으로 배포하고 있다.

같이 보기

• 변분 베이즈 방법

외부 링크

• LDA(Latent Dirichlet Allocation): 겉핥기
• '잠재 디리슐레 할당' 고안자 직강