Lecture by Vladimir Vapnik in January 2020, part of the MIT Deep Learning Lecture Series.
Slides: http://bit.ly/2ORVofC
Associated podcast conversation: https://www.youtube.com/watch?v=bQa7hpUpMzM
Series website: https://deeplearning.mit.edu
Playlist: http://bit.ly/deep-learning-playlist

OUTLINE:
0:00 - Introduction
0:46 - Overview: Complete Statistical Theory of Learning
3:47 - Part 1: VC Theory of Generalization
11:04 - Part 2: Target Functional for Minimization
27:13 - Part 3: Selection of Admissible Set of Functions
37:26 - Part 4: Complete Solution in Reproducing Kernel Hilbert Space (RKHS)
53:16 - Part 5: LUSI Approach in Neural Networks
59:28 - Part 6: Examples of Predicates
1:10:39 - Conclusion
1:16:10 - Q&A: Overfitting
1:17:18 - Q&A: Language

CONNECT:
- If you enjoyed this video, please subscribe to this channel.
- Twitter: https://twitter.com/lexfridman
- LinkedIn: https://www.linkedin.com/in/lexfridman
- Facebook: https://www.facebook.com/lexfridman
- Instagram: https://www.instagram.com/lexfridman

Today we're happy and honored to have Vladimir Vapnik with us, co-inventor of supported vector machines, support vector clustering, VC theory of statistical learning, and author of statistical learning theory.

He's 1 of the greatest and most impactful statisticians and computer scientists of our time.

Plus, he grew up in the Soviet Union, eventually heading the Computer Science Department Institute of Controlled Sciences in Moscow.

So he will give today's lecture in Russian and I will translate.

It's an honor and a pleasure to have Vladimir with us today, so please give him a warm welcome.

About 50 years ago, Professor Chervonenkis and me started statistical learning theory.

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

And there are this theory almost in all books.

They might be written in different languages, but mostly they follow this line.

The line is just law of large number is not enough.

We need uniform law of large number, uniform convergence and so on.

But because we started this discussion about empirical error, how good you do on the training data, and bound shows the better you're doing on training data, you will be better on test data.

People decided that it is only way to have a training data and do something with this training data, to minimize number of error.

And all algorithm was constructed based on this principle.

About 5 years ago, I found that there exists another principle even more interesting than this 1.

Because if this principle, it is brute force principle, Give me more data, I will give better answer.

So the second principle is intelligent principle.

So I will start with statistical learning theory, and then I will introduce this new theory.

But because there are only 2 ways for generalization, 1 with data, another I will show what.

I call it complete statistical learning theory because there are no other way to do something.

There are no third way for generalization.

But it is not so bad, because you will see that learning theory move in different direction, in direction of intelligence, to understanding what is intelligence.

It is not the same what Turing explained.

Turing told that you should imitate intelligent person.

But now a question, what is intelligence?

The first part is, this is the theory of generalization.

And that is the question, when instead of in a given set of function, you can minimize function now.

Instead of y f of x and l is loss function, I can consider difference between y and function.

It is what we're doing in regression, in pattern recognition, and all this stuff, but this is more general setting.

But this is more important, that when we consider minimization of function, we should say in which set of function.

In a given set of function, we have to minimize functional.

If probability measure is unknown, but we are given iid data pairs.

That exact setting of both path recognition and regression estimation problem.

For path recognition set of function is indicator functions.

For regression function it is continuous function.

We can minimize this functional using data if and only if this dimension H of set of function is finite.

Everything depends on which set of function you have to minimize this function.

So we call it capacity, but maybe it better called diversity of the set of function.

But measure of this capacity diversity is VC dimension.

You consider continuous function F and in front of it you're looking for indicator.

And we see this dimension of set of indicator function equal h if h is the maximal number of vectors that can be shattered, separated in all possible to the H subset using indicator function from the set.

So you have set, you should find H vectors which you can shatter in all possible way, to the l possible way.

But you cannot shatter in h plus 1 vector.

Then, you see dimension of this set of function will be h.

And if you can shatter for any l, then we say that VC dimension is infinite.

And then I will give you 2 theorems which we will use and then the main theorem, probability of the theory.

If set of function has VC dimension H, then this probability of 1 minus zeta for all functions in the set, the bound holds true.

And because this bound holds true for all function, and you would like to have

right-hand side, you will choose function which minimize empirical loss.

And the second theorem, if you have set of linear function, indicator from the set of linear function.

And so happen that your vector x inside of circle for radius 1 and w inside of c, then we see dimension is bounded by maximum of 2 values, C and N, N is dimensionality of the vector, plus 1.

That means exactly that VC dimension can be smaller than dimensionality of the space.

And you can control somehow VC dimension, never show you have to, it is very important theory.

But what is the general way suggest VC dimension for searching for function.

You have set of function, maybe set of function have infinite VC dimension.

Then you make a structure of the set of function.

You choose subset of function, the small subset of function, with VC dimension H, then another subset of function which includes a small 1.

So this is nested, we have nested subset of function.

And then when you're minimizing this function, you're doing 2 things.

