[기계학습개론] Sequential Learning - Hidden Markov Model(Viterbi, Forward-Backward, Baum-Welch algorithm)

시퀀스 데이터의 비밀을 푸는 열쇠: Sequential Learning과 Hidden Markov Model (HMM) 완벽 정복 🗝️

지난 시간에는 제한된 라벨링 데이터로 모델 성능을 극대화하는 Active Learning에 대해 깊이 있게 탐구해 보았다. 이번에는 또 다른 머신러닝의 중요 갈래인 Sequential Learning (순차적 학습)에 대해 알아보고자 한다. 이름에서 알 수 있듯, Sequential Learning은 입력 데이터가 시간 순서나 특정 순서를 가진 시퀀스(sequence) 형태로 주어지고, 그에 대한 출력 역시 시퀀스인 문제를 다루는 핵심 분야이다.

가장 대표적인 예시로 개체명 인식 (Named Entity Recognition, NER)을 들 수 있다. NER은 "어제 페드로 도밍고스가 뉴욕으로 떠났다 (Yesterday Pedro Domingos flew to New York)"와 같은 문장 시퀀스에서 "페드로 도밍고스"를 '사람 이름'으로, "뉴욕"을 '장소 이름'으로 식별하고 분류하는 작업이다. 여기서 핵심은 각 단어(토큰)를 독립적으로 보는 것이 아니라, "페드로" 다음에 "도밍고스"가 올 가능성, "뉴욕"이라는 장소명 앞뒤에 올 수 있는 단어 패턴 등 시퀀스 내 요소들 간의 상호 의존성을 파악하는 것이다. 예를 들어, NER 레이블에서 'I-PER' (사람 이름의 중간 또는 끝 부분) 레이블은 보통 'B-PER' (사람 이름의 시작 부분) 레이블 다음에 나타나는 강력한 순차적 경향성을 보인다. 이러한 복잡한 의존성을 모델링하는 데 아주 강력하고 고전적인 프레임워크가 바로 *Hidden Markov Model (HMM)이다.

NER by Classifying Tokens

순차적 의존성의 첫걸음: 마르코프 모델 (Markov Model) 🐾

HMM의 심오한 세계로 들어가기 전에, 그 기초가 되는 마르코프 모델부터 확실히 짚고 넘어가야 한다.

가장 단순한 형태의 시퀀스 모델은 모든 관측치(observation)가 서로 독립(independent)이라고 가정한다. 이는 마치 내일 비가 올 확률을 계산할 때, 어제 그제 날씨는 전혀 고려하지 않고 오로지 과거에 비가 왔던 날들의 단순 빈도만으로 판단하는 것과 같다. 당연히 현실의 많은 시퀀스 데이터는 이러한 가정을 만족하지 못한다.

Simplest Model for Sequential Data

마르코프 모델은 이러한 한계를 넘어 시퀀스 내 관측치들 간의 의존성을 모델링한다. 특히 1차 마르코프 모델 (1st Order Markov Model)은 현재 시점 t의 상태(state) St의 확률 분포가 바로 직전 시점 t−1의 상태 St−1에만 의존하고, 그 이전의 과거 상태들 (St−2,St−3,...)과는 독립이라고 가정한다. 이를 마르코프 가정 (Markov assumption)이라 한다.

First Order Markov Model

수학적으로, 길이가 n인 상태 시퀀스 $S_{1}, S_{2}, . . ., S_{n}$ 에 대한 결합 확률 분포는 다음과 같이 표현된다:

$P (S_{1}, S_{2}, . . ., S_{n}) = P (S_{1}) \prod_{t = 2}^{n} P (S_{t} | S_{t - 1})$

날씨 예시를 다시 생각해보자. 오늘의 날씨 상태(비, 흐림, 맑음)가 내일의 날씨 상태로 어떻게 변할지, 즉 상태 전이 확률(transition probability)을 모델링할 수 있다. 예를 들어, 오늘 비가 왔을 때( $S_{t o d a y} = R a i n$ ) 내일도 비가 올 확률( $S_{t o m o r r o w} = R a i n$ )은 $P (S_{t o m o r r o w} = R a i n | S_{t o d a y} = R a i n) = 0.3$ 과 같이 정의된다.

Markov Model

