"

25

25.1. Ví dụ mở đầu

[latexpage]

Xét một mô hình tự hồi quy tuyến tính cho chuỗi thời gian, trong đó $y_t$ là một hàm tuyến tính của $y_{t-1},y_{t-2}$:

$$
y_t=w_1+w_2 y_{t-1}+w_3 y_{t-2}, \quad t=1, \ldots, T
$$

Ta có thể viết $y_t=w^T x_t$, với $x_t$ là các “véc-tơ đặc trưng”

$$
x_t:=\left(1, y_{t-1}, y_{t-2}\right), \quad t=1, \ldots, T .
$$

Ta có thể khớp mô hình này dựa trên dữ liệu quá khứ thông qua bình phương tối thiểu:

$$
\min _{w}\left\|X^T w-y\right\|_2^2
$$

Quy tắc dự báo tương ứng là

\[ \hat{y}_{T+1} = w_1 + w_2 y_T + w_3 y_{T-1} = w^T x_{T+1} \]

Ta có thể giới thiệu một phiên bản phi tuyến, trong đó $y_t$ là một hàm bậc hai của $y_{t-1}, y_{t-2}$:

$$
y_t=w_1+w_2 y_{t-1}+w_3 y_{t-2}+w_4 y_{t-1}^2+w_5 y_{t-1} y_{t-2}+w_6 y_{t-2}^2 .
$$

Ta có thể viết $y_t=w^T \phi\left(x_t\right)$, với $\phi\left(x_t\right)$ là các véctơ đặc trưng mở rộng

$$
\phi\left(x_t\right):=\left(1, y_{t-1}, y_{t-2}, y_{t-1}^2, y_{t-1} y_{t-2}, y_{t-2}^2\right) .
$$

Dùng thủ thuật tương tự, chỉ thay $x$ bằng $\phi(x)$.

Ở đây, kích thước của bài toán bình phương tối thiểu tăng nhanh theo bậc của các véctơ đặc trưng. Như vậy, làm thế nào để chúng ta thực hiện điều này một cách hiệu quả về mặt tính toán?

25.2. Phương pháp sử dụng hạt nhân

Ta khai thác một thực tế đơn giản: trong bài toán bình phương tối thiểu

$$
\min _w\left\|X^T w-y\right\|_2^2+\lambda\|w\|_2^2
$$

véctơ $w$ tối ưu nằm trong bao tuyến tính của các điểm dữ liệu $\left(x_1, \ldots, x_m\right)$:

$$
w=X v
$$

với một véctơ $v \in \mathbb{R}^m$ nào đó. Thật vậy, từ định lý cơ bản của đại số tuyến tính, mọi $w \in \mathbb{R}^n$ có thể được viết thành tổng của hai véctơ trực giao:

$$
w=X v+r
$$

trong đó $X^T r=0$, có nghĩa là $r$ nằm trong không gian hạt nhân $\mathbf{N}(X^T)$.

Do đó, bài toán bình phương tối thiểu chỉ phụ thuộc vào $K:=X^T X$:

$$
\min _v\|K v-y\|_2^2+\lambda v^T K v .
$$

Quy tắc dự báo phụ thuộc vào các tích vô hướng giữa điểm mới $x$ và các điểm dữ liệu $x_1, \ldots, x_m$:

$$
w^T x=v^T X^T x=v^T k, \quad k:=X^T x=\left(x^T x_1, \ldots, x^T x_m\right) .
$$

Một khi $K$ được tạo ra (mất $O(n)$), thì bài toán huấn luyện chỉ có $m$ biến. Khi $n \gg m $, điều này dẫn đến sự giảm đáng kể về kích thước bài toán.

25.3. Trường hợp phi tuyến

Trong trường hợp phi tuyến, ta chỉ cần thay thế các véctơ đặc trưng $x$ bằng các véctơ đặc trưng “mở rộng” $\phi\left(x_i\right)$, với $\phi$ là một ánh xạ phi tuyến.

Điều này dẫn đến ma trận hạt nhân được viết lại:

$$
K_{i j}=\phi\left(x_i\right)^T \phi\left(x_j\right), \quad 1 \leq i, j \leq m .
$$

Hàm hạt nhân tương ứng với ánh xạ $\phi$ là

$$
k(x, z)=\phi(x)^T \phi(z) .
$$

Nó cung cấp thông tin về metric trong không gian đặc trưng, ví dụ:

$$
\|\phi(x)-\phi(z)\|_2^2=k(x, x)-2 k(x, z)+k(z, z) .
$$

Các tính toán liên quan đến việc

1. giải bài toán huấn luyện;

2. đưa ra dự báo

chỉ phụ thuộc vào khả năng tính toán nhanh các tích vô hướng như vậy của chúng ta. Ta không thể chọn $k$ một cách tùy ý; nó phải thỏa mãn đẳng thức trên với một ánh xạ $\phi$ nào đó.

25.4. Ví dụ về hạt nhân

Có nhiều loại hạt nhân khác nhau. Một số được điều chỉnh cho phù hợp với cấu trúc của dữ liệu, ví dụ như văn bản hoặc hình ảnh. Dưới đây là một vài lựa chọn phổ biến.

Các hạt nhân đa thức

Hồi quy với các hàm bậc hai liên quan đến các véctơ đặc trưng

$$
\phi(x)=\left(1, x_1, x_2, x_1^2, x_1 x_2, x_2^2\right) .
$$

Thực tế, với hai véctơ $x, z \in \mathbb{R}^2$, ta có

$$
\phi(x)^T \phi(z)=\left(1+x^T z\right)^2 .
$$

Tổng quát hơn, khi $\phi(x)$ là véctơ được tạo thành từ tất cả các tích giữa các thành phần của $x \in \mathbb{R}^n$, lên đến bậc $d$, thì với bất kỳ hai véctơ $x, z \in \mathbb{R}^n$ nào,

$$
\phi(x)^T \phi(z)=\left(1+x^T z\right)^d .
$$

Khối lượng tính toán tăng tuyến tính theo $n$.

Điều này thể hiện sự giảm tốc độ đáng kể so với cách tiếp cận tự nhiên, đó là

1. Xét $\phi(x), \phi(z)$;

2. Tính $\phi(x)^T \phi(z)$. Trong cách tiếp cận trên, công sức tính toán tăng theo $n^d$.

Các hạt nhân Gauss

Hàm hạt nhân Gauss:

$$
k(x, z)=\exp \left(-\frac{\|x-z\|_2^2}{2 \sigma^2}\right),
$$

trong đó $\sigma>0$ là một tham số tỉ lệ. Điều này cho phép bỏ qua các điểm ở quá xa nhau. Tương ứng với một ánh xạ phi tuyến $\phi$ đến không gian đặc trưng vô hạn chiều.

25.5. Tổng kết

1. Chúng ta cần lựa chọn loại hạt nhân.

2. Sự lựa chọn không phải lúc nào cũng rõ ràng; các hạt nhân Gauss hoặc hạt nhân đa thức là những lựa chọn phổ biến.

3. Chúng ta kiểm soát hiện tượng \textit{quá khớp} thông qua \textit{kiểm định chéo} (để chọn, chẳng hạn, tham số tỉ lệ của hạt nhân Gauss, hoặc bậc của hạt nhân đa thức).

License

Icon for the Public Domain license

This work (Đại số tuyến tính by Tony Tin) is free of known copyright restrictions.