사람은 직관적으로 주어진 문장 다음에 어떤 단어가 이어질지 예측할 수 있다.
이 장에서는 이러한 직관을 수학적으로 표현하여 기계학습에 이용하고자 한다.

N-Grams

• $P(w|h)$ : 문장 $h$ 다음에 단어 $w$가 이어져 나올 확률
  
   Example)
    $P(the|its\;water\;is\;so\;transparent\;that)$
      -> 문장 $its\;water\;is\;so\;transparent\;that$ 다음에 단어 $the$ 가 나올 확률

이 확률을 계산하는 방법 중 하나는 단어 $w$가 나오는 횟수를 이용하는 것이다.
즉 이전 문장 $h$ 다음에 $w$가 나오는 횟수를 문장 $h$ 전체가 나오는 횟수로 나누는 것이다.

• $P(w|h) = \frac{C(w,\;h)}{C(h)}$
  
   Example)
    $P(the|its\;water\;is\;so\;transparent\;that) = \frac{C(its\;water\;is\;so\;transparent\;that\;the)}{C(its\;water\;is\;so\;transparent\;that)}$

이를 계산할 때의 문제점은 문장 $h$도 여러 개의 단어 $w$로 이루어져 있다는 점이다.
즉 문장 $h$가 나오는 횟수를 셀 때에도 위와 같은 공식을 반복해서 사용하게 되는 것이다.

이러한 반복은 그 값을 예측하기 너무 어렵기 때문에 다음과 같은 방법을 이용할 수 있다.

corpus에서 단어 $w_{i}$가 나오는 것에 대응되는 확률 변수 $X_{i}$의 확률을 $P(X_{i})$로 표현하면
단어 $w_{1}, w_{2},\;…\;w_{n}$ 순으로 이루어진 문장이 나올 확률은 $P(X_{1},\;X_{2},\;…\;X_{n})$ 이다.
여기에 확률 연쇄 법칙을 적용하면 다음과 같이 조건부 확률의 단순 곱으로 표현이 가능하다.

$P(X_{1},\;X_{2},\;…\;X_{n}) = P(X_{1})P(X_{2}|X_{1})P(X_3|X_{1:2})\;...\;P(X_n|X_{1:n-1})$
→ $P(w_{1},\;w_{2},\;…\;w_{n}) = P(w_{1})P(w_{2}|w_{1})P(w_3|w_{1:2})\;...\;P(w_n|w_{1:n-1})$
$=\overset{n}{\underset{k=1}{\Pi}} P(w_k|w_{1:k-1})$

이렇게 곱으로 표현함으로써 얻는 또 다른 장점은 log 계산이 쉽다는 것이다.
확률은 0과 1 사이의 작은 값이므로 $n$이 커질수록 그들의 곱은 매우 작아진다.
이로 인해 발생하는 계산 오차를 줄이고자 log probability를 종종 사용한다.

Example)
  $p_1 \times p_2 \times p_3 \times p_4 = \exp(\log{p_1} + \log{p_2} + \log{p_3} + \log{p_4})$

그러나, 얼핏 정리된 듯 보이는 이 표현 방식으로도 그 값을 계산하기는 여전히 쉽지 않다.
또한, 이 표현만으로는 언어 자체가 가진 고유한 특성을 완벽히 반영할 수 없다.

예를 들어, $its\;water$ 와 $Walden\;Pond’s\;water$ 는 동일한 의미로 사용될 수 있지만
둘 중 하나를 문장 $h$로 정하면 다른 하나는 corpus에서 찾을 수 없다는 단점이 있다.

우리는 이러한 몇 가지 문제들을 해결하고자 다음과 같은 관점으로 바라보기로 한다.

이제는 이전에 나온 단어 몇 개만 일치하는 경우를 corpus에 존재함으로 여기는 것이다.

예를 들어, 위의 예시에서 두 문구의 공통된 마지막 단어 1개는 $water$ 이므로
이 부분만 일치하면 동일한 문구라고 여기는 것이다.

