Probabilistic Reasoning

CS 416
Artificial Intelligence
Professor Brogan
Fall 2004

This assignment is based on the beginning of chapter 15, "Probabilistic Reasoning over Time." You will need to understand the terminology in 15.1 and 15.2 in order to understand this assignment.

Problem description:

Based on a vector of evidence values and a prior belief about the state at time 0, you will be required to calculate the following for a system consisting of one time-varying discrete random variable:

  1. The probability distribution over the possible states at any time t such that 0 <= t <= 2^30. (Filtering, prediction and smoothing)
  2. The probability of that sequence of evidence having appeared
  3. The vector of probability distributions over the possible states. (forward-backward)
  4. The sequence of states most likely to have produced the observed evidence. (Viterbi)

Due date:  This assignment is due at 11:59:59 pm on November 15.

Assignment details:

In an effort to provide a balance between helping with the coding without restricting implementation options, we are providing a basic code skeleton in main.cpp.  This skeleton should help you by outlining the basic implementation requirements of your program and by making explicit the types of information your system may use to satisfy the four types of queries listed above.  For example, a header file describes the types of data required to store the probability distribution of the state at time 0, the transition model, the sensor model, and the evidence sequence. The output specification is also provided in the skeleton code.  At grading time, the output will be scanned with an istream, so format the white space however you like.

This assignment requires manipulating vectors and matrices.  There are libraries that can assist with such operations (Blitz++, Boost::uBLAS) and you are encouraged to explore their use.  A matrix inversion routine will be provided with the code skeleton.

There are some properties of probability theory that must be observed in the input file for this code to work correctly. For example, a coin cannot land TAILS with probability 1.2.  Find these semantic requirements and check for their validity in the input.  Create a file named README in which you explain the semantic requirements. 

The submission procedure is identical to the previous assignment. You may submit questions either to TAs or to the forums.  You may use outside resources to better understand language issues, but write all your own code.  Please refrain from looking at any outside code that has anything to do with inference algorithms.  Let us know of any outstanding resources you find so that we may post them to the forums.

Finally, don't build when you can borrow!  Feel free to use Boost, a set of supplemental C++ libraries:

Extra credit:

If you ignore the prior belief about the state at time 0, given an evidence sequence, can you calculate the distribution over states at time 0? How about time -1? If you can, do it, and explain how in the README; if you can't, explain why not.