Bài giảng Học máy - Bài 4: Giải thuật di truyền - 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