?? dynamic.html
字號:
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML 2.0//EN"><html> <head><title>Bayesian inference in dynamic models -- an overview</title></head><body><h1><center>Bayesian inference in dynamic models -- an overview</center></h1><h3><center>by <a href="/~minka/">Tom Minka</a></center></h3><p> The following algorithms all try to infer the hidden state of a dynamicmodel from measurements. The input is a dynamic model and a measurementsequence and the output is an approximate posterior distribution over thehidden state at one or many times. Only discrete-time models are discussedhere. <p>Inferring only the most recent hidden state is known as <b>filtering</b>;inferring past states is known as <b>smoothing</b>.Most filtering methods are <b>on-line</b>, which means they process each measurement exactly once, after which it can be discarded.This allows them to operate with a fixed amount of memory.The opposite of <b>on-line</b> is <b>off-line</b> or <b>batch</b>.There are standard ways to turn an on-line filtering algorithm into a batch filtering or smoothing algorithm.Therefore, the overview is divided into two parts: on-line filtering andbatch filtering/smoothing.<p>Some of these algorithms are general algorithms for approximate Bayesianinference and others are specialized for dynamic models. With thedescription of each algorithm is a partial list of references. I'veincluded more references for algorithms which are lesswell-known. <p>Some related pages on the web:<ul><li><a href="http://www.cs.berkeley.edu/~murphyk/Bayes/kalman.html">KevinMurphy's Kalman filter toolbox</a></ul><hr><h2>On-line filtering algorithms</h2>The algorithms are grouped according to how they represent the posteriordistribution over the hidden state (their <b>belief</b>).<hr><h2>Gaussian belief</h2>The following algorithms use a multivariate Gaussian for their belief. Infact, most of them are more general than this---they could use anyexponential family as their belief.<p><dl><dt><b>Kalman filter</b><dd>The Kalman filter only applies to models with Gaussian noise, linearstate equations, and linear measurement equations, i.e.<pre>s_t = A s_(t-1) + noisex_t = C s_t + noise</pre>For these models the state posterior really is Gaussian, and the Kalmanfilter is exact.<ul><li><a href="http://www.cs.unc.edu/~welch/kalman/">The Kalman filter</a><li><ahref="http://vismod.media.mit.edu/tech-reports/TR-531-ABSTRACT.html">"FromHidden Markov Models to Linear Dynamical Systems"</a>, T. Minka, 1998</ul></dd><p><dt><b>Extended Kalman filter</b><dd>The Extended Kalman filter applies to models with Gaussian noise.The state and measurement equations are linearized by a Taylor expansionabout the current state estimate. The noise variance in the equations isnot changed, i.e. the additional error due to linearization is not modeled. After linearization, the Kalman filter is applied.<ul><li>"Stochastic models, estimation and control", Peter S. Maybeck,Volume 2, Chapter 12, 1982.<li>"A linear approximation method for probabilistic inference",Ross Shachter, UAI'1990.</ul></dd><p><dt><b>Bottleneck filter</b><dd>This algorithm applies to any type of measurement equation.The measurement equation is rewritten in terms of an intermediatebottleneck variable <kbd>b_t</kbd>, such that <kbd>p(x_t|b_t)</kbd> issimple while <kbd>p(b_t|s_t)</kbd> may be complicated. At each time step,the Gaussian belief on <kbd>s_t</kbd> is converted into a Gaussian beliefon <kbd>b_t</kbd> (usually involving approximations), <kbd>b_t</kbd> isupdated exactly from <kbd>x_t</kbd> (since <kbd>p(x_t|b_t)</kbd> issimple), and the new Gaussian belief on <kbd>b_t</kbd> is converted back toa Gaussian belief on <kbd>s_t</kbd>. ("Bottleneck" is my own terminology. In the West paper below, theyused Gamma distributions.)<ul><li>"Dynamic Generalized Linear Models and Bayesian Forecasting,"M. West, P. J. Harrison, & H. S. Migon, J Am Stat Assoc 80:73-97, 1985.</ul></dd><p><dt><b>Linear-update filter</b>a.k.a. linear-regression filter or "statistical linearization" filter<dd>This algorithm applies to any type of measurement equation.The measurement equation is converted into a linear-Gaussian equationby regressing the observation onto the state.The result is a Kalman filter whose Kalman gain is<kbd>cov(state,measurement)/var(measurement)</kbd>.Note that the regression is done without reference to the actual measurement.I call it "linear-update" because the update to the state is always a linearfunction of the measurement.A variety of approximations have been proposed when<kbd>cov(state,measurement)</kbd>is not available analytically. The <b>unscented filter</b>,<b>central difference filter</b>, and <b>divided difference filter</b> arefilters of this type.<ul><li>"Stochastic models, estimation and control", Peter S. Maybeck,Volume 2, Chapter 12, 1982.<li><a href="http://citeseer.ist.psu.edu/457152.html">"Kalman Filters for nonlinear systems: a comparison of performance"</a>,Tine Lefebvre, Herman Bruyninckx, Joris De Schutter.<li><a href="http://cslu.ece.ogi.edu/nsel/research/ukf.html">"The Unscented Kalman Filter for Nonlinear Estimation"</a>,Eric A. Wan and Rudolph van der Merwe, 2000.</ul></dd><p><dt><b>Assumed-density filter</b> a.k.a. moment matching<dd>This algorithm chooses the Gaussian belief which is "closest", in somesense, to the exact state posterior given previous beliefs.Usually this amounts to matching the moments of the exact posterior.This is the most general approximation technique proposed to date---itutilizes not only the form of the measurement equation but also themeasurement itself. The assumed-density filter requires analytic ornumerical solution of integrals over the measurement distribution.For this, one could use Monte Carlo, quadrature, or Laplace's method.<ul><li><a href="ep/">"Expectation Propagation for approximate Bayesian inference"</a>,T. Minka, Uncertainty in AI'2001.<li>"Stochastic models, estimation and control", Peter S. Maybeck,Volume 2, Chapter 12.7, 1982.<li><a href="http://www.unc.edu/depts/statistics/faculty/amarjit/pdffile/Amarjit7.ps">"A nonlinear filtering algorithm based on an approximation of the conditional distribution"</a>,H. J. Kushner and A. S. Budhiraja, IEEE Trans Automatic Control45(3):580-585, 2000.<li><a href="http://citeseer.ist.psu.edu/ito99gaussian.html">"Gaussian filters for nonlinear filtering problems"</a>,K. Ito and K. Q. Xiong, IEEE Trans Automatic Control 45(5): 910-927, 2000.<li><a href="http://uai.sis.pitt.edu/displayArticleDetails.jsp?mmnu=2&smnu=2&author_id=311&article_id=212">"Approximate Learning in Complex Dynamic Bayesian Networks"</a>,Settimi, Smith, & Gargoum, UAI'1999.<li><a href="http://www.ucl.ac.uk/Stats/research/Resrprts/psfiles/135.zip">"A comparison of sequential learning methods for incompletedata"</a>,R. G. Cowell, A. P. Dawid, & P. Sebastiani, Bayesian Statistics 5, 1996.<li><a href="http://www.google.co.uk/search?q=%22A+Bayesian+Approach+to+On%2Dline+Learning%22">"A Bayesian Approach to On-line Learning"</a>,Manfred Opper, On-Line Learning in Neural Networks, 1999.</ul></dd><p><!-- Laplace ADF --></dl><h2>Mixture of Gaussian belief</h2>A natural choice in moving beyond a single Gaussian is to use a mixture ofGaussian belief. Unfortunately, an algorithm for general dynamicmodels has proven elusive. Instead, existing algorithms assume that thedynamic model is a mixture of linear-Gaussian models, i.e. it switchesrandomly between different linear-Gaussian state/measurement equations.This can be understood as having discrete state variables in addition tothe continuous ones.For these models, the true state posterior is a mixture of Gaussians, but avery big one. The algorithms focus on reducing the size of this mixture,in an on-line way.Most of them generalize beyond Gaussian to any exponential family.<p><dl><dt><b>Assumed-density filter</b> a.k.a. "pseudo-Bayes"<dd>Same as assumed-density filtering for a single Gaussian, but now thebelief representation is categorical for the discrete state component andconditional Gaussian for the continuous state component, producing amixture of Gaussian marginal for the continuous state component. For eachsetting of the discrete state component, this algorithm chooses theGaussian which is "closest" to the exact state posterior given previousbeliefs. A drawback of this algorithm is that the size of the mixture ispredetermined by the cardinality of the discrete state component. However,it does allow the state/measurement equations, conditional on the discretestate, to be non-Gaussian.<ul><li><ahref="http://www.cs.berkeley.edu/~murphyk/Papers/skf.ps.gz">"SwitchingKalman filters"</a>, Kevin Murphy, 1998.<li>"Bayesian forecasting",P. J. Harrison and C. F. Stevens, J Royal Stat Soc B 38:205--247, 1976.<li><ahref="http://www.cs.ru.nl/~tomh/publications.html">"Expectationpropagation for approximate inference in dynamic Bayesian networks"</a>,Tom Heskes and Onno Zoeter, Uncertainty in AI'2002.</ul></dd><p><dt><b>Gaussian-sum filter</b><dd>This is a family of algorithms which propagate the exact posterior forone step, giving a large Gaussian mixture, and then reduce the mixtureas needed. Methods for reducing the mixture include:<dl><dt>Drop mixture components with low weight<dd><ul><li><a href="http://www.ucl.ac.uk/Stats/research/Resrprts/psfiles/135.zip">"A comparison of sequential learning methods for incompletedata"</a>,R. G. Cowell, A. P. Dawid, & P. Sebastiani, Bayesian Statistics 5, 1996.<li>Tugnait, Automatica 18: 607--615, 1982<li>Smith & Winter, IEEE Conf Decision & Control, 1979 </ul><dt>Sample mixture components according to weight<dd>Used in Rao-Blackwellised particle filters:<ul><li><a href="http://citeseer.ist.psu.edu/chen00mixture.html">"Mixture Kalman Filters"</a>, Chen and Liu<li><a href="http://www.stats.ox.ac.uk/pub/clifford/Particle_Filters/jj.Abstract.html">"Building Robust Simulation-based Filters for Evolving Data Sets"</a>,J. Carpenter, P. Clifford, & and P. Fearnhead</ul>?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -