Studies on Intelligence - Chapter 3: Representing Knowledge in Computer - Tu Bao Ho

1Chapter 3 Representing Knowledge in Computer K216 C: Studies on Intelligence School of Knowledge Science JAIST TuBao Ho 21. Introduction  Representing knowledge  Metrics for assessing knowledge representation schemes 2. Logic representation 3. Inference rules 4. Semantics networks 5. Frames and Scripts 6. Decision trees Outline of chapter 3 3Introduction  declarative knowledge is knowledge about things  location of JAIST, its transport links  “JAIST is in Tatsunokuchi”, “Hokuriku Railroad Ishikawa line goes from Nomachi to Tsurugi”  procedural knowledge is knowledge about how to do things  how to get to JAIST  “Take the Hokuriku Railroad, Ishikawa line to go to Tsurugi”, “Get on the JAIST shuttle” 4Introduction  domain-specific knowledge: specific knowledge on a particular subject Example: “JAIST shuttle goes from Tsurugi to JAIST”  domain-independent knowledge: general knowledge that applies throughout our experience Example: “shuttle bus is a means of transport”  Common sense: common knowledge about the world that is possessed by every schoolchild. It is evident for human but not for machine Example: “Bird can fly” 5Introduction  In order to make use of knowledge in AI and intelligent systems we need to get it from the source (knowledge acquisition) and represent it in a form usable by the machine  Human knowledge is usually expressed through language, which cannot be accurately understood by machine  The representation of knowledge in computer must therefore be both appropriate for the computer to use and allow easy and accurate encoding from the source 6The “15 game”: two people A and B take turns selecting numbers from 1 to 9 without replacement. The person who first has exactly three numbers in his collection that add up to 15 wins the game  A 5; B 3 (A selects 5; B selects 3)  A 5, 9; B 3, 1 (A selects 9: B chooses 1 to prevent A from achieving 15)  A 5, 9, 4; B 3, 1, 2 (A selects 4; B chooses 2 to block A)  A 5 9 4 6 win!! (A selects 6 and wins with 4+5+6 = 15) Example of representing knowledge 7Example of representing knowledge  A choosing 5 is equivalent to putting A’s marker in the tick- tack-toe board. Use tick-tack-toe representation for the “15 game” A A B A A B B B A A A B B A 5; B 3 A 5, 9; B 3, 1 A 5, 9, 4; B 3, 1, 2 A 5 9 4 6 win!! B A B AB A 3 1 4 5 92 6 8Aspects of representation languages 1. The syntax describes the possible configurations that can constitute sentences  External representation: how sentences are represented on the printed page  Internal representation: the real representation inside the computer 2. The semantics determines the fact in the world to which the sentences refer. Without semantics, a sentence is just an arrangement of electrons or a collection of marks on a page 9Metrics for assessing knowledge representation schemes  Expressiveness Handle different types and levels of knowledge  Effectiveness （効果） Effectiveness is doing the right thing  Efficiency （能率） Efficiency is doing the thing right  Explicitness Be able to provide an explanation of its inferences 10 Outline of chapter 3 1. Introduction 2. Logic representation 2.1 Propositional logic 2.2 Predicate logic 3. Inference rules 4. Semantics networks 5. Frames and Scripts 6. Decision trees 11 Propositional logic  A proposition is a statement that can have one of two values: true or false (known as truth values) Example: “It is raining” and “I am hungry” are propositions whose values depend on the situation at the time  Propositions P and Q can be combined using operators such as and  (PQ) and or  (PQ) Example: “It is raining” and “I am hungry” P Q PQ PQ T T T F T F F T F T F T F F F F True value table 12  simple syntax: proposition symbols such as P and Q with logical values True and False, and  the logical connectives , , , , , and ()  sentences are made by symbols using rules: - Propositional symbol such as P or Q is a sentence by itself - Wrapping parentheses around a sentence yields a sentence, e.g., (PQ) - A sentence can be formed by combining simpler sentences with one of the five logical connectives Propositional logic 13  (and): A sentence using , such as P  (Q  R), is called a conjunction (logic); its parts are the conjuncts  (or): A sentence using , such as A  (P  Q), is a disjunction of the disjuncts A and (P  Q)  (implies): A sentence such as (P  Q)  R is called an implication. Its premise or antecedent is P  Q, and its conclusion or consequent is R. Implications are also known as rules or if-then statements  (equivalent): The sentence (P  Q)  (Q  P) is an equivalence  (not): A sentence such as P is called the negation of P;  is the only connective that operates on a single sentence. Propositional logic 14 Straightforward semantics: we define it by specifying the interpretation of the proposition symbols and constants, and specifying the meanings of the logical connectives Propositional logic P Q P P  Q P  Q P  Q P  Q T T F T T T T T F F F T F F F T T F T T F F F T F F T T 15 Predicate logic  The propositional logic has limitations in its expressive power and is expanded to the predicate logic by introducing terms, functions, predicates, and quantifiers  A “predicate” denotes a relationship between objects - Red(x), a unary relation, is a predicate expression that asserts that x is red. - Father(Ichiro, Taro) asserts that Ichiro is the father of Taro.  A predicate can take on a value of true or false when its variables have assumed specific values 16 Predicate logic  Parametrized propositions give us predicate logic father(Ichiro, Taro), father(Ichiro, Jiro) father is the predicate, Ichiro, Taro and Jiro are parameters  In predicate logic parameters can also include variables father(Ichiro, x) x is a variable that can be instantiated with a value (name of someone of whom Ichiro is the father) 17  The universal quantifier (), e.g., x, is the notation that indicates “for all x” “all men are animals”: (x)[Man(x)  Animal(x)]  The existential quantifier, “there exists” is designated by an  “There is at least one x such that x is greater than zero” can be represented by (x)(x>0) “A red object is on top of a green one” can be represented by (x) (y)[Red(x)  Green(y)  ontop(x,y)] Predicate logic 18  These quantifiers can be combined in the same expression “Everyone has a mother” can be expressed as (x)(y)[(Human(x)  Mother(y, x)]  (x)Q(x) expresses the fact that something has a certain property without saying which thing has that property  (x)[P(x)  Q(x)] expresses the fact that everything in a certain class has a certain property without saying what everything in that class is Predicate logic 19 Semantics in logic representation  to an automatic theorem proving system these are merely symbols that are to be manipulated. The system sees no difference between P(x) and Red(x); the meaning or semantics must be provided by the user mapping the variables and functions to things in the problem domain.  The specification of a domain and the associations between logical symbols and the problem domain constitute an interpretation or a model of the logical system. 20 Assessing logic representation  expressive: it allows representation of facts, relationships between facts and assertions about facts. It is relatively understandable  effective: new facts can be inferred from old. It is also amenable to computation through PROLOG  efficient: the use of predicates and variables makes the representation scheme relatively efficient, although computational efficiency depends to a degree on the interpreter being used and the programmer  explicit: explanations and justifications can be provided by backtracking 21 Outline of chapter 3  Introduction  Logic representation  Inference rules  Representing knowledge by rules  The conditions of rules  Semantics networks  Frames and Scripts  Decision trees 22 Representing knowledge by rules  Inference rules (production rules) condition  conclusion [condition and action parts] A  B （if A then B）  if (Primary Exam>700) (live in Kansai)(good at math) then (take the entrance exam at the School of Knowledge Science of JAIST)  if (feel tired)  (has fever)  (sneeze) then (have a cold) 23 Representing knowledge by rules Given a true fact “Wind blows”, and the rule if wind blows then the hooper makes money, We have a total match of the form A = true if A then B and we can conclude B = true. To check whether a condition part matches a fact or an expression is called pattern-matching if height of X > height of Y then X is taller than Y height of Ichiro = 1.70m height of Jiro = 1.75m, X = Jiro, Y = Ichiro We get the result “Jiro is taller than Ichiro” 24 Using logical expressions The condition part of a production rule can contain the usual logical expressions. The following is a sample condition: Ex. if the season is june  isobarometric line runs east to west then isobarometric line is the line of rainy season Ex. if the line of rainy season is at the south shore of Japan  cloud is growing at the south shore of Japan then the south shore will have heavy rain 25  should not write rules that are inconsistent. Rules in which the condition parts are the same should have the same action parts if A then B and if A then B  should not write a production rule that causes a loop if A then B1 if B1 then B2 if Bn then A The conditions of rules 26 Assessing inference rules  Expressiveness: particularly good at representing procedural knowledge. They are ideal in situations where knowledge changes over time and where the final and initial states differ from user to user (or subject to subject)  Effectiveness: very amenable to computation  Efficiency: the scheme is relatively efficient for procedural problems, and their flexibility makes it transferable between domains  Explicitness: production systems can be programmed to provide explanations 27 Outline of chapter 3 1. Introduction 2. Logic representation 3. Inference rules 4. Semantic networks  Relationships among concepts  Property inheritance  Case frames 5. Frames and Scripts 6. Decision trees 28 Semantics networks  Knowledge is not only a fact or notion itself; it is also the relationships that exist among facts  Semantic networks are based on the idea that objects or concepts can be joined by some relationship. Semantic networks represent this relationship using an arc that connects the two concepts (nodes) 29 Relationship among concepts R x y (a) R(x, y) (b) R(x1, x2, ..., xn) R xn ... x1 x2 pred xn R ... x1 x2 The basic unit of a semantic network, as shown in Figure (a), corresponds to R(x,y) in predicate logic. A relation, R(xl, x2, , xn), with n arguments when expressed in logic, is hard to express in a semantic network. But it might look like Figure (b). 30  A common relation that joins two concepts in a semantic network is the more General/less General relation, which is also called the isa relation: A isa B Ex. isa isa Taro  human being  animal  Other relations besides isa links are: has X has Y (Y is a partial concept of X) is X is Y (X has Y property) cause X causes Y (X is a cause of Y) Relationship among concepts 31 black hair has is isa 23 year old Taro student is studies with at tall friend knowledge science school Taro is a student. Taro is 23 years old. Taro is tall. Taro has black hair. Taro studies with a friend at the school of knowledge science. ISA(Taro, student) IS(Taro, 23 years old) IS(Taro, tall) HAS(Taro, black hair) STUDY(Taro, friend, school of Knowledge Science) Relationship among concepts 32 Property inheritance animal isa isa invertebrate animal mollusk do isa move arthropod ~fly isa wing do isa has has penguin insect isa isa isa vertebrate animal bird dove has has do color isa fly white and neck bone black mammal carnivorous tiger isa animal isa do do lactate eat meat a Bird isa vertebrate animal a Mammal isa vertebrate animal a Carnivorous animal isa Mammal a Tiger isa Carnivorous animal wing has Insect Fly do Bird Semantics network of animal classification Some labels are isa. Labels on the other arcs represent other properties 33  The principle of property inheritance says that objects belonging to more specific concepts inherit all the properties of objects belonging to a more general concept (default value). The isa arc satisfies the transitive law and we can prove “A isa C” from “A isa B” and “B isa C”  A penguin is a bird and a bird has a property that it can fly. However, a penguin can not fly, and we must clearly indicate that fact, that means we need to modify the default value (a penguin “does not fly”)  Once we organize knowledge, it is easy to answer many questions - Does a bird fly? - What properties does a bird have? - Does a dove have a neck? Property inheritance 34 Property inheritance  there are two Taros and one is a teacher and the other is a student?  imagining that “Taro” is a label and using two nodes (token), and , both of which are joined to the label “Taro” Taro name name is is 23 years old 50 years old isa isa student teacher school of knowledge science 35 Case frames Consider knowledge relates to movement and change (persisting over time and space and relates many objects): time (when), location (where), agent (who), object (what), tool (how), purpose (why), method (how) study agent time (who) EVENT (when) object location (what) (where) tool method purpose (how) (how) (why) 36 A semantic network using a token expression: “Taro studied English in his room on April 1st” Case frames study agent time taro EVENT April 1st object location English his room 37 Semantics networks  expressiveness: The levels of the hierarchy provide a mechanism for representing general and specific knowledge. The representation is a model of human memory, and it is therefore relatively understandable  effectiveness: they support inference through property inheritance  efficiency: they reduce the size of the knowledge base and help maintain consistency in the knowledge base  explicitness: reasoning equates to following paths through the network, so the relationships and inference are explicit in the network links 38 Outline of chapter 3  Introduction  Logic representation  Inference rules  Semantics networks  Frames and Scripts  Frames  Scripts  Decision trees 39  Proposed by M. Minsky: when we look at, listen to, or think about something, we do so within a certain general framework  When we focus on one particular idea or object, there is often a frame (its internal structure) corresponding to the idea, which is a structure made up of slots that contain each constituent element of the idea. Frames 40 Frames name: instructor specialization of: teacher name: unit(last name, first name) age: unit(year) address: ADDRESS department: range (engineering, science, literature, law) subject: range (information science, computer, ) salary: SALARY date started: unit(year, month) name: student specialization of: young person name: unit(last name, first name) age: unit(year) address: ADDRESS home address: ADDRESS department: range(engineering, science, literature, law) subject: range(information science, computer, ) date entered: unit(year, month) Slots Slot content 41 Connection between frames teach frame student frame young people frame instructure frame ADDRESS SALARY name: SALARY monthly salary: unit(dollars) annual salary: unit(dollars) average monthly salary: unit(dollars), compute(AVE-M) tax amount: unit(dollars), compute(TAX) the system will do the calculation at the frames called AVE-M and TAX and return the results 42 Frames  expressiveness: they allow representation of structured knowledge and procedural knowledge  effectiveness: actions or operations can be associated with a slot and performed  efficiency: they allow more complex knowledge to be captured efficiently  explicitness: the additional structure makes the relative importance of particular objects and concepts explicit 43 Scripts location: bed room action: make bed open the window go to the door open the door and get out 1. get out of the bed go to the Bathroom France 2. wash one’s face 3. eat breakfast bath room location: bath room action: enter the bath room use the tooth brush wash one’s face comb one’s hair get out of the bath room ... location: kitchen action: ... folk blankets ... unlock the window key hold the window handle pull the handle walk hold the door knob turn the knob push the door open the door, ... turn on the tap, ... wipe your face by hand shave ... dry your face washstand mirror light ... tap sink tooth cleaning set shaving ... water comes out when you turn on the water water stops when you turn off the water water stays in when you close the drain water goes away when you open the drain tooth brush tooth paste Scripts describe knowledge about chronological flow. This script for getting up in the morning and eating breakfast 44 Overview  Introduction  Logic representation  Inference rules  Semantics networks  Frames and Scripts  Decision trees 45 Decision Trees Decision Tree is a classifier in the form of a tree structure that is either: A decision tree can be used to classify an instance by starting at the root of the tree and moving through it until a leaf is met.  a leaf, indicating a class of instances, or  a decision node that specifies some test to be carried out on a single attribute value, with one branch and subtree for each possible outcome of the test 46 Data of London Stock Market Major factors affecting the stock market: - What it did yesterday - Bank interest rate - What the New York market - Unemployment rate is doing today - England is losing Instance No. (previous days) 1 2 3 4 5 6 It rises today Y Y Y N N N It rose yesterday Y Y N Y N N NY rises today Y N N N N N Bank rate high N Y N Y N Y Unemployment high N Y Y N N N England is losing Y Y Y Y Y Y Decision to make: The London market will rise today? Y Y Y N N ? 7 47 Decision Trees Is unemployment high? YES NO Is the New York market rising today ? The London market will rise today YES NO The London market will rise today The London market will not rise today decision node leaf node {2, 3} {4, 5, 6}{1} 48 Semantic Network School Joe Boy Kay Woman Human Being Sam Mercedes Benz Car Silver Soccer Sport MF Food League Verdy Germany Man Has a child Has a child Is a Is a Is a Is a Is a Is a Is a Is a Color Made in Plays Is a Work for Needs Is member of Owns a Goes to Married to 49 Example of Frames Automobile Frame Class of: Transportation Name of manufacturer: Audi Origin of manufacturer: Germany Model: 5000 Turbo Type of car: Sedan Weight (kg): 1500 Wheelbase (inches): 105.8 Number of door: 4 (default) Transmission: 3-speed automatic Number of wheels: 4 (default) Engine: (Reference Engine Frame) - Type: In-line, overhead cam - Number of c