Chương 9: Học máy
Chương IX
HỌC MÁY (MACHINE LEARNING)

Nội dung chính: Trong chương này, chúng ta sẽ tìm hiểu về một nhánh nghiên cứu hiện đại
của Trí Tuệ Nhân Tạo, đó là học máy bao gồm giải thuật ID3, mạng neuron, và giải thuật di
truyền.
Mục tiêu cần đạt : Sau chương này, sinh viên có thể :
¾ Hiểu được mục tiêu của lĩnh vực ‘máy hoc’.
¾ Biết 3 tiếp cận học của lĩnh vực học máy.
¾ Vận dụng giải thuật ID3 vào các bài toán thực tế
¾ Hiểu khái niệm mạng neuron và các vấn đề có liên quan
¾ Hiểu giải thuật di truyền và ứng dụng của nó vào các bài toán thực tế.
Kiến thức tiên quyết: Biểu diễn tri thức ở dạng luật, tìm kiếm trong không gian trạng thái,
khái niệm Entropy trong Lý thuyết thông tin.
Tài liệu tham khảo :
[1] Geogre F. Luger – Artificial Intelligence, Structures and Strategies for Complex Problem
Solving– Addison – Wesley Publishing Company, Inc – 2002 (trang 349 – 381, 417 – 438,
469 – 480)
[2] Tom M. Mitchell – Machine Learning – McGraw Hill, Inc (trang 52 – 65)
[3] Wikipedia – Bách khoa toàn thư mở - Học máy:
/>[4] Ender ÖZCAN, Murat ERENTÜRK – A Brief Review Of Memetic Algorithms For
Solving TSP :

I GIỚI THIỆU:

đúng đắn những ví dụ chưa từng gặp trong lĩnh vực đó. Đây chính là bài toán quy nạp
(induction), và nó chính là trung tâm của việc học. Trong hầu hết các bài toán học, dữ liệu
luyện tập sẵn có thường không đủ để đảm bảo đưa ra được một khái quát hóa tối ưu, cho dù
CTH sử dụng giải thuật nào. Vì vậy, các giải thuật học phải khái quát hóa theo phương pháp
heuristic, nghĩa là chúng sẽ chọn một số khía cạnh nào đó mà theo kinh nghiệm là cho hiệu
quả trong tương lai để khái quát. Các tiêu chuẩn lựa chọn này gọi là thiên lệch quy nạp
(inductive bias).
Có nhiều nhiệm vụ học (learning task) khác nhau. Ở đây chỉ trình bày nhiệm vụ học quy nạp
(inductive learning), đây là một trong những nhiệm vụ học cơ bản. Nhiệm vụ của CTH là
học một khái quát (generalization) từ một tập hợp các ví dụ. Học khái niệm (concept
learning) là một bài toán học quy nạp tiêu biểu: cho trước một số ví dụ của khái niệm, chúng
ta phải suy ra một định nghĩa cho phép người dùng nhận biết một cách đúng đắn những thể
hiện của khái niệm đó trong tương lai.
154 Võ Huỳnh Trâm – Trần Ngân Bình
Chương 9: Học máy
I.2 Các tiếp cận học:
Có ba tiếp cận học: tiếp cận ký hiệu (symbol-based learning), tiếp cận mạng neuron hay kết
nối (neural or connectionist networks) và tiếp cận nổi trội (emergent) hay di truyền và tiến
hóa (genetic and evolutionary learning).
Các CTH thuộc tiếp cận dựa trên ký hiệu biểu diễn vấn đề dưới dạng các ký hiệu (symbol),
các giải thuật học sẽ tìm cách suy ra các khái quát mới, hợp lệ, hữu dụng và được biểu diễn
bằng các ký hiệu này. Có nhiều giải thuật được đưa ra theo tiếp cận học này, tuy nhiên phần
II của chương này chỉ trình bày một giải thuật được sử dụng rộng rãi trong số đó, đó là giải
thuật quy nạp cây quyết định ID3.
Ngược lại với tiếp cận ký hiệu, tiếp cận kết nối không học bằng cách tích lũy các câu trong
một ngôn ngữ ký hiệu. Giống như bộ não động vật chứa một số lượng lớn các tế bào thần
kinh liên hệ với nhau, mạng neuron là những hệ thống gồm các neuron nhân tạo liên hệ với
nhau. Tri thức của chương trình là ngầm định trong tổ chức và tương tác của các neuron này.
Phần III sẽ đi vào chi tiết của tiếp cận này.
Tiếp cận thứ ba là tiếp cận nổi trội mô phỏng cách thức các hệ sinh học tiến hóa trong tự

