Machine Learning: A Bayesian and Optimization Perspective 2nd Edition

1 Solutions To Problems of Chapter 10 10.1. Show that the step, in a greedy algorithm, that selects the column of the sensing matrix, so that to maximize the correlation between the column and the currently available error vector e(i1), is equivalent with selecting the column that reduces the l2norm of the error vector. Hint: All

1 Solutions To Problems of Chapter 11 11.1. Derive the formula for the number of groupings O(N, l) in Covers theo- rem. Hint: Show first the following recursion O(N+ 1, l) = O(N, l) + O(N, l 1). To this end, start with Npoints and add an extra one. Show that the extra number of linear dichotomies

1 Solutions To Problems of Chapter 12 12.1. Show that if p(z) = N(z|z, z), and p(t|z) = N(t|Az, t|z), then E[z|t] = (1 z+AT1 t|zA)1(AT1 t|zt+1 zz) Solution: We have shown in the Appendix of the chapter that, E[z|t] := z|t=z+ (1 z+AT1 t|zA)1AT1 t|z(tAz) (1) orz|t=(1z+AT1t|zA)1AT1t|zt+I(1z+AT1t|zA)1AT1t|zAz.(2)Recall the matrix inversion identity(P1+BTR1B)1BTR1=P BT(R+BP BT)1.(3)Then the following is true(1z+AT1t|zA)1AT1t|z=zAT(t|z+AzAT)1.(4) orz|t=(1z+AT1t|zA)1AT1t|zt+I(1z+AT1t|zA)1AT1t|zAz.(2)Recall the matrix inversion identity(P1+BTR1B)1BTR1=P BT(R+BP BT)1.(3)Then the following is

16 we get yT(y) = ||y||2+TTy T1A =||y||2+TTy T1+TA.Taking into account that1=1Ty,proves the claim.Combining, the formulae for C, D, E, we obtain thatL(, ) = N2ln(2)12ln |1|+12ln |A|+12Nln 12||y||212TA.(30)Using standard formulae for the differentiation for matrices and determi- T1+TA.Taking into account that1=1Ty,proves the claim.Combining, the formulae for C, D, E, we obtain thatL(, ) = N2ln(2)12ln

1 Solutions To Problems of Chapter 13 13.1. Show Eq. (13.5). Solution: The functional F(q) is defined as F(q) = Zq(Xl,) ln p(X,Xl,) q(Xl,)dXld.(1)Plugging in the mean field approximation, q(Xl,) = qXl(Xl)q(), theprevious equation becomesF(q) = ZqXl(Xl)q() ln p(X,Xl,)qXl(Xl)q()dXld,(2)orF(q) = ZqXl(Xl)Zq() ln p(X,Xl,)ddXlZqXl(Xl) ln qXl(Xl)Zq()ddXlZq() ln q()ZqXl(Xl)dXld,(3)which then leads trivially to the claim. q(Xl,)dXld.(1)Plugging in the

1 Solutions To Problems of Chapter 14 14.1. Show that if Fx(x) is the cumulative distribution function of a random variable x, then the random variable u = Fx(x) follows the uniform distri- bution in [0,1]. Solution: Let u = Fx(x),0u1. Then, we have that Fu(u) := Prob{uu}= Prob{Fx(x) u}= Prob{xF1x(u)}= Prob{xx}=Fx(x) = u.Hence,Fu(u) = uwhich implies that

1 Solutions To Problems of Chapter 15 15.1. Show that in the product n Y i=1 (1 xi) the number of cross product terms, x1x2 xk,1kn, for all possible combinations of x1, , xnis equal to 2nn1.Solution: The claim is true for n= 1. Also, the total number of non-product terms is equal to n, excluding the

1 Solutions To Problems of Chapter 16 16.1. Prove that an undirected graph is triangulated if and only if its cliques can be organized into a join tree. Solution: The proof follows [Jens 01]. a) Let the cliques be organized in a join tree. Let Vbe a leaf clique and let Fbe its unique neighbor. From

1 Solutions To Problems of Chapter 17 17.1. Let := E[f(x)] = Zf(x)p(x)dx and q(x) be the proposal distribution. Show that if w(x) := p(x) q(x), and =1Nw(xi)f(xi), =1Nw(xi)f(xi), =1 N w(xi)f(xi), N X i=1then the variance2f=Eh(E[])2i=1NZf2(x)p2(x)q(x)dx2.Observe that if f2(x)p2(x) goes to zero slower than q(x), then for fixedN 2f .Solution: Following the solution of Problem 14.6, using pin place of , we i=1then the variance2f=Eh(E[])2i=1NZf2(x)p2(x)q(x)dx2.Observe

1 Solutions To Problems of Chapter 18 18.1. Prove that the perceptron algorithm, in its pattern-by-pattern mode of operation, converges in a finite number of iteration steps. Assume that (0) =0. Hint: Note that since classes are assumed to be linearly separable, there exists a normalized hyperplane, , and a > 0, so that ynT xn, n =

1 Solutions To Problems of Chapter 19 19.1. Show that the second principal component in PCA is given as the eigen- vector corresponding to the second largest eigenvalue. Solution As pointed out in the text, the following optimization task is in order, maximize vT v,(1) s.t. vTv= 1,(2)s.t. vTv1= 0.(3)Forming the Lagrangian, taking the gradient and setting it

