COMS 4771 SP21 HW1

Due: Sat Feb 13, 2021 at 11:59pm

This homework is to be done alone. No late homeworks are allowed. To receive credit, a type-

setted copy of the homework pdf must be uploaded to Gradescope by the due date. You must show

your work to receive full credit. Discussing possible solutions for homework questions is encour-

aged on piazza and with your peers, but you must write your own individual solutions and not share

your written work/code. You must cite all resources (including online material, books, articles, help

taken from specific individuals, etc.) you used to complete your work.

1

Analyzing iterative optimization

Minimizing an objective function is of central importance in machine learning. In this problem, we

will analyze the an iterative approach for finding β ∈ Rd that (approximately) minimizes ∥Aβ −b∥2

2

for a given matrix A ∈ Rn×d and vector b ∈ Rn.

Consider the following iteration approximation algorithm:

• Initially, β(0) = (0, . . . , 0) ∈ Rd is the zero vector in Rd.

• For k = 1, 2, . . . , N:

- Compute β(k) := β(k−1) + ηAT(b − Aβ(k−1)).

In above, η > 0 is a fixed positive number usually referred to as the step size, and N is the total

number of iterations. Define M := ATA and v := ATb.

(i) Show that the matrix M is symmetric positive semi-definite.

Throughout, assume that the eigenvalues of M, denoted by λ1, . . . , λd, satisfy λi < 1/η

for all i = 1, . . . , d.

(ii) Prove (e.g., using mathematical induction) that, for any positive integer N,

β(N) = η

N−1

�

k=0

(I − ηM)kv.

(Here, for a square matrix B, we have B0 = I, B1 = B, B2 = BB, B3 = BBB, and so

on.)

(iii) What are the eigenvalues of η �N−1

k=0 (I − ηM)k? Give your answer in terms of λ1, . . . , λd,

η, and N.

1

(iv) Let ˆβ be any non-zero vector in the range of M satisfying M ˆβ = v. Prove that

∥β(N) − ˆβ∥2

2 ≤ e−2ηλminN∥ˆβ∥2

2,

where λmin is the smallest non-zero eigenvalue of M.

Hint: You may use the fact that 1 + x ≤ ex for any x ∈ R.

This implies that as the number of iterations N increases, the difference between our estimate

β(N) and ˆβ decreases exponentially!

2

Statistical Estimators

Here we will study some statistical estimators.

(i) Given a, b ∈ R s.t. a < b, consider the density p(x | θ = (a, b)) ∝

� 1

if a ≤ x ≤ b

0

otherwise

.

Suppose that n samples x1, . . . , xn are drawn i.i.d. from p(x|θ). What is the Maximum Like-

lihood Estimate (MLE) of θ given the samples?

(ii) Show that for the MLE θML of a parameter θ ∈ Rd and any known differentiable function

g : Rd → Rk, the MLE of g(θ) is g(θML).

(iii) For a 1-dimensional Gaussian distribution, give two examples for each of the following types

of estimators for the mean parameter.

• consistent and unbiased.

• consistent, but not unbiased.

• not consistent, but unbiased.

• neither consistent, nor unbiased.

3

Evaluating Classifiers

Consider the following decision rule ft for a two-category problem in R. Given an input x ∈ R

decide category y1, if x > t; otherwise decide category y2

(i) What is the error rate for this rule, that is, what is P[ft(x) ̸= y]?

(ii) Show that at for the optimally selected threshold value t (i.e., the one which gives minimum

error rate), it must be the case that

P(X = t|Y = y1)P(Y = y1) = P(X = t|Y = y2)P(Y = y2).

(iii) Assume that the underlying population distribution has equal class priors (i.e., P[Y = y1] =

P[Y = y2]), and the individual class conditionals (i.e., P[X|Y = y1] and P[X|Y = y1])

are distributed as Gaussians. Give an example setting of the class conditionals (i.e., give an

example parameter settings for the Gaussians) such that for some threshold value t, the rule ft

achieves the Bayes error rate; and similarly, give an example setting of the class conditionals

such that for no threshold value t, the rule ft achieves the Bayes error rate.

2

4

Email spam classification case study

Download the datafile email data.tar.gz. This datafile contains email data of around 5,000

emails divided in two folders ‘ham’ and ‘spam’ (there are about 3,500 emails in the ‘ham’ folder,

and 1,500 emails in the ‘spam’ folder). Each email is a separate text file in these folders. These

emails have been slightly preprocessed to remove meta-data information.

(i) (Embedding text data in Euclidean space) The first challenge you face is how to systematically

embed text data in a Euclidean space. It turns out that one successful way of transforming text

data into vectors is via “Bag-of-words” model. Basically, given a dictionary of all possible

words in some order, each text document can be represented as a word count vector of how

often each word from the dictionary occurs in that document.

Example: suppose our dictionary D with vocabulary size 10 (|D| = 10). The words (ordered

in say alphabetical order) are:

1: also

2: football

3: games

4: john

5: likes

6: Mary

7: movies

8: to

9: too

10: watch

Then any text document created using this vocabulary can be embedded in R|D| by counting

how often each word appears in the text document.

Say, an example text document t is:

John likes to watch football.

Mary likes movies.

Then the corresponding word count vector in |D| = 10 dimensions is:

[ 0 1 0 1 2 1 1 1 0 1]

(because the word “also” occurs 0 times, ”football” occurs 1 time, etc. in the document.)

While such an embedding is extremely useful, a severe drawback of such an embedding is that

it treats similar meaning words (e.g. watch, watches, watched, watching, etc.) independently

as separate coordinates. To overcome this issue one should preprocess the entire corpus to re-

move the common trailing forms (such as “ing”, “ed”, “es”, etc.) and get only the root word.

This is called word-stemming.

Your first task is to embed the given email data in a Euclidean space by: first performing word

stemming, and then applying the bag-of-words model.

Some useful references:

3

• Bag-of-words: http://en.wikipedia.org/wiki/Bag-of-words model

• Word stemming: http://en.wikipedia.org/wiki/Stemming

(ii) Once you have a nice Euclidean representation of the email data. Your next task is to develop

a spam classifier to classify new emails as spam or not-spam. You should compare per-

formance of naive-bayes, nearest neighbor (with L1, L2 and L∞ metric) and decision tree

classifiers.

(you may use builtin functions for performing basic linear algebra and probability calculations

but you should write the classifiers from scratch.)

You must submit your code to receive full credit.

(iii) Which classifier (discussed in part (ii)) is better for the email spam classification dataset? You

must justify your answer with appropriate performance graphs demonstrating the superiority

of one classifier over the other. Example things to consider: you should evaluate how the

classifier behaves on a holdout ‘test’ sample for various splits of the data; how does the training

sample size affects the classification performance.