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.
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
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
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
A
tutorial on particle filters for online nonlinear/nonGaussian Bayesian
tracking by Arulampalam et al., 2002.
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.
o
Penalty
for unethical activity is a FF and expulsion from the department
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.
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
o Programming tasks (3): 60%
o Individual
Reports (15% each), Group Presentations (5% each)
o Worksheets,
Attendance, Participation: 20%
o Tests
(2): 20%
First Day of Week 
Topics 
Second Day 
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) 


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 pairwise 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 28^{th}.
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.
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