Hidden Markov Models

Description:

• Each variable is modeled as a Markov Chain, so conditional probablity of next state only depends on last state
  • first order Markov Chain
    • Past and future independent given the present
    • Each time step only depends on the previous
    • Has Stationary Assumption
  • transition probablity: $P(X_t|X_{t-1})$
• But we need to update our model (beliefs) as we see new observations

Formulation:

• Underlying Markov chain over states X and observe outputs (effects) at each time step
• Conditional independence: HMMs have two important independence properties:
  • Markov hidden process: future depends on past via the present
  • Current observation independent of all else given current state
• Evidence variables are not guaranteed to be independent because they are correlated by the hidden state

Filtering with HMMS:

• Define $B(X)$ as states of belief model
• Filtering, or monitoring, is the task of tracking the distribution $B_t(X)=P_t(X_t|e_1,...,e_t)$ over time
• We start with $B_1(X)$ in an initial setting, usually uniform
• As time passes, or we get observations, we update $B(X)$

Inference: find state given evidence

• We are given evidence at each time and want to know $B_t(X)=P(X_t|E_{1:t})$
• Idea: Start with $P(X_1)$ and derive $B_t$ in terms of $B_{t-1}$ and $B_{t+1}$ in terms of $B_t$ with conditional
• Equivalently, derive $B_{t+1}$ in terms of $B_t$

Passage of time:

• Assume that $B(X_t)=P(X_t|e_{1:t})$
• After 1 time step from $t$, $P(X_{t+1}|e_{1:t})={\sum }_{x_t}P(X_{t+1,x_t}|e_{1:t})={\sum }_{x_t}P(X_{t+1}|x_t,e_{1:t})P(x_t,e_{1:t})$
• At $t+1$, we observe $e_{t+1}$ but the state $X_{t+1}$ only depends on $X_t$ and doesnt depend on $e_{1:t}$
• $P(X_{t+1}|e_{1:t})={\sum }_{x_t}P(X_{t+1}|x_t)P(x_t,e_{1:t})$ and $P(X_t|e_{1:t})$ is known recursively equal to $B(X_t)$
• Or compactly $B^{\prime }(X_{t+1})={\sum }_{x_1}P(X^{\prime }|x_1)B(x_t)$

Two steps: passage of time + observation

• Assume that $B^{\prime }(X_{t+1})=P(X_t|e_{1:t})$
• $P\left(X_{t+1}\mid e_{1:t+1}\right)=P\left(X_{t+1},e_{t+1}\mid e_{1:t}\right)/P\left(e_{t+1}\mid e_{1:t}\right)$
• ${\propto }_{X_{t+1}}P\left(X_{t+1},e_{t+1}\mid e_{1:t}\right)$
  • $=P(e_{t+1}|e_{1:t},X_{t+1})P(X_{t+1}|e_{1:t})=P(e_{t+1}|X_{t+1})P(X_{t+1}|e_{1:t})$
• or compactly, $B(X_{t+1}){\propto }_{X_{t+1}}P(e_{t+1}|X_{t+1})B^{\prime }(X_{t+1})$
• Basic idea: beliefs get “pushed” through the transitions:
  • With the “B” notation, we have to be careful about what time step t the belief is about, and what evidence it includes
• Online beliefs updates:
  • Every time step, we start with current P(X | evidence)
  • We update for time: $P(x_t|e_{1:t-1})={\sum }_{x_{t-1}}P(x_{t-1}|e_{1:t-1}).P(x_t|x_{t-1})$
  • update for evidence: $P\left(x_t\mid e_{1:t}\right){\propto }_{X}P\left(x_t\mid e_{1:t-1}\right)\cdot P\left(e_t\mid x_t\right)$
  • This is our updated belief $B_t(X)=P\left(X_t\mid e_{1:t}\right)$
  • The forward algorithm does both at once (and doesn’t normalize)

• ex: cant observe the weather but we can observe whether someone comes home with umbrella or not (evidence)

  | Transition probability matrix | rain | sun |
  | --- | --- | --- |
  | rain | 0.7 | 0.3 |
  | sun |  0.3  | 0.7  | 
  

  • Prob of evidence given actual: $P(E|X)$:
    • P(umbrella | rain) = 0.9
    • P(umbrella’ | rain) = 0.1
    • P(umbrella | sun) = 0.2
    • P(umbrella’ | sun) = 0.8
  • Starting with $P(X_1=rain)=P(X_1=sun)=0.5$
  • Observe umbrella, $P(X_1|E_1=umb)=$
    • $P(X_1=rain|E_1=umb)=P(X_1=rain\&E_1=umb)/P(E_1=umb)=0.9/(0.9+0.2)=0.82$
    • $P(X_1=sun|E_1=umb)=P(X_1=sun\&E_1=umb)/P(E_1=umb)=0.2/(0.9+0.2)=0.18$
  • Elapse: $P(X_2|E_1=umb)=$
    • $P(X_2=rain|E_1=umb)$
      • $=P(X_2=rain|X_1=rain)\ast P(X_1=rain|E_1=umb)+P(X_2=rain|X_1=sun)P(X_1=sun|E_1=umb)$
      • $=0.7\ast 0.82+0.3\ast 0.18=0.63$
    • $P(X_2=sun|E_1=umb)$
      • $=P(X_2=sun|X_1=rain)\ast P(X_1=rain|E_1=umb)+P(X_2=sun|X_1=sun)P(X_1=sun|E_1=umb)$
      • $=0.3\ast 0.82+0.7\ast 0.18=0.37$
  • Observe umbrella again, $P(X_2|E_1=umb)=$
    • $P(X_2=rain|E_1=umb,E_2=umb){\propto }_{X}P(X_2=rain|E_1=ubm).P(E_2=umb|X_2=rain)$
      • $=0.63\ast 0.9$ normalized to $0.88$
    • $P(X_2=sun|E_1=umb,E_2=umb){\propto }_{X}P(X_2=sun|E_1=ubm).P(E_2=umb|X_2=sun)$
      • $=0.37\ast 0.2$ normalized to $0.12$

Particle Filtering