Artificial Intelligence

Non-monotonic Reasoning
 Non-monotonic reasoning Often available

knowledge is incomplete.
 However, to model commonsense reasoning,
it is necessary to be able to jump to plausible
conclusions from the given knowledge.
 To draw plausible conclusions it is necessary
to make assumptions.
 The choice of assumptions is not blind: most
of the knowledge on the world is given by
means of general rules which specify typical
properties of objects. For instance, "birds fly"
means: birds typically fly, but there can be
exceptions such as penguins, ostriches, ...
 Nonmonotonic reasoning deals with the
problem of deriving plausible conclusions,
but not infallible, from a knowledge base (a
set of formulas).
 Since the conclusions are not certain, it
must be possible to retract some of them if
new information shows that they are wrong
 Classical logic is inadequate since it is
monotonic: if a formula B is derivable from
a set of formulas S, then B is also derivable
from any superset of S:
S ⊢ B implies S ∪ { A} ⊢ B, for any formula A
Example:
let the KB contain:
Typically birds fly.
Penguins do not fly.
Tweety is a bird.
It is plausible to conclude that Tweety flies.
However if the following information is
added to KB
Tweety is a penguin
the previous conclusion must be retracted
and, instead, the new conclusion that
Tweety does not fly will hold.
What is TMS?
A Truth Maintenance System (TMS) is a Problem
Solver module responsible for:
 Enforcing logical relations among beliefs.

 Generating explanations for conclusions.
 Finding solutions to search problems
 Supporting default reasoning.
 Identifying causes for failure and recover from
inconsistencies.
TMS Structure
Justifications
Inference TMS
Engine (IE)
Beliefs
Knowledge Belief - 
Base expression which can be true or false

Justification -

inference rule (step) which lead to
a belief
 Premise -
true fact (no justification needed)
6
1. Enforcement of logical relations
 AI problem -> search.
 Search utilizes assumptions.
 Assumptions change.
 Changing assumptions -> updating
consequences of beliefs.
 TMS: mechanism to maintain and update
relations among beliefs.
1. Enforcement of logical relations
Example: If (cs-501) and (math-218) then (cs-570).
If (cs-570) and (CIT) then (TMS).
If (TMS) then (AI-experience).
The following are relations among beliefs:
(AI-experience) if (TMS).
(TMS) if (cs-570), (CIT).
(cs-570) if (cs-501), (math-218)
 Beliefs are propositional variables

 TMS is a mechanism for processing large collections of
logical relations on propositional variables.
2. Generation of explanations
 Solving problems is what Problem Solvers do.
 However, often solutions are not enough.
 The PS is expected to provide an explanation

 TMS uses cached inferences for that aim.
 TMS is efficient:
 Generating cached inferences once
is more beneficial than
 running inference rules that have generated these
inferences more than once.
2. Generation of explanations
Example:
Q: Shall I have an AI experience after completing the CIT program?
A: Yes, because of the TMS course.
Q: What do I need to take a TMS course?

A: CS-570 and CIT.
 There are different types of TMSs that provide different ways of

explaining conclusions (JTMS vs ATMS).
 In this example, explaining conclusions in terms of their immediate
predecessors works much better.
3. Finding solutions to search problems
B
A D
C E
 Color the nodes: red (1), green (2) yellow (3).

 Adjacent nodes are of different colors.
 The set of constraints describe this problem:
A1 or A2 or A3 not (A1 and B1) not (A3 and C3) not (D2 and E2)
B1 or B2 or B3 not (A2 and B2) not (B1 and D1) not (D3 and E3)
C1 or C2 or C2 not (A3 and B3) not (B2 and D2) not (C1 and E1)
D1 or D2 or D3 not (A1 and C1) not (B3 and D3) not (C2 and E2)
E1 or E2 or E2 not (A2 and C2) not (D1 and E1) not (C3 and E3)
3. Finding solutions to search problems
To find a solution we can use search:
A is red A is green A is yellow
B is red B is green B is yellow
C is green C is yellow C is red
D is red D is yellow D is green
E is red E is green E is yellow

4. Default reasoning and TMS
 PS must make conclusions based on incomplete
information.
 “Closed-World Assumption” (CWA)
 X is true unless there is an evidence to the contrary.
 CWA helps us limit the underlying search space.
 The reasoning scheme that supports CWA is called “default
(or non-monotonic) reasoning”.
4. Default reasoning and TMS
 Example: Consider the following knowledge base
Bird(tom) and ¬Abnormal(tom)  Can_fly(tom)

Penguin(tom)  Abnormal(tom)
Ostrich(tom)  Abnormal(tom)
Bird(tom)
---------------------------------------------
Under the CWA, we assume
¬Abnormal(tom)
and therefore we can derive:
Can_fly(tom)
 Non-monotonic TMS supports this type of reasoning.
5. Identifying causes for failures and
recovering from inconsistencies
 Inconsistencies among beliefs in the KB are
always possible:
 wrong data (example: “Outside temperature is 320
degrees.”)
 Impossible constraints (example: Big-house and
Cheap-house and Nice-house).
 TMS maintains help identify the reason for an
inconsistency
 “dependency-directed backtracking” allows the
TMS to recover.
TMS applications
 Constraint Satisfaction Problems (CSP)
 Set of variables
 Domain over each variable
 Constraints between variables’ domain
 Goal: find “solution”: assignments to the variables
that satisfy the constraints
 Scenario and Planning Problems
 Find a path of state transitions lead from initial to
final states. (games, strategies).
 TMS – identifies of applicable rules.
Bayesian networks
 Bayesian networks have been the most
important contribution to the field of AI in
the last 10 years
 Provide a way to represent knowledge in