이를 일반화하여 N-gram model 이라고 하며, 이전의 단어 $(N-1)$개 만을 바라본다.
확률 식에서의 근사는 $P(w_n|w_{1:n-1}) \approx P(w_n|w_{n-N+1:n-1})$ 이며,
이를 통해 원래의 식을 다시 써보면 다음과 같다.

$P(w_1, w_2,\;…\; w_n) \approx \overset{n}{\underset{k=1}{\Pi}} P(w_k|w_{k-N+1:k-1})$

이러한 관점 및 근사가 가능한 근거는 Markov assumption,
즉 현재의 확률에 먼 과거는 영향을 주지 못한다는 의사 결정 모형에 있다.

다음은 $N=1,\;N=2,\;N=3$ 일 경우의 N-gram model의 명칭과 그 식이다.
$N=4$ 이상일 경우에는 특별한 명칭 없이 4-gram, 5-gram, … 등으로 불린다.

• unigram($N=1$) : $P(w_1, w_2,\;…\; w_n) \approx \overset{n}{\underset{k=1}{\Pi}} P(w_k)$
• bigram($N=2$) : $P(w_1, w_2,\;…\; w_n) \approx \overset{n}{\underset{k=1}{\Pi}} P(w_k|w_{k-1})$
• trigram($N=3$) : $P(w_1, w_2,\;…\; w_n) \approx \overset{n}{\underset{k=1}{\Pi}} P(w_k|w_{k-2:k-1})$

Evaluating Language Models: Perplexity(PPL)

앞서 확률을 많이 언급하였지만, 실제 언어 모델에서는 Perplexity라는 값을 많이 이용한다.

Perplexity란 사전적 의미로는 혼란스럽고 복잡한 상황을 의미하며,
정보 이론에서는 이산 확률 분포 $p$와 교차 엔트로피 $H_p(\hat p)$ 에 대하여 $2^{H_p(\hat p)}$ 값을 의미한다.

교차 엔트로피(cross-entropy)란 학습된 모델의 예측에서
실제 확률 분포 $p$, 예측 확률 분포 $\hat p$를 따르는 각 사건들이 갖는 정보량에 대해
해당 모델 예측에서의 정보량 기댓값을 의미하며,

수식으로 나타내면 $H_p(\hat p)= \sum_x p(x)\log_2(1/\hat p(x)) = -\sum_x p(x)\log_2\hat p(x)$ 이다.

확률의 역수가 사건의 정보량을 나타내는 이유는 6면체 주사위와 12면체 주사위에서
원하는 눈이 나올 확률의 역수를 비교해보면 이해할 수 있다.

cf) N-gram 에서 정보량은 어떤 단어를 인코딩하는 데에 필요한 bit 수를 의미한다.
    그리고 그 기댓값이란 주어진 test set에서 필요한 평균 bit 수를 말한다.
    각 단어의 등장 빈도가 다르다면 높은 등장 빈도의 단어를 적은 bit 수로 인코딩하여
    그 평균 bit 수, 즉 엔트로피를 최소화함으로써 오차 발생 가능성을 줄인다.

      Example 1)
        $p(w_1)=1/2,\;p(w_2)=1/4,\;p(w_3)=1/8,\;p(w_4)=1/16$
        $p(w_5)=1/64,\;p(w_6)=1/64,\;p(w_7)=1/64,\;p(w_8)=1/64$
          -> $H(p) = 2\;bits$

      Example 2)
        $p(w_1)=1/8,\;p(w_2)=1/8,\;p(w_3)=1/8,\;p(w_4)=1/8$
        $p(w_5)=1/8,\;p(w_6)=1/8,\;p(w_7)=1/8,\;p(w_8)=1/8$
          -> $H(p) = 3\;bits$

cf) 교차 엔트로피는 실제 엔트로피 $H(p) = -\sum_x p(x)\log_2p(x)$의 upper bound,
    모델의 예측이 정확할수록 실제 엔트로피에 가까워진다.

cf) 지수와 로그의 밑이 같다면 그 값이 꼭 2일 필요는 없다.

즉 언어 모델의 예측 성능을 평가함에 있어 Perplexity는 부정적 지표인 셈인 것이다.
정보 이론에서의 정의를 N-gram model에 적용하면 그 식은 다음과 같다.

