L2A Knowledge Representation.ppt

Propositional Logic (Propositional Calculus) First-order Logic (First-order Predicate Calculus) Rules, Frames and Semantic Networks 19-Feb-15 1  Together, representation and reasoning support the operation of a knowledge- based agent. A Knowled...

Propositional Logic (Propositional Calculus) First-order Logic (First-order Predicate Calculus) Rules, Frames and Semantic Networks 19-Feb-15 1  Together, representation and reasoning support the operation of a knowledge- based agent. A Knowledge Representation Language is defined by two aspects: – Syntax and Semantics From the syntax and semantics, we can derive an inference mechanism for an agent that uses the language. 19-Feb-15 2 The syntax: Vocabulary: – A set of propositional symbols - e.g., P, Q, … A set of logical connectives or operators – usually  (OR),  (AND), ¬ (NOT), (implication), maybe  (equivalence), Parenthesis (for grouping) The special symbols – True, False (logical constants) 19-Feb-15 3 Rules for forming sentences: Each symbol (i.e., a constant or a propositional symbol) is a sentence (an atomic sentence). A sentence in parentheses is a sentence. If P and Q are sentences, then so are – P  Q (disjunction) – P  Q (conjunction) – ¬P (negation) – P Q (implication) – and similarly for whatever other connectives we allow 19-Feb-15 4 Sample What do the sentences sentences mean? P  E.g., P might be “It is True raining in Mombasa”, and P  Q Q, “Eldoret is a city” ¬P  We interpret logical (P  Q) connectives in the obvious way. ¬(P  Q)  E.g., ¬P means that P is not the ¬P  Q case; P  Q means that at least one of P or Q is true. (P  Q) R P  ¬P 19-Feb-15 5 Truth For sentences, we also get to say whether they are true or false. – True is always true; False always false. – P, Q, etc., are true or false depending on their interpretation. So these are satisfiable, but not valid. – Complex sentences are true or false as a function of their connective. Usually specified as a truth table. 19-Feb-15 6  Truth tables Conjunction() Disjunction() P Q PQ P Q PQ false false false false false false false true false false true true true false false true false true true true true true true true Implication() Negation() P Q PQ P P false false true true false false true false false true true false true true true true 19-Feb-15 7 A Proof Theory for Propositional Logic It is easy to devise a procedure to determine the truth of an arbitrary sentence in propositional logic. Just write down a big truth table, and see if the sentence is always true. E.g., suppose we want to know if ¬(PQ) ¬P  ¬Q. Here is a truth table: P Q ¬(PQ) ¬P  ¬Q ¬(PQ) ¬P  ¬Q false false true true true false true true true true true false true true true true true false false true 19-Feb-15 8 Reasoning in Propositional Logic Similarly, if we assume a few things, we can determine if something follows. E.g., if we assume P, then PQ, say, degenerates into True  Q, which a truth table will tell us is always true. So, we can always draw valid conclusions from premises, regardless of what any of this means 19-Feb-15 9  Propositional Logic has limitations, - it is not expressive enough First-Order Logic is an improvement and is useful 19-Feb-15 10 Note: FOL forms the basis of most representation schemes in A.I 19-Feb-15 11  FOL is an extension of Propositional Logic In FOL, the world consists of objects, i.e. things with individual identities and properties that distinguish them from other objects. Among these objects, various relations hold. Some of these relations are functions. i.e. relations in which there is only one “value” for a given “input”. Examples: – Objects: people, houses, colours, the moon, Mutua,... – Relation: brother of, bigger than, inside, part of, owns,.. – Properties: red, round, healthy, tall.. – Functions: father of, best friend,... 19-Feb-15 12 Syntax: Connectives - , , ,  Quantifiers - ,  Constants - A, X ,Mutua, Alice,.. 1, Variables - a, x, s,.. Predicate - Before, HasColour, Raining,.. Functions - Mother, LegOf,.. 19-Feb-15 13  Quantifiers allow expression of properties of entire collection of objects, instead of numerating the objects.  We examine the two standard quantifiers in predicate logic and these are universal and existential quantifiers. 19-Feb-15 14  This quantification is used when the predicate is true for all objects. For example:  (x), cat(x)  mammal(x). 19-Feb-15 15  This quantifier is used when a predicate P is true for some object in the universe. For example someone is tall may be denoted as x , tall(x).  Someone is short is denoted as x short(x).  Someone likes a given person is denoted by x, a likes(a, x). 19-Feb-15 16  Quantifiers can be mixed such as in x y likes(x,y) equivalenty x y likes(x,y).  To say there is someone who likes everyone we express x y likes(x,y).  To say there is some liked by everybody we express x y likes(y,x). 19-Feb-15 17   and  are linked by negation of each other. In the universe  represents a conjunction and  represents a disjunction. Everyone dislikes paper No one likes paper x likes(x, paper)  x likes(x, papers). Everyone likes sweets Nobody does not like sweets x likes(x, sweets)  x likes(x, sweets). “Everybody likes ice cream” no one who doesn’t like ice cream. x likes(x, icecream)  x likes(x, icecream) 19-Feb-15 18  x P  x P  x P  x P  x P  x P  x P  x P  PQ  (PQ) 19-Feb-15 19  (PQ)  PQ  PQ  (PQ)  PQ  (PQ)  Equality (=)  Equality symbol is used to indicate that two terms refer to the same object.  Father(jane) = james. 19-Feb-15 20  Example ‘ All men are people’  X: Man(X) Person(X)  If it is not raining, then it is sunny  RAINING SUNNY  Is converse true?  RAINING  SUNNY  All Kenyans are loyal to Kibaki or hate him   x : Kenyan(x) loyalto(x, Kibaki) hate(x, Kibaki).  Every one is loyal to someone  x : y : loyalto (x,y)  All men are people  x : man(x) person(x)  We explore the use of these notations further in a later section. 19-Feb-15 21  Some dogs bark  x. Dog x  Barks x All barking dogs are irritating. All barking dogs are irritating  x. Dog x  Barking x Irritating x 19-Feb-15 22  No dogs purr. ¬  x. Dog x  Purrs x  x. Dog x ¬ Purrs x  Fathers are male parents with children  x. Male x  Parent x  ( y. Child y and has x y)  Father x  Students are people who are enrolled in courses.  x. Student x  Person x  ( y. Course y  enrolled_on x y) 19-Feb-15 23 19-Feb-15 24  Production rules  A knowledge representation method in which knowledge is formalized into rules that have IF parts and THEN parts (also called conditions and actions, respectively)  A set of if-then rules - typically state that if certain conditions hold, then some action should be taken. 19-Feb-15 25  If -then relation: Examples: 1. IF high_temperature THEN prescribe aspirin IF A THEN B 2. IF international Conflict Begins AND it is in Middle East THEN oil price goes up. Symbolically: IF A AND B THEN C 19-Feb-15 26 Example Consider the following information given by consumers surveying bureau of Kenya Let the rules and symbols be as follows: “if one leaves near Muthaiga road (A)and has a plump salary(B) then he is likely to join muthaiga golf club(C). One can say he leaves near Muthaiga road(A) if he leaves less than 15 kilometers off the road.(D). The survey also reveals that you have to have a plump income (B) and be a who-is-who in Nairobi(E) so that you can join an exclusive club(F). If you can join an exclusive club(F) then you are likely to meet politicians(G). One who meets politicians (G)is said to be well connected(H). If one can join exclusive (F) and is a who-is-who in Nairobi (E) then he is well connected.(H). If well connected then (H)one can join Muthaiga golf club (C). If one can join Muthaiga golf club (C) then he is likely to meet the president (I).” 19-Feb-15 27  IF A AND B THEN C  IF D THEN A  IF B AND E THEN F  IF F THEN G  IF G THEN H  IF F AND E THEN H  IF H THEN C  IF C THEN I 19-Feb-15 28  Major advantages of rules  Rules are easy to understand  Inferences and explanations are easily derived  Modifications and maintenance are relatively easy  Uncertainty is easily combined with rules  Each rule is often independent of all others 19-Feb-15 29  Major limitations of rule representation:  Complex knowledge requires thousands of rules, which may create difficulties in using and maintaining the system  Builders like rules, so they try to force all knowledge into rules rather than look for more appropriate representations  Systems with many rules may have a search limitation in the control program  Some programs have difficulty evaluating rule-based systems and making inferences 19-Feb-15 30  Semantic network A knowledge representation method that consists of a network of nodes, representing concepts or objects, connected by arcs describing the relations between the nodes 19-Feb-15 31 A semantic net is represented as a graph, where the nodes in the graph represent concepts, and the arcs represent binary relationships between concepts. Nodes represent objects, attributes and values Links represent attributes and relationships between nodes Labels attached to links: the name of the corresponding attribute or relation 32 19-Feb-15 1. animal Is_a Is_a Has part reptile mammal head Is_a elephant Is_instance_of Clyde 19-Feb-15 33 19-Feb-15 34  Frame A knowledge representation scheme that associates one or more features with an object in terms of slots and particular slot values  Slot A sub-element of a frame of an object. A slot is a particular characteristic, specification, or definition used in forming a knowledge base  Facet An attribute or a feature that describes the content of a slot in a frame 19-Feb-15 35 19-Feb-15 36 Mammal subclass: Animal warm_blooded: yes Elephant subclass: Mammal * colour: grey * size: large Clyde instance: Elephant color: pink owner: Fred 37 19-Feb-15  Inheritance The process by which one object takes on or is assigned the characteristics of another object higher up in a hierarchy  Instantiate To assign (or substitute) a specific value or name to a variable in a frame (or in a logic expression), making it a particular “instance” of that variable 19-Feb-15 38 19-Feb-15 39 19-Feb-15 40 19-Feb-15 41  1. Machine Learning, Tom Mitchell, McGraw-Hill.  Stuart Russell, Norvig Peter, Artificial Intelligence : A Modern ApproachPrentice Hall series in AI 2ND ED, New Jersey, U.S.A, 2003  3. Rich,E., and Knight.K., Artificial Intelligence.2nd Ed., Tata Mcgraw-Hill , New Delhi India, 2003.Turban, E. Aronson, J., Decision Support systems and Intelligent Systems, 6nd Edition. Pearson Education, New Delhi India,2003.  2. WWW as guided topic to topic. 19-Feb-15 42 19-Feb-15 43