Bài giảng: Các hệ cơ sở trí 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. 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...
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: [email protected]
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
