Chapter 2-The Representation of Knowledge.ppt

1、Chapter 2: The Representation of Knowledge,Expert Systems: Principles and Programming, Fourth Edition,Expert Systems: Principles and Programming, Fourth Edition,2,What is the study of logic?,Logic is the study of making inferences given a set of facts, we attempt to reach a true conclusion. An examp

2、le of informal logic is a courtroom setting where lawyers make a series of inferences hoping to convince a jury / judge . Formal logic (symbolic logic) is a more rigorous approach to proving a conclusion to be true / false.,Expert Systems: Principles and Programming, Fourth Edition,3,Why is Logic Im

3、portant,We use logic in our everyday lives “should I buy this car”, “should I seek medical attention”. People are not very good at reasoning because they often fail to separate word meanings with the reasoning process itself. Semantics refers to the meanings we give to symbols.,Expert Systems: Princ

4、iples and Programming, Fourth Edition,4,The Goal of Expert Systems,We need to be able to separate the actual meanings of words with the reasoning process itself. We need to make inferences w/o relying on semantics. We need to reach valid conclusions based on facts only.,Expert Systems: Principles an

5、d Programming, Fourth Edition,5,Knowledge vs. Expert Systems,Knowledge representation is key to the success of expert systems. Expert systems are designed for knowledge representation based on rules of logic called inferences. Knowledge affects the development, efficiency, speed, and maintenance of

6、the system.,Expert Systems: Principles and Programming, Fourth Edition,6,Arguments in Logic,An argument refers to the formal way facts and rules of inferences are used to reach valid conclusions.The process of reaching valid conclusions is referred to as logical reasoning.,Expert Systems: Principles

7、 and Programming, Fourth Edition,7,How is Knowledge Used?,Knowledge has many meanings data, facts, information. How do we use knowledge to reach conclusions or solve problems? Heuristics refers to using experience to solve problems using precedents. Expert systems may have hundreds / thousands of mi

8、cro-precedents to refer to.,Expert Systems: Principles and Programming, Fourth Edition,8,Epistemology,Epistemology is the formal study of knowledge .Concerned with nature, structure, and origins of knowledge.,Expert Systems: Principles and Programming, Fourth Edition,9,Categories of Epistemology,Exp

9、ert Systems: Principles and Programming, Fourth Edition,10,A Priori Knowledge,“That which precedes”Independent of the sensesUniversally trueCannot be denied without contradiction,Expert Systems: Principles and Programming, Fourth Edition,11,A Posteriori Knowledge,“That which follows”Derived from the

10、 sensesNow always reliableDeniable on the basis of new knowledge w/o the necessity of contradiction,Expert Systems: Principles and Programming, Fourth Edition,12,Procedural Knowledge,Knowing how to do something:Fix a watch Install a window Brush your teeth Ride a bicycle,Expert Systems: Principles a

11、nd Programming, Fourth Edition,13,Declarative Knowledge,Knowledge that something is true or falseUsually associated with declarative statementsE.g., “Dont touch that hot wire.”,Expert Systems: Principles and Programming, Fourth Edition,14,Tacit Knowledge,Unconscious knowledgeCannot be expressed by l

12、anguageE.g., knowing how to walk, breath, etc.,Expert Systems: Principles and Programming, Fourth Edition,15,Knowledge in Rule-Based Systems,Knowledge is part of a hierarchy.Knowledge refers to rules that are activated by facts or other rules.Activated rules produce new facts or conclusions.Conclusi

13、ons are the end-product of inferences when done according to formal rules.,Expert Systems: Principles and Programming, Fourth Edition,16,Expert Systems vs. Humans,Expert systems infer reaching conclusions as the end product of a chain of steps called inferencing when done according to formal rules.H

14、umans reason,Expert Systems: Principles and Programming, Fourth Edition,17,Expert Systems vs. ANS,ANS does not make inferences but searches for underlying patterns.Expert systems Draw inferences using facts Separate data from noise Transform data into information Transform information into knowledge

15、Expert Systems: Principles and Programming, Fourth Edition,18,Metaknowledge,Metaknowledge is knowledge about knowledge and expertise.Most successful expert systems are restricted to as small a domain as possible.In an expert system, an ontology is the metaknowledge that describes everything known a

16、bout the problem domain. Wisdom is the metaknowledge of determining the best goals of life and how to obtain them.,Expert Systems: Principles and Programming, Fourth Edition,19,Figure 2.2 The Pyramid of Knowledge,Expert Systems: Principles and Programming, Fourth Edition,20,Productions,A number of k

17、nowledge-representation techniques have been devised:Rules Semantic nets Frames Scripts Logic Conceptual graphs,Expert Systems: Principles and Programming, Fourth Edition,21,Figure 2.3 Parse Tree of a Sentence,Expert Systems: Principles and Programming, Fourth Edition,22,Semantic Nets,A classic repr

