Knowledge Representation

Presentation on theme: "Knowledge Representation"— Presentation transcript:

1 Knowledge Representation
Chapter　5 Knowledge Representation 知識表示法 Expert Systems sstseng

2 5.1 The meaning of Knowledge（知識）
　Knowledge（知識） ＋ Inference （推論）＝ Expert Systems（專家系統） 　Affect the development, efficiency, speed, and maintenance of 　　 　 expert systems 　epistemology: concerned with the nature, structure, and origin of knowledge 　a priori comes from the Latin and means “That which precedes” Epistemology(認知論) Philosophic Theories ARISTOTLE PLATO LOCKE MILL A Priori Knowledge e.g. all triangles have 180 degrees (considered to be universally true) A posteriori Knowledge e.g. the light is green 　a posteriori knowledge can be verified using 　sense experience Expert Systems sstseng

3 Classifications of knowledge（知識）
　Procedural Knowledge（程序性知識） 　　How to do something 　Declarative Knowledge（陳述性知識） 　　The truth of something 　　“Don’t put your fingers in a pot of boiling water” 　Tacit Knowledge（隱含知識） 　(Unconscious Knowledge) 　　Cannot be expressed explicitly －An example is how to move your hand －Walking or riding a bicycle －ANS is related to tacit knowledge Expert Systems sstseng

4 Analogy to Wirth’s classic expression
Algorithms + data structures = programs Knowledge + Inference = expert systems Expert Systems sstseng

5 Expert Systems sstseng
Levels Meta Knowledge (rules about rules) Knowledge (rules+facts) Information (facts) Data Noise Expert Systems sstseng

6 Expert Systems sstseng
The sequence of 12 numbers： Without knowledge. This entire sequence may appear to be noise. Rule 1：IF Rain THEN Bring Raincoat Rule 2：IF Rain THEN Bring Umbrella Meta Rule 1：Try Rule 2 First Meta Rule 2：IF Ride a motorcycle THEN 　　　　　　Try Rule 1 First Meta knowledge is knowledge about knowledge and expertise. －would specify which knowledge base was applicable. Expert Systems sstseng

7 Expert Systems sstseng
Representation（表示法） 　Backus - Naur form 　Ontology（本體論） 　Semantic Network（語意網路） 　Frames-based Knowledge（框架式知識） 　Case-based Knowledge（案例式知識） 　Rule-based Knowledge（規則式知識） 　Knowledge Object（知識物件） 　Logic（邏輯） Expert Systems sstseng

8 5.2 Backus - Naur form ( BNF )
　This notation is a meta language for defining the 　 　 syntax of a language 　Define the syntax of a language e.g. <sentence>::＝ <subject><verb><end-mark> <subject>::＝ I ｜ You｜We <verb> ::＝ left ｜came <end-mark> ::＝ . ｜ ?｜！ 　Parse Tree (derivation tree) sentence subject verb end-mark You came ? Expert Systems sstseng

9 Expert Systems sstseng
5.3 Ontology（本體論） Ontology一詞在90年代就開始被使用在人工智慧領域，描述知識的知識構成要素之間的關係。 Ontology的研究大致上可略為分為兩個方向： 針對特定的問題領域建立大量的Ontology 例如：建立某些領域詞彙的Ontology 研究Ontology的建構方法與表示方法 例如：利用XML（可延伸標記語言）或是RDF（資源描述格式） Expert Systems sstseng

10 Expert Systems sstseng
Ontology的發展主要是用來使知識分享和再用更為容易。 不同的研究對於Ontology的表示與描述有不同的方法，目前還未看到較一般化、通用的表示法 。 範例：使用RDF來描述適性化教材的Ontology Expert Systems sstseng

11 5.4 Semantic Network（語意網路） (Quillian 67 & 68)
　A classic AI representation technique used for 　 propositional information is sometimes called 　 Propositional Net 　A proposition(命題) is a statement that is either true or false 　A directed graph（有向圖形） 　Node（點） : 知識的組成元素或是種類 　Arc（有向線段） : 知識組成元素間的關 　「is a」 　「a kind of」 Expert Systems sstseng

12 Expert Systems sstseng
General Net San Francisco Chicago New York Indianapolis Los Angeles Houston Expert Systems sstseng

13 Expert Systems sstseng
A Semantic Net（語意網路） sister-of Carol David wife-of wife-of Ann Mark husband-of husband-of Father- of Mother- of father-of Mother-of wife-of Tom Susan husband-of father-of Mother-of John Expert Systems sstseng

