 #### 聯系方式 #### 您當前位置：首頁 >> Matlab編程Matlab編程

###### 日期：2019-07-19 08:29

COMS 4771 SU19 HW1

Due: Sun Jul 21, 2019 at 11:59pm

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

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)+f0.

Assuming that there exists L ≥ 0 such that for all a, b ∈ R, |f0(a)f0

(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 f0

(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

2

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.)

3

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

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