Vapnik's Case for Learning by Predicates, Not Just by More Data

Vapnik opens with the history. About fifty years ago, he and Professor Chervonenkis began statistical learning theory to answer when doing well on a small training set guarantees doing well on test data. Theory showed that the law of large numbers is not enough and that uniform convergence is needed, and the bounds say that lower training error means lower test error.

As a result, he says, people concluded that the only way forward was to minimize errors on training data, and algorithms were built on that principle. About five years earlier he found another principle that he considers more interesting. The first is brute force, where more data gives better answers, while the second is an intelligent principle.

He argues there is no short way to generalize and that both mechanisms must be used together, which is why he calls the result a complete statistical theory of learning. It points learning toward intelligence and understanding, rather than the imitation Turing described.

Vapnik frames learning as minimizing a functional over a given set of functions with unknown probability and iid data. The answer is simple: you can minimize it from data if and only if the VC dimension of the set is finite. He prefers to call capacity the diversity of the set of functions.

VC dimension is defined as the largest number of vectors that can be shattered in all possible ways by indicator functions from the set. A key theorem bounds the risk, with probability 1 minus eta, for all functions in the set, so minimizing empirical loss minimizes the right-hand side. For linear indicator functions, the dimension is bounded by the radius and weight norm, so it can be smaller than the dimension of the space and can be controlled.

Even if a set has infinite VC dimension, you can build a nested structure of subsets with growing VC dimension, choose a subset and then minimize empirical loss within it. VC theory does not tell you how to choose the loss, the admissible set of functions, the structure on that set or how to minimize. The rest of the talk addresses those gaps.

Vapnik describes pattern recognition as nature, which draws x and then "plays dice" with a conditional probability to produce y. With indicator loss, you want the smallest expected number of errors, but that loss is zero almost everywhere, so gradients are unusable. People instead replace it with squared error, whose minimizer is the conditional probability of class one given x, and thresholding at 0.5 gives the optimal rule.

Expanding the square, he shows the loss splits into an irrelevant term plus a sum of two integrals. The goal is to minimize only the first, distance to the conditional probability, but least squares minimizes the sum. The second integral eventually goes to zero but slows the rate of convergence.

His alternative writes the conditional probability as the solution of an integral equation, which is ill-posed, and replaces the unknown measure with the empirical one, as Kolmogorov justified for distribution functions. The classical Nadaraya-Watson estimator, he notes, solves a corrupted version of that equation. Solving the equation by least squares yields a weighted form with a matrix he calls the V-matrix, which replaces the identity matrix of ordinary least squares and is easy to estimate.

Vapnik says that when engineers design a neural network architecture, they are implicitly choosing an admissible set of functions. In Hilbert space there are strong convergence of functions and weak convergence, defined by inner products with every function phi. Strong implies weak by Cauchy-Schwarz, and on a compact set weak implies strong.

Everyone uses strong convergence, so he asks what weak convergence offers. Requiring equality for all phi is unrealistic, so he picks m functions, called predicates, and defines the admissible set as the functions that satisfy those m equalities, estimated on training data. These are the statistical invariants.

He illustrates with the duck test: if it looks, swims and quacks like a duck, it is a duck. Predicates define what "looks," "swims" and "quacks" mean, and the admissible functions are those that classify accordingly. Unlike features, more predicates reduce VC dimension, because they restrict the set, while more features increase it.

The complete problem is then to minimize the V-matrix functional subject to the invariant constraints. In practice you can relax this into an unconditional problem, summing the functional with a weighted squared violation of the constraints, which depends on the covariance matrix of the predicates and is easy to compute.

Vapnik moves to reproducing kernel Hilbert spaces, defined by a Mercer kernel with an expansion in orthonormal functions. The representer theorem says that if the function's norm is bounded, the minimizer is a linear expansion over kernels at the training points. Bounding the norm controls the VC dimension, so the constant C acts as the capacity knob.

For this space, both the exact conditional problem and its approximate unconditional version have closed-form solutions obtained by solving a linear system. Vapnik notes that minimizing a data-fit term under a bounded norm gives exactly the support vector machine.

