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/non-Gaussian 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 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.
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