Markov model은 어떠한 날씨, 주식가격 등과 같은 어떠한 현상의 변화를 확률 모델로 표현한 것이다. Hidden Markov model (HMM)은 이러한 Markov model에 은닉된 state와 직접적으로 확인 가능한 observation을 추가하여 확장한 것이다. HMM은 observation을 이용하여 간접적으로 은닉된 state를 추론하기 위한 문제를 풀기 위해 사용된다.
아래의 [그림 1]은 은닉된 state와 그에 따른 observation의 개념을 나타낸다. HMM을 이용해 우리가 풀고자 하는 문제는 관측 가능한 것은 오직
1950년대 이후 forward-backward recursion, Baum-Welch algorithm, Viterbi algorithm이 소개되면서 HMM에 대한 많은 연구가 진행되었고, 1970년대에는 음성 인식 분야에서 HMM이 활발히 응용되기 시작하였다. 현재는 필기체 인식, 동작 인식, 품사 태깅 등과 같이 이전 시간의 데이터에 영향을 받는 순차 데이터에서 패턴을 인식하기 위해 이용되고 있다.
HMM은 <
- 은닉된 state들의 집합이다. - 은닉된 state에서 발생할 수 있는 observation들의 집합이다. - 초기 state가 일 확률을 나타내는 initial probability 의 집합이다. - 에서 로 이동할 확률을 나타내는 transition probability 의 집합이다. - 에서 가 발생할 확률을 나타내는 emission probability 의 집합이다.
일반적으로 HMM은 아래의 [그림 1]과 같은 그래프의 형태로 표현된다. 그래프에서
HMM의 동작을 설명하기 위한 한 가지 예시로써 지출내역을 통해 과거의 행동을 유추하는 문제를 [그림 3]과 같은 HMM으로 정의할 수 있다. 오늘 하려는 행동은 무엇을 했는지에 영향을 받으며, 과거에 했던 행동은 과거로 돌아가지 않는 한 다시는 관측할 수 없기 때문에 과거의 행동은 은닉된 state에 해당한다. 이 예제에서
HMM을 구성하기 위해서는 위에서 정의한
[표 1]을 통해서는 사람의 행동 양식을 알 수 있다. 예를 들어, 전날 친구를 만나고 오늘도 친구를 만날 확률은 0.1로 매우 작다는 것이나 전날 게임을 했다면 오늘은 0.5의 확률로 공부를 한다는 것이다. 또한, [표 2]를 통해서는 소비 습관을 알 수 있다. 예를 들어, 공부를 하는 날에는 돈을 거의 쓰지 않는다는 것이나 친구를 만나면 0.4의 확률로 많은 돈을 쓴다는 것이다. HMM은 이러한 확률적 사실들을 바탕으로 observation을 통해 은닉된 state를 추론하는 것이다.
[그림 3]과 [표 1, 2]로 정의된 HMM이 주어졌을 때, 우리는 HMM을 이용하여 아래의 두 가지 사항을 추론할 수 있다.
- 지출 내역이 1 1 4 2일 때, 이러한 지출 내역이 나타날 확률 계산
- 지출 내역이 1 1 4 2일 때, 이러한 지출 내역이 나타날 확률이 가장 큰 과거의 행동 추론
- HMM의 parameter가 주어졌을 때, 주어진 observation이 나타날 확률 계산
- HMM의 parameter가 주어졌을 때, 주어진 observation이 나타날 확률이 가장 높은 state의 나열을 계산
- 학습 데이터로부터 HMM의 parameter
를 학습
첫 번째와 두 번째 문제는 각각 dynamic programming 기반의 forward algorithm과 Viterbi algorithm으로 해결할 수 있다. HMM의 parameter를 학습시키는 마지막 문제는 주로 expectation-maximization algorithm (EM algorithm)의 한 형태는 Baum-Welch algorithm으로 해결한다.
첫 번째 문제는 HMM의 모든 parameter가 결정되었을 때, 주어진 observation
그다음, 첫 번째와 두 번째 observation이 연속으로 나타날 확률은 다음과 같다.
따라서, 시간
그러나 [식 3]을 계산하는 것은
또한,
아래의 [알고리즘 1]은 HMM에서 forward algorithm을 이용하여 [식 3]의 likelihood를 계산하는 과정을 나타낸다.
위의 [그림 3]의 예제에서 지출내역이 1, 3, 2, 1, 2인 (
두 번째 문제는 주어진 observation이 나타날 확률이 가장 state의 연속
위의 [그림 3]의 예제에서 지출내역이 1, 3, 2, 1, 2인 (
HMM의 parameter 학습은 observation들의 집합인
HMM의 parameter 학습에는 주로 EM algorithm의 한 종류인 Baum-Welch algorithm가 이용된다. 이 알고리즘에서는 먼저
양변에 log를 취하면 [식 7]과 같다.
그러나 대부분의 경우에는
[식 7]을 [식 8]에 대입하면, Baum-Welch algorithm을 통해 최대화하고자 하는
마지막으로, 라그랑주 승수법 (Lagrange multiplier method)를 이용하여 확률의 정의에 의한 제약 조건을
따라서, HMM의 학습은
그다음,
마지막으로,
'지능형시스템 > 머신러닝' 카테고리의 다른 글
[머신 러닝/딥 러닝] 인공 신경망을 위한 확률적 경사 하강법 (3) | 2018.12.24 |
---|---|
[머신 러닝/딥 러닝] 인공신경망 (Artificial Neural Network, ANN)과 역전파 알고리즘 (Backpropagation Algorithm) (11) | 2018.04.21 |
[머신 러닝/강화 학습] Markov Decision Process (MDP) (0) | 2018.04.11 |
[머신 러닝] 나이브 베이즈 분류기 (Naive Bayes Classifier, NBC) (0) | 2018.04.10 |
[머신 러닝] Bayesian Decision Theory (0) | 2018.04.08 |