Bài giảng: Các Hệ cơ sở tri thức

ệ ơ ở

ứ

Các H c s tri th c KBS: Knowledge Based Systems

ễ ệ ố

Nguy n Đình Thuân Khoa H th ng Thông tin ĐH Công ngh thông tin

ệ

TP HCM 1-2011

1

H c s tri th c

ệ ơ ở

ứ

ề ệ ơ ở

ậ

ễ

ụ

ờ

Ch Ch Ch Ch Ch Ch

ươ ươ ươ ươ ươ ươ

ng 1: T ng quan v H c s tri th c ổ ứ ng 2: Bi u di n và suy lu n tri th c ứ ể ng 3: H MYCIN ệ ng 4: H h c ệ ọ ng 5: H th ng m cho các bi n liên t c ế ệ ố ng 6: Công c t o l p H CSTT ụ ạ ậ

ệ

Tài li u tham kh o

ệ

ả

[1] McGraw-Hill/Irwin. Management information

system The McGraw-Hill Companies, Inc. 2008 .

[2] Robert I. Levine. Knowledge based systems.

Wissenschafs Verlag, 1991

ệ ơ ở

ế

th c. ĐHQG TP H Chí Minh. 2007

[3] Hoàng Ki m. Giáo trình Các h c s tri ồ

ứ

Ch

ng 1: T ng quan v H c s tri th c

ươ

ề ệ ơ ở

ứ

ổ

ứ

1.1 Khái ni m v H C s tri th c ệ  H c s tri th c là ch

ươ t k đ mô hình hoá kh năng gi

ng trình máy tính i ả

đ ả quy t v n đ c a chuyên gia con ng

ệ ơ ở c thi ượ ế ấ

ề ệ ơ ở ứ ế ế ể ề ủ ệ

i. ườ ứ

ự

ệ

ố

 H CSTT là h th ng d a trên tri th c, cho phép mô hình hoá các tri th c c a chuyên ứ ủ i quy t v n đ gia, dùng tri th c này đ gi ề ế ấ ể ả ứ ph c t p thu c cùng lĩnh v c. ự

ộ

ọ

ố

ứ ạ ế

ứ

ậ

ệ ươ ơ ở

quan tr ng trong H CSTT là: tri ng ng v i th c chuyên gia và l p lu n, t ớ ậ h th ng có 2 kh i chính là C s tri th c và ứ ố đ ng c suy di n.

 Hai y u t ứ ệ ố ộ

ễ

1.1 Khái ni m v H CSTT (Ti p)

ề ệ

ế

ệ

ượ

ộ

 H Chuyên gia là m t lo i c s tri th c đ ứ ộ ụ ể

ệ

ườ

ệ ự

ụ

ấ

i đã đ

ự ườ

ượ

ệ

ệ ạ ơ ở t k cho m t lĩnh v c ng d ng c th . thi ự ứ ế ế ụ Ví d : H Chuyên gia v ch n đoán b nh ệ ề ụ ẩ trong Y khoa, H Chuyên gia ch n đoán h ng ỏ ẩ ng dây đi n tho i,… hóc c a đ ạ ệ ủ  H Chuyên gia làm vi c nh m t chuyên gia ư ộ ệ th c th và cung c p các ý ki n d a trên kinh ế nghi m c a chuyên gia con ng c ủ đ a vào H Chuyên gia. ệ

1.1 Khái ni m v H CSTT (Ti p)

ề ệ

ế

ệ

ứ

ự

ơ ở

ồ

ậ

ứ ệ

ư ự ệ

ộ

 C s tri th c: Ch a các tri th c chuyên sâu ơ ở v lĩnh v c nh chuyên gia. C s tri th c ề bao g m: các s ki n, các lu t, các khái ni m và các quan h . ệ ễ ơ

ứ

ủ

ậ

ạ ộ

ề ấ

ộ

ứ ư

ớ

ứ ồ

ế

 K s tri th c (Knowledge Engineer): ng

 Đ ng c suy di n: b x lý tri th c theo mô ộ ử hình hoá theo cách l p lu n c a chuyên gia. ậ Đ ng c ho t đ ng trên thông tin v v n đ ề đang xét, so sánh v i tri th c l u trong c s ơ ở tri th c r i rút ra k t lu n. ậ ứ

i ườ t k , xây d ng và th nghi m H Chuyên ử

ỹ ư ế ế

ệ

ự

thi gia.

1.2 C u trúc c a H CSTT

ủ

ệ

ấ

1.2 C u trúc c a H CSTT(ti p)

ủ

ế

ệ

ấ

ệ

ự

ế

ệ ữ

i máy (User Interface): ậ

ầ

ề

ừ

ự

ả

ả ờ ệ

ề ộ ử

nhiên và các h th ng t

ồ ươ

ệ ố

i thích (Explanation system):

i thích các

ng tác khác. ả

ủ

ơ

ễ

ớ

ệ

ớ

ự ệ ự ề

ề ề ấ

ệ ớ ứ

ứ ậ

ể

1. Giao di n ng Th c hi n ườ giao ti p gi a H Chuyên gia và User. Nh n các thông ệ User (các câu h i, các yêu c u v lĩnh v c) và đ a tin t ỏ i, các l ra các câu tr l i khuyên, các gi i thích v lĩnh ờ i máy bao g m: Menu, b x lý v c đó. Giao di n ng ườ ự ngôn ng t ữ ự 2. B gi ộ ả ho t đ ng khi có yêu c u c a User. ầ ạ ộ Quá trình 3. Đ ng c suy di n (Inference Engine): ộ trong H Chuyên gia cho phép kh p các s ki n trong vùng nh làm vi c v i các tri th c v lĩnh v c trong c ơ i s tri th c, đ rút ra các k t lu n v v n đ đang gi ả ế ở quy t. ế

1.2 C u trúc c a H CSTT(ti p)

ủ

ệ

ế

ấ

chuyên gia con ng

ệ

ơ ở ữ

ể

ầ ơ ở ậ

ư ơ ở

ứ ệ

ả

ứ

ồ ớ

ầ

ự ệ

ộ ề

ủ

ệ

Làm 4. B ti p nh n tri th c (Knowledge editor): ộ ế ứ ậ nhi m v thu nh n tri th c t i ậ ườ ừ ứ ụ k s tri th c và User thông qua các (human expert), t ứ ừ ỹ ư yêu c u và l u tr vào c s tri th c ứ ữ ứ L u tr , bi u di n các tri th c mà h 5. C s tri th c: ệ ễ đ m nh n, làm c s cho các ho t đ ng c a h . C s ơ ở ủ ạ ộ t (rules). tri th c bao g m các s ki n (facts) và các l ụậ ự ệ M t ph n 6. Vùng nh làm vi c (working memory): ệ c a H Chuyên gia ch a các s ki n c a v n đ đang ấ ứ ủ xét.

1.3 Các đ c tính c a H CSTT

ủ

ệ

ặ

ộ

ỏ

ề

ố

ứ

ứ ễ

ơ ở ờ

ố

1. Tách tri th c ra kh i đi u khi n: c s tri th c và đ ng ể c suy di n là các kh i tách r i: m t kh i ch a tri ơ th c còn kh i kia là c ch gi ế ả ứ

2. Tri th c c a chuyên gia: các tri th c đ

ứ

ủ

ứ

ề

ể

i có k năng gi

ế

ề

ấ

ỹ ả

ậ

ả

i quy t đúng v n đ và ả i quy t hi u qu . H có kh năng l p lu n h n ậ ả ữ

ườ

ự

ườ ọ ệ i khác trong lĩnh v c đó.” 3. T p trung ngu n chuyên gia: M i chuyên gia ch gi

ồ

ỗ

ự

ề

ấ

ứ ố ộ i quy t v n đ . ề ế ấ c thu n p t ạ ừ ượ nhi u chuyên gia hi u sâu v lĩnh v c đang gi i ả ự ề quy t.ế Expert: “Ng gi ế nh ng ng i ậ ỉ ả quy t các v n đ trong lĩnh v c c a mình. Nên chia nh bài toán ch n đoán theo các h th ng nh h n.

ủ ệ ố

ế ỏ

ỏ ơ

ẩ

1.3 Các đ c tính c a H CSTT (ti p) ủ

ế

ệ

ặ

ậ

ệ

ự

ể ể ệ

5. L p lu n may r i: Kinh nghi m giúp các chuyên gia

ế

ả

ẳ

ạ

ậ

ớ

i pháp. ủ ầ ứ ấ

ệ ỏ ượ

ề

ắ

ộ

7. Ch a kh năng suy di n, m c đ sâu s c cao, có h c trong quá trình suy

c nhi u thông tin. ễ ki m tra, t

ứ ự ọ

ự ể

4. L p lu n trên các ký hi u: Chuyên gia dùng các ký ệ ậ hi u đ th hi n tri th c, thay vì th c hi n vi c x ử ứ ệ lý s .ố ệ ủ ậ ậ nhanh chóng tìm đ n các gi 6. L p lu n v i thông tin không đ y đ : ch ng h n, ậ bác sĩ khám b nh nhân vào c p c u trong hoàn c nh không h i đ ả ả ứ kh năng t ả lu n. ậ

(ti p)ế

1.3 Các đ c tính c a H CSTT

ủ

ệ

ặ

Đ i t

ng so sánh

Ch

ố ượ

ươ

Các h CSTT ệ

ng trình bình th

ngườ

X lýử

Số

Ký h uịệ

S d ng ử ụ

Thu t toán ậ

Kinh nghi mệ

T ch c thông tin

ổ ứ

ề

ể

Tri th c tách r i đi u khi n ể ờ

ứ

ề

c tích h p

Thông tin và đi u khi n đ ợ ượ

Kh năng thay đ i ổ

ả

Khó thay đ iổ

D thay đ i ổ

ễ

Thông tin chính xác

Thông tin không chính xác

Tính ch c ch n ắ ắ

Giao di n câu l nh

nhiên có gi

Giao di nệ

ệ

ạ ự

ả

H i tho i t ộ thích

Lo i k t qu ạ ế

ả

K t qu cu i cùng ả ố

ế

ả

Khuy n cáo kèm theo gi thích

Tính t

i ch p nh n đ

i uố ư

Nghi m t ệ

i u ố ư

L i gi ờ

ả

c ậ ượ

ấ

B ng 1.1: So sánh H chuyên gia và ch

ng trình bình th

ệ

ả

ươ

ườ

1.4 H h tr ra quy t đ nh

ệ ỗ ợ

ế ị

ỗ ợ

i s d ng

ươ

ứ ạ ộ

ớ

ườ ử ụ

ế ị

ườ

ủ

i qu n lý ả

ể

ả

DSS (Decision Support System)  Ch c năng: H tr ra quy t đ nh ế ị  Ho t đ ng theo cách t ng tác v i ng Các tính ch t c a DSS: ấ ủ  H ng đ n các quy t đ nh c a ng ướ ế  Uy n chuy n v i hoàn c nh ớ ể  Tr l ố ỏ ả ờ  Do ng

i s d ng kh i đ ng và ki m soát

i câu h i trong tình hu ng ườ ử ụ

ở ộ

ể

1.5 H h c

ệ ọ

 Trong nhi u tinh hu ng, s không có s n tri th c

ứ

ố

ề

ẽ

ẵ

chuyên gia lĩnh

nh :ư – K s tri th c c n thu nh n tri th c t ầ

ỹ ư ứ ừ ứ ậ

ả

v c.ự – C n bi t các lu t mô t ậ ế ầ – Bài toán không đ ượ lĩnh v c c th . ự ụ ể ễ ườ ể ng minh theo lu t, s ự ậ

 Có hai ti p c n cho h th ng h c:

c bi u di n t ki n hay các quan h . ệ ệ

ọ

– H c t

ế ký hi u: bao g m vi c hình th c hóa, s a ch a

ữ ứ ử

ọ ừ các lu t t ậ ườ

d li u s : đ

ệ ố ậ ồ ệ ệ ng minh, s ki n và các quan h . ệ ự ệ ữ

ụ

ố ượ ướ ạ ệ ố ỹ ố ậ

c mô hình d ố ư ố ọ ố ạ

ồ i di truy n, bài toán t ố ạ ậ

ề ố ạ ỹ

– H c t c áp d ng cho nh ng h th ng ọ ừ ữ ệ đ i d ng s liên quan đ n các k thu t ượ ế nh m t i u các tham s . H c theo d ng s bao g m ằ m ng Neural nhân t o, thu t gi i ạ ả u truy n th ng. Các k thu t h c theo s không t o ra ậ ọ ư CSTT t

ố ng minh. ề ườ

1.6 H đi u khi n m

ệ ề

ể

ờ

 M hóa: Chuy n đ i giá tr rõ đ u vào thành

ầ

ổ

ị

ờ

ể các vector m ờ

 Xác đ nh các lu t h p thành và thu t toán

ậ ợ

ậ

ị ị

 Gi

xác đ nh giá tr m ị ờ ng pháp đi m tr ng tâm ể

i m : Ph ờ

ươ

ả

ọ

1.7 ng d ng c a H C s tri th c

ệ ơ ở

Ứ

ụ

ủ

ứ

i (Interpretation): Mô t

tình hu ng

1. Di n gi ễ

ả

ố

các d li u thu th p đ

ả ữ ệ

ậ

ứ

ượ ư

ả

ộ

ự t k (Design): L a ch n c u hình phù

2. D báo (Prediction): đ a ra các tri th c v ề d báo m t tình hu ng: d báo giá c , … ố ự

ế ế

ấ

h p, ví d : s p x p công vi c.

ự ự 3. Thi ợ

ụ ắ

ế

ọ ệ

ẩ

ữ ệ

ự

i h ng hóc.

quan sát đ

4. Ch n đoán (Diagnosis): D a vào các d li u c, xác đ nh các l ị

ỗ ỏ

ượ

1.7 ng d ng c a H C s tri th c

ệ ơ ở

ứ (ti p)ế

Ứ

ụ

ủ

5. V ch k ho ch (Planing): t o l p các

ạ

ậ

ế

ạ ng án hành đ ng.

ộ

6. D n d t (Monotoring): So sánh d li u và

ạ ph ươ ẫ

ữ ệ

ắ

ạ ộ

các ph

ng pháp

ả

ươ

ệ ố 8. Gi ng d y (Instruction): S a ch a các l

i ỗ

ử

9. Đi u khi n (Control): d n d t dáng đi u

ế ỡ ố ắ ả c a ng ủ ề

ữ ọ ậ ắ

ệ

các k t qu ho t đ ng. ả 7. G r i (Debugging): Mô t kh c ph c c a h th ng. ụ ủ ạ i h c trong quá trình h c t p. ườ ọ ể ể ủ

ẫ t ng th c a h th ng. ổ

ệ ố

Thông tin v môn h c ề

ọ

Đánh giá Đánh giá

Ph ng pháp đánh giá Tr ng s [%] ươ ố ọ

15% Chuyên c n, bài t p trên l p ớ ầ ậ

15% Cài đ tặ

Ti u lu n, báo cáo 20% ể ậ

08/23/12

www.lhu.edu.vn

50% Thi cu i h c kỳ ố ọ

ng 2: Bi u di n và suy lu n tri

ể

ễ

ậ

ươ

Ch th cứ

ở ầ

ứ ứ ệ

ộ ườ ể ậ

ủ ụ ủ ụ ế ề ượ ộ ấ ấ

ứ ể ạ ơ

ứ ẳ ặ ạ

ể ẳ ị

2.1. M đ u ứ .  tri th cứ , lĩnh v cự và bi u di n tri th c ể ễ c chia thành 5 lo i 2.2. Các lo i tri th c: đ ạ ạ ượ ứ cách th c gi Tri th c th t c: mô t i quy t m t v n đ . Lo i ủ ụ ạ ề ộ ấ ế ả ứ ả 1. i pháp đ th c hi n m t công vi c nào tri th c này đ a ra gi ệ ể ự ả ư đó. Các d ng tri th c th t c tiêu bi u th ng là các lu t, ứ ạ c, l ch trình và th t c. chi n l ị ế ượ c th y nh th t m t v n đ đ Tri th c khai báo: cho bi ư ứ ế i nào. Lo i tri th c này bao g m các phát bi u đ n gi n, d ướ ả ồ d ng các kh ng đ nh logic đúng ho c sai. Tri th c khai báo ị cũng có th là m t danh sách các kh ng đ nh nh m mô t ả ộ đ y đ h n v đ i t ề ố ượ

