[잠재 디리클레 할당 파헤치기] 3. 깁스 샘플링으로 파라미터 추정

여기까지 오시느라 다들 수고많으셨습니다. LDA에 사용되는 수많은 개념(베이즈 추론, 디리클레 분포 등...)을 지나서 드디어 마지막 깁스샘플링만을 남겼습니다. 베이즈 추론에서 사후 확률을 쉽게 계산하기 위해 켤레 사전분포를 사용한다고 했었는데요, 앞서 설명했던

식에서 문헌 내의 모든 단어 개수가 N개라고 하면 관측되는 단어 벡터 W도, 그 단어들의 주제 벡터인 Z도 모두 N차 벡터가 됩니다. 즉 N차 벡터가 주어졌을때 확률을 계산하는 일이 필요하게 됩니다. N값이 커질수록 이 계산은 기하급수적으로 복잡해집니다. 이를 빠르고 쉽게 계산하기 위해서 깁스 샘플링(Gibbs Sampling)이라는 편법을 사용하게 됩니다. 이 과정이 어떻게 이뤄지는지 살펴보도록 합시다.

깁스 샘플링

N차의 자료를 대상으로 확률 분포를 계산하기는 어렵습니다. 이를 위해 N차의 자료를 1차 자료 N개가 모인것으로 가정하고, 나머지 N-1개를 고정하면 한 차원에 대해서만 자료를 샘플링할 수 있습니다. 이렇게 N개의 차원에 대해 각각 자료를 샘플링하여 이를 합치면 전체 N차원의 자료를 샘플링한것과 같지 않겠냐는 것이 깁스 샘플링의 아이디어입니다.

위의 LDA 계산식 역시 N차 벡터에 대한 확률 분포 계산이기 때문에 깁스샘플링을 적용하면 1차원의 자료를 샘플링하는 것으로 전체 확률 계산을 수행할 수 있겠죠. 이때 1차원의 자료는 결국 단어 1개가 되는것이구요. 따라서 단어를 1개씩 보아가면서 전체 확률을 추론하는 과정을 거치게 됩니다.

앞선 거인들이 열심히 식을 풀어본 결과 P(Z|W)는 깁스 샘플링을 통해서 다음과 같이 근사할수 있다고 합니다.

C_mj는 단어 m이 주제 j에 속하는 횟수이고, C_dj는 문헌 d의 단어들이 주제 j에 속하는 횟수입니다. 문헌 d에 속하는 어떤 단어 m이 주제 j에 속할 확률은 주제 j에 속하는 모든 단어 중에서 단어 m이 차지하는 비중과 문헌 d에 속하는 모든 주제 중 주제 j가 차지하는 비중의 곱에 비례한다는 것입니다.

LDA를 수행해보자

깁스샘플링을 이용한 LDA는 다음과 같은 절차로 이뤄집니다.

1. 각각의 단어에 임의의 주제를 배정한다
2. (잘못됐겠지만) 모든 단어에 주제가 배정되어있고, 그 결과 문헌별 주제 분포와 주제별 단어분포가 결정되었음. 이를 깁스샘플링을 통해서 개선해 나가자.
3. n번째 단어를 골라 빼낸다. (나머지 단어들이 모두 적절하게 배정되어 있다고 가정하고)
4. 빼낸 단어를 제외하고, 그 단어가 속한 문헌의 주제분포(P(Topic | Document))를 계산하고, 그 단어가 속한 주제의 단어분포(P(Word | Topic))를 계산한다. P(Word | Topic) * P(Topic | Document)에서 Topic을 하나 뽑아 그 단어에 배정한다.
5. n <- n+1로 하고 3번으로 돌아간다.
6. 충분히 반복하다 보면 값들이 수렴하고 안정되게 된다. 그럼 끝.

글로만 봐서는 어떻게 작동하는지 잘 이해가 안되게 마련이니 실제로 해봅시다. 다음과 같은 문헌들이 있어요. α = 0.1, β = 0.001이라고 하고, 주제 개수 K=2로 두고 LDA를 수행해 봅시다.

• A: Cute kitty
• B: Eat rice or cake
• C: Kitty and hamster
• D: Eat bread
• E: Rice, bread and cake
• F: Cute hamster eats bread and cake

불용어를 제거하고 의미있는 단어만 남기면 다음과 같이 될겁니다. (문헌별로 색깔 다르게 칠했습니다.)

1.각각의 단어의 임의의 주제를 배정한다

주제가 2개이므로 #1, #2 둘 중에 하나를 각 단어에 임의로 배정했습니다. 이렇게 단어가 배정되었으니 우리는 이제 문헌별 주제 분포와 주제별 단어분포를 계산할 수 있습니다.

2. 문헌별 주제 분포, 주제별 단어 분포를 계산한다.

문헌별 주제분포 θ입니다. 각 값이 0으로 끝나는게 아니라 .1인 이유는 모든 값에 하이퍼 파라미터 α값이 합쳐져 있기 때문입니다. A문헌에는 #1,#2가 각각 하나씩이므로 (1.1, 1.1)이 계산된것이고, C문헌에는 #2만 2개 배정되었으므로 (0.1, 2.1)가 계산된것 입니다.

주제별 단어분포 φ입니다. 마찬가지로 0.001로 끝나는 이유는 하이퍼 파라미터 β값이 합쳐져 있기 때문입니다.

3. 첫번째 단어를 골라 빼낸다.

첫번째 단어 cute를 빼냈습니다. 따라서 문헌별 주제분포, 주제별 단어분포도 다음과 같이 바뀌게 됩니다.

4. 새로운 주제를 배정한다

