#140 Isabelle Guyon: The Future of AI and Support Vector Machines

0:00The vectors are actually the coefficients or the features, the components that you compute that get into the system. So the vector is the list or the collection of all the information that you've gathered that include in my example of medical classification. It could include the age, the amounts of certain proteins, the family history, anything that goes into your medical files. The amazing thing is that it looks like from this just very simple training strategy, predict what comes next from the past part of the sentence, you can get these chatbots like ChatGPT that give very sophisticated answers.

0:41But this should not fool us because really we've trained parrots. Hi, I'm Craig Smith and this is Eye on AI. It's an increasingly confusing time in machine learning, with generative AI consuming all the oxygen, and a plethora of startups offering new services based on large language models. While I'll continue to talk to select founders, I'm going to try to get back to fundamental research and pay attention to the many avenues that have sort of fallen by the wayside, but are still pushing AI forward. This week, I speak to Isabelle Guillaume, a French researcher in machine learning and pattern recognition.

1:27She's known for her work on support vector machines, otherwise known as SVMs, a type of supervised learning algorithm used for classification and regression analysis. SVMs are based on the idea of finding the boundary that separates data into different classes with the largest possible margin. Support vector machines are still widely used today in a variety of applications, including image classification, text classification, and bioinformatics. SVMs are particularly useful when dealing with high-dimensional data. While deep learning has dominated AI in recent years, SVMs remain a powerful tool in the machine learning toolkit.

2:18I hope you find the conversation as informative as I did. Before we begin, I want to give a shout out to our sponsor, UAI. They're a fascinating company that does a number of things, but I'm most interested in their Mind Studio, which is a platform for building AIs on top of large language models that you can deploy for free or for profit. Think back to the days when smartphone apps were first getting started, and if you were able to have been among the first couple of thousand people to build a smartphone app, you would have learned a lot and may have earned a lot of money. So give MindStudio a try.

3:05Visit uai.ai to build your own AI today. I'm a professor at Université Paris, and I'm in the detachment at Google as a director of research in San Francisco. I'm also president of a nonprofit organization called Chalearn, which is dedicated to organizing challenges in machine learning. And I've had a long time interest in benchmarking machine learning algorithms. As early as, you know, during my thesis, I was already collecting data samples of handwritten digits. And I collected one of the very first data sets called the little 1200 that had 1200 digits written by people at Bell Labs while I was doing an internship there.

3:57Yeah. When you were at Bell Labs, I'm guessing that's where you worked with Vladimir Vapnik and others on support vector machines. Is that right? Or did your work on that start before that internship? Yeah, that's right. Actually, I started working towards the end of my PhD on kernel methods. I was guided by that by one of my mentors, John Denker, with whom I was doing this internship at Bell Labs before the end of my PhD. And also, I was working on methods that we now refer to as the kernel trick that one of my co-advisors, Leon Personas, had pointed out to me. There was a paper from Tommy Poggio in 1974 that had induced the polynomial kernel.

4:41And I was using that in my thesis to make Hopfield networks behave as nonlinear, learning machines that are nonlinear in their parameters, to be more precise. So my PhD was originally on architectures of neural networks. I started off with studying Hopfield networks that were inspired by magnetic systems. The reason for that is that I was studying in a physics school, the School of Physics and Chemistry of Paris. That's where Marie Curie and Pierre Curie discovered radium. So I was always very inspired by Marie Curie. So I'm very fortunate that I studied in that school. And yes, initially I was a physicist and worked with Hopfield Networks with my advisors, Gérard Dreyfus and Léon Personas.

5:25And so, yes, I was familiar with the kernel trick and I was already using it during my PhD. I was also familiar with large margin methods. That is the other component of the support vector machine algorithm, as there were people from Ecole Normale right across the street from my school who are working on methods called from minimum overlap. So these are methods that ensure stability and basically also see a large margin. And so, yeah, when I started working at Bell Labs, the situation was very different than from when I did my internship. Yann Le Kuhn and Bernard Bozer, two young men, had just joined.

6:03And there was a lot of excitement around backpropagation networks that at the time were called multilayer perceptron. And I was strongly advised by my department head, Larry Jackal, to work on backprop nets. And so I started working on them. And I did some work with Yann Le Kuhn on applying convolutional neural networks to pen computers. So how to replace the keyboard by a pen. At the time, we thought this was very promising and handwriting would be a good user interface. We were proven wrong. And only basically two years after I joined Bell Labs, Vladimir Vapnik came. At the very beginning, he shared my office because there was no office space for him yet.

6:45So I was very lucky to have many long conversations with him. And he talked about this algorithm for optimal margin that he had an appendix of his book and that nobody had ever implemented. I thought this was interesting. I mentioned to him work that I had done around that. And I always thought, yeah, I should do that. I should implement that algorithm. But I was busy with many other things. So I never did it. And then all of a sudden, my husband got a position at UC Berkeley, and he didn't have time to start a new project before we left. And he was seeking a short thing he could do. And he asked Vladimir Vapnik, what is some small project I could do?

