Bài giảng Trí tuệ nhân tạo - Lec 1+2 - Phạm Thị Anh Lê

Nội dung text: Bài giảng Trí tuệ nhân tạo - Lec 1+2 - Phạm Thị Anh Lê

1. Khoa Công nghệ thông tin Trường Đại học Sư phạm Hà nội TRÍ TUỆ NHÂN TẠO Artificial Intelligence Phạm Thị Anh Lê Khoa CNTT - ĐHSP Hà nội TTNT. p.1
2. Nội Dung  Lec 1. Giới thiệu về TTNT, các khái niệm cơ bản  Lec 2. Agent thông minh  Lec 3. Giải quyết bài toán bằng tìm kiếm: tìm kiếm mù  Lec 4. Tìm kiếm kinh nghiệm (heuristics)  Lec 5. Tìm kiếm có đối thủ  Lec 6. Logic mệnh đề  Lec 7-8. Logic vị từ cấp một  Lec 9-10. Biểu diễn tri thức bởi các luật và lập luận  Lec 11-13. Lập trình logic Prolog  Lec 14-15. Tri thức không chắc chắn: logic xác suất, logic mờ TTNT. p.2
3.  Tài liệu tham khảo: – Trí tuệ nhân tạo, by Đinh Mạnh Tường – 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, by Nguyễn Thanh Thủy – Artificial Intelligence: A Modern Approach, by Stuart Russell and Peter Norvig. (2nd ed) – Citeseer - Scientific Literature Digital Library. Artificial Intelligence- - 2003 TTNT. p.3
4. Overview (Giới thiệu tổng quan) General Introduction 01-Introduction. [AIMA Ch 1] Course Schedule. Homeworks, exams and grading. Course material, TAs and office hours. Why study AI? What is AI? The Turing test. Rationality. Branches of AI. Research disciplines connected to and at the foundation of AI. Brief history of AI. Challenges for the future. Overview of class syllabus. Agent sensors effectors  02-Intelligent Agents. [AIMA Ch 2] What is an intelligent agent? Examples. Doing the right thing (rational action). Performance measure. Autonomy. Environment and agent design. Structure of agents. Agent types. Reflex agents. Reactive agents. Reflex agents with state. Goal-based agents. Utility-based agents. Mobile CS 460, Lecture 1 TTNT. p. agents. Information agents. 4
5. Overview (cont.) How can we solve complex problems?  03/04-Problem solving and search. [AIMA Ch 3] 9 l Example: measuring problem. Types of problems. 3 l 5 l More example problems. Basic idea behind search Using these 3 buckets, algorithms. Complexity. Combinatorial explosion measure 7 liters of water. and NP completeness. Polynomial hierarchy.  05-Uninformed search. [AIMA Ch 3] Depth-first. Breadth-first. Uniform-cost. Depth-limited. Iterative deepening. Examples. Properties.  06/07-Informed search. [AIMA Ch 4] Best-first. A* search. Heuristics. Hill climbing. Problem of local extrema. Simulated annealing. Traveling salesperson problem CS 460, Lecture 1 TTNT. p.5
6. Overview (cont.) Practical applications of search.  08/09-Game playing. [AIMA Ch 5] The minimax algorithm. Resource limitations. Aplha- beta pruning. Elements of chance and non- deterministic games. tic-tac-toe CS 460, Lecture 1 TTNT. p.6
7. Overview (cont.) Towards intelligent agents  10-Agents that reason logically 1. [AIMA Ch 6] Knowledge-based agents. Logic and representation. Propositional (boolean) logic.  11-Agents that reason logically 2. [AIMA Ch 6] Inference in propositional logic. Syntax. Semantics. wumpus world CS 460, Lecture 1 Examples. TTNT. p.7
8. Overview (cont.) Building knowledge-based agents: 1st Order Logic  12-First-order logic 1. [AIMA Ch 7] Syntax. Semantics. Atomic sentences. Complex sentences. Quantifiers. Examples. FOL knowledge base. Situation calculus.  13-First-order logic 2. [AIMA Ch 7] Describing actions. Planning. Action sequences. CS 460, Lecture 1 TTNT. p.8
9. Overview (cont.) Representing and Organizing Knowledge  14/15-Building a knowledge base. [AIMA Ch 8] Knowledge bases. Vocabulary and rules. Ontologies. Organizing knowledge. An ontology for the sports domain , 2000 Mcleod Kahn & CS 460, Lecture 1 TTNT. p.9
10. Overview (cont.) Reasoning Logically  16/17/18-Inference in first-order logic. [AIMA Ch 9] Proofs. Unification. Generalized modus ponens. Forward and backward chaining. Example of backward chaining CS 460, Lecture 1 TTNT. p.10
11. Overview (cont.) Examples of Logical Reasoning Systems  19-Logical reasoning systems. [AIMA Ch 10] Indexing, retrieval and unification. The Prolog language. Theorem provers. Frame systems and semantic networks. Semantic network used in an insight generator (Duke university) CS 460, Lecture 1 TTNT. p.11
12. Overview (cont.) Systems that can Plan Future Behavior  20-Planning. [AIMA Ch 11] Definition and goals. Basic representations for planning. Situation space and plan space. Examples. CS 460, Lecture 1 TTNT. p.12
13. Overview (cont.) Expert Systems  21-Introduction to CLIPS. [handout] Overview of modern rule-based expert systems. Introduction to CLIPS (C Language Integrated Production System). Rules. Wildcards. Pattern matching. Pattern network. Join network. CS 460, Lecture 1 CLIPS expert system shell TTNT. p.13
14. Overview (cont.) Logical Reasoning in the Presence of Uncertainty  22/23-Fuzzy logic. [Handout] Introduction to Center of gravity fuzzy logic. Linguistic Hedges. Fuzzy inference. Examples. Center of largest area CS 460, Lecture 1 TTNT. p.14
15. Overview (cont.) AI with Neural networks  24/25-Neural Networks. [Handout] Introduction to perceptrons, Hopfield networks, self-organizing feature maps. How to size a network? What can neural x (t) networks achieve? 1 w1 x 2 (t) w axon 2  y(t+1) w n CS 460, Lecturex n (t) 1 TTNT. p.15
16. Overview (cont.) Evolving Intelligent Systems  26-Genetic Algorithms. [Handout] Introduction to genetic algorithms and their use in optimization problems. CS 460, Lecture 1 TTNT. p.16
17. Overview (cont.) What challenges remain?  27-Towards intelligent machines. [AIMA Ch 25] The challenge of robots: with what we have learned, what hard problems remain to be solved? Different types of robots. Tasks that robots are for. Parts of robots. Architectures. Configuration spaces. Navigation and motion planning. Towards highly-capable robots.  28-Overview and summary. [all of the above] What have we learned. Where do we go from here? CS 460, Lecture 1 robotics@USC TTNT. p.17
18. Artificial Intelligence?  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: CS 460, Lecture 1 TTNT. p.18
19. Trí tuệ nhân tạo là gì? “Nỗ lực tạo ra các máy tính “Việc nghiên cứu các năng lực trí biết tư duy máy tính có ý tuệ sử dụng các mô hình tính toán thức (The exciting new effort (The study of mental faculties to make computers thinks through the use of computational machine with minds, in the full models)” and literal sense)” (Charniak et al. 1985) (Haugeland 1985) “Nghệ thuật sáng tạo ra các “Nghiên cứu tìm cách giải thích và máy thực hiện các chức năng mô phỏng các hành vi thông minh đòi hỏi sự thông minh như khi bằng các quá trình tính toán (A field thực hiện bởi con người (The of study that seeks to explain and art of creating machines that emulate intelligent behavior in terms perform functions that require of computational processes)” intelligence when performed (Schalkol, 1990) by people)” (Kurzweil, 1990)CS 460, Lecture 1 TTNT. p.19
20. 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 Hệ thống tư duy như con biết tư duy máy tính có ý người thức (The exciting new effort (Systems that think to make computers thinks ) machine with minds, in the full like humans and literal sense)” (Haugeland 1985) Ví dụ: Newell&Simson (1961) phát triển GPS Con người tư duy như thế (General Problem Solving) nào? Chưa có câu trả lời bắt chước cách giải quyết chính xác trong rất nhiều các bài toán trong toán học tình huống. của con người. CS 460, Lecture 1 TTNT. p.20
21. 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à Turing (1950) đề xuất hành vi, ứng xử của nó như con bộ test (Turing test): hội người) thoại giữa hệ thống và người phỏng vấn. Nếu Systems that act like người phỏng vấn không biết được hệ thống là humans người hay là máy thì hệ “Nghệ thuật sáng tạo ra các thống đó được cho là máy thực hiện các chức năng thông minh. đòi hỏi sự thông minh như khi thực hiện bởi con người (The - Con người lúc nào cũng art of creating machines that ứng xử “đúng”? perform functions that require - Hành vi như thế nào được intelligence when performed coi là giống con người? CS 460, Lecture 1 TTNT. p. by people)” (Kurzweil, 1990) 21
22. 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 1. Không biểu diễn được tri thức tư duy đúng). Hệ tam không chắc chắn đoạn luận là khuôn mẫu 2. Nhiều bài toán không dễ giải để thu được kết luận quyết do thiếu tài nguyên đúng khi cho giả thiết (không gian nhớ và thời gian) đúng. VD: Socrat là 3. Nhiều hành động coi là thông người; tất cả mọi người minh nhưng ko liên quan đến đều chết; do đó Socrat tư duy (chẳng hạn: co tay lại khi chạm vật nóng) phải chết. CS 460, Lecture 1 TTNT. p.22
23. 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: “Nghiên cứu tìm cách giải thích và -Tổng quát hơn mô phỏng các hành vi thông minh -Tính hợp lý có thể dễ bằng các quá trình tính toán (A field dàng được định nghĩa of study that seeks to explain and (rationality is well emulate intelligent behavior in terms defined) of computational processes)” (Schalkol, 1990) CS 460, Lecture 1 TTNT. p.23
24. Trí tuệ nhân tạo: Hệ thống hành động hợp lý Systems that think like Systems that think humans rationally Systems that act like Systems that act humans rationally Rational (artificial) agent An agent is just something that act (agent comes from the Latin agere, to do) CS 460, Lecture 1 TTNT. p.24
25. AI: 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 đó.  (In this class, we adopt the view that intelligence is concerned mainly with rational action, Ideally, an rational agent takes the best possible action in a situation.)  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 đó. Vì vậy Intelligence có thể coi đồng nghĩa với rational action, hay intelligent/rational agent CS 460, Lecture 1 TTNT. p.25
26. AI Prehistory Triết học (Philosophy, 428 B.C – Present): -Các luật hình thức có thể được sử dụng để rút ra kết luận hợp lý không? -Ý thức được sản sinh như thế nào từ não? -Tri thức từ đâu đến? -Làm thế nào tri thức dẫn dắt hành động? Toán học (Mathematics, C. 800 – Present): -Những luật hình thức nào để rút ra kết luận hợp lý? -Chúng được tính toán như thế nào? -Làm thế nào chúng ta lập luận với tri thức không chắc chắn? Kinh tế học (Economics, 1776 – Present): -Chúng ta nên làm ra các quyết như thế nào để làm tối đa lợi ích? -How should we do this when others may not go along? -How should we do this when the payoff may be far in the future? CS 460, Lecture 1 TTNT. p.26
27. AI Prehistory Khoa học về thần kinh (Neuronscience,1861 – Present): -Bộ não xử lý thông tin như thế nào? Tâm lý học (Psychology, 1879 – Present): -Con người và động vật tư duy và hành động như thế nào? Công nghệ máy tính (Computer engineering 1940 – Present): -Làm thế nào chúng ta xây dựng máy tính hiệu quả? Điều khiển học (Control theory and cybernetics 1948 – Present): -Làm thế nào các máy nhân tạo vận hành dưới sự điều khiển của chính nó? Ngôn ngữ học (Linguistics 1957 – Present): -Ngôn ngữ liên quan đến tư duy như thế nào? CS 460, Lecture 1 TTNT. p.27
28. AI Prehistory CS 460, Lecture 1 TTNT. p.28
29. AI History CS 460, Lecture 1 TTNT. p.29
30. AI State of the art (Những tiến bộ gần đây của AI)  Have the following been achieved by AI? – World-class chess playing (Chơi cờ) – Playing table tennis (Chơi tennis) – Cross-country driving (Lái xe đường dài) – Solving mathematical problems (Giải các bài trong toán học) – Discover and prove mathematical theories (Khám phá và chứng minh các định lý trong toán học) – Engage in a meaningful conversation (Hội thoại) – Understand spoken language (Hiểu ngôn ngữ) – Observe and understand human emotions (Nhận ra và hiểu cảm xuc của con người) – Express emotions (Thế hiện cảm xúc) CS 460, Lecture 1 TTNT. p. – 30
31. Định nghĩa AI  Rich, E. and K. Knight . 1991. Artificial Intelligence. New York: McGraw-Hill. “Artificial intelligence (AI) is the study of how to make computers do things which at the moment, people do better.”  George Luger: “An AI approach problem-solving is one which: • uses domain-specific knowledge • to find a good-enough solution • to a hard problem • in a reasonable amount of time.” TTNT. p.31
32. Định nghĩa AI Inputs KNOWLEDGE INFERENCING (questions, BASE CAPABILITY Outputs problems, ) (answers, solutions, )  Một trong những mục tiêu quan trọng của lĩnh vực nghiên cứu này là làm cho máy tính có khả năng tiếp nhận, giải quyết vấn đề giống như con người, thậm chí hơn cả con người (máy tính IBM Deep Blue đã chiến thắng vua cờ Kasparov). TTNT. p.32
33. 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 TTNT. p.33
34. 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. TTNT. p.34
35. 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. TTNT. p.35
36. TTNT - Đặ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 – “kinh nghiệm”  Sử dụng tri thức chuyên môn  TTNT. p.36
37. 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. TTNT. p.37
38. TTNT = Biểu Diễn + tìm kiếm TTNT. p.38
39. Hệ thống ký hiệu vật lý  Hệ thống ký hiệu = tập hợp các mẫu và các quá trình, trong đó các quá trình sản xuất, triệt tiêu và thay đổi các mẫu.  Các hành vi thông minh đạt được bằng việc sử dụng: 1. Các mẩu ký hiệu để biểu diễn các khía cạnh quan trọng của lĩnh vực bài toán. 2. Các phép toán trên những mẫu này để sinh ra các lời giải có khả năng của bài toán 3. Tìm kiếm một lời giải trong số các khả năng này. TTNT. p.39
40. Giả thuyết về hệ thống ký hiệu vật lý  “Một hệ thống ký hiệu vật lý có các phương tiện cần và đủ cho một hành vi thông minh tổng quát” (Nowell và Simon) Allen Newell and Herbert A. Simon, Computer Science as Empirical Inquiry: Symbols and Search, Communications of the ACM (March 1976) TTNT. p.40
41. TTNT như là sự biểu diễn và tìm kiếm Sự biểu diễn phải: Cung cấp một cơ cấu tự nhiên để thể hiện tri thức/thông tin/ dữ liệu một cách đầy đủ => Tính biểu đạt Hỗ trợ việc thực thi một cách hiệu quả việc tìm kiếm đáp án cho một vấn đề => Tính hiệu quả Liệu việc tìm kiếm: – Có kết thúc không ? – Có chắc chắn sẽ tìm được lời giải không ? – Có chắc chắn sẽ tìm được lời giải tối ưu không ? TTNT. p.41
42. TTNT như là biểu diễn & tìm kiếm  Giải quyết vấn đề như là sự tìm kiếm lời giải trong một đồ thị không gian trạng thái: – Nút ~ trạng thái (node ~ state) – Liên kết (link)  Ví dụ: – Trò chơi tic-tac-toe – Chẩn đoán trục trặc máy móc trong ô tô TTNT. p.42
43. KGTT của Trò Chơi Tic-Tac-Toe TTNT. p.43
44. Chẩn đoán trục trặc máy móc trong ô tô TTNT. p.44
45. Agent thông minh – Agent (Tác nhân) là bất cứ cái gì hành động trong môi trường. Ví dụ: con người, robot, – Mục tiêu của TTNT là nghiên cứu và thiết kế các tác nhân thông minh: các tác nhân tồn tại trong moi trường và hành động một cách thông minh – Tác nhân thông minh cần có khả năng nhận thức được môi trường các robot được trang bị các bộ cảm nhận (sensors) – Tác nhân thông minh cần đưa ra các hành động đáp ứng môi trường cần bộ tác động (effectors) TTNT. p. Lec2 – Agent thông minh 45
46. Agent thông minh (tiếp) – Tác nhân được xem như một hộp đen: Môi trường các hành động đến Các thông tin Tác nhân ừ ường t môi tr thông minh cần trang bị cho tác nhân một chương trình, gọi là chương trình tác nhân: mô tả thuật toán kết hợp với các thông tin về trạng thái của môi trường với các tri thức đã được lưu để cho ra hành động thích ứng. TTNT. p.46
47. Agent thông minh (tiếp) Thử nghiệm Turing Alan Turing (1950) đã xác định các hành vi thông minh như là các hành vi trong các nhiệm vụ nhận thức đạt tới mức độ có thể đánh lừa được con người Tác nhân thông minh (TNTM) cần có các khả năng: – Ghi nhớ tri thức và lập luận biểu diễn tri thức và lập luận – Hiểu ngôn ngữ tự nhiên (natural language understanding) xử lý ngôn ngữ tự nhiên – Khả năng học để có thể đưa ra các hành động thích ứng với hoàn cảnh mới học máy (mechine learning) – Nhận biết các đối tượng khi đưa ra các hình ảnh của nó nhìn máy (computer vision): là lĩnh vực nghiên cứu để máy tính có thể hiểu được cấu trúc và các tính chất của các đối tượng trong không gian ba chiều từ các hình ảnh hai chiều. – Khả năng suy ra các mục đích cần đạt được và đưa ra dãy các hành động mà nó cần thực hiện để đạt mục đích đó quá trình lập kế hoạch (planning) TTNT. p.47
48. Agent thông minh (tiếp) Biểu diễn và lập luận – Để máy tính có thể lưu trữ được tri thức, sử dụng được tri thức cần tìm các phương pháp biểu diễn tri thức. – Lập luận tự động được hiểu là quá trình tính toán trên các biểu diễn tri thức: cho đầu vào là các biểu diễn tri thức thì đầu ra nhận được là các biểu diễn tri thức mới. – Mục tiêu trọng tâm của TTNT là nghiên cứu thiết kế các hệ thông minh, nó lưu trữ tri thức về lĩnh vực và có khả năng đưa ra hành động thích ứng bằng lập luận dựa tren các tri thức đă lưu trữ và các thông tin thu nhận từ môi trường. TTNT. p.48
49. Agent thông minh (tiếp) Các lĩnh vực nghiên cứu và ứng dụng – Robot đưa thư – Hệ chuyên gia trong y học: với mục đích trợ giúp các bác sĩ trong việc chuẩn đoán bệnh và điều trị. TTNT. p.49