CPECSC481Knowledge-BasedSystems

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level, 2002 Franz J. Kurfess,Logic and Reasoning,60,CPE/CSC 481: Knowledge-Based Systems,Dr. Franz J. Kurfess,Computer Science Department,Cal Poly,Course Overview,Introduction,Knowledge Representation,Semantic Nets, Frames, Logic,Reasoning and Inference,Predicate Logic, Inference Methods, Resolution,Reasoning with Uncertainty,Probability, Bayesian Decision Making,Expert System Design,ES Life Cycle,CLIPS Overview,Concepts, Notation, Usage,Pattern Matching,Variables, Functions, Expressions, Constraints,Expert System Implementation,Salience, Rete Algorithm,Expert System Examples,Conclusions and Outlook,Overview Logic and Reasoning,Motivation,Objectives,Knowledge and Reasoning,logic as prototypical reasoning system,syntax and semantics,validity and satisfiability,logic languages,Reasoning Methods,propositional and predicate calculus,inference methods,Knowledge Representation and Reasoning Methods,Production Rules,Semantic Nets,Schemata and Frames,Logic,Important Concepts and Terms,Chapter Summary,Logistics,Term Project,Lab and Homework Assignments,Exams,Grading,Bridge-In,Pre-Test,Motivation,Objectives,Evaluation Criteria,Chapter Introduction,Review of relevant concepts,Overview new topics,Terminology,Introduction to Logic,expresses knowledge in a particular mathematical notation,All birds have wings - x. Bird(x) - HasWings(x),rules of inference,guarantee that, given true facts or premises, the new facts or premises derived by applying the rules are also true,All robins are birds - x Robin(x) - Bird(x),given these two facts, application of an inference rule gives:,x Robin(x) - HasWings(x),Logic and Knowledge,rules of inference act on the superficial structure or syntax of the first 2 formulas,doesnt say anything about the meaning of birds and robins,could have substituted mammals and elephants etc.,major advantages of this approach,deductions are guaranteed to be correct to an extent that other representation schemes have not yet reached,easy to automate derivation of new facts,problems,computational efficiency,uncertain, incomplete, imprecise knowledge,Validity and Satisfiability,a sentence is valid or necessarily true if and only if it is true under all possible interpretations in all possible worlds,also called a tautology,IsBird(Robin) V IsBird(Robin),Stench1,1 V Stench1,1,OpenAreasquare in front of me V Wallsquare in front of me,is NOT a tautology!,assumes every square has either a wall or an open area, so not true for all worlds,If every square has either a wall or an open area in it, then OpenAreasquare in front of me V Wallsquare in front of me,is a tautology.,a sentence is satisfiable iff there is some interpretation in some world for which it is true,a sentence that is not satisfiable is unsatisfiable (also known as a contradiction):,It is raining and it is not raining.,Summary of Logic Languages,propositional logic,facts,true/false/unknown,first-order logic,facts, objects, relations,true/false/unknown,temporal logic,facts, objects, relations, times,true/false/unknown,probability theory,facts,degree of belief 0.1,fuzzy logic,degree of truth,degree of belief 0.1,Propositional Logic,Syntax,Semantics,Validity and Inference,Models,Inference Rules,Complexity,Syntax,symbols,logical constants,True, False,propositional symbols,P, Q, ,logical connectives,conjunction , disjunction ,negation ,implication , equivalence ,parentheses, ,sentences,constructed from simple sentences,conjunction, disjunction, implication, equivalence, negation,BNF Grammar Propositional Logic,Sentence, AtomicSentence | ComplexSentence,AtomicSentence,True,|,False,|,P,|,Q,|,R,|,.,ComplexSentence,(,Sentence,),| Sentence Connective Sentence,|,Sentence,Connective,|,|,|,ambiguities are resolved through precedence, ,or parentheses,e.g.,P,Q,R,S,is equivalent to (,P),(Q,R),S,Semantics,interpretation of the propositional symbols and constants,symbols can be any arbitrary fact,sentences consisting of only a propositional symbols are satisfiable, but not valid,the constants,True,and,False,have a fixed interpretation,True,indicates that the world is as stated,False,indicates that the world is not as stated,specification of the logical connectives,frequently explicitly via truth tables,Truth Tables for,Connectives,P,True,True False,False,P,Q,False,False,False,True,P,Q,False,True,True,True,P,Q,True,True,False True,P,Q,True,False,False,True,Q,False,True,False True,P,False,False,True,True,Validity and Inference,truth tables can be used to test sentences for validity,one row for each possible combination of truth values for the symbols in the sentence,the final value must be,True,for every sentence,Propositional Calculus,properly formed statements that are either True or False,syntax,logical constants, True and False,proposition symbols such as P and Q,logical connectives: and , or V, equivalence , implies = and not ,parentheses to indicate complex sentences,sentences in this language are created through application of the following rules,True and False are each (atomic) sentences,Propositional symbols such as P or Q are each (atomic) sentences,Enclosing symbols and connective in parentheses yields (complex) sentences, e.g., (P Q),Complex Sentences,Combining simpler sentences with logical connectives yields complex sentences,conjunction,sentence whose main connective is and: P (Q V R),disjunction,sentence whose main connective is or: A V (P Q),implication (conditional),sentence such as (P Q) = R,the left hand side is called the premise or antecedent,the right hand side is called the conclusion or consequent,implications are also known as rules or if-then statements,equivalence (biconditional),(P Q) (Q P),negation,the only unary connective (operates only on one sentence),e.g., P,Syntax of Propositional Logic,A BNF (Backus-Naur Form) grammar of sentences in propositional logic,Sentence - AtomicSentence | ComplexSentence,AtomicSentence - True | False | P | Q | R | .,ComplexSentence - (Sentence),| Sentence Connective Sentence,| Sentence,Connective - | V | | =,Semantics,propositions can be interpreted as any facts you want,e.g., P means robins are birds, Q means the wumpus is dead, etc.,meaning of complex sentences is derived from the meaning of its parts,one method is to use a truth table,all are easy except P = Q,this says that if P is true, then I claim that Q is true; otherwise I make no claim;,P is true and Q is true, then P = Q is true,P is true and Q is false, then P = Q is false,P is false and Q is true, then P = Q is true,P is false and Q is false, then P = Q is true,Exercise Semantics and Truth Tables,Use a truth table to prove the following:,P represents the fact Wally is in location 1, 3 - W1,3,H represents the fact Wally is in location 2, 2 - W2,2,We know that Wally is either in 1,3 or 2,2: (P V H),We learn that Wally is not in 2,2: H,Can we prove that Wally is in 1,3: (P V H) H) = P,This says that if the agent has some premises, and a possible conclusion, it can determine if the conclusion is true (i.e., all the rows of the truth table are true),Inference Rules,more efficient than truth tables,Modus Ponens,eliminates =,(X = Y), X,_,Y,If it rains, then the streets will be wet.,It is raining.,Infer the conclusion: The streets will be wet. (affirms the antecedent),Modus tollens,(X = Y), Y,_, X,If it rains, then the streets will be wet.,The streets are not wet.,Infer the conclusion: It is not raining.,NOTE: Avoid the fallacy of affirming the consequent:,If it rains, then the streets will be wet.,The streets are wet.,cannot,conclude that it is raining.,If Bacon wrote Hamlet, then Bacon was a great writer.,Bacon was a great writer.,cannot conclude that Bacon wrote Hamlet.,Syllogism,chain implications to deduce a conclusion),(X = Y), (Y = Z),_,(X = Z),More Inference Rules,and-elimination,and-introduction,or-introduction,double-negation elimination,unit resolution,Resolution,(X v Y), (Y v Z),_,(X v Z),basis for the inference mechanism in the Prolog language and some theorem provers,Complexity issues,truth table enumerates 2,n,rows of the table for any proof involving n symbol,it is complete,computation time is exponential in n,checking a set of sentences for satisfiability is NP-complete,but there are some circumstances where the proof only involves a small subset of the KB, so can do some of the work in polynomial time,if a KB is monotonic (i.e., even if we add new sentences to a KB, all the sentences entailed by the original KB are still entailed by the new larger KB), then you can apply an inference rule locally (i.e., dont have to go checking the entire KB),Horn clauses or sentences,class of sentences for which a polynomial-time inference procedure exists,P1 P2 .Pn = Q,where Pi and Q are non-negated atoms,not every knowledge base can be written as a collection of Horn sentences,Reasoning in Knowledge-Based Systems,shallow and deep reasoning,forward and backward chaining,alternative inference methods,metaknowledge,Shallow and Deep Reasoning,shallow reasoning,also called experiential reasoning,aims at describing aspects of the world heuristically,short inference chains,possibly complex rules,deep reasoning,also called causal reasoning,aims at building a model of the world that behaves like the “real thing”,long inference chains,often simple rules that describe cause and effect relationships,Examples Shallow and Deep Reasoning,shallow reasoning,deep reasoning,IF a car has,a good battery,good spark plugs,gas,good tires,THEN the car can move,IF the battery is goodTHEN there is electricity,IF there is electricity ANDgood spark plugsTHEN the spark plugs will fire,IF the spark plugs fire ANDthere is gasTHEN the engine will run,IF the engine runs AND there are good tiresTHEN the car can move,Forward Chaining,given a set of basic facts, we try to derive a conclusion from these facts,example: What can we conjecture about Clyde?,IF elephant(x) THEN mammal(x),IF mammal(x) THEN animal(x),elephant (Clyde),modus ponens:,IF p THEN q,p,q,unification:,find compatible values for variables,Forward Chaining Example,IF elephant(x) THEN mammal(x),IF mammal(x) THEN animal(x),elephant(Clyde),modus ponens:,IF p THEN q,p,q,elephant (Clyde),IF elephant( x ) THEN mammal( x ),unification:,find compatible values for variables,Forward Chaining Example,IF elephant(x) THEN mammal(x),IF mammal(x) THEN animal(x),elephant(Clyde),modus ponens:,IF p THEN q,p,q,elephant (Clyde),IF elephant(Clyde) THEN mammal(Clyde),unification:,find compatible values for variables,Forward Chaining Example,IF elephant(x) THEN mammal(x),IF mammal(x) THEN animal(x),elephant(Clyde),modus ponens:,IF p THEN q,p,q,elephant (Clyde),IF elephant(Clyde) THEN mammal(Clyde),IF mammal( x ) THEN animal( x ),unification:,find compatible values for variables,Forward Chaining Example,IF elephant(x) THEN mammal(x),IF mammal(x) THEN animal(x),elephant(Clyde),modus ponens:,IF p THEN q,p,q,elephant (Clyde),IF elephant(Clyde) THEN mammal(Clyde),IF mammal(Clyde) THEN animal(Clyde),unification:,find compatible values for variables,Forward Chaining Example,IF elephant(x) THEN mammal(x),IF mammal(x) THEN animal(x),elephant(Clyde),modus ponens:,IF p THEN q,p,q,elephant (Clyde),IF elephant(Clyde) THEN mammal(Clyde),IF mammal(Clyde) THEN animal(Clyde),animal( x ),unification:,find compatible values for variables,Forward Chaining Example,IF elephant(x) THEN mammal(x),IF mammal(x) THEN animal(x),elephant(Clyde),modus ponens:,IF p THEN q,p,q,elephant (Clyde),IF elephant(Clyde) THEN mammal(Clyde),IF mammal(Clyde) THEN animal(Clyde),animal(Clyde),unification:,find compatible values for variables,Backward Chaining,Backward Chaining,try to find supportive evidence (i.e. facts) for a hypothesis,example: Is there evidence that Clyde is an animal?,IF elephant(x) THEN mammal(x),IF mammal(x) THEN animal(x),elephant (Clyde),modus ponens:,IF p THEN q,p,q,unification:,find compatible values for variables,Backward Chaining Example,IF elephant(x) THEN mammal(x),IF mammal(x) THEN animal(x),elephant(Clyde),modus ponens:,IF p THEN q,p,q,IF mammal( x ) THEN animal( x ),animal(Clyde),unification:,find compatible values for variables,?,Backward Chaining Example,IF elephant(x) THEN mammal(x),IF mammal(x) THEN animal(x),elephant(Clyde),modus ponens:,IF p THEN q,p,q,IF mammal(Clyde) THEN animal(Clyde),animal(Clyde),unification:,find compatible values for variables,?,Backward Chaining Example,IF elephant(x) THEN mammal(x),IF mammal(x) THEN animal(x),elephant(Clyde),modus ponens:,IF p THEN q,p,q,IF elephant( x ) THEN mammal( x ),IF mammal(Clyde) THEN animal(Clyde),animal(Clyde),unification:,find compatible values for variables,?,?,Backward Chaining Example,IF elephant(x) THEN mammal(x),IF mammal(x) THEN animal(x),elephant(Clyde),modus ponens:,IF p THEN q,p,q,IF elephant(Clyde) THEN mammal(Clyde),IF mammal(Clyde) THEN animal(Clyde),animal(Clyde),unification:,find compatible values for variables,?,?,Backward Chaining Example,IF elephant(x) THEN mammal(x),IF mammal(x) THEN animal(x),elephant(Clyde),modus ponens:,IF p THEN q,p,q,elephant ( x ),IF elephant(Clyde) THEN mammal(Clyde),IF mammal(Clyde) THEN animal(Clyde),animal(Clyde),unification:,find compatible values for variables,?,?,?,Backward Chaining Example,IF elephant(x) THEN mammal(x),IF mammal(x) THEN animal(x),elephant(Clyde),modus ponens:,IF p THEN q,p,q,elephant (Clyde),IF elephant(Clyde) THEN mammal(Clyde),IF mammal(Clyde) THEN animal(Clyde),animal(Clyde),unification:,find compatible values for variables,Forward vs. Backward Chaining,Forward Chaining,Backward Chaining,planning, control,diagnosis,data-driven,goal-driven (hypothesis),bottom-up reasoning,top-down reasoning,find possible conclusions supported by given facts,find facts that support a given hypothesis,similar to breadth-first search,similar to depth-first search,antecedents (LHS) control evaluation,consequents (RHS) control evaluation,Alternative Inference Methods,Metaknowledge,Post-Test,Evaluation,Criteria,Use of References,Giarratano & Riley 1998,Russell & Norvig 1995,Jackson 1999,Durkin 1994,Giarratano & Riley 1998,References,Altenkrger & Bttner Doris Altenkrger and Winfried Bttner.,Wissensbasierte Systems - Architektur, Enwicklung, Echtzeit-Anwendungen. Vieweg Verlag, 1992.,Awad 1996 Elias Awad.,Building Expert Systems - Principles, Procedures, and Applications.,West Publishing, Minneapolis/St. Paul, MN, 1996.,Bibel 1993 Wolfgang Bibel with Steffen Hldobler and Torsten Schaub.,Wissensreprsentation und Inferenz - Eine grundlegende Einfhrung. Vieweg Verlag, 1993.,Durkin 1994 John Durkin.,Expert Systems - Design and Development.,Prentice Hall, Englewood Cliffs, NJ, 1994.,Giarratano & Riley 1998 Joseph Giarratano and Gary Riley.,Expert Systems - Principles and Programming.,3,rd,ed., PWS Publishing, Boston, MA, 1998,Jackson, 1999 Peter Jackson.,Introduction to Expert Systems.,3,rd,ed., Addison-Wesley, 1999.,Russell & Norvig 1995 Stuart Russell and Peter Norvig,Artificial Intelligence - A Modern Approach.,Prentice Hall, 1995.,Important Concepts and Terms,natural language processing,neural network,predicate logic,propositional logic,rational agent,rationality,Turing test,agent,automated reasoning,belief network,cognitive science,computer science,hidden Markov model,intelligence,knowledge representation,linguistics,Lisp,logic,machine learning,microworlds,Summary Chapter-Topic,