Slide bài giảng Nhập môn Trí tuệ nhân tạo - Chương 1 đến 4

Slide bài giảng môn Nhập môn Trí tuệ nhân tạo do thầy cung cấp, mình gộp bốn chương đầu vào một file cho tiện in hai mặt. Phần ghi chú ở lề là do mình tự thêm khi nghe giảng, các bạn đọc tham khảo thôi nhé, có chỗ nào sai thì báo lại giúp mình. Chương 1: Tổng quan về trí tuệ nhân tạo Trí tuệ nhân tạo là ngành nghiên cứu cách làm cho máy thực hiện những việc mà nếu do người làm thì cần đến trí thông minh. Định nghĩa này cố tình để mở, vì ranh giới của "thông minh" thay đổi theo thời gian. Bốn cách tiếp cận kinh điển: 1. Hệ thống suy nghĩ như người 2. Hệ thống hành động như người, tiêu biểu là phép thử Turing 3. Hệ thống suy nghĩ hợp lý, dựa trên logic 4. Hệ thống hành động hợp lý, tức tác tử duy lý Giáo trình đi theo hướng thứ tư. Tác tử duy lý là tác tử chọn hành động sao cho tối đa hóa độ đo hiệu quả, dựa trên những gì nó nhận biết được và tri thức nó có sẵn. Chương 2: Không gian trạng thái và tìm kiếm mù Bài toán tìm kiếm được mô tả bởi năm thành phần: trạng thái đầu, tập hành động, hàm chuyển trạng thái, điều kiện đích và chi phí đường đi. Mục 2.1 Tìm kiếm theo chiều rộng Duyệt hết các nút cùng mức trước khi xuống mức sâu hơn, cài bằng hàng đợi. - Luôn tìm ra lời giải nếu tồn tại - Cho lời giải nông nhất, tối ưu khi mọi bước có chi phí bằng nhau - Tốn bộ nhớ rất nhanh vì phải giữ toàn bộ một mức trong hàng đợi Mục 2.2 Tìm kiếm theo chiều sâu Đi sâu hết một nhánh rồi mới quay lui, cài bằng ngăn xếp hoặc đệ quy. Tốn ít bộ nhớ hơn nhiều nhưng có thể đi vào nhánh vô hạn và không bảo đảm tìm ra lời giải ngắn nhất. Cách chữa thường dùng là giới hạn độ sâu rồi tăng dần. Chương 3: Tìm kiếm có thông tin Mục 3.1 Hàm heuristic Hàm heuristic ước lượng chi phí còn lại từ một trạng thái tới đích. Heuristic tốt phải rẻ để tính và bám sát chi phí thật. Hai tính chất quan trọng: - Chấp nhận được: không bao giờ ước lượng cao hơn chi phí thật - Nhất quán: chi phí ước lượng giảm không nhanh hơn chi phí thật của mỗi bước Mục 3.2 Thuật toán A* A* chọn nút mở rộng theo f(n) = g(n) + h(n), trong đó g là chi phí đã đi và h là ước lượng còn lại. Nếu h chấp nhận được thì A* bảo đảm tìm ra lời giải tối ưu. Nếu h nhất quán thì A* còn không phải xét lại nút đã đóng. Trường hợp h luôn bằng 0, A* trở thành thuật toán Dijkstra. Bài tập hay ra: cho bàn cờ 8 ô, so sánh số nút phải mở rộng khi dùng heuristic đếm số ô sai vị trí và heuristic tổng khoảng cách Manhattan. Kết quả cho thấy Manhattan mạnh hơn vì nó luôn cho giá trị lớn hơn mà vẫn chấp nhận được. Chương 4: Biểu diễn tri thức bằng logic Logic mệnh đề dùng các biến chỉ nhận giá trị đúng hoặc sai, nối với nhau bằng phép và, hoặc, phủ định, kéo theo. Ưu điểm là suy diễn đơn giản, nhược điểm là không diễn đạt được quan hệ giữa các đối tượng. Logic vị từ khắc phục bằng cách thêm vị từ, hằng, biến và hai lượng từ với mọi và tồn tại. Nhờ đó viết được những câu dạng: mọi sinh viên đã qua môn tiên quyết đều được đăng ký môn này. Quy trình suy diễn bằng phép phân giải gồm ba bước: 1. Chuyển toàn bộ tri thức về dạng chuẩn hội 2. Thêm phủ định của điều cần chứng minh vào tập mệnh đề 3. Áp dụng phép phân giải cho tới khi sinh ra mệnh đề rỗng Sinh ra mệnh đề rỗng nghĩa là tập ban đầu mâu thuẫn, tức điều cần chứng minh là đúng.