Khi điều chỉnh một mô hình dự đoán, điều gì được thay đổi và điều gì phải giữ cố định? Câu hỏi này phân biệt dữ liệu với biến quyết định. Nếu chưa xác định rõ hai vai trò ấy, ta chưa có một bài toán tối ưu hoàn chỉnh.

1. Biến, mục tiêu và ràng buộc

Một quyết định nhiều thành phần được biểu diễn bằng vector cột

$$x=\left[\begin{array}{c}{x}_1\\ x_2\\ vdots\\ x_n\end{array}\right]\in {\mathbb{R}}^n.$$

Cho hàm mục tiêu $f$ và các hàm ràng buộc $f_i$, đều nhận đầu vào trong ${\mathbb{R}}^n$ và trả về một số thực. Các ngưỡng $b_1,\dots ,b_m$ là dữ liệu cố định. Bài toán là

$$\begin{array}{rl}& \underset{x}{min}f(x),\\ & f_i(x)\le b_i,i=1,\dots ,m.\end{array}$$

Miền khả thi $D$ gồm tất cả các điểm thỏa đồng thời các ràng buộc. Một $x\in D$ là phương án khả thi. Điểm $x^{\star }$ là phương án tối ưu nếu

$$\begin{array}{rl}& x^{\star }\in D,\\ f(x^{\star })& \le f(x),\mathrm{\forall }x\in D.\end{array}$$

Giá trị nhỏ nhất khi đạt được là $f_{min}=f(x^{\star })$. Nếu chưa biết có đạt nghiệm hay không, dùng cận dưới đúng $p^{\star }=\underset{x\in D}{inf}f(x)$. Chẳng hạn, min $x$ trên $x>0$ có cận dưới bằng không nhưng không có điểm khả thi đạt cận ấy.

Trong quy hoạch nguyên, biến phải có tọa độ nguyên, nên miền được thay bằng $D\cap {\mathbb{Z}}^n$. Hạn chế này thay đổi những quyết định được phép chọn, không chỉ thay đổi cách tính.

2. Học có giám sát và hàm mất mát

Để tránh nhầm miền khả thi với tập dữ liệu, ký hiệu tập dữ liệu bằng $\mathcal{D}$:

$$\begin{array}{rl}\mathcal{D}& =\{(x_1,y_1),\dots ,(x_N,y_N)\},\\ & x_i\in {\mathbb{R}}^d,y_i\in {\mathbb{R}}^k.\end{array}$$

Mỗi $x_i$ là một đầu vào có $d$ đặc trưng, còn $y_i$ là đầu ra đích có $k$ thành phần. Nhiệm vụ là tìm hàm dự đoán từ ${\mathbb{R}}^d$ sang ${\mathbb{R}}^k$. Khi chọn một họ mô hình $f_a$, vector tham số $a\in {\mathbb{R}}^p$ quyết định mô hình cụ thể.

Hàm mất mát $\ell$ nhận dự đoán và đầu ra đích, rồi đo mức sai lệch. Một lựa chọn là khoảng cách Euclid. Với hai đầu ra $u,v\in {\mathbb{R}}^k$,

$$\begin{array}{rl}\ell (u,v)& =\parallel u-v{\parallel }_2,\\ \ell (u,v{)}^2& =(u_1-v_1{)}^2+\cdots +(u_k-v_k{)}^2.\end{array}$$

Đặt ${\ell }_i(a)=\ell (f_a(x_i),y_i)$ là mất mát ở quan sát thứ $i$. Hàm mục tiêu trên tập huấn luyện là trung bình mất mát. Viết trước các số hạng rồi mới dùng ký hiệu tổng:

$$\begin{array}{rl}L(a,\mathcal{D})& =\frac{{\ell }_1(a)+\cdots +{\ell }_N(a)}{N}\\ & =\frac{1}{N}\sum _{i=1}^N\ell (f_a(x_i),y_i).\end{array}$$

Như vậy, huấn luyện là tìm $a$ làm $L$ nhỏ nhất. Dữ liệu và họ mô hình được giữ cố định. Chỉ tham số được điều chỉnh. Ký hiệu $\arg \underset{a}{min}L$ chỉ tập các tham số đạt giá trị nhỏ nhất, khác với $\underset{a}{min}L$ là một giá trị số.

3. Hồi quy affine với đầu ra vô hướng

Xét $k=1$. Mô hình tuyến tính có hệ số chặn được viết

$$\begin{array}{rl}a& =(a_0,a_1,\dots ,a_d{)}^T,\\ f_a(x)& =a_0+a_1{x}_1+\cdots +a_d{x}_d\\ & =a_0+\sum _{j=1}^d{a}_j{x}_j.\end{array}$$

Tên gọi hồi quy tuyến tính nói đến tính tuyến tính theo các hệ số. Khi $a_0\ne 0$, ánh xạ theo đầu vào là affine. Nếu muốn viết một tích vô hướng duy nhất, thêm tọa độ 1 vào đầu vào.

Chọn mất mát bình phương $\ell (u,v)=(u-v{)}^2$. Đặt sai số dự đoán ở quan sát thứ $i$ là $r_i$. Khi đó

