Comparison of perceptron training by linear programming and by the perceptron convergence procedure

The performance of the perceptron convergence procedure is compared with that of using a linear programming algorithm to train perceptrons. It is shown that the ellipsoid method for linear programming can be implemented in a version of the perceptron to be trained. This gives a perceptron training method for which the number of training cycles required is bounded by a polynomial in the number of input units. In contrast, the number of training cycles needed by the perceptron convergence procedure can increase exponentially in the number of input units. In an empirical comparison on randomly generated training sets, the method based on linear programming required significantly fewer training cycles in the majority of the cases tested. >