23
[latexpage]
23.1. Định nghĩa
Bài toán \textit{Bình phương tối thiểu thông thường} (OLS, hay LS) được định nghĩa là
\[
\min_x \|A x – y\|_2^2
\]
trong đó $A \in \mathbb{R}^{m \times n}, \; y \in \mathbb{R}^m$ là các dữ liệu đã cho. Cặp $(A, y)$ được gọi chung là \textit{dữ liệu bài toán}. Véctơ $y$ thường được gọi là véctơ “đo lường” hoặc “đầu ra”, và ma trận dữ liệu $A$ được gọi là ma trận “thiết kế” hoặc “đầu vào”. Véctơ $r:=y-A x$ được gọi là \textit{véctơ phần dư}.
Lưu ý rằng bài toán này tương đương với bài toán không có bình phương ở chuẩn. Việc lấy bình phương được thực hiện để thuận tiện cho việc giải.
23.2. Các diễn giải
Diễn giải dưới dạng phép chiếu lên không gian ảnh
 |
Ta có thể diễn giải bài toán theo các cột của $A$. Giả sử $A=\left[a_1, \ldots, a_n\right]$, trong đó $a_j \in \mathbb{R}^m$ là cột thứ $j$ của $A \; (j=1, \ldots, n)$. Bài toán được viết là |
| $$ \min _x\left\|\sum_{j=1}^n x_j a_j-y\right\|_2 . $$ |
|
| Theo nghĩa này, ta đang cố gắng tìm xấp xỉ tốt nhất của $y$ dưới dạng một tổ hợp tuyến tính của các cột của $A$. Do đó, bài toán OLS tương đương với việc chiếu (tìm khoảng cách Euclid nhỏ nhất) véctơ $y$ lên bao tuyến tính của các véctơ $a_j$ (tức là: không gian ảnh của $A$). | |
| Như được thấy trong hình, tại điểm tối ưu, véctơ phần dư $A x-y$ trực giao với không gian ảnh của $A$. |
Xem thêm: Nén ảnh thông qua bình phương tối thiểu. .
Diễn giải dưới dạng khoảng cách nhỏ nhất đến tập khả thi
Bài toán OLS thường được áp dụng cho các bài toán mà hệ phương trình tuyến tính $Ax=y$ không \textit{khả thi}, tức là không tồn tại nghiệm của $Ax=y$.
OLS có thể được diễn giải là việc tìm một nhiễu $\delta y$ nhỏ nhất (theo nghĩa chuẩn Euclid) ở vế phải, sao cho hệ phương trình tuyến tính
$$
A x=y+\delta y
$$
trở nên khả thi. Theo nghĩa này, cách phát biểu OLS ngầm giả định rằng ma trận dữ liệu $A$ của bài toán là đã biết chính xác, trong khi chỉ có vế phải chịu nhiễu, hoặc sai số đo lường. Một mô hình phức tạp hơn, \textit{bình phương tối thiểu toàn phần}, có tính đến sai số trong cả $A$ và $y$.
Diễn giải dưới dạng hồi quy
Ta cũng có thể diễn giải bài toán theo các hàng của $A$. Giả sử $A^T=\left[a_1, \ldots, a_m\right]$, trong đó $a_i \in \mathbb{R}^{n}$ là hàng thứ $i$ của $A \;\; (i=1, \ldots, m)$. Bài toán được viết là
$$
\min _x \sum_{i=1}^m\left(y_i-a_i^T x\right)^2 .
$$
Theo nghĩa này, ta đang cố gắng khớp mỗi thành phần của $y$ như một tổ hợp tuyến tính của đầu vào $a_i$ tương ứng, với $x$ là các hệ số của tổ hợp tuyến tính này.
Xem thêm:
23.3. Nghiệm thông qua phân tích QR (trường hợp hạng đầy đủ)
x^*=\left(A^T A\right)^{-1} A^T y .
$$
Ta có thể thấy điều này bằng cách lấy \textit{gradient} (véctơ của các đạo hàm) của hàm mục tiêu, dẫn đến điều kiện tối ưu $A^T(A x-y)=0$. Về mặt hình học, véctơ phần dư $A x-y$ trực giao với bao tuyến tính của các cột của $A$, như đã thấy trong hình trên.
Ta cũng có thể chứng minh điều này thông qua \textit{phân tích QR} của ma trận $A: A=Q R$ với $Q$ là một ma trận $m \times n$ có các cột trực chuẩn ($Q^T Q=I_n$) và $R$ là một ma trận tam giác trên, khả nghịch, cỡ $n \times n$. Lưu ý rằng
\begin{align*} \|A x-y\|_2^2 & = x^T A^T A x – 2 x^T A^T y + y^T y \\ & = x^T R^T R x – 2 x^T R^T Q^T y + y^T y \\ & = \left\|R x-Q^T y\right\|_2^2 + y^T\left(I-Q Q^T\right) y \end{align*}
và sử dụng tính chất $R$ là ma trận khả nghịch, ta thu được nghiệm tối ưu $x^*=R^{-1} Q^T y$. Công thức này cũng tương tự như công thức trên, vì
$$
\left(A^T A\right)^{-1} A^T y=\left(R^T Q^T Q R\right)^{-1} R^T Q^T y=\left(R^T R\right)^{-1} R^T Q^T y=R^{-1} Q^T y .
$$
Do đó, để tìm nghiệm dựa trên phân tích QR, ta chỉ cần thực hiện hai bước:
- Xoay véctơ đầu ra: đặt $\bar{y}=Q^T y$.
- Giải hệ phương trình tam giác $R x=\bar{y}$ bằng phép thế ngược.
23.4. Nghiệm tối ưu và tập tối ưu
Nhắc lại rằng \textit{tập tối ưu} của một bài toán tối thiểu hóa là tập hợp các phần tử tối thiểu hóa của nó. Đối với bài toán bình phương tối thiểu, tập tối ưu là một tập afin, và tập này thu về một tập đơn tử khi $A$ có hạng cột đầy đủ.
Trong trường hợp tổng quát ($A$ không nhất thiết là ma trận cao, và/hoặc không có hạng đầy đủ) thì nghiệm có thể không phải là duy nhất. Nếu $x^0$ là một nghiệm riêng, thì $x=x^0+z$ cũng là một nghiệm, nếu $z$ sao cho $A z=0$, tức là, $z \in \mathbf{N}(A)$. Tức là, không gian hạt nhân của $A$ mô tả sự không duy nhất của các nghiệm. Theo ngôn ngữ toán học:
\[ \underset{x}{\text{argmin}} \|A x-y\|_2 = x^0 + \mathbf{N}(A) . \]
Biểu thức hình thức cho tập hợp các phần tử tối thiểu hóa của bài toán bình phương tối thiểu có thể được tìm lại thông qua phân tích QR. Điều này được trình bày tại đây.
