CS 229, Public Course Problem Set #1 Solutions: Supervised ...

1 CS229 Problem Set #1 Solutions1CS 229, Public CourseProblem Set #1 Solutions: Supervised s method for computing least squaresIn this Problem , we will prove that if we use Newton s method solve the least squaresoptimization Problem , then we only need one iteration to converge to .(a) Find the Hessian of the cost functionJ( ) =12 Pmi=1( Tx(i) y(i)) :As shown in the class notes J( ) j=mXi=1( Tx(i) y(i))x(i) 2J( ) j k=mXi=1 k( Tx(i) y(i))x(i)j=mXi=1x(i)jx(i)k= (XTX)jkTherefore, the Hessian ofJ( )isH=XTX. This can also be derived by simply applyingrules from the lecture notes on Linear Algebra.(b) Show that the first iteration of Newton s method gives us = (XTX) 1XT~y, thesolution to our least squares :Given any (0), Newton s method finds (1)according to (1)= (0) H 1 J( (0))= (0) (XTX) 1(XTX (0) XT~y)= (0) (0)+ (XTX) 1XT~y= (XTX) 1XT~ , no matter what (0)we pick, Newton s method always finds after logistic regressionIn this Problem you will implement a locally-weighted version of logisticregression, wherewe weight different training examples differently according to the query point.

2 The locally-weighted logistic regression Problem is to maximize ( ) = 2 T +mXi=1w(i)hy(i)logh (x(i)) + (1 y(i)) log(1 h (x(i))) Problem Set #1 Solutions2 The 2 T here is what is known as a regularization parameter, which will be discussedin a future lecture, but which we include here because it is needed for Newton s method toperform well on this task. For the entirety of this Problem you can use the value = this definition, the gradient of ( ) is given by ( ) =XTz wherez Rmis defined byzi=w(i)(y(i) h (x(i)))and the Hessian is given byH=XTDX IwhereD Rm mis a diagonal matrix withDii= w(i)h (x(i))(1 h (x(i)))For the sake of this Problem you can just use the above formulas, but you shouldtry toderive these results for yourself as a query pointx, we choose compute the weightsw(i)= exp ||x x(i)||22 2 .Much like the locally weighted linear regression that was discussed in class,this weightingscheme gives more when the nearby points when predicting the class of a new example.

3 (a) Implement the Newton-Raphson algorithm for optimizing ( ) for a new query pointx, and use this to predict the class contains data and code for this Problem . You should implementthey = lwlr(Xtrain, ytrain, x, tau)function in This func-tion takes as input the training set (theXtrainandytrainmatrices, in the formdescribed in the class notes), a new query pointxand the weight this input the function should 1) compute weightsw(i)for each training exam-ple, using the formula above, 2) maximize ( ) using Newton s method, and finally 3)outputy= 1{h (x)> }as the provide two additional functions that might help. The[Xtrain, ytrain] =loaddata;function will load the matrices from files in thedata/folder. The func-tionplotlwlr(Xtrain, ytrain, tau, resolution)will plot the resulting clas-sifier (assuming you have properly ). This function evaluates thelocally weighted logistic regression classifier over a large grid of points and plots theresulting prediction as blue (predictingy= 0) or red (predictingy= 1).

4 Dependingon how fast yourlwlrfunction is, creating the plot might take some time, so werecommend debugging your code withresolution = 50;and later increase it to atleast 200 to get a better idea of the decision :Our implementation :function y = lwlr(X_train, y_train, x, tau)m = size(X_train,1);n = size(X_train,2);CS229 Problem Set #1 Solutions3theta = zeros(n,1);% compute weightsw = exp(-sum((X_train - repmat(x , m, 1)).^2, 2) / (2*tau));% perform Newton s methodg = ones(n,1);while (norm(g) > 1e-6)h = 1 ./ (1 + exp(-X_train * theta));g = X_train * (w.*(y_train - h)) - 1e-4*theta;H = -X_train * diag(w.*h.*(1-h)) * X_train - 1e-4*eye(n);theta = theta - H \ g;end% return predicted yy = double(x *theta > 0);(b) Evaluate the system with a variety of different bandwidth parameters . In particular,try = , , , How does the classification boundary change whenvarying this parameter? Can you predict what the decision boundary of ordinary(unweighted) logistic regression would look like?

