Toán ứng dụng và Tính toán

Toán cho học máy

Đại số tuyến tính, tối ưu và xác suất làm nền tảng cho các thuật toán học mẫu hình từ dữ liệu.

Trực giácHọc máy: đi xuống một địa hình

Giả sử bạn muốn dự đoán điều gì đó — giá nhà, nhãn thư rác, từ tiếp theo trong câu — bằng một mô hình có các núm điều chỉnh $\theta$ . Huấn luyện mô hình nghĩa là chọn $\theta$ sao cho một độ đo sai số đã chọn $L(\theta)$ , gọi là hàm mất mát, càng nhỏ càng tốt. Nếu hình dung $L$ như độ cao của một địa hình trên không gian mọi cách đặt núm, việc học trở thành một quá trình vật lý: bắt đầu ở đâu đó, rồi liên tục bước xuống dốc.

z = \sin x \cos y

: một địa hình mất mát với nhiều đồi và thung lũng. Khác với một cái bát duy nhất, gradient descent xuất phát gần các điểm khác nhau có thể trượt vào các thung lũng khác nhau — các cực tiểu địa phương khác nhau.

Hình dạng bạn nhận được phụ thuộc vào mô hình. Một mô hình tuyến tính huấn luyện bằng sai số bình phương có hàm mất mát chính xác là một paraboloid — một cái bát duy nhất như cái dùng để minh họa tối ưu lồi — nên gradient descent luôn tìm được điểm khớp tốt nhất. Một mạng nơ-ron sâu, với nhiều lớp hàm phi tuyến ghép lại, thường có địa hình mất mát gần giống mặt gồ ghề ở trên: đầy những hố địa phương, cao nguyên phẳng và điểm yên ngựa.

Đại họcCực tiểu hóa rủi ro thực nghiệm

Định nghĩa: Hàm mất mát

Một hàm mất mát $\ell(\hat y, y)$ đo mức độ tệ của việc dự đoán $\hat y$ khi giá trị thật là $y$ : nó bằng $0$ (hoặc nhỏ) khi $\hat y$ gần $y$ , và tăng lên khi dự đoán tệ hơn. Với bài toán hồi quy, lựa chọn phổ biến là sai số bình phương $\ell(\hat y, y) = (\hat y - y)^2$ ; với phân loại, entropy chéo là chuẩn mực.

Định nghĩa: Rủi ro thực nghiệm

Với tập huấn luyện gồm $n$ ví dụ $\{(x_i, y_i)\}_{i=1}^n$ và một mô hình $f_\theta$ , rủi ro thực nghiệm $\hat R(\theta)$ là mất mát trung bình trên tập huấn luyện. Huấn luyện một mô hình — bao gồm hồi quy tuyến tính, hồi quy logistic, và cả mạng sâu — nghĩa là tìm $\theta$ cực tiểu hóa $\hat R(\theta)$ .

\hat R(\theta) = \frac{1}{n}\sum_{i=1}^n \ell(f_\theta(x_i), y_i)

Trên thực tế, ta quan tâm tới hiệu năng trên dữ liệu mới, không chỉ tập huấn luyện: rủi ro tổng thể (thật) $R(\theta)$ lấy trung bình mất mát trên toàn bộ phân phối nền $\mathcal{D}$ mà các ví dụ đến từ đó, chứ không chỉ $n$ ví dụ ta tình cờ lấy mẫu. Vì $\mathcal{D}$ không biết được, $R(\theta)$ không thể tính trực tiếp — $\hat R(\theta)$ chỉ là một đại diện, và khoảng cách $R(\theta) - \hat R(\theta)$ được gọi là khoảng cách tổng quát hóa.

R(\theta) = \mathbb{E}_{(x,y)\sim \mathcal{D}}[\ell(f_\theta(x), y)]

Đại họcGradient descent và tốc độ hội tụ

Gradient descent cực tiểu hóa $\hat R(\theta)$ (viết gọn là $L(\theta)$ bên dưới) bằng cách liên tục di chuyển theo hướng làm $L$ giảm nhanh nhất: gradient âm. Ở mỗi bước, ta tính $\nabla L(\theta_k)$ và di chuyển một khoảng nhỏ được điều khiển bởi tốc độ học $\eta > 0$ .

