Machine Learning

난다로~ 2008. 4. 13. 12:12

 

[출처] KISS ILVB Tutorial(한국정보과학회) 에서 발표( Dr. Sung-Jung Cho)된 내용 중 발췌 


얼마전에 Markov Model에 대해서 주석을 달아서 올렸는데, 이번에는 HMM에 대해서 알아보자

 

지난번 글에서 언급되었듯이 MM과 HMM의 차이점은 상태(state)를 관측할 수 있는가에 달려있다.

 

날씨나 동전던지기와 같은 사건(event)에서는 쉽게 상태를 알 수 있지만, 그렇지 않는 사건들도 존재한다.

 

예를 들어,  아래와 같은 문제가 있다고 하자.

 

 

이와 같이 3개의 통(상태 1,2,3  -> N = 3)에는 빨간색, 파란색, 녹색 공들이 6개(M = 6)가 들어있는데, 하나의 통에 들어있는 서로다른 색의 공들은 같은 숫자로

들어있지 않다.

이 그림에서 나오는 화살표는 Markov Model에서 처럼 한 상태에서 다른 상태로 전이할 확률(transition probability)이다.

그런데, 각각의 상태에 도착하면 그 상태에서는 빨간, 파란, 녹색 공중 하나를 어떤 확률에 기반해서 뱉어낸다고 한다. 약간 crazy한 콜라 자판기를 생각해도 된다.

3개의 자판기에 빨간, 파란, 녹색 콜라캔이 위의 그림처럼 들어있고, 동전을 넣으면 어떤 확률에 의해서 지맘대로 토해내는 그런 자판기 말이다~

 

이렇게 어떤 확률에 의해서 콜라를 뱉어내는 자판기는 아래와 같이 generation process로 모델링 할 수 있다.

 

 

위 그림에서 ouput process가 바로 어떤 상태 q에서 어떤 ball  x 를 뱉어낼 확률이며 이는 조건부 확률 f(x | q)로 나태낼 수 있다.

그리고  1, 2, 3번 상태에 대한 전이 확률을 알고 있기 때문에 이 부분은 Markov Model을 이용해서 모델링할 수 있을 것이다.

 

자 그럼 이제 우리는 각 상태로의 전이 확률과 각 상태에서의 생성 확률을 모델링했다.  그렇다면 아래와 같은 문제를 생각해 볼 수 있을 것이다.

 

블랙박스에는 관측할 수 없는(unobservable) 3개의 상태들이 있고, Markov Process를 따른다. 각 상태에서는 위의 그림처럼 '빨간->파란->파란' 순서로 공들이

출력된다는 것을 관측했다(observed)

 

이러한 정보로 부터, 우리가 알고 싶은 것은 '과연 감춰진 state sequence는 무엇인가?'일 것이다.

 

음....  약간 거꾸로 생각해서 만약에 '빨간, 파란, 녹색' 공들 그 자체가 state이고 그들간의 전이 확률을 계산한다면 굳이 근본적인 상태들의 sequence를 알 필요가

없을 수도 있다. 하지만, 우리는 다음에 나올 공에 관심이 있는 것이 아니라 과연 어떤 근본적인 상태가 있었는지에 관심이 있기 때문에, 이런 가정은 필요없다.

 

아무튼 이 문제를 풀기 전에 우선, 전체적인 Notation을 정리하고 넘어갈 필요가 있다.

 

여기 기술된 notation은 HMM을 정의이며 문제를 풀기 위한 기본 절차라고 할 수 있다. 앞으로 만약 어떤 문제를 HMM으로 풀고자 한다면, 이와 같이 기본

notation을 정리하고 들어가면 편하겠다.

다음으로 정리할 것은 Markov Model과 generation process를 결합한 그림이다. 이 그림이야 말로, HMM의 핵심이라 할 수 있다.

 

 

 이 그림이 나타내는 것은 MM에서도 배웠지만, 일단 기본적으로 Markov Model을 따른다는 것이고, 추가적으로

 어떤 상태 q에서 x를 출력할 확률은 그 이전 상태와는 완전히 독립적이라는 가설이다.

 (conditional independency assumption)

 근데 왜 'Bayesian network' 이라는 말이 있을까? 이는 HMM도 '베이지안 네트웍' 모델링 기법에 그 기반을 두었기 때문인데, 좀더 상위 모델 개념이라고

 이해하고 넘어가자.

 

 지금까지, 해결하려고 하는 문제를 정의하고 모델링까지 했으니, 이제 진짜 우리가 풀려고 하는 문제를 다시 정의해 보자.

 

 

 

이 그림에서 initial state distribution은 그 첨자가 1 이다. 이는 반드시 HMM의 경우 start state가 존재해야 한다는 의미이다. 그 시작 상태에서 어떤 output을

출력할 확률 분포가 필요한 이유이다.

 

그러면, 위와 같이 좀더 보기 좋게 정리된 문제를 가지고 우리는 실제 어떤 문제를 풀어야 할까? 

