Bài giảng Hệ chuyên gia (Expert System): Chương 3

HHệệ

chuyên gia chuyên gia

KhKháánhnh

PGS.TS. PhanPhan PGS.TS.

Expert System)) ((Expert System HuyHuy khanhph@vnn.vn khanhph@vnn.vn

Chương

Máy

3 diễn

suy

Chương 3 Máy suy diễn

(cid:97) Các hệ thống sản xuất Post

(cid:97) Thuật toán Markov và thuật toán mạng lưới

(cid:97) Nguyên lý hoạt động của các máy suy diễn

(cid:97) Một số phương pháp suy diễn thông dụng

(cid:86) Phương pháp suy diễn tiến

(cid:86) Phương pháp suy diễn lùi

(cid:86) Phương pháp hỗn hợp

2/2/7070

Nền tảng của công nghệ

chuyên gia hiện đại

hệ

(Foundation of Modern Rule-Based Expert System)

Hệ Hệ

chuyên gia dựa trên luật chuyên gia dựa trên luật

Máy suy diễn Máy suy diễn

Luật Luật Sự Sự kiện kiện

So khớp So khớp hiệu quả hiệu quả Suy diễn Suy diễn bên phải luật bên phải luật Luật sản xuất Luật sản xuất Post Post Hợp giải Hợp giải xung đột xung đột

Thuật toán mạng lưới Thuật toán mạng lưới

Thuật toán Markov Thuật toán Markov

3/3/7070

Foundations of Expert Systems

Rule-Based Expert Systems Rule-Based Expert Systems

Knowledge Base Knowledge Base

Inference Engine Inference Engine

Facts Facts

RulesRules

Pattern Pattern Matching Matching

Conflict Conflict Resolution Resolution

Rete Rete Algorithm Algorithm

Post Post Production Production Rules Rules

Action Action Execution Execution

Markov Markov Algorithm Algorithm

4/4/7070

Hệ

thống sản xuất Post

(cid:97) Hệ thống sản xuất (SX) Post (Post production systems)

(cid:86) SX Post (production rule, also called condition-action,

or situation-action rules)

(cid:86) Mỗi có dạng :

< xâu kết quả>

< xâu tiền đề> →

(cid:86) Ý tưởng cơ bản của Post là :

(cid:153) Xuất phát từ một xâu tiền đề(antecedent)

(cid:153) Sản xuất ra một xâu kết quả mới khác (consequent)

(cid:86) 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/5/7070

Lịch sử

thống SX Post

các hệ

(cid:86) 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

(cid:86) Also called rewrite rules (they rewrite one string into another)

(cid:86) He proved any system of mathematics or logic could be written

as a type of production rule system

(cid:86) Minsky showed that any formal system can be realized as a

canonical system

(cid:86) 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)

(cid:97) First developed by Post (1943), who studied the properties of rule systems based on productions & called his systems canonical systems

6/6/7070

Example of a Canonical System

(cid:97) Let the alphabet Σ = {a, b, c} With axioms a, b, c, aa, bb, cc

(cid:97) Then these production rules will give :

(cid:86) all the possible palindromes (and only palindromes) (cid:86) based on the alphabet, starting from the above axioms

P1: P2: P3: $ -> a$a $ -> b$b $ -> c$c

(cid:86) P1 is applied to the axiom cto get aca ( $ = c ) (cid:86) Then we apply P2 to get bacab

(cid:97) To generate the string bacab:

(cid:86) If P2 is applied to cwe get bcb

(cid:86) If P1 is applied after we get abcba

Using a different order gives a different result

7/7/7070

Ví

2 dụ

(cid:97) 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) :

(cid:97) 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 batteryvà Check gas

(cid:97) Nếu đưa vào xâu Battery badvà Check battery thì luật 3 có thể

được áp dụng để sinh ra xâu Replace battery

t start 1. Car won’’t start 1. Car won 1. Car won’t start t start 2. Car won’’t start 2. Car won 2. Car won’t start 3. Check battery AND Battery bad 3. Check battery AND Battery bad 3. Check battery AND Battery bad 4. Check gas AND No gas 4. Check gas AND No gas 4. Check gas AND No gas Check battery Check battery Check battery Check gas Check gas Check gas Replace battery Replace battery Replace battery Fill gas tank Fill gas tank Fill gas tank →→ → →→ → →→ → →→ →

8/8/7070

Họat động của hhệệ

ng SX Post ththốống SX Post

ng SX Post : (cid:97)(cid:97) HHệệ ththốống SX Post :

Không cóó cơ ch

cơ chếế ááp dp dụụng đng đồồng th

ng thờời ci cảả hai xâu v

ng đượợc mc mộột lut luậật trong hai, ho

hai xâu vààoo c không t trong hai, hoặặc không

Không đặặt ra th

(cid:86)(cid:86) Không c (cid:86)(cid:86) ChChỉỉ ccóó ththểể ááp dp dụụng đư (cid:86)(cid:86) Không đ (cid:86)(cid:86) HHệệ ththốống gi

ng giữữ nguyên gi

t ra thứứ ttựự ccáác luc luậật trong h nguyên giáá trtrịị khi đ

t trong hệệ ththốốngng khi đảảo tho thứứ ttựự ccáác luc luậậtt

Check battery →→ Check battery Check battery → Check gas →→ Check gas Check gas → Replace battery →→ Replace battery Replace battery → Fill gas tank →→ Fill gas tank Fill gas tank → 4. Check gas AND No gas 4. Check gas AND No gas 4. Check gas AND No gas t start 2. Car won’’t start 2. Car won 2. Car won’t start t start 1. Car won’’t start 1. Car won 1. Car won’t start 3. Check battery AND Battery bad 3. Check battery AND Battery bad 3. Check battery AND Battery bad

