Giáo trình Trí tuệ nhân tạo (Phần 2)

oài kết quả đạt được trên, NETtalk còn cho thấy một số tính chất đáng chú ý của 
mạng neuron, có nhiều tính chất trong số đó phản ánh bản chất tự nhiên của việc học ở 
người. Chẳng hạn như, việc học, khi được đo bằng phần trăm câu trả lời đúng, sẽ tiến 
triển nhanh lúc đầu, sau đó chậm dần khi tỉ lệ đúng tăng lên. Và cũng như con người, 
khi neuron càng học phát âm được nhiều từ, thì nó càng phát âm đúng các từ mới 
nhiều hơn. 
IV.3 Ví dụ 2: Exclusive–or 
Một ví dụ khác cho mạng đa tầng là dùng để giải quyết bài toán Ex-or mà mạng đơn 
tầng không thể phân loại được. 
Hình 8.12 minh họa mạng với hai đầu vào, một nút ẩn và một nút đầu ra. Mạng cũng 
có hai đầu vào thiên lệch (bias), một đi vào nút ẩn và một đi vào nút đầu ra. Một điểm 
đặc biệt là các đầu vào cũng được nối trực tiếp vào nút đầu ra. Liên kết thêm vào này 
cho phép nhà thiết kế mạng neuron đạt được một mạng với ít nút hơn trên tầng ẩn và 
hội tụ nhanh hơn. 
Giá trị net cho nút ẩn và nút đầu ra cũng được tính như cách thông thường, là tổng của 
các tích giữa giá trị đầu nhân với trọng số. Các trọng số được điều chỉnh theo giải 
thuật học lan truyền ngược và sử dụng hàm kích hoạt sigmoidal. 
Thật ra, mạng neuron trong hình 8.12 không phải là một mạng duy nhất có thể giải 
quyết bài toán này. 
101 
Hình 8.12 - Một mạng lan truyền ngược dùng để giải quyết bài toán exclusive-or. 
Mạng này được rèn luyện với 4 ví dụ: (0,0) → 0; (1,0) → 1; (0,1) → 1; (1,1) → 0 
Sau khi được huấn luyện 1400 lượt với 4 dữ liệu trên, các trọng số hội tụ về các giá trị 
như sau: 
W
H1 
= -7.0 W
HB 
= 2.6 W
O1 
= -5.0 W
H2 
= -7.0 
W
OB 
= 7.0 W
O2 
= -4.0 W
OH 
= -11.0 
Với giá trị đầu vào là (0,0), giá trị đầu ra của nút ẩn sẽ là: 
f(0 * (-7.0) + 0 * (-7.0) + 1* 2.6 ) = f(2.6) → 1 
Kết quả trả về của nút đầu ra cho (0,0) sẽ là: 
f(0 * (-5.0) + 0 * (-4.0) + 1 * (-11.0) + 1 * (7.0)) = f(-4.0) → 0 
Như vậy, ta thấy rằng mạng lan truyền ngược đã phân loại được các điểm dữ liệu 
không tuyến tính. 
V. Nhận xét chung về mạng neuron 
Nói chung các mạng đa tầng là đầy đủ về mặt tính toán (computationally complete), 
có nghĩa là có thể giải quyết được mọi bài toán. Tuy nhiên, để thiết kế một mạng 
neuron đa tầng thì nhà thiết kế phải giải quyết được những vấn đề sau: 
 - Làm sao để chọn số nút ẩn và số tầng ẩn thích hợp? 
 - Khi nào sử dụng các nút thiên lệch? 
 - Cách chọn một tập rèn luyện? 
 - Điều chỉnh các trọng số như thế nào? 
 - Nên chọn tốc độ học như thế nào? 
Nói chung, không có một quy luật nào về tất cả những điều này, nó phụ thuộc vào 
kinh nghiệm của nhà thiết kế, cũng như là kết quả của quá trình thử-sai lặp đi lặp lại. 
102 
Chương IX 
 TIẾP CẬN XÃ HỘI VÀ NỔI TRỘI: GIẢI THUẬT DI 