아래 그림에 잘 정리가 되어 있다.

 

 

첫째, 관측된 output들이 sequence에 대한 확률이다. 이건 약간 Markov Model을 계산할 때와 비슷해 보인다.

        ==> 다른 점은 모델 파라미터 '람다'가 들어가 있는 것이다.

둘째, 관측된 output sequence를 가지고 가장 그럴 듯한 state sequence를 찾아내는 것이다.

        ==> 사실 진짜로 알고 싶은 것은 바로 이것이다.

셋째, 학습에 관련된 이슈인데, 이는 학습 데이터를 가지고 있는 상태에서 모델 파라미터 '람다'를 적절하게 결정해야 할 필요가 있기 때문에

        학습 알고리즘을 통해서 '람다'를 최적화 해야 한다.

 

지금부터 기술되는 것은 이 세가지 문제를 푸는 방법이다. 관심없는 분은 넘어가시길 바란다. 좀 복잡하니....

 

이제 첫번째 문제를 해결해 보자.

 

음... 먼가  Markov Model을 풀 때와 비슷해 보이지 않는가?  output sequence가 x1 ~ x8 일때 그에 대응하는 state sequence Q는 엄청나게 많다.

하지만, 확률로 표현하면, 전부 OR 이기 때문에 단순히 더하면 된다. summation 안에 들어가 있는 수식은 조건부 확률을 Bayesian Theorem에 의해서

뒤집은 결과이다. 이 수식을 어떻게 계산할까?  머리가 약간 아플 수도 있지만  하나의 Q = q1 ~ qT에 대해서만 생각해 보면,

아주 위쪽에서 그려진 Bayesian network representation을 이용해서 아래와 같이 풀어 쓸 수 있다. 그리고 이 결과를 계산하면 된다.

 

하지만,  이것도 Markov Model처럼 DP 기법(수학적 귀납법을 생각)을 사용하면, 아래와 같이 빠르게 계산할 수 있다.

 

즉, 시간 t 에서의 확률은  시간 t-1 에서의 확률을 알면,  t-1 에서 t 까지의 모든 path만 고려해면 된다는 이 엄청나게 깔끔하고 단순한 수식!!!

멋지다 @.@

아무튼 이 수식에 Forward Algorithm이라는 말이 들어간 것은 계산 순서가 1부터 t까지 순차적으로 계산하기 때문에 그런거고 별 의미는 없다.

다시한번 정리하면

 

 DP 기법에서 자주 나오는 notation인데, 다시 한번 숙지하고 넘어가자. DP는 아래와 같이 구성되어 있다.

1. initialization

    - 고등학교때 수열 문제 풀때, 초기 a1, a2 등등을 지정하고 가는 것 처럼 초기값 설정

2. induction

    -  a(n)과 a(n-1)의 관계를 수식으로 표현

    - 그래서 귀납법(induction)이다.

    - 그래서 deduction이 아니다.

3. termination

    - 계산하려고 하는 대상이 a(100) 인 경우, a(101)은 계산할 필요가 없다. 그래서 종료 조건이 반드시 필요하다.

    - 프로그램으로 작성한다고 생각하면 recursive call이 되겠는데, 여기에 종료 조건이 없으면 무한루프에 걸리니까...

 

 

다시 원래 문제로 돌아가서, '아니 그럼 forward algorithm'이 있으니 'backward'도 있겠네? 하시는 분도 계실 것이다. 그렇다!

backward 방향으로 계산하면 똑같다. 다만, 초기 상태까지 와 봐야, 그 중간에 저장된 확률 값들을 알 수 있다는 단점이 있다.

 

 

 아무튼, 자 ~ 이제 첫번째 문제는 해결된 셈이다.  이젠 어떤 output sequence가 주어져도 그 확률을 계산할 수 있다.

 

 다음으로, 두번째 문제를 풀어보자. 관측된 output sequence로부터 가장 그럴듯한 state sequence를 구하는 문제인데, 

 most probable  sequence decoding이라고도 한다. 즉, 아래와 같은 문제이다.

 

 위 수식에서  argmax 는 해당 확률 값을 최대로 하는 state sequence Q를 찾는다는 의미이다.

 이 문제를 해결하는 데, 가장 잘 알려진 알고리즘이 바로 Viterbi Algorithm이다. 이것도 DP 방법을 사용해서 문제를 해결하는데,

 관점은 지금까지와는 조금 다르게, path의 확률을 계산하는 데 초점이 맞춰져 있다.

 

 단순하게 생각하면 시간 t의 여러개의 상태에서 시간 t+1의 어떤 상태 q(j)로 오는 path는 상태의 숫자만큼 존재한다. 그런데, 여러개의

 path에서 어떤 path로 오는 것이 가장 그럴듯 한가? 라는 문제를 생각해 보면, 아래와 같이 두가지를 고려해야 한다.

 1. t의 어떤 상태에서 t+1의 상태 q(j)로의 전이 확률  : a(i,j)

 2. q(j)에서 관측된 output x(t+1)의 확률 : b(j, x(t+1))

 즉, 이 두가지 확률을 곱한 값이 최대가 되는 path를 선택하면 된다.

 이 문제를 DP 문제로 확대시켜서 수학적 귀납법으로 표현하면 아래와 같이 되는 것이다.

  

 위에서 path probability는 잘 알겠는데, 그럼 path node는 먼가?  이는 path probability에서 destination의 output 확률을 제거하고

 , 그 확률이 최대가 되는 이전 상태이다.  현재 어떤 output이 있는 지 고려하지 않고 계산한다.

 

 