With invariants added, the coefficients are defined through the predicate matrix. Here the parameters are determined by invariants and not only by data, and the data is needed only for the kernel expansion. Because weak convergence holds for any function in the space, one or a few smart predicates might be enough, which he calls intelligent learning rather than brute force.

He also notes the representer theorem implies the optimal solution is a one-layer expansion, and suggests it may not be best to use deep networks, a point he says they will return to.

Vapnik shows illustrations comparing least squares, the V-matrix method, invariants, and both combined, on small synthetic problems with 48, 98 and 192 points and on multidimensional data. The combination does better each time. In one diabetes example, a baseline with some invariants gave a 22.73 error rate, and he asked whether a better invariant could be found.

The team looked for a region where the existing invariants were violated and added a predicate that is one inside that region and zero outside. That improved performance, which he takes as evidence that smart invariants help. The process mirrors scientific discovery: find a situation where the approximation contradicts the invariants, then revise the solution to remove the contradiction.

He stresses that, as in physics, the difficult part is finding the contradictory situation. Physicists look for where theory disagrees with experiment and then rebuild the theory, and Vapnik says the same principle applies to choosing invariants.

Although Vapnik says he is not fond of neural networks, he shows the theory applies to them. Instead of minimizing least squares, you minimize the approximation combining the V-matrix and the predicate matrix. Backpropagation then needs only one correction: the error vector at the last layer is multiplied by the matrix before the usual updates proceed.

He asked people with a good deep network to try it. They used a single trivial invariant, the constant function, set V to the identity, trained on 1,000 MNIST examples, 100 per class, with batch size six. Error moved from 3.1 to 2.9.

Adding one predicate based on a cosine coefficient of the digit image improved results further, and he mentions using 16 Fourier coefficients and says one could use hundreds or thousands of invariants. He notes this is only an approximation of the exact solution, and still it works.

Vapnik calls the theory complete because Hilbert space has only two kinds of convergence, so you can play one game or both together. To improve learning beyond that, you must ask how to choose invariants. Among many silly predicates, such as "plays chess like a duck," there are smart ones, and picking them is the subject of intelligent learning.

Simple predicates already carry meaning. The constant function forces the expected number of class-one examples to match training data, the identity forces the center of mass to match, and x times x transpose enforces matching covariance. For images, Fourier coefficients and convolutions are predicates too, and he says understanding image recognition means understanding which predicates are involved.

He distinguishes predicate, an abstract concept, from invariant, its instantiation on training data. Using Simard et al.'s picture of digit clones, he shows transformations such as translation and rotation generated by Lie derivatives, and suggests requiring invariance with respect to them. Closely related is tangent distance, the closeness of two digits after allowing small linear transformations.

Tangent distance leads to a measure of symmetry. Compare an image with a flipped version of itself and see how close they are after alignment, giving coefficients for horizontal symmetry, vertical symmetry or antisymmetry. He calls this just one predicate among many one could invent.

Summing up, Vapnik says one can minimize a slightly improved functional subject to a serious constraint: an admissible set built from smart predicates, which can be carved out of, say, all continuous functions. This gives a unique solution in reproducing kernel Hilbert space and an approximate one for neural networks. Further progress, he says, goes beyond statistics toward predicates that form a basis for understanding.

He ties this to a line of philosophy from Plato's world of ideas, to Hegel's claim that what is reasonable exists, to Wigner's unreasonable effectiveness of mathematics. Predicates are abstract ideas, and invariants are the elements of the solution built from them. He thinks these concepts reflect the essence of intelligence and not its imitation.

He poses a challenge: deep networks reach 0.5% error on MNIST with 60,000 examples, so use 1% of the data and get the same result. His last example is Vladimir Propp's 1928 *Morphology of Folk Tale*, which described 31 predicates for synthesizing Russian folk tales. He believes a small number of predicates may likewise describe 2D images.

In Q&A, asked about overfitting, he says more predicates reduce the set of functions, so overfitting decreases, and with infinitely many predicates only one function is left. On language predicates he says natural language is very complicated and he does not know, agrees it is harder than images, and advises tackling simple problems step by step.