7:24Well, We're waiting to leave to California. I can't start a new hardware project. He's a hardware guy. Something small and very inventive. And he said, oh, well, implement my optimal margin classifier. And so he did. And I thought, oh, my God, I'm going to be scooped. I really wanted to work on that. And then my husband, Bernhard Bozer, the third co-inventor of a support vector machine, came to me and said, oh, yeah, it works nicely now. And Vladimir said I should move on to a nonlinear version of it. and we should make products of the inputs to make it nonlinear. And I said, no, you shouldn't do that.

7:59You should use the kernel trick. It's much more powerful. That way you have almost for free the possibility of plunging your problem in a very high dimensional space, but just essentially taking every dot product and replacing it by another similarity measure. And for example, you need to take every dot product and raise it to a certain power. And say, wow, this is simple. So he didn't really know how to do that with the algorithm that was in the appendix of that book. So I just rewrote the algorithm and he implemented it. And sure enough, it worked very nicely. Yeah. So to make a long story short, this is how the invention of SDM happened.

8:38That's interesting. I didn't realize that you were already working on neural nets when you did that work, or on backpropagation, I should say, because I'm a novice. So correct me if I'm wrong, but support vector machines are not deep learning. They're a much simpler way of classifying data and work very well on small data sets, whereas deep learning, you need very, very large data sets. Was there a connection between your work on the nonlinear support vector machine and backpropagation, or were they very separate? No, they were not separate at all. They were not separate. For me, it was, I should tell you why I didn't do the work on support vector machine earlier than I did, and I was dragging my feet to implement that algorithm.

9:23The reason is that I thought this wouldn't make that much of a difference because the way I was training neural networks was with a strategy very similar to support vector machines. I had realized early on that in order to effectively train, you need to be focused on those examples the hardest to learn, which ended up being called the support vectors and the examples that are closest to the decision boundary. So this is already underlying also the other works going on, finding large margin algorithms that are stable. The idea is very simple. The idea is that if you have a variety of possibilities to separate examples, and that happens often when you have very few examples and you are in a large dimensional space in particular.

10:10So if you have very few examples, there are many ways in which you could create a decision boundary. There's a no man's land between the decision boundary and the examples. And it's natural to say that you want to have the largest possible distance between the decision boundary and those examples, which is the idea of the large margin classifiers, the large stability classifiers, etc. How do you achieve that? Well, you actually achieve that by showing more often the examples that are hardest to learn. And this is what was underlying this algorithm that had proposed many people at ONS close to my institute when I was doing my PhD.

10:47What their algorithm was doing is that it was a modification of the very classical perceptron algorithm. In the very classical perceptron algorithm, you make a change in the weights when an example that is shown is misclassified. And you don't make a change if the example is well classified. And the very minor change that they made in this algorithm is that they were going through all the examples of the training set, and they made a change only for the example that was worst classified. And that simple change, you can show that asymptotically the algorithm converges to the optimal margin classifier.

11:24So it reaches the same solution as the SVM. I had many arguments with Vladimir Vapnik, what was best. He told me, well, this algorithm only asymptotically converges. It is not guaranteed in a finite number of steps to get to the solution. But on the other hand, it's amenable to be combined with the very popular stochastic gradient descent methods that neural networks are trained with. Because the only thing that you need to do is you train your neural network and you show more often the examples that are hard to learn. So in the extreme case, you would at each epoch only show the example that is hardest to learn.

12:03But this is kind of inefficient because you have to do a forward propagation for every example, figure out which one is the worst one, and then only update the weights for that one example that is hardest to learn. So it's a waste. So you can do something in between, identify the examples that are hardest to learn, and only do the updates on those. And this is what I had implemented, and it worked very nicely. So I didn't really see a need to implement this algorithm. I was getting good results. Now, what happened is that when Bernard Bosom has been implemented Vapnik's algorithm, he got good results.

12:41And then I suggested to combine it with the kernel trick, which is the trick that I was using also extensively with other algorithms than the maximum margin algorithm already in my thesis. And it's not a new idea. It comes from the 1960s. There's a paper about this idea of the kernel trick. Perhaps most interestingly, this paper was written in the same institute as Vapnik, and he never realized that the two algorithms could be combined. It was called the potential function algorithm, and his algorithm was the optimal margin algorithm. So it took 30 years before somebody had the idea of putting them together.

