[HMM] Hidden Markov Models

[참조1]: https://www.youtube.com/watch?v=HB9Nb0odPRs

[참조2]: https://www.youtube.com/watch?v=P02Lws57gqM

Three problems of hidden Markov model

HMM에서 풀수있는 문제들 나열

lambda = (A, B, pai)

 

*O 는 Observations

1. Given HMM(lambda) and O, find the probability of O > Evaluation problem
2. Given HMM(lambda) and O, find the optimal hidden state sequence (S) > Decoding problem
   1. HMM의 핵심
3. Given X = {O1, ... , On}, find the HMM(lambda) > Learning problem
   1. 제일먼저 선행되어야할 스텝. 즉, parameter estimation. 모델 구축

Evaluation problem

problem: Given HMM(lambda) and O, find the probability of O

Solution: Forward algorithm

Example: 정 박사가 오늘 산책, 내일 산책, 모레 연구, 글피 쇼핑할 확률은?

 

먼저 Given HMM(lambda)라 했으니 정 박사의 HMM모델은 다음과 같다.

위와 같은 모델이 주어졌을땐 Given X = {O1, ... , On}, find the HMM(lambda) > Learning problem 해당 문제는 이미 풀려져 있는 상태다.

주어진 문제를 풀려고하면 다음과같은 확률을 구해야하는것인데

Probability O = {o1 = 산책, o2= 산책, o3 = 연구, o4 = 쇼핑)

하지만 자세히 들여다보면 날씨관련 Hidden State도 포함되어야한다. 즉,

Probability O = {o1 = 산책, o2= 산책, o3 = 연구, o4 = 쇼핑 | 날씨1, 날씨2, 날씨3, 날씨4) 와같이 날씨관련 전제조건이 있어야한다는 점.

Hidden State는 총 두개이므로, 총 경우의 수는 2^4 = 16 가지 종류를 다 계산해줘야한다. 16가지 종류는 손으로 어찌어찌 계산하겠지만 이 숫자가 늘어날수록 사람의 힘으로는 매우 힘들어진다. 그래서 HMM에서는 Forward algorithm이라는 방법으로 쉽게 문제를 해결한다.

 

위와같이 그래프를 그려놓는다. Hidden State는 총 두개 (s1, s2). T는 시점. 그러면 처음 두개 O1(alpha1, alpha2)의 확률을 구하고싶다면, 각 파라미터 값은 위에 박사의 HMM모델에 들어있다.

- alpha1(1) : 비가왔을때 산책할 확률

- alpha1(2) : 해가 나왔을때 산책할 확률

자 그러면 O2에 대해서 확률을 구할때는 좀더 복잡해진다. 즉 위에 그래프에서 이어져있는 확률에 날씨관련 확률(hidden state probability,상태전이확률)을 곱하고 각각 더해줘서 확률을 곱해야한다.

이렇게 계산하게된다면 예를들어서 alpha2(1)에서는 모든 날씨정보종류를 다 고려하여 확률이 계산된다. 이와같이 똑같은 방법으로 끝까지 계산한다. 결국 해당 문제의 정답은 밑 그래프와 같이 두개노드를 합하므로 0.0111이라는 답이 나온다. (그림은 숫자가 잘못나온것같다)

Forward algorithm은 결국 DP(Dynamic Programming)과 유사하다.

 

Learning Problem

자 Forward algorithm이 있다면 당연히 Backward algorithm도 있다.

위에 문제가 박사가 O(산책, 산책, 연구, 쇼핑) 의 확률을 구한다면

이번 문제는 박사가 산책, 산책, 연구, 쇼핑 순서가 나올 확률을 구함 이다.

Backward algorithm에서는 기존에 알파state로 표시했던걸 베타state로 표시한다.

다음과 같이 계산된다. Forward algorithm과 다른점이라면 기존에 State곱셈이 안으로 들어가져있다는 차이.

backward algorithm은 세번째 문제인 learning problem을 풀기위해서 사용된다.

Decoding Problem

Decoding Problem문제는 다음과 같이 만들수있다.

박사가 산책, 산책, 연구, 쇼핑을 할때 각 날에 날씨는 어떤지? 에대한 문제를 풀수가있다. 즉, 여기서 날씨는 Hidden State이다.

따라서 다음과같이 수식이 만들어진다.

기존 Forward Algorithm(FA)과 차이라면 FA는 max를 구하지않고 해당 값들을 합쳤고. Decoding Algorithm에서는 둘중 max값만 이용해서 확률값을 구했다.

Forward algorithm VS Viterbi algorithm(Decoding algorithm)

 

이 세가지 알고리즘을 코딩을하면 다음과같이 쓸수있다.

import numpy as np

#=======Forward Algorithm=======#
# parameter setting
pai = [0.6, 0.4]

a = np.array([[0.7, 0.4], [0.3, 0.6]])
b = {}
b['walk'] = [0.1, 0.6]
b['shopping'] = [0.4, 0.3]
b['research'] = [0.5, 0.1]

state_sequence = ['walk', 'walk', 'research', 'shopping']
for index, state in enumerate(state_sequence):
    index += 1
    if index == 1:
        a1 = pai[0] * b[state][0]
        a2 = pai[1] * b[state][1]
        temp_np = np.array([a1, a2])
        if len(state_sequence) == 1:
            print('[Result]:', np.sum(temp_np))
    else:
        temp_np = np.sum(np.multiply(temp_np, a), axis=1) * np.array([b[state][0], b[state][1]])

for index, i in enumerate(state_sequence):
    if index == 0:
        print(f'[STATE]\t {i} ->', end='')
    elif index + 1 != len(state_sequence):
        print(i, '->', end='')
    else:
        print(i, end='\n')

print('[Forward Algorithm RESULT]=>\t' + str(round(np.sum(temp_np), 6) * 100) + '%')

#=======Backward Algorithm=======#
beta = [1,1]
for index, state in enumerate(state_sequence[::-1]): 
    if index == 0:
        temp_np = np.sum(np.multiply(np.array(beta), np.transpose(a)) * np.array([b[state][0], b[state][1]]), axis=1)
    elif index < len(state_sequence) - 1:
        temp_np = np.sum(np.multiply(np.array(temp_np), np.transpose(a)) * np.array([b[state][0], b[state][1]]), axis=1)
    else:
        temp_np = np.multiply(np.array(temp_np), np.transpose(np.array(pai))) * np.array([b[state][0], b[state][1]])

for index, i in enumerate(state_sequence):
    if index == 0:
        print(f'[STATE]\t {i} ->', end='')
    elif index + 1 != len(state_sequence):
        print(i, '->', end='')
    else:
        print(i, end='\n')

print('[Backward Algorithm RESULT]=>\t' + str(round(np.sum(temp_np), 6) * 100) + '%')

#=======Decoding Algorithm=======#
result = []
for index, state in enumerate(state_sequence):
    index += 1
    if index == 1:
        a1 = pai[0] * b[state][0]
        a2 = pai[1] * b[state][1]
        temp_np = np.array([a1, a2])
        result.append(np.argmax(temp_np))
        if len(state_sequence) == 1:
            print('[Result]:', result)
    else:
        temp_np = np.max(np.multiply(temp_np, a), axis=1) * np.array([b[state][0], b[state][1]])
        result.append(np.argmax(temp_np))
weather_list = []
for i in result:
    if i == 1:
        weather_list.append('해')
    else:
        weather_list.append('비')
print(weather_list)