Description
Question 1 (Problem 3 – Final 2019)
There was a village surrounded by hundreds of lakes. Each lake was either poisonous or healthy.
Anyone who ate fish from a poisonous lake would die immediately while anyone who ate fish from
a healthy lake would survive. All fish looked and tasted identical and villagers knew no other way
of knowing whether a lake was poisonous or healthy, which of course was a huge problem for the
villagers.
Fortunately, a famous chemist visited the village and was told of this dilemma. The chemist suggested using the pH level of water to determine whether a given lake was poisonous or healthy, and
hypothesized that lakes with poisonous fish would have higher pH value than healthy lakes. Accordingly, the chemist visited each lake and collected the pH value of the water in each lake. The data
set is denoted by D = {l1, l2, . . . , lN }, where li denotes the pH level of the lake i ∈ {1, 2, . . . , N}.
Assume that l1 ≤ l2 ≤ l3 ≤ . . . ≤ lN .
You are hired as a machine learning scientist to help determine the probability that a randomly
selected lake is poisonous given its pH value. In order to do this you propose to use a Gaussian
Mixture Model (GMM) as follows.
• Pr(lake is poisonous) = p1
• Pr(lake is healthy) = p2
• f(pH = l| lake is poisonous) ∼ N (µ1, σ2
1
)
• f(pH = l| lake is healthy) ∼ N (µ2, σ2
2
)
• µ1 ≥ µ2 as the pH value for poisonous lakes will be higher on average.
Here f(·) denotes the conditional density function for the pH value. You decide to use the EM
algorithm to train the above GMM on the dataset D.
1
Homework Problems – Tutorial #9 Due: March 27, 2022 11:59 PM
(a) Using the above GMM, provide an expression of the probability that a randomly selected lake
is poisonous given that its pH level is measured to be l.
(b) Write down the pseudocode for the EM algorithm with hard decisions that finds the parameters of the GMM. Assume that we initialize the algorithm in such a way that B2 =
{l1, l2, . . . , lK} denotes one cluster of lakes and B1 = {lK+1, lK+2, . . . , lN } denotes its complement.
(c) Write down the pseudocode for the EM algorithm with soft decisions that finds the parameters
of the GMM. Do state the initialization of your algorithm explicitly.
(d) Suppose that N = 5 and we observe D = {1, 2, 3, 6, 10}. Let B2 = {1, 2, 3} and B1 = {6, 10}.
Execute the hard decision EM algorithm and compute the parameters of the GMM.
Question 2 (Problem 8.2 from LFD)
Consider the dataset X with three data points in R
2
, and the label vector y consisting of the labels
of the three data points:
X =
0 0
0 −1
−2 0
, y =
−1
−1
+1
. (1)
Use X and y to train a SVM by solving the following optimization problem. Obtain the optimal
hyperplane (b
?
, w?
) and its margin.
min
w,b
1
2
w
>w
subject to yn(w
>xn + b) ≥ 1, n = 1, . . . , N
(2)