CS 229 - Học máy

Đại số tuyến tính và Giải tích cơ bản
Star

Bởi Afshine Amidi và Shervine Amidi


Dịch bởi Hoàng Minh Tuấn và Phạm Hồng Vinh

Kí hiệu chung

Định nghĩa

Vectơ Chúng ta kí hiệu $x\in\mathbb{R}^n$ là một vectơ với $n$ phần tử, với $x_i\in\mathbb{R}$ là phần tử thứ $i$:

\[x=\left(\begin{array}{c}x_1\\x_2\\\vdots\\x_n\end{array}\right)\in\mathbb{R}^n\]

Ma trận Kí hiệu $A\in\mathbb{R}^{m\times n}$ là một ma trận với $m$ hàng và $n$ cột, $A_{i,j}\in\mathbb{R}$ là phần tử nằm ở hàng thứ $i$, cột $j$:

\[A=\left(\begin{array}{ccc}A_{1,1}& \cdots&A_{1,n}\\\vdots&& \vdots\\A_{m,1}& \cdots&A_{m,n}\end{array}\right)\in\mathbb{R}^{m\times n}\]

Ghi chú: vectơ $x$ được xác định ở trên có thể coi như một ma trận $n\times1$ và được gọi là vectơ cột.


Ma trận chính

Ma trận đơn vị Ma trận đơn vị $I\in\mathbb{R}^{n\times n}$ là một ma trận vuông với các phần tử trên đường chéo chính bằng 1 và các phần tử còn lại bằng 0:

\[I=\left(\begin{array}{cccc}1&0& \cdots&0\\0& \ddots& \ddots& \vdots\\\vdots& \ddots& \ddots&0\\0& \cdots&0&1\end{array}\right)\]

Ghi chú: với mọi ma trận vuông $A\in\mathbb{R}^{n\times n}$, ta có $A\times I=I\times A=A$.


Ma trận đường chéo Ma trận đường chéo $D\in\mathbb{R}^{n\times n}$ là một ma trận vuông với các phần tử trên đường chéo chính khác 0 và các phần tử còn lại bằng 0:

\[D=\left(\begin{array}{cccc}d_1&0& \cdots&0\\0& \ddots& \ddots& \vdots\\\vdots& \ddots& \ddots&0\\0& \cdots&0&d_n\end{array}\right)\]

Ghi chú: chúng ta kí hiệu $D$ là $\textrm{diag}(d_1,...,d_n)$.


Các phép toán ma trận

Phép nhân

Vectơ/vectơ Có hai loại phép nhân vectơ/vectơ:

- phép nhân inner: với $x,y\in\mathbb{R}^n$, ta có:

\[\boxed{x^Ty=\sum_{i=1}^nx_iy_i\in\mathbb{R}}\]

- phép nhân outer: với $x\in\mathbb{R}^m, y\in\mathbb{R}^n$, ta có:

\[\boxed{xy^T=\left(\begin{array}{ccc}x_1y_1& \cdots&x_1y_n\\\vdots&& \vdots\\x_my_1& \cdots&x_my_n\end{array}\right)\in\mathbb{R}^{m\times n}}\]

Ma trận/vectơ Phép nhân giữa ma trận $A\in\mathbb{R}^{m\times n}$ và vectơ $x\in\mathbb{R}^{n}$ là một vectơ có kích thước $\mathbb{R}^{m}$:

\[\boxed{Ax=\left(\begin{array}{c}a_{r,1}^Tx\\\vdots\\a_{r,m}^Tx\end{array}\right)=\sum_{i=1}^na_{c,i}x_{i}\in\mathbb{R}^{m}}\]

với $a_{r,i}^T$ là các vectơ hàng và $a_{c,j}$ là các vectơ cột của $A$, và $x_i$ là các phần tử của $x$.


Ma trận/ma trận Phép nhân giữa ma trận $A\in\mathbb{R}^{m\times n}$ và $B\in\mathbb{R}^{n\times p}$ là một ma trận kích thước $\mathbb{R}^{m\times p}$:

