联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-21:00
  • 微信:codinghelp

您当前位置:首页 >> Algorithm 算法作业Algorithm 算法作业

日期: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

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

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

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

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


版权所有:编程辅导网 2021 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp