April 6, 2025 6 min to read

NLP(2) - Shannon의 N-gram과 엔트로피란?

A Mathematical Theory of Communication 논문 리뷰

오늘은 앞선 포스팅에 이어 “A Mathematical Theory of Communication”에서 다룬 내용들을 계속 다루어보겠다.

저번 시간에는 정보량이란 ‘선택 가능한 경우의 수’에 의해 결정된다는 걸 배웠고, 모든 기호가 동일한 확률로 도착을 가정하면, 정보량은 log₂(모든 기호의 개수) bits로 표현된다는 것도 배웠다.

이 과정에서, 기호의 단위 시간이 다른 경우와 제약이 있는 경우에 정보량을 구하는 방법도 배웠다.

오늘 배울 내용은 조금 더 확장된 개념이다.

1. 메세지 vs 기호

앞의 포스트에서는 [점, 선, 문자 사이 공백, 단어 사이 공백]의 4가지 기호를 예시로 설정했다.

하지만 우리는 이 하나의 기호를 ‘메시지’라고 부르지 않는다. 왜냐하면, 예를 들어 [A, B, C … Z]라는 27개의 기호가 있을 때도, 보통은 한 글자 단위로 통신하지 않고, 여러 기호를 조합해 메시지를 전달하기 때문이다.

따라서 단일 기호가 가지는 정보량만 다루는 것이 아니라, 그 기호들의 조합, 즉 ‘메시지 전체의 정보량’을 분석할 수 있어야 한다.

앞에서 다룬 것처럼 그냥 전체 경우의 수에 log를 취하면 안되냐고? 아래를 읽어보자.

2. N-gram의 도입

자연어에서는 특이한 성질이 존재한다.

예를 들어, T-H-E 순서로 많이 나오고, I 다음에는 N이라는 기호가 많이 나오는 것처럼 모든 기호가 확률적으로 동일한 것이 아니라, 앞 글자에 의존적인 경향을 보인다.

이러한 상황에서 정보량을 단순히 ‘선택 가능한 경우의 수’로 나타내는 것에 한계가 생겼다.

THE나 IN 같은 단어가 가지는 정보량과 가끔 나오는 MINFLIX와 같은 단어가 가지는 정보량이 같다는 것은 인간 직관에도 다르기 때문이다.

즉, Shannon은 자연어의 이런 통계적인 경향을 모델링하고자 했다.

Shannon은 처음에는 기호의 확률을 모두 동일하게해서 무작위 생성을 시도했다. 이를 zero-order approximation이라고 하고, 다음과 같은 말도 안되는 문장이 나오게 된다.

그런데, 여기서 확률적 모델링을 도입하면 흥미로운 결과가 나온다.

First-order approximation은 확률을 기반하여 글자를 생성하게된다. 실제로 많이 나오지 않는 X,Y,Z가 줄어들고 확률적으로 많이 나오는 A,E,I,O,U의 빈도가 확 늘어나게된다.

Second-order approximation, Third-order approximation은 기호간 확률을 독립적이게 하지 않고, 앞 몇글자에 종속시키게 바꾼다. 예를 들어 Second-order은 앞 전글자에 영향을 받는 Digram 모델링을 하고, Third-order은 앞의 두 글자에 영향을 받는 Trigram으로 모델링을 하게 된다.

여기까지만 해도 충분히 처음보다 영어스러운(?) 문장이 나오게 된다.

이 성질은 기호 수준에서만 도입되는 것이 아니다. 자연어는 단어 간에도 확률적으로 종속되기 때문이다.

만약 앞 단어의 영향을 받아 Digram, Trigram으로 메세지를 생성하면 놀라운 결과가 나온다.

어떤가? 단어 수준의 Trigram 모델은 정말 있을 법한 영어 메세지를 만들어낸다!

Shannon은 이러한 확률적 특성을 반영한 N-gram 모델델의 작동 원리를 ‘정보원(source)’이라는 개념으로 설명했다.

3. 에르고딕 정보원

정보원이란, 메시지를 확률적으로 생성해내는 시스템을 말한다.

우리가 보고 듣는 문장들은 이 정보원이 만든 출력값이며, 그 내부에는 일정한 확률 구조와 규칙이 존재한다.

Shannon은 이 정보원의 구조를 설명하기 위해 마르코프 과정(Markov process)을 이용했다.