음...?  그런데 여기서 path backtracking은 무엇인가?  HMM을 공부할때, 자주 하는 착각중에 하나는 바로

'그럼 처음 상태에서 다음 상태로 가는 path 중에서 path probability가 가장 높은 path를 선택해고, 선택된 그 상태에서 다음으로의 path들을

 계속해서 선택해 나간다면 최종적으로 가장 그럴듯한 path가 나오는 게 아닌가?' 이다.

 

 답은 '아니다' 이다. 이 방법은 그냥 단순히 local search를 하는 것 뿐이고, viterbi algorithm은 global search를 하는 알고리즘이다. global search는

 모든 가능한 path를 전부 계산하기 때문에 너무 시간이 오래 걸린다. local search는 그냥 단순하게 현재 눈앞에 가장 이득인 놈을 선택해서 탐색하는 방법으로

 greedy search라고도 한다. '탐욕스런 탐색'이라니~ 정말 이름 잘 지었다!!  사설이지만, 우리의 인생의 방향을 선택할때도 가끔 이러지 않을까?

 

 아무튼, viterbi algorithm은 가장 optimal한 path를 선택해야 하기 때문에 끝까지 가본 이후, 마지막 상태부터 거꾸로  back tracking을 하면서

 가장 확률이 높게 나오는 이전 state를 선택해 가면서 처음 상태로 되돌아 가야 최종적인 결과가 나오는 알고리즘이다.

 

 그래서 path backtracking 공식이 있는 것이고...  위 그림에서 화살표가 거꾸로 되어 있는 이유도 이것 때문이다. ^^

 

 자 이제 여기까지 왔으면, HMM으로 모델링 된 어떤 문제에서 output sequence를 알면 대응되는 state sequence를 계산할 수 있겠다.

 대단하지 않은가?

 

 이제 마직막으로 세번째 '모델 학습'에 관련된 문제만 해결하면 되는데, 그러기 전에 우선 NLP에서는 어떤 응용이 있는 지 먼저 살펴보고 넘어 가자.

 

 NLP 분야에서 HMM이 쓰이는 대표적인 모듈은 POS(Part-of-Speech) Tagger이다. 즉, 아래와 같은 문제이다.

 

 [출처] 부산대학교  한국어 정보처리 연구실 - 품사태거 - 정성원 

 

 

 한국어 형태소 분석기는 어떤 어절에 대해 가능한 모든 형태소 분석 결과를 출력해 준다. 하지만, 우리가 필요한 것은 이중에서 진짜로 문맥에 맞는 형태소 분석

 결과이기 때문에, 이 문제도 HMM으로 모델링해서 해결할 수 있다.

 어절을 output , 형태소 조합을 state라고 한다면 HMM에 쉽게 대응해 볼 수 있을 것이다.

 태거를 HMM으로 모델링한다면, output과 state는 얼마나 될까?  일단 state는 그렇게 많지 않다. 형태소 분석기 내부에는 하나의 어절에 대해 구성 가능한

 형태소 결합 규칙을 기술해 두는데, 이 규칙의 수가 state의 수가 될 수 있다. 하지만, output의 숫자는 엄청나게 많다. 따라서, 일반적으로 태거를 구현할때는

 형태소 분석단계에서 최대한 분석의 수를 줄인 이후에 태거에서 HMM 기법을 통해 가장 적합한 품사를 결정한다. 즉, 중의성이 있는 어절들에 대해서만

 가능한 형태소 분석 결과를 출력하고, 그렇지 않은 경우는 고려하지 않는다.

 

 어쨌든, 이러한 품사 태거를 만들기 위해서는 대용량의 품사태깅된 학습 말뭉치가 필요한데, 이 말뭉치는 보통 아래와 같이 생겼다.

 

 나는 학교에 간다   -->   나/대명사+는/조사  학교/보통명사+에/조사  가다/동사+ㄴ다/종결어미

 하늘을 나는 새를 보았다 -->  하늘/보통명사+을/조사  날다/동사+ㄴ/관형형어미  새/보통명사+를/조사 보다/동사+았/선어말어미+다/종결어미

 .....

 

 우리는 이러한 학습 말뭉치를 가지고  상태전이확률(품사간 전이 확률, 편의상), 생성확률(어휘 생성 확률)을 계산할 수 있다.

 

 다시 본론으로 돌아가서, 세번째 문제는 모델의 파라미터를 학습 데이터로부터 최적화하는 것인데, 품사 태거를 학습시키는 문제에 적용해 보면 확률 데이터를 좀더

 정교한 방식으로 계산해서 얻겠다는 의미도 될 수 있다. 어떤 품사에서 출력되는 output의 숫자는 엄청나게 많아서 학습시킬 때 언제나, 데이터 부족 문제

 (data sparseness problem)가 생기는 것은 피할 수 없다. 즉, 관측된 데이터만으로는 관측되지 않은 확률 값을 계산하는 데 심각한 문제가 있다는 의미이다.

 이러한 문제를 해결하기 위해서 보통 우리가 하는 일은 "모델을 잘 만든다" 이다.

 조금 우습지만 이게 정답이다. 잘 만들어진 모델이 있으면, 잘 모르는 확률도 해당 모델을 기반으로 해서 좀 더 그럴듯하게 근사값을 계산할 수 있다.

 아주 대표적인 예가 있는 데, 바로 '정규분포(standard distribution)'이다. '학교 성적, 인구 분포 등등의 현상은 대부분 정규분포에 근사한다' 라는 게 우리의 가설이고

 이를 모델링한 것이 바로 정규분포이다. 따라서, 우리는 모든 사람을 일일히 호구조사하지 않아도 대충 몇살부터 몇살까지 몇명이 있는 지 근사값을 계산할 수

 있는 것이다. 그러니, 잘 모르면 모델을 잘 만들면 된다. 사설이지만, 가장 완벽한 모델은 무엇일까? 음... 바로 수학이다!!  한치의 오차도 없는 완벽한 모델 ^^

 