→→ → →→ → →→ → →→ →

9/9/7070

Fill gas tank Fill gas tank Fill gas tank Check gas Check gas Check gas Check battery Check battery Check battery Replace battery Replace battery Replace battery

Nhận xét về

hạn chế

của SX Post

(cid:97) 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

(cid:97) Hạn chế chủ yếu của các sản xuất Post :

(cid:86) Không có các chiến lược điều khiển (control strategy) để định

hướng sử dụng luật

(cid:86) 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

(cid:86) 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/10/7070

Thuật toán Markov

n Markov (Markov Algorithm) : (cid:97)(cid:97) ThuThuậật tot toáán Markov (Markov Algorithm) : t năm 1954 c 1954 cảải ti t xâu vààoo

(cid:86)(cid:86) ĐĐềề xuxuấất năm ttừừ mmộột xâu v

c SX i tiếến cn cáách ch ááp dp dụụng cng cáác SX

ưu tiên t theo thứứ ttựự đ độộ ưu tiên

(cid:86)(cid:86) NhNhóóm cm cáác sc sảản xun xuấất theo th (cid:86)(cid:86) NNếếu SX c ththìì SX ti

ưu tiên cao nhấất không đư t không đượợc c ááp dp dụụng,ng,

(cid:86)(cid:86) ThuThuậật tot toáán Markov d

u SX cóó đ độộ ưu tiên cao nh SX tiếếp theo s

p theo sẽẽ đư đượợc c ááp dp dụụng vng vàà ccứứ ththếế titiếếp tp tụụcc n Markov dừừng nng nếếu :u :

(cid:153)(cid:153) ssảản xun xuấất cut cuốối ci cùùng không đư (cid:153)(cid:153) nnếếu su sảản xun xuấất đt đóó llàà cucuốối mi mộột giai đo

ng cho xâu, hoặặcc

A Markov algorithm: (cid:97)(cid:97) A Markov algorithm: (cid:86)(cid:86) is a

ng không đượợc c ááp dp dụụng cho xâu, ho t giai đoạạn đưn đượợc c ááp dp dụụngng

that uses grammar like rules to operate grammar--like rules to operate

(cid:86)(cid:86) Important difference from canonical system: now the set of rules

string rewriting system that uses of symbols strings of symbols

is a string rewriting system on on strings Markov algorithms have been shown to have sufficient power to be (cid:86)(cid:86) Markov algorithms have been shown to have sufficient power to be computation.. a general model of computation a general model of Important difference from canonical system: now the set of rules is is ordered ordered

11/11/7070

Markov Algorithm (MA)

(cid:97) The basic operation:

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

If none are found, stop executing the Algorithm

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

If the applied rule was a terminating one, stop executing the Algorithm

Return to step 1 and carry on

12/12/7070

Áp dụng thuật toán Markov

(cid:97)(cid:97) ThuThuậật tot toáán Markov c

n Markov cóó ththểể ááp dp dụụng cho t

ng cho từừng xâu con c

ng xâu con củủa a

bên tráái :i :

xâu vàào wo w∈∈Σ∗, b, bắắt đt đầầu tu từừ bên tr xâu v (cid:86)(cid:86) VVíí ddụụ : : ááp dp dụụng lu

cho xâu vàào o ggababkabkab

ng luậật t abab→→ hijhijcho xâu v

(cid:86)(cid:86) NhNhậận đưn đượợc xâu m

c xâu mớới i gghijhijkabkab

ng. Víí ddụụ : :

TiTiếếp tp tụục nhc nhậận đưn đượợc xâu m (cid:97)(cid:97) Ký tKý tựự đ đặặc bic biệệt t εε bibiềều diu diễễn xâu r

c xâu mớới i gghijhijkkhijhij n xâu rỗỗng. V xxóóa ta tấất ct cảả ccáác xuc xuấất hi

t hiệện cn củủa A trong m

t xâu a A trong mộột xâu

(cid:86)(cid:86) A A →→ εε

(cid:86)(cid:86) A x B (cid:97)(cid:97) CCáác ký hi

vai trò như biếến bin biểểu diu diễễn mn mộột t

A x B →→ B x AB x A nghnghịịch đch đảảo co cáác ký t c ký tựự A vA vàà BB c ký hiệệu đu đặặc bic biệệt kht kháác cc cóó vai trò như bi ký tký tựự bbấất kt kỳỳ đư đượợc vic viếết bt bởởi ci cáác chc chữữ ccáái thư

ng a, b, c... i thườờng a, b, c...

(cid:97)(cid:97) CCáác chc chữữ ccáái Hy l

a xâu i Hy lạạp p αα, , ββ ∉∉ Σ, ch, chỉỉ ccáác dc dấấu đu đặặc bic biệệt ct củủa xâu

13/13/7070

Ví

dụng thuật toán Markov

sử

(cid:97) Cho các SX có độ ưu tiên giảm

Luật Thànhcông(S) hoặcthấtbại(F) Xâu kếtquả

dụ dần như sau (ký hiệu ε hoạt động như là một biến trung gian) :

abc 1 F

εxy → yεx

2 F abc ε → ε

εabc

ε → ε 3 S

(cid:97) Cho xâu vào abc, cần di chuyển chữ cái đầu tiên a đến vị trí cuối cùng của xâu

(cid:97) Quá trình di chuyển được cho

1 S bεac

1 S bcεa

trong bảng

1 F bcεa

2 S bca

14/14/7070

