Transcript Extensions to FOL

Extensions to FOL
Extensions to FOL
•When the form of the statements provides useful information
•Rule-based systems
•Frame systems
•When FOL isn’t enough
•Default reasoning and circumscription
•Reasoning with uncertainty
•Degrees of membership (fuzzy logic)
•Reasoning about belief
What Does  Really Mean?
HasChildren  Mother
AB
definition of B
Raining  Wet
AB
A causes B
Fever  Infection
AB
A is a symptom of B
B causes A
LikeBig  GetHummer
AB
whenever A occurs,
B usually does too
So how should we reason with these very different things?
Rule-Based Systems
The logic:
So, given:
ab
is equivalent to:
fever  infection
fever  infection
fever
infection
Conclude:
Given:
a  b
fever  infection
Conclude:
But are these two inferences equally useful?
fever  infection
infection
fever
An Example for a Design Task:
XCON (1982)
From XCON (1982):
If: the most current active context is distributing
massbus devices, and
there is a single-port disk drive that has not been
assigned to a massbus, and
there are no unassigned dual-port disk drives, and
the number of devices that each massbus should support is known, and
there is a massbus that has been assigned at least one disk drive that
should support additional disk drives, and
the type of cable needed to connect the disk drive to the previous
device on the massbus is known
Then: assign the disk drive to the massbus.
An Example for a Diagnosis Task:
Mycin (1975)
If: (1) the stain of the ogranism is gram-positive, and
(2) the morphology of the organism is coccus, and
(3) the growth conformation of the organism is clumps
Then: there is suggestive evidence (0.7) that the identity of
the organism is staphylococcus.
Simple Examples Today
eXpertise2Go: http://www.expertise2go.com/
AcquiredIntelligence: http://www.aiinc.ca/demos/
(whales, graduate school)
DecisionScript:
http://www.vanguardsw.com/decisionscript/Examples.htm
Implementation of Rule-Based Systems
If (1) the suggested technique category is correlation and regression
analysis, and
(2) one of the values of the desired correlation/regression result is a
measure of the degree to which 2 variables move together
Then the suggested analysis approach is to calculate a sample correlation
coefficient
If a  b  reply(sampcor)
•Prolog: The KB:
A query:
reply(sampcor) :- a, b
?- reply(X)
Use backward chaining to answer the question.
•Expert system shells: Typically combine methods
Expert System Shells
Some rules are best used in forward chaining mode. For
example, data collection and reasoning from symptoms.
Other rules (e.g., how to achieve goals) are best used in
backward chaining mode.
All these rules may also want to exploit other kinds of
knowledge, like default information associated with classes of
objects:
Inheritance, Again
birds
ISA
robins
Instance-of
Tweety
canfly
T
ISA
ostriches
Instance-of
Richy
Scooter is a bird. Can Scooter fly?
canfly
F
Inheritance
Objects inherit from their parents:
•Scooter inherits from Bird the facts that:
•its birthmode is eggs, and
•it has two wings
Should Scooter inherit from Bird the fact that it can fly?
Default Reasoning
•The importance of default reasoning
•Default reasoning is nonmonotonic.
•Techniques for default reasoning
•Inheritance
•The closed world assumption
•Circumscription
•Maintaining consistency in nonmonotonic reasoning systems
Default Reasoning - Examples
Inheritance from superclasses:
x bird(x)  canfly(x) UNLESS ostrich(x)
The “normal” case:
x bird(x)  canfly(x) UNLESS (broken-wing(x) 
sick(x) 
in(oil-slick, x))
The closed world assumption:
can cats fly?
Abduction:
infection  fever
Given fever, can we
conclude infection?
Default Reasoning in Nonmonotonic
Inference in FOL systems is monotonic:
The addition of any new assertion that is consistent with the KB
will never cause a formula that was previously true to become
false.
Default reasoning may be nonmonotonic:
Birds can fly.
Tweety is a bird.

Tweety can fly.
But what if we now learn:
Tweety is an ostrich.
Tweety has a broken wing.
or
Implementing Inheritance
birds
ISA
robins
Instance-of
Tweety
canfly
T
ISA
ostriches
canfly
F
Instance-of
Richy
If we implement inheritance procedurally, we don’t have to write
the UNLESS clauses. We assume Tweety isn’t an ostrich.
The Closed World Assumption
The CWA: Any ground atomic sentences that are not asserted to
be true in the KB can be assumed to be false.
We make the closed world assumption for two reasons:
•We have to. In any complex domain, there may be a huge
number of possible facts and there isn’t time to mention each of
them explicitly:
•A database of classes mentions the ones that are offered.
•An inventory database mentions all the objects on hand.
•An airline scheduling system assumes that it will be told if
the power is out or the terminal has burned down or is held by
terrorists or there is a storm.
•It is consistent with felicitous human communication.
Implementing the CWA: Negation as Failure
A common way to implement the CWA: Interpret failure to
prove p as a proof of p.
Example:
 hasonhand(x)  uses(x)  mustorder(x)
How do we prove  hasonhand(x)?
Circumscription
x bird(x)  canfly(x) UNLESS (broken-wing(x) 
sick(x) 
in(oil-slick, x))
Is different from:
x bird(x)  broken-wing(x)   sick(x)   in(oil-slick, x)
 canfly(x)