\theta_{k+1} = \theta_k - \eta \nabla L(\theta_k)

Các thuật toán huấn luyện phổ biến và quy tắc cập nhật của chúng
Phương pháp	Quy tắc cập nhật	Chi phí mỗi bước	Thường dùng cho
Gradient descent theo lô đầy đủ	$\theta_{k+1} = \theta_k - \eta \nabla L(\theta_k)$	$O(n)$ mỗi bước	Tập dữ liệu nhỏ, gradient chính xác
Gradient descent ngẫu nhiên	$\theta_{k+1} = \theta_k - \eta \nabla \ell_i(\theta_k)$	$O(1)$ mỗi bước	Tập dữ liệu khổng lồ, cập nhật nhanh nhưng nhiễu
SGD theo mini-batch	$\theta_{k+1} = \theta_k - \eta \dfrac{1}{b}\sum_{i \in B} \nabla \ell_i(\theta_k)$	$O(b)$ mỗi bước	Chuẩn mực trong học sâu; cân bằng tốc độ và ổn định
Momentum	$v_{k+1} = \beta v_k + \nabla L(\theta_k), \quad \theta_{k+1} = \theta_k - \eta v_{k+1}$	$O(n)$ hoặc $O(b)$ mỗi bước	Tăng tốc qua các thung lũng hẹp và cao nguyên

Định lý: Tốc độ hội tụ của gradient descent

Cho $L$ lồi và $L$ -trơn (gradient của nó Lipschitz với hằng số $L$ : $\|\nabla L(x) - \nabla L(y)\| \le L\|x-y\|$ ), và $\theta^\star$ cực tiểu hóa $L$ . Gradient descent với bước $\eta = 1/L$ thỏa mãn $L(\theta_K) - L(\theta^\star) \le \dfrac{L\|\theta_0 - \theta^\star\|^2}{2K}$ sau $K$ bước.

Vì sao đúng?

Tính trơn đảm bảo mỗi bước gradient làm $L$ giảm một lượng tỉ lệ với bình phương độ lớn gradient, nên $L(\theta_k)$ không bao giờ tăng. Tính lồi cho phép ta so sánh mức giảm mỗi bước đó với khoảng cách còn lại $L(\theta_k) - L(\theta^\star)$ . Cộng dồn các mức giảm được đảm bảo qua $K$ bước — một tổng kính viễn vọng — cho thấy tổng mức giảm bị chặn, và vì điểm tốt nhất trong một dãy không tăng ít nhất cũng tốt bằng trung bình, khoảng cách cuối cùng phải thu hẹp theo tốc độ $1/K$ .

Chứng minh

Do tính $L$ -trơn, với mọi $x, y$ : $L(y) \le L(x) + \nabla L(x)^\top (y-x) + \dfrac{L}{2}\|y-x\|^2$ . Đặt $y = \theta_{k+1} = \theta_k - \dfrac{1}{L}\nabla L(\theta_k)$ và $x = \theta_k$ ta được bổ đề giảm dần: $L(\theta_{k+1}) \le L(\theta_k) - \dfrac{1}{2L}\|\nabla L(\theta_k)\|^2$ .

Do tính lồi của $L$ : $L(\theta_k) \le L(\theta^\star) + \nabla L(\theta_k)^\top(\theta_k - \theta^\star)$ . Cộng vào bổ đề giảm dần: $L(\theta_{k+1}) - L(\theta^\star) \le \nabla L(\theta_k)^\top(\theta_k - \theta^\star) - \dfrac{1}{2L}\|\nabla L(\theta_k)\|^2$ .

Hoàn thiện bình phương ở vế phải: $\nabla L(\theta_k)^\top(\theta_k - \theta^\star) - \dfrac{1}{2L}\|\nabla L(\theta_k)\|^2 = \dfrac{L}{2}\left(\|\theta_k - \theta^\star\|^2 - \left\|\theta_k - \theta^\star - \dfrac{1}{L}\nabla L(\theta_k)\right\|^2\right) = \dfrac{L}{2}\left(\|\theta_k - \theta^\star\|^2 - \|\theta_{k+1} - \theta^\star\|^2\right)$ , vì $\theta_{k+1} - \theta^\star = \theta_k - \theta^\star - \dfrac{1}{L}\nabla L(\theta_k)$ .