\[\boxed{AB=\left(\begin{array}{ccc}a_{r,1}^Tb_{c,1}& \cdots&a_{r,1}^Tb_{c,p}\\\vdots&& \vdots\\a_{r,m}^Tb_{c,1}& \cdots&a_{r,m}^Tb_{c,p}\end{array}\right)=\sum_{i=1}^na_{c,i}b_{r,i}^T\in\mathbb{R}^{n\times p}}\]

với $a_{r,i}^T, b_{r,i}^T$ là các vectơ hàng và $a_{c,j}, b_{c,j}$ lần lượt là các vectơ cột của $A$ và $B$.


Một số phép toán khác

Chuyển vị Chuyển vị của một ma trận $A\in\mathbb{R}^{m\times n}$, kí hiệu $A^T$, khi các phần tử hàng cột hoán đổi vị trí cho nhau:

\[\boxed{\forall i,j,\quad\quad A_{i,j}^T=A_{j,i}}\]

Ghi chú: với ma trận $A$,$B$, ta có $(AB)^T=B^TA^T$


Nghịch đảo Nghịch đảo của ma trận vuông khả đảo $A$ được kí hiệu là $A-1$ và chỉ tồn tại duy nhất:

\[\boxed{AA^{-1}=A^{-1}A=I}\]

Ghi chú: không phải tất cả các ma trận vuông đều khả đảo. Ngoài ra, với ma trận $A$,$B$, ta có $(AB)^{-1}=B^{-1}A^{-1}$


Truy vết Truy vết của ma trận vuông $A$, kí hiệu $\textrm{tr}(A)$, là tổng của các phần tử trên đường chéo chính của nó:

\[\boxed{\textrm{tr}(A)=\sum_{i=1}^nA_{i,i}}\]

Ghi chú: với ma trận $A$,$B$, chúng ta có $\textrm{tr}(A^T)=\textrm{tr}(A)$ và $\textrm{tr}(AB)=\textrm{tr}(BA)$


Định thức Định thức của một ma trận vuông $A\in\mathbb{R}^{n\times n}$, kí hiệu $|A|$ hay $\textrm{det}(A)$ được tính đệ quy với $A_{\backslash i, \backslash j}$, ma trận $A$ xóa đi hàng thứ $i$ và cột thứ $j$:

\[\boxed{\textrm{det}(A)=|A|=\sum_{j=1}^n(-1)^{i+j}A_{i,j}|A_{\backslash i,\backslash j}|}\]

Ghi chú: $A$ khả đảo nếu và chỉ nếu $|A|\neq0$. Ngoài ra, $|AB|=|A||B|$ và $|A^T|=|A|$.


Những tính chất của ma trận

Định nghĩa

Phân rã đối xứng Một ma trận $A$ đã cho có thể được biểu diễn dưới dạng các phần đối xứng và phản đối xứng của nó như sau:

\[\boxed{A=\underbrace{\frac{A+A^T}{2}}_{\textrm{Symmetric}}+\underbrace{\frac{A-A^T}{2}}_{\textrm{Antisymmetric}}}\]

