Computer Science 246/446

Homework

Spring 2006

Homework 6

Due Thursday April 6 in class

• mackay 29.4
• mackay 29.8
• mackay 29.9

Due Friday April 7 5pm

• Create a Gibbs sampling version of the mixture of gaussians estimator from homework 4. To make things simpler, fix the mixture weights and the (tied) covariance matrix to be the results from the last homework. Sample the latent variables and the means of each cluster using Gibbs sampling. Do Gibbs sampling and EM converge on similar results? Which takes fewer operations?

Homework 5

Due Tuesday March 7 in class

Kearns and Vazirani exercises 3.1, 3.3, 3.4

Homework 4

Due Thursday Feb 16 in class

Convert the following simple belief networks into the factor graph representation, and run the polytree (sum-product) algorithm by hand, computing expressions for each message in terms of the parameters of the original belief net, and showing that the final result gives the desired probability:

• Given network A->B, compute P(B) and P(A|B)
• Given network A->B<-C, compute P(A|B,C)

Due Friday Feb 17 5pm

Implement EM fitting of a mixture of gaussians on the two-dimensional data set hw4.dat. You should (at a minimum) try different numbers of mixtures, as well as tied vs. separate covariance matrices for each gaussian. Which model seems to fit the data best?

Homework 3

Due Friday Feb 10 5pm

Implement the Decision Tree algorithm described in class, including the MDL criterion. Test it using the following dataset: voting2.dat. Turn in your code along with a report describing how the algorithm worked, and any observations about the types of trees it learned. You should try varying (at least) the amount of training data (the training/test split is up to you), whether MDL is used, and how the description length is weighted. You may use any programming language.

Homework 2

Due Tuesday 2/6 in class

• Use Lagrange multipliers to derive the multinomial distribution over K possible outcomes that maximizes entropy.
• Derive the maximum likelihood estimate of the mean and variance of a (one dimensional) Gaussian given N data points.

Homework 1

Due Thursday 1/26 in class

Wasserman ch. 1 ex. 10, 11, 12, 13, 14, 15, 17; ch. 2 ex. 14; ch. 3 ex. 4, 5, 14