Directed Drift: A New Linear Threshold Algorithm for Learning Binary Weights On-Line

By Santosh S. Venkatesh. 1993

Abstract 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-Pitts 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, non-binary solution weight vector).

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Born to Learn: the Inspiration, Progress, and Future of Evolved Plastic Artificial Neural Networks (2017, methodology): “r (1991) used the same approach of Chalmers (1990) but constrained the weights to binary values. Also in this case, evolution autonomously rediscovered a handdesigned rule, the directed drift rule by Venkatesh (1993). They also observed that the performance on new tasks was 8 variable genotype lengt”