Starting from:
$30
COMS4771- Homework 01 Solved
1 [Statistical Estimators] Here we will study some statistical estimators.
(i) Given a,b ∈ R s.t. a < b, consider the density .
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 θ ∈ Rd and any known injective 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.
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?
3 [Designing the optimal predictor for continuous output spaces] We studied in class that the “Bayes Classifier” f := argmax 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 , 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 .
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., f00(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 + 2ex. 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.
(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.
(i) Given a,b ∈ R s.t. a < b, consider the density .
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 θ ∈ Rd and any known injective 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.
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?
3 [Designing the optimal predictor for continuous output spaces] We studied in class that the “Bayes Classifier” f := argmax 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 , 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 .
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., f00(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 + 2ex. 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.
(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.
1 file (2.2MB)
