Complete Statistical Theory of Learning: From Brute Force to Intelligent Principles with Vladimir Vapnik

Vladimir Vapnik, co-inventor of Support Vector Machines and VC theory, introduces a "complete statistical learning theory" that extends beyond the traditional "brute force principle" of relying solely on more data for better generalization. He traces the origins of statistical learning theory, which sought to answer when models trained on limited data could perform well on unseen test data. The conventional approach, focused on minimizing empirical error, is deemed insufficient, necessitating concepts like the uniform law of large numbers and the crucial VC-dimension, which measures the capacity or diversity of a function set. Vapnik emphasizes that the ability to minimize a functional depends entirely on the finiteness of this VC-dimension, and he outlines methods for structuring function sets to manage this capacity.

The lecture highlights critical limitations of the existing VC theory, particularly its failure to provide guidance on selecting optimal loss functions, admissible function sets, or constructing effective structures for learning. Vapnik explains how common practices, such as replacing non-differentiable indicator loss functions with squared error, can inadvertently slow down convergence by optimizing for a composite objective rather than the true conditional probability. He then introduces a new constructive setting that replaces unknown probability measures with empirical ones, leading to a refined functional involving a "V-matrix" that offers an improved approach over the standard least squares method for estimating conditional probabilities.

The core of Vapnik's "intelligent principle" lies in the concept of "predicates" or statistical invariants. Unlike features, which increase the diversity and thus the VC-dimension of a function set, predicates *decrease* the VC-dimension by imposing constraints that define a more specific, admissible set of functions. This approach is likened to the "duck test logic," where functions are selected based on whether they satisfy certain desired properties. The complete learning problem is framed as a conditional optimization task: minimizing the V-matrix functional subject to these predicate-based constraints, which can be solved exactly or approximately through unconditional optimization with penalty terms.

In the context of Reproducing Kernel Hilbert Spaces (RKHS), Vapnik demonstrates that this complete problem has closed-form solutions, leveraging the Representer Theorem. Crucially, the parameters of the optimal solution are shown to be defined by these invariants (predicates), rather than being solely data-driven. This paradigm shift suggests that incorporating "smart predicates"—domain knowledge or desired properties—can significantly reduce the amount of data required for effective learning, moving towards a more intelligent and efficient learning process. Vapnik illustrates this potential with examples, including a substantial improvement in diabetes error rates by identifying and applying specific invariants, underscoring the power of embedding intelligence into the learning framework, akin to how physicists approach problem-solving by seeking fundamental invariants.

The problem was to answer the question when if we will do well with training data if you will have small amount of our own training data, you will do well also on the test data.

About five years ago I found that there exists another principle, even more interesting than this one, because in this principle it is brute force principle, give me more data, you give better answer with. So the second principle is intelligent principle and I will talk today about this.

Everything depend on which set of function you have to minimize this functional, and you can not avoid that. So we call it capacity, but maybe better called, diversity of the set of function, but measure of this capacity, diversity, is VC-dimension.

But VC theory does not answer four very important questions. How to choose loss function L y f? How to select admissible set of function f of x? How to construct good set of function? How to construct structure on admissible set of function?

In statistics, we're given data and would like to know function, and it doesn't matter how many data. We will see, it is not equivalent to function.

If it looks like a duck, swims like a duck, and quack like a duck, then it probably is a duck.

With increasing number of predicates, the VC-dimension of admissible set of function is decreased. Why does it decrease? Because we have set of function, then we from this set of function, select function which satisfy new predicate.

But parameters is defined by invariants, but you could use these invariants, and what it means if you will write in the form, that you have K which is matrix, depending on your training data, phi is predicate matrix, so you have vector over here, and this is Y vector, F is vector, so you have element, you have different formulation of learning problem in term of this vector and these values.

That means that if you have smart way to looking for invariants, then you can have a chance to improve your performance, but this is exactly the same philosophy which use physicist.