CS 561a: Introduction to Artificial Intelligence

CS 561a: Introduction to Artificial Intelligence

Inference in First-Order Logic Proofs Unification Generalized modus ponens Forward and backward chaining Completeness Resolution Logic programming CS 561, Session 16-18 1 Inference in First-Order Logic Proofs extend propositional logic inference to deal with quantifiers

Unification Generalized modus ponens Forward and backward chaining inference rules and reasoning program Completeness Gdels theorem: for FOL, any sentence entailed by another set of sentences can be proved from that set Resolution inference procedure that is complete for any set of sentences Logic programming CS 561, Session 16-18 2 Logic as a representation of the World

entails Representation: Sentences Sentence Refers to (Semantics) World Facts follows CS 561, Session 16-18

Fact 3 Desirable Properties of Inference Procedures derivation Sentences Facts entail Follows from-1

CS 561, Session 16-18 Sentence Fact 4 Remember: propositional logic CS 561, Session 16-18 5

Reminder Ground term: A term that does not contain a variable. A constant symbol A function applies to some ground term {x/a}: substitution/binding list CS 561, Session 16-18 6 Proofs CS 561, Session 16-18

7 Proofs The three new inference rules for FOL (compared to propositional logic) are: Universal Elimination (UE): for any sentence , variable x and ground term , x {x/} Existential Elimination (EE): for any sentence , variable x and constant symbol k not in KB, x {x/k} Existential Introduction (EI): for any sentence , variable x not in and ground term g in ,

x {g/x} CS 561, Session 16-18 8 Proofs The three new inference rules for FOL (compared to propositional logic) are: Universal Elimination (UE): for any sentence , variable x and ground term , x e.g., from x Likes(x, Candy) and {x/Joe} {x/} we can infer Likes(Joe, Candy) Existential Elimination (EE): for any sentence , variable x and constant symbol k not in KB,

x e.g., from x Kill(x, Victim) we can infer {x/k} Kill(Murderer, Victim), if Murderer new symbol Existential Introduction (EI): for any sentence , variable x not in and ground term g in , e.g., from Likes(Joe, Candy) we can infer x {g/x} x Likes(x, Candy) CS 561, Session 16-18 9 Example Proof CS 561, Session 16-18

10 Example Proof CS 561, Session 16-18 11 Example Proof CS 561, Session 16-18 12 Example Proof

4&5 CS 561, Session 16-18 13 Search with primitive example rules CS 561, Session 16-18 14 Unification Goal of unification: finding

CS 561, Session 16-18 15 Unification CS 561, Session 16-18 16 Extra example for unification P Q

Student(x) Student(Bob) {x/Bob} Sells(Bob, x) Sells(x, coke) {x/coke, x/Bob} Is it correct?

CS 561, Session 16-18 17 Extra example for unification P Q Student(x) Student(Bob)

{x/Bob} Sells(Bob, x) Sells(y, coke) {x/coke, y/Bob} CS 561, Session 16-18 18 More Unification Examples VARIABLE