1 Solutions To Problems of Chapter 2 2.1. Derive the mean and variance for the binomial distribution. Solution: For the mean value we have that, E[x] = n X k=0 kn! (nk)!k!pk(1 p)nk =k=1(nk)!(k1)!pk(1 p)nk=npnXk=1(n1)!(n1) (k1)!(k1)!pk1(1 p)(n1)(k1)=npn1Xl=0(n1)!(n1) l!l!pl(1 p)(n1)l=np(p+ 1 p)n1=np. (1) =k=1(nk)!(k1)!pk(1 p)nk=npnXk=1(n1)!(n1) (k1)!(k1)!pk1(1 p)(n1)(k1)=npn1Xl=0(n1)!(n1) l!l!pl(1 p)(n1)l=np(p+ 1 p)n1=np. (1) = k=1 (nk)!(k1)!pk(1 p)nk =np n X k=1 (n1)! (n1) (k1)!(k1)!pk1(1 p)(n1)(k1) =np n1 X l=0 (n1)! (n1) l!l!pl(1 p)(n1)l =np(p+ 1 p)n1=np. (1) n X n! where the formula

14 cos(2))/2, and also the fact N1 X n=0 cos 4 Nkn + 2=1 2 N1 X n=0 ej(4 Nkn+2)+ej(4 Nkn+2) =12e2jn=0ej4Nkn +12e2jn=0ej4Nkn=12e2j 1ej4NkN1ej4Nk+12e2j 1ej4NkN1ej4Nk= 0,since ej4NkN = 1, where j:= 1.Hence, if stands for an unbiased estimator of , thenvar()22NA2.However, looking back at (15), we can verify that there does not exist afunction gsuch that yRN,g(y)=2NAN1Xn=0 yncos 2Nkn +A2sin 4Nkn + 2.Thus,

1 Solutions To Problems of Chapter 3 3.1. Prove the least squares optimal solution for the linear regression case given in Eq. (3.13). Solution: The cost function is J() = N X n=1 (ynTxn)2 =n=1(ynTxn)(ynxTn),orJ() =NXn=1y2n2T NXn=1xnyn!+T NXn=1xnxTn!.Taking the gradient of the cost with respect to and equating to zero, wefinally get, NXxnxTn!=NXxnyn =n=1(ynTxn)(ynxTn),orJ() =NXn=1y2n2T NXn=1xnyn!+T NXn=1xnxTn!.Taking the gradient of the

1 Solutions To Problems of Chapter 4 4.1. Show that the set of equations =p has a unique solution if > 0 and infinite many if is singular. Solution: a) Let > 0. Then the linear system of equations has a unique solution. The converse is also true. Let the linear system has a unique solution, .

1 Solutions To Problems of Chapter 5 5.1. Show that the gradient vector is perpendicular to the tangent at a point of an isovalue curve. Solution: The differential of the cost function, J(), at a point (i), is given by dJ((i)) = J((i))(i)1d(i)1+. . . +J((i))(i)ld(i)l= [d(i)1, . . . , d(i)l]TJ((i)) = d(i)TJ((i)).However, moving along

1 Solutions To Problems of Chapter 6 6.1. Show that if ACmmis nonnegative definite, its trace is nonnegative. Solution: By the definition of a positive semidefinite matrix, xCm, xHAx0.Hence, this will also be true for x= [1,0,...,0]. Thus, [A]11 0. In thesame way, we can prove that any element in the diagonal is a

1 Solutions To Problems of Chapter 7 7.1. Show that the Bayesian classifier is optimal, in the sense that it minimizes the probability of error. Hint: Consider a classification task of Mclasses and start with the proba- bility of correct label prediction, P(C). Then the probability of error will be P(e)=1P(C). Solution: Let P(C) be the probability

1 Solutions To Problems of Chapter 8 1. Prove the Cauchy - Schwartzs inequality in a general Hilbert space. Solution: We have to show that x,yH, |hx,yi| kxkkyk, and that equality holds only if y=ax,aC.Solution: The inequality holds true for xand/or y=0. Let now y,x6=0.We have0 kxyk2=hxy,xyi=kxk2+||2kyk2hx,yi hy,xi.Since the last inequality is valid for any

19 or kxT2T1(x)k221 21 (kxyk2 kT1(x)yk2) +22 22 (kT1(x)yk2 kT2T1(x)yk2). Let b2= max 2121,2222.Then obviously, we can writekxT2T1(x)k22b2(kxyk2 kT12(x)yk2),whereT12(x) = T2T1(x).Following a similar rationale and by induction we can show thatkxT(x)k2bK2K1(kxyk2 kT(x)yk2),(17)where,T=TKTK1 T1,andbK= max1kKk2k.Now by induction,kT(x)T2(x)k2bK2K1(kT(x)y)k2 kT2(x)yk(18).........................................................kTn1(x)Tn(x)k2bK2K1(kTn1(x)y)k2 kTn(x)yk(19)Summing by parts (17)(19), we obtainXn=1kTn1(x)Tn(x)k2bK2K1kxyk2<+.Hence,limn kTn1(x)Tn(x)k= 0.Note that till now, everything is valid for general Hilbert spaces. b2= max 2121,2222.Then obviously, we

1 Solutions To Problems of Chapter 9 9.1. Show that if xi, yi, i = 1,2, . . . , l, are real numbers, then prove the Cauchy-Schwarz inequality: l X i=1 xiyi!2 l X i=1 x2 i! l X i=1 y2 i!. Solution: Consider the identity l X i=1 (zxi+yi)20,zR. Expanding the previous we getz2lXi=1x2i+ 2zlXi=1xiyi+lXi=1y2i0,z.Since the previous quadratic expansion is nonnegative for every z, weknow from our early