# Homework

## Spring 2011

Homework 11
Due Thursday 4/21 in class

• Thrun ch 15, ex 1(a) - 1(d)
• Morris p51 ex 7
• Define a matrix game to be fair if its value is zero. Consider the matrix game [ a 2 ; 1 -1 ]. For which values of the paramter a is the game fair? When does it favor the row player (positive value)? When does it favor the column player?

Homework 10
Due Fri 4/8 5pm

Implement EM to train an HMM for the data from Homework 6. The model should have four hidden states with gaussian observation probabilities. Does the HMM model the data better than the original mixture of gaussians?

Homework 9
Due Thursday 3/31 in class

• Bishop 4.12, 4.13, 4.14, 4.15, 4.20

Homework 8
Due Tuesday 3/15 in class

• Midterm review problems

Homework 7
Due Thursday 3/3 in class

• Kearns and Vazirani 3.1, 3.6
Homework 6
Due Fri 2/25 5pm

Implement EM fitting of a mixture of gaussians on the two-dimensional data set points.dat. You should 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 5
Due Tu 2/15 in class

• Bishop 6.2, 6.8, 6.9
• Bishop 7.2, 7.7
Homework 4
Due Wed 2/9 5pm

• Implement a perceptron and naive bayes on the voting dataset using MATLAB. For perceptron, use a sigmoid activation function and squared error. For naive bayes, optimize your Dirichlet prior on the tuning set. Compare results with the decision tree.
Homework 2
Due Friday 1/28 5pm

• Implement a decision tree classifier to predict the party of a US representative from their voting record: voting2.dat.
Homework 2
Due Thursday 1/20 in class

• Prove that, given a set of n i.i.d. observations x_1 to x_n, a distribution Q that minimizes the KL divergence with the empirical distribution P, D(P||Q), also maximizes the probability of the data Q(x_1 ... x_n).
• Prove (step by step) that entropy for a discrete random variable is maximized by the uniform distribution.
Homework 1
Due Tuesday 1/18 in class

Bishop ex. 1.3, 1.11

gildea @ cs rochester edu
April 14, 2011