CX4240 Homework 1

Caiden

homework.pdf

Home >Mathematics homework help >CX4240 Homework 1

CX4240 Homework 1

Le Song

Deadline: 2/06 Thur, 9:30am (before starting the class)

• Submit your answers as an electronic copy on T-square.

• No unapproved extension of deadline is allowed. Late submission will lead to 0 credit.

• Typing with Latex is highly recommended. Typing with MS Word is also okay. If you handwrite, try to be clear as much as possible. No credit may be given to unreadable handwriting.

• Explicitly mention your collaborators if any.

1 Probability

On the morning of September 31, 1982, the won-lost records of the three leading baseball teams in the western division of the National League of the United States were as follows:

Team Won Lost

Atlanta Braves 87 72 San Francisco Giants 86 73 Los Angeles Dodgers 86 73

Each team had 3 games remaining to be played. All 3 of the Giants games were with the Dodgers, and the 3 remaining games of the Braves were against the San Diego Padres. Suppose that the outcomes of all remaining games are independent and each game is equally likely to be won by either participant. If two teams tie for first place, they have a playoff game, which each team has an equal chance of winning.

(a) What is the probability that Atlanta Braves wins the division? [5 pts]

(b) What is the probability that San Francisco Giants wins the division? [5 pts]

(d) What is the probability to have an additional playoff game? [5 pts]

2 Maximum Likelihood

Suppose we have n i.i.d (independent and identically distributed) data samples from the following probability distribution. This problem asks you to build a log-likelihood function, and find the maximum likelihood estimator of the parameter(s).

(a) Poisson distribution [5 pts]

The Poisson distribution is defined as

P(xi = k) = λke−λ

k! (k = 0, 1, 2, ...).

What is the maximum likelihood estimator of λ?

(b) Exponential distribution [5 pts]

The probability density function of Exponential distribution is given by

f(x) =

{ λe−λx x ≥ 0

0 x < 0

What is the maximum likelihood estimator of λ?

Suppose we have n i.i.d (Independent and Identically Distributed) data samples from a univariate Gaussian normal distribution N(µ,σ2), which is given by

N(x; µ,σ2) = 1

σ √

2π exp

( −

(x−µ)2

2σ2

) .

What is the maximum likelihood estimator of µ and σ2?

3 Principal Component Analysis

In class, we learned that Principal Component Analysis (PCA) preserves variance as much as possible. We are going to explore another way of deriving it: minimizing reconstruction error.

Consider data points xn(n = 1, ...,N) in D-dimensional space. We are going to represent them in {u1, ...,uD} coordinates. That is,

xn =

D∑ i=1

αni ui =

D∑ i=1

(xn T ui)ui.

Here, αni is the length when x n is projected onto ui.

Suppose we want to reduce the dimension from D to M < D. Then the data point xn is approximated by

x̃n =

M∑ i=1

zni ui +

D∑ i=M+1

biui.

In this representation, the first M directions of ui are allowed to have different coefficient zni for each data point, while the rest has a constant coefficient bi. As long as it is the same value for all data points, it does not need to be 0.

Our goal is setting ui, zni, and bi for n = 1, ...,N and i = 1, ...,D so as to minimize reconstruction error. That is, we want to minimize the difference between xn and x̃n:

J = 1

N∑ n=1

‖xn − x̃n‖2

(a) What is the assignment of znj for j = 1, ...,M minimizing J? [5 pts]

(b) What is the assignment of bj for j = M + 1, ...,D minimizing J? [5 pts]

(d) What should be the ui for i = 1, ...,D to minimize J? [8 pts]

Hint: Use S = 1 N

∑N n=1(x

n − x̄)(xn − x̄)T for sample covariance matrix.

4 Image Compression using Principal Component Analysis

For this section, you will be using PCA to perform dimensionality reduction on the given dataset (q4.mat). This dataset contains vectorized grey scale photos of all members of the class. The file contains a matrix ’faces’ of size (62x 4500) for each of the 59 students (as well as 2 TA’s and Prof) in the class. You are to use Principal Component Analysis to perform Image Compression.

• Submit a plot of the Eigen values in ascending order (Visualize the increase of Eigen values across all Eigen vectors).

• Select a cut off to choose the top n eigen faces (or vectors) based on the graph. Discuss the reasoning for choosing this cut off.

• For your choosen eigen faces, calculate the reconstruction error (Squared distance from original image, and reconstructed image) for the first two images in the dataset. (They are images of the two TAs).

• Vary the number of eigen faces to view the differences in reconstruction error and in the quality of the image. Use imshow() to display the two images for your choosen n eigen faces. Attach the two images to your submission.

Hint: Use Matlab function eig or eigs for calculating the eigen values and vectors. For reconstructing the images, you can convert the row vectors to matrices using reshape(rowVector, 75, 60)