Baum-Welch 알고리즘은 은닉 마르코프 모델(HMM)의 알려지지 않은 매개변수를 찾는 데 사용되는 기대값 최대화(EM) 알고리즘의 특수한 경우이다. 이는 HMM에서 추론을 위한 주요 방법으로, 기대값 단계의 통계량을 계산하기 위해 전방-후방 알고리즘을 활용한다. 이 알고리즘은 1960년대 후반과 1970년대 초반에 프린스턴의 IDA 통신 연구 센터에서 동료들과 함께 이를 개발한 Leonard E. Baum과 Lloyd R. Welch의 이름을 따서 명명되었다.
은닉 마르코프 모델은 은닉 및 관측된 이산 확률 변수들의 집합의 결합 확률을 설명한다. 이는 i번째 은닉 변수가 (i-1)번째 은닉 변수가 주어졌을 때 이전 은닉 변수들과 독립적이며, 현재 관측 변수들은 현재 은닉 상태에만 의존한다는 가정에 기반한다. Baum-Welch 알고리즘은 주어진 관측 특징 벡터 집합에 대해 HMM의 매개변수의 최대 우도 추정치를 찾기 위해 EM 알고리즘을 사용한다.
공식 설명
\(X_t\)를 총 \(N\)개의 상태를 나타내는 \(N\)개의 가능한 값을 가진 이산 은닉 확률 변수라고 하자. 전이 확률은 시간 독립적이라고 가정되며, 이는 확률적 전이 행렬 \(A = \{a_{ij}\} = P(X_t = j \mid X_{t-1} = i)\)의 정의로 이어진다. 초기 상태 분포는 \(\pi_i = P(X_1 = i)\)로 주어진다.
관측 변수 \(Y_t\)는 \(K\)개의 가능한 값 중 하나를 취할 수 있다. 시간 \(t\)에서 상태 \(X_t = j\)에 대한 특정 관측 \(y_i\)의 확률은 \(b_j(y_i) = P(Y_t = y_i \mid X_t = j)\)로 주어진다. 이는 \(N \times K\) 행렬 \(B = \{b_j(y_i)\}\)를 산출한다. 관측 시퀀스는 \(Y = (Y_1 = y_1, Y_2 = y_2, \ldots, Y_T = y_T)\)로 주어진다. 따라서 은닉 마르코프 체인은 \(\theta = (A, B, \pi)\)로 설명될 수 있다. Baum-Welch 알고리즘은 \(\theta^* = \arg\max_\theta P(Y \mid \theta)\)에 대한 지역 최대값을 찾는다.
알고리즘 단계
이 알고리즘은 매개변수 추정치를 반복적으로 개선한다. 기대값 단계에서는 전방-후방 알고리즘을 사용하여 전방 확률 \(\alpha_t(i) = P(Y_1, \ldots, Y_t, X_t = i \mid \theta)\)과 후방 확률 \(\beta_t(i) = P(Y_{t+1}, \ldots, Y_T \mid X_t = i, \theta)\)을 계산한다. 이들은 시간 \(t\)에서 상태 \(i\)에 있을 확률과 시간 \(t\)와 \(t+1\) 사이에 상태 \(i\)에서 상태 \(j\)로 전이할 확률과 같은 기대 충분 통계량을 계산하는 데 사용된다.
최대화 단계에서는 알고리즘이 기대 로그 우도를 최대화하기 위해 매개변수 \(A\), \(B\), \(\pi\)를 업데이트한다. 업데이트된 전이 확률은 상태 \(i\)에서 상태 \(j\)로의 전이의 기대 횟수와 상태 \(i\)에 있을 기대 횟수의 비율로 계산된다. 유사하게, 방출 확률은 각 상태에서 관측의 기대 횟수에 기반하여 업데이트된다. 초기 상태 분포는 시간 1에서 각 상태에 있을 기대 확률에 기반하여 업데이트된다.
알고리즘은 수렴할 때까지, 일반적으로 로그 우도의 변화가 임계값 아래로 떨어질 때까지 반복을 계속한다. 이는 우도 함수의 지역 최대값으로 수렴하는 것이 보장되지만, 반드시 전역 최대값은 아니다.
수치적 안정성
Baum-Welch 알고리즘은 결합 확률의 재귀적 계산으로 인해 수치적으로 불안정하다. 변수의 수가 증가함에 따라 이러한 결합 확률은 점점 더 작아지며, 전방 재귀가 기계 정밀도 아래의 값에 빠르게 접근하게 된다. 이는 특히 긴 관측 시퀀스에서 실제 구현 시 언더플로를 유발할 수 있다. 이를 완화하기 위해 구현은 각 시간 단계에서 전방 및 후방 변수를 정규화하거나 로그 도메인에서 작업하는 것과 같은 스케일링 기법을 자주 사용한다.
응용 분야
HMM의 첫 번째 주요 응용 분야 중 하나는 음성 처리 분야였다. 1980년대에 HMM은 생물학적 시스템 및 정보, 특히 유전 정보 분석에서 유용한 도구로 등장했다. 이후 이들은 유전체 시퀀스의 확률적 모델링에서 중요한 도구가 되었다. Baum-Welch 알고리즘은 또한 품사 태깅 및 개체명 인식과 같은 자연어 처리와 유전자 발견 및 단백질 구조 예측을 위한 계산 생물학에서도 사용된다.
관련 개념
Baum-Welch 알고리즘은 기계 학습의 다른 매개변수 추정 기법과 밀접하게 관련되어 있다. 이는 잠재 변수 모델에 널리 사용되는 기대값 최대화 알고리즘의 특정 사례이다. 핵심 구성 요소인 전방-후방 알고리즘은 디코딩을 위한 Viterbi 알고리즘과 같은 다른 HMM 추론 작업에서도 사용된다. 현대 딥러닝에서는 잠재 변수를 가진 모델을 훈련할 때 유사한 원리가 나타나지만, 신경망은 EM 대신 Adam (Optimizer) 및 Stochastic Gradient Descent Variants와 같은 경사 기반 방법을 자주 사용한다. 이 알고리즘의 Machine learning 및 Artificial intelligence와의 연결은 시퀀스 데이터 학습을 위한 초기 프레임워크를 제공했기 때문에 기초적이다.