Bài giảng Biểu diễn tri thức và giải toán tự động - Hoàng Kiếm

Nội dung text: Bài giảng Biểu diễn tri thức và giải toán tự động - Hoàng Kiếm

1. BIỂU DIỄN TRI THỨC VÀ GIẢI TOÁN TỰ ĐỘNG Hoàng Kiếm Đỗ Văn Nhơn Đại Học Quốc Gia TP.HCM - 2001
2. NỘI DUNG: ª Tổng quan về biểu diễn tri thức và giải toán dựa trên tri thức. ª Mạng suy diễn và tính toán ª Mô hình tri thức các đối tượng tính toán. Đại Học Quốc Gia TP.HCM - 2001
3. PHẦN 1. TỔNG QUAN I. Khái niệm về Tri thức và biểu diễn tri thức. II. Cấu trúc của một hệ giải bài toán dựa trên tri thức. III. Các phương pháp biểu diễn tri thức. IV. Suy diễn tự động. V. Giới thiệu và nhận định một số công trình nghiên cứu. Đại Học Quốc Gia TP.HCM - 2001
4. I. TRI THỨC VÀ BIỂU DIỄN TRI THỨC 1.1 Khái niệm tri thức 1.2 Khái niệm về biểu diễn tri thức 1.3 Các dạng tri thức Đại Học Quốc Gia TP.HCM - 2001
5. 1.1 Khái niệm tri thức ° Tri thức không có được định nghĩa chính xác ° Khái niệm: Tri thức (knowledge) là sự hiểu biết về một lĩnh vực của chủ đề. ° Lĩnh vực: miền chủ đề được chú trọng. ª Tri thức thuờng bao gồm các khái niệm, các loại sự kiện, các luật, Đại Học Quốc Gia TP.HCM - 2001
6. Ví dụ: 1. Kiến thức về một lĩnh vực y học và khả năng chẩn đoán bệnh là tri thức. 2. Biết một tam giác có các yếu tố nào cùng với các công thức liên hệ giữa các yếu tố là tri thức. 3. Biết các dạng cấu trúc dữ liệu thường dùng trong lập trình cùng với các thuật toán xử lý cơ bản trên các cấu trúc là tri thức. Đại Học Quốc Gia TP.HCM - 2001
7. 1.2 Khái niệm về biểu diễn tri thức ° Biểu diễn tri thức (Knowledge Representation) là sự diễn đạt và thể hiện của tri thức dưới những dạng thích hợp để có thể tổ chức một cơ sở tri thức của hệ thống. ° Tại sao phải biểu diễn tri thức? Biểu diễn tri thức giúp có thể tổ chức và cài đặt một cơ sở tri thức cho các hệ chuyên gia, các hệ cở sở tri thức và các hệ giải bài toán dựa trên tri thức. Đại Học Quốc Gia TP.HCM - 2001
8. Công cụ cho việc biểu diễn tri thức ° Các cấu trúc dữ liệu cơ bản: dãy, danh sách, tập hợp, mẫu, ° Các cấu trúc dữ liệu trừu tượng: ngăn xếp, hàng đợi. ° Các mô hình toán học: đồ thị, cây. ° Các mô hình đối tượng. ° Các ngôn ngữ đặc tả tri thức. Đại Học Quốc Gia TP.HCM - 2001
9. Ví dụ: Kiến thức về một tam giác cần thiết cho việc giải bài toán tam giác có thể được biểu diễn gồm: ° Một tập hợp các biến thực, mỗi biến đại diện cho một yếu tố của tam giác. ° Một tập hợp các công thức liên hệ tính toán trên các yếu tố của tam giác. Đại Học Quốc Gia TP.HCM - 2001
10. Tập các biến trong tam giác gồm: a, b, c : 3 cạnh của tam giác. , , : 3 góc đối diện với 3 cạnh tương ứng trong tam giác. ha, hb, hc : 3 đường cao tương ứng với 3 cạnh của tam giác. S : diện tích tam giác. p : nửa chu vi của tam giác. R : bán kính đường tròn ngoại tiếp tam giác. v.v Đại Học Quốc Gia TP.HCM - 2001
11. Tập các công thức trong tam giác gồm: „ f1 : + + = (radian). 2 2 2 „ f2 : a = b + c - 2.b.c.cos 2 2 2 „ f3 : b = a + c - 2.a.c.cos 2 2 2 „ f4 : c = a + b - 2.a.b.cos „ f5 : a / sin = b / sin „ v.v Đại Học Quốc Gia TP.HCM - 2001
12. 1.3 Các dạng tri thức ° Tri thức mô tả: các khái niệm, các đối tượng cơ bản. ° Tri thức cấu trúc: các khái niệm cấu trúc, các quan hệ, các đối tượng phức hợp, ° Tri thức thủ tục: các luật dẫn, các thủ tục xử lý, các chiến lược, ° Tri thức meta: tri thức về các dạng tri thức khác và cách sử dụng chúng. Đại Học Quốc Gia TP.HCM - 2001
13. II. CẤU TRÚC CỦA HỆ GIẢI TOÁN DỰA TRÊN TRI THỨC 2.1 Cấu trúc hệ thống 2.2 Vấn đề biểu diễn tri thức 2.3 Vấn đề suy diễn tự động Đại Học Quốc Gia TP.HCM - 2001
14. 2.1 Cấu Trúc Hệ Thống Cấu trúc của một hệ giải toán thông minh Đại Học Quốc Gia TP.HCM - 2001
15. Các thành phần chính của hệ thống trong việc giải toán: Hệ giải toán thông minh có thể giải được các dạng bài toán tổng quát trong một miền tri thức. ° Cơ sở tri thức (Knowledge Base). Đây là trái tim của hệ thống, trong đó chứa các kiến thức cần thiết cho việc giải các bài toán. ° Bộ suy diễn (hay mô tơ suy diễn). Bộ suy diễn sẽ áp dụng kiến thức được lưu trữ trong cơ sở tri thức để giải quyết hay tìm lời giải cho các bài toán đặt ra. Đại Học Quốc Gia TP.HCM - 2001
16. Sự tách biệt của bộ suy diễn và cơ sở tri thức là một tiêu chuẩn quan trọng. Sự tách biệt: tính độc lập tương đối giữa cơ sở tri thức và bộ suy diễn. Cần có sự tách biệt này vì: 1. Việc biểu diễn tri thức sẽ được thực hiện một cách tự nhiên hơn, gần gũi hơn với quan niệm của con người. 2. Các nhà thiết kế hệ thống sẽ tập trung vào vệc nắm bắt và tổ chức cơ sở tri thức hơn là phải đi vào những chi tiết cho việc cài đặt trên máy tính. Đại Học Quốc Gia TP.HCM - 2001
17. 3. Giúp tăng cường tính mô-đun hóa của phần cơ sở tri thức, bộ suy diễn và bộ phận cập nhật, hiệu chỉnh kiến thức. Sự bổ sung hay loại bỏ bớt một phần kiến thức sẽ không gây ra những hiệu ứng lề cho các thành phần khác trong hệ thống. 4. Cho phép cùng một chiến lược điều khiển và giao tiếp có thể được sử dụng cho nhiều hệ thống khác nhau. 5. Sự tách biệt của kiến thức giải bài toán và bộ suy diễn còn giúp ta có thể thử nghiệm nhiều chiến lượt điều khiển khác nhau trên cùng một cơ sở tri thức. Đại Học Quốc Gia TP.HCM - 2001
18. 2.2 Vấn đề biểu diễn tri thức ° Biểu diễn tri thức đóng vai trò rất quan trọng trong thiết kế và xây dựng một hệ giải bài toán thông minh và các hệ chuyên gia. ° Phương pháp biểu diễn tri thức thích hợp sẽ tạo nên một hệ thống có trái tim khỏe mạnh. ° Xây dựng và phát triển các phương pháp biểu diễn tri thức là một hướng nghiên cứu quan trọng cho các nhà nghiên cứu về Trí tuệ Nhân tạo Đại Học Quốc Gia TP.HCM - 2001
19. 2.3 Vấn suy diễn tự động ° Suy diễn tự động để giải quyết các bài toán dựa trên tri thức cũng là một vấn đề quan trọng. ° Các phương pháp suy diễn tự động nhằm vận dụng kiến thức đã biết trong quá trính lập luận giải quyết vấn đề trong đó quan trọng nhất là các chiến lược điều khiển giúp phát sinh những sự kiện mới từ các sự kiện đã có. „ Xây dựng và phát triển các phương pháp biểu diễn tri thức là một hướng nghiên cứu quan trọng cho các nhà nghiên cứu về Trí tuệ Nhân tạo Đại Học Quốc Gia TP.HCM - 2001
20. III. CÁC PHƯƠNG PHÁP BIỂU DIỄN TRI THỨC 3.1 Biểu diễn dựa trên logic hình thức 3.2 Hệ luật dẫn 3.3 Mạng ngữ nghĩa 3.4 Các khung (frame) Đại Học Quốc Gia TP.HCM - 2001
21. 3.1 Logic hình thức ° Sử dụng các biểu thức logic hình thức trong một hệ thống logic để diễn đạt các sự kiện và các luật trong cơ sở tri thức. ° Phép tính logic vị từ cấp 1 được sử dụng phổ biến nhất và có cả một ngôn ngữ lập trình hỗ trợ cho phương pháp này. Đó là ngôn ngữ lập trình PROLOG. ° Trong ngôn ngữ PROLOG, chỉ cần khai báo các sự kiện và các luật. Hệ thống sẽ thức hiện giải quyết vấn đề được yêu cầu dựa trên tri thức được khai báo. Đại Học Quốc Gia TP.HCM - 2001
22. 3.2 Hệ luật dẫn ° Mỗi luật dẫn được phát biểu dưới dạng: if then ° Mô hình: Một cách hình thức, hệ luật dẫn gồm 1) Tập ký hiệu đại diện cho các sự kiện. 2) tập luật dẫn trong đó và là các tập hợp sự kiện ° Nhận xét: Mô hình hệ luật dẫn trên khó áp dụng trực tiếp vì quan niệm sự kiện khá đơn giản. Đại Học Quốc Gia TP.HCM - 2001
23. 3.3 Mạng ngữ nghĩa ° Mạng ngữ nghĩa (semantic network) có dạng một đồ thị gồm các nút và các cung, trong đó - Các nút thể hiện các khái niệm, các đối tượng. - Các cung thể hiện các quan hệ giữa các đối tượng. ° Dựa trên mạng ngữ nghĩa ta nhận biết tri thức một cách trực quan giúp thiết kế các xử lý như: thêm/bớt các khái niệm hay các đối tượng, tìm kiếm thông tin. ° Nhận xét: Mô hình khá trừu tượng và khái quát, trong áp dụng phải phát triển các mô hình tri thức cụ thể hơn. Đại Học Quốc Gia TP.HCM - 2001
24. 3.4 Các khung ° Các khung (frame) thể hiện các khái niệm dưới dạng cấu trúc mẫu tin và có hình thức như một bảng mẫu. ° Khung cơ bản: gồm các thành phần cơ bản sau - Tên đối tượng (loại khung). - Các thuộc tính. - Giá trị của các thuộc tính. ° Khung lớp: thể hiện các tính chất tổng quát của một lớp các đối tượng, với những quan hệ kế thừa và cấu trúc phân cấp. Đại Học Quốc Gia TP.HCM - 2001
25. IV. SUY DIỄN TỰ ĐỘNG 4.1 Khái niệm 4.2 Hợp giải trong tri thức dạng logic 4.3 Suy diễntiến 4.4 Suy diễn lùi 4.5 Suy diễn hỗn hợp Đại Học Quốc Gia TP.HCM - 2001
26. 4.1 Khái niệm suy diễn tự động ° Suy diễn nhằm vận dụng kiến thức đã biết trong quá trính lập luận giải quyết vấn đề trong đó quan trọng nhất là các chiến lược điều khiển giúp phát sinh những sự kiện mới từ các sự kiện đã có. ° Suy diễn tự động: Quá trình suy diễn được thuật giải hóa và có thể cài đặt thành chương trình máy tính. ° Các kỹ thuật suy diễn cơ bản: - Suy diễn tiến. - Suy diễn lùi. Đại Học Quốc Gia TP.HCM - 2001
27. 4.2 Hợp giải trong tri thức dang logic ° Phương pháp: Thực hiện quá trình phát sinh sự kiện mới bằng cách sử dụng các luật suy diễn cơ bản trên các biểu thức logic như: Modus Ponens, Modus Tollens, tam đoạn luận ° Trong logic vị từ: Quá trình hợp giải có thể được cài đặt dựa trên kỹ thuật hợp nhất (unification) và quay lui (backtracking). ° PROLOG là một ngôn ngữ lập trình được thiết kế với chức năng suy diễn theo phương pháp này. Đại Học Quốc Gia TP.HCM - 2001
28. 4.3 Suy diễn tiến ° Phương pháp: Suy dẫn từ giả thiết đi đến kết luận. Chiến lược này được bắt đầu bằng tập sự kiện đã biết, rút ra các sự kiện mới nhờ dùng các luật mà phần giả thiết khớp với sự kiện đã biết, và tiếp tục quá trình này cho đến khi thấy trạng thái đích, hoặc cho đến khi không còn luật nào khớp được các sự kiện đã biết hay được sự kiện suy luận ° Trong áp dụng cụ thể phương pháp thường sử dụng kết hợp với các qui tắc heuristic trong việc chọn luật. Đại Học Quốc Gia TP.HCM - 2001
29. 4.4 Suy diễn lùi ° Phương pháp: Truy ngược từ kết luận trở về giả thiết. Phương pháp này được tiến hành bằng cách truy ngược từ mục tiêu cần đạt được trở về phần giả thiết của bài toán bằng cách áp dụng các luật trong cơ sở tri thức. ° Quá trình suy diễn lùi này sẽ phát sinh một sơ đồ cây mục tiêu kèm theo một cơ chế quay lui và lời giải sẽ được tìm thấy khi tất cả các mục tiêu ở các nút lá của cây mục tiêu đều thuộc về những sự kiện đã biết ° Trong áp dụng cụ thể phương pháp thường sử dụng kết hợp với các qui tắc heuristic trong việc chọn luật. Đại Học Quốc Gia TP.HCM - 2001
30. 4.5 Suy diễn hỗn hợp ° Phương pháp: Kết hợp 2 quá trình suy diễn tiến và suy diễn lùi nhằm khắc phục khuyết điểm của mỗi phương pháp và nâng cao hiệu quả của quá trình suy diễn trong áp dụng cụ thể. ° Nhược điểm của suy diễn tiến: Không cảm nhận được sự gần tới đích. ° Nhược điểm của suy diễn lùi: thường dẫn tới sự phân nhánh lớn và không cảm nhận được sự cần chuyển hướng dòng suy nghĩ. Đại Học Quốc Gia TP.HCM - 2001
31. V. GIỚI THIỆU, NHẬN ĐỊNH MỘT SỐ CÔNG TRÌNH NGHIÊN CỨU. 5.1 Các phương pháp biểu diễn tri thức 5.2 Một số lý thuyết về chứng minh tự động 5.3 Phương pháp Wu 5.4 Một số phương pháp chứng minh định lý hình học. Đại Học Quốc Gia TP.HCM - 2001
32. 5.5 Một số nghiên cứu xây dựng hệ giải toán hình học. 5.6 Một số phần mềm ứng dụng về giải toán trên máy tính 5.7 Phầm mềm MAPLE Đại Học Quốc Gia TP.HCM - 2001
33. 5.1 Các phương pháp biểu diễn tri thức ° Các phương pháp chung: các phương pháp biểu diễn theo logic hình thức, các phương pháp biểu diễn thủ tục, các phương pháp biểu diễn dạng mạng và các phương pháp biểu diễn cấu trúc ° Ưu điểm của mỗi phương pháp: thích hợp cho việc biểu diễn từng dạng tri thức riêng lẻ. ° Nhược điểm chung: chỉ biểu diễn được một khía cạnh của tri thức đa dạng và chưa hướng tới một mô hình tri thức bao hàm nhiều dạng thông tin và nhiều dạng sự kiện khác nhau. Đại Học Quốc Gia TP.HCM - 2001
34. 5.2 Một số lý thuyết về chứng minh tự động ° Phương pháp hình thức: xây dựng các hệ thống logic khác nhau bao gồm tập ký hiệu, cú pháp của công thức hình thức, ngữ nghĩa và hệ luật trên các công thức. ° Ưu điểm: Tính chặc chẽ cao, khá đơn giản với sô luật không nhiều. ° Nhược điểm: Trừu tượng và không thich hợp cho nhiều ứng dụng cụ thể như hệ giải bài toán hình học, các hệ chuyên gia ứng dụng. Đại Học Quốc Gia TP.HCM - 2001
35. 5.3 Phương pháp Wu ° Phương pháp Wu là một phương pháp biểu diễn và chứng minh định lý hình học theo cách tiếp cận đại số: biểu diễn các sự kiện dựa trên các đa thức và các tính toán trên tập nghiệm của các đa thức. ° Ưu điểm: Phương pháp nầy cho ta một biểu diễn khá đẹp về mặt lý thuyết toán học. Đại Học Quốc Gia TP.HCM - 2001
36. ° Nhược điểm: (1) thực hiện thiết kế một thuật toán thực hành tính toán trên máy tính một cách hiệu quả rất khó. (2) Không thể làm cơ sở hay công cụ cho việc thiết kế một cách hệ thống một chương trình giải toán dựa trên tri thức, đặc biệt là chương trình cho lời giải tường minh phù hợp với việc học và dạy toán hình học. (3) Có những quan hệ trên các yếu tố hình học không thể diễn đạt bởi các đa thức. Đại Học Quốc Gia TP.HCM - 2001
37. 5.4 Một số phương pháp chứng minh định lý hình học ° Phương pháp diện tích chủ yếu tập trung vào sự thẳng hàng và sự song song. ° Phương pháp hiệu Pythagoras (Pythagoras Difference) tập trung vào khảo sát sự vuông góc của đường thẳng và đường tròn. Hiệu Pythagoras còn có thể được sử dụng để khảo sát sự song song và có liên quan đến phương pháp diện tích. Đại Học Quốc Gia TP.HCM - 2001
38. ° Phương pháp “full angle”:đề xuất một khái niệm hình thức liên quan đến góc “full angle” và thực hiện một số chứng minh tự động dựa trên khái niệm nầy. ° Phương pháp “thể tích” và phương pháp hiệu Pythagoras cho không gian. ° Phương pháp vector sử dụng đại số tuyến tính và lý thuyết về không gian vector trong chứng minh định lý hình học. Đại Học Quốc Gia TP.HCM - 2001
39. Nhận định: ° Các phương pháp nầy đều tập trung vào việc tìm ra các đặc trưng về mặt toán học nhất là các lý thuyết đại số trừu tượng cho từng khía cạnh liện hệ thể hiện một loại sự kiện hình học nhất định để dựa vào đó thực hiện các chứng minh tự động. ° Các phương pháp trở nên nặng nề về tính toán toán học trừu tượng và khó cài đặt trên máy tính. ° Hạn chế chủ yếu: không cho được những mô hình biểu diễn tri thức thích hợp cho việc xây dựng một cơ sở tri thức, bộ suy diễn và các thành phần khác của hệ thống. Đại Học Quốc Gia TP.HCM - 2001
40. 5.5 Một số nghiên cứu xây dựng hệ giải toán hình học ° “Xây dựng Hệ Giải Toán Hình học Phẳng”, Luận Văn Thạc Sĩ nặm 2000 của Lê Phấn Ninh. ° “Xây Dựng Hệ Chứng minh Hình học”, Luận Văn Thạc Sĩ nặm 1999 của Trần Xuân Phương. Đại Học Quốc Gia TP.HCM - 2001
41. Nhận định chung: ° Các tác giả chưa có một mô hình biểu diễn tri thức cho khái niệm “đối tượng” có thể sử dụng trong biểu diễn kiến thức hình học và chưa xem xét đầy đủ đến vấn đề tính toán. ° Chưa xây dựng mô hình biểu diễn tri thức chung cho việc xây dựng một cơ sở tri thức với một hệ thống khái niệm cơ bản cùng với các thông tin đa dạng kèm theo, các loại sự kiện và luật khác nhau trên các khái niệm. ° Chưa xây dựng một mô hình tổng quát cho các dạng bài toán hình học khác nhau. Đại Học Quốc Gia TP.HCM - 2001
42. 5.6 Một số phần mềm ứng dụng về giải toán trên máy tính ° Các chương trình tính toán hình học trong bộ phần mềm Engineering 2000 trong đó có chương trình Geometrix của ByteSize CD-ROM, Inc. ° Chương trình StudyWorks của MathSoft, Inc. ° Chương trình Math Express! của Aces Research, Inc. Đại Học Quốc Gia TP.HCM - 2001
43. Nhận định chung: ° Các chương trình chỉ thực hiện các tính toán dữ liệu số cụ thể dựa vào một vài khung (frames) dữ liệu đơn giản. ° Chưa có một cơ sở tri thức và một bộ giải bài toán dựa trên tri thức có thể giải các lớp bài toán tổng quát khác nhau. ° Chưa phải là một hệ giải toán dựa trên tri thức. Đại Học Quốc Gia TP.HCM - 2001
44. 5.7 Phần mềm MAPLE ° MAPLE là phần mềm đại số tính toán khá mạnh với phiên bản mới nhất là MAPLE 6.0. ° Chương trình không chỉ các tính toán số mà cả các tính toán ký hiệu (symbolic computation). Nó có một nhân tính toán rất mạnh và một hệ thống thư viện tính toán gồm nhiều gói chương trình (package) cho các phần tính toán toán học khác nhau như đại số tuyến tính, giải tích, hình học, số học, v.v ° Maple còn cho phép khả năng lập trình với các cấu trúc dữ liệu trừu tượng. Đại Học Quốc Gia TP.HCM - 2001
45. Nhận định chung: ° Tuy khả năng hỗ trợ tính toán và lập trình của Maple đạt đến trình độ rất cao nhưng chủ yếu là các thủ tục tính toán cho từng vấn đề đơn lẻ như giải một phương trình, tính đạo hàm của một hàm số, thức hiện các phép tính trên đa thức. ° Maple chưa thật sự cài đặt một cơ sở tri thức cho các phần toán học khác nhau với các bộ suy luận giải toán dựa trên tri thức. Đại Học Quốc Gia TP.HCM - 2001
46. TỔNG KẾT ° Trong cấu trúc của một hệ giải toán dựa trên tri thức, 2 thành phần trung tâm là cơ sở tri thức và bộ suy diễn dựa trên tri thức. ° Các phương pháp biểu diễn tri thức và suy diễn đã được nghiên cứu và đề xuất. Tuy nhiên mỗi phương pháp đều có những nhược điểm nhất định. ° Nhiều chương trình giải toán đã được xây dựng nhưng còn hạn chế như chưa dựa trên những mô hình tri thức thich hợp cho cơ sở tri thức. Đại Học Quốc Gia TP.HCM - 2001
47. Những Vấn đề được xem xét tiếp theo ° Xây dựng và phát triển một số mô hình biểu diễn tri thức và các thuật giải để giải tự động các dạng bài toán khác nhau dựa trên trí thức. ° Mạng suy diễn và tính toán. ° Mô hình tri thức về các đối tượng tính toán. Đại Học Quốc Gia TP.HCM - 2001