언어 모델(Language Models)과 N-gram
22 May 2020 | NLP
본 포스트의 내용은 조경현 교수님의 강의 , 고려대학교 강필성 교수님의 강의 와 김기현의 자연어처리 딥러닝 캠프 , 밑바닥에서 시작하는 딥러닝 2 , 한국어 임베딩 , 자연어 처리 인 액션 , 딥 러닝을 이용한 자연어 처리 입문 책을 참고하였습니다.
Language Model
이번 시간에 알아볼 N-gram(엔그램) 은 언어 모델(Language Models, LM) 에서 사용되는 횟수 기반의 벡터 표현방식(Count-based representation) 입니다. N-gram을 알아보기 전에 먼저 언어 모델이 무엇인지에 대해 간략하게 알아보도록 합시다.
언어 모델이란 무엇일까요? 언어 모델의 입력과 출력값을 보며 어떤 것을 수행하고자 하는 지를 유추해봅시다. 언어 모델에 입력되는 것은 하나의 문장이고, 출력값은 입력했던 문장에 대한 확률입니다. 이 확률은 입력은 문장이 얼마나 그럴듯한 지를 계산한 값입니다. 즉, 언어 모델의 목적은 가장 자연스러운 단어의 시퀀스를 찾아내는 것입니다. 수식으로 나타내면 다음과 같습니다.
\[P(X) = P(x_1, x_2, \cdots, x_T)\]
언어 모델은 말뭉치 내에 있는 수많은 단어 중 가장 적절한 결합을 찾아내기 위한 작업이므로 비지도 학습(Unsupervised Learning) 입니다. 하지만 비지도 학습은 어려우며 기법도 많이 나와있지 않습니다. 그렇기 때문에 단어(토큰)에 순서를 부여하여 연속되는 지도 학습(Supervised Learning)으로 바꾸어주기로 합니다.
Autoregressive Language Model
어떻게 지도학습으로 바꿀 수 있을까요? 자기회귀 언어모델(Autoregressive language model)이라는 방법을 사용합니다. 자기회귀 모델을 사용하면 다음에 올 토큰의 분포를 이전 모든 토큰들의 조건부 확률로 표현합니다. 그리고 이 방법을 문장이 끝나는 토큰 end of sentence 이 올 때까지 반복하면 하나의 문장이 완성되는 방식입니다. 자기회귀 언어모델을 사용하여 언어모델의 식을 변형해봅시다.
\[\begin{aligned}
P(X) &= P(x_1, x_2, \cdots, x_T) \\
&= P(x_1)P(x_2\vert x_1)P(x_3\vert x_1, x_2) ... P(x_T\vert x_1, x_2 ... x_{T-1}) \\
&\because P(a,b) = P(a)P(b \vert a)
\end{aligned}\]
가장 아래 식을 풀어 설명해봅시다. 첫 번째 항인 $P(x_1)$ 은 단어 $x_1$ 이 문장의 첫 번째 자리로 올 확률입니다. 두 번째 항인 $P(x_2\vert x_1)$ 은 무엇일까요? 문장의 첫 번째 단어가 $x_1$ 일 때, 그 뒤에 $x_2$ 가 위치할 확률이 됩니다. 이렇게 문장이 끝나는 토큰이 올 때까지 구하는 것을 자기회귀 언어모델이라고 합니다.
자기회귀 언어모델의 하나마다의 입력과 출력은 어떻게 될까요? 이제는 문장 전체가 아니라 목표하는 토큰인 $x_T$ 이전까지의 모든 토큰의 시퀀스 $x_1, x_2 … x_{T-1}$ 를 입력합니다. 출력값은 $x_T$ 자리에 올 가능성이 있는 토큰들의 확률 분포가 됩니다.
하나의 예시를 들어봅시다. 자기회귀 언어모델은 “In Korea, more than half of residents speak Korean.” 이라는 문장을 어떻게 생성하게 될까요? 일단은 “In” 이 문장 맨 앞에 오는 것이 적절한지에 대한 확률(Scoring)을 계산합니다. 그 다음에는 “Korea” 가 “In” 뒤에 오는 것이 적절한지에 대한 확률을 계산합니다. 이 과정을 모든 단어에 대하여 반복합니다. 마지막 “Korean” 에 대한 확률은 “Korean” 이 “In Korea, more than half of residents speak” 뒤에 오는 것이 적절한가? 라는 질문에 대한 답이 됩니다. 예를 들어, “In Korea, more than half of residents speak Korean.” 와 “In Korea, more than half of residents speak Finnish.” 라는 선택지에서 전자의 확률이 더 높다고 판단하는 것이지요.
각 경우의 조건부 확률은 말뭉치에 등장하는 단어 시퀀스의 횟수를 통해 계산됩니다. 횟수의 통계로부터 계산하기 때문에 이 방법을 이후에 등장하는 신경망 기반의 언어모델과 구분하여 통계 기반의 언어 모델(Statistical Language Models) 이라고도 합니다. 예를 들어, 말뭉치에 “In Korea, more” 이라는 단어 시퀀스가 1000번 등장하였고 “In Korea, more than” 이 라는 단어 시퀀스가 600번 등장하였다면 조건부 확률 $P(\text{than} \vert\text{In Korea, more})$ 은 다음과 같이 계산됩니다.
\[P(\text{than} \vert\text{In Korea, more}) = \frac{P(\text{In Korea, more than})}{P(\text{In Korea, more})} = \frac{600}{1000} = 0.6\]
Sparsity
자기회귀 모델은 비지도 학습을 지도 학습으로 변화시켜 주지면 한 가지 문제를 가지고 있습니다. 가장 큰 문제는 데이터의 희소성(Sparsity)에 대한 문제입니다. 만약 말뭉치에 “In Korea, more than half of” 란 표현은 $k$ 번 등장하지만, “In Korea, more than half of residents” 란 표현은 한 번도 등장하지 않는다면 어떻게 될까요? “In Korea, more than half of residents speak Korean.” 라는 문장이 등장할 확률은 0이 됩니다. 수식으로 알아보도록 합시다.
\[P(\text{residents} \vert \text{In Korea, more than half of}) = \frac{P(\text{In Korea, more than half of residents})}{P(\text{In Korea, more than half of})} = \frac{0}{k} = 0\]
“In Korea, more than half of residents speak Korean.” 은 현실에서 사용 가능한 자연스러운 문장입니다. 하지만 말뭉치에 등장하지 않았다는 이유만으로 언어 모델은 이 문장을 생성할 수 없게 됩니다. 물론 말뭉치의 크기를 키우면 이런 문제가 줄어들기는 하지만 원천적으로 문제를 해결하기 위한 방법은 아닙니다. 이런 문제를 크게 개선하기 위해 나온 방법이 바로 N-gram 입니다.
N-gram
N-gram(엔그램) 은 Bag of Words , TF-IDF 와 같이 횟수를 사용하여 단어를 벡터로 표현(Count-based representation) 하는 방법입니다. 이전 두 방법을 사용할 때에는 한 개의 단어만을 분석 대상으로 삼았지만 N-gram은 한 단어 이상의 단어 시퀀스를 분석 대상으로 삼습니다. N-gram 앞에 N에 따라서 단어 시퀀스를 몇 개의 단어로 구성할 지를 결정하게 됩니다. $N = 1, 2, 3$ 인 경우를 각각 Uni-gram, Bi-gram, Tri-gram 이라 부르며 $N >= 4$ 일 때는 그냥 4-gram, 5-gram 의 방식으로 부릅니다. 아래의 그림을 통해 Uni-gram, Bi-gram, Tri-gram에서 단어 시퀀스가 어떻게 구성되는 지를 알아봅시다.
이미지 출처 : deepai.org
각각의 방법으로 $i$ 번째 토큰인 $x_i$ 의 조건부 확률을 구하면 다음과 같습니다.
\[\begin{aligned}
\text{Uni-gram : } P(x_i|x_1, x_2, \cdots , x_{i-1}) &\approx P(x_i)\\
\text{Bi-gram : } P(x_i|x_1, x_2, \cdots , x_{i-1}) &\approx P(x_i|x_{i-1})\\
\text{Tri-gram : } P(x_i|x_1, x_2, \cdots , x_{i-1}) &\approx P(x_i|x_{i-2}, x_{i-1})
\end{aligned}\]
위와 같이 식을 변형할 수 있는 이유는 마르코프 가정(Markov assumption) 덕분입니다. 마르코프 가정이란 특정 시점에서 어떤 상태의 확률은 최근 상태에만 의존한다는 가정입니다. 즉, $x_i$ 의 확률을 그 이전에 있는 수 개의 토큰으로부터 추론할 수 있다는 것이지요. 수식으로 나타내면 다음과 같고 그 아래는 마르코프 가정을 사용한 마르코프 체인을 이미지로 나타낸 것입니다.
\[P(x_i|x_1, x_2, \cdots , x_{i-1}) \approx P(x_i|x_{i-k}, \cdots , x_{i-1})\]
이미지 출처 : machlearnwiki
총 $T$ 개의 토큰으로 구성된 문장의 확률을 N-gram을 사용하여 나타내면 다음과 같이 됩니다.
\[\begin{aligned}
P(x_1, x_2, \cdots , x_T) &\approx \prod^T_{i=1} P(x_i|x_{i-k}, \cdots , x_{i-1}) \quad \text{[N-gram]}, N=k+1 \\
&\approx \prod^T_{i=1} P(x_i) \quad \text{[Uni-gram]} \\
&\approx \prod^T_{i=1} P(x_i|x_{i-1}) \quad \text{[Bi-gram]} \\
&\approx \prod^T_{i=1} P(x_i|x_{i-1},x_{i-2}) \quad \text{[Tri-gram]}
\end{aligned}\]
N-gram이 어떻게 희소성 문제를 해결하는지 알아봅시다. 이전에 들었던 예시를 그대로 가져와 봅시다. 말뭉치에 “In Korea, more than half of” 라는 표현은 등장하지만 “In Korea, more than half of residents” 란 표현은 한 번도 등장하지 않는 경우를 가정하였습니다. N-gram은 문장의 처음부터 조건을 걸어주지 않아도 되기 때문에 조건이 매우 간단해집니다.
예를 들어, Bi-gram을 사용할 때 “of residents” 라는 단어가 한 번 이상 말뭉치에 등장한다면 “In Korea, more than half of” 의 뒤에 “residents” 라는 토큰이 올 확률은 0이 아니게 됩니다. 전체 문장인 “In Korea, more than half of residents speak Korean.” 의 확률을 구할 때도 “In Korea”, “Korea, more”, “more than”, … , “speak Korean.” 의 횟수만 세어가며 구하게 되지요. 하지만 N-gram도 여러 문제를 가지고 있습니다. 어떤 문제를 발생시킬까요?
Problems of N-grams
N-gram의 첫 번째 문제는 장기 의존성(Long-term dependency) 의 부재입니다. 이전에는 목표 토큰 이전에 있는 모든 토큰을 고려하여 목표 토큰의 확률을 계산하였습니다. 하지만 N-gram에서는 일부 단어 시퀀스의 횟수만을 가지고 판단하기 때문에 문장 앞쪽의 문맥을 고려하지 않은 채 토큰을 선택하게 됩니다.
위에서 사용했던 다른 예시를 다시 가져와 봅시다. “In Korea, more than half of residents speak Korean.” 와 “In Korea, more than half of residents speak Finnish.” 중 더 적절한 문장을 고르는 문제입니다. 마지막 단어 토큰을 선택할 때 이전에 위치한 모든 토큰을 고려한다면 당연히 “In Korea, more than half of residents speak Korean.” 를 선택할 것입니다. 말뭉치에 “In Korea, more than half of residents speak Korean.” 가 등장할 확률이 “In Korea, more than half of residents speak Finnish.” 가 등장할 확률보다는 높겠지요.
하지만 N-gram을 사용하면 어떻게 될까요? 다시 Bi-gram을 사용하는 경우를 생각해봅시다. 우리가 준비한 말뭉치에 “speak Finnish.” 라는 시퀀스가 “speak Korean.” 보다 많이 등장할 수 있습니다. 이렇게 된다면 충분히 “In Korea, more than half of residents speak Finnish.” 라는 사실과 다른 문장을 컴퓨터가 만들 수 있게 됩니다.
실제로 N-gram을 사용할 때는 $N=1 \sim 5$ 까지 여러 N-gram을 섞어 사용하여 이런 문제를 해결합니다. 의존성 분석(Dependency parsing)도 장기 의존성 문제를 해결하기 위한 방법입니다. 의존성 분석의 방법에는 Shift reduce parsing 과 같은 Transition-based Model과 토큰끼리의 의존성 구조를 그래프로 표현한 Graph-based Model이 있습니다.
이미지 출처 : researchgate.net
그런데 $N$ 을 $7,8$ 정도로 늘리면 장기 의존성 문제가 해결되지 않을까요? 그런데 왜 N을 증가시키지 않는 것일까요? $N$ 을 증가시키면 이전에 살펴보았던 희소성 문제가 부활하게 됩니다. 실제로 $N >= 7$ 인 N-gram에서는 대부분의 시퀀스 등장 확률이 0이 됩니다. 그리고 Bi-gram과 같이 짧은 단어 시퀀스에서도 희소성(Sparsity) 문제는 여전히 발생합니다.
예를 들어, “마라룽샤를 요리하다.” 라는 단어는 실제로 사용할 수 있는 단어이지만 실제로 많이 쓰는 단어는 아니기 때문에 우리가 학습에 사용할 말뭉치에 없을 수도 있습니다. “마라룽샤를 요리하다” 는 “컵을 요리하다”, “책꽂이를 요리하다” 와 달리 자연스러운 문장임에도 등장 확률은 0이 됩니다. N-gram 모델에서 발생하는 희소성 문제를 해결하기 위해서 스무딩(Smoothing) 과 백오프(Backoff) 라는 방법이 사용되고 있습니다.
스무딩은 발생 횟수가 0이 되지 않도록 단어 시퀀스의 출현 빈도를 보정해주는 방법입니다. 가장 기본적인 스무딩으로는 모든 단어 시퀀스의 출현 빈도에 작은 값을 더해주는 방법이 있습니다. 아래는 모든 단어 시퀀스의 출현 횟수에 $k$ 를 더해주는 스무딩을 수식으로 나타낸 것입니다.
\[P(w_i|w_{<i}) \approx \frac{\text{Count}(w_{<i},w_i) + k}{\text{Count}(w_{<i}) + kV} \approx \frac{\text{Count}(w_{<i},w_i) + (m/V)}{\text{Count}(w_{<i}) + m}\]
백오프는 $p=0$ 이 되는 경우에만 $N$ 을 더 작게하는 방법입니다. 예를 들어, Bi-gram을 사용하면서 “마라룽샤를 요리하다” 가 없을 경우에는 Uni-gram을 사용하여 “마라룽샤를” 을 찾습니다. 백오프를 사용할 경우에는 보정을 위해서 Correction factor $\alpha, \beta$ 를 사용해줍니다. 수식으로 표현하면 아래와 같습니다.
\[c(x_{-N}, ... ,x) = \begin{cases}{\alpha}c(x_{-N+1}, ... ,x) + \beta \quad \text{if } c(x_{-N}, ... ,x) = 0 \\ c(x_{-N}, ... ,x) \qquad \qquad \text{ otherwise} \end{cases}\]
가장 널리 사용되는 방법으로는 Kneser-Ney(KN) 스무딩 방법이 있습니다. 기본적인 아이디어는 목적이 되는 단어 $w$ 이전에 나타나는 단어 $v$ 가 얼마나 다양한 지를 알아내는 데에 있습니다. $v$ 가 클수록 말뭉치에서 나타나지 않는 단어 시퀀스가 될 가능성이 높기 때문입니다. KN 스무딩은 다음의 수식을 사용하여 단어가 나타날 확률 $P_{KN}$ 을 나타냅니다.
\[P_{KN} (w_i|w_{i-1}) = \frac{\max(\text{Count}(w_{i-1},w_i) - d,0)}{\text{Count}(w_i)} + \lambda(w_{i-1}) \times \text{Score}_{\text{continuation}}(w_i) \\
\begin{aligned}
\text{where} \quad &\lambda(w_{i-1}) = \frac{d}{\sum_v \text{Count}(w_{i-1})} \times |\{w:c(w_{i-1},v) > 0\}| \\
&\text{Score}_{\text{continuation}}(w_i) = \frac{|\{v:\text{Count}(v,w) > 0\}|}{\sum_{w^{\prime}}|\{v:\text{Count}(v,w^{\prime}) > 0\}|}
\end{aligned}\]
위 식에서 $d$ 는 하이퍼파라미터이며 일반적으로는 0.75를 사용합니다. 또한 Score를 산출하는 식에서 $w^\prime$ 은 $v$ 뒤에 등장하는 다른 단어를 나타냅니다. KN 스무딩은 KenLM 패키지 내에 구현되어 있습니다.
본 포스트의 내용은 조경현 교수님의 강의 , 고려대학교 강필성 교수님의 강의 와 김기현의 자연어처리 딥러닝 캠프 , 밑바닥에서 시작하는 딥러닝 2 , 한국어 임베딩 , 자연어 처리 인 액션 , 딥 러닝을 이용한 자연어 처리 입문 책을 참고하였습니다.
Language Model
이번 시간에 알아볼 N-gram(엔그램) 은 언어 모델(Language Models, LM) 에서 사용되는 횟수 기반의 벡터 표현방식(Count-based representation) 입니다. N-gram을 알아보기 전에 먼저 언어 모델이 무엇인지에 대해 간략하게 알아보도록 합시다.
언어 모델이란 무엇일까요? 언어 모델의 입력과 출력값을 보며 어떤 것을 수행하고자 하는 지를 유추해봅시다. 언어 모델에 입력되는 것은 하나의 문장이고, 출력값은 입력했던 문장에 대한 확률입니다. 이 확률은 입력은 문장이 얼마나 그럴듯한 지를 계산한 값입니다. 즉, 언어 모델의 목적은 가장 자연스러운 단어의 시퀀스를 찾아내는 것입니다. 수식으로 나타내면 다음과 같습니다.
\[P(X) = P(x_1, x_2, \cdots, x_T)\]언어 모델은 말뭉치 내에 있는 수많은 단어 중 가장 적절한 결합을 찾아내기 위한 작업이므로 비지도 학습(Unsupervised Learning) 입니다. 하지만 비지도 학습은 어려우며 기법도 많이 나와있지 않습니다. 그렇기 때문에 단어(토큰)에 순서를 부여하여 연속되는 지도 학습(Supervised Learning)으로 바꾸어주기로 합니다.
Autoregressive Language Model
어떻게 지도학습으로 바꿀 수 있을까요? 자기회귀 언어모델(Autoregressive language model)이라는 방법을 사용합니다. 자기회귀 모델을 사용하면 다음에 올 토큰의 분포를 이전 모든 토큰들의 조건부 확률로 표현합니다. 그리고 이 방법을 문장이 끝나는 토큰 end of sentence 이 올 때까지 반복하면 하나의 문장이 완성되는 방식입니다. 자기회귀 언어모델을 사용하여 언어모델의 식을 변형해봅시다.
가장 아래 식을 풀어 설명해봅시다. 첫 번째 항인 $P(x_1)$ 은 단어 $x_1$ 이 문장의 첫 번째 자리로 올 확률입니다. 두 번째 항인 $P(x_2\vert x_1)$ 은 무엇일까요? 문장의 첫 번째 단어가 $x_1$ 일 때, 그 뒤에 $x_2$ 가 위치할 확률이 됩니다. 이렇게 문장이 끝나는 토큰이 올 때까지 구하는 것을 자기회귀 언어모델이라고 합니다.
자기회귀 언어모델의 하나마다의 입력과 출력은 어떻게 될까요? 이제는 문장 전체가 아니라 목표하는 토큰인 $x_T$ 이전까지의 모든 토큰의 시퀀스 $x_1, x_2 … x_{T-1}$ 를 입력합니다. 출력값은 $x_T$ 자리에 올 가능성이 있는 토큰들의 확률 분포가 됩니다.
하나의 예시를 들어봅시다. 자기회귀 언어모델은 “In Korea, more than half of residents speak Korean.” 이라는 문장을 어떻게 생성하게 될까요? 일단은 “In” 이 문장 맨 앞에 오는 것이 적절한지에 대한 확률(Scoring)을 계산합니다. 그 다음에는 “Korea” 가 “In” 뒤에 오는 것이 적절한지에 대한 확률을 계산합니다. 이 과정을 모든 단어에 대하여 반복합니다. 마지막 “Korean” 에 대한 확률은 “Korean” 이 “In Korea, more than half of residents speak” 뒤에 오는 것이 적절한가? 라는 질문에 대한 답이 됩니다. 예를 들어, “In Korea, more than half of residents speak Korean.” 와 “In Korea, more than half of residents speak Finnish.” 라는 선택지에서 전자의 확률이 더 높다고 판단하는 것이지요.
각 경우의 조건부 확률은 말뭉치에 등장하는 단어 시퀀스의 횟수를 통해 계산됩니다. 횟수의 통계로부터 계산하기 때문에 이 방법을 이후에 등장하는 신경망 기반의 언어모델과 구분하여 통계 기반의 언어 모델(Statistical Language Models) 이라고도 합니다. 예를 들어, 말뭉치에 “In Korea, more” 이라는 단어 시퀀스가 1000번 등장하였고 “In Korea, more than” 이 라는 단어 시퀀스가 600번 등장하였다면 조건부 확률 $P(\text{than} \vert\text{In Korea, more})$ 은 다음과 같이 계산됩니다.
\[P(\text{than} \vert\text{In Korea, more}) = \frac{P(\text{In Korea, more than})}{P(\text{In Korea, more})} = \frac{600}{1000} = 0.6\]Sparsity
자기회귀 모델은 비지도 학습을 지도 학습으로 변화시켜 주지면 한 가지 문제를 가지고 있습니다. 가장 큰 문제는 데이터의 희소성(Sparsity)에 대한 문제입니다. 만약 말뭉치에 “In Korea, more than half of” 란 표현은 $k$ 번 등장하지만, “In Korea, more than half of residents” 란 표현은 한 번도 등장하지 않는다면 어떻게 될까요? “In Korea, more than half of residents speak Korean.” 라는 문장이 등장할 확률은 0이 됩니다. 수식으로 알아보도록 합시다.
\[P(\text{residents} \vert \text{In Korea, more than half of}) = \frac{P(\text{In Korea, more than half of residents})}{P(\text{In Korea, more than half of})} = \frac{0}{k} = 0\]“In Korea, more than half of residents speak Korean.” 은 현실에서 사용 가능한 자연스러운 문장입니다. 하지만 말뭉치에 등장하지 않았다는 이유만으로 언어 모델은 이 문장을 생성할 수 없게 됩니다. 물론 말뭉치의 크기를 키우면 이런 문제가 줄어들기는 하지만 원천적으로 문제를 해결하기 위한 방법은 아닙니다. 이런 문제를 크게 개선하기 위해 나온 방법이 바로 N-gram 입니다.
N-gram
N-gram(엔그램) 은 Bag of Words , TF-IDF 와 같이 횟수를 사용하여 단어를 벡터로 표현(Count-based representation) 하는 방법입니다. 이전 두 방법을 사용할 때에는 한 개의 단어만을 분석 대상으로 삼았지만 N-gram은 한 단어 이상의 단어 시퀀스를 분석 대상으로 삼습니다. N-gram 앞에 N에 따라서 단어 시퀀스를 몇 개의 단어로 구성할 지를 결정하게 됩니다. $N = 1, 2, 3$ 인 경우를 각각 Uni-gram, Bi-gram, Tri-gram 이라 부르며 $N >= 4$ 일 때는 그냥 4-gram, 5-gram 의 방식으로 부릅니다. 아래의 그림을 통해 Uni-gram, Bi-gram, Tri-gram에서 단어 시퀀스가 어떻게 구성되는 지를 알아봅시다.
이미지 출처 : deepai.org
각각의 방법으로 $i$ 번째 토큰인 $x_i$ 의 조건부 확률을 구하면 다음과 같습니다.
\[\begin{aligned} \text{Uni-gram : } P(x_i|x_1, x_2, \cdots , x_{i-1}) &\approx P(x_i)\\ \text{Bi-gram : } P(x_i|x_1, x_2, \cdots , x_{i-1}) &\approx P(x_i|x_{i-1})\\ \text{Tri-gram : } P(x_i|x_1, x_2, \cdots , x_{i-1}) &\approx P(x_i|x_{i-2}, x_{i-1}) \end{aligned}\]위와 같이 식을 변형할 수 있는 이유는 마르코프 가정(Markov assumption) 덕분입니다. 마르코프 가정이란 특정 시점에서 어떤 상태의 확률은 최근 상태에만 의존한다는 가정입니다. 즉, $x_i$ 의 확률을 그 이전에 있는 수 개의 토큰으로부터 추론할 수 있다는 것이지요. 수식으로 나타내면 다음과 같고 그 아래는 마르코프 가정을 사용한 마르코프 체인을 이미지로 나타낸 것입니다.
\[P(x_i|x_1, x_2, \cdots , x_{i-1}) \approx P(x_i|x_{i-k}, \cdots , x_{i-1})\]
이미지 출처 : machlearnwiki
총 $T$ 개의 토큰으로 구성된 문장의 확률을 N-gram을 사용하여 나타내면 다음과 같이 됩니다.
\[\begin{aligned} P(x_1, x_2, \cdots , x_T) &\approx \prod^T_{i=1} P(x_i|x_{i-k}, \cdots , x_{i-1}) \quad \text{[N-gram]}, N=k+1 \\ &\approx \prod^T_{i=1} P(x_i) \quad \text{[Uni-gram]} \\ &\approx \prod^T_{i=1} P(x_i|x_{i-1}) \quad \text{[Bi-gram]} \\ &\approx \prod^T_{i=1} P(x_i|x_{i-1},x_{i-2}) \quad \text{[Tri-gram]} \end{aligned}\]N-gram이 어떻게 희소성 문제를 해결하는지 알아봅시다. 이전에 들었던 예시를 그대로 가져와 봅시다. 말뭉치에 “In Korea, more than half of” 라는 표현은 등장하지만 “In Korea, more than half of residents” 란 표현은 한 번도 등장하지 않는 경우를 가정하였습니다. N-gram은 문장의 처음부터 조건을 걸어주지 않아도 되기 때문에 조건이 매우 간단해집니다.
예를 들어, Bi-gram을 사용할 때 “of residents” 라는 단어가 한 번 이상 말뭉치에 등장한다면 “In Korea, more than half of” 의 뒤에 “residents” 라는 토큰이 올 확률은 0이 아니게 됩니다. 전체 문장인 “In Korea, more than half of residents speak Korean.” 의 확률을 구할 때도 “In Korea”, “Korea, more”, “more than”, … , “speak Korean.” 의 횟수만 세어가며 구하게 되지요. 하지만 N-gram도 여러 문제를 가지고 있습니다. 어떤 문제를 발생시킬까요?
Problems of N-grams
N-gram의 첫 번째 문제는 장기 의존성(Long-term dependency) 의 부재입니다. 이전에는 목표 토큰 이전에 있는 모든 토큰을 고려하여 목표 토큰의 확률을 계산하였습니다. 하지만 N-gram에서는 일부 단어 시퀀스의 횟수만을 가지고 판단하기 때문에 문장 앞쪽의 문맥을 고려하지 않은 채 토큰을 선택하게 됩니다.
위에서 사용했던 다른 예시를 다시 가져와 봅시다. “In Korea, more than half of residents speak Korean.” 와 “In Korea, more than half of residents speak Finnish.” 중 더 적절한 문장을 고르는 문제입니다. 마지막 단어 토큰을 선택할 때 이전에 위치한 모든 토큰을 고려한다면 당연히 “In Korea, more than half of residents speak Korean.” 를 선택할 것입니다. 말뭉치에 “In Korea, more than half of residents speak Korean.” 가 등장할 확률이 “In Korea, more than half of residents speak Finnish.” 가 등장할 확률보다는 높겠지요.
하지만 N-gram을 사용하면 어떻게 될까요? 다시 Bi-gram을 사용하는 경우를 생각해봅시다. 우리가 준비한 말뭉치에 “speak Finnish.” 라는 시퀀스가 “speak Korean.” 보다 많이 등장할 수 있습니다. 이렇게 된다면 충분히 “In Korea, more than half of residents speak Finnish.” 라는 사실과 다른 문장을 컴퓨터가 만들 수 있게 됩니다.
실제로 N-gram을 사용할 때는 $N=1 \sim 5$ 까지 여러 N-gram을 섞어 사용하여 이런 문제를 해결합니다. 의존성 분석(Dependency parsing)도 장기 의존성 문제를 해결하기 위한 방법입니다. 의존성 분석의 방법에는 Shift reduce parsing 과 같은 Transition-based Model과 토큰끼리의 의존성 구조를 그래프로 표현한 Graph-based Model이 있습니다.
이미지 출처 : researchgate.net
그런데 $N$ 을 $7,8$ 정도로 늘리면 장기 의존성 문제가 해결되지 않을까요? 그런데 왜 N을 증가시키지 않는 것일까요? $N$ 을 증가시키면 이전에 살펴보았던 희소성 문제가 부활하게 됩니다. 실제로 $N >= 7$ 인 N-gram에서는 대부분의 시퀀스 등장 확률이 0이 됩니다. 그리고 Bi-gram과 같이 짧은 단어 시퀀스에서도 희소성(Sparsity) 문제는 여전히 발생합니다.
예를 들어, “마라룽샤를 요리하다.” 라는 단어는 실제로 사용할 수 있는 단어이지만 실제로 많이 쓰는 단어는 아니기 때문에 우리가 학습에 사용할 말뭉치에 없을 수도 있습니다. “마라룽샤를 요리하다” 는 “컵을 요리하다”, “책꽂이를 요리하다” 와 달리 자연스러운 문장임에도 등장 확률은 0이 됩니다. N-gram 모델에서 발생하는 희소성 문제를 해결하기 위해서 스무딩(Smoothing) 과 백오프(Backoff) 라는 방법이 사용되고 있습니다.
스무딩은 발생 횟수가 0이 되지 않도록 단어 시퀀스의 출현 빈도를 보정해주는 방법입니다. 가장 기본적인 스무딩으로는 모든 단어 시퀀스의 출현 빈도에 작은 값을 더해주는 방법이 있습니다. 아래는 모든 단어 시퀀스의 출현 횟수에 $k$ 를 더해주는 스무딩을 수식으로 나타낸 것입니다.
\[P(w_i|w_{<i}) \approx \frac{\text{Count}(w_{<i},w_i) + k}{\text{Count}(w_{<i}) + kV} \approx \frac{\text{Count}(w_{<i},w_i) + (m/V)}{\text{Count}(w_{<i}) + m}\]백오프는 $p=0$ 이 되는 경우에만 $N$ 을 더 작게하는 방법입니다. 예를 들어, Bi-gram을 사용하면서 “마라룽샤를 요리하다” 가 없을 경우에는 Uni-gram을 사용하여 “마라룽샤를” 을 찾습니다. 백오프를 사용할 경우에는 보정을 위해서 Correction factor $\alpha, \beta$ 를 사용해줍니다. 수식으로 표현하면 아래와 같습니다.
\[c(x_{-N}, ... ,x) = \begin{cases}{\alpha}c(x_{-N+1}, ... ,x) + \beta \quad \text{if } c(x_{-N}, ... ,x) = 0 \\ c(x_{-N}, ... ,x) \qquad \qquad \text{ otherwise} \end{cases}\]가장 널리 사용되는 방법으로는 Kneser-Ney(KN) 스무딩 방법이 있습니다. 기본적인 아이디어는 목적이 되는 단어 $w$ 이전에 나타나는 단어 $v$ 가 얼마나 다양한 지를 알아내는 데에 있습니다. $v$ 가 클수록 말뭉치에서 나타나지 않는 단어 시퀀스가 될 가능성이 높기 때문입니다. KN 스무딩은 다음의 수식을 사용하여 단어가 나타날 확률 $P_{KN}$ 을 나타냅니다.
\[P_{KN} (w_i|w_{i-1}) = \frac{\max(\text{Count}(w_{i-1},w_i) - d,0)}{\text{Count}(w_i)} + \lambda(w_{i-1}) \times \text{Score}_{\text{continuation}}(w_i) \\ \begin{aligned} \text{where} \quad &\lambda(w_{i-1}) = \frac{d}{\sum_v \text{Count}(w_{i-1})} \times |\{w:c(w_{i-1},v) > 0\}| \\ &\text{Score}_{\text{continuation}}(w_i) = \frac{|\{v:\text{Count}(v,w) > 0\}|}{\sum_{w^{\prime}}|\{v:\text{Count}(v,w^{\prime}) > 0\}|} \end{aligned}\]위 식에서 $d$ 는 하이퍼파라미터이며 일반적으로는 0.75를 사용합니다. 또한 Score를 산출하는 식에서 $w^\prime$ 은 $v$ 뒤에 등장하는 다른 단어를 나타냅니다. KN 스무딩은 KenLM 패키지 내에 구현되어 있습니다.
Comments