You choose appropriate subset, and then in this subset, you pick up function which minimize empirical loss.

you can see that epsilon in this depend on VC dimension of subset you choose.

And also it depends on the empirical loss which you achieve.

So you can do, as soon as you make a structure, you can do whatever you want, even if you have infinite VC dimension in initial set of function.

But this is more or less all what contain the main result of VC theory.

But VC theory does not answer 4 very important questions.

Have to choose loss function LYFI told that any function.

Have to select admissible set of function f of x.

I told you that given set of function, but my business is stupid set of function, have to construct good set of function, how to construct structure on the admissible set of function and then how to minimize functional to construct the structure.

In this talk I will try to answer all those questions.

What is setting of pattern recognition problem?

I will consider in this talk just pattern recognition problem for 2 class classification, but generalization is straightforward.

So what is setting of pattern recognition problem?

Given generator, given nature, we generate randomly and independently situation X, which come on the object.

And this object is conditional probability y given x, says that y equals 1 given x, and y equals 0 given x.

This object knows this conditional probability and play dice.

So he has a function of conditional probability, he has x on the input, he plays dice and say y.

That is the most general setting of learning problem.

Deterministic is particular case of this set.

Learning machine has a set of functions and it can choose any function from this set.

And the problem is observing L observations, X1Y1XLYL, to pick up the function for classification.

That means given observations generated by conditional probability PXY equal P, Y given X on P of X, that's the whole scheme, finds the rules that minimize functional.

So in my case, when I have Y 0 or 1, or N theta also 0 1, it is indicator function.

So last function, I'll just collect how many errors I do.

But I have probability measure, it collect expectation of error.

I would like to find function which guarantee the smallest expectation of error.

Because my function now, this model is just, it is everywhere 0 except for some points where it is 1 or minus 1.

So it is 0 everywhere and defined and 1 in some point.

And people, what people doing, they replace model and indicator function with just

It's not so bad choice because it's so happened that minimum of this function now gives conditional probability function, probability of y equal 1 given x, And then when we can find this probability of y equal 1 given x, we easily can construct our decision rule.

We just consider function if our conditional probability exceed

But Something wrong with this replacement.

I will subtract from bracket inside on the first term.

So the last integral show me the first integral does not depend on function, which I looking for, and I have to minimize my function now over f over set of function, just sum of 2 last terms.

How I got this, it is just normal binomial for 2 terms, square of 1, square of second, and 2 term with multiplications.

But our goal is to minimize first integral, to find function which is close to conditional probability function, not sum of 2 integrals.

We can show that second integral eventually will go to 0, but it will slow down rate of convergence.

To have a rate of convergence big, we need to find way how to minimize first integral, not sum of these 2.

And that means that not least square loss, but something else.

First of all, when y, it is 0 or 1, probability of y equal 1 given x is some real valued function between 0 and 1.

from Bayesian formula, we know that probability of conditional probability of y equal 1 given x on density p of x, it is joint density p of y given now comma x.

Now if I will multiply on some function, g of x minus x star, which belong to L2 space, and take integral, I will have this equation.

And I can say that conditional probability is solution of this equation.

It was constructed like that because You see I put conditional probability, I did something like that.

But I would like to solve this equation to find function when I don't know probability measure, but I'm given data.

Given observations generated according to Px, Pyx, I would like to solve this equation.

But solving equation, it is ill-posed problem.

But before I will do that, I would like to mention that in classical statistics, there is a way have to replace unknown probability measure with empirical measure.

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.

So in classical statistics, people suggest to approximate cumulative distribution function by empirical cumulative distribution function.

And that is empirical cumulative distribution function.

In 30 years, mathematician tried to prove that it is good idea that we can do that.

And in 33, Kolmogorov found exact bound which is on the last line, almost the same like on the last line, and then people prove that we have bound like that.

Now, if we can replace unknown measure with empirical measure, we can construct our problem, our constructing problem, what we should do.

Let us replace in this functional, which we would like to minimize, instead of real measure, empirical measure.

And we will have empirical least square root functional which we have to minimize

to find our problem, to find our conditional probability of decision rule, whatever you want.

But let me consider a new constructive set, where we also will replace a known probability measure with empirical probability measure, obtained on the training data.

And to find conditional probability, we have to solve this equation in set of function f of x.

Right hand side is known because our function g is known.

In left hand side we don't know f of x so it is our goal in the set of function to find this function.

In classical statistics it was 1 algorithm called Watson-Nadaray estimator.

It show how to estimate conditional probability to a regression function.

And this is a show function which is have a numerator and denominator.

So, and g is special kernel, say Gaussian.

So this is estimate of regression, a very general way of estimation regression, conditional probability, and all this business have to find, if it Gaussian, have to find the best value of variance to approximate conditional probability well.

So they spent a lot of time on this subject and they have this.

This is Watson, not derived Watson estimator comes from corrupted equation.

Here it is in the middle is f of x, not of f of xi, like in last, like in correct.

So then you can put out of some f of x and you will get this function.

So actually classical, what's an estimator, it is solution of corrupted equation which we obtained.

