CS 189/289A Introduction to Machine Learning HW2 Solutions University of California, Berkeley COMPSCI 189
48 views 0 purchase
Course
COMPSCI 189
Institution
COMPSCI 189
CS 189/289A Introduction to Machine Learning
Spring 2021 Jonathan Shewchuk HW2: I r Math
Due Wednesday, February 10 at 11:59 pm
• Homework 2 is an entirely written assignment; no coding involved.
• We prefer that you typeset your answers using LATEX or other word processing software. If
yo...
cs 189289a introduction to machine learning spring 2021 jonathan shewchuk hw2 i r math due wednesday
february 10 at 1159 pm • homework 2 is an entirely written assignment no coding in
Written for
COMPSCI 189
All documents for this subject (1)
Seller
Follow
ExamsConnoisseur
Reviews received
Content preview
CS 189/289A Introduction to Machine Learning
Spring 2021 Jonathan Shewchuk HW2: I r Math
Due Wednesday, February 10 at 11:59 pm
• Homework 2 is an entirely written assignment; no coding involved.
• We prefer that you typeset your answers using LATEX or other word processing software. If
you haven’t yet learned LATEX, one of the crown jewels of computer science, now is a good
time! Neatly handwritten and scanned solutions will also be accepted.
• In all of the questions, show your work, not just the final answer.
• Start early. This is a long assignment. Most of the material is prerequisite material not
covered in lecture; you are responsible for finding resources to understand it.
Deliverables:
1. Submit a PDF of your homework to the Gradescope assignment entitled “HW2 Write-Up”.
You may typeset your homework in LATEX or Word (submit PDF format, not .doc/.docx
format) or submit neatly handwritten and scanned solutions. Please start each question on
a new page. If there are graphs, include those graphs in the correct sections. Do not put
them in an appendix. We need each solution to be self-contained on pages of its own.
• In your write-up, please state whom you had discussions with (not counting course staff)
about the homework contents.
• In your write-up, please copy the following statement and sign your signature next to it.
(Mac Preview and FoxIt PDF Reader, among others, have tools to let you sign a PDF
file.) We want to make it extra clear so that no one inadvertently cheats.
“I certify that all solutions are entirely in my own words and that I have not looked at
another student’s solutions. I have given credit to all external sources I consulted.”
,1 Identities with Expectation
For this exercise, the following identity might be useful: for a probability event A, P(A) = E[1{A}],
where 1{·} is the indicator function.
1. Let X be a random variable with density f (x) = λe−λx 1{x > 0}. Show that E[X k ] = k!
λk
for
integer k ≥ 0. Hint: One way is to do induction on k.
2. For any non-negative random variable X and constant t > 0, show that P(X ≥ t) ≤ E[X]
t
.
Hint: show that for a, b > 0, 1{a ≥ b} ≤ ab .
3. For any non-negative random variable X, prove the identity
Z ∞
E[X] = P(X ≥ t)dt.
0
You may assume that X admits a density to simplify.
4. For any non-negative random variable X with finite variance (i.e., E[X 2 ] < ∞), prove that
(EX)2
P(X > 0) ≥ .
E[X 2 ]
Hint: Use the Cauchy–Schwarz inequality hu, vi2 ≤ hu, uihv, vi. You have most likely seen it
applied when the inner product is the real dot product; however, it holds for arbitrary inner
products. Without proof, use the fact that the expectation E[UV] is a valid inner product of
random variables U and V.
(Note that by assumption we know P(X ≥ 0) = 1, so this inequality is indeed quite powerful.)
5. For a random variable X with finite variance and E[X] = 0, prove that
E[X 2 ]
P(X ≥ t) ≤ for any t ≥ 0
E[X 2 ] + t2
Hint: Try using logic similar to Question 1.4 on t − X.
Solution:
1. Moment Generating Function. Calculate the MGF: MX (t) = E[etX ] = x>0 λe(t−λ)x dx =
R
1
1−(t/λ)
if t < λ and undefined otherwise. Since the MGF is defined in a neighborhood of 0
(specifically |t| < λ), all moments E[X k ] exist. Furthermore, from properties of the MGF,
E[X k ] 1
is the coefficient of tk . Expanding 1−(t/λ) as k≥0 λ1k tk completes the solution.
P
k!
R ∞ case: EX = 1. Inductive hypothesis: for k > 0, EX = λ EX . Inductive
0 k k k−1
Induction. Base
step: EX k = 0 λxk e−λx dx. Let u = xk and dv = λe−λx , so du = kxk−1 and v = −e−λx . Then
R∞ R∞ R∞
0
λxk e−λx dx = [−xk e−λx ]∞
0 + 0 kx e dx = 0 + λk 0 λxk−1 e−λx dx = λk EX k−1 , where the
k−1 −λx
last equality comes from the inductive hypothesis. So EX k = Πki=0 λi = λk!k . Note that the trick
of separating out the k (= kλλ
) factor in the second-to-last equality represents a generally useful
, approach for solving problems: figure out what form you want the problem to “look like”
and try to transform it as close as possible to that form. Since we know we’re dealing with
k−1
induction, we know we would
R ∞ like to somehow obtain EX during the inductive step. By
our assumption, EX k−1 = 0 λxk−1 eλx dx. By keeping this in mind and paying close attention,
we realize we can move a constant λk outside the integral in the second to last equality, leaving
behind the needed λ factor.
[RUBRIC: There could be other ways to solve this. Any completely correct solution gets (+2
points). Any partially correct or incomplete solution gets (+1 point).]
2. When X ≥ t, 1{X ≥ t} = 1 ≤ Xt . On the other hand, when X < t, 1{X ≥ t} = 0 ≤ X
t
since X is
non-negative. Take expectations on both sides to complete.
[RUBRIC: A completely correct solution gets (+1 point).]
3. First see that X = t≥0 1{X ≥ t}dt. Take expectation and use linearity of expectation: E[X] =
R
R R R∞
E t≥0 1{X ≥ t}dt = t≥0 E[1{X ≥ t}]dt = 0 P(X ≥ t)dt. Note that X need not have a density
function for this solution.
Assuming density f (x):
"Z ∞ # Z ∞Z ∞ Z ∞Z ∞
E[X] = E 1{X ≥ t}dt = 1{x ≥ t}dt f (x)dx = 1{x ≥ t} f (x)dx dt
0 0 0 0 0
Z ∞
= P(X ≥ t)dt.
0
Again assuming density f (x):
Z ∞ Z ∞ Z x Z ∞ Z ∞ Z ∞
E[X] = x f (x)dx = f (x)dtdx = f (x)dxdt = P(X ≥ t)dt
0 0 0 0 t 0
[RUBRIC: A completely correct solution gets (+1 point).]
4. Using the non-negativity of X, we have EX = E[X1{X > 0}]. [RUBRIC: (+1 point)]
Now use Cauchy–Schwarz applied to U := X and V := 1{X > 0} to conclude that
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller ExamsConnoisseur. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $9.99. You're not tied to anything after your purchase.