TRUYỀN (GENETIC ALGORITHM - GA) 
Cũng như các mạng neuron, các thuật toán di truyền cũng dựa trên một ẩn dụ sinh 
học: Các thuật toán này xem việc học như là sự cạnh tranh trong một quần thể gồm 
các lời giải ứng viên đang tiến hóa của bài toán. Một hàm ‘thích nghi’ (fitness 
function) sẽ đánh giá mỗi lời giải để quyết định liệu nó có đóng góp cho thế hệ các lời 
giải kế tiếp hay không. Sau đó, thông qua các phép toán tương tự với biến đổi gene 
trong sinh sản hữu tính, giải thuật sẽ tạo ra một quần thể các lời giải ứng viên mới. 
I. Giải thuật 
Hình 9.1- Giải thuật di truyền. 
Hình 9.1 mô tả giải thuật di truyền tổng quát. Tùy theo từng bài toán mà nhà thiết kế 
giải thuật sẽ phải mô tả chi tiết hơn về: 
 Phương pháp biểu diễn một cá thể trong quần thể các lời giải ứng viên của bài 
toán, hay nói khác hơn là hình thức biểu diễn một lời giải tiềm năng của bài toán. 
Không phải lời giải của mọi bài toán đều có thể được mã hóa một cách dễ dàng và 
tự nhiên dưới dạng biểu diễn mức bit như trong bài toán thỏa mãn CNF dưới đây. 
 Độ lớn của quần thể là số lượng ứng viên có trong quần thể. Thông thường các 
ứng viên của quần thể ban đầu được chọn một cách ngẫu nhiên. Độ lớn của quần 
103 
thể là không đổi qua các thế hệ, vì vậy, sẽ có một quá trình chọn lọc và loại bỏ một 
số lời giải ứng viên có độ thích nghi thấp. 
 Điều kiện dừng của vòng lặp: có thể là chương trình đạt tới một số lần lặp nhất 
định nào đó, hay đạt tới trung bình độ tốt nào đó của quần thể, 
 Hàm đánh giá (fitness function): Dùng để đánh giá một ứng viên có tốt hay không. 
Một ứng viên càng tốt nghĩa là độ thích nghi của nó càng cao và tiến đến trở thành 
lời giải đúng của bài toán. Việc thiết kế một hàm đánh giá tốt là rất quan trọng 
trong thuật toán di truyền. Một hàm đánh giá không chính xác có thể làm mất đi 
các ứng viên tốt trong quần thể. 
 Chọn lựa bao nhiêu phần trăm lời giải tốt để giữ lại? Hay chọn bao nhiêu lời giải 
ứng viên để kết hợp với nhau và sinh ra lời giải con? 
 Phương pháp tạo thành viên mới từ thành viên hiện có, còn gọi là toán tử di truyền 
(genetic operators): Các toán tử di truyền phổ biến là 
 o Lai ghép (cross-over): Toán tử lai ghép lấy hai lời giải ứng viên và chia từng 
lời giải ra thành hai phần, sau đó trao đổi các phần với nhau để tạo ra ứng viên 
mới. Ví dụ xem hình 9.18. 
 o Đột biến (mutation): Đột biến lấy một ứng viên đơn lẻ và thay đổi một cách 
ngẫu nhiên một khía cạnh nào đó của nó. Ví dụ xem hình 9.2. 
Hình 9.2 - Ví dụ minh họa giải thuật và toán tử di truyền. 
Trong ví dụ minh họa bằng hình 9.2, ta thấy tại thế hệ thứ n ta có một lời giải có độ 
thích nghi rất thấp (2), và vì vậy, nó không được sử dụng trong quá trình tái sản xuất. 
Thay vào đó, lời giải có độ thích nghi cao nhất (13) sẽ được nhân đôi và đưa vào quá 
trình tái sản xuất. 
Hoặc ít phổ biến hơn là các toán tử di truyền: 
 o Đảo ngược (inversion): Đảo ngược thứ tự các bit trong mẫu lời giải. 
 o Trao đổi (Exchange): Trao đổi hai bit bất kỳ trong mẫu lời giải với nhau. 
