JM4) Language Modeling with N-grams
Language Modeling with N-grams
이번 챕터에 대해서는, 다소 덜 복잡한 단어를 예측하는 방법에 대해 배울 것이다.
예를 들어 다음과 같은 문장을 살펴보자.
Please turn your homework ...
대부분의 사람들이 예측하길, 위와 같은 문장에서 따라오는 단어는 in이나 over라고 생각할 것이다. 하지만 refrigerator나 the가 올 것 같지는 않다. 이번 section에서는 이러한 추측을 형태화하고, 확률을 도입하여 다음 가능한 단어들을 예측하는 모델을 소개하고자 한다. 또한 이러한 모델은 전체 문장에 대해 확률을 도입하기도 한다. 예를 들어, 다음과 같은 두 문장을 생각해보자.
1) all of a sudden I notice three guys standing on the sidewalk
2) on guys all I of notice sidewalk three a sudden standing the
위와 같은 두 문장에서 1)번 문장이 보다 나타날 확률이 높다는 것을 알고 있을 것이다.
우리는 그렇다면 왜 다음에 오는 단어를 예측하거나 문장에 대해 확률을 부여해야하는가? 확률은 노이즈가 있거나 모호한 input에 대해 단어를 정의하는데 필수적이기 때문이다. 예를 들어 다음과 같은 오타가 있는 문장을 생각해보자.
"I have a gub"
이러한 문장은 다음과 같이 수정될 수 있다.
"I have a gun"
"I have a gub"
"I have a gull"
이 세 문장 중에서 확률적으로 가장 많이 나타나는 문장은 당연히 "I have a gun"일 것이다. 우리는 이러한 문장의 지식을 사용하는 것으로 이러한 오타 실수가 나는 것을 방지할 수 있을 것이다.
Spelling correction (철자 보정)에서 Their are two midterms in this class라는 문장을 살펴보면 Their를 There로 고쳐야 한다. There are라는 형태가 Their are보다 나타날 확률이 훨씬 높기 때문이다. 이러한 잘못된 형태의 문장은 spell check가 이러한 error를 발견하고 보정해줘야 한다.
단어의 서열에 확률을 매기는 것은 기계 번역에서도 매우 유용하다. 예를 들어 다음과 같은 문장을 생각해보자.
그는 리포터들에게 중요 요소를 설명하였다.
He to Reporters main content introduced
이러한 문장을 토대로 가능성있는 영어 번역은 다음과 같다.
1) he introduced reporters to the main contents of the statement
2) he briefed to reporters the main contents of the statement
3) he briefed reporters on the main contents of the statement
단어 서열의 확률적 모델은 briefed reporters on가 영어 문장에서 제일 있음직한 구라는 것을 알고 있다.
이렇듯, 단어 서열에 확률을 부여하는 것은 언어 통계학에 매우 중요한 일이다. 우리는 단어 서열에 확률을 부여하는 모델을 language model 혹은 LM이라고 부른다. 이번 chapter에서는 N-gram이라는, 단어의 서열과 문장에 확률을 부여하는 가장 간단한 모델을 소개하고자 한다. 하나의 N-gram은 N개의 단어 서열을 의미한다. 예를 들어서 please turn your homework에서 2-gram (bigram)은 "please turn", "turn your" 그리고 "your homework"로 구성되고, 3-gram은 "please turn your", "turn your homework"로 구성된다. 우리는 어떻게 주어진 전 단어들로부터 N-gram의 마지막 단어의 확률을 추측하는 N-gram model을 사용할지에 대해 배워볼 것이다.
N-Grams
주어진 history h에 대하여 단어 w의 확률 p(w|h)를 계산해보도록 하자. history h는 "its water is so transparent that"이고, 우리는 다음 단어 "the"가 나올 확률을 원하고자 한다.
$$P(\text{the}|\text{its water is so transparent that})$$
이러한 확률을 예측하는 방법은 바로 매우 큰 corpus로부터 상대적 빈도수를 세는 것이 있다. 즉,
$$P(\text{the}|\text{its water is so transparent that}) = $$
$$\frac{C(\text{its water is so transparent that the})}{C(\text{its water is so transparent that})}$$
을 계산하면 되는 일이다. web과 같은 충분히 큰 corpus에 대해서는 이러한 빈도수와 확률을 계산하는 것이 가능하지만 위험성이 따르기도 한다. 이러한 위험성은, 만약 이러한 문장이 corpus에서 나오지 않을 경우 나타나게 된다.
its water is so transparent that이라는 문장이 corpus에서 나타나지 않게 되면 확률의 분모가 0이 되므로 확률이 무한으로 수렴하게 된다. 즉 우리는 이러한 위험성을 알고 있어야 한다.
만약 위와 같은 방법을 사용한다고 했을 때, 확률의 chain rule을 이용하여 확률을 분해할 수 있다.
$$ P(X_1...X_n) = P(X_1)P(X_2|X_1)P(X_3|X_1^2)...P(X_n|X^{n-1}_1) = \prod^n_{k=1} P(X_k|X^{k-1}_1)$$
이를 단어로 chain rule를 적용하면 다음과 같은 식이 탄생한다.
$$ P(w^n_1) = P(w_1)P(w_2|w_1)P(w_3|w^2_1)...P(w_n|w^{n-1}_1) = \prod^n_{k=1}P(X_k|X^{k-1}_1)$$
이러한 확률은 우리가 근사를 하여 사용할 수 있다. 예를 들어 bigram 모델에서는,
$$P(\text{the}|\text{Walden Pond's water is so transparent that})$$
을, 다음과 같은 확률로 근사한다.
$$P(\text{the}|\text{that})$$
이는 우리가 다음과 같은 근사를 하고 있기 때문에 나타난 결과이다:
$$P(w_n|w^{n-1}_1) \approx P(w_n|w_{n-1}) $$
이는 현재 단어가 나타나기 전의 history가 전의 단어가 나타나는 것으로 근사하기 때문이다. 이렇듯 단어의 확률이 오직 전 단어에 대해서만 의존하는 추측 방법론을 Markov assumption이라고 부른다. Markov 모델은 과거의 history에 대해서 너무 먼 과거에 대해서는 보지 않은 채로 미래의 unit의 확률을 예측하는 것이다. 우리는 이러한 bigram을 trigram으로도 일반화시킬 수 있으며, 이것은 N-gram 방법론이 되는 것이다.
N-gram 근사법은 다음과 같이 된다:
$$P(w_n|w^{n-1}_1) \approx P(w_n|w^{n-1}_{n-N+1}) $$
개인의 단어에 대해서 bigram assumption은 다음과 같이 된다.
$$P(w^n_1) \approx \prod^n_{k=1} P(w_k|w_{k-1}) $$
그렇다면 우리는 어떻게 이러한 bigram과 N-gram 확률을 추측하는가? 확률을 추측하는 일반적인 방법론을 maximum likelihood estimation이나 MLE로 부른다. MLE는 corpus로 부터 빈도수를 얻어서 이러한 parameter를 예측한다.
$$P(w_n|w_{n-1}) = \frac{C(w_{n-1}w_n)}{\sum_w C(w_{n-1}w)} $$
이러한 equation은 다음과 같이 정리할 수 있다.
$$P(w_n|w_{n-1}) = \frac{C(w_{n-1}w_n)}{ C(w_{n-1}) } $$
아래의 그림은 이러한 equation의 예시이다.
MLE N-gram parameter 추측의 일반적인 case는 다음과 같다:
$$P(w_n|w^{n-1}_{n-N+1}) = \frac {C(w^{n-1}_{n-N+1} w_n)}{ C(w^{n-1}_{n-N+1}) } $$
다음 그림은 bigram probability를 구하는 과정의 그림이다.
예를 들어 다음과 같은 Bigram probability를 생각해보자:
$$P(\text{i}|\text{<s>}) = 0.25, P(\text{want}|\text{i}) = 0.33, P(\text{english}|\text{want}) = 0.0011 $$
$$P(\text{food}|\text{english}) = 0.5, P(\text{</s>}|\text{food}) = 0.68$$
그렇다면, i want english food라는 문장이 나타날 확률은 다음과 같다:
$$ P(\text{<s> i want english food </s>}) = P(i|\text{<s>})P(want|i)P(english|want)P(food|english)P(\text{</s>}|food) $$
$$ =.25 * .33 * .0011 * .5 * .68 = .000031 $$
즉 이러한 문장이 나타날 확률은 0.000031이 된다.
이러한 확률을 지속적으로 계속 곱하게 되면 결국 확률이 0으로 수렴하게 된다. 그래서 이러한 확률은 log probability로 사용하기도 한다.
$$ p_1 * p_2 * ... * p_m = exp(log p_1 + log p_2 + ... + log p_m) $$
Evaluating Language Models
언어 모델에서 performance를 평가하는 최고의 방법은 모델을 적용해보고 이러한 적용이 얼마나 향상되었나를 측정하는 것이다. 이러한 end-to-end 평가 방식을 extrinsic evaluation이라 부른다.
하지만, 공교롭게도 거대한 NLP system을 작동시키는 것의 비용은 매우 비싸다. 대신에, 언어 모델에서 향상 기대치를 빠르게 평가할 수 있는 지표들이 있다. intrinsic evaluation 지표는 어느 적용 분야와 독립적인 모델의 퀄리티를 측정한다.
이러한 언어 모델의 intrinsic evaluation을 위해서는 test set이 필요하다. 많은 통계학 모델에서처럼, N-gram model의 확률은 그것이 학습된 corpus로부터 오며, 이를 training set이라 부른다. 이러한 학습된 모델의 퀄리티를 측정하기 위한, training set에서 발견되지 않은 data의 set들을 test set이라 부른다.
우리의 평가 지표들은 test set 확률에 기반하고 있으며, 그것은 test 문장들이 training set에 있지 않도록 하는 것이 중요하다. 만약 우리가 특정 test 문장의 확률을 계산하려 한다고 생각하자. 만약 test 문장이 training corpus에 한 부분이라면, 우리는 그 문장이 test set에서 나타날 때, 인공적으로 높은 확률을 그 문장에 실수로 부여하게 되는 셈이다. 이러한 상황을 training on the test set이라 부른다. Training on the test set은 어떠한 편향성은 확률을 매우 높게 보이게 만드는 것을 말하며, perplexity에 있어 부정확성을 일으킨다.
Perplexity
우리는 언어 모델을 평가하는 지표로써 raw probability를 이용하지 않고 perplexity를 이용한다. (종종 PP라고도 부름). test set에서의 언어 모델의 perplexity는 test set의 inverse probability이며, 단어의 숫자로 normalized되어 있다:
For a test set $W = w_1w_2...w_N$:
$$PP(W) = P(w_1w_2...w_N)^{-\frac{1}{N}}$$
$$=\sqrt[N]{\frac{1}{P(w_1w_2...w_N)}} $$
이 때, W의 확률을 확장하기 위한 chain rule을 사용하면,
$$PP(W) = \sqrt[N]{\prod^N_{i=1}\frac{1}{P(w_i|w_1...w_{i-1})}} $$
이러한 chain rule이 bigram이 적용될 경우,
$$PP(W) = \sqrt[N]{\prod^N_{i=1}\frac{1}{P(w_i|w_{i-1})}} $$
inverse probability에 의해 조건부 확률 값이 높을 수록 perplexity 값이 낮아진다는 것을 상기해라. 즉, perplexity를 최소화 시키는 것이 언어학 모델에 따른 test set 확률을 최대화 시키는 것과 같은 셈이다.
perplexity에 대해 다른 관점으로 생각하는 것은 바로 weighted average branching factor이다. 언어의 branching factor는 어느 단어 후에 따라올 수 있는 가능한 다음 단어의 수이다.
다른 N-gram model을 비교할 때 어떻게 perplexity가 사용될 수 있는지에 대해 예시를 보자. 우리는 unigram, bigram 그리고 trigram grammar를 3800만 개의 단어에 적용하였다. 그 후 1500만개 단어의 test set을 각각의 model에 적용하였다.
위에서 볼 수 있듯이, N-gram은 단어 서열에 대해 더 많은 정보를 주면, 더 낮은 perplexity를 기록한다.
Generalization and Zeros
많은 통계학적 모델과 같은 N-gram model은 training corpus에 의존한다. 이것의 의미는 확률이 주어진 training corpus에 대한 특정 사실들을 압축한다는 것이다. 또 다른 의미로는 N-gram이 우리가 N의 값을 증가 시킬 때마다 training corpus 모델링에서 더 좋은 결과를 낸다는 것이다.
우리는 다른 N-gram model로부터 무작위 문장을 생성하는 Shannon과 Miller and Selfridge의 논문 기술을 토대로 이러한 사실들을 가시화했다.
그림을 확인하면, 모델을 학습시킨 context가 길수록, 문장이 보다 일관된 내용을 갖고 있는 것으로 보였다. unigram 문장은 단어나 문장 종결 구두점 사이에 일관된 관계가 없었지만, bigram 문장 같은 경우 보다 더 단어들 사이의 일관성이 보이는 것으로 확인되었다. tri-gram이나 4-gram 문장부터는 보다 더 Shakespeare와 같은 느낌이 나왔다.
training set에서의 문법 의존성을 얻기 위하여, 완전히 다른 corpus 상에서 학습된 N-gram 문법을 보자: Shakespeare와 The Wall Street Journal은 모두 영어이고, 우리는 두 장르의 corpus사이에서 우리의 N-gram사이에 약간의 공통점이 있을 것이라 기대한다.
이들은 영어와 같은 문장을 모델링하는 것으로 보이지만, 가능한 문장사이에는 공통점이 없으며 작은 구에서조차 거의 겹치지 않는 부분이 대부분이다. 이와 같은 뚜렷한 차이점은 Training set와 Test Set가 Shakespeare와 Wall Street Journal만큼 다른 경우 통계 모델이 예측 변수로 쓸모없게 될 가능성이 매우 높다는 것이다.
어떻게 우리는 이러한 문제를 N-gram model을 만들 때 해결할 수 있는가? 하나의 방법은 우리가 이루고자 하는 임무에 유사한 장르를 가지는 training corpus를 사용하는 것이다. 적법한 문서를 번역하기 위한 언어 모델링을 하기 위해서는, 우리는 적법한 문서의 training corpus를 요한다. QA system을 위한 언어 모델을 만들 대에도, 우리는 질문들의 training corpus를 요한다.
장르를 맞추는 것으로는 아직 충분하지 않다. 우리의 모델은 아직 희소성에 대한 문제가 있다. N-gram이 만약 충분한 빈도수를 갖고 나타난다면 문제가 없이 그 N-gram에 대한 확률을 잘 예측할 것이지만, 만약 corpus가 한계가 있다면 몇몇 완벽하게 수용 가능한 영어 단어 서열이 corpus로부터 빠져있을 수 있다. 이러한 것을 확률 0 N-gram이라 부르지만, 실제로는 0의 확률을 가져서는 안된다. 예를 들어 WSJ corpus에서 다음과 같은 bigram이 나타났다고 하자:
denied the allegations : 5
denied the speculation: 2
denied the rumors: 1
denied the report: 1
하지만 만약 test set이 다음과 같은 구를 갖는다 해보자:
denied the offer
denied the load
이 때, 우리의 모델에서 P(offer|denied the)는 0이 될 것이다.
이러한 0값들은 training set에서는 나타나지 않는 data가 test set에서 나타날 때 발생한다. 이러한 것의 존재는 우리가 이 데이터를 이용하여 적용하고 싶은 문야의 퍼포먼스를 해칠수 있는, 단어 서열의 확률이 부정확하게 예측된다는 것을 의미한다.
두 번째, 만약 이러한 단어의 확률이 test set에서 0이 되면, 전체 확률은 0이 된다. 정의에 의해 perplexity는 test set의 inverse 확률에 기반한다고 위에서 배웠다. 그러므로 몇몇 단어가 확률 0을 가지면 우리는 perplexity를 구할 수 없다.
Unknown Words
그렇다면 이러한 training set에서는 보이지 않은 단어들을 처리하는 방법에는 무엇이 있을까?
예시로, closed vocabulary system에서는 test set이 오직 이 사전으로부터만 단어를 포함할 수 있고 알려지지 않은 단어는 없다. 이는 speech recognition이나 machine trainslation과 같은 몇몇 domain에서 납득 가능한 추측이고, 우리는 사전에 고정된 발음 사전이나 구에 관한 표를 가지고 있고, 언어 모델이 오직 이 사전이나 구 표에 대한 단어만 사용할 수 있다고 생각하는 것이다.
다른 케이스로, 우리는 우리가 전에 보지 못한 단어들을 다뤄야만 한다. 우리는 이것들을 unknown word라 부르거나 out of vocabulary (OOV)단어라 부른다. test set에서 나타나는 OOV 단어의 백분율을 OOV rate라 부른다. Open vocabulary system에서는 우리가 이러한 가능성있는 unknown 단어들을 pseudo-word <UNK>를 붙이는 것으로 처리한다.
그곳에는 <UNK>의 확률을 학습하는 두 가지의 방법이 있다. 첫 번째는 사전에 고정된 사전을 선택하는 것으로 close vocabulary로 문제점을 돌리는 것이다.
1. 사전에 고정된 사전 (word list)을 선택한다.
2. 텍스트 정규화 작업 단계에서 training set에 없는 단어를 unknown word token <UNK>로 변환한다.
3. 훈련 세트의 다른 일반 단어처럼 그 카운트에 대해 <UNK>에 대한 확률을 추정한다.
우리가 사전에 사전을 가지고 있는 상황에서의 두 번째 대안은, 암묵적으로 사전을 만드는 것으로 training data의 단어를 그들의 빈도수에 기반하여 <UNK>로 치환하는 것이다. 예를 들어 우리는 <UNK>로 training set에서 n번 보다 적게 나타나는 모든 단어들을 치환할 수 있다. 혹은 상위 V단어들을 제외하고 나머지들은 UNK로 치부할 수도 있다.
Smoothing
위에 있는 방법말고도 unknown words에 대하여 확률 0을 만들지 않게 하기 위한 방법이 존재한다. 발견되지 않았던 사건들에 확률 0을 대입하는 것이 아니라 보다 빈도수가 높은 사건들로부터 매우 작은 확률을 깎아내려 그것을 발견되지 않은 사건들에게 나눠주는 것이다. 이러한 수정 방법은 smoothing 혹은 discounting 기법이라 부른다.
Laplace Smoothing
Count에 1을 더해주는 방식이다.
예를 들어 단어의 count가 0이었던 단어들은 count가 1로 되고, 1이었던 단어들은 2가 되고, ... 이러한 형식으로 변환되는 알고리즘을 Laplace smoothing이라고 하며, add-1 smoothing이라고도 부른다. 예를 들어 unsmooth된 maximum likelihood estimate는 다음과 같았다.
단어 $w_i$에 대하여 unigram probability의 unsmooth된 maximum likelihood estimate는 그것의 빈도수 $c_i$를 word token N의 전체 숫자로 정규화한것과 같다:
$$P(w_i) = \frac{c_i}{N}$$
Laplace smoothing은 각각의 count에다가 1을 전부 더하는 것이다. 즉 분모에는 $|V|$만큼이 커지고, 분자에는 1만큼 커지게 되는 것이다.
$$P_{\text{Laplace}}(w_i)=\frac{c_i+1}{N+V}$$
이것을 adjusted count c*로 표시하면 다음과 같다:
$$c^*_i=(c_i+1)\frac{N}{N+V}$$
$$P_{\text{Laplace}}(w_i) = \frac{c^*_i}{N} $$
smoothing을 바라보는 방법으로는 discount term을 보는 것이 있다. 이것은 original count와 discount의 비율을 의미한다.
$$d_c = \frac{c^*}{c}$$
이 Laplace smoothing 방법을 bigram count에 적용시켜보도록 하자.
$$P^*_{\text{Laplace}}(w_n|w_{n-1}) = \frac{C(w_{n-1}w_n)+1}{C(w_{n-1})+V} $$
Add-k smoothing
Count에 k를 더해주는 방식이다.
$$P^*_{\text{Add-k}}(w_n|w_{n-1}) = \frac{C(w_{n-1}w_n)+k}{C(w_{n-1})+kV} $$
Backoff and Interpolation
Backoff
Backoff는 증거의 충분성에 따라 계층적 구조에 의하여 N-gram의 N을 한 단계씩 낮추는 것이다.
예를 들어 trigram을 사용한다고 할 때, trigram에서의 해당하는 단어가 불충분하면, bigram을 사용하고, bigram에서의 해당하는 단어가 불충분하면 unigram을 사용하는 방식으로 계층적 구조를 가지고 N-gram기법을 사용하는 것을 말한다.
Interpolation
특정 weight값을 주어서 trigram, bigram, unigram과 같은 count들을 combine시키는 것을 의미한다. 예를 들어 다음과 같은 예시가 있다:
$$\hat{P}(w_n|w_{n-2}w_{n-1}) = \lambda_1P(w_n|w_{n-2}w_{n-1}) +\lambda_2P(w_n|w_{n-1}) + \lambda_3P(w_n) $$
$$ \sum_i \lambda_i = 1 $$
그렇다면 이러한 $\lambda$값을 어떻게 설정하는가? 간단한 interpolation부터 조건부 interpolation까지 모두 held-out corpus로부터 학습된다. held-out corpus는 이러한 $\lambda$ 값과 같은 hyperparameter를 세팅하기 위한 추가적 training corpus를 의미한다. 최적의 $\lambda$값을 찾는 데에는 다양한 방법이 있으나, 대표적인 방법은 EM algorithm을 사용하는 것으로 iterative learning algorithm을 통해 국소적 최적의 $\lambda$값을 찾는 것이다.
Katz Backoff
Katz Backoff는 Backoff와 Interpolation의 방법을 합친 방법이다.
$$P_{\text{BO}}(w_n|w^{n-1}_{n-N+1}) = \begin{cases} P^*(w_n|w^{n-1}_{n-N+1}), & \text{if } C(w^n_{n-N+1}) > 0 \\ \alpha(w^{n-1}_{n-N+1})P_{\text{BO}}(w_n|w^{n-1}_{n-N+2}), & \text{otherwise.} \end{cases} $$
Kneser-Ney Smoothing
N-gram smoothing 방법 중에서 최고로 효율이 좋고 널리 쓰이는 알고리즘은 interpolated Kneser-Ney 알고리즘이다.
Kneser-Ney는 absolute discounting이라 불리는 방법과 함께 그것의 root들을 가지고 있다. 빈도수가 많은 N-gram을 위한 빈도의 discounting이 관찰되지 않았던 N-gram을 분포하기 위한 smoothing algorithm의 약간의 확률 밀도를 저장하는데에 필수적이었다는 것을 상기하라.
Church and Gale이 고안한 아이디어를 사용해보자. 먼저, count가 4인 한 N-gram을 생각해보자. 우리는 몇몇의 합으로 이 빈도수를 discount하고자 한다. 그러나 우리는 얼마나 discount 해야하는가? Church와 Gale의 현명한 아이디어는 held-out corpus를 바라보는 것으로, training set에서 count가 4인 모든 이러한 bigram이 얼만큼의 빈도수를 갖고있는 것인지 바라보는것이다. 그들은 AP newswire의 2천 2백만의 단어로부터 bigram 문법을 계산했고, 그후 또 다른 2200만개의 bigram의 각각의 빈도 수를 구하였다. 평균적으로, 처음 2200만 개의 단어에서 4번 나타나는 bigram은 다음 2200만개의 단어에서 3.23번 나타났다.
아래의 그림은 Church와 Gale이 고안하여 count를 구한 그림이다.
즉 training set에서 4번 나타났던 bigram들은 heldout set에서 평균적으로 3.23번 나타났다는 이야기이다. 표를 잘보면 training set에서 0.75를 빼주면 heldout set에서 나타나는 bigram count와 비슷한 것을 볼 수 있다. 이 점을 이용하여 다음과 같은 식을 만들 수 있다:
$$P_{\text{AbsoluteDiscounting}}(w_i|w_{i-1}) = \frac{C(w_{i-1}w_i)-d}{\sum_vC(w_{i-1}v)} + \lambda(w_{i-1})P(w_i) $$
첫 번째 term은 discounted bigram이고, 두 번째 term은 weight $\lambda$와 함께있는 unigram을 뜻한다. 우리는 d value를 0.75를 맞추거나, count가 1일때는 0.5로 맞춘다.
Kneser-Ney discounting은 하위 unigram 분포를 조정하는 보다 복잡한 discounting 방법을 보완한다. 만약 이 문장에서 다음 단어가 뭐가 나올지 예측한다고 생각하자. 이 때 model은 interpolation bigram과 unigram model이다.
I can't see without my reading ____________________.
단어 glasses가 단어 Kong보다는 보다 더 있음직 하기 때문에 우리는 unigram 모델이 glasses를 선호하길 바란다. 하지만 사실 Kong이라는 단어는 매우 흔한데, 왜냐하면 Hong Kong이라는 단어 자체가 빈도수가 매우 높기 때문이다. 표준 unigram model에서는 Kong이라는 단어가 glasses보다 높은 확률을 가졌다. 우리는 Kong이 더 많은 빈도수를 가짐에도 Hong Kong이라는 구에서만 오직 빈도수가 높다는 직관을 가지고 싶다. 단어 glasses는 보다 더 넓은 분포를 가진다.
다른 말로, "w에 뭐가 들어갈만 하냐"는 질문에 P(w) 대신에, 우리는 "새로운 연장으로써 w가 얼만큼 있음직 하냐"를 답하는 $P_{\text{CONTINUATION}}$이라 불리는 unigram model을 생성할 것이다. 어떻게 우리는 새로운 연장으로 관찰되지 않았던 context에 대하여 단어 w를 바라보는 확률을 추측할 것인가? Kneser-Ney 직관은 단어 w가 나타난 다른 context들의 합에 기반하여 $P_{\text{CONTINUATION}}$을 추측하고, 그것은 bigram으로 이루어져있다.
$$P_{\text{CONTINUATION}}(w) \propto |\{v:C(vw) > 0\}| $$
이 횟수를 확률로 변환하게 위해, bigram type의 전체 수로 일반화시킨다:
$$P_{\text{CONTINUATION}}(w) = \frac{|\{v:C(vw)>0\}|}{|\{(u', w'):C(u'w')>0\}|} $$
위 공식은 전체 bigram word에 대하여 일반화를 시킨 것이고, 아래의 식은 w보다 앞에 있는 단어의 형태로 일반화를 시킨 내용이다.
$$P_{\text{CONTINUATION}}(w) = \frac{|\{v:C(vw)>0\}|}{\sum_{w'}|\{v:C(vw')>0\}|} $$
bigram에 대한 Interpolated Kneser-Ney smoothing의 최종 공식은 다음과 같다:
$$P_{KN}(w_i|w_{i-1}) = \frac{max(C(w_{i-1}w_i)-d, 0)}{C(w_{i-1})} + \lambda(w_{i-1})P_{\text{CONTINUATION}}(w_i) $$
그 $\lambda$값은 일반화 상수이며, 우리 discount한 확률 밀도를 분포하는데에 사용한다.
$$\lambda(w_{i-1}) = \frac{d}{\sum_vC(w_{i-1}v)}|{w:C(w_{i-1}w)>0}| $$
첫번째 term은 normalized discount이며, 두번째 term은 $w_{i-1}$을 따라올 수 있는 단어 유형의 갯수를 말한다.
General한 recursive 형태는 다음과 같다:
$$P_{KN}(w_i|w^{i-1}_{i-n+1}) = \frac{max(c_{KN}(w^i_{i-n+1})-d, 0)}{\sum_vc_{KN}(w^{i-1}_{i-n+1}v)} + \lambda(w^{i-1}_{i-n+1})P_{KN}(w_i|w^{i-1}_{i-n+2})$$
이 때 $c_{KN}$의 정의는 우리가 highest-order N-gram이 interpolated되어 있을 때, 우리가 빈도수를 세는 것으로 정의되며, lower-order N-gram일 때는 다음과 같다:
$$c_{KN}(\cdot)= \begin{cases} \text{count}(\cdot) && \text{for the highest order} \\ \text{continuationcount}(\cdot) && \text{for lower orders} \end{cases} $$
이 때 highest-order N-gram being interpolated라는 뜻은 만약 trigram, bigram 그리고 unigram을 interpolated할 때 trigram인 경우를 말하고, lower-order N-gram being interpolated는 bigram이나 unigram일 때를 말한다.
이 recursion의 종결에서, unigram은 uniform distribution과 함께 interpolated되며, parameter $\epsilon$은 empty string이다:
$$P_{KN}(w) = \frac{max(c_{KN}(w)-d, 0)}{\sum_{w'}c_{KN}(w')} + \lambda(\epsilon)\frac{1}{V} $$
만약 unknown 단어 <UNK>를 넣고 싶다면, 그저 count 0과 함께 식을 돌려보면, 그것의 확률은 lambda-weight uniform distribution $\frac{\lambda(\epsilon)}{V}$가 된다.
Stupid Backoff
Stupid Backoff 알고리즘은 언어 모델이 참 확률 분포로 만드는 시도를 포기한다. 그곳에는 higher-order 확률의 discounting 방법을 적용하지 않는다. 만약 higher-order N-gram이 zero count일 경우에, 우리는 간단히 고정된 weight을 통해 lower order N-gram으로 backoff한다. 이러한 알고리즘은 확률 분포를 제공하지 않는다.
$$S(w_i|w^{i-1}_{i-K+1}) = \begin{cases} \frac{\text{count}(w^i_{i-k+1})}{\text{count}(w^{i-1}_{i-k+1})} && \text{if count}(w^i_{i-k+1})>0 \\ \lambda S(w_i|w^{i-1}_{i-k+2}) && \text{otherwise} \end{cases} $$
Advanced: Perplexity's Relation to Entropy
우리는 test set에서 N-gram model을 평가하는 방법으로 perplexity를 소개하였다. 더 나은 N-gram model은 test data에 더 높은 확률을 부여하는 것이고, perplexity는 test set에서의 확률을 일반화시킨 버전이다. perplexity 측정은 실제로 cross-entropy라는 perplexity의 의문적인 특성을 설명하는 것의 정보-이론 컨셉으로부터 떠오른 것이다. Entropy는 정보의 측정이다. 우리가 예측하려는 무엇이든 간에, 분포해 있는 임의 변수 X에 대하여, 그리고 특정 확률 분포에서, 그것을 p(x)라 부르면 임의 변수 X에 대한 entropy는 다음과 같다:
$$H(X) = -\sum_{x\in\chi} p(x)\log_2p(x) $$
entropy를 생각하는 직관적인 방법은 최적의 coding 스키마에서 정포의 조각들이나 결정들을 encode하는데 최소 몇 개의 bit가 필요한지에 대한 것으로 생각할 수 있다.
예시를 생각해보자.
이러한 prior 확률이 존재한다고 가정해보자.
그럴 경우 정보학에서 Horse 1은 0으로 표현될 수 있으며, Horse 2는 10, Horse 3은 110, Horse 4는 1110, Horse 5는 111100, Horse 6은 111101, Horse 7은 111110, Horse 8은 111111을 대표하게 된다. 이 때 확률을 통해 평균 몇 비트면 표현이 가능한지 확인해보면,
1*(1/2) + 2*(1/4) + 3*(1/8) + 4*(1/16) + 4*6*(1/64) = 0.5 +0.5 + 0.375 + 0.25 + 0.375 = 2
즉 2 bit라는 것을 알 수 있다.
그렇다면 Entropy의 식을 구해보면,
$$ H(X) = - \sum^{8}_{i=1} p(i)logp(i) = 2 bits $$ 라는 것을 알 수 있다.
우리는 Entropy를 통해 Entropy rate라는 것을 정의한다. (per-word entropy)
$$ \frac{1}{n}H(W^n_1) = -\frac{1}{n}\sum_{W^n_1\in L} p(W^n_1)\log p(W^n_1) $$
하지만 언어의 참 엔트로피를 구하기 위해선, 우리는 무한한 길이의 서열을 고려해야만 한다. 우리가 언어를 단어 서열을 생성하는 확률론적 방법 L로써 고려한다면, W가 단어 서열 $w_1, ... , w_n$을 대표한다할때, L의 Entropy rate H(L)은 다음과 같다:
$$ H(L) = -\lim_{n\to\infty} \frac{1}{n}H(w_1,w_2,...,w_n) $$
$$ = -\lim_{n\to\infty} \frac{1}{n} \sum_{W\in L} p(w_1,...,w_n)\log p(w_1, ..., w_n) $$
만약 언어가 정규적 성격이 있다면, 즉 정적이고 에르고딕성 성직이 있다면, Shannon-McMillan-Breiman 이론에 의해 다음과 같이 서술될 수 있다:
$$ H(L) = \lim_{n\to\infty} -\frac{1}{n}\log p(w_1w_2...w_n) $$
확률적 process가 stationary (정적인)이라는 뜻은 확률적 프로세스가 서열에 할당할 확률이 시간 흐름의 변화에 대해 불변이라는 뜻이다. 다른 말로, time t에 대한 단어 확률 분포가 time t+1에서도 확률 분포가 같다는 뜻이다. Markov model, 즉 N-gram은 정적이다. 예를 들어 bigram에서, $P_i$은 오직 $P_{i-1}$에 대하여만 의존한다. 그래서 만약 x에 대하여 시간 index를 이동할 경우, $P_{i+x}$는 아직 $P_{i+x-1}$에 대하여만 의존한다. 그러나 자연어는 정적이지가 않아서, 다가오는 단어들의 확률은, 임의로 멀거나 시간에 의존하는 사건들에 의존한다. 그러므로 우리의 통계학적 모델은 오직 자연어의 엔트로프와 옳은 분포를 향한 근사만을 제공한다.
요약하자면, 조금은 옳지 못한 에러를 만들지만 편하고 간단한 추측을 만드는 것으로 우리는 그것의 매우 긴 sample output을 취할 수 있고, 그것의 평균 로그 확률을 구하는 확률론적 프로세스의 엔트로피를 계산할 수 있는 것이다.
이제 우리는 cross-entropy를 소개할 준비가 되었다. cross-entropy는 우리가 생성된 data에 대하여 실제 확률 분포 p를 모를 때 유용하다.
$$ H(p, m) = \lim_{n\to\infty} - \frac{1}{n}\sum_{W\in L} p(w_1, ..., w_n) \log m(w_1, ..., w_n) $$
이것은 확률 분포 p를 서열이 따르게 하지만, m에 따른 확률 log를 합친다.
다시, Shannon-McMillan-Breiman 이론에 의해 정적 에르고딕 상태는 다음과 같다:
$$H(p, m) = \lim_{n\to\infty} -\frac{1}{n}\log m(w_1,w_2, ... ,w_n) $$
이것에 대한 의미는, entropy에 대하여 우리는 전체 가능한 서열을 더하는 것 대신에 충분히 긴 개인 서열을 취함으로써, 확률 분포 p에서의 model p의 cross-entropy를 추측할 수 있다.
무엇이 cross-entropy를 유용하게 하냐면, cross-entropy H(p, m)은 entropy H(p)의 상한선이다:
$$H(p) \leq H(p,m) $$
이것은 우리가 확률 p에 따른 기호의 서열들의 참 엔트로피를 추측하는데에 도와주는 간단화된 model m을 사용할 수 있다는 것을 의미한다. model m이 더 정확할 수록, H(p,m)이 보다 더 참 엔트로피인 H(p)와 가까워진다. 그러므로, H(p,m)과 H(p)의 차이점은 어떻게 모델이 정확하냐는 것에 대한 측정이다. 두 개의 모델 $m_1$과 $m_2$ 사이에, 더 정확한 모델은 더 낮은 cross-entropy를 갖게 된다.
우리는 마지막으로 perplexity와 cross-entropy간 관계를 볼 수 있게 된다. Cross-entropy는 limit에서 정의되며, 관찰된 단어 서열의 길이가 무한으로 갈 때 정의된다. 우리는 cross-entropy에 대한 근사가 필요한데, 이는 고정된 길이의 서열에 의존한다. 이러한 근사는 단어 W의 서열에 존재하는 model $M = P(w_i|w_{i-M+1}...w_{i-1})$에 대하여 다음과 같이 정의된다:
$$H(w) = -\frac{1}{N}\log P(w_1w_2...w_N) $$
단어 W의 서열에 존재하는 model P의 perplexity는 이제 형식적으로 cross-entropy의 expression 표기로써 정의된다:
$$ \text{Perplexity}(W) = 2^{H(w)} $$
$$ = P(w_1w_2...w_N)^{-\frac{1}{N}} $$
$$ = \sqrt[N]{\prod^N_{i=1} \frac{1}{P(w_i|w_1...w_{i-1})}} $$
이번 챕터에 대해서는, 다소 덜 복잡한 단어를 예측하는 방법에 대해 배울 것이다.
예를 들어 다음과 같은 문장을 살펴보자.
Please turn your homework ...
대부분의 사람들이 예측하길, 위와 같은 문장에서 따라오는 단어는 in이나 over라고 생각할 것이다. 하지만 refrigerator나 the가 올 것 같지는 않다. 이번 section에서는 이러한 추측을 형태화하고, 확률을 도입하여 다음 가능한 단어들을 예측하는 모델을 소개하고자 한다. 또한 이러한 모델은 전체 문장에 대해 확률을 도입하기도 한다. 예를 들어, 다음과 같은 두 문장을 생각해보자.
1) all of a sudden I notice three guys standing on the sidewalk
2) on guys all I of notice sidewalk three a sudden standing the
위와 같은 두 문장에서 1)번 문장이 보다 나타날 확률이 높다는 것을 알고 있을 것이다.
우리는 그렇다면 왜 다음에 오는 단어를 예측하거나 문장에 대해 확률을 부여해야하는가? 확률은 노이즈가 있거나 모호한 input에 대해 단어를 정의하는데 필수적이기 때문이다. 예를 들어 다음과 같은 오타가 있는 문장을 생각해보자.
"I have a gub"
이러한 문장은 다음과 같이 수정될 수 있다.
"I have a gun"
"I have a gub"
"I have a gull"
이 세 문장 중에서 확률적으로 가장 많이 나타나는 문장은 당연히 "I have a gun"일 것이다. 우리는 이러한 문장의 지식을 사용하는 것으로 이러한 오타 실수가 나는 것을 방지할 수 있을 것이다.
Spelling correction (철자 보정)에서 Their are two midterms in this class라는 문장을 살펴보면 Their를 There로 고쳐야 한다. There are라는 형태가 Their are보다 나타날 확률이 훨씬 높기 때문이다. 이러한 잘못된 형태의 문장은 spell check가 이러한 error를 발견하고 보정해줘야 한다.
단어의 서열에 확률을 매기는 것은 기계 번역에서도 매우 유용하다. 예를 들어 다음과 같은 문장을 생각해보자.
그는 리포터들에게 중요 요소를 설명하였다.
He to Reporters main content introduced
이러한 문장을 토대로 가능성있는 영어 번역은 다음과 같다.
1) he introduced reporters to the main contents of the statement
2) he briefed to reporters the main contents of the statement
3) he briefed reporters on the main contents of the statement
단어 서열의 확률적 모델은 briefed reporters on가 영어 문장에서 제일 있음직한 구라는 것을 알고 있다.
이렇듯, 단어 서열에 확률을 부여하는 것은 언어 통계학에 매우 중요한 일이다. 우리는 단어 서열에 확률을 부여하는 모델을 language model 혹은 LM이라고 부른다. 이번 chapter에서는 N-gram이라는, 단어의 서열과 문장에 확률을 부여하는 가장 간단한 모델을 소개하고자 한다. 하나의 N-gram은 N개의 단어 서열을 의미한다. 예를 들어서 please turn your homework에서 2-gram (bigram)은 "please turn", "turn your" 그리고 "your homework"로 구성되고, 3-gram은 "please turn your", "turn your homework"로 구성된다. 우리는 어떻게 주어진 전 단어들로부터 N-gram의 마지막 단어의 확률을 추측하는 N-gram model을 사용할지에 대해 배워볼 것이다.
N-Grams
주어진 history h에 대하여 단어 w의 확률 p(w|h)를 계산해보도록 하자. history h는 "its water is so transparent that"이고, 우리는 다음 단어 "the"가 나올 확률을 원하고자 한다.
$$P(\text{the}|\text{its water is so transparent that})$$
이러한 확률을 예측하는 방법은 바로 매우 큰 corpus로부터 상대적 빈도수를 세는 것이 있다. 즉,
$$P(\text{the}|\text{its water is so transparent that}) = $$
$$\frac{C(\text{its water is so transparent that the})}{C(\text{its water is so transparent that})}$$
을 계산하면 되는 일이다. web과 같은 충분히 큰 corpus에 대해서는 이러한 빈도수와 확률을 계산하는 것이 가능하지만 위험성이 따르기도 한다. 이러한 위험성은, 만약 이러한 문장이 corpus에서 나오지 않을 경우 나타나게 된다.
its water is so transparent that이라는 문장이 corpus에서 나타나지 않게 되면 확률의 분모가 0이 되므로 확률이 무한으로 수렴하게 된다. 즉 우리는 이러한 위험성을 알고 있어야 한다.
만약 위와 같은 방법을 사용한다고 했을 때, 확률의 chain rule을 이용하여 확률을 분해할 수 있다.
$$ P(X_1...X_n) = P(X_1)P(X_2|X_1)P(X_3|X_1^2)...P(X_n|X^{n-1}_1) = \prod^n_{k=1} P(X_k|X^{k-1}_1)$$
이를 단어로 chain rule를 적용하면 다음과 같은 식이 탄생한다.
$$ P(w^n_1) = P(w_1)P(w_2|w_1)P(w_3|w^2_1)...P(w_n|w^{n-1}_1) = \prod^n_{k=1}P(X_k|X^{k-1}_1)$$
이러한 확률은 우리가 근사를 하여 사용할 수 있다. 예를 들어 bigram 모델에서는,
$$P(\text{the}|\text{Walden Pond's water is so transparent that})$$
을, 다음과 같은 확률로 근사한다.
$$P(\text{the}|\text{that})$$
이는 우리가 다음과 같은 근사를 하고 있기 때문에 나타난 결과이다:
$$P(w_n|w^{n-1}_1) \approx P(w_n|w_{n-1}) $$
이는 현재 단어가 나타나기 전의 history가 전의 단어가 나타나는 것으로 근사하기 때문이다. 이렇듯 단어의 확률이 오직 전 단어에 대해서만 의존하는 추측 방법론을 Markov assumption이라고 부른다. Markov 모델은 과거의 history에 대해서 너무 먼 과거에 대해서는 보지 않은 채로 미래의 unit의 확률을 예측하는 것이다. 우리는 이러한 bigram을 trigram으로도 일반화시킬 수 있으며, 이것은 N-gram 방법론이 되는 것이다.
N-gram 근사법은 다음과 같이 된다:
$$P(w_n|w^{n-1}_1) \approx P(w_n|w^{n-1}_{n-N+1}) $$
개인의 단어에 대해서 bigram assumption은 다음과 같이 된다.
$$P(w^n_1) \approx \prod^n_{k=1} P(w_k|w_{k-1}) $$
그렇다면 우리는 어떻게 이러한 bigram과 N-gram 확률을 추측하는가? 확률을 추측하는 일반적인 방법론을 maximum likelihood estimation이나 MLE로 부른다. MLE는 corpus로 부터 빈도수를 얻어서 이러한 parameter를 예측한다.
$$P(w_n|w_{n-1}) = \frac{C(w_{n-1}w_n)}{\sum_w C(w_{n-1}w)} $$
이러한 equation은 다음과 같이 정리할 수 있다.
$$P(w_n|w_{n-1}) = \frac{C(w_{n-1}w_n)}{ C(w_{n-1}) } $$
아래의 그림은 이러한 equation의 예시이다.
MLE N-gram parameter 추측의 일반적인 case는 다음과 같다:
$$P(w_n|w^{n-1}_{n-N+1}) = \frac {C(w^{n-1}_{n-N+1} w_n)}{ C(w^{n-1}_{n-N+1}) } $$
다음 그림은 bigram probability를 구하는 과정의 그림이다.
예를 들어 다음과 같은 Bigram probability를 생각해보자:
$$P(\text{i}|\text{<s>}) = 0.25, P(\text{want}|\text{i}) = 0.33, P(\text{english}|\text{want}) = 0.0011 $$
$$P(\text{food}|\text{english}) = 0.5, P(\text{</s>}|\text{food}) = 0.68$$
그렇다면, i want english food라는 문장이 나타날 확률은 다음과 같다:
$$ P(\text{<s> i want english food </s>}) = P(i|\text{<s>})P(want|i)P(english|want)P(food|english)P(\text{</s>}|food) $$
$$ =.25 * .33 * .0011 * .5 * .68 = .000031 $$
즉 이러한 문장이 나타날 확률은 0.000031이 된다.
이러한 확률을 지속적으로 계속 곱하게 되면 결국 확률이 0으로 수렴하게 된다. 그래서 이러한 확률은 log probability로 사용하기도 한다.
$$ p_1 * p_2 * ... * p_m = exp(log p_1 + log p_2 + ... + log p_m) $$
Evaluating Language Models
언어 모델에서 performance를 평가하는 최고의 방법은 모델을 적용해보고 이러한 적용이 얼마나 향상되었나를 측정하는 것이다. 이러한 end-to-end 평가 방식을 extrinsic evaluation이라 부른다.
하지만, 공교롭게도 거대한 NLP system을 작동시키는 것의 비용은 매우 비싸다. 대신에, 언어 모델에서 향상 기대치를 빠르게 평가할 수 있는 지표들이 있다. intrinsic evaluation 지표는 어느 적용 분야와 독립적인 모델의 퀄리티를 측정한다.
이러한 언어 모델의 intrinsic evaluation을 위해서는 test set이 필요하다. 많은 통계학 모델에서처럼, N-gram model의 확률은 그것이 학습된 corpus로부터 오며, 이를 training set이라 부른다. 이러한 학습된 모델의 퀄리티를 측정하기 위한, training set에서 발견되지 않은 data의 set들을 test set이라 부른다.
우리의 평가 지표들은 test set 확률에 기반하고 있으며, 그것은 test 문장들이 training set에 있지 않도록 하는 것이 중요하다. 만약 우리가 특정 test 문장의 확률을 계산하려 한다고 생각하자. 만약 test 문장이 training corpus에 한 부분이라면, 우리는 그 문장이 test set에서 나타날 때, 인공적으로 높은 확률을 그 문장에 실수로 부여하게 되는 셈이다. 이러한 상황을 training on the test set이라 부른다. Training on the test set은 어떠한 편향성은 확률을 매우 높게 보이게 만드는 것을 말하며, perplexity에 있어 부정확성을 일으킨다.
Perplexity
우리는 언어 모델을 평가하는 지표로써 raw probability를 이용하지 않고 perplexity를 이용한다. (종종 PP라고도 부름). test set에서의 언어 모델의 perplexity는 test set의 inverse probability이며, 단어의 숫자로 normalized되어 있다:
For a test set $W = w_1w_2...w_N$:
$$PP(W) = P(w_1w_2...w_N)^{-\frac{1}{N}}$$
$$=\sqrt[N]{\frac{1}{P(w_1w_2...w_N)}} $$
이 때, W의 확률을 확장하기 위한 chain rule을 사용하면,
$$PP(W) = \sqrt[N]{\prod^N_{i=1}\frac{1}{P(w_i|w_1...w_{i-1})}} $$
이러한 chain rule이 bigram이 적용될 경우,
$$PP(W) = \sqrt[N]{\prod^N_{i=1}\frac{1}{P(w_i|w_{i-1})}} $$
inverse probability에 의해 조건부 확률 값이 높을 수록 perplexity 값이 낮아진다는 것을 상기해라. 즉, perplexity를 최소화 시키는 것이 언어학 모델에 따른 test set 확률을 최대화 시키는 것과 같은 셈이다.
perplexity에 대해 다른 관점으로 생각하는 것은 바로 weighted average branching factor이다. 언어의 branching factor는 어느 단어 후에 따라올 수 있는 가능한 다음 단어의 수이다.
다른 N-gram model을 비교할 때 어떻게 perplexity가 사용될 수 있는지에 대해 예시를 보자. 우리는 unigram, bigram 그리고 trigram grammar를 3800만 개의 단어에 적용하였다. 그 후 1500만개 단어의 test set을 각각의 model에 적용하였다.
Generalization and Zeros
우리는 다른 N-gram model로부터 무작위 문장을 생성하는 Shannon과 Miller and Selfridge의 논문 기술을 토대로 이러한 사실들을 가시화했다.
그림을 확인하면, 모델을 학습시킨 context가 길수록, 문장이 보다 일관된 내용을 갖고 있는 것으로 보였다. unigram 문장은 단어나 문장 종결 구두점 사이에 일관된 관계가 없었지만, bigram 문장 같은 경우 보다 더 단어들 사이의 일관성이 보이는 것으로 확인되었다. tri-gram이나 4-gram 문장부터는 보다 더 Shakespeare와 같은 느낌이 나왔다.
training set에서의 문법 의존성을 얻기 위하여, 완전히 다른 corpus 상에서 학습된 N-gram 문법을 보자: Shakespeare와 The Wall Street Journal은 모두 영어이고, 우리는 두 장르의 corpus사이에서 우리의 N-gram사이에 약간의 공통점이 있을 것이라 기대한다.
이들은 영어와 같은 문장을 모델링하는 것으로 보이지만, 가능한 문장사이에는 공통점이 없으며 작은 구에서조차 거의 겹치지 않는 부분이 대부분이다. 이와 같은 뚜렷한 차이점은 Training set와 Test Set가 Shakespeare와 Wall Street Journal만큼 다른 경우 통계 모델이 예측 변수로 쓸모없게 될 가능성이 매우 높다는 것이다.
어떻게 우리는 이러한 문제를 N-gram model을 만들 때 해결할 수 있는가? 하나의 방법은 우리가 이루고자 하는 임무에 유사한 장르를 가지는 training corpus를 사용하는 것이다. 적법한 문서를 번역하기 위한 언어 모델링을 하기 위해서는, 우리는 적법한 문서의 training corpus를 요한다. QA system을 위한 언어 모델을 만들 대에도, 우리는 질문들의 training corpus를 요한다.
장르를 맞추는 것으로는 아직 충분하지 않다. 우리의 모델은 아직 희소성에 대한 문제가 있다. N-gram이 만약 충분한 빈도수를 갖고 나타난다면 문제가 없이 그 N-gram에 대한 확률을 잘 예측할 것이지만, 만약 corpus가 한계가 있다면 몇몇 완벽하게 수용 가능한 영어 단어 서열이 corpus로부터 빠져있을 수 있다. 이러한 것을 확률 0 N-gram이라 부르지만, 실제로는 0의 확률을 가져서는 안된다. 예를 들어 WSJ corpus에서 다음과 같은 bigram이 나타났다고 하자:
denied the allegations : 5
denied the speculation: 2
denied the rumors: 1
denied the report: 1
하지만 만약 test set이 다음과 같은 구를 갖는다 해보자:
denied the offer
denied the load
이 때, 우리의 모델에서 P(offer|denied the)는 0이 될 것이다.
이러한 0값들은 training set에서는 나타나지 않는 data가 test set에서 나타날 때 발생한다. 이러한 것의 존재는 우리가 이 데이터를 이용하여 적용하고 싶은 문야의 퍼포먼스를 해칠수 있는, 단어 서열의 확률이 부정확하게 예측된다는 것을 의미한다.
두 번째, 만약 이러한 단어의 확률이 test set에서 0이 되면, 전체 확률은 0이 된다. 정의에 의해 perplexity는 test set의 inverse 확률에 기반한다고 위에서 배웠다. 그러므로 몇몇 단어가 확률 0을 가지면 우리는 perplexity를 구할 수 없다.
Unknown Words
그렇다면 이러한 training set에서는 보이지 않은 단어들을 처리하는 방법에는 무엇이 있을까?
예시로, closed vocabulary system에서는 test set이 오직 이 사전으로부터만 단어를 포함할 수 있고 알려지지 않은 단어는 없다. 이는 speech recognition이나 machine trainslation과 같은 몇몇 domain에서 납득 가능한 추측이고, 우리는 사전에 고정된 발음 사전이나 구에 관한 표를 가지고 있고, 언어 모델이 오직 이 사전이나 구 표에 대한 단어만 사용할 수 있다고 생각하는 것이다.
다른 케이스로, 우리는 우리가 전에 보지 못한 단어들을 다뤄야만 한다. 우리는 이것들을 unknown word라 부르거나 out of vocabulary (OOV)단어라 부른다. test set에서 나타나는 OOV 단어의 백분율을 OOV rate라 부른다. Open vocabulary system에서는 우리가 이러한 가능성있는 unknown 단어들을 pseudo-word <UNK>를 붙이는 것으로 처리한다.
그곳에는 <UNK>의 확률을 학습하는 두 가지의 방법이 있다. 첫 번째는 사전에 고정된 사전을 선택하는 것으로 close vocabulary로 문제점을 돌리는 것이다.
1. 사전에 고정된 사전 (word list)을 선택한다.
2. 텍스트 정규화 작업 단계에서 training set에 없는 단어를 unknown word token <UNK>로 변환한다.
3. 훈련 세트의 다른 일반 단어처럼 그 카운트에 대해 <UNK>에 대한 확률을 추정한다.
우리가 사전에 사전을 가지고 있는 상황에서의 두 번째 대안은, 암묵적으로 사전을 만드는 것으로 training data의 단어를 그들의 빈도수에 기반하여 <UNK>로 치환하는 것이다. 예를 들어 우리는 <UNK>로 training set에서 n번 보다 적게 나타나는 모든 단어들을 치환할 수 있다. 혹은 상위 V단어들을 제외하고 나머지들은 UNK로 치부할 수도 있다.
Smoothing
위에 있는 방법말고도 unknown words에 대하여 확률 0을 만들지 않게 하기 위한 방법이 존재한다. 발견되지 않았던 사건들에 확률 0을 대입하는 것이 아니라 보다 빈도수가 높은 사건들로부터 매우 작은 확률을 깎아내려 그것을 발견되지 않은 사건들에게 나눠주는 것이다. 이러한 수정 방법은 smoothing 혹은 discounting 기법이라 부른다.
Laplace Smoothing
Count에 1을 더해주는 방식이다.
예를 들어 단어의 count가 0이었던 단어들은 count가 1로 되고, 1이었던 단어들은 2가 되고, ... 이러한 형식으로 변환되는 알고리즘을 Laplace smoothing이라고 하며, add-1 smoothing이라고도 부른다. 예를 들어 unsmooth된 maximum likelihood estimate는 다음과 같았다.
단어 $w_i$에 대하여 unigram probability의 unsmooth된 maximum likelihood estimate는 그것의 빈도수 $c_i$를 word token N의 전체 숫자로 정규화한것과 같다:
$$P(w_i) = \frac{c_i}{N}$$
Laplace smoothing은 각각의 count에다가 1을 전부 더하는 것이다. 즉 분모에는 $|V|$만큼이 커지고, 분자에는 1만큼 커지게 되는 것이다.
$$P_{\text{Laplace}}(w_i)=\frac{c_i+1}{N+V}$$
이것을 adjusted count c*로 표시하면 다음과 같다:
$$c^*_i=(c_i+1)\frac{N}{N+V}$$
$$P_{\text{Laplace}}(w_i) = \frac{c^*_i}{N} $$
smoothing을 바라보는 방법으로는 discount term을 보는 것이 있다. 이것은 original count와 discount의 비율을 의미한다.
$$d_c = \frac{c^*}{c}$$
이 Laplace smoothing 방법을 bigram count에 적용시켜보도록 하자.
$$P^*_{\text{Laplace}}(w_n|w_{n-1}) = \frac{C(w_{n-1}w_n)+1}{C(w_{n-1})+V} $$
Add-k smoothing
Count에 k를 더해주는 방식이다.
$$P^*_{\text{Add-k}}(w_n|w_{n-1}) = \frac{C(w_{n-1}w_n)+k}{C(w_{n-1})+kV} $$
Backoff and Interpolation
Backoff
Backoff는 증거의 충분성에 따라 계층적 구조에 의하여 N-gram의 N을 한 단계씩 낮추는 것이다.
예를 들어 trigram을 사용한다고 할 때, trigram에서의 해당하는 단어가 불충분하면, bigram을 사용하고, bigram에서의 해당하는 단어가 불충분하면 unigram을 사용하는 방식으로 계층적 구조를 가지고 N-gram기법을 사용하는 것을 말한다.
Interpolation
특정 weight값을 주어서 trigram, bigram, unigram과 같은 count들을 combine시키는 것을 의미한다. 예를 들어 다음과 같은 예시가 있다:
$$\hat{P}(w_n|w_{n-2}w_{n-1}) = \lambda_1P(w_n|w_{n-2}w_{n-1}) +\lambda_2P(w_n|w_{n-1}) + \lambda_3P(w_n) $$
$$ \sum_i \lambda_i = 1 $$
그렇다면 이러한 $\lambda$값을 어떻게 설정하는가? 간단한 interpolation부터 조건부 interpolation까지 모두 held-out corpus로부터 학습된다. held-out corpus는 이러한 $\lambda$ 값과 같은 hyperparameter를 세팅하기 위한 추가적 training corpus를 의미한다. 최적의 $\lambda$값을 찾는 데에는 다양한 방법이 있으나, 대표적인 방법은 EM algorithm을 사용하는 것으로 iterative learning algorithm을 통해 국소적 최적의 $\lambda$값을 찾는 것이다.
Katz Backoff
Katz Backoff는 Backoff와 Interpolation의 방법을 합친 방법이다.
$$P_{\text{BO}}(w_n|w^{n-1}_{n-N+1}) = \begin{cases} P^*(w_n|w^{n-1}_{n-N+1}), & \text{if } C(w^n_{n-N+1}) > 0 \\ \alpha(w^{n-1}_{n-N+1})P_{\text{BO}}(w_n|w^{n-1}_{n-N+2}), & \text{otherwise.} \end{cases} $$
Kneser-Ney Smoothing
N-gram smoothing 방법 중에서 최고로 효율이 좋고 널리 쓰이는 알고리즘은 interpolated Kneser-Ney 알고리즘이다.
Kneser-Ney는 absolute discounting이라 불리는 방법과 함께 그것의 root들을 가지고 있다. 빈도수가 많은 N-gram을 위한 빈도의 discounting이 관찰되지 않았던 N-gram을 분포하기 위한 smoothing algorithm의 약간의 확률 밀도를 저장하는데에 필수적이었다는 것을 상기하라.
Church and Gale이 고안한 아이디어를 사용해보자. 먼저, count가 4인 한 N-gram을 생각해보자. 우리는 몇몇의 합으로 이 빈도수를 discount하고자 한다. 그러나 우리는 얼마나 discount 해야하는가? Church와 Gale의 현명한 아이디어는 held-out corpus를 바라보는 것으로, training set에서 count가 4인 모든 이러한 bigram이 얼만큼의 빈도수를 갖고있는 것인지 바라보는것이다. 그들은 AP newswire의 2천 2백만의 단어로부터 bigram 문법을 계산했고, 그후 또 다른 2200만개의 bigram의 각각의 빈도 수를 구하였다. 평균적으로, 처음 2200만 개의 단어에서 4번 나타나는 bigram은 다음 2200만개의 단어에서 3.23번 나타났다.
아래의 그림은 Church와 Gale이 고안하여 count를 구한 그림이다.
$$P_{\text{AbsoluteDiscounting}}(w_i|w_{i-1}) = \frac{C(w_{i-1}w_i)-d}{\sum_vC(w_{i-1}v)} + \lambda(w_{i-1})P(w_i) $$
첫 번째 term은 discounted bigram이고, 두 번째 term은 weight $\lambda$와 함께있는 unigram을 뜻한다. 우리는 d value를 0.75를 맞추거나, count가 1일때는 0.5로 맞춘다.
Kneser-Ney discounting은 하위 unigram 분포를 조정하는 보다 복잡한 discounting 방법을 보완한다. 만약 이 문장에서 다음 단어가 뭐가 나올지 예측한다고 생각하자. 이 때 model은 interpolation bigram과 unigram model이다.
I can't see without my reading ____________________.
단어 glasses가 단어 Kong보다는 보다 더 있음직 하기 때문에 우리는 unigram 모델이 glasses를 선호하길 바란다. 하지만 사실 Kong이라는 단어는 매우 흔한데, 왜냐하면 Hong Kong이라는 단어 자체가 빈도수가 매우 높기 때문이다. 표준 unigram model에서는 Kong이라는 단어가 glasses보다 높은 확률을 가졌다. 우리는 Kong이 더 많은 빈도수를 가짐에도 Hong Kong이라는 구에서만 오직 빈도수가 높다는 직관을 가지고 싶다. 단어 glasses는 보다 더 넓은 분포를 가진다.
다른 말로, "w에 뭐가 들어갈만 하냐"는 질문에 P(w) 대신에, 우리는 "새로운 연장으로써 w가 얼만큼 있음직 하냐"를 답하는 $P_{\text{CONTINUATION}}$이라 불리는 unigram model을 생성할 것이다. 어떻게 우리는 새로운 연장으로 관찰되지 않았던 context에 대하여 단어 w를 바라보는 확률을 추측할 것인가? Kneser-Ney 직관은 단어 w가 나타난 다른 context들의 합에 기반하여 $P_{\text{CONTINUATION}}$을 추측하고, 그것은 bigram으로 이루어져있다.
$$P_{\text{CONTINUATION}}(w) \propto |\{v:C(vw) > 0\}| $$
이 횟수를 확률로 변환하게 위해, bigram type의 전체 수로 일반화시킨다:
$$P_{\text{CONTINUATION}}(w) = \frac{|\{v:C(vw)>0\}|}{|\{(u', w'):C(u'w')>0\}|} $$
위 공식은 전체 bigram word에 대하여 일반화를 시킨 것이고, 아래의 식은 w보다 앞에 있는 단어의 형태로 일반화를 시킨 내용이다.
$$P_{\text{CONTINUATION}}(w) = \frac{|\{v:C(vw)>0\}|}{\sum_{w'}|\{v:C(vw')>0\}|} $$
bigram에 대한 Interpolated Kneser-Ney smoothing의 최종 공식은 다음과 같다:
$$P_{KN}(w_i|w_{i-1}) = \frac{max(C(w_{i-1}w_i)-d, 0)}{C(w_{i-1})} + \lambda(w_{i-1})P_{\text{CONTINUATION}}(w_i) $$
그 $\lambda$값은 일반화 상수이며, 우리 discount한 확률 밀도를 분포하는데에 사용한다.
$$\lambda(w_{i-1}) = \frac{d}{\sum_vC(w_{i-1}v)}|{w:C(w_{i-1}w)>0}| $$
첫번째 term은 normalized discount이며, 두번째 term은 $w_{i-1}$을 따라올 수 있는 단어 유형의 갯수를 말한다.
General한 recursive 형태는 다음과 같다:
$$P_{KN}(w_i|w^{i-1}_{i-n+1}) = \frac{max(c_{KN}(w^i_{i-n+1})-d, 0)}{\sum_vc_{KN}(w^{i-1}_{i-n+1}v)} + \lambda(w^{i-1}_{i-n+1})P_{KN}(w_i|w^{i-1}_{i-n+2})$$
이 때 $c_{KN}$의 정의는 우리가 highest-order N-gram이 interpolated되어 있을 때, 우리가 빈도수를 세는 것으로 정의되며, lower-order N-gram일 때는 다음과 같다:
$$c_{KN}(\cdot)= \begin{cases} \text{count}(\cdot) && \text{for the highest order} \\ \text{continuationcount}(\cdot) && \text{for lower orders} \end{cases} $$
이 때 highest-order N-gram being interpolated라는 뜻은 만약 trigram, bigram 그리고 unigram을 interpolated할 때 trigram인 경우를 말하고, lower-order N-gram being interpolated는 bigram이나 unigram일 때를 말한다.
이 recursion의 종결에서, unigram은 uniform distribution과 함께 interpolated되며, parameter $\epsilon$은 empty string이다:
$$P_{KN}(w) = \frac{max(c_{KN}(w)-d, 0)}{\sum_{w'}c_{KN}(w')} + \lambda(\epsilon)\frac{1}{V} $$
만약 unknown 단어 <UNK>를 넣고 싶다면, 그저 count 0과 함께 식을 돌려보면, 그것의 확률은 lambda-weight uniform distribution $\frac{\lambda(\epsilon)}{V}$가 된다.
Stupid Backoff
Stupid Backoff 알고리즘은 언어 모델이 참 확률 분포로 만드는 시도를 포기한다. 그곳에는 higher-order 확률의 discounting 방법을 적용하지 않는다. 만약 higher-order N-gram이 zero count일 경우에, 우리는 간단히 고정된 weight을 통해 lower order N-gram으로 backoff한다. 이러한 알고리즘은 확률 분포를 제공하지 않는다.
$$S(w_i|w^{i-1}_{i-K+1}) = \begin{cases} \frac{\text{count}(w^i_{i-k+1})}{\text{count}(w^{i-1}_{i-k+1})} && \text{if count}(w^i_{i-k+1})>0 \\ \lambda S(w_i|w^{i-1}_{i-k+2}) && \text{otherwise} \end{cases} $$
Advanced: Perplexity's Relation to Entropy
우리는 test set에서 N-gram model을 평가하는 방법으로 perplexity를 소개하였다. 더 나은 N-gram model은 test data에 더 높은 확률을 부여하는 것이고, perplexity는 test set에서의 확률을 일반화시킨 버전이다. perplexity 측정은 실제로 cross-entropy라는 perplexity의 의문적인 특성을 설명하는 것의 정보-이론 컨셉으로부터 떠오른 것이다. Entropy는 정보의 측정이다. 우리가 예측하려는 무엇이든 간에, 분포해 있는 임의 변수 X에 대하여, 그리고 특정 확률 분포에서, 그것을 p(x)라 부르면 임의 변수 X에 대한 entropy는 다음과 같다:
$$H(X) = -\sum_{x\in\chi} p(x)\log_2p(x) $$
entropy를 생각하는 직관적인 방법은 최적의 coding 스키마에서 정포의 조각들이나 결정들을 encode하는데 최소 몇 개의 bit가 필요한지에 대한 것으로 생각할 수 있다.
예시를 생각해보자.
이러한 prior 확률이 존재한다고 가정해보자.
그럴 경우 정보학에서 Horse 1은 0으로 표현될 수 있으며, Horse 2는 10, Horse 3은 110, Horse 4는 1110, Horse 5는 111100, Horse 6은 111101, Horse 7은 111110, Horse 8은 111111을 대표하게 된다. 이 때 확률을 통해 평균 몇 비트면 표현이 가능한지 확인해보면,
1*(1/2) + 2*(1/4) + 3*(1/8) + 4*(1/16) + 4*6*(1/64) = 0.5 +0.5 + 0.375 + 0.25 + 0.375 = 2
즉 2 bit라는 것을 알 수 있다.
그렇다면 Entropy의 식을 구해보면,
$$ H(X) = - \sum^{8}_{i=1} p(i)logp(i) = 2 bits $$ 라는 것을 알 수 있다.
우리는 Entropy를 통해 Entropy rate라는 것을 정의한다. (per-word entropy)
$$ \frac{1}{n}H(W^n_1) = -\frac{1}{n}\sum_{W^n_1\in L} p(W^n_1)\log p(W^n_1) $$
하지만 언어의 참 엔트로피를 구하기 위해선, 우리는 무한한 길이의 서열을 고려해야만 한다. 우리가 언어를 단어 서열을 생성하는 확률론적 방법 L로써 고려한다면, W가 단어 서열 $w_1, ... , w_n$을 대표한다할때, L의 Entropy rate H(L)은 다음과 같다:
$$ H(L) = -\lim_{n\to\infty} \frac{1}{n}H(w_1,w_2,...,w_n) $$
$$ = -\lim_{n\to\infty} \frac{1}{n} \sum_{W\in L} p(w_1,...,w_n)\log p(w_1, ..., w_n) $$
만약 언어가 정규적 성격이 있다면, 즉 정적이고 에르고딕성 성직이 있다면, Shannon-McMillan-Breiman 이론에 의해 다음과 같이 서술될 수 있다:
$$ H(L) = \lim_{n\to\infty} -\frac{1}{n}\log p(w_1w_2...w_n) $$
확률적 process가 stationary (정적인)이라는 뜻은 확률적 프로세스가 서열에 할당할 확률이 시간 흐름의 변화에 대해 불변이라는 뜻이다. 다른 말로, time t에 대한 단어 확률 분포가 time t+1에서도 확률 분포가 같다는 뜻이다. Markov model, 즉 N-gram은 정적이다. 예를 들어 bigram에서, $P_i$은 오직 $P_{i-1}$에 대하여만 의존한다. 그래서 만약 x에 대하여 시간 index를 이동할 경우, $P_{i+x}$는 아직 $P_{i+x-1}$에 대하여만 의존한다. 그러나 자연어는 정적이지가 않아서, 다가오는 단어들의 확률은, 임의로 멀거나 시간에 의존하는 사건들에 의존한다. 그러므로 우리의 통계학적 모델은 오직 자연어의 엔트로프와 옳은 분포를 향한 근사만을 제공한다.
요약하자면, 조금은 옳지 못한 에러를 만들지만 편하고 간단한 추측을 만드는 것으로 우리는 그것의 매우 긴 sample output을 취할 수 있고, 그것의 평균 로그 확률을 구하는 확률론적 프로세스의 엔트로피를 계산할 수 있는 것이다.
이제 우리는 cross-entropy를 소개할 준비가 되었다. cross-entropy는 우리가 생성된 data에 대하여 실제 확률 분포 p를 모를 때 유용하다.
$$ H(p, m) = \lim_{n\to\infty} - \frac{1}{n}\sum_{W\in L} p(w_1, ..., w_n) \log m(w_1, ..., w_n) $$
이것은 확률 분포 p를 서열이 따르게 하지만, m에 따른 확률 log를 합친다.
다시, Shannon-McMillan-Breiman 이론에 의해 정적 에르고딕 상태는 다음과 같다:
$$H(p, m) = \lim_{n\to\infty} -\frac{1}{n}\log m(w_1,w_2, ... ,w_n) $$
이것에 대한 의미는, entropy에 대하여 우리는 전체 가능한 서열을 더하는 것 대신에 충분히 긴 개인 서열을 취함으로써, 확률 분포 p에서의 model p의 cross-entropy를 추측할 수 있다.
무엇이 cross-entropy를 유용하게 하냐면, cross-entropy H(p, m)은 entropy H(p)의 상한선이다:
$$H(p) \leq H(p,m) $$
이것은 우리가 확률 p에 따른 기호의 서열들의 참 엔트로피를 추측하는데에 도와주는 간단화된 model m을 사용할 수 있다는 것을 의미한다. model m이 더 정확할 수록, H(p,m)이 보다 더 참 엔트로피인 H(p)와 가까워진다. 그러므로, H(p,m)과 H(p)의 차이점은 어떻게 모델이 정확하냐는 것에 대한 측정이다. 두 개의 모델 $m_1$과 $m_2$ 사이에, 더 정확한 모델은 더 낮은 cross-entropy를 갖게 된다.
우리는 마지막으로 perplexity와 cross-entropy간 관계를 볼 수 있게 된다. Cross-entropy는 limit에서 정의되며, 관찰된 단어 서열의 길이가 무한으로 갈 때 정의된다. 우리는 cross-entropy에 대한 근사가 필요한데, 이는 고정된 길이의 서열에 의존한다. 이러한 근사는 단어 W의 서열에 존재하는 model $M = P(w_i|w_{i-M+1}...w_{i-1})$에 대하여 다음과 같이 정의된다:
$$H(w) = -\frac{1}{N}\log P(w_1w_2...w_N) $$
단어 W의 서열에 존재하는 model P의 perplexity는 이제 형식적으로 cross-entropy의 expression 표기로써 정의된다:
$$ \text{Perplexity}(W) = 2^{H(w)} $$
$$ = P(w_1w_2...w_N)^{-\frac{1}{N}} $$
$$ = \sqrt[N]{\prod^N_{i=1} \frac{1}{P(w_i|w_1...w_{i-1})}} $$
잘보고갑니다
답글삭제