Due in class, Tue, Dec 6th.

- Consider the Weighted majority algorithm with both reward and penalty. On a mistake, experts that get it right have their weight increased by a fixed factor R (R > 1) while those who got it wrong have their weight decreased by a factor P (P < 1). What guarantee does this give on the number of mistakes?
- A kernel is pairwise similarity function for which there is a mapping that represents as an inner product in the mapped space, . Show that if are kernels, then so are and . Show that and are kernels. Give an example of a positive similarity function that is not a kernel.
- Consider the EM algorithm for a mixture of two Gaussians: start with random centers, identity covariances and 0.5 mixing weights; repeat: assign each point to the Gaussian that gives the point higher likelihood; compute the mean and covariance of each cluster. Give an example where this algorithm fails, with high probability.