COMS 4771 SP21 HW1

 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.
 

热门主题

课程名

mktg2509 csci 2600 38170 lng302 csse3010 phas3226 77938 arch1162 engn4536/engn6536 acx5903 comp151101 phl245 cse12 comp9312 stat3016/6016 phas0038 comp2140 6qqmb312 xjco3011 rest0005 ematm0051 5qqmn219 lubs5062m eee8155 cege0100 eap033 artd1109 mat246 etc3430 ecmm462 mis102 inft6800 ddes9903 comp6521 comp9517 comp3331/9331 comp4337 comp6008 comp9414 bu.231.790.81 man00150m csb352h math1041 eengm4100 isys1002 08 6057cem mktg3504 mthm036 mtrx1701 mth3241 eeee3086 cmp-7038b cmp-7000a ints4010 econ2151 infs5710 fins5516 fin3309 fins5510 gsoe9340 math2007 math2036 soee5010 mark3088 infs3605 elec9714 comp2271 ma214 comp2211 infs3604 600426 sit254 acct3091 bbt405 msin0116 com107/com113 mark5826 sit120 comp9021 eco2101 eeen40700 cs253 ece3114 ecmm447 chns3000 math377 itd102 comp9444 comp(2041|9044) econ0060 econ7230 mgt001371 ecs-323 cs6250 mgdi60012 mdia2012 comm221001 comm5000 ma1008 engl642 econ241 com333 math367 mis201 nbs-7041x meek16104 econ2003 comm1190 mbas902 comp-1027 dpst1091 comp7315 eppd1033 m06 ee3025 msci231 bb113/bbs1063 fc709 comp3425 comp9417 econ42915 cb9101 math1102e chme0017 fc307 mkt60104 5522usst litr1-uc6201.200 ee1102 cosc2803 math39512 omp9727 int2067/int5051 bsb151 mgt253 fc021 babs2202 mis2002s phya21 18-213 cege0012 mdia1002 math38032 mech5125 07 cisc102 mgx3110 cs240 11175 fin3020s eco3420 ictten622 comp9727 cpt111 de114102d mgm320h5s bafi1019 math21112 efim20036 mn-3503 fins5568 110.807 bcpm000028 info6030 bma0092 bcpm0054 math20212 ce335 cs365 cenv6141 ftec5580 math2010 ec3450 comm1170 ecmt1010 csci-ua.0480-003 econ12-200 ib3960 ectb60h3f cs247—assignment tk3163 ics3u ib3j80 comp20008 comp9334 eppd1063 acct2343 cct109 isys1055/3412 math350-real math2014 eec180 stat141b econ2101 msinm014/msing014/msing014b fit2004 comp643 bu1002 cm2030
联系我们
EMail: 99515681@qq.com
QQ: 99515681
留学生作业帮-留学生的知心伴侣!
工作时间:08:00-21:00
python代写
微信客服:codinghelp
站长地图