bayesian filtering classes.html

良好的代码实现

<H4>Changing the state representation size</H4>
<P>The classes assume their state representation is a constant size.
They define their matrix sizes on construction. Matrices (and
vectors!) in public representation <U>should NOT be externally
resized</U>.</P>
<P>Since matrix resizing invariable involves reallocation, it is just
as efficient to create new matrices as to resize them. Also for a
filter scheme to change it size it must recomputed its internal
states. Therefore if the size of filter needs to change, the solution
is to create a new filter. The new filter can then be <I>initialized</I>
from the state of the old filter plus some new states. What you do
with these new states usually influences the state representation you
choose. Generally new states either enter the system with nothing
being know about them (zero information), or extract value being know
(zero covariance).</P>
<H2>Numerical and Exception Guarantees</H2>
<P>It is important to be able to rely on the numerical results of
Bayes++. Generally the Schemes are implemented using the most
numerically stable approach available in the literature. Bayes++
provides its own UdU' factorization functions to factorize PSD
positive (semi)definite matrices. The factorization is numerically
stable, computing and checking the conditioning of matrices.</P>
<P>Exceptions are thrown in the case of numerical failure. They
follow a simple rule:<BR><EM><STRONG>Bayes_filter_exception</STRONG>
is thrown if an algorithm cannot continue or guarantee the numerical
post-conditions of a function</EM></P>
<P>The only <EM>exception guarantee</EM> that Bayes++ makes when
throwing <STRONG><EM>Bayes_filter_exception</EM> </STRONG>from any
function, is that no resources will be leaked. That is the <I>Weak
guarantee</I> as defined by <A HREF="#Reference">Reference[9]</A>.
Therefore, unless otherwise specified, the numeric value of a class's
public state is <STRONG>undefined</STRONG> after this exception is
thrown by a member of a class.</P>
<P>Be aware that numerical post-conditions may be met even with
extreme input values. For example some inputs may result in overflow
of a result. This does not invalidate the post-conditions that the
result is positive. Even some <EM>Not a Number</EM> values may be
valid. Therefore the results may be computed without exception, but
include <EM>NaN</EM> or <EM>non-number</EM> values.</P>
<H3>Using exceptions in filter schemes</H3>
<P>What does this mean when using a filter Scheme? If the Scheme
throws an exception then, unless otherwise specified, the numeric
value of its state is undefined. Therefore you <STRONG>cannot</STRONG>
use any function of the filter that has any preconditions on its
numerical state. To continue using a filter either the <EM>init</EM>()
function should be used (which has no pre-conditions) or the filter
destructed.</P>
<P>Generally to access the public state of a Scheme you must first
call the <EM>update</EM>() function. If no exception is thrown then
the post-conditions of update are guaranteed. The post-conditions of
<EM>update</EM>() may include such useful properties as the
covariance matrix is PSD. Many application specific tests may also be
required. Just being PSD doesn't say much about X. It could even have
<EM>Infinity</EM> values on the diagonal! Conditioning, trace,
determinate, and variance bounds can all be applied at his point.
</P>
<H1>Polymorphic design</H1>
<P>Why are models and filter Schemes <STRONG>polymorphic</STRONG> ?
OR Why are they implemented with virtual functions?</P>
<BLOCKQUOTE><P>One alternative would be to use <STRONG>generic</STRONG>
instead of <STRONG>polymorphic</STRONG> Schemes. This would implement
Schemes as templates. If the sizes of matrix operations could be
fixed generic models and schemes would directly manipulate matrices
for predefined size.</P></BLOCKQUOTE>
<P>Bayes++ relies on a <STRONG>dual abstraction</STRONG>, separating
numerical schemes from model structure. To represent these, a
<STRONG>polymorphic design </STRONG>was a very important part of
Bayes++ design. After a fair bit of use I still think it was the
correct one. Why?</P>
<P>A) <EM>Usage</EM> : There are many (run time) polymorphic things I
really want to do with the library. I want to be able to build
composite filtering algorithms that switch models and schemes at run
time. This requires<U> both</U> polymorphic filters and models <U>and</U>
runtime sizing of matrices.<BR>A generic approach, especially one
parametrized on matrix size would not allow this. The code size
produced would also bloat massively. Not even STL parameterizes its
containers template with size!</P>
<P>B) <EM>Type safety</EM>: There is surprising little orthogonality
in filtering schemes. The numerics often dictate restrictions or
additional functionality. The type hierarchy in Bayes++ provides a
succinct and safe way to enforce much of this structure.<BR>In a
Generic approach checking that a particular Scheme models a generic
concept correct would be very difficult to enforce.</P>
<P>C) <EM>Compiler problems</EM>: Generic programming in C++ has a
nasty syntax, is very slow to compile and pushes the limits of
compiler reliability.</P>
<P>D) <EM>Efficiency</EM>: The run time overhead of a polymorphic
filter is negligible compared to the matrix algebra required. In fact
using common code may increase efficiency on a many computing
architectures.</P>
<H1 ALIGN=LEFT>Matrix Representation</H1>
<P>Bayes++ requires an external library to represent matrices and
vectors, and to support basic linear algebra operations. Bayes++ uses
the <A HREF="http://www.boost.org/libs/numeric/ublas/doc/index.htm"><B>uBLAS</B></A>
library from <A HREF="http://www.boost.org/"><B>Boost</B></A> for all
these requirements. It an excellent basic linear algebra library. The
interface and syntax are easy to use.</P>
<P>Previous versions of the filters were implemented with the <A HREF="http://www.osl.iu.edu/research/mtl/" TARGET="_top">Matrix
Template Library</A>, <I>MPP</I> and <I>TNT</I>. Public releases
using MTL are still available.
</P>
<P>The Bayes++ implementation uses a set of adapter classes in the
namespace <I>Bayesian_filter_matrix</I> (FM for short) for matrix
access. This system should make it simpler to port the library to
other matrix types. For uBLAS these function generally have no
runtime overhead. This efficiency is due to uBLAS's excellent
expression template implementation. For MTL most functions are
reasonably efficient but some functions create matrix temporaries to
return values.</P>
<H2>Matrix library efficiency - Temporary object usage</H2>
<P>Most of the filters avoid using Matrix and Vector temporaries.
They also have optimizations for a constant (on construction) state
size, noise and observations. In particularly the UD_filter scheme
avoids creating any temporary objects. All matrices maintain a fixed
size, other then when the observation state size is varied.</P>
<P>Why are temporary matrix objects bad? The main difficulty is
construction and destruction of Matrices. This generally requires
dynamic memory allocation which is very slow. For small matrices this
dominates compared to the cost of simple operations such as addition
and multiplication.</P>
<P>There are three ways out of this problem.</P>
<BLOCKQUOTE><P>1. Use fixed size matrices; they can (nearly) always
be efficiently allocated on the stack.<BR>2. Use stack based dynamic
allocators (such as C99's dynamic arrays or alloca) for
temporaries.<BR>3. Don't create temporaries. This is achievable with
a combination of hard coding in the algorithms (pre-allocation) and
by using a Matrix library with expression templates to avoid creating
temporaries for return values.</P></BLOCKQUOTE>
<P>Bayes++ is implemented to avoid creating temporaries. At present
my solution is somewhat of a compromise. MTL is only moderately
efficient on most C++ compilers. On release code this results in a
50% performance reduction if temporaries are avoided. uBLAS attains
close to optimal efficiency in many situations.</P>
<P>The UD_filter is a good illustration. It has been hand crafted to
avoid construction of any temporaries (I use it for embedding) and
can be compiled with either uBLAS, MTL or a special fast matrix
library. UD_filter is heavily optimized to use row operations to
avoid indexing overheads. uBLAS and the special library achieve
comparable results, which I believe are as fast as can be achieved.</P>
<P>On the flip side, the current Unscented_filter implementation
shows some of the problems. Because of my wrapper classes Row/Column
of a 2D matrix are not compatible with the Vec type. This results in
a lot of unnecessary copying into pre-allocated temporary vectors.</P>
<P>Future work includes a general method of avoiding implementation
temporaries. Filter schemes will be parameterised with helper objects
that deal with all the temporaries required. These helper objects can
then hide all the hard work of pre-allocation or dynamic allocation
of temporary objects.</P>
<H1>Restrictions</H1>
<P>For numerical precision, all filter calculations use <B>doubles</B>.
Templates could be used o provide numerical type parameterization but
are not. However the base class <I>Bayes_filter</I> defines <I>Float</I>,
which is used throughout as the numerical type.</P>
<P>The <I>Bayes_filter</I> base class is constructed with constant
state size. This allows efficient use of the matrix library to
implement the algorithms. Each derived class requires additional
representation and matrix temporaries and where possible they are
restricted to a constant size. In general, the only unknown is the
size of the observation state as parameterized by the observation
model.</P>
<P>Where the state size varies efficient solutions are still possible
using either spares matrix representations or by recreating new
filters with increased size.</P>
<H1>The future</H1>
<P>The Bayesian Filtering Classes are now a stable set of solution
for the majority of linear, linearisable and non-linear filtering
problems. I am very happy with their form and function. In
particular, the two-layer abstraction works extremely well. The
classes show best practice in both their design and in efficiency and
numerical stability of the algorithms used. So where to go from here?</P>
<P>The basic tenant of Bayesian theory is that the Likelihood
function complete captures all that is know to update the state. The
Bayesian Filtering classes now allow the modeling systems using
Likelihood functions. At present the SIR filter is the only
Likelihood filter. Sample filters will grow into a separate branch in
the class hierarchy. A general set of adapters will be required to
move between these varied representations.</P>
<P>To further improve the abstraction, the method of internal
variable exposure needs to be regularized. This will require the
addition of a few classes that hold and limit access to filters
internal variables.</P>
<P>The ordering of parameters used in Scheme class constructors is
prone to error. It requires the parameter list to be varied for each
scheme used. An extensible method of model parameterization is
required. A common parameterization could then be used with scheme
constructor extracting the information they require.</P>
<H2>STATE ABSTRACTION</H2>
<P>Can the state representation be abstracted away from the numerics
of a filter Scheme?</P>
<P>At the moment Bayes++ filter Schemes are a combination of the
numerical solution (e.g. innovation update) AND the representation
(e.g. Covariance matrix). Can these two functions be separated?</P>
<P>A highly sophisticated solution could use polymorphic (or generic)
filter algorithms that depend on the type (or traits) of the
representation. I think this in unnecessarily complex. In Bayes++ a
Scheme should only implement one algorithm.</P>
<P>The problem I would like to address is a bit more limited. A lot
of representations are naturally hierarchical and dynamic.<BR>e.g.
state := vehicle states &amp; feature states, feature states :=
{feature1 state &amp; feature2 state ....}</P>
<P>There would seem to be too possible ways to solve this</P>
<P>A) HARD: Use a state representation that represents this kind of
hierarchy. The filter schemes could therefore use hierarchical
numerical solutions that exploit the properties of the hierarchical
state.</P>
<P>B) EASY: Allow a sparse matrix representation of state. If the
sparse representation is a Graph then the sort of augmented state
representation in the example can be easily built without any copy
overhead. Each scheme would then just use sparse matrix techniques in
its numerical solution. Mostly what is needed is Cholesky and QR
decomposition and these have good sparse solutions. Obviously there
would be a runtime overhead for this but it would be great for
Simultaneous Location and Mapping problems!</P>
<H1 ALIGN=LEFT></A>Copyright</H1>
<P ALIGN=LEFT>Copyright (c) 2003,2004,2005 Michael Stevens. This document is
part of the Bayes++ library - see Bayes++.html for copyright license
details.</P>
<H1><A NAME="References"></A>References</H1>
<P>[1] &quot;A New Approach for Filtering Nonlinear Systems&quot;, SJ
Julier JK Uhlmann HF Durrant-Whyte, American Control Conference 1995</P>
<P>[2] &quot;Factorisation Methods for Discrete Sequential
Estimation&quot;, Gerald J. Bierman, ISBN 0-12-097350-2</P>
<P>[3] &quot;Real time Kalman Filter Application&quot;, Mohinder S.
Grewal, Angus P. Andrews, ISBN 0-13-211335-X</P>
<P>[4] &quot;Extension of Square-Root Filtering to Include Process
Noise&quot;, P. Dyer and S. McReynolds, Journal of Optimization
Theory and Applications, Vol.3 No.6 1969</P>
<P>[5] &quot;Novel approach to nonlinear-non-Guassian Bayesian state
estimation&quot;, NJ Gordon, DJ Salmond, AFM Smith, IEE Proceeding-F,
Vol.140 No.2 April 1993</P>
<P>[6] &quot;Tracking and Data Association&quot;, Y Bar-Shalom and T
Fortmann, Academic Press, ISBN 0-12-079760-7</P>
<P>[7] &quot;Stochastic Models, Estimation, and Control&quot;, Peter
S Maybeck, Academic Press, ISBN 0-12-480701-1</P>
<P>[8] &quot;A non-divergent Estimation Algorithm in th Presence of
Unknown Correlaltion&quot;, SJ Julier, JK Uhlmann, Proc. American
Control Conference 6/1997
</P>
<P>[9] &quot;Exception-Safety in Generic Components&quot;, David
Abrahams, Proc. of a Dagstuhl Seminar 'Generic Programming', Lecture
Notes on Computer Science 1766,
<A HREF="http://www.boost.org/more/error_handling.html" TARGET="_top">http://www.boost.org/more/error_handling.html</A></P>
</BODY>
</HTML>