Nền tảng học máy

0Ký hiệu và quy ước#

Để đọc giáo trình này, người học cần biết đạo hàm của hàm một biến, phép nhân ma trận và đọc được mã Python dùng NumPy. Kiến thức đại số tuyến tính và xác suất ở mức cần thiết được nhắc lại trong Chương 2 và Chương 3, nên không đòi hỏi học trước.

0.1Bảng ký hiệu#

Chữ $\lambda$ được dùng cho hai việc: hệ số regularization (Chương 9) và trị riêng (Chương 2, Chương 14). Hai cách dùng không xuất hiện trong cùng một công thức, trừ Mục 9.3 là nơi trị riêng được viết qua giá trị suy biến $d_i$ để tránh nhầm.

0.2Quy ước thuật ngữ#

Giáo trình dùng thuật ngữ theo cách phổ biến trong cộng đồng học máy tiếng Việt, có tham khảo bản dịch tiếng Việt các cheatsheet CS229 và CS230 của Đại học Stanford. Thuật ngữ nào đã có tên tiếng Việt thông dụng thì dùng tiếng Việt; thuật ngữ nào người làm nghề vẫn gọi bằng tiếng Anh thì giữ nguyên tiếng Anh.

Chữ bias trong tiếng Anh có hai nghĩa khác nhau. Nghĩa thứ nhất là sai lệch có hệ thống của một ước lượng so với giá trị thật; giáo trình gọi là độ chệch, theo cách gọi "ước lượng không chệch" quen thuộc của thống kê. Nghĩa thứ hai là tham số cộng thêm $b$ trong $w^\top x + b$; giáo trình gọi là hệ số chặn. Bảng đối chiếu đầy đủ nằm ở trang Từ điển thuật ngữ.

0.3Quy ước về chiều và cách viết số#

Ma trận dữ liệu $X$ có $n$ hàng ứng với $n$ điểm dữ liệu và $d$ cột ứng với $d$ đặc trưng, đúng như X.shape == (n, d) trong NumPy. Trong công thức, $x$ là vector cột nên tích với trọng số viết là $w^\top x$; trong mã, cả tập dữ liệu nhân với trọng số viết là X @ w. Hai cách viết chỉ khác nhau một phép chuyển vị.

Phần chữ dùng dấu phẩy thập phân theo lối Việt Nam (0,15). Phần mã và kết quả in ra từ script giữ dấu chấm như Python (0.15).

1Tổng quan về học máy#

Có rất nhiều thuật toán học máy mang tên khác nhau, và người mới dễ có cảm giác phải học thuộc từng cái một. Thực ra phần lớn chúng được ghép từ cùng ba thành phần, và khi đã hiểu ba thành phần ấy thì học một thuật toán mới chỉ còn là trả lời ba câu hỏi. Trước khi đi vào từng thuật toán ở các chương sau, ta dựng khung đó, bắt đầu từ câu hỏi học máy là gì.

1.1Khái niệm học máy#

Một định nghĩa hay được trích dẫn là của Tom Mitchell (1997): một chương trình được gọi là học từ kinh nghiệm $E$ đối với một lớp nhiệm vụ $T$ và một thước đo hiệu năng $P$, nếu hiệu năng của nó trên các nhiệm vụ trong $T$, đo bằng $P$, tăng lên theo kinh nghiệm $E$. Với bài toán lọc thư rác, $T$ là việc gắn nhãn "rác" hoặc "không rác" cho một thư, $P$ là tỉ lệ thư được gắn nhãn đúng, còn $E$ là tập thư đã được người dùng đánh dấu.

Định nghĩa trên đúng nhưng chưa nói cách làm. Để thấy cách làm, ta nhìn vào cấu tạo của các thuật toán. Mỗi thuật toán học có giám sát đều gồm ba thành phần, như Hình 1 minh hoạ.

Thành phần thứ nhất là mô hình, tập các hàm $f_\theta$ mà ta cho phép thuật toán chọn. Hồi quy tuyến tính chỉ cho phép các hàm tuyến tính, chính xác hơn là affine, của đầu vào; cây quyết định cho phép các hàm hằng trên từng vùng; mạng nơ-ron cho phép hợp của nhiều phép biến đổi tuyến tính xen với các hàm phi tuyến. Thành phần thứ hai là hàm mất mát, đo mức sai của một dự đoán so với nhãn thật. Đây là nơi ta nói ra điều mình thực sự muốn: sai lệch lớn có bị phạt nặng hơn không, đoán sai lớp dương có đắt hơn đoán sai lớp âm không. Thành phần thứ ba là thuật toán tối ưu, cách tìm tham số $\theta$ làm tổng mất mát trên dữ liệu huấn luyện nhỏ nhất. Có bài toán giải được bằng công thức, có bài toán phải lặp như gradient descent.

Khung ba thành phần biến việc học một thuật toán mới thành việc trả lời ba câu hỏi: mô hình là họ hàm nào, mất mát là gì, tối ưu bằng cách nào. Với bài toán định giá căn hộ theo diện tích ở Chương 4, câu trả lời là: mô hình là các đường thẳng $f(x) = w_0 + w_1 x$, mất mát là bình phương độ lệch giữa giá dự đoán và giá thật, còn tối ưu bằng một công thức đóng, hoặc bằng gradient descent ở Chương 5. Nó cũng cho thấy nhiều thuật toán mang tên khác nhau thực ra rất gần nhau. Chương 6 sẽ chỉ ra rằng perceptron, hồi quy logistic và SVM dùng chung một mô hình là hàm tuyến tính và chung một cách tối ưu là gradient descent; chúng chỉ khác nhau ở hàm mất mát.

Định nghĩa 1.1 (Bài toán học có giám sát)

Cho tập huấn luyện $\mathcal{D} = \{(x_i, y_i)\}_{i=1}^{n}$, một họ hàm $\{f_\theta\}$ và một hàm mất mát $\ell$. Bài toán học có giám sát là tìm

$$\hat\theta = \arg\min_\theta \; \frac{1}{n}\sum_{i=1}^{n} \ell\big(y_i, f_\theta(x_i)\big),$$

với mục đích cuối cùng là $f_{\hat\theta}$ dự đoán tốt trên những điểm dữ liệu chưa gặp khi huấn luyện.

Vế cuối của định nghĩa là chỗ tạo ra toàn bộ độ khó của học máy. Tối thiểu hoá mất mát trên dữ liệu huấn luyện chỉ là phương tiện; mục tiêu thật là khả năng tổng quát hoá (generalization) sang dữ liệu mới. Một mô hình ghi nhớ nguyên văn tập huấn luyện có mất mát huấn luyện bằng 0 nhưng có thể vô dụng trên dữ liệu mới. Hiện tượng này gọi là overfitting và được bàn kỹ ở Chương 9.

1.2Các dạng bài toán học máy#

Cách phân loại thông dụng nhất dựa vào việc dữ liệu có nhãn hay không. Trong học có giám sát (supervised learning), mỗi điểm dữ liệu $x_i$ đi kèm một nhãn $y_i$. Nếu nhãn là số thực, như giá nhà hay nhiệt độ ngày mai, bài toán là hồi quy; nếu nhãn thuộc một tập hữu hạn các lớp, như thư rác hay không, ảnh chứa chữ số nào, bài toán là phân loại. Trong học không giám sát (unsupervised learning), ta chỉ có $x_i$ mà không có nhãn, và mục tiêu là tìm cấu trúc trong dữ liệu: gom các điểm giống nhau thành cụm, tìm vài hướng chứa phần lớn thông tin, hay ước lượng mật độ phân phối. Dạng thứ ba là học tăng cường (reinforcement learning), trong đó một tác tử tương tác với môi trường và nhận tín hiệu thưởng thay vì nhận nhãn đúng cho từng đầu vào; giáo trình Biểu diễn & Căn chỉnh trình bày dạng này.

Bảng sau xếp các chương của giáo trình theo cách phân loại trên.

Ranh giới giữa hai cột không cứng. Trong hệ thống gợi ý ở Chương 16, các ô đánh giá đã biết đóng vai trò nhãn, nhưng phần lớn ma trận là ô trống cần điền, nên bài toán nằm giữa hai loại. Ngoài ra còn các dạng lai như học bán giám sát, khi chỉ một phần nhỏ dữ liệu có nhãn, và học tự giám sát, khi nhãn được tạo ra từ chính dữ liệu, chẳng hạn đoán từ tiếp theo trong câu. Học tự giám sát là cách các mô hình ngôn ngữ lớn được huấn luyện, và được trình bày trong giáo trình Biểu diễn & Căn chỉnh.

Ba ví dụ nhỏ đi suốt giáo trình, mỗi ví dụ ứng với một dạng bài toán. Bốn căn hộ với diện tích và giá là bài toán hồi quy, xuất hiện từ Chương 2 tới Chương 11. Sáu sinh viên với số giờ ôn thi và kết quả đỗ hay trượt là bài toán phân loại, từ Chương 6 tới Chương 13. Bốn cửa hàng cần đặt hai kho hàng là bài toán phân cụm ở Chương 15. Các ví dụ đủ nhỏ để tính tay, nên mỗi công thức được kiểm tra trên chúng trước khi đi tới thí nghiệm trên dữ liệu lớn hơn.

1.3Các yếu tố cần xét trước khi chọn thuật toán#

