Transcript Document

L3. Knowledge Representation and
Matching in Java
Matching.java
Unify.java
What to Represent

Facts about the world

Definitions and general rules

An agent’s beliefs and those of other agents

Plans of action

Degrees of certainty and uncertainty
How to represent

Logical representation schemes

Procedural representation schemes

Network representation schemes

Structured representation schemes
different inference
mechanisms
Representing Simple Facts

Objects: potato, mike. Cooker, …

Predicates: male, father, at, …

Properties: male(mike), female(rose), rich(john), …

Relations: father(mike, rose), in(john, restaurant, now), …
Knowledge Base: Facts
parent(jock, morag)
parent(jock, alasdair)
parent(jock, hamish) parent(mairi, morag)
parent(mairi, alasdair) parent(mairi, hamish)
parent(fergus, jock)
parent(rhoda, jock)
parent(fergus, flora)
parent(rhoda, flora)
male(fergus)
male(jock)
male(alasdair)
male(hamish)
female(rhoda)
female(mairi)
female(morag)
female(flora)
The Need for Rules

Some facts can be inferred from others,
e.g. fergus is morag’s grandfather

Need generality
variables stand for arbitrary objects, e.g. X

Define some relations in terms of others
e.g. mother is female parent
Representing Simple Rules
Variables: x, P, C, ...
Generalised Facts: female(P), parent(P, C), ...
Conjunctions: parent(P, C)  female(P)
Rules: parent(P, C)  female(P)  mother(P, C)
Knowledge Bases: Rules
Family Relations
parent(P, C)  female(P)  mother(P, C)
parent(P, C)  male(P)  father(P, C)
parent(GP, P)  parent(P, C)  grandparent(GP, C)
parent(GP, P)  female(GP)  parent(P, C)
grandmother(GP, C)
grandparent(GP, C)  male(GP)  grandfather(GP, C)
Knowledge Base Architecture
Updates
KNOWLEDGE
BASE (KB)
facts and rules
Query
INFERENCE
MECHANISM
Note: compare with problem solving as search
Answer
Representing Language
• Formal language to represent facts and rules about a
microworld as sentences.
• Interpreted sentences represent a model of the microworld
• Syntax: how sentences formed
mother_of(sarah,tal)  mother_of(sarah,mor)
• Semantics: how to interpret sentences
True/False
• Set of all sentences (axioms, rules) is the abstract
representation of the KB
• Base sentences are called axioms, derived sentences
theorems, derivations proofs
Reasoning with Logic
• Mathematical logics have well-defined syntax,
semantics, and models:
–
–
–
–
Propositional: facts are True/False
First Order: facts, objects, relations are True/False
Temporal logic: First Order + time
Probability theory: facts, degree of belief [0…1]
• Interpretation: truth assignment to each
element on the formula
A is True
Sentence in propositional logic
• Sentence  AtomicSentence | ComplexSentence
• AtomicSentence  proposition symbols like P, Q, R
True | False
• ComplexSentence  (Sentence)
| Setence Connective Sentence
like P  Q  (P  Q)  ( P   Q)
True | False
• Connectives:  (not),  (and),  (or),  (implies), and  (equivalent)
Sentences in first-order logic
• Atomic sentences = predicate(term1, term2, …termn)
or term1 = term2
Term = function(term1, term2, …termn)
or constant or variable
• Complex sentences: made from atomic sentences using connectives.
 (not),  (and),  (or),  (implies), and  (equivalent)
Syntax of FOL: basic element
• Constant symbols:
refer to the same object in the same interpretation
e.g. Mike Jason, 4, A, B, …
• Predicate symbols: refer to a particular relation in the model.
e.g., Brother, >,
• Function symbols: refer to particular objects without using their names.
Some relations are functional, that is, any given object is related to
exactly one other object by the relation. (one-one relation)
e.g., Cosine, FatherOf,
• Variables: substitute the name of an objec.
e.g., x, y, a, b,… x, Cat(x)  Mammal(x)
if x is a cat then x is a mammal.
• Logic connectives:
 (not),  (and),  (or),  (implies), and  (equivalent)
• Quantifiers:  (universal quantification symbol),  (existential quantification symbol)
x, for any x, …
• Equality: =
e.g. Father(John) = Henry
x, there is a x, …
Seven inference rules for propositional Logic
• (1) Modus Ponens   , 

• (2) And-Elimination
1  2 … n
• (3) And-Introduction
1, 2, …, n
1  2 … n
• (4) Or-Introduction
i
1  2  …  n
i
• (5) Double-Negation Elimination
• (6) Unit Resolution
• (7) Logic connectives:
  ,  

  ,    



