Bài giảng Học máy - Bài 3: 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

Kỹ thuật kiểm tra chéo, hiệu chỉnh mô hình, mô hình thưa 1CSE 445: Học máy | Học kỳ 1, 2016-2017 Nguyễn Thanh Tùng Khoa Công nghệ thông tin – Đại học Thủy Lợi tungnt@tlu.edu.vn 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 Website môn học: https://sites.google.com/a/wru.vn/cse445spring2016/ 2Cluster Analysis Dimensionality Reduction Classification Regression KNN Supervised Unsupervised Yes No Do you have labeled data? Do you want to group the data? Yes No What do you want to predict? Category Quantity PCA Logistic Regression CART LASSOSVM ICA Linear Regression Các dạng giải thuật Học máy CSE 445: Học máy | Học kỳ 1, 2016-2017 K-means Nhắc lại Hồi quy tuyến tính đơn giản 3 Figure 3.1 , ISL 2013 CSE 445: Học máy | Học kỳ 1, 2016-2017 • 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.
(i) = (i)  ˆ (i) • Tổng phần dư bình phương-Residual sum of squares (RSS):  =
(1) 2 +
(2) 2 + ⋯+
(n) 2 • Lỗi bình phương trung bình-Mean squared error (MSE): Nhắc lại Bình phương nhỏ nhất 4CSE 445: Học máy | Học kỳ 1, 2016-2017 Hàm tổn thất Loss Functions 5CSE 445: Học máy | Học kỳ 1, 2016-2017 Loss Functions 6 ˆ i iL(θ ,θ ) CSE 445: Học máy | Học kỳ 1, 2016-2017 Loss Functions 7 Lỗi bình phương (Squared error) Lỗi tuyệt đối (Absolute error) iθ −θˆi∑ i ˆ i i(θ −θ )2∑ i Lỗi điều hướng (Indicator error) i ˆ iI(θ ≠ θ )∑ i ˆ i iL(θ ,θ ) CSE 445: Học máy | Học kỳ 1, 2016-2017 Học máy chỉ để giải 1 vấn đề 8CSE 445: Học máy | Học kỳ 1, 2016-2017 Kỹ thuật kiểm tra chéo Cross-validation 9CSE 445: Học máy | Học kỳ 1, 2016-2017 10 “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 Kỹ thuật kiểm tra chéo 11 Tập huấn luyện-Training Set Tập kiểmthử-Test Set Tập kiểm chứng-Validation Set CSE 445: Học máy | Học kỳ 1, 2016-2017 Kỹ thuật kiểm tra chéo Training Data Testing Data Kỹ thuật kiểm tra chéo K--fold Vídụ5--fold 12 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 13 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 Kỹ thuật kiểm tra chéo 14 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 Kỹ thuật kiểm tra chéo 15 • 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ánggiềnggần nhất) CSE 445: Học máy | Học kỳ 1, 2016-2017 Kỹ thuật kiểm tra chéo 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 17 Figures 2.4 and 2.6 ,ISL 2013 CSE 445: Học máy | Học kỳ 1, 2016-2017 • 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ử Thách thức: Overfitting 18 Figure2.9 , ISL 2013 Sai số trên tập huấn luyện 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 CSE 445: Học máy | Học kỳ 1, 2016-2017 Overfitting 19 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 Kỹ thuật kiểm tra chéo (đường cong của hàm học) Mô hình có điều chỉnh 20CSE 445: Học máy | Học kỳ 1, 2016-2017 Nhắc lại: Hồi quy tuyến tính đa biến 21 Figure3.4 , ISL 2013 Y = β0 + β1 ⋅ X1 + β2 ⋅X2 CSE 445: Học máy | Học kỳ 1, 2016-2017 22 khi có tương tác giữa các biến đầu vào 2 2 Y = β0 +β1 ⋅X1 +β2 ⋅X2 +β3 ⋅ (X1X2 )+β4 ⋅X1 +β5 ⋅X 2 +β6 ⋅ log(X1 / X2 )+β7 ⋅sin(X1 − X2 ) khi có quá nhiều biến đầu vào Y = β0 +β1 ⋅X1 +β2 ⋅X2 +β3 ⋅X3 +β4 ⋅X4 +β5 ⋅X5 +β6 ⋅X6 +β7 ⋅X7 +β8 ⋅X8 CSE 445: Học máy | Học kỳ 1, 2016-2017 Trường hợp quá nhiều biến 23 Y = β0 + β1 ⋅X1 Y = β0 + β1 ⋅ X1 + β2 ⋅ X2 Hai mẫu xác định 1 đường thẳng Ba mẫu xác định 1 mặt phẳng CSE 445: Học máy | Học kỳ 1, 2016-2017 Trường hợp quá nhiều biến 24 Y = β0 + β1 ⋅ X1 + β2 ⋅ X2 Hai mẫu không xác định một mặt phẳng duy nhất CSE 445: Học máy | Học kỳ 1, 2016-2017 Trường hợp quá nhiều biến 25 Y = β0 +β1 ⋅X1 +β2 ⋅X2 +β3 ⋅X3 +β4 ⋅X4 +β5 ⋅X5 +β6 ⋅X6 +β7 ⋅X7 +β8 ⋅X8 Gene expression arrays CSE 445: Học máy | Học kỳ 1, 2016-2017 Trường hợp quá nhiều biến 26 Y = β0 +β1 ⋅X1 +β2 ⋅X2 +β3 ⋅X3 +β4 ⋅X4 +β5 ⋅X5 +β6 ⋅X6 +β7 ⋅X7 +β8 ⋅X8 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 Điều gì xảy ra? Đa cộng tuyến (Multi-collinearity) 27 Y = β0 +β1 ⋅X1 +β2 ⋅X2 +β3 ⋅X3 +β4 ⋅X4 +β5 ⋅X5 +β6 ⋅X6 +β7 ⋅X7 +β8 ⋅X8 CSE 445: Học máy | Học kỳ 1, 2016-2017 Ta cần phải làm gì? 28 Phạt các hệ số β lớn. CSE 445: Học máy | Học kỳ 1, 2016-2017 29 30 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 0 1 1 2 2[Y − (β +β ⋅X +β ⋅X )]2∑ các mẫu CSE 445: Học máy | Học kỳ 1, 2016-2017 Hồi quy tuyến tính đa biến 30 ∑ samples 0 1 1 2 2 0 1 2 2 2 2 2[Y − (β +β ⋅X +β ⋅X )] +λ ⋅ (β +β +β ) Tìm giá trị β để cực tiểu lỗi phạt “penalized”, tương đương với L2 CSE 445: Học máy | Học kỳ 1, 2016-2017 Hồi quy Ridge 31 ∑ 0 1 1 2 2 0 1 2 2 2 2 2[Y − (β +β ⋅X +β ⋅X )] +λ ⋅ (β +β +β ) Hồi quy Ridge Tìm giá trị β để cực tiểu lỗi phạt “penalized”, tương đương với 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 Hiệu chỉnh mô hình (Regularization) 32 1e−01 1e+03 0 1 0 2 0 3 0 4 0 5 0 6 0 M e a n S q u a r e d E r r o r 1e+01 λ 60 Error 50 40 Squared 30 20 Mean 10 0 0.0 0.2 0.4 0.6 0.8 1.0 ∥ˆ ˆβR λ ∥2/∥β∥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ử? Hastie, Trevor, et al. Introduction to statistical learning. CSE 445: Học máy | Học kỳ 1, 2016-2017 Hồi quy Ridge 33 1e−01 1e+03 0 1 0 2 0 3 0 4 0 5 0 6 0 M e a n S q u a r e d E r r o r 1e+01 λ 60 Error 50 40 Squared 30 20 Mean 10 0 0.0 0.2 0.4 0.6 0.8 1.0 ∥ˆ ˆβR λ ∥2/∥β∥2 Hastie, Trevor, et al. Introduction to statistical learning. CSE 445: Học máy | Học kỳ 1, 2016-2017 Hồi quy Ridge 34 Ta đã xử lý: •Underdetermined •Overfitting •Đa cộng tuyến (Multi--collinearity) Vậy mô hình thưa là gì (sparsity)? Y = β0 +β1 ⋅X1 +β2 ⋅X2 +β3 ⋅X3 +β4 ⋅X4 +β5 ⋅X5 +β6 ⋅X6 +β7 ⋅X7 +β8 ⋅X8 0 0 0 CSE 445: Học máy | Học kỳ 1, 2016-2017 Hiệu chỉnh mô hình Mô hình thưa (Sparsity) 35 Y = β0 +β1 ⋅X1 +β2 ⋅X2 +β3 ⋅X3 +β4 ⋅X4 +β5 ⋅X5 +β6 ⋅X6 +β7 ⋅X7 +β8 ⋅X8 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 36 Lasso “Least absolute shrinkage and selection operator” Tibshirani, Robert. "Regression shrinkageandselection via the lasso." Journal of the Royal Statistical Society. Series B (Methodological)(1996): 267--288. [Y − (β0 + β1 ⋅ X1 +β2 2 2∑ samples ⋅X )] + λ⋅ (β0 + β1 + β2 ) L1 CSE 445: Học máy | Học kỳ 1, 2016-2017 Mô hình thưa (Sparsity) Mô hình giống như hồi quy Rigde nhưng khác hàm phạt 37 “Least absolute shrinkage and selection operator” [Y − (β0 + β1 ⋅ X1 +β2 2 2∑ ⋅X )] +λ ⋅ ( 0 1 2β + β + β ) samples hoặc viết ở dạng khác, CSE 445: Học máy | Học kỳ 1, 2016-2017 Lasso 38 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 0 0.2 0.4 1.6 1.8 2 XAxis Y A x i s L2 L1 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1 0 0.01 0.02 0.03 0.04 0.05 0.06 1.4 0.1 1.2 0.09 1 0.08 0.8 0.07 0.6 XAxis Y A x i s L2 x x2 Đường bậc 2 thô Kiểu đường bậc 2. CSE 445: Học máy | Học kỳ 1, 2016-2017 Phương thức phạt (Penalties) Các độ đo khoảng cách 39 x = x2 x1 + x2 x2 + x2 1 2-4 -3 -2 -1 0 1 2 3 4 5 -1 1 2 3 4 5 CSE 445: Học máy | Học kỳ 1, 2016-2017 Các độ đo khoảng cách được gọi là chuẩn - Norms 40 L1 L2 CSE 445: Học máy | Học kỳ 1, 2016-2017 Distance measures are called Norms 41CSE 445: Học máy | Học kỳ 1, 2016-2017 Các chuẩn, “Norms” 42 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 43 Ridge Lasso ≡ 50 ≡ CSE 445: Học máy | Học kỳ 1, 2016-2017 Mục tiêu khác: Mô hình thưa 44 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 Mục tiêu khác: Mô hình thưa 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 45CSE 445: Học máy | Học kỳ 1, 2016-2017 L1 (lasso) tính nhanh hơn và thưa 46 20 2000 5000 − 2 0 0 0 1 0 0 2 0 0 3 0 0 4 0 0 S t a n d a r d i z e d C o e f f i c i e n t s 50 100 200 500 λ Hastie, Trevor, et al. Introduction to statistical learning. CSE 445: Học máy | Học kỳ 1, 2016-2017 Ridge vs. Lasso: Mô hình thưa 47 −1.5 −0.5 0.0 0.5 1.0 1.5 − 1 . 5 − 0 . 5 0 . 5 1 . 5 C o e f f i c i e n t E s t i m a t e Ridge Least Squares −1.5 −0.5 0.0 0.5 1.0 1.5 − 1 . 5 − 0 . 5 0 . 5 1 . 5 C o e f f i c i e n t E s t i m a t e Lasso Hastie, Trevor, et al. Introduction to statistical learning. Least Squares yjyj CSE 445: Học máy | Học kỳ 1, 2016-2017 Câu hỏi? 48CSE 445: Học máy | Học kỳ 1, 2016-2017