7.4 이산 정보원과 마르코프 연쇄 모형

1. 이산 정보원의 정의

이산 정보원(discrete information source)은 유한한 기호 집합(알파벳) $\mathcal{A} = \{a_1, a_2, \ldots, a_q\}$ 으로부터 이산 시간 $t = 1, 2, 3, \ldots$ 에 따라 기호의 수열 $X_1, X_2, X_3, \ldots$ 을 생성하는 확률 과정(stochastic process)이다. 클로드 섀넌(Claude Shannon)은 “A Mathematical Theory of Communication“에서 정보원을 확률적 대상으로 모형화함으로써, 정보의 정량적 측정과 부호화의 이론적 한계를 도출하는 수학적 기반을 확립하였다.

이산 정보원의 완전한 통계적 기술은 임의 유한 길이 $n$ 에 대해 결합 확률 분포(joint probability distribution)를 명시하는 것이다:

$P(X_1 = x_1, X_2 = x_2, \ldots, X_n = x_n) \quad \text{for all } x_i \in \mathcal{A}, \; n \geq 1$

이 결합 분포가 정보원의 모든 통계적 성질을 결정한다. 그러나 일반적 경우에 이 분포를 완전히 기술하는 것은 매개변수의 수가 기호 수열의 길이에 대해 지수적으로 증가하므로 실용적이지 않다. 이러한 이유로 정보원의 통계적 구조에 대한 가정이 필요하며, 그 가장 기본적이고 중요한 가정이 마르코프 성질(Markov property)이다.

2. 이산 무기억 정보원

2.1 정의와 엔트로피

가장 단순한 이산 정보원 모형은 이산 무기억 정보원(discrete memoryless source, DMS)이다. 이 모형에서 각 시점의 기호 생성은 다른 모든 시점과 통계적으로 독립이며 동일한 분포를 따른다. 즉, 확률 변수 $X_1, X_2, \ldots$ 는 독립 동일 분포(i.i.d.)이다:

$P(X_1 = x_1, \ldots, X_n = x_n) = \prod_{i=1}^{n} P(X_i = x_i) = \prod_{i=1}^{n} p(x_i)$

여기서 $p(a_j) = P(X_i = a_j)$ 는 기호 $a_j$ 의 출현 확률이다.

DMS의 엔트로피는 다음과 같이 정의된다:

$H(X) = -\sum_{j=1}^{q} p(a_j) \log_2 p(a_j)$

$n$ 개 기호로 이루어진 수열의 결합 엔트로피는 독립성에 의해 $H(X_1, X_2, \ldots, X_n) = nH(X)$ 이다. 따라서 기호 당 평균 엔트로피, 즉 엔트로피율(entropy rate)은 $H(X)$ 자체이다.

2.2 무기억 가정의 한계

무기억 가정은 수학적으로 편리하나, 현실의 정보원을 모형화하는 데 있어 심각한 한계를 가진다. 자연어 텍스트를 예로 들면, 영어에서 문자 ‘q’ 다음에는 거의 항상 ’u’가 뒤따르며, ’th’라는 이중자(digram) 뒤에는 ‘e’, ‘a’, ‘i’ 등의 모음이 높은 빈도로 출현한다. 이러한 기호 간 의존 구조는 무기억 모형에서는 포착할 수 없다.

섀넌은 이 점을 명확히 인식하고, 기호 간 통계적 의존성을 체계적으로 모형화하기 위한 도구로 마르코프 연쇄를 도입하였다.

3. 마르코프 연쇄의 수학적 기초

3.1 마르코프 성질의 정의

마르코프 연쇄(Markov chain)는 마르코프 성질을 만족하는 확률 과정이다. $m$ 차 마르코프 성질은 현재 상태의 조건부 확률이 직전 $m$ 개의 상태에만 의존하고, 그 이전의 이력에는 의존하지 않음을 의미한다:

$P(X_n = x_n \mid X_{n-1} = x_{n-1}, \ldots, X_1 = x_1) = P(X_n = x_n \mid X_{n-1} = x_{n-1}, \ldots, X_{n-m} = x_{n-m})$

$m = 1$ 인 경우, 1차 마르코프 연쇄(first-order Markov chain)가 되며, 이는 가장 기본적이고 널리 사용되는 형태이다:

$P(X_n = x_n \mid X_{n-1} = x_{n-1}, \ldots, X_1 = x_1) = P(X_n = x_n \mid X_{n-1} = x_{n-1})$

3.2 전이 확률 행렬

1차 마르코프 연쇄의 통계적 구조는 전이 확률 행렬(transition probability matrix) $\mathbf{P}$ 에 의해 완전히 결정된다. 행렬의 $(i, j)$ 원소는 상태 $a_i$ 에서 상태 $a_j$ 로의 전이 확률을 나타낸다:

$P_{ij} = P(X_n = a_j \mid X_{n-1} = a_i)$

