Định thức và ứng dụng trong thuật toán nén PCA

Định thức (Determinant)

Định thức của một ma trận vuông, ký hiệu là det(A), là một hàm ánh xạ ma trận sang một số thực. Định thức của ma trận bằng tích của tất cả các giá trị riêng của nó. Giá trị tuyệt đối của định thức có thể được xem như một thước đo mức độ mà phép nhân với ma trận đó làm mở rộng hoặc thu hẹp không gian.

• Nếu định thức bằng 0, không gian bị co lại hoàn toàn theo ít nhất một chiều, khiến nó mất toàn bộ thể tích.
• Nếu định thức bằng 1, phép biến đổi bảo toàn thể tích.

Ví dụ: Phân tích thành phần chính (Principal Components Analysis - PCA)

Một thuật toán học máy đơn giản là phân tích thành phần chính (PCA), có thể được xây dựng chỉ bằng kiến thức cơ bản về đại số tuyến tính.

Giả sử chúng ta có tập hợp gồm ( m ) điểm ( { x^{(1)}, ..., x^{(m)} } ) trong không gian ( \mathbb{R}^n ) và muốn nén chúng theo cách mất mát dữ liệu (lossy compression), tức là lưu trữ các điểm này bằng ít bộ nhớ hơn nhưng có thể làm mất một phần độ chính xác. Mục tiêu là giảm thiểu tổn thất thông tin.

Một cách để mã hóa các điểm này là biểu diễn chúng dưới dạng phiên bản có số chiều thấp hơn. Với mỗi điểm ( x^{(i)} \in \mathbb{R}^n ), ta tìm một vector mã tương ứng ( c^{(i)} \in \mathbb{R}^l ). Nếu ( l < n ), thì lưu trữ các vector mã sẽ tiêu tốn ít bộ nhớ hơn so với dữ liệu gốc.

PCA xác định bằng cách chọn hàm giải mã ( g(c) ). Để đơn giản hóa bộ giải mã, ta sử dụng phép nhân ma trận để ánh xạ mã trở lại không gian ( \mathbb{R}^n ), với:
[
g(c) = Dc
]
trong đó ( D \in \mathbb{R}^{n \times l} ) là ma trận giải mã.

Tính toán mã tối ưu cho bộ giải mã này có thể là một bài toán khó. Để đơn giản hóa, PCA ràng buộc các cột của ( D ) phải trực giao với nhau. (Lưu ý rằng ( D ) chỉ là ma trận trực giao nếu ( l = n )).

Tuy nhiên, nhiều nghiệm có thể xảy ra do ta có thể tăng tỷ lệ của ( D ) nếu giảm tỷ lệ của ( c ) theo cách tương ứng cho tất cả các điểm. Để đảm bảo nghiệm duy nhất, PCA thêm ràng buộc rằng tất cả các cột của ( D ) phải có chuẩn đơn vị.

Tối ưu hóa mã hóa

Để hiện thực hóa ý tưởng trên thành thuật toán có thể triển khai, ta cần tìm cách xác định điểm mã ( c^* ) tối ưu cho mỗi điểm dữ liệu ( x ). Một cách để làm điều này là tối thiểu hóa khoảng cách giữa ( x ) và ( g(c^*) ), được đo bằng chuẩn ( L_2 ):

[
c^* = \arg\min_c ||x - g(c)||_2.
]

Vì cả chuẩn ( L_2 ) và chuẩn bình phương ( L_2^2 ) đều có cùng giá trị cực tiểu tại cùng một ( c ), ta có thể sử dụng:

[
c^* = \arg\min_c ||x - g(c)||_2^2.
]

Sử dụng tính chất của chuẩn ( L_2 ), phương trình trên có thể triển khai như sau:

[
(x - g(c))^T (x - g(c)) = x^T x - 2x^T g(c) + g(c)^T g(c).
]

Vì thành phần ( x^T x ) không phụ thuộc vào ( c ), ta có thể loại bỏ nó để thu gọn thành:
[
c^* = \arg\min_c -2x^T g(c) + g(c)^T g(c).
]
Thay ( g(c) = Dc ) vào, ta có:
[
c^* = \arg\min_c -2x^T Dc + c^T D^T Dc.
]
Do các cột của ( D ) trực giao và có chuẩn đơn vị, ta thu được:
[
c^* = D^T x.
]
Điều này có nghĩa là để mã hóa một điểm ( x ), ta chỉ cần thực hiện một phép nhân ma trận-vector đơn giản:
[
f(x) = D^T x.
]
Tương tự, để tái tạo lại điểm dữ liệu từ vector mã, ta sử dụng:
[
r(x) = g(f(x)) = DD^T x.
]