tính đích (target attribute).
Mỗi thuộc tính đều có một tập các giá trị hữu hạn. Thuộc tính quang cảnh có ba giá trị (âm u,
mưa, nắng), nhiệt độ có ba giá trị (nóng, mát, ấm áp), độ ẩm có hai giá trị (cao, TB) và gió
có hai giá trị (mạnh, nhẹ). Các giá trị này chính là ký hiệu (symbol) dùng để biểu diễn bài
toán.
Từ tập dữ liệu rèn luyện này, giải thuật ID3 sẽ học một cây quyết định có khả năng phân loại
đúng đắn các ví dụ trong tập này, đồng thời hy vọng trong tương lai, nó cũng sẽ phân loại
đúng các ví dụ không nằm trong tập này. Một cây quyết định ví dụ mà giải thuật ID3 có thể
quy nạp được là:

Hình 9.1 - Cây quyết định
cho khái niệm ‘Có đi chơi
tennis không?’

156 Võ Huỳnh Trâm – Trần Ngân Bình
Chương 9: Học máy
Các nút trong cây quyết định biểu diễn cho một sự kiểm tra trên một thuộc tính nào đó, mỗi
giá trị có thể có của thuộc tính đó tương ứng với một nhánh của cây. Các nút lá thể hiện sự
phân loại của các ví dụ thuộc nhánh đó, hay chính là giá trị của thuộc tính phân loại.
Sau khi giải thuật đã quy nạp được cây quyết định, thì cây này sẽ được sử dụng để phân loại
tất cả các ví dụ hay thể hiện (instance) trong tương lai. Và cây quyết định sẽ không thay đổi
cho đến khi ta cho thực hiện lại giải thuật ID3 trên một tập dữ liệu rèn luyện khác.
Ứng với một tập dữ liệu rèn luyện sẽ có nhiều cây quyết định có thể phân loại đúng tất cả
các ví dụ trong tập dữ liệu rèn luyện. Kích cỡ của các cây quyết định khác nhau tùy thuộc
vào thứ tự của các kiểm tra trên thuộc tính.
Vậy làm sao để học được cây quyết định có thể phân loại đúng tất cả các ví dụ trong tập rèn
luyện? Một cách tiếp cận đơn giản là học thuộc lòng tất cả các ví dụ bằng cách xây dựng một
cây mà có một lá cho mỗi ví dụ. Với cách tiếp cận này thì có thể cây quyết định sẽ không
phân loại đúng cho các ví dụ chưa gặp trong tương lai. Vì phương pháp này cũng giống như
hình thức ‘học vẹt’, mà cây không hề học được một khái quát nào của khái niệm cần học.

+ : D9, D11
–
:
D1, D2, D8
+ : D3, D7, D12, D13
–
:
+ : D3, D5, D10
–
:
D6, D14
Nắng
Âm u
Mưa
Hình 9.2 - Một phần cây quyết định xây dựng được
Bắt đầu với bảng đầy đủ gồm 14 ví dụ rèn luyện, ID3 chọn thuộc tính quang cảnh để làm
thuộc tính gốc sử dụng hàm chọn lựa thuộc tính mô tả trong phần kế tiếp. Trắc nghiệm này
phân chia tập ví dụ như cho thấy trong hình 9.2 với phần tử của mỗi phân vùng được liệt kê
bởi số thứ tự của chúng trong bảng.
* ID3 xây dựng cây quyết định theo giải thuật sau:
Function induce_tree(tập_ví_dụ, tập_thuộc_tính)
begin
if mọi ví dụ trong tập_ví_dụ đều nằm trong cùng một lớp then
return một nút lá được gán nhãn bởi lớp đó
else if tập_thuộc_tính là rỗng then
return nút lá được gán nhãn bởi tuyển của tất cả các lớp trong tập_ví_dụ
else begin
chọn một thuộc tính P, lấy nó làm gốc cho cây hiện tại;
xóa P ra khỏi tập_thuộc_tính;
với mỗi giá trị V của P

