Backpropagation

[Google] define: backpropagation algorithm

The backpropagation algorithm is a learning rule for multi-layered Neural Networks, credited to Rumelhart and McClelland. The algorithm gives a prescription for adjusting the initially randomized set of synaptic weights (existing between all pairs of neurons in each successive layer of the network) so as to maximize the difference between the network's output of each input fact and the output with which the given input is known (or desired) to be associated. ...

Potential Applications

A large amount of input/output data is available, but it is unclear how to relate it the inputs to the outputs
The problem has an overwhelming amount of complexity, but there exists a clear solution
It is easy to create a number of examples of correct behavior, ie the Learning Data.
Outputs can be non-numeric, or "fuzzy"

Some Applications

Counting parity
Symmetry
Relations: the family-tree network (Hinton)
Rotation and translation invariance
Context-dependent categorization: NETtalk
Auto-association
Facial Recognition
Character recognition
ALVIN

Algorithm from the Mitchell book p98, Table 4.2

Begins by constructing a network with the desired number of hidden and output units and initializing all network weights to small random values
The main loop of the algorithm then repeatedly iterates over the training examples.
For each training examples, it applies the network to the example, calcuates the error of the network output, computes the gradient with respect to the error, the updates all weights in the network
Repeated until the network performs acceptably well

Simple example w/ Perceptrons [OR, AND, XOR]

Can we construct the AND or XOR? We already did the OR in last class

x1	x2	t
-1	-1	-1
-1	1	1
1	-1	1
1	1	1

AND

x1	x2	t
-1	-1	-1
-1	1	-1
1	-1	-1
1	1	1

XOR

x1	x2	t
-1	-1	-1
-1	1	1
1	-1	1
1	1	-1

Backpropagation Applet #1

The network state is shown on the center-left of the applet.
The input and the output signals of neurons and the weights of the connections are indicated on the network figure.
The relation between the input feature space and the network output is shown on the center-right of the applet.
The vertical and the horizontal axes are according to the input value to each input neuron. The color of the feature space means the output value of the network.

Backpropagation Applet #2

Backpropagation Applet

Additional Links

Points to Consider

If you can write a flow chart or a formula that accuratley describes the problem, then stick with a traditional programming method. (ie. human digestable, like decision trees)
Does a piece of hardware or software already exist that does what you want? If so building a NN could be a big waste of time
Do you want the functionality to "evolve" in a direction that is not pre-defined? If so, then consider using a Genetic Algorithm (that's another topic!).
Do you have an easy way to generate a significant number of input/output examples of the desired behavior? If not, then you won't be able to train your NN to do anything.
Is the problem is very "discrete"? Can the correct answer can be found in a look-up table of reasonable size? A look-up table is much simpler and more accurate.
Are precise numeric output values required? NN's are not good at giving precise numeric answers.

Summary points from Mitchell Book

The Backpropagation algorithm is the most common network learning method.
Backpropagation searches the space of possible hypotheses using gradient descent to iteratively reduce the error in the nuetwork fit to the training examples.
Intriguing property: ability to invent new features that are not explicit in the input to the network.