We need a rule that converges towards the unknown, target function even if the examples are not linearly separable.

The key idea is to use gradient descent to search the space of weight vectors to find weights that best fit the training examples. The learning task is relaxed to that of training an unthresholded Perceptron:

The objective is to minimize the following error: E( w ) = ( ½ ) S _e ( y_e – o_e )²

The training is a process of minimizing the error E( w ) in the direction of the steepest most rapid decrease, that is in direction opposite to the gradient:

Ñ E( w ) = [ ¶E/¶w₀, ¶E/¶w₁, …, ¶E/¶w_d ]

which leads to the Gradient descent training rule:

w_i = w_i - h ¶E/¶w_i

The weight update can be derived as follows:

¶ E/¶w_i = ¶ ( ( ½ )S _e( y_e–o_e )²)/¶w_i

where x_ie denotes the i-th component of the example

The Gradient descent training rule becomes:

w_i = w_i + h S_e ( y_e–o_e ) x_ie

In order to avoid overstepping of the error surface the value of the learning rate h may be gradually reduced as the number of gradient steps grows.

Gradient Descent Learning Algorithm

Initialization: Examples {( x_e, y_e)}_e=1^N, initial weights w_i set to small random values, learning rate parameter h = 0.1

Repeat

until termination condition is satisfied.

Example: Suppose an example of Perceptron which accepts two inputs x₁ and x₂, with weights w₁ = 0.5 and w₂ = 0.3 and w₀ = -1.

Let the following example is given: x₁ = 2, x₂ = 1, y = 0
The output of the Perceptron is :

O = 2 * 0.5 + 1 * 0.3 - 1 = 0.3

The weight updates according to the gradient descent algorithm will be:

Dw₁ = ( 0 - 0.3 ) * 2 = - 0.6

Dw₂ = ( 0 - 0.3 ) * 1 = - 0.3

Dw₀ = ( 0 - 0.3 ) * 1 = - 0.3

Let another example is given: x₁ = 1, x₂ = 2, y = 1

The output of the Perceptron is :

O = 1 * 0.5 + 2 * 0.3 - 1 = 0.1

The weight updates according to the gradient descent algorithm will be:

Dw₁ = - 0.6 + ( 1 - 0.1 ) * 1 = 0.3

Dw₂ = - 0.3 + ( 1 - 0.1 ) * 2 = 1.5

Dw₀ = - 0.3 + ( 1 - 0.1 ) * 1= 0.6

If there are no more examples in the batch, the weights will be modified as follows:

w₁ = 0.5 + 0.3 = 0.8

w₂ = 0.3 + 1.5 = 1.8

w₀ = - 1 + 0.6 = 1.6

Suggested Readings:

Bishop,C. (1995) "Neural Networks for Pattern Recognition",
Oxford University Press, Oxford, UK, pp.98-105.

Haykin, Simon. (1999). "Neural Networks. A Comprehensive Foundation",
Second Edition, Prentice-Hall, Inc., New Jersey, 1999.