Bài giảng Trí tuệ nhân tạo - Nguyễn Cao Trí

202 trang hapham 650

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 Cao Trí", để 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:

bai_giang_tri_tue_nhan_tao_nguyen_cao_tri.ppt

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

TRÍ TUỆ NHÂN TẠO Artificial Intelligent Khoa Công Nghệ Thông Tin Đại Học Bách Khoa – Tp. HCM ThS Nguyễn Cao Trí – caotri@dit.hcmut.edu.vn KS Lê Thành Sách – ltsach@dit.hcmut.edu.vn Ñaïi Hoïc Baùch Khoa - Tp.HCM - Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Thaùng 6/2001
Nội dung môn học – Giới thiệu ⚫ Chương 1: Giới thiệu – Ngành Trí tuệ nhân tạo là gì? – Mục tiêu nghiên cứu của ngành Trí tuệ nhân tạo – Lịch sử hình thành và hiện trạng – Turing Test ⚫ Chương 2: Logic vị từ – Mệnh đề & logic vị từ – Logic vị từ dưới góc nhìn của AI Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 2
Nội dung môn học – Các kỹ thuật tìm kiếm ⚫ Chương 3:Tìm kiếm trên không gian trạng thái (State Space Search) – AI : Biểu diễn và tìm kiếm – Các giải thuật tìm kiếm trên không gian trạng thái – Depth first search (DFS) - Breath first search (BFS) ⚫ Chương 4:Tìm kiếm theo Heuristic – Heuristic là gì? – Tìm kiếm theo heuristic – Các giải thuật Best first search (BFS), Giải thuật A* – Chiến lược Minimax, Alpha Beta Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 3
Nội dung môn học – Kỹ thuật phát triển ứng dụng ⚫ Chương 5:Hệ luật sinh – Tìm kiếm đệ qui – Hệ luật sinh: Định nghĩa và ứng dụng – Tìm kiếm trên hệ luật sinh ⚫ Chương 6:Hệ chuyên gia – Giới thiệu về hệ chuyên gia – Mô hình hệ chuyên gia: dự trên luật, dựa trên frame – Phát triển một hệ chuyên gia ⚫ Chương 7:Biểu diển tri thức – Biểu diển tri thức trong AI: vai trò và ứng dụng – Các kỹ thuật biểu diển tri thức: semantic network, lưu đồ phụ thuộc khái niệm, frame, script Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 4
Thực hành &Tài liệu tham khảo ⚫ Thực hành Prolog và CLISP – Prolog : Các giải thuật tìm kiếm – CLISP : Biểu diển tri thức – Bài tập lớn ⚫ Tài liệu tham khảo – Bài giảng “Trí tuệ nhân tạo” – ThS Nguyễn Cao Trí – KS Lê Thành Sách – Artificial Inteligent – George F. Luget & Cilliam A. Stubblefied – Giáo trình “Trí tuệ nhân tạo” – KS Nguyễn Đức Cường – Trí tuệ nhận tạo – Nguyễn Quang Tuấn – Hà nội Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 5
Chương 1: GIỚI THIỆU ❖Ngành Trí tuệ nhân tạo là gì? ❖Mục tiêu nghiên cứu của ngành Trí tuệ nhân tạo ❖Lịch sử hình thành và hiện trạng ❖Turing Test ThS Nguyễn Cao Trí – caotri@dit.hcmut.edu.vn KS Lê Thành Sách – ltsach@dit.hcmut.edu.vn Ñaïi Hoïc Baùch Khoa - Tp.HCM - Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Thaùng 6/2001
Đối tượng nghiên cứu của AI ⚫ Đối tượng nghiên cứu của ngành AI AI là ngành nghiên cứu về các hành xử thông minh (intelligent behaviour) bao gồm: thu thập, lưu trữ tri thức, suy luận, hoạt động và kỹ năng. Đối tượng nghiên cứu là các “hành xử thông minh” chứ không phải là “sự thông minh”. ‘Không có’ Sự Thông Minh Chỉ có Biểu hiện thông minh qua hành xử Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 7
Sự Thông Minh ⚫ Thông minh hay Hành xử thông minh là gì? – Hành xử thông minh: là các hoạt động của một đối tượng như là kết quả của một quá trình thu thập, xử lý và điều khiển theo những tri thức đã có hay mới phát sinh (thường cho kết quả tốt theo mong đợi so với các hành xử thông thường) là biểu hiện cụ thể, cảm nhận được của “Sự thông minh” – Khái niệm về tính thông minh của một đối tượng thường biểu hiện qua các hoạt động: ⚫ Sự hiểu biết và nhận thức được tri thức ⚫ Sự lý luận tạo ra tri thức mới dựa trên tri thức đã có ⚫ Hành động theo kết quả của các lý luận ⚫ Kỹ năng (Skill) TRI THỨC Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 ??? Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 8
Tri thức (Knowledge) ⚫ Tri thức là những thông tin chứa đựng 2 thành phần – Các khái niệm: ⚫ Các khái niệm cơ bản: là các khái niệm mang tính quy ước ⚫ Các khái niệm phát triển: Được hình thành từ các khác niệm cơ bản thành các khái niệm phức hợp phức tạp hơn. – Các phương pháp nhận thức: ⚫ Các qui luật, các thủ tục ⚫ Phương pháp suy diễn, lý luận, ❖ Tri thức là điều kiện tiên quyết của các hành xử thông minh hay “Sự thông minh” ❖ Tri thức có được qua sự thu thập tri thức và sản sinh tri thức ❖ Quá trình thu thập và sản sinh tri thức là hai quá trình song song và nối tiếp với nhau – không bao giờ chấm dứt trong một thực thể “Thông Minh” Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 9
Tri thức – Thu thập và sản sinh ⚫ Thu thập tri thức: – Tri thức được thu thập từ thông tin, là kết quả của một quá trình thu nhận dữ liệu, xử lý và lưu trữ. Thông thường quá trình thu thập tri thức gồm các bước sau: ⚫ Xác định lĩnh vực/phạm vi tri thức cần quan tâm ⚫ Thu thập dữ liệu liên quan dưới dạng các trường hợp cụ thể. ⚫ Hệ thống hóa, rút ra những thông tin tổng quát, đại diện cho các trường hợp đã biết – Tổng quát hóa. ⚫ Xem xét và giữ lại những thông tin liên quan đến vấn đề cần quan tâm , ta có các tri thức về vấn đề đó. ⚫ Sản sinh tri thức: – Tri thức sau khi được thu thập sẽ được đưa vào mạng tri thức đã có. – Trên cơ sở đó thực hiện các liên kết, suy diễn, kiểm chứng để sản sinh ra các tri thức mới. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 10
Tri thức – Tri thức siêu cấp ⚫ “Trí thức siêu cấp” (meta knowledge) hay “Tri thức về Tri thức” Là các tri thức dùng để: – Đánh giá tri thức khác – Đánh giá kết quả của quá trình suy diễn – Kiểm chứng các tri thức mới ⚫ Phương tiện truyền tri thức: ngôn ngữ tự nhiên Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 11
Hành xử thông minh – Kết luận ⚫ Hành xử thông minh không đơn thuần là các hành động như là kết quả của quá trình thu thập tri thức và suy luận trên tri thức. ⚫ Hành xử thông minh còn bao hàm – Sự tương tác với môi trường để nhận các phản hồi – Sự tiếp nhận các phản hồi để điều chỉnh hành động - Skill – Sự tiếp nhận các phản hồi để hiệu chỉnh và cập nhật tri thức ⚫ Tính chất thông minh của một đối tượng là sự tổng hợp của cả 3 yếu tố: thu thập tri thức, suy luận và hành xử của đối tượng trên tri thức thu thập được. Chúng hòa quyện vào nhau thành một thể thống nhất “ Sự Thông Minh” ⚫ Không thể đánh giá riêng lẽ bất kỳ một khía cạnh nào để nói về tính thông minh. ➔ THÔNG MINH CẦN TRI THỨC Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 12
Mục tiêu nghiên cứu của ngành AI Trí tuệ nhân tạo nhằm tạo ra “Máy người”? Mục tiêu ➢ Xây dựng lý thuyết về thông minh để giải thích các hoạt động thông minh ➢ Tìm hiểu cơ chế sự thông minh của con người ➢ Cơ chế lưu trữ tri thức ➢ Cơ chế khai thác tri thức ➢ Xây dựng cơ chế hiện thực sự thông minh ➢ Áp dụng các hiểu biết này vào các máy móc phục vụ con người. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 13
Mục tiêu của AI (tt) ⚫ Cụ thể: – Kỹ thuật: xây dựng các máy móc có tính thông minh nhằm đáp ứng tốt hơn nhu cầu của con người. – Khoa học: xây dựng và phát triển các khái niệm, thuật ngữ, phương pháp để hiểu được các hành xử thông minh của sinh vật. – Đối tượng thường được chú trọng phát triển là máy tính Sự cần thiết của ngành AI ????? Làm sao biết máy có thông minh? Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 14
Turing Test: Thử tính thông minh ⚫ Bài toán xác định tính thông minh của một đối tượng ⚫ Turing test: Ai đây?? Máy/người?? Câu hỏi Đối tượng được test Người thực hiện test Người đối chứng Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 15
Turing Test: Ưu - Khuyết ⚫ Ưu điểm – Đem lại quan điểm khách quan về sự thông minh: Thông minh hay không thể hiện qua các trả lời của các câu hỏi – Loại trừ các thành kiến: không thích công nhận tính thông minh của máy móc. Sự thông minh chỉ được đánh giá qua các câu hỏi, không bị chi phối bởi các yếu tố khác. – Tránh tình trạng hiểu lầm ⚫ Khuyết điểm: – Phép thử tập trung vào các công việc biểu diển hoàn toàn bằng ký hiệu do đó làm mất một đặc tính rất quan trọng của máy tính là tính toán chính xác và hiệu quả – Không thử nghiệm được các khả năng tri giác và khéo léo – Giới hạn khả năng thông minh của máy tính theo khuôn mẫu con người. Nhưng con người chưa hẳn là thông minh hoàn hảo. – Không có một chỉ số rõ ràng định lượng cho sự thông minh. Phụ thuộc vào người tester. Thông Minh? ➔ Còn tùy ☺ Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 16
Lịch sử phát triển của AI : Giai đoạn cổ điển ⚫ Giai đoạn cổ điển (1950 – 1965) Đây là giai đoạn của 2 lĩnh vực chính:Game Playing (Trò chơi) và Theorem Proving (Chứng minh định ký) Game Playing: dựa trên kỹ thuật State Space Search với trạng thái (State) là các tình huống của trò chơi. Đáp án cần tìm là trạng thái thắng hay con đường dẩn tới trạng thái thắng. áp dụng với các trò chơi loại đối kháng. Ví dụ: Trò chơi đánh cờ vua. Có 2 kỹ thuật tìm kiếm cơ bản: ➢ Kỹ thuật generate and test : chỉ tìm được 1 đáp án/ chưa chắc tối ưu. ➢ Kỹ thuật Exhaustive search (vét cạn): Tìm tất cả các nghiệm, chọn lựa phương án tốt nhất. (Bùng nổ tổ hợp mn với m>=10) Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 17
Lịch sử phát triển của AI : Giai đoạn cổ điển (tt) Theorem Proving: dựa trên tập tiên đề cho trước, chương trình sẽ thực hiện chuỗi các suy diển để đạt tới biểu thức cần chứng minh. Nếu có nghĩa là đã chứng minh được. Ngược lại là không chứng minh được. Ví dụ: Chứng minh các định lý tự động, giải toán, Vẫn dựa trên kỹ thuật state space search nhưng khó khăn hơn do mức độ và quan hệ của các phép suy luận: song song, đồng thời, bắc cầu, Có các kết quả khá tốt và vẫn còn phát triển đến ngày nay (Bùng nổ tổ hợp mn , m>=10) Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 18
Lịch sử phát triển của AI- Giai đoạn viễn vông ⚫ Giai đoạn viễn vông (1965 – 1975) – Đây là giai đoạn phát triển với tham vọng làm cho máy hiểu được con người qua ngôn ngữ tự nhiên. – Các công trình nghiên cứu tập trung vào việc biểu diển tri thức và phương thức giao tiếp giữa người & máy bằng ngôn ngữ tự nhiên. – Kết quả không mấy khả quan nhưng cũng tìm ra được các phương thức biểu diễn tri thức vẫn còn được dùng đến ngày nay tuy chưa thật tốt như: – Semantic Network (mạng ngữ nghĩa) – Conceptial graph (đồ thị khái niệm) – Frame (khung) – Script (kịch bản) Vấp phải trở ngại về năng lực của máy tính Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 19
Lịch sử phát triển của AI- Giai đoạn hiện đại ⚫ Giai đoạn hiện đại (từ 1975) – Xác định lại mục tiêu mang tính thực tiễn hơn của AI là: ⚫ Tìm ra lời giải tốt nhất trong khoảng thời gian chấp nhận được. ⚫ Không cầu toàn tìm ra lời giải tối ưu – Tinh thần HEURISTIC ra đời và được áp dụng mạnh mẽ để khắc phục bùng nổ tổ hợp. – Khẳng định vai trò của tri thức đồng thời xác định 2 trở ngại lớn là biểu diển tri thức và bùng nổ tổ hợp. – Nêu cao vai trò của Heuristic nhưng cũng khẳng định tính khó khăn trong đánh giá heuristic. Phát triển ứng dụng mạnh mẽ: Hệ chuyên Better than nothing gia, Hệ chuẩn đoán, Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 20
Các lĩnh vực ứng dụng ➢ Game Playing: Tìm kiếm / Heuristic ➢ Automatic reasoning & Theorem proving: Tìm kiếm / Heuristic ➢ Expert System: là hướng phát triển mạnh mẽ nhất và có giá trị ứng dụng cao nhất. ➢ Planning & Robotic: các hệ thống dự báo, tự động hóa ➢ Machine learning: Trang bị khả năng học tập để giải quyết vấn đề kho tri thức: ➢ Supervised : Kiểm soát được tri thức học được. Không tìm ra cái mới. ➢ UnSupervised:Tự học, không kiểm soát. Có thể tạo ra tri thức mới nhưng cũng nguy hiểm vì có thể học những điều không mong muốn. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 21
Các lĩnh vực ứng dụng (tt) ➢ Natural Language Understanding & Semantic modelling: Không được phát triển mạnh do mức độ phức tạp của bài toán cả về tri thức & khả năng suy luận. ➢ Modeling Human perfromance: Nghiên cứu cơ chế tổ chức trí tuệ của con người để áp dụng cho máy. ➢ Language and Environment for AI:Phát triển công cụ và môi trường để xây dựng các ứng dụng AI. ➢ Neurol network / Parallel Distributed processing: giải quyết vấn đề năng lực tính toán và tốc độ tính toán bằng kỹ thuật song song và mô phỏng mạng thần kinh của con người. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 22
Mô hình phát triển ứng dụng AI ⚫ Mô hình ứng dụng Ai hiện tại: AI = Presentation & Search Tìm kiếm Tri Thức Search Knowledge Suy luận Engineering Heurictic Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 23
Chương 2: PHÉP TOÁN VỊ TỪ ❖Phép toán vị từ dưới góc nhìn của AI ❖Mệnh đề ❖Vị từ ThS Nguyễn Cao Trí – caotri@dit.hcmut.edu.vn KS Lê Thành Sách – ltsach@dit.hcmut.edu.vn Ñaïi Hoïc Baùch Khoa - Tp.HCM - Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Thaùng 6/2001
AI & Phép toán vị từ ⚫ Tại sao Ai phải nghiên cứu phép toán vị từ? – AI ➔ Phát triển các chương trình có khả năng suy luận – Suy luận giúp chương trình AI biết được tính đúng/sai của một vấn đề nào đó. ⚫ Phép toán vị từ ➔ cung cấp một khả năng triển khai các quá trình suy diễn trên máy tính ⚫ Phát triển chương trình AI cần phép toán vị từ. ⚫ Phép toán vị từ được hiện thực bằng ngôn ngữ lập trình trên máy tính PROLOG Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 25
AI & Phép toán vị từ: Minh họa 1 Mệnh đề thực tế Mệnh đề logic ⚫ “Nếu trời mưa thì bầu trời có mây” ⚫ P=“Trời mưa” ⚫ Trời đang mưa ⚫ Q= “Bầu trời có mây” Vậy ➔ Bầu trời có mây Ta có hai phát biểu sau đúng: ⚫ P➔ Q ⚫ P Vậy theo luật suy diễn ➔ Q là đúng. Nghĩa là: “Bầu trời có mây” Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 26
AI & Phép toán vị từ: Minh họa 2 Mệnh đề thực tế Mệnh đề logic ⚫ “Nếu NAM có nhiều tiền thì NAM đi ⚫ P=“Nam có nhiều tiền” mua sắm” ⚫ Q= “Nam đi mua sắm” ⚫ “Nam KHÔNG đi mua sắm” Ta có hai phát biểu sau đúng: Vậy ➔ Nam KHÔNG có nhiều tiền ⚫ P➔ Q ⚫  Q Vậy theo luật suy diễn ➔  P là đúng. Nghĩa là: “Nam KHÔNG có nhiều tiền” Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 27
Phép toán mệnh đề : Định nghĩa Mệnh đề: ⚫ Mệnh đề là một phát biểu khai báo ⚫ Mệnh đề chỉ nhận một trong hai giá trị: ĐÚNG (True) hoặc SAI (False) Ví dụ: ⚫ Ngày 01tháng giêng là ngày tết cổ truyền ⚫ Môn bạn đang học là AI ⚫ Hôm nay là quốc khánh ⚫ Hôm nay trời lạnh ⚫ Tại sao phải học AI ? Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 28
Mệnh đề : Các phép toán ⚫ Biểu thức mệnh đề: là sự kết hợp của các mệnh đề bởi các phép toán mệnh đề ⚫ Các phép toán:  Phủ định một ngôi  Hội hai ngôi Ưu  Tuyển hai ngôi tiên Suy ra hai ngôi = Tương đương hai ngôi ⚫ Cách đánh giá giá trị của phép toán: Bảng chân trị Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 29
Mệnh đề : Các phép toán – ví dụ P=“Nam học giỏi” ; Q=“Nam thông minh” ; R=“Nam đẹp trai” Mệnh đề thực tế Biểu thức mệnhđề ⚫ “Nam học giỏi, thông minh, đẹp trai” ⚫ P  Q  R ⚫ “Nam học giỏi hoặc thông minh” ⚫ “Nam hoặc học giỏi, hoặc đẹp trai” ⚫ P  Q ⚫ “Nam thông mình thì học giỏi” ⚫ ⚫ (P  R) (P  R) ⚫ Q P ⚫ Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 30
Mệnh đề : Các biểu thức mệnh đề đúng ⚫ Ký hiệu biểu thức đúng: wff ⚫ Thành phần cơ bản là P hay P, với P là một mệnh đề ⚫ Các biểu thức đúng định nghĩa theo dạng luật sinh sau: Wff= “Thành phần cơ bản”| wff | wff^wff | wff v wff | wff wff | wff = wff | (wff) Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 31
Mệnh đề : Ngữ nghĩa ⚫ Ngữ nghĩa của một biểu thức mệnh đề là giá trị của biểu thức mệnh đề đó. ⚫ Giá trị của biểu thức mệnh đề là có khả năng tính toán được. Trong đó: – Mỗi mệnh đề được gán một giá trị true hay false – Mỗi toán tử được đánh giá theo bảng chân trị và thứ tự ưu tiên của toán tử. ⚫ Giá trị của biểu thức mệnh đề tính bằng cách: – Dùng bảng chân trị – Đánh giá ngược từ node lá khi biểu thức mệnh đề được biểu diễn ở dạng cây Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 32
Mệnh đề : Các tương đương ⚫ Các tương đương được sử dụng thường xuyên trong quá trình biến đổi một biểu thức từ dạng này sang dạng khác. ⚫ Khả năng biến đổi tương đương trên máy tính có thể được làm tự động ⚫ Các tương đương: Trong các tương đương sau A,B,C là các mệnh đề bất kỳ. ⚫ Dạng phủ định kép ⚫ Dạng hôäi  A = A A  TRUE = A ⚫ Dạng tuyển A  FALSE = FALSE A  TRUE = TRUE A  A = A A  FALSE = A A   A = FALSE A  A = A A   A = TRUE Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 33
Mệnh đề : Các tương đương (tt) ⚫ Dạng suy ra ⚫ Dạng khác A TRUE = TRUE A B = A  B A FALSE = A  (A B) = A  B TRUE A = A A B = FALSE A = TRUE A  B FALSE A A = TRUE ⚫ Dạng hấp thu ⚫ Phép  và  có khả năng kết hợp. A  (A  B) = A ⚫ Phép  và  có khả năng hoán vị. A  (A  B) = A ⚫ Phép  có khả năng phân phối trên  A  (A  B)= AB A  (BC) =(AB)(AC) A  (A  B)= AB ⚫ Phép  có khả năng phân phối trên  ⚫ Dạng De Morgan A  (BC) =(AB)(AC)  (A  B) = A  B  (A  B) = A  B Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 34
Mệnh đề : Các dạng chuẩn CNF & DNF ⚫ Dạng chuẩn là kết xuất chuẩn của các giải thuật làm việc với phép toán mệnh đề. ⚫ Tuyển cơ bản: là thành phần cơ bản hay sự kết hợp của các thành phần cơ bản bằng phép tuyển(v) ⚫ Hội cơ bản: là thành phần cơ bản hay sự kết hợp của các thành phần cơ bản bằng phép hội (^). ⚫ Dạng chuẩn hội – CNF: là thành phần tuyển cơ bản hay các tuyển cơ bản kết hợp bởi phép hội. ⚫ Dạng chuẩn tuyển – DNF: là thành phần hội cơ bản hay các hội cơ bản kết hợp bởi phép tuyển. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 35
Mệnh đề : Luật suy diễn & chứng minh Luật suy diễn được áp dụng để phát triển các ứng dụng có khả năng suy luận. Suy luận là hoạt động thường xuyên của con người để hiểu các lý lẽ, kiểm chứng, phán đoán các vấn đề. ⚫ Luật Modus Ponens (MP) ⚫ Luật Cộng A, A B  B A  AvB ⚫ Luật Modus Tollens (MT) ⚫ Luật tam đoạn luận tuyển A B, B  A Av B, A  B ⚫ Luật Hội ⚫ Luật tam đoạn luận giả thiết A,B  A^B A B,B C A C ⚫ Luật đơn giản A^B  A Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 36
Mệnh đề : Luật suy diễn & chứng minh – Ví dụ 1 ⚫ Ta có các biểu thức sau: AvB, AvC,và A là TRUE ⚫ Chứng minh B^C có trị TRUE 1 AvB P (tieân ñeà) 2 AvC P (tieân ñeà) 3 A P (tieân ñeà) 4 B 1,3, tam ñoaïn luaän tuyeån 5 C 2,3, tam ñoaïn luaän tuyeån 6 B^C 4,5, Luaät hoäi ⚫ Đã chứng minh xong Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 37
Mệnh đề : Luật suy diễn & chứng minh – Ví dụ 2 ⚫ Ta có các biểu thức sau là đúng: AvB, A C, B D, D Chứng minh C ⚫ Ta giả thiết C dẩn đến false 1 AvB P (tieân ñeà) 2 A C P (tieân ñeà) 3 B D P (tieân ñeà) 4 P (tieân ñeà) D 5 C P (giaû thieát phaûn chöùng) 6 B 3,4,Modus Tollens 7 A 1,6, Tam ñoaïn luaän tuyeån 8 A 2,5,Modus Tollens 9 A ^A 7,8, Luaät hoäi 10 False Maâu thuaãn vôùi Luaät hoäi Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 38
Mệnh đề : Luật phân giải mệnh đề ⚫ Clause: là tuyển của không hay nhiều thành phần cơ bản. ⚫ Dạng clause:là hội của một hay nhiều Clause ⚫ Luật phân giải mệnh đề: PVD1, PvD2  (D1-P)v(D2-P) – D1,D2 là tuyển của không hay một thành phần cơ bản. – P là mệnh đề – D1-P : là một clause thu được bằng cách xóa bỏ các P trong D1 – D2- P : là một clause thu được bằng cách xóa bỏ các P trong D2 Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 39
Mệnh đề : Luật phân giải mệnh đề (tt) ⚫ Luật phân giải bảo toàn tính Unsatisfiable ⚫ S là unsatisfiable Rn(S)cũng unsatisfiable R: luật phân giải, n số lần áp dụng R trên S, n>0 ⚫ Ứng dụng của luật phân giải : dùng để chứng minh: Có S là tập các clause, dùng S chứng minh biểu thức mệnh đề W ⚫ Phương pháp: i. Thành lập phủ định của W ii. Đưa W về dạng clause iii. Thêm clause trong bước ii vào S thành lập S1 iv. Dùng luật phân giải trên S1 để dẫn ra clause rỗng. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 40
Mệnh đề : Luật phân giải mệnh đề - Ví dụ ⚫ Cho đoạn sau: “ Nam đẹp trai, giàu có. Do vậy, Nam hoặc là phung phí hoặc là nhân từ và giúp người. Thực tế, Nam không phung phí hoặc cũng không kêu căng.” “Do vậy, có thể nói Nam là người nhân từ” ⚫ Kiểm chứng kết quả suy luận trên, bằng luật phân giải. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 41
Mệnh đề : Luật phân giải mệnh đề - Ví dụ ⚫ (i) Chuyển sang mệnh đề: – P1 = “Nam đẹp trai.” – P2 = “Nam giàu có.” – P3 = “Nam phung phí.” – P4 = “Nam kêu căng.” – P5 = “Nam nhân từ.” – P6 = “Nam giúp người.” Các biểu thức thành lập được từ đoạn trên: – Wff1 = P1 ^ P2 – Wff2 = (P1 ^ P2) => (P3 ^ (P5 ^ P6)) v (P3 ^ (P5 ^ P6)) – Wff3 = P3 ^ P4 Wff4 = P5 Biểu thức cần chứng minh. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 42
Mệnh đề : Luật phân giải mệnh đề - Ví dụ ⚫ (ii) Đưa về dạng clause: ⚫ Wff1, sinh ra hai clause: C1 = P1 C2 = P2 ⚫ Wff2 = (P1 ^ P2) v ((P3 ^ (P5 ^ P6)) v (P3 ^ (P5 ^ P6)) ) = (P1 v P2 v P3 v P3 v P6) ^ (P1 v P2 v P5 v P3 v P6)^(P1 v P2 v P3 v P3 v P5) ^ (P1 v P2 v P5 v P3 v P5) ^ (P1 v P2 v P3 v P5 v P6)^ (P1 v P2 v P5 v P5 v P6) ^(P1 v P2 v P3 v P3 v P6) ^ (P1 v P2 v P5 v P3 v P6) Sinh ra các clause: C3 = (P1 v P2 v P6) C4 = (P1 v P2 v P5 v P3 v P6) C5 = (P1 v P2 v P3 v P5) C6 = (P1 v P2 v P3 v P5) C7 = (P1 v P2 v P3 v P5 v P6) C8 = (P1 v P2 v P5 v P6) C9 = (P1 v P2 v P3 v P6) C10 =(P1 v P2 v P5 v P3 v P6) ⚫ Wff3 sinh ra các clause: C11 = P3 C12 = P4 C13 = P5 (gồm cả bước lấy phủ định kết luận) Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 43
Mệnh đề : Luật phân giải mệnh đề - Ví dụ ⚫iii) áp dụng luật phân giải trên các clause: TT Clauses Luật áp dụng TT Clauses Luật áp dụng 1 P1 P 12.P4 P 2 P2 P 13 P5 P 3 P1 v P2 v P6 P 4 P1 v P2 v P5 v P3 v P6 P 14 P2 v P6 1,2, R 5 P1 v P2 v P3 v P5 P 15 P6 2, 14, R 6 P1 v P2 v P3 v P5 P 16 P1 v P2 v P5 v P3 10,15,R 7 P1 v P2 v P3 v P5 v P6 P 17 P2 v P5 v P3 1,16,R 8 P1 v P2 v P5 v P6 P 18 P5 v P3 2,17, R 9 P1 v P2 v P3 v P6 P 19 P3 13, 18, R 10 P1 v P2 v P5 v P3 v P6 P 11.P3 P 20  11, 19, R ĐÃ CHỨNG MINH Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 44
Logic Vị từ: Tại sao? ⚫ Phép toán mệnh đề ➔ suy diễn tự động nhưng chưa đủ khi cần phải truy cập vào thành phần nhỏ trong câu, dùng biến số trong câu. Ví dụ: “Mọi sinh viên trường ĐHBK đều có bằng tú tài. Lan không có bằng tú tài. Do vậy, Lan không là sinh viên trường ĐHBK” “Lan” là một đối tượng cụ thể của “SV trường ĐHBK” – không thể đặc tả được “quan hệ” này trong mệnh đề được mà chỉ có thể là: “LAN là sinh viên trường ĐHBK thì Lan có bằng tú tài. Lan không có bằng tú tài. Do vậy, Lan không là sinh viên trường ĐHBK” ⚫ Mệnh đề phải giải quyết bằng cách liệt kê tất cả các trường hợp → Không khả thi ⚫ Do đó, chúng ta cần một Logic khác hơn là phép toán mệnh đề: PHÉP TOÁN VỊ TỪ Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 45
Vị từ: Định nghĩa ⚫ Vị từ là một phát biểu nói lên quan hệ giữa một đối tượng với các thuộc tính của nó hay quan hệ giữa các đối tượng với nhau. Vị từ được biểu diễn bởi một tên được gọi là tên vị từ, theo sau nó là một danh sách các thông số. Ví dụ: + Phát biểu: “Nam là sinh viên trường ĐHBK” + Biểu diễn: sv_bk(“Nam”) Ý nghĩa: đối tượng tên là “Nam” có thuộc tính là “sinh viên trường ĐHBK”. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 46
Vị từ: Biểu diễn vị từ – Cú pháp ⚫ Chúng ta có bao nhiêu cách biểu diễn đúng cú pháp cho phát biểu nói trên? ➔ Không biết bao nhiêu nhưng chắc chắn nhiều hơn 1 ☺ Ví dụ chúng ta có thể thay đổi các tên vị từ thành các tên khác nhau như : sinhvien_bk, sinhvien_bachkhoa, Tất cả chúng đều đúng cú pháp. Một số quy ước/ chú ý khi biểu diễn: – Không mô tả những vị từ thừa, có thể suy ra từ một tập các vị từ khác. Hình thức thừa cũng tương tự dư (thừa) dữ liệu khi thiết kế CSDL. – Tên vị từ phải có tính gợi nhớ. Cụ thể, trong ví dụ trên chúng ta có thể biểu diễn bởi q(“Nam”), nhưng rõ ràng cách này không mấy thân thiện và dễ nhớ. Bạn có biết q(“Nam”) có nghĩa gì ??? Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 47
Vị từ: Biểu diễn vị từ – Cú pháp (tt) Dạng vị từ: tên_vị_từ(term1, term2, , termn) ⚫ Tên vị từ: [a z](a z| A Z| 0 9|_)* Bắt đầu bởi một ký tự chữ thường. Ví dụ: ban_than, banThan,bAN_THAN, ⚫ Term có thể là: Hằng,Biến, Biểu thức hàm. ⚫ Hằng: có thể hằng chuỗi hay hằng số. Hằng chuỗi: [“](a z| A Z| 0 9|_)*[“] hay [a z](a z| A Z| 0 9|_)* Ví dụ: “Nam”, “nam”, “chuoi”, nam, chuoi, qua, Hằng số: (0 9)* Ví dụ: 10, 32, ⚫ Biến: [A Z](a z| A Z| 0 9|_)* Ví dụ: Nguoi, NGUOI, ⚫ Biểu thức hàm có dạng: tên_hàm(term1, term2, , termk) Trong đó Tên hàm = [a z ](a z| A Z| 0 9|_)* Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 48
Vị từ : Biểu thức vị từ ⚫ Biểu thức Vị từ: là sự kết hợp của các vị từ bởi các phép toán vị từ. ⚫ Các phép toán:  Phủ định - một ngôi. X Với mọi - một ngôi X Tồn tại - một ngôi Ưu ^ Hội - hai ngôi. tiên v Tuyển - hai ngôi. => Suy ra - hai ngôi. = Tương đương - hai ngôi. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 49
Vị từ: Các biểu thức vị từ đúng ⚫ Biểu thức vị từ đúng được ký hiệu wff. ⚫ Biểu thức cơ bản: Có thể là một vị từ , một đại diện trị TRUE (trị là T - đúng), một đại diện trị FALSE (trị là F - sai). ⚫ Một biểu thức đúng cú pháp được định nghĩa như sau: Wff = “Biểu thức cơ bản” | wff |wff ^ wff |wff v wff |wff=>wff |wff = wff |(wff) |X wff |X wff Với – X : Là một biến. –  : Lượng từ với mọi. –  : Lượng từ tồn tại. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 50
Vị từ: Lượng từ ⚫ Giả sử chúng ta có: Nam là học sinh khá. Lan là học sinh trung bình. Mai học sinh khá ⚫ Xét tập D = [Nam, Lan, Mai] ⚫ Gọi p(X) cho biết: “X là học sinh khá” ta có các vị từ p(“Nam”) : trị là T. p(“Lan”) : trị là F. p(“Mai”) : trị là T. ⚫ Lượng từ tồn tại: Xét mệnh đề p(“Nam”) v p(“Lan”) v p(“Mai”) có thể biểu diễn bằng vị từ X D: p(X) “Tồn tại X thuộc tập D, mà X là học sinh khá” ⚫ Lượng từ với mọi: Xét mệnh đề p(“Nam”) ^ p(“Lan”) ^ p(“Mai”) có thể biểu diễn bằng vị từ X D: p(X) “Mọi X thuộc tập D đều là học sinh khá” Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 51
Vị từ: Biểu diễn thế giới thực ⚫ Chuyển các câu sau sang biểu thức vị từ: “Mọi sinh viên trường ĐHBK đều có bằng tú tài. Lan không có bằng tú tài. Do vậy, Lan không là sinh viên trường ĐHBK” ⚫ Với sv_bk(X) cho biết: “X là sinh viên trường DHBK” tu_tai(X) cho biết: “X có bằng tú tài” ⚫ Các câu trên được chuyển qua vị từ là: X(sv_bk(X) => tu_tai(X)). tu_tai(“Lan”). Do vậy, sv_bk(“Lan”). Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 52
Vị từ: Biểu diễn thế giới thực (tt) ⚫ “Chỉ vài sinh viên máy tính lập trình tốt.” với sv_mt(X) : “X là sinh viên máy tính” laptrinh_tot(X) : “X lập trình tốt” Câu trên chuyển sang vị từ là: X(sv_mt(X) ^ laptrinh_tot(X)) ⚫ “Không một sinh viên máy tính nào không cần cù.” với: sv_mt(X) : “X là sinh viên máy tính can_cu(X) : “X cần cù” Câu trên chuyển sang là: X (sv_mt(X) => can_cu(X)) ⚫ “Không phải tất cả các sinh viên máy tính đều thông minh” với thong_minh(X) : “X thông minh” Câu trên chuyển sang là: X(sv_mt(X) ^ thong_minh(X)) Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 53
Vị từ: Ngữ nghĩa ⚫ Vấn đề: Nếu chúng ta có biểu thức sau: XY p(X,Y) Chúng ta hiểu như thế nào ????! -> Cần sự diễn dịch. + Cách hiểu 1: X, Y : là con người. p(X,Y) cho biết : “X là cha của Y” Do vậy: XY p(X,Y) có thể hiểu là: “Mọi người X, tồn tại người Y để X là cha của Y” -> wff = XY p(X,Y) có trị là F (sai) Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 54
Vị từ: Ngữ nghĩa (tt) + Cách hiểu 2: X, Y : là con người. p(X,Y) cho biết : “Y là cha của X” Do vậy: XY p(X,Y) có thể hiểu là: “Mọi người X, tồn tại người Y là cha của X” -> wff = XY p(X,Y) có trị là T (đúng) + Cách hiểu 3: X, Y : là số nguyên. p(X,Y) cho biết : “Y bằng bình phương của X” -> wff = XY p(X,Y) có trị là T (đúng) Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 55
Vị từ: Ngữ nghĩa (tt) ⚫ Diễn dịch: gồm - Tập D, không rỗng, miền diễn dịch. - Các phép gán:  Vị từ : Quan hệ trên D  Hàm : Hàm (ánh xạ) trên D  Biến tự do : Một trị trên D, cùng một trị cho các xuất hiện  Hằng : Một trị trên D, cùng một trị cho các xuất hiện Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 56
Vị từ: Ngữ nghĩa (tt) ⚫ Ngữ nghĩa: Có diễn dịch I trên miền D của wff.  Wff không có lượng từ: Ngữ nghĩa = trị sự thật (T|F) của wff khi áp dụng diễn dịch  wff có lượng từ: XW là T, nếu: W(X/d) là T cho một d thuộc D ngược lại: XW là F XW là T, nếu: W(X/d) là T cho mọi d thuộc D ngược lại: XW là F Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 57
Vị từ: Khái niệm Có I : diễn dịch, E là wff ⚫ Model: I là cho E có trị T > I là Model của E Ngược lại: > I là CounterModel của E ⚫ Valid: E là valid nếu mọi diễn dịch I đều là Model. Ngược lại là : Invalid ⚫ Unsatisfiable: E là unsatisfiable : mọi I đêu là CounterModel Ngược lại :Satisfiable Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 58
Vị từ: Tương đương ⚫ Từ tương đương của mệnh đề: Nếu chúng ta thay thế các mệnh đề bởi các biểu thức vị từ, các mệnh đề cùng tên thì được thay cùng một biểu thức vị từ, thì được một tương đương của vị từ. Ví dụ: Mệnh đề: (P => Q) = (P v Q) Vị từ: P bởi: XYp(X,Y), Q bời: q(X) tương đương: (XYp(X,Y) => q(X)) = ((XYp(X,Y)) v q(X)) Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 59
Vị từ: Tương đương ⚫ Lượng từ: (X W) = X(W) (X W) = X(W) Với W là một wff ⚫ Tương đương có ràng buộc: Sau đây: Y: biến, W(X): wff có chứa biến X, C là wff không chứa X Ràng buộc: Y không xuất hiện trong W(X) Tương đương:  X W(X) = Y W(Y)  X W(X) =  Y W(Y) Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 60
Vị từ: Tương đương Tương đương: Dạng tuyển:  C v XA(X) = X(C v A(X))  C v XA(X) = X(C v A(X)) Dạng hội:  C ^ XA(X) = X(C ^ A(X))  C ^ XA(X) = X(C ^ A(X)) Dạng suy ra:  C => XA(X) = X(C => A(X))  C => XA(X) = X(C => A(X))  XA(X) => C = X(A(X) => C)  XA(X) => C = X(A(X) => C) Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 61
Vị từ: Dạng chuẩn Prenex ⚫ Dạng Chuẩn Prenex: Q1X1Q2X2 QnXnM Qi : , . M : wff không có lượng từ. Ví dụ: - sv_bk(x) - X(sv_bk(X) ^ hoc_te(X)) - XYcha(X,Y) ⚫ Giải thuật đưa wff về chuẩn Prenex:  Đổi tên biến > wff không còn lượng từ cùng tên biến, biến lượng từ không trùng tên biến tự do.  Đưa lượng từ sang trái dùng tương đương. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 62
Vị từ: Dạng chuẩn Prenex ⚫ Dạng chuẩn Tuyển Prenex: Q1X1Q2X2 QnXn(C1 v v Ck) Ci : Thành phần hội cơ bản. ⚫ Dạng chuẩn Hội Prenex: Q1X1Q2X2 QnXn(D1 v v Dk) Di : Thành phần tuyển cơ bản. ⚫ Giải thuật:  Đổi tên biến.  Loại bỏ => bởi : A => B = A v B  Chuyển  sang phải dùng De Morgan và phủ định kép.  Chuyển lượng từ sang trái dùng tương đương.  Phân phối v trên ^ (CNF), hay ^ trên v (DNF) Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 63
Chương 3: TÌM KIẾM TRÊN KHÔNG GIAN TRẠNG THÁI (State Space Search) ❖AI : Biểu diễn và tìm kiếm ❖Không gian tìm kiếm ❖Graph Search ❖Các giải thuật tìm kiếm trên không gian trạng thái ❖Depth first search (DFS) - Breath first search (BFS) ThS Nguyễn Cao Trí – caotri@dit.hcmut.edu.vn KS Lê Thành Sách – ltsach@dit.hcmut.edu.vn Ñaïi Hoïc Baùch Khoa - Tp.HCM - Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Thaùng 6/2001
Tại sao phải tìm kiếm? ⚫ Tìm kiếm cái gì? ⚫ Biểu diễn và tìm kiếm là kỹ thuật phổ biến giải các bài toán trong lĩnh vực AI ⚫ Các vấn đề khó khăn trong tìm kiếm với các bài toán AI – Đặc tả vấn đề phức tạp – Không gian tìm kiếm lớn – Đặc tính đối trượng tìm kiếm thay đổi – Đáp ứng thời gian thực – Meta knowledge và kết quả “tối ưu” ⚫ Khó khăn về kỹ thuật Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 65
Lý thuyết đồ thị - Review ⚫ Đồ thị: là một cấu trúc bao gồm: – Tập các nút N1, N2, Nn, Không hạn chế – Tập các cung nối các cặp nút, có thể có nhiều cung trên một cặp nút A B A B C E D D C E Nút: {A,B,C,D,E} Cung: {(a,d), (a,b), (a,c), (b,c), (c,d), (c,e), (d,e) } Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 66
Đặc tính đồ thị ⚫ Đồ thị có hướng: là đồ thị với các cung có định hướng, nghĩa là cặp nút có quan hệ thứ tự trước sau theo từng cung. Cung (Ni,Nj) có hướng từ Ni đến Nj, Khi đó Ni là nút cha và Nj là nút con. ⚫ Nút lá: là nút không có nút con. ⚫ Path: là chuổi có thứ tự các nút mà 2 nút kế tiếp nhau tồn tại một cung. ⚫ Đồ thị có gốc: Trên đồ thị tồn tại nút X sao cho tất cả các path đều đi qua nút đó. X là gốc - Root ⚫ Vòng : là một path đi qua nút nhiều hơn một lần ⚫ Cây: là graph mà không có path vòng ⚫ Hai nút nối nhau :nếu có một path đi qua 2 nút đó Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 67
Không gian trạng thái ⚫ Định nghĩa:Không gian trạng thái là một hệ thống gồm 4 thành phần [N,A,S,GD]. Trong đó: – N là tập nút của Graph. Mỗi nút là một trạng thái của quá trình giải quyết vấn đề – A: Tập các cung nối giữa các nút N. Mỗi cung là một bước trong giải quyết vấn đề. Cung có thể có hướng – S: Tập các trạng thái bắt đầu. S khác rỗng. – GD: Tập các trạng thái đích. GD Không rỗng. ⚫ Solution path: Là một path đi từ một nút bắt đầu Si đến một nút kết thúc GDj . ⚫ Mục tiêu của các giải thuật tìm kiếm là tìm ra một solution path và/hay solution path tốt nhất. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 68
Biểu diễn không gian trạng thái-Ví dụ ⚫ Trò chơi Tic Tac Toa ▪Trạng thái là một tình Trạng thái huống của bàn cờ ▪ Số trạng thái bùng nỗ nhanh. X ▪Biểu diễn trạng thái X X ▪Biểu diễn không gian Trạng thái kết thúc: có một người có 3 dấu liên tục theo đường chéo, thẳng, ngang. Số trạng thái kết thúc=??? Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 69
State Space & Database search State Space Database ⚫ Không gian tìm kiếm thường là một ⚫ Không gian tìm kiếm là một list graph hay tree ⚫ Mục tiêu tìm kiếm là một path ⚫ Tìm kiếm một record/nút ⚫ Phải lưu trữ toàn bộ không gian trong ⚫ Phần tử đã duyệt qua là không quá trình tìm kiếm còn dùng tới ⚫ Không gian tìm kiếm biến động liên ⚫ Không gian tìm kiếm là cố định tục trong quá trình tìm kiếm trong quá trình tìm kiếm ⚫ Đặc tính của trạng thái/nút là phức tạp ⚫ Thuộc tính của một record/nút là & biến động cố định Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 70
Chiến lược điều khiển trong SSS ⚫ Mục tiêu của bài toán tìm kiến trên không gian trạng thái: PATH vs STATE ⚫ Xuất phát từ đâu và kết thúc như thế nào? ⚫ Chiến lược Data-Driven-Search: Quá trình search sẽ đi từ trạng thái hiện thời áp dụng các luật để đi đến trạng thái kế tiếp và cứ thế cho đến khi đạt được một goal. ⚫ Chiến lược Goal-Driven-Search: Quá trình search sẽ đi từ trạng thái hiện tại (goal tạm thời) tìm xem luật nào có thể sinh ra trạng thái này. Các điều kiện để áp dụng được các luật đó trở thành subgoal. Quá trình lặp lại cho đến khi lui về đến các sự kiện ban đầu. Data-Driven Search hay Goal-Driven Search?? Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 71
Data-Driven vs Goal-Driven ⚫ Cả hai chiến lược cùng làm việc trên không gian trạng thái nhưng thứ tự và số các sự kiện duyệt qua khác nhau. Do cơ chế sinh ra các state khác nhau. ⚫ Quyết định chọn lựa chiến lược tùy thuộc vào: – Độ phức tạp của các luật – Độ phân chia của không gian trạng thái – Sự hiện hữu của dữ liệu ⚫ Goal đã có hay chưa, nhiều hay ít ⚫ Goal được đặc tả như thế nào: state cụ thể hay mô tả mang tính đặc tính ⚫ Cơ sở thông tin để chọn lựa chiến lược hợp lý là một META KNOWLEDGE Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 72
Data-Driven vs Goal-Driven – Ví dụ ⚫ Ba và Nam là bà con. Ba hơn nam 250 tuổi. Tìm mối quan hệ giữa Ba và Nam. ⚫ Trong bài toán này: – Không gian trạng thái là cây phả hệ – Mục tiêu tìm kiếm là path nối Ba với Nam ⚫ Giả sử mỗi thế hệ cách nhau 25 năm, như vậy Ba cách nam 10 thế hệ ⚫ Data-Driven-Search: Tìm từ Ba đến Nam. nếu trung bình mỗi thế hệ có X con thì số trạng thái cần xét là X10 ⚫ Goal-Driven search: Tìm từ Nam đến Ba mỗi người chỉ có 1 cha và 1 mẹ. Số trạng thai cần xét là 210. Như vậy Goal-Driven sẽ tốt hơn Data driven nếu số con > 2 Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 73
Graph Search ⚫ Giải thuật graph search phải có khả năng tìm kiếm ra tất cả các path có thể có để tìm được nghiệm : PATH từ trạng thái khởi đầu đến goal. ⚫ Graph search thực hiện bằng cách “lần” theo các nhánh của graph. Từ một trạng thái, sinh ra các trạng thái con, chọn một trạng thái con, xem đó là trạng thái xét kế tiếp. Lặp lại cho đến khi tìm thấy một trạng thái đích. ⚫ “Lần” theo các trạng thái → Đi vào ngõ cụt ? ⚫ Khi gặp nhánh không đi tiếp được, giải thuật phải có khả năng quay lui lại trạng thái trước đó để đi sang nhánh khác: BACK TRACKING. Do đó giải thuật còn có tên là BACKTRACK search. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 74
Giải thuật chi tiết Procedure backtrack; Cs:= first element of NSL; Begin end; S:=[start]; NLS:=[start]; De:=[ ]; add CS to SL; CS:=start; End; While (NSL [ ]) and CS=First element end; of SL)) do End; {end while} begin add CS to DE Return FAIL; remove first element from SL; End; remove first element from NSL; Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 75
Giải thuật chi tiết (tt) ⚫ Trong đó: – SL (State list) : chứa danh sách các trạng thái trên path hiện đang xét. Nếu tìm ra goal thì SL chính là nghiệm. – NSL (New State List): chứa danh sách các trạng thái đang đợi xét. – DE (Dead End): chứa các trạng thái mà con cháu của chúng không chứa đích. – CS (Current State): chứa trạng thái đang xét. ⚫ Hướng phát triển của quá trình search tùy theo cơ cấu tổ chức của NSL: FIFO, FILO hay Evaluated. ⚫ Giải thuật có thể bị loop vô tận. Lý do???? Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 76
Giải thuật chi tiết (tt) – Ví dụ ⚫ Xét graph sau: A S=[A] baét ñaàu GD=[G] laø goal. Keát B C D thuùc Cung graph E F G Ñöôøng ñi Quy trình tìm kieám? H I J F: ñi qua maáy laàn ?? Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 77
Giải thuật chi tiết (tt) – Ví dụ ⚫ Với G là goal ta có kết quả tìm kiếm theo bảng sau: Laàn laëp CS SL NSL DE 0 A [A] [A] [] 1 B [B A] [B C D A] [] 2 E [E B A] [E F B C D A] [] 3 H [H E B A] [H I E F B C D A] [] 4 I [I E B A] [I E F B C D A] [H] 5 F [F B A] [F B C D A] [E I H] 6 J [J F B A] [J F B C D A] [E I H] 7 C [C A] [C D A] [B F J E I H] 8 G [G C A] [G C D A] [B F J E I H] Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 78
Breath First Search Procedure Breath_frist_search; Là graph search với các Begin nút “anh em” của nút open :=[start]; close:=[]; hiện thời được xem xét While (open <>[]) do trước các nút “con cháu” begin remove X which is the leftmost of Open; If (X=goal) the return (Success) else begin generate children of X; Put X to close; eleminate children of X which is in Open or Close; Put remain children on RIGHT end of open; End; End; Return (FALL); End; Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 79
Breath First Search – Ví dụ ⚫ Với đồ thị đã có trong ví dụ graph search.Với Breath first search ta có quá trình như sau: Laàn laëp X Open Close 0 [A] [] 1 A [B C D ] [A] 2 B [C D E F] [A B] 3 C [D E F G] [A B C ] 4 D [E F G] [A B C D] 5 E [F G H I] [A B C D E] 6 F [G H I J] [A B C D E F] 7 G [H I J] [A B C D E F] Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 80
Depth First Search Procedure depth_frist_search; Begin Là graph search với các open :=[start]; close:=[]; nút “con cháu” của nút While (open <>[]) do hiện thời được xem xét begin trước các nút “anh em”. remove X which is the leftmost of Open; If (X=goal) the return (Success) else begin generate children of X; Put X to close; eleminate children of X which is in Open or Close; Put remain children on LEFT end of open; End; End; Return (FALL); End; Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 81
Depth First Search – Ví dụ ⚫ Với đồ thị đã có trong ví dụ graph search.Với Depth First Search ta có quá trình như sau: Laàn laëp X Open Close 0 [A] [] 1 A [B C D ] [A] 2 B [E F C D] [A B] 3 E [H I F C D] [A B E ] 4 H [I F C D] [A B E H] 5 I [F C D] [A B E H I] 6 F [J C D] [A B E H I F] 7 J [C D] [A B E H I F J] 8 C [G D] [A B E H I F J C] 9 G Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 82
Breath First vs Depth First ⚫ Breath First: open được tổ chức dạng FIFO ⚫ Depth First: open được tổ chức dạng LIFO ⚫ Hiệu quả – Breath First luôn tìm ra nghiệm có số cung nhỏ nhất – Depth First “thường” cho kết quả nhanh hơn. ⚫ Kết quả – Breath First search chắc chắn tìm ra kết quả nếu có. – Depth First có thể bị lặp vô tận. Tại sao?????? ⚫ Bùng nổ tổ hợp là khó khăn lớn nhất cho các giải thuật này. Giải Pháp cho bùng nổ tổ hợp?? Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 83
Depth first search có giới hạn ⚫ Depth first search có khả năng lặp vô tận do các trạng thái con sinh ra liên tục. Độ sâu tăng vô tận. ⚫ Khắc phục bằng cách giới hạn độ sâu của giải thuật. ⚫ Sâu bao nhiêu thì vừa? ⚫ Chiến lược giới hạn: – Cố định một độ sâu MAX, như các danh thủ chơi cờ tính trước được số nước nhất định – Theo cấu hình resource của máy tính – Meta knowledge trong việc định giới hạn độ sâu. ⚫ Giới hạn độ sâu => co hẹp không gian trạng thái => có thể mất nghiệm. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 84
AND/OR Graph ⚫ AND/OR graph là một đồ thị với các nút có thể là OR hay AND của các nút con. A A AND node OR node B C B C ⚫ Hypergraph: Một cung xác định bởi một cặp 2 phần tử: – Phần tử đầu là một node thuộc N. – Phần tử sau là một tập con của N. – Nếu phần tử sau có k node thì ta nói Hypergraph có K-Connector ⚫ AND/OR Graph đòi hỏi lưu trữ nhiều dữ liệu hơn – Các node OR kiểm tra như Backtrack Search – Các node AND phải kiểm tra đồng thời – Phải lưu trữ tất cả các vết đã đi qua để kiểm tra AND/OR Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 85
Chương 4: HEURISTIC SEARCH ❖Heuristic là gì? ❖Tìm kiếm theo heuristic ❖Các giải thuật Best first search (BFS), Giải thuật A* ❖Chiến lược Minimax, Alpha Beta ThS Nguyễn Cao Trí – caotri@dit.hcmut.edu.vn KS Lê Thành Sách – ltsach@dit.hcmut.edu.vn Ñaïi Hoïc Baùch Khoa - Tp.HCM - Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Thaùng 6/2001
Heuristic ⚫ Heuristic là gì? – Heuristic là những tri thức được rút tỉa từ những kinh nghiệm, “trực giác” của con người. – Heuristic có thể là những tri thức “đúng” hay “sai”. – Heuristic là những meta knowledge và “thường đúng”. ⚫ Heuristic dùng để làm gì? Trong những bài toán tìm kiếm trên không gian trạng thái, có 2 trường hợp cần đến heuristic: 1. Vấn đề có thể không có nghiệm chính xác do các mệnh đề không phát biểu chặt chẽ hay thiếu dữ liệu để khẳng định kết quả. 2. Vấn đề có nghiệm chính xác nhưng phí tổn tính toán để tìm ra nghiệm là quá lớn (hệ quả của bùng nỗ tổ hợp) Heuristic giúp tìm kiếm đạt kết quả với chi phí thấp hơn Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 87
Heuristic (tt) ⚫ Heuristic dùng như thế nào trong SSS? – Tìm kiếm trên không gian trạng thái theo chiều nào? Sâu hay rộng? – Tìm theo Heuristic : Heuristic định hướng quá trình tìm kiếm theo hướng mà “nó” cho rằng khả năng đạt tới nghiệm là cao nhất. Không “sâu” cũng không “rộng” ⚫ Kết quả của tìm kiếm với Heuristic – Việc tìm kiếm theo định hướng của heuristic có kết quả tốt hay xấu tùy theo heuristic “đúng” hay “sai”. – Heuristic có khả năng bỏ xót nghiệm – Heuristic càng tốt càng dẫn đến kết quả nhanh và tốt. Làm sao tìm được Heuristic tốt??? Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 88
Best First Search Procedure Best_First_Search; Y đã có trong Open: Begin if đến được Y bằng một path ngắn hơn open:=[start]; close:=[]; then gán path ngắn hơn này cho Y trên While (open<>[]) do Open. begin Lấy phần tử đầu tiên X khỏi Open. Y đã có trên close: if X là goal then return path từ start đến X if đến được Y bằng một path ngắn hơn else begin then begin xóa Y khỏi danh sách Close; sinh ra các nút con của X; thêm Y vào danh sách Open; end; for mỗi nút con Y của X do end; /*end case*/ case Y of Đưa X vào close; Y không có trong open hay close: Xếp thứ tự các trạng thái trên Open theo giá begin gán giá trị heuristic cho Y; trị Heuristic (tăng dần) đưa Y vào open; end; end; / while/ return failure; End; Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 89
Best First Search (tt) ⚫ Best First search vs Depth First & Breath First – Best First search tương tự như Depth First & Breath First nhưng phần tử được xét tiếp theo là phần tử có giá trị heuristic tốt nhất. – Cần có một hàm đánh giá các trạng thái để xác định giá trị heuristic cho các trạng thái. – Không gian trạng thái vẫn không thay đổi về “toàn cục“ tuy nhiên thường Heuristic search có không gian trạng thái làm việc nhỏ hơn Depth First và Breath First. Tại sao?? ⚫ Do sự định hướng các trạng thái kế tiếp theo hướng có khả năng tìm ra nghiệm nhanh hơn nên số trạng thái xét dư thừa sẽ hạn chế ➔ sinh ít trạng thái con hơn ⚫ Điều này cũng là nguyên nhân làøm cho Best First Search có thể dẫn đến kết quả là “nghiêäm phụ” thay vì “nghiệm tối ưu”. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 90
Hàm lượng giá Heuristic ⚫ Hàm lượng giá Heuristic là hàm ước lượng phí tổn để đi từ trạng thái hiện tại đến trạng thái goal. ⚫ Cơ sở để xác định hàm lượng giá là dựa vào tri thức/kinh nghiệm thu thập được. ⚫ Hàm lượng giá cho kết quả đúng (gần thực thế) hay sai (xa giá trị thực) sẽ dẫn đến kết quả tìm được tốt hay xấu. ⚫ Không có chuẩn mực cho việc đánh giá một hàm lượng giá Heuristic. Lý do: – Không có cấu trúc chung cho hàm lượng giá – Tính đúng/sai thay đổi liên tục theo từng vấn đề cụ thể – Tính đúng/sai thay đổi theo từng tình huống cụ thể trong một vấn đề ⚫ Có thể dùng nhiều hàm lượng giá khác nhau theo tình huống ➔ cần hàm lượng giá về các hàm lượng giá. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 91
Hàm lượng giá Heuristic – Ví dụ ⚫ Xét bài toán 8 pussle với 2 8 3 goal là: 1 6 4 5 6 0 7 5 1 2 3 8 4 7 6 5 2 8 3 1 4 3 4 0 7 6 5 Heuristic 1: Tổng số miếng sai vị trí 2 8 3 Heuristic 2: Tổng khoảng 1 6 4 5 6 0 cách sai vị trí của từng 7 5 miếng. Việc chọn lựa hàm Heuristic là khó khăn và có ý Heuristic 3: Số cặp hoán đổi nghĩa quyết định đối với tốc độ của giải thuật vị trí nhân cho 2 Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 92
Hàm lượng giá Heuristic – Cấu trúc ⚫ Xét lại hoạt động của giải thuật Best First Search: – Khi có 2 nút cùng có giá trị kỳ vọng đạt đến mục tiêu bằng nhau thì nút có path từ nút bắt đầu đến nút đó ngắn hơn sẽ được chọn trước như vậy nút này có giá trị Heuristic tốt hơn. – Hay nói cách khác hàm lượng giá Heuristic cho nút gần start hơn là tốt hơn nếu kỳ vọng đến goal là bằng nhau. – Vậy chọn nút nào nếu kỳ vọng của 2 nút khác nhau? Nút kỳ vọng tốt hơn nhưng xa start hay nút kỳ vọng xấu hơn nhưng gần root ⚫ Hàm lượng giá bao gồm cả 2 và có cấu trúc: F(n) := G(n) + H(n) G(n): phí tổn thực từ root đến n H(n): phí tổn ước luợng heuristic từ n đến goal. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 93
Ví dụ – Best first search ⚫ Xét ví dụ là bài toán 8 puzzle với: 2 8 3 1 2 3 1 6 4 8 4 7 5 7 6 5 Bắt đầu Mục tiêu  Hàm lượng giá: F(n) = G(n) + H(n) Với G(n): số lần chuyển vị trí tile đã thực hiện H(n): Số tile nằm sai vị trí Nút X có giá trị heuristic tốt hơn nút Y nếu F(x) < F(y). Ta có hoạt động của giải thuật Best First search trên như hình sau: Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 94
Ví dụ – Best first search (tt) 1 2 8 3 State A 1 6 4 7 5 F(a) =0+4=4 x 2 8 3 State B 2 2 8 3 State C x 2 8 3 State C 1 6 4 1 4 1 6 4 7 5 F(b) =1+5=6 7 6 5 F(c) =1+3=4 7 5 F(c) =1+5=6 3 2 8 3 State E 4 2 3 State F x 2 8 3 State G 1 4 1 8 4 1 4 7 6 5 F(e) =2+3=5 7 6 5 F(f) =2+3=5 7 6 5 F(g) =2+4=6 x 8 3 State H x 2 8 3 State I 2 1 4 7 1 4 7 6 5 F(h) =3+3=6 6 5 F(i) =3+4=7 Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 95
Ví dụ – Best first search (tt) 4 2 3 State F 1 8 4 7 6 5 F(f) =2+3=5 5 2 3 State J x 2 3 State K y 2 8 3 State Close 1 8 4 1 8 4 1 4 7 6 5 F(j) =3+2=5 7 6 5 F(k) =3+4=7 7 6 5 1 2 3 6 State L y 2 3 8 4 Close 1 8 4 7 6 5 F(l) =4+1=5 7 6 5 y 2 3 State Close 7 1 2 3 State M x 1 2 3 State N 1 8 4 8 4 7 8 4 7 6 5 7 6 5 F(m) =5+0=5 6 5 F(n) =5+1=7 Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 96
Hoạt động theo giải thuật Best First Search Laàn X Open Close 0 [a4] [] 1 A4 [c4,b6,d6] [a4] 2 C4 [e5,f5,g6,b6,d6] [a4,c4] 3 E5 [f5,h6,g6,b6,d6,i7] [a4,c4,e5] 4 F5 [j5,h6,g6,b6,d6,k7,i7] [a4,c4,e5,f5] 5 J5 [l5,h6,g6,b6,d6,k7,i7] [a4,c4,e5,f5,j5] 6 l5 [m5,h6,g6,b6,d6,k7,i7,n7] [a4,c4,e5,f5,j5,l5] 7 m5 Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 97
Đánh giá giải thuật Heuristic ⚫ Admissibility – Tính chấp nhận Một giải thuật Best first search với hàm đánh giá F(n) = G(n) + H(n) với N : Trạng thái bất kỳ G(n) : Phí tổn đi từ nút bắt đầu đến nút n H(n) : Phí tổn ước lượng heuristic đi từ nút n đến goal Được gọi là giải thuật A Một giải thuật tìm kiếm được xem là admissible nếu đối với một đồ thị bất kỳ nó luôn dừng ở path nghiệm tốt nhất (nếu có). Giải thuật A*: Là giải thuật A với hàm heuristic H(n)luôn luôn giá trị thực đi từ n đến goal. Giải thuật A* là admissible Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 98
Đánh giá giải thuật Heuristic ⚫ Monotonicity – Đơn điệu Một hàm heuristic H(n) được gọi là monotone (đơn điệu) nếu: 1. ni, nj : nj là nút con cháu của ni ta có H(ni)-H(nj) phí tổn thật đi từ ni đến nj 2. Đánh giá heuristic của đích là 0 : H(goal) = 0. Giải thuật A có hàm H(n) monotone là giải thuật A* và Admissible ⚫ Informedness Xét 2 hàm heuristic H1(n) và H2(n) nếu ta có H1(n) H2(n) với mọi trạng thái n thì H2(n) được cho là informed hơn H1(n). Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 99
Chiến lược minimax ⚫ Giải thuật tìm kiếm Heuristic với các hàm heuristic chỉ thích hợp cho các bài toán không có tính đối kháng. Như các trò chơi chỉ có một người chơi: Puzzle, tìm lối ra mê cung, bài toán n quân hậu, ⚫ Các trò chơi có tính đối kháng cao, thường là các trò chơi 2 người chơi như: tic tac toa, caro, cờ quốc tế, giải thuật trên không có tác dụng vì: Đối phương không bao giờ đi theo con đường cho ta có thể đi đến goal ⚫ Cần phải có một giải thuật khác phù hợp hơn. Chiến lược MINIMAX ⚫ Chiến lược Minimax (được thể hiện bằng giải thuật minimax) dựa trên 2 giả thiết sau: – Cả 2 đối thủ có cùng kiến thức như nhau về không gian trạng thái của trò chơi – Cả 2 đối thủ có cùng mức cố gắng thắng như nhau Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 100
Giải thuật minimax ⚫ Chiến lược Minimax Hai đối thủ trong trò chơi có tên là MAX và MIN – Max: biểu diễn cho mục đích của đối thủ này là làm lớn tối đa lợi thế của mình – Min: biểu diễn cho mục đích của đối thủ này là làm nhỏ tối đa lợi thế của đối phương. Trên cây tìm kiếm sẽ phân lớp thành các lớp Max và Min. Với một node n bất kỳ, – Nếu nó thuộc lớp Max thì gán cho nó giá trị Max của các node con – Nếu nó thuộc lớp Min thì gán cho nó giá trị nhỏ nhất của các node con. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 101
Giải thuật minimax – ví dụ ⚫ Bài toán que diêm Một tập que diêm ban đầu đặt giữa 2 người chơi. Lần lượt đi xen kẽ. Người đến lượt đi phải chia nhóm que diêm theo nguyên tắc: – Chọn nhóm bất kỳ có số que >2 – Chia thành 2 nhóm có số que khác nhau Goal: người nào đến lượt mà không chia được là thua. MINIMAX ⚫ Không gian trạng thái của trò chơi được phát triển toàn bộ, các node lá được gán giá trị 1 nếu là MAX thắng và 0 nếu là MIN thắng. ⚫ Với một node bất kỳ nếu thuộc lớp MAX gán cho nó giá trị lớn nhất của các node con. Nếu thuộc lớp MIN gán cho nó giá trị nhỏ nhất của các node con. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 102
Minimax – bài toán que diêm MIN 7 1 1 1 1 MAX 6-1 5-2 4-3 0 1 0 1 MIN 5-1-1 4-2-1 3-2-2 3-3-1 0 1 0 MAX 4-1-1-1 3-2-1-1 2-2-2-1 0 1 MIN 3-1-1-1-1 2-2-1-1-1 0 MAX 2-1-1-1-1-1 Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 103
Minimax với độ sâu giới hạn ⚫ Minimax như đã xét buộc phải có toàn bộ không gian trạng thái đã được triển khai để có thể gán trị cho các nút lá và tính ngược lại ➔ Không khả thi với các bài toán lớn vì không gian trạng thái là quá lớn. ➔ Giới hạn không gian trạng thái lại theo một độ sâu nào đó và giới hạn các node con theo một qui tắc nào đó. ⚫ Đây là chiến lược thông thường của các người chơi cờ: khả năng tính trước bao nhiêu nước. ⚫ Khi đó ta chỉ triển khai các nút con đến độ sâu giới hạn. ⚫ Đánh giá cho các nút này như là nút lá bằng một hàm lượng giá Heuristic. ⚫ áp dụng chiến lược minimax cho việc đánh giá các nút cấp trên. ⚫ Kỹ thuật này gọi là nhìn trước K bước với K la øđộ sâu giới hạn. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 104
Ví dụ: Bài toán Tic Tac Toa ⚫ Hàm lượng giá heuristic E(n) = X(n) – O(n) với – X(n) số khả năng thắng của quân X. – O(n) số khả năng thắng của quân O X X có 6 khả năng thắng X O E(n) = 6 - 5 = 1 O X O có 5 khả năng thắng O Với hàm Heuristic trên X sẽ cố làm cho E(n) lớn nhất (MAX) và O làm cho E(n) nhỏ nhất (MIN). Triển khai bài toán với 2 bước nhìn trước. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 105
Ví dụ: Bài toán Tic Tac Toa 1 MAX X -1 1 -2 MIN X X 1 2 MAX X X X -1 X 0 X 1 X 0 X -1 O O O O O Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 106
Độ phức tạp của giải thuật SSS ⚫ Độ phức tạp tính theo hệ số rẽ nhánh. ⚫ Xét bài toán có hệ số rẽ nhánh trung bình là B, độ sâu trung bình của solution path là D . Với T là số trạng thái đã được xét qua để tìm ra lới giải thì ta có T= (B +B2 + B2 + .+BD)/(B-1) T sẽ rất lớn đối với các vấn đề thực tế. Phải dùng Heuristic để giới hạn độ phức tạp của giải thuật bằng cách giảm số trạng thái phải đi qua. Tuy nhiên hàm Heuristic tốt thì lại đòi hỏi yêu cầu tính toán nhiều ➔ Phí tổn cho tính toán tăng cao. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 107
Chương 5: HỆ LUẬT SINH Production system ❖Tìm kiếm đệ qui ❖Hệ luật sinh: Định nghĩa và ứng dụng ❖Tìm kiếm trên hệ luật sinh ThS Nguyễn Cao Trí – caotri@dit.hcmut.edu.vn KS Lê Thành Sách – ltsach@dit.hcmut.edu.vn Ñaïi Hoïc Baùch Khoa - Tp.HCM - Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Thaùng 6/2001
Đặc tính dữ liệu và điều khiển của SSS ⚫ Các đặc tính của giải thuật SSS: – Lời giải là một PATH từ điểm START đến điểm GOAL – Tìm kiếm là sự kiểm tra có hệ thống các đường dẫn đến GOAL – Backtracking cho phép giải thuật “phục hồi” khi đi vào một nhánh không có đáp án. – Các danh sách sẽ giữ các trạng thái đang xem xét: ⚫ Danh sách Open: cho phép hệ thống backtrack về các trạng thái chưa được xét. ⚫ Danh sách Close: cho phép hệ thống kiểm tra sự quay vòng tránh lặp vô tận – Dùng STACK cho DFS, QUEUE cho BFS và dùng PRIORITY QUEUE cho BFS. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 109
Tìm kiếm đệ qui – Tại sao??? ⚫ Tìm kiếm đệ qui là giải thuật tìm kiếm trên SSS với các đặc tính: – Ngắn gọn xúc tích hơn – Tiếp cận của giải thuật tự nhiên hơn – Hợp nhất với phương thức hiện thực của Logic vị từ ⚫ Các giải thuật tìm kiếm đệ qui chính: – Tìm kiếm đệ qui – Recursive Search (RS) – Tìm kiếm theo mẫu – Pattern Directed Search (PDS) ⚫ Các giải thuật tìm kiếm đệ qui được sử dụng rộng rải trong các shell của các Hệ chuyên gia (Expert System). ⚫ Pattern Directed Search là nền tản của PROLOG Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 110
Thế nào là đệ qui? ⚫ Đệ qui là sự định nghĩa một đối tượng bằng cách sử dụng chính đối tượng đó – Toán học ⚫ Đệ qui được dùng để định nghĩa và phân tích các cấu trúc dữ liệu cũng như các thủ tục xử lý trong ngành máy tính. ⚫ Một thủ tục đệ qui bao gồm: – Thành phần đệ qui, trong đó thủ tục gọi chính nó để lặp lại chuổi các thao tác. – Thành phần dừng dùng để dừng quá trình đệ qui vô tận. (lặp vô tận) ⚫ Hai thành phần này tồn tại đồng thời trong tất cả các định nghĩa đệ qui cũng như giải thuật đệ qui. ⚫ Đệ qui là một cấu trúc điều khiển dữ liệu tự nhiên cho những cấu trúc không xác định số phần tử cố định: list, tree, và đồ thị. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 111
Thủ tục đệ qui – ví dụ Function Member(item, list); ⚫ Đệ qui có đầy đủ tính năng của các cấu begin trúc điều khiển truyền thống như Loop và rẽ nhánh➔mọi chương trình viết if List rỗng then return (Fail) được bằng cấu trúc truyền thống đều có else thể viết đệ qui. if Item = phần tử đầu của list then return ⚫ Đệ qui thích hợp biểu diễn các cấu trúc (succes) toán học ➔ thuận tiện trong việc kiểm tra tính đúng đắn của giải thuật đệ qui. else ⚫ Công thức đệ qui cũng thường được begin dùng trong việc sinh và kiểm tra Tail:= List \ phần tử đầu; chương trình tự động. member (item, Tail); ⚫ Đệ qui là công cụ tự nhiên và mạnh mẻ cho hiện thực các chiến lược giải quyết end vấn đề của AI. end; Tại sao? Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 112
Giải thuật DFS đệ qui - DFS Function Depth_First_Search; Begin if Open rỗng then return (fail); Current_state := phần tử đầu tiên của open; If (current_state là mục tiêu) then return (Success) else begin open:=phần đuôi của open; Closed := Closed + current_state; for mỗi phần tử con Y của current_state do if not (Y in close) and not (Y in open) then thêm Y vào đầu của Open; End; depth_first_search; End; Nhược điểm của recursive ? Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 113
Pattern-Directed Search (PDS) ⚫ Các giải thuật Search đã tìm hiểu và Recursive Seach không trình bày cách biểu diển một trạng thái trong không gian trạng thái cũng như cách sinh các trạng thái mới. ⚫ Pattern-Directed Search là một giải thuật search đệ quy dùng Logic Vị từ để hiện thực việc sinh các trạng thái mới. ⚫ Paterm-Directed Search xuất phát từ goal và các modus ponen dạng q(x)->p(x) để chuyển trạng thái. Các modus ponen này gọi là các luật sinh. ⚫ Giải thuật: Xuất phát từ goal P, áp dụng một giải thuật để tìm các rule với P ở vế phải , sau đó xem vế trái Q là subgoal. Đệ quy với Q cho đến khi Qx là một sự kiện trong kho tri thức. Sự kiện (FACT) trong kho tri thức????? Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 114
Giải thuật PDS Function Pattern_search(current_goal); If tất cả các hội đều success Begin then return success else return fail. If current_goal có trong closed then retuen fail end; else thêm current_goal vào trong closed; Current_goal là vế phải một rule: while còn trong database các rule hay fact chưa xét begin begin case áp dụng các thành phần vào vế trái Q. current_goal trùng với fact: if pattern_search(Q) then return success return(success); else return fail; current_goal là một phép hội: end; begin end; /* case for mỗi thành phần hội Pi do Return fail; pattern_search(Pi); End; Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 115
Giải thuật PDS ⚫ PDS dùng các rule và thành phần hội để sinh các trạng thái con. ⚫ Tách bạch quá trình điều khiển của giải thuật và dữ liệu của giải thuật – ➔ Cùng giải thuật chỉ cần thay đổi database : Fact & Rule ta sẽ áp dụng cho các bài toán khác nhau. – ➔Xây dựng các shell và có thể vận hành cho các hệ thống khác nhau bằng cách thay đổi Database. ⚫ Để đơn giản hoá giải thuật chưa giải quyết ở mức độ có các biến trong các rule. Ví dụ P(x)^Q(x) chỉ thõa khi P và Q cùng thỏa với cùng giá trị X. ⚫ Các phép , v, cũng chưa giải quyết trong giải thuật này. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 116
Ví dụ: Bài toán mã đi tuần Đặc tả bài toán: tìm đường đi cho con mã qua tất cả các ô trên bàn cờ. Ví dụ với bàn cờ 3x3. move(1,8) move(1,6) move(2,9) move(2,7) 1 2 3 move(3,4) move(3,8) move(4,9) move(4,3) move(6,1) move(6,7) move(7,2) move(7,6) 4 5 6 move(8,3) move(8,1) move(9,2) move(9,4) 7 8 9 X path(X,X); X,Y [path(X,Y)  Z[move(X,Z]^path(Z,Y)]] Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 117
Giải thuật PDS đầy đủ Function Pattern_search(current_goal); If tất cả các hội đều success then return các Begin thành phần hội else return fail. If current_goal có trong Closed then return fail else end; thêm current_goal vào Closed; current_goal là phép tuyển: while còn các rule hay fact chưa xét begin begin repeat cho mọi thành phần tuyển Vi; case until (pattern_search(Vi) or (hết thành phần hội) current_goal trùng với fact: return(success); if pattern_search (Vi) then return các thay thế current_goal là negated(p): else return fail; begin end; if pattern_search(p) then return fail Current_goal là vế phải một rule: else return{} begin end; áp dụng các thành phần vào vế trái Q. current_goal là một phép hội: if pattern_search(Q) then return kết hợp của begin Current_goal và các thay thế của Q else return fail; for mỗi thành phần hội Pi do end; end; /* case*/ if not (pattern_search(Pi)) the return fail else thay thế tất cả các biến cho các thành phần hội return fail; End; khác. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 118
Hệ Luật Sinh – Production System ⚫ Khái niệm: Hệ luật sinh là một mô hình tính toán quan trọng trong các bài toán tìm kiếm cũng như mô phỏng cách giải quyết vấn đề của con người trong lĩnh vực ứng dụng AI. ⚫ Định nghĩa: Hệ luật sinh là một mô hình tính toán cung cấp cơ chế điều khiển Pattern_directed trong quá trình giải quyết vấn đề (Proplem solving process). ⚫ Cấu trúc hệ luật sinh bao gồm 3 thành phần: 1. Production rules ( Tập luật sản sinh) 2. Working memory (Vùng nhớ làm việc) 3. Recognize-action control (Bộ điều khiển nhận dạng và hành động) Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 119
Định nghĩa (tt) – Production Rule ⚫ Production rules: là một tập các luật sản sinh được đặc tả dạng: Condition – Action (điều kiện – hành động) ⚫ Một luật là một mắt xích của kho tri thức giải quyết vấn đề. Kho tri thức là một database của các production rules. ⚫ Thành phần Condition: là một mẫu (pattern) dùng xác định điều kiện áp dụng của rule cho một vấn đề tương ứng. ⚫ Thành phần action: mô tả bước giải quyết vấn đề tương ứng sẽ được thực hiện. Đây là phần sẽ tác động lên hiện trạng của không gian tìm kiếm. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 120
Định nghĩa (tt) – Working memory ⚫ Working memory chứa những đặc tả trạng thái hiện tại của quá trình suy luận. Chúng được lưu trữ như là tập các mẫu. ⚫ Những đặc tả này là các mẫu để so trùng với các condition của các production rules. ⚫ Khi một production rule được so trùng phần condition thì phần action của nó có thể được áp dụng, và phần action này được xây dựng đặc thù để tác động trực tiếp lên working memory. ⚫ Working memory được khởi tạo bằng trạng thái bắt đầu của vấn đề cần giải quyết. ⚫ Working memory diễn tả hiện trạng của vấn đề cần suy luận Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 121
Định nghĩa (tt) – Recognize-action ⚫ Đây là cấu trúc điều khiển dùng trong production system. Quy trình hoạt động của Recognize -Action Recognize Working (match pattern) Memory Chọn thế nào?? (tập các mẫu) Conflict Set Select rule Tập các production rule Chọn một rule Matched với working memory Tác động làm thay đổi Working Memory Apply Action Thực hiện action Selected Conflict của rule được chọn Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 122
Các vấn đề khác ⚫ Chọn lựa Conflict để thực hiện Có thể chọn bằng cách đơn giản hay áp dụng các chiến lược lựa chọn heurictic → Ứng dụng meta knowledge. Nếu gọi chiến lược heuristic chọn conflict là meta knowledge thì knowledge “thường” ở đâu trong hệ thống? ⚫ Các hệ luật sinh đơn thuần không cung cấp cơ chế để quay lui khi việc áp dụng các action làm cho working memory thay đổi dẫn đến lúc không còn production rule nào có thể áp dụng được→ Hệ thống sẽ dừng. ⚫ Cần cung cấp cơ chế backtracking (Thường dùng UNDO). Tuy nhiên cần chú ý để tránh lặp vòng. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 123
Ví dụ: bài toán 8 Puzzle 2 8 3 1 2 3 ▪ Working Memory Current state 1 6 4 8 4 Goal state ▪ Production Rules 7 5 7 6 5 Goal state → Halt Blank is not on top edge → Move the blank up Blank is not on the right edge → Move the blank right Blank is not on the bottom edge → Move the blank down Blank is not on the left edge → Move the left down ▪ Recognize-Action 1- Try each production rule in order 2- Do not allow loops 3- Stop when goal is found Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 124
Điều khiển tìm kiếm trong hệ luật sinh ⚫ Chiến lược Data-Driven / Goal-Driven: – Data-Driven: bắt đầu với problem trong working memory, matching các condition trong production rule → conflict → áp dụng các action → thay đổi working memory. Lặp lại cho đến khi đạt được goal state. – Goal-Driven: Bắt đầu với mô tả goal trong working memory, matching với các kết quả của Action → sinh tập các condition→ đưa các condition vào trong working memory. Lặp lại cho đến khi working memory chứa FACT. ⚫ Điều khiển qua cấu trúc rule: Dùng các biến đổi tương đương của các biểu thức trong rule để điều khiển quá trình tìm kiếm. ⚫ Điều khiển bằng sự phân tích các Conflict: Các conflict có thể được chọn lựa thông qua các Heuristic. áp dụng các meta knowledge trong việc chọn conflict. Ví dụ: 1) Refraction: Khi một rule đã được áp dụng, nó sẽ không được dùng nữa cho đến khi thánh phần trùng lặp với rule cũ trong working memory được thay đỗi. 2) Recency: Chọn rule có phần condition match với phần mới thêm vào working memory. Theo đuổi một hướng triển khai. 3) Specificity: Rule nào càng được đặc tả chi tiết càng được ưu tiên cao. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 125
Các ưu điểm của Hệ luật sinh ⚫ Hệ luật sinh là khung làm việc tổng quát để thực thi các giải thuật tìm kiếm. Với đặc tính đơn giản, dể sửa đổi, và linh động, hệ luật sinh được dùng như một công cụ quan trọng để xây dựng các hệ chuyên gia và các ứng dụng AI khác ⚫ Các ưu điểm của Hệ luật sinh: ▪ Tách bạch giữa Tri thức & Điều khiển: ⚫ Điều khiển: nằm trong chu trình Recognize-Action ⚫ Tri thức: được chứa đựng trong bản thân các luật sinh. ➔ Cung cấp khả năng cập nhật tri thức mà không cần điều chỉnh chương trình. Thay đổi mã chương trình mà không ảnh hưởng đến tập luật sinh. ▪ Dễ dàng áp dụng trong tìm kiếm trên không gian trạng thái. Các state của working memory là các node. Các production rule là các chuyển đổi giữa các trạng thái (cơ chế sinh các trạng thái mới) ▪ Tính độc lập của các luật sinh. ▪ Khả năng áp dụng heuristic cho việc điều khiển quá trình hoạt động. ▪ Theo dõi và giải thích quá trình hoạt động ▪ Độc lập với ngôn ngữ & có thể dùng như kỹ thuật mô phỏng giải pháp của người. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 126
Chương 6: HỆ CHUYÊN GIA (ES) ❖Giới thiệu về hệ chuyên gia ❖Mô hình hệ chuyên gia: dự trên luật, dựa trên frame ❖Phát triển một hệ chuyên gia ThS Nguyễn Cao Trí – caotri@dit.hcmut.edu.vn KS Lê Thành Sách – ltsach@dit.hcmut.edu.vn Ñaïi Hoïc Baùch Khoa - Tp.HCM - Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Thaùng 6/2001
Nội dung. ⚫ Giới thiệu về hệ chuyên gia. – Định nghĩa, khả năng ứng dụng. – Cấu trúc, các đặc trưng cơ bản của ES. – Biểu diễn tri thức. – Các kỹ thuật suy luận. ⚫ Khảo sát một vài hệ chuyên gia đã có. – XCON: ES trợ giúp cấu hình hệ thống máy tính của DEC – MYCIN: ES chuẩn đoán bệnh nhiễm trùng máu. ⚫ Hệ chuyên gia dựa trên luật. – Kiến trúc, thiết kế. – Ưu - nhược điểm. ⚫ Hệ chuyên gia dựa vào Frame. – Kiến trúc, thiết kế. – Ưu - nhược điểm. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 128
Giới thiệu về hệ chuyên gia. ⚫ Định nghĩa: Hệ chuyên gia là một chương trình được thiết kế để theo mô hình có khả năng giải quyết vấn đề của chuyên gia con người. ⚫ Sơ đồ khối cơ bản: Cô sôû Ñoäng cô tri thöùc Suy luaän Heä chuyeân gia Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 129
Giới thiệu về hệ chuyên gia. ⚫ Cơ sở tri thức: . Dùng để chứa tri thức trong một lĩnh vực nào đó, tri thức này do chuyên gia con người chuyển giao. . Nó bao gồm: các khái niệm cơ bản, các sự kiện, các luật và quan hệ giữa chúng. Ví dụ: - Tri thức về bệnh nhiễm trùng máu do các bác sĩ chuyên khoa này chuyển giao. - Tri thức về chiến lược đầu tư do các nhà cố vấn đầu tư chuyển giao. - Tri thức về sự diễn dịch dữ liệu khảo sát địa vật lý do các kỹ sư địa chất chuyển giao. - ? Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 130
Giới thiệu về hệ chuyên gia. ⚫ Động cơ suy luận: Là bộ xử lý cho tri thức, được mô hình sao cho giống với việc suy luận của chuyên gia con người. Bộ xử lý này làm việc dựa trên thông tin mà người dùng mô tả về vấn đề, kết hợp với CSTT, cho ra kết luận hay đề nghị. ⚫ Tạo sao phải xây dựng ES ? Chuyên gia con người là tài nguyên quý giá cho nhiều tổ chức. Họ có thể giải quyết những vấn đề khó, hiệu quả, . Vậy có giá trị không khi chúng ta xây dựng một chương trình có khả năng như chuyên gia con người ?Một số mặt nào đó còn có thể hơn hẳn. Xem bảng so sánh sau: Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 131
Giới thiệu về hệ chuyên gia. . Bảng so sánh: Tiêu chí CG con người ES. 1. Sẵng dùng TG. hành chính Mọi lúc. 2. Vị trí Cục bộ Mọi nơi. 3. An toàn không thể thay thế Có thể thay thế. 4. Có thể chết Có Không. 5. Hiệu suất Thay đổi Hằng số. 6. Tốc độ Thay đổi Hằng số (thường nhanh hơn) 7. Chi phí Cao Có thể cố gắng. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 132
Giới thiệu về hệ chuyên gia. . Vài lý do để phát triển ES thay cho chuyên gia con người:  Tạo cho tính chuyên gia sẵn dùng ở mọi nơi, mọi lúc.  Tự động hoá các công việc đòi hỏi chuyên gia.  Các chuyên gia đang nghỉ hưu hay chuyển đến nơi khác – Cần thay thế.  Thuê chuyên gia với chi phí quá lớn.  Tính chuyên gia cần thiết trong các môi trường làm việc không thân thiện, ở đó hỏi một ES sẽ nhanh hơn một chuyên gia con người.  Phát triển ES để trợ giúp cho chuyên gia con người. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 133
Giới thiệu về hệ chuyên gia. ⚫ Các kiểu vấn đề thường được giải quyết bởi ES: . Lựa chọn: . Điều khiển: . Mô phỏng: . Thiết kế: . Chuẩn đoán: . Dạy học: . Diễn dịch: . Giám sát: . Hoạch định: . Dự đoán: Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 134
Cấu trúc của ES. ⚫ Cấu trúc của ES: ES mô phỏng khả năng giải quyết vấn đề của chuyên gia con người. Do vậy, chúng ta cần xem xét cách thức giải quyết của chuyên gia con người, để từ đó mô phỏng. Long- Term Memory Tri thöùc cuûa lónh vöïc Ngöôøi ñöôïc khuyeân Boä suy luaän Söï kieän, Short- Term Memory Keát luaän Söï kieän, keát luaän Chuyeân gia con ngöôøi Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 135
Cấu trúc của ES. . Cách giải quyết vấn đề ở ES: CSTT Tri thöùc cuûa lónh vöïc Ngöôøi duøng Ñoäng cô suy luaän Söï kieän, Boä nhôù laøm vieäc Keát luaän Söï kieän, keát luaän Heä chuyeân gia Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 136
Cấu trúc của ES. ⚫ CSTT: Là một bộ phận của ES nhằm chứa tri thức của lĩnh vực. . ES chứa tri thức của chuyên gia con người trong một bộ phận được gọi là CSTT. Để có tri thức này, người kỹ sư tri thức phải thu thập tri thức từ chuyên gia con người rồi mã hoá vào CSTT – cách thức mã hoá sẽ được đề cập trong phần kỹ thuật biểu diễn tri thức. . Một trong các cách tiêu biểu để biểu diễn là dùng luật, như sau: RULE 1: IF “Xe car không thể khởi động được” THEN “Vấn đề trong hệ thống điện” RULE 2: IF “Vấn đề trong hệ thống điện” AND “Điện thế AC-quy nhỏ hơn 10Volt” THEN lỗi tại bộ AC-quy” Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 137
Cấu trúc của ES. ⚫ Bộ nhớ làm việc: Là bộ phận của ES dùng để chứa các sự kiện của vấn đề. Các sự kiện này có thể do người dùng nhập vào lúc đầu hay do ES sinh ra trong quá trình làm việc. - Với ES dùng cho nhiều người cùng thì bộ nhớ làm việc thường phân nhóm theo phiên làm việc (session) của người dùng. Đó là trường hợp một ES chung cho nhiều người dùng từ xa. - Nhiều ES cũng tận dụng các thông tin được chứa trong các nguồn ngoài như: CSDL, bảng tính, sensor, ES sẽ tải thông tin này vào bộ nhớ làm việc đầu mỗi session hay khi cần thiết. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 138
Cấu trúc của ES. ⚫ Động cơ suy luận: Là bộ xử lý trong hệ chuyên gia, là nhiệm vụ so trùng các sự kiện được chứa trong bộ nhớ làm việc với tri thức được chứa trong CSTT nhằm dẫn ra kết luận cho vấn đề. . Tiêu biểu, nếu CSTT có chứa luật, ES sẽ tìm ra luật mà các tiên đề của luật so trùng với các sự kiện được chứa trong bộ nhớ làm việc, lúc đó ES sẽ thêm các kết luận của luật đó vào bộ nhớ làm việc, rồi tiếp tục tìm ra sự so trùng khác – giống như nguyên lý hoạt động của hệ luật sinh. . Ví dụ: Giả sử CSTT chỉ với hai luật nêu trên Bước 1: ES: Có phải xe car không khởi động được ? Người dùng: Đúng. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 139
Cấu trúc của ES. Chú thích: Người dùng trả lời “Đúng”, nên ES thêm vào bộ nhớ làm việc sự kiện để mô tả: “Xe car không thể khởi động được” Động cơ suy diễn của ES làm nhiệm vụ so trùng, nhận thấy RULE 1 có thể so trùng được, nên nó thêm vào bộ nhớ làm việc phần kết luận của RULE 1, đó là: “Vấn đề trong hệ thống điện” Bước 2: ES: Có phải điện Ac-quy dưới 10 Volt? Người dùng: Đúng. Chú thích: Người dùng trả lời “Đúng”, nên ES thêm vào bộ nhớ làm việc sự kiện để mô tả: “Điện thế Ac-quy nhỏ hơn 10Volt” Động cơ suy diễn của ES làm nhiệm vụ so trùng, nhận thấy RULE 2 có thể so trùng được, nên nó thêm vào bộ nhớ làm việc phần kết luận của RULE 2, đó là: lỗi tại bộ Ac-quy” – phiên làm việc cũng kết thúc vì CSTT chỉ gồm hai luật trên. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 140
Cấu trúc của ES. ⚫ Tiện ích giải thích. Một trong các điểm nổi bật của ES là khả năng giải thích về suy luận của nó. ES còn có một khối cơ bản nữa trong cấu trúc của nó đó là: khối tiện ích giải thích. Với khối này ES có thể cung cấp cho người dùng các khả năng giải thích: - Tại sao ES lại hỏi câu hỏi nào đó. (WHY) - Bằng cách nào ES có thể suy ra kết luận nào đó. (HOW) Khối tiện ích giải thích thuận tiện cho cả người phát triển ES và người dùng. Người phát triển có thể nhờ đó khám phá các lỗi trong tri thức của ES. Người thì có thể yên tâm hơn khi nhận một kết luận nào đó, không cần thiết phải quan tâm với cấu trúc tri thức của ES. . Giải thích bằng cách nào (HOW) Ngoài chức năng cung cấp cho người dùng kết quả suy luận cuối cùng, ES càng có thể cung cấp nó đạt đến kết luận bằng cách nào. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 141
Cấu trúc của ES. Khả năng giải thích bằng cách nào rất quan trọng với ES, nó làm cho ES khác với các chương trình truyền thống. Các chương trình truyền thống làm việc trên các bài toán được định nghĩa tốt, kết quả của chương trình đã được kiểm nghiệm trước khi chuyển giao. ES làm việc trên các bài toán thiếu nhiều thông tin, thậm chí tri thức còn có thể cập nhật khi ES đã được triển khai – chính vì vậy mà kết luận của nó phải được giải thích bằng cách nào để cho kết quả cuối cùng có giá trị hơn. Ví dụ: trong phiên làm việc của ES nói trên. ES: lỗi tại bộ Ac-quy”. Người dùng: HOW ES: “Bởi vì, khi xe của bạn không khởi động được, tôi cho rằng đã có vấn đề trong hệ thống điện. Mỗi lần, tôi thấy điện thế của ac-quy dưới 10 volt, tôi biết rằng ac-quy đã hư.” - Khả năng giải thích HOW của ES có thể thực hiện được bằng cách cho phép nó theo vết các luật mà nó đã sử dụng vào suy luận. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 142
Cấu trúc của ES. . Giải thích tại sao (WHY) khả năng của ES cung cấp cách giải thích: “tạo sao nó lại hỏi một câu hỏi nào đó.” Với khả năng này, người dùng cũng có thể theo vết được luồng suy luận của ES và yên tâm hơn với kết quả. Ví dụ: trong phiên làm việc với ES nói trên. ES: Có phải xe car không khởi động được ? Người dùng: WHY ES: “Nếu tôi biết rằng xe car không khởi động được, thì tôi thường cho rằng có vấn đề trong hệ thống điện.” Khi chúng ta hỏi WHY, ES thường đáp trả bằng cách mô tả cái gì mà nó có thể kết luận từ câu trả lời. Hầu hết các ES thường đáp trả bằng cách hiện luật mà nó đang quan tâm. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 143
Cấu trúc của ES. ⚫ Giao diện người dùng: Giao diện cũng là một thành phần quan trọng của ES, nó giúp cho ES có thể đặt câu hỏi với người dùng và nhận về câu trả lời chính xác. Yêu cầu cao nhất cho giao diện là có khả năng cung cấp cách hỏi đáp tương tự như giữa người - với - người. Khi hiện thực hệ thống, vì những hạn chế của kỹ thuật hiện tại nên người thiết kế phải nghĩ đến những hình thức giao tiếp sao cho tiện lợi, tuy chưa thật giống với “người- người”. Cụ thể, có thể dùng giao diện đồ họa , dạng menu chọn, phát âm câu hỏi, cũng cần phải tính đến khả năng dùng web như môi trường tương tác. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 144
Các đặc trưng cơ bản của ES. ⚫ Phân tách tri thức và điều khiển. Đã đề cập trong hệ luật sinh. Đây cũng là đặc điểm phân biệt giữa chương trình truyền thống và ES. Hãy so sánh khả năng thay đổi tri thức của vấn đề giữa hai loại chương trình nói trên. ⚫ Sỡ hữu tri thức chuyên gia. ES có chứa tri thức của lĩnh vực trong CSTT. Nhờ có tri thức mà nó có giá trị. Đặc biệt là tri thức này có thể được nhân ra thành nhiều bản, có thể cập nhật trong khi hệ thống đã được triển khai. ⚫ Tính chuyên gia trong lĩnh vực hẹp. Cũng giống như chuyên gia con người, ES được phát triển nhằm vào một lĩnh vực hẹp. Điều này cũng dễ hiểu, vì lý do: trong lĩnh vực hẹp đó số lượng tri thức cũng nhỏ hơn, và giúp cho người thiết dễ dàng quản lý hơn, dể dàng thử nghiệm chiến lược điều khiển trong động cơ suy diễn. Người thiết thường chia tri thức theo từng mảng như hình sau để quản lý nó. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 145
Các đặc trưng cơ bản của ES. Chuaån ñoaùn xe Heä thoáng ñieän Heä thoáng nhieân lieäu Ac-quy Boä ñaùnh löûa Boä cheá hoaø khí OÁng daãn Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 146
Các đặc trưng cơ bản của ES. ⚫ Suy luận trên ký hiệu. Chúng ta có thể dùng ký hiệu để thể hiện tri thức cho ES. Chính vì vậy mà có thể tận dụng được các giải thuật trên ký hiệu để tri thức thức, như các giải thuật đã đề cập trong chương 2 – phần phép toán vị từ. ⚫ Suy luận có heuristic Chuyên gia con người có thể từ kinh nghiệm của mình để dẫn ra cách giải quyết vấn đề hiệu quả hơn, ví dụ: Khi chuẩn đoán xe, họ có thể giả thiết cách làm: - Luôn luôn kiểm tra luật về hệ thống điện trước các luật khác. Hay một bác sĩ chuyên khoa có thể giả thiết: - Nếu nghi ngờ bị ung thư, thì kiểm tra dòng họ trước. Để có thể hiện thực trong ES, người thiết kế cần phải có cách đánh giá thứ tự ưu tiên của các luật, để từ một ngữ cảnh nào đó có thể chọn một luật có lý nhất để bắt đầu. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 147
Các đặc trưng cơ bản của ES. ⚫ Cho phép suy luận không chính xác. ES có một khả năng rất mạnh đó là: nó có thể làm việc với các vấn đề đang thiếu thông tin, hay có nhưng hổn tạp, không rõ ràng. Cũng giống như trường hợp: một ekip bác sĩ đang phải cứu một bệnh nhân hấp hối, lúc đó họ không còn kịp thời gian để làm tất cả các xét nghiệm cần thiết. Khi thiếu thông tin như vậy họ đành tiến hành những cách có lý nhất theo họ. Chúng ta cũng có thể hiện thực ES có tính chất đó bằng cách đưa vào những luật tương ứng với tình huống thiếu thông tin để động cơ suy diễn vận dụng. ⚫ Bị giới hạn vào vấn đề giải quyết. Không phải mọi vấn đề đều có thể giải quyết bởi ES. Cụ thể, nếu lĩnh vực chúng muốn xây dựng ES hiện tại chưa có, chưa cần một chuyên gia con người thì việc xây dựng ES khó mà thành công. ⚫ Giải quyết các vấn đề có độ phức tạp vừa phải. Nếu vấn đề quá khó, yêu cầu chuyên gia con người đến vài giờ, cần thiết nghĩ đến khả năng chia thành nhiều bài toán con tương ứng mỗi ES. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 148
Các đặc trưng cơ bản của ES. ⚫ Có khả năng bị lỗi. Giống như chuyên gia con người ES có khả năng bị lỗi. Chính vì vậy, cần thiết đưa vào khả năng phục hồi lại lỗi cho ES – ES có khả năng lưu vết quá trình suy luận, nếu nó đưa ra một kết luận mà người dùng kiểm nghiệm với thực tế có sai và báo cho ES, lúc đó nó phải có khả năng ghi nhận và theo đuổi một hướng suy luận khác. đặc điểm này không xuất hiện trong các chương trình truyền thống, nhưng đừng vội kết luận loại chương trình đó tốt hơn. Mỗi loại có những đặc điểm riêng như bảng so sánh sau: CT truyền thống ES Xử lý số Xử lý ký hiệu. Giải thuật Heuristic Tích hợp thông tin+ điều khiển Tách bạch thông tin+ điều khiển Khó thay đổi dễ thay đổi. Thông tin chính xác Thông tin không chắc chắn. Giao diện lệnh điều khiển Hội thoại + giải thích. Kết quả cuối cùng đề nghị + giải thích Tối ưu Có thể chấp nhận. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 149
Công nghệ tri thức. Định nghĩa lại 1. Đánh giá ⚫ Quá trình gồm các giai Các yêu cầu đoạn như hình bên. Các khảo sát khác ⚫ Một số định nghĩa: 2. Thu thập tri thức . Công nghệ tri thức: Tri thức Là quá trình xây dựng Các tinh chỉnh ES. 3. Thiết kế . Thu thập tri thức: Kiến trúc Là quá trình thu thập, tổ 4. Kiểm tra chức và nghiên cứu tri thức. Sự đánh giá 5. Lập tài liệu Sản phẩm 6. Bảo trì Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 150
Các nhân tố trong một dự án ES ⚫ Các nhân tố chính: ⚫ Các yêu cầu cho mỗi nhân tố:  Chuyên gia lĩnh vực. Chuyên gia lĩnh vực:  Kỹ sư tri thức  Có tri thức chuyên gia  Người dùng sản phẩm  Có kỹ năng giải quyết vấn đề hiệu quả  Có thể chuyển giao tri thức  Không chống đối (thân thiện). Kỹ sư tri thức:  Có kỹ năng về công nghệ tri thức  Có kỹ năng giao tiếp tốt.  Có thể làm cho vấn đề được giải quyết bởi phần mềm.  Có kỹ năng lập trình hệ chuyên gia. Người dùng sản phẩm:  Có thể trợ giúp thiết kế giao diện cho ES.  Có thể trợ giúp việc thu thập tri thức.  Có thể trợ giúp trong quá trình phát triển ES. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 151
Các kỹ thuật suy luận ⚫ Suy luận: là quá trình làm việc với tri thức, sự kiện, chiến lược giải toán để dẫn ra kết luận. ⚫ Bạn suy luận như thế nào? Các hình thức cơ bản: Các kỹ thuật cơ bản: Suy luận diễn dịch. . Suy luận tiến (forward-chaing) Suy luận quy nạp. . Suy luận lùi (backward-chaining) Suy luận tương tự. Suy luận khả sai. Suy luận common-sense. .Suy luận đơn điệu .Suy luận không đơn điệu. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 152
Ưu – nhược điểm của mỗi kỹ thuật Suy luận tiến – forward chaining ⚫ Ưu điểm: ⚫ Nhược điểm: . Làm việc tốt với bài toán có bản . Không có cách để nhận thấy tính chất: gôm thông tin và sau đó tìm xem quan trọng của từng sự kiện. Hỏi nhiều câu hỏi thừa, vì đôi lúc chỉ cần một vài có thể suy ra cái gì từ thông tin đó. sự kiện là cho ra kết luận. . Có thể dẫn ra rất nhiều thông tin chỉ . Có thể hỏi những câu hỏi không liên từ một ít sự kiện ban đầu. quan gì nhau – chuổi câu hỏi không ăn . Thích hợp cho một số vấn đề như: nhập nhau. hoạch định, giám sát, điều khiển, diễn VD: dịch. - Bạn có thân nhiệt cao ? - Bạn đến VN đã lâu rồi ? - Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 153
Ưu – nhược điểm của mỗi kỹ thuật Suy luận lùi – backward chaining ⚫ Ưu điểm: ⚫ Nhược điểm: . Làm việc tốt với bài toán có bản . Luôn hướng theo dòng suy luận định chất: thành lập giả thiết , sau đó tìm trước thậm chí có thể dừng và rẽ sang xem có thể chứng minh được không. một goal khác. . Hướng đến một goal nào, nên hỏi → Giải quyết: dùng meta-rule để khắc những câu hỏi có liên quan nhau. phục. . Chỉ khảo sát CSTT trên nhánh vấn Meta-rule: dùng để hướng không gian đề đang quan tâm. tri thức được khảo sát sang một vùng . Tốt cho các vấn đề: chuẩn đoán, kê khác. toa, gỡ rối. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 154
Khảo sát ES: MYCIN ⚫ Giới thiệu: ⚫ Các đặc điểm chính: . Là ES về lĩnh vực chuẩn đoán bệnh . Sử dụng kỹ thuật suy luận lùi. nhiễm trùng nháu. . Có khả năng phân tách tri thức và . Được phát triển vào khoảng năm điều khiển. 1970, tại đại học Standford . Là thước đo cho nhiều ES dựa trên . Có tích hợp Meta-rule. luật sau này. . Có thể dùng khi thiếu thông tin hay . Được viết trên ngôn ngữ thông tin không chính xác. INTERLISP, một nhánh của LISP. . Có khả năng nhớ được các thông tin . Người ta từ MYCIN, tước bỏ phần trong một phiên làm việc với người CSTT của nó để được một hệ thống bệnh cụ thể. EMYCIN (empty MYCIN), dùng để . Dể sử dụng – giao tiếp với bác sĩ qua phát triển các ES khác. tiếng anh. . Cung cấp các chức năng giải thích: WHY, HOW. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 155
Khảo sát ES: MYCIN ⚫ Một phiên làm việc cụ thể với MYCIN ? MYCIN cố gắng xác định bản chất lây (“Expert System”. Author: John Durkin) nhiễm. đã được Việt hóa. 5. MYCIN: Có bất kỳ phép cấy vi khuẩn ? Một vài thông tin về bệnh nhân: cho Jack Durkin liên qua đến bệnh hiện tại? 1. MYCIN: Họ tên ? USER: Có USER: Jack Durkin. 6. MYCIN: Mẫu vật lấy từ đâu? 2. MYCIN: Tuổi ? USER: CSF USER: 24 7. MYCIN: Ngày, giờ thực hiện cấy? 3. MYCIN: Giới tính ? USER: 7- July-7:00 USER: Nam . 4. MYCIN: Chủng tộc? MYCIN: Gần đây Jack Durkin có các triệu chứng như: choáng ván, hôn mê USER: CAUCASIAN không? USER: Có. . Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 156
Khảo sát ES: XCON ⚫ Giới thiệu: . Là ES về lĩnh vực hướng dẫn cấu hình các hệ thống máy tính của DEC trước khi xuất xưởng. . Được phát triển vào khoảng năm 1980, tại đại học CMU . Được công bố giảm thời gian cấu hình cho mỗi hệ thống xuống còn 2 phút (so với 25 phút bằng tay.). Tiết kiệm vào khoảng 25 triệu $ cho mỗi năm. (Theo “Expert System” – John Durkin) Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 157
Hệ chuyên gia dựa trên luật ⚫ Định nghĩa: Là một chương trình máy tính, xử lý các thông tin cụ thể của bài toán được chứa trong bộ nhớ làm việc và tập các luật được chứa trong CSTT, sử dụng động cơ suy luận để suy ra thông tin mới. ES dựa trên luật: có nền tảng xây dựng lá hệ luật sinh – chương trước. ES dựa trên luật cũng có những đặc trưng cơ bản như đã nêu trong phần trước cho các ES tổng quát, một vài đặc điểm: . Có CSTT chứa các luật. . Có bộ nhớ làm việc tạm thời. . Có động cơ suy luận. . Có một giao diện để giao tiếp với người dùng, người phát triển. . Có tiện ích giải thích. . Có khà năng giao tiếp với chương trình ngoài như: các DBMS, xừ lý bảng tính, Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 158
Hệ chuyên gia dựa trên luật ⚫ Kiến trúc: (như hình sau) ⚫ Nguyên lý hoạt động tương tự hệ luật sinh đã giới thiệu. Boä nhôù laøm vieäc Boä giao tieáp Ñoäng cô Giao dieän chöông trình Ngöôøi duøng suy luaän ngöôøi duøng ngoaøi Ngöôøi phaùt trieån Giao dieän Cô sôõ tri thöùc Boä giaûi thích Ngöôøi phaùt trieån Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 159
Hệ chuyên gia dựa trên luật ⚫ Ưu điểm ⚫ Nhược điểm . Biểu diễn tri thức tự nhiên: IF . Các fact muốn đồng nhất nhau, phải THEN. khớp nhau hoàn toàn → Các facts cùng một ý nghĩa phải giống nhau về cú . Phân tách tri thức – điều khiển. pháp, ngôn ngữ tự nhiên không như . Tri thức là tập các luật có tính độc vậy. lập cao -> dễ thay đổi, chỉnh sữa. . khó tìm mối qua hệ giữa các luật . Dễ mở rộng. trong một chuổi suy luận, vì chúng có thể nằm rải rác trong CSTT. . Tận dụng được tri thức heuristic. . Có thể hoạt động chậm. . Có thể dùng biến trong luật, tri xuất . Làm cho nhà phát triển phải hình chương trình ngoài. chung mọi cái ở dạng luật -→ không phải bài toán nào cũng có thể làm được như thế này. Ñaïi Hoïc Baùch Khoa Tp.HCM – 2001 Baûn quyeàn © Khoa Coâng Ngheä Thoâng Tin Baøi giaûng “Trí tueä nhaân taïo” - Slide 160