이번 포스팅에서는 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는 다른 단어에 비해 적은 확률이 더해지게 된다. 

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

우와 NLP다. 이거 사실 분야가 너무 큰 분야라서 폴더 하나 새로 만들어서 "시작하며" 부터 시작을 해야 하는 분야이다. 그런데 왜 이게 그냥 Data Mining 폴더 안에 있냐면.. 그렇게 자세하게 하지 않을꺼면서 거창하게 폴더까지 만들고 싶지 않아서이다. 그리고 사실 Data Mining과도 유사한 부분이 많기도 하다.

우선 NLP가 뭐하는 것인지 대략 설명해보자. 한국말로 하면 자연어 처리인데, 말 그대로 컴퓨터가 언어를 "이해하는 것처럼" 만들어 보자는 것이다. 가령 Twitter Data(Twitt)를 컴퓨터가 "Positive" 또는 "Negative"를 예상한다던지, 특정 문단을 보고 어떤 Topic에 속하는 것인지 예측을 한다든지.. 마치 컴퓨터가 인간의 글을 읽고 이해하는 것처럼 보이게 하는 것이다. 

그렇다면 그것을 어떻게 가능케할까? 그것을 위해서 우리는 Preprocessing을 먼저한다. Data를 실제로 Classify 하기 전에 우선 먼저 손을 봐준다는 것이다. 어떻게 손을 봐줄까? 가령 아래와 같은 Twitt이 있다고 해보자.

