UVic Dynamics and Probability Seminar: Will Perkins

The Perceptron model was proposed as early as the 1950's as a toy model of a one-layer neural network. The basic model consists of a set of solutions (either the Hamming cube or the sphere of dimension n) and a set of constraints given by independent n-dimensional Gaussian vectors. The constraints are that the inner product of a solution vector with each constraint vector scaled by sqrt{n} must lie in some interval on the real line. Probabilistic questions about the model include the satisfiability threshold (or the "storage capacity") and questions about the typical structure of the solution space. Algorithmic questions include the tractability of finding a solution (the learning problem in the neural network interpretation). I will describe the model, the main problems, and recent progress.