Trước khi chọn một mô hình cụ thể, có ba câu hỏi về dữ liệu và mục tiêu ảnh hưởng tới lựa chọn nhiều hơn bản thân thuật toán.

Câu hỏi đầu tiên là số điểm dữ liệu so với số đặc trưng. Tỉ lệ $n/d$ quyết định mô hình được phép linh hoạt tới mức nào. Khi $n$ lớn hơn $d$ rất nhiều, ta có thể dùng mô hình nhiều tham số mà ít lo overfitting. Khi $n$ xấp xỉ hoặc nhỏ hơn $d$, regularization trở thành bắt buộc (Chương 9), và một số phương pháp không dùng được nữa: Mục 4.3 cho thấy phương trình chuẩn của hồi quy tuyến tính không có nghiệm duy nhất khi các cột của $X$ phụ thuộc tuyến tính, điều chắc chắn xảy ra khi $d > n$.

Câu hỏi thứ hai là dữ liệu có cấu trúc gì. Ảnh có tính cục bộ, vì điểm ảnh gần nhau liên quan với nhau, và bất biến theo dịch chuyển, vì con mèo ở góc trái hay góc phải vẫn là con mèo. Văn bản và chuỗi thời gian có thứ tự. Dữ liệu dạng bảng, như bảng thông tin khách hàng, không có cấu trúc nào như vậy: đổi thứ tự các cột không làm thay đổi ý nghĩa. Mạng nơ-ron tích chập và Transformer mạnh vì khai thác được cấu trúc của ảnh và chuỗi. Trên dữ liệu dạng bảng, mô hình tuyến tính và các mô hình dựa trên cây quyết định thường cho kết quả tương đương hoặc tốt hơn mạng nơ-ron với chi phí thấp hơn nhiều.

Câu hỏi thứ ba là mục tiêu là dự đoán hay giải thích. Có bài toán chỉ cần dự đoán đúng, chẳng hạn xếp hạng quảng cáo. Có bài toán cần trả lời câu hỏi "đặc trưng này ảnh hưởng tới kết quả bao nhiêu", chẳng hạn đánh giá tác dụng của một chính sách. Hai mục tiêu có thể dẫn tới hai lựa chọn khác nhau. Mục 4.4 đo một trường hợp cụ thể: khi hai đặc trưng gần như trùng nhau, độ dao động của hệ số hồi quy tăng khoảng 25 lần trong khi độ dao động của dự đoán gần như không đổi. Nếu chỉ cần dự đoán thì hiện tượng này vô hại; nếu cần đọc ý nghĩa của hệ số thì các hệ số đó không đáng tin.

1.4Vị trí của giáo trình trong lộ trình#

Giáo trình này là chặng đầu của một lộ trình sáu giáo trình, xây dựng theo roadmap AI Engineer của roadmap.sh và bổ sung phần kiến thức nền mà roadmap đó giả định người học đã có.

Kiến thức của giáo trình này được dùng lại ở nhiều chỗ trong các giáo trình sau. Gradient descent ở Chương 5 là nền cho Chương 5 của Học sâu, nơi thuật toán được mở rộng thành momentum, Adam và lan truyền ngược qua nhiều lớp. Hồi quy logistic ở Chương 6 là một mạng nơ-ron một lớp, và Chương 4 của Học sâu bắt đầu bằng việc chồng nhiều lớp như vậy lên nhau. Regularization ở Chương 9 và ước lượng MAP ở Chương 10 giải thích nguồn gốc của weight decay, kỹ thuật được dùng mặc định khi huấn luyện mạng sâu (Chương 5 của Học sâu). Các độ đo đánh giá ở Chương 8 là nền cho việc đánh giá mô hình trong sản xuất ở Chương 6 của MLOps. Tích vô hướng, cosine và PCA ở Chương 2 và Chương 14 là công cụ để hiểu embedding và tìm kiếm vector trong giáo trình Biểu diễn & Căn chỉnh và Ứng dụng LLM. Còn SVD ở Mục 2.6 là công cụ để đọc Chương 11 của Quantization, nơi các phương pháp như GPTQ dựa trên phân rã ma trận.

1.5Quy trình giải một bài toán học máy#

Các chương sau đi sâu vào từng thuật toán. Mục này mô tả quy trình bao quanh thuật toán, vì trên thực tế phần lớn lỗi nằm ở quy trình chứ không nằm ở thuật toán.

Mọi thứ bắt đầu từ việc xác định bài toán và thước đo: viết rõ đầu vào, đầu ra và thước đo thành công trước khi đụng tới dữ liệu. Thước đo phải phản ánh chi phí thật. Với bài toán phát hiện gian lận, bỏ sót một ca gian lận thường đắt hơn nhiều so với báo động nhầm, nên độ chính xác không phải thước đo phù hợp (Mục 8.1).

Bước tiếp theo là thu thập và chia dữ liệu. Dữ liệu được chia thành tập huấn luyện, tập xác thực và tập kiểm tra ngay từ đầu. Tập huấn luyện dùng để học tham số, tập xác thực dùng để chọn siêu tham số và so sánh mô hình, còn tập kiểm tra chỉ dùng một lần ở cuối để báo cáo kết quả. Cách chia phải khớp với cách mô hình sẽ được dùng, chẳng hạn dữ liệu có yếu tố thời gian thì chia theo thời gian (Mục 8.5).

Trước khi thử mô hình phức tạp, nên dựng một mô hình cơ sở đơn giản nhất có thể: đoán giá trị trung bình, đoán lớp phổ biến nhất, hoặc một mô hình tuyến tính. Mô hình cơ sở cho biết một mô hình phức tạp hơn có thật sự mang lại gì hay không. Sau đó mới tới xây dựng đặc trưng và huấn luyện: chuẩn hoá đặc trưng, mã hoá biến hạng mục, xử lý giá trị thiếu. Mọi phép biến đổi có tham số, như trung bình và độ lệch chuẩn khi chuẩn hoá, chỉ được ước lượng trên tập huấn luyện.

Mô hình được đánh giá và điều chỉnh trên tập xác thực hoặc bằng cross-validation (Mục 9.5) để chọn siêu tham số. Khi đánh giá, nên xem lỗi theo từng nhóm dữ liệu chứ không chỉ một con số tổng. Cuối cùng, mô hình được đo trên tập kiểm tra đúng một lần rồi mới triển khai. Sau khi triển khai, mô hình cần được giám sát vì phân phối dữ liệu thay đổi theo thời gian; giáo trình MLOps trình bày phần này.

Lưu ý

Nếu tập kiểm tra được dùng nhiều lần để chọn mô hình, nó trở thành một tập xác thực thứ hai và con số báo cáo sẽ lạc quan hơn thực tế. Đây là lỗi phổ biến nhất khi so sánh mô hình, và Mục 9.5 nói cách tránh.

1.6Tóm tắt#

Mỗi thuật toán học có giám sát gồm ba thành phần: mô hình là họ hàm được phép chọn, hàm mất mát đo mức sai, và thuật toán tối ưu tìm tham số. Mục tiêu thật của học máy là tổng quát hoá sang dữ liệu chưa gặp, không phải tối thiểu hoá mất mát trên dữ liệu huấn luyện. Bài toán học máy chia theo việc có nhãn hay không thành học có giám sát, gồm hồi quy và phân loại, học không giám sát, và học tăng cường; bốn căn hộ, sáu sinh viên và bốn cửa hàng là ba ví dụ của ba dạng đó, đi cùng các chương sau. Trước khi chọn thuật toán cần xét tỉ lệ số điểm trên số đặc trưng, cấu trúc của dữ liệu, và mục tiêu là dự đoán hay giải thích. Quy trình bao quanh thuật toán, từ chọn thước đo, chia dữ liệu tới dùng tập kiểm tra đúng một lần, là nơi xảy ra phần lớn lỗi.

Để làm việc với cả ba thành phần, ta cần một ngôn ngữ chung: dữ liệu là ma trận, mô hình tuyến tính là phép nhân ma trận với vector, và tối ưu cần đạo hàm theo vector. Chương 2 nhắc lại phần đại số tuyến tính cần cho ngôn ngữ đó.

2Đại số tuyến tính#

Mọi thuật toán trong giáo trình đều viết bằng ngôn ngữ vector và ma trận, và nhiều kết luận quan trọng ở các chương sau thực ra là hệ quả của vài định lý đại số tuyến tính. Chẳng hạn, việc hồi quy tuyến tính có nghiệm duy nhất hay không phụ thuộc vào hạng của ma trận dữ liệu, còn tốc độ của gradient descent phụ thuộc vào tỉ số giữa trị riêng lớn nhất và nhỏ nhất. Ở đây ta nhắc lại những khái niệm đó, mỗi khái niệm kèm lý do nó cần thiết. Các khái niệm được minh hoạ trên cùng một ma trận dữ liệu nhỏ, diện tích của bốn căn hộ, ma trận mà Chương 4 sẽ dùng để định giá căn hộ. Người đã vững đại số tuyến tính có thể đọc lướt bảng ở Mục 2.1 rồi chuyển sang Chương 3.

2.1Vector, ma trận và hạng#

Một vector $x \in \mathbb{R}^d$ là một danh sách $d$ số thực, quy ước viết thành cột. Trong học máy, mỗi điểm dữ liệu là một vector: một căn nhà được mô tả bằng diện tích, số phòng và khoảng cách tới trung tâm là một vector ba chiều. Một ma trận $X \in \mathbb{R}^{n \times d}$ là một bảng $n$ hàng, $d$ cột; ma trận dữ liệu xếp $n$ điểm dữ liệu thành $n$ hàng.

