Bài giảng Hệ chuyên gia (Expert System) - Chương 3: Máy suy diễn - Phan Huy Khánh

HHệệ chuyênchuyên giagia ((ExpertExpert SystemSystem))
 PGS.TS. Phan Huy Khánh
 khanhph@vnn.vn 
 Chương 3
 Máy suy diễn
 Chương 3 Máy suy diễn
a Các hệ thống sản xuất Post
a Thuật toán Markov và thuật toán mạng lưới
a Nguyên lý hoạt động của các máy suy diễn
a Một số phương pháp suy diễn thông dụng
 V Phương pháp suy diễn tiến
 V Phương pháp suy diễn lùi
 V Phương pháp hỗn hợp
 2/70
 Nền tảng của công nghệ hệ chuyên gia hiện đại
 (Foundation of Modern Rule-Based Expert System)
 HHệệ chuyênchuyên giagia ddựựaa trêntrên luluậậtt
 LuLuậậtt MáyMáy suysuy didiễễnn SSựự kikiệệnn
LuLuậậtt ssảảnn xuxuấấtt SoSo khkhớớpp HHợợpp gigiảảii SuySuy didiễễnn
 PostPost hihiệệuu ququảả xungxung độđộtt bênbên phphảảii luluậậtt
 ThuThuậậtt toántoán mmạạngng llướướii
 ThuThuậậtt toántoán MarkovMarkov
 3/70
 Foundations of Expert Systems
 Rule-BasedRule-Based ExpertExpert SystemsSystems
 InferenceInference EngineEngine KnowledgeKnowledge BaseBase
 PatternPattern 
 FactsFacts RulesRules
MatchingMatching ConflictConflict 
 ResolutionResolution 
 ReteRete PostPost 
AlgorithmAlgorithm ActionAction ProductionProduction 
 ExecutionExecution RulesRules 
 MarkovMarkov 
AlgorithmAlgorithm 
 4/70
 Hệ thống sản xuất Post
a Hệ thống sản xuất (SX) Post (Post production systems)
 V SX Post (production rule, also called condition-action,
 or situation-action rules)
 V Mỗi có dạng :
 → 
 V Ý tưởng cơ bản của Post là :
 ™ Xuất phát từ một xâu tiền đề (antecedent)
 ™ Sản xuất ra một xâu kết quả mới khác (consequent)
 V Dấu mũi tên → chỉ ra rằng :
 xâu vào bên trái được chuyển (transformation)
 thành xâu kết quả bên phải
 5/70
 Lịch sử các hệ thống SX Post
a First developed by Post (1943), who studied the properties of rule 
 systems based on productions & called his systems canonical 
 systems
 V Production rules are grammar rules for manipulating strings of 
 symbols, in automata theory, formal grammars, programming 
 language design & used for psychological modeling before they 
 were used for expert systems
 V Also called rewrite rules (they rewrite one string into another)
 V He proved any system of mathematics or logic could be written 
 as a type of production rule system
 V Minsky showed that any formal system can be realized as a 
 canonical system
 V Các ngôn ngữ lập trình thường được định nghĩa
 từ dạng chuẩn Backus-Naur Normal Form (BNF)
 6/70
 Example of a Canonical System
a Let the alphabet Σ = {a, b, c} 
 With axioms a, b, c, aa, bb, cc
a Then these production rules will give :
 V all the possible palindromes (and only palindromes) 
 V based on the alphabet, starting from the above axioms
 P1: $ -> a$a
 P2: $ -> b$b
 P3: $ -> c$c
a To generate the string bacab:
 V P1 is applied to the axiom c to get aca ( $ = c )
 V Then we apply P2 to get bacab
 Using a different order gives a different result
 V If P2 is applied to c we get bcb
 V If P1 is applied after we get abcba
 7/70
 Ví dụ 2
a Cho hệ thống SX Post gồm các luậ t SX như sau
 (Chú ý số thứ tự trong dấu ngoặc chỉ dùng để trình bày) :
 1.1. CarCar wonwon’t’t startstart →→ CheckCheck batterybattery
 2.2. CarCar wonwon’t’t startstart →→ CheckCheck gasgas
 3.3. CheckCheck batterybattery ANDAND BatteryBattery badbad →→ ReplaceReplace batterybattery
 4.4. CheckCheck gasgas ANDAND NoNo gasgas →→ FillFill gas gas tanktank
a Nếu đưa vào xâu Car won’t start, thì các luật 1 và 2 có thể được 
 áp dụng để sinh ra các xâu Check battery và Check gas
a Nếu đưa vào xâu Battery bad và Check battery thì luật 3 có thể 
 được áp dụng để sinh ra xâu Replace battery
 8/70
 Họat động của hhệệ ththốốngng SXSX PostPost 