104 
Một toán tử di truyền tốt đóng một vai trò quan trọng trong thuật toán di truyền. Toán 
tử di truyền phải bảo toàn những mối quan hệ cốt yếu trong quần thể; ví dụ, sự có mặt 
và sự duy nhất của tất cả các thành phố trong hành trình của người bán hàng trong bài 
toán người đi bán hàng. 
 - Thay thế thành viên mới cho các thành viên hiện có như thế nào? 
 -  
II Ví dụ 1: Bài toán thỏa CNF 
Bài toán thỏa mãn dạng chuẩn hội (Conjunctive normal form – CNF) là một bài toán 
đơn giản: Một biểu thức của các mệnh đề (clause) ở dạng chuẩn hội hay CNF khi nó 
là một dãy các biến mệnh đề được kết nối với nhau bởi toán tử quan hệ and (∧). Mỗi 
mệnh đề có dạng là một tuyển (disjunction), gồm các toán tử quan hệ or (∨) trên các 
biến mệnh đề (literal). 
Ví dụ : Nếu ta có 6 biến mệnh đề a, b, c, d, e và f, thì biểu thức sau đây là một CNF: 
(¬a ∨ c) ∧ (¬a ∨ c ∨ ¬e) ∧ (¬b ∨ c  d ∨ ¬e) ∧ (a ∨ ¬b ∨ c) ∧ (¬e ∨ f) (1-
3) 
Thỏa mãn CNF có nghĩa rằng chúng ta phải tìm ra một phép gán true hoặc false (1 
hoặc 0) cho mỗi biến mệnh đề a, b, c, d, e, f sao cho biểu thức CNF có giá trị là 
TRUE. 
Một cách biểu diễn tự nhiên cho lời giải của bài toán này là một dãy sáu bit, mỗi bit 
theo thứ tự a, b, c, d, e, f biểu diễn true (1) hoặc false (0) cho mỗi biến mệnh đề. Như 
vậy mẫu bit: 
1 0 1 0 1 0 
cho biết a, c, và e là true và b, d, và f là false, và do đó khi thay các giá trị này vào 
biểu thức (1-3), thì cho giá trị false. 
Chúng ta muốn rằng các toán tử di truyền sinh ra các thế hệ lời giải sao cho biểu thức 
CNF mang trị true, vì vậy mỗi toán tử phải sinh ra một mẫu 6-bit của phép gán true 
cho biểu thức. Cách biểu diễn lời giải dưới dạng một mẫu các bit như trên mang lại 
cho ta rất một điều rất thuận lợi là bất kỳ toán tử di truyền nào (lai ghép, đột biến, đảo 
ngược, hay trao đổi) đều tạo ra một mẫu bit mới là một lời giải khả dĩ hợp lệ. 
Việc chọn lựa một hàm thích nghi cho quần thể các chuỗi bit này không phải hoàn 
toàn dễ dàng. Thoạt nhìn chuỗi bit, ta khó có thể xác định một hàm thích nghi để đánh 
giá được chất lượng của nó như thế nào, nghĩa là khó đoán được độ tốt của nó so với 
105 
đáp án đúng. Đáp án đúng ở đây chính là chuỗi bit sao cho biểu thức CNF có giá trị 
true. 
Tuy nhiên có một số cách khác. Nếu ta chú ý đến biểu thức CNF (1-3), thì ta thấy rằng 
nó được tạo thành từ hội của 5 mệnh đề. Do đó chúng ta có thể thiết lập một hệ phân 
hạng cho phép chúng ta sắp hạng các lời giải (mẫu bit) tiềm năng trong khoảng giá trị 
từ 0 đến 5, tùy thuộc vào số mệnh đề mà mẫu đó thỏa mãn. Do đó mẫu: 
1 1 0 0 1 0 có độ thích nghi là 1 
0 1 0 0 1 0 có độ thích nghi là 2 
0 1 0 0 1 1 có độ thích nghi là 3 
1 0 1 0 1 1 có độ thích nghi là 5, và nó chính là một lời giải. 
III. Ví dụ 2: Bài toán người đi bán hàng TSP 
Bài toán người bán hàng (traveling salesperson problem – TSP) là một bài toán cổ 
điển đối với AI và khoa học máy tính1. Như chúng đã giới thiệu ở chương III, toàn bộ 
không gian trạng thái của nó đòi hỏi phải xem xét N! trạng thái để có thể tìm ra lời 
giải tối ưu, trong đó N là số thành phố cần đi qua. Khi N khá lớn thì bài toán sẽ bị 
bùng nổ tổ hợp, vì vậy người ta đặt vấn đề là có cần thiết hay không cho việc chạy 
một máy trạm làm việc đắt tiền trong nhiều giờ để cho một lời giải tối ưu hay chỉ nên 
chạy một PC rẻ tiền trong vài phút để có được những kết quả “đủ tốt”. Giải thuật di 
truyền chính là một giải pháp cho lựa chọn thứ hai. 
Ở bài toán này, dùng mẫu bit để biểu diễn cho lời giải của bài toán không phải là một 
cách hay. Chẳng hạn, ta có chín thành phố cần ghé thăm 1, 2, 9, ta xem mỗi thành 
phố như một mẫu 4 bit 0001, 0010, 1001. Khi đó một lời giải khả dĩ sẽ có hình thức 
như sau: 
0001 0010 0011 0100 0101 0110 0111 1000 1001 
Với cách biểu diễn như vậy, việc thiết kế các toán tử di truyền sẽ trở nên rất khó khăn. 
Toán tử lai ghép nhất định là không được, vì chuỗi mới được tạo từ hai cha mẹ khác 
nhau hầu như sẽ không biểu diễn một đường đi trong đó ghé thăm mỗi thành phố đúng 
một lần. Trong thực tế, với lai ghép, một số thành phố có thể bị xóa bỏ trong khi các 
thành phố khác được ghé thăm nhiều hơn một lần, và vì vậy đó không phải là một lời 
giải hợp lệ. Còn toán tử đột biến thì thế nào? Giả sử bit trái nhất của thành phố thứ 
sáu, 0110, được đột biến thành 1? 1110, hay là 14, thì nó không còn là một thành phố 
hợp lệ. 
Một cách tiếp cận khác là sẽ bỏ qua biểu diễn dạng mẫu bit và đặt cho mỗi thành phố 
một tên theo bảng chữ cái hoặc số, ví dụ 1, 2, 9; xem đường đi qua các thành phố là 
một sự sắp thứ tự của chín ký số này, và sau đó chọn toán tử di truyền thích hợp để tạo 
ra các đường đi mới. Ở đây ta thấy phép trao đổi (exchange) ngẫu nhiên hai thành phố 
trong đường đi có thể sử dụng được, còn phép toán lai ghép (crossover) thì không. 
Việc trao đổi các đoạn của một đường đi với những đoạn khác của cùng đường đi đó, 
hoặc bất cứ toán tử nào sắp xếp lại các chữ cái của đường đi ấy (mà không xóa bỏ, 
thêm, hay nhân đôi bất cứ thành phố nào) đều có thể sử dụng được. Tuy nhiên, những 
phương pháp này gây khó khăn cho việc đưa vào thế hệ con cháu những thành phần 
106 
“tốt hơn” của các mẫu trong các đường đi qua của các thành phố của hai cha mẹ khác 
nhau. 
Nhiều nhà nghiên cứu đã đưa ra các toán tử lai ghép có khả năng khắc phục những 
vấn đề này, trong đó có toán tử lai ghép có thứ tự (order crossover) do Davis đưa ra 
vào năm 1985. Lai ghép có thứ tự xây dựng con cháu bằng cách chọn một dãy con các 
thành phố trong đường đi của một mẫu cha mẹ. Nó cũng bảo toàn thứ tự tương đối các 
thành phố từ cha mẹ kia. Đầu tiên, chọn hai điểm cắt, biểu thị bởi dấu “|”, điểm cắt 
này được chen vào một cách ngẫu nhiên vào cùng một vị trí của mỗi mẫu cha mẹ. 
Những điểm cắt này là ngẫu nhiên, nhưng một khi được chọn, thì những vị trí như 
nhau sẽ được sử dụng cho cả hai cha mẹ. Ví dụ, có hai mẫu cho mẹ p1 và p2, với các 
điểm cắt sau thành phố thứ ba và thứ bảy: 
p1 = (1 9 2 | 4 6 5 7 | 8 3) 
p2 = (4 5 9 | 1 8 7 6 | 2 3) 
1 
Phát biểu của bài toán TSP: Một người bán hàng có nhiệm vụ ghé thăm N thành phố 
như là một phần của lộ trình bán hàng. Đường đi giữa mỗi cặp thành phố có một chi 
phí (ví dụ như độ dài đoạn đường, giá vé máy bay). Hãy tìm ra đường đi có chi phí 
thấp nhất cho người bán hàng để bắt đầu lên đường tại một thành phố, thăm tất cả các 
thành phố khác chỉ đúng một lần rồi quay lại thành phố xuất phát. 
Hai mẫu con c1 và c2 sẽ được sinh ra theo cách sau. Đầu tiên, các đoạn giữa hai điểm 
cắt sẽ được chép vào các mẫu con: 
c1 = (x x x | 4 6 5 7 | x x) 
c2 = (x x x | 1 8 7 6 | x x) 
Bước kế tiếp là bắt đầu từ điểm cắt thứ hai của một trong hai mẫu cha mẹ, nếu ta đang 
muốn hoàn tất mẫu c1, thì ta sẽ bắt đầu từ điểm cắt thứ hai của mẫu p2, ta chép các 
thành phố từ điểm cắt này theo thứ tự vào các chỗ còn trống của c1, bỏ qua những 
thành phố mà c1 đã có (các ký số được in đậm và nghiêng trong sơ đồ bên dưới). Khi 
đến cuối mẫu p2, thì quay lại đầu mẫu p2 tiếp tục chép sang c1 cho đến khi c1 đủ. 
p2 = (4 5 9 | 1 8 7 6 | 2 3) p1 = (1 9 2 | 4 6 5 7 | 8 3) 
c1 = (2 3 9 | 4 6 5 7 | 1 8) c2 = (3 9 2 | 1 8 7 6 | 4 5) 
Với giải thuật lai ghép này, các đường đi của thế hệ con sẽ được đảm bảo là các 
đường đi hợp lệ, đi qua mỗi thành phố một lần duy nhất. 
Tóm lại, trong lai ghép thứ tự, các mảnh của một đường đi được truyền từ một cha 
mẹ, p1, sang một con, c1, trong khi sắp xếp của các thành phố còn lại của con c1 được 
thừa kế từ cha mẹ kia, p2. Điều này ủng hộ cho trực giác hiển nhiên là thứ tự của các 
thành phố đóng vai trò quan trọng trong việc tạo ra đường đi với chi phí thấp nhất, và 
vì vậy việc truyền lại các đoạn thông tin có thứ tự này từ các cha mẹ có độ thích nghi 
cao sang con cái là một điều rất quan trọng. 
107 
Ngoài toán tử lai ghép thứ tự trên, còn có rất nhiều toán tử lai ghép và đột biến khác 
được đưa ra để giải quyết bài toán này. Bảng 9.1 liệt kê các toán tử lai ghép, bảng 9.2 
liệt kê các toán tử đột biến. 
Bảng 9.1 - Danh sách các toán tử lai ghép cho bài toán TSP. 
Bảng 9.2 - Danh sách các toán tử đột biến cho bài toán TSP. 
IV. Đánh giá giải thuật 
Các ví dụ vừa nêu trên làm nổi bật những vấn đề mang tính duy nhất của thuật toán di 
truyền về biểu diễn tri thức, chọn toán tử di truyền, và thiết kế hàm thích nghi. Biểu 
diễn được chọn phải hỗ trợ cho các toán tử di truyền. Một điểm dáng lưu ý nữa là các 
toán tử di truyền phải được thiết kế sao cho bảo lưu được những mảnh thông tin có ý 
nghĩa trong lời giải tiềm năng từ thế hệ này sang các thế hệ tiếp theo. 
Một sức mạnh quan trọng của thuật toán di truyền là bản chất song song trong tìm 
kiếm của nó. Các thuật toán này thực hiện một dạng mạnh của leo núi (hill climbing) 
108 
trong đó duy trì nhiều lời giải (trong quần thể các lời giải), loại bỏ những lời giải 
không có triển vọng, và nâng cao chất lượng của những lời giải tốt. Hình 9.3 phỏng 
theo Holland (1986), cho thấy nhiều lời giải hội tụ về các điểm tối ưu trong không 
gian tìm kiếm. Trong hình này, trục hoành biểu diễn các điểm có thể có trong không 
gian lời giải, trong khi trục tung phản ánh chất lượng của những lời giải đó. Các điểm 
chấm nằm trên cung là các thành viên của quần thể hiện tại. Khởi đầu, những lời giải 
được rải trong không gian những lời giải có thể có. Sau một vài thế hệ, chúng có 
khuynh hướng cụm lại xung quanh những vùng có chất lượng lời giải cao hơn. 
Hình 9.3- Các thuật toán di truyền được xem là leo núi song song (theo Holland 1986) 
Tuy nhiên, với sức mạnh như vậy, giải thuật genetic cũng không thể áp dụng cho tất 
cả các bài toán có thể có. Vì như ta thấy qua hai ví dụ trên, lời giải của bài toán phải 
được biểu diễn dưới một dạng mẫu thích hợp cho các toán tử di truyền hoạt động. 
Trong thực tế có nhiều bài toán không thể làm được điều này. Vì vậy, khi nghiên cứu 
về giải thuật này, có rất nhiều câu hỏi đã được đưa ra nhằm hiểu rõ hơn nữa về bản 
chất hoạt động của nó: 
1. Liệu chúng ta có thể đưa ra những đặc điểm về các loại bài toán mà giải thuật di 
truyền (GA) có thể thực hiện tốt 
2. Các loại bài toán nào thì không thích hợp với GA. 
3. Dựa vào đâu để ta có thể nói là GA thực hiện tốt hay không tốt đối với một loại bài 
toán nào đó? 
4. Liệu có những qui luật nào mô tả hành vi của GA ở mức vĩ mô? Hay cụ thể hơn, là 
liệu có bất kỳ sự phán đoán nào về sự thay đổi của độ thích nghi của các nhóm con 
trong quần thể theo thời gian? 
5. Có cách nào để mô tả các hiệu ứng khác nhau của các toán tử di truyền như lai 
ghép, đột biến, đảo ngược, v.v 
6. Trong những trường hợp nào (bài toán nào, toán tử di truyền nào) thì GA sẽ thực 
hiện tốt hơn các phương pháp nghiên cứu của TTNT truyền thống. 
Những câu hỏi này (và còn nhiều hơn nữa) vẫn đã và đang được các nhà khoa học như 
Holland, Mitchell, Golderg, nghiên cứu. 
109 
TỔNG KẾT PHẦN 3 
Nội dung chính của chương này bao gồm: 
 Giới thiệu tổng quát về một nhánh nghiên cứu mới của Trí Tuệ Nhân Tạo, đó là 