Tích ma trận với vector có hai cách đọc, và cả hai đều được dùng:

$$Xw = \begin{pmatrix} x_1^\top w \\ \vdots \\ x_n^\top w \end{pmatrix} = w_1 X_{:,1} + w_2 X_{:,2} + \dots + w_d X_{:,d}.$$

Đọc theo hàng, $Xw$ là vector chứa dự đoán của mô hình tuyến tính cho từng điểm dữ liệu. Đọc theo cột, $Xw$ là một tổ hợp tuyến tính của các cột của $X$. Tập mọi tổ hợp tuyến tính như vậy gọi là không gian cột của $X$, và hồi quy tuyến tính chính là tìm điểm trong không gian cột gần $y$ nhất (Chương 4).

Bốn căn hộ có diện tích 40, 60, 80 và 100 m² cho thấy cả hai cách đọc. Thêm một cột hằng 1 cho hệ số chặn, ma trận dữ liệu và một vector tham số là

$$X = \begin{pmatrix}1&40\\1&60\\1&80\\1&100\end{pmatrix}, \qquad w = \begin{pmatrix}0{,}57\\0{,}024\end{pmatrix}.$$

Đọc theo hàng, $Xw = (1{,}53;\ 2{,}01;\ 2{,}49;\ 2{,}97)$ là giá dự đoán, tính bằng tỉ đồng, của bốn căn: căn 40 m² được đoán $0{,}57 + 0{,}024 \cdot 40 = 1{,}53$ tỉ. Đọc theo cột, cùng vector đó là 0,57 lần cột hằng cộng 0,024 lần cột diện tích. Chương 4 sẽ chỉ ra vì sao $w$ này là lựa chọn tốt nhất cho bốn căn hộ.

Định nghĩa 2.1 (Hạng)

Hạng của ma trận $X$, ký hiệu $\operatorname{rank}(X)$, là số cột độc lập tuyến tính lớn nhất của $X$ (bằng số hàng độc lập tuyến tính lớn nhất). Ma trận $X \in \mathbb{R}^{n \times d}$ gọi là đủ hạng cột nếu $\operatorname{rank}(X) = d$, tức không cột nào là tổ hợp tuyến tính của các cột còn lại.

Vì hạng không vượt quá số hàng, một ma trận có nhiều cột hơn hàng ($d > n$) không thể đủ hạng cột. Đó chính là cơ sở toán học của nhận xét ở Mục 1.3 rằng dữ liệu có nhiều đặc trưng hơn số điểm cần được xử lý đặc biệt. Ma trận $X$ của bốn căn hộ có hai cột không tỉ lệ với nhau, nên có hạng 2 và đủ hạng cột. Thêm một cột ghi diện tích bằng dm², tức 100 lần cột diện tích, thì ma trận có ba cột nhưng hạng vẫn là 2 và không còn đủ hạng cột; Mục 4.3 xét đúng tình huống đặc trưng trùng lặp này.

Bảng sau liệt kê các khái niệm của chương và nơi chúng được dùng.

2.2Tích vô hướng và siêu phẳng#

Định nghĩa 2.2 (Tích vô hướng)

Tích vô hướng của hai vector $w, x \in \mathbb{R}^d$ là

$$w^\top x = \sum_{j=1}^{d} w_j x_j = \|w\|_2\,\|x\|_2\cos\vartheta,$$

trong đó $\vartheta$ là góc giữa hai vector.

Hai cách viết ứng với hai cách hiểu. Theo cách đại số, $w^\top x$ là tổng có trọng số của các đặc trưng: đặc trưng nào có trọng số lớn thì đóng góp nhiều vào kết quả. Theo cách hình học, $w^\top x$ bằng độ dài hình chiếu của $x$ lên hướng của $w$ nhân với độ dài của $w$. Khi hai vector cùng hướng, tích vô hướng lớn và dương; khi vuông góc, nó bằng 0; khi ngược hướng, nó âm. Chia cho tích hai độ dài ta được $\cos\vartheta$, gọi là độ tương đồng cosine, thước đo dùng khắp nơi khi so sánh embedding.

Cách hiểu hình học cho biết tập nghiệm của phương trình $w^\top x + b = 0$ là gì. Đó là tập các điểm mà hình chiếu lên hướng $w$ có cùng một giá trị, tức một siêu phẳng vuông góc với $w$. Trong không gian hai chiều, siêu phẳng là một đường thẳng; trong ba chiều, là một mặt phẳng. Vector $w$ gọi là vector pháp tuyến của siêu phẳng. Mọi bộ phân loại tuyến tính ở Chương 6 và Chương 13 đều chia không gian bằng một siêu phẳng như vậy: phía $w^\top x + b > 0$ là một lớp, phía còn lại là lớp kia.

Định lý 2.1 (Khoảng cách từ một điểm tới siêu phẳng)

Khoảng cách từ điểm $x_0$ tới siêu phẳng $w^\top x + b = 0$ là

$$\operatorname{dist}(x_0) = \frac{|w^\top x_0 + b|}{\|w\|_2}.$$

Chứng minh

Gọi $x_p$ là hình chiếu vuông góc của $x_0$ lên siêu phẳng. Vì $x_0 - x_p$ vuông góc với siêu phẳng nên nó cùng phương với $w$: $x_0 - x_p = t\,w/\|w\|$ với $|t|$ là khoảng cách cần tìm. Nhân vô hướng hai vế với $w$ và dùng $w^\top x_p = -b$ ta được $w^\top x_0 + b = t\,\|w\|$, suy ra $|t| = |w^\top x_0 + b|/\|w\|$.

Ví dụ 2.1

Cho $w = (3, 4)$, $b = -5$ và điểm $x_0 = (2, 1)$. Ta có $w^\top x_0 + b = 6 + 4 - 5 = 5$ và $\|w\| = \sqrt{9 + 16} = 5$, nên khoảng cách từ $x_0$ tới đường thẳng $3x_1 + 4x_2 = 5$ bằng 1. Dấu của $w^\top x_0 + b$ là dương, nên $x_0$ nằm về phía mà $w$ chỉ tới.

Công thức khoảng cách xuất hiện lại ở Mục 13.2. Trong SVM, khoảng cách từ điểm dữ liệu gần nhất tới siêu phẳng tỉ lệ nghịch với $\|w\|$, nên cực đại khoảng cách đó tương đương với cực tiểu $\|w\|$.

2.3Chuẩn của vector#

Chuẩn là cách đo độ dài của một vector. Ba chuẩn hay gặp là

$$\|w\|_1 = \sum_j |w_j|, \qquad \|w\|_2 = \sqrt{\textstyle\sum_j w_j^2}, \qquad \|w\|_\infty = \max_j |w_j|.$$

Chuẩn $\ell_2$ là độ dài Euclid thông thường. Chuẩn $\ell_1$ là tổng trị tuyệt đối, còn gọi là khoảng cách Manhattan khi dùng để đo khoảng cách giữa hai điểm, vì giống cách đi theo các khối nhà vuông góc. Chuẩn $\ell_\infty$ là thành phần có trị tuyệt đối lớn nhất. Chẳng hạn với $w = (3, -4, 0)$: $\|w\|_1 = 7$, $\|w\|_2 = 5$, $\|w\|_\infty = 4$.

Cách dễ nhất để thấy khác biệt giữa các chuẩn là vẽ quả cầu đơn vị $\{w : \|w\| \le 1\}$ trong hai chiều. Với $\ell_2$ đó là hình tròn. Với $\ell_1$ đó là hình vuông xoay 45 độ, có bốn đỉnh nằm trên các trục toạ độ. Với $\ell_\infty$ đó là hình vuông có cạnh song song với các trục.

Nghe như ba cách đo cùng một thứ, nhưng khi dùng làm thành phần regularization, chọn $\ell_1$ hay $\ell_2$ cho ra hai thuật toán có hành vi khác nhau về bản chất. Mục 9.4 đo được rằng phạt $\ell_2$ (ridge) không bao giờ đưa một hệ số về đúng 0, còn phạt $\ell_1$ (lasso) thì có: ở $\lambda = 100$, lasso đưa đúng 9 trong 12 hệ số về 0, trùng với số hệ số bằng 0 của mô hình sinh ra dữ liệu. Về hình học, các đỉnh nhọn của quả cầu $\ell_1$ nằm trên trục toạ độ và nghiệm tối ưu hay rơi vào các đỉnh đó; về giải tích, hàm $|w|$ không khả vi tại 0. Mục 9.4 trình bày cả hai cách giải thích.

2.4Trị riêng và vector riêng#

Định nghĩa 2.3 (Trị riêng, vector riêng)

Cho ma trận vuông $A \in \mathbb{R}^{d \times d}$. Số $\lambda$ là một trị riêng và vector khác không $v$ là một vector riêng tương ứng nếu

$$A v = \lambda v.$$

Phép nhân với $A$ nói chung vừa xoay vừa kéo dãn một vector. Vector riêng là những hướng đặc biệt mà $A$ không xoay, chỉ kéo dãn với hệ số $\lambda$, hoặc lật ngược nếu $\lambda < 0$. Trong học máy, ma trận ta gặp nhiều nhất là ma trận hiệp phương sai và ma trận $X^\top X$, và cả hai đều đối xứng. Với ma trận đối xứng có một kết quả rất mạnh.