14 Expert Systems sstseng
「is a」 and 「a kind of」 　「is a」 : 在Tail（有向線段尾段）所表示的知識物件屬 於Head（有向線段頭段）的知識類別中的一 個例子。 　「a kind of」(AKO) : 在Tail（有向線段尾段）的知識類別屬Head （有向線段頭段）所表示的知識類別。 　Superclass（父類別） and Subclass（子類別） 　Attribute, Value, Property 　Inheritance（繼承） Expert Systems sstseng

15 A Semantic Network with 「is a」 and 「a kind of」(AKO) Links
鴿子 鳥 動物 is a AKO has-property 飛 A Semantic Network with 「is a」 and 「a kind of」(AKO) Links Expert Systems sstseng

16 A Semantic Network with 「is a」 and 「a kind of」(AKO) Links
aircraft AKO AKO AKO round balloon Propeller driven jet has-shape AKO AKO AKO AKO AKO AKO ellipsoidal has-shape blimp special DC-3 DC-9 Concorde is a is a is a Goodyear Blimp Spirit of St. Louis Air Force 1 A Semantic Network with 「is a」 and 「a kind of」(AKO) Links Expert Systems sstseng

17 5.5 PROLOG and Semantic Nets（語意網路）
Essentials(本質、要素) of PROLOG Each of the statements above is a PROLOG predicate(述部) expression, or simply a predicate. 　Color(red).　　　　　　　　; red is a color 　father_of(Tom,John).　　　　 ; Tom is the father of John 　mother_of(Susan,John).　　　; Susan is the mother of John 　parents(Tom,Susan,John).　　 ; Tom and Susan are 　　　　　　　　　　　　　　 parents of John Expert Systems sstseng

18 Expert Systems sstseng
Predicates can also be expressed with relations such as the IS-A and HAS-A. 　is_a (red,color). 　has_a (John,father). 　has_a (John,mother). 　has_a (John,parents). Some additional predicates 　is_a (Tom,father). 　is_a (Susan,mother). 　is_a (Tom,parent). 　is_a (Susan,parent). Expert Systems sstseng

19 Expert Systems sstseng
Programs in PROLOG consist of facts and rules in the general form of goals. 　　　p:-p1,p2…pn. In which p is the rule’s head and the pi are the subgoals. The symbol,:-, is interpreted as an IF. parent (x,y) : - father (x,y). parent (x,y) : - mother(x,y). grandparent(x,y) :- parent (x,z) ,parent(z,y). and an ancestor can be defined as: 　(1) ancestor(x,y) :- parent(x,y). 　(2) ancestor(x,y) :- ancestor(x,z),ancestor(z,y). Expert Systems sstseng

20 General Organization of a PROLOG System
Predicate Database (Rules and Facts) Queries Answers Interpreter User General Organization of a PROLOG System Expert Systems sstseng

21 Expert Systems sstseng
　(3) parent (Ann,Mary). 　(4) parent (Ann,Susan). 　(5) parent (Mary,Bob). 　(6) parent (Susan,John). As another example, suppose the query is :-ancestor(Ann,John). The first ancestor rule(1) matches and X is set to Ann and Y is set to John. PROLOG now tries to match the body of (1), parent (Ann,John) with every parent statement. Expert Systems sstseng

22 Expert Systems sstseng
(1) is not true, the head cannot be true. 　Because(1) cannot be true, PROLOG then tries the 　 second ancestor statement (2) X is set to Ann and Y is set to John. Control structure of PROLOG is of the Markov algorithm type, in which searching for pattern matching is normally determined by the order in which the Horn clauses are entered. Expert Systems sstseng

23 5.6 Schema (plural schemas or schematas)
A semantic net（語意網路） is an example of a shallow knowledge（淺層知識） structure. A general term to describe a complex knowledge structure Focus on only relevant(有意義的) knowledge For examples：FRAME,SCRIPT Expert Systems sstseng

24 5.7 Frames-based Knowledge（框架式知識） (Minsky 75)
Suitable for related knowledge about a narrow subject with much default knowledge script－a time-ordered sequence of frames Slot(槽)：Attribute(屬性) 　Slot 值：Value Example a car frame Expert Systems sstseng

25 Expert Systems sstseng
Slot 值 Some frame-based tools (KEE) allow a wide range of items to be stored in slots an assigned value .a default value Rules .graphics Comments .debugging information questions for users .function procedural attachment .to other frame Expert Systems sstseng

26 Procedural Attachment
If – needed, if-added, if-removed Examples：Human Property Expert Systems sstseng

27 Expert Systems sstseng
Hierarchy Expert Systems sstseng

