Lecture
Complete Statistical Theory of Learning (Vladimir Vapnik) | MIT Deep Learning Series
- Core Thesis: Vladimir Vapnik argues that statistical learning theory is "complete" because there are only two fundamental modes of generalization:
- Data-driven brute force: Relying on large datasets and the law of large numbers (empirical risk minimization).
- Intelligence-driven principles: Incorporating specific knowledge (invariants) to guide the learning process, reducing dependence on data volume.
- Historical Context: The original Statistical Learning Theory (founded ~50 years ago with Chervanenko) established that generalization is possible if and only if the VC dimension (capacity) of the function set is finite.
- Critique of Current Paradigms:
- Existing methods primarily rely on minimizing empirical error, which assumes the "brute force" principle is the only viable path.
- Classical approaches often replace indicator functions with differentiable loss functions (e.g., least squares), which alters the convergence rate and optimization landscape without solving the underlying ill-posed nature of the problem.
- The New Framework (Complete Learning Theory):
- Dual Convergence: Requires balancing strong convergence (function values close to target) and weak convergence (invariance properties hold across the function set).
- Admissible Sets: Instead of minimizing error over a broad function space, the learner must select a subset of functions (admissible set) that satisfy specific invariants.
- Optimization Formulation: Solves a conditional optimization problem: minimize a loss functional (improved over standard least squares) subject to constraints defined by statistical invariants.
- Mathematical Implementation:
- Reproducing Kernel Hilbert Space (RKHS): Provides a closed-form solution via the Representer Theorem, where the optimal function is a linear expansion of kernel functions.
- Invariant Construction: Invariants are derived from inner products of the solution with specific predicate functions ($\phi$).
- Computational Form: The solution involves solving linear systems with matrices constructed from kernel evaluations ($K$) and predicate evaluations ($\Phi$).
- Empirical Results:
- Diabetes Dataset: Introducing a single smart invariant (identifying a specific contradictory area) reduced the error rate from 73% to 7%.
- Neural Networks: Applying one simple invariant (cosine coefficient) to backpropagation improved digit recognition error from 3.1% to 2.9%.
- Fourier Coefficients: Using 16 Fourier coefficients as predicates yielded a 0.6% improvement in performance.
- Definition of Intelligence:
- Intelligence is defined not as imitation (Turing Test) but as the ability to discover and apply smart predicates (abstract ideas) that constrain the solution space.
- Predicates vs. Invariants: Predicates are abstract concepts (e.g., symmetry, translation), while invariants are the specific mathematical constraints derived from these concepts applied to training data.
- Examples of Smart Predicates:
- Symmetry: Horizontal, vertical, and diagonal symmetries in image data.
- Tangent Distance: Minimizing distance between class instances via Lie derivatives (e.g., translation, rotation, scaling).
- Structural Similarities: Drawing parallels to Vladimir Propp's "Morphology of Folktale," which identified only 31 structural predicates to describe all Russian folktales.
- Overfitting Dynamics:
- Increasing the number of predicates reduces the size of the admissible function set, thereby decreasing the risk of overfitting, contrary to the behavior of adding features.
- The theoretical limit suggests an infinite number of predicates converges to a single, unique optimal function.
- Open Challenges & Future Directions:
- Data Efficiency Challenge: The speaker challenges researchers to achieve 0.5% error on MNIST using only 1% of the data (600 samples) by discovering the correct set of predicates.
- Language Processing: While predicates are effective for structured data like images (due to known symmetries), identifying analogous predicates for natural language remains an unsolved, harder problem.
- Philosophical Underpinning: The theory aligns with the Platonic/Hegelian view that a finite set of abstract "ideas" (predicates) underlies the complexity of the physical world, echoing Wigner's "unreasonable effectiveness of mathematics."