Định lý 2.2 (Định lý phổ)

Mọi ma trận đối xứng thực $A \in \mathbb{R}^{d\times d}$ có $d$ trị riêng thực $\lambda_1, \dots, \lambda_d$ và một hệ $d$ vector riêng trực chuẩn $v_1, \dots, v_d$. Viết $V = [v_1, \dots, v_d]$ và $\Lambda = \operatorname{diag}(\lambda_1, \dots, \lambda_d)$ thì

$$A = V \Lambda V^\top = \sum_{i=1}^{d} \lambda_i v_i v_i^\top.$$

Định lý phổ nói rằng một ma trận đối xứng chỉ làm một việc đơn giản: trong hệ toạ độ gồm các vector riêng, nó kéo dãn mỗi trục một hệ số $\lambda_i$. Đây là nền tảng của PCA ở Chương 14, vì các thành phần chính chính là các vector riêng của ma trận hiệp phương sai.

Ví dụ 2.2

Ma trận $A = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$ có hai trị riêng $\lambda_1 = 3$ và $\lambda_2 = 1$, với vector riêng $v_1 = \tfrac{1}{\sqrt2}(1, 1)$ và $v_2 = \tfrac{1}{\sqrt2}(1, -1)$. Kiểm tra: $A v_1 = \tfrac{1}{\sqrt2}(3, 3) = 3 v_1$. Như vậy $A$ kéo dãn gấp ba theo đường chéo $x_1 = x_2$ và giữ nguyên theo đường chéo $x_1 = -x_2$.

Hai đẳng thức sau được dùng thường xuyên về sau:

$$\operatorname{tr}(A) = \sum_i \lambda_i, \qquad \det(A) = \prod_i \lambda_i.$$

Với ma trận ở Ví dụ 2.2, vết bằng $2 + 2 = 4 = 3 + 1$ và định thức bằng $4 - 1 = 3 = 3 \times 1$.

Định nghĩa 2.4 (Số điều kiện)

Với ma trận đối xứng xác định dương $A$, số điều kiện là tỉ số giữa trị riêng lớn nhất và nhỏ nhất:

$$\kappa(A) = \frac{\lambda_{\max}}{\lambda_{\min}} \ge 1.$$

Số điều kiện đo độ "dẹt" của ma trận: $\kappa = 1$ nghĩa là $A$ kéo dãn mọi hướng như nhau, còn $\kappa$ lớn nghĩa là có hướng bị kéo rất mạnh và có hướng gần như bị ép dẹt. Với bốn căn hộ, $X^\top X = \begin{pmatrix}4 & 280\\ 280 & 21\,600\end{pmatrix}$ có hai trị riêng khoảng 21 604 và 0,37, nên $\kappa \approx 58\,340$: theo một hướng, ma trận kéo dãn mạnh hơn hướng kia khoảng 58 nghìn lần. Đại lượng này quyết định tốc độ của gradient descent. Mục 5.3 đo được rằng số vòng lặp cần thiết tỉ lệ thuận với $\kappa$: khi $\kappa$ tăng từ 1 lên 10 000, số vòng lặp tăng từ 1 lên 92 104. Cũng ở mục đó, chỉ cần trừ trung bình rồi chia diện tích cho độ lệch chuẩn là $\kappa$ của bài toán bốn căn hộ giảm từ 58 340 xuống 1.

2.5Ma trận xác định dương#

Định nghĩa 2.5 (Ma trận xác định dương)

Ma trận đối xứng $A$ gọi là xác định dương nếu $z^\top A z > 0$ với mọi $z \neq 0$, và nửa xác định dương nếu $z^\top A z \ge 0$ với mọi $z$. Tương đương: mọi trị riêng của $A$ dương (tương ứng, không âm).

Sự tương đương với trị riêng suy ra ngay từ định lý phổ: viết $z$ trong hệ toạ độ vector riêng, $z = \sum_i c_i v_i$, thì $z^\top A z = \sum_i \lambda_i c_i^2$. Tổng này dương với mọi $z \ne 0$ khi và chỉ khi mọi $\lambda_i > 0$.

Các chương sau cần tới khái niệm này ở ba chỗ. Thứ nhất, hàm bậc hai $f(z) = \tfrac12 z^\top A z + c^\top z$ là hàm lồi khi và chỉ khi $A$ nửa xác định dương (Chương 11), và khi $A$ xác định dương thì $f$ có đúng một điểm cực tiểu. Thứ hai, ma trận $X^\top X$ luôn nửa xác định dương, vì $z^\top X^\top X z = \|Xz\|_2^2 \ge 0$; nó xác định dương khi và chỉ khi $Xz \ne 0$ với mọi $z \ne 0$, tức khi $X$ đủ hạng cột. Đó chính là điều kiện để phương trình chuẩn của hồi quy tuyến tính có nghiệm duy nhất (Mục 4.3). Với bốn căn hộ, hai trị riêng 21 604 và 0,37 của $X^\top X$ đều dương, nên ma trận này xác định dương. Thứ ba, nếu $A$ nửa xác định dương và $\lambda > 0$ thì $A + \lambda I$ xác định dương, vì $z^\top (A + \lambda I) z = z^\top A z + \lambda\|z\|^2 > 0$ với mọi $z \ne 0$; các trị riêng của $A + \lambda I$ là $\lambda_i + \lambda$, đều lớn hơn hoặc bằng $\lambda$. Nhờ tính chất này, hồi quy ridge luôn có nghiệm duy nhất, kể cả khi hồi quy tuyến tính thông thường không có (Mục 9.2).

2.6Phân tích giá trị suy biến (SVD)#

Định lý phổ chỉ áp dụng cho ma trận vuông đối xứng. Ma trận dữ liệu $X$ thường chữ nhật, và công cụ tương ứng cho nó là SVD.

Định lý 2.3 (Phân tích giá trị suy biến)

Mọi ma trận $X \in \mathbb{R}^{n \times d}$ viết được dưới dạng

$$X = U D V^\top,$$

trong đó $U \in \mathbb{R}^{n \times n}$ và $V \in \mathbb{R}^{d \times d}$ là ma trận trực giao, còn $D \in \mathbb{R}^{n \times d}$ có các phần tử trên đường chéo $d_1 \ge d_2 \ge \dots \ge 0$ và bằng 0 ở mọi chỗ khác. Các số $d_i$ gọi là giá trị suy biến của $X$.

Về mặt hình học, SVD nói rằng mọi phép biến đổi tuyến tính đều gồm ba bước: xoay (nhân $V^\top$), kéo dãn theo các trục toạ độ (nhân $D$), rồi xoay lần nữa (nhân $U$). Các chương sau dùng ba hệ quả của nó.

Hệ quả thứ nhất là liên hệ với trị riêng. Ta có $X^\top X = V D^\top D\, V^\top$, nên các vector riêng của $X^\top X$ là các cột của $V$ và các trị riêng là $d_i^2$. Khi $X$ đã được trừ trung bình theo cột, ma trận hiệp phương sai mẫu là $X^\top X/(n-1)$, nên trị riêng của nó bằng $d_i^2/(n-1)$. Mục 14.2 kiểm chứng điều này bằng số: tính theo hai cách, kết quả lệch nhau $7{,}1 \times 10^{-15}$.

Hệ quả thứ hai là số điều kiện bị bình phương. Vì trị riêng của $X^\top X$ là bình phương giá trị suy biến của $X$, ta có $\kappa(X^\top X) = \kappa(X)^2$, trong đó $\kappa(X) = d_1/d_{\min}$. Nếu $\kappa(X) = 100$ thì $\kappa(X^\top X) = 10^4$. Với bốn căn hộ, hai giá trị suy biến của $X$ là khoảng 146,98 và 0,609, nên $\kappa(X) \approx 241{,}5$ và $\kappa(X^\top X) \approx 241{,}5^2 \approx 58\,340$, đúng số điều kiện ở Mục 2.4. Khi giải một hệ tuyến tính có số điều kiện $\kappa$ bằng số thực dấu phẩy động, ta có thể mất khoảng $\log_{10}\kappa$ chữ số có nghĩa, nên lập $X^\top X$ làm mất gấp đôi số chữ số so với làm việc trực tiếp trên $X$. Vì vậy các thư viện giải bài toán bình phương tối thiểu bằng phân tích QR hoặc SVD của $X$ thay vì dùng công thức $(X^\top X)^{-1}X^\top y$.

Hệ quả thứ ba là xấp xỉ hạng thấp tốt nhất. Giữ lại $k$ giá trị suy biến lớn nhất và đặt các giá trị còn lại bằng 0 cho ma trận hạng $k$ gần $X$ nhất theo chuẩn Frobenius; đây là định lý Eckart–Young, và Mục 14.3 kiểm chứng đẳng thức sai số của nó tới $10^{-13}$.

2.7Đạo hàm theo vector#

Hầu hết thuật toán học máy tìm tham số bằng cách cho gradient của hàm mất mát bằng 0 hoặc đi ngược hướng gradient. Vì vậy cần tính được đạo hàm của hàm nhiều biến.

Định nghĩa 2.6 (Gradient)

Với hàm $f: \mathbb{R}^d \to \mathbb{R}$, gradient của $f$ tại $w$ là vector các đạo hàm riêng

$$\nabla_w f = \Big(\frac{\partial f}{\partial w_1}, \dots, \frac{\partial f}{\partial w_d}\Big)^\top.$$

