To Kernels and Back Again — A study of Empirical Phenomena in Machine Learning
Recording: To Kernels and Back Again — A study of Empirical Phenomena in Machine Learning
Club yep okay recording them okay cool all right cool all right let's get started Thank You Alexi my name is Vishal Shankar I'm a final year PhD student just offended a couple weeks ago at UC Berkeley I work with bender act and yeah and today I'm gonna be talking about some of my work over the last five years so this is basically just a rehash of my PhD defense so the general audience for this is like a general computer science audience because everyone in Berkeley defenses are open and Berkeley but there are like a few slides that are a little technical but most of it should be accessible but if you're confused at any point feel free to flag me down so that the whole idea of this talk is to talk about studying empirical phenomena and machine learning through the lens of this old algorithm or older algorithm called kernels if you if you're familiar with that so let's get started all right so I'm sure you guys have seen slides like this in many talks machine learning is like effectively fundamentally unavoidable in today's society so whether you're like dealing with law enforcement medical applications browsing the internet on Facebook YouTube or Netflix or order anything on Amazon you've probably touched a machine learning system in some way shape or form so so it's already out there the cats out of the bag machine learning is interacting the real people but we need to ask the question if we're going to deploy machine learning in in real life higher stakes scenarios we have to understand whether we understand machine learning or because these systems can fail and they can fail in quite drastic ways we know self-driving cars can crash we know that translation systems can make pretty big mistakes and we know that there's a systemic bias in our society can get propagated into our machine learning and we're sort of just automating bias with by automating by using machine learning on just a raw data so in order to understand understand your machine learning we got to go to this the primary workhorse of machine learning in the last ten years so most state-of-the-art algorithms in speech natural language processing computer vision are based on artificial neural networks so so we need we should be able to we should understand this algorithm if we're going to make any sort of broad statement of not machine machine learning and but the important thing to note is that this wasn't the algorithm of choice machine learning has been around for like 20 30 years or maybe 50 60 years depending on how you call it what way you caught machine learning but a neural networks have only been really popular since 2011 so only the last 10 years or so after they had phenomenal success in a particular task which is the image net object recognition task the actual algorithm isn't new it's been around this Annan's have been around since 1957 it was known as the perceptron back in the day and and one fascinating thing about neural networks is that they do more than just exceed on standard benchmark casts they capture the imagination of the public so we see New York Times articles about the great AI awakening or AI labs that want him to make the brain and they get a billion dollars from Microsoft and this isn't this isn't just a statement of the current time in 1958 there right after Rosenblatt published the original perceptron paper there was an article in The New York Times talking about the electronic brain that was teaching itself so this this the sense of neural networks mimicking the brain has been around for a long time and it's even permeated through our pop culture so this is a live one of my favorite movies Terminator 2 we're all fortunate ago says my CPU is a neural network processor a learning computer so even in fictional works no that works are the algorithm choice so so this is like so this is you know these are neural networks these are important algorithms and but these aren't the only algorithms that exist so let's look at the other side where we let's look at a very simple algorithm it's been around for much longer and but isn't used that much in machine learning but used quite a lot outside of machine learning so linear regression is simply the thing that you've done in since eighth grade math where you're just spitting lines - fitting a line to a set of points whether you're doing this in two dimensions or 100 dimensions they're still effectively doing some form of linear regression and it's the primary workhorse in many disciplines outside of machine learning so if you're doing if you're in epidemiology economics finance linear regression is a tool in your tool belt and this is much older than the perceptron it's been around since the 1800s it was introduced by Gaussian Legendre who it's attributed to it bumps back and forth and though there aren't flashing New York Times articles about linear regression linear regression has has been fun has been a core subroutine in humanity and some of humanity's greatest achievements so in the lunar in the Apollo missions the lunar module had a fundamental the fundamental stabilisation routine that was just based on the least squares regression which is it surprising if you know how prevalent linear regression is and every time you get a triangulation we had GPS it's solving a simple system of linear equations so linear regression is an algorithm that's used in many in many real world applications maybe not maybe not that much in machine learning so so this gives us like a try Asaf trade-offs so on one side we have deep neural networks which are the best tool for certain tasks but if anyone's worked with the neural network they know that they're exceeding complex and brittle like there are a lot of training and neural networks is a I would still say still somewhat of an art you need to know how to tune your learning rate you need to know how which architectures are important you need to know if batch nor if you need batch norm if you need residual connections so but if you want the state-of-the-art model for a vision task or an NLP toss these say to our algorithm will be based on a neural network on the other side we have something like linear methods so with this is a it's sufficient reliable it works because it's not really doing that much all it's doing is again fitting as fitting a line to a set of points but it's it doesn't really work for modern tasks so like that now do you like to think about is like the neural network is like an iPhone it has all these fancy features it can take pictures connect to the Internet and the Nokia is just a phone like I make phone calls at the front they can make big and both make phone calls but if you drop an iPhone it's gonna break yeah just an analogy I like to think about when I'm working with these algorithms so the central question in this talk is how can we use these linear methods to better understand our machine learning systems so and I'm gonna break this down into two two parts that I'm gonna bounce back and forth between and I'll explain why you little become clear in a few slides so one is that is this fundamental can you have linear methods that can max predictive performance of neural networks because if you can that tells us something about what neural networks are doing cuz if a linear method can get closed that means no networks aren't approximating the brain in any way because we know our intuition is that the brain isn't like a linear function and then the second thing is that do no networks fail in the same exact way is that linear methods fail so let's start with the first branch first so okay so this is the these two sides are the most technical slides so I'm just gonna breeze through them but if but if you have any questions feel free to stop me so the way linear regression generally works is you have you're gonna you're gonna you're gonna need to find some vector of weights data such that X data it is approximately equal to Y and the way to think about this for like a standard classification task is what we're going to do is try to find a line that that separates our data from with one side of examples and one and so like dogs in one side and catch the other so so the way we would do this is we would just regress our labels in the linear regression would be 0 & 1 so 0 would be dog one would be cat so on and so forth and then you would just solve this simple optimization problem which this is my favorite part military aggression we don't actually have to worry about any sort of optimization routine this is just something we can write in closed form so this is just you take some derivatives set it to zero and you get this equation but this is like not that interesting in my opinion because linear methods or their fundamental flaw is that they're linear so they can only draw these straight lines so if you if dogs and cats aren't separable and by a linear by a straight line then you're kind of hosed you want what you want to do is model fundamentally nonlinear relationships with something like a linear linear method so if you've if you've taken a machine learning class before 2010 you've probably heard of the kernel trick so the way this works is first we're gonna do this sleight of hand where what we're going to do is just assume there exists some function that makes our space linear so all I did is I took my last the equation of my last slide and replace X with Phi of X and then once I do this then I have a space where I have a space where cats and dogs are linearly separable now the question is how do i define this function that makes my space linearly separable and this is where the kernel trick comes in so the idea is because of the representative theorem the up we can change the optimization problem to be a function of this matrix K and K is going to be is going to be Phi Phi transpose and the actual slabs are right here doesn't matter all you all I need to know is you can you can rewrite the linear regression problem to with this matrix K and now K is just the similarity function between data points and your between all data points in your space so what you you've done is you instead of doing linear regression by coming up with some clever features you just have to come up with a clever distance function so or similarity function so if you can somehow come up with a function that takes in an image of a cat and dimension of a cat and gives a high value an image of a cat an image of a dog and gives a low value then you can separate cats and dogs in this space and this is just like the math that makes it work all right so so for the rest of the talk I'm just going to we're going to talk about how we come up with the similarity functions because these similarity functions are gonna be key in making these linear methods actually work for domain for these interesting domains that we care about so so that's the that's the underlying meeting bones on how we're gonna use linear regression but once we have this K everything else is just standard you just call like standard packages from dumb PI or side PI or remember okay so what we want to do is we want to compute the similarity between X and Z two data points so X and Z could be two cats two dogs two pieces of train strings two voice recordings and we want it we want a similarity function that's non linear so if you just have like tabular data so here are some like just simple mathematical kernel functions they can use so you can just take the linear similarity which is the dot product and this will just if you use the similarity function you're just gonna do linear regression again you're not gonna transform the space anyway you can do use the quadratic kernel which would just be level into if you've ever done regression by adding quadratic terms that's what the quadratic kernel does and then you can do the RBF kernel which is a very popular kernel that tricycle that tries to capture an infinite number of so wire whereas the quadratic only captures quadratic terms you can think of the RBF kernel captures quadratic cubic quartic and so on an infinite number of terms decaying in some way so these are simple kernels that people use for like tabular data if your data isn't something like images or text and does any structure and you're just going to do linear regression anyway then you can use this and turns out so if you if you have data that's like tabular so if you just have day like this turns out the colonel this colonel works quite well so this is a meta-study on 90 tabular data sets and we basically see that this RBF kernel does around as well as random forests and slightly better than any other network but this is sort of well known that which is community that if you have data that's like unstructured like tabular data you know networks don't really accept only perform well in this regime so the interesting thing is where machine learning is made all this fried to the last ten years is for structured data so my structured data talked about things like speech text and images right cuz like in once you have something like this you can't just you can't just vectorize you can't just think of it as a bag of numbers so here's here's an example that I like to use where let's say you have two two images that are that are just random noise and let's say I just one simple way is you can think of an image is just a vector where it's just a bag of numbers right this is a 32 by 32 pixel image with three colour channels so it's 30 72 numbers so I can take I can just vectorize this and take the RBF kernel value so ignore just think of this as a giant spreadsheet with 3072 columns and take the RBF kernel value between the two these two images and I get point nine nine seven I don't know what that means someone have a question which 1990 UCI data sets I get a these are all like it's like adult I don't have the exact list in my head I can it's in the source it's in the it's in that one paper I can I can pull it up after but they're mostly they're both continuous and discrete features and the they're all classification tasks okay so the so for these two images the RBF kernel is point nine seven nine nine seven and this doesn't actually tell me much but maybe it means they're really portal but let's say I apply a permutation map to both these images and turns out the image of the left it was a frog the image on the right becomes a truck but the RBF kernel value doesn't change because the RBF kernel value is invariant to these permutations so whether you scramble the pixels or you have the correct arrangement of pixels the kernel value is going to be the same so it's sort of ignoring the structure between the pixels which is why we need a better kernel function we need a better similarity function that does more than just think of think of our image as a bag of actor as a bag of numbers as a list of numbers okay so what we want is an image kernel we want something that takes an X an image z an image and given up and the really simple idea want to use and it's it ends up being very powerful is that we're just gonna compare some regions so I'm gonna use something I'm gonna take some regions and then just ignore destructor so the way this works is I'm just going to take two regions let's say so here I take a 6x6 region so now I'm just gonna look at 108 numbers so 6x6 region and I'm going to compare them with a simple kernel so like I'm just gonna throw away all structure in that in that 6x6 region and I'm going to compare them and that's going to give me some one value I'm just comparing these two regions and then what I'm going to do is just sum over all pairs of regions so this is kind of expensive but they're pretty efficient approximations to do this but now what I'm doing is effectively what I'm doing is just comparing all sub regions in these two images with this simple kernel and and then some something in the up so I get one value so the way to think about this is that there's three steps so there's a I have to concatenate and get a sub region then I have to compute a nonlinear compute a nonlinear interaction between these two sub regions and then after some the comparisons so I'm going to call this a convolutional kernel and it's going to be called a single layer convolutional kernel and the it's called a convolutional kernels because it's like this local pack price comparison has this convolutional structure to it and in fact you can actually write this as a convolution so if you want to efficiently run this on a GPU you end up writing this as a convolution so and I like writing this in this like sort of like network like diagram because people have seen deep networks represented as a series of operations so I'm going to think of this as concatenate compare and some right so now let's see if the horse dances does it doesn't work so so these are three like papers I wrote earlier in my PhD using using this method where we just saw these are just like applications where we just try to find applications of this algorithm so one was this transcription factor binding site detection algorithm the detection set problem where there was a DNA string and we have to predict whether it is a binary task of whether a particular protein will bind to that DNA string or not so just a binary task if we're given the string does this protein ATP f80 F P or whatever bind to this location and the way the way we did this we just we just thought of the representative string as if you're one image so you can just represent a CG in TS as basis vectors in in as 100 codings in R 4 and run the exact same algorithm and effectively wouldn't wrote this paper we found was this was on par or best slightly better than the state-of-the-art cons will still network for this task which we were quite surprised and it was like I think a thousand times faster the actual details of how it's faster and are in this paper but because this algorithm has a very efficient approximation which I'm not going to cover in this talk really I can talk about it offline in my head approximating these algorithms is a different is more of an engineering problem a different problem than actually just trying to see if these kernel methods are performant ok next this is a satellite image task where this is we work with the the the start-up in San Francisco called planet which can has access to terabytes of silent image salmon savagery and we wanted to see if we could predict a particular outcome from space in an efficient manner so so this is like if we want to predict population from just images of images of the ground and this isn't as useful in like the US but it's very useful in in if we were doing this in like Africa where there isn't good census data so an unpredicted forest cover and then again same thing here we compare to a resonant 50 because that I trained because since we collected this data there wasn't like a benchmark that we could just run so we just took one of the state-of-the-art networks not say they are but like a easy to train network that was good at this task Planet planta was the company and yeah so so yeah so the question was what's an ID image company is this maybe I'll do questions at the end because I guess it is sort of breaking the flow okay so yeah so again we saw that it's within striking distance of a ResNet and the whole point was we didn't try that hard this is a this is a very simple kernel function and it's like I would say comparable in performance and again our thing is much faster because we're using this efficient approximation and this is my favorite one of the tasks where we're trying to do is predict a solar flare by looking at picture of the Sun so Eric a postdoc I worked with now he's a professor University of Chicago had had this brilliant idea to NASA has these salad and these telescopes at this pointed the Sun and they're downloading terabytes of pictures of the Sun and what they want to do is one of the problems they want to do is like give it a picture of the Sun they want to predict whether a solar flow is gonna occur 24 or 2 hours in advance and so that's exactly what we did so we took a picture of the Sun and try to predict whether a solar flare was going to happen and here the baseline wasn't a neural network these were physicists so what they had was a set of handwritten features that were like diverging and curls and particular locations in this image that they new correlated with solar flares and we found that our conditional kernel captured all that and exceeded it and this is exactly the algorithm I talked about like four slides ago so all three of these tasks we just plugged and played this this convolutional algorithm and it worked pretty well and basically the high-level idea is like it's just a mechanic for a little bit of the structure in the input data and we get pretty far okay but this isn't a totally fair comparison because neural networks were sort of tuned not on these tasks but tuned on tasks like safar and nest and imagenet so we need to see how they do on these benchmark tasks so one of the most important one of these benchmark tasks is imagenet so if you are if you don't familiar with image net it's 1.2 million in training images 50k validation images there's like a bunch of different dog breeds animals objects and this is the data set that would say has single-handedly push the field forward in the in the last ten years dictionnaire Moloch is quoted as saying it's one of the most impactful papers in machine learning computer vision in the last five years because of progress that that resulted directly from this data set alex net now we have these large industrial labs at google AI Microsoft Amazon Facebook that that are that are pushing that are pushing the progress of AI because of progress on this data set and just last year in the economic report of the president there was a the first-ever chapter on AI and this chapter had progress on on image net as as figure one and it was just they just labeled it AI because they were just using progress on image net as a proxy for promising I so this is a very very important assets was it so even though it's kind of silly it's important we do gonna do well on it because it's it's sort of the measuring stick that everyone's using unfortunately it's it's very difficult to iterate on this data set because it's huge so there's another smaller in a set that is that again the person who who wrote Alex net and started the whole deep learning revolution worked on this data set first the farken it was introduced by Alistair Suzuki and these are so much smaller images blurry images there was only 10 classes but this is also a very very popular data set so for at at Europe's last year at Europe's basically the three most popular data sets are Amnesty farken and image net and M&S this sort of assault dataset like most classifiers can get above 99 quite easily so we're just going to look at Sephora image net so how do we do on image net unfortunately this is okay so this is the I got I made this plot around year two of my PhD and this is quite depressing so essentially there's like a forty percent gap between performance on image net versus performance versus like a resident so that's huge right that's like that's the difference between something to sort of working and not working at all kind of certainty and then on so far Ken we saw a smaller gap of 12% that's still significant that's like eight years of progress so we scratched her head and we were like what are the potential causes for this gap so this is like two years ago so what is that new networks are fundamentally better at this task and that's interesting to know on his own right but the second which was which would have been more interesting to us which was more interesting to us if it was true or like if this if this direction was destruction seemed more promising to us that neural networks actually overfit these these tasks because everyone's measuring progress on things like image net and so far Ken and these datasets have fixed test sets perhaps were just overestimate our accuracy and we're just over over fit to these tests so let's just see if this was true because if this is true then it doesn't really matter than your networks in front of them the better at the task if they're over fit so this is where we're going to switch to the second branch of the talk so basically we're gonna see if neural networks over fit your own happen layer methods over fit at the same right so what is the ideal machine learning workflow the ideal machine learning workflow is that you have a training set a balanced set and a test set so the way it works is you train a trainer model on a training set then you tune the model on the validation set and then the day before you deploy or the day before you the day before you submit your paper you compute the test accuracy on the test set and then you submit but this isn't what common learning is done at least in in academia and my understanding is this is how the best models were actually created what we do the way we've gotten our best model the way we we have these efficient nets and inception nets and resonates is that we download the best model that gets the best accuracy on a fixed asset then we tune that model by just looking at the accuracy and the test set and then once we can maximize that accuracy then we just release that model so we've looked at the test set over and over and over and over again which is theoretically a big no-no if you've taken an intermission learning class so now the question is because we looked at the test set over and over and over again do I have unreliable evaluations so like here's progress on Zafar Khan over the last ten years and all of these years use the exact same composite images so and there are probably tens of thousands evaluations on those ten thousand images over the last ten years same exact thing for image net so order fitting really could be a problem and this is what I would this is how I would describe overfitting like in a cartoon is that if you plotted tested accuracy of x-axis and tested accuracy on you on a new held-out test set on the y-axis well you would see is that over over a long period of time what's going to happen is that you're gonna start plateauing on the truly held out data whereas you're going to keep making progress on the test set that you've been tuning on so this is what we this is what we thought was happening so how we're going to do this how we're going to how we're going to test if this is happening the way we did this was we contacted the authors of the original these original data sets and constructed new test sets so this took around two years of our life so this is a group of us at at Berkeley where we constructed a brand new in it and a brand-new support can cassette and so and we try to make sure that these images were as close as possible to the test set that originally existed but the images that results are new close in distribution so we figured out how they set up the Mechanical Turk tough for image net for image net and how they labeled images for support now and then now now we can look at classifiers accuracy on image 2 and in that classifiers I couldn't image said me too and sort of the gap tells us how much it over fit in some sense or so we thought so this is the this is what we plotted after after creating the test set so let me explain this so on the x axis I have the accuracy on the original test set on the y axis I have the accuracy on this new test set that we created image net v2 so these images to be human eye look indistinguishable in terms of light there it'll be a dog on one sock on the image net me to a different type of dog and image net so you won't be able to tell if images came from is net vitor image net and we just measured a classifiers accuracy on both the both both test sets and plotted each blue point is one classifier so the blue point on the far left on the far right is like the state-of-the-art model when we made this plot so so this is this is I think this was like a want to say this was a resonant 152 or a dense and I don't remember the exact the exact model that was the same they are that this may be a se net doesn't matter so the what we see is that the best model drops around 10% but interestingly all models seem to be dropping around test 10% and more interestingly that the original the best models the original test set still say the best model in the new Tessa which isn't like what we thought was gonna happen basically what were we instead we thought we would get this like curve but all models on drop in accuracy so now we just made a harder cassette but okay but let's what we're actually looking for is overfitting and this doesn't seem to indicate that there's any sign of overfitting and then the interesting thing is that the kernel models also drop this much so so this sort of like at least on average and it doesn't seem like the image if there's any sort of overfitting or any sort of accuracy drop it seems like the neural networks and kernels are just as susceptible exact same exact same phenomenon so farken and and this is this is the thing I was talking about where what we expected is a thing on the right we'd expect that we thought we would see overfitting in that the original test accuracy would plateau and the new test act with respect to the new test accuracy but instead we saw the original test accuracy and every inch of progress we made the original tests actually translate into progress in a new test accuracy and it's even more dramatic than that neural networks actually see a smaller drop in accuracy for this fresh test set then the well then the new and the old Tessa for example if you take our kernel and the wide ResNet there were not there was a nine percent difference on so far ten if you take our kernel and wide resonate there was a fifteen percent difference when so far 10.1 that means the advantage between these between these methods was exaggerated on a on a held out fresh data which is like the opposite of the hypothesis that we that we had coming into this paper so essentially what like our takeaway from this paper that overfitting was surprisingly absent so our hypothesis was effectively wrong so over the last like even though these datasets are used for for over a decade the relative ordering is preserved so this is kind of good news in that the way we're doing machine learning is still fine the best model on imagenet is still the best model on a new slightly different image net and this has been a since then this has been backed up by numerous follow-up works and that's show this is also true for transfer learning someone replicated this 4m nest and then we wrote it we actually did this meta study using Kaggle where we did a masses of those graphs kernels were orange which graphs the the circled points are the the circle points of the kernel points o where the wide resonant and the yeah the wide resident is like here somewhere and the kernel point the kernels are like here somewhere yeah and then we also repeated this experiment there's a similar experiment on a hundred and twelve cattle competitions and effectively what we saw was that though there could be large changes in rankings for cattle competitions between a public leader board and a private leader board and you can think of the public leader board as the as the held that as the as a validation set they can tune on and the private leader board is it truly held that test set because you can only see it at the end well we what we saw was that your actual if you just look at the difference in accuracy it was always within noise or almost always within noise that and the noise depended on statistical fluctuations on the size of the test set so this doesn't mean that that the best the the best score if you're ranked 1 on the public leaderboard you'll be ranked 1 on the private leader board but if you're right one on a public leader board if you get accuracy 99% on the public leader board your accuracy won't drop to like fifty percent of the private leader board in most cases so this is we said this was another paper we said published at Europe's last year so after this these three papers we were quite convinced that it's pretty hard to do adapt overfitting in this like bad sense that you learn and like but this isn't all rosy distribution shift is still a real problem so like for both of these things we made us very small change in the test set right in that in that we just recently a test set but the actual images look very similar this is a very benign change this isn't like ever so examples and this small change was enough to cause a 10% drop in imagenet and like in 7% drop in so far 10 so it's around five to six years of progress so we just wiped away by creating a new test set and this is definitely gonna happen when you deploy machine learning models in production and they're gonna be worse than this because they're not gonna be we tried as much as possible to make the images make sure the images it so when we create an image net v2 we only took images from 2012 and 2013 because the image net original M is no data so it's constructed around that but there many other distribution shifts that you can't control for and you can get a much larger accuracy drop so our conclusion was that like this active drop was due a distribution shift and models are very very very susceptible to distribution shift and after this we wrote another paper where we created a created a sort of natural distribution shift that was more controllable where we just looked at video frames and we what we saw was that we can basically create a very similar phenomena by just taking a classifier evaluating it honest on a video frame and then evaluating on the worst of the nearby frames and even though the nearby frames are gonna look identical the classifier will make well you can drop the classifiers accuracy by like 20 percent so this is sort of like amber so examples except the images are just natural images so again this is just more more fuel to the fire and the distribution shifts are a real problem so take away from this we we try to show overfitting was a problem we failed we actually found the distribution shifts were a real problem we're the real problem and kernels were just as good and just as bad for distribution shift as neural networks which was surprising kind of is heartening when we did this but like that's how science works sometimes you don't always get the hypothesis that you want and then and then one final thing - to convincing the distribution for the real problem we also wrote a paper where we checked we for at least for the image net image net v2 example we took a group of five of us trained us on the image net classification task and made sure that our accuracies were the same between image net image net detail so like if we created a harder harder test set it's only harder for bottles humans perform around the same so this is the same plot as before but now we have these orange points which the humans and you see the orange points are near the dotted line which is the y equals excellent so if your human gets ninety five percent an image image net image that they get roughly 95 percent on the mission of v2 so which is good okay so again key takeaways or fittings not a problem mr. bishops a real problem 10 years of progress of neural networks is real ok so this brings us back to kernels may be neural networks are just fundamentally better than kernels at this task and that is a possibility but this might just be because we're just now like after doing all this well we learned is it all networks actually been doing like there's something fundamentally better about them right because like then then at least this one kernel that we were comparing the single area kernel and so we ruled out the second hypothesis so maybe networks are phenomenally better at this task so now the question is can we improve our kernel so the networks aren't fundamentally better and one thing that so after all this I just stared at a resident diagram and our kernel and I realized that there's a we're comparing apples and oranges the a very standard 34 layer of ResNet has 34 layers there's 34 none there's over 30 for 9 molarity x' there's many they're looking you're looking at many spatial scales and this is true for Minneapolis different domains - whether you're looking at a speech to a transformer or a speech network they're usually very hard whereas console kernel is three steps concatenate compare and some so in hindsight this is quite dumb that we didn't think about this we just turned our single area convolutional kernel into a multi-layered convolutional kernel yeah so we're just going to stack more layers just like we're gonna stack we could stack more layers for a network or stack more layers or the kernel the interesting thing is when you stack more layers for a for a network you're actually adding more learner balarama ters you're adding more knobs that SGD can train whereas when you stack more layers for a kernel you're just changing what this what this similarity function does so we're gonna do is we're gonna come catenate compare and do a partial sum then concatenate compare and partial sum and we repeat this until we get one value so a very similar idea except now it's just like we're gonna have just like a resident has hierarchical structure we're gonna have many steps and in the world of call this our multilevel spectrum so this actually took me four years just think understand that i could do this and this was a good idea and i guess it took the the segue to understanding the understanding that all this neural network progress is real to understand that like there's something fun fundamentally better about me all networks that that led me to coming up with this kind of hierarchical structure [Music] okay so the so the so the initial so the initial performance and so far can this is what we this is apply it said earlier the commercial kernel is around 12% worse right and so the white person has around 30 layers here and the complan kernel has only two so let's compare apples and apples so first let's compare a two layer CNN with the two layer kernel and we have to see that two layer CNN does worse than into where kernel which just might be because there's not enough learn double parameters for the network to learn but now what we can do is we can compare a five layer CNN with a five there colonel and we see there's a four percent gap now we compared ten layer CNN with a ten layer colonel we see there's a three percent gap this three to four percent varies so now we were we were at 83 before now we're at 88 and then now we can add some data augmentation which is like which is a very simple trick that again bringing techniques from neural networks to linear methods we can just add data augmentation to a kernel and now accuracy increases again so now we're around three percent difference again remember the wide ResNet was at 95 but now what I'm doing is I'm just constructing the CNN and the kernel at the same time so I'm comparing I'm doing apples to apples then what I can do is I can just add more data documentation I can add flips I can add crops I can cut out and then the accuracy of the CNN goes up to 96% unfortunately at this point you can't actually evaluate the kernel at this with all this data augmentation because this is still like this is like bleeding it was like misses like worked from those published this year I see well so this kernel is actually very expensive to evaluate so every time you add data augmentation increased amount of data set you're going to it's a quadratic dependence on the data set size so this is I'm working on this now but but the interesting thing is that are seeing like there's now if we only compare apples apples there's only like a 3% gap and now we've also improved our best kernel by 7% and this is like quite good for just a simple method that only has a deterministic similarity function and so this is what I'm working on and then again we did this on safari 100 very similar phenomena here where there is a 3% gap oh and another important thing is that I alluded the original Alex and accuracy and our kernel is now better than the original excellent accuracy so our kernel is better than the original neural network that sort of spurred all this progress but since then they've made ten years of progress but just catching up here was a lot of effort in its own then again we have similar results of safar 100 so it's a different dataset with the hundred classes and so then there's this holy girl of image dance so this is like my white whale of trying to I want to get good accuracy and image net before I graduate and I will I'm almost here I have like a month before I submit my thesis and these are experiments that I'm doing right now but basically there's originally this 40% gap but and again one functional images is very large in that it's hard to iterate even training a neural network takes around a week on imagenet if you want to try it out like close to city or marvel so what we did was we just sub sample the data set and looked at accuracies in that sub sampled regime and effectively what we saw was that again this iterative the kernel business works so taking the depth idea moving into linear regression works and now we can basically bridge the gap between us between a resident 50 and a kernel by just adding layers and this is also well known the layers have like a diminishing effect so the reason the resident 50 does well is because there's this residual connection that allows you to have identity layers so layers that do nothing so but like basically you see that a six layer kernel is like edging in on the performance of rs.150 and I actually improved these numbers this this ends up this ends up being true even if you go to ATK 160 K so I'm working on scaling this up to one fortunately and yeah so like basically this is the accuracy like so the accuracy trend as you scale them amount of samples is quite reliable so yeah I'm almost out of time but the main takeaway is that layer methods if you put enough elbow grease can be competitive for certain ml tasks so we can't ignore all those scientific tests they talked about earlier but and then layer methods can be further improved by borrowing successful techniques from deep neural networks so I did argumentation this depth idea even an idea of convolutions came from I got the idea from CN NS because you're adapting to the structure of the data you don't use you don't use CN NS on tabular you CNN's on image data and then finally this this other this other branch is that tested overfitting is not a huge problem for new networks upon your methods and distribution shifts are a huge problem for all methods and we should be thinking about the sugar shifts all the time they're very scary and the the way we were able to do all this is careful experimentation so these are all this is due to very careful methodological experimentations you only way we can find this phenomena we need better science like this and so none of this would be possible without all my collaborators so these are all the collaborators they've made all the work I've talked about possible and that's it thank you so much recording for the questions that folks ask questions right so I think we've got some questions in the chat so feel free to answer those and folks feel free to ask questions live okay thank you can I just have some quickie three slides ago on the the graph for the ten twenty percent where the y-axis was ten twenty percent what was that was that the correlation between kernel rock curacy on just 41 foundation 41 beta yeah you might I don't know you might like to plot it on a log existed sense yeah yeah cuz I the number is so though that I assumed that it has to be correlation because nobody would ever quote an accuracy of 10 percent so I would explicitly label it accuracy knowledge because I assumed it was correlation I mean this is accuracy yeah and so this is this is like this is just a common technique for models that we use for model selection where these models that are really good at 1.2 million are still our still most perform better sample complexity and are better even at 41,000 yeah no no I got the point I was just trying to understand what the y-axis was yeah sorry yeah I made this plot really quickly at the end because I got the spot the day I made my thesis talk so I did wanted a number the show I had some number no no sure it was totally awesome thinker assuming Karl met this reach parity in in time what would be the benefits of networks well so this is okay one is that if it's possible I think scientifically it's interesting just to know this is possible if we can get okay so if we can get kernel methods to reach parity and accuracy with the CNN like a ResNet then I think it's fundamentally possible to create a deterministic feature map and it's like does it look at your data that you don't need any training where you can just pass your data through it and you get this like feature representation that that that is the underlying feature representation of the kernel method and you can just do linear regression on that so it would if this was true if this conjecture is true it would speed up machine learning by like orders of magnitude because you never have to train a neural network because you can just scope you could use all the other optimization algorithms that work on a nominal networks because the reason we have to use SGD which is a fundamentally bad algorithm for optimization is because it seems to be the only algorithm that works well for training a neural network but if we can reduce this to a feature representation a deterministic each representation and a linear regression problem then we can just use something like l-bfgs or Newton's method or a variety of other method and converge much quickly so that's one example and the other thing is just like a lot there's a lot of tickets two techniques that exist in lexical literature from like the last 50 years that we can use for linear regression that we don't we're trying we're still trying to build analogs for for neural networks so like there are things like influence functions that tell you how different how important certain data points are like that you can they can just compute for manera that russian that you can't do for neural networks you can understanding like understanding like if you want to do rapid retraining of certain parts of your certain parts of your training set that's like very trivial to do with the with the with the linear method but fundamentally right now I'm just trying to see if this is like scientifically possible because this is just like a thing that I've been thinking about the last four years would it be fruitful to use analogous approaches or tabular methods well so things of tableau methods is that there aren't there isn't much structure to exploit so via now I think the thing is like I think for cobbler methods I really don't think you can you can beat like a next a good finally to to next you boost implementation but I'm not sure like so all the stuff comes from like using structure so if there's some structure in a tabular method perhaps and what was the big oak a big no complexity of finding each of the kernels I actually have a plot for this I don't have big oh but oh yeah I was thinking like when you showed like 40 K parameter accuracy you know if you can show how yeah what yeah it but I'm saying if you can plot it on the same series as the accuracy so then we can see that like 40 K parameters you know the accuracy ain't great but it's very cheap to compute oh you know right now right now nothing is right now nothing is cheap because these kernels are just a well in general and what's the Big O of of getting the 40 K the Big O is N squared d squared is to construct internal matrix and then it's NQ to compute the to compute the result to answer in in is number of parameters or the number of rows and as a number of data points and D is what D is the the size of the the size of the image so okay but that the number of Big O in terms of the number of parameters you don't so the number front that so the number of parameters in a kernel method is always going to be n by D so it's a nonparametric regression methods so there's like there's no lower complexity way of computing a car so there could be so the important the important thing is the the the lower bound of how fast you can approximate this is just a computer kernel exactly so the nice part is because the because the the kernel is a deterministic function because the kernel is a deterministic function there's a lot of approximations that are that you can do to compute the kernel function so for all the at for for all day scientific applications I talked about where the the Big O complexity was like M cubed where m is like some small number of parameters so M is like a thousand so you can choose an approximation to mention so here's a plot can you guys see my plot on my screen yet this plot is great and I was just talking about the lower left-hand quadrant of this sort of for very low accuracies of like point one point two if you can show the extension down to smaller yeah yeah so so I don't know so this is I've only made this plot for like training an entire dataset I don't know what so the that that image that yeah I think that imagenet plot is just like a network in progress thing I think we need to look at that we need to look at the the flops once we get the accuracies up to like the 70s which is where which is where ResNet is and I think that's possible is just like a bunch of engineering but the reason I wanted a labor on this is that so so the the main thing about computing a kernel is you have to solve this KX equals B equation and solving this equation is n cubed in terms of the number of data points so kernel methods always depend on the number of data points well optimally solving it is yet but you could yeah yeah but like a color wit or something yeah exactly but like even if you're solving it optimally the the number of floating-point operations you have to do is still less then the number of floating-point you do when you train a resident 52 convergence when you train a resident 52 convergence on a GPU so the important thing that we forget is that trainees at that works on modern GPUs is extraordinarily expensive but we have an extremely good tooling for it right now so you can't so the main reason you can't solve ax equals B on a GPU is because we don't actually have very fast out of GPU code for doing this that's like available on like that you can just like pip install whereas whereas for training a resident you can just download the latest version of Pi torch and that's that will give you that will reach this like lower bound whereas here I have to write my own solver to do this so I have done some work on like riding fast solvers to see this is like possible it's just like not very easy to use and like but if I can come up with a good kernel function I can make the optimization problem roughly as difficult as as training a resident but right now like the the hard part is like actually see the thing is like I don't even know if this is possible like maybe maybe as you maybe for these large data sets these neural networks are just like 50 10 20 30 % ahead I don't think that's true but I have to like convince myself that's not true how do we get here is takes non-optimal Sakura stick solutions to K X equals B in more efficient Big O you could you can yeah you could get heuristic solutions you can even you can use like coordinate descent or some sort of you're breaking up you can use something like porn in descent or some sort of hello can you hear me yeah sorry you broke up could you repeat the last sentence yeah you could use something like coordinate descent so I'm some sort of iterative algorithm but the problem there is what we found is that the exact solution just always had better test accuracy so just like if you want to get the best performance having the exact solution it was always the best this is also sort of true for training and network where like you need to optimize a network quite a bit to get the best test accuracy so yeah I'm not I don't really think the optimization problem is this KX equals B is the difficult part the hard part is actually figuring out what the correct K is which was the the bulk of the the bulk of the difficulty so like the bulk of the difficulty is just like figuring out how to do like figuring out how to do like right now I can only do things that are equivalent to cons values and average fulling but maybe there are more units that give you better performance and just constructing this is difficult right now because like what the kernel is is comparing all pairs of like sub sub images in a data set and that's just fundamentally expensive but is that a weight weighted sum no it's just like it's just it's literally just a it's just the sum of like the the way this kernel works is you take all if you have a data set of a million by million images you take all three by three patches compare compare them and then use some sum them up in a small way and then you do any of those comparison over and over again but there are no weights so that I'll grow them anymore it doesn't need to have any weights this and the reason it's you don't have too many weights is because it ends up like so like theoretically this couldn't ends up converging to if you have a neural network that's initialized as just gouchin and you make the neural network infinitely wide and just train the last layer then these these two algorithms converge the exact same solution solution and there's no there's no weights for the algorithm but you could add weights and you see the most what you think I actually don't know what the most impactful application of the multi-layer kernel is yet like when I'm currently what I think is there's a lot of applications where a single layer like there's a lot of applications that are going to look like this like there's a lot of applicants that are going to look like the genomics application or the the remote sensing application where you can just use the simplest thing and you would have extracted basically all the juice from the problem because the problem wasn't that hard to begin with and you can just like spend time doing other stuff like it's it's like the marginal value of getting like the extra point one point zero one R two might be the difference between accomplish McConnell and like something much more expensive so all of these use a very efficient version because it's one layer this one layer this one layer version is quite easy to approximate so if I'm doing this I can I can approximate this really quickly and I can do this on like a few seconds on a GPU whereas the multi layer thing ends up being quite expensive but that's that's because it's current research no there's no gradients I never have to take a single grade II when I'm doing any of this stuff because what I'm doing is I'm just solving the optimization problem directly so what I do is once they construct K then like so that was the point of this initial like the the whole point of visit like this initial section was that once I write k the optimize the the optimal solution the optimization is just this justice matrix inverse and I just compute that exactly so there's no gradient the hard part is just like constructing K can be very expensive or very cheap depending on how many layers you have just because of the nature of the computation my yeah my paper goes into it's called neural kernels without tangents it was recently accepted I say ml and those are the details of like why it's more expensive when you have more layers and we're working on it but then the reason part of the reason this is like this is hard this is bad right now is part partly engineering because it's like I'm the only person that looks like I have to come up with the algorithm and also write the kudo code to do this stuff so it ends up taking it's a long cycle of iteration but I haven't nailed down which parts are fundamentally slower and which parts are like which parts are fundamentally like better yet like coming up these is a lot of work is a lot of like tuning but once you have the kernel functions - deterministic thing yeah we can do some sort of explained ability that's I think that's that's yeah it's like that's like one of the one of the applications that you can do like cuz like you have a linear method and you could you can see what data points are important for the I want to briefly talk about some of your previous work with regards to overfitting yeah so like one of the hypotheses that people have put forth is that you know the over parametrization isn't really a problem because you know you're it's just you're essentially giving your algorithm a search space and then it's going and finding sort of a subset of of connections within that search space you know kind of analogous to the lottery ticket hypothesis mm-hmm I was wondering if you had sort of any thoughts or insights along those lines well I think well so I think this I think they're over fitting the overfitting hypothesis is sort of orthogonal to that in that this is this is fun beyond like the this distribution shift Lakha or setting thing is beyond just neural models so even if you take a simple linear regression model or a one nearest neighbor bottle which is this blue point down here right it's on this red line and it still drops ten percent so what what this means is that whatever phenomena is causing the accuracies to drop ten percent and keeping the ordering preserve is beyond what beyond is not specific to neural networks or or linear methods it's just something to do with the way we're doing our m is a lot is makes the way we're doing these like during your arm mixer makes our classifiers fundamentally brittle when the input distribution changes input distribution of images and so like and then so if you look at this so far things so what happens is like so I didn't actually plot this but so here our kernel models so here are some so you can there are some like Alex it would be like here and if when when we improved our kernel our kernel what it was better than Alex net but like it was also better than Alex set on the new test set so basically like all of the this phenomena seems to be invariant to whether you're talking about a very over parametrized neural network or a very skinny neural network or a just one nearest neighbor so I think yeah I'm not I'm pretty sure I've tested networks that came out of water to get head but this is like the the sparse networks and they also follow this red line so this seems to be some sort of universal phenomena about just like if you change the test distribution a little bit you're all your accuracy is either go up or down we actually created a different test set where the accuracies all went up so it's possible to go either direction we just got unlucky twice here yeah all right if you don't have any other questions let's all thank my shell once again for excellent talk and pull up your name nice question one yeah kind of kind of like it's just the same as previous but so when you mentioned that there's no resource in currently in optimizing finding the kernels you know is there any does anybody care I mean is there any doing that that's that's the problem right I spent a while I spent the first two years my PhD writing good solvers but then I realize no one really cares unless kernels work right that's what I'm sure like if if we assume the performance of kernel will always be worse than resident then why would people spend resource on on yes what that explain ability perhaps what because the explained ability is better like what's the the business case for why people would so that the the fundamental the concrete applications I can see why how this would be powerful is if I can match the performance of of a resident with the kernel method and come up with they come up with an efficient approximation for the constructing the kernel matrix which they do think is possible so it's just like step one show that the kernel can match the resonant once you can do that assuming compute is not a problem then trying to reduce the amount of compute is the follow-up problem which you can do because these kernel functions are actually just deterministic functions of inputs rather than like some complicate optimization trajectory you can actually come up with just state you'd the way to think about this you can think of you can come up with some a set of universal weights that that don't depend on your data and then you can just think of us are confident you don't have to train and you can just feed data through it and just train a linear model at the end and if you could do that then that would that would make deploying machine learning models and retraining machine learning models much more effective basically if you can if you can keep the performance of neural networks but then go back to training linear models tooling wise like the things you can do are insane in my opinion so but the problems were not very I think I think we're still probably like three four years out I'm not being true if it's true I have like I put like 60 percent odds that this is actually possible but that's true then if you could just basically have it would be like having your cake and eating it too so like if you could have the performance of a neural network but then have all the nice parts of a linear linear model why not but like again this is this is still like research so I'm guessing suppose like three to four years to come to fruition but then then we don't have to worry as much about whether like in but there's a lot time invested in tuning and training these neural networks that would you could just eliminate because a lot of the optimization problems convex a lot of these problems that are fundamental to neural networks goes away if you can reduce them to kernel methods yeah but like again several years away I think you step in for a great question any other questions No thank you very much again why Charlotte was awesome appreciate the talk and we have a pretty good schedule for the rest of the month of have Hagen pace coming up and