YouSub
Untitled

en English

Untitled English subtitles

0 downloads · 918 lines · added Nov 17, 2015

Report a problem
What's wrong?
Advertisement

English transcript

PATRICK WINSTON: Many of you, maybe most of you, will never
have to work another search problem by hand in your
natural life.
Others will want to take another run
at it on the final.
I've been much criticized for this way of doing
grading in the class.
But the way I look at it is that the relationship between
students and instructors ought to be less adversarial than it
used to be in the good old days when I was a student.
I especially remember an examination we took--
all of us took-- on Rayleigh scattering.
That was 803, I think.
And back in the old days, we had to take four physics
courses, not just two.
And we had to take four math courses, not just two.
Back in the days when--
well, I was going to say men were men.
But most of us were men in those days.
I think we only had 20 women in our class.
Anyway, we had a quiz on Rayleigh scattering.
And I thought, well, this is pretty hard.
And then I got my quiz back.
26.
I thought, well, I've been found out.
I'm going to flunk out.
My father will make me go to law school.
I'll never attract anyone to marry.
Horrible things will happen.
Then the instructor announced the class average was 18.
I was two standard deviations above that.
They gave us the same exam two weeks later,
and accounts vary.
Some people say that the class average went down.
Anyway, today we're going to study some stuff.
We're going to study some stuff that will make it
possible for you to understand how you can do that
computation in just a couple of seconds, even with the
delays introduced by the redrawing.
Now this particular program--
I'm not real sure and I don't have a proof, but I think it
will take more than the lifetime of the universe to
find a legitimate coloring of the continental United States.
But by the end of the next class, you'll see how to do
that lickety-split in just couple of seconds, even with
the re-display delays.
Now we could, of course, do this in two ways.
One way is I could start off by saying, let C be a
constraint satisfaction problem and just
give you the result.
And anybody can do that.
That's great.
And you needed to learn some stuff that way.
But there are some things that you needed to learn, I think,
a different way.
And that different way involves my telling you the
story of how it all came to be.
This is a new field, pretty much, and therefore I know
most of the people in it.
And I know all of the people who did the work that I'm
going to tell you about today.
I'm going to tell you a little bit about the struggle for
coming up with the ideas that led to one of the most
powerful methods you'll learn about in the subject.
It all has to do, originally, with an attempt to make a
computer capable of seeing.
And everybody said to themselves, well, let's start
with seeing simple things, like children's blocks.
And so Adolfo Guzman, a graduate student of Marvin
Minsky's, was charged with the summer project, which led to
his Ph.D. thesis, of writing a program that could look at a
line drawing and determine how many objects
are in the line drawing.
So for example, there behind my outline is a line drawing.
And you believe instantly that there are two objects there,
even though in some deep sense, it's ambiguous.
There are all sorts of ways that you could, through
trickery, arrange something with even seven objects that
look that way.
But most people would say there are two objects.
So Guzman set about the problem of figuring
out how to do that.
And then his work was followed by Dave Huffman.
And his work was followed up by Dave Waltz.
And his work was followed up by Jane [? Froyter ?], who's
not listed there quite yet.
And I want to tell you a little bit of story how that
all happened.
So Guzman took a lot of pictures.
He went to Boston Baby, the precursor to Toys R Us,
purchased a large block set on a government contract, and
went about the business of taking a lot of pictures of
them so he'd get a feel for the domain.
And eventually he decided that he could build a program that
could determine that there are two objects here by using the
lines as a quanta of evidence about which faces belong
together in an object.
So he said, after studying these for a long time, that
these drawings tend to have a lot of arrow-type junctions
and a lot of fork-type junctions.
And when you see an arrow, it's a little bit of evidence
that the objects on either side of the shaft are the
same-- the face on either side of the shaft belong to the
same object.
And over here, the fork-type junction suggests that
pairwise, three pairs of faces seem to
belong to the same object.
So with that idea, he could come back to a drawing like
this and start decorating it with these so-called links,
these quanta of evidence that faces
belong to the same object.
And if I've done it right, you get something
that looks like so.
It's a little hard to see what's going on
on the drawing itself.
So let me number these.
Now I have an easier-to-deal-with picture.
There are two links between 1 and 2 and 1 and 3.
One link between 2 and 3.
One between 2 and 4.
Two here.
And one each from all of these.
So Guzman produces this evidence for how the problem
ought to be solved and then he begins to think about various
ways of using the evidence.
So he could, and did, decide that one link is enough to
presume that the faces belong to the same object.
And you can see that that's a little bit too liberal.
Because that says that the whole
thing is just one object.
So Guzman rejected the one-link theory and went to
the two-link theory.
And the two-link theory says, oh, well, let's see.
If we insist that two links should be there before we are
willing to decide that it's the same object, then these
three faces are pulled together into one object.
These three are pulled together into one object.
But alas, 7 doesn't share two links with anything, so it's
left dangling out there.
So plainly, the two-link theory is too conservative.
So that as you would soon discover in any [INAUDIBLE]
project, would lead you to a third theory, which is two
lengths repeated.
So now that we've formed these super regions, we can come
back and say we'll merge super regions if they're connected
together by two or more links.
So nothing new happens up here.
But this super region is joined at 7
by two or more links.
So it pulls everything together like so.
So that worked fine.
Well, it didn't work fine.
There were lots of examples of situations
where it didn't work--
in situations that were considered nonsensical by us
humans because it seemed silly, the kind of conclusions
that it reached.
So when Guzman presented this work in his Ph.D. thesis
defense, it's said--
and who knows if it's true-- but it's said that Marvin
Minsky thought it was great work and we
should make him a professor.
It happens that Dave Huffman was also on the committee and
said that it was ad hoc and the thesis should be rejected.
So we had two polar opposites of impressions there.
Dave Huffman, by the way--
you've heard that name before, I imagine.
It's the guy who invented Huffman coating as a term
paper in a information theory course taught by Bob Fano.
He got an A, they say.
So Huffman didn't like it.
He thought it was a little bit too ad hoc.
It was too heuristic.
It didn't take advantage of anything we
might know about physics.
And so people began to say, well, why does it work?
And when does it not work?
And that's just about the best question you can answer in a
situation like this.
And by playing with some more of Guzman's pictures and
reflecting on them, it turned out that it worked because the
world is full of three-face junctions.
Or let me say three-face vertexes because they're out
there in the world.
We'll reserve the word junction for something else.
And three-face vertexes generally project into either
an arrow or a fork.
So Guzman's whole program worked on the weak backward
conclusion that if you see one of those, it probably came
from one of these.
So this is in the drawing.
That's in the world.
So by a process that's neither deduction or induction, but
rather abduction, you see one of those guys.
And you say, well, they often come from three-face vertexes
in the world, so if you see one, it probably came from a
three-face vertex in the world.
That's abduction.
So once Huffman saw all that, being a mathematician, he
began to think about how one might develop a different and
better theory.
But we have to recognize that all this work started off with
the efforts of Guzman, who was an experimentalist.
And Huffman was a mathematician.
So naturally, they approached the problem differently.
So Huffman says, I'm not going to concern myself too much
with the actual problem that Guzman was trying to solve.
Rather, I'm going to work in a very simple world, which I can
deal with mathematically.
So he decided that he was going to work in a world which
had several characteristics.
Characteristic number one was that the world would be
presented in general position.
That is to say, no screw cases.
So if you see a cube, it's going to look like this.
And it's not going to look like this.
So that's out.
And this is in.
And the idea here is that that's not general position,
because if you perturb your point of view a little bit,
you'll change those T junctions
into forks and arrows.
So we know it had to deal with those kinds of
weird kinds of cases.
So that's presumption number one.
Presumption number two is that we're going to be dealing with
a world that's trihedral.
That means all vertexes out there are going to be formed
from three planes.
So you're going to have the intersection of three planes.
So how many kinds of junctions can you see if the world is
composed that way is the question that Huffman sent
himself upon.
The next assumption was that there are going to be four
kinds of lines.
See, Guzman only recognized two kinds of lines-- lines
that have a length and lines that don't have a link.
And they don't have very much to do with the physical world.
So Huffman says, I want to get the constraint out of the
physical world.
So I'm going to deal with four kinds of lines--
concave, convex, and boundary.
So each of those kinds of lines is going to
have its own notation.
We'll call the convex lines plus, the concave lines minus,
and a boundary lines are going to get an arrow on them,
depending on which side of the object--
which side you would see the object if you walk along the
direction of this little arrow.
STUDENT: Question.
Which is concave and which is convex?
You said something and you wrote the opposite.
PATRICK WINSTON: Yeah, sorry.
Thank you.
So concave, convex, and boundary.
Thank you.
So this down here, that's a concave line.
And that would get a minus label.
Oh, I don't know.
These lines you're seeing here, if there were stuff
behind them instead of me, then all those
would be convex lines.
Many times you see a boundary line.
For example, now you don't see both sides of that line down
here at the bottom.
So that's a boundary line.
And the arrow would point in that direction, so as to keep
the stuff of the object on the right as you walk along a kind
of mathematical convention.
So three kinds of lines, four kinds of labels.
And there's some things left out.
That's because Huffman wanted to keep his problem simple,
something he could manage by hand.
What's left out?
Cracks are left out.
Shadows are left out.
There's a presumption that there's nothing of interest
here with respect to that.
So let's have a little vocabulary before I go on.
And I'll try to stick to it.
But there's the stuff out there, and that consists of
vertexes and edges.
And over here, on the blackboard, we'll have
junctions and lines.
And I'll try to stick to that vocabulary.
All right?
Yes, Christopher?
STUDENT: Didn't you say there were four types of lines?
PATRICK WINSTON: Yeah, there are four kinds of--
the question is, didn't I say there were
four kinds of lines?
There are three kinds of lines, but since we can label
a boundary line in either direction,
we have four labels.
OK?
It depends on which side of the object the stuff is on.
And that will be clear, I think, as
soon as I do an example.
So one, two, three assumptions.
A little bit of vocabulary.
So we have the possibility of making a complete catalog.
This is so simple.
We have the possibility of making a complete catalog of
all the ways that lines can come together to form a
junction with respect to these four labels.
Now at first you might say, oh my god, that will take a
couple of years.
But maybe it won't take a couple of years.
And in the end, to perhaps your surprise, you discover
that there are only 18 ways to arrange the labels around a
junction in this world.
Everything else is excluded.
If you have something that's not in the set we're going to
produce now, it can't be built with trihedral vertexes.
So I've listed up there six L's, five forks, four T's, and
three arrows.
Let's see if I can figure out why there are those 18 and
nothing else.
Well, if we have three vertexes coming together, that
means there are eight octants, right?
And the stuff of the object may fill 1, 2, 3, 4, 5, 6, 7
or all eight octants.
Now of course, if you fill all eight
octants, there's no junction.
So we don't consider that case.
If we don't fill any the octants, there's no junction.
There's no vertex.
So we don't consider that case.
But if just one of the eight octants is filled with stuff,
then we can look at it from any of the
seven remaining octants.
So right now, you're looking at it from one of the seven
remaining octants.
And if I'm not mistaken, you're going to see a
fork-style junction there, right?
And you're going to see a fork-style junction in which
all of the edges are convex.
An unfortunate selection of names, because the linguists
tell me that we index all of our words
by the first forename.
And those have the same first forename, so
they're easily confused.
So here's a fork-style junction.
And we know that one way that's legitimate for the
lines to come in is with four pluses.
Now that's not the only way you can see that.
And here's another way.
There's an L-style junction, right?
And both of those are boundary lines.
And we want to draw the boundary line indicators on
there so that if we walk along the arrows, the stuff of the
object would be on the right.
So I suppose, to make it easier to me do my drawing, I
should look at it this way.
And then I would say, well, that has to be a legitimate
way of labeling a junction.
Are there any more?
Well, there's seven altogether, but many of them
are the same.
There is one more that's a little different, though.
I can hold this guy up like so.
And if I'm holding at the right angle for you, you see
an arrow-style junction, right?
Two boundaries, and the barb is convex.
So in this particular case, I've got that.
I've got that.
And I've got a plus there.
And that's there happen to be for the one octant filled with
stuff case.
I happen to be able to reverse this, though.
And here's the seven octants filled case.
So that tells us that it's possible to have a vertex out
there in a space that when reduced to a junction on the
board deserves three minus labels, because all of these
that you're seeing now are concave.
So another fork-style junction looks like so.
And since there's only one octant to look at from, that
completes our analysis of the seven octants filled case.
Now we have a couple of other possibilities here.
We might have five octants filled with stuff.
So that means there are three octants that we can look from.
So let's suppose that these little chalk
pieces are little people.
And they're looking at this junction down there, where
this white object is fused with the table.
I'm fusing it with the table because I want to consider it
to be one object.
We can view it from the three objects indicated by those
three little chalk pieces.
And ask ourselves, well, in the event that we look at it
from those three places, what do we see?
And if we look at it from the perspective of the piece of
purple chalk--
I'll have to walk around and be sure--
looks like an arrow junction with two
concaves and a convex.
Did I get that right?
So I'm looking at it from this perspective.
It's an arrow.
This is convex and these two are concave because I fused
the paper box with the table.
Looking at it from the perspective of this blue guy--
let me rotate it so you can have a better understanding of
the blue guy--
it looks like a concave line and a boundary.
So it's an L. And this one is a boundary.
And that's concave.
And by a kind of symmetry, we're also going to get that
one from the other side, the third of the three octants.
Well, we're off and running.
But we still have an awful lot to go.
And we could manage to deal with it by thinking about this
object once again.
But instead of this situation out here, to turn it around
and look at this vertex.
Think about the junctions that it can produce.
I think I'll do that for you.
Because you really have to play with this and move it
around a little bit to see how things are going to look.
So let me think about how that's going to work out.
I know that one of the possibilities is going
to look like so.
I might as well not hide that from you.
It's going to be what happens when there's a little man
looking up at the junction.
And this one's going to be minus.
And now we've got two more that are just like that.
Look like so.
And you say, oops.
You say, aren't those just a rotational
variance of each other?
And the answer is sure.
I write them all down, because if you get a fork-style
junction in space, there are three different ways it could
be labeled.
Depending on which of the lines you put
the minus label on.
So that takes care of that.
And then there's one more of these fork-style junctions.
And that's plus, plus, minus that derives from this case.
And there appear to be three more of
these L-style junctions.
And they look like, let's see, plus, then plus.
I'm having to think this through as I go.
And then--
and that's it.
Well, what about the T's?
Well, in this world, the only way you can get a T is if some
object is obscuring another object.
And if an object is obscuring a line, it can
be any line at all.
So that's why the four remaining ones are easy beyond
description to label.
And of course, the cross pieces of the T are all
boundary lines, with the obscuring object on the right.
Now let's see.
We've taken care now of the one, three, five, and seven
octants filled cases.
What about two, four, and six?
Well, it turns out you can have vertexes that are made
that way too.
But they will have more than three faces.
They'll have six faces.
They'll be like what happens when an object comes together
at a point, like so.
Like that.
You can play with it a little bit and see that if you have
two, four, or six objects filled with stuff, there are
more than three faces.
So we're going to ignore those.
So our constraint is going to be a little more severe than
would be suggested by the terminology Huffman uses.
They're going to be trihedral all right, but they're also
going to be three faces.
So we went to a lot of work there.
But what have we discovered?
We've discovered that in this world, this is a complete,
100% percent, nothing excluded, nothing else can be
there, catalog of all possible ways the junctions can have
line labels arranged around them.
There's nothing else in this world.
So that's a very powerful constraint.
So now let's see what we can do with it.
This example is usually more fun when the Red Sox are doing
better, but they're not.
Yet we'll use it any way.
We're going to start with an object that
looks like home plate.
And I'll ask you the question.
Can you build one of those?
I don't know.
Let's give it a shot.
We're going to assume that this object is hanging,
floating in space.
So therefore, all of these lines around the boundary are
boundary lines, like so.
Now that gets us off to a good-- it's just hanging in
space, Christopher, all right?
You look
…

Need subtitles from another video?