The three new inference rules
• (8) Universal Elimination: For any sentence , variable v, and ground term g:
v 
SUBST({v/g}, )
Ground term is a
term that contains
no variables.
e. g.,  x Likes(x, IceCream), we can use the substitute {x/Rose} and
infer Like(Rose, IceCream).
• (9) Existential Elimination: For any sentence , variable v, and constant symbol
k that does not appear elsewhere in the knowledge base:
v 
SUBST({v/k}, )
e. g.,  x Kill(x, Victim), we can infer Kill(Murderer, Victim), as long as Murderer
does not appear elsewhere in the knowledge base.
• (10) Existential Introduction: For any sentence , variable v that does not occur
in , and ground term g that does occur in :
e. g., from Likes(Rose, IceCream)
we can infer  x Likes(x, IceCream).

 v SUBST({g/v}, )
Example of proof
Bob is a buffalo
| 1. Buffalo(Bob)
Pat is a pig
| 2. Pig(Pat)
Buffaloes outrun pigs
| 3.  x, y Buffalo(x)  Pig(y)  Faster(x,y)
---------------------------------------------------------------------------------------------------Bob outruns Pat
--------------------------------------------------------------------------------------------------Apply (3) to 1 And 2
| 4. Buffalo(Bob)  Pig(Pat)
Apply (8) to 3 {x/Bob, y/Pat} | 5. Buffalo(Bob)  Pig(Pat)  Faster(Bob,Pat)
Apply (1) to 4 And 5
| 6. Faster(Bob,Pat)
Unification and Matching
The process of matching is called unification: for example,
- p(x) matches p(Jack) with x = Jack
- q(fatherof(x),y) matches q(y,z) with y=fatherof(x) and z = y
• note the result of the match is q(fatherof(x),fatherof(x))
- p(x) matches p(y) with
• x = Jack and y = Jack
• x = John and y = John or
•x=y
- The match that makes the least commitment is called the most general unifier
(MGU)
Unify
Unification function, Unify, is to take two atomic sentences p and q and return a
substitution that would make p and q look the same.
A substitute  unifies atomic sentences p and q if p  =q 
For example,
p

q
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Knows(John, x)
Knows(John, x)
Knows(John, x)
| Knows(John, Jane)
| Knows(y, OJ)
| Knows(y, Mother(y))
| {x/Jane}
| {y/John, x/OJ}
| {y/John, x/Mother(John)}
Premise 前提
e.g., Unify(Knows(John, x), Knows(John, Jane)) = {x/Jane}
Idea: Unify rule premises with known facts, apply unifier to conclusion.
e.g., if we know q and Knows(John, x) Likes(John, x)
then we can conclude Likes(John, Jane)
Likes(John, OJ)
Likes(John, Mother(John))
(unify ‘(?x ?y a) ‘(?y ?x ?x))
((?y . A) (?X . ?Y))
(unify ‘(?x) ‘(f ?x))
NIL
(unify ‘a ‘a)
((T . T))
Unify
String matching: string1 = string2
e.g. “rose” = “rose”
if string1.equals(string2)
“I am Rose” = “I am Rose”
40: // 同じなら成功
“I am ?x” = “I am Rose”
41: if(string1.equals(string2)) return true;
?
“I am ?x” = “?y am Rose”
I = ?y
am = am
Check? String  Tokens
?x = Rose
51: int length = st1.countTokens(); // 定数同士
44: st1 = new StringTokenizer(string1);
52: for (int i = 0 ; i < length; i++){
45: st2 = new StringTokenizer(string2);
53:
if (!tokenMatching(st1.nextToken(),st2.nextToken())){
46:
54:
// トークンが一つでもマッチングに失敗したら失敗
47: // 数が異なったら失敗
55:
48: if (st1.countTokens() != st2.countTokens())
56:
49: return false;
57: }
return false;
}
Token matching: token1 = token2
Three pairs of tokens’ matching:
e.g. two strings’ matching, “I am ?x” = “?y am Rose”
I = ?y
am = am
?x = Rose
64: boolean tokenMatching(String token1,String token2){
73: boolean varMatching(String vartoken,String token){
65: if(token1.equals(token2)) return true;
74: if(vars.containsKey(vartoken)){
66: if( var(token1) && !var(token2))
75: if(token.equals(vars.get(vartoken))){
67:
76: return true;
return varMatching(token1,token2);
68: if(!var(token1) && var(token2))
77: } else {
69:
78: return false;
return varMatching(token2,token1);
70: return false;
79: }
71: }
80: } else {
81: vars.put(vartoken,token);
86: boolean var(String str1){
82: }
87: // 先頭が ? なら変数
83: return true;
27: Matcher(){
88: return str1.startsWith("?");
84: }
28: vars = new Hashtable();
89: }
29: }
Output: matching vs. unify
Output from Matching.java
?x is ?y and ?x
Rose is rose and ?y
false
Output from Unify.java
?x is ?y and ?x
Rose is rose and ?y
{?y=rose, ?x=Rose}
true