만약 "맑음-맑음-비-비-맑음-흐림-맑음" (S-S-R-R-S-C-S)과 같은 7일간의 특정 날씨 시퀀스가 나타날 확률은 각 전이 확률을 순서대로 곱하여 간단히 계산할 수 있다. 하지만, 만약 첫날 날씨가 "맑음(S)"일 때, 3일 후의 날씨가 어떠할 확률을 알고 싶다면 어떻게 해야 할까? 이 경우, 첫날이 S일 때 3일째에 도달 가능한 모든 날씨 경로(S→S→S, S→S→C, S→S→R, ..., S→R→R)의 확률을 각각 계산하여 모두 더해야 한다. 날씨 상태가 3가지(N=3)라고 할 때, 3일 후(t=3)의 날씨를 예측하기 위해서는 총 $N^{t} = 3^{3} = 27$ 가지 경로를 고려해야 한다. 시퀀스 길이가 길어지면 이 계산량은 기하급수적으로 폭증한다 ( $O (N^{t})$ ).

Computational Limitation of Markov Model

이러한 계산 복잡성 문제를 해결하는 것이 바로 동적 계획법 (Dynamic Programming)이다. 동적 계획법은 반복되는 하위 문제(subproblem)의 결과를 저장하고 재활용하여 계산량을 획기적으로 줄인다. 1차 마르코프 모델에서 동적 계획법을 적용하면, 특정 시점 t에 각 상태 k에 도달할 총 확률을 효율적으로 계산할 수 있으며, 전체 계산 복잡도를 $O (N^{t})$ 에서 $O (N^{2} t)$ 로 낮출 수 있다. (각 시점 t마다 N개 상태에 대해, 각 상태는 이전 N개 상태로부터 전이될 수 있으므로 $N \times N = N^{2}$ 연산, 이를 t번 반복).

물론, 현재 상태가 직전 두 개의 상태에 의존하는 2차 마르코프 모델처럼 더 긴 범위의 의존성을 포착하는 모델도 존재한다.

Second Order Markov Model

숨겨진 상태를 찾아서: 은닉 마르코프 모델 (Hidden Markov Model, HMM) 🕵️‍♀️

마르코프 모델은 상태 시퀀스 자체가 직접 관측되는 경우를 다룬다. 반면, 은닉 마르코프 모델 (HMM)은 우리가 직접 관측하는 시퀀스(observations, xt)와는 별개로, 관측되지 않는 '숨겨진(hidden)' 상태 시퀀스 (St)가 존재한다고 가정하고 이 숨겨진 상태를 모델링한다.

날씨 예시를 확장해보자. 우리는 친구가 매일 어떤 활동(산책, 쇼핑, 독서 등)을 하는지는 관측할 수 있지만 (xt), 그날의 실제 날씨(St)는 직접 보지 못한다고 가정하자. 이때 HMM은 관측된 활동 시퀀스를 통해 숨겨진 날씨 상태 시퀀스를 추론하는 데 사용될 수 있다.

Hidden Markov Model

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

숨겨진 상태 (Hidden States) $S = {\begin{matrix} S_{1}, S_{2}, . . ., S_{N} \end{matrix}}$ : 모델 내부의 관측 불가능한 상태들의 집합 (예: 날씨 - 맑음, 흐림, 비).
관측 심볼 (Observation Symbols) $X = {\begin{matrix} x_{1}, x_{2}, . . ., x_{M} \end{matrix}}$ : 각 시점에서 관측 가능한 값들의 집합 (예: 활동 - 산책, 쇼핑, 독서).
초기 상태 확률 (Initial State Probabilities) $π = {\begin{matrix} π_{i} \end{matrix}} : π_{i} = P (S_{1} = s_{i})$ , 시퀀스가 시작될 때 각 숨겨진 상태 si에서 시작할 확률.
상태 전이 확률 (State Transition Probabilities) $A = {\begin{matrix} a_{i j} \end{matrix}} : a_{i j} = P (S_{t} = s_{j} | S_{t - 1} = s_{i})$ , 현재 숨겨진 상태 si에서 다음 숨겨진 상태 sj로 전이될 확률.
방출 확률 (Emission Probabilities) $B = {\begin{matrix} b_{j} (k) \end{matrix}} : b_{j} (k) = P (x_{t} = x_{k} | S_{t} = s_{j})$ , 현재 숨겨진 상태 sj에서 특정 관측 심볼 xk가 나타날 확률.

