잠재 디리클레 할당

자연어 처리에서 잠재 디리클레 할당(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]등의 단어들이 많이 쓰인 문서가 있다고 해보자. 우리는 첫번째 문서가 물리학에 관련된 내용이고, 두번째 문서가 문학에 관련된 내용으로 추측할 수 있다. 그 이유는 우리는 문서에 들어가 있는 단어들이 해당 해당 주제들을 표현하고 있음을 알기 때문이다. 이러한 사전 정보가 없다면 주제를 예측할 수 없다. 하지만 사전정보가 없어도 단어들과 주제들은 연관성이 있다. 주제는 의미나 인식으로 결정되는 것이 아니고, 지도 학습으로 라벨링된 단어들의 가능도로 결정된다.
모형.
formula_1개의 문서가 주어져 있고, 모든 문서는 각각 formula_2개의 주제 중 하나에 속할 때,
LDA는 각각의 문서 formula_12에 대해 다음과 같은 생성 과정을 가정한다.
1. formula_13 을 선택한다.
2. formula_14를 선택한다.
3. 문서 내의 단어 formula_15 에 대해서
생성 과정에서 각각의 변수는 다음과 같은 의미를 가진다.
여기에서 formula_36는 실제 문서를 통해 주어지며, 다른 변수는 관측할 수 없는 잠재 변수이다.
이 모형은 다음과 같이 해석될 수 있다. 각 문서에 대해 formula_2개의 주제에 대한 가중치 formula_22가 존재한다. 문서 내의 각 단어 formula_18은 formula_2개의 주제에 대한 가중치 formula_17을 가지는데, formula_17은 formula_22에 의한 다항 분포로 선택된다. 마지막으로 실제 단어 formula_18이 formula_17에 기반하여 선택된다.
잠재 변수 formula_20, formula_31가 주어졌을 때 formula_22, formula_49, formula_50에 대한 결합 분포는 다음과 같이 구해진다.
여기서 formula_17과 formula_22를 모두 더하여 문서의 주변 분포 (marginal distribution)를 구할 수 있다. 이 때 디 피네치의 정리 (de Finetti's theorem)에 의해 단어가 문서 안에서 교환성을 가지는 것을 확인할 수 있다.
마지막으로 각각의 문서에 대한 주변 분포를 모두 곱하여 전집의 확률을 구할 수 있다.
기존의 잠재 변수 모형과의 차이점.
LDA 이전에도 다양한 잠재 변수 모형(latent variable model)이 제시되어 왔다. 아래에서는 그 중 대표적인 유니그램 혼합(mixture of uni-grams) 모형, pLSI 모형과의 차이점을 서술한다.
유니그램 혼합 모형.
유니그램 혼합 모형은 다음과 같은 생성 과정을 가정한다.
1. formula_56로부터 문서의 주제를 선택한다.
2. 문서의 주제가 주어졌을 때 formula_18은 formula_58 로부터 선택한다.
위 과정으로부터 문서의 확률을 구하면 다음과 같다.
유니그램 혼합 모형의 생성 과정은 각각의 문서가 정확히 하나의 주제를 가진다는 것을 가정한다. 따라서 문서의 개수가 많아질 때 전집을 효율적으로 모형화할 수 없다는 단점이 있다. 반면, LDA는 하나의 문서에 대해 여러 개의 주제가 서로 다른 가중치로 혼합되는 것을 허용한다.
pLSI 모형.
pLSI 모형은 다음과 같은 생성 과정을 가정한다.
1. 문서의 주제 분포 formula_60로부터 주제 formula_56를 선택한다.
2. 주제 formula_56가 주어졌을 때 formula_18은 formula_58 로부터 선택한다.
위 과정으로부터 문서와 단어가 나올 결합 확률을 구하면 다음과 같다.
pLSI 모형은 formula_66를 통해 하나의 문서가 여러개의 주제를 가질 수 있도록 허용한다. 그러나 formula_60는 트레이닝 셋에 속한 문서들에 대한 인덱스이기 때문에 formula_66는 트레이닝 셋에 포함된 문서에 대해서만 정의된다. 따라서 pLSI 새로운 문서에 대한 확률을 계산할 수 없으며, 이 때문에 잘 정의된(well-defined) 생성 모형이 아니다.
또한 pLSI에서 각각의 주제는 formula_69 크기의 혼합(mixture)으로 정의된다. 따라서 formula_2개의 주제에 대해 formula_71 개의 매개변수를 필요로 하며, 이는 전집의 크기 formula_1에 대해 선형적으로 증가한다. 따라서 트레이닝 셋의 크기가 커질 때 모형이 과적합(overfitting)되기 쉽다.
반면, LDA는 잘 정의된 생성 모형이기 때문에 새로운 문서에 대해서도 쉽게 일반화될 수 있다. 또한 각각의 주제가 formula_3 크기의 혼합으로 정의되기 때문에, formula_2개의 주제에 대해 전집의 크기와 무관하게 formula_75 개의 매개변수를 필요로 한다. 따라서 pLSI와 같은 과적합 문제를 겪지 않는다.
추론.
LDA를 사용하기 위해서는 문서가 주어졌을 때 잠재 변수에 대한 사후 확률을 구할 수 있어야 한다.
그러나 이 분포는 잠재 변수인 formula_22와 formula_31의 결합 형태를 더하기 때문에 일반적으로 계산하기 어렵다. 따라서 사후 확률을 구하기 위한 다양한 근사 알고리즘이 사용된다. 처음 제시된 LDA에서는 볼록 기반 변분 알고리즘(convexity-based variational algorithm)을 사용하였으며, 다른 접근 방법으로는 기브스 표집과 기대 전파법(expectation propagation)을 사용할 수도 있다.
볼록 기반 변분 알고리즘.
볼록 기반 변분 알고리즘의 기본 아이디어는 옌센 부등식을 기반으로 로그 가능도(log likelihood)의 하한값을 계산하는 것이다. 로그 가능도의 하한값은 변분 매개 변수(varional paremeter)로 나타내지며, 이 매개변수는 최적화 과정을 통해 가장 좋은 하한값을 가지도록 정해진다.
이 알고리즘을 LDA에 적용하기 위해서는 LDA의 그래프 도식을 간단화시켜야 한다. formula_80에서 formula_22와 formula_31의 결합을 제거해야 하므로, 기존의 그래프 도식에서 formula_22, formula_84, formula_50 사이의 간선을 제거한 뒤 변분 매개변수 formula_86와 formula_87을 추가한다. formula_86는 디리클레 분포의 매개변수이며, formula_89는 다항 분포의 매개변수이다. 이 때 변분 매개 변수에 대한 formula_22와 formula_84의 조건부 확률은 다음과 같다.
이것을 바탕으로 임의의 formula_93에 대해 문서의 로그 가능도의 하한값을 구할 수 있다.
위의 식에서 우변을 formula_95라 표기하자. 그러면 좌변과 우변의 차이가 쿨백-라이블러 발산임을 이용하여 다음과 같이 나타낼 수 있다.
따라서 문서의 로그 가능도의 하한값인 formula_95을 최대화 하는 것은 변분 사후 확률과 기존의 사후 확률간의 쿨백-라이블러 발산값을 최소화하는 것과 동치이다.
최적화 과정을 유도하기 위해 formula_95을 모델 매개 변수 formula_100와 변분 매개 변수 formula_101에 관한 식으로 나타내면 다음과 같다.
여기서 formula_103는 다이감마 함수(digamma function)이다.
변분 다항 분포 매개 변수의 최적화.
우선 formula_95을 formula_105에 대해 최대화 한다. formula_105는 formula_107번째 단어가 formula_25번째 주제로부터 생성될 확률을 의미하며, formula_109을 만족한다.
formula_105가 들어간 항을 분리하고, 적당한 상수를 더하여 라그랑지언을 구하면 다음과 같다. 여기서 formula_111는 주어진 formula_18에 대해 formula_113를 만족하는 값이다.
위 식을 formula_105에 대해 편미분하면 다음과 같은 식을 얻을 수 있다.
formula_117를 최대화 하기 위해 위의 식이 0이 되어야 하므로, formula_105에 대해 다음과 같은 결론을 얻을 수 있다.
변분 디리클레 매개 변수의 최적화.
마찬가지로 formula_86에 대해서 formula_95를 최대화 한다.
위 식을 formula_123에 대해 편미분하면 다음과 같은 식을 얻을 수 있다.
formula_117를 최대화 하기 위해 위의 식이 0이 되어야 하므로, formula_123에 대해 다음과 같은 결론을 얻을 수 있다.
이 때 변분 매개 변수 formula_89와 formula_86는 서로 의존하므로 두 값은 수렴할 때까지 번갈아가면서 계산되어야 한다.
매개 변수 추정.
매개 변수 추정의 목적은 전집 formula_130가 주어졌을 때, 주어진 전집에 대한 로그 가능도를 최대화하는 매개 변수 formula_20와 formula_31를 찾는 것이다.
변분 매개 변수 formula_86, formula_89를 통해 formula_136의 하한값을 구할 수 있으므로 기댓값 최대화 알고리즘을 통하여 formula_136를 최대화하는 formula_20와 formula_31를 구할 수 있다.
1. (기댓값 단계) 각각의 문서에 대해 최적 변분 매개 변수 formula_140를 계산한다.
2. (최대화 단계) 기댓값 단계에서 구한 변분 매개 변수를 바탕으로 로그 가능도의 하한값을 최대화 하도록 formula_20, formula_31를 갱신한다.
최대화 단계에서 로그 가능도의 하한값을 증가시키는 formula_31는 다음과 같이 구할 수 있다.
formula_145를 formula_33에 대해 편미분하여 최대화 시키는 값을 구하면 다음과 같다.
마찬가지로 로그 가능도의 하한값을 증가시키는 formula_20는 다음과 같이 구할 수 있다.
뉴턴의 방법을 사용하여 새로운 formula_20를 기존의 formula_20와 formula_154, formula_155에 대한 식으로 구할 수 있다.
붕괴 기브스 표집 알고리즘.
아래의 유도 과정은 평활화(smoothed)된 LDA에 대해 formula_156와 formula_22를 소거하는 붕괴 기브스 표집을 사용한다. 유도 과정을 간략화하기 위해 모든 문서의 길이가 formula_8으로 같다고 가정한다. 물론 아래의 유도는 문서의 길이가 서로 달라도 유효하다.
모형에 대한 전체 결합 분포는 다음과 같다.
여기서 formula_156와 formula_22를 모두 더하여 주변 분포를 구할 수 있다.
모든 formula_22는 formula_156에 대해 독립적이다. 따라서 formula_22와 formula_156를 분리할 수 있다. 우선 formula_22가 포함된 식을 정리하면,
이 때 각각의 formula_169에 대해 식을 풀어 쓰면 다음과 같다.
이제 formula_171를 formula_60번째 문서의 단어 중 단어집의 formula_173번째 단어이면서 formula_25번째 주제에 포함된 것의 개수라 정의하자. 그러면 formula_175는 3차원 행렬로 정의될 수 있다. 이 때 값이 정확하게 정해지지 않은 성분은 formula_176으로 표기하기로 한다. 가령 formula_177은 formula_60번째 문서의 단어 중 formula_25번째 주제에 포함된 것의 개수를 나타낸다. formula_175을 이용하면 위의 식의 마지막 항은 다음과 같이 다시 쓰일 수 있다.
마찬가지로 식 전체를 다시 쓰면,
위 식에서 적분하는 식은 디리클레 분포 확률 밀도 함수와 같다. 따라서 확률 밀도 함수의 정의에 의해 다음을 만족한다.
따라서 처음의 주변 분포에서 formula_22가 포함된 식은 다음과 같이 정리된다.
이제 주변 분포에서 formula_186가 포함된 식을 정리하자. 이 식은 formula_22과 포함된 식과 유사한 방법에 의해 정리될 수 있다.
위의 결과들을 종합하여 formula_189를 정리하면 다음과 같다.
기브스 표집의 목표는 formula_191의 분포를 근사(approximate)하는 것이다. 이를 위해 다음과 같은 식을 사용하도록 한다.
여기서부터 formula_193를 나타낼 때 formula_194번째 문서의 formula_195번째 단어는 단어집에서 formula_173의 인덱스를 가진다고 가정한다. 또한 formula_197는 formula_193를 제외한 모든 formula_56를 의미한다. 이 때 기브스 표집은 formula_193만을 고려하기 때문에 위의 식의 정확한 값은 필요가 없으며, 모든 formula_56에 대한 formula_193의 비율만 구하면 된다. 따라서 위의 식을 다음과 같이 정리할 수 있다.
위의 유도 과정은 디리클레 다항 분포나 디리클레 분포를 사전 확률 분포로 사용하는 베이즈 네트워크에서 사전 확률을 모두 더한 주변 확률을 구할 때에도 사용된다.
변형 모형.
LDA 모형은 모듈형 구조여서 쉽게 확장될 수 있다. 여러 주제들 사이의 관계를 알아내는 연구가 주요 관심 목적이다. 이 목적을 달성하기 위해 디리클레 분포 대신 다른 분포를 사용해서 다양한 변형 모형을 만들 수 있다. 상관 주제 모형은 디리클레 분포 대신 로지스틱 정규분포를 이용하여 주제들간의 상관관계를 알아낸다. 또 다른 확장모형으로는 계층적 잠재 디리클레 할당(hierarchical LDA, hLDA)가 있다. hLDA는 중첩된 중국집 프로세스(Chinese Restaurant Process)를 이용하여 주제들간의 계층 구조를 만든다. LDA를 확장한 또 다른 모형인 이중 잠재 디리클레 모형(LDA-dual model)은 각각의 문서가 두 가지 종류의 정보를 가지고 있는 전집에도 적용할 수 있다. 또 다른 예로 LDA의 비모수적 확장 모형인 계층적 디리클레 프로세스(Hierarchical Dirichlet process)모형은 주제의 개수를 모르는 상황에서 사용될 수 있다. 계층적 디리클레 프로세스는 정보를 계층적 구조로 만들 수 있는 중첩된 중국집 프로세스를 이용하여 주제의 개수를 알아낼 수 있다.
응용.
문서 모형화.
문서 모형화는 LDA가 가장 많이 쓰이는 분야 중 하나이다.
생물정보학.
유전자 온톨로지는 유전자와 관련된 정보들을 담고 있는 지식베이스이다. 유전자 기능 분석을 효율적으로 진행하기 위해서는 방대하고 신뢰성이 보장된 유전자 온톨로지가 필수적이다. 때문에 생물학 문헌에서 정보를 자동으로 추출하여 유전자 온톨로지를 자동으로 확장하는 연구가 진행되고 있다. 이러한 유전자 온톨로지 연구에 LDA가 사용될 수 있다. 유전자 온톨로지에서 LDA는 문서 대신에 유전자를 사용하고, 단어 대신에 유전자 특징을 사용하고, 주제 대신 유전자 기능을 사용한다.
화상 분류.
LDA를 이용하면 이미지에 나타난 물체가 어떤 종류인지 알아낼 수 있다. Sivic의 방식에 따르면 문서 대신 이미지를 사용하고, 단어 대신 부호단어를 사용하고, 주제 대신 화상 분류를 사용한다. 하나의 이미지는 여러 종류의 혼합으로 모형화 될 수 있다. LDA를 화상 분류에 적용할 때 사용되는 변수들을 다음과 같이 설명할 수 있다.
자동 화성 분석.
음악에서도 LDA을 이용한 연구들이 진행되고 있다. 음악에서 LDA를 사용하기가 쉽지 않은 이유는 단어와 같이 "단위"가 되는 정보가 없기 때문이다. 그래서 화성 분석과 같이 음의 조합으로부터 특징을 추출할 수 있는 문제에 대해서만 LDA를 적용할 수 있다. LDA를 화성 분석에 적용할 때 사용되는 변수들을 다음과 같이 설명할 수 있다.
한국어와 LDA.
LDA를 사용할 때 단어의 집합이 필요하다. 영어에서는 공백문자 단위로 나누어서 집합에 넣은 후 'and', 'in', 'to'와 같은 불용어(stop word)를 제거함으로써 단어의 집합을 생성할 수 있다. 하지만 한국어는 단어에 조사와 동사 활용으로 인해 추가적인 처리가 필요하다. 보통 한국어 형태소 분석기를 이용하여 문서에서 명사와 동사 원형만 걸러낸 후에 LDA에 사용한다.
구현.
Python.
붕괴 깁스 표집을 이용한 잠재 디리클레 할당 구현이다. 모질라 공용 허가서 2.0으로 배포하고 있다.
다양한 토픽 모델링을 지원하는 라이브러리이다. 잠재 디리클레 할당과 모든 CPU의 코어를 병렬적으로 사용하는 병렬 잠재 디리클레 할당 구현을 포함하고 있다. GNU 약소 일반 공중 사용 허가서로 배포하고 있다.
Java.
매개 변수 추정과 추론을 위해 깁스 표집을 이용한 잠재 디리클레 할당구현이다. GNU 일반 공중 사용 허가서로 배포하고 있다.
통계적 자연어 처리, 문서 분류, 클러스터링, 토픽 모델링, 정보 추출 등의 문서 머신 러닝을 지원하는 패키지이다. MALLET 토픽 모델링 툴킷은 잠재 디리클레 할당, 파친코 할당, 계층 잠재 디리클레 할당을 지원한다. 커먼 퍼블릭 라이선스로 배포하고 있다.
C, C++.
야후의 토픽 모델링을 위한 잠재 디리클레 할당의 구현이다. 아파치 라이선스 2.0으로 배포하고 있다.
빠른 깁스 표집을 이용한 잠재 디리클레 할당의 구현이다. 아파치 라이선스 2.0으로 배포하고 있다.