1 unify(P(a,X), P(a,b)) 2 unify(P(a,X), P(Y,b)) 3 unify(P(a,X), P(Y,f(a)) 4 unify(P(a,X), P(X,b)) term = {X/b} = {Y/a, X/b} = {Y/a, X/f(a)} = failure Note: If P(a,X) and P(X,b) are independent, then we can replace X with Y and get the unification to work.

CS 561, Session 16-18 19 Generalized Modus Ponens (GMP) CS 561, Session 16-18 20 Soundness of GMP CS 561, Session 16-18 21

Properties of GMP Why is GMP and efficient inference rule? - It takes bigger steps, combining several small inferences into one - It takes sensible steps: uses eliminations that are guaranteed to help (rather than random UEs) - It uses a precompilation step which converts the KB to canonical form (Horn sentences) Remember: sentence in Horn from is a conjunction of Horn clauses (clauses with at most one positive literal), e.g., (A B) (B C D), that is (B ), that is (B A) ((C D), that is (B ) B) CS 561, Session 16-18 22

Horn form We convert sentences to Horn form as they are entered into the KB Using Existential Elimination and And Elimination e.g., x Owns(Nono, x) Missile(x) becomes Owns(Nono, M) Missile(M) (with M a new symbol that was not already in the KB) CS 561, Session 16-18 23

Forward chaining CS 561, Session 16-18 24 Forward chaining example CS 561, Session 16-18 25 Backward chaining CS 561, Session 16-18

26 Backward chaining example CS 561, Session 16-18 27 Another Example (from Konelsky) Nintendo example. Nintendo says it is Criminal for a programmer to provide emulators to people. My friends dont have a Nintendo 64, but they use software that runs N64 games on their PC, which is written by Reality Man, who is a

programmer. CS 561, Session 16-18 28 Forward Chaining The knowledge base initially contains: Programmer(x) Emulator(y) People(z) Provide(x,z,y) Criminal(x) Use(friends, x) Runs(x, N64 games) Provide(Reality Man, friends, x) Software(x) Runs(x, N64 games) Emulator(x) CS 561, Session 16-18

29 Forward Chaining Programmer(x) Emulator(y) People(z) Provide(x,z,y) Criminal(x) (1) Use(friends, x) Runs(x, N64 games) Provide(Reality Man, friends, x) (2) Software(x) Runs(x, N64 games) Emulator(x)

(3) Now we add atomic sentences to the KB sequentially, and call on the forward-chaining procedure: FORWARD), that is (B -CHAIN(KB, Programmer(Reality Man)) CS 561, Session 16-18 30 Forward Chaining Programmer(x) Emulator(y) People(z) Provide(x,z,y) Criminal(x) (1) Use(friends, x) Runs(x, N64 games) Provide(Reality Man, friends, x) (2) Software(x) Runs(x, N64 games)

Emulator(x) (3) Programmer(Reality Man) (4) This new premise unifies with (1) with subst({x/Reality Man}, Programmer(x)) but not all the premises of (1) are yet known, so nothing further happens. CS 561, Session 16-18 31 Forward Chaining Programmer(x) Emulator(y) People(z) Provide(x,z,y) Criminal(x)

Use(friends, x) Runs(x, N64 games) Provide(Reality Man, friends, x) Software(x) Runs(x, N64 games) Emulator(x) Programmer(Reality Man) (1) (2) (3) (4) Continue adding atomic sentences: FORWARD), that is (B -CHAIN(KB, People(friends)) CS 561, Session 16-18

32 Forward Chaining Programmer(x) Emulator(y) People(z) Provide(x,z,y) Criminal(x) (1) Use(friends, x) Runs(x, N64 games) Provide(Reality Man, friends, x) (2) Software(x) Runs(x, N64 games) Emulator(x) (3) Programmer(Reality Man) (4) People(friends) (5) This also unifies with (1) with subst({z/friends},

People(z)) but other premises are still missing. CS 561, Session 16-18 33 Forward Chaining Programmer(x) Emulator(y) People(z) Provide(x,z,y) Criminal(x) Use(friends, x) Runs(x, N64 games) Provide(Reality Man, friends, x) Software(x) Runs(x, N64 games) Emulator(x) Programmer(Reality Man)

(4) People(friends) (1) (2) (3) (5) Add: FORWARD), that is (B -CHAIN(KB, Software(U64)) CS 561, Session 16-18 34 Forward Chaining Programmer(x) Emulator(y) People(z) Provide(x,z,y)

Criminal(x) (1) Use(friends, x) Runs(x, N64 games) Provide(Reality Man, friends, x) (2) Software(x) Runs(x, N64 games) Emulator(x) (3) Programmer(Reality Man) (4) People(friends) (5) Software(U64) (6) This new premise unifies with (3) but the other premise is not yet known. CS 561, Session 16-18

35 Forward Chaining Programmer(x) Emulator(y) People(z) Provide(x,z,y) Criminal(x) (1) Use(friends, x) Runs(x, N64 games) Provide(Reality Man, friends, x) (2) Software(x) Runs(x, N64 games) Emulator(x) (3) Programmer(Reality Man) (4) People(friends) (5)

Software(U64) (6) Add: FORWARD), that is (B -CHAIN(KB, Use(friends, U64)) CS 561, Session 16-18 36 Forward Chaining Programmer(x) Emulator(y) People(z) Provide(x,z,y) Criminal(x) (1) Use(friends, x) Runs(x, N64 games) Provide(Reality Man, friends, x) (2) Software(x) Runs(x, N64 games) Emulator(x) (3) Programmer(Reality Man)

People(friends) Software(U64) Use(friends, U64) (4) (5) (6) (7) This premise unifies with (2) but one still lacks. CS 561, Session 16-18 37 Forward Chaining

Programmer(x) Emulator(y) People(z) Provide(x,z,y) Criminal(x) Use(friends, x) Runs(x, N64 games) Provide(Reality Man, friends, x) Software(x) Runs(x, N64 games) Emulator(x) (3) (1) (2) Programmer(Reality Man) (4) People(friends) (5) Software(U64) (6) Use(friends, U64) (7) Add: FORWARD), that is (B -CHAIN(Runs(U64, N64 games))

CS 561, Session 16-18 38 Forward Chaining Programmer(x) Emulator(y) People(z) Provide(x,z,y) Criminal(x) (1) Use(friends, x) Runs(x, N64 games) Provide(Reality Man, friends, x) (2) Software(x) Runs(x, N64 games) Emulator(x) (3) Programmer(Reality Man) People(friends) Software(U64)

Use(friends, U64) Runs(U64, N64 games) (4) (5) (6) (7) (8) This new premise unifies with (2) and (3). CS 561, Session 16-18 39 Forward Chaining Programmer(x) Emulator(y) People(z) Provide(x,z,y) Criminal(x)

(1) Use(friends, x) Runs(x, N64 games) Provide(Reality Man, friends, x) (2) Software(x) Runs(x, N64 games) Emulator(x) (3) Programmer(Reality Man) (4) People(friends) (5) Software(U64) (6) Use(friends, U64) (7) Runs(U64, N64 games) (8) Premises (6), (7) and (8) satisfy the implications fully. CS 561, Session 16-18

40 Forward Chaining Programmer(x) Emulator(y) People(z) Provide(x,z,y) Criminal(x) (1) Use(friends, x) Runs(x, N64 games) Provide(Reality Man, friends, x) (2) Software(x) Runs(x, N64 games) Emulator(x) (3) Programmer(Reality Man) People(friends) (5) Software(U64) Use(friends, U64) Runs(U64, N64 games) (8)

(4) (6) (7) So we can infer the consequents, which are now added to the knowledge base (this is done in two separate steps). CS 561, Session 16-18 41 Forward Chaining Programmer(x) Emulator(y) People(z) Provide(x,z,y) Criminal(x) (1)

Use(friends, x) Runs(x, N64 games) Provide(Reality Man, friends, x) (2) Software(x) Runs(x, N64 games) Emulator(x) (3) Programmer(Reality Man) (4) People(friends) (5) Software(U64) (6) Use(friends, U64) (7) Runs(U64, N64 games)

(8) Provide(Reality Man, friends, U64) Emulator(U64) (9) (10) Addition of these new facts triggers further forward chaining. CS 561, Session 16-18 42 Forward Chaining

Programmer(x) Emulator(y) People(z) Provide(x,z,y) Criminal(x) (1) Use(friends, x) Runs(x, N64 games) Provide(Reality Man, friends, x) (2) Software(x) Runs(x, N64 games) Emulator(x) Programmer(Reality Man) People(friends) (5) Software(U64) (6)

Use(friends, U64) (4) (7) Runs(U64, N64 games) (8) Provide(Reality Man, friends, U64) Emulator(U64) (3) (9)

(10) Criminal(Reality Man) (11) Which results in the final conclusion: CS 561, Session 16-18 Criminal(Reality Man) 43 Forward Chaining Forward Chaining acts like a breadth-first search at the top level, with depth-first sub-searches.

Since the search space spans the entire KB, a large KB must be organized in an intelligent manner in order to enable efficient searches in reasonable time. CS 561, Session 16-18 44 Backward Chaining The algorithm (available in detail in textbook): a knowledge base KB a desired conclusion c or question q

finds all sentences that are answers to q in KB or proves c if q is directly provable by premises in KB, infer q and remember how q was inferred (building a list of answers). find all implications that have q as a consequent. for each of these implications, find out whether all of its premises are now in the KB, in which case infer the consequent and add it to the KB, remembering how it was inferred. If necessary, attempt to prove the implication also via backward chaining premises that are conjuncts are processed one conjunct at a time CS 561, Session 16-18 45 Backward Chaining

Question: Has Reality Man done anything criminal? Criminal(Reality Man) Possible answers: Steal(x, y) Criminal(x) Kill(x, y) Criminal(x) Grow(x, y) Illegal(y) Criminal(x) HaveSillyName(x) Criminal(x) Programmer(x) Emulator(y) People(z) Provide(x,z,y) Criminal(x) CS 561, Session 16-18 46

Backward Chaining Question: Has Reality Man done anything criminal? Criminal(x) CS 561, Session 16-18 47 Backward Chaining Question: Has Reality Man done anything criminal? Criminal(x) Steal(x,y)

CS 561, Session 16-18 48 Backward Chaining Question: Has Reality Man done anything criminal? Criminal(x) Steal(x,y) FAIL CS 561, Session 16-18 49 Backward Chaining

Question: Has Reality Man done anything criminal? Criminal(x) Steal(x,y) Kill(x,y) FAIL CS 561, Session 16-18 50 Backward Chaining Question: Has Reality Man done anything criminal?

Criminal(x) Steal(x,y) FAIL Kill(x,y) FAIL CS 561, Session 16-18 51 Backward Chaining Question: Has Reality Man done anything criminal? Criminal(x) Steal(x,y)

FAIL Kill(x,y) grows(x,y) Illegal(y) FAIL CS 561, Session 16-18 52 Backward Chaining Question: Has Reality Man done anything criminal?

Criminal(x) Steal(x,y) FAIL Kill(x,y) FAIL grows(x,y) FAIL CS 561, Session 16-18 Illegal(y) FAIL

53 Backward Chaining Question: Has Reality Man done anything criminal? Criminal(x) Steal(x,y) FAIL Kill(x,y) FAIL grows(x,y) FAIL

Illegal(y) FAIL Backward Chaining is a depth-first search: in any knowledge base of realistic size, many search paths will result in failure. CS 561, Session 16-18 54 Backward Chaining Question: Has Reality Man done anything criminal? We will use the same knowledge as in our forward-chaining version of this example: Programmer(x) Emulator(y) People(z) Provide(x,z,y) Criminal(x) Use(friends, x) Runs(x, N64 games) Provide(Reality Man, friends,

x) Software(x) Runs(x, N64 games) Emulator(x) Programmer(Reality Man) People(friends) Software(U64) Use(friends, U64) Runs(U64, N64 games) CS 561, Session 16-18 55 Backward Chaining Question: Has Reality Man done anything criminal?

Criminal(x) CS 561, Session 16-18 56 Backward Chaining Question: Has Reality Man done anything criminal? Criminal(x) Programmer(x) Yes, {x/Reality Man} CS 561, Session 16-18

57 Backward Chaining Question: Has Reality Man done anything criminal? Criminal(x) Programmer(x) People(Z) Yes, {x/Reality Man} Yes, {z/friends} CS 561, Session 16-18

58 Backward Chaining Question: Has Reality Man done anything criminal? Criminal(x) Programmer(x) Yes, {x/Reality Man} Emulator(y) People(Z) Yes, {z/friends}

CS 561, Session 16-18 59 Backward Chaining Question: Has Reality Man done anything criminal? Criminal(x) Programmer(x) Emulator(y) Yes, {x/Reality Man}

People(z) Yes, {z/friends} Software(y) Yes, {y/U64} CS 561, Session 16-18 60 Backward Chaining Question: Has Reality Man done anything criminal? Criminal(x) Programmer(x)

Emulator(y) People(z) Yes, {x/Reality Man} Yes, {z/friends} Software(y) Runs(U64, N64 games) Yes, {y/U64} yes, {} CS 561, Session 16-18

61 Backward Chaining Question: Has Reality Man done anything criminal? Criminal(x) Programmer(x) Emulator(y) People(z) Yes, {x/Reality Man} Provide

(reality man, Yes, {z/friends} U64, friends) Software(y) Runs(U64, N64 games) Yes, {y/U64} yes, {} CS 561, Session 16-18 62 Backward Chaining Question: Has Reality Man done anything criminal?

Criminal(x) Programmer(x) Emulator(y) People(z) Yes, {x/Reality Man} Provide (reality man, U64, Yes, {z/friends} friends)

Software(y) Yes, {y/U64} Use(friends, U64) CS 561, Session 16-18 Runs(U64, N64 games) yes, {} 63 Backward Chaining Backward Chaining benefits from the fact that it is directed toward proving one statement or answering one question. In a focused, specific knowledge base, this greatly decreases the amount of superfluous work that

needs to be done in searches. However, in broad knowledge bases with extensive information and numerous implications, many search paths may be irrelevant to the desired conclusion. Unlike forward chaining, where all possible inferences are made, a strictly backward chaining system makes inferences only when called upon to answer a query. CS 561, Session 16-18 64 Completeness As explained earlier, Generalized Modus Ponens requires sentences to be in Horn form:

atomic, or an implication with a conjunction of atomic sentences as the antecedent and an atom as the consequent. However, some sentences cannot be expressed in Horn form. e.g.: x bored_of_this_lecture (x) Cannot be expressed in Horn form due to presence of negation. CS 561, Session 16-18 65 Completeness A significant problem since Modus Ponens

cannot operate on such a sentence, and thus cannot use it in inference. Knowledge exists but cannot be used. Thus inference using Modus Ponens is incomplete. CS 561, Session 16-18 66 Completeness However, Kurt Gdel in 1930-31 developed the completeness theorem, which shows that it is possible to find complete inference rules. The theorem states: any sentence entailed by a set of sentences can be

proven from that set. => Resolution Algorithm which is a complete inference method. CS 561, Session 16-18 67 Completeness The completeness theorem says that a sentence can be proved if it is entailed by another set of sentences. This is a big deal, since arbitrarily deeply nested functions combined with universal quantification make a potentially infinite search space.

But entailment in first-order logic is only semidecidable, meaning that if a sentence is not entailed by another set of sentences, it cannot necessarily be proven. CS 561, Session 16-18 68 Completeness in FOL CS 561, Session 16-18 69 Historical note

CS 561, Session 16-18 70 Kinship Example KB: (1) father (art, jon) (2) father (bob, kim) (3) father (X, Y) parent (X, Y) Goal: parent (art, jon)? CS 561, Session 16-18 71

Refutation Proof/Graph parent(art,jon) father(X, Y) \/ parent(X, Y) \ / father (art, jon) father (art, jon) \ / [] CS 561, Session 16-18 72 Resolution

CS 561, Session 16-18 73 Resolution inference rule CS 561, Session 16-18 74 Remember: normal forms product of sums of simple variables or negated simple variables

sum of products of simple variables or negated simple variables CS 561, Session 16-18 75 Conjunctive normal form CS 561, Session 16-18 76 Skolemization

CS 561, Session 16-18 77 Examples: Converting FOL sentences to clause form Convert the sentence 1. (x)(P(x) => ((y)(P(y) => P(f(x,y))) ^ (y)(Q(x,y) => P(y)))) (like A => B ^ C) 2. Eliminate => (x)(P(x) ((y)(P(y) P(f(x,y))) ^ (y) (Q(x,y) P(y)))) 3. Reduce scope of negation (x)(P(x) ((y)(P(y) P(f(x,y))) ^ (y)(Q(x,y) ^ P(y)))) 4. Standardize variables (x)(P(x) ((y)(P(y) P(f(x,y))) ^ (z)(Q(x,z) ^ P(z))))

CS 561, Session 16-18 78 Examples: Converting FOL sentences to clause form 5. Eliminate existential quantification (x)(P(x) ((y)(P(y) P(f(x,y))) ^ (Q(x,g(x)) ^ P(g(x))))) 6. D), that is (B rop universal quantification symbols (P(x) ((P(y) P(f(x,y))) ^ (Q(x,g(x)) ^ P(g(x))))) 7. Convert to conjunction of disjunctions (P(x) P(y) P(f(x,y))) ^ (P(x) Q(x,g(x))) ^(P(x) P(g(x)))

CS 561, Session 16-18 79 Examples: Converting FOL sentences to clause form 8. Create separate clauses P(x) P(y) P(f(x,y)) P(x) Q(x,g(x)) P(x) P(g(x)) 9. Standardize variables P(x) P(y) P(f(x,y)) P(z) Q(z,g(z)) P(w) P(g(w)) CS 561, Session 16-18

80 Resolution proof CS 561, Session 16-18 81 Resolution proof CS 561, Session 16-18 82 Inference in First-Order Logic

Canonical forms for resolution Conjunctive Normal Form (CNF) Form (INF) P ( w) Q( w) P( x) R( x) Q( y ) S ( y ) R( z ) S ( z ) Implicative Normal P( w) Q( w) True P ( x) R ( x) Q( y ) S ( y ) R( z ) S ( z )

CS 561, Session 16-18 83 Example of Refutation Proof (in conjunctive normal form) (1) Cats like fish (2) Cats eat everything they like (3) Josephine is a cat. (4) Prove: Josephine eats fish. cat (x) likes (x,fish) cat (y) likes (y,z) eats (y,z)

cat (jo) eats (jo,fish) CS 561, Session 16-18 84 Refutation Negation of goal wff: eats(jo, fish) z) eats(jo, fish) cat(y) likes(y, z) eats(y, = {y/jo, z/fish}

cat(jo) likes(jo, fish) cat(jo) = cat(x) likes(x, fish) likes(jo, fish) = {x/jo} cat(jo) CS 561, Session 16-18 cat(jo)

(contradiction) 85 Forward chaining cat (jo) \ cat (X) likes (X,fish) / likes (jo,fish)

cat (Y) likes (Y,Z) eats (Y,Z) \ / cat (jo) eats (jo,fish) cat (jo) \ / eats (jo,fish)

eats (jo,fish) \ / [] CS 561, Session 16-18 86 Backward chaining Is more problematic and seldom used CS 561, Session 16-18

87

Recently Viewed Presentations

  • Department of Meteorology CARBONACEOUS AEROSOL ABSORPTION IN HADGEM3

    Department of Meteorology CARBONACEOUS AEROSOL ABSORPTION IN HADGEM3

    Modelled dry SSA matches the aircraft estimate of ~0.85 well with no changes required to the model. However, to match ambient SSA retrieved by AERONET in Ascension, one would need to multiply BC emissions by 3 and make OC absorbing....
  • Chapter 3 Logic Gates and Boolean Algebra

    Chapter 3 Logic Gates and Boolean Algebra

    Chapter 3 Logic Gates and Boolean Algebra - Part 1 ... the logic levels present at the inputs. 3-3 OR Operation with OR gates Truth Table and circuit symbol 3-3 symbol and truth table for a three-input OR gate Summary...
  • Elements of Nonfiction - Montgomery Township School District

    Elements of Nonfiction - Montgomery Township School District

    Elements of Nonfiction What is nonfiction? It is writing about real people, places things, and ideas. Purposes on Nonfiction To inform To give an opinion To persuade To entertain Types of Nonfiction Biography/autobiography Personal narrative (one incident) Informative article True-life...
  • Linversion --another way to make a question. What

    Linversion --another way to make a question. What

    **Inversion with verbs that end in a vowel in the third person** When you invert the subjects . il (he), elle (she), or . on (one) and a verb that ends in a vowel when conjugated, pronunciation requires that you...
  • Engineering Your Future

    Engineering Your Future

    Front Page Test:" What if my decision was reported on the front page of the . ... Engineering Your Future, A Comprehensive Approach, Sixth Edition, by Oakes, Leone, Gunn. Publisher: Great Lake Press.
  • Data Types and Conversions, Input from the Keyboard

    Data Types and Conversions, Input from the Keyboard

    Data Types and Conversions, Input from the Keyboard. CS303E: Elements of Computers and Programming. What is a Data Type? The type of value stored by a variable. Two so far: String: represents text. For now, only use for input/output. More...
  • GCSE Food Preparation and Nutrition What factors affect food ...

    GCSE Food Preparation and Nutrition What factors affect food ...

    Factors combined. Key things to remember: Many people in the world do not have much choice about the food they eat. For people who have choices, a mixture . individua. l needs combined with . economic, social, moral . and...
  • New Work-Study Student Information Session

    New Work-Study Student Information Session

    You will submit a time sheet on uaonline to document hours worked. Important: submit correct time on time sheet and get supervisor's approval. Ask your employer about deadline for submitting hours worked. Pay day is every other Friday and timesheets...