Last revised:4/5/2011 11:20 AM

CIS 6930-13: Probabilistic Modeling, Estimation, and Inference

Classes: Tuesdays and Thursdays, 12:30 pm to 1:45pm, SOC 153

 

Prof. Sudeep Sarkar (sarkar@csee.usf.edu) Office hrs: 10:30 am to 12 noon Tuesday and Thursdays, ENB 315

Probabilistic methods are useful tools for manipulating uncertainty. They appear in solutions to many real world solutions. This course will concentrate on an extremely useful class of probabilistic solutions based on graphical models and sampling that have found effective in many different domains. They have the elegance and rigor of probabilistic modeling, as well as, offer scalable solutions. The emphasis of the course will be to give you a deep understanding of the underlying theory and to encourage you to use these models in your own research problems or problems of your own choice. The structuring of the course presented below is just a starting point. It will be adapted to the needs of the students enrolled in the class.

 

Topic Listings

1.       Bayesian Networks

o    Genie/Smile software for Bayesian Networks

o    Andrew Moore’s Introductory Lecture on Bayesian reasoning and networks

o    Other Bayesian Network software

  1. Markov Random Fields/Conditional Random Fields
  2. Hidden Markov Models

o      Introduction to HMM by Rabiner and Juang, IEEE ASSP Mag, Jan 1986

o      A tutorial on HMMs and selected application in speech recognition

4.       Bayesian Estimation, Expectation Maximization

  1. Kalman Filters, Particle Filters

o      A Bayesian Approach to Problems in Stochastic Estimation and Control, Ho and Lee

o      Special Issue on Sequential State Estimation - Proceedings of the IEEE (Mar 2004)

o    The Kalman filter

o      A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking by Arulampalam et al., 2002.

Prerequisites

o    Traditional probability and statistics course at an upper undergrad or grad level.

o    Ability to write extensive programs in any language of your choice: C/C++/Matlab etc.

Policies

o    Penalty for unethical activity is a FF and expulsion from the department

o    You are expected to attend all classes

o    There are no make ups for worksheets in any circumstances.

o    If you miss an examination due to a valid, documented reason, considerations for a makeup or prorated grading might be considered. Please get in touch with Dr. Sarkar as soon as possible regarding this.

o    Students who anticipate to be absent from class due to religious observance should inform Dr. Sarkar by email by second class meeting.

o    You do not have the right to sell notes or tapes of lectures generated from this class.

o    Audio and/or video recording of the lectures is prohibited without prior WRITTEN permission.

 

Reference Books (on reserve in the library)

o    Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference

o    Richard O. Duda, Peter E. Hart and David G. Stork, Pattern Classification

o    Athanasios Papoulis, Probability, random variables, and stochastic processes

 

Grading

o    Programming tasks (3): 60%

o    Individual Reports (15% each), Group Presentations (5% each)

o    Worksheets, Attendance, Participation: 20%

o    Tests (2): 20%

 

Tentative Schedule

 

First Day

of Week

Topics

Second Day
of Week

Topics

Jan 11

Probability Basics (Joint, Marginal, Conditional, Bayes rule, Independence)

Jan 13

Bayesian Networks (Two node networks, correspondence between Bayes rule updating and message passing.)

Jan 18

Bayesian Networks (Three node configurations and updating by message passing.)

Jan 20

Bayesian Networks (General polytree updating equations.)

Jan 25

Bayesian Networks (Polytree updating equations contd.)

Jan 27

Bayesian Networks (Work through examples.)

 

Feb 1

Bayesian Networks – Gibbs sampling

Feb 3

Markov Networks

Feb 8

Markov Random Fields 

Assignment 1 due

Feb 10

Review for Test One

Feb 15

Test One

Feb 17

Summary Presentations 1

 

Feb 22

Markov Random Fields: Join trees

Feb 24

Multivariate Gaussian Distributions

March 1

Estimation: Maximum Likelihood

Assignment 2 (part 1) due

Mar 3

ML Estimation

Mar 8

Bayesian Estimation

Mar 10

Bayesian Estimation

Mar 15

SPRING BREAK

Mar 17

SPRING BREAK

Mar 22

Video: Graphical Models (Due April 8)

