본문 바로가기

Audio & Speech

[음성인식] 4.3 Baum–Welch algorithm

[음성인식]4,2 HMM에서 이어지는 글입니다. HMM은 likelihood, decoding, learning의 세 과정으로 이뤄져 있습니다. 그 중 마지막 과정인 learning 알고리즘에 사용되는 E-M 알고리즘 중 하나인 Baum–Welch algorithm에 대해 알아보겠습니다.

우리는 이전 글에서 HMM의 세가지 과정 중 likelihood를 계산하기 위한 forward algorithm, decoding을 하기 위한 Viterbi algorithm을 공부했다. 마지막 과정인 learning은 디코딩 과정에서 구한 best path hidden state Q와 관측값 O를 가지고 HMM 파라미터인 A(transition prob), B(emission prob)를 학습(추정)하는 과정이다. 

A, B를 추정 하는데 중요한 아이디어는 디코딩에서 구한 state path는 best paht의 후보 역할을 할 뿐,  전체 모델에서 best path가 아니고 정확한 best state는 모른다는 생각이다. 따라서 다음과 같이 모든 가능한 path에 대해 기댓값을 취해 A, B를 추정한다. 

i state에서 j state로 전이 할 확률 추정값
j state에서 Vk가 관측 될 방출확률

 

Esimate transition probability(A)

우선 A부터 어떻게 추정하는지 알아보자. 우선 결과부터 보고 역으로 구체화 시키겠다. A에 대한 추정은 최종적으로 다음과 같이 쓸 수 있다. 

수식1

여기서 $\xi_t(i,j)$ 는 관측 시퀸스 O, 모델 파라미터 람다가 주어졌을 때, t 시점에 i state, t+1 시점에 j state일 확률을 의미한다. 분모는 t-1 시점까지 sum 해주고, t+1 시점에 모든 가능한 state에 대해 sum 했으므로 시점에 관계없이 i state로 시작 할 확률이 된다. 분자는 t-1 시점까지 시점에 대해 sum 해주므로 시점에 상관없이 i state에서 j state로 전이 할 확률이 된다. 즉, 위에서 얘기한데로 모든 시점에서의 모든 path를 고려하여 i state에서 j state로 전이 할 확률의 기댓값을 구하고 이를 전이확률 A의 추정값으로 사용한다.

그러면 $\xi_t(i,j)$, 너는 뭐하는 놈이냐. 모델과 관측값이 주어졌을 때, t 시점에 i state, t+1 시점에 j state 일 확률이다. 다음과 같이 표현 가능하다.

람다 : 모델, O : 관측값

조건부 확률의 성질을 이용해 형태를 바꿔보자.

그러면 다음과 같은 식을 얻을 수 있다.

수식 2

분모는 해당 관측 시퀸스가 나타날 전체 likelihood를 의미하고, 분자는 t 시점에서 i state고 t+1시점에서 j state이며 관측 시퀸스 O가 나타날 확률을 의미한다. 다음 그림으로 분자를 이해해보자.

수식2 에서, forward probability($\alpha$), transition probability(a), emission probability(b)는 이전 글에서 정의 했었다. 여기서 새로운 표현은 backward probability $\beta$이다. 

$\beta_{t}(i)$는 t+1 시점 부터 끝까지 관측값이 주어졌을 때 t 시점에 i state일 확률을 의미한다. 다음의 그림을 보면, 지난 글에서 얘기한 forward probability와 개념은 동일하고 방향만 다른 것을 알 수 있다.

Backward probability

자 backward 까지 정의를 했으니 우리는 수식 2을 구할 수 있게 되었다. 수식 2 ; 모델과 관측값이 주어졌을 때, t 시점에 i state, t+1 시점에 j state 일 확률을 구한 뒤 처음에 정의했던 A 추정값(수식 1)을 구한다.

 

Esimate emission probability(B)

다음으로, HMM의 두번째 파라미터인 방출 확률 B를 추정한다. 이 과정의 논리는 위의 A 추정 과정과 동일하다. 역시 결론을 내고 역으로 과정을 구체화 시키겠다. 우리가 구하려는 j state에서 Vk가 관측될 방출 확률 B의 추정값은 최종적으로 다음과 같이 정의된다. 

수식3

$\gamma_t(j)$는 모델 $\lambda$와 관측 시퀸스 O가 주어졌을 때 t 시점에 j state일 확률을 의미한다. 따라서 위 수식은 $\gamma_t(j)$를 전체 시점에 대해 sum(분모)한 값 중에 우리가 관심있는 Vt가 t 시점에 관측되는 시점에 대한 sum(분자)을 의미한다. 그러면 $\gamma_t(j)$를 구해보자.

$\gamma_t(j)$는 상기했듯이 모델 $\lambda$와 관측 시퀸스 O가 주어졌을 때 t 시점에 j state일 확률이므로, 다음과 같이 표현할 수 있다.

이를 조건부 확률의 성질을 이용해 전개하면 다음과 같다.

$= \frac{\alpha _t(j)\beta _t(j)}{\sum_{j=1}^{N}\alpha _t(j)\beta _t(j)}$

분자는 모델이 주어졌을 때, t 시점에 j state에서 관측 시퀸스 O가 관측될 확률이고 분모는 전체 관측 시퀸스가 관측 될 우도(likelihood)이다. 다음 그림과 같이 forward, backward probability의 곱으로 계산할 수 있다.

이를 통해, 수식 3를 구하기 위한 $\gamma_t(j)$를 계산할 수 있다. 


Baum–Welch algorithm(forward-backward)

자 이제 우린 A 추정값(수식 1)과 B 추정값(수식 3)를 구할 수 있고, 이를 이용해서 관측 시퀸스 O로 부터 A, B를 추정할 수 있다. 이 추정 과정은 Baum–Welch 알고리즘을 통해 구한다. Baum–Welch 알고리즘은 E-M 알고리즘의 한 종류로, Expectation과 Maximization 과정을 추정하려는 값이 수렴할때까지 반복 수행한다.

그 과정은 위 그림과 같다. 우선 A, B를 랜덤 초기화 시켜 Expectation step으로 넘긴다. Expectation step에서는 A, B를 고정시킨 상태에서 위에서 알아 본 $\xi$, $\gamma$를 계산한다. 이후 Maximization step에서는 $\xi$, $\gamma$값들을 가지고 다시 A, B를 계산 한다. Sudo 코드는 다음과 같다.

이 알고리즘은 A, B에 대한 비지도 학습이기 때문에 실제 task에서 초기값 설정이 매우 중요하다. 


Summary

HMM 추론 전체 과정을 요약해보면, 다음과 같다.

1. HMM은 관측 시퀸스와 관측 시퀸스를 설명하는 hidden state를 연관시키는 방법이다.

2. 관측 시퀸스가 주어졌을 때, hidden state의 시퀸스를 찾는 과정을 디코딩(decoding)이라고 하고, 계산을 위해 Viterbi algorithm을 사용한다.

3. HMM의 파라미터 전이확률(A), 방출확률(B)는 Baum-Welch(forward-backward) algorithm으로 추정할 수 있다.