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

2021.12.31 - [분류 전체보기] - 조건부 확률부터 마르코프까지 - 5-1) HMM 기초

조건부 확률부터 마르코프까지 - 5-1) HMM 기초

211231_대폭 수정

이전에 작성해놓았던 글이나, 설명이 누락되고 잘못된 부분들이 있어, 다시 정리합니다.

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

김성범님의 [핵심 머신러닝] Hidden Markov Models - Part 1 (개념, Evaluation) Youtube 강의

해당 유투브에 Forward Algorithm과 BackWard에 대한 내용도 수립되어있으니 꼭 한번 보세요!

 

유투브 정리 내용

아래 내용과 함께 보시길 추천합니다.

이전 시간에, HMM에 대한 기본적 지식과, 그를 이용해서 해결할 수 있는 문제. 그리고 해결하기 위해서는 어떤 값들이 필요한지에 대해서 알아보았다.

 

이번 시간에는 차근차근, 해결할 수 있는 Task를 하나씩 톺아보고자 한다. (Forward Algorithm. Evaluation 문제)

풀이하고자 하는 문제는 아래 블로그를 참고했다. 설명도 잘 되어있으니 한번 보면 이해하는데 도움이 많이된다.

https://ratsgo.github.io/machine%20learning/2017/03/18/HMMs/

은닉마코프모델(Hidden Markov Models) · ratsgo's blog

일단은 위의 사이트 내용은 Hidden Markov Model의 Forward Algorithm, Backward Algorithm, Model Learning, Decoding Problem 해결 등이 전부 나와있다. 한번에 보기 조금 어려울 수 있다.

하나씩 하나씩, Forward Algorithm에만 초점을 맞추기로 했으니, 그것에만 집중해보자.

 

이전 시간에 HMM을 설명할때, 해결할 수 있는 문제 1번째는 Evaluation Task라고 많이 표현되는데,

Likelihood를 구하는 문제로, 해당 input sequence가 관측될 확률을 구하는 문제이다.

이걸 구해서 어쩔건데?가 궁금할 수 있는데, 뒤에서 설명해줄테니 일단 구하고 보자...!

 

자 그럼, 5-1에서 설명하기 위해 사용했던 예제를 잠시 가져와보자. (일단 HMM모델은 있다는 가정하에.)

성현이가 아이스크림을 3,1,3개 순으로 먹을 확률은 얼마인가?

를 구하는 Task이다. (벌써 온도를 구하고 싶을 수도 있는데, 그건 Decoding Task에서 다루므로, 일단 차근차근 본다고 생각하자. 분명 Foward도 유용한 알고리즘이니까)

 

우리에겐 일단 HMM모델(춥고 더운날의 변화 확률 정보 / 춥고 더운날에 아이스크림을 먹을 확률 정보)가 주어져있으니,

아이스크림을 3,1,3개 순으로 먹을 확률은, 전체 춥고 더운날 경우의 수(case)에서, 3,1,3개의 아이스크림을 먹었을 확률을 전부 더하면 된다.

 

각 case는 춥고, 덥고 2개의 선택지중 아이스크림을 3,1,3 3일간 먹은 케이스니 2**3으로, 8개의 경우의 수가 나온다.

덥고 덥고 덥고

덥고 덥고 춥고

덥고 춥고 춥고

춥고 춥고 덥고

춥고 덥고 덥고

춥고 춥고 춥고

덥고 춥고 덥고

춥고 덥고 춥고

이 전체에 대한 3,1,3 순으로 아이스크림을 먹을 확률을 구해서, 전체 확률을 Sum 해주면 된다.

일단 환경이 2, sequence가 3이니까 S의 T승으로 8개가 나오는데, 만약에 환경이 3개만 되도 3의 3승이라 27개로 확 늘어난다. (제곱이다보니, 상태값의 종류나, 시간 시퀀스가 길어지면 시간이 제곱수만큼으로 무지막지하게 걸린다.)

 

이 연산 이슈를 해결해주기 위한 것이, Forward Algorithm의 사상으로, 마르코프 특성을 이용하여, 직전 상태의 확률(정보)을 계속 누적시켜나가면서, 직전 상태만 바라보게 만드는 것이다. 이 아이디어를 사용함으로써, 재귀나 DP 사상을 활용할 수 있게되어, 계산의 복잡도도, 컴퓨터의 연산량도 상당히 줄어들게 된다.

직전상태에서 이후상태를 보면서 전진해나가므로, Forward Alogrithm이라고 부른다.

 

그러면 이제 말로만 설명하지 말고 실제로 한번 보자.

Forward Algorithm의 사상에 입각하면, P(3 1 3|8개의 경우의 수)를

출처 : https://ratsgo.github.io/machine%20learning/2017/03/18/HMMs/

위와 같이 도식화 할 수 있다.

 

일반화를 위해서 한 시점만 직접 구해보면,