an uncertain domain and a way to
reason about this knowledge
 Many applications: medicine, factories,
help desks, spam filtering, etc.
16
Example
B P(B) E P(E) A Bayesian network is made
false 0.999 false 0.998 up of two parts:
true 0.001 true 0.002 1. A directed acyclic graph
2. A set of parameters
Burglary Earthquake
B E A P(A|B,E)
Alarm
false false false 0.999
false false true 0.001
false true false 0.71
false true true 0.29
true false false 0.06
true false true 0.94
true true false 0.05
true true true 0.95
A Directed Acyclic Graph
Burglary Earthquake
Alarm
1. A directed acyclic graph:

 The nodes are random variables (which can be discrete or
continuous)
 Arrows connect pairs of nodes (X is a parent of Y if there is
an arrow from node X to node Y).
18
A Directed Acyclic Graph
Burglary Earthquake
Alarm
 Intuitively, an arrow from node X to node Y means X has a direct

influence on Y (we can say X has a casual effect on Y)
 Easy for a domain expert to determine these relationships
 The absence/presence of arrows will be made more precise later
on
19
A Set of Parameters
B P(B) E P(E) Burglary Earthquake
false 0.999 false 0.998
true 0.001 true 0.002
Alarm
B E A P(A|B,E)
false false true 0.001 Each node Xi has a conditional
false true false 0.71 probability distribution P(Xi |
false true true 0.29 Parents(Xi)) that quantifies the
true false false 0.06 effect of the parents on the node
true false true 0.94 The parameters are the
true true false 0.05 probabilities in these conditional
true true true 0.95 probability distributions
Because we have discrete random
variables, we have conditional
probability tables (CPTs)
20
A Set of Parameters
Conditional Probability Stores the probability
Distribution for Alarm
distribution for Alarm
given the values of
B E A P(A|B,E)
Burglary and Earthquake
For a given combination of
false false true 0.001
values of the parents (B and
false true false 0.71
E in this example), the
false true true 0.29 entries for P(A=true|B,E) and
true false false 0.06 P(A=false|B,E) must add up
true false true 0.94 to 1 eg.
true true false 0.05 P(A=true|B=false,E=false) +
true true true 0.95 P(A=false|B=false,E=false)=
1
If you have a Boolean variable with k Boolean parents, how big
is the conditional probability table?
How many entries are independently specifiable?
Semantics of Bayesian Networks
Two ways to view Bayes nets:
1. A representation of a joint probability
distribution
2. An encoding of a collection of
conditional independence statements
22
Bayesian Network Example
Weather Cavity
Toothache Catch P(A|B,C) = P(A|C)

I(ToothAche,Catch|Cavity)
• Weather is independent of the other variables,

I(Weather,Cavity) or P(Weather) = P(Weather|Cavity) =
P(Weather|Catch) = P(Weather|Toothache)
• Toothache and Catch are conditionally independent given
Cavity
• I(Toothache,Catch|Cavity) meaning P(Toothache|Catch,Cavity)
= P(Toothache|Cavity)
23
Bayes’ rule and its use
P(A  B) = P(A|B) *P(B)
P(A  B) = P(B|A) *P(A)
Bays’ rule (theorem)

 P(B|A) = P(A | B) * P(B) / P(A)
 P(B|A) = P(A | B) * P(B) / P(A)

Bayes Theorem
hi – hypotheses (i=1,k);
e1,…,en - evidence
P(hi)
P(hi | e1,…,en)
P(e1,…,en| hi)
P(e ,...,eenn ||hhi )i ) P(h

P(e11, e 2 ,..., P(hi )i )
P(h i | ie|1e,1e, 2e,...,
P(h een n))==
2 ,..., kk , i,=i =
1,1,
kk

P(e
jj11
1 22 nn  P(h) )
,...,ee | |hh ) ) P(h
P(e , e ,..., jj j j
25
 If e1,…,en are independent hypotheses
then
P(e1 , e 2 ,..., e n | h j ) = P(e1 | h j )  P(e 2 | h j )  ...  P(e n | h j ), j = 1, k
Certainty factors
 two probabilistic functions to model the
degree of belief and the degree of disbelief
in a hypothesis
 function to measure the degree of belief -
MB
 function to measure the degree of disbelief -
MD
 MB[h,e] – how much the belief in h
increases based on evidence e
 MD[h,e] - how much the disbelief in h
increases based on evidence e
Certainty factor
CF[h, e] = MB[h, e]  MD[h, e]

Artificial Intelligence

Uploaded by

Copyright:

Available Formats

Artificial Intelligence

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Artificial Intelligence

Uploaded by

Copyright:

Available Formats

Non-monotonic Reasoning

 Non-monotonic reasoning Often available

 Enforcing logical relations among beliefs.

Base expression which can be true or false

 Beliefs are propositional variables

 The PS is expected to provide an explanation

Q: What do I need to take a TMS course?

 There are different types of TMSs that provide different ways of

 Color the nodes: red (1), green (2) yellow (3).

A is red A is green A is yellow

B is red B is green B is yellow

C is green C is yellow C is red

D is red D is yellow D is green

E is red E is green E is yellow

Bird(tom) and ¬Abnormal(tom)  Can_fly(tom)

1. A directed acyclic graph:

 Intuitively, an arrow from node X to node Y means X has a direct

Toothache Catch P(A|B,C) = P(A|C)

• Weather is independent of the other variables,

Bays’ rule (theorem)

 P(B|A) = P(A | B) * P(B) / P(A)

P(e ,...,eenn ||hhi )i ) P(h

CF[h, e] = MB[h, e]  MD[h, e]

You might also like