--------------------------------------------------------------------------------------------------------------------------------------------------

[여기서 잠깐]

Q) 위와 같은 품사 태깅된 말뭉치가 있는 경우에도 파라미터 '람다'를, 좀더 정확히 말하면 state transition 파라미터를, 학습시켜야 하나?

 

A) Linguist's Guide to Statistics [참고 : http://blog.daum.net/hazzling/16884279]

    여기에 보면 아래와 같은 내용이 나온다.

 

 

   즉, "underlying state sequence는 unknown이고 오직 signal sequence 즉, output sequence만 학습데이터로 가지고 있는 경우에만

    state transition probability parameter를 Baum-Welch reestimation 알고리즘 등을 이용해서 추정한다"

   따라서, '그럴 필요 없다'가 정답이다. 다만,  품사조합(state)들 간의 transition 데이터가 좀 부족하면 보정작업등을 해서

   학습 데이터의 부족문제를 약간 해결할 수 있을 것이다.

   아래에서 언급되는 내용은 우리가 오직 output sequence만을 학습 데이터로 가지고 있는 경우에 어떻게 state transition에 관한

   정보를 끄집어 낼 것인가에 대한 것이다.

--------------------------------------------------------------------------------------------------------------------------------------------------

 

 아무튼, 우리는 관측된 데이터만 가지고 모든 상태전이확률, 생성확률을 잘 구할 수 있도록 모델을 구해야 하며, 이것이 지금부터 언급될 내용이다.

 

 보통 HMM의 파라미터 '람다'라 하면 아래 3가지를 의미한다.

 

 1. 상태전이확률  : A

 2. 생성확률 : B

 3. 초기확률 : py

 

 따라서,  람다 = ( A, B, py )  이렇게 표현하고  실제 우리가 관측한 데이터를 X 라고 한다면,

 우리가 만들려고 하는 어떤 모델은 '람다'를 조건으로 할때, 관측 데이터 X를 가장 잘 표현해야 한다. 이런 종류의 문제는 Likelihood 를 최대한 높여야 한다고

 보통 얘기하는데, 잠깐 Likelihood에 대해서 알고 넘어가자.

 

 예를 들어서, 동전던지기 사건에서 앞면이 나올 확률 p를 동전던지기 사건 모델의 파라미터라고 하고, 1000번 던저 나온 결과값 즉, 관측 데이터를 우리가 가지고

 있다고 하자. 1000번의 550번은 앞면, 450번은 뒷면이 나왔다. 자~ 그럼 어떻게 하면 확률 p를 가장 잘 결정할까? 일단 p = 0 으로 해보자.

 엥?  만약 그렇다면 관측한 데이터와 완전히 동떨어진다. 그럼 p = 1 로 하면?  역시 마찬가지다. p = 0.5 로 해도 관측된 데이터와는 조금 미스매치다.

 그래서 관측데이터를 가장 잘 표현할 수 있도록 조금씩 p값을 앞뒤로 조정해 나가면 p = ( 550 ) / ( 1000 ) = 0.55 로 결정된다. 이런 조정 작업이 바로

 모델 파라미터 학습이라고 하고, 여기서 사용된 개념이 바로 'Likelihood를 최대로 해서 모델 파라미터를 결정한다'는 것이다.

 그런데, 관측데이터에 너무 지나치게 모델 파라미터를 학습시키면 어떨까? 사실 동전을 많이 던지면 p 는 0.5에 접근한다. 실험을 적게하면 Likelihood로

 계산한 모델 파라미터 p는 0.1일 수도 있다. 이것이 보통 우리가 얘기하는 overfitting 되었다는 것이고, 거꾸로 생각하면 학습 데이터가 부족하다는 것이다.  

 (data sparseness problem)

 

 기계학습의 아주 기초적인 개념이 사실 고등학교때 배운 동전던지기 확률 모델에 거의 다 들어있다는 것을 요새 새삼 깨닫게 된다 @.@

 

 

 

  

 다시 파라미터 학습 문제로 돌아가면, 결국 Likelihood를 최대화하도록 람다를 학습시켜야 하는데 이를 수식으로 풀어내면 위의 그림과 같다.

 P( X | 람다 ) 는 3가지 문제 중에서 첫번째 문제를 해결할 때, 위의 수식처럼 summation 형태로 바꿀 수 있는데, P( Q | 람다 ) 는 state transition이

 숨겨져 있어서 구하기 어렵다. 따라서, estimation을 해야 한다. 그럼 어떤 방법을 사용해야 할까? 

 일반적으로 이런 문제에서는 EM(Expected Maximization) 알고리즘을 사용한다. EM도 결국 Likelihood를 최대화 하도록 파라미터를 학습시키는

 방법론이라고 할 수 있는 데, 좀더 잘 정리되어 있다는 점이 다를 뿐이다.

 ( 위에서 기술된 Baum-Welch reestimation은 EM 프레임웍을 HMM에 최적화시킨 알고리즘이다. )

 

 EM 알고리즘 참조 ==> http://blog.daum.net/hazzling/17067790

 

 

 

 잘 이해하기 힘든 그림이다.  이것 말고, 다른 문서를 참고하자.

 

 Linguist's Guide to Statistics [참고 : http://blog.daum.net/hazzling/16884279]

 여기에 있는 HMM chapter를 보면

 output sequence  =  o1, o2, .... , oT

 이런 관측 데이터가 있을 때,

 time (t)의 상태가 si 이고

 time(t+1)의 상태가 sj 일 조건부 확률을 아래와 같이 정의할 수 있는데,

 

 이 확률 값은  forward, backward probability의 조합으로도 표현할 수 있다.  

 

 

 그리고,

 가장 아래 부분은 관측렬이 아래와 같고

 output sequence  =  o1, o2, .... , oT

 time ( t ) 일때 상태가 si 일 확률은 

 partition 이론으로 부터, summation으로 풀어쓸 수 있고

 이 풀어쓴 결과가

 결국

 위 그림의 마지막 라인과 같다는 것을 알려준다.

 

 이것으로 부터 아래와 같은 4가지 fact를 추출할 수 있다.

 

  

 0) time 1 에서 상태 si 로 시작할 확률값

 1) si --> sj 로 transition하는 횟수의 평균값

 2) si 로부터 어떤 다른 상태로의 transition 횟수의 평균값

 3) si 에서 어떤 시그널(output)을 뱉을 평균 횟수

 

 그리고, 위에서 나온 fact를 이용해서,

 

 초기 py 값 :  time 1 에서 각각의 상태 si로 시작할 확률값

 pij   :  ( time 1 ~ T-1  사이에서 si -> sj transition 평균값 )  /   (  time 1 ~ T-1 사이에서 si 로 시작하는 transition 평균값 )

          이것이 바로  si --> sj  전이 확률의 평균값(기대값)

 aij   :  ( time 1 ~ T 사이에서 상태 si가  signal(j)를 출력할 평균값 ) / ( time 1 ~ T 사이에서 si 로 시작하는 transition 평균값 )

 

 

  이와 같이 모델 lamda를 계산할 수 있다.

 

  우리가 만약 어떤 m개의 관측 데이터를 가지고 있다고 하자.

 

  o11  o21  o31 ....  oT1

  o12 o22  o32 ....  oT2

  .........

  o1m o2m  o3m ....  oTm

 

  BW 알고리즘은 이것으로 부터 transition proability를 추정해 내는 알고리즘이라 할 수 있는데,

  그럼 우선 어떤 것을 먼저 설정해 줘야 할까?

 

  일단, number of state ( N ) 값과 number of observation ( M ) 값을 설정해야 한다.

  M 값은 관측 데이터로 부터 자연스럽게 설정되고

  N 값은 미리 알고 있다고 가정하자 ( 문제의 종류에 따라 다르다.)

  초기 시작 상태에서의 emission probability py는 그냥 대충 설정해 주면 된다. 합이 1이 되도록....

  마지막으로, transition probability aij, emission proability pij 도 랜덤하게 설정해 둔다.

  이 상태의 모델이 바로 lamda(0)

 

  자 이제 이러한 상태에서, 위의 그림에 나온 공식을 사용해서 계속 parameter를 최적화하는 작업을 진행해야 한다.

 

  위의 공식을 뜯어보면, 결국 최종적으로 forward, backward probability(variable)을 알아야 계산 가능하다는 것을 알 수 있다.

  그렇다면, forward, backward 확률은 어떤 순서로 계산하는가?

 

  forward는 기본적으로 time 1에서 먼저 계산하고 그 다음 time 2, 그리고 그 결과를 이용해서 time3 ...

  이런 식으로 해서 최종적으로 time T 까지 계산한다.

 

  backward는 forward와는 반대로 time T 부터 계산하고 거꾸로 time 1 까지 가면서 계산한다.

  ( 물론, time T에서는 초기값은 확률 합이 1이 되도록 임의로 설정해 둔다)

 

  이러한 과정을 통해서 alpha(t), beta(t) 값을 전부 어떤 테이블에 저장해 두고 사용한다.

  

  아래 그림을 보자.

 

  [reter to] http://nlp.korea.ac.kr/~kshan/resources/AlgorithmsForHMM.ppt

 

 

 

 

 초기에 initial guessing을 통해서 설정된 전이확률 및 생성확률을 가지고

 alpha, beta를 계산하고

 이를 이용해서 다시  아래를 계산한다.

 

 

 

  그러면 전이확률 및 생성확률, 초기확률이 변화할 것이다.

 

   또, 변화된 모델에서 alpha, beta를 구한다.

 

   이 과정을 아래 그림과 같이 반복한다.

 

   [refer to]  http://www.facweb.iitkgp.ernet.in/~sudeshna/courses/ml08/hmmkanungo2.pdf 

 

 

  아... 이제 무한루프에서 탈출한 기분 ^^

 

  그런데 이러한 BW 추정에도 단점이 있다.

  [reter to] http://nlp.korea.ac.kr/~kshan/resources/AlgorithmsForHMM.ppt

 

 

 어쩔수 없는 문제이긴 하지만.... ^^;

 

 HMM을 이해하는 데 있어서 가장 헷갈리는 부분이 바로 이 BW 알고리즘이 아닐까 한다.

 흠... 직접 구현해 보지 않으니, 개념적으로만 맴돌고 약간 모호한 느낌이긴 하다.

 구현이라...

 

 이미 구현된 패키지를 사용하는 방법 관련해서

 --> [참고] http://blog.daum.net/hazzling/16781469

 

