›
›

Bài giảng Trí tuệ nhân tạo - Nguyễn Thanh Cẩm

ppt 118 trang phuongnguyen 10
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Trí tuệ nhân tạo - Nguyễn Thanh Cẩm", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptbai_giang_tri_tue_nhan_tao_nguyen_thanh_cam.ppt

Nội dung text: Bài giảng Trí tuệ nhân tạo - Nguyễn Thanh Cẩm

  1. TRƯỜNG CAO ĐẲNG CNTT HỮU NGHỊ ViỆT - HÀN KHOA KHOA HỌC MÁY TÍNH TRÍ TUỆ NHÂN TẠO (Artificial Intelligence - AI) Nguyễn Thanh Cẩm
  2. Contents 1 Tổng quan về khoa học trí tuệ nhân tạo 2 Các phương pháp giải quyết vấn đề cơ bản 3 Tri thức và các phương pháp biểu diễn tri thức 4 Máy học 5 Mạng Nơron 7/13/2021 2
  3. Chương 3 Tri thức và các phương pháp biểu diễn tri thức 3.1 Thông tin, dữ liệu và tri thức 3.2 Thuật toán – một phương pháp biểu diễn tri thức 3.3 Các phương pháp biểu diễn tri thức trên máy tính 7/13/2021 3
  4. 3.1 Thông tin, dữ liệu và tri thức ◆Tri thức là một khái niệm rất trừu tượng. ◼ So sánh khái niệm "tri thức" với hai khái niệm ◼ Thông tin và ◼ Dữ liệu. ◆ Nhà bác học nổi tiếng Karan Sing đã từng nói: "Chúng ta đang ngập chìm trong biển thông tin nhưng lại đang khát tri thức". 7/13/2021 4
  5. 3.1 Thông tin, dữ liệu và tri thức ◆ Dữ liệu là các con số, chữ cái, hình ảnh, âm thanh mà máy tính có thể tiếp nhận và xử lý. ◆ Dữ liệu thường không có ý nghĩa đối với con người. ◆ Thông tin là tất cả những gì mà con người có thể cảm nhận được một cách trực tiếp hoặc gián tiếp ◆ Đối với con người Thông tin luôn có một ý nghĩa nhất định nào đó. 7/13/2021 5
  6. 3.1 Thông tin, dữ liệu và tri thức ◆ Thông tin là quan hệ giữa các dữ liệu. Nếu những quan hệ này được chỉ ra một cách rõ ràng thì đó là các tri thức. Chẳng hạn: ◼ Trong toán học: 1, 1, 3, 5, 2, 7, 11, là các dữ liệu. ◆ Dữ liệu: 1, 1, 2, 3, 5, 8, 13, 21, 34, ◆ Biểu diễn bằng công thức: Un = Un-1 + Un-2. ◆ Công thức nêu trên chính là tri thức. 7/13/2021 6
  7. 3.1 Thông tin, dữ liệu và tri thức ◼Trong vật lý: I U R 5 10 2 2.5 20 8 4 12 3 7.3 14.6 2 Công thức này là tri thức 7/13/2021 7
  8. 3.1 Thông tin, dữ liệu và tri thức ◼ Trong cuộc sống hàng ngày: ◆ Chuồn chuồn bay thấp thì mưa, bay cao thì nắng, bay vừa thì râm. ◆ Lời nhận xét trên là tri thức. ◆ Mọi mối liên hệ giữa các dữ liệu đều có thể được xem là tri thức, bởi vì những mối liên hệ này thực sự tồn tại. 7/13/2021 8
  9. 3.1 Thông tin, dữ liệu và tri thức ◆ Bạn hãy hình dung dữ liệu như là những điểm trên mặt phẳng ◆ Còn tri thức chính là phương trình của đường cong nối tất cả những điểm này lại. 7/13/2021 9
  10. 3.1 Thông tin, dữ liệu và tri thức ◆ Người ta thường phân loại tri thức ra làm các dạng như sau: ◼ Tri thức sự kiện: Chẳng hạn: mặt trời mọc ở phía đông, tam giác đều có 3 góc 600, ◼ Tri thức thủ tục: Thuật toán, thuật giải là một dạng của tri thức thủ tục. ◼ Tri thức mô tả: một cái bàn thường có 4 chân, con người có 2 tay, 2 mắt, ◆ Tri thức Heuristic: là một dạng tri thức cảm tính. có dạng ước lượng, phỏng đoán, và thường được hình thành thông qua kinh nghiệm. 7/13/2021 10
  11. 3.1 Thông tin, dữ liệu và tri thức ◆ Tri thức không quyết định sự thông minh (người biết nhiều định lý toán hơn chưa chắc đã giải toán giỏi hơn!) ◆ Nhưng nó là một yếu tố cơ bản cấu thành trí thông minh. ◆ Muốn xây dựng một trí thông minh nhân tạo, ta cần phải có tri thức. ◆ Vấn đề đầu tiên là: đưa tri thức vào máy tính (được gọi là biểu diễn tri thức). 7/13/2021 11
  12. Tri thức và các phương pháp biểu diễn tri thức 3.1 Thông tin, dữ liệu và tri thức 3.2 Thuật toán – một phương pháp biểu diễn tri thức 3.3 Các phương pháp biểu diễn tri thức trên máy tính 7/13/2021 12
  13. 3.2 Thuật toán – một phương pháp biểu diễn tri thức ◆ Chương trình giải phương trình bậc hai có được xem là một chương trình có tri thức hay không? ◆ Vậy thì tri thức nằm ở đâu? ◆ Tất cả các chương trình máy tính ít nhiều đều đã có tri thức. Đó chính là tri thức của lập trình viên được chuyển thành các câu lệnh của chương trình. ◆ Các tri thức trong những chương trình truyền thống là những tri thức "cứng", 7/13/2021 13
  14. 3.2 Thuật toán – một phương pháp biểu diễn tri thức ◆ Chương trình hỗ trợ ra quyết định (như đầu tư cổ phiếu, đầu tư bất động sản chẳng hạn), ◆ Người dùng muốn đưa vào chương trình những kiến thức của mình thì anh ta phải chọn một trong hai cách là: ◼ (1) tự sửa lại mã chương trình!? ◼ (2) tìm tác giả của chương trình để nhờ người này sửa lại!?. ◆ Cả hai thao tác trên đều không thể chấp nhận được. 7/13/2021 14
  15. 3.2 Thuật toán – một phương pháp biểu diễn tri thức ◆ Cần phải "mềm" hóa các tri thức được biểu diễn trong máy tính. ◆ Mọi chương trình máy tính đều gồm hai thành phần là các mã lệnh và dữ liệu. ◆ Mã lệnh được ví như là phần cứng của chương trình còn dữ liệu được xem là phần mềm. ◆ "mềm" hóa tri thức là tìm các phương pháp để có thể 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 tính có thể xử lý được. ◆ Đây cũng chính là ý nghĩa của thuật ngữ "biểu diễn tri thức". 7/13/2021 15
  16. 3.2 Thuật toán – một phương pháp biểu diễn tri thức ◆ Con người vẫn chưa thể tìm ra một kiểu biểu diễn tổng quát cho mọi loại tri thức! ◆ Hãy xét một số bài toán: ◼ Bài toán 1: Cho hai bình rỗng X và Y có thể tích lần lượt là VX và VY, hãy dùng hai bình này để đong ra z lít nước (z <= min(VX,VY)). ◼ Bài toán 2: Cho biết một số yếu tố của tam giác (như chiều dài cạnh và góc, ). Hãy tính các yếu tố còn lại. ◼ Bài toán 3: Tính diện tích phần giao của các hình hình học cơ bản. 7/13/2021 16
  17. 3.2 Thuật toán – một phương pháp biểu diễn tri thức ◆ Bài toán 1 sẽ được giải quyết bằng cách sử dụng các luật dẫn xuất (luật sinh). ◆ Bài toán 2 sẽ được giải quyết bằng mạng ngữ nghĩa và ◆ Bài toán 3 sẽ giải quyết bằng công cụ frame. 7/13/2021 17
  18. 3.2 Thuật toán – một phương pháp biểu diễn tri thức ◆ Với bài toán 1, như VX = 5, VY = 7 và z = 4, một quy trình đổ nước như: ◼ Múc đầy bình 7 ◼ Trút hết sang bình 5 cho đến khi 5 đầy. ◼ Đổ hết nước trong bình 5 ◼ Đổ hết nước còn lại từ bình 7 sang bình 5 ◼ Múc đầy bình 7 ◼ Trút hết sang bình 5 cho đến khi bình 5 đầy. ◼ Phần còn lại chính là số nước cần đong. 7/13/2021 18
  19. 3.2 Thuật toán – một phương pháp biểu diễn tri thức ◆ Mỗi một trường hợp sẽ có một cách đổ nước hoàn toàn khác nhau. ◆ Nếu có một ai đó yêu cầu bạn đưa ra một cách làm tổng quát thì chính bạn cũng sẽ lúng túng. 7/13/2021 19
  20. 3.2 Thuật toán – một phương pháp biểu diễn tri thức ◆ Sau nhiều lần thí nghiệm, rất có thể bạn sẽ rút ra được một số kinh nghiệm như: ◼ "khi bình 7 đầy nước mà bình 5 chưa đầy thì hãy đổ nó sang bình 5 cho đến khi bình 5 đầy" ◆ Tại sao bạn không thử "truyền" những kinh nghiệm này cho máy tính và để cho máy tính "mày mò" tìm các thao tác cho chúng ta? ◆ Vì máy tính có khả năng "mày mò" hơn hẳn chúng ta! ◆ Những "kinh nghiệm" mà chúng ta cung cấp cho máy tính không giúp tìm được lời giải, chúng ta sẽ thay thế nó bằng những kinh nghiệm khác 7/13/2021 20
  21. 3.2 Thuật toán – một phương pháp biểu diễn tri thức ◆ Chúng ta hãy phát biểu lại bài toán một cách hình thức: ◼ Giả sử rằng VX<VY. ◼ Gọi lượng nước chứa trong bình X là x (0<=x<=VX) ◼ Gọi lượng nước chứa trong bình Y là y (0<=y<=VY) ◼ Điều kiện kết thúc của bài toán sẽ là : ◼ x = z hoặc y = z ◼ Điều kiện đầu của bài toán là : x = 0 và y = 0 7/13/2021 21
  22. 3.2 Thuật toán – một phương pháp biểu diễn tri thức ◆ Quá trình giải được thực hiện bằng cách xét lần lượt các luật (kinh nghiệm ). ◆ Sau khi áp dụng luật, trạng thái của bài toán sẽ thay đổi. ◆ Ba luật được mô tả như sau: ◼ (L1) Nếu bình X đầy thì đổ hết nước trong bình X đi. ◼ (L2) Nếu bình Y rỗng thì đổ đầy nước vào bình Y. ◼ (L3) Nếu bình X không đầy và bình Y không rỗng thì hãy trút nước từ bình Y sang bình X (cho đến khi bình X đầy hoặc bình Y hết nước). 7/13/2021 22
  23. 3.2 Thuật toán – một phương pháp biểu diễn tri thức ◆ Trên thực tế, lúc đầu người ta dùng đến hơn 15 luật (kinh nghiệm) khác nhau. rút gọn còn 3 luật. ◆ Chuyển đổi cách giải thành chương trình như sau: x = 0; y = 0; while ( (x != z) && (y != z) ) { if (x = = Vx) x = 0; if (y = = 0) y = Vy; if (y > 0) { k = min(Vx - x, y); x = x + k; y = y - k; } } 7/13/2021 23
  24. 3.2 Thuật toán – một phương pháp biểu diễn tri thức ◆ Thử "chạy" chương trình trên với số liệu cụ thể: ◼ Vx = 3, Vy = 4 và z = 2 ◼ Ban đầu : x = 0, y = 0 ◼ Luật (L2) -> x = 0, y = 4 ◼ Luật (L3) -> x = 3, y = 1 ◼ Luật (L1) -> x = 0, y = 1 ◼ Luật (L3) -> x = 1, y = 0 ◼ Luật (L2) -> x = 1, y = 4 ◼ Luật (L3) -> x = 3, y = 2 7/13/2021 24
  25. 3.2 Thuật toán – một phương pháp biểu diễn tri thức ◆ Ba luật mà chúng ta đã cài đặt trong chương trình ở trên được gọi là cơ sở tri thức. ◆ Còn cách thức tìm kiếm lời giải bằng cách duyệt tuần tự từng luật và áp dụng nó được gọi là động cơ suy diễn. ◆ Bài toán đong nước chỉ có lời giải khi số nước cần đong là một bội số của ước số chung lớn nhất của thể tích hai bình. ◆ z = n × USCLN(VX, VY) (với n nguyên dương) 7/13/2021 25
  26. 3.2 Thuật toán – một phương pháp biểu diễn tri thức ◆ Cách giải quyết vấn đề theo kiểu này khác so với cách giải bằng thuật toán thông thường ◼ Không đưa ra một trình tự giải quyết vấn đề cụ thể ◼ Chỉ đưa ra các quy tắc chung chung (dưới dạng các luật), ◼ Máy tính sẽ dựa vào đó (áp dụng các luật) để tự xây dựng một quy trình giải quyết vấn đề. hãy quan sát phiên bản kế tiếp của chương trình 7/13/2021 26
  27. 3.2 Thuật toán – một phương pháp biểu diễn tri thức bool DK(int L ) { switch (L) { case 1 : DK = (x = = Vx); case 2 : DK = (y = = 0); case 3 : DK = (y>0); } #define SO_LUAT 3; } { while ((x !=z) && (y !=z)) void ThiHanh(int L) { for (i = 1; i <= SO_LUAT; i++) if (DK(i)) ThiHanh(i); { switch (L){case 1 : x = 0; } case 2: y = Vy; } case 3 : k = min(Vx-x,y); x = x+k; y = y-k; } } 7/13/2021 27
  28. 3.2 Thuật toán – một phương pháp biểu diễn tri thức ◆ Bây giờ giả sử rằng ta đã có các hàm đặc biệt sau: ◆ bool GiaTriBool(String DK); ◆ void ThucHien(String ThaoTac); ◆ Hàm GiaTriBool nhận vào một chuỗi điều kiện, nó sẽ phân tích chuỗi, tính toán rồi trả ra giá trị bool của biểu thức này. ◆ Ví dụ : GiaTriBoolean(‘6<7’) sẽ trả về true. ◆ Hàm ThucHien cũng nhận vào một chuỗi, nó cũng sẽ phân tích chuỗi rồi tiến hành thực hiện những hành động được miêu tả trong chuỗi này. 7/13/2021 28
  29. 3.2 Thuật toán – một phương pháp biểu diễn tri thức #define SO_LUAT 3; struct Luat{ String DK; String ThaoTac; }; CacLuat DSLuat[SO_LUAT]; void KhoiDong() { CacLuat[1].DK = ‘x = = Vx’; CacLuat[2].DK = ‘y = = 0’; CacLuat[3].DK = ‘y>0’; CacLuat[1].ThaoTac = ‘x = 0’; CacLuat[2].ThaoTac = ‘y = Vy’; CacLuat[3].ThaoTac= ‘k = min(Vx-x,y), x = x + k, y = y-k’; } { while ((x != z) && (y != z)) { for (i = 1; i<= SO_LUAT; i++) if GiaTriBoolean(CacLuat[i].DK) ThucHien(CacLuat[i].ThaoTac); } } 7/13/2021 29
  30. 3.2 Thuật toán – một phương pháp biểu diễn tri thức ◆ Khi muốn sửa đổi "tri thức", bạn chỉ cần thay đổi giá trị mảng Luật là xong. ◆ Người dùng vẫn gặp khó khăn khi muốn bổ sung hoặc hiệu chỉnh tri thức. ◆ Họ cần phải nhập các chuỗi đại loại như ‘x = 0’ hoặc ‘k = min(Vx-x,y)’ ◆ Chúng ta cần giảm bớt "khoảng cách" này lại bằng cách đưa ra những chuỗi điều kiện hoặc thao tác có ý nghĩa trực tiếp đối với người dùng. ◆ Chương trình sẽ có sự chuyển đổi các điều kiện và thao tác này sang dạng phù hợp với chương trình. 7/13/2021 30
  31. 3.2 Thuật toán – một phương pháp biểu diễn tri thức Một số trạng thái và thao tác cơ bản. ◆ Trạng thái cơ bản: ◼ Bình X đầy, ◼ Bình X rỗng, ◼ Bình X không rỗng, ◼ Bình X có n lít nước ◆ Thao tác: ◼ Đổ hết nước trong bình, ◼ Đổ đầy nước trong bình, ◼ Đổ nước từ bình A sang bình B cho đến khi B đầy hoặc A rỗng. 7/13/2021 31
  32. 3.2 Thuật toán – một phương pháp biểu diễn tri thức ◆ Lưu ý: không thể có thao tác "Đổ n lít nước từ A sang B" ◆ "Múc đầy X" ◆ "Đổ z lít nước từ X sang Y" ◆ Vì đây là một bài toán đơn giản nên bạn có thể dễ nhận thấy rằng, các trạng thái cơ bản và thao tác chẳng có gì khác so với các điều kiện mà chúng ta đã đưa ra. 7/13/2021 32
  33. 3.2 Thuật toán – một phương pháp biểu diễn tri thức ◆ Chương trình truyền thống được cấu tạo từ hai "chất liệu" cơ bản là: ◼ dữ liệu và ◼ thuật toán ◆ chương trình trí tuệ nhân tạo được cấu tạo từ hai thành phần là: ◼ cơ sở tri thức (knowledge base) và ◼ động cơ suy diễn (inference engine). 7/13/2021 33
  34. 3.2 Thuật toán – một phương pháp biểu diễn tri thức ◆ Cơ sở tri thức: là tập hợp các tri thức liên quan đến vấn đề mà chương trình quan tâm giải quyết. ◆ Động cơ suy diễn: là phương pháp vận dụng tri thức trong cơ sở tri thức để giải quyết vấn đề. 7/13/2021 34
  35. 3.2 Thuật toán – một phương pháp biểu diễn tri thức Chương trình truyền thống và trí tuệ nhân tạo 7/13/2021 35
  36. 3.2 Thuật toán – một phương pháp biểu diễn tri thức ◆ Nhận xét: ◼ Cơ sở tri thức chỉ là một dạng dữ liệu đặc biệt và ◼ Động cơ suy diễn cũng chỉ là một dạng của thuật toán đặc biệt. 7/13/2021 36
  37. 3.2 Thuật toán – một phương pháp biểu diễn tri thức Cấu trúc chương trình trí tuệ nhân tạo 7/13/2021 37
  38. 3.2 Thuật toán – một phương pháp biểu diễn tri thức ◆ bên cạnh vấn đề biểu diễn tri thức, ta còn phải đề ra các phương pháp để ◼ loại bỏ những tri thức trùng lắp, ◼ thừa hoặc mâu thuẫn. 7/13/2021 38
  39. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.1 Logic mệnh đề 3.3.2 Logic vị từ 3.3.3 Một số thuật giải liên quan đến lôgíc mệnh đề 3.3.4 Biểu diễn tri thức sử dụng luật dẫn xuất (luật sinh) 3.3.5 Biểu diễn tri thức nhờ mạng ngữ nghĩa 3.3.6 Biểu diễn tri thức nhờ Frame 7/13/2021 39
  40. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.1. Logic mệnh đề ◆ Là kiểu biểu diễn tri thức đơn giản nhất và gần gũi nhất đối với chúng ta. ◆ Mệnh đề là một khẳng định, một phát biểu mà giá trị của nó chỉ có thể hoặc là đúng hoặc là sai. ◆ Ví dụ: ◼ Phát biểu "1 + 1 = 2" có giá trị đúng. ◼ Phát biểu "Mọi loại cá có thể sống trên bờ" có giá trị sai. 7/13/2021 40
  41. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.1. Logic mệnh đề ◆ Ký hiệu mệnh đề như: A, B, C, ◆ Có 3 phép toán cơ bản là: ◼ phép hội (), ◼ giao() và ◼ phủ định (). ◆ Modus Ponens: Nếu mệnh đề A là đúng và mệnh đề A → B là đúng thì giá trị của B sẽ là đúng. ◆ Modus Tollens: Nếu mệnh đề A → B là đúng và mệnh đề B là sai thì giá trị của A sẽ là sai. 7/13/2021 41
  42. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.1 Logic mệnh đề 3.3.2 Logic vị từ 3.3.3 Một số thuật giải liên quan đến lôgíc mệnh đề 3.3.4 Biểu diễn tri thức sử dụng luật dẫn xuất (luật sinh) 3.3.5 Biểu diễn tri thức nhờ mạng ngữ nghĩa 3.3.6 Biểu diễn tri thức nhờ Frame 7/13/2021 42
  43. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.2. Logic vị từ ◆ Người ta đã đưa vào khái niệm vị từ và lượng từ ( - với mọi,  - tồn tại) để tăng cường tính cấu trúc của một mệnh đề. ◆ Trong logic vị từ, một mệnh đề được cấu tạo bởi hai thành phần là các đối tượng tri thức và mối liên hệ giữa chúng (gọi là vị từ). ◆ Các mệnh đề sẽ được biểu diễn dưới dạng: ◆ Vị từ ( , , , ) 7/13/2021 43
  44. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.2. Logic vị từ ◆ Để biểu diễn vị của các trái cây, các mệnh đề sẽ được viết lại thành: ◼ Cam có vị Ngọt  Vị (Cam, Ngọt) ◼ Cam có màu Xanh  Màu (Cam, Xanh) ◼ 7/13/2021 44
  45. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.2. Logic vị từ ◆ Với vị từ, ta có thể biểu diễn các tri thức dưới dạng các mệnh đề tổng quát. ◆ Chẳng hạn tri thức "A là bố của B nếu B là anh hoặc em của một người con của A" có thể biểu diễn dưới dạng vị từ như sau: ◆ Bố(A, B) = Tồn tại Z sao cho: Bố(A, Z) và (Anh(Z, B) hoặc Anh(B,Z)) ◆ Trong trường hợp này, mệnh đề Bố(A,B) là một mệnh đề tổng quát 7/13/2021 45
  46. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.2. Logic vị từ ◆ Như vậy nếu ta có các mệnh đề cơ sở là: ◼ a) Bố ("An", "Bình") có giá trị đúng (An là bố của Bình) ◼ b) Anh("Tú", "Bình") có giá trị đúng (Tú là anh của Bình) ◼ thì mệnh đề c) Bố ("An", "Tú") sẽ có giá trị là đúng. (An là bố của Tú). 7/13/2021 46
  47. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.2. Logic vị từ ◆ Câu cách ngôn "Không có vật gì là lớn nhất và không có vật gì là bé nhất!" có thể được biểu diễn dưới dạng vị từ như sau : ◼ LớnHơn(x,y) = x>y ◼ NhỏHơn(x,y) = x<y ◼ x, y: LớnHơn(y,x) và x, y : NhỏHơn(y,x) ◆ Câu châm ngôn "Gần mực thì đen, gần đèn thì sáng" được hiểu là "chơi với bạn xấu nào thì ta cũng sẽ thành người xấu" có thể được biểu diễn bằng vị từ như sau : ◼ NgườiXấu (x) = y: Bạn(x,y) và NgườiXấu(y) 7/13/2021 47
  48. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.1 Logic mệnh đề 3.3.2 Logic vị từ 3.3.3 Một số thuật giải liên quan đến lôgíc mệnh đề 3.3.4 Biểu diễn tri thức sử dụng luật dẫn xuất (luật sinh) 3.3.5 Biểu diễn tri thức nhờ mạng ngữ nghĩa 3.3.6 Biểu diễn tri thức nhờ Frame 7/13/2021 48
  49. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.3. Một số thuật giải liên quan đến lôgíc mệnh đề ◆ Một trong những vấn đề khá quan trọng của logic mệnh đề là chứng minh tính đúng đắn của phép suy diễn (a → b). ◆ với hai phép suy luận cơ bản của logic mệnh đề (Modus Ponens, Modus Tollens) cộng với các phép biến đổi hình thức, ta có thể chứng minh được phép suy diễn. 7/13/2021 49
  50. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.3. Một số thuật giải liên quan đến lôgíc mệnh đề ◆ Với máy tính, có thể dễ dàng chứng minh được mọi bài toán bằng một phương pháp "thô bạo" là lập bảng chân trị. ◆ Độ phức tạp của phương pháp này là quá lớn, O(2n) với n là số biến mệnh đề. ◆ Chúng ta sẽ nghiên cứu hai phương pháp chứng minh mệnh đề với độ phức tạp O(n). 7/13/2021 50
  51. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.3. Một số thuật giải liên quan đến lôgíc mệnh đề ◆ Thuật giải Vương Hạo: ◆ B1: Phát biểu lại giả thiết và kết luận của vấn đề theo dạng chuẩn sau : ◼ GT1, GT2, , GTn → KL1, KL2, , KLm ◼ Trong đó các GTi và KLi là các mệnh đề được xây dựng từ các biến mệnh đề và 3 phép nối cơ bản : , ,  ◆ B2: Chuyển vế các GTi và KLi có dạng phủ định. ◆ Ví dụ : ◼ p  q,  (r  s),  g, p  r → s,  p ◼ p  q, p  r, p → (r  s), g, s 7/13/2021 51
  52. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.3. Một số thuật giải liên quan đến lôgíc mệnh đề ◆ Thuật giải Vương Hạo: ◆ B3: Nếu GTi có phép  thì thay thế phép  bằng dấu ",“; Nếu KLi có phép  thì thay thế phép  bằng dấu ",“. ◆ Ví dụ : ◼ p  q, r  ( p  s) →  q,  s ◼ p, q, r,  p  s →  q,  s ◆ B4: Nếu GTi có phép  thì tách thành hai dòng con. Nếu ở KLi có phép  thì tách thành hai dòng con. ◆ Ví dụ : ◼ p,  p  q → q ◼ p,  p → q ◼ p, q → q 7/13/2021 52
  53. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.3. Một số thuật giải liên quan đến lôgíc mệnh đề ◆ B5: Một dòng được chứng minh nếu tồn tại chung một mệnh đề ở cả hai phía. ◆ Ví dụ: ◼ p, q → q được chứng minh ◼ p,  p → q p → p, q được chứng minh ◆ B6: ◼ a) Nếu một dòng không còn phép nối  hoặc  ở cả hai vế và ở hai vế không có chung một biến mệnh đề thì dòng đó không được chứng minh. ◼ b) Một vấn đề được chứng minh nếu tất cả dòng dẫn xuất từ dạng chuẩn ban đầu đều được chứng minh. 7/13/2021 53
  54. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.3. Một số thuật giải liên quan đến lôgíc mệnh đề ◆ Thuật giải Robinson: ◆ Phương pháp chứng minh phản chứng: ◆ Chứng minh phép suy luận (a → b) là đúng (với a là giả thiết, b là kết luận). ◆ Phản chứng: giả sử b sai suy ra b là đúng. ◆ Bài toán được chứng minh nếu a đúng và b đúng sinh ra một mâu thuẫn. 7/13/2021 54
  55. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.3. Một số thuật giải liên quan đến lôgíc mệnh đề ◆ Thuật giải Robinson: ◆ B1: 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 đó : GTi và KLj được xây dựng từ các biến mệnh đề và các phép toán , ,  ◆ B2: Nếu GTi có phép  thì thay bằng dấu ",“; Nếu KLi có phép  thì thay bằng dấu "," ◆ B3: Biến đổi dòng chuẩn ở B2 về thành danh sách mệnh đề như sau: ◼ {GT1, GT2, , GTn ,  KL1,  KL2, ,  KLm} 7/13/2021 55
  56. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.3. Một số thuật giải liên quan đến lôgíc mệnh đề ◆ Thuật giải Robinson: ◆ B4: Nếu trong danh sách mệnh đề ở bước 3 có 2 mệnh đề đối ngẫu thì bài toán được chứng minh. Ngược lại thì chuyển sang B5. ◆ B5: 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 đề ở bước 3. Nếu mệnh đề mới có các biến mệnh đề đối ngẫu thì các biến đó được loại bỏ. ◆ Ví dụ: p  q  r  s  q ◼ Hai mệnh đề  q, q là đối ngẫu nên sẽ được loại bỏ ◼ p   r  s 7/13/2021 56
  57. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.3. Một số thuật giải liên quan đến lôgíc mệnh đề ◆ B6: Thay thế hai mệnh đề vừa tuyển trong danh sách mệnh đề bằng mệnh đề mới. ◆ Ví dụ: ◼ {p  q ,  r  s  q , w  r, s  q} ◼ {p   r  s , w  r, s  q} ◆ B7: 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ó 2 mệnh đề nào đối ngẫu nhau thì vấn đề không được chứng minh. 7/13/2021 57
  58. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.3. Một số thuật giải liên quan đến lôgíc mệnh đề Ví dụ: Chứng minh rằng ◆  p  q,  q  r,  r  s,  u   s →  p,  u ◆ B3: { p  q,  q  r,  r  s,  u   s, p, u} ◆ B4: Có tất cả 6 mệnh đề nhưng chưa có mệnh đề nào đối ngẫu nhau. ◆ B5: tuyển một cặp mệnh đề (chọn hai mệnh đề có biến đối ngẫu). Chọn hai mệnh đề đầu: ◆  p  q   q  r  p  r ◆ Danh sách mệnh đề thành: ◆ { p  r ,  r  s,  u   s, p, u} ◆ Vẫn chưa có mệnh đề đối ngẫu. ◆ Tuyển hai cặp mệnh đề đầu tiên ◆  p  r   r  s  p  s 7/13/2021 58
  59. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.3. Một số thuật giải liên quan đến lôgíc mệnh đề ◆ Danh sách mệnh đề thành { p  s,  u   s, p, u} ◆ Vẫn chưa có hai mệnh đề đối ngẫu ◆ Tuyển hai cặp mệnh đề đầu tiên ◆  p  s   u   s  p   u ◆ Danh sách mệnh đề thành : { p   u, p, u} ◆ Vẫn chưa có hai mệnh đề đối ngẫu ◆ Tuyển hai cặp mệnh đề : ◆  p   u  u  p ◆ Danh sách mệnh đề trở thành : { p, p} ◆ Có hai mệnh đề đối ngẫu nên biểu thức ban đầu đã được chứng minh. 7/13/2021 59
  60. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.1 Logic mệnh đề 3.3.2 Logic vị từ 3.3.3 Một số thuật giải liên quan đến lôgíc mệnh đề 3.3.4 Biểu diễn tri thức sử dụng luật dẫn xuất (luật sinh) 3.3.5 Biểu diễn tri thức nhờ mạng ngữ nghĩa 3.3.6 Biểu diễn tri thức nhờ Frame 7/13/2021 60
  61. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.4. Biểu diễn tri thức sử dụng luật dẫn xuất (luật sinh) ◆ Phương pháp biểu diễn tri thức bằng luật sinh được phát minh bởi Newell và Simon trong lúc hai ông đang cố gắng xây dựng một hệ giải bài toán tổng quát. ◆ Đây là một kiểu biểu diễn tri thức có cấu trúc. ◆ Ý tưởng cơ bản là tri thức có thể được cấu trúc bằng một cặp điều kiện – hành động : "NẾU điều kiện xảy ra THÌ hành động sẽ được thi hành". 7/13/2021 61
  62. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.4. Biểu diễn tri thức sử dụng luật dẫn xuất (luật sinh) ◆ Luật sinh có dạng như sau: P1  P2   Pn → Q ◆ Trong logic vị từ: P1, P2, , Pn, Q là những biểu thức logic. ◆ Trong ngôn ngữ lập trình, mỗi một luật sinh là một câu lệnh. ◆ IF (P1 AND P2 AND AND Pn) THEN Q. ◆ Trong lý thuyết hiểu ngôn ngữ tự nhiên, mỗi luật sinh là một phép dịch: ◼ ONE → một. ◼ TWO → hai. ◼ JANUARY → tháng một 7/13/2021 62
  63. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.4. Biểu diễn tri thức sử dụng luật dẫn xuất (luật sinh) ◆ Để biểu diễn một tập luật sinh, người ta thường phải chỉ rõ hai thành phần chính sau: ◼ (1) Tập các sự kiện F(Facts) F = {f1, f2, fn} ◼ (2) Tập các quy tắc R (Rules) áp dụng trên các sự kiện dạng như sau: f1 ^ f2 ^ ^ fi → q. Trong đó, các fi , q đều thuộc F 7/13/2021 63
  64. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.4. Biểu diễn tri thức sử dụng luật dẫn xuất (luật sinh) ◆ Ví dụ: Cho cơ sở tri thức được xác định như sau ◆ Các sự kiện : A, B, C, D, E, F, G, H, K ◆ Tập các quy tắc hay luật sinh (rule) ◼ R1: A → E ◼ R2: B → D ◼ R3: H → A ◼ R4: E  G → C ◼ R5: E  K → B ◼ R6: D  E  K → C ◼ R7: G  K  F → A 7/13/2021 64
  65. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.4. Biểu diễn tri thức sử dụng luật dẫn xuất (luật sinh) ◆ Cơ chế suy luận trên các luật sinh ◆ Suy diễn tiến: là quá trình suy luận xuất phát từ một số sự kiện ban đầu, xác định các sự kiện có thể được "sinh" ra từ sự kiện này. ◼ Sự kiện ban đầu: H, K ◼ R3: H → A {A, H. K} ◼ R1: A → E {A, E, H, K} ◼ R5: E  K → B {A, B, E, H, K} ◼ R2: B → D {A, B, D, E, H, K} ◼ R6: D  E  K → C {A, B, C, D, E, H, K} ◆ Suy diễn lùi: là quá trình suy luận ngược xuất phát từ một số sự kiện ban đầu, ta tìm kiếm các sự kiện đã "sinh" ra sự kiện này. 7/13/2021 65
  66. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.4. Biểu diễn tri thức sử dụng luật dẫn xuất (luật sinh) ◆ Ví dụ: Tập các sự kiện: ◼ Ổ cứng là "hỏng" hay "hoạt động bình thường" ◼ Hỏng màn hình. ◼ Lỏng cáp màn hình. ◼ Tình trạng đèn ổ cứng là "tắt" hoặc "sáng". ◼ Có âm thanh đọc ổ cứng. ◼ Tình trạng đèn màn hình "xanh" hoặc "chớp đỏ". ◼ Không sử dụng được máy tính. ◼ Điện vào máy tính "có" hay "không". 7/13/2021 66
  67. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.4. Biểu diễn tri thức sử dụng luật dẫn xuất (luật sinh) ◆ Tập các luật: ◼ R1. Nếu ((ổ cứng "hỏng") hoặc (cáp màn hình "lỏng")) thì không sử dụng được máy tính. ◼ R2. Nếu (điện vào máy là "có") và ((âm thanh đọc ổ cứng là "không") hoặc tình trạng đèn ổ cứng là "tắt")) thì (ổ cứng "hỏng"). ◼ R3. Nếu (điện vào máy là "có") và (tình trạng đèn màn hình là "chớp đỏ") thì (cáp màn hình "lỏng"). 7/13/2021 67
  68. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.4. Biểu diễn tri thức sử dụng luật dẫn xuất (luật sinh) ◆ Để xác định được các nguyên nhân gây ra sự kiện "không sử dụng được máy tính", ta phải xây dựng một cấu trúc đồ thị gọi là đồ thị AND/OR như sau: Cấu trúc đồ thị AND/OR 7/13/2021 68
  69. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.4. Biểu diễn tri thức sử dụng luật dẫn xuất (luật sinh) ◆ Vấn đề tối ưu luật ◆ Rút gọn bên phải ◼ Luật sau hiển nhiên đúng: A  B → A (1) ◼ Do đó luật A  B → A  C ◼ Là hoàn toàn tương đương với A  B → C ◆ Quy tắc rút gọn: Có thể loại bỏ những sự kiện bên vế phải nếu những sự kiện đó đã xuất hiện bên vế trái. Nếu sau khi rút gọn mà vế phải trở thành rỗng thì luật đó là luật hiển nhiên. Ta có thể loại bỏ các luật hiển nhiên ra khỏi tri thức. 7/13/2021 69
  70. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.4. Biểu diễn tri thức sử dụng luật dẫn xuất (luật sinh) ◆ Rút gọn bên trái ◆ Xét các luật : ◼ (L1) A, B → C ◼ (L2) A → X ◼ (L3) X → C ◆ Rõ ràng là luật A, B → C có thể được thay thế bằng luật A → C mà không làm ảnh hưởng đến các kết luận trong mọi trường hợp. Ta nói rằng sự kiện B trong luật (1) là dư thừa và có thể được loại bỏ khỏi luật dẫn trên. 7/13/2021 70
  71. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.4. Biểu diễn tri thức sử dụng luật dẫn xuất (luật sinh) ◆ Phân rã và kết hợp luật ◼ Luật A  B → C Tương đương với hai luật ◼ A → C ◼ B → C ◆ Với quy tắc này, ta có thể loại bỏ hoàn toàn các luật có phép nối HOẶC. Các luật có phép nối này thường làm cho thao tác xử lý trở nên phức tạp. 7/13/2021 71
  72. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.4. Biểu diễn tri thức sử dụng luật dẫn xuất (luật sinh) ◆ Luật thừa ◆ Một luật dẫn A → B được gọi là thừa nếu có thể suy ra luật này từ những luật còn lại. ◆ Ví dụ: trong tập các luật gồm {A → B, B → C, A → C} thì luật thứ 3 là luật thừa vì nó có thể được suy ra từ 2 luật còn lại. 7/13/2021 72
  73. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.4. Biểu diễn tri thức sử dụng luật dẫn xuất (luật sinh) Thuật toán tối ưu tập luật dẫn ◆ B1: Rút gọn vế phải ◼ Với mỗi luật r trong R; Với mỗi sự kiện A VếPhải(r) ◼ Nếu A VếTrái(r) thì Loại A ra khỏi vế phải của R. ◼ Nếu VếPhải(r) rỗng thì loại bỏ r ra khỏi hệ luật dẫn: R = R – {r} ◆ B2: Phân rã các luật ◼ Với mỗi luật r : X1  X2   Xn → Y trong R ◼ Với mỗi i từ 1 đến n R := R + {Xi → Y} ◼ R := R – {r} 7/13/2021 73
  74. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.4. Biểu diễn tri thức sử dụng luật dẫn xuất (luật sinh) Thuật toán tối ưu tập luật dẫn ◆ B3: Loại bỏ luật thừa ◼ Với mỗi luật r thuộc R ◼ Nếu VếPhải(r) BaoĐóng(VếTrái(r), R-{r}) thì R := R – {r} ◆ B4: Rút gọn vế trái ◼ Với mỗi luật dẫn r: X : A1  A2, , An → Y thuộc R ◼ Với mỗi sự kiện Ai thuộc r ◼ Gọi luật r1: X – Ai → Y ◼ S = ( R – {r} )  {r1} ◼ Nếu BaoĐóng(X – Ai, S)  BaoĐóng(X, R) thì loại sự kiện A ra khỏi X 7/13/2021 74
  75. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.4. Biểu diễn tri thức sử dụng luật dẫn xuất (luật sinh) ◆ Ưu điểm và nhược điểm của biểu diễn tri thức bằng luật ◆ Ưu điểm ◼ Các luật dễ hiểu, dễ dàng dùng để trao đổi với người dùng ◼ dễ xây dựng cơ chế suy luận và giải thích từ các luật. ◼ Việc hiệu chỉnh và bảo trì hệ thống là tương đối dễ dàng. ◼ Có thể cải tiến để tích hợp các luật mờ. ◼ Các luật thường ít phụ thuộc vào nhau 7/13/2021 75
  76. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.4. Biểu diễn tri thức sử dụng luật dẫn xuất (luật sinh) ◆ Nhược điểm ◼ Các tri thức phức tạp đôi lúc đòi hỏi quá nhiều (hàng ngàn) luật sinh → tốc độ lẫn quản trị hệ thống. ◼ thường biểu diễn tri thức bằng luật sinh (dễ hiểu, dễ cài đặt). Đây là nhược điểm mang tính chủ quan của con người. ◼ Cơ sở tri thức luật sinh lớn sẽ làm giới hạn khả năng tìm kiếm của chương trình điều khiển. 7/13/2021 76
  77. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.1 Logic mệnh đề 3.3.2 Logic vị từ 3.3.3 Một số thuật giải liên quan đến lôgíc mệnh đề 3.3.4 Biểu diễn tri thức sử dụng luật dẫn xuất (luật sinh) 3.3.5 Biểu diễn tri thức nhờ mạng ngữ nghĩa 3.3.6 Biểu diễn tri thức nhờ Frame 7/13/2021 77
  78. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.5. Biểu diễn tri thức nhờ mạng ngữ nghĩa ◆ Mạng ngữ nghĩa là một phương pháp biểu diễn tri thức đầu tiên và cũng là phương pháp dễ hiểu nhất đối với chúng ta. ◆ Phương pháp này biểu diễn tri thức dưới dạng một đồ thị, trong đó: ◼ đỉnh là các đối tượng (khái niệm) ◼ các cung cho biết mối quan hệ giữa các đối tượng (khái niệm). 7/13/2021 78
  79. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.5. Biểu diễn tri thức nhờ mạng ngữ nghĩa ◆ Chẳng hạn: giữa các khái niệm chích chòe, chim, hót, cánh, tổ có một số mối quan hệ như sau : ◼ Chích chòe là một loài chim. ◼ Chim biết hót ◼ Chim có cánh ◼ Chim sống trong tổ 7/13/2021 79
  80. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.5. Biểu diễn tri thức nhờ mạng ngữ nghĩa ◆ Biểu diễn bằng một đồ thị: Chích chòe có làm tổ không?". Mạng ngữ nghĩa 7/13/2021 80
  81. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.5. Biểu diễn tri thức nhờ mạng ngữ nghĩa ◆ Mạng ngữ nghĩa là một đồ thị nên nó thừa hưởng tất cả những mặt mạnh của công cụ này. Như: ◆ Thuật toán tìm liên thông, tìm đường đi ngắn nhất, để thực hiện các cơ chế suy luận. ◆ Điểm đặc biệt của mạng ngữ nghĩa so với đồ thị thông thường chính là việc gán một ý nghĩa (có, làm, là, biết, ) cho các cung. ◆ Việc gán ngữ nghĩa vào các cung của đồ thị đã giúp giảm bớt được số lượng đồ thị. ◆ Ví dụ, nếu sử dụng đồ thị thông thường, ta phải dùng đến 4 loại đồ thị cho 4 mối liên hệ: một đồ thị để biểu diễn mối liên hệ "là", một đồ thị cho mối liên hệ "làm", một cho "biết" và một cho "có". 7/13/2021 81
  82. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.5. Biểu diễn tri thức nhờ mạng ngữ nghĩa ◆ mô hình mạng ngữ nghĩa được dùng chủ yếu để phân tích vấn đề. ◆ Sau đó, nó sẽ được chuyển đổi sang dạng luật hoặc frame để thi hành hoặc mạng ngữ nghĩa sẽ được dùng kết hợp với một số phương pháp biểu diễn khác. 7/13/2021 82
  83. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.5. Biểu diễn tri thức nhờ mạng ngữ nghĩa ◆ Ưu điểm và nhược điểm của mạng ngữ nghĩa ◆ Ưu điểm ◼ Dễ dàng thêm vào mạng các đỉnh hoặc cung mới để bổ sung các tri thức cần thiết. ◼ Mạng ngữ nghĩa có tính trực quan cao nên rất dễ hiểu. ◼ Mạng ngữ nghĩa cho phép các đỉnh có thể thừa kế các tính chất từ các đỉnh khác thông qua các cung loại "là", từ đó, có thể tạo ra các liên kết "ngầm" giữa những đỉnh không có liên kết trực tiếp với nhau. ◼ Mạng ngữ nghĩa hoạt động khá tự nhiên theo cách thức con người ghi nhận thông tin. 7/13/2021 83
  84. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.5. Biểu diễn tri thức nhờ mạng ngữ nghĩa ◆ Nhược điểm ◼ Tính thừa kế (vốn là một ưu điểm) trên mạng sẽ có thể dẫn đến nguy cơ mâu thuẫn trong tri thức. ◼ tính thừa kế sinh ra rất nhiều mối liên "ngầm" nên khả năng nảy sinh ra một mối liên hệ không hợp lệ là rất lớn! ◆ Hầu như không thể biển diễn các tri thức dạng thủ tục bằng mạng ngữ nghĩa vì các khái niệm về thời gian và trình tự không được thể hiện tường minh trên mạng ngữ nghĩa. 7/13/2021 84
  85. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.5. Biểu diễn tri thức nhờ mạng ngữ nghĩa ◆ Các ví dụ tiêu biểu ◆ Hai loại ứng dụng tiêu biểu của mạng ngữ nghĩa là xử lý ngôn ngữ tự nhiên và giải bài toán tự động. ◆ Ví dụ 1: Trong ứng dụng xử lý ngôn ngữ tự nhiên, mạng ngữ nghĩa có thể giúp máy tính phân tích được cấu trúc của câu để từ đó có thể phần nào "hiểu" được ý nghĩa của câu. Chẳng hạn, câu "Châu đang đọc một cuốn sách dày và cười khoái trá" có thể được biểu diễn bằng một mạng ngữ nghĩa như sau: 7/13/2021 85
  86. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.5. Biểu diễn tri thức nhờ mạng ngữ nghĩa Mạng ngữ nghĩa xử lý ngôn ngữ tự nhiên 7/13/2021 86
  87. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.5. Biểu diễn tri thức nhờ mạng ngữ nghĩa ◆ Ví dụ 2: Giải bài toán tam giác tổng quát ◼ "Cho 3 cạnh của tam giác, tính chiều dài các đường cao", "Cho góc a, b và cạnh AC. Tính chiều dài trung tuyến", ◼ việc bạn cần làm là lấy giấy bút ra tìm cách tính, sau khi đã xác định các bước tính toán, bạn chuyển nó thành chương trình. ◼ Nếu có 10 bài, bạn phải làm lại việc tính toán rồi lập trình 10 lần. Nếu có 100 bài, bạn phải làm 100 lần. ◼ Bài toán này sẽ được giải bằng mạng ngữ nghĩa. 7/13/2021 87
  88. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.5. Biểu diễn tri thức nhờ 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 một tam giác hay để xây dựng một tam giác ta cần có 3 yếu tố trong đó phải có yếu tố cạnh. 3 Như vậy có khoảng C 22 -1 cách để xây dựng hay xác định một tam giác. Theo thống kê, có khoảng 200 công thức liên quan đến cạnh và góc một tam giác. ◆ Để giải bài toán này bằng công cụ mạng ngữ nghĩa, ta phải sử dụng khoảng 200 đỉnh để chứa công thức và khoảng 22 đỉnh để chứa các yếu tố của tam giác. Mạng ngữ nghĩa cho bài toán này có cấu trúc như sau: ◆ Đỉnh của đồ thị bao gồm hai loại: ◼ Đỉnh chứa công thức (ký hiệu bằng hình chữ nhật) ◼ Đỉnh chứa yếu tố của tam giác (ký hiệu bằng hình tròn) 7/13/2021 88
  89. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.5. Biểu diễn tri thức nhờ mạng ngữ nghĩa ◆ 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 (không có trường hợp cung nối giữa hai đỉnh hình tròn hoặc cung nối giữa hai đỉnh hình chữ nhật). 7/13/2021 89
  90. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.5. Biểu diễn tri thức nhờ mạng ngữ nghĩa ◆ Cơ chế suy diễn thực hiện theo thuật toán "loang" đơn giản sau: ◆ B1: Kích hoạt những đỉnh hình tròn đã cho ban đầu (những yếu tố đã có giá trị) ◆ B2: Lặp lại bước sau cho đến khi kích hoạt đượ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. ◆ 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à tính giá trị đỉnh còn lại này thông qua công thức ở đỉnh hình chữ nhật). 7/13/2021 90
  91. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.5. Biểu diễn tri thức nhờ mạng ngữ nghĩa ◆ Giả sử ta có mạng ngữ nghĩa để giải bài toán tam giác như hình sau Mạng ngữ nghĩa giải bài toán tam giác 7/13/2021 91
  92. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.5. Biểu diễn tri thức nhờ mạng ngữ nghĩa ◆ "Cho hai góc A, B và cạnh a của tam giác. Tính hC". ◼ Bắt đầu: đỉnh A, B, a của đồ thị được kích hoạt. ◼ Công thức (1) được kích hoạt (vì A, B, a được kích hoạt). Từ (1) tính được cạnh b. Đỉnh b được kích hoạt. ◼ Công thức (4) được kích hoạt (vì A, B). Từ công thức (4) tính được góc C ◼ Công thức (2) được kích hoạt (vì 3 đỉnh B, C, b được kích hoạt). Từ công thức (2) tính được cạnh c. Đỉnh c được kích hoạt. ◼ Công thức (3) được kích hoạt (vì 3 đỉnh a, b, c được kích hoạt) . Từ công thức (3) tính được diện tích S. Đỉnh S được kích hoạt. ◼ Công thức (5) được kích hoạt (vì 2 đỉnh S, c được kích hoạt). Từ công thức (5) tính được hC. Đỉnh hC được kích hoạt. ◼ Giá trị hC đã được tính. Thuật toán kết thúc. 7/13/2021 92
  93. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.5. Biểu diễn tri thức nhờ mạng ngữ nghĩa ◆ Mạng ngữ nghĩa giải bài toán tam giác bằng một mảng hai chiều A: ◼ Cột: ứng với công thức. ◼ Dòng: ứng với yếu tố tam giác. ◼ Phần tử A[i][ j] = -1 nghĩa là trong công thức ứng với cột j có yếu tố tam giác ứng với dòng i. Ngược lại A[i][j] = 0. ◼ Để thực hiện thao tác "kích hoạt" một đỉnh hình tròn, ta đặt giá trị của toàn dòng ứng với yếu tố tam giác bằng 1. ◼ Để kiểm tra xem một công thức đã có đủ n-1 yếu tố ta lấy hiệu giữa tổng số ô có giá trị bằng 1 và tổng số ô có giá trị -1 trên cột ứng với công thức cần kiểm tra. Nếu kết quả bằng n, thì công thức đã có đủ n-1 yếu tố. 7/13/2021 93
  94. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.5. Biểu diễn tri thức nhờ mạng ngữ nghĩa ◆ Mảng biểu diễn mạng ngữ nghĩa ban đầu (1) (2) (3) (4) (5) A -1 0 0 -1 0 B -1 -1 0 -1 0 C 0 -1 0 -1 0 a -1 0 -1 0 0 b -1 -1 -1 0 0 c 0 -1 -1 0 -1 S 0 0 -1 0 -1 hC 0 0 0 0 -1 7/13/2021 94
  95. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.5. Biểu diễn tri thức nhờ mạng ngữ nghĩa (1) (2) (3) (4) (5) A 1 0 0 1 0 B 1 1 0 1 0 C 0 -1 0 -1 0 a 1 0 1 0 0 b -1 -1 -1 0 0 c 0 -1 -1 0 -1 S 0 0 -1 0 -1 hC 0 0 0 0 -1 Trên cột (1), hiệu (1+1+1 – (-1)) = 4 nên dòng b sẽ được kích hoạt. 7/13/2021 95
  96. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.5. Biểu diễn tri thức nhờ mạng ngữ nghĩa (1) (2) (3) (4) (5) A 1 0 0 1 0 B 1 1 0 1 0 C 0 -1 0 -1 0 a 1 0 1 0 0 b 1 1 1 0 0 c 0 -1 -1 0 -1 S 0 0 -1 0 -1 hC 0 0 0 0 -1 Trên cột (4), hiệu (1+1 – (-1)) = 3 nên dòng C sẽ được kích hoạt. 7/13/2021 96
  97. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.5. Biểu diễn tri thức nhờ mạng ngữ nghĩa (1) (2) (3) (4) (5) A 1 0 0 1 0 B 1 1 0 1 0 C 0 1 0 1 0 a 1 0 1 0 0 b 1 1 1 0 0 c 0 -1 -1 0 -1 S 0 0 -1 0 -1 hC 0 0 0 0 -1 Trên cột (2), hiệu (1+1+1 – (-1)) = 4 nên dòng c được kích hoạt. 7/13/2021 97
  98. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.5. Biểu diễn tri thức nhờ mạng ngữ nghĩa (1) (2) (3) (4) (5) A 1 0 0 1 0 B 1 1 0 1 0 C 0 1 0 1 0 a 1 0 1 0 0 b 1 1 1 0 0 c 0 1 1 0 1 S 0 0 -1 0 -1 hC 0 0 0 0 -1 Trên cột (3), hiệu (1+1+1 – (-1)) = 4 nên dòng S được kích hoạt 7/13/2021 98
  99. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.5. Biểu diễn tri thức nhờ mạng ngữ nghĩa (1) (2) (3) (4) (5) A 1 0 0 1 0 B 1 1 0 1 0 C 0 1 0 1 0 a 1 0 1 0 0 b 1 1 1 0 0 c 0 1 1 0 1 S 0 0 1 0 1 hC 0 0 0 0 -1 Trên cột (5), hiệu (1+1 – (-1)) = 3 nên dòng hC được kích hoạt. 7/13/2021 99
  100. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.1 Logic mệnh đề 3.3.2 Logic vị từ 3.3.3 Một số thuật giải liên quan đến lôgíc mệnh đề 3.3.4 Biểu diễn tri thức sử dụng luật dẫn xuất (luật sinh) 3.3.5 Biểu diễn tri thức nhờ mạng ngữ nghĩa 3.3.6 Biểu diễn tri thức nhờ Frame 7/13/2021 100
  101. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.6. Biểu diễn tri thức nhờ Frame ◆ Frame là một CTDL chứa tất cả những tri thức liên quan đến một đối tượng cụ thể nào đó. ◆ khác với các phương pháp biểu diễn tri thức trước, frame "đóng gói" toàn bộ một đối tượng, tình huống hoặc cả một vấn đề phức tạp thành một thực thể duy nhất có cấu trúc. ◆ Một frame bao hàm trong nó một khối lượng tri thức về một đối tượng, sự kiện, vị trí, tình huống hoặc những yếu tố khác. 7/13/2021 101
  102. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.6. Biểu diễn tri thức nhờ Frame ◆ phương pháp biểu diễn tri thức bằng frame chính là nguồn gốc của ngôn ngữ lập trình hướng đối tượng. ◆ ý tưởng chính của frame là khi biểu diễn một tri thức, ta sẽ "gắn kèm" những thao tác thường gặp trên tri thức này. ◆ Chẳng hạn như khi mô tả khái niệm về hình chữ nhật, ta sẽ gắn kèm cách tính chu vi, diện tích. 7/13/2021 102
  103. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.6. Biểu diễn tri thức nhờ Frame ◆ Frame thường được dùng để biểu diễn ◼ những tri thức "chuẩn" ◼ những tri thức được xây dựng dựa trên những kinh nghiệm ◼ các đặc điểm đã được hiểu biết cặn kẽ. ◆ Bộ não con người luôn "lưu trữ" rất nhiều các tri thức chung mà khi cần, chúng có thể "lấy ra" để vận dụng nó trong những vấn đề cần phải giải quyết. ◆ Frame là một công cụ thích hợp để biểu diễn những kiểu tri thức này. 7/13/2021 103
  104. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.6. Biểu diễn tri thức nhờ Frame ◆ Cấu trúc của frame ◆ Một frame bao gồm hai thành phần cơ bản là slot và facet. Một slot là một thuộc tính đặc tả đối tượng được biểu diễn bởi frame. ◆ Mỗi slot có thể chứa một hoặc nhiều facet. Các facet (slot "con") đặc tả thông tin hoặc thủ tục liên quan đến thuộc tính được mô tả bởi slot. 7/13/2021 104
  105. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.6. Biểu diễn tri thức nhờ Frame ◆ Facet có nhiều loại khác nhau, sau đây là một số facet thường gặp. ◼ Value (giá trị): cho biết giá trị của thuộc tính đó. ◼ Default (giá trị mặc định): hệ thống sẽ tự động sử dụng giá trị trong facet này nếu slot là rỗng ◼ Range (miền giá trị): tương tự như kiểu biến, cho biết giá trị slot có thể nhận những loại giá trị gì (như số nguyên, số thực, chữ cái, ) ◼ If added : mô tả một hành động sẽ được thi hành khi một giá trị trong slot được thêm vào (hoặc được hiệu chỉnh). ◼ If needed : được sử dụng khi slot không có giá trị nào. Facet mô tả một hàm để tính ra giá trị của slot. 7/13/2021 105
  106. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.6. Biểu diễn tri thức nhờ Frame Frame : XE HƠI Thuộc lớp: phương tiện vận chuyển. Tên nhà sản xuất: Audi Quốc gia của nhà sản xuất: Đức Model: 5000 Turbo Frame MÁY Loại xe: Sedan Xy-lanh: 3.19 inch Trọng lượng: 3300lb Tỷ lệ nén: 3.4 inche Số lượng cửa: 4 (default) Xăng: TurboCharger Hộp số: 3 số tự động Mã lực: 140 hp Số lượng bánh: 4 (default) Máy (tham chiếu đến frame Máy) Kiểu: In-line, overhead cam Số xy-lanh: 5 Khả năng tăng tốc 0-60 : 10.4 giây ¼ dặm : 17.1 giây, 85 mph. Frame 7/13/2021 106
  107. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.6. Biểu diễn tri thức nhờ Frame ◆ Tính kế thừa ◆ một hệ thống trí tuệ nhân tạo thường sử dụng nhiều frame được liên kết với nhau. ◆ Frame: có tính phân cấp -> kế thừa. 7/13/2021 107
  108. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.6. Biểu diễn tri thức nhờ Frame Cấu trúc phân cấp của Frame 7/13/2021 108
  109. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.6. Biểu diễn tri thức nhờ Frame ◆ Một ví dụ biểu diễn các đối tượng hình học bằng frame ◆ Các kiểu dữ liệu cơ bản : ◼ Area: numeric; // diện tích ◼ Height: numeric; //chiều cao ◼ Perimeter: numberic; //chu vi ◼ Side: numeric; //cạnh ◼ Diagonal: numeric; //đường chéo ◼ Radius: numeric; //bán kính ◼ Angle: numeric; //góc ◼ Diameter: numeric; //đường kính ◼ pi: (val:numeric = 3.14159) 7/13/2021 109
  110. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.6. Biểu diễn tri thức nhờ Frame ◆ Frame: CIRCLE (hình tròn) ◼ r: radius; ◼ s: area; ◼ p: perimeter; ◼ d: diameter; ◼ d = 2 x r; 2 ◼ s = pi x r ; ◼ p = 2 x pi x r; 7/13/2021 110
  111. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.6. Biểu diễn tri thức nhờ Frame ◆ Frame RECTANGLE (hình chữ nhật) ◼ b1: side; ◼ b2: side; ◼ s: area; ◼ p: perimeter; ◼ s = b1 x b2; ◼ p = 2 x (b1+b2); 2 2 2 ◼ d2 = b1 + b2 ; 7/13/2021 111
  112. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.6. Biểu diễn tri thức nhờ Frame ◆ Frame SQUARE (hình vuông) ◼ Là: RECTANGLE ◼ b1 = b2; ◆ Frame RHOMBUS (hình thoi) ◼ b: side; ◼ d1: diagonal; ◼ d2: diagonal; ◼ s: area; ◼ p: perimeter; ◼ alpha1: angle; ◼ alpha2: angle; ◼ h: height; ◼ cos (alpha2/2) x d1 = h; ◼ s = d1 x d2 / 2; ◼ p = 4 x b; ◼ s = b x h; ◼ cos (alpha2/2)/(2x b) = d2; 7/13/2021 112
  113. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.6. Biểu diễn tri thức nhờ Frame ◆ Sau khi đã biểu diễn các tri thức về các hình học cơ bản xong, ta có thể vận dụng nó để giải các bài toán hình học, chẳng hạn bài toán tính diện tích. ◆ Ví dụ, cho hình vuông k và vòng tròn nội tiếp c, biết cạnh hình vuông có chiều dài là x, hãy viết chương trình để tính diện tích phần tô đen. 7/13/2021 113
  114. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.6. Biểu diễn tri thức nhờ Frame numeric x, s; square; circle c; { ; k.b1 = x; c.d = x; s = k.s – c.s; } 7/13/2021 114
  115. 3.3 Các phương pháp biểu diễn tri thức trên máy tính 3.3.6. Biểu diễn tri thức nhờ Frame ◆ Để tăng thêm sức mạnh cho hệ thống này, người ta thường cài đặt một mạng ngữ nghĩa ngay bên trong mỗi frame. ◆ Chẳng hạn, ta có thể có một frame TRIANGLE, trong đó cài đặt một mạng ngữ nghĩa để đặc tả mối liên hệ giữa các yếu tố tam giác. 7/13/2021 115
  116. Tổng kết chương 7/13/2021 116
  117. Câu hỏi & Bài tập Phase 1 Phase 3 Phase 2 Phase 1 Phase 3 Phase 2 Phase 1 Phase 3 Phase 2 Phase 2 7/13/2021 117
  118. TRƯỜNG CAO ĐẲNG CNTT HỮU NGHỊ ViỆT - HÀN KHOA KHOA HỌC MÁY TÍNH