User1 : Oh my god, I rushed to my class at 8AM but it was cancelled. Give me my sweet morning back :(
User2 : Yeaaaaaaaaaah, I got A+ for all classes in this term.

User3 : San Francisco is cold, isn't it?

User4 : I was jogging 5km in the morning.

우선, NLP에서 가장 대표적으로 하는 Preprocessing에는 Tokenization이다. 단어별로 나누는 것이다. 그러고 난 후, 한번 이것을 Naive Bayes를 적용시켜서 Positive? Negative?를 예측해보자. 그렇게 하기 위해서 위의 Twitt을 아래와 같이 고쳐볼 것이다.

자, 직관적으로 생각해봤을 때, 위의 data를 NB에 집어 넣으면 결과가 나올까? 나온다. 당연히 나온다. 뭐 딱히 안될 것은 없다. 저 data와 각 User에 대한 positive negative값만 같이 넣어주면 Naive Bayes model 만드는데는 문제가 없다. 그런데!! 위의 데이터는 정말 여러 면에서 잘못됐다.

우선 너무 크고 sparse하다. 너무 0이 많다. 위에서 짧은 4개의 Twitt으로도 저렇게 큰 matrix가 나오는데 실제로 Twitter에서 받아 처리하는 데이터로 위의 작업을 하면? 어마어마한 크기가 나오고 prediction은 느리게 되겠지. 자!! feature 사이즈를 줄여보자 (NLP에서 각각의 단어를 통해 예측을 하므로 각각의 단어를 feature라고 한다.)

이게 가장 큰 문제점이다. 그럼 이걸 어떻게 줄일까? 음 직관적으로 풀수 있는 것부터 풀어보자. 

1. 우선 i와 I는 같으니까 이걸 해결하기 위해 모든 문자를 소문자로 바꿔주자.

2. ? ! , 등등은 없어도 되니까 지워주자.

.은 경우에 따라서 유용하게 쓰일 수 있다고 하나 이번에는 그냥 과감히 지워줘버리자.

3. 여기서 data를 조금 normalization 해줄 필요가 있다. 무슨 말이냐? 예를 들어, class와 classes는 결국 의미는 같은 것이다. 두 개의 다른 feature로 존재할 필요가 없다. 그리고 was is are 등도 그냥 be동사이기 때문에 be로 바꿔주면 좋다. NLP에서 이것을 Stemming이라고 한다. 단어들의 뿌리를 찾는 것이다. (비슷한 개념으로 Lemmatization 이라고도 한다. 다른 개념이나 설명은 생략하도록 하자.)

4. 자 여기서 또 비슷한 개념을 적용시켜서 feature 수를 줄여보자. POS Tag이다. POS는 Part of Speech의 약자이다. 가령, In은 전치사, have 는 동사, car는 명사 이런 식으로 Speech의 일부분이라는 것이다. 지금까지 남아있는 단어들에 대하여 POS Tag를 적용하면 각 단어가 특정 POS Tag를 가지게 된다.

우리는 딱히 쓸모 없는 POS Tag들은 빼버리려고 한다. 예를 들어 전치사나 a the등은 positive negative 구분을 하는데는 별로 필요가 없지 않을까? 

이제 feature크기가 많이 줄어들었다. 이것을 기반으로 word count table을 만들어서 Nave Bayes에 넣어서 Positive Negative를 예측하면 된다. 물론 Model 빌드할 때 positive negative를 같이 넣어줘야 model이 뭘 배우든 말든 하겠지. (여기서 계속 NB를 얘기하는데 물론 SVM, Logistic Regression등등 여러가지를 시도해봐도 좋다)

대략 이런식으로 text classification을 구현한다. 이는 매우 단편적인 예일 뿐이다. 실제로 Word2Vec같은 전혀 다른 것들도 쓰이기도 하는데 그것은 나중에 자세히 포스팅할 것이다. (내가 NLP부분은 사실 별로 그렇게 좋아하는 분야는 아니라 포스팅이 건성건성일 수 있으나 Word2Vec만큼은 잘 해놓을 것이다.)

아무튼 이번 포스팅은 누군가 text classification을 해야 하는데 도무지 어떻게 해야되는지 감이 오지 않는 사람을 위한 포스팅으로 보면 된다.

드디어 마지막이다. DBSCAN Clustering이다. 이것도 굉장히 간단한 clustering이므로 이번 포스팅도 그리 길지는 않을 것 같다. DBSCAN은 epsilon과 data 개수로 clustering을 한다.

위의 그림이 DBSCAN에서의 가장 기본적인 element이다. 저것을 parameter라고도 한다. 저것을 가지고 각각의 data에 대해서 density reachable/density connected/not reachable 을 판단한다.

하나의 Cluster는 모든 data가 서로 density connected한 것들인 묶음이다. 아래의 data를 통해 clustering을 해보자.

위의 data는 epsilon 1.72cm에 number of data는 4로 놓은 것이다. 이해를 위해서 p1, p2, p3, p4를 각각 다른 색으로 표시를 해놨다. 각 색깔의 data를 중심으로 epsilon길이의 반지름으로 원을 그려보면 그 원 안에는 적어도 4개 이상의 data가 들어가 있는 것을 알 수 있다. p1과 p2는 density reachable, p2와 p3도 density reachable, p3와 p4도 density reachable. 따라서 p1과 p4는 density connected이다.

자 이런식으로 구분을 하면 많은 data들을 통해 DBSCAN을 돌렸을 때는 결과가 어떤 식으로 나누어질까? 그렇다. sparse한 영역의 기준으로 나누어진다. 데이터가 별로 없는 부분을 기준으로 나누어진다는 말이다.

출처 : https://en.wikipedia.org/wiki/DBSCAN

후 그래도 몇 일 동안 계속 포스팅하면서 다행히 하고자 한 포스팅들은 다 끝냈다. 이번 학기 때 배운 것들이다.(semantic web은 포스팅 안할래) 힘들고 힘든 한 학기였지만 보람있었고 재밌었다. 다음 학기가 배우는 학기로는 마지막 학기인데, 딱 두달 뒤에 다시 컴백해서 포스팅하려고 한다. (음 중간중간에 보안쪽 관련된, 탐지규칙 관련된 포스팅이 올라올 수도 있다.)