SVD rút gọn: Khi toán học nén cả mặt trăng thành vài con số

SVD rút gọn (Truncated SVD) là một trong những kỹ thuật giảm chiều dữ liệu quyền năng nhất trong học máy và xử lý ảnh. Bằng cách loại bỏ các giá trị suy biến nhỏ, ta có thể nén một bức ảnh 1.024×1.024 xuống chỉ còn một phần nhỏ dữ liệu gốc mà vẫn giữ được phần lớn thông tin. Bài viết dưới đây giải thích mối quan hệ giữa SVD và Phân tích thành phần chính (PCA), cùng phần minh họa trực quan đầy ấn tượng với ảnh mặt trăng.

PCA – giảm chiều bằng biến đổi tuyến tính

Phân tích thành phần chính (PCA) là phương pháp giảm chiều dữ liệu dựa trên việc biến đổi tuyến tính dữ liệu sang một hệ tọa độ mới, nơi phần lớn sự biến thiên của dữ liệu có thể được mô tả bằng ít chiều hơn so với dữ liệu ban đầu. Về bản chất, quá trình này liên quan đến việc phân rã trị riêng (eigen-decomposition) của ma trận hiệp phương sai.

SVD – phân rã ma trận thành ba thành phần

Phân rã giá trị suy biến (SVD) là một kỹ thuật phân rã ma trận thực M thành ba ma trận U, Σ và V sao cho:

M = U × Σ × Vᵀ

Nếu M có kích thước m×n, thì U là m×m, Σ là m×n và V là n×n. Cả U và V đều trực giao chuẩn hóa (orthonormal), còn Σ là ma trận chéo chữ nhật với các hệ số không âm.

Minh họa ma trận SVD

Điểm khác biệt then chốt so với PCA: SVD phân rã trực tiếp trên ma trận dữ liệu, còn PCA phân rã trên ma trận hiệp phương sai. Các hệ số trên đường chéo của Σ được gọi là giá trị suy biến (singular values) của M, và thông thường người ta sắp xếp chúng theo thứ tự giảm dần. Số lượng giá trị suy biến khác không chính là hạng (rank) của M.

Mối liên hệ chặt chẽ giữa SVD và PCA:

• Các cột của V là các hướng/trục chính (vector riêng).
• Các cột của U × Σ là các thành phần chính (điểm số).
• Các giá trị suy biến gắn liền với các trị riêng của ma trận hiệp phương sai.

SVD rút gọn – bỏ đi những gì không cần thiết

Hãy thử với một ảnh xám 1.024×1.024 của mặt trăng. Ta có thể coi ảnh này như 1.024 vector, mỗi vector gồm 1.024 thành phần – tức một tập hợp 1.024 vector trong không gian 1.024 chiều.

Khi chạy PCA/SVD trên tập dữ liệu này, ba ma trận U, Σ, V đều có kích thước 1.024×1.024. Riêng Σ là ma trận chéo vuông – chỉ các hệ số trên đường chéo mới có thể khác không, và được sắp xếp từ lớn nhất (góc trên trái) xuống nhỏ nhất (góc dưới phải).

Mặt trăng gốc

SVD rút gọn đơn giản là việc đặt về 0 tất cả các hệ số trong Σ, chỉ giữ lại n hệ số ở góc trên trái. Việc cắt bỏ này kéo theo ta cũng vứt luôn 1.024 − n cột trong U và V. Khi tái tạo ma trận gốc bằng công thức M' = U' × Σ' × V'ᵀ, ta thu được M' gần giống M. Càng giữ nhiều hệ số, M' càng xấp xỉ M chính xác hơn. Nhưng nhờ đặc tính bảo toàn thông tin của PCA/SVD, chỉ cần giữ một số ít hệ số đầu tiên là đủ để khôi phục gần như toàn bộ thông tin ban đầu.

Tái tạo mặt trăng – phép màu của PCA/SVD

Hãy áp dụng tất cả những điều trên vào ảnh mặt trăng. Thay vì cắt tại một giá trị n duy nhất, ta sẽ quét n trên toàn bộ dải giá trị và quan sát cách xấp xỉ thay đổi.

Bố cục các hình ảnh và video minh họa:

