Written Assignment 4 (“W4”)

Total Points: 135

Remember to include your name and case ID. Make sure your answers are concise, neat, and legible. Submit to canvas by the deadline. You can scan your hand-written assignment, but make sure all your answers are legible and scans are complete. Your submitted file must be a .pdf file (.doc or .txt files are not allowed), and the filename should have the following format: W4_yourCaseID .pdf.

Note: Some of the questions below ask you to make plots and/or write simple programs. This might be more convenient to do in a language with a good plotting library such as Matlab or python using matplotlib.

Q1. Deriving a learning rule

In k-means clustering, µk is the vector mean of the kth cluster. Assume the data vectors have I dimensions, so µk is a (column) vector [µ1 , . . . , µI ]k(T), where the symbol T indicates vector transpose.

Derive update rule for µk using the objective function

N   K

D = C C rn,k∥xn− µk∥2

n=1k=1

where xn is the nth data vector, rn,k is 1 if xn is in the kth class and 0 otherwise, and ∥x∥2 = xTx =写ixixi = 写ixi(2) . The update rule is derived by computing the gradient for each element of the kth mean and solving for the value where the gradient is zero. Express your answer first in scalar form for µk,i and in vector form for µk . (20 P.)

Q2. Bernoulli trials and bias beliefs

Recall the binomial distribution describing the likelihood of getting y heads for n flips:

p(y|θ , n) = (  |y(n) θy(1 − θ)n−y

where θ is the probability of heads.

a) Using the fact

l01 p(y|θ , n)dθ =

derive the posterior distribution for θ assuming a uniform prior. (10 P.)

b) Plot the likelihood for n = 4 and θ = 3/4. Make sure your plot includes y = 0. (10 P.)

c) Plot the posterior distribution of θ after each of the following coin flips:  head, head, tail, head.  You should have four plots total. (10 P.)

Q3. After R&N 20.1 Bags O’Surprise

The data used for Figure 20.1 (page 804 in 3rd edition or page 723 in the 4th edition) can be viewed as being generated by h5 , since P(h5|d) 一 1.0 as the number of observations increases.

a) For each of the other four hypotheses, write code to generate a data set of length 100 and plot the corresponding graphs for P(hi|d1 , . . . , dN ) and P(DN+1 = lime|d1 , . . . , dN ).  The plots should follow the format of Figure 20.1. Comment on your results. (20 P.)

b) What is the mathematical expression for how many candies you need to unwrap before you are more 90% sure which type of bag you have? (10 P.)

c) Make a plot that illustrates the reduction in variabilty of the curves for the posterior probability for each type of bag by averaging each curve obtained from multiple datasets. (20 P.)