On the perceptron learning algorithm on data with high precision

摘要

We investigate the convergence rate of the perceptron algorithm when the patterns are given with high precision. In particular, using the result 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 → ∞, with high probability, the patterns can be classified into all 2n possible ways using perceptron algorithm with O(n log n) iteration. Further, the storage of parameters requires only O(n log2 n) bits. We also indicate some interesting mathematical connections with the theory of random matrices.