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

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 one 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 Control Sciences in Moscow. So he will give today's lecture in Russian and I will translate. Just kidding, right? It's an honor and a pleasure to have Vladimir with us today. So please give him a warm welcome.

Thank you. About 50 years ago, Professor Chervonenkis and me started statistical learning theory. The problem 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. You will minimize expectation of error. So we solve this problem. 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 that 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 five years ago, I found that there exist another principle even more interesting than this one. Because if this principle, it is brute force principle, give me more data, I will give better answer. The second principle is intelligent principle. And I will talk today about this. So I will start with statistical learning theory and then I will introduce this new theory. But because there are only two ways for generalization. One with data. Another I will show what I call it complete statistical learning theory. Because there are more also another way to do something. There are not third way for generalization. You should use both of them. So that is complete theory. 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 question what is intelligence? And we will discuss this. So let me start the first part is this theory of generalization. And that is the question when in a given set of function we can minimize function. Now this is pretty general 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 and pattern recognition and all this stuff. But this is more general setting. But this is more important that when we consider minimization of functional, 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 pattern recognition set of function is indicator functions. For regression function it is continuous function. But the statement is the same. But the answer is very simple. We can minimize this functional using data if and only if this dimension age offset of function is finite. Everything depend on which set of function. You have to minimize this functional and you cannot avoid that. So we call it capacity. But maybe it better call diversity of the set of function. But measure of this capacity diversity is VC dimension. And what is VC dimension? I will give you definition. First we set of indicator function T is step function. You consider continuous function F and in front of it you're looking for indicator. If function is positive you say one, if it's not positive, you say zero that is indicator. And we see this dimensional set of indicator function equal H. If H is the maximal number of vectors that can be shattered separated in all possible 2 in the H subset using indicator function from the set. So you have set, you should find H vectors which you can shutter in all possible way to the possible way. But you cannot shutter in H +1 vector. Then you see dimension of this set of function will be H. This is pure combinatorical definition. And if you can shutter for any L, then we say that VC dimension is infinite. And then I will give you two theorems which we will use. And then the main theorem probably of theory. If set of function has VC dimension H, then this probability of 1 minus Z for all functions in this set the bound holds true. And because this bound holds true for all function and you would like to have a minimal estimate the minimal 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 VC dimension is bounded by maximum of two values c and n is dimensionality of the object 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 how. That 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 this set of functions. You choose subset of functions, a small subset of function with VC dimension H. Then another subset of function which includes a small one with this dimension H2. So this nested we have nested subset of function is nested with the dimension. And then when you minimizing this functional, you're doing two things. You choose appropriate subset and then in this subset you pick up function which minimize empirical loss. But you can see that epsilon in this depend on this dimension of subset. You choose at this dimension over L. And also it depend on 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 functions. But this is more or less all what contain the main result of BC theory. But VC theory does not answer four very important questions. How to choose loss function? Lyfe I told that any function have to select admissible set of function F of X. I told you that given set of function. But maybe this is a stupid set of function. How to construct good set of functions, 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 these questions. Target functional minimization. And this is important. Slide Good place dice. What is setting of path recognition problem? I will consider in this talk just pattern recognition problem for two class specification. But generalization is straightforward. So what is setting of pattern recognition problem? Given generator given nature, we generate randomly and independently citation X which come on the object and this object. This conditional probability Y given X says that y equal 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 yes, that is the most general setting of learning problem deterministic is particular case of this set. And what does learning machine? A learning machine has a set of functions and it can choose any function from this set. And the problem is Observing L observations x1 y1xly to pick up the function for classification. That means given observations generated by conditional probability p xy p y given X on P of X. That's all scheme find the rules that minimize functional. So in my case, when I have y0 or 1 or and theta also 01, 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. But this is not very good. Why it's not very good? Because my functional this model is just it is everywhere 0 except for some points where it is 1 or minus 1. So if I took model it is 1, so it is 0 everywhere and in defined and 1 in some point. So I cannot use gradient in this case. So I should do something smarter. And what people doing? They replace model and indicator function with just Y minus F of x least square error instead of whatever I formulated before. It's not so bad choice because it's so certain that minimum of this functional gives conditional probability function probability of y +1 given x. And then when we can find this probability of y =1 given x, we easily can construct our decision rule. We just consider function. If our conditional probability exceed 0.5, say first class. If it's less than 0.5, second class. And this is optimal solution. But something wrong with this replacement. Let us rewrite the first line. I will subtract from bracket inside on the first term regression and then odd regression. So I have two brackets instead of one. And then I make a square. So the last integral show me the first integral does not depend on on function which I looking for. And I have to minimize my functional over F over set of function just sum of two last terms. How I got this, it is just normal binom four two terms square of one, square of second and two term with multiplications. But our goal is to minimize first integral to find function which is close to conditional probability function not sum of two integrals. We can show that second integral eventually will go to zero, but it slowed 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 two. And that means that not least square square loss, but something else. What we can do there exists. 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. Because from Bayesian formula we know that probability of conditional probability of y 1 given x on density P of X, it is joint density P of Y given now comma X that is just always true. Now if I will multiply on some function G of X minus X star this 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 imposed problem. Okay, let's do that. But before I will do that, I would like to mention that in classical statistics there is a way how to replace a known probability measure with empirical measure. That is the most important part is main induction step in statistics. In statistics we're given data and would like to know function. It doesn't matter how many data we will see. It is not equivalent to function. 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. 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, this 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 conditional probability or decision rule, whatever you want. But let me consider new constructive setup where we also will replace unknown probability measure with empirical probability measure obtained on the training data. And you will see the last equation. 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 this set of function to find this function. In classical statistics. It was one algorithm called Watson Nadarai estimator which show how to estimate conditional probability or regression function. They just somehow define this. And this is a show function which is have a numerator, denominator numerator. So NG is special kernel, say Gaussian. So this is estimate of regression. A very general way of estimation regression, conditional probability. And all this business how to find if it goes and how to find the best value of variance to approximate additional probability. Well, so they spent a lot of time on this subject and they have this. But you can see the line in middle. This is Watson derived Watson estimator comes from corrupted equation, not form equations which we derive 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 Watson Watson estimator, it is solution of corrupted equation which we obtain. But what means to solve equation? 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 functional. So let us do that. 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 X Y YJ minus F of xj multiply on some coefficients XY xj. So we can estimate this value. And this value is J x Y X I jxi XJ over measure. And this is matrix. And if you know from Watson exact formula. This we know this matrix, this element of matrix. So what is V matrix? If you will replace this integral with empirical integral, we will have this estimate of V matrix. If you will use just say line between -1 and 1 and Nu of X is uniformly distributed over this line. We will have and we will have NG's Gaussian distribution. We will have this V matrix. So V matrix is easily to find. Now I would like to use vector notation. What I will do, I will call Y vectors of elements of training data. Y1, Y L. I am 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 this is F. And I have V matrix. So. So and I can rewrite this functional in the way that in matrix form I have Y minus F capital from F V Y 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 gives least square method. But let's see. But it is not major stuff, because okay, I improve rate of convergence. But it still lists were not 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 talking that you're constructing smart admissible set of functions. You Know something? You're smart guys. You just construct and then you minimize over this set of functions. But let me consider from mathematical perspective what it is. If you consider Hilbert space and also Euclidean space. In this space there are two way of convergence. Strong convergence. It is convergence of functions. It is first line. My sequence of function fl converge to f 0. If fl is in this integral converge when fl go goes to infinity. But there exists weak convergence. We say that my sequence of function fl 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 inner product described property of function. If for all functions properties the same, then will be convergence. So it is easy to show that if you have strong convergence, you also have weak convergence. It's just from Watson, from Schwarz inequality, casuist Schwarz inequality. But also one 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. In our consideration of machine learning, we consider stroke convergence everywhere 100%. But what about weak convergence? Let's explore this opportunity. Let us consider path recognition case. For path recognition case, the first line I just writing definition of weak convergence equals second. And that is I use bias in the equation. It is phi from DP =1 over phi for all function from phi. So it converts. It must converge for all function from y phi. If it converge for all function from phi, I will have one function which is desired one. But it is not realistic. Let us do following. 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. 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. For any function F, I have vector. And also I introduce new vector vector of predicates on the value x1, xl. Because phi is function, I can consider value of function in this case. Then I can write my equation in this form. I would like that my admissible set of Function satisfy in vector form these M equations. Now. Let me explain what we're talking about. There is a duck test logic. 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. It is 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 explains what means looks, swims and quack, then in your admissible function will be function such function for which classify animals that swim, quack and looks like a dog. Concept of predicated it is very different from feature, right? So with increasing number of predicate, the VC dimension of admissible set of function is decreased. Why it is a 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. We satisfy all this predicate. But with increasing number of features we see dimension increase. Because your decision will be coming 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 subject to this constraint. And this constraint is what you would like to see is a set of admissible functions. But existing classical method of pattern recognition they just minimize this functionality that at least square functional. So we minimizing this functional subject to this constraint. That is our set 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 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 weight. It should be one. 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 now and where P is just covariance matrix of your predicate. And everything is simple compute. So that is concept what we have to do. We have to solve our problem using both big and strong convergence. That means using invariance and minimizing functionals. And we can do it in exact way and in approximation. But here it was written for any set of function. I did not talk how I will minimize that. So it is true as a least Square method. You can minimize least square function functional for any set of functions. That is the same here. But now let me see how I can find the solution. And first of all I will do it. For reproducing kernel Hilbert space. This is definition of reproducing kernel Hilbert space. You have some kernel which is mercer kernel. You multiply, you take inner product this function F of X and you have the same function. It is reproduced the same function. It's called reproducing kernel here in the space. And it is known that kernel Bertha kernel have expansion over lambda whereas lambda it is non negative values. And psi is orthonormal functions. So set of function with inner product and norm. This is inner product and that is norm forms. Reproducing kernel Hilder space. It is very easy to check. It means that if you will use some function psi or to normal function psi and expansion of C and if you will have this set of function and if you will introduce special inner product inner product of this type. And then you will have this definition. So you will have reproduction cannot heal that space. It is pretty general space. But in reproducing kernel Hilbert space you have a great theorem called representative theory. And represented theorem says if you would like to minimize this function in subset of function and subset of function. It's norm of your function. And reproducing kernel Hilbert space is bounded. So that your solution has a linear representation over kernel with finite number of parameters. So let's introduce matrix vector of functions f k x 1 of x. It is vector of expansion. And then square of our norm will be A and this is A over k. This is what is how it looks. Your function which you're looking for AKA is norm of your function. From reproducing kernel Hilbert space. K is matrix k x I, x j and this is F of F. From reproducing kernel Hilbert space is just linear function subset of function with bounded norm. And find VC dimension. The smaller C, the smaller VC dimension. And that is according to second theorem which I show you before and to control VC dimension you should control just C. You should looking for norm of this function. So conditional minimization and producing kernel Hilbert space has closed form solution. To minimize this functional subject to this constraint and constraint on bound of the norm will give you. And this is your solution. It linear expansion over this vector of functions and value of coefficients is like that where it is just in closed form. It is function of matrix is multiplication of matrix. This is gamma C. C is depend on this value C gamma Or c depend on this C. This is identical matrix. Or you have the solution and to find nu over here you have to solve linear equation. So you're solving linear equation and then you have closed form solution. So the complete problem in reproducing kernel Hilbert space have closed form solution. But what about unconditional minimization which approximately minimization like that in this constraint it also has closed form solution. And this is how looks closed form solution. Your solution is coefficients over this expansion and you have this equation. How to find a? So everything is computable. But very special role play in explanation support vector machine. What is support vector machine? Given data I would like in reproducing kernel Hilbert space this bounded norm minimize this functionality. And then when I minimizing this function. Now that is exactly you will get support vector machine. If you will look how derived support vector machine. It is just minimization this function. Now this set of function. But here I will do something else. I will do data like in support vector machine Y I minus A K A. That is, I would like approximate data is a norm like here. But also I would like to that my invariant will be good enough will be close left hand side and right hand side of invariant will be close. So I would like minimize this function. Now under the same constraint. And this is the solution. The solution is like a. A is function which is phi from T and phi from T. As you remember is it is vector of predicate and this is indicator vector. If I would like here to make strong for invariance and not too strong for approximation function. I just want to use just weak convergence. I will have that my A is defined by invariance by function of predicate. But my function of predicate. How I choose predicate? I can choose any function I want. That means that if I can choose one function which will give me optimal solution that there exists so smart predicate that I will not need a lot of data. Why I need data. I need data for expansion over kernel. But for estimating coefficients I don't need data. I use my predicate. And that means that what means predicate? It is property. It is explanation about what I want. I will talk about this later. So this example on support vector machine show that philosophy of this learning is very different. According to represented theorem solution of learning problem. In reproducing kernel Hilbert space have a property. It define linear parametric function in form of expansion of kernel function. That means that optimal expansion belong to one layer network, not multi layer network. But because of reproducing kernel Hilbert space is richer than this. Maybe it is not the best idea to use deep network. Deep network. Okay, we will discuss this in a bit. Observation vectors and kernel defined basis for expansion for optimal parametric solution. But parameters is defined by invariance. But you can use this invariance 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 F. Y is vector. F is vector. So you have element. You have different formulation of learning problem in term of this vector and these values. So simple function in Hilbert space can be. Since any function from Hilbert space can be used. Because when we told about weak convergence, it converged for all functions simultaneously of hillbar space. So any function can be used. So we have a chance to pick up several smart functions or maybe even one. And it will be enough for our training. And then we will talk about what means smart. It is intelligent learning, not just brute force learning. Let me give you illustration to have a feeling. This is least square method. What it does. This is vmatrix method. If I will do a little bit improvement, it's a little bit better here. If I will introduce invariants, I will do better here. If I will use both invariant and V matrix. So you can see this difference for 48 points. And to be sure that it is difficult problem, we took 16.