[언어모델] HPYLM : 계층적 피트만-요 언어 모델

언어 모델(Language Model)은 특정한 문장(단어의 나열)이 등장할 확률을 계산해주는 모형입니다. 당연히 언어별로 사용되는 단어나 문법에 차이가 있을 것이므로, 특정 문장의 등장 확률 값이 언어마다 다르겠죠. 그렇기에 특정 언어의 문장 등장 확률을 모형화한다는 점에서 언어 모델이라고 이름을 붙인듯 합니다. 

그런데 문장의 등장 확률을 계산하는게 무슨 쓸모가 있을까요? 다음 예시를 생각해봅시다.

길이 많이 막혀서 학교에 _____.

위와 같은 문장이 있습니다. 마지막 단어가 빠져있는데, 한국어를 할 줄 아는 사람이라면, 자연스럽게 마지막에 들어갈 단어가 '늦었다'나 이와 비슷한 단어일것이라고 예상할 수 있습니다. '배고프다'라는 단어가 들어갈 것이라고 예상하는 사람은 한국어를 잘못 배운 사람이겠죠. 언어 모델을 이용하면 마지막 위치에 '늦었다'가 들어가는 경우와 '배고프다'가 들어가는 경우의 확률을 각각 구할 수 있을 겁니다. 훌륭한 한국어 언어 모델이라면 '늦었다'가 들어가는 경우의 확률이 '배고프다'보다 훨씬 높겠죠.

즉 언어 모델은 다음 단어를 예측하는데 쓰일 수 있습니다. 예측을 할 수 있으면 뭐가 좋으냐! 일례로 음성 인식을 수행하는 경우, 마지막 단어가 시끄러워서 노이즈 때문에 잘 안들렸습니다. 그래서 '늦었다'나 '노젓다'가 비슷하게 들려서 어느 단어를 넣어야할지 애매할때, 언어 모델을 활용하면 적절한 단어인 '늦었다'를 채워넣을 수 있겠죠. 이처럼 언어 모델은 음성 인식을 비롯하여, 기계 번역, 필기 인식, 철자 검사 등등, 특정 언어의 특징을 활용해야하는, 자연언어처리 분야에 널리 쓰일 수 있습니다.

본 포스팅에서는 언어 모델의 기본적인 개념부터 현재 가장 높은 성능을 보이고 있는 HPYLM까지 개략적으로 훑어보는 시간을 갖도록 하겠습니다.

언어 모델의 수학적 표현

총 N개의 단어(w_1, w_2, w_3, ... w_n)로 이뤄진 문장이 있다고 합시다. 문장은 단어들의 나열(순서가 중요한 영향을 미치는)이므로, i번째 단어가 등장할 확률은 그 이전의 i-1개의 단어들에게 영향을 받는다고 할 수 있겠습니다. 즉 i번째 단어로 w_i가 등장할 확률은 다음과 같이 조건부 확률로 표현할 수 있습니다.

따라서 전체 N개의 단어로 이뤄진 문장이 나타날 확률은 w_1이 등장할 확률부터 w_n이 등장할 확률까지를 모두 곱하면 되므로

가 되겠죠! 즉 문장이 등장할 확률은 단어가 등장할 조건부 확률의 곱으로 바꿔 쓸 수 있으니 이제 우리는 단어가 등장할 확률에만 신경 쓰면 됩니다. 단어가 등장할 확률은 어떻게 따질 수 있을까요?

유니그램(Unigram) 언어 모델

가장 단순한 것은 각 단어들이 등장하는 것이 서로 독립이라고 가정하는 것입니다. 즉

이라고 하자는 것입니다. 유니그램 언어 모델은 결국 단어의 순서는 무시하고 등장 횟수만 보겠다는 것과 같습니다. 그렇기 때문에 흔히 이 모형을 Bag of Words(BOW, 단어 주머니) 모형이라고 부르기도 합니다. 단어가 등장할 확률을 계산하는 것은 간단하죠. (해당 단어의 등장 횟수) / (전체 코퍼스의 단어수)라고 하면 되니깐요.

당연히도 단어 순서를 고려하지 못하는 너무 단순한 모형이기에 한계가 명확하다는 것 굳이 언급하지 않아도 되겠죠?

N-gram 언어 모델

유니그램 언어 모델의 한계를 극복하기 위해서 N-gram 언어 모델이 등장했습니다. 이는 특정 단어가 등장할 확률은 그 단어 앞쪽의 n-1개의 단어에 영향을 받는다고 가정하는 것입니다.

간단하죠? a, b, c 단어 뒤에 d가 등장할 확률을 계산하는 것은 유니그램 모델과 비슷하게 간단합니다. (a, b, c, d가 연속하여 등장하는 경우의 수) / (a, b, c가 연속하여 등장 경우의 수)로 계산하면 됩니다.