Ma trận các đạo hàm riêng cấp hai $\big[\partial^2 f / \partial w_j \partial w_k\big]$ gọi là ma trận Hessian, ký hiệu $\nabla^2 f$.

Bốn công thức trong bảng dưới đủ cho toàn bộ giáo trình.

Công thức cuối được dùng nhiều nhất, và suy ra được từ ba công thức đầu. Khai triển

$$\begin{aligned} \|y - Xw\|_2^2 &= (y - Xw)^\top(y - Xw) \\ &= y^\top y - 2\,(X^\top y)^\top w + w^\top (X^\top X)\, w. \end{aligned}$$

Số hạng đầu không phụ thuộc $w$ nên có gradient bằng 0. Số hạng thứ hai có dạng $a^\top w$ với $a = -2X^\top y$. Số hạng thứ ba có dạng $w^\top A w$ với $A = X^\top X$ đối xứng, nên gradient là $2X^\top X w$. Cộng lại, ta được

$$\nabla_w \|y - Xw\|_2^2 = -2X^\top y + 2X^\top X w = -2X^\top (y - Xw).$$

Cho gradient này bằng 0 ta được phương trình chuẩn của Chương 4. Với bốn căn hộ, giá thật là $y = (1{,}5;\ 2{,}1;\ 2{,}4;\ 3{,}0)$ tỉ, và với $w = (0{,}57;\ 0{,}024)$ ở Mục 2.1, phần dư $y - Xw$ là $(-0{,}03;\ 0{,}09;\ -0{,}09;\ 0{,}03)$. Thành phần thứ nhất của $X^\top(y - Xw)$ là tổng các phần dư, bằng 0; thành phần thứ hai là tổng có trọng số theo diện tích, $-1{,}2 + 5{,}4 - 7{,}2 + 3{,}0 = 0$. Gradient bằng 0, nên $w$ này là nghiệm, đúng như Chương 4 sẽ tìm ra. Ma trận Hessian của hàm này là $2X^\top X$, nửa xác định dương theo Mục 2.5, nên hàm lồi và mọi điểm có gradient bằng 0 đều là cực tiểu.

Lưu ý

Công thức gradient tự suy ra bằng tay rất dễ sai dấu hoặc thiếu hệ số 2. Cách kiểm tra đáng tin là so sánh với đạo hàm tính bằng sai phân hữu hạn. Mục 5.5 trình bày cách làm và cách chọn bước sai phân $\varepsilon$, trong đó $\varepsilon$ quá nhỏ lại cho kết quả kém hơn.

2.8Tóm tắt#

Ma trận dữ liệu xếp mỗi điểm thành một hàng, và tích $Xw$ vừa là vector dự đoán vừa là tổ hợp tuyến tính của các cột. Hạng của $X$ cho biết các cột có độc lập hay không, nên quyết định hồi quy tuyến tính có nghiệm duy nhất hay không. Tích vô hướng đo độ chiếu của vector này lên vector kia, và mặt $w^\top x + b = 0$ là một siêu phẳng với khoảng cách từ một điểm tới nó bằng $|w^\top x_0 + b|/\|w\|$. Chuẩn $\ell_1$ và $\ell_2$ khác nhau ở hình dạng quả cầu đơn vị, và khác biệt đó quyết định hành vi của lasso và ridge. Ma trận đối xứng chỉ kéo dãn các trục vector riêng của nó, số điều kiện đo độ dẹt của phép kéo dãn đó, và SVD mở rộng ý tưởng này cho ma trận chữ nhật. Cuối cùng, gradient của $\|y - Xw\|^2$ là $-2X^\top(y - Xw)$, công thức sẽ dùng ngay ở Chương 4. Ma trận của bốn căn hộ minh hoạ cả chương: $Xw$ cho giá dự đoán, $X$ đủ hạng cột, $\kappa(X^\top X) \approx 58\,340$ là bình phương của $\kappa(X) \approx 241{,}5$, và gradient bằng 0 tại $w = (0{,}57;\ 0{,}024)$.

Đại số tuyến tính mô tả dữ liệu và mô hình, nhưng chưa nói gì về nhiễu. Dữ liệu thật luôn có nhiễu, và mô hình học từ một mẫu hữu hạn nên kết quả của nó cũng ngẫu nhiên. Chương 3 nhắc lại các công cụ xác suất để mô tả sự không chắc chắn đó.

3Xác suất và thống kê#

Chương 2 mô tả dữ liệu và mô hình bằng vector và ma trận, như thể mọi con số đều chính xác. Thực tế thì không: hai căn nhà cùng diện tích vẫn có giá khác nhau, nhãn do người gán có lúc sai, và mỗi lần thu thập lại dữ liệu ta được một mẫu khác. Mô hình học từ một mẫu hữu hạn như vậy, nên bản thân nó cũng là một đại lượng ngẫu nhiên. Xác suất là ngôn ngữ để nói về sự không chắc chắn đó, và nó còn trả lời được hai câu hỏi mà đại số tuyến tính không trả lời được: vì sao hàm mất mát có dạng như vậy, và vì sao regularization có tác dụng.

3.1Vai trò của xác suất trong học máy#

Xác suất xuất hiện trong giáo trình theo ba cách. Cách thứ nhất là mô tả dự đoán không chắc chắn. Hồi quy logistic (Chương 6) trả về xác suất một điểm thuộc lớp dương chứ không chỉ một nhãn, và nhờ có xác suất, ta chọn được ngưỡng quyết định theo chi phí của từng loại sai (Chương 8). Cách thứ hai là giải thích nguồn gốc của hàm mất mát. Bình phương sai số và cross-entropy không phải hai lựa chọn tuỳ ý; Chương 10 chỉ ra rằng chúng là hệ quả của nguyên lý hợp lý cực đại dưới hai giả thiết khác nhau về nhiễu. Cách thứ ba là giải thích nguồn gốc của regularization: Mục 10.4 chỉ ra rằng hồi quy ridge trùng với ước lượng hậu nghiệm cực đại khi tiên nghiệm của trọng số là phân phối Gauss, và kiểm chứng điều này bằng số.

3.2Kỳ vọng và phương sai#

Định nghĩa 3.1 (Kỳ vọng, phương sai)

Với biến ngẫu nhiên $X$ có hàm xác suất (hoặc hàm mật độ) $p$, kỳ vọng của $X$ là

$$\begin{aligned} \mathbb{E}[X] &= \sum_x x\,p(x) && \text{(rời rạc)}, \\ \mathbb{E}[X] &= \int x\,p(x)\,dx && \text{(liên tục)}, \end{aligned}$$

và phương sai của $X$ là $\operatorname{Var}(X) = \mathbb{E}\big[(X - \mathbb{E}X)^2\big] = \mathbb{E}[X^2] - (\mathbb{E}X)^2$.

Kỳ vọng là giá trị trung bình nếu lặp lại phép thử rất nhiều lần. Phương sai đo mức phân tán quanh giá trị trung bình đó; căn bậc hai của nó là độ lệch chuẩn, có cùng đơn vị với $X$.

Các tính chất sau được dùng nhiều lần. Với hằng số $a, b$,

$$\mathbb{E}[aX + b] = a\,\mathbb{E}[X] + b, \qquad \operatorname{Var}(aX + b) = a^2 \operatorname{Var}(X).$$

Kỳ vọng của tổng luôn bằng tổng các kỳ vọng, không cần điều kiện gì: $\mathbb{E}[X + Y] = \mathbb{E}[X] + \mathbb{E}[Y]$. Phương sai của tổng thì phụ thuộc vào mức độ hai biến liên quan với nhau:

$$\operatorname{Var}(X + Y) = \operatorname{Var}(X) + \operatorname{Var}(Y) + 2\operatorname{Cov}(X, Y),$$

trong đó hiệp phương sai $\operatorname{Cov}(X, Y) = \mathbb{E}\big[(X - \mathbb{E}X)(Y - \mathbb{E}Y)\big]$. Chuẩn hoá hiệp phương sai bằng tích hai độ lệch chuẩn ta được hệ số tương quan $\rho = \operatorname{Cov}(X,Y)/(\sigma_X\sigma_Y) \in [-1, 1]$. Chỉ khi $X$ và $Y$ không tương quan ($\rho = 0$), chẳng hạn khi chúng độc lập, phương sai của tổng mới bằng tổng các phương sai.

Ví dụ 3.1 (Trung bình của nhiều mô hình)

Giả sử có $n$ mô hình, dự đoán của mỗi mô hình là một biến ngẫu nhiên có phương sai $\sigma^2$, và mỗi cặp mô hình có hệ số tương quan $\rho$. Phương sai của trung bình $n$ dự đoán là

$$\operatorname{Var}\Big(\frac1n\sum_{i=1}^n X_i\Big) = \rho\,\sigma^2 + \frac{1-\rho}{n}\,\sigma^2.$$

Với $\sigma^2 = 1$ và $n = 10$: nếu các mô hình không tương quan ($\rho = 0$), phương sai giảm còn $0{,}1$; nếu $\rho = 0{,}5$, phương sai chỉ giảm còn $0{,}5 + 0{,}05 = 0{,}55$. Dù có thêm bao nhiêu mô hình, phương sai không xuống dưới $\rho\sigma^2$.

