전방-후방 알고리즘(forward-backward algorithm)은 은닉 마르코프 모델(HMM) 및 관련 확률적 시퀀스 모델의 맥락에서 사용되는 기본적인 동적 프로그래밍 기법이다. 이 알고리즘은 관측 시퀀스가 주어졌을 때 각 은닉 상태의 사후 주변 분포를 계산하여 효율적인 추론과 매개변수 추정을 가능하게 한다. 이 알고리즘은 고전적 머신 러닝의 초석이며, 음성 인식, 생물정보학, 자연어 처리와 같은 현대적 응용 분야에서도 여전히 관련성이 있다.
이 알고리즘은 1960년대 후반과 1970년대 초반에 레너드 바움(Leonard Baum)과 그의 동료들이 마르코프 체인의 확률적 함수에 대한 통계적 추정에 관한 일련의 논문에서 공식화하였다. 이 알고리즘은 가장 가능성 높은 은닉 상태 시퀀스를 찾는 비터비 알고리즘과 함께 자주 소개되는데, 전방-후방 알고리즘은 각 시간 단계에서 각 개별 상태의 확률을 계산하는 반면, 비터비 알고리즘은 전체 시퀀스의 최적 경로를 찾는다. 이 알고리즘은 두 번의 패스로 작동한다. 전방 패스는 주어진 시간 지점까지의 관측 시퀀스 확률과 특정 상태에서 끝날 확률을 계산하고, 후방 패스는 시작 상태가 주어졌을 때 나머지 시퀀스를 관측할 확률을 계산한다. 이 두 확률 집합을 결합하면 원하는 사후 주변 확률을 얻을 수 있다.
수학적 공식화
은닉 상태 \( S = \{s_1, s_2, \ldots, s_N\} \), 전이 확률 \( a_{ij} = P(s_j | s_i) \), 방출 확률 \( b_j(o_t) = P(o_t | s_j) \), 초기 상태 분포 \( \pi_i = P(s_i) \)를 가진 HMM을 고려하자. 관측 시퀀스 \( O = (o_1, o_2, \ldots, o_T) \)에 대해, 전방 변수 \( \alpha_t(i) \)는 시간 \( t \)까지의 부분 관측 시퀀스와 시간 \( t \)에서 상태 \( s_i \)에 있을 확률로 정의된다. 즉, \( \alpha_t(i) = P(o_1, o_2, \ldots, o_t, q_t = s_i | \lambda) \)이며, 여기서 \( \lambda \)는 모델 매개변수를 나타낸다. 전방 패스는 \( \alpha_1(i) = \pi_i b_i(o_1) \)로 초기화하고, 재귀적으로 \( \alpha_{t+1}(j) = b_j(o_{t+1}) \sum_{i=1}^N \alpha_t(i) a_{ij} \)를 계산한다.
후방 변수 \( \beta_t(i) \)는 시간 \( t \)에서 상태가 \( s_i \)일 때 시간 \( t+1 \)부터 \( T \)까지의 관측 시퀀스 확률로 정의된다. 즉, \( \beta_t(i) = P(o_{t+1}, o_{t+2}, \ldots, o_T | q_t = s_i, \lambda) \)이다. 후방 패스는 모든 \( i \)에 대해 \( \beta_T(i) = 1 \)로 초기화하고, 재귀적으로 \( \beta_t(i) = \sum_{j=1}^N a_{ij} b_j(o_{t+1}) \beta_{t+1}(j) \)를 계산한다. 시간 \( t \)에서 상태 \( s_i \)에 있을 사후 확률은 \( \gamma_t(i) = \frac{\alpha_t(i) \beta_t(i)}{\sum_{j=1}^N \alpha_t(j) \beta_t(j)} \)로 주어진다.
시퀀스 모델링에서의 응용
이 알고리즘은 기대값 최대화의 한 예인 바움-웰치 알고리즘을 통해 HMM을 훈련하는 데 널리 사용된다. E-단계에서 전방-후방 알고리즘은 상태 간 전이의 기대 횟수와 각 관측 기호의 방출 기대 횟수와 같은 기대 충분 통계량을 계산한다. 이러한 통계량은 M-단계에서 모델 매개변수를 업데이트하는 데 사용된다. 이 반복 절차는 우도 함수의 국소 최대값으로 수렴한다.
음성 인식에서 전방-후방 훈련을 사용한 HMM은 1970년대부터 2000년대 초반까지 음향 모델링의 지배적인 접근 방식이었으며, 이후 딥 러닝 방법에 의해 크게 대체되었다. 생물정보학에서 이 알고리즘은 유전자 예측과 단백질 서열 분석에 사용되며, HMM이 보존 모티프를 모델링한다. 자연어 처리에서는 품사 태깅과 구조화된 출력 레이어를 사용하는 시퀀스-투-시퀀스 모델의 훈련에 나타난다.
현대 머신 러닝과의 관계
전방-후방 알고리즘은 고전적 기법이지만, 그 원리는 현대 머신 러닝에서도 지속된다. 전방 패스는 순환 신경망에서 정보의 전파와 유사하고, 후방 패스는 오류 신호의 역전파와 유사하지만, 수학적 목적은 다르다. 양방향 LSTM과 같은 시퀀스 레이블링에 사용되는 신경망에서는 전방 및 후방 은닉 상태를 결합하여 양방향의 맥락을 포착하는데, 이는 알고리즘의 전방 및 후방 변수를 반영한다. 또한, 이 알고리즘의 효율적인 동적 프로그래밍 사용은 트랜스포머 기반 모델에서 유사한 기법에 영감을 주었으며, 예를 들어 일부 형태의 구조화 예측과 명명된 엔티티 인식과 같은 작업을 위한 대규모 언어 모델 훈련에서 사용되는 전방-후방 알고리즘이 있다.
이 알고리즘은 빔 서치의 개념과도 관련이 있는데, 둘 다 시퀀스 문제에서 계산 복잡성을 관리하지만 목적은 다르다. 빔 서치는 가장 가능성 높은 시퀀스를 근사하는 반면, 전방-후방 알고리즘은 정확한 주변 확률을 계산한다. 확률적 그래픽 모델에서 전방-후방 알고리즘은 체인 그래프에서 합-곱 알고리즘의 특수한 경우이며, 신뢰 전파를 통해 트리 구조 모델로 일반화된다.
계산 복잡성 및 변형
전방-후방 알고리즘은 \( O(T N^2) \) 시간과 \( O(T N) \) 공간으로 실행되며, 여기서 \( T \)는 시퀀스 길이, \( N \)은 은닉 상태 수이다. 이러한 효율성 덕분에 수백 개의 상태를 가진 수천 개의 시간 단계 시퀀스에도 적용 가능하다. 큰 상태 공간의 경우 전방 필터링 후방 샘플링 알고리즘과 같은 근사 기법이 입자 필터링 및 몬테카를로 방법에서 사용된다. 온라인 설정에서는 전방 알고리즘만 필터링에 사용할 수 있지만, 후방 패스는 전체 시퀀스를 필요로 하므로 오프라인 방식이다. 변형으로는 긴 시퀀스와 작은 확률을 다룰 때 흔히 발생하는 수치적 언더플로를 방지하기 위한 스케일링된 전방-후방 알고리즘이 있다.
같이 보기
- hidden-markov-model
- 비터비 알고리즘
- 바움-웰치 알고리즘
- dynamic-programming
- sequence-modeling