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 đó.