Or:
x bird(x)  adult(x)  withmother(x)
One way to implement this is to create the predicate Abnormal:
x bird(x)  canfly(x) UNLESS Abnormal(x)
(broken-wing(x)  sick(x)  in(oil-slick, x))  Abnormal(x)
Circumscription
Then we circumscribe Abnormal, i.e., we prefer models in
which Abnormal is true of the smallest possible number of
individuals consistent with the rest of the KB.
But what happens if we are told just:
bird(Tweety) and then we conclude canfly(Tweety)
Then we are told:
broken-wing(Tweety)
How do we undo the conclusion canfly(Tweety)?
Abbott, Babbitt, and Cabot
Truth Maintenance Systems
The basic idea: Associate with each assertion one or more
justifications. Believe any assertion with at least one valid
justification.
Each justification is composed of two parts:
•An IN-list
•An OUT-list
We will define the operation of a TMS that operates as a
service to a separate reasoning system. The TMS doesn’t make
choices. It is just a bookkeeper.
The Structure of a Justification
Before Alibis
Abbott’s Situation, with Alibi
Babbitt’s Situation
Cabot’s Situation
The Big Picture
New Facts Come In
Deciding How to Resolve the Conflict
Abduction
Examples:
infection  fever
measles  spots
raining  wetsidewalks
If given:
fever, can we conclude infection?
spots, can we conclude measles?
wetsidewalks, can we conclude raining?
Uncertainty and Fuzziness
•Degrees of truth
John is tall.
John is very tall.
•Probability of truth
John is in Austin
Coin is heads
(p = .6)
(p = .5)
•Certainty of belief
John is in Austin (c = .2)
a wild guess
Coin is heads
(c = 1)
sure it’s 50/50
When Must We Deal with Uncertainty?
•Diagnosis:
Observe: spots, fever, headache. What’s wrong with the patient?
Observe: clothes are wrinkled and hot. What’s wrong with the dryer?
•Interpretation:
•Speech understanding
•Language understanding
•Image understanding
•Data interpretation
•Planning:
If I turn the steering wheel, where will the car go?
Probabilistic Reasoning
P(strep) = x (the probability that a random person has
strep right now)
P(staph) = y (similar)
Suppose that we can use the same drug in either case, so we
want to know
P(strep  staph) =
Probabilistic Reasoning
P(strep) = x (the probability that a random person has
strep right now)
P(staph) = y (similar)
Suppose that we can use the same drug in either case, so we
want to know
P(strep  staph) = P(strep) + P(staph) - P(strep  staph)
Probabilistic Reasoning
Suppose There are Three Factors
P(a  b  c) = P(a) + P(b) + P(c)
- P(a  b) - P(a  c) - P(b  c)
+P(a  b  c)
P(a  b  c) =
P(a  b  c)
- P(a) - P(b) - P(c)
+ P(a  b) + P(a  c) + P(b  c)
Conditional Probability
P(measles  spots) = P(measles | spots) P(spots)
definition
P(measles  spots) = P(spots | measles) P(measles)
P(measles | spots) =
P(measles  spots)
P(spots)
P(measles | spots) =
P(spots | measles)  P(measles) Bayes Rule
P(spots)
definition
Examples from Diagnosis and Interpretation
P(measles | spots) =
P(spots | measles)  P(measles)
P(spots)
P(word x | sound y) = P(sound y | word x)  P(word x)
P(sound y)
Word = Argmax(P(sound y | word x)  P(word x))
x
Naïve Bayes Classifier
What if Multiple Observations Are Available?
P(measles | spots  fever)
= P(spots  fever | measles)  P(measles)
P(spots  fever)
Assume spots and fever are independent:
= P(spots  fever | measles)  P(measles)
P(spots  fever)
= P(spots|measles)  P(fever | measles)  P(measles)
P(spots)  P(fever)
Disease = Argmax(P(spots|x)  P(fever |x)  P(x) )
x
Not Quite So Naïve Bayes Classifier
Comparing chicken pox (pox) to measles:
P(measles | spots  fever)
= P(spots  fever | measles)  P(measles)
P(spots  fever)
Assume spots and fever are independent given measles or pox and
measles and pox are independent:
= P(spots|measles)  P(fever | measles)  P(measles)
P(spots  fever)
= P(spots|measles)  P(fever | measles)  P(measles)
P(spots|measles)*P(fever|measles)*P(measles) + P(spots|pox)* P(fever|pox)*P(pox)
Disease = Argmax(P(spots|x)  P(fever |x)  P(x) )
x
Learning Naïve Bayes Classification
An important aspect of naïve Bayes classification is that a
classifier can be learned.
Where do numbers like p(spots | measles) come from?
Answer:
patient
diagnosis
fever
cough
spots
sore throat
sneezes
achy
1
Measles
Yes
Yes
Yes
No
No
Yes
2
Measles
Yes
No
Yes
No
No
Yes
3
Measles
Yes
No
No
No
No
No
4
Chickenpox
Yes
No
Yes
Yes
No
No
5
Chickenpox
Yes
No
Yes
No
No
No
Various ad hoc Approaches
Unfortunately, it often happens that we don’t have all the joint
probabilities required to compute true probabilities for our
conclusions. So a variety of approximate methods are used.
http://www.expertise2go.com/webesie/tutorials/Inference/Conf
idence1.htm