DYNAMICS OF LEARNING FOR THE BINARY PERCEPTRON PROBLEM

A polynomial learning algorithm for a perceptron with binary bonds and random patterns is investigated within dynamic mean field theory. A discontinuous freezing transition is found at a temperature where the entropy is still positive. Critical slowing down is observed approaching this temperature from above. The fraction of errors resulting from this learning procedure is finite in the thermodynamic limit for all temperatures and all finite values of the number of patterns per bond. Monte-Carlo simulations on larger samples (N greater-than-or-equal-to 127) are in quantitative agreement. Simulations on smaller samples indicate a finite bound for the existence of perfect solutions in agreement with the replica theory and the zero entropy criterion. This suggests that perfect solutions exist also in larger samples but cannot be found with a polynomial procedure as expected for a combinatorial hard problem.