이전 댓글 더보기
2년전에 Twoply Hmm으로 만든 형태소 분석기 트레이너 소스를 날리는 바람에,
이론 좀 다시 보려고 찾았는데, 정말 완벽한 정리군욤 ^^

소중한 자료 출처남기고 퍼가도 될까욤??
제 블로그 NLP 폴더에 넣어두겠습니다.(__)
넵 ^^
현재 제가 HMM이용해서 마우스 모션 인식하려고 하는데요.
관련 윈도우용 소스, 라이브러리등을 구했는데요.
어떻게 적용해야 할지 몰라서요.
실례지만 개발관련해서 lovealbert@naver.com 연락주시면 감사하겠습니다. (사례금 있습니다.)
HMM관련 영어자료밖에 없어서 고생했는데 덕분에 많은 도움 되었습니다.
별말씀을<img src="http://cafeimg.daum-img.net/pie2/texticon/texticon28.gif" value="~" /> <img src="http://cafeimg.daum-img.net/pie2/texticon/texticon30.gif" value="^^" />
헐...너무 어렵네요...그래도 참조해서 잘보겠습니다~^^ 트위터로 주소 좀 옮겨놓을게요~
넹~~
이런 가뭄에 단비같은 포스트가...ㄷㄷㄷㄷㄷㄷ
수학적인 지식이 너무 부족해서...책을 보다가 막혀서 죽어가고 있었는데
한글로 이렇게 친철하게..ㅠㅠ 감사합니다~ 잘보구가용~ㅎ
소스인 pt가 너무 좋아서 주석달았을 뿐인데요 뭘~ ^^ 암튼 감사합니다.
정말 도움이 많이 되었습니다. 스터디를 위해 논문 발표를 해야되는데 자료를 좀 인용해도 될까요??
아 넵~ 상관없습니다. 혹시 설명에 문제가 있을수도 있지만, 너그러이 봐주세요 ㅎㅎ
좋은 자료 감사합니다.~
^^
정말 좋은 정보 감사합니다. 많은 도움이 될것 같습니다.
별말씀을요~~ ^^
좋은 정보 감사합니다. 제 카페로 퍼가도 될까요?? 불편하시면 말씀해주세요~ 주석보면서 많은 도움 되었습니다.
아 넹~ 도움이 되신다면 ^^
좋은 자료 감사합니다. 덕분에 이해가 쉽게 됐네요. 블로그에 담아갈께요^^
넹~~ :)
자료 담아갑니다. dev.naver.com/projects/tali
넹~~
안녕하세요 HMM 입문한 학생입니다..
HMM을 이용해서 어떤 데이터를 실시간으로 예측하는 프로그램을 만들어야하는데..
이제 막 hmm해서 아는게 없어서 그런데 ㅜㅜ 어떤 방식으로하면되는지 좀 여쭤봐도 될까요..ㅠ
음 hmm은 sequential tagging 문제를 푸는 알고리즘입니다. 해결하려고 하는 문제가 이렇게 모델링이 가능한지 우선 확인해보셔야할 것 같아요. 만약 그렇다면 가지고 계신 데이터를 hmm에 맞게 표현하고(즉 state와 관측 symbol로 이루어진 그래프로 표현) hmm을 이용하시면 됩니다. 오픈소스가 많이 있기때문에 다운받아서 적용해보셔요
너무너무 좋은자료 담아갈게요, 감사합니다 ! 덕분에 HMM을 이해하는데 도움이 많이되었습니다 ^0^
^^ 원본 자료가 좋아서 그런것 같네요~
우어, 열등감 지대로네, 댓글 보니깐 이해가 쉽게?ㅋ 도대체 수학을 어떤 책으로 공부하셨길래 술술되는지 궁금합니다. 결론은 내 뇌가 썩었다.ㅠ
관측 심벌 확률이 그냥 단순히 주머니에서 색깔별로 나올 공의 확률을 행렬로 나타낸거군요...?
넵 그렇습니다~ 각 상태 주머니에서 색깔별로 공이 나올 확률을 행렬로 표현한거에요
안녕하세요 NLP 와 확률모델에 관심있는 초보 학생입니다. ^^ 잘 이해가 가지 않는 부분들이 조금 있습니다 ㅠ 다른 HMM 논문에서는 viterbi 알고리즘이 안나오는 논문도 있는데...여기선 말씀하시는 viterbi 알고리즘이 β-pass 알고리즘 (back-word)을 말하는 건가요?? 그리고 for-word 알고리즘에서 이미 상태 전이확률과 관측확률의 곱으로 각 상태에서 다음 상태로 갈수 있는 최적의 path 를 알아내는데 다시 백트랙킹을 하는 이유가 잘 와닿지 않네요 ㅠㅠ T 에서의 확률은 T-1 에서 T 의 전이확률과 T에서의 관측확률 그리고 T+1 에서 T 의 전이확률로 정하는 건가요??
1. forward, backward 알고리즘은 output sequence의 확률을 계산할때나 모델 파라미터를 학습할때 사용하고
viterbi 알고리즘은 이미 HMM 모델이 학습된 상태에서, 어떤 output sequence가 주어졌을때
그것을 생성해낸 가장 그럴듯한 state sequence를 찾아내는 decoding 방법입니다.
2. forward 알고리즘은 어떤 상태 i에서 j로 전이 가능한 모든 가능한 패스에 대해서
확률을 합하게 되어 있습니다. 따라서, 그것이 최적의 확률이 아니구요. output sequence가 나올
확률일 뿐입니다.
3. backtracking을 하는 이유는 viterbi 알고리즘이
t=1에서 t=T까지 진행하면서 각 상태 i에서 j로 전이 가능한 모든 가능한 패스 중에서 가장 큰 확률값
(path probability, path node)을 각 단계별로 저장해 두는데요. forward에서는 모든 가능한 패스에 대해서
summation을 한다면 viterbi에서는 최대 확률값에 해당하는 path를 하나 선택해서 기록해 둔다는
것에서 차이가 납니다.
- path probability : i -> j로 가는 모든 패스에서 가장 확률이 높은 패스의 확률
- path node : 그런 확률을 보이는 이전 노드 i
t=T까지 진행하면 각 t별로 상태의 수만큼 path probability가 저장되어 있겠죠?
그럼 마지막 t=T의 각 상태들 중에서도 최대값을 갖는 노드 하나가 있을겁니다.
그 노드가 가지고 있는 이전 path node를 따라서 거꾸로 가서
다시 그 path node의 path node를 따라서 t=1까지 진행하면
t=1 ~ t=T까지 모든 가능한 패스중에서 최대 확률을 보이는 path를 찾을수 있는 것입니다.
더 자세한 사항은 아래 글에 나오는 그림을 참고하세요~
http://blog.daum.net/hazzling/17187116
와 친절한 답변 감사 드립니다 ^^ 덕분에 공부에 많은 도음을 얻고 있습니다 . ^^ viterbi 알고리즘은 학습된 후에 상태를 백트레킹하여 최적의 path node 를 찾는것이라면 그렇다면 제가 궁금한것은 β-pass 입니다. ^^ 람다를 학습 시킬때 Υ(i) = α(i)β(i) / P(O|X) 로 계산되어 지는데 α-pass 만 가지고도 확률을 계산해 낼수 잇는데 β-pass까지 보는 이유가 무엇인가요?
좀 길어서 https://github.com/dsindex/blog/wiki/%5BHMM%5D-forward-and-backward-variable 여기에 기술했습니다. :)
그리고 현재 CRF 도 공부하고 있는데 조금더 개념이 많이 어렵네요 ㅠㅠ 나이브 베이지안이나 마코브 처럼 joint probability model은 조금 이해가 쉬운 반면에 ㅠㅠ CRF 는 약간 핵심이 잘 보이지가 않네요 ㅠㅠ 특징 함수니 팩터노드 들로 각 상태의 모든 확률을 구한후 정규화 한후 맥시멈을 구하는거 같은데 ㅠㅠ 이해가 어렵습니다. 간략하게 설명 부탁드려도 될까요?ㅠㅠ
음 저도 CRF는 공부하고 있는 중이라 정확히는 잘 설명을 못하겠지만,
핵심적인 차이점은
1. Naive Bayesian은 p(x, y)를 계산하는 생성모델이고 HMM은 단지 Naive Bayesian을 sequential하게
확장한 버전일 뿐이라는 것
2. 비슷한 관점에서 CRF는 Maximum Entropy Model의 sequential한 확장이라는 것입니다.
따라서, CRF를 공부하기 전에 우선 Maximum Entropy에 대해 정확히 이해하면 도움이 될것 같네요.

