Bài giảng Trí tuệ nhân tạo - Chương 4: Biểu diễn tri thức - Bùi Đức Dương
Nội dung
1. Giới thiệu
2. Các loại tri thức
3. Các kỹ thuật biểu diễn tri thức
4. Suy diễn dữ liệu
5. Chứng minh mệnh đề
Bạn đang xem trước 20 trang tài liệu Bài giảng Trí tuệ nhân tạo - Chương 4: Biểu diễn tri thức - Bùi Đức Dương, để xem tài liệu hoàn chỉnh bạn click vào nút TẢI VỀ ở trên
nghĩa: đ i tư ng tên là “Nam” có thu c tính là “sinh
viên trư ng ĐHNT”.
3. Các k thu t bi u di n tri th c (tt)
Bi u th c V t : là s k t h p c a các v t b i các phép
toán v t .
Các phép toán:
¬ Ph đ nh m t ngôi.
∀∀∀X V i m i m t ngôi
∃∃∃XT n t i m t ngôi
^ H i hai ngôi.
v Tuy n hai ngôi.
=> Suy ra hai ngôi.
= Tương đương hai ngôi.
3. Các k thu t bi u di n tri th c (tt)
Ví d :
Chuy n các câu sau sang bi u th c v t :
“M i sinh viên trư ng ĐHNT đ u có b ng tú tài.
Lan không có b ng tú tài.
Do v y, Lan không là sinh viên trư ng ĐHNT”
V i sv_NT(X) cho bi t: “X là sinh viên trư ng DHNT”
tu_tai(X) cho bi t: “X có b ng tú tài”
Các câu trên đư c chuy n qua v t là:
∀X(sv_NT(X) => tu_tai(X)).
¬tu_tai(“Lan”).
Do v y, ¬sv_NT(“Lan”).
4. Suy di n d li u
Suy lý
Là quá trình s d ng các s ki n riêng c a bài toán và tri th c t ng
th c a lĩnh v c đ rút ra k t lu n.
Suy lý theo cách suy di n
S d ng s ki n (ti n đ ) và tri th c chung liên quan các d ng
lu t kéo theo.
(A → B) ∧∧∧ (A = True) ⇒ (B = True)
Ví d :
Kéo theo: IF Ph n c ng h ng THEN Máy tính không kh i đ ng
đư c
Ti n đ : Ph n c ng h ng
K t lu n: Máy tính không kh i đ ng đư c
4. Suy di n d li u (tt)
Suy lý quy n p
Rút ra k t lu n (tri th c) t ng quát t m t t p các s ki n.
Ví d :
Ti n đ : Máy tính Dell có CPU
Ti n đ : Máy tính Sony có CPU
K t lu n: Máy tính có CPU
Suy lý gi đ nh
K t lu n có th đúng ho c sai.
Ví d :
Kéo theo: Máy tính không kh i đ ng đư c n u cúp đi n
Ti n đ : Máy tính không kh i đ ng.
K t lu n: Cúp đi n?
4. Suy di n d li u (tt)
Suy lý tương t , lo i suy
V ch ra đi m tương t gi a 2 v t so sánh, rút ra đi m gi ng và
khác nhau.
Ví d :
Khung: Con h
Ch ng lo i: Thú v t
Ăn: Th t
S ng t i: n Đ và Đông Nam Á
Màu: Vàng có v ch
4. Suy di n d li u (tt)
Suy lý theo l thư ng
S d ng kinh nghi m đ nhanh chóng rút ra k t lu n.
Ví d :
Si t qu t l ng thư ng gây ti ng n.
Suy lý không đơn đi u
Khi có s ki n thay đ i, đưa vào s ki n ph thu c khác đ đưa ra k t
lu n mong mu n.
4. Suy di n d li u (tt)
Suy di n
Là quá trình rút ra thông tin m i t các thông tin cũ
Modus ponens
1. E1
2. E1→ E2
3. E2
Modus tollens
1. ¬ E2
2. E1 → E2
3. ¬ E1
4. Suy di n d li u (tt)
Suy di n ti n
Thêm thông tin vào
b nh làm vi c
Xét lu t đ u tiên Xét lu t ti p theo
True
Gi thi t kh p False
Còn lu t
v i b nh
True False
K t lu n vào
b nh làm vi c D ng suy di n
4. Suy di n d li u (tt)
Suy di n ti n v i logic m nh đ
Input: T p lu t Rule= {r 1, r 2, ..., r m}; GT; KL.
Output: Return “True” n u GT→KL
Ngư c l i, return “False”.
Method:
TĐ=GT;
T= Filter(Rule, TĐ);
while (KL ⊄ TĐ) and (T ≠ ∅) do
{
r = Get(T);
TĐ=TĐ ∪{q}; // r: left→q
Rule = Rule \ {r};
T= Filter(Rule, TĐ);
}
if (KL ⊂ TĐ) then return “True”
else return “False”
4. Suy di n d li u (tt)
Suy di n lùi
Th t c b t đ u tìm ki m t d li u đích c a bài toán.
Ch n t t c các lu t ng v i v k t lu n h p v i d li u đích,
thi t l p d li u v đi u ki n phát sinh ra đích làm d li u đích
m i.
T i m i đi m d li u đích m i, ch n t t c các lu t ng v i v k t
lu n h p v i đích m i, thi t l p d li u đi u ki n làm d li u
đích m i hơn.
Th t c này l p l i cho t t c các đích m i cho đ n khi nào d
li u ban đ u c a bài toán đư c tìm th y.
4. Suy di n d li u (tt)
Thêm thông tin vào
b nh làm vi c
Ki m tra b nh làm
Tìm đích m i
vi c Tìm đích m i
True
False
True
Đích kh p v i Còn lu t Quay lui
gi thi t
False
True False
D ng
K t lu n vào đích
4. Suy di n d li u (tt)
Suy di n lùi v i logic m nh đ
Input: T p lu t Rule= {r 1, r 2, ..., r m}; GT; KL.
Output: Return “True” n u GT→KL
Ngư c l i, return “False”.
Method:
If (KL ⊆ GT) then return “True”
Else
{
TĐ=∅; V t = ∅; First=1; QuayLui= False;
}
For (Each q ∈KL) do TĐ=TĐ ∪∪∪{(q,0)};
Repeat
{
first ++;
(f,i)=Get(TĐ);
4. Suy di n d li u (tt)
If (f ∉GT) then
{
j=TìmLu t(f,i,Rule); // r j: Left j → f
If (Tìm có rj) THEN
{
V t = V t ∪ {(f,j)};
For (Each t ∈ (Left j\GT)) do TĐ = TĐ ∪ {(t,0)};
}
else
{
QuayLui=True;
While ((f ∉KL) and Quaylui) do
{
Repeat
{
(g,k)=Get(V t);
TĐ = TĐ \ Left k;
}
Until (f ∈Left k);
4. Suy di n d li u (tt)
l=Tìmluat(g,k,Rule);
If (Tìm có rl) Then
{
TĐ = TĐ \ Left k;
For (Each t ∈(Left l\GT)) do
TĐ= TĐ ∪{(t,0)};
V t = V t ∪ {(g,l)};
Quaylui = False;
} // end if3
else f=g;
} // end while
} // end if2
} // end if1
Until (TĐ = ∅) or ((f ∈KL) and (First>2));
If (f ∈KL) then Return False
else Return True;
4. Suy di n d li u (tt)
So sánh ưu đi m
Suy di n ti n Suy di n lùi
Làm vi c t t đ i v i bài toán Phù h p v i bài toán đưa ra gi
thu th p thông tin r i tìm ra đi u thuy t r i ki m ch ng gi thuy t đó
c n suy di n. đúng hay không.
Cho kh i lư ng l n các thông T p trung vào đích đã cho. T o ra
tin (m i) t m t s thông tin ban m t lo t câu h i liên quan đ n v n
đ u. đ , hoàn c nh đang xét.
Lý tư ng cho các bài toán l p Ch tìm trên m t không gian con
k ho ch, đi u hành, đi u khi n CSTT liên quan đ n bài toán đang
và di n d ch. xét.
4. Suy di n d li u (tt)
So sánh như c đi m
Suy di n ti n Suy di n lùi
Không c m nh n đư c: Ch Thư ng ph i ti p dòng suy
m t s thông tin là quan tr ng. di n: Không d ng đúng lúc.
H th ng có th h i câu không
liên quan và câu tr l i có th
không quan tr ng.
5. Ch ng minh m nh đ
Thu t gi i Vương H o
Bư c 1: Phát bi u l i gi thi t và k t lu n c a v n đ dư i d ng
chu n như sau:
GT1, GT2, , GTn → KL1, KL2, KLm
Trong đó các GTi và KLj đư c xây d ng t các bi n m nh đ và các phép
toán ∧, ∨, ¬.
Bư c 2: Chuy n v các GTi và KLj có d ng ph đ nh.
Ví d :
(p → q, ¬ (r →s), ¬q, p ∨ r) → (s, ¬p)
≡ (p → q, p ∨ r, p) → (s, r →s, q)
Bư c 3: Thay d u “∧∧∧” trong GTi và d u “∨∨∨” trong KLj b ng d u
“,” (ph y).
Ví d :
p ∧ q, r ∧ (p ∨ s) → q ∨ r
≡ p, q, r, (p ∨ s) → q, r
5. Ch ng minh m nh đ (tt)
Bư c 4: N u GTi còn d u “∨” và KLj còn d u “∧” thì dòng đó đư c tách
thành hai dòng con.
Ví d : p, q, r, (p ∨ s) → q, r
≡ p, q, r, p → q, r và p, q, r, s → q, r
Bư c 5: N u m t dòng đư c ch ng minh: n u t n t i chung m t m nh đ
c 2 v thì coi như đúng.
Ví d : p, q → p: m nh đ đúng
Bư c 6:
+ N u m t dòng không còn d u liên k t tuy n và h i mà c hai v đ u
không có chung bi n m nh đ nào thì dòng đó không đư c ch ng minh.
Ví d : p, ¬q → q
+ M t v n đ đư c gi i quy t m t cách tr n v n n u m i dòng d n xu t t
d ng chu n đư c ch ng minh.
Lưu ý: T bư c 2 đ n bư c 4 không c n làm theo th t .
5. Ch ng minh m nh đ (tt)
Ví d : CMR
p ∨ ¬q , ( ¬s ∨ ¬q) ∧ (r ∨s) , ¬p ∧ u ⇒ r ∨ u
Gi i:
p ∨ ¬q , ( ¬s ∨q) ∧ (r ∨s) , ¬p ∧ u ⇒ r ∨ u
⇔ p ∨ ¬q , ¬s ∨ q, r ∨s , ¬p , u ⇒ r, u
⇔ p ∨ ¬q , ¬s ∨ q, r ∨s , u ⇒ r , u, p
⇔ p ∨ ¬q , ¬s ∨ q, r ∨s , u ⇒ r , u, p
Tách phép ∨: (p ∨ ¬q) thành 2 dòng con
1: p, ¬s ∨ q, r ∨s , u ⇒ r , u, p (đcm vì có m nh đ p
hai phía)
2: ¬q , ¬s ∨ q, r ∨s , u ⇒ r , u, p ⇔ ¬s ∨ q, r ∨s , u ⇒ r , u, p,
q
5. Ch ng minh m nh đ (tt)
2: ¬q , ¬s ∨ q, r ∨s , u ⇒ r , u, p
⇔ ¬s ∨ q, r ∨s , u ⇒ r , u, p, q
Tách phép ∨ : ¬s ∨ q thành 2 dòng con
2.1: q, r ∨s , u ⇒ r , u, p, q (đcm vì có m nh đ q hai phía)
2.2: ¬s , r ∨s , u ⇒ r , u, p, q ⇔ r ∨s , u ⇒ r , u, p, q, s
Tách phép ∨: r ∨ s thành 2 dòng con
2.2.1: s , u ⇒ r , u, p, q, s (đcm vì có s, u c hai phía)
2.2.2: r , u ⇒ r , u, p, q, s (đcm vì có r, u c hai phía)
Các dòng d n xu t t d ng chu n ban đ u đ u đư c ch ng minh,
v y v n đ đư c ch ng minh.
5. Ch ng minh m nh đ (tt)
Thu t gi i Robinson
Thu t gi i Robinson hành đ ng d a trên phương pháp ch ng minh
b ng ph n ch ng.
Bư c 1: Đưa v n đ v d ng chu n như sau:
GT1, GT2, ...,GTn ⇒ KL1, KL2,...,KLm
Trong đó các GTi và KLj đư c xây d ng t các bi n m nh đ và
các phép logic: ∧,∨, ¬.
Bư c 2: N u GTi có phép ∧ thì thay b ng d u",". N u KLj có phép
∨ thì thay b ng d u ",".
Bư c 3: Bi n đ i d ng chu n Bư c 1 v d ng sau:
GT1, GT2, ...,GTn , ¬ KL1, ¬KL2,..., ¬KLm
Bư c 4: N u trong danh sách m nh đ Bư c 3 có m nh đ đ i
ng u (p và ¬p) thì m nh đ đư c ch ng minh. Ngư c l i thì chuy n
sang Bư c 5.
5. Ch ng minh m nh đ (tt)
Bư c 5: Xây d ng m t m nh đ m i b ng cách tuy n m t c p
m nh đ trong danh sách m nh đ . N u m nh đ m i có các bi n
m nh đ đ i ng u thì lo i b các bi n đó.
Bư c 6: Thay th hai m nh đ v a tuy n trong danh sách m nh đ
b ng m nh đ m i, áp d ng phép h p gi i:
i) p ∧ ( ¬p ∨ q) ⇒ q
ii) ( p ∨ q) ∧ ( ¬p ∨ r) ⇒ q ∨ r
Bư c 7: N u không xây d ng đư c thêm m t m nh đ m i nào và
trong danh sách m nh đ không có hai m nh đ nào đ i ng u nhau
thì v n đ không đư c ch ng minh. N u danh sách m nh đ không
còn m nh đ nào (danh sách r ng), v n đ đư c ch ng minh.
5. Ch ng minh m nh đ (tt)
Ví d : CMR
¬p ∨ q , (s ∨ ¬ q) ∧ (r ∨ ¬s) , p ∧ u ⇒ r, u
Gi i:
¬p ∨ q , (s ∨ ¬ q) ∧ (r ∨ ¬s) , p ∧ u ⇒ r, u
¬p ∨ q , s ∨ ¬ q, r ∨ ¬s , p , u ⇒ r, u
¬p ∨ q , s ∨ ¬ q, r ∨ ¬s , p , u, ¬r, ¬ u
(¬p ∨ q , s ∨ ¬ q), r ∨ ¬s , p , u, ¬r, ¬ u
(¬p ∨ s, r ∨ ¬s) , p , u, ¬r, ¬ u
(¬p ∨ r , p) , u, ¬r, ¬ u
(r ∨ ¬r), u, ¬ u
u, ¬ u = Φ
Bài t p Chương
Gi i bài toán tam giác (M ng ng nghĩa)
Cài đ t thu t toán suy di n ti n
Cài đ t thu t toán suy di n lùi
Cài đ t thu t toán Vương H o
Cài đ t thu t toán Robinson
LOGO
Bùi Đ c Dương
Khoa Công ngh Thông tinFile đính kèm:
Microsoft PowerPoint - Chuong4_KnowledgeRepresent.pdf
