[ML] Hidden Markov Model(HMM)

※해당 게시물에 사용된 일부 자료는 순천향대학교 빅데이터공학과 정영섭 교수님의 머신러닝 전공수업 자료에 기반하였음을 알려드립니다.

 

이번 포스팅에서는 HMM(Hidden Markov Model)이라고 불리우는 히든 마르코프 모델에 대해 다루려고 한다. HMM은 기본적으로 Markov Property(마르코프 특성)를 가정한다. 따라서 '마르코프 특성'에 대한 개념부터 정립하고 넘어가야 한다. 이번 글에서 써내려갈 목차는 다음과 같다.

 

1. Markov Property란?

2. Markov Model의 종류

3. HMM(Hidden Markov Model)

4. HMM의 알고리즘

 

1. Markov Property란?

마르코프 특성의 정의에 대해 알아보기 전에 밑의 수식을 살펴보자.

 

Markov Property란 무엇일까?

위 그림의 맨 윗줄 쌍따옴표(") 부분을 살펴보자. 한국어로 해석하게 된다면 "현재가 주어졌을 때, 미래는 과거와 독립적이다" 이다. 이를 수학적인 수식(확률 수식)으로 나타나게 된다면 P(St+1 | St) = P(St+1 | S1, S2, ... St)가 된다. 이 말은 t시점의 S가 주어졌을 때 St+1의 발생확률은 1부터 t시점까지의 S가 주어졌을 때 St+1이 발생할 확률과 같다는 것이다. 결국 미래의 값인 St+1이 발생할 확률은 과거의 확률에 상관없이 현재시점인 t의 확률값에 의해서만 영향을 받는다는 의미이다. 

 

위 설명에서는 단순히 시간 간격이 1일 때만을 고려했지만 시간 간격(r값)에 따라 마르코프 특성을 정의하게 되면 다음 그림과 같다.

 

시간 간격(r값)에 따른 Markov Property

2. Markov Model의 종류

마르코프 모델의 종류에는 크게 두가지가 존재한다. 

 

2-1. Ergodic(에르고딕) Model

한 노드에서 다른 임의노드로 도달이 가능한 구조이다.

 

에르고딕 모델

 

2-2. Left-Right(좌우) Model

방향성을 가지는 모델로서 순서가 있는 Sequence 데이터에 적합하다. 따라서 음성인식에 주로 사용된다. 하지만 방향성을 가지므로 이전의 State로 돌아갈 수 없는 제약이 존재한다.

 

좌우 모델

3. HMM(Hidden Markov Model)

이제 이번 포스팅의 메인 주제인 HMM모델에 대해 알아보자. HMM은 위에서 소개했던 '마르코프 모델'과는 달리 'Hidden State' 즉, '보이지 않는 상태'가 추가된 모델이다. Hidden state를 추가하는 것은 단순히 '관측 데이터'에만 의존하는 것이 아닌 더욱 더 고차원적인 문제를 해결하기 위함이다. 이렇게 서술하는 것이 피부에 와닿게 이해되지 않을 수 있기 때문에 필자도 공부할 때 이해를 했던 예시자료를 같이 살펴보자.

 

HMM 모델의 구성

위 예시에서는 커튼 뒤에 존재하는 3개의 항아리가 Hidden state에 해당한다. 그리고 보여주는 공이 '관측 데이터'에 해당한다. 그리고 이를 기반으로 모델을 구성하게 되면 위 그림의 오른쪽 에르고딕 모델과 같아진다. 

 

그리고 HMM에서 3가지 파라미터를 정의하게 되는데 이에 대한 설명은 밑의 그림을 보면서 이해해보자.

 

HMM의 3가지 파라미터는 무엇을 의미할까?

우선 모델 파라미터 θ값은 3가지 파라미터 A, B, π 총 3가지로 구성되어 있다. 이에 대해 하나씩 정의해보자.

 

• A : 상태(State) 전이 확률을 나타내는 aij들의 모음을 의미한다. 예를 들어 a12라고 나타낸다면 1번 상태에서 2번 상태로 전이될 확률을 의미한다.

• B : 상태 별 관측 확률을 나타내는 bj(k)의 모음을 의미한다.(이 때, k는 관측 데이터이다.) 예를들어 b2(k=빨간공) 이라고 한다면 2번 상태에서 '빨간공' 관측값이 나올 확률을 의미한다.

• 파이값 : 상태별로 초기값을 나타내는 파이값들의 모음이다.

이렇게 우리는 HMM의 모델의 파라미터가 무엇이고 어떤 요소들로 구성되어 있는지 확인해보았다. 그런데 이러한 HMM도 어떠한 문제를 해결하기 위해 존재하는 것임이 분명하다.

그렇다면 이러한 HMM을 어떻게 이용해서 문제를 해결할 수 있을까? 답을 찾기 위해 대표적인 3가지의 HMM 알고리즘들에 대해서 살펴보자.

 

4. HMM 알고리즘

HMM 알고리즘들에는 대표적으로 모델 파라미터가 주어진 상태에서 시작하는 Probability Evaluation, Optimal Sequence Detection이 있고 주어진 데이터들로부터 파라미터를 추정해나가는 Parameter Estimation 알고리즘이 존재한다. 

 

4-1. Probability Evaluation

이 알고리즘은 모델 파라미터가 주어지고 관측된 Sequence 데이터가 여러개의 모델 파라미터로 각각 들어가보면서 각각으로 계산되는 likelihood 중 가장 큰 값 즉, '가장 그럼직함'을 계산하는 알고리즘이다. 따라서 이 알고리즘은 Parameter(3번 목차 HMM의 파라미터인 θ값)가 주어졌을 때, 관측데이터 값이 나올 확률을 찾아주는 것이다

 

Probability Evaluation은 모든 상태의 모든 관측을 모두 고려한다.

 

이제 Probability Evaluation 알고리즘의 예시를 통해서 일반화 식도 같이 살펴보자.

 

Probability Evaluation 예시

위 예시는 파라미터가 주어졌을 때, Sequence 형태인 관측 데이터(O)가 '산책, 산책, 청소, 쇼핑'으로 나왔을 확률을 구하는 예시이다. Probability Evaluation 알고리즘을 적용하기 위해서 '비'와 '해' 2가지의 모든 상태를 고려해 계산을 하게 된다. 그런데 위와 같이 직접 계산을 하게 되면 계산량이 어마어마하게 많아지므로 '동적 프로그래밍(Dynamic programming)' 방법을 통해 계산을 간소화 시켜야 한다.

 

다음 그림은 위의 예시를 일반화하여 구하려는 Likelihood의 최종적인 수식이다.

 

Probability Evaluation의 일반화 수식

 

이제 위에서 언급했던 Probability Evaluation의 계산량을 줄여주기 위해 사용하는 동적 프로그래밍의 2가지 알고리즘에 대해서 알아보자. 알고리즘을 이해하기 위해 예시를 들을 것이다. 예시는 최대한 누가 보아도 이해할 수 있을 정도로 필자가 다시 필기로 재구성한 그림들이다.

 

#Dynamic Programming

#-1. Forward 알고리즘

 

Forward 알고리즘

 

#-2. Backward 알고리즘

Backward 알고리즘의 특징은 초기값을 1로 설정하는 것이다. 즉, π라는 초기값을 설정할 수 있는 Forward 알고리즘과는 달리 Backward 알고리즘에서는 마지막 time step에서 모든 상태에 대한 초기값을 1로 설정한다.

 

Backward 알고리즘

 

4-2. Optimal Sequence Detection

이 알고리즘은 최적의 시퀀스를 찾아주는 알고리즘이다. 즉, 시퀀스 데이터가 주어진 파라미터(모델)에 들어갔을 때, 모델이 해당 시퀀스를 보고 마치 "이 시퀀스의 첫번째 관측치는 A라는 상태에서 나온 것이고, 두번째 관측치는 B라는 상태에서 나온 것이고..." 하면서 상태에 대한 Optimal Sequence를 찾는 알고리즘이다.

 

이 알고리즘을 이해하기 위해서도 필자가 직접 필기로 재구성한 예시를 통해 이해해보자. 최대한 이해하기 쉽도록 구성했다. 필기를 읽으며서 중점을 두어야할 점은 다음과 같다.

 

• Forward 알고리즘 + Back Tracking 알고리즘을 함께 사용

• Back Tracking 할 때 가야할 길목(index)은 Forward 알고리즘을 진행할 때 가장 Promising한 State에 길목(index)을 미리 세워 놓는다.

• Back Tracking할 때 가야할 길목(index)은 밑의 그림에서 초록색 형광펜으로 표시한 부분이다.

Optimal Sequence를 찾는 알고리즘

 

4-3. Parameter Estimation

이 알고리즘은 기존의 2가지 알고리즘과는 달리 파라미터가 주어지는 것이 아닌 데이터들을 보고 최적의 파라미터를 계산하여 모델링하는 방법이다. 구체적으로 사용하는 알고리즘은 Baum-Welch 알고리즘이다. Baum-Welch 알고리즘은 Maximum Likelihood를 만족하는 파라미터를 찾는 방식이다. 즉, 이전 포스팅에서 배웠던 EM(Expectation Maximum) 알고리즘을 사용하게 된다.

(EM 알고리즘에 대해 궁금하다면? https://techblog-history-younghunjo1.tistory.com/88 )

 

Parameter Estimation의 E-step

 

우선 State에 대한 확률변수로 Z를 정의하고 이에 대한 확률분포함수 P(Z)를 정의해준다. 그리고 이에 대한 Expectation값을 구하게 된다. 

 

다음은 위 단계에서 구한 기댓값(Expectation)을 최대화시키는 M-step을 거치게 된다.

 

Parameter Estimation의 M-step

 

이 때 HMM의 파라미터 θ값에 포함되는 A, B, π의 각 합이 1임을 만족시키면서 기댓값의 최대값을 구해야 하기 때문에 라그랑지 승수방법을 이용하게 된다. 그리고 업데이트된 각 파라미터에 대한 수식은 위와 같아진다.

 

이 때 B에 대한 업데이트 수식을 살펴보게 되면 idx라고 표시되어 있는 특수한 함수가 존재한다. 이는 함수 안의 조건을 만족하면 1, 만족하지 않으면 0으로 되는 일종의 True/False로 나오는 Boolean 종류의 함수라고 생각하면 쉽겠다. 이러한 특수한 함수를 집어넣은 이유는 Back Tracking을 수행할 때 Forward 알고리즘에서 지정해놓았던 가장 Promising한 State로 가는 길목(index)을 찾아가기 때문이다. 즉, 함수 안의 조건을 만족하면 사전에 지정해놓았던 길목(index)으로 잘 찾아간 것이고, 함수 안의 조건을 만족하지 못하면 0값이 되므로 다른 길목(index)으로 가는 방법을 계산하지 않게 된다.

 

지금까지 HMM의 모델과 HMM이 문제를 해결하기 위해 사용하는 알고리즘을 살펴보았다. 이제 HMM에 대해서 간략하게 정리해보고 포스팅을 마무리 해보자.

 

• HMM은 Generative Model이다. 왜냐하면 한쪽 방향에서 다른 방향으로(Forward, Backward 알고리즘) 흐르기 때문이다. 따라서 Sequence 패턴 모델링에 적합하다.

• 한글 형태소 분석, 수화분석 등에 응용이 되는 방법이다.

• 2개 이상 간격의 상호관계를 갖는 모델링(즉, r=2 이상인 Markov Property를 갖는 HMM)을 수행할 시 계산할 파라미터 개수가 너무 많아진다.

• Parameter Estimation도 EM 알고리즘을 사용하기 때문에 GMM(Gaussian Mixture Model)과 마찬가지로 Global optimum을 찾을 수 없다.