[자연어]N-gram

Rule-based approach 문제점

1. Hard to scale-up

2. Brittle(깨지기 쉬움)

3. Ambiguity

 

 

Tagged Corpus 종류

Ø 품사(Part-of-Speech)가 tag된 corpus

Ø Tree tagged corpus ( Penn Treebank)

Ø Semantic code(feature) tagged corpus

Ø Discourse structure tagged corpus

Ø Parallel corpus for MT ( 한-영의 parallel corpus를 뜻함)

 

 

N-gram 사용 영역

Ø Speech recognition - 음성인식

Ø OCR & Handwriting recognition 

Ø Machine translation - 기계번역

Ø Generation - 문장생성

Ø Context sensitive spelling correction - 스펠링 오류 체크

Ø Predictive text input system - 문장 자동 완성 기능

 

 

Language Modeling

 아래의 확률 수식내용을 language modeling 이라고함 

P(w1, w2, w3, w4) = P(w4 | w1, w2, w3 )

** P( Wn | W1, W2, ...Wn-1)

 

 

How to comput this joint probability?

--> Chain rule 사용

chain rule of probability

--> P(A,B,C,D) = P(A)P(B|A)P(C|A,B)P(D|A,B,C)

 

단점, 문장이 길면 길 수록 count하기가 어렵고 rare하게 나올경우가 더 많음

--> 해결책 = Markov Assumption

 

Marcov Assumption:

바로 다음에 나타날 단어는 이전에 나타난 단어에만 dependent하다는 가정

이전 수식은 Marcov 가정의 적용하면 아래와 같은 수식으로 근사시킬 수 있고, 

여기서 N=2일 때는 아래와 같음 (Bigram version)

N=3이면

Wn-2 ~ Wn-1까지 보는 것이므로, 앞의 두 단어까지 보자는 의미임

Unigram은 이전것 어느것도 보지않는 것

 

Ø Unigram: P(phone)

Ø Bigram: P(phone | cell)

 

  

Ø Trigram: P(phone | your cell)

 

참고로, 문장의 시작일때는 <s>를, 끝일 때는 </s>를 넣어 시작과 끝을 알림

 

 

Maximum LIkelihood Estimates를 사용함

--> 어떤 특정 training set에서 general하게 계산 된 값

--> 단, 특정 training set에 종속되어있긴 함.

 

Bigram counts & Unigram counts 테이블로 Bigram 확률테이블을 만들어서

MLE기반 sentence 확률을 계산 함

 

 

Shannon Visualization Method

임의의 문장을 생성해보기로 하자.

시작기호인 <s>뒤에 가장 많이 나오는 확률을 순서대로 생각해보자.

 

 

N-gram의 단점

1. 예측할 corpus가 training corpus와 유사할 때만 잘 학습이 됨

2. sparse한 테이블 구성으로 저장공간낭비 (Zipf's law)

--> 해결책: 0으로 구성된 값들에 대해 likelihood 값을 추정해보자

--> Smoothing(ELE Expected likelihood estimation)

ELE: Expected Likelihood Estimation

3. 긴문장에서는 예측 성능이 좋지 않음

 - Syntactic dependencies

    Ø “The man next to the large oak tree near the grocery store on the corner is tall.”

    Ø “The men next to the large oak tree near the grocery store on the corner are tall.”

 - Semantic dependencies

    Ø “The bird next to the large oak tree near the grocery store on the corner flies rapidly.”

    Ø “The man next to the large oak tree near the grocery store on the corner talks rapidly.”

--> 해결책 attention!

 

Laplace smoothing:

A.k.a add-one smothing

즉, 그냥 1을 더해주는 것

N은 전체 단어수, V는 그 중, unique한 단어 수

위의 식과 같은 식임

위의 확률값은 Ci > 0이면, 항상 C*i <= Ci 임

 

일반적으로 실험해 본 결과, Laplace기법은 너무 실제값의 카운트와 많이 차이가 난다는 단점이 있다.

--> 해결책: Add-k

--> 1보다 더 작은 k값으로 더해주자.

--> Bayesian Prior Smoothing

 

 

Bayesian Prior Smoothing

분모의 1은 P(Wn)의 모든 합이 1이므로

 

 

Language model에서 주의해야할 점

계속 곱셈으로 진행이 되므로(underflow 발생),

log를 취한 값을 곱하고 최종적으로 exp값을 취해준다.

또한 위처럼 하면, 덧셈 연산으로 쉽게 계산할 수 있음(덧셈이 곱셈보다 빠르니)

 

 

N-gram model 평가하기

1. Extrinsic evalution

 - A로 test해보고, B로 test해봐서 더 좋은 것을 선택하는 평가방법

 - 하지만, 실험을 위해 너무 많인 시간낭비

2. Intrinsic evalution(=perplexity)

 - perplexity값을 계산해서 A와 B를 비교하는 것

 - 시간은 짧게 걸리나, 성능을 정확히 비교할수는 없다.

 

 

perplexity

 = 단어가 나타날 확률값/ 단어의 개수

perplexity의 chain rule과 bigrams

 

perplexity가 낮을 수록 좋은 모델임

 

예를 들어, 0~9까지 하나의 값을 예측하는 것을 한다고 하면

perplexity는 10이고 숫자가 커지면 커질 수록 perplexity는 높아짐

(아래 그림 참고)

 

 

Out Of Vocabulary(OOV)처리 방법

예를 들어, training시에 1번이하(또는 2번이하)나타나는 단어를 Unknown라고 

해당 unkonwn에 대해서 확률을 계산할 수 있게 training시키는 것임 

 

 

Advanced Smoothing

Ø Kneser-Ney smoothing: current best smoothing algorithm

Ø Good-Turing

Ø Interpolation

Ø Backoff

Ø Class-based(cluster) N-grams (단어를 clustering 한다음에 n-gram하는 것)

 

 

Backoff

: use trigram if you have it, otherwise bigram, otherwise unigram

 

Interpolation: 

trigram + bigram + unigram을 다 통합해서 쓰자

Lambda1 + Lambda2+ Lambda3 = 1

Lambda 값은 어떻게 정하는가?

Held-Out data(validation data)를 활용해서 parameter인 lambda를 계산