Another Example of MA

(cid:97) Rules:

(cid:97) The Symbol string will change in

the following manner: "A" -> "apple" 1.

R1: "B" -> "bag" 2.

"I bought a B of apples from T S." . "S" -> "shop" 3.

R2: "T" -> "the" 4. "I bought a bag of apples from T S."

5. "the shop" -> "my brother" R3:

6. "I bought a bag of apples from T shop."

(cid:97) Symbol string :

"a never used" -> ."terminating rule" R4:

"I bought a bag of apples from the shop."

"I bought a B of As from T S." R5:

(cid:97) The algorithm will then terminate

"I bought a bag of apples from my brother."

15/15/7070

Another Example of MA

They rewrite binary numbers to (cid:97)(cid:97) They rewrite binary numbers to their unary counterparts their unary counterparts For example: 101 will be (cid:97)(cid:97) For example: 101 will be rewritten to a string of 5 rewritten to a string of 5 consecutive bars consecutive bars Rules: (cid:97)(cid:97) Rules: > "0||" "|0" --> "0||" "|0" > "0|" "1" --> "0|" "1" "0" --> ""> "" "0" Symbol string: (cid:97)(cid:97) Symbol string: "101" "101"

(cid:97) MA chọn áp dụng luật có độ ưu tiên nhất theo chiến lược điều khiển tất định

(definite control strategy)

(cid:97) Nếu không chọn được, MA tìm luật khác có độ ưu tiên thấp hơn (cid:97) MA thiếu tính hiệu quả trong những hệ chuyên gia có nhiều luật

If the algorithm is applied to the (cid:97)(cid:97) If the algorithm is applied to the above example, it will terminate above example, it will terminate after the following steps after the following steps Execution: (cid:97)(cid:97) Execution: "0|01" "0|01" "00||1" "00||1" "00||0|" "00||0|" "00|0|||" "00|0|||" "000|||||" "000|||||" "00|||||" "00|||||" "0|||||" "0|||||" "|||||" "|||||"

16/16/7070

Thuật toán mạng lưới (Rete Algorithm)

(cid:97) 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)

(cid:97) 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 : (cid:86) Đóng vai trò quan trọng khi giải quyết các bài toán thực tiễn chứa

(cid:86) NSD không phải chờ đợi nhiều thời gian để nhận được câu trả lời

(cid:97) 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

từ hàng trăm đến hàng ngàn luật

17/17/7070

RETE algorithm

p (pattern mattching) rấất nhanh đ

t nhanh đểể nhnhậận n

(cid:86)(cid:86) Cho ph

p so khớớp (pattern mattching) r

ch lưu giữữ thông tin c

thông tin củủa ca cáác c

c câu trảả llờời ti tứức thc thờời bi bằằng cng cáách lưu gi i (network) t trong mộột mt mạạng lưng lướới (network)

so khớớp lp lặặp đi l

(cid:86)(cid:86) Thay v

p đi lặặp lp lạại ci cáác sc sựự kikiệện mn mỗỗi li lầần n ááp dp dụụng mng mộột t

t trong mỗỗi chu tr

i chu trìình nh

nh nhậận thn thứức (recognize

act cycle), c (recognize--act cycle), i khi so khớớp p ng thay đốối khi so kh

(cid:97)(cid:97) ThuThuậật tot toáán mn mạạng lưng lướới :i : Cho phéép so kh đưđượợc câu tr luluậật trong m Thay vìì so kh luluậật trong m thuthuậật tot toáán mn mạạng lưng lướới chi chỉỉ nhnhììn nhn nhữững thay đ trong mỗỗi chu tr trong m

i chu trììnhnh

Activities (cid:97)(cid:97) Activities

Creates a decision tree where each node corresponds to a (cid:86)(cid:86) Creates a decision tree where each node corresponds to a hand side of a rule pattern occurring at the left--hand side of a rule pattern occurring at the left Each node has a memory of facts that satisfy the pattern (cid:86)(cid:86) Each node has a memory of facts that satisfy the pattern

Complete LHS as defined by a path from root to a leaf (cid:86)(cid:86) Complete LHS as defined by a path from root to a leaf

18/18/7070

The Rete-Algorithm

(cid:97) The net encodes the condition parts (IF-parts) of the rules (cid:97) The input are the changes of the working memory, i.e.:

(cid:86) New elements or deleted elements (cid:86) Modification of elements is simulated by first delete then add

(cid:97) The output is the conflict set (i.e., the applicable rules)

modified version)

19/19/7070

Rete example

Rules: IF x & y THEN p Rules: IF x & y THEN p

IF x & y & z THEN q IF x & y & z THEN q

y?y?

x?x?

z?z?

x?x?

y?y?

Pattern Pattern Network Network

Join Network Join Network

8 nodes 8 nodes