N이 높아질수록 처음 제시하였던 원래의 언어 모델 형태와 유사하게 됩니다. 즉 N이 클수록 N-gram 모델은 언어 모델을 더 잘 근사하게 되는데요, 문제는 N을 키울수록 계산량이 급격하게 커진다는 문제점이 있습니다. 전체 단어가 1만 가지라고 할때 N=3일 경우만 하더라도 총 1만*1만*1만 = 1조 가지의 경우를 모두 따져 봐야합니다. N을 더 키우는 것은 현실적으로 어렵습니다. (따라서 현실적으로 대게 N=2~4로 사용합니다.)

유니그램 및 N-gram 모델은 그 자체로는 큰 허점이 있습니다. 학습에 아무리 큰 코퍼스를 사용한다고 하더라도, 거기에 모든 종류의 단어가 들어가 있기는 어렵습니다. 특히 N-gram의 경우 전체 단어의 종류를 V개라고 했을 경우, V^N가지 조합을 따져야하는데 학습 코퍼스에 V^N가지의 조합이 모두 등장하기는 더욱 어렵습니다. 즉 이 경우 해당 단어가 등장한 횟수가 없기 때문에 확률이 0이 되어버립니다. 따라서 만약 신조어나 기존 학습 데이터에 없는 단어가 포함된 문장의 경우 이 언어모델은 해당 문장의 확률을 전부 0으로 계산해버리는 문제가 생기죠. 이를 방지하기 위해 N-gram 모델은 필연적으로 Smoothing기법(학습 데이터에 등장하지 않은 단어도 확률이 0이 되지 않도록 조절해주는 기법)을 사용해야만 합니다.

Kneser-Ney Smoothing 기법

크네저-네이 Smoothing(Kneser-ney Smoothing)은 가장 성능이 좋다고 알려진 N-gram smoothing기법입니다. 이 기법은 높은 차수의 N-gram과 낮은 차수의 N-gram을 적절히 섞어서 최적의 확률을 계산해 내는데 그 계산식은 다음과 같습니다.

P^KN(w | u)은 크네저 네이 스무딩이 적용된 상황에서 단어열 u뒤에 단어 w가 등장할 확률을 나타냅니다. C(uw)는 단어열 uw가 등장한 횟수, C(u·)는 모든 w에 대해 C(uw)를 합한 값입니다. N(u·)는 C(uw)가 0보다 큰 w의 개수를 나타냅니다. 그리고 마지막으로 u는 u에서 첫번째 단어를 뺀(즉 u = w_1 w_2 w_3이었다면 u = w_2 w_3) 단어열입니다. 그리고 더 짧은 길이의 C(uw)를 계산할때는 빈도 세는 방식을 약간 바꿉니다. 원래는 단어열 uw가 등장한 횟수를 전부 세었다면, uw부터는 uw 앞에 등장한 단어의 종류 수만 세는 것으로 세는 방식을 다르게 합니다.

굉장히 복잡해보이지만 핵심은 다음과 같습니다.

• uw가 등장한 횟수가 0보다 클 경우 거기서 d를 빼간다. 등장한 횟수가 0일때는 더 뺄수 없으니 그대로 0으로 둔다. 
• 전체에서 d/C(u·)를 뺀 수가 총 N(u·)개므로, 이를 모든 단어에 골고루 분배해서 0인 확률을 0보다 높게 해준다.
• 이때 분배해주는 비율은 (N-1)-gram의 확률 값에 비례해서 나눠준다.

일종의 확률 세계의 사회 복지 정책 같은 것이죠! 이 때 빼가는 값인 d를 할인계수(discount factor)라고 합니다. 대게 0<d<1 인 범위에서 그 값을 설정하며, d가 0에 가까울수록 단순 N-gram 모형에 가까워지고, 1에 가까워질수록 스무딩이 더 강해집니다.

Hierarchical Pitman-Yor Language Model

짠! 드디어 목표했던 HPYLM에 도달했습니다. Teh, Y. W. (2006). A Bayesian interpretation of interpolated Kneser-Ney. 의 논문에 따르면 위에서 설명했던 Kneser-Ney Smoothing을 적용한 N-gram이 결국 Pitman-Yor 과정의 반복으로 표현될 수 있다고 합니다. 더 정확히는 계층적 Pitman-Yor 과정을 Kneser-Ney Smoothing의 일반화 형태로 볼 수 있고, 깁스 샘플링과 같은 과정으로 더 정교하게 모델 학습이 가능하다는 것이 포인트가 되겠네요.

