Transcript Methods of inference

METHODS OF INFERENCE
Hasan Zafari
METHODS OF INFERENCE
What is reasoning?
 Inferences with rules
 trees
 The inference tree
 Inference by Inheritance
 Inference with frames
 Reasoning with semantic networks
 Reasoning with logic

KR LANGUAGES AND NATURAL LANGUAGE
how is a knowledge representation language different
from natural language e.g. English, Spanish, German, …
 natural languages are expressive, but have evolved
to meet the needs of communication, rather than
representation
 the meaning of a sentence depends on the sentence
itself and on the context in which the sentence was
spoken e.g. “Look!”
 sharing of knowledge is done without explicit
representation of the knowledge itself and they are
ambiguous (e.g. small dogs and cats)
GOOD KNOWLEDGE REPRESENTATION LANGUAGES
combines the best of natural and formal
languages:




expressive
concise
unambiguous
independent of context


formal


what you say today will still be interpretable tomorrow
the knowledge can be represented in a format that is suitable for
computers
effective

there is an inference procedure which can act on it to make new
sentences
REASONING

process of constructing new sentences from old ones
proper reasoning ensures that the new sentences
represent facts that actually follow from the facts that
the old sentences represent
 this relationship is called entailment and can be
expressed as
KB |= alpha


knowledge base KB entails the sentence alpha
WHAT INFERENCE METHODS DO?

an inference procedure can do one of two things:


given a knowledge base KB, it can derive new sentences 
that are (supposedly) entailed by KB
KB |--  ==> KB |= 
given a knowledge base KB and another sentence alpha, it
can report whether or not alpha is entailed by KB
KB   ==> KB |= 
an inference procedure that generates only entailed
sentences is called sound or truth-preserving
 the record of operation of a sound inference
procedure is called a proof
 an inference procedure is complete if it can find a
proof for any sentence that is entailed

TREES: MAKING DECISIONS
 Trees
/ lattices are useful for classifying objects in
a hierarchical nature.
 Trees
 We
/ lattices are useful for making decisions.
refer to trees / lattices as structures.
 Decision
trees are useful for representing and
reasoning about knowledge.
7
DECISION TREE EXAMPLE
8
‫مثالی دیگر از درخت تصمیم گیری‬
‫‪ ‬سایت جالب ‪http://en.akinator.com/‬‬
‫‪9‬‬
AND-OR TREES AND GOALS
 1990s,
PROLOG was used for commercial
applications in business and industry.
 PROLOG uses backward chaining to divide
problems into smaller problems and then solves
them.
 AND-OR trees also use backward chaining.
 AND-OR-NOT lattices use logic gates to describe
problems.
10
11
12
INHERITANCE
Inheritance is one of the main
kind of reasoning done in
semantic nets
 The ISA (is a) relation is often
used to link a class and its
superclass.
 Some links (e.g. haspart) are
inherited along ISA paths
 The semantics of a semantic net
can be relatively informal or
very formal


Often defined at the
implementation level
Animal
isa
Bird
hasPart
isa
Robin
isa
Rusty
isa
Red
Wings
INFERENCE BY INHERITANCE


One of the main types of reasoning done in a
semantic net is the inheritance of values
(properties) along the subclass and instance
links.
Semantic networks differ in how they handle
the case of inheriting multiple different values.
All possible values are inherited, or
 Only the “lowest” value or values are inherited

14
15
MULTIPLE INHERITANCE

A node can have any number of superclasses that
contain it, enabling a node to inherit properties from
multiple parent nodes and their ancestors in the
network. It can cause conflicting inheritance.
Nixon Diamond
(two contradictory inferences from the same data)
subclass
pacifist
Person
non-pacifist
Republican
Quaker
instance
instance
Nixon
P ? !P
subclass
Q
R
N
CONFLICT RESOLUTION
 double
arrows signify deductive or strict
(i.e., non-defeasible) inferences
 single arrows signify defeasible inferences,
and strikethrough
 single arrows signify that the negation of
the pointed formula is defeasibly implied
 Penguins are birds (no exceptions); Birds
usually fly; and Penguins usually don't fly.

conflict
Penguin ⇒ Bird → flies
 Penguin → not-flies
According to the Specificity Principle an inference with a
more specific antecedent overrides a conflicting defeasible
inference with a less specific antecedent.

FRAMES
Frames – semantic net with properties
 A frame represents an entity as a set of slots
(attributes) and associated values
 A frame can represent a specific entry, or a general
concept
 Frames are implicitly associated with one another
because the value of a slot can be another frame

3 components of a frame
•frame name
•attributes (slots)
•values (fillers: list of values,
range, string, etc.)
Book Frame
Slot  Filler
•Title
 AI. A modern Approach
•Author  Russell & Norvig
•Year
 2003
FEATURES OF FRAME REPRESENTATION
More natural support of values than semantic nets
(each slots has constraints describing legal values that
a slot can take)
 Can be easily implemented using object-oriented
programming techniques
 Inheritance is easily controlled

INHERITANCE

Similar to Object-Oriented programming paradigm
Hotel Chair
Hotel Room
•what
 room
•where hotel
•contains
–hotel chair
–hotel phone
–hotel bed
•what  chair
•height 20-40cm
•legs
4
Hotel Phone
•what  phone
•billing  guest
Hotel Bed
•what
•size
•part
 bed
king
 mattress
Mattress
•price
 100$
