Chapter 3 - Knowledge Representation.pptx

Department of Computer Sciences College of Computers & Information Technology 501481-3 Artificial Intelligence Chapter 3: Knowledge Space Representation 1  Knowledge When we...

Department of Computer Sciences College of Computers & Information Technology 501481-3 Artificial Intelligence Chapter 3: Knowledge Space Representation 1  Knowledge When we handle knowledge, we need to address two fundamental issues: – How to represent knowledge space (Chapter 2&3) – How to implement the process of reasoning within that knowledge Space (Chapter 4&5) Our goal is to represent the world in logic, and to enable an intelligent agent (program) to make intelligent decision about its environment.  Knowledge representation Knowledge representation is the way to store and process knowledge efficiently. Knowledge is the primary factor to make a decision in an intelligent system. For an intelligent agent to decide, it needs a knowledge base (KB). The knowledge base represents facts about the world  What is Knowledge? data – primitive verifiable facts, of any representation. Data reflects current world, often voluminous frequently changing. information – interpreted data knowledge – relation among sets of data (information), that is very often used for further information deduction. Knowledge is (unlike data) general. Knowledge contains information about behavior of abstract models of the world.  General Knowledge Representations Schemas 1.Logic based representation – first order predicate logic (FOL) 2.Procedural representation – production rules 3.Network representation – semantic networks, conceptual graphs 4.Structural representation – scripts, frames, objects  Logic based representation Propositional Logic Knowledge is represented as propositions. Proposition is a statement that is either true or false. E.g. lobster is expensive. logical operators: join propositions in various ways – Conjunction (and) () – Disjunction (or) () – Negation (not) () – Implication ( ) – Equivalence ().  Propositional logic Consider the following example: – If it is raining, then the ground is wet. – If the ground is wet, then the ground is slippery. – It is raining. Let us define: – Logical symbol p = “it is raining” – Logical symbol q =“the ground is wet”. – Logical symbol r = “the ground is slippery”. Then to represent the above statements we right: – pq – qr – p.  Propositional logic Table below shows the truth of logical symbols connected with different logical connectors: p q p pq pq pq pq 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1 P  Q is translated to English as P implies to Q, or if P then Q. P  Q is translated to English as P is equivalent to Q. Using P Q we can infer new knowledge from old. For example: If P->Q  Q->R then P->R.  Propositional Logic Limitation Can only handle true or false values. Entire Proposition is represented as single symbol. – We can not talk about objects that have properties (height, width, size, …) and relation between objects. It dose not support changes to the knowledge base easily.  Propositional Logic Limitation It is not expressive and lack the ability to talk about specifics. – For example, let us say we have a vacuum cleaner, and we have thousands of locations, and we want to say that these locations are free of dirt. – Then we need to define a conjunction of thousands of logical propositions for that. – There is no way to have a single sentence to define that, saying that all the locations are clean at once. Those propositional logic limitations can be handled by First Order Logic (FOL). 1. Logic based representation First Order Logic (FOL) In first order logic we have relations about things in the world, objects and functions on those objects. What we can believe about those relations is that they are true or false or unknown. This is an extension of propositional logic in which all we have was facts about the world, and we can belief that these facts can be true, false or unknown.  //First Order Logic Constructs Constants are objects: john, apples Predicates are properties and relations: – likes(john, apples) Functions transform objects: – likes(john, fruit_of(apple_tree)) Variables represent any object: likes(X, apples) Quantifiers qualify values of variables – True for all objects (Universal): X. likes(X, apples) – Exists at least one object (Existential): X. likes(X, apples)  First Order Logic Syntax Examples: – x person(x) means: there exist x, that is a person. – x person(x)  x (knows(x, salem)  knows(x, ahmed)). Means: For all people, there exists someone that Knows salem or ahmed. Note that sometimes abbreviation omits the quantifier, when we do that, you can just assume that it means for all  that is left at just as a short cut.  First Order Logic Syntax Example: “Every rose has a thorn” This is how to read it: For all X if (X is a rose) Then there exists Y such that (X has Y) and (Y is a thorn) First Order Logic and Prolog What is Prolog? It is a declarative programming tool that we can use to write artificial intelligent programs Prolog is Programming in Logic Prolog is based on First Order Logic syntax. Prolog consists of: – Facts – Rules. Artificial Intelligence 15 12:10 AM  Prolog Example Consider the following FOL statements: – All men are mortal: X (man(X)mortal(X)). – Socrates is a man: man(socrates). – So, Socrates is mortal: mortal(socrates). Here is the corresponding Prolog statements: mortal(X) :- man(X). man(socrates). Here is sample program run: ?mortal(socrates). Yes ?- Artificial Intelligence 16 12:10 AM  2. Procedural representation Production Rules Rule set of pairs – “if condition then action” Match-resolve-act cycle – Match: Agent checks if each rule’s condition holds – Resolve: Multiple production rules may fire at once (conflict set) Agent must choose rule from set (conflict resolution) – Act: If so, rule “fires” and the action is carried out Working memory: – rule can write knowledge to working memory – knowledge may match and fire other rules  Production Rules Example Fact entering KB RULE #1: if patient salt intake is high then blood pressure is likely to be high Rule fires RULE #2: if blood pressure is likely to be high then risk of heart failure is high new generated Facts into KB  3. Network Representations Semantic Networks Semantic networks where nodes represents objects Semantic networks is a hierarchal network of relationships of objects can be developed using a semantic network Inheritance of properties is very similar to objects in OOP. Inheritance is a mechanism for insuring that an object is not represented by more nodes or links than necessary.  Semantic Networks Example: Draw a semantic network for the following KB: Fact-1: Canary is a bird Fact-2: Birds can fly Fact-3: Canary is Yellow in colour Fact-4: Birds have wings  Semantic Networks Wings Fly Can have Birds is-a Canary is a Yellow member of Colour Canary class of objects called “Birds” Can we deduce any new knowledge?  Semantic Networks Wings Fly Can have Birds is-a Yellow Colour Canary Yes, two new facts could be added to the KB: Canary has wings & Canary can  Semantic Networks Graphical representation (a graph) – Links indicate subset, member, relation,... Equivalent to logical statements (usually FOL) – Easier to understand than FOL? Example: natural language understanding – Sentences with same meaning have same graphs 4. Structural representation Frame Representations A frame is a data structure with typical knowledge about a particular object or concept. Frames, first proposed by Marvin Minsky in the 1970s (Minsky, 1975), are used to capture and represent knowledge in a frame-based expert system.  Frame Representation More natural support of values then semantic nets (each slots has constraints describing legal values that a slot can take) Can be easily implemented using oop techniques Inheritance is easily controlled