(http://aaaprod.gsfc.nasa.gov/teas/Jess/JessUMBC/sld010.htm)

20/20/7070

Rete example

Rules: IF x & y THEN p Rules: IF x & y THEN p

IF x & y & z THEN q IF x & y & z THEN q

x?x?

y?y?

z?z?

Pattern Pattern Network Network

Join Network Join Network

8 nodes 8 nodes

(http://aaaprod.gsfc.nasa.gov/teas/Jess/JessUMBC/sld010.htm)

21/21/7070

Rete example

Rules: IF x & y THEN p Rules: IF x & y THEN p

x?x?

y?y?

z?z?

Pattern Pattern Network Network

Join Network Join Network

8 nodes 8 nodes

(http://aaaprod.gsfc.nasa.gov/teas/Jess/JessUMBC/sld010.htm)

IF x & y & z THEN q IF x & y & z THEN q

22/22/7070

Matching Patterns

(cid:97) At each cycle the interpreter looks to see which rules have

conditions that can be satisfied

(cid:97) If a condition has no variables:

(cid:86) It will only be satisfied by an identical expression in working

memory

(cid:97) If the condition contains variables then

(cid:86) 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/23/7070

Rule-Based Production Systems

(cid:97) A production system consists of

(cid:86) a rule set / knowledge base / production memory (cid:86) a rule interpreter / inference engine (cid:153) that decides when to apply which rules

(cid:86) a working memory

(cid:153) that holds the data, goal statements, & intermediate results

(cid:97) Rules have the general form

→

IF THEN P1 Q1

, …, Pm

(cid:97) Patterns are usually represented by OAV vectors

, …, Qn

that make up the current state of the problem.

24/24/7070

Nguyên lý hoạt động của các máy suy diễn

t, khi mmááy duy di

(cid:97)(cid:97) Trong c

ng luậật, khi tri thứức chc chứứa thông tin liên quan đ

y duy diễễnn ( (MSD)MSD) a thông tin liên quan đếến n

Trong cáác hc hệệ ththốống dng dùùng lu đưđượợc khc khởởi đi độộng, ng, cơ scơ sởở tri th t biểểu bu bàài toi toáán cn cầần gin giảải :i : phpháát bi (cid:86)(cid:86) CCáác sc sựự kikiệện đã đư

n đã đượợc xc xáác nhc nhậận vn vàà ccáác sc sựự kikiệện sn sẽẽ đư đượợc thi

c thiếết t

llậập bip biểểu diu diễễn bn bàài toi toáán hay đ

n hay đííchch

(cid:86)(cid:86) NhNhữững tri th

o nên cơ sởở luluậật t

(cid:86)(cid:86) Suy lu

ch quyếết đt địịnh xem nh

nh xem nhữững lu

ng luậật nt nàào so sẽẽ llààm m

a mãn cáác sc sựự kikiệện, cn, cáác đc đốối tưi tượợngng a mãn n ưu tiên cáác luc luậật tht thỏỏa mãn

ng tri thứức thc thựực hc hàành thu nh thuộộc lc lĩĩnh vnh vựực tc tạạo nên cơ s MSD : (cid:97) Hoạt động suy diễn của MSD : Suy luậận bn bằằng cng cáách quy ththỏỏa mãn c (cid:86)(cid:86) ChChọọn ưu tiên c (cid:86)(cid:86) ThThựực hic hiệện cn cáác luc luậật ct cóó ttíính ưu tiên cao nh

nh ưu tiên cao nhấấtt

25/25/7070

Một số quy ước

(cid:97) Ta quy ước gọi :

(cid:86) RB (Rules Base) là cơ sởluật(CSL)

(cid:86) FB (Facts Base) là cơ sởsựkiện (CSSK)

(cid:97) Máy suy diễn họat động theo chu kỳ(cycle),

mỗi chu kỳ gồm hai giai đoạn(phase) :

(cid:86) Giai đoạn đánh giá ( EVALUATION), gồm ba bước(step) :

(cid:153) Thu hẹp (RESTRICTION. hay SELECTION)

(cid:153) So khớp (PATTERN−MATCHING, hay FILTERING)

(cid:153) Giải quyết xung đột (CONFLICT-RESOLUTION)

(cid:86) Thực hiện (EXECUTION)

26/26/7070

Chu kỳỳ Chu k

hhọọat đat độộng cơ b

a MSD ng cơ bảản cn củủa MSD

Giai đoạn 1 : EVALUATION

ThThựực hic hiệện cn cáác tiên đ

c tiên đềề

RESTRICTION RESTRICTION a trong RB R1 chứứa trong RB R1 ch a trong FB F1 chứứa trong FB F1 ch

CCáác quy t

c quy tắắc cc củủa R3a R3

FB vFB vàà

n 2 : Giai đoạạn 2 : Giai đo EXECUTION EXECUTION

PATTERN−−MATCHING MATCHING PATTERN nh giữữa R1 v F1F1 a R1 vàà so sáánh gi so s ttììm đưm đượợcc a trong R1 R2 chứứa trong R1 R2 ch

ththểể

thay đổổii

ccóó

RBRB bbịị thay đ

CCáác kc kếết qut quảả

khkháác cc cóó

ththểể

CONFLICT--RESOLUTION RESOLUTION CONFLICT ttììm đưm đượợcc a trong R2 R3 chứứa trong R2 R3 ch

TuTuỳỳ theo đi u khiểển cn củủa ma mááy :y : TuTuỳỳ theo đi u khiểển cn củủa ma mááy :y :

theo điềều khi ddừừng hay quay l ng hay quay lạạii theo điềều khi ddừừng hay quay l ng hay quay lạạii

27/27/7070

Mô hình so khớp luật trong một chu kỳ

R1 ∈

F1 ∈

TiTiếếp tp tụụcc

28/28/7070

Bước thu hẹp

(cid:97) Là bước đầu tiên của giai đoạn đánh giá (cid:97) Đầu vào :

(cid:86) Một sự kiện f ∈ FB (CSSK) và/hoặc luật r ∈ RB (CSL)

(cid:97) Đầu ra :

(cid:86) Một tập hợp con F1 ⊆ FB (cid:86) 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

(cid:97) Nguyên lý làm việc :

(cid:86) Ư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 Return

29/29/7070

Bước so khớp

(cid:97) Là bước thứ hai của giai đoạn đánh giá (cid:97) Đầu vào :

(cid:86) Một sự kiện f ∈ FB (CSSK) và/hoặc luật r ∈ RB (CSL)

(cid:97) Đầu ra :

(cid:86) 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

(cid:97) Nguyên lý làm việc :

(cid:86) 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

(cid:86) Tuỳ theo hệ thống mà có tiêu chuẩn thoả mãn khác nhau (cid:86) R2 được gọi là tập hợp xung độthay tập hợp tương tranh

(conflict set)

Return Return

30/30/7070

Bước giải quyết xung đột

(cid:97) Là bước thứ ba của giai đoạn đánh giá (cid:97) Đầu vào :

(cid:86) Tập hợp các luật trong tập xung đột R2

(cid:97) Đầu ra :

(cid:86) Tập hợp con các luật R3 ⊆ R2 cần được thực hiện

(cid:97) Nguyên lý làm việc :

(cid:86) Nếu R3 rỗng, không thực hiện giai đoạn EXECUTION của chu kỳ (cid:86) Nếu R3≠∅, chọn các luật dựa trên những tiêu chuẩn như sau :

(cid:153) Hoặc chọn theo thứ tự xuất hiện của luật với giả thiết RB đã

(cid:153) Hoặc chọn các luật có mối quan hệ với bối cảnh áp dụng liên

được sắp xếp theo một thứ tự nào đó

(cid:153) Hoặc chọn ngẫu nhiên : ưu tiên luật ít sử dụng, hoặc ít điều kiện

quan đến nghĩa (meaning/signification)

cần kiểm tra, ít biến cần xác định trước khi khởi động, v.v... Return Return

31/31/7070

Conflict Resolution

(cid:97) Selection a rule to fire

(cid:86) Production systems have a decision-making step between pattern

(cid:86) All rules that have their conditions satisfied are put on the agenda

matching & rule firing

(cid:86) The set of rules on the agenda is sometimes called the conflict set (cid:86) Conflict resolution selects which rule to fire from the agenda

(in CLIPS for ex.)

(cid:86) Sensibility (quick response to changes in WM)

(Packages like CLIPS provide more than one option for conflict resolution)

and Stability (continuous reasoning)

32/32/7070

Conflict Resolution in CLIPS

(cid:97) First, CLIPS uses salience to sort the rules (cid:97) Then it uses the other strategies to sort rules with

equal salience

(cid:97) CLIPS uses refraction, recency & specificity in the

form of following 7 strategies: (cid:86) The depth strategy (cid:86) The breadth strategy (cid:86) The simplicity strategy (cid:86) The complexity strategy (cid:86) The LEX strategy (cid:86) The MEA strategy (cid:86) It is possible also to set strategy to random

(cid:97) Syntax: (set-strategy )

33/33/7070

Giai đoạn thực hiện EXECUTION

(cid:97) Khi R3 rỗng, tuỳ theo HCG mà có hai cách xử lý như sau :

(cid:86) Cho MSD tự động dừng : những MSD như vậy được gọi là hoạt

(cid:86) Cho MSD xem xét lại tập hợp xung đột R2 của chu kỳ trước đó và

động theo chế độ điều khiển bắt buộc(irrevocable control regime)

(cid:97) Trường hợp không tìm được luật trong R2 :

(cid:86) Nếu sử dụng kết quả của các luật đã áp dụng, thì người ta cũng gọi những MSD như vậy hoạt động theo chế độ điều khiển bắt buộc

(cid:86) Ngược lại, người ta gọi MSD hoạt động theo chế độ thăm dò

áp dụng một luật khác của R2

(cid:97) Khi MSD quay lại giải quyết các xung đột trước đó, bằng cách khởi động lại các luật, người ta gọi máy hoạt động quay lui (backtrack)

(tentative control regime)

34/34/7070

The Working Memory

(cid:97) Role:

(cid:86) Holds data in the form of OAV vectors

(cid:86) These data are then used by the interpreter to activate the

rules of RB

(cid:86) The presence, or absence, of data elements in the Working

Memory will trigger rules by satisfying patterns on the LHS part of rules

(cid:86) Actions such as assert or modify the Working Memory

35/35/7070

Nhận xét về

chu kỳ cơ bản của MSD

(cid:97) 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

(cid:97) 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ỳ

(cid:97) Mỗi chu kỳ cơ bản của MSD :

(cid:86) Có liên hệ với chu kỳ lệnh của máy tính

(cid:86) 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)

(cid:86) 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 Return

36/36/7070

Phương pháp suy luận của các MSD

(cid:97) 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

(cid:97) Ba phương pháp hay gặp :

(cid:86) Phương pháp suy diễn tiến (Foward Chaining/Data-Driven)

(cid:86) Phương pháp suy diễn lùi (Backward Chaining/Goal-Driven)

(cid:86) Phương pháp phối hợp hai phương pháp này

(Mixed Chaining)

(cid:97) Ngoài ra còn một số phương pháp khác :

(cid:86) Phân tích phương tiện(means-end analysis)

(cid:86) Rút gọn vấn đề(problem reduction)

(cid:86) Kiểm tra lập kếhoạch(plan-generate-test)

(cid:86) Lập kếhoạch phân cấp(hierachical planning)...

37/37/7070

Phương pháp suy diễn tiến

(cid:97) Suy diễn tiến là lập luận từ các sự kiện, sự việc

để rút ra các kết luận (cid:86) Ví dụ :

(sự kiện) (kết luận)

để MSD tìm cách rút ra các kết luận có thể (cid:86) Kết luận có thể là những thuộc tính được gán giá trị (cid:86) Trong số những kết luận này, có thể có : (cid:153) những kết luận làm NSD quan tâm (cid:153) một số khác không nói lên điều gì (cid:153) một số khác có thể vắng mặt

Nếu thấy trời mưa trước khi ra khỏi nhà thìphải lấy áo mưa (cid:97) NSD cung cấp các sự kiện

38/38/7070

Các sự

kiện trong suy diễn tiến

(cid:97) Các sự kiện thường có dạng :

(cid:86) Atthibute = value (cid:86) Lần lượt các sự kiện trong cơ sở tri thức được chọn (cid:86) 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 đề

(cid:86) 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

(cid:86) 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

(cid:86) Sau khi mọi sự kiện đã được xem xét, kết quả được xuất ra

cho NSD

39/39/7070

Forward Chaining

(cid:97) The inference engine works from the initial content of the

workspace towards the final conclusion

(cid:97) Conclude from "A" and "A implies B" to "B"

A A A A

→ →

B B

(cid:97) Example:

It is raining If it is raining, the dress is wet -------------------------------------- The dress is wet

40/40/7070

Một ví

dụ

khác

41/41/7070

Palindrome Example

(cid:97) If we have the following grammar rules

(P1) $ -> a$a (P2) $ -> b$b (P3) $ -> c$c

(cid:97) They can be used Forward Chaining

to generate palindromes: (cid:86) apply P1, P1, P3, P2, to c: ⇒ aca, aacaa, caacaac, ...

(cid:97) To generate bacab

(cid:86) P1 is applied to the axiom cto get aca (cid:86) Then we apply P2 to get bacab (cid:86) Using a different order gives a different result (cid:86) If P2 is applied to cwe get bcb (cid:86) If P1 is applied after we get abcba

42/42/7070

Example 1

Workspace

base

A,B

Rule R1: R2: R3:

IF A AND B THEN D IF B THEN C IF C AND D THEN E

43/43/7070

Forward Chaining Model

Facts Facts

Rule Rule base base

Determine Determine possible possible rules to fire rules to fire

Conflict set

Rule found

Working Working memory memory

No rule found

Fire Fire rule rule Select Select rule to rule to fire fire Conflict Conflict resolution resolution strategy strategy

Exit if specified by the rule

ExitExit

44/44/7070

Thuật toán suy diễn tiến

(cid:97) Definitions :

RB,

Q : Sự

kiện đưa vào xử

lý

DEDUCE(Q)

FB Then

;

Q ∈

' Bắt đầu chu kỳ

xử

lý với r1 ∈RB

Call

Write "Success" CYCLE(RB)

; CYCLE(R1)

Write "Failure"

; Return

;

' Chọn một luật từ luật đã xử ' Loại bỏ

R1 lý

If

Write " Success"

; Return

;

Then CHOIX(r, R1) ; { r } R1 – FB Then RHF(r) Then

FB, RB, R1 ⊆ (cid:97) Algorithme : Procedure If Else Procedure R1 = ∅ If r ← R1 ← LHF(r) ∈ Q ∈ If Else

' Thêm vào FB các sự luật r đã xử ' Loại bỏ

' Không tìm thấy Q nhưng vẫn tiếp tục áp dụng luật r kiện mới FB ← RB ← lý Call

RHF(r) ; FB ∪ } ; { r RB – ; CYCLE(RB)

CYCLE(R1)

;

Else Return

Call ;

45/45/7070

Forward chaining algorithm

46/46/7070

Forward chaining Example 2.

WMWM

A B C D E

C D E

Fire

Match KBKB

Match BKBK

D

Z

Y ∧

Y Ÿ

E

Y

X Ÿ

B Ÿ

X Ÿ

B Ÿ

X Ÿ

B Ÿ

X Ÿ

B Ÿ

X

A C

L

A C

L

A C

L

A C

L

M

N

L Ÿ

Cycle 1

Cycle 2

Cycle 3

47/47/7070

Example 3. Diagnosing car problems

(cid:97) Rule 1: IF

the engine is getting gas AND the engine will turn over THEN the problem is spark plugs

(cid:97) Rule 2: IF

the engine does not turn over AND the lights do not come on THEN the problem is battery or cables

(cid:97) Rule 3: IF

the engine does not turn over AND the lights do come on

THEN the problem is the starter motor

(cid:97) Rule 4: IF

there is gas in the fuel tank AND there is gas in the carburettor

THEN the engine is getting gas

48/48/7070

(cid:97) Facts

The engine is getting gas

Working space

Rule 1 Rule 1 Rule 2 Rule 2 Rule 3 Rule 3 Rule 4 Rule 4

the engine the engine turns over turns over

Rule 1 Rule 1 Rule 2 Rule 2 Rule 3 Rule 3 Rule 4 Rule 4

49/49/7070

Working space

Rule 1 Rule 1 Rule 2 Rule 2 Rule 3 Rule 3 Rule 4 Rule 4

The engine is The engine is getting gas getting gas There is gas There is gas in the fuel tank in the fuel tank There is gas There is gas in the carburettor in the carburettor The engine The engine turns over turns over

50/50/7070

Example 4.

thị thị VÀ-HOẶC VÀ-HOẶC GG

Đồ Đồ (And-Or Tree) (And-Or Tree)

== EE DD C C

HH F F CC HH

II I QQ Q BB B QQ Q

→→ → →→ → →→ → →→ →

M M LL KK

== == ==

== BB AA O O NN JJ LL J J RR MM

LL II

QQ Q RR R SS S BB B FF F

→→ → →→ → →→ → →→ → →→ →

Rulesbase: (cid:97)(cid:97) Rulesbase: (cid:97) Rulesbase: K, L, M 1.1. K, L, M K, L, M 1. I, L, J 2.2. I, L, J I, L, J 2. 3.3. C, D, E C, D, E C, D, E 3. A, BA, B 4.4. A, B 4. L, N, O, P 5.5. L, N, O, P 5. L, N, O, P C, HC, H 6.6. 6. C, H R, J, M 7.7. R, J, M R, J, M 7. F, HF, H 8.8. F, H 8. GG 9.9. G 9. Factsbase: (cid:97)(cid:97) Factsbase: (cid:97) Factsbase: A, C, D, E, G, H, K A, C, D, E, G, H, K A, C, D, E, G, H, K

== == == ==

QQ SS

51/51/7070

Example 4.

Kết quả

suy diễn

(cid:97) Xây dựng đồ thị con VÀ-HOẶC từ đồ thị VÀ-HOẶC trên đây

(cid:86) Tìm được Q khi các sự kiện A, C, D và E được thiết lập

C C

F F

EE DD C C

J J RR

O O NN

BB AA

52/52/7070

Exercise 1.

(cid:97) Yêu cầu :

(cid:86) Vẽ đồ thị và-hoặc (cid:86) Áp dụng thuật toán suy diễn tiến

FF F AA A AA A XX X EE E HH H DD D AA A DD D

→→ → →→ → →→ → →→ → →→ → →→ → →→ → →→ → →→ →

Rulesbase: (cid:97)(cid:97) Rulesbase: (cid:97) Rulesbase: 1.1. B, D, E B, D, E B, D, E 1. G, DG, D 2.2. G, D 2. C, FC, F 3.3. 3. C, F BB 4.4. B 4. DD 5.5. D 5. X, AX, A 6.6. 6. X, A CC 7.7. C 7. X, CX, C 8.8. X, C 8. X, BX, B 9.9. X, B 9. Factsbase: (cid:97)(cid:97) Factsbase: (cid:97) Factsbase: B, CB, C B, C

để tìm kết quả H (cid:86) Có nhận xét gì ?

53/53/7070

Exercise 2.

(cid:97) Rules Base: (cid:97) Rules Base: R1: R1:

(cid:97) Facts Base: (cid:97) Facts Base: Bank's credit rating Bank's credit rating

UNKNOWN UNKNOWN

IF management competence is good IF management competence is good AND External credit rating is fair AND External credit rating is fair AND Bank's credit rating is AND Bank's credit rating is

marginal marginal THEN Loan is rejected THEN Loan is rejected IF Loan type is seasonal IF Loan type is seasonal

R2: R2:

0.18 Cash/current liabilities Cash/current liabilities 0.18 FAIR External credit rating External credit rating FAIR SEASONAL Loan Loan SEASONAL UNKNOWN Loan type UNKNOWN Loan type Management competence UNKNOWN Management competence UNKNOWN Profitability rating Profitability rating Solvency rating Solvency rating Tentative solvency rating Tentative solvency rating

HIGH HIGH UNKNOWN UNKNOWN LOW LOW

AND Profitability rating is high AND Profitability rating is high AND Solvency rating is low AND Solvency rating is low THEN Bank's credit rating is THEN Bank's credit rating is marginal marginal IF Cash/current liabilities > 0.1 IF Cash/current liabilities > 0.1

R3: R3:

AND Tentative solvency rating is AND Tentative solvency rating is

low low THEN Solvency rating is low THEN Solvency rating is low

54/54/7070

Example knowledge base contd.

... it is a crime for an American to sell weapons to hostile nations:

American(X) Weapon(Y) Criminal(X) ∧ ∧ Sells(X,Y,Z) ∧

Nono … → Missile(X): Hostile(Z) ∧

Owns(Nono,X) has some missiles, i.e., ∃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“:

Hostile(X)

Enemy(X,America) → West, who is American … American(West)

The country Nono, an enemy of America …

Enemy(Nono,America)

55/55/7070

Forward chaining proof

Criminal(West) Criminal(West) Criminal(West)

Weapon(M1) Weapon(M1) Weapon(M1)

Sells(West,M1,Nono) Sells(West,M1,Nono) Sells(West,M1,Nono)

Hostile(Nono) Hostile(Nono) Hostile(Nono)

American(West) American(West) American(West)

Missile(M1) Missile(M1) Missile(M1)

Owns(Nono,M1) Owns(Nono,M1) Owns(Nono,M1)

Enemy(Nono,America) Enemy(Nono,America) Enemy(Nono,America)

56/56/7070

Phương pháp suy diễn lùi

(cid:97) Phương pháp suy diễn lùi :

(cid:86) 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)

(cid:86) Đầu vào có dạng một câu hỏi «Cho biết giá trị thuộc tính đích (goal) A ?» (cid:86) 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

(cid:97) Ví dụ :

(cid:86) 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)

