순차데이터 분석을 위한 Hidden Markov Model (HMM)

순차데이터 분석을 위한 Hidden Markov Model (HMM)

분석에 사용되는 feature들이 시간적 특성을 지닌다.

e.g., 지진파, 음성, 주식 거래량, 온라인 필기 문자 등

이러한 데이터를 sequential data 또는 context-dependent data라고 부른다.

시간성의 없는 데이터 선후 관계를 바꿔도 아무런 의미 변화가 없다.

시간성이 있는 데이터의 경우 선후 관계가 매우 중요해서

그것을 변경하면 새로운 결과가 나오게 된다.

HMM을 배우기 전에 기본적으로 Markov model이 무엇인지 부터 보자.

러시아 수학자 Andrey Markov 제안

시간 t에서의 관측은 가장 최근 r개 관측에만 의존한다는 가정 하의 확률 추론

예제

최근 4일간의 날씨 정보를 가지고 오늘 날씨를 추론하는것을 생각해 보자.

해 해 해 비 

1차 마코브 모델을 사용하면 어제의 날씨 변화만 오늘에 영향을 미치므로 아래와 같이 4가지 경우가 모두 같게 된다.

1차 마커브 모델을 표로 표현하면 아래와 같다.

오늘 비 였을때 내일 {비,구름,해}의 확률을 모두 합하면 1이 되야한다. 계산해 보면 1이 된다.

하지만, 내일 {비}라고해서 오늘 {비,구름,해}일 확률의 합이 1은 아니다. '역'의 관계에서는 어떠한 시간적 의미도 없기 때문이다.

여기서 2차 마코브 모델을 고려한다고 생각해보자.

선후 관계가 있으므로 순서가 있는 경우다. 즉 순열이며

{비,비,비}와 같은 중복을 허용한다.

따라서 2차 마코브 일때의 경우의 수는 아래와 같다.

위 표를 이용해서 3x3 matrix를 생성한다. 이것을 이용해서 마크브 모데의 상태전이도를 만들게 된다.

아래와 같은 조건을 만족 한다.

마코브 모델을 이용해서 무엇을 할 수 있을 까?

관측백터 x를 구할 수 있게 된다.

P(x|마코브 모델) = P(x|A)라는 식이 나온다.

여기서 마코브 모델을 나타내는 A는결국 joint probability가 되므로

마크모델 A와 관측 벡터 O간의 독립이면 P(O|A) = P(O)로 기술 할 수 있다.

그리고 joint probability가 갑자기 3->4로 넘어갈때 간단해 지는데 이러한 이유는

DAG 그래프 형태로, 즉 노드가 바로 직전의 부모에만 의존적인 베이시안 네트워크 구조를 가지기 때문이다.

즉 우리가 가정한 마코브는 1차원 바코브기 때문에 조인트 확률이 바로 직전의 노드에만 의존적이므로 뒷 부분을 모두 다 날려 버릴 수 있게 된다.

1차 마코브라도 계산을 위해서는 초기 확률이 필요하다.

초기 확률은 해가 되기위한 "파이3" 이다

곱의 확률이기 때문에 확률이 너무 적게 된다.

히든 마코브와 그냥 마코브와의 근본적인 차이점.

- 마코브 모델은 상태를 나타내는 노드에 관측 (비,해,구름) 그 자체가 들어 있다. 즉 상태를 볼 수 있다.

- HMM에서는 상태를 볼수 없게 했다. 즉 상태를 은닉 하게 된다.

동기

r차 마크브에서는 m^r (m-1)개의 매개변수가 생성 된다.

차수에 따라 모델의 크기가 너무 크게 증가 한다.

HMM

- 차수를 미리 고정하지 않고 모델 자체가 확률 프로세스에 따라 적응적으로 정함

- 따라서 아무리 먼 과거의 관측도 현재에 영향을 미침

- 즉 P(해 |비,비), P(해 | 비,비,비) , P(해,비,비,...,비) 모든 것에 따라서 확률 값이 다르게 된다. 즉 특정 어떤 차수에 고정적이지 않다.

- 이런 뛰어난 능력에도 불구하고 모델의 크기는 감당할 정도 이다.

비결

- 상태를 감추자

상태를 가지는 대신에 모든 노드가 모든 상태를 가질 수 있는 확률을 가지게 된다.

이용방법

