Bài giảng Học máy - L7: Các phương pháp học có giám sát Học quy nạp luật (Rule induction)

Nội dung text: Bài giảng Học máy - L7: Các phương pháp học có giám sát Học quy nạp luật (Rule induction)

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 „ Học quy nạp luật (Rule induction) „ 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. Quy nạp luật – Giới thiệu (2) „ Nhắclại: Học cây quyết định (Decision tree learning) cũng có cho ppphép học mộttập các luật logic định đề • Bước 1: Học cây quyết định • Bước 2: Biểudiễnmỗi đường đi trong cây (từ nút gốc đến nút lá) thành một luật tương ứng „ Học mộttậpcácluật • Học cây qqyuyết định: Tập các luật logic định đề được học đồng thời • Học quy nạpluật: Tậpcácluật logic định đề/vị từ được học tuầntự (từng luật một) „ Cácgiải thuật khácnhau để học các kiểu luật khácnhau • Các luật logic định đề (chỉ sử dụng các ký hiệuhằng) • Các luật logic vị từ (sử dụng cả các ký hiệubiến và các ký hiệuvị từ) –khả năng diễn đạt cao hơn ọ H c Máy – IT 4862 4
3. Quy nạp luật – Ví dụ (2) „ Luật: IF (Age=Old Λ Student=No) THEN Buy_Computer=No „ Những ví dụ nào được phân loại chính xác bởi luật trên? Rec. ID Age Income Student Credit_Rating Buy_Computer 1 Young High No Fair No 2 Medium High No Fair Yes X 3 Old Medium No Fair Yes 4 Old Low Yes ElltExcellent No 5 Medium Low Yes Excellent Yes 6 Young Medium No Fair No 7 Old Medium Yes Fair Yes 8 Medium High Yes Fair Yes √ 9 Old Medium No Excellent No ọ H c Máy – IT 4862 6
4. Sequential-Covering(TargetAttribute, Attributes, TrainingSet, Threshold) LearnedRules ← {} Rule ← LEARN-ONE-RULE(TargetAttribute, Attributes, TrainingSet) while PERFORMANCE(Rule, TrainingSet) > Threshold LearnedRules ← LearnedRules ∪ Rule TrainingSet ← TrainingSet \ {các ví dụ được phân loại chính xác bởi Rule} Rule ← LEARN-ONE-RULE(TargetAttribute, Attributes, TrainingSet) end while Sắpxếp LdRlLearnedRules theo đáhánh giá PERFORMANCE đối với tập TiiStTrainingSet return {LearnedRules, DefaultRule} • DfDefau ltRlltRule: IF THEN (Giá trị phổ biếnnhất của TargetAttribute trong tập TrainingSet) • LEARN-ONE-RULE: Hàm thựchiệnhọc mộtluật đốivớitập TrainingSet • PERFORMANCE: Hàm đánh giá chất lượng (hiệu quả) của một luậtht học được Học Máy – IT 4862 8
5. Chiến lược bao phủ gia tăng – Các vấn đề „ Chuyển bài toán (phức tạp hơn) học một tập các luật thành một chuỗi các bài toán (đơn giản hơn), mỗi bài toán học một luật • Sau khi học được một luật, thì tất cả các ví dụ học bị bao phủ (được phân loại chính xác) bởi luật đó sẽ được loại khỏi tập huấn luyện • Mỗi luật được học một cách độc lập với các luật khác – Vấn đề: Nếu các luật có sự phụ thuộc (tác động) lẫn nhau? „ Để tìm một chuỗi các luật, thực hiện chiến lược tìm kiếm tham lam (greedy search) mà không có quay lui xét lại (without backtracking) • Không đảm bảo tìm được một tập nhỏ nhất các luật • Không đảm bảo tìm được một tập tối ưu (vd: về khía cạnh phân loại chính x ác) các luật ọ H c Máy – IT 4862 10
6. LEARN-ONE-RULE_1(TargetAttribute, Attributes, TrainingSet) Best_Pre-cond ← Ø whilhile (Attr ibu tes ≠ Ø) and (TiiStTrainingSet ≠ Ø) // 1. Sinh ra tập ứng cử củacácđiềukiệncóthể bổ sung (thêm vào) mệnh đề IF củaluật All_constraints ← Tậpcácđiềukiệncódạng (A=v), trong đó A ∈ Attr ibu tes và v là một giá trị của A xảyratrong TiiStTrainingSet Candidate_Pre-conds ← for each c ∈ All_constraints, Tạo một mệnh đề điềukiện(Best_Pre-cond ∧ c) // 2 . Cập nhật mệnh đề điều kiện tốt nhất Best_Pre-cond Best_Pre-cond ← argmaxPC ∈ Candidate_Pre-conds {PERFORMANCE(PC, TrainingSet, TargetAttribute)} Attr ibu tes ← Attr ibu tes \ {Thuộc tính A+ tương ứng với điều kiện c+ vừamới đượcbổ sung vào Best_Pre-cond} (*) TrainingSet ← {Các ví dụ học phù hợpvới Best_Pre-cond} endhild while return (Luật: IF Best_Pre-cond THEN prediction) (prediction giá trị (nhãn lớp) phổ biến nhất của TargetAttribute trong số các ví dụ học, TrainingSet (trước Bước (*)), phù hợp với Best_Pre-cond Học Máy – IT 4862 12
7. LEARN-ONE-RULE_1 –Các vấn đề „ LEARN-ONE-RULE_1 có chiếnlược tìm kiếmgiống như ID3 • Học (phát triển) luật/cây bằng cách bổ sung dần dần các điều kiện đốivớicácthuộc tính • Dừng, khi luật/cây học được đạttớimứchiệunăng chấpnhận được „ Nhưng có sự khácnhau: • Tạimỗibước tìm kiếm, LEARN-ONE-RULE_1 chỉđi theo mộthướng cụ thể hóa điềukiện (A=v*) giúp đem lạihiệunăng cao nhất • ID3 phát triểnmột cây con gồmtấtcả các giá trị có thể vi của A „ LEARN-ONE-RULE_1 thựchiện tìm kiếm theo chiều sâu tham lam (greedy depth-first), không xét lại (without backtracking) → Tạimỗibước tìm kiếm, điềukiện đượcbổ sung (A=v*) có thể không tối ưu „ Giải pháp khắcphục: Thựchiện tìm kiếm chùm (beam search) ọ H c Máy – IT 4862 14
8. LEARN-ONE-RULE_2(TargetAttribute, Attributes, TrainingSet) Best_ Pre-cond ← Ø // mệnh đề điều kiện tổnggq quát nhất Candidate_Pre-conds ← {Best_Pre-cond} while (Attributes ≠ Ø) // 1 . Sinh ra t ập ứng cử của các điều kiện cóthó thể bổ sung (thêm và o) mệnh đề IF của các luật All_constraints ← Tập các điều kiện có dạng (A=v), trong đó A ∈ Attributes và v là một giá trị của A xảy ra trong TrainingSet New_candidate_Pre-conds ← for each pc ∈ Candidate_Pre-conds, for each c ∈ All_constraints, Tạo một mệnh đề điều kiện (pc ∧ c) Loạikhi khỏiti tập New_ candidatecandidate_Pre-conds bấtkt kỳ mệnh đề điềuuki kiện nào trùng lặp hoặc mâu thuẫn // vd: (Ai=vj) Λ (Ai=vk) . . . Học Máy – IT 4862 16
9. Đánh giá hiệu quả của một luật (1) „ Hàm PERFORMANCE(.) được sử dụng trong các giải thuật nêu trên „ Đánh giá dựa trên tỷ lệ phân loại chính xác • D_trainR: Tập cáídác ví dụ học phù hợp với mệnh đề điều kiện (IF) của luật R • n: Kích thước của tập D__trainR R • nc: Số lượng các ví dụ trong tập D_train được phân loại chính xác bởi R n PERFORMANCE(R, D _ train R ) = c n ọ H c Máy – IT 4862 18
10. Đánh giá hiệu quả của một luật (3) „ Đánh giá dựa trên giá trị Entropy • c:S: Số lượng các giá trị củathua thuộc tính phân loạii(=S (= Số lượng nhãn lớp) R • pi: Tỷ lệ số lượng các ví dụ trong tập D_train được phân (gán) vào lớp thứ i PERFORMANCE(R, D _ train R ) = −Entropy(D _ train R ) c = ∑ pi .log2 pi i=1 ọ H c Máy – IT 4862 20
11. Học các luật logic vị từ –Giải thuật FOIL „ Để học một tập các luật logic vị từ (có chứa các biến) • Các luật logic vị từ có khả năng diễn đạt cao hơn nhiều so với các luậttl logi c định đề „ Giải thuật FOIL (“first-order inductive logic”) • Bắt đầu với một tập rỗng (các luật học được) • Học mộttl luật mớiià, và sau đóób bổ sung vààto tập cáálc luậtth học được ─ Tuần tự bổ sung các literals kết hợp (conjunctive) vào trong luật mới, cho đến khi không có ví dụ sai nào (negative instance) được phân lo ại (phù hợp) vớiilu luậttm mới → Một ví dụ sai là ví dụ thỏa mãn mện đề điều kiện (IF) của luật, nhưng có giá trị sai đối với vị từ (trong mệnh đềTHEN) ─ Khi xét các literals ứng cứ viên, cần lựa chọn literal có giá trị đánh giá Foil_Gain lớn nhất • Loại bỏ các ví dụ đúng (positive instances) đối với luật mới • Lặp lại để học một luật khác Cho đến khi không còn ví dụ đúng (positive instances) nào nữa ọ H c Máy – IT 4862 22
12. FOIL(Target_predicate, Predicates, Examples) . . . Best_literal ← argmaxL ∈ Candidate_literalsFoil_Gain(L,R) Add Best_ literal to the preconditions of R NegSet_R ← {instances in NegSet_R that match the precondtions of R} end while Learned_rules ← {Learned_rules, R} PosSet ← PosSet \ {instances in PosSet covered by R} end while return Learned_rules Học Máy – IT 4862 24
13. Sản sinh các điều kiện cụ thể hóa trong FOIL „ Luật cần được cụ thể hóa: L1 Λ Λ Ln → P(x1, ,xk) • L1, ,Ln: Các literals tạo nên mệnh đề điềuuki kiệnnc củaalu luật • P(x1, ,xk): Literal tạo nên mệnh đề kết luận của luật „ Sinh ra các điềukiu kiệnnc cụ thể hóa củaalu luậtbt bằng cách bổ sung một literal mới Ln+1 , có thể là: • xi=xj, xi=c, xi>xj, xi≥xj; trong đó xi và xj là các biến đã tồn tại trong luật • Q(y1, ,ym); trong đó Q là một vị từ thuộc tập Predicates, và yi là các biếnnvà và ít nhấtmt một trong số các biến này (yi)ph) phải đã tồn tại trong luật • Dạng phủ định (negation) của 1 trong 2 dạng literals nêu trên ọ H c Máy – IT 4862 26
14. Hàm đánh giá Foil_Gain ⎛ p p ⎞ ⎜ 1 0 ⎟ Foil _ Gain (L, R) = t.⎜ log 2 − log 2 ⎟ ⎝ p1 + n1 p0 + n0 ⎠ •R: Luật ban đầu (trước khi bổ sung literal L) •L: Literal ứng cử viên để bổ sung vào luật R •p0: Số lượng các ràng buộc đúng (positive bindings) của luật R •n0: Số lượnggg các ràng buộc sai ((gnegative bindin g)gs) của luật R •p1: Số lượng các ràng buộc đúng của luật mới (R+L) •n1: Số lượng các ràng buộc sai của luật mới (R+L) •t: Số lượng các ràng buộc đúng của luật ban đầu R cũng là các ràng buộc đúng của luật mới (R+L) (Số lượng các ràng buộc biến làm cho cả 2 luật R và (R+L) cùng đúng) ọ H c Máy – IT 4862 28
15. Tài liệu tham khảo • T. M. Mitchell. Machine Learning. McGraw-Hill, 1997. ọ H c Máy – IT 4862 30