a Hệ thống SX Post : 
 V Không có cơ chế áp dụng đồng thời cả hai xâu vào
 V Chỉ có thể áp dụng được một luật trong hai, hoặc không
 V Không đặt ra thứ tự các luật trong hệ thống
 V Hệ thống giữ nguyên giá trị khi đảo thứ tự các luật
 1.1. CarCar wonwon’t’t startstart →→ CheckCheck batterybattery
 2.2. CarCar wonwon’t’t startstart →→ CheckCheck gasgas
 3.3. CheckCheck batterybattery ANDAND BatteryBattery badbad →→ ReplaceReplace batterybattery
 4.4. CheckCheck gasgas ANDAND NoNo gasgas →→ FillFill gasgas tanktank
 4.4. CheckCheck gasgas ANDAND NoNo gasgas →→ FillFill gasgas tanktank
 2.2. CarCar wonwon’t’t startstart →→ CheckCheck gasgas
 1.1. CarCar wonwon’t’t startstart →→ CheckCheck batterybattery
 3.3. CheckCheck batterybattery ANDAND BatteryBattery badbad →→ ReplaceReplace batterybattery
 9/70
 Nhận xét về hạn chế của SX Post 
a Mặc dù các SX Post được sử dụng trong HCG nhưng không 
 thuận tiện cho việc viết các trình ứng dụng
a Hạn chế chủ yếu của các sản xuất Post :
 V Không có các chiến lược điều khiển (control strategy) để định 
 hướng sử dụng luật
 V Chỉ áp dụng luật cho một xâu vào theo cách tuỳ ý mà không 
 chỉ ra cụ thể làm thế nào để luật được áp dụng
 V Sự lựa chọn luật một cách ngẫu nhiên làm mất nhiều
 thời gian tìm kiếm trong các hệ thống có nhiều luật
 10/70
 Thuật toán Markov
a Thuật toán Markov (Markov Algorithm) :
 V Đề xuất năm 1954 cải tiến cách áp dụng các SX 
 từ một xâu vào
 V Nhóm các sản xuất theo thứ tự độ ưu tiên
 V Nếu SX có độ ưu tiên cao nhất không được áp dụng,
 thì SX tiếp theo sẽ được áp dụng và cứ thế tiếp tục
 V Thuật toán Markov dừng nếu :
 ™ sản xuất cuối cùng không được áp dụng cho xâu, hoặc
 ™ nếu sản xuất đó là cuối một giai đoạn được áp dụng
a A Markov algorithm:
 V is a string rewriting system that uses grammar-like rules to operate 
 on strings of symbols
 V Markov algorithms have been shown to have sufficient power to be
 a general model of computation.
 V Important difference from canonical system: now the set of rules is 
 ordered
 11/70
 Markov Algorithm (MA)
a The basic operation:
 1. Check the Rules in order from top to bottom to see whether 
 any of the strings to the left of the arrow can be found in the 
 Symbol string
 2. If none are found, stop executing the Algorithm
 3. If one or more is found, replace the leftmost matching text 
 in the Symbol string with the text to the right of the arrow in 
 the first corresponding Rule
 4. If the applied rule was a terminating one, stop executing the 
 Algorithm
 5. Return to step 1 and carry on
 12/70
 Áp dụng thuật toán Markov
a Thuật toán Markov có thể áp dụng cho từng xâu con của 
 xâu vào w∈Σ∈ ∗, bắt đầu từ bên trái :
 V Ví dụ : áp dụng luật ab → hij cho xâu vào gabkab
 V Nhận được xâu mới ghijkab
 Tiếp tục nhận được xâu mới ghijkhij
a Ký tự đặc biệt ε biều diễn xâu rỗng. Ví dụ : 
 V A → ε xóa tất cả các xuất hiện của A trong một xâu
 V A x B → B x A nghịch đảo các ký tự A và B
a Các ký hiệu đặc biệt khác có vai trò như biến biểu diễn một 
 ký tự bất kỳ được viết bởi các chữ cái thường a, b, c...
a Các chữ cái Hy lạp α, β ∉Σ∉ , chỉ các dấu đặc biệt của xâu
 13/70
 Ví dụ sử dụng thuật toán Markov
 Thành công (S) Xâu
a Cho các SX có độ ưu tiên giảm Luật
 dần như sau (ký hiệu ε hoạt động hoặcthấtbại(F) kếtquả
 như là một biến trung gian) : 1 F abc
 εxy → yεx
 2 F abc
 ε→ ε
 ε→ε
 3 S εabc
a Cho xâu vào abc, cần di chuyển 
 chữ cái đầu tiên a đến vị trí cuối 1 S bεac
 cùng của xâu
a Quá trình di chuyển được cho 1 S bcεa
 trong bảng
 1 F bcεa
 2 S bca
 14/70
 Another Example of MA
a Rules: a The Symbol string will change in 
 1. "A" -> "apple" the following manner:
 2. "B" -> "bag" R1: "I bought a B of apples from 
 T S." .
 3. "S" -> "shop" 
 R2: "I bought a bag of apples 
 4. "T" -> "the" from T S." 
 5. "the shop" -> "my brother" R3: "I bought a bag of apples 
 6. "a never used" -> from T shop." 
 ."terminating rule" 
 R4: "I bought a bag of apples 