HMM은 다음과 같은 생성 과정(generative process)으로 설명할 수 있다:

초기 상태 확률 π에 따라 첫 번째 숨겨진 상태 $S_{1}$ 을 선택한다.
현재 상태 $S_{1}$ 에서 방출 확률 B에 따라 관측치 $x_{1}$ 을 방출(emit)한다.
상태 전이 확률 A에 따라 다음 숨겨진 상태 $S_{2}$ 로 전이한다.
현재 상태 $S_{2}$ 에서 관측치 $x_{2}$ 를 방출한다.
시퀀스 길이만큼 위 3, 4단계를 반복한다.

HMM 파라미터 학습 (Training):

주어진 훈련 데이터(예: NER에서 단어 시퀀스와 해당 개체명 레이블 시퀀스)를 사용하여 HMM의 파라미터 (π,A,B)를 추정한다. 훈련 데이터가 (관측 시퀀스, 숨겨진 상태 시퀀스) 쌍으로 완벽히 레이블링 되어 있다면 (supervised learning), 파라미터 추정은 비교적 간단하다. 각 상태 전이 및 방출의 횟수를 세어 확률을 계산하면 된다.

$a_{i j} = P (S_{t} = s_{j} | S_{t - 1} = s_{i}) = \frac{t h e n u m b e r o f t r a n s i t i o n f r o m s_{i} t o s_{j}}{t o t a l n u m b e r o f t r a n s i t i o n o f s_{i}}$
$b_{j} (k) = P (x_{t} = x_{k} | S_{t} = s_{j}) = \frac{t h e n u m b e r o f e m i t e d x_{k} f r o m s_{j}}{t o t a l n u m b e r o f s_{j}}$

하지만 숨겨진 상태가 주어지지 않은, 관측 시퀀스만 있는 경우(unsupervised learning)에는 Baum-Welch 알고리즘을 사용한다 (뒤에서 설명).

Testing Stage of HMM

HMM의 핵심 문제와 알고리즘 🧠

HMM의 파라미터 ( $λ = (A, B, π)$ )가 주어졌다고 가정할 때, 우리는 주로 다음과 같은 문제들을 풀고자 한다.

1. 디코딩 문제 (Decoding Problem) & 비터비 알고리즘 (Viterbi Algorithm)

문제: 주어진 관측 시퀀스 $X = {\begin{matrix} x_{1}, x_{2}, . . ., x_{T} \end{matrix}}$ 에 대해, 이 관측 시퀀스를 생성했을 가능성이 가장 높은 (most probable) 숨겨진 상태 시퀀스 $S^{*} = {\begin{matrix} S_{1}^{*}, S_{2}^{*}, . . ., S_{T}^{*} \end{matrix}}$ 를 찾는 문제.
$S^{*} = a r g m a x_{{\begin{matrix} S_{1}^{*}, S_{2}^{*}, . . ., S_{T}^{*} \end{matrix}}} P (S_{1}, . . . S_{T} | x_{1}, . . . x_{T}, λ)$
NER에서는 관측된 단어 시퀀스에 대해 가장 확률이 높은 개체명 레이블(숨겨진 상태) 시퀀스를 찾는 것에 해당한다.
해결책: 비터비 알고리즘 (Viterbi Algorithm)
이 문제는 동적 계획법을 사용하는 비터비 알고리즘으로 효율적으로 풀 수 있다. 비터비 알고리즘은 각 시점 t에서 각 숨겨진 상태 $s_{k}$ 에 도달하는 가장 확률이 높은 경로와 그 경로의 확률을 계산한다.
- $V_{t} (k)$ : 시점 t에서 상태 $s_{k}$ 로 끝나면서 관측 시퀀스 x1,...,xt를 생성하는 가장 확률 높은 경로의 확률.
- $p t r_{t} (k)$ : 시점 t에서 상태 $s_{k}$ 로 도달하는 최적 경로의 직전 시점 $t - 1$ 에서의 상태.
1. 초기화 (Initialization, t=1): 각 상태 $s_{k}$ 에 대해, $V_{1} (k) = π_{k} \cdot b_{k} (x_{1})$
$p t r_{1} (k) = 0$ (시작이므로 이전 상태 없음)

Initialization

