HW3 Solutions San Jose City College CS 189

CS 189 Introduction to Machine Learning
Spring 2021 Jonathan Shewchuk HW3
Due: Wednesday, February 24 at 11:59 pm

This homework consists of coding assignments and math problems.
Begin early; you can submit models to Kaggle only twice a day!
DELIVERABLES:

1. Submit your predictions for the test sets to Kaggle as early as possible. Include your Kaggle
scores in your write-up. The Kaggle competition for this assignment can be found at
• MNIST: https://www.kaggle.com/c/spring21-cs189-hw3-mnist
• SPAM: https://www.kaggle.com/c/spring21-cs189-hw3-spam
2. Write-up: Submit your solution in PDF format to “Homework 3 Write-Up” in Gradescope.
• On the first page of your write-up, please list students with whom you collaborated
• Start each question on a new page. If there are graphs, include those graphs on the
same pages as the question write-up. DO NOT put them in an appendix. We need each
solution to be self-contained on pages of its own.
• Only PDF uploads to Gradescope will be accepted. You are encouraged use LATEX
or Word to typeset your solution. You may also scan a neatly handwritten solution to
produce the PDF.
• Replicate all your code in an appendix. Begin code for each coding question in a fresh
page. Do not put code from multiple questions in the same page. When you upload this
PDF on Gradescope, make sure that you assign the relevant pages of your code from
appendix to correct questions.
• While collaboration is encouraged, everything in your solution must be your (and only
your) creation. Copying the answers or code of another student is strictly forbidden.
Furthermore, all external material (i.e., anything outside lectures and assigned readings,
including figures and pictures) should be cited properly. We wish to remind you that
consequences of academic misconduct are particularly severe!
3. Code: Submit your code as a .zip file to “Homework 3 Code”.
• Set a seed for all pseudo-random numbers generated in your code. This ensures
your results are replicated when readers run your code.
• Include a README with your name, student ID, the values of random seed (above) you
used, and any instructions for compilation.
• Do NOT provide any data files. Supply instructions on how to add data to your code.
• Code requiring exorbitant memory or execution time might not be considered.



HW3, ©UCB CS 189, Spring 2021. All Rights Reserved. This may not be publicly shared without explicit permission. 1

, • Code submitted here must match that in the PDF Write-up. The Kaggle score will not be
accepted if the code provided a) does not compile or b) compiles but does not produce
the file submitted to Kaggle.
4. The assignment covers concepts on Gaussian distributions and classifiers. Some of the ma-
terial may not have been covered in lecture; you are responsible for finding resources to
understand it.

1 Honor Code
Declare and sign the following statement (Mac Preview and FoxIt PDF Reader, among others, have
tools to let you sign a PDF file):
“I certify that all solutions are entirely my own and that I have not looked at anyone else’s solution.
I have given credit to all external sources I consulted.”
Signature:


2 Gaussian Classification
Let f (x | Ci ) ∼ N(µi , σ2 ) for a two-class, one-dimensional classification problem with classes C1
and C2 , P(C1 ) = P(C2 ) = 1/2, and µ2 > µ1 .

1. Find the Bayes optimal decision boundary and the corresponding Bayes decision rule by
finding the point(s) at which the posterior probabilities are equal.
2. Suppose the decision boundary for your classifier is x = b. The Bayes error is the probability
of misclassification, namely,
Pe = P((C1 misclassified as C2 ) ∪ (C2 misclassified as C1 )).
Show that the Bayes error associated with this decision rule, in terms of b, is
Z b  
 (x − µ2 )2   (x − µ1 )2  
  Z ∞ 
1
Pe (b) = √  dx +  dx .

 exp − exp −
2 2πσ −∞ 2σ2 b 2σ2

3. Using the expression above for the Bayes error, calculate the optimal decision boundary b∗
that minimizes Pe (b). How does this value compare to that found in part 1? Hint: Pe (b) is
convex for µ1 < b < µ2 .

Solution:

1.
P(C1 | x) = P(C2 | x) ⇔
f (x | C1 ) P(C 1)
f (x)
= f (x | C2 ) P(C 2)
f (x)
⇔
f (x | C1 ) = f (x | C2 ) ⇔
N(µ1 , σ2 ) = N(µ2 , σ2 ) ⇔
(x − µ1 )2 = (x − µ2 )2

HW3, ©UCB CS 189, Spring 2021. All Rights Reserved. This may not be publicly shared without explicit permission. 2

, µ1 +µ2
Thus, the decision boundary is the point equidistant to µ1 and µ2 : b = 2
.
The corresponding decision rule is, given a data point x ∈ R:
µ1 +µ2
• if x < 2
, then classify x in class 1;
• otherwise, classify x in class 2.
Note that this is the centroid method.
2. Applying basic rules of probability, we have

Pe = P((C1 misclassified as C2 ) ∪ (C2 misclassified as C1 ))
= P(C1 misclassified as C2 ) + P(C2 misclassified as C1 )
= P(misclassified as C2 | C1 )P(C1 ) + P(misclassified as C1 | C2 )P(C2 ).

We know P(C1 ) = P(C2 ) = 21 . Thus, we use the PDF to calculate
Z b
1
e−(x−µ2 ) /(2σ ) dx.
2 2
P(misclassified as C1 | C2 ) = √
−∞ 2πσ

Z ∞
1
e−(x−µ1 ) /(2σ ) dx.
2 2
P(misclassified as C2 | C1 ) = √
b 2πσ
Therefore,
1
Pe (b) = P(misclassified as C1 | C2 ) + P(misclassified as C1 | C2 )


2 Z b
(x−µ2 )2
Z ∞ (x−µ )2 
1 1
= √ e 2σ2 dx + e− 2σ2 dx .
 − 

2 2πσ −∞ b


3. We know the optimal decision boundary must lie between µ1 and µ2 (convince yourself this
is the case!). Thus, we can minimize Pe (b) by taking the derivative and setting it equal to
zero. Letting C = 2 √12πσ , f1 (x) = e−(x−µ2 ) /(2σ ) , and f2 (x) = e−(x−µ1 ) /(2σ ) , we have
2 2 2 2



Z Z ∞ 
dPe (b) d  b
= C  f1 (x)dx +

f2 (x)dx
db db −∞ b
 Z  !
 d  b  d Z ∞
= C   f1 (x)dx + f2 (x)dx  .

db −∞ db b

From the fundamental theorem of calculus, we know that, for continuous functions f (x) such
that | f | → 0 for x → −∞, Z x
d
f (t) dt = f (x).
dx −∞
Noting that f1 and f2 satisfy these properties, we apply that here to get
dPe (b)
= C f1 (b) − f2 (b)] .
 
db

HW3, ©UCB CS 189, Spring 2021. All Rights Reserved. This may not be publicly shared without explicit permission. 3