저도 정리중인 자료가 있었는데 https://github.com/dsindex/blog/wiki/%5Bstatistics%5D-Naive-Bayesian,-HMM,-Maximum-Entropy-Model,-CRF
이 자료가 도움이 될 것 같습니다.
한가지 더 궁금한게 생겼는데요 ^^ backword 알고리즘을 사용할때 가장 오른쪽에 있는 노드의 초기값은 무슨 값으로 설정해야 하나요??
beta는 아래와 같이 정의됩니다.
beta(t, i)
= p( O(>t) | e(t) = s(i) )
= 시간 t에서 상태가 s(i)였는데, 그 다음 output sequence가 O(>t)일 확률

따라서,
beta(T, i)
= p( O(>T+1) | e(T) = s(i) )
= 시간 T에서 상태가 s(i)였는데,
그 다음 output sequence가 O(>T+1)일 확률

그런데,
관측열이 t=T까지만 존재하기 때문에 O(>T+1)에 해당하는 event는 어떤 empty event라고 보고
1건이라고 생각하면
(즉, output sequence o1, o2, ..., oT, end에서 end라는 어떤 가상 symbol)

p( O(>T+1) | e(T) = s(i) )
= num( 'T+1에서 empty event' AND e(T) = s(i) ) / num( e(T) = s(i) )
= 1