예를 들어서 고나측 데이터로써 해->해->비->구름 이렇게 4일간의 관측 데이터가 존재한다고 하자.

그냥 마코브 모델을 사용한다면, 저러한 상태 전이는

s3 -> s3 -> S1 -> s2가 된다.

하지만 HMM의 경우

모든 상태에서 {비,해,구름}이 관측이 가능 하므로 가능한 시퀀스가 여러개 존재한다.

상태가 3개이니

3*3*3*3 의 경우의 수가 나온다.

3^4 = 81

이중에서 하나만 골라서 계산해 보면 

s3-> s3 -> s1 -> s2

HMM의 예제 (1) 

n개의 항아리에 공의 색깔 m개가 존재함

이러한 구성이 아래의 그림처럼

항아리 3개이고 공의 색깔은 4개이다.

이제 관측 백터에 대한 확률을 하나를 구해보자.

모델이 학습을 통해서 위와 같이 생성 되었다면,

관측 백터 O가 {진파, 연파, 검, 흰}이고

상태전이가 s1->s1->s1->s1 일때의 확률을 구하라

구하면 위와 같다.

그러면, 관측 백터 O가 {진파, 연파, 검, 흰} 나올 확률은 어떻게 구할까?

상태가 3개이고 4단계 이므로 나오는 확률의 경우의 수는 3^4 즉 81개이다.

이 81개의 확률을 모두 더해주면 관측 백터 O의 확률이 된다.

더하기다. 즉 그냥 Markov 모델은 곱하기인데, HMM은 더하기로 연산이 된다. 당연히 확률이 클 수 밖에 없다.

HMM의 예제 (2) 

여자친구의 삶 [Wikipedia]

-여자 친구의 일상을 관찰, V={산책, 쇼핑, 청소}

- 날씨는 {해,비} 2가지 상태 존재

- 수집한 정보는 아래와 같다.

답할 수 있는 문제

- 그녀가 일주일 연속으로 쇼핑만 할 확률은 ? (평가문제)

- { 산책, 산책, 청소 } 이렇게 했다면, 3일동안 날씨는 각각 어떠했는가 ? (디코딩 문제)

- { 산책, 산책, 청소} 했다면 오늘과 내일은 무엇을 할까? {복합적인 문제}

HMM의 구성요소와 세가지 문제

- 모델을 알고 있을 때 확률을 추론하라.(평가)

- 어느 것이 상태인가? 상태는 몇가지 인가? (아키텍쳐 설계)

- 확률 분포는 어떻게 구하나? (학습)

아키텍쳐 설계

HMM은 통상 가중치 방향 그래프로 표현 한다.

노드가 상태가 된다.

상태로 사용할 것이 명확한 경우도 있지만 그렇지 않은 경우도 있다.

대표적인 아키텍처

어고딕 모델과 좌우 모델

응용의 특성에 따라 적절한 아키텍처 선택이 중요

예를들어 음성인식은 좌우 모델이 좋다.

세개의 변수 결정

- 상태전이 확률 행렬 구성

- 관측 행렬 구성

- 초기 확률 백터 구성

세가지 문제점

평가: 모델 A가 주어졌을 때 관측 백터 O를 얻었을 때의 확률 P(O|A)는?

디코딩: 모델 A가 주어진 상화에서, 관측 벡터 O를 얻었을 때 최적의 상태열은 ? 역으로 가는 형태이다.

학습: 훈련집합을 가지고 모델 A를 도출 하는 과정이다.

HMM으로 Classficiation을 하는 방법은

Class 라벨마다 HMM을 생성해서 가장 높은 값을 가지는 Class 라벨로 prediction 하는 방법이 있다.

세가지 문제점에 적용 가능한 방법

평가: 동적 프로그래밍 이용

디코딩: 동적 프로그래밍 이용 (Viterbi 알고리즘)

학습: EM 알고리즘 (Baum-Welch 알고리즘)

평가: 동적 프로그래밍 이용

계산은 할 수 있어도

만약 관측 백터가 시퀀스 4이고 상태가 2이라면 (여자친구의 생활 패턴 문제)

2^4 = 16개를 계산 해야한다.

이것을 일반화 하면

상태수 n 관축 백터 O의 길이 T에 대해서

n의 t제곱 * t가 된다. 마지막 T는 더하기 연산 때문에 발생

동적 프로그래밍을 통한 중복 계산의 제거