Transcript Knowledge Representation

Knowledge
Representation
1
Definitions

Knowledge Base



Knowledge Representation


A set of representations of facts about
the world.
Each representation is a sentence.
Expressing knowledge in a form that
can be manipulated by a computer.
Inference Mechanism

Generates new sentences that are
necessarily true given that the old
sentences are true.
2

Two aspects of the Knowledge
Representation language:
1. Formal system of defining the world

Syntax


What constitutes a sentence
Semantics

Meaning. Connects sentences to facts.
KB entails a (KB |= a) means when all
sentences in KB are true, a is true.
(|= means entailment)
2. A proof theory

Rules for determining all entailments.
(KB |-- a)
3
KR Languages

Logic




Propositional Logic
First Order Logic
Production rules
Structured Objects



Semantic Nets
Frames
Script
4
Logic

Logic is reasoning technique.
It is the study of rules of
inference and the principles
of sound argument.
Much of the basis of Expert
systems reasoning comes from
logic
5
Reasoning(inferencing)
Strategies

Deduction

Induction

Abduction
6
Deduction

This process takes general
principles and applies the
specific instances to infer a
conclusion


All dogs have hair
Lassie is a dog

We can deduce that Lassie has hair.
7
Deduction (cont…)




Deduction uses major and minor
premises
A major premise can have many
minor premises
All minor premises must be true
for a deduction to be made.
This is a limitation of deduction
8
Induction

This process uses a number of
established facts or premises to draw
some general conclusion.



1994 Cat show all Siamese cats had blue
eyes.
1995 Cat show all Siamese cats had blue
eyes.
1996 Cat show all Siamese cats had blue
eyes.

Conclusion all Siamese cats have blue eyes
9
Induction (cont…)

Induction conclusions may not be
entirely accurate


only Siamese cats in Australia have
blue eyes
Inferred conclusions may change
as more facts are known
10
Abduction
A
form of deductive inference
which uses probability to
determine most probable
conclusion.
11
Abduction Example






Major Premise
I do not jog when the
temperature exceeds 38 degrees
Minor Premise
I did not jog today
Conclusion
The temperature today is greater
than 40 degrees
12
Propositional Logic: Syntax

A BNF (Backus-Naur Form) grammar of
sentences in propositional logic.
Sentence  Atomic Sentence  Complex Sentence
Atomic Sentence  True  False
PQR…
Complex Sentence  (Sentence)
Sentence Connective Sentence
 Sentence
Connective        
13
Propositional Logic:
Semantics

Truth tables for the five logical
connectives.
P
Q
P
PQ
PQ
PQ
False False
True False False
True
True
False
True
True False
True
True
False
True
False False False
True
False
False
True
True
True
True
True
False
PQ
True
14
Propositional Logic: Rules
of Inference

Modus Ponens/ImplicationElimination:


  ,


And-Elimination:


From an implication and the premise of the
implication, you can infer the conclusion
From a conjunction you can infer any of
the conjuncts.
1  2  ...  n
i
And-Introduction:

From a list you can infer their conjunction.
1, 2 , ... , n
1  2  ...  n
15

Or-Introduction:


Double-Negation Elimination:


From a doubly negated sentence, you can
infer a positive sentence


Unit Resolution:


From a sentence, you can infer its
disjunction with anything else at all.
i
1  2  ...  n
From a disjunction, if one of the disjuncts
is false, then you can infer the other one is
true.
  ,  

Resolution:
This is the most difficult. Because  cannot
be both true and false, one of the other
disjuncts must be true in one of the
premises. Or equivalently, implication is
transitive.
  ,    
   ,   

 
  

16
Propositional Logic:
Inference

Resolution refutation theorem
prover


Inference mechanism for
propositional logic
Refutation:

Recall that S |=  is defined as:


Whenever all sentences in S are true,
than  is true as well.
This is equivalent to saying that:
It impossible for S to be true and  to
be false.
Or
 It is impossible for S and  to be true
at the same time.


In a refutation theorem prover, in
order to prove  from S, add 
to S and try to derive a
17
contradiction.

Algorithm to prove S |= :
1.
Rewrite S in clausal form.
2.
Rewrite  in clausal
form.
3.
Using the various
inference rules, derive the empty
clause from the results of 1. and
2.
18
Clausal Form or CNF

Conjunctive Normal Form (CNF).


Representing a sentence as a
conjunction of disjunctions.
To do this:
1. Eliminate Implications
 Remember a  b 
a  b
2. Push negation inwards
 (a  b)  a   b
 (a  b)  a   b
(De Morgan’s Laws)
3. Eliminate double negations
4. Push disjunctions into conjunctions
 a  (b  c)  (a  b)  (a  c)
19

Example: Converting to
CNF
Converting the following
sentence to CNF:
(a   b)  (c  d)

Steps:
1. Remove Implication
(a   b)  (c  d)
2. Push Negations Inwards
a    b  (c  d)
3. Eliminate Double Negations
a  b  (c  d)
4. Push Disjunctions into
Conjunctions
(a  b  c)  (a  b  d)

CNF
Represented in KB as the 2
clauses:
{a  b  c} and {a  b  d}
20
Example: Resolution

Prove that
r follows from:
(p  q)  (r  s) - (1)
ps
- (2)
p q
- (3)

Solution:
1. Clause (1) in CNF
 (p  q)  (r  s)
 { p   q  r  s} - (1)
Clause (2)
{ p   s} - (2)
Clause (3)
{p} - (3)
{q} - (4)
21
Example (con’t)
2. Clause of r is { r}
- (5)
3. Using inference rules:
{p   q  s}
- (6)
from unit resolution rule of (1) and
(5)
{ q  s}
- (7)
from unit resolution of (3) and (6)
{s}
from (4) and (7)
{ p}
from (2) and (8)

- (8)
- (9)
{}
- (10)
from (3) and (9)
Therefore r follows from the original
clauses
22