Chapter10.ppt

1、Knowledge Representation,Based on ppt slides for CMSC 421 by B.J. Dorr,2,2020年7月18日星期六,Knowledge Representation and Logic,Instructional Objective understand the importance of knowledge representation in intelligent agents understand the use of formal logic as a knowledge representation language lear

2、n different inference mechanisms should be able do the following: Represent a natural language description as statements in logic Deduct new sentences by applying inference rules.,3,2020年7月18日星期六,Logic,The Case of the Silk Gloves “It was elementary my dear Watson. The killer always left a silk glove

3、 at the scene of the murder. That was his calling card. Our investigations showed that only three people have purchased such gloves in the past year. Of these, Professor Doolally and Reverend Fisheye have iron-clad alibis, so the murderer must have been Sergeant Heavyset. When he tried to murder us

4、with that umbrella, we knew we had our man.”,4,2020年7月18日星期六,Not So Elementary,“The killer always left a silk glove at the scene of the murder.” (This is inductive reasoning - guessing at a hypothesis) “That was his calling card.” (This is abductive reasoning - choosing an explanation) “only three p

5、eople have purchased such gloves in the past year.” (This is model generation - constructing examples) “Professor Doolally and Reverend Fisheye have iron-clad alibis.” (This is constraint-based reasoning - ruling out possibilities) “so the murderer must have been Sergeant Heavyset.” (This is deducti

6、ve reasoning - inferring new information from known facts),5,2020年7月18日星期六,Bring on the Lawyers,The murderer always confesses in some way So, Holmes never has to defend his reasoning This is a good job, as its mostly unsound A good lawyer might point out that all the victims were - coincidentally -

7、members of the silk glove appreciation society. Wheres your case now, Mr. Holmes?,6,2020年7月18日星期六,Automated Reasoning,Very important area of AI research “Reasoning” usually means deductive reasoning New facts are deduced logically from old ones Inductive reasoning Guessing facts from old ones and fr

8、om evidence Two main aspects of deductive reasoning Logical representations (thousands of them) Rules of deduction (how to deduce new things),7,2020年7月18日星期六,Applications of Automated Reasoning,Automated theorem proving Automated mathematics Axioms(A) are given, theorem statement(T) is given Reasoni

9、ng agent searches from A to T (or from T to A) Using rules of deduction to move around the search space Automated verification Hardware and Software verification That they perform as specified Intel now have lots of people working on automated verification,8,2020年7月18日星期六,Logic as a Knowledge Repres

10、entation Language,A Logic is a formal language, with precisely defined syntax and semantics, which supports sound inference. Independent of domain of application. Different logics exist, which allow you to represent different kinds of things, and which allow more or less efficient inference. proposi

11、tional logic, predicate logic, temporal logic, modal logic, description logic. But representing some things in logic may not be very natural, and inferences may not be efficient. More specialised languages may be better.,9,2020年7月18日星期六,Propositional logic,In general a logic is defined by syntax: wh

12、at expressions are allowed in the language. Semantics: what they mean, in terms of a mapping to real world proof theory: how we can draw new conclusions from existing statements in the logic. Propositional logic is the simplest.,10,2020年7月18日星期六,Connectives: And, Or,“And” represented by: (i) If eith

13、er predicate p1 or predicate p2 is true (or both) then (p1 p2) is true Also note the use of brackets Indicate where to stop and work out truth values,11,2020年7月18日星期六,Connectives:Not, Implies, Equivalence,“Not” represented by: (i) (ii) (iii) + Changes predicate truth (true to false, or false to true

14、) “Implies” represented by: (i) or (ii) = If one statement is true, then another is also true “is equivalent to” represented by: (i) (ii) Youll also hear: “if and only if” & “necessary and sufficient condition”,12,2020年7月18日星期六,Propositional Logic: Syntax,Symbols (e.g., letters, words) are used to r

15、epresent facts about the world, e.g., “P” represents the fact “Andrew likes chocolate” “Q” represents the fact “Andrew has chocolate” These are called atomic propositions Logical connectives are used to represent and: , or: , if-then: , not: . Statements or sentences in the language are constructed

16、from atomic propositions and logical connectives. P Q “Andrew likes chocolate and he doesnt have any.” P Q “If Andrew likes chocolate then Andrew has chocolate”,13,2020年7月18日星期六,Propositional Logic: Semantics,What does it all mean? Sentences in propositional logic tell you about what is true or fals

17、e. P Q means that both P and Q are true. P Q means that either P or Q is true (or both) P Q means that if P is true, so is Q. This is all formally defined using truth tables.,X Y X Y T T TT F T F T TF F F,We now know exactly what is meant in terms of the truth of the elementary propositions when we

18、get a sentence in the language (e.g., P Q v R).,14,2020年7月18日星期六,Proof Theory,How do we draw new conclusions from existing supplied facts? We can define inference rules, which are guaranteed to give true conclusions given true premises. For propositional logic useful one is modus ponens: If A is tru

19、e and AB is true, then conclude B is true.,A, A B B,15,2020年7月18日星期六,Proof Theory and Inference,So, let P mean “It is raining”, Q mean “I carry my umbrella”. If we know that P is true, and P Q is true. We can conclude that Q is true. Note that certain expressions are equivalent think about P Q and P

20、 v Q.,16,2020年7月18日星期六,A B, B C A C,More complex rules of inference,Other rules of inference can be used, e.g.,: This is essentially the resolution rule of inference. Consider: What can we conclude?,sunny raining raining umbrella,17,2020年7月18日星期六,Proof,Suppose we want to try and prove that a certain

21、 proposition is true, given some sentences that are true. It turns out that the resolution rule is sufficient to do this. We put all the sentences into a standard or “normal” form (replacing A B with A B) There is then a standard procedure that lets you determine if the proposition in question is tr

22、ue.,18,2020年7月18日星期六,First Order Predicate Logic,Syntax and Semantics Keep thinking of predicate logic as a language We need to communicate (share knowledge) with AI agent Using logic as the knowledge representation scheme Need to both inform and understand Syntax Symbols used and how sentences are

23、put together Predicates, connectives, constants, functions, variables, quantifiers Semantics How we interpret sentences How we translate between the two languages How we tell the truth of a sentence,19,2020年7月18日星期六,Predicate Logic,Propositional logic isnt powerful enough as a general knowledge repr

24、esentation language. Impossible to make general statements. E.g., “all students sit exams” or “if any student sits an exam they either pass or fail”. So we need predicate logic.,20,2020年7月18日星期六,Predicates,Predicates are statements that Certain things are related in specific ways Predicate name iden

25、tifies the relationship Arguments are the things being related Arity is the number of things being related Example: father(bob,bill) Father is the predicate name Relationship is (nearly) obvious: bob is bills father Bob and bill are the arguments (arity here is 2) Predicates can relate Constants, fu

26、nctions and variables,21,2020年7月18日星期六,Examples of Connectives in Use,“Simon lectures AI and bioinformatics” lectures_ai(simon) lectures_bioinformatics(simon) Better: lectures(simon,ai) lectures(simon,bioinfo) “If Simon isnt lecturing AI, Bob must be” lectures(simon,ai) lectures(bob,ai) “George and

27、Tony will win or Saddam will lose” (will_win(george) will_win(tony) will_win(saddam),22,2020年7月18日星期六,Constants,Stand for actual things Such as england or barbara_woodhouse Also use constants for specific words like blue But blue has different shades In this case you should have: Made blue a predica

28、te name, then you could have had: shade_of_blue(aqua_marine), shade_of_blue(navy), etc. Choosing predicates and constants is important Convention: use lower case letters for constants,23,2020年7月18日星期六,Functions,Special predicates Where we think of them having inputs and an output If arity n, then th

29、e first n-1 arguments are inputs And the final argument is thought of the output Important Only a function if a set of inputs has a unique output Use the equals sign to make I/O clear And to make it clear this is a function,24,2020年7月18日星期六,Example of a Function,“The cost of an omelette at the Red L

30、ion is 5” Normally: cost_of(omelette,red_lion,five_pounds) But cost_of is a function Input: the name of a meal and the name of a pub Output: the cost of the meal So, we can write this as: cost_of(omelette,red_lion) = five_pounds,25,2020年7月18日星期六,Using Functions for Abbreviation,We want to minimise m

31、isunderstanding So, if we can, we should make sentences succinct If we want to, we can abbreviate: If we are talking about the output of a function We can replace it with the function part Example: “Omelettes at the Red Lion cost less than pancakes at House of Pancakes” less_than(cost_of(omelette,re

32、d_lion),cost_of(pancake,pancake_house),26,2020年7月18日星期六,Variables,Want to be more expressive now “Theres a meal at the Red Lion which costs 3” cost_of(meal,red_lion,3) But meal is a constant, like omelette or pancake Doesnt express what we wanted it to Were really talking about some general meal Not

33、 a meal in particular Call this meal X (a variable) cost_of(X,red_lion,3) Not quite right yet,27,2020年7月18日星期六,Variables Continued,Need to further express our beliefs about X We say that: “There is such a meal X” “There exists such a meal X” We need a symbol for “there exists” This is represented as

34、: X (cost_of(X,red_lion,3) Still not quite right (see later),28,2020年7月18日星期六,Quantifiers,The exists sign is known as a quantifier A sentence is known as “existentially quantified” Using quantifiers is known as quantification One other quantifier: (“for all sign”) Example: “all students enjoy AI lec

35、tures” X (student(X) enjoys(X,ai_lectures) This is “universally quantified” For all says that each predicate involving the quantified variable is true for every possible choice of that variable Terminology: Constants are ground variable, and we instantiate a variable “All meals cost 3” becomes “Spag

36、hetti costs 3”,29,2020年7月18日星期六,Be careful with quantifiers!,“There is a meal at the Red Lion which costs three pounds” X (meal(X) cost_of(red_lion, X, 3) What about: “All the meals at the Red Lion cost three pounds” Replace exists by for all:, X (meal(X) cost_of(red_lion, X, 3), X (meal(X) cost_of(

37、red_lion, X, 3), X (meal(X) serves(red_lion, X) cost_of(red_lion, X,3),30,2020年7月18日星期六,More Translation Pitfalls to Avoid,Getting and mixed up Example “Every Monday and Wednesday I go to Johns house for dinner” X (day(X,mon) day(X,weds) go(me,house(john) eat(me,dinner),31,2020年7月18日星期六,Even More Pi

38、tfalls,Getting confused with quantifiers Translate: “All things in the bag are red” Which of these translations is correct? 1. X (in_bag(X) red(X) 2. X (red(X) in_bag(X) 3. X ( Y (bag(X) in_bag(Y,X) red(Y),32,2020年7月18日星期六,Translating Logic to English,Take explicit sentence, make it more succinct Ex

39、ample: X (meal(X) cost_of(red_lion, X,3) 1. “There is something called X, where X is a meal and X costs three pounds at the Red Lion” 2. “There is a meal, X, which costs three pounds at the Red Lion” 3. “There is a meal which costs 3 at the Red Lion”,33,2020年7月18日星期六,Substitutions and Unifiers,A mot

40、ivating example: Axioms: (x)(Bird(x) Flies(x) Bird(Tweety) Goal: Flies(Tweety) In order to deduce the goal substitutions and unifiers must be used,34,2020年7月18日星期六,Substitutions and Unifiers,Substitution Definition: A substitution is a finite set of specifications of the form t/v, in which t is a te

41、rm, v is a variable, and tv. Substitutions are usually written in set notation: t1/v1, t2/v2, ., tn/vn Substitutions are applied to terms, or to sets of terms. Important: The semantics of a substitution is that all of its elements are applied simultaneously. Example: The application of the substitut

42、ion g(y)/x, h(z)/y, x/z to f(x, y, g(z), w) Is: f(g(y), h(z), g(x), w), and not: f(g(h(x), h(x), g(x), w). The order of the elements in a substitution list is irrelevant.,35,2020年7月18日星期六,Substitutions and Unifiers,Composition of substitutions: Substitutions may be composed. Example: Let s1 = f(a)/x

43、, g(b,z)/y, x/z s2 = w/x, h(z)/y, a/z Then s1s2 = f(a)/x, g(b,a)/y, w/z Note that Substitution composition occurs from left to right. Thus, s1s2 means that first s1 should be applied, and then s2. Application of substitution respects composition. That is: j(s1s2) = (js1)s2 Example: Let j = P(x,y,z),

44、 and let s1 and s2 be as above. Then js1 = P(f(a), g(b,z), x) (js1)s2 = P(f(a), g(b,a), w) = j(s1s2) Note, however, that composition is not commutative: s2s1 = w/x, h(x)/y, a/z s1s2.,36,2020年7月18日星期六,Substitutions and Unifiers,Unification Unification is the operation which is applied to terms in ord

45、er to make them “match”. It is accomplished by applying substitutions to the clauses containing the atoms to be matched. Definition: Let y1 and y2 be atoms. A unifier for y1 and y2 is a substitution s such that y1s = y2s Example: Let y1 = Bird(x) y2 = Bird(Tweety). Then s = Tweety/x is a unifier for

46、 these atoms. Let y1 = P(a, x, f(g(y) y2 = P(z, f(z), f(w) Then s = a/z, f(a)/x, g(y)/w is a unifier for y1 and y2. Let y1 = P(x,f(y),B) y2 = P(x,f(B),B) Then s1 = A/x,B/y s2 = B/y both are unifiers for y1 and y2. y1s1= y2s1= P(A,f(B),B) y1s2= y2s2= P(x,f(B),B),37,2020年7月18日星期六,Substitutions and Uni

47、fiers,Most general unifier (mgu) Unifiers are not unique A unifier g for atoms y1 and y2 is a most general unifier (mgu) if for any unifiers s of y1 and y2 , there exits a substitution s, s= gs. Mgu is unique. Let y1 = P(x,f(y),B) y2 = P(x,f(B),B) Then s1 = A/x,B/y s2 = B/y both are unifiers for y1

48、and y2. y1s1= y2s1= P(A,f(B),B) y1s2= y2s2= P(x,f(B),B) s1=s2A/x s2 is mgu,38,2020年7月18日星期六,Substitutions and Unifiers,The mgu algorithm: Example: y1 = P(a, x, f(g(y) y2 = P(z, f(z), f(w) Step 1: Make sure that the predicate symbols match. Atoms with different predicate symbols can never be unified.

49、 Step 2: Attempt to unify each pair of terms. The first pair is (a,z). Since one of the elements is a variable, they can be unified by substituting the other term for this variable. The appropriate substitution is a/z. So, set mgua/z This substitution must also be applied to both clauses yielding P(

50、a, x, f(g(y) P(a, f(a), f(w),39,2020年7月18日星期六,The mgu algorithm,Now the atoms become P(a, x, f(g(y) and P(a, f(a), f(w) The second pair is (x,f(a). Again, since one term is a variable, substitute the other for it: f(a)/x. The new value of mgu is the old value, composed with this new substitution. mg

51、u mguf(a)/x = a/z, f(a)/x This substitution must also be applied to both clauses yielding P(a, f(a), f(g(y) P(a, f(a), f(w) The third and final pair is (f(g(y),f(w). Neither is an atom, so we check to see whether the function symbols are the same. They are, so we strip them and unify each pair of su

52、b-terms. (In this case, there is just one such pair.) The new pair is (g(y),w). This pair may be unified with the substitution g(y)/w. Thus,mgu mgug(y)/w = a/z, f(a)/x, g(y)/w) This substitution must also be applied to both clauses yielding P(a, f(a), f(g(y) P(a, f(a), f(g(y) The clauses match, and

53、an mgu has been found.,40,2020年7月18日星期六,Substitutions and Unifiers,Not all pairs of atoms unify Example: y1 = Q(f(a), g(x) y2 = Q(y, y) y1 = Q(x, x) y2 = Q(y, f(y),41,2020年7月18日星期六,Translate the following sentences into first order logic. (a) All dogs are mammals (b) Fido is a dog (c) Fido is a mamm

54、al (d) All mammals produce milk Use the Modus Ponens deduction rule to deduce sentence (c) from (a) and (b). What did you unify in order to use Modus Ponens, and what substitution made the unification possible? Find the mgu of P(a,x,f(g(y) and P(z,h(z,u),f(w),42,2020年7月18日星期六,Semantic Networks,Seman

55、tic nets, frames and objects all allow you to define relations between objects, including class relations (X isa Y). Knowledge represented as a network or graph Only restricted inference supported by the methods - that based on inheritance,43,2020年7月18日星期六,Semantic network example,44,2020年7月18日星期六,M

56、any variations All represent individual objects, categories of objects and relationships among objects. Allows for inheritance reasoning Female persons inherit all properties from person. Inference of inverse links SisterOf vs. HasSister,45,2020年7月18日星期六,More Example,46,2020年7月18日星期六,By traversing n

57、etwork we can find: That Nellie has a head (by inheritance) That certain concepts related in certain ways (e.g., apples and elephants). BUT: Meaning of semantic networks was not always well defined. Are all Elephants big, or just typical elephants? Do all Elephants live in the “same” Africa? Do all

58、animals have the same head?,47,2020年7月18日星期六,Semantic networks,Drawbacks Links can only assert binary relations Can be resolved by reification of the proposition as an event Representation of default values Enforced by the inheritance mechanism.,48,2020年7月18日星期六,Semantic Networks,Logic is not the on

59、ly fruit Humans draw diagrams all the time, e.g., E.g. causal relationships:,49,2020年7月18日星期六,Graphical Representations,Graphs are very easy to store inside a computer For information to be of any use We must impose a formalism on the graphs Jason is 15, Bryan is 40, Arthur is 70, Jim is 74 How old is Julia?,50,2020年7月18日星期六,Better Graphical Representation,Because the formalism is the same We can guess that Julias age is similar to Bryans Limited the syntax to impose formalism,51,2020年7月18日星期六,Semantic Network Formalisms,Used a lot for n