|
NeuroCOLT
Technical Report NC-TR-97-009
Multilayer
Perceptrons and Learning
Alberto
Bertoni, Paola Campadelli, Nicolò Cesa-Bianchi
Università degli Studi di Milan
Italy
Abstract
In this paper we present a survey on some interesting contributions
offered by theoretical computer science to the area of supervised
learning. In the first part, we discuss the computing capabilities
of multilayer preceptrons with binary inputs and outputs and we describe
design techniques for some classes of simple boolean functions. Finally,
we show the application of communication complexity to obtain separations
between complexity classes related to multilayer preceptrons.
In the second part, we look at the learnability of these computing
models within the PAC learning framework and some of its variants.
The hardness of polynomial time prediction for the class of multilayer
perceptrons is shown under cryptographical assumptions. We conclude
by presenting a recently developed technique for boosting the accuracy
of PAC learning algorithms.
Download Compressed Postscript
|