Mọi mô hình trí tuệ nhân tạo, từ hồi quy tuyến tính cổ điển đến các mạng nơ-ron sâu với hàng trăm tỷ , đều vận hành quanh một cơ chế cốt lõi: Ánh xạ dữ liệu đầu vào thành dự đoán, đo lường sai số bằng hàm mất mát, và lần theo để tinh chỉnh tham số. Khi mô hình dự đoán chệch hướng, ta cần biết chính xác tham số nào phải thay đổi, thay đổi bao nhiêu và theo chiều nào.

Bài giảng mở đầu này hệ thống hóa các trụ cột toán học và tính toán số nền tảng sẽ đồng hành cùng chúng ta xuyên suốt toàn bộ chương trình:

1. Đại số và Chuẩn: Công cụ biểu diễn đồng thời hàng triệu quan sát, đo lường khoảng cách và tận dụng năng lực tính toán song song trên GPU.
2. Giải tích và đa biến (Gradient & ): Chiếc la bàn chỉ hướng dốc nhất để hạ thấp hàm mất mát và tấm gương phản chiếu độ cong địa hình tối ưu.
3. Phần bù Schur và Phân tích giá trị kỳ dị (SVD): Các công cụ đại số cao cấp phân tích tính xác định dương của khối và bản chất hình học của không gian dữ liệu.
4. Đại số tuyến tính số (Numerical Linear Algebra): Cấu trúc tính toán thực tế, phân tích Cholesky, khai thác thưa và ngân sách độ phức tạp tính toán (flops).
5. Mô hình xác suất và Ước lượng hợp lý cực đại (MLE): Cội nguồn lý thuyết giải thích vì sao tiêu chuẩn sai số xuất hiện tự nhiên từ giả thiết .

Toàn bộ công thức và biến đổi giải tích sẽ được gắn kết chặt chẽ với các ví dụ số học tường minh, giúp người học tự tay kiểm chứng từng bước biến đổi đại số mà không bị phân tâm bởi quy mô dữ liệu.

---

1. Biểu diễn dự đoán bằng phép nhân ma trận

Xét bài toán học có giám sát đơn giản: Ta muốn xây dựng một mô hình tuyến tính đơn để dự đoán biến mục tiêu ${\hat{b}}_i$ từ đầu vào $a_i$ theo quy tắc ${\hat{b}}_i=a_{i}w$.

Giả sử ta thu thập được ba quan sát thực nghiệm sau:

Quan sát $i$	Đầu vào $a_i$	Đầu ra thực tế $b_i$
1	1	1
2	2	2
3	3	2

Ở đây, các cặp $(a_i,b_i)$ là dữ liệu thực nghiệm đã cố định. Trọng số $w\in \mathbb{R}$ là tự do mà chúng ta có quyền điều chỉnh để mô hình khớp dữ liệu nhất có thể. Chẳng hạn, nếu thử chọn $w=1$, mô hình đưa ra ba dự đoán lần lượt là $1,2,3$. Hai dự đoán đầu khớp hoàn toàn với thực tế, nhưng ở quan sát thứ ba, mô hình dự đoán vượt giá trị thực tế một đơn vị (${\hat{b}}_3-b_3=3-2=1$).

Thay vì viết ba phương trình rời rạc bằng vòng lặp tuần tự, trong kỹ nghệ AI ta gom toàn bộ đầu vào thành một cột và đầu ra thành một cột:

$$A=\left[\begin{array}{c}1\\ 2\\ 3\end{array}\right],b=\left[\begin{array}{c}1\\ 2\\ 2\end{array}\right],\hat{b}=Aw,r=Aw-b.$$

• $b,\hat{b},r\in {\mathbb{R}}^3$ là các danh sách số có thứ tự, trong đó mỗi phần tử đại diện cho một mẫu dữ liệu.
• $A\in {\mathbb{R}}^{3\times 1}$ là bảng số gồm 3 hàng và 1 cột.
• phần dư $r=\hat{b}-b$ phản ánh độ lệch giữa dự đoán và nhãn thực tế. Ta quy ước dấu phần dư là dự đoán trừ đi quan sát. Sự nhất quán về quy ước dấu này là điều kiện tiên quyết để tính đúng chiều của gradient sau này.

Trong bài toán tổng quát với $m$ quan sát và $n$ đặc trưng, dữ liệu có kích thước $A\in {\mathbb{R}}^{m\times n}$, trọng số $w\in {\mathbb{R}}^n$, còn nhãn thực tế và phần dư là các vector trong không gian $m$ chiều: $b,r\in {\mathbb{R}}^m$. Hàng thứ $i$ của ma trận $A$ (ký hiệu $a_i^T$) chứa đựng toàn bộ thông tin đặc trưng của mẫu thứ $i$, và $a_i^{T}w$ sinh ra đúng giá trị dự đoán cho mẫu đó.

Một cách người ta hay dùng trong thực tế để không bao giờ nhầm lẫn chiều khi nhân là quy tắc "khớp ở giữa, nở hai đầu": Khi nhân ma trận kích thước $(m\times k)$ với ma trận kích thước $(k\times n)$, hai chỉ số ở giữa bắt buộc phải trùng nhau để các phép nhân thực hiện được, và kết quả thu được sẽ có kích thước chính là hai đầu ngoài cùng $(m\times n)$. Trong kỹ nghệ học sâu, tư duy ma trận hóa này (vectorization) giúp thuật toán chạy nhanh hơn hàng trăm lần trên phần cứng GPU/TPU so với các vòng lặp tuần tự.

---

2. Chuẩn vector và Chuẩn ma trận

Làm thế nào để đo lường độ lớn của một hoặc kích thước của một toán tử? Để làm được điều này, ta cần đến khái niệm Chuẩn ().

2.1. Chuẩn vector

Với hai $u,v\in {\mathbb{R}}^n$, (inner product) được định nghĩa là:

$$u^{T}v=\sum _{j=1}^n{u}_j{v}_j=u_1{v}_1+u_2{v}_2+\cdots +u_n{v}_n.$$

Cần phân biệt rõ: Đại lượng $u^{T}v$ là một số thực vô hướng (scalar), trong khi tích ngoài $u{v}^T$ lại tạo ra một kích thước $n\times n$. Hai cấu trúc này hoàn toàn khác biệt và không được hoán đổi cho nhau.

Các thông dụng nhất trong học máy bao gồm:

1. ($L_2$): Đo khoảng cách hình học thẳng hàng từ gốc tọa độ:
   $$\parallel u{\parallel }_2=\sqrt{u^{T}u}=\sqrt{\sum _{j=1}^n{u}_j^2}.$$
2. Chuẩn $L_1$ (Manhattan): Tổng giá trị tuyệt đối các tọa độ:
   $$\parallel u{\parallel }_1=\sum _{j=1}^n|u_j|=|u_1|+|u_2|+\cdots +|u_n|.$$
   Chuẩn $L_1$ đóng vai trò cốt tử trong hồi quy Lasso và nén tín hiệu nhờ đặc tính thúc đẩy nghiệm thưa (sparse solution).
