[인공지능] 16. Hidden Markov Models (HMM)

1. Definition of Hidden Markov Model : 시간의 개념이 포함된 확률 모델

  - single discrete random variable로 이루어져 있는 probabilistic model. 

  - state variable Xt 는 정수 1, ... , S를 가질 수 있으며, S는 가능한 states의 수이다.

  - transition model P(Xt|Xt-1) 은 S*S의 matrix T이다. (T_ij = P(Xt = j | X_t-1 = i) 

  - evidence variable Et는 각 state에서 specify하고, 각 state i에서 P(et | Xt = i) 를 통해 state가 et를 야기하는지에 대해 알 수 있다. 이 value는 편의상 S*S의 diagonal matrix Ot로 나타낸다. i번째 entry가 바로 P(et|Xt = i) 이다. 나머진 다 0

 

transition matrix를 보면, column은 현재 state, row는 그 전 state임. 그래서 현재 STATE가 true일 때 진리값은 지난 state에서 t/f 여부에 따른 vector로 나타낼 수 있음. 

 

sensor model matrix를 보면 column이 현재 state의 진리값 t/f, row가 그에 따른 effect가 true일 확률 

 

2. Forward-Backward Algorithms

 1) Forward Backward Messages

   - Forward Messages

 filtering : P(Xt|e_1:t) = f_1:t = αP(et | Xt)∑P(Xt|x_t-1) P(x_t-1 | e_ 1:t-1)

여기서 sensor matrix와 transition matrix 를 행렬로 써서 한번에 계산하는 것이 바로 forward message

 

 f_1:t = α(sensor matrix) * (transition matrix의 transpose) * f_1:t-1

 

  - Backward Message

  P(e_k+1:t|Xk) = b_k+1:t = ∑ P(x_kx+1|Xk) P(e_k+1 | x_k+1) P(e_k+2:t | x_k+1)

  b_k+1:t = (transition matrix) * (sensor matrix) * b_k+2:t

 

  - Forward-Backward Algorithm 

  -> time complexity : O(S^2t) (SxS matrix, time t)

  -> space complexity : O(St) 

 

 2) Constant-space Forward-Backward Algorithm

"forward" message f 는 backward로 구할 수 있다! 즉, 현재 time의 forward message(t-1)는 다음 time의 것(t)으로 구할 수 있다. 

  f_1:t = αOtT^t f_1:t-1

 ==> 1/α T^(-1) Ot^(-1) f_1:t = f_1:t-1

 

이걸 이용해서 smoothing algorithm을 수정할 수 있음

원래는 forward message에서 t-10, ... t-1, t를 다 구해서 기억하고 있었는데, 이제는 t까지 기억 안하고 다 계산한 다음에, backward message처럼 거꾸로 되돌아가면서 값을 구해냄 

 

그래서 t값과 관계없이 항상 space complexity가 constant하다!!!! 

 

 

 3) Fixed-Lag Forward-Backward Algorithm

 

우리가 t까지의 evidence를 알고 있어서 이걸로 t-d 시점의 state를 구했다고 생각해보자. 그렇다면 우리는

P(X_t-d | e_1:t) = α f_1:t-d * b_t-d+1:t 

을 통해 구할 수 있겠지?

근데 이 상황에서 새로운 observation이 도착한거야. 그래서 이젠 t-d+1시점, 즉 구한 시점의 state보다 한 칸 후의 state을 구하고 싶은거지. 

 

원래는 이 때 t+1을 구한다음에 다시 -d를 해주는 작업을 했어야 했는데, 이걸 좀 더 효율적으로 바꿀거야? 어떻게? t-d를 이용해서!

 

t+1-d 는 t-d에 +1 한 값이지? 그래서 굳이 다시 t+1로 안넘어가고 t-d에서 바로 t-d+을 구할 것이다!

 

f_1:t+1-d는 애초에 forward라서 filtering을 통해 f_1:t-d를 통해 구할 수 있으니까 ok~

 

b_(t+1-d : t+1)은 어떻게 할 거냐~ 

b_(k+1 : t) = TO_(k+1)b_(k+2:t) 

b_(t+1-d : t) = TO_(t+1-d)b_(t+2-d : t) = TO_(t+1-d){TO_(t+2-d)b_(t-d+3 : t) = .....

b_(t+1-d : t) = ( ∏(t, i=t-d+1) TO_i )* b_(t+1:t) = B_(t-d+1:t) * 1

 

b_(t+2-d : t) = ( ∏(t+1, i=t-d+2) TO_i )* b_(t+2:t+1) = B_(t-d+2:t+1) * 1

 

여기서 B_(t-d+1 : t) 에 대해 쓰고 싶으면

b_(t+2-d : t) = (O_(t-d+1)) ^(-1) * T^(-1) * B_(t-d+1:t) * TO_(t+1) * 1

 

 

3. Viterbi Algorithm

 

- sudo code 

 

4. Applications

 

 1) erroneous sensor  

 

로봇의 위치를 파악하는 문제 기억나나요 그거 다시 나옴

 

- state variable Xt : 로봇의 현재 위치를 나타냄

- transition model : 로봇이 i번째 칸에서 j번째 칸으로 옮겨갈 확률

  P(X_(t+1) = j | Xt = i) - Tij = 1/N(i) or 0

- 로봇이 어디서 시작할 지 모르니까 각 squares에 있을 확률을 P(X0=i) = 1/n 으로 모두 같다고 가정

- sensor variable Et : 총 16개의 값(2*2*2*2)을 가질 수 있음. 각 방향 동서남북에 장애물이 없는지 있는지!

- sensor가 틀릴 확률을 ε라고 하자. 모든 방향에 대한 sensor는 모두 독립적이므로 모든 방향이 다 틀릴 확률은 ε^4 이고, 네 방향이 모두 맞을 확률은 (1-ε)^4 이다.  

- 따라서 로봇이 state i에 있을 때 사실대로 et를 관측할 확률은 (1-ε)^(4-d_it) * ε^(d_it) 가 된다.

 

  2) Inference for Robot Localization 

 - Filtering to estimate its current location

 P(X1 | E1 =  NSW): NSW을 관측했을 때 로봇이 x1에 있을 확률

 - Smoothing : 과거의 로봇 위치를 알고 있다면 스무딩을 활용하자

 - Viterbi algorithm : 로봇이 어떤 경로로 지금까지 왔는지를 알아보자

 

 -> 관측하면 할 수록 error가 줄어들어서 로봇의 위치를 빠르게 찾을 수 있다. 또 경로 정확도도 높아진다.