5 Answer:These are the resulting decision boundaries, for the different values of .tau = = = = = = 5 For smaller , the classifier appears to overfit the data set, obtaining zero training error,but outputting a sporadic looking decision boundary. As grows, the resulting deci-sion boundary becomes smoother, eventually converging (in the limit as to theunweighted linear regression solution). least squaresSo far in class, we have only considered cases where our target variableyis a scalar that instead of trying to predict a single output, we have a training set withCS229 Problem Set #1 Solutions4multiple outputs for each example:{(x(i), y(i)), i= 1, .. , m}, x(i) Rn, y(i) for each training example,y(i)is vector-valued, withpentries. We wish to use a linearmodel to predict the outputs, as in least squares, by specifying the parameter matrix iny= Tx,where Rn p.

6 (a) The cost function for this case isJ( ) =12mXi=1pXj=1 ( Tx(i))j y(i)j ( ) in matrix-vector notation ( , without using any summations). [Hint:Start with them ndesign matrixX= (x(1))T (x(2))T .. (x(m))T and them ptarget matrixY= (y(1))T (y(2))T .. (y(m))T and then work out how to expressJ( ) in terms of these matrices.]Answer:The objective function can be expressed asJ( ) =12tr (X Y)T(X Y) .To see this, note thatJ( ) =12tr (X Y)T(X Y) =12Xi X Y)T(X Y) ii=12 XiXj(X Y)2ij=12mXi=1pXj=1 ( Tx(i))j y(i)j 2CS229 Problem Set #1 Solutions5(b) Find the closed form solution for which minimizesJ( ). This is the equivalent tothe normal equations for the multivariate :First we take the gradient ofJ( )with respect to . J( ) = 12tr (X Y)T(X Y) = 12tr TXTX TXTY YTX YTT =12 tr( TXTX ) tr( TXTY) tr(YTX ) + tr(YTY) =12 tr( TXTX ) 2tr(YTX ) + tr(YTY) =12 XTX +XTX 2 XTY =XTX XTYS etting this expression to zero we obtain = (XTX) looks very similar to the closed form solution in the univariate case, except nowYis am pmatrix, so then is also a matrix, of sizen p.

7 (c) Suppose instead of considering the multivariate vectorsy(i)all at once, we insteadcompute each variabley(i)jseparately for eachj= 1, .. , p. In this case, we have apindividual linear models, of the formy(i)j= Tjx(i), j= 1, .. , p.(So here, each j Rn). How do the parameters from thesepindependent leastsquares problems compare to the multivariate solution?Answer:This time, we construct a set of vectors~yj= y(1)jy(2) (m)j , j= 1, .. , ourj-th linear model can be solved by the least squares solution j= (XTX) 1XT~ we line up our j, we see that we have the following equation:[ 1 2 p] = (XTX) 1XT~y1(XTX) 1XT~y2 (XTX) 1XT~yp = (XTX) 1XT[~y1~y2 ~yp]= (XTX) 1 XTY= .Thus, ourpindividual least squares problems give the exact same solution as the multi-variate least Problem Set #1 BayesIn this Problem , we look at maximum likelihood parameter estimation using the naiveBayes assumption. Here, the input featuresxj, j= 1.

8 , nto our model are discrete,binary-valued variables, soxj {0,1}. We callx= [x1x2 xn]Tto be the input each training example, our output targets are a single binary-valuey {0,1}. Ourmodel is then parameterized by j|y=0=p(xj= 1|y= 0), j|y=1=p(xj= 1|y= 1), and y=p(y= 1). We model the joint distribution of (x, y) according top(y) = ( y)y(1 y)1 yp(x|y= 0) =nYj=1p(xj|y= 0)=nYj=1( j|y=0)xj(1 j|y=0)1 xjp(x|y= 1) =nYj=1p(xj|y= 1)=nYj=1( j|y=1)xj(1 j|y=1)1 xj(a) Find the joint likelihood function ( ) = logQmi=1p(x(i), y(i); ) in terms of themodel parameters given above. Here, represents the entire set of parameters{ y, j|y=0, j|y=1, j= 1, .. , n}.Answer: ( ) = logmYi=1p(x(i), y(i); )= logmYi=1p(x(i)|y(i); )p(y(i); )= logmYi=1 nYj=1p(x(i)j|y(i); ) p(y(i); )=mXi=1 logp(y(i); ) +nXj=1logp(x(i)j|y(i); ) =mXi=1"y(i)log y+ (1 y(i)) log(1 y)+nXj=1 x(i)jlog j|y(i)+ (1 x(i)j) log(1 j|y(i)) (b) Show that the parameters which maximize the likelihood function are the sameasCS229 Problem Set #1 Solutions7those given in the lecture notes; , that j|y=0=Pmi=11{x(i)j= 1 y(i)= 0}Pmi=11{y(i)= 0} j|y=1=Pmi=11{x(i)j= 1 y(i)= 1}Pmi=11{y(i)= 1} y=Pmi=11{y(i)= 1} :The only terms in ( )which have non-zero gradient with respect to j|y=0are those which include j|y(i).

