[MUSIC PLAYING]
DAVID MALAN: This is CS50, Harvard University's introduction
to the intellectual enterprises of computer science--
over here, computer science.
So today we are joined by CS50's own Brian Yu.
This is an unusual week, a look at artificial intelligence or AI.
You might recall that some weeks ago when we first introduced Python,
we talked about writing programs that answered you
by saying hello if you said hello, or by saying goodbye if you said goodbye.
But those programs were all implemented with if conditions and else ifs
and else ifs and so that really wasn't artificial intelligence.
If you wanted to have a whole conversation with a computer
program like that, that would be a huge number of ifs and else ifs just
to anticipate all of the things the human might say.
So we can do better, and indeed humans have
been doing better in this field of artificial intelligence.
And I'm so pleased to say that Brian is here to lead us along that way.
Now, CS50's own, Brian Yu.
BRIAN YU: Thanks very much.
Welcome, everyone, to CS50.
And today as David alluded to, the topic of discussion
is artificial intelligence, which is all about taking our computers
and trying to make them intelligent somehow,
trying to get them to be able to act in a way
that's somewhat rational, somewhat human and that
could take a number of different forms.
One example of artificial intelligence, for example, might be game play.
You might be familiar with the game of tic-tac-toe,
where you've got this three by three grid
and X and O take turns trying to get three in a row.
And if, for example X started the game and played
in the middle square of this grid and then it was O's turn
and O played in the top, it turns out that at this point in the game
X has a very strategic move.
And a human that's very good at the game or a computer that can maybe
try and figure out how to play this game well,
might make an intelligent move like playing
in the top right corner for example.
And if X plays in the top right corner, well then
O is going to need to play in the bottom left corner
in order to block X from getting three in a row.
And here maybe you can see one of a couple of possible good moves
that X has now, but X could play a move like moving
in the right square over there.
And now O is in a tricky position, X has one way that could potentially
win the game horizontally, and another way they could potentially
win the game vertically.
And so O is going to have to block one of those ways,
and maybe they go to block horizontally but then
X is going to win no matter what just by playing in that bottom right corner.
And so a human playing this game could reason through the game thinking
about how the opponent might respond and how X would respond in turn
and a computer might try to do the same thing for a game as simple
as tic-tac-toe or a game even more complex.
But AI goes beyond just game plan, you might see examples
like handwriting recognition, where nowadays computers
are pretty good at taking human handwritten text, which can be messy,
which is different from person to person,
and somehow figuring out with pretty high accuracy exactly what characters
the human was actually writing.
AI comes up in areas like spam detection.
Maybe in your email inbox you have your inbox
and your spam email usually gets sorted into a separate folder
where you might get a whole bunch of emails coming into your email inbox
and somehow your computer is able to figure out with reasonable accuracy,
which emails are good and which emails are spam.
Now of course, the computer is not perfect at this.
There are false positives, where the computer thinks that an email might
be spam when it isn't actually.
And there are false negatives too, where a spam email might accidentally
end up in your inbox because the computer doesn't catch it,
but those sorts of false positives and false negatives
are the types of things that AI researchers are
working on trying to reduce to make these systems more and more accurate.
You see these kinds of systems show up as well if you've ever
been on a video watching website, like YouTube or Netflix,
for example, where you have watched a whole bunch of videos or TV shows
or movies and then software behind Netflix or behind YouTube
is able to give you recommendations, suggest other videos that you
might be interested in watching based on the things that you've watched already.
And in more recent years, AI has gotten pretty good
at doing even more sophisticated things, things like generating data.
Take a look at these two images, for example, of people
and see if you notice anything strange.
See if either of these people look strange to you.
In fact, can you figure out which of these two images is not a real person?
That is to say, a computer-generated person that looks like it's human
but is not actually a photo of a real person.
So you can look at these two images carefully, maybe look
at the eyes and the hair and the mouth and the nose
and see if you can figure out which one it is.
It turns out neither of these two images are images of real people.
They're both computer generated, not photos of real people but a computer
has been trained to generate images of people that look like real people that
could fool someone into thinking that it's a real person,
but it's all just AI generated information.
So today we'll take a look at all of those ideas, how it
is that artificial intelligence works.
And ultimately one of the big takeaways is that AI is not just
one algorithm or one principle, it's really
a collection, a category of approaches to problem solving that can all
be used to try and solve some of these problems of trying
to make computers intelligent.
So let's begin with one of the first areas
where we might want to make our AI work and that's
in the area of decision making.
Very frequently we want to train a computer
to be able to make a decision well.
That decision might be deciding if an email is spam or not spam,
or deciding whether or not to recommend a video to you,
or it could be deciding what action to take in a game, for example.
So let's take a simple game, maybe you've
played a game like this before where you control this paddle along the bottom
and you're trying to bounce this ball in order to hit all of the bricks
along the top.
Imagine if you were trying to program a computer
to be able to play this game strategically, to play this game well
and the computer observed the ball move that way.
So the ball is moving that way, what should you program the computer to do?
Well, it makes logical sense that if the ball's moving to the left, then
you should program the computer to move the paddle to the left as well,
to try and catch that ball before it falls through the ground.
And so you could take that kind of logic and encode it
into a computer program using what we might call a decision tree.
Decision trees are just a way of representing a decision
that a computer might make by asking questions
and depending on the answers to those questions we might ask another question
or make some sort of decision.
So for this game of the paddle, we could create a decision tree
by asking a question like this, we could ask,
is the ball to the left of the paddle?
If the answer to that question is yes, well then the action we should take
is we should move the paddle to the left because the ball is moving left,
the paddle should move left as well.
If the answer to the question is no, well then we
need to maybe ask another question, we might ask a question like,
is the ball to the right of the paddle?
And if the answer to that question is yes,
then we'll go ahead and move the paddle to the right.
And if the answer to the question is no, well that
means the ball is not to the left of the paddle
and it's not to the right of the paddle, so we may as well just not
move the paddle at all in that case.
So this again is that decision tree that can
allow us to make these choices about what it is that our AI should
do in this situation and we could take that decision tree and turn it
into a kind of pseudocode, something that might look like something
you would write in C or in Python.
I might say while the game is ongoing, if the ball is
to the left of the paddle, go ahead and move the paddle to the left.
Else if the ball is to the right of the paddle, move the paddle to the right.
And else if neither of those are true, then don't move the paddle at all.
So one of the advantages of this decision tree
is that it translates quite nicely to the conditions
that you're familiar with from the world of programming.
So let's give this a try with something a little more complex.
Let's take the game of tic-tac-toe for example.
And imagine you were trying to program an AI to strategically play
the game of tic-tac-toe.
What questions might you ask in your decision tree, what yes or no questions
might you want to ask to create an AI that can play this game well,
that can play this game strategically?
And maybe I'll take a volunteer if anyone
wants to suggest one possible question I might want to ask of my AI
as I'm trying to teach this AI how to play this game?
Any thoughts for questions that I might ask in this situation?
And let's go to--
let's see, let's try [? Vasily ?] if you have an idea?
AUDIENCE: Maybe let's ask what is the probability
of winning given a certain move?
BRIAN YU: Great.
And what would winning mean?
How could you detect what it would mean to win, like what are you
going to look for on the board?
AUDIENCE: Three consecutive yeah, Xs or circles.
BRIAN YU: Great, you're looking for some opportunity
for like three consecutive Xs or three consecutive Os.
So one of the questions you might ask is checking
to see whether or not you could get three in a row maybe on the next turn.
If you already have two in a row and there's an empty space
that could be an opportunity for something that we might want to try.
Any other questions we might want to ask as part of our strategic decision
making if we're trying to play this game of tic-tac-toe,
any thoughts about other things we could try,
other types of things we should be looking for or asking
as we're training our artificial intelligence, as we're
trying to program it to play this game strategically?
Let's go to Santiago, you have an idea?
AUDIENCE: Hello, Brian.
If there is any possibility to win, the other player?
BRIAN YU: For the other player?
Yeah, so you might want to check the other player to see
if they have some possibility to win.
And if they have some possibility to win you could try to block them.
So those are great questions you could ask.
And we could start to formulate a decision tree for tic-tac-toe
based on those questions.
I might start by asking, can I get three in a row on this turn?
And if the answer is yes, well, then my action is pretty straightforward.
I should play in the square that will get me to three in a row.
If the answer to the question is no, well then I
might ask Santiago's question, I might ask,
can my opponent get three in a row on their next turn?
And if the answer to that is yes, well then, we better
play in the square to block them from getting three in a row,
otherwise they're going to win the game if we don't block them now.
If the answer to this question is no though,
if I can't get three in a row in this turn
and my opponent can't get three in a row in the next turn,
well now it's a little bit less clear.
You could maybe try and come up with additional questions
you might ask but these two questions are very clear
and the rest maybe a little bit less obvious but ultimately we
don't want to be doing any of this as we're starting to make
our AI more and more intelligent.
As David was alluding to earlier, ultimately
rather than us have to program every condition into the computer,
telling it what to do in every situation,
we'd like for the computer to be smart enough to just figure out on its own,
analyze on its own all of the possibilities
and figure out what move it should make.
And ultimately we want our computer to make
the optimal decision, the best possible decision when playing this game.
And so to do so we can introduce our first algorithm
in artificial intelligence that we'll look at today
and that algorithm is called minimax.
Minimax is a game playing algorithm that's
useful any time you have two competing players that
are trying to play some sort of competitive game like tic-tac-toe,
but it'll work for other games as well.
And ultimately as with we've seen all throughout CS50,
we need some way of representing this game inside of the computer.
And ultimately you'll recall way back from the beginning of CS50,
we've been trying to take everything and represent it just with numbers
and we can do the same thing with games.
As far as our AI is concerned, there are only three possible outcomes
of the game that our AI is going to care about,
either O wins or X wins and X gets three in a row,
or it's possible that neither side wins, that it ends up being a tie.
And so what we're going to do is take each of these three possible outcomes
and assign a number to each of those outcomes.
We'll say O winning, we're just going to say,
let's call that negative one, X winning, we'll call that one.
And a tie, well that's somewhere in between the two.
So we'll go ahead and call that zero.
Nobody wins that game.
And now each player has a goal, some objective that we
can quantify using these numbers.
The X player, who we might also call the max player,
aims to maximize the score, what's best for X is a score of one,
meaning X is going to win.
But if X can't win, well then tying the game
is zero, that's better than losing the game which is negative one.
Meanwhile the O player we're going to call
the min player, the minimizing player, their goal is to minimize the score.
Negative one is the best outcome for the O player,
but if negative one can't happen, if O can't win, well,
then tying the game is still better than X
winning because X winning would mean our minimizing player, player O,
is ultimately going to lose the game.
And so we can take every board in tic-tac-toe and assign a score to it,
it's either one or zero or negative one.
So this board for example, this game is over, X has already won the game
and because X has won the game, we're going to give that a value of one.
One corresponds to X winning, negative one to O winning, zero for a tie.
So let's now consider this game board.
This game board isn't over yet, but we can still assign a score to it.
Let's assume that it's X's turn, what score would we give this board?
Well, when we're giving each board a score,
we're considering what would happen if both players were playing optimally.
In other words, if both players are playing the best possible moves
and in this case, if X is playing the best possible move,
well then X is going to play in this square to get three in a row
and so this board also has a value of one because if X plays their best move,
ultimately X is going to win the game, that has a value of one.
So let's take a look at another board, maybe one that's a little bit trickier.
Now in this board let's assume it's O's turn, so O gets to make a move
and then because there's one empty square,
X will get to make a move after that, what value
would you give to this board?
Maybe we'll ask for a volunteer.
Remember the possibilities are one if X is
going to win, negative one if O is going to win,
and a zero if it's going to be a tie.
If both players play the best moves and it's O's turn right now,
what value would you give to this board and why?
Maybe let's go to Santiago, go ahead.
AUDIENCE: Yeah, I would say that the value would be zero
because if both players pay their best move no one in the end
will win because O will block X and then there would be nothing left to do.
BRIAN YU: Yeah.
Absolutely correct.
It's certainly possible that X could win because X has two in a row,
they could get three in a row.
But if both players play their best moves,
well then O is going to block here and then
X is going to play in the upper left and it's
going to be a tie, which means this board is going to have a value of zero.
And the way a computer might figure that out
is by reasoning it through exactly the same way we did,
by considering both of the possible options.
If I want to know the value for this board where it's O's turn,
well then I'm going to consider both of the possible options.
O has two choices, O could play in the top left
or O could block X by playing in the bottom there
and the computer would consider both of those possible choices
and try and figure out what value each of those boards has.
So what happens if O plays in the top left?
Well, then X is going to play in the bottom and X is going to win the game.
X winning the game, that has a value of one,
remember X winning, that's the value of one, which means this board also
is going to have a value of one.
So X wins, that's not great.
So let's consider the other possible choice,
O could also have blocked X by playing in the bottom here
and in that case, that's going to lead to X playing in the upper left,
it's the only other possible option, that board has a value of zero,
it's a tie since nobody won.
Which means this board also has a value of zero.
And now the minimizing player is going to look at these two options.
If I play in the top left, that's going to be a value of one,
that's not good for me.
If I play in the bottom, that's going to be a value of zero, so that's better.
And so ultimately we can conclude that this board up
top as Santiago correctly stated, is also going to have a value of zero.
If both players play their best moves it's ultimately going to be a tie.
And this is what we may call a game tree, where
you're exploring all of the possible branches, all of the ways
this game could go.
And from here, we're two moves away from the end of the game.
But you could back up and consider what would it look like three moves away
from the end of the game.
And you'd end up with a bigger tree because you now
need to explore even more possibilities if you're
trying to figure out what the value of any particular game board is.
And so that's the way the minimax algorithm works,
consider all of the possible moves you could make
and then recursively in a sense, consider if I make my best move, what's
my opponent going to do in response and then
what could I do in response to that?
And we could formulate that as a little bit of pseudocode
by saying if the player is X, well then for all of the possible moves
let's go ahead and calculate a score for that board.
The same way we were just doing, by recursively following
all the possible moves, let's get a score for that board
and let's choose the move with the highest score.
And otherwise, if the player is O, well, then we'll do the same thing.
For all the possible moves, we'll calculate a score for that board,
but then we'll choose the move with the lowest score.
So the X player is picking the move that maximizes the score,
the O player is picking the move that minimizes the score.
And using this approach you can create an AI
that can play a game like tic-tac-toe perfectly.
It'll never lose the game if you've programmed it correctly.
And this works not only for tic-tac-toe but for other games as well.
But do you see any problems with this approach?
This approach of considering all of my possible moves, then
all of my opponent's possible responses to those moves, and then
all of my possible responses to those moves recursively
until we get down to the end of the game.
Any possible problems that might arise?
Let's go to Sophia maybe.
AUDIENCE: It can take a really long time to like explore all the branches
and actually come to a conclusion.
BRIAN YU: Yeah, the amount of time it's going
to take to explore all of those possible moves,
it could be quite large depending on how complex the game is.
For a game like tic-tac-toe, maybe think about how many possible games
of tic-tac-toe there are.
It turns out there are about 255,000 possible games of tic-tac-toe, which
seems like a lot, but computers are pretty fast
and computers can make it through all 255,000
of these possible tic-tac-toe games usually in a matter of seconds
on most modern computers.
But if you imagine a game like chess for example,
known for being a fairly complex game, how many possible games of chess
are there?
If there are 255,000 possible games of tic-tac-toe,
how many possible games of chess are there?
Well, it turns out that only after the first four moves,
if you only look at the first four moves of chess,
there are 288 billion possible chess games, which
is a lot for any computer to try to deal with
and that's only the first four moves.
If you consider the entire game of chess, nobody knows the answer exactly,
but people estimate that 10 to the 29,000
is probably a lower bound on the number of possible chess games.
The actual number is probably higher than that.
That is far too many for any computer to be able to reasonably get through
in any amount of time.
Computers as they exist now are not going
to be able to consider all of the possible moves going
all the way to the end of the game in order to figure out
what the score for any board is.
Which is why a game like chess is much harder for an AI
to play than a game like tic-tac-toe.
But it's not impossible.
And in fact, the best computer chess players
are far better than the best human chess players at this point.
So what could we do, what maybe improvement could we make
or what change could we make to the algorithm
so that our AI can still play a game like chess even though there
are so many additional possible moves?
There are a lot of possible answers but any ideas,
anyone want to offer a thought or a suggestion
as to how we might address this problem?
They are so many moves to consider, too many for a computer
to ever reasonably try to attempt.
Any thoughts on something we could try?
Let's go to, Kurt.
Yeah, you have an idea?
AUDIENCE: Yeah, just if there was some way along the way
to maybe assign some point values where you could, below some threshold maybe
you could like discard those paths?
BRIAN YU: Yeah, we want some way to be able to more intelligently not explore
all of the paths, but somehow like discard some of the paths
or not consider some of them or stop ourselves somewhere.
So that rather than consider all of the 10
to the 29,000 possible games of chess, we just consider fewer of them.
Exploring fewer possible games, exploring fewer possible levels
and so there are many variants on the minimax algorithm.
One of the most common being what's called depth-limited minimax, where
in depth-limited minimax, we consider what's called an evaluation function.
Rather than follow the game until the very end,
we follow the game some number of moves.
In chess maybe you're going 15, 16 moves, but not all the way
to the end of the game and then you're just asking a question like all right,
at this point in the game, who seems likely to win?
Even if we're not going to calculate it all the way,
you can maybe make some judgment by counting up
how many pieces of what value each side happens to have.
And you might come up with other strategies for different games.
But this now is where we need to start being even more
intelligent, to thinking about how can we come up with a good evaluation
function that's able to take a complex game and estimate who
is potentially likely to win.
So that then is minimax, an example of an algorithm that
can be used to play games.
And I'll pause here for any questions about minimax or game
playing artificial intelligence before we
move on to an entirely different type of artificial intelligence.
Yeah, Sophia, go ahead.
AUDIENCE: Yeah.
I just have a question, like this algorithm
is kind of following like how you would think about the game,
but are there any other algorithms that like don't necessarily
look like step by step evaluations?
BRIAN YU: Yeah, there are definitely other algorithms and other approaches.
In fact, right now what we've given an example of
is really just an example of an exhaustive search,
searching for all of the possible different moves
and then making a judgment based on that.
We'll see some examples of more intelligent algorithms or algorithms
that can learn later today in fact.
And we'll take a look at some of those other possibilities
and how we might apply them.
And so this then is really an example of what we might call a search algorithm.
A search algorithm is just a type of algorithm
where we're looking for some solution or some answer.
It could be looking for the best move to make in a game
or you might imagine a search problem more abstractly of something
like finding your way through a maze.
You're trying to get from one point in a maze to another point in a maze
and you have to make decisions about which way to turn and how to go.
And the real world application of this might
be something like driving directions.
If you go into Google Maps for example.
And you type where you are and where you're trying to get to,
Google Maps pretty quickly can give you a fairly optimal route, some path
to take which way to turn and when, when to make which decision, that
will get you from one point to another.
This is an example of a search problem, Google Maps
needs to somehow search through all of the possible routes you
can take to figure out how to get you to the place that you're going.
And so we could come up with an algorithm for trying to do that.
Imagine we have a maze like this, we're trying to get from point A to point B
but of course, we have some walls here, these
grayed out squares are walls that we can't cross through,
but we'd still like to try and find some path that will get us from point A
to point B.
There are a number of algorithms that you might try.
And you could think about if you were solving this maze as a person,
how would you do this?
How would you decide what decision to make, whether to go left
or whether to go right?
But as far as the computer is concerned, we
need to give it a very precise algorithm.
And one of the simplest algorithms we might come up with
is one called depth-first search.
And the way that depth-first search would navigate its way through a maze
is to say, the AI is going to just follow a path
and if ever the AI needs to make a choice, it reaches a fork in the road,
so to speak, where it could go left, or it could go right,
it's just going to choose one randomly.
It doesn't know which way is better, so it's going to pick one path
and it's going to try it.
And if ever it hits a dead end, it reaches
some wall where it can't make any more progress,
then our AI is just going to back up and it's going to try another path instead.
So I can show you what that looks like, we're starting at point A,
we're trying to get to point B. And the way our AI might work
is that we might start by just following one square after another.
Initially, we don't have much choice in the matter,
we haven't reached any branching points or any forks in the road.
But at this point right here, now we have a decision, we could go left
or we could go right.
And as far as depth-first search, otherwise known as DFS is concerned,
DFS doesn't know which way to go.
It doesn't know whether to go left, it doesn't know whether to go right,
so we pick one randomly.
We might choose to go left for example.
So we're going to go left and we're going to keep
following the path until we get to another fork in the road.
We could go left or right, DFS doesn't know which to pick,
so we're going to choose randomly, maybe we'll go left
and now we hit a dead end.
At that point our algorithm knows this was not a good path to take.
So it's going to back up to the latest decision point
and make a different choice.
So it's going to back up to right here and say, all right, I tried going left,
it didn't work.
Let's try going right instead.
So it's going to go right, it'll hit a dead end,
realize that OK, this was not a good path to take, it just led to dead ends,
it didn't go anywhere.
So instead of going left, let's try going right.
So we'll try this path, maybe we'll try going up but hit a dead end,
so we'll try going to the right.
Here again, we hit a decision, we're going to make some choice.
And again, we're just going to repeatedly hit dead ends
and try new paths until eventually we make our way to the destination.
And so that is depth-first search, and as long
as there are like a finite number of squares,
this algorithm is eventually going to find a path to the destination
if such a path exists.
Like if there is a way to get from point A to point B,
then this algorithm will eventually find it because it tries something
and if we reach a dead end then we try it again
and we keep doing that until eventually we find our way to the destination.
But this algorithm isn't great.
There are certainly some problems, some maybe room for improvement.
So maybe I'll ask all of you, what problems do you see with this approach?
Maybe reasons why this algorithm might not
be ideal, areas where we might be able to improve upon this algorithm
as it stands right now?
This again is depth-first search.
Let's go to Joy.
AUDIENCE: I think it is very time consuming.
BRIAN YU: Yeah, it's very time consuming.
And it's time consuming in a number of ways.
In one sense, we're exploring a lot of paths that really don't lead anywhere
in the sense that we explored all of this area
but ultimately that didn't help us towards trying to find the goal.
And it's also time consuming in the route that it ultimately finds,
like if you imagine using Google Maps, for example, to navigate
our way from one place to another, it's likely
going to be the case that you want to find an efficient route,
you want like the fastest way to get from where
you are to where you want to go.
And if Google Maps were to give you like a long and winding route with lots
of detours that got you to the destination but took
much longer than it needed to, that's probably
not the best user experience for you.
And depth-first search unfortunately could run into just that situation.
Imagine a maze like this, where from point A, we could go up
or we could go to the right, we don't know which to take,
so depth-first search will just randomly choose.
We might choose to go up and maybe we'll go right
and we'll find our way to the destination.
Sure, depth-first search was able to find us a path from A to B,
but remember that often what we want to do
is we want to make the optimal decision.
This is a correct path for getting from A to B, but it's not the best path.
If we're looking for the shortest path from A to B,
well that's going to be this one, it's going
to be this path here that goes from A to B there.
So we'd like some way to fix that, we'd like
an algorithm that is able to find us the shortest path,
not just finding us any path.
And so for that, we can use an algorithm called breadth-first search, otherwise
known as BFS.
And the way this algorithm works is that instead of whenever we
reach a fork in the road, pick one until we hit a dead end
and then pick the other.
What breadth-first search is going to do is whenever we hit a fork in the road,
let's take both paths, let's take one step on the left
and then one step on the right and then another step on the left
and another step on the right and effectively just
search outwards from the starting point.
We're going to start from the beginning and look for all of the places
we can get to by taking one step away from A,
and then everywhere we can get to taking two steps away from A,
and then three steps away from A, so on and so forth.
So we're always looking at the things that
are nearby before we look at the things that are further away.
So the way this might work is that from A we're going to take one step up
and then we're going to search one square to the right.
And then we'll look a second square on this direction and then a second square
along the path to the right and then a third square and a third square
and we're going to repeat that process, effectively alternating
between all of the different options that we have
until eventually we find this optimal path from A to B.
And because we're looking for the shorter paths
before we look for those longer paths, eventually we're
going to find that shortest possible path.
Now there are still problems with this too.
As Joy pointed out, these algorithms have a tendency
to explore a lot of paths unnecessarily.
Let's go back to that original maze for example
and consider what would breadth-first search
do if I presented it with this maze.
We'll consider what might happen, we might
go until we reach the first decision point right here,
we could go left or right.
And remember, depth-first search picked one
and just followed it until a dead end.
What breadth-first search is going to do is it's going to pick both.
It's going to go to the left and to the right.
And then to the left and to the right and basically alternate
between all of those until we reach another decision point and then
it's going to consider all of those possibilities.
Let's go left or left here and right and consider these possibilities too
and it's going to keep exploring.
Any time we reach any decision point, it's
going to explore this way and that way, this way and that way,
over and over again.
And ultimately, if we repeat this process
and consider what breadth-first search is looking for,
sure it's going to find me the shortest and in this case, the only possible
path to get from A to B but it took such a long time to be able to do so.
It looked at so many different squares, in fact,
it looked at all of the squares in order to do
something as simple as find the shortest path to get from one point to another.
And so here we can try to start to be a little bit more intelligent.
What we'd ideally like to do is that when we reach this first decision
point, go left or go right, most humans if you gave them this maze
and told you to try to solve it at this decision point,
you wouldn't just pick randomly, you would choose to go to the right
because you know the goal is somewhere to the right
and so it's probably the case that we should
follow that direction if we're trying to find our way to the end of the maze.
And so these algorithms we've looked at so far,
depth-first search and breadth-first search
are examples of what we might call uninformed search.
They're not using any specialized knowledge about the problem.
They don't really know anything about the maze.
They're just basically blindly guessing and hoping
that eventually we make our way to the solution.
But in AI we can improve upon this by using an informed search.
An informed search uses something that we know about the problem
to try and improve the way we search, to allow us to search a little bit more
effectively.
And to do so we're often going to make use
of what's known as a heuristic, some way of estimating how
good a particular state is going to be.
So in this maze for example, if I'm trying to get from A to B,
a heuristic would allow me to answer a question like,
if I see point C over here and point D over there, which one of those points
would I rather be at?
Which one is better for trying to find our way to the destination?
And between C and D, breadth-first search and depth-first search,
they have no knowledge of which one of those
is going to be better, as far as it's concerned every square is just
a square, but if you're looking at this as a maze,
most people would intuitively tell you, well, D is better.
Even if I don't know exactly how to get to the destination,
if I could be at either C or D, I'd probably
pick D because it just looks like it's closer to that destination.
And so the heuristic we could use is one that's
often known as the Manhattan distance.
The Manhattan distance between any two squares
effectively says ignore the walls, ignore all the boundaries,
just consider how many squares like in this case up and to the right
would I have to go to get from where I am to the destination.
And so for C, we would go up this many squares and then all the way
to the right, whereas from D doesn't matter whether you go up
or to the right first, but I would go right four squares and then up two.
D as far as Manhattan distance is concerned
is much closer to the goal than C and so I would rather be at D than at C.
And as soon as we have that notion of like between any two choices,
which one of those would I rather be at?
That gives us a way to improve upon the random guessing
that the other algorithms do.
Remember the depth-first search when it reached a fork in the road
and it could go left or right, it didn't know which to pick,
so it just randomly picked one.
Now that we have a heuristic like this, we can make an informed choice.
We can say, I don't know whether left or right is the correct solution,
but right is probably going to be better than left because of this heuristic.
And so I can make those sorts of judgments.
And so for that, we'll take a look at another algorithm
known as greedy best-first search.
So in greedy best-first search, what we're going to do
is consider for each of the squares what it's heuristic value is according
to the Manhattan distance in this case.
So this square for example, is one away from the goal,
so we've labeled it with the number one.
This square meanwhile is two away from our goal,
so we're labeling it with the number two, this is three away,
this is four away.
You'll notice though that we're ignoring any
of the walls, any of the boundaries, because those
are going to be difficult to compute.
We want something efficient.
This square here, even though in order to get to the goal
we have to follow this winding path to go around all the boundaries,
we're still giving it a score of two.
We want something efficient, right now, it just looks like it's two away.
So it's not a perfect heuristic, the heuristic is just an estimate
but we're using it as an approximation that's
going to help us as we go about this search process.
And so what we'll do is we'll start the same way, starting from point A looking
at all of the squares we can get to until we reach our first decision
point.
So here we could choose to go left or we could choose to go right
and in this case, going left according to the heuristic,
this square is 13 away from the goal and this one over here
is 11 away from the goal.
So between those two, being 11 away from the goal,
that sounds a whole lot better.
So greedy best-first search is going to make the choice to go to the right.
So we'll go 11, we'll keep following until we reach the next decision point.
Here from the eight we have two choices, up or to the right.
As far as the heuristic is concerned both of these are equivalent,
going up we're seven squares away, going to the right we're six plus one.
That's a total of seven squares away.
So here even greedy best-first search sometimes needs to pick randomly.
If both squares have the same heuristic value, we just have to make a choice.
And maybe we make a bad choice and hit a dead end
but then we can just try the other one.
So seven, six, we're going to keep following.
Here we have another decision point, we can go down or we can go to the right,
but the one to the right has a smaller heuristic value.
It's a six instead of an eight.
So we're always going to try and pick the one that
looks like it's going to be closer.
So we'll pick the six, we'll go to the five.
And here we reach one more decision point,
we can go up which has a heuristic of four
and we can go down which has a heuristic of six.
So even here because the four is the smaller value,
we're going to go up even though you, the human can
see we're ultimately going to run into a dead end,
the computer doesn't know that yet.
The computer just has to judge based on the heuristic what
it thinks is the best thing to do but eventually
it's going to run into that wall, realize that it can't make any progress
and then go back down here and will follow that path until ultimately we
arrive at the solution.
And so here we arrived at the same solution that breadth-first search did,
but we didn't need to consider all of the squares.
We could ignore all of these off to the left,
we could ignore all of these down below just
by being a little bit smarter about what choice we make.
Instead of just choosing randomly we make an informed choice
based on that heuristic.
I'll pause here for any questions then about the algorithms
we've looked at so far, depth-first search, breadth-first search, and now
an informed algorithm, greedy best-first search.
Any questions about these algorithms?
Yeah, let's go to let's see, Sofia?
AUDIENCE: In like the decision to go randomly
is it possible to like go further and see if there's like lesser values,
like go one more step?
BRIAN YU: You certainly could like maybe try and look ahead a couple of steps
and look at what might be following it.
And that might offer numbers that would improve upon the situation.
But even this algorithm is not perfect.
In fact, when you're just looking at these heuristic values
and following the heuristic values, sometimes the heuristic values
will lead you in a good direction, like sometimes in this case,
we ultimately, we made a couple of wrong turns
but ultimately we kind of found our way.
But that's not always going to be the case.
There are some cases where because the heuristic is really just an estimate,
the heuristic can sometimes be wrong.
Take a maze like this for example, if you
were to follow greedy best-first search, you
would go 16, 15, 14, 13, 12, at this point
you could decide either the 11 or the 13.
And greedy best-first search would look ahead and say,
this path looks pretty good and it's going to-- and none of these values
are any bigger than this 12 and so it would
find this path that takes you from A to B.
But even that path isn't actually the optimal path to take.
The optimal path to take, the shortest path between A and B
is actually this one here, which looks a little counterintuitive
and the reason we didn't catch it is because it
involves like going to the left first and then winding around.
And normally according to this heuristic,
we usually don't want to be going to the left
because we know that our goal, point B where we're trying to get to,
it's off to the right.
So even if you're looking at these heuristic values and looking ahead,
this algorithm might not be perfect.
And so we might try to improve upon this algorithm even more.
And so for one final search algorithm that I'll show you,
the most complex one that we've seen yet,
is an algorithm known as A * search.
A * search tries to build upon the ideas of greedy best-first search, which
is to say we're going to use a heuristic to try and intelligently make choices,
but we're going to try and solve the problem we just saw,
which is that greedy best-first search isn't always optimal.
When it just takes into account the heuristic,
it's not always going to make the best choice
because we might end up choosing a path that's ultimately longer.
What A * search is going to try to realize
is that if we've made it like all the way down here
and now we're at a spot where we could be like 11 squares away
from the goal, that's OK but honestly, being 13 squares away from the goal
much sooner is probably better.
So we can't just take into account the heuristic value,
we should also take into account how far have we gone already.
If I've already traveled many squares and I
find myself pretty close to the goal, I would rather
have traveled fewer squares and find myself close to the goal.
And so A * search is going to try to combine these two
pieces of information, combine the heuristic information that we have seen
here, and also combine how many steps have
I taken so far because that factors into the ultimate optimal solution too.
And so here's how A * search is going to work.
It's going to be the exact same idea as before,
just looking at the heuristic value, but instead of only considering
the heuristic value, we're going to consider taking the heuristic value
and adding to it how many steps we've already taken.
So we take our first step.
And now we've taken one step and we're 16 squares away from the goal
according to the heuristic, for a total of 17.
And then we take our second step and we're 15 squares away from the goal
and we take our third step and we're 14 squares away from the goal,
and we keep going until we reach a decision point after five squares,
we're now 12 away from the goal and now we have a choice,
we could go six squares and be 11 away from the goal
or we could go six squares and be 13 away from the goal, which is worse.
So we're going to make the decision to go up.
So for now, it doesn't seem like we've done any better,
we haven't found the optimal solution just yet.
But notice what will happen, eventually if we
follow this path for long enough we'll end up at a point
where we've made 14 steps and we're estimated
to be five away from the goal, one, two, three, four, five, ignoring the walls.
And now we have a choice, we could be six squares away from the goal
after having walked 15 steps, so 15 plus six that's a total of 21,
or this option is still available to us.
We could be six squares away from the start,
but be 13 away from the goal, six plus 13, that's a total of 19
and that 19 is a smaller number than this 21.
So this 19 is ultimately a better choice as far as A * is concerned.
So by combining information about how far we've traveled
and how far is left to go, we can make a more intelligent choice,
we can say you know what, let's go ahead and try this path
and A * then will ultimately be able to find its way
to get from the starting point ultimately to the goal.
And this algorithm then relies upon having a good heuristic function
and it just so happens that you can prove
that if you pick a good heuristic function,
this algorithm will be optimal.
it will always find the shortest path from point A to point B
and it's not going to get stuck like greedy best-first search might
on a path that isn't actually optimal.
And so there are many of these sorts of search algorithms
that are designed to try and find intelligent ways to find
a solution to some problem, to navigate its way through some landscape.
And so I'll pause here for any questions then
about search algorithms in general.
We've taken a look at what we call classical search, navigating
our way through a maze for example, or finding driving directions as well
as what we might call adversarial search, where there's an opponent
and you're trying to search for the best move in a game of tic-tac-toe
or a game of chess.
DAVID MALAN: Brian, one question from the chat.
Does the assignment of these heuristic values
also take a lot of time for the computer or is that automatic?
BRIAN YU: Ideally you want to find a heuristic that's
going to be efficient to calculate.
So if the time it takes to calculate the heuristic takes a long time, then yeah,
it could be the case that this would be even worse.
But ideally, you want to look for a heuristic that's
going to be very quick to calculate and this
is why sometimes when we're looking at heuristics,
we're going to ignore some of the details that make this more complex.
Like when we're calculating these heuristics,
we're ignoring the walls because having to deal with the walls is
going to make it even--
it's going to make it take longer and longer amounts of time
to be able to figure out these values.
And so by ignoring the walls, we can pretty quickly
calculate just like x, y coordinate wise,
how many coordinate squares are we away from that destination.
Also, I've been labeling all of the squares
in this grid with their heuristic value, just so you can
see what those heuristic values are.
In practice, if our search algorithm never touches a square,
like it never touches any of these squares,
it's not going to bother computing heuristic values for them
because it's not relevant to the search process.
So it'll never actually calculate the heuristic values
for all of these squares, which will save time too.
I have just shown them to you visually so that you can see all of the squares
and what numbers would be assigned to them.
But yeah, really great question.
All right and, Kurt, was there another question?
AUDIENCE: Yeah, I was just wondering if, I
mean, the example that you showed it's using like a map
to actually search through a map, so it kind of
like maps directly onto sort of the concept
but like could this also be used for like textual search
or other kinds of searches through like different kinds of problem
spaces or no?
BRIAN YU: Yeah, this can be used for a lot of different problem spaces.
For text they're usually different approaches
in the world of like natural language processing
but you can use these kinds of search algorithms any time
you have some computer which we'll usually
call like an agent, something that's making decisions, that
has to make certain decisions at certain points,
even if those decisions aren't like geographic decisions about which
way to walk, for example, as long as it's making some decision that moves it
into like a different position, you can often apply these types of algorithms
in order to solve problems.
And so these algorithms are not just good for maze solving,
they can be used in other domains too.
So ultimately what I want to move on to now
is less about just coming up with these algorithms that let the AI figure out
exactly what to do right away, but looking
at a type of artificial intelligence that you've probably
heard of called machine learning.
And machine learning is all about trying to take our AI
and trying to get it to learn, learn somehow from data
or learn from experience.
Much the same way that humans might learn,
that we learn from looking at our environment,
we learn from our surroundings, we learn from our experiences,
and we get something out of those experiences.
And so one type of machine learning is known
as reinforcement learning, where you learn
from positive or negative rewards.
The computer does something well and it gets a reward,
the computer does something poorly, it gets some sort of punishment
and the computer tries to learn from that.
Let's imagine for example, a very simple game
that we might want our computer to play, the computer
is going to try to navigate its way through these tiles
and it's going to try and get to the goal,
similar to what we've seen before, but this time the computer
doesn't know where the obstacles are.
Let's imagine that there are some obstacles in its way highlighted
in red here and if our computer agent, this yellow dot here,
ever hits one of those obstacles, the computer loses this game.
So it hits an obstacle, the computer loses but the computer
doesn't know where the obstacles are.
I'm showing them to you visually but the computer has no idea.
How would the computer try to solve this problem?
How would you try to solve the problem?
Well, all it can do it first is randomly make a choice, randomly guess.
Like let's choose to go to the right, OK we hit an obstacle that was no good.
But the computer now can learn from experience.
As long as it knows once it hits the obstacle that was a bad outcome, well
now in the future the computer can learn, I better not do that anymore,
rather than go to the right, let me try something else, I'll try moving up.
All right, that seemed to have worked better,
let me try making another action and let's try another one,
maybe I'll go down this time.
OK that led to an obstacle, so the computer learns from that too.
It learns that was a bad thing to try, so let's try something else.
Maybe we try going up this time, that too
leads to an obstacle, that was no good, so maybe we'll try going to the right.
That seemed OK, maybe we'll go to the right again.
All right, that led to another obstacle.
And so over and over it's just making mistakes
and we let the computer make those mistakes
but every time it makes a mistake, the computer
is learning something from that.
It's learning what to do or what not to do the next time it
goes through the same process.
And so in the future, it can navigate its way around and eventually
with enough trial and error, it can find its way to the goal.
And once it's found its way to the goal, it'll
remember that too, it'll know I now know exactly what sequence of actions
will take me from the starting point to the goal.
And so in the future I can just keep doing that again and again and again.
So that then is an example of reinforcement learning,
but even with this example here do you see any potential problems
with this approach?
Limitations or downsides to what we've just
done here, reasons why this AI might not be perfect, any thoughts?
Let's go to [? Lexleen. ?]
AUDIENCE: It might not be taking the most efficient path.
BRIAN YU: Yeah, absolutely because it's randomly trying,
eventually it will find its way to the goal
but it might not necessarily find the best path because here there
was a faster path, there was a faster way to get to the goal,
and that was to say once you get here go up instead
and that will lead to a more efficient path.
But because our AI is learning, like whenever it
reaches the goal it learns to do that.
When it doesn't reach the goal learns not to do that.
Our AI doesn't have that ability to find that better path in the future.
And so we could improve upon this.
And this is what we call a trade off between exploring and exploiting
in artificial intelligence.
We want our AI to do both of these things.
We want AI to exploit the knowledge it already has, it knows what to do,
it knows what not to do, we want it to use that information,
but we also want it to explore a little bit.
We want it to sometimes try some new action
that it hasn't tried before because maybe
that'll be even better than the things I've already tried in the past.
So so far our AI in the example just now,
was only ever exploiting the knowledge it already has but it was never
exploring something new.
And so often when we're training AI, we want
it to find some sort of nice balance between the two.
We want it to make good choices, but occasionally take a risk,
try something else, see if maybe we can find a better solution.
And so one strategy for doing this is known as the epsilon-greedy approach
to trying to solve these problems, where we assign a value, epsilon,
which is equal to some proportion, some probability
that our computer is just going to make a random choice.
And so we might say if we generate a random number
and it's less than epsilon, which in this case happens like 10% of the time,
then let's go ahead and make a random move,
rather than make an intelligent, smart move just pick a move randomly
and the rest of the time, 90% of the time,
make the move that we know to be the best, the one with the highest value
we know of so far.
And this will often result in a nice balance.
90% of the time our AI will make good choices
that it knows to be good choices, but 10% of the time
it'll make a new choice, something random
and maybe it'll stumble across something bad
and know to avoid that in the future, but maybe it'll
come across something better and know to do that better in the future as well.
And so I'll show you a real live demo of this actually.
Years back, the Italian Institute of Technology
was working through an example of trying to do something just like this,
but before we move on I think there's a question from the chat?
DAVID MALAN: Brian, someone asks, is this related
to genetic algorithms, this approach?
BRIAN YU: Genetic algorithms are another type of this type of learning.
We're going to actually going to talk about genetic algorithms in just
a moment.
So we'll get there very shortly.
But yes, definitely something related.
So the Italian Institute of Technology a couple of years
back tried to teach a robot how to flip pancakes.
Something that you might have done before or seen someone else
do before but in practice, it's difficult to encode in a robot
exactly how to do that.
Exactly what moves to make, exactly how to move its robotic muscle to be
able to flip a pancake effectively.
So rather than try to program every last movement into the computer,
they just let the robot learn via reinforcement learning.
Every time it flipped a pancake incorrectly it
learned what not to do in the future and every time it
flipped a pancake correctly, it learned what to do in the future.
And so I'll go ahead and pull up an example of this now.
And so what we're going to take a look at here is a artificial pancake.
And initially, the human researcher shows
the robot what success looks like.
The robot needs to know what is success and what
is failure so the human demonstrates.
Here is what it looks like to actually do the pancake flipping
by demonstrating exactly what motion to make
and what it feels like to successfully flip a pancake
and then we let the robot try it.
All right, that was his first try, not to successful.
We'll try it again.
Here's after three tries.
OK, not great but it's learning.
Every time it does something wrong it learns what not to do in the future.
He has five tries, he has 10 tries, not great.
And now after 15 tries or so, or 11 tries I guess, we'll see what happens.
OK so not great, right?
It takes a while to learn these kinds of techniques to learn, here's 15 tries,
all right but finally after enough tries once you do enough practice with this.
Here's after 50 tries and we now actually
have a robot that has learned to successfully perform this task,
not because human programmers told it exactly how to do so,
but because it learned from that failure and learned from experience.
And once it knows how, it knows exactly what to do in the future.
It can continually replicate that behavior over and over again
once it's trained to be able to perform that task.
So that then is how you might take advantage of this idea of reinforcement
learning but someone in the chat brought up another approach
to this type of thing known as genetic algorithms or genetic learning.
And this is where a lot of machine learning
has taken inspiration from the human brain, how humans learn
and how nature works and because nature has managed
to evolve intelligent beings, why couldn't we
try to do the same thing in a computer as well?
And so in nature, you have generations of populations that evolve over time,
where the most fit organisms survive and are
able to evolve and mutate and change over time to become better and better
at adapting to their environment.
And so one strategy, one approach to trying
to build intelligent machines is rather than program one algorithm that
is really good at performing a task, let's
just create a lot of algorithms that are really bad at performing the task
because that's much easier to do.
But we'll let them evolve, we'll let them try some task
and after they do it, they won't do very well
but we'll take the ones that did the best
and replicate them and mutate them and let them try again.
And then repeat this generation after generation,
eliminating all of the computer programs that don't perform well
but duplicating and mutating the ones that do.
The pseudocode for which might look a little something like this.
We're going to start by making an initial generation of candidates
randomly, where each candidate is some program designed to try and solve
some task but rather than program it intelligently
the way you've been doing all semester, we're
just going to program them randomly to just make random choices
and we're going to repeat this process until eventually they're successful.
We're going to for each one of these candidates calculate its fitness,
calculate how good is it at performing the task that it's designed to do.
And then we're going to remove the least fit candidates.
Maybe take the half of them that didn't do very well,
eliminate those but take the ones that did do well
and make a new generation from the remaining candidates, duplicate them,
make a few mutations to them randomly just to change things up
and to see how things work in order to try to create a better generation.
And over time as we repeat this process, in much the same way that evolution
is able to continually produce better and better organisms that
are more and more fit, we can do the same thing with our algorithms
too, producing better and better algorithms over time.
I have another demo to show you of this.
Here is a simulation of some self-driving cars that
have not been programmed how to drive but are starting out driving entirely
randomly each of these rectangles you see
is one example of a virtual self-driving car.
Each of the little crosshairs you see, the little Xs,
are sensors that the car has access to.
So the car has access to data about how far away in any given direction
particular obstacles are and what these cars are trying
to learn is how to drive through some sort of environment
while not crashing into anything.
And initially they didn't do very well, you
notice they were crashing almost immediately but now we're
about six generations in, seven generations in,
they're starting to do a little bit better.
They're starting to get a sense for like turning when you run into a wall.
Even when they get to new environments they
haven't necessarily seen before, they're starting to do a little bit better.
But of course, they're still not great, they're
still crashing quite frequently.
Sometimes a generation does even worse than the generation before it,
because it's not always going to be the case that when
you make random mutations those mutations are not necessarily
going to be better.
Sometimes the mutations actually end up being a little bit worse.
And so they might move backwards a little bit.
But over time, generation after generation,
you're hopefully seeing that now 10 generations in, these cars in general
are doing a whole lot better than they were before
and every generation we're taking whichever cars made it the furthest,
duplicating those, eliminating the rest, and moving forward.
Is there a question in the chat?
DAVID MALAN: Yeah, with regard to the pancakes,
how did the robot know what was wrong with the previous pancake flips?
In the case of the cars how does the car know that it erred?
BRIAN YU: Yeah, so whenever you're doing anything with reinforcement learning,
whether it's the pancakes or these robots here,
the programmer still needs to tell the AI what does success look like
and what does failure look like.
So in the pancake example, we trained the pancake flipper
to be able to know that when you're flipping this pancake when it's first
taught what does it look like when it's successful.
So it gets a feel for that and it was probably
also told that if the pancake falls, that's not a good thing for example.
And that's not something that the AI should try to do.
And in this case, I assume these cars have
been programmed to be told that if you crash into something that that is not
good, that the car presumably can detect after it's crashed into something
and so it probably also has some sense of like how far it was able to drive,
such that we could duplicate the ones that did drive the furthest
and not the ones that didn't and let's see how this car does,
it was so close to the end, didn't quite make it.
Maybe give it one more generation and we'll see how this generation does.
And all right, so it's navigating these turns,
looks like a whole bunch didn't make it but as long
as we get one successful one, we can learn
from that successful one in the future.
Here's the ending, looks like they crashed but and all right, it
looks like one car was finally able to make it to the end
and was able to successfully learn that task of how to navigate
through this environment of mazes.
So I'll pause here for questions then about reinforcement learning
and how these ideas might have worked.
And, Samuel, did you have a question?
AUDIENCE: Yes.
So with the genetic algorithm, the car one specifically,
so all the cars are learning from each other as each one crashes?
BRIAN YU: It's not so much that the cars are learning from each other
that we're generating new cars based on the cars that
were previously successful.
The idea being that if we run 10 cars and see
how far they go, we take the five that went the furthest,
we eliminate the other five that didn't make it very far
but then we duplicate and repeat the ones that
did do well, such that in the future, hopefully this new generation of cars
will make it a little bit further.
And generation after generation, the hope
is that we're able to make it a little further along the road
until eventually as you saw like 15 generations in,
we were able to get some cars that could perform the task successfully.
Let's go now to Josiah.
AUDIENCE: Is the car specifically learning just from the track?
I mean, when you change the track, do we need another, I mean,
do we need to start from zero again or?
BRIAN YU: Yeah, so if the track were different would it have to learn again?
Hopefully not.
Hopefully what the cars were learning was
in this case was learning based on sensor data,
like how far away a wall is in any direction, which way to turn.
And the goal is for this type of approach to generalize.
And I mean, hopefully actual self-driving cars in the real world
are not trained this way.
But you would hope that as they're trained on sample environments,
that when you put them in a different environment
they would be able to generalize their knowledge
to be able to apply similar techniques.
That if in a real world setting you take a car and put it on a road
that it's never seen before, hopefully it's
seen enough examples of things that are like it, sensor data
that it recognizes, that it's able to make an intelligent decision based
on that.
So yeah, the hope is and the goal in many cases with AI
is to be able to generalize this knowledge beyond just
a specific example.
Any other questions?
Yeah, let's go to [? Yagonch. ?]
AUDIENCE: Yeah, so can these algorithms ever reach like a bottleneck,
just like in real life evolution, there are branches
and some branches just reach a bottleneck.
So is that possible here [INAUDIBLE]?
BRIAN YU: Yes, it's definitely possible that there might be--
the algorithms might end up converging to something that seems pretty good
and it doesn't seem like any mutations are doing any better,
but it turns out a totally different algorithm
might actually do better than that.
That's what we will often call a local maximum
in the context of artificial intelligence,
where there is some better approach, there is some better algorithm
but we can't necessarily find it.
There are other strategies for trying to deal with that problem.
But it is definitely a challenge we're thinking about.
And one more question.
Let's go to Sophia.
AUDIENCE: I have a question about how the fitness is calculated.
Like in both of these cases, is it like [INAUDIBLE] motors that
are running or here like the distance?
BRIAN YU: Yeah, in the case of the pancake, it was probably
like a binary of just like did the pancake end up
landing in the pan or not, was our way of calculating
the fitness of that particular example.
In the case of the cars, we would probably calculate fitness
based on distance traveled, whichever cars ended up traveling the furthest,
that would be our definition of fitness and that's
really the part the programmer needs to be involved in.
The programmer needs to decide, what does it
mean to be most fit, what does a bad example look like and using that,
once the computer knows what success looks like and what failure looks like,
then it's able to learn from that to be able to do better in the future.
All right, so that was genetic algorithms,
which is one example of computers that are able to learn from the way
that humans learn, learning from the way that nature works for example,
but computer scientists didn't really stop there.
There are other examples that we can do to add to this as well.
And so one other example of using this idea of reinforcement learning
and using genetic algorithms might be in video recommendations for example,
where you could have some watch history and the way
that an algorithm like YouTube or Netflix might suggest videos for you
to watch is via this reinforcement process,
that it will just try suggesting videos to you and learn from experience.
If it suggests a video to you that you like, that you click on
that, you watch all the way through, well
then the algorithm learns in the future, let's recommend
more of those sorts of things.
That's like the car traveling very far and so we
learn to do more of that in the future.
If they recommend a video to you and you don't click on it
you don't ever watch it, well then it's probably not
going to recommend that to you in the future.
And it's probably going to learn from that experience as well.
And so this is one example of computer science learning from nature,
learning from the way that humans are.
Another place that's happened too is by looking at the human brain.
That the human brain consists of neurons and those neurons are connected
to one another and they pass information from one to another,
electrical signals flow through one neuron to another neuron
and that's how brains are able to make these very
sophisticated kinds of computations.
And this is what we might call a neural network, a collection of these neurons.
And one place that AI has been looking into especially recently gaining
in popularity, has been trying to develop artificial neural networks.
Instead of using a biological neuron we just
use what we might call an artificial neuron or a unit.
And you can think of this unit as just storing some value,
like some electrical signal for example, like you might find in the human brain,
now just in a digital format and these artificial neurons,
these units can be connected to each other
in sort of an input that translates into an output sort of format
where this arrow represents some sort of calculation, some calculation that
is taking this value on the left and transforming it
into that value on the right.
And neural networks are usually not just one input unit and one output unit,
but they can be more complex.
You might have a neural network with two different inputs, each of which
connects to an output or even more sophisticated neural networks
like this one, where you have multiple layers of these units that are all
connected to each other, each of these arrows performing
some sort of calculation and if you've ever
heard the term deep learning, this is often what that's referring to,
this idea of deep neural networks with many layers, each of which
is performing calculations.
And ultimately using some linear algebra,
these neural networks are able to figure out
exactly how to tune these calculations to translate input into some output.
If you give a neural network enough data it can learn from that data,
it can learn exactly how to set these various different arrows
to be able to calculate some task, to be able to translate
some input into some output.
So for example, that might take the form of handwriting recognition.
How exactly do we train computers to be able to learn
how to recognize handwriting given all the different types of handwriting?
Well, one way to try to do that is by using a neural network,
setting up a network of all of these neurons and all of these connections
and then you give to that neural network a whole bunch of data.
I give to the neural network a whole bunch
of already existing handwritten digits, each of which is labeled.
So the computer knows which image corresponds to which digit.
This data set you're looking at here is a very famous data
set of handwritten digits called the MNIST data set,
and given all of this data the computer can start to train the neural network
and start to figure out exactly what calculations
to run at each layer of the neural network
to be able to translate the input into the output,
to be able to translate like a screenshot of what looks
like a handwritten number eight, that we all could tell is the number eight
but might be difficult for us to describe exactly how a computer could
figure that out, but via the neural network,
by training the neural network on all of the sample data,
it's able to learn some sort of function that
can translate this input, this handwritten digit
into the output, what the actual digit happens to be.
And these neural networks have proved to be incredibly versatile
and we won't get into all the math here because it
does get a little bit more complex, but it's used all over the place.
It can be used for email spam detection, where
if you give the computer a whole bunch of data, a whole bunch of emails,
some of which are labeled spam and some of which are not,
it can learn a function.
It can learn exactly how to tune that neural network to be able to predict,
for any given email, whether it's spam or not.
And really the key factor here to making these networks work
is having access to large amounts of data.
And this is why a lot of companies now are doing a lot of work
and trying to get a lot of data and use that data in training
their machine learning models, it's because the more data that you have,
the better you can make these algorithms because the better you can tune them
to all the different types of inputs there might be,
to help to make them even more accurate in the future,
to be able to test these networks to see how well they work.
And every time you're interacting with websites online,
you're often helping to provide some of that data.
Every time you go to your email app for example
and you mark an email as spam, that email app might be learning from that,
learning OK this type of email, that's an example of a spam email.
And so it learns in the future to do a better job
of trying to do that classification.
And likewise, every time an email is marked as spam
and you have to tell the computer, you know
what, that wasn't spam the computer is learning from that too.
It's more data that the computer can use to help to inform its algorithm
and the way that it's working.
And so for one final example, we can take a look at how images like this
were actually generated.
How could a computer possibly get an image like this
and generate it and make something that looks very much like a real person,
even though it's not actually a real person?
Well, it's done using the exact same technique,
using a neural network that learns how to translate inputs
into outputs by having access to a large amount of data.
In this case, having access to many, many photos of real people,
so the computer can start to get a sense for what a real person looks like,
it can start to train the network in that way.
And then rather than build the entire person all at once,
build it up step by step.
A computer generating a photo like this, this is a pretty complicated task,
it's pretty difficult to do.
But you know what's easier is generating that.
That is 16 pixels it doesn't look like a person at all
but this a computer could do pretty readily,
just generate what seems to be a whole bunch of kind of random looking pixels.
But then you would train the computer to add a little bit of detail
to this image to be able to learn if this were a real image,
how would I add a little more detail to it to make it look a little bit more
like what a person would look like?
And it does so again by having access to large amounts of data
many, many photos of people, so it can begin to learn from that experience.
So the computer learns how to take this image
and turn it into this for example.
Still doesn't really look like a person but it
looks a little more like a person.
It's got a higher resolution.
You can maybe make out that there is some hair here and a face here.
And then the algorithm learns how do you take an image like this, an 8 by 8 grid
and turn it into a 16 by 16 grid.
Now this, I mean, it still doesn't look like a person,
but it looks a little more accurate.
And over time we can follow these steps one
after another adding more and more detail.
Until eventually, the computer is able to generate an entire image that really
looks like a person, that's very hard to distinguish just
by this input to output process.
Learning some mapping from inputs to outputs
by having access to a whole lot of data.
So before we wrap up here I'll pause for any final questions
about artificial intelligence, any of the algorithms
we looked at for searching, for learning or anything like that?
Any final questions?
Yeah, Sophia, go ahead.
AUDIENCE: I had a question about like with the fitness,
how is all the I guess, like data-- you mentioned they get regenerated
like the successful ones, but I was wondering
like how is all that data sort like what the success was exactly,
but fitness is just like a score it's hard to know
like exactly what decisions it made that said it was successful.
BRIAN YU: Yeah, and that's actually one of the trickier things about machine
learning, that we can train these machine learning models
to be very, very good but it's not always
immediately apparent to us like what it was doing in order to be successful.
And this is an active area of research within machine learning,
including some faculty at Harvard that work on this too,
which is the interpretability of machine learning results.
Like the algorithm becomes very, very good at recommending a video to you
or generating an image of a person, but it's hard for a person
to look at that machine learning model and understand
how it arrived at that conclusion.
Ultimately, in many cases, people just throw their hands up and say,
we don't really care how the algorithm is doing it,
as long as the algorithm is doing it successfully
and eventually produces good results, we'll
just take the ones that are doing the best and use those,
even if we don't necessarily understand exactly how those algorithms are
working.
And that's definitely an area of concern for some people
and an area of research for others that are looking into these types of tools
and technologies.
Is there a question in the chat maybe?
DAVID MALAN: A final question from the chat, Brian.
Every time I choose the parts of the picture that contain traffic lights
or crosswalks to prove I am not a robot, am I training Google's driverless car?
BRIAN YU: Maybe not Google's necessarily, but certainly
a lot of times when you're doing that type of thing.
I mean, in one part it's to verify that you are in fact human.
That is one of the purposes of those things,
to make sure that robots aren't signing up for websites, for example.
But certainly it could be just giving more examples of labeled data.
That oftentimes what machine learning models rely on
is labeled data where you have like a digit, a handwritten digit,
and you have a label of "this is the number 2," or "this is the number 8."
And so the computer can then use those digits along with those numbers
in order to figure out how to learn how to take handwritten digits
and convert it to individual numbers.
And so having access to that kind of labeled data ultimately
ends up being really, really valuable.
All right, so that's it for artificial intelligence for today.
Thank you all so much and we'll see you next time.
[MUSIC PLAYING]