Bài giảng Học máy - L9: Các phương pháp học có giám sát Giải thuật di truyền (Genetic algorithm)

Nội dung text: Bài giảng Học máy - L9: Các phương pháp học có giám sát Giải thuật di truyền (Genetic algorithm)

1. Nội dung môn học: „ Giới thiệu chung „ Đánh giá hiệunăng hệ thống họcmáy „ Các phương pháp họccd dựatrênxácsua trên xác suất „ Các phương pháp họccógiámsá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ọccộng tác „ Họctăng cường Học Máy – IT 4862 2
2. Giải thuật di truyền – Các bước chính „ Xây dựng (khởitạo) quầnthể (population) ban đầu • Tạo nên mộtsố các giả thiết(khả năng củalờigiả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ầnthể • Đánh giá (cho điểm) mỗi giả thiết (vd: bằng cách kiểm tra độ chính xác của hệ thống trên mộttậpdữ liệukiểmthử) • Trong lĩnh vựcsinhhọc, điểm đánh giá này củamỗigiả thiết đượcgọilàđộ phù hợp (fitness) của giả thiết đó • Xếphạng các giả thiết theo mức độ phù hợpcủa chúng, và chỉ giữ lại các giả thiếttốtnhất(gọilàcác giả thiết phù hợpnhất – survival of the fittest) „ Sản sinh ra thế hệ tiếp theo (next generation) • Thay đổingẫu nhiên các giả thiết để sảnsinhrathế hệ tiếp theo (gọilà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ó độ phù hợp cao hơn giá tri phù hợp mong muốn(định trước) ọ H c Máy – IT 4862 4
3. GA(Fitness, θ, n, rco, rmu) Crossover. Probabilistically select (rco.n/2) pairs of hypotheses from H, according to the probability computation P(hi) given above. For each pair (hi, hj), produce two offspring (i.e., children) by applying the crossover operator. Then, add all the offspring to Hnext. MttiMutation. next Select (rmu.n) hypotheses of H , 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) Học Máy – IT 4862 6
4. 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 ảnxun 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 (“phốihi hợpp)")c 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ắcthc thể hj, và ng ượccl lại, để sinh ra 2 nhiễmms sắccth 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ạo nên mộttht thay đổihi nhỏ và ngẫu nhiên đối với mộtátht cá thể cha mẹ! ọ H c Máy – IT 4862 8
5. Biểu diễn giả thiết – Ví dụ Ánh xạ (chuyển đổi) giữa: „ Biểu diễn các nhiễmsm sắcthc 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] ọ H c Máy – IT 4862 10