PHẦN II TRÍ TUỆ NHÂN TẠO NHƯ LÀ BIỂU DIỄN VÀ TÌM KIẾM

Chia sẻ: Bui Trung Hieu | Ngày: | Loại File: PDF | Số trang:17

Thêm vào BST

Báo xấu

123
lượt xem 13
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

“Mọi khoa học đều miêu tả bản chất cơ bản nhất của những hệ thống mà chúng ta nghiên cứu. Tính chất của những miêu tả ấy về bản chất không thay đổi theo thời gian, chúng ta có thể phát triển được một tập hợp các thuật ngữ mô tả chúng ngày một chi tiết hơn. Các nghiên cứu về logic và máy tính đã chỉ cho chúng ta thấy trí tuệ có ở trong các hệ thống ký hiệu vật lý. Đây là quy luật về cấu trúc định tính căn bản nhất của khoa học máy tính....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: PHẦN II TRÍ TUỆ NHÂN TẠO NHƯ LÀ BIỂU DIỄN VÀ TÌM KIẾM

Chương 9: Học máy PHẦN II TRÍ TUỆ NHÂN TẠO NHƯ LÀ BIỂU DIỄN VÀ TÌM KIẾM “Mọi khoa học đều miêu tả bản chất cơ bản nhất của những hệ thống mà chúng ta nghiên cứu. Tính chất của những miêu tả ấy về bản chất không thay đổi theo thời gian, chúng ta có thể phát triển được một tập hợp các thuật ngữ mô tả chúng ngày một chi tiết hơn. Các nghiên cứu về logic và máy tính đã chỉ cho chúng ta thấy trí tuệ có ở trong các hệ thống ký hiệu vật lý. Đây là quy luật về cấu trúc định tính căn bản nhất của khoa học máy tính. Các hệ thống ký hiệu là những tập hợp của các mẫu (pattern) và các quá trình (process), trong đó cái sau có khả năng sản xuất, triệt tiêu và thay đổi cái trước. Đặc tính quan trọng nhất của các mẫu là chúng có thể chỉ định các đối tượng, các quá trình và các mẫu khác, và khi chúng chỉ định các quá trình thì có thể hiểu được chúng”. - Newell và Simon (trong bài thuyết trình nhận giải thưởng “ACM Turing Award Lecture” năm 1976) lập luận rằng: hành vi trí tuệ, dù là ở người hay máy tính đều đạt được thông qua những yếu tố sau đây : 1. Những mẫu ký hiệu dùng biểu diễn những khía cạnh quan trọng của lĩnh vực bài toán. 2. Những phép toán trên các mẫu này để phát sinh những lời giải có khả năng cho bài toán. 3. Tìm kiếm một lời giải trong số những khả năng này. Những nhận định này xuất phát từ cơ sở giả thuyết về hệ thống ký hiệu vật lý (physical symbol system hypothesis). Trong giả thuyết này, các mẫu (pattern) - tạo thành do sự sắp xếp các ký hiệu, được phân biệt rõ với phương tiện (medium) – dùng để thực hiện chúng. Nếu như trí tuệ chỉ bắt nguồn từ cấu trúc của một hệ ký hiệu thì bất cứ phương tiện nào thực hiện được thành công trên các mẫu và các quá trình đều sẽ có trí tuệ. Khả năng xây dựng một máy tính có thể vượt qua được trắc nghiệm Turing phụ thuộc vào sự phân biệt này. Giả thuyết hệ thống ký hiệu vật lý cũng phác thảo những tiêu điểm chính của việc phát triển nghiên cứu và ứng dụng TTNT: việc định nghĩa các cấu trúc và phép toán ký hiệu là hết sức cần thiết cho việc giải quyết vấn đề một cách thông minh cũng như việc phát triển các chiến lược tìm kiếm một cách hiệu quả và chính xác cho những lời giải tiềm năng phát sinh bởi các cấu trúc và phép toán này. Đây là những vấn đề liên quan lẫn nhau của biểu diễn tri thức và tìm kiếm (knowledge representation and search) – chúng chính là những tâm điểm của nghiên cứu hiện đại trong TTNT. Võ Huỳnh Trâm – Trần Ngân Bình 1
Giáo Trình Trí Tuệ Nhân Tạo I Biểu diễn tri thức Chức năng của bất kỳ một sơ đồ biểu diễn nào là nắm bắt được những đặc trưng chủ yếu nhất của lĩnh vực vấn đề và làm cho những thông tin đó trở nên thao tác được đối với thủ tục giải quyết vấn đề. Rõ ràng một ngôn ngữ biểu diễn phải cho phép người lập trình thể hiện được tri thức cần thiết để tìm ra lời giải. Sự biểu diễn phải đáp ứng hai tiêu chuẩn đánh giá quan trọng như sau : 1. Tính biểu đạt : 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 đủ. 2. Tính hiệu quả : Hỗ trợ thực thi một cách hiệu quả cho việc tìm kiếm đáp án của một vấn đề. Nhiều biểu diễn có tính biểu đạt cao lại kém hiệu quả cho việc sử dụng đối với những loại bài toán nào đó. Đôi khi phải hy sinh tính biểu đạt để nâng cao tính hiệu quả. Chẳng hạn, những nhà lập trình với các ngôn ngữ cấp thấp (BASIC, FORTRAN, C,...) thường thất bại trong việc xây dựng các hệ chuyên gia vì một lý do đơn giản là những ngôn ngữ này có cấu trúc khá đơn giản, tuy có tính biểu đạt cao nhưng không cung cấp được tính module cần thiết hay không hiệu quả cho việc lập trình dựa trên tri thức. Vấn đề đặt ra là làm thế nào để có được sự thỏa hiệp tốt nhất giữa tính hiệu quả và tính biểu đạt là một trong những nhiệm vụ chính yếu đối với những người thiết kế các hệ thông minh. II Giải quyết vấn đề như là tìm kiếm Khía cạnh thứ hai trong giả thuyết hệ thống ký hiệu của Newell và Simon là: vấn đề được giải quyết bằng cách tìm kiếm giữa những lựa chọn khác nhau. Nói chung, con người thường cân nhắc một số chiến lược khác nhau trong quá trình họ giải quyết một vấn đề nào đó. Chẳng hạn, một đấu thủ cờ thường cân nhắc giữa một số nước đi khác nhau bằng cách lựa chọn sự tương ứng theo tiêu chuẩn tốt nhất cho toàn ván đấu. Khía cạnh này của hành vi thông minh là cơ sở cho một kỹ thuật giải quyết vấn đề có tên là tìm kiếm trong không gian trạng thái (state space search). Trong chiến lược tìm kiếm này, người ta biểu diễn quá trình giải quyết vấn đề như một quá trình tìm kiếm đường đi trên một đồ thị không gian trạng thái (state space graph) mà trong đó: mỗi trạng thái bài toán được xem như một nút (node) của đồ thị hay còn gọi là một trạng thái (state) và các đường chuyển trạng thái khi áp dụng các phép toán hợp lệ vào một trạng thái nào đó sẽ chuyển bài toán từ trạng thái này sang trạng thái khác được gọi là các liên kết (link) của đồ thị. Đây không chỉ là một trong những kỹ thuật hiệu quả mà tính quy tắc và chính xác của nó làm cho việc cài đặt trên máy tính mang tính trực tiếp. Chẳng hạn, xét một ví dụ đơn giản là trò chơi tic-tac-toe. Cho trước một tình huống bàn cờ nào đó, chỉ có một số hữu hạn các nước đi mà người chơi có thể đi. Bắt đầu ván đấu bằng bàn cờ trống, đấu thủ thứ nhất có thể đặt ký hiệu nước đi X vào bất cứ ô nào trong 9 ô trống của bàn cờ. Mỗi trong số những nước đi này tạo ra một bàn cờ khác cho phép đấu thủ thứ hai đến lượt mình đi sẽ có thể chọn 8 cách đặt ký hiệu nước đi O của mình vào... Và sẽ cứ luân phiên như thế. Chúng ta có thể xem mỗi hình thái bàn cờ này như là một nút trong đồ thị, các liên kết của đồ thị biểu diễn các nước đi hợp lệ từ một thế cờ này sang thế cờ khác. Cấu trúc kết quả tạo thành một đồ thị không gian trạng thái cho bài toán. Và lúc đó, một chiến lược 2 Võ Huỳnh Trâm – Trần Ngân Bình
Chương 9: Học máy chơi hiệu quả sẽ là việc tìm kiếm xuyên suốt đồ thị để tìm ra đường đi dẫn đến kết thúc thắng lợi. x x x x x x x x x 0 0 0 0 0 x0 x x x x x x 0x x x x x 0 0 0 0 0 x x x x x 0xx0x 0x 0x x0 x0 x0 x0 x0 x0 0x 0x x x x x x Hình 2.1- Một khoảng không gian trạng thái triển khai cho trò chơi tic-tac-toe Hay, trong một vấn đề phức tạp hơn, chúng ta xem xét bài toán chẩn đoán trục trặc máy móc trong một chiếc ô tô. Thay vì mỗi nút trên đồ thị không gian trạng thái biểu diễn một “trạng thái bàn cờ”, ta cho nó biểu diễn một phần tri thức về các vấn đề máy móc trong ô tô. Quá trình xem xét các triệu chứng của trục trặc và kết luận nguyên nhân của nó có thể được xem như tìm kiếm giữa các trạng thái tri thức có cấp độ tăng dần. Nút bắt đầu của đồ thị là rỗng biểu thị rằng chúng ta không biết gì về nguyên nhân của vấn đề. Mỗi trạng thái trong đồ thị có các cung đi đến các trạng thái khác biểu diễn tri thức sâu hơn trong quá trình chẩn đoán. Võ Huỳnh Trâm – Trần Ngân Bình 3
Giáo Trình Trí Tuệ Nhân Tạo Một chương trình giải quyết vấn đề sẽ chẩn đoán hư hỏng của xe ô tô bằng cách tìm kiếm một đường đi trong đồ thị này mà đường đi đó phù hợp với những triệu chứng của chiếc xe đang bị hỏng hóc. Mặc dù bài toán này rất khác so với việc tìm ra một đường đi tối ưu trong trò chơi tic-tac-toe, nó cũng tuân theo cách giải quyết vấn đề tương đương bằng phương pháp tìm kiếm trong không gian trạng thái. Trục trặc ở đâu ? ... Trục trặc do Trục trặc do động cơ Trục trặc bộ truyền dẫn Hỏi: xe có nổ máy do phanh Hỏi : ... không ? Hỏi : ... không có Động cơ không nổ máy được Động cơ nổ Hỏi : Động cơ có khởi động máy được điện được không? Hỏi : .... có không Động cơ khởi động điện Động cơ khởi không được. động điện được. Hỏi: Đèn có sáng không? Hỏi: . . . không có Hư bình điện Bình điện tốt Hình 2.2 - Biểu diễn không gian trạng thái bài toán chẩn đoán trục trặc ô tô Trong phần II này, các khía cạnh lý thuyết của biểu diễn tri thức và tìm kiếm sẽ được áp dụng cho việc xây dựng những chương trình hiệu quả. Việc xem xét cách biểu diễn tri thức bắt đầu bằng phép tính vị từ trong Chương 2. Chương 3 giới thiệu các chiến lược tìm kiếm trong ngữ cảnh là những trò chơi đơn giản. Bắt đầu bằng trò chơi, chúng ta có thể nghiên cứu được những vấn đề liên quan đến tìm kiếm trong không gian trạng thái mà không cần 4 Võ Huỳnh Trâm – Trần Ngân Bình
Chương 9: Học máy phải xem xét đến những cách biểu diễn bài toán trong thế giới thực. Trong Chương 4, chúng ta sẽ thảo luận đến việc cài đặt các thuật toán tìm kiếm với sự quan tâm đặc biệt đến việc sử dụng các heuristic vào hướng dẫn tìm kiếm. Chương 5 đề cập đến các hệ sinh – một mô hình tổng quát và hiệu quả cho việc giải quyết vấn đề dựa trên tìm kiếm, cũng như mô hình kiến trúc bảng đen. Võ Huỳnh Trâm – Trần Ngân Bình 5
Giáo Trình Trí Tuệ Nhân Tạo Chương II LOGIC HÌNH THỨC Nội dung chính : Trong chương này, chúng ta giới thiệu phép tính vị từ như một ngôn ngữ biểu diễn dùng cho Trí tuệ nhân tạo. Những ưu điểm của việc dùng phép tính vị từ bao gồm một ngữ nghĩa hình thức (formal semantics) được định nghĩa chính xác cùng với các luật suy diễn vững chắc và đầy đủ. Chương này bắt đầu bằng việc nhắc lại phép tính mệnh đề, định nghĩa cú pháp và ngữ nghĩa của phép tính vị từ. Tiếp theo, chúng ta thảo luận về các luật suy diễn của phép tính vị từ và việc sử dụng chúng trong giải quyết vấn đề. Phần cuối chương sẽ minh họa cách sử dụng phép tính vị từ để cài đặt một cơ sở tri thức trong lĩnh vực tư vấn đầu tư tài chính. Mục tiêu cần đạt : Sau chương này, sinh viên có thể : Hiểu Logic mệnh đề và Logic vị từ Vận dụng các phép biến đổi tương đương Biết biểu diễn tri thức của vấn đề bằng logic vị từ bậc nhất. Vận dụng các phép suy diễn để chứng minh một vấn đề đơn giản. Vận dụng phép hợp nhất và giải thuật đối sánh mẫu Kiến thức tiên quyết : Khái niệm về Trí tuệ nhân tạo, Logic mệnh đề, Logic vị từ, … Tài liệu tham khảo : [1] George F. Luger, William A. Stubblefield – Albuquerque – Artificial Intelligence – Wesley Publishing Company, Inc – 1997 (Chapter 2) [2] Bùi Xuân Toại – Trương Gia Việt (Biên dịch) – Trí tuệ nhân tạo – Các cấu trúc và chiến lược giải quyết vấn đề - NXB Thống kê, 2000 (Phần II) [3] Wikipedia – Bách khoa toàn thư mở - Phép tính vị từ bậc nhất http://en.wikipedia.org/wiki/Predicate_calculus 6 Võ Huỳnh Trâm – Trần Ngân Bình
Chương 9: Học máy I PHÉP TÍNH MỆNH ĐỀ I.1 Định nghĩa – Ký hiệu phép tính mệnh đề I.1.1 Mệnh đề : Mệnh đề là một phát biểu có thể khẳng định tính đúng hoặc sai. Các ký hiệu (symbol) của phép tính mệnh đề là các ký hiệu mệnh đề : P, Q, R, S, … (thông thường nó là các chữ cái in hoa nằm gần cuối bảng chữ cái tiếng Anh), các ký hiệu chân lý – chân trị (truth symbol) : true, false hay các phép toán kết nối như : ∧, ∨, ¬, ⇒, = Các ký hiệu mệnh đề (propositional symbol) biểu thị các mệnh đề (proposition) hay các phát biểu về thế giới thực mà giá trị của chúng có thể là đúng hoặc sai. Thí dụ 2.1: Các mệnh đề “Chiếc xe hơi kia màu đỏ” “Nước thì ướt” I.1.2 Câu : Câu trong phép tính mệnh đề được cấu tạo từ những ký hiệu sơ cấp (atomic symbol) theo các luật sau đây : - Tất cả các ký hiệu mệnh đề và ký hiệu chân lý đều là câu (sentences) : true, P, Q và R là các câu. Phủ định của một câu là một câu : ¬ P và ¬ false là các câu - Hội hay và của hai câu là một câu : P ∧ ¬ P là một câu - Tuyển hay hoặc của hai câu là một câu : P ∨ ¬ P là một câu - Kéo theo của một câu để có một câu khác là một câu : P ⇒ Q là một câu. - Tương đương của hai câu là một câu : P ∨ Q = R là một câu - Các câu hợp lệ được gọi là các công thức dạng chuẩn (well-formed formula) hay WFF. Trong các câu phép tính mệnh đề, các ký hiệu ( ) và [ ] dùng để nhóm các ký hiệu vào các biểu thức con và nhờ đó kiểm soát được thứ tự của chúng trong việc đánh giá biểu thức và diễn đạt. Ví dụ (P ∨ Q) = R hoàn toàn khác với P ∨ (Q = R). I.1.3 Biểu thức : Một biểu thức là một câu hay công thức dạng chuẩn, của phép tính mệnh đề khi và chỉ khi nó có thể đ ư ợc tạo từ những ký hiệu hợp lệ thông qua một dãy những luật này. Thí dụ 2.2: (( P ∧ Q) ⇒ R = ¬ P ∨ ¬ Q ∨ R là một câu dạng chuẩn trong phép tính mệnh đề vì : P, Q, R là các mệnh đề và do đó là các câu. P ∧ Q, hội của hai câu là một câu. (P ∧ Q) ⇒ R, kéo theo của một câu là một câu. ¬ P và ¬ Q, phủ định của các câu là câu. Võ Huỳnh Trâm – Trần Ngân Bình 7
Giáo Trình Trí Tuệ Nhân Tạo ¬ P ∨ ¬ Q, tuyển của hai câu là câu. ¬ P ∨ ¬ Q ∨ R, tuyển của hai câu là câu. (( P ∧ Q) ⇒ R = ¬ P ∨ ¬ Q ∨ R, tương đương của hai câu là câu. Đây là câu xuất phát, nó đã được xây dựng thông qua một loạt các luật hợp lệ và do đó nó có dạng chuẩn. I.2 Ngữ nghĩa của phép tính mệnh đề Sự gán giá trị chân lý cho các câu mệnh đề được gọi là một sự diễn giải (interpretation), một sự khẳng định chân trị của chúng trong một thế giới khả hữu (possible world) nào đó. Một cách hình thức, một diễn giải là một ánh xạ từ các ký hiệu mệnh đề vào tập hợp {T, F}. Phép gán giá trị chân lý cho các mệnh đề phức tạp thường được mô tả thông qua bảng chân trị như sau : ¬P P∧Q P∨Q P⇒Q P Q P=Q T T F T T T T T F F F T F F F T T F T T F F F T F F T T Thí dụ 2.3: Chân trị của mệnh đề (¬ P ∨ ¬ Q) = (P ⇒ Q) được cho như trong bảng sau : ¬P ¬P∨¬Q P⇒Q (¬ P ∨ ¬ Q) = (P ⇒ Q) P Q T T F T T T T F F F F T F T T T T T F F T T T T Hai biểu thức trong phép tính mệnh đề là tương đương nhau nếu chúng có cùng giá trị trong mọi phép gán chân trị. Một số công thức biến đổi tương đương của các mệnh đề đươc cho như trong bảng sau: ¬(¬P) = P (P∨Q) = (¬P ⇒ Q) (P ⇒ Q) = (¬Q ⇒ ¬P) Luật tương phản: ¬(P ∨ Q) = (¬P ∧ ¬Q), và Luật De Morgan: ¬(P ∧ Q) = (¬P ∨ ¬Q) (P ∧ Q) = (Q ∧ P), và (P∨Q) = (Q∨P) Luật giao hoán: Luật kết hợp: ((P ∧ Q) ∧ R) = (P ∧ (Q ∧ R)), ((P ∨ Q) ∨ R) = (P ∨ (Q ∨ R)) P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R), Luật phân phối: P ∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R) Bảng 2.1 – Bảng công thức biến đổi t ươ ng đ ươ ng 8 Võ Huỳnh Trâm – Trần Ngân Bình
Chương 9: Học máy Những đồng nhất thức trong bảng 2.1 trên được dùng để biến đổi các biểu thức mệnh đề sang một dạng khác về mặt cú pháp nhưng tương đương về mặt logic. Có thể dùng các đồng nhất thức này thay cho các bảng chân trị để chứng minh hai biểu thức mệnh đề là tương đương nhau. Câu hỏi : Sử dụng bảng chân trị, hãy chứng minh sự tương đương của các đồng nhất thức trong bảng 2.1. I.3 Phép tính vị từ Trong phép tính mệnh đề, mỗi ký hiệu câu sơ cấp P, Q, … biểu thị một mệnh đề và chúng ta không thể tác động vào từng phần riêng lẻ của câu. Phép tính vị từ (predicate calculus) cung cấp cho chúng ta khả năng này. Chẳng hạn, đặt mệnh đề “hôm qua trời mưa” là P, từ đó chúng ta có thể tạo ra một vị từ chỉ thời tiết mô tả quan hệ giữa một ngày và thời tiết trong ngày ấy: thời_tiết (hôm_qua, mưa). Thông qua các luật suy diễn, chúng ta sẽ có thể thao tác trên các biểu thức phép tính mệnh đề, truy xuất và suy ra những câu mới. I.3.1 Ký hiệu vị từ : là tập hợp gồm các chữ cái, chữ số, ký hiệu “_”, và được bắt đầu bằng chữ cái. Thí dụ 2.4 : X3, tom_and_jerry Ký hiệu vị từ có thể là: - Ký hiệu chân lý: true, false - Hằng: dùng để chỉ một đối tượng / thuộc tính trong thế giới. Hằng được ký hiệu bắt đầu bằng chữ thường: helen, yellow, rain, … - Biến: dùng để chỉ một lớp tổng quát các đối tượng/thuộc tính. Biến được ký hiệu bắt đầu bằng chữ hoa: X, People, Students, … - Hàm: dùng để chỉ một hàm trên các đối tượng. Hàm được ký hiệu bắt đầu bằng chữ thường: father, plus, … Mỗi ký hiệu hàm có một ngôi n, chỉ số lượng các đối số của hàm. - Vị từ: dùng để định nghĩa một mối quan hệ giữa không hoặc nhiều đối tượng. Vị từ được ký hiệu bắt đầu bằng chữ thường: likes, equals, part_of, … a. Biểu thức hàm: là một ký hiệu hàm theo sau bởi n đối số. Ví dụ: father(david) price(bananas) like(tom, football) b. Mục (term): là một hằng, một biến hay một biểu thức hàm c. Câu sơ cấp: là một hằng vị từ với n ngôi theo sau bởi n thành phần nằm trong cặp dấu ( ), cách nhau bởi dấu ‘,’, và kết thúc với dấu ‘.’ - Trị chân lý true, false là các câu sơ cấp. - Câu sơ cấp còn được gọi là: biểu thức nguyên tử, nguyên tử hay mệnh đề Võ Huỳnh Trâm – Trần Ngân Bình 9
Giáo Trình Trí Tuệ Nhân Tạo Thí dụ 2.5 : friends(helen, marry). likes(hellen, mary). likes(helen, sister(mary)). likes(X, ice-cream). Ký hiệu vị từ trong các câu này là friends, likes. Câu: được tạo ra bằng cách kết hợp các câu sơ cấp sử dụng: Các phép kết nối logic: ¬, ∧, ∨, ⇒, = - - Các lượng tử biến: o Lượng tử phổ biến ∀: dùng để chỉ một câu là đúng với mọi giá trị của biến lượng giá ∀ X likes(X, ice-cream). Ví dụ: o Lượng tử tồn tại ∃: dùng để chỉ một câu là đúng với một số giá trị nào đó của biến lượng giá. ∃Y friends(Y,tom). Ví dụ: likes(helen, chocolat) ∧ ¬ likes(bart, chocolat). Thí dụ 2.6: ∃ X foo(X,two,plus(two,three)) ∧ equal(plus(three,two),five) (foo(two, two,plus(two,three))) ⇒ (equal(plus(three,two),five)= true I.4 Ngữ nghĩa - Phép tính vị từ Tương tự như phép tính mệnh đề, ng ữ nghĩa của phép tính vị từ cung cấp một cơ sở để xác định chân trị của các biểu thức dạng chuẩn. Chân trị của các biểu thức phụ thuộc vào ánh xạ từ các hằng, các biến, các vị từ và các hàm vào các đối tượng và quan hệ trong lĩnh vực được đề cập. Sự thông dịch (cách diễn giải) của một tập hợp các câu phép tính vị từ: là một sự gán các thực thể trong miền của vấn đề đang đề cập cho mỗi ký hiệu hằng, biến, vị từ và hàm. Giá trị chân lý của một câu sơ cấp được xác định qua sự thông dịch. Đối với các câu không nguyên tố, sử dụng bảng chân lý cho cho các phép nối kết, và: Giá trị của câu ∀ X là true nếu là T cho tất cả các phép gán có thể - được cho X. Giá trị của câu ∃ X là true nếu tồn tại một phép gán cho X làm cho - có giá trị T. Thí dụ 2.7: Cho trước một tập hợp các quan hệ gia đình như sau : mother (eve,abel) mother(eve,cain) father(adam,abel) father(adam,cain) ∀X ∀Y father(X,Y) ∨ mother(X,Y) ⇒ parent(X,Y) ∀X ∀Y ∃Z parent(Z,X) ∧ parent(Z,Y) ⇒ sibling(X,Y) Ta có thể suy luận: 10 Võ Huỳnh Trâm – Trần Ngân Bình
Chương 9: Học máy parent(eve,abel) parent(eve,cain) parent(adam,abel) parent(adam,cain) sibling(abel,cain) sibling(cain,abel) sibling(abel,abel) sibling(cain,cain) ! Không có nghĩa I.5 Phép tính vị từ bậc nhất (First – order predicate calculus) Phép tính vị từ bậc nhất cho phép các biến lượng giá tham chiếu đến các đối tượng trong miền của vấn đề đang đề cập nhưng KHÔNG được tham chiếu đến các vị từ và hàm. Ví dụ không hợp lệ: ∀(Likes) Likes(helen, ice-cream) Thí dụ 2.8 : Ví dụ hợp lệ: Nếu ngày mai trời không mưa, Tom sẽ đi biển. ¬weather(rain, tomorrow) ⇒ go(tom, sea) Tất cả các cầu thủ bóng rổ đều cao. ∀ X ( basketball_player(X) ⇒ tall(X) ) Có người thích coca-cola. ∃ X person(X) ∧ likes(X, coca-cola) Không ai thích thuế. ¬ ∃ X likes(X, taxes) Hầu hết bất kỳ câu đúng ngữ pháp nào cũng có thể biểu diễn trong phép tính vị từ bậc nhất bằng cách sử dụng các ký hiệu, các phép kết nối và ký hiệu biến. I.6 Các luật suy diễn Ngữ nghĩa của phép tính vị từ cung cấp một cơ sở cho lý thuyết hình thức về suy diễn logic. Khả năng suy ra những biểu thức đúng mới từ một tập hợp các khẳng định đúng là một đặc trưng quan trọng của phép tính vị từ. Logic vị từ dùng các luật suy diễn sau : d. Luật Modus Ponens (MP): P P⇒Q Q Thí dụ 2.9: Nếu ta có quan sát sau đây “nếu trời mưa thì sân ướt” (P ⇒ Q) và “trời đang mưa” (P) thì ta dễ dàng suy ra được “sân ướt” (Q). Luật Modus Tollens (MT): P ⇒ Q e. ¬Q . ¬P f. Luật triển khai phổ biến (Universal Instantiation): ∀X P(X) a thuộc miền xác định của X P(a) Võ Huỳnh Trâm – Trần Ngân Bình 11
Giáo Trình Trí Tuệ Nhân Tạo (1) ∀X (man(X) ⇒ mortal(X)) Thí dụ 2.10: Cho trước: (2) man(socrates) (3) man(socrates) ⇒ mortal(socrates) => từ (1),(2) bằng luật UI. (4) mortal(socrates) từ (3) và (2) bằng luật MP. II ĐỐI SÁNH MẪU VÀ PHÉP HỢP NHẤT II.1 Phép hợp nhất Phép hợp nhất (unification) là một thuật toán dùng để xác định những phép thế cần thiết để làm cho hai biểu thức vị từ đối sánh (match) nhau. Hợp nhất và các luật suy diễn khác như Modus ponens cho phép chúng ta tạo ra các suy diễn dựa trên một tập hợp các khẳng định logic. Phép hợp nhất phức tạp do có thể thay thế một biến với bất kỳ mục nào gồm cả những biến và những biểu thức hàm khác với độ phức tạp tùy ý. Những biểu thức này tự thân chúng lại có thể chứa các biến. Thí dụ 2.11: Đối sánh foo(X,a,goo(Y)) với: foo(X,b,foo(Y)) không đối sánh foo(X,Y) không đối sánh moo(X,a,goo(Y)) không đối sánh foo(fred,a, goo(Z)) {fred/X, Z/Y} foo(W,a,goo(jack)) {W/X,jack/Y} foo(Z,a,goo(moo(Z))) {Z/X,moo(Z)/Y} Nói chung một quá trình giải quyết vấn đề sẽ đòi hỏi nhiều suy diễn và do đó cần nhiều phép hợp nhất nói tiếp nhau. Các chương trình giải quyết vấn đề logic phải duy trì tính nhất quán của các phép thế biến. Điều này được phát biểu trong giải thuật đối sánh mẫu. II.2 Giải thuật đối sánh mẫu 1. Hằng / hằng đối sánh : chỉ khi chúng giống hệt nhau 2. Hằng a / biến X đối sánh: a. Biến chưa kết buộc: biến trở thành kết buộc với hằng {a/X} b. Biến đã kết buộc : xem (1) 3. Biến / biến đối sánh: a. Hai biến chưa kết buộc: luôn luôn đối sánh b. Một biến kết buộc và một biến chưa kết buộc: xem (2) 12 Võ Huỳnh Trâm – Trần Ngân Bình
Chương 9: Học máy c. Hai biến kết buộc: xem (1) 4. Biểu thức / biểu thức đối sánh: chỉ khi các tên hàm hoặc vị từ, số ngôi giống nhau thì áp dụng đối sánh từng đối số một. Lưu ý : Phạm vi của một biến là một câu. Một khi biến đã bị kết buộc, các phép hợp nhất theo sau và các suy luận kế tiếp phải giữ sự kết buộc này. Câu hỏi : Hợp nhất các cặp biểu thức dưới đây, chỉ ra các giá trị đối sánh (nếu có) hoặc giải thích tại sao chúng không thể hợp nhất : a) P(X, Y) và p(a, Z) b) P(X, X) và p(a, b) c) ancestor(X, Y) và ancestor(bill, father(bill)) d) ancestor(X, father(X)) và ancestor(david, george) e) q(X) và ¬ q(a) II.3 Ứng dụng : Chương trình tư vấn tài chính Họat động của chương trình là trợ giúp người dùng trong việc quyết định có nên đầu tư vào một tài khoản tiết kiệm hay thị trường chứng khoán hay không, một số nhà đầu tư cũng có thể muốn phân bổ số tiền của họ thành hai khoản. Việc đầu tư sẽ được gợi ý cho những nhà đầu tư dựa trên thu nhập của họ và số tiền hiện tại mà họ đã có trong tài khoản tiết kiệm. Hệ làm việc theo các quy tắc sau : 1. Các cá nhân không đủ tiền tiết kiệm cần ưu tiên tăng tiền tiết kiệm, bất kể thu nhập là bao nhiêu. 2. Các cá nhân có đủ tiền tiết kiệm và đủ thu nhập nên xem xét việc đầu tư mạo hiểm hơn nhưng có khả năng đem lại lợi nhuận hơn vào thị trường chứng khoán. 3. Các cá nhân với thu nhập thấp nhưng đủ tiền tiết kiệm có thể chia phần thu nhập thêm vào tiết kiệm và chứng khoán, nhằm làm tăng số tiền tiết kiệm trong khi vẫn muốn tăng thu nhập thông qua chứng khoán. Sự tương xứng giữa tiền tiết kiệm và thu nhập được xác định bởi số thành viên gia đình mà một cá nhân cần chu cấp. Quy tắc là : - Tiết kiệm đủ là 5000$/ người phụ thuộc - Thu nhập đủ 15000$ + (4000$ / người phụ thuộc) Ta xây dựng hệ thống logic với các câu vị từ như sau: 1. savings_account(inadequate) ⇒investment(saving) 2. savings_account(adequate) ∧ income(adequate) ⇒ investment(stocks) 3. savings_account(adequate) ∧ income(inadequate) ⇒ investment(combination) Võ Huỳnh Trâm – Trần Ngân Bình 13
Giáo Trình Trí Tuệ Nhân Tạo 4. ∀X amount_saved(X) ∧ ∃Y(dependents(Y) ∧ greater(X,minsavings(Y))) ⇒ savings_account(adequate) 5. ∀X amount_saved(X) ∧ ∃Y(dependents(Y) ∧ ¬greater(X,minsavings(Y))) ⇒ savings_account(inadequate) 6. ∀X earning(X, steady) ∧ ∃Y(dependents(Y) ∧ ⇒ greater(X,minincome(Y))) income(adequate) 7. ∀X earning(X, steady) ∧ ∃Y(dependents(Y) ∧ ¬greater(X,minincome(Y))) ⇒ income(inadequate) 8. ∀X earning(X, unsteady) ⇒ income(inadequate) With: minsavings(X) = 5000 * X minincome(X)=15000+(4000*X) Để thực hiện một phiên tư vấn, thông tin mô tả về một nhà đầu tư nào đó được bổ sung vào tập hợp các câu vị từ. Chẳng hạn một cá nhân với 3 thành viên phụ thuộc, có số tiền trong tài khoản tiết kiệm là 22.000$ và có thu nhập ổn định là 25.000$ sẽ được mô tả như sau : 9. amount_saved(22000) 10. earnings(25000,steady) 11. dependents(3) Sử dụng phép hợp nhất và modus ponens, một chiến lược đầu tư đúng đắn người này có thể được rút ra như là một hệ quả logic từ những mô tả này : Hợp giải (10), (11) với (7) bằng đối sánh {25000/X, 3/Y}, ta có : 12. income(inadequate) Hợp giải (9), (11) với (4) bằng đối sánh {22000/X, 3/Y}, ta có : 13. savings_account(adequate) Hợp giải (12), (13) với (3) ⇒ investment (combination) Như vậy hình thức đầu tư được tư vấn từ hệ là kết hợp cả việc gởi tiền vào tài khoản tiết kiệm và đầu tư vào chứng khoán. TỔNG KẾT CHƯƠNG II: Trong chương này, chúng ta đã được giới thiệu phép tính vị từ như một ngôn ngữ biểu diễn dùng cho việc giải quyết vấn đề trong AI. Chúng ta đã định nghĩa các khái niệm về biến, hàng, hàm, biểu thức, … và ngữ nghĩa của ngôn ngữ này. Dựa trên ngữ nghĩa của phép tính vị từ, các luật suy diễn cũng cho phép suy diễn các câu từ một tập hợp các biểu thức cho trước. Phần cuối chương định nghĩa một thuật toán hợp nhất và đối sánh mẫu dùng xác định các phép thay thế biến làm cho hai biểu thức đối sánh nhau, một ví dụ minh họa ứng dụng cụ thể cho giải thuật này là bài toán hệ tư vấn tài chính. Trong chương tiếp theo, lý thuyết và những kỹ thuật tìm kiếm trên không gian trạng thái bài toán sẽ được giới thiệu. 14 Võ Huỳnh Trâm – Trần Ngân Bình
Chương 9: Học máy III BÀI TẬP CHƯƠNG 2 II.1. Jane có bốn thành viên gia đình phụ thuộc, thu nhập bằng lương hàng tháng là 30.000$ và tài khoản tiết kiệm của cô ta là 20.000$. Hãy đưa ra các vị từ thích hợp mô tả tình trạng tài chính của Jane cho chương trình tư vấn tài chính và tiến hành các phép hợp nhất, suy diễn cần thiết để xác định phương thức đầu tư thích hợp cho cô ta. II.2. Chuyển các câu sau đây thành câu trong logic vị từ: a) Tất cả các con mèo đều là động vật. b) Không có con chó nào là loài bò sát. c) Tất cả các nhà khoa học máy tính đều thích một hệ điều hành nào đó. d) Mọi đứa trẻ đều thích Coca-cola. e) Không có đứa trẻ nào thích ăn rau. f) Một số người thích kẹo, một số khác thì không. g) Không có sinh viên nào học mà thi rớt môn này. II.3. Cho một vấn đề được phát biểu như sau: a) John thích mọi loại thức ăn. b) Táo là thức ăn. c) Gà là thức ăn. d) Tất cả mọi thứ ăn được mà vẫn còn sống thì đó là thức ăn. e) Bill ăn đậu phộng và Bill vẫn còn sống. f) Sue ăn mọi thứ mà Bill ăn. 1. Hãy biểu diễn vấn đề trên theo logic vị từ bậc nhất. 2. Dùng giải thuật đối sánh mẫu để chứng minh “John thích đậu phộng” II.4. Câu chuyện dưới đây được lấy từ quyển sách Algorithms + Data structures = Programs (Thuật toán + Cấu trúc dữ liệu = Chương trình) của N. Wirth (1976): “Tôi cưới một góa phụ (W), bà ta có một cô con gái đã lớn (D). Cha tôi (F), người thường xuyên đến thăm chúng tôi đã phải lòng cô con riêng của vợ tôi và cưới cô ta. Vì thế cha tôi trở thành con rể tôi và con ghẻ tôi trở thành mẹ tôi. Vài tháng sau đó, vợ tôi sinh một đứa con trai (S1), nó trở thành em rể của bố tôi, cũng như trở thành chú tôi. Vợ của bố tôi, tức là con ghẻ của tôi, cũng sinh một đứa con trai (S2).” Sử dụng phép tính vị từ, hãy tạo ra một tập hợp các biểu thức biểu diễn hoàn cảnh trong câu chuyện trên. Hãy đưa ra các biểu thức định nghĩa các quan hệ gia đình cơ bản như định nghĩa bố vợ chẳng hạn, và sử dụng modus ponens trên hệ này để chứng minh kết luận “Tôi cũng chính là ông tôi”. Võ Huỳnh Trâm – Trần Ngân Bình 15
Giáo Trình Trí Tuệ Nhân Tạo 16 Võ Huỳnh Trâm – Trần Ngân Bình
Chương 9: Học máy PHẦN II ....................................................................................................................................1 TRÍ TUỆ NHÂN TẠO NHƯ LÀ .............................................................................................1 BIỂU DIỄN VÀ TÌM KIẾM ....................................................................................................1 Chương II..................................................................................................................................6 LOGIC HÌNH THỨC ...............................................................................................................6 I. PHÉP TÍNH MỆNH ĐỀ ..............................................................................................7 I.1. Định nghĩa – Ký hiệu phép tính mệnh đề............................................................7 I.2. Ngữ nghĩa của phép tính mệnh đề .......................................................................8 I.3. Phép tính vị từ .....................................................................................................9 I.4. Ngữ nghĩa - Phép tính vị từ ...............................................................................10 I.5. Phép tính vị từ bậc nhất (First – order predicate calculus) ...............................11 I.6. Các luật suy diễn ...............................................................................................11 II. ĐỐI SÁNH MẪU VÀ PHÉP HỢP NHẤT................................................................12 II.1. Phép hợp nhất....................................................................................................12 II.2. Giải thuật đối sánh mẫu.....................................................................................12 II.3. Ứng dụng : Chương trình tư vấn tài chính ........................................................13 BÀI TẬP CHƯƠNG II ............................................................................................15 Võ Huỳnh Trâm – Trần Ngân Bình 17