13:20My conjecture is that because they were fighting for funding, so they wanted to differentiate their methods as much as possible, and so they had never considered putting them together. So at any rate, yeah, I finally pushed Bernhardt to use the kernel trick with the optimal margin classifier. And then, yeah, this gives this new algorithm that basically sparked a big fire. Yeah. It just occurs to me for listeners that don't know what support vector machines are that we should probably define them. Okay. Let me try to explain that. Without pen and a paper, it's a little hard, but you'll stop me anytime with questions.

13:55So, well, the auditors probably know about classification problems that have been popularized with AI and neural networks. We've seen a lot of applications of face recognition, of object classification, of text classification, for example, classifying between spam and ham or classifying between bees and wasps if you want to determine which insect is a good pollinating insect or a dangerous insect. Anyways, this has taken off recently using neural networks, for the most part because neural networks are very good at learning representations, whereas algorithms like support vector machines rely on the fact that you've already come up essentially with a good representation.

14:44And this is not so obvious in the case of computer vision problems because you basically start with an image that has been transformed into pixels, that, you know, little elements of image. And so the representation is bizarre, right? What the algorithm sees just little dots that don't seem to make so much sense. They don't have an idea of what the object is as a whole from these little dots. But for a lot of applications, the representation that you start with makes more sense. For example, if you have a biomedical application and you're trying to classify whether patients have cancer or not, you may have a whole bunch of diagnoses, like whether you have a sort of protein in your blood that has an elevated.

15:30That is the case, for example, if you diagnose prostate cancer, the prostate cancer antigen is elevated often in prostate cancer patients. This is not going by itself to give you a certain diagnosis, but if you have many features together, like the age of the patient, family history of cancer, the weight of the patient, whether the patient has been exposed to certain chemicals, etc. These are all called biomarkers. If you use all of them, you can try to create a classification method that will tell you with a certain confidence whether the person is at risk or not of a certain disease. And this is what these methods try to compute.

16:10They try to compute a number that rates the degree with which you believe that a certain person or a certain object belongs to a certain category. So you can do that with many different methods, but in machine learning, what you do is that you get examples. So you get examples of all these different features, and you have examples of normal patients and these patients. And then you try to determine whether you can combine these different coefficients or these different features. We call them pictures, coefficients, biomarkers, etc. All these quantities that you've measured about the subjects of interest.

16:53You try to combine them and then come up with a single number. So how do you combine them? One of the easiest ways is that you turn them into numbers and you do a voting, which is a weighted sum. So you multiply each coefficient by a weight and then you average. So it's like voting, where each voter would have a different number of votes. Some coefficients will be seen as more important than others. But these weights, these weights are subject to training. So they are adjusted during a session in which you show many examples, and then you try to make it that according to the combination that you are computing of these input coefficients, you can then separate well the training examples.

17:36So you vote among these many features. you get this coefficient that is the average vote. And you see if the average vote is higher than a certain threshold, I will say that this is a disease patient. If it's lower than the certain threshold, this will be a patient that is not at risk. So what does SVM do more than any such method? Well, what it does is that if you come up with one such combination, what you want is to have the maximum distance between the disease patients, say, for example, in this example, and the non-at-race patients. These are basically according to this rating that you've made, which is the voting that you've created.

18:15According to this rating, if you would just represent all the patients on the line and look at what rating they get, and you put on one side all the patients that have high rating and on the other side the patients that have low rating, you will have some that are borderline, right? That have rating that is neither very high nor very low. And you would like to have the maximum gap between the ratings of the patients that are at high risk and the patients that are at low risk. And if your rating is such that you can make a really big gap, then you can be reasonably confident that you've made a good discrimination between these two types of patients.

18:52If you don't succeed in separating them well, for example, if there is an overlap between the distribution of the patients at risk and the distribution of the patients that are not at risk, then you can't really separate them well and then you kind of fail, right? So the idea between a maximum margin classifier is that if with the training examples you can maximize this gap, then maybe when you get new patients that you haven't used for training, they will not be classified incorrectly. So you have basically this big gap. In the middle of the gap, you can say, okay, this will be my decision threshold.

19:27I put it in the middle of the gap. Now, what you don't want is that patients that are of the wrong category climb over the decision threshold and end up on the wrong side. So if you have the maximum possible gap, then you can minimize your chance that the new patients will cross the gap and end up on the wrong side. And this is primarily for labeled data. Is that right? That is correct. So originally, the original algorithm was created for classification problems with label data. And moreover, the labels are categorical, that is, they correspond to different classes or categories. Later, it was generalized by Vepnik and other collaborators to the regression case in which what you want to predict is not categories but continuous values.

20:10For example, if you wanted to predict the age of somebody based on pictures, then this would be a regression problem, not a classification problem. And then it was also extended to unlabeled problems, so-called unsupervised problems, for example to the problem of determining the support of a density by Bernard Shalkoff and also to some clustering methods that are also for unlabeled data. But the same idea always applied, and the idea is you create a no-man's land, a big gap, so that you get some confidence that when you get new examples, then they will not kind of cross the border and end up making wrong decisions.