ằ ng hay m t khái ni m nào đó. ủ ơ ệ ầ ộ

2.2. Các lo i tri th c ạ

ứ (ti p)ế

3. Siêu tri th c: ứ mô t

ạ ả tri th c v tri th c

ọ ự ứ ề ấ

ề ế

ứ ứ ứ i quy t v n đ b ng cách h ỉ ộ ấ ệ ướ

ề ả ể ề ậ ố ử ụ ề ằ ơ ề

ế ấ ả các “ ể ẫ ả ắ ậ 4. Tri th c heuristic: ứ

ậ ậ

ể

ộ ố ệ ế ậ ả ơ

ứ . Lo i tri th c này ứ giúp l a ch n tri th c thích h p nh t trong s các tri th c khi ợ i quy t m t v n đ . Các chuyên gia s d ng tri th c này gi ng đ đi u ch nh hi u qu gi ả ả các l p lu n v mi n tri th c có kh năng h n c . ứ ả kinh nghi mệ " đ d n d t mô t ti n trình l p lu n. Tri th c heuristic là tri th c ứ không b m ả ế ứ i quy t v n đ m hoàn toàn 100% chính xác v k t qu gi ả ả ề ế ả ế ấ ng dùng các tri th c khoa h c nh đ . Các chuyên gia th ư ọ ứ ườ ề s ki n, lu t, … sau đó chuy n chúng thành các tri th c ậ ứ ự ệ heuristic đ thu n ti n h n trong vi c gi i quy t m t s bài ệ ể toán.

5. Tri th c có c u trúc:

ấ ả

ứ ệ ố

ể ồ

ứ mô t tri th c theo c u trúc. Lo i ạ ứ mô hình t ng quan h th ng theo quan tri th c này mô t ổ đi m c a chuyên gia, bao g m khái ni m, khái ni m con, và ệ ủ ch c năng và m i liên h gi a các tri ng; di n t các đ i t ố ố ượ th c d a theo c u trúc xác đ nh. ấ ự

ệ ệ ữ ễ ả ứ

ứ ị

Ví d : Hãy phân lo i các tri th c sau ạ

ụ

ứ

ố ẹ

ọ

ạ

ế ế

i Greedy

1. Nha Trang là thành ph đ p. 2. B n Lan thích đ c sách. 3. Modus Ponens. 4. Modus Tollens. 5. Thu t toán tìm ki m BFS ậ 6. Thu t toán tìm ki m DFS ậ 7. Thu t toán A ậ 8. Thu t gi ậ

ả

Ví d : Hãy phân lo i các tri th c sau(ti p)

ứ

ụ

ế

ạ

9. M t s cách chi u t

ế ướ

ng trong vi c ch i c ơ ờ ệ

ọ

ế

ộ ố t ng. ướ 10. H th ng các khái ni m trong hình h c. ệ ệ ố 11. Cách t p vi t ch đ p. ậ ữ ẹ ế t quy n sách v H chuyên gia. 12. Tóm t ề ệ ể ắ 13. Ch n lo i c phi u đ mua c phi u. ể ế ạ ổ 14. Ch n các thông tin v các lo i c phi u trên ề

ổ ạ ổ

ế

ng.

ọ ọ th tr ị ườ

2.3. CÁC K THU T BI U DI N TRI TH C

Ứ

Ậ

Ỹ

Ễ

ng-Thu c tính-Giá tr ị

ộ

ố ượ

2.3.1 B ba Đ i t ộ 2.3.2 Các lu t d n ậ ẫ 2.3.3 M ng ng nghĩa ữ ạ 2.3.4 Frames 2.3.5 Logic

2.3.1 B ba Đ i t ộ

ố ượ

ng-Thu c tính-Giá tr ị

ộ

 M t s ki n có th đ

ộ ự ệ ể

ể ượ ủ ị ủ ệ ố ượ ụ ị

ị

ỏ ự ệ ố ượ ượ ọ ộ

ng-Thu c tính-Giá tr (O-A-V – Object-Attribute-Value). c dùng đ xác nh n giá tr c a m t ộ ậ ng. Ví d , m nh đ thu c tính xác đ nh c a m t vài đ i t ộ ề "qu bóng màu đ " xác nh n "đ " là giá tr thu c tính "màu" ỏ ộ ả c g i là b ba c a đ i t ả ủ Đ i t ố ượ ộ ậ ng "qu bóng". Ki u s ki n này đ ể ị ộ

Hình 2.1. Bi u di n tri th c theo b ba O-A-V

ứ

ể

ễ

ộ

ng-Thu c tính-Giá tr (ti p)

2.3.1 B ba Đ i t ộ

ố ượ

ị ế

ộ

ộ ề ể ộ ố ượ

 Trong các s ki n O-A-V, m t đ i t ự ệ ể

ị ơ ớ

ị ộ ọ ề ượ

ệ ệ ứ ễ ể

t. ế ứ

ả ả ả

ng có th có nhi u thu c tính v i các ki u giá tr khác nhau. H n n a m t thu c tính ộ ộ ữ c g i là các s cũng có th có m t hay nhi u giá tr . Chúng đ ự ể ị (single-valued) ho c ặ đa tr ị (multi-valued). Đi u này ki n ệ đ n trơ ề cho phép các h tri th c linh đ ng trong vi c bi u di n các tri ộ th c c n thi ầ ự ệ ắ ự ệ ế

ệ ộ

ắ ử ụ ề ể ả

ắ ố ầ ả

 Các s ki n không ph i lúc nào cũng b o đ m là đúng hay sai v i đ ch c ch n hoàn toàn. Ví th , khi xem xét các s ki n, ớ ộ đ tin c y i ta còn s d ng thêm m t khái ni m là ng ậ . ộ ườ ng pháp truy n th ng đ qu n lý thông tin không ch c Ph ắ ố ươ ch n là s d ng nhân t ch c ch n CF (certainly factor). Khái ắ ắ ố ử ụ h th ng MYCIN (kho ng năm 1975), ni m này b t đ u t ừ ệ ắ ệ i cho các thông tin suy lu n. Khi đó, trong s dùng đ tr l ự ậ ể ả ờ ki n O-A-V s có thêm m t giá tr xác đ nh đ tin c y c a nó là ị ẽ ệ CF.

ủ ậ ộ ộ ị

2.3.2 Các lu t d n

ậ ẫ

ấ

ế

ể

ứ

ậ

ữ

ậ ừ

 Lu t là c u trúc tri th c dùng đ liên k t thông tin đã ậ bi t v i các thông tin khác giúp đ a ra các suy lu n, ế ớ k t lu n t ế

 Trong h th ng d a trên các lu t, ng ự

ườ

ậ

ự

ư nh ng thông tin đã bi t. ế ậ ộ ậ ố

ệ ố ứ ơ ở

ứ

ủ

ệ

ậ

ư ố ộ ệ ố

ớ ử

ả

ệ ậ ượ

ậ ằ

ả

ộ

ọ

i ta thu th p các tri th c lĩnh v c trong m t t p và l u chúng trong c s tri th c c a h th ng. H th ng dùng các lu t này cùng v i các thông tin trong b nh đ ớ ể i bài toán. Vi c x lý các lu t trong h th ng d a gi ự trên các lu t đ c qu n lý b ng m t module g i là ễ . b suy di n

ộ

2.3.2 Các lu t d n

ậ ẫ (ti p)ế

ạ

ậ ơ ả

ạ

Các d ng lu t c b n: 7 d ng 1. Quan h : ệ

c ượ ở ộ

2. L i khuyên:

c ở ộ ượ

ướ

ở ộ ệ ố t ệ ố

IF Bình đi n h ng ệ ỏ THEN Xe s không kh i đ ng đ ẽ ờ IF Xe không kh i đ ng đ THEN Đi b ộ 3. H ng d n ẫ IF Xe không kh i đ ng đ THEN Ki m tra h th ng đi n ệ ố ể c AND H th ng nhiên li u t ượ ệ

2.3.2 Các lu t d n

ậ ẫ (ti p)ế

4. Chi n l

ế ượ

c ở ộ ượ

ệ ố ệ ầ

ệ

c IF Xe không kh i đ ng đ THEN Đ u tiên hãy ki m tra h th ng nhiên li u, sau đó ể ki m tra h th ng đi n ệ ố i ả

IF Xe n AND ti ng giòn ế THEN Đ ng c ho t đ ng bình th ng ạ ộ ơ ườ ể 5. Di n gi ễ ổ ộ

6. Ch n đoán ẩ ố

ọ

IF S t cao AND hay ho AND H ng đ ỏ THEN Viêm h ngọ

7. Thi

t kế ế ữ

IF Là n AND Da sáng THEN Nên ch n Xe Spacy AND Ch n màu sáng ọ ọ

2.3.2 Các lu t d n

ậ ẫ (ti p)ế

ụ

ự

M r ng cho các lu t ậ ầ ộ ố

ộ ậ

ộ

ở ộ Trong m t s áp d ng c n th c hi n cùng m t phép toán trên m t t p hay các đ i t

lu t có bi n

ố

ế .

ệ ầ

ậ

ng gi ng nhau. Lúc đó c n các ổ ủ

ể

ố ượ Ví d : IF X là nhân viên AND Tu i c a X > 65 ụ THEN X có th ngh h u ệ

ự ệ

ể

ả

ắ

 Khi m nh đ phát bi u v s ki n, hay b n thân s ki n có th không ch c t l p quan h không ệ ế ậ lu t không ch c c g i là ọ

ỉ ư ề ề ự ệ i ta dùng h s ch c ch n CF. Lu t thi ắ ườ thi ữ

ậ t và k t lu n đ ế

ự ệ

ượ

ế

ậ

ả

ậ

ắ

ch n, ng ệ ố chính xác gi a các s ki n gi ch nắ .

ấ ẽ

ắ

ạ c vi

Ví d : IF L m phát CAO THEN H u nh ch c ch n lãi su t s CAO ầ i v i giá tr CF có th nh sau:

ư ể

t l ậ ượ ế ạ ớ ị

ụ Lu t này đ ạ  D ng lu t ti p theo là ậ ế

ư IF L m phát cao THEN Lãi su t cao, CF = 0.8

ứ ứ ậ

ạ M t lu t v i ch c năng mô t ộ lu t s đ a ra chi n l d ng, thay vì đ a ra thông tin m i.

ế ượ ự ậ

ấ siêu lu t:ậ cách th c dùng các lu t khác. Siêu ả c s d ng các lu t theo lĩnh v c chuyên ử ụ ớ

ụ

ệ ố

ườ

Ví d : IF Xe không kh i đ ng AND H th ng đi n làm vi c bình th THEN Có th s d ng các lu t liên quan đ n h th ng đi n ậ

ệ ệ ố

ể ử ụ

ệ ệ

ế

ậ ớ ậ ẽ ư ụ

ư ở ộ

Ví d : Gi ụ

ả

ể

i quy t v n đ b ng cách bi u ế ấ ề ằ di n tri th c ứ ễ

ể

t là c

ầ ượ ướ

ể

Bài toán: Cho hai bình r ng X và Y có th tích l n l ỗ VX và VY, hãy dùng hai bình này đ đong ra z lít n (v i z ớ

 Xét tr

min(VX,VY)). ng h p c th c a bài toán, ch ng h n: V ợ

ườ

ạ

ẳ

X=5 và

ế ầ

bình 7 sang bình 5 i t ạ ừ

ụ ể ủ VY=7 và z = 4, có th đ a ra quy trình sau: ể ư – Múc đ y bình 7 ầ – Trút h t qua bình 5 cho đ n khi 5 đ y. ế c trong bình 5 – Đ h t n ổ ế ướ c còn l – Đ h t n ổ ế ướ – Múc đ y bình 7 ầ – Trút h t qua bình 5 cho đ n khi bình 5 đ y. ế – Ph n còn l ầ

ầ c c n đong. ế i chính là s n ố ướ ạ ầ

Ví d : Gi ụ

ả

ể

i quy t v n đ b ng cách bi u ề ằ di n tri th c (tt)

ế ấ ễ

ứ

ả

ể ổ

c phát bi u t ng quát h n: s r ng V

ổ

ả ử ằ