2. 재귀 (Recursion, t=2,...,T):
각 상태 $s_{k}$ (다음 상태)에 대해,
$V_{t} (k) = m a x_{s_{j} \in S} {\begin{matrix} V_{t - 1} (j) \cdot a_{j k} \end{matrix}} \cdot b_{k} (x_{t})$
$p t r_{t} (k) = a r g m a x_{s_{j} \in S} {\begin{matrix} V_{t - 1} (j) \cdot a_{j k} \end{matrix}}$
즉, $V_{t} (k) = P (x_{t} | S_{t} = s_{k}) \cdot m a x_{s_{j} \in S} {\begin{matrix} P (S_{t} = s_{k} | S_{t - 1} = s_{j}) \cdot V_{t - 1} (j) \end{matrix}}$
그리고 $p t r_{t} (k) = a r g m a x_{s_{j} \in S} {\begin{matrix} P (x_{t} | S_{t} = s_{k}) \cdot P (S_{t} = s_{k} | S_{t - 1} = s_{j}) \cdot V_{t - 1} (j) \end{matrix}}$
(여기서 $P (x_{t} | S_{t} = s_{k})$ 는 $b_{k} (x_{t})$ 이고 $P (S_{t} = s_{k} | S_{t - 1} = s_{j})$ 는 $a_{j k}$ 이다.)

Recursion

3. 종료 (Termination):
가장 확률이 높은 전체 시퀀스의 확률 $P^{*} = m a x_{s_{k} \in S} {\begin{matrix} V_{T} (k) \end{matrix}}$
마지막 상태 $S_{T}^{*} = a r g m a x_{s_{k} \in S} {\begin{matrix} V_{T} (k) \end{matrix}}$
Termination

4. 경로 역추적 (Path Backtracking):
t=T−1,...,1 에 대해,
$S_{t}^{*} = p t r_{t + 1} (S_{t + 1}^{*})$

날씨/활동 예시에서, 관측된 활동 시퀀스 ('산책', '쇼핑', '독서')가 주어졌을 때, 비터비 알고리즘은 각 시점마다 각 날씨 상태(비, 흐림, 맑음)로 끝나는 가장 확률 높은 경로의 확률을 계산하고, 최종적으로 가장 가능성 있는 전체 날씨 시퀀스를 찾아낸다.

2. 추론 문제 (Inference Problem) & 전후진 알고리즘 (Forward-Backward Algorithm)

문제: 주어진 관측 시퀀스 $X = (x_{1}, . . . x_{T})$ 와 HMM 파라미터 λ에 대해, 특정 시점 j에서 숨겨진 상태가 $s_{k}$ 일 확률 $P (S_{j} = s_{k} | X, λ)$ 를 찾는 문제. 이는 개별 토큰에 대한 최적의 레이블을 결정하거나, 특정 상태일 확률 자체를 분석하는 데 사용될 수 있다.
해결책: 전후진 알고리즘 (Forward-Backward Algorithm)
이 또한 동적 계획법을 활용하며, "Forward" 패스와 "Backward" 패스로 구성된다.

Initialization

recursion

Initialization

recursion

결합:
특정 시점 j에서 상태가 $s_{k}$ 일 확률은 다음과 같이 계산된다:
$P (S_{j} = s_{k} | X, λ) = \frac{α_{j} (k) \cdot β_{j} (k)}{P (X | λ)} = \frac{α_{j} (k) \cdot β_{j} (k)}{\sum_{s_{i} \in S} α_{j} (i) \cdot β_{j} (i)}$
분모 $P (X | λ) = \sum_{s_{k} \in S} α_{T} (k)$ 는 주어진 관측 시퀀스 X가 나타날 전체 확률로, 평가 문제(Evaluation Problem)의 답이기도 하다.

Forward-Backward 알고리즘은 주소 파싱, 인용문 파싱과 같은 순차 데이터 구조 인식 문제에 효과적으로 응용될 수 있다.

Forward-Backward Algorithm

3. 비지도 학습과 바움-웰치 알고리즘 (Baum-Welch Algorithm)

문제: HMM의 파라미터 (π,A,B)가 주어지지 않고, 숨겨진 상태 시퀀스도 레이블링되지 않은 오직 관측 시퀀스 X만 주어진 경우 (unsupervised learning), 어떻게 HMM 파라미터를 학습할 수 있을까?
해결책: 바움-웰치 알고리즘 (Baum-Welch Algorithm)
이 알고리즘은 EM (Expectation-Maximization) 알고리즘의 특별한 형태로, 관측된 데이터 X의 가능도(likelihood) P(X∣λ)를 최대화하는 HMM 파라미터 λ를 반복적으로 추정한다.
초기화 (Initialization): HMM 파라미터 $λ = (A, B, π)$ 를 임의의 값으로 (또는 사전 지식을 활용하여) 초기화한다.
반복 (Iteration): 파라미터가 수렴할 때까지 다음 E-step과 M-step을 반복한다.