Ví dụ này là cơ sở lý thuyết của phương pháp bagging và rừng ngẫu nhiên: lấy trung bình nhiều mô hình chỉ giảm phương sai hiệu quả khi các mô hình ít tương quan với nhau. Rừng ngẫu nhiên chọn ngẫu nhiên một tập con đặc trưng ở mỗi nhát cắt của cây chính là để giảm $\rho$. Mục 3.3 của Học sâu đo hiện tượng này trên dữ liệu.

3.3Ma trận hiệp phương sai#

Khi dữ liệu có nhiều chiều, ta cần biết phương sai của từng chiều và hiệp phương sai giữa mọi cặp chiều. Các con số đó được xếp vào một ma trận.

Định nghĩa 3.2 (Ma trận hiệp phương sai)

Với vector ngẫu nhiên $x \in \mathbb{R}^d$ có kỳ vọng $\mu$, ma trận hiệp phương sai là

$$\Sigma = \mathbb{E}\big[(x - \mu)(x - \mu)^\top\big] \in \mathbb{R}^{d \times d}, \qquad \Sigma_{jk} = \operatorname{Cov}(x_j, x_k).$$

Từ $n$ điểm dữ liệu, gọi $X_c$ là ma trận dữ liệu đã trừ trung bình của từng cột, ước lượng mẫu của $\Sigma$ là

$$\hat\Sigma = \frac{1}{n-1} X_c^\top X_c.$$

Đường chéo của $\Sigma$ chứa phương sai của từng đặc trưng; các phần tử ngoài đường chéo chứa hiệp phương sai giữa từng cặp đặc trưng. Ma trận này có ba tính chất, ứng với ba chỗ dùng ở các chương sau. Trước hết, $\Sigma$ đối xứng và nửa xác định dương, vì $z^\top \Sigma z = \operatorname{Var}(z^\top x) \ge 0$ với mọi $z$. Theo định lý phổ, $\Sigma$ có hệ vector riêng trực chuẩn, và đó là các thành phần chính của PCA (Chương 14). Tiếp theo, trị riêng lớn nhất của $\Sigma$ là phương sai lớn nhất mà một phép chiếu lên một hướng đơn vị có thể đạt được, và hướng đạt giá trị đó là vector riêng tương ứng. Cuối cùng, giả thiết "naive" của thuật toán Naive Bayes Gauss tương đương với việc ép $\Sigma$ của mỗi lớp thành ma trận đường chéo, tức coi mọi cặp đặc trưng là không tương quan khi đã biết lớp; Mục 7.4 kiểm chứng điều này bằng số và cho thấy Naive Bayes, LDA và QDA chỉ khác nhau ở ràng buộc đặt lên $\Sigma$.

Bốn căn hộ của Chương 2 cho một ma trận hiệp phương sai cụ thể. Lấy hai đặc trưng là diện tích và giá; trừ trung bình 70 m² và 2,25 tỉ, các hàng của $X_c$ là $(-30;\ -0{,}75)$, $(-10;\ -0{,}15)$, $(10;\ 0{,}15)$ và $(30;\ 0{,}75)$, nên

$$\hat\Sigma = \frac13 X_c^\top X_c = \begin{pmatrix}666{,}7 & 16\\ 16 & 0{,}39\end{pmatrix}.$$

Phương sai của diện tích là 666,7, tức độ lệch chuẩn khoảng 25,8 m²; phương sai của giá là 0,39, tức độ lệch chuẩn khoảng 0,62 tỉ. Hiệp phương sai 16 dương, tức căn rộng hơn thì đắt hơn, và hệ số tương quan $16/\sqrt{666{,}7 \times 0{,}39} \approx 0{,}992$ cho thấy giá gần như tỉ lệ thuận với diện tích. Tỉ số $16/666{,}7 = 0{,}024$ là con số sẽ gặp lại ở Chương 4: đó là độ dốc của đường thẳng khớp bốn căn hộ tốt nhất. Hai phần tử trên đường chéo chênh nhau khoảng 1 700 lần chỉ vì đơn vị đo, mét vuông so với tỉ đồng, nên vector riêng ứng với trị riêng lớn nhất gần như trùng với trục diện tích; Mục 14.2 cho thấy vì sao cần chuẩn hoá trước khi dùng các vector riêng này.

Mẫu số $n - 1$ thay cho $n$ trong ước lượng mẫu có lý do, được giải thích ở Ví dụ 3.4.

3.4Phân phối Gauss#

Phân phối Gauss, hay phân phối chuẩn, là phân phối được dùng nhiều nhất, vì hai lý do. Về lý thuyết, định lý giới hạn trung tâm nói rằng tổng của nhiều biến ngẫu nhiên độc lập nhỏ xấp xỉ phân phối Gauss, nên nhiễu tổng hợp từ nhiều nguồn thường có dạng Gauss. Về tính toán, logarit của mật độ Gauss là một hàm bậc hai, nên các bài toán tối ưu dẫn xuất từ nó thường có nghiệm dạng đóng.

Định nghĩa 3.3 (Phân phối Gauss)

Biến ngẫu nhiên một chiều $x \sim \mathcal{N}(\mu, \sigma^2)$ có mật độ

$$p(x) = \frac{1}{\sqrt{2\pi\sigma^2}}\exp\!\left(-\frac{(x-\mu)^2}{2\sigma^2}\right).$$

Vector ngẫu nhiên $x \in \mathbb{R}^d$ có phân phối Gauss nhiều chiều $\mathcal{N}(\mu, \Sigma)$, với $\Sigma$ xác định dương, nếu có mật độ

$$p(x) = \frac{1}{(2\pi)^{d/2}|\Sigma|^{1/2}}\exp\!\left(-\tfrac12 (x-\mu)^\top \Sigma^{-1}(x-\mu)\right).$$

Đại lượng trong hàm mũ, $\Delta^2(x) = (x-\mu)^\top \Sigma^{-1}(x-\mu)$, gọi là bình phương khoảng cách Mahalanobis từ $x$ tới $\mu$. Các điểm có cùng khoảng cách Mahalanobis nằm trên một đường elip, có các trục là vector riêng của $\Sigma$ và độ dài bán trục tỉ lệ với căn bậc hai của trị riêng tương ứng.

Ví dụ 3.2

Cho $\mu = 0$ và $\Sigma = \operatorname{diag}(4, 1)$, tức độ lệch chuẩn theo trục thứ nhất là 2 và theo trục thứ hai là 1. Hai điểm $a = (2, 0)$ và $b = (0, 2)$ cùng cách gốc 2 đơn vị theo khoảng cách Euclid. Nhưng $\Delta^2(a) = 2^2/4 = 1$ còn $\Delta^2(b) = 2^2/1 = 4$, tức $a$ cách tâm 1 độ lệch chuẩn còn $b$ cách tâm 2 độ lệch chuẩn. Theo phân phối này, điểm $a$ bình thường hơn điểm $b$ nhiều.

Ví dụ trên cho thấy khoảng cách Mahalanobis là khoảng cách Euclid sau khi đã quy mỗi hướng về đơn vị độ lệch chuẩn của dữ liệu theo hướng đó. Đi một đơn vị theo hướng dữ liệu trải rộng thì "gần", còn theo hướng dữ liệu co hẹp thì "xa".

Lấy logarit của mật độ Gauss ta được

$$\log p(x) = -\tfrac12 (x-\mu)^\top \Sigma^{-1}(x-\mu) + \text{hằng số},$$

một hàm bậc hai của $x$. Nhận xét đơn giản này có hai hệ quả lớn: hợp lý cực đại dưới giả thiết nhiễu Gauss dẫn tới bài toán bình phương tối thiểu (Mục 10.2), và bộ phân loại dùng phân phối Gauss cho mỗi lớp có biên quyết định là mặt bậc hai (Mục 7.4).

3.5Định lý Bayes#

Định lý 3.1 (Định lý Bayes)

Với hai biến cố (hoặc biến ngẫu nhiên) $A$ và $B$, $p(B) > 0$:

