Knowledge Representation and Reasoning Intelligent agents should have capacity for: Perceiving: that is, acquiring information from environment, Knowledge Representation: that is, representing its understanding of the world, Reasoning: that is, inferring the implications of what it knows and of the choices it has, and Acting: that is, choosing what it want to do and carry it out.

PowerPoint Presentation:

Motivation Representation of knowledge and the reasoning process are central to the entire field of artificial intelligence. Different knowledge representation schemes may be appropriate depending on tasks and circumstances KBs are useless without the ability to represent knowledge

PowerPoint Presentation:

A knowledge-base is a set of sentences. Each sentence is expressed in a language (KRL). Inferencing/reasoning: New sentences (TELL & ASK ) Inference must obey the primary requirement that the new sentences should follow logically from the previous ones. Logic

PowerPoint Presentation:

KB Agent Program function KB- Agent (percepts) returns an action static: KB, a knowledge base t, a counter, initially 0, indicating time TELL (KB, MAKE-P E R C E P T - S E N T E N C E (Percept, t)), action ASK (KB, MAKE-ACTION- QUERY(^)) TELL (KB, MAKE-ACTION-SENTENCE (action, t)), t = t + l return action

PowerPoint Presentation:

Objectives know the basic principles and concepts for knowledge representation knowledge - information - data meaning be familiar with the most frequently used knowledge representation methods logic, rules, semantic nets, schemata understand the relationship between knowledge representation and reasoning syntax, semantics

PowerPoint Presentation:

Knowledge Pyramid Noise Data Information Knowledge Meta-

PowerPoint Presentation:

Knowledge Representation Methods Production Rules Semantic Nets Schemata and Frames Logic

PowerPoint Presentation:

Production Rules frequently used to formulate the knowledge in expert systems a grammar is a complete, unambiguous set of production rules for a specific language Condition-Action Pairs IF this condition (or premise or antecedent) occurs, THEN some action (or result, or conclusion, or consequence) will (or should) occur IF the stop light is red AND you have stopped, THEN a right turn is OK

PowerPoint Presentation:

10 Forms of Rules IF premise, THEN conclusion IF your income is high, THEN your chance of being audited by the IT is high Conclusion, IF premise Your chance of being audited is high, IF your income is high

PowerPoint Presentation:

11 Inclusion of ELSE IF your income is high, OR your deductions are unusual, THEN your chance of being audited by the IT is high, OR ELSE your chance of being audited is low More Complex Rules IF credit rating is high AND salary is more than $30,000, OR assets are more than $75,000, AND pay history is not "poor," THEN approve a loan up to $10,000, and list the loan in category "B.” Action part may have more information: THEN "approve the loan" and "refer to an agent"

PowerPoint Presentation:

Relationships without relationships, knowledge is an unrelated collection of facts relationships express structure in the collection of facts this allows the generation of meaningful new knowledge generation of new facts generation of new relationships

PowerPoint Presentation:

Relationships cntd.. relationships can be arbitrarily defined by the knowledge engineer allows great flexibility for reasoning, the inference mechanism must know how relationships can be used to generate new knowledge inference methods may have to be specified for every relationship frequently used relationships IS-A relates an instance (individual node) to a class (generic node) AKO (a-kind-of) relates one class (subclass) to another class (superclass)

PowerPoint Presentation:

Advantages of Production Rules Simple and easy to understand Straightforward implementation in computers possible Formal foundations for some variants Easy to derive inference and explanations Easy to modify and maintain Rules are frequently independent

PowerPoint Presentation:

Problems with Production Rules simple implementations are very inefficient some types of knowledge are not easily expressed in such rules complex knowledge requires many rules large sets of rules become difficult to understand and maintain Search limitations in systems with many rules

PowerPoint Presentation:

16 Knowledge and Inference Rules Common Types of Rules Knowledge rules, or declarative rules, state all the facts and relationships about a problem Inference rules, or procedural rules, advise on how to solve a problem, given that certain facts are known Inference rules contain rules about rules ( metarules ) Knowledge rules are stored in the knowledge base Inference rules become part of the inference engine

PowerPoint Presentation:

17

PowerPoint Presentation:

Semantic Networks graphical representation for propositional information originally developed by M. R. Quillian as a model for human memory labeled, directed graph nodes represent objects, concepts, or situations links represent relationships the label indicates the type of the relationship is-a has-a

PowerPoint Presentation:

19 Semantic networks can show inheritance Semantic Nets - visual representation of relationships Can be combined with other representation methods

PowerPoint Presentation:

20 Semantic Network Example Joe Boy Kay Woman Food Human Being School Has a child Needs Goes to Is a Is a Is a Is a

PowerPoint Presentation:

Frame represents related knowledge about a subject frames are organized hierarchically allows the use of inheritance knowledge is usually organized according to cause and effect relationships slots can contain all kinds of items rules, facts, images, video, comments, debugging info, questions, hypotheses, other slots can also have procedural attachments procedures that are invoked in specific situations involving a particular slot on creation, modification, removal of the slot value

PowerPoint Presentation:

Overview of Frame Structure two basic elements: slots and facets (fillers, values, etc.); descriptive slots contain declarative information or data (static knowledge) procedural attachments contain functions which can direct the reasoning process (dynamic knowledge) e.g., "activate a certain rule if a value exceeds a given level" data-driven, event-driven pointers to related frames/scripts - can be used to transfer control to a more appropriate frame

PowerPoint Presentation:

Simple Frame Example Slot Name Filler name Max height small weight Average profession warrior armor helmet intelligence very high marital status single

PowerPoint Presentation:

Slots each slot contains one or more facets facets may take the following forms: values default Range if-added procedural attachment which specifies an action to be taken when a value in the slot is added or modified (data-driven, event-driven or bottom-up reasoning) if-needed procedural attachment which triggers a procedure which goes out to get information which the slot doesn't have (expectation-driven; top-down reasoning) other may contain frames, rules, semantic networks, or other types of knowledge

PowerPoint Presentation:

Restaurant Frame Example generic template for restaurants different types default values script for a typical sequence of activities at a restaurant

PowerPoint Presentation:

Generic Restaurant Frame Generic RESTAURANT Fram e Types : range : (Cafeteria, Fast-Food, Seat-Yourself, Wait-To-Be-Seated) default : Seat-Yourself if-needed : IF reservations-made THEN Wait-To-Be-Seated, OTHERWISE Seat-Yourself. Name : if-needed : (Look at the MENU) Food-Style : range : (Burgers, Chinese, American, Seafood, French) default : American Times-of-Operation : range : a Time-of-Day default : open evenings except Mondays Payment-Form : range : (Cash, Credit Card, Check, Washing-Dishes-Script) Event-Sequence : default : Eat-at-Restaurant Script Alternatives :

PowerPoint Presentation:

Restaurant Script EAT-AT-RESTAURANT Script Props : (Restaurant, Money, Food, Menu, Tables, Chairs) Roles : (Hungry-Persons, Wait-Persons) Point-of-View : Hungry-Persons Time-of-Occurrence : (Times-of-Operation of Restaurant) Place-of-Occurrence : (Location of Restaurant) Event-Sequence : first : Enter-Restaurant Script then : if (Wait-To-Be-Seated-Sign or Reservations) then Get- Waiters Attention Script then : Please-Be-Seated Script then : Order-Food-Script then : Eat-Food-Script unless (Long-Wait) when Exit-Restaurant-Angry Script then : if (Food-Quality is good) then Compliments-To-The-Chef Script then : Pay-For-It-Script finally : Leave-Restaurant Script

PowerPoint Presentation:

Frame Advantages important for many applications similar to human knowledge organization easier to understand than logic or rules very flexible

PowerPoint Presentation:

Summary Knowledge Representation knowledge representation is very important for knowledge-based system popular knowledge representation schemes are rules, semantic nets, schemata (frames, scripts), logic the selected knowledge representation scheme should have appropriate inference methods to allow reasoning a balance must be found between effective representation, efficiency, understandability

PowerPoint Presentation:

Logic

PowerPoint Presentation:

Outline Knowledge-based agents Logic in general - models and entailment Propositional logic Equivalence, validity, satisfiability Inference rules and theorem proving resolution horn clause forward chaining backward chaining

PowerPoint Presentation:

Knowledge bases Knowledge base = set of sentences in a formal language Declarative approach to building an agent (or other system): Tell what it needs to know Then it can Ask itself what to do - answers should follow from the KB Agents can be viewed at the knowledge level i.e., what they know, regardless of how implemented Or at the implementation level i.e., data structures in KB and algorithms that manipulate them

PowerPoint Presentation:

A simple knowledge-based agent The agent must be able to: Percept, Represent, Reasoning, Action.

