Bài giảng Trí tuệ nhân tạo - Chương 6: Học má - Lê Thanh Hương

1Chương 6. Học máy
Lê Thanh Hương
Bộ ô HTTT Kh CNTT
1
 m n , oa 
Đại học Bách khoa Hà Nội
6.1. Học
“Học đề cập đến các thay đổi của hệ thống theo 
hướng thích nghi: chúng cho phép hệ thống 
thực hiện các công việc trong cùng một môi 
trường hiệu quả hơn từ lần thực hiện thứ 2”
2
Các phương pháp học
• Học có giám sát: biết trước câu trả lời đúng
• Học không giám sát: không biết trước câu 
trả lời đúng
• Học tăng cường: đôi khi có thưởng/phạt cho 
các hành động
3
Những gì cần học?
• Mẹo trong tìm kiếm 
• Hàm đánh giá trò chơi
• Tri thức khai báo (các mệnh đề logic)
• Các bộ phân loại 
Cấu trúc phân loại
4
– 
– Ngữ pháp
2Học có giám sát: qui nạp
• Trường hợp tổng quát: 
– Cho tập các cặp (x, f(x)), tìm hàm f. 
• Phân loại: 
– Cho tập các cặp (x, y) với y là 1 nhãn, tìm hàm 
cho phép gán x với giá trị đúng của nó.
• Phân loại đơn giản:
5
– Cho tập các cặp (x, y) với x là 1 đối tượng và y = 
+ nếu x thuộc đúng lớp và - nếu ngược lại. Tìm 
hàm cho phép gán nhãn chính xác.
Coi học như việc tìm kiếm
• Đoán hàm phù hợp với các đầu vào = xác 
định 1 giả thiết.
• Không gian giả thiết = tập tất cả các giả thiết 
có thể.
• Học là việc tìm kiếm 1 giả thiết phù hợp trong 
không gian giả thiết
6
Các phương pháp phân loại
• Học qui nạp 
• Láng giềng gần
• Xác suất
• Cây quyết định
• Mạng nơron
7
• Giải thuật di truyền
• 
6.2. Học cây quyết định
Bài toán: quyết định có đợi 1 bàn ở quán ăn không, dựa trên các 
thông tin sau:
1 Lựa chọn khác: có quán ăn nào khác gần đó không?. 
2. Quán rượu: có khu vực phục vụ đồ uống gần đó không?
3. Fri/Sat: hôm nay là thứ sáu hay thứ bảy?
4. Đói: chúng ta đã đói chưa? 
5. Khách hàng: số khách trong quán (không có, vài người, 
đầy) 
6. Giá cả: khoảng giá ($,$$,$$$)
8
7. Mưa: ngoài trời có mưa không?
8. Đặt chỗ: chúng ta đã đặt trước chưa?
9. Loại: loại quán ăn (Pháp, Ý, Thái, quán ăn nhanh)
10. Thời gian đợi: 0-10, 10-30, 30-60, >60
3Phép biểu diễn dựa trên thuộc tính
• Các mẫu được miêu tả dưới dạng các giá trị thuộc tính 
(logic, rời rạc, liên tục)
• Ví dụ, tình huống khi đợi 1 bàn ăn
9
• Các loại (lớp) của mẫu là khẳng định (T) hoặc phủ định (F)
10
Patrons, WaitEstimates, Alternative, Hungry, Rain
Cây quyết định
 là cách biểu diễn các giả thiết. 
