Bài giảng: Các hệ cơ sở trí thức

Chia sẻ: quangdat

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. Cơ sở dữ liệu quan hệ: dữ liệu được lưu trữ trong các bảng dữ liệu gọi là các thực thể, giữa các thực thể này có mối liên hệ với nhau gọi là các quan hệ, mỗi quan hệ có các thuộc...

Bạn đang xem 10 trang mẫu tài liệu này, vui lòng download file gốc để xem toàn bộ.

Nội dung Text: Bài giảng: Các hệ cơ sở trí thức

z






Bài giảng: Các hệ cơ sở trí 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à
4 ng cơ suy di n.




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

1. Di n gi i (Interpretation): Mô t tình hu ng
các d li u thu th p ư c
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 , …
3. Thi t k (Design): L a ch n c u hình phù
h p, ví d : s p x p công vi c.
4. Ch n oán (Diagnosis): D a vào các d
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)

5. V ch k ho ch (Planing): t o l p các
phương án hành ng.
6. D n d t (Monotoring): So sánh d li u và
các k t qu ho t ng.
7. G r i (Debugging): Mô t các phương
pháp kh c ph c c a h th ng.
8. Gi ng d y (Instruction): S a ch a các l i
c a ngư i h c trong quá trình h c t p.
9. i u khi n (Control): d n d t dáng i u
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
1. Tri th c th t c: mô t cách th c gi i quy t m t v n . Lo i
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.
2. Tri th c khai báo: cho bi t m t v n ư c th y như th
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)
3. Siêu tri th c: 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 .
4. Tri th c heuristic: mô t các "m o" d n d t ti n
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.
5. Tri th c có c u trúc: mô t 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
v i 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 .

Minh h a Ví d suy di n lùi

31




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= {r1, r2, ..., rm}
- 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

{
j = Tìmlu t(f,i,Rule); // rj: Leftj → f
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
35 ang xét.




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
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
sinh ã em l i không ít ph n ng ph .
2. Cơ s tri th c c a MYCIN ư c thu n p t các
chuyên gia xu t s c nh t trong lĩnh v c.
3. MYCIN không bao gi i n ngay k t lu n luôn
có thêm các thông tin c t y u qua m i bư c.
4. MYCIN ư c hình thành t m t chương trình trí tu
nhân t o ã ư c áp d ng th c t (DENDRAL) và
ã ư c th c hi n t i trung tâm y t n i ti ng v i các
tri th c m i nh t v b nh h c và dư c h c.

41




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
có ch ng c E.
MD(H/E) là o s không tin c y c a gi thuy t H
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
o ch c ch n CF(H/E) ư c tính b ng công th c:
CF(H/E) = MB(H/E) – MD(H/E)

42




21
3.2 LÝ THUY T V S CH C CH N(ti p)

1. Lu t ơn gi n: If(e) then (c)
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 ư c tính
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))
43




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
- 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
CF(t1) và Cf(t2) u dương thì:
Ct ng = CF(t1) + CF(t2) – CF(t1) * CF(t2)
Khi CF(t1) và Cf(t2) u âm thì:
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))))

44




22
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
hình 3.1 v i c5 là gi thuy t c n hư ng n.

45




Hình 3.1. M ng suy di n




46




23
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



47




L p lu n trên m ng suy di n (ti p)
Chúng ta s l p lu n t các CF c a ch ng c d n
lên gi thuy t c5 như sau:
D a vào lu t r1 tính ư c CF(c1):
CF(c1) = CF(e1) * CF(r1) = 0,8*0,9 = 0,72
D a vào lu t r2, r3 tính ư c CF(c2)
V i lu t r2: CF(c2) = CF(e2) * CF(r2) = 0,9 * 0,9 =
0,81
V i lu t r3: CF(c2) = CF(e3) * CF(r3) = -0,3 * 0,7 = -
0,21
Do CF(c2) c a r2 trái d u v i CF(c2) c a r3, nên:
CF(c2)t ng = (0,81 + (-0,21)) / (1-MIN (0,81, 0,21)) =
0,74


48