a Symbol string : from the shop." 
 "I bought a B of As from T S." R5: "I bought a bag of apples 
 from my brother." 
 a The algorithm will then terminate
 15/70
 Another Example of MA
 a They rewrite binary numbers to a If the algorithm is applied to the 
 their unary counterparts above example, it will terminate 
 a For example: 101 will be after the following steps
 rewritten to a string of 5 a Execution:
 consecutive bars "0|01" 
 a Rules: "00||1" 
 "|0" -> "0||" "00||0|" 
 "1" -> "0|" "00|0|||" 
 "0" -> "" "000|||||" 
 a Symbol string: "00|||||" 
 "101" "0|||||" 
 "|||||"
a MA chọnápdụng luậtcóđộ ưutiênnhấttheochiếnlược điềukhiểntất định
 (definite control strategy)
a Nếukhôngchọn được, MA tìm luậtkháccóđộ ưutiênthấphơn
a MA thiếutínhhiệuquả trong những hệ chuyên gia có nhiềuluật
 16/70
 Thuật toán mạng lưới (Rete Algorithm)
a Do Charles L. Forgy đề xuất năm 1979 tại trường ĐH Carnegie, 
 Mellon, Hoa Kỳ trong luận văn tiến sĩ của ông về OPS (Official 
 Production System)
a Thuật toán mạng lưới giải quyết vấn đề hiệu suất
 (efficient) của các hệ chuyên gia :
 V Đóng vai trò quan trọng khi giải quyết các bài toán thực tiễn chứa 
 từ hàng trăm đến hàng ngàn luật
 V NSD không phải chờ đợi nhiều thời gian để nhận được câu trả lời
a Cần có thuật toán xử lý hết các luật để chọn ra các luật 
 cần thiết để áp dụng thay vì thử lần lượt các luật
 17/70
 RETE algorithm
a Thuật toán mạng lưới :
 V Cho phép so khớp (pattern mattching) rất nhanh để nhận 
 được câu trả lời tức thời bằng cách lưu giữ thông tin của các 
 luật trong một mạng lưới (network)
 V Thay vì so khớp lặp đi lặp lại các sự kiện mỗi lần áp dụng một 
 luật trong mỗi chu trình nhận thức (recognize-act cycle),
 thuật toán mạng lưới chỉ nhìn những thay đối khi so khớp 
 trong mỗi chu trình
a Activities
 V Creates a decision tree where each node corresponds to a 
 pattern occurring at the left-hand side of a rule
 V Each node has a memory of facts that satisfy the pattern
 V Complete LHS as defined by a path from root to a leaf
 18/70
 The Rete-Algorithm 
a The net encodes the condition parts (IF-parts) of the rules
a The input are the changes of the working memory, i.e.:
 V New elements or deleted elements
 V Modification of elements is simulated by first delete then add 
 modified version) 
a The output is the conflict set (i.e., the applicable rules) 
 19/70
 Rete example
Rules:Rules: IFIF xx && yy THENTHEN pp
 IFIF xx && yy && zz THENTHEN qq
PatternPattern x? y?
 x?x? y?y? x? y? z?z?
NetworkNetwork
JoinJoin NetworkNetwork
 pp
