[인공지능] 15. Probabilistic Reasoning over Time (PRoT)

1. Introduction

 

 - 세상을 몇 개의 observable 하거나 그렇지 않은 random variables을 포함하고 있는 어떤 snapshot 또는 time slices의 집합이라고 생각하자.

 - Xt : state variables at time t , 시간이 t일 때의 state variable들의 집합. 관측할 수 없는, 그 값을 알 수 없는 variable이다.

 - Et : evidence variables, 관측할 수 있는, 알 수 있는 variable

 - transition model : state이 어떻게 변하는지 정의한다. 예를 들어 t-1 일 때 state이 X일 때, 다음 state이 X 일 확률

 - sensor model : evidence variable이 값이 어떻게 되어야 하는지 정의한다. 예를 들어 state가 X일 때 Evidence E가 관측될 확률

 

  1) Transition Model : P(Xt | X 0:t-1) (state Xt의 확률분포 정의) 

   - First-order Markov process : 오직 직전 state에만 dependence 하다 

     P(Xt | X 0:t-1 ) = P(Xt | Xt-1)

   - Second- order Markov process: 직전 2개의 state에만 dependence하다 

     P(Xt | X 0:t-1 ) = P(Xt | Xt-1, Xt-2)

 

   - Stationary process : 시간이 변해도 확률은 변하지 않는다. 즉, 모든 t에 대해서 P(Xt|Xt-1) 의 값은 늘 같다

   - 모든 것의 시작은 P(X0) ; time이 0일 때의 prior probability

 

  2) Sensor Models : P(Et | X0:t, E1:t-1) = P(Et | Xt) (evidence의 확률분포 정의)

   -> Sensor Markov assumption : Et는 Xt에만 dependent 하다고 가정한다 (현재 state에만 영향을 받는다) 

  

  3) Complete Joint Distribution 

   P(X_0:t , E_1:t) = P(X0)P(X1|X0)P(E1|X1, X0)P(X2|X1, X0, E1)P(E2|X2,X1,X0,E1) ...

  = P(X0)P(X1|X0)P(E1|X1)P(X2|X1)P(E2|X2) ... 

  = P(X0)∏P(Xi|X_i-1)P(Ei|Xi) (transition model * sensor model)

 

  4) Inference in Temporal Models

   ① Filtering(=state estimation)

       :  1~t의 evidence 가 주어졌을 때 Xt를 구하는 것. P(Xt | e_1:t) 

   ② Prediction 

      : 1~t의 evidence가 주어졌을 때 미래의 state, t시간 이후의 state X_t+k를 추측하는 것 

       P(X_t+k | e_1:k)

   ③ Smoothing 

      : 1~t의 evidence가 주어졌을 때, t 이전 시점의 state  구하기. P(Xk | e_1:t)

 

   ④ most likely sequence of states : observations의 sequence가 주어졌을 때, 이 관측 결과로부터 생성될 확률이 가장 높은 sequence of states를 구한다. arg max P(x_1:t | e_1:t) 

 

  -> transition and sensor models을 모르더라도 observation을 통해 학습될 수 있음. (EM algorithm)

 

 

2. Filtering : 현재 시간까지의 evidences를 알 때 현재 state 추측

 P(Xt | e_1:t) = α Forward(f_1:t-1, et) 

 f_1:0 = P(X0 | e_1:0) = P(X0) // prior probability 

1~0 은 역순이니까 말이 안됨! 그냥 항상 확률 1이라고 생각하셈 ㅇㅇ

 

-> state variables이 다 discrete할 때, time과 space는 constant하게 필요(?)함. 그리고 이 상수값은 state space와 question의 temporal model의 종류에 따라 결정됨. 즉, time/space complexity는 constant하며, 이 constant 값은 state와 time t에 dependent하다. 

 

 

3. Evidence

  - Evidence Sequence Likelihood 

   : P(e_1:t) = ∑ P(xt, e_1:t) 

 

4. Prediction : t까지의 evidence가 주어졌을 때 t+k의 미래의 state을 예상하는 것 

P(X_t+k | e_1:t) 

 

5. Smoothing 

 -Backward Message : state k 일 때 미래의 evidence e_k+1:t 구하기

  P(e_k+1:t | Xk)

 -Smoothing : 1~t의 evidence를 알 때 t>k 인 시점, 이전 시점의 state 알기

 

 

 

6. Viterbi Algorithm : 가장 확률이 큰 state sequence 구하기 

  1) Lattice