[머신러닝] HMM - Hidden Markov Model(1)

본 포스팅은 다음 포스팅[http://untitledtblog.tistory.com/97]을 참고하여 작성했습니다.

HMM 개요

HMM은 MM(Markov Model)에서 발전된 방법으로 관찰 가능한 결과와 관찰이 불가능한 은닉된 상태로 이루어진 모델입니다.

관찰가능한 결과를 야기하는 직접적인 원인은 관측될 수 없는 은닉 상태들이고, 오직 그 상태들이 마르코프 과정을 통해 도출된 결과들만이 관찰 될 수 있기 때문에 마르코프 모델 앞에 '은닉' 이라는 수식어가 붙었습니다. 

여기서 왜 '은닉'이 붙었는지 의문이 갈 수 있습니다.

실제 문제를 예로 들면, 환율의 변동을 통해 주식 시장의 상태를 유추하는 등, 관찰 가능한 정보로부터 은닉된 정보를 유추해야 하는 경우가 많습니다. 

HMM은 이러한 문제를 해결하기 위해 관찰 가능한 정보로부터 은닉된 정보에 대한 추론이 가능하도록 마르코프 연쇄를 변형한 것입니다. HMM에서는 어떠한 정보가 은닉되어 있고, 이를 유추하기 위해 모델을 학습시키기 때문에 은닉이라는 수식어가 붙습니다.

이와같이 HMM은 MM에서 발전된 모델이기 때문에 마르코프 모델의 기본적인 특징을 가지고 있습니다. 그 특징은 아래와 같습니다.

• 확률 과정(stochastic process) : 시간의 진행에 따라 확률적으로 변화를 가지는 구조를 의미한다. 
• 마르코프 특성(Markov property) : 확률론에서 마르코프 특성은 확률 과정에서 과거와 미래의 정보가 현재의 시행에 독립적이란 것을 의미합니다. 즉, 어떠한 확률변수 (random variable)   가 있을 때, 과거와 미래의 상태는 특정 시점의 확률변수 와 독립적이라는 것이다.
• 1차 마르코프 연쇄 (First order Markov chain) :  1차 마르코프 연쇄는 어떠한 시점의 상태  에 대해  는   에만 영향을 받는다. 예를 들어, 주식의 경우 이전의 여러 사건들의 영향을 받지만, 1차 마르코프 연쇄에 따르면 주식의 변동은 어제 주식의 가격만이 오늘 주식변동에 영향을 미친다고 가정합니다.
• 잠재 변수 (latent variable) : 변수의 구성 및 특성을 직접적으로 관찰하거나 측정할 수 없는 변수를 의미합니다. HMM에서는 직접적으로 관찰할 수 없는 각각의 상태 가 잠재 변수에 해당합니다. 
  

HMM 구조

HMM은 유한 상태 기계(finite state machine)와 비슷하게 어떠한 시간 t에서 오직 하나의 상태와 출력만을 가질 수 있으며, 시간의 진행에 따라 상태를 전이합니다. HMM은 이전의 상태가 다음 상태에 영향을 주기 때문에 음성, 주가 변동, 자연어 등 시간의 진행에 따라 생성되는 데이터를 표현하는 것에 매우 유용하게 이용될 수 있습니다. 아래 그림을 예로 설명드리겠습니다.

위 그림에서 는 시간 t에서의 은닉 변수(hidden variable)로써, 조건부 확률 분포를 따르는 변수입니다. HMM은 1차 마르코프 연쇄 특성을 따르기 때문에 의 조건부 확률 분포는 에만 영향을 받습니다. 은닉 변수 아래에 위치한 는 에 의해 특정된 상태로부터 결정되는 출력을 의미하는 변수이며, 또한 확률 분포에 의해 결정됩니다. 두 변수 와 는 그 자체가 특정 값을 갖는 것이 아니라, 상태와 출력을 나타내는 하나의 변수입니다. 즉, 확률적으로 상태 집합 S와 출력 집합 V의 한 원소를 값으로 갖습니다.

 HMM에서 각 시간대의 출력을 나타내는 를 이으면 HMM의 최종 출력인   가 됩니다.

HMM의 목적은 학습된 모델로부터 출력 O를 계산해내거나, 입력에 대해 주어진 입력이 도출될 확률이 가장 큰 상태의 연속된 순서를 유추해내는 것입니다.

HMM 동작

HMM의 동작을 설명하기 전에 아래와 같은 3가지 확률을 정의하겠습니다. 확률을 합쳐서 HMM을 구성하는 인자 (parameter)라고 합니다.

• 초기 확률 (initial probability) : 초기 확률 로 나타내며 HMM이 에서 시작할 확률을 의미한다.

• 천이 확률 (transition probability) : 전이 확률 로 나타내면 에서 로 이동할 확률을 의미한다.

• 출력 확률(emission probability) : 출력 확률 로 나타내며, 에서 가 출력될 확률을 의미한다. 

  
  

위 인자를 통해 HMM으로부터 관측열을 발생 시키는 과정은 아래와 같습니다.

1. 에 따라 첫 상태 가 결정된다.

2. 시간 T = 1

3. 상태  에서 에 따라 이 출력된다.

4. 상태 에 대한 상태 상태 천이 확률 에따라 다음 상태 로의 천이가 일어난다. 

5. 시간을 하나 증가시키고 ( t = t+1) , 최종 시가넹 도달하지 못했다면 (t < T ) 3번 과정으로 돌아가고, 도달했으면 관측열 생성을 종료한다. 

아래 예제를 살펴보겠습니다.

어떠한 지역은 통계적으로 아래의 [표 1]과 같이 날시가 변하는 지역에 살고 있다. 

또한, 이 지역에 거주하고 있는 A는 날씨에 따라 아이스크림을 하루에 [표 2]와 같이 확률적으로 소비한다. 

A는 항상 자신이 먹은 아이스크림의 수를 하루 단위로 기록했다. 어떠한 사고로 인해 A가 거주하고 있는 지역의 날씨를 기록한 데이터가 모두 소실되었다. 기상청은 A가 먹은 아이스크림의 수에 대한 기록을 이용하여 해당 지역의 과거 날씨를 유추해내고자 한다. 이러한 상황에서 A가 먹은 아이스크림의 수는 관측 가능한 정보이고, A가 거주하고 있는 지역의 날씨는 은닉된 정보이다. 

또한, [표 1]에는 나타나지 않았지만, A가 살고 있는 지역의 날씨는 대체로 흐리다. 이러한 사실과 [표 1,2]의 내용을 모두 표현하는 다이어그램은 아래 그림과 같다. 그림 3-a 에서 파란색 화살표는 초기 확률을 나타낸다.

위와 같은 예제가 있을 때, 아래와 같은 두 가지 가능한 동작을 생각해볼 수 있다.

• 아이스크림 소비가 (1,3,3,2)와 같이 나타났을 때, 이러한 소비 결과가 도출될 확률 계산
• 아이스크림의 소비가 (1,3,3,2)와 같이 나타났을 때, 이러한 소비 결과가 도출될 확률이 가장 큰 날씨의 변화 과정 유추

이러한 두 가지 동작은 결국 HMM을 이용하여 특정 출력이 도출될 확률을 계산하거나, 특정 출력에 대한 최적의 상태 전이 과정을 유추하는 것이다. HMM을 구현할 때는 이 두가지 동작을 어떻게 계산할 것인지에 대해 고려해야 한다. 또한, 위의 경우와는 다르게 HMM의 인자가 주어져있지 않을 때, 주어진 출력으로부터 인자를 결정해나가는 학습 연산 또한 HMM 구현 시 고려해야하는 문제이다. HMM을 구현할 때 고려해야하는 문제는 아래와 같이 총 3가지로 나눌 수 있다 

• HMM의 인자 및 특정 출력이 주어졌을 때, 주어진 출력이 도출될 확률 계산
• HMM의 인자 및 특정 출력이 주어졌을 때, 주어진 출력이 도출될 가능성이 가장 높은 상태전이 과정 유추
• 특정 출력만 주어졌을 때, HMM의 인자를 학습

위 문제는 각각 아래 알고리즘으로 해결할 수 있다.

• 동적계획법 기반의 Forward algorithm
• 동적계획법 기반의 Viterbi Algorithm
• 기댓값 최적화 알고리즘 기반의 Baum-Welch Algorithm

다음 장부터 이 3가지 알고리즘에 대해 알아보겠습니다.