먼저 Pitman-Yor Process(피트만-요 과정)에 대해서 살펴봐야 하겠습니다. 이 녀석은 예전 게시물에서 다뤘던 Dirichlet Process(디리클레 과정)의 일반화 버전이라고 할 수 있습니다. 디리클레 과정 DP를 다시한번 설명하자면, 이 녀석은 원 분포 G에서 G와 유사한 이산 분포를 뽑아내는 확률 과정입니다. 이 과정에는 하나의 하이퍼 파라미터 θ가 관여합니다. DP(G, θ) 과정을 잘 설명한 예시가 바로 중국집 식당 과정(Chinese Restaurant Process)이죠. 또 다시 식당을 차려보도록 하겠습니다.

Dirichlet Process의 중국집 식당 비유

원탁이 무한히 많고, 탁자에도 무한히 많은 의자가 있어서 손님이 무한히 들어올 수 있는 중국집 식당이 있습니다. 손님들이 자리에 앉는데는 특별한 규칙이 있습니다.

1. 손님은 요리가 차려진 식탁에 앉거나 빈 식탁에 앉을 수 있습니다. 그리고 손님은 식탁에 인기도를 기준으로 자리를 잡습니다.
2. 요리가 차려진 식탁의 인기도는 식탁에 앉아 있는 사람들의 수 n입니다.
3. 빈 식탁의 인기도는 집중 파라미터 θ의 값입니다. 만약 손님이 빈 식탁에 앉기로 결정했으면, 그때 원 분포 G에서 임의의 값을 하나 뽑아 그 식탁의 요리로 놓습니다.
4. 손님이 차례대로 계속 들어와 앉게 되면 요리별 손님의 비율은 특정한 값으로 수렴하게 됩니다. 이 때 각 요리의 수가 DP(G, θ)에서 뽑힌 서로 다른 값의 수가 되며, 각 요리의 손님 비율이 DP(G, θ)에서 해당 값이 뽑힐 확률이 됩니다.

당연히 처음에 들어온 손님은 빅 식탁에 앉아서 G로부터 새로운 요리를 뽑아와야겠죠. 단 손님이 무한히 들어온다고해서 식탁이 무한히 늘어나지는 않습니다. θ이 유한한 값이므로, 손님이 계속 늘어날수록 다른 식탁의 인기도는 계속 상승하고, 상대적으로 θ가 차지하는 비중은 작아지기 때문에 빈 식탁을 선택할 확률이 줄어들기 때문이죠. 그렇기에 θ가 클수록 다양한 식탁이 생길 경향이 증가합니다. (즉, 원래의 G 분포를 더 많이 닮게 됩니다. 이론적으로 θ가 무한대로 발산하면 DP(G, θ)는 G로 수렴하게 됩니다.)

Pitman-Yor Process의 중국집 식당 비유

PYP는 DP와 굉장히 유사하지만 할인 계수(discount factor)가 추가되었다는 점이 다릅니다. 기본적인 가정은 DP와 같으므로 생략하겠습니다. PYP(G, d, θ)에서 샘플링을 하는 과정은 다음 중국집 식당을 통해 설명될 수 있겠습니다.

1. 손님은 요리가 차려진 식탁에 앉거나 빈 식탁에 앉을 수 있습니다. 그리고 손님은 식탁에 인기도를 기준으로 자리를 잡습니다.
2. 요리가 차려진 식탁의 인기도는 식탁에 앉아 있는 사람들의 수 n에서 할인 계수 d를 뺀 값(n-d)입니다.
3. 빈 식탁의 인기도는 θ + N*d(N은 기존의 요리가 차려진 식탁의 개수)의 값입니다. 만약 손님이 빈 식탁에 앉기로 결정했으면, 그때 원 분포 G에서 임의의 값을 하나 뽑아 그 식탁의 요리로 놓습니다.
4. 손님이 차례대로 계속 들어와 앉게 되면 요리별 손님의 비율은 특정한 값으로 수렴하게 됩니다. 마찬가지로 이 분포가 PYP(G, d, θ)의 분포가 됩니다.

차이점은 요리가 차려진 식탁들의 인기도를 d씩 감소시키고, 이 것을 빈 식탁의 인기도로 몰빵해주었다는 것입니다. 만약 d = 0이면 이 과정은 DP와 동일하게 됩니다. d >= 1 이상이면 손님이 1명인 식탁의 인기도가 0이 되어버리므로, 0 <= d < 1로 제한할게요. 