전이 확률 행렬은 다음의 두 성질을 만족한다:

비음성: $P_{ij} \geq 0$ for all $i, j$
행 합이 1: $\sum_{j=1}^{q} P_{ij} = 1$ for all $i$

이러한 행렬을 확률 행렬(stochastic matrix) 또는 마르코프 행렬이라 한다.

시간에 따라 전이 확률이 변하지 않는 경우, 즉 $P(X_n = a_j \mid X_{n-1} = a_i)$ 가 $n$ 에 무관할 때, 시간 동차적(time-homogeneous) 마르코프 연쇄라 한다. 섀넌의 정보 이론에서 다루는 마르코프 정보원은 일반적으로 시간 동차적이다.

3.3 정상 분포와 에르고드 성질

마르코프 연쇄의 장기적 행동을 결정하는 핵심 개념은 정상 분포(stationary distribution)이다. 확률 벡터 $\boldsymbol{\pi} = (\pi_1, \pi_2, \ldots, \pi_q)$ 가 다음을 만족할 때, $\boldsymbol{\pi}$ 를 마르코프 연쇄의 정상 분포라 한다:

$\boldsymbol{\pi} \mathbf{P} = \boldsymbol{\pi}, \quad \sum_{j=1}^{q} \pi_j = 1, \quad \pi_j \geq 0$

즉, 정상 분포는 전이 확률 행렬 $\mathbf{P}$ 의 고유값 1에 대응하는 좌고유벡터(left eigenvector)이다.

마르코프 연쇄가 기약적(irreducible)이고 비주기적(aperiodic)일 때, 유일한 정상 분포가 존재하며, 초기 상태에 무관하게 연쇄의 상태 분포는 $n \to \infty$ 에서 정상 분포에 수렴한다:

$\lim_{n \to \infty} P(X_n = a_j) = \pi_j \quad \text{for all } j$

기약성은 임의의 상태에서 다른 임의의 상태로 유한 단계 내에 도달할 수 있음을 의미하고, 비주기성은 상태 방문의 주기가 1임을 의미한다. 이 두 조건을 동시에 만족하는 마르코프 연쇄를 에르고드 마르코프 연쇄(ergodic Markov chain)라 한다.

에르고드 마르코프 연쇄는 에르고드 정리(ergodic theorem)를 만족한다. 시간 평균이 앙상블 평균과 일치한다는 이 성질은, 정보원이 충분히 긴 수열을 생성할 때 그 수열의 통계적 성질이 정상 분포에 의해 결정됨을 보장하며, 정보원의 엔트로피율이 잘 정의됨을 보장한다.

4. 마르코프 정보원의 엔트로피율

4.1 엔트로피율의 정의

정보원의 엔트로피율(entropy rate)은 기호 당 평균 정보량의 극한으로 정의된다:

$\mathcal{H} = \lim_{n \to \infty} \frac{1}{n} H(X_1, X_2, \ldots, X_n)$

에르고드 정상 마르코프 연쇄에서 이 극한이 존재하며, 동등한 표현으로 다음이 성립한다:

$\mathcal{H} = \lim_{n \to \infty} H(X_n \mid X_{n-1}, X_{n-2}, \ldots, X_1)$

4.2 차 마르코프 정보원의 엔트로피율 계산

1차 마르코프 정보원에서 마르코프 성질에 의해 $H(X_n \mid X_{n-1}, \ldots, X_1) = H(X_n \mid X_{n-1})$ 이 성립한다. 따라서 정상 상태에서 엔트로피율은 다음과 같이 계산된다:

$\mathcal{H} = H(X_n \mid X_{n-1}) = -\sum_{i=1}^{q} \pi_i \sum_{j=1}^{q} P_{ij} \log_2 P_{ij}$

이 식은 각 상태 $a_i$ 에서의 조건부 엔트로피 $H_i = -\sum_j P_{ij} \log_2 P_{ij}$ 를 정상 분포 $\pi_i$ 로 가중 평균한 것이다:

$\mathcal{H} = \sum_{i=1}^{q} \pi_i H_i$

마르코프 정보원의 엔트로피율은 항상 동일한 정상 분포를 가지는 무기억 정보원의 엔트로피 이하이다. 이는 기호 간 통계적 의존성이 불확실성을 감소시키기 때문이다. 형식적으로:

$\mathcal{H}_{\text{Markov}} = H(X_n \mid X_{n-1}) \leq H(X_n) = H_{\text{DMS}}$

이 부등식은 조건화가 엔트로피를 감소시킨다는 일반적 성질 $H(X \mid Y) \leq H(X)$ 의 직접적 결과이다.

4.3 고차 마르코프 정보원으로의 확장

$m$ 차 마르코프 정보원의 엔트로피율은 다음과 같이 표현된다:

$\mathcal{H} = H(X_n \mid X_{n-1}, X_{n-2}, \ldots, X_{n-m})$

$m$ 차 마르코프 연쇄는 상태 공간을 확장하여 1차 마르코프 연쇄로 변환할 수 있다. 길이 $m$ 의 기호 블록 $(X_{n-m+1}, \ldots, X_n)$ 을 하나의 상태로 정의하면, 확장된 상태 공간 $\mathcal{A}^m$ 위에서 1차 마르코프 연쇄가 구성된다. 확장된 상태 공간의 크기는 $q^m$ 이므로, 차수 $m$ 이 증가함에 따라 모형의 매개변수 수가 지수적으로 증가한다.

5. 섀넌의 영어 텍스트 근사 실험

5.1 정보원의 계층적 근사

섀넌은 “A Mathematical Theory of Communication“에서 영어 텍스트를 다양한 차수의 마르코프 모형으로 근사하는 실험을 제시하였다. 이 실험은 마르코프 차수의 증가에 따라 생성되는 텍스트가 자연어에 점진적으로 접근하는 양상을 시각적으로 보여주며, 정보원의 통계적 구조가 텍스트의 성격을 결정함을 직관적으로 입증하였다.

0차 근사(독립 균등 분포): 알파벳의 27개 기호(26문자 + 공백)가 동등한 확률로 무작위 선택된다. 결과물은 무의미한 기호 나열이다.

1차 근사(독립 비균등 분포): 각 문자의 출현 빈도가 영어 텍스트의 실제 빈도에 일치하도록 독립 생성된다. ’e’와 ’t’가 빈번히 출현하지만 문자 간 조합은 비자연적이다.

2차 근사(1차 마르코프): 이전 문자가 주어졌을 때 다음 문자의 조건부 확률이 영어의 이중자(digram) 빈도에 일치한다. ‘th’, ‘he’, ‘in’ 등의 자연스러운 이중자가 출현하기 시작한다.

3차 근사(2차 마르코프): 이전 두 문자가 주어졌을 때의 조건부 확률을 사용한다. 삼중자(trigram) 수준의 영어 구조가 반영되어, 영어 단어와 유사한 기호열이 빈번히 생성된다.

마르코프 차수가 증가할수록 생성 텍스트는 자연어에 가까워지며, 동시에 엔트로피율은 감소한다. 이는 더 긴 맥락 정보를 활용할수록 다음 기호에 대한 불확실성이 줄어들기 때문이다.

5.2 영어의 엔트로피 추정

섀넌은 영어 텍스트의 엔트로피율을 추정하기 위한 실험을 수행하였다. 인간 피험자에게 영어 텍스트의 다음 문자를 예측하게 하고, 예측 성공률로부터 엔트로피의 상한과 하한을 추정하였다. 이 방법을 통해 섀넌은 영어의 엔트로피율이 문자 당 약 1.0~1.5비트임을 추정하였다.

영어 알파벳이 27개 기호를 가지므로, 균등 분포 가정 하의 엔트로피는 $\log_2 27 \approx 4.76$ 비트/문자이다. 실제 엔트로피율이 이보다 훨씬 낮다는 사실은 영어 텍스트가 상당한 잉여성(redundancy)을 가짐을 의미한다. 잉여성 비율은 대략 $1 - \mathcal{H}/\log_2 27 \approx 70\text{--}80\%$ 로 추정되며, 이는 영어 텍스트의 약 70~80%가 언어의 통계적 구조에 의해 예측 가능한 부분임을 나타낸다.

6. 마르코프 모형과 현대 언어 모형의 관계

섀넌이 도입한 마르코프 정보원 모형은 현대 자연어 처리(natural language processing)에서 사용되는 통계적 언어 모형(statistical language model)의 직접적 선구이다. $n$ -그램 언어 모형( $n$ -gram language model)은 $(n-1)$ 차 마르코프 가정 하에서 다음 단어의 조건부 확률을 추정하는 것으로, 섀넌의 마르코프 정보원 모형의 단어 수준 적용이다.

현대의 대규모 언어 모형은 고정된 차수의 마르코프 가정을 넘어, 임의 길이의 맥락을 처리할 수 있는 구조를 가진다. 그러나 정보원의 확률적 모형화, 엔트로피율의 개념, 교차 엔트로피에 의한 모형 성능 평가 등 섀넌이 확립한 이론적 틀은 현대 언어 모형의 분석에서도 핵심적 도구로 기능한다.

마르코프 정보원 모형의 역사적 의의는 단순한 모형 자체에 있는 것이 아니라, 정보원을 확률 과정으로 모형화하고 그 통계적 구조를 엔트로피율로 정량화하는 방법론을 확립한 데 있다. 이 방법론은 정보원의 구체적 모형(무기억, 마르코프, 또는 보다 복잡한 확률 과정)에 무관하게 적용되는 보편적 분석 틀이다.