E-step (Expectation): 현재 파라미터 λ를 사용하여 Forward-Backward 알고리즘을 실행한다. 이를 통해 두 가지 중요한 값을 계산한다:
- $γ_{t} (i) = P (S_{t} = s_{i} | X, λ)$ : 시점 t에서 상태가 $s_{i}$ 일 확률.
- $ϵ_{t} (i, j) = P (S_{t} = s_{i}, S_{t + 1} = s_{j} | X, λ)$ : 시점 $t$ 에서 상태가 $s_{i}$ 이고 시점 $t + 1$ 에서 상태가 $s_{j}$ 일 확률 (기대 전이 횟수).
  $ϵ_{t} (i, j) = \frac{α_{t} (i) \cdot a_{i j} \cdot b_{j} (x_{t + 1}) \cdot β_{t + 1} (j)}{P (X | λ)}$
M-step (Maximization): E-step에서 계산된 기댓값을 사용하여 파라미터를 업데이트한다.

초기 상태 확률: $\hat{π_{i}} = γ_{1} (i)$
상태 전이 확률: $\hat{a_{i j}} = \frac{\sum_{t = 1}^{T - 1} ε_{t} (i, j)}{\sum_{t = 1}^{T - 1} γ_{t} (i)}$
방출 확률: $\hat{b_{j} (k)} = \frac{\sum_{t = 1, s . t . x_{t} = x_{k}}^{T} γ_{t} (j)}{\sum_{t = 1}^{T} γ_{t} (j)}$ (관측 심볼 $x_{k}$ 에 대한 방출 확률)

Baum-Welch 알고리즘은 국소 최적값(local optimum)으로 수렴하는 것이 보장되며, 레이블 없는 순차 데이터를 사용하여 HMM의 내부 구조와 확률 분포를 효과적으로 학습할 수 있게 해준다.

결론: 순차적 데이터 분석의 강력한 무기 🎯

Sequential Learning은 시퀀스 데이터 내에 숨겨진 복잡한 의존성을 파악하고 모델링하는 머신러닝의 핵심 분야이다. Hidden Markov Model은 이러한 문제를 해결하기 위한 강력하고 유연한 확률적 모델을 제공하며, 그 이면에는 깊이 있는 수학적 원리들이 자리 잡고 있다.

Viterbi 알고리즘은 주어진 관측치에 대해 가장 가능성 있는(최종) 숨겨진 상태 시퀀스를 찾아내는 디코딩 문제를 해결하고,
Forward-Backward 알고리즘은 특정 시점의 숨겨진 상태 확률을 계산하는 추론 문제를 동적 계획법으로 효율적으로 풀어낸다.
마지막으로, Baum-Welch 알고리즘은 레이블이 없는 데이터로부터 HMM의 파라미터를 학습하는 비지도 학습의 길을 열어준다.

이러한 기법들은 음성 인식, 자연어 처리(개체명 인식, 품사 태깅 등), 생물정보학(DNA 서열 분석 등), 금융 시계열 분석 등 광범위한 분야에서 순차적 데이터를 이해하고 예측하는 데 필수적인 도구로 활용되고 있다.

이번 학습을 통해 마르코프 모델의 기본 개념부터 HMM의 구조, 그리고 HMM과 관련된 세 가지 핵심 알고리즘의 작동 원리까지 상세히 살펴볼 수 있었다. Sequential Learning의 세계는 알면 알수록 흥미로운 주제들로 가득 차 있으며, HMM은 그 중요한 첫걸음이라고 할 수 있을 것이다. 앞으로 더 정교한 시퀀스 모델들 (예: RNN, LSTM, Transformer)을 배우기 위한 훌륭한 기초가 될 것이라 확신한다.

[기계학습개론] Semi-Supervised Learning (SSL) - Self-training / Generative Model based / Margin based / Graph based

[기계학습개론] Active Learning: 제한된 리소스에서 최대의 성능을 이끌어내는 법