Instructions: You can choose any programming language as long as you implement the algorithm from scratch. Use this latex file as a template to develop your homework. Submit your homework on time as a single pdf file to Canvas. Please check Piazza for updates about the homework.
• Principal Component Analysis [60 pts]
Download three.txt and eight.txt. Each has 200 handwritten digits. Each line is for a digit, vectorized from a 16 × 16 grayscale image.
1. (10 pts) Each line has 256 numbers: They are pixel values (0=black, 255=white) vectorized from the im-age as the first column (top-down), the second column, and so on. Visualize the two grayscale images corresponding to the first line in three.txt and the first line in eight.txt.
2. (10 pts) Putting the two data files together (three first, eight next) to form an n × D matrix X where
n = 400 digits and D = 256 pixels. Note we use n × D size for X instead of D × n to be consistent with the convention in linear regression. The i-th row of X is x⊤i, where xi ∈ RD is the i-th image in the combined data set. Compute the sample mean y = 1 n xi. Visualize y as a 16 × 16 grayscale image.
n i=1
3. (10 pts) Center X using y above. Then form the sample covariance matrix S = X⊤X Show the 5 × 5
n−1
submatrix S(1 . . . 5, 1 . . . 5).
4. (10 pts) Use appropriate software to compute the two largest eigenvalues λ1 ≥ λ2 and the corresponding eigenvectors v1, v2 of S. For example, in Matlab one can use eigs(S,2). Show the value of λ1, λ2. Visualize v1, v2 as two 16 × 16 grayscale images. Hint: Their elements will not be in [0, 255], but you can shift and scale them appropriately. It is best if you can show an accompanying ’colorbar’ that maps the grayscale to values.
5. (10 pts) Now we project (the centered) X down to the two PCA directions. Let V = [v1 v2] be the D × 2 matrix. The projection is simply XV. Show the resulting two coordinates for the first line in three.txt and the first line in eight.txt, respectively.
6. (10 pts) Now plot the 2D point cloud of the 400 digits after projection. For visual interest, color the points in three.txt red and the points in eight.txt blue. But keep in mind that PCA is an unsupervised learning method, and it does not know such class labels.
• Directed Graphical Model [20 points]
Consider the directed graphical model (aka Bayesian network) in Figure 1.
1
Homework 6 CS 760 Machine Learning
Figure 1: A Bayesian Network example.
Compute P(B = t | E = f, J = t, M = t) and P(B = t | E = t, J = t, M = t). These are the conditional probabilities of a burglar in your house (yikes!) when both of your neighbors John and Mary call you and say they hear an alarm in your house, but without or with an earthquake also going on in that area (what a busy day), respectively.
2