• Nửa trái: ma trận tái tạo M'.
• Nửa phải: sai số tái tạo abs(M − M').
• Đồ thị vàng giảm dần: MSE khi ngày càng ít giá trị suy biến bị đặt về 0.

Tái tạo mặt trăng với 32 thành phần

Đáng chú ý là với chỉ 32 trong số 1.024 thành phần, chi phí lưu trữ cực kỳ nhỏ: các nhân tử rút gọn gồm U' (1.024×32), 32 giá trị suy biến còn lại, và V' (1.024×32). Tổng cộng là 65.568 con số, so với 1.048.576 con số trong ma trận M gốc – tức giảm 16 lần – mà hình ảnh vẫn đọc ra được là mặt trăng.

Điều đáng kinh ngạc (phép màu của PCA/SVD) là đồ thị sai số giảm cực nhanh. Điều này chứng minh rằng các thành phần đầu tiên nắm giữ phần lớn thông tin trong M, trong khi các thành phần cuối chỉ mang chi tiết tần số cao/biên độ thấp.

Chuỗi tái tạo mặt trăng

Hiện tượng này gợi nhớ đến Biến đổi Fourier, Biến đổi Cosin/Sin và các phép biến đổi tương tự. Những phép biến đổi đó xử lý tính đối ngẫu không gian – tần số, còn PCA/SVD thuần túy là thay đổi cơ sở dựa trên phương sai. Tuy nhiên, tất cả đều biến đổi thông tin sang dạng đối ngẫu, nơi "lượng thông tin" xuất hiện một cách có cấu trúc và dễ quản lý.

Các phép biến đổi Fourier/Cosin... chính là nền tảng của .jpeg, .mp3 và nhiều hệ thống nén khác, khai thác việc hệ thống cảm nhận của con người nhạy hơn với độ sáng (so với độ màu) và với tần số thấp (so với tần số cao). Với SVD/PCA, các hệ số phía trên trong Σ nắm giữ nhiều phương sai dữ liệu hơn các hệ số phía dưới.

Trường hợp dễ và khó

Như đã giải thích, phân rã ma trận có thể được hiểu là phép đổi cơ sở sang một không gian đặc biệt, nơi các hàng dữ liệu phụ thuộc tuyến tính lẫn nhau. Trong trường hợp đó, các ma trận U/V hạng thấp hơn sẽ đủ để tái tạo chính xác ma trận gốc.

Một trường hợp cực đoan là hình hộp vuông, nơi chỉ 1 hệ số/hàng/cột là đủ. Trong trường hợp này, cả bên trong lẫn bên ngoài hình, mọi hàng/cột đều giống hệt nhau. Hộp cũng chính là một bộ lọc tích chập tách rời (separable convolution filter).

Ngược lại, xoay hình lại gây ra thảm họa, dù PCA/SVD có khả năng "tự phát hiện" những phép đổi cơ sở như vậy. Vì ta đang xử lý toán học rời rạc, hình bị xoay sẽ trở nên "rỗ hạt" (pixelated), khiến phân rã trở nên không thuần khiết về mặt số học. Thú vị là trong những khung hình đầu tiên của video, phép tái tạo "cố chấp" giữ nguyên hình vuông chưa xoay.

Ứng dụng thực tiễn

Bên cạnh việc giảm chiều trong phân tích dữ liệu, SVD rút gọn còn có nhiều ứng dụng thực tiễn đáng chú ý:

• Nén dữ liệu: Bart Wronski có một bài viết rất hay về việc nén bộ texture PBR bằng kỹ thuật này. Nén texture BCn cũng dựa trên giảm chiều, với bài phân tích chất lượng của Nathan Reed.
• Xấp xỉ hạng thấp (Low-rank approximation): một hướng ứng dụng thú vị khác, cũng được Bart Wronski đề cập đến.

Chi tiết triển khai

Tác giả bài viết đã dùng mã C++ PCA/SVD cũ trong API của Maverick để tạo ra các hình ảnh và video trong bài. Tuy nhiên, sau khi đọc bài của Atrix256, tác giả dự định sẽ thay thế phần triển khai của lớp xsvd_c cũ bằng thư viện Eigen – một lựa chọn phổ biến và mạnh mẽ cho đại số tuyến tính trong C++.