c ch a trong bình X là x (0 c ch a trong bình Y là y (0

ứ ứ

ẽ

ủ c th c hi n b ng cách xét l n l

t các lu t

ầ ượ

ậ

c áp d ng.

ụ

c trong bình X đi. c vào bình Y.

ướ

ỗ

ế

ầ

ặ

ậ ế ế ế n c t ướ ừ bình Y h t n

c).

 L i gi i trên đ ờ ượ – Không m t tính t ng quát, gi ấ VX) – G i l ng n ướ ọ ượ ng n – G i l VY) ọ ượ ướ – Đi u ki n k t thúc c a bài toán s là: x=z ho c y=z ủ ế ệ ề – Đi u ki n đ u c a bài toán là: x=0 và y=0 ầ ệ ề i đ  Quá trình gi ằ ệ ự ả ượ sau, lu t nào th a mãn thì s đ ẽ ượ ỏ (L1) N u bình X đ y thì đ h t n ổ ế ướ ầ (L2) N u bình Y r ng thì đ đ y n ổ ầ ỗ (L3) N u bình X không đ y và bình Y không r ng thì hãy trút ầ bình Y sang bình X (cho đ n khi bình X đ y ho c ế ướ

Ví d : Gi ụ

ả

ể

i quy t v n đ b ng cách bi u ề ằ di n tri th c (tt)

ế ấ ễ

ứ

i trên đ

ả

ượ

c minh h a nh sau: ọ

L i gi ờ ... x:= 0; y := 0; WHILE ((x <> z) AND (y<>z)) DO BEGIN

IF (x = Vx) THEN x := 0; IF (y = 0) THEN (y:= Vy); IF (y > 0) THEN BEGIN k:= min(Vx - x, y); x := x + k; y := y - k;

END;

i quy t

ế ấ

ể

ộ

gi ự ả

ế

END; ... - Cách gi ả v n đ c th ấ ườ ố ướ

ả

i quy t v n đ theo ki u này không đ a ra m t trình t ư ề i d ng các lu t ề ụ ể mà ch đ a ra các quy t c d ậ ướ ạ ắ ỉ ư c r ng, bài toán đong n i ta đã ch ng minh đ ượ ằ ứ c c n đong là m t b i s c a ớ ộ ộ ố ủ ướ

ầ

i ướ ờ c s chung l n nh t c a th ể

c ch có l ỉ ấ ủ

ố

- Ghi chú: Ng i khi s n gi tích hai bình.

2.3.3 M ng ng nghĩa

ữ

ạ

M ng ng nghĩa là m t ph

ộ

ữ

ươ

ễ

ồ

ễ

ể ệ ữ

ố ố

ị ể

ng pháp bi u di n tri ể ạ th c dùng đ th trong đó nút bi u di n đ i ứ ng và cung bi u di n quan h gi a các đ i t ễ ượ t ng. ượ

Hình 2.3. "S là Chim" th hi n trên m ng ng nghĩa

ể ệ

ữ

ẻ

ạ

(ti p)ế

2.3.3 M ng ng nghĩa

ữ

ạ

Hình 2.4. Phát tri n m ng ng nghĩa ể

ữ

ạ

2.3.4 Frame

Hình 2.6. C u trúc frame ấ

quan h ph c t p h n

Hình 2.7. Nhi u m c c a frame mô t ứ

ủ

ề

ả

ứ ạ

ệ

i bài toán tam giác t ng quát

Ví d : Gi ụ

ả

ổ

c a tam giác. Nh v y có C

ể

ự

ư ậ

ế ố ủ

22 -1 cách đ xây d ng hay

ạ

ả

ế

ứ

ằ

ữ

ử ụ

i bài toán này b ng công c m ng ng nghĩa, s d ng kho ng ả c a

ứ

ụ ạ ả

ế ố ủ

ứ

ể

ỉ

•Có 22 y u t xác đ nh m t tam giác. ộ ị •Theo th ng kê, có kho ng 200 công th c liên quan đ n c nh và góc 1 ố tam giác. • Đ gi ể ả 200 đ nh đ ch a công th c và kho ng 22 đ nh đ ch a các y u t ỉ tam giác. M ng ng nghĩa cho bài toán này có c u trúc nh sau :

ấ

•Đ nh c a đ th bao g m hai lo i :

ồ

ỉ

ạ ệ

ữ

ằ

ậ

ằ

t y u

ế ế

ữ

ậ

ỉ

ế ứ ệ ữ

t giá tr c a n-1 y u t

c a tam giác, ta gi ị ủ

ế ố

ượ

ế

ứ ị ủ ư

ế ạ

ả c giá tr c a i. Ch ng h n nh trong công th c t ng 3 góc c a tam giác ủ i.

c hai góc, ta s tính đ

c góc còn l

ể ạ ữ ủ ồ ị •·Đ nh ch a công th c (ký hi u b ng hình ch nh t) ỉ ứ ứ •·Đ nh ch a y u t c a tam giác (ký hi u b ng hình tròn) ỉ ứ ế ố ủ ệ •Cung : ch n i t đ nh hình tròn đ n đ nh hình ch nh t cho bi ỉ ố ừ ỉ tam giác xu t hi n trong công th c nào t ấ ệ ố •* L u ý : trong m t công th c liên h gi a n y u t ế ố ủ ộ ư thì s tính đ đ nh r ng n u đã bi ẽ ằ ị còn l y u t ứ ổ ạ ẳ ế ố t đ 0 thì khi bi b ng 180 ượ ế ượ ằ

ẽ

ạ

i bt tam giác t ng quát (tt)

Ví d : Gi ụ

ả

ổ

đã cho

đ nh hình tròn

ỉ

ạ

ỉ

ứ

ế ớ

ể

ậ

ỉ

•B1 : Kích ho t nh ng ữ đã có giá tr ) ban đ u (nh ng y u t ị ế ố ữ ầ •B2 : L p l i b c sau cho đ n khi kích ho t ặ ạ ướ ạ t c nh ng đ nh ng v i nh ng y u t c t đ ế ố ữ ữ ượ ấ ả c b t kỳ c n tính ho c không th kích ho t đ ấ ạ ượ ặ ầ đ nh nào n a. ữ ỉ •N u ế m t đ nh hình ch nh t có cung n i v i ố ớ n ữ ộ ỉ n-1 đ nh hình tròn đã đ c đ nh hình tròn mà ượ i (và kích ho t ạ thì kích ho t đ nh hình tròn còn l ạ ạ ỉ tính giá tr đ nh còn l i này thông qua công th c ứ ạ ỉ ị đ nh hình ch nh t). ậ ở ỉ

ữ

i bt tam giác t ng quát (tt)

Ví d : Gi ụ

ả

ổ

ủ

Ví d : ụ "Cho hai góc a, b tam giác. Tính chi u dài đ

ề ng cao h

ề

và chi u dài c nh a c a ạ C". ườ

(6)

p=(a+b+c)/2

2.3.5 Logic

ề

ượ

c (A) ế

nhà đ n ch làm là xa (B) ỗ

A(cid:217) B(cid:222)

C

1. Logic m nh đ ệ IF Xe không kh i đ ng đ ở ộ AND Kho ng cách t ừ ả làm (C) THEN S tr gi ẽ ễ ờ  Lu t trên có th bi u di n l ể ể

ậ

ễ ạ

i nh sau: ư

2. Logic v tị ừ  Logic v t

ị ừ

ệ

ố

ể ể ệ

ề ệ

ứ

ệ

ồ

, cũng gi ng nh logic m nh đ , dùng các ư ký hi u đ th hi n tri th c. Nh ng ký hi u này g m ữ h ng s

ố, v tị ừ, bi n ế và hàm.

ằ

2.4 SUY DI N D LI U Ễ

Ữ Ệ

1. Modus ponens

E2 ﬁ E3 thì E3 đ c đ a vào ạ ượ ư

1. E1 2. E1ﬁ 3. E2 N u có tiên đ khác, có d ng ề ế danh sách.

2. Modus tollens E2

1. (cid:216) 2. E1ﬁ 3. (cid:216) E1

ạ ộ

ệ ố

ễ

2.4.2 Các ho t đ ng c a H th ng Suy di n ủ ti nế

Ví d v Suy di n ti n

ụ ề

ế

ễ

IF B nh nhân rát h ng Lu t 1ậ .

ọ AND Nghi viêm nhi mễ THEN Tin r ng b nh nhân viêm h ng, đi ch a h ng. ệ ằ ữ ệ ọ ọ

Lu t 2ậ . IF Nhi ệ ộ ệ ộ

t đ b nh nhân qúa 37 đ ệ THEN B nh nhân b s t ị ố

Lu t 3ậ . IF B nh nhân m trên 1 tu n ầ AND B nh nhân s t ố ệ ệ

THEN Nghi b nh nhân viêm nhi m. ễ ố ệ

b nh nhân là: ừ ệ

t đ 39 đ ệ ộ ộ

ầ ố

ệ ệ ệ

ế ủ ớ ớ

ọ ấ nh , câu k t lu n c a lu t đ Thông tin t · B nh nhân có nhi · B nh nhân đã m hai tu n · B nh nhân h ng rát Khi h th ng th y gi ả ậ ệ ố ớ thi ủ ế t c a lu t kh p v i thông tin trong b ộ ậ c b sung vào b nh . ớ ậ ượ ộ ổ

Ví d suy di n lùi

ụ

ễ

Minh h aọ

C ch suy di n

ơ

ế

ễ

ớ

ề

Suy di n v i logic m nh đ : 1.

ễ ậ

ễ

ậ

ệ Thu t toán suy di n ti n ế Input: - T p lu t Rule= {r 1, r2, ..., rm} ậ - GT, KL

Output: Thông báo “thành công” n u GT

ﬁ KL

ế

Ng

i, thông báo “không thành công”

c l ượ ạ

Method:

TD) AND (T„

) Do

TD=GT; T=Loc(Rule, TD); While (KL ¸ {

{q}; // r:leftﬁ q

r = Get(T); TD=TD¨ Rule = Rule \ {r}; T=Loc(Rule, TD);

TD THEN Return “True”

} If KL˝ else Return “False”

1:a ﬁ c, r2:b ﬁ d, r3:a ﬁ e, r4:a(cid:217) d ﬁ e, r5:b (cid:217) c ﬁ

f, r6:e (cid:217) fﬁ g}

(cid:217) b ﬁ g? a ﬁ g?

Ví d : Rule ={r ụ H i a ỏ

Thu t toán suy di n lùi

ễ

ậ

GT THEN Return “True”

; First=1; Quaylui= False;}

; V t = ế

{(q,0)};

