Cơ sở trí tuệ nhân tạo - Chương 3: Biểu diễn tri thức - Phạm Thi Vương

Nội dung text: Cơ sở trí tuệ nhân tạo - Chương 3: Biểu diễn tri thức - Phạm Thi Vương

1. BIỂU DIỄN TRI THỨC Phạm Thi Vương
2. Nội dung • 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 10/11/2009 Nhập mơn Trí tuệ nhân tạo 2
3. Khái niệm • Tri thức (knowledge) ? • Knowledge: the psychological result of perception and learning and reasoning (English – English Dictionary) • Tri thức là kết quả của quá trình nhận thức, học tập và lập luận • 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 đó. 10/11/2009 Nhập mơn Trí tuệ nhân tạo 3
4. Tri thức thường bao gờm • Khái niệm – Khái niệm: điểm, tam giác • Các sựki ện, các nguyên lý, định lý, định luật, quan hệ giữa các khái niệm = luật – 2 tam giác cĩ 3 cạnh bằng nhau thì bằng nhau • Kinh nghiệm 10/11/2009 Nhập mơn Trí tuệ nhân tạo 4
5. Cơ sở tri thức • 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. 10/11/2009 Nhập mơn Trí tuệ nhân tạo 5
6. Vấn đềbi ểu diễn tri thức • tìm ra các kỹ thuật, các phương pháp thể 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 tính có thểx ử lý được 10/11/2009 Nhập mơn Trí tuệ nhân tạo 6
7. Biểu diễn tri thức Dạng thực Dạng hình thức - Facts (sự kiện): - Representations (sự biểu diễn): sự thật trong lĩnh vực dạng biểu diễn của sự kiện theo lược đồ được chọn. Cái cần biểu diễn Cái có thể xử lý được 10/11/2009 Nhập mơn Trí tuệ nhân tạo 7
8. 4 thuộc tính của hệ thống BDTT 1. Representational adequacy: Khả năng biểu diễn tất cả các tri thức cần thiết cho lĩnh vực đó. 2. Inferential adequacy: Khả năng xử lý các cấu trúc sẵn có để sinh ra các cấu trúc mới tương ứng với tri thức mới được sinh ra từ tri thức cũ. 10/11/2009 Nhập mơn Trí tuệ nhân tạo 8
9. 4 thuộc tính của hệ thống BDTT 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ơ chế suy luận theo hướng có nhiều triển vọng nhất. 4. Acquisitional efficiency: Khả năng thu được thơng tin mới dễ dàng. 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ểm sốt việc thu được tri thức. 10/11/2009 Nhập mơn Trí tuệ nhân tạo 9
10. Năng lực hiện nay: – Khơng một hệ thống nào có thể tối ưu tất cả các khả năng trên cho mọi kiểu tri thức. – Nhiều kỹ thuật dùng cho biểu diễn tri thức cùng tờn tại. – Chương trình thường dùng nhiều hơn 1 kỹ thuật biểu diễn. 10/11/2009 Nhập mơn Trí tuệ nhân tạo 10
11. Phân loại tri thức • Tri thức thủ tục: mơ tả cách thức, các buớ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 10/11/2009 Nhập mơn Trí tuệ nhân tạo 11
12. Phân loại tri thức • 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 10/11/2009 Nhập mơn Trí tuệ nhân tạo 12
13. Phân loại tri thức • 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 cịn được gọi là tri thức nơng cạn do khơng bảo đảm hồn tồn chính xác về kết quả giải quyết vấn đề. 10/11/2009 Nhập mơn Trí tuệ nhân tạo 13
14. Phân loại tri thức • 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 đề. 10/11/2009 Nhập mơn Trí tuệ nhân tạo 14
15. Phương pháp tiếp nhận tri thức • Thụ động – Gián tiếp: những tri thức kinh điển. – Trực tiếp: những tri thức kinh nghiệm (khơng kinh điển) do “chuyên gia lĩnh vực” đưa ra • Chủ động – Đối với những tri thức tiềm ẩn, khơng rõ ràng hệ thống phải tự phân tích, suy diễn, khám phá để có thêm tri thức mới 10/11/2009 Nhập mơn Trí tuệ nhân tạo 15
16. Phương pháp BDTT • Dựa trên logic hình thức: dạng biểu diễn tri thức cở điển nhất trong máy tính, với hai dạng phở biến là logic mệnh đề và logic vị từ. Cả hai kỹ thuật này đều dùng ký hiệu để thể hiện tri thức và các tốn tử áp lên các ký hiệu để suy luận logic. 10/11/2009 Nhập mơn Trí tuệ nhân tạo 16
17. Phương pháp BDTT • Dạng sơ đờ mạng: là 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 10/11/2009 Nhập mơn Trí tuệ nhân tạo 17
18. Phương pháp BDTT • Dạng luật dẫn: 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. 10/11/2009 Nhập mơn Trí tuệ nhân tạo 18
19. Phương pháp BDTT • Dạng cấu trúc frames, classes: là cấu trúc dữ liệu để thể hiện tri thức đa dạng về khái niệm hay đối tượng nào đó. • Sử dụng các ngơn ngữ đặc tả 10/11/2009 Nhập mơn Trí tuệ nhân tạo 19
20. BDTT theo logic hình thức • Logic mệnh đề • Logic vịt ừ cấp 1, cấp cao • Logic đa trị: các mệnh đềkhơng đúng khơng sai • Logic mờ • Logic thời gian 10/11/2009 Nhập mơn Trí tuệ nhân tạo 20
21. Logic mệnh đề • Các ký hiệu đại diện cho các mệnh đề có chân trị đúng hoặc sai: p,q,r, (có thể phụ thuộc vào khơng gian, thời gian, chủ thể phát biểu, hoặc luơn có chân trị xác định. • Các tốn tửlogic not(), and(), or(), • Quy ước ngữ nghĩa: hằng đúng, hằng sai • Các tiên đề, các quy luật 10/11/2009 Nhập mơn Trí tuệ nhân tạo 21
22. Logic mệnh đề • 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 (có thể phụ thuộc vào khơng gian, thời gian, chủ thể phát biểu, hoặc luơn có chân trị xác định). 10/11/2009 Nhập mơn Trí tuệ nhân tạo 22
23. Logic mệnh đề • Các ký hiệu đại diện cho các mệnh đề có chân trị đúng hoặc sai: p,q,r. • Các tốn tửlogic not(), and(), or(), • Quy ước ngữ nghĩa: hằng đúng, hằng sai • Các tiên đề, các quy luật 10/11/2009 Nhập mơn Trí tuệ nhân tạo 23
24. • Biểu thức logic được định nghĩa đệ quy như sau: – Các hằng logic (True, False) và các biến mệnh đề là các biểu thức logic – Các biểu thức logic kết hợp với các tốn 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ểu thức logic 10/11/2009 Nhập mơn Trí tuệ nhân tạo 24
25. • Biểu thức logic dạng chuẩn: là biểu thức được xây dựng từ các biến mệnh đề và các phép tốn , , . 10/11/2009 Nhập mơn Trí tuệ nhân tạo 25
26. Tri thức biểu diễn theo logic mệnh đề – Tập kí hiệu, mỡi kí hiệu đại diện cho mơt vấn đề cơ bản trong tri thức: p,q,r Các mệnh đề 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. – 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 10/11/2009 Nhập mơn Trí tuệ nhân tạo 26
27. Ví dụ • Ta có cơ sở tri thức mơ tả mối quan hệ của các thành phần trong một tam giác như sau: – Nếu biết 3 cạnh của 1 tam giác ta có thể biết nữa chu vi của tam giác đó – Nếu biết 2 cạnh và nữa chu vi của một tam giác thì ta có thể biết được cạnh cịn lại của tam giác đó – Nếu biết được diện tích và một cạnh của một tam giác thì ta có thể biết được chiều cao tương ứng với cạnh đó – Nếu biết 2 cạnh và một góc kẹp giữa 2 cạnh đó của một tam giác thì ta có thể biết được cạnh cịn lại của tam giác đó. 10/11/2009 Nhập mơn Trí tuệ nhân tạo 27
28. – Nếu biết 2 cạnh và một góc kẹp giữa 2 cạnh đó của một tam giác thì ta có thể biết được diện tích của tam giác đó – Nếu biết ba cạnh và nữa chu vi của một tam giác thì ta biết được diện tích của tam giác đó – Nếu biết diện tích và đường cao của một tam giác thì ta biết được cạnh tương ứng với đường cao của tam giác đó 10/11/2009 Nhập mơn Trí tuệ nhân tạo 28
29. Logic mệnh đề • Vấn đề: chứng minh tính đúng đắn của suy diễn a b • Giải quyết: sử dụng các phép suy luận và biến đởi logic khó cài đặt Sử dụng bảng chân trị O( 2n) 2 phương pháp với độ phức tạp O(n) 10/11/2009 Nhập mơn Trí tuệ nhân tạo 29
30. 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 10/11/2009 Nhập mơn Trí tuệ nhân tạo 30
31. 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ó chứa phép  thì tách thành hai dòng con. Nếu ở KLi có chứa phép  thì tách thành hai dòng con. Ví dụ : p, p  q q p, p q p, q q 10/11/2009 Nhập mơn Trí tuệ nhân tạo 31
32. Thuật giải Vương Hạo 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 B6 : a) Nếu một dòng không còn phép nối  hoặc  ở cả hai vế và ở 2 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. 10/11/2009 Nhập mơn Trí tuệ nhân tạo 32
33. Thuật giải Vương Hạo r, p  s q, r  s a  b c và b  c d và a và b, suy ra d 10/11/2009 Nhập mơn Trí tuệ nhân tạo 33
34. Thuật giải Vương Hạo Xét các câu đúng sau: • “Nếu trời mưa thì Lan mang theo 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 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 10/11/2009 Nhập mơn Trí tuệ nhân tạo 34
35. Thuật giải Vương Hạo • Cho các biểu thức logic mệnh đề đúng sau a f a (f p) p ^ q d a a ^ d g • Hãy dùng phương pháp Vương Hạo để chứng minh hoặc bác bỏ g1 10/11/2009 Nhập mơn Trí tuệ nhân tạo 35
36. Thuật giải Robinson „ Thuật giải này hoạt động dựa trên 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. 10/11/2009 Nhập mơn Trí tuệ nhân tạo 36
37. 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 thế phép  bằng dấu “,” Nếu ở KLi có phép  thì thay thế phép  bằng dấu “,” „ B3 : Biến đổi dòng chuẩn ở B1 về thành danh sách mệnh đề như sau : { GT1, GT2, , GTn ,  KL1,  KL2, ,  KLm } 10/11/2009 Nhập mơn Trí tuệ nhân tạo 37
38. Thuật giải Robinson „ B4 : Nếu trong danh sách mệnh đề ở bước 3 có 2 mệnh đề đối ngẫu nhau thì bài toán được chứng minh. Ngược lại thì chuyển sang B5. (a và a gọi là hai mệnh đề đối ngẫu nhau) „ 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 nhau 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 10/11/2009 Nhập mơn Trí tuệ nhân tạo 38
39. Thuật giải Robinson „ 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. 10/11/2009 Nhập mơn Trí tuệ nhân tạo 39
40. Thuật giải Robinson „ Chứng minh rằng „ p  q, q  r, r  s, u  s p, u 10/11/2009 Nhập mơn Trí tuệ nhân tạo 40
41. Thuật giải Robinson „ 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. 10/11/2009 Nhập mơn Trí tuệ nhân tạo 41
42. Thuật giải Robinson „ Tuyển hai cặp mệnh đề đầu tiên: p  r  r  s p  s 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. 10/11/2009 Nhập mơn Trí tuệ nhân tạo 42
43. Logic vị từ • Logic mệnh đề: khơng thể can thiệp vào cấu trúc của một mệnh đề. Hay nói một cách khác là mệnh đề khơng cĩ cấu trúc. 10/11/2009 Nhập mơn Trí tuệ nhân tạo 43
44. Logic vị từ • Vị từ là một phát biểu đề cập tới các phần tử thuộc những phạm vi nhất định và chân 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ố” “m là ước số của n” 10/11/2009 Nhập mơn Trí tuệ nhân tạo 44
45. Logic vị từ • Về mặt tốn học vị từ là hàm lấy giá trị logic phụ thuộc bao gờm tên và biến. • Kí hiệu: hàm bao gờm tên và biến – p(n)= “n là 1 số nguyên tố” – us(m,n)=“m là ước số của n” – Vi(Cam, ngọt)=”Vị cam là ngọt” – Mau(Cam, xanh)=”Cam co mau xanh” Vitu( , , , ); 10/11/2009 Nhập mơn Trí tuệ nhân tạo 45
46. Logic vị từ • Liên quan đến vị từ ta cũng có các phép tốn vị từ: , , , , . • Khi thực hiện các phép tốn trên vịt ừ ta được vị từ mới • Các lượng từ: , ,  10/11/2009 Nhập mơn Trí tuệ nhân tạo 46
47. Logic vị từ • Các phát biểu có lượng từ (các phát biểu lượng từ hóa) là phát biểu có lượng từ và có các vị từ theo các biến Vd: x,p(x) x, p(x) Vd: bất kỳ số nào cũng có số nguyên tố lớn hơn nĩ – p(y) = “y là số nguyên tố” – x N, y N, p(y)  (y>x) Hoặc có thể viết - x, y, p(y)  (y>x) 10/11/2009 Nhập mơn Trí tuệ nhân tạo 47
48. Logic vị từ Tri thức biễu diễn theo logic vị từ gờm 2 thành phần: – Tập các vị từ, trong đó mỡi vị từ đại diện cho một phát biểu – Tập các sự kiện và luật dưới dạng các biểu thức logic vị từ 10/11/2009 Nhập mơn Trí tuệ nhân tạo 48
49. Logic vị từ • Để biểu diễn tri thức theo logic vị từ ta thực hiện 2 giai đoạn sau: – Gđ1: Xác lập các vị từ cần thiết cho việc biễu diễn(mỡi vị từ phải có tên gọi, biến phải có kiểu xác đị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ừ 10/11/2009 Nhập mơn Trí tuệ nhân tạo 49
50. Logic vị từ • Vd: “A là bố của B nếu B là anh hoặc là em một người con của A ” Bo(A,B)= Z: Bo(A,Z)  (Anh(B,Z)  Anh (Z,B)) 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) c) Bố ("An", "Tú") sẽ có giá trị là đúng. (An là bố của Tú). 10/11/2009 Nhập mơn Trí tuệ nhân tạo 50
51. Logic vị từ • Vd: “Khơng có vật gì lớn nhất và khơng có vật gì nhỏ nhất” (x, y : LớnHơn(y,x) )  (x, y : LớnHơn(x,y) ) 10/11/2009 Nhập mơn Trí tuệ nhân tạo 51
52. Logic vị từ • Bất kì số tự nhiên nào cũng là ước số của chính nó • 1 là ước của mọi số tựnhiên • Mọi số tự nhiên đều là ước số của 0 • 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ì a là ước số của c. • USCLN của 1 số a tùy ý và 0 là bằng a. 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 là uscln của a và b Với a <b, ta có uscln của b-a và a cũng chính là uscln của a và b 10/11/2009 Nhập mơn Trí tuệ nhân tạo 52
53. • Us(a,b): a là ước của b • us(a,a) • Us(1,a) • Us(a,0) • Us(a,b) và us(b,c) us(a,c) 10/11/2009 Nhập mơn Trí tuệ nhân tạo 53
54. • Uscln(a,b,d) • Uscln(a,0,a) • Uscln(0,a,a) • (a>b) và uscln(a-b,b,d)  uscln(a,b,d) 10/11/2009 Nhập mơn Trí tuệ nhân tạo 54
55. Logic vị từ • Thuật tốn hợp giải • Ngơn ngữ Prolog 10/11/2009 Nhập mơn Trí tuệ nhân tạo 55
56. Mạng ngữ nghĩa 10/11/2009 Nhập mơn Trí tuệ nhân tạo 56
57. Mạng ngữ nghĩa 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 các yếu tố của tri thức 10/11/2009 Nhập mơn Trí tuệ nhân tạo 57
58. cánh cĩ Sẻ là Chim di chuyển bay Một số tri thức về lồi “chim sẻ” được biểu diễn trên mạng ngữ nghĩa 10/11/2009 Nhập mơn Trí tuệ nhân tạo 58
59. Mạng ngữ nghĩa 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 Chích Hót là biết Chim có cánh chòe Chim Chim sống trong tổ có là Tổ Cánh m Các mối quan hệ này sẽ được biểu diễn trực quan bằng một đồ thị bên trên 10/11/2009 Nhập mơn Trí tuệ nhân tạo 59
60. Mạng ngữ nghĩa • Ví dụ 2: Bài tốn tam giác tởng quát • Một số bài tốn thơng thường về tam giác như: “Cho 3 cạnh của một 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 các đường trung tuyến”, • 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 tốn tam giác dạng này ? Câu trả lời là có. • Bài tố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 tố trong đó có yếu tố cạnh • Sử dụng khoảng200 đỉnh để chứa cơng thức + 22 đỉnh để chứa các yếu tố của tam giác. 10/11/2009 Nhập mơn Trí tuệ nhân tạo 60
61. Phép lan truyền kích hoạt Vấn đề: Trên mạng ngữ nghĩa có một số đỉnh được cho trước. Ta muốn đạt đến 1(nhiều) đỉnh mục tiêu. Đỉnh kích hoạt: đỉnh đã biết 10/11/2009 Nhập mơn Trí tuệ nhân tạo 61
62. Phép lan truyền kích hoạt Bước1: Kích hoạt các đỉnh được cho trước Bước 2: while (chưa đạt tới mục tiêu) { 2.1 Tìm đỉnh để có thể truyền kích hoạt tới 2.2 if(tìm khơng được) KL: khơng tìm thấy mục tiêu 2.3 else kích hoạt đỉnh mới } 10/11/2009 Nhập mơn Trí tuệ nhân tạo 62
63. Bài tốn tam giác • Mạng ngữ nghĩa cho bài tốn có cấu trúc như sau • Đỉnh của đờ thị bao gờm2 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ố tam giác (ký hiệu bằng hình trịn) • 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 • Lưu ý: Trong một cơng thức liên hệ giữa n yếu tố của 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 10/11/2009 Nhập mơn Trí tuệ nhân tạo 63
64. Bài tốn tam giác • Ví dụ: Cho hai gĩc A, B và chiều dài cạnh a của tam giác. Tính chiều dài đường cao hc . Với mạng ngữ nghĩa đã cho trong hình trên. Các bước thi hành của thuật tốn như sau: 10/11/2009 Nhập mơn Trí tuệ nhân tạo 64
65. Bài tốn tam giác f1 :0 A B C ab f : 2 sin(AB ) sin( ) cb f : 3 sin(CB ) sin( ) f4 : S p ( p a )( p b )( p c ) hc fS: c 5 2 10/11/2009 Nhập mơn Trí tuệ nhân tạo 65
66. A+ B + C - = 0 (4) A B C a b c b (1) (2) sinA sinB sinC sinB c a b hc (3) S p p-a p- b p-c S – ½ hc.c = 0 (5) S 10/11/2009 Nhập mơn Trí tuệ nhân tạo 66
67. • Thuật giải lan truyền kích hoạt • 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). 10/11/2009 Nhập mơn Trí tuệ nhân tạo 67
68. • Kích hoạt: Yếu tớ: đã biết do giả thiết hay do tính từ cơng thức Cơng thức: Cơng thức áp dụng được để tạo yếu tố mới 10/11/2009 Nhập mơn Trí tuệ nhân tạo 68
69. • Quy tắc lan truyền Đới với cơng thức: cơng thức được áp dụng khi trong số các yếu tố liên hệ với cơng thức có đúng một yếu tố chưa biết. Đớ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ố đó 10/11/2009 Nhập mơn Trí tuệ nhân tạo 69
70. A+ B + C - = 0 (4) A B C a b c b (1) (2) sinA sinB sinC sinB c a b hc (3) S p p-a p- b p-c S – ½ hc.c = 0 (5) S 10/11/2009 Nhập mơn Trí tuệ nhân tạo 70
71. A+ B + C - = 0 (4) A B C a b c b (1) (2) sinA sinB sinC sinB c a b hc (3) S p p-a p- b p-c S – ½ hc.c = 0 (5) S 10/11/2009 Nhập mơn Trí tuệ nhân tạo 71
72. A+ B + C - = 0 (4) A B C a b c b (1) (2) sinA sinB sinC sinB c a b hc (3) S p p-a p- b p-c S – ½ hc.c = 0 (5) S 10/11/2009 Nhập mơn Trí tuệ nhân tạo 72
73. A+ B + C - = 0 (4) A B C a b c b (1) (2) sinA sinB sinC sinB cc a b hc (3) S p p-a p- b p-c S – ½ hc.c = 0 (5) S 10/11/2009 Nhập mơn Trí tuệ nhân tạo 73
74. A+ B + C - = 0 (4) A B C a b c b (1) (2) sinA sinB sinC sinB c a b hc (3) S p p-a p- b p-c S – ½ hc.c = 0 (5) S 10/11/2009 Nhập mơn Trí tuệ nhân tạo 74
75. • Giả thiết: a=5, b=4, A=Pi/2 • Mục tiêu: S • Kết quả: S=6 10/11/2009 Nhập mơn Trí tuệ nhân tạo 75
76. Cấu trúc dữ liệu biểu diễn mạng ngữ nghĩa • Biễn diễn đờ thị dưới dạng ma trận • Biễn diễn đờ thị dưới dạng danh sách 10/11/2009 Nhập mơn Trí tuệ nhân tạo 76
77. • E = tập các yếu tố liệt kê theo thứ tự = {a,b,c,A,B,C,S,R,p } • F = tập các cơng thức ab f: A B C ; f : = 12 sin(AB ) sin( ) Giả sử có m cơng thức, n yếu tố r là ma trận cấp mxn 1 nếu fi có quan hệ với yếu tố j R[ i ][ j ] 0 10/11/2009 Nhập mơn Trí tuệ nhân tạo 77
78. U U2 RPPI 2R P=UI I R 10/11/2009 Nhập mơn Trí tuệ nhân tạo 78
79. Gà Hót biết là là Chích chòe Chim có làm Tổ Cánh 10/11/2009 Nhập mơn Trí tuệ nhân tạo 79
80. Hệ luật dẫn 10/11/2009 Nhập mơn Trí tuệ nhân tạo 80
81. Hệ luật dẫn • Luật dẫn? • Luật dẫn là phát biểu dưới dạng if p1, p2, , pm then q1, q2, , qn pi là các sựki ện giả thiết qj là các sự kiện kết luận p1, p2, , pm q1, q2, , qn 10/11/2009 Nhập mơn Trí tuệ nhân tạo 81
82. Nếu 2 tam giác cĩ 3 cạnh tương ứng bằng nhau thì bằng nhau Biểu diễn:1 T : tam giác T2: tam giác If T1.a=T2.a, T1.b=T2.b, T1.c=T2.c then T1=T2 10/11/2009 Nhập mơn Trí tuệ nhân tạo 82
83. • Mỡi phản ứng hóa học có thể xem là một luật dẫn HCl + NaOH NaCl +H2O Biễu diễn HCl, NaOH NaCl, H2O 10/11/2009 Nhập mơn Trí tuệ nhân tạo 83
84. Mơ hình hệ luật dẫn • Hệ luật dẫn là tri thức gờm một tập các luật trên tập sựki ện • Hệ luật dẫn gờm 2 thành phần chính: (F,R) • F=tập sự kiện • R=tập luật dẫn, mỡi luật có dạng A B Thường tởch ức hệ luật dẫn với vế phải chỉ là 1 sựki ện 10/11/2009 Nhập mơn Trí tuệ nhân tạo 84
85. Ví dụ • Biễu diễn quan hệ dẫn xuất giữa các yếu tố trong tam giác • Biễu diễn phản ứng hóa học dưới dạng luật dẫn 10/11/2009 Nhập mơn Trí tuệ nhân tạo 85
86. f1 :0 A B C ab f : 2 sin(AB ) sin( ) cb f : 3 sin(CB ) sin( ) f4 : S p ( p a )( p b )( p c ) hc fS: c 5 2 10/11/2009 Nhập mơn Trí tuệ nhân tạo 86
87. Kỹ thuật suy diễn trên hệ luật dẫn Vấn đề: trên một tri thức dạng hệ luật dẫn(F,R), giả sửcho trước tập sựki ện GT G và có 1 tập sự kiện mục tiêu KL K mà ta muốn đạt được. Hãy tìm một quá trình áp dụng các luật dẫn để từ GT G suy ra KL K 10/11/2009 Nhập mơn Trí tuệ nhân tạo 87
88. Ví dụ Cho một cơ sở tri thức • r1: A, B C • r2: C, D E • r3: F, B G • r4: A, E H • r5: F E • r6: B, E G Với các sự kiện B đúng, D, đúng. Hãy trình bày quá trình lập luận tiến và lập luận lùi để biết G đúng hay sai. 10/11/2009 Nhập mơn Trí tuệ nhân tạo 88
89. • Ví dụ: F = {a,b,c, A, B, C } R={A,B C, } • Bài tốn GT = {a,b,A} KL={S,R} 10/11/2009 Nhập mơn Trí tuệ nhân tạo 89
90. • 2 kỹ thuật suy diễn cơ bản là: Suy diễn tiến Suy diễn lùi 10/11/2009 Nhập mơn Trí tuệ nhân tạo 90
91. Suy diễn tiến • Là quá trình suy diễn đi từ giả thiết đến kết luận thơng qua việc áp dụng các định luật, định lý. • Quá trình này trải qua nhiều bước suy luân xuất phát từ giả thiết ban đầu để sinh ra những sự kiện mới cho tới khi đạt được mục tiêu hay tới khi khơng tìm được luật nào áp dụng được để sinh ra sự kiện mới. 10/11/2009 Nhập mơn Trí tuệ nhân tạo 91
92. Thuật giải suy diễn tiến • Bước 1: Đặt A là tập sư kiện đang có. A=GT • Bước 2: while(mục tiêu chưa thuộc A) { } • Bước 3: Kết luận: tìm được mục tiêu 10/11/2009 Nhập mơn Trí tuệ nhân tạo 92
93. Bước 2: while(mục tiêu chưa thuộc A) { Tìm kiếm luật r để áp dụng sinh ra sụ kiện mới if( khong tim duoc luật) Dừng, kết luận khơng giải được else Ghi nhận r đã được sử dụng Bở sung sự kiến mới tìm được vào A } 10/11/2009 Nhập mơn Trí tuệ nhân tạo 93
94. Suy diễn lùi • Là phép suy luận truy ngược đi từ mục tiêu trở về giả thiết • Xuất phát từ mục tiêu ta xem xét hệ luật để tìm xem những sụ kiện nào có thể dẫn ra được mục tiêu và sự kiện này sẽ được xem xét như là mục tiếu mới cho các bước truy ngược tiếp theo. • Quá trình này kết thúc khi tất cả các mục tiêu phát sinh đầu đã được biết hay thuộc giả thiết. 10/11/2009 Nhập mơn Trí tuệ nhân tạo 94
95. • Quá trình suy diễn ngược này này sẽ phát sinh ra 1 sơ đờ cây AND/OR các mục tiêu nên việc cài đặt khá phức tạp. 10/11/2009 Nhập mơn Trí tuệ nhân tạo 95
96. Cài đặt class Luat { public: sets gt; sets kl; int dsd; Luat(); friend ostream & operator <<(ostream &o,Luat &L); }; 10/11/2009 Nhập mơn Trí tuệ nhân tạo 96
97. sets Tapsukien; Luat Tapluat[50]; int soluat; sets GT; sets KL; 10/11/2009 Nhập mơn Trí tuệ nhân tạo 97
98. • void khoitao(); • void nhaplieu(); • int timluat(); • void Giaitoan(); 10/11/2009 Nhập mơn Trí tuệ nhân tạo 98
99. void main() { clrscr(); init(); input(); Giaitoan(); getch(); } 10/11/2009 Nhập mơn Trí tuệ nhân tạo 99
100. void Giaitoan() { int i; while(!in(GT,KL) && (i=timluat())>-1) { if(!in(GT,Tapluat[i].kl)) { GT.insert(Tapluat[i].kl); Tapluat[i].dsd=1; } else Tapluat[i].dsd=1; } if(!in(GT,KL)) cout<<"Khong giai duoc"; else cout<<"Thanh cong"; } 10/11/2009 Nhập mơn Trí tuệ nhân tạo 100
101. void Giaitoan() { int i,buoc; buoc=0; while(!in(GT,KL) && (i=timluat())>-1) { if(!in(GT,Tapluat[i].kl)) { GT.insert(Tapluat[i].kl); Tapluat[i].dsd=1; buoc++; cout<<"Buoc "<<buoc<<" :\n"; cout<<" Gia thiet: "<<GT; cout<<"\n Do :"<<Tapluat[i]<<"\n"; // getch(); } else Tapluat[i].dsd=1; } if(!in(GT,KL)) cout<<"Khong giai duoc"; else cout<<"Thanh cong"; } 10/11/2009 Nhập mơn Trí tuệ nhân tạo 101
102. int timluat() { for(int i=0;i<soluat;i++) { if(Tapluat[i].dsd==0 && in(GT,Tapluat[i].gt)) return i; } return -1; } 10/11/2009 Nhập mơn Trí tuệ nhân tạo 102
103. Mạng ngữ nghĩa class yeuto{ char s[3]; public: yeuto(){s[0]='\0';}; yeuto(char *s1){strcpy(s,s1);}; void set(char *s1){strcpy(s,s1);}; friend istream & operator >>(istream &i,yeuto &yt); friend ostream & operator <<(ostream &o,yeuto &yt); friend int operator ==(yeuto yt1,yeuto yt2); }; 10/11/2009 Nhập mơn Trí tuệ nhân tạo 103
104. class congthuc{ char s[30]; public: congthuc(){s[0]='\0';}; void set(char *s1){strcpy(s,s1);}; congthuc(char *s1){strcpy(s,s1);}; friend ostream & operator <<(ostream &o,congthuc &ct); }; 10/11/2009 Nhập mơn Trí tuệ nhân tạo 104
105. yeuto ytGoc[12]; int nGoc; congthuc ctGoc[30]; int mGoc; yeuto giathiet[12]; float gt[12]; int ngt; int R[30][12]; 10/11/2009 Nhập mơn Trí tuệ nhân tạo 105
106. void khoitao(); void input(); void Giaitoan(); void output(); int vitri(yeuto y); int timcongthuc(); float tinhtheocongthuc(int i, int vt); float congthuc0(int vt); float congthuc1(int vt); float congthuc2(int vt); float congthuc3(int vt); float congthuc4(int vt); float congthuc5(int vt); 10/11/2009 Nhập mơn Trí tuệ nhân tạo 106
107. void main() { clrscr(); khoitao(); input(); Giaitoan(); getch(); } 10/11/2009 Nhập mơn Trí tuệ nhân tạo 107
108. int timcongthuc(int &vt) { int i,j,dem; for(i=0;i<mGoc;i++) { dem=0; for(int j=0;j<nGoc;j++) if(R[i][j]==-1) {dem++;vt=j;} if(dem==1) return i; } return -1; } 10/11/2009 Nhập mơn Trí tuệ nhân tạo 108
109. void Giaitoan() { int i,vt,buoc=0; while(!giaihet() &&((i=timcongthuc(vt))>-1)) { gt[vt]=tinhtheocongthuc(i,vt); for(int j=0;j<mGoc;j++) if(R[j][vt]==-1) R[j][vt]=1; buoc++; cout<<"Buoc "<<buoc<<":\n"; cout<<"\tTinh duoc "<<ytGoc[vt]<<"="<<gt[vt]<<"\n"; cout<<"\tdo cong thuc "<<ctGoc[i]<<"\n"; }; if(giaihet()) cout<<"thanh cong"; else cout<<"thatbai"; } 10/11/2009 Nhập mơn Trí tuệ nhân tạo 109