SVD Explained: Interactive Demo & Machine Learning Uses

Singular Value Decomposition - SVD là một trong những phép phân tích quan trọng nhất trong đại số tuyến tính vì nó được áp dụng cực kỳ phổ biến trong các lĩnh vực về Machine Learning để giảm chiều dữ liệu hay nén ảnh... Bài viết này mình muốn giới thiệu đến bạn về phương pháp này và một interactive demo để các bạn có thể “vọc“ tận tay với nó :)

Singular Value Decomposition

SVD cho phép ta phân rã một ma trận $A$ bất kỳ kích thước $m \times n$ thành ba ma trận khác:

A = U \Sigma V^T

$U$ là ma trận trực giao kích thước $m\times m$ với các cột là là eigenvectors của $AA^T$
$\Sigma$ là ma trận chéo kích thước $m \times n$ chứa các singular values (luôn không âm)
$V$ là ma trận trực giao kích thước $n \times n$ với các cột là eigenvectors của $A^TA$

Một chút kiến thức nền tảng

Eigenvalues và Eigenvectors

Cho ma trận vuông $M$ , một vector được gọi là eigenvector nếu:

Mv = \lambda v

trong đó $\lambda$ là eigen value. Điều này có nghĩa là khi nhân ma trận $M$ với $v$ chỉ làm cho thay đổi độ dài chứ không thay đổi hướng.

Chéo hóa (diagonalization)

Nếu ma trận $M$ có thể viết dưới dạng

M = PDP^{-1}

với $D$ là ma trận chéo chứa các eigenvalues, thì ta nói $M$ có thể chéo hóa. Một tính chất cực kỳ quan trọng là ma trận đối xứng luôn có thể chéo hóa được.

Ý tưởng cốt lõi của SVD

Khi một ma trận $M$ bất kỳ nhân với một không gian vector, nó thực hiện các phép biến đổi tuyến tính phức tạp như quay (rotation), lật (reflection), và kéo giãn (stretching). Những phép biến đổi này thường làm thay đổi hình dạng và định hướng của các vector trong không gian.

Cụ thể, nếu chúng ta xét một hệ cơ sở trực chuẩn thông thường, ví dụ như các vector đơn vị chuẩn $e_1, e_2, \dots, e_n$ , khi chúng ta áp dụng phép biến đổi $M$ lên chúng (tức là tính $Me_1, Me_2, \dots, Me_n$ ), các vector kết quả thường sẽ bị "bóp méo". Điều này có nghĩa là chúng không còn giữ được tính trực giao (vuông góc) và độ dài đơn vị như ban đầu nữa. Việc phân tích một phép biến đổi như vậy trở nên khó khăn vì các hướng cơ bản đã bị lẫn lộn.

SVD ra đời để giải quyết vấn đề này. Ý tưởng chính của SVD là tìm ra một tập hợp các vector cơ sở trực chuẩn đặc biệt trong không gian đầu vào (được định nghĩa bởi các cột của ma trận $V$ ) sao cho khi $M$ biến đổi các vector này, chúng chỉ tạo thành một tập hợp các vector trực chuẩn khác trong không gian đầu ra (được định nghĩa bởi các cột của ma trận $U$ ) với một tập hợp các hệ số kéo giãn tương ứng $\sigma_1, \sigma_2,\dots$ (được định nghĩa bởi ma trận đường chéo $\Sigma$ ), từ đó ta có quan hệ như sau:

MV = U\Sigma \\ \Rightarrow MVV^{-1} = U \Sigma V^{-1} \Rightarrow M = U \Sigma V^{-1}

Để ý là vì $V$ cũng là một hệ trực chuẩn cho nên ta có $V^{-1}=V^T$ . Từ đó ta có công thức:

M = U \Sigma V^T

Tính vuông góc được bảo toàn trong cả hai không gian này, làm cho việc hiểu và phân tích phép biến đổi của ma trận $M$ trở nên minh bạch hơn rất nhiều.

Mối liên hệ giữa Chéo hóa và SVD

Ta xét ma trận tích $M^TM$ , đây là một ma trận vuông, đối xứng, do đó nó luôn có thể chéo hóa được theo như đã đề cập ở trên. Lúc này ta có:

M^TM = PDP^{-1}

Lại tiếp tục áp dụng khai triển SVD, ta có (để ý rằng cả $U,V$ đều trực chuẩn):

\begin{align*} M^TM &= (U \Sigma V^T)^T U \Sigma V^T\\ &= V\Sigma^TU^T U \Sigma V^T \\ &= V \Sigma^T\Sigma V^T \end{align*}

Như vậy $PDP^{-1} = V\Sigma^T \SigmaV^T$ và vì $V$ là hệ trực chuẩn nên $V^T = V^{-1}$ . Lúc này ta có thể nhận ra sự tương quan giữa 2 vế:

$P$ bên vế trái chính là $V$ của vế phải
$D$ bên vế trái chính là $\Sigma^T \Sigma$ của vế phải, mà $\Sigma^T \Sigma$ có dạng ma trận đường chéo với các phần tử tương ứng là $\sigma_1^2, \sigma_2^2,\dots$ Vậy có thể kết luận rằng mỗi phần tử $\sigma_i$ chính là bằng $\sqrt{e_i}$ với $e_i$ là trị riêng thứ $i$ của ma trận $M$ .

Low-rank Approximation

Giả sử ma trận $A$ có phân rã: $A=U\Sigma V^T$ , nếu sắp xếp các singular values $\sigma_1 \ge \sigma_2 \ge \dots \ge\sigma_r > 0$ với là $r$ rank của $A$ , ta có thể viết lại

A = \sum_{i=1}^r \sigma_iu_iv_i^T

Trong đó:

$u_i$ là cột thứ $i$ của $U$
$v_i$ là cột thứ $i$ của $V$ (chú ý là công thức là $V^T$ , nên $v_i^T$ trở thành hàng)

Nếu chỉ giữ lại $k<r$ thành phần lớn nhất, ta sẽ có:

A_k = \sum_{i=1}^k \sigma_iu_iv_i^T

Lúc đó $A_k$ sẽ là xấp xỉ lớn nhất của $A$ trong chuẩn Frobenius và chuẩn 2 (Eckart–Young–Mirsky theorem)

Như vậy:

Trong xử lý ảnh: chỉ cần vài chục singular values lớn để khôi phục ảnh gần như đầy đủ, thay vì lưu toàn bộ ma trận pixel.
Trong machine learning: thay vì lưu một ma trận lớn (ví dụ 1 triệu user × 100 nghìn sản phẩm), ta có thể xấp xỉ bằng hạng thấp → tiết kiệm bộ nhớ và tính toán.

Ví dụ: Nếu ta lưu một ảnh kích thước 1,920 × 1,080 thì số pixel phải lưu là 2,073,600. Nếu áp dụng SVD với k=100 ta cần:

$U_x$ : 100 cột đầu tiên của ma trận là 100×1,920 = 192,000
$\Sigma_k$ : 100 phần tử trên đường chéo
$V_k$ : 100 cột đầu tiên của của ma trận là 100×1,080 = 108,000

Tổng cộng là 300,100 phần tử so với 2,073,600 phần tử của ma trận gốc.

Singular Value Decomposition (SVD) Demo