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 truyền thông Năm học 2011-2012 CuuDuongThanCong.com https://fb.com/tailieudientucntt Nội dung d môn ô học: h „ Giới thiệu chung g „ Đánh giá hiệu hệ thống học máy „ Các phương pháp học dựa 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 CuuDuongThanCong.com https://fb.com/tailieudientucntt Máy vectơ hỗ trợ - Giới thiệu (1) „ Máy vectơ hỗ trợ (Support vector machine - SVM) đề cử V V Vapnik đồng nghiệp ông vào năm 1970s Nga, sau trở nên tiếng phổ biến vào năm 1990s „ SVM phương pháp phân lớp tuyến tính (linear classifier), với mục đích xác định siêu phẳng (hyperplane) để phân tách hai lớp liệu – ví dụ: lớp ví dụ có nhãn dương (positive) lớp ví dụ có nhãn âm (negative) „ Các hàm nhân (kernel functions), gọi hàm biến đổi (transformation functions), dùng cho trường hợp phân lớp phi tuyến Học Máy – IT 4862 CuuDuongThanCong.com https://fb.com/tailieudientucntt Máy vectơ hỗ trợ - Giới thiệu (2) „ SVM có tảng lý thuyết chặt chẽ – dựa nhiều định lý toán học „ SVM phương pháp tốt (phù hợp) toán phân lớp có khơng gian biểu diễn thuộc tính lớn – đối tượng cần phân lớp biểu diễn tập lớn thuộc tính „ SVM biết ế đến ế số ố phương pháp phân lớp tốt toán phân lớp văn (text/document classification) Học Máy – IT 4862 CuuDuongThanCong.com https://fb.com/tailieudientucntt Máy vectơ hỗ trợ - Giới thiệu (3) Các vectơ ký hiệu chữ đậm nét! „ Biểu Biể diễn diễ tập tậ r víí dụ d huấn h ấ luyện l ệ (training (t i i examples) l ) {(x1, y1), (x2, y2), …, (xr, yr)}, „ „ „ ‰ xi vectơ đầu vào biểu diễn không gian X ⊆ Rn ‰ yi nhãn lớp (giá trị đầu ra), yi ∈ {1,-1} ‰ yi=1: lớp dương (positive); yi=-1: lớp âm (negative) ⎧ nêu 〈 w ⋅ x i 〉 + b ≥ Đối với ví dụ xi: yi = ⎨ ⎩− nêu 〈 w ⋅ x i 〉 + b < SVM xác định hàm phân tách tuyến tính f(x) = 〈w ⋅ x〉 + b ‰ [Eq.1] [Eq.2] w vectơ trọng số ố thuộc tính; b giá trị số ố thực Học Máy – IT 4862 CuuDuongThanCong.com https://fb.com/tailieudientucntt Mặt siêu phẳng phân tách „ Mặt siêu phẳng phân tách ví dụ huấn luyện lớp dương ví dụ huấn luyện lớp âm: 〈w ⋅ x〉 + b = „ Còn gọi ranh giới (bề mặt) định „ Tồn nhiều mặt siêu phẳng phân tách tách Chọn nào? [Liu, 2006] CuuDuongThanCong.com Học Máy – IT 4862 https://fb.com/tailieudientucntt 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 „ Lý thuyết học máy mặt siêu phẳng phân tách tối thiểu hóa giới hạn lỗi (phân lớp) mắc phải [Liu, 2006] CuuDuongThanCong.com Học Máy – IT 4862 https://fb.com/tailieudientucntt SVM – Dữ liệu phân tách tuyến tính „ Giả sử tập liệu (tập ví dụ huấn luyện) phân tách ợ ộ cách tuyến y tính „ Xét ví dụ lớp dương (x+,1) ví dụ lớp âm (x-,-1) gần siêu phẳng phân tách H0 (+b=0) „ Định nghĩa siêu phẳng lề song song với ‰ H+ qua x+, song song với H0 ‰ H- q qua a x-, song song với ới H0 H+: +b = [[Eq.3] q ] H-: < +b = -1 cho: +b ≥ 1, yi = +b ≤ -1,, yi = -1 Học Máy – IT 4862 CuuDuongThanCong.com https://fb.com/tailieudientucntt Tính tốn mức lề (1) „ „ Mức lề (margin) khoảng cách siêu phẳng lề H+ H- Trong hình vẽ nêu trên: ‰ d+ khoảng cách H+ H0 ‰ d- khoảng cách H- H0 ‰ (d+ + d−) mức lề Theo lý thuyết đại số vectơ, khoảng cách (trực giao) từ ột điểm điể xi đến đế mặt ặt siêu iê phẳng hẳ (〈w (〈 ⋅ x〉〉 + b = 0) là: | 〈w ⋅ xi 〉 + b | || w || ||w|| độ dài w: 2 || w ||= < w ⋅ w > = w1 + w2 + + wn Học Máy – IT 4862 CuuDuongThanCong.com [Eq.4] [[Eq.5] q ] https://fb.com/tailieudientucntt Tính tốn mức lề (2) „ Tính tốn d+ – khoảng cách từ x+ đến (〈w ⋅ x〉 + b = 0) ‰ Áp dụng d ng biểu biể thức [Eq.3-4]: [Eq 4] | 〈w ⋅ x+ 〉 + b | |1| d+ = = = || w || || w || || w || „ Tính toán d- – khoảng cách từ x- đến (〈w ⋅ x〉 + b = 0) ‰ „ [Eq.6] Áp dụng biểu thức [Eq.3-4]: | 〈 w ⋅ x − 〉 + b | | −1 | = = d− = || w || || w || || w || Tí h tốn Tính t mức ứ lề [Eq.7] margin = d + + d − = || w || [Eq.8] Học Máy – IT 4862 CuuDuongThanCong.com 10 https://fb.com/tailieudientucntt Ranh ggiới qquyết định p phân lớp p „ Ranh giới định phân lớp siêu phẳng: r 〈 w * ⋅x〉 + b* = ∑ α i yi 〈 x i ⋅ x〉 + b* = i =1 → Rất nhiều ví dụ ụ học ọ xi có g giá trịị αi g 0! ((chính đặc ặ điểm thưa thớt – sparsity – phương pháp SVM) „ Đối với ví dụ cần phân loại z, phân loại bởi: sign(〈w*⋅z〉+b*) „ Cần xác định giá trị phù hợp tham số C (trong hàm tối ưu mục tiêu) → Thường xác định cách sử dụng tập liêu tối ưu (validation set) Học Máy – IT 4862 CuuDuongThanCong.com 33 https://fb.com/tailieudientucntt Linear SVM – Tổng g 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 xác định dựa tập vectơ hỗ trợ „ Chỉ vectơ hỗ trợ, trợ hệ số nhân Lagrange chúng khác ‰ Đối với ví dụ huấn luyện khác (không phải vectơ hỗ trợ) hệ số nhân Lagrange chúng trợ), „ Việc xác định vectơ hỗ trợ (trong số ví dụ huấn luyện) địi hỏi phải giải toán tối ưu bậc hai „ Trong biểu thức đối ngẫu (LD) biểu thức biểu diễn siêu phẳng phân tách, ví dụ huấn luyện xuất bên tích vơ hướng (inner/dot-products) vectơ Học Máy – IT 4862 CuuDuongThanCong.com 34 https://fb.com/tailieudientucntt SVM phân lớp phi tuyến – Non-linear SVM „ Lưu ý: Các cơng thức phương pháp SVM địi hỏi tập liệu phải phân lớp tuyến tính (có/khơng nhiễu) „ Trong nhiều tốn thực tế, tập liệu phân lớp phi tuyến (non-linearly separable) „ Phương pháp phân loại SVM phi tuyến (Non-linear (Non linear SVM): ‰ Bước Chuyển đổi không gian biểu diễn đầu vào ban đầu sang không gian khác (thường có số chiều lớn nhiều) → Dữ liệu biểu diễn không gian (đã chuyển đổi) phân lớp tuyến tính (linearly separable) ‰ „ „ Bước Áp dụng lại công thức bước phương pháp phân lớp SVM tuyến tính Khơng gian biểu diễn ban đầu: Khơng gian đầu vào (input space) Không gian biểu diễn sau chuyển đổi: Không gian đặc trưng (f t (feature space)) Học Máy – IT 4862 CuuDuongThanCong.com 35 https://fb.com/tailieudientucntt Chuyển đổi khôngg gian g biểu diễn (1) „ Ý tưởng việc ánh xạ (chuyển đổi) biểu diễn liệ từ không liệu khô gian i b ban đầ đầu X sang ột không khô gian i khác F cách áp dụng hàm ánh xạ phi tuyến φ φ:X →F x a φ ( x) „ Trong không gian chuyển đổi, tập ví dụ học ban đầu {(x1, y1), (x2, y2), …, (xr, yr)} biểu diễn (ánh xạ) t tương ứ ứng: {(φ(x1), y1), (φ(x2), y2), …, (φ(xr), yr)} Học Máy – IT 4862 CuuDuongThanCong.com 36 https://fb.com/tailieudientucntt Chuyển y đổi khôngg gian g biểu diễn ((2)) [Liu, 2006] • Trong ví dụ này, khơng gian sau chuyển đổi có số chiều khơng gian ban đầu (2 chiều) • Nhưng thông thường, số chiều không gian sau chuyển đổi (feature space) lớn (nhiều) số chiều không gian ban đầu ầ ((input space)) Học Máy – IT 4862 CuuDuongThanCong.com 37 https://fb.com/tailieudientucntt Non-linear SVM – Bài toán tối ưu „ Sau q trình chuyển đổi khơng gian biểu diễn, toán tối ưu: r 〈 w ⋅ w〉 LP = + C ∑ ξi Cực tiểu hóa: Với điều kiện: „ i =1 ⎧ yi (〈 w ⋅ φ (x i )〉 + b ) ≥ − ξ i , ∀i = r ⎨ ⎩ ξ i ≥ 0, ∀i = r [Eq.34] Bài tốn (tối ưu) đối ngẫu: r Cực đại hóa: Với điều kiện: „ r LD = ∑ α i − ∑ α iα j yi y j 〈φ (x i ) ⋅ φ (x j )〉 i , j =1 i =1 ⎧ r ⎪ ∑ α i yi = ⎨ i =1 ⎪⎩0 ≤ α i ≤ C , ∀i = r [Eq.35] Ranh giới định phân lớp siêu phẳng phân tách: r f (z ) = 〈 w * ⋅φ (z )〉 + b* = ∑ α i yi 〈φ (x i ) ⋅ φ (z )〉 + b *) = [Eq 36] [Eq.36] i =1 Học Máy – IT 4862 CuuDuongThanCong.com 38 https://fb.com/tailieudientucntt Chuyển đổi khơngg gian g – Ví dụ „ Xét khơng gian biểu diễn ban đầu có chiều, chọn h hà hàm ánh h xạ từ không khô gian i b ban đầ đầu (2 (2-D) D) sang không gian (3-D) sau: 2 ( x1 , x2 ) a ( x1 , x2 , x1 x2 ) „ Xét ví dụ học (x=(2, (x=(2 3) 3), y=-1) không gian ban đầu (2-D) „ Trong không gian sau chuyển đổi (3-D) (3-D), ví dụ học biểu diễn sau: (φ((x)=(4, ) ( , 9,, 8.49), ), y=-1) y ) Học Máy – IT 4862 CuuDuongThanCong.com 39 https://fb.com/tailieudientucntt Chuyển đổi khôngg gian g – Trở ngại g „ Việc chuyển đổi không gian cách trực tiếp gặp vấn đề số chiều khơng gg gian q lớn (curse ( of dimensionality) y) „ Ngay với khơng gian ban đầu có số chiều không lớn, hàm chuyển đổi (ánh xạ) thích hợp trả khơ gian khơng i ới có ó số ố chiều hiề ất lớn lớ → “thích hợp” mang ý nghĩa hàm chuyển đổi cho phép xác định không gian mà tập liệu phân lớp tuyến tính „ Vấn đề: Chi phí tính tốn q lớn việc chuyển đổi khơ gian không i ttrực tiếp tiế „ Rất may, việc chuyển đổi không gian trực tiếp không cần t ết thiết… Học Máy – IT 4862 CuuDuongThanCong.com 40 https://fb.com/tailieudientucntt Các hàm nhân – Kernel functions „ Trong biểu thức đối ngẫu ([Eq.35]) biểu thức siêu phẳng phân tách ([ p ([Eq.36]): q ]) ‰ Việc xác định trực tiếp (cụ thể) giá trị φ(x) φ(z) không cần thiết ‰ Chỉ cần tính giá trị tích vơ hướng vectơ 〈φ(x)⋅φ(z)〉 → Việc chuyển đổi không gian trực tiếp khơng cần thiết! „ „ Nếu tính tích vơ hướng vectơ 〈φ(x)⋅φ(z)〉 trực tiếp từ vectơ x z, khơng cần phải xác định (không cần biết): ‰ vectơ đặc trưng (trong không gian sau chuyển đổi) φ(x), ‰ hàm chuyển đổi (ánh xạ) φ Trong phương pháp SVM, mục tiêu đạt thông qua việc sử dụng hàm nhân (kernel functions), ký hiệu K K(x z) = 〈φ(x)⋅φ(z)〉 K(x,z) [Eq 37] [Eq.37] Học Máy – IT 4862 CuuDuongThanCong.com 41 https://fb.com/tailieudientucntt Hàm nhân – Ví dụ „ „ Hàm nhân đa thức K(x z) = 〈x⋅z〉d K(x,z) [Eq.38] Xét hàm nhân đa thức với bậc d=2, vectơ biểu diễn g không gg gian chiều: x=(x ( 1,x2) z=(z ( 1,z2) 〈 x ⋅ z〉 = ( x1 z1 + x z ) 2 2 = x1 z1 + x1 z1 x z + x z 2 2 2 = 〈( x1 , x , x1 x ) ⋅ ( z1 , z , z1 z )〉 = 〈φ (x) ⋅ φ (z )〉 = K (x, z ) „ Ví dụ thể hàm nhân 〈x⋅z〉2 tích vơ hướng vectơ φ(x) φ(z) không gian sau chuyển đổi Học Máy – IT 4862 CuuDuongThanCong.com 42 https://fb.com/tailieudientucntt Kernel trick „ Diễn giải chi tiết bước tính tốn ví dụ mang mục đích giải thích (minh họa) „ Trong thực tế, ta khơng cần phải tìm (xác định) hàm ánh xạ φ „ Bởi vì: Ta áp dụng hàm nhân cách trực tiếp →Thay tất giá trị tích vô hướng vectơ 〈φ(x)⋅φ(z)〉 [Eq.35-36] hàm nhân chọn K(x,z) K(x z) (ví dụ: hàm nhân đa thức 〈x 〈x⋅z〉 z〉d [Eq.38]) „ Chiến lược gọi kernel trick! Học Máy – IT 4862 CuuDuongThanCong.com 43 https://fb.com/tailieudientucntt Kernel function – How to know? „ Làm để biết hàm hàm nhân hay không – mà không cần thực bước suy diễn (phân tích) cụ thể ví dụ minh họa? → Là Làm để biết ột hàm hà có ó phải hải ột tích tí h vô ô hướng vectơ không gian đó? „ Câu hỏi trả lời định lý Mercer (Mercer’s theorem) →Nằm Nằ ài phạm h vii ủ giảng iả này! ! Học Máy – IT 4862 CuuDuongThanCong.com 44 https://fb.com/tailieudientucntt Các hàm nhân thườngg dùngg „ Đa thức: K(x,z) = (〈 x ⋅ z〉 + θ ) ; : θ ∈ R,d ∈ N d „ Gaussian RBF (Gaussian radial basis function) K(x,z) = e „ − x−z 2σ ; t : σ > Xích-ma (Sigmoidal) K(x,z) = (β 〈 x ⋅ z〉 − λ) = 1+ e − ( β 〈 x⋅z 〉 − λ ) ; : β,λ ∈ R Học Máy – IT 4862 CuuDuongThanCong.com 45 https://fb.com/tailieudientucntt Phân lớp SVM – Các vấn đề „ SVM làm việc với không gian đầu vào số thực → Đối với thuộc ộ tính định ị danh ((nominal), ), cần chuyển y g giá trịị định ị danh thành giá trị số „ SVM làm việc (thực phân lớp) với lớp → Đối với toán phân lớp gồm nhiều lớp, cần chuyển thành tập toán phân lớp gồm lớp, sau giải riêng rẽ tốn lớp → Ví dụ: chiến lược “one-against-rest” „ Siêu phẳng phân tách (ranh giới định phân lớp) xác định SVM thường khó hiểu người dùng ‰ ‰ Vấn đề (khó giải thích định phân lớp) nghiêm trọng, hàm nhân (kernel functions) sử dụng SVM thường dùng toán ứng dụng mà việc giải thích hoạt động (quyết định) hệ thống cho người dùng yêu cầu ầ quan trọng Học Máy – IT 4862 CuuDuongThanCong.com 46 https://fb.com/tailieudientucntt Tài liệu tham khảo •B Liu Web Data Mining: Exploring Hyperlinks, g Data Springer, p g 2006 Contents, and Usage •C J C Burges A Tutorial on Support Vector Machines for Pattern Recognition Data Mining and Knowledge Discovery, 2(2): 121-167, 1998 Học Máy – IT 4862 CuuDuongThanCong.com 47 https://fb.com/tailieudientucntt ... tập vectơ hỗ trợ „ Chỉ vectơ hỗ trợ, trợ hệ số nhân Lagrange chúng khác ‰ Đối với ví dụ huấn luyện khác (khơng phải vectơ hỗ trợ) hệ số nhân Lagrange chúng trợ) , „ Việc xác định vectơ hỗ trợ. .. 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 CuuDuongThanCong.com https://fb.com/tailieudientucntt Máy vectơ hỗ trợ - Giới thiệu (1) „ Máy vectơ hỗ trợ (Support... https://fb.com/tailieudientucntt Tính giá trị w* b* „ Gọi SV tập vectơ hỗ trợ ‰ SV tập tập r ví dụ huấn luyện ban đầu →αi>0 vectơ hỗ trợ xi →αi=0 vectơ vectơ hỗ trợ xi „ Sử dụng biểu ể thức [Eq.12], ta ể tính