Bài giảng Học máy (IT 4862): Chương 4.5 - Nguyễn Nhật Quang

Học Máy<br /> (IT 4862)<br /> <br /> Nguyễn<br /> ễ Nhật<br /> hậ Quang<br /> quangnn-fit@mail.hut.edu.vn<br /> <br /> Trường Đại học Bách Khoa Hà Nội<br /> Viện Công nghệ thông tin và truyền thông<br /> Năm học 2011-2012<br /> <br /> Nội dung<br /> d<br /> môn<br /> ô học:<br /> h<br /> „<br /> <br /> Giới thiệu chung<br /> g<br /> <br /> „<br /> <br /> Đánh giá hiệu năng hệ thống học máy<br /> <br /> „<br /> <br /> Các phương pháp học dựa trên xác suất<br /> <br /> „<br /> <br /> Các phương pháp học có giám sát<br /> „<br /> <br /> Máy vectơ hỗ trợ (Support vector machine)<br /> <br /> „<br /> <br /> Các phương pháp học không giám sát<br /> <br /> „<br /> <br /> L cộng<br /> Lọc<br /> ộ tác<br /> tá<br /> <br /> „<br /> <br /> Học tăng cường<br /> Học Máy – IT 4862<br /> <br /> 2<br /> <br /> Máy vectơ hỗ trợ - Giới thiệu (1)<br /> „<br /> <br /> Máy vectơ hỗ trợ (Support vector machine - SVM) được<br /> đề cử bởi V<br /> V. Vapnik và các đồng nghiệp của ông vào<br /> những năm 1970s ở Nga, và sau đó đã trở nên nổi tiếng<br /> và phổ biến vào những năm 1990s<br /> <br /> „<br /> <br /> SVM là một phương pháp phân lớp tuyến tính (linear<br /> classifier), với mục đích xác định một siêu phẳng<br /> (hyperplane) để phân tách hai lớp của dữ liệu – ví dụ:<br /> lớp các ví dụ có nhãn dương (positive) và lớp các ví dụ<br /> có nhãn âm (negative)<br /> <br /> „<br /> <br /> Các hàm nhân (kernel functions), cũng được gọi là các<br /> hàm biến đổi (transformation functions), được dùng cho<br /> các trường hợp phân lớp phi tuyến<br /> Học Máy – IT 4862<br /> <br /> 3<br /> <br /> Máy vectơ hỗ trợ - Giới thiệu (2)<br /> „<br /> <br /> SVM có một nền tảng lý thuyết chặt chẽ – dựa trên nhiều<br /> định lý toán học<br /> <br /> „<br /> <br /> SVM là một phương pháp tốt (phù hợp) đối với những bài<br /> toán phân lớp có không gian biểu diễn thuộc tính lớn –<br /> các đối tượng cần phân lớp được biểu diễn bởi một tập<br /> rất lớn các thuộc tính<br /> <br /> „<br /> <br /> SVM đã được biết<br /> ế đến<br /> ế là một trong số<br /> ố các phương pháp<br /> 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<br /> (text/document classification)<br /> <br /> Học Máy – IT 4862<br /> <br /> 4<br /> <br /> Máy vectơ hỗ trợ - Giới thiệu (3)<br /> Các vectơ được ký hiệu bởi các chữ đậm nét!<br /> „ Biểu<br /> Biể diễn<br /> diễ tập<br /> tậ r các<br /> á víí dụ<br /> d huấn<br /> h ấ luyện<br /> l ệ (training<br /> (t i i examples)<br /> l )<br /> {(x1, y1), (x2, y2), …, (xr, yr)},<br /> „<br /> <br /> „<br /> <br /> „<br /> <br /> ‰<br /> <br /> xi là một vectơ đầu vào được biểu diễn trong không gian X ⊆ Rn<br /> <br /> ‰<br /> <br /> yi là một nhãn lớp (giá trị đầu ra), yi ∈ {1,-1}<br /> <br /> ‰<br /> <br /> yi=1: lớp dương (positive); yi=-1: lớp âm (negative)<br /> <br /> ⎧ 1 nêu 〈 w ⋅ x i 〉 + b ≥ 0<br /> Đối với một ví dụ xi: yi = ⎨<br /> ⎩− 1 nêu 〈 w ⋅ x i 〉 + b < 0<br /> SVM xác định một hàm phân tách tuyến tính<br /> f(x) = 〈w ⋅ x〉 + b<br /> ‰<br /> <br /> [Eq.1]<br /> <br /> [Eq.2]<br /> <br /> w là vectơ trọng số<br /> ố các thuộc tính; b là một giá trị số<br /> ố thực<br /> Học Máy – IT 4862<br /> <br /> 5<br /> <br />