Nhờ vào cách xây dựng này, PCA trở thành một phương pháp nén dữ liệu hiệu quả, giúp giảm số chiều dữ liệu trong khi vẫn bảo toàn thông tin quan trọng nhất.

Dưới đây là phần tiếp theo về phân tích thành phần chính (PCA), tiếp tục từ nội dung trước đó.

Ý nghĩa hình học của PCA

PCA tìm kiếm một không gian con có số chiều thấp hơn sao cho dữ liệu được chiếu lên không gian này có phương sai lớn nhất. Điều này có nghĩa là PCA tìm ra các trục chính (principal components) của dữ liệu, nơi mà dữ liệu có độ phân tán cao nhất.

Giả sử ta có tập dữ liệu ( X ) gồm ( m ) điểm dữ liệu ( x^{(i)} \in \mathbb{R}^n ). Trước tiên, ta cần chuẩn hóa dữ liệu bằng cách trừ đi giá trị trung bình:
[
\bar{x} = \frac{1}{m} \sum_{i=1}^{m} x^{(i)}
]
[
\tilde{x}^{(i)} = x^{(i)} - \bar{x}
]
Sau đó, ta xây dựng ma trận hiệp phương sai:
[
C = \frac{1}{m} \sum_{i=1}^{m} \tilde{x}^{(i)} \tilde{x}^{(i)T} = \frac{1}{m} X^T X.
]
PCA tìm các vector riêng (eigenvectors) của ma trận hiệp phương sai ( C ). Các giá trị riêng tương ứng cho biết lượng phương sai được giải thích bởi mỗi thành phần chính.

Giải pháp sử dụng phân rã giá trị kỳ dị (SVD)

Một cách phổ biến để tính PCA là sử dụng phân rã giá trị kỳ dị (Singular Value Decomposition - SVD). Giả sử ta thực hiện SVD trên ma trận dữ liệu ( X ):
[
X = U \Sigma V^T.
]
Trong đó:

• ( U ) là ma trận trực giao chứa các vector riêng của ( XX^T ).
• ( V ) là ma trận trực giao chứa các vector riêng của ( X^T X ), cũng chính là các thành phần chính (principal components).
• ( \Sigma ) là ma trận đường chéo chứa các giá trị kỳ dị, tương ứng với căn bậc hai của các giá trị riêng.

Các thành phần chính chính là các cột của ( V ), và ta có thể chọn số chiều thấp hơn bằng cách lấy ( l ) cột đầu tiên của ( V ) để tạo thành ma trận chiếu ( D ):

[
D = V_l.
]

Sau đó, việc mã hóa dữ liệu được thực hiện như:

[
c = D^T x.
]
Và tái tạo lại dữ liệu bằng:
[
\hat{x} = D c = D D^T x.
]

Ứng dụng của PCA

PCA là một kỹ thuật mạnh mẽ và được sử dụng trong nhiều lĩnh vực, bao gồm:

• Giảm chiều dữ liệu: PCA giúp giảm số chiều của tập dữ liệu mà vẫn giữ được nhiều thông tin quan trọng nhất.
• Tiền xử lý cho các thuật toán học máy: Giảm chiều giúp tăng tốc độ huấn luyện mô hình và giảm hiện tượng quá khớp (overfitting).
• Xử lý ảnh và thị giác máy tính: PCA được sử dụng để trích xuất đặc trưng từ ảnh, như trong nhận diện khuôn mặt.
• Nén dữ liệu: PCA giúp nén dữ liệu bằng cách giữ lại các thành phần có phương sai cao nhất.

Tổng kết

PCA là một kỹ thuật quan trọng trong học máy và thống kê, giúp trích xuất thông tin chính từ dữ liệu bằng cách tìm các hướng có phương sai lớn nhất. Với việc sử dụng phân rã giá trị kỳ dị (SVD), PCA có thể được tính toán một cách hiệu quả ngay cả khi số chiều dữ liệu lớn.