🔙 Quay lại trang tải sách pdf ebook Machine Learning Cơ Bản
Ebooks
Nhóm Zalo
Machine Learning cơ bản
Cập nhật lần cuối: 20/01/2020.
Bản quyền ©2016 – 2020: Vũ Hữu Tiệp
Mọi hình thức sao chép, in ấn đều cần được sự đồng ý của tác giả. Mọi chia sẻ đều cần được dẫn nguồn tới https://github.com/tiepvupsu/ebookMLCB.
Mục lục
Mục lục
0 Lời nói đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 0.1 Mục đích của cuốn sách . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 0.2 Hướng tiếp cận của cuốn sách . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 0.3 Đối tượng của cuốn sách . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 0.4 Yêu cầu về kiến thức . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 0.5 Mã nguồn đi kèm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 0.6 Bố cục của cuốn sách . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 0.7 Các lưu ý về ký hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 0.8 Tham khảo thêm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 0.9 Đóng góp ý kiến . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 0.10 Lời cảm ơn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 0.11 Bảng các ký hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Phần I Kiến thức toán cơ bản
1 Ôn tập Đại số tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.1 Lưu ý về ký hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.2 Chuyển vị và Hermitian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4 Machine Learning cơ bản
Mục lục
1.3 Phép nhân hai ma trận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.4 Ma trận đơn vị và ma trận nghịch đảo. . . . . . . . . . . . . . . . . . . . . . . . . 27 1.5 Một vài ma trận đặc biệt khác . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.6 Định thức . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.7 Tổ hợp tuyến tính, không gian sinh . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 1.8 Hạng của ma trận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.9 Hệ trực chuẩn, ma trận trực giao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.10 Biễu diễn vector trong các hệ cơ sở khác nhau . . . . . . . . . . . . . . . . . . 34 1.11 Trị riêng và vector riêng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 1.12 Chéo hoá ma trận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 1.13 Ma trận xác định dương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 1.14 Chuẩn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 1.15 Vết . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2 Giải tích ma trận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.1 Gradient của hàm trả về một số vô hướng . . . . . . . . . . . . . . . . . . . . . 43 2.2 Gradient của hàm trả về vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.3 Tính chất quan trọng của gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.4 Gradient của các hàm số thường gặp . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.5 Bảng các gradient thường gặp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.6 Kiểm tra gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3 Ôn tập Xác suất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.1 Xác suất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.2 Một vài phân phối thường gặp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Machine Learning cơ bản 5
Mục lục
4 Ước lượng tham số mô hình . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.2 Ước lượng hợp lý cực đại . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 4.3 Ước lượng hậu nghiệm cực đại . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.4 Tóm tắt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
Phần II Tổng quan
5 Các khái niệm cơ bản. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 5.1 Nhiệm vụ, kinh nghiệm, phép đánh giá . . . . . . . . . . . . . . . . . . . . . . . . 80 5.2 Dữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.3 Các bài toán cơ bản trong machine learning . . . . . . . . . . . . . . . . . . . . 82 5.4 Phân nhóm các thuật toán machine learning . . . . . . . . . . . . . . . . . . . 84 5.5 Hàm mất mát và tham số mô hình . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6 Các kỹ thuật xây dựng đặc trưng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 6.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 6.2 Mô hình chung cho các bài toán machine learning . . . . . . . . . . . . . . 89 6.3 Một số kỹ thuật trích chọn đặc trưng . . . . . . . . . . . . . . . . . . . . . . . . . 91 6.4 Học chuyển tiếp cho bài toán phân loại ảnh . . . . . . . . . . . . . . . . . . . . 96 6.5 Chuẩn hoá vector đặc trưng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
7 Hồi quy tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 7.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 7.2 Xây dựng và tối ưu hàm mất mát . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 7.3 Ví dụ trên Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
6 Machine Learning cơ bản
Mục lục
7.4 Thảo luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
8 Quá khớp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 8.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 8.2 Xác thực . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 8.3 Cơ chế kiểm soát . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 8.4 Đọc thêm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
Phần III Khởi động
9 K lân cận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 9.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 9.2 Phân tích toán học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 9.3 Ví dụ trên cơ sở dữ liệu Iris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 9.4 Thảo luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
10 Phân cụm K-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 10.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 10.2 Phân tích toán học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 10.3 Ví dụ trên Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 10.4 Phân cụm chữ số viết tay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 10.5 Tách vật thể trong ảnh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 10.6 Nén ảnh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 10.7 Thảo luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
Machine Learning cơ bản 7
Mục lục
11 Bộ phân loại naive Bayes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 11.1 Bộ phân loại naive Bayes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 11.2 Các phân phối thường dùng trong NBC . . . . . . . . . . . . . . . . . . . . . . . 147 11.3 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 11.4 Thảo luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
Phần IV Mạng neuron nhân tạo
12 Gradient descent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 12.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 12.2 Gradient descent cho hàm một biến . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 12.3 Gradient descent cho hàm nhiều biến . . . . . . . . . . . . . . . . . . . . . . . . . . 164 12.4 Gradient descent với momentum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 12.5 Nesterov accelerated gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 12.6 Stochastic gradient descent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 12.7 Thảo luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
13 Thuật toán học perceptron . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 13.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 13.2 Thuật toán học perceptron . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 13.3 Ví dụ và minh hoạ trên Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 13.4 Mô hình mạng neuron đầu tiên . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 13.5 Thảo Luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
8 Machine Learning cơ bản
Mục lục
14 Hồi quy logistic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 14.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 14.2 Hàm mất mát và phương pháp tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . 188 14.3 Triển khai thuật toán trên Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 14.4 Tính chất của hồi quy logistic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 14.5 Bài toán phân biệt hai chữ số viết tay . . . . . . . . . . . . . . . . . . . . . . . . 195 14.6 Bài toán phân loại đa lớp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 14.7 Thảo luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
15 Hồi quy softmax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 15.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 15.2 Hàm softmax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 15.3 Hàm mất mát và phương pháp tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . 205 15.4 Ví dụ trên Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 15.5 Thảo luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
16 Mạng neuron đa tầng và lan truyền ngược . . . . . . . . . . . . . . . . . . . . 214 16.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 16.2 Các ký hiệu và khái niệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 16.3 Hàm kích hoạt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 16.4 Lan truyền ngược . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 16.5 Ví dụ trên Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 16.6 Suy giảm trọng số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 16.7 Đọc thêm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
Machine Learning cơ bản 9
Mục lục
Phần V Hệ thống gợi ý
17 Hệ thống gợi ý dựa trên nội dung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 17.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 17.2 Ma trận tiện ích . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 17.3 Hệ thống dựa trên nội dung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 17.4 Bài toán MovieLens 100k . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240 17.5 Thảo luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
18 Lọc cộng tác lân cận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 18.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 18.2 Lọc cộng tác theo người dùng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 18.3 Lọc cộng tác sản phẩm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 18.4 Lập trình trên Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 18.5 Thảo luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
19 Lọc cộng tác phân tích ma trận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 19.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 19.2 Xây dựng và tối ưu hàm mất mát . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 19.3 Lập trình Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 19.4 Thảo luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
10 Machine Learning cơ bản
Mục lục
Phần VI Giảm chiều dữ liệu
20 Phân tích giá trị suy biến. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266 20.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266 20.2 Phân tích giá trị suy biến . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267 20.3 Phân tích giá trị suy biến cho bài toán nén ảnh . . . . . . . . . . . . . . . . . 271 20.4 Thảo luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
21 Phân tích thành phần chính . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 21.1 Phân tích thành phần chính. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 21.2 Các bước thực hiện phân tích thành phần chính . . . . . . . . . . . . . . . . 279 21.3 Liên hệ với phân tích giá trị suy biến . . . . . . . . . . . . . . . . . . . . . . . . . . 280 21.4 Làm thế nào để chọn số chiều của dữ liệu mới . . . . . . . . . . . . . . . . . . 282 21.5 Lưu ý về tính toán phân tích thành phần chính . . . . . . . . . . . . . . . . . 282 21.6 Một số ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283 21.7 Thảo luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
22 Phân tích biệt thức tuyến tính. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288 22.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288 22.2 Bài toán phân loại nhị phân . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290 22.3 Bài toán phân loại đa lớp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293 22.4 Ví dụ trên Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 22.5 Thảo luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
Machine Learning cơ bản 11
Mục lục
Phần VII Tối ưu lồi
23 Tập lồi và hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 23.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 23.2 Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304 23.3 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309 23.4 Tóm tắt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
24 Bài toán tối ưu lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 24.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 24.2 Nhắc lại bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324 24.3 Bài toán tối ưu lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326 24.4 Quy hoạch tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 24.5 Quy hoạch toàn phương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332 24.6 Quy hoạch hình học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334 24.7 Tóm tắt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
25 Đối ngẫu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 25.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 25.2 Hàm đối ngẫu Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 25.3 Bài toán đối ngẫu Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342 25.4 Các điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344 25.5 Tóm tắt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
12 Machine Learning cơ bản
Mục lục
Phần VIII Máy vector hỗ trợ
26 Máy vector hỗ trợ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350 26.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350 26.2 Xây dựng bài toán tối ưu cho máy vector hỗ trợ . . . . . . . . . . . . . . . . 352 26.3 Bài toán đối ngẫu của máy vector hỗ trợ . . . . . . . . . . . . . . . . . . . . . . . 354 26.4 Lập trình tìm nghiệm cho máy vector hỗ trợ . . . . . . . . . . . . . . . . . . . 357 26.5 Tóm tắt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359
27 Máy vector hỗ trợ lề mềm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361 27.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361 27.2 Phân tích toán học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362 27.3 Bài toán đối ngẫu Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364 27.4 Bài toán tối ưu không ràng buộc cho SVM lề mềm . . . . . . . . . . . . . 367 27.5 Lập trình với SVM lề mềm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372 27.6 Tóm tắt và thảo luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
28 Máy vector hỗ trợ hạt nhân . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378 28.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378 28.2 Cơ sở toán học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380 28.3 Hàm số hạt nhân . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382 28.4 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384 28.5 Tóm tắt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
Machine Learning cơ bản 13
Mục lục
29 Máy vector hỗ trợ đa lớp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387 29.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387 29.2 Xây dựng hàm mất mát . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390 29.3 Tính toán giá trị và gradient của hàm mất mát . . . . . . . . . . . . . . . . . 393 29.4 Thảo luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 400
A Phương pháp nhân tử Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402 B Ảnh màu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
14 Machine Learning cơ bản
Chương 0. Lời nói đầu
Chương 0
Lời nói đầu
Những năm gần đây, trí tuệ nhân tạo (artificial intelligence, AI) dần nổi lên như một minh chứng cho cuộc cách mạng công nghiệp lần thứ tư, sau động cơ hơi nước, năng lượng điện và công nghệ thông tin. Trí tuệ nhân tạo đã và đang trở thành nhân tố cốt lõi trong các hệ thống công nghệ cao. Thậm chí, nó đã len lỏi vào hầu hết các lĩnh vực của đời sống mà có thể chúng ta không nhận ra. Xe tự hành của Google và Tesla, hệ thống tự tag khuôn mặt trong ảnh của Facebook, trợ lý ảo Siri của Apple, hệ thống gợi ý sản phẩm của Amazon, hệ thống gợi ý phim của Netflix, hệ thống dịch đa ngôn ngữ Google Translate, máy chơi cờ vây AlphaGo và gần đây là AlphaGo Zero của Google DeepMind,... chỉ là một vài ứng dụng nổi bật trong vô vàn những ứng dụng của trí tuệ nhân tạo.
Học máy (machine learning, ML) là một tập con của trí tuệ nhân tạo. Machine learning là một lĩnh vực nhỏ trong khoa học máy tính, có khả năng tự học hỏi dựa trên dữ liệu được đưa vào mà không cần phải được lập trình cụ thể (Machine Learning is the subfield of computer science, that “gives computers the ability to learn without being explicitly programmed” – Wikipedia).
Những năm gần đây, sự phát triển của các hệ thống tính toán cùng lượng dữ liệu khổng lồ được thu thập bởi các hãng công nghệ lớn đã giúp machine learning tiến thêm một bước dài. Một lĩnh vực mới được ra đời được gọi là học sâu (deep learning, DL). Deep learning đã giúp máy tính thực thi những việc vào mười năm trước tưởng chừng là không thể: phân loại cả ngàn vật thể khác nhau trong các bức ảnh, tự tạo chú thích cho ảnh, bắt chước giọng nói và chữ viết, giao tiếp với con người, chuyển đổi ngôn ngữ, hay thậm chí cả sáng tác văn thơ và âm nhạc1.
1 Đọc thêm: 8 Inspirational Applications of Deep Learning (https://goo.gl/Ds3rRy). Machine Learning cơ bản 15
Chương 0. Lời nói đầu
Hình 0.1. Mối quan hệ giữa AI, ML, và DL. (Nguồn What’s the Difference Be tween Artificial Intelligence, Machine Learning, and Deep Learning? – https://goo. gl/NNwGCi).
Mối quan hệ AI-ML-DL
DL là một tập con của ML. ML là một tập con của AI (xem Hình 0.1).
0.1. Mục đích của cuốn sách
Những phát triển thần kỳ của trí tuệ nhân tạo dẫn tới nhu cầu cao về mặt nhần lực làm việc trong các ngành liên quan tới machine learning ở Việt Nam cũng như trên thế giới. Đó cũng là nguồn động lực để tác giả gây dựng và phát triển blog Machine Learning cơ bản từ đầu năm 2017 (https://machinelearningcoban.com). Tính tới thời điểm đặt bút viết những dòng này, blog đã có hơn một triệu lượt ghé thăm. Facebook page Machine Learning cơ bản2chạm mốc 14 nghìn lượt likes, Forum Machine Learning cơ bản3 đạt tới 17 nghìn thành viên. Trong quá trình viết blog và duy trì các trang Facebook, tác giả đã nhận được nhiều sự ủng hộ của bạn đọc về tinh thần cũng như vật chất. Nhiều bạn đọc cũng khuyến khích tác giả tổng hợp kiến thức trên blog thành một cuốn sách cho cộng đồng những người tiếp cận với ML bằng tiếng Việt. Sự ủng hộ và những lời động viên đó là động lực lớn cho tác giả khi bắt tay vào thực hiện và hoàn thành cuốn sách này.
2https://goo.gl/wyUEjr
3https://goo.gl/gDPTKX
16 Machine Learning cơ bản
Chương 0. Lời nói đầu
Lĩnh vực ML nói chung và DL nói riêng là cực kỳ lớn và có nhiều nhánh nhỏ. Phạm vi một cuốn sách chắc chắn không thể bao quát hết mọi vấn đề và đi sâu vào từng nhánh cụ thể. Do vậy, cuốn sách này chỉ nhằm cung cấp cho bạn đọc những khái niệm, kỹ thuật chung và các thuật toán cơ bản nhất của ML. Từ đó, bạn đọc có thể tự tìm thêm các cuốn sách và khóa học liên quan nếu muốn đi sâu vào từng vấn đề.
Hãy nhớ rằng luôn bắt đầu từ những điều đơn giản. Khi bắt tay vào giải quyết một bài toán ML hay bất cứ bài toán nào, chúng ta nên bắt đầu từ những thuật toán đơn giản. Không phải chỉ có những thuật toán phức tạp mới có thể giải quyết được vấn đề. Những thuật toán phức tạp thường có yêu cầu cao về khả năng tính toán và đôi khi nhạy cảm với cách chọn tham số. Ngược lại, những thuật toán đơn giản giúp chúng ta nhanh chóng có một bộ khung cho mỗi bài toán. Kết quả của các thuật toán đơn giản cũng mang lại cái nhìn sơ bộ về sự phức tạp của mỗi bài toán. Việc cải thiện kết quả sẽ được thực hiện dần ở các bước sau. Cuốn sách này sẽ trang bị cho bạn đọc những kiến thức khái quát và một số hướng tiếp cận cơ bản cho các bài toán ML. Để tạo ra các sản phẩm thực tiễn, chúng ta cần học hỏi và thực hành thêm nhiều.
0.2. Hướng tiếp cận của cuốn sách
Để giải quyết mỗi bài toán ML, chúng ta cần chọn một mô hình phù hợp. Mô hình này được mô tả bởi bộ các tham số mà chúng ta cần đi tìm. Thông thường, lượng tham số có thể lên tới hàng triệu và được tìm bằng cách giải một bài toán tối ưu.
Khi viết về các thuật toán ML, tác giả sẽ bắt đầu từ những ý tưởng trực quan. Những ý tưởng này được mô hình hoá dưới dạng một bài toán tối ưu. Các suy luận toán học và ví dụ mẫu trên Python ở cuối mỗi chương sẽ giúp bạn đọc hiểu rõ hơn về nguồn gốc, ý nghĩa, và cách sử dụng mỗi thuật toán. Xen kẽ giữa những thuật toán ML, tác giả sẽ trình bày các kỹ thuật tối ưu cơ bản, với hy vọng giúp bạn đọc hiểu rõ hơn bản chất của vấn đề.
0.3. Đối tượng của cuốn sách
Cuốn sách được thực hiện hướng tới nhiều nhóm độc giả khác nhau. Nếu bạn không thực sự muốn đi sâu vào phần toán, bạn vẫn có thể tham khảo mã nguồn và cách sử dụng các thư viện. Nhưng để sử dụng các thư viện một cách hiệu quả, bạn cũng cần hiểu nguồn gốc của mô hình và ý nghĩa của các tham số. Còn nếu bạn thực sự muốn tìm hiểu nguồn gốc, ý nghĩa của các thuật toán, bạn có thể học được nhiều điều từ cách xây dựng và tối ưu các mô hình. Phần tổng hợp các kiến thức toán cần thiết trong Phần I sẽ là một nguồn tham khảo súc tích bất cứ khi nào bạn có thắc mắc về các dẫn giải toán học. Phần VII được dành riêng để
Machine Learning cơ bản 17
Chương 0. Lời nói đầu
nói về tối ưu lồi – một mảng quan trọng trong tối ưu, phù hợp với các bạn thực sự muốn đi sâu thêm về tối ưu.
Các dẫn giải toán học được xây dựng phù hợp với chương trình toán phổ thông và đại học ở Việt Nam. Các từ khóa khi được dịch sang tiếng Việt đều dựa trên những tài liệu tác giả được học trong nhiều năm tại Việt Nam.
Phần cuối cùng của sách có mục Index các thuật ngữ quan trọng và thuật ngữ tiếng Anh đi kèm giúp bạn dần làm quen khi đọc các tài liệu tiếng Anh.
0.4. Yêu cầu về kiến thức
Để có thể bắt đầu đọc cuốn sách này, bạn cần có một kiến thức nhất định về đại số tuyến tính, giải tích ma trận, xác suất thống kê, và kỹ năng lập trình.
Phần I của cuốn sách ôn tập lại các kiến thức toán quan trọng được dùng trong ML. Khi gặp khó khăn về toán, bạn được khuyến khích đọc lại các chương trong phần này.
Ngôn ngữ lập trình được sử dụng trong cuốn sách là Python. Python là một ngôn ngữ lập trình miễn phí, có thể được cài đặt dễ dàng trên các nền tảng hệ điều hành khác nhau. Quan trọng hơn, có rất nhiều thư viện hỗ trợ ML cũng như DL trên Python. Có hai thư viện Python chính thường được sử dụng trong cuốn sách là numpy và scikit-learn.
Numpy (http://www.numpy.org/) là một thư viện phổ biến giúp xử lý các phép toán liên quan đến các mảng nhiều chiều, hỗ trợ các hàm gần gũi với đại số tuyến tính. Nếu bạn đọc chưa quen thuộc với numpy, bạn có thể tham gia một khóa học ngắn miễn phí trên trang web kèm theo cuốn sách này (https://fundaml.com). Bạn sẽ được làm quen với cách xử lý các mảng nhiều chiều với nhiều ví dụ và bài tập thực hành. Các kỹ thuật xử lý mảng trong cuốn sách này đều được đề cập tại đây.
Scikit-learn, hay sklearn (http://scikit-learn.org/), là một thư viện chứa đầy đủ các thuật toán ML cơ bản và rất dễ sử dụng. Tài liệu của scikit-learn cũng là một nguồn tham khảo chất lượng cho các bạn làm ML. Scikit-learn sẽ được dùng trong cuốn sách để kiểm chứng các suy luận toán học và các mô hình được xây dựng thông qua numpy.
Có rất nhiều thư viện giúp chúng ta tạo ra các sản phẩm ML/DL mà không yêu cầu nhiều kiến thức toán. Tuy nhiên, cuốn sách này hướng tới việc giúp bạn đọc hiểu bản chất toán học đằng sau mỗi mô hình trước khi áp dụng các thư viện sẵn có. Việc sử dụng thư viện cũng yêu cầu kiến thức nhất định về việc lựa chọn mô hình và điều chỉnh các tham số.
18 Machine Learning cơ bản
Chương 0. Lời nói đầu
0.5. Mã nguồn đi kèm
Toàn bộ mã nguồn trong cuốn sách có thể được tìm thấy tại https://goo.gl/ Fb2p4H. Các file có đuôi .ipynb là các Jupyter notebook chứa mã nguồn. Các file có đuôi .pdf, và .png là các hình vẽ được sử dụng trong cuốn sách.
0.6. Bố cục của cuốn sách
Cuốn sách này được chia thành 8 phần và sẽ tiếp tục được cập nhật:
Phần I ôn tập lại những kiến thức quan trọng trong đại số tuyến tính, giải tích ma trận, xác suất, và hai phương pháp phổ biến trong việc ước lượng tham số cho các mô hình ML dựa trên thống kê.
Phần II giới thiệu các khái niệm cơ bản trong ML, các kỹ thuật xây dựng vector đặc trưng cho dữ liệu, một mô hình ML cơ bản – hồi quy, và một hiện tượng cần tránh khi xây dựng các mô hình ML.
Phần III giúp các bạn làm quen với các mô hình ML không yêu cầu nhiều kiến thức toán phức tạp. Qua đây, bạn đọc sẽ có cái nhìn sơ bộ về việc xây dựng các mô hình ML.
Phần IV đề cập tới một nhóm các thuật toán ML phổ biến nhất – mạng neuron nhân tạo, là nền tảng cho các mô hình DL phức tạp hiện nay. Phần này cũng giới thiệu một kỹ thuật tối ưu phổ biến cho các bài toán tối ưu không ràng buộc.
Phần V giới thiệu về các kỹ thuật thường dùng trong các hệ thống gợi ý sản phẩm.
Phần VI giới thiệu các kỹ thuật giảm chiều dữ liệu.
Phần VII trình bày cụ thể hơn về tối ưu, đặc biệt là tối ưu lồi. Các bài toán tối ưu lồi có ràng buộc cũng được giới thiệu trong phần này.
Phần VIII giới thiệu các thuật toán phân loại dựa trên máy vector hỗ trợ. 0.7. Các lưu ý về ký hiệu
Các ký hiệu toán học trong sách được mô tả ở Bảng 0.1 và đầu Chương 1. Các khung với font chữ có cùng chiều rộng được dùng để chứa các đoạn mã nguồn.
text in a box with constant width represents source codes.
Các đoạn ký tự với constant width (có cùng chiều rộng) được dùng để chỉ các biến, hàm số, chuỗi,... trong các đoạn mã.
Machine Learning cơ bản 19
Chương 0. Lời nói đầu
Đóng khung và in nghiêng
Các khái niệm, định nghĩa, định lý, và lưu ý quan trọng được đóng khung và in nghiêng.
Ký tự phân cách giữa phần nguyên và phần thập phân của các số thực là dấu chấm (.) thay vì dấu phẩy (,) như trong các tài liệu tiếng Việt khác. Cách làm này thống nhất với các tài liệu tiếng Anh và các ngôn ngữ lập trình.
0.8. Tham khảo thêm
Có nhiều cuốn sách, khóa học, website hay về machine learning/deep learning. Trong đó, tôi xin đặc biệt nhấn mạnh các nguồn tham khảo sau:
0.8.1. Khoá học
a. Khoá học Machine Learning của Andrew Ng trên Coursera (https://goo.gl/ WBwU3K).
b. Khoá học mới Deep Learning Specialization cũng của Andrew Ng trên Cours era (https://goo.gl/ssXfYN).
c. Các khóa CS224n: Natural Language Processing with Deep Learning (https: //goo.gl/6XTNkH); CS231n: Convolutional Neural Networks for Visual Recog nition (http://cs231n.stanford.edu/); CS246: Mining Massive Data Sets (https: //goo.gl/TEMQ9H) của Stanford.
0.8.2. Sách
a. C. Bishop, Pattern Recognition and Machine Learning (https://goo.gl/pjgqRr), Springer, 2006 [Bis06].
b. I. Goodfellow et al., Deep Learning (https://goo.gl/sXaGwV), MIT press, 2016 [GBC16].
c. J. Friedman et al., The Elements of Statistical Learning (https://goo.gl/ Qh9EkB), Springer, 2001 [FHT01].
d. Y. Abu-Mostafa et al., Learning from data (https://goo.gl/SRfNFJ), AML Book New York, 2012 [AMMIL12].
e. S. JD Prince, Computer Vision: Models, Learning, and Inference (https://goo. gl/9Fchf3), Cambridge University Press, 2012 [Pri12].
20 Machine Learning cơ bản
Chương 0. Lời nói đầu
f. S. Boyd et al., Convex Optimization (https://goo.gl/NomDpC), Cambridge university press, 2004 [BV04].
Ngoài ra, các website Machine Learning Mastery (https://goo.gl/5DwGbU), Py imagesearch (https://goo.gl/5DwGbU). Kaggle (https://www.kaggle.com/), Scikit learn (http://scikit-learn.org/) cũng là các nguồn thông tin hữu ích.
0.9. Đóng góp ý kiến
Các bạn có thể gửi các đóng góp tới địa chỉ email [email protected] hoặc tạo một GitHub issue mới tại https://goo.gl/zPYWKV.
0.10. Lời cảm ơn
Trước hết, tôi xin được cảm ơn sự ủng hộ và chia sẻ nhiệt tình của bạn bè trên Facebook từ những ngày đầu ra mắt blog. Xin được gửi lời cảm ơn chân thành tới bạn đọc Machine Learning cơ bản đã đồng hành trong hơn một năm qua.
Tôi cũng may mắn nhận được những góp ý và phản hồi tích cực từ các thầy cô tại các trường đại học lớn trong và ngoài nước. Xin phép được gửi lời cảm ơn tới thầy Phạm Ngọc Nam và cô Nguyễn Việt Hương (ĐH Bách Khoa Hà Nội), thầy Chế Viết Nhật Anh (ĐH Bách Khoa TP.HCM), thầy Nguyễn Thanh Tùng (ĐH Thuỷ Lợi), và thầy Trần Duy Trác (ĐH Johns Hopkins).
Đặc biệt, xin cảm ơn Nguyễn Hoàng Linh và Hoàng Đức Huy, Đại học Waterloo, Canada đã nhiệt tình giúp tôi xây dựng trang FundaML.com, cho phép độc giả học Python/Numpy trực tiếp trên trình duyệt. Xin cảm ơn các bạn Nguyễn Tiến Cường, Nguyễn Văn Giang, Vũ Đình Quyền, Lê Việt Hải, và Đinh Hoàng Phong đã góp ý sửa đổi nhiều điểm trong các bản nháp.
Ngoài ta, cũng xin cảm ơn những người bạn thân của tôi tại Penn State (ĐH bang Pennsylvania) đã luôn bên cạnh tôi trong thời gian tôi thực hiện dự án, bao gồm gia đình anh Triệu Thanh Quang, gia đình anh Trần Quốc Long, bạn thân Nguyễn Phương Chi, và các đồng nghiệp tại Phòng nghiên cứu Xử lý Thông tin và Thuật toán (Information Processing and Algorithm Laboratory, iPAL).
Cuối cùng và quan trọng nhất, xin gửi lời cảm ơn sâu sắc nhất tới gia đình tôi, những người luôn ủng hộ vô điều kiện và hỗ trợ tôi hết mình trong quá trình thực hiện dự án này.
0.11. Bảng các ký hiệu
Các ký hiệu sử dụng trong sách được liệt kê trong Bảng 0.1 ở trang tiếp theo. Machine Learning cơ bản 21
Chương 0. Lời nói đầu
Bảng 0.1: Các quy ước ký hiệu và tên gọi được sử dụng trong sách
Ký hiệu
Ý nghĩa
x, y, N, k
in nghiêng, thường hoặc hoa, là các số vô hướng
x, y
in đậm, chữ thường, là các vector
X, Y
in đậm, chữ hoa, là các ma trận
R
tập hợp các số thực
N
tập hợp các số tự nhiên
C
tập hợp các số phức
Rm
tập hợp các vector thực có m phần tử
Rm×n
tập hợp các ma trận thực có m hàng, n cột
Sn
tập hợp các ma trận vuông đối xứng bậc n
Sn+
tập hợp các ma trận nửa xác định dương bậc n
Sn++
tập hợp các ma trận xác định dương bậc n
∈
phần tử thuộc tập hợp
∃
tồn tại
∀
mọi
,
ký hiệu là/bởi. Ví dụ a , f(x) nghĩa là “ký hiệu f(x) bởi a”.
xi
phần tử thứ i (tính từ 1) của vector x
sgn(x)
hàm xác định dấu. Bằng 1 nếu x ≥ 0, bằng -1 nếu x < 0.
exp(x)
ex
log(x)
logarit tự nhiên của số thực dương x
f(x)
argmin
x
giá trị của x để hàm f(x) đạt giá trị nhỏ nhất
f(x)
argmax
x
giá trị của x để hàm f(x) đạt giá trị lớn nhất
aij
phần tử hàng thứ i, cột thứ j của ma trận A
AT
chuyển vị của ma trận A
AH
chuyển vị liên hợp (Hermitian) của ma trận phức A
A−1
nghịch đảo của ma trận vuông A, nếu tồn tại
A†
giả nghịch đảo của ma trận không nhất thiết vuông A
A−T
chuyển vị của nghịch đảo của ma trận A, nếu tồn tại
kxkp
`p norm của vector x
kAkF
Frobenius norm của ma trận A
diag(A)
đường chéo chính của ma trận A
trace(A)
trace của ma trận A
det(A)
định thức của ma trận vuông A
rank(A)
hạng của ma trận A
o.w
otherwise – trong các trường hợp còn lại
∂f
∂x
đạo hàm của hàm số f theo x ∈ R
∇xf
gradient của hàm số f theo x (x là vector hoặc ma trận)
∇2xf
gradient bậc hai của hàm số f theo x, còn được gọi là Hesse
Hadamard product (elemenwise product). Phép nhân từng phần tửcủa hai vector hoặc ma trận cùng kích thước.
∝
tỉ lệ với
đường nét liền
đường nét đứt
đường nét chấm (đường chấm chấm)
đường chấm gạch
nền chấm
nền sọc chéo
22 Machine Learning cơ bản
Phần I
Kiến thức toán cơ bản
Chương 1. Ôn tập Đại số tuyến tính
Chương 1
Ôn tập Đại số tuyến tính
1.1. Lưu ý về ký hiệu
Trong cuốn sách này, những số vô hướng được biểu diễn bởi các chữ cái in nghiêng và có thể viết hoa, ví dụ x1, N, y, k. Các ma trận được biểu diễn bởi các chữ viết hoa in đậm, ví dụ X, Y,W. Các vector được biểu diễn bởi các chữ cái thường in đậm, ví dụ y, x1. Nếu không giải thích gì thêm, các vector được mặc định hiểu là các vector cột.
Đối với vector, x = [x1, x2, . . . , xn] được hiểu là một vector hàng, x = [x1; x2; . . . ; xn] được hiểu là vector cột. Chú ý sự khác nhau giữa dấu phẩy (,) và dấu chấm phẩy (;). Đây chính là ký hiệu được Matlab sử dụng. Nếu không giải thích gì thêm, một chữ cái viết thường in đậm được hiểu là một vector cột.
Tương tự, trong ma trận, X = [x1, x2, . . . , xn] được hiểu là các vector cột xj được đặt cạnh nhau theo thứ tự từ trái qua phải để tạo ra ma trận X. Trong khi X = [x1; x2; . . . ; xm] được hiểu là các vector xi được đặt chồng lên nhau theo thứ tự từ trên xuống dưới dể tạo ra ma trận X. Các vector được ngầm hiểu là có kích thước phù hợp để có thể xếp cạnh hoặc xếp chồng lên nhau. Phần tử ở hàng thứ i, cột thứ j được ký hiệu là xij .
Cho một ma trận W, nếu không giải thích gì thêm, ta hiểu rằng wilà vector cột thứ i của ma trận đó. Chú ý sự tương ứng giữa ký tự viết hoa và viết thường.
1.2. Chuyển vị và Hermitian
Cho một ma trận/vector A ∈ Rm×n, ta nói B ∈ Rn×m là chuyển vị (transpose) của A nếu bij = aji, ∀1 ≤ i ≤ n, 1 ≤ j ≤ m.
24 Machine Learning cơ bản
Chương 1. Ôn tập Đại số tuyến tính
Chuyển vị của ma trận A được ký hiệu là AT. Cụ thể hơn:
x =
x1
x2...
xm
⇒ xT = x1 x2 . . . xm ;
A =
a11 a12 . . . a1n
a21 a22 . . . a2n . . . . . .... . . . am1 am2 . . . amn
⇒ AT =
a11 a21 . . . am1
a12 a22 . . . am2 . . . . . .... . . . a1n a2n . . . amn
Nếu A ∈ Rm×nthì AT ∈ Rn×m. Nếu AT = A, ta nói A là một ma trận đối xứng.
Trong trường hợp vector hay ma trận có các phần tử là số phức, việc lấy chuyển vị thường đi kèm với việc lấy liên hợp phức. Tức là ngoài việc đổi vị trí của các phần tử, ta còn lấy liên hợp phức của các phần tử đó. Tên gọi của phép toán chuyển vị và lấy liên hợp này còn được gọi là chuyển vị liên hợp (conjugate transpose), và thường được ký hiệu bằng chữ H thay cho chữ T. Chuyển vị liên hợp của một ma trận A được ký hiệu là AH, được đọc là A Hermitian.
Cho A ∈ Cm×n, ta nói B ∈ Cn×m là chuyển vị liên hợp của A nếu bij = aji, ∀1 ≤ i ≤ n, 1 ≤ j ≤ m, trong đó a là liên hiệp phức của a.
Ví dụ:
A =
1 + 2i 3 − 4i i 2
⇒ AH =
1 − 2i −i 3 + 4i 2
(1.1)
Nếu A, x là các ma trận và vector thực thì AH = AT, xH = xT.
Nếu chuyển vị liên hợp của một ma trận vuông phức bằng với chính nó, AH = A, ta nói ma trận đó là Hermitian.
1.3. Phép nhân hai ma trận
Cho hai ma trận A ∈ Rm×n, B ∈ Rn×p, tích của hai ma trận được ký hiệu là C = AB ∈ Rm×ptrong đó phần tử ở hàng thứ i, cột thứ j của ma trận kết quả
được tính bởi:
cij =Xn k=1
aikbkj , ∀1 ≤ i ≤ m, 1 ≤ j ≤ p (1.2)
Để nhân được hai ma trận, số cột của ma trận thứ nhất phải bằng số hàng của ma trận thứ hai. Trong ví dụ trên, chúng đều bằng n.
Machine Learning cơ bản 25
Chương 1. Ôn tập Đại số tuyến tính
Giả sử kích thước các ma trận là phù hợp để các phép nhân ma trận tồn tại, ta có một vài tính chất sau:
a. Phép nhân ma trận không có tính chất giao hoán. Thông thường (không phải luôn luôn), AB 6= BA. Thậm chí, trong nhiều trường hợp, các phép tính này không tồn tại vì kích thước các ma trận lệch nhau.
b. Phép nhân ma trận có tính chất kết hợp: ABC = (AB)C = A(BC).
c. Phép nhân ma trận có tính chất phân phối đối với phép cộng: A(B + C) = AB + AC.
d. Chuyển vị của một tích bằng tích các chuyển vị theo thứ tự ngược lại. Điều tương tự xảy ra với Hermitian của một tích:
(AB)T = BTAT; (AB)H = BHAH (1.3)
Tích trong, hay tích vô hướng (inner product) của hai vector x, y ∈ Rn được định
nghĩa bởi:
xT y = yT x =Xn i=1
xiyi (1.4)
Nếu tích vô hướng của hai vector khác không bằng không, ta nói hai vector đó trực giao (orthogonal).
Chú ý, xHy và yHx bằng nhau khi và chỉ khi chúng là các số thực.
xHx ≥ 0, ∀x ∈ Cn vì tích của một số phức với liên hiệp của nó luôn là một số không âm.
Phép nhân của một ma trận A ∈ Rm×n với một vector x ∈ Rnlà một vector b ∈ Rm:
Ax = b, với bi = Ai,:x (1.5)
với Ai,:là vector hàng thứ i của A.
Ngoài ra, có một phép nhân khác được gọi là phép nhân từng thành phần hay tích Hadamard (Hadamard product) thường xuyên được sử dụng trong machine learning. Tích Hadamard của hai ma trận cùng kích thước A, B ∈ Rm×n, được ký hiệu là C = A B ∈ Rm×n, trong đó:
cij = aij bij (1.6)
26 Machine Learning cơ bản
Chương 1. Ôn tập Đại số tuyến tính
1.4. Ma trận đơn vị và ma trận nghịch đảo
1.4.1. Ma trận đơn vị
Đường chéo chính của một ma trận là tập hợp các điểm có chỉ số hàng và cột bằng nhau. Cách định nghĩa này cũng có thể được áp dụng cho một ma trận không vuông. Cụ thể, nếu A ∈ Rm×nthì đường chéo chính của A bao gồm {a11, a22, . . . , app}, trong đó p = min{m, n}.
Một ma trận đơn vị bậc n là một ma trận đặc biệt trong Rn×n với các phần tử trên đường chéo chính bằng 1, các phần tử còn lại bằng 0. Ma trận đơn vị thường được ký hiệu là I. Khi làm việc với nhiều ma trận đơn vị với bậc khác nhau, ta thường ký kiệu In cho ma trận đơn vị bậc n. Dưới đây là các ma trận đơn vị bậc
3 và bậc 4:
I3 =
1 0 0 0 1 0 0 0 1
, I4 =
1 0 0 0
0 1 0 0 0 0 1 0 0 0 0 1
(1.7)
Ma trận đơn vị có một tính chất đặc biệt trong phép nhân. Nếu A ∈ Rm×n, B ∈ Rn×m và I là ma trận đơn vị bậc n, ta có: AI = A, IB = B.
Với mọi vector x ∈ Rn, ta có Inx = x.
1.4.2. Ma trận nghịch đảo
Cho một ma trận vuông A ∈ Rn×n, nếu tồn tại một ma trận vuông B ∈ Rn×n sao cho AB = In, ta nói A là khả nghịch, và B được gọi là ma trận nghịch đảo của A. Nếu không tồn tại ma trận B thoả mãn điều kiện trên, ta nói rằng ma trận A là không khả nghịch.
Nếu A khả nghịch, ma trận nghịch đảo của nó được ký hiệu là A−1. Ta cũng có: A−1A = AA−1 = I (1.8)
Ma trận nghịch đảo thường được sử dụng để giải hệ phương trình tuyến tính. Giả sử A ∈ Rn×nlà một ma trận khả nghịch và b là một vector bất kỳ trong Rn. Khi đó, phương trình:
Ax = b (1.9)
có nghiệm duy nhất x = A−1b. Thật vậy, nhân bên trái cả hai vế của phương trình với A−1, ta có Ax = b ⇔ A−1Ax = A−1b ⇔ x = A−1b.
Nếu A không khả nghịch, thậm chí không vuông, phương trình tuyến tính (1.9) có thể không có nghiệm hoặc có vô số nghiệm.
Machine Learning cơ bản 27
Chương 1. Ôn tập Đại số tuyến tính
Giả sử các ma trận vuông A, B là khả nghịch, khi đó tích của chúng cũng khả nghịch, và (AB)−1 = B−1A−1. Quy tắc này cũng giống với cách tính ma trận chuyển vị của tích các ma trận.
1.5. Một vài ma trận đặc biệt khác
1.5.1. Ma trận đường chéo
Ma trận đường chéo là ma trận mà các thành phần khác không chỉ nằm trên đường chéo chính. Định nghĩa này cũng có thể được áp dụng lên các ma trận không vuông. Ma trận không (tất cả các phần tử bằng 0) và đơn vị là các ma trận
đường chéo. Một vài ví dụ về các ma trận đường chéo: 1 , 2 0
,
0 0
1 0 0 0 2 0
,
−1 0 0 2 0 0
.
Với các ma trận đường chéo vuông, thay vì viết cả ma trận, ta có thể chỉ liệt kê các thành phần trên đường chéo chính. Ví dụ, một ma trận đường chéo vuông A ∈ Rm×m có thể được ký hiệu là diag(a11, a22, . . . , amm) với aii là phần tử hàng thứ i, cột thứ i của ma trận A.
Tích, tổng của hai ma trận đường chéo vuông cùng bậc là một ma trận đường chéo. Một ma trận đường chéo vuông là khả nghịch khi và chỉ khi mọi phần tử trên đường chéo chính của nó khác không. Nghịch đảo của một ma trận đường chéo khả nghịch cũng là một ma trận đường chéo. Cụ thể hơn, (diag(a1, a2, . . . , an))−1 = diag(a−1
1, a−1
2, . . . , a−1
n).
1.5.2. Ma trận tam giác
Một ma trận vuông được gọi là ma trận tam giác trên nếu tất cả các thành phần nằm phía dưới đường chéo chính bằng 0. Tương tự, một ma trận vuông được gọi là ma trận tam giác dưới nếu tất cả các thành phần nằm phía trên đường chéo chính bằng 0.
Các hệ phương trình tuyến tính với ma trận hệ số ở dạng tam giác (trên hoặc dưới) có thể được giải mà không cần tính ma trận nghịch đảo. Xét hệ:
a11x1+ a12x2+ · · · + a1,n−1xn−1+ a1nxn = b1 a22x2+ · · · + a2,n−1xn−2+ a2nxn = b2 . . . . . . . . . . . .
an−1,n−1xn−1+ an−1,nxn = bn−1
annxn = bn
(1.10)
Hệ này có thể được viết gọn dưới dạng Ax = b với A là một ma trận tam giác trên. Nhận thấy rằng phương trình này có thể giải mà không cần tính ma trận nghịch đảo A−1. Thật vậy, ta có thể giải xn dựa vào phương trình cuối cùng. Tiếp theo, xn−1 có thể được tìm bằng cách thay xn vào phương trình thứ hai từ
28 Machine Learning cơ bản
Chương 1. Ôn tập Đại số tuyến tính
cuối. Tiếp tục quá trình này, ta sẽ có nghiệm cuối cùng x. Quá trình giải từ cuối lên đầu và thay toàn bộ các thành phần đã tìm được vào phương trình hiện tại được gọi là phép thế ngược. Nếu ma trận hệ số là một ma trận tam giác dưới, hệ phương trình có thể được giải bằng một quá trình ngược lại – lần lượt tính x1 rồi x2, . . . , xn. Quá trình này được gọi là phép thế xuôi.
1.6. Định thức
1.6.1. Định nghĩa
Định thức của một ma trận vuông A được ký hiệu là det(A) hoặc det A. Có nhiều cách định nghĩa khác nhau của định thức. Chúng ta sẽ sử dụng cách định nghĩa dựa trên quy nạp theo bậc n của ma trận.
Với n = 1, det(A) chính bằng phần tử duy nhất của ma trận đó. Với một ma trận vuông bậc n > 1:
A =
a11 a12 . . . a1n
a21 a22 . . . a2n . . . . . .... . . . an1 an2 . . . ann
⇒ det(A) = Xn j=1
(−1)i+jaij det(Aij ) (1.11)
Trong đó i là một số tự nhiên bất kỳ trong khoảng [1, n] và Aij là phần bù đại số của A ứng với phần tử ở hàng i, cột j. Phần bù đại số này là một ma trận con của A, nhận được từ A bằng cách xoá hàng thứ i và cột thứ j của nó. Đây chính là cách tính định thức dựa trên cách khai triển hàng thứ i của ma trận4.
1.6.2. Tính chất
a. det(A) = det(AT): Một ma trận vuông bất kỳ và chuyển vị của nó có định thức như nhau.
b. Định thức của một ma trận đường chéo vuông bằng tích các phần tử trên đường chéo chính. Nói cách khác, nếu A = diag(a1, a2, . . . , an) thì det(A) = a1a2 . . . an.
c. Định thức của một ma trận đơn vị bằng 1.
d. Định thức của một tích bằng tích các định thức.
det(AB) = det(A) det(B) (1.12)
với A, B là hai ma trận vuông cùng chiều.
4 Việc ghi nhớ định nghĩa này không thực sự quan trọng bằng việc ta cần nhớ một vài tính chất của nó.
Machine Learning cơ bản 29
Chương 1. Ôn tập Đại số tuyến tính
e. Nếu một ma trận có một hàng hoặc một cột là một vector 0, thì định thức của nó bằng 0.
f. Một ma trận là khả nghịch khi và chỉ khi định thức của nó khác 0.
g. Nếu một ma trận khả nghịch, định thức của ma trận nghịch đảo của nó bằng nghịch đảo định thức của nó.
det(A−1) = 1
det(A)vì det(A) det(A−1) = det(AA−1) = det(I) = 1. (1.13)
1.7. Tổ hợp tuyến tính, không gian sinh
1.7.1. Tổ hợp tuyến tính
Cho các vector khác không a1, . . . , an ∈ Rm và các số thực x1, . . . , xn ∈ R, vector: b = x1a1 + x2a2 + · · · + xnan (1.14)
được gọi là một tổ hợp tuyến tính của a1, . . . , an. Xét ma trận A = [a1, a2, . . . , an] ∈ Rm×n và x = [x1, x2, . . . , xn]T, biểu thức (1.14) có thể được viết lại thành b = Ax. Ta có thể nói rằng b là một tổ hợp tuyến tính các cột của A.
Tập hợp các vector có thể biểu diễn được dưới dạng một tổ hợp tuyến tính của một hệ vector được gọi là một không gian sinh của hệ vector đó. Không gian sinh của một hệ vector được ký hiệu là span(a1, . . . , an). Nếu phương trình:
0 = x1a1 + x2a2 + · · · + xnan (1.15)
có nghiệm duy nhất x1 = x2 = · · · = xn = 0, ta nói rằng hệ {a1, a2, . . . , an} là một hệ độc lập tuyến tính. Ngược lại, nếu tồn tại xi 6= 0 sao cho phương trình trên thoả mãn, ta nói rằng đó là một hệ phụ thuộc tuyến tính.
1.7.2. Tính chất
a. Một hệ là phụ thuộc tuyến tính khi và chỉ khi tồn tại một vector trong hệ đó là tổ hợp tuyến tính của các vector còn lại. Thật vậy, giả sử phương trình (1.15) có nghiệm khác không, và hệ số khác không là xi, ta sẽ có:
ai =−x1
xia1 + · · · +−xi−1
xiai−1 +−xi+1
xiai+1 + . . .−xn
xian (1.16)
tức ailà một tổ hợp tuyến tính của các vector còn lại.
b. Tập con khác rỗng của một hệ độc lập tuyến tính là một hệ độc lập tuyến tính. 30 Machine Learning cơ bản
Chương 1. Ôn tập Đại số tuyến tính
c. Các cột của một ma trận khả nghịch tạo thành một hệ độc lập tuyến tính.
Giả sử ma trận A khả nghịch, phương trình Ax = 0 có nghiệm duy nhất x = A−10 = 0. Vì vậy, các cột của A tạo thành một hệ độc lập tuyến tính.
d. Nếu A là một ma trận cao, tức số hàng lớn hơn số cột, m > n, tồn tại vector b sao cho phương trình Ax = b vô nghiệm.
Việc này có thể hình dung được trong không gian ba chiều. Không gian sinh của một vector là một đường thẳng, không gian sinh của hai vector độc lập tuyến tính là một mặt phẳng, tức chỉ biểu diễn được các vector nằm trong mặt phẳng đó. Nói cách khác, với ít hơn ba vector, ta không thể biểu diễn được mọi điểm trong không gian ba chiều.
Ta cũng có thể chứng minh tính chất này bằng phản chứng. Giả sử mọi vector trong không gian m chiều đều nằm trong không gian sinh của n vector cột của một ma trận A. Xét các cột của ma trận đơn vị bậc m. Vì mọi cột của ma trận này đều có thể biểu diễn dưới dạng một tổ hợp tuyến tính của n vector đã cho nên phương trình AX = I có nghiệm. Nếu thêm các vector cột bằng 0 vào A và các vector hàng bằng 0 vào X để được các ma trận vuông, ta sẽ có
A 0 X0 = AX = I. Việc này chỉ ra rằng A 0 là một ma trận khả nghịch. Đây là một điều vô lý vì định thức của A 0 bằng 0.
e. Nếu n > m, n vector bất kỳ trong không gian m chiều tạo thành một hệ phụ thuộc tuyến tính.
Thật vậy, giả sử {a1, . . . , an ∈ Rm} là một hệ độc lập tuyến tính với n > m. Khi đó tập con của nó {a1, . . . , am} cũng là một hệ độc lập tuyến tính, suy ra A = [a1, . . . , am] là một ma trận khả nghịch. Khi đó phương trình Ax = am+1 có nghiệm x = A−1am+1. Nói cách khác, am+1 là một tổ hợp tuyến tính của {a1, . . . , am}. Điều này mâu thuẫn với giả thiết phản chứng.
1.7.3. Cơ sở của một không gian
Một hệ các vector {a1, . . . , an} trong không gian vector m chiều V = Rm được gọi là một cơ sở nếu hai điều kiện sau thoả mãn:
a. V ≡ span(a1, . . . , an)
b. {a1, . . . , an} là một hệ độc lập tuyến tính.
Khi đó, mọi vector b ∈ V đều có thể biểu diễn duy nhất dưới dạng một tổ hợp tuyến tính của các ai. Từ hai tính chất cuối ở Mục 1.7.2, ta có thể suy ra rằng m = n.
Machine Learning cơ bản 31
Chương 1. Ôn tập Đại số tuyến tính
1.7.4. Range và Null space
Với mỗi A ∈ Rm×n, có hai không gian con quan trọng ứng với ma trận này. Range của A, ký hiệu là R(A), được định nghĩa bởi
R(A) = {y ∈ Rm : ∃x ∈ Rn, Ax = y} (1.17)
Nói cách khác, R(A) chính là không gian sinh của các cột của A. R(A) là một không gian con của Rm với số chiều bằng số lượng lớn nhất các cột độc lập tuyến tính của A.
Null của A, ký hiệu là N (A), được định nghĩa bởi
N (A) = {x ∈ Rn: Ax = 0} (1.18)
Mỗi vector trong N (A) tương ứng với một bộ các hệ số làm cho tổ hợp tuyến tính các cột của A bằng vector 0. N (A) có thể được chứng minh là một không gian con trong Rn. Khi các cột của A là độc lập tuyến tính, phần tử duy nhất của N (A) là x = A−10 = 0.
R(A) và N (A) là các không gian con vector với số chiều lần lượt là dim(R(A)) và dim(N (A)), ta có tính chất quan trọng sau đây:
dim(R(A)) + dim(N (A)) = n (1.19)
1.8. Hạng của ma trận
Hạng của một ma trận A ∈ Rm×n, ký hiệu là rank(A), được định nghĩa là số lượng lớn nhất các cột của nó tạo thành một hệ độc lập tuyến tính.
Dưới đây là các tính chất quan trọng của hạng.
a. Một ma trận có hạng bằng 0 khi và chỉ khi nó là ma trận 0. b. Hạng của một ma trận bằng hạng của ma trận chuyển vị. rank(A) = rank(AT)
Nói cách khác, số lượng lớn nhất các cột độc lập tuyến tính của một ma trận bằng với số lượng lớn nhất các hàng độc lập tuyến tính của ma trận đó. Từ đây ta suy ra tính chất dưới đây.
c. Hạng của một ma trận không thể lớn hơn số hàng hoặc số cột của nó. Nếu A ∈ Rm×n, thì rank(A) ≤ min(m, n).
32 Machine Learning cơ bản
Chương 1. Ôn tập Đại số tuyến tính
d. Hạng của một tích không vượt quá hạng của mỗi ma trận nhân tử. rank(AB) ≤ min(rank(A),rank(B))
e. Hạng của một tổng không vượt quá tổng các hạng.
rank(A + B) ≤ rank(A) + rank(B) (1.20)
Điều này chỉ ra rằng một ma trận có hạng bằng k không thể được biểu diễn dưới dạng tổng của ít hơn k ma trận có hạng bằng 1. Trong Chương 20, chúng ta sẽ thấy rằng một ma trận có hạng bằng k có thể biểu diễn được dưới dạng đúng k ma trận có hạng bằng 1.
f. Bất đẳng thức Sylvester về hạng: nếu A ∈ Rm×n, B ∈ Rn×k, thì rank(A) + rank(B) − n ≤ rank(AB)
Xét một ma trận vuông A ∈ Rn×, hai điều kiện bất kỳ trong các điều kiện dưới đây là tương đương:
• A là một ma trận khả nghịch.
• Các cột của A tạo thành một cơ sở trong không gian n chiều.
• det(A) 6= 0. • rank(A) = n
1.9. Hệ trực chuẩn, ma trận trực giao
1.9.1. Định nghĩa
Một hệ cơ sở {u1, u2, . . . , um ∈ Rm} được gọi là trực giao nếu mỗi vector khác không và tích vô hướng của hai vector khác nhau bất kỳ bằng không:
ui 6= 0; uTi uj = 0 ∀ 1 ≤ i 6= j ≤ m (1.21)
Một hệ cơ sở {u1, u2, . . . , um ∈ Rm} được gọi là trực chuẩn nếu nó là một hệ trực giao và độ dài Euclid (xem thêm Mục 1.14.1) của mỗi vector bằng 1:
uTi uj =
1 nếu i = j
0 nếu i 6= j(1.22)
Gọi U = [u1, u2, . . . , um] với {u1, u2, . . . , um ∈ Rm} là trực chuẩn. Từ (1.22) ta có thể suy ra:
UUT = UTU = I (1.23)
trong đó I là ma trận đơn vị bậc m. Nếu một ma trận thoả mãn điều kiện (1.23), ta gọi nó là một ma trận trực giao. Ma trận loại này không được gọi là ma trận trực chuẩn, không có định nghĩa cho ma trận trực chuẩn.
Nếu một ma trận vuông phức U thoả mãn UUH = UHU = I, ta nói rằng U là một ma trận unitary.
Machine Learning cơ bản 33
Chương 1. Ôn tập Đại số tuyến tính
1.9.2. Tính chất
a. Nghịch đảo của một ma trận trực giao chính là chuyển vị của nó. U−1 = UT
b. Nếu U là một ma trận trực giao thì chuyển vị của nó UTcũng là một ma trận trực giao.
c. Định thức của một ma trận trực giao bằng 1 hoặc −1.
Điều này có thể suy ra từ việc det(U) = det(UT) và det(U) det(UT) = det(I) = 1.
d. Ma trận trực giao thể hiện cho phép xoay một vector (xem thêm mục 1.10).
Giả sử có hai vector x, y ∈ Rm và một ma trận trực giao U ∈ Rm×m. Dùng ma trận này để xoay hai vector trên ta được Ux, Uy. Tích vô hướng của hai vector mới là:
(Ux)T(Uy) = xTUTUy = xT y
như vậy phép xoay không làm thay đổi tích vô hướng giữa hai vector.
e. Giả sử Uˆ ∈ Rm×r, r < m là một ma trận con của ma trận trực giao U được tạo bởi r cột của U, ta sẽ có Uˆ TUˆ = Ir. Việc này có thể được suy ra từ (1.22).
1.10. Biễu diễn vector trong các hệ cơ sở khác nhau
Trong không gian m chiều, toạ độ của mỗi điểm được xác định dựa trên một hệ toạ độ nào đó. Ở các hệ toạ độ khác nhau, toạ độ của mỗi điểm cũng khác nhau.
Tập hợp các vector e1, . . . , em mà mỗi vector ei có đúng 1 phần tử khác 0 ở thành phần thứ i và phần tử đó bằng 1, được gọi là hệ cơ sở đơn vị (hoặc hệ đơn vị, hoặc hệ chính tắc) trong không gian m chiều. Nếu xếp các vector ei, i = 1, 2, . . . , m cạnh nhau theo đúng thứ tự đó, ta sẽ được ma trận đơn vị m chiều.
Mỗi vector cột x = [x1, x2, . . . , xm] ∈ Rm có thể coi là một tổ hợp tuyến tính của các vector trong hệ cơ sở chính tắc:
x = x1e1 + x2e2 + · · · + xmem (1.24)
Giả sử có một hệ cơ sở độc lập tuyến tính khác u1, u2, . . . , um. Trong hệ cơ sở mới này, x được viết dưới dạng
x = y1u1 + y2u2 + · · · + ymum = Uy (1.25)
34 Machine Learning cơ bản
e2
u1
Chương 1. Ôn tập Đại số tuyến tính
Hình 1.1. Chuyển đổi toạ độ
trong các hệ cơ sở khác nhau.
Trong hệ toạ độ Oe1e2, x có toạ độ
x
u2
x2y1 y2
là (x1, x2). Trong hệ toạ độ Ou1u2, x có toạ độ là (y2, y2).
e1
O
x1
với U = u1 . . . um . Lúc này, vector y = [y1, y2, . . . , ym]Tchính là biểu diễn của x trong hệ cơ sở mới. Biểu diễn này là duy nhất vì y = U−1x.
Trong các ma trận đóng vai trò như hệ cơ sở, các ma trận trực giao, tức UTU = I, được quan tâm nhiều hơn vì nghịch đảo và chuyển vị của chúng bằng nhau, U−1 = UT. Khi đó, y có thể được tính một cách nhanh chóng y = UT x. Từ đó suy ra yi = xTui = uTi x, i = 1, . . . , m. Dưới góc nhìn hình học, hệ trực giao tạo thành một hệ trục toạ độ Descartes vuông góc. Hình 1.1 là một ví dụ về việc chuyển hệ cơ sở trong không gian hai chiều.
Có thể nhận thấy rằng vector 0 được biểu diễn như nhau trong mọi hệ cơ sở.
Việc chuyển đổi hệ cơ sở sử dụng ma trận trực giao có thể được coi như một phép xoay trục toạ độ. Nhìn theo một cách khác, đây cũng chính là một phép xoay vector dữ liệu theo chiều ngược lại, nếu ta coi các trục toạ độ là cố định. Trong Chương 21, chúng ta sẽ thấy một ứng dụng quan trọng của việc đổi hệ cơ sở.
1.11. Trị riêng và vector riêng
1.11.1. Định nghĩa
Cho một ma trận vuông A ∈ Rn×n, một vector x ∈ Cn(x 6= 0) và một số vô hướng λ ∈ C. Nếu
Ax = λx, (1.26)
ta nói λ là một trị riêng của A, x là một vector riêng ứng với trị riêng λ.
Từ định nghĩa ta cũng có (A − λI)x = 0, tức x là một vector nằm trong không gian N (A − λI). Vì x 6= 0, ta có A − λI là một ma trận không khả nghịch. Nói cách khác det(A − λI) = 0, tức λ là nghiệm của phương trình det(A − tI) = 0. Định thức này là một đa thức bậc n của t. Đa thức này còn được gọi là đa thức đặc trưng của A, được ký hiệu là pA(t). Tập hợp tất cả các trị riêng của một ma trận vuông còn được gọi là phổ của ma trận đó.
Machine Learning cơ bản 35
Chương 1. Ôn tập Đại số tuyến tính
1.11.2. Tính chất
a. Giả sử λ là một trị riêng của A ∈ Cn×n, đặt Eλ(A) là tập các vector riêng ứng với trị riêng λ đó. Bạn đọc có thể chứng minh được:
• Nếu x ∈ Eλ(A) thì kx ∈ Eλ(A), ∀k ∈ C.
• Nếu x1, x2 ∈ Eλ(A) thì x1 + x2 ∈ Eλ(A).
Từ đó suy ra tập hợp các vector riêng ứng với một trị riêng của một ma trận vuông tạo thành một không gian vector con, thường được gọi là không gian riêng ứng với trị riêng đó.
b. Mọi ma trận vuông bậc n đều có n trị riêng, kể cả lặp và phức.
c. Tích của tất cả các trị riêng của một ma trận bằng định thức của ma trận đó. Tổng tất cả các trị riêng của một ma trận bằng tổng các phần tử trên đường chéo của ma trận đó.
d. Phổ của một ma trận bằng phổ của ma trận chuyển vị của nó.
e. Nếu A, B là các ma trận vuông cùng bậc thì pAB(t) = pBA(t). Như vậy, tuy AB có thể khác BA, đa thức đặc trưng của AB và BA luôn bằng nhau nhau. Tức phổ của hai tích này là trùng nhau.
f. Tất cả các trị riêng của một ma trận Hermitian là các số thực. Thật vậy, giả sử λ là một trị riêng của một ma trận Hermitian A và x là một vector riêng ứng với trị riêng đó. Từ định nghĩa ta suy ra:
Ax = λx ⇒ (Ax)H = λ¯xH ⇒ λ¯xH = xHAH = xHA (1.27) với λ¯ là liên hiệp phức của số vô hướng λ. Nhân cả hai vế vào bên phải với x
ta có:
λ¯xHx = xHAx = λxHx ⇒ (λ − λ¯)xHx = 0 (1.28)
vì x 6= 0 nên xHx 6= 0. Từ đó suy ra λ¯ = λ, tức λ phải là một số thực.
g. Nếu (λ, x) là một cặp trị riêng, vector riêng của một ma trận khả nghịch A, thì (1λ, x) là một cặp trị riêng, vector riêng của A−1, vì Ax = λx ⇒1λx = A−1x.
1.12. Chéo hoá ma trận
Việc phân tích một đại lượng toán học ra thành các đại lượng nhỏ hơn mang lại nhiều hiệu quả. Phân tích một số thành tích các thừa số nguyên tố giúp kiểm tra một số có bao nhiêu ước số. Phân tích đa thức thành nhân tử giúp tìm nghiệm của đa thức. Việc phân tích một ma trận thành tích của các ma trận đặc biệt
36 Machine Learning cơ bản
Chương 1. Ôn tập Đại số tuyến tính
cũng mang lại nhiều lợi ích trong việc giải hệ phương trình tuyến tính, tính luỹ thừa của ma trận, xấp xỉ ma trận,... Trong mục này, chúng ta sẽ ôn lại một phương pháp phân tích ma trận quen thuộc có tên là chéo hoá ma trận.
Giả sử x1, . . . , xn 6= 0 là các vector riêng của một ma trận vuông A ứng với các trị riêng lặp hoặc phức λ1, . . . , λn: Axi = λixi, ∀i = 1, . . . , n. Đặt Λ = diag(λ1, λ2, . . . , λn), và X = x1, x2, . . . , xn , ta sẽ có AX = XΛ. Hơn nữa, nếu các trị riêng x1, . . . , xn là độc lập tuyến tính, ma trận X là một ma trận khả nghịch. Khi đó ta có thể viết A dưới dạng tích của ba ma trận:
A = XΛX−1(1.29)
Các vector riêng xi thường được chọn sao cho xTi xi = 1. Cách biểu diễn một ma trận như (1.29) được gọi là phép phân tích trị riêng.
Ma trận các trị riêng Λ là một ma trận đường chéo. Vì vậy, cách khai triển này cũng có tên gọi là chéo hoá ma trận. Nếu ma trận A có thể phân tích được dưới dạng (1.29), ta nói rằng A là chéo hoá được.
1.12.1. Lưu ý
a. Khái niệm chéo hoá ma trận chỉ áp dụng với ma trận vuông. Vì không có định nghĩa vector riêng hay trị riêng cho ma trận không vuông.
b. Không phải ma trận vuông nào cũng chéo hoá được. Một ma trận vuông bậc n chéo hoá được khi và chỉ khi nó có đủ n vector riêng độc lập tuyến tính.
c. Nếu một ma trận là chéo hoá được, có nhiều hơn một cách chéo hoá ma trận đó. Chỉ cần đổi vị trí của các λi và vị trí tương ứng các cột của X, ta sẽ có một cách chéo hoá mới.
d. Nếu A có thể viết được dưới dạng (1.29), khi đó các luỹ thừa có nó cũng chéo hoá được. Cụ thể:
A2 = (XΛX−1)(XΛX−1) = XΛ2X−1; Ak = XΛkX−1, ∀k ∈ N (1.30)
Xin chú ý rằng nếu λ và x là một cặp trị riêng, vector riêng của A, thì λk và x là một cặp trị riêng, vector riêng của Ak. Thật vậy, Akx = Ak−1(Ax) = λAk−1x = · · · = λkx.
e. Nếu A khả nghịch, thì A−1 = (XΛX−1)−1 = XΛ−1X−1.
Machine Learning cơ bản 37
Chương 1. Ôn tập Đại số tuyến tính
1.13. Ma trận xác định dương
1.13.1. Định nghĩa
Một ma trận đối xứng5 A ∈ Rn×n được gọi là xác định dương nếu: xTAx > 0, ∀x ∈ Rn, x 6= 0. (1.31)
Một ma trận đối xứng A ∈ Rn×n được gọi là nửa xác định dương nếu: xTAx ≥ 0, ∀x ∈ Rn, x 6= 0. (1.32)
Trên thực tế, ma trận nửa xác định dương được sử dụng nhiều hơn. Ma trận xác định âm và nửa xác định âm cũng được định nghĩa tương tự.
Ký hiệu A 0, 0, ≺ 0, 0 lần lượt để chỉ một ma trận là xác định dương, nửa xác định dương, xác định âm, và nửa xác định âm. Ký hiệu A B cũng được dùng để chỉ ra rằng A − B 0.
Ví dụ, A =
1 −1 −1 1
u
là nửa xác định dương vì với mọi vector x = v
, ta có:
xTAx = u v 1 −1 −1 1
u v
= u2 + v2 − 2uv = (u − v)2 ≥ 0, ∀u, v ∈ R (1.33)
Mở rộng, một ma trận Hermitian A ∈ Cn×nlà xác định dương nếu xHAx > 0, ∀x ∈ Cn, x 6= 0. (1.34)
Các khái niệm nửa xác định dương, xác định âm, và nửa xác định dương cũng được định nghĩa tương tự cho các ma trận Hermitian.
1.13.2. Tính chất
a. Mọi trị riêng của một ma trận Hermitian xác định dương đều là một số thực dương. Trước hết, các trị riêng của một ma trận Hermitian là các số thực. Để chứng minh chúng là các số thực dương, ta giả sử λ là một trị riêng của một ma trận xác định dương A và x 6= 0 là một vector riêng ứng với trị riêng đó. Nhân vào bên trái cả hai vế của Ax = λx với xH ta có:
λxHx = xHAx > 0 (1.35)
Vì ∀x 6= 0, xHx > 0 nên ta phải có λ > 0. Tương tự, ta có thể chứng minh được rằng mọi trị riêng của một ma trận nửa xác định dương là không âm.
5 Chú ý, tồn tại những ma trận không đối xứng thoả mãn điều kiện (1.31). Ta sẽ không xét những ma trận này trong cuốn sách.
38 Machine Learning cơ bản
Chương 1. Ôn tập Đại số tuyến tính
b. Mọi ma trận xác định dương đều khả nghịch. Hơn nữa, định thức của nó là một số dương. Điều này được trực tiếp suy ra từ tính chất (a). Nhắc lại rằng định thức của một ma trận bằng tích tất cả các trị riêng của nó.
c. Tiêu chuẩn Sylvester. Trước hết, chúng ta làm quen với hai khái niệm: ma trận con chính và ma trận con chính trước.
Giả sử A là một ma trận vuông bậc n. Gọi I là một tập con khác rỗng bất kỳ của {1, 2, . . . , n}, ký hiệu AI để chỉ một ma trận con của A nhận được bằng cách trích ra các hàng và cột có chỉ số nằm trong I của A. Khi đó, AI được gọi là một ma trận con chính của A. Nếu I chỉ bao gồm các số tự nhiên liên tiếp từ 1 đến k ≤ n, ta nói AI là một ma trận con chính trước bậc k của A.
Tiêu chuẩn Sylvester nói rằng: Một ma trận Hermitian là xác định dương khi và chỉ khi mọi ma trận con chính trước của nó là xác định dương.
Các ma trận Hermitian nửa xác định dương cần điều kiện chặt hơn: Một ma trận Hermitian là nửa xác định dương khi và chỉ khi mọi ma trận con chính của nó là nửa xác định dương.
d. Với mọi ma trận B không nhất thiết vuông, ma trận A = BHB là nửa xác định dương. Thật vậy, với mọi vector x 6= 0 với chiều phù hợp, xHAx = xHBHBx = (Bx)H(Bx) ≥ 0.
e. Phân tích Cholesky: Mọi ma trận Hermitian nửa xác định dương A đều biểu diễn được duy nhất dưới dạng A = LLH với L là một ma trận tam giác dưới với các thành phần trên đường chéo là thực dương.
f. Nếu A là một ma trận nửa xác định dương thì xTAx = 0 ⇔ Ax = 0.
Nếu Ax = 0, dễ thấy xTAx = 0. Nếu xTAx = 0, với y 6= 0 bất kỳ có cùng kích thước với x, xét hàm số
f(λ) = (x + λy)TA(x + λy) (1.36)
Hàm số này không âm với mọi λ vì A là một ma trận nửa xác định dương. Đây là một tam thức bậc hai của λ:
f(λ) = yTAyλ2 + 2yTAxλ + xTAx = yTAyλ2 + 2yTAxλ (1.37) Xét hai trường hợp:
• yTAy = 0. Khi đó, f(λ) = 2yTAxλ ≥ 0, ∀λ khi và chỉ khi yTAx = 0.
• yTAy > 0. Khi đó tam thức bậc hai f(λ) ≥ 0, ∀λ xảy ra khi và chỉ khi ∆0 = (yTAx)2 ≤ 0. Điều này cũng đồng nghĩa với việc yTAx = 0
Tóm lại, yTAx = 0, ∀y 6= 0. Điều này chỉ xảy ra nếu Ax = 0. Machine Learning cơ bản 39
Chương 1. Ôn tập Đại số tuyến tính
1.14. Chuẩn
Trong không gian một chiều, khoảng cách giữa hai điểm là trị tuyệt đối của hiệu giữa hai giá trị đó. Trong không gian hai chiều, tức mặt phẳng, chúng ta thường dùng khoảng cách Euclid để đo khoảng cách giữa hai điểm. Khoảng cách Euclid chính là độ dài đoạn thẳng nối hai điểm trong mặt phẳng. Đôi khi, để đi từ một điểm này tới một điểm kia, chúng ta không thể đi bằng đường thẳng vì còn phụ thuộc vào hình dạng đường đi nối giữa hai điểm.
Việc đo khoảng cách giữa hai điểm dữ liệu nhiều chiều rất cần thiết trong machine learning. Đây chính là lý do khái niệm chuẩn (norm) ra đời. Để xác định khoảng cách giữa hai vector y và z, người ta thường áp dụng một hàm số lên vector hiệu x = y − z. Hàm số này cần có một vài tính chất đặc biệt.
Định nghĩa 1.1: Chuẩn – Norm
ột hàm số f : Rn → R được gọi là một chuẩn nếu nó thỏa mãn ba điều kiện sau đây:
a. f(x) ≥ 0. Dấu bằng xảy ra ⇔ x = 0.
b. f(αx) = |α|f(x), ∀α ∈ R
c. f(x1) + f(x2) ≥ f(x1 + x2), ∀x1, x2 ∈ Rn
Điều kiện a) là dễ hiểu vì khoảng cách không thể là một số âm. Hơn nữa, khoảng cách giữa hai điểm y và z bằng 0 khi và chỉ khi hai điểm đó trùng nhau, tức x = y − z = 0.
Điều kiện b) cũng có thể được lý giải như sau. Nếu ba điểm y, v và z thẳng hàng, hơn nữa v − y = α(v − z) thì khoảng cách giữa v và y gấp |α| lần khoảng cách giữa v và z.
Điều kiện c) chính là bất đẳng thức tam giác nếu ta coi x1 = y − w, x2 = w − z với w là một điểm bất kỳ trong cùng không gian.
1.14.1. Một số chuẩn vector thường dùng
Độ dài Euclid của một vector x ∈ Rnchính là một chuẩn, chuẩn này được gọi là chuẩn `2 hoặc chuẩn Euclid:
q
kxk2 =
x21 + x22 + · · · + x2n(1.38)
Bình phương của chuẩn `2 chính là tích vô hướng của một vector với chính nó, kxk22 = xT x.
40 Machine Learning cơ bản
x2
kx − yk1 = |x1 − y1| + |x2 − y2| x
Chương 1. Ôn tập Đại số tuyến tính
Hình 1.2. Minh họa chuẩn `1 và chuẩn `2 trong không gian hai chiều. Chuẩn `2 chính là khoảng cách Euclid.
y2
|x2 − y2|
z
kx − yk2 |x1 − y1|
Trong khi đó chuẩn `1 là quãng đường
ngắn nhất giữa hai điểm nếu chỉ được
đi theo các đường song song với các
trục toạ độ.
y
x1 y1
Với p là một số không nhỏ hơn 1 bất kỳ, hàm số:
kxkp = (|x1|p + |x2|p + . . . |xn|p)1p (1.39)
được chứng minh thỏa mãn ba điều kiện của chuẩn, và được gọi là chuẩn `p. Dưới đây là một vài giá trị của p thường được dùng.
a. Khi p = 2, ta có chuẩn `2 như ở trên.
b. Khi p = 1, ta có chuẩn `1: kxk1 = |x1| + |x2| + · · · + |xn| là tổng các trị tuyệt đối của từng phần tử của x. Hình 1.2 là một ví dụ sánh chuẩn `1 và chuẩn `2 trong không gian hai chiều. Chuẩn `2 chính là khoảng cách Euclid giữa x và y. Trong khi đó, khoảng cách chuẩn `1 giữa hai điểm này (đường gấp khúc xzy) có thể diễn giải như là quãng đường từ x tới y nếu chỉ được phép đi song song với các trục toạ độ.
c. Khi p → ∞, giả sử i = arg maxj=1,2,...,n |xj|. Khi đó:
kxkp = |xi|
Ta thấy rằng
1 +
x1 xi
p+ · · · + xi−1 xi
p+ xi+1 xi
p+ · · · + xn xi
p 1p(1.40)
lim
p→∞
1 +
x1 xi
p+ · · · + xi−1 xi
p+ xi+1 xi
p+ · · · + xn xi
p 1p= 1 (1.41)
vì đại lượng trong dấu ngoặc đơn không vượt quá n. Ta có
kxk∞ , lim
p→∞kxkp = |xi| = max
j=1,2,...,n|xj| (1.42)
1.14.2. Chuẩn Frobenius của ma trận
Với một ma trận A ∈ Rm×n, chuẩn thường được dùng nhất là chuẩn Frobenius, ký hiệu là kAkF , là căn bậc hai của tổng bình phương tất cả các phần tử của nó:
Machine Learning cơ bản 41
Chương 1. Ôn tập Đại số tuyến tính kAkF =
vuutXm i=1
Xn j=1
a2ij
Chú ý rằng chuẩn `2, kAk2, là một chuẩn khác của ma trận, không phổ biến bằng chuẩn Frobenius. Bạn đọc có thể xem chuẩn `2 của ma trận trong Phụ lục A.
1.15. Vết
Vết (trace) của một ma trận vuông A được ký hiệu là trace(A), là tổng tất cả các phần tử trên đường chéo chính của nó. Hàm vết xác định trên tập các ma trận vuông được sử dụng nhiều trong tối ưu vì nó có những tính chất đẹp.
Các tính chất quan trọng của hàm vết, với giả sử rằng các ma trận trong hàm vết là vuông và các phép nhân ma trận thực hiện được:
a. Một ma trận vuông bất kỳ và chuyển vị của nó có vết bằng nhau: trace(A) = trace(AT). Việc này được suy ra từ việc phép chuyển vị không làm thay đổi các phần tử trên đường chéo chính của một ma trận.
b. Vết của một tổng bằng tổng các vết:
trace(Xk i=1
Ai) = Xk i=1
trace(Ai)
c. trace(kA) = ktrace(A) với k là một số vô hướng bất kỳ.
d. trace(A) = PDi=1 λi với A là một ma trận vuông và λi, i = 1, 2, . . . , N là toàn bộ các trị riêng của nó, có thể lặp hoặc phức. Việc chứng minh tính chất này có thể được dựa trên ma trận đặc trưng của A và định lý Viète.
e. trace(AB) = trace(BA). Đẳng thức này được suy ra từ việc đa thức đặc trưng của AB và BA là như nhau. Bạn đọc cũng có thể chứng minh bằng cách tính trực tiếp các phần tử trên đường chéo chính của AB và BA.
f. trace(ABC) = trace(BCA), nhưng trace(ABC) không đồng nhất với trace(ACB). g. Nếu X là một ma trận khả nghịch cùng chiều với A thì
trace(XAX−1) = trace(X−1XA) = trace(A)
h. kAk2F = trace(ATA) = trace(AAT) với A là một ma trận bất kỳ. Từ đây ta cũng suy ra trace(AAT) ≥ 0 với mọi ma trận A.
42 Machine Learning cơ bản
Chương 2. Giải tích ma trận
Chương 2
Giải tích ma trận
Giả sử rằng các gradient tồn tại trong toàn bộ chương. Tài liệu tham khảo chính của chương là Matrix calculus – Stanford (https://goo.gl/BjTPLr).
2.1. Gradient của hàm trả về một số vô hướng
Gradient bậc nhất (first-order gradient) hay viết gọn là gradient của một hàm số f(x) : Rn → R theo x, ký hiệu là ∇xf(x), được định nghĩa bởi
∈ Rn, (2.1)
trong đó ∂f(x)
∇xf(x) ,
∂f(x)
∂x1
∂f(x) ∂x2
...
∂f(x) ∂xn
∂xilà đạo hàm riêng của hàm số theo thành phần thứ i của vector x. Đạo hàm này được tính khi tất cả các biến, ngoài xi, được giả sử là hằng số. Nếu không có thêm biến nào khác, ∇xf(x) thường được viết gọn là ∇f(x). Gradient của hàm số này là một vector có cùng chiều với vector đang được lấy gradient. Tức nếu vector được viết ở dạng cột thì gradient cũng phải được viết ở dạng cột.
Gradient bậc hai (second-order gradient) của hàm số trên còn được gọi là Hesse (Hessian) và được định nghĩa như sau:
Machine Learning cơ bản 43
Chương 2. Giải tích ma trận
∂2f(x)
∂x21
∂2f(x)
∂x1∂x2. . .∂2f(x)
∂2f(x)
∂x1∂xn
∂x22. . .∂2f(x) ∂2f(x)
∈ Sn. (2.2)
∇2f(x) ,
∂x2∂x1
∂x2∂xn
............
∂2f(x) ∂xn∂x1
∂xn∂x2. . .∂2f(x)
∂2f(x)
∂x2n
Gradient của một hàm số f(X) : Rn×m → R theo ma trận X được định nghĩa là
∇f(X) =
∂f(X)
∂x11
∂f(X) ∂x21
∂f(X)
∂x12. . .∂f(X)
∂x1m
∂f(X)
∂x22. . .∂f(X) ∂x2m
∈ Rn×m. (2.3)
............
∂f(X) ∂xn1
∂xn2. . .∂f(X)
∂f(X)
∂xnm
Gradient của hàm số f : Rm×n → R là một ma trận trong Rm×n.
Cụ thể, để tính gradient của một hàm f : Rm×n → R, ta tính đạo hàm riêng của hàm số đó theo từng thành phần của ma trận khi toàn bộ các thành phần khác được giả sử là hằng số. Tiếp theo, ta sắp xếp các đạo hàm riêng tính được theo đúng thứ tự trong ma trận.
Ví dụ: Xét hàm số f : R2 → R, f(x) = x21 + 2x1x2 + sin(x1) + 2. Gradient bậc nhất theo x của hàm số đó là
∇f(x) =
∂f(x)
∂x1
∂f(x) ∂x2
=
2x1 + 2x2 + cos(x1) 2x1
.
Gradient bậc hai theo x, hay Hesse là
∇2f(x) =
∂2f(x)
∂x21
∂2f(x) ∂x2∂x1
∂f 2(x) ∂x1∂x2 ∂f 2(x) ∂x22
=
2 − sin(x1) 2 2 0
.
Chú ý rằng Hesse luôn là một ma trận đối xứng.
44 Machine Learning cơ bản
Chương 2. Giải tích ma trận
2.2. Gradient của hàm trả về vector
Những hàm số mà đầu ra là một vector được gọi là hàm trả về vector (vector valued function).
Xét một hàm trả về vector với đầu vào là một số thực v(x) : R → Rn:
v(x) =
v1(x)
v2(x)
...
vn(x)
. (2.4)
Gradient của hàm số này theo x là một vector hàng như sau:
∇v(x) ,
∂v1(x) ∂x
∂x . . .∂vn(x)
∂v2(x)
∂x
. (2.5)
Gradient bậc hai của hàm số này có dạng:
∇2v(x) ,
∂2v1(x) ∂x2
∂x2. . .∂2vn(x)
∂2v2(x)
∂x2
. (2.6)
Ví dụ: Cho một vector a ∈ Rn và một hàm số trả về vector v(x) = xa, gradient và Hesse của nó lần lượt là
∇v(x) = aT, ∇2v(x) = 0 ∈ R1×n. (2.7)
Xét một hàm trả về vector với đầu vào là một vector h(x) : Rk → Rn, gradient
của nó là
∂h1(x) ∂x1
∂h2(x)
∂x1. . .∂hn(x)
= ∇h1(x) . . . ∇hn(x) ∈ Rk×n.(2.8)
∂h2(x)
∂x1
∇h(x) ,
∂h1(x) ∂x2
∂x2. . .∂hn(x) ∂x2
............ ∂h2(x)
∂h1(x) ∂xk
∂xk. . .∂hn(x) ∂xk
Gradient của hàm số g : Rm → Rnlà một ma trận thuộc Rm×n.
Gradient bậc hai của hàm số trên là một mảng ba chiều. Trong phạm vi của cuốn sách, chúng ta sẽ không xét gradient bậc hai của các hàm số g : Rm → Rn.
Trước khi đến phần tính gradient của các hàm số thường gặp, chúng ta cần biết hai tính chất quan trọng khá giống với gradient của hàm một biến.
Machine Learning cơ bản 45
Chương 2. Giải tích ma trận
2.3. Tính chất quan trọng của gradient
2.3.1. Quy tắc tích
Giả sử các biến đầu vào là một ma trận và các hàm số có chiều phù hợp để phép nhân ma trận thực hiện được. Ta có
∇f(X)Tg(X) = (∇f(X)) g(X) + (∇g(X)) f(X). (2.9) Quy tắc này tương tự như quy tắc tính đạo hàm của tích các hàm f, g : R → R: (f(x)g(x))0 = f0(x)g(x) + g0(x)f(x).
Lưu ý rằng tính chất giao hoán không còn đúng với vector và ma trận, vì vậy nhìn chung
∇f(X)Tg(X) 6= g(X) (∇f(X)) + f(X) (∇g(X)). (2.10) Biểu thức bên phải có thể không xác định khi chiều của các ma trận lệch nhau. 2.3.2. Quy tắc chuỗi
Quy tắc chuỗi được áp dụng khi tính gradient của các hàm hợp: ∇Xg(f(X)) = (∇Xf)(∇f g). (2.11)
Quy tắc này cũng giống với quy tắc trong hàm một biến:
(g(f(x)))0 = f0(x)g0(f).
Một lưu ý nhỏ nhưng quan trọng khi làm việc với tích các ma trận là sự phù hợp về kích thước của các ma trận trong tích.
2.4. Gradient của các hàm số thường gặp
2.4.1. f(x) = aT x
Giả sử a, x ∈ Rn, ta viết lại f(x) = aT x = a1x1 + a2x2 + · · · + anxn. Nhận thấy ∂f(x)
∂xi= ai, ∀i = 1, 2 . . . , n.
Vậy, ∇x(aT x) = a1 a2 . . . an T= a.
Ngoài ra, vì aT x = xT a nên ∇x(xT a) = a.
46 Machine Learning cơ bản
Chương 2. Giải tích ma trận
2.4.2. f(x) = Ax
Đây là một hàm trả về vector f : Rn → Rm với x ∈ Rn, A ∈ Rm×n. Giả sử ailà
hàng thứ i của ma trận A. Ta có Ax =
a1x
a2x...
amx
.
Từ định nghĩa (2.8) và công thức gradient của aix, có thể suy ra ∇x(Ax) = aT1 aT2. . . aTm = AT(2.12)
Từ đây suy ra đạo hàm của hàm số f(x) = x = Ix là
∇x = I
với I là ma trận đơn vị.
2.4.3. f(x) = xT Ax
Với x ∈ Rn, A ∈ Rn×n, áp dụng quy tắc tích (2.9) ta có
∇f(x) = ∇xT (Ax)
= (∇(x)) Ax + (∇(Ax)) x
= IAx + AT x
= (A + AT)x. (2.13)
Từ (2.13) và (2.12), có thể suy ra ∇2xTAx = AT + A. Nếu A là một ma trận đối xứng, ta có ∇xTAx = 2Ax, ∇2xTAx = 2A.
Nếu A là ma trận đơn vị, tức f(x) = xTIx = xT x = kxk22, ta có ∇kxk22 = 2x, ∇2kxk22 = 2I. (2.14)
2.4.4. f(x) = kAx − bk22
Có hai cách tính gradient của hàm số này:
• Cách 1: Trước hết, khai triển:
f(x) = kAx − bk22 = (Ax − b)T(Ax − b) = (xTAT − bT)(Ax − b) = xTATAx − 2bTAx + bTb.
Lấy gradient cho từng số hạng rồi cộng lại ta có
∇kAx − bk22 = 2ATAx − 2ATb = 2AT(Ax − b).
• Cách 2: Sử dụng ∇(Ax − b) = AT và ∇kxk22 = 2x và quy tắc chuỗi (2.11), ta cũng sẽ thu được kết quả tương tự.
Machine Learning cơ bản 47
Chương 2. Giải tích ma trận
2.4.5. f(x) = aT xxT b
Viết lại f(x) = (aT x)(xTb) và dùng quy tắc tích (2.9), ta có ∇(aT xxTb) = axTb + baT x = abT x + baT x = (abT + baT)x, ở đây ta đã sử dụng tính chất yT z = zT y.
2.4.6. f(X) = trace(AX)
Giả sử A ∈ Rn×m, X = Rm×n, và B = AX ∈ Rn×n. Theo định nghĩa của trace:
f(X) = trace(AX) = trace(B) = Xn j=1
Từ đó suy ra ∂f(X)
bjj =Xn j=1
Xn i=1
ajixji. (2.15)
∂xij= aji. Theo định nghĩa (2.3), ta có ∇Xtrace(AX) = AT. 2.4.7. f(X) = aT Xb
Giả sử rằng a ∈ Rm, X ∈ Rm×n, b ∈ Rn. Ta có thể chứng minh được
f(X) = Xm i=1
Xn j=1
xijaibj.
Từ đó, sử dụng định nghĩa (2.3), ta đạt được
a1b1 a1b2 . . . a1bn
= abT. (2.16)
∇X(aTXbT) =
2.4.8. f(X) = kXk2F
Giả sử X ∈ Rn×n, ta có
a2b1 a2b2 . . . a2bn . . . . . .... . . . amb1 amb2 . . . ambn
kXk2F =Xn i=1
Xn j=1
x2ij ⇒∂f
∂xij= 2xij ⇒ ∇kXk2F = 2X.
2.4.9. f(X) = trace(XT AX)
Giả sử rằng X = x1 x2 . . . xn ∈ Rm×n, A ∈ Rm×m. Bằng cách khai triển 48 Machine Learning cơ bản
Chương 2. Giải tích ma trận
XTAX =
xT1
xT2...
xTn
A x1 x2 . . . , xn =
xT1 Ax1 xT1 Ax2 . . . xT1 Axn
xT2 Ax1 xT2 Ax2 . . . xT2 Axn . . . . . .... . . . xTnAx1 xTnAx2 . . . xTnAxn
,
ta tính được trace(XTAX) = Pni=1 xTi Axi.
Sử dụng công thức ∇xixTi Axi = (A + AT)xi, ta có
∇Xtrace(XTAX) = (A + AT) x1 x2 . . . xn = (A + AT)X. (2.17) Bằng cách thay A = I, ta cũng thu được ∇Xtrace(XTX) = ∇XkXk2F = 2X. 2.4.10. f(X) = kAX − Bk2F
Bằng kỹ thuật hoàn toàn tương tự như đã làm trong Mục 2.4.4, ta thu được ∇XkAX − Bk2F = 2AT(AX − B).
2.5. Bảng các gradient thường gặp
Bảng 2.1 bao gồm gradient của các hàm số thường gặp với biến là vector hoặc ma trận.
Bảng 2.1: Bảng các gradient cơ bản.
f(x)
∇f(x)
f(X)
∇Xf(X)
x
I
trace(X)
I
aT x
a
trace(ATX)
A
xTAx
(A + AT)x
trace(XTAX)
(A + AT)X
xT x = kxk22
2x
trace(XTX) = kXk2F
2X
kAx − bk22
2AT(Ax − b)
kAX − Bk2F
2AT(AX − B)
aT(xT x)b
2aTbx
aTXb
abT
aT xxTb
(abT + baT)x
trace(ATXB)
ABT
2.6. Kiểm tra gradient
Việc tính gradient của hàm nhiều biến thông thường khá phức tạp và rất dễ mắc lỗi. Trong thực nghiệm, có một cách để kiểm tra liệu gradient tính được có chính xác không. Cách này dựa trên định nghĩa của đạo hàm cho hàm một biến.
Machine Learning cơ bản 49
Chương 2. Giải tích ma trận
2.6.1. Xấp xỉ đạo hàm của hàm một biến
Xét cách tính đạo hàm của hàm một biến theo định nghĩa:
f0(x) = limε→0f(x + ε) − f(x)
ε. (2.18)
Trên máy tính, ta có thể chọn ε rất nhỏ, ví dụ 10−6, rồi xấp xỉ đạo hàm này bởi f0(x) ≈ limε→0f(x + ε) − f(x)
ε. (2.19)
Trên thực tế, công thức xấp xỉ đạo hàm hai phía thường được sử dụng: f0(x) ≈f(x + ε) − f(x − ε)
2ε. (2.20)
Cách tính này được gọi là numerical gradient. Có hai cách giải thích việc tại sao cách tính như (2.20) được sử dụng rộng rãi hơn:
* Bằng giải tích
Sử dụng khai triển Taylor với ε rất nhỏ, ta có hai xấp xỉ sau: 2ε2 +f(3)
f(x + ε) ≈ f(x) + f0(x)ε +f”(x)
6ε3 + . . . (2.21)
2ε2 −f(3)
6ε3 + . . . (2.22)
Từ đó ta có:
f(x − ε) ≈ f(x) − f0(x)ε +f”(x)
f(x + ε) − f(x)
ε≈ f0(x) + f”(x)
2ε + · · · = f0(x) + O(ε). (2.23)
2ε≈ f0(x) + f(3)(x)
f(x + ε) − f(x − ε)
trong đó O() là Big O notation.
6ε2 + · · · = f0(x) + O(ε2). (2.24)
Từ đó, nếu xấp xỉ đạo hàm bằng công thức (2.23), sai số sẽ là O(ε). Trong khi đó, nếu xấp xỉ đạo hàm bằng công thức (2.24), sai số sẽ là O(ε2). Khi ε rất nhỏ, O(ε2) O(ε), tức cách đánh giá sử dụng công thức (2.24) có sai số nhỏ hơn, và vì vậy nó được sử dụng phổ biến hơn.
50 Machine Learning cơ bản
2ε
f(x0 + ε) − f(x0 − ε)
ε
Chương 2. Giải tích ma trận
Hình 2.1. Giải thích
cách xấp xỉ đạo hàm
bằng hình học
f(x0 + ε) − f(x0)
f(x0) − f(x0 − ε)
ε
* Bằng hình học
Quan sát Hình 2.1, vector nét liền là đạo hàm chính xác của hàm số tại điểm có hoành độ bằng x0. Hai vector nét đứt thể hiện xấp xỉ đạo hàm phía phải và phía trái. Vector chấm gạch thể hiện xấp xỉ đạo hàm hai phía. Trong ba vector xấp xỉ đó, vector chấm gạch gần với vector nét liền nhất nếu xét theo hướng.
Sự khác biệt giữa các phương pháp xấp xỉ còn lớn hơn nữa nếu tại điểm x, hàm số bị bẻ cong mạnh hơn. Khi đó, xấp xỉ trái và phải sẽ khác nhau rất nhiều. Xấp xỉ hai phía sẽ cho kết quả ổn định hơn.
2.6.2. Xấp xỉ gradient của hàm nhiều biến
Với hàm nhiều biến, công thức (2.24) được áp dụng cho từng biến khi các biến khác cố định. Cụ thể, ta sử dụng định nghĩa gradient của hàm số nhận đầu vào là một ma trận như công thức (2.3). Mỗi thành phần của ma trận kết quả là đạo hàm riêng của hàm số tại thành phần đó khi ta coi các thành phần còn lại cố định. Chúng ta sẽ thấy rõ điều này hơn ở cách lập trình so sánh hai cách tính gradient ngay sau đây.
Cách tính gradient xấp xỉ hai phía thường cho giá trị khá chính xác. Tuy nhiên, cách này không được sử dụng để tính gradient vì độ phức tạp quá cao so với cách tính trực tiếp. Tại mỗi thành phần, ta cần tính giá trị của hàm số tại phía trái và phía phải. Việc làm này không khả thi với các ma trận lớn. Khi so sánh đạo hàm xấp xỉ với gradient tính theo công thức, người ta thường giảm số chiều dữ liệu và giảm số điểm dữ liệu để thuận tiện cho tính toán. Nếu gradient tính được là chính xác, nó sẽ rất gần với gradient xấp xỉ này.
Đoạn code dưới đây giúp kiểm tra gradient của một hàm số khả vi f : Rm×n → R, có kèm theo hai ví dụ. Để sử dụng hàm kiểm tra check_grad này, ta cần viết hai hàm. Hàm thứ nhất là hàm fn(X) tính giá trị của hàm số tại X. Hàm thứ hai là hàm gr(X) tính giá trị của gradient của fn(X).
Machine Learning cơ bản 51
Chương 2. Giải tích ma trận
from __future__ import print_function
import numpy as np
def check_grad(fn, gr, X):
X_flat = X.reshape(-1) # convert X to an 1d array, 1 for loop needed shape_X = X.shape # original shape of X
num_grad = np.zeros_like(X) # numerical grad, shape = shape of X grad_flat = np.zeros_like(X_flat) # 1d version of grad
eps = 1e-6 # a small number, 1e-10 -> 1e-6 is usually good numElems = X_flat.shape[0] # number of elements in X
# calculate numerical gradient
for i in range(numElems): # iterate over all elements of X Xp_flat = X_flat.copy()
Xn_flat = X_flat.copy()
Xp_flat[i] += eps
Xn_flat[i] -= eps
Xp = Xp_flat.reshape(shape_X)
Xn = Xn_flat.reshape(shape_X)
grad_flat[i] = (fn(Xp) - fn(Xn))/(2*eps)
num_grad = grad_flat.reshape(shape_X)
diff = np.linalg.norm(num_grad - gr(X))
print(’Difference between two methods should be small:’, diff)
# ==== check if grad(trace(A*X)) == A^T ====
m, n = 10, 20
A = np.random.rand(m, n)
X = np.random.rand(n, m)
def fn1(X):
return np.trace(A.dot(X))
def gr1(X):
return A.T
check_grad(fn1, gr1, X)
# ==== check if grad(x^T*A*x) == (A + A^T)*x ====
A = np.random.rand(m, m)
x = np.random.rand(m, 1)
def fn2(x):
return x.T.dot(A).dot(x)
def gr2(x):
return (A + A.T).dot(x)
check_grad(fn2, gr2, x)
Kết quả:
Difference between two methods should be small: 2.02303323394e-08 Difference between two methods should be small: 2.10853872281e-09
52 Machine Learning cơ bản
Chương 2. Giải tích ma trận
Kết quả cho thấy sự khác nhau giữa Frobenious norm (norm mặc định trong np.linalg.norm) trong kết quả của hai cách tính là rất nhỏ. Sau khi chạy lại đoạn code với các giá trị m, n khác nhau và biến X khác nhau, nếu sự khác nhau vẫn là nhỏ, ta có thể kết luận rằng gradient mà ta tính được là chính xác.
Bạn đọc có thể kiểm tra lại các công thức trong Bảng 2.1 bằng phương pháp này. Machine Learning cơ bản 53
Chương 3. Ôn tập Xác suất
Chương 3
Ôn tập Xác suất
Chương này được viết dựa trên Chương 2 và 3 của cuốn Computer Vision: Models, Learning, and Inference – Simon J.D. Prince (https://goo.gl/GTEXzd).
3.1. Xác suất
3.1.1. Biến ngẫu nhiên
Một biến ngẫu nhiên (random variable) x là một biến dùng để đo những đại lượng không xác định. Biến này có thể được dùng để ký hiệu kết quả/đầu ra của một thí nghiệm, ví dụ như tung đồng xu, hoặc một đại lượng biến đổi trong tự nhiên, ví dụ như nhiệt độ trong ngày. Nếu quan sát một số lượng lớn đầu ra {xi}Ii=1 của các thí nghiệm này, ta có thể nhận được những giá trị khác nhau ở mỗi thí nghiệm. Tuy nhiên, sẽ có những giá trị xảy ra nhiều lần hơn những giá trị khác, hoặc xảy ra gần một giá trị này hơn những giá trị khác. Thông tin về đầu ra này được đo bởi một phân phối xác suất (probability distribution) được biểu diễn bằng một hàm p(x). Một biến ngẫu nhiên có thể là rời rạc hoặc liên tục.
Một biến ngẫu nhiên rời rạc sẽ lấy giá trị trong một tập hợp các điểm rời rạc cho trước. Ví dụ tung đồng xu thì có hai khả năng là xấp và ngửa. Tập các giá trị này có thể có thứ tự như khi tung xúc xắc hoặc không có thứ tự như khi đầu ra là các giá trị nắng, mưa, bão. Mỗi đầu ra có một giá trị xác suất tương ứng với nó. Các giá trị xác suất này không âm và có tổng bằng một.
Nếu x là biến ngẫu nhiên rời rạc thì X x
p(x) = 1. (3.1)
Biến ngẫu nhiên liên tục lấy giá trị là các số thực. Những giá trị này có thể là hữu hạn, ví dụ thời gian làm bài của mỗi thí sinh trong một bài thi 180 phút, hoặc vô hạn, ví dụ thời gian phải chờ tới khách hàng tiếp theo. Không như biến
54 Machine Learning cơ bản
Chương 3. Ôn tập Xác suất
ngẫu nhiên rời rạc, xác suất để đầu ra bằng chính xác một giá trị nào đó theo lý thuyết là bằng không. Thay vào đó, phân phối của biến ngẫu nhiên rời rạc thường được xác định dựa trên xác suất để đầu ra rơi vào một khoảng giá trị nào đó. Việc này được mô tả bởi một hàm số được gọi là hàm mật độ xác suất (probability density function, pdf). Hàm mật độ xác suất luôn cho giá trị dương, và tích phân của nó trên toàn miền giá trị đầu ra phải bằng một.
Z
Nếu x là biến ngẫu nhiên liên tục thì
p(x)dx = 1. (3.2)
Nếu x là một biến ngẫu nhiên rời rạc thì p(x) ≤ 1, ∀x. Trong khi đó, nếu x là biến ngẫu nhiên liên tục, p(x) có thể nhận giá trị không âm bất kỳ, điều này vẫn đảm bảo tích phân của hàm mật độ xác suất theo toàn bộ giá trị của x bằng một.
3.1.2. Xác suất đồng thời
Nếu quan sát số lượng lớn các cặp đầu ra của hai biến ngẫu nhiên x và y thì có những cặp đầu ra xảy ra thường xuyên hơn những cặp khác. Thông tin này được biểu diễn bằng một phân phối được gọi là xác suất đồng thời (joint probability) của x và y, được ký hiệu là p(x, y). Hai biến ngẫu nhiên x và y có thể cùng là biến ngẫu nhiên rời rạc, liên tục, hoặc một rời rạc, một liên tục. Luôn nhớ rằng tổng các xác suất trên mọi cặp giá trị (x, y) đều bằng một.
Cả x và y là rời rạc: X
p(x, y) = 1. (3.3)
Z
Cả x và y là liên tục:
x,y
p(x, y)dxdy = 1. (3.4)
x rời rạc, y liên tục: X x
Z
p(x, y)dy =
Z X x
p(x, y)
!
dy = 1. (3.5)
Xét ví dụ trong Hình 3.1, phần “Xác suất đồng thời”. Biến ngẫu nhiên x thể hiện điểm thi môn Toán của học sinh ở một trường THPT trong một kỳ thi quốc gia, biến ngẫu nhiên y thể hiện điểm thi môn Vật Lý cũng trong kỳ thi đó. Đại lượng p(x = x∗, y = y∗) là tỉ lệ giữa tần suất số học sinh được đồng thời x∗ điểm môn Toán và y∗ điểm môn Vật lý với toàn bộ số học sinh của trường đó. Tỉ lệ này có thể coi là xác suất khi số học sinh trong trường là lớn. Ở đây x∗ và y∗là các số xác định. Thông thường, xác suất này được viết gọn lại thành p(x∗, y∗), và p(x, y) được dùng như một hàm tổng quát để mô tả các xác suất.
Giả sử thêm rằng điểm các môn là các số tự nhiên từ 1 đến 10.
Các ô vuông màu đen thể hiện xác suất p(x, y), với diện tích ô vuông càng lớn biểu thị xác suất càng cao. Chú ý rằng tổng các xác suất này bằng một.
Machine Learning cơ bản 55
Chương 3. Ôn tập Xác suất Xác suất biên
(x) = X
(x, y)
y
1 2 3 4 5 6 7 8 9 10
10 9
8
(
Xác suất đồng thời
10
9
8
(x, y)
1 2 3 4 5 6 7 8 9 10
7 6 5 4 3 2 1
x
y) =
X (x, y
)
Lý y: Điểm
7
6
5
4
3
2
1
2
1
3
4
5
6
7
8
9
10
(x|y = 9)
1 2 3 4 5 6 7 8 9 10 (x|y = 3)
10 9
8
7
6
5
4
3
2
1
x: Điểm Toán
(
y|x =
2)
10 9
8
7
6
5
4
3
2
1
( y|x = 10)
Xác suất
có điều kiện
Hình 3.1. Xác suất đồng thời, xác suất biên, xác suất có điền kiện và mối quan hệ giữa chúng
Có thể thấy rằng xác suất để một học sinh được 10 điểm môn Toán và 1 điểm môn Lý rất thấp, điều tương tự xảy ra với 10 điểm môn Lý và 1 điểm môn Toán. Xác suất để một học sinh được khoảng 7 điểm cả hai môn là cao nhất.
Thông thường, chúng ta sẽ làm việc với các bài toán ở đó xác suất được xác định trên nhiều hơn hai biến ngẫu nhiên. Chẳng hạn, p(x, y, z) thể hiện xác suất đồng thời của ba biến ngẫu nhiên x, y và z. Khi có nhiều biến ngẫu nhiên, ta có thể viết chúng dưới dạng vector. Cụ thể, ta có thể viết p(x) để thể hiện xác suất của biến ngẫu nhiên nhiều chiều x = [x1, x2, . . . , xn]T. Khi có nhiều tập các biến ngẫu nhiên, ví dụ x và y, ta có thể viết p(x, y) để thể hiện xác suất đồng thời của tất cả các thành phần trong hai biến ngẫu nhiên nhiều chiều này.
56 Machine Learning cơ bản
Chương 3. Ôn tập Xác suất
3.1.3. Xác suất biên
Nếu biết xác suất đồng thời của nhiều biến ngẫu nhiên, ta cũng có thể xác định được phân phối xác suất của từng biến bằng cách lấy tổng (với biến ngẫu nhiên rời rạc) hoặc tích phân (với biến ngẫu nhiên liên tục) theo tất cả các biến còn lại:
Nếu x, y rời rạc: p(x) = X y
p(y) = X
x
Z
p(x, y), (3.6) p(x, y). (3.7)
Nếu x, y liên tục: p(x) = p(y) =
Z
p(x, y)dy, (3.8) p(x, y)dx. (3.9)
Với nhiều biến hơn, chẳng hạn bốn biến rời rạc x, y, z, w, cách tính được thực hiện tương tự:
p(x) = X y,z,w
p(x, y, z, w), (3.10)
p(x, y) = X z,w
p(x, y, z, w). (3.11)
Cách xác định xác suất của một biến dựa trên xác suất đồng thời của nó với các biến khác được gọi là phép biên hoá (marginalization). Xác suất đó được gọi là xác suất biên (marginal probability).
Từ đây trở đi, nếu không đề cập gì thêm, chúng ta sẽ dùng ký hiệu P để chỉ chung cho cả hai loại biến ngẫu nhiên rời rạc và liên tục. Nếu biến là liên tục, ta
sẽ ngầm hiểu rằng dấu tổng (P) cần được thay bằng dấu tích phân (R), biến lấy vi phân chính là biến được viết dưới dấu P. Chẳng hạn, trong (3.11), nếu z là liên tục, w là rời rạc, công thức đúng sẽ là
p(x, y) = X w
Z
p(x, y, z, w)dz
=
Z X w
p(x, y, z, w)
!
dz. (3.12)
Quay lại ví dụ trong Hình 3.1 với hai biến ngẫu nhiên rời rạc x, y. Lúc này, p(x) được hiểu là xác suất để một học sinh đạt được x điểm môn Toán. Xác suất này được biểu thị ở khu vực “Xác suất biên”. Có hai cách tính xác suất này. Cách thứ nhất là đếm số học sinh được x điểm môn toán rồi chia cho tổng số học sinh. Cách thứ hai dựa trên xác suất đồng thời để một học sinh được x điểm môn Toán và y điểm môn Lý. Số lượng học sinh đạt x = x∗ điểm môn Toán sẽ bằng tổng số học sinh đạt x = x∗ điểm môn Toán và y điểm môn Lý, với y là một giá trị bất kỳ từ 1 đến 10. vì vậy, để tính xác suất p(x), ta chỉ cần tính tổng của toàn bộ p(x, y) với y chạy từ 1 đến 10.
Machine Learning cơ bản 57
Chương 3. Ôn tập Xác suất
Dựa trên nhận xét này, mỗi giá trị của p(x) chính bằng tổng các giá trị trong cột thứ x của hình vuông trung tâm. Mỗi giá trị của p(y) sẽ bằng tổng các giá trị trong hàng thứ y tính từ đưới lên của hình vuông đó. Chú ý rằng tổng các xác suất luôn bằng một.
3.1.4. Xác suất có điều kiện.
Dựa vào phân phối điểm của các học sinh, liệu ta có thể tính được xác suất để một học sinh được điểm 10 môn Lý, biết rằng học sinh đó được điểm 1 môn Toán?
Xác suất để một biến ngẫu nhiên x nhận một giá trị nào đó biết rằng biến ngẫu nhiên y có giá trị y∗ được gọi là xác suất có điều kiện (conditional probability), ký hiệu là p(x|y = y∗).
Xác suất có điều kiện p(x|y = y∗) có thể được tính dựa trên xác suất đồng thời p(x, y). Quay lại Hình 3.1 ở khu vực “Xác suất có điều kiện”. Nếu biết rằng y = 9, xác suất p(x|y = 9) có thể tính được dựa trên hàng thứ chín của hình vuông trung tâm, tức hàng p(x, y = 9). Xác suất p(x|y = 9) lớn nếu p(x, y = 9) lớn. Chú ý rằng tổng các xác suất Pxp(x, y = 9) nhỏ hơn một, và bằng tổng các xác suất trên hàng thứ chín này. Để thoả mãn điều kiện tổng các xác suất bằng một, ta cần chia mỗi đại lượng p(x, y = 9) cho tổng của hàng này, tức là
p(x|y = 9) = p(x, y = 9)
p(x, y = 9) =p(x, y = 9)
P
p(y = 9) . (3.13)
x
Tổng quát,
p(x|y = y∗) = p(x, y = y∗)
p(x, y = y∗)=p(x, y = y∗)
P
p(y = y∗), (3.14)
x
ở đây ta đã sử dụng công thức tính xác suất biên trong (3.7) cho mẫu số. Thông thường, ta có thể viết xác suất có điều kiện mà không cần chỉ rõ giá trị y = y∗ và có các công thức gọn hơn:
p(y), p(y|x) = p(y, x)
p(x). (3.15)
Từ đó ta có quan hệ
p(x|y) = p(x, y)
p(x, y) = p(x|y)p(y) = p(y|x)p(x). (3.16)
Khi có nhiều hơn hai biến ngẫu nhiên, ta có các công thức
p(x, y, z, w) = p(x, y, z|w)p(w) (3.17) = p(x, y|z, w)p(z, w) = p(x, y|z, w)p(z|w)p(w) (3.18)
= p(x|y, z, w)p(y|z, w)p(z|w)p(w). (3.19)
Công thức (3.19) có dạng chuỗi và được sử dụng nhiều sau này. 58 Machine Learning cơ bản
Chương 3. Ôn tập Xác suất
3.1.5. Quy tắc Bayes
Công thức (3.16) biểu diễn xác suất đồng thời theo hai cách. Từ đó có thể suy ra p(y|x)p(x) = p(x|y)p(y). (3.20)
Biến đối một chút:
p(y|x) = p(x|y)p(y)
p(x)(3.21)
=p(x|y)p(y)
P y
p(x, y)(3.22)
=p(x|y)p(y)
P y
p(x|y)p(y). (3.23)
Trong dòng thứ hai và thứ ba, các công thức về xác suất biên và xác suất đồng thời ở mẫu số đã được sử dụng. Từ (3.23) ta có thể thấy rằng p(y|x) hoàn toàn có thể tính được nếu ta biết mọi p(x|y) và p(y). Tuy nhiên, việc tính trực tiếp xác suất này thường phức tạp.
Ba công thức (3.21)-(3.23) thường được gọi là quy tắc Bayes. Chúng được sử dụng rộng rãi trong machine learning
3.1.6. Biến ngẫu nhiên độc lập
Nếu biết giá trị của một biến ngẫu nhiên x không mang lại thông tin về việc suy ra giá trị của biến ngẫu nhiên y và ngược lại, thì ta nói rằng hai biến ngẫu nhiên này là độc lập. Chẳng hạn, chiều cao của một học sinh và điểm thi môn Toán của học sinh đó có thể coi là hai biến ngẫu nhiên độc lập. Khi hai biến ngẫu nhiên x và y là độc lập, ta có
p(x|y) = p(x), (3.24)
p(y|x) = p(y). (3.25)
Thay vào biểu thức xác suất đồng thời trong (3.16), ta có
p(x, y) = p(x|y)p(y) = p(x)p(y). (3.26)
3.1.7. Kỳ vọng
Kỳ vọng (expectation) của một biến ngẫu nhiên x được định nghĩa bởi
E[x] = X
xp(x) nếu x là rời rạc. (3.27)
Z
E[x] =
x
xp(x)dx nếu x là liên tục. (3.28)
Machine Learning cơ bản 59
Chương 3. Ôn tập Xác suất
Giả sử f(.) là một hàm số trả về một số với mỗi giá trị x∗của biến ngẫu nhiên x. Khi đó, nếu x là biến ngẫu nhiên rời rạc, ta có
E[f(x)] = X x
f(x)p(x). (3.29)
Công thức cho biến ngẫu nhiên liên tục cũng được viết tương tự. Với xác suất đồng thời, kỳ vọng của một hàm cũng được xác định tương tự:
E[f(x, y)] = X
x,y
Có ba tính chất cần nhớ về kỳ vọng:
f(x, y)p(x, y)dxdy. (3.30)
a. Kỳ vọng của một hằng số theo một biến ngẫu nhiên x bất kỳ bằng chính hằng số đó:
E[α] = α. (3.31)
b. Kỳ vọng có tính chất tuyến tính:
E[αx] = αE[x], (3.32)
E[f(x) + g(x)] = E[f(x)] + E[g(x)]. (3.33)
c. Kỳ vọng của tích hai biến ngẫu nhiên độc lập bằng tích kỳ vọng của chúng: E[f(x)g(y)] = E[f(x)]E[g(y)]. (3.34)
Khái niệm kỳ vọng thường đi kèm với khái niệm phương sai (variance) trong không gian một chiều và ma trận hiệp phương sai (covariance matrix) trong không gian nhiều chiều.
3.1.8. Phương sai
Cho N giá trị x1, x2, . . . , xN . Kỳ vọng và phương sai của bộ dữ liệu này được tính theo công thức
x¯ =1NXN n=1
σ2 =1NXN n=1
xn =1Nx1, (3.35) (xn − x¯)2, (3.36)
với x = x1, x2, . . . , xN , và 1 ∈ RN là vector cột chứa toàn phần tử 1. Kỳ vọng đơn giản là trung bình cộng của toàn bộ các giá trị. Phương sai là trung bình
60 Machine Learning cơ bản
σx¯ (a)
x
e2
σ1
σ2 e1
(b)
Chương 3. Ôn tập Xác suất e2
σ1
e1
σ2
(c)
Hình 3.2. Ví dụ về kỳ vọng và phương sai. (a) Dữ liệu trong không gian một chiều. (b) Dữ liệu trong không gian hai chiều mà hai chiều không tương quan. Trong trường hợp này, ma trận hiệp phương sai là ma trận đường chéo với hai phần tử trên đường chéo là σ1, σ2, đây cũng chính là hai trị riêng của ma trận hiệp phương sai và là phương sai của mỗi chiều dữ liệu. (c) Dữ liệu trong không gian hai chiều có tương quan. Theo mỗi chiều, ta có thể tính được kỳ vọng và phương sai. Phương sai càng lớn thì dữ liệu trong chiều đó càng phân tán. Trong ví dụ này, dữ liệu theo chiều thứ hai phân tán nhiều hơn so với chiều thứ nhất.
cộng của bình phương khoảng cách từ mỗi điểm tới kỳ vọng. Phương sai càng nhỏ, các điểm dữ liệu càng gần với kỳ vọng, tức các điểm dữ liệu càng giống nhau. Phương sai càng lớn, dữ liệu càng có tính phân tán. Ví dụ về kỳ vọng và phương sai của dữ liệu một chiều có thể được thấy trong Hình 3.2a.
Căn bậc hai của phương sai, σ còn được gọi là độ lệch chuẩn (standard deviation) của dữ liệu.
3.1.9. Ma trận hiệp phương sai
Cho N điểm dữ liệu được biểu diễn bởi các vector cột x1, . . . , xN , khi đó, vector kỳ vọng và ma trận hiệp phương sai của toàn bộ dữ liệu được định nghĩa là
x¯ =1NXN n=1
S =1NXN n=1
xn, (3.37) (xn − x¯)(xn − x¯)T =1NXˆ Xˆ T. (3.38)
Trong đó Xˆ được tạo bằng cách trừ mỗi cột của X đi x¯:
xˆn = xn − x¯. (3.39)
Machine Learning cơ bản 61
Chương 3. Ôn tập Xác suất
Một vài tính chất của ma trận hiệp phương sai:
a. Ma trận hiệp phương sai là một ma trận đối xứng, hơn nữa, nó là một ma trận nửa xác định dương.
b. Mọi phần tử trên đường chéo của ma trận hiệp phương sai là các số không âm. Chúng chính là phương sai của từng chiều dữ liệu.
c. Các phần tử ngoài đường chéo sij , i 6= j thể hiện sự tương quan giữa thành phần thứ i và thứ j của dữ liệu, còn được gọi là hiệp phương sai. Giá trị này có thể dương, âm hoặc bằng không. Khi nó bằng không, ta nói rằng hai thành phần i, j trong dữ liệu là không tương quan.
d. Nếu ma trận hiệp phương sai là ma trận đường chéo, ta có dữ liệu hoàn toàn không tương quan giữa các chiều.
Ví dụ về sự tương quan của dữ liệu được cho trong Hình 3.2b và 3.2c. 3.2. Một vài phân phối thường gặp
3.2.1. Phân phối Bernoulli
Phân phối Bernoulli là một phân phối rời rạc mô tả các biến ngẫu nhiên nhị phân với đầu ra chỉ nhận một trong hai giá trị x ∈ {0, 1}. Hai giá trị này có thể là xấp và ngửa khi tung đồng xu; có thể là giao dịch lừa đảo và giao dịch thông thường trong bài toán xác định giao dịch lừa đảo trong tín dụng; có thể là người và không phải người trong bài toán xác định xem trong một bức ảnh có người hay không.
Phân phối Bernoulli được mô tả bằng một tham số λ ∈ [0, 1]. Xác suất của mỗi đầu ra là
p(x = 1) = λ, p(x = 0) = 1 − p(x = 1) = 1 − λ. (3.40) Hai đẳng thức này thường được viết gọn lại thành
p(x) = λx(1 − λ)1−x, (3.41)
với giả định 00 = 1. Thật vậy, p(0) = λ0(1−λ)1 = 1−λ, và p(1) = λ1(1−λ)0 = λ.
Phân phối Bernoulli thường được ký hiệu ngắn gọn dưới dạng p(x) = Bernx[λ]. (3.42)
3.2.2. Phân phối categorical
Trong nhiều trường hợp, đầu ra của biến ngẫu nhiên rời rạc có thể nhận nhiều hơn hai giá trị. Ví dụ, một bức ảnh có thể chứa một chiếc xe, một người, hoặc
62 Machine Learning cơ bản
Chương 3. Ôn tập Xác suất
một con mèo. Khi đó, ta dùng một phân phối tổng quát của phân phối Bernoulli, được gọi là phân phối categorical. Các đầu ra được mô tả bởi một phần tử trong tập hợp {1, 2, . . . , K}.
Nếu có K đầu ra, phân phối categorical sẽ được mô tả bởi K tham số, viết dưới dạng vector λ = [λ1, λ2, . . . , λK] với các λk không âm và có tổng bằng một. Mỗi giá trị λk thể hiện xác suất để đầu ra nhận giá trị k: p(x = k) = λk.
Phân phối categorical thường được ký hiệu dưới dạng:
p(x) = Catx[λ]. (3.43)
Cách biểu diễn đầu ra là một số k trong tập hợp {1, 2, . . . , K} có thể được thay bằng biểu diễn one-hot. Mỗi vector one-hot là một vector K phần tử, trong đó K − 1 phần tử bằng 0, một phần tử bằng 1 tại vị trí ứng với đầu ra k. Nói cách khác, mỗi đầu ra là một trong các vector đơn vị bậc K: {e1, e2, . . . , eK}. Ta có
thể viết
p(x = k) = p(x = ek) = YK j=1
λxj
j = λk. (3.44)
Dấu bằng cuối cùng xảy ra vì xk = 1, xj = 0 ∀j 6= k.
3.2.3. Phân phối chuẩn một chiều
Phân phối chuẩn một chiều (univariate normal distribution) được định nghĩa trên các biến liên tục nhận giá trị x ∈ (−∞,∞). Đây là một phân phối được sử dụng nhiều nhất với các biến ngẫu nhiên liên tục. Phân phối này được mô tả bởi hai tham số: kỳ vọng µ và phương sai σ2.
Hàm mật độ xác suất của phân phối này được định nghĩa bởi
p(x) = 1
√2πσ2exp
−(x − µ)2 2σ2
. (3.45)
Hàm mật độ này thường được viết gọn dưới dạng p(x) = Normx[µ, σ2] hoặc N (µ, σ2).
Ví dụ về đồ thị hàm mật độ xác suất của phân phối chuẩn một chiều được biểu thị trên Hình 3.3a.
3.2.4. Phân phối chuẩn nhiều chiều
Phân phối chuẩn nhiều chiều (multivariate normal distribution) là trường hợp tổng quát của phân phối chuẩn khi biến ngẫu nhiên là nhiều chiều, giả sử là D chiều. Có hai tham số mô tả phân phối này là vector kỳ vọng µ ∈ RD và ma trận hiệp phương sai Σ ∈ SD là một ma trận đối xứng xác định dương.
Machine Learning cơ bản 63
Chương 3. Ôn tập Xác suất
0.5
0.4
p(x)
0.3
0.2
0.1
0.0
µ = .5, σ2 = .5
µ = 0, σ2 = 1
p(x, y)
µ = −1, σ2 = 2
2
−2
0
y
−7.5 −5.0 −2.5 0.0 2.5 5.0 7.5 x
(a)
0
x
(b)
2
−2
Hình 3.3. Ví dụ về hàm mật độ xác suất của (a) phân phối chuẩn một chiều, và (b) phân phối chuẩn hai chiều.
Hàm mật độ xác suất có dạng
p(x) = 1
(2π)D/2|Σ|1/2exp
−12(x − µ)T Σ−1(x − µ) , (3.46)
với |Σ| là định thức của ma trận hiệp phương sai Σ.
Hàm mật độ này thường được viết gọn lại dưới dạng p(x) = Normx[µ, Σ] hoặc N (µ, Σ).
Ví dụ về hàm mật độ xác suất của một phân phối chuẩn hai chiều được mô tả bởi một mặt cong trên Hình 3.3b. Nếu cắt mặt này theo các mặt phẳng song song với mặt đáy, ta sẽ thu được các hình ellipse đồng tâm.
3.2.5. Phân phối Beta
Phân phối Beta là một phân phối liên tục được định nghĩa trên một biến ngẫu nhiên λ ∈ [0, 1]. Phân phối Beta được dùng để mô tả tham số cho một phân phối khác. Cụ thể, phân phối này phù hợp với việc mô tả sự biến động của tham số λ trong phân phối Bernoulli.
Phân phối Beta được mô tả bởi hai tham số dương α, β. Hàm mật độ xác suất của nó được cho bởi
p(λ) = Γ(α + β)
Γ(α)Γ(β)λα−1(1 − λ)β−1, (3.47)
với Γ(.) là hàm số gamma, được định nghĩa bởi
Z ∞
Γ(z) =
0
tz−1exp(−t)dt. (3.48)
64 Machine Learning cơ bản
(2, 2)
(0.5, 0.5)
(10, 10)
(0.1, 0.1)
p(λ)
(1, 1)
(4, 12)
(1, 3)
(2, 6)
(0.25, 0.75)
p(λ)
Chương 3. Ôn tập Xác suất
(12, 4)
(6, 2)
(3, 1)
(1.5, 0.5)
p(λ)
0.00 0.25 0.50 0.75 1.00 λ
(a) α = β
0.00 0.25 0.50 0.75 1.00 λ
(b) α < β
0.00 0.25 0.50 0.75 1.00 λ
(c) α > β
Hình 3.4. Ví dụ về hàm mật độ xác suất của phân phối Beta. (a) α = β, đồ thị hàm số là đối xứng. (b) α < β, đồ thị hàm số lệch sang trái, chứng tỏ xác suất λ nhỏ là lớn. (c) α > β, đồ thị hàm số lệch sang phải, chứng tỏ xác suất λ lớn là lớn.
Trên thực tế, việc tính giá trị của hàm số gamma không thực sự quan trọng vì nó chỉ mang tính chuẩn hoá để tổng xác suất bằng một.
Phân phối Beta thường được ký hiệu là p(λ) = Betaλ[α, β].
Hình 3.4 minh hoạ hàm mật độ xác suất của phân phối Beta với các cặp giá trị (α, β) khác nhau.
• Trong Hình 3.4a, khi α = β. Đồ thị của các hàm mật độ xác suất đối xứng qua đường thẳng λ = 0.5. Khi α = β = 1, thay vào (3.47), ta thấy p(λ) = 1 với mọi λ. Trong trường hợp này, phân phối Beta trở thành phân phối đều Khi α = β > 1, các hàm số đạt giá trị cao tại gần trung tâm, tức λ sẽ nhận giá trị xung quanh điểm 0.5 với xác suất cao. Khi α = β < 1, hàm số đạt giá trị cao tại các điểm gần 0 và 1.
• Trong Hình 3.4b, khi α < β, ta thấy rằng đồ thị có xu hướng lệch sang bên trái. Các giá trị (α, β) này nên được sử dụng nếu ta dự đoán rằng λ là một số nhỏ hơn 0.5.
• Trong Hình 3.4c, khi α > β, điều ngược lại xảy ra với các hàm số đạt giá trị cao tại các điểm gần 1.
Machine Learning cơ bản 65
Chương 3. Ôn tập Xác suất
3.2.6. Phân phối Dirichlet
Phân phối Dirichlet chính là trường hợp tổng quát của phân phối Beta khi được dùng để mô tả tham số của phân phối categorical. Nhắc lại rằng phân phối categorical là trường hợp tổng quát của phân phối Bernoulli.
Phân phối Dirichlet được định nghĩa trên K biến liên tục λ1, . . . , λK trong đó các λk không âm và có tổng bằng một. Bởi vậy, nó phù hợp để mô tả tham số của phân phối categorical. Có K tham số dương để mô tả một phân phối Dirichlet: α1, . . . , αK.
Hàm mật độ xác suất của phân phối Dirichlet được cho bởi
p(λ1, . . . , λK) = Γ(PKk=1 αk)
QK
k=1 Γ(αk)
YK k=1
λαk−1
k. (3.49)
Dạng thu gọn của nó là p(λ1, . . . , λK) = Dirλ1,...,λK[α1, . . . , αK]. 66 Machine Learning cơ bản
Chương 4. Ước lượng tham số mô hình
Chương 4
Ước lượng tham số mô hình
4.1. Giới thiệu
Có rất nhiều mô hình machine learning được xây dựng dựa trên các mô hình thống kê. Các mô hình thống kê thường dựa trên các phân phối xác suất đã được đề cập trong Chương 3. Với một mô hình thông kê bất kỳ, ký hiệu θ là tập hợp tất cả các tham số của mô hình đó. Với phân phối Bernoulli, tham số là biến λ. Với phân phối chuẩn nhiều chiều, các tham số là vector kỳ vọng µ và ma trận hiệp phương sai Σ. “Learning” chính là quá trình ước lượng bộ tham số θ sao cho mô hình tìm được khớp với phân phối của dữ liệu nhất. Quá trình này còn được gọi là ước lượng tham số (parameter estimation).
Có hai cách ước lượng tham số thường được dùng trong các mô hình machine learning thống kê. Cách thứ nhất chỉ dựa trên dữ liệu đã biết trong tập huấn luyện, được gọi là ước lượng hợp lý cực đại(maximum likelihood estimation hay ML estimation hoặc MLE). Cách thứ hai không những dựa trên tập huấn luyện mà còn dựa trên những thông tin biết trước của các tham số. Những thông tin này có thể có được bằng cảm quan của người xây dựng mô hình. Cảm quan càng rõ ràng, càng hợp lý thì khả năng thu được bộ tham số tốt càng cao. Chẳng hạn, thông tin biết trước của λ trong phân phối Bernoulli là việc nó là một số trong đoạn [0, 1]. Với bài toán tung đồng xu, với λ là xác suất có được mặt xấp, ta dự đoán được rằng giá trị này là một số gần với 0.5. Cách ước lượng tham số thứ hai này được gọi là ước lượng hậu nghiệm cực đại (maximum a posteriori estimation hay MAP estimation). Trong chương này, chúng ta cùng tìm hiểu ý tưởng và cách giải quyết bài toán ước lượng tham số mô hình theo MLE hoặc MAP.
Machine Learning cơ bản 67
Chương 4. Ước lượng tham số mô hình
4.2. Ước lượng hợp lý cực đại
4.2.1. Ý tưởng
Giả sử có các điểm dữ liệu x1, x2, . . . , xN tuân theo một phân phối nào đó được mô tả bởi bộ tham số θ. Ước lượng hợp lý cực đại là việc đi tìm bộ tham số θ để
θ = argmax θ
p(x1, . . . , xN |θ). (4.1)
Bài toán (4.1) có ý nghĩa như thế nào và vì sao việc này hợp lý?
Giả sử rằng ta đã biết rằng mô hình có dạng đặc biệt được mô tả bởi bộ tham số θ. Xác suất có điều kiện p(x1|θ) chính là xác suất xảy ra sự kiện x1 trong trường hợp mô hình được mô tả bởi bộ tham số θ. Tương tự, p(x1, . . . , xN |θ) là xác suất để toàn bộ các sự kiện x1, x2, . . . , xN đồng thời xảy ra, xác suất đồng thời này còn được gọi là sự hợp lý (likelihood).
Phân phối của dữ liệu và bản thân dữ liệu có thể lần lượt được coi là nguyên nhân và kết quả. Ta cần tìm nguyên nhân (bộ tham số θ) để khả năng xảy ra kết quả (hàm hợp lý) là cao nhất.
4.2.2. Giả sử về sự độc lập và log-likelihood
Người ta thường ít khi giải trực tiếp bài toán (4.1) vì khó tìm được một mô hình xác suất đồng thời cho toàn bộ dữ liệu. Một cách tiếp cận phổ biến là đơn giản hoá mô hình bằng cách giả sử các điểm dữ liệu xn độc lập với nhau khi biết bộ tham số θ. Nói cách khác, hàm hợp lý trong (4.1) được xấp xỉ bởi6
p(x1, . . . , xN |θ) ≈YN n=1
p(xn|θ). (4.2)
Lúc đó, bài toán (4.1) có thể được giải quyết bằng cách giải bài toán tối ưu
θ = argmax θ
YN n=1
p(xn|θ) (4.3)
Mỗi giá trị p(xn|θ) là một số dương nhỏ hơn một. Khi N lớn, tích của các số dương này rất gần với 0, máy tính có thể không lưu chính xác được do sai số tính toán. Để tránh hiện tượng này, việc tối đa hàm mục tiêu thường được chuyển về việc tối đa logarit7của hàm mục tiêu:
θ = argmax θ
log
YN n=1
p(xn|θ)
!
= argmax θ
XN n=1
log (p(xn|θ)). (4.4)
6 Nhắc lại rằng nếu hai sự kiện x, y là độc lập thì xác suất đồng thời bằng tích xác suất của từng sự kiện: p(x, y) = p(x)p(y). Với xác suất có điều kiện, p(x, y|z) = p(x|z)p(y|z).
7 Logarit là một hàm đồng biến.
68 Machine Learning cơ bản
Chương 4. Ước lượng tham số mô hình
4.2.3. Ví dụ
Ví dụ 1: Phân phối Bernoulli
Bài toán: Giả sử tung một đồng xu N lần và nhận được n mặt ngửa, hãy ước lượng xác suất nhận được mặt ngửa khi tung đồng xu đó.
Lời giải:
Một cách tự nhiên, ta có thể ước lượng xác suất đó là λ =nN. Chúng ta cùng ước lượng giá trị này bằng phương pháp MLE.
Đặt λ là xác suất để nhận được một mặt ngửa và x1, x2, . . . , xN là các đầu ra quan sát thấy. Trong N giá trị này, có n giá trị bằng 1 tương ứng với mặt ngửa và m = N − n giá trị bằng 0 tương ứng với mặt xấp. Nhận thấy
XN i=1
xi = n, N −XN i=1
xi = N − n = m. (4.5)
Vì đây là một xác suất của biến ngẫu nhiên nhị phân rời rạc, sự kiện nhận được mặt ngửa hay xấp khi tung đồng xu tuân theo phân phối Bernoulli:
p(xi|λ) = λxi(1 − λ)1−xi. (4.6)
Khi đó tham số mô hình λ có thể được ước lượng bằng việc giải bài toán tối ưu sau đây, với giả sử rằng kết quả của các lần tung đồng xu độc lập với nhau:
λ = argmax
[p(x1, x2, . . . , xN |λ)] = argmax
"YN
p(xi|λ)
#
(4.7)
λ
= argmax λ
"YN i=1
#
λxi(1 − λ)1−xi
λ
= argmax λ
i=1
h
λPNi=1 xi(1 − λ)N−PNi=1 xii(4.8)
= argmax λ
[λn(1 − λ)m] = argmax λ
[n log(λ) + m log(1 − λ)] (4.9)
Tới đây, bài toán tối ưu (4.9) có thể được giải bằng cách giải phương trình đạo hàm của hàm mục tiêu bằng 0. Tức λ là nghiệm của phương trình n
λ−m
1 − λ= 0 ⇔nλ=m
1 − λ⇔ λ =n
n + m=nN(4.10)
Vậy kết quả ước lượng ban đầu là có cơ sở.
Ví dụ 2: Phân phối categorical
Bài toán: Giả sử tung một viên xúc xắc sáu mặt có xác suất rơi vào các mặt không đều nhau. Giả sử trong N lần tung, số lượng xuất hiện các mặt thứ nhất,
Machine Learning cơ bản 69
Chương 4. Ước lượng tham số mô hình
thứ hai,. . . , thứ sáu lần lượt là n1, n2, . . . , n6 lần với X6 i=1
rơi vào mỗi mặt. Giả sử thêm rằng ni > 0, ∀i = 1, . . . , 6. Lời giải:
ni = N. Tính xác suất
Bài toán này phức tạp hơn bài toán trên, nhưng ta cũng có thể dự đoán được ước lượng tốt nhất của xác suất rơi vào mặt thứ i là λi =ni
N.
Mã hoá mỗi kết quả đầu ra thứ i bởi một vector 6 chiều xi ∈ {0, 1}6trong đó các phần tử của nó bằng 0 trừ phần tử tương ứng với mặt quan sát được bằng 1. Ta
có PNi=1 xji = nj, ∀j = 1, 2, . . . , 6, trong đó xjilà thành phần thứ j của vector xi.
Nhận thấy rằng xác suất rơi vào mỗi mặt tuân theo phân phối categorical với các tham số λj > 0, j = 1, 2, . . . , 6. Ta dùng λ để thể hiện cho cả sáu tham số này.
Với các tham số λ, xác suất để sự kiện xi xảy ra là
p(xi|λ) = Y6 j=1
λxji
j(4.11)
Khi đó, vẫn với giả sử về sự độc lập giữa các lần tung xúc xắc, ước lượng bộ tham
số λ dựa trên việc tối đa log-likelihood ta có:
"YN
λ = argmax λ
"YN
i=1
"Y6
p(xi|λ) PN
#
= argmax λ
#
i=1
"Y6
Y6 j=1
λxji j
#
#
(4.12)
= argmax λ
λ
j
j=1
"X6
i=1 xji
= argmax λ
#
λnj
j
j=1
(4.13)
= argmax λ
njlog(λj )
j=1
. (4.14)
Khác với bài toán (4.9), chúng ta không được quên điều kiện P6j=1 λj = 1. Ta có bài toán tối ưu có ràng buộc sau đây:
max λ
X6 j=1
njlog(λj ) thoả mãn:X6 j=1
λj = 1 (4.15)
Bài toán tối ưu này có thể được giải bằng phương pháp nhân tử Lagrange (xem Phụ lục A).
Lagrangian của bài toán này là
L(λ, µ) = X6 j=1
njlog(λj ) + µ(1 −X6 j=1
λj ) (4.16)
70 Machine Learning cơ bản
Chương 4. Ước lượng tham số mô hình
Nghiệm của bài toán là nghiệm của hệ đạo hàm L(.) theo từng biến bằng 0: ∂L(λ, µ)
∂λj=nj
λj− µ = 0, ∀j = 1, 2, . . . , 6; (4.17)
∂µ = 1 −X6
∂L(λ, µ)
j=1
λj = 0. (4.18)
Từ (4.17) ta có λj =njµ. Thay vào (4.18):
X6 j=1
µ= 1 ⇒ µ =X6
nj
j=1
nj = N (4.19)
Từ đó ta có ước lượng λj =nj
N, ∀j = 1, 2, . . . , 6.
Qua hai ví dụ trên ta thấy MLE cho kết quả khá hợp lý.
Ví dụ 3: Phân phối chuẩn một chiều
Bài toán: Khi thực hiện một phép đo, giả sử rằng rất khó để có thể đo chính xác độ dài của một vật. Thay vào đó, người ta thường đo vật đó nhiều lần rồi suy ra kết quả, với giả thiết rằng các phép đo độc lập với nhau và kết quả mỗi phép đo tuân theo một phân phối chuẩn. Hãy ước lượng chiều dài của vật đó dựa trên các kết quả đo được.
Lời giải:
Vì đã biết kết quả phép đo tuân theo phân phối chuẩn, ta sẽ đi tìm phân phối chuẩn đó. Chiều dài của vật có thể được coi là giá trị mà hàm mật độ xác suất đạt giá trị cao nhất. Trong phân phối chuẩn, ta biết rằng hàm mật độ xác suất đạt giá trị lớn nhất tại kỳ vọng của phân phối đó. Chú ý rằng kỳ vọng của phân phối và kỳ vọng của dữ liệu quan sát được có thể không bằng nhau, nhưng rất gần nhau. Nếu ước lượng kỳ vọng của phân phối bằng MLE, ta sẽ thấy rằng kỳ vọng của dữ liệu chính là đánh giá tốt nhất cho kỳ vọng của phân phối.
Thật vậy, giả sử các kích thước quan sát được là x1, x2, . . . , xN . Ta cần đi tìm một phân phối chuẩn, được mô tả bởi giá trị kỳ vọng µ và phương sai σ2, sao cho các giá trị x1, x2, . . . , xN là hợp lý nhất. Ta đã biết rằng, hàm mật độ xác suất tại xi của môt phân phối chuẩn có kỳ vọng µ và phương sai σ2là
p(xi|µ, σ2) = 1
√2πσ2exp
−(xi − µ)2 2σ2
. (4.20)
Để đánh giá µ và σ, ta sử dụng MLE với giả thiết rằng kết quả các phép đo là độc lập:
Machine Learning cơ bản 71
Chương 4. Ước lượng tham số mô hình "YN
#
µ, σ = argmax µ,σ
"
i=1
p(xi|µ, σ2) 1
PN
i=1(xi − µ)2
(4.21)
!#
= argmax µ,σ
"
(2πσ2)N/2exp
−
2σ2
(4.22)
#
= argmax µ,σ
−N log(σ) −
PN
i=1(xi − µ)2
2σ2, J(µ, σ)
. (4.23)
Ta đã lấy logarit của hàm bên trong dấu ngoặc vuông của (4.22) để được (4.23), phần hằng số có chứa 2π cũng đã được bỏ đi vì không ảnh hưởng tới kết quả.
Để tìm µ và σ, ta giải hệ phương trình đạo hàm của J(µ, σ) theo mỗi biến bằng không:
∂µ =1σ2XN
∂J
i=1
(xi − µ) = 0 (4.24)
∂σ = −Nσ+1σ3XN ∂J
(xi − µ)2 = 0 (4.25)
PN
i=1 xi
i=1
PN
i=1(xi − µ)2
⇒ µ =
N, σ2 =
N. (4.26)
Kết quả thu được không có gì bất ngờ.
Ví dụ 4: Phân phối chuẩn nhiều chiều
Bài toán: Giả sử tập dữ liệu ta thu được là các giá trị nhiều chiều x1, . . . , xN tuân theo phân phối chuẩn. Hãy đánh giá vector kỳ vọng µ và ma trận hiệp phương sai Σ của phân phối này bằng MLE, giả sử rằng các x1, . . . , xN độc lập.
Lời giải:
Việc chứng minh các công thức
PN
i=1 xi
µ =
N, (4.27)
Σ =1NXN i=1
(x − µ)(x − µ)T(4.28)
xin được dành lại cho bạn đọc như một bài tập nhỏ. Dưới đây là một vài gợi ý: • Hàm mật độ xác suất của phân phối chuẩn nhiều chiều là
72 Machine Learning cơ bản
Chương 4. Ước lượng tham số mô hình
p(x|µ, Σ) = 1
(2π)D/2|Σ|1/2exp
−12(x − µ)T Σ−1(x − µ) . (4.29)
Chú ý rằng ma trận hiệp phương sai Σ là xác định dương nên có nghịch đảo. • Một vài đạo hàm theo ma trận:
∇Σ log |Σ| = (Σ−1)T , Σ−T(chuyển vị của nghịch đảo)
(4.30)
∇Σ(xi − µ)T Σ−1(xi − µ) = −Σ−T(xi − µ)(xi − µ)T Σ−T(4.31)
(Xem thêm Matrix Calculus, mục D.2.1 và D.2.4 tại https://goo.gl/JKg631.) 4.3. Ước lượng hậu nghiệm cực đại
4.3.1. Ý tưởng
Quay lại với Ví dụ 1 về bài toán tung đồng xu. Nếu tung đồng xu 5000 lần và nhận được 1000 lần ngửa, ta có thể đánh giá xác suất nhận được mặt ngửa là 1/5 và việc đánh giá này là đáng tin vì số mẫu lớn. Nếu tung năm lần và chỉ nhận được một mặt ngửa, theo MLE, xác suất để có một mặt ngửa được ước lượng là 1/5. Tuy nhiên với chỉ năm kết quả, ước lượng này là không đáng tin. Khi tập huấn luyện quá nhỏ, ta cần quan tâm thêm tới một vài giả thiết của các tham số. Trong ví dụ này, một giả thiết hợp lý là xác suất nhận được mặt ngửa gần với 1/2.
Ước lượng hậu nghiệm cực đại (maximum a posteriori, MAP) ra đời nhằm giải quyết vấn đề này. Trong MAP, ta giới thiệu một giả thiết biết trước của tham số θ. Từ giả thiết này, ta có thể suy ra các khoảng giá trị và phân bố của tham số.
Khác với MLE, trong MAP, ta đánh giá tham số như một xác suất có điều kiện của dữ liệu:
θ = argmax θ
p(θ|x1, . . . , xN ) | {z } hậu nghiệm
. (4.32)
Biểu thức p(θ|x1, . . . , xN ) còn được gọi là xác suất hậu nghiệm của θ. Chính vì vậy, việc ước lượng θ theo (4.32) được gọi là ước lượng hậu nghiệm cực đại.
Thông thường, hàm tối ưu trong (4.32) khó xác định dạng một cách trực tiếp. Chúng ta thường biết điều ngược lại, tức nếu biết tham số, ta có thể tính được hàm mật độ xác suất của dữ liệu. Vì vậy, để giải bài toán MAP, quy tắc Bayes thường được sử dụng. Bài toán MAP được biến đổi thành
Machine Learning cơ bản 73
Chương 4. Ước lượng tham số mô hình
hàm hợp lý
z }| {
tiên nghiệm z}|{
(4.33)
θ = argmax
p(θ|x1, . . . , xN ) = argmax
p(x1, . . . , xN |θ)
p(θ)
θ
p(x1, . . . , xN )
θ
= argmax
[p(x1, . . . , xN |θ)p(θ)] (4.34)
θ
= argmax θ
"YN i=1
p(xi|θ)p(θ)
#
. (4.35)
Đẳng thức (4.33) xảy ra theo quy tắc Bayes. Đẳng thức (4.34) xảy ra vì mẫu số của (4.33) không phụ thuộc vào tham số θ. Đẳng thức (4.35) xảy ra nếu có giả thiết về sự độc lập giữa các xi.
Như vậy, điểm khác biệt lớn nhất giữa hai bài toán tối ưu MLE và MAP là việc hàm mục tiêu của MAP có thêm p(θ), tức phân phối của θ. Phân phối này chính là những thông tin biết trước về θ và được gọi là tiên nghiệm (prior). Ta kết luận rằng hậu nghiệm tỉ lệ thuận với tích của hàm hợp lý và tiên nghiệm.
Để chọn tiên nghiệm chúng ta cùng làm quen với một khái niệm mới: tiên nghiệm liên hợp (conjugate prior).
4.3.2. Tiên nghiệm liên hợp
Nếu phân phối hậu nghiệm p(θ|x1, . . . , xN ) có cùng dạng với phân phối tiên nghiệm p(θ), hai phân phối này được gọi là cặp phân phối liên hợp (conju gate distribution), và p(θ) được gọi là tiên nghiệm liên hợp của hàm hợp lý p(x1, . . . , xN |θ). Ta sẽ thấy rằng bài toán MAP và MLE có cấu trúc giống nhau.
Một vài cặp phân phối liên hợp8:
• Nếu hàm hợp lý và tiên nghiệm cho vector kỳ vọng là các phân phối chuẩn thì phân phối hậu nghiệm cũng là một phân phối chuẩn. Ta nói rằng phân phối chuẩn liên hợp với chính nó, hay còn gọi là tự liên hợp (self-conjugate).
• Nếu hàm hợp lý là một phân phối chuẩn và tiên nghiệm cho phương sai là một phân phối gamma, phân phối hậu nghiệm cũng là một phân phối chuẩn. Ta nói rằng phân phối gamma là tiên nghiệm liên hợp cho phương sai của phân phối chuẩn.
• Phân phối beta là liên hợp của phân phối Bernoulli.
• Phân phối Dirichlet là liên hợp của phân phối categorical.
8 Đọc thêm: Conjugate prior – Wikipedia (https://goo.gl/E2SHbD).
74 Machine Learning cơ bản
Chương 4. Ước lượng tham số mô hình
4.3.3. Siêu tham số
Xét phân phối Bernoulli với hàm mật độ xác suất
p(x|λ) = λx(1 − λ)1−x(4.36)
và liên hợp của nó, phân phối beta, có hàm phân mật độ xác suất p(λ) = Γ(α + β)
Γ(α)Γ(β)λα−1(1 − λ)β−1. (4.37)
Bỏ qua thành phần hằng số chỉ mang mục đích chuẩn hoá, ta có thể nhận thấy rằng phần còn lại của phân phối beta có cùng dạng với phân phối Bernoulli. Cụ thể, nếu sử dụng phân phối beta làm tiên nghiệm cho tham số λ, và bỏ qua phần thừa số hằng số, hậu nghiệm sẽ có dạng
p(λ|x) ∝ p(x|λ)p(λ)
∝ λx+α−1(1 − λ)1−x+β−1(4.38)
Nhận thấy (4.38) vẫn có dạng của một phân phối Bernoulli. Vì vậy, phân phối beta là một tiên nghiệm liên hợp của phân phối Bernoulli.
Trong ví dụ này, tham số λ phụ thuộc vào hai tham số khác là α và β. Để tránh nhầm lẫn, hai tham số (α, β) được gọi là các siêu tham số (hyperparameter).
Quay trở lại ví dụ về bài toán tung đồng xu N lần có n lần nhận được mặt ngửa và m = N − n lần nhận được mặt xấp. Nếu sử dụng MLE, ta nhận được ước lượng λ = n/M. Nếu sử dụng MAP với tiên nghiệm là một beta[α, β] thì kết quả sẽ thay đổi thế nào?
Bài toán tối ưu MAP
λ = argmax
[p(x1, . . . , xN |λ)p(λ)]
λ
= argmax λ
" YN i=1
λxi(1 − λ)1−xi
!
λα−1(1 − λ)β−1
#
h
= argmax
λPNi=1 xi+α−1(1 − λ)N−PNi=1 xi+β−1i
λ
= argmax λ
λn+α−1(1 − λ)m+β−1 (4.39)
Bài toán tối ưu (4.39) chính là bài toán tối ưu (4.9) với tham số thay đổi một chút. Tương tự như (4.10), nghiệm của (4.39) là
λ =n + α − 1
n + m + α + β − 2=n + α − 1
N + α + β − 2(4.40)
Machine Learning cơ bản 75
Chương 4. Ước lượng tham số mô hình
(2, 2)
(0.5, 0.5)
(10, 10)
(0.1, 0.1)
p(λ)
(1, 1)
0.00 0.25 0.50 0.75 1.00 λ
Hình 4.1. Đồ thị hàm mật độ xác suất của phân phối beta khi α = β và nhận các giá trị khác nhau. Khi cả hai giá trị này lớn, xác suất để λ gần 0.5 sẽ cao hơn.
Việc chọn tiên nghiệm phù hợp đã khiến cho việc tối ưu bài toán MAP được thuận lợi.
Việc còn lại là chọn cặp siêu tham số α và β.
Chúng ta cùng xem lại dạng của phân phối beta và thấy rằng khi α = β > 1, hàm mật độ xác suất của phân phối beta đối xứng qua điểm 0.5 và đạt giá trị cao nhất tại 0.5. Xét Hình 4.1, ta thấy rằng khi α = β > 1, mật độ xác suất xung quanh điểm 0.5 nhận giá trị cao, điều này chứng tỏ λ có xu hướng gần 0.5.
Nếu chọn α = β = 1, ta nhận được phân phối đều vì đồ thị hàm mật độ xác suất là một đường thẳng. Lúc này, xác suất của λ tại mọi vị trí trong khoảng [0, 1] là như nhau. Thực chất, nếu ta thay α = β = 1 vào (4.40) ta sẽ thu được λ = n/N, đây chính là ước lượng thu được bằng MLE. MLE là một trường hợp đặc biệt của MAP khi prior là một phân phối đều.
Nếu ta chọn α = β = 2, ta sẽ thu được: λ =n + 1
N + 2. Chẳng hạn khi N = 5, n = 1
như trong ví dụ. MLE cho kết quả λ = 1/5, MAP sẽ cho kết quả λ = 2/7, gần với 1/2 hơn.
Nếu chọn α = β = 10 ta sẽ có λ = (1 + 9)/(5 + 18) = 10/23. Ta thấy rằng khi α = β và càng lớn thì ta sẽ thu được λ càng gần 1/2. Điều này có thể dễ nhận thấy vì prior nhận giá trị rất cao tại 0.5 khi các siêu tham số α = β lớn.
76 Machine Learning cơ bản
Chương 4. Ước lượng tham số mô hình
4.4. Tóm tắt
• Khi sử dụng các mô hình thống kê machine learning, chúng ta thường xuyên phải ước lượng các tham số của mô hình θ. Có hai phương pháp phổ biến được sử dụng để ước lượng θ là ước lượng hợp lý cực đại (MLE) và ước lượng hậu nghiệ cực đại (MAP).
• Với MLE, việc xác định tham số θ được thực hiện bằng cách đi tìm các tham số sao cho xác suất của tập huấn luyện, được xác định bằng hàm hợp lý, là lớn nhất:
θ = argmax θ
p(x1, . . . , xN |θ). (4.41)
• Để giải bài toán tối ưu này, giả thiết các dữ liệu xi độc lập thường được sử dụng. Và bài toán MLE trở thành
θ = argmax θ
YN i=1
p(xi|θ). (4.42)
• Với MAP, các tham số được đánh giá bằng cách tối đa hậu nghiệm:
θ = argmax θ
p(θ|x1, . . . , xN ) (4.43)
• Quy tắc Bayes và giả thiết về sự độc lập của dữ liệu thường được sử dụng:
θ = argmax θ
"YN i=1
p(xi|θ)p(θ)
#
(4.44)
Hàm mục tiêu ở đây chính là tích của hàm hợp lý và tiên nghiệm.
• Tiên nghiệm thường được chọn dựa trên các thông tin biết trước của tham số, và phân phối được chọn thường là các phân phối liên hợp của likelihood.
• MAP có thể được coi như một phương pháp giúp tránh thiên lệch khi có ít dữ liệu huấn luyện.
Machine Learning cơ bản 77
Phần II
Tổng quan
Chương 5. Các khái niệm cơ bản
Chương 5
Các khái niệm cơ bản
5.1. Nhiệm vụ, kinh nghiệm, phép đánh giá
Một thuật toán machine learning là một thuật toán có khả năng học tập từ dữ liệu. Vậy thực sự “học tập” có nghĩa như thế nào? Theo Mitchell [M+97], “A computer program is said to learn from experience E with respect to some tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.”
Tạm dịch:
Một chương trình máy tính được gọi là “học tập” từ kinh nghiệm E để hoàn thành nhiệm vụ T với hiệu quả được đo bằng phép đánh giá P, nếu hiệu quả của nó khi thực hiện nhiệm vụ T, khi được đánh giá bởi P, cải thiện theo kinh nghiệm E.
Lấy ví dụ về một chương trình máy tính có khả năng tự chơi cờ vây. Chương trình này tự học từ các ván cờ đã chơi trước đó của con người để tính toán ra các chiến thuật hợp lý nhất. Mục đích của việc học này là tạo ra một chương trình có khả năng giành phần thắng cao. Chương trình này cũng có thể tự cải thiện khả năng của mình bằng cách chơi hàng triệu ván cờ với chính nó. Trong ví dụ này, chương trình máy tính có nhiệm vụ chơi cờ vây thông qua kinh nghiệm là các ván cờ đã chơi với chính nó và của con người. Phép đánh giá ở đây chính là khả năng giành chiến thắng của chương trình.
Để xây dựng một chương trình máy tính có khả năng học, ta cần xác định rõ ba yếu tố: nhiệm vụ, phép đánh giá, và nguồn dữ liệu huấn luyện. Bạn đọc sẽ hiểu rõ hơn về các yếu tố này qua các mục còn lại của chương.
80 Machine Learning cơ bản