할인계수가 도입되면 무엇이 달라질까요? 일반적으로 DP는 빈익빈 부익부의 분포를 잘 모델링한다고 평가받습니다. 손님이 많이 앉은 식탁일수록 인기도가 높기 때문에 더 많은 손님이 앉기 때문이죠. 우리가 다루는 언어는 본질적으로 빈익빈 부익부, 지프의 법칙을 따릅니다. 즉 소수의 어휘가 전체 중 대부분의 비중을 차지하고, 대부분의 어휘가 작은 비중을 나눠서 차지하고 있는 현상이죠. 이 대다수의 어휘가 작은 비중을 나눠서 차지하고 있는 구간을 긴 꼬리(Long tail)라고 합니다. DP의 약점은 Long tail을 잘 묘사하지 못한다는 것입니다. 식당에 들어오는 손님이 늘어날수록 θ값은 상대적으로 작아지므로, 빈 식탁에 앉을 확률은 더욱 낮아지기 때문에, 굉장히 많은 수의 식탁을 만들어내지는 않습니다. 반면 PYP는 요리가 차려진 식탁이 늘어날수록 빈 식탁의 인기도 역시 조금씩 증가하기 때문에, DP보다 더 긴 꼬리를 잘 묘사할 수 있습니다. 즉 멱법칙을 따르는 분포를 근사하는데 강점이 있습니다.

Hierarchical Pitman-Yor Process

자 그런데 PYP를 어떻게 N-gram 모델과 결합시킬 수 있을까요? Teh의 놀라운 아이디어를 한번 살펴봅시다. PYP가 원 분포 G와 유사한 분포를 (긴 꼬릴를 잘 유지하면서) 뽑아내는 확률 과정이라고 설명했었습니다.  단어열 a, b 뒤에 단어 w가 등장하는 확률 분포 G(w | a, b)는 잘 생각해보면 단어열 b 뒤에 w가 등장하는 확률 분포 G(w | b)와 어느 정도 유사할 것입니다. 거꾸로 말하면 G(w | b)에서 G(w | a, b)가 도출될 수 있는 것이구요. 이를 PYP로 설명할 수 있지 않을까요?

G(w | a, b) ~ PYP(G(w | b), d, θ)

마찬가지로 G(w | b)도

G(w | b) ~ PYP(G(w), d, θ)

...

와 같이 생각할 수 있습니다. 

즉 N-gram 모델의 확률 분포는 (N-1)-gram의 확률분포와 관련이 있고, 이를 PYP로 설명할 수 있으므로, 이를 재귀적으로 적용하면 궁극적으로 가장 기본적인 Unigram 모델에 도달하게 되겠죠. 이 Unigram 모델 역시 모든 단어가 고르게 등장하는 uniform distribution에서 PYP로 추출된 것으로 볼 수 있습니다. 따라서

G(w | Φ) ~ PYP(G₀, d₀, θ₀)

G(w | u) ~ PYP(G(w | u), d_|u|, θ_|u|)

이렇게 재귀적으로 확률 분포를 추출해 나감으로써 앞에 N개의 단어열이 등장하였을때 다음 단어가 나타날 확률 분포를 계산할 수 있습니다. 이때 d, θ 계수는 u의 길이에 따라서 다르게 주는 것이 좋다고 합니다. 논문에 따르면 이 두 파라미터는 샘플링 과정에서 베타 분포와 감마 분포를 사용하여 최적의 값으로 추정할 수 있다고 하구요.

이렇게 단순하던 N-gram 모델을 확률 과정으로 치환시켰습니다. 이렇게 하니 토픽 모델링에서 자주 사용하던 깁스 샘플링 같은 기법도 적용할 수 있고, 하이퍼 파라미터 최적화도 가능해졌죠! 즉 해당 언어의 코퍼스를 좀 더 잘 설명하도록 확률 모델을 정교하게 맞출수 있게 된 것이에요! 우와..!

HPYLM의 가능성은 여기서 끝나지 않습니다. HPYLM를 두 겹 쌓아서, 한 겹은 문자->단어를 생성하고, 다른 한겹은 단어->문장을 생성하도록 이중 확률 모델을 구축할 경우, 단어 구분이 전혀 없는 텍스트에서 스스로 단어를 발견하고 이를 통해 적절하게 단어 구분을 해내는 언어 모델을 만들 수 있습니다. 이에 대해서는 다음 포스팅에서 계속 이어서 설명하도록 하겠습니다.

참고 자료

https://en.wikipedia.org/wiki/Language_model

https://en.wikipedia.org/wiki/N-gram

https://en.wikipedia.org/wiki/Kneser%E2%80%93Ney_smoothing

https://en.wikipedia.org/wiki/Dirichlet_process

https://en.wikipedia.org/wiki/Pitman%E2%80%93Yor_process

Teh, Y. W. (2006). A Bayesian interpretation of interpolated Kneser-Ney.