20:50And at this point, because deep learning, backpropagation, supervised learning, I should say, in deep learning has been so successful in classification, if you're building a model, what point do you decide, oh, this should, I should use deep learning or I'll just use support vector? Yeah, I think the method, the mistake people make is that, is to oppose the methods because they're completely complementary. They address essentially different problems. The deep learning methods address the power of learning representations. And once representations are learned, which can take a lot of compute resources, and we see now that it's very common that big companies train for many days with very large forms of computers, a model that is then released publicly.

21:37And we are very grateful that such companies are generous and share that with the public. Then these models can be stripped off their last layer that's basically making decisions and used as a preprocessor to compute new features. So that's what's missing essentially with super vector machines, is that they are not very good at coming up with good features, even though they can implicitly function in a very large feature space. I didn't explain the kernel trick, but I can explain that later. But essentially, they still rely on original features that are man-made, that are the input. And so they can benefit greatly from using as a preprocessor the features computed by deep learning methods.

22:21And then if you do that, then you can harvest the benefits of these methods because they can learn with very few examples. And in fact, there are many methods that are so-called future learning methods that are essentially based on kernel methods. When I talk about kernels, it's a broader family to which support vector machines belong. And these are methods that you can call case-based or example-based methods that rely on memorizing examples, essentially. The question is, what are the vectors in a super vector machine? The vectors are actually the coefficients or the features, the components that you compute that get into the system.

23:01So the vector is the list or the collection of all the information that you've gathered that include in my example of medical classification. It could include the age, the amounts of certain proteins, the family history, anything that goes into your medical file. So this would be a vector. And why not take a stab at the kernel trick, since I don't understand it? Okay, so now I've only talked so far about the vanilla, essentially, support vector machine, the linear version that was already invented in the 60s by Vladimir Vapnik and his collaborators, that consists in just making a vote among the inputs or the features that I was mentioning.

23:43So to take this a step further and go beyond linear classification, we can manipulate these features. And this was the first idea of ethnic. Let's make products or sums or let's make functions of these features and put that at the input of the classifier. In this way, we're going to massage them first in many different ways. And then hopefully this will create a richer vocabulary, in essence, that will make it possible to get more complex decision boundaries. That idea is not new. Already in the 60s, Frank Rosenblatt and his collaborators when they invented the perceptron, they in fact already had a first layer that was made of random functions.

24:25So you take the inputs and you combine them randomly. And so you expand your feature vector to a very large feature vector. And it can be shown that if you do that, then virtually every possible separation of a finite number of examples will be able to be made, provided the feature vector is long enough. So it's a question of, the big question that people had in the 60s is whether the examples are linearly separable, which means that if you have some training examples, will you be able to compute a weighted sum such that all the training examples of the first class are on one side and all the training examples of the other class are on the other side?

25:04And you can just set a threshold on this combination and you can classify 100 % correct all the training examples. So everybody was set on that problem. And later people discovered that it's not really necessary to have all the examples of the training set perfectly separated to get good generalization on test examples. But at any rate, this was really their focus. And so people had come up with that idea of let's make random functions. And then we will have a much larger space of features. And then if that much larger space of feature is going to be much easier to be able to find a combination that will separate perfectly the training examples.

25:42So a linear combination. So starting from this idea, then some people have observed that, in fact, you could use a different type of method that is an example-based method, similar to what people call the nearest neighbor classifier, and transform it into one of these linear classifier methods. So how does it work? Well, first of all, let's understand the nearest neighbor classifier. It's a very simple method. You just calculate the distance between your new unknown example with all the training example, and you classify it according to the example that is closest to it. So if you have a new patient, compare that patient to all the patients you have in your database and find the medical record that is most similar to that patient's medical record, and then classify that patient as disease or not disease according to this training example that you have.

26:34Okay. And so people invented many variants of this nearest neighbor method. And those methods are as a whole known as kernel methods. And what is a kernel? Well, a kernel is very simple. It's nothing but a similarity measure. I was talking about distance, but whenever you have a distance, you can also define a similarity measure. It's the opposite, right? The distance says how far away two examples are, a similarity measure, how resemblant they are. Some similarity measures are very simple to compute. For example, if you just do correlation. Correlation is a similarity measure. Everybody knows percent correlation coefficient.

27:10So if you take two records and compute their correlation, then you compute their similarity in a way. Well, there are many ways in which you can compute similarities. And you don't need to use just a correlation coefficient, which is basically a linear way of computing similarity. One popular way of computing similarity is to use a Gaussian kernel. And that's a method for a distance like the Euclidean distance, and you raise it to the minus power, the distance square. And the result is that you have high resemblance near the example that you compare with, and then the similarity dies off quite quickly as you get farther away from the example.