Học Máy (IT 4862)
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
Nguyễn Nhật Quang hậ ễ
Nội dung môn học: Nội d
ô h
(cid:132) Giới thiệu chungg
(cid:132) Đánh giá hiệu năng hệ thống học máy
(cid:132) Các phương pháp học dựa trên xác suất (cid:132) Các phương pháp học dựa trên xác suất
(cid:132) Các phương pháp học có giám sát
(cid:132) Máy vectơ hỗ trợ (Support vector machine) (cid:132) Máy vectơ hỗ trợ (Support vector machine)
(cid:132) Các phương pháp học không giám sát
(cid:132) Lọc cộng tác tá ộ
L
(cid:132) Học tăng cường
Học Máy – IT 4862
2
Máy vectơ hỗ trợ - Giới thiệu (1)
(cid:132) Máy vectơ hỗ trợ (Support vector machine - SVM) được đề cử bởi V. Vapnik và các đồng nghiệp củ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
(cid:132) 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ụ: ví dụ: (hyperplane) để phân tách hai lớp của dữ liệu lớp các ví dụ có nhãn dương (positive) và lớp các ví dụ có nhãn âm (negative)
(cid:132) 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
Học Máy – IT 4862
3
Máy vectơ hỗ trợ - Giới thiệu (2)
(cid:132) 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
(cid:132) 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 – 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
ế ế
ố
(cid:132) 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)
Học Máy – IT 4862
4
Máy vectơ hỗ trợ - Giới thiệu (3)
í d h ấ l ệ (t
Biể diễ tậ
á
i
i
l
(cid:132) Các vectơ được ký hiệu bởi các chữ đậm nét! (cid:132) Biểu diễn tập r các ví dụ huấn luyện (training examples) )
{(x1, y1), (x2, y2), …, (xr, yr)},
(cid:137) xi là một vectơ đầu vào được biểu diễn trong không gian X ⊆ Rn (cid:137) xi là một vectơ đầu vào được biểu diễn trong không gian X ⊆ R (cid:137) yi là một nhãn lớp (giá trị đầu ra), yi ∈ {1,-1} (cid:137) yi=1: lớp dương (positive); yi=-1: lớp âm (negative)
i
y
=
(cid:132) Đối với một ví dụ xi:
i
1 1
nêu nêu
0 0
−
〈 〈
[Eq.1]
xw ⋅ xw ⋅
b ≥+〉 b <+〉
i
⎧ ⎨ ⎩ ⎩
(cid:132) SVM xác định một hàm phân tách tuyến tính
f(x) = 〈w ⋅ x〉 + b
[Eq.2]
(cid:137) 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
(cid:132) 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: dương và các ví dụ huấn luyện lớp âm:
〈w ⋅ x〉 + b = 0 〈w x〉 + b = 0
(cid:132) Còn được gọi là ranh giới (bề mặt) quyết định
(cid:132) Tồn tại nhiều mặt siêu phẳng phân tách. Chọn cái nào? Tồn tại nhiều mặt siêu phẳng phân 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
(cid:132) SVM lựa chọn mặt siêu phẳng phân tách có lề (margin) lớn nhất
(cid:132) Lý thuyết học máy đã chỉ ra rằng một mặt siêu phẳng phân tách như (cid:132) Lý thuyết học máy đã chỉ ra rằng một mặt siêu phẳng phân tách như
[Liu, 2006]
Học Máy – IT 4862
7
thế sẽ tối thiểu hóa giới hạn lỗi (phân lớp) mắc phải
SVM – Dữ liệu phân tách được tuyến tính
(cid:132) 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
ợ
ộ
y
(cid:132) 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 (
(cid:132) Định nghĩa 2 siêu phẳng lề song song với nhau
(cid:137) H+ đi qua x+, và song song với H0 (cid:137) H- đi qua x- , và song song với H0 à song song ới H H đi q a
[ q ]
[Eq.3] >+b H+:
sao cho:
nếu yi = 1
i
Học Máy – IT 4862
8
Tính toán mức lề (1)
(cid:132) 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: và H Trong hình vẽ nêu trên: (cid:137) d+ là khoảng cách giữa H+ và H0 (cid:137) d- là khoảng cách giữa H- và H0 (cid:137) (d+ + d−) là mức lề
ột điể
hẳ
đế
ặt
iê
(cid:132) Theo lý thuyết đại số vectơ, khoảng cách (trực giao) từ một điểm xi đến mặt siêu phẳng (〈w ⋅ x〉 + b = 0) là: 0) là
|
(〈 | 〈
[Eq.4]
b 〉 b xw ⋅ i +〉 || w || || ||
2
2
2
trong đó ||w|| là độ dài của w:
|| ||
[ q ] [Eq.5]
w w
|| || <= <=
ww ww ⋅ ⋅
=> =>
+ +
... ++ ++
w w 1
w w 2
nw w
Học Máy – IT 4862
9
Tính toán mức lề (2)
(cid:132) Tính toán d+ – khoảng cách từ x+ đến (〈w ⋅ x〉 + b = 0)
+
(cid:137) Áp dụng các biểu thức [Eq.3-4]: Áp d ng các biể thức [Eq 3 4] | |
b
〈
d
=
=
=
+
|| ||
|| ||
|| ||
|| ||
[Eq.6]
xw ⋅ || || w
|1| w
1 w
+〉 || || (cid:132) Tính toán d- – khoảng cách từ x- đến (〈w ⋅ x〉 + b = 0)
(cid:137) Áp dụng các biểu thức [Eq.3-4]:
−
|
|
b
〈
d
=
=
=
−
[Eq.7]
xw ⋅ || w
+〉 ||
|1| − w || ||
1 w
||
||
(cid:132) Tính toán mức lề ứ lề
Tí h t á
margin
d
d
=
+
=
−
+
[Eq.8]
2 || w || w
|| ||
Học Máy – IT 4862
10
Học SVM – Cực đại hóa mức lề
í d h ấ l ệ
Tậ
ồ
Định nghĩa (Linear SVM – Trường hợp phân tách được) (cid:132) Tập gồm r ví dụ huấn luyện có thể phân tách tuyến tính ó thể hâ tá h t ế tí h
D = {(x1,y1), (x2,y2), …, (xr,yr)}
(cid:132) SVM học một phân lớp nhằm cực đại hóa mức lề ề
ằ
(cid:132) Tương đương với việc giải quyết bài toán tối ưu bậc
hai sau đây hai sau đây
(cid:137) Tìm w và b sao cho: đạt cực đại
margin
=
2 w
(cid:137) Với điều kiện:
,1
ệ
i
nêu ,1
y = i nêu y
1 ; -1
với mọi ví dụ huấn luyện xi (i=1..r)
xw ⋅ xw ⋅
b ≥+〉 b −≤+〉
=
i
i
〈 ⎧ ⎨ 〈 ⎩
Học Máy – IT 4862
11
Cực đại hóa mức lề – Bài toán tối ưu
(cid:132) Học SVM tương đương với giải quyết bài toán cực tiểu
〈
〉
Cực tiểu hóa:
,1
yif
1
=
i
i
Với điều kiện:
,1
yif
[Eq.9]
hóa có ràng buộc sau đây hóa có ràng buộc sau đây ww ⋅ 2 xw 〈 ⋅ xw ⋅
b ≥+〉 b −≤+〉
1 −=
i
i
⎧ ⎨ 〈 ⎩
(cid:132) …tương đương với
〉 〉
Cực tiểu hóa: Cực tiểu hóa:
b
1.. r
y
(
+〉
,1) ≥
i =∀
[Eq.10] [Eq 10]
〈 ww 〈 ⋅ 2 xw ⋅ 〈
Với điều kiện:
i
i
Học Máy – IT 4862
12
Lý thuyết tối ưu có ràng buộc (1)
(cid:132) 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), với điều kiện g(x)=0 Cực tiểu hóa f(x) với điều kiện g(x)=0
(cid:132) Điều kiện cần để x0 là một lời giải:
x f( )
αg
+
=
(
) (x )
0 ;
với αlà một hệ số nhân (multiplier) Lagrange
0
0xx =
=
⎧ ∂ ⎧ ∂ ⎪ x ∂ ⎨ ⎪ x )g( ⎩
(cid:132) 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(
=
+
i
x )(gα i
∑
0 ;
với αi là một hệ số nhân Lagrange
g
g
i 1 = 0 0
⎞ ⎟ ⎠
0xx =
∂ ⎛ ⎜ x ∂ ⎝ =)(gi x )(
⎧ ⎪ ⎨ ⎪ ⎪ ⎩ ⎩
Học Máy – IT 4862
13
Lý thuyết tối ưu có ràng buộc (2)
(cid:132) 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), với các điều kiện gi(x)≤0 Cực tiểu hóa f(x) với các điều kiện g (x)≤0
(cid:132) Điều kiện cần để x0 là một lời giải:
r
x f( )
=
+
i
x )(gα i
∑
0 ;
với αi ≥ 0
i 1 =
0 0
⎞ ⎟ ⎠
0xx =
∂ ⎛ ⎜ x ∂ ⎝ ≤)(gi x )( ≤
⎧ ⎪ ⎨ ⎪ ⎪ ⎩ ⎩
(cid:132) Hàm
r
L
x ) f(
=
+
x )(gα i
i
∑
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
(cid:132) Biểu thức Lagrange
r
(
)
[Eq.11]
, , αw b
[
y
(
b
ww ⋅
−〉
〈
xw ⋅
+〉
]1) −
i
L P
α i
i
∑
1 〈= 2
i
1 =
trong đó αi (≥0) là các hệ số nhân Lagrange
(cid:132) 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, được gọi là các phải thỏa mãn các điều kiện nhất đị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 đủ)
(cid:132) 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 có ràng buộc
Học Máy – IT 4862
15
Tập điều kiện Karush-Kuhn-Tucker
r
[Eq.12]
w
0
=
−
=
ix
yα i
i
∑
1i 1 i =
r
0
−=
=
yα i
i
∑
i
[Eq.13]
b b
i ( (
..r )1 )1
[Eq.14] [E 14]
1 = x ,01 01 ∀ ∀≥−+
=
) )
i
i
) 0 ) 0 ) ) + b 1 =−+ 1 = b
[Eq.15]
L ∂ P w ∂ L ∂ P b ∂ ( ( yi xw ⋅ 0≥iα ( ( ( ( yα yα i
i
ixw xw ⋅
(cid:132) [Eq.14] chính là tập các ràng buộc ban đầu (cid:132) Điều kiện bổ sung [Eq.16] chỉ ra rằng chỉ những ví dụ (điểm dữ liệu)
[Eq.16] [Eq 16]
(cid:132) Đố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
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ợ! ố
Giải bài toán cực tiểu hóa có ràng buộc
(cid:132) 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, nhưng chưa đủ Tucker là cần đối với một lời giải tối ưu nhưng chưa đủ
h K h T k
à đủ đối ới
là ầ
(cid:132) 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ều kiện Karush-Kuhn-Tucker là cần và đủ đối với một lời điề kiệ K ột lời giải tối ưu
(cid:132) Giải quyết bài toán tối ưu này vẫn là một nhiệm vụ khó (cid:132) 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!
(cid:132) 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) (primal)
Học Máy – IT 4862
17
Biểu thức đối ngẫu
(cid:132) Để 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 →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)
(cid:137) Tức là: áp dụng các biểu thức [Eq.12-13] vào biểu thức Lagrange
→Sau đó, áp dụng các quan hệ thu được đối với biểu thức Lagrange
ể ể
r
ban đầu ([Eq.11]) để loại bỏ các biến ban đầu (w và b)
[Eq.17]
)( α
−
〈
〉
α i
L D
yy i
j
xx ⋅ i
j
(cid:132) Biểu thức đối ngẫu LD (cid:132) Biểu thức đối ngẫu L r ∑ ∑ =
1 2
, ji ji ,
i i
αα j i 1 1 =
1 1 =
tiể hó L h ặ
iải tì
á h
Lời
bằ
đ
(cid:132) Cả hai biểu thức LP và LD đều là các biểu thức Lagrange (cid:137) 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 (cid:137) Lời giải tìm được, bằng cách cực tiểu hóa LP hoặc cực đại hóa LD đ i hó L
Học Máy – IT 4862
18
Bài toán tối ưu đối ngẫu
r
r
α )(
−
〈
〉
Cực đại hóa:
L D
α i
yy i
j
i xx ⋅
j
= ∑
∑
1 2
i i
, ji ji
αα j i 1 1 = =
r
0
i
Với điều kiện:
1.. 1 r
i
1 1 = = ⎧ =∑ y α ⎪ i ⎨ i 1 = ⎪⎩ ⎪⎩ ,0α i 0 i ∀≥ =∀≥
[Eq.18] [Eq.18]
(cid:131) Đố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 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
(cid:131) 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) (các hệ số αi này sẽ được dùng để tính w và b)
(cid:131) 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)
Học Máy – IT 4862
19
→ Chi tiết các phương pháp này nằm ngoài phạm vi của bài giảng! → Chi tiết các phương pháp này nằm ngoài phạm vi của bài giảng!
Tính các giá trị w* và b*
(cid:132) Gọi SV là tập các vectơ hỗ trợ
(cid:137) SV là tập con của tập r các ví dụ huấn luyện ban đầu (cid:137) 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
(cid:132) Sử dụng biểu thức [Eq.12], ta có thể tính được giá trị w*
ể
ể
r
w*
y
x
y
x
;
=
=
α i
i
i
i
i
bởi vì ∀xi ∉ SV: αi=0
∑
∑
i i
α i SV SV
1 1 =
∈
ix
(cid:132) Sử dụng biểu thức [Eq.16] và (bất kỳ) một vectơ hỗ trợ xk, ta có
(cid:137) αk(yk(
Học Máy – IT 4862
20
Ranh giới quyết định phân lớp
g
y
[Eq.19] [Eq.19]
xw x*w
x ) f( f( ) x
b b*
b b*
+〉 +〉⋅
+〉 +〉⋅
0 0=
〈 〈=
=
〈 〈
i xx i xx
yα yα i i
i i
(cid:132) Ranh giới quyết định phân lớp được xác định bởi siêu phẳng: ∑ ∑
SV
∈
ix
(cid:132) Đối với một ví dụ cần phân lớp z, cần tính giá trị:
sign(
[Eq.20]
z*w
b*)
b*
〈
+〉⋅
=
〈
+〉⋅
yα i
i
i zx
∑
∈SV
⎛ ⎛ ⎜ sign ⎜ ⎝
⎞ ⎞ ⎟ ⎟ ⎠
ix → Nếu biểu thức [Eq.20] trả về giá trị 1, thì ví dụ z được phân vào lớp → Nếu biểu thức [Eq 20] trả về giá trị 1 thì ví dụ z được phân vào lớp có nhãn dương (positive); ngược lại, được phân vào lớp có nhãn âm (negative)
(cid:132) Việc phân lớp này:
(cid:137) Chỉ phụ thuộc vào các vectơ hỗ trợ g (cid:137) Chỉ cần giá trị tích vô hướng (tích trong) của 2 vectơ (chứ không
g ( g) g ( ị
Học Máy – IT 4862
21
cần biết giá trị của 2 vectơ đấy)
Linear SVM: Không phân tách được(1) g p
(cid:132) Phương pháp SVM trong trường hợp các ví dụ phân lớp tuyến
tính nhưng không thể phân tách được?
(cid:137) Trường hợp phân lớp tuyến tính và phân tách được là lý tưởng (ít
(cid:137) Tập dữ liệu có thể chứa nhiễu, lỗi (vd: một số ví dụ được gán nhãn
xảy ra)
ợ g ập ụ ộ ệ ( ,
〉 〉
〈 〈
lớp sai)
Cực tiểu hóa:
2,1, 2,1,
..., ...,
b b
y y
r r
( (
Với điều kiện:
(cid:132) Đối với trường hợp phân tách được, bài toán tối ưu: ww ⋅ 2 xw xw 〈 〈 ⋅
,1) ,1) i i ≥ ≥
+〉 +〉
=
i i
i i
(cid:132) Nếu tập dữ liệu chứa nhiễu, các điều kiện có thể không được
thỏa mãn → Không tìm được lời giải (w* và b*)! * à b*)! Khô
Học Máy – IT 4862
22
tì đ iải ( lời
Linear SVM: Không phân tách được (2) g p
Hai ví dụ nhiều xa và xb được gán nhãn lớp sai
[Liu, 2006]
Học Máy – IT 4862
23
Nới lỏng các điều kiện
g
ụ g
g
)
(cid:132) Để 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ề (margin constraints) bằng cách sử dụng các biến slack g ( ệ ξi (≥ 0)
〈w⋅xi〉+b ≥ 1−ξi đối với các ví dụ có giá trị yi = 1 đối với các ví dụ có giá trị yi = -1 ố 〈w⋅xi〉+b ≤ −1+ξi
(cid:132) Đối với một ví dụ nhiễu/lỗi: ξi >1 (cid:132) (Σiξi) là giới hạn trên của lỗi của các ví dụ huấn luyện
(cid:132) 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 ξ 0 ∀i 1
Học Máy – IT 4862
24
Tích hợp lỗi trong hàm mục tiêu
(cid:132) Cần phải tích hợp lỗi trong hàm tối ưu mục tiêu
(cid:132) Bằng cách gán giá trị chi phí (cost) cho các lỗi, và tích á lỗi à tí h
iá t ị hi hí (
á h á
t) h
Bằ hợp chi phí này trong hàm mục tiêu mới:
r r
Cực tiểu hóa: Cực tiểu hóa:
〉 〉
〈 〈
k
C
(
)
+
ξ i
∑
ww ⋅ 2
i
1
=
g ) (
trong đó C (>0) là tham số xác định mức độ chi phí (penalty y ( degree) đối với các lỗi
(cid:132) k =1 thường được sử dụng
(cid:137) Lý do (ưu điểm): Thu được biểu thức đối ngẫu (dual formulation) đơn giản hơn – không chứa ξi và các hệ số nhân Lagrange của chúng
Học Máy – IT 4862
25
→ Giá trị C càng lớn, thì mức độ chi phí càng cao đối với các lỗi
Bài toán tối ưu mới
r
〈
〉
Cực tiểu hóa:
C
+
iξ
∑
[Eq.21] [Eq.21]
ww ⋅ 2 2
(
,
1)
1..
r
〈
Với điều kiện:
xw ⋅ ,0 0
−≥ r r 1.. 1
ξ i
i =∀
≥ ≥
1 i = b +〉 i i i =∀ =∀
y i iξ ξ
⎧ ⎨ ⎩ ⎩
(cid:132) Bài toán tối ưu mới này được gọi là Soft-margin SVM
(cid:132) Biểu thức tối ưu Lagrange:
r
r
r
C C
[ [
y y
( (
b b
1) 1)
] ]
[Eq.22]
ww ww ⋅ ⋅
+〉 +〉
〈 〈
xw xw ⋅ ⋅
+〉 +〉
+ +−
−
α α i
i
i
ξ ξ i
ξμ ξμ i i
L L P
∑∑ ∑∑ ξ ξ − i
∑ ∑
1 〈= 〈= 2
i
i
i
1 =
1 =
1 =
trong đó αi (≥0) và μi (≥0) là các hệ số nhân Lagrange
Học Máy – IT 4862
26
Tập điều kiện Karush-Kuhn-Tucker (1)
p
r
[Eq.23] [Eq 23]
w
y
0 0
=
−
=
α i
i
ix
∑ ∑
PL ∂ P w ∂
i
1 =
r
y
0
−=
=
α i
i
∑
L ∂ ∂ P b ∂
i
1 =
[Eq.24]
,0
..1 r
C −=
=
i =∀
μα − i
i
L ∂ P i∂ξ ∂ ξ
Học Máy – IT 4862
27
[Eq.25]
Tập điều kiện Karush-Kuhn-Tucker (2)
p
y
b
,0
..1 r
+〉
1 +−
≥
i =∀
( 〈
)
i
[Eq.26]
ixw ⋅
ξ i
0≥iξ
[Eq.27]
0≥iα
[Eq.28]
0≥iμ 0≥μ
[Eq.29] [Eq 29]
y
b
+〉
1 +−
( (
( ( 〈
) )
) ) 0 =
α i
i
[Eq.30]
ixw ⋅
ξ i
iξμ
0=i
Học Máy – IT 4862
28
[Eq.31]
Chuyển về biểu thức đối ngẫug
ợ ,
(cid:132) Giống như với trường hợp dữ liệu có thể phân tách ạ g
g
g
g
y
được, chúng ta chuyển biểu thức Lagrange từ dạng ban đầu (primal formulation) về dạng đối ngẫu (dual formulation)
(cid:137) Gán giá trị bằng 0 cho các đạo hàm bộ phận của biểu thức (cid:137) Gán giá trị bằng 0 cho các đạo hàm bộ phận của biểu thức Lagrange ([Eq.22]) đối với các biến ban đầu (w, b, ξi)
(cid:137) Thay thế các kết quả thu được vào biểu thức Lagrange ban đầu
→ Sử dụng các kết quả của các biểu thức [Eq.23-25] để thay thế ế ế ể ể
ó C
(cid:132) Từ biểu thức [Eq.25], ta có: C - αi - μi = 0, 0
Từ biể thứ [E 25] t (cid:137) và bởi vì: μi ≥0, (cid:137) nên ta suy ra điều kiện: αi ≤C (cid:137) nên ta suy ra điều kiện: α ≤C
Học Máy – IT 4862
29
vào trong biểu thức Lagrange ban đầu [Eq.22]
Biểu thức đối ngẫug
r
r
Cực đại hóa:
α )(
−
〈
〉
i xx ⋅
j
L D
α i
yy i
j
= ∑
1 ∑2 2
ji ,
i
1 =
αα i j 1 =
r
Với điều kiện:
0
i
,
..1 r
i =∀
⎧ =∑ y α ⎪ i ⎨ ⎨ 1 i = ⎪⎩ 0 Ci α ≤ ≤
(cid:132) 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ục tiêu giống hệt như đối với bài toán phân lớp → Hàm mục tiêu giống hệt như đối với bài toán phân lớp
tuyến tính phân tách được (separable linear classification)!
(cid:132) Khác biệt duy nhất là tập các ràng buộc mới: αi ≤C (cid:132) Khác biệt duy nhất là tập các ràng buộc mới: αi ≤C
Học Máy – IT 4862
30
[Eq.32]
Tìm lời giải cho các biến ban đầu
(cid:132) Bài toán đối ngẫu [Eq.32] được giải quyết bằng 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)
ế
(cid:132) Các giá trị (hệ số nhân Lagrange) αi lời giải được sử dụng để
tính toán w và b tính toán w* và b* (cid:137) w* được xác định sử dụng biểu thức [Eq.23]
(cid:137) b* được xác định sử dụng các điều kiện bổ sung Karush-Kuhn- Tucker trong [Eq.30-31] …nhưng, có vấn đề: ξi chưa biết! ế
(cid:132) Để tính được b*
(cid:137) Từ [Eq.25] và [Eq.31], ta suy ra được: ξi=0 nếu αi ề ấ (cid:137) Đến đây, việc tính toán b tương tự như với trường hợp phân lớp
(cid:137) Đến đây, việc tính toán b* tương tự như với trường hợp phân lớp (0<αk Học Máy – IT 4862 31 tuyến tính phân tách được! (cid:132) Từ các biểu thức [Eq.25-31], ta có thể suy ra các kết luận sau: Nêu 0 thì b 0 = ≥ = < Nêu
Nêu C
thì y
yi
i
thì
y 0
0 α
i
i
0
α
<
i
C
= [Eq.33] =
> (
〈 α
i i ,
và
,1
ξ
ξ
i
i
)
b
,1
và
ξ
=
i
,1
và
ξ
i (cid:132) Biểu thức [Eq.33] thể hiện một đặc điểm rất quan trọng của SVM (cid:137) Lời giải được xác định dựa trên rất ít (sparse) các giá trị αi (cid:132) Rất nhiều ví dụ học nằm ngoài khoảng lề (margin area), và chúng có giá
(cid:132) Rất nhiều ví dụ học nằm ngoài khoảng lề (margin area) và chúng có giá trị αi bằng 0 (cid:132) Các ví dụ nằm trên lề (yi(〈w⋅xi〉+b)=1 – chính là các vectơ hỗ trợ), thì có g ( ị )
giá trị αi khác không (0<αi i i (cid:132) 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) g p p
(cid:137) Nếu không có đặc điểm thưa thớt (sparsity) này, thì phương pháp ( p y) g ặ p y Học Máy – IT 4862 32 SVM không thể hiệu quả đối với các tập dữ liệu lớn (cid:132) Ranh giới quyết định phân lớp chính là siêu phẳng: r b
*
*
b y 〈
〈 +〉⋅
〉 = 〈
〈 +〉⋅
〉 b
*
0*
b
= α
i i i
1
=
ụ ọ g ặ ( ị i → Rất nhiều ví dụ học xi có giá trị αi bằng 0! (chính là đặc
g
điểm thưa thớt – sparsity – của phương pháp SVM) (cid:132) Đối với một ví dụ cần phân loại z, nó được phân loại bởi: sign(〈w*⋅z〉+b*) (cid:132) Cần xác định giá trị phù hợp của tham số C (trong hàm
(cid:132) Cần xác định giá trị phù hợp của tham số C (trong hàm tối ưu mục tiêu) → Thường được xác định bằng cách sử dụng một tập dữ liêu tối Học Máy – IT 4862 33 ưu (validation set)
ưu (validation set) (cid:132) Sự phân lớp dựa vào siêu phẳng phân tách (cid:132) Siêu phẳng phân tách được xác định dựa trên tập các vectơ ẳ (cid:132) Chỉ đối với các vectơ hỗ trợ, thì hệ số nhân Lagrange của
(cid:132) Chỉ đối với các vectơ hỗ trợ thì hệ số nhân Lagrange của chúng khác 0
(cid:137) Đối với các ví dụ huấn luyện khác (không phải là các vectơ hỗ (cid:132) 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 (cid:132) 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ủa các vectơ
trong các tích vô hướng (inner/dot-products) của các vectơ Học Máy – IT 4862 34 trợ), thì hệ số nhân Lagrange của chúng bằng 0
trợ) thì hệ số nhân Lagrange của chúng bằng 0 SVM phân lớp phi tuyến – Non-linear SVM (cid:132) Lưu ý: Các công thức trong phương pháp SVM đòi hỏi tập dữ liệu phải (cid:132) Trong nhiều bài toán thực tế, thì các tập dữ liệu có thể là phân lớp phi có thể phân lớp tuyến tính (có/không nhiễu) (cid:132) Phương pháp phân loại SVM phi tuyến (Non linear SVM):
(cid:132) Phương pháp phân loại SVM phi tuyến (Non-linear SVM): (cid:137) Bước 1. Chuyển đổi không gian biểu diễn đầu vào ban đầu tuyến (non-linearly separable) phân lớp tuyến tính (linearly separable) (cid:137) Bước 2. Áp dụng lại các công thức và các bước như trong sang một không gian khác (thường có số chiều lớn hơn nhiều)
→ Dữ liệu được biểu diễn trong không gian mới (đã chuyển đổi) có thể
→ Dữ liệu được biểu diễn trong không gian mới (đã chuyển đổi) có thể (cid:132) Không gian biểu diễn ban đầu: Không gian đầu vào (input space)
(cid:132) Không gian biểu diễn sau khi chuyển đổi: Không gian đặc trưng phương pháp phân lớp SVM tuyến tính
phương pháp phân lớp SVM tuyến tính Học Máy – IT 4862 35 (feature space)
(f
) t ột khô đầ X b i (cid:132) Ý tưởng cơ bản là việc ánh xạ (chuyển đổi) biểu diễn dữ
liệu từ không gian ban đầu X sang một không gian khác F
khá F
i
liệ từ khô
bằng cách áp dụng một hàm ánh xạ phi tuyến φ (cid:132) 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:
t ứ {(φ(x1), y1), (φ(x2), y2), …, (φ(xr), yr)} Học Máy – IT 4862 36 [Liu, 2006] • Trong ví dụ này, không gian sau chuyển đổi vẫn là có số chiều bằng không gian ban đầu (2 chiều)
chiều bằng không gian ban đầu (2 chiều) • Nhưng thông thường, số chiều của không gian sau chuyển
đổi (feature space) lớn hơn (nhiều) số chiều của không gian
ban đầu (input space)
) ầ ( Học Máy – IT 4862 37 r (cid:132) Sau quá trình chuyển đổi không gian biểu diễn, bài toán tối ưu:
〉 〈 C + = L
P
P ξ
ξ
i
i Cực tiểu hóa:
Cực tiểu hóa: y , r
..1 i
=∀ [Eq.34] ∑
∑
i
1
=
)
b
1
−≥ )
+〉
r
..1 ξ
i Với điều kiện: ⎧
⎨
⎩ r ( = − ⋅ )
〉 L
D α
i yy
i j Cực đại hóa: (cid:132) Bài toán (tối ưu) đối ngẫu:
r
∑ ∑ 1
2
2 i ,
ji 1
= αα
i
j
1
= r [Eq.35] 0 i , r
r
..1
1 i
i
=∀
=∀ ⎧
=∑
y
α
⎪
i
⎨
1
i
=
0⎪⎩
⎪⎩
Ciα
C
0
α
≤
≤
≤
≤ (cid:132) Ranh giới quyết định phân lớp là siêu phẳng phân tách: r Với điều kiện: f
f [Eq.36]
[Eq 36] b
*
b y
y )
) b
b 〈=
〈= φ
⋅
⋅
φ +〉
+〉 =
= 〈
〈 ⋅
⋅ +〉
+〉 0)*
0)
=
= i i ∑
∑ =i
1 Học Máy – IT 4862 38 (cid:132) Xét không gian biểu diễn ban đầu có 2 chiều, và chúng ta
i đầ (2 D) từ khô á h hà b chọn hàm ánh xạ từ không gian ban đầu (2-D) sang
h
không gian mới (3-D) như sau: 2
2 2
2 (
( )
) (
( , x 2,
2 )
) xx
,
1 2 x
1 2 xx
21 a (cid:132) Xét ví dụ học (x=(2, 3), y=-1) trong không gian ban đầu
(cid:132) Xét ví dụ học (x=(2 3) y=-1) trong không gian ban đầu (2-D) (cid:132) Trong không gian sau chuyển đổi (3-D), thì ví dụ học này
(cid:132) Trong không gian sau chuyển đổi (3-D) thì ví dụ học này được biểu diễn như sau: ), y )
(φ(x)=(4, 9, 8.49), y=-1)
,
(φ( ) ( , Học Máy – IT 4862 39 (cid:132) 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ông gian quá lớn (curse of dimensionality)
y) g g q ( (cid:132) 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 gian mới có số chiều rất lớn
khô ới ó ố hiề ất lớ i → “thích hợp” ở đây mang ý nghĩa là hàm chuyển đổi cho phép (cid:132) Vấn đề: Chi phí tính toán quá lớn đối với việc chuyển đổi không gian trực tiếp
khô tiế t i (cid:132) Rất may, việc chuyển đổi không gian trực tiếp là không cần thiết…t ết Học Máy – IT 4862 40 xác định không gian mới mà trong đó tập dữ liệu có thể phân lớp
xác định không gian mới mà trong đó tập dữ liệu có thể phân lớp
tuyến tính (cid:132) Trong biểu thức đối ngẫu ([Eq.35]) và trong biểu thức siêu phẳng ])
phân tách ([Eq.36]):
p ([ q (cid:137) Việc xác định trực tiếp (cụ thể) giá trị φ(x) và φ(z) là không cần thiết
(cid:137) 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 là không cần thiết!
Việc chuyển đổi không gian trực tiếp là không cần thiết! (cid:132) Nếu có thể tính được tích vô hướng vectơ 〈φ(x)⋅φ(z)〉 trực tiếp từ
các vectơ x và z, thì không cần phải xác định (không cần biết):
các vectơ x và z, thì không cần phải xác định (không cần biết): (cid:137) vectơ đặc trưng (trong không gian sau chuyển đổi) φ(x), và
(cid:137) hàm chuyển đổi (ánh xạ) φ (cid:132) Trong phương pháp SVM, mục tiêu này đạt được thông qua việc
sử dụng các hàm nhân (kernel functions), được ký hiệu là K 〈φ(x) φ(z)〉
K(x z) = 〈φ(x)⋅φ(z)〉
K(x,z) Học Máy – IT 4862 41 [Eq.37]
[Eq 37] Hàm nhân – Ví dụ (cid:132) Hàm nhân đa thức
K(x z) = 〈x⋅z〉d
K(x,z) = 〈x⋅z〉 (cid:132) Xét hàm nhân đa thức với bậc d=2, đối với 2 vectơ được biểu ( 1 ( 1 2) 2 2 diễn trong không gian 2 chiều: x=(x1,x2) và z=(z1,z2)
2)
2
) zx ( g
2zx
=〉⋅ + 〈 g g
zx
11 2 2 2 2 2 2 2
2 2
zx
zx =
= +
+ +
+ 2
zx
zx
1
1 zxzx
zxzx
11 2 2 2 2 2 2 ( 2 , 2 〈= ()
⋅ )
〉 zz
1 [Eq.38] 〈= ⋅ xx
1
K=〉 (cid:132) 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à φ(z) trong không gian sau chuyển đổi
vectơ φ(x) và φ(z) trong không gian sau chuyển đổi Học Máy – IT 4862 42 Kernel trick (cid:132) Diễn giải chi tiết của các bước tính toán trong ví dụ trên chỉ mang mục đích giải thích (minh họa)
chỉ mang mục đích giải thích (minh họa) (cid:132) Trong thực tế, ta không cần phải tìm (xác định) hàm ánh xạ φxạ φ (cid:132) Bởi vì: Ta có thể áp dụng hàm nhân một cách trực tiếp →Thay thế tất cả các giá trị tích vô hướng vectơ 〈φ(x)⋅φ(z)〉 trong [Eq.35-36] bằng một hàm nhân được
chọn K(x z) (ví dụ: hàm nhân đa thức 〈x⋅z〉d trong
chọn K(x,z) (ví dụ: hàm nhân đa thức 〈x z〉 trong
[Eq.38]) (cid:132) Chiến lược này được gọi là kernel trick!
(cid:132) Chiến lược này được gọi là kernel trick! Học Máy – IT 4862 43 (cid:132) 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ột hàm có phải là một tích vô
ó hải là ột tí h ô để biết ột hà
Là
hướng vectơ trong một không gian nào đó? (cid:132) Câu hỏi này được trả lời bằng định lý Mercer (Mercer’s →Nằm ngoài phạm vi của bài giảng này!
à ! i ủ bài ài h Nằ iả Học Máy – IT 4862 44 (cid:132) Đa thức: d θ ;
trong :đó
θ R,d N +〉⋅ ∈ ∈ (
〈= ) (cid:132) Gaussian RBF (Gaussian radial basis function) 2 − 2
2 σ
σ e ; trong
t σ
:đó
đó 0
0 = >
> (cid:132) Xích-ma (Sigmoidal) λ) ;
trong :đó β,λ R tanh = (
β
〈 −〉⋅ = ∈ λ − ) 1 e + Học Máy – IT 4862 45 Phân lớp bằng SVM – Các vấn đề (cid:132) 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 ), g ộ y ị ị ị
danh thành các giá trị số (cid:132) SVM chỉ làm việc (thực hiện phân lớp) với 2 lớp → Đối với các bài toán phân lớp gồm nhiều lớp, cần chuyển thành một tập
→ Đối với các bài toán phân lớp gồm nhiều lớp, cần chuyển thành một 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” (cid:132) 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 (cid:137) Vấn đề (khó giải thích quyết định phân lớp) này càng nghiêm trọng, nếu
(cid:137) 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 (cid:137) 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 Tài liệu tham khảo •B. Liu. Web Data Mining: Exploring Hyperlinks, g p g Contents, and Usage Data. Springer, 2006. •C. J. C. Burges. A Tutorial on Support Vector Học Máy – IT 4862 47 Machines for Pattern Recognition. Data Mining and
Knowledge Discovery, 2(2): 121-167, 1998.Các đặc điểm quan trọng
g
q
(
ixw(
〈
〈
⋅
(
y
〈
i
xw
⋅
)
)
〉
+〉
i
xw
⋅
+〉
i
)
b
+〉
<
i
Ranh giới quyết định phân lớp
p
p
q
g
x*w
xx
i
∑
∑
i
Linear SVM – Tổng kết
g
hỗ trợ
Chuyển đổi không gian biểu diễn (1)
g g
X →
X →
F
F
:φ
:
φ
x φ
x
)(
a
Chuyển đổi không gian biểu diễn (2)
( )
g g
y
Non-linear SVM – Bài toán tối ưu
ww
⋅
2
(
(
ixw
φ
⋅
〈
i
i
,0
ξ
≥
=∀
i
x
x
)
(
φφ
〈
i
j
z
)(
)(
z
w
*w
z
)(
)(
z
x
x
z
)(
)(
z
(
(
i φφα
φφα
Chuyển đổi không gian – Ví dụ
g g
Chuyển đổi không gian – Trở ngại
g g
g
Các hàm nhân – Kernel functions
z
)(
2
z,z
1
zx
),(
2
,x,x
1
x
)(
φφ
Kernel function – How to know?
theorem)
Các hàm nhân thường dùng
g
g
zx
),K(
zx
zx
−
zx
),K(
K(
)
zx
),K(
zx
1
(
zx
β
−〉⋅〈