‫استنتاج در فریم‬
‫‪ ‬فریم از اجزای به هم وابسته ای تشکیل می شود‬
‫‪ ‬بین اجزای فریم ارتباطات معناداری وجود دارد‬
‫‪ ‬دانستن برخی اجزای فریم به استنباط دیگر اجزا کمک می کند‬
‫‪ ‬مثال‪ FrameNet :‬برای درک متن‬
‫‪ ‬در مثال زیر دو جمله با ساختارها و افعال متفاوت بیان شده اند که به دلیل‬
‫تعلق به یک فریم مشابه می توان یکی بودن معنای آنها را نتیجه گرفت‬
‫‪21‬‬
INFERENCE WITH FRAMES
22
Reasoning with semantic networks
- Knowledge explicitly represented in a semantic network can be
used to infer additional facts which are NOT explicitly
represented
(1) Inferences may rely on rules of common sense
e.g., For all objects X, Y, and Z
cup-1
if X is on Y
is left of
and Y is left of Z
is on
then X is left of Z
in the example network
teapot-1
saucer-1
is left of
cup-1 is on saucer-1
and saucer-1 is left of teapot-1
it follows the above general rule, then:
cup-1 is left of teapot-1
Inferences based on transitivity
- Relationship is a is transitive
if X is a Y
and Y is a Z
then X is a Z
holds for all distinct objects X, Y and Z
drinking
vessel
is a
is a
cup-1
is a
cup
- Relationship part of is transitive
- Relationship supported by is transitive, allowing the inference
shown by the dotted line in the following semantic network fragment
table-1
supported by
supported by
cup-1
saucer-1
supported by
- However, the relationship is on (i.e., resting directly on) is not
transitive
cup-1 is on saucer-1 and saucer-1 is on table-1
but cup-1 is not on table-1
- Relationships among people brother of is transitive but not father of
Inference based on inheritance
- A node inherits information from its related more general node
- Add a general object node, other nodes inherit its properties
- Eases the task of coding knowledge
- Automatically infer information about related objects in hierarchy
Example: attribute purpose is inherited
a cup is a drinking vessel
purpose of a drinking vessel is drinking
drinking
ves sel
it follows by inheritance that:
purpose of a cup is drinking
is a
cup
purpose
purpose
drinking
Inferences based on transitivity
and inheritance
drinking
vessel
purpose
drinking
is a
cup
purpose
is a
cup-1
Two steps involved in the inference shown by
the dotted line:
Step 1. inference based on transitivity
Step 2. inference based on inheritance
Dealing with exceptions
- Inheritance is a default mechanism and exceptions do occur
Wings
Air
HAS
Tweety
Canary
IS-A
IS-A
Bird
BREATHE
IS-A
Animal
TRAVEL
IS-A
Fly
Penguin
From the above semantic network, it can be inferred that:
Canary is a animal, Tweety is a bird, Tweety is a animal,
Penguin is a bird, Penguin is a animal, Penguin travel fly
…...
- If an attribute’s value is explicitly represented in a semantic net,
it takes priority over the value that would otherwise by inherited
Step 1. Account for exceptions on local basis
Step 2. Link new node with information that over-ride the incorrectly
inherited information
Wings
Air
HAS
Tweety
IS-A
Canary
IS-A
IS-A
Penguin
TRAVEL
Walk
Bird
BREATHE
IS-A
TRAVEL
Fly
Animal
SEMANTIC NET OPERATION
User
How do you travel?
Bird
Fly
TRAVEL
Fly
How do you travel?
How do you travel? How do you travel?
Tweety
User
Fly
Bird
Canary
Fly
Fly
TRAVEL
Fly
ADVANTAGES & DISADVANTAGES
Advantages
Explicit and succinct
Reduced search time
Inheritance
Has correspondence with human memory
Disadvantages
No interpretation standards
Invalid inferences
Combinatorial explosion: if a relation is false many or all of
the relations in the network must be examined.
Rules of Inference
Expert Systems: Principles and Programming, Fourth Edition
32
REASONING WITH LOGIC
Truth Table Modus Ponens
Expert Systems: Principles and Programming, Fourth Edition
34
Types of Logic
• Deduction – reasoning where conclusions must
follow from premises
• Induction – inference is from the specific case to
the general
• Analogy – inferring conclusions based on
similarities with other situations
• Abduction – reasoning back from a true
condition to the premises that may have caused
the condition
Expert Systems: Principles and Programming, Fourth Edition
35
Deductive Logic
• Argument – group of statements where the last is
justified on the basis of the previous ones
• Deductive logic can determine the validity of an
argument.
• Syllogism – has two premises and one conclusion
• Deductive argument – conclusions reached by
following true premises must themselves be true
Expert Systems: Principles and Programming, Fourth Edition
36
Syllogisms vs. Rules
• Syllogism:
– All basketball players are tall.
– Jason is a basketball player.
–  Jason is tall.
• IF-THEN rule:
IF
All basketball players are tall and
Jason is a basketball player
THEN Jason is tall.
Expert Systems: Principles and Programming, Fourth Edition
37
Figure 3.21 Causal Forward Chaining
Expert Systems: Principles and Programming, Fourth Edition
38
Comparing abduction, deduction,
and induction
A => B
A
--------B
Deduction: major premise:
minor premise:
conclusion:
All balls in the box are black
These balls are from the box
These balls are black
Abduction: rule:
observation:
explanation:
All balls in the box are black A => B
B
These balls are black
These balls are from the box ------------Possibly
A
Induction: case:
These balls are from the box
Whenever
observation:
These balls are black
A then B
------------hypothesized rule: All ball in the box are black
Possibly
A => B
Deduction reasons from causes to effects
Abduction reasons from effects to causes
Induction reasons from specific cases to general rules
40