Vậy $L(\theta_{k+1}) - L(\theta^\star) \le \dfrac{L}{2}\left(\|\theta_k - \theta^\star\|^2 - \|\theta_{k+1} - \theta^\star\|^2\right)$ . Cộng dồn bất đẳng thức này với $k = 0, \dots, K-1$ , vế phải rút gọn kính viễn vọng thành $\dfrac{L}{2}\left(\|\theta_0 - \theta^\star\|^2 - \|\theta_K - \theta^\star\|^2\right) \le \dfrac{L}{2}\|\theta_0 - \theta^\star\|^2$ .

Bổ đề giảm dần cũng cho thấy $L(\theta_k)$ không tăng, nên $L(\theta_K)$ nhỏ hơn hoặc bằng trung bình của $L(\theta_1), \dots, L(\theta_K)$ : $L(\theta_K) - L(\theta^\star) \le \dfrac{1}{K}\sum_{k=1}^K \left(L(\theta_k) - L(\theta^\star)\right) \le \dfrac{L\|\theta_0 - \theta^\star\|^2}{2K}$ , đúng bằng chặn cần chứng minh.

Đại họcLan truyền ngược: quy tắc chuỗi ở quy mô lớn

Một mạng có $D$ lớp tính $z^{(l)} = W^{(l)} a^{(l-1)} + b^{(l)}$ , rồi áp dụng một hàm phi tuyến $a^{(l)} = \sigma(z^{(l)})$ , với $l = 1, \dots, D$ , và $a^{(0)}$ là đầu vào. Áp dụng ngây thơ quy tắc chuỗi để tính $\partial L / \partial W^{(l)}$ cho từng lớp riêng rẽ sẽ lặp lại cùng các phép tính con nhiều lần, tốn thời gian tăng theo bậc hai với độ sâu.

z^{(l)} = W^{(l)} a^{(l-1)} + b^{(l)}, \qquad a^{(l)} = \sigma(z^{(l)})

Lan truyền ngược tránh công việc lặp lại bằng cách tính một đại lượng trung gian cho mỗi lớp, số hạng lỗi $\delta^{(l)} = \partial L / \partial z^{(l)}$ , bắt đầu từ lớp đầu ra và đi ngược lại. Mỗi $\delta^{(l)}$ được xây dựng trực tiếp từ $\delta^{(l+1)}$ , tái sử dụng nó thay vì tính lại, và gradient của trọng số suy ra ngay từ $\delta^{(l)}$ và đầu vào của lớp $a^{(l-1)}$ :

\delta^{(l)} = \left((W^{(l+1)})^\top \delta^{(l+1)}\right) \odot \sigma'(z^{(l)}), \qquad \frac{\partial L}{\partial W^{(l)}} = \delta^{(l)} (a^{(l-1)})^\top

Vì mỗi $\delta^{(l)}$ chỉ được tính một lần và tái sử dụng bởi lớp phía trước nó, tổng chi phí của một lượt lan truyền ngược tỉ lệ với $D$ , cùng bậc với một lượt lan truyền xuôi — không phải $D^2$ . Đây chính là điều khiến việc huấn luyện các mạng có hàng chục hoặc hàng trăm lớp trở nên khả thi về mặt tính toán.

Đại họcGiảm chiều dữ liệu: SVD và PCA

Dữ liệu thực tế thường có các đặc trưng dư thừa, tương quan với nhau. Phân tích giá trị kỳ dị (SVD) phân tích bất kỳ ma trận $A$ nào (chẳng hạn $n$ điểm dữ liệu đã căn giữa xếp thành hàng) thành $A = U \Sigma V^\top$ , trong đó $U$ và $V$ có các cột trực chuẩn và $\Sigma$ là ma trận đường chéo với các phần tử không âm $\sigma_1 \ge \sigma_2 \ge \cdots \ge 0$ , gọi là giá trị kỳ dị.

A = U \Sigma V^\top

Phân tích thành phần chính (PCA) dùng các vector kỳ dị phải $v_1, v_2, \dots$ (các cột của $V$ ) làm trục tọa độ mới: $v_1$ là hướng mà dữ liệu (đã căn giữa) trải rộng nhất, $v_2$ là hướng trải rộng nhì, v.v., mỗi hướng trực giao với các hướng trước. Chỉ giữ lại $k$ hướng đầu và bỏ phần còn lại nén dữ liệu trong khi giữ được nhiều biến thiên nhất có thể mà bất kỳ phép chiếu $k$ chiều nào cũng có thể giữ.

