Tom Mitchell: Welcome to machine learning. Tom Mitchell: How did we get here? Tom Mitchell: I'm Tom Mitchell, your podcast host. Tom Mitchell: Now many people ask, how did we get to this point where today we Tom Mitchell: have these amazing AI systems? Tom Mitchell: I have a one sentence answer to that question.
Tom Mitchell: We tried for fifty years to Tom Mitchell: write by hand intelligent Tom Mitchell: programs, but we discovered Tom Mitchell: about a decade ago that it was Tom Mitchell: actually much easier and much Tom Mitchell: more successful to use machine Tom Mitchell: learning methods to instead Tom Mitchell: train them to become Tom Mitchell: intelligent. Tom Mitchell: So the real question is, how did machine learning get here?
Tom Mitchell: What were the successes along the way and the failures? Tom Mitchell: Who were the people involved? Tom Mitchell: What were they thinking? Tom Mitchell: What even made them want to get Tom Mitchell: into this field in the first Tom Mitchell: place? Tom Mitchell: This first episode will set the stage for the podcast.
Tom Mitchell: It is a recording of a lecture I gave this month in February Tom Mitchell: twenty twenty six at Carnegie Mellon University, and it Tom Mitchell: attempts to cover in one hour a seventy five year history of the Tom Mitchell: field of machine learning.
Tom Mitchell: Most of the rest of the episodes Tom Mitchell: in the podcast involve Tom Mitchell: interviews with various pioneers Tom Mitchell: in the field, who made very Tom Mitchell: significant contributions along Tom Mitchell: the way. Tom Mitchell: Before we start, I want to thank Carnegie Mellon University and Tom Mitchell: also the Stanford University Digital Economy Lab for Tom Mitchell: supporting the podcast. Tom Mitchell: And I want to thank Maddie Smith, our podcast producer.
Tom Mitchell: I hope you enjoy the podcast. Tom Mitchell: If we're going to talk about Tom Mitchell: machine learning, it's only fair Tom Mitchell: to start with the first people Tom Mitchell: who talked about how on earth is Tom Mitchell: learning possible? Tom Mitchell: Which were the philosophers? Tom Mitchell: And so as early as Aristotle, he was talking about the question Tom Mitchell: of how is it that people could look at examples of things and Tom Mitchell: learn their general essence?
Tom Mitchell: In his words, about a century later, there was a school of Tom Mitchell: philosophers called the Pyrrhonists, who really zeroed Tom Mitchell: in on the problem of induction and how it can be justified. Tom Mitchell: When we say induction, what we Tom Mitchell: really mean is the process of Tom Mitchell: coming up with a general rule Tom Mitchell: from looking at specific Tom Mitchell: examples.
Tom Mitchell: And so they talked about Tom Mitchell: questions like, well, if all of Tom Mitchell: the swans we've seen so far in Tom Mitchell: our life are white, should we Tom Mitchell: conclude that all swans are Tom Mitchell: white? Tom Mitchell: What would be the justification for that? Tom Mitchell: Maybe there's a black swan out there that we haven't seen. Tom Mitchell: And, uh, that debate went on for Tom Mitchell: some time around thirteen Tom Mitchell: hundred.
Tom Mitchell: William of Ockham, uh, suggested Tom Mitchell: something that we now call Tom Mitchell: Occam's razor, the policy that Tom Mitchell: we should prefer the simplest Tom Mitchell: hypothesis. Tom Mitchell: So, indeed, if all the swans we've seen so far are white, Tom Mitchell: then the simplest hypothesis is all swans are white. Tom Mitchell: That was his prescription.
Tom Mitchell: Later on, around sixteen hundred, Francis Bacon brought Tom Mitchell: up the importance of data collection, of actively Tom Mitchell: experimenting, to collect data that could falsify hypotheses Tom Mitchell: that weren't correct. Tom Mitchell: And then in the seventeen hundreds, the philosopher David Tom Mitchell: Hume really kind of nailed the problem of induction.
Tom Mitchell: He argued very persuasively that it's really impossible to Tom Mitchell: generalize from examples if you don't have some additional Tom Mitchell: assumption that you're making. Tom Mitchell: And he pointed out that even the assumption that the future will Tom Mitchell: be like the past is itself not a provable assumption is just a Tom Mitchell: guess that we use. Tom Mitchell: So his point was that people do induction, but it's a habit.
Tom Mitchell: It's not a justified, rational, provable, correct process. Tom Mitchell: So they had plenty to say around the nineteen forties when Tom Mitchell: computers became available. Tom Mitchell: Alan Turing, who's often called Tom Mitchell: the father of computing, uh, Tom Mitchell: suggested that maybe computers Tom Mitchell: could learn.
Tom Mitchell: He said instead of trying to produce a program to simulate Tom Mitchell: the adult mind, why not rather try to produce one which Tom Mitchell: simulates a child's? Tom Mitchell: If this were then subjected to Tom Mitchell: an appropriate course of Tom Mitchell: education, one would obtain the Tom Mitchell: adult brain. Tom Mitchell: So he had the idea that maybe computers could learn.
Tom Mitchell: But he did not have an algorithm by which they would learn that Tom Mitchell: waited until the nineteen fifties, when there were two Tom Mitchell: important seminal events. Tom Mitchell: One was a computer program Tom Mitchell: written by an IBM researcher Tom Mitchell: named Art Samuel, and his Tom Mitchell: program learned to play Tom Mitchell: checkers. Tom Mitchell: I'll just read you a couple Tom Mitchell: sentences from the abstract of Tom Mitchell: this paper.
Tom Mitchell: He said two machine learning procedures have been Tom Mitchell: investigated in some detail using the game of checkers. Tom Mitchell: enough work has been done to Tom Mitchell: verify the fact that a computer Tom Mitchell: can be programmed so that it Tom Mitchell: will learn to play a better game Tom Mitchell: of checkers than can be played Tom Mitchell: by the person who wrote the Tom Mitchell: program.
Tom Mitchell: And then he went on to point out Tom Mitchell: the principles of machine Tom Mitchell: learning verified by these Tom Mitchell: experiments are, of course, Tom Mitchell: applicable to many other Tom Mitchell: situations. Tom Mitchell: So he had really one of maybe Tom Mitchell: the first demonstration of a Tom Mitchell: program that learned to do Tom Mitchell: something interesting.
Tom Mitchell: And he understood that the Tom Mitchell: techniques he was using were Tom Mitchell: very general. Tom Mitchell: Now, how did he get the computer to learn to play checkers? Tom Mitchell: His program learned an Tom Mitchell: evaluation function that would Tom Mitchell: assign a numerical score to any Tom Mitchell: checkers position, and that Tom Mitchell: score would be higher, the Tom Mitchell: better the checkers position Tom Mitchell: was.
Tom Mitchell: From your point of view as you're playing the game, and Tom Mitchell: then you would use that to control a search. Tom Mitchell: A look ahead search for which move to proceed to take that Tom Mitchell: evaluation function was a linear weighted combination of board Tom Mitchell: features that he made up. Tom Mitchell: Things like how many checkers are on the board that are mine, Tom Mitchell: how many are on the board that are yours, and so forth.
Tom Mitchell: So his program learned. Tom Mitchell: What it learned was that evaluation function. Tom Mitchell: How did it learn it? Tom Mitchell: By playing games against itself. Tom Mitchell: And he points out that in eight to ten hours, it could learn Tom Mitchell: well enough to beat him. Tom Mitchell: Those ideas persisted through the decades.
Tom Mitchell: They became reused over and over, including in the computer Tom Mitchell: programs that finally beat the World Chess Champion and the Tom Mitchell: World Backgammon Champion and the World Go champion. Tom Mitchell: So those ideas were really seminal.
Tom Mitchell: A second thing that happened in Tom Mitchell: the fifties was the invention of Tom Mitchell: the first early version of Tom Mitchell: neural networks by Frank Tom Mitchell: Rosenblum, wrote, I'm sorry, Tom Mitchell: Frank Rosenblatt from Cornell, Tom Mitchell: and he was interested in Tom Mitchell: neuroscience. Tom Mitchell: How can the brain neurons in the brain be used to learn?
Tom Mitchell: And he ended up building a simple, uh, at least by today's Tom Mitchell: standards, simple neural network that consisted of, uh, one layer Tom Mitchell: of neurons where, uh, there would be a receptive field, uh, Tom Mitchell: input, say an image, and then the neurons would respond to Tom Mitchell: that and produce an output set of neuron firings.
Tom Mitchell: What got learned in that case Tom Mitchell: were the connection strengths Tom Mitchell: between the input to the neuron Tom Mitchell: and the probability that it Tom Mitchell: would fire. Tom Mitchell: And the way he trained it was Tom Mitchell: what we now call supervised Tom Mitchell: learning. Tom Mitchell: You show an input and and what the output should be. Tom Mitchell: And he had schemes for updating those weights to fit the data.
Tom Mitchell: Now that the importance of this Tom Mitchell: work is that it catalyzed a Tom Mitchell: whole bunch of work in the Tom Mitchell: nineteen sixties, for the next Tom Mitchell: decade, looking at different Tom Mitchell: algorithms for tuning the Tom Mitchell: weights of perceptron style Tom Mitchell: systems.
Tom Mitchell: That work proceeded for a Tom Mitchell: decade or so, and at the end of Tom Mitchell: the nineteen sixties, two MIT Tom Mitchell: scientists, Marvin Minsky and Tom Mitchell: Seymour Papert, wrote a book Tom Mitchell: called perceptrons.
Tom Mitchell: But unfortunately, that book Tom Mitchell: proved that a single layer Tom Mitchell: perceptron, which is the only Tom Mitchell: thing we knew how to train at Tom Mitchell: that point, uh, could never even Tom Mitchell: represent any many, many Tom Mitchell: functions that we wanted to Tom Mitchell: learn. Tom Mitchell: It could only represent linear functions, not even, uh, Tom Mitchell: exclusive or, you know, where the input could be. Tom Mitchell: The output would be one.
Tom Mitchell: If input one is a one and the other is a zero, or if it's a Tom Mitchell: zero and a one. Tom Mitchell: But the output would have to be zero if they were both one. Tom Mitchell: You can't even represent that Tom Mitchell: simple function with a Tom Mitchell: perceptron no matter how you Tom Mitchell: train it. Tom Mitchell: So this really kind of put the Tom Mitchell: kibosh on work on perceptrons, Tom Mitchell: uh, following the publication of Tom Mitchell: this book.
Tom Mitchell: Now, if we're not going to be able or don't want to spend our Tom Mitchell: time figuring out how to learn perceptrons, Then what's next? Tom Mitchell: Well, it turned out one of Tom Mitchell: Minsky's PhD students, Patrick Tom Mitchell: Winston.
Tom Mitchell: The next year published his Tom Mitchell: thesis, and Winston suggested Tom Mitchell: that instead of learning Tom Mitchell: perceptron type representations Tom Mitchell: of information, we should learn Tom Mitchell: symbolic descriptions. Tom Mitchell: And so his program, uh, in his thesis, he showed how his Tom Mitchell: program could learn descriptions of different physical structures Tom Mitchell: like an arch or a tower.
Tom Mitchell: And he would train the program by showing it line drawings of Tom Mitchell: positive and negative examples of, uh, in this example arches. Tom Mitchell: And then the program would process those incrementally Tom Mitchell: arriving examples to produce a symbolic description that would Tom Mitchell: describe the different parts and relations among them.
Tom Mitchell: For example, an arch could be two rectangles which don't touch Tom Mitchell: each other, but which jointly support a roof of any shape. Tom Mitchell: So this was an important step Tom Mitchell: because it shifted the focus Tom Mitchell: onto learning a much richer kind Tom Mitchell: of representation, symbolic Tom Mitchell: descriptions. Tom Mitchell: And this became the new paradigm Tom Mitchell: which dominated the nineteen Tom Mitchell: seventies.
Tom Mitchell: So during the seventies, there Tom Mitchell: were a number of people working Tom Mitchell: on learning symbolic Tom Mitchell: descriptions. Tom Mitchell: My favorite is the metaphor program, developed by Bruce Tom Mitchell: Buchanan at Stanford. Tom Mitchell: This program, again, was a symbolic learning program.
Tom Mitchell: What it learned was rules that would predict how molecules Tom Mitchell: would shatter inside a mass spectrometer, and therefore Tom Mitchell: predict what the mass spectrum of a new molecule would be. Tom Mitchell: And those rules again described, Tom Mitchell: Symbolically described a Tom Mitchell: subgraph of atoms within the Tom Mitchell: molecular graph.
Tom Mitchell: And the rules would say, if you find this subgraph, then Tom Mitchell: specific bonds in that subgraph are likely to fragment when you Tom Mitchell: put this in a mass spectrometer. Tom Mitchell: And this was an important step forward. Tom Mitchell: I asked Bruce Buchanan, how will it work? Tom Mitchell: What was this program able to do in terms of did it work. Bruce Buchanan: Well for one small class of steroid molecules, the keto and Bruce Buchanan: estranes, if you will?
Bruce Buchanan: Uh, we had, uh, fewer than a Bruce Buchanan: dozen spectra, and we were able Bruce Buchanan: to tease out the rules that Bruce Buchanan: determine, uh, How a new keto Bruce Buchanan: androstane would fragment in a Bruce Buchanan: mass spectrometer, and we were Bruce Buchanan: able to publish that set of Bruce Buchanan: rules in a refereed chemical Bruce Buchanan: chemical journal, Chemistry Bruce Buchanan: Journal.
Bruce Buchanan: Sorry. Bruce Buchanan: Uh, and it was, to our Bruce Buchanan: knowledge, the first time that Bruce Buchanan: the result of a machine learning Bruce Buchanan: program, Symbolic Learning, had Bruce Buchanan: been published, uh, in a Bruce Buchanan: refereed journal. Tom Mitchell: So that was an important milestone for machine learning, Tom Mitchell: really, the first time that a program discovered some Tom Mitchell: knowledge that was useful enough to get published in that domain.
Tom Mitchell: Now it turned out personal note Tom Mitchell: I was a PhD student at Stanford Tom Mitchell: at the time, and Bruce became my Tom Mitchell: PhD advisor, so my PhD thesis Tom Mitchell: was also built around, this same Tom Mitchell: data set.
Tom Mitchell: And for my thesis I developed a system called Version Spaces Tom Mitchell: that was the first symbolic learning algorithm where you Tom Mitchell: could prove that it would converge, and furthermore, that Tom Mitchell: the learner would know when it had converged, so it would know Tom Mitchell: it was done.
Tom Mitchell: And it did that by maintaining Tom Mitchell: not just one hypothesis that it Tom Mitchell: would modify, but by keeping Tom Mitchell: track of every hypothesis Tom Mitchell: consistent with the data that it Tom Mitchell: had seen. Tom Mitchell: And this also opened up the possibility of what we call Tom Mitchell: today active learning. Tom Mitchell: It made it easy for the system Tom Mitchell: to play twenty questions with Tom Mitchell: the teacher.
Tom Mitchell: Uh, it could ask the teacher, please label this example so Tom Mitchell: that in a way, uh, it could reduce the set of hypothesis as Tom Mitchell: quickly as possible. Tom Mitchell: So by the end of the seventies, there seemed to be enough work Tom Mitchell: going on in the field that it was time to hold a meeting.
Tom Mitchell: And so we organized the first Tom Mitchell: workshop in machine learning was Tom Mitchell: held here at CMU at Wayne Hall, Tom Mitchell: a couple of buildings that Tom Mitchell: direction, and it was organized Tom Mitchell: by Jaime Carbonell, who was an Tom Mitchell: assistant professor here at the Tom Mitchell: time.
Tom Mitchell: Richard Michalski, who is a more Tom Mitchell: senior professor at Illinois and Tom Mitchell: myself, I was at the time an Tom Mitchell: assistant professor at Rutgers Tom Mitchell: University. Tom Mitchell: And so we held this meeting, pulled together some people. Tom Mitchell: One of the people who attended was a student of Richard Tom Mitchell: Michalski named Tom Dietterich.
Tom Mitchell: And Tom went on to make many Tom Mitchell: contributions in the field of Tom Mitchell: machine learning. Tom Mitchell: And so I asked Tom, what was the field like in nineteen eighty? Tom Dietterich: I'd say it was really chaotic. Tom Dietterich: you know, I was, Tom Dietterich: attended that very first machine Tom Dietterich: learning workshop that was Tom Dietterich: organized.
Tom Dietterich: I think you were one of the core Tom Dietterich: organizers at CMU, and there Tom Dietterich: were probably thirty people in Tom Dietterich: the room and, uh, and probably Tom Dietterich: thirty completely different Tom Dietterich: talks. Tom Dietterich: You know, I remember, I was talking Tom Dietterich: about I had done, a sort of algorithm comparison paper Tom Dietterich: that I published at Ijcai seventy nine, I think.
Tom Dietterich: So just before that workshop, in which I was, by Tom Dietterich: hand executing these very simple algorithms for this kind of Tom Dietterich: subgraph learning problem, uh, and comparing how many subgraph Tom Dietterich: isomorphism calculations they had to do.
Tom Dietterich: But it was like the first Tom Dietterich: attempt to actually compare Tom Dietterich: multiple machine learning Tom Dietterich: algorithms that were more or Tom Dietterich: less trying to do the same Tom Dietterich: thing. Tom Dietterich: There were a couple of them there, and, you Tom Dietterich: know, I think John Anderson was there talking about, you Tom Dietterich: know, cognitive models.
Tom Dietterich: You were there talking about Tom Dietterich: the beginnings of EBL and the Tom Dietterich: Lex system for, for, Tom Dietterich: calculus, symbolic Tom Dietterich: integration. Tom Dietterich: You know, I remember the most interesting talk I Tom Dietterich: thought was Ross Quinlan's talk on, on ID3, where he was Tom Dietterich: trying to take these reverse numerated chess endgames Tom Dietterich: and learn decision trees.
Tom Dietterich: That would completely, Tom Dietterich: exactly losslessly, Tom Dietterich: basically compress those Tom Dietterich: giant tables into a small Tom Dietterich: decision tree. Tom Dietterich: A really important thing people should understand in those days Tom Dietterich: was we believed there was a right answer for our Tom Dietterich: machine learning problems.
Tom Dietterich: And we would, Tom Dietterich: it would often happen that I Tom Dietterich: would run like the algorithms Tom Dietterich: and it would not get the right Tom Dietterich: answer. Tom Dietterich: It would not get the, the logical expression that we Tom Dietterich: thought was the right answer. Tom Dietterich: It would get something that was really, actually equally Tom Dietterich: accurate on the training data.
Tom Dietterich: And actually it worked Tom Dietterich: pretty well although we Tom Dietterich: didn't really have a set idea of Tom Dietterich: a separate test set in those Tom Dietterich: days. Tom Dietterich: I mean, it was not a field of statistics. Tom Dietterich: It was, the idea was right.
Tom Dietterich: We were coming out of the, really the John McCarthy program Tom Dietterich: of programs with common sense, which didn't have a lot to do Tom Dietterich: with common sense, but was about we're going to represent Tom Dietterich: everything in logic, and we're going to use logical inference Tom Dietterich: as the execution engine. Tom Mitchell: So there's Tom's take on what things were like.
Tom Mitchell: He mentioned that he thought the most interesting talk was Tom Mitchell: Ross Quinlan's talk. Tom Mitchell: I agree, I thought that was the most interesting talk. Tom Mitchell: Ross's talk presented the idea Tom Mitchell: that we should learn decision Tom Mitchell: trees.
Tom Mitchell: A decision tree is something where you classify your example Tom Mitchell: by putting it at the root of the tree, and then you sort it down Tom Mitchell: to a leaf in the tree based on its features, and the leaf tells Tom Mitchell: you what the output classification label should be. Tom Mitchell: That's what get learned. Tom Mitchell: What gets learned? Tom Mitchell: So I asked Ross how he came up with this idea. JR Quinlan: I had done a PhD under a psychologist, Earl hunt.
JR Quinlan: And part of his work involved decision trees, which I learned JR Quinlan: about, of course, as a student, but then put in the back of my JR Quinlan: mind for fifteen years or so. JR Quinlan: And then I was at at Stanford on JR Quinlan: sabbatical at the same time as JR Quinlan: Donald.
JR Quinlan: Mickey was teaching a course on learning, and he had a challenge JR Quinlan: for the class on which, you know, I sat in on the class and JR Quinlan: the challenge was to work out a way of predicting a win in JR Quinlan: a very simple chess end game. JR Quinlan: King rook versus king knight. JR Quinlan: So I remembered Earl Hunt's work on decision trees, and I JR Quinlan: thought, well, maybe that would be the way to go.
JR Quinlan: So I developed a thing called ID3, which was just a simple JR Quinlan: decision tree program. JR Quinlan: No pruning, just straight decision tree. JR Quinlan: And then, uh, that that seemed JR Quinlan: to solve the problem pretty JR Quinlan: well, up to about ninety five JR Quinlan: percent. JR Quinlan: And then I got that up to one hundred the next year. JR Quinlan: And then remember, the first real time I talked about this JR Quinlan: was at that conference.
JR Quinlan: You organized the workshop in nineteen eighty at Pittsburgh, JR Quinlan: at Carnegie Mellon. JR Quinlan: You, Richard and Hymie all, all set up that workshop. JR Quinlan: And then I gave a talk on, uh, decision tree learning. Tom Mitchell: So there's Ross's story.
Tom Mitchell: He he got the idea of decision Tom Mitchell: trees from his thesis advisor Tom Mitchell: many years earlier, but it turns Tom Mitchell: out Ross was the one who came up Tom Mitchell: with the algorithm that actually Tom Mitchell: successfully discovered useful Tom Mitchell: decision trees. Tom Mitchell: And that whole idea of decision tree learning became very Tom Mitchell: important in the field.
Tom Mitchell: By twenty ten, it was probably Tom Mitchell: the one of the most commercially Tom Mitchell: used approaches in machine Tom Mitchell: learning. Tom Mitchell: So in the early eighties, there were various experiments like Tom Mitchell: these trying to build machine learning systems, but really no Tom Mitchell: theory, no theory that could tell us, for example, how many Tom Mitchell: examples would we have to present to a learner in order Tom Mitchell: for it to reliably learn?
Tom Mitchell: And that changed in nineteen Tom Mitchell: eighty four, when Les Valiant Tom Mitchell: published a paper on what he Tom Mitchell: calls probably approximately Tom Mitchell: correct learning. Tom Mitchell: And the idea is it really Tom Mitchell: was the first practical theory Tom Mitchell: to tell us how many examples you Tom Mitchell: would need.
Tom Mitchell: And it in particular, in Tom Mitchell: particular, the number of Tom Mitchell: examples you need depends on Tom Mitchell: three things. Tom Mitchell: The complexity of your hypothesis space. Tom Mitchell: For example, if you're going to learn decision trees of depth Tom Mitchell: two, that's a lot less complex than if you're learning decision Tom Mitchell: trees of depth twelve.
Tom Mitchell: So the it depends on how complex Tom Mitchell: your hypotheses are, depends on Tom Mitchell: the error rate you're willing to Tom Mitchell: tolerate in the final Tom Mitchell: hypothesis. Tom Mitchell: One percent error five percent error. Tom Mitchell: It also depends on the probability you're willing to Tom Mitchell: put up with that. Tom Mitchell: If you do choose that many Tom Mitchell: random randomly provided Tom Mitchell: training examples.
Tom Mitchell: The probability that you'll still fail. Tom Mitchell: You can't guarantee that you Tom Mitchell: won't fail, but you can reduce Tom Mitchell: that probability. Tom Mitchell: So this was a breakthrough in the area of theoretical Tom Mitchell: characterization of algorithms. Tom Mitchell: So I asked I asked les what he thought was the key idea there. Leslie Valiant: It's a it's a kind of a model of computation.
Leslie Valiant: But it yeah, it makes sense Leslie Valiant: because it's got some Leslie Valiant: applications.
Leslie Valiant: So that's the particular result which persuaded Leslie Valiant: people that there was something there is this result Leslie Valiant: that if you take a conjunctive normal form formula, Leslie Valiant: which, you know, from NP completeness at the time, we Leslie Valiant: already knew there's some hardness in it, because if Leslie Valiant: someone gave you the formula was computationally difficult to Leslie Valiant: find out whether it's a null, it's the equivalent of formula
Leslie Valiant: which, is always zero, which is never satisfiable. Leslie Valiant: On the other hand, this was Leslie Valiant: kind of this, uh, conducting Leslie Valiant: normal form formula with three, Leslie Valiant: variables in each Leslie Valiant: clause. Leslie Valiant: Uh, so this was PAC learnable. Leslie Valiant: And so this was a bit striking that something which is very Leslie Valiant: hard is learnable.
Leslie Valiant: But then this, this Leslie Valiant: highlighted the difference Leslie Valiant: between, uh, computing and uh, Leslie Valiant: and learning because so with the Leslie Valiant: learning model, the idea was Leslie Valiant: that there was a distribution of Leslie Valiant: inputs. Leslie Valiant: And you learned from this distribution, but you only have Leslie Valiant: to be good on this distribution when you have to predict.
Leslie Valiant: So if, for example, in this formula, there were some very Leslie Valiant: rare ones which are so very rare, then the learner wouldn't Leslie Valiant: have to know about that. Leslie Valiant: So in this sense this was easier than the NP completeness. Tom Mitchell: So I was actually quite surprised at that answer. Tom Mitchell: What he's saying.
Tom Mitchell: Put another way is that what was Tom Mitchell: really interesting there is that Tom Mitchell: for this one kind of hypothesis, Tom Mitchell: conjunctive normal form, which Tom Mitchell: is a way of it's a kind of Tom Mitchell: logical expression. Tom Mitchell: If your hypotheses are of that form, then it's easier to learn Tom Mitchell: them than it is to compute them.
Tom Mitchell: When he says compute them, what he means is the cost of Tom Mitchell: answering the question, can you find a positive example of this? Tom Mitchell: And it was known at the time that the computational cost of Tom Mitchell: answering that question, is there a positive example of this Tom Mitchell: formula was exponential in the size of the formula?
Tom Mitchell: And then he discovered that Tom Mitchell: learning a formula, if somebody Tom Mitchell: gives you a positive and Tom Mitchell: negative examples only takes Tom Mitchell: polynomial less than exponential Tom Mitchell: time. Tom Mitchell: So I agree with him that that's Tom Mitchell: a fascinating theoretical fact, Tom Mitchell: but that would not be the answer Tom Mitchell: I would give about why this Tom Mitchell: revolutionized the field of Tom Mitchell: machine learning.
Tom Mitchell: It revolutionized the field, in my view, because he was the Tom Mitchell: first person, really to be able to come up with a framing, a new Tom Mitchell: framing of the machine learning problem that even allowed this Tom Mitchell: kind of theoretical analysis.
Tom Mitchell: In particular, his framing Tom Mitchell: included assumptions like the Tom Mitchell: training data would come from Tom Mitchell: some source that would give you Tom Mitchell: that would give you random Tom Mitchell: examples according to some Tom Mitchell: probability distribution. Tom Mitchell: And then later, when you wanted to test your hypothesis on new Tom Mitchell: data, you would get more random examples from that same source.
Tom Mitchell: And so he reframed the problem Tom Mitchell: in a way that made theory Tom Mitchell: possible. Tom Mitchell: The consequence of that was he Tom Mitchell: catalyzed a huge amount of Tom Mitchell: theoretical work in machine Tom Mitchell: learning and continues this day Tom Mitchell: just keeps branching further and Tom Mitchell: further. Tom Mitchell: There are conferences specifically designed to cover Tom Mitchell: theoretical computer science.
Tom Mitchell: So the eighties was really a very generative decade. Tom Mitchell: There are a lot of things going on. Tom Mitchell: Another thing was going on was some people were looking at Tom Mitchell: human learning and how that might inspire our models of AI Tom Mitchell: and machine learning. Tom Mitchell: One such effort was here at CMU Tom Mitchell: by Alan Newell and his two PhD Tom Mitchell: students, John Laird and Paul Tom Mitchell: Rosenbloom. Tom Mitchell: They took the approach of.
Tom Mitchell: They built a system they called Tom Mitchell: Soar, which was really one of Tom Mitchell: the first AI agents designed to Tom Mitchell: capture the full breadth of what Tom Mitchell: humans do play games, solve Tom Mitchell: problems many different tasks, Tom Mitchell: so they frame their machine Tom Mitchell: learning problem as one of Tom Mitchell: getting a general agent to Tom Mitchell: learn.
Tom Mitchell: And their architecture had very interesting properties that I Tom Mitchell: think are relevant today. Tom Mitchell: Now that agents are again a topic of hot activity, I won't Tom Mitchell: go into the details, but in the podcast there's an interview Tom Mitchell: with John Laird who goes into detail on this. Tom Mitchell: Another item that can't be Tom Mitchell: overlooked in the eighties was Tom Mitchell: really the rebirth of neural Tom Mitchell: network.
Tom Mitchell: Remember, in the end of sixties, Tom Mitchell: Minsky and Papert published that Tom Mitchell: book that killed off work on Tom Mitchell: perceptrons? Tom Mitchell: Well, in the mid eighties, Tom Mitchell: finally, people came up with an Tom Mitchell: algorithm that could train not Tom Mitchell: just one layer perceptrons, but Tom Mitchell: multilayer perceptrons. Tom Mitchell: And that allowed learning Tom Mitchell: functions that were highly Tom Mitchell: non-linear.
Tom Mitchell: And Dave Rumelhart, J. Tom Mitchell: McClelland and Geoff Hinton were Tom Mitchell: three of the ringleaders of this Tom Mitchell: effort. Tom Mitchell: So I asked Geoff about that period. Tom Mitchell: Now we're up to the mid eighties Tom Mitchell: when really neural nets are Tom Mitchell: reborn. Tom Mitchell: Is that the right word? Tom Mitchell: How would you. Geoffrey Hinton: Backprop with backpropagation? Geoffrey Hinton: I mean, we didn't invent it.
Geoffrey Hinton: Invented by several different Geoffrey Hinton: groups, but we showed that it Geoffrey Hinton: really worked to learn Geoffrey Hinton: representations. Geoffrey Hinton: And as you know, sort of one of the big problems in AI is how do Geoffrey Hinton: you learn new representations? Geoffrey Hinton: How do you avoid having to put them all in by hand?
Geoffrey Hinton: And my particular example, Geoffrey Hinton: which was the family trees Geoffrey Hinton: example, where you take all the Geoffrey Hinton: information in some family Geoffrey Hinton: trees, you convert it into Geoffrey Hinton: triples of symbols like John has Geoffrey Hinton: Father Mary. Geoffrey Hinton: And then you train a neural Geoffrey Hinton: net to predict the last term in Geoffrey Hinton: a triple. Geoffrey Hinton: Given the first two terms.
Geoffrey Hinton: So it's just like the big language models. Geoffrey Hinton: You're predicting the next word given the context. Geoffrey Hinton: It's just much simpler.
Geoffrey Hinton: I had one hundred and twelve Geoffrey Hinton: total examples, of which one Geoffrey Hinton: hundred and four training Geoffrey Hinton: examples and eight were test Geoffrey Hinton: examples, which is a bit less Geoffrey Hinton: than the trillion examples they Geoffrey Hinton: have nowadays, Geoffrey Hinton: but it was the same idea. Geoffrey Hinton: You convert a symbol into a feature vector.
Geoffrey Hinton: You then have the feature vectors of the context interact Geoffrey Hinton: via a hidden layer. Geoffrey Hinton: They then predict the features Geoffrey Hinton: of the next symbol, and from Geoffrey Hinton: those features you guess what Geoffrey Hinton: the next symbol should be, and Geoffrey Hinton: you try and maximize the Geoffrey Hinton: probability of predicting the Geoffrey Hinton: next symbol.
Geoffrey Hinton: And you then backpropagate Geoffrey Hinton: through the feature interactions Geoffrey Hinton: and through the process of Geoffrey Hinton: converting a symbol into Geoffrey Hinton: features. Geoffrey Hinton: And that way you learn feature vectors to represent the Geoffrey Hinton: symbols and how these vectors should interact to predict the Geoffrey Hinton: features of the next symbol. Geoffrey Hinton: And that's what these big language models do.
Tom Mitchell: So there's Jeff in the mid Tom Mitchell: nineteen eighties work on Tom Mitchell: backpropagation. Tom Mitchell: Another personal note in Tom Mitchell: nineteen eighty six, while this Tom Mitchell: was going on, I came to spend a Tom Mitchell: year at CMU as a visiting Tom Mitchell: professor. Tom Mitchell: And I got to meet Allen Newell at the time. Tom Mitchell: And Allen said, hey, do you want to team teach a course?
Tom Mitchell: We'll teach a course on Tom Mitchell: architectures for intelligent Tom Mitchell: agents. Tom Mitchell: And of course I said yes. Tom Mitchell: The opportunity to teach with Allen. Tom Mitchell: And he said, by the way, there Tom Mitchell: will be another, uh, an Tom Mitchell: assistant professor working with Tom Mitchell: us. Tom Mitchell: The three of us will team teach it. Tom Mitchell: That's Geoff Hinton.
Tom Mitchell: So Allen, Geoff and I team Tom Mitchell: taught in spring of nineteen Tom Mitchell: eighty six. Tom Mitchell: Uh, this course was one of the best experiences of my career up Tom Mitchell: to that point. Tom Mitchell: And so it was a large part of the reason why I ended up Tom Mitchell: staying at CMU. Tom Mitchell: But when I came, I was here Tom Mitchell: for about a year, and then Jeff Tom Mitchell: moved on.
Tom Mitchell: He moved up to the University of Toronto and started Tom Mitchell: building up a group there. Tom Mitchell: One of the people who joined his group was a person named Yann Tom Mitchell: LeCun, who went on to win the Turing Award jointly with Jeff Tom Mitchell: and Yoshua Bengio for their work in neural networks. Tom Mitchell: So I asked Jon about this period.
Yann LeCun: And then, mid nineteen Yann LeCun: eighty seven, I moved to Toronto Yann LeCun: to do a postdoc with Jeff, and I Yann LeCun: completed this, the Yann LeCun: simulator. Yann LeCun: Jeff thought I was not doing Yann LeCun: anything because I was just Yann LeCun: basically hacking, you know, all Yann LeCun: the time, Yann LeCun: and this, this system was kind of Yann LeCun: interesting because we had to build a front end language to Yann LeCun: interact with it.
Yann LeCun: And that language was the Lisp Yann LeCun: interpreter that Leon and I Yann LeCun: wrote. Yann LeCun: And so we're using Lisp, even though as a front end to kind of Yann LeCun: a neural net simulator. Yann LeCun: And I, you know, implemented Yann LeCun: a weight sharing, abilities Yann LeCun: and all that stuff and started Yann LeCun: experimenting with what became Yann LeCun: convolutional nets.
Yann LeCun: You know, when I was a postdoc in Toronto, early nineteen Yann LeCun: eighty eight, roughly, and started to get really good Yann LeCun: results on, you know, very simple shape recognition, like, Yann LeCun: yhandwritten characters that had drawn with my mouse or Yann LeCun: something like that.
Yann LeCun: Right. Tom Mitchell: So, as you just heard, Yann was Tom Mitchell: experimenting with can we apply Tom Mitchell: neural networks to the problem Tom Mitchell: of character recognition, Tom Mitchell: written characters. Tom Mitchell: People were experimenting with many different uses of neural Tom Mitchell: nets at the time. Tom Mitchell: My favorite, the one I would vote application of the decade Tom Mitchell: was done in the area. Tom Mitchell: Surprisingly, of self-driving cars.
Tom Mitchell: There was a PhD student here at CMU named Dean Pomerleau. Tom Mitchell: He trained a neural network Tom Mitchell: where the input was an image Tom Mitchell: taken by a camera looking out Tom Mitchell: the front windshield of a Tom Mitchell: vehicle. Tom Mitchell: And the output of the neural Tom Mitchell: network was the steering command Tom Mitchell: telling the car which direction Tom Mitchell: to steer. Tom Mitchell: So I asked Dean about that work.
Tom Mitchell: How much training data did you have? Dean Pommerleau: So the interesting thing was, to Dean Pommerleau: begin with, it was all batch Dean Pommerleau: training. Dean Pommerleau: So I'd drive, I'd have a person drive the vehicle along Schenley Dean Pommerleau: Park, uh, Flagstaff Hill Path, and then I would go off and Dean Pommerleau: crunch it overnight. Dean Pommerleau: But in the end, what we were Dean Pommerleau: able to do is, uh, real time Dean Pommerleau: learning.
Dean Pommerleau: So one drive up the hill with a Dean Pommerleau: human behind the wheel steering Dean Pommerleau: and the neural network, learning Dean Pommerleau: to pair images with camera Dean Pommerleau: images with the steering command Dean Pommerleau: that the human was giving was Dean Pommerleau: able to, uh, train it in about Dean Pommerleau: five minutes to, uh, take over Dean Pommerleau: and steer on its own from there Dean Pommerleau: on, on that road and on similar
Dean Pommerleau: roads. Dean Pommerleau: So it was one of the first real time, real world vision Dean Pommerleau: applications of, uh, of artificial neural networks going Dean Pommerleau: beyond just Flagstaff Hill, you know, the little paths on there. Dean Pommerleau: And we went out on, on real roads first through the golf Dean Pommerleau: course, Schenley Golf Course, on the, uh, on the road there.
Dean Pommerleau: And then we, we went on, you know, the local highways, in Dean Pommerleau: fact, the longest as part of my PhD, the longest trip we did Dean Pommerleau: was, I think, about one hundred miles at the time from basically Dean Pommerleau: up, uh, I-79 from Pittsburgh all the way up to Erie. Dean Pommerleau: Uh, and it drove basically the, the whole way. Dean Pommerleau: So it and it was getting up to fifty five miles per hour after Dean Pommerleau: we got a faster vehicle.
Tom Mitchell: It turns out he didn't ask for permission. Tom Mitchell: So so this was all happening in the nineteen eighties. Tom Mitchell: Really, it was a decade of Tom Mitchell: amazing invention and innovation Tom Mitchell: and exploration. Tom Mitchell: Another important thing that Tom Mitchell: happened in that decade was the Tom Mitchell: development of reinforcement Tom Mitchell: learning.
Tom Mitchell: The way to understand that is to first realize that supervised Tom Mitchell: learning was the kind of standard way of framing the Tom Mitchell: machine learning question. Tom Mitchell: When Dean talked about training Tom Mitchell: his system, he would input an Tom Mitchell: image. Tom Mitchell: He had people drive the car, so he got a lot of training Tom Mitchell: examples of the form. Tom Mitchell: Here's the image and here's the correct steering command.
Tom Mitchell: So he could tell the neural network for this input. Tom Mitchell: Here's the correct output. Tom Mitchell: That's called supervised learning. Tom Mitchell: But reinforcement learning reframes the problem. Tom Mitchell: It takes into account that sometimes we don't know what the Tom Mitchell: right output is.
Tom Mitchell: For example, if you're learning to play chess, you might not Tom Mitchell: have a person who tells you at every step given this board Tom Mitchell: position, here's the right move. Tom Mitchell: Instead, you might have to wait until the end of the game after Tom Mitchell: you've made many moves to get the feedback signal that says Tom Mitchell: you lost or you won, and then you have to figure out what to Tom Mitchell: do about that because you actually took many moves.
Tom Mitchell: So that's what reinforcement learning is about. Tom Mitchell: And Rich Sutton and Andy Barto were instrumental in kind of Tom Mitchell: framing that problem and, and working on it. Tom Mitchell: They recently won the Turing Award for this work. Tom Mitchell: So I asked Rich how Tom Mitchell: reinforcement learning fit into Tom Mitchell: the field.
Rich Sutton: The field of machine learning Rich Sutton: has always been been dominated Rich Sutton: by the more straightforward Rich Sutton: supervised approach. Rich Sutton: There was, as I mentioned at the very beginning, Rich Sutton: the rewards and penalties were were very much a part of it.
Rich Sutton: But then the, focus, as Rich Sutton: things became more clear and Rich Sutton: more better defined and it Rich Sutton: became more clear, learning Rich Sutton: problem then became pattern Rich Sutton: recognition and supervised Rich Sutton: learning. Rich Sutton: And, this fellow, the strange, uh, fellow Harry Klopf, Rich Sutton: recognized this more than other people and Rich Sutton: wrote some reports and ultimately a book, saying Rich Sutton: that something had been lost.
Rich Sutton: And Andy Barta and I picked up on his work and Rich Sutton: and eventually realized that he was right, that something had Rich Sutton: been left out, and in some sense it was obvious that something Rich Sutton: had been left out. Rich Sutton: From the point of view of Rich Sutton: psychology, where I'd been Rich Sutton: studying how animals learn and Rich Sutton: animals learn.
Rich Sutton: Really in both ways, in both a Rich Sutton: supervised way and a Rich Sutton: reinforcement way. Rich Sutton: And so, we picked up on that and made that into a well Rich Sutton: defined area in the. Rich Sutton: When was that? Rich Sutton: That would have been in the eighties. Rich Sutton: And then finally, you wrote a book on it in ninety eight. Rich Sutton: So then it became a clear, uh, subfield of machine learning.
Rich Sutton: Yeah. Rich Sutton: But the key thing is why is why why is I the way I say it to Rich Sutton: myself is that why is reinforcement learning off? Rich Sutton: Why is it powerful? Rich Sutton: Potentially powerful. Rich Sutton: It's powerful because it's learning. Rich Sutton: It's really learning from experience. Rich Sutton: Learning from the normal data Rich Sutton: that an animal or a person would Rich Sutton: get.
Rich Sutton: And it doesn't require a Rich Sutton: prepared special data like you Rich Sutton: of course do in supervised Rich Sutton: learning. Tom Mitchell: So during the eighties, there were a lot of other really Tom Mitchell: interesting things going on. Tom Mitchell: Uh, people experimenting with Tom Mitchell: the idea that maybe machines Tom Mitchell: should learn by simulating Tom Mitchell: evolution.
Tom Mitchell: There was an entire set of conferences on something called Tom Mitchell: genetic algorithms, genetic programming, which had to do Tom Mitchell: with that sort of thing. Tom Mitchell: Uh, a cluster of work on Tom Mitchell: studying human learning and Tom Mitchell: other areas. Tom Mitchell: But we don't have time for all of those.
Tom Mitchell: Let's move on to the nineteen Tom Mitchell: nineties, when, again, there was Tom Mitchell: a, I would say, a sea change in Tom Mitchell: terms of the style of work that Tom Mitchell: went on. Tom Mitchell: The theme of the nineteen nineties was really the Tom Mitchell: integration of statistical and probabilistic methods into the Tom Mitchell: field of machine learning.
Tom Mitchell: And a lot of that took the Tom Mitchell: grounded form of learning a new Tom Mitchell: kind of object, which people Tom Mitchell: called either graphical models Tom Mitchell: or Bayes. Tom Mitchell: Bayes nets. Tom Mitchell: But what got learned in that Tom Mitchell: case was, again, a network where Tom Mitchell: each node would represent a Tom Mitchell: variable. Tom Mitchell: For example, maybe you would be interested in predicting whether Tom Mitchell: somebody has lung cancer.
Tom Mitchell: You'd make that a variable and maybe you'd have evidence like Tom Mitchell: are they a smoker? Tom Mitchell: Do they have a normal or abnormal X-ray result? Tom Mitchell: You'd make those variables. Tom Mitchell: And then the edges in the graph represent probabilistic Tom Mitchell: dependencies among the variables in a way such that in the end, Tom Mitchell: the whole graph represents the full joint probability Tom Mitchell: distribution over the entire collection of variables.
Tom Mitchell: So that's what got learned and how it got learned. Tom Mitchell: Waited for some algorithms to be discovered.
Tom Mitchell: One of the key people who was Tom Mitchell: involved in inventing those Tom Mitchell: algorithms, although Judea Tom Mitchell: Pearl, came up with the idea of Tom Mitchell: how to represent these, Tom Mitchell: Daphne Kohler, a professor at Tom Mitchell: Stanford, was one of the most Tom Mitchell: active researchers in terms of Tom Mitchell: designing algorithms for Tom Mitchell: learning these. Tom Mitchell: So I asked her, why do we need graphical models?
Daphne Koller: Graphical models, for me, emerged by realizing that the Daphne Koller: problems that we needed to solve to address most real world Daphne Koller: applications went beyond. Daphne Koller: You have a vector representation Daphne Koller: of an input and a single, Daphne Koller: oftentimes binary or at best Daphne Koller: continuous output. Daphne Koller: There was so much more opportunity to think about Daphne Koller: richly structured environments, richly structured problems.
Daphne Koller: So even if you think about problems like understanding what Daphne Koller: is in an image, that's not a single label problem of there is Daphne Koller: a dog, because images are complex and there's Daphne Koller: interrelationships between the different objects you want it to Daphne Koller: get beyond the yes no. Is there a dog in this image to something Daphne Koller: that is much more rich?
Daphne Koller: There's a dog and a Frisbee and Daphne Koller: a beach and three kids building Daphne Koller: a sandcastle. Daphne Koller: You have a rich input and a rich output. Daphne Koller: Thinking about these richly Daphne Koller: structured domains gave rise to Daphne Koller: we have to think about multiple Daphne Koller: variables.
Daphne Koller: We have to think about the Daphne Koller: interactions between those Daphne Koller: variables and leverage that Daphne Koller: structure both in our input and Daphne Koller: output space in order to get to Daphne Koller: much better conclusions and deal Daphne Koller: with problems that really Daphne Koller: matter.
Tom Mitchell: So this work on training Tom Mitchell: graphical models was really part Tom Mitchell: of a bigger theme that decade, Tom Mitchell: which was just the integration Tom Mitchell: of statistical methods with what Tom Mitchell: had been pretty much statistics Tom Mitchell: free machine learning up to that Tom Mitchell: point. Tom Mitchell: Another person who was Tom Mitchell: instrumental in that was Tom Mitchell: Berkeley professor named Mike Tom Mitchell: Jordan.
Tom Mitchell: I asked him about the Tom Mitchell: relationship between statistics Tom Mitchell: and machine. Michael I. Jordan: So anyway, by the time I moved to wanted to move to Berkeley, I Michael I. Jordan: was realizing that I was missing the whole statistics community, Michael I. Jordan: that, uh, it was just separate from machine learning, as maybe Michael I. Jordan: you kind of remember, there was occasionally a little leakage, Michael I. Jordan: but it was way too separate.
Michael I. Jordan: And and nowadays we're often seeing, you know, people will Michael I. Jordan: run a machine learning method, but then it's not calibrated. Michael I. Jordan: It's not, you know, has bias and all that. Michael I. Jordan: And that's the thing statisticians have talked about Michael I. Jordan: for a long, long time. Michael I. Jordan: And so nowadays I think it's a given that, yeah, they're, Michael I. Jordan: they're kind of two parts, two sides of the same coin.
Michael I. Jordan: Machine learning is maybe a little more engineering in order Michael I. Jordan: to build a system and make it do great things in the world. Michael I. Jordan: And statistics is a little bit more, well, let's be cautious. Michael I. Jordan: Let's say we're going to do like clinical trials.
Michael I. Jordan: Let's make sure that the the answer is really trustable, but Michael I. Jordan: those are two sides of the same coin, and I think that's Michael I. Jordan: probably pretty much clear now. Michael I. Jordan: But for a long time there was a resistance. Michael I. Jordan: Everyone said this is a brand new field, this is different. Michael I. Jordan: And I kept and again annoying colleagues by saying, no, I Michael I. Jordan: don't believe it is.
Michael I. Jordan: So anyway, long story short, it is. Tom Mitchell: It is remarkable that to me that Tom Mitchell: the field of machine learning Tom Mitchell: went through most of the Tom Mitchell: nineteen eighties, kind of Tom Mitchell: without even noticing that Tom Mitchell: statistics exist. Michael I. Jordan: I mean, people like Leo Breiman Michael I. Jordan: were around to help make the Michael I. Jordan: passage.
Michael I. Jordan: So ensemble methods, they were kind of invented by Leo and stat Michael I. Jordan: literature, but they were independently invented in the Michael I. Jordan: machine learning literature. Michael I. Jordan: And is that machine learning or statistics? Michael I. Jordan: Well, clearly it's both and it needs both perspectives.
Michael I. Jordan: And yes, in the nineteen nineties that the Em algorithm, Michael I. Jordan: you know, the graphical models, they were they had, they had uh, Michael I. Jordan: so yeah, the nineties, it was a real flourishing of that. Tom Mitchell: So Mike mentioned that one of the themes was ensemble.
Tom Mitchell: So anyway, I think that's Tom Mitchell: actually a very nice example of Tom Mitchell: how machine learning theory and Tom Mitchell: statistical theory kind of Tom Mitchell: intertwined. Tom Mitchell: The idea of ensemble learning is Tom Mitchell: instead of learning one Tom Mitchell: hypothesis, let's learn multiple Tom Mitchell: ones.
Tom Mitchell: For example, instead of learning Tom Mitchell: a decision tree, you might learn Tom Mitchell: a whole forest of decision Tom Mitchell: trees. Tom Mitchell: And then when it comes to Tom Mitchell: classifying a new example, you Tom Mitchell: give it to all of the Tom Mitchell: classifiers and you let them Tom Mitchell: vote and you take the vote of Tom Mitchell: the classifiers.
Tom Mitchell: Well, that turned out to be very Tom Mitchell: successful and commercially very Tom Mitchell: important. Tom Mitchell: But it also is a beautiful Tom Mitchell: example where, there's a Tom Mitchell: pretty interesting theory around Tom Mitchell: that. Tom Mitchell: And initially, Yoav Freund and Robert Shapiro, uh, in the early Tom Mitchell: nineties, uh, started working on a theory and methods for doing Tom Mitchell: this kind of ensemble.
Tom Mitchell: Leo Breiman, who was a statistician, recognized that Tom Mitchell: this echoed some of the themes of resampling and statistics. Tom Mitchell: And those two things, uh, kind Tom Mitchell: of came together in a very Tom Mitchell: successful way. Tom Mitchell: So in the nineties and the first Tom Mitchell: decade of the two thousand, Tom Mitchell: there were many other things Tom Mitchell: going on.
Tom Mitchell: The development of things called support vector machines, Tom Mitchell: kernel methods, which were, mathematical techniques for Tom Mitchell: learning, very nonlinear classifiers that were actually Tom Mitchell: commercially important and opened the door in many cases to Tom Mitchell: machine learning for non-numerical data, data like Tom Mitchell: images or text. Tom Mitchell: There is work on manifold learning.
Tom Mitchell: There was also growing Tom Mitchell: commercialization during that Tom Mitchell: decade. Tom Mitchell: More and more companies were Tom Mitchell: starting to use machine learning Tom Mitchell: commercially.
Tom Mitchell: But for me, the theme of that first decade of the two thousand Tom Mitchell: was really a growing awareness by many people that, you know, Tom Mitchell: maybe we have good enough machine learning algorithms that Tom Mitchell: the bottleneck to more accuracy is not the algorithm. Tom Mitchell: Maybe we need more data and more computation.
Tom Mitchell: And this idea was crystallized in this beautiful paper written Tom Mitchell: in two thousand and nine by three authors at Google, called Tom Mitchell: The Unreasonable Effectiveness of Data, which really Tom Mitchell: highlighted, cases where, if you want better Tom Mitchell: results, keep your same algorithm, get more data. Tom Mitchell: And that was kind of a theme of what was going on at the time, Tom Mitchell: but things really broke open in the year twenty twelve.
Tom Mitchell: In twenty twelve, the computer vision community had Tom Mitchell: been using a data set created by Fei-Fei Li called ImageNet to Tom Mitchell: test out different vision algorithms, see who could do the Tom Mitchell: best job of labeling which object was the primary object in Tom Mitchell: an image, and the image net data set was very large. Tom Mitchell: In twenty twelve, Geoff Hinton and some of his students entered Tom Mitchell: the competition and they blew away the competition.
Tom Mitchell: What's interesting is they were the only neural network approach Tom Mitchell: in the competition by that time. Tom Mitchell: By the way, neural networks were Tom Mitchell: very scarce in the field of Tom Mitchell: machine learning. Tom Mitchell: They had been displaced really Tom Mitchell: by more recent probabilistic Tom Mitchell: methods, and only a smallish Tom Mitchell: number of researchers were even Tom Mitchell: still working on neural Tom Mitchell: networks.
Tom Mitchell: But, nevertheless, this happened. Tom Mitchell: So I asked Geoff about that. Geoffrey Hinton: And Yann realized when Fei-Fei came up with the ImageNet Geoffrey Hinton: dataset, Yann realized they could win that competition, and Geoffrey Hinton: he tried to get graduate students and postdocs in his lab Geoffrey Hinton: to do it, and they all declined. Geoffrey Hinton: And Ilya, Ilya Sutskever realized that, backprop Geoffrey Hinton: would just kill ImageNet.
Geoffrey Hinton: He wanted Alex to work on it and actually didn't really Geoffrey Hinton: want to work on it. Geoffrey Hinton: Alex had already been Geoffrey Hinton: working on small images and Geoffrey Hinton: recognizing small images in Cfar Geoffrey Hinton: ten, and pre-processed Geoffrey Hinton: everything for Alex to make it Geoffrey Hinton: easy. Geoffrey Hinton: And I bought Alex two Nvidia Geoffrey Hinton: GPUs to have in his bedroom at Geoffrey Hinton: home.
Geoffrey Hinton: Alex then got on with got on with it, and he was an Geoffrey Hinton: absolutely wizard programmer. Geoffrey Hinton: He wrote amazing code on Geoffrey Hinton: multiple GPUs to do convolution Geoffrey Hinton: really efficiently. Geoffrey Hinton: Much better code than anybody else had ever written. Geoffrey Hinton: I believe and so it's a combination of Ilya realizing we Geoffrey Hinton: really had to do this.
Geoffrey Hinton: I know you was involved in the design of the net and so on, but Geoffrey Hinton: Alex's programming skills. Geoffrey Hinton: And then I added a few ideas, like use rectified linear units Geoffrey Hinton: instead of sigmoid units and use little patches of the images. Geoffrey Hinton: I mean, big patches of the images.
Geoffrey Hinton: So you can translate things Geoffrey Hinton: around a bit to get some Geoffrey Hinton: translation invariance, as well Geoffrey Hinton: as using convolution, and Geoffrey Hinton: use dropout. Geoffrey Hinton: So that was one of the first applications of dropout. Geoffrey Hinton: And that helped about one percent. Geoffrey Hinton: It helped. Geoffrey Hinton: And then we beat the best vision systems.
Geoffrey Hinton: The best vision systems were sort of plateauing at twenty Geoffrey Hinton: five percent errors. Geoffrey Hinton: That's errors for getting the right answer in the top in your Geoffrey Hinton: top five bets. Geoffrey Hinton: And we got like fifteen percent, fifteen or sixteen, Geoffrey Hinton: depending on how you count it. Geoffrey Hinton: So we got almost half the error rate.
Geoffrey Hinton: And what happened then was what Geoffrey Hinton: ought to happen in science but Geoffrey Hinton: seldom does. Geoffrey Hinton: So our most vigorous opponents, like Jitendra Malik and Geoffrey Hinton: Zisserman, Andrew Zisserman, looked at these results and Geoffrey Hinton: said, okay, you were right. Geoffrey Hinton: That never happens in science. Geoffrey Hinton: And slightly irritating. Andrew Zisserman then switched Geoffrey Hinton: to doing this.
Geoffrey Hinton: He had some very good postdocs or students working with him. Geoffrey Hinton: Simonyan, after about Geoffrey Hinton: a year, they were making better Geoffrey Hinton: networks than us, but that was Geoffrey Hinton: really the. Geoffrey Hinton: As far as the general public was concerned. Geoffrey Hinton: That was the start of this big Geoffrey Hinton: swing towards deep learning in Geoffrey Hinton: twenty twelve.
Tom Mitchell: So that event, that competition Tom Mitchell: and the fact that the neural Tom Mitchell: network approach, totally Tom Mitchell: dominated all the other Tom Mitchell: approaches really was a wake up Tom Mitchell: call to both the computer vision Tom Mitchell: community, which within a couple Tom Mitchell: of years everybody was using Tom Mitchell: neural networks.
Tom Mitchell: But it was also a wake up call to the machine learning Tom Mitchell: community, who had kind of scoffed at neural networks for Tom Mitchell: several decades, that neural networks were back. Tom Mitchell: And so people started again, now Tom Mitchell: experimenting with this new Tom Mitchell: generation of deep neural Tom Mitchell: networks.
Tom Mitchell: That just meant that instead of having two layers, they could Tom Mitchell: have many layers, dozens of layers, because training Tom Mitchell: algorithms were available and so was is computation. Tom Mitchell: People start experimenting with these and primarily on Tom Mitchell: perceptual style problems.
Tom Mitchell: In fact, by twenty sixteen, Tom Mitchell: neural nets had taken over not Tom Mitchell: only computer vision, but in Tom Mitchell: twenty sixteen, some scientists Tom Mitchell: from Microsoft showed that they Tom Mitchell: had been able to train a neural Tom Mitchell: network to finally reach human Tom Mitchell: level recognition. Tom Mitchell: Speech recognition performance for individual words in a widely Tom Mitchell: used data set called the switchboard data set.
Tom Mitchell: So people were experimenting with neural nets for visual Tom Mitchell: data, speech data, radar, lidar, all kinds of sensory data. Tom Mitchell: People started also asking, Tom Mitchell: well, can we apply these to text Tom Mitchell: data? Tom Mitchell: And the answer was yes.
Tom Mitchell: And people started inventing various architectures, things Tom Mitchell: with names like long short term memory and others to analyze Tom Mitchell: sequences of text and applying them to problems like machine Tom Mitchell: translation, translating English into French, and so forth. Tom Mitchell: And, uh, that kind of worked. Tom Mitchell: And then in twenty seventeen, Tom Mitchell: a very important paper was Tom Mitchell: published.
Tom Mitchell: The name of the paper was Attention is All You Need. Tom Mitchell: And with that was referring to was a subcircuit in a Tom Mitchell: neural network called an attention mechanism that had Tom Mitchell: recently been invented and developed and was trainable. Tom Mitchell: But that attention mechanism Tom Mitchell: was used in this paper, and it Tom Mitchell: advanced the state of the art in Tom Mitchell: machine translation.
Tom Mitchell: But even more importantly for us today, it introduced the Tom Mitchell: transformer architecture based on this attention mechanism. Tom Mitchell: And it's that transformer Tom Mitchell: architecture that underlies GPT Tom Mitchell: and pretty much all of the large Tom Mitchell: language models that were Tom Mitchell: released around twenty twenty Tom Mitchell: two. Tom Mitchell: So that was a major event.
Tom Mitchell: Now, around the same time, Yann Tom Mitchell: LeCun, remember the guy who was Tom Mitchell: a postdoc with Jeff in nineteen Tom Mitchell: eighty seven? Tom Mitchell: Yann had become the head of AI research at Facebook. Tom Mitchell: And so he was in a very interesting position because he Tom Mitchell: was both an academic.
Tom Mitchell: He retained his NYU professorship and at the same Tom Mitchell: time he had a foot in the commercial world directing the Tom Mitchell: AI strategy for Facebook. Tom Mitchell: So ask John about this period Tom Mitchell: and what it looked like to him Tom Mitchell: from from being inside both Tom Mitchell: worlds.
Tom Mitchell: His first part of his answer was Tom Mitchell: that he said for him, a key Tom Mitchell: development was realizing that Tom Mitchell: you didn't have to wait for Tom Mitchell: people to label all your Tom Mitchell: training data, that you could do Tom Mitchell: something called self-supervised Tom Mitchell: learning.
Tom Mitchell: For example, just take data like a string of words and remove a Tom Mitchell: word and have the program force the program to predict what that Tom Mitchell: removed word was. Tom Mitchell: So there's no human labeling you have to do for that. Tom Mitchell: You can use the whole web and Tom Mitchell: you get a lot of training Tom Mitchell: examples. Tom Mitchell: So that's self-supervised learning was a key development. Tom Mitchell: But then here's this description of what next.
Yann LeCun: So the idea that self-supervised learning could really kind of Yann LeCun: bring something to the table there, I think was kind of a Yann LeCun: big sort of mind, change of mindset. Yann LeCun: And then there was Transformers, of course.
Yann LeCun: Right. Yann LeCun: Um, that, so, so before that, there was some Yann LeCun: demonstration that, you know, you could basically match Yann LeCun: the performance of classical systems for tasks like Yann LeCun: translation, language translation using large neural Yann LeCun: nets like LSTM. Yann LeCun: So this was the work by Ilya Sutskever when he was at Google.
Yann LeCun: We had this big sequence to sequence model with LSTMs and Yann LeCun: some gigantic model where you can train it to do. Yann LeCun: Translation. Yann LeCun: And it kind of works at the same Yann LeCun: level, if not better in some Yann LeCun: cases than the then classical, Yann LeCun: classical, the transition Yann LeCun: methods.
Yann LeCun: Then a few months later, Yann LeCun: Yoshua Bengio and Kyunghyun Cho, Yann LeCun: who is now a colleague at NYU, Yann LeCun: uh, showed that you could change Yann LeCun: the architecture and use this Yann LeCun: attention mechanism. Yann LeCun: That, that they proposed, to basically get really good Yann LeCun: performance on translation with much smaller models than what Yann LeCun: Ilya had been proposing.
Yann LeCun: And the entire industry jumped Yann LeCun: on this, Chris Manning's Yann LeCun: group at Stanford, kind of, you Yann LeCun: know, used that architecture and Yann LeCun: basically beat, you know, Yann LeCun: won the WMT competition for a Yann LeCun: particular, uh, type of Yann LeCun: translation. Yann LeCun: And the entire industry jumped on it.
Yann LeCun: So within a few months after that, like, you know, all the Yann LeCun: big players, uh, in translation, were using attention type Yann LeCun: architectures for translation. Yann LeCun: And that's when, the transformer paper came out. Yann LeCun: Attention is all you need. Yann LeCun: So basically, if you build a neural net just with those kind Yann LeCun: of attention circuit, you don't need much else. Yann LeCun: And it ends up working super well.
Yann LeCun: And that's what started the, you Yann LeCun: know, the transformer Yann LeCun: revolution. Yann LeCun: Uh, and then after that came Bert, that also came out of Yann LeCun: Google, which was this idea of using self-supervised learning, Yann LeCun: where I take a sequence of words, corrupt it, remove some Yann LeCun: other words, and then train this big neural net to reconstruct Yann LeCun: the words that are missing. Yann LeCun: Predict the words that are missing.
Yann LeCun: And again, people were Yann LeCun: amazed by like how how good the Yann LeCun: representations learned by the Yann LeCun: system were for all kinds of NLP Yann LeCun: tasks. Yann LeCun: And that really, uh, you know, kind of captured the imagination Yann LeCun: of a lot of people. Yann LeCun: And then after that, the next revolution was, oh, Yann LeCun: actually, the best thing to do is you remove the encoder, you Yann LeCun: just use a decoder.
Yann LeCun: And you just train a system, you feed it a sequence, and you Yann LeCun: just train it to reproduce the input sequence on its output, Yann LeCun: and because the architecture of the decoder is strictly causal. Yann LeCun: Because a particular output is not connected to the Yann LeCun: corresponding input, it's only connected to the ones to the Yann LeCun: left of it.
Yann LeCun: Implicitly, you're training the Yann LeCun: system to predict the next word Yann LeCun: that comes after a sequence of Yann LeCun: words. Yann LeCun: That's the GPT architecture that Yann LeCun: was, you know, promoted by Yann LeCun: OpenAI. Yann LeCun: And, that turned out to be more scalable than Bert.
Yann LeCun: And so in a sense that you can Yann LeCun: train gigantic networks on Yann LeCun: enormous amounts of data and you Yann LeCun: get some sort of emergent, Yann LeCun: property. Yann LeCun: And that's what gave us llms. Tom Mitchell: So that brings us up to today with Transformers. Tom Mitchell: And you can see this very strange evolution in wandering Tom Mitchell: path of, uh, progress exploration over decades.
Tom Mitchell: So before we leave, I Tom Mitchell: want to let's just take a look Tom Mitchell: at that history And say, what if Tom Mitchell: this is a case study of how Tom Mitchell: scientific progress was made in Tom Mitchell: this field? Tom Mitchell: What are the main themes we see? Tom Mitchell: Well, I think the first one is progress happens in waves. Tom Mitchell: It's paradigm after paradigm, right?
Tom Mitchell: First there were perceptrons, Tom Mitchell: but that got, uh, thrown away Tom Mitchell: and replaced by symbolic Tom Mitchell: representations being learned, Tom Mitchell: eventually to be replaced by Tom Mitchell: neural nets, which were replaced Tom Mitchell: by probabilistic methods and so Tom Mitchell: forth. Tom Mitchell: So there's wave after wave of paradigm. Tom Mitchell: Another theme is that a lot of Tom Mitchell: these ideas really came from Tom Mitchell: other fields.
Tom Mitchell: Even the very notion of Tom Mitchell: perceptrons came from somebody Tom Mitchell: who was fundamentally a Tom Mitchell: neuroscientist interested in how Tom Mitchell: neurons in the brain could even Tom Mitchell: learn stuff. Tom Mitchell: Pack learning. Tom Mitchell: You heard less valiant talk. Tom Mitchell: He's very much a Tom Mitchell: computational complexity Tom Mitchell: researcher who found that this Tom Mitchell: was an interesting theoretical Tom Mitchell: result.
Tom Mitchell: Bayesian networks heavily Tom Mitchell: influenced by statistics and so Tom Mitchell: forth. Tom Mitchell: Many of these advances really Tom Mitchell: were new framings of the Tom Mitchell: problem. Tom Mitchell: So, uh, Winston's work on Tom Mitchell: symbolic learning was really a Tom Mitchell: reframing of what the problem Tom Mitchell: was.
Tom Mitchell: The work on reinforcement Tom Mitchell: learning is really changing the Tom Mitchell: definition of what the training Tom Mitchell: signal even is for these Tom Mitchell: systems. Tom Mitchell: So that's another theme that you see. Tom Mitchell: And finally, I think like a lot Tom Mitchell: of scientific fields, machine Tom Mitchell: learning is really a blend of Tom Mitchell: technical forces and social Tom Mitchell: forces.
Tom Mitchell: Certainly in the long term, Tom Mitchell: the cold, hard facts of what Tom Mitchell: works best come out and those Tom Mitchell: methods win. Tom Mitchell: But in the shorter term, the Tom Mitchell: question of who works on what Tom Mitchell: kinds of problems is very much Tom Mitchell: influenced by the personalities Tom Mitchell: of people.
Tom Mitchell: Their ability to persuade other Tom Mitchell: people to jump in and start Tom Mitchell: working with them on their Tom Mitchell: problems. Tom Mitchell: So these are some of the themes you see. Tom Mitchell: And I think if you look around at other fields, sometimes you Tom Mitchell: see similar themes. Tom Mitchell: Finally, what are the lessons from all this for researchers? Tom Mitchell: I think the first lesson really is question authority.
Tom Mitchell: Because really, if you think Tom Mitchell: about the major advances, many Tom Mitchell: of those came from just, uh, Tom Mitchell: going against what was currently Tom Mitchell: the conventional wisdom in the Tom Mitchell: field. Tom Mitchell: Inventing a new framing or Tom Mitchell: taking a radically different Tom Mitchell: approach. Tom Mitchell: Another lesson don't drag your feet.
Tom Mitchell: I've seen decade after decade, new paradigms emerge in the Tom Mitchell: field, and every single time that happens, existing Tom Mitchell: researchers take longer than they need to to recognize the Tom Mitchell: benefits of the new paradigm. Tom Mitchell: And the most guilty people are the senior researchers.
Tom Mitchell: You can probably explain that by Tom Mitchell: taking into account who has the Tom Mitchell: most to lose if there's a new Tom Mitchell: paradigm replacing the current Tom Mitchell: approach. Tom Mitchell: Another lesson learn to Tom Mitchell: communicate and learn to follow Tom Mitchell: through. Tom Mitchell: You heard Geoff Hinton when he Tom Mitchell: was talking about in the mid Tom Mitchell: eighties, the development of Tom Mitchell: back propagation.
Tom Mitchell: You heard him say we didn't invent backpropagation, but we Tom Mitchell: showed that it was important. Tom Mitchell: And actually, to be fair, they Tom Mitchell: thought they were inventing Tom Mitchell: backpropagation.
Tom Mitchell: They they actually reinvented Tom Mitchell: it, but they had no idea that Tom Mitchell: somebody had invented it before, Tom Mitchell: because whoever did that didn't Tom Mitchell: succeed in waking up the Tom Mitchell: research community to the fact Tom Mitchell: that they had a really good Tom Mitchell: idea. Tom Mitchell: I don't know why. Tom Mitchell: Maybe they didn't put in the Tom Mitchell: effort or succeed in Tom Mitchell: communicating.
Tom Mitchell: Maybe they dropped it after they Tom Mitchell: did it and went some other Tom Mitchell: direction so that they didn't Tom Mitchell: follow through to provide the Tom Mitchell: evidence. Tom Mitchell: But that kind of thing happens Tom Mitchell: frequently in successful Tom Mitchell: researchers are good Tom Mitchell: communicators, and they follow Tom Mitchell: through to to push the field to Tom Mitchell: pay attention.
Tom Mitchell: The final lesson, I think, is Tom Mitchell: the philosophers were actually Tom Mitchell: right. Tom Mitchell: We really today, despite these amazing capabilities of our Tom Mitchell: learning systems, we don't have a proof or anything like a Tom Mitchell: rational justification of why you can generalize from examples Tom Mitchell: to get these general rules that work well despite the success Tom Mitchell: that we have.
Tom Mitchell: We don't really understand at this very fundamental level why. Tom Mitchell: And I think that if we did pay more attention to that question, Tom Mitchell: we might have a better chance to develop algorithms that Tom Mitchell: outperform what we have today. Tom Mitchell: So I'll stop there. Tom Mitchell: Thank you very much. Speaker 12: Tom Mitchell is the Founders Speaker 12: University professor at Carnegie Speaker 12: Mellon University.
Speaker 12: Machine learning How Did We get here? Speaker 12: Is produced by the Stanford Digital Economy Lab. Speaker 12: If you enjoyed this episode, Speaker 12: subscribe wherever you listen to Speaker 12: podcasts.