Recursive Bayesian estimation: Difference between revisions

Revision as of 14:55, 5 July 2008

Latest revision as of 17:14, 30 October 2024

(75 intermediate revisions by 62 users not shown)

Line 1:

{{Short description|Process for estimating a probability density function}}

{{mergefrom|Bayes filter|Talk:Recursive Bayesian estimation#Merger proposal|date=January 2008}}

{{About|Bayes filter, a general probabilistic approach|the spam filter with a similar name|Naive Bayes spam filtering}}

In [[Probability Theory|probability theory]], [[statistics]], and [[Machine Learning|machine learning]], '''Recursiverecursive Bayesian estimation''', also known as a '''Bayes filter''', is a general probabilistic approach for [[density estimation|estimating]] an unknown [[probability density function]] ([[probability density function|PDF]]) recursively over time using incoming measurements and a mathematical process model. The process relies heavily upon mathematical concepts and models that are theorized within a study of prior and posterior probabilities known as [[Bayesian statistics]].

==In robotics==

A Bayes filter is an algorithm used in [[computer science]] for calculating the probabilities of multiple beliefs to allow a [[robot]] to infer its position and orientation. Essentially, Bayes filters allow robots to continuously update their most likely position within a coordinate system, based on the most recently acquired sensor data. This is a recursive algorithm. It consists of two parts: prediction and innovation. If the variables are [[Normal Distribution|normally distributed]] and the transitions are linear, the Bayes filter becomes equal to the [[Kalman filter]].

In a simple example, a robot moving throughout a grid may have several different sensors that provide it with information about its surroundings. The robot may begin with certainty that it is at position (0,0). However, as it moves further and further from its original position, the robot has continuously less certainty about its position; using a Bayes filter, a probability can be assigned to the robot's belief about its current position, and that probability can be continuously updated from additional sensor information.

== Model ==

The true statemeasurements <math>xz</math> isare assumedthe to[[Manifest bevariable|manifestations]] anof unobserveda [[hidden Markov processmodel]] (HMM), andwhich means the measurementstrue state <math>zx</math> areis theassumed observedto statesbe ofan aunobserved [[Hidden Markov Modelprocess]]. The following picture presents a [[Bayesian network]] of a (HMM).

:[[Image:HMMKalmanFilterDerivationHMM Kalman Filter Derivation.png|463-239svg|Hidden Markov Modelmodel|center]]

Because of the Markov assumption, the probability of the current true state given the immediately previous one is conditionally independent of the other earlier states.

:<math>p(\textbf{x}_k|\textbf{x}_{k-1},\textbf{x}_{k-2},\dots,\textbf{x}_0) = p(\textbf{x}_k|\textbf{x}_{k-1} )</math>

Line 16 ⟶ 22:

:<math>p(\textbf{z}_k|\textbf{x}_k,\textbf{x}_{k-1},\dots,\textbf{x}_{0}) = p(\textbf{z}_k|\textbf{x}_{k} )</math>

Using these assumptions the probability distribution over all states of the HMM can be written simply as:

:<math>p(\textbf{x}_0,\dots,\textbf{x}_k,\textbf{z}_1,\dots,\textbf{z}_k) = p(\textbf{x}_0)\prod_{i=1}^k p(\textbf{z}_i|\textbf{x}_i)p(\textbf{x}_i|\textbf{x}_{i-1}).</math>

However, when using the Kalman filter to estimate the state '''x''', the probability distribution of interest is associated with the current states conditioned on the measurements up to the current timestep. (This is achieved by marginalising out the previous states and dividing by the probability of the measurement set.)

This leads to the ''predict'' and ''update'' steps of the Kalman filter written probabilistically. The probability distribution associated with the predicted state is productthe sum (integral) of the products of the probability distribution associated with the transition from the (''k'' - 1)-th timestep to the ''k''-th and the probability distribution associated with the previous state, withover theall truepossible state at (''<math>x_{k'' - 1) integrated out}</math>.

:<math> p(\textbf{x}_k|\textbf{Zz}_{1:k-1}) = \int p(\textbf{x}_k | \textbf{x}_{k-1}) p(\textbf{x}_{k-1} | \textbf{Zz}_{1:k-1} ) \, d\textbf{x}_{k-1} </math>

The probability distribution of updatedupdate is proportional to the product of the measurement likelihood and the predicted state.

:<math> p(\textbf{x}_k|\textbf{Zz}_{1:k}) = \frac{p(\textbf{Zz}_k|\textbf{x}_k) p(\textbf{x}_k|\textbf{Zz}_{1:k-1})}{p(\textbf{Zz}_k|\textbf{Zz}_{1:k-1})} \propto p(\textbf{z}_k|\textbf{x}_k) p(\textbf{x}_k|\textbf{z}_{1:k-1})

= \alpha\,p(\textbf{Z}_k|\textbf{x}_k) p(\textbf{x}_k|\textbf{Z}_{k-1})

</math>

The denominator

:<math>p(\textbf{Zz}_k|\textbf{Zz}_{1:k-1}) = \int p(\textbf{Zz}_k|\textbf{x}_k) p(\textbf{x}_k|\textbf{Zz}_{1:k-1}) d\textbf{x}_k_{k}</math>

is constant relative to <math>x</math>, so we can always substitute it for a coefficient <math>\alpha</math>, which can usually be ignored in practice. The numerator can be calculated and then simply normalized, since its integral must be unitaryunity.

== Applications ==

* [[Kalman filter]], a recursive Bayesian filter for [[multivariate normal distribution]]s

* [[Particle filter]], a sequential Monte Carlo (SMC) based technique, which models the [[Probability density function|PDF]] using a set of discrete points

* '''Grid-based estimators''', which subdivide the PDF into a deterministic discrete grid

==Sequential Bayesian filtering==

Sequential Bayesian filtering is the extension of the Bayesian estimation for the case when the observed value changechanges in time. It is a method to estimate the real value of an observed variable that evolves in time.

There Theare method is namedseveral variations:
;filtering: when we estimateestimating the ''current'' value given past and current observations,
;[[smoothing problem|smoothing]]: when estimating ''past'' valuevalues given presentpast and pastcurrent measuresobservations, and
;prediction: when estimating a probable ''future'' value given past and current observations.

The notion of Sequential Bayesian filtering is extensively used in [[control theory|control]] and [[robotics]].

== ExternalFurther linksreading ==

*{{cite [http://citeseerjournal |first1=M.ist.psu.edu/504843.html Sanjeev |last1=Arulampalam |first2=Simon |last2=Maskell |first3=Neil |last3=Gordon |title=A Tutorial on Particle Filters for On-line Non-linear/Non-Gaussian Bayesian Tracking], |journal=IEEE Transactions on Signal Processing (2001)|volume=50 |issue= 2|pages=174–188 |year=2002 |doi= 10.1109/78.978374|bibcode=2002ITSP...50..174A |citeseerx=10.1.1.117.1144 }}

*{{cite book |last1=Burkhart |first1=Michael C. |title=A Discriminative Approach to Bayesian Filtering with Applications to Human Neural Decoding |date=2019 |publisher=Brown University |___location=Providence, RI, USA |chapter=Chapter 1. An Overview of Bayesian Filtering|doi=10.26300/nhfp-xv22 }}

* [http://julien.diard.free.fr/articles/CIRAS03.pdf A survey of probabilistic models, using the Bayesian Programming methodology as a unifying framework]

*{{cite journal |last1=Chen |first1=Zhe Sage |title=Bayesian Filtering: From Kalman Filters to Particle Filters, and Beyond |journal=Statistics: A Journal of Theoretical and Applied Statistics |date=2003 |volume=182 |issue=1 |pages=1–69}}

*{{cite web |first1=Julien |last1=Diard |first2=Pierre |last2=Bessière |first3=Emmanuel |last3=Mazer |title=A survey of probabilistic models, using the Bayesian Programming methodology as a unifying framework |date=2003 |publisher=cogprints.org |url=http://cogprints.org/3755/1/Diard03a.pdf }}

*{{cite book |first1=Simo |last1=Särkkä |title=Bayesian Filtering and Smoothing |publisher=Cambridge University Press |year=2013 |url=https://users.aalto.fi/~ssarkka/pub/cup_book_online_20131111.pdf }}

*{{cite journal |first1=Alexander |last1=Volkov |title=Accuracy bounds of non-Gaussian Bayesian tracking in a NLOS environment |journal=Signal Processing |volume=108 | pages=498–508 |year=2015 |doi= 10.1016/j.sigpro.2014.10.025 |bibcode=2015SigPr.108..498V }}

[[Category:Bayesian statisticsestimation]]

[[Category:EstimationNonlinear theoryfilters]]

[[Category:Non-linear filters]]

[[Category:Linear filters]]

[[Category:Signal processingestimation]]