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

2021.12.27 - [Python과 확률] - 조건부 확률부터 마르코프까지 - 5-2) HMM Forward Algorithm

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

backward 알고리즘은 learning과 함께 다룰까 했는데, learning 샘플소스를 짜다가, 원래 샘플용으로 짜놨던 소스들과는 많이 달라져서 내용을 따로 다루고자 한다.

 

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

김성범님의 강의 내용 중 맨 뒷부분 backward 쪽 설명을 참고하였으며, 예제 case는 https://ratsgo.github.io/machine%20learning/2017/03/18/HMMs/

을 참고하였습니다.

해당 이미지를 참고하시면 좋습니다.

backward prob은 forward와는 방향만 반대일뿐, 관측 시퀀스의 확률을 구한다는 점에서는, Evaluation을 해결하는 문제 해결방식으로 forward와 완벽하게 동일하다.

 

때문에 소스로 구현하였을 때, 같은 관측 시퀀스를 입력으로 주었다면, 두개의 값은 결국 같아야 한다. (다르면 뭔가 잘못짠거다.)

 

때문에 소스도, 정확하게 위의 필기 예제와 같이, 하나씩 그려보면서, 점화식은 그대로 사용하고, 방향만 반대로 처리해줬다.

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

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

practice용 소스는 forward와 backward만을 따로 다루며, 해당 예제에 대한 데이터를 효과적으로 펼쳐보기위해 작성되어있다. 오늘 기준으로, 최종 버전일 것이라고 생각하면 될 것 같다. (이후의 내용은 HMM 클래스를 만들어서 업로드할 예정)

 

end부터 역으로 돌아가니, 데이터의 마지막부터 1씩 빼주면서 0까지 돌린다.

역으로 돌아가는 환경이기에, from과 to만 대상이 서로 바뀌었다는 점만 고려하면, forward와 구성 자체는 똑같다.

def backward(start_keyword:str, transition_dict:collections.defaultdict(dict), emission_key:list, observation_list:list) -> (collections.defaultdict(dict), float):
    # dp[상태][관측값(T)]
    dp = collections.defaultdict(dict)
    print('Backward Algo')
    for observ in range(len(observation_list)-1,-1,-1):
        for to_emi in emission_key:
            # END로는 무조건 끝이라는 1가지 경우의 수밖에 없으니, END로의 전이는 무조건 확률 1
            if observ == len(observation_list)-1:
                dp[to_emi][observ] = 1
                continue
            dp[to_emi][observ]=0
            for from_emi in emission_key:
                # print(from_emi,to_emi)
                print('후방('+from_emi+'|'+str(observ+1)+') * '+'전이('+to_emi+'|'+from_emi+') * '+'관측('+str(observation_list[observ+1])+'|'+from_emi+') '+ 'Target : '+'후방('+to_emi+'|'+str(observ)+')')
                dp[to_emi][observ] = (dp[from_emi][observ+1]*transition_dict[from_emi][to_emi]*emission_dict[observation_list[observ+1]][from_emi]) + dp[to_emi][observ]
    
    backward_prob = 0
    for emi in emission_key:
        backward_prob = dp[emi][0]*transition_dict[emi][start_keyword]*emission_dict[observation[0]][emi] + backward_prob

    return dp, backward_prob

참고할만한 점은, backward로 구했을시엔, 처음 노드에서 start노드로 전이되는 case를 고려하여 최종 시퀀스의 확률을 구해야한다.

 

출력해보면 결과를 알 수 있고, 각 출력에서 점화식이 어떻게 구성되는지도 print로 찍어놔서 보기 편할 것이다.

result_for, forward_prob = forward('start',transition_dict,emission_key,observation)
result_back, backward_prob = backward('start',transition_dict,emission_key,observation)

print('3,1,3 개의 순서로 아이스크림을 먹을 확률(forward) :',forward_prob)
print('3,1,3 개의 순서로 아이스크림을 먹을 확률(backward) :',backward_prob)

 

뭐 forward던 backward던 evaluation task에서는 편한걸 쓰면 될텐데, 나는 아무래도 forward가 훨씬 편한 것 같다.

 

backward는 지금 보면 하등 쓸모가 없어보이지만, learning에서 전체 flow에서의 특정 시점에서의 상태 확률을 구해내고자 할때 유용하게 쓰이므로(과거에서부터 오는 조건(전방), 미래에서와의 조건(후방)를 따져서 특정 시점을 짚어낼때 사용됨), 꼭 짚어보고 넘어갈 필요가 있겠다.