Bài giảng Học máy - Bài 4: Hồi quy Logistic, máy véctơ hỗ trợ - Nguyễn Thanh Tùng

Hồi quy Logistic, Máy véc-
tơ hỗ trợ (SVM)
CSE 445: Học máy | Học kỳ 1, 2016-2017
Bài giảng có sử dụng hình vẽ trong cuốn sách “An Introduction to Statistical Learning with Applications in R” với sự
cho phép của tác giả, có sử dụng slides các khóa học CME250 của ĐH Stanford và IOM530 của ĐH Southern California
Nguyễn Thanh Tùng
Khoa Công nghệ thông tin – Đại học Thủy Lợi
tungnt@tlu.edu.vn
Website môn học: https://sites.google.com/a/wru.vn/cse445spring2016/
Hồi quy Logit 
(Logistic Regression)
CSE 445: Học máy | Học kỳ 1, 2016-2017
Types of Algorithms
Cluster 
Analysis
Dimensionality 
Reduction
Classification Regression
KNN
Supervised Unsupervised
Yes No
Do you have 
labeleddata?
Do you want to group the data?
Yes No
What do you want to predict?
Category Quantity
PCALogistic 
Regression
LASSO
ICA
Linear 
Regression
K-means
Hierarchical 
Clustering SOM
SVM
CSE 445: Học máy | Học kỳ 1, 2016-2017
Phân lớp
CSE 445: Học máy | Học kỳ 1, 2016-2017
• Hồi quy – dự đoán biến định lượng (liên tục) Y
– Trong nhiều ứng dụng, biến đầu ra là định tính hoặc kiểu
định danh/hạng mục
• Phân lớp: Dự đoán biến đầu ra định tính
– Gán mỗi quan sát cho một lớp/mục
– vd: Bộ phân lớp K-láng giềng gần nhất trong bài học
trước
Ví dụ về phân lớp
CSE 445: Học máy | Học kỳ 1, 2016-2017
• Các giao dịch thẻ tín dụng
– Có phải dịch gian lận hay không khi ta dựa trên thông tin 
lịch sử giao dịch của chúng?
• Rủi ro tín dụng
– Liệu một cá nhân có bị vỡ nợ với tài khoản tín dụng của
mình không?
• Thị giác máy (Computer Vision)
– Hiểu được các đối tượng xuất hiện trong ảnh
Ví dụ về phân lớp
CSE 445: Học máy | Học kỳ 1, 2016-2017
Hình 4.1 , ISL 2013*
Phân lớp và Hồi quy
CSE 445: Học máy | Học kỳ 1, 2016-2017
• Phân lớp và Hồi quy có liên quan với nhau lớn.
• Phân lớp hoạt động như hồi quy:
– Dự đoán xác suất của 1 mẫu dữ liệu thuộc vào một
lớp, ta gán vào 1 lớp có xác suất cao nhất
Hồi quy Logistic
CSE 445: Học máy | Học kỳ 1, 2016-2017
• Phân lớp nhị phân: Y nhận 2 giá trị (“0” hoặc “1”) 
với 2 lớp tương ứng
• Mô hình hồi quy Logistic đối với bài toán phân lớp
nhị phân
– Ngưỡng để đạt được các quyết định phân lớp
– Là mô hình hồi quy tuyến tính có chỉnh sửa để dự đoán
xác suất trong [0, 1]
Ví dụ: Dữ liệu Credit Card Default
• Ta cần dự đoán các khách hang có nguy cơ phá
sản (default)
• Các biến X là:
• Thu nhập thường xuyên (Annual Income)
• Cân đối thẻ hàng tháng (Monthly credit card balance)
• Biến Y (Default) có kiểu rời rạc (categorical): Yes 
hoặc No
• Làm sao để tìm quan hệ giữa Y và X?
CSE 445: Học máy | Học kỳ 1, 2016-2017
Tập dữ liệu Default
CSE 445: Học máy | Học kỳ 1, 2016-2017
Tại sao không dùng hồi quy tuyến tính?
• Khi Y chỉ nhận giá trị Yes hoặc No (1 
hoặc 0), tại sao mô hình hồi quy tuyến
tính không thích hợp?
• Nếu ta xây dựng mô hình hồi quy tuyến
tính trên dữ liệu Default, thì với những
cân đối tài chính thấp (low balances) ta 
sẽ dự đoán một xác suất âm, và với cân
đối cao ta sẽ dự đoán xác suất trên 1! Khi biến Balance < 500, 
Pr(default) là số âm!
CSE 445: Học máy | Học kỳ 1, 2016-2017
Diễn giải giá trị nhỏ hơn 0 thế nào?
Hàm Logistic trên dữ liệu Default
Xác suất của việc phá sản sát 0 
nhưng không âm đối với các tài
khoản có cân bằng tài chính
thấp, tương tự với cân bằng tài
chính cao sẽ sát nhưng không
lớn hơn 1
CSE 445: Học máy | Học kỳ 1, 2016-2017
X
X
e
eYPp
10
10
1
)1( ββ
ββ
+
+
+
===
Diễn giải giá trị β1
• Việc diễn giải ý nghĩa của β1 không dễ đối với hồi quy logistic, 
bởi vì ta đang dự đoán xác suất P(Y), không phải giá trị Y.
• Nếu β1 =0, có nghĩa là không tồn tại mối quan hệ giữa Y và X. 
• Nếu β1 >0, nghĩa là khi X nhận giá trị lớn hơn đồng nghĩa với việc
tăng xác suất của Y = 1.
• Nếu β1 <0, nghĩa là khi X nhận giá trị lớn hơn, xác suất mà Y = 1 
nhỏ đi.
• Tuy nhiên giá trị lớn hoặc nhỏ hơn là bao nhiêu lại phụ thuộc
vào vị trí ta đang đứng ở độ dốc (the slope) nào
CSE 445: Học máy | Học kỳ 1, 2016-2017
Hồi quy Logistic
CSE 445: Học máy | Học kỳ 1, 2016-2017

(βO+ β1X)
1 + 
(βO+ β1X)	 
 =
Hồi quy Logistic
CSE 445: Học máy | Học kỳ 1, 2016-2017
 =

(βO+ β1X)
1 + 
(βO+ β1X)
Ý nghĩa của các hệ số?
• Ta thực hiện kiểm định giả thuyết để xem ý nghĩa của các hệ số
β0 và β1. 
• Ta dùng kiểm định Z thay thế cho T-test, nhưng việc diễn giải p-
value không thay đổi
• Trong ví dụ này, p-value cho biến balance rất nhỏ, và β1 dương, 
vì vậy ta có thể khẳng định rằng khi biến balance tăng thì xác
suất phá sản cũng tăng theo
CSE 445: Học máy | Học kỳ 1, 2016-2017
Dự đoán
• Giả sử mỗi cá nhân có cân đối tài chính trung bình là $1000. Xác
suất phá sản là bao nhiêu?
• Xác suất phá sản dự đoán cho mỗi cá nhân với cân đối tài chính
$1000 là nhỏ hơn 1%. 
• Với cân đối là $2000, xác suất lớn hơn và kết quả là 0.586 (58.6%).
CSE 445: Học máy | Học kỳ 1, 2016-2017
Biến X rời rạc trong Hồi quy Logistic
• Ta có thể dự đoán từng cá nhân phá sản với việc kiểm tra xem
người đó có phải là sinh viên hay không. Do đó, ta sử dụng biến
rời rạc “Student” được mã như sau: Student = 1, Non-student =0. 
• β1 dương: Điều này chỉ ra rằng sinh viên có xu hướng xác suất vỡ
nợ cao hơn là người không phải là sinh viên
CSE 445: Học máy | Học kỳ 1, 2016-2017
Hồi quy Logistic đa biến
CSE 445: Học máy | Học kỳ 1, 2016-2017
• Ta có thể mở rộng hồi quy logistic với trường
hợp nhiều biến đầu vào:
Hồi quy Logistic đa biến- Default Data
Dự đoán khả năng vỡ nợ (Default) dùng:
Balance (dữ liệu số, quantitative)
Income (dữ liệu số, quantitative)
Student (rời rạc, qualitative)
CSE 445: Học máy | Học kỳ 1, 2016-2017
Dự đoán
Một sinh viên với mức cân đối thẻ tín dụng là $1,500 và
tổng thu nhập là $40,000 có xác suất dự đoán khả năng
vỡ nợ như sau
CSE 445: Học máy | Học kỳ 1, 2016-2017
Mâu thuẫn kiểu biến!
Dương
Âm
CSE 445: Học máy | Học kỳ 1, 2016-2017
Sinh viên (màu cam) vs. Không phải
sinh viên (màu xanh)
CSE 445: Học máy | Học kỳ 1, 2016-2017
• Sinh viên rủi ro hơn là người không phải sinh viên nếu không có thông tin về mức cân đối thẻ tín dụng
• Tuy nhiên, sinh viên ít rủi ro hơn với đối tượng không phải là sinh viên nếu có cùng mức cân đối thẻ
tín dụng! 
Hồi quy Logistic
CSE 445: Học máy | Học kỳ 1, 2016-2017
• Các tham số của mô hình β0 và β1 được ước
lượng từ dữ liệu huấn luyện
– Trong phương pháp hồi quy tuyến tính, ta sử dụng
bình phương nhỏ nhất
• Tìm tham số mô hình hồi quy Logistic sử dụng
phương pháp Ước lượng hợp lý cực đại
(maximum likelihood estimation)
Câu hỏi?
CSE 445: Học máy | Học kỳ 1, 2016-2017
Đánh giá hiệu quả
bộ phân lớp
CSE 445: Học máy | Học kỳ 1, 2016-2017
Phân lớp
• Học có giám sát: Học từ các mẫu đã gán nhãn
• Biến đích có dạng rời rạc / hạng mục
• Mục tiêu: dự đoán biến đích có kiểu rời rạc
– Gán mỗi mẫu cho 1 lớp
– Các bài trước: K--NN, hồiquylogistic
– Hôm nay: SVM
CSE 445: Học máy | Học kỳ 2, 2015-2016 27
Học từ mẫu đã gán nhãn
Lớp “+” Lớp “−”
CSE 445: Học máy | Học kỳ 2, 2015-2016 28
Nhãn mất cân bằng
• Nhãn mất cân bằng (Imbalanced classes): lớp
dương (+) xuất hiện với tần suất nhiều hơn lớp
âm (--)trong tập dữ liệu huấn luyện
– vd: phát hiện gian lận, dữ liệu y học
CSE 445: Học máy | Học kỳ 2, 2015-2016 29
Nhãn mất cân bằng
• Tại sao đây là vấn đề?
– Các thuật toán thực hiện tốt khi huấn luyện trên
các mẫu trong mỗi lớp
– Hiệu quả thấp trên các lớp có ít đại diện
CSE 445: Học máy | Học kỳ 2, 2015-2016 30
Đánh giá hiệu quả bộ phân lớp
• Trong bài toán hồi quy, chúng ta dùng tổng phần dư
bình phương đo lỗi để đánh giá hiệu quả thuật toán
• Với bài toán phân lớp, chúng ta cần độ đo để đánh giá
hiệu quả của bộ phân lớp
– Ví dụ: Ma trận nhầm lẫn (Confusion matrix), Độ chính xác/Hồi
tưởng (Precision/Recall), Độ nhạy/Độ đặc hiệu (Sensitivity/ 
Specificity), Đường cong ROC (ROC curve)
• Xét bài toán phân lớp nhị phân: Có 2 lớp (+) và (–)
CSE 445: Học máy | Học kỳ 2, 2015-2016 31
Đánh giá hiệu quả bộ phân lớp
• Ta có thể biểu thị tính hiệu quả của bộ phân lớp trong
1 bảng gọi làma trận nhầm lẫn (confusion matrix):
– “Hiệu quả tốt”: True Positive (TP), True Negative (TN) lớn và
False Positive (FP), False Negative (FN) nhỏ
• TP: Số lượng các mẫu thuộc lớp (+) được phân loại chính
xác vào lớp (+)
• FP: Số lượng các mẫu không thuộc lớp (+) bị phân loại nhầm
vào lớp (+)
CSE 445: Học máy | Học kỳ 2, 2015-2016 32
Đánh giá hiệu quả bộ phân lớp
True Positive-TP False Negative-FN 
Type II error
(False Positive-FP) 
Type I error
True Negative-TN
Lớp thực
(True class)
• TN: Số lượng các mẫu không thuộc lớp (+) được phân loại đúng
• FN: Số lượng các mẫu thuộc lớp (+) bị phân loại nhầm (vào các lớp 
khác lớp (+))
Lớp dự đoán (Predicted class)
+ –
+
–
CSE 445: Học máy | Học kỳ 2, 2015-2016 33

 =
 + 
True positive rate (TPR) Positive predictive value (PPV) (precision)
(recall, sensitivity)
 =

 + 
False positive rate (FPR)
 =

 + 
True negative rate (SPC)
(specificity)
 =

 + 
Đánh giá hiệu quả bộ phân lớp
TP FN
FP TN
T
r
u
e
c
l
a
s
s
+
–
TP FN
FP TN
T
r
u
e
c
l
a
s
s
Predicted class Predicted class
– –+ +
+
–
TP FN
FP TN
T
r
u
e
c
l
a
s
s
Predicted class
+ –
+
–
TP FN
FP TN
T
r
u
e
c
l
a
s
s
Predicted class
+ –
+
–
CSE 445: Học máy | Học kỳ 2, 2015-2016 34

 =
 + 
True positive rate (TPR) Positive predictive value (PPV) (precision)
(recall, sensitivity)
 =

 + 
False positive rate (FPR)
 =

 + 
True negative rate (SPC)
(specificity)
 =

 + 
Đánh giá hiệu quả bộ phân lớp
TP FN
FP TN
T
r
u
e
c
l
a
s
s
+
–
TP FN
FP TN
T
r
u
e
c
l
a
s
s
Predicted class Predicted class
– –+ +
+
–
TP FN
FP TN
T
r
u
e
c
l
a
s
s
Predicted class
+ –
+
–
TP FN
FP TN
T
r
u
e
c
l
a
s
s
Predicted class
+ –
+
–
P
recisio
n
/recall
R
O
C
c
u
r
v
e
CSE 445: Học máy | Học kỳ 2, 2015-2016 35
Đánh giá hiệu quả bộ phân lớp
• Đường cong ROC (receiver operating characteristic)
Tỷ lệ lỗi chấp
nhận đúng
(TPR)
Tỷ lệ lỗi chấp nhận sai
(FPR)
1
0
0 1
Dự đoán ngẫu nhiên
(50/50, randomguessing)
phân lớp
hoàn hảo
đơn điệu tăngBộ phân lớp A
Bộ phân lớpB
TP
TPR=
TP+FN
FP
FPR=
FP+TN
CSE 445: Học máy | Học kỳ 2, 2015-2016 36
Đánh giá hiệu quả bộ phân lớp
90 10
1188 8712T
r
u
e
c
l
a
s
s
• Nhược điểm của đường cong ROC
– ROC không biểu thị đúng độ mất cân bằng các mẫu trong lớp thực
– vd: Xét bộ dữ liệu có 1% mẫu thuộc lớp “+” và 99%mẫuthuộc lớp“–”
• Giả sử ta nhận được kết quả phân lớp như sau:
TPR = 0.9 và FPR = 0.12
• TPR và FPR không hiểu thị được theo tính chất của đường cong ROC
Predicted class
+ –
+
–
CSE 445: Học máy | Học kỳ 2, 2015-2016 37
Đánh giá hiệu quả bộ phân lớp
• Độ chính xác/Triệu hồi (Precision/recall)
– Độ chính xác (Positive predictive value):  = TP
TP+FP
• Tỷ lệ phần trăm của số mẫu thuộc lớp (+) được dự đoán đúng trên số mẫu thực là (+)
– Recall (True positive rate):  = TP = TP
TP+FN P
• Tỷ lệ các mẫu (+) phân lớp chính xác lớp (+)
90 10
1188 8712T
r
u
e
c
l
a
s
s
– Recall và precision tỷ lệ nghịch với nhau
– Với bộ phân lớp hoàn hảo, Recall = 1, Precision = 1
– VD phân lớp mất cân bằng: Recall = 0.9, Precision = 0.07
Predicted class
+ –
+
–
0 0
8 12
CSE 445: Học máy | Học kỳ 2, 2015-2016 38
Máy véc-tơ hỗ trợ
Support Vector Machines 
(SVMs)
CSE 445: Học máy | Học kỳ 1, 2016-2017
Máy véc-tơ hỗ trợ
• Máy véc-tơ hỗ trợ được đề xuất 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 
• Phương pháp học phân loại có giám sát: Bài toán phân loại 2 lớp
• Khái quát hóa bộ phân lớp với lề cực đại (maximal margin 
classifier)
• Support vector classifier: có thể áp dụng với dữ liệu không tách
được tuyến tính
• Support vector machine: ranh giới quyết định phi tuyến
(non-linear decision boundary)
CSE 445: Học máy | Học kỳ 1, 2016-2017
Bộ phân lớp có lề cực đại
• Bộ phân lớp có lề cực đại
– Giả định quan trọng: Dữ liệu có 2 lớp tách được tuyến tính
• 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 để phân tách hai lớp của dữ liệu –
ví dụ: lớp các mẫu có nhãn dương (positive) và lớp các mẫu có nhãn 
âm (negative)
• Tìm hiểu về siêu phẳng (hyperplanes)
CSE 445: Học máy | Học kỳ 1, 2016-2017
Các siêu phẳng
• Siêu phẳng là gì?
– Trong không gian d-chiều, tồn tại một không gian
con (d−1)-chiều
Vd: đường thẳng trong 2D, máy bay trong không gian 3D
– Siêu phẳng trong không gian d-chiều:
– Tách không gian thành 2 nửa không gian con
CSE 445: Học máy | Học kỳ 1, 2016-2017
−7+2x1− x2 = 0
Các siêu phẳng
−7+ 2x1− x2 < 0
−7+ 2x1− x2 > 0
4+9x1+6x2 −2x3 < 0
4+9x1+6x2 −2x3 = 0
4+9x1+6x2 −2x3 > 0
CSE 445: Học máy | Học kỳ 1, 2016-2017
Mặt siêu phẳng phân tách
Ý tưởng:
Dùng mặt siêu phẳng phân
tách cho phân lớp nhị phân
Giả định:
Các lớp có thể tách được
tuyến tính
Hình 9.2 , ISL 2013
CSE 445: Học máy | Học kỳ 1, 2016-2017
Mặt siêu phẳng phân tách
Phân lớp đối tượng mới:
Phân lớp dựa vào vị trí của đối
tượng mới tương ứng với siêu
phẳng:
Hình 9.2 , ISL 2013
CSE 445: Học máy | Học kỳ 1, 2016-2017
Mặt siêu phẳng phân tách
Giả định:
Các lớp có thể tách được
tuyến tính

 Tồn tại nhiều mặt phẳng
tách
Hình 9.2 , ISL 2013
CSE 445: Học máy | Học kỳ 1, 2016-2017
Phân lớp sai
Câu hỏi:
Đường tách tuyến
tính nào phù hợp?
Ta sử dụng tiêu chí gì để chọn?
Hình 9.2 , ISL 2013
CSE 445: Học máy | Học kỳ 1, 2016-2017
Mặt siêu phẳng phân tách
Hình 9.2, 9.3 , ISL 2013
Đường tách tuyến tính nào phù hợp?
CSE 445: Học máy | Học kỳ 1, 2016-2017
• Thay vì việc tìm 1 đường thẳng
tách 2 lớp, ta tìm 2 đường
thẳng tách các điểm này.
• Không có điểm DL nào nằm
giữa 2 đường này.
• Đây là ý tưởng đơn giản nhất
của SVM, gọi là SVM tuyến tính.
Mặt phẳng phân tách “xa nhất” 
từ tập dữ liệu huấn luyện

 “Bộ phân lớp có lề cực đại”
Bộ phân lớp có lề cực đại
Hình 9.3 , ISL 2013
Siêu phẳng có lề cực đại
Siêu phẳng “xa nhất” từ tập huấn
luyện
Cực đại lề
Lề (Margin): khoảng cách nhỏ nhất giữa
bất kỳ đối tượng nào trong tập huấn
luyện và siêu phẳng
Véc-tơ hỗ trợ (Support vectors): Các đối
tượng cách đều từ siêu phẳng
CSE 445: Học máy | Học kỳ 1, 2016-2017
Support Vectors là các điểm
dữ liệu nằm trên 2 đường
thẳng
Bộ phân lớp có lề cực đại
• Véc-tơ hỗ trợ
– Các đối tượng cách đều từ siêu phẳng có lề cực đại (maximal margin
(MM) hyperplane)
– “Hỗ trợ”: siêu phẳng MM chỉ phụ thuộc vào các đối tượng (véc-tơ) này
• Nếu các véc-tơ hỗ trợ bị nhiễu thì siêu phẳng MM sẽ thay đổi
• Nếu bất kỳ một mẫu huấn luyện nào bị nhiễu, siêu phẳng MM không ảnh hưởng
CSE 445: Học máy | Học kỳ 1, 2016-2017
Bộ phân lớp có lề cực đại
• Để tìm siêu phẳng có lề cực đại, ta giải:
là các nhãn lớp
Bài toán tối ưu có ràng buộc
Cực đại lề,M
Tất cả các mẫu phải có
khoảng cách tối thiểu M 
từ siêu phẳng
CSE 445: Học máy | Học kỳ 1, 2016-2017
Tóm lược khái niệm cho SVM
• Xét bài toán dùng siêu phẳng tách 2 lớp
• Tịnh tiến song song siêu phẳng này về phía tập
mẫu của mỗi lớp, quá trình này dừng khi có ít
nhất 1 điểm thuộc siêu phẳng và không tiến
thêm được nữa
 siêu phẳng lề
• Hành lang nằm giữa 2 siêu phẳng gọi làmiền lề
• Khoảng cách giữa 2 siêu phẳng gọi là lề của
siêu phẳng tách
• Siêu phẳng tách tốt nhất có lề cực đại

phương pháp tìm ra siêu phẳng tốt nhất này gọi là SVM
CSE 445: Học máy | Học kỳ 1, 2016-2017
Hình 9.3 , ISL 2013
Hình 9.5 , ISL 2013
34CSE 445: Học máy | Học kỳ 1, 2016-2017
Nhược điểm:
Có thể bị overfit trên dữ
liệu huấn luyện
Bộ phân lớp có lề cực đại
Bộ phân lớp có lề cực đại
Nhược điểm:
Có thể bị overfit trên dữ
liệu huấn luyện
Nhạy cảm với các mẫu
độc lập
Hình 9.5 , ISL 2013
35CSE 445: Học máy | Học kỳ 1, 2016-2017
Bộ phân lớp có lề cực đại
Quay lại giả định trước:
Các lớp tách được bởi hàm
tuyến tính
Điều gì xảy ra khi không tồn
tại siêu phẳng tách?
Hình 9.4 , ISL 2013
CSE 445: Học máy | Học kỳ 1, 2016-2017
Bộ phân loại véc-tơ hỗ trợ
Điều gì xảy ra khi không tồn
tại siêu phẳng tách?
Bộ phân loại véc-tơ hỗ trợ
(Support Vector Classifier): 
cho phép các mẫu huấn luyện
nằm phía phân loại sai
“wrong side” của lề hoặc siêu
phẳng
Hình 9.4 , ISL 2013
36CSE 445: Học máy | Học kỳ 1, 2016-2017
Bộ phân loại véc-tơ hỗ trợ
• Support Vector Classifier
– Bộ phân loại dựa trên siêu phẳng
– Cho phépmột sốmẫu trong tập huấn luyện nằm sai vị trí đối
với lề/siêu phẳng
– Lề mềm (Soft margin): lề không cố định ranh giới quyết
định phân lớp 
Mục tiêu để mở rộng miền áp dụng, ta 
chấp nhận trong miền lề có lỗi nhưng ngoài miền lề phải
phân lớp đúng
CSE 445: Học máy | Học kỳ 1, 2016-2017
Bộ phân loại véc-tơ hỗ trợ
Hình 9.6 , ISL 2013
CSE 445: Học máy | Học kỳ 1, 2016-2017
Bộ phân loại véc-tơ hỗ trợ
• Support Vector Classifier
– Bộphân loại dựa trên siêu phẳng
– Cho phépmột sốmẫu trong tập huấn luyệnnằm sai vị trí đối với lề/siêu
phẳng
– Lề mềm (Soft margin): lề không có ranh giới cố định
• Ý tưởng: giải bài toán cực đại lề, nhưng cho phép một số lỗi
(vi phạm) trong miền lề
– Đưa thêm hệ số phạt để giới hạn số lượng/bậc của vi phạm
CSE 445: Học máy | Học kỳ 1, 2016-2017
giới hạn của
tổng lượng
phạt
Các mẫu huấn luyện có khoảng
cách nhỏ hơn M từ siêu phẳng với
giá trị phạt εi
Bộ phân loại véc-tơ hỗ trợ
• Để tìm siêu phẳng cho bộ phân loại véc-tơ hỗ trợ, ta giải:
Bài toán tối ưu có ràng buộc
cực đại lề, M
biến chùng (“slack”) εi
CSE 445: Học máy | Học kỳ 1, 2016-2017
Bộ phân loại véc-tơ hỗ trợ
• Biến chùng (Slack) εi cho phép nới lỏng các vi phạm của lề
– εi = 0 : mẫu huấn luyện X(i) nằm đúng phía so với lề
– εi∈ (0, 1) : X(i) ở trong miền lề và phân lớp đúng
– εi > 1 : X(i) phân lớp sai (nằm sai vị trí so với siêu phẳng tách)
• Ta muốn tìm hàm quyết định có lề lớn nhất và số điểm có εi> 0 nhỏ nhất. 
Tham số phạt C (C>0) – biểu thị cho việc phạt các điểm phân lớp sai. C càng
lớn thì lề càng hẹp, C→∞ ứng với trường hợp tách được tuyến tính.
– Gán các giá trị chi phí C (cost) cho các lỗi. Cho phép nhiều nhất C phân lớp
sai trên tập dữ liệu huấn luyện
CSE 445: Học máy | Học kỳ 1, 2016-2017
Bộ phân loại véc-tơ hỗ trợ
Hình 9.7 , ISL 2013
“Misclassification
budget” tham số C
được chọn bởi kỹ thuật
cross-validation
*điều khiển cân bằng
bias-variance*
Các véc-tơ hỗ trợ: các mẫu
trên lề hoặc vi phạm lề
Large budget 
many Support Vectors
Small budget 
fewer Support Vectors
CSE 445: Học máy | Học kỳ 1, 2016-2017
Bộ phân loại véc-tơ hỗ trợ
Hình 9.8 , ISL 2013
Nhược điểm:
Ranh giới quyết định
tuyến tính
CSE 445: Học máy | Học kỳ 1, 2016-2017
Mở rộng không gian biến
Some data sets are not linearly
separable
But they become linearly 
separable when transformed 
into a higher dimensional
space
Các biến: X1 , X2 Các biến: X1 , X2, X1X2
CSE 445: Học máy | Học kỳ 1, 2016-2017
Mở rộng không gian biến
• Hồi quy tuyến tính
Mô hình phi tuyến
– Tạo ra các biến mà chúng là các hàm của biến đầu vào
• Áp dụng kỹ thuật tương tự này vào bộ phân lớp
véc-tơ hỗ trợ
– Xem xét các hàm đa thức của biến đầu vào
CSE 445: Học máy | Học kỳ 1, 2016-2017
Phântáchphi tuyến
• Giả sử dữ liệu đầu vào của ta có d biến:
• Mở rộng không gian biến gồm 2d biến:
– Ranh giới quyết định sẽ là phi tuyến trong không gian biến ban đầu
CSE 445: Học máy | Học kỳ 1, 2016-2017
Phântáchphi tuyến
• Dữ liệu được biểu diễn trong không gian mới (đã chuyển đổi) 
có thể phân lớp tuyến tính:
• Ranh giới quyết định trong không gian mở rộng là hình E-líp
(ellipse) trong không gian biến ban đầu:
CSE 445: Học máy | Học kỳ 1, 2016-2017
Phântáchphi tuyến
CSE 445: Học máy | Học kỳ 1, 2016-2017
Phântáchphi tuyến
CSE 445: Học máy | Học kỳ 1, 2016-2017
Phântáchphi tuyến
CSE 445: Học máy | Học kỳ 1, 2016-2017
Phântáchphi tuyến
• Thêm đa thức bậc cao cho tập không gian biến mở rộng

 số lượng biến tăng rất nhanh
– Bài toán nhiều biến sẽ gặp trở ngại vì thời gian tính toán lâu
– Ta cần 1 phương pháp hiệu quả để xử lý bài toán nhiều biến
CSE 445: Học máy | Học kỳ 1, 2016-2017
72
Không gian đặc trưng mới (3D)Không gian đầu vào (2D)
Φ: X→ φ(X)
Phântáchphi tuyến
CSE 445: Học máy | Học kỳ 1, 2016-2017
Máy véc-tơ hỗ trợ (SVM)
Support VectorMachine: 
mở rộng để sử dụng các
nhân (kernels) đạt được
ranh giới quyết định phi 
tuyến
• Các hàm nhân ánh xạ dữ
liệu vào không gian có số
chiều cao hơn
– Áp dụng bộ phân lớp véc-tơ
hỗ trợ vào không gian chiều cao
với siêu phẳng (tuyến tính) ranh
giới quyết định
CSE 445: Học máy | Học kỳ 1, 2016-2017
Máy véc-tơ hỗ trợ
• Việc tính toán trong bộ phân lớp véc-tơ hỗ trợ chỉ yêu cầu xử
lý nội tại (inner product) của dữ liệu huấn luyện, không cần
thiết phải chuyển đổi không gian trực tiếp
• Trong phương pháp SVM, ta sử dụng các hàm nhân (kernel 
functions), được ký hiệu là K
CSE 445: Học máy | Học kỳ 1, 2016-2017
Ví dụ về φ(.) và K(.,.)
• Giả sử φ(.) được cho bởi
• Inner product trong không
gian đặc trưng mới là
• Do đó, nếu ta định nghĩa hàm nhân (kernel function) như dưới
đây, ta không cần phải thực hiện φ(.) một cách tường minh
• Việc sử dụng hàm nhân để tránh thực hiện φ(.) tường minh được
gọi là kernel trick
)2,,,2,2,1( 21222121
2
1
xxxxxx
x
x
=












φ
2
2211
2
1
2
1 )1(, yxyx
y
y
x
x
++=


























 φφ
( ) 22211 )1(, yxyxK ++=yx
CSE 445: Học máy | Học kỳ 1, 2016-2017 75
Máy véc-tơ hỗ trợ
• Tính chất của hàm nhân K(X, X’):
– Không cần chuyển đổi trực tiếp không gian biến
– Đối xứng: K(X, X’) = K(X’, X)
– Cho ta tính tương tự của X và X’
• Nếu X và X’ gần nhau thì K(X, X’) lớn
• Nếu X và X’ xa nhau từng phần thì K(X, X’) nhỏ
CSE 445: Học máy | Học kỳ 1, 2016-2017
Máy véc-tơ hỗ trợ
• Nhân tuyến tính (Linear kernel)
• Nhân đa thức bậc p (Polynomial kernel (degree p))
• Nhân Radial (Radial basis kernel)
CSE 445: Học máy | Học kỳ 1, 2016-2017
Máy véc-tơ hỗ trợ
• Tại sao sử dụng nhân thay thế cho xây dựng trực
tiếp không gian biến chiều cao?
– Ưu điểm tính toán nhanh hơn
• Các phương pháp học máy khác sử dụng nhân
– Vd: kernel PCA
CSE 445: Học máy | Học kỳ 1, 2016-2017
• Ví dụ: nhân đa thức (polynomial kernel), p = 2, d = 2:
Ta có
CSE 445: Học máy | Học kỳ 1, 2016-2017
Máy véc-tơ hỗ trợ
CSE 445: Học máy | Học kỳ 1, 2016-2017
Máy véc-tơ hỗ trợ
• Ưu điểm
– Điều chỉnh tham số C để tránh overfitting
– Sử dụng nhân cung cấp độ linh hoạt dưới hình thức ranh
giới quyết định
– Tối ưu hóa hàm lồi – cho lời giải duy nhất
• Nhược điểm
– Phải thử nhiều siêu tham số (vd: C, kernel function)
• Đạt hiệu suất kém nếu chọn sai
– Phải đưa được về bài toán phân lớp nhị phân
– Khó diễn giải
CSE 445: Học máy | Học kỳ 1, 2016-2017
Câu hỏi?
CSE 445: Học máy | Học kỳ 1, 2016-2017
SVM với 3+ lớp
• SVMs được thiết kế cho phân lớp nhị phân
– Siêu phẳng tách phân dữ liệu thành 2 lớp
• Làm sao để xử lý dữ liệu khi số lớp nhiều hơn 2?
• Có 2 cách tiếp cận thông dụng:
1. One--versus--one
2. One--versus--all
CSE 445: Học máy | Học kỳ 1, 2016-2017
SVM với 3+ lớp
• Phân lớp One-versus-one
– Xây dựng SVM cho từng cặp
– Với # lớp sẽ yêu cầu huấn luyện
$($%&)
'
SVMs
– Để phân lớp đối tượng mới, áp dụng tất cả
$($%&)
'
SVMs
cho từng mẫu – chọn lớp có tần suất nhiều nhất trong
từng cặp để lấy giá trị phân lớp cuối cùng
– Nhược điểm: thời gian tính toán lâu khi giá trị của K lớn
CSE 445: Học máy | Học kỳ 1, 2016-2017
SVM với 3+ lớp
• PhânlớpOne--versus--all
– Xấp xỉ # SVMs, ở đó lớp K biểu thị một phân lớp, và
các lớp #−1 còn lại được gộp vào thành lớp thứ 2
– Khoảng cách đến siêu phẳng tách sẽ đại diện
cho độ tin cậy của phân lớp
– Với đối tượng mới, chọn lớp có “độ tin cậy cao
nhất” để dự đoán
CSE 445: Học máy | Học kỳ 1, 2016-2017
Câu hỏi?
CSE 445: Học máy | Học kỳ 1, 2016-2017