24
L p lu n trên m ng suy di n (ti p)
D a vào lu t r4, r5 ta tính ư c CF(c3)
V i lu t r4:
CF(c3) = CF(e4) * CF(r4) = 0,4 * 0,6 = 0, 24
V i lu t r5:
CF(c3) = CF(NOT e5)*CF(r5) = -CF(e5)*CF(r5) = 0,3*0,5 = 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 r6 ta tính ươc CF(c4):
CF(c4) = MIN(CF(c2), CF(c3)) * CF(r6) = MIN(0,74, 0,354) * 0,9
= 0,354 * 0,9 = 0,3186
D a vào lu t r7 ta tính ư c CF(c5)
CF(c5) = MAX(CF(c1), CF(c4)) * CF(r7) = MAX(0,72, 0,3186) *
0,8 = 0,576
Như th ch c ch n c a gi thuy t c5 là 0,576.


49




Chương 4 H h c

4.1 M U
Các chương trư c ã th o lu n v bi u di n và suy lu n tri
th c. Trong trư ng h p này gi nh ã có s n tri th c và
có th bi u di n tư ng minh tri th c.
Tuy v y 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.
50




25
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ương tác.
2. H c b ng cách ch d n: Thay vì ưa ra m t lu t c th
c n áp d ng vào tình hu ng cho trư c, h th ng s
ư c cung c p b ng các ch d n t ng quát. Ví d : "gas
h u như b thoát ra t van thay vì thoát ra t ng d n".
H th ng ph i t mình ra cách bi n i t tr u
tư ng n các lu t kh d ng.
3. H c b ng qui n p: H th ng ư c cung c p m t t p
các ví d và k t lu n ư c rút ra t t ng ví d . H liên
t c l c các lu t và quan h nh m x lý t ng ví d m i.
51




4.2 CÁC HÌNH TH C H C (Ti p)
4. H c b ng tương t : H th ng ư c cung c p áp ng úng
cho các tác v tương 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: H th ng phân tích t p các l i gi i ví
d (và k t qu ) nh m n nh kh năng úng ho c sai và t o
ra các gi i thích dùng hư ng d n cách gi i bài toán trong
tương lai.
6. H c d a trên tình hu ng: B t kỳ tính hu ng nào ư c h
th ng l p lu n u ư c lưu tr cùng v i k t qu cho dù
úng hay sai. Khi g p tình hư ng m i, h th ng s làm thích
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: Thay vì có m c tiêu tư ng
minh, h khám phá liên t c tìm ki m các m u và quan 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ơ b n như
c nh t các i m nh.

52




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

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ư ng




53




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.
- Do Quinlan ưa ra năm 1979.
- Ý tư ng: Ch n thu c tính quan tr ng nh 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 cho t m i b ng con này d phân tích
tìm quy lu t chung.

54




27
4.3.1 THU T GI I A. Quinlan

STT Size Nationality Family Conclusion

1 Small German Single A

2 Large French Single A

3 Large German Single A

4 Small Italian Single B

5 Large German Married B

6 Large Italian Single B

7 Large Italian Married B

8 Small German Married B
55




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) = (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(Size=Small) = (1/3 , 2/3)
V(Size=Large) = (2/5 , 3/5)
V i thu c tính Nationality
V(Nat = German)= (2/4 , 2/4)
V(Nat = French) = (1 , 0)
V(Nat = Italian) = (0 , 1)
Thu c tính Family:
V(Family=Single) = (2/5 , 3/5)
V(Family = Married) = (0, 1)


56




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

Ch còn xét German STT Size Family Conclusion
•Thu c tính Size:
V(Size=Small) = (1/2 , 1/2) 1 Small Single A
V(Size=Large) = (1/2 , 1/2)
•Thu c tính Family: 2 Large Single A
V(Family=Single) = (1, 0)
3 Large Married B
V(Family=Married) = (0,1)
4 Small Married B


Nationality


Italian French German

57
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)
58 then (Conclusion IS B)




29
Thu t gi i: H c theo b t nh

Stt Age Competition Type Profit

1 Old No Software Down

2 Midle Yes Software Down

3 Midle No Hardware Up