(cid:86) Để củng cố giả thuyết này,

ta sẽ hỏi người đó xem có phải trời mưa không ?

(cid:86) 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 (cid:86) Nghĩa là trời mưa nên phải cầm áo mưa và áo quần bị ướt

57/57/7070

Ý tưởng thuật toán suy diễn lùi

(cid:97) Với mỗi thuộc tính đã cho, người ta định nghĩa nguồn của nó :

(cid:86) Nếu thuộc tính xuất hiện như là tiền đề của một luật (phần đầu

(cid:86) 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

(cid:86) 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

(cid:86) 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 (cid:86) 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

(cid:86) Nếu các luật thoã mãn, thuộc tính kết luận sẽ được ghi nhận

của luật), thì nguồn sẽ thu gọn thành một câu hỏi

58/58/7070

Backward Chaining

(cid:97) Conclude from "B" and "A implies B" to "A"

B B A A

→ →

B B

A A

(cid:97) Example:

The dress is wet If it is raining, the dress is wet -------------------------------------- It is raining

59/59/7070

Backward Chaining

60/60/7070

Thuật toán suy diễn lùi

(cid:97) Definitions :

FB, RB, R1 ⊆

Q : Sự

kiện đưa vào xử

lý

(cid:97) Algorithme :

Procedure

