Ma trận xác định dương là gì
Trong trang này: Show
1. Giới thiệuHẳn các bạn vẫn nhớ một loại bài toán được làm rất nhiều khi học Đại số tuyến tính: Bài toán chéo hoá ma trận. Bài toán đó nói rằng: Một ma trận vuông \(\mathbf{A} \in \mathbb{R}^{n\times n}\) được gọi là chéo hoá được (diagonalizable) nếu tồn tại ma trận đường chéo \(\mathbf{D}\) và ma trận khả nghịch \(\mathbf{P}\) sao cho: \[ \mathbf{A} = \mathbf{P} \mathbf{D} \mathbf{P}^{-1}~~~~(1) \] Số lượng phần tử khác 0 của ma trận đường chéo \(\mathbf{D}\) chính là rank của ma trận \(\mathbf{A}\). Nhân cả hai vế của \((1)\) với \(\mathbf{P}\) ta có: \[ \mathbf{AP} = \mathbf{PD}~~~~(2) \] Gọi \(\mathbf{p}_i, \mathbf{d}_i\) lần lượt là cột thứ \(i\) của ma trận \(\mathbf{P}\) và \(\mathbf{D}\). Vì mỗi một cột của vế trái và vế phải của \((2)\) phải bằng nhau, ta sẽ có: \[ \mathbf{Ap}_i = \mathbf{Pd}_i = d_{ii}\mathbf{p}_i ~~~~ (3) \] với \(d_{ii}\) là phần tử thứ \(i\) của \(\mathbf{p}_i\). Dấu bằng thứ hai xảy ra vì \(\mathbf{D}\) là ma trận đường chéo, tức \(\mathbf{d}_i\) chỉ có thành phần \(d_{ii}\) là khác 0. Và nếu bạn vẫn nhớ, biểu thức \((3)\) chỉ ra rằng mỗi phần tử \(d_{ii}\) phải là một trị riêng (eigenvalue) của \(\mathbf{A}\) và mỗi vector cột \(\mathbf{p}_i\) phải là một vector riêng (eigenvector) của \(\mathbf{A}\) ứng với trị riêng \(d_{ii}\). Cách phân tích một ma trận vuông thành nhân tử như \((1)\) còn được gọi là Eigen Decomposition. Một điểm quan trọng là cách phân tích như \((1)\) chỉ được áp dụng với ma trận vuông và không phải lúc nào cũng tồn tại. Nó chỉ tồn tại nếu ma trận \(\mathbf{A}\) có \(n\) vector riêng độc lập tuyến tính, vì nếu không thì không tồn tại ma trận \(\mathbf{P}\) khả nghịch. Thêm nữa, cách phân tích này cũng không phải là duy nhất vì nếu \(\mathbf{P}, \mathbf{D}\) thoả mãn \((1)\) thì \(k\mathbf{P}, \mathbf{D}\) cũng thoả mãn với \(k\) là một số thực khác 0 bất kỳ. Việc phân tích một ma trận ra thành tích của nhiều ma trận đặc biệt khác (Matrix Factorization hoặc Matrix Decomposition) mang lại nhiều ích lợi quan trọng mà các bạn sẽ thấy: giảm số chiều dữ liệu, nén dữ liệu, tìm hiểu các đặc tính của dữ liệu, giải các hệ phương trình tuyến tính, clustering, và nhiều ứng dụng khác. Recommendation System cũng là một trong rất nhiều ứng dụng của Matrix Factorization. Trong bài viết này, tôi sẽ giới thiệu với các bạn một trong những phương pháp Matrix Factorization rất đẹp của Đại số tuyến tính. Phương pháp đó có tên là Singular Value Decomposition (SVD). Các bạn sẽ thấy, mọi ma trận, không nhất thiết là vuông, đều có thể được phân tích thành tích của ba ma trận đặc biệt. Dưới đây, tôi sẽ phát biểu SVD cũng như các tính chất và ứng dụng điển hình của nó. Trước hết, chúng ta cần ôn tập lại một chút về Đại số tuyến tính. Chú ý rằng các ma trận trong bài viết này đều được ngầm giả sử là ma trận thực. 2. Một chút về Đại số tuyến tính2.1. Trị riêng và vector riêngCho một ma trận vuông \(\mathbf{A} \in \mathbb{R}^{n\times n}\), nếu số vô hướng \(\lambda\) và vector \(\mathbf{x} \neq \mathbf{0} \in \mathbb{R}^n\) thoả mãn: \[ \mathbf{Ax} = \lambda \mathbf{x} \] thì \(\lambda\) được gọi là một trị riêng của \(\mathbf{A}\) và \(\mathbf{x}\) được gọi là vector riêng tương ứng với trị riêng đó. Một vài tính chất:
Tính chất cuối cùng có thể được suy ra từ định nghĩa của ma trận (nửa) xác định dương. Thật vậy, gọi \(\mathbf{u} \neq \mathbf{0}\) là vector riêng ứng với một trị riêng \(\lambda\) của ma trận \(\mathbf{A}\) xác định dương, ta có: \[ \mathbf{Au} = \lambda \mathbf{u} \Rightarrow \mathbf{u}^T\mathbf{Au} = \lambda \mathbf{u}^T\mathbf{u} = \lambda ||\mathbf{u}||_2^2 \] Vì \(\mathbf{A}\) là nửa xác định dương nên với mọi \(\mathbf{u} \neq \mathbf{0}\): \(\mathbf{u}^T\mathbf{Au} \geq 0\); \(\mathbf{u} \neq 0\) nên \(||\mathbf{u}||_2^2 > 0\). Từ đó suy ra \(\lambda\) là một số không âm. 2.2. Hệ trực giao và trực chuẩnMột hệ cơ sở \({\mathbf{u}_1, \mathbf{u}_2,\dots, \mathbf{u}_m \in \mathbb{R}^m}\) được gọi là trực giao (orthogonal) nếu mỗi vector là khác 0 và tích của hai vector khác nhau bất kỳ bằng 0: \[ \mathbf{u}_i \neq \mathbf{0}; ~~ \mathbf{u}_i^T \mathbf{u}_j = 0 ~ \forall ~1 \leq i \neq j \leq m \] Một hệ cơ sở \({\mathbf{u}_1, \mathbf{u}_2,\dots, \mathbf{u}_m \in \mathbb{R}^m}\) được gọi là trực chuẩn (orthonormal) nếu nó là một hệ trực giao và độ dài Euclidean (norm 2) của mỗi vector bằng 1: \[ \begin{eqnarray} \mathbf{u}_i^T \mathbf{u}_j = \left\{ \begin{matrix} 1 & \text{if} &i = j \newline 0 & \text{otherwise} \end{matrix} \right. ~~~~ (4) \end{eqnarray} \] Gọi \(\mathbf{U} = [\mathbf{u}_1, \mathbf{u}_2,\dots, \mathbf{u}_m]\) với \({\mathbf{u}_1, \mathbf{u}_2,\dots, \mathbf{u}_m \in \mathbb{R}^m}\) là trực chuẩn, thế thì từ \((4)\) có thể suy ra ngay: \[ \mathbf{UU}^T = \mathbf{U}^T\mathbf{U} = \mathbf{I} \] trong đó \(\mathbf{I}\) là ma trận đơn vị bậc \(m\). Ta gọi \(\mathbf{U}\) là ma trận trực giao (orthogonal matrix). Ma trận loại này không được gọi là ma trận trực chuẩn, không có định nghĩa cho ma trận trực chuẩn. Một vài tính chất:
3. Singular Value DecompositionVì trong mục này cần nắm vững chiều của mỗi ma trận nên tôi sẽ thay đổi ký hiệu một chút để chúng ta dễ hình dung. Ta sẽ ký hiệu một ma trận cùng với số chiều của nó, ví dụ \(\mathbf{A}_{m \times n}\) nghĩa là ma trận \(\mathbf{A} \in \mathbb{R}^{m \times n}\). 3.1. Phát biểu SVDMột ma trận \(\mathbf{A}_{m \times n}\) bất kỳ đều có thể phân tích thành dạng: \[ \mathbf{A}_{m \times n} = \mathbf{U}_{m \times m}\mathbf{\Sigma}_{m \times n} (\mathbf{V}_{n \times n})^T ~~~~ (5) \] Trong đó, \(\mathbf{U}, \mathbf{V}\) là các ma trận trực giao, \(\mathbf{\Sigma}\) là ma trận đường chéo không vuông với các phần tử trên đường chéo \(\sigma_1 \geq \sigma_2 \geq \dots \geq\sigma_r \geq 0 = 0 = \dots = 0\) và \(r\) là rank của ma trận \(\mathbf{A}\). Lưu ý rằng mặc dù \(\Sigma\) không phải ma trận vuông, ta vẫn có thể coi nó là ma trận chéo nếu các thành phần khác không của nó chỉ nằm ở vị trí đường chéo, tức tại các vị trí có chỉ số hàng và chỉ số cột là như nhau. Số lượng các phần tử khác 0 trong \(\Sigma\) chính là rank của ma trận \(\mathbf{A}\). Nếu bạn muốn xem chứng minh về sự tồn tại của SVD, bạn có thể xem tại đây. Chú ý rằng cách biểu diễn \((5)\) không là duy nhất vì ta chỉ cần đổi dấu của cả \(\mathbf{U}\) và \(\mathbf{V}\) thì \((5)\) vẫn thoả mãn. Tuy vậy, người ta vẫn thường dùng ‘the SVD’ thay vì ‘a SVD’. Hình 1 mô tả SVD của ma trận \(\mathbf{A}_{m \times n}\) trong hai trường hợp: \(m < n\) và \(m > n\). Trường hợp \(m =n\) có thể xếp vào một trong hai trường hợp trên. Hình 1: SVD cho ma trận \(\mathbf{A}\) khi: \(m < n\) (hình trên), và \(m > n\) (hình dưới). \(\Sigma\) là một ma trận đường chéo với các phần tử trên đó giảm dần và không âm. Màu đỏ càng đậm thể hiện giá trị càng cao. Các ô màu trắng trên ma trận này thể hiện giá trị 0. 3.2. Nguồn gốc tên gọi Singular Value DecompositionTạm bỏ qua chiều của mỗi ma trận, từ \((5)\) ta có: \[ \begin{eqnarray} \mathbf{AA}^T &=& \mathbf{U}\mathbf{\Sigma} \mathbf{V}^T (\mathbf{U}\mathbf{\Sigma} \mathbf{V}^T)^T \newline &=& \mathbf{U}\mathbf{\Sigma} \mathbf{V}^T \mathbf{V}\mathbf{\Sigma}^T\mathbf{U}^T \newline &=& \mathbf{U}\mathbf{\Sigma}\mathbf{\Sigma}^T\mathbf{U}^T = \mathbf{U}\mathbf{\Sigma}\mathbf{\Sigma}^T\mathbf{U}^{-1} ~~~~~ (6) \end{eqnarray} \] Dấu bằng cuối cùng xảy ra vì \(\mathbf{V}^T\mathbf{V} = \mathbf{I}\) do \(\mathbf{V}\) là một ma trận trực giao. Quan sát thấy rằng \(\Sigma\Sigma^T\) là một ma trận đường chéo với các phần tử trên đường chéo là \(\sigma_1^2, \sigma_2^2, \dots\). Vậy \((6)\) chính là Eigen Decomposition của \(\mathbf{A}\mathbf{A}^T\). Thêm nữa, \(\sigma_1^2, \sigma_2^2, \dots\) chính là các trị riêng của \(\mathbf{A}\mathbf{A}^T\). Ma trận \(\mathbf{A}\mathbf{A}^T\) luôn là ma trận nửa xác định dương nên các trị riêng của nó là không âm. Các \(\sigma_i\) là căn bậc hai của các trị riêng của \(\mathbf{A}\mathbf{A}^T\) còn được gọi là singular values của \(\mathbf{A}\). Cái tên Singular Value Decomposition xuất phát từ đây. Cũng theo đó, mỗi cột của \(\mathbf{U}\) chính là một vector riêng của \(\mathbf{A}\mathbf{A}^T\). Ta gọi mỗi cột này là left-singular vectors của \(\mathbf{A}\). Tương tự như thế, \(\mathbf{A}^T\mathbf{A} = \mathbf{V}\Sigma^T\Sigma \mathbf{V}^T\) và các cột của \(\mathbf{V}\) còn được gọi là các right-singular vectors của \(\mathbf{A}\). Trong Python, để tính SVD của một ma trận, chúng ta sử dụng module linalg của numpy như sau: import numpy as np from numpy import linalg as LA m, n = 2, 3 A = np.random.rand(m, n) U, S, V = LA.svd(A) # checking if U, V are orthogonal and S is a diagonal matrix with # nonnegative decreasing elements print 'Frobenius norm of (UU^T - I) =', \ LA.norm(U.dot(U.T) - np.eye(m)) print '\n S = ', S, '\n' print 'Frobenius norm of (VV^T - I) =', \ LA.norm(V.dot(V.T) - np.eye(n)) Frobenius norm of (UU^T - I) = 3.14018491737e-16 S = [ 1.82891093 0.2125061 ] Frobenius norm of (VV^T - I) = 7.77403895378e-16 Lưu ý rằng biến S được trả về chỉ bao gồm các phần tử trên đường chéo của \(\Sigma\). Biến V trả về là \(\mathbf{V}^T\) trong \((5)\). 3.3. Compact SVDViết lại biểu thức \((5)\) dưới dạng tổng của các ma trận rank 1: \[ \mathbf{A} = \sigma_1 \mathbf{u}_1 \mathbf{v}^T_1 + \sigma_2\mathbf{u}_2\mathbf{v}_2^2 + \dots + \sigma_r\mathbf{u}_r\mathbf{v}_r^T \] với chú ý rằng mỗi \(\mathbf{u}_1 \mathbf{v}^T_i, 1 \leq i \leq r\) là một ma trận có rank bằng 1. Rõ ràng trong cách biểu diễn này, ma trận \(\mathbf{A}\) chỉ phụ thuộc vào \(r\) cột đầu tiên của \(\mathbf{U, V}\) và \(r\) giá trị khác 0 trên đường chéo của ma trận \(\Sigma\). Vì vậy ta có một cách phân tích gọn hơn và gọi là compact SVD: \[ \mathbf{A} = {\mathbf{U}}_r{\Sigma}_r({\mathbf{V}}_r)^T \] Với \(\mathbf{U}_r, \mathbf{V}_r \) lần lượt là ma trận được tạo bởi \(r\) cột đầu tiên của \(\mathbf{U}\) và \(\mathbf{V}\). \(\Sigma_r\) là ma trận con được tạo bởi \(r\) hàng đầu tiên và \(r\) cột đầu tiên của \(\Sigma\). Nếu ma trận \(\mathbf{A}\) có rank nhỏ hơn rất nhiều so với số hàng và số cột \(r \ll m, n\), ta sẽ được lợi nhiều về việc lưu trữ. Dưới đây là ví dụ minh hoạ với \(m = 4, n = 6, r = 2\). Hình 2: Biểu diễn SVD dạng thu gọn và biểu diễn ma trận dưới dạng tổng các ma trận có rank bằng 1. 3.4. Truncated SVDChú ý rằng trong ma trận \(\Sigma\), các giá trị trên đường chéo là không âm và giảm dần \(\sigma_1 \geq \sigma_2 \geq \dots, \geq \sigma_r \geq 0 = 0 = \dots = 0\). Thông thường, chỉ một lượng nhỏ các \(\sigma_i\) mang giá trị lớn, các giá trị còn lại thường nhỏ và gần 0. Khi đó ta có thể xấp xỉ ma trận \(\mathbf{A}\) bằng tổng của \(k < r\) ma trận có rank 1: \[ \mathbf{A} \approx \mathbf{A}_k = \mathbf{U}_k \Sigma_k (\mathbf{V}_k)^T = \sigma_1 \mathbf{u}_1 \mathbf{v}^T_1 + \sigma_2\mathbf{u}_2\mathbf{v}_2^2 + \dots + \sigma_k\mathbf{u}_k\mathbf{v}k^T ~~~~ (7) \] Dưới đây là một định lý thú vị. Định lý này nói rằng sai số do cách xấp xỉ trên chính là căn bậc hai của tổng bình phương của các singular values mà ta đã bỏ qua ở phần cuối của \(\Sigma\). Ở đây sai số được định nghĩa là Frobineous norm của hiệu hai ma trận: Định lý: \[ ||\mathbf{A} - \mathbf{A}_k||_F^2 = \sum_{i = k + 1}^r \sigma_i^2 ~~~ (8) \] Chứng minh: Sử dụng tính chất \(||\mathbf{X}||_F^2 = \text{trace}(\mathbf{X}\mathbf{X}^T)\) và \(\text{trace}(\mathbf{XY}) = \text{trace}(\mathbf{YX})\) với mọi ma trận \(\mathbf{X, Y}\) ta có: \[ \begin{eqnarray} ||\mathbf{A} - \mathbf{A}_k||_F^2 & = & ||\sum_{i = k + 1}^r \sigma_i \mathbf{u}_i\mathbf{v}_i^T ||_F^2 & (9)\newline & = & \text{trace}\left\{ \left(\sum_{i = k + 1}^r \sigma_i \mathbf{u}_i\mathbf{v}_i^T\right) \left(\sum_{j = k + 1}^r \sigma_j \mathbf{u}_j\mathbf{v}_j^T\right)^T \right\} & (10) \newline &=& \text{trace}\left\{ \sum_{i = k + 1}^r \sum_{j = k + 1}^r \sigma_i\sigma_j \mathbf{u}_i\mathbf{v}_i^T \mathbf{v}_j \mathbf{u}_j^T \right\} & (11) \newline &=& \text{trace}\left\{ \sum_{i = k + 1}^r \sigma_i^2\mathbf{u}_i\mathbf{u}_i^T \right\} & (12) \newline &=& \text{trace}\left\{ \sum_{i = k + 1}^r \sigma_i^2\mathbf{u}_i^T\mathbf{u}_i \right\} & (13) \newline &=& \text{trace}\left\{ \sum_{i = k + 1}^r \sigma_i^2 \right\} & (14) \newline & = & \sum_{i = k + 1}^r \sigma_i^2 & (15) \end{eqnarray} \] Dấu bằng ở \((12)\) là vì \(\mathbf{V}\) là ma trận trực giao (xem \((4)\)). Dấu bằng ở \((13)\) là vì hàm \(\text{trace}\) có tính chất giao hoán. Dấu bằng ở \((15)\) là vì biểu thức trong dấu ngoặc của \((14)\) là một số vô hướng. Thay \(k = 0\) ta sẽ có: \[||\mathbf{A}||_F^2 = \sum_{i = 1}^r \sigma_i^2~~~~ (16) \] Từ đó: \[ \frac{||\mathbf{A} - \mathbf{A}_k||_F^2}{||\mathbf{A}||_F^2} = {\frac{\sum_{i = k + 1}^r \sigma_i^2}{\sum_{j = 1}^r \sigma_j^2}} ~~~~ (17) \] Như vậy, sai số do xấp xỉ càng nhỏ nếu phần singular values bị truncated có giá trị càng nhỏ so với phần singular values được giữ lại. Đây là một định lý quan trọng giúp xác định việc xấp xỉ ma trận dựa trên lượng thông tin muốn giữ lại. Ví dụ, nếu ta muốn giữ lại ít nhất 90% lương thông tin trong \(\mathbf{A}\), trước hết ta tính \(\sum_{j = 1}^r \sigma_j^2\), sau đó chọn \(k\) là số nhỏ nhất sao cho: \[ \frac{\sum_{i = 1}^k \sigma_i^2}{\sum_{j = 1}^r \sigma_j^2} \geq 0.9 \] Khi \(k\) nhỏ, ma trận \(\mathbf{A}_k\) có rank là \(k\), là một ma trận có rank nhỏ. Vì vậy, Truncated SVD còn được coi là một phương pháp Low-rank approximation. 3.5. Best Rank \(k\) ApproximationNgười ta chứng minh được rằng (Singular Value Decomposition - Princeton) \(\mathbf{A}_k\) chính là nghiệm của bài toán tối ưu: \[ \begin{eqnarray} \min_{\mathbf{B}} &&||\mathbf{A} - \mathbf{B}||_F \newline \text{s.t.} && \text{rank}(\mathbf{B}) = k ~~~~~~~~~~~~~~ (17) \end{eqnarray} \] và như đã chứng minh ở trên \(||\mathbf{A} - \mathbf{A}_k||_F^2 = \sum_{i = k + 1}^r \sigma_i^2\). Nếu sử dụng norm 2 của ma trận thay vì Frobenius norm để đo sai số, \(\mathbf{A}_k\) cũng là nghiệm của bài toán tối ưu: \[ \begin{eqnarray} \min_{\mathbf{B}} &&||\mathbf{A} - \mathbf{B}||_2 \newline \text{s.t.} && \text{rank}(\mathbf{B}) = k ~~~~~~~~~~~~~~ (18) \end{eqnarray} \] và sai số: \(||\mathbf{A} - \mathbf{A}_k||_2^2 = \sigma_{k+1}^2\). Định nghĩa của norm 2 của một ma trận là: \[ ||\mathbf{A}||_2 = \max_{||\mathbf{x}||_2 = 1} ||\mathbf{Ax}||_2 \] Đây là lý do căn bậc hai của tổng bình phương của các phần tử của một ma trận không được gọi là norm 2 như đối với vector. Nếu bạn muốn biết thêm: \[ ||\mathbf{A}||_2 = \sigma_1 \] tức norm 2 của một ma trận chính là singular value lớn nhất của ma trận đó. Frobenius norm và norm 2 là hai norms được sử dụng nhiều nhất trong ma trận. Như vậy, xét trên cả hai norm này, Truncated SVD đều cho xấp xỉ tốt nhất. Vì vậy Truncated SVD còn được gọi là Best low-rank Approximation. 4. Một vài ứng dụng của SVD4.1. Image CompressionXét ví dụ trong Hình 3 dưới đây: Hình 3 mô tả chất lượng ảnh khi chọn các giá trị \(k\) khác nhau. Khi \(k\) gần 100, lượng thông tin mất đi rơi vào khoảng nhỏ hơn 2%, ảnh thu được có chất lượng gần như ảnh gốc. Hình 4: Ảnh thu được với các giá trị \(k\) khác nhau. Khi \(k\) tới gần 100, chất lượng ảnh gần như ảnh gốc. Để lưu ảnh với Truncated SVD, ta sẽ lưu các ma trận \(\mathbf{U}_k \in \mathbb{R}^{m \times k}, \Sigma_k \in \mathbb{R}^{k \times k}, \mathbf{V}_k \in \mathbb{R}^{n \times k}\). Tổng số phần tử phải lưu là \(k(m + n + 1)\) với chú ý rằng ta chỉ cần lưu các giá trị trên đường chéo của \(\Sigma_k\). Giả sử mỗi phần tử được lưu bởi một số thực 4 byte, thế thì số byte cần lưu trữ là \(4k(m + n + 1)\). Nếu so giá trị này với ảnh gốc có kích thước \(mn\), mỗi giá trị là 1 số nguyên 1 byte, tỉ lệ nén là: \[ \frac{4k(m + n + 1)}{mn} \] Khi \(k \ll m, n\), ta được một tỉ lệ nhỏ hơn 1. Trong ví dụ của chúng ta \(m = 960, n = 1440, k = 100\), ta có tỉ lệ nén xấp xỉ 0.69, tức đã tiết kiệm được khoảng 30% bộ nhớ. 4.2. Truncated SVD cho Recommendation SystemNhư đã nhắc ở Mục 1, SVD là một phương pháp Matrix Factorization, vì vậy, nó cũng hoàn toàn có thể được áp dụng vào bài toán Recommendation Systems như trong Bài 25. Ý tưởng hoàn toàn tương tự, ta sẽ xấp xỉ Utility Matrix đã được chuẩn hoá (theo user-based hoặc item-based). Giá trị của ma trận xấp xỉ có rank nhỏ hơn chính là giá trị được dự đoán. Kết quả (RMSE) với cơ sở dữ liệu tương tự như Bài 25 là:
Như vậy, Truncated SVD cho kết quả tốt hơn so với Matrix Factorization giải bằng Gradient Descent một chút. Một cách giải thích thú vị về mối liên quan giữa SVD và Utility Matrix với user- 5. Thảo luận
6. Tài liệu tham khảo[1] Singular Value Decomposition - Stanford University [2] Singular Value Decomposition - Princeton [3] CS168: The Modern Algorithmic Toolbox Lecture #9: The Singular Value Decomposition (SVD) and Low-Rank Matrix Approximations - Stanford [4] The Moore-Penrose Pseudoinverse (Math 33A - UCLA) Nếu có câu hỏi, Bạn có thể để lại comment bên dưới hoặc trên Forum để nhận được câu trả lời sớm hơn. |