Tutorial Rao-Blackwell Particle Filtering

By Gilbert Alexander,2014-04-21 22:14
8 views 0
Tutorial Rao-Blackwell Particle Filtering

    John Bevilacqua / Brenda Ng

    Tutorial: Rao-Blackwell Particle Filtering


    This tutorial describes how to apply Rao-Blackwellised Particle Filtering (RBPF) to a dynamic Bayesian network (DBN). It will use a model of a space probe’s state in order

    to provide several examples of concepts.

    The model:

    We model the probe’s state using a DBN consisting of 3 variables that can be sampled: position (P), velocity (V), and acceleration (A). In this system, time (T) is an observed variable. The system has the following dependencies:

A=f(A, q) t+1t

    V=f(V, A) t+1tt

    P = f(P, V) = f(P, A) t+1tttt

    Where q is a variable that can only be analyzed probabilistically (eg. a possible undetected mechanical glitch, undetected collision with an object, etc.)

    If we attempt to keep track of the probe’s position taking all possibilities into account, the number of possible predictions will increase exponentially with time.

    Methods for analyzing this system

Exact Computation:

Exact computation will perform a projection on every sample. If there are X possible toutcomes, each sample will generate X possibilities. This will result in there being X

    samples. The computational cost of any system will increases exponentially with the complexity of the system, making the problem quickly computationally intractable.

Particle Filtering:

    One way to reduce the computational cost of the problem is to reduce the number of samples that we analyze. Particle filtering essentially combines the particles at a particular position into a single particle, giving that particle a weight to reflect the number of particles that were combined to form it. This eliminates the need to perform redundant computations without skewing the probability distribution. Particle filtering accomplishes this by sampling the system to create N particles, then comparing the samples with each other to generate an importance weight. After normalizing the weights, it resamples N particles from the system using these weights. This process greatly reduces the number of particles that must be sampled, making the system much less computationally intensive.

Rao-Blackwellised Particle Filtering:

    An additional way to improve our computational efficiency is to reduce the complexity of each sample. If we sample 2 variables instead of 3, then we will reduce the number of dimensions in the system. RBPF reduces the number of variables that must be sampled by identifying variables that do not need to be sampled to be computed. In the case of the model proposed above, RBPF would marginalize out P and V because they can be determined by sampling A. This optimization enables RBPF to perform significantly better than simple PF for a particular computational cost. The more that a network can be broken down into subnetworks, the greater performance increase will be.


A Simple Tutorial on RBPF for DBNs

    Arnaud Doucet, Nando de Freitas, Kevin Murphy, & Stuart Russel

    Tutorial provided with UAI2000 paper

Rao-Blackwellised Particle Filtering for Dynamic Bayesian Networks

    Arnaud Doucet, Nando de Freitas, Kevin Murphy, & Stuart Russel

    Technical Report(2000)

Report this document

For any questions or suggestions please email