Định lý: Định lý Eckart–Young–Mirsky

Cho $A \in \mathbb{R}^{m \times n}$ có các giá trị kỳ dị $\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_r > 0$ , và với $k < r$ đặt $A_k = \sum_{i=1}^k \sigma_i u_i v_i^\top$ chỉ giữ $k$ thành phần kỳ dị đầu. Khi đó với mọi ma trận $B$ có $\operatorname{rank}(B) \le k$ , $\|A - B\|_2 \ge \sigma_{k+1}$ , và chặn này đạt được: $\|A - A_k\|_2 = \sigma_{k+1}$ . Vậy $A_k$ là xấp xỉ hạng $k$ tốt nhất của $A$ theo chuẩn toán tử.

Vì sao đúng?

Các giá trị kỳ dị đo mức độ $A$ kéo giãn vector theo mỗi hướng trực giao $v_i$ ; giữ lại các giá trị lớn nhất và bỏ các giá trị nhỏ nhất nghĩa là bỏ đi các hướng mà $A$ kéo giãn ít nhất. Bất kỳ ma trận hạng $k$ nào khác $B$ đều phải thất bại trong việc tái tạo một hướng nào đó trong số $k+1$ hướng kỳ dị hàng đầu (có quá nhiều hướng để vừa trong một ảnh $k$ chiều), và thất bại đó tốn ít nhất $\sigma_{k+1}$ .

Chứng minh

Đạt được chặn. Vì $U, V$ có các cột trực chuẩn, $\|A - A_k\|_2 = \|U(\Sigma - \Sigma_k)V^\top\|_2 = \|\Sigma - \Sigma_k\|_2$ , trong đó $\Sigma_k$ giữ $k$ giá trị kỳ dị đầu và đặt phần còn lại bằng 0. $\Sigma - \Sigma_k$ là ma trận đường chéo với các phần tử $0, \dots, 0, \sigma_{k+1}, \dots, \sigma_r$ , nên chuẩn toán tử của nó là phần tử lớn nhất, $\sigma_{k+1}$ .

Tính tối ưu. Cho $B$ là ma trận bất kỳ với $\operatorname{rank}(B) \le k$ ; không gian không (hạt nhân) của nó có số chiều ít nhất $n - k$ . Đặt $S = \operatorname{span}(v_1, \dots, v_{k+1})$ , một không gian con $(k+1)$ chiều. Vì $\dim(\ker B) + \dim(S) \ge (n-k) + (k+1) = n+1 > n$ , hai không gian con này phải giao nhau nhiều hơn chỉ gốc tọa độ: tồn tại vector đơn vị $z \in S$ với $Bz = 0$ .

Viết $z = \sum_{i=1}^{k+1} c_i v_i$ với $\sum_{i=1}^{k+1} c_i^2 = 1$ (vì $z$ có chuẩn đơn vị và các $v_i$ trực chuẩn). Vì $Bz = 0$ , $\|(A-B)z\| = \|Az\| = \left\|\sum_{i=1}^{k+1} c_i \sigma_i u_i\right\| = \sqrt{\sum_{i=1}^{k+1} c_i^2 \sigma_i^2}$ , dùng tính trực chuẩn của các $u_i$ .

Vì $\sigma_i \ge \sigma_{k+1}$ với mọi $i \le k+1$ , $\sum_{i=1}^{k+1} c_i^2 \sigma_i^2 \ge \sigma_{k+1}^2 \sum_{i=1}^{k+1} c_i^2 = \sigma_{k+1}^2$ . Do đó $\|A-B\|_2 \ge \|(A-B)z\| \ge \sigma_{k+1}$ với mọi ma trận hạng $\le k$ là $B$ , cùng với việc chặn đạt được, điều này chứng minh định lý.

