Markov Processes and Sensor Models

Every model so far has described a world that holds still while you reason about it. Now the world changes, and you watch it through a sensor that sometimes lies. The apparatus for that turns out to be the previous path's Bayesian network, unrolled through time and made repetitive on purpose.

State and evidence

Split the variables in two.

• $\mathbf{X}_t$ is the state at time $t$: what is actually true, and what you cannot observe.
• $\mathbf{E}_t$ is the evidence at time $t$: what your sensors report. The observation is $\mathbf{E}_t = \mathbf{e}_t$.

Time is sliced into steps of a fixed size, so $t$ counts slices rather than seconds. The interval is a modelling choice; the algorithms do not care.

The umbrella world

Russell and Norvig's example is deliberately small. You are a security guard in an underground installation. You want to know whether it is raining today, and your only contact with the outside world is seeing the director arrive each morning with or without an umbrella. So $R_t$ (rain today) is the state, $U_t$ (umbrella today) is the evidence, and the whole problem is inferring a hidden variable from a proxy.

$$\begin{array}{ll} P(R_0) = \langle 0.5,\ 0.5 \rangle & \\[4pt] P(r_t \mid r_{t-1}) = 0.7 & P(r_t \mid \lnot r_{t-1}) = 0.3 \\[4pt] P(u_t \mid r_t) = 0.9 & P(u_t \mid \lnot r_t) = 0.2 \end{array}$$

Read those three blocks as a prior, a transition model, and a sensor model. Rain persists: a rainy day is followed by another with probability $0.7$. The director is a decent but imperfect indicator: he carries an umbrella on $90\%$ of rainy days, and on $20\%$ of dry ones anyway.

Two assumptions

A history has no bounded length, so $P(\mathbf{X}_t \mid \mathbf{X}_{0:t-1})$ involves a conditional distribution whose parent set grows without limit. Two assumptions cut it down.

The Markov assumption. The current state depends on the history only through a bounded number of previous states. Taking one, a first-order Markov process:

$$\mathbf{P}(\mathbf{X}_t \mid \mathbf{X}_{0:t-1}) = \mathbf{P}(\mathbf{X}_t \mid \mathbf{X}_{t-1}).$$

The sensor Markov assumption. The current reading depends only on the current state:

$$\mathbf{P}(\mathbf{E}_t \mid \mathbf{X}_{0:t}, \mathbf{E}_{0:t-1}) = \mathbf{P}(\mathbf{E}_t \mid \mathbf{X}_t).$$

Both are claims about the state, not about physics or hardware. If yesterday's reading still tells you something about today's once today's state is known, your state variable is missing something.

When the assumption is wrong, enlarge the state. If rain today really does depend on the two previous days, you have two repairs. Raise the order of the model, letting $R_t$ depend on $R_{t-1}$ and $R_{t-2}$; or keep it first-order and enrich the state, adding $\mathit{Season}_t$ or $\mathit{Pressure}_t$ so that the extra dependence runs through a variable rather than through time. The second is usually better, because it is a claim about the world rather than a patch.

We also assume the process is stationary: the transition and sensor models are the same at every step. That is what lets two small tables describe a history of any length. Stationary is not the same as static - the world changes, the laws do not.

The joint distribution

With those assumptions the model is an ordinary Bayesian network in which each state's only parent is the previous state and each observation's only parent is its own state. The semantics is the one from the previous path:

$$P(\mathbf{X}_{0:t}, \mathbf{E}_{1:t}) \;=\; P(\mathbf{X}_0) \prod_{i=1}^{t} P(\mathbf{X}_i \mid \mathbf{X}_{i-1})\, P(\mathbf{E}_i \mid \mathbf{X}_i).$$

Three factors describe a history of any length, which is the whole payoff.

Worked example: the probability of one history

Suppose it rains on both days and the umbrella appears on both. Reading one entry per factor:

$$\begin{aligned} P(r_1, r_2, u_1, u_2) &= \underbrace{\textstyle\sum_{r_0} P(r_1 \mid r_0) P(r_0)}_{0.7 \times 0.5 + 0.3 \times 0.5 \,=\, 0.5} \times P(u_1 \mid r_1) \times P(r_2 \mid r_1) \times P(u_2 \mid r_2) \\ &= 0.5 \times 0.9 \times 0.7 \times 0.9 \\ &= 0.2835 . \end{aligned}$$

Because every history has a probability, every question about the world has an answer: sum the histories that agree with it. That is correct and hopeless - there are $2^t$ of them. The next lesson is about not enumerating them.

Here is that chain with the entries on it. Every arrow carries the one table entry it contributes, and the product underneath is whichever history you have selected; change a day and watch exactly two entries move. The count beside it is the price of the honest answer, and it doubles each time you add a day. The panel at the bottom states the sensor Markov assumption as four numbers, because it is the one readers over-read: yesterday’s umbrella does tell you something about today’s, and stops telling you anything the moment today’s rain is known.

The four questions

Everything the rest of this path does falls into four tasks.

• Filtering: $\mathbf{P}(\mathbf{X}_t \mid \mathbf{e}_{1:t})$, the belief about now given everything so far. This is what a running agent maintains.
• Prediction: $\mathbf{P}(\mathbf{X}_{t+k} \mid \mathbf{e}_{1:t})$ for $k > 0$, the belief about a future state.
• Smoothing: $\mathbf{P}(\mathbf{X}_k \mid \mathbf{e}_{1:t})$ for $k < t$, a better estimate of an earlier state, made with hindsight.
• Most likely explanation: $\operatorname*{argmax}_{\mathbf{x}_{1:t}} P(\mathbf{x}_{1:t} \mid \mathbf{e}_{1:t})$, the single history that best explains the observations.

The first three share one recursion. The fourth, deceptively, does not.

Before the quiz

Be able to separate state from evidence, state both Markov assumptions and say which object each constrains, write the joint as a product of prior, transition and sensor factors, and name the two repairs when the assumption fits badly.