If KL ˝ Else {TĐích=˘ For Each q˛ KL DO TĐích=TĐích¨ Repeat

first ++; ((f,i)=Get(TĐích); If (fˇ GT) THEN {

j = Tìmlu t(f,i,Rule); ậ

// rj: Leftj ﬁ

If (Tìm có rj) THEN

{ Vet = Vet ¨ For Each t˛

{((t,0)};

{(f,j)}; (Leftj\GT) DO TĐích = TĐích¨

else

{ Quaylui=True; While (fˇ KL) AND Quaylui DO { Repeat

{ (g,k)=Get(V t);ế TĐích = TĐích \ Leftk;}

Until f˛ Leftk; l=Tìmlu t(g,k,Rule); ậ

Thu t toán suy di n lùi

ễ

ậ

If (Tìm có rl) THEN

{ TĐích = TĐích \ Leftl ; For Each t˛

(Leftl \GT) DO

{((t,0)};

{(g,l)};

ế

TĐích = TĐích¨ ế ¨ V t = V t Quaylui = False; }

else f=g; } }

) OR ((f ˛ KL) and (First>2));

1:a ﬁ c, r2:b ﬁ d, r3:a ﬁ e, r4:a(cid:217) d ﬁ e, r5:b (cid:217) c ﬁ

f, r6:e(cid:217) fﬁ g}

(cid:217) b ﬁ g? , a ﬁ g?

} Until (TĐích = ˘ If (f ˛ KL) then Return False else Return TRue; Ví d : Rule ={r ụ H i a ỏ

2.4.3 u đi m

Ư

ể

ế

ủ ề ả ệ ố

* Suy di n ti n ễ Ư ể ấ ề

m t s thông ớ ừ ộ ố

ng đ i v i lo i bài toán c n gi ạ ế ễ ầ ễ i ả ầ

ế ụ ưở ế ậ ư ậ ề ễ ể

• u đi m chính c a suy di n ti n là làm vi c t t khi bài toán v b n ế ễ ch t đi thu th p thông tin r i th y đi u c n suy di n. ậ ễ ầ ấ ồ • Suy di n ti n cho ra kh i l ng l n các thông tin t ố ượ ế tin ban đ u. Nó sinh ra nhi u thông tin m i. ớ ề • Suy di n ti n là ti p c n lý t ố ớ quy t các nhi m v nh l p k ho ch, đi u hành đi u khi n và di n ề ạ ệ ế d ch. ị * Suy di n lùi ễ ộ ớ ợ

ễ ư thuy t r i xem hi u q a gi ể ế ồ ủ ế ả

thi ạ ộ

ả ậ ế ế ề ệ ậ ả ấ

các thông tin đã bi i dùng. ễ ừ ế

ễ ơ ở ố ớ ứ ủ ộ ỉ

•M t trong các u đi m chính c a suy di n lùi là phù h p v i bài ủ t đó có đúng không. toán đ a ra gi ệ ư •Suy di n lùi t p trung vào đích đã cho. Nó t o ra m t lo t câu h i ỏ ạ ễ ch liên quan đ n v n đ đang xét, đ n hoàn c nh thu n ti n đ i v i ỉ ố ớ ng ườ •Khi suy di n lùi mu n suy di n cái gì đó t t, nó ố ch tìm trên m t ph n c a c s tri th c thích đáng đ i v i bài toán ầ đang xét.

2.4.4 Nh

ượ

c đi m ể

ệ ố ễ ế

ủ ỉ ộ ọ

t r ng ch m t ít ế ằ

ể ỏ c. ượ

ệ ố ể

* Suy di n ti n ế ễ • M t nh c đi m chính c a h th ng suy di n ti n là không ể ượ ộ c r ng ch m t vài thông tin là quan tr ng. H c m nh n đ ệ ượ ằ ậ ả th ng h i các câu h i có th h i mà không bi ỏ ỉ ộ ỏ ố câu đã đi đ n k t lu n đ ậ ế ế • H th ng có th h i c câu không liên quan. Có th các câu tr ể ỏ ả ả i dùng lúng túng khi ph i tr l ả ả ư ọ ờ l ờ

ườ

* Suy di n lùi ễ c đi m c b n c a suy di n này là nó th ể ượ

i cũng quan tr ng, nh ng làm ng i các câu không dính đ n ch đ . ủ ề ế

ơ ả ủ ễ ườ ế

ng ti p theo đó mà sang nhánh ễ

ở ậ ể ố tin c y và các lu t meta đ ể ậ

•Nh dòng suy di n, thay vì đúng ra ph i đúng ả khác. Tuy nhiên có th dùng nhân t kh c ph c. ụ ắ

Ch

ươ

ng 3: H MYCIN ệ

ớ

3.1 Gi MYCIN là m t h l p lu n trong y h c đ

i thi u ệ ộ ệ ậ

ậ ấ ượ

c hoàn t ộ ệ

ử ụ ự ệ ự ể ử

ậ ế ễ ự ế ậ ắ

ờ ậ ầ ắ ệ

ằ ộ ơ ở ượ ạ ậ ứ

ấ ậ

ụ ể ẽ ổ ế ậ ủ ể ạ ứ

ệ

t vào năm 1970 ọ i đ i h c Standford, Hoa Kỳ. Đây là m t h chuyên gia d a trên t ạ ạ ọ lu t và s ki n. MYCIN s d ng c ch l p lu t g n đúng đ x lý ơ ậ các lu t suy di n d a trên đ đo ch c ch n. Ti p theo sau ộ MYCIN, h EMYCIN ra đ i. EMYCIN là m t h chuyên gia t ng ổ ệ c t o l p b ng cách lo i ph n c s tri th c ra kh i h quát đ ỏ ệ ầ ạ MYCIN. EMYCIN cung c p m t c ch l p lu n và tuỳ theo bài ộ ơ toán c th s b sung tri th c riêng c a bài toán đó đ t o thành h chuyên gia. Các đ c đi m chính: ể ậ ễ ỹ

ặ ử ụ ả ề ể

ợ

ặ ắ ắ

ế

ằ i thích: HOW, WHY. ể ễ ử ụ ấ ả - S d ng k thu t suy di n lùi. - Có kh năng phân tích tri th c và đi u khi n. ứ - Có tích h p Meta-Rule. - Có th dùng khi thi u thông tin ho c thông tin không ch c ch n. ế - D s d ng, giao ti p b ng ti ng Anh. ế - Cung c p các ch c gi ứ

M t phiên làm vi c c th v i MYCIN:

ệ ụ ể ớ

ộ

?Thông tin v b nh nhân ề ệ H và tên? ọ

Tu i?ổ

i tính?

ớ

Ch ng t c?

ộ

ủ

ấ

ả Có b t kỳ phép c y vi khu n cho Jack Durkin liên quan đ n b nh hi n t

ấ

ệ

ế

ệ ạ

M u v t l y t

đâu?

ậ ấ ừ

ẫ

Ngày gi

th c hi n c y: ệ

ờ ự

ấ

G n đây Jack Durkin có các tri u

ầ

ệ

 MYCIN:  User: Jack Durkin.  MYCIN:  User: 24.  MYCIN:  User: Nam.  MYCIN:  User: CAUCASIAN. …… ? Xác đ nh b n ch t lây nhi m ễ ị  MYCIN: ẩ  User: Có.  MYCIN:  User: CSF.  MYCIN:  User: 5-6-77 8:09 AM  …..  MYCIN:  ch ng nh : choáng ván, hôn mê không? ư ứ  User: Có.  …..

CÁC THÀNH PH N C A H MYCIN Ầ

Ủ

Ệ

ấ

ươ

ư ấ ọ

ị

ị ị ở

ấ

ừ

ả ờ ủ

ỏ ủ

ạ

ộ

i thích có tác đ ng qua l v n gi

ả ư ấ

ươ

ứ

i: Cho phép i thích các ki n th c c a nó ủ ế ả ng pháp đi u tr và ch ng minh các chú ề

ươ

ứ ị ặ

ệ

ị ng pháp đi u tr đ c bi ề ươ ứ

ạ

ự

ề

ệ

ế

ạ

ậ

ị

ng pháp đi u tr mà h tìm th y trong th c t ọ

ề

ấ

ị

trình t 1. Ch v n: Cung c p cho các Bác sĩ ươ ng pháp đi u tr thích i khuyên đ ch n ph các l ề ể ờ h p b ng cách xác đ nh rõ cách th c đi u tr b i các ợ ứ ằ ề các phòng thí nghi m lâm sàng d li u l y ra t ệ ữ ệ thông qua các câu tr l i c a bác sĩ cho câu h i c a máy tính. 2. Kh năng gi ả ng trình t ch v các ph ề thích v các ph ề 3. Thu n p tri th c: cho phép các chuyên gia con i trong lĩnh v c đi u tr các căn b nh truy n ng ườ ị nhi m d y cho MYCIN các lu t quy t đ nh theo ễ ph ự ế ươ lâm sàng.

PH M VI S D NG C A H MYCIN

Ử Ụ

Ủ

Ạ

Ệ

ẩ ề

ệ ị ắ ố ớ ế

ợ ờ ắ ả ả

ế ư ệ . Nhi u tr ề ậ

ọ ơ

ỏ ề ể

ệ ệ ả ờ ả ừ ệ

ẩ

2. T o ra ph ư ươ ượ ề ậ

ố

t ho c bi ặ ạ ả ờ ắ ợ

ế các thông tin không hoàn ch nh. ệ ậ ừ ủ ự ế ằ ỏ

ệ ấ

ệ

1. Ch n đoán nguyên nhân gây b nh: đ i v i các bác sĩ đi u tr , ệ khi xét nghi m cho b nh nhân đ có k t qu ch n đoán ch c ể ẩ ng h p ph i đi u tr c ngay ch n m t 24-48 gi ị ả ề ườ ấ khi ch a có k t lu n hoàn ch nh. MYCIN giúp ch n đoán ẩ ỉ ng trình nguyên nhân gây b nh nhanh h n: khi g i ch ươ i các câu h i v ti u s b nh nhân, MYCIN, các bác sĩ tr l ử ệ đó b nh án, các k t qu xét nghi m, các tri u ch ng, … t ứ ệ ế MYCIN đ a ra ch n đoán b nh. ệ c các câu tr l ng pháp đi u tr : Sau khi nh n đ i ị ạ ả ờ c a bác sĩ v tình tr ng b nh nhân thông qua đ i tho i. Trong ạ ệ ề ủ t không ch c ch n, ng h p câu tr l tr i không bi ắ ế ườ thì MYCIN s suy lu n t ỉ ẽ 3. D đoán di n bi n c a b nh: B ng các câu h i “HOW, WHY”, ễ MYCIN s gi i thích các nguyên nhân và lý do cho các bác sĩ. ẽ ả t, bác sĩ có th Sau khi vi c ch n đoán b nh và kê đ n hoàn t ẩ ể ơ ệ theo dõi toàn b quá trình ch n đoán b nh c a MYCIN và qua ủ ẩ ộ đó theo dõi di n bi n c a b nh ủ ễ ế ệ

NGUYÊN NHÂN THÀNH CÔNG C A MYCIN

Ủ

1. S c n thi ự ầ

ế ủ

ệ ư ấ

ủ

t c a vi c t ể ờ

ụ

v n dùng kháng sinh c a các bác sĩ: vào th i đi m này vi c l m d ng kháng ệ ạ i không ít ph n ng ph . sinh đã đem l ụ

c thu n p t

các

ơ ở

ượ

ạ

ừ

chuyên gia xu t s c nh t trong lĩnh v c.

ả ứ ạ 2. C s tri th c c a MYCIN đ ủ ứ ấ ắ

3. MYCIN không bao gi

ờ

ể

4. MYCIN đ

ừ ộ

ượ

có thêm các thông tin c t y u qua m i b c hình thành t ụ

m t ch c áp d ng th c t ự ế ượ i trung tâm y t ệ

ự

nhân t o đã đ ạ c th c hi n t đã đ ượ các tri th c m i nh t v b nh h c và d ớ ứ

ự ấ đi đ n ngay k t lu n đ luôn ậ ế ế c. ỗ ướ ố ế ng trình trí tu ươ ệ (DENDRAL) và n i ti ng v i ớ ế ổ ế c h c. ọ ượ

ạ ấ ề ệ

ọ

3.2 LÝ THUY T V S CH C CH N

Ề Ự

Ắ

Ế

ự

ộ

MB (Measure of Belief in): đ đo s tin c y ậ MD (Measure of Disbelief in): đ đo s không tin c y ự ậ CF (Certainly Factor): H s ch c ch n ắ ệ ố G i: ọ MB(H/E) là đ đo s tin c y c a gi ự

ộ ắ ậ

thuy t H khi ế

ủ

ả

ộ

ứ

ủ

ậ

ả

thuy t H ế

ứ

c tính b ng công th c:

có ch ng c E. MD(H/E) là đ đo s không tin c y c a gi ự ộ khi có ch ng c E. ứ Khi đó: 0 < MB(H/E) < 1 trong khi MD(H/E) = 0 0 < MD(H/E) < 1 trong khi MB(H/E) = 0 ắ CF(H/E) đ ộ

Đ đo ch c ch n ắ

ượ

ằ

ứ

CF(H/E) = MB(H/E) – MD(H/E)

3.2 LÝ THUY T V S CH C CH N

Ề Ự

Ắ (ti p)ế

Ắ

Ế

ả

ậ ơ

ứ

r: If(e) then (c) ủ ủ

ắ ắ ộ ộ ậ

c tính CF(e) là đ đo ch c ch n c a ch ng c . ớ CF(r) là đ đo ch c ch n c a lu t suy di n. ễ Khi đó: CF(c) là đ đo ch c ch n c a k t lu n s đ ế ắ ủ ậ ắ ẽ ượ

1. Lu t đ n gi n: ắ ắ ộ b ng công th c:

ứ ằ

CF(c) = CF(e) * CF(r)

ậ

2. Lu t ph c t p: ứ ạ  If(e1 AND e2) then (c)

CF (e1 AND e2) = MIN(CF(e1), CF(e2))

 if (e1 OR e2) then (c)

CF (e1 OR e2) = MAX(CF(e1), CF(e2))

3.2 LÝ THUY T V S CH C CH N

Ề Ự

Ắ (ti p)ế

Ắ

Ế

ậ ớ

ề ế ậ

3. V i lu t: if ((e1 AND e2) OR e3) then (c) CF ((e1 AND e2) OR e3) = MAX(MIN(CF(e1), CF(e2)), CF(e3)) 4. CF(NOT e) = - CF(e) 5. K t h p nhi u lu t có cùng k t lu n: ậ - Lu t 1: If(e1) then (c) v i CF(r1): đ đo ch c ch n c a lu t ủ ớ ộ ắ ắ ậ

ủ ớ ộ ắ ắ

ế ợ ậ 1 ậ ớ ủ ậ ậ

ươ ề

 Khi CF(t1) và Cf(t2) đ u âm thì:

- Lu t 2: If(e2) then (c) v i CF(r2): đ đo ch c ch n c a lu t 2 ậ  V i CF(t1), CF(t2) là CF c a k t lu n c a lu t 1 và 2, khi ủ ế ng thì: Ct ng = CF(t1) + CF(t2) – CF(t1) * CF(t2) CF(t1) và Cf(t2) đ u d ổ

ề

Ct ng = CF(t1) + CF(t2) + CF(t1) * CF(t2) ổ

ế ớ ấ

 N u CF(t1) khác d u v i CF(t2) thì: Ct ng = (CF(t1) + CF(t2)) / (1 – MIN(ABS(CF(t1)), ABS(CF(t2))))

ổ

Ví d v l p lu n trong H MYCIN

ụ ề ậ

ệ

ậ

 Ví dụ: Có 7 lu t sau đây:

ạ

ậ

ậ r1: If(e1) Then (c1) CF(r1) = 0,8 r2: If (e2) Then (c2) CF(r2) = 0,9 r3: If (e3) Then (c2) CF(r3) = 0,7 r4: If (e4) Then (c3) CF(r4) = 0,6 r5: If (NOT e5) Then (c3) CF(r5) = 0,5 r6: If (c2 AND c3) Then (c4) CF(r6) = 0,9 r7: If (c1 OR c4) Then (c5) CF(r7) = 0,8  B ng lu t này t o thành m ng suy di n ả ả

ạ thuy t c n h ế ầ

hình 3.1 v i c5 là gi ớ

ướ

ễ ở ng đ n. ế

Hình 3.1. M ng suy di n ạ

ễ

L p lu n trên m ng suy di n

ễ

ạ

ậ

 Gi

s các ch ng c e1, e2, e3, e4, e5 có đ ộ

ứ

ớ

ả ử ắ

đo ch c ch n nh sau: ắ

CF(e1) = 0,9 CF(e2) = 0,9 CF(e3) = -0,3 CF(e4) = 0,4 CF(e5) = -0,3

L p lu n trên m ng suy di n (ti p) ạ

ễ

ế

ậ

các

CF c a ch ng c d n ứ

ứ ầ

ủ

lên gi ự

c ượ CF(c1):

ậ r2, r3 tính đ

c ượ CF(c2)

ậ r2: CF(c2) = CF(e2) * CF(r2) = 0,9 * 0,9 =

ậ r3: CF(c2) = CF(e3) * CF(r3) = -0,3 * 0,7 =

 Chúng ta s l p lu n t ẽ ậ ậ ừ thuy t c5 nh sau: ư ế ả ậ r1 tính đ  D a vào lu t  CF(c1) = CF(e1) * CF(r1) = 0,8*0,9 = 0,72  D a vào lu t ự  V i lu t ớ 0,81  V i lu t ớ -0,21

 Do CF(c2) c a ủ r2 trái d u v i

ớ CF(c2) c a ủ r3, nên:

ấ

MIN (0,81, 0,21)) =

ổ

CF(c2)t ng = (0,81 + (-0,21)) / (1- 0,74

L p lu n trên m ng suy di n (ti p) ạ

ễ

ế

ậ

c ượ CF(c3) ậ r4, r5 ta tính đ

ậ r4:

 D a vào lu t ự  V i lu t ớ  CF(c3) = CF(e4) * CF(r4) = 0,4 * 0,6 = 0, 24  V i lu t ớ  CF(c3) = CF(NOT e5)*CF(r5) = -CF(e5)*CF(r5) = 0,3*0,5 =

ậ r5:

0,15

 Do CF(c3) c a ủ r4 và CF(c3) c a ủ r5 cùng d

ng nên ươ

CF(c3)t ng = 0,24 + 0,15 – 0, 24 * 0, 15 = 0,354 ổ

 D a vào lu t c ươ CF(c4):  CF(c4) = MIN(CF(c2), CF(c3)) * CF(r6) = MIN(0,74, 0,354) * 0,9

ự ậ r6 ta tính đ

= 0,354 * 0,9 = 0,3186

 D a vào lu t c ượ CF(c5)  CF(c5) = MAX(CF(c1), CF(c4)) * CF(r7) = MAX(0,72, 0,3186) *

 Nh th đ ch c ch n c a gi

ự ậ r7 ta tính đ

thuy t c5 là 0,576. 0,8 = 0,576 ư ế ộ ủ ắ ắ ả ế

Ch

ng 4

ươ

H h c ệ ọ

ễ ậ

ng h p này gi

4.1 M Đ U  Các ch ng tr ứ

ậ ứ ẵ

ả ợ ng minh tri th c.

Ở Ầ ướ ươ tri th c. Trong tr và có th bi u di n t ể ể

c đã th o lu n v bi u di n và suy lu n ề ể đ nh đã có s n tri th c ả ị ườ ứ ễ ườ

 Tuy v y trong nhi u tinh hu ng, s không có s n tri th c ố

ứ ề ẽ ẵ ậ

chuyên gia lĩnh v c.

ự

ậ

nh :ư – K s tri th c c n thu nh n tri th c t ỹ ư – C n bi ế ầ – Bài toán không đ

ả c bi u di n t

ứ ừ lĩnh v c c th . ự ụ ể ễ

ườ

ể

ng minh theo lu t, s ự

ậ

ệ

ọ

ký hi u: bao g m vi c hình th c hóa, s a ch a các

 Có hai ti p c n cho h th ng h c: ệ

ệ

ử

ữ

– H c t lu t t – H c t

ứ ng minh, s ki n và các quan h . ệ c áp d ng cho nh ng h th ng đ

ế ọ ừ ậ ườ ọ ừ ữ ệ

ụ

ữ

ứ ầ t các lu t mô t ậ ượ ki n hay các quan h . ệ ệ ố ậ ồ ự ệ ố ượ ố

ằ

d li u s : đ ướ ạ ố

ệ ố ậ ạ

ạ ọ i di truy n, bài toán t

ố

ề

ả

c ượ i d ng s liên quan đ n các k thu t nh m t i ố ế u các tham s . H c theo d ng s bao g m m ng Neural ố i u truy n th ng. ề ng minh.

mô hình d ỹ ồ ư nhân t o, thu t gi ố ư Các k thu t h c theo s không t o ra CSTT t

ậ ậ ọ

ạ ỹ

ườ

ố

ạ

4.2 CÁC HÌNH TH C H C

Ọ

Ứ

1. H c v t: ệ ế ủ ế

ị ế ị ệ ậ ệ ạ ậ ệ

ọ ị ệ ẽ ư ụ ọ

ẹ H ti p nh n các kh ng đ nh c a các quy t ẳ đ nh đúng. Khi h t o ra m t quy t đ nh không đúng, ộ h s đ a ra các lu t hay quan h đúng mà h đã s ử d ng. Hình th c h c v t nh m cho phép chuyên gia ằ ẹ ứ cung c p tri th c theo ki u t ể ươ ứ

2. H c b ng cách ch d n: ấ ằ ộ ng tác. ư

ệ ố ụ

ọ ầ ượ ỉ ẫ

ầ ừ

ỉ ẫ Thay vì đ a ra m t lu t c th ậ ụ ể c, h th ng s ướ ẽ ố c cung c p b ng các ch d n t ng quát. Ví d : ổ ụ ng van thay vì thoát ra t ừ ố mình đ ra cách bi n đ i t ổ ừ ế

ộ ậ

3. H c b ng qui n p: ậ ụ ụ ệ

c n áp d ng vào tình hu ng cho tr đ ấ ằ "gas h u nh b thoát ra t ư ị d n". H th ng ph i t ề ả ự ố ệ ẫ ng đ n các lu t kh d ng. tr u t ả ụ ậ ế ừ ượ ạ H th ng đ c cung c p m t t p ấ ượ ệ ố ằ ọ t ng ví d . H liên c rút ra t các ví d và k t lu n đ ừ ừ ượ ụ ớ t c l c các lu t và quan h nh m x lý t ng ví d m i. ử ằ ệ ụ ọ ế ậ ừ

4.2 CÁC HÌNH TH C H C (Ti p)

Ọ

Ứ

ế

4. H c b ng t

ấ

ằ

ọ

ứ

ượ

ươ

: ng t

ư

ự H th ng đ ệ ố ự

ậ

ướ

ệ ố ộ

ả

i gi

ố H th ng phân tích t p các l

ả

ờ

ệ ố

ng t c cung c p đáp ng đúng cho các tác v t nh ng không gi ng nhau. H th ng ụ ươ ố c n làm thích ng đáp ng tr c đó nh m t o ra m t lu t ạ ứ ằ ứ ớ m i có kh năng áp d ng cho tình hu ng m i. ụ ậ

ả

5. H c d a trên gi ự ả

ả

ầ ớ ọ ụ

i thích: ằ ấ

ặ

ng d n cách gi

ị i thích dùng đ h ể ướ

ẫ

ả

6. H c d a trên tình hu ng:

ượ

ấ

i ví d (và k t qu ) nh m n đ nh kh năng đúng ho c sai và t o ạ ế i bài toán trong ra các gi ả ng lai. t ươ ự ọ ậ ố

B t kỳ tính hu ng nào đ ả

ố ượ ư

ữ

ề

ướ

ớ

ẽ

ằ

th ng l p lu n đ u đ ậ đúng hay sai. Khi g p tình h nghi hành vi đã l u tr v i tình hu ng m i.

ữ ớ

ư

ố

ụ

7. Khám phá hay h c không giám sát: ọ

ệ ữ ệ ụ

ạ

ặ

c h ệ ố c l u tr cùng v i k t qu cho dù ớ ế ng m i, h th ng s làm thích ệ ố ớ Thay vì có m c tiêu ng minh, h khám phá liên t c tìm ki m các m u và quan t ẫ ế ụ ườ h trong d li u nh p. Các ví d v h c không giám sát bao ụ ề ọ ệ ậ g m gom c m d li u, h c đ nh n d ng các đ c tính c ồ ữ ệ ơ ậ ể các đi m nh. b n nh c nh t ả

ọ ể ả

ư ạ

ừ

Ví d v CÁC HÌNH TH C H C

Ứ Ọ

ụ ề

ạ

ọ

ậ

ạ

ng

Ví d :ụ - H MYCIN ệ - M ng Neural nhân t o ạ - Thu t toán h c Quinland - Bài toán nh n d ng ậ - Máy ch i c carô, c t ơ ờ

ờ ướ

4.3 THU T GI

I Quinlan

Ậ

Ả

- Là thu t toán h c theo quy n p dùng lu t, đa

ạ

ậ

ọ

m c tiêu.

ụ

ng: Ch n thu c tính quan tr ng nh t đ ấ ể

ọ

ưở

- Do Quinlan đ a ra năm 1979. ư - Ý t ọ ộ t o cây quy t đ nh. ế ị ạ ọ

ộ

ấ

ộ ả

ể

ễ

- Thu c tính quan tr ng nh t là thu c tính phân lo i B ng quan sát thành các b ng con sao ả ạ m i b ng con này d phân tích đ tìm cho t ừ ỗ ả quy lu t chung. ậ

4.3.1 THU T GI

I A. Quinlan

Ậ

Ả

STT Size Nationality Family Conclusion

Small German Single 1 A

Large French Single 2 A

Large German Single 3 A

Small Italian Single 4 B

Large German Married 5 B

Large Italian Single 6 B

Large Italian Married 7 B

Small Married 8 B German

V i m i thu c tính c a b ng quan sát:

ủ

ớ

ỗ

ộ

ả

 Xét vector V: có s chi u b ng s phân lo i ạ

ố

ổ

ố

ổ

ố

ố ằ ố

V(Size=Small) = (1/3 , 2/3) V(Size=Large) = (2/5 , 3/5)

 V i thu c tính Nationality

ề – V(Size=Small) = (ASmall, BSmall) – ASmall=S quan sát A có Size là Small / T ng s quan sát có Size=Small – BSmall= S quan sát B có Size là Small / T ng s quan sát có Size=Small

V(Nat = German)= (2/4 , 2/4) V(Nat = French) = (1 , 0) V(Nat = Italian) = (0/3,3/3)=(0 , 1)

 Thu c tính Family:

ớ ộ

V(Family=Single) = (3/5 , 2/5) V(Family = Married) = (0/3,3/3)=(0, 1)

ộ

V i m i thu c tính c a b ng quan sát:

ủ

ớ

ộ

ỗ

ả

ỉ STT Size Family Conclusion

Ch còn xét German •Thu c tính Size: 1 Small Single A

2 Large Single A

•Thu c tính Family: 3 Large Married B

4 Small Married B ộ V(Size=Small) = (1/2 , 1/2) V(Size=Large) = (1/2 , 1/2) ộ V(Family=Single)=(2/2,0,2)=(1, 0) V(Family=Married)=(0/2,2/2)=(0,1)

Nationality

Italian

French

German

Single

Married

V i m i thu c tính c a b ng quan sát(ti p)

ủ ả

ớ

ộ

ỗ

ế

Nationality

Italian

French

German

Single

Married

Rule 1: If (Nationality IS Italian) then (Conclusion IS B)

Rule 2: If (Nationality IS French) then (Conclusion IS A)

Rule 3: If (Nationality IS German) AND (Family IS Single)

then (Conclusion IS A)

Rule 4: If (Nationality IS German) AND (Family IS Married)

then (Conclusion IS B)

i: H c theo đ b t đ nh

Thu t gi ậ

ả

ộ ấ ị

ọ

Stt

Competition

Type

Age

Profit

Old

Software

Down

Midle

Yes

Software

Down

Midle

Hardware

Old

Hardware

Down

New

Hardware

New

Software

Midle

Software

New

Yes

Software

Midle

Yes

Hardware

Down

Old

Yes

Hardware

Down

H c theo đ b t đ nh(ti p)

ộ ấ ị

ọ

ế

 Đ b t đ nh c a X:

ộ ấ ị

ủ

XE (

)

log

p i

= 1i

 Tính Entropy cho m i thu c tính và ch n thu c tính ộ

ọ

ộ

(

log)

(

)

(cid:229)

ỗ có Entropy nh nh t. ấ ỏ ACE acp , ) - i i

acp , i i

= 1i

CE (

)

log

918.0

Competitio

CE (

)

log

811.0

Competitio

Yes

4 6 1 4

2 6 3 4

4 6 1 4 =

2 6 3 4 918.0*6.0)

811.0*4.0

8752

CE (

Competitio

(cid:229)

H c theo đ b t đ nh(ti p)

ộ ấ ị

ọ

ế

 T

STT Competition Type Profit ng t : ươ ự

Software Down Yes 1

 Age cho nhi u thông

Hardware Up No 2

E(C/Age) = 0.4 E(C/Type) = 1 ề Software Up No 3 tin nh tấ

Hardware Down Yes 4

Age

Milde

Old

New

Down

Competition

Up

Yes

No

Up

Down

H c theo đ b t đ nh(ti p)

ộ ấ ị

ọ

ế

Age

Milde

New

Old

Up

Down

Competition

Yes

No

Up

Down

Rule 1: If (Age IS Old) then (Profit IS Down)

Rule 2: If (Age IS New) then (Profit IS Up)

Rule 3: If (Age IS Midle) And (Competition IS No)

then (Profit IS Up)

Rule 4: If (Age IS Midle) And (Competition IS Yes)

then (Profit IS Down)

4.4 THU T GI

I ILA(Inductive Learning Algorithm)

Ậ

Ả

ớ

ộ ả

ỗ ộ

ể ệ

ộ

ậ

Xác đ nh d li u ữ ệ ị t kê trong m t b ng, v i m i dòng c li 1. T p m u đ ậ ẫ ệ ượ ng ng m t m u, và m i c t th hi n m t thu c t ỗ ộ ẫ ộ ứ ươ tính trong m u.ẫ ẫ

ẫ

2. T p m u có ộ ộ

m m u, m i m u g m ỗ ế ị ị

ậ

ộ

ị

3. T p lu t R có giá tr kh i t o là 4. T t c các dòng trong b ng ban đ u ch a đ

ồ k thu c tính và ộ ố n các giá tr ị có m t thu c tính quy t đ nh. T ng s ổ c a thu c tính quy t đ nh chính là s l p c a t p ủ ố ớ ế ủ m u.ẫ ậ ấ

ở ạ ả

ượ

ầ

đánh d u (ki m tra).

ậ ả ấ

ể

4.4 THU T GI

I ILA

Ậ

Ả

(ti p)ế

ả

ộ

ớ

ứ

ầ ị ủ

: Chia b ng ả m m u ban đ u thành ẫ ộ

ẫ

c 2 đ n 8 cho m i b ng con*)

ướ

ỗ ả

ế ợ

ế ế

ỗ

ế ả

n b ng con.  B c 1 ướ M i b ng con ng v i m t giá tr c a thu c tính phân l p ỗ ả c a t p m u. ủ ậ (* th c hi n các b ệ ự : Kh i t o bi n đ m k t h p thu c tính j, j=1.  B c 2 ở ạ ướ : V i m i b ng con đang kh o sát, phân chia  B c 3 ớ ướ t, m i ỗ

ệ

ớ : V i m i t

ộ

ị

ấ

ộ

ệ i). G i t

ờ ả ố ầ

ổ ợ ớ

ệ

ấ

ộ ả danh sách các thu c tính theo các t h p phân bi ộ ổ ợ t. h p ng v i j thu c tính phân bi t ệ ộ ổ ợ ứ h p các thu c tính, tính s l  B c 4 ng các ớ ỗ ổ ợ ướ ố ượ giá tr thu c tính xu t hi n theo cùng t h p thu c tính ấ ộ ổ ợ ệ ộ trong các dòng ch a đ c đánh d u c a b ng con đang ủ ả ượ xét (mà đ ng th i không xu t hi n v i t h p thu c tính ồ ớ ổ ợ h p đ u tiên (trong này trên các b ng còn l ầ ọ ổ ợ ạ h p l n t b ng con) có s l n xu t hi n nhi u nh t là ề ấ ả nh tấ .

4.4 THU T GI

I ILA

Ậ

Ả

(ti p)ế

, tăng j lên 1 và

h p l n nh t b ng

ớ

ổ ợ

ấ

ằ

: N u t ế i b c 3. ạ ướ : Đánh d u các dòng tho t

h p l n nh t c a

ấ ủ

ả ổ ợ ớ

b ng con đang x lý theo l p.

ớ

 B c 5 ướ quay l  B c 6 ướ ả  B c 7 ướ

ớ

ậ

ộ

ứ

ậ ế

ấ

: Thêm lu t m i vào t p lu t R, v i v trái là t p ớ ế h p l n nh t (k t ớ ổ ợ ớ AND) và v ph i là giá ế

ả

ằ

ươ

ượ

ấ

ả

ế

ượ

t c các b ng con đã đ ả c là t p lu t c n tìm.

ấ ử ậ ậ các giá tr c a thu c tính ng v i t ị ủ h p các thu c tính b ng toán t ử ộ ợ ng ng. tr thu c tính quy t đ nh t ứ ế ị ộ ị : N u t t c các dòng đ u đã đ c đánh d u  B c 8 ề ấ ế ả ướ phân l p, ti p t c th c hi n t c 2 cho các b ng con ệ ừ ướ ự ế ụ ớ i (n u ch a đánh d u h t các dòng) thì c l còn l i. Ng ấ ư ế ượ ạ ạ quay l c xét thì c 4. N u t i b ế ấ ả ạ ướ k t thúc, k t qu thu đ ượ ả ế ế

ậ ầ

ậ

Minh h a thu t gi

i ILA

ọ

ậ

ả

Size

Color

Shape

Decision

M u ẫ số

1 2 3 4 5 6 7

blue red red red green red green

yes no yes no yes no yes ng

medium small small large large large large T p m u h c cho bài toán phân l p đ i t ậ

brick wedge sphere wedge pillar pillar sphere ớ

B ng 4.1 ọ ố ượ ả ẫ

Minh h a thu t gi

i ILA

(ti p): B c 1

ọ

ậ

ả

ướ

ế

B ng con 1 ả

Size Color Decision Shape M u s cũ, m i ớ ẫ ố

medium blue brick yes 1 1

small red sphere yes 3 2

large green pillar yes 5 3

large green sphere yes 7 4

B ng con 2 ả

Color Size Shape Decision M u s cũ m i ớ ẫ ố

small red wedge no 2 1

large red wedge no 4 2

large red pillar no 6 3

B ng 4.2.

V i n=2, Chia thành hai b ng con theo thu c tính Decision

ả

ộ

ớ

Minh h a thu t gi

i ILA

ọ

ậ

ả

(ti p)ế

c 2 c a thu t gi

ậ

ả

ủ

i vào b ng con th ứ h p

ổ ợ

ấ

ả

ớ

ị ổ ợ ộ ị

ấ

ở

ả

ấ

ả ớ ổ ợ

ượ

ướ

• Áp d ng b ướ ụ ớ j=1, danh sách các t nh t trong b ng trên. V i ấ ả thu c tính g m có {Size}, {Color}, và {Shape}. ộ ồ • V i t h p {Size}, giá tr thu c tính "medium" xu t ộ ị ớ ổ ợ hi n trong b ng con th nh t nh ng không có ứ ệ trong b ng con th hai, do đó giá tr t h p l n ứ nh t là "medium". B i vì các giá tr thu c tính "small" và "large" xu t hi n trong c hai b ng con, ệ h p c này. V i t c xét trong b nên không đ {Size}, giá tr thu c tính "medium" ch b ng 1 ỉ ằ ộ ị

Minh h a thu t gi

i ILA

ọ

ậ

ả

(ti p)ế

ấ

ộ

ằ

, v i t

ươ

ớ ổ ợ

ố ướ

ầ

ớ

ố ầ ọ

ườ

ị

ấ ấ ể

ậ ị

c đánh d u đã phân l p, ta có lu t d n nh sau:

• Xét ti p cho t h p l n nh t h p {Color} thì giá tr t ị ổ ợ ớ ổ ợ ế là b ng 2, ng v i thu c tính "green", còn thu c tính ứ ộ ớ "blue" là b ng 1. ằ • T ng t h p {Shape}, ta có "brick" xu t ự ấ hi n m t l n, và "sphere" hai l n. Đ n cu i b c 4, ộ ầ ế ệ h p {Color} v i thu c tính "green" và {Shape} ta có t ộ ổ ợ v i thu c tính "sphere" đ u có s l n xu t hi n l n ệ ớ ấ ề ộ ớ ng h p th nh t là 2. Thu t toán m c đ nh ch n tr ứ ợ ặ h p l n nh t. Dòng 3 và 4 nh t đ xác đ nh lu t t ấ ậ ổ ợ ớ đ ậ ẫ ớ

ượ

ấ

Rule 1: IF color IS green THEN decision IS yes

Minh h a thu t gi

i ILA

ọ

ậ

ả

(ti p)ế

ẫ ế ự ướ ạ

ệ ả ế ụ ấ c 4 đ n 8 cho các m u còn l ụ

ấ ư ủ ị

ề ệ ộ

ố ầ ậ ố

ở ặ ầ ậ ợ ọ

• Ti p t c th c hi n b i (ch a ư đánh d u) trong b ng con này (t c dòng 1 và 2). Áp d ng t ng ươ ứ nh trên, ta th y giá tr thu c tính "medium" c a {Size}, "blue" t ộ ự c a "Color", "brick" và "sphere" c a {Shape} đ u xu t hi n m t ấ ủ ủ l n. B i vì s l n xu t hi n này gi ng nhau, thu t gi i áp d ng ụ ả ệ ấ ầ lu t m c đ nh ch n tr ng h p đ u tiên. Ta có thêm lu t sau: ậ ườ ị Rule 2: IF size IS medium THEN decision IS yes

ứ ụ ế ấ

ụ ấ ướ ạ ứ

t c các dòng trong b ng con 1 đã

ư ậ

ượ

ấ

ả

ế ủ c 4 đ n 8 trên dòng còn l ệ ộ ầ ị ứ ậ ấ

c đánh d u, ta chuy n qua x lý ti p b ng con 2.

c đánh d u. Nh v y, t ể ấ

ấ ả ế

ượ

ử

ả

Đánh d u cho dòng 1 trong b ng con th nh t. Ti p t c áp ả d ng b i (t c dòng 2). Giá tr thu c ộ tính "sphere" c a {Shape} xu t hi n m t l n, ta có lu t th ba: :Rule 3: IF shape IS sphere THEN decision IS yes Dòng 2 đ đ

Minh h a thu t gi

i ILA

ọ

ậ

ả

(ti p)ế

ủ ệ ấ

•Thu c tính "wedge" c a {Shape} xu t hi n hai l n trong dòng 1 và 2 c a b ng con này. Đánh d u các dòng này v i lu t d n th t ủ ầ ậ ẫ ứ ư ấ ớ

ộ sau: ả Rule 4: IF shape IS wedge THEN decision IS no

ớ ộ ả ủ ạ ứ

ệ

ng t ả ự ậ ủ

ị i, ta lo i b tr ng h p này. T ạ ỏ ườ ủ ở ạ

ứ ề ệ ấ ả

ệ ấ

ổ ợ ả ặ ộ ườ ủ ấ ứ ậ ợ

• V i dòng còn l i (t c dòng 3) c a b ng con 2, ta có thu c tính {Size} v i giá tr "large" có xu t hi n trong b ng con 1. Do đó, theo thu t ấ ớ nh v y cho giá tr "red" c a gi ị ư ậ ươ ợ ả {Color} và "pillar" c a {Shape}. Khi đó, ILA tăng j lên 1, và kh i t o các h p 2 thu c tính là {Size và Color}, {Size và Shape}, và {Color và t ộ ổ ợ Shape}. Các t h p th nh t và th ba tho mãn đi u ki n không ứ xu t hi n trong b ng con 1 v i các c p thu c tính hi n có c a dòng ặ ệ này. Theo lu t m c đ nh, ta ch n lu t theo tr ng h p th nh t. Đánh ậ ị d u dòng này, ta có thêm lu t d n th 5: ớ ọ ậ ẫ ứ ấ

Rule 5: IF size IS large AND color IS red THEN decision IS no

Minh h a thu t gi

i ILA

ọ

ậ

ả

(ti p)ế

Rule 1: IF color IS green THEN decision IS yes Rule 2: IF size IS medium THEN decision IS yes Rule 3: IF shape IS sphere THEN decision IS yes Rule 4: IF shape IS wedge THEN decision IS no Rule 5:IF size IS large AND color IS red THEN decision IS no

ậ

i: ả ng các lu t thu đ ậ

ượ ứ ậ ộ

ủ ớ ụ

ộ ậ ạ ọ

ượ ể ẫ ả ớ

Đánh giá thu t gi • S l c xác đ nh m c đ thành công c a thu t ố ượ ị i. Đây chính là m c đích chính c a các bài toán phân l p thông gi ủ ả qua m t t p m u h c. Ngoài ra, đ đánh giá các h h c quy n p là ể kh năng h th ng có th phân l p các m u đ • Thu t gi ượ ả ậ pháp h c quy n p tr

ẫ ệ ố i ILA đ i v ph ng c đ a vào sau này. ươ ả ề ệ ọ ư ậ ạ

ơ c đây là ID3 và AQ). c đánh giá m nh h n hai thu t gi ướ ạ ọ

Ch

ng 5: H th ng m cho các bi n liên t c

ươ

ệ ố

ụ

ờ

ế

5.1 Các khái ni mệ 1. T p rõ và hàm đ c tr ng ặ

ữ ự

ậ - Ngôn ng t - T p rõ (crisp set): G i A là m t t p h p rõ, m t ph n t

nhiên và logic m . ờ ộ ậ ọ ˛ A ho c xặ

ậ có th có x ể khái ni m thu c v . N u x ề ộ ệ (x)=0. Hàm c

ộ ợ ˇ A, Có th s d ng hàm ể ử ụ ế đ ượ

x ầ ử c đ mô t ả ể i n u x ợ ạ ế c g i là hàm đ c tr ng c a t p ủ ậ ư ặ

˛ A, c (x) = 1, ngu c l ọ

ệ

A, c h p A. ợ ậ

ứ

ở ộ ờ

ờ ề ượ ộ ằ c a t p m A. M t t p m (fuzzy set): A đ ộ ậ

- T p m và hàm thành viên: Khác v i t p rõ, khái ni m ớ ậ c m r ng nh m ph n ánh m c đ x là ả c ờ và cho x là m t ph n

ượ ầ

ộ

A(x) ph n ánh m c đ x thu c v A.

ề c xác đ nh b i hàm: ượ

ằ ả ờ

ứ ậ

ở

ị

thu c v đ ộ ph n t ầ ử ủ ậ đ c tr ng b ng hàm thành viên ư ặ , ử m t ộ - M t t p m A trong t p vũ tr U đ ụ ộ ậ [0,1]

A: U ﬁ

5.1 Các khái ni m v

ề Logic mờ

ệ

• Ví d v t p m : ụ ề ậ ờ

ờ ạ ữ ờ ậ ạ

ể 1. N u t p vũ tr U là r i r c và h u h n thì t p m A trong U đ - High - Young - S g n 7 ố ầ - T c đ nhanh ộ ố Bi u di n t p m : ờ ễ ậ ế ậ ụ c bi u di n: ể ượ

ễ m

)( x A x

(cid:229)

Ví d : Cho U={a, b, c, d}. Ta có th xác đ nh m t t p m A nh sau: ể

ộ ậ

ụ

ư

ờ

ị

3.0 a

5.0 b

0 c

7.0 d

Ho c A={0.3, 0.5, 0.0, 0.7} ặ

5.1 Các khái ni m v

ề Logic m (ti p)

ờ ế

ệ

2. N u t p vũ tr U là liên t c thì t p m A trong U đ

c bi u di n:

ế ậ

ụ

ậ

ượ

ễ

ể

ụ =

(cid:242)

Ví d : T p m A={“S g n 2”} có th xác đ nh hàm thu c nh sau:

ụ ậ

ố ầ

ư

ờ

ộ

ị

ờ )( x A x ể

-(x

2)-

)( x

2)-(x-

(cid:242)

5.1 Các khái ni m v

ề Logic m (ti p)

ờ ế

ệ

Ghi chú: Đ th hàm thu c cho t p m A={“S g n 2”} có th xác đ nh

ố ầ

ộ

ờ

ể

ậ

ị

ồ ị cách khác nh sau:

ư

ế

A (x)=

0 n u x < 1 x-1 n u 1ế x < 2 1 n u x = 2 -x+3 n u 2 < x 0 n u x>3

ế ế ế

5.2 Các d ng c a hàm thành viên ủ

ạ

 Các hàm thành viên c a t p m có 3 d ng c b n là:

ủ ậ ơ ả ờ

 D ng S tăng

ạ d ng tăng, d ng gi m và d ng chuông ả ạ ạ

ạ ạ

Hình 4.2. Hàm S tăng

ả

ạ ạ

 b) D ng S gi m  c) D ng hình chuông

Hình 4.3. Hàm d ng chuông

ạ

5.3 Bi n ngôn ng (Linguistic Variable)

ữ

ế

ữ ờ ậ ờ

 Logic m liên quan đ n l p lu n trên các thu t ng m và m ơ ậ ế ậ nhiên c a con ng ủ

h trong ngôn ng t i. ườ

ữ ự trong ngôn ng t nhiên làm giá tr g i là ữ ự ừ ị ọ

ụ c xác đ nh b i b b n (x, T, U, M): ở ộ ố ố ộ

ồ  Bi n nh n các t ế ậ bi n ngôn ng . ế ữ  Bi n ngôn ng đ ị ế ữ ượ – X là tên bi n. Ví d : “nhi ế – T là t p các t ậ ệ ộ ị ấ ể ữ

(các giá tr ngôn ng ) mà x có th nh n. Ví ừ ậ ộ ụ ố

t đ ”, “t c đ ”, “áp su t”, ... ậ d : x là “t c đ ” thì T có th là T={ch m, v a, nhanh} ể – U là mi n giá tr mà x có th nh n. Ví d , n u x là “t c đ ” ố ể ừ ụ ế ề ộ ị

ậ c a xe máy thì U=[0 .. 120 km/h] ủ – M là lu t ng nghĩa, ng v i m i t t ứ ữ ậ ớ ỗ ừ ˛ T v i m t t p m A. ộ ậ ớ ờ

5.4 Bi n ngôn ng (ti p)

ữ ế

ế

Bi n ngôn ng

Các giá tr đi n hình

ế

ữ

ị ể

ấ

t đệ ộ Nhi Đ cao ộ T c đố ộ

Nóng, l nhạ Th p, trung bình, cao Ch m, v a, nhanh ừ

ậ

ụ ừ ừ ậ

Ví d : Cho x là t c đ , T={ch m, v a, nhanh}, các t ố “v a”, “nhanh” đ “ch m”, ộ ậ c xác đ nh b i các t p m trong hình sau: ậ ượ ừ ờ ờ ị

Nhanh

Ch mậ

V aừ

30 50 60 70 120

5.5 Gia tử

làm m h thêm các câu nh : ư r t, h i, có v , ... ơ ẻ ấ

 Gia t ử 1. R t:ấ m

R t(A) ấ

A(x))2 Ví d : T p m g m nh ng ng ữ ờ ồ

