Reasoning Under Uncertainty- Artificial Intelligence Video Lecture - Computer Science Engineering (CSE)

right so we are going to start a new
topic from this lecture and this topic
is also a very important topic in AI
namely we will be studying reasoning
under uncertainty so we have to rush up
our school fund on probability there
will be quite a bit of probability
coming up for you so let us get started
so why do we need reasoning under
uncertainty so let us see a few examples
to get a clearer picture about why this
is at all necessary firstly the problem
of handling uncertain knowledge suppose
we are given the rule that for all P
symptom P toothache implies disease P
cavity so this is that whenever one has
a toothache then that person has the
disease which is a cavity in the truth
now this is not correct because
toothache can be caused in many other
cases right so we cannot say that
whenever we have to take it is because
of cavity so if we have to actually
analyze the case the the problem of
toothache then we have to
comprehensively specify that what are
the different causes for which this can
happen so cavity is one gum disease is
one impacted wisdom is one and so many
other cases for which we can have a to
take now a numerating all of these is a
problem because all of these may not be
known right and you can miss out quite a
few
like for example you can have to take
also if somebody is hit you on the teeth
which you would probably not put in this
rule right but for a diagnostic system
unless you have the complete set of
causes then this rule will formally not
be correct because we are using
implication here let us try to model
this in the other direction so suppose
we want to say that for all P disease P
cavity implies symptom P to take so we
are saying that whenever there is cavity
then the symptom is too thick right but
this is not correct either because all
cavities do not cause too thick so even
if someone has a cavity that person may
not have a to take so these are the this
is a kind of scenario which is very
difficult to represent unless we use
some kind of statement which says okay
sometimes the cavity can cause to take
and if we have to take then sometimes it
is because of the cavity right now what
are the reasons for using probability
one is that without using probability
the specification becomes too large as
we will see you have to explicitly
enumerate the complete set of
antecedents or consequence for a
exception less rule which in practice is
very difficult to achieve
it can also be because of theoretical
ignorance the complete set of
antecedents is not known we do not know
what are the different kinds of diseases
which can cause toothache and the third
one is practical in ignorant where the
antecedents is known but their truth is
not known so if we do not have a
mechanism of determining the truth of
those antecedents in practice we will
never be able
apply those rules so to apply a rule the
antecedents will have to be there in the
knowledge base now if one of the
antecedents is something which we cannot
experimental II measure then we will
never be able to add that antecedent
into the fact base and therefore we will
never be able to apply that rule right
so in the cases where something is
difficult to measure we can leave that
to chance based on previous experience
about the percentage of cases where that
actually happened right before we come
to the axioms of probability
let me explain a few subtle points about
this see one thing is that when we are
unable to model a set of rules exactly
and completely then we resort to things
like probability that people also have
resorted instead of using probability to
other kinds of logic like fuzzy logic
now the difference between possibility
which is part of fuzzy logic and
probability which is the classical
Bayesian analysis that we do the
difference is very subtle
for example suppose we are talking about
how the obesity of a person is related
to cardiac diseases right so we are
saying that if if the person is fat then
with certain probability that person
will have a cardiac problem now when we
are talking about a given person then we
have to talk about what is the
probability that he is fat now the
scenario is that we do not we do not
know that person we have not seen that
person and based on some other
information we have some certainty that
yes this person
is fat with so much probability suppose
we want to reason about the probability
of cardiac diseases among Indian people
now we have statistics about what
fraction of Indian people are fat so
therefore we can have a certainty or a
probability that a given X is fat right
and then with that if we multiply it
with the probability that if this person
is fat if X is fat the next will have
cardiac disease with a 90% probability
then okay let me write it down is
becoming complex okay suppose we know
that probability that
this we know from the population of X
from Indians if X is Indians we know
what percentage of Indians are fat so we
know that if X is an Indian what is the
probability that is fat and then we are
given that if X is fat then
X has
let us call that CHD with probability of
0.7 right then we ask that what is the
probability that X has CH T so this we
can say that it is 0.2 times 0.7 right
which is equal to 0.14 okay
yes plus 0.8 into y why should we have
this
yes right right right so we also have to
consider the case where X is not fat but
still has a heart disease right so that
case that probability will also have to
be added with this right so we will see
how we do that analysis once we go into
the Bayesian analysis but the point I am
trying to make air is that this is a
probability that we are given and we can
apply that to determine the probability
of some other event but fuzzy logic
deals with a slightly different
philosophy there we we can see the
person X is given to us okay but we are
trying to say he is fat but how fat okay
how fat fat is not a true true false
value you cannot say that that this
person is that if they if the weight is
above this then in then his fat if it is
below this then he is not fat fat is
actually a gradation right from thin to
fat we have a we have a distribution
right so fuzzy logic tries to reason in
that sense it tries to look at the the
the truth value not as boolean but as a
value between 0 & 1
so you say that X is very fat then that
means that that the truth of X being fat
is point 8 and X is moderately fat which
is 0.6 and so on right now there you see
it is not a question of whether X is fat
or not it is a question of how fat is X
and the rules therefore also has to be
graded that way right so that is a
different kind of analysis which people
do so I just want to
Doucette at the beginning because later
on when we talk about these different
kinds of reasoning you have to be sure
that which is what so one is probability
and the other is the gradation of the
truth axioms of probability so let me
ask a simple puzzle this is a this is a
puzzle which goes like this that we are
given that the probability that one
person carries a bomb into the aircraft
is 0.1 0.1 okay so probability that
someone carries a bomb into the aircraft
is 0.1 right then what is the
probability that two people carry a bomb
into the aircraft so it is point zero
one right now one professor see is that
okay the probability of two people
carrying a bomb into the aircraft is
significantly lesser than the
probability of one person carrying a
bomb so what he does is he carries a
bomb with him he carries a bomb with him
into the aircraft so the question is
does that reduce the probability that
another person will come up with a bomb
right so why why why is that what is the
difference between these two the
difference is conditional probability
the probability that two people carry a
bomb into the aircraft is this fine but
probability that another person carries
a bomb into the aircraft given that one
person has carried it is again point one
right so that is what we
we have as conditional probability so
the important thing is to realize that
which events are independent and which
are conditional to each other and that
will be the core thing that we will that
will form the basis of all our infancy
so these are schoolbook axioms of
probability PA or B is PA plus PB minus
PA and B right then we have Bayes rule
everyone remembers Bayes rule right okay
so let us move into the next belief
networks belief networks are networks
with the following we have a set of
random variables as knowns we have
directed links the intuitive meaning of
a link from node X to node Y is that X
has a direct influence on Y cause-effect
relationship between this now each node
has a conditional probability table that
quantifies the effects that the parent
have on the node and the graph has no
directed cycles right because we assume
that there is that there is a cause
effect relationship between the events
and there is no feedback right networks
with feedback has been also studied but
in this particular lecture we are not
going to consider that okay let us start
with an example so this is an example
where we have a burglar alarm installed
at home the alarm is fairly reliable at
detecting a burglary so with some
probability whenever there is a burglary
the alarm will go it will
but it also responds at times to minor
earthquakes so if there is a minor
earthquake then also the burglar alarm
can ring actually this particular
example is due to judea pearl who was
who is and in fact a residence of la los
angeles and that is why his interest in
earthquakes so they have it quite
frequently right to neighbors on hearing
the alarm calls the police
john always calls when he hears the
alarm but sometimes confuses the
telephone ringing with the alarm and
calls then too and many likes loud music
and sometimes misses the alarm all
together because of the music right so
this is what we are given so we will
model this as a belief network so this
is a example of the belief network
slides please slides please
yes so let us see what we have here
these are the events so burglary
earthquake alarm John calls and miracles
and this ordering that we have done is
our choice of doing this right you can
construct for the same scenario
different belief Network that but the
correct one will have certain desirable
properties so we will study this one
first and then later on we will see that
if we model the same thing in a
different in a different topology then
we will get a different kind of property
so what this says is it says that
burglary is an independent event and the
probability that the burglary occurs is
point zero zero one probability that an
earthquake occurs is point zero zero two
right so these figures are all from Los
Angeles the probability of earthquake is
more than the probability of burglary
then we have this alarm and this table
tells us that given that it is a
burglary and given that there is an
earthquake what is the probability that
the alarm goes off so if both a burglary
and an earthquake has taken place then
it goes off with 0.95 probability if
there is a burglary and there is no
earthquake then also with 0.95
probability the alarm rings if there is
no burglary but there is an earthquake
then the alarm goes off with probability
0.29 so so sometimes when there is no
burglary but there is an earthquake the
alarm mistakenly goes off if there is no
burglary and no earthquake then the
probability that the alarm goes off is
very less point zero zero one right if
you sum up all these probabilities then
you will find that you have one no
I think this should be point zero one
wait wait wait wait wait just just a
minute okay these are for all this okay
if you if these cases where exhaustive
then you would get one right if is if
these cases were exhaustive then you
would get one but these are not always
independent so that is why you will get
this thing now this overlap is there
okay
I will come back to this and explain
this later is okay here we have John
calls and given the alarm takes place
the probability that John calls is 0.9
and if the alarm does not go off then
the probability of John calls is point
zero five because this is when John
mistakes the telephone ring to be the
alarm and when we look at Mary calls
then when there is an alarm then Mary
calls with 0.7 the remaining 0.3 is
because of the music
yes and when there is no alarm then also
Mary might call but with a very small
probability right so this is the belief
Network now how do we use this network
to first we will see how we can use this
network to answer different kinds of
queries and we will also see how we can
construct this Network now the joint
probability distribution of a set of
variables is given by this now let us
see what we mean by this
the probability that we have a that that
x1 to xn take a given value is given by
the probability of each X i given that
the parents have taken place let us see
an example probability of the event that
the alarm has sounded but neither a
burglary nor an earthquake has occurred
and both Mary and John call right so let
me write this down here so I have
probability of John calls and Mary calls
and there is an alarm but no burglary
and no earthquake ok so what we will do
here is we will start breaking this up
as follows we will break this up as
probability of J given a right
and times probability of okay YJ given a
because if you recall in the in the
belief network that we had here slides
please in the belief network slides
please in the belief network that we had
here slides please in the belief network
that we had here we had J only alarm was
the predecessor of John calls so that is
why for the probability of John calls
only given the alarm is what is relevant
okay so we have here PJ given a and then
PM text please given a because Mary
calls given alarm and then probability
of a given not B and not E and then
times probability of not B and
probability of not e right so it's the
is the product of all these
so what does this mean this means that
when I have a set of literals here then
the probability of the conjunction of
this in the belief Network is given by
the probability of each of those events
given the values of the predecessors of
that those in the belief network right
now if some of these was missing like if
a was not there then also we will have
to bring this here and then reason about
probability of a right so if we just
wanted to know about probability of J
for example then we will have to first
look at probability of J given a times
probability of a
yes and also for not a weight then plus
probability of je given not a write
times probability of not a in this case
because we were given a so that is why
these terms disappeared wait so we had
we will have this and then again this
probability of a will be broken up
similarly in terms of the probability of
a given what were the pc predecessors of
a B and E so B and D then probability of
a given not B and the probability of a
given B and not E and so on that we have
to break it up like this and analyze
them right so the idea is that for any
event if we have to compute the
probability then we have to compute it
in terms of the predecessors of these
events in the belief Network right and
those probability values are the ones
that are given in the table for example
when we have PJ given a so that
probability is given in the belief
Network so if you look at the belief
Network then probability of J given a is
0.9 right so for this we will take a
take this down as 0.9 times probability
of M given a M given a here is 0.7
and then if you look at this probability
of a given not be and naughty not be n
not is this one point zero zero one
point zero zero one probability of not
be is what one minus point zero zero one
right and probability of not e is one
minus point zero zero two
slides please here text yes no no this
is not product this this will also have
to be done with PB and D and then plus
with
right so so now this makes sense that
when we have the joint probability
distribution of a set of events then
what we have here is the product of the
PX I given parents of X I for each of
them yes the belief Network is attempt
to model the cause-effect relationship
between the events along with their
probability values right so there are
two phases in in this reason the first
phase is to learn or the model the
belief Network how do we do that one way
could be that we know the events and we
know the cause-effect relationship
between the events suppose for a medical
diagnostic system the doctor tells us
that this is if this happens then that
will happen with so much probability and
so on and we just write it down in the
form of a belief Network right that is
one way of constructing the belief
Network and then when we actually do the
diagnostic and we want to find out that
if that person has fever then with what
probability does he have leukemia right
then we can find out those probabilities
by analyzing the belief Network
right that is the use of the belief
Network but there has been also a
significant amount of research on
learning of belief networks from
experimental data and one of the most
interesting work that has been done in
the last couple of years is on the
following thing that if you have a
genome a genome is a is the DNA sequence
that we have and
there is a thing called DNA microarray
with which you can do experiments and
find out that for a given sample which
are the genes that are being expressed
right so suppose we take a cancer
patient and we analyze for a given
protein injection that what is the set
of genes that are being expressed right
so we have some twenty samples of them
so we know that these genes have been
expressed and similarly we have for the
healthy people also a set of genes which
are being expressed right then what we
try to do is we try to find out cause
effect relationships between these jeans
because expression of one gene produces
some protein which in turn causes some
other gene to express right for example
when we are born we are born with only
one cell right and that cell multiplies
and creates all the organs etcetera how
does this happen
it happens because there is a genetic
pathway through which it happens so
depending on what we have in the cells
app certain genes will express more at
that time there are genes in our body
which are expressed only during the
first couple of weeks of our
fertilization and thereafter they are
not expressed anywhere anytime in the
future so what happens is those genes
will express they will create some
proteins which will cause other genes to
express and slowly this sequence of
expressions will cause the entire
organism to develop so there is a lot of
research to model these in terms of
Bayes networks and to discover that what
is this cause effect relationship so
what are the steps that we have to do
there we have to first decide which way
the links will go we have the set of
events the events are this gene
expresses this gene expresses etcetera
but we do not know what is
the which causes which so one thing is
to learn the direction of those links
and the other is to learn the
probabilities of those links so so
learning that from experimental data is
a subject on its own which we will not
address into in detail but once we have
the belief Network then we can always
reason and find out the probabilities of
more complex events from the belief
network which is we what we will study
in more detail
the key feature of the belief network is
conditional independence now we have
noted here okay let me go back to this
slide we have noted here that the joint
probability distribution in a belief
network is given by probability of X i
given the parents of x i write and take
their products then you will get the
probability of x1 through xn right now
how does that come from where does that
that formula come from it comes from
here so I start with P x1 through xn so
I can use Bayes rule to break it up like
this right then I can use Bayes rule on
this part to again break it up like this
so this one will again break up into xn
minus 1 given the remaining ones and the
probability of xn minus 2 2 X 1 which
recursively can get broken down and then
we will have this as the result right
now what is this ordering that we have
this ordering of the variables is the is
1 topological order of the belief
Network so the larger index variable is
towards the bottom so when I am
analyzing X I then all these X X 1
through X I minus 1 are all variables
which are topologically having a lesser
number than X I right so these set of
variables is the superset of all those
variables which can influence the value
of x I but all these are not going to
influence X I not directly I can
as the cause the cause of X I expressing
in terms of the parents of X I in the
belief Network so the belief network
tells me that okay
it's these parents of X I whose values
are instrumental in determining the
value of x I'd right you could have
transitively other factors influencing
it transitively parents parent parents
parent and any ancestors like that but
if I knew the values of the immediate
parents then I can get the probability
of X I by looking up the probability
table that that is there in the belief
Network so those of these which are not
parents of X I can be dropped because
this term is going to remain the same
and that is what we mean by conditional
independence right so it means that this
term can be simplified to just the
parents of X i PX i given parents of X I
so that is the conditional independence
and that makes our analysis much simpler
than having to do with all the variables
together okay so how do we construct the
network I'll I will just outline this
today and we will discuss it in more
details in the later classes choose a
set of relevant variables X I that
describe the domain that is selecting
the set of events choose an ordering for
the variables this is very important the
ordering has to be such that we have the
cause-effect relationship in the proper
direction but what happens if you choose
an incorrect ordering we will discuss
that later
you will still be able to construct a
belief network but there will be certain
problems we will come to that later then
while there are variables left pick a
variable X and add a node for it set
parents of X to some minimal set of
existing nodes such that the conditional
independence property is satisfied so a
minimal set which such that I can write
probability of X given all its
predecessors is equal to the probability
of X given its parents right so that is
what we mean by conditional independence
and then define the conditional
probability table for X this can be
given or it can be extracted from the
experimental data now see this step 2 is
the most important step if you are able
to do this properly from your existing
knowledge then learning the conditional
probability table is much easier because
then you can actually just check out
what is the probability of x given the
parents of X by just analyzing
experimental data but if you do not know
this ordering if this ordering is
incorrect then also you will get
conditional probability tables but they
will not be what will happen is that
this set of parents of X is going to be
very large and the larger the parent set
of X the larger is the size of your
conditional probability table if you
have two parents of X then you have four
entries in the conditional probability
table if you have 10 parents of X then
you have 2 to the power of 10 entries in
the conditional probability table so if
you have the ordering appropriately done
then you will find that the number of
parents of X for every X will be limited
otherwise it will become very large so
we will see in the next lecture that how
we are able to deduce this to do to some
extent
19:51 a young nation aspiring to find
ways to fulfill a dream humor lays the
foundation of an institution that will
give aspiring technic rats
the license to fly high the first Indian
Institute of Technology is born at
colored board
founded on the basis of the
recommendations of the NRS Sarkar
committee that was set up in 1945 to
consider the development of higher
technical institutions in India the
Institute was first established in five
esplanade East Kolkata before it moved
to Kirk pool in 1951 with sir Garin
Chandra Ghosh as the first director and
dr. BC Roy as one of its founding
Guardians the Institute established
itself as the symbol of a young dynamic
and resurgent nation as top students rub
shoulders with the most celebrated of
professors and scholars
visions took shape and iit caribou
continued to play the pioneering role
that was envisaged for it
enabling India to become a knowledge
powerhouse that it is today
at every stage of its evolution iit
kharagpur remained ahead of its times it
provided the best of facilities for the
budding technologists helping them shape
their own as well as the nation's future
indeed today iit carrot Poole has
blossomed into a time-tested venerable
Institute of learning with the rich
experience of converting individuals
into brilliant professionals through 50
glorious years as you cross the campus
gate you feel the distinct NIP that is
iit kharagpur the spirit of objective
inquiry and lateral thinking hangs heavy
in the air
the modern township like camper society
color pools set in Sylvan surroundings
is self-sufficient in all respects from
modern bangs to the good old post office
from vast playgrounds and well-equipped
gins to modern auditoría and open-air
theaters
and from the quiet fiber-optic lute
residential quarters for the faculty to
the web-enabled hostel rooms for the
students at iit Carriacou lush green
bowers of tranquility coexist with smart
cards and ATMs spread over six hundred
and ninety hectares of sprawling cyber
habitat a hundred and twenty kilometres
from kolkata iit kharagpur is one of the
largest network campuses in asia just
the academic complexes itself spreads
over a built-up area of about 2 million
square feet of which a hundred and fifty
thousand square feet is the new complex
that commemorates the golden jubilee
celebrations and that's not all it is
the only IIT to have conquered territory
beyond its own through cutting edge
courses offered in its extension
campuses at Kolkata and Ruben issuer IIT
Kharagpur is not just about its large
campus but its diverse range of
activities it offers the widest spectrum
of disciplines ranging from aerospace
biotechnology cryogenics - architecture
mining and agricultural engineering
supported by strong faculties of
sciences humanities and management there
are more than 30 departments and centers
that offer the largest number of
undergraduate and postgraduate courses
amongst the IITs the courses are
ever-evolving and show the way for other
sister institutions the richness in its
diverse activities is showcased by the
technological support the institution
provides in areas like architecture
agriculture post-harvest technology and
medical sciences
the institute has revolutionized and
popularized rice milling technology the
other major contributions of iit
kharagpur have been in the critical
fields of Defence railways space
research our systems and petrochemicals
all these activities directly empower
the human requirements of the nation
advanced facilities at the Institute
make it possible to undertake
cutting-edge research and service
sponsored research projects the array of
equipment ranges from aerodynamic
testing laboratories to intelligent
machining centers atomic spectrometers
to VLSI design labs when Mikula beam
epitaxy to anechoic chamber farce
protein liquid chromatographs
to liquid nitrogen plans
the cutting-edge technologies are at par
with the best research facilities across
the globe in fact the volume of research
and development activities at the
Institute is incredible in terms of the
number of patents it owns the volume of
industrial consultancy it provides and
the revenue that it ends from all these
make iit kharagpur a class apart and
strengthens its position as the true
pioneer in technological education in
India the Institute library deserves a
special mention fully web-enabled it is
one of the largest in Asia with over
three hundred and twenty four thousand
volumes of material including ebooks
videos microphone and baton documents
Bin's that ensure a student's mind
develops at the right pace
along with its strong sense of academics
which is ensured by a strict selection
process life at Carrick pool is a
celebration of well life and at its
heart are the students in fact the same
goes that you can take an IIT and out of
kgp 'the but not gay GP out of an IIT M
you've left a part of you bar for most
of the students life in the campus was
in itself a festivity a collage of
activities that shape their mind and
body a collage of events that was a
synthesis of competition and cooperation
a collage of interests as diverse as
dramatics and ham radio yes life at
Caribou has always been exciting and the
years cemented lifelong bonds as lives
mingled over cuts of joy and stretched a
row stimulating semesters
you
the holes were there blocks and wings
connected by charming catwalks remain
ensconced in their own world a collage
of memories infrastructurally adequate
architectural II meticulous and
holistically inspiring where students
wherever they might be from invariably
come to their own developing their
individual talents honing their skills
to take on challenges with confidence so
they can move ahead in fulfilling their
dreams
what makes iit carrot balls so unique is
its environment undiluted by the
diversions of metropolitan surroundings
the close-knit campus life enhances the
entrepreneurial and innovative spirit of
the achievers to be in an environment
that is so stimulating it is only
natural that down the years iit carrot
bore has consistently produced
well-rounded individuals many of them
are celebrity
their own right holistic grooming has
had a lot to do with this so no matter
which walk of life they choose the IIT
kgp ID stands tall and so does the
institution that bred him in logistic
splendor
the alumni of this Institute command
global respect their distinguished
presence at the helm of global joins is
a matter of national pride for the
students of IIT Kharagpur it is
impossible to erase any scratch of
memory about their alma mater in fact
some come back to invest sentiment pride
and money to see the Institute they call
home rise to even greater heights
structurally functionally as well as
holistically their singular aim is to
make iit kharagpur and Institute which
ever way you look at it par excellence a
man's journey into quiet accomplishment
and the Hall of Fame starts with the
right step and the training and
placement cell of IIT has been the
efficient facilitator in this regard for
over 30,000 graduates having placed more
than 95% of its students in a wide range
of industries consistently for over two
decades it is no wonder that the
Institute is the most preferred campus
for technical recruitment of quality
manpower
with infrastructure like industrial
power and communication facilities in
addition to its excellent research in
consultancy facilities step or science
and technology entrepreneur spark aims
to assist the budding entrepreneur into
a successful adventure capitalist
guiding him right from the concept
institutional financing production
leading up to the launch and marketing
of the product with its rich pool of
talent and excellent infrastructure it
is no surprise that through the last
three decades
IIT carrot pool has developed strong
layers all with the industry
SR I see or sponsored research and
industrial consultancy cell was
formalized as the special industry
interaction cell in 1982 devoted full
time to handle industrial projects and
consultancies and for deploying and
propagating intellectual property
successful sponsored research projects
straddle a wide spectrum ranging from
computers communication and
biotechnology to robotics photonics and
food processing
the setting up of a state-of-the-art
VLSI CAD laboratory and tie-ups with GE
in areas ranging from vehicle structure
design to electrical communication and
software technologies are excellent
examples of IIT correct poles
ever-evolving pioneering spirit
collaborations with a host of national
and industrial majors are a testimony of
its proven expertise and research
repertoire
haha listen - I didn't
indeed in this Golden Jubilee year as
the celebration continues pundit Nehru
would surely have been a proud man today
for him
IIT Kharagpur was always more than just
an Institute of Technology in his own
immortal words it is indeed a fine
monument of modern India