1. Trang Chủ
  2. Kỹ thuật lập trình
  3. Bài giảng Biểu diễn tri thức

Bài giảng Biểu diễn tri thức

Bài giảng Biểu diễn tri thức nhằm trình bày các nội dung chính: khái niệm biểu diễn tri thức, biểu diễn tri thức bằng Logic hình thức, biểu diễn tri thức bằng mạng ngữ nghĩa, biểu diễn tri thức bằng hệ luật dẫn. Bài giảng được trình bày khoa học, súc tích giúp các bạn sinh viên tiếp thu bài Biểu diễn tri thức và ứng dụng. • Khái niệm • BDTT bằng Logic hình thức • BDTT bằng mạng ngữ nghĩa • BDTT bằng hệ luật dẫn Phạm Thi Vương Biểu diễn tri thức và ứng dụng 30/10/07 2 • Tri thức (knowledge) ? • K

Thể loại Tài liệu miễn phí Kỹ thuật lập trình

Số trang 28

Ngày tạo 8/30/2018 4:28:10 AM +00:00

Loại tệp PDF

Kích thước 0.60 M

Tên tệp

Tải Bài giảng Biểu diễn tri thức (.pdf)

Xem mẫu

  1. • Khái niệm • BDTT bằng Logic hình thức • BDTT bằng mạng ngữ nghĩa • BDTT bằng hệ luật dẫn Phạm Thi Vương Biểu diễn tri thức và ứng dụng 30/10/07 2 • Tri thức (knowledge) ? • Khái niệm – Khái niệm: điểm, tam giác… • Knowledge: the psychological result of perception and learning and reasoning (English – English • Các sự kiện, các nguyên lý, định lý, định Dictionary) luật, quan hệ giữa các khái niệm = luật • Tri thức là kết quả của q trình nhận thức, học tập q quá ậ , ọ ập – 2 tam giác có 3 cạnh bằng nhau thì bằng và lập luận nhau • Kinh nghiệm • Sự hiểu biết của con người trong một phạm vi, 1 lĩnh vực nào hay 1 vấn đề nào đó. Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 3 30/10/07 4
  2. • Tập hợp các tri thức liên quan đến vấn đề • tìm ra các kỹ thuật, các phương pháp thể mà chương trình quan tâm giải quyết. hiện, diễn đạt tri thức nhằm tổ chức được cơ sở tri thức trên máy tính và thực hiện các xử lý tri thức, vận dụng tri thức giải quyết vấn đề. • BDTT: biểu diễn các loại tri thức của con người bằng các cấu trúc dữ liệu mà máy g g ệ y tính có thể xử lý được Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 5 30/10/07 6 1. Representational adequacy: Khả năng biểu diễn tất cả các tri thức cần thiết Dạng thực Dạng hình thức cho lĩnh vực đó. - Facts (sự kiện): - Representations (sự biểu diễn): 2. 2 Inferential adequacy: sự thật trong lĩnh vực dạng biểu diễn của sự kiện theo lược Khả năng xử lý các cấu trúc sẵn có để sinh ra các đồ được chọn. ợ ọ cấu trúc mới tương ứng với tri thức mới được sinh ra từ tri thức cũ. Cái cần biểu diễn Cái có thể xử lý được Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 7 30/10/07 8
  3. 3. Inferential efficiency: Khả năng thêm vào cấu trúc tri thức thông tin bổ sung mà nó có thể được dùng để hướng dẫn cơ – Không một hệ thống nào có thể tối ưu tất cả chế suy luận theo hướng có nhiều triển vọng các khả năng trên cho mọi kiểu tri thức. nhất. nhất 4. Acquisitional efficiency: – Nhiều kỹ thuật dùng cho biểu diễn tri thức Khả năng thu được thông tin mới dễ dàng. dàng cùng tồn tại. ồ Trường hợp đơn giản nhất là chèn trực tiếp tri thức mới (do người) vào cơ sở tri thức. Lý tưởng nhất là chương trình có thể kiể soát việc thu hấ h ì h ó hể kiểm á iệ h – Chương trình thường dùng nhiều hơn 1 kỹ được tri thức. thuật biểu diễn. Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 9 30/10/07 10 • Tri thức thủ tục: mô tả cách thức, các • Tri thức khai báo: cho biết một vấn đề buớc để giải quyết một vấn đề. được thấy như thế nào. Loại tri thức này đưa ra g p p để ạ y giải pháp Loại tri thức này bao gồm các phát biểu thực hiện một công việc nào đó. đơn giản, dưới dạng các khẳng định logic Các dạng tri thức thủ tục tiêu biểu đúng hoặc sai thường là các luật, chiến lược, lịch trình, và thủ tục Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 11 30/10/07 12
  4. • Tri thức heuristic: mô tả các "mẹo" để dẫn • Siêu tri thức: mô tả tri thức về tri thức. dắt tiến trình lập luận. 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 Tri thức heuristic còn được gọi là tri thức quyết một vấn đề. nông cạn do không bảm đảm hoàn toàn chính xác về kết quả giải quyết vấn đề đề. Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 13 30/10/07 14 • Thụ động • Dựa trên logic hình thức: dạng biểu diễn – Gián tiếp: những tri thức kinh điển. tri thức cổ điển nhất trong máy tính, với – Trực tiếp: những tri thức kinh nghiệm ( ự p g g ệ (khôngg hai dạng phổ biến là logic mệnh đề và kinh điển) do “chuyên gia lĩnh vực” đưa ra logic vị từ. Cả hai kỹ thuật này đều dùng • Chủ động ộ g ký hiệu để thể hiện tri thức và các toán tử – Đối với những tri thức tiềm ẩn, không rõ ràng áp lên các ký hiệu để suy luận logic. hệ thống p ệ g phải tự phân tích, suy diễn, khám ựp y phá để có thêm tri thức mới Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 15 30/10/07 16
  5. • Dạng sơ đồ mạng: là phương pháp biểu • Dạng luật dẫn: là cấu trúc tri thức dùng diễn tri thức dùng đồ thị trong đó nút biểu để liên kết thông tin đã biết với các thông diễn đối tượng và cung biểu diễn quan hệ tin khác giúp đưa ra các suy luận, kết luận giữa các đối tượng từ những thông tin đã biết. Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 17 30/10/07 18 • Dạng cấu trúc frames, classes: là cấu • Logic mệnh đề trúc dữ liệu để thể hiện tri thức đa dạng về • Logic vị từ cấp 1, cấp cao khái niệm hay đối tượng nào đó. • Logic đa trị: các mệnh đề không đúng không sai • Sử dụng các ngôn ngữ đặc tả • Logic mờ • Logic L i thời giani Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 19 30/10/07 20
  6. • Các ký hiệu đại diện cho các mệnh đề có • Mệnh đề là một khẳng định, một phát biểu chân trị đúng hoặc sai: p,q,r,...(có thể phụ mà giá trị của nó chỉ có thể hoặc là đúng thuộc vào không gian, thời gian, chủ thể hoặc là sai (có thể phụ thuộc vào không phát biểu, hoặc luôn có chân trị xác định. gian, thời gian, chủ thể phát biểu, hoặc • Các toán tử logic not(¬), and(∧), or(∨), g ( ), ( ), ( ), luôn có chân trị xác định). • Quy ước ngữ nghĩa: hằng đúng, hằng sai • Các tiên đề các quy luật đề, Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 21 30/10/07 22 • Các ký hiệu đại diện cho các mệnh đề có • Biểu thức logic được định nghĩa đệ quy chân trị đúng hoặc sai: p,q,r. như sau: • Các toán tử logic not(¬), and(∧), or(∨), g ( ), ( ), ( ), – Các hằng logic ( g g (True, False) và các biến ) mệnh đề là các biểu thức logic • Quy ước ngữ nghĩa: hằng đúng, hằng sai – Các biểu thức logic kết hợp với các toán tử • Các tiên đề các quy luật đề, logic (phép tuyển (∨), phép hội (∧ ), phủ định ể (¬ , ~, ), phép kéo theo (⇒, →), phép tương đương (⇔, ≡)) là các biể thức logic đ ( )) á biểu thứ l i Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 23 30/10/07 24
  7. • Biểu thức logic dạng chuẩn: là biểu thức – Tập kí hiệu, mỗi kí hiệu đại diện cho môt vấn được xây dựng từ các biến mệnh đề và đề cơ bản trong tri thức: p,q,r... Các mệnh đề ề ề các phép toán ¬, ∧, ∨. phức hợp của các mệnh đề cơ bản được viết dưới dạng các biểu thức logic. logic – Các luật thể hiện những liên hệ trên các mệnh đề và các biểu thức Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 25 30/10/07 26 • Ta có cơ sở tri thức mô tả mối quan hệ của các – Nếu biết 2 cạnh và một góc kẹp giữa 2 cạnh thành phần trong một tam giác như sau: nh sa đó của một tam giác thì ta có thể biết được ể ế – Nếu biết 3 cạnh của 1 tam giác ta có thể biết nữa chu diện tích của tam giác đó vi của tam giác đó g – Nếu biết 2 cạnh và nữa chu vi của một tam giác thì ta – Nế biết ba cạnh và nữa chu vi của một t Nếu b h à ữ h i ủ ột tam có thể biết được cạnh còn lại của tam giác đó giác thì ta biết được diện tích của tam giác đó – Nếu biết được diện tích và một cạnh của một tam – Nế biết diện tí h và đ ờ cao của một tam Nếu diệ tích à đường ủ ột t giác thì ta có thể biết được chiều cao tương ứng với cạnh đó giác thì ta biết được cạnh tương ứng với – Nế biết 2 cạnh và một góc kẹp giữa 2 cạnh đó của Nếu h à ột ó k iữ h ủ đường cao của tam giác đó một tam giác thì ta có thể biết được cạnh còn lại của tam giác đó. Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 27 30/10/07 28
  8. Thuật giải Vương Hạo B1 : Ph ùt bi åu l i giaûû thieáát vaøø k át l än cuûûa vaáán ñ à theo Phaù bieå laï i hi keá luaä ñeà h daïng chuaån sau : • Vấn đề: chứng minh tính đúng đắn của GT1, GT2, ..., GTn → KL1, KL2, ..., KLm suy diễn a b Trong ñoù caùc GTi vaø KLi laø caùc meänh ñeà ñöôïc xaây • Giải quyết: q y döïng tö cac bien döng töø caùc bieán meänh ñeà vaø 3 pheùp noái cô baûn : ∧ ∨ ñe va phep noi ban ∧, ∨, sử dụng các phép suy luận và biến đổi ¬ g logic khó cài đặt ặ B2 : Chuyeån veá caùc GTi vaø KLi coù dang phuû ñònh. Chuyen ve cac va co daïng phu Sử dụng bảng chân trị O(2n) Ví duï : 2 phương pháp với độ phức tạp O(n) p ∨ q ¬ (r ∧ s) ¬g, p ∨ r → s ¬p q, s), g s, p ⇒ p ∨ q, p ∨ r, p → (r ∧ s), g, s Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 29 30/10/07 30 Thuật giải Vương Hạo Thuật giải Vương Hạo B3 : Neááu ôûû GTi coùù pheùùp ∧ thì thay theáá pheùùp ∧ b èng d áu “,” h h h h h baè daá Neáu ôû KLi coù pheùp ∨ thì thay theá pheùp ∨ baèng daáu “,” B5 : Moät doøng ñöôïc chöùng minh neáu toàn taïi chung moät meänh ñeà ôû ôû caû hai phía ñe ô ô ca phía. Ví duï : p ∧ q, r ∧ (¬p ∨ s) → ¬q, ¬s Ví duï : p, q → q ñöôïc chöùng minh ⇒ p, q, r, ¬p ∨ s → ¬q, ¬s p, ¬p → q ⇒ p→ p, q B4 : Neáu ôû GTi coù chöùa pheùp ∨ thì taùch thaønh hai doøng con. B6 : a) Neáu moät doøng khoâng coøn pheùp noái ∧ hoaëc ∨ ôû Neu ô Neáu ôû KLi coù chöùa pheùp ∧ thì taùch thaønh hai doøng con. co chöa phep tach thanh dong caûû h i veáá vaøø ôûû 2 veáá kh âng coùù chung moäät bi án meäänh ñ à hai khoâ h bieá ñeà Ví duï : p, ¬p ∨ q → q thì doøng ñoù khoâng ñöôïc chöùng minh. b) Moät vaán ñeà ñöôc chöùng minh neáu taát caû doøng daãn van ñe ñöôïc chöng neu tat ca dong dan xuaát töø daïng chuaån ban ñaàu ñeàu ñöôïc chöùng minh. p, ¬p → q p, q → q Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 31 30/10/07 32
  9. Thuật giải Vương Hạo Xét các câu đúng sau: r ¬p r, p ∨ s → ¬q, ¬r ∧ s q r • “Nếu trời mưa thì Lan mang theo dù” a ∧ b → c và b ∧ c → d và a và b, suy ra d • “Nếu Lan mang theo dù thì Lan không bị ướt” • “Nếu trời không mưa thì Lan không bị ướt” • Xây dựng các câu trên bằng các biểu thức y g g logic mệnh đề Hãy chứng minh rằng “Lan không bị ướt” bằng phương pháp Vương Hạo Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 33 30/10/07 34 • Cho các biểu thức logic mệnh đề đúng • Thuaät giaûi naøy hoaït ñoäng döïa treân phöông sau phaùp chöùng minh phaûn chöùng. a→f • Chöùng minh pheùp suy luaään (a → b) laø ñuùng C p y ( ) a → (f → p) (vôùi a laø giaû thieát, b laø keát luaän). p^q→d • Phaûn chöng : gia söû b sai suy ra ¬b laø ñuùng Phan chöùng giaû sö la ñung. a • Baøi toaùn ñöôïc chöùng minh neáu a ñuùng vaø ¬b a ^ d →g ñung i h ñ ù sinh ra moäät mau th ã â thuan. • Hãy dùng phương pháp Vương Hạo để chứng minh hoặc bác bỏ g≡1 g 1 Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 35 30/10/07 36
  10. • B1 : Phaùt bieåu laïi giaû thieát vaø keát luaän cuûa vaán ñeà döôùi daïng • B4 : Neáu trong danh saùch meänh ñeà ôû böôùc 3 coù 2 chuaån nhö sau : meänh ñeà ñoái ngaãu nhau thì baøi toaùn ñöôïc chöùng GT1, GT2, GTn GT1 GT2 ...,GTn → KL1 KL2 .., KLm KL1, KL2, minh. Ngöôïc laïi thì chuyeåån sang B5. ( vaøø ¬a goïi laøø i h N l hì h B5 (a l Trong ñoù : GTi vaø KLj ñöôïc xaây döïng töø caùc bieán meänh hai meänh ñeà ñoái ngaãu nhau) ñeà vaø caùc pheùp toaùn : ∧, ∨, ¬ • B5 : Xay döïng moät meänh ñeà môùi bang caùch tuyen Xaây döng ñe môi baèng cach tuyeån moät caëp meänh ñeà trong danh saùch meänh ñeà ôû böôùc • B2 : Neáu ôû GTi coù pheùp ∧ thì thay theá pheùp ∧ baèng daáu “,” 3. Neáu meänh ñeà môùi coù caùc bieán meänh ñeà ñoái ngaãu Neu ôû Neáu ô KLi coù pheùp ∨ thì thay the pheùp ∨ baèng daáu “,” co phep theá phep bang dau nhau thì caùc bieáán ñoù ñöôïc loaïi boû. Ví duï : p ∨ ¬q ∨ ¬r ∨ s ∨ q • B3 : Bieán ñoåi doøng chuaån ôû B1 veà thaønh danh saùch meänh ñeà nhö sau : Hai H i meäänh ñ à ¬q, q l ø ñoáái ngaããu neâân seõõ ñöôïc loaïi boûû ñeà laø ñ ñ l b { GT1, GT2, ..., GTn , ¬ KL1, ¬ KL2, ..., ¬ KLm } ⇒ p ∨ ¬r ∨ s Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 37 30/10/07 38 • B6 : Thay theá hai meänh ñeà vöøa tuyeån trong danh • Chöùng minh raèng saùùch meäänh ñ à b èng meäänh ñ à môùi. ñeà baè ñeà ôù Ví duï : • ¬p ∨ q, ¬q ∨ r, ¬r ∨ s, ¬u ∨ ¬s → ¬p, ¬u { p ∨ ¬q , ¬r ∨ s ∨ q , q r w∨r r, s ∨ q } ⇒ { p ∨ ¬r ∨ s , w ∨ r, s ∨ q } • B7 : Neáu khoâng xaây döïng ñöôïc theâm moät meänh ñeà môùi naøo vaø trong danh saùch meäänh ñeà khoâng coù 2 g meänh ñeà naøo ñoái ngaãu nhau thì vaán ñeà khoâng ñöôïc chöùng minh. Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 39 30/10/07 40
  11. • B3: { ¬p ∨ q, ¬q ∨ r, ¬r ∨ s, ¬u ∨ ¬s, p, u } • Tuyeån hai caëp meänh ñeà ñaàu tieân: ¬p ∨ r ∨ ¬r ∨ s ⇒ ¬p ∨ s Danh D h saùùch meäänh ñ à th ønh {¬p ∨ s, ¬u ∨ ¬s, p, u } ñeà thaø { • B4 : Coù taát caû 6 meänh ñeà nhöng chöa coù meänh ñeà Vaãn chöa coù hai meänh ñeà ñoái ngaãu naøo ñoái ngaãu nhau. • B5 : ⇒ tuyeån moät caëp meänh ñeà (choïn hai meänh ñeà • Tuyeån hai caëp meänh ñeà ñaàu tieân: ¬p ∨ s ∨ ¬u ∨ ¬s ⇒ ¬p ∨ ¬u coù bieán ñoái ngaãu). Choïn hai meänh ñeà ñaàu : Danh saùch meänh ñeà thaønh : {¬p ∨ ¬u, p, u } ¬p ∨ q ∨ ¬q ∨ r ⇒ ¬p ∨ r Vaããn chöa coù hai meänh ñeàà ñoáái ngaããu • Tuyeån hai caëp meänh ñeà : ¬p ∨ ¬u ∨ u ⇒ ¬p Danh saùch meänh ñeà thaønh : {¬p ∨ r , ¬r ∨ s, ¬u ∨ Danh sach meänh ñeà trôû thaønh : {¬p, p } saùch ñe trô thanh {¬p ¬s, p, u } Coù hai meänh ñeà ñoái ngaãu neân bieåu thöùc ban ñaàu ñaõ ñöôïc Vaãn chöa coù meänh ñeà ñoái ngaãu. chöùng minh. Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 41 30/10/07 42 • Logic mệnh đề: không thể can thiệp vào • Vị từ là một phát biểu đề cập tới các phần cấu trúc của một mệnh đề. Hay nói một tử thuộc những phạm vi nhất định và chân cách khác là mệnh đề không có cấu trúc. trị phụ thuộc các phần tử này. • Khi các phần tử xác định rõ thì phát biểu trở thành mệnh đề. ệ • Ví dụ: “n là 1 số nguyên tố” n tố “m là ước số của n” Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 43 30/10/07 44
  12. • Về mặt toán học vị từ là hàm lấy giá trị logic phụ thuộc • Liên quan đến vị từ ta cũng có các phép bao gồm tên và biến. ồ ế toán vị từ: ¬, ∧, ∨, →, ↔. • Kí hiệu: hàm bao gồm tên và biến • Khi thực hiện các phép toán trên vị từ ta ự ệ p p ị – p(n)= “n là 1 số nguyên tố” ố ố được vị từ mới – us(m,n)=“m là ước số của n” – Vi(Cam, ngọt)=”Vị Vi(Cam ngọt) ”Vị cam là ngọt” • Các lượng từ: ∃ ∀ ∃! ∃, ∀, – Mau(Cam, xanh)=”Cam co mau xanh” Vitu(, , ,...); Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 45 30/10/07 46 • Các phát biểu có lượng từ (các phát biểu lượng Tri thức biễu diễn theo logic vị từ gồm 2 từ hóa) là phát biểu có lượng từ và có các vị từ theo các biến thành phần: Vd: ∃x,p(x) – Tập các vị từ, trong đó mỗi vị từ đại diện g ∀x, p(x) cho một phát biểu Vd: bất kỳ số nào cũng có số nguyên tố lớn hơn – Tập các sự kiện và luật dưới dạng các biểu nó – p(y) = “y là số nguyên tố” thức logic vị từ – ∀x∈N, ∃y∈N, p(y) ∧ (y>x) Hoặc có thể viết ể ế - ∀x, ∃y, p(y) ∧ (y>x) Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 47 30/10/07 48
  13. • Để biểu diễn tri thức theo logic vị từ ta • Vd: “A là bố của B nếu B là anh hoặc là em thực hiện 2 giai đoạn sau: một người con của A ” ộ ời ủ – Gđ1: Xác lập các vị từ cần thiết cho việc biễu Bo(A,B)= ∃Z: Bo(A,Z) ∧ (Anh(B,Z) ∨ Anh (Z,B)) diễn(mỗi vị từ phải có tên gọi, biến phải có kiểu xác định) a) Bố ("An", "Bình") có giá trị đúng (Anh là bố của Bình) – Gđ2: Viết các sự kiện và luật thành(dưới ế dạng) các công thức logic vị từ b) Anh("Tú", "Bình") có giá trị đúng (Tú là anh của Bình) c) Bố ("An", "Tú") sẽ có giá trị là đúng. (An là bố của Tú). Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 49 30/10/07 50 • Vd: “Không có vật gì lớn nhất và không có • Bất kì số tự nhiên nào cũng là ước số của chính nó vật gì nhỏ nhất” • 1 là ước của mọi số tự nhiên (∀x, ∃y : LớnHơn(y,x) ) ∧ (∀x, ∃y : ( , y (y, ) ( , y • Mọi số tự nhiên đều là ước số của 0 ọ ự LớnHơn(x,y) ) • Với a,b,c tuỳ ý ta có nếu a là ước số của b và b là ước số của c thì à là ước số của c. • USCLN của 1 số a tù ý và 0 là bằ a. ủ ố tùy à bằng USCLN của 0 và 1 số a tùy ý là bằng a. • Với a >b, ta có uscln của a-b và b cũng chính , g là uscln của a và b Với a
  14. • Thuật toán hợp giải • Kiểu biểu diễn tri thức vị từ giống như hàm trong các ngôn ngữ lập trình, đối tượng tri thức là tham số • Ngôn ngữ Prolog của hàm, giá trị mệnh đề chính là kết quả của hàm (kiểu Boolean) Boolean). • Biểu diễn tri thức bằng mệnh đề gặp khó khăn là không thể can thiệp vào cấu trúc của một mệnh đề → g ệp ộ ệ đưa ra khái niệm lượng từ, vị từ. • Với vị từ có thể biểu diễn tri thức dưới dạng các mệnh đề tổng quát tổng quát. Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 53 30/10/07 54 Mạng ngữ nghĩa là 1 mô hình biểu diễn tri thức có dạng đồ thị trong đó: – Mỗi đỉnh(nút) của sơ đồ thể hiện một yếu tố nào đó của tri thức. – Mỗi cung thể hiện một sự liên hệ nào đó giữa g ệ ộ ự ệ g các yếu tố của tri thức Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 55 30/10/07 56
  15. giöõa caùùc khaùùi nieääm chích choøøe, chim, h ùt, caùùnh, t å coùù iöõ kh i hí h h hi hoù h toå moät soá moái quan heä nhö sau : Chích choøe la moät loai chim choe laø loaøi chim. cánh có Chim bieát hoùt Chích Hoùt laø bieát Sẽ là Chim Chim Chi coùù caùùnh choe choøe di chuyển Chim soáng trong toå Chim coù bay b laø Caùnh Toå m Một số tri thức về loài “chim sẽ” được biểu diễn trên Caùc moái quan heä naøy seõ ñöôïc bieåu dieãn tröïc quan mạng ngữ nghĩa baèng moät ñoà thò beân treân Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 57 30/10/07 58 • Ví dụ 2: Bài toán tam giác tổng quát • Một số bài toán thông thường về tam giác như: “Cho 3 Cho Vấn đề: cạnh của một tam giác, tính chiều dài các đường cao”, Trên mạng ngữ nghĩa có một số đỉnh “cho góc a, b và cạnh AC, tính chiều dài các đường trung tuyến”, … g y , được cho trước trước. • Tồn tại hay không một chương trình tổng quát có thể giải được tất cả những bài toán tam giác dạng này ? Câu trả Ta muốn đạt đến 1(nhiều) đỉnh mục tiêu. lời là có. • Bài toán sẽ giải bằng mạng ngữ nghĩa: • Có 22 yếu tố liên quan đến cạnh và góc của tam giác. Để xác định hay để xây dựng một tam giác ta cần 3 yếu Đỉnh kích hoạt: đỉnh đã biết tố trong đó có yếu tố cạnh • Sử dụng khoảng 200 đỉnh để chứa công thức + 22 đỉnh để chứa các yếu tố của tam giác. y g Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 59 30/10/07 60
  16. Bước1: Kích hoạt các đỉnh được cho trước • Mạng ngữ nghĩa cho bài toán có cấu trúc như sau • Đỉ h của đồ thị bao gồm 2 l i Đỉnh ủ b ồ loại: Bước 2: while (chưa đạt tới mục tiêu) • Đỉnh chứa công thức (ký hiệu bằng hình chữ nhật) { • Đỉnh chứa yếu tố tam giác ( ý hiệu bằng hình tròn) y g (ký ệ g ) 2.1 Tìm đỉnh để có thể truyền kích hoạt • Cung: chỉ nối từ đỉnh hình tròn đến đỉnh hình chữ nhật cho biết yếu tố tam giác xuất hiện trong công thức nào tới 2.2 if(tìm không được) KL: không tìm • Lưu ý: Trong một công thức liên hệ giữa n yếu tố của thấy mục tiêu y tam giác, ta giả định rằng nếu đã biết giá trị của n-1 yếu tố thì sẽ tính được giá trị của yếu tố còn lại ố ủ ế ố 2.3 else kích hoạt đỉnh mới } Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 61 30/10/07 62 • Ví dụ: Cho hai góc A, B và chiều dài cạnh f1 : A + B + C − π = 0 a của tam giác. Tính chiều dài đường cao a b hc . Với mạng ngữ nghĩa đã cho trong hình f2 : = sin( A) sin( B) trên. Các bước thi hành của thuật toán c b như sau: f3 : = sin(C ) sin( B ) i ( i ( f4 : S = p( p − a)( p − b)( p − c) hc c f5 : S − 2 Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 63 30/10/07 64
  17. A+ B + C - π = 0 (4) • Thuật giải lan truyền kích hoạt A B C • B1 Kích hoạt những đỉnh hình tròn đã cho ban B1: đầu (những yếu tố đã có giá trị) a b c b • B2: Lặp lại bước sau cho đến khi kích hoạt ặp ạ ạ (1) sin A = sin B sin C = sin B (2) được tất cả những đỉnh ứng với những yếu tố cần tính hoặc không thể kích hoạt được bất kỳ đỉnh nào nữa a b hc c • Nếu một đỉnh hình chữ nhật có cung nối với n đỉnh hình tròn mà n-1 đỉnh hình tròn đã được kích hoạt thì kích hoạt đỉnh hình tròn còn lại (và (3) S= p (p - a )(p - b )(p - c ) S – ½ hc.c = 0 (5) tính giá trị đỉnh còn lại này thông qua công thức ở đỉnh hình chữ nhật). S Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 65 30/10/07 66 • Kích hoạt: • Quy tắc lan truyền Yếu tố: đã biết do giả thiết hay do tính từ Đối với công thức: công thức được công thức g áp dụng khi trong số các yếu tố liên hệ với p ụ g g y ệ Công thức: Công thức áp dụng được để công thức có đúng một yếu tố chưa biết. tạo yếu tố mới Đối với yếu tố: kích hoạt được khi có một công thức được kích hoạt quan hệ với yếu tố đó Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 67 30/10/07 68
  18. A+ B + C - π = 0 (4) A+ B + C - π = 0 (4) A B C A B C a b c b a b c b (1) = = (2) (1) = = (2) sin A sin B sin C sin B sin A sin B sin C sin B a b hc c a b hc c (3) S= p (p - a )(p - b )(p - c ) S – ½ hc.c = 0 (5) (3) S= p (p - a )(p - b )(p - c ) S – ½ hc.c = 0 (5) S S Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 69 30/10/07 70 A+ B + C - π = 0 (4) A+ B + C - π = 0 (4) A B C A B C a b c b a b c b (1) = = (2) (1) = = (2) sin A sin B sin C sin B sin A sin B sin C sin B a b hc c a b hc c (3) S= p (p - a )(p - b )(p - c ) S – ½ hc.c = 0 (5) (3) S= p (p - a )(p - b )(p - c ) S – ½ hc.c = 0 (5) S S Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 71 30/10/07 72
  19. A+ B + C - π = 0 (4) • Giả thiết: a=5, b=4, A=Pi/2 A B C • Mục tiêu: S (1) a b c b • Kết quả: S=6 sin A = sin B = (2) sin C sin B a b hc c (3) S= p (p - a )(p - b )(p - c ) S – ½ hc.c = 0 (5) S Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 73 30/10/07 74 • Biễn diễn đồ thị dưới dạng ma trận • E = tập các yếu tố liệt kê theo thứ tự • Biễn diễn đồ thị dưới dạng danh sách = {a,b,c,A,B,C,S,R,p....} • F = tập các công thức ⎧ a b ⎫ = ⎨ f : A + B + C = π ; f : sin( A) = sin( B) ...⎬ ⎩ 1 2 ⎭ Giả sử có m công thứ n yếu tố ử ó ô thức, ế r là ma trận cấp mxn ⎧1 neáu fi coù quan heä vôùi yeáu toá j R[i ][ j ] = ⎨ ⎩0 Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 75 30/10/07 76
  20. Öu ñi Ö ñieååm Maïng ngöõ nghóa raát linh ñoäng, ta coù theå deã daøng them vao mang caùc theâm vaøo maïng cac ñænh hoaëc cung môi ñe boå sung môùi ñeå bo caùc tri thöùc caàn thieát. Maïng ngö Mang ngöõ nghóa co tính tröc quan cao neân raát deã coù tröïc nen rat de 2 U U hieåu. R= P= P= I2R P=UI I R Maïng ngö Mang ngöõ nghóa cho phep cac ñænh coù theå thöøa ke pheùp caùc co the thöa keá caùc tính chaát töø caùc ñænh khaùc thoâng qua caùc cung loaïi “laø”, töø ñoù, coù theå taïo ra caùc lieân keát “ngaàm” giöõa nhöng nhöõng ñænh khong coù lieân ket tröïc tiep vôi nhau khoâng co lien keát tröc tieáp vôùi nhau. Maïng ngöõ nghóa hoaït ñoäng khaù töï nhieân theo caùch thöc thöùc con ngöôi ghi nhaän thong tin ngöôøi thoâng tin. Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 77 30/10/07 78 Nhược điểm: Cho ñeán nay, vaãn chöa coù moät chuaån naøo quy ñònh caùc giôùi haïn cho caùc ñænh vaø cung cuûa maïng Nghóa laø g g g. g baïn coù theå gaùn gheùp baát kyø khaùi nieäm naøo cho ñænh hoaëc cung! Tính thöøa keá (voán laø moät öu ñieåm) treân mang seõ coù thöa ke (von la ñiem) tren maïng se co theå daãn ñeán nguy cô maâu thuaãn trong tri thöùc. Gaø Hoùt laø bieát laø Chích choøe Chim coù lam laøm Can C ù Toåå h Biểu diễn tri thức và ứng dụng Biểu diễn tri thức và ứng dụng 30/10/07 79 30/10/07 80
nguon tai.lieu . vn
Tin học văn phòng Đồ họa - Thiết kế - Flash Quản trị Web Cơ sở dữ liệu Quản trị mạng Kỹ thuật lập trình Hệ điều hành Phần cứng An ninh - Bảo mật Chứng chỉ quốc tế Thủ thuật máy tính Điện - Điện tử Kinh tế học Hoá học Xã hội học Môi trường