3. Chuẩn cực đại ($L_{\mathrm{\infty }}$): Độ lệch lớn nhất trong các thành phần:
   $$\parallel u{\parallel }_{\mathrm{\infty }}=\underset{1\le j\le n}{max}|u_j|.$$
4. Chuẩn bậc $p$ tổng quát ($L_p$): Với $p\ge 1$:
   $$\parallel u{\parallel }_p={(\sum _{j=1}^n|u_j{|}^p)}^{1/p}.$$

2.2. Chuẩn ma trận

Với $A\in {\mathbb{R}}^{m\times n}$, hai chuẩn quan trọng nhất là:

1. Chuẩn Frobenius: Tương đương với coi như một kéo dài:
   $$\parallel A{\parallel }_F=\sqrt{\mathrm{tr}(A^{T}A)}=\sqrt{\sum _{i=1}^m\sum _{j=1}^n{A}_{ij}^2}.$$
2. Chuẩn phổ (Spectral / Chuẩn cảm sinh $L_2$): Đo độ khuếch đại lớn nhất mà $A$ có thể tác động lên một đơn vị:
   $$\parallel A{\parallel }_2=\underset{x\ne 0}{sup}\frac{\parallel Ax{\parallel }_2}{\parallel x{\parallel }_2}={\sigma }_{max}(A),$$
   trong đó ${\sigma }_{max}(A)$ là giá trị kỳ dị lớn nhất của $A$.

---

3. Giải tích ma trận và Đạo hàm nhiều biến

Khi tối ưu hóa các nhận đầu vào là hoặc , việc thành thạo các quy tắc ma trận là điều kiện bắt buộc để tính toán gradient nhanh chóng và chính xác.

3.1. Gradient và Vi phân toàn phần

Cho hàm mục tiêu khả vi $f:{\mathbb{R}}^n\to \mathbb{R}$. gradient là vector cột chứa toàn bộ các bậc nhất:

$$\mathrm{\nabla }f(w)=\left[\begin{array}{c}\frac{\partial f}{\partial w_1}\\ ⋮\\ \frac{\partial f}{\partial w_n}\end{array}\right]\in {\mathbb{R}}^n.$$

Mối liên hệ giữa gradient và vi phân toàn phần cấp một $df$:

$$df=\sum _{j=1}^n\frac{\partial f}{\partial w_j}d{w}_j=(\mathrm{\nabla }f(w){)}^{T}dw.$$

Quy tắc vi phân này là bí quyết giúp ta tìm gradient của các biểu thức phức tạp mà không cần tách rời từng tọa độ.

3.2. Một số công thức đạo hàm ma trận cốt lõi

1. Hàm tuyến tính: Xét $f(w)=a^{T}w$. Vi phân $df=a^{T}dw$, suy ra:
   $${\mathrm{\nabla }}_w(a^{T}w)=a.$$
2. Hàm toàn phương: Xét $f(w)=\frac{1}{2}{w}^{T}Pw$ với đối xứng $P=P^T$. Vi phân:
   $$df=\frac{1}{2}(d{w}^{T}Pw+w^{T}Pdw)=w^{T}Pdw=(Pw{)}^{T}dw⟹{\mathrm{\nabla }}_w\left(\frac{1}{2}{w}^{T}Pw\right)=Pw.$$
3. theo vết (Trace):
   $${\mathrm{\nabla }}_X\mathrm{tr}(AX)=A^T,{\mathrm{\nabla }}_X\mathrm{tr}(X^{T}AX)=(A+A^T)X.$$
4. của Logarit Định thức: Cho đối xứng dương xác định $X\succ 0$:
   $${\mathrm{\nabla }}_X\log det(X)=X^{-1}.$$

3.3. Gradient của Hàm mất mát Bình phương tối thiểu

Xét hàm mất mát:

$$f(w)=\frac{1}{2}\parallel Aw-b{\parallel }_2^2=\frac{1}{2}(Aw-b{)}^T(Aw-b).$$

Khai triển hàm mất mát:

$$f(w)=\frac{1}{2}{w}^T{A}^{T}Aw-b^{T}Aw+\frac{1}{2}{b}^{T}b.$$

Lấy vi phân theo biến $w$:

$$df=w^T{A}^{T}Adw-b^{T}Adw=(A^{T}Aw-A^{T}b{)}^{T}dw=[A^T(Aw-b){]}^{T}dw.$$

Từ đó, ta thu được công thức gradient chuẩn mực:

$$\boxed{{\displaystyle \mathrm{\nabla }f(w)=A^{T}r=A^T(Aw-b).}}$$

Ý nghĩa hình học của gradient: gradient $\mathrm{\nabla }f(w)$ luôn chỉ về hướng tăng nhanh nhất (dốc nhất). Do đó, hướng di chuyển tự nhiên để hạ thấp sai số là hướng ngược chiều gradient: Hướng $-\mathrm{\nabla }f(w)$. Đây chính là nguyên lý của phương pháp Gradient Descent.

---

4. Ma trận Hessian, Tính xác định dương và Phần bù Schur

4.1. Ma trận Hessian và Khai triển Taylor bậc hai

$H={\mathrm{\nabla }}^{2}f(w)\in {\mathbb{R}}^{n\times n}$ toàn bộ các bậc hai:

$$H_{ij}=\frac{{\partial }^{2}f}{\partial w_i\partial w_j}.$$

phản ánh độ cong địa hình của hàm mục tiêu qua khai triển Taylor bậc hai quanh điểm $w$:

$$f(w+d)\approx f(w)+\mathrm{\nabla }f(w{)}^{T}d+\frac{1}{2}{d}^{T}Hd.$$

Độ cong của theo hướng dịch chuyển $d\in {\mathbb{R}}^n$ được định đoạt bởi dạng toàn phương $d^{T}Hd$:

• Nếu $d^{T}Hd>0$: Địa hình uốn cong lên trên theo hướng $d$ (đáy thung lũng).
• Nếu $d^{T}Hd<0$: Địa hình uốn cong xuống dưới theo hướng $d$ (đỉnh đồi).
• Nếu $d^{T}Hd=0$: Địa hình phẳng tuyến tính theo hướng $d$.

Với hàm mất mát $f(w)=\frac{1}{2}\parallel Aw-b{\parallel }_2^2$, của gradient $\mathrm{\nabla }f(w)=A^{T}Aw-A^{T}b$ cho ra hằng số:

$$H={\mathrm{\nabla }}^{2}f(w)=A^{T}A.$$

Dạng toàn phương của này với mọi $d\in {\mathbb{R}}^n$:

$$d^{T}Hd=d^T(A^{T}A)d=(Ad{)}^T(Ad)=\parallel Ad{\parallel }_2^2\ge 0.$$

