[Data Mining] Smoothing Techniques

이번 포스팅에서는 Smoothing에 대해서 알아보려고 한다. 보통 Smoothing이라고 하면 부드럽게 스무스 하게 보통 이런 것을 생각하게 되는데, 그거 맞다. 이번 포스팅에서 가장 대표적인 Smoothing인 Laplace smoothing 먼저 공부하고 Interpolation과 Backoff도 공부해볼 것이다. 마지막으로 Kneser Ney까지 포스팅하는 걸로 하자.

우선 Smoothing이 언제 필요한지 알아보자. 예를 들어, Naive Bayes를 쓰는데 training과정에서는 나오지 않았던 경우가 test 과정에서 나올 수 있다. 이런 경우를 zero count problem 이라고 한다.

위의 그림은 Golf data set으로 Naive Bayes를 만드는 과정에서 conditional probabilities를 계산해놓은 것이다. 위의 경우에서 overcast-no는 한번도 관찰되지 않았다. 그런데 test 과정에서 overcast-no가 나타나면 다른 확률이 아무리 높아도 0을 곱해서 확률은 0이 된다. 이런 경우를 막기 위한 것이 Smoothiing이고 Laplace smoothing은 가장 직관적인 해결방법이다. 

Laplace smoothing은 모든 경우의 수를 적어도 한번 이상은 봤다고 가정하는 것이다. 따라서 아래와 같은 테이블이 만들어진다.

모든 수를 적어도 한번 이상은 봤다고 가정했으므로 분자에는 모든 경우의 수에 1을 더해주었고 분모에는 모든 경우의 수를 더해준 것이다. 이걸 안 해주면 확률의 합이 1이 넘어버리는 이상한 경우가 발생해버린다. 참고로 위의 경우에서 전체 개수가 왜 어디는 11개이고 어디는 12개냐고 물어보면 안된다. 어짜피 Laplace smoothing에서는 전체 개수는 신경쓰지 않고 확률에만 신경쓰기 때문이다.

이게 Laplace smoothing이다. 모든 경우를 한번 이상은 봤다고 가정하여 zero count problem을 해결하는 것이다. 1을 더해서 해결한 smoothing이므로 Add-one smoothing이라고도 한다.

Laplace smoothing을 적용할 수 있는 또 다른 부분은 NLP 쪽에 있는데, N-gram에 적용시킬 수 있다. N-gram은 무엇이냐? 여기서 유명한 예를 하나 봐보자. 

2gram을(bigram) 고려하며 위의 테이블을 봤을 때, 

"I want"가 전체 data에서 827번 나왔따는 것이다. 즉 연속으로 나타난 두개의 단어를 하나의 '구'로 만들어서 그 '구'를 feature로 하겠다는 것이다. 3gram 4gram 5gram .. N gram 모두 숫자만 다르고 원리는 같다. N gram이면 N개의 연속된 단어로 이루어진 '구'를 하나의 feature로 보겠다는 것이다. 

그런데 위의 table에서 보면, I 다음에 to가 나온 경우는 없다(zero count) 이런 경우를 해결하기 위해 bigram smoothing을 적용해보면 아래와 같다.

(V=1446, 즉 전체 data(corpus)에서 발견된 unique한 단어 개수가 1446이다.)

이렇게 하면 확률이 0인 경우는 없으므로 zero count는 해결됐다. 그런데 Laplace Smoothing은 N-gram에는 쓰면 그다지 좋지 않다. 이유는 간단하다. 위의 테이블은 확률 테이블이다. 그러면 위의 두 테이블을 곱해서 다시 count 테이블을 만들어보자. 이것을 reconstructed count라고 한다.

원래의 count와 무지하게 다르다. 그래서 laplace smoothing은 N-gram에는 잘 맞는 방법이 아닌 것이다. 그러면 N-gram일 경우에는 어떻게 해야 좋은가? 그것이 바로 Interpolation 또는 backoff이다. Interpolation은 (중간값을) 채우다. 뭐 이런 뜻이란다. 말 그대로 중간값 채우기다. 우선 공식을 먼저 보자.

뭔가 공식이 복잡한데, 알고보면 아무것도 아니다. 한 단어의 N-gram에 대한 확률을 얻기 위해서 그 단어의 N-gram, (N-1)-gram, (N-2)-gram, ..., 1-gram까지의 확률을 일정 비율로(Weight) 곱해서 합을 구하라는 것이다.(위의 식은 3gram을 가정했기 때문에 λ가 세개만 있는 것이다.) 참고로 저 λ값은 EM algorithm을 통해서 구한다고 하고 합치면 1이 된다고 한다. 이 부분은 나도 잘 모르므로 그냥 넘어가자.

Backoff도 대략 비슷한 개념인데 합하지만 않는다고 보면 된다.

위의 식은 3gram을 가정한 식인데, 3gram에 대한 확률이 있으면(0보다 크면) 그것을 쓰고, 그것이 없으면(0이면) 그 단어에 대한 2gram을 쓰고, 그것도 없으면 1gram을 쓰라는 것이다.

마지막으로 kneser-ney smoothing이다. 이걸 이해하려면 우선 absolute interpolation smoothing 부터 알아야 된다. absolute interpolation smoothing은 아래의 식으로 나타낼 수 있다.

위의 식은 bigram을 가정한 식인데, 특정 단어의 bigram probability는 그 확률에 어느 정도를 빼고(absolute discounting, 즉 무작정 특정 값만큼을 빼주겠다는 것이다.) 그 단어에 대한 1gram을 α만큼 곱해서 더하겠다는 것이다. 이렇게 smoothing을 해주는 것이 absolute interpolation smoothing인데, 이 경우에는 문제가 있다. 유명한 예시로, San Francisco가 있다. 가령 전체 text가 아래와 같다고 할 때,

San Francisco is wonderful city. What a sun-shine San Francisco. Do I want to live in here? Yes of course, I love San Francisco. 

San Francisco가 무지하게 많이 나오는 text가 있다고 하자. 그래서 자연스럽게 Francisco도 많이 나오게 된다. Francisco는 San Francisco가 많이 나왔기 때문에 덩달아 1gram probability가 높게 나온다. 이럴 경우를 고려해준 것이 kneser-ney smoothing이다. kneser-ney smoothing은 absolute interpolation smoothing에서 마지막 1gram probability 더하는 그 부분만 바꿔주면 된다.

사실 이 부분은 나도 정확하게는 잘 모르겠다. 예시가 숫자로 딱 나와있는 그런 것을 찾았다면 나도 쉽게 공부했을텐데, 왜 이거는 예시가 없는지 모르겠다. 그래서 살짝 개념만 말하고 넘어간다. 위에서 말한 1gram 부분은 대략 어떤 식이냐면.. 예를 들어

I like Sam, She loves Sam. My friend Sam.

이런 경우, Sam은 like, loves, friend 라는 세 개의 단어 다음에 왔으므로 p(countinuation)의 분자 부분에 3이 들어간다. 같은 원리를 San Francisco에 적용하면 분자부분에 1이 들어가게 된다. 그러면 Francisco와 같은 경우에는 kneser-ney smoothing을 적용시키면 Sam과 같은 단어로 적용시킬 때보다 확률이 적게 더해진다. 따라서 San Francisco에서 Francisco는 다른 단어에 비해 적은 확률이 더해지게 된다. 

대~략 이런 식이다. -_- 자세하지 못 하나... 그래도 개념이라도 잡으면 그게 어디냐 하는 심정으로 쓴다.