gradient can be obtained by differentiating E from Equation (42), as in Software

Maker QR-Code in Software gradient can be obtained by differentiating E from Equation (42), as

where xid denotes the single input component xi for training example d We now have an equation that gives in terms of the linear unit inputs xid, outputs Od, and target values td associated with the training examples Substituting Equation (46) into Equation (45) yields the weight update rule for gradient descent

To summarize, the gradient descent algorithm for training linear units is as follows: Pick an initial random weight vector Apply the linear unit to all training examples, then compute Awi for each weight according to Equation (47) Update each weight wi by adding Awi, then repeat this process This algorithm is given in Table 41 Because the error surface contains only a single global minimum, this algorithm will converge to a weight vector with minimum error, regardless of whether the training examples are linearly separable, given a sufficiently small learning rate q is used If r) is too large, the gradient descent search runs the risk of overstepping the minimum in the error surface rather than settling into it For this reason, one common modification to the algorithm is to gradually reduce the value of r) as the number of gradient descent steps grows

Gradient descent is an important general paradigm for learning It is a strategy for searching through a large or infinite hypothesis space that can be applied whenever (1) the hypothesis space contains continuously parameterized hypotheses (eg, the weights in a linear unit), and (2) the error can be differentiated with respect to these hypothesis parameters The key practical difficulties in applying gradient descent are (1) converging to a local minimum can sometimes be quite slow (ie, it can require many thousands of gradient descent steps), and (2) if there are multiple local minima in the error surface, then there is no guarantee that the procedure will find the global minimum

~ ~ A D I E N T - D E s c E N )T ( ~ ~ ~ ~ ~ ~ ~ ~ ~ x ~ ~ ~ ~ ~ s , q Each training example is a pair of the form (2,t ) , where x' is the vector of input values, and

t is the target output value q is the learning rate (eg, 05)

Initialize each w, to some small random value Until the termination condition is met, Do 0 Initialize each Awi to zero 0 For each (2,t ) in trainingaxamples, Do w Input the instance x' to the unit and compute the output o For each linear unit weight w , , Do

GRADIENT DESCENT algorithm for training a linear unit To implement the stochastic approximation to gradient descent, Equation (T42) is deleted, and Equation (T41) replaced by wi c wi +q(t - o b i

One common variation on gradient descent intended to alleviate these difficulties is called incremental gradient descent, or alternatively stochastic gradient descent Whereas the gradient descent training rule presented in Equation (47) computes weight updates after summing over a22 the training examples in D, the idea behind stochastic gradient descent is to approximate this gradient descent search by updating weights incrementally, following the calculation of the error for each individual example The modified training rule is like the training rule given by Equation (47) except that as we iterate through each training example we update the weight according to

where t, o, and xi are the target value, unit output, and ith input for the training example in question To modify the gradient descent algorithm of Table 41 to implement this stochastic approximation, Equation (T42) is simply deleted and Equation (T41)replaced by wi t wi +v (t -o) xi One way to view this stochastic defined gradient descent is to consider a distinct error function ~ ~ ( 6 ) for each individual training example d as follows 1 (411) E (6)= - (td - 0 d )2 d 2 where t, and od are the target value and the unit output value for training example d Stochastic gradient descent iterates over the training examples d in D, at each iteration altering the weights according to the gradient with respect to E() d ; The sequence of these weight updates, when iterated over all training examples, provides a reasonable approximation to descending the gradient with respect to our original error function E(G) By making the value of 7 (the gradient