ON THE PERCEPTRON LEARNING ALGORITHM ON DATA WITH HIGH-PRECISION

We investigate the convergence rate of the perceptron algorithm when t he patterns are given with high precision. In particular, using the re sult of A. Dembo (Quart. Appl. Math. 47 (1989), 185-195), we show that when the n pattern vectors are independent and uniformly distributed over {+1, -1}nlogn, as n --> infinity, with high probability, the patt erns can be classified into all 2n possible ways using perceptron algo rithm with O(n log n) iteration. Further, the storage of parameters re quires only O(nlog2n) bits. We also indicate some interesting mathemat ical connections with the theory of random matrices. (C) 1994 Academic Press, Inc.