The Bayes Filter in Different Contexts

30 Mar, 2025

Bayes Filter

The Bayes Filter is a general algorithm for state estimation. A Kalman Filter, for example, is a specific implementation of the Bayes Filter and may be the most important algorithm in robotics. Due to the generality of the Bayes Filter, it was difficult for me to grasp the different applications. I've found that studying the implementation in different contexts helped me quite a bit. In this post, I'll cover two different scenarios where a Bayes Filter is useful: state estimation with a Hidden Markov Model (beginning with a regular Markov Model) and with an "Action Model".

Markov Model - Transitioning between states without observation

Our system can be in one of two states. The likelihood of transitioning to one state from another is summarized in a transition matrix:

If we're certain about the starting probability distribution (we know what state we're in), $P(X_1)={\pi }_1=[P(X_1=0),P(X_1=1)]=[1,0]$. We need to use the law of total probability to compute the probability of the next state $P(X_2)$ or ${\pi }_2$:

Equivalently:

This means ${\pi }_2^{(i)}$ is just the dot product of ${\pi }_1$ and the $i$-th column of $T$. Therefore, in general terms, we can compute ${\pi }_t$ by taking the dot product of $T^{\prime }$ and ${\pi }_{t-1}$ where $T^{\prime }$ is the transpose:

As $t\to inf$, the distribution stops changing which gives us the steady-state distribution of the system. We can approximate the steady-state distribution by running the transition propagation algorithm many times, or exploit the fact that the distribution won't change as follows:

Therefore, the steady state distribution is just the eigenvector of $T^{\prime }$ for an eigenvalue $1$.

Note that this is just a description of how the state would evolve without any observations that might help us refine our judgment. I haven't yet introduced the "hidden" aspect which lets us exploit observations -- so far it's just a Markov Model. At this point, the state at any timestep $t$ can be fully described by the starting state (which may be initialized using the steady-state distribution) and the transition matrix:

$P(X_t=x|X_0,T)$

By computing this value for every state $x$, we get the probability distribution of the state at time $t$. This is what we want.

The markov model provides us a very clean method of representing the state of the system and how it evolves. It's all packaged up nicely. The action model is a bit less elegant, although it is more generally applicable.

Under the markov assumption, $X_t$ depends only on $X_{t-1}$. However, in the above conditional probability, $X_t$ seems to depend on $X_0$ and $T$. Because we don't know what $X_{t-1}$ will be, we must marginalize over all possible values of $X_{t-1}$ to express $P(X_t|X_0,T)$ in a form which can be computed recursively and shows the Markov assumption more clearly. For the rest of this section, I won't show the explicit dependence on $T$.

Oftentimes, the prior $X_0$ is also assumed implicitly:

I'll go with this notation because it's pretty clear that the recursion begins with $P(X_0)$. Finally, we can express the conditional in terms of the transition matrix:

Action Model -- Transitioning between states without observation

In the action model, our state is the position of a robot in a $2\times 2$ grid. We are given a list of actions $u_{1:t}$ over the timesteps along with probabilities related to how an action affects the state. This is known as the motion model, similar to $T$ in the hidden markov model. A robot can either move up, down, left, or right. It succeeds with probability $\mathrm{.9}$ and fails with probability $\mathrm{.1}$. If the action would move the robot off the grid, it stays in place with absolute certainty ($1$).

I think this approach lends itself more to a code implementation, although I won't get into those details in this post.

If our set of actions is $u_{1:t}$, then our probability of interest is the state at time $t$:

Once again, we can assume the prior implicitly: $P(X_t=x|u_{1:t})$. Similar to the HMM, the dependence on the entire sequence of actions reflects the fact that there are many possible previous states $X_{t-1}$ given our model. If we knew the previous state, we could describe the current state just in terms of the previous state and the current action $P(X_t=x|X_{t-1},u_t)$.

If we didn't know the previous state, we would marginalize over possible previous states:

To align more with the HMM notation, we could say that $P(X_t)$ implicitly considers the current action and the same for the previous state, therefore expressing it as such:

However, it's convention to show that the distribution of the current state depends on the history of all previous states, so I will depart from the HMM notation from here on out. The idea is the exact same.

Including observations in the HMM estimate

Now let's say we have a set of observations which provide us some information about the probability (this matrix doesn't have to be square -- we can have more observation modalities than hidden states):

Now our state estimation objective must include the sequence of observations:

At this point, I think you get the idea about the notation basically being determined by clarity and preference, so I won't explain myself further.

If we knew the previous state, we could write $P(X_t=x|X_{t-1},Y_t)$. However, we must marginalize over all possible states of $X_{t-1}$. I will use Bayes Rule in this derivation and the marginalization will appear.

Now observe this:

Replacing this in the original expression:

Defining a variable called ${\text{bel}}_t(x)=P(X_t=x|Y_{1:t})$ will help simplify this expression. I'll also substitute $T$ and $M$:

Finally, since the denominator doesn't depend on the state, we can consider this a normalizing factor to simplify. I'll come back to computing this later:

Including observations in the action model estimate

Now let's say we have a set of observations which provide us some information about the state. Maybe the points on the grid are painted either black or white and these values are known ahead of time. The sensor is noisy, correctly predicting the color with an accuracy of .9.

Our new state estimation objective:

Similar to before, I can calculate the normalizing factor as follows:

Substituting:

Since the denominator doesn't depend on the state, I'll let $\eta =\frac{1}{P(z_t|u_{1:t},z_{1:t-1})}$ once again and substitute:

Since we don't have a clear definition for the transition (or motion model) and emission (sensor model), I will simply call create two functions and redefine ${\text{bel}}_t(x)$ in this context:

Finally, I will substite all these into the derived expression:

Finally, I will get to deriving $\eta$. I'm only going to do it for the action model because they're basically the same, and I don't feel like doing the same thing twice!

I will include everything for a single Bayes filter in one equation because it's satisfying to look at. This means I'll have to rename variables to avoid overlap.

This is nice. Next stop, Kalman Filters. After that, Extended and Unscented Kalman Filters.