(PrincipleComponent Analysis(PCA): Consider 3 data points in the 2-D space: (-1, -1), (0,0), (1,1). (a) What is the rst principal component (write down the actual vector)? (b) If we project the original data points into the 1-D subspace by the principal component you choose, what are their coordinates in the 1-D subspace? And what is the variance of the projected data? (c) For the projected data you just obtained above, now if we represent them in the original 2-D space and consider them as the reconstruction of the original data points, what is the reconstruction error?

(ExpectationMaximization(EM)): In Naive Bayes, the joint likelihood of the data is:

p(D)=

N Y i=1

p(Xi,Yi)

=

N Y i=1

p(Yi)

M Y j=1

p(Xj i|Yi)

Let us assume that Yi {0,1}i and Xj i {1,2,...,V}i,j. Denote the parameters of p(Y) by and the parameters of p(X|Y) by . In the presence of labeled data (i.e., Yi is observed for all i), we can get estimates of ={0,1}, ={1|0,2|0,...,V|0,1|1,2|1,...,V|1} by counting and normalizing. We denote random variables by capital letters and their values

3

by lowercase letters (e.g., Yi denotes a random variable, yi denotes its assignment from the set of possible values of random variable Yi). Suppose that we do not have labeled data. We can still estimate these parameters using the Expectation Maximization algorithm. (a)Specifythe(log)likelihoodfunctionthatneedstobemaximized(hint: thelikelihood function will now be a summation over all possible assignments to all latent variables). (b) Derive the E-step, i.e., compute the probability of all class assignments for each data point, given current parameters and . (c) Derive the M-step, i.e., compute the parameter updates for each class, given the class assignment distributions for each point from E-step. (d) Specify a good initialization technique and describe your rationale.