Transcript

well that's the koto drummers about 30 or 40 Japanese who live in a village on some island off the coast of Japan and preserve traditional Japanese music it's an unusual semi communal group they generally run about ten kilometers before breakfast which is served at five a.m. strange group wouldn't miss a concert for the world elderly alas don't seem to be coming down my to to to the Boston area very soon if you if you go to a concert from the koto drummers and you should and if you are no longer young you'll want to bring earplugs because as as we humans get older the dynamic range control in our inner ear tends to be less effective so that's why a person of my age might find some piece of music excruciating ly loud whereas you'll think it's just fine because you have better automatic gain control just like enough any kind of communication device there's a control on how intense the sound gets ah but I go off on a sidebar many of you have looked at me an astonishment as I drink my coffee and you doubtlessly been saying to yourself you know Winston doesn't look like a professional athlete but he seemed to have no trouble drinking his coffee so today's material is there going to be pretty easy so I want to give you the side problem of thinking about how it's possible for somebody to to do that how is it possible how did you make a computer program that could reach out it drink a cup of coffee don't want it a cup of coffee so that's one puzzle like it work out there's another puzzle to that puzzle concerns diet drinks this is a so-called diet coke that's right if you take a diet coke and ask yourself what would a dog think a diet coke is for that's another puzzle that you can work on while we go through the material of the day so this is our first lecture on learning and I want to spend a minute or two in the beginning talking about the lay of the land and then we'll race through some material on nearest-neighbor learning and then we'll finish up with a discussion with the advertised discussion of sleep because I know many of you think that because you're MIT students you're pretty tough and you don't need to sleep and stuff and we need to address that question the force before it's too late of the semester to to get back on track alright so here's the story now the way we're going to look at learning is that there are two kinds there's this kind and there's that kind and we're going to talk a little bit about both kinds the kind on the right is a regular is learning based on observations of regularity and computers are particularly good at this stuff and amongst the things that we'll talk about in connection with regularity based learning our today's topic which is nearest neighbors then a little bit downstream we'll talk about neural nets and then somewhere near the end of this segment we'll talk about boosting and these ideas come from all over the place in particular the stuff we're talking about today nearest neighbors is the stuff of which the field of pattern recognition it's the stuff of which pattern-recognition journals are filled this stuff has been around a long time does that mean it's not necessary that mean it's not good I hope not because that would mean that everything you learned in 1801 is not good because the same course was taught in 1910 so it's not it's been around a while but it's extremely useful and it's the first thing to try when you have a learning problem because it's the simplest thing you always want to try the simplest thing before you try something more complex that you will be less likely to understand so that's nearest neighbors and pattern recognitions and the custodians of knowledge about neural nets well this is sort of attempt to mimic biology and I'll cast a lot of calumny on that when we get down Erica talked about it and finally this uh this is the gift of the theoreticians so we and AI have invented some stuff we've borrowed some stuff we've stolen some stuff we've championed some stuff and we've improved some stuff that's why our discussion learning will reach around all these topics that's regularity based learning and you can think of this as the as the branch of bulldozer computing because when doing these kinds of things a computer is processing information like a bulldozer processes gravel now that's not necessarily good model for all the kinds of learning that we humans do and after all learning is one of the things that we think that characterizes human intelligence so if we're to build models of it and understand that we have to go down this other branch too and down this other branch we find learning ideas that are based on constraint now let's call this the human-like side of the picture and we'll talk about ideas that they enable for example one-shot learning where you learn something definite from each from each experience and we'll talk about explanation based learning by the way do you learn much by self explanation I think so an advisee once we've got nothing but A's and EPS and I said what are the subjects you get A's in and why don't you get a is in all of your subjects and he said oh I get A's in the subjects when I convince myself the material is true so the learning was a byproduct of self explanation some kind of important kind of learning but alas that's that's downstream and what we're going to talk about today is this path through the tree nearest neighbor learning and here's how it works in general there is or here's just a general picture of what we're talking about when you think of pattern recognition or nearest neighbor based learning you've got some sort of mechanism that generates a vector of features so we'll call this the feature detector and out comes a vector of values and that vector of values goes into a comparator of some sort and that comparator compares the feature vector with feature vectors coming from a library of possibilities and by finding the closest match the compare tour determines what the object what some object is it does recognition okay so let me demonstrate that with these electrical covers suppose they arrive on an assembly line and some robot wants to sort them how would it go about doing that well it could easily use a nearest neighbor sorting mechanism so how would that work well here's how it would work you would make some measurements and we'll just make some measurements in two dimensions and one of those measurements might be the total area including the area of the holes of these electrical covers just so you can follow what I'm doing without craning your neck you see if I can find the electrical covers yes now they are so we've got one big blank one several others so we might also measure the whole area and this one here this this guy here this big black one has no whole area and it's got the maximum amount of total area so it will find itself at that point in this space of features then we've got the guy here with room for four sockets in it that's got the maximum amount of hole area as well as the maximum amount of area so it'll be right straight up maybe up here then we have in addition to those two a blank cover like this it's got about half the total area than any other than any cover can have so put it right here and finally we've got one more of these guys oh yes this one half the whole area and half the total area so I don't know let's see where will I go maybe about right here so now our robot is looking on the assembly line and it sees something coming along and it measures the area and of course there's noise there's manufacturing variability so it won't be precisely on top of anything but suppose it's right there well it doesn't take any genius even our computer to figure out that this must be one of those guys with maximum area and maximum hole area but now let's ask some other questions where would where would a what would that be or what would this be and so on well we have to figure out what those newly viewed objects are closest to in order to do an identification but that's easy we just calculate the distance to all of those all those standard Platonic ideal descriptions of things and we find it I know which is nearest but in general it's a little easier to think about producing some boundaries between these various idealize places so that we can just say well which area is the object in and then we'll know it instantaneously to what category it belongs so if we only had to like the purple one and the yellow one it would be easy because we're just going to construct a line between the two with the line between the purple and yellow is a perpendicular bisector and so drawing it out instead of talking about it if there were only two that would be the boundary line anything south of the dotted line the purple and anything north would be yellow and now we can do this with all the points right so we can figure out Oh could you Pierre could you just close about cut please so if we want to do this with all these guys it would go something like this I better get rid of these dotted X's before they confuse me let's see we got if these were the only two points then we want to construct a perpendicular bisector between the line joining them and if these two are the only points I'd want to construct this for a particular bisector and if these two were the only points I want to construct a perpendicular bisector and if these two points we're the only ones involved I'd want to construct oh you see what I'm doing I'm constructing perpendicular bisectors and and those are exactly the those are exactly the lines that I need in order to divide up this space and it's going to divide up like this and I won't say we'll give you a problem like this on an examination but we have every year in the past had to divide up a space and produce what we would like to give something we would like to give a name you know Rumpelstiltskin effect when you have a name you get power over it so we're going to call these decision boundaries okay so those are the simple decision boundaries produced in a simple space by a simple idea but there is a little bit more to say about this because I've talked about this as if we're trying to identify something there's another way of thinking about it that's extremely important and that is this suppose I come in with a brand new cover never before seen and I only measure well let's say I only measure lets they only measure the whole area and the whole area is has that value what is the most likely total area well I don't know but there's a kind of weak principle of if something is similar in some respects it's likely to be similar in other respects so I'm going to guess if you hold a knife to my throat and back me into a corner that its total area is going to be something like that orange cover whole sole area so this is a contrived example I don't make too much of it but what I do want to make a lot of the of that first principle over there and that is the idea that if something is similar in some respects it's likely to be similar in other respects because that's what most of education is about fairytales legal cases medical cases business cases if you can see that they're similar in some respects to a situation you've got now and it's likely that they're going to be similar in other respects as well so when we're learning we're just not not just learning to recognize a category we're learning because we're attempting to apply some kind of precedent that's the story on that well that's a simple idea but that doesn't have any application the answer is sure well here's an example my second example the the example of cell identification suppose you have some white blood cells what might you do you might measure the total area of the cell and not the whole area but maybe the nucleus area and maybe you might measure four or five other things and put this thing in a high dimensional space you can still measure the nearness and a high dimensional space so you can use the idea to do that it works pretty well friend of mine once started to cut me based on this idea he got wiped out of course but it wasn't his fault what happened is that somebody had been in the Stane and was became much easier to just to the recognition by brute force so let's see huh that's two examples the introductory example of the holes of the electoral covers and the example of cells and what I want to do now is show you how the idea can reappear in disguise forms in areas where you might not expect to see it so consider the following problem you have a collection of articles from magazines and you and you and you're interested in learning something about how to address a particular question how do you go about finding the articles that are relevant to your question so this is this is a puzzle that has been studied for decades by people interested in information retrieval and here's the simple way to do it I'm going to illustrate once again in just two dimensions but it works and has to be applied in many many dimensions the idea is you count up the words and the articles in your library and you compare the word counts to the word counts in your probing question alright so there might be you might be interested in 100 words I'm only going to write two on the board for illustration so we're going to have we're going to think about articles from two magazines well first of all what words are we going to use one word is going to be hacked and that will include all derivatives of hack hacker hacking and so on and the other word is going to be computer and so it would not be surprising for you to see that articles from Wired magazine might appear in places like this they would involve lots of uses of the word computer and lots of uses of the word hack and now for the sake of illustration the second magazine from which we are going to draw articles is a Town and Country it's a very Toni magazine and the people who read Town & Country tend to be social parasites and they they still use the word hack because you can talk about hackings there's some sort of specialized term of art and dealing with horses so all the Town & Country articles would be likely to be down here somewhere and maybe there would be one like that where they talk about hiring some computer expert to keep track of the results of the data of the weekly hunts or something and now then you come with your probe and of course your probe question is going to be relatively small it's not going to have a lot of words in it so here's your here's your probe question here's your unknown which article is going to be closest which articles are going to be closest well alas all those Town & Country articles are closest so you can't use the nearest neighbor idea it would seem anybody got a suggestion for how we might get out of this dilemma yes oh brother using decision boundaries that our processors have you treated like wires and tons of geezers of this certain parties routers oh here we go we're going to use an including distance metric we're going to some other metric let me give you a hint let me give you a hint there all those articles up there out there and out there just for example and here are the Town & Country articles are out there and out there for example and now our unknown is out there and I got an idea now hey Brad what do you think let's be off there we go we're getting a horse biscuit the nectar is good so various different metric what we're going to do is we're going to forget about Euclidean distance and we're going to measure the angle between the vectors so the angle between the vectors well let's actually measure the cosine of the angle between the vectors and see how we can calculate that so we've take the cosine of the angle between the vectors we'll call it theta that's going to be equal to the sum of the of the unknown values times the article values those are just the values in various dimensions and then we'll divide that by the magnitude of the other vectors so we have will divide by the magnitude of U and we'll divide by the magnitude of the art vector to the article so that's just the dot product right that's a very fast computation so with a very fast computation you can see if these things are going to be in the same direction by the way if if this vector here is actually identical to one of those articles what will the value be well then the cosine will be zero and we'll get the maximum guy of the cosine which is one what if yeah that'll do it so if we use any of the articles to probe the article space they'll find themselves which is a good thing to have a mechanism do okay so that's just the dot product for those two vectors and it works like a charm it's not the most sophisticated way of doing these things there are hairy ways you can get a PhD by doing this sort of stuff in some new and sophisticated way but this is a simple way it works pretty well and you don't have to strain yourself much to implement it so that's cool that's an example where we have a very non-standard metric now let's see what else can we do how about a robotic arm control here we go here's we're going to just have a simple arm and what we want to do is we want to get this arm to move that ball along some trajectory at a speed velocity and acceleration that we become it so we've got two problems here well let's see we've got two problems because first of all we've got angles theta one and theta two it's a two degree of freedom arm so there are only two to two angles so the first problem we have is the kinematic problem of translating the XY coordinates of the ball the desired ones into the theta one theta two space that's simple kinematic problem no F equals MA there it doesn't involve forces or time or acceleration anything pretty simple but then we've got the problem of getting it to go along that trajectory at us you know with positions speeds and accelerations that we whether we desire and now you say to me well I've had 801 I can do that and that's true you care because it's Newtonian mechanics all you have to do is solve the equations there are the equations good luck why are they so complicated well because of the complicated geometry you notice we've got some products of theta 1 and theta 2 in there somewhere I think you got theta twos I see acceleration squared and yeah there's a theta 1 dot times theta 2 dot velocity times the velocity where the hell that come from I suppose be F equals MA right so the Coriolis force is because of this complicated geometry okay so you hire a Berthold horn or somebody to work these equations out for you and it comes up with something like this you try it out doesn't work why doesn't it work it's Newtonian mechanics I said it doesn't work because we forgot to tell bertholle there's friction and all the joints and we forgot to tell them that they weren't a little bit since yesterday and we forgot that the measurements we make on the lab table are not quite precise so people tried to do this and just doesn't work you know as soon as you get a ball of a different weight you have to start over it's gross so so I don't know I I can do this sort of thing effortlessly and I couldn't begin to solve those equations so let's see what we're going to do is going to forget about the problem for a minute now we're going to talk talking about building ourselves a gigantic table and here's what's going to be on a table and table theta1 theta2 theta3 whoops oh they're only two so that's theta one again but it's the Becht is the velocity angular velocity and then we have the accelerations so we're gonna have a big table of these things what we're going to do is we're going to give this arm a childhood and we're going to write down all the combinations we ever see every 100 milliseconds or something and the arm is just going to wave around like a kid does and a cradle and then we're not quite done because the two other things we're going to record and guess what they are they're going to be the torque on the first motor and the torque on the second motor and so now you've got a whole bunch of those records and the question is what are we going to do with it well here's what we're going to do with it we're going to divide this trajectory that we're hoping to achieve up into little pieces and there's a little piece and in that little piece nothing is going to change much there's going to be an acceleration velocity position and so we can look those up in at it in a table that we made in a childhood and we'll look around and find the closest match and this will be the set of values for the positions velocities and accelerations that are associated with that particular movement and guess what we can do now well we can say in the past the torques associated with that particular little piece of movement lie right there so we can just look it up now this method was thought up and rejected because computers weren't powerful enough and then this is the age of recycling right so the idea got recycled when computers got strong enough and it works pretty well there's things like this but you might say to me well going to do this stuff that we humans could do like this and the answer is let's look so this is the training phase it's going through his childhood you see what's happening is this the initial table won't be very good but that's okay because there are only a small number of things that it's important for you to be able to do so when you try those things it's still writing into the table so the next time you tried that particular motion it's going to be better at it because it's got better stuff to interpolate so monks in that table so that's why this thing is getting better and better as it goes in good as I was doing pretty good though I think there's just one thing I want to show you at the end of this clip it's just for fun maybe you've seen some old Zorro movies so here's a little setup where this thing has learned to use a lash so here's the lash and there's a candle down there so watch this pretty good don't you think so how fast is the learning take place let me go back to that other slides and show you so here here's some graphs to show you how fast that goes oh that gives you the curve of the purpose of how well the robot arm can go along a straight line after no practice with just some stuff recording the memory and then with a couple of practice runs that give it better better values amongst which to interpolate so that's I think that that's pretty cool so simple but yet so effective but you still might say well I don't know it might be something that can be done in special cases I wonder if Winston uses something like that when he drinks his coffee well we ought to do the numbers and see if it's possible but I don't want to use coffee it's the baseball season we're approaching the World Series we might as well talk about professional athletes so well let's suppose that this is a baseball pitcher and I want to know how much memory I'll need to record a whole lot of pitches is there a good pitcher these days the Red Sox suck so I don't that sucks clay Buckholtz I guess I don't know some pitcher and what we're going to do is we're going to say for each of these little segments we are going to record 100 bytes for joint and we you know we got joints all over the place I don't know how many are involved in doing a baseball pitch but let's just say that we have a hundred joints and then we have to divide the pitch up and do a bunch of segments so let's just say sake of argument that there are a hundred segments and how many pitches is a pitcher throw and day what a day yeah this we all know is about a hundred everybody knows that they take them out after about a hundred pitches so what I wanna know is how much memory we need to record all the pitches a pitcher pitches in his career so we still have to work on this a little bit more how many days a year does a pitcher pitch well they've got winter ball and that sort of thing so let's just approximate it as a hundred I know some of these may be a little high some of the others may be a little low and of course the career just to make things easy a hundred years so that's a one two three four five six so we have ten to the twelfth bytes is that hopelessly big to store in here 100 pitches in a day and we're going to record Chris was asking some detail what we're going to do is we report everything there is to know about one pitch and then we're going to see how many pitches he pitches in his lifetime and we're going to record all that okay so we want to know if this is actually a practical scheme and this by the way is cocktail conversation who knows right but it's useful to work out these numbers and know some of these numbers so question we have to ask is how many how much computation is in there and first question irrelevant to that is how many neurons do we have in our brain volunteer neuroscience no one but volunteer all right well this is a number you should this is a number you should know because this is what you got in there there are 10 to the 10th neurons in the brain of which 10 to the 11th are in the cerebellum alone what the devil do I mean by that I mean that your cerebellum is so full of neurons it Dwarfs the rest of the brain so if you exclude the cerebellum you've got about 10 to the 10th of neurons and there are about 10 to 11th neurons in the cerebellum alone what's the cerebellum for motor control hmm interesting so we're a little short oh but we forget that's just a number of neurons we have to count up the number of synapses because conceivably might be able to adjust those synapses right so how many synapses does a neuron have the answer is it depends but the ones in the cerebellum I should be pointing back there I guess 10 to the fifth so if we add all that up we have 10 to the 16th no problem it's just an existence proof you don't have to worry too much about having enough story so maybe our cerebellum functions in some way as a gigantic table and that's maybe how we learn motor skills by filling up that table as we run around emerging from the cradle learning how to manipulate ourselves as we as we go on so that's a story on unarmed control now all this is uh all this is pretty straightforward easy to understand and of course there are some there are some problems problem number one what if the space of samples looks like this what's going to happen in that case well what's going to happen in that case is that the let's see which values are going to be more important the X values right the Y values are spread out all over the place so you like the spread of the data to sort of be the same in all the dimensions so is there anything we can do to arrange for that to be true sure we could just normalize the data so we can borrow from our statistics course and say well let's see we're interested in X and we know that the variance of X is equal to 1 over N times the sum of the values minus the mean value squared that's a measure of how much the data spreads out so now instead of using X we can use X prime which is equal to 1 over Sigma the which is equal to X over Sigma what's the variance is that going to be x over Sigma sub X anybody see instantaneously what the variance are that's going to be what do we have to work it out everyone work at work out the algebra for me this is obvious it's simple just substitute ex-prime into this formula for the variance and do the algebraic highschool manipulation you'll see that the variance turns out now to be of this new variable this transform variable 1 so that problem the the non-uniformity problem the spread problem is easy to handle now what about that other problem no cake without flour what if it turns out that the data you have two dimensions and the answer actually doesn't depend on Y at all what will happen then you're going to get all your often I get screwy results because it will be measuring a distance that is merely confusing the answer right so problem number two is the is the what matters problem problem number three write it down what matters problem number three is what if the what if there what if the answer doesn't depend on the data at all then you got the note you've got they're trying to build a cake without flour once somebody asked me and a classmate of mine who went on to become an important executive and an important credit card company asked me if we could use artificial intelligence to determine when somebody was going to go bankrupt and the answer was no because the data available was it was data that was independent of that question so he was trying to bake a cake a flower you can't do that all right so that concludes what I want to say about nearest neighbors now I want to talk a little bit about sleep now over there on that left side branch now disappeared we talked about the human side of learning and I said something about one shot an explanation based learning and what that means is that you don't learn without problem-solving and the question is is how is problem-solving related how much sleep you get and that answer questions like that of course you want to go to the people who are the custodians of the kind of knowledge you're interested in and so you would say who are the custodians of knowledge about how much sleep you need and what happens if you don't get it and the answer is the United States Army because they're extremely interested in what happens when you cross ten or twelve time zones have no sleep and have to perform so they're very interested in that question and they got even more interested after the first Gulf War which was the most studied war in history up to that time because there were after-action reports that were full of examples like this the US forces in a certain part of the battlefield had drawn up for the night and those are Bradley fighting vehicles there and back here Abrams tanks and they're all just kind of settling down for a good night's sleep they've been up for about 36 hours straight by the way when much to their amazement across their field of view came a column of Iraqi vehicles and both sides were enormous ly surprised a firefight broke out the lead vehicle over here on the Iraqi side caught on fire so these guys in these Bradley fighting vehicles went around to investigate whereupon these guys started blasting away in acts of fratricidal fire and the interesting thing is that all these folks here swore in the after-action reports that they were firing straight ahead and what happened was their ability to put ordnance on target was not impaired at all their idea of where the target was what the target was whether it was a target was all screwed up so this led to a lot of experiments in which people were sleep-deprived and by the way you think you're tough MIT student right these are arming Rangers that it doesn't get any tougher than this believe me so what here's one of the experiments was performed in those days they had what they call fire control teams and their job is to take information from an observer over here about a target over here until the the artillery over here where to fire so they kept some of these folks up for 36 hours straight and after 36 hours they all said we're doing great and at that time they were bringing fire down on hospitals mosques churches schools and themselves because they couldn't do the calculations anymore after 36 hours without sleep and now you say to me well I'm an MIT student I want to see the data so that's how I look at the data okay so there goes that's what happens to you after 72 hours without sleep these are simple things to do simple things to very simple calculations have to in your head like adding numbers spelling words and things like that so after 72 hours without sleep your performance relative to what you were at the beginning is about 30% so loss of sleep destroys ability sleep loss accumulates so you say well I needed hours of sleep and I what you need by the way berries but I'm going to get by with seven hours of sleep so after 20 days one hours worth of sleep deprivation you're down about 25% if you say well I only need I need eight hours of sleep but I'm gonna have to get by with just six after twenty days that you're down to about 25% of your original capability so you might say well this caffeine help our naps naps in this case and the answer is yes a little bit some people argue that you get more effect out of the sleep that you do get if you divide it into two Winston Churchill always took a three hour nap in the afternoon he said that way he got a day and a half's worth of work out of every day he got the full amount of sleep but he divided into two pieces here's the caffeine one so caffeine does help but now you say well shoot you know I think I'm going to take it kind of easy this semester and I'll just work hard during the week before finals maybe I'll go twenty would bother sleeping up for the 24 hours before the 603 for file it's okay well let's see what will happen let's work the numbers here's 24 hours and that's where your effectiveness is is after 24 hours now let's go over to the same amount of effectiveness on the blood alcohol curve and it's about the level at which you would be legally drunk so I guess what we ought to do is check everybody as they come into the 603 for final and arrest you if you spend 24 hours without sleep and not like to take any finals again for a year so if you do all that you might as well to get drunk and now we have one thing left to do today and that is addressed the original question of why it is that all the dogs and cats in the world think that the diet drink makes people fat what's the answer it's because only fat guys like me drink this crap so since the dogs and cats don't have the ability to tell themselves stories don't have that capacity to string together events into narratives they don't have any way of saying well this is a consequence of desiring not to be fat not a quenched consequence of being cut they don't have that story and so what they're doing is something had to be very careful about and that thing you have to be very careful about is the confusion of correlation with cause they see the correlation but they don't understand the cost so that's why they make a mistake you