Chuẩn Một chuẩn (norm) là một hàm $N:V\longrightarrow[0,+\infty[$ mà $V$ là một không gian vectơ, và với mọi $x,y\in V$, ta có:

- $N(x+y)\leqslant N(x)+N(y)$
- $N(ax)=|a|N(x)$ với $a$ là một số
- nếu $N(x)=0$, thì $x=0$

Với $x\in V$, các chuẩn thường dùng được tổng hợp ở bảng dưới đây:

Chuẩn Kí hiệu Định nghĩa Trường hợp dùng
Manhattan, $L^1$ $||x||_1$ $\displaystyle\sum_{i=1}^n|x_i|$ LASSO regularization
Euclidean, $L^2$ $||x||_2$ $\displaystyle\sqrt{\sum_{i=1}^nx_i^2}$ Ridge regularization
$p$-norm, $L^p$ $||x||_p$ $\displaystyle\left(\sum_{i=1}^nx_i^p\right)^{\frac{1}{p}}$ Hölder inequality
Infinity, $L^{\infty}$ $||x||_{\infty}$ $\underset{i}{\textrm{max }}|x_i|$ Uniform convergence

Sự phụ thuộc tuyến tính - Một tập hợp các vectơ được cho là phụ thuộc tuyến tính nếu một trong các vectơ trong tập hợp có thể được biểu diễn bởi một tổ hợp tuyến tính của các vectơ khác.

Ghi chú: nếu không có vectơ nào có thể được viết theo cách này, thì các vectơ được cho là độc lập tuyến tính


Hạng ma trận (rank) Hạng của một ma trận $A$ kí hiệu $\textrm{rank}(A)$ và là số chiều của không gian vectơ được tạo bởi các cột của nó. Điều này tương đương với số cột độc lập tuyến tính tối đa của $A$.


Ma trận bán xác định dương Ma trận $A\in\mathbb{R}^{n\times n}$ là bán xác định dương (PSD) kí hiệu $A\succeq 0$ nếu chúng ta có:

\[\boxed{A=A^T}\quad\textrm{ và }\quad\boxed{\forall x\in\mathbb{R}^n,\quad x^TAx\geqslant0}\]

Ghi chú: tương tự, một ma trận $A$ được cho là xác định dương và được kí hiệu $A\succ0$, nếu đó là ma trận PSD thỏa mãn cho tất cả các vectơ khác không $x$, $x^TAx>0$.


Giá trị riêng, vectơ riêng Cho ma trận $A\in\mathbb{R}^{n\times n}$, $\lambda$ được gọi là giá trị riêng của $A$ nếu tồn tại một vectơ $z\in\mathbb{R}^n\backslash\{0\}$, được gọi là vectơ riêng, sao cho:

\[\boxed{Az=\lambda z}\]

Định lý phổ Cho $A\in\mathbb{R}^{n\times n}$. Nếu $A$ đối xứng, thì $A$ có thể chéo hóa bởi một ma trận trực giao thực $U\in\mathbb{R}^{n\times n}$. Bằng cách kí hiệu $\Lambda=\textrm{diag}(\lambda_1,...,\lambda_n)$, chúng ta có:

\[\boxed{\exists\Lambda\textrm{ đường chéo},\quad A=U\Lambda U^T}\]

Phân tích giá trị suy biến Đối với một ma trận $A$ có kích thước $m\times n$, Phân tích giá trị suy biến (SVD) là một kỹ thuật phân tích nhân tố nhằm đảm bảo sự tồn tại của đơn vị $U$ $m\times m$, đường chéo $\Sigma$m×n và đơn vị $V$ $n\times n$ ma trận, sao cho:

\[\boxed{A=U\Sigma V^T}\]

Giải tích ma trận

Gradien Cho $f:\mathbb{R}^{m\times n}\rightarrow\mathbb{R}$ là một hàm và $A\in\mathbb{R}^{m\times n}$ là một ma trận. Gradien của $f$ đối với $A$ là ma trận $m\times n$, được kí hiệu là $\nabla_A f(A)$, sao cho:

\[\boxed{\Big(\nabla_A f(A)\Big)_{i,j}=\frac{\partial f(A)}{\partial A_{i,j}}}\]

Ghi chú: gradien của $f$ chỉ được xác định khi $f$ là hàm trả về một số.


Hessian Cho $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ là một hàm và $x\in\mathbb{R}^{n}$ là một vectơ. Hessian của $f$ đối với $x$ là một ma trận đối xứng $n\times n$, ghi chú $\nabla_x^2 f(x)$, sao cho:

\[\boxed{\Big(\nabla_x^2 f(x)\Big)_{i,j}=\frac{\partial^2 f(x)}{\partial x_i\partial x_j}}\]

Ghi chú: hessian của $f$ chỉ được xác định khi $f$ là hàm trả về một số.


Các phép toán của gradien Đối với ma trận $A$,$B$,$C$, các thuộc tính gradien sau cần để lưu ý:

\[\boxed{\nabla_A\textrm{tr}(AB)=B^T}\quad\quad\boxed{\nabla_{A^T}f(A)=\left(\nabla_Af(A)\right)^T}\] \[\boxed{\nabla_A\textrm{tr}(ABA^TC)=CAB+C^TAB^T}\quad\quad\boxed{\nabla_A|A|=|A|(A^{-1})^T}\]