BG trí tuệ nhân tạo, Trần Thị Hương, PDF, 100 trang, 2 MB
NỘI DUNG:
Trí tuệ nhân tạo – Các phương pháp Giải quyết vấn đề và kỹ thuật xử lý tri thức (1999) Nguyễn Thanh Thuỷ 2. Trí tuệ nhân tạo – Đinh Mạnh Tường 3 KHỐI LƯỢNG & CẤU TRÚC HỌC PHẦN □ Số đơn vị học trình: 3 □ Lý thuyết: 30 tiết □ Thực hành, bài tập: 15tiết 4 CHƯƠNG 1: TỔNG QUAN VỀ KHOA HỌC TTNT 5 Trí Tuệ Nhân Tạo là gì? □ Là một nhánh của khoa học máy tính liên quan đến sự tự động hóa hành vi thông minh. Trí tuệ là gì? □ Các câu hỏi chưa có câu trả lời: ∎ Liệu trí tuệ có phải là một khả năng duy nhất hay chỉ là một tên gọi cho một tập hợp các hành vi phân biệt và độc lập nhau? ∎ Thế nào là khả năng sáng tạo? ∎ Thế nào là trực giác? ∎ Điều gì diễn ra trong quá trình học? 6 Trí Tuệ Nhân Tạo là gì? □ Intelligence? Trí năng, trí tuệ, trí thông minh □ Thế nào là Artificial intelligence? Chúng ta sẽ phân tích 4 loại quan niệm về intelligence sau: 7 Trí Tuệ Nhân Tạo là gì? "Nỗ lực tạo ra các máy tính biết tư duy ... máy tính có ý thức (The exciting new effort to make computers thinks ... machine with minds, in the full and literal sense)" (Haugeland 1985) "Nghệ thuật sáng tạo ra các máy thực hiện các chức năng đòi hỏi sự thông minh như khi thực hiện bởi con người (The art of creating machines that perform functions that require intelligence when performed by people)" (Kurzweil, 1990) "Việc nghiên cứu các năng lực trí tuệ sử dụng các mô hình tính toán (The study of mental faculties through the use of computational models)" (Charniak et al. 1985) "Nghiên cứu tìm cách giải thích và mô phỏng các hành vi thông minh bằng các quá trình tính toán (A field of study that seeks to explain and emulate intelligent behavior in terms of computational processes)" (Schalkol, 1990) 8 Trí tuệ nhân tạo: Hệ thống tư duy như con người "Nỗ lực tạo ra các máy tính biết tư duy ... máy tính có ý thức (The exciting new effort to make computers thinks ... machine with minds, in the full and literal sense)" (Haugeland 1985) Hệ thống tư duy như con người (Systems that think like humans) Con người tư duy như thế nào? Chưa có câu trả lời chính xác trong rất nhiều tình huống. Ví dụ: Newell&Simson (1961) phát triển GPS (General Problem Solving) bắt chước cách giải quyết các bài toán trong toán học của con người. 9 Trí tuệ nhân tạo: hệ thống ứng xử như con người Hệ thống ứng xử (hành động) như con người (Hệ thống mà hành vi, ứng xử của nó như con người) Systems that act like humans "Nghệ thuật sáng tạo ra các máy thực hiện các chức năng đòi hỏi sự thông minh như khi thực hiện bởi con người (The art of creating machines that perform functions that require intelligence when performed by people)" (Kurzweil, 1990) Turing (1950) đề xuất bộ test (Turing test): hội thoại giữa hệ thống và người phỏng vấn. Nếu người phỏng vấn không biết được hệ thống là người hay là máy thì hệ thống đó được cho là thông minh. - Con người lúc nào cũng ứng xử "đúng"? - Hành vi như thế nào được coi là giống con người? Trí tuệ nhân tạo: hệ thống tư duy hợp lý Hệ thống tư duy hợp lý "Việc nghiên cứu các năng lực trí tuệ sử dụng các mô hình tính toán System that think (The study of mental faculties rationally through the use of computational models)" Aristotle hình thức hóa (Charniak et al. 1985) "tư duy đúng" (Luật của tư duy đúng). Hệ tam đoạn luận là khuôn mẫu để thu được kết luận đúng khi cho giả thiết đúng. VD: Socrat là người; tất cả mọi người đều chết; do đó Socrat phải chết. 1. Không biểu diễn được tri thức không chắc chắn 2. Nhiều bài toán không dễ giải quyết do thiếu tài nguyên (không gian nhớ và thời gian) 3. Nhiều hành động coi là thông minh nhưng ko liên quan đến tư duy (chẳng hạn: co tay lại khi chạm vật nóng) Trí tuệ nhân tạo: hệ thống ứng xử hợp lý Hệ thống ứng xử hợp lý (Hệ thống mà hành động/ứng xử hợp lý) Systems that act rationally Ưu điểm: -Tổng quát hơn -Tính hợp lý có thể dễ dàng được định nghĩa (rationality is well defined) CS 460, Lecture 1 "Nghiên cứu tìm cách giải thích và mô phỏng các hành vi thông minh bằng các quá trình tính toán (A field of study that seeks to explain and emulate intelligent behavior in terms of computational processes)" (Schalkol, 1990) Artificial Intelligence: Hành động hợp lý □ Intelligence? Trí năng, trí tuệ, trí thông minh □ Môn học này, chúng ta thống nhất quan niệm trí thông minh là hành động hợp lý, hành động tốt nhất hoặc hợp lý nhất mà cho kết quả tối ưu của một hàm nào đó. □ Quan niệm như trên phù hợp với: khi nói đến tính thông minh, chúng ta thường gắn với một hành động, hành vi, ứng xử nào đó. Vi vậy Intelligence có thể coi đồng nghĩa với rational action, hay intelligent/rational agent Turing Test □ Interrogator Ưu điểm của Turing Test ∎ Khái niệm khách quan về trí tuệ ∎ Tránh đi những thảo luận về quá trình bên trong và ý thức ∎ Loại trừ định kiến thiên vị của người thẩm vấn Các ý kiến phản đối Turing Test □ Thiên vị các nhiệm vụ giải quyết vấn đề bằng ký hiệu □ Trói buộc sự thông minh máy tính theo kiểu con người, trong khi con người có: ∎ Bộ nhớ giới hạn ∎ Có khuynh hướng nhầm lẫn Tuy nhiên, trắc nghiệm Turing đã cung cấp một cơ sở cho nhiều sơ đồ đánh giá dùng thực sự cho các chương trình TTNT hiện đại. Các Ứng Dụng của TTNT 1. Trò chơi và các bài toán đố 2. Suy luận và chứng minh định lý tự động 3. Các hệ chuyên gia (các hệ tri thức) 4. Xử lý ngôn ngữ tự nhiên 5. Lập kế hoạch và người máy 6. Máy học 7. Mạng Neuron và giải thuật di truyền 8. ... Trí Tuệ Nhân Tạo - Đặc Điểm □ Sử dụng máy tính vào suy luận trên các ký hiệu, nhận dạng qua mẫu, học, và các suy luận khác... □ Tập trung vào các vấn đề "khó" không thích hợp với các lời giải mang tính thuật toán. □ Quan tâm đến các kỹ thuật giải quyết vấn đề sử dụng các thông tin không chính xác, không đầy đủ, mơ hồ... □ Cho lời giải 'đủ tốt' chứ không phải là lời giải chính xác hay tối ưu. □ Sử dụng heuristics – "bí quyết" □ Sử dụng tri thức chuyên môn □ ... Những vấn đề chưa được giải quyết □ Chương trình chưa tự sinh ra được heuristic □ Chưa có khả năng xử lý song song của con người □ Chưa có khả năng diễn giải một vấn đề theo nhiều phương pháp khác nhau như con người. □ Chưa có khả năng xử lý thông tin trong môi trường liên tục như con người. □ Chưa có khả năng học như con người. □ Chưa có khả năng tự thích nghi với môi trường. Các phương pháp và kỹ thuật □ Các phương pháp biểu diễn tri thức và kỹ thuật xử lý tri thức □ Các phương pháp giải quyết vấn đề □ Các phương pháp Heuristic □ Các phương pháp học □ Các ngôn ngữ TTNT 19 Các phương pháp và kỹ thuật □ Các phương pháp biểu diễn tri thức và kỹ thuật xử lý tri thức □ Các phương pháp giải quyết vấn đề □ Các phương pháp Heuristic □ Các phương pháp học □ Các ngôn ngữ TTNT 20 CÁC TIỀN ĐỀ CƠ BẢN CỦA TTNT Nghiên cứu tâm trí con người Nghiên cứu ý nghĩa và cấu trúc của ngôn ngữ TTNT kế thừa nhiều ý tưởng, quan điểm và các kỹ thuật từ các ngành khoa học khác TTNT Ngôn ngữ học Khoa học máy tính Các lý thuyết của lập luận và học Các lý thuyết xác suất logic, tạo quyết định và tính toán Làm cho TTNT trở thành hiện thực Toán học 21 LỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNT 22 CÁC THÀNH TỰU CỦA KHOA HỌC TTNT 23 CÁC THÀNH TỰU CỦA KHOA HỌC TTNT 24 CÁC THÀNH TỰU CỦA KHOA HỌC TTNT 25 CÁC THÀNH TỰU CỦA KHOA HỌC TTNT SONY AIBO 26 CÁC THÀNH TỰU CỦA KHOA HỌC TTNT Honda Humanoid Robot & Asimo Đi bộ Quay Lên xuống cầu thang 27 CÁC THÀNH TỰU CỦA KHOA HỌC TTNT 28 CÁC THÀNH TỰU CỦA KHOA HỌC TTNT 29 CÁC XU HƯỚNG MỚI TRONG TTNT 30 CÁC XU HƯỚNG MỚI TRONG TTNT 31 CÁC XU HƯỚNG MỚI TRONG TTNT 32 CÁC XU HƯỚNG MỚI TRONG TTNT 33 CÁC XU HƯỚNG MỚI TRONG TTNT 34 CÁC XU HƯỚNG MỚI TRONG TTNT 35 CÁC XU HƯỚNG MỚI TRONG TTNT 36 Chương 2. CÁC CHIẾN LƯỢC TÌM KIẾM MÙ I. Biểu diễn vấn đề trong KG trạng thái. □ Vấn đề là gì? □ Một bài toán nào đó cần giải quyết, chẳng hạn như một trò chơi, c.minh một định lý,... □ Một lớp rộng các bài toán có thể giải quyết bằng cách biểu diễn bởi các trạng thái và các tóan tử (phép biến đổi trạng thái). Ví dụ (trò chơi 8 số) Các thành phần của KGTT □ Sự sắp xếp các số tại mỗi thời điểm là một TT. □ Hình bên trái là trạng thái ban đầu. □ Hình bên phải là trạng thái kết thúc hay trạng thái đích (goal). □ Trạng thái đích của một bài toán có thể nhiều hơn một. Toán □ tử là một phép biển đổi hợp lệ chuyển từ trạng thái này sang trạng thái khác. □ Bằng các tóan tử, từ trạng thái ban đầu, tiếp tục phát triển, cuối cùng thu được một không gian trạng thái (KGTT). Định nghĩa □ KGTT là một bộ bốn (X, u0, F, G), trong đó: X là tập các trạng thái u0 là trạng thái bắt đầu F là tập các toán tử, gồm các phép biến đổi. G là tập trạng thái đích. Biểu diễn KGTT □ Không gian trạng thái có thể biểu diễn bằng đồ thị có hướng: mỗi đỉnh là một trạng thái, mỗi cung là một toán tử. □ Nghiệm của bài toán nếu như ta tìm được đường đi từ trạng thái bắt đầu đến một trong các trạng thái đích. Biểu diễn bằng cây □ Trong đồ thị của KGTT có thể xuất hiện chu trình gây khó khăn cho việc tìm kiếm, hạn chế các toán tử trong F có thể đưa đồ thị trở thành cây, một cấu trúc dễ tìm kiếm hơn. □ VD. KGTT của trò chơi caro là cây. Chiến lược tìm kiếm? □ Khi tìm kiếm lời giải, từ một trạng thái nào đó chưa phải là trạng thái đích, ta dựa theo toán tử sinh ra tập các trạng thái mới: mở rộng. □ Để được lời giải, ta phải liên tục chọn trạng thái mới, mở rộng, kiểm tra cho đến khi tìm được trạng thái đích hoặc không mở rộng được KGTT. □ Tập các trạng thái được mở rộng sẽ có nhiều phần tử, việc chọn trạng thái nào để tiếp tục mở rộng được gọi là chiến lược tìm kiếm. Đánh giá một chiến lược? + Tính đầy đủ: chiến lược phải đảm bảo tìm được lời giải nếu có. + Độ phức tạp thời gian: mất thời gian bao lâu để tìm được lời giải. + Độ phức tạp không gian: tốn bao nhiêu đơn vị bộ nhớ để tìm được lời giải. + Tính tối ưu: tốt hơn so với một số chiến lược khác hay không. Thông tin mỗi nút? + Nội dung trạng thái mà nút hiện hành đang biểu diễn. + Nút cha đã sinh ra nó. + Toán tử đã được sử dụng để sinh ra nút hiện hành. + Độ sâu của nút. + Giá trị đường đi từ nút gốc đến nút hiện hành. Tìm kiếm mù? □ Trạng thái được chọn để phát triển chỉ đơn thuần dựa theo cấu trúc của KGTT mà không có thông tin hướng dẫn nào khác. □ Nói chung tìm kiếm mù sẽ không hiệu quả. □ Đây là cơ sở để chúng ta cải tiến và thu được những chiến lược hiệu quả hơn. 1. Tìm kiếm theo chiều rộng (BFS) □ Trạng thái được ưu tiên phát triển là trạng thái được sinh ra trước. □ Dùng danh sách open chứa các trạng thái sinh ra đang chờ phát triển □ Danh sách closed chứa các trạng thái đã được khảo sát. Ví dụ Thuật toán BFS procedure bfs; begin open:=[start]; closed:=[]; while open<>[] do begin loại tt ngoài cùng bên trái của open, gọi nó là u if (u là một đích) then thông báo kết quả, thoát else begin Đưa u vào closed Phát sinh các con v của u Loại các con đã có trong open+closed Đưa các con còn lại vào bên phải open (1) end end Thông báo thất bại End Open 1. = [A]; closed = [] 2. Open = [B,C,D]; closed = [A] 2. Open = [C,D,E,F]; closed = [B,A] 3. Open = [D,E,F,G,H]; closed = [C,B,A] 4. Open = [E,F,G,H,I,J]; closed = [D,C,B,A] 5. Open = [F,G,H,I,J,K,L]; closed = [E,D,C,B,A] 6. Open = [G,H,I,J,K,L,M]; (vì L đã có trong open); closed = [F,E,D,C,B,A] ... Nhận xét □ Các trạng thái con phát sinh nhờ các toán tử hợp lệ. □ Danh sách open bổ sung phần tử bên phải, lấy phần tử bên trái. □ Thuật tóan khảo sát tất cả các nút ở độ sâu d sau đó mới đến mức d+1 nên chắc chắn tìm được nghiệm. □ Nếu vô nghiệm và KGTT hữu hạn thì thuật toán sẽ dừng và thông báo vô nghiệm. Đánh giá □ Giả sử mỗi trạng thái trung bình sinh ra b trạng thái con (kề), b - gọi là nhân tố nhánh. □ Giả sử đường đi nghiệm có độ dài d. Tình trạng xấu nhất phải khảo sát là ? □ Độ phức tạp thời gian là O(b^d), độ phức tạp không gian cũng là O(b^d). 55 2. Tìm kiếm theo chiều sâu (DFS) □ Mở rộng nút có độ sâu hơn trước các nút khác đang chờ xử lý. □ Khi nào không mở rộng được nữa thì mới quay lại nút ở độ sâu thấp hơn. □ Do đó, các nút mới được sinh ra chờ xử lý phải được bỏ bên trái của hàng đợi open (tại câu lệnh 1). 56 Thuật toán DFS procedure bfs; begin open:=[start]; closed:=[]; while open<>[] do begin loại tt u ngoài cùng bên trái của open if (u là một đích) then thông báo kết quả, thoát else begin Đưa u vào closed Phát sinh các con v của u Loại các con đã có trong open+closed Đưa các con còn lại vào bên trái open (1) end end Thông báo thất bại End 57 Tìm kiếm Sâu 1. Open = [A]; closed = [] 2. Open = [B,C,D]; closed = [A] 3. Open = [E,F,C,D];closed = [B,A] 4. Open = [K,L,F,C,D]; closed = [E,B,A] 5. Open = [S,L,F,C,D]; closed = [K,E,B,A] 6. Open = [L,F,C,D]; closed = [S,K,E,B,A] 7. Open = [T,F,C,D]; closed = [L,S,K,E,B,A] 8. Open = [F,C,D]; closed = [T,L,S,K,E,B,A] 9. ... 58 Nhận xét □ Khảo sát nút ở độ sâu d thì DFS lưu trữ b*d nút, khi đó BFS phải lưu trữ b^d nút. □ Ở độ sâu d=12, DFS chỉ sử dụng 12KB trong khi BFS dùng đến 111TB. □ Độ phức tạp thời gian của DFS vẫn là O(b^d) vì trong trường hợp xấu nhất các nút được khảo sát vẫn như BFS. □ Cơ hội để tìm thấy đích nhanh hơn nếu nó nằm ở phần KGTT bên trái. 59 Hạn chế □ Bỏ qua cơ hội tìm thấy ngay trạng thái đích khi trạng thái này nằm gần gốc. □ Nếu KGTT vô hạn có thể không tìm được trạng thái đích. □ Nghiệm nói chung không phải là đường đi ngắn nhất. □ DFS là chiến lược không đầy đủ, không tối ưu. Không nên sử dụng khi KGTT có độ sâu lớn hoặc vô hạn. 60 Tìm kiếm sâu bằng cách đào sâu nhiều lần □ Độ sâu giới hạn (depth bound): giải thuật TK sâu sẽ quay lui khi trạng thái đang xét đạt đến độ sâu giới hạn đã định. □ TK Sâu bằng cách đào sâu nhiều lần: TK sâu với độ sâu giới hạn là 1, nếu thất bại, nó sẽ lặp lại GT TK sâu với độ sâu là 2,... GT tiếp tục cho đến khi tìm được mục tiêu, mỗi lần lặp lại tăng độ sâu lên 1. □ GT này có độ phức tạp về thời gian cùng bậc với TK Rộng và TK Sâu. 61 Thuật toán procedure DFS(d); begin open:=[start]; closed:=[]; depth(start):=0; while open<>[] do begin loại u ngoài cùng bên trái open if (u là một đích) then thbáo kết quả, thoát else 62 begin Đưa u vào closed If depth(u)[] do begin loại tt ngoài cùng bên trái của open, gọi nó là u if (u là một đích) then thông báo kết quả, thoát else begin Đưa u vào closed Phát sinh các con v của u Loại các con đã có trong open+closed Sap xep danh sach cac dinh con cua u theo thu tu tang dan, goi la L1. Day L1 vao ben trai danh sach open. end end 93 B1: open =[A], close=[] B2: close=[A], open=[C] B3: close=[A,C], open=[G]; B4: Thông báo thành công 94 Yêu cầu: áp dụng thuật toán leo đồi mô tả không gian trạng thái qua các bước. Vẽ đồ thị đường đi Nhanh, có thể thất bại □ Hiệu quả khi có một hàm đánh giá tốt. Bế tắc nếu ∎ Gặp điểm cực đại địa phương. ∎ Khu vực bình nguyên. □ Giải pháp xáo trộn ngẫu nhiên. □ Không có giải pháp tổng quát. Cải tiến? 96 Tìm kiếm ưu tiên tốt nhất – Best First Search (Best-FS) □ Chọn trạng thái tốt nhất trong open để phát triển, kể cả trạng thái này không tốt bằng trạng thái đã sinh ra nó. □ Lưu trữ tất cả các trạng thái anh em nên khi đi vào ngõ cụt, chiến lược này có thể lui ra được mà không bị bế tắc. □ Best-FS kết hợp tìm kiếm sâu và rộng. □ Best-FS "cẩn thận" hơn ghi nhớ lại các một số trạng thái không tốt hơn trước đó để còn có thể quay lại. 97 Ví dụ 98 99 Thuật toán Best_FS procedure Best_FS; begin open:={u0}; closed:={ }; while open<>{ } do begin loại trạng thái ngoài cùng bên trái của open, gọi nó là u if (u là một đích) then thông báo thắng lợi, thoát else begin Đưa u vào closed Phát sinh các con v của u Loại các con v đã có mặt trong open + closed Đưa các con còn lại vào open Sắp xếp open sao cho phần tử tốt nhất nằm bên trái end end Thông báo thất bại end 100
XEM VÀ TẢI VỀ:
[linkxem]https://drive.google.com/file/d/1cH69cIBnhFT8RnQLI-Rr6zq1nWpUapS2/preview[/linkxem][linktai]https://drive.google.com/file/d/1cH69cIBnhFT8RnQLI-Rr6zq1nWpUapS2/view[/linktai]
