Reasoning: Goal Trees and Problem Solving - Artificial Intelligence Video Lecture - Computer Science Engineering (CSE)

that's what we're going to talk about
today
so just quite a way of a little warm-up
exercise I'd like you to look at that
integration problem over there go on
this different
this one has disappeared
so the question is can you do it in your
head
probably not the question is if a
program can do that is a program in any
sense of the word intelligent that's a
background task I'd like you to work on
as I talk today so today we're going to
be modeling a little bit of human
problem solving the kind that is
required when you do symbolic
integration now you all learned how to
do that
you may not be able to do that
particular problem anymore we all
learned how to integrate in high school
or 801 or something like 1801 or
something like that
the question is how did you do it and is
the problem-solving technique that we
are trying to model by building a
program that does symbolic integration
is that a common kind of is that a
common kind of description of what
people do when they solve problems so
the answer the question is yes the kind
of problem solving you'll see today is
like generate and test which you saw
last time it's a very common kind of
problem solving that we all engage in we
all engage in it without thinking about
it without having a name for it but once
we get a name for it we'll get power
over it and then we'll be able to deploy
it it'll become a skill well not just
witness it will not just understand it
will use it instinctively as a skill so
there you are you've got that problem
there's your problem
and what do you do to solve it I don't
know look it up in a table you'll never
find it in a table because of that minus
sign in that five so you're going to
have to do something better than that
so what you're going to do is what you
always do you see a problem like that
you try to make you try to apply a
transform and make it into a different
problem that's easier to solve and
eventually what you hope is that you'll
simplify it sufficiently that the pieces
that you've simplified to will be found
in some small table of integrals so how
long is this table it's not the case
that we're gonna look at a table with
388 elements because this is not the
this is not a big table of integrals
this is what a freshman might have in a
freshman's head after taking a course in
integral calculus one of the interesting
questions is how many elements have to
be in that table to get an A in the
course we're interested in how much
knowledge is involved it's one of the
it's one of the elements of catechism
that I've listed over there that will be
part of the Goldstar ideas suite of the
day so I'd like to take that we'd like
to take that problem and find a way to
make it into another problem that's more
likely or closer to being found in the
table so what we're going to do is very
simple graphically we're going to take
the problem we're given and convert it
into another problem that's simpler
we're going to give that process a name
and we're going to call it problem
reduction and so in the world of
integral calculus there are all sorts of
simple methods simple transformations we
can try that we'll take a hard problem
and make it into an easier problem and
some of these transformations are
extremely simple and always safe some of
them are just well let's try and see
what happens but some of them are safe
and I'd like to make a short list of
safe transformations right now now I'm
going to be going into some detail and
that detail will be grungy and the
question is why do I do it and it's
educational philosophy is why I do it so
here's the educational philosophy at one
level you want to have a skill
but if you're going to have a skill you
have to understand it so if you're going
to have a skill you don't have to
understand it one level down if you can
understand it you have to witnessed it
on a level lower than that
so I'm not going to talk about the idea
of problem reduction because if I were
just going to do that then we could all
go home now so I'm going to show you a
particular example of it so you
understand it better and I'm going to
show you the detail not even lower level
than that so you'll witness this stuff
that makes it possible to understand the
stuff that makes it possible to build a
skill so that's why I'm going through
the grungy detail so I don't know let's
see maybe we can get some hints from
that example but what if somebody could
volunteer a simple transformation that
always is a good thing to do you know
Sebastian take the constants out so
we'll make that number two and we'll say
that the integral of C f of X DX is
equal to C times the integral of f of X
DX
other suggestions yes what trig
substitution now this is no no that's
for day two we know the trig
substitution here and the stuff that's
safe always works never any doubt there
are simpler things these are the safe
transformations well you're giving me as
a heuristic transformation often is
helpful doesn't necessarily always work
we're going to divide our
transformations into those two
categories so I need another safe one
arie the architects are sitting over
there divided not only by nationality
but by course what you know some of the
area center with some what's missing
what's number one you're probably
thinking it's already there because
you've given me the transformation that
involves a constant and you think you
can think of minus one is a constant so
whether you need to separate
transformation out of course depends on
how you represent the knowledge and all
of this knowledge all of this whole
thing is was written in was written in
an early form of Lisp as consequence the
way in which - was represented as
different from the way - one is
representative so we need one more
transformation a rather Jim Schlegel
needed one more transformation when he
wrote his famous integration program and
that was that if you have the integral
of minus f of X that's equal to minus
the integral of F X so that almost
completes our safe transformation set
there's one more than I'm going to
supply you because I don't think you'd
guess it why should you it's number four
there are more than this this is a
sample and these are the ones we're
going to need in order to solve that
problem by way of illustration so the
fourth one is that if you have the
integral of P of x over Q of X then you
divide if you can wait reach way back in
highschool and figure out how to divide
polynomials but if the degree of the
numerator is greater than the degree of
the denominator then it's a knee-jerk
always win you must do it
light it out so this then forms the core
of an integration program they'll
integrate almost nothing but actually
almost nothing is integrable anyway so
it's a good head start so let's see how
we would put this into some kind of
procedure some kind of framework for
deploying the knowledge that we're
beginning to develop what we're going to
do is apply all safe transforms that's
our step first step then we're going to
look in the table and then we're going
to do a test to see if we're done and if
we are we report success but we're not
likely to get done with just that stuff
but you know what
there was one transformation up here
which breaks my little diagram which one
is it
it's the third one right because this
picture does not reflect what happens
when you apply number three because it
breaks the problem up not into just one
problem but into a whole bunch so we
have to extend a graphical our graphical
device for talking about this by a
little bit and show what is called an
and a node so we've got a program core
we've got a table of integrals we've got
a few transformations we've got an
architecture a way of putting that stuff
together and now we can try it out on
our sample problem so let's have a go at
that
let's see this one immediately
transforms into five X to the fourth
over one minus x squared to the five
halves DX and that in turn immediately
transforms into the integral of X to the
fourth over one minus x squared to the
five halves DX this program by the way
is a dawn age program this was written
by a nearly blind subsequently
completely blind to graduate student by
the name of James Slagle in 1960 a long
time ago the reason I give it to you
today is because it is because of by
describing it I'm giving you a one
lecture course in artificial
intelligence he anticipated so much of
the subsequent 20 years that talking
about his program which is possible in
one day is a miniature introduction the
whole field so Slagle as he was doing
this on an antique computer almost no
memory almost no speed only slightly
faster than mice running around on the
treadmill he was able to write a program
that did extremely well when the Bedouin
benchmarked against freshmen the way we
benchmark against freshmen of course is
you you give it an examination drawn
from the previous MIT finals for four or
five years the hardest problems and this
was the hardest problem that it solved
so at this point with what we've got so
far we would be stuck
we have no transformation that can take
us further so we need something else and
what we need by way of something else
there's some transformations that we
will describe as
perhaps we'll call them heuristic
transformations a funny word meaning a
method that often works isn't guaranteed
to work it's not an algorithm in the
usual sense that we talk about
algorithms but rather it's a it's a it's
an it's a it's an attempt so these
things I'm going to talk about now are
sometimes useful not always useful
sometimes take it into a blind alley
don't always work but you can't get an A
in calculus without knowing some of them
so you said some kind of trig
substitution so here is some kind of
trick substitution call this heuristic
transformation a you have a function
sine X cosine X tangent of X cotangent
of X secant of X and cosecant of X and
we all know from high school
trigonometry that we can rewrite that as
a function sine x + cosine X or we can
rewrite that as a function of tangent of
X and cosecant of X
or we can rewrite that as function of
cotangent of X and the secant of X so
that's a transformation from
trigonometric form into another
trigonometric form it's not always a
good idea
sometimes it helps well that's just part
one of our suite of heuristic
transformations stop
there are others that we need to have in
our in our repertoire in order to solve
the problem one of them is a family of
transformations which I'll show you only
one it goes like this if you have the
integral of a function of the tangent
and X then you can rewrite that as the
integral of a function of Y over 1 plus
y squared dy
so that's a transformation from a
trigonometric form into a polynomial
form so it gets rid of all that
trigonometric garbage we don't want to
deal with there's a whole family and
things like that just as there was a
family of transformations like so but
this is enough to give you flavor now
there's a C that we need as well and
that's going to be your proper knee-jerk
reaction you see something of the form 1
minus x squared what do you do when you
see that what's that Ronna
well wait a second you could do that
there's nothing you can do
Kristen you got something you can
suggest cause of what where is our
Hungarian I turn our young turn yeah
well let's see cosines of where cosine
stories with one so what's that suggest
here so suggested we make the
transformation that involves X people
sign apply so Scylla doesn't actually
have to remember that anymore because
going forward she will never have to
integrate anything personally in her
life she can just simulate the program
so these go from polynomial form back in
a trigonometric form so you have three
of these heuristic transformations we've
got four safe transformations let's see
if we can make any progress on our
integration problem
okay so keeping track of what we've been
using this is safe transformation number
one this is safe transformation number
two what do we do next we decided there
were no more safe transformations that
apply and now we can look at our eristic
transformations and behold we see
watching multiplying see transformation
see suggest that we do X equals the sine
Y and now we get the integral of sine to
the fourth Y over cosine to the fourth Y
dy right all good I see some confused
worried concerned looks maybe I've made
a mistake
perhaps I should use notes well no wait
a minute
for those of you have a concerned look
remember that if x equals a sine Y and
DX is equal to cosine Y dy that's why
it's cosine to the fourth like cosine to
the fifth as you were perhaps thinking
it might be so now we made some progress
we look at this we say are there any
safe transformations that apply the
answer is no now we look for heuristic
transformation that might apply now so
what do you see which one
what's that
she said something unintelligible she
probably said is that this looks like a
pattern that might match with the
heuristic transformation a right because
we have a function in which the variable
is very beautifully in science or
cosines and tangents or pro tangents or
sequence or Co sequence and we know we
can rewrite that in one of three ways
it's already written as a function of
sine and cosine but we can also rewrite
that in terms of tangent and cosecant or
cotangent and secant so when we do that
we can go this way and we can get the
integral 1 over the cotangent of X DX
that's G 2 up there
no that's G 3 up there or we can do it
now this path and get the integral of
tangent of X DX and of course those are
both to the fourth we know what I've
broken my little graphical diagram again
where did it go
it's disappeared
you know there it is how have I broken
it because the transformation a I've
introduced the possibility that a
particular problem can be transformed in
more than one kind of problem any of
which will be the solution to my problem
so so far I've got an end node but now
I'm going to introduce an or node
because now we have an example of
something if we solve one of two
different ways we don't care which one
of this now you'll notice if there's
already some confusion here because how
can you tell there's between a node and
or node so the universal convention you
draw an arc over the end notes and that
makes it look like an A so it's easy to
remember so those are an nodes and now
we have the method of problem reduction
and this is sometimes called a problem
reduction tree sometimes it's called an
and or tree
and sometimes it's called the goal tree
because this tree of problems is a tree
that shows how our goals are related to
one another these are items for your
vocabulary that are all synonymous
problem induction tree and/or tree goal
tree all same thing now you have a name
for it you've got some power over it so
we'll get a situation like this unlike
the previous situation which we
suggested might come up and
transformation a
let's see we got one to see and this one
is a it's an or node which one of these
problems we work on well Slagel who
considered himself to be modeling of
freshman modeling the intelligence of a
freshman modeling something that after
all you have to be pretty smart to do
right I mean most people don't know how
to do integration everybody MIT knows
how to do integration you would think
that somebody therefore that knows how
to do integration is pretty smart
what would a smart person do when faced
with this choice well smart person would
say which of these two problems is
easier so how do you think you might
determine which of two or many algebraic
expressions is the easiest to to
integrate what do you think
feels yes
feels how would I miss hop how would you
decide how would you feel it which one
I feel the tenth yeah we could make a
little bit more precise inside of
simplicity ah the other Turkish Egyptian
until you said this idea of simplicity
so that I realized that what I was about
to suggest was it gonna clarify
simplicity what I was gonna say
whichever one we've had more encounters
with more experience
yeah there was something over the
hyperbolic tangent might said well stay
away from around linen which one of
those the
explosion switch well like she might go
look at and see which tire thing will be
next
Erica oh you have a table see if them
something something is in it this is
post this is tangent of course oh that's
not commuting area I choose the month
reciprocal why just because when people
see one of my comments yeah we're on
we're on the right track you a symbols
in it now we're really getting somewhere
because you can measure that little
program library where I'll take means
every other great conversions are be
written as
all these ones will fly together divided
well I heard it perhaps others didn't
but what Brett said is he suggested is
that you should measure the depth of
function composition so the number of
symbols may not matter because if you
had X plus X plus X plus X - 100 100
that would not be hard to integrate but
if you got something that's really deep
deeply nested and a lot of functional
composition that could be a problem and
that's in fact what's label decided to
use after trying several trying several
alternatives so if we measure the
function the depth of functional
composition this is the winner and we
put the other one on the shelf or at
least for the moment and now we have
tangent to the fourth X DX do any of the
safe transformation supply which of the
you know something has to apply
otherwise it would be up here as an
example so what are the what of the
heuristic transformation supply Elliott
yeah be military background may be flies
airplane okay
so B says it is a factor function of the
tangent and when we do that we're going
to make a substitution that y is equal
to tangent so that means that this
becomes the integral of Y to the fourth
over 1 plus y squared and that's my
transformation B and the transformation
is y equals tangent of X
tangent I guess I've lost track of the
fact that I've already transformed a why
but relabeling doesn't matter all right
so that's progress
maybe but let's see this in any of the
eristic transformations what do I do now
I didn't have to look in the use of
transformations because one of the safe
transformations applies right because
this thing is a rational function and
the degree of the numerator is greater
than you created nominator so I have to
divide and when I divide and that by the
way is number 4 I get what so many good
at high school algebra help me out with
that
I see responds to busing it really love
this question that my squared minus 1
plus 1 over 1 plus y squared I think now
what now we're really getting close to
getting through this because that is a
sum
and virtually the fact that it's a sum
that divides into three pieces and the
top piece is the integral of y-squared
the middle piece is the integral of
minus one and the bottom piece is the
integral of 1 over 1 plus y squared dy
in all cases gosh if I look this up I
found it right that's something that's
number B or letter B so I'm done with
that this one I can transform again by
virtue of 1 and now I get the integral
of dy that's in there that's B as well
and this one I don't know and I better
keep track what I'm doing here this is
an and node so I've got to do all of
those I can't give up on that last thing
and that end transformation is
transformation number 3 so this is in
the table this is in the table you still
have this to do but that's C youstick
transformation C we have 1 plus y
squared then with the transformation C
with Y that's Y squared y equals tangent
of Z then we get to the integral of DZ
and that's on the table and we're done
so now we solve the problem it's the
hardest problem appeared in that half
decade on MIT 1801 finals this is
exactly the problem was given except
that it started here I put the other two
pieces on just to illustrate a couple
other transformations but that's
a problem that it solved and now that
we've seen in the example we can finish
up what what we talked about a little
bit ago having to do with the
architecture of this thing so far all
we've done is talk about the safe
transformations but now we know that if
we're not done we need to find a problem
to work on using that depth of
functional composition business and then
after that we apply heuristic
transformation and the waste legal
designers program is he found just one
problem work on did one transformation
then went back around the loop because
the eristic transformation is a little
harder to apply to the the safe ones so
I've given you an accurate portrayal of
what this program did except for one
thing which I would like now to go back
and patch up and that thing is over here
you know what to do with something like
this
well we got to that and a board that's
disappeared but when we try to deal with
this we had to find a heuristic
transformation and when we decided to
work on this it must have been the case
that this was the simplest problem at
the leaf node at a leaf node that has
not yet been solved so what's the
functional composition depth of this
it's three back over here we have
something that has a depth of functional
composition of two so when the program
actually ran on this particular problem
it stopped a few inches short of the
finish line and went back and screw it
around with another problem for a little
bit before it gave up and came back here
so it's always looking across the whole
the whole tree the leaves of the tree
whatever it has to find a place to work
on with the heuristic transformation it
happened to look at all the leaves of
the tree that had not yet been dealt
with tried to find the easiest one and
that could involve a lot of backing up
and starting over on a branch of the
tree that it previously ignored a small
detail not a particularly important one
now where are we we've got the we've got
that guy there we've got our complete
architecture
we've got our solves problem and now we
can start reflecting on what we've done
you can say for example how good an
integration program is this and the
answer is it was pretty good
this machine that Slagel was using was a
machine it was over in building 26 and
we were so proud of it there was behind
glass and you could go there and watch
the tape spin it was really a delight
32k of memory that's 32 K of memory it's
amazing that he was able to do anything
with a machine of that size let's see
yes here's a clean one well
can't do board geometry and talk at the
same time we can now ask some questions
about how well the program performed it
was given 56 of the hardest problems and
it got 54 right what happened when it
didn't get the other two well you might
be right if you said it all probably ran
out of memory since it had 32 K but in
fact it just was lacking two
transformations that were needed in
order to solve the whole entire set of
final quiz problems so it when a program
fails is often the most interesting
question you can ask this is an
exception this failed for uninteresting
reasons on two of the 56 problems that
it were that it was given to now you're
the next question you can say is what is
the depth of the tree in the maximal
case and the answer is it's that case we
just worked out and since I once again
lost the whole tree I'll tell you that
it's deputy depth was 7 when you take
off that minus 5 so in the worst case
this thing had to go down 7 levels
that's the worst case a more interesting
question is what was the average depth
and that was approximately three and now
we're beginning to say something not
only about Schlegel's model of how
freshmen works but we're beginning to
say something about the nature of the
domain in the domain of calculus
problems integrals expressions that are
given to freshmen in that domain the
average depth of problem reduction
needed to solve the problems three such
as not very not very complicated if it
were ten you'd say wow how can anybody
ever do those problems if it were five
you'd say well only people destined to
be math professors are going to get
anything right
because 3s ordinary mortals can do a
pretty good job
another question of even greater
interest is how many branches were
unused
here's an unused here's a branch that
turned out to be unused didn't pursue
that and so you might say well maybe
there are a lot of unused branches maybe
have to be pretty smart about your your
method for determining what problem to
work on because otherwise you'll go down
a lot of raffles and guess what here's
another statement about the domain in
the domain of problems that freshmen
could work on a final the number of
unused branches is about one so that
means this tree kind of keeps itself
together and doesn't run down to a very
large bushy useless tree so this means
that the depth of functional composition
which Brett suggested as a technique for
recognizing the right problem to work on
was a choice that didn't actually matter
because the tree doesn't grow deep it
doesn't grow broad doesn't matter what
you use to decide what to work on
because in the worst case you'll just
generate a couple of extra useless notes
but they very quickly run to a fun -
dead end so you don't have to do
anything more with it so now the next
thing we need to do is back you and
further away from this program and ask
ourselves some questions about the
nature of the what we've been doing and
that brings me to the things I've got on
that upper right-hand board one of those
things is a catechism having to do with
knowledge and what we've done informally
as we went through this program was
we've asked questions such as what kind
of knowledge is involved in doing this
well knowledge about transformation
knowledge about how old trees work and
when we're done with the problem
knowledge about what things don't need
to be transformed because you can look
them up in a table that's the kind of
knowledge that is involved in doing 1801
and if you do 80 no circuit theory six
on circuit theory or six oh Maxwell's
equations is the same thing
you have to ask questions of this sort
about the nature of the knowledge
involved and question number one as
always what kind of knowledge is
involved is it kerkoff's laws Maxwell's
equations what is it the next question
is how is the knowledge represented and
our answers here are well all this stuff
ultimately was represented in lists best
expressions some of the knowledge was
recorded in a table of s expressions
that show what transformations there are
there was a similar table of integrals
knowledge about gold trees was embedded
in a procedure so it was procedurally
represented and so for each of the
categories of knowledge there's a way it
gets represented how is it used
straightforward
transformations are used to make the
problem simpler the table is used to
trim off and complete the to serve as
the bottom of the tree those are the
ways in which the knowledge is used and
then there's a question of course of how
much knowledge is required something
that's useful to know if you're if it's
late at night you have two finals the
next day you're not sure which of course
you should study so how much knowledge
might you suppose was actually in this
program I've shown you a glimpse of the
kind of knowledge that's involved in the
program I've answered a little bit of
question five what exactly but how much
knowledge was involved you might be
surprised by the answer first of all the
table of integrals I've listed only
three things there there are lots of
other things you can think of like
integral of e to the X is e to the X but
in the end what's legal found as a table
of only 26 elements was enough to solve
all of these problems how about the
transformations here the safe ones now
twelve how about the heuristic ones
about twelve so just a little few bits
of pieces of knowledge here and they are
sufficient to do everything you need to
do in order to do with the integration
problems on a calculus final that was a
surprise another surprise of a similar
kind also about knowledge is that the
relationship between the method to be
used and the characteristics of the
problem was almost a diagonal table that
means that you could in this domain make
the right transformation almost all the
time if you're a little bit smart and
never back up that was an observation
made by Joel Moses who became
subsequently our Provost here at MIT for
a while and he wrote a program that
could solve anything even you know that
it would beat the most dedicated
mathematicians of integration and it's
and it's the sentencer in MATLAB today
but this is how it all works and now you
could write one of these things yourself
partly because you now have this
catechism this is the kind of stuff you
should ask anytime you're dealing with a
new domain it will make you smarter and
this is of course meta knowledge this is
knowledge about knowledge so this entire
day for ism isn't quite what we are
going to complete ourselves with we're
going to say that knowledge about
knowledge is where the real power is now
there's one final thing that this
program does for us it tells us
something about our appreciation of what
it means to be intelligent you know that
in the beginning of this hour I asked
you to think about whether a program
that could do symbolic integration would
be in anyway where should be considered
to any degree intelligent and I'm
imagining
that even in the day in these days of
MATLAB and whatnot many of you said well
yes I learned how to do that MIT or late
in high school so it must be smart but
now that we've completed this discussion
I also expect that your book feeling of
intelligence in this program is somewhat
diminished because what happens is that
when we understand how something works
its intelligence seems to vanish you've
seen this in your friends right they
solve some well no they they solve some
problem they seem super smart then they
tell you how they did it and they don't
seems too smart anymore so let me
conclude the let's conclude our
discussion today with a little story I
was once some a long time ago I was
talking with a student who said
computers cannot be intelligent and I
said ok maybe you're right
but let me show you this program so I
showed it the integration program
working on problems like this and after
I showed him a couple of those examples
as well all right I guess maybe they can
be intelligent I'm learning how to do
that it's not always easy then I made a
fatal mistake I said let me show you how
it works and we spent the an hour going
through it like this and at the end of
that time he turned to me and said I
take it back it's not intelligent after
all it does integration the same way I
do
you