Computer Science 246/446

Homework

Spring 2008

Homework 9
Due Thursday 4/11 in class
  • Bishop 1995 7.9
  • Bishop 13.5
Homework 8
Due Tuesday 3/18 in class
  • Midterm review problems.
Homework 7
Due Thursday 3/6 in class
  • Derive (without using VC dimension) a PAC-learning bound for the concept class of axis-aligned squares
  • Kearns and Vazirani 3.1, 3.6
Homework 6
Due Tuesday 2/26 in class
  • Bishop 9.11, 9.19
  • Implement EM for the voting data, using the algorithm you derived in ex 9.19, with party as a hidden variable as votes as independent observed variables conditioned on the party. What can you say about the resulting parameters and clusters? Do the clusters correspond to the real party affliliations?
Homework 5
Due Friday 2/15 5pm
  • Implement a perceptron and multilayer perceptron for the voting data. What seems to be a good number of hidden units?
Homework 4
Due Tuesday 2/12 in class
  • Bishop 5.1, 5.3, 5.7
Homework 3
Due Tuesday 2/5 at 5pm
  • Implement a decision tree classifier and a naive bayes classifier to predict the party of a US representative from their voting record: voting2.dat. Experiment with feature selection methods and write an analysis of which method does better on this data set. You can use any language for the decision tree, but should use matlab for naive bayes.
Homework 2
Due Tuesday 1/29 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).
  • Bayes nets: Prove that, given a network structure A->B->C, A is conditionally independent of C given B.
  • Explaining away: Prove that, given a network structure A->B<-C, A is not independent of C given B, and is independent when marginalizing over B.
Homework 1
Due Tuesday 1/22 in class

Bishop ex. 1.3, 1.5, 1.6, 1.11

gildea @ cs rochester edu
May 9, 2008