## Intro 이제 통계적인 관점에서 NL을 input으로 하는 문제를 해결할 방법을 찾을 것이다. 이를 Language Modeling이라고 하며, 이를 위해서 또는 이를 더 효과적으로 하기 위한 방법들을 소개할 것이다. ## Noisy Channel 일반적으로 우리는 원하는 결과가 있다. 그 결과를 얻기 위해서 우리는 말을 하거나 행동을 하거나 글을 쓴다. 그 과정은 우리가 갖고 싶은 A라는 것을 얻기 위해서 B라는 행동을 대신하는 것과 같다. 즉, 우리는 이를 A에 noise가 껴서 B라는 것이 생성되었다고 생각하는 것이다. 그리고 우리가 관측할 수 있는 것은 B밖에 없는 것이다. 이는 우리가 사용하는 NL에서도 동일하다. 우리가 원하는 결과값 A를 얻기 위해서 우리는 B라는 문장, 음성을 제시한다. 그 결과가 원하는 결과로 될 수 있는 확률을 얻어서 최종 결과를 예측하는 것이 우리의 목표인 것이다. 이 과정을 수식으로 표현하면 다음과 같아진다. $$ P(A|B) = {P(B|A)P(A)\over{P(B)}}\quad(\text{Bayes Rule}) $$ 우리가 얻고 싶은 $P(A|B)$ 를 얻기 위해서, $P(A)$와 $P(B|A)$ 를 통해서 구할 수 있는 것이다. 이에 대한 더 자세한 내용은 ML을 이해하는 것이 좋을 것이다. 추천하는 Posting은 [🔗 [ML] Parametric Estimation](/posts/ml-parametric-estimation)이다. ## Language Modeling 결국 우리가 얻고 싶은 것은 특정 문장의 할당된 확률인 것이다. 따라서, Language Model은 input으로 word sequence과 들어왔을 때, 확률을 계산하는 것이다. 그리고, 이 계산을 수행하기 위해서 필요한 parameter를 찾는 과정을 Language Modeling이라고 한다. ## Input(N-gram) 대게 이러한 모델은 문장 또는 word의 배열이 다음과 같이 주어질 때, $W = w_{1}\ w_{2}\ w_{3}\ ...\ w_{n}$ 아래와 같은 형태로 표현하는 것이 일반적이다. - **Single word probability** 하나의 단어의 확률을 나타낼 때 단순하게 아래와 같이 표현한다. $P(w_{i})\quad(w_{i} \in W)$ - **Sequence of Words probability** 일반적으로 sentence의 확률을 나타낼 때, 여러 문장을 한꺼번에 가지는 확률이므로 아래와 같이 표현하는 것이 일반적이다. $P(W) = P(w_{1}, w_{2}, w_{3}, ..., w_{n})$ - **single word probability with context** 일반적으로 우리는 이전에 사용한 단어가 문맥이라고 이해할 수 있다. 따라서, 구체적인 단어들 이후에 특정 단어가 나오는 것은 문맥을 반영한 확률이라고 생각할 수 있다. $P(W) = P(w_{5}| w_{1}, w_{2}, w_{3}, w_{4})$ 위의 식을 보게 되면, 우리는 다시 한번 sentence의 확률을 다시 정리할 수 있다. $$ P(W) = P(w_{1}) \times P(w_{2}|w_{1}) \times P(w_{3}|w_{1},w_{2}) \times ... \times P(w_{n}| w_{1},w_{2},..., w_{n-1}) $$ 위의 식을 보게되면, W가 짧다고 하더라도 굉장히 많은 처리가 필요하고, 저장을 위해 많은 공간이 필요하다는 것을 알 수 있다. 따라서, 우리는 현재 단어를 기준으로 너무 오래된 단어에 대해서는 무시를 하도록 하는 방법을 취하는 것이다.(**Markov Chain**) 이를 "n 번째까지 허락"했을 때, 이를 n-gram 이라고 부른다. $$ p(W) = \prod_{i=1}^{n}{p(w_{i}|w_{i-n+1},w_{i-n+2},...,w_{i-1})} $$ 그렇다면, n-gram에서 적절한 n이란 무엇일까? 일반적으로는 n이 크다는 것은 context를 많이 받아들일 수 있다는 의미로 받아들여질 수 있다. 따라서, n이 클수록 성능의 최적화 가능성이 더 높다. 하지만, Vocabulary의 사이즈가 커지는 경우를 예를 들어보자. 여기서는 $|V| = 60$k 라고 해보자. | n-gram | p(w_{i}) | # of parameters | | :-------------- | :------------------------------- | :---------------- | | 0-gram(uniform) | ${1\over\vert V\vert}$ | 1 | | 1-gram(unigram) | $p(w_{i})$ | $6\times10^4$ | | 2-gram(bigram) | $p(w_{i}\vert w_{i-1})$ | $3.6\times10^9$ | | 3-gram(trigram) | $p(w_{i}\vert w_{i-2}, w_{i-1})$ | $2.16\times10^14$ | n이 커질 수록 가능한 조합의 수는 굉장히 커지기 때문에 우리가 보지 못하는 경우의 수도 굉장히 증가하게 되어 data자체의 빈도가 적어지는 현상(sparse)이 발생한다. 따라서, 대게의 경우 최대 n의 크기는 3정도로 하는 것이 일반적이다. ```plaintext 🤔 주의 실제 데이터를 가공할 때에는 bigram부터는 문장의 시작과 끝을 표시해주어야 한다. 그렇지 않으면, 첫번째 문자의 확률을 구할 때, 이전 단어의 영향을 받을 수 없다. 정해진 규칙은 없지만, 대게 를 이용한다. ex. bigram : ~~w1 w2 w3 w4~~ trigram : ~~w1 w2 w3 w4~~ ``` ```plaintext 🤔 Google N-gram 구글에서 2006년에 N-gram을 직접 구성한 것이 있다. 총 1,024,908,257,229개의 단어가 존재하고, 40회 이상 등장하는 5-gram이 1,176,470,663개 존재한다. 총 Vocabulary의 size는 200번 이하로 등장하는 것은 제외하면, 13,588,391개이다. ``` ## Estimation ML에서는 Estimation을 수행할 때, continuous하게 추정하였다. 즉, 보지 못한 데이터에 대한 처리를 수행하기 위해서 continuous한 분포의 parameter만 추정하면 되었다. 하지만, NLP에서는 다르다. NL를 continuous하게 표현할 마땅한 방법이 없다. 따라서, 우리는 결국 모든 확률을 discrete하게 구해야 한다. 따라서, 우리는 특정 단어의 확률을 구하는 방법은 단 하나가 된다. $$ |T| = \text{count of observed tokens} $$ $$ c(w_{i}) = \text{count of observed } w_{i} $$ $$ \begin{align*} &P(w_{i}) = {{c(w_{i})}\over{|T|}} \\ &P(w_{i}| w_{i-1}) = {{c(w_{i-1}, w_{i})}\over{c(w_{i-1})}} \\ &P(w_{i}| w_{i-2}, w_{i-1}) = {{c(w_{i-2}, w_{i-1}, w_{i})}\over{c(w_{i-2}, w_{i-1})}} \\ \end{align*} $$ 이때, 반드시 sequence의 순서를 유의하도록 하자. 순서가 바뀌면 다른 종류이다. > **Small Example** 데이터가 다음과 같이 주어진다고 하자. ```plaintext He can buy the can of soda. ``` 이때 각 n-gram을 이용한 model의 확률들을 살펴보자. | model | probability | | :------- | :-------------------------------------------------------------------------------------------------------------------------------------------------------------- | | uni-gram | $p(He)=p(buy)=p(the)=p(of)=p(soda)=p(.) = 0.125$
$p(can)=0.25$ | | bi-gram | $p(He\vert ~~)=p(can\vert He)=p(the\vert buy)=p(can\vert the)=p(soda\vert of)=p(.\vert sode) =p(~~ \vert .) = 1$
$p(buy\vert can)=p(of\vert can)= 0.5$ | | tri-gram | $p(He\vert , ~~)=p(can\vert ~~, He)=p(the\vert He, buy)=...=p(~~\vert .,~~ ) =1$ | ## Evaluation 평가할 때는 ML과 결국은 동일하다. 우리가 확률분포를 구할 때, 사용한 데이터 외에 데이터를 이용해서 잘 적용이 되었는지를 확인할 수 있다. 하지만, word의 갯수와 데이터의 수가 굉장히 많은 NL의 특성상 이 Evaluation 단계에만 굉장히 많은 시간을 소모할 수 있다. 따라서, 즉각적인 평가를 위해서 사용하는 척도가 있다. > **Perplexity** train set을 통해 학습을 하고, test set을 통해서 평가를 수행할 때, train set을 통해 구한 확률이 실제 test set에서 어느정도의 Entropy를 발생시키는지를 확인하는 것이다. 원래의 식은 $PP = 2^{H}$이지만, 이를 변형하여 다음과 같이 나타낼 수 있다. $$ \begin{align*} PP(W) &= \sqrt[N]{1 \over P(w_1, w_2, ..., w_N)} \\ &= \sqrt[N]{\prod_{i=1}^{N}{P(w_i|w_{i-n+1}, w_{i-n+2}, ..., w_{i-1})}} \end{align*} $$ 이를 통해서, 실제로 해당 문제가 너무 어렵지는 않은지, 선택한 model이 잘못되지는 않았는지를 판단한다. | model | probability | entropy | | :------- | :-------------------------------------------------------------------------------------------------------------------------------------------------------------- | :------ | | uni-gram | $p(He)=p(buy)=p(the)=p(of)=p(soda)=p(.) = 0.125$
$p(can)=0.25$ | 2.75 | | bi-gram | $p(He\vert ~~)=p(can\vert He)=p(the\vert buy)=p(can\vert the)=p(soda\vert of)=p(.\vert sode) =p(~~ \vert .) = 1$
$p(buy\vert can)=p(of\vert can)= 0.5$ | 0.25 | | tri-gram | $p(He\vert , ~~)=p(can\vert ~~, He)=p(the\vert He, buy)=...=p(~~\vert .,~~ ) =1$ | 0 | 위의 예시를 가져와서 봐보자. 물론 동일한 dataset에서 perplexity를 측정하기는 했지만, n이 커질 수록 점점 entropy가 작아지는 것을 볼 수 있다. 그렇다면, 이런 data가 좋은 걸까? 이는 좋은 게 아니다. 왜냐하면, 해당 dataset에서만 잘 작동하도록 되어있기 때문이다. 일명 **overfitting**이다. ## Smooting 위에서 말한 overfitting을 어느정도 해소할 뿐만 아니라 정말 큰 문제가 될 수 있는 probability가 0이 되는 문제(우리가 trainset을 통해 학습한 확률 분포에서 testset에 들어오는 데이터에 해당하는 확률값이 없을 때, 즉 해당 확률이 0일때)를 해결하기 위해서는 smoothing이 필수적이다. probability가 0이 된다는 것은 후에 위에서 구한 확률로 Prediction을 할 때 모든 예측을 망치는 요인이 된다. 왜냐하면, 추정확률의 최적 Entropy를 의미하는 Cross Entropy를 $\infin$로 만들기 때문이다. (최적 Entropy가 무한대라는 것은 추정이 불가능하다는 것이다.) 따라서, 우리는 probability가 0이 되지 않게 하는 방법으로 기존의 확률의 일부를 나누어주도록 하는 방법을 제시한다. 이것이 smoothing이다. 이때 반드시 유의할 점은 smoothing을 하건 안하건 각 확률의 총합은 1이 되도록 보장해야 한다는 것이다. $$ \sum_{w \in \Omega}p(w) = 1 $$ 대략 6가지의 대표적인 smoothing 방식들을 소개하겠다. > **1. Add-1(Laplace)** 가장 간단한 방법의 smoothing 방법이지만, 실용적인면은 다소 떨어지는 방법이다. 아이디어는 간단하다. prediction을 수행할 때, 현재 들어온 input까지 포함하여 만든 $|V|$를 분모에 더하고, 분자에 1을 더해주는 방법이다. 이 방법을 사용하면, 설사 count가 0이 더라도 확률이 0이 되지는 않는다. $$ p(w) = {X \over Y} \rArr p^{\prime}(w) = {X + 1 \over Y + |V|} $$ 여기서, $|V|$ 값이 정말 헷갈렸는데, 아무도 잘 설명을 안하는 것 같아서 짚고 넘어가면, 우리가 확률값을 얻기 위해서 사용했던 dataset과 현재 prediction을 하기 위해서 들어온 input 둘에서 발생한 모든 unique한 단어의 수를 의미한다. (# of vocabulary) 그렇게 해야만 $\sum_{w \in \Omega}p(w) = 1$을 만족하는 값이 나온다. 따라서, 이를 각 각의 n-gram에 대입하면 다음과 같다. | n | $p(w_{i})$ | $p^{\prime}(w_{i})$ | | :--- | :--------------------------------------------------------- | :----------------------------------------------------------------------------- | | $1$ | $c(w_{i}) \over \vert T \vert$ | $c(w_{i}) + 1 \over \vert T \vert + \vert V \vert$ | | $2$ | ${{c(w_{i-1}, w_{i})}\over{c(w_{i-1})}}$ | ${{c(w_{i-1}, w_{i}) + 1}\over{c(w_{i-1})} + \vert V \vert} $ | | $3$ | ${{c(w_{i-2}, w_{i-1}, w_{i})}\over{c(w_{i-2}, w_{i-1})}}$ | ${{c(w_{i-2}, w_{i-1}, w_{i}) + 1}\over{c(w_{i-2}, w_{i-1})} + \vert V \vert}$ | > **2. Add-k** 1이라는 숫자가 경우에 따라서는 굉장히 큰 영향을 줄 때가 있다. 특히 기존 데이터의 수가 적은 경우에 더욱 그렇다. 따라서, 이를 해결하기 위해서 1보다 작은 임의의 값(k)을 쓰는 방법이다. $$ p(w) = {X \over Y} \rArr p^{\prime}(w) = {X + 1 \over Y + k|V|} $$ 하지만, 위와 같은 방식은 결국 어떤 확률 값이든지 분자에 1을 더하기 때문에 불평등하게 값을 나눠준다고 할 수 있다. 왜냐하면, 애초에 count(분자)가 큰 데이터에게 1은 별로 영향을 안주겠지만, 분자가 처음부터 작았던 경우에는 이로 인해서 받는 영향이 굉장히 크기 때문이다. 따라서, 이러한 한계점을 극복할 수 있는 방법들이 아래와 같은 방법들이다. > **3.Good Turing** 이를 이해하기 위해서는 우리는 새로운 feature의 데이터를 가져와야 한다. 바로 word의 frequency의 frequency이다. $$ N_{k} = \sum_{i=1}^{n}1[c(w_{i}) = k] $$ 아마 예시를 봐야 이해가 빠를테니 하나의 예시를 보자. ```plaintext sam I am I am sam I do not eat ``` 이 경우 우리는 다음과 같이 count를 구할 수 있다. $$ \begin{align*} &c(I) &=\ 3 \\ &c(sam) &=\ 2\\ &c(am) &=\ 2\\ &c(do) &=\ 1\\ &c(not) &=\ 1\\ &c(eat) &=\ 1\\ \end{align*} \quad\rArr\quad \begin{align*} & N_{1} = 3 \\ & N_{2} = 2 \\ & N_{3} = 1 \end{align*} $$ 여기서 Good Turing은 한 번도 안본 데이터에게는 한 번만 보는 경우의 수를 전체 경우의 수로 나눈값만큼의 확률을 나누어주고, 기존 데이터들에게는 laplace처럼 1을 더해주는 것이 아니라 비례하는 만큼을 곱해주어 적절한 확률을 가져갈 수 있게하였다. 따라서, 식은 다음과 같다. $$ p(w_{i}) = {(c(w_{i})+1)N_{c(w_{i})+1}\over{N_{c(w_{i})}}} \times {1\over |T|},\quad (N_{0} = 1) $$ 대게 ${(c(w_{i})+1)N_{c(w_{i})+1}\over{N_{c(w_{i})}}}$이 부분을 $c^{*}$라고도 부른다. > **4. Kneser-Ney** 가장 널리 쓰이는 Smoothing 방식으로 기억해두는 것이 좋다. 이를 이해하기 위해서는 먼저, Absolute Discounting을 먼저 이해해야 한다. Good-turing 방식을 사용했을 때 $c$와 $c^{*}$사이에 차이가 경험적으로 특정 상수만큼씩 차이가 난다는 것을 발견하여, $$ c^{*} = c - d $$ Church과 Gale은 이를 Absolute Discounting 확률이라며 다음 식을 제시한다. $$ P(w_{i}|w_{i-1}) = {c(w_{i-1}, w_{i}) -d \over c(w_{i-1})} + \lambda(w_{i-1})P(w) $$ 여기서 뒷에 부분 $\lambda(w_{i-1})P(w)$은 discounting으로 발생한 오차를 매꾸기 위한 값이다. 여기서 Kneser-Ney problem은 더 넓은 범위로 확장시킬 수 있는 범위로 확장시킨 것이다. 기존에는 bigram으로 제한되어 있던 Absolute Discounting의 식은 다음과 같이 변형된다. $$ P_{KN}(w_{i}|w_{i-n+1}^{i-1}) = {\max(c(w_{i-1}, w_{i}) -d, 0) \over c(w_{i-n+1}^{i-1})} + \lambda(w_{i-n+1}^{i-1})P_{KN}(w_{i}|w_{i-n+2}^{i-1}) $$ (위의 식에 대해서 정확하게 이해를 하지 않았지만, 그렇구나 하고 넘어가도 충분할 것 같다.) > **5. Backoff & Interpolation** 상황에 따라서 unigram, bigram, trigram을 가중치만큼 더해서 사용하는 방식이다. 결국 n-gram에서 n이 작아질 수록 detail을 신경쓸 수 없지만, 신뢰도 자체는 늘어날 수 있다. 따라서, 이를 적절히 섞어쓰면 좋은 결과가 나온다는 이론이다. 하지만, 어떤 것을 더 중점으로 직접 정해주어야 한다. $$ p^{\prime}(w_{i}|w_{i-2}, w_{i-1}) = \lambda_{3}p(w_{i}|w_{i-2}, w_{i-1}) + \lambda_{2}p(w_{i}|w_{i-1}) + \lambda_{1}p(w_{i}) + {\lambda_{0}\over|V|} $$ 이를 정할 때는 대게 held-out data를 활용해서 구한다.(validation set이라고 부른다.) 즉, 전체 corpus를 (train, validation, test)로 적절히 나누어 쓰라는 것이다. 그래서 성능을 측정할 때는 testset을 쓰고, $\lambda$를 추정할 때에는 validation(heldout)set을 사용하라는 것이다. ## Word Class Smoothing 방식을 이용해서 unseen data를 처리해주었는데 좀 더 효과적으로 이를 처리하는 방법을 고려한 것이다. class단위로 word를 grouping하는 것이다. 그래서 존재하지 않는 단어였다고 하더라도 특정 group에 속한다면, 이를 활용해서 어느정도 확률을 부여할 수 있다는 것이다. 이 방식을 활용하면, 실제로 보지 않은 데이터에 대해서도 현실적인 추정이 가능하지만 detail에 대한 성능은 감소할 수 있다. $$ p(w_{i}|w_{i-1}) \rArr p(w_{i}|c_{i-1}) ={ c(c_{i}, w_{i}) \over c(c_{i-1}) } $$ 위의 식을 보면, 이전 단어의 context를 보는 것이 아니라 이제는 class를 보고 다음 단어를 probability를 계산하도록 바뀐 것이다. 그리고 이 확률은 class내부에서 해당 단어의 빈도를 이전 class의 빈도로 나누었다고 보면 되겠다. $$ p(w_{i}|c_{i-1}) = p(w_{i}|c_{i}) \times p(c_{i}|h_{i}) $$ 즉, class 단위로 단어를 묶고 class에서 단어의 발생 확률에 class에서의 n-gram을 곱한 값이 되는 것이다. 일반적인 Bayes Decison Rule에 기반하여 선택한다고 보면 되겠다. ## Example. Spelling Correction 여태까지 배운 내용을 활용하여 Spelling 오류를 정정해주는 application을 제작한다고 해보자. 먼저, Spelling Error의 종류부터 알아보도록 하자. - **Non word Error** 잘못된 spelling에 의해서 전혀 뜻이 없는 단어가 만들어진 경우이다. 해결을 위해서는 사전에서 유사한 단어를 찾아서 가장 가능성이 높은 것 또는 이전에 배웠던 shortest edit distance를 찾는 것이다. - **Real word Error** 잘못된 spelling 또는 유사한 발음 때문에 뜻이 있는 단어가 만들어졌지만, 오류가 의심되는 경우이다. 해결책은 비슷한 발음 또는 spelling의 모든 단어를 찾아서 해당 단어와 함께 language model에 넣어서 가장 높은 가능성을 가지는 값을 찾는 것이다. 먼저, **Non Word Error** 같은 경우는 오타 데이터에 원래 쓰려고 했던 값을 labeling해서 모아두고 다음 값을 학습시키는 것이다. (*x=오타데이터, w=사전에있는단어) - $P(x|w)$ = x가 w일 가능성 - $p(w)$ = w의 확률 그리고 나서, 다음을 실행시켜서 가장 적절한 $\hat{w}$를 찾으면 된다. $$ \begin{align*} \hat{w} &= \argmax_{w \in V}P(w|x) \\ &= \argmax_{w \in V}{P(x|w)P(w)} \end{align*} $$ **Real Word Error**의 경우에는 결국 이전 단어 sequence를 활용해야 한다. 전체 corpus를 학습해서 tri-gram을 추출해놓고, 번갈아가면서 후보 단어들을 집어넣어서 가장 높은 확률이 나오는 단어를 사용하는 것이다. 예를 들어, 후보 단어가 다음과 같이 정해졌다고 하자. ($\bold{w}_{3} = {w_3^{(1)}, w_3^{(2)}, w_3^{(3)}, ...}$) 이때 우리가 원하는 w는 다음과 같이 구할 수 있다. $$ \hat{w}_{3} = \argmax_{w_{3}^{(i)} \in \bold{w}_{3}} P(w_{3}^{(i)}| w_{1}, w_{2}) $$ ## Reference - Tumbnail : Photo by [David Ballew](https://unsplash.com/@daveballew?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) on [Unsplash](https://unsplash.com/@daveballew?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)

Ngram