ụ ậ

ơ ồ (x) = (m

A(x))0.5

ụ

ữ

ườ ầ

ữ

ậ

ườ

i thiên v ề

Ví d : A là t p nh ng ng ậ cao và th p trong nh ng ng

i r t cao ườ ấ Co giãn (A) (x) = (m i t m th ướ i t m th ườ ầ

ữ

ấ

c thì Co giãn A là t p nh ng ng ướ

m 2. Co giãn / m t ít:ộ

ấ ự ự ạ

Nh n m nh(A)

ạ

ấ

m £ m 0.5 3. Nh n m nh/ th c s là: A(x))2

A(x) £ 1

Nh n m nh(A)

A(x) £

ạ

c t p nh ng ng

ấ ụ

A(x))2 n u 0.5 ế ờ ớ ậ

ượ ậ

ữ

ườ

ii th c ự

m £ (x) = 2(m (x) = 1-2(1-m n u 0 ế m

4. M nh m / r t r t: (x) = (m m

Ví d : Sau khi dùng phép toán này v i t p m cao ta đ s cao ự ạ

R t r t(A) ấ ấ

c t p nh ng ng

A(x))n ờ

ụ

ớ ậ

ượ ậ

ữ

ườ

ii th c ự

Ví d : Sau khi dùng phép toán này v i t p m cao ta đ s cao ự

ẽ ấ ấ

5.6 Các phép toán trên t p mậ

ờ

A(x), m

B (x), m

C(x)

ậ B: m B : m

B (x)) B (x))

A :

ớ m Cho ba t p m A, B , C v i ờ A(x), m C(x) = min(m  C=A ˙ A(x), m C(x) = max(m  C=A ¨ C(x) = 1- m  C=(cid:216)

A(x)

ờ ậ i: ườ ủ ề

Cao ˙

gi a t p, th p nh t

i t m th

Dùng đ ch nh ng ng ỉ

ữ

ấ ở ữ ậ

ườ ầ

ấ ở

ướ

ấ

ị

 m

Cao ¨

i không t m th

Th p ấ (x) = 0.0/1.5 + 0.2/1.55 + 0.5/1.60 + 0.2/1.65 + 0.0/1.70 2 bên c: giá tr cao nh t ể Th p ấ (x) = 1.0/1.5 + 0.8/1.55 + 0.5/1.60 + 0.8/1.65 + 1.0/1.70 ể

ườ

ữ

ầ

c ướ

 m

i không cao hay t m th

c hay th p.

Dùng đ ch nh ng ng ỉ (cid:216) Cao (x) = 1.0/1.5 + 0.8/1.55 + 0.5/1.60 + 0.2/1.65 + 0.0/1.70 Dùng đ ch nh ng ng ỉ

ướ

ữ

ể

ấ

ầ

ườ

Xét t p m “cao” và “th p” v chi u cao c a ng ề ấ Cao = 0.0/1.5 + 0.2/1.55 + 0.5/1.60 + 0.8/1.65 + 1.0/1.70 Th p = 1.0/1.5 + 0.8/1.55 + 0.5/1.60 + 0.2/1.65 + 0.0/1.70 ấ  m

5.7 Suy di n mễ

ờ

ệ ệ ế ẳ ị ị

M nh đ m là m nh đ kh ng đ nh giá tr cho bi n ngôn ng . ữ ậ

ờ c ướ ề ầ

ề ề ờ is ề ị Ví d : Chi u cao là t m th ụ ậ ờ ử ụ  Logic m s d ng t p m trong các m nh đ m . ề ờ ờ ệ

c thì tr ng l ng là IF X is A THEN Y is B Ví d : N u chi u cao là t m th ề ế ụ ầ ướ ọ ượ

ế ư ữ ế ậ ờ

ệ

ợ ả

trung bình • N u A và B là t p m thì H chuyên gia l u tr liên k t (A,B) ệ trong ma tr n M (hay ký hi u R). • Có th th hi n c A và B nh các vector (A, B) thích h p và ư đ t quan h này vào ma tr n M. ậ ặ

ậ ờ ờ ờ

ạ ậ ế • Hai k thu t suy di n thông d ng là; ễ - Ma tr n liên k t m M ánh x t p m A sang t p m B. ụ ỹ

ự

ậ ể ể ệ ệ ậ ậ • Suy di n Max-Min ễ • Suy di n c c đ i. ạ ễ

5.7.1 Nhân ma tr n vector m

ậ

ờ

A(xi) B(yj)

n*p đ

v i aớ i = m v i bớ j = m c xác đ nh nh sau: A o M = B ư ị

i £ n

Cho A =(a1, a2, ..., an) Cho B =(b1, b2, ..., bp) Ma tr n Mậ ượ Trong đó bj = Max { Min (ai, mij)} 1£ Ví d : Cho A=(0.2, 0.4, 0.6, 1) ụ

Cho

M =

ươ

ự 2=0.6 và b3 = 0.5

b1 = Max{Min(0.2, 0.1), Min(0.4, 0.6), Min(0.6, 0.8), Min(1, 0.0)} = 0.6 b2 = Max{Min(0.2, 0.6), Min(0.4, 0.8), Min(0.6, 0.6), Min(1, 0.5)} = 0.6 T Nh v y, B=(0.6, 0.6, 0.5)

ng t ư ậ

0.1 0.6 0.8 0.0 0.6 0.8 0.6 0.5 0.8 0.6 0.5 0.5

5.7.2 Suy di n Max-Min (Tìm ma tr n M)

ễ

ậ

t đ bình th

ng”

ệ ộ ậ

- Suy di n Max-Min: Ví d : ụ

mij = Min(ai , bj) t đ , t p m A tr n X: “nhi ờ

ườ

ệ

ệ ộ ộ ừ

ố

t đ bình th

ng THEN t c đ v a ph i”.

ườ

ả ộ ừ

ả

ờ ệ ộ ờ ể ệ

ả ử ả ử

ằ

Gi Gi Nhi

ng =(0/100, 0.5/125, 1/150, 0.5/175, 0/200)

ễ X: nhi Y: t c đô, t p m B trên Y: “t c đ v a ph i” ố ậ s có lu t: IF nhi ố ậ s các t p m th hi n b ng các vector sau: ậ t đ bình th ệ ộ

ườ

Ho c (0, 0.5, 1, 0.5. 0)

ặ

T c đ v a ph i = (0/10, 0.6/20, 1/30, 0.6/40, 0/50)

ộ ừ

ả

ố

Ho c (0, 0.6, 1, 0.6, 0)

ặ Ma tr n M đ ậ

c t o ra nh sau:

M =

ậ

ượ ạ 0.0 0.0 0.0 0.0 0.0 ư 0.0 0.5 0.6 0.5 0.0 0.0 0.5 1.0 0.5 0.0 0.0 0.5 0.6 0.5 0.0 0.0 0.0 0.0 0.0 0.0

Cho t p A’ = (0/100, 0.5/125, 0/150, 0/175, 0/200) Ta có b1= max{min(0,0), min(0.5,0), min(0,0), min(0,0), min(0,0)}=0 B’ = (0/10, 0.5/20, 0.5/30, 0.5/40, 0/50)

5.7.3 Suy di n Tích c c đ i (Tìm ma tr n M)

ự ạ

ễ

ậ

- Dùng phép nhân đ t o các thành ph n c a ma tr n M

ậ

ủ

ể ạ Suy di n Tích c c đ i:

ễ

ự

A’

ể

ừ

ầ ạ mij = ai * bj - Sau đó dùng cách tính Max-Min đ suy ra B’ t Ví d : ụ

c t o ra nh sau: Ma tr n M đ ậ

M =

ậ

A = (0, 0.5, 1, 0.5, 0) B = (0, 0.6, 1, 0.6, 0) ư 0.0 0.3 0.6 0.3 0.0 Cho t p A’ = (0, 0.5, 0, 0, 0) Ta có b1= max{min(0,0), min(0.5,0), min(0,0), min(0,0), min(0,0)}=0 B’ = (0, 0.3, 0.5, 0.3, 0)

ượ ạ 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.3 0.6 0.3 0.0 0.0 0.5 1.0 0.5 0.0

5.8 NGUYÊN LÝ X LÝ CÁC BÀI TOÁN M

Ử

Ờ

Hình 9.4. H th ng m ờ

ệ ố

1. M hóa: Chuy n đ i giá tr rõ đ u vào thành vector

ể

ầ

ờ

ổ

ị

2. Xác đ nh các lu t h p thành và thu t toán xác đ nh giá

ậ ợ

ậ

ị

ị tr m ị ờ

m x

)( dxx

3. Gi

ả

i m : Ph ờ

ươ

ng pháp đi m tr ng tâm ể

ọ

x 0

)( dxx

(cid:242)

5.8 NGUYÊN LÝ X LÝ BÀI TOÁN M (ti p)

Ờ ế

Ử

Hình 9.4. H th ng m ờ

ệ ố

ị

ữ ệ

ị

ở

Bài toán 1: D li u Input là các giá tr rõ. Ví d : ụ Xét bài toán m xác đ nh b i các lu t sau: ậ ờ Lu t 1ậ :if x is A1 and y is B1 Then z is C1 Lu t 2ậ :if x is A2 or y is B2 Then z is C2 Vào: tr x0, y0 ị ------------------------------------------------------------ Ra : tr z0 t ị

ng ng ứ

ươ

5.8 NGUYÊN LÝ X LÝ BÀI TOÁN M (ti p)

Ờ ế

Ử

ng v i t p m A ng v i t p m A ng v i t p m B ng v i t p m B ng v i t p m C ng v i t p m C

Ứ Ứ Ứ Ứ Ứ Ứ

ớ ậ ớ ậ ớ ậ ớ ậ ớ ậ ớ ậ

ờ 1 ta có hàm thành viên m ờ 2 ta có hàm thành viên m ờ 1 ta có hàm thành viên m ờ 2 ta có hàm thành viên m ờ 1 ta có hàm thành viên m ờ 2 ta có hàm thành viên m

A1 (x) A2 (x) B1 (y) B2 (x) C1 (x) C2 (x)

i bài toán đi u khi n t

đ ng m cho h ệ ờ

ể ự ộ gi ng.

c t

Ví d : Gi ả ụ th ng b m n ơ

ề c l y n ướ ừ ế

ướ ấ

ố

Trong khi h h t n

c và trong gi ng có n

c thì

ế

ướ

máy b m t

ồ ế ướ ơ

H.Đầy H.L ngư

ự động b m.ơ H.C nạ

N.Cao

B.Lâu

B.V aừ

N.V aừ

B.V aừ

B.H iLâu ơ

N.Ít

ớ

ậ

ế

ờ ồ đầy (H.Đầy), h l ng

ồ ư

ạ

ớ

ế

ồ ạ ữ

ừ

ế

ớ

ờ

ớ

ừ

ớ

định th i gian b m s có các t p m ờ

ậ

ờ

•V i bi n ngôn ng H có các t p m h ữ ồ (H.L ng) và h c n (H.C n). •V i bi n ngôn ng Gi ng có các t p m nu c cao (N.Cao), nu c v a ậ (N.V a), nu c ít (N.Ít). •V i bi n ngôn ng k t lu n xác ữ ế b m v a (B.V a), b m lâu (B.Lâu), b m h i lâu(B.H iLâu). ơ

ớ ơ

ẽ ơ

ế ừ

ừ

100

Ví d (ti p) ụ ế

Trong đó x ch ỉ độ sâu c a H (0<=x<=2), y ch ủ

ế

ỉ độ sâu c a Gi ng ồ ủ (0<=y<=10) và z ch th i gian b m (0<=z<=30). ỉ ờ

101

Ví d (ti p) ụ ế

ậ

ừ

ừ ả ậ ậ ậ ậ

ừ

ế

ậ

ị

T b ng trên ta có các lu t: •Lu t 1: if x is H.L ng and y is N.Cao Then z is B.V a ư ừ •Lu t 2: if x is H.C n and y is N.Cao Then z is B.Lâu ạ •Lu t 3: if x is H.L ng and y is N.V a Then z is B.V a ư ừ •Lu t 4: if x is H.C n and y is N.V a Then z is B.H i lâu ơ ạ c trong h ), N u nh p tr Input c trong gi ng)

