[토픽 모델링] 가우시안 LDA 모델 - Word2Vec과 결합한 LDA

Posted by 적분 ∫2tdt=t²+c
2018.08.05 21:07 그냥 공부

최근 단어 임베딩(Word Embedding)이 매우 뜨겁게 떠오르고 있습니다. 단어 임베딩 이전의 자연언어처리에서는 각각의 단어를 모두 독립적인 존재로 보고 번호를 붙여주는 방식으로 언어 처리를 실시했습니다. 예를 들어 {옷, 의류, 의복}이라는 단어가 있으면 옷 = 0, 의류 = 1, 의복 = 2 처럼 임의로 번호를 붙여준 것이죠. 0, 1, 2번에는 아무런 의미가 없고 단지 계산을 편리하게 하기 위해 정수를 붙인것 뿐입니다. 이를 통해 간편하게 0번이 몇번 등장하는지, 1번이 몇번 등장하는지 등을 셀 수 있고 이 빈도가 전체 문헌의 의미를 나타낸다고 가정하여 분석을 진행했었죠.

하지만 단어 임베딩 기법에서는 각 단어를 임의의 차원의 실수로 대응시킵니다. 옷 = (0.1, 0.1), 의류 = (0.2, 0.1), 의복 = (0.1, -0.1) 처럼 말이지요. 그리고 이 때 각 벡터값(2개의 실수를 묶어서 사용하므로 벡터라고 하는게 맞겠죠)은 실질적인 의미를 반영합니다. 의미가 유사한 단어가 실제로 유사한 벡터값을 가지게 한다는 거죠. 이를 수행하는 대표적인 기법으로 Word2Vec이나 GloVe, FastText와 같은 기법들이 있습니다. 이전에는 {옷, 의류, 의복}이라는 단어 사이의 관계를 전혀 반영하지 않은 채로 분석을 진행했다면, 단어 임베딩 기법이 등장하면서 이 단어들이 유사한 단어라는 것을 알고리즘 상에 반영하여 분석을 진행할 수 있는 기법이 열린 것이지요.


본 포스팅에서는 이런 단어 임베딩의 트렌드를 토픽 모델링에 적용한 모형을 살펴보고자 합니다. 


Das, R., Zaheer, M., & Dyer, C. (2015). Gaussian lda for topic models with word embeddings. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers) (Vol. 1, pp. 795-804).


사실 이 논문을 접한 건 한 달도 더 전의 일이지만, 쓰이는 통계적 기법을 전혀 이해하지 못해서 구석에 던져두었다가 드디어 어느 정도 이해가 되어서 이렇게 정리를 하게 되었습니다. 논문을 이해하는데 필요한 열쇠는 역 위샤트 분포(inverse Wishart distribution)숄레스키 분해(Cholesky decomposition)입니다. 어려운 개념이 나왔다고 당황하지 마시고 (글쓴이도 아직 잘 모르지만) 최대한 쉽게 설명해볼테니 찬찬히 읽어보시면 이해하는데 도움이 되실것 같습니다.