즉, 어떤 기호가 등장할 확률은 앞에서 나온 기호들(상태)에 의존하며, 이러한 조건부 확률이 전체 메시지 생성을 이끄는 방식이다.

정보원이 생성해내는 결과는 일련의 기호들로 이루어지며, 이를 시퀀스(sequence)라고 부른다.

예를 들어, “a b b c a b a a…” 와 같은 기호의 흐름이 하나의 시퀀스가 된다.

이 시퀀스는 실제로 우리가 전달하거나 해석하게 되는 메시지(message) 그 자체이며, Shannon은 이를 수학적으로 분석하기 위해 시퀀스라는 표현을 사용했다.

즉, 시퀀스 = 메시지라고 이해해도 무방하다.

그리고 이렇게 만들어진 정보원 중에서도, 특정한 통계적 성질을 가지는 정보원을 에르고딕 정보원(ergodic source)이라고 한다.

에르고딕 정보원은 충분히 긴 시퀀스를 관찰하면, 그 안에서 전체 정보원의 확률 구조가 드러나는 특징을 가진다.

논문의 표현을 빌리면, 정보원의 구조는 기호를 나타내는 상태(state)들을 노드로 하고, 기호 간 전이 확률은 방향성 엣지로 표현된다.

이 그래프에서 어떤 상태로부터 출발해, 방향성을 따라 다시 그 상태로 되돌아오는 경로를 회로(circuit)라고 하며, 그 회로에 포함된 엣지의 수를 길이(length)라고 한다.

그리고 그래프 내 모든 회로의 길이들의 최대공약수(GCD)가 1일 때, 이 정보원은 에르고딕(ergodic)하다고 정의된다.

(만약 GCD가 1보다 크면 시퀀스에 일정한 주기성이 생기고, 통계적으로 균일하지 않은 패턴이 반복되는데, 이는 논의에서 크게 중요하지 않아 Shannon도 생략한다.)

어떤 상태 \( i \)에 있을 확률을 \( P_i \), 그 상태에서 \( j \)로 전이될 확률을 \( p_i(j) \)라고 하자.

이 마르코프 과정이 정상 상태(stationary)가 되려면, 각 상태 \( j \)에 대한 평형 확률 \( P_j \)는 다음 조건을 만족해야 한다:

\[ P_j = \sum_i P_i \cdot p_i(j) \]

즉, 모든 상태로 들어오는 확률의 합 = 그 상태에 머무는 확률이 되어야 한다는 뜻이다. 이걸 정상 방정식(equilibrium condition) 또는 평형 조건이라 부른다.

여기서 에르고딕한 정보원이라면, 어떤 초기 상태에서 시작하더라도 상태 \( j \)에 있을 확률 \( P_j^{(N)} \)는 시퀀스가 충분히 길어질수록 자연스럽게 평형값 \( P_j \)로 수렴하게 된다:

\[ \lim_{N \to \infty} P_j^{(N)} = P_j \]

이는 확률론에서 말하는 큰수의 법칙(Law of Large Numbers)과 같은 의미를 가진다.

즉, 하나의 긴 시퀀스를 관찰하는 것만으로도 전체 정보원의 통계적 성질을 추정할 수 있으며, 시간 평균이 전체 평균과 일치하게 되는 구조인 것이다.

4. 혼합 정보원

에르고딕 정보원의 첫 번째 조건인 “모든 상태가 서로 연결되어 있어야 한다”가 위배되면, 그래프는 서로 연결되지 않은 여러 개의 부분 그래프(subgraph)로 나뉘게 된다.

이 경우 전체 정보원은 하나의 에르고딕 정보원이 아니라, 여러 개의 에르고딕한 부분 정보원(component sources)으로 구성되며,

Shannon은 이를 혼합 정보원(mixed source)이라고 정의했다.

혼합 정보원의 상태 확률은은 다음과 같이 정의된다:

\[ L = p_1 L_1 + p_2 L_2 + \cdots + p_n L_n \]

• \( L \): 전체 혼합 정보원
• \( L_k \): 각각의 에르고딕한 부분 정보원(component source)
• \( p_k \): 정보원 \( L_k \)가 선택될 확률 \((0 < p_k < 1,\ \sum p_k = 1)\)

이때 혼합 정보원 \( L \)에서 어떤 상태 \( j \)에 있을 확률 \( P_j \)는 다음과 같이 각 부분 정보원에서의 상태 확률을 가중 평균한 값으로 계산된다:

