CS 534
Assignment #2: probability
Due: March 16
Part 1: Gibbs sampling
What you will write
You will write code that uses Gibbs sampling to compute conditional probabilities for a Bayesian network. Note: part of this assignment will be an interview with the course staff including questions about the code. If we conclude the code is not yours, you will receive an NR for the course and we will initiate formal procedures for academic dishonesty.
To enable you to focus on Gibbs sampling, your code is only responsible for working with one specific network structure provided at https://docs.google.com/spreadsheets/d/1wgIZUV3dvcKMC5_yAbDCHW-lvj1ON7LBNnVGUvyTSkA/edit?usp=sharing
Input/Output format
Your program will take the following command-line arguments:
- The node to query, and the observed evidence nodes. You can assume we are only interested in the probabilities of one of the nodes.
- The number of updates to perform. You can assume that each time a node changes value that is an update.
- The number of initial samples to drop before computing the probability.
For example:
gibbs price schools=good location=ugly -u 10000 -d 0
Would query the node size, given evidence location=ugly and schools=good. It would run 10000 iterations of gibbs sampling, and discard none of the observations. The output should be something like:
P(price = cheap) = 0.58
P(price = ok) = 0.34
P(price = expensive) = 0.08
gibbs amenities location=bad neighborhood=good -u 100000 -d 1000
Should return something like:
P(amenities = lots) = 0.15
P(amenities = little) = 0.85
Writeup
For your writeup, come up with 3 queries of varying complexity.
- How did you select which node to update? Did you sweep through the nodes as a batch? Sample randomly? Something else? Justify your decision.
- Experiment with using varying numbers of samples for each of the queries. How many samples are required for the estimated probability to converge? For each query plot the # of samples vs. estimated probability.
- What, if anything, seems to influence the number of samples required?
- Does discarding initial samples speed the convergence of probabilities?
Part 2: Kalman filter
For this question, you will not program and should perform the calculations “by hand.” Code to multiply matrices is fine, but simply finding someone’s code for Kalman filters and running it is not. You are to show the steps of your work. The point of this question is to have you understand the inputs to a Kalman filter and how it updates its estimates. Note: this question goes beyond the simple examples of Kalman filters we did in class.
For this task, consider a scenario where you need to keep track of a country’s gross domestic product using a Kalman filter. For the sensor model, you must make use of at least two sensors. For the transition model, you must consider the prior GDP (position) and the prior rate of growth (velocity). Sketch the network that represents your Kalman filter, and specify all of the necessary CPTs (probability distributions).
Next, compute the estimate of the GDP in the absence of any sensor information.
Finally, compute the estimate of the GDP given that you have information from all of the sensors.
March 7, clarification.
The purpose of this question is for you to understand how Kalman filters work. You will need to : come up with some plausible sensors for GDP, come up with transition and sensor models that are loosely based on reality (it doesn’t have to be publishable economics research, just something that looks plausible like a higher GDP leads to more exports), and hand compute a transition.
