[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / wiki/concepts/filters.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "filter" type: concept related: [Filters, Gaussian Distribution, Bayes Theorem, Belief] source: https://www.jemoka.com/posts/kbhfilters/ confidence: high status: active --- filters are how beliefs are updated from observation discrete state filter \begin{equation} b’(s’) = P(s’|b,a,o) \end{equation} \(b’\) is what state we think we are in next, and its a probability distribution over all states, calculated given from \(b,a,o\) our current belief about our state, our action, and our observation. We can perform this belief update by performing Bayes Theorem over \(o\): \begin{align} b’(s’) &= P(s’|b,a,o) \\ &\propto P(o|b,a,s’) P(s’ | b,a) \end{align} Now, consider \(b\) is a representation of \(s\) (“belief is a representation of what previous state you are in.”) However, you will note that \(s\) is conditionally independent to \(o\) through d-seperation as there is a chain \(s \to s’ \to o\). So: \begin{align} b’(s’) &\propto P(o|b,a,s’) P(s’ | b,a) \\ &= P(o|a,s’) P(s’ | b,a) \end{align} This first term is by definition the observation model, so we have: \begin{align} b’(s’) &\propto P(o|a,s’) P(s’ | b,a) \\ &= O(o|a,s’)P(s’ | b,a) \end{align} We now invoke the law of total probability over the second term, over all states: \begin{align} b’(s’) &\propto O(o|a,s’)P(s’ | b,a) \\ &= O(o|a,s’) \sum_{s}^{} P(s’|b,a,s)P(s|b,a) \end{align} If we know \(s\) and \(a\) in the \(P(s’|b,a,s)\) terms, we can drop \(b\) because if we already know \(a,s\) knowing what probability we are in \(s\) (i.e. \(b(s)\)) is lame. Furthermore, \(P(s|b,a)=b(s)\) because the action we take is irrelavent to what CURRENT state we are in, if we already are given a distribution about what state we are in through \(b\). \begin{align} b’(s’) &\propto O(o|a,s’) \sum_{s}^{} T(s’|s,a)b(s) \end{align} Kalman Filter A Kalman Filter is a continous state-filter where by each of our \(T, O, b\) is represented via a Gaussian distribution. Kalman Filter is discrete state filter but continuous. Consider the final, belief-updating result of the discrete state filter above, and port it to be continous: \begin{equation} b’(s’) \propto O(o|a,s’) \int_{s} T(s’|s,a) b(s) ds \end{equation} if we modeled our transition probabilties, observations, and initial belief with a gaussian whereby each parameter is a gaussian model parameterized upon a few matricies. \begin{equation} T(s’|s,a) = \mathcal{N}(s’|T_{s} s + T_{a} a, \Sigma_{s}) \end{equation} \begin{equation} O(o|s’) = \mathcal{N}(o|O_{s}s’, \Sigma_{o}) \end{equation} \begin{equation} b(s) = \mathcal{N}(s | \mu_{b}, \Sigma_{b}) \end{equation} where, \(T, O\) are matricies that maps vectors states to vectors. \(\Sigma\) are covariances matricies. Finally, \(\mu\) is a mean belief vector. Two main steps: predict \begin{equation} \mu_{p} \leftarrow T_{s} \mu_{b} + T_{a}a \end{equation} \begin{equation} \Sigma_{p} \leftarrow T_{s} \Sigma_{b} T_{s}^{T} + \Sigma_{s} \end{equation} given our current belief \(b\) and its parameters, and our current situation \(s,a\), we want to make a prediction about where we should be next. We should be somewhere on: \(b’_{p} = \mathcal{N}(\mu_{p}, \Sigma_{p})\). update \begin{equation} \mu_{b} \leftarrow \mu_{p}+K(o-O_{s}\mu_{p}) \end{equation} \begin{equation} \Sigma_{b} \leftarrow (I-KO_{s})\Sigma_{p} \end{equation} where \(K\) is Kalmain gain We are now going to take an observation \(o\), and update our belief about where we should be now given our new observation. Kalmain gain \begin{equation} K \leftarrow \Sigma_{p} O_{s}^{T} (O_{s}\Sigma_{p}O_{s}^{T}+\Sigma_{O})^{-1}} \end{equation} Additional Information Extended Kalman Filter Kalman Filter, but no linearity required by forcing linearity by a point-jacobian estimate about the mean of the belief state. Unscented Kalman Filter its Extended Kalman Filter but derivative free, which means its clean and hence its unscented. Its achieved through using “sigma point samples”: just taking some representative points (mean + 2 points in each direction), and draw a line. Particle Filter Its a filter with Likelihood Weighted Sampling. Say we are flying a plane; we want to use our height measures to infer our horizontal location. Let us take an observation model: \(O(o|s,a) = \mathcal{N}(o|h(s), \sigma)\) (“the probability of getting an observation given we are in the state”) start off with a prior distribution over the states you have: a distribution over the possible states make \(N\) monte-calro samples from our prior. These are our particles. use the transition model to propagate the \(N\) samples forward to get \(N\) new next-state samples take action \(a\); calculate \(O(o|s,a)\) for each of your proper gated samples \(s\) (“how likely is our observed altitude given each of our sampled states?”) normalise the resulting probabilities into a single distribution re-sample \(N\) samples that from the resulting distribution. these are our updated belief. repeat from step 3 main pitfalls: if we don’t have enough sampled particles, you may get condensations that doesn’t make sense particle filter with rejection This is used almost never but if you really want to you can. You’d get a bunch of particles and take an action. You propagate the particles forward. For each propergated state \(s\), if what you observed \(o\) is equal to (or close to, for continuous cases) \(sample(o|s,a)\), you keep it around. Otherwise, you discard it. You keep doing this until you have kept enough states to do this again, and repeat. Injection particle filter Add a random new particle every so often to prevent particle deprivation. Adaptive injection particle filter We perform injection based on the ratio of two moving averages of particle weights—if all weights are too low, we chuck in some to perturb it