Artificial Intelligence - Chapter 3: Knowledge Representation PDF

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 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 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 11 12:46 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  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 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