$PPL(w_1, w_2,\;…\;w_n) = P(w_1, w_2,\;...\;w_n)^{-\frac{1}{n}} \approx \sqrt[n]{\overset{n}{\underset{k=1}{\Pi}} \frac{1}{P(w_k|w_{k-N+1:k-1})}}$
  cf) 이 식에서의 $W = w_1, w_2,\;…\;w_n$ 은 평가를 위한 test set을 의미한다.

또한, 언어 모델에서의 Perplexity를 또 다른 방식으로 표현할 수도 있다.
단어 예측에서 여러 후보들 중에서 어떤 단어를 답으로 내놓을지 결정해야 할 것이다.
이 때의 후보들의 개수를 branching factor, 즉 분기 계수라고 부른다.

그리고 이러한 branching factor의 가중 평균을 Perplexity로 바라보는 것이다.

이를테면 어떤 6면체의 사기 주사위가 있다고 가정해보자.
이 주사위의 6의 눈이 나올 확률이 7/12, 다른 1~5의 눈이 나올 확률은 1/12 이라면
그 때의 branching factor는 여전히 6이지만, Perplexity는 다음과 같이 그보다 작다.
즉 이 사기 주사위가 원래의 주사위보다 덜 혼잡하여 다음에 나올 눈을 예측하기 더 쉽다.

$PPL = ((\frac{7}{12})^7(\frac{1}{12})^5)^{-\frac{1}{12}} \approx 3.86$
  cf) test set [1, 2, 3, 4, 5, 6, 6, 6, 6, 6, 6, 6] 에서 branching factor의 가중 평균

N-gram model에서 Perplexity 값을 계산함으로써 더 나은 성능의 $N$을 찾을 수 있다.
실제 월 스트리트 저널을 이용해 각 $N$에 따른 Perplexity를 계산한 어떤 실험이 있었는데
해당 실험에서의 결과는 다음 표와 같았다고 한다.

	unigram($N=1$)	bigram($N=2$)	trigram($N=3$)
Perplexity	962	170	109

이처럼 일반적으로는 $N$이 커질수록 그 Perplexity가 작아져 모델이 개선됨을 보인다.

하지만, 언어 모델 평가에서 Perplexity 값이 무조건적인 우위를 의미하는 것은 아니다.
동일한 단어들을 기반으로 하여 비교해야 하며, 실제 end-to-end 평가도 필요다.

또한, 실제 상황에서는 $N$이 커짐에 따른 부작용도 존재한다.
그럼에도 불구하고 Perplexity는 동일한 조건에서 성능을 빠르게 비교할 때 매우 유용하다.

다음 장에서는 실제 상황에서 N-gram model의 부작용과 그 대응책을 정리하려 한다.

---

내용에 관한 더 자세하고 정확한 설명은 아래 Reference 링크를 참고

특히 Perplexity 정의가 어떻게 N-gram 언어 모델의 수식으로 유도될 수 있는지,
엔트로피와 그 지수 로그 수식의 의미가 무엇인지에 관해서는 [1], [4], [5], [6], [7], [8] 을 참고하시면 좋을 것 같습니다.

Reference
[1] https://web.stanford.edu/~jurafsky/slp3/
[2] https://github.com/jacobeisenstein/gt-nlp-class/blob/master/notes/eisenstein-nlp-notes.pdf
[3] https://en.wikipedia.org/wiki/N-gram
[4] https://en.wikipedia.org/wiki/Perplexity
[5] https://en.wikipedia.org/wiki/Entropy_(information_theory)
[6] https://en.wikipedia.org/wiki/Cross_entropy
[7] https://towardsdatascience.com/perplexity-intuition-and-derivation-105dd481c8f3
[8] https://towardsdatascience.com/the-intuition-behind-shannons-entropy-e74820fe9800
[9] https://towardsdatascience.com/perplexity-in-language-models-87a196019a94
[10] https://en.wikipedia.org/wiki/Markov_chain
Thumbnail : https://dlabs.ai/blog/10-books-to-learn-natural-language-processing/