To solve equation means I will take a difference between left-hand side and right-hand side, define area where I would like that my function will operate, take a square, and integrate over some probability measure and minimize this function.

And if you will do simple algebra, it is just very simple and you can check it.

You will have this Rf function, which is y minus f of XYYJ minus f of x, j multiply on some coefficients, YXJ.

And this value is jxy, xi, jxi, xj over measure, and this is matrix.

If you know from Watson-Nadarayev exact formula, this is it, we know this matrix, this element of matrix.

If you will replace this integral, this empirical integral, we will have this estimate of the matrix.

If you will use just say, line between minus 1 and 1, and mu of x is uniformly distributed over this line, we will have, and g is Gaussian distribution, we will have this V matrix.

What I will do, I will call y vectors of elements of training data y1, yl.

I'm given l pairs, so I create y, vector y, which is vector of all y's.

I will create F, capital from f, which is also l-dimensional vector of, I will pick up function f, and this is value of this function in point x1, and the last is value of this function is the point xl.

So, and I can rewrite this functional in the way that in matrix form, I have y minus f capital from FVY minus f capital from F.

But if I will write this notation least square, I will have Y minus F capital from F, Y minus F capital from F, and here instead of Y, identity matrix.

So I got some improvement over least square method and I hope that it will give me rate of convergence better than this least square method.

But it is not major stuff because okay, I improve rate of convergence but it's still least square method good.

But now the most important part, selection of admissible set of functions.

What it means, When you're constructing neural network, you're talking that you're doing smart structure.

What it means, you're talking that you're constructing smart admissible set of functions.

You just construct it and then you minimize over this set of functions.

But Let me consider from a mathematical perspective what it is.

If you consider Hilbert space, and also Euclidean space, in this space there are 2 way of convergence.

Strong convergence, it is convergence of functions.

My set of, my sequence of function f l converge to f 0 if f l is in this integral converge when f l goes to infinity.

You say that my set of, my sequence of function f l converge for f 0 if this inner product converge to this inner product for all function phi from Hilbert space.

You can, thinking that this is a inner product, describe property of function.

If for all functions, property is the same, that will be convergence.

So it is easy to show that if you have strong convergence, you also have weak convergence.

But also, 1 can prove that if you have weak convergence and your set of function belong to compact, you also have strong convergence.

So In some sense, the both convergence are equivalent.

of machine learning, we consider stroke convergence everywhere, 100%.

For path recognition case, the first line, I just writing definition of weak convergence equals second.

And that is I use by same equation it is phi from dp equal 1 over phi for all function from phi.

it converge, it must converge for all function from phi.

If it converge for all function from phi, I will have 1 function, which is desired 1.

Let us select from set of Hilbert space, m function phi.

We will talk a lot how to select these functions.

So, and then we will consider equality, not for all function, but just for this m function.

And we will call admissible set of functions the set of function which satisfies this equality.

We know that our function must satisfy this equality for any phi, any phi because of V convergence.

So, but we select something which we want.

Okay, if you will use instead of our cumulative distribution function, it empirical estimate, we will have, instead of integral property like here, the property written by the sum.

Again, let me use the same notation for matrix scheme.

I will use y vector, I will use function f, capital from f, which is f from x1, f from xl, which is vector.

And also, I introduce new vector, vector of predicates on the value X1XL.

I can consider the value of function in this case.

I would like that my admissible set of function satisfy in vector form this m equations.

Now, Let me explain what we're talking about.

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

What this means, we have the statistical invariance in vector form of this line.

What it does, it collect admissible function which identify animals as a duck if it looks, swims, and quack like a duck.

So if you will choose predicate which explain what means looks, swims, and quack, then your admissible function will be function, such function, which classify animals that swim, quack, and looks like a duck.

Concept of predicate, it is very different from feature.

With increasing number of predicate, the VC dimension of admissible set of function is decrease.

Because we have set of function, then we from this set of function, select function, which satisfy new predicate.

Not all of function will satisfy and consider only set of function which satisfy all this predicate.

But with increasing number of features, we see dimension increase because your decision rule becoming more and more diverse.

So what is exact setting of complete learning problem?

Minimize functional, which is with this V matrix.

A little bit improve of least square functional.

And this constraint is what you would like to see in the set of admissible functions.

But existing classical method of pattern recognition, they just minimize this functional, that least square functional.

So we're minimizing this functional subject to this constraint.

That was exact setting, which is in mathematical is called conditional optimization.

Optimization of functional under conditions.

But approximation is unconditional optimization.

I would like minimize this functional subject to this constraint, but I will do the following.

I will make a sum of this functional and I will take square of difference between this constraint and make a sum with some weight.

So I would like to do both, to minimize over both, and put weights, how important for me to minimize data and how important for me to minimize constraint.

And then if I will do that, I can rewrite this function in this way, where you have to minimize this function.

And where P is just covariance matrix of your predicate.

See all Lex Fridman transcripts on Youtube

Complete Statistical Theory of Learning (Vladimir Vapnik) | MIT Deep Learning Series