YouSub
Untitled

en English

Untitled English subtitles

0 downloads · 835 lines · added Nov 18, 2015

Report a problem
What's wrong?
Advertisement

English transcript

PATRICK WINSTON: I have extremely bad news.
Halloween falls this year on a Sunday.
But we in 6.034 refuse to suffer the slings and arrows
of outrageous fortune.
So we've decided that Halloween is today, as far
6.034 is concerned.
Kenny, could you give me a hand, please?
If you could take that and put it over there.
STUDENT: [INAUDIBLE]?
PATRICK WINSTON: Mm hm.
Just give it to them.
You can take as much of this as you like.
The rest will be given to that herd of stampeding freshman
that comes in after.
It's a cornucopia of legal drugs.
Chocolate does produce a kind of mild high, and I recommend
it before quizzes and giving lectures.
I have a friend of mine, one of the Nobel laureates in
biology, always eats chocolate before he lectures.
Gives him a little edge.
Otherwise, he'll be flat.
So I recommend it.
It will take, I suppose, a little while to digest that
neural net stuff.
A little richer than usual in mathematics.
So today, we're going to talk about another effort at
mimicking biology.
This is easy stuff.
It's just conceptual.
And you won't see this on the next quiz.
But you will see it on the final.
It's one of those quiz five type problems, where I ask you
questions to see if you were here and awake.
So a typical question might be, Professor Winston is a
creationist, or something like that.
Not too hard to answer.
In any event, if it's been hard to develop a real
understanding of intelligence, occasionally the hope is that
by mimicking biology or mimicking evolution, you can
circumnavigate all the problems.
And one of those kinds of efforts is
ever to imitate evolution.
So we're going to talk today about so-called genetic
algorithms, which are naive attempts
to mimic naive evolution.
Now, I realize that most MIT students have a basic grasp of
sexual reproduction.
But I've found in talking with students that many times,
they're a little fuzzy on some of the details.
So let's start off by reflecting a little bit about
how that works.
So let's see, we need pink and blue.
And here's our cell, and here is its nucleus, and here are
mommy and daddy's chromosomes.
We'll just pretend there's one pair.
Now ordinarily, in ordinary cell
division, you get two cells.
Both have a nucleus, and the process of producing them
involves the duplication of those chromosomes.
And then one pair ends up in each of the child cells, and
that's all there is to that.
That's mitosis.
But then, when we talk about reproduction, it's more
complicated because those chromosomes get all twisted
up, and they break, and they recombine.
So when we talk about the cells that split off from one
of these germ cells, it's no longer appropriate to talk
about the pink one and the blue one, because the pink one
and the blue one are all mixed up.
So you get two chromosomes here and two here.
But through some miracle of nature, which has always
amazed me, these two cells split, in turn, into four
cells altogether.
And each of those four cells at the bottom gets one of the
chromosomes that was produced by the twisting up of the rope
and recombination.
Then, along comes a special occasion.
And now we can think of this as being a blue one and this
as being a pink one.
And they come together, and you get a new person, like so.
Note that your mother and father's chromosomes are
never, never recombined.
It's your grandparents chromosomes that recombine.
So that's what it's like.
And the main thing to note about this is--
well, a couple things.
If you happen to be female, this part of the process--
this part over here--
took place before you were born.
If you happen to be male, it's going on right now as we
speak, which probably explains something.
But in any event, it's going on right now.
But whenever it goes on, there are lots of opportunities for
throwing dice.
So God threw all the dice before you were born, if you
happen to be a female, in this part of the process over here.
Then, of course, more dice got thrown here when the decision
was made about which particular cells got to fuse
to form a new individual.
So I want to beat on this idea of lots of choice.
When we talk about genetic algorithms, and we talk about
nature, there are lots of choices in there.
And that means there are lots of choices to intervene, to
screw around, to make things work out the way you want.
But in any event, there we are.
That's the basic idea, and it all starts with chromosomes.
So we could think of implementing something that
imitates that with the ACTG stuff that you learned all
about in Seminar 1.
But we're computer scientists.
We don't like Base 4.
We like Base 2.
So I'm going to just suggest that our chromosomes are
binary in this system that we're going to build.
So that might be a chromosome.
And it doesn't have to be binary.
It can be symbolic for fall I care.
But it's just some string of things that determine how the
ultimate system behaves.
So it all starts out, then, with some of these
chromosomes, some of these simulated chromosomes,
simulated, simplified, and naive.
And there's a population of chromosomes.
The population of chromosomes-- it might be
subject to a little bit of mutation.
That is to say, a zero becomes a one, or a
one becomes a zero.
That happens a lot.
That mutation stuff happens over here when things get
twisted up and recombined.
There are copying errors and stuff.
Cosmic rays hit it all the time.
All sorts of reasons why there might be a
single point of change.
That produces the mutation effect.
So here, we have a population that starts off over here.
And some of those things are subject to mutation.
And you'll note, here's a whole bunch of choice already.
How many of these mutations do you allow per
chromosome, for example?
How many of the chromosomes just slip
through without any mutation?
Those are choices you can make.
Once you've made those choices, then we have the
crossover phenomenon.
Let's identify one of these guys as the pink one and one
of these guys as the blue one.
And so now we have the pink one cruised along as well as
the blue one.
The pink one and the blue one cross and produce a new
chromosome, just like in nature.
So we take the front part of one, back part of the other,
and we fuse them together.
And some may slip by without any of that, like so.
Well, these things are meant to be combined in pairs, like
so, but they may not have any crossover in them.
So you have another set of choices.
How many crossovers do you allow per recombination?
You get another set of choices.
So now we've got a population of modified chromosomes
through mutation and crossover.
So the next thing to do is we have the genotype to phenotype
transition.
That is to say the chromosome determines the individual.
It may be a person.
It may be a cow.
It may be a computer program.
I don't care what.
But that code down there has to be
interpreted to be a something.
So it is the genotype, and it has to be interpreted to be
something which is the phenotype, the thing that the
stuff down there is encoding for.
So here, we have a bunch of individuals.
Now, each of those individuals, because they have
varying chromosomal composition, will have a
different fitness.
So these fitnesses might be--
well, who knows how they might be scored.
But we're computer scientists.
We might as well use numbers.
So maybe this guy's fitness is 88, and this guy's fitness is
77, and so on.
So now that we've got fitness--
by the way, notice all the choices involved there--
choice of how you interpret the genotype, choice about how
the phenotype produces the fitness.
And now we have a choice about how the fitness produces a
probability, like 0.8 and 0.1, or something like that--
probability of survival into the next generation.
So now, once we've got those probabilities, we actually
have selection.
And those phenotypes out there produce genotypes, a new set
of chromosomes, and that completes our loop that goes
back in there.
And so that's the new generation.
Sounds simple.
So if you're going to make this work, of course, you have
a million choices, as I'm going to emphasize over and
over again.
And one of your choices is, for example, how do you
compute the probability of survival to the next
generation given the fitness?
So we have to go, somehow, from numbers like these to
probabilities like those.
So I'm going to talk about several ways of doing it.
None of them are magic.
None of them was specified and stipulated by God
as the right way.
But they have increasingly good properties with respect
to this kind of processing.
So the simplest thing you can do--
idea number one for computing the--
see, what you do is you get this whole bag of individuals,
and you have to decide who's going to survive to the next
generation.
So at each step, everything in the bank has a probability of
being the one you pick out and put in the next generation.
So at any step, the sum of the probabilities for each of
those guys is 1, because that's how
high probability works.
The probability of a complete set, added all up, is
probability of 1.
So one thing you can do is you can say that the probability
that you're going to draw individual i is equal to, or
maybe is proportional to, the fitness of that individual.
I haven't completed the expression, so it's not a
probability yet, because some piece of it won't add up to 1.
How can I ensure that it will add up to 1?
That's easy.
Right.
All I have to do is divide by the sum of the
fitnesses over i.
So there's a probability measure that's produced from
the fitnesses.
Yeah.
STUDENT: You need to make sure that the
fitnesses aren't negative.
PATRICK WINSTON: Have to make sure the fitnesses are what?
STUDENT: Aren't negative.
PATRICK WINSTON: He says I have to make sure the
fitnesses aren't negative.
Yeah, it would be embarrassing if they were.
So we'll just [? strike ?] anything like that as 0.
You've got a lot of choice how you can calculate the fitness.
And maybe you will produce negative numbers, in which
case you have to think a little bit more about it.
So now, what about an example?
Well, I'm going to show you an example.
Why don't I show you the example.
What we're going to do is we're going to have a genetic
algorithm that looks for an optimal value in a space.
And there's the space.
Now, you'll notice it's a bunch of contour lines, a
bunch of hills in that space.
Let me show you how that space was produced.
The fitness is a function of x and y, and it's equal to the
sine of some constant times x, quantity squared, times the
sine of some constant y, quantity squared, e to the
plus x plus y divided by some constant.
So sigma and omega there are just in there so that it kind
of makes a nice picture for demonstration.
So there's a space.
And clearly, where you want to be in this space is in the
upper right-hand corner.
That's the optimal value.
But we have a genetic algorithm that
doesn't know anything.
All it knows how to do is mutate and cross over.
So it's going to start off with a population of 1.
It's a little red dot down in the lower left.
So here's how it's going to evolve.
There's going to be s chromosome consisting of two
numbers, an x number and a y number, like,
say, 0.3 and 0.7.
Here's another one, which might be 0.6 and 0.2.
So the mutation operator is going to take one of those
values and change it a little bit.
So it might say, well, we'll take 3, and we'll make it 0.2.
And the crossover operation is going to exchange the x and y
values of pairs.
So if we have a crossover here, then what we're going to
get out from this one--
well, we're going to get out a combination of these two.
And it's going to look like this.
Because what we're going to do is we're going to take the x
value of 1 and combine it with the y value of the other one.
So this is going to be 0.2--
my mutated value and 0.2--
and this is going to be 0.6 and 0.7.
So that's how my little genetic algorithm heck is
going to work.
So having coded this up, we can now see how it flows.
Let's run it 10 generations.
So the population is rapidly expanded to some fixed limit.
I forgot what it is--
30 or so.
And we can run that 100 generations.
And so this seems to be getting stuck, kind of, right?
So what's the problem?
The problem is local maxima.
This is fundamentally a hill-climbing mechanism.
Note that I have not included any crossover so far.
So if I do have crossover, then if I've got a good x
value and a good y value, I can cross them over and get
them both in the same situation.
But nevertheless, this thing doesn't seem to be
working very well.
STUDENT: Professor, I have a question.
PATRICK WINSTON: Yeah.
STUDENT: That picture is just the contour
lines of that function.
PATRICK WINSTON: The contour lines of that function.
So the reason you see a lot of contour lines in the upper
right is because it gets much higher because there's that
exponential term that increases as you
go up to the right.
So I don't know, it looks--
let's put some crossover in and repeat the experience.
We'll run 100 generations.
I don't know.
It just doesn't seem to be going anywhere.
Sometimes, it'll go right to the global maximum.
Sometimes it takes a long time.
It's got a random number generator in there, so I have
no control over it.
So it's going to get there.
I couldn't tell whether the crossover was
doing any good or not.
Oh, well, here's one.
Let's make this a little bit more complicated.
Suppose that's the space.
Now it's going to be in real trouble, because it'll never
get across that moat.
You know, you would think that it would climb up to the x
maximum or to the y maximum, but it's not
going to do very well.
Even with crossover, it's just not going to do very well,
because it's climbing up those local hills.
Anybody got an idea about one simple thing we could do to
make it work better?
Yeah, you could increase step size, right?
Let me you see if that will help.
You know, even that doesn't seem to help.
So we have to conclude-- do we conclude that
this is a bad idea?
Well, we don't have to conclude it's a bad idea yet,
because we may just look at it and ask why five times.
And we might ask, well, maybe we can get a better mechanism
in there to translate fitness into probability of survival.
Using this formula is kind of strange, anyway, because
suppose temperature is one of your fitness characteristics.
The hotter, the better.
Then the ratio of the probability that you'll
survive versus the person next to you, that ratio will depend
on whether you're measuring the temperature in Celsius or
Fahrenheit, right?
Because you've shifted the origin that shifts the ratio
that shifts the probability of success.
So it seems kind of strange to just take these things right
straight into probabilities.
So a better idea--
idea number two--
is to say, well, shoot, maybe we don't care about what the
actual fitnesses are.
All we really care about is the rank order of all the
candidates.
So the candidate with the most fitness will have the most
probability of getting into the next generation.
The candidate with the second-most fitness will have
the second-highest probability, and so on.
But we're not going to use the actual fitnesses themselves to
make the determination.
Instead, what we're going to do with this
mechanism number two--
this is the rank space method--
is this.
We're going to say that the probability of the
highest-ranking individual of getting into the next
generation is some constant P sub c, which, of course, you
can select.
You have another choice.
Then, if that guy doesn't get selected, the probability of
the second-highest-ranking individual getting in the next
generation is going to be the probability that that guy
didn't get in there.
That's 1 minus P sub c times the same probability constant.
And so you can see how this is going.
P3 will be equal to 1 minus P sub c squared terms P sub c.
P sub n minus 1 will be equal to 1 minus that probability
constant to the n minus--
n minus 2 times P sub c.
And then there's only one individual left.
And then if you got through all these guys and haven't got
anybody selected, then you've got to select the last guy.
And so the probability you're going to select the last guy
is going to be 1 minus P sub c to the n minus 1.
So it's a probability you've missed all those guys in the
first n minus 1 choices.
Yeah, it is, honest to God.
See, this is the probability that this last guys is going
to get selected.
It's not the probability that it's the last guy getting
selected, given that the others haven't been select.
Trust me, it's right.
Are you thinking it ought to be 1?
STUDENT: What?
PATRICK WINSTON: Were you thinking it ought to be 1?
STUDENT: No, I was thinking that I was wondering why you
were re-rolling the dice, so to speak.
PATRICK WINSTON: You are re-rolling the dice.
You've got a probability each time, except for the last
time, when, of course, you have to take it.
There's nothing left.
There's no other choice.
STUDENT: I have a question.
PATRICK WINSTON: Yeah, [INAUDIBLE].
STUDENT: So when you jump from [INAUDIBLE], that makes sense.
[INAUDIBLE] you're saying [INAUDIBLE].
PATRICK WINSTON: It's the probability [INAUDIBLE] the
first two choices.
STUDENT: Yeah, but the second choice had probability one
minus P sub c times P sub c, not--
PATRICK WINSTON: Think about it this way.
It's the probability you didn't choose the first two.
So the probability you didn't choose the first one is one
minus P sub c.
The probability you didn't choose the next one, as well,
because you're choosing that next one with probability P
sub c, it's the square of it.
So that might work better.
Let's give it a shot.
Let's go back to our original space choice, and we set and
switch to the rank fitness method.
And we'll run out 100 generations.
Whoa!
What happened there?
That was pretty fast.
Maybe I used a big step size.
Yeah, that's a little bit more reasonable.
Oops--
what happened?
It's really getting stuck on a local maximum.
So evidently, I've choosed a constant P sub c such that it
just drove it right up the nearest hill.
On the other hand, if I change the step size a little bit,
maybe I can get it to spread out.
I sure did.
And now that it's managed to evolve over there to find the
maximum value, now I can clamp down on the step size again.
And now it shows no more diversity.
It's just locked on to that global maximum.
So this is not unlike what evolution sometimes does.
Sometimes, species collapse into a state where they don't
change for 500 million or 600 million years, like sharks,
for example.
Sometimes, they only survive if they've got a lot of
diversity built into their way of life so that they can
adjust to habitat changes.
Now, when you increase the step size, because you're
stuck on a local maximum, it's like heating up a metal.
You make everything kind of vibrate
more, make bigger steps.
So this kind of process, where you may start with a big step
size and then gradually reduce the step size, is called
simulated annealing, because it's like letting
a metal cool down.
So you start off with a big temperature-- big step size--
that covers the space.
And then you slowly reduce the step size, so you actually
crawl up to the local maxima that are available.
So that seemed to work pretty well.
Let's see if we can get it to work on the harder
problem of the moat.
So it's not doing very well.
Better increase the step size.
No, it's still kind of stuck.
Even though it's got the capacity to cross over, it's
so stuck on that lower right-hand corner, it can't
get up that vertical branch to get to a point where a
crossover will produce a value up there in the upper
right-hand corner.
So we're still not home yet.
So what's the trouble?
The trouble is that the fitness mechanism is just
driving things up to the local maximum.
It's just terribly unfortunate.
What to do?
Well, here's something you could do.
You can say, well, if the problem is we've lost the
diversity in our population, then we can measure the
diversity--
not only the fitness of the set of individuals we're
selecting fr
…

Need subtitles from another video?