28 Expert Systems sstseng
FRAMES School meeting A KIND OF Monthly Meeting Weekly Meeting Occasional Meeting IF-ADDED:inform the participants IF-REMOVED: inform IS A IF-ADDED:inform the person IF-REMOVED: inform the person IF-CHANGED:... Expert Systems sstseng

29 Difficulties with FRAMES（框架）
Stereotype is that it have well defined features so that many of its slots have default values name 　　　　　　　　　　　　elephant specialization of 　　　　　　　a-kind-of mammal color 　　　　　　　　　　　　　gray legs　　　　　　　　　　　　　　　4 trunk 　　　　　　　　　　　　a cylinder Three-legged, two-legged Most frame（框架） systems do not? Provide a way of defining unalterable slots Nothing is really certain is such a unrestrained system Expert Systems sstseng

30 Expert Systems sstseng
Shopping Script： C(customer),S(salesperson) M(merchandise),D(dollars) L(a store) 1.Centers L 2.C begins looking around 3. C looks for a specific M 4. C looks for any interesting M 5. C asks S for help 6. 7.C finds M’ 8. C fails to find M 9. C leaves L 10.C buys M’ 11.C leaves L 12. goto step 2 13.C leaves L 14.C takes M’ Expert Systems sstseng

31 Expert Systems sstseng
Did Mary buy anything? Mary went shopping for a new coat. She found a new one. She really liked When she got it home, and discovered that it went perfectly with her favorite dress . Question：Did Mary buy anything? Expert Systems sstseng

32 5.8 Case-based Knowledge （案例式知識）
通常是用來描述屬於經驗的知識 從過去的經驗中，判定是何種相似的case（案例），並且依據過去解決此問題的方法，來解決此次問題 Case（案例） : 案例名稱 屬性 屬性值 案例名稱 屬性1 屬性值 屬性2 …… 屬性N Expert Systems sstseng

33 利用Case-based Knowledge（案例式知識）建構Expert System（專家系統）
Case Retrieve（案例擷取） Case Reuse（案例再用） Case Revise（案例修正） Case Retain（案例更新） Expert Systems sstseng

34 Expert Systems sstseng
案例推論循環 Expert Systems sstseng

35 5.9 Rule-based Knowledge （規則式知識）
知識領域具備需要推論的特性 例如：醫生依據其所學的醫學知識及病人所呈現的症狀去判別所罹患的疾病 最基本的Rules（規則）形式 如果 「狀態」 則 「結論」 IF (condition) THEN (conclusion) Inference Chaining（推論鏈） Forward Inference（前向推論） Backward Inference（後向推論） Expert Systems sstseng

36 5.10 Knowledge Object （知識物件）
Object Oriented（物件導向） Class（類別） and Object（物件） Super-class（父類別） and Sub-class（子類別） Inheritance（繼承）、Encapsulation（封裝）、Polymorphism（多型） Knowledge Object（知識物件） Object-Attribute-Value Triples ( OAV ) （物件-屬性-屬性值法） 物件導向規則庫管理系統 Knowledge Object Model（知識物件模型） Expert Systems sstseng

37 Object-Attribute-Value Triples ( OAV ) （物件-屬性-屬性值法）
OAV can be used to characterizes all the knowledge（知識） in a semantic net（語意網路） and was used in MYCIN for diagnosing infections diseases Especially useful for representing facts（事實） for only a single object： only attribute-value pairs (AV) Expert Systems sstseng

38 Object-Attribute-Value Triples（物件-屬性-屬性值法）
Car Wheel: 4 Function:run Object Attribute Value AKO AKO Door:3 . Door:4 . AKO AKO Carry:people size:small Carry:goods size:big AKO AKO price:$$$ Civic R9 price:$$$ price:$$$ price:$$$ ‧‧‧‧‧‧ ‧‧‧‧‧‧ is a is a year:1992 owner:crt year:1988 owner:gjh Expert Systems sstseng

39 Expert Systems sstseng
Limitations Lack of standard names for links and nodes（點） Combinatorial explosion of searching nodes（點） Logically inadequate 　　　no “for all”, “there exist”... Heuristically inadequate 　　　no effective search heuristics Expert Systems sstseng

40 Expert Systems sstseng
物件導向規則庫管理系統 將規則集合與物件導向概念結合 Rule Class（規則類別） and Rule Object（規則物件） Expert Systems sstseng

41 Expert Systems sstseng
5.11 Logic（邏輯） A description team for logic programming and expert systems is automated reasoning systems Syllogism（三段論）: The oldest and one of the simplest types of formal logic premise: all men are mortal premise: Socrates is a man Conclusion: Socrates is mortal Propositional Logic（命題邏輯） －a symbolic logic for manipulating propositions First－Order Predicate Logic（第一層敘述邏輯） Fuzzy Logic（模糊邏輯） Expert Systems sstseng

