Bài giảng Nhập môn trí tuệ nhân tạo: Phần 1 - ĐH Sư phạm kỹ thuật Nam Định

Chia sẻ: Ermintrudetran Ermintrudetran | Ngày: | Loại File: PDF | Số trang:118

Thêm vào BST

Báo xấu

63
lượt xem 11
download

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

Bài giảng Nhập môn trí tuệ nhân tạo: Phần 1 cung cấp cho người học những kiến thức như: Tổng quan về Trí tuệ nhân tạo; Các chiến lược tìm kiếm; Các giải thuật tìm kiếm lời giải cho trò chơi;...Mời các bạn cùng tham khảo!

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Nhập môn trí tuệ nhân tạo: Phần 1 - ĐH Sư phạm kỹ thuật Nam Định

DANH MỤC HÌNH VẼ ..................................................................................................4 BẢNG KÝ HIỆU VIẾT TẮT..........................................................................................5 CHƢƠNG 1. TỔNG QUAN VỀ TRÍ TUỆ NHÂN TẠO ...............................................6 1.1. Lịch sử phát triển của TTNT ................................................................................6 1.1.1. Lịch sử hình thành và phát triển ....................................................................6 1.1.2. Đối tƣợng và mục tiêu nghiên cứu của TTNT ..............................................8 1.1.3. Những tiền đề cơ bản của TTNT ...................................................................8 1.2. Khái niệm về TTNT .............................................................................................9 1.2.1. Trí tuệ của con ngƣời.....................................................................................9 1.2.2. Trí tuệ nhân tạo ............................................................................................10 1.3. Vai trò của TTNT trong công nghệ thông tin .....................................................11 1.4. Các kỹ thuật TTNT .............................................................................................11 1.5. Các thành phần trong hệ thống TTNT ................................................................12 1.6. Các lĩnh vực nghiên cứu và ứng dụng cơ bản của TTNT ..................................13 1.6.1. Trò chơi .......................................................................................................13 1.6.2. Suy luận và chứng minh định lý tự động ....................................................14 1.6.3. Các hệ chuyên gia ........................................................................................15 1.6.4. Hiểu và mô hình hoá ngữ nghĩa ngôn ngữ tự nhiên ....................................17 1.6.5. Mô hình hoá hoạt động của con ngƣời ........................................................18 1.6.6. Lập kế hoạch và robotics .............................................................................19 1.6.7. Các ngôn ngữ và môi trƣờng dùng cho TTNT ............................................20 1.6.8. Máy học .......................................................................................................21 1.6.9. Xử lý phân tán song song ............................................................................22 1.7. Những thách thức đối với TTNT ........................................................................23 CÂU HỎI CHƢƠNG 1 .................................................................................................25 CHƢƠNG 2: CÁC CHIẾN LƢỢC TÌM KIẾM ...........................................................26 2.1. Biểu diễn vấn đề trong không gian trạng thái ....................................................26 2.1.1. Không gian trạng thái của bài toán ..............................................................26 2.1.2. Các ví dụ ......................................................................................................27 2.2. Giới thiệu các chiến lƣợc tìm kiếm ....................................................................32 2.2.1. Các chiến lƣợc tìm kiếm mù........................................................................32 2.2.2. Các chiến lƣợc tìm kiếm kinh nghiệm (tìm kiếm heuristic) ........................33 2.3. Cây tìm kiếm ......................................................................................................33 2.4. Các chiến lƣợc tìm kiếm mù ...............................................................................34 2.4.1. Tìm kiếm theo bề rộng ................................................................................34 2.4.2. Tìm kiếm theo chiều sâu..............................................................................38 2.4.3. Các trạng thái lặp .........................................................................................43 2.4.4. Tìm kiếm sâu lặp .........................................................................................43 2.4.5.Tìm kiếm trên đồ thị và/hoặc........................................................................47 2.5. Các chiến lƣợc tìm kiếm kinh nghiệm................................................................56 2.5.1. Hàm đánh giá và tìm kiếm kinh nghiệm .....................................................56 2.5.2 Tìm kiếm tốt nhất đầu tiên............................................................................58 2.5.3. Tìm kiếm leo đồi .........................................................................................61 2.6. Các chiến lƣợc tìm kiếm tối ƣu ..........................................................................64 2.6.1. Thuật toán A* ..............................................................................................66 2.6.2. Thuật toán nhánh_cận..................................................................................70 2.7. Các giải thuật tìm kiếm lời giải cho trò chơi ......................................................74 2.7.1. Cây trò chơi đầy đủ .....................................................................................74 1
2.7.2. Giải thuật Minimax......................................................................................76 2.7.3. Giải thuật Minimax với độ sâu hạn chế.......................................................78 2.7.4. Giải thuật Minimax với cắt tỉa Alpha-Beta .................................................80 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 2 ..........................................................................83 CHƢƠNG 3. LOGIC MỆNH ĐỀ .................................................................................95 3.1. Biểu diễn tri thức ................................................................................................95 3.2. Cú pháp và ngữ nghĩa của logic mệnh đề...........................................................96 3.2.1. Các ký hiệu ..................................................................................................96 3.2.2. Các quy tắc xây dựng các công thức ...........................................................97 3.2.2. Ngữ nghĩa ....................................................................................................97 3.3. Dạng chuẩn tắc ...................................................................................................99 3.3.1. Sự tƣơng đƣơng của các công thức .............................................................99 3.3.2. Dạng chuẩn tắc ..........................................................................................100 3.3.3. Các câu Horn .............................................................................................101 3.4. Luật suy diễn ....................................................................................................102 3.4. Luật phân giải. Thủ tục chứng minh bác bỏ bằng luật phân giải .....................105 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 3 ........................................................................113 CHƢƠNG 4: LOGIC VỊ TỪ .......................................................................................119 4.1. Cú pháp và ngữ nghĩa của logic vị từ ...............................................................119 4.1.1. Cú pháp ......................................................................................................119 4.1.2. Ngữ nghĩa ..................................................................................................121 4.2. Các công thức tƣơng đƣơng .............................................................................123 4.3. Chuẩn hóa các công thức ..................................................................................124 4.4. Các luật suy diễn ..............................................................................................126 4.4.1. Luật thay thế phổ dụng ..............................................................................126 4.4.2. Hợp nhất ....................................................................................................126 4.4.3. Luật Modus Ponens tổng quát ...................................................................127 4.4.4. Luật phân giải tổng quát ............................................................................128 4.5. Thuật toán hợp nhất ..........................................................................................129 4.6. Chứng minh bằng luật phân giải ......................................................................131 4.7. Các chiến lƣợc phân giải ..................................................................................137 4.7.1. Chiến lƣợc phân giải theo bề rộng ............................................................139 4.7.2. Chiến lƣợc phân giải sử dụng tập hỗ trợ ...................................................139 4.7.3. Chiến lƣợc tuyến tính ................................................................................141 4.8. Xây dựng CSTT................................................................................................141 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 4 ........................................................................144 CHƢƠNG 5. BIỂU DIỄN TRI THỨC .......................................................................148 5.1. Các dạng mô tả tri thức.....................................................................................148 5.1.1. Biểu diễn tri thức bằng logic .....................................................................148 5.1.2. Biểu diễn tri thức bằng mạng ngữ nghĩa ...................................................148 5.1.3. Biểu diễn tri thức bằng khung (Frame) .....................................................149 5.1.4. Biểu diễn tri thức bằng các luật nếu - thì ..................................................149 5.2. Lập luận tiến .....................................................................................................151 5.2.1. Khái niệm ..................................................................................................151 5.2.2. Thủ tục lập luận tiến ..................................................................................153 5.3. Lập luận lùi .......................................................................................................158 5.3.1. Khái niệm lập luận lùi ...............................................................................158 5.3.2. Thủ tục lập luận lùi ....................................................................................160 2
5.4. Lập trình Prolog ................................................................................................166 5.4.1. Giới thiệu ngôn ngữ Prolog .......................................................................166 5.4.2. Cú pháp Prolog ..........................................................................................167 5.4.3. Các kiểu dữ liệu sơ cấp của Prolog ...........................................................169 5.4.4. Sự kiện và luật trong Prolog ......................................................................170 5.4.5. Kiểu dữ liệu cấu trúc của Prolog ...............................................................182 5.4.6. Ngữ nghĩa của chƣơng trình Prolog ..........................................................184 5.4.7. Các phép toán ............................................................................................190 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 5 ........................................................................203 HƢỚNG DẪN GIẢI BÀI TẬP ...................................................................................205 1. Bài tập Chƣơng 2 .................................................................................................205 2. Bài tập Chƣơng 3 .................................................................................................238 3. Bài tập Chƣơng 4 .................................................................................................248 4. Bài tập Chƣơng 5 .................................................................................................256 TÀI LIỆU THAM KHẢO ...........................................................................................259 3
DANH MỤC HÌNH VẼ Hình 1.1. Những tiền đề cơ bản của TTNT .....................................................................9 Hình 2.1. Mô tả không gian trạng thái bằng đồ thị định hƣớng ....................................27 Hình 2.2. Trò chơi 8 số ..................................................................................................28 Hình 2.3. Đồ thị biểu diễn cách rót nƣớc ......................................................................30 Hình 2.4. Biểu diễn không gian trạng của bài toán Tháp Hà Nội. ................................31 Hình 2.5. Một phần không gian trạng thái của bài toán với n=3 ...................................32 Hình 2.6. Đồ thị không gian trạng thái và cây tìm kiếm tƣơng ứng .............................34 Hình 2.7. Đồ thị không gian trạng thái ..........................................................................36 Hình 2.8. Đồ thị không gian trạng thái ..........................................................................40 Hình 2.9. Đồ thị không gian trạng thái ví dụ 2.13 .........................................................45 Hình 2.10. Các mức tìm kiếm trong cây tìm kiếm ví dụ 2.13 .......................................46 Hình 2.11. Đồ thị không gian trạng thái ví dụ 2.14 .......................................................46 Hình 2.12. Các mức tìm kiếm trong cây tìm kiếm ví dụ 2.14 .......................................47 Hình 2.13. Quy một tích phân về các tích phân cơ bản.................................................48 Hình 2.14. Bản đồ nối các thành phố ............................................................................48 Hình 2.15. Đồ thị và/hoặc và vấn đề tìm đƣờng đi .......................................................49 Hình 2.16. Đồ thị và hoặc biểu diễn toán tử a  b, c, d ...............................................49 Hình 2.17. Minh họa đồ thị và/hoặc ..............................................................................50 Hình 2.18. Cây nghiệm ..................................................................................................51 Hình 2.19. Đồ thị và/ hoặc trong Ví dụ 2.16 .................................................................54 Hình 2.20. Cây nghiệm trong ví dụ 2.16 .......................................................................55 Hình 2.21. Cây nghiệm trong ví dụ 2.17 .......................................................................56 Hình 2.22. Hai hàm đánh giá trạng thái u......................................................................57 Hình 2.23. Đồ thị không gian trạng thái ........................................................................58 Hình 2.24. Cây tìm kiếm tốt nhất – đầu tiên .................................................................59 Hình 2.25. Đồ thị không gian trạng thái ........................................................................60 Hình 2.26. Một phần đồ thị không gian trạng thái của ví dụ 2.22.................................61 Hình 2.27. Đồ thị không gian trạng thái ........................................................................63 Hình 2.28. Đồ thị không gian trạng thái ........................................................................64 Hình 2.29. Đồ thị không gian trạng thái với hàm đánh giá ...........................................66 Hình 2.30. Cây tìm kiếm theo thuật toán A* .................................................................67 Hình 2.31. Đồ thị không gian trạng thái ........................................................................69 Hình 2.32. Cây tìm kiếm nhánh _cận ............................................................................72 Hình 2.33. Đồ thị không gian trạng thái ........................................................................73 4
Hình 4.1. Đồ thị phân giải ...........................................................................................138 Hình 4.2. Một cây chứng minh từ đồ thị phân giải trong Hình 4.2 .............................139 Hình 4.3. Một cây chứng minh tìm đƣợc theo chiến lƣợc bề rộng .............................139 Hình 4.4. Đồ thị phân giải theo chiến lƣợc sử dụng tập hỗ trợ ...................................140 Hình 5.1. Biểu diễn tri thức bằng mạng ngữ nghĩa. ....................................................148 Hình 5.2. Các kiểu dữ liệu trong Prolog ......................................................................168 Hình 5.3. Cây gia hệ ....................................................................................................170 Hình 5.4. Định nghĩa quan hệ chị em gái ....................................................................176 Hình 5.5. (a) X là tổ tiên trực tiếp của Z, (b) X là tổ tiên gián tiếp của Z ...................179 Hình 5.6. Các cặp tổ tiên hậu duệ gián tiếp ở các mức khác nhau ..............................180 Hình 5.7. Ngày tháng là một đối tƣợng có cấu trúc ....................................................182 Hình 5.8. Mô hình vào/ra của một thủ tục thực hiện một danh sách các đích ............189 BẢNG KÝ HIỆU VIẾT TẮT STT Ký hiệu Ý nghĩa 1 TTNT Trí tuệ nhân tạo 2 CSTT Cơ sở tri thức 3 NSD Ngƣời sử dụng 5
CHƢƠNG 1. TỔNG QUAN VỀ TRÍ TUỆ NHÂN TẠO 1.1. Lịch sử phát triển của TTNT 1.1.1. Lịch sử hình thành và phát triển Trong lĩnh vực Công nghệ thông tin, Trí tuệ nhân tạo (Artificial Intelligence) là một ngành mới, nhƣng phát triển rất mạnh mẽ và đem lại nhiều kết quả to lớn. Lịch sử của TTNT cho thấy ngành khoa học này có nhiều kết quả đáng ghi nhận. Theo các mốc phát triển, ngƣời ta thấy TTNT đƣợc sinh ra từ những năm 50 của thế kỷ 20 với các sự kiện sau: Turing đƣợc coi là ngƣời khai sinh ngành TTNT bởi phát hiện của ông về máy tính có thể lƣu trữ chƣơng trình và dữ liệu. Phép thử Turing là một cách để trả lời câu hỏi „máy tính có biết nghĩ không?‟, đƣợc phát biểu dƣới dạng một trò chơi. Hình dung có ba ngƣời tham gia trò chơi, một ngƣời đàn ông (A), một ngƣời đàn bà (B) và một ngƣời chơi (C). Ngƣời chơi ngồi ở một phòng tách biệt với A và B, không biết gì về A và B (nhƣ hai đối tƣợng ẩn X và Y) và chỉ đặt các câu hỏi cũng nhƣ nhận trả lời từ A và B qua một màn hình máy tính. Ngƣời chơi cần kết luận trong X và Y ai là đàn ông ai là đàn bà. Trong phép thử này, A luôn tìm cách làm cho C bị nhầm lẫn và B luôn tìm cách giúp C tìm đƣợc câu trả lời đúng. Phép thử Turing thay A bằng một máy tính, và bài toán trở thành liệu C có thể phân biệt đƣợc trong X và Y đâu là máy tính đâu là ngƣời đàn bà. Phép thử Turing cho rằng máy tính là thông minh (qua đƣợc phép thử) nếu nhƣ biết cách làm sao cho C không thể chắc chắn kết luận của mình là đúng. Tuy phép thử Turing đến nay vẫn đƣợc xem có tầm quan trọng lịch sử và triết học hơn là giá trị thực tế (vì con ngƣời vẫn chƣa làm đƣợc máy hiểu ngôn ngữ và biết lập luận nhƣ vậy), ý nghĩa rất lớn của nó nằm ở chỗ đã nhấn mạnh rằng khả năng giao tiếp thành công của máy với con ngƣời trong một cuộc đối thoại tự do và không hạn chế là một biểu hiện chính yếu của trí thông minh nhân tạo. Tháng 8/1956 J.Mc Carthy, M. Minsky, A. Newell, Shannon. Simon… đƣa ra khái niêm"Trí tuệ nhân tạo”. Vào khoảng năm 1960 tại Đại học MIT (Massachussets Institure of Technology) ngôn ngữ LISP ra đời, phù hợp với các nhu cầu xử lý đặc trƣng của TTNT - đó là ngôn ngữ lập trình đầu tiên dùng cho TTNT. Thuật ngữ TTNT đƣợc dùng đầu tiên vào năm 1961 cũng tại MIT. Những năm 60 là giai đoạn lạc quan cao độ về khả năng làm cho máy tính biết suy nghĩ. Trong giai đoạn này ngƣời ta đã đƣợc chứng kiến máy chơi cờ đầu tiên và các chƣơng trình chứng minh định lý tự động. Cụ thể: - 1961: Chƣơng trình tính tích phân bất định 6
- 1963: Các chƣơng trình Heuristics: Chƣơng trình chứng minh các định lý hình học không gian có tên là"tƣơng tự”, chƣơng trình chơi cờ của Samuel. - 1964: Chƣơng trình giải phƣơng trình đại số sơ cấp, chƣơng trình trợ giúp ELIZA (có khả năng làm việc giống nhƣ một chuyên gia phân tich tâm lý). - 1966: Chƣơng trình phân tích và tổng hợp tiếng nói. Tuy nhiên, do giới hạn khả năng của các thiết bị, bộ nhớ và đặc biệt là yếu tố thời gian thực hiện nên có sự khó khăn trong việc tổng quát hoá các kết quả cụ thể vào trong một chƣơng trình mềm dẻo thông minh. Vào những năm 70, máy tính với bộ nhớ lớn và tốc độ tính toán nhanh nhƣng các phƣơng pháp tiếp cận TTNT cũ vẫn thất bại (do sự bùng nổ tổ hợp trong quá trình tìm kiếm lời giải các bài toán đặt ra). Vào cuối những năm 70 một vài kết quả nhƣ xử lý ngôn ngữ tự nhiên, biểu diễn tri thức và giải quyết vấn đề. Những kết quả đó đã tạo điều kiện cho sản phẩm thƣơng mại đầu tiên của TTNT ra đời đó là Hệ chuyên gia, đƣợc đem áp dụng trong các lĩnh vực khác nhau (Hệ chuyên gia là một phần mềm máy tính chứa các thông tin và tri thức về một lĩnh vực cụ thể nào đó, có khả năng giải quyết những yêu cầu của ngƣời sử dụng trong một mức độ nào đó, ở một trình độ nhƣ một chuyên gia con ngƣời có kinh nghiệm khá lâu năm). Một sự kiện quan trọng vào những năm 70 là sự ra đời ngôn ngữ Prolog, tƣơng tự LISP nhƣng nó có cơ sở dữ liệu đi kèm. Vào những năm 80, thị trƣờng các sản phẩm dân dụng đã có khá nhiều sản phẩm ở trình độ cao nhƣ: máy giặt, máy ảnh... sử dụng TTNT. Các hệ thống nhận dạng và xử lý ảnh, tiếng nói. Những năm 90, các nghiên cứu nhằm vào cài đặt thành phần thông minh trong các hệ thống thông tin, gọi chung là cài đặt TTNT, làm rõ hơn các ngành của khoa học TTNT và tiến hành các nghiên cứu mới, đặc biệt là nghiên cứu về cơ chế suy lý, về TTNT phân tạo, về các mô hình tƣơng tác. Hiện nay, nhiều lĩnh vực mới của TTNT đã ra đời và tiến triển sôi động theo sự thay đổi của môi trƣờng tính toán và tiến bộ khoa học. Chẳng hạn sự xuất hiện của những hệ dữ liệu lớn với quan hệ phức tạp nhƣ dữ liệu Web, dữ liệu sinh học, thƣ viện điện tử… đã là động lực ra đời các ngành khai phá dữ liệu, Web ngữ nghĩa, tìm kiếm thông tin trên Web. Thêm nữa, TTNT đã thâm nhập từ các khoa học vi mô nhƣ góp phần giải các bài toán của sinh học phân tử (tin-sinh học) đến các khoa học vĩ mô nhƣ nghiên cứu vũ trụ, rồi cả khoa học xã hội và kinh tế nhƣ phát hiện các cộng đồng mạng trong xã hội hay phân tích các nhóm hành vi. Trong các thành công của TTNT giai đoạn này có sự kiện máy tính thông minh tranh tài với các kỳ thủ cờ vua, và đặc biệt máy tính 7
Deep Blue của IBM với trí tuệ nhân tạo đã đánh bại nhà vô địch cờ vua thế giới Garry Kasparov vào năm 1997, và cuối năm 2006 máy tính Deep Fritz lại đánh bại nhà vô địch Kramnik. Một lĩnh vực tiêu biểu của TTNT trong giai đoạn này là các tác nhân thông minh. Tác nhân (agent), theo nghĩa chung nhất, là một thực thể có khả năng hành động để thực hiện những nhiệm vụ đƣợc giao. Một ngƣời đƣa hàng, một luật sƣ hay một điệp viên là những tác nhân. Một robot cứu ngƣời sau động đất hay một robot hút bụi trong nhà là những tác tử. Một chƣơng trình đƣợc cài trên máy tính để lọc thƣ rác hay một chƣơng trình luôn xục xạo trên Internet để tìm những thông tin mới về một chủ đề là những tác tử. tác nhân thông minh là những tác nhân biết hành động với các phẩm chất của trí thông minh, tiêu biểu là biết nhận thức môi trƣờng xung quanh và biết hƣớng các hành động tới việc đạt mục đích. Một robot hút bụi sẽ là thông minh nếu biết tìm đến các chỗ bẩn trong phòng để hút bụi và không đi tới những chỗ đã làm. 1.1.2. Đối tượng và mục tiêu nghiên cứu của TTNT TTNT nghiên cứu về cách hành xử thông minh với mục tiêu là xây dựng lý thuyết đầy đủ để có thể giải thích đƣợc hoạt động thông minh của sinh vật và áp dụng đƣợc các hiểu biết vào các máy móc nói chung, nhằm phục vụ cho con ngƣời. - Về mặt kỹ thuật: Tạo ra các máy thông minh để giải quyết vấn đề thực tế dùng các kỹ thuật TTNT. - Về mặt khoa học: Phát triển các khái niệm và thuật ngữ để hiểu đƣợc các hành xử thông minh của sinh vật. 1.1.3. Những tiền đề cơ bản của TTNT Những tiền đề ban đầu cho sự ra đời của TTNT là những nghiên cứu lý thuyết sâu sắc của các chuyên gia về logic hình thức, tâm lý học nhận thức (cognitive Psychology) và điều khiển học (Cybernetics). A Turing, ngƣời đặt nền móng lý thuyết cho tin học, tác giả của mô hình máy tính vạn năng đã đƣa ra mô hình máy tính dựa trên những phép tính logic cơ bản: AND, OR và NOT. Khi đó dự án này không đƣợc chấp nhận. Do chịu ảnh hƣởng của các chuyên gia Mỹ, ngƣời ta đã tiến hành chế tạo ra những máy tính đầu tiên, thực hiện các phép tính số học cơ bản. Dầu vậy, một nhóm các chuyên gia tin học vẫn tiếp tục nghiên cứu khả năng của máy tính xử lý các dữ liệu phi số, các ký hiệu. Một cách độc lập, các chuyên gia tâm lý học nhận thức cũng đã tạo dựng những mô hình dùng máy tính để mô phỏng hành vi của con ngƣời khi giải quyết những bài toán đòi hỏi sự sáng tạo. Lúc đó, các chƣơng trình TTNT lại quá phức tạp, quá tốn kém nên không thể đƣa ra áp dụng trong thực tiễn. 8
Những tiến bộ trong kỹ thuật vi điện tử đã tạo nên tiền đề vật chất có tính chất quyết định, làm thay đổi toàn bộ sự phát triển và ứng dụng các kỹ thuật TTNT Hình 1.1. Những tiền đề cơ bản của TTNT 1.2. Khái niệm về TTNT 1.2.1. Trí tuệ của con người Trí tuệ con ngƣời (Human Intelligence): Cho đến nay có hai khái niệm về trí tuệ con ngƣời đƣợc chấp nhận và sử dụng nhiều nhất, đó là: Khái niệm trí tuệ theo quan điểm của Turing:"Trí tuệ là những gì có thể đánh giá đƣợc thông qua các trắc nghiệm thông minh”. Khái niệm trí tuệ đƣa ra trong từ điển Bách khoa toàn thƣ: “Trí tuệ là khả năng: - Phản ứng một cách thích hợp những tình huống mới thông qua hiệu chỉnh hành vi một cách thích đáng; - Hiểu rõ những mối liên hệ qua lại của các sự kiện của thế giới bên ngoài nhằm đƣa ra những hành động phù hợp đạt tới một mục đích nào đó". Những nghiên cứu các chuyên gia tâm lý học nhận thức chỉ ra rằng quá trình hoạt động trí tuệ của con ngƣời bao gồm 4 thao tác cơ bản: (1) Xác định tập đích (goals). (2) Thu thập các sự kiện (facts) và các luật suy diễn (inference rules) để đạt đƣợc đích đặt ra. 9
(3) Thu gọn (pruning) quá trình suy luận nhằm xác định tập các suy diễn có thể sử dụng đƣợc. (4) Áp dụng các cơ chế suy diễn cụ thể (inference mechanisms) để đƣa các sự kiện ban đầu đi đến đích. 1.2.2. Trí tuệ nhân tạo Có nhiều khái niệm được đưa ra về trí tuệ nhân tạo: •"Sự nghiên cứu các năng lực trí tuệ thông qua việc sử dụng các mô hình tính toán"(“The study of mental faculties through the use ò computational models"– Charniak and McDormott, 1985). •"Nghệ thuật tạo ra các máy thực hiện các chức năng đòi hỏi sự thông minh khi đƣợc thực hiện bởi con ngƣời"(“The art of creating machies that perform functions that require intelligence when performed by people"– Kurzweil, 1990). •"Lĩnh vực nghiên cứu tìm cách giải quyết và mô phỏng các hành vi thông minh trong thuật 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"– Schalkoff, 1990). •"Sự nghiên cứu các tính toán để có thể nhận thức, lập luận và hành động"(“The study of computations that make it possible to perceive, reason, and act"– Winston, 1992). •"Một nhánh của khoa học máy tính liên quan tới sự tự động hoá các hành vi thông minh"(“The branch of computer science that is concerned with the automation of intelligent behavior"– Luger and Stubblefield, 1993) Sau đây là một số định nghĩa gần đây nhất: •"TTNT là sự thiết kế và nghiên cứu các chƣơng trình máy tính ứng xử một cách thông minh. Các chƣơng trình này đƣợc xây dựng để thực hiện các hành vi mà khi ở ngƣời hoặc động vật chúng ta xem là thông minh"(“Artificial Intelligence is the design and study of computer programs that behave intelligently.These programs are constructed to perform as would a human or an animal whose behvior we consider intelligent"– Dean, Allen and Aloimonos, 1995). •"TTNT là sự nghiên cứu các tác nhân tồn tại trong môi trƣờng, nhận thức và hành động"(“Artificial Intelligence is the design of agents that exists in an environment and act"– Russell and Norvig, 1995). •"TTNT là sự nghiên cứu ác thiết kế các tác nhân thông minh"(“Computational Intelligence is the study of the design of Intelligent agents"– Pulle, Mackworth and Goebel, 1998). 10
• Hiện nay nhiều nhà nghiên cứu quan niệm rằng, TTNT là lĩnh vực nghiên cứu sự thiết kế các tác nhân thông minh (intelligent agent). 1.3. Vai trò của TTNT trong công nghệ thông tin TTNT bao quát rất nhiều lĩnh vực nghiên cứu hẹp. Nó nghiên cứu từ các lĩnh vực tổng quát nhƣ máy nhận biết, suy luận logic, đến các bài toán nhƣ chơi cờ, chứng minh định lý. Thƣờng thì các nhà khoa học ở các lĩnh vực khác tìm đến với TTNT ở các kỹ thuật hệ thống hoá và tự động hoá các xử lý tri thức cũng nhƣ các phƣơng pháp thuộc lĩnh vực mang tính ngƣời. TTNT nghiên cứu kỹ thuật làm cho máy tính có thể"suy nghĩ một cách thông minh"và mô phỏng quá trình suy nghĩ của con ngƣời khi đƣa ra những quyết định, lời giải. Trên cơ sở đó, thiết kế các chƣơng trình cho máy tính để giải quyết bài toán. Sự ra đời và phát triển của TTNT đã tạo ra một bƣớc nhảy vọt về chất trong kỹ thuật và kỹ nghệ xử lý thông tin. TTNT chính là cơ sở của công nghệ xử lý thông tin mới, độc lập với công nghệ xử lý thông tin truyền thống dựa trên văn bản giấy tờ. Điều này đƣợc thể hiện qua các mặt sau: - Nhờ những công cụ hình thức hoá (các mô hình logic ngôn ngữ, logic mờ,...), các tri thức thủ tục và tri thức mô tả có thể biểu diễn đƣợc trong máy. Do vậy quá trình giải bài toán đƣợc tiến hành hữu hiệu hơn. - Mô hình logic ngôn ngữ đã mở rộng khả năng ứng dụng của máy tính trong lĩnh vực đòi hỏi tri thức chuyên gia ở trình độ cao, rất khó nhƣ: y học, sinh học, địa lý, tự động hóa. - Một số phần mềm TTNT thể hiện tính thích nghi và tính mềm dẻo đối với các lớp bài toán thuộc nhiều lĩnh vực khác nhau. - Khi máy tính đƣợc trang bị các phần mềm TTNT ghép mạng sẽ cho phép giải quyết những bài toán cỡ lớn và phân tán. 1.4. Các kỹ thuật TTNT Có nhiều kỹ thuật nghiên cứu, phát triển ngành khoa học TTNT. Tuy vậy, các kỹ thuật TTNT thƣờng khá phức tạp khi cài đặt cụ thể, lý do là các kỹ thuật này thiên về xử lý các ký hiệu tƣợng trƣng và đòi hỏi phải sử dụng những tri thức chuyên môn thuộc nhiều lĩnh vực khác nhau. Do vậy, các kỹ thuật TTNT hƣớng tới khai thác những tri thức về lĩnh vực đang quan tâm đƣợc mã hoá trong máy sao cho đạt đƣợc mức độ tổng quát, dễ hiểu, dễ diễn đạt thông qua ngôn ngữ chuyên môn gần gũi với ngôn ngữ tự nhiên; dễ sửa đổi, hiệu chỉnh; dễ sử dụng, khai thác nhằm thu hẹp các khả năng cần xét để đi tới lời giải cuối cùng. 11
Các kỹ thuật TTNT cơ bản bao gồm: Lý thuyết giải bài toán và suy diễn thông minh: Lý thuyết giải bài toán cho phép viết các chƣơng trình giải câu đố, chơi các trò chơi thông qua các suy luận mang tính ngƣời; các hệ thống chứng minh định lý. Ngoài ra các hệ thống hỏi đáp thông minh còn cho phép lƣu trữ và xử lý khối lƣợng lớn các thông tin. Lý thuyết tìm kiếm may rủi: Lý thuyết này bao gồm các phƣơng pháp và kỹ thuật tìm kiếm với sự hỗ trợ của thông tin phụ để giải bài toán một cách có hiệu quả. Các ngôn ngữ về TTNT: Để xử lý các tri thức ngƣời ta không chỉ sử dụng các ngôn ngữ lập trình dùng cho các xử lý dữ liệu số, mà cần có ngôn ngữ khác. Các ngôn ngữ chuyên dụng này cho phép lƣu trữ và xử lý thông tin ký hiệu. Một số ngôn ngữ đƣợc nhiều ngƣời biết đến là IPL.V, LISP, PROLOG. Lý thuyết thể hiện tri thức và hệ chuyên gia: TTNT là khoa học về thể hiện và sử dụng tri thức. Mạng ngữ nghĩa, lƣợc đồ, logic vị từ, khung là các phƣơng pháp thể hiện tri thức thông dụng. Việc gắn liền cách thể hiện và sử dụng tri thức là cơ sở hình thành hệ chuyên gia. Lý thuyết nhận dạng và xử lý tiếng nói: Giai đoạn phát triển đầu của TTNT gắn với lý thuyết nhận dạng. Các phƣơng pháp nhận dạng chính gồm: nhận dạng hình học, nhận dạng dùng tâm lý học, nhận dạng theo phƣơng pháp hàm thế, dùng máy nhận dạng, ứng dụng của phƣơng pháp này trong việc nhận dạng chữ viết, âm thanh. Người máy: Ngƣời máy có bộ phận cảm nhận và các cơ chế hoạt động đƣợc nối ghép theo sự điều khiển thông minh. Khoa học về cơ học và TTNT đƣợc tích hợp trong khoa học ngƣời máy. Tâm lý học xử lý thông tin: Các kết quả nghiên cứu của tâm lý học giúp TTNT xây dựng các cơ chế trả lời theo hành vi, có ý thức; nó giúp cho việc thực hiện các suy diễn mang tính ngƣời. Xử lý danh sách, kỹ thuật đệ quy, kỹ thuật quay lui và xử lý cú pháp hình thức: là những kỹ thuật cơ bản của tin học truyền thống có liên quan trực tiếp đến TTNT. 1.5. Các thành phần trong hệ thống TTNT Hai thành phần cơ bản trong bất kỳ một hệ thống TTNT là: - Các phƣơng pháp biểu diễn vấn đề, các phƣơng pháp biểu diễn tri thức; - Các phƣơng pháp tìm kiếm trong không gian bài toán, các chiến lƣợc suy diễn. Hai khía cạnh này trong một hệ thống TTNT tƣơng hỗ với nhau rất chặt chẽ, Việc lựa chọn một phƣơng pháp biểu diễn tri thức sẽ quyết định phƣơng pháp giải quyết tƣơng ứng để có thể áp dụng đƣợc. Chẳng hạn, nếu tri thức đƣợc biếu diễn dƣới dạng các công thức của logic vị từ, khi đó phƣơng pháp hợp giải (resolution) của Robinson 12
khá phù hợp và thƣờng đƣợc dùng để suy diễn. Ngƣợc lại, nếu phƣơng pháp biễu diễn tri thức là mạng ngữ nghĩa thì các thủ tục tìm kiếm sẽ hiệu quả hơn. Mặc dù phƣơng pháp biểu diễn tri thức sử dụng cú pháp chặt chẽ thƣờng rất hiệu quả cho việc biểu diễn và điều khiển quá trình suy diễn, nhƣng chúng lại không đủ mạnh để khắc phục bùng nổ tổ hợp khi giải những bài toán khó. Trong trƣờng hợp đó, các thủ tục tìm kiếm heuristics dựa trên các tri thức đặc tả nảy sinh từ chính bản thân cấu trúc của bài toán trở nên rất cần thiết. Có thể phân chia các hệ thống TTNT nhƣ sau: 1. Các hệ tìm kiếm thông tin, các hệ thống hỏi đáp thông minh cho phép hội thoại giữa những ngƣời sử dụng đầu cuối không chuyên tin với CSTT và cơ sở dữ liệu thông qua ngôn ngữ chuyên ngành gần với ngôn ngữ tự nhiên. 2. Các hệ thống suy diễn – tính toán, cho phép giải quyết những bài toán phức tạp dựa trên các mô hình toán học và tri thức chuyên gia. 3. Các hệ chuyên gia, cho phép sử dụng các tri thức chuyên gia trong các lĩnh vực tri thức chuyên biệt. 1.6. Các lĩnh vực nghiên cứu và ứng dụng cơ bản của TTNT Hai mối quan tâm nền tảng nhất của các nhà nghiên cứu TTNT là biểu diễn tri thức (knowledge representation) và tìm kiếm (search). Biểu diễn tri thức chú ý đến diễn tả vấn đề theo một ngôn ngữ hình thức, tức là một dạng thức thích hợp để máy tính vận hành, phạm vi tri thức đầy đủ mà hành vi thông minh đòi hỏi. Tìm kiếm là kỹ thuật giải quyết vấn đề theo cách khảo sát có hệ thống không gian trạng thái bài toán (problem state). Giống nhƣ hầu hết các ngành khoa học khác, TTNT cũng đƣợc phân thành những ngành con. Trong khi chia sẻ một tiếp cận giải quyết vấn đề cơ bản, các ngành con này có các mối quan tâm đến các ứng dụng khác nhau. Dƣới đây là tổng thể một vài lĩnh vực ứng dụng chính và những đóng góp của chúng cho TTNT. 1.6.1. Trò chơi Ngay từ thời kỳ đầu của việc nghiên cứu vấn đề tìm kiếm trong không gian trạng thái, ngƣời ta đã tiến hành nhiều thử nghiệm bằng cách sử dụng các trò chơi thông dụng có bàn cờ nhƣ cờ đam (checker), cờ vua và trò đố 15 ô (15 puzzule). Hầu hết các trò chơi đều sử dụng một tập hợp các luật chơi đƣợc xác định rõ ràng. Điều này làm cho việc phát sinh không gian tìm kiếm trở nên dễ dàng và giải phóng nhiều nghiên cứu khỏi những sự mơ hồ và phức tạp vốn có trong các bài toán ít cấu trúc hơn. Hình dạng của những bàn cờ sử dụng trong các trò chơi này đƣợc biểu diễn vào máy tính, 13
trong khi không đòi hỏi một hình thức khó hiểu cần thiết nào để nắm bắt những tinh tế và ngữ nghĩa trong những lĩnh vực bài toán phức tạp hơn. Các trò chơi có thể phát sinh ra một số lƣợng không gian tìm kiếm cực kỳ lớn. Những không gian này đủ lớn và phức tạp để đòi hỏi những kỹ thuật mạnh nhằm quyết định xem những chọn lựa nào cần đƣợc khảo sát trong không gian bài toán. Những kỹ thuật này đƣợc gọi là các heuristic và chúng tạo thành một lĩnh vực lớn trong nghiên cứu TTNT. Một heuristic là một chiến lƣợc giải quyết vấn đề tốt nhƣng tiềm ẩn khả năng thất bại, chẳng hạn nhƣ việc kiểm tra để biết chắc rằng một thiết bị không nhạy đã đƣợc cắm vào trƣớc khi giả định rằng nó bị hỏng, hay cố gắng bảo vệ quân cờ hoàng hậu khỏi bị bắt trong trò chơi cờ vua. Nhiều thứ mà chúng ta gọi là thông minh thuộc về các heuristic đƣợc ngƣời ta sử dụng để giải quyết các vấn đề. Hầu hết chúng ta đều có một số kinh nghiệm với những trò chơi đơn giản, nên chúng ta cũng có khả năng nghĩ ra và kiểm nghiệm tính hiệu quả của những heuristic của chính mình. Chúng ta không cần đi tìm và hỏi ý kiến chuyên gia trong một số lĩnh vực chuyên môn sâu nhƣ là y học hay toán học. Vì những lý do đó, các trò chơi cung cấp một không gian mênh mông cho việc nghiên cứu các tìm kiếm heuristic. Các chƣơng trình chơi trò chơi, trái ngƣợc với tính đơn giản của chúng, đƣa ra những thử thách riêng của chúng, bao gồm các đấu thủ mà các nƣớc đi của anh ta có thể không dự đoán trƣớc đƣợc một cách chắc chắn. Sự có mặt này của đấu thủ càng làm phức tạp hơn mô hình chƣơng trình do sự thêm vào một yếu tố không dự đoán trƣớc đƣợc và sự cần thiết phải tính đến những yếu tố tâm lý cũng nhƣ là chiến thuật trong chiến lƣợc của trò chơi. 1.6.2. Suy luận và chứng minh định lý tự động Chúng ta có thể cho rằng chứng minh định lý tự động là một nhánh nghiên cứu có từ lâu đời nhất của Trí tuệ nhân tạo khi tìm lại nguồn gốc của nó qua các tác phẩm"Nhà lý luận logic (logic theorist)"(Newell và Simon, 1963) và"Công cụ giải quyết vấn đề tổng quát (General problem solver)"(Newell và Simon, 1965) của Newell và Simon. Trong bất cứ trƣờng hợp nào, nó chắc chắn vẫn là một trong những ngành phong phú nhất của lĩnh vực này. Nghiên cứu chứng minh định lý đã đạt đƣợc nhiều thành tích trong thời kỳ đầu của việc hình thức hoá các giải thuật tìm kiếm và phát triển các ngôn ngữ biểu diễn hình thức nhƣ phép tính vị từ. Ngƣời ta có thể khảo sát một số lƣợng lớn những bài toán khác nhau, bằng cách biểu diễn mô tả của bài toán và những thông tin cơ sở liên quan nhƣ là tiên đề logic, và xem những trƣờng hợp bài toán là những định lý cần phải chứng minh. Sự hiểu biết thấu đáo này là cơ sở cho việc nghiên cứu chứng minh định lý tự động và các hệ suy luận toán học. Một lý do khác 14
cho việc tiếp tục quan tâm đến các máy chứng minh định lý tự động là sự nhận thức rằng một hệ thống kiểu nhƣ vậy không nhất thiết phải có khả năng giải quyết những bài toán cực kỳ phức tạp một cách độc lập mà không có sự trợ giúp nào của con ngƣời. Nhiều máy chứng minh định lý hiện đại hoạt động nhƣ những trợ lý viên thông minh khi chúng cho phép con ngƣời thực hiện những công tác đòi hỏi trình độ cao hơn là phân tích một bài toán lớn thành nhiều bài toán con và đặt ra những heuristic để tìm kiếm trong không gian những chứng minh có thể chọn. Máy chứng minh định lý sau đó thực hiện công tác đơn giản hơn nhƣng cũng quan trọng là chứng minh các bổ đề, kiểm chứng những giải quyết nhỏ hơn, và hoàn thành những khía cạnh hình thức của một chứng minh đã đƣợc phác thảo bởi sự hợp tác của nó với con ngƣời (Boyer và More, 1979). 1.6.3. Các hệ chuyên gia Kể từ lúc khoa học giải quyết vấn đề đƣợc nghiên cứu, ngƣời ta đã sớm ý thức một cách sâu sắc và cơ bản về tầm quan trọng của tri thức chuyên ngành. Lấy ví dụ một bác sĩ không thể chẩn đoán bệnh tốt chỉ nhờ vào một số kỹ năng giải quyết vấn đề tổng quát bẩm sinh; mà bác sĩ đã chẩn đoán tốt là vì có nhiều kiến thức y học. Tƣơng tự nhƣ thế, một nhà địa chất giỏi phát hiện các mỏ khoáng vì biết áp dụng một cách hiệu quả nhiều tri thức lý thuyết và thực nghiệm về địa lý. Tri thức chuyên gia về lĩnh vực là sự kết hợp giữa kiến thức lý thuyết về vấn đề đó và một tập hợp các quy tắc giải quyết vấn đề theo kiểu heuristic mà khi sử dụng những quy tắc này đã tỏ ra hiệu quả trong lĩnh vực đó. Các hệ chuyên gia đƣợc ngƣời ta xây dựng bằng cách thu thập các kiến thức từ chuyên gia ngƣời và mã hoá nó thành dạng thức mà máy tính có thể áp dụng cho những bài toán tƣơng tự. Sự tin cậy vào tri thức của chuyên gia chuyên ngành trong các chiến lƣợc giải quyết vấn đề của hệ là một đặc trƣng chính của các hệ chuyên gia. Ngƣời ta đã viết ra một số chƣơng trình mà ở đó ngƣời thiết kế cũng là nguồn tri thức chuyên ngành, nhƣng sẽ điển hình hơn nhiều nếu chúng ta xem xét những chƣơng trình đƣợc phát sinh từ sự cộng tác giữa một chuyên gia chuyên ngành chẳng hạn nhƣ một bác sĩ, một nhà hoá học, một nhà địa chất học hay một kỹ sƣ, với một chuyên gia riêng về trí tuệ nhân tạo. Chuyên gia chuyên ngành cung cấp kiến thức cần thiết về chuyên ngành thông qua những cuộc thảo luận tổng quát về các phƣơng pháp giải quyết vấn đề của anh ta, và bằng cách biểu diễn những kỹ năng đó trên một tập hợp các bài toán mẫu đƣợc chọn lựa cẩn thận. Chuyên gia TTNT, hay còn gọi là kỹ sƣ tri thức (knowledge engineer), nhƣ ngƣời ta vẫn thƣờng gọi là các nhà thiết kế hệ chuyên gia, có trách nhiệm thể hiện tri thức này vào một chƣơng trình mà chƣơng trình đó phải vừa hiệu quả vừa có vẻ 15
thông minh trong các hành vi của nó. Một chƣơng trình nhƣ thế vừa hoàn thành xong, cần phải tinh chế kiến thức chuyên môn của nó thông qua một quá trình cung cấp cho nó những bài toán mẫu để giải, để cho chuyên gia chuyên ngành phê bình hành vi của nó và thực hiện bất cứ thay đổi hay cải biến nào cần thiết đối với tri thức của chƣơng trình. Quá trình này lặp đi lặp lại cho đến khi chƣơng trình đạt đƣợc mức độ hoàn thiện mong muốn. Một trong các hệ chuyên gia sớm nhất khai thác tri thức chuyên ngành để giải quyết vấn đề là DENDRAL đƣợc phát triển tại Stanford vào cuối những năm 1960 (Lindsay et al,1980). DENDRAL đƣợc thiết kế để phỏng đoán cấu trúc của các phân tử hữu cơ từ công thức hoá học của chúng và các thông tin về khối quang phổ có liên quan đến các liên kết hoá học có mặt trong các phân tử. Vì các phân tử hữu cơ thƣờng rất lớn, nên số lƣợng cấu trúc có khả năng tồn tại đối với những phân tử này thƣờng là khổng lồ. DENDRAL chú ý vào bài toán của không gian tìm kiếm rộng lớn này bằng cách áp dụng tri thức heuristic của các chuyên gia hoá học vào bài toán làm sáng tỏ cấu trúc. Các phƣơng pháp của DENDRAL đã tỏ ra có một sức mạnh đáng kể. Khi thƣờng xuyên tìm thấy cấu trúc đúng trong hàng triệu khả năng khác nhau chỉ sau có vài phép thử. Phƣơng pháp này tỏ ra thành công đến mức ngƣời ta đã sử dụng những phiên bản của hệ chuyên gia nói trên trong các phòng thí nghiệm hoá học khắp nơi trên thế giới. Trong khi DENDRAL là một trong số những chƣơng trình đầu tiên sử dụng tri thức chuyên ngành một cách hiệu quả để đạt đƣợc khả năng giải quyết vấn đề cấp chuyên gia, thì MYCIN là hệ chuyên gia đã thiết lập nên phƣơng pháp luận cho các hệ chuyên gia hiện đại (contemporary expert systems) (Buchanan and Shortliff, 1984). MYCIN sử dụng tri thức y khoa chuyên gia để chẩn đoán và kê đơn điều trị cho bệnh viêm màng não tuỷ sống và những trƣờng hợp nhiễm trùng vi khuẩn trong máu. MYCIN, đƣợc các nhà nghiên cứu phát triển ở Stanford vào giữa những năm 1970, là một trong những chƣơng trình đầu tiên chú ý đến những bài toán suy luận bằng thông tin không chắc chắn hoặc không đầy đủ. MYCIN cung cấp những giải quyết rõ ràng và logic về quá trình suy luận của nó, sử dụng một cấu trúc kiểm tra thích hợp với lĩnh vực chuyên môn của vấn đề, và nhận biết đặc tính để đánh giá một cách tin cậy hoạt động của nó. Nhiều kỹ thuật xây dựng hệ chuyên gia đang dùng hiện nay đã đƣợc ngƣời ta phát triển lần đầu trong dự án MYCIN. Những hệ chuyên gia cổ điển khác bao gồm chƣơng trình PROSPECTOR dùng để tìm ra những nơi có chứa quặng mỏ và xác định loại quặng mỏ, dựa trên thông tin địa lý về một địa điểm nào đó, chƣơng trình INTERNIST dùng để chẩn đoán trong lĩnh vực nội khoa, Dipmeter Advisor dùng để phiên dịch các kết quả của các máy khoan 16
giếng dầu (Smith and Baker, 1983) và XCON dùng để định hình các máy tính hệ VAX. XCON đƣợc sử dụng từ năm 1981, tất cả các máy VAX và Digital Equipment Corporation bán thời bấy giờ đều đƣợc định hình bằng XCON. Rất nhiều hệ chuyên gia khác ngày nay đang giải quyết những bài toán trong nhiều lĩnh vực khác nhau nhƣ y học, giáo dục, kinh doanh, thiết kế và khoa học. Một điều thú vị mà chúng ta có thể nhận thấy là hầu hết các hệ chuyên gia đƣợc viết cho những lĩnh vực khá chuyên biệt và ở cấp độ chuyên gia. Nói chung những lĩnh vực này đều đƣợc nghiên cứu kỹ và chúng có những chiến lƣợc giải quyết vấn đề đã xác định một cách rõ ràng. Mặc dù còn tồn tại những hạn chế này các hệ chuyên gia vẫn đang chứng minh giá trị của chúng trong nhiều ứng dụng quan trọng. 1.6.4. Hiểu và mô hình hoá ngữ nghĩa ngôn ngữ tự nhiên Một trong những mục tiêu có từ lâu đời của Trí tuệ nhân tạo là tạo ra các chƣơng trình có khả năng hiểu ngôn ngữ của con ngƣời. Khả năng hiểu ngôn ngữ tự nhiên không chỉ là một trong những biểu hiện căn bản nhất của trí thông minh con ngƣời mà sự tự động hoá nó một cách thành công sẽ gây ra một tác động ngoài sức tƣởng tƣợng đối với năng lục và hiệu quả chính của những chiếc máy tính. Ngƣời ta đã bỏ ra nhiều công sức để viết các chƣơng trình có khả năng hiểu ngôn ngữ tự nhiên. Tuy những chƣơng trình này đã có đƣợc một số thành công trong những ngữ cảnh hạn chế, nhƣng các hệ thống có khả năng sử dụng ngôn ngữ tự nhiên một cách linh hoạt và tổng quát theo cách nhƣ con ngƣời vẫn còn ở ngoài tầm tay những phƣơng pháp luận hiện nay. Hiểu ngôn ngữ tự nhiên liên quan đến nhiều thứ hơn nhiều so với chỉ phân tích các câu thành các phần riêng rẽ những nhóm câu của chúng và tìm những từ đó trong từ điển. Khả năng hiểu thực sự tuỳ thuộc vào kiến thức nền tảng rộng lớn về lĩnh vực của bài văn và những thành ngữ dùng trong lĩnh vực đó, cũng nhƣ là khả năng ứng dụng những kiến thức tổng quát tuỳ thuộc theo ngữ cảnh để giải quyết những trƣờng hợp bỏ sót hay tối nghĩa, là một đặc điểm bình thƣờng trong lối nói con ngƣời. Công việc tập hợp và tổ chức kiến thức nền tảng này đƣợc tiến hành theo cách mà sao cho cách ấy có thể áp dụng đƣợc cho sự lĩnh hội ngôn ngữ, đã hình thành nên vấn đề chủ yếu của việc tự động hoá quá trình hiểu ngôn ngữ tự nhiên. Để đáp ứng yêu cầu này, các nhà nghiên cứu đã phát triển nhiều kỹ thuật dùng để cấu trúc hoá ý nghĩa ngữ nghĩa, các kỹ thuật này đƣợc dùng xuyên suốt khoa học TTNT. Do việc hiểu ngôn ngữ tự nhiên đòi hỏi những khối lƣợng kiến thức khổng lồ, hầu hết các công trình đƣợc ngƣời ta thực hiện trong những lĩnh vực vấn đề đã đƣợc hiểu rõ và chuyên môn hoá. Một trong những chƣơng trình khai thác sớm nhất phƣơng pháp luận"thế giới qui mô"này là SHRDLU của Winograd, một hệ ngôn ngữ tự nhiên 17
có khả năng"trò chuyện"về hình dáng đơn giản của các khối có nhiều hình dạng và màu sắc khác nhau (winograd, 1973). Mặc dù SHRDLU thành công với việc trò chuyện về sự sắp xếp của các khối, nhƣng phƣơng pháp của nó đã không đủ khái quát đƣợc để vƣợt ra khỏi thế giới các khối. Những kỹ thuật biểu diễn đƣợc sử dụng trong chƣơng trình này quá đơn giản nên không đủ để tổ chức nắm bắt ngữ nghĩa của nhiều lĩnh vực phong phú và phức tạp hơn một cách có kết quả. Nhiều sự đầu tƣ nghiên cứu về hiểu ngôn ngữ tự nhiên trong thời gian gần đây đƣợc ngƣời ta dành hết cho việc tìm ra những hình thức biểu diễn, mà về cơ bản đủ dùng trong một phạm vi rộng lớn các ứng dụng mà những ứng dụng này tự bản thân chúng còn chƣa thích nghi tốt với cấu trúc đặc thù của lĩnh vực đó. Ngƣời ta khảo sát một số lƣợng những kỹ thuật khác nhau (hầu hết đều là những mở rộng hay cải tiến của kỹ thuật mạng ngữ nghĩa) cho mục đích này và dùng chúng vào việc phát triển những chƣơng trình có khả năng hiểu ngôn ngữ tự nhiên trong những lĩnh vực tri thức cấp bách nhƣng lý thú. Chẳng hạn, chức năng trợ lý ảo"Siri"trên hệ điều hành IOS,"Cortana"trên hệ điều hành Windows phone là những minh chứng về khả năng hiểu ngôn ngữ tự nhiên (tiếng Anh) đã có nhiều tiến bộ vƣợt bậc. Tuy nhiên, hiểu ngôn ngữ tự nhiên một cách tổng quát là vấn đề vẫn còn vƣợt quá giới hạn hiện nay của chúng ta. 1.6.5. Mô hình hoá hoạt động của con người Mặc dù khá nhiều vấn đề đã nói ở trên dùng trí tuệ con ngƣời làm điểm tựa tham khảo để xem xét TTNT, thực tế đã không diễn biến theo cách mà những chƣơng trình cần phải lấy sự tổ chức của trí óc con ngƣời làm kiểu mẫu cho chúng. Thực ra nhiều chƣơng trình TTNT đƣợc thiết kế để giải một số bài toán cần thiết mà không cần chú ý đến tính tƣơng tự của chúng so với kiến trúc trí óc con ngƣời. Ngay cả các hệ chuyên gia, trong khi nhận đƣợc nhiều tri thức từ các chuyên gia con ngƣời, cũng không thực sự cố gắng bắt chƣớc những quá trình trí tuệ bên trong của con ngƣời. Nếu nhƣ sự hoạt động chỉ là những đặc tính mà theo đó một hệ thống sẽ đƣợc đánh giá, thì có thể là không có mấy lý do để mô phỏng các phƣơng pháp giải quyết vấn đề của con ngƣời. Trong thực tế, những chƣơng trình sử dụng các phƣơng pháp không theo kiểu con ngƣời để giải quyết các bài toán thƣờng thành công hơn những chƣơng trình theo kiểu con ngƣời. Tuy nhiên, mô hình của những hệ thống rõ ràng bắt chƣớc một số khía cạnh của cách giải quyết vấn đề theo kiểu con ngƣời vẫn là một mảnh đất màu mỡ trong nghiên cứu cho cả hai ngành khoa học TTNT và tâm lý học. Mô hình hóa hoạt động con ngƣời, ngoài việc cung cấp cho TTNT nhiều phƣơng pháp luận cơ bản, đã chứng tỏ đƣợc rằng nó là một dụng cụ mạnh để công thức hóa và thử nghiệm những lý 18
thuyết về sự nhận thức của con ngƣời. Những phƣơng pháp luận giải quyết vấn đề đƣợc các nhà khoa học máy tính phát triển đã đem đến cho các nhà tâm lý học một sự ẩn dụ mới để khảo sát trí tuệ con ngƣời. Hơn cả việc mở rộng đƣợc các lý thuyết về sự nhận thức trong thứ ngôn ngữ không rõ ràng sử dụng vào đầu thời kỳ nghiên cứu hay là từ bỏ đƣợc bài toán mô tả toàn bộ những hoạt động bên trong của trí óc con ngƣời (nhƣ đề nghị của các nhà hành vi học), nhiều nhà tâm lý học đã đƣa ngôn ngữ và lý thuyết khoa học máy tính vào để công thức hóa các mô hình trí tuệ con ngƣời. Những kỹ thuật này không chỉ cung cấp một vốn từ vựng cho việc mô tả trí tuệ con ngƣời mà sự thể hiện trên máy tính những lý thuyết này đã tạo cho các nhà tâm lý học một cơ hội để thử nghiệm, phê bình và cải tiến một cách thực nghiệm những ý tƣởng của họ (luger, 1994). 1.6.6. Lập kế hoạch và robotics Lập kế hoạch (planning) là một khía cạnh quan trọng trong những cố gắng nhằm chế tạo ra các robot có thể thực hiện đƣợc nhiệm vụ của chúng với một trình độ nhất định và khả năng linh hoạt và phản ứng với thế giới bên ngoài. Nói một cách khác ngắn gọn, việc lập kế hoạch giả định rằng robot có khả năng thực hiện những hành động sơ cấp (atomic action) nhất định. Nó cố gắng tìm ra một chuỗi các hành động cho phép hoàn thành một công tác ở cấp độ cao hơn, chẳng hạn nhƣ đi qua một căn phòng chứa đầy những chƣớng ngại vật. Có nhiều những lý do khiến cho việc lập kế hoạch trở thành một bài toán khó khăn. Ví dụ, chúng ta hãy tƣởng tƣợng rằng, một robot có khả năng di chuyển về phía trƣớc, phía sau, bên phải, bên trái và cần xem xét có bao nhiêu cách khác nhau mà robot đó có thể dùng để di chuyển quanh căn phòng đó và robot phải lựa chọn một đƣờng đi quanh chúng theo một phƣơng pháp nào đó có hiệu quả. Viết một chƣơng trình có khả năng tìm ra đƣờng đi tốt nhất một cách thông minh với điều kiện nhƣ vậy, mà không bị chôn vùi bởi khối lƣợng khổng lồ các khả năng dự kiến, đòi hỏi phải có những kỹ thuật phức tạp để biểu diễn tri thức về không gian và kiểm soát việc tìm kiếm trong môi trƣờng cho phép. Một phƣơng pháp mà con ngƣời vẫn áp dụng để lập kế hoạch là phân rã vấn đề từng bƣớc (hierarchical problem decoposition). Nếu bạn đang lập kế hoạch cho chuyến du lịch đến Pari, thì nói chung những vấn đề nhƣ sắp xếp chuyến bay, đến sân bay, liên hệ với hãng hàng không, vận chuyển đƣờng bộ tại Pari sẽ đƣợc bạn xem xét một cách riêng lẻ, cho dù tất cả chúng đều là bộ phận của một kế hoạch toàn thể lớn hơn. Từng vấn đề này có thể đƣợc tiếp tục phân rã thành những vấn đề con (subproblem) nhỏ hơn nhƣ tìm một bản đồ thành phố, xem xét hệ thống giao thông, và tìm một nơi ăn ở phù 19
hợp điều kiện về tài chính. Cách làm này không những làm giảm bớt một cách hiệu quả không gian tìm kiếm mà nó còn cho phép chúng ta tiết kiệm đƣợc những kế hoạch con có thể dùng trong tƣơng lai. Trong khi con ngƣời lập kế hoạch một cách chẳng mấy khó khăn, thì việc tạo ra một chƣơng trình máy tính có thể làm đƣợc công việc nhƣ vậy là một thách thức ghê gớm. Một công tác có vẻ đơn giản là phân rã một vấn đề lớn thành nhiều vấn đề con liên quan thực sự cần đến những heuristic phức tạp và kiến thức bao quát về lĩnh vực đang lập kế hoạch. Quyết định xem cần giữ lại những kế hoạch con nào và tổng quát hóa chúng nhƣ thế nào cho sự sử dụng trong tƣơng lai là một vấn đề phức tạp tƣơng đƣơng. Một robot thực hiện một dãy các hành động một cách mù quáng mà không biết phản ứng lại với những thay đổi trong môi trƣờng hoặc không có khả năng phát hiện và sửa chữa trong chính kế hoạch của nó khó có thể đƣợc ngƣời ta coi là thông minh. Thông thƣờng, một robot sẽ phải làm thành công thức một kế hoạch dựa trên thông tin không đầy đủ và sửa chữa hành vi của nó khi thi hành kế hoạch. Robot có thể không có những giác quan thích hợp để định vị tất cả những chƣớng ngại vật trên con đƣờng đi đã vạch ra. Một robot nhƣ vậy phải bắt đầu di chuyển qua căn phòng dựa vào những gì mà nó"nhận thức"đƣợc và điều chỉnh đƣờng đi của nó khi phát hiện ra những chƣớng ngại vật khác. Thiết lập cho các kế hoạch cho phép có thể phản ứng lại với những điều kiện của môi trƣờng là một nhiệm vụ chủ yếu khác trong lập kế hoạch. Nói chung, thiết kế robot là một trong những lĩnh vực nghiên cứu của TTNT đã mang lại nhiều hiểu biết sâu sắc hỗ trợ cho phƣơng pháp giải quyết vấn đề theo kiểu hƣớng tác nhân (agent - oriented). Bị thất bại bởi những phức tạp trong việc bảo đảm độ lớn của không gian biểu diễn cũng nhƣ bởi mô hình của các thuật toán tìm kiếm dùng cho việc lập kế hoạch theo kiểu truyền thống, các ngành nghiên cứu, gồm cả agre và chapman (1987) và brooks (1991), đã phát biểu lại vấn đề lớn hơn này dựa trên các thuật ngữ về sự tƣơng tác lẫn nhau giữa nhiều tác nhân (agent) theo kiểu bán tự quản. Mỗi thành viên chịu trách nhiệm về phần đóng góp của chính nó trong nhiệm vụ của bài toán và thông qua sự phối hợp giữa chúng lời giải tổng quát sẽ hiện ra. 1.6.7. Các ngôn ngữ và môi trường dùng cho TTNT Nghiên cứu TTNT đã tạo ra một số những tiến bộ trong các ngôn ngữ lập trình và các môi trƣờng phát triển phần mềm. Vì nhiều lý do, bao gồm cả qui mô tổng thể của hầu hết các chƣơng trình TTNT, khuynh hƣớng phát sinh ra các không gian khổng lồ của các thuật toán tìm kiếm, và những khó khăn trong việc tiên đoán các hành vi của các chƣơng trình điều khiển bằng heuristics, các nhà lập trình TTNT đã bị thúc ép phải xây dựng nên một tập hợp các phƣơng pháp lập trình. 20