Bài giảng Học máy: Các phương pháp học có giám sát (P6) - Nguyễn Nhật Quang

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:47

Thêm vào BST

Báo xấu

40
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng cung cấp cho người học các kiến thức: Giới thiệu mạng nơron nhân tạo, các ứng dụng điển hình, cấu trúc và hoạt động của một nơron nhân tạo, đầu vào và tổng kết dịch chuyển, hàm tác động - Giới hạn cứng, logic ngưỡng, kiến trúc mạng,... Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Học máy: Các phương pháp học có giám sát (P6) - Nguyễn Nhật Quang

Học Máy (IT 4862) Nguyễn ễ Nhật hậ 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 dung d môn ô học: h Giới thiệu chung g Đá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 Máy vectơ hỗ trợ (Support vector machine) Các phương pháp học không giám sát L cộng Lọc ộ tác tá Học tăng cường Học Máy – IT 4862 2
Máy vectơ hỗ trợ - Giới thiệu (1) Máy vectơ hỗ trợ (Support vector machine - SVM) được đề cử bởi V V. Vapnik và các đồng nghiệp của ông vào những năm 1970s ở Nga, và sau đó đã trở nên nổi tiếng và phổ biến vào những năm 1990s SVM là một phương pháp phân lớp tuyến tính (linear classifier), với mục đích xác định một siêu phẳng (hyperplane) để phân tách hai lớp của dữ liệu – ví dụ: lớp các ví dụ có nhãn dương (positive) và lớp các ví dụ có nhãn âm (negative) Các hàm nhân (kernel functions), cũng được gọi là các hàm biến đổi (transformation functions), được dùng cho các trường hợp phân lớp phi tuyến Học Máy – IT 4862 3
Máy vectơ hỗ trợ - Giới thiệ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ểu diễn 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
Máy vectơ hỗ trợ - Giới thiệu (3) Các vectơ được ký hiệu bởi các chữ đậm nét! Biểu Biể diễn diễ tập tậ r cácá víí dụ d huấn h ấ luyện l ệ (training (t i i examples) l ) {(x1, y1), (x2, y2), …, (xr, yr)}, xi là một vectơ đầu vào được biểu diễn trong không gian X ⊆ Rn yi là một nhãn lớp (giá trị đầu ra), yi ∈ {1,-1} yi=1: lớp dương (positive); yi=-1: lớp âm (negative) ⎧ 1 nêu 〈 w ⋅ x i 〉 + b ≥ 0 [Eq.1] Đối với một ví dụ xi: yi = ⎨ ⎩− 1 nêu 〈 w ⋅ x i 〉 + b < 0 SVM xác định một hàm phân tách tuyến tính f(x) = 〈w ⋅ x〉 + b [Eq.2] w là vectơ trọng số ố các thuộc tính; b là một giá trị số ố thực Học Máy – IT 4862 5
Mặt siêu phẳ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ấn luyện lớp âm: 〈w ⋅ x〉 + b = 0 Còn được gọi là ranh giới (bề mặt) quyết định Tồn tại nhiều mặt siêu phẳng phân tách tách. Chọn cái nào? [Liu, 2006] Học Máy – IT 4862 6
Mặt siêu phẳng có lề cực đại SVM lựa chọn mặt siêu phẳng phân tách có lề (margin) lớn nhất Lý thuyết học máy đã chỉ ra rằng một mặt siêu phẳng phân tách như thế sẽ tối thiểu hóa giới hạn lỗi (phân lớp) mắc phải [Liu, 2006] Học Máy – IT 4862 7
SVM – Dữ liệu phân tách được tuyế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 y 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- đi q qua a x-, và à song song với ới H0 H+: +b = 1 [[Eq.3] q ] H-: < +b = -1 1 sao cho: +b ≥ 1, nếu yi = 1 +b ≤ -1,, nếu yi = -1 Học Máy – IT 4862 8
Tính toán mức lề (1) Mức lề (margin) là khoảng cách giữa 2 siêu phẳng lề H+ và H-. Trong hình vẽ nêu trên: d+ là khoảng cách giữa H+ và H0 d- là khoảng cách giữa H- và H0 (d+ + d−) là mức lề Theo lý thuyết đại số vectơ, khoảng cách (trực giao) từ một ột điểm điể xi đến đế mặt ặt siêu iê phẳng (〈 ⋅ x〉〉 + b = 0) là: hẳ (〈w là | 〈w ⋅ xi 〉 + b | [Eq.4] trong đó ||w|| là độ dài của w: || w || 2 2 2 [[Eq.5] q ] || w ||= < w ⋅ w > = w1 + w2 + ... + wn Học Máy – IT 4862 9
Tính toán mức lề (2) Tính toán d+ – khoảng cách từ x+ đến (〈w ⋅ x〉 + b = 0) Áp dụng d ng các biểu biể thức [Eq.3-4]: [Eq 3 4] | 〈w ⋅ x+ 〉 + b | |1| 1 [Eq.6] d+ = = = || 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ểu thức [Eq.3-4]: | 〈 w ⋅ x − 〉 + b | | −1 | 1 [Eq.7] d− = = = || w || || w || || w || Tí h toán Tính t á mức ứ lề 2 margin = d + + d − = [Eq.8] || w || Học Máy – IT 4862 10
Học SVM – Cực đại hóa mức lề Định nghĩa (Linear SVM – Trường hợp phân tách được) Tập Tậ gồmồ r víí dụd huấn h ấ luyện l ệ có ó thể phân hâ tách tá h tuyến t ế tính tí h D = {(x1,y1), (x2,y2), …, (xr,yr)} SVM học một phân lớp nhằm ằ cực đại hóa mức lề ề Tương đương với việc giải quyết bài toán tối ưu bậc hai sau đây 2 Tìm w và b sao cho: margin = đạt cực đại w Với điều kiện: ệ ⎧〈 w ⋅ x i 〉 + b ≥ 1, nêu y i = 1 ⎨ ; với mọi ví dụ huấn luyện xi (i=1..r) ⎩〈 w ⋅ x i 〉 + b ≤ −1, nêu y i = -1 Học Máy – IT 4862 11
Cực đại hóa mức lề – Bài toán tối ưu Học SVM tương đương với giải quyết bài toán cực tiểu hóa có ràng buộc sau đây 〈 w ⋅ w〉 Cực tiểu hóa: [Eq.9] 2 Với điều kiện: ⎧ 〈 w ⋅ x i 〉 + b ≥ 1, if yi = 1 ⎨ ⎩〈 w ⋅ x i 〉 + b ≤ −1, if yi = −1 …tương đương với 〈 w ⋅ w〉 [Eq 10] [Eq.10] Cực tiểu hóa: 2 Với điều kiện: yi (〈 w ⋅ x i 〉 + b) ≥ 1, ∀i = 1..r Học Máy – IT 4862 12
Lý thuyết tối ưu có ràng buộc (1) Bài toán cực tiểu hóa có ràng buộc đẳng thức: Cực tiểu hóa f(x), f(x) với điều kiện g(x)=0 Điều kiện cần để x0 là một lời giải: ⎧∂ ⎪ ( f(x) + αg (x)) =0 ⎨ ∂x x=x0 ; với α là một hệ số nhân ⎪ g(x) = 0 (multiplier) Lagrange ⎩ Trong trường hợp có nhiều ràng buộc đẳng thức gi(x)=0 (i=1..r), cần một hệ số nhân Lagrange cho mỗi ràng buộc: ⎧∂ ⎛ r ⎞ ⎪ ⎜ ⎨ ∂x ⎝ f(x) + ∑ i =1 α g i i (x) ⎟ ⎠ x=x0 =0 ; với αi là một hệ số nhân ⎪ g (x) = 0 Lagrange g g ⎩ i Học Máy – IT 4862 13
Lý thuyết tối ưu có ràng buộc (2) Bài toán cực tiểu hóa có các ràng buộc bất đẳng thức: Cực tiểu hóa f(x), f(x) với các điều kiện gi(x)≤0 Điều kiện cần để x0 là một lời giải: ⎧∂ ⎛ r ⎞ ⎪ ⎜ ⎨ ∂x ⎝ f(x) + ∑ i =1 α g i i (x) ⎟ ⎠ x=x0 =0 ; với αi ≥ 0 ⎪ g (x) ≤ 0 ⎩ i Hàm r L = f(x) + ∑ αi g i(x) i =1 được gọi là hàm Lagrange Học Máy – IT 4862 14
Giải bài toán cực tiểu hóa có ràng buộc Biểu thức Lagrange r 1 LP (w, b, α ) = 〈 w ⋅ w〉 − ∑ α i [ yi (〈 w ⋅ x i 〉 + b) − 1] [Eq.11] 2 i =1 trong đó αi (≥0) là các hệ số nhân Lagrange Lý thuyết tối ưu chỉ ra rằng một lời giải tối ưu cho [Eq.11] phải thỏa mãn các điều kiện nhất định định, được gọi là các điều kiện Karush-Kuhn-Tucker – là các điều kiện cần (nhưng không phải là các điều kiện đủ) Các điều kiện Karush-Kuhn-Tucker đóng vai trò trung tâm trong cả lý thuyết và ứng dụng của lĩnh vực tối ưu có ràng buộc Học Máy – IT 4862 15
Tập điều kiện Karush-Kuhn-Tucker ∂LP r = w − ∑ αi y i x i = 0 [Eq.12] ∂w i =1 ∂LP r = − ∑ αi y i = 0 [Eq.13] ∂b i =1 yi ( w ⋅ x i + b ) − 1 ≥ 0, ∀x i (i = 1..r ) [E 14] [Eq.14] αi ≥ 0 [Eq.15] αi ( yi ( w ⋅ x i + b ) − 1) = 0 [Eq 16] [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ợ! ố với các ví dụ khác (không phải là các vectơ hỗ trợ) thì αi=0 Đối Học Máy – IT 4862 16
Giải bài toán cực tiểu hóa có ràng buộc Trong trường hợp tổng quát, các điều kiện Karush-Kuhn- Tucker là cần đối với một lời giải tối ưu, ưu nhưng chưa đủ Tuy nhiên, đối với bài toán cực tiểu hóa đang xét có hàm mục tiêu lồi (convex) và các ràng buộc tuyến tính, thì các điề kiện điều kiệ Karush-Kuhn-Tucker K h K h T k là cần ầ và à đủ đối với ới mộtột lời giải tối ưu Giải quyết bài toán tối ưu này vẫn là một nhiệm vụ khó khăn – do sự tồn tại của các ràng buộc bất đẳng thức! Phương pháp Lagrange giải quyết bài toán tối ưu hàm lồi dẫn ẫ đến ế một biểu ể thức đối ố ngẫuẫ (dual) của bài toán tối ố ưu → Dễ giải quyết hơn so với biểu thức cần tối ưu ban đầu (primal) Học Máy – IT 4862 17
Biểu thức đối ngẫu Để thu được biểu thức đối ngẫu từ biểu thức ban đầu: →Gán giá trị bằng 0 đối với các đạo hàm bộ phận của biểu 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ểu thức đối ngẫu LD r 1 r LD (α ) = ∑ α i − ∑ α iα j yi y j 〈 x i ⋅ x j 〉 [Eq.17] 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ời giải iải tì tìm được, đ bằng bằ cách á h cực tiểu tiể hóa hó LP hoặc h ặ cực đại đ i hó hóa LD Học Máy – IT 4862 18
Bài toán tối ưu đối ngẫu r 1 r Cực đại hóa: LD (α ) = ∑ α i − ∑ α iα j yi y j 〈 x i ⋅ x j 〉 i =1 2 i , j =1 [Eq.18] ⎧ r Với điều kiện: ⎪∑ α i yi = 0 ⎨ i =1 ⎪⎩α i ≥ 0, ∀i = 1..1 r Đối với hàm mục tiêu là hàm lồi và các ràng buộc tuyến tính, giá trị cực đại của LD xảy ra tại cùng các giá trị của w, b và αi giúp đạt được giá trị cực tiểu của LP Giải quyết biểu thức [Eq.18], ta thu được các hệ số nhân Lagrange αi (các hệ số αi này sẽ được dùng để tính w và b) Giải quyết biểu thức [Eq.18] cần đến các phương pháp số học (để giải quyết bài toán tối ưu hàm lồi bậc hai có các ràng buộc tuyến tính) → Chi tiết các phương pháp này nằm ngoài phạm vi của bài giảng! Học Máy – IT 4862 19
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 đối với các vectơ hỗ trợ xi →αi=0 đối với các vectơ không phải là vectơ hỗ trợ xi Sử dụng biểu ể thức [Eq.12], ta có thể ể tính được giá trị w* r w* = ∑ α i yi x i = ∑α y x ; i i i bởi vì ∀xi ∉ SV: αi=0 i =1 x i ∈SV Sử dụng biểu thức [Eq.16] và (bất kỳ) một vectơ hỗ trợ xk, ta có αk(yk( (+b*)-1)=0 b ) 1) 0 Nhớ rằng αk>0 đối với mọi vectơ hỗ trợ xk Vì vậy: (yk(+b*)-1)=0 Từ đây, ta tính được giá trị b*= yk- Học Máy – IT 4862 20