Starting from:
$29.99
Gradient-based learning_Assignment 5
Assignment5
5.1 Gradient-basedlearning
X1 X2 X3 Xd ...
Y
Consider the belief network shown above with binary random variable Y ∈ {0,1}and conditional probability table (CPT): P(Y =1|x1,x2,...,xd) = f d X i=1 wixi! = f(w~·~x). Here, we assume that the weights wi ∈ < are real-valued parameters to be estimated from data and that f :<→ [0,1] is a differentiable function that maps its real-valued argument to the unit interval. Consider a data set of i.i.d. examples {(~xt,yt)}T t=1 where ~xt = (x1t,x2t,...,xdt) denotes the observed vector of values from the tth example for the network’s inputs. Also, as shorthand, let pt = P (Y =1|~xt). (a) Show that the gradient of the conditional log-likelihoodL =Pt logP(yt|~xt) is given by: ∂L ∂wi = T X t=1?f0(w~·~xt) pt(1−pt)?(yt −pt)xit, where f0(z) denotes the first derivative of f(z). Intuitively, this result shows that the differences between observed values yt and predictions pt appear as error signals for learning.
(b) Showthatthegeneralresultinpart(a)reducestotheresultinlecturewhen f(z) = [1 + e−z]−1 isthe sigmoid function.
1
5.2 Multinomiallogisticregression
X1 X2 X3 Xd ...
Y Asimplegeneralizationoflogisticregressionistopredictadiscrete(butnon-binary)label y ∈{1,2,...,c} from a real-valued vector ~x ∈ Rd. Here c is the number of classes. For the belief network shown above, consider the following parameterized conditional probability table (CPT):
P(Y =i|~ X=~x) =
ew~i·~x Pc j=1 ew~j·~x
.
The parameters of this CPT are the weight vectors w~i which must be learned for each possible label. The denominator normalizes the distribution so that the elements of the CPT sum to one. Consider a data set of T examples {(~xt,yt)}T t=1, which you can assume to be identically, independently distributed(i.i.d.). Asshorthand,let yit ∈{0,1}denotethe c×T matrixoftargetassignmentswithelements yit = ( 1 if yt = i, 0 otherwise. Also, let pit ∈ [0,1] denote the conditional probability that the model classifies the tth example by the ith possible label:
pit =
ew~i·~xt Pc j=1 ew~j·~xt
.
Theweightvectorscanbeobtainedbymaximumlikelihoodestimationusinggradientascent. Showthatthe gradient of the conditional log-likelihoodL =Pt logP(yt|~xt) is given by: ∂L ∂w~i = X t (yit −pit)~xt. Again, this result shows that the differences between observed values yit and predictions pit appear as error signals for learning.
2
5.3 Convergenceofgradientdescent
One way to gain intuition for gradient descent is to analyze its behavior in simple settings. For a onedimensional function f(x) over the real line, gradient descent takes the form: xn+1 = xn −ηf0(xn).
(a) Considerminimizingthefunction f(x) = α 2(x−x∗)2 bygradientdescent,where α0. (Inthiscase,we know that the minimum occurs at x = x∗; our goal is to analyze the rate of convergence to this minimum.) Derive an expression for the error εn = xn −x∗ at the nth iteration in terms of the initial error ε0 and the step size η0. (b) For what values of the step size η does the update rule converge to the minimum at x∗? What step size leads to the fastest convergence, and how is it related to f00(xn)?
In practice, the gradient descent learning rule is often modified to dampen oscillations at the end of the learning procedure. A common variant of gradient descent involves adding a so-called momentum term: ~xn+1 = ~xn −η∇f + β (~xn −~xn−1), whereβ0. Intuitively,thenamearisesbecausetheoptimizationcontinuesofitsownmomentum(stepping inthesamedirectionasitspreviousupdate)evenwhenthegradientvanishes. Inonedimension,thislearning rule simplifies to: xn+1 = xn −ηf0(xn) + β(xn−xn−1).
(c) Consider minimizing the quadratic function in part (a) by gradient descent with a momentum term. Again, let εn=xn −x∗ denote the error at the nth iteration. Show that the error in this case satisfies the recursion relation: εn+1 = (1−αη + β)εn −βεn−1. (d) Suppose that the second derivative f00(x∗) is given by α = 1, the learning rate by η = 4 9, and the momentum parameter by β = 1 9. Show that one solution to the recursion in part (c) is given by: εn = λnε0,
where ε0 is the initial error and λ is a numerical constant to be determined. (Other solutions are also possible, depending on the way that the momentum term is defined at time t = 0; do not concern yourself with this.) How does this rate of convergence compare to that of gradient descent with the same learning rate (η = 4 9) but no momentum parameter (β = 0)?
3
5.4 Newton’smethod
One way to gain intuition for Newton’s method is to analyze its behavior in simple settings. For a twicedifferentiable function f(x) over the real line, Newton’s method takes the form:
xn+1 = xn −
f0(xn) f00(xn)
.
(a) Consider the polynomial function f(x) = (x−x∗)2p for positive integers p, whose minimum occurs at x=x∗. Supposethat Newton’smethod isusedto minimizethis function, startingfromsome initial estimate x0. Deriveanexpressionfortheerror εn = |xn−x∗|atthe nth iterationintermsoftheinitial error ε0. (b) Forthefunctioninpart(a),howmanyiterationsofNewton’smethodarerequiredtoreducetheinitial error by a constant factor δ <1, such that εn ≤ δε0? Starting from your previous answer, show that n ≥ (2p−1)log(1/δ) iterations are sufficient. (Hint: use the inequality that logz ≤ z−1 for z0.) (c) Consider the function f(x) = x∗log(x∗/x)−x∗ + x, where x∗0. Show that the minimum occurs at x=x∗, and sketch the function in the region|x−x∗| < x∗. (d) Consider minimizing the function in part (c) by Newton’s method. Derive an expression for the relative error ρn = (xn−x∗)/x∗ at the nth iteration in terms of the initial relative error ρ0. Note the rapid convergence (which is typical of Newton’s method). For what range of initial values (for x0) does Newton’s method converge to the correct answer?
4
5.5 Handwrittendigitclassification
In this problem, you will use logistic regression to classify images of handwritten digits. From the course web site, download the files train3.txt, test3.txt, train5.txt, and test5.txt. These files contain data for binary images of handwritten digits. Each image is an 8x8 bitmap represented in the files by one line of text. Some of the examples are shown in the following figure.
(a) Training Perform a logistic regression (using gradient ascent or Newton’s method) on the images in files train3.txt and train5.txt. Indicate clearly the algorithm used, and provide evidence that it has converged (or nearly converged) by plotting or printing out the log-likelihood on several iterations of the algorithm, as well as the percent error rate on the images in these files. Also, print out the 64 elements of your solution for the weight vector as an 8x8 matrix.
(b) Testing Use the model learned in part (a) to label the images in the files test3.txt and test5.txt. Report your percent error rate on these images.
(c) Source code Turn in a print-out of your source code. Once again, you may program in the language of your choice. You should write your own routines for computing the model’s log-likelihood, gradient, and/or Hessian, as well as for updating its weight vector.
5.1 Gradient-basedlearning
X1 X2 X3 Xd ...
Y
Consider the belief network shown above with binary random variable Y ∈ {0,1}and conditional probability table (CPT): P(Y =1|x1,x2,...,xd) = f d X i=1 wixi! = f(w~·~x). Here, we assume that the weights wi ∈ < are real-valued parameters to be estimated from data and that f :<→ [0,1] is a differentiable function that maps its real-valued argument to the unit interval. Consider a data set of i.i.d. examples {(~xt,yt)}T t=1 where ~xt = (x1t,x2t,...,xdt) denotes the observed vector of values from the tth example for the network’s inputs. Also, as shorthand, let pt = P (Y =1|~xt). (a) Show that the gradient of the conditional log-likelihoodL =Pt logP(yt|~xt) is given by: ∂L ∂wi = T X t=1?f0(w~·~xt) pt(1−pt)?(yt −pt)xit, where f0(z) denotes the first derivative of f(z). Intuitively, this result shows that the differences between observed values yt and predictions pt appear as error signals for learning.
(b) Showthatthegeneralresultinpart(a)reducestotheresultinlecturewhen f(z) = [1 + e−z]−1 isthe sigmoid function.
1
5.2 Multinomiallogisticregression
X1 X2 X3 Xd ...
Y Asimplegeneralizationoflogisticregressionistopredictadiscrete(butnon-binary)label y ∈{1,2,...,c} from a real-valued vector ~x ∈ Rd. Here c is the number of classes. For the belief network shown above, consider the following parameterized conditional probability table (CPT):
P(Y =i|~ X=~x) =
ew~i·~x Pc j=1 ew~j·~x
.
The parameters of this CPT are the weight vectors w~i which must be learned for each possible label. The denominator normalizes the distribution so that the elements of the CPT sum to one. Consider a data set of T examples {(~xt,yt)}T t=1, which you can assume to be identically, independently distributed(i.i.d.). Asshorthand,let yit ∈{0,1}denotethe c×T matrixoftargetassignmentswithelements yit = ( 1 if yt = i, 0 otherwise. Also, let pit ∈ [0,1] denote the conditional probability that the model classifies the tth example by the ith possible label:
pit =
ew~i·~xt Pc j=1 ew~j·~xt
.
Theweightvectorscanbeobtainedbymaximumlikelihoodestimationusinggradientascent. Showthatthe gradient of the conditional log-likelihoodL =Pt logP(yt|~xt) is given by: ∂L ∂w~i = X t (yit −pit)~xt. Again, this result shows that the differences between observed values yit and predictions pit appear as error signals for learning.
2
5.3 Convergenceofgradientdescent
One way to gain intuition for gradient descent is to analyze its behavior in simple settings. For a onedimensional function f(x) over the real line, gradient descent takes the form: xn+1 = xn −ηf0(xn).
(a) Considerminimizingthefunction f(x) = α 2(x−x∗)2 bygradientdescent,where α0. (Inthiscase,we know that the minimum occurs at x = x∗; our goal is to analyze the rate of convergence to this minimum.) Derive an expression for the error εn = xn −x∗ at the nth iteration in terms of the initial error ε0 and the step size η0. (b) For what values of the step size η does the update rule converge to the minimum at x∗? What step size leads to the fastest convergence, and how is it related to f00(xn)?
In practice, the gradient descent learning rule is often modified to dampen oscillations at the end of the learning procedure. A common variant of gradient descent involves adding a so-called momentum term: ~xn+1 = ~xn −η∇f + β (~xn −~xn−1), whereβ0. Intuitively,thenamearisesbecausetheoptimizationcontinuesofitsownmomentum(stepping inthesamedirectionasitspreviousupdate)evenwhenthegradientvanishes. Inonedimension,thislearning rule simplifies to: xn+1 = xn −ηf0(xn) + β(xn−xn−1).
(c) Consider minimizing the quadratic function in part (a) by gradient descent with a momentum term. Again, let εn=xn −x∗ denote the error at the nth iteration. Show that the error in this case satisfies the recursion relation: εn+1 = (1−αη + β)εn −βεn−1. (d) Suppose that the second derivative f00(x∗) is given by α = 1, the learning rate by η = 4 9, and the momentum parameter by β = 1 9. Show that one solution to the recursion in part (c) is given by: εn = λnε0,
where ε0 is the initial error and λ is a numerical constant to be determined. (Other solutions are also possible, depending on the way that the momentum term is defined at time t = 0; do not concern yourself with this.) How does this rate of convergence compare to that of gradient descent with the same learning rate (η = 4 9) but no momentum parameter (β = 0)?
3
5.4 Newton’smethod
One way to gain intuition for Newton’s method is to analyze its behavior in simple settings. For a twicedifferentiable function f(x) over the real line, Newton’s method takes the form:
xn+1 = xn −
f0(xn) f00(xn)
.
(a) Consider the polynomial function f(x) = (x−x∗)2p for positive integers p, whose minimum occurs at x=x∗. Supposethat Newton’smethod isusedto minimizethis function, startingfromsome initial estimate x0. Deriveanexpressionfortheerror εn = |xn−x∗|atthe nth iterationintermsoftheinitial error ε0. (b) Forthefunctioninpart(a),howmanyiterationsofNewton’smethodarerequiredtoreducetheinitial error by a constant factor δ <1, such that εn ≤ δε0? Starting from your previous answer, show that n ≥ (2p−1)log(1/δ) iterations are sufficient. (Hint: use the inequality that logz ≤ z−1 for z0.) (c) Consider the function f(x) = x∗log(x∗/x)−x∗ + x, where x∗0. Show that the minimum occurs at x=x∗, and sketch the function in the region|x−x∗| < x∗. (d) Consider minimizing the function in part (c) by Newton’s method. Derive an expression for the relative error ρn = (xn−x∗)/x∗ at the nth iteration in terms of the initial relative error ρ0. Note the rapid convergence (which is typical of Newton’s method). For what range of initial values (for x0) does Newton’s method converge to the correct answer?
4
5.5 Handwrittendigitclassification
In this problem, you will use logistic regression to classify images of handwritten digits. From the course web site, download the files train3.txt, test3.txt, train5.txt, and test5.txt. These files contain data for binary images of handwritten digits. Each image is an 8x8 bitmap represented in the files by one line of text. Some of the examples are shown in the following figure.
(a) Training Perform a logistic regression (using gradient ascent or Newton’s method) on the images in files train3.txt and train5.txt. Indicate clearly the algorithm used, and provide evidence that it has converged (or nearly converged) by plotting or printing out the log-likelihood on several iterations of the algorithm, as well as the percent error rate on the images in these files. Also, print out the 64 elements of your solution for the weight vector as an 8x8 matrix.
(b) Testing Use the model learned in part (a) to label the images in the files test3.txt and test5.txt. Report your percent error rate on these images.
(c) Source code Turn in a print-out of your source code. Once again, you may program in the language of your choice. You should write your own routines for computing the model’s log-likelihood, gradient, and/or Hessian, as well as for updating its weight vector.
1 file (210.6KB)