88 nodesnodes
 qq
 (
 20/70
 Rete example
Rules:Rules: IFIF xx && yy THENTHEN pp
 IFIF xx && yy && zz THENTHEN qq
PatternPattern x?x? y?y? z?z?
NetworkNetwork
JoinJoin NetworkNetwork
 pp
88 nodesnodes
 qq
 (
 21/70
 Rete example
Rules:Rules: IFIF xx && yy THENTHEN pp
 IFIF xx && yy && zz THENTHEN qq
PatternPattern x?x? y?y? z?z?
NetworkNetwork
JoinJoin NetworkNetwork
 pp
 88 nodesnodes
 qq
 (
 22/70
 Matching Patterns
a At each cycle the interpreter looks to see which rules have 
 conditions that can be satisfied
a If a condition has no variables:
 V It will only be satisfied by an identical expression in working 
 memory
a If the condition contains variables then
 V It will be satisfied if there is an expression in working 
 memory with an attribute-value pair that matches it in a way 
 that is consistent with the way other conditions in the same 
 rule have already been matched
 23/70
 Rule-Based Production Systems
a A production system consists of
 V a rule set / knowledge base / production memory
 V a rule interpreter / inference engine
 ™ that decides when to apply which rules
 V a working memory
 ™ that holds the data, goal statements, & intermediate results 
 that make up the current state of the problem. 
a Rules have the general form
 IF THEN 
 P1, , Pm → Q1, , Qn
a Patterns are usually represented by OAV vectors
 24/70
 Nguyên lý hoạt động của các máy suy diễn
a Trong các hệ thống dùng luật, khi máy duy diễn (MSD) 
 được khởi động, cơ sở tri thức chứa thông tin liên quan đến 
 phát biểu bài toán cần giải :
 V Các sự kiện đã được xác nhận và các sự kiện sẽ được thiết 
 lập biểu diễn bài toán hay đích
 V Những tri thức thực hành thuộc lĩnh vực tạo nên cơ sở luật 
a Hoạt động suy diễn của MSD :
 V Suy luận bằng cách quyết định xem những luật nào sẽ làm 
 thỏa mãn các sự kiện, các đối tượng
 V Chọn ưu tiên các luật thỏa mãn
 V Thực hiện các luật có tính ưu tiên cao nhất
 25/70
 Một số quy ước 
a Ta quy ước gọi :
 V RB (Rules Base) là cơ sở luật (CSL)
 V FB (Facts Base) là cơ sở sự kiện (CSSK)
a Máy suy diễn họat động theo chu kỳ (cycle),
 mỗi chu kỳ gồm hai giai đoạn (phase) :
 V Giai đoạn đánh giá ( EVALUATION), gồm ba bước (step) :
 ™ Thu hẹp (RESTRICTION. hay SELECTION)
 ™ So khớp (PATTERN−MATCHING, hay FILTERING)
 ™ Giải quyết xung đột (CONFLICT-RESOLUTION)
 V Thực hiện (EXECUTION)
 26/70
 ChuChu kkỳỳ hhọọatat đđộộngng ccơơ bbảảnn ccủủaa MSDMSD 
 Giai đoạn 1 : Giai đoạn 2 : 
 EVALUATION EXECUTION
 RESTRICTION
 R1 chứa trong RB Thực hiện các tiên đề
 F1 chứa trong FB
 Các quy tắc của R3
 PATTERN−MATCHING
 so sánh giữa R1 và F1
 tìm được FB và RB
 R2 chứa trong R1 có thể bị thay đổi
 CONFLICT-RESOLUTION Các kết qu ả kh ác có thể
 tìm được
 R3 chứa trong R2 
Tuỳ theo điều khiển của máy : Tuỳ theo điều khiển của máy :
 dừng hay quay lại dừng hay quay lại
 27/70
Mô hình so khớp luật trong một chu kỳ
 R1 ∈ RB
 F1 ∈ FB
 R3 R2
 Tiếp tục
 28/70
 Bước thu hẹp
a Là bước đầu tiên của giai đoạn đánh giá
a Đầu vào :
 V Một sự kiện f ∈ FB (CSSK) và/hoặc luật r ∈ RB (CSL)
a Đầu ra :
 V Một tập hợp con F1 ⊆ FB 
 V Một tập hợp con R1 ⊆ RB sao cho có thể tiến hành so sánh 
 được trong bước FILTERING tiếp theo
a Nguyên lý làm việc :
 V Ưu tiên cho một nhóm các luật
 hay một nhóm các sự kiện đối với một hoặc nhiều chu kỳ
 Return
 29/70
 Bước so khớp
a Là bước thứ hai của giai đoạn đánh giá
a Đầu vào :
 V Một sự kiện f ∈ FB (CSSK) và/hoặc luật r ∈ RB (CSL)
a Đầu ra :
 V Một tập hợp con các luật R2⊆R1 tương thích với F1,
 nghĩa là những luật r∈R2 có điều kiện khởi động thoả mãn 
 các trạng thái của F1
a Nguyên lý làm việc :
 V Máy suy diễn so sánh phần khởi động của mỗi quy tắc của 
 R1 với tập hợp các sự kiện F1
 V Tuỳ theo hệ thống mà có tiêu chuẩn thoả mãn khác nhau
 V R2 được gọi là tập hợp xung đột hay tập hợp tương tranh
 (conflict set)
 Return
 30/70
 Bước giải quyết xung đột
a Là bước thứ ba của giai đoạn đánh giá
a Đầu vào :
 V Tập hợp các luật trong tập xung đột R2
a Đầu ra :
 V Tập hợp con các luật R3 ⊆ R2 cần được thực hiện
a Nguyên lý làm việc :
 V Nếu R3 rỗng, không thực hiện giai đoạn EXECUTION của chu kỳ
 V Nếu R3≠∅, chọn các luật dựa trên những tiêu chuẩn như sau :
 ™ Hoặc chọn theo thứ tự xuất hiện của luật với giả thiết RB đã 
 được sắp xếp theo một thứ tự nào đó
 ™ Hoặc chọn các luật có mối quan hệ với bối cảnh áp dụng liên 
 quan đến nghĩa (meaning/signification)
 ™ Hoặc chọn ngẫu nhiên : ưu tiên luật ít sử dụng, hoặc ít điều kiện 
 cần kiểm tra, ít biến cần xác định trước khi khởi động, v.v...
 Return
 31/70
 Conflict Resolution
a Selection a rule to fire
 V Production systems have a decision-making step between pattern 
 m ... s
 V Actions such as assert or modify the Working Memory
 35/70
 Nhận xét về chu kỳ cơ bản của MSD
a Trên thực tế, có nhiều cách sắp đặt các giai đoạn trong một 
 chu kỳ cơ bản (hay chu kỳ suy diễn) của MSD
a Khi HCG làm việc, có thể cần đến hàng hàng trăm, thậm chí
 hàng ngàn chu kỳ
a Mỗi chu kỳ cơ bản của MSD :
 V Có liên hệ với chu kỳ lệnh của máy tính
 V Cần những máy tính có tốc độ lớn
 (hàng trăm chu kỳ cơ bản trong một giây)
 V Chẳng hạn dự án máy tính thế hệ 5 của Nhật đề xuất những 
 kiến trúc đặc trưng để đạt được tốc độ hàng triệu hay hàng 
 tỷ lips (Logical Inference Per Second)
 Return
 36/70
 Phương pháp suy luận của các MSD
a Có nhiều phương pháp tổng quát để suy luận trong các 
 chiến lược giải quyết vấn đề của HCG
a Ba phương pháp hay gặp :
 V Phương pháp suy diễn tiến (Foward Chaining/Data-Driven)
 V Phương pháp suy diễn lùi (Backward Chaining/Goal-Driven)
 V Phương pháp phối hợp hai phương pháp này
 (Mixed Chaining)
a Ngoài ra còn một số phương pháp khác :
 V Phân tích phương tiện (means-end analysis)
 V Rút gọn vấn đề (problem reduction)
 V Kiểm tra lập kế hoạch (plan-generate-test)
 V Lập kế hoạch phân cấp (hierachical planning)...
 37/70
 Phương pháp suy diễn tiến
a Suy diễn tiếnlàlập luận từ các sự kiện, sự việc
 để rút ra các kết luận
 V Ví dụ :
 Nếu thấy trời mưa trước khi ra khỏi nhà (sự kiện)
 thì phải lấy áo mưa (kết luận)
a NSD cung cấp các sự kiện
 để MSD tìm cách rút ra các kết luận có thể
 V Kết luận có thể là những thuộc tính được gán giá trị
 V Trong số những kết luận này, có thể có :
 ™ những kết luận làm NSD quan tâm
 ™ một số khác không nói lên điều gì
 ™ một số khác có thể vắng mặt
 38/70
 Các sự kiện trong suy diễn tiến
a Các sự kiện thường có dạng :
 V Atthibute = value
 V Lần lượt các sự kiện trong cơ sở tri thức được chọn
 V Hệ thống xem xét tất cả các luật mà các sự kiện này
 xuất hiện như là tiền đề
 V Khi MSD tìm thấy những luật thoã mãn, MSD lấy ra để gán 
 giá trị cho các thuộc tính thuộc kết luận tương ứng,
 người ta nói rằng các sự kiện đã được thoã mãn
 V Các thuộc tính được gán giá trị sẽ là một phần của kết quả
 chuyên gia
 V Sau khi mọi sự kiện đã được xem xét, kết quả được xuất ra 
 cho NSD
 39/70
 Forward Chaining
a The inference engine works from the initial content of the 
 workspace towards the final conclusion
a Conclude from "A" and "A implies B" to "B"
 AA
 AA →→ BB
 BB
a Example: 
 It is raining
 If it is raining, the dress is wet
 --------------------------------------
 The dress is wet
 40/70
Một ví dụ khác
 41/70
 Palindrome Example
a If we have the following grammar rules
 (P1) $ -> a$a
 (P2) $ -> b$b
 (P3) $ -> c$c
a They can be used Forward Chaining
 to generate palindromes:
 V apply P1, P1, P3, P2, to c:
 ⇒ aca, aacaa, caacaac, ...
a To generate bacab
 V P1 is applied to the axiom c to get aca
 V Then we apply P2 to get bacab
 V Using a different order gives a different result
 V If P2 is applied to c we get bcb
 V If P1 is applied after we get abcba
 42/70
 Example 1
Rule base Workspace
R1: IF A AND B THEN D A,B
R2: IF B THEN C 
R3: IF C AND D THEN E
 43/70
 Forward Chaining Model
FactsFacts RuleRule
 basebase DetermineDetermine 
 possiblepossible 
 rulesrules toto firefire
 WorkingWorking
 memorymemory Conflict set
 SelectSelect ConflictConflict
 FireFire Rule found
 rulerule toto resolutionresolution
 rulerule
 firefire strategystrategy
 No rule found
 ExitExit
 Exit if specified by the rule
 44/70
 Thuật toán suy diễn tiến
a Definitions :
 FB, RB, R1 ⊆ RB, Q : Sự kiện đưa vào xử lý 
a Algorithme :
 Procedure DEDUCE(Q)
 If Q ∈ FB Then Write "Success" ;
 Else Call CYCLE(RB) ; ' Bắt đầu chu kỳ xử lý với r1 ∈RB
 Procedure CYCLE(R1)
 If R1 = ∅ Then Write "Failure" ; Return ;
 r ← CHOIX(r, R1) ; ' Chọn một luật từ R1
 R1 ← R1 – { r } ; ' Loại bỏ luật đã xử lý
 If LHF(r) ∈ FB Then
 If Q ∈ RHF(r) Then Write " Success" ; Return ;
 Else ' Không tìm thấy Q nhưng vẫn tiếp tục áp dụng luật r
 FB ← FB ∪ RHF(r) ; ' Thêm vào FB các sự kiện mới
 RB ← RB – { r } ; ' Loại bỏ luật r đã xử lý 
 Call CYCLE(RB) ;
 Else Call CYCLE(R1) ;
 Return ;
 45/70
Forward chaining algorithm
 46/70
 Forward chaining Example 2.
 WMWM WMWM WMWM WMWM
 A B C D E A B C D E A B C D E A B C D E
 X X L X L Y X L Y Z
Match Fire Match Fire Match Fire Match Fire
 KBKB BKBK BKBK KBKB
 Y ∧ D Z Y Ÿ D Z Y Ÿ D Z Y Ÿ D Z
 X Ÿ B Ÿ E Y X Ÿ B Ÿ E Y X Ÿ B Ÿ E Y X Ÿ B Ÿ E Y
 A X A X A X A X
 C L C L C L C L
 L Ÿ M N L Ÿ M N L Ÿ M N L Ÿ M N
 Cycle 1 Cycle 2 Cycle 3
 47/70
 Example 3. Diagnosing car problems
a Rule 1: 
 IF the engine is getting gas
 AND the engine will turn over
 THEN the problem is spark plugs
a Rule 2:
 IF the engine does not turn over
 AND the lights do not come on
 THEN the problem is battery or cables
a Rule 3:
 IF the engine does not turn over
 AND the lights do come on
 THEN the problem is the starter motor
a Rule 4:
 IF there is gas in the fuel tank
 AND there is gas in the carburettor
 THEN the engine is getting gas
 48/70
a Facts
 The engine is getting gas
 Working space
 RuleRule 11
 RuleRule 22
 RuleRule 33
 RuleRule 44
 Working space
 RuleRule 11
 thethe engineengine RuleRule 22
 turnsturns overover RuleRule 33
 RuleRule 44
 49/70
 Working space
 TheThe engineengine isis RuleRule 11
 gettinggetting gasgas Rule 2
 Rule 2
 ThereThere isis gasgas RuleRule 33
 inin thethe fuelfuel tanktank RuleRule 44
 There is gas
 There is gas 
inin thethe carburettorcarburettor
 The engine
 The engine 
 turnsturns overover
 50/70
 Example 4.
 G ĐồĐồ ththịị VÀ-HOVÀ-HOẶẶCC 
 (And-Or(And-Or Tree)Tree)
aa Rulesbase:Rulesbase: 
 1.1. K,K, L,L, MM →→ II = E D C 
 2.2. I,I, L,L, JJ →→ QQ
 3. C, D, E B H F C H
 3.3. C,C, D,D, EE →→ BB 
 4. A, B Q M L K
 4.4. A,A, BB →→ QQ 
 = = =
 5.5. L,L, N,N, O,O, PP 
 →→ QQ
 B A =
 6. C, H R O N J L J R M
 6.6. C,C, HH →→ RR 
 7. R, J, M S P L 
 7.7. R,R, J,J, MM →→ SS I 
 8.8. F,F, HH →→ BB 
 = = = =
 9. G F = = = =
 9.9. GG →→ FF 
aa Factsbase:Factsbase: 
 A,A, C,C, D,D, E,E, G,G, H,H, KK
 Q S
 51/70
 Example 4. Kết quả suy diễn
a Xây dựng đồ thị con VÀ-HOẶC từ đồ thị VÀ-HOẶC trên đây
 V Tìm được Q khi các sự kiện A, C, D và E được thiết lập 
 G
 E D C 
 =
 = E D C 
 H F C H
 M L K =
 = = =
 B A
 B A = J R M
 O N J L J R M
 P L 
 I 
 = = = = =
 Q
 Q S Q
 52/70
 Exercise 1.
aa Rulesbase:Rulesbase: a Yêu cầu :
 1.1. B,B, D,D, EE →→ FF V Vẽ đồ thị và-hoặc
 2.2. G,G, DD →→ AA V Áp dụng thuật toán suy diễn tiến
 để tìm kết quả H
 3.3. C,C, FF →→ AA
 V Có nhận xét gì ?
 4.4. BB →→ XX 
 5.5. DD →→ EE 
 6.6. X,X, AA →→ HH 
 7.7. CC →→ DD 
 8.8. X,X, CC →→ AA 
 9.9. X,X, BB →→ DD 
aa Factsbase:Factsbase: 
 B,B, CC
 53/70
 Exercise 2.
aa RulesRules Base:Base: aa FactsFacts Base:Base:
R1:R1: IFIF managementmanagement competencecompetence isis goodgood Bank'sBank's creditcredit ratingrating UNKNOWNUNKNOWN
 ANDAND ExternalExternal creditcredit ratingrating isis fairfair
 ANDAND Bank'sBank's creditcredit ratingrating isis Cash/currentCash/current liabilitiesliabilities 0.180.18
 marginalmarginal ExternalExternal creditcredit ratingrating FAIRFAIR
 THENTHEN LoanLoan isis rejectedrejected LoanLoan SEASONALSEASONAL
R2:R2: IFIF LoanLoan typetype isis seasonalseasonal LoanLoan typetype UNKNOWNUNKNOWN
 ANDAND ProfitabilityProfitability ratingrating isis highhigh ManagementManagement competencecompetence UNKNOWN UNKNOWN
 ANDAND SolvencySolvency ratingrating isis lowlow ProfitabilityProfitability ratingrating HIGHHIGH
 THENTHEN Bank'sBank's creditcredit ratingrating isis SolvencySolvency ratingrating UNKNOWNUNKNOWN
 marginalmarginal TentativeTentative solvencysolvency ratingrating LOWLOW
R3:R3: IFIF Cash/currentCash/current liabilitiesliabilities >> 0.10.1 
 ANDAND TentativeTentative solvencysolvency ratingrating isis 
 lowlow 
 THENTHEN SolvencySolvency ratingrating isis lowlow
 54/70
 Example knowledge base contd.
... it is a crime for an American to sell weapons to hostile nations:
 American(X) ∧ Weapon(Y) ∧ Sells(X,Y,Z) ∧ Hostile(Z) → Criminal(X)
Nono  has some missiles, i.e., ∃X Owns(Nono,X) ∧ Missile(X): 
 Owns(Nono,M1) and Missile(M1) 
 all of its missiles were sold to it by Colonel West
 Missile(X) ∧ Owns(Nono,X) → Sells(West,X,Nono)
Missiles are weapons: 
 Missile(X) → Weapon(X)
An enemy of America counts as "hostile“:
 Enemy(X,America) → Hostile(X)
West, who is American  
 American(West)
The country Nono, an enemy of America 
 Enemy(Nono,America)
 55/70
 Forward chaining proof
 Criminal(West)Criminal(West)
 Weapon(M1)Weapon(M1) Sells(West,M1,Nono)Sells(West,M1,Nono) Hostile(Nono)Hostile(Nono)
American(West)American(West) Missile(M1)Missile(M1) Owns(Nono,M1)Owns(Nono,M1) Enemy(Nono,America)Enemy(Nono,America)
 56/70
 Phương pháp suy diễn lùi
a Phương pháp suy diễn lùi :
 V Tiến hành các lập luận theo chiều ngược lại
 (so với phương pháp suy diễn tiến)
 V Đầu vào có dạng một câu hỏi «Cho biết giá trị thuộc tính đích (goal) A ?»
 V MSD suy diễn để đưa ra tình huống trả lời gồm các sự kiện là cơ sở của giả
 thuyết đã cho gồm để gán giá trị cho thuộc tính A
a Ví dụ :
 V Nếu ai đó vào nhà mà cầm áo mưa và áo quần bị ướt (hậu quả)
 thì giả thuyết là trời mưa (nguyên nhân)
 V Để củng cố giả thuyết này,
 ta sẽ hỏi người đó xem có phải trời mưa không ?
 V Nếu người đótrả lời có
 thì giả thuyết trời mưa đúng và trở thành một sự kiện
 V Nghĩa là trời mưa nên phải cầm áo mưa và áo quần bị ướt
 57/70
 Ý tưởng thuật toán suy diễn lùi
a Với mỗi thuộc tính đã cho, người ta định nghĩa nguồn của nó :
 V Nếu thuộc tính xuất hiện như là tiền đề của một luật (phần đầu 
 của luật), thì nguồn sẽ thu gọn thành một câu hỏi
 V Nếu thuộc tính xuất hiện như là hậu quả của một luật (RHS),
 thì nguồn sẽ là các luật mà trong đó, thuộc tính là kết luận
 V Nếu thuộc tính là trung gian, xuất hiện đồng thời như là tiền đề và 
 như là kết luận, khi đónguồn có thể là các luật, hoặc có thể là các 
 câu hỏi mà chưa được nêu ra
 V Nếu mỗi lần với câu hỏi đã cho, người sử dụng trả lời hợp lệ, giá trị
 trả lời này sẽ được gán cho thuộc tính và xem như thành công
 V Nếu nguồn là các luật, MSD sẽ tìm giá trị các thuộc tính thuộc tiền 
 đề (LHS) bằng cách xét lần lượt các luật có thuộc tính đích xuất 
 hiện ở kết luận
 V Nếu các luật thoã mãn, thuộc tính kết luận sẽ được ghi nhận
 58/70
 Backward Chaining
a Conclude from "B" and "A implies B" to "A" 
 BB
 AA →→ BB
 AA
a Example: 
 The dress is wet
 If it is raining, the dress is wet
 --------------------------------------
 It is raining
 59/70
Backward Chaining
 60/70
 Thuật toán suy diễn lùi
a Definitions :
 FB, RB, R1 ⊆ RB
 Q : Sự kiện đưa vào xử lý 
a Algorithme : 
 Procedure DEDUCE (Q)
 If Q ∈ BF Then Write " Success" ;
 Else 
 Push BR, BF ;
 IP ≠ 1; 
 Call CYCLE(BR, BF) ;
 Return; 
 61/70
 Thuật toán suy diễn lùi
Procedure CYCLE(ER, EF)
Var : ER, EF, r ; ' Các biến làm việc địa phương
If ER = ∅ Then 
 IP ≠ IP -1 ; ' Lấy một luật ở đỉnh Stack
 If IP = 0 Then Write " Failure" ; Return;
 Else ER ≠ Lu ật ở đỉnh Stack chưa xét
 EF ≠ Các sự ki ện ở đỉnh Stack; 
 Call CYCLE(ER, EF) ; Return;
r ≠ CHOOSE(r, ER) ; ' Chọn một luật
ER ≠ ER – { r } ; ' Lo ại bỏ luật đã xét ở ER
If LHS(r) ∈ EF Then 
 If RHF(r) ∈ Q Then Write " Success" ; Return ;
 Else Push (EF ∪ RHF(r)), BR ; ' (IP ≠ IP +1)
 Đ ánh dấu màu đỏ ph ần tử ngay dướ i đỉnh Stack;
 Đánh dấu màu đỏ cho luật r ở đỉnh
 Đánh dấu màu xanh cho luật r tại đỉnh - 1 ;
 ER ≠ Các luật ởđỉnh ch ưa đánh dấu. Thông thường là màu đỏ;
 EF ≠ Các sự kiện ở đỉnh Stack ; 
 Call CYCLE(ER, EF) ; Return; 
Call CYCLE(ER, EF) ; Return ; 
 62/70
 Example 4. Backward Chaining
 G
 ĐồĐồ ththịị VÀ-HOVÀ-HOẶẶCC 
aa Rulesbase:Rulesbase:
 (And-Or(And-Or Tree)Tree)
 1.1. K,K, L,L, MM →→ II = E D C 
 2.2. I,I, L,L, JJ →→ QQ 
 3. C, D, E → B H F C H
 3. C, D, E → B 
 4. A, B → Q M L K
 4. A, B → Q M L K 
 5. L, N, O, P → Q = = =
 5. L, N, O, P → Q 
 6.6. C,C, H H →→ RR B A =
 O N J L J R M
 7.7. R,R, J,J, MM →→ SS J L J R M
 8. F, H → B P L 
 8. F, H → B I
 9.9. GG →→ FF 
 = = = =
a Factsbase:
a Factsbase: 
 A,A, C,C, D,D, E,E, G,G, H,H, KK
aa QuestionQuestion (Goal):(Goal):
 QQ Q S
 63/70
Đồ thị Và-Hoặc thiết lập Q
 E D C 
 LuLuậậtt 33
 M L K
 KhKhởởii đđộộngng 44 = LuLuậậtt 11
 B A = KhKhởởii đđộộngng 22
 J L
 LuLuậậtt 44 I
 LuLuậậtt 22
 KhKhởởii đđộộngng 33 = =
 KhKhởởii đđộộngng 11
 Q
 64/70
 Áp dụng thuật toán suy diễn lùi
 QQ AA CC DD EE GG HH KK
 Luật 2 Luật 4
 (khởi động 1) (khởi động 3)
 II JJ LL AA CC DD EE GG HH KK BB AA CC DD EE GG HH KK
 Luật 1 Luật 3
(khởi động 2) (khởi động 4)
 MM JJ LL AA CC DD EE GG HH KK AA CC DD EE GG HH KK
 Failure Success
 65/70
 Exercise
a Áp dụng thuật toán suy diễn lùi cho ví dụ Colonel West 
 66/70
 Data-driven × Goal-driven
 herehere seenseen holidayholiday
 data driven
 absentabsent
 buildingbuilding
 homehome
 goal driven
finefine sicksick
 67/70
 Data-driven × Goal-driven
a Goal Driven (backward chaining) ~ blood diagnostic, 
 theorem proving
 V Limited number of goal hypothesis
 V Data shall be acquired, complicated data about the object
 V Less operators to start with at the goal rather than at the data
a Data Driven (forward chaining) ~ configuration, interpretation,
 V reasonable set of input data
 V data are given at the initial state
 V huge set of possible hypothesis
a Taxonomy of rules, meta-rules, priorities, 
 68/70
 Forward or Backward Reasoning?
a Four major factors
a More possible start states or goal states?
 Move from smaller set of states to the larger
 Assume you are at home and you need some bread. You've one initial 
 state and many possible goal states where to get bread from 
 (Sainsbury's, Tesco, Aldi, Morrison, ASDA, CornerShop, Bakery). That is, 
 in such a situation it is probably a good approach to search in forward 
 chaining fashion, since you have many chances to hit a goal. If you 
 choose backward chaining you would have to commit to one of the 
 goals, e.g. the Bakery and then search backwardly how the get there 
 from home.
 If, however, there are 5 people Alice, Bob, Claire, Dora, and Edgar at 5 
 different places A, B, C, D, and E, and one of them should get the Tesco 
 home brand of ketchup, then it would be better to start backward
 chaining from the Tesco store and stop search when one of the places 
 A, B, C, D, or E is reached
 69/70
 Forward or Backward Reasoning? (Cont'd)
a Has program to justify reasoning?
 V Prefer direction that corresponds more closely to the way 
 users think
a What kind of events triggers problem-solving?
 V If it is arrival of a new fact, forward chaining makes sense
 V If it is a query to which a response is required, 
 backward chaining is more natural. 
a In which direction is branching factor greatest?
 V Go in direction with lower branching factor
 70/70