조건부 확률부터 마르코프까지 - 5-4) HMM Learning Task (Training)

2022.01.02 - [Python과 확률] - 조건부 확률부터 마르코프까지 - 5-3) HMM Backward Algorithm

조건부 확률부터 마르코프까지 - 5-3) HMM Backward Algorithm

역시나 해당 유투브가 도움이 많이 됩니다. (김성범님의 강의 part 2입니다.)

https://www.youtube.com/watch?v=P02Lws57gqM 

김성범님 유투브 강의 - [핵심 머신러닝] Hidden Markov Models - Part 2 (Decoding, Learning)

해당 유투브 강의에는 decoding과 learning 2가지를 다루고 있는데, 내가 지난 HMM을 소개하는 자리에서 사실 learning이 실무에서 가장 먼저 수행되어야 할 것이라고 생각했다는 점 때문에, learning부터 다루고자 한다.

(decoding은 다음 시간에 다루겠다.)

 

learning은 좀 여기저기 아티클들을 많이 참고해서 정리해서 작성되는데,

실제 소스 구성은 여기

실제 내용을 작성함에 있어서는,

유투브 강의와 대조하면서는 여기를 (근데 여기는 크사이 구하는 분모가 뭔가 이상하다. 덕분에 필기 잘못함...;;ㅋㅋ)

유투브 강의와 위의 아티클이 잘못됨을 알고 다시 점화식을 확인할때는 여기를

EM Algorithm의 termination 조건은 여기를 (위키피디아)

EM step의 내용과 전반적으로 잘 정리된 강의를 찾아서 여기도 보고 (여기는 정말 정리 잘되어있다. 내가 여태 찾은 내용 다 정리되어있음.)

Addictive Smoothing은 여기를 (위키피디아)

HMM Parameter Initialize를 효과적으로 하는 방법이 없을까? 해서 여기를

확인을 했으니, 내가 일단 정리해서 작성해놓을 것이긴 하지만, 잘 이해가 안된다면 한번 들어가서 확인해보는 것을 추천하겠다.

 

Learning!

모델의 Parameter를 estimate 하는 과정이며, 결과적으로 잘 Optimization된 모델이 될 수 있도록, Parameter를 estimate하는 것이 우리의 역할이다.

HMM에서의 목적은, 관측 시퀀스의 확률을 잘 예측하는 모델을 만드는 것이 목적이다.

어떤 알 수 없는 hidden variable이 있을 때, 그래도 hidden variable과 '종속'된 알 수 있는 관측값을 잘 예측하도록 만드는 것이다.

해당 이미지와 같이보시면 좋습니다.

과정은 심플한게,

    1. Parameter 초기화 (여기를 확인해보면, 여러가지 방법들이 있는 것 같다. 필자는 소스를 짤 때, 정확한 문제가 제시되어있는 해결안을 찾던 것이 아니고, 학습과 블로그 작성에 목적이 있던 지라, Git에 샘플로 올라와 있는 것을 최대한 활용했다.)

    2. 새로운 모델이 이전 모델보다 좋은 case를 찾는다.

    3. 계속 반복하다가, 어느 시점에서 멈춘다.

그냥 머신러닝 Training 과정과 동일하다.

 

우리는 이 Task Flow를 EM 알고리즘의 일종인 Baum-Welch Algorithm으로 해결해보고자 한다.

EM 알고리즘은 Expectation-Maximization 알고리즘으로, 기대값을 최대로 만들어주는 모델을 선택한다는 이야기이다. (최대 우도를 가장 중요하게 여기겠다.)

Baum-Welch 알고리즘은 우리가 앞서 배웠던, Forward-Backward Algorithm을 이용해서, EM Algorithm 사상으로 모델을 학습시켜나가는 방식이다. (때문에 Backward가 필요했던 것이다...!)

위에서의 이유로, 우리는 관측 시퀀스에서의 우도(likelihood)와 그것을 뽑아줄 수 있는 Evaluation Task인 Forward-Backward 알고리즘이 필요한 것이다.

 

EM Algorithm은, E-Step에서 기대값을 구하고, M-Step에서 그것이 최대가 되도록 파라미터를 수정한다.

먼저 E-Step을 수행해야 하므로 알아보도록 하자.

 

E-Step

E-Step에서는 감마와 크사이를 실제로 구하는 작업을 진행한다.

감마 : 모델과 관측시퀀스가 주어졌을때, t 시점 상태가 Si일 확률 (특정 시점에서의 기댓값 기준으로)

크사이 : 모델과 관측시퀀스가 주어졌을때, t 시점 상태가 Si, t+1 시점 상태가 Sj일 확률 (특정 시점에서 다음 시점으로의 변화에서 나타나는 기대값의 기준)

말그대로 Expectation. 기대값을 구하는 작업을 진행한다. 우리가 궁금한 것은 시점 순서에서 특정 상태의 특정 관측시퀀스가 나올 확률이 궁금하며, 결국 그것이 기대값이 되는 것이다.  (특정 시점의 정보와 시점의 변화와 상태의 변화의 정보를 다룬다고 하면 이해하기 쉬울까...?)

 

감마

감마는 현재 시점에서의 상태가 Si일때를 의미하며, 즉 특정 관측치의 가정하에 시점 상태가 Si일 확률을 구하면 된다.

그러면 조건부 확률의 이전 베이즈 정리에서 다뤘던 것을 기억해보면,

으로 한글로 표현해볼 수 있겠고, 이것은

와 같이 표현될 수 있겠다.

감마 최종 정리

https://github.com/YooSungHyun/probability/blob/main/HMM_ysh.py

GitHub - YooSungHyun/probability: Independent, Markov Property, Chain, HMM and BEYOND!🚀

