On-Line Learning with a Perceptron

We study on--line learning of a linearly separable rule with a simple perceptron. Training utilizes a sequence of uncorrelated, randomly drawn N--dimensional input examples. In the thermodynamic limit the generalization error after training with P such examples can be calculated exactly. For the standard perceptron algorithm it decreases like (N=P ) 1=3 for large P=N , in contrast to the faster (N=P ) 1=2 --behavior of the so--called Hebbian learning. Furthermore, we show that a specific parameter--free on--line scheme, the AdaTron algorithm, gives an asymptotic (N=P )--decay of the generalization error. This coincides (up to a constant factor) with the bound for any training process based on random examples, including off-- line learning. Simulations confirm our results. PACS. 87.10, 02.50, 05.90 A very important feature of Feedforward Neural Networks is their ability to learn a rule from examples 1, 2. Methods known from Statistical Mechanics have been successfully used to s...