P(3 1 3|hot hot cold) = P(hot|start)×P(3|hot)×P(hot|hot)×P(1|hot)×P(cold|hot)×P(3|cold)

아이스크림 3개 먹은 날 더울 확률 : 시작해서 더울확률 * 더운날 아이스크림 3개 먹을확률

아이스크림 1개 먹은 날 더울 확률 : 더운 전제하에 또 더울 확률 * 더운날 아이스크림 1개 먹을확률

아이스크림 3개 먹은 날 추울 확률 : 더운 전제하에 추워질 확률 * 추운날 아이스크림 3개 먹을 확률

을 곱확률 관점에서 전부 곱해주면, 사실상 교집합과 같은 덥고 덥고 추웠을때 아이스크림 3개 1개 3개 먹을 확률이 된다.

해당 일반화는 점화식을 구하기위해 한번 들렀다고 생각하자.

앞에서 얘기한 최종 시점의 가능도를 구하기 위해서는 해당 확률 1개로만은 알기 어려우며, 모든 확률들이 누적이되어야 모든 케이스에 대한 가능도가 출력 가능해진다.

 

따지고보면 전이확률 행렬에 대한 특정 index의 곱이 연속되게 되는데, Attention에서도 다뤘지만 이런 곱 연산은,

    1) 값이 무작정 길어지는경우 연산이 무척이나 오래걸린다.

        => 해당 방법은 내가 코테 준비에서도 무척이나 열심히 쓰고있는 DP로 해결 가능하다.

        => 다음값들은 이전값에만 의존하므로, 차근차근 앞에서부터 값을 채워나가면서, 필요할때 호출해서 사용한다. 

    2) 또한, 소숫점의 값을 계속 곱하게 되므로, 값의 크기관계가 미미해질 가능성이 크다.

        => 정규화 하는 방법이 있었던 것 같은데, 지금 다루진 않고 마무리 쯤에 한번 찾아서 다뤄보도록 하겠다.

             (Attention에서는 정규화 하기위해 루트 나누는 방법을 쓰듯이)

 

뭐 그리하여, 알고리즘 슈도코드 관점에서 접근하면, 재귀로 풀이하는 방식과, DP로 풀이하는 방식이 있는데,

현재 소개하고자 하는 방식은 재귀를 사용하지 않는 상향식 접근 방법 DP로 풀이하는 방식을 사용하겠다.

 

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

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

 

학습과 채득에 목적을 두고 최대한 조건부 서식과도 비슷한 형태가 나오도록 직관적으로 짜기위해 노력했다.

import collections

# data initialize
transition_dict = collections.defaultdict(dict)
transition_key = ['start','hot','cold','end']
transition_arr = [[0.0, 0.8, 0.2, 0.0],[0.0, 0.6, 0.3, 0.1],[0.0, 0.4, 0.5, 0.1],[0.0, 0.0, 0.0, 0.0]]
for i in range(len(transition_key)):
    for j in range(len(transition_key)):
        transition_dict[transition_key[j]][transition_key[i]]=transition_arr[i][j]

emission_dict = collections.defaultdict(dict)
emission_key = ['hot','cold']
emission_arr = [[0.0,0.0],[0.2,0.5],[0.4,0.4],[0.4,0.1]]

observation = [3,1,3]
for i in range(len(emission_arr)):
    for j in range(len(emission_key)):
        emission_dict[i][emission_key[j]]=emission_arr[i][j]

DP를 풀거나, 그래프 탐색 등의 로직을 짤때, Array가 편한 사람도 있을테고, Dict가 편한 사람도 있을 것이라 생각되어서, 둘다 사용 가능하게 선언한다. Array로 사용하는 경우, transition_key와 emission_key의 Array Index와 매칭되는 서순이라고 생각해주면 되겠다.

유의할 점은 내 소스는 조건부확률처럼 P(cold|hot) '더웠을 가정하에 추워질 확률'에서의 P(cold|hot)의 관점에서 구현하였다는 점 꼭 명심하자. (대부분의 소스는 '더웠을 가정하에 추워질 확률'에 초점을 맞춰, i와 j가 역인 경우가 많다.)

위와 같이 짜면, 데이터를 선언하는 부분에서는 혼동이 올 수 있지만, 실제 사용부에서 좀 더 점화식과 비슷하게 직관적으로 볼 수 있다.

 

위에서의 일반화를 위한 확률을 뽑아봤고, 데이터 초기화에서 i,j를 반대로 활용했기 때문에, 확률 연산식과 소스가 1:1매핑이다.

print(transition_dict['hot']['start'],emission_dict[3]['hot'],transition_dict['hot']['hot'],emission_dict[1]['hot'],transition_dict['cold']['hot'],emission_dict[3]['cold'])

 

실제로 전방확률을 구해나가는 소스이며, end는 아무도 구해보려고 노력조차 한 사람이 없길래, 필요하면 구해서 보라고 넣어뒀다. (물론 볼 이유는 하등없지만, what if....?가 궁금한 사람이라면야...)

