Chương 9: Học máy
Võ Huỳnh Trâm – Trần Ngân Bình
1
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.
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
Võ Huỳnh Trâm – Trần Ngân Bình
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.
00 xx
0
0
x x x
x x x
x
x
x
x
xx x x x xx x x x x
x x x x x x
x x x x x x
0 0
0 0 0
00 0
0 0
x
x
0 0
x x
x x
0 0 0 0 0 0 0 0
xx 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.
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.
không
có
có không
không
có
. . .
Trục trặc ở đâu ?
Trục trặc do động cơ
Hỏi: xe có nổ máy
không ?
Trục trặc do
bộ truyền dẫn
Hỏi : ...
Trục trặc
do phanh
Hỏi : ...
Động cơ nổ
máy được
Hỏi : ....
Động cơ không nổ máy được
Hỏi : Động cơ có khởi động
điện được không?
Động cơ khởi
động điện được.
Hỏi: . . .
Động cơ khởi động điện
không được.
Hỏi: Đèn có sáng không?
Bình điện tốt Hư bình điện
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
Võ Huỳnh Trâm – Trần Ngân Bình
5
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.
