Học Máy
(IT 4862)
ễhậ
Nguy
ễ
n N
hậ
t 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
d
ô
h
Nội
d
ung m
ô
n
h
ọc:
Giới thiệu chun
g
g
Đánh giá hiệunăng hệthống họcmáy
Các phương pháp họcdựatrênxácsuất
Các
phương
pháp
học
dựa
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)
Máy
vectơ
hỗ
trợ
(Support
vector
machine)
Các phương pháp học không giám sát
L
ộ
tá
L
ọcc
ộ
ng
tá
c
Họctăng cường
2
Học Máy – IT 4862
Máy vectơhỗtrợ-Giớithiệu(1)
Máy vectơ hỗ trợ (Support vector machine - SVM) được
đề cửbởi V Vapnik và các đồng nghiệpcủa ông vào
đề
cử
bởi
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ủadữliệu
ví dụ:
(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
các
trường
hợp
phân
lớp
phi
tuyến
3
Học Máy – IT 4862
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
đị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ểudiễnthuộc tính lớn
–
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)
(text/document
classification)
4
Học Máy – IT 4862
Máy vectơhỗtrợ-Giớithiệu(3)
Các vectơđượckýhiệubởicácchữđậm nét!
Biể
diễ
tậ
á
í
d
hấ
lệ
(t i i l )
Biể
u
diễ
n
tậ
p
r
c
á
cv
í
d
ụ
h
u
ấ
n
l
uy
ệ
n
(t
ra
i
n
i
ng examp
l
es
)
{(x1, y1), (x2, y2), …, (xr, yr)},
x
i
là
một
vectơ
đầu
vào
được
biểu
diễn
trong
không
gian
X
⊆
R
n
x
i
là
một
vectơ
đầu
vào
được
biểu
diễn
trong
không
gian
X
⊆
R
yilà mộtnhãn lớp(giá trịđầura), yi∈{1,-1}
yi=1: lớpdương (positive); yi=-1: lớpâm (negative)
Đốivớimộtvídụxi:
⎩
⎨
⎧
<+〉⋅〈−
≥+〉⋅〈
=01
01
bnêu
bnêu
y
i
i
ixw
xw [Eq.1]
SVM xác định một hàm phân tách tuyến tính
f(x)= 〈w ⋅x〉+ b
ố
ố
⎩
[Eq.2]
wlà vectơtrọng s
ố
các thuộc tính;
b
là mộtgiátrịs
ố
thực
5
Học Máy – IT 4862