4 Old No Hardware Down

5 New No Hardware Up

6 New No Software Up

7 Midle No Software Up
59
8 New Yes Software Up




H c theo b t nh(ti p)

b t nh c a X:
k
E ( X ) = -∑ pi log 2 pi
i =1




Tính Entropy cho m i thu c tính và ch n thu c tính
có Entropy nh nh t.
k
E (C / A) = -∑ p (ci , ai ) log 2 p (ci , ai )
i =1

4 4 2 2
E (C / Competitio n = No ) = - log 2 - log 2 = 0.918
6 6 6 6
1 1 3 3
E (C / Competitio n =Yes ) = - log 2 - log 2 = 0.811
4 4 4 4
E (C / Competitio n ) = 0.6 * 0.918 + 0.4 * 0.811 = 0.8752
60




30
H c theo b t nh(ti p)

Tương t : STT Competition Type Profit
E(C/Age) = 0.4 1 Yes Software Down
E(C/Type) = 1
2 No Hardware Up
Age cho nhi u thông
tin nh t 3 No Software Up

4 Yes Hardware Down
Age


Old Milde New


Down Competition Up
No Yes
61
Up Down




H c theo b t nh(ti p)
Age


Old Milde New


Down Competition Up
No Yes
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)
62 then (Profit IS Down)




31
4.4 THU T GI I ILA(Inductive Learning Algorithm)

Xác nh d li u
1. T p m u ư c li t kê trong m t b ng, v i m i dòng
tương ng m t m u, và m i c t th hi n m t thu c
tính trong m u.
2. T p m u có m m u, m i m u g m k thu c tính và
trong ó có m t thu c tính quy t nh. T ng s n các
giá tr c a thu c tính quy t nh chính là s l p c a
t p m u.
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 ư c
ánh d u (ki m tra).


63




4.4 THU T GI I ILA(ti p)
Bư c 1: Chia b ng m m u ban u thành n b ng con.
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ư c 2 n 8 cho m i b ng con*)
Bư c 2: Kh i t o bi n m k t h p thu c tính j, j=1.
Bư c 3: V i m i b ng con ang kh o sát, phân chia
danh sách các thu c tính theo các t h p phân bi t, m i
t h p ng v i j thu c tính phân bi t.
Bư c 4: V i m i t h p các thu c tính, tính s lư 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
này trên các b ng còn l i). G i t h p u tiên (trong
b ng con) có s l n xu t hi n nhi u nh t là t h p l n
nh t.
64




32
4.4 THU T GI I ILA(ti p)

Bư c 5: N u t h p l n nh t b ng ∅, tăng j lên 1 và
quay l i bư c 3.
Bư c 6: á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 7: Thêm lu t m i vào t p lu t R, v i v trái là t p
các giá tr c a thu c tính ng v i t h p l n nh t (k t
h p các thu c tính b ng toán t AND) và v ph i là giá
tr thu c tính quy t nh tương ng.
Bư c 8: N u t t c các dòng u ã ư c ánh d u
phân l p, ti p t c th c hi n t bư c 2 cho các b ng con
còn l i. Ngư c l i (n u chưa ánh d u h t các dòng) thì
quay l i bư c 4. N u t t c các b ng con ã ư c xét thì
65 k t thúc, k t qu thu ư c là t p lu t c n tìm.




Minh h a thu t gi i ILA

M us Size Color Shape Decision
1 medium blue brick yes
2 small red wedge no
3 small red sphere yes
4 large red wedge no
5 large green pillar yes
6 large red pillar no
7 large green sphere yes
66 B ng 4.1 T p m u h c cho bài toán phân l p i tư ng




33
Minh h a thu t gi i ILA(ti p): Bư c 1

B ng con 1
M u s cũ, m i Size Color Shape Decision

1 1 medium blue brick yes
3 2 small red sphere yes
5 3 large green pillar yes
7 4 large green sphere yes
B ng con 2
M u s cũ m i Size Color Shape Decision
2 1 small red wedge no
4 2 large red wedge no
6 3 large red pillar no
67 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)

