Bài giảng Trí tuệ nhân tạo: Chương 4 - PGS.TS. Lê Thanh Hương

4.1. Tri thức là gì?<br /> • Dữ liệu và Tri thức: là những dạng khác nhau<br /> của thông tin nên khó phân biệt rạch ròi<br /> <br /> Chương 4<br /> Tri thức và suy diễn<br /> <br /> Tri thức<br /> <br /> Lê Thanh Hương<br /> Khoa CNTT - ĐHBK HN<br /> <br /> 1<br /> <br /> Dữ liệu<br /> <br /> - ký hiệu tượng trưng<br /> - tản mạn<br /> - cấu trúc phức hợp<br /> <br /> - số<br /> - có cấu trúc<br /> - cấu trúc đơn giản<br /> <br /> - VD: Đông y:<br /> - hâm hấp sốt<br /> - mạch nhanh/chậm<br /> <br /> - VD: Tây y:<br /> - t0 390<br /> - mạch 75<br /> <br /> Lê Thanh Hương – Khoa CNTT - ĐHBKHN<br /> <br /> 2<br /> <br /> Phân loại tri thức<br /> <br /> Phân loại tri thức<br /> <br /> b. Tri thức thủ tục: how?<br /> <br /> a Tri thức mô tả: what?<br /> a.<br /> <br /> – Modus Ponens<br /> – Modus Tollens<br /> Tri thức cũ về tình huống --------→ Tri thức mới về t/huống<br /> <br /> – về tình huống (GT + KL): sự kiện<br /> – về lĩnh vực: luật nếu … thì<br /> <br /> Hiểu biết về lĩnh vực<br /> Modus Ponens<br /> Modus Tollens<br /> A, A →B<br /> A →B, ¬B<br /> B<br /> ¬A<br /> • Ví dụ: Trán rộng →Thông minh<br /> Bình: trán rộng ⇒ Bình thông minh<br /> Lê Thanh Hương – Khoa CNTT - ĐHBKHN<br /> <br /> 3<br /> <br /> Lê Thanh Hương – Khoa CNTT - ĐHBKHN<br /> <br /> 4<br /> <br /> 1<br /> <br /> Ví dụ 1: Chứng minh bài toán hình học<br /> <br /> Phân loại tri thức<br /> <br /> GT, KL, hình vẽ + Định lý, tính chất<br /> • Mô tả?<br /> Áp dụng định lý đường trung bình vào tam giác ABC ta có<br /> • Thủ tục?<br /> • Điều khiển? Nghĩ → SD tiến, lùi; Viết → SD tiến<br /> <br /> c Tri thức điều khiển: heuristic<br /> c.<br /> <br /> X<br /> <br /> – Chọn hướng suy diễn: tiến, lùi, hỗn hợp<br /> – Chọn luật áp dụng: đảm bảo đủ, không<br /> thừa, có cấu trúc, ngắn gọn<br /> – Vẽ hình phụ<br /> <br /> Cho X = 600, Y = 600. CM XY = XZ, XY = YZ<br /> Mô tả:<br /> • Sự kiện: Bnhau(XY,UV) Bang(X,Y) Banggoc(X,a)<br /> • Luật:<br /> 60<br /> Bnhau(XY,UV) ⇒ bnhau(UV,XY)<br /> Y<br /> Bnhau(XY,UV) ⇒ bnhau(XY,VU)<br /> Bang(Y,Z) ⇒ bnhau(XY,XZ)<br /> Bnhau(XY,UV) ∧ bnhau(UV,ST) ⇒ bnhau(XY,ST)<br /> ???<br /> Ban đầu: banggoc(X,60), banggoc(Y,60)<br /> Đích: bnhau(XY,XZ), bnhau(XY,YZ)<br /> –<br /> –<br /> –<br /> –<br /> –<br /> <br /> •<br /> •<br /> Lê Thanh Hương – Khoa CNTT - ĐHBKHN<br /> <br /> 60<br /> <br /> 5<br /> <br /> Lê Thanh Hương – Khoa CNTT - ĐHBKHN<br /> <br /> Z<br /> <br /> 6<br /> <br /> Tom và Harry<br /> <br /> Ví dụ 2<br /> Tri thức mô tả:<br /> <br /> • Giả thiết dưới dạng phép And<br /> <br /> • H<br /> Harry là 1 con thỏ<br /> H (H<br /> Hare(Harry)<br /> )<br /> • Tom là 1 con rùa<br /> Tortoise(Tom)<br /> • Thỏ chạy nhanh hơn rùa<br /> <br /> Harry ( Hare) ∧ Tortoise (Tom)<br /> • Luật<br /> <br /> Hare( Harry ) ∧ Tortoise(Tom) → Outruns( Harry, Tom)<br /> <br /> ∀x, yHare( x) ∧ Tortoise( y ) → Outruns( x, y )<br /> <br /> • Kết luận<br /> <br /> O t<br /> Outruns<br /> ( Harry<br /> H<br /> , Tom<br /> T )<br /> <br /> • Harry chạy nhanh hơn Tom?<br /> <br /> Tri thức thủ tục?<br /> Tri thức điều khiển?<br /> <br /> Lê Thanh Hương – Khoa CNTT - ĐHBKHN<br /> <br /> 7<br /> <br /> Lê Thanh Hương – Khoa CNTT - ĐHBKHN<br /> <br /> 8<br /> <br /> 2<br /> <br /> Bản chất tri thức chuyên gia<br /> <br /> Biểu diễn tri thức<br /> <br /> Làm sao để chuyển tri thức từ chuyên gia con<br /> người<br /> ời vào<br /> à máy<br /> á Æ kỹ sư xử<br /> ử lý tri<br /> t i thức<br /> thứ<br /> tin học<br /> <br /> ch/gia đầu ngành<br /> lập trình viên<br /> <br /> lĩnh vực<br /> chuyên môn<br /> giỏi<br /> ε2 ∼ 0<br /> <br /> ksư xử lý tri thức<br /> <br /> khá<br /> <br /> khá<br /> <br /> Có nhiều cách biểu diễn tri thức.<br /> GT, KL → sự kiện → mệnh đề, vị từ → đỉnh<br /> R → luật → mệnh đề, vị từ, sản xuất → cung ngữ nghĩa<br /> 1.<br /> 2.<br /> 3<br /> 3.<br /> 4.<br /> 5.<br /> <br /> ε1 ∼ 0<br /> giỏi<br /> <br /> Lê Thanh Hương – Khoa CNTT - ĐHBKHN<br /> <br /> 9<br /> <br /> Lê Thanh Hương – Khoa CNTT - ĐHBKHN<br /> <br /> 10<br /> <br /> Ví dụ<br /> <br /> BDTT = logic<br /> <br /> • Nếu trời đẹp<br /> ẹp thì đi chơi.<br /> p<br /> q<br /> • Nếu đi chơi và có tiền và có thời gian thì đi Hồ Tây.<br /> q<br /> s<br /> t<br /> u<br /> • Nếu đi Hồ Tây và có tiền và có thời gian thì đi Nhật Tân.<br /> u<br /> s<br /> t<br /> v<br /> • Nếu đi Nhật Tân thì mời Lâm<br /> Lâm.<br /> v<br /> w<br /> • Nếu mời Lâm thì mời bạn Lâm.<br /> w<br /> x<br /> <br /> • BDTT = logic mệnh đề<br /> – Tri thức mô tả:<br /> • Các mệnh đề p, q, r, …<br /> • Các luật suy diễn (đưa về dạng chuẩn Horn)<br /> p1 ∧ p2 ∧ … ∧ pn ⇒ q<br /> <br /> – Tri thức thủ tục:<br /> ụ<br /> • modus ponens: {A, A →B} → {A,B}<br /> • modus tollens: {A →B, ¬B} → {¬A, ¬B}<br /> <br /> – Tri thức điều khiển: tiến, lùi<br /> Lê Thanh Hương – Khoa CNTT - ĐHBKHN<br /> <br /> BDTT = logic<br /> BDTT = luật sản xuất<br /> BDTT = mạng ngữ nghĩa<br /> BDTT = frame<br /> BDTT = bộ 3 Object – Attribute - Value<br /> <br /> 11<br /> <br /> Lê Thanh Hương – Khoa CNTT - ĐHBKHN<br /> <br /> 12<br /> <br /> 3<br /> <br /> BDTT = luật sản xuất<br /> <br /> BDTT = mạng ngữ nghĩa<br /> <br /> Các luật sản xuất có dạng:<br /> • Nếu điều kiện 1<br /> .....<br /> và điều kiện m<br /> • thì kết luận 1 và … và kết luận n<br /> <br /> • Mạng ngữ nghĩa là một đồ thị định hướng<br /> G=(N,A), trong đó<br /> <br /> • Trong logic mệnh đề hay vị từ, đk1…đkm, kl1…kln là<br /> những biểu thức logic, còn cặp nếu…thì thì ⇔ dấu →<br /> • Trong nguyên tắc dịch<br /> – one → một<br /> – one → người ta<br /> – one → cái<br /> <br /> – N - tập các đối tượng, các sự kiện hay các khái<br /> niệm cụ thể (đỉnh)<br /> – A - tập các mối liên hệ giữa các cặp đối tượng, sự<br /> kiện hay khái niệm (cung)<br /> – A = {(x,y) | x,y ∈ N} = ∪ {(x,y) | x Ri y}<br /> Ri là 1 quan hệ nào đó trên tập N<br /> <br /> • VD: Giải bài toán lượng giác: cho biết a,b,ma.<br /> Tìm hc<br /> <br /> Lê Thanh Hương – Khoa CNTT - ĐHBKHN<br /> <br /> 13<br /> <br /> BDTT = frame<br /> • Là 1 dẫn xuất của BDTT = mạng ngữ nghĩa, là cơ sở<br /> của phương pháp xử lý thông tin kiểu hướng đối tượng<br /> • Phương pháp BDTT = logic và mạng ngữ nghĩa mang<br /> đặc trưng mô tả<br /> • Phương pháp BDTT = luật sản xuất : thủ tục<br /> • Phương pháp BDTT = frame kết hợp mô tả và thủ tục<br /> <br /> thực thể<br /> <br /> mạng<br /> ngữ nghĩa<br /> đỉnh<br /> <br /> frame (tri thức<br /> hướng đối tượng)<br /> đối tượng (object)<br /> <br /> quan hệ<br /> <br /> cung<br /> <br /> phân cấp (hierachy)<br /> <br /> VD: …<br /> Lê Thanh Hương – Khoa CNTT - ĐHBKHN<br /> <br /> Lê Thanh Hương – Khoa CNTT - ĐHBKHN<br /> <br /> 14<br /> <br /> BDTT = bộ 3<br /> Object – Attribute - Value<br /> • VD:<br /> – (bồ câu, là, chim)<br /> – (bồ câu, biết, ăn)<br /> – (bồ câu, biết, bay)<br /> <br /> ⇔ mạng ngữ nghĩa<br /> <br /> • Hạn chế: chỉ thể hiện được những quan<br /> hệ “=“, khó khăn khi biểu diễn ≥, ≤, …<br /> 15<br /> <br /> Lê Thanh Hương – Khoa CNTT - ĐHBKHN<br /> <br /> 16<br /> <br /> 4<br /> <br /> Các phương pháp chứng minh<br /> <br /> Kỹ thuật CM<br /> <br /> Suy diễn<br /> <br /> • Chứng minh sử dụng phương pháp tìm kiếm<br /> • Hợp giải (kỹ thuật chứng minh)<br /> • Suy diễn<br /> – Sinh các câu mới từ các câu cũ<br /> – Chứng minh = áp dụng các luật suy diễn. Có thể<br /> sử<br /> ử dụng<br /> d<br /> luật<br /> l ật suy diễn<br /> diễ như<br /> h các<br /> á ttoán<br /> á tử trong<br /> t<br /> phương pháp tìm kiếm chuẩn<br /> – Thường đòi hỏi chuyển các câu sang dạng chuẩn<br /> Horn<br /> Lê Thanh Hương – Khoa CNTT - ĐHBKHN<br /> <br /> 17<br /> <br /> Suy diễn<br /> <br /> BT = GT + KL<br /> GT → KL<br /> <br /> CM<br /> GT + ¬KL → ><<br /> <br /> R<br /> GT + R → KL<br /> <br /> Lê Thanh Hương – Khoa CNTT - ĐHBKHN<br /> <br /> 18<br /> <br /> Suy diễn đối với logic mệnh đề<br /> <br /> • Dạng chuẩn Horn<br /> CSTT = tập các câu ở dạng chuẩn Horn<br /> – Câu<br /> Câ H<br /> Horn =<br /> • các ký hiệu mệnh đề<br /> • biểu thức kết hợp các ký hiệu ⇒ ký hiệu<br /> – Ví dụ<br /> C ∧ (B ⇒ A) ∧ (C ∧ D ⇒ B)<br /> <br /> Bài toán: Cho 1 CSTT R={r<br /> R {r1, …, rn},<br /> }<br /> ri là luật, ri có dạng p1∧…∧pm→q<br /> Ngữ nghĩa:<br /> – Nếu p1 đúng và … và pm đúng<br /> – thì q đúng<br /> <br /> • Modus Ponens (cho dạng chuẩn Horn):<br /> α1, … ,αn,<br /> α1 ∧ … ∧ αn ⇒ β<br /> <br /> • Cho biết GT={f<br /> { 1,,…,f<br /> , u}<br /> • Cần CM KL={q1,…,qv} đúng<br /> *<br /> • Ta nói<br /> <br /> β<br /> • Có thể dùng cho suy diễn tiến và suy diễn lùi<br /> • Các thuật toán này có độ phức tạp tuyến tính.<br /> Lê Thanh Hương – Khoa CNTT - ĐHBKHN<br /> <br /> BT = GT + KL<br /> GT → KL<br /> <br /> GT a KL<br /> R<br /> <br /> 19<br /> <br /> Lê Thanh Hương – Khoa CNTT - ĐHBKHN<br /> <br /> 20<br /> <br /> 5<br /> <br />