왜냐하면, 시간 T에서 어떤 상태에 있던지, 그 다음 시간 T+1에서 empty event가 발생하기 때문입니다.

따라서, beta(T, i) = 1, 1 <= i <= N

시간 T에서의 beta값은 전부 1로 초기화되어야 합니다.
안녕하세요? 네트웍을 공부하는 전기과 대학원생입니다. 뜬금없이 HMM 세미나를 준비해야해서 ^^; 정말 좋은 글 잘 읽었습니다!!

다름이 아닌 오타같은게 있는 것 같은데요, 가져오신 ppt의 28 page 'Forward Algorithm' 에 forward probability \alpha_t(j)를 구할 때 수식의 2번째 줄, Q_t = q_1, ..., q_t 에 q_t 가 아닌 S_j 가 들어가야 할 것 같은데요 =_= q_t를 S_j로 fix 시킨 모든 path Q_t 가 들어가야 할 것 같아요 (j index 도 수식에 없구요)

너무 minor한 질문이지만 감사의 인사를 전할 겸... 휴먼 daum ID도 살렸습니다.

다시한번 감사합니다 ^^
아 넵~ 별말씀을요. 해당 ppt 자료는 'Dr. Sung-Jung Cho'님이 편의상 간략하게 표현하기 위해서 그렇게 작성하신것 같습니다.
좋은정보 담아갑니다ㅣ http://mkmworld.tistory.com/
안녕하세요~ 좋은글 감사합니다
최근에 공부를 시작했습니다.
HMM, MRF, CRF 차이점이 어떻게 되는지 알 수 있을까요?
안녕하세요~ 자주 안들어와서, 이제와 봤네요.

HMM, CRF의 차이점은 아래 글을 보시면 될것 같구요.
https://github.com/dsindex/blog/wiki/%5Bstatistics%5D-Naive-Bayesian,-HMM,-Maximum-Entropy-Model,-CRF

MRF, CRF의 차이점은 다음 글에 잘 나와있다고 생각합니다~
https://www.quora.com/What-is-the-difference-between-Markov-Random-Fields-MRFs-and-Conditional-Random-Fields-CRFs-When-should-I-use-one-over-the-other