Introduction to Artificial Intelligence with Python PDF

Introduction to Artificial Intelligence with Python Knowledge knowledge-based agents agents that reason by operating on internal representations of knowledge If it didn't rain, Harry visited Hagrid today. Harry visited Hagrid or Dumbledore today, but not both. Harry visited Dumbledore tod...

Introduction to Artificial Intelligence with Python Knowledge knowledge-based agents agents that reason by operating on internal representations of knowledge If it didn't rain, Harry visited Hagrid today. Harry visited Hagrid or Dumbledore today, but not both. Harry visited Dumbledore today. Harry did not visit Hagrid today. It rained today. Logic sentence an assertion about the world in a knowledge representation language Propositional Logic Proposition Symbols P Q R Logical Connectives ¬ ∧ ∨ not and or → ↔ implication biconditional Not (¬) P ¬P false true true false And (∧) P Q P∧Q false false false false true false true false false true true true Or (∨) P Q P∨Q false false false false true true true false true true true true Implication (→) P Q P→Q false false true false true true true false false true true true Biconditional (↔) P Q P↔Q false false true false true false true false false true true true model assignment of a truth value to every propositional symbol (a "possible world")  P: It is raining. model Q: It is a Tuesday. {P = true, Q = false} knowledge base a set of sentences known by a knowledge-based agent Entailment α⊨β In every model in which sentence α is true, sentence β is also true. If it didn't rain, Harry visited Hagrid today. Harry visited Hagrid or Dumbledore today, but not both. Harry visited Dumbledore today. Harry did not visit Hagrid today. It rained today. inference the process of deriving new sentences from old ones P: It is a Tuesday. Q: It is raining. R: Harry will go for a run. KB: (P ∧ ¬Q) → R P ¬Q Inference: R Inference Algorithms  Does KB ⊨ α ? Model Checking Model Checking To determine if KB ⊨ α: Enumerate all possible models. If in every model where KB is true, α is true, then KB entails α. Otherwise, KB does not entail α. P: It is a Tuesday. Q: It is raining. R: Harry will go for a run. KB: (P ∧ ¬Q) → R P ¬Q Query: R P Q R KB false false false false false true false true false false true true true false false true false true true true false true true true P: It is a Tuesday. Q: It is raining. R: Harry will go for a run. KB: (P ∧ ¬Q) → R P ¬Q Query: R P Q R KB false false false false false false true false false true false false false true true false true false false false true false true true true true false false true true true false P: It is a Tuesday. Q: It is raining. R: Harry will go for a run. KB: (P ∧ ¬Q) → R P ¬Q Query: R P Q R KB false false false false false false true false false true false false false true true false true false false false true false true true true true false false true true true false Knowledge Engineering Clue Clue People Rooms Weapons Col. Mustard Ballroom Knife Prof. Plum Kitchen Revolver Ms. Scarlet Library Wrench Clue People Rooms Weapons Col. Mustard Ballroom Knife Prof. Plum Kitchen Revolver Ms. Scarlet Library Wrench Clue People Rooms Weapons Prof. Plum Library Wrench Ms. Scarlet Kitchen Knife Col. Mustard Ballroom Revolver People Rooms Weapons Prof. Plum Library Wrench Ms. Scarlet Kitchen Knife Col. Mustard Ballroom Revolver People Rooms Weapons Library Wrench Ms. Scarlet Kitchen Col. Mustard Revolver Prof. KnifePlum Ballroom Clue Propositional Symbols mustard ballroom knife plum kitchen revolver scarlet library wrench Clue (mustard ∨ plum ∨ scarlet) (ballroom ∨ kitchen ∨ library) (knife ∨ revolver ∨ wrench) ¬plum ¬mustard ∨ ¬library ∨ ¬revolver Logic Puzzles Gilderoy, Minerva, Pomona and Horace each belong to a different one of the four houses: Gryffindor, Hufflepuff, Ravenclaw, and Slytherin House. Gilderoy belongs to Gryffindor or Ravenclaw. Pomona does not belong in Slytherin. Minerva belongs to Gryffindor. Logic Puzzles Propositional Symbols GilderoyGryffindor MinervaGryffindor GilderoyHufflepuff MinervaHufflepuff GilderoyRavenclaw MinervaRavenclaw GilderoySlytherin MinervaSlytherin PomonaGryffindor HoraceGryffindor PomonaHufflepuff HoraceHufflepuff PomonaRavenclaw HoraceRavenclaw PomonaSlytherin HoraceSlytherin Logic Puzzles (PomonaSlytherin → ¬PomonaHufflepuff) (MinervaRavenclaw → ¬GilderoyRavenclaw) (GilderoyGryffindor ∨ GilderoyRavenclaw) Mastermind 2 0 4 Inference Rules Modus Ponens If it is raining, then Harry is inside. It is raining. Harry is inside. Modus Ponens α→ β α β And Elimination Harry is friends with Ron and Hermione. Harry is friends with Hermione. And Elimination α∧β α  Double Negation Elimination It is not true that Harry did not pass the test. Harry passed the test. Double Negation Elimination ¬(¬α) α Implication Elimination If it is raining, then Harry is inside. It is not raining or Harry is inside. Implication Elimination α→ β ¬α ∨ β Biconditional Elimination It is raining if and only if Harry is inside. If it is raining, then Harry is inside, and if Harry is inside, then it is raining. Biconditional Elimination α↔ β (α → β) ∧ (β → α) De Morgan's Law It is not true that both Harry and Ron passed the test. Harry did not pass the test or Ron did not pass the test. De Morgan's Law ¬(α ∧ β) ¬α ∨ ¬β De Morgan's Law It is not true that Harry or Ron passed the test. Harry did not pass the test and Ron did not pass the test. De Morgan's Law ¬(α ∨ β) ¬α ∧ ¬β Distributive Property (α ∧ (β ∨ γ)) (α ∧ β) ∨ (α ∧ γ) Distributive Property (α ∨ (β ∧ γ)) (α ∨ β) ∧ (α ∨ γ) Search Problems initial state actions transition model goal test path cost function Theorem Proving initial state: starting knowledge base actions: inference rules transition model: new knowledge base after inference goal test: check statement we're trying to prove path cost function: number of steps in proof Resolution (Ron is in the Great Hall) ∨ (Hermione is in the library) Ron is not in the Great Hall Hermione is in the library P∨Q ¬P Q P ∨ Q1 ∨ Q2 ∨...∨ Qn ¬P Q1 ∨ Q2 ∨...∨ Qn (Ron is in the Great Hall) ∨ (Hermione is in the library) (Ron is not in the Great Hall) ∨ (Harry is sleeping) (Hermione is in the library) ∨ (Harry is sleeping) P∨Q ¬P ∨ R Q∨R  P ∨ Q1 ∨ Q2 ∨...∨ Qn ¬P ∨ R1 ∨ R2 ∨...∨ Rm Q1 ∨ Q2 ∨...∨ Qn ∨ R1 ∨ R2 ∨...∨ Rm clause a disjunction of literals e.g. P ∨ Q ∨ R conjunctive normal form logical sentence that is a conjunction of clauses e.g. (A ∨ B ∨ C) ∧ (D ∨ ¬E) ∧ (F ∨ G) Conversion to CNF Eliminate biconditionals turn (α ↔ β) into (α → β) ∧ (β → α) Eliminate implications turn (α → β) into ¬α ∨ β Move ¬ inwards using De Morgan's Laws e.g. turn ¬(α ∧ β) into ¬α ∨ ¬β Use distributive law to distribute ∨ wherever possible Conversion to CNF (P ∨ Q) → R ¬(P ∨ Q) ∨ R eliminate implication (¬P ∧ ¬Q) ∨ R De Morgan's Law (¬P ∨ R) ∧ (¬Q ∨ R) distributive law Inference by Resolution P∨Q ¬P ∨ R (Q ∨ R)  P∨Q∨S ¬P ∨ R ∨ S (Q ∨ S ∨ R ∨ S) P∨Q∨S ¬P ∨ R ∨ S (Q ∨ R ∨ S) P ¬P () Inference by Resolution To determine if KB ⊨ α: Check if (KB ∧ ¬α) is a contradiction? If so, then KB ⊨ α. Otherwise, no entailment. Inference by Resolution To determine if KB ⊨ α: Convert (KB ∧ ¬α) to Conjunctive Normal Form. Keep checking to see if we can use resolution to produce a new clause. If ever we produce the empty clause (equivalent to False), we have a contradiction, and KB ⊨ α. Otherwise, if we can't add new clauses, no entailment.  Inference by Resolution Does (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) entail A? (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) ∧ (¬A) (A ∨ B) (¬B ∨ C) (¬C) (¬A)  Inference by Resolution Does (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) entail A? (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) ∧ (¬A) (A ∨ B) (¬B ∨ C) (¬C) (¬A)  Inference by Resolution Does (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) entail A? (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) ∧ (¬A) (A ∨ B) (¬B ∨ C) (¬C) (¬A) (¬B)  Inference by Resolution Does (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) entail A? (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) ∧ (¬A) (A ∨ B) (¬B ∨ C) (¬C) (¬A) (¬B)  Inference by Resolution Does (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) entail A? (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) ∧ (¬A) (A ∨ B) (¬B ∨ C) (¬C) (¬A) (¬B)  Inference by Resolution Does (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) entail A? (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) ∧ (¬A) (A ∨ B) (¬B ∨ C) (¬C) (¬A) (¬B) (A)  Inference by Resolution Does (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) entail A? (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) ∧ (¬A) (A ∨ B) (¬B ∨ C) (¬C) (¬A) (¬B) (A)  Inference by Resolution Does (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) entail A? (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) ∧ (¬A) (A ∨ B) (¬B ∨ C) (¬C) (¬A) (¬B) (A)  Inference by Resolution Does (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) entail A? (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) ∧ (¬A) (A ∨ B) (¬B ∨ C) (¬C) (¬A) (¬B) (A) ()  Inference by Resolution Does (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) entail A? (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) ∧ (¬A) (A ∨ B) (¬B ∨ C) (¬C) (¬A) (¬B) (A) () First-Order Logic Propositional Logic Propositional Symbols MinervaGryffindor MinervaHufflepuff MinervaRavenclaw MinervaSlytherin … First-Order Logic Constant Symbol Predicate Symbol Minerva Person Pomona House Horace BelongsTo Gilderoy Gryffindor Hufflepuff Ravenclaw Slytherin First-Order Logic Person(Minerva) Minerva is a person. House(Gryffindor) Gryffindor is a house. ¬House(Minerva) Minerva is not a house. BelongsTo(Minerva, Gryffindor) Minerva belongs to Gryffindor. Universal Quantification Universal Quantification ∀x. BelongsTo(x, Gryffindor) → ¬BelongsTo(x, Hufflepuff) For all objects x, if x belongs to Gryffindor, then x does not belong to Hufflepuff. Anyone in Gryffindor is not in Hufflepuff. Existential Quantification Existential Quantification ∃x. House(x) ∧ BelongsTo(Minerva, x) There exists an object x such that x is a house and Minerva belongs to x. Minerva belongs to a house. Existential Quantification ∀x. Person(x) → (∃y. House(y) ∧ BelongsTo(x, y)) For all objects x, if x is a person, then there exists an object y such that y is a house and x belongs to y. Every person belongs to a house. Knowledge  Introduction to Artificial Intelligence with Python