DEDUCE (Q)

If

Write " Success"

;

Q ∈

BF Then

Else

Push BR, BF

;

1 ;

IP ≠

Call

CYCLE(BR, BF)

;

Return;

61/61/7070

Thuật toán suy diễn lùi

CYCLE(ER, EF)

: ER, EF, r

; ' Các biến làm việc địa phương

Procedure Var If

Then

; ' Lấy một luật ở đỉnh Stack

Write " Failure"

; Return;

kiện

ER = ∅ IP -1 IP ≠ If IP = 0 Then ER ≠ Else EF ≠ Call CHOOSE(r, ER)

Luật ở đỉnh Stack chưa xét ở đỉnh Stack; Các sự CYCLE(ER, EF) ; Return; ; ' Chọn một luật

; ' Loại bỏ

luật đã xét ở

r ≠ ER ≠ If

; Return;

Write " Success"

RHF(r)), BR

ER – LHS(r) ∈ If RHF(r) ∈ Else

; ' (IP ≠ IP +1)

phần tử ngay dưới đỉnh Stack; cho luật r ở đỉnh

;

màu đỏ;

kiện

ở đỉnh Stack ; ; Return;

Các luật ở đỉnh chưa đánh dấu. Thông thường là Các sự CYCLE(ER, EF) ; Return;

