Kỹ thuật kiểm tra chéo, hiệu chỉnh mô hình, mô hình thưa
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/
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
CSE 445: Học máy | Học kỳ 1, 2016-2017
1
Các dạng giải thuật Học máy
Do you have labeled data?
Yes
No
Unsupervised
Supervised
What do you want to predict?
Do you want to group the data?
Category
Quantity
Yes
No
Classification
Regression
Cluster Analysis
Dimensionality Reduction
SVM
KNN
LASSO
CART
K-means
ICA
PCA
Logistic Regression
Linear Regression
CSE 445: Học máy | Học kỳ 1, 2016-2017
2
Nhắc lại Hồi quy tuyến tính đơn giản
Figure 3.1 , ISL 2013
CSE 445: Học máy | Học kỳ 1, 2016-2017
3
Nhắc lại Bình phương nhỏ nhất
•
Sử dụng phương pháp bình phương nhỏ nhất để đo lường độ xấp xỉ của mô hình áp dụng trên dữ liệu
• Phần dư (Residual): sai số giữa giá trị quan sát được và giá trị dự đoán.
(cid:1)(i) = (cid:7)(i) (cid:8) (cid:7)ˆ(i)
• Tổng phần dư bình phương-Residual sum of squares (RSS): 2
2
(cid:10)(cid:11)(cid:11) = (cid:1)(1)
+ (cid:1)(2)
+ ⋯ + (cid:1)(n) 2 Lỗi bình phương trung bình-Mean squared error (MSE):
•
CSE 445: Học máy | Học kỳ 1, 2016-2017
4
Hàm tổn thất Loss Functions
CSE 445: Học máy | Học kỳ 1, 2016-2017
5
Loss Functions ˆ L(q ,q ) i
i
CSE 445: Học máy | Học kỳ 1, 2016-2017
6
Loss Functions ˆ L(q ,q ) i
i
Lỗi bình phương (Squared error)
(q - q ) 2
∑
ˆ i
i
i
Lỗi tuyệt đối (Absolute error)
q - qˆ
∑
i
i
i
Lỗi điều hướng (Indicator error)
I(q „
∑
i
ˆ q ) i
i
CSE 445: Học máy | Học kỳ 1, 2016-2017
7
Học máy chỉ để giải 1 vấn đề
CSE 445: Học máy | Học kỳ 1, 2016-2017
8
Kỹ thuật kiểm tra chéo Cross-validation
CSE 445: Học máy | Học kỳ 1, 2016-2017
9
Kỹ thuật kiểm tra chéo
“Dùng lỗi trên tập dữ liệu kiểm thử để ước lượng lỗi dự đoán”
err = E[L(Y, fˆ(X))]
CSE 445: Học máy | Học kỳ 1, 2016-2017
10
Kỹ thuật kiểm tra chéo
Tập huấn luyện-Training Set
Tập kiểm thử-Test Set
Tập kiểm chứng-Validation Set
Training Data
Testing Data
CSE 445: Học máy | Học kỳ 1, 2016-2017
11
Kỹ thuật kiểm tra chéo K--fold
Vídụ5--fold
Hastie, Trevor, et al. The elements of statistical learning. Vol. 2. No. 1. New York: Springer, 2009.
10
CSE 445: Học máy | Học kỳ 1, 2016-2017
12
Kỹ thuật kiểm tra chéo 5-fold và 10-fold thường được ưa dùng (lỗi bias cao, phương sai thấp)
CSE 445: Học máy | Học kỳ 1, 2016-2017
13
Kỹ thuật kiểm tra chéo N-fold gọi là kỹ thuật kiểm tra chéo “leave one out-LOOCV” (lỗi bias thấp, phương sai cao)
CSE 445: Học máy | Học kỳ 1, 2016-2017
14
Kỹ thuật kiểm tra chéo
• Dùng để ước lượng lỗi dự đoán • Dùng để chọn các giá trị tham số phù hợp cho mô hình (vd: tham số k trong k--láng giềng gần nhất)
CSE 445: Học máy | Học kỳ 1, 2016-2017
15
Auto Data: LOOCV vs. K-fold CV
Hình trái: Sai số LOOCV Hình phải: 10-fold CV được chạy nhiều lần, đồ thị biểu diễn sai khác nhỏ về lỗi CV LOOCV là trường hợp đặc biệt của k-fold, khi k = n
Cả hai đều ổn định, tuy nhiên LOOCV mất nhiều thời gian tính toán hơn!
CSE 445: Học máy | Học kỳ 1, 2016-2017
16
Thách thức: Overfitting
• Overfitting: Kết quả tốt trên tập huấn luyện nhưng cho kết quả
kém trên tập kiểm thử
Figures 2.4 and 2.6 ,ISL 2013
CSE 445: Học máy | Học kỳ 1, 2016-2017
17
Overfitting
Sai số trên tập kiểm thử
“With four parameters I can fit an elephant, and with five I can make him wiggle his trunk”
--John von Neumann according to Enrico Fermi
Sai số trên tập huấn luyện
Figure2.9 , ISL 2013
CSE 445: Học máy | Học kỳ 1, 2016-2017
18
Kỹ thuật kiểm tra chéo (đường cong của hàm học)
Ta cần thêm biến (mô hình mới) hoặc thêm dữ liệu?
CSE 445: Học máy | Học kỳ 1, 2016-2017
19
Mô hình có điều chỉnh
CSE 445: Học máy | Học kỳ 1, 2016-2017
20
Nhắc lại: Hồi quy tuyến tính đa biến
+ b
+ b
Y = b
(cid:215) X1
1
(cid:215) X2
2
0
Figure3.4 , ISL 2013
CSE 445: Học máy | Học kỳ 1, 2016-2017
21
Trường hợp quá nhiều biến
khi có quá nhiều biến đầu vào
1
2
0
3
4
5
6
7
8
khi có tương tác giữa các biến đầu vào
2
2
+ b
+ b
+ b
+ b
+ b
Y = b
(cid:215) X1
1
(cid:215) X2
2
0
(cid:215) (X1X2 ) + b
3
4
(cid:215) X1
(cid:215) X 2
5
(cid:215) log(X1 / X2 ) + b
(cid:215) sin(X1
- X2 )
7
6
CSE 445: Học máy | Học kỳ 1, 2016-2017
22
+ b + b + b + b + b + b + b + b Y = b (cid:215) X1 (cid:215) X2 (cid:215) X3 (cid:215) X4 (cid:215) X5 (cid:215) X6 (cid:215) X7 (cid:215) X8
Trường hợp quá nhiều biến
Hai mẫu xác định 1 đường thẳng
Ba mẫu xác định 1 mặt phẳng
1
0
1
2
0
CSE 445: Học máy | Học kỳ 1, 2016-2017
23
+ b + b + b Y = b Y = b (cid:215) X1 (cid:215) X1 (cid:215) X2
Trường hợp quá nhiều biến
Hai mẫu không xác định một mặt phẳng duy nhất
1
2
0
CSE 445: Học máy | Học kỳ 1, 2016-2017
24
+ b + b Y = b (cid:215) X1 (cid:215) X2
Trường hợp quá nhiều biến
1
2
0
3
4
5
6
7
8
+ b + b + b + b + b + b + b + b Y = b (cid:215) X1 (cid:215) X3 (cid:215) X5 (cid:215) X4 (cid:215) X6 (cid:215) X7 (cid:215) X8
CSE 445: Học máy | Học kỳ 1, 2016-2017
25
(cid:215) X2 Gene expression arrays
Điều gì xảy ra?
1
2
0
3
4
5
6
7
8
Câu hỏi: Ta có 8 biến và có hàng trăm mẫu. Hai biến (X3 và X4) có tương quan yếu với Y (do đó cũng hữu dụng nhỏ cho dự đoán), tuy nhiên chúng có tương quan cao với các biến khác. Điều gì xảy ra khi diễn giải các hệ số β của hai biến X3 và X4?
CSE 445: Học máy | Học kỳ 1, 2016-2017
26
+ b + b + b + b + b + b + b + b Y = b (cid:215) X1 (cid:215) X2 (cid:215) X3 (cid:215) X4 (cid:215) X5 (cid:215) X6 (cid:215) X7 (cid:215) X8
Đa cộng tuyến (Multi-collinearity)
1
2
0
3
4
5
6
7
8
CSE 445: Học máy | Học kỳ 1, 2016-2017
27
+ b + b + b + b + b + b + b + b Y = b (cid:215) X1 (cid:215) X2 (cid:215) X3 (cid:215) X4 (cid:215) X5 (cid:215) X6 (cid:215) X7 (cid:215) X8
Ta cần phải làm gì?
Phạt các hệ số β lớn.
CSE 445: Học máy | Học kỳ 1, 2016-2017
28
Hồi quy tuyến tính đa biến
Quay lại hồi quy tuyến tính, ta cố gắng để cực tiểu hóa lỗi bình phương
∑
1
1
0
2
2
các mẫu
30
CSE 445: Học máy | Học kỳ 1, 2016-2017
29
[Y - (b + b (cid:215) X + b (cid:215) X )]2
Hồi quy Ridge
Tìm giá trị β để cực tiểu lỗi phạt “penalized”, tương đương với
2
∑
1
1
0
2
2 1
2 0
2
2 2
samples
L2
CSE 445: Học máy | Học kỳ 1, 2016-2017
30
[Y - (b + b (cid:215) X + b (cid:215) X )] + l (cid:215) (b + b + b )
Hiệu chỉnh mô hình (Regularization)
2
Hồi quy Ridge Tìm giá trị β để cực tiểu lỗi phạt “penalized”, tương đương với (cid:215) X )] + l (cid:215) (b + b + b
∑
0
1
1
2
2
2 1
2 0
2 2
các mẫu
L2
hoặc viết ở dạng khác,
CSE 445: Học máy | Học kỳ 1, 2016-2017
31
(b + b (cid:215) X + b [Y - )
Hồi quy Ridge
0 6
60
0 5
50
r o r r
0 4
Error 40
0 3
30
0 2
Đường cong nào là lỗi bias, đâu là phương sai, và đâu là lỗi dự đoán trên tập dữ liệu kiểm thử?
Squared 20
0 1
E d e r a u q S n a e M
Mean 10
0
0
1e−01
1e+01
1e+03
0.0
0.2
0.8
1.0
0.6 ˆ
0.4 ∥ˆ βR
λ
λ ∥2/∥β∥2
Hastie, Trevor, et al. Introduction to statistical learning.
CSE 445: Học máy | Học kỳ 1, 2016-2017
32
Hồi quy Ridge
0 6
60
0 5
50
r o r r
0 4
Error 40
0 3
30
0 2
Squared 20
0 1
E d e r a u q S n a e M
Mean 10
0
0
1e−01
1e+01
1e+03
0.0
0.2
0.8
1.0
0.6 ˆ
0.4 ∥ˆ βR
λ
λ ∥2/∥β∥2
Hastie, Trevor, et al. Introduction to statistical learning.
CSE 445: Học máy | Học kỳ 1, 2016-2017
33
Hiệu chỉnh mô hình
Ta đã xử lý:
•Underdetermined •Overfitting •Đa cộng tuyến (Multi--collinearity)
Vậy mô hình thưa là gì (sparsity)?
1
2
0
3
4
5
6
7
8
0
0
0
CSE 445: Học máy | Học kỳ 1, 2016-2017
34
+ b + b + b + b + b + b + b + b Y = b (cid:215) X1 (cid:215) X2 (cid:215) X3 (cid:215) X4 (cid:215) X5 (cid:215) X6 (cid:215) X7 (cid:215) X8
Mô hình thưa (Sparsity)
1
2
0
3
4
5
6
7
8
0
0
0
• Dùng cho lựa chọn biến (Feature selection) • Thời gian tính toán lâu (computational
efficiency)
CSE 445: Học máy | Học kỳ 1, 2016-2017
35
+ b + b + b + b + b + b + b + b Y = b (cid:215) X1 (cid:215) X2 (cid:215) X3 (cid:215) X4 (cid:215) X5 (cid:215) X6 (cid:215) X7 (cid:215) X8
Mô hình thưa (Sparsity)
Lasso
“Least absolute shrinkage and selection operator”
2
∑
1
2
0
2
1
0
2 )
L1
samples
Mô hình giống như hồi quy Rigde nhưng khác hàm phạt
Tibshirani, Robert. "Regression shrinkage and selection via the lasso." Journal of the Royal Statistical Society. Series B (Methodological)(1996): 267--288.
CSE 445: Học máy | Học kỳ 1, 2016-2017
36
+ b +b [Y - (b + b + b (cid:215) X1 (cid:215) X )] + l (cid:215) (b
Lasso
“Least absolute shrinkage and selection operator”
2
b + b + b
∑
1
2
2
0
0
1
2
samples
hoặc viết ở dạng khác,
CSE 445: Học máy | Học kỳ 1, 2016-2017
37
+ b +b (cid:215) X )] + l (cid:215) ( ) [Y - (b (cid:215) X1
Phương thức phạt (Penalties)
x2
Đường bậc 2 thô
x
2
1.8
L2
1.6
L1
1.4
0.1
1.2
0.09
1
s i x A Y
0.08
0.8
0.07
0.6
0.06
0.4
0.05
0.2
s i x A Y
0.04
0
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
0.03
X Axis
0.02
L2
0.01
Kiểu đường bậc 2.
0
0
0.01
0.02
0.03
0.04
0.05
0.06
0.07
0.08
0.09
0.1
X Axis
CSE 445: Học máy | Học kỳ 1, 2016-2017
38
Các độ đo khoảng cách
5
4
3
2
1
x2 + x2
0
-4
-3
-2
-1
1
2
3
4
5
-1
1
2
x1
+ x2
CSE 445: Học máy | Học kỳ 1, 2016-2017
39
x = x 2
Các độ đo khoảng cách được gọi là
chuẩn - Norms
L1
L2
CSE 445: Học máy | Học kỳ 1, 2016-2017
40
Distance measures are called Norms
CSE 445: Học máy | Học kỳ 1, 2016-2017
41
Các chuẩn, “Norms”
Hastie, Trevor, et al. The elements of statistical learning. Vol. 2. No. 1. New York: Springer, 2009.
CSE 445: Học máy | Học kỳ 1, 2016-2017
42
Mục tiêu khác: Mô hình thưa
Lasso
Ridge
”
50
CSE 445: Học máy | Học kỳ 1, 2016-2017
43
”
Mục tiêu khác: Mô hình thưa
Hastie, Trevor, et al. The elements of statistical learning. Vol. 2. No. 1. New York: Springer, 2009.
CSE 445: Học máy | Học kỳ 1, 2016-2017
44
Các chuẩn với các góc nhọn trên các trục
tạo các giải pháp thưa
CSE 445: Học máy | Học kỳ 1, 2016-2017
45
L1 (lasso) tính nhanh hơn và thưa
i
0 0 4 0 0 3 0 0 2 0 0 1
i
0
s t n e c i f f e o C d e z d r a d n a t S
0 0 2 −
20
50
100 200
500
2000
5000
λ
Hastie, Trevor, et al. Introduction to statistical learning.
CSE 445: Học máy | Học kỳ 1, 2016-2017
46
Ridge vs. Lasso: Mô hình thưa
5 . 1
5 . 1
Ridge Least Squares
Lasso Least Squares
e t a m
e t a m
5 . 0
5 . 0
i t s E
i t s E
i
i
5 . 0 −
5 . 0 −
t n e c i f f e o C
t n e c i f f e o C
5 . 1 −
5 . 1 −
−1.5
−0.5 0.0
0.5
1.0
1.5
−1.5
−0.5 0.0
0.5
1.0
1.5
yj
yj
Hastie, Trevor, et al. Introduction to statistical learning.
CSE 445: Học máy | Học kỳ 1, 2016-2017
47
Câu hỏi?
CSE 445: Học máy | Học kỳ 1, 2016-2017
48
