Bài giảng Học máy - Bài 10: Các phương pháp học có giám sát (Phần 7) - Nguyễn Nhật Quang

Học Máy
(IT 4862)
ễ hậNguy n N t Quang
quangnn-fit@mail.hut.edu.vn
Trường Đại học Bách Khoa Hà Nội
Viện Công nghệ thông tin và truyền thông
Năm học 2011-2012
Nội d ô hung m n ọc:
„ Giới thiệu chung
„ Đánh giá hiệu năng hệ thống học máy
„ Các phương pháp học dựa trên xác suất 
„ Các phương pháp học có giám sát
„ Giải thuật di truyền (Genetic algorithm) 
„ Các phương pháp học không giám sát
L ộ tᄠọc c ng c
„ Học tăng cường
2
Học Máy – IT 4862
Giải thuật di truyền – Giới thiệu
„ Dựa trên (bắt chước) quá trình tiến hóa tự nhiên trong sinh học
„ Áp dụng phương pháp tìm kiếm ngẫu nhiên (stochastic search) 
để tìm được lời giải (vd: một hàm mục tiêu, một mô hình phân 
lớp, ) tối ưu
„ Giải thuật di truyền (Generic Algorithm GA) có khả năng tìm – 
được các lời giải tốt thậm chí ngay cả với các không gian tìm 
kiếm (lời giải) không liên tục rất phức tạp
Mỗi khả ă ủ lời iải đ biể diễ bằ ộ h ỗi hị„ n ng c a g ược u n ng m t c u n 
phân (vd: 100101101) – được gọi là nhiễm sắc thể 
(chromosome)
• Việc biểu diễn này phụ thuộc vào từng bài toán cụ thể
„ GA cũng được xem như một bài toán học máy (a learning 
bl ) d t ê á t ì h tối hó ( ti i ti )
3Học Máy – IT 4862
pro em ựa r n qu r n ưu a op m za on
Giải thuật di truyền – Các bước chính
„ Xây dựng (khởi tạo) quần thể (population) ban đầu
• Tạo nên một số các giả thiết (khả năng của lời giải) ban đầu
Mỗi giả thiết khác các giả thiết khác (vd: khác nhau đối với các giá trị của một• 
số tham số nào đó của bài toán)
„ Đánh giá quần thể
Đánh giá (cho điểm) mỗi giả thiết ( d bằng cách kiểm tra độ chính ác của• v : x
hệ thống trên một tập dữ liệu kiểm thử)
• Trong lĩnh vực sinh học, điểm đánh giá này của mỗi giả thiết được gọi là độ
phù hợp (fitness) của giả thiết đó
• Xếp hạng các giả thiết theo mức độ phù hợp của chúng, và chỉ giữ lại các giả
thiết tốt nhất (gọi là các giả thiết phù hợp nhất – survival of the fittest)
„ Sản sinh ra thế hệ tiếp theo (next generation) 
• Thay đổi ngẫu nhiên các giả thiết để sản sinh ra thế hệ tiếp theo (gọi là các
con cháu – offspring)
„ Lặp lại quá trình trên cho đến khi ở một thế hệ nào đó có giả thiết tốt nhất có độ
4Học Máy – IT 4862
phù hợp cao hơn giá tri phù hợp mong muốn (định trước)
GA(Fitness, θ, n, rco, rmu)
Fit A f ti th t d th (fit ) i h th iness: unc on a pro uces e score ness g ven a ypo es s
θ: The desired fitness value (i.e., a threshold specifying the termination condition)
n: The number of hypotheses in the population
rco: The percentage of the population influenced by the crossover operator at each step
rmu: The percentage of the population influenced by the mutation operator at each step
Initialize the population: H Randomly generate hypotheses ← n
Evaluate the initial population. For each h∈H: compute Fitness(h)
while (max{h∈H}Fitness(h) < θ) do
Hnext ← ∅
Reproduction (Replication). Probabilistically select (1-rco).n hypotheses of 
H to add to Hnext .
The probability of selecting hypothesis hi from H is:
∑
= n
j
i
i
)Fitness(h
)Fitness(h)P(h
=j 1
5
Học Máy – IT 4862
GA(Fitness, θ, n, rco, rmu)
Crossover.
Probabilistically select (rco.n/2) pairs of hypotheses from H, according to 
the probability computation P(h ) given above i .
For each pair (hi, hj), produce two offspring (i.e., children) by applying 
the crossover operator. Then, add all the offspring to Hnext.
M t tiu a on.
Select (rmu.n) hypotheses of Hnext, with uniform probability.
For each selected hypothesis, invert one randomly chosen bit (i.e., 0 to 1, 
or 1 to 0) in the hypothesis’s representation .
Producing the next generation: H ← Hnext
Evaluate the new population. For each h∈H: compute Fitness(h)
end while
return argmax{h∈H}Fitness(h)
6
Học Máy – IT 4862
Giải thuật di truyền – Minh họa
[Duda et al., 2000]
7Học Máy – IT 4862
Các toán tử di truyền
„3 toán tử di truyền được sử dụng để sinh ra các cá thể con cháu 
(offspring) trong thế hệ tiếp theo
• Nhưng chỉ có 2 toán tử lai ghép (crossover) và đột biến (mutation) tạo nên 
sự thay đổi
„Tái sản xuất (Reproduction) 
→ Một giả thiết được giữ lại (không thay đổi)
„Lai ghép (Crossover) để sinh ra 2 cá thể mới
Ghép (“phối hợp") của hai cá thể cha mẹ→ 
• Điểm lai ghép được chọn ngẫu nhiên (trên chiều dài của nhiễm sắc thể)
• Phần đầu tiên của nhiễm sắc thể hi được ghép với phần sau của nhiễm 
sắc thể hj và ngược lại để sinh ra 2 nhiễm sắc thể mới , , 
„Đột biến (Mutation) để sinh ra 1 cá thể mới
→Chọn ngẫu nhiên một bit của nhiễm sắc thể, và đổi giá trị (0→1 / 1→0)
Chỉ t ê ột th đổi hỏ à ẫ hiê đối ới ột á thể h !
8Học Máy – IT 4862
• ạo n n m ay n v ng u n n v m c c a mẹ
Các toán tử di truyền – Ví dụ
Cha mẹ – Thế hệ 
hiện tại
Con cháu– Thế 
hệ tiếp theo
Tái sản xuất: 11101001000 11101001000
11101001000
00001010101
11111000000
(crossover mask)
11101010101
00001001000
Lai ghép tại 
1 điểm:
11101001000
00001010101
11001011000
00101000101
Lai ghép tại 
2 điểm:
00111110000
(crossover mask)
Đột biến: 11101001000 11101011000
[Mitchell, 1997]
9Học Máy – IT 4862
Biểu diễn giả thiết – Ví dụ
Ánh xạ (chuyển 
đổi) giữa: 
„ Biểu diễn các 
nhiễm sắc thể 
(chuỗi nhị phân), và
„ Biểu diễn cây 
quyết định cho bài 
toán phân lớp có 2 
lớp
[Duda et al., 2000]
10Học Máy – IT 4862
Tài liệu tham khảo
•T. M. Mitchell. Machine Learning. McGraw-Hill, 
1997.
•R. O. Duda, P. E. Hart, and D. G. Stork. Pattern 
Classification (2nd Edition). Wiley-Interscience, 
2000.
11Học Máy – IT 4862