Mar 24

Assignment 2 due (Friday)

Mixture of Gaussians ML Estimate

Mar 29

Review for Test 2

Mar 31

TORNADO WARNING – CLASSES CANCELLED

Apr 5

Summary Presentations 2

Apr 7

Test Two

Apr 12

Kalman Filters (single state/obs pair distributions for the Gaussian case, make connection to recursive Bayesian)

Apr 14

Kalman filters

(do an example, extended Kalman filters)

Apr 19

 

Particle Filters

Apr 21

Markov Chain Monte Carlo (MCMC) and applications

Apr 26

 

Conditional Random Fields

Apr 28

 

Conditional Random Fields

May 1 (Sunday)

Summary Presentation 3 (3pm to 5pm)

 

 

 

       

 

Assignments

 

The following are assignments. For each assignment upload on Blackboard (i) a 5 page report/paper, and (ii) source code, all zipped as one file.

Assignment 1:

1.       Download Genie/Smile code from HERE

2.       Design your own polytree Bayesian network(s) using Genie. One example is the alarm network in Pearl’s book. You can design your networks too.

3.       Implement Pearl’s polytree updating strategy by message passing. The program should be able to read the Bayesian network saved in one of the formats by Genie/Smile; there are 7 formats, pick one that you are comfortable with.

4.       Compare the performance of your code with the results produced by the GENIE/SMILE code. To compare performance compute the posterior probabilities of the nodes in your network given some evidence.

5.       Experiment with multiple evidences too. Do the order of the evidence matter in terms of the final answer? Show examples.

6.       The Bayesian inference algorithm that we studied can help us compute the marginal probabilities of  each node. Can you use the updating mechanism to compute the pair-wise joint probabilities of the nodes?

7.       For the alarm network, study the effect of perturbing the conditional probability specifications on the updated probabilities of the nodes. Which conditional probability specifications have the most effect?

8.       Write a report (5 pages at most) in a conference format. Follow the format at http://www.auai.org/uai2011/instructions.html

9.       Submit report (in PDF format), zipped file of your polytree code.

 

 

Assignment 2: In this assignment you will design a graphical model (Bayesian network or Markov network), implement and reason with it using SMILE. You will be using the API provides through SMILE to input, infer, and output information.

1.       Each group will choose and focus on one application area and one problem definition. This problem could be from a research area of group member or from a journal paper that uses Markov or Bayesian networks. The network should have more than 50 nodes; the richer the structure, the better. Description of this problem, along with a support journal paper or extended document, is due on March 1, 2011. One submission per group is sufficient

2.       Each member of a group will individually implement the chosen problem using SMILE and performs a set of analyses. You have to be creative about the kind of experiments and analyses you want to conduct.

3.       Each member of a group will individually write a report (5 pages at most) in a conference format. Follow the format at http://www.auai.org/uai2011/instructions.html Submit report (in PDF format), zipped file of your code.

 

Assignment 3: Color pixel values in an image can be modeled as a mixture of Gaussians over RGB values. Write code to estimate the mixture parameters. As outputs, show the posteriors of the components as images so that all pixels from the same component or the same Gaussian mode are bright and the rest are dark. (The TA (Ravi) can help you with reading and writing images.) In your report show some results from images downloaded from the internet. Experiment with the number of components? Think and research about how you would choose the number of components in a systematic/rigorous manner. Show some results with your finding.

 

Extra Credit Assignments: These do not have any presentations associated with them. Each is worth 10% pts.

These are all due by April 28th.

1.    Implement Bayesian network reasoning based on Gibbs sampling. (see Pearl’s book for algorithm). Compare with exact reasoning as computed by Genie. This form of reasoning works for Bayesian nets with cycles.

2.             Implement Kalman filters. Test with synthetic sequences generated using a prespecified model.

3.             Apply any of the methods discussed in this class to a problem from your research domain and show how it works.

 

 

 Summary Presentations

 

There will be 5 groups for summary presentations. Each group will have upto 6 students. Each presentation should be a synthesis of the results/findings of the group. One person chosen by the group will present to the class.

1.       Bayes group

  1. Markov group
  2. Kolmogorov group
  3. Pearl group
  4. Kalman group