42 Propositional Logic（命題邏輯）
A sentence whose truth value can be determined 　e.g. it is raining 　　　Feather ( Albatrass) Compound Statement 　e.g. 　　If it is raining then carry an umbrella Expert Systems sstseng

43 Expert Systems sstseng
Tautology 　A compound statement that is always true 　e.g. P  ~p Contradiction 　A compound statement that is always false 　e.g. P  ~p Contingent Statement 　neither tautology nor contradiction 　e.g. P Expert Systems sstseng

44 5.12 First - Order Predicate Logic（第一層敘述邏輯）
Propositional logic（命題邏輯） is a subset of predicate logic（敘述邏輯） The basis of logic programming languages 　　　　e.g. Prolog Addition　: 　　　Variable universal quantifier: For all existential quantifier: There exist　　　 　e.g. 　　(　x) (x is a triangle x is a polygon) Expert Systems sstseng

45 Limitations of Predicate Logic（敘述邏輯）
The following statement can’t be expressed in predicate logic（敘述邏輯）: Most of the class received As To implement Most, a logic must provide some predicates for counting, e.g. fuzzy logic（模糊邏輯）. Expert Systems sstseng

46 Expert Systems sstseng
知識表示法 邏輯（Logic） 　語言正規而簡單（formal syntax） 　嚴密的理論 　完整的推理法則（rules of inference） 　可證性 　彈性大 模組性高（modularity） 不容易表示有處理（processing）和控制（control）的 　知識 Expert Systems sstseng

47 Expert Systems sstseng
缺乏結構性 有時不太自然 解釋不易 　採用解析原則（resolution principles）的邏輯 　系統解不易 　事實量大時，法則的選取（rule selection）會 　有組合膨脹（combinatorial explosion）的現象 Expert Systems sstseng

48 Expert Systems sstseng
Exercise 1. Draw an action frame system explaining what to do in case of hardware failure for your computer system. Consider disk crash , power supply , CPU, and memory problems. 2. Determine whether the following are valid or invalid arguments. A) pq, ~qr, r; ∴ p B)~pq, p(r  s),s q; ∴ q  r C) p (q r), q; ∴ p r Expert Systems sstseng

49 Expert Systems sstseng
專題進度規劃 10/18 交分組名單（每組最多四人） 11/01 交專題題目與初步構想書 11/29 交專題計劃書 12/20~1/10 上台presentation（每組十 五分鐘） 01/17 系統Demo & 交期末專題報告 Expert Systems sstseng

50 Expert Systems sstseng
誰殺了仙道？(1) 神奈川縣高中籃球決賽前夕，陵南高中籃球隊中的明星選手——仙道彰被殺死於自家住處。警方稍後拘捕了五名嫌犯。他們是湘北高中籃球隊的櫻木花道、三井壽、流川楓、赤木剛憲、宮城良田。在警方的盤問中，他們各人都要回答四個問題。但是由安西教練側面瞭解，各嫌犯所答的四個問題中有三個答案是真話，另一個答案是假話。而且兇手就是五人其中之一。以下是五人的供詞： Expert Systems sstseng

51 Expert Systems sstseng
誰殺了仙道？(2) 櫻木花道： （a）我沒有殺死仙道。 （b）我從未有手槍。 （c）流川楓討厭我。 （d）當天下午我在練球。 Expert Systems sstseng

52 Expert Systems sstseng
誰殺了仙道？(3) 三井壽： （a）我沒有殺死仙道。 （b）流川楓在今年內從未到過仙道家。 （c）我和赤木不熟。 （d）當天下午，我和櫻木在練球。 Expert Systems sstseng

53 Expert Systems sstseng
誰殺了仙道？(4) 流川楓： （a）我沒有殺死仙道。 （b）我今年內從未到過仙道家。 （c）我不討厭櫻木。 （d）如果赤木說我是兇手，這是謊言。 Expert Systems sstseng

54 Expert Systems sstseng
誰殺了仙道？(5) 赤木剛憲： （a）仙道被殺時，我在家中。 （b）我從未殺過人。 （c）流川楓是兇手。 （d）我和三井是好朋友。 Expert Systems sstseng

55 Expert Systems sstseng
誰殺了仙道？(6) 宮城良田： （a）如果櫻木說他從未有手槍，這是謊言。 （b）仙道在決賽前夕被殺的。 （c）命案發生時，赤木在家中。 （d）我們其中一人是兇手。 Expert Systems sstseng