Advertisement
English transcript
PROFESSOR PATRICK WINSTON: Ladies and gentlemen, the
engineers drinking song.
Back in the day, I've drunk quite a lot to that song.
And as drinking songs go, it's not bad.
I caution you, however, before playing this song in the
presence of small children, audition it first.
Some of the verses are sufficiently gross as to make
a sailor go beyond blushing.
It's an interesting song because there are an infinite
number of verses.
Here's the mathematical proof.
Suppose there were a finite number of verses.
Then there would be a last verse.
And if there were a last verse, then some drunk alumni
would compose a new one.
Therefore, there is no last verse, the size is not finite,
and there are an infinite number of verses.
I play it for you today because I'm an engineer.
I like to build stuff.
I build stuff out of wood.
I build stuff out of metal.
I build stuff out of rocks.
And I especially like to write programs.
I don't know, sometimes people come to me and say, I'm
majoring in computer science, but I don't
like to write programs.
I've always been mystified by that.
I mean, if you want to show how tough you are, you can go
bungee jumping or drive a nail through your hand or something
like that instead.
But I've written quite a few programs for demonstrating
stuff in this subject.
They're all written in Java, principally because I can
therefore make them available to you and to the rest of the
world by way of Web Start.
A few weeks ago, I was mucking around with the system and
broke the version on the server, and within 15 minutes,
I got an email from somebody in the depths of Anatolia
complaining about it and asking me to bring it back up.
This particular program is patterned
after an early AI classic.
And it was the business end of a program written by Terry
Winograd, who became, and is, a professor of computer
science at Stanford University--
which is on the west coast for those of you--
on the strength of his work on the natural language front end
of this program.
But the natural language part is not what makes it of
interest for us today.
It's more the other kinds of stuff.
Let's pile these things up.
Now, I'm going to ask to do something, maybe put
B2 on top of B7.
Not bad.
How about B6 on B3?
This program's kind of clever.
Let me do one more.
Let's put B7 on B2.
OK, now let's see.
Maybe B5 on B2?
B4 on B3 first, maybe?
Oh, I must have clicked the wrong button.
Oh, there it goes.
OK.
Let's put B4 on B1.
Agh, my mouse keeps getting out of control.
Now, let's put B1 on B2.
This is an example I'm actually going to
work out on the board.
Oh, I see.
My touch pad accidentally got activated.
B1 on B2.
Now, let's ask a question.
OK.
Well.
SPEAKER 2: [SINGING]
PROFESSOR PATRICK WINSTON: Stop.
SPEAKER 3: [LAUGHTER]
PROFESSOR PATRICK WINSTON: Had enough of that.
Let's see.
Why did you put--
why did you want to get rid of B4?
OK, one--
SPEAKER 2: [SINGING]
PROFESSOR PATRICK WINSTON: Maybe they think, that's what
happens when you use software you write yourself.
Why did you want to clear the top of B2?
Did I do that?
Why did you clear the top of B1?
OK.
SPEAKER 2: [SINGING]
SPEAKER 3: [LAUGHTER]
PROFESSOR PATRICK WINSTON: Oh, it's haunting me.
Yeah.
So the drinking song is easily offended, I guess.
But I won't develop that scenario again.
What I want to show you is that this program looks like
it's kind of smart, and it somehow can answer questions
about its own behavior.
Have you ever written a program that's answered
questions about its own behavior?
Probably not.
Would you like to learn how to do that?
OK.
So by the end of the hour, you'll be able to write this
program and many more like it that know how to answer
questions about their own behavior.
There have been tens of thousands of such programs
written, but only by people who know the stuff I'm going
to tell you about right now, OK?
So what I want to do is I want to start by taking this
program apart on the board and talking to you about the
modules, the subroutines that it contains.
So here it is.
The first thing we need to think about,
here are some blocks.
What has to happen if I'm going to put the bottom block
on the larger block?
Well, first of all, I have to find space for it.
Then I have to grasp the lower block.
And I have to move it and I have to ungrasp it.
So those are four things I need to do in order to achieve
what I want to do.
So therefore, I know that the put-on method has four pieces.
It has to find space on the target block.
It has to grasp the block that it's been commanded to move.
Then it has to move, and then it has to ungrasp.
But taking hints from some of the questions that it did
answer before I got haunted by the music, taking our cue from
that, we know that in order to grasp something, in this
particular world, you can't have anything on top of it.
So grasp, therefore, may call clear top in order to get
stuff off from the target object.
And that may happen in an iterative loop because there
may be several things on top.
And how do you get rid of stuff?
Well, by calling get rid of.
And that may go around a loop several times.
And then, the way you get rid of stuff is by calling put-on.
So that gives us recursion, and it's from the recursion
that we get a lot of the apparent complexity of the
program's behavior when it solves a problem.
Now, in order to find space, you also have to
call get rid of.
So that's where I meant to put this other iterative
loop, not down here.
Cleat top has got the iterative loop inside of it.
So that's the structure of the program.
It's extremely simple.
And you might say to me, well, how can you get such
apparently complex-looking behavior out of
such a simple program?
A legitimate question.
But before we tackle that one head on, I'd like to do a
simulation of this program with a very
simple blocks problem.
And it's the one I almost showed you, but
it goes like this.
Here's B1.
We'll call this BX because I forgot its name.
Here's BY.
And here's B2.
And the task is to put B1 on B2.
And according to our system diagram, that results in four
calls to subroutines.
We have to find space.
We have to grasp B1.
We have to move, and then we ungrasp.
Now, the way we grasp something is the first thing
we have to do is clear off its top.
So grasp calls clear top.
And clear top in turn calls get rid of.
And let me see.
Let me keep track of these.
This is clearing the top of B1, and this is
getting rid of BX.
And the way we get rid of BX is by putting BX on the table.
And then that in turn causes calls to another find space,
another grasp, another move, and another ungrasp.
So that's a little trace of the program as it works on
this simple problem.
So how does it go about answering the questions that I
demonstrated to you a moment ago?
Let's do that by using this trace.
So how, for example, does it answer the question, why did
you get rid of BX?
[INAUDIBLE], what do you think?
How can it answer that question?
SPEAKER 4: [INAUDIBLE]
PROFESSOR PATRICK WINSTON: So it goes up one level and
reports what it sees.
So it says, and said in the demonstration, I got rid of BX
because I was trying to clear the top of B1.
So if I were to say why did you clear the top of B1, it
would say because I was trying to grasp it.
If I were to say, why did you grasp B1, it would say because
I was putting B1 on B2.
If I say, why did you put B1 on B2, it would say,
slavishly, because you told me to.
OK, so that's how it deals with why questions.
How about how questions?
Timothy, what do you think about that one?
How would it go about answering a question about how
you did something?
Do you have a thought?
TIMOTHY: Um, yeah, it would think about what I was trying
to accomplish.
PROFESSOR PATRICK WINSTON: Yeah, but
how would it do that?
How would the program do that?
We know that answering a why question makes
it go up one level.
How does it answer a how question?
Sebastian?
SEBASTIAN: It goes down one level.
PROFESSOR PATRICK WINSTON: You go down one level.
So you start off all the way up here with a put-on.
You will say, oh, well I did these four things.
You say, why did you grasp B1?
It will say because I was trying to clear its top.
Why did you clear its top?
Because I was trying to get rid of it.
Why were you trying to get rid of it?
Because I was trying to put it on the table.
So that's how it answers how questions, by going down in
this tree and this trace of the program of action so as to
see how things are put together.
What are these things that are being put together?
What's the word I've been avoiding so as to bring this
to a crescendo?
What are these objectives, these things it wants to do?
They're goals.
So this thing is leaving a trace, which is a goal tree.
Does that sound familiar?
Three days ago, we talked about goal trees in connection
with integration.
So this thing is building a goal tree, also known as an
and-or tree.
So this must be an and tree.
And if this is an and tree, are there any and nodes?
Sure, there's one right there.
So do you think then that you can answer questions about
your own behavior as long as you build an and-or tree?
Sure.
Does this mean that the integration program could
answer questions about its own behavior?
Sure.
Because they both build goal trees, and wherever you got a
goal tree, you can answer certain kinds of questions
about your own behavior.
So let me see if in fact it really does build itself a
goal tree as it solves problems.
So this time, we'll put B6 on B3 this time.
But watch it develop its goal tree.
So in contrast to the simple example I was working on the
board, this gets to be a pretty complicated goal tree.
But I could still answers questions about behavior.
For example, I could say, why did you put B6 on B3?
Because you told me to.
All right, so the complexity of the behavior is largely a
consequence not of the complexity of the program in
this particular case, but the building of this giant goal
tree as a consequence of the complexity of the problem.
This brings us to one of our previous matters--
early on to one of the gold star ideas of today.
And this gold star idea goes back to a lecture given in the
late '60s by Herb Simon, who was the first Nobel Laureate
in the pseudo Nobel Prize for economics.
Is that right, Bob?
Was he the first?
All right, he was the first winner of the Nobel Prize,
pseudo Nobel Prize in economics.
And in this lecture, which was titled "The Sciences of the
Artificial," he said imagine that you're looking on a beach
at the path of a ant.
And he said, well, you know, the path of the ant looks
extremely complicated.
And you're tempted to think the ant is some kind of genius
or monster brain ant.
But in fact, when you take a closer look, what you discover
is that there are a bunch of pebbles on the beach, and all
the ant is doing is avoiding those pebbles on his way home.
So the complexity of the behavior, said Simon, is a
consequence of the complexity of the environment, not the
complexity of the program.
So that's the metaphoric Simon's ant.
And what it says is that the complexity of the behavior is
the max of the complexity of the program and the complexity
of the environment.
So that's something we'll see many times during the rest of
the semester.
Complex behavior, simple program.
You think it's going to be complicated.
It turns out to be simple because the problem has the
complexity, not the program.
So that brings us to check box three in today's talk, and
there's a little bit of a scene here because now I want
to stop talking about goal-centered programming and
start talking about rule-based expert systems.
The rule-based expert systems were developed in a burst of
enthusiasm about the prospects for commercial applications of
artificial intelligence in the mid-1980s.
At that time, it was supposed lengthy articles are written,
but you could account for useful aspects of human
intelligence by writing all the knowledge in the form of
simple rules.
So if this is true, then that's true.
If you want to achieve this, then do that.
But all the knowledge had to be encapsulated in the form of
simple rules.
So what might you want to do with this?
All sorts of things.
Thousands of these systems were written,
as I indicated before.
But here's an example.
I'm going to work out an example having to do with
identification.
And this example is patterned off of a classic program,
strangely also written at Stanford, called MYCIN.
It was developed to diagnose bacterial
infections in the blood.
So you come in.
You got some horrible disease, and the doctor gets curious
about what antibiotic would be perfect for your disease.
He starts asking a lot of questions.
So I'm not going to deal with that because that world has
all kinds of unpronounceable terms like bacterioides and
anaerobic and stuff like that.
So it's completely analogous to talk about identifying
animals in a little zoo, sort of a small town type of zoo.
So I'm going to suggest that we write down on a piece of
paper all the things we can observe about an animal, and
then we'll try to figure out what the animal is.
So I don't know, what can we start with?
Has hair.
Then there are some characteristics of the
following form.
Has claws.
Sharp teeth.
And forward-pointing eyes.
And these are all characteristics of carnivores.
We happen to have forward-pointing eyes too, but
that's more because we used to swing around the trees a lot,
and we needed the stereo vision.
And we don't have the claws and the sharp teeth
that go with it.
But anyhow, those are typically characteristics of
carnivores, as is eating meat.
And this particular little animal we're looking at has
also got spots, and it's very fast.
What is it?
Well, everybody says it's a cheetah.
Let's see how our program would figure that out.
Well, program might say, let's see if it has hair, then rule
one says that that means it must be a mammal.
We can imagine another rule that says if you have sharp
claws, sharp teeth, and forward-pointing eyes, then
you're a carnivore.
And I'm using sort of hardware notation here.
That's an and gate, right?
So that means we have to have all of these characteristics
before we will conclude that the animal is a carnivore.
Now, this animal has been also observed to eat meat.
So that means we've got extra evidence that the animal is
carnivorous.
And now, because the animal is a mammal and a carnivore and
has spots, and it's very fast, then the animal is a cheetah.
And I hope all of our African students agree that
it must be a cheetah.
It's a small zoo--
I mean, a big zoo.
Who knows what it is?
It's probably got some unpronouncable name--
there's possibilities.
But for our small zoo, that will do.
So we have group now written down in the form
of these and gates.
Several rules, R1, R2-- and there needs to
be an and gate here--
that's R3 and an R4.
All of which indicate that this animal is a cheetah.
So we built ourself a little rule-based expert system that
can recognize exactly one animal, but you could imagine
filling out this system with other rules so that you could
recognize giraffes and penguins and all the other
sorts of things you find in a small zoo.
So when you have a system like this that works as I've
indicated, then what we're going to call that, we're
going to give that a special name, and we're going to call
that a forward-chaining rule-based--
because it uses rules--
expert system.
And we're going to put expert in parentheses because when
these things were developed, for marketing reasons, they
called them expert systems instead of novice systems.
But are they really experts in a human sense?
Not really, because they have these knee-jerk rules.
They're not equipped with anything you might want to
call common sense.
They don't have an ability to deal with previous cases, like
we do when we go to medical school.
So they really ought to be called rule-based novice
systems because they reason like novices on
the basis of rules.
But the tradition is to call them
rule-based expert systems.
And this one works forward from the facts we give it to
the conclusion off on the right.
That's why it's a forward-chaining system.
Can this system answer questions
about its own behavior?
[INAUDIBLE], what do you think?
SPEAKER 5: [INAUDIBLE].
PROFESSOR PATRICK WINSTON: Why?
SPEAKER 5: [INAUDIBLE].
PROFESSOR PATRICK WINSTON: Because it
looks like a goal tree.
Right.
This is, in fact, building a goal tree because each of
these rules that require several things to be true is
creating an and node.
And each of these situations here where you have multiple
reasons for believing that the thing is a carnivore, that's
creating an or node.
And we already know that you can answer questions about
your own behavior if you leave behind a trace of a goal tree.
So look at this.
If I say to it, why were you interested in
the animal's claws?
Because I was trying to see if it was a carnivore.
How did you know that the animal is a mammal?
Because it has hair.
Why did you think it was a cheetah?
Because it's a mammal, a carnivore, has
spots, and very fast.
So by working forward and backward in this goal tree,
this too can answer questions about its own behavior.
So now you know how, going forward, you can write
programs that answer questions about their behavior.
Either you write the subroutines so that each one
is wrapped around a goal, so you've got goal-centered
programming, or you build a so-called expert system using
rules, in which case it's easy to make it leave behind a
trace of a goal tree, which makes it possible to answer
questions about its own behavior, just as this
[INAUDIBLE]
program did.
But now, a little more vocabulary.
I'm going to save time by erasing all of these things
that I previously drew by way of connections.
And I'm going to approach this zoo in a little different way.
I'm going to not ask any questions about the animal.
Instead, I'm going to say, mommy, is this thing I'm
looking at a cheetah?
And how would mommy go about figuring it out.
In her head, she would say, well, I don't know.
If it's going to be a cheetah, then it must be the case that
it's a carnivore, and it must be the case that it has spots.
And it must be the case that it's very fast.
So so far, what we've established is that if it's
going to be a cheetah, it has to have the four
characteristics that mommy finds behind
this rule are four.
So instead of working forward from facts, what I'm going to
do is work backward from a hypothesis.
So here the hypothesis is this thing is a cheetah.
How do I go about showing whether that's true or not?
Well, I haven't done anything so far because all I know is a
cheetah if all these things are true, but are they true?
Well, to find out if it's a mammal, I can use rule one.
And if I know or can determine that the animal has hair, then
that part of it is taken care of.
And I can similarly work my way back through carnivore.
I say, well, it's a carnivore if it has claws, sharp teeth,
and forward-pointing eyes.
And then as much as the animal in question
does, then I'm through.
I know it's a carnivore.
I don't have to go through and show that it's a carnivore
another way.
So I never actually ask questions about
whether it eats meat.
Finally, the final two conditions are met by just an
inspection of the animal.
That's to say, it's in the database.
I don't have to use any rules to determine that the animal
has spots and is very fast.
So now, I've got everything in place to say that it's a
cheetah, because it's a carnivore, because it has
claws, sharp teeth, and forward-pointing eyes, and all
the rest of this stuff is similarly determined by going
backwards, backwards from the hypothesis toward the facts,
instead of from the facts forward to the conclusions.
So building a system that works like that, I have a
backward-chaining rule-based expert system.
But there's a very important characteristic of this system
in both backward and forward mode, and that is that this
thing is a deduction system.
That's because it's working with facts
to produce n
…
engineers drinking song.
Back in the day, I've drunk quite a lot to that song.
And as drinking songs go, it's not bad.
I caution you, however, before playing this song in the
presence of small children, audition it first.
Some of the verses are sufficiently gross as to make
a sailor go beyond blushing.
It's an interesting song because there are an infinite
number of verses.
Here's the mathematical proof.
Suppose there were a finite number of verses.
Then there would be a last verse.
And if there were a last verse, then some drunk alumni
would compose a new one.
Therefore, there is no last verse, the size is not finite,
and there are an infinite number of verses.
I play it for you today because I'm an engineer.
I like to build stuff.
I build stuff out of wood.
I build stuff out of metal.
I build stuff out of rocks.
And I especially like to write programs.
I don't know, sometimes people come to me and say, I'm
majoring in computer science, but I don't
like to write programs.
I've always been mystified by that.
I mean, if you want to show how tough you are, you can go
bungee jumping or drive a nail through your hand or something
like that instead.
But I've written quite a few programs for demonstrating
stuff in this subject.
They're all written in Java, principally because I can
therefore make them available to you and to the rest of the
world by way of Web Start.
A few weeks ago, I was mucking around with the system and
broke the version on the server, and within 15 minutes,
I got an email from somebody in the depths of Anatolia
complaining about it and asking me to bring it back up.
This particular program is patterned
after an early AI classic.
And it was the business end of a program written by Terry
Winograd, who became, and is, a professor of computer
science at Stanford University--
which is on the west coast for those of you--
on the strength of his work on the natural language front end
of this program.
But the natural language part is not what makes it of
interest for us today.
It's more the other kinds of stuff.
Let's pile these things up.
Now, I'm going to ask to do something, maybe put
B2 on top of B7.
Not bad.
How about B6 on B3?
This program's kind of clever.
Let me do one more.
Let's put B7 on B2.
OK, now let's see.
Maybe B5 on B2?
B4 on B3 first, maybe?
Oh, I must have clicked the wrong button.
Oh, there it goes.
OK.
Let's put B4 on B1.
Agh, my mouse keeps getting out of control.
Now, let's put B1 on B2.
This is an example I'm actually going to
work out on the board.
Oh, I see.
My touch pad accidentally got activated.
B1 on B2.
Now, let's ask a question.
OK.
Well.
SPEAKER 2: [SINGING]
PROFESSOR PATRICK WINSTON: Stop.
SPEAKER 3: [LAUGHTER]
PROFESSOR PATRICK WINSTON: Had enough of that.
Let's see.
Why did you put--
why did you want to get rid of B4?
OK, one--
SPEAKER 2: [SINGING]
PROFESSOR PATRICK WINSTON: Maybe they think, that's what
happens when you use software you write yourself.
Why did you want to clear the top of B2?
Did I do that?
Why did you clear the top of B1?
OK.
SPEAKER 2: [SINGING]
SPEAKER 3: [LAUGHTER]
PROFESSOR PATRICK WINSTON: Oh, it's haunting me.
Yeah.
So the drinking song is easily offended, I guess.
But I won't develop that scenario again.
What I want to show you is that this program looks like
it's kind of smart, and it somehow can answer questions
about its own behavior.
Have you ever written a program that's answered
questions about its own behavior?
Probably not.
Would you like to learn how to do that?
OK.
So by the end of the hour, you'll be able to write this
program and many more like it that know how to answer
questions about their own behavior.
There have been tens of thousands of such programs
written, but only by people who know the stuff I'm going
to tell you about right now, OK?
So what I want to do is I want to start by taking this
program apart on the board and talking to you about the
modules, the subroutines that it contains.
So here it is.
The first thing we need to think about,
here are some blocks.
What has to happen if I'm going to put the bottom block
on the larger block?
Well, first of all, I have to find space for it.
Then I have to grasp the lower block.
And I have to move it and I have to ungrasp it.
So those are four things I need to do in order to achieve
what I want to do.
So therefore, I know that the put-on method has four pieces.
It has to find space on the target block.
It has to grasp the block that it's been commanded to move.
Then it has to move, and then it has to ungrasp.
But taking hints from some of the questions that it did
answer before I got haunted by the music, taking our cue from
that, we know that in order to grasp something, in this
particular world, you can't have anything on top of it.
So grasp, therefore, may call clear top in order to get
stuff off from the target object.
And that may happen in an iterative loop because there
may be several things on top.
And how do you get rid of stuff?
Well, by calling get rid of.
And that may go around a loop several times.
And then, the way you get rid of stuff is by calling put-on.
So that gives us recursion, and it's from the recursion
that we get a lot of the apparent complexity of the
program's behavior when it solves a problem.
Now, in order to find space, you also have to
call get rid of.
So that's where I meant to put this other iterative
loop, not down here.
Cleat top has got the iterative loop inside of it.
So that's the structure of the program.
It's extremely simple.
And you might say to me, well, how can you get such
apparently complex-looking behavior out of
such a simple program?
A legitimate question.
But before we tackle that one head on, I'd like to do a
simulation of this program with a very
simple blocks problem.
And it's the one I almost showed you, but
it goes like this.
Here's B1.
We'll call this BX because I forgot its name.
Here's BY.
And here's B2.
And the task is to put B1 on B2.
And according to our system diagram, that results in four
calls to subroutines.
We have to find space.
We have to grasp B1.
We have to move, and then we ungrasp.
Now, the way we grasp something is the first thing
we have to do is clear off its top.
So grasp calls clear top.
And clear top in turn calls get rid of.
And let me see.
Let me keep track of these.
This is clearing the top of B1, and this is
getting rid of BX.
And the way we get rid of BX is by putting BX on the table.
And then that in turn causes calls to another find space,
another grasp, another move, and another ungrasp.
So that's a little trace of the program as it works on
this simple problem.
So how does it go about answering the questions that I
demonstrated to you a moment ago?
Let's do that by using this trace.
So how, for example, does it answer the question, why did
you get rid of BX?
[INAUDIBLE], what do you think?
How can it answer that question?
SPEAKER 4: [INAUDIBLE]
PROFESSOR PATRICK WINSTON: So it goes up one level and
reports what it sees.
So it says, and said in the demonstration, I got rid of BX
because I was trying to clear the top of B1.
So if I were to say why did you clear the top of B1, it
would say because I was trying to grasp it.
If I were to say, why did you grasp B1, it would say because
I was putting B1 on B2.
If I say, why did you put B1 on B2, it would say,
slavishly, because you told me to.
OK, so that's how it deals with why questions.
How about how questions?
Timothy, what do you think about that one?
How would it go about answering a question about how
you did something?
Do you have a thought?
TIMOTHY: Um, yeah, it would think about what I was trying
to accomplish.
PROFESSOR PATRICK WINSTON: Yeah, but
how would it do that?
How would the program do that?
We know that answering a why question makes
it go up one level.
How does it answer a how question?
Sebastian?
SEBASTIAN: It goes down one level.
PROFESSOR PATRICK WINSTON: You go down one level.
So you start off all the way up here with a put-on.
You will say, oh, well I did these four things.
You say, why did you grasp B1?
It will say because I was trying to clear its top.
Why did you clear its top?
Because I was trying to get rid of it.
Why were you trying to get rid of it?
Because I was trying to put it on the table.
So that's how it answers how questions, by going down in
this tree and this trace of the program of action so as to
see how things are put together.
What are these things that are being put together?
What's the word I've been avoiding so as to bring this
to a crescendo?
What are these objectives, these things it wants to do?
They're goals.
So this thing is leaving a trace, which is a goal tree.
Does that sound familiar?
Three days ago, we talked about goal trees in connection
with integration.
So this thing is building a goal tree, also known as an
and-or tree.
So this must be an and tree.
And if this is an and tree, are there any and nodes?
Sure, there's one right there.
So do you think then that you can answer questions about
your own behavior as long as you build an and-or tree?
Sure.
Does this mean that the integration program could
answer questions about its own behavior?
Sure.
Because they both build goal trees, and wherever you got a
goal tree, you can answer certain kinds of questions
about your own behavior.
So let me see if in fact it really does build itself a
goal tree as it solves problems.
So this time, we'll put B6 on B3 this time.
But watch it develop its goal tree.
So in contrast to the simple example I was working on the
board, this gets to be a pretty complicated goal tree.
But I could still answers questions about behavior.
For example, I could say, why did you put B6 on B3?
Because you told me to.
All right, so the complexity of the behavior is largely a
consequence not of the complexity of the program in
this particular case, but the building of this giant goal
tree as a consequence of the complexity of the problem.
This brings us to one of our previous matters--
early on to one of the gold star ideas of today.
And this gold star idea goes back to a lecture given in the
late '60s by Herb Simon, who was the first Nobel Laureate
in the pseudo Nobel Prize for economics.
Is that right, Bob?
Was he the first?
All right, he was the first winner of the Nobel Prize,
pseudo Nobel Prize in economics.
And in this lecture, which was titled "The Sciences of the
Artificial," he said imagine that you're looking on a beach
at the path of a ant.
And he said, well, you know, the path of the ant looks
extremely complicated.
And you're tempted to think the ant is some kind of genius
or monster brain ant.
But in fact, when you take a closer look, what you discover
is that there are a bunch of pebbles on the beach, and all
the ant is doing is avoiding those pebbles on his way home.
So the complexity of the behavior, said Simon, is a
consequence of the complexity of the environment, not the
complexity of the program.
So that's the metaphoric Simon's ant.
And what it says is that the complexity of the behavior is
the max of the complexity of the program and the complexity
of the environment.
So that's something we'll see many times during the rest of
the semester.
Complex behavior, simple program.
You think it's going to be complicated.
It turns out to be simple because the problem has the
complexity, not the program.
So that brings us to check box three in today's talk, and
there's a little bit of a scene here because now I want
to stop talking about goal-centered programming and
start talking about rule-based expert systems.
The rule-based expert systems were developed in a burst of
enthusiasm about the prospects for commercial applications of
artificial intelligence in the mid-1980s.
At that time, it was supposed lengthy articles are written,
but you could account for useful aspects of human
intelligence by writing all the knowledge in the form of
simple rules.
So if this is true, then that's true.
If you want to achieve this, then do that.
But all the knowledge had to be encapsulated in the form of
simple rules.
So what might you want to do with this?
All sorts of things.
Thousands of these systems were written,
as I indicated before.
But here's an example.
I'm going to work out an example having to do with
identification.
And this example is patterned off of a classic program,
strangely also written at Stanford, called MYCIN.
It was developed to diagnose bacterial
infections in the blood.
So you come in.
You got some horrible disease, and the doctor gets curious
about what antibiotic would be perfect for your disease.
He starts asking a lot of questions.
So I'm not going to deal with that because that world has
all kinds of unpronounceable terms like bacterioides and
anaerobic and stuff like that.
So it's completely analogous to talk about identifying
animals in a little zoo, sort of a small town type of zoo.
So I'm going to suggest that we write down on a piece of
paper all the things we can observe about an animal, and
then we'll try to figure out what the animal is.
So I don't know, what can we start with?
Has hair.
Then there are some characteristics of the
following form.
Has claws.
Sharp teeth.
And forward-pointing eyes.
And these are all characteristics of carnivores.
We happen to have forward-pointing eyes too, but
that's more because we used to swing around the trees a lot,
and we needed the stereo vision.
And we don't have the claws and the sharp teeth
that go with it.
But anyhow, those are typically characteristics of
carnivores, as is eating meat.
And this particular little animal we're looking at has
also got spots, and it's very fast.
What is it?
Well, everybody says it's a cheetah.
Let's see how our program would figure that out.
Well, program might say, let's see if it has hair, then rule
one says that that means it must be a mammal.
We can imagine another rule that says if you have sharp
claws, sharp teeth, and forward-pointing eyes, then
you're a carnivore.
And I'm using sort of hardware notation here.
That's an and gate, right?
So that means we have to have all of these characteristics
before we will conclude that the animal is a carnivore.
Now, this animal has been also observed to eat meat.
So that means we've got extra evidence that the animal is
carnivorous.
And now, because the animal is a mammal and a carnivore and
has spots, and it's very fast, then the animal is a cheetah.
And I hope all of our African students agree that
it must be a cheetah.
It's a small zoo--
I mean, a big zoo.
Who knows what it is?
It's probably got some unpronouncable name--
there's possibilities.
But for our small zoo, that will do.
So we have group now written down in the form
of these and gates.
Several rules, R1, R2-- and there needs to
be an and gate here--
that's R3 and an R4.
All of which indicate that this animal is a cheetah.
So we built ourself a little rule-based expert system that
can recognize exactly one animal, but you could imagine
filling out this system with other rules so that you could
recognize giraffes and penguins and all the other
sorts of things you find in a small zoo.
So when you have a system like this that works as I've
indicated, then what we're going to call that, we're
going to give that a special name, and we're going to call
that a forward-chaining rule-based--
because it uses rules--
expert system.
And we're going to put expert in parentheses because when
these things were developed, for marketing reasons, they
called them expert systems instead of novice systems.
But are they really experts in a human sense?
Not really, because they have these knee-jerk rules.
They're not equipped with anything you might want to
call common sense.
They don't have an ability to deal with previous cases, like
we do when we go to medical school.
So they really ought to be called rule-based novice
systems because they reason like novices on
the basis of rules.
But the tradition is to call them
rule-based expert systems.
And this one works forward from the facts we give it to
the conclusion off on the right.
That's why it's a forward-chaining system.
Can this system answer questions
about its own behavior?
[INAUDIBLE], what do you think?
SPEAKER 5: [INAUDIBLE].
PROFESSOR PATRICK WINSTON: Why?
SPEAKER 5: [INAUDIBLE].
PROFESSOR PATRICK WINSTON: Because it
looks like a goal tree.
Right.
This is, in fact, building a goal tree because each of
these rules that require several things to be true is
creating an and node.
And each of these situations here where you have multiple
reasons for believing that the thing is a carnivore, that's
creating an or node.
And we already know that you can answer questions about
your own behavior if you leave behind a trace of a goal tree.
So look at this.
If I say to it, why were you interested in
the animal's claws?
Because I was trying to see if it was a carnivore.
How did you know that the animal is a mammal?
Because it has hair.
Why did you think it was a cheetah?
Because it's a mammal, a carnivore, has
spots, and very fast.
So by working forward and backward in this goal tree,
this too can answer questions about its own behavior.
So now you know how, going forward, you can write
programs that answer questions about their behavior.
Either you write the subroutines so that each one
is wrapped around a goal, so you've got goal-centered
programming, or you build a so-called expert system using
rules, in which case it's easy to make it leave behind a
trace of a goal tree, which makes it possible to answer
questions about its own behavior, just as this
[INAUDIBLE]
program did.
But now, a little more vocabulary.
I'm going to save time by erasing all of these things
that I previously drew by way of connections.
And I'm going to approach this zoo in a little different way.
I'm going to not ask any questions about the animal.
Instead, I'm going to say, mommy, is this thing I'm
looking at a cheetah?
And how would mommy go about figuring it out.
In her head, she would say, well, I don't know.
If it's going to be a cheetah, then it must be the case that
it's a carnivore, and it must be the case that it has spots.
And it must be the case that it's very fast.
So so far, what we've established is that if it's
going to be a cheetah, it has to have the four
characteristics that mommy finds behind
this rule are four.
So instead of working forward from facts, what I'm going to
do is work backward from a hypothesis.
So here the hypothesis is this thing is a cheetah.
How do I go about showing whether that's true or not?
Well, I haven't done anything so far because all I know is a
cheetah if all these things are true, but are they true?
Well, to find out if it's a mammal, I can use rule one.
And if I know or can determine that the animal has hair, then
that part of it is taken care of.
And I can similarly work my way back through carnivore.
I say, well, it's a carnivore if it has claws, sharp teeth,
and forward-pointing eyes.
And then as much as the animal in question
does, then I'm through.
I know it's a carnivore.
I don't have to go through and show that it's a carnivore
another way.
So I never actually ask questions about
whether it eats meat.
Finally, the final two conditions are met by just an
inspection of the animal.
That's to say, it's in the database.
I don't have to use any rules to determine that the animal
has spots and is very fast.
So now, I've got everything in place to say that it's a
cheetah, because it's a carnivore, because it has
claws, sharp teeth, and forward-pointing eyes, and all
the rest of this stuff is similarly determined by going
backwards, backwards from the hypothesis toward the facts,
instead of from the facts forward to the conclusions.
So building a system that works like that, I have a
backward-chaining rule-based expert system.
But there's a very important characteristic of this system
in both backward and forward mode, and that is that this
thing is a deduction system.
That's because it's working with facts
to produce n
…