Vì của một luôn không âm, ta có $d^{T}Hd\ge 0$ với mọi hướng $d$. Một đối xứng thỏa mãn điều kiện này được gọi là (Positive Semidefinite, ký hiệu $H⪰0$). Điều này chứng minh rằng mặt mất mát của bài toán luôn là một mặt lồi paraboloid hướng lên trên.

Để là dương xác định ngặt (Positive Definite, ký hiệu $H\succ 0$, tức $d^{T}Hd>0$ với mọi $d\ne 0$), điều kiện cần và đủ là các cột của dữ liệu $A$ phải độc lập tuyến tính (ma trận $A$ đủ hạng cột: $\mathrm{rank}(A)=n$). Khi đó, nghiệm cực tiểu toàn cục được bảo đảm là duy nhất.

4.2. Phần bù Schur (Schur Complement)

Xét một khối đối xứng kích thước $(p+q)\times (p+q)$:

$$M=\left[\begin{array}{cc}A& B\\ B^T& C\end{array}\right],$$

trong đó $A\in {\mathbb{S}}^p$, $C\in {\mathbb{S}}^q$, và $B\in {\mathbb{R}}^{p\times q}$. Giả sử khối con $A$ khả nghịch ($A\succ 0$).

phần bù Schur của $A$ trong $M$ được định nghĩa là:

$$S=C-B^T{A}^{-1}B.$$

Bổ đề Phần bù Schur:

1. khối $M$ dương xác định ($M\succ 0$) khi và chỉ khi:
   $$A\succ 0,C-B^T{A}^{-1}B\succ 0.$$
2. Nếu $A\succ 0$, khối $M$ ($M⪰0$) khi và chỉ khi:
   $$C-B^T{A}^{-1}B⪰0.$$

Ý nghĩa và Ứng dụng trong AI:

• Khử biến toàn phương: Cực tiểu hóa dạng toàn phương theo biến $x$ trong biểu thức ${\left[\begin{array}{c}x\\ y\end{array}\right]}^T\left[\begin{array}{cc}A& B\\ B^T& C\end{array}\right]\left[\begin{array}{c}x\\ y\end{array}\right]$ cho ra đúng dạng toàn phương thu gọn theo biến $y$: $y^T(C-B^T{A}^{-1}B)y$.
• có điều kiện: Nếu ghép $(X,Y)$ tuân theo phân phối Gauss với khối, ma trận hiệp phương sai của phân phối có điều kiện $Y\mid X$ chính là phần bù Schur của khối $X$.
• Chuyển đổi bất đẳng thức tuyến tính (LMI): Phần bù Schur cho phép biến đổi các ràng buộc phi tuyến lồi (như $x^{T}Px\le t$) thành bất đẳng thức ma trận tuyến tính chuẩn tắc trong Quy hoạch nửa xác định (SDP).

---

5. Phân tích giá trị kỳ dị (SVD) và Ý nghĩa hình học

Mọi thực $A\in {\mathbb{R}}^{m\times n}$ đều có thể phân tích thành tích của ba ma trận:

$$A=U\mathrm{\Sigma }{V}^T,$$

trong đó:

