마르코프 체인, 현재 상태만으로 미래를 예측하는 확률 모델

미래가 과거를 기억하지 않는다는 가정

Markov Chain(마르코프 체인)은 미래 상태의 확률이 현재 상태에만 의존하는 확률 과정(stochastic process)이다. 러시아 수학자 안드레이 마르코프(Andrey Markov)가 개발한 이 모델은 다음과 같은 특징을 갖는다.

Memoryless property(무기억성): 시스템의 다음 상태는 오직 현재 상태에만 의존하며, 과거 이력은 영향을 미치지 않음
Stationary transitions(정상 전이): 상태 간 전이 확률은 시간에 따라 변하지 않음
Discrete state space(이산 상태 공간): 유한한 수의 가능한 상태가 존재함

이러한 특성으로 인해 Markov Chain은 통신 네트워크, 금융 모델링, 자연어 처리, 생물학적 시스템 등 다양한 분야에서 활용된다.

상태 공간과 전이 확률로 구성하는 수학적 표현

Markov Chain은 다음과 같은 요소로 구성된다.

상태 공간(State Space) S = {s₁, s₂, ..., sₙ}: 시스템이 취할 수 있는 모든 가능한 상태의 집합
전이 확률(Transition Probability) P(Xₜ₊₁ = j | Xₜ = i): 현재 상태 i에서 다음 상태 j로 이동할 확률
전이 행렬(Transition Matrix) P: 모든 상태 간 전이 확률을 포함하는 행렬

전이 행렬 P는 다음과 같이 표현된다.

P = [p₁₁ p₁₂ ... p₁ₙ]
    [p₂₁ p₂₂ ... p₂ₙ]
    [  ...       ...]
    [pₙ₁ pₙ₂ ... pₙₙ]

여기서 pᵢⱼ는 상태 i에서 상태 j로 이동할 확률을 나타내며, 각 행의 합은 1이 된다(Σⱼ pᵢⱼ = 1).

방향 그래프로 그려보는 상태 전이

Markov Chain은 방향 그래프(directed graph)로 표현할 수 있다.

⤢✕

위 다이어그램에서 노드는 상태를, 에지는 전이 확률을 나타낸다. 예를 들어, 상태 A에서 상태 B로 전이할 확률은 0.2다.

상태를 재귀·일시·흡수로 나누는 기준

Markov Chain의 상태는 다음과 같이 분류된다.

Recurrent state(재귀 상태): 시스템이 이 상태로 반드시 돌아올 확률이 1인 상태
Transient state(일시 상태): 시스템이 이 상태로 돌아오지 않을 확률이 0보다 큰 상태
Absorbing state(흡수 상태): 일단 이 상태에 도달하면 다른 상태로 전이할 수 없는 상태 (pᵢᵢ = 1)

Markov Chain이 비환원적(Irreducible, 모든 상태에서 다른 모든 상태로 도달 가능함), 비주기적(Aperiodic, 상태로 돌아오는 경로의 길이가 특정 주기를 갖지 않음), 양의 재귀성(Positive recurrent, 모든 상태에서 평균 회귀 시간이 유한함)을 모두 만족할 때 ergodic(에르고딕)하다고 한다. Ergodic Markov Chain은 초기 상태와 무관하게 장기적으로 고유한 정상 분포(stationary distribution)에 수렴한다.

정상 분포로 수렴하는 지점

정상 분포 π는 π = π·P를 만족하는 확률 분포다. 이는 시스템이 충분히 오랜 시간 실행된 후 각 상태에 있을 확률을 나타낸다. Ergodic Markov Chain에서는 초기 상태와 무관하게 이 분포에 수렴한다.

통신 네트워크부터 금융 모델링까지, 마르코프 체인이 쓰이는 곳

통신 네트워크에서의 패킷 전송, 네트워크 트래픽, 서버 대기열 등을 모델링할 때 Markov Chain이 활용된다.

⤢✕

N-gram 모델과 같은 텍스트 생성 알고리즘에서는 단어나 문자 시퀀스의 확률적 모델링에 Markov Chain을 사용한다. 예를 들어 "오늘 날씨가" 다음에 올 단어의 확률은 "좋다" 0.6, "나쁘다" 0.3, "변덕스럽다" 0.1로 나타낼 수 있다.