Học máy. Học được định nghĩa như là bất cứ sự thay đổi nào trong một hệ thống 
cho phép nó tiến hành tốt hơn trong lần thứ hai khi lặp lại cùng một nhiệm vụ hoặc 
với một nhiệm vụ khác rút ra từ cùng một quần thể các nhiệm vụ đó. 
 Có ba tiếp cận học: Tiếp cận thứ nhất là tiếp cận ký hiệu, hai là tiếp cận mạng 
neuron hay kết nối và tiếp cận thứ ba là tiếp cận nổi trội hay di truyền và tiến hóa. 
 Các chương trình học theo tiếp cận ký hiệu sẽ biểu diễn vấn đề dưới dạng các ký 
hiệu. Chương này trình bày một giải thuật được sử dụng rộng rãi của tiếp cận này, 
đó là ID3. ID3 sẽ học từ tập dữ liệu rèn luyện bao gồm rất nhiều ví dụ, mỗi ví dụ 
bao gồm một tập các cặp ‘thuộc tính – giá trị’. Thuộc tính và giá trị ở đây là các ký 
hiệu. Sau khi học xong, ID3 biểu diễn khái niệm học được bằng một cây quyết 
định. 
 Tiếp cận kết nối hay mạng neuron mô phỏng hệ thần kinh của con người để học 
