Theory of Computation II
summary
Perceptron learning gets a provable mistake bound of one over margin squared and becomes practical via the kernel trick that maps nonlinearly separable data into higher dimensions (basis of SVMs, later eclipsed by deep nets). PAC sample complexity scales with 1/epsilon, log|H| or the VC dimension. Evolutionary dynamics reduce to a multiplicative weights update with a fitness-plus-entropy Lyapunov function. Spiking-record experiments show sparse assemblies (Eiffel/Obama cells); a G(n,p) + Hebbian plasticity model proves stable assemblies and overlap after coactivation.
AI-written summary · about
chapters (9)
- 0:00Intro
- 2:15Perceptron Algorithm
- 12:10Learning Theory
- 15:55Learning Theorem
- 18:25Computational Science
- 20:10Statistical Physics
- 22:20Simulation by Computers
- 30:23Life Science
- 47:58Hardware
related talks
01h 04mStatistical Physics and Computation in High Dimension
01h 17mGeneralization I
01h 03mStatistical Physics and Computation in High Dimension
51mThe Brain as an Efficient, Robust Adaptive Learner
54mA Curious Case Of Symmetric Binary Perceptron Model: Algorithms And Barriers
12mTheoretical understanding of learning through the computational lens
58mStrong Generalization from Small Brains and No Training Data
01h 08mTutorial: Methods from Statistical Physics III