CS4540/CS8803: (Is there) A(n Algorithmic) Theory of (Artificial) Intelligence(?)
Fall 2023. MW: 9:30-10:45, Mason 5134
Santosh Vempala, Klaus 2222, Office hour: Mon 1:30-3pm (or by appt)
TAs: Xinyuan Cao OH: Tue 2-4pm, Klaus 3100. Mirabel Reid OH: Wed 12-2pm, Klaus 2100
What is the basis of intelligence? How can neural networks, artificial or natural, provably lead to perception, learning and cognition? We'll begin by studying a few classics, highlight the gaps and challenges posed by modern artificial models and the brain, and then discuss more recent rigorous proposals. Note that this is a mathematically rigorous course and the focus is on what is provably true related to this topic. Students interested in the latest developments in empirical AI should take other courses.
Prerequisites: algorithms, linear algebra.
HW (40%): 4-6 Problem sets.
Exams (40%): Two in-class exams. No final. No exams for 8803 students.
Project (20%): Each team can choose one of the following options: (a) read a paper and provide an insightful explanation/simpler proof/ generalization (b) prove a conjecture (c) formulate a precise conjecture supported by experimental or theoretical evidence. A list of candidate projects will be provided.
Candidate Project topics are available here.
- The McCulloch-Pitts Neuron
- PAC Learning
- Winnow and Weighted Majority
- VC dimension
- Support Vector Machines
- Random Projection for Learning
- Random Graphs
- The Regularity Lemma
- Dynamics and Equilibria: the Brouwer-Kakutani Fixed Point Theorems
- Cell Assemblies: Hebb, D. O. (2005). The organization of behavior: A neuropsychological theory. Psychology press.
- The Assembly Hypothesis
- Generalization in Deep Learning
- Recurrent Neural Networks
Aug 21, 23. Course overview. The Perceptron Algorithm Notes.
Aug 28, 30. Weighted Majority and Winnow Notes.
Sep 6, 11, 13. PAC learning, Sample Complexity, VC dimension Notes.
Sep 18, 20. Support Vector Machines Notes. Random Projection for Learning Notes.
Sep 25, 27. Boosting, Concentration Inequalities Notes. Random Graphs.
Oct 2. The Regularity Lemma.
Oct 4. Midterm I.
Oct 11. Learning and Games.
Oct 16, 18. Fixed Point Iterations.
Oct 23, 25. Assemblies of Neurons.
Oct 30, Nov 1. Generalization in Neural Networks.
Nov 6, 8. Convolution and Recurrence in Neural Networks.
Nov 13, 15.
Nov 27. Midterm II.
Nov 29. Language.
Dec 4. Language models and Next-word Prediction.