$$\begin{array}{rl}{r}_i& =a_0+\sum _{j=1}^d{a}_j{x}_{ij}-y_i,\\ L(a,\mathcal{D})& =\frac{1}{N}\sum _{i=1}^N{r}_i^2.\end{array}$$

Ở đây $x_{ij}$ là đặc trưng thứ $j$ của quan sát thứ $i$. Mỗi số hạng là bình phương sai số của một quan sát. Tổng bên trong dự đoán đã được khai triển ở công thức mô hình.

4. Ma trận thiết kế

Đặt ma trận $X$ có $N$ hàng và $d+1$ cột, hàng thứ $i$ là $(1,x_i^T)$. Khai triển cấu trúc này:

$$X=\left[\begin{array}{cccc}1& x_{11}& \cdots & x_{1d}\\ 1& x_{21}& \cdots & x_{2d}\\ ⋮& ⋮& & ⋮\\ 1& x_{N1}& \cdots & x_{Nd}\end{array}\right].$$

Gom các đầu ra vào $y=(y_1,\dots ,y_N{)}^T$. Tích ma trận $Xa$ là vector dự đoán, vì hàng thứ $i$ cho

$$(Xa{)}_i=a_0+a_1{x}_{i1}+\cdots +a_d{x}_{id}.$$

Đặt phần dư $r=Xa-y$. Từ định nghĩa chuẩn Euclid,

$$\begin{array}{rl}L(a,\mathcal{D})& =\frac{r_1^2+\cdots +r_N^2}{N}\\ & =\frac{1}{N}\sum _{i=1}^N{r}_i^2\\ & =\frac{1}{N}\parallel Xa-y{\parallel }_2^2.\end{array}$$

Vì bình phương là hàm tăng trên các số không âm và $N>0$, cực tiểu hóa $L$ tương đương cực tiểu hóa $\parallel Xa-y{\parallel }_2$. Hai bài có cùng tập nghiệm, nhưng giá trị mục tiêu khác nhau.

5. Phép chiếu và phương trình chuẩn

Mọi vector dự đoán có dạng $Xa$, nên nằm trong không gian cột $W=\mathrm{Col}(X)$. Viết các cột là $X_0,\dots ,X_d$ thì

$$Xa=a_0{X}_0+a_1{X}_1+\cdots +a_d{X}_d.$$

Bài toán tìm điểm $\hat{y}\in W$ gần $y$ nhất. Hình học của nghiệm là phép chiếu trực giao

$$\hat{y}={\mathrm{proj}}_W(y).$$

Vector từ dự đoán tới dữ liệu vuông góc với $W$. Vì thế $X^T(y-Xa)=0$, tương đương phương trình chuẩn

$$X^{T}Xa=X^{T}y.$$

Cũng có thể tính gradient của $L$:

$${\mathrm{\nabla }}_{a}L=\frac{2}{N}{X}^T(Xa-y).$$

Hessian là $2X^{T}X/N$, luôn nửa xác định dương. Do đó phương trình chuẩn đủ để chứng nhận tối ưu. Nếu $X$ có hạng cột đầy đủ thì $X^{T}X$ khả nghịch và hệ số tối ưu duy nhất. Nếu các cột phụ thuộc, dự đoán tối ưu vẫn duy nhất nhưng hệ số có thể không duy nhất. Trong tính toán số, có thể dùng QR hoặc SVD để giải bình phương tối thiểu, tránh hình thành nghịch đảo một cách trực tiếp.

Ví dụ: Mở từng bước của một hồi quy nhỏ

Lấy ba quan sát $(0,1)$, $(1,2)$ và $(2,2)$, dùng mô hình $a_0+a_{1}x$. Đây là ví dụ bổ sung để đọc được phương trình chuẩn.

$$\begin{array}{rl}& X=\left[\begin{array}{cc}1& 0\\ & 11\\ & 12\end{array}\right],\\ & y=\left[\begin{array}{c}1\\ & 2\\ & 2\end{array}\right],\\ & X^{T}X=\left[\begin{array}{cc}3& 3\\ & 35\end{array}\right],\\ & X^{T}y=\left[\begin{array}{c}5\\ & 6\end{array}\right].\end{array}$$

Giải hệ được $a_0=7/6$, $a_1=1/2$. Phần dư là $(1/6,-1/3,1/6{)}^T$. Tổng phần dư bằng không và tích vô hướng với cột đặc trưng cũng bằng không. Mất mát trung bình là $1/18$.

6. Câu hỏi ôn lại

Bài tập: Không gian dự đoán và hệ số

Nếu hai cột của $X$ giống nhau, vì sao không thể kết luận hệ số hồi quy duy nhất? Dự đoán tối ưu có còn duy nhất không?

Lời giải

Nếu hai cột giống nhau, tăng một hệ số một lượng $t$ rồi giảm hệ số kia cùng lượng ấy không thay đổi $Xa$. Vì thế có thể có nhiều hệ số cho cùng dự đoán. Tuy nhiên, phép chiếu trực giao lên không gian con $W$ là duy nhất, nên vector dự đoán tối ưu vẫn duy nhất.

Đọc tiếp quy hoạch tuyến tính để thấy một kiểu hình học tối ưu khác: Nghiệm xuất hiện tại biên của miền khả thi.