문헌 A에 속하는 단어 cute가 #1에 속할지 #2에 속할지 판단해야합니다. 문헌내 주제 분포를 따르면

(문헌 A 내에 #1이 있을 확률) = 0.1 / (0.1+1.1) = 0.083...

주제별 단어분포를 따르면 

(#1 내의 단어가 cute일 확률) = 0.001 / 8.007 = 0.00012...

따라서 (A 안의 cute가 #1일 확률) = 0.083 * 0.00012 ... = 0.00008... 이 됩니다. 

주제별 단어분포에서 확률 계산시 SUM으로 나눈 덕분에 한 주제에 너무 많은 단어가 몰리지 않게 됩니다. 특정 주제에 단어가 많이 몰리게 되면 SUM이 커지게되고, 그 결과 정규화 이후 단어의 비중이 낮아지기 때문에 그 주제에 단어가 배정될 확률이 낮아지게 되죠. 문헌 내의 단어끼리 유사한 주제를 가지려는 경향과 한 주제에 너무 많은 단어가 몰리는 것을 막는 경향이 서로 균형을 이루며 적절한 지점에서 주제별로 단어를 분할하여 가지는 현상이 발생합니다. 놀라운 일이죠!

마찬가지로 #2에 속할 확률도 계산해봅시다.

(문헌 A 내에 #2이 있을 확률) = 1.1 / (0.1+1.1) = 0.916...

(#2 내의 단어가 cute일 확률) = 1.001 / 8.007 = 0.125...

따라서 (A 안의 cute가 #2일 확률) = 0.916 * 0.125 ... = 0.114... 가 됩니다.

즉 A안의 cute는 (0.00008, 0.114)의 카테고리 분포를 따라 #1이 되거나 #2가 되겠죠. 가능도 비중을 따라 #1이나 #2 중에 하나를 뽑습니다. (물론 높은 확률로 #2가 뽑히겠죠. 하지만 #1이 뽑힐 가능성이 아예 0이 되지는 않습니다. 이는 하이퍼 파라미터 α와 β가 하는 역할 중 하나에요.) 여기서는 #2로 배정되었다고 가정할게요.

3-1. 두번째 단어를 골라서 빼낸다.

여기서부터는 반복입니다. 설명은 다 적지 않도록 하고 각 단어 샘플링단계마다 주제 배정이 어떻게 바뀌었는지만 보여드리도록 하겠습니다.

두번째 단어 업데이트. #2에 배정됨

세번째 단어 업데이트. #1에 배정됨

네번째단어 업데이트. #1에 배정됨

.

.

.

마지막 단어까지 업데이트가 끝나면 이것이 1회 깁스샘플링을 마무리한것이 됩니다. 이 작업을 적절하게 여러번 반복하다보면 모든 단어가 적절하게 자기 주제를 찾아 배정되게 될것이라는 것이 깁스샘플링을 이용한 LDA의 가정이죠. 수렴할때까지 반복하면 다음과 같은 결과가 나옵니다.

최종 결과물

이를 바탕으로 구한 문헌별 주제분포, 주제별 단어분포는 다음과 같습니다.

이를 보기 좋게 정리하면 다음과 같이 되겠죠.

A문헌: #2(0.955), #1(0.045)

B문헌: #1(0.968), #2(0.032)

C문헌: #2(0.955), #1(0.045)

D문헌: #1(0.955), #2(0.045)

E문헌: #1(0.968), #2(0.032)

F문헌: #1(0.596), #2(0.404)

#1: eat(0.272), cake(0.272), bread(0.272), rice(0.181), cute(0.001), kitty(0.001) hamster(0.001)

#2: cute(0.333), kitty(0.333), hamster(0.333), eat(0.001), rice(0.001), cake(0.001), bread(0.001)

적절하게 잘 분류된것 같군요. #1에는 '음식'이라는 타이틀을, #2에는 '귀여운 동물'이라는 타이틀을 붙여주면 딱 좋겠군요.

한계

위에서 소개한 LDA 분석방법은 본질적으로 샘플링을 이용하기 때문에, 아무리 반복횟수를 높여서 값이 안정되게 한다고 하더라도 실행시마다 결과가 달라질 수 있는 가능성을 안고 있습니다. 특히 문헌 집합이 작을수록, 그리고 단어가 희소(sparse)할 수록 랜덤값에 의해 실행결과가 좌우될 가능성이 큽니다. 이는 위 방법이 가지고 있는 근본적인 한계라고 할 수 있습니다.

또한 LDA가 묶어주는 주제가 사람이 인지하는 주제와 얼마나 일치하는가에 대한 문제도 있습니다. 단어의 분포만을 가지고 주제를 묶어내는 것이기 때문에 실제 사람이 생각하는 주제와 다를 수 있고, 또한 주제 간의 관계와 같은 다른 배경 정보들을 활용하지 못한다는 점도 한계겠지요.

마지막으로 문헌 내에 주제가 몇 개나 들어있는지 알수 없기 때문에 K값을 몇으로 두는게 적절한지 모른다는 것 또한 문제입니다. 적절한 K값을 설정하고 그에 따르는 α, β값을 잘 튜닝해야 좋은 결과를 얻을 수 있을겁니다.

참고링크

https://flonelin.wordpress.com/2017/03/08/lda/ Latent Dirichlet Allocation

알고리즘 구현

위에서 설명한 깁스 샘플링을 이용해 LDA를 구현한 코드를 https://github.com/bab2min/tm-cpp에서 살펴볼 수 있습니다. 이론은 복잡했는데, 막상 코드를 보면 간단해서 이 단순한 반복 작업으로 잠재적인 주제 추출이 어떻게 되는지 신기하더라구요.