• Áp d ng bư c 2 c a thu t gi i vào b ng con th
nh t trong b ng trên. V i j=1, danh sách các t h p
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, nên không
ư c xét trong bư c này. V i t h p {Size}, giá tr
thu c tính "medium" ch b ng 1

68




34
Minh h a thu t gi i ILA(ti p)

• Xét ti p cho t h p {Color} thì giá tr t h p l n nh 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 , v i 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, ta
có t h p {Color} v i thu c tính "green" và {Shape}
v i thu c tính "sphere" u có s l n xu t hi n l n
nh t là 2. Thu t toán m c nh ch n trư ng h p th
nh t xác nh lu t t h p l n nh t. Dòng 3 và 4
ư c ánh d u ã phân l p, ta có lu t d n như sau:

Rule 1: IF color IS green THEN decision IS yes
69




Minh h a thu t gi i ILA(ti p)

• Ti p t c th c hi n bư c 4 n 8 cho các m u còn l i (chưa
ánh d u) trong b ng con này (t c dòng 1 và 2). Áp d ng tương
t như trên, ta th y giá tr thu c tính "medium" c a {Size}, "blue"
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

ánh d u cho dòng 1 trong b ng con th nh t. Ti p t c áp
d ng bư c 4 n 8 trên dòng còn l 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 ư c ánh d u. Như v y, t t c các dòng trong b ng con 1 ã
ư c ánh d u, ta chuy n qua x lý ti p b ng con 2.
70




35
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

• 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 gi i,
ta lo i b trư ng h p này. Tương t như v y cho giá tr "red" c a
{Color} và "pillar" c a {Shape}. Khi ó, ILA tăng j lên 1, và kh i t o các
t h p 2 thu c tính là {Size và Color}, {Size và Shape}, và {Color và
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
71




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

ánh giá thu t gi i:
• S lư ng các lu t thu ư c xác nh m c thành công c a thu t
gi i. ây chính là m c ích chính c a các bài toán phân l p thông
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 ư c ưa vào sau này.
• Thu t gi i ILA ư c ánh giá m nh hơn hai thu t gi i v phương
pháp h c quy n p trư c ây là ID3 và AQ).

72




36
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 nhiên và logic m .
- T p rõ (crisp set): G i A là m t t p h p rõ, m t ph n t x
có th có x∈A ho c x∉A, Có th s d ng hàm χ mô
t khái ni m thu c v . N u x ∈A, χ(x) = 1, ngu c l i n u
x ∉ A, χ (x)=0. Hàm χ ư c g i là hàm c trưng c a
t p h p A.
- T p m và hàm thành viên: Khác v i t p rõ, khái ni m
thu c v ư c m r ng nh m ph n ánh m c x là
ph n t c a t p m A. M t t p m (fuzzy set): A ư c
c trưng b ng hàm thành viên µ và cho x là m t ph n
t , µA(x) ph n ánh m c x thu c v A.
- M t t p m A trong t p vũ tr U ư c xác nh b i hàm:
73 µA: U →[0,1]




5.1 Các khái ni m v Logic m
• Ví d v t p m :
- High
- Young
- S g n7
- T c nhanh
Bi u di n 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
ư c bi u di n:
µ A ( x)
A= ∑
x∈U x


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

0 .3 0 .5 0 0 .7
A = + + +
a b c d
74




37
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:

µ A ( x)
A= ∫
x∈U
x
dx


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


2
µ A ( x) = e -(x -2)
2
e -(x -2)
A= ∫U x dx
x∈




75




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:


0 n u x
Đề thi vào lớp 10 môn Toán |  Đáp án đề thi tốt nghiệp |  Đề thi Đại học |  Đề thi thử đại học môn Hóa |  Mẫu đơn xin việc |  Bài tiểu luận mẫu |  Ôn thi cao học 2014 |  Nghiên cứu khoa học |  Lập kế hoạch kinh doanh |  Bảng cân đối kế toán |  Đề thi chứng chỉ Tin học |  Tư tưởng Hồ Chí Minh |  Đề thi chứng chỉ Tiếng anh
Theo dõi chúng tôi
Đồng bộ tài khoản