COMS 4771  HW1

COMS 4771  HW1

You are allowed to write up solutions in groups of (at max) two students. These group members
don’t necessarily have to be the same from previous homeworks. Only one submission per group
is required by the due date on Gradescope. Name and UNI of all group members must be clearly
specified on the homework. No late homeworks are allowed. To receive credit, a typesetted 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 encouraged on piazza
and with peers outside your group, but every group must write their own individual solutions. You
must cite all external references you used (including the names of individuals you discussed the
solutions with) to complete the homework.
1 [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)) ∝
n
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
Likelihood Estimate (MLE) of θ given the samples?
(ii) Show that for the MLE θML of a parameter θ ∈ R
d
and any known injective function
g : R
d → R
k
, 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.
2 [Universality of Decision Trees]
(i) Show that any binary classifier g : {0, 1}
D → {0, 1} can be implemented as a decision
tree classifier. That is, for any classifier g there exists a decision tree classifier T with k
nodes n1, . . . , nk (each ni with a corresponding threshhold ti), such that g(x) = T(x)
for all x ∈ {0, 1}
D.
(ii) What is the best possible bound one can give on the maximum height of such a decision
tree T (from part (i))? For what function g is the bound tight?
1
3 [Designing the optimal predictor for continuous output spaces] We studied in class that
the “Bayes Classifier”
f := arg maxy P[Y |X]
?
is optimal in the sense that it minimizes
generalization error over the underlying distribution, that is, it maximizes Ex,y[1[g(x) = y]].
But what can we say when the output space Y is continuous?
Consider predictors of the kind g : X → R that predict a real-valued output for a given input
x ∈ X . One intuitive way to define the quality of of such a predictor g is as
Q(g) := Ex,y[(g(x) − y)
2
].
Observe that one would want a predictor g with the lowest Q(g).
(i) Show that if one defines the predictor as f(x) := E[Y |X = x], then Q(f) ≤ Q(g) for
any g, thereby showing that f is the optimal predictor with respect to Q for continuous
output spaces.
(ii) If one instead defines quality as Q(g) := Ex,y
|g(x) − y|

, which f is the optimal
predictor? Justify your reasoning.
4 [Finding (local) minima of generic functions] Finding extreme values of functions in a
closed form is often not possible. Here we will develop a generic algorithm to find the extremal values of a function. Consider a smooth function f : R → R.
(i) Recall that Taylor’s Remainder Theorem states:
For any a, b ∈ R, exists z ∈ [a, b], such that f(b) = f(a)+f
0
(a)(b−a)+1
2
f
00(z)(b−a)
2
.
Assuming that there exists L ≥ 0 such that for all a, b ∈ R, |f
0
(a) − f
0
(b)| ≤ L|a − b|,
prove the following statement:
For any x ∈ R, there exists some η 0, such that if x¯ := x−ηf0
(x), then f(¯x) ≤ f(x),
with equality if and only if f
0
(x) = 0.
(Hint: first show that the assumption implies that f has bounded second derivative, i.e.,
f
00(z) ≤ L (for all z); then apply the remainder theorem and analyze the difference
f(x) − f(¯x)).
(ii) Part (i) gives us a generic recipe to find a new value x¯ from an old value x such that
f(¯x) ≤ f(x). Using this result, develop an iterative algorithm to find a local minimum
starting from an initial value x0.
(iii) Use your algorithm to find the minimum of the function f(x) := (x − 4)2 + 2e
x
. You
should code your algorithm in a scientific programming language like Matlab to find the
solution.
5 [Email spam classification case study] Download the datafile hw1data.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 remove 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:
– 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 performance 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 Courseworks to receive full credit.
3
(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.
4