9 Therefore, j|y=0 ( ) = j|y=0mXi=1 x(i)jlog j|y(i)+ (1 x(i)j) log(1 j|y(i)) = j|y=0mXi=1 x(i)jlog( j|y=0)1{y(i)= 0}+ (1 x(i)j) log(1 j|y=0)1{y(i)= 0} =mXi=1 x(i)j1 j|y=01{y(i)= 0} (1 x(i)j)11 j|y=01{y(i)= 0} .Setting j|y=0 ( ) = 0gives0 =mXi=1 x(i)j1 j|y=01{y(i)= 0} (1 x(i)j)11 j|y=01{y(i)= 0} =mXi=1 x(i)j(1 j|y=0)1{y(i)= 0} (1 x(i)j) j|y=01{y(i)= 0} =mXi=1 (x(i)j j|y=0)1{y(i)= 0} =mXi=1 x(i)j 1{y(i)= 0} j|y=0mXi=11{y(i)= 0}=mXi=1 1{x(i)j= 1 y(i)= 0} j|y=0mXi=11{y(i)= 0}.We then arrive at our desired result j|y=0=Pmi=11{x(i)j= 1 y(i)= 0}Pmi=11{y(i)= 0}The solution for j|y=1proceeds in the identical Problem Set #1 Solutions8To solve for y, y ( ) = ymXi=1 y(i)log y+ (1 y(i)) log(1 y) =mXi=1 y(i)1 y (1 y(i))11 y Then setting y= 0gives us0 =mXi=1 y(i)1 y (1 y(i))11 y =mXi=1 y(i)(1 y) (1 y(i)) y =mXi=1y(i) mXi=1 , y=Pmi=11{y(i)= 1}m.(c) Consider making a prediction on some new data pointxusing the most likely classestimate generated by the naive Bayes algorithm.

10 Show that the hypothesis returnedby naive Bayes is a linear classifier , ifp(y= 0|x) andp(y= 1|x) are the classprobabilities returned by naive Bayes, show that there exists some Rn+1suchthatp(y= 1|x) p(y= 0|x) if and only if T 1x 0.(Assume 0is an intercept term.)Answer:p(y= 1|x) p(y= 0|x) p(y= 1|x)p(y= 0|x) 1 Qnj=1p(xj|y= 1) p(y= 1) Qnj=1p(xj|y= 0) p(y= 0) 1 Qnj=1( j|y=0)xj(1 j|y=0)1 xj y Qnj=1( j|y=1)xj(1 j|y=1)1 xj (1 y) 1 nXj=1 xjlog j|y=1 j|y=0 + (1 xj) log 1 j|y=01 j|y= 0 + log y1 y 0 nXj=1xjlog ( j|y=1)(1 j|y=0)( j|y=0)(1 j|y=1) +nXj=1log 1 j|y=11 j|y=0 + log y1 y 0 T 1x 0,CS229 Problem Set #1 Solutions9where 0=nXj=1log 1 j|y=11 j|y=0 + log y1 y j= log ( j|y=1)(1 j|y=0)( j|y=0)(1 j|y=1) , j= 1, .. , family and the geometric distribution(a) Consider the geometric distribution parameterized by :p(y; ) = (1 )y 1 , y= 1,2,3, ..Show that the geometric distribution is in the exponential family, and giveb(y), ,T(y), anda( ).