PowerPoint Presentation:

Logic in general Logics are formal languages for representing information such that conclusions can be drawn Syntax defines the sentences in the language Semantics define the "meaning" of sentences; i.e., define truth of a sentence in a world E.g., the language of arithmetic x+2 ≥ y is a sentence; x2+y > {} is not a sentence x+2 ≥ y is true iff the number x+2 is no less than the number y x+2 ≥ y is true in a world where x = 7, y = 1 x+2 ≥ y is false in a world where x = 0, y = 6

PowerPoint Presentation:

Reasoning process of constructing new configurations (sentences) from old ones proper reasoning ensures that the new configurations represent facts that actually follow from the facts that the old configurations represent this relationship is called entailment and can be expressed as KB |= alpha knowledge base KB entails the sentence alpha

PowerPoint Presentation:

Inference Methods an inference procedure can do one of two things: given a knowledge base KB, it can derive new sentences that are (supposedly) entailed by KB KB |- ==> KB |= given a knowledge base KB and another sentence alpha, it can report whether or not alpha is entailed by KB KB ==> KB |= an inference procedure that generates only entailed sentences is called sound or truth-preserving the record of operation of a sound inference procedure is called a proof an inference procedure is complete if it can find a proof for any sentence that is entailed

PowerPoint Presentation:

Big Ideas Logic is a great knowledge representation language for many AI problems Propositional logic is the simple foundation and fine for some AI problems First order logic (FOL) is much more expressive as a KR language and more commonly used in AI

PowerPoint Presentation:

Propositional logic Logical constants : true, false Propositional symbols : P, Q,... ( atomic sentences ) Wrapping parentheses : ( … ) Sentences are combined by connectives : and [conjunction] or [disjunction] implies [implication / conditional] is equivalent [biconditional] not [negation] Literal : atomic sentence or negated atomic sentence P, P

PowerPoint Presentation:

Propositional logic: Syntax Propositional logic is the simplest logic – illustrates basic ideas The proposition symbols P 1 , P 2 etc are sentences If S is a sentence, S is a sentence ( negation ) If S 1 and S 2 are sentences, S 1 S 2 is a sentence ( conjunction ) If S 1 and S 2 are sentences, S 1 S 2 is a sentence ( disjunction ) If S 1 and S 2 are sentences, S 1 S 2 is a sentence ( implication ) If S 1 and S 2 are sentences, S 1 S 2 is a sentence ( biconditional )

PowerPoint Presentation:

Propositional logic: Semantics Each model specifies true/false for each proposition symbol E.g. P 1,2 P 2,2 P 3,1 false true false With these symbols, 8 possible models, can be enumerated automatically. S is true iff S is false S 1 S 2 is true iff S 1 is true and S 2 is true S 1 S 2 is true iff S 1 is true or S 2 is true S 1 S 2 is true iff S 1 is false or S 2 is true i.e., is false iff S 1 is true and S 2 is false S 1 S 2 is true iff S 1 S 2 is true and S 2 S 1 is true Simple recursive process evaluates an arbitrary sentence, e.g., P 1,2 (P 2,2 P 3,1 ) = true ( true false ) = true true = true Rules for evaluating truth with respect to a model m:

PowerPoint Presentation:

On the implies connective: P Q Note that is a logical connective So P Q is a logical sentence and has a truth value, i.e., is either true or false If we add this sentence to the KB, it can be used by an inference rule, Modes Ponens , to derive/infer/prove Q if P is also in the KB Given a KB where P=True and Q=True, we can also derive/infer/prove that P Q is True

PowerPoint Presentation:

P Q When is P Q true? Check all that apply P=Q=true P=Q=false P=true, Q=false P=false, Q=true

PowerPoint Presentation:

P Q When is P Q true? Check all that apply P=Q=true P=Q=false P=true, Q=false P=false, Q=true We can get this from the truth table for Note: in FOL it’s much harder to prove that a conditional true. ✔ ✔ ✔

PowerPoint Presentation:

Truth tables Truth tables for the five logical connectives Example of a truth table used for a complex sentence Truth tables are used to define logical connectives and to determine when a complex sentence is true given the values of the symbols in it P H P v H (P v H) ^ ¬ H ((P v H) ^ ¬ H) => P

PowerPoint Presentation:

Some terms The meaning or semantics of a sentence determines its interpretation Given the truth values of all symbols in a sentence, it can be “evaluated” to determine its truth value (True or False) A model for a KB is a possible world – an assignment of truth values to propositional symbols that makes each sentence in the KB True

PowerPoint Presentation:

Examples of PL sentences (P Q) R “If it is hot and humid, then it is raining” Q P “If it is humid, then it is hot” Q “It is humid.” We’re free to choose better symbols, btw: Ho = “It is hot” Hu = “It is humid” R = “It is raining”

PowerPoint Presentation:

Model for a KB Let the KB be [P Q R, Q P] What are the possible models? Consider all possible assignments of T|F to P, Q and R and check truth tables FFF: OK FFT: OK FTF: NO FTT: NO TFF: OK TFT: OK TTF: NO TTT: OK If KB is [P Q R, Q P, Q], then the only model is TTT P: it’s hot Q: it’s humid R: it’s raining

PowerPoint Presentation:

Inference KB ├ i α = sentence α can be derived from KB by procedure i Soundness : i is sound if whenever KB ├ i α, it is also true that KB ╞ α Completeness : i is complete if whenever KB ╞ α, it is also true that KB ├ i α Preview: we will define a logic (first-order logic) which is expressive enough to say almost anything of interest, and for which there exists a sound and complete inference procedure. That is, the procedure will answer any question whose answer follows from what is known by the KB .

PowerPoint Presentation:

Inference rules Logical inference creates new sentences that logically follow from a set of sentences (KB) An inference rule is sound if every sentence X it produces when operating on a KB logically follows from the KB i.e., inference rule creates no contradictions An inference rule is complete if it can produce every expression that logically follows from (is entailed by) the KB.

PowerPoint Presentation:

Resolution Resolution is a valid inference rule producing a new clause implied by two clauses containing complementary literals A literal is an atomic symbol or its negation, i.e., P, ~P Amazingly, this is the only interference rule you need to build a sound and complete theorem prover The resolution rule was discovered by Alan Robinson (CS, U. of Syracuse) in the mid 60s

PowerPoint Presentation:

Resolution A KB is actually a set of sentences all of which are true, i.e., a conjunction of sentences. To use resolution, put KB into conjunctive normal form (CNF), A sentence expressed as a conjunction of disjunctions of literals is said to be in conjunctive normal form. Any wff can be converted to CNF by using the following equivalences, 1. A ↔ B = (A->B) ∧ (B->A) 2. A →B = ￢ A ∨ B 3. ￢ (A ∧ B) = ￢ A ∨ ￢ B 4. ￢ (A ∨ B) = ￢ A ∧ ￢ B 5. ￢￢ A = A 6. A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C)

PowerPoint Presentation:

Logical equivalence Two sentences are logically equivalent iff true in same models: α ≡ ß iff α╞ β and β ╞ α

PowerPoint Presentation:

09/04/12 (A→B)→C ￢ (A→B) ∨ C (2) ￢ ( ￢ A ∨ B) ∨ C (3) (A ∧ ￢ B) ∨ C (4) (A ∨ C) ∧ ( ￢ B ∨ C) (6) (A→(B ∧ C)) ∧ ((B ∧ C)→A) (1) (￢A ∨ (B ∧ C)) ∧ (￢(B ∧ C) ∨ A) (2) (￢A ∨ (B ∧ C)) ∧ (￢B ∨ ￢C ∨ A) (3) (￢A ∨ B) ∧ (￢A ∨ C) ∧ (￢B ∨ ￢C ∨ A) (6) A further example follows: A↔ (B ∧ C) For example, we will convert (A →B)→C to CNF:

PowerPoint Presentation:

Resolution algorithm

PowerPoint Presentation:

A ∨ B ￢B ∨ C A ∨ C Resolution Rule ￢ A → B B → C ￢ A → C Transitive Implication This can be applied to wff ’s in clause form in WFF: clauses, consist of literal L and ￢ L, then these two clauses can be combined together, {(A,B),( ￢B,C )} {(A,C)} Example {(A, B, C), D, (￢A, D, E), (￢D, F)} ￢ L can be removed from those clauses.

PowerPoint Presentation:

Horn sentences A Horn sentence or Horn clause has the form: P1 P2 P3 ... Pn Qm where n>=0, m in{0,1} Note: a conjunction of 0 or more symbols to left of and 0-1 symbols to right A Horn clause, or Horn sentence, is a clause that has, at most, one positive literal. Hence, the following Horn clause takes the following form: A ∨ ￢B ∨ ￢C ∨ ￢D ∨ ￢E can be written as: B ∧ C ∧ D ∧ E→A In Prolog: can be written as A :− B, C, D, E (P Q) = ( P Q)