18、esentation technique for propositional information Propositions a form of declarative knowledge, stating facts (true/false) Propositions are called “atoms” cannot be further subdivided. Semantic nets consist of nodes (objects, concepts, situations) and arcs (relationships between them).,Expert Syste

19、ms: Principles and Programming, Fourth Edition,23,Common Types of Links,IS-A relates an instance or individual to a generic classA-KIND-OF relates generic nodes to generic nodes,Expert Systems: Principles and Programming, Fourth Edition,24,Figure 2.4 Two Types of Nets,Expert Systems: Principles and

20、Programming, Fourth Edition,25,Figure 2.6: General Organization of a PROLOG System,Expert Systems: Principles and Programming, Fourth Edition,26,PROLOG and Semantic Nets,In PROLOG, predicate expressions consist of the predicate name, followed by zero or more arguments enclosed in parentheses, separa

21、ted by commas.Example: mother(becky,heather) means that becky is the mother of heather,Expert Systems: Principles and Programming, Fourth Edition,27,PROLOG Continued,Programs consist of facts and rules in the general form of goals. General form: p:- p1, p2, , pNp is called the rules head and the pi

22、represents the subgoals Example: spouse(x,y) :- wife(x,y)x is the spouse of y if x is the wife of y,Expert Systems: Principles and Programming, Fourth Edition,28,Object-Attribute-Value Triple,One problem with semantic nets is lack of standard definitions for link names (IS-A, AKO, etc.).The OAV trip

23、let can be used to characterize all the knowledge in a semantic net.,Expert Systems: Principles and Programming, Fourth Edition,29,Problems with Semantic Nets,To represent definitive knowledge, the link and node names must be rigorously defined.A solution to this is extensible markup language (XML)

24、and ontologies.Problems also include combinatorial explosion of searching nodes, inability to define knowledge the way logic can, and heuristic inadequacy.,Expert Systems: Principles and Programming, Fourth Edition,30,Schemata,Knowledge Structure an ordered collection of knowledge not just data. Sem

25、antic Nets are shallow knowledge structures all knowledge is contained in nodes and links. Schema is a more complex knowledge structure than a semantic net. In a schema, a node is like a record which may contain data, records, and/or pointers to nodes.,Expert Systems: Principles and Programming, Fou

26、rth Edition,31,Frames,One type of schema is a frame (or script time-ordered sequence of frames). Frames are useful for simulating commonsense knowledge. Semantic nets provide 2-dimensional knowledge; frames provide 3-dimensional. Frames represent related knowledge about narrow subjects having much d

27、efault knowledge.,Expert Systems: Principles and Programming, Fourth Edition,32,Frames Continued,A frame is a group of slots and fillers that defines a stereotypical object that is used to represent generic / specific knowledge. Commonsense knowledge is knowledge that is generally known. Prototypes

28、are objects possessing all typical characteristics of whatever is being modeled. Problems with frames include allowing unrestrained alteration / cancellation of slots.,Expert Systems: Principles and Programming, Fourth Edition,33,Logic and Sets,Knowledge can also be represented by symbols of logic.L

29、ogic is the study of rules of exact reasoning inferring conclusions from premises.Automated reasoning logic programming in the context of expert systems.,Expert Systems: Principles and Programming, Fourth Edition,34,Figure 2.8 A Car Frame,Expert Systems: Principles and Programming, Fourth Edition,35

30、Forms of Logic,Earliest form of logic was based on the syllogism developed by Aristotle. Syllogisms have two premises that provide evidence to support a conclusion. Example: Premise: All cats are climbers. Premise: Garfield is a cat. Conclusion: Garfield is a climber.,Expert Systems: Principles and

31、 Programming, Fourth Edition,36,Venn Diagrams,Venn diagrams can be used to represent knowledge. Universal set is the topic of discussion. Subsets, proper subsets, intersection, union , contained in, and complement are all familiar terms related to sets. An empty set (null set) has no elements.,Exper

32、t Systems: Principles and Programming, Fourth Edition,37,Figure 2.13 Venn Diagrams,Expert Systems: Principles and Programming, Fourth Edition,38,Syllogism 三段論法,Premise: All men are mortalPremise: Socrates is a manConclusion: Socrates is mortalOnly the form is important.Premise: All X are YPremise: Z

33、 is a XConclusion: Z is a Y,Expert Systems: Principles and Programming, Fourth Edition,39,Categorical Syllogism,Syllogism: a valid deductive argument having two premises and a conclusion.major premise: All M are Pminor premise: All S is MConclusion: All S is PM middle termP major termS minor term,Ex