Cùng $A_k$ đó cũng cực tiểu hóa sai số theo chuẩn Frobenius trong số các ma trận hạng $\le k$ , với sai số bị loại bỏ bằng các giá trị kỳ dị bị loại bỏ: $\|A - A_k\|_F = \sqrt{\sum_{i=k+1}^r \sigma_i^2}$ . Vì tổng phương sai của dữ liệu bằng $\sum_i \sigma_i^2$ , đây chính xác là phương sai mà PCA bỏ lại khi chỉ giữ $k$ thành phần — đại lượng này càng nhỏ, $k$ chiều càng tóm tắt trung thực dữ liệu gốc.

\|A - A_k\|_F = \sqrt{\sum_{i=k+1}^r \sigma_i^2}

Đại họcỨng dụng thực tiễn và Ví dụ minh họa

Các công cụ này xuất hiện cùng nhau trong hầu hết mọi hệ thống học máy thực tế: gradient descent (và các biến thể của nó) huấn luyện hệ thống gợi ý, bộ phân loại ảnh và mô hình ngôn ngữ; lan truyền ngược là thứ khiến việc huấn luyện mạng sâu cho nhận dạng giọng nói và thị giác máy tính khả thi; và PCA được dùng để nén dữ liệu gen, khử nhiễu tín hiệu cảm biến, và trực quan hóa các tập dữ liệu tài chính hoặc khoa học nhiều chiều xuống còn hai hoặc ba chiều.

Ví dụ: Một bước gradient descent để dự đoán giá nhà

Một trang bất động sản mô hình hóa giá dự đoán (đơn vị $100{,}000$ đô la) là $\hat y = \theta x$ , với $x$ là diện tích nhà (đơn vị $1{,}000$ feet vuông). Ba ngôi nhà huấn luyện cho $(x_i, y_i)$ : $(1, 2)$ , $(2, 3)$ , $(3, 5)$ . Dùng rủi ro thực nghiệm sai số bình phương $\hat R(\theta) = \tfrac{1}{3}\sum_{i=1}^3 (\theta x_i - y_i)^2$ và xuất phát từ $\theta_0 = 1$ , tìm $\theta_1$ sau một bước gradient descent với $\eta = 0.05$ .

Lời giải

Trước tiên lấy đạo hàm: $\nabla \hat R(\theta) = \tfrac{2}{3}\sum_{i=1}^3 x_i(\theta x_i - y_i) = \tfrac{2}{3}\big[(\theta - 2) + 2(2\theta - 3) + 3(3\theta - 5)\big] = \tfrac{2}{3}(14\theta - 23)$ .

Tính tại $\theta_0 = 1$ : các dự đoán là $\hat y_i = 1, 2, 3$ ; phần dư $\hat y_i - y_i = -1, -1, -2$ ; nên $\nabla \hat R(1) = \tfrac{2}{3}(14 \cdot 1 - 23) = \tfrac{2}{3}(-9) = -6$ .

Áp dụng quy tắc cập nhật: $\theta_1 = \theta_0 - \eta \nabla \hat R(\theta_0) = 1 - 0.05 \times (-6) = 1 + 0.3 = 1.3$ .

Gradient âm nên gradient descent đã đẩy $\theta$ tăng lên đúng hướng: tăng độ dốc giá-trên-diện-tích làm giảm sai số bình phương trên tập huấn luyện này, đưa $\theta$ tiến về điểm tối ưu bình phương tối thiểu thật sự (hóa ra là $\theta^\star = 23/14 \approx 1.64$ , tìm được bằng cách đặt $\nabla \hat R(\theta) = 0$ ).

Ví dụ: Tìm thành phần chính của một ma trận hiệp phương sai

Hai đặc trưng đã căn giữa có ma trận hiệp phương sai $\Sigma = \begin{pmatrix} 4 & 2 \\ 2 & 1 \end{pmatrix}$ . Tìm hướng của thành phần chính thứ nhất và tỉ lệ phương sai tổng nó giải thích được.

Lời giải

Các hướng chính là vector riêng của $\Sigma$ . Phương trình đặc trưng là $\det(\Sigma - \lambda I) = (4-\lambda)(1-\lambda) - 2 \cdot 2 = \lambda^2 - 5\lambda = 0$ , cho trị riêng $\lambda_1 = 5$ , $\lambda_2 = 0$ .