được các khái niệm mà không sử dụng ký hiệu để biểu diễn vấn đề. Mạng đơn tầng 
perceptron cho thấy sức mạnh của mạng neuron, tuy nhiên khả năng áp dụng của 
chúng chỉ hạn chế cho các bài toán có tính tách rời tuyến tính. Mạng đa tầng áp 
dụng giải thuật học lan truyền ngược đã vượt qua những hạn chế của mạng 
perceptron, chứng tỏ được sức mạnh thực sự của tiếp cận này. 
 Tương tự như tiếp cận kết nối, tiếp cận di truyền và tiến hóa có cảm hứng bắt 
nguồn từ tri thức của con người về sự tiến hóa của sinh vật: chỉ có những cá thể có 
khả năng thích nghi với sự thay đổi của môi trường thì mới tồn tại và phát triển. 
Thuật toán di truyền mô phỏng theo nguyên lý đó. 
 Bài tập 
 1. Cho một tập hợp các ví dụ rèn luyện như sau: 
An muốn áp dụng giải thuật ID3 để xây dựng cây quyết định với tập dữ liệu rèn luyện 
trên. Áp dụng các công thức tính entropy và gain, hãy giúp An xác định thuộc tính nào 
(A
1
, A
2
, hay A
3
) là thuộc tính tốt nhất để hỏi đầu tiên nhằm tạo ra một cây quyết định 
đơn giản nhất. (Lưu ý: phải trình bày các tính toán entropy và gain để đi đến kết luận). 
110 
2. Cho một tập hợp gồm 10 ví dụ rèn luyện như sau: 
Tập dữ liệu trên thể hiện quyết định sẽ chờ bàn hay không của một người khi bước 
vào một nhà hàng đông khách không còn bàn trống. Quyết định của anh ta sẽ phụ 
thuộc vào một số yếu tố như hôm đó có phải là ngày cuối tuần không (cuối-tuần) – 
A1, anh ta có đang đói không (đang-đói) – A2, thời gian chờ bàn (TG-chờ) – A3: dưới 
10 phút (0-10), từ 10 đến 30 phút (10-30) hay trên 30 phút (>30). 
Áp dụng các công thức tính entropy và gain, để xác định thuộc tính tốt nhất để hỏi kế 
tiếp nhằm tạo ra một cây quyết định đơn giản nhất theo giải thuật ID3. Trình bày các 
tính toán entropy và gain ở mỗi bước. 
111 
Tài liệu tham khảo 
¾ Đinh Mạnh Tường. Trí tuệ nhân tạo. Nhà xuất bản Khoa học kỹ thuật, 
2002 
¾ Stuart Russell, Peter Norvig. Artificial Intelligence: A modern Approach, 
Prentice- Hall, 2002 
¾ Chin-Liang Chang, Richard Char-Tung Lee, Symbolic Logic and 
Mechanical Theorem Proving, Academic Press, Inc, 1973 
¾ Enn Tyugu. Algorithms and Architectures of Artificial Intelligence, IOS 
Press 2007 
¾ Nguyễn Thanh Thuỷ. Trí tuệ nhân tạo: Các phương pháp giải quyết vấn đề 
và xử lý tri thức. Nhà xuất bản Giáo dục, 1999