\[ P_j = \sum_k p_k \cdot P_j^{(k)} \]

• \( P_j^{(k)} \): 정보원 \( L_k \)에서 상태 \( j \)에 있을 확률

즉, 전체 상태 확률은 “어떤 정보원이 선택될지 모르는 상황에서의 평균적인 확률 구조”를 나타낸다.

한 번 어떤 정보원 ( L_k )가 선택되면, 그 이후의 시퀀스는 계속 해당 정보원의 확률 구조를 따르며 생성되기 때문에, 혼합 정보원은 하나의 에르고딕 정보원처럼 보이지만 실제로는 여러 확률 구조의 결합이라고 볼 수 있다.

그렇다면, 혼합 정보원이 에르고딕하지 않다는 사실은 왜 중요할까?

그 이유는, 현실의 대부분의 정보원이 본질적으로 에르고딕하지 않기 때문이다.

예를 들어 뉴스 기사, SNS 글, 학술 논문 등은 각기 다른 확률적 구조를 가진 정보원이라 할 수 있다.

Shannon은 이러한 현실의 복잡한 메시지 구조를 설명하기 위해, 에르고딕한 부분 정보원들을 섞은 혼합 정보원 모델을 제안함으로써, 현실 언어의 통계적 특성을 수학적으로 표현할 수 있게 하였다.

5. 엔트로피란?

다시 돌아와서, Shannon은 현실 세계의 언어와 메시지를 수학적으로 설명하기 위해 정보량을 새롭게 정의하고자 했다.

그는 현실의 메시지가 단순한 독립적인 기호들의 나열이 아니라, 이전 기호(혹은 단어)에 조건적으로 의존하는 구조를 가진다는 점에 주목했고, 이러한 특성을 반영하기 위해 Shannon은 N-gram 모델, 특히 혼합 정보원(mixed source) 형태의 마르코프 모델로 자연어를 모델링했다.

이제는 단순히 전체 경우의 수에 로그를 취하는 방식으로는 정보량을 설명할 수 없다.

왜냐하면 현실 세계의 메시지에서는 각 조합의 출현 확률이 제각각이기 때문이다.

Shannon은 이 문제를 해결하기 위해, 확률 분포 전체를 반영하는 새로운 정보량의 정의인 엔트로피(Entropy) 개념을 도입했다.

즉, 확률이 모두 같지 않은 현실 세계의 정보원에서는, 정보량 = 가능한 경우의 수가 아니라, 정보량 = 엔트로피로 계산된 평균적인 불확실성이 되어야 한다는 것이다.

\[ H = -\sum_{i=1}^{n} p_i \log_2 p_i \]

• \( H \): 전체 평균 정보량 (단위: bit)
• \( p_i \): 사건 \( i \)가 일어날 확률
• \( \log_2 p_i \): 사건 \( i \)가 일어났을 때의 정보량 (자주 나올수록 정보량은 작음)

이 식은 기존의 확률이 모두 동일한 경우의 정보량의 개념도 아래와 같이 포함한다.

\[ H = -\sum_{i=1}^{n} \frac{1}{n} \log_2 \frac{1}{n} = \log_2 n \]

또한, 혼합 정보원에서 에르고딕 정보원들의 가중합을 통해서 전체 정보원의 정보량(엔트로피)도 표현할 수 있다.

\[ H = \sum_i P_i \cdot H_i \]

• \( H \): 전체 혼합 정보원의 엔트로피
• \( H_i \): 정보원 \( L_i \)의 엔트로피
• \( P_i \): 정보원 \( L_i \)가 선택될 확률 \((\sum_i P_i = 1)\)

사실 논문에는 관련해서 많은 수학적 특성이 나오는데, 우리는 관련해서 스킵하도록 하겠다.

가장 중요한 부분은, 혼합 정보원도 충분히 긴 시퀀스를 생성하면, 마치 하나의 에르고딕 정보원처럼 안정적인 정보량(엔트로피)을 갖게 된다는 점이다. (증명은 생략)

즉, 따라서 Shannon은 이 성질을 통해 혼합 정보원도 평균 정보량을 기준으로 압축하거나 분석할 수 있다고 했다.

이제 NLP를 공부하기 위한 기본적인 개념(N-gram, 엔트로피)를 다 다루었다.

다음 시간은 Shannon은 N-gram 모델링을 코딩으로 실습해보는 시간을 가질 것이다.