Với $\lambda_1 = 5$ : giải $(\Sigma - 5I)v = 0$ , tức $\begin{pmatrix} -1 & 2 \\ 2 & -4 \end{pmatrix} v = 0$ , cho $v \propto (2, 1)$ . Chuẩn hóa, hướng thành phần chính thứ nhất là $u_1 = \tfrac{1}{\sqrt5}(2, 1)$ .

Tổng phương sai là $\operatorname{tr}(\Sigma) = 4 + 1 = 5$ , bằng $\lambda_1 + \lambda_2 = 5 + 0$ . Tỉ lệ phương sai được giải thích bởi thành phần thứ nhất là $\lambda_1/(\lambda_1+\lambda_2) = 5/5 = 100\%$ .

Vì $\lambda_2 = 0$ , tập dữ liệu này chính xác là một chiều: mọi điểm nằm đúng trên hướng $(2,1)$ , nên chiếu lên đường thẳng duy nhất đó (xấp xỉ hạng 1) không mất thông tin nào cả, khớp với công thức Eckart–Young $\|A-A_1\|_F = \sqrt{\lambda_2} = 0$ .

Hiện trạng nghiên cứu tính đến năm 2026

Tính đến năm 2026, một câu hỏi mở trung tâm là vì sao các mạng sâu bị tham số hóa quá mức nặng nề vẫn tổng quát hóa tốt dù có thể khớp hoàn hảo với nhãn ngẫu nhiên, như Zhang và cộng sự (2017) đã chứng minh bằng thực nghiệm, làm lung lay các cách giải thích cổ điển dựa trên dung lượng mô hình. Belkin và cộng sự (2019) chỉ ra điều này khớp với một đường cong giảm kép rộng hơn: khi kích thước mô hình vượt qua điểm mà sai số huấn luyện lần đầu về 0, sai số kiểm tra có thể tăng vọt rồi lại giảm, trái ngược với đánh đổi thiên lệch–phương sai hình chữ U trong sách giáo khoa. Về mặt tối ưu, khung nhân tiếp tuyến nơ-ron của Jacot, Gabriel và Hongler (2018) cho thấy trong giới hạn độ rộng vô hạn, gradient descent trên mạng nơ-ron hoạt động như một phương pháp nhân cố định, cho một góc nhìn chặt chẽ (dù lý tưởng hóa) về việc vì sao huấn luyện trên các địa hình không lồi như vậy lại thường tìm được nghiệm tốt trong thực tế; mở rộng các kết quả này sang chế độ huấn luyện độ rộng hữu hạn, thời gian hữu hạn thực tế vẫn là một hướng nghiên cứu đang hoạt động.

Hàm mất mát là $L(\theta) = (\theta - 4)^2$ . Xuất phát từ $\theta_0 = 0$ với tốc độ học $\eta = 0.1$ , $\theta_1$ sau một bước gradient descent là bao nhiêu?

Công thức nào định nghĩa đúng rủi ro thực nghiệm $\hat R(\theta)$ cho tập huấn luyện $n$ ví dụ $\{(x_i,y_i)\}$ và hàm mất mát $\ell$ ?

Một ma trận có các giá trị kỳ dị $\sigma_1 = 6$ , $\sigma_2 = 3$ , $\sigma_3 = 2$ . Sai số theo chuẩn Frobenius $\|A - A_1\|_F$ của xấp xỉ hạng 1 tốt nhất $A_1$ là bao nhiêu?

Mạng thị giác của một xe tự lái có 50 lớp. Tính gradient của mọi trọng số bằng lan truyền ngược tốn chi phí xấp xỉ một lượt lan truyền xuôi thêm, chứ không phải gấp 50 lần. Tính chất nào của lan truyền ngược giải thích điều này?

Tài liệu tham khảo

Ian Goodfellow, Yoshua Bengio, Aaron Courville (2016). Deep Learning
Christopher M. Bishop (2006). Pattern Recognition and Machine Learning
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, Oriol Vinyals (2017). Understanding deep learning requires rethinking generalization · arXiv:1611.03530
Arthur Jacot, Franck Gabriel, Clément Hongler (2018). Neural Tangent Kernel: Convergence and Generalization in Neural Networks · arXiv:1806.07572
Mikhail Belkin, Daniel Hsu, Siyuan Ma, Soumik Mandal (2019). Reconciling modern machine learning practice and the classical bias-variance trade-off · arXiv:1812.11118