Bài giảng Học máy - L9: Các phương pháp học có giám sát Máy vectơ hỗ trợ (Support vector machine)

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 Máy vectơ hỗ trợ (Support vector machine)

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 „ Máy vectơ hỗ trợ (Support vector machine) „ 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. Máy vectơ hỗ trợ -Giớithiệu(2) „ SVM có một nền tảng lý thuyết chặt chẽ –dựa trên nhiều định lý toán học „ SVM là một phương pháp tốt (phù hợp) đối với những bài toán phân lớp có không gian biểudiu diễnthun thuộc tính lớn – các đối tượng cần phân lớp được biểu diễn bởi một tập rất lớn các thuộc tính „ SVM đã được biết đến là một trong số các phương pháp phân lớp tốt nhất đối với các bài toán phân lớp văn bản (text/document classification) ọ H c Máy – IT 4862 4
3. Mặtsiêuphẳng phân tách „ Mặt siêu phẳng phân tách các ví dụ huấn luyện lớp dương và các ví dụ huấnnluy luyệnln lớpâm:p âm: 〈w ⋅ x〉 +b+ b =0= 0 „ Còn được gọi là ranh giới (bề mặt) quyết định „ Tồntn tại nhiềumu mặtsiêupht siêu phẳng phân tách. Ch ọn cái nào? [Liu, 2006] ọ H c Máy – IT 4862 6
4. SVM – Dữ liệu phân tách đượctuyến tính „ Giả sử rằng tập dữ liệu (tập các ví dụ huấn luyện) có thể phân tách được một cách tuyến tính „ Xét một ví dụ của lớp dương (x+,1) và một ví dụ của lớp âm - (x ,-1) gần nhất đối với siêu phẳng phân tách H0 ( +b=0) „ Định nghĩa 2 siêu phẳng lề song song với nhau + ‰ H+ đi qua x , và song song với H0 - ‰ H- điqi qu a x , và song song với H0 + H+: +b = 1 - [[qEq.3 ] H-: +b = -1 sao cho: +b ≥ 1, nếu yi = 1 +b ≤ -1, nếu yi = -1 ọ H c Máy – IT 4862 8
5. Tính toán mứclề (2) + „ Tính toán d+ –khoảng cách từ x đến(〈w ⋅ x〉 + b = 0) ‰ Áp dụng các biểu thức [Eq.3 -4]: | 〈w ⋅x+ 〉 + b | |1| 1 d = = = [Eq.6] + || w || || w || || w || - „ Tính toán d- –khoảng cách từ x đến(〈w ⋅ x〉 + b = 0) ‰ Áp dụng các biểuthức [Eq.3-4]: | 〈w ⋅x− 〉 + b | | −1| 1 d = = = [Eq.7] − || w || || w || || w || „ Tính tátoánmức lề 2 margin = d + d = [Eq.8] + − || w || ọ H c Máy – IT 4862 10
6. Cực đại hóa mứclề – Bài toán tối ưu „ Học SVM tương đương vớigiải quyết bài toán cựctiểu hóa có ràng buộc sau đây 〈w ⋅w〉 Cựctiểu hóa: [Eq.9] 2 ⎧〈w ⋅xi 〉 + b ≥1, if yi =1 Với điềukiện: ⎨ ⎩〈w ⋅xi 〉 + b ≤ −1, if yi = −1 „ tương đương với Cực tiểu hóa: 〈w ⋅w〉 [Eq. 10] 2 Với điềukiện: yi (〈w ⋅xi 〉 + b) ≥1, ∀i =1 r ọ H c Máy – IT 4862 12
7. Lý thuyếttối ưu có ràng buộc(2) „ Bài toán cựctiểu hóa có các ràng buộcbất đẳng thức: Cực tiểu hóa f(x), với các điều kiện gi(x)≤0 „ Điềukiệncần để x0 là mộtlờigiải: ⎧ ∂ ⎛ r ⎞ ⎪ ⎜ f(x)+ ∑αi gi(x)⎟ = 0 ∂x ; với αi ≥ 0 ⎨ ⎝ i=1 ⎠ x=x ⎪ 0 ⎩gi(x) ≤ 0 „ Hàm r L = f(x)+ ∑αi gi(x) i=1 đượcgọi là hàm Lagrange ọ H c Máy – IT 4862 14
8. Tập điềukiện Karush-Kuhn-Tucker ∂L r P [Eq.12] = w − ∑αi yixi = 0 ∂w i=1 ∂L r P [Eq.13] = −∑αi yi = 0 ∂b i=1 yi ( w ⋅xi + b)−1≥ 0, ∀xi (i =1 r) [Eq. 14] αi ≥ 0 [Eq.15] αi (yi ( w ⋅xi + b)−1)= 0 [Eq. 16] „ [Eq.14] chính là tập các ràng buộc ban đầu „ Điều kiện bổ sung [Eq.16] chỉ ra rằng chỉ những ví dụ (điểm dữ liệu) thuộc các mặt siêu phẳng lề (H+ và H-) mới có αi>0 – bởi vì với những ví đụ đó thì yi(〈w⋅xi〉+b)-1=0 →Những ví dụ (điểm dữ liệu) này được gọi là các vectơ hỗ trợ! „ Đốối với các ví dụ khác (không phải là các vectơ hỗ trợ) thì αi=0 ọ H c Máy – IT 4862 16
9. Biểuthức đốingẫu „ Để thu được biểu thức đối ngẫu từ biểu thức ban đầu: →Gán giá tr ị bằng 0 đốiiv vớiicác các đạo hàm bộ phậnnc củaabi biểuuth thức Lagrange trong [Eq.11] đối với các biến ban đầu (w và b) →Sau đó, áp dụng các quan hệ thu được đối với biểu thức Lagrange ‰ Tức là: áp dụng các biểu thức [Eq.12-13] vào biểu thức Lagrange ban đầu ([Eq.11]) để loại bỏ các biến ban đầu (w và b) „ Biểuthu thức đốingi ngẫu LD r 1 r [Eq.17] LD (α) = ∑αi − ∑αiα j yi y j 〈xi ⋅x j 〉 i=1 2 i, j=1 „ Cả hai biểu thức LP và LD đều là các biểu thức Lagrange ‰ Dựa trên cùng một hàm một tiêu – nhưng với các ràng buộc khác nhau ‰ Lờiii giảiitì tìm được, bằng cááhch cực tiểu hóa LP hoặc cực đạihói hóa LD ọ H c Máy – IT 4862 18
10. Tính các giá trị w* và b* „ Gọi SV là tập các vectơ hỗ trợ ‰ SV là tập con của tập r các ví dụ huấn luyện ban đầu →αi>0 đốivới các vectơ hỗ trợ xi →αi=0 đốivới các vectơ không phảilàvectơ hỗ trợ xi „ Sử dụng biểuthức [Eq.12], ta có thể tính đượcgiátrị w* r w* = ∑αi yixi = ∑αi yixi ; bởivì ∀xi ∉ SV: αi=0 i=1 xi∈SV „ Sử dụng biểuthức [Eq.16] và (bấtkỳ) mộtvectơ hỗ trợ xk, ta có . ‰ αk(yk( +bb)*)-1)= 0 ‰ Nhớ rằng αk>0 đốivớimọivectơ hỗ trợ xk . ‰ Vì vậy: (yk( +b*)-1)=0 . ‰ Từđây, ta tính đượcgiátrị b*= yk- ọ H c Máy – IT 4862 20
11. Linear SVM: Khônggp phân tách được(1) „ Phương pháp SVM trong trường hợpcácvídụ phân lớptuyến tính nhưng không thể phân tách được? ‰ Trường hợp phân lớptuyến tính và phân tách đượclàlýtưởng (ít xảyra) ‰ Tập dữ liệucóthể chứa nhiễu, lỗi (vd: mộtsố ví dụ được gán nhãn lớpsai) „ Đốivớitrường hợp phân tách được, bài toán tối ưu: 〈w ⋅w〉 Cựctiểu hóa: 2 Với điềukiện: yi (〈w ⋅xi 〉 + b) ≥1, i =1, 2, , r „ Nếutậpdữ liệuchứa nhiễu, các điềukiệncóthể không được thỏamãn → Không tìm được lời giải (w* và b*)! ọ H c Máy – IT 4862 22
12. Nới lỏng các điều kiện „ Để làm việc với các dữ liệu chứa nhiễu, cần nới lỏng các điều kiện lề (g(margin constraints ) bằng cách sử dụng các biến slack ξi (≥ 0) 〈w⋅xi〉+b ≥ 1−ξi đối với các ví dụ có giá trị yi = 1 〈w⋅xi〉+b ≤ −1+ξi đối với các ví dụ có giá trị yi = -1 „ Đối với một ví dụ nhiễu/lỗi: ξi >1 „ (Σiξi) là giới hạn trên của lỗi của các ví dụ huấn luyện „ Các điều kiện mới đối với trường hợp (phân lớp tuyến tính) không thể phân tách được: yi(〈w⋅xi〉+b) ≥ 1−ξi, ∀i =1 r ξi ≥ 0, ∀i =1 r ọ H c Máy – IT 4862 24
13. Bài toán tối ưu mới 〈w ⋅ w〉 r Cực tiểu hóa: + C ξ ∑ i [Eq.21] 2 i=1 ⎧yi (〈w ⋅ xi 〉 + b) ≥ 1− ξi , ∀i = 1 r Với điều kiện: ⎨ ⎩ξi ≥ 0, ∀i = 1 r „ Bài toán tối ưu mới này được gọi là Soft-margin SVM „ Biểu thức tối ưu Lagrange: [Eq.22] 1 r r r LP = 〈w ⋅ w〉 + C∑ξi − ∑αi[yi (〈w ⋅ xi 〉 + b) −1+ ξi ] − ∑μiξi 2 i=1 i=1 i=1 trong đó αi (≥0) và μi (≥0) là các hệ số nhân Lagrange ọ H c Máy – IT 4862 26
14. Tập điều kiện Karush-Kuhn-Tucker (2) yi ()〈w ⋅xi 〉 + b −1+ξi ≥ 0, ∀i =1 r [Eq.26] [Eq.27] ξi ≥ 0 [Eq.28] αi ≥ 0 μi ≥ 0 [Eq. 29] [Eq.30] αi (yi (〈w ⋅xi 〉 + b)−1+ξi ) = 0 [Eq.31] μiξi = 0 ọ H c Máy – IT 4862 28
15. Biểu thức đối ngẫu rr1 Cực đại hóa: LD (α) = ∑αi − ∑αiα j yi y j 〈xi ⋅x j 〉 i=112 i, j= ⎧ r Với điều kiện: [Eq.32] ⎪∑αi yi = 0 ⎨ i=1 ⎪ ⎩0 ≤ αi ≤ C, ∀i =1 r „ Quan trọng: ξi và các hệ số nhân Lagrange của chúng (μi) không xuất hiện trong biểu thức đối ngẫu → Hàm mụctiêugic tiêu giống hệttnh như đốiiv với bài toán phân lớp tuyến tính phân tách được (separable linear classification)! „ Khác biệt duy nhấtlàtt là tập các ràng buộcmc mới: αi ≤C ọ H c Máy – IT 4862 30
16. Các đặc điểm quan trọng „ Từ các biểu thức [Eq.25-31], ta có thể suy ra các kết luận sau: Nêu αi = 0 thì yi (〈w ⋅xi 〉 + b) ≥1, và ξi = 0 Nêu 0 0 „ Biểu thức [Eq.33] thể hiện một đặc điểm rất quan trọng của SVM ‰ Lời giải được xác định dựa trên rất ít (sparse) các giá trị αi „ Rất nhi ềuvídu ví dụ học nằm ngoài khoảng lề (margin area), và chúng có giá trị αi bằng 0 „ Các ví dụ nằm trên lề (yi(〈w⋅xi〉+b)=1 – chính là các vectơ hỗ trợ), thì có giá trị αi khác khôngg( (0<αi<C) „ Các ví dụ nằm trong khoảng lề (yi(〈w⋅xi〉+b)<1 – là các ví dụ nhiễu/lỗi), thì có giá trị αi khác không (αi=C) ‰ Nếu không có đặc điểm thưa thớt ((psparsit y) nà y, thì phươngpg phá p SVM không thể hiệu quả đối với các tập dữ liệu lớn ọ H c Máy – IT 4862 32
17. Linear SVM – Tổng kết „ Sự phân lớp dựa vào siêu phẳng phân tách „ Siêu phẳng phân tách được xác định dựa trên tập các vectơ hỗ trợ „ Chỉ đốivi với các vect ơ hỗ trợ, thì h ệ số nhân Lagrange của chúng khác 0 ‰ Đối với các ví dụ huấn luyện khác (không phải là các vectơ hỗ trợ)thìh), thì hệ số nhân Lagrange của chúng bằng 0 „ Việc xác định các vectơ hỗ trợ (trong số các ví dụ huấn luyện) đòi hỏi phải giải quyết bài toán tối ưu bậc hai „ Trong biểu thức đối ngẫu (LD) và trong biểu thức biểu diễn siêu phẳng phân tách, các ví dụ huấn luyện chỉ xuất hiện bên trong các tích vô hướng (inner/dot-products) củacáca các vectơ ọ H c Máy – IT 4862 34
18. Chuyển đổi khônggg gian biểu diễn (1) „ Ý tưởng cơ bản là việc ánh xạ (chuyển đổi) biểu diễn dữ liệu từ không g ian ban đầu X sang một khô ng g ian khác F bằng cách áp dụng một hàm ánh xạ phi tuyến φ φ : X → F x a φ(x) „ Trong không gian đã chuyển đổi, tập các ví dụ học ban đầu {(x1, y1), (x2, y2), , (xr, yr)} được biểu diễn (ánh xạ) tương ứng: {(φ(x1), y1), (φ(x2), y2), , (φ(xr), yr)} ọ H c Máy – IT 4862 36
19. Non-linear SVM – Bài toán tối ưu „ Sau quá trình chuyển đổi không gian biểu diễn, bài toán tối ưu: 〈w ⋅w〉 r Cựctic tiểu hóa: LP = + C∑ξi 2 i=1 [Eq.34] ⎧yi ()〈w ⋅φ(xi )〉 + b ≥1−ξi , ∀i =1 r Với điều kiện: ⎨ ⎩ξi ≥ 0, ∀i =1 r „ Bài toán (tối ưu) đối ngẫu: r 1 r Cực đại hóa: L = α − α α y y 〈φ(x )⋅φ(x )〉 D ∑ i 2 ∑ i j i j i j i=1 i, j=1 [Eq.35] ⎧ r Với điều kiện: ⎪∑αi yi = 0 ⎨ i=1 ⎪ ⎩0 ≤ αi ≤ C, ∀i =1 r „ Ranh giới quyết định phân lớp là siêu phẳng phân tách: r [Eq. 36] f (z) = 〈w *⋅φ(z)〉 + b* = ∑αi yi 〈φ(xi )⋅φ(z)〉 + b*) = 0 i=1 ọ H c Máy – IT 4862 38
20. Chuyển đổi khônggg gian – Trở ngại „ Việc chuyển đổi không gian một cách trực tiếp có thể gặp vấn đề về số chiều khônggg gian quá lớn ((y)curse of dimensionality) „ Ngay cả với một không gian ban đầu có số chiều không lớn, một hàm chuyển đổi (ánh xạ) thích hợp có thể trả về một không g ian mớiói có số chiều rấtlt lớn → “thích hợp” ở đây mang ý nghĩa là hàm chuyển đổi cho phép xác định không gian mới mà trong đóót tậppd dữ liệuucóth có thể phân lớp tuyến tính „ Vấn đề: Chi phí tính toán quá lớn đối với việc chuyển đổi không g ian trực tiếp „ Rất may, việc chuyển đổi không gian trực tiếp là không cần thiết ọ H c Máy – IT 4862 40
21. Hàm nhân – Ví dụ „ Hàm nhân đa thức K(x,z)=) = 〈x⋅z〉d [Eq.38] „ Xét hàm nhân đa thức với bậc d=2, đối với 2 vectơ được biểu diễn trongggg không gian 2 chiều: x=(x1,x2) và z=(z1,z2) 2 2 〈x⋅z〉 = (x1z1 + x 2 z 2 ) 2 2 2 2 = x1 z1 + 2x1z1x 2 z 2 + x 2 z 2 2 2 2 2 = 〈(x1 , x 2 , 2x1x 2 )⋅(z1 , z 2 , 2z1z 2 )〉 = 〈φ(x)⋅φ(z)〉 = K(x,z) „ Ví dụ trên thể hiện hàm nhân 〈x⋅z〉2 là một tích vô hướng của 2 vectơ φ(x)và) và φ(z) trong không gian sau chuyển đổi ọ H c Máy – IT 4862 42
22. Kernel function – How to know? „ Làm sao để biết một hàm là hàm nhân hay không – mà không cần thực hiện các bước suy diễn (phân tích) cụ thể như trong ví dụ minh họa? → Làm sao để biết mộtthà hàm c ó p hảiilà là mộttíht tích vô hướng vectơ trong một không gian nào đó? „ Câu hỏi này được trả lời bằng định lý Mercer (Mercer’s theorem) →Nằm ngoài p hạm vi của bài g iảng nàà!y! ọ H c Máy – IT 4862 44
23. Phân lớpbằng SVM – Các vấn đề „ SVM chỉ làm việc với không gian đầu vào là các số thực → Đối với các thuộc tính định danh (),(nominal), cần chuyển các giá trị định danh thành các giá trị số „ SVM chỉ làm việc (thực hiện phân lớp) với 2 lớp → Đốivi với các bài toán phân lớppg gồm nhi ềuul lớp, c ần chuy ển thành mộttt tập các bài toán phân lớp gồm 2 lớp, và sau đó giải quyết riêng rẽ từng bài toán 2 lớp này → Ví dụ: chiến lược “one-against-rest” „ Siêu phẳng phân tách (ranh giới quyết định phân lớp) xác định được bởi SVM thường khó hiểu đối với người dùng ‰ Vấn đề (khó gi ải thích quy ết định phân lớp) này càng nghiêm trọng, nếu các hàm nhân (kernel functions) được sử dụng ‰ SVM thường được dùng trong các bài toán ứng dụng mà trong đó việc giải thích hoạt động (quyết định) của hệ thống cho người dùng không phải là một yêu cầu quan trọng ọ H c Máy – IT 4862 46