주식 가격 변동, 이자율 변화, 신용 등급 전이 등을 모델링할 때도 Markov Chain이 사용된다. 신용 등급 전이 행렬 예시는 다음과 같다.

       AAA    AA     A     BBB    BB     B     CCC
AAA  [0.90  0.08  0.01  0.01   0.00  0.00  0.00]
AA   [0.02  0.85  0.10  0.02   0.01  0.00  0.00]
A    [0.00  0.05  0.85  0.07   0.02  0.01  0.00]
BBB  [0.00  0.00  0.08  0.80   0.08  0.03  0.01]
BB   [0.00  0.00  0.02  0.10   0.75  0.10  0.03]
B    [0.00  0.00  0.00  0.02   0.15  0.70  0.13]
CCC  [0.00  0.00  0.00  0.00   0.05  0.25  0.70]

유전자 발현, 단백질 구조 변화, 생태계 변화 등을 모델링할 때도 Markov Chain이 활용된다.

관측할 수 없는 상태를 다루는 은닉 마르코프 모델

Hidden Markov Model은 Markov Chain의 확장 개념으로, 시스템의 실제 상태는 관찰할 수 없고 오직 상태에 의해 생성된 출력만 관찰할 수 있는 모델이다.

HMM은 다음과 같은 요소로 구성된다.

Hidden states(은닉 상태) S = {s₁, s₂, ..., sₙ}: 직접 관찰할 수 없는 상태들
Observations(관측치) O = {o₁, o₂, ..., oₘ}: 관찰 가능한 출력값
Transition probabilities(전이 확률) A = {aᵢⱼ}: 상태 간 전이 확률
Emission probabilities(방출 확률) B = {bᵢ(k)}: 상태 i에서 관측치 k를 방출할 확률
Initial state probabilities(초기 상태 확률) π = {πᵢ}: 초기 상태의 확률 분포

⤢✕

HMM은 음성 인식, 필적 인식, 생물정보학 등 다양한 분야에서 활용된다.

표본을 뽑기 어려운 분포에서 샘플링하는 MCMC

MCMC는 복잡한 확률 분포로부터 샘플을 추출하는 알고리즘 계열로, 베이지안 통계에서 널리 사용된다. Metropolis-Hastings 알고리즘은 제안 분포를 사용하여 다음 상태 후보를 생성하고 수용 확률에 따라 이동 여부를 결정한다. Gibbs Sampling은 조건부 분포를 사용하여 각 변수를 순차적으로 샘플링한다. Hamiltonian Monte Carlo는 물리학의 해밀턴 역학을 활용하여 효율적으로 샘플링한다.

MCMC 방법은 고차원 통계 모델의 파라미터 추정, 복잡한 베이지안 네트워크의 추론 등에 활용된다.

무기억성 가정이 무너지는 지점

Markov Chain은 강력한 모델링 도구이지만 한계도 있다.

Memoryless 가정은 실제 시스템이 종종 과거 이력에 의존하는 경우가 많다는 점에서 제약이 된다. 정상성 가정, 즉 전이 확률이 시간에 따라 변하지 않는다는 가정도 항상 현실적이지는 않다. 복잡한 시스템에서는 상태 수가 기하급수적으로 증가하는 상태 폭발(State explosion) 문제가 발생할 수 있고, 대규모 시스템에서는 전이 확률을 정확히 추정하기 어렵다.

이러한 한계를 극복하기 위해 Variable-Order Markov Models, Partially Observable Markov Decision Processes(POMDP) 등의 확장 모델이 개발됐다.

단순한 가정으로 복잡한 시스템을 설명하는 힘

Markov Chain은 확률적 시스템을 모델링하는 강력한 수학적 도구로, 통신, 금융, 자연어 처리, 생물학 등 다양한 분야에서 활용되고 있다. 과거에 의존하지 않고 현재 상태만으로 미래를 예측한다는 단순한 가정에도 불구하고, 많은 실제 시스템을 효과적으로 모델링할 수 있다.

현대적인 확장 모델인 Hidden Markov Model과 Markov Chain Monte Carlo 방법은 Markov Chain의 기본 개념을 더욱 발전시켜, 더 복잡한 시스템과 문제를 해결하는 데 기여하고 있다.