D14
Quang cảnh?
+ : D9, D11
– : D1
,
D2
,
D8
+ : D3, D7, D12, D13
–:
+ : D3, D5, D10
–: D6
,
D14
Nắng
Âm u
Mưa
Yes
Độ ẩm? Gió?
+ :
– : D1
,
D2
,
D8
+ : D9, D11
– :
+ :
–:D6
,

thực hiện điều này.
II.3 Thuộc tính nào là thuộc tính dùng để phân loại tốt nhất?
Quinlan (1983) là người đầu tiên đề xuất việc sử dụng lý thuyết thông tin để tạo ra các cây
quyết định và công trình của ông là cơ sở cho phần trình bày ở đây. Lý thuyết thông tin của
Shannon (1948) cung cấp khái niệm entropy để đo tính thuần nhất (hay ngược lại là độ pha
trộn) của một tập hợp. Một tập hợp là thuần nhất nếu như tất cả các phần tử của tập hợp đều
thuộc cùng một loại, và khi đó ta nói tập hợp này có độ pha trộn là thấp nhất. Trong trường
hợp của tập ví dụ, thì tập ví dụ là thuần nhất nếu như tất cả các ví dụ đều có cùng giá trị phân
loại.
Khi tập ví dụ là thuần nhất thì có thể nói: ta biết chắc chắn về giá trị phân loại của một ví dụ
thuộc tập này, hay ta có lượng thông tin về tập đó là cao nhất. Khi tập ví dụ có độ pha trộn
cao nhất, nghĩa là số lượng các ví dụ có cùng giá trị phân loại cho mỗi loại là tương đương
nhau, thì khi đó ta không thể đoán chính xác được một ví dụ có thể có giá trị phân loại gì,
hay nói khác hơn, lượng thông tin ta có được về tập này là ít nhất. Vậy, điều ta mong muốn ở
đây là làm sao chọn thuộc tính để hỏi sao cho có thể chia tập ví dụ ban đầu thành các tập ví
dụ thuần nhất càng nhanh càng tốt. Vậy trước hết, ta cần có một phép đo để đo độ thuần nhất
của một tập hợp, từ đó mới có thể so sánh tập ví dụ nào thì tốt hơn. Phần kế tiếp sẽ trình bày
công thức tính entropy của một tập hợp. 160 Võ Huỳnh Trâm – Trần Ngân Bình
Chương 9: Học máy
II.3.1 Entropy đo tính thuần nhất của tập ví dụ
Khái niệm entropy của một tập S được định nghĩa trong Lý thuyết thông tin là số lượng
mong đợi các bít cần thiết để mã hóa thông tin về lớp của một thành viên rút ra một cách
ngẫu nhiên từ tập S. Trong trường hợp tối ưu, mã có độ dài ngắn nhất. Theo lý thuyết thông
tin, mã có độ dài tối ưu là mã gán –log
2
p bits cho thông điệp có xác suất là p.
Trong trường hợp S là tập ví dụ, thì thành viên của S là một ví dụ, mỗi ví dụ thuộc một lớp

∑
=
−=
c
i
ii
ppSEntropy
1
2
log)(

II.3.2 Lượng thông tin thu được đo mức độ giảm entropy mong đợi
Entropy là một số đo đo độ pha trộn của một tập ví dụ, bây giờ chúng ta sẽ định nghĩa một
phép đo hiệu suất phân loại các ví dụ của một thuộc tính. Phép đo này gọi là lượng thông tin
Võ Huỳnh Trâm – Trần Ngân Bình 161
Giáo Trình Trí Tuệ Nhân Tạo
thu được, nó đơn giản là lượng giảm entropy mong đợi gây ra bởi việc phân chia các ví dụ
theo thuộc tính này.
Một cách chính xác hơn, Gain(S,A) của thuộc tính A, trên tập S, được định nghĩa như sau:
∑
−= )(
||
||
)(),(
v
v
SEntropy
S
S
SEntropyASGain

• Trong khi tìm kiếm, ID3 chỉ duy trì
một giả thuyết hiện tại. Vì vậy, giải
thuật này không có khả năng biểu
diễn được tất cả các cây quyết định
khác nhau có khả năng phân loại
đúng dữ liệu hiện có.
Hình 9.5 - Không gian tìm kiếm của ID3.
• Giải thuật thuần ID3 không có khả
năng quay lui trong khi tìm kiếm. Vì vậy, nó có thể gặp phải những hạn chế giống như
giải thuật leo núi, đó là hội tụ về cực tiểu địa phương.
162 Võ Huỳnh Trâm – Trần Ngân Bình
Chương 9: Học máy
• Vì ID3 sử dụng tất cả các ví dụ ở mỗi bước để đưa ra các quyết định dựa trên thống kê,
nên kết quả tìm kiếm của ID3 rất ít bị ảnh hưởng bởi một vài dữ liệu sai (hay dữ liệu
nhiễu).
• Trong quá trình tìm kiếm, giải thuật ID3 có xu hướng chọn cây quyết định ngắn hơn là
những cây quyết định dài. Đây là tính chất thiên lệch quy nạp của ID3.
II.5 Đánh giá hiệu suất của cây quyết định:
Một cây quyết định sinh ra bởi ID3 được đánh giá là tốt nếu như cây này có khả năng phân
loại đúng được các trường hợp hay ví dụ sẽ gặp trong tương lai, hay cụ thể hơn là có khả
năng phân loại đúng các ví dụ không nằm trong tập dữ liệu rèn luyện.
Để đánh giá hiệu suất của một cây quyết định người ta thường sử dụng một tập ví dụ tách
rời, tập này khác với tập dữ liệu rèn luyện, để đánh giá khả năng phân loại của cây trên các
ví dụ của tập này. Tập dữ liệu này gọi là tập kiểm tra (validation set). Thông thường, tập dữ
liệu sẵn có sẽ được chia thành hai tập: tập rèn luyện thường chiếm 2/3 số ví dụ và tập kiểm
tra chiếm 1/3.
II.6 Chuyển cây về các luật
Thông thường, cây quyết định sẽ được chuyển về dạng các luật để thuận tiện cho việc cài đặt
và sử dụng. Ví dụ cây quyết định cho tập dữ liệu rèn luyện trong bảng 9.1 có thể được
chuyển thành một số luật như sau :

quyết định khác nhau trên cùng tập dữ liệu rèn luyện đã cho như kỹ thuật bagging and
boosting.
III TIẾP CẬN KẾT NỐI: MẠNG NEURON
III.1 Giới thiệu
Các mô hình học theo tiếp cận này bắt chước theo cách học của các hệ thần kinh sinh vật.
Các hệ thống theo mô hình này có khi còn được gọi là các hệ kết nối (connectionist
systems), tính toán neural (Neural computing), mạng neural (Neural Networks), các hệ xử lý
phân tán song song (parallel distributed processing – PDP).
Không giống như các giải thuật của tiếp cận ký hiệu, các mô hình này không sử dụng ký
hiệu một cách tường minh để giải quyết vấn đề. Thay vào đó, chúng giữ cho trí tuệ phát triển
trong các hệ thống gồm các thành phần (neuron sinh học hay neuron nhân tạo) đơn giản,
tương tác thông qua một quá trình học hay thích nghi mà nhờ đó kết nối giữa các thành phần
này được điều chỉnh. Việc xử lý của các hệ thống này được phân tán trên một tập hợp các
lớp neuron. Các hệ thống này giải quyết vấn đề song song theo nghĩa rằng tất cả các neuron
trong tập hợp hay trong các lớp sẽ xử lý tín hiệu vào một cách đồng thời và độc lập.
Trong khi các giải thuật của tiếp cận ký hiệu sử dụng ký hiệu để mô tả các mẫu của bài toán
như ta đã thấy trong giải thuật ID3 thì những nhà thiết kế mạng neuron phải tạo ra một sơ đồ
164 Võ Huỳnh Trâm – Trần Ngân Bình
Chương 9: Học máy
mã hóa các mẫu (pattern) của bài toán thành các đại lượng số để đưa vào mạng. Việc chọn
lựa một sơ đồ mã hóa thích hợp đóng vai trò quyết định cho sự thành công hay thất bại trong
việc học của mạng.
Các mẫu (pattern) của bài toán được mã hóa thành các vector số. Các kết nối giữa các thành
phần, hay neuron, cũng được biểu diễn bằng các giá trị số. Cuối cùng, sự biến đổi của các
mẫu cũng là kết quả của các phép toán số học, thông thường là phép nhân ma trận. Sự chọn
lựa kiến trúc kết nối của nhà thiết kế mạng neuron góp phần vào tính thiên lệch quy nạp
(inductive bias) của hệ thống.
Các giải thuật và kiến trúc dùng để cài đặt mạng neuron thường được huấn luyện (trained)
hay tạo điều kiện (conditioned) chứ không được lập trình một cách tường tận. Và đây chính
là sức mạnh chủ yếu của tiếp cận này.

. Các trọng số này dùng để mô tả sức
mạnh kết nối, hay sức mạnh của các kết nối thiên lệch (bias link)
¾ Một mức kích hoạt (activation level) hay hàm kích hoạt Σw
i
x
i
. Mức kích hoạt của một
neuron được xác định bởi sức mạnh tích lũy từ các tín hiệu đầu vào của nó nơi mà mỗi
tín hiệu đầu vào được tỷ lệ lại bằng trọng số kết nối wi ở đầu vào đó. Vì vậy, mức kích
họat được tính toán bằng cách lấy tổng các giá trị đầu vào sau khi được tỉ lệ hóa, Σw
i
x
i
.
¾ Một hàm ngưỡng (threshold function), f. Hàm này tính kết quả đầu ra của neuron bằng
cách xác định xem mức kích hoạt nằm dưới hay trên một giá trị ngưỡng là ít hay nhiều.
Hàm ngưỡng này có khuynh hướng tạo ra trạng thái tắt/mở của các neuron.
III.2.2 Các đặc trưng của một mạng Neuron
Ngoài các tính chất của một neuron đơn lẻ, một mạng neuron còn được đặc trưng bởi các
tính chất toàn cục như sau:
¾ Hình thái mạng (network topology): là mô hình hay mẫu kết nối giữa các neuron đơn lẻ. Hình 9.7 - Các hình thái mạng neuron khác nhau.

đầu vào với giá trị trọng số tương ứng và cộng chúng lại; nếu tổng lớn hơn hay bằng không,
thì neuron trả về 1, ngược lại, là –1.
McCulloch-Pitts cho thấy các neuron này có thể được xây dựng để tính toán bất cứ hàm
logic nào, chứng minh rằng các hệ thống gồm các neuron này cung cấp một mô hình tính
toán đầy đủ.
Hình 9.8 minh họa các neuron McCulloch-Pitts dùng để tính hàm logic and và or.
I
1
I
2
H
1
O
1
w
11

w
12

166 Võ Huỳnh Trâm – Trần Ngân Bình
Chương 9: Học máy

Hình 9.8 - Các neuron McCulloch-Pitts dùng để tính toán các hàm logic and và or.
Các neuron này có 3 đầu vào: x và y là các giá trị cần đưa vào, còn đầu vào thứ ba, đôi khi
còn được gọi là một thiên lệch (bias), có giá trị hằng là +1.
Ba đầu vào của neuron and có 3 trọng số tương ứng là +1, +1 và –2. Vì vậy, với các giá trị
bất kỳ của x, y, neuron tính giá trị x+y-2; nếu giá trị này nhỏ hơn 0, nó trả về –1. Ngược lại
trả về 1.
Bảng bên dưới minh họa cho tính toán neuron x and y.

>= t
-1 nếu ∑w
i
x
i
< t

Perceptron sử dụng một hình thức đơn giản của học có giám sát (supervised learning). Sau
khi perceptron cố gắng giải quyết một mẫu bài toán (mẫu này rút ra từ tập dữ liệu rèn luyện
Võ Huỳnh Trâm – Trần Ngân Bình 167
Giáo Trình Trí Tuệ Nhân Tạo
– training data), chương trình đóng vai trò như một người thầy giáo sẽ cung cấp cho nó kết
quả đúng của mẫu bài toán đó (giá trị này cũng lấy từ tập dữ liệu rèn luyện). Dựa vào sự
khác biệt giữa kết quả đúng được cung cấp và kết quả mà perceptron tính toán được, nó sẽ tự
điều chỉnh các trọng số của nó để làm thu hẹp khoảng cách lỗi. Perceptron sử dụng luật như
sau: với c là một hằng số cho trước, hằng số này thể hiện tốc độ học và d là giá trị đầu ra
mong muốn, perceptron sẽ điều chỉnh trọng số trên thành phần thứ i của vectơ đầu vào một
lượng ∆w
i
:
w
i
= c(d – f(∑w
i
x
i
)) x
i
∆
f(∑w
Hình 9.9 - Một hệ
thống phân loại đầy đủ.
Hình trên đưa ra một cái nhìn khái quát về bài toán phân loại. Dữ liệu thô từ một không gian
các điểm có thể có sau khi qua bộ chuyển đổi (transducer) sẽ được chọn và chuyển đổi thành
một không gian các dữ liệu hay mẫu mới. Trong không gian mẫu mới này, bộ trích lọc đặc
trưng (feature extractor) sẽ chọn ra các đặc trưng của dữ liệu, và cuối cùng, dữ liệu thể hiện
168 Võ Huỳnh Trâm – Trần Ngân Bình
Chương 9: Học máy
qua các đặc trưng sẽ được đưa vào máy phân loại (classifier) để cho ra kết quả lớp phân loại
(class) của dữ liệu đó.
Trong dây chuyền này, mạng perceptron nói riêng và mạng neuron nói chung đóng vai trò
như một máy phân loại.
Một dữ liệu đầu vào sẽ được biểu diễn như một vectơ gồm n thành phần (thể hiện cho n đặc
trưng) x
1
, x
2
, …, x
n

1
và x
2
, cùng với một
đầu vào thiên lệch (bias)
luôn có giá trị 1.

Hình 9.11- Mạng perceptron cho ví dụ của bảng 9.3.
Mức kích hoạt:
net = w
1
x
1
+ w
2
x
2

+ w
3
Hàm ngưỡng f(net) là một hàm dấu, hay còn gọi là hàm ngưỡng hai cực tuyến tính
Võ Huỳnh Trâm – Trần Ngân Bình 169
Giáo Trình Trí Tuệ Nhân Tạo

f(net) = +1, nếu net>0
f(net) = -1, nếu net<=0 Tín hiệu thiên lệch phục vụ cho việc chuyển dịch hàm ngưỡng trên trục tung. Phạm vi của
chuyển dịch này sẽ được học bằng cách điều chỉnh trọng số w

f(net)
2
= f(0.75 * 9.4 + 0.5 * 6.4 – 0.6 *1 ) = f(9.65) = 1
Nhưng giá trị mong đợi ở đây là -1, vì vậy, ta cần điều chỉnh trọng số theo luật học:
t
= W
t-1
+ c( d
t-1
– f(net)
t-1
)X
t-1
W
trong đó: c là hằng số học

W, X: là vectơ trọng số, và vectơ dữ liệu đầu
vào
t là thời điểm
Trong trường hợp này: c = 0.2, d
2
= -1, và f(net)
2
= 1
Áp dụng luật học trên, ta có:

3
= W
2
+ 0.2(–1 – 1)X

⎦
⎤
⎢
⎢
⎢
⎣
⎡
− 00.1
06.2
01.3
0.1
4.6
4.9
4.0
6.0
5.0
75.0
W
Bây giờ chúng ta xét ví dụ thứ 3:
f(net)
3
= f(-3.01 * 2.5 -2.06 * 2.1 – 1.0 *1 ) = f(-12.84) = -1
170 Võ Huỳnh Trâm – Trần Ngân Bình
Chương 9: Học máy
Trong khi giá trị mong đợi của ví dụ này là 1, nên các trọng số tiếp tục được điều chỉnh

4
= W
3
+ 0.2(1–(– 1))X

⎦
⎤
⎢
⎢
⎢
⎣
⎡
−
−
−
60.0
22.1
01.2
0.1
1.2
5.2
4.0
0.1
06.2
01.3
W
Cứ tiếp tục như thế, sau 10 lần lặp, đường phân cách tuyến tính như trong hình 9.10 xuất
hiện. Sau khi lặp lại việc huấn luyện perceptron trên tập dữ liệu đã cho, khoảng 500 lần lặp
tổng cộng, vectơ trọng số hội tụ về giá trị [-1.3, -1.1, 10.9]. Và đây chính là các hệ số của
phương trình đường phân cách tuyến tính trong hình 9.10:
-1.3 * x
1
– 1.1 * x
2
+ 10.9 = 0.

, tạo thành các
điểm dữ liệu trong hình 9.12. Bài toán học một phân loại nhị phân của các dữ liệu rèn luyện
rút lại thành bài toán tách các điểm này thành hai nhóm. Như vậy, đối với một không gian n
chiều, một sự phân loại là phân tách được một cách tuyến tính nếu như các lớp của nó có thể
được tách ra bởi một mặt phẳng n-1 chiều. (Trong không gian hai chiều thì mặt siêu phẳng n-
1 chiều là một đường thẳng, trong không gian 3 chiều thì nó là một mặt phẳng, …).
Võ Huỳnh Trâm – Trần Ngân Bình 171
Giáo Trình Trí Tuệ Nhân Tạo
III.3.4 Luật Delta
Một cách dễ dàng để tổng quát hóa mạng perceptron là thay hàm ngưỡng giới hạn cứng bằng
một hàm kích hoạt kiểu khác. Chẳng hạn như, hàm kích hoạt liên tục (để có khả năng lấy vi
phân) tạo điều kiện cho các giải thuật học phức tạp hơn.

Hình 9.13 - Các hàm ngưỡng.
Hình 9.13 minh họa đồ thị của một số hàm ngưỡng: hình 9.13a là một hàm ngưỡng hai cực,
hình 9.13b minh họa một hàm kích hoạt sigmoidal thông dụng (hàm sigmoidal là hàm có
hình cong như chữ S), được gọi là hàm logistic, hàm này có công thức như sau:
f(net) = 1/(1 + e
-λ*net
) với net = ∑
i
w
i
x
i

Cũng như các hàm định nghĩa trước đây, x
i
là đầu vào của đường thứ i, w
i

Chương 9: Học máy
trong đó, c là hằng số điều khiển tốc độ học, d
i
và O
i
là các giá trị đầu ra thực sự và mong
muốn của nút thứ i. f’(net
i
) là đạo hàm của hàm kích hoạt cho nút thứ i, và x
j
là đầu vào thứ j
của nút thứ i. Thay thế công thức đạo hàm (1-1) của hàm logistic f’(net), ta được công thức
để điều chỉnh trọng số như sau:
∆w = c(d
i
– O
i
) O
i
( 1 – O
i
) x
j
(1-2)
Từ công thức này cho thấy, công thức điều chỉnh trọng số này chỉ có thể áp dụng cho các nút
của mạng perceptron đơn tầng, vì tại đó ta mới có các giá trị đầu ra mong muốn d
i
.
III.4 Học Lan truyền ngược:
Như đã phân tích ở trên, ta thấy các mạng perceptron đơn tầng có khả năng giới hạn, chúng

i
– O
i
) O
i
(1 – O
i
) x
k
cho nút ở tầng ra
∆w
k
= c ∑
j
(delta
j
w
ij
) O
i
(1 – O
i
) x
k
cho nút ở tầng ẩn
với delta
j
= (d
j
– O

Kết quả của NETtalk là có thể phát âm đúng 60% sau khi rèn luyện với một tập dữ liệu rèn
luyện gồm 500 ví dụ và lặp lại 100 lượt.
Ngoà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.
III.4.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 9.16 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 9.16 không phải là một mạng duy nhất có thể giải quyết bài
toán này.

Hình 9.16 - Một mạng lan truyền ngược dùng để giải quyết bài toán
exclusive-or.
Võ Huỳnh Trâm – Trần Ngân Bình 175
Giáo Trình Trí Tuệ Nhân Tạo
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
176 Võ Huỳnh Trâm – Trần Ngân Bình
Chương 9: Học máy
IV TIẾP CẬN XÃ HỘI VÀ NỔI TRỘI: GIẢI THUẬT DI
TRUYỀN (GENETIC ALGORITHM - GA)
IV.1 Giới thiệu
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.
IV.2 Giải thuật

Khởi tạo quần thể
Thỏa ĐK dừng
•Gọi hàm thích nghi để đánh giá các lời giải
ứng viên
•Chọn các ứng viên tốt
•Tạo con mới
•Thay thế ứng viên kém bằng các con mới
Chọn lời giải tốt nhất từ quần thể
N
Y
Hình 9.17- Giải thuật di truyền.
Hình 9.17 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,