Call

{ r } EF Then Q Then Push (EF ∪ Đánh dấu màu đỏ Đánh dấu màu đỏ Đánh dấu màu xanh cho luật r tại đỉnh - ER ≠ EF ≠ Call CYCLE(ER, EF)

62/62/7070

Example 4. Backward Chaining

GG thị thị VÀ-HOẶC VÀ-HOẶC

Đồ Đồ (And-Or Tree) (And-Or Tree) == EE DD C C

HH F F CC HH

M M LL KK

== == ==

== BB AA O O NN JJ LL J J RR MM

PP LL II

II I QQ Q BB B QQ Q QQ Q RR R SS S BB B FF F →→ → →→ → →→ → →→ → →→ → →→ → →→ → →→ → →→ → == == == ==

QQ SS Rulesbase: (cid:97)(cid:97) Rulesbase: (cid:97) Rulesbase: K, L, M 1.1. K, L, M K, L, M 1. I, L, J 2.2. I, L, J 2. I, L, J C, D, E 3.3. C, D, E 3. C, D, E A, BA, B 4.4. A, B 4. L, N, O, P 5.5. L, N, O, P 5. L, N, O, P C, HC, H 6.6. 6. C, H R, J, M 7.7. R, J, M 7. R, J, M F, HF, H 8.8. 8. F, H GG 9.9. G 9. Factsbase: (cid:97)(cid:97) Factsbase: (cid:97) Factsbase: A, C, D, E, G, H, K A, C, D, E, G, H, K A, C, D, E, G, H, K Question (Goal): (cid:97)(cid:97) Question (Goal): (cid:97) Question (Goal): QQ Q

63/63/7070

Đồ

Và-Hoặc thiết lập Q

thị

LuLuậật 3t 3 Luật 3

EE DD C C

KhKhởởi đi độộng 4ng 4 Khởi động 4

LuLuậật 1t 1 Luật 1

M M LL KK

KhKhởởi đi độộng 2ng 2 Khởi động 2

LuLuậật 4t 4 Luật 4

BB AA == JJ LL

LuLuậật 2t 2 Luật 2

KhKhởởi đi độộng 3ng 3 Khởi động 3

KhKhởởi đi độộng 1ng 1 Khởi động 1

== ==

64/64/7070

Áp dụng thuật toán suy diễn lùi

QQ Q A C D E G H K A C D E G H K A C D E G H K

Luật 2 (khởi động 1) Luật 4 (khởi động 3)

BB B A C D E G H K A C D E G H K A C D E G H K A C D E G H K A C D E G H K A C D E G H K I J LI J L I J L

Luật 1

(khởi động 2) Luật 3 (khởi động 4)

A C D E G H K A C D E G H K A C D E G H K M J LM J L M J L A C D E G H K A C D E G H K A C D E G H K

Success Failure

65/65/7070

Exercise

(cid:97) Áp dụng thuật toán suy diễn lùi cho ví dụ Colonel West

66/66/7070

Data-driven ×

Goal-driven

seenseenseen hereherehere holiday holiday holiday

data driven data driven

absent absent absent

building building building home home home

goal driven goal driven

finefinefine sicksicksick

67/67/7070

Data-driven ×

Goal-driven

(cid:97) Goal Driven (backward chaining) ~ blood diagnostic,

theorem proving

(cid:86) Limited number of goal hypothesis

(cid:86) Data shall be acquired, complicated data about the object

(cid:86) Less operators to start with at the goal rather than at the data (cid:97) Data Driven (forward chaining) ~ configuration, interpretation,

(cid:86) reasonable set of input data

(cid:86) data are given at the initial state

(cid:86) huge set of possible hypothesis

(cid:97) Taxonomy of rules, meta-rules, priorities, …

68/68/7070

Forward or Backward Reasoning?

(cid:97) Four major factors

(cid:97) 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