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.