Directed drift: A new linear threshold algorithm for learning binary weights on-line (Q2366277)

Learning real weights for a McCulloch-Pitts neuron is equivalent to linear programming and can hence be done in polynomial time. Efficient local learning algorithms such as Perceptron Learning further guarantee convergence in finite time. The problem becomes considerably harder, however, when it is sought to learn binary weights; this is equivalent to integer programming which is known to be NP-complete. A family of probabilistic algorithms which learn binary weights for a McCulloch-Pits neuron with inputs constrained to be binary is proposed here, the target functions being majority functions of a set literals. These algorithms have low computational demands and are essentially local in character. Rapid (average-case) quadratic rates of convergence for the algorithm are predicted analytically and confirmed through computer simulations when the number of examples is within capacity. It is also shown that, for the functions under consideration, Preceptron Learning converges rapidly (but to an, in general, nonbinary solution weight vector).