34、pert Systems: Principles and Programming, Fourth Edition,40,Categorical Statements,Expert Systems: Principles and Programming, Fourth Edition,41,MoodAAA-1 EAE-1 IAI-4All M is P No M is P Some P is MAll S is M All S is M All M is SAll S is P No S is P Some S is P,Expert Systems: Principles and Progra

35、mming, Fourth Edition,42,Propositional Logic,Formal logic is concerned with syntax of statements, not semantics.Syllogism: All goons are loons. Zadok is a goon. Zadok is a loon.The words may be nonsense, but the form is correct this is a “valid argument.”,Expert Systems: Principles and Programming,

36、Fourth Edition,43,Figure 2.14 Intersecting Sets,Expert Systems: Principles and Programming, Fourth Edition,44,Boolean Logic,Defines a set of axioms consisting of symbols to represent objects / classes. Defines a set of algebraic expressions to manipulate those symbols. Using axioms, theorems can be

37、constructed. A theorem can be proved by showing how it is derived from a set of axioms.,Expert Systems: Principles and Programming, Fourth Edition,45,Features of Propositional Logic,Concerned with the subset of declarative sentences that can be classified as true or false. We call these sentences “s

38、tatements” or “propositions”. Paradoxes statements that cannot be classified as true or false. Open sentences statements that cannot be answered absolutely.,Expert Systems: Principles and Programming, Fourth Edition,46,Features Continued,Compound statements formed by using logical connectives (e.g.,

39、 AND, OR, NOT, conditional, and biconditional) on individual statements.Material implication p q states that if p is true, it must follow that q is true.Biconditional p q states that p implies q and q implies p.,Expert Systems: Principles and Programming, Fourth Edition,47,Features Continued,Tautolo

40、gy a statement that is true for all possible cases.Contradiction a statement that is false for all possible cases.Contingent statement a statement that is neither a tautology nor a contradiction.,Expert Systems: Principles and Programming, Fourth Edition,48,Truth Tables,Expert Systems: Principles an

41、d Programming, Fourth Edition,49,Rule of Inference,Modus ponens, way assertdirect reasoning, law of detachment assuming the antecedentModus tollens, way denyindirect reasoning, law of contrapositionassuming the antecedent,Expert Systems: Principles and Programming, Fourth Edition,50,Modus Ponens,If

42、there is power, the computer will work There is power - The computer will workA B p, p -q; qA -B,Expert Systems: Principles and Programming, Fourth Edition,51,Modus tollens,p q conditional p - qq converse q - p- inverse p - q p contrapositiveq - p,Expert Systems: Principles and Programming, Fourth E

43、dition,52,Formal Logic Proof,Chip prices rise only if the yen rises. The yen rises only if the dollar falls and if the dollar falls then the yen rises. Since chip prices have risen,the dollar must have fallen.C Y C = chip prices rise (Y D) (D Y) Y = yen rises C D = dollar falls - D,Expert Systems: P

44、rinciples and Programming, Fourth Edition,53,Formal Logic Proof,C Y (Y D) (D Y) C D1. C Y premise 2. (Y D) (D Y) premise3. C 4. Y = D 2 Equivalence5. C D 1 Substitution6. D 3,5 modus ponens,Expert Systems: Principles and Programming, Fourth Edition,54,Resolution,Normal form Conjunctive normal form(P

45、1vP2v)(Q1vQ2)(Z1vZ2) Kowalski clausal formA1, A2, ., An B1, B2, ., Bm Horn clauseA1, A2, ., An B,Expert Systems: Principles and Programming, Fourth Edition,55,Method of Contradiction,A v B (AvB)(AvB)A v B A v (BB)- AA,Expert Systems: Principles and Programming, Fourth Edition,56,Forward Reasoning,T:

46、 A B B C CONCLUSION?C D A Resolve by modus ponens,Expert Systems: Principles and Programming, Fourth Edition,57,Backward Reasoning,What if T is very large?T may support all kinds of inferenceswhich have nothing to do withthe proof of our goalCombinational explosion Use Backward Reasoning,Expert Syst

47、ems: Principles and Programming, Fourth Edition,58,Resolution Refutation,To refute something is to prove it false Refutation complete:Resolution refutation will terminate ina finite steps if there is a contradiction Example: Given the argumentA BB CC D-A D,Expert Systems: Principles and Programming,

48、 Fourth Edition,59,Example,A BB CC D-A DTo prove that A D is a theorem by resolution refutation:A D equ A v D convert to disjunction form (A v D) equ A D negate the conclusion 3. A B equ A v B B C equ B v C C D equ C v D (A v B) (B v C ) (C v D) A D resolution= nil false,Expert Systems: Principles and Programming, Fourth Edition,60,Method of Contradiction,A v B (AvB)(AvB)A v B A v (BB)- AA,Expert Systems: Principles and Programming, Fourth Edition,