[ML][패턴인식] 7. 순차 데이터 인식(Hidden Markov Model)

Hidden Markov Model의 개요: 순차 데이터나 문맥 의존 데이터를 인식하는 가장 대표적인 모델, 확률을 이용한 모델

(1) 순차 데이터 : 시간성을 갖는 데이터, 대부분 가변 길이를 가짐

(2) 문맥 의존 데이터 : 명시적으로 시간성을 갖지는 않지만 단어 간에 앞 뒤 관계가 있는 문장속의 단어나 단어속의 문자들

(3) 읽어볼만한 논문 

- HMM : rabiner89, Bilmes02, 

- 제스쳐 인식 : wang07, wu99, nam96 -> [Davis02, Rabiner93, Rabiner89]

- 컴퓨터 비전 응용 : Forsyth03, pp.550-567

7.2 마코프 모델

모델 : 수학적 특, 확률 이론을 바탕으로 개발된 확률 모델을 뜻함 (ex:  베이시언 분류기)

시간 t에서의 관측은 단지 가장 최근 r개의 관측에만 의존한다는 가정하에 만듬

0차 마르코프 체인은 과거를 전혀 보지 않고 과거에 독립적임

1차 마르코프 체인은 단지 바로 이전의 관측에만 관련이 있음

2차 마르코프 체인은 바로 이전 두 개의 관측만 본다.

마르코프 모델은 1차 마르코프 체인을 사용한다. 2차 이상은 매개변수가 너무 많아서 현실적으로 적용이 어렵다.

(1) 상태 전이

- 상태 전이 확률 행렬 : 오늘 비가 왔을 때 내일 날씨가 맑을 확률 등을 행렬로 표현함

- 상태 전이도 : state transition diagram

7.3 은닉 마코프 모델(Hidden Markov Model)로의 발전

패턴 인식이 가장 기본적으로 요구하는 작업 즉 훈련 집합으로 학습을 한 후 새로 들어오는 테스트 샘플을 높은 성능으로 분류하는 일을 위해 은익을 추가한 은닉 마르코프 모델로의 발전이 필요

HMM은 차수를 미리 고정하지 않고 모델 자체가 확률 프로세스에 따라 적응적으로 정하도록 한다.

7.3.2 HMM의 예

- 공을 담은 항아리

A. 상태에 해당하는 공 항아리에서 공을 하나 뽑고 색깔을 확인하고 다시 집어 넣는다.

B. 색깔을 o1에 기록한다.

C. 그 상태에 해당하는 카드 항아리에서 카드를 하나 뽑고 번호를 보고 다시 집어 넣는다.

D. 카드 번호의 상태로 이동한다.

E. A.부터 다시 반복한다.

7.3.3 구성 요소와 세가지 문제

- 아키텍쳐

(1) ergodic(어고딕) 모델 : 완전 연결 구조

(2) 좌우(left to right) 모델 : 상태 전이가 왼쪽에서 오른쪽으로 일어남, 음성 인식에서 주로 사용 됨

- 매개 변수

(1) 상태 전이 확률 : 오늘 비가 왔을 때 내일 날씨가 맑을 확률

(2) 관측 확률
- 비가 올 때 집에 있을 확률, 비가 올 때 외출할 확률
(3) 초기 상태 확률 벡터
- HMM(Hidden Markov Model)을 기동시킬 때 어느 상태에서 시작할 지를 결정하는데 쓰임

- 세 가지 문제

(1) 평가 evaluation

(2) 디코딩 decoding

(3) 학습 learning

7.4 알고리즘

평가와 디코딩을 위한 알고리즘은 계산 효율을 위해 동적 프로그래밍을 사용

7.4.1 평가

ⓗ : 모델 HMM이 가지는 매개변수 set ⓗ = (A, B, π) A: 상태 전이 확률 B: 관측 확률 π: 초기 상태 확률 벡터

O : 관측 벡터 (산책, 청소 쇼핑 등)

P(O|ⓗ) : 발생확률

평가 문제 : 주어진 모델 ⓗ 하에서 관측 벡터 O의 발생 확률 P(O|ⓗ)를 계산 하는 것

Q : O를 관측한 상태 열을 알고 있다고 가정

P(O,Q|ⓗ) : ⓗ가 주어진 상황에서 O가 Q에서 발생했을 확률

ex)

(1) πp1의 확률로 q1로 들어간다.

(2) q1에서 bq1(o1)의 확률로 o1을 관측한다.

(3) 전이 확률 aq1q2로 상태 q1에서 q2로 이동한다.

(4) q2에서 bqw(o2)의 확률로 o2를 관측한다.

(5) aq(T-1)qT로 상태 q(T-1)에서 qT로 이동한다. qT에서 bqT(oT)의 확률로 oT를 관측하고 마친다.

(1)~(5)의 관측과 전이를 반복하는 과정에서 발생하는 확률을 모두 곱하면 P(O,Q|ⓗ)

즉, P(O|ⓗ) = 모든 Q에 대해 P(O,Q|ⓗ)의 합

동적 프로그래밍 기법 : 전방 알고리즘 사용

- 이유 : 계산식이 너무 많아지므로 중복된 계산을 피하기 위해 사용

7.4.2 디코딩

Viterbi 알고리즘 사용

디코딩은 모델 ⓗ 하에서 관측 벡터 O를 얻었을 때 O에 해당하는 최적의 상태 열 Q를 찾는 문제

P(O,Q|ⓗ)를 기준 함수로 채택하고 이것을 최대화하는 Q를 찾는다.

Q = arg max P(O,Q|ⓗ)

* arg max(f(x))는 f(x)를 최대로 만드는 x값

7.4.3 학습

관측 벡터 O의 확률을 최대로 하는 모델 ⓗ를 찾는 문제

O로 ⓗ를 직접 구할 수는 없고 중간에 '숨어서' 매개 역할을 하는 변수가 필요하다. 이러한 변수는 이미 3.4.2절의 EM알고리즘에서 등작하였고 은닉 변수(latent variable)라 불렀다.

가우시안 혼합에서는 샘플이 독립 동일 분포에서 발생했다는 가정 하에 요소 분포들을 독립적으로 취급하는 반면 HMM은 분포들이 시간에 따라 관련성을 갖는다고 간주하고 상태 이전 확률을 개입시키는 근본적인 차이가 있다.

알고리즘에서 기대값을 구하는 단계와 우도를 최대화 하는 (Maximum likelihood) 단계로 구성된다.

*일단 더 공부하기 위해서는 다시 3.4절을 공부하고 와야할 것 같음

좌우 모델은 온라인 필기 인식이나 음성 인식 같은 응용에 주로 사용되는데 이런 응용에서는 T가 작다. 대신 하나의 관측이 주어지는 것이 아니라 여러 개가 주어진다. 따라서 다중 관측을 위한 학습이 가능하도록 알고리즘을 변경해야 한다. 이에 대해서는 [Davis02, Rabiner93, Rabiner89]를 참고

7.5 부연 설명

Cambridge 대학의 Machine Intelligence Lab이 개발한 HTK(HMM Toolkit)은 C로 구현된 공개 소프트웨어이다. 한번 사용해 보아야겠다.