Bài giảng Học máy - L3: Các phương pháp học dựa trên xác suất

Nội dung text: Bài giảng Học máy - L3: Các phương pháp học dựa trên xác suất

1. Nội dung môn họ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 têtrênxácsuất „ Các phương pháp họccógiámsát „ Các phương pháp học không giám sát „ Lọc cộng tác „ Họctăng cường Học Máy – IT 4862 2
2. Các khái niệm cơ bản về xác suất „ Giả sử chúng ta có một thí nghiệm (ví dụ: đổ một quân xúc sắc) mà kết quả của nó mang tính ngẫu nhiên (phụ thuộcvàokhc vào khả năng có th ể xảy ra) „ Không gian các khả năng S. Tập hợp tất cả các kết quả có thể xảy ra Ví d ụ: S= {123456}{1,2,3,4,5,6} đốivi với thí nghiệm đổ quân xúc sắc „ Sự kiện E. Một tập con của không gian các khả năng Ví dụ: E= {1}: kết quả quân súc xắc đổ ra là 1 Ví d ụ: E= {1,3,5}: kết quả quââún súc xắc đổ ra là một số lẻ „ Không gian các sự kiện W. Không gian (thế giới) mà các kết quả của sự kiện có thể xảy ra Ví dụ: W bao gồm tất cả các lần đổ súc xắc „ Biến ngẫu nhiên A. Một biến ngẫu nhiên biểu diễn (diễn đạt) một sự kiện, và có một mức độ về khả năng xảy ra sự kiện này ọ H c Máy – IT 4862 4
3. Các biến ngẫu nhiên 2 giá trị „ Một biến ngẫu nhiên 2 giá trị (nhị phân) có thể nhận một trong 2 giá trị đúng (true)ho) hoặccsai( sai (false) „ Các tiên đề • 0 ≤ P(A) ≤ 1 • P(true)= 1 • P(false)= 0 • P(A V B)= P(A) + P(B) - P(A ∧ B) „ Các hệ quả • P(not A)≡ P(~A)= 1 - P(A) • P(A)= P(A ∧ B) + P(A ∧ ~B)B) ọ H c Máy – IT 4862 6
4. Xác suất có điều kiện (1) „ P(A|B) là phần của không gian (thế giới) mà trong đó A là đúng, với điều kiện (đã biết) là B đúng „ Ví dụ • A: Tôi sẽ đi đá bóng vào ngày mai • B: Trời sẽ không mưa vào ngày mai • P(A|B): Xác suất của việc tôi sẽ đi đá bóng vào ngày mai nếu (đã biết rằng) trời sẽ không mưa (vào ngày mai) ọ H c Máy – IT 4862 8
5. Các biến độc lập về xác suất (1) „ Hai sự kiện A và B được gọi là độc lập về xác suất nếu xác suấtct củasa sự kiện A là như nhau đốivi vớicáctri các trường hợp: • Khi sự kiện B xảy ra, hoặc • Khi sự kiện B không xảy ra, hoặc • Không có thông tin (không biết gì) về việc xảy ra của sự kiện B „ Ví d ụ •A: Tôi sẽ đi đá bóng vào ngày mai •B:Tu: Tuấnsn sẽ tham gia trận đá bóng ngày mai •P(A|B) = P(A) → “Dù Tuấn có tham gia trận đá bóng ngày mai hay không cũng không ảnh hưởng tới quyết định của tôi về việc đi đá bóng ngày mai.” ọ H c Máy – IT 4862 10
6. Xác suất có điều kiện với >2 biến „ P(A|B,C) là xác suất của A đối với (đã biết) B và C B C „ Ví dụ : Tôi sẽ đi dạo bờ sông vào sáng mai • A A • B: Thời tiết sáng mai rất đẹp • C: Tôi sẽ dậy sớm vààáo sáng ma i P(A|B, C) • P(A|B,C): Xác suất của việc tôi sẽ đi dạo dọc bờ sôngg,g vào sáng mai, nếu (đã biết rằng) thời tiết sáng mai rất đẹp và tôi sẽ dậy sớm vào sáng mai ọ H c Máy – IT 4862 12
7. Các quy tắc quan trọng của xác suất „ Quy tắc chuỗi (chain rule) • P(A,B) = P(A|B). P(B) = P(B|A). P(A) • P(A|B) = P(A,B)/P(B) = P(B|A).P(A)/P(B) • P(A,B|C) = P(A,B,C)/P(C) = P(A|B,C).P(B,C)/P(C) = P(A|B,C).P(B|C) „ Độclc lậpvp về xác suấttvà và độccl lậppcó có điềuuki kiện • P(A|B) = P(A); nếu A và B là độc lập về xác suất • P(A,B|C) = P(A|C).P(B|C);n; nếu A và B là độccl lậppcó có điều kiện đối với C • P(A1, ,An|C) = P(A1|C) P(An|C); nếu A1, ,An là độc lập có điềukiu kiện đốiiv với C ọ H c Máy – IT 4862 14
8. Định lý Bayes – Ví dụ (1) Giả sử chúng ta có tập dữ liệu sau (dự đoán 1 người có chơi tennis)? Ngày Ngoài trời Nhiệt độ Độ ẩm Gió Chơi tennis N1 Nắng Nóng Cao Yếu Không N2 Nắng Nóng Cao Mạnh Không N3 Âmu Nóng Cao Yếu Có N4 MưaBìnhthường Cao YếuCó N5 MưaMátmẻ Bình thường YếuCó N6 MưaMátmẻ Bình thường Mạnh Không N7 Âm u Mát mẻ Bình thường Mạnh Có N8 Nắng Bình thường Cao Yếu Không N9 Nắng Mát mẻ Bình thường YếuCó N10 MưaBìnhthường Bình thường YếuCó N11 Nắng Bình thường Bình thường Mạnh Có N12 Âm u Bình thường Cao Mạnh Có [Mitchell, 1997] ọ H c Máy – IT 4862 16
9. Xác suất hậu nghiệm cựu đại (MAP) „ Với một tập các giả thiết (các phân lớp) có thể H, hệ thống học sẽ tìm giả thiếttcóth có thể xảyyranh ra nhất (the most probable hypothesis) h(∈H) đối với các dữ liệu quan sát được D „ Giả thiết h này được gọi là giả thiết có xác suất hậu nghiệm cực đại (Maximum a posteriori – MAP) hMAP = arg max P(h | D) h∈H P(D | h).P(h) (bởi định lý Bayes) hMAP = arg max h∈H P(D) (P(D) là như nhau hMAP = arg max P(D | h).P(h) h∈H đối với các giả thiết h) ọ H c Máy – IT 4862 18
10. Đánh giá khả năng có thể nhất (MLE) „ Phương pháp MAP: Với một tập các giả thiết có thể H, cần tìm mộtgit giả thiếttc cực đại hóa giá trị: P(D|h).P(h) „ Giả sử (assumption) trong phương pháp đánh giá khả năng có thể nhất (Maximum likelihood estimation – MLE): Tất cả các giả thiết đều có giá trị xác suất trước như nhau: P(hi)=P(hj), ∀hi,hj∈H „ Phương pháp MLE tìm giả thiếttc cực đại hóa giá trị P(D|h); trong đó P(D|h) được gọi là khả năng có thể (likelihood) của dữ liệu D đối với h „ Giả thiết có khả năng nhất (maximum likelihood hypothesis) hML = arg max P(D | h) h∈H ọ H c Máy – IT 4862 20
11. Phân loại Naïve Bayes (1) „ Biểu diễn bài toán phân loại (classification problem) • Mộttt tập học D_train, trong đó mỗiiíd ví dụ học x được biểu diễn là một vectơ n chiều: (x1, x2, , xn) • Một tập xác định các nhãn lớp: C={c1, c2, , cm} • Với một ví dụ (mới) z, thì z sẽ được phân vào lớp nào? „ Mục tiêu: Xác định phân lớp có thể (phù hợp) nhất đối với z cMAP = arg max P(ci | z) ci∈C cMAP = arg max P(ci | z1, z2 , , zn ) ci∈C P(z1, z2 , , zn | ci ).P(ci ) (bởi định lý Bayes) cMAP = arg max ci∈C P(z1, z2 , , zn ) ọ H c Máy – IT 4862 22
12. Phân loại Naïve Bayes – Giải thuật „ Giai đoạn học (training phase), sử dụng một tập học Đốivi vớiim mỗi phân lớppcóth có thể (mỗi nhãn lớp) ci∈C • Tính giá trị xác suất trước: P(ci) • Đối với mỗi giá trị thuộc tính xj, tính giá trị xác suất xảy ra của giá trị thuộc tính đó đối với mộthâlt phân lớp ci: P(xj|ci) „ Giai đoạn phân lớp (classification phase), đối với một ví dụ mới • Đốivi vớiim mỗi phân lớp ci∈C, tính giá tr ị củaabi biểuuth thức: n P(ci ).∏ P(x j | ci ) j=1 • Xác định phân lớp của z là lớp có thể nhất c* n * c = arg max P(ci ).∏ P(x j | ci ) ci∈C j=1 ọ H c Máy – IT 4862 24
13. Phân lớp Naïve Bayes – Ví dụ (2) „ Biểu diễn bài toán phân loại • z = (Age= Young,Income=MdiMedium,Student=Yes,Credit_Rating= FiFair) • Có 2 phân lớp có thể: c1 (“Mua máy tính”) và c2 (“Không mua máy tính”) „ Tính giá trị xác suấtttr trướccchom cho mỗi phân lớp • P(c1) = 9/14 • P(c2) = 5/14 „ Tính giá trị xác suất của mỗi giá trị thuộc tính đối với mỗi phân lớp • P(Age=Young|c1) = 2/9; P(Age=Young|c2) = 3/5 • P(Income=Medium|c1) = 4/9; P(Income=Medium|c2) = 2/5 • P(Student=Yes|c1) = 6/9; P(Student=Yes|c2) = 1/5 • P(Credit_ Rating=Fair|c1)); = 6/9; P(Credit_ Rating=Fair|c2) = 2/5 ọ H c Máy – IT 4862 26
14. Phân lớp Naïve Bayes – Vấn đề (1) „ Nếu không có ví dụ nào gắnvới phân lớp ci có giá trị thuộc tính xj n P(xj|ci)=0 , và vì vậy: P(ci ).∏ P(x j | ci ) = 0 j=1 „ Giải pháp: Sử dụng phương pháp Bayes để ướclượng P(xj|ci) n(ci , x j ) + mp P(x j | ci ) = n(ci ) + m • n(ci): số lượng các ví dụ học gắnvới phân lớp ci • n(ci,xj): số lượng các ví dụ họcgắnvới phân lớp ci có giá trị thuộc tính xj • p: ướclượng đốivớigiátrị xác suất P(xj|ci) → Các ướclượng đồng mức: p=1/k, vớithuộc tính fj có k giá trị có thể • m: mộthệ số (trọng số) → Để bổ sung cho n(ci) các ví dụ thựcsựđược quan sát với thêm m mẫuvídụ với ướclượng p ọ H c Máy – IT 4862 28
15. Phân loại văn bản bằng NB (1) „ Biểu diễn bài toán phân loại văn bản • Tập học D_train, trong đó mỗi ví dụ học là một biểu diễn văn bản gắn với một nhãn lớp: D = {(dk, ci)} • Một tập các nhãn lớp xác định: C = {ci} „ Giai đoạnhn học • Từ tập các văn bản trong D_train, trích ra tập các từ khóa (keywords/terms): T = {tj} • Gọi DcD_ci (⊆D_ train)làt) là tậpcácvp các vănnb bản trong D_ train có nhãn lớp ci • Đối với mỗi phân lớp ci D _ ci - Tính giá trị xác suất trước của phân lớp ci: P(c ) = i D - Đối với mỗi từ khóa tj, tính xác suất từ khóa tj xuất hiện đối với lớp ci (∑ n(dk ,t j ))+1 dk ∈D _ ci (n(dk,tj): số lần xuất hiện của từ P(t j | ci ) = khóa tj trong v ănnb bản dk) n(dk ,tm ) + T (∑dTkm∈∈D _ ci ∑t ) ọ H c Máy – IT 4862 30
16. Phân loại Naïve Bayes – Tổng kết „ Một trong các phương pháp học máy được áp dụng phổ biến nhất trong thực tế „ Dựa trên định lý Bayes „ Việc phân loại dựa trên các giá trị xác suất của các khả năng xảyracy ra của các giả thiết (phân lo ại) „ Mặc dù đặt giả sử về sự độc lập có điều kiện của các thuộc tính đối với các phân lớp, nhưng phương pháp phân loại NïNaïve Bayes vẫn thu được cákác kết quả phân loạiit tốttt trong nhiều lĩnh vực ứng dụng thực tế „ Khi nào nên sử dụng? • Có một tập huấn luyện có kích thước lớn hoặc vừa • Các ví dụ được biểu diễn bởi một số lượng lớn các thuộc tính • Các thuộctínhc tính độclc lậpcóp có điềukiu kiện đốiiv với các phân l ớp ọ H c Máy – IT 4862 32
17. Cực đại hóa kỳ vọng – EM (2) „ Phương pháp học EM thường được sử dụng trong những bài toán tồntn tại các biến(thun (thuộc tính) không quan sát được (ẩn) • EM tìm các đánh giá có thể nhất (maximum likelihood estimates) của các tham số trong một mô hình xác suất phụ thuộc vào các biến không quan sát được (()unobserved variables) • Không sử dụng tốc độ học (vd: như phương pháp học mạng nơ-ron nhân tạo) • Đảm bảo tìm được một giá trị tối ưu cục bộ (a local optimum) của xác suất likelihood, cùng với các giá trị ướclc lượng đượccc của các biến không quan sát được ọ H c Máy – IT 4862 34
18. EM – Phát biểu bài toán (2) „ Phương pháp EM lặp lại 2 bước sau đây • Tính toán giá trị kỳ vọng (Expectation step). Với các giá trị được ước lượng hiện tại của các tham số θ, tính toán các giá trị kỳ vọng của các biến không quan sát được • Cực đại hóa (Maximization step). Với các giá trị kỳ vọng được gán cho các biến không quan sát được (tính ở bướcctrên trên – E-step), tính toán l ạiicác các đánh giá có thể nhất (maximum likelihood estimates) của các tham số θ „ Ký hiệu E[P(X|θ)] là giá trị kỳ vọng của khả năng có thể (likelihood) củata tậppd dữ liệu X, đốivi với các giá trị ướccl lượng hiện tại của các tham số θ • Giá trị (trung bình) kỳ vọng được tính toán dựa trên các giá trị có thể của phầndn dữ liệu không qu an sát đợđược Z, • Gắn trọng số (weighting) mỗi giá trị có thể với xác suất xảy ra của giá trị đó „ Giải thuật EM tìm các đánh giá có thể nhất (maximum likelihood estimates) θ* giúp cực đại hóa (cục bộ) giá trị E[P(X|θ)] ọ H c Máy – IT 4862 36
19. Phân loại văn bản bằng EM (1) „ Trong thực tế, chúng ta thường có một tập nhỏ các văn bản có nhãn lớp và một tập lớn hơn các văn bản không có nhãn lớp Tập các văn bản D = DL ∪ DU •DL: Tập các văn bản có nhãn lớp • DU: Tập các văn bản không có nhãn lớp • |DL| << |DU| „ Mục tiêu: Gán nhãn lớp chính xác cho các văn bản trong tập DU „ Tại sao chúnggyg ta không xây dựngg( (học) một bộ phân loại dựa trên tập các văn bản có nhãn trong DL, và sau đó sử dụng bộ phân loại đó để phân loại các văn bản không có nhãn? →Cần khai thác các thông tin ẩn trong tập DU để nâng cao hiệu năng của bộ phân loại học được • Khai thác các phân bố kết hợp của các từ khóa đối với các phân lớp • Khai thác sự tương đồng giữa các văn bản (vd: một văn bản có nhãn và một văn bản không có n hãn c ùng c hứa một số cáátc từ khóa ) ọ H c Máy – IT 4862 38
20. Phân loại văn bản bằng EM (3) „ Ở bước lặp thứ k ( tiếp tục) • Bước cực đại hóa (M-step). Đối với mỗi từ khóa tj và mỗi phân lớp ci, đáhánh g iáliá lạiiáth các tham số của phân bố xác suất(t (của tàtoàn bộ tập văn bản D) (k) 1+ ∑ P (ci | d).n(d,t j ) P(k) (t | c ) = d∈D j i (k) | T | + P (ci | d).n(d,tq ) ∑d∈D ∑tq∈T 1 P(k ) (c ) = P(k ) (c | d) i | D | ∑d∈D i -Đóng góp củagiátra giá trị củata tầnsun suấtxut xuấthit hiệnnt từ khóa n(d, tj) trong văn bản d đối với phân lớp ci được gán trọng số (weighted) bởi P(ci|d) –giá trị xác suất của văn bản d thuộc vào lớp ci L -Đối với một văn bản có nhãn d (∈D ) và nhãn lớppg gắn với nó cd, P(ci|d)=1 if ci≡cd, and P(ci|d)=0 if ci≠cd „ Lặp lại 2 bước (E-step, M-step) cho đến khi thỏa mãn đk hội tụ Ví d ụ:%c: % của thay đổiiv về nhãn lớp được gán cho các vănnb bản không có nhãn (trong DU) giữa 2 bước lặp kế tiếp nhỏ hơn một giá trị ngưỡng. ọ H c Máy – IT 4862 40