Learning algorithms for restricted neural networks.

Abstract

The problem of supervised learning can be phrased in terms of finding a good approximation to some unknown target function f, based on observing f's values on some examples drawn randomly according to some underlying distribution. Unfortunately, finding an algorithm that efficiently learns simple classes of neural networks under any distribution has proven to be very hard. In this thesis, we propose learning algorithms that provably and efficiently learn simple classes of neural networks under simple distributions within the rigorous framework of computational learning theory. We therefore propose some restrictions on both the neural network class and the underlying distribution that generates the examples because, otherwise, the learning problem becomes intractable. In the first part of the thesis, we present an algorithm that provably learns the class of stochastic perceptrons with arbitrary monotonic activation function and binary weights when the probability distribution that generates the input examples is member of a class that we call k-blocking distributions . The problem studied in the second part of the thesis is much more involved. Whereas in the first part, the target function consists only of a single perceptron, in the second part, it consist of a nonoverlapping network of perceptrons. We provide an algorithm that provably finds both the binary-valued weights and the network connectivity of the target function when the distribution is such that each variable is statistically independent of all the others.