(물론 아주 기초적인 선행 지식으로 정규 분포t 분포, 베이즈 추론에 대해서는 알고 계셔야합니다. 베이즈 추론과 LDA와의 관계에 대해서는 http://bab2min.tistory.com/567 시리즈를 읽으시면 이해에 도움이 되실겁니다.)



LDA에 대해 다시 생각해보자

LDA에서는 단어와 단어 사이의 유사도를 따로 다루지는 않습니다. 이는 LDA의 생성 모형을 보면 알 수 있는데, LDA에서 각 주제(topic)는 다항 분포(multinomial distribution)를 따른다고 가정합니다. 다항분포는 n가지의 선택지 중 1가지를 임의로 고르는 작업을 여러번 반복하는 것으로 볼 수 있습니다. 선택지의 개수는 유한하고 다른 선택지와는 독립적입니다. 

{옷, 의류, 의복, 초콜릿, 사탕}과 같은 단어집합이 있다면 이중에서 하나의 단어를 임의로 뽑는것을 생각해볼 수 있겠죠. 주제#1 "패션"은 {옷:30%, 의류:30%, 초콜릿:5%, 의복:30%, 사탕:5%}와 같은 확률로 임의의 단어를 뽑아낼 것이고, 주제#2 "군것질"은 {옷:4%, 의류:4%, 초콜릿:44%, 의복:4%, 사탕:44%}와 같은 확률로 임의의 단어를 뽑아낼 것입니다.

그리고 이런 주제들(다항분포)의 분포를 설명하기 위해 디리클레 분포(Dirichlet distribution)를 도입한거라는걸 기억하실겁니다. 다항분포의 켤레 사전분포가 디리클레분포이기 때문에, 주제에 대한 사전 분포를 디리클레 분포로 설정하면 계산이 간단해진다고 설명했었습니다.


그런데 여기서 잠깐. {옷, 의류, 초콜릿, 의복, 사탕}과 같은 단어집합은 컴퓨터에겐 그저 {0, 1, 2, 3, 4}와 다름 없는 집합일 뿐입니다. 0과 1과 3가 서로 유사한 의미이고, 2와 4가 유사한 의미인지 컴퓨터는 전혀 알 수 없습니다. 컴퓨터는 주제#1에서는 0, 1, 3이 등장할 확률이 높고, 주제#2에서는 2, 4가 등장할 확률이 높다는 것만 아는 겁니다. 다행히도 추론에 사용하는 문헌 집합의 크기가 충분히 크고 양질일 경우, 옷/의류/의복이 함께 등장하는 문헌이 많아지고, 또 마찬가지로 초콜릿/사탕이 함께 등장하는 문헌이 많아지므로, 자연스럽게 옷/의류/의복을 같은 주제로 묶고, 초콜릿/사탕을 같은 주제로 묶도록 학습을 하게 됩니다. 이 덕분에 단어의 의미를 전혀 모르는 컴퓨터가 단순히 더하기 빼기만 반복하지만, LDA가 의미적으로 유사한 단어를 군집화하며 잘 작동하는 것이지요.


하지만 추론에 사용하는 문헌 집합의 크기가 충분히 크지 않거나 질이 나쁘면 어떨까요? 옷/의류/의복이 함께 등장하는 문헌이 거의 없으면? LDA는 옷/의류/의복을 같은 주제로 묶어내지 못할 가능성이 높습니다. 사람이 보기에는 누가 봐도 같은 의미인데, 단어를 다르게 사용했다고 다른 주제로 갈리게 될 수도 있습니다. 이는 잘 알려진 단어 임베딩 기법 이전의 자연언어처리의 대표적 한계입니다.


그러면 토픽 모델링에도 단어 임베딩을 적용해보자고 생각할 수 있겠죠. LDA에서는 주제를 다항분포로 두어 {0, 1, 2, 3, 4} 중 임의의 숫자 1개를 뽑도록 했지만, 이를 다차원으로 확장시켜서 주제에서 임의의 벡터 (0.1, 0.2)나 (0.15, 0.7)과 같은 녀석을 뽑아내도록 해서 단어 임베딩과 연결할 수 있습니다. 좋은 아이디어죠, 먼저 그 결과부터 보고 갈까요?


G-LDA 실험 결과

이 표는 본 논문에 나온것을 발췌한 것입니다. 20-newsgroup 데이터를 K=50으로 토픽 모델링 실시한 것인데요, 제일 아래쪽에는 Topic Coherence 값이 나와 있습니다. 이 값이 높을수록 유사한 단어끼리 클러스터링이 된 것이라 판단할 수 있습니다. 보다시피 가우시안 LDA쪽이 훨씬 높은 Coherence 값을 보이고 있습니다. 인간이 옷-의류-의복이 서로 유사한 의미라는 걸 배경지식으로 알고 있는것처럼, 단어의 벡터값으로 Word2Vec이나 GloVe에서 얻은 배경지식을 사용하기 때문에 좋은 결과가 나올수 있던 것이라고 볼 수 있습니다.


또한 이 방법은 OOV(Out of Vocabulary, 미등록 단어)를 깔끔하게 해결할 수 있습니다. 기존의 LDA모델은 일단 학습을 진행하고 나면 전체 단어의 개수 V가 고정이 되기 때문에 새로운 단어를 추가할수가 없고, 이를 개선해 새로운 단어를 추가할수 있는 LDA with infinite vocabulary와 같은 기법을 사용하더라도 새로운 단어는 그 의미를 알 수가 없기 때문에 적절한 주제에 배치하는데 한계가 있을수 밖에 없습니다. 반면 G-LDA에서는 기존 학습데이터에 없는 단어가 등장하더라도 단어 임베딩 데이터에 해당 단어가 포함되어 있다면 성공적으로 P차원의 벡터로 변환될 수 있고, 혹시나 단어 임베딩 데이터가 없다하더라도 Character-level에서 임베딩을 수행하는 방법 등을 사용하여 P차원 벡터로 변환할 수 있습니다. 본 논문을 따르면 OOV 문제를 해결하는데에도 LDA with Infinite Vocabulary보다 좋은 성능을 보였다고 합니다.


정말 괜찮은 녀석인것 같습니다. 그럼 과연 저자들이 어떻게 LDA 모델이 P차원의 임베딩 벡터를 받아들일 수 있게 확장했는지 살펴봅시다.


정규 분포와 다변수 정규분포(multivariate normal distribution)

{0, 1, 2, 3, 4} 중 1개의 숫자를 뽑는건 간단합니다. 뽑을 대상이 5개니깐 5개 중에서 1개를 뽑으면 되거든요. 하지만 [-1, 1] 범위에서 임의의 실수를 뽑는건 어떻게 할까요? 더 확장해서 (-∞, ∞), 즉 모든 실수 범위에서 임의의 수 하나를 뽑는건 어떻게 할수 있을까요? 이를 위해 정규분포(normal distribution)를 사용할 수 있습니다.

이런 종 모양의 그래프는 자주보셨을 겁니다. 정규분포는 평균(μ)표준편차(σ, 혹은 분산 Σ=σ²을 쓰기도 합니다.)라는 2개의 파라미터를 통해 전 범위의 실수 상의 분포를 표현하는 방법 중 하나입니다. 한국 남성의 키 하나를 무작위하게 뽑는 문제를 생각해볼 수 있겠죠. 그냥 머릿속에서 생각나는 숫자 180을 골라서 "한국 남성의 키를 임의로 뽑았다!"고 우겨도 되겠지만 이 방법은 정확하지도 않고 컴퓨터가 사용할수도 없겠죠. 한국 남성의 키를 가장 잘 표현할수 있는 두 파라미터를 찾아서(예를 들어 μ=173, σ=5), 이 파라미터를 가지고 임의의 키를 생성하는게 좋을 겁니다.


정규 분포를 사용해서 특정 상황에 어울리는 임의의 실수를 뽑을 수 있다는 것은 충분히 이해하셨을 겁니다. 다음은 2개 이상의 실수, 즉 벡터값을 뽑는 방법에 대해서 살펴봅시다. 정규분포를 그대로 다차원으로 확장한 분포를 다변수 정규분포(multivariate normal distribution)이라고 합니다. 이 분포 역시 2개의 파라미터로 설명됩니다. 하나는 평균(μ), 다른 하나는 분산(Σ)입니다. 단 이 때 뽑으려는 벡터의 차원이 p라고 할때(즉 p개의 실수로 이뤄진 벡터를 뽑으려고 할때) μ는 p x 1 행렬, Σ는 p x p행렬이 됩니다.


다변수 정규분포의 사전 켤레 분포 - Normal-Inverse-Wishart Distribution

앞에서 임의의 벡터를 뽑아낼 수 있는 확률 분포에 대해서 설명했습니다. 앞서 설명했듯이, LDA에 단어 임베딩을 적용하기 위해서는 각 주제가 뽑아내는 값이 1~V 사이의 임의의 정수가 아니라 그 범위가 정해지지 않은 벡터값이어야 합니다. 따라서 주제 분포는 다변수 정규분포로 두는 것이 적합하겠습니다. 

그러면 켤레 사전 분포로는 무엇이 적합할까요? 다항 분포의 켤레 사전 분포로 디리클레 분포가 있었던것처럼, 다변수 정규분포의 켤레 사전분포도 수학자들이 이미 만들어 두었습니다. (다만 전공자 아니면 아무도 모를뿐이죠) 그 이름하여 Normal-Inverse-Wishart Distribution 입니다. 길고 끔찍한 이름에 당황하실 수 있을텐데 유도 방법이나 계산식을 외울 필요는 전혀 없으니깐 그런건 싹 다 무시하고 개념만 보고 넘어갑시다.


Normal-Inverse-Wishart 분포는 총 4개의 파라미터를 가집니다. μ, λ, Ψ, ν인데요 각각의 역할이 있습니다.

μ: 평균값 (p x 1 행렬)

λ: inverse scaling 파라미터 (분산의 역수, 뽑히는 값이 평균으로 부터 얼마나 떨어져 있는지를 조절합니다.) (실수값)

Ψ: inverse scale 행렬 (이 역시 분산에 영향을 미침) (p x p 행렬)

ν: 자유도 (p - 1 보다 큰 실수값)


그냥 4가지 파라미터가 이 분포를 구성한다고 생각하면 됩니다. 그럼 이걸 어디에 쓰느냐 하면? 베이즈 추론에 대한 이야기로 돌아가봅시다.


베이즈 추론의 목적은 관측을 통해서 모델을 더 그럴싸하게 수정해나가는 것을 반복하여 정교한 모델을 구축하는 것입니다. 주머니 안에 0, 1, 2가 써진 구슬이 여러 개 들어 있는데, 그 비율은 모른다고 생각해봅시다. 이 때 사전 분포는 주머니에 대한 정보가 없을때 임의로 우리가 정해놓는 분포입니다. 주머니에서 구슬 3개를 뽑았는데, 각각 0, 0, 1이 나왔습니다. 이 때 뽑힌 구슬이 관측 결과라고 할 수 있겠죠. 최종적으로 우리는 관측 결과를 통해 더 정교한 사후분포를 만들 수 있습니다.


주머니 안에 무한히 많은 벡터 값들이 들어 있고, 왠지 이 벡터 값(편의상 3차원이라고 가정)들은 어떤 정규분포를 따를것만 같습니다. 이 경우 우리는 사전 분포를 Normal-Inverse-Wishart 분포로 설정할 수 있습니다. 일단 잘 모르겠으니 μ = (0, 0, 0), λ = 1, Ψ = (1 0 0 || 0 1 0 || 0 0 1) (단위행렬), ν = 3 으로 둡시다.

그리고 실제로 이 주머니에서 하나의 벡터값을 뽑아봅시다. 그랬더니 y = (1, 0, 0.6)가 나왔습니다. 그러면 우리는 이제 이 사전분포를 좀더 정교한 사후분포로 계산할 수 있습니다. 그 계산식은 다음과 같습니다.


간단하죠? 이 계산식에 따르면 새로운 파라미터는 다음과 같습니다.

μ = (0.5, 0, 0.3)

λ = 2

ν = 4

Ψ = (1.5  0  0.3 || 0  1  0 || 0.3  0  1.18)


그리고 또 다음 벡터값을 뽑고, 그렇게 얻은 y를 가지고 다시 파라미터를 업데이트하는 것을 반복하면서 점점 사후분포를 개선해 나갑니다. 그리고 이렇게 얻은 분포에서 임의의 값 x가 등장할 확률을 계산할 수 있죠. Murphy에 따르면 이때 공분산 Σ는 다음과 같이 계산할 수 있다고 합니다.[각주:1]


그래서 이 분포에서 임의의 벡터 x가 등장할 확률을 다음과 같이 추론할 수 있습니다.

[각주:2]


G-LDA의 깁스 샘플링 과정

이제 이걸 이해하는데 필요한 지식은 어느정도 갖췄습니다. 가우시안 LDA의 깁스 샘플링 과정은 본질적으로 LDA의 깁스샘플링 과정과 동일합니다. 그 순서는 다음과 같습니다.


  1. (초기화) 모든 문헌의 모든 단어에 임의의 주제를 부여한다.
  2. (초기화) 각 주제에 부여된 단어들의 벡터를 바탕으로 주제별 파라미터 μ, λ, ν, Ψ를 계산한다.
  3. (샘플링) 각 문헌의 각 단어에 대해
    1. 단어 하나를 선정해 제외시키고, 해당 주제의 파라미터 μ, λ, ν, Ψ를 업데이트한다.
    2. 뽑은 단어가 주제k(=1~K)에 속할 확률을 계산한다.
    3. 계산된 확률을 기반으로 임의의 주제 k를 선정해 해당 단어에 배정하고 다시 그 주제의 파라미터 μ, λ, ν, Ψ를 업데이트한다.
    4. 모든 문헌의 모든 단어에 대해 반복
  4. 충분히 여러번 샘플링을 반복한다.


3.2에서 단어가 어떤 주제 k에 속할 확률은 다음과 같이 계산됩니다. (+ 논문에서는 λ 대신에 κ를 사용하고 있습니다. 둘이 같은걸 가리키는 것이니 헷갈리지 마시길!)

이때

[각주:3]

첫째항은 LDA와 동일하게 문헌 내 단어 중 주제 k에 속하는 단어의 수에 디리클레 하이퍼 파라미터를 더한 값이 됩니다. 둘째항은 바로 윗 단락에서 소개한 Normal-inverse-wishart 분포에서 임의의 벡터가 등장할 확률을 계산하는 부분이구요.


식을 잘 보면 아시겠지만, |Σ|(x-μ)TΣ-1(x-μ)라는 행렬 연산을 수행해야합니다. 별거 아닌것처럼 보이지만, 매 샘플링에 모든 단어에 대해서 주제 개수 K개씩 행렬식(det)과 역행렬과 행렬 곱셈 연산을 수행해야하는데 이게 연산량이 굉장히 많습니다. 시간복잡도로 따지면 행렬 크기의 세제곱에 비례하는 연산시간 O(p^3)이 소요되는데, 비현실적이기 때문에 이를 해결하기 위한 방법이 필요합니다.


숄레스키 분해(Cholesky decomposition)

숄레스키 분해는 행렬을 삼각행렬로 분해하는 것을 가리킵니다. 실수 정치행렬은 다음과 같이 숄레스키 분해가 가능합니다.

예를 들어 다음 3x3행렬은 다음과 같이 분해가 가능합니다.


즉 모든 실수 정치행렬은 하삼각행렬과 하삼각행렬의 전치행렬의 곱으로 나타낼 수가 있고, 따라서 하삼각행렬 하나만으로 전체 행렬을 나타내는게 가능합니다. 게다가 이렇게 표현하면 여러 행렬 연산이 더 간편해지는 장점이 있습니다. 먼저 A의 행렬식 경우 L의 대각선 원소들의 곱의 제곱으로 간단하게 계산할 수 있습니다. 위의 예시에서는 (2*1*3)^2 = 36이 되겠습니다.

또한 bTA-1b도 역행렬을 계산할 필요 없이 간단히 계산가능합니다. 

이므로  bTA-1b를 계산하기 위해선 Lx=b의 해를 가우스 소거법으로 간단하게 구하면 됩니다. L이 하삼각행렬이기 때문에 가우스 소거법 역시 간단해집니다.


그리고 파라미터 업데이트 과정에 필요한

연산의 경우 Rank 1 Update를 통해 L에서 다시 A를 구하지 않아도 수행가능합니다.


한줄로 요약하자면, 우리는 굳이 Ψ나 Σ (어차피 Σ는 Ψ의 실수배일 뿐이니) 전체를 다 가지고 있을 필요 없이 숄레스키 분해 결과인 하삼각행렬 L 하나만 가지고 있으면 되고, 이를 통해서 모든 행렬 연산을 단순화할 수 있다는 것입니다. 논문의 저자는 최종적으로 O(K*p^2)의 시간복잡도를 달성하는데 성공하였다고 밝히고 있습니다. p가 보통 100이상의 큰 수인것을 감안할때 매우 큰 향상이 있었다고 봐도 되겠네요.


기타

저자가 작성한 java 코드가 github에 공개되어 있습니다. 코드가 조금 지저분하기는 한데, 전체적인 알고리즘을 이해하는데에는 아주 좋은듯 합니다. 

https://github.com/rajarshd/Gaussian_LDA


연구용으로 LDA나 DMR 등을 사용할때 영 미덥지 않는 결과가 나와 답답할 때가 많았는데 단어 임베딩을 결합하면 이를 개선하는데 도움이 될것 같다는 기대가 개인적으로는 많이 됩니다. 연산량이 LDA보다 크게 늘어서 대량에 데이터에 적용하기에는 조금 무리가 있을법도 하지만 충분히 발전가능성이 있는 좋은 방법이라고 개인적으로 생각합니다.


  1. Kevin P. Murphy. 2012. Machine Learning: A Probabilistic Perspective. The MIT Press. [본문으로]
  2. https://en.wikipedia.org/wiki/Multivariate_normal_distribution#Density_function [본문으로]
  3. https://en.wikipedia.org/wiki/Multivariate_t-distribution#Definition [본문으로]
이 댓글을 비밀 댓글로