• $U\in {\mathbb{R}}^{m\times m}$ là trực giao ($U^{T}U=I_m$), các cột của $U$ là các kỳ dị trái (left singular vectors).
• $V\in {\mathbb{R}}^{n\times n}$ là trực giao ($V^{T}V=I_n$), các cột của $V$ là các kỳ dị phải (right singular vectors).
• $\mathrm{\Sigma }\in {\mathbb{R}}^{m\times n}$ là đường chéo chữ nhật chứa các giá trị kỳ dị được xếp theo thứ tự giảm dần:
  $${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_r>0={\sigma }_{r+1}=\cdots =0,$$
  với $r=\mathrm{rank}(A)$ là hạng của .

5.1. Ý nghĩa hình học của SVD

Phép nhân $x\mapsto Ax$ có thể phân rã thành ba bước hình học cơ bản:

1. Phép quay/phản xạ trong không gian gốc ${\mathbb{R}}^n$: Nhân với trực giao $V^T$, chuyển hệ tọa độ sang các trục trực chuẩn $v_i$.
2. Phép co giãn dọc theo các trục tọa độ: Nhân với đường chéo $\mathrm{\Sigma }$, kéo dãn theo từng trục với hệ số co giãn đúng bằng các giá trị kỳ dị ${\sigma }_i$.
3. Phép quay/phản xạ trong không gian đích ${\mathbb{R}}^m$: Nhân với trực giao $U$, đưa các trục đã co giãn về hướng của các trực chuẩn $u_i$.

Hệ quả hình học: $A$ biến đổi quả cầu đơn vị $\parallel x{\parallel }_2\le 1$ trong ${\mathbb{R}}^n$ thành một khối ellipsoid trong ${\mathbb{R}}^m$, với độ dài các bán trục chính đúng bằng các giá trị kỳ dị ${\sigma }_i$ và các trục đối xứng có phương trùng với các $u_i$.

5.2. Số điều kiện của ma trận (Condition Number)

Số điều kiện của khả nghịch $A\in {\mathbb{R}}^{n\times n}$ được định nghĩa là tỷ số giữa giá trị kỳ dị lớn nhất và nhỏ nhất:

$$\kappa (A)=\frac{{\sigma }_{max}(A)}{{\sigma }_{min}(A)}=\frac{{\sigma }_1}{{\sigma }_n}\ge 1.$$

Ý nghĩa thực tiễn:

• Nếu $\kappa (A)\approx 1$: có điều hòa tốt (well-conditioned). Địa hình hàm mất mát gần như hình tròn đồng mức, thuật toán gradient descent hội tụ rất nhanh.
• Nếu $\kappa (A)\gg 1$: có điều hòa xấu (ill-conditioned). Địa hình mất mát là một thung lũng hẹp và dài (khe núi sâu), gradient descent sẽ dao động zig-zag dữ dội và hội tụ rất chậm.

---

6. Đại số tuyến tính số trong Tối ưu hóa (Numerical Linear Algebra)

Khi triển khai các thuật toán tối ưu hóa trong thực tế, việc hiểu rõ chi phí tính toán và tính ổn định số học của các thuật toán đại số tuyến tính là kỹ năng phân biệt giữa một người làm lý thuyết thuần túy và một kỹ sư tính toán thực thụ.

6.1. Đơn vị đo độ phức tạp: Flop

Một flop (floating-point operation) là một phép tính số thực dấu phẩy động cơ bản gồm một phép cộng, trừ, nhân, hoặc chia.

Chi phí tính toán của các thao tác đại số cơ bản:

• của hai $x,y\in {\mathbb{R}}^n$: Tiêu tốn $2n$ flops (bao gồm $n$ phép nhân và $n-1$ phép cộng).
• Nhân với $Ax$ với $A\in {\mathbb{R}}^{m\times n}$: Tiêu tốn $2mn$ flops.
• Nhân hai $AB$ với $A\in {\mathbb{R}}^{m\times p}$ và $B\in {\mathbb{R}}^{p\times n}$: Tiêu tốn $2mpn$ flops.

6.2. Giải hệ phương trình ma trận tam giác

Hệ phương trình có hệ số là ma trận tam giác (dưới hoặc trên) là khối cấu trúc cơ bản nhất của mọi thuật toán đại số tuyến tính số học:

1. Thế tiến (Forward substitution) cho hệ tam giác dưới $Ly=b$ (với $L_{ii}\ne 0$):
   $$$$

y_1 &= \frac{b_1}{L_{11}}, \ y_i &= \frac{1}{L_{ii}} \left( b_i - \sum_{j=1}^{i-1} L_{ij} y_j \right), \quad i = 2, \dots, n. \end

$$\text{Số phép tính cần thực hiện là \$sum\_{i=1}^n (2i - 1) = n^2\$ flops. 2. **Thế lùi (Back substitution)** cho hệ tam giác trên \$U x = y\$: Hoàn toàn tương tự, giải từ \$x\_n\$ ngược lên \$x\_1\$ với chi phí đúng \$n^2\$ flops. \#\#\# 6.3. Phân tích LU cho ma trận vuông tổng quát Với một ma trận vuông tổng quát không suy biến \$A in mathbb{R}^{n times n}\$, phép khử Gauss với chiến lược chọn phần tử trục (pivoting) phân tích ma trận thành dạng:}$$

A = P L U,

$$\text{trong đó \$P\$ là ma trận hoán vị các hàng, \$L\$ là ma trận tam giác dưới với các số 1 trên đường chéo chính, và \$U\$ là ma trận tam giác trên không suy biến. - Chi phí phân tích ma trận: Đạt \$frac{2}{3} n^3\$ flops. - Chi phí giải hệ \$A x = b\$: Sau khi đã có \$P, L, U\$, ta áp dụng hoán vị vector \$P^T b\$, giải thế tiến \$L y = P^T b\$ (\$n^2\$ flops) và giải thế lùi \$U x = y\$ (\$n^2\$ flops). Tổng chi phí giải sau khi phân tích chỉ là \$2n^2\$ flops. \#\#\# 6.4. Phân tích Cholesky: Cỗ máy giải hệ đối xứng xác định dương Để giải hệ phương trình tuyến tính đối xứng xác định dương \$H x = b\$ (xuất hiện trong mọi bước lặp của phương pháp Newton và bài toán bình phương tối thiểu), ta không bao giờ tính ma trận nghịch đảo \$H^{-1}\$ một cách trực tiếp vì thao tác này vừa chậm vừa dễ tích lũy sai số số học. Thay vào đó, ta sử dụng **Phân tích Cholesky**: Mọi ma trận đối xứng dương xác định \$H in mathbb{S}\_{++}^n\$ đều có thể phân tích duy nhất thành dạng:}$$

H = L L^T,

$$trongđó\$L\$làmatrậntamgiácdướivớicácphầntửtrênđườngchéochínhdươngngặt(\$L_{ii}>0\$).Quytrìnhgiảihệ\$Hx=b\$quaphântíchCholeskygồmbabước:1.\ast \ast PhântíchCholesky\ast \ast :Tìmmatrậntamgiácdưới\$L\$thỏamãn\$H=L{L}^T\$.Chiphítínhtoánlà:$$

\frac{1}{3} n^3 \text{ flops}.

$$\text{2. **Thế tiến (Forward substitution)**: Giải hệ tam giác dưới \$L y = b\$. Chi phí là \$n^2\$ flops. 3. **Thế lùi (Back substitution)**: Giải hệ tam giác trên \$L^T x = y\$. Chi phí là \$n^2\$ flops. Tổng chi phí để giải hệ là \$frac{1}{3} n^3 + 2n^2 approx frac{1}{3} n^3\$ flops. Phân tích Cholesky nhanh gấp đôi phân tích LU tổng quát (\$frac{2}{3} n^3\$ flops), tiết kiệm một nửa bộ nhớ lưu trữ vì chỉ cần lưu nửa tam giác dưới, và có độ ổn định số học tối ưu mà không cần bất kỳ hoán vị hàng nào. \#\#\# 6.5. Phân tích \$LDL^T\$ cho ma trận đối xứng không xác định dấu Trong các bài toán tối ưu có ràng buộc đẳng thức, ma trận hệ KKT có dạng:}$$

K = \begin{bmatrix} H & A^T \ A & 0 \end{bmatrix}.

$$Matrận\$K\$đốixứngnhưngkhôngxácđịnhdương(nóluôncócảgiátrịriêngdươngvàgiátrịriêngâm,tạothànhđiểmyênngựa).TakhôngthểdùngphântíchCholeskytrựctiếpcho\$K\$.Giảipháptốiưusốhọclà\ast \ast Phântích\$LD{L}^T\$vớimatrậnhoánvị\ast \ast :$$

K = P L D L^T P^T,

$$\text{trong đó \$P\$ là ma trận hoán vị, \$L\$ là ma trận tam giác dưới với đường chéo gồm các số 1, và \$D\$ là ma trận đường chéo khối gồm các khối con kích thước \$1 times 1\$ và \$2 times 2\$. - Thuật toán Bunch–Kaufman tự động chọn các khối \$1 times 1\$ hoặc \$2 times 2\$ trên đường chéo để bảo đảm độ ổn định số học mà vẫn duy trì tính đối xứng. - Chi phí phân tích: Đúng \$frac{1}{3} n^3\$ flops, bằng một nửa chi phí phân tích LU tổng quát. \#\#\# 6.6. Khử ma trận khối (Block Elimination) và Phần bù Schur Xét hệ phương trình tuyến tính cấu trúc khối:}$$

\begin{bmatrix} A_{11} & A_{12} \ A_{21} & A_{22} \end{bmatrix} \begin{bmatrix} x_1 \ x_2 \end{bmatrix} = \begin{bmatrix} b_1 \ b_2 \end{bmatrix},

$$trongđó\$A_{11}\in {\mathbb{R}}^{n_1\times n_1}\$làmatrậnkhôngsuybiến.Tacóthểkhửbiến\$x_1\$từphươngtrìnhthứnhất:$$

x_1 = A_{11}^{-1} (b_1 - A_{12} x_2).

$$Thaybiểuthứcnàyvàophươngtrìnhthứhai:$$

A_{21} A_{11}^{-1} (b_1 - A_{12} x_2) + A_{22} x_2 = b_2,

$$dẫnđếnhệphươngtrìnhrútgọntheoriêngbiến\$x_2\$:$$

S x_2 = b_2 - A_{21} A_{11}^{-1} b_1,

$$\text{trong đó \$S = A\_{22} - A\_{21} A\_{11}^{-1} A\_{12}\$ chính là **Phần bù Schur** của khối \$A\_{11}\$. Quy trình giải hệ bằng phương pháp khử khối: 1. Giải \$A\_{11} hat{x}\_1 = b\_1\$ và giải \$A\_{11} Z = A\_{12}\$ (gồm \$n\_2\$ hệ phương trình với cùng ma trận hệ số \$A\_{11}\$). 2. Tính phần bù Schur \$S = A\_{22} - A\_{21} Z\$ và vế phải \$tilde{b}\_2 = b\_2 - A\_{21} hat{x}\_1\$. 3. Giải hệ phương trình kích thước nhỏ \$S x\_2 = tilde{b}\_2\$. 4. Thu hồi nghiệm \$x\_1\$: Giải \$A\_{11} x\_1 = b\_1 - A\_{12} x\_2\$. Phương pháp này rất hiệu quả khi \$n\_2 ll n\_1\$ hoặc khi khối \$A\_{11}\$ có cấu trúc đặc biệt (như ma trận đường chéo, ma trận băng hoặc phân tích Cholesky của nó đã được tính sẵn). \#\#\# 6.7. Công thức cập nhật Sherman–Morrison–Woodbury Khi giải một chuỗi các hệ phương trình tuyến tính mà ma trận hệ số chỉ bị biến đổi bởi một số hạng hạng thấp (low-rank perturbation):}$$

(A + U C V)^{-1} = A^{-1} - A^{-1} U (C^{-1} + V A^{-1} U)^{-1} V A^{-1},

$$ với $A \in \mathbb{R}^{n \times n}$, $U \in \mathbb{R}^{n \times p}$, $C \in \mathbb{R}^{p \times p}$ và $V \in \mathbb{R}^{p \times n}$. - Khi $p \ll n$, thay vì phải tính nghịch đảo ma trận $n \times n$ với chi phí $O(n^3)$, ta chỉ cần nghịch đảo ma trận kích thước nhỏ $p \times p$ với chi phí $O(p^3)$ cộng với các phép nhân ma trận. - Công thức này là nền tảng của bộ lọc Kalman, thuật toán cập nhật Quasi-Newton (BFGS, DFP, SR1), và các mô hình học trực tuyến (Online Learning). ### 6.8. Khai thác Cấu trúc Ma trận Thưa và Ma trận Băng Trong các bài toán học máy quy mô lớn (như đồ thị, bài toán quy hoạch mạng lưới, hay mô hình chuỗi thời gian), ma trận dữ liệu và ma trận Hessian thường chứa phần lớn phần tử bằng 0 (**ma trận thưa - sparse matrix**). Nếu ma trận $H \in \mathbb{R}^{n \times n}$ là ma trận dạng băng (banded matrix) với độ rộng băng $k \ll n$ (chỉ có các phần tử cách đường chéo chính không quá $k$ vị trí là khác 0): - Chi phí phân tích Cholesky giảm từ $O(n^3)$ xuống chỉ còn $O(n k^2)$ flops. - Khi $k$ cố định, độ phức tạp là **tuyến tính $O(n)$** theo số chiều biến. Việc nhận diện và khai thác cấu trúc thưa giúp giảm thời gian giải bài toán từ nhiều ngày xuống vài giây. --- ## 7. Mật độ xác suất và Phân phối chuẩn Gauss Tại sao trong thực tế người ta lại chọn chuẩn bình phương $\|Aw - b\|_2^2$ để tối ưu mà không phải chuẩn bậc 3 hay bậc 4? Để trả lời thấu đáo câu hỏi này, ta cần xem xét bài toán qua lăng kính của lý thuyết xác suất và thống kê. Với một biến ngẫu nhiên liên tục $Z$ có hàm mật độ xác suất $p(z)$, xác suất để $Z$ rơi vào một khoảng $[a, b]$ được tính bằng tích phân của hàm mật độ: $$

P(a \le Z \le b) = \int_a^b p(z) , dz.

$$Lưuýrằnggiátrịhàmmậtđộ\$p(z)\$tạimộtđiểmkhôngphảilàxácsuấtsinhrađúngđiểmđó(đốivớibiếnliêntục,xácsuấttạimộtđiểmđơnlẻluônbằng0).Haiđặctrưngquantrọngcủaphânphốilà\ast \ast kỳvọng\ast \ast \$\mathbb{E}[Z]=\int zp(z)dz\$(trọngtâmphânphối)và\ast \ast phươngsai\ast \ast \$\mathrm{Var}(Z)=\mathbb{E}[(Z-\mathbb{E}[Z]{)}^2]\$(mứcđộphântánquanhtrọngtâm).\ast \ast Phânphốichuẩn(Gauss)\ast \ast mộtbiếnvớikỳvọng\$\mu \$vàphươngsai\${\sigma }^2>0\$cóhàmmậtđộhìnhchuông:$$

p(z) = \frac{1}{\sqrt{2\pi\sigma^2}} \exp\left[ -\frac{(z - \mu)^2}{2\sigma^2} \right].

$$Khimởrộngsangvectorngẫunhiên\$Z\in {\mathbb{R}}^m\$vớivectorkỳvọng\$\mu \in {\mathbb{R}}^m\$vàmatrậnhiệpphươngsaiđốixứngdươngxácđịnh\$\mathrm{\Sigma }\succ 0\$,hàmmậtđộGaussđabiếncódạng:$$

p(z) = \frac{1}{(2\pi)^{m/2} \sqrt{\det\Sigma}} \exp\left[ -\frac{1}{2} (z - \mu)^T \Sigma^{-1} (z - \mu) \right].

$$\text{- Ma trận hiệp phương sai \$Sigma\$ lưu giữ phương sai của từng thành phần trên đường chéo chính (\$Sigma\_{ii} = sigma\_i^2\$) và mức độ tương quan tuyến tính giữa các cặp thành phần ở các vị trí ngoài đường chéo (\$Sigma\_{ij} = operatorname{Cov}(Z\_i, Z\_j)\$). - Định thức \$detSigma\$ phản ánh thể tích của ellipsoid phân tán dữ liệu, đóng vai trò chuẩn hóa diện tích tích phân của hàm mật độ về đúng bằng 1. - Khi các thành phần sai số độc lập thống kê và có cùng phương sai \$sigma^2\$, ma trận hiệp phương sai trở thành ma trận đường chéo \$Sigma = sigma^2 I\_m\$. Lúc này, mật độ đa biến phân rã thành tích của \$m\$ mật độ Gauss độc lập: \$p(z) = prod\_{i=1}^m p(z\_i)\$. --- \#\# 8. Cội nguồn xác suất của Bài toán Bình phương tối thiểu Giờ đây ta có thể nhìn thấy mối liên hệ trực tiếp giữa học máy và xác suất thống kê. Giả sử trong thực tế, quá trình sinh dữ liệu tuân theo mô hình tuyến tính bị làm nhiễu:}$$

b_i = a_i^T w + \varepsilon_i, \qquad \varepsilon_i \overset{\text{i.i.d.}}{\sim} \mathcal{N}(0, \sigma^2).

$$Nghĩalànhãnthựctế\$b_i\$làmộtbiếnngẫunhiêncókỳvọngđúngbằnggiátrịmôhìnhdựđoán\$\mathbb{E}[b_i]=a_i^{T}w\$,vàbịsailệchbởimộtnhiễungẫunhiênGauss\${\epsilon }_i\$khôngthiênvịvớiphươngsai\${\sigma }^2\$.Theomôhìnhnày,mậtđộxácsuấtcóđiềukiệncủanhãn\$b_i\$khibiếtthamsố\$w\$là:$$

p(b_i \mid w) = \frac{1}{\sqrt{2\pi\sigma^2}} \exp\left[ -\frac{(b_i - a_i^T w)^2}{2\sigma^2} \right].

$$Vìcácquansátđộclậpvớinhau,xácsuấtđồngthời(hàm\ast \ast Likelihood\ast \ast ,tứchàmhợplý)củatoànbộtậpdữliệu\$b=(b_1,\dots ,b_m{)}^T\$bằngtíchcácmậtđộthànhphần:$$

\begin{aligned} L(w) &= p(b \mid w) = \prod_{i=1}^m p(b_i \mid w) \ &= \left( \frac{1}{2\pi\sigma^2} \right)^{m/2} \exp\left[ -\frac{1}{2\sigma^2} \sum_{i=1}^m (a_i^T w - b_i)^2 \right]. \end

$$Triếtlýướclượnghợplýcựcđại(\ast \ast MaximumLikelihoodEstimation-MLE\ast \ast ):Tamuốntìmbộthamsố\$w\$saochokhảnăngquansátđượctậpdữliệuhiệncótrongthựctếlàlớnnhất.Đểcựcđạihóamộttíchcáchàmmũ,trongtoántốiưungườitadùngphépbiếnđổilấy\ast \ast âmlogarittựnhiên\ast \ast (NegativeLog-Likelihood-NLL).Dohàmlogaritđơnđiệutăngngặt,việccựcđạihóa\$L(w)\$hoàntoàntươngđươngvớiviệccựctiểuhóa\$-\log L(w)\$:$$

-\log p(b \mid w) = \frac{m}{2} \log(2\pi\sigma^2) + \frac{1}{2\sigma^2} |Aw - b|_2^2.

$$Quansátbiểuthứctrên:-Sốhạngđầutiên\$\frac{m}{2}\log (2\pi {\sigma }^2)\$làmộthằngsốđộclậpvớithamsố\$w\$.-Hệsố\$\frac{1}{2{\sigma }^2}\$làmộtsốdươngcốđịnh.Dođó,bàitoántìmthamsố\$w\$đểcựcđạihóahàmhợplýLikelihoodquyvềchínhxác:$$

\arg\min_w \left[ -\log p(b \mid w) \right] \equiv \arg\min_w \frac{1}{2} |Aw - b|_2^2.

$$Tiêuchuẩnbìnhphươngtốithiểukhôngphảilàmộtcôngthứccảmtínhđượcchọnngẫunhiên.NólàhệquảtoánhọctrựctiếpcủanguyênlýcựcđạihóahàmhợplýdướigiảthiếtsaisốquansáttuântheophânphốichuẩnGaussđộclập.Nếucácsaisốquansátcótươngquanlẫnnhauvớimatrậnhiệpphươngsaitổngquát\$\mathrm{\Sigma }\succ 0\$,biểuthứcNLLsẽdẫntớihàmmấtmátbìnhphươngcótrọngsố:$$

f(w) = \frac{1}{2} (Aw - b)^T \Sigma^{-1} (Aw - b).

$$\text{Mỗi quan sát có phương sai lớn sẽ tự động bị ma trận \$Sigma^{-1}\$ giảm trọng số ảnh hưởng trong hàm mất mát. --- \#\# 9. Hệ thống Bài tập Tự luyện Chuyên sâu ::: warning exercise: Bài tập 1: Kiểm tra tính xác định dương và Phần bù Schur cho ma trận khối Xét ma trận khối đối xứng:}$$

M = \begin{bmatrix} 2 & 1 & 0 \ 1 & 2 & 1 \ 0 & 1 & c \end{bmatrix},

$$trongđó\$c\in \mathbb{R}\$làthamsốthực.1.Hãyphânrãmatrận\$M\$thànhcấutrúckhối\$\left[\begin{array}{cc}A& B\\ B^T& C\end{array}\right]\$vớikhốicon\$A\$kíchthước\$2\times 2\$.2.TínhphầnbùSchur\$S=C-B^T{A}^{-1}B\$.3.SửdụngBổđềphầnbùSchurđểtìmđiềukiệncầnvàđủcủa\$c\$đểmatrận\$M\$dươngxácđịnh(\$M\succ 0\$).::::::detailsLờigiải\ast \ast Lờigiải\ast \ast :1.Phânrãmatrậnthànhcấutrúckhối:$$

A = \begin{bmatrix} 2 & 1 \ 1 & 2 \end{bmatrix}, \qquad B = \begin{bmatrix} 0 \ 1 \end{bmatrix}, \qquad C = [c].

$$Khốicon\$A\$đốixứng,cóđịnhthức\$det(A)=2(2)-1(1)=3>0\$vàphầntửgóc\$A_{11}=2>0\$,dođó\$A\succ 0\$.2.Tínhmatrậnnghịchđảocủa\$A\$:$$

A^{-1} = \frac{1}{3} \begin{bmatrix} 2 & -1 \ -1 & 2 \end{bmatrix}.

$$Tínhtích\$B^T{A}^{-1}B\$:$$

B^T A^{-1} B = \begin{bmatrix} 0 & 1 \end{bmatrix} \left( \frac{1}{3} \begin{bmatrix} 2 & -1 \ -1 & 2 \end{bmatrix} \right) \begin{bmatrix} 0 \ 1 \end{bmatrix} = \frac{1}{3} \begin{bmatrix} -1 & 2 \end{bmatrix} \begin{bmatrix} 0 \ 1 \end{bmatrix} = \frac{2}{3}.

$$PhầnbùSchurlà:$$

S = C - B^T A^{-1} B = c - \frac{2}{3}.

$$3.TheoBổđềphầnbùSchur,vì\$A\succ 0\$,matrậnkhối\$M\succ 0\$khivàchỉkhi\$S>0\$:$$

c - \frac{2}{3} > 0 \iff c > \frac{2}{3}.

$$Nhưvậy,điềukiệncầnvàđủđểmatrận\$M\$dươngxácđịnhlà\$c>\frac{2}{3}\$.::::::warningexercise:Bàitập2:ThựchiệnphântíchCholeskyvàGiảihệphươngtrìnhchuẩntắcChomatrậnđốixứngdươngxácđịnh:$$

H = \begin{bmatrix} 4 & 2 \ 2 & 10 \end{bmatrix}, \qquad b = \begin{bmatrix} 8 \ 16 \end{bmatrix}.

$$1.Hãytìmmatrậntamgiácdưới\$L=\left[\begin{array}{cc}{l}_{11}& 0\\ l_{21}& l_{22}\end{array}\right]\$trongphântíchCholesky\$H=L{L}^T\$.2.Ápdụngphươngphápthếtiếnvàthếlùiđểgiảihệphươngtrình\$Hx=b\$.::::::detailsLờigiải\ast \ast Lờigiải\ast \ast :1.Khaitriểntích\$L{L}^T\$:$$

L L^T = \begin{bmatrix} l_{11} & 0 \ l_{21} & l_{22} \end{bmatrix} \begin{bmatrix} l_{11} & l_{21} \ 0 & l_{22} \end{bmatrix} = \begin{bmatrix} l_{11}^2 & l_{11} l_{21} \ l_{11} l_{21} & l_{21}^2 + l_{22}^2 \end{bmatrix}.

$$Đồngnhấtcácphầntửvớimatrận\$H\$:-\$l_{11}^2=4⟹l_{11}=2\$(chọnphầntửđườngchéodương).-\$l_{11}{l}_{21}=2⟹2l_{21}=2⟹l_{21}=1\$.-\$l_{21}^2+l_{22}^2=10⟹l_{22}^2=9\$,suyra\$l_{22}=3\$.Dođó,matrậnCholeskylà:$$

L = \begin{bmatrix} 2 & 0 \ 1 & 3 \end{bmatrix}.

$$2.Giảihệphươngtrình\$Hx=b\$quahaibước:-\ast \ast Bước1(Thếtiến\$Ly=b\$)\ast \ast :$$

 \begin{bmatrix} 2 & 0 \\ 1 & 3 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \end{bmatrix} = \begin{bmatrix} 8 \\ 16 \end{bmatrix} \implies \begin{cases} 2 y_1 = 8 \implies y_1 = 4, \\ 1(4) + 3 y_2 = 16 \implies 3 y_2 = 12 \implies y_2 = 4. \end{cases}
 $$
 Suy ra $y = \begin{bmatrix} 4 \\ 4 \end{bmatrix}$.

• Bước 2 (Thế lùi $L^{T}x=y$):
  $$\left[\begin{array}{cc}2& 1\\ 0& 3\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]=\left[\begin{array}{c}4\\ 4\end{array}\right]⟹\{\begin{array}{l}3x_2=4⟹x_2=\frac{4}{3},\\ 2x_1+\frac{4}{3}=4⟹2x_1=\frac{8}{3}⟹x_1=\frac{4}{3}.\end{array}$$
  Nghiệm duy nhất của hệ là $x=\left[\begin{array}{c}4/3\\ 4/3\end{array}\right]$. :::

Bài tập 3: Phân tích SVD và Độ co giãn của ma trận dữ liệu

Cho $A=\left[\begin{array}{cc}3& 0\\ 0& -2\end{array}\right]$.

1. Hãy xác định các giá trị kỳ dị ${\sigma }_1,{\sigma }_2$ và số điều kiện $\kappa (A)$.
2. Mô tả hình học ảnh của quả cầu đơn vị $\parallel x{\parallel }_2\le 1$ qua ánh xạ $A$.

Lời giải

Lời giải:

1. Xét $A^{T}A=\left[\begin{array}{cc}9& 0\\ 0& 4\end{array}\right]$. Các giá trị riêng của $A^{T}A$ là ${\lambda }_1=9$ và ${\lambda }_2=4$. Các giá trị kỳ dị của $A$ là căn bậc hai của các giá trị riêng này:

   $${\sigma }_1=\sqrt{9}=3,{\sigma }_2=\sqrt{4}=2.$$

   Số điều kiện của là:

   $$\kappa (A)=\frac{{\sigma }_1}{{\sigma }_2}=\frac{3}{2}=1.5.$$

2. Xét điểm $x=(x_1,x_2{)}^T$ nằm trên biên của quả cầu đơn vị: $x_1^2+x_2^2=1$. Ảnh của $x$ qua ánh xạ $A$ là $y=Ax=(3x_1,-2x_2{)}^T$. Đặt $y_1=3x_1⟹x_1=y_1/3$ và $y_2=-2x_2⟹x_2=-y_2/2$. Thay vào phương trình quả cầu đơn vị:

   $${\left(\frac{y_1}{3}\right)}^2+{(-\frac{y_2}{2})}^2=1⟺\frac{y_1^2}{3^2}+\frac{y_2^2}{2^2}=1.$$

   Đây chính là phương trình của một hình ellipse trong mặt phẳng với bán trục lớn bằng ${\sigma }_1=3$ dọc theo trục hoành và bán trục nhỏ bằng ${\sigma }_2=2$ dọc theo trục tung. Ánh xạ $A$ đã kéo giãn quả cầu tròn thành một khối ellipse có kích thước đúng bằng các giá trị kỳ dị.

Bài tập 4: So sánh chi phí Flops và Thuật toán Khử khối Schur cho Hệ KKT

Xét hệ phương trình Newton–KKT xuất hiện trong tối ưu hóa có ràng buộc đẳng thức:

$$\left[\begin{array}{cc}H& A^T\\ A& 0\end{array}\right]\left[\begin{array}{c}v\\ w\end{array}\right]=-\left[\begin{array}{c}g\\ h\end{array}\right],$$

trong đó $H\in {\mathbb{S}}_{++}^n$ đối xứng xác định dương và $A\in {\mathbb{R}}^{p\times n}$ có đủ hạng hàng ($p\le n$).

1. Trình bày chi tiết thuật toán khử khối bằng phần bù Schur để tìm nghiệm $(v,w)$.
2. Phân tích chi phí tính toán (số flops) khi giải hệ theo phương pháp khử khối:
   • Phân tích Cholesky $H=L{L}^T$.
   • Tính phần bù Schur $S=-A{H}^{-1}{A}^T$ thông qua giải $p$ hệ tam giác.
   • Giải hệ phương trình theo biến đối ngẫu $w$ và thu hồi nghiệm nguyên thủy $v$.
3. So sánh chi phí này với phương pháp giải trực tiếp bằng phân tích $LD{L}^T$ trên toàn bộ kích thước $(n+p)\times (n+p)$ khi số ràng buộc nhỏ hơn rất nhiều số chiều biến ($p\ll n$).

Lời giải

Lời giải:

1. Thuật toán khử khối Schur:

   • Từ phương trình thứ nhất, biểu diễn $v$ theo $w$:
     $$Hv+A^{T}w=-g⟹v=-H^{-1}g-H^{-1}{A}^{T}w.$$
   • Thế biểu thức của $v$ vào phương trình thứ hai $Av=-h$:
     $$A(-H^{-1}g-H^{-1}{A}^{T}w)=-h⟺(A{H}^{-1}{A}^T)w=h-A{H}^{-1}g.$$
   • Đặt $M=A{H}^{-1}{A}^T=-S$. Vì $H\succ 0$ và $A$ đủ hạng hàng, $M\in {\mathbb{S}}_{++}^p$ đối xứng dương xác định.
   • Sau khi giải tìm được $w$, ta thu hồi $v$ từ phương trình: $Hv=-(g+A^{T}w)$.

2. Phân tích chi phí Flops theo từng công đoạn:

   • Phân tích Cholesky $H=L{L}^T$: Tốn $\frac{1}{3}{n}^3$ flops.
   • Tính $H^{-1}{A}^T$: Giải $p$ hệ phương trình $HZ=A^T$ (với $Z=H^{-1}{A}^T\in {\mathbb{R}}^{n\times p}$) bằng hai lần thế tam giác qua $L$ và $L^T$. Mỗi cột tốn $2n^2$ flops, tổng cộng tốn $2p{n}^2$ flops.
   • Tính tích $M=AZ=A{H}^{-1}{A}^T$: Nhân ma trận $p\times n$ với ma trận $n\times p$, tận dụng tính đối xứng chỉ cần tính nửa tam giác, tốn khoảng $p^{2}n$ flops.
   • Phân tích Cholesky kích thước nhỏ $M$ ($p\times p$): Tốn $\frac{1}{3}{p}^3$ flops.
   • Giải tìm $w$ và thu hồi $v$: Tốn thêm $2p^2+2n^2$ flops (các số hạng bậc hai nhỏ).
   • Tổng chi phí chủ đạo của phương pháp khử khối là:
     $$\frac{1}{3}{n}^3+2p{n}^2+p^{2}n+\frac{1}{3}{p}^3\text{ flops}.$$

3. So sánh hiệu năng:

   • Nếu giải trực tiếp toàn bộ hệ kích thước $(n+p)\times (n+p)$ bằng phân tích $LD{L}^T$, chi phí tính toán là:
     $$\frac{1}{3}(n+p{)}^3=\frac{1}{3}{n}^3+p{n}^2+p^{2}n+\frac{1}{3}{p}^3\text{ flops}.$$
   • Khi $p\ll n$ (số ràng buộc đẳng thức rất ít so với số chiều biến tối ưu, chẳng hạn $n=10000,p=10$): Chi phí của cả hai phương pháp đều bị chi phối bởi số hạng $\frac{1}{3}{n}^3$ flops của phân tích . Tuy nhiên, phương pháp khử khối cho phép tận dụng trực tiếp tính xác định dương của $H$ để chạy thuật toán Cholesky nhanh nhất và ổn định nhất, không cần theo dõi chiến lược chọn trục (pivoting) phức tạp của $LD{L}^T$.
   • Đặc biệt, nếu $H$ có cấu trúc thưa hoặc đường chéo (như trong phương pháp điểm trong), việc tính $H^{-1}{A}^T$ chỉ tốn $O(pn)$ flops thay vì $2p{n}^2$, đưa tổng chi phí của phương pháp khử khối xuống chỉ còn $O(n)+O(p^3)$ flops, nhanh hơn hàng trăm lần so với giải hệ đầy đủ!

---

7. Các chủ đề chuyên khảo về Giải tích Ma trận và Hệ thiếu xác định

Để nghiên cứu sâu hơn về không gian nghiệm của các hệ phương trình thiếu xác định ($m<n$), nghiệm chuẩn nhỏ nhất và các bổ đề giải tích vi phân nâng cao trong học máy, người học có thể đào sâu qua chuyên đề độc lập dưới đây:

1 chủ đề · tổng cộng khoảng 7 phút đọc

I. Hệ phương trình và giải tích ma trận

Giải hệ thiếu xác định, bổ đề Woodbury và vi phân hàm ma trận trong học máy.

1. 1Hệ Tuyến Tính Thiếu Xác Định và Giải Tích Ma TrậnTrong vô số nghiệm của hệ thiếu xác định, nghiệm nào có chuẩn nhỏ nhất và tính thưa cao nhất?Khoảng 7 phút

---

Tóm tắt cốt lõi

1. Biểu diễn : Gom dữ liệu thành ma trận $A\in {\mathbb{R}}^{m\times n}$ giúp tính toán đồng thời mọi dự đoán $Aw$ và phần dư $r=Aw-b$, khai phóng sức mạnh xử lý song song của GPU.
2. Gradient và Hướng dốc nhất: Gradient của hàm mất mát tổng bình phương là $\mathrm{\nabla }f(w)=A^T(Aw-b)$. Hướng $-\mathrm{\nabla }f(w)$ là kim chỉ nam hạ thấp mất mát trong thuật toán Gradient Descent.
3. và Độ cong địa hình: bậc hai $H=A^{T}A$ luôn ($H⪰0$), bảo đảm địa hình tối ưu luôn là một mặt lồi paraboloid. Khi $A$ đủ hạng cột, nghiệm cực tiểu là duy nhất.
4. Phần bù Schur: Công cụ kiểm tra tính xác định dương của khối, khử biến trong dạng toàn phương và giải hệ phương trình tuyến tính cấu trúc khối lớn.
5. Phân tích SVD và Số điều kiện: SVD giải mã cấu trúc hình học của qua tích phân rã $U\mathrm{\Sigma }{V}^T$. Tỷ số $\kappa (A)={\sigma }_{max}/{\sigma }_{min}$ đo lường độ méo mó của địa hình tối ưu.
6. Đại số tuyến tính số: Phân tích Cholesky ($H=L{L}^T$) tốn $\frac{1}{3}{n}^3$ flops là tiêu chuẩn vàng cho xác định dương. Ma trận đối xứng không xác định dùng $LD{L}^T$, và các hệ phương trình khối KKT lớn được tối ưu hóa vượt bậc qua kỹ thuật khử khối Schur.
7. Cội nguồn xác suất: Tiêu chuẩn là hệ quả toán học trực tiếp của nguyên lý Cực đại hóa hợp lý (MLE) khi sai số tuân theo Gauss độc lập.

---

Tài liệu tham khảo

• Stephen Boyd, Lieven Vandenberghe, Convex Optimization, Cambridge University Press. Đọc kỹ Phụ lục A (Đại số tuyến tính, hình học giải tích và vi phân ) và Phụ lục C (Đại số tuyến tính số, phân tích Cholesky, cấu trúc ma trận thưa).
• Gene H. Golub, Charles F. Van Loan, Computations, Johns Hopkins University Press.
• Gilbert Strang, Linear Algebra and Learning from Data, Wellesley-Cambridge Press.

Tiếp theo: Bài 01: Nhập môn tối ưu hóa, Tập lồi và Hàm lồi.