$$p(A \mid B) = \frac{p(B \mid A)\, p(A)}{p(B)}, \qquad p(B) = \sum_{A'} p(B \mid A')\,p(A').$$

Định lý Bayes cho phép đổi chiều một xác suất có điều kiện: biết xác suất quan sát được $B$ khi $A$ xảy ra, suy ra xác suất $A$ xảy ra khi đã quan sát được $B$. Hai chiều này rất khác nhau, và nhầm lẫn chúng là lỗi suy luận phổ biến.

Ví dụ 3.3 (Xét nghiệm bệnh hiếm)

Một bệnh có tỉ lệ mắc 1% dân số. Xét nghiệm cho kết quả dương tính với 99% người mắc bệnh, và dương tính nhầm với 5% người không mắc bệnh. Một người có kết quả dương tính. Xác suất người đó thật sự mắc bệnh là

$$p(\text{bệnh} \mid +) = \frac{0{,}99 \times 0{,}01}{0{,}99 \times 0{,}01 + 0{,}05 \times 0{,}99} = \frac{0{,}0099}{0{,}0594} \approx 0{,}167.$$

Chỉ khoảng 1 trong 6 người có kết quả dương tính thật sự mắc bệnh, dù xét nghiệm "đúng 99%". Lý do là số người khoẻ rất lớn, nên 5% dương tính nhầm của họ vẫn nhiều hơn số người bệnh được phát hiện.

Hiện tượng trong Ví dụ 3.3 xuất hiện lại ở Chương 8 dưới tên gọi khác: khi lớp dương hiếm, precision của bộ phân loại có thể rất thấp dù tỉ lệ báo động nhầm nhỏ.

Trong học máy, định lý Bayes được dùng với $A$ là tham số $\theta$ của mô hình và $B$ là dữ liệu $\mathcal{D}$:

$$\underbrace{p(\theta \mid \mathcal{D})}_{\text{hậu nghiệm}} = \frac{\overbrace{p(\mathcal{D} \mid \theta)}^{\text{hợp lý}} \; \overbrace{p(\theta)}^{\text{tiên nghiệm}}}{\underbrace{p(\mathcal{D})}_{\text{bằng chứng}}}.$$

Phân phối tiên nghiệm $p(\theta)$ mô tả hiểu biết về tham số trước khi thấy dữ liệu. Hàm hợp lý $p(\mathcal{D} \mid \theta)$ cho biết dữ liệu quan sát được có khả năng xảy ra tới mức nào nếu tham số là $\theta$. Phân phối hậu nghiệm $p(\theta \mid \mathcal{D})$ là hiểu biết đã được cập nhật sau khi thấy dữ liệu. Mẫu số $p(\mathcal{D})$ không phụ thuộc $\theta$, nên khi tìm $\theta$ làm hậu nghiệm lớn nhất có thể bỏ qua nó:

$$\begin{aligned} \arg\max_\theta p(\theta \mid \mathcal{D}) &= \arg\max_\theta \; p(\mathcal{D} \mid \theta)\,p(\theta) \\ &= \arg\min_\theta \;\big[-\log p(\mathcal{D} \mid \theta) - \log p(\theta)\big]. \end{aligned}$$

Vế phải có dạng "mất mát cộng thành phần phạt". Chương 10 khai triển đẳng thức này và cho thấy thành phần phạt chính là regularization.

3.6Ước lượng tham số: độ chệch và phương sai#

Học một mô hình từ dữ liệu là ước lượng tham số của nó. Vì dữ liệu là một mẫu ngẫu nhiên, ước lượng thu được cũng là ngẫu nhiên: lấy một mẫu khác thì được một giá trị khác.

Định nghĩa 3.4 (Độ chệch, phương sai của ước lượng)

Một ước lượng $\hat\theta$ của tham số $\theta$ là một hàm của dữ liệu. Độ chệch (bias) và phương sai của nó là

$$\operatorname{Bias}(\hat\theta) = \mathbb{E}[\hat\theta] - \theta, \qquad \operatorname{Var}(\hat\theta) = \mathbb{E}\big[(\hat\theta - \mathbb{E}\hat\theta)^2\big].$$

Ước lượng có độ chệch bằng 0 gọi là ước lượng không chệch.

Ở đây kỳ vọng được lấy trên mọi tập dữ liệu có thể rút ra từ cùng một phân phối, không phải trên các điểm trong một tập dữ liệu. Để hình dung, hãy lặp lại việc thu thập dữ liệu và huấn luyện rất nhiều lần: độ chệch là khoảng cách từ trung bình các kết quả tới giá trị thật, còn phương sai là mức các kết quả tản ra quanh trung bình của chúng.

Định lý 3.2 (Phân tích sai số bình phương trung bình)

Với mọi ước lượng $\hat\theta$,

$$\mathbb{E}\big[(\hat\theta - \theta)^2\big] = \operatorname{Bias}(\hat\theta)^2 + \operatorname{Var}(\hat\theta).$$

Chứng minh

Đặt $m = \mathbb{E}[\hat\theta]$. Viết $\hat\theta - \theta = (\hat\theta - m) + (m - \theta)$ rồi bình phương và lấy kỳ vọng. Số hạng chéo $2(m - \theta)\,\mathbb{E}[\hat\theta - m]$ bằng 0 vì $\mathbb{E}[\hat\theta - m] = 0$. Hai số hạng còn lại là $\operatorname{Var}(\hat\theta)$ và $(m - \theta)^2$.

Ví dụ 3.4 (Vì sao chia cho $n-1$)

Với $n$ quan sát độc lập có phương sai $\sigma^2$, ước lượng $\hat\sigma^2_n = \frac1n\sum_i (x_i - \bar x)^2$ có kỳ vọng $\frac{n-1}{n}\sigma^2$, tức luôn nhỏ hơn giá trị thật. Nguyên nhân là $\bar x$ được tính từ chính dữ liệu, nên các điểm luôn gần $\bar x$ hơn so với gần giá trị trung bình thật. Chia cho $n - 1$ thay cho $n$ cho ước lượng không chệch. Với $n = 5$ và $\sigma^2 = 1$, mô phỏng 200 000 lần cho giá trị trung bình của $\hat\sigma^2_n$ là $0{,}802$, khớp với $4/5 = 0{,}8$.

Định lý 3.2 cho thấy một ước lượng không chệch chưa chắc là ước lượng tốt: nếu phương sai lớn, sai số tổng vẫn lớn. Ngược lại, chấp nhận một chút độ chệch để đổi lấy phương sai nhỏ hơn nhiều có thể làm sai số tổng giảm. Hồi quy ridge ở Chương 9 là ví dụ điển hình: nó là ước lượng có chệch, trong khi bình phương tối thiểu thông thường là ước lượng không chệch, vậy mà ridge thường có sai số nhỏ hơn. Mục 9.3 chỉ ra phần phương sai mà ridge cắt đi nằm ở những hướng nào.

Cùng ý tưởng này áp dụng cho dự đoán của cả mô hình, dưới tên gọi đánh đổi độ chệch – phương sai (bias–variance tradeoff). Chương 2 của Học sâu trình bày đầy đủ phân tích đó và đo từng thành phần trên 250 tập huấn luyện mô phỏng.

3.7Tóm tắt#

Kỳ vọng và phương sai mô tả giá trị trung bình và mức phân tán của một đại lượng ngẫu nhiên. Phương sai của tổng phụ thuộc vào hiệp phương sai, nên lấy trung bình nhiều mô hình chỉ giảm phương sai xuống tới mức $\rho\sigma^2$. Ma trận hiệp phương sai gom phương sai và hiệp phương sai của mọi cặp đặc trưng; nó đối xứng, nửa xác định dương, và các vector riêng của nó là các thành phần chính của PCA. Với bốn căn hộ, hiệp phương sai 16 giữa diện tích và giá chia cho phương sai 666,7 của diện tích cho đúng độ dốc 0,024 của Chương 4. Logarit mật độ Gauss là một hàm bậc hai, điều sẽ biến hợp lý cực đại thành bình phương tối thiểu. Định lý Bayes đổi chiều xác suất có điều kiện, như ví dụ xét nghiệm bệnh hiếm cho thấy chỉ khoảng 16,7% người dương tính thật sự mắc bệnh, và viết hậu nghiệm thành dạng mất mát cộng thành phần phạt. Cuối cùng, sai số bình phương của một ước lượng tách thành độ chệch bình phương cộng phương sai, nên một ước lượng có chệch nhưng ít dao động có thể tốt hơn một ước lượng không chệch.

Có đại số tuyến tính và xác suất, ta đã đủ công cụ cho thuật toán học máy đầu tiên. Chương 4 xét hồi quy tuyến tính, bài toán đơn giản tới mức có nghiệm dạng đóng, nên mọi hiện tượng của nó quan sát được trực tiếp.

4Hồi quy tuyến tính#

Ta bắt đầu với một bài toán quen thuộc: định giá căn hộ. Bảng dưới ghi diện tích và giá bán của bốn căn hộ trong cùng một khu, chính là bốn căn hộ của ma trận dữ liệu ở Mục 2.1. Đây là số liệu minh hoạ, chọn tròn để tính tay được.

Nếu được hỏi một căn 90 m² trong khu này đáng giá bao nhiêu, hầu hết mọi người sẽ trả lời khoảng 2,7 tỉ, vì giá tăng gần đều theo diện tích. Hồi quy tuyến tính biến trực giác "tăng gần đều" đó thành một quy trình chính xác: chọn một đường thẳng, đo xem đường thẳng khớp dữ liệu tới mức nào, rồi tìm đường khớp nhất. Đây là thuật toán học có giám sát đơn giản nhất, nhưng đáng học kỹ vì bài toán có nghiệm dạng đóng. Nhờ vậy, những hiện tượng sẽ gặp lại ở mọi mô hình phức tạp hơn, như overfitting, regularization, ảnh hưởng của số điều kiện và đánh đổi độ chệch – phương sai, đều quan sát được trực tiếp mà không bị lẫn với câu hỏi thuật toán tối ưu có hội tụ hay không.

4.1Bài toán hồi quy tuyến tính#

Mô hình đơn giản nhất cho bảng trên là một đường thẳng,

$$f(x) = w_0 + w_1 x.$$

Hệ số $w_1$ là phần giá tăng thêm khi diện tích tăng 1 m², còn $w_0$ là điểm đường thẳng cắt trục tung. Học từ dữ liệu ở đây nghĩa là chọn $w_0$ và $w_1$. Nhưng trước khi chọn, ta cần một cách nói đường thẳng nào tốt hơn đường thẳng nào.

Với mỗi căn hộ, đường thẳng mắc một sai số $y_i - f(x_i)$, tức chênh lệch giữa giá thật và giá dự đoán. Cộng thẳng các sai số thì không dùng được, vì sai số dương và sai số âm triệt tiêu nhau: một đường dự đoán quá cao cho nửa số căn và quá thấp cho nửa còn lại vẫn có thể cho tổng bằng 0. Cách phổ biến nhất là lấy trung bình bình phương sai số,

$$L(w_0, w_1) = \frac1n\sum_{i=1}^{n}\big(y_i - w_0 - w_1 x_i\big)^2.$$

Bình phương làm mọi sai số thành số dương, phạt sai số lớn nặng hơn nhiều so với sai số nhỏ, và cho một hàm trơn, dễ lấy đạo hàm. Còn vì sao là bình phương mà không phải trị tuyệt đối thì có một câu trả lời chính xác hơn, trình bày ở Mục 10.2: bình phương sai số là hệ quả của giả thiết nhiễu có phân phối Gauss.

Có hàm $L$, ta so sánh được các đường thẳng bằng số. Đường $f(x) = 0{,}03x$, tức giá 30 triệu đồng mỗi mét vuông, dự đoán 1,2; 1,8; 2,4 và 3,0 tỉ cho bốn căn. Sai số là 0,3; 0,3; 0 và 0, nên $L = (0{,}09 + 0{,}09)/4 = 0{,}045$. Đường $f(x) = 0{,}6 + 0{,}024x$ dự đoán 1,56; 2,04; 2,52 và 3,0 tỉ, với sai số $-0{,}06$; $0{,}06$; $-0{,}12$ và $0$, nên $L = 0{,}0216/4 = 0{,}0054$, nhỏ hơn khoảng tám lần. Đường thứ hai tốt hơn hẳn. Câu hỏi còn lại là có đường nào tốt hơn nữa không, và đường tốt nhất là đường nào. Mục 4.2 trả lời câu hỏi đó.

Trước khi giải, ta viết bài toán ở dạng tổng quát. Giá căn hộ còn phụ thuộc số phòng, tầng và khoảng cách tới trung tâm, nên mỗi điểm dữ liệu thường là một vector đặc trưng $x_i \in \mathbb{R}^d$ chứ không phải một số. Để công thức gọn, ta thêm vào mỗi $x_i$ một thành phần hằng bằng 1 ở vị trí đầu. Khi đó hệ số chặn trở thành trọng số $w_0$ ứng với thành phần này, và mô hình viết được là $f_w(x) = w^\top x$. Xếp các $x_i$ thành các hàng của ma trận $X$ và các nhãn thành vector $y$, toàn bộ dự đoán trên tập dữ liệu là $Xw$. Giáo trình dùng quy ước này ở mọi chỗ: cột đầu tiên của ma trận dữ liệu $X$ gồm toàn số 1.

Một cách tốt để nắm ký hiệu là tự kiểm tra kích thước. Với $n$ điểm dữ liệu, $X$ có $n$ hàng và $d$ cột, vector $w$ có $d$ thành phần, nên $Xw$ là vector $n$ chiều, cùng kích thước với $y$, đúng như cần để so từng dự đoán với nhãn của nó. Trong ví dụ căn hộ, $n = 4$, $d = 2$, và hàng đầu tiên của $X$ là $(1;\ 40)$.

Định nghĩa 4.1 (Hồi quy tuyến tính bình phương tối thiểu)

Với ma trận dữ liệu $X \in \mathbb{R}^{n\times d}$ và vector nhãn $y \in \mathbb{R}^n$, hồi quy tuyến tính tìm

$$\begin{aligned} \hat w &= \arg\min_w L(w), \\ L(w) &= \frac1n\sum_{i=1}^{n}\big(y_i - w^\top x_i\big)^2 = \frac1n\,\|y - Xw\|_2^2. \end{aligned}$$

Phương pháp này còn gọi là bình phương tối thiểu thông thường (ordinary least squares, OLS).

Theo khung ở Hình 1, đây là đủ ba thành phần của một thuật toán học: mô hình là họ hàm tuyến tính $w^\top x$, hàm mất mát là bình phương sai số, còn thuật toán tối ưu là cách tìm $\hat w$ mà Mục 4.2 sẽ trình bày.

Bài toán còn có một cách hiểu hình học, sẽ dùng nhiều ở các mục sau. Khi $w$ chạy khắp $\mathbb{R}^d$, vector dự đoán $Xw$ chạy khắp không gian cột của $X$ (Mục 2.1). Trong ví dụ căn hộ, $y$ là một vector trong $\mathbb{R}^4$, còn không gian cột là mặt phẳng hai chiều sinh bởi $(1; 1; 1; 1)$ và $(40; 60; 80; 100)$: dự đoán của mọi đường thẳng đều nằm trên mặt phẳng này. Cực tiểu $\|y - Xw\|_2$ nghĩa là tìm điểm trên mặt phẳng gần $y$ nhất, tức hình chiếu vuông góc của $y$ lên không gian cột. Vector phần dư $r = y - X\hat w$ vì thế phải vuông góc với mọi cột của $X$.

4.2Phương trình chuẩn#

Ta tìm đường thẳng tốt nhất cho ví dụ căn hộ trước, rồi mới tổng quát hoá. Hàm $L(w_0, w_1)$ là hàm bậc hai của hai biến và có dạng một cái chén: đi xa theo hướng nào nó cũng tăng. Đáy chén là điểm mà đạo hàm riêng theo cả hai biến đều bằng 0.

Đạo hàm theo $w_0$ cho

$$\frac{\partial L}{\partial w_0} = -\frac2n\sum_{i=1}^{n}\big(y_i - w_0 - w_1 x_i\big) = 0 \quad\Longleftrightarrow\quad \bar y = w_0 + w_1 \bar x,$$

với $\bar x$ và $\bar y$ là trung bình của các $x_i$ và các $y_i$. Phương trình này đã cho biết một điều cụ thể: đường thẳng tốt nhất luôn đi qua điểm trung bình $(\bar x, \bar y)$ của dữ liệu. Đạo hàm theo $w_1$ cho

$$\frac{\partial L}{\partial w_1} = -\frac2n\sum_{i=1}^{n}x_i\big(y_i - w_0 - w_1 x_i\big) = 0.$$

Thay $w_0 = \bar y - w_1\bar x$ vào phương trình thứ hai, mỗi số hạng trong tổng trở thành $x_i\big[(y_i - \bar y) - w_1(x_i - \bar x)\big]$, và giải ra

$$w_1 = \frac{\sum_i (x_i - \bar x)(y_i - \bar y)}{\sum_i (x_i - \bar x)^2}, \qquad w_0 = \bar y - w_1\bar x.$$

Ở bước cuối, thừa số $x_i$ đứng trước được thay bằng $x_i - \bar x$. Phép thay không làm đổi tử số và mẫu số, vì $\sum_i \bar x\,(y_i - \bar y) = 0$ và $\sum_i \bar x\,(x_i - \bar x) = 0$.

Công thức có một cách đọc quen thuộc từ Chương 3. Chia cả tử và mẫu cho $n - 1$, hệ số góc chính là hiệp phương sai mẫu giữa $x$ và $y$ chia cho phương sai mẫu của $x$; với bốn căn hộ, đó là tỉ số $16/666{,}7$ ở Mục 3.3. Hệ số góc lớn khi $y$ biến thiên cùng chiều với $x$ và mạnh so với độ phân tán của $x$.

Với bốn căn hộ, $\bar x = 70$ và $\bar y = 2{,}25$. Các độ lệch $x_i - \bar x$ là $-30$; $-10$; $10$; $30$ và các độ lệch $y_i - \bar y$ là $-0{,}75$; $-0{,}15$; $0{,}15$; $0{,}75$, nên tử số bằng $22{,}5 + 1{,}5 + 1{,}5 + 22{,}5 = 48$ và mẫu số bằng $900 + 100 + 100 + 900 = 2\,000$. Do đó $w_1 = 0{,}024$ tỉ đồng mỗi mét vuông, tức 24 triệu đồng, và $w_0 = 2{,}25 - 0{,}024 \cdot 70 = 0{,}57$. Đường thẳng này dự đoán 1,53; 2,01; 2,49 và 2,97 tỉ cho bốn căn, với sai số $-0{,}03$; $0{,}09$; $-0{,}09$; $0{,}03$ và $L = 0{,}018/4 = 0{,}0045$, nhỏ hơn cả đường thứ hai ở Mục 4.1. Căn 90 m² được định giá $0{,}57 + 0{,}024 \cdot 90 = 2{,}73$ tỉ, khớp với ước đoán bằng mắt ở đầu chương.

Hệ số chặn $w_0 = 0{,}57$ tỉ không có nghĩa một căn hộ 0 m² đáng giá 570 triệu đồng. Nó chỉ là điểm đường thẳng cắt trục tung, cần có để đường thẳng khớp dữ liệu trong khoảng 40 tới 100 m². Dùng mô hình cho những điểm nằm xa ngoài khoảng dữ liệu đã thấy, gọi là ngoại suy (extrapolation), luôn cần thận trọng.

Cách làm vừa rồi tổng quát hoá trực tiếp sang $d$ đặc trưng nhờ ký hiệu ma trận. Viết bình phương chuẩn thành tích vô hướng rồi khai triển như khai triển $(a - b)^2$:

$$\begin{aligned} L(w) &= \frac1n(y - Xw)^\top(y - Xw) \\ &= \frac1n\big(y^\top y - 2\,w^\top X^\top y + w^\top X^\top X\,w\big). \end{aligned}$$