def forward(start_keyword:str, transition_dict:collections.defaultdict(dict), emission_key:list, observation_list:list) -> collections.defaultdict(dict):
    # dp[상태][관측값(T)]
    dp = collections.defaultdict(dict)

    # start로부터 첫번째 dp를 결정짓기 위함 (initialize)
    for i in emission_key:
        dp[i][0] = transition_dict[i][start_keyword]*emission_dict[observation_list[0]][i]


    for observ in range(1,len(observation_list)):
        for to_emi in emission_key:
            dp[to_emi][observ]=0
            for from_emi in emission_key:
                # print(from_emi,to_emi)
                dp[to_emi][observ] = (dp[from_emi][observ-1]*transition_dict[to_emi][from_emi]*emission_dict[observation_list[observ]][to_emi]) + dp[to_emi][observ]
    
    # end로의 전방확률구하기
    # for i in emission_key:
    #     dp[i][(list(dp[i].keys())[-1])+1] = transition_dict['end'][i]*dp[i][(list(dp[i].keys())[-1])]
    return dp

3중 포문을 통해

각 시점별, 가야되는 to_emission target에, 각 from_emission 별로 계산을 채우며 곱해나간다.

다른사람들 소스 짠 걸 보면 *emission 하는 부분을, 연산법칙에 의해 밖으로 빼놨던데, 위에서 도식화된 서순과 똑같이 구현하려면, 위와같이 작성하는 편이 더 일관적이다.

예시) (4+4)*2 = 4*2+4*2 / 대부분은 좌항과 같이 짜놓는데, 나는 우항으로 짰다는 말씀!

 

dp는 백준이랑 프로그래머스를 하도 쓰다보니까 아주 버릇이 되버렸는데, 확률 도메인에서는 Alpha 라고 부른다.

알파를 전방확률, 베타를 후방확률이라고 부르는데, 후방확률은 이후에 설명할 예정이니 생략하고, 우리가 위에 구현한 Foward Algorithm의 점화식은 알파의 저것과 일치한다.

전방확률 = 이전노드확률*현재전이확률*관측치확률(방출확률)을 상태 i개 만큼 구해서 전부 더한다.

            = (dp[from_emi][observ-1]*transition_dict[to_emi][from_emi]*emission_dict[observation_list[observ]][to_emi]) + dp[to_emi][observ] <- (list같은거에 넣고 sum을 때리는게 좀 더 직관적이었으려나 싶기도 하고...)

 

최종 사용법

forward('start',transition_dict,emission_key,observation)

 

그러므로, 3,1,3개의 순으로 아이스크림을 먹을 확률은,

result = forward('start',transition_dict,emission_key,observation)

print('3,1,3 개의 순서로 아이스크림을 먹을 확률 :',result['hot'][2]+result['cold'][2])

와 같이 구할 수 있고, 뭐 상태가 2개 밖에 없어서 직관적으로 하드코딩해서 짰는데, 만약 상태가 많아질 상황이라면,

for문을 돌려서 각 상태별로 누적합 시키도록 하면 된다.

 

자 그럼 그래서 어쩔건데? (확장)

지금의 문제는 단순히 emission이 한가지 상황이었기 때문에, 그냥 확률 하나 나오는게 뭐가 대수인가? 싶을 수 있다.

하지만, 성현이는 춥고 더울때 해당 관측치만큼 아이스크림을 먹지만, 민지(동생)는 춥고 더울때 아이스크림을 먹는 관측치가 다를 수 있다.

그러면 아이스크림을 3,1,3개 먹었는 행동을 취했을 때, 그게 성현이일지, 민지일지 알고싶다.

어떤가? 이제 감이 좀 오는가?

HMM모델을 사람의 대상, 혹은 기계의 대상 등 각 대상의 관측치들로 만들어놓고, 같은 관측 시퀀스를 주어, 해당 관측 시퀀스가 어떤 대상이었는지 '분류'할때, 유용하게 사용할 수 있겠다.

 

최종 시퀀스 Sum의 결과가 성현이 HMM에서 나온 결과가 높으면 성현이일거고, 민지 HMM에서 나온 결과가 높으면 민지일 것이다!

 

위에 올려놓은 유투브를 보고 생각이 좀 깨었으며, 그를 토대로 더 정확하고 효과적으로 내용을 전달하게 된 것 같다.

이후 시간에는 Viterbi 혹은 Backward에 대해서 다뤄보고자 한다.

 

해당 아티클은 일단 HMM Model이 있다는 전제하이기 때문에, 그래서 HMM 모델은 어케 만드는건데?가 더 궁금할 수도 있고, HMM 모델이 실제로 무엇인지 궁금한 사람도 있을 것이라고 판단되어서, 어쩌면 Backward부터 다룰 확률이 더 높지 않을까...