Project for Probabilistic Reasoning in AI (308526B)
Winter 2002
Goals
The main goal of the project is to allow you to study more indepth
probabilistic reasoning techniques described in class. A secondary
goal is to help you develop your research skills (reviewing research
literature, formulating questions, deciding on a theoretical or
empirical approach to answer them, writing up your findings).
Ideally, the project topic you choose should be related to your
research interests.
There are three main categories of projects:

Applying probabilistic to interesting problem domains, thereby
allowing you to gain indepth experience with specific algorithms.

Studying probabilistic reasoning techniques not covered or skimmed in
class

Investigating theoretical issues.
Ideally, the projects would be individual. However, teams of two
people would be accepted under special circumstances. If you choose
to team up, there should be a clear delimitation between the work of
that each person does. Both students should turn in separate
writeups.
I strongly encourage you to perform some experiments as part of your
project, in order to gain practical experience with probabilistic
reasoning algorithms. Many algorithms are available free from
universities and research labs, so you would not have to code them.
The resources web page should help you find both papers and software
as needed.
Project themes
If you are already have a research topic in mind, feel free to propose
it. Otherwise, you can choose a topic from the list below (which is
ordered fairly randomly). If no topic suits your interest, please
make an appointment to discuss alternatives.
Proposed topics:

Probabilistic reasoning applied to a problem domain
Such a project will involve describing the problem you have in mind,
formulating it appropriately for probabilistic reasoning, summarizing
existing literature that attempted to solve this problem using
probabilistic methods and/or coming up with a solution yourself.
For such a project, you have to experiment with at least an
algorithm of your choice

Learning in active vision
The problem of active vision investigates where the focus of attention
should be in order to gather as much information as possible about the
task at hand. Reinforcement learning and Bayesian methods are
adequate for this task.

Structured action representations in MDPs
As we will discuss in class, a lot of work in MDPs/RL has been devoted
to structured state space. But a lot less literature exists on
structured action descriptions. This is a researchoriented project,
involving a study on the literature regarding action representations,
and a proposal for how to do planning/learning with richer action
representations.

Effect of exploration strategies in reinforcement learning.
There is a great variety of exploration strategies in RL, varying from
very straightforward methods (such as Boltzmann exploration or
epsilongreedy) to methods very wellmotivated, such as Singh and
Kearns' E3 algorithm. The project would involve surveying and
comparing existing methods.

Effect of eligibility traces in reinforcement learning
Eligibility traces can significantly speed up reinforcement learning.
In class we discuss only one version (accumulating traces) but
several have been proposed. The project will especially involve
looking a variable eligibility trace parameters.

Function approximation in reinforcement learning
This involves surveying the existing methods and theoretical results,
and comparing different algorithms

Yahtzee
For the gameminded people, this is a great application of
probabilities, and it does not need to involve an opponent. I am
interested in finding optimal policies for the whole game, or part of
it. The game is slightly too big to solve exactly, I think, which
makes it interesting. If several people are interested, we can have a
tournament too.

Hierarchical Hidden Markov Models
We discussed the basics of HMMs in class. Hierarchical HMMs can be
more efficient than flat ones. This project will involve describing
how the HMM inference procedures are done in hierarchical HMMs, and
doing one experiment with hierarchical HMMs (possibly describing other
existing applications).

Importance sampling and particle filtering in RL
We talked a bit in class about how these methods are used with RL.
The project involves looking at the current approaches and identifying
others (this is a researchoriented topic).

Using structured CPTs in Bayes nets
This is a very useful technique, but we had no time to discuss it.
The project involves surveying existing techniques, presenting how
they affect the Bayes net inference algorithms, and experimenting with
structured CPTs on a Bayes net of your choice.

Survey of algorithms for dealing with loops in beliefs nets
We talked about this issue in class, but we only really covered
variable elimination and a bit on junction trees. I am interested in
a survey of the other techniques, and comparison.

MCMC methods and applications
We just touched on the very basic in class, Gibbs sampling is the
simplest MCMC methods. The project would be to look at more
sophisticated methods and applications.

Efficient EM approaches
Again, we just talked about the basic EM idea in class. The project
should cover more sophisticated approaches.
Format and dates
Please send me by email by Monday, March 25, a brief
project description, specifying the topic you want to address,
why you are interested in it, a rough plan of what you will do and
five references you think might be useful. You do not have to read
the papers before the proposal, nor do you have to include them in
your final bibliography, if they end up not being relevant. The main
purpose of this document is to inform me of your intentions, so I can
give you feedback on the scope of the work.
Project report.
The report should be approximately 10 pages long (this requirement is
just to get you oriented; do not take it as a hard restriction). The
format should be similar to the research papers we have been reading
during the semester. It should contain the following information:

A description of the topic and why you were interested in it

A review of related literature; this should include at least 5 papers
relevant to your topic. If you want help seeking such papers,
let me know.

One or more specific questions that you wanted to investigate

The methodology you decided to follow (e.g. theory or experiments,
what kind of experiments, etc.)

An analysis of your findings

Conclusion and possible future work directions
The due date for the report is April 30.
Prof. Doina PRECUP
Last modified: Mon Mar 18 12:00:33 EDT 2002