smoothing of NGRAM

smoothing(평탄화)

ngram으로 Language Model을 구축할때

데이터 부족으로 출현하지 않은 엔트리에 대해서

어떤 확률 값을 부여할지에 대한 것이 smoothing이다.

데이터가 출현하지 않았기 때문에

확률값은 0인데

0/100000 과 0/10은 다를수 있다.

따라서 분모가 되는 수에 대한 고려를 해야한다.

10만개에서 출현하지 않은 것과 10개에서 출현하지 않은 것은 경험적으로 다른 정보량임을 알수 있다.

10만개에서 출현하지 않았다는 것은 상대적을로 10개에서 출현하지 않은 것보다는 출현할 가능성이 희박하다는 정보를 갖고 있다고 볼수 있다.

    C  +  M*P

---------------

    N  +  M 

C/N은 측정된 데이터값이다. 

바이그램과 유니그램을 사용한다면 COUNT(다음 검색)/COUNT(다음) 으로 '다음'뒤에 '검색'이 올 확률을 계산할수 있다.

그러면 뒤에 오는 M과 P에 대해서 설명하면

이해를 쉽게 하기 위해서 M을 상당히 큰 값으로 설정한다면

편의상 N=100 C=10, M=100 , P=0.5

스무딩 전에는 10/100 = 0.1

10 + 100*p

-----------

100 + 100

= (10 + 100*0.5 )/200

= 60/200

= 0.3

이 된다.

그러면 N=100 C+ 10 , M=10, P=0.5

10 + 10*0.5

------------

100 + 10

= (10+10*0.5)/110

= 15/110

= 0.13636363636363636363636363636364

이 된다.

두개를 비교하면

case 1> N = 100, C = 10, M  = 100, P = 0.5 = 0.3

case 2> N = 100, C = 10,  M = 10, P = 0.5 = 0.13

두값에서 달라진 것은 M값이 100과 10으로 바뀌었고

확률값은 0.3과 0.13으로 나타났다.

스무딩을 하지 않았을때의 확률값  0.1과 비교하면

case2가 스무딩을 하지 않았을 때의 값과 유사하게 나왔음을 알수 있다.

즉 M값이 크게 된다는 것은 측정값의 가중치를 낮추겠다는 의미이고 M값을 작게 한다는 것은

측정값을 신뢰한다는 의미로 판단할수 있다.

P는 prior probability로 볼수 있는데

값이 없을때 어떤 값으로 수렴하는지로 사용하면 된다.

평균값이 만약 0.3이면 값이 없을때는 0.3으로 하겠다고 할때 P = 0.3을 부여하는 식으로 이해하면 된다.

---------------------------추가----------------------------

Good Turning

이 알고리즘을 이해하고 나면 다음과 같이 설명할수 있다.

우리가 코퍼스에서 unigram의 빈도를 구하면 

N1~부터 Nx까지의 빈도를 구할수 있는데

스무딩을 위해

N1을 N0으로 대체하고

N2을 N1으로 대체한다.

아래와 같이 세개의 문장이 있다고 할때

Sam i am

i am sam

i do not eat

i : 3

sam : 2

am  : 2

do : 1

not : 1

eat : 1

위 내용을 빈도의 빈도( frequency of frequency)로 표현하면

N1 : 3( do, not, eat )

N2 : 2( sam, am )

N3 : 1이 된다.( i )

물고기가

10 carp, 3perch, 2 whitefish, 1 trout, 1 salmon, 1 eel = 18 마리가 있다고 할때

빈도 0의 경우

P(unseen) = N1/N = 3/18이되고

발견되었던 (trout)의 경우는

P(trout)=(2/3) / 18 = 1/27이된다.

C* ={ (c+1)/Nc+1 } / Nc