Transcript Data Modeling

First Order Predicate Logic
CPSC 386 Artificial Intelligence
Ellen Walker
Hiram College
First Order Logic (ch. 8)
• Has a greater expressive power than
propositional logic
– We no longer need a separate rule for each
square to say which other squares are breezy/pits
• Allows for facts, objects, and relations
– In programming terms, allows classes, functions
and variables
Components of First Order Logic
• Term
– Constant, e.g. Red
– Function of constant, e.g. Color(Block1)
• Atomic Sentence
– Predicate relating objects (no variable)
• Brother (John, Richard)
• Married (Mother(John), Father(John))
• Complex Sentences
– Atomic sentences + logical connectives
• Brother (John, Richard) Brother (John, Father(John))
More Components…
• Quantifiers
– Each quantifier defines a variable for the duration
of the following expression, and indicates the truth
of the expression…
• Universal quantifier “for all” 
– The expression is true for every possible value of
the variable
• Existential quantifer “there exists” 
– The expression is true for at least one value of the
variable
Quantification examples
• Everyone like chocolate
– x, likes(x, chocolate)
• Someone likes chocolate
– x, likes(x, chocolate)
• All children like chocolate
– x, child(x)  likes(x, chocolate)
• Everyone likes chocolate unless they are allergic to it
– x, likes(x, chocolate)  allergic(x, chocolate)
– x, allergic (x, chocolate)  likes(x, chocolate)
Quantification and Negation
• Not everyone like chocolate
(x, likes(x, chocolate))
x, likes(x, chocolate)
• No one likes chocolate
(x, likes(x, chocolate))
x, likes(x, chocolate)
Nesting Variables
• Everyone likes some kind of food
y x, food(x)  likes(y, x)
• There is a kind of food that everyone likes
x y, food(x)  likes(y, x)
• Someone likes all kinds of food
y x, food(x)  likes(y, x)
• Every food has someone who likes it
x y, food(x)  likes(y, x)
Quantification with Classes
• To say “everyone likes chocolate”, the following is too
broad!
– x, likes(x, chocolate)
– Example: likes (chocolate, chocolate)
• We mean: Every one (who is a person) likes
chocolate
– x, person(x)  likes(x, chocolate)
• Essentially, the left side of the rule declares the class
of the variable x
• Constraints like this are often called “domain
constraints”
Equality
• We allow the usual infix = operator
– Father(John) = Henry
– x, sibling(x, y)  (x=y)
• Generally, we also allow mathematical
operations when needed, e.g.
– x,y, NatNum(x)  NatNum(y) x = (y+1)  x > y
Try some!
•
•
•
•
•
Every successful person has a mentor.
Every successful person is a mentor.
Every mentor is a successful person.
No person is successful without a mentor.
There are no successful people who are
mentors.
Using FOL to Model the World
• Tell the system assertions
– Facts :
• Tell (KB, person (John) )
– Rules:
• Tell (KB,x, person(x)  likes(x, chocolate))
• Ask questions
– Ask (KB, person(John))
– Ask (KB, likes(John, chocolate))
– Ask (KB, likes(x, chocolate))
Types of Answers
• Fact is in the KB
– Yes.
• Fact is not in the KB
– Yes (if it can be proven from the KB)
– No (otherwise)
• Fact contains variables
– List of bindings for which the fact can be proven,
e.g. ((x John) (x Ellen) … )
Example Domains (pp. 254-260)
• Kinship domain
– What is a second cousin once removed, anyway?
• Numbers, sets, and lists
– This one is a classic. You should understand these, even if
you don’t memorize them.
• The Wumpus World
– Note how much simpler the description is in FOL!
• “Whatever your domain, if the axioms correctly and
completely describe how the world works, any
complete logical inference procedure will infer the
strongest possible description of the world, given the
available percepts” (AIMA, p. 260)
Knowledge Engineering
•
Translating real-world knowledge to a
usable form
1. Identify the task (PEAS description)
2. Assemble the relevant knowledge (knowledge
acquisition)
3. Decide on the vocabulary: predicates, functions,
constants (ontology)
4. Encode general knowledge
5. Encode a specific problem instance
6. Query and debug …
Types of Rules
• Diagnostic Rules lead from observed effects
to hidden causes (like medical diagnosis)
• Causal Rules lead from (hidden) causes to
observed effects (like simulation systems)
• Systems should reason either one way or the
other, but not mix rules of both types (to avoid
circular reasoning!)
Necessary algorithms (Ch. 9)
• We already know enough to implement TELL
(although maybe not efficiently)
• But how do we implement ASK?
• Recall 3 cases
– Direct matching
– Finding a proof (inference)
– Finding a set of bindings (unification)
Inference with Quantifiers
• Universal Instantiation:
– Given x, person(x)  likes(x, chocolate)
– Infer person(john)  likes(john, chocolate)
• Existential Instantiation:
– Given x, likes(x, chocolate)
– Infer  likes(S1, chocolate)
– S1 is a “Skolem Constant” that is not found
anywhere else in the KB and refers to (one of) the
indviduals that likes chocolate.
Reduction to Propositional Inference
• Use instantiation rules to create relevant (!)
propositional facts in the KB, then use
propositional reasoning
• Problems:
– May generate infinite sentences when it cannot
prove
– Will generate many irrelevant sentences along the
way!
Generalized Modus Ponens
• This is a general inference rule for FOL that
does not require instantiation
• Given:
– p1’, p2’ … pn’ (p1  … pn)  q
– Subst(theta, pi’) = subst(theta, pi) for all i
• Conclude:
– Subst(theta, q)
Simple Example of GMP
• Rule: king(x)  rich(x)
– p1 = king(x), q = rich(x)
• Fact: king(John)
– p1’ = king(John)
• Theta is x = John
– Subst(x=John, king(x)) = king(John)
– Subst(x=John, rich(x)) = rich(John)
• We can conclude rich(John).
GMP in “CS terms”
• Given a rule containing variables
• If there is a consistent set of bindings for all of
the variables of the left side of the rule
(before the arrow)
• Then you can derive the result of substituting
all of the same variable bindings into the right
side of the rule
GMP Example
• x, parent(x,y)  parent(y,z) 
grandparent(x,z)
• Parent(james, john), parent(james, richard),
parent(harry, james), parent(charles,hal)
• We can derive:
– Grandparent(harry, john), bindings:
((x harry) (y james) (z john))
– Grandparent(harry, richard), bindings:
((x harry) (y james) (z richard))
Unification
• Process of finding all legal substitutions
• Given 2 expressions
• Find a set of unifiers (variable bindings) that
causes the expressions to “match”
• This is a beautifully recursive algorithm.
Base Cases for Unification
• If two expressions are identical, the result is
(NIL) (succeed with empty unifier set)
• If two expressions are different constants, the
result is NIL (fail)
• If one expression is a variable and is not
contained in the other, the result is
((variable other-exp))
Recursive Case
• If both expressions are lists,
– Combine the results of unifying the CAR with
unifying the CDR
– (append (unify (car list1) (car list2))
(unify (cdr list1) (cdr list2))
A few more details…
• Don’t reuse variable names
– Before actually unifying, give each rule a separate
set of variables.
– The lisp function gentemp creates uniquely
numbered variables
• Keep track of bindings
– If a variable is already bound to something, it must
retain the same value throughout the computation.
– This requires substituting each successful binding
in the remainder of the expression.
Storage and retrieval
• Most systems don’t use variables on
predicates
• Therefore, hash statements by predicate for
quick retrieval (predicate indexing)
• Subsumption lattice for efficiency (see p. 279)
Forward Chaining
• Given a new fact, generate all consequences
• Assumes all rules are of the form
– C1 and c2 and c3 and…. --> result
• Each rule & binding generates a new fact
• This new fact will “trigger” other rules
• Keep going until the desired fact is generated
• (Semi-decidable as is FOL in general)
Efficient Forward Chaining
• Order conjuncts appropriately
– E.g. most constrained variable
• Don’t generate redundant facts; each new
fact should depend on at least one newly
generated fact.
– Production systems
– RETE matching
– CLIPS
Backward Chaining
• Consider the item to be proven a goal
• Find a rule whose head is the goal (and
bindings)
• Apply bindings to the body, and prove these
(subgoals) in turn
• If you prove all the subgoals, increasing the
binding set as you go, you will prove the item.
• Logic Programming (SWI Prolog)