Tìm hiểu Các hệ cơ sở tri thức

Chia sẻ: Vũ Xuân Trường Trường | Ngày: | Loại File: PDF | Số trang:50

Thêm vào BST

Báo xấu

151
lượt xem 25
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Hệ CSTT là chương trình máy tính được thiết kế để mô hình hoá khả năng giải quyết vấn đề của chuyên gia con ngườ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 gia, dùng tri thức này để giải quyết vấn đề phức tạp thuộc cùng lĩnh vực. Hai yếu tố quan trọng trong Hệ CSTT là: tri thức chuyên gia và lập luận, tương ứng với 2 khối chính là cơ sở tri thức và động cơ suy diễn....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tìm hiểu 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 Công ngh Thông tin i h c Nha Trang Email: thuanvinh@vnn.vn Nha Trang 4-2007 1 H cơ s tri th c Chương 1: T ng quan v H c s tri th c Chương 2: Bi u di n và suy lu n tri th c Chương 3: H MYCIN Chương 4: H h c Chương 5: H th ng m cho các bi n liên t c 2 1
Tài li u tham kh o [1] Rich Elaine. Artificial Intelligence. Addison Wesley 1983 [2] Robert I. Levine. Knowledge based systems. Wissenschafs Verlag, 1991 [3] Trung Tu n. H chuyên gia. NXB Giáo d c 1999 [4] Hoàng Ki m. Giáo trình Các h cơ s tri th c. HQG TP H Chí Minh. 2002 3 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ương trình máy tính ư c thi t k mô hình hoá kh năng gi i quy t v n c a chuyên gia con ngư 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 gia, dùng tri th c này gi i quy t v n ph c t p thu c cùng lĩnh v c. Hai y u t quan tr ng trong H CSTT là: tri th c chuyên gia và l p lu n, tương ng v i h th ng có 2 kh i chính là Cơ s tri th c và ng cơ suy di n. 4 2
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 ư c thi t k cho m t lĩnh v c ng d ng c th . 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 hóc c a ư ng dây i n tho i,… 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ư i ã ư c ưa vào H Chuyên gia. 5 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 . 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. K sư tri th c (Knowledge Engineer): ngư i thi t k , xây d ng và th nghi m H Chuyên 6 gia. 3
1.2 C u trúc c a H Chuyên gia 7 1.2 C u trúc c a H Chuyên gia(ti p) 1. Giao di n ngư i máy (User Interface): Th c hi n giao ti p gi a H Chuyên gia và User. Nh n các thông tin t User (các câu h i, các yêu c u v lĩnh v c) và ưa ra các câu tr l i, các l i khuyên, các gi i thích v lĩnh v c ó. Giao di n ngư i máy bao g m: Menu, b x lý ngôn ng t nhiên và các h th ng tương tác khác. 2. B gi i thích (Explanation system): Gi i thích các ho t ng khi có yêu c u c a User. 3. ng c suy di n (Inference Engine): Quá trình 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ơ s tri th c, rút ra các k t lu n v v n ang gi i quy t. 8 4
1.2 C u trúc c a H Chuyên gia(ti p) 4. B ti p nh n tri th c (Knowledge editor): Làm nhi m v thu nh n tri th c t chuyên gia con ngư i (human expert), t k sư tri th c và User thông qua các yêu c u và lưu tr vào cơ s tri th c 5. C s tri th c: Lưu tr , bi u di n các tri th c mà h m nh n, làm cơ s cho các ho t ng c a h . Cơ s tri th c bao g m các s ki n (facts) và các l t (rules). 6. Vùng nh làm vi c (working memory): M t ph n c a H Chuyên gia ch a các s ki n c a v n ang xét. 9 1.3 H h tr ra quy t nh 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ư i s d ng Các tính ch t c a DSS: Hư ng n các quy t nh c a ngư i qu n lý Uy n chuy n v i hoàn c nh Tr l i câu h i trong tình hu ng Do ngư i s d ng kh i ng và ki m soát 10 5
1.4 H h c Trong nhi u tinh hu ng, s không có s n tri th c như: K sư tri th c c n thu nh n tri th c t chuyên gia lĩnh – v c. C n bi t các lu t mô t lĩnh v c c th . – Bài toán không ư c bi u di n tư ng minh theo lu t, s – ki n hay các quan h . Có hai ti p c n cho h th ng h c: 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ư ng minh, s ki n và các quan h . H c t d li u s : ư c áp d ng cho nh ng h th ng – ư c mô hình dư 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 di truy n, bài toán t i ưu truy n th ng. Các k thu t h c theo s không t o ra CSTT tư ng minh. 11 1.5 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 xác nh giá tr m Gi i m : Phương pháp i m tr ng tâm 12 6
1.6 ng d ng c a H Cơ s tri th c Di n gi i (Interpretation): Mô t tình hu ng 1. các d li u thu th p ư c D báo (Prediction): ưa ra các tri th c v 2. d báo m t tình hu ng: d báo giá c , … Thi t k (Design): L a ch n c u hình phù 3. h p, ví d : s p x p công vi c. Ch n oán (Diagnosis): D a vào các d 4. li u quan sát ư c, xác nh các l i h ng hóc. 13 1.6 ng d ng c a H Cơ s tri th c(ti p) V ch k ho ch (Planing): t o l p các 5. phương án hành ng. D n d t (Monotoring): So sánh d li u và 6. các k t qu ho t ng. G r i (Debugging): Mô t các phương 7. pháp kh c ph c c a h th ng. Gi ng d y (Instruction): S a ch a các l i 8. c a ngư i h c trong quá trình h c t p. i u khi n (Control): d n d t dáng i u 9. t ng th c a h th ng. 14 7
Chương 2: Bi u di n và suy lu n tri th c 2.1. M u tri th c, lĩnh v c và bi u di n tri th c. 2.2. Các lo i tri th c: ư c chia thành 5 lo i Tri th c th t c: mô t cách th c gi i quy t m t v n . Lo i 1. tri th c này ưa ra gi i pháp th c hi n m t công vi c nào ó. Các d ng tri th c th t c tiêu bi u thư ng là các lu t, chi n lư c, l ch trình và th t c. Tri th c khai báo: cho bi t m t v n ư c th y như th 2. nào. Lo i tri th c này bao g m các phát bi u ơn gi n, dư i 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 ó. 15 2.2. Các lo i tri th c (ti p) Siêu tri th c: 3. mô t tri th c v tri th c. 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 gi i quy t m t v n . Các chuyên gia s d ng tri th c này i u ch nh hi u qu gi i quy t v n b ng cách hư ng các l p lu n v mi n tri th c có kh năng hơn c . Tri th c heuristic: mô t các "m o" d n d t ti n 4. trình l p lu n. Tri th c heuristic là tri th c không b m m hoàn toàn 100% chính xác v k t qu gi i quy t v n . Các chuyên gia thư ng dùng các tri th c khoa h c như 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. Tri th c có c u trúc: mô t 5. tri th c theo c u trúc. Lo i tri th c này mô t mô hình t ng quan h th ng theo quan i m c a chuyên gia, bao g m khái ni m, khái ni m con, và các i tư ng; di n t ch c năng và m i liên h gi a các tri th c d a theo c u trúc xác nh. 16 8
Ví d : Hãy phân lo i các tri th c sau 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, DFS 6. Thu t gi i Greedy 7. M t s cách chi u tư ng trong vi c chơi c tư ng. 8. H th ng các khái ni m trong hình h c. 9. Cách t p vi t ch p. 10. Tóm t t quy n sách v H chuyên gia. 11. Ch n lo i c phi u mua c phi u. 17 2.3. CÁC K THU T BI U DI N TRI TH C 2.3.1 B ba i tư ng-Thu c tính-Giá tr 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 18 9
2.3.1 B ba i tư ng-Thu c tính-Giá tr M t s ki n có th ư c dùng xác nh n giá tr c a m t thu c tính xác nh c a m t vài i tư ng. Ví d , m nh "qu bóng màu " xác nh n " " là giá tr thu c tính "màu" c a i tư ng "qu bóng". Ki u s ki n này ư c g i là b ba i tư ng-Thu c tính-Giá tr (O-A-V – Object-Attribute-Value). Hình 2.1. Bi u di n tri th c theo b ba O-A-V 19 2.3.1 B ba i tư ng-Thu c tính-Giá tr (ti p) Trong các s ki n O-A-V, m t i 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ũng có th có m t hay nhi u giá tr . Chúng ư c g i là các s ki n ơn tr (single-valued) ho c a tr (multi-valued). i u này 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 t. Các s ki n không ph i lúc nào cũng b o m là úng hay sai vi ch c ch n hoàn toàn. Ví th , khi xem xét các s ki n, ngư i ta còn s d ng thêm m t khái ni m là tin c y. Phương pháp truy n th ng qu n lý thông tin không ch c ch n là s d ng nhân t ch c ch n CF (certainly factor). Khái ni m này b t u t h th ng MYCIN (kho ng năm 1975), dùng tr l i cho các thông tin suy lu n. Khi ó, trong s ki n O-A-V s có thêm m t giá tr xác nh tin c y c a nó là CF. 20 10
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 nh ng thông tin ã bi t. Trong h th ng d a trên các lu t, ngư 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 gi i bài toán. Vi c x lý các lu t trong h th ng d a trên các lu t ư c qu n lý b ng m t module g i là b suy di n. 21 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 : IF Bình i n h ng THEN Xe s không kh i ng ư c 2. L i khuyên: IF Xe không kh i ng ư c THEN i b 3. Hư ng d n IF Xe không kh i ng ư c AND H th ng nhiên li u t t THEN Ki m tra h th ng i n 22 11
2.3.2 Các lu t d n(ti p) 4. Chi n lư c IF Xe không kh i ng ư c 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 5. Di n gi i IF Xe n AND ti ng giòn THEN ng cơ ho t ng bình thư ng 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 23 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ư ng gi ng nhau. Lúc ó c n các lu t có bi n. 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 ch n, ngư i ta dùng h s ch c ch n CF. Lu t thi t l p quan h không chính xác gi a các s ki n gi thi t và k t lu n ư c g i là lu t không ch c ch n. Ví d : IF L m phát CAO THEN H u như ch c ch n lãi su t s CAO Lu t này ư c vi t l i v i giá tr CF có th như sau: IF L m phát cao THEN Lãi su t cao, CF = 0.8 D ng lu t ti p theo là siêu lu t: M t lu t v i ch c năng mô t cách th c dùng các lu t khác. Siêu lu t s ưa ra chi n lư c s d ng các lu t theo lĩnh v c chuyên d ng, thay vì ưa ra thông tin m i. Ví d : IF Xe không kh i ng AND H th ng i n làm vi c bình thư ng 24 THEN Có th s d ng các lu t liên quan n h th ng i n 12
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 tư ng và cung bi u di n quan h gi a các i tư ng. Hình 2.3. "S là Chim" th hi n trên m ng ng nghĩa 25 2.3.3 M ng ng nghĩa(ti p) Hình 2.4. Phát tri n m ng ng nghĩa 26 13
2.3.4 Frame Hình 2.6. C u trúc frame Hình 2.7. Nhi u m c c a frame mô t quan h ph c t p hơn 27 2.3.5 Logic 1. Logic m nh IF Xe không kh i ng ư c (A) AND Kho ng cách t nhà n ch làm là xa (B) THEN S tr gi làm (C) Lu t trên có th bi u di n l i như sau:A∧B⇒ C 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. 28 14
2.4 SUY DI N D LI U 1. Modus ponens 1. E1 2. E1→ E2 3. E2 N u có tiên khác, có d ng E2 → E3 thì E3 ư c ưa vào danh sách. 2. Modus tollens 1. ¬ E2 2. E1→ E2 3. ¬ E1 29 2.4.2 Các ho t ng c a H th ng Suy di n ti n 30 15
Ví d v Suy di n ti n Lu t 1. IF B nh nhân rát h ng 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. Thông tin t b nh nhân là: · B nh nhân có nhi t 39 · 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 nh , câu k t lu n c a lu t ư c b sung vào b nh . Ví d suy di n lùi Minh h a 31 Cơ ch suy di n Suy di n v i logic m nh : 1. Thu t toán suy di n ti n - T p lu t Rule= {r1, r2, ..., rm} Input: - GT, KL Output: Thông báo “thành công” n u GT→KL Ngư c l i, thông báo “không thành công” Method: TD=GT; T=Loc(Rule, TD); While (KL ⊄ TD) AND (T≠∅) Do { r = Get(T); TD=TD∪{q}; // r:left→ q Rule = Rule \ {r}; T=Loc(Rule, TD); } If KL⊆ TD THEN Return “True” else Return “False” Ví d : Rule ={r1:a →c, r2:b →d, r3:a →e, r4:a∧d →e, r5:b ∧ c →f, r6:e ∧f→g} H i a ∧ b →g? 32 16
Thu t toán suy di n lùi If KL ⊆ GT THEN Return “True” Else {T ích=∅; V t = ∅; First=1; Quaylui= False;} For Each q∈KL DO T ích=T ích∪{(q,0)}; Repeat first ++; ((f,i)=Get(T ích); If (f∉GT) THEN { // rj: Leftj → f j = Tìmlu t(f,i,Rule); If (Tìm có rj) THEN { Vet = Vet ∪{(f,j)}; For Each t∈ (Leftj\GT) DO T ích = T ích∪{((t,0)}; else { Quaylui=True; While (f∉KL) AND Quaylui DO { Repeat { (g,k)=Get(V t); T ích = T ích \ Leftk;} Until f∈Leftk; 33 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 \ Leftk ; For Each t∈ (Leftl\GT) DO T ích = T ích∪{((t,0)}; V t = V t ∪ {(g,l)}; Quaylui = False; } //end if3 else f=g; } //end while } //enf if2 }//end if1 Until (T ích = ∅) OR ((f ∈KL) and (First>2)); If (f ∈KL) then Return False else Return TRue; Ví d : Rule ={r1:a →c, r2:b →d, r3:a →e, r4:a∧d →e, r5:b ∧ c →f, r6:e∧f→g} H i a ∧ b →g? Ví d 2: Rule ={r1:a∧b→c, r2:a∧h→d, r3:b∧c→e, r4:a∧d→m, r5:a∧b→p, r6:p∧e→m} H i i) a ∧ b →m? ii) a →m? 34 17
2.4.3 Ưu i m * Suy di n ti n • Ư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 m t s thông 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ư ng i v i lo i bài toán c n gi i 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 •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 toán ưa ra gi thuy t r i xem hi u q a gi thi t ó có úng không. •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ư i dùng. •Khi suy di n lùi mu n suy di n cái gì ó t các thông tin ã bi 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. 35 2.4.4 Như c i m * 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 m nh n ư c r ng ch m t vài thông tin là quan tr ng. H th ng h i các câu h i có th h i mà không bi t r ng ch m t ít câu ã i n k t lu n ư c. • H th ng có th h i c câu không liên quan. Có th các câu tr l i cũng quan tr ng, nhưng làm ngư i dùng lúng túng khi ph i tr l i các câu không dính n ch . * Suy di n lùi •Như c i m cơ b n c a suy di n này là nó thư ng ti p theo dòng suy di n, thay vì úng ra ph i úng ó mà sang nhánh khác. Tuy nhiên có th dùng nhân t tin c y và các lu t meta kh c ph c. 36 18
Chương 3: H MYCIN 3.1 Gi i thi u MYCIN là m t h l p lu n trong y h c ư c hoàn t t vào năm 1970 t i i h c Standford, Hoa Kỳ. ây là m t h chuyên gia d a trên 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 quát ư c t o l p b ng cách lo i ph n cơ s tri th c ra kh i h 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: - 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 i thích: HOW, WHY. 37 M t phiên làm vi c c th v i MYCIN: ?Thông tin v b nh nhân MYCIN: H và tên? User: Jack Durkin. MYCIN: Tu i? User: 24. MYCIN: Gi i tính? User: Nam. MYCIN: Ch ng t c? User: CAUCASIAN. …… ? Xác nh b n ch t lây nhi m MYCIN: Có b t k ỳ phép c y vi khu n cho Jack Durkin liên quan n b nh hi n t i? User: Có. MYCIN: M u v t l y t âu? User: CSF. MYCIN: Ngày gi th c hi n c y: User: 5-6-77 8:09 AM ….. MYCIN: G n ây Jack Durkin có các tri u ch ng như: choáng ván, hôn mê không? User: Có. ….. 38 19
CÁC THÀNH PH N C A H MYCIN 1. Chương trình tư v n: Cung c p cho các Bác sĩ các l i khuyên ch n phương pháp i u tr thích h p b ng cách xác nh rõ cách th c i u tr b i các d li u l y ra t các phòng thí nghi m lâm sàng 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 i thích có tác ng qua l i: Cho phép chương trình tư v n gi i thích các ki n th c c a nó v các phương pháp i u tr và ch ng minh các chú thích v các phương pháp i u tr c bi t. 3. Thu n p tri th c: cho phép các chuyên gia con ngư i trong lĩnh v c i u tr các căn b nh truy n nhi m d y cho MYCIN các lu t quy t nh theo phương pháp i u tr mà h tìm th y trong th c t lâm sàng. 39 PH M VI S D NG C A H MYCIN 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 ch n m t 24-48 gi . Nhi u trư ng h p ph i i u tr c ngay khi chưa có k t lu n hoàn ch nh. MYCIN giúp ch n oán nguyên nhân gây b nh nhanh hơn: khi g i chương trình MYCIN, các bác sĩ tr l i các câu h i v ti u s b nh nhân, 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. 2. T o ra phương pháp i u tr : Sau khi nh n ư c các câu tr l i c a bác sĩ v tình tr ng b nh nhân thông qua i tho i. Trong trư ng h p câu tr l i không bi t ho c bi t không ch c ch n, thì MYCIN s suy lu n t các thông tin không hoàn ch nh. 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ĩ. Sau khi vi c ch n oán b nh và kê ơn hoàn t t, bác sĩ có th 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 40 20