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

Atlanta Braves

San Francisco Giants

Los Angeles Dodgers

Won

87

86

86

Lost

72

73

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 ﬁrst place, they have a playoﬀ 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]

(c) What is the probability that Los Angeles Dodgers wins the division? [5 pts]

(d) What is the probability to have an additional playoﬀ 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 ﬁnd the maximum likelihood

estimator of the parameter(s).

1

(a) Poisson distribution [5 pts]

The Poisson distribution is deﬁned as

P ( xi = k ) =

λk e−λ

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

k!

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

0

x≥0

x<0

What is the maximum likelihood estimator of λ?

(c) Gaussian normal distribution [10 pts]

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

(x − µ)2

1

√ exp −

2σ 2

σ 2π

N (x; µ, σ 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,

D

xn =

D

(xn T ui )ui .

n

αi ui =

i=1

i=1

n

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

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

by

M

xn =

˜

D

n

zi ui +

i=1

bi ui .

i=M +1

In this representation, the ﬁrst M directions of ui are allowed to have diﬀerent coeﬃcient zni for each data

point, while the rest has a constant coeﬃcient 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 diﬀerence between xn and xn :

˜

1

J=

N

N

xn − xn

˜

n=1

2

2

n

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

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

(c) Express optimal xn and xn − xn using your answer for (a) and (b). [2 pts]

˜

˜

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

Hint: Use S =

4

1

N

N

n

n=1 (x

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

¯

¯

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 ﬁle 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 oﬀ to choose the top n eigen faces (or vectors) based on the graph. Discuss the reasoning

for choosing this cut oﬀ.

• For your choosen eigen faces, calculate the reconstruction error (Squared distance from original image,

and reconstructed image) for the ﬁrst two images in the dataset. (They are images of the two TAs).

• Vary the number of eigen faces to view the diﬀerences 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)

Why Work with Us

Top Quality and Well-Researched Papers

We always make sure that writers follow all your instructions precisely. You can choose your academic level: high school, college/university or professional, and we will assign a writer who has a respective degree.

Professional and Experienced Academic Writers

We have a team of professional writers with experience in academic and business writing. Many are native speakers and able to perform any task for which you need help.

Free Unlimited Revisions

If you think we missed something, send your order for a free revision. You have 10 days to submit the order for review after you have received the final document. You can do this yourself after logging into your personal account or by contacting our support.

Prompt Delivery and 100% Money-Back-Guarantee

All papers are always delivered on time. In case we need more time to master your paper, we may contact you regarding the deadline extension. In case you cannot provide us with more time, a 100% refund is guaranteed.

Original & Confidential

We use several writing tools checks to ensure that all documents you receive are free from plagiarism. Our editors carefully review all quotations in the text. We also promise maximum confidentiality in all of our services.

24/7 Customer Support

Our support agents are available 24 hours a day 7 days a week and committed to providing you with the best customer experience. Get in touch whenever you need any assistance.

Try it now!

How it works?

Follow these simple steps to get your paper done

Place your order

Fill in the order form and provide all details of your assignment.

Proceed with the payment

Choose the payment system that suits you most.

Receive the final file

Once your paper is ready, we will email it to you.

Our Services

No need to work on your paper at night. Sleep tight, we will cover your back. We offer all kinds of writing services.

Essays

No matter what kind of academic paper you need and how urgent you need it, you are welcome to choose your academic level and the type of your paper at an affordable price. We take care of all your paper needs and give a 24/7 customer care support system.

Admissions

Admission Essays & Business Writing Help

An admission essay is an essay or other written statement by a candidate, often a potential student enrolling in a college, university, or graduate school. You can be rest assurred that through our service we will write the best admission essay for you.

Reviews

Editing Support

Our academic writers and editors make the necessary changes to your paper so that it is polished. We also format your document by correctly quoting the sources and creating reference lists in the formats APA, Harvard, MLA, Chicago / Turabian.

Reviews

Revision Support

If you think your paper could be improved, you can request a review. In this case, your paper will be checked by the writer or assigned to an editor. You can use this option as many times as you see fit. This is free because we want you to be completely satisfied with the service offered.