x0 = 1 (Độ cao c a n y0 = 3 (Độ cao c a n

ướ ướ

ồ ế

ủ ủ

102

Ví d (ti p) ụ ế

103

Ví d (ti p) ụ ế

ọ ố ủ

ở ậ ậ ủ ứ

m m ế Wi K1i(Z) i = 1 …N

2.B.Lâu(z) + W3.B.V a(z) + W

m ừ ừ

4.B.H i Lâu(z) ơ ơ

m ừ ừ

hàm thành viên c a k t lu n b ng ủ ế ế ả ậ

m i m t ờ ừ C(z)

(cid:242)

U z )(

(cid:242)

15.8

z )(

(cid:242) Các Wi g i là các tr ng s c a lu t th i ứ ọ Theo lý thuy t hàm thành viên c a k t lu n cho b i công th c: ế C(z) = S C(z) = W1.B.V a(z) + W C(z) = 3/10.B.V a(z) + 0.5.B.Lâu(z) + 3/5.B.V a(z) + 0.5.B.H iLâu(z) B c ti p theo là ta ph i gi ằ ả ướ cánh tính tr ng tâm c a hàm ủ ọ m )( z z Moment m C(z) là m z)( dz z dz và

(cid:242)

ậ

c trong h và gi ng là 1m và 3m thì th i gian c n ế ầ ồ ờ

104

V y Defuzzy(z) =8.15 Do đó n u m c n ướ ự ế b m là 8 phút và 15/100 giây. ơ

Kh m : L y đi m tr ng tâm

ử ờ ấ

ọ

ể

)( dxx

m x

= 1

x 0

i n

)( dxx

(cid:229) (cid:242) (cid:242)

)( dxx

= 1

m x

)( dxx

(cid:242) (cid:229) (cid:242)

= 1 i U n

)( dxx

(cid:229) (cid:242)

= 1 i U

105

(cid:229) (cid:242)

Tính các tích phân

A(x)

H

m x

)(

dxx

x 0

)(

dxx

(cid:242)

a b x

(cid:242)

m1 m2

)

m x

)(

dxx

a -

+ ambm

( 3

2 m 2

2 bm 1

H 6

(

)(

dxx

)bam ++

m 2

(cid:242)

H 2

106

(cid:242)

5.8 NGUYÊN LÝ X LÝ CÁC BÀI TOÁN M (ti p)

Ờ ế

Ử

B đi u khi n

ộ ề

ể

ng Đ i t ố ượ đi u khi n ể ề

C m bi n ế ả (Sensor)

SISO: Single Input, Single Output

MIMO: Multi Input, Multi Output

SIMO: Single Input, Multi Output

107

MISO: Multi Input, Single Output

B đi u khi n m : ờ ộ ề ể

5.8 NGUYÊN LÝ X LÝ CÁC BÀI TOÁN M (ti p)

Ờ ế

Ử

SISO:

If (A is A1) Then (B is B1)

...

If (A is An) Then (B is Bn)

MIMO:

If (A1 is A11) and ... and (Am is Am1) Then (B1 is B11) and ... and (Bs is B1s) ... If (A1 is An1) and ... and (Am is An1) Then (B1 is Bn1) and ... and (Bs is Bns)

MISO:

If (A1 is A11) and ... and (Am is Am1) Then (B is B1) ... If (A1 is An1) and ... and (Am is An1) Then (B is Bn)

SIMO:

108

If (A is A1) Then (B1 is B11) and ... and (Bs is B1s) ... If (A is An) Then (B1 is Bn1) and ... and (Bs is Bns)

B đi u khi n m : ờ ộ ề ể

Bài t p: Đi u khi n m c n

c

ự ướ

ề

ể

ậ

Bài toán đi u khi n m c n ể ự ộ

ụ ỉ ỏ ề ả

ng ượ ng ượ c h trong ướ Không ph thu c vào l c: c ch y ra kh i bình, c n ph i đi u ch nh van cho l ầ c ch y vào bình v a đ đ sao cho m c n ủ ể ề ả ả ướ ướ ướ ự

n n ừ bình là luôn không đ i. ổ

Gi s b đi u khi n là con ng i, s có các nguyên t c sau: ả ử ộ ề ể ườ ẽ ắ

109

ở m c đ m thì van ị

c c c c . R1: N u ế m c n R2: N u ế m c n R3: N u ế m c n R4: N u ế m c n ự ự ự ự ở m c đ m to ướ là th pấ nhi u ề thì van ộ ở ứ ộ ở nhỏ ướ là th p ítấ ứ ở v trí đóng ướ là đủ thì van . ở v trí đóng ướ là cao thì van ị

Bài t p: Đi u khi n m c n

ự ướ

ề

ể

ậ

c(ti p) ế

ữ

c:có 4 giá tr T={th p nhi u, th p ít, đ , cao} ướ ự ấ ị ủ ề ấ

Các bi n ngôn ng : ế + x là m c n + y van: có 3 giá tr T={to, nh , đóng} ị ỏ

˛ c X [0 .. 3] (mét) M c n ự ướ

m (x)

Th p nhi u Th p đ cao

ủ

ề

ấ

0.7 0.4

1 1.5 2 2.5 3

110

Bài t p: Đi u khi n m c n

ự ướ

ề

ể

ậ

c(ti p) ế

Van Y ˛ [0 .. 10] (cm)

V i y là đ m c a van, T={to, nh , đóng} ộ ở ủ ỏ ớ

m (y)

đóng nh to

ỏ

c cao x

1 10 y ướ

0= 2 m, h i đ m c a van y ỏ ộ ở ủ

0 là bao

Cho m c n ự nhiêu

111

Ch

ươ

ng 6: Công c t o l p H CSTT ụ ạ ậ

ệ

H CSTT g m 3 thành ph n sau: 1. B t o l p c s tri th c: b o đ m các tính ả

ồ ộ ạ ậ

ầ ứ

ơ ở

ả

ữ ệ ư ừ

ơ

ễ

c ứ ầ ế ượ

i thích ộ ậ ả

ch t:ấ  Nh t quán ấ  Không mâu thu nẫ  Không d th a d li u  C p nh t d dàng ậ ễ ậ 2. B t o đ ng c suy di n ộ ộ ạ  V i m i cách bi u di n tri th c c n có chi n l ể ỗ ễ ớ suy di n t ng ng ứ ễ ươ  T o thu n ti n cho b ph n gi ệ ậ ạ ệ ộ ạ  Cung c p kh năng t o giao di n v i ng

i s d ng.

3. B t o các giao di n: ạ ấ

112

ớ ệ ả ườ ử ụ

Công c t o l p H CSTT

ụ ạ ậ

ệ

ạ

ứ

ạ ả ự ệ

ả ơ ả ạ

ạ ư ứ ầ

ị ầ ạ t cho m i đ i ế ỗ ố

ng.

ậ ư ủ

ắ ặ ự ự ứ ổ

ứ ử

ơ ở ệ ỷ ỏ  H so n th o tri th c làm vi c trên c s ngôn ng g c: ệ ữ ố

6.1 So n th o tri th c Các ch c năng c b n c a h so n th o tri th c: ứ ệ ủ ứ Cho phép so n th o các s ki n, các lu t. ậ ả Đ a ra ph m vi tri th c c n thu n p. Lên danh sách các giá tr c n thi t ượ Ki m tra s đúng đ n c a các lu t đ a vào. ể Ki m tra s trùng l p khi b sung tri th c. ể Cho phép s a đ i, hu b tri th c. ổ ứ nhiên. ứ

113

ạ ả – Ngôn ng t ữ ự – Ngôn ng hình th c. ữ

6.1 So n th o tri th c ả

ứ (ti p)ế

ạ

Các lu t d ng văn b n

ậ ạ

ả

ạ ậ ằ

Ngôn ng g c ữ ố

ớ

Ng pháp

ữ

1. So n th o các lu t b ng ả ngôn ng t nhiên v i cú ữ ự pháp h n ch . ế ạ

Ví d : ụ -

ộ

Phân tích t

v ng

ừ ự

T đi n ừ ể

Phân tích cú pháp

Ki m tra l

v ng:

Phân tích t

IF ch t l ng có đ PH<6 ấ ỏ THEN đó là Axit IF tam giác có 2 góc b ng ằ nhau THEN đó là tam giác cân i ỗ

ừ ự

ể

Ng pháp

ữ

chính tả

i

ể

ỗ

Bi u di n trong máy tính

ể

ễ

Phân tích cú pháp: Ki m tra l ệ

ặ

câu, đ t m nh đ . ề Bi u di n trong máy tính

ễ

ể

: G m ồ

các s ki n, các lu t.

ự ệ

ậ

C s tri th c ứ

ơ ở

114

B so n th o C s tri th c

ơ ở

ứ

ộ

ạ

ả

6.1 So n th o tri th c

ứ (ti p)ế

ạ

ả

2. So n th o các lu t theo cú pháp m nh đ Horn ề

H so n th o lu t = H so n th o văn b n + H phân tích cú ạ ệ ả ạ ậ ậ ệ ệ ạ ả ả

ệ ả pháp.

D ng t ng quát c a lu t: ủ ậ ạ ổ

IF AND AND ... AND THEN

ạ

Trong đó: Ci, C có d ng: ị ị

Cú pháp:

:= IF <đi u ki n> THEN <đk đ n gi n> ệ ề ơ ả

ệ ơ ả

ơ ừ ơ ả ị

115

ậ <Đi u ki n> := <đk đ n gi n> / <đk đ n gi n> AND <đk> ề <Đk đ n gi n> := / := < / £ ả ừ / > / ‡ / = / < >

Ví d : So n th o các lu t theo cú pháp m nh đ Horn

ụ

ệ

ề

ậ

ạ

ả

30 THEN trẻ

S ki n ự ệ

Lu tậ

Lu t:ậ Bi u di n bên trong: ể

IF tu i ổ £ ễ

Trẻ

Tu i ổ £ 30

Bi u di n bên ngoài:

ễ

ể

ậ

THEN

IF

<đk>

<đk đ n gi n> ơ

ả

<đk đ n gi n> ơ

ả

ừ

ị

30 tu i ổ

tr ẻ

116

6.1 So n th o tri th c

ứ

ạ

ả

ạ

ả

ộ

ợ

3. So n th o các lu t d a vào b ba liên h p O-A-V ậ ự D ng t ng quát c a lu t: ậ

ủ

ạ

ổ

IF AND AND ... AND THEN

c bi u di n d

i d ng b ba liên h p Object-Attribute-Value

ượ

ể

ễ

ướ ạ

ộ

ợ

Trong đó m i Cỗ i đ (O-A-V)

Nh câu l nh Horn, ngo i tr đi u ki n đ

ạ ừ ề

ệ

ượ

c thay b i: ở

Ng pháp:

ữ

<đi u ki n đ n gi n> :=

ng>

ố ượ

ệ

ề

ả

ộ

ị

c vi

i d ng:

Ghi chú: M i liên h gi a <đ i t ệ ữ

ố

ố ượ

ượ

ộ

ị

ế ướ ạ

<đ i t

ng> đ ố ượ

t d ng>. = ị

ộ

117

6.2. H chuyên gia d a trên lu t ậ

ự

ệ

ể

ị ự ệ

ể nhiên hi n th các ể ị

ằ ỉ ộ

6.2.1 Hi n th s ki n và lu t ậ 1. Hi n th s ki n: B ng ngôn ng t ị ự ệ ữ ự dòng văn b n ch n i dung s ki n ự ệ ả Cao huy t ápế Ví d : ụ Viêm ph i c p ổ ấ

ậ

2. Hi n th các lu t: ị • ể Trong ngôn ng t nhiên

ể

Bdi n khái ni m

ệ

ễ

Bi u di n ngoài ễ

ể

ữ ự Bi u di n trong ễ

Bdi n CSTT

ễ

Văn b nả

N ng c a KSTT

ữ ủ

Nng bd kni m

ữ

ệ

N ng t

nhiên

ữ ự

•

D i d ng đ th ồ ị ướ ạ

ﬁ q p1 (cid:217) p2 (cid:217) ... (cid:217) pn

Bi u di n khái ni m: ệ ễ p1 Bi u di n ngoài: ễ ể ể

p2

118

pn

6.2.2 C p nh t tri th c

ứ

ậ

1. C p nh t lu t: Khi c p nh t lu t c n

ầ

ậ

ề

ạ

ậ ể ế ế ẫ

ậ ẵ

ậ ự ệ

ể

ậ ki m tra các 2 đi u ki n: ệ - N u đã t n t i thì lo i b . ạ ỏ ồ ạ - N u ch a t n t i thì ki m tra có mâu ể ư ồ thu n ho c tranh ch p v i các lu t s n ớ ấ ặ có trong CSTT. 2. C p nh t s ki n: Ki m tra cú pháp và ậ duy t trong CSTT, n u trùng thì lo i b . ạ ỏ ế

ệ

119

6.2.2 C p nh t tri th c(ti p) ậ

ứ

ế

ậ

ơ ở

ẫ ự ư ừ ẫ

ư ừ ự ệ ứ

ậ ơ ở

ứ Tính mâu thu n trong c s tri th c: 1. S d th a các lu t, d th a s ki n 2. Mâu thu n trong c s tri th c 3. S nh t quán c a các lu t ậ

ủ

ự

ấ

120

1. S d th a các lu t, d th a s ki n

ự ư ừ

ư ừ

ự ệ

ậ

Cho t p SC=(SF,SR) Trong đó:

ơ ở ậ

ﬁ q, ký hi u SR ậ ậ ệ

Đn 5.1: Ta nói t p SR suy di n lu t r: left

SC: c s tri th c ứ SF: t p các s ki n ự ệ SR ={r1, r2, ..., rm} : t p lu t ậ ậ ri: lefti ﬁ q ễ ấ ả ậ ╞ r, t c các lu t trong SR thì cũng th a ỏ ỏ

nếu $ F˝ SF th a mãn t r. ụ

1: a ﬁ b, r2: b ﬁ c}╞ {a ﬁ c}

ủ ậ ủ ậ ậ ự ệ Ví d : SF={a, b, c}, SR={r Đn 5.2: Bao đóng c a t p lu t: SR Đn 5.3: Bao đóng c a t p s ki nX

+={r| SR╞r} ˝ SF là SR+} ng đ

ng n u: ươ ế ậ ậ

Đn 5.4: Hai t p lu t SR

121

X+={A| X ﬁ A ˝ 1 và SR2 là t SR1 ươ + = SR2 +

Thu t toán 6.1

ậ

Input: SR = {r1, r2, ..., rm}

X ˝ SF X+={A| X ﬁ A ˝ SR+}

Output: Method:

{ // r: left ﬁ q

{q};

TG = X; Sat = Loc(SR, TG); While (Sat „ ) do r = Get(Sat); TG = TG ¨ SR = SR \ {r}; Sat = Loc(SR, TG);

122

} X+ = TG Return X+

S d th a các lu t, d th a s ki n (ti p)

ự ư ừ

ư ừ

ự ệ

ế

ậ

ồ

c

d

Ví d : Cho SR g m các lu t: d ﬁ b (cid:217) e ﬁ c (cid:217) g ﬁ e (cid:217) g ﬁ c (cid:217) e ﬁ

ụ a (cid:217) b ﬁ c ﬁ a b (cid:217) c ﬁ a (cid:217) b (cid:217) dﬁ b c (cid:217) e ﬁ

e (cid:217) g c b d g

a

Ta có: {b, d}+ = (a,b,c,d,e,g}

123

S d th a các lu t, d th a s ki n (ti p)

ự ư ừ

ư ừ

ự ệ

ế

ậ

ộ ơ ở ậ

ự

ỏ

ế

ể

Đn 5.6: M t c s lu t SR là c c ti u n u th a: 1. M i lu t r

ậ ˛ SR có d ng Horn: ạ

˝ Left, sao cho:

ỗ r: p1 (cid:217) p2 (cid:217) ... (cid:217) pk ﬁ ậ ˛ SR, sao cho: (SR\{r})+ = SR+ i lu t r ồ ạ ﬁ q và t p con F i lu t r: left ậ ậ ồ ạ {F ﬁ q}] + = SR+

2. Không t n t 3. Không t n t [(SR\{r}) ¨ ề ư ừ ệ ậ

Ghi chú: Đi u ki n 2 tránh tình tr ng d th a lu t. Đi u ki n 3 tránh d th a s ki n. ạ ư ừ ự ệ ề

ệ ơ ở ậ

124

c, r2: a ﬁ ơ ở ậ ươ ’: a ﬁ ố ’ : b ﬁ i thi u là: ể c Ví d 1: Cho c s lu t: ụ SR = {r1: a (cid:217) b ﬁ Nh v y, c s lu t t ư ậ ’, r2 , r3} v i rớ 1 SR = {r1 b, r3: b ﬁ ng t ng đ ươ c ho c rặ 1

2. Mâu thu n trong c s tri th c ứ

ơ ở

ẫ

Đn 5.7: Các lu t r và r’ g i là xung đ t v i nhau n u t n t

i s liên h gi a

ế ồ ạ ự

ộ ớ

ệ ữ

ọ

p ; left ˝

left; nh ng p và q là

r’: left’ ﬁ

left’ ho c left’ ặ

ậ chúng nh sau: ư r: left ﬁ q ; mâu thu n nhau. ẫ

Ví d : ụ

r: IF A THEN B r’: IF A AND C THEN NOT B thi

ậ

ố

ế

ả

ậ

t vô d ng: là các lu t có k t lu n gi ng nhau và ế t t o nên h ng đ . ề

ụ thi ế ạ

ậ ằ

t p các ph n c a các gi ầ ậ Ví d : ụ

Đn 5.8: Các lu t có gi ả ủ r: IF A AND B THEN C r’: IF A AND NOT B THEN C

ể

ế

Có th thay th nh sau: r’’: IF A THEN C

Đn 5.9: Lu t n i vòng mâu thu n: Là dãy các lu t mà trong đó các k t qu ả

ế

thi

t ti p theo và trong chúng có gây

ộ

ủ

ậ ế ế

ả

Ví d : ụ

ậ ố ẫ c a lu t tr c là m t ph n c a gi ậ ướ ủ ầ mâu thu n gi a các s ki n. ự ệ ữ ẫ IF A AND B THEN C IF C AND D THEN NOT A

125

3. S nh t quán c a các lu t ậ

ự

ủ

ấ

Gi

ả

ơ ở

ứ

ẫ

i hai lu t r và r’ mâu thu n, c n ch ra

ồ ạ

ẫ

ầ

ỉ

i quy t mâu thu n trong c s tri th c: ế N u có t n t ậ lu t nào s lo i b

ẽ ạ ỏ ự

ố ủ

Ví d : r’: IF có ti n THEN mua xe máy

ế ậ Nguyên t c 1: ắ Lu t r’ đ ượ ậ ụ

r: IF có ti n THEN mua xe ôtô

D a vào tr ng s c a lu t ậ ọ c lo i b n u w(r’) < w(r) ạ ỏ ế ề ề

Ta có w(r’) < w(r)

ự

ệ

ấ

ệ

Nguyên t c 2: D a vào t n su t xu t hi n ắ ấ ầ Lu t r’ đ c lo i b n u f(r’) < f(r) ượ ậ ạ ỏ ế xa THEN không làm vi c ban đêm Ví d : r’: IF nhà ở ụ xa AND ph i tăng ca THEN có th làm r: IF nhà ể ở

ả

đêm

126

3. S nh t quán c a các lu t (ti p)

ự

ủ

ế

ậ

ấ

Nguyên t c 3:

ự

ắ ậ

D a vào lĩnh v c đang xét ẫ

ậ ậ

Nguyên t c 4:

ắ

ng h p tranh ch p (chung- riêng) ấ

r’: left ﬁ r : left’ ﬁ

q q’ và left ˝

left’

ị ườ ị ườ

r’: IF lu t r và r’ mâu thu n nhau AND lu t r thu c lĩnh v c A ự ộ AND lu t r’ thu c lĩnh v c B ự ộ AND đang xét lĩnh v c A ự THEN lo i b lu t r’ ạ ỏ ậ Tr ợ ườ IF lu t r và r’ mâu thu n nhau ẫ ậ ng h p chung r’ bi u th tr ợ ể ng h p riêng r bi u th tr ợ ể THEN Không áp d ng lu t r’ ậ ụ

127

6.3 Mô t

suy di n

ơ

ễ

ộ

 Suy di n tri th c ứ ễ  Đ ng c suy di n ễ ơ  Suy di n v i logic m nh đ : Suy di n ễ

ễ

ề

ệ

ti n, Suy di n lùi

ế

 Suy di n v i logic v t

ị ừ

: Suy di n ti n, ễ

ế

ớ ễ ễ ớ Suy di n lùi ễ

128

C ch suy di n

ơ

ế

ễ

:

ị ừ

ớ

nh trong logic m nh đ , thêm

ươ

ư

ề

ệ

2. Suy di n v i logic v t ễ - Suy di n ti n ế ễ - Suy di n lùi ễ ng t T ự vào phép h p gi

i ả

ợ

129

6.4 C ch đi u khi n

ế ề

ể

ơ

ng suy di n

ọ

ướ

ễ

6.4.1 Ch n h G i: ọ

ủ ể ậ

c ướ = Max #{r| r có th áp d ng cho t p con c a GT} ụ

1:a ﬁ b, r2:a ﬁ c, r3:a (cid:217) b (cid:217) c ﬁ d, r4:d(cid:217) b ﬁ e, r5:bﬁ

fGT = #GT fKL = # KL fTr fSau = Max #{r| r có cùng KL} Ví d : Rule ={r ụ r6:e ﬁ g} ﬁ e

ng suy di n: ướ

H i: a ỏ Ta có: fGT = 1, fKL = 1, fTr Heuristic ch n h Lu t 1: IF Lu t 2: IF ễ ễ ậ ậ fTr fTr

cướ =1, fsau=4 ễ ọ c ướ > fsau THEN Ch n Suy di n ti n ế ọ c ướ < fsau THEN Ch n Suy di n lùi ọ

130

6.4 C ch đi u khi n(ti p)

ế ề

ể

ế

ơ

ọ ọ ễ ễ

Lu t 3: IF ( Lu t 4: IF ( Lu t 5: IF ( ậ ậ ậ

c ướ = fsau) AND (fGT fKL) THEN Ch n Suy di n lùi c ướ = fsau) AND (fGT = fKL) THEN ế ế

t k mu n Ch n Suy di n ti n ọ ườ ố ễ ế

fTr fTr fTr IF Ng THEN Ch n Suy di n ti n ế ELSE Ch n Suy di n lùi i thi ọ ọ ễ ễ

Ghi chú: Thay vì dùng fTr

t và ố ậ ể ử ụ ự ệ

ả ự ệ ố ậ

cướ = c ướ và fSau ta có th s d ng f’ Tr thi S lu t trung bình s d ng cho các s ki n gi ế ử ụ f’Sau= S lu t trung bình s d ng cho các s ki n k t ế ử ụ lu n ậ

131

6.4.2 Gi

i quy t v n đ c nh tranh

ả

ế ấ

ề ạ

1. V n đ c nh tranh trong suy di n ti n:

q2 , left1

ế ễ ˝ F và ˝ F, left2

ề ạ ﬁ q1 , r2:left2 ﬁ ‡ 2

ế

ể

ề ậ

ọ ượ

Gi

ứ

ả

ượ

Gi

ể ử ụ

ứ

ậ

ả

ổ c thành Queue ổ c thành Stack

ượ

ng

Gi

ả

ả ủ

ế

ấ r1:left1 #l c(F,R) ọ V n đ : Làm th nào đ ch n 1 lu t r trong s ố ể ấ ậ c b i l c(F,R)? các lu t có th áp d ng đ ở ọ ụ i pháp 1: T ch c các lu t có th s d ng ể ử ụ ậ đ i pháp 2: T ch c các lu t có th s d ng đ i pháp 3: Dùng Heuristic: Dùng hàm c l ướ ượ đánh giá liên h gi a KL và v ph i c a các ệ ữ lu t.ậ

132

C nh tranh trong suy di n ti n

ế

ễ

ạ

Gi

ả

ồ ị

ự ệ i là

ả ủ

ế

i pháp 4: Dùng đ th FPG (Fact Precedence Graph): S ki n f ậ k nào đó có

fj) n u fế j là k t qu c a lu t r

ướ ự ệ j (fi ﬁ c s ki n f ở ế

tr ch a fứ i

$

fi ﬁ

ng đi đ n k t lu n là ng n

leftk (cid:217) fj =Rightk ậ

ế ắ

v trái, nghĩa là: fj (cid:219) ề

rk: fi ˛ ườ

ậ

f, ế 1:a ﬁ b, r2:a ﬁ c, r3:a (cid:217) b (cid:217) c ﬁ d, r4:d(cid:217) b ﬁ e, r5:bﬁ

Ch n lu t có chi u dài đ ọ Ví d : Rule ={r ụ r6:c ﬁ g} a

e

b

d

c

g

f

ﬁ

H i: a

ỏ

e, ta có h(r1,e)=1, h(r2,e)=2 Chon r1

133

C nh tranh trong suy di n ti n(ti p)

ế

ễ

ạ

Gi ả ồ ị

ậ i i pháp 5: Dùng đ th RPG (Rule Precedence Graph): Lu t r là tr i s ki n f sao cho: c lu t r ướ rj) n u t n t ậ j (ri ﬁ

ri: leftﬁ ng ch n h(r,r ọ c l ướ ượ ế ồ ạ ự ệ f và rj: ... f ... ﬁ q KL) là nh nh t ấ ỏ

Hàm Rule ={r1:a ﬁ b, r2:a ﬁ c, r3:a (cid:217) b (cid:217) c ﬁ d, r4:d(cid:217) b ﬁ e, r5:bﬁ f, r6:c ﬁ g}

r1

r3

r4

r5

r2

r6

134

ﬁ H i: a ỏ e, h(r1,r4)=1, h(r2,r4)=2 Ch n rọ 1

C nh tranh trong suy di n lùi

ễ

ạ

C nh tranh trong suy di n lùi x y ra

ễ

ạ

ả

v ph i:

khi: ớ ự ệ

ồ ạ ấ ậ ở ế ả

ﬁ ﬁ i ít nh t 2 lu t có f f

c ch n. V i s ki n f có t n t f và r2: left2 r1: left1 i pháp 1: N u i

i đ

Gi ộ

135

nh trong suy di n ti n ng t i pháp 2: Dùng đ thì FPG. ả T ễ ư ươ ự ế

6.5 B gi

i thích

ộ ả

ỏ

T i sao ph i xác đ nh s t n t

i / giá tr (s ,

ạ

ự ồ ạ

ị ố

i đ xác đ nh k t lu n KL. ợ ể ng đi t

ị ế

ế f đ n k t lu n ế

ậ ậ

ừ

6.5.1 Câu h i: Why? ả ị logic) c a m t s ki n f nào đó. ủ ộ ự ệ Tr l i: S ki n f có l ự ệ ả ờ K thu t: T n t i đ ồ ạ ườ ậ ỹ trong đ th FPG. ồ ị

(cid:219)

C s lu t R ơ ở ậ

(cid:222)

đ th FPG bi u di n b ng ma tr n A=(a

ồ ị ể

ễ

ậ

ằ

ij)

136

6.5 B gi

i thích (ti p)

ộ ả

ế

 Câu h i: How? ỏ

 Làm th nào mà h th ng l

i k t lu n s ki n

ệ ố

ế

ạ ế

ự ệ

ậ

 Tr l

f là đúng? ả ờ

ự ệ

ậ

i: H th ng đã k t lu n s ki n f là ế

ễ

ậ

ế đúng vì áp d ng t p Vet trong suy di n ti n ho c suy di n lùi

ệ ố ụ ễ

ặ

 K thu t: Xác đ nh t p

ị

ỹ

ậ V t T={r ế

1, r2, ..., rk}

ậ sao cho:

GTﬁ

{f}

Hai cách gi

ả

c.

- Gi - Gi

i thích: i thích tr n v n. ẹ ọ i thích t ng b ướ ừ

ả ả

137

Bài giảng: Các Hệ cơ sở tri thức - Nguyễn Đình Thuận

ệ ơ ở

ứ

Các H c s tri th c KBS: Knowledge Based Systems

ễ ệ ố

Nguy n Đình Thuân Khoa H th ng Thông tin ĐH Công ngh thông tin

TP HCM 1-2011

1

H c s tri th c

ệ ơ ở

ứ

Tài li u tham kh o

ệ

ả

Ch

ng 1: T ng quan v H c s tri th c

ươ

ề ệ ơ ở

ứ

ổ

ứ

1.1 Khái ni m v H C s tri th c ệ  H c s tri th c là ch

ề ệ ơ ở ứ ế ế ể ề ủ ệ

1.1 Khái ni m v H CSTT (Ti p)

ề ệ

ế

ệ

1.1 Khái ni m v H CSTT (Ti p)

ề ệ

ế

ệ

1.2 C u trúc c a H CSTT

ủ

ệ

ấ

1.2 C u trúc c a H CSTT(ti p)

ủ

ế

ệ

ấ

ệ ữ

i máy (User Interface): ậ

i thích (Explanation system):

ơ

ễ

1.2 C u trúc c a H CSTT(ti p)

ủ

ệ

ế

ấ

ầ ơ ở ậ

ồ ớ

1.3 Các đ c tính c a H CSTT

ủ

ệ

ặ

1.3 Các đ c tính c a H CSTT (ti p) ủ

ế

ệ

ặ

(ti p)ế

1.3 Các đ c tính c a H CSTT

ủ

ệ

ặ

Đ i t

ng so sánh

Ch

ố ượ

ươ

Các h CSTT ệ

ng trình bình th

ngườ

1.4 H h tr ra quy t đ nh

ệ ỗ ợ

ế ị

1.5 H h c

ệ ọ

ứ

ố