HMM_ysh.py에 오늘 설명할 전반적인 내용은 다 작성되어 있어서, 내용 중에 보면,

1번과 2번 내용을 보면, 위의 수식이 그대로 소스로 작성되어있음을 확인할 수 있다.

 

크사이

크사이가 조금 복잡할 수도 있다.

t시점 상태가 Si, t+1시점 상태가 Sj일 확률인데, 이것을 구하려면

    1) t일때 상태

    2) t+1일때 상태

    3) t에서 t+1로 가는 전이확률

    4) t에서 t+1로 갔을때 우리가 원하는 \( O_{t+1} \) (Ot+1)이 나왔을 확률

이 4개가 전부 곱확률로 이루어져야지만 제대로된 값을 구할 수 있다. (이런 조합은 도대체 어떻게 생각하는지 대단하다.)

감마와 마찬가지로 모든 가능한 확률에서 특정 확률을 구하는 상황이기 때문에,

가 되고, 말로 설명해보면,

t상태에서 i, t+1상태에서 j이고, i -> j 되었을 때, \( O_{t+1} \) (Ot+1)이 나올 확률을 구하게 되는 것이다....ㄷㄷ

 

내가 찾아보던 아티클에서 오타가있어서 필기가 조금 더럽게 되어있는데, '예시)'라고 풀어써놓은걸 정확하게 표현해보자면,

로 표현 가능하다.

크사이 최종 정리

로써 크사이를 구할 수 있다. (사실 공식이나 이렇게 복잡해보이지, 차근차근 소스로 짜면 별거 아니긴 하다...ㄷㄷ)

 

구조 자체는 감마와 똑같다. 두개를 다 구해주면 E-Step은 끝나게 된다.

 

참고로 크사이와 람다는 시계열 순이 중요하기에, 기존 forward, backward에서는 대부분 t를 dict형태로 활용하였으나, 앞에서 설명한 이유로 크사이와 람다에서는 list로 선언하여 활용하였다.

 

M-Step

실제로 파라미터를 업데이트 하는 작업을 진행하게 된다.

진행되는 파라미터는 (파이, 전이, 방출)

파이

초기확률로 t가 1일때 Si에 있을 확률이다.

초기확률은 감마로 간단히 구할 수 있다.

소스에서는 확률이 0일때 분모처리에서 예외가 없게 하기위해, Addictive Smoothing을 사용했는데, 때문에 파이를 구하는 식도 그에 입각해서 조금은 더 복잡해졌다.

 

전이확률

전이확률 업데이트 식

 

방출확률

방출확률 업데이트 식

을 구해주면된다. (약간은 뭐랄까, 확률적 연산의 수식 증명에 대한 이해보다는, 검증된 알고리즘이니, 슈도코드를 확인하고 그대로 소스로 구현해서 검증하는데 조금 더 비중을 두었다.)

 

파이와 전이확률 업데이트

방출확률 업데이트

위에 적어놓은 정리내용과 소스를 대조해보면, 정확하게 일치함을 확인할 수 있다.

 

내 소스는 조건부 확률 모양을 그대로 의거해서 작성하여서, from -> to 모양이 아닌 P(to|from)의 형태이다.

 

실제 Learning과 Termination은,

과 같이 진행하게 되며,

위에서 순서를 확인했듯이,

    1. Parameter 초기화 (_get_init_model)

        - 해당 예제에서는, 횟수에 기반하여 확률을 지정하는 것으로 초기값을 설정했다.

        - 아티클들 찾아보면 초기값을 잡는데에는 여러가지 방법론들이 존재한다.

    2. 새로운 모델이 이전 모델보다 좋은 case를 찾는다. (learn and likelihood calc)

        - 변화시킬 likelihood가 없어질때까지 바꾸는 방법 외에도 epoch를 사용한다던가,

          원하는 특정 우도값에서 종료 시키는 등 이것도 방법론이 많다.

        - 참고로 Addictive Smoothing이 들어가서, Input 예제에 분모가 0이 나오는 Case가 많아지면,

          위와 같은 termination rule을 설정하면, 거의 확률이 평균값에 수렴하게 되어버리므로,

          오히려 학습에 더 악영향을 미치게 되는 것 같다.

    3. 계속 반복하다가, 어느 시점에서 멈춘다. (delta stop)

 

소스는 같은 깃의 HMM_ysh_test.ipynb를 구동해보면 확인 가능하다.

https://github.com/YooSungHyun/probability/blob/main/HMM_ysh_test.ipynb

GitHub - YooSungHyun/probability: Independent, Markov Property, Chain, HMM and BEYOND!🚀

참고로, Input 예제가 썩 좋은 것 같지는 않다. 그래도 값 자체는 원작자의 소스와 비교하여서, 결과가 동일하게 떨어지는 것을 확인했으니, 내 소스 수정 간 오차가 발생할 여지는 없다.

decoding까지 다 보고나면, 이후에 내가 수정한 소스를 이용해서 뭔가 실제로 HMM 예제를 풀어보는 시간을 가져야겠다.

 

여기까지 이해했다면, HMM을 Learning하고, Evaluation하여, 분류기를 만들 수 있는 수준까지는 완성 된 것이다!

HMM에서 다뤄보지 않은 유일한 문제는 이제 Decoding (실제로 Hidden State를 찾아나가는 과정) Task만 남아있다.

 

이 부분까지 정리하고, 실제로 자연어처리나 결측치 채우기와 같은 문제를 한번 풀어볼까 싶다.

 

연말에도 신정에도 주말에도 계속 인강보면서 아티클 뒤져보고 정리했는데, 많은 이들에게 도움이 되었으면 좋겠다.