PowerPoint Presentation:

Horn clauses can take three forms: Clause with one positive literal, and one or more negative literals is called a rule relation. A ∨ ￢B ∨ ￢C ∨ ￢D ∨ ￢E A clause with no negative literals is called a fact: A :− Finally, a clause with no positive literal is called a goal, or a headless clause: :− B, C, D, E Horn sentences

PowerPoint Presentation:

Forward and backward chaining Horn Form (restricted) KB = conjunction of Horn clauses Horn clause = proposition symbol; or (conjunction of symbols) symbol E.g., C (B A) (C D B) Modus Ponens (for Horn Form): complete for Horn KBs α 1 , … ,α n , α 1 … α n β Can be used with forward chaining or backward chaining . These algorithms are very natural and run in linear time. β

PowerPoint Presentation:

Forward chaining Idea: fire any rule whose premises are satisfied in the KB , add its conclusion to the KB , until query is found

PowerPoint Presentation:

Forward chaining algorithm Forward chaining is sound and complete for Horn KB

PowerPoint Presentation:

Forward chaining example

PowerPoint Presentation:

Forward chaining example

PowerPoint Presentation:

Forward chaining example

PowerPoint Presentation:

Forward chaining example

PowerPoint Presentation:

Forward chaining example

PowerPoint Presentation:

Forward chaining example

PowerPoint Presentation:

Forward chaining example

PowerPoint Presentation:

Forward chaining example

PowerPoint Presentation:

Proof of completeness FC derives every atomic sentence that is entailed by KB FC reaches a fixed point where no new atomic sentences are derived Consider the final state as a model m , assigning true/false to symbols Every clause in the original KB is true in m a 1 … a k b Hence m is a model of KB If KB ╞ q , q is true in every model of KB , including m

PowerPoint Presentation:

Backward chaining Idea: work backwards from the query q : to prove q by BC, check if q is known already, or prove by BC all premises of some rule concluding q Avoid loops: check if new subgoal is already on the goal stack Avoid repeated work: check if new subgoal has already been proved true, or has already failed

PowerPoint Presentation:

Backward chaining example

PowerPoint Presentation:

Backward chaining example

PowerPoint Presentation:

Backward chaining example

PowerPoint Presentation:

Backward chaining example

PowerPoint Presentation:

Backward chaining example

PowerPoint Presentation:

Backward chaining example

PowerPoint Presentation:

Backward chaining example

PowerPoint Presentation:

Backward chaining example

PowerPoint Presentation:

Backward chaining example

PowerPoint Presentation:

Backward chaining example

PowerPoint Presentation:

Forward vs. backward chaining FC is data-driven , automatic, unconscious processing, e.g., object recognition, routine decisions May do lots of work that is irrelevant to the goal BC is goal-driven , appropriate for problem-solving, e.g., Where are my keys? How do I get into a PhD program? Complexity of BC can be much less than linear in size of KB

PowerPoint Presentation:

Hard satisfiability problems Consider random 3-CNF sentences. e.g., ( D B C) (B A C) ( C B E) (E D B) (B E C) m = number of clauses n = number of symbols Hard problems seem to cluster near m/n = 4.3 (critical point)

PowerPoint Presentation:

Summary Logical agents apply inference to a knowledge base to derive new information and make decisions Basic concepts of logic: syntax : formal structure of sentences semantics : truth of sentences wrt models entailment : necessary truth of one sentence given another inference : deriving sentences from other sentences soundness : derivations produce only entailed sentences completeness : derivations can produce all entailed sentences Wumpus world requires the ability to represent partial and negated information, reason by cases, etc. Resolution is complete for propositional logic Forward, backward chaining are linear-time, complete for Horn clauses Propositional logic lacks expressive power

You do not have the permission to view this presentation. In order to view it, please
contact the author of the presentation.

Send to Blogs and Networks

Processing ....

Premium member

Use HTTPs

HTTPS (Hypertext Transfer Protocol Secure) is a protocol used by Web servers to transfer and display Web content securely. Most web browsers block content or generate a “mixed content” warning when users access web pages via HTTPS that contain embedded content loaded via HTTP. To prevent users from facing this, Use HTTPS option.