11
Không gian giả thiết
Khi ó th ộ tí h B l ố l á â ết đị h là? c n u c n oo ean, s ượng c c c y quy n 
= số các hàm Boolean
= số các giá trị khác nhau trong bảng ví dụ mẫu với 2n hàng
= 22n
Ví dụ, với 6 thuộc tính Boolean, có 
18,446,744,073,709,551,616 cây
12
4Thuật toán ID3
Mục đích: tìm cây thoả mãn tập mẫu
Ý tưởng: (lặp) chọn thuộc tính quan trọng nhất làm gốc của 
cây/cây con
ID3(Examples, Target_attribute, Attributes)
/* Examples: các mẫu luyện
Target_attribute: thuộc tính cần đoán giá trị
Attributes: các thuộc tính có thể được kiểm tra qua phép học 
cây quyết định. */
• Tạo 1 nút gốc Root cho cây
13
• If ∀ Examples +, trả về cây chỉ có 1 nút Root, với nhãn +
• If ∀ Examples -, trả về cây chỉ có 1 nút Root, với nhãn –
• If Attributes rỗng, trả về cây chỉ có 1 nút Root, với nhãn = giá trị 
thường xuất hiện nhất của Target_attribute trong Examples
Thuật toán ID3
• Otherwise Begin:
– A ← thuộc tính trong Attributes cho phép phân loại tốt nhất
Examples
– Thuộc tính quyết định của nút gốc← A 
– Với các giá trị vi có thể có của A,
• Thêm 1 nhánh mới dưới gốc, ứng với phép kiểm tra A = vi
• Đặt Examplesvi = tập con của Examples với giá trị thuộc 
tính A = vi
• If Examplesvi rỗng
– Then, dưới nhánh mới này, thêm 1 lá với nhãn = giá trị 
ấ ấ ủ
14
thường xu t hiện nh t c a Target_attribute trong 
Examples
– Else, dưới nhánh mới này thêm cây con 
ID3(Examplesvi, Target_attribute, Attributes - {A}))
• End
• Return Root
Thuộc tính nào tốt nhất?
15
Sử dụng lượng thông tin đạt được Information Gain
Ö xác định thông qua độ đo Entropy
Entropy của một tập mẫu 
•S là một tập mẫu của tập luyện
•p+ là tỷ lệ các mẫu dương trong S 
•p- là tỷ lệ các mẫu âm trong S
16
•Entropy đo độ nhiễu của S = số các bit cần thiết để 
mã hoá lớp + hoặc - của các thành viên ngẫu nhiên 
của S 
•Entropy(S) = - p+*log2p+ - p-*log2p-
5Entropy
Entropy H(X) của biến ngẫu nhiên X:
Ví dụ, với S gồm 9 mẫu dương và 5 mẫu âm, kí hiệu 
S([9+,5-]). 
Entropy([9+ 5-])
17
,
= - (9/14)log2(9/14) – (5/14)log2(5/14)
= 0.940
Information Gain
Gain(S, A) = độ giảmentropy do việc phân loại trong A
Sv
Gain(S,A) = Entropy(S) – )(
)(
SvEntropy
SAValuesv
∑
∈
18
Ví dụ: tập luyện
Day Outlook Temperature Humidity Wind PlayTennis
D1 Sunny Hot High Weak No
D2 Sunny Hot High Strong No S = [9+,5-]
D3 Overcast Hot High Weak Yes 
D4 Rain Mild High Weak Yes 
D5 Rain Cool Normal Weak Yes 
D6 Rain Cool Normal Strong No 
D7 Overcast Cool Normal Strong Yes 
D8 Sunny Mild High Weak No 
D9 S C l N l W k Y
Humidity 
={High,Normal}: 
Shigh=[3+,4-]; 
Snormal=[6+,1-]
Wind ={Weak,Strong}: 
Sweak = [6+,2-]; 
19
unny oo orma ea es 
D10 Rain Mild Normal Weak Yes 
D11 Sunny Mild Normal Strong Yes 
D12 Overcast Mild High Strong Yes 
D13 Overcast Hot Normal Weak Yes 
D14 Rain Mild High Strong No 
Sstrong = [3+,3-]
Thuộc tính nào phân loại tốt nhất?
Humidity
High Normal
Wind 
Weak Strong
S:[9+,5-]
E=0.940
S:[9+,5-]
E=0.940
[3+,4-]
E=0.985
[6+,1-]
E=0.592
[6+,2-]
E=0.811
[3+,3-]
E=1.000
Gain(S,Wind) = Entropy(S) –
= Entropy(S) – (8/14)Entropy(SWeak) – (6/14)Entropy(SStrong)
)(
)(
SvEntropy
S
Sv
AValuesv
∑
∈
20
= 0.940 – (8/14)*0.811 – (6/14)*1.00 = 0.048
Gain(S,Humidity) = 0.940 – (7/14)*0.985 – (7/14)*0.592 = 0.151
Gain(S,Outlook)=0.246; Gain(S,Humidity)=0.151
Gain(S,Wind)=0.048; Gain(S,Temperature)=0.029
6SSunny = {D1,D2,D8,D9,D11}
Gain(SSunny, Humidity ) 
= .970 – (3/5)*0.0 – (2/5)*0.0 = .970
Thuộc tính nào tiếp?
G i (S T t )
21
a n Sunny, empera ure 
= .970 –(2/5)*0.0– (2/5)*1.0– (1/5)*0.0=.570
Gain(SSunny, Wind ) 
= 0.970 – (2/5)*1.0 – (3/5)*0.918 = 0.019
Cây quyết định sử dụng khi nào?
Các bài toán với các đặc tính sau thích hợp với học 
cây quyết định:
ẫ ả ở• Các m u mô t được b i các cặp thuộc tính-giá trị
• Hàm đích có giá trị rời rạc
• Cần có các giả thiết rời rạc 
• Các dữ liệu luyện có thể có nhiễu
• Dữ liệu luyện có thể thiếu giá trị thuộc tính
22
Ví dụ:
• Chẩn đoán y tế
• Phân tích các nguy cơ về tín dụng
• Mô hình hoá việc lập lịch
Đo độ chính xác
• Làm sao để biết h ≈ f ? 
• Sử dụng lý thuyết tính toán
1. Thử giả thiết h trên 1 tập các ví dụ mới (tập thử) (sử dụng 
ốcùng 1 mức độ phân b các mẫu như tập luyện)
Learning curve = % chính xác trên tập thử, sử dụng hàm xây dựng 
trên tập luyện
23
6.3. Học dựa trên mẫu
Ý tưởng: lưu tất cả các mẫu luyện 
Láng giềng gần nhất:
• Cho mẫu hỏi x trước tiên định vị mẫu luyện gần q, 
nhất xn, sau đó đánh giá
K láng giềng gần nhất:
• Cho xq, quyết định dựa trên k láng giềng gần nhất 
(nếu hàm đích có giá trị rời rạc)
• Lấy trung bình giá trị f của k láng giềng gần nhất
)f(x)(xfˆ nq ←
24
(nếu là giá trị thực) 
k
∑
=←
k
1i
i
q
)f(x
)(xfˆ
7Phương pháp láng giềng gần
• Tổ chức dữ liệu dưới dạng bảng . 
• Xây dựng ma trận cho phép tính 
khoảng cách giữa các cặp đối tượng. 
• Khi có 1 đối tượng mới chưa có kết 
luận, lấy kết luận của láng giềng gần 
25
nhất gán cho nó. 
Ví d
kNN
a2 ụ:
K = 4 mẫu mới
S1
S2 S3
S6
S7
Sx
26
S4 S5 S8 a1(0,0)
a1 a2 T
S1 -2 0 B
S2 -1 5 2 B.
S3 0.4 1.8 R
S4 1.5 -1 R
S5 3 -0.2 B
S6 3.2 1.5 R
27
S7 4.5 2 B
S8 4.7 -0.2 B
Sx 2 0.5 X
kNN
• Để định nghĩa độ tương tự giữa 2 TH, ta dùng 
ma trận. 
• Giả sử các mẫu là các điểm trong không gian n 
chiều Rn và dùng khoảng cách Euclidean 
• Cho Xi và Xj là 2 ví dụ. Khoảng cách của chúng 
là [ ]∑ −= jkikji xxXXd 22 ),(
28
trong đó xik là giá trị của thuộc tính k trên ví dụ 
Xi. 
k
8Thuật toán kNN cho các giá trị rời rạc
Thuật toán (tham số k)
1. Với mỗi mẫu luyện (X, f(X)), bổ sung mẫu vào 
tập luyện
2. Khi có mẫu mới Xq, gán lớp:
f(Xq) = lớp của đa số các thành viên trong k 
láng giềng gần nhất của Xq
29
với δ(a,b) = 1 nếu a = b và 0 nếu ngược lại
∑
=∈
=
k
1iVv
f(Xi)) (v, argmax (Xq)fˆ δ
kNN cho các hàm giá trị thực
Thuật toán (tham số k) 
1. Với mỗi mẫu luyện (X, f(X)), bổ sung mẫu vào tập 
luyện
2. Khi có mẫu mới Xq, gán lớp:
f(Xq) = giá trị trung bình của k láng giềng gần 
ấ
30
nh t của Xq
∑= kXfXf iq )()(ˆ
Đánh trọng số khoảng cách kNN 
Có thể muốn các láng giềng gần nhất có trọng số cao
∑k xf )(ˆ ωk
trong đó
à d( ) là kh ả á h iữ à
∑=
=← k
i i
i ii
qxf
1
1)( ω
2),(
1
iq
i xxd
=ϖ
∑
=∈
=
1i
i
Vv
q ))f(X (v, argmax )(Xfˆ δϖ i
31
v xq, xi o ng c c g a xq v xi
Chú ý: từ đây có thể thấy lý do dùng tất cả các mẫu luyện 
thay vì chỉ có k
→ phương pháp Shepard
Khi nào nên dùng láng giềng gần
• Các mẫu tương ứng với các điểm trong Rn
• Mỗi mẫu có dưới 20 thuộc tính
Nhiề ẫ l ệ• u m u uy n
Ưu điểm:
• Luyện rất nhanh
• Học các hàm đích phức tạp
• Không mất thông tin
32
Nhược điểm:
• Chậm khi truy vấn
• Dễ bị ảnh hưởng bởi các thuộc tính không liên quan
9Ảnh hưởng của số chiều
Giả thiết các mẫu được mô tả bởi 20 thuộc tính, 
nhưng chỉ có 2 thuộc tính liên quan đến hàm đích 
Ảnh hưởng của số chiều: phương pháp kNN thường 
bị mất phương hướng khi X nhiều chiều
Một số giải pháp:
• Giãn chiều thứ j bởi trọng số zj, trong đó z1,,zn
33
được chọn để tối thiểu hoá lỗi dự tính
• Sử dụng cross-validation để tự động chọn các trọng 
số z1,,zn
6.4. Mạng nơron nhân tạo
nghiên cứu và mô phỏng các tiến trình xử lý song song 
và phân tán khổng lồ diễn ra trong bộ não con người
34
Các vấn đề:
• Tốc độ bộ não nhận dạng hình ảnh
• Rất nhiều nơron trong một bộ não
• Tốc độ một nơron truyền dữ liệu
Ví dụ
Lái xe
Luyện bộ phận điền khiển xe lái xe chính xác 
trên nhiều địa hình khác nhau
máy tính
(thuật toán học)
35
lớp 1
sang trái
lớp 2
đi thẳng
lớp 3
sang phải
Biểu diễn mạng nơron
Trái Giữa Phải
Tầng ra
Tầng ẩn
Tầng vào
36
10
Định nghĩa
• Là một hệ thống gồm rất nhiều phần tử xử 
lý đ iả h t độ ơn g n oạ ng song song. 
• Tính năng: phụ thuộc vào 
– cấu trúc hệ thống
– mức độ liên kết giữa các phần tử 
á t ì h ử lý bê t á hầ tử
37
– qu r n x n rong c c p n 
• Có thể học từ số liệu và tổng quát hoá từ 
các số liệu đó. 
Khi nào sử dụng mạng nơron? 
Mạng nơron thích hợp với những bài toán có đặc 
điểm sau: 
• Các mẫu luyện được thể hiện bởi nhiều cặp giá trị-thuộc 
tính (ví dụ, điểm ảnh)
• Các mẫu luyện có thể có lỗi
• Chấp nhận thời gian huấn luyện dài 
• Cần đánh giá nhanh hàm mục tiêu được học
38
• Không cần hiểu giả thiết cuối cùng vì NN được coi là 
hộp đen
Perceptron
o(x1,...,xn) = 1 nếu w0 + w1x1 + w2x2 ++wnxn >0
-1 trong trường hợp ngược lại 
hay:
o( ) = sgn( )x
r xw rr .
39
trong đó
sgn(y) = 1 nếu y >0
-1 nếu ngược lại
Nhiệm vụ học: tìm các giá trị của w
Không gian giả thiết: không gian các vectơ trọng số
Khả năng của Perceptron
Mỗi perceptron tạo ra 1 mặt phân cách siêu phẳng trên 
không gian đầu vào n chiều
+
+
+
-
-
-
Mặt phân cách (WX = 0)
40
11
Khả năng của Perceptron
– có thể học các hàm ¬, ∧, ∨, NAND, NOR
– không biểu diễn được các hàm không phân tách được 
ằ ếb ng đường tuy n tính, vd XOR
1 0
(x1 ∨ x2) ∧ (¬x1 ∨ ¬x2)
0 1
41
¾ Mọi hàm logic đều có thể biểu diễn bằng 1 mạng 
perceptron có ít nhất 2 tầng
Mạng nơron biểu diễn hàm XOR
v1 = x1 ∨ x2
x1
x2
v1
v2
y
v = ¬x ∨ ¬ x
y = v1 ∧ v2
(x1 ∨ x2) ∧ (¬x1 ∨ ¬x2)
42
2 1 2
tầng vào tầng ẩn tầng ra
Học các trọng số mạng
• Luật perceptron: 
dùng khi tập luyện 
– phân tách được bằng 1 đường tuyến tính
– đủ nhỏ
• Luật delta:
43
dùng khi tập luyện không phân thể tách tuyến tính
Luật huấn luyện Perceptron
• Khởi tạo một vector có các trọng số ngẫu nhiên
Lặ l i hà t h ỗi ẫ l ệ đế khi hà• p ạ m percep ron c o m m u uy n n m 
perceptron phân loại đúng tất cả các mẫu luyện:
• Các trọng số được sửa đổi tại mỗi bước dựa vào luật huấn 
luyện perceptron:
trong đó 
iii www Δ+⎯⎯←
xotww )( −+Δ⎯⎯←Δ η
44
với
– t = c( ) là hàm đích
– o là đầu ra perceptron
– η = tốc độ học, là hằng số nhỏ
xr
iii
12
Ví dụ...
Biểu diễn g(x1,x2) = AND(x1,x2)
x1 W1
x1 x2 g
0 0 0
{0; 1}
x2
x0=1
W0
W2
Σ 0 1 0
1 0 0
1 1 1
w0 + 1.w1 + 1.w2 >0
45
o(x) = 1 nếu > 0
0 nếu ngược lại
xw rr. w0 + 1.w1 + 0.w2 < 0
w0 + 0.w1 + 1.w2 < 0
w0 + 0.w1 + 0.w2 < 0
Öw0 = -0.8; w1= 0.5; w2 = 0.5
Ví dụ...
ầ
iii xotww )( −+Δ⎯⎯←Δ ηiii www Δ+⎯⎯←
∑
=
=
2
0
*.
i
ii xwxw
rr
Khởi tạo các giá trị đ u: Δw0 = 0, Δw1 = 0, Δw2 = 0
w0 = -1.5, w1 = -0.5, w2 = 0.5, η = 0.1
x0 x1 x2 t ∑ o Δw0 Δw1 Δw2
1 0 0 0 -1.5 0 0 0 0
Δw0 = Δw0 + η*(t-o)*x0 = 0 + 0.1*(0-0)*1 = 0∑ = x0.w0+x1.w1+x2.w2 = 1.w0+0.w1+0.w2 = w0 = -1.5
w0 = w0 + Δw0 = -1.5 + 0 = -1.5, w1 = -0.5, w2 = 0.5
46
1 0 1 0 -1 0 0 0 0
1 1 0 0 -2 0 0 0 0
1 1 1 1 -1.5 0 0.1 0.1 0.1
Δw0 = Δw0 + η*(t-o)*x0 = 0 + 0.1*(1-0)*1 = 0.1
w0 = w0 + Δw0 = -1.5 + 0.1 = -1.4, w1 = -0.4, w2 = 0.6
Ví dụ...
iii xotww )( −+Δ⎯⎯←Δ ηiii www Δ+⎯⎯←
∑
=
=
2
0
*.
i
ii xwxw
rr
Δw0 = 0.1, Δw1 = 0.1, Δw2 = 0.1
w0 = -1.4, w1 = -0.4, w2 = 0.6, η = 0.1
w0 = w0 + Δw0 = -1.4 + 0.1 = -1.3, w1 = -0.3, w2 = 0.7
∑ = x0.w0+x1.w1+x2.w2 = 1.w0+0.w1+0.w2 = w0 = -1.4
Δw0 = Δw0 + η*(t-o)*x0 = 0.1 + 0.1*(0-0)*1 = 0.1
47
x0 x1 x2 t ∑ o Δw0 Δw1 Δw2
1 0 0 0 -1.4 0 0.1 0.1 0.1
1 0 1 0 -0.6 0 0.1 0.1 0.1
1 1 0 0
1 1 1 1
Ứng dụng của mạng nơron -
Nhận dạng mặt
48
13
Ứng dụng của mạng nơron -
Nhận dạng mặt
• Có nhiều hàm đích có thể học trong 
việc nhận dạng ảnh:
– xác định người
– hướng quay (trái, phải, thẳng, ...)
– giới tính
49
– có đeo kính hay không
Ứng dụng của mạng nơron -
Nhận dạng mặt
• Nhiệm vụ học: phân loại các hình ảnh camera về mặt người 
với nhiều góc độ khác nhau
• CSDL hình ảnh
• Các hình ảnh với 624 grayscale: 20 người, mỗi người khoảng 
32 ảnh 
• Nhiều cách biểu cảm (vui, buồn, giận, bình thường)
• Các hướng khác nhau (trái, phải, thẳng, hướng lên)
• Độ phân giải 120x128
50
• Học hướng quay của mặt người:
– không cần các lựa chọn tối ưu, phương pháp này cho kết 
quả tốt
– sau khi luyện trên 260 hình ảnh, việc phân loại đạt độ 
chính xác trên tập thử là 90%
Các lựa chọn
1 Mã hoá đầu vào: hình ảnh hay các đặc tính. 
2. Mã hoá đầu ra: số lượng đầu ra, các hàm đích cho 
đầu ra
3. Cấu trúc mạng: số lượng nút mạng và liên kết giữa 
chúng
4. Các tham số thuật toán học
ố
51
– T c độ học
– giá trị momentum
Mã hoá đầu vào
• Thiết kế các lựa chọn
• Tiền xử lý hình ảnh để rút ra các hướng, các vùng có 
ậ độ iố h h ặ á đặ í h hì h ả h bộm t g ng n au, o c c c c t n n n cục 
khác
• Khó khăn: số cạnh có thể thay đổi, trong khi NN có số 
lượng cố định các đầu vào
• Các hình đã mã hoá là 1 tập cố định các giá trị mật độ 
30x32 điểm ảnh (tóm tắt về độ phân giải của ảnh ban 
đầu) từ 0 đến 255
52
, 
14
Mã hoá đầu ra
• Mỗi đầu ra: 4 giá trị xác định hướng mà 
người nhìn (trái, phải, thẳng, hướng lên)
• Mỗi đơn vị: phân loại sử dụng 1 đầu ra, gán 
0.2, 0.4, 0.6 và 0.8 cho 4 giá trị 
• Chọn 1 trong n đầu ra mã hoá:
ấ hiề ứ độ t d để biể diễ hà
53
– cung c p n u m c ự o u n m 
đích (n lần số trọng số ở tầng ra)
– độ khác nhau giữa giá trị cao nhất và nhì dùng để 
đo độ tin cậy
Cấu trúc mạng
54
mạng 960 x 3 x 4