Linear Regression
Giả sử ta có \(N\) điểm dữ liệu đầu vào \(\bm{x}_1\), \(\bm{x}_2\), ..., \(\bm{x}_N\) với \(\bm{x}_i \in \mathbb{R}^d\). Ứng với từng điểm dữ liệu đầu vào \(\bm{x}_i\) ta có một đầu ra \(y_i\), nghĩa là ta có \(N\) cặp dữ liệu \((\bm{x}_i, y_i)\). Khi đó \(y_i\) được gọi là nhãn (hay label) tương ứng với điểm dữ liệu \(\bm{x}_i\).
Mục tiêu là xây dựng hàm số \(\hat{y} = f(x_1, x_2, \ldots, x_d)\) sao cho tổng sai số của \(y_i\) và \(\hat{y}_i\) là nhỏ nhất, tức là
\[\sum_{i=1}^N \lVert y_i - \hat{y}_i \rVert^2 \to \min.\]
Để hàm số đạt giá trị nhỏ nhất (hoặc lớn nhất) ta tìm cực trị của hàm số và khảo sát. Tuy nhiên không phải hàm số nào cũng đạo hàm được. Một cách tiếp cận đơn giản là sử dụng hàm tuyến tính, dễ xây dựng và luôn khả vi. Ta đặt
\[\hat{y} = f(x_1, x_2, \ldots, x_d) = w_0 + w_1 x_1 + w_2 x_2 + \ldots + w_d x_d.\]
Lúc này, hàm mất mát có dạng
\[\mathcal{L} = \sum_{i=1}^N \lVert y_i - (w_0 + w_1 x_{i1} + w_2 x_{i2} + \ldots + w_d x_{id}) \rVert^2.\]
Bình phương chuẩn Euclid chính là bình phương của vector. Do đó dưới dấu tổng là các hàm số bình phương. Khi đạo hàm riêng theo \(w_j\) ta có
\[\dfrac{\partial \mathcal{L}}{\partial w_j} = \sum_{i=1}^N 2 x_{ij} \cdot \left[ y_i - (w_0 + w_1 x_{i1} + w_2 x_{i2} + \ldots + w_d x_{id}) \right]\]
với \(1 \leqslant j \leqslant d\).
Với \(j = 0\) có chút khác biệt:
\[\dfrac{\partial \mathcal{L}}{\partial w_0} = \sum_{i=1}^N 2 \cdot \left[ y_i - (w_0 + w_1 x_{i1} + \ldots + w_d x_{id}) \right].\]
Ta cho các đạo hàm riêng \(\dfrac{\partial \mathcal{L}}{\partial w_j}\) bằng \(0\) thì được
\[\begin{split}\sum_{i=1}^N x_{ij} (w_0 + w_1 x_{i1} + w_2 x_{i2} + \ldots + w_d x_{id}) & = \sum_{i=1}^N x_{ij} y_i \\ \Leftrightarrow w_0 \sum_{i=1}^N x_{ij} + w_1 \sum_{i=1}^N x_{ij} x_{i1} + w_2 \sum_{i=1}^N x_{ij} x_{i2} \\ + \cdots + w_d \sum_{i=1}^N x_{ij} x_{id} & = \sum_{i=1}^N x_{ij} y_i.\end{split}\]
Bây giờ chúng ta cần biểu diễn các dấu tổng lại thành dạng đại số (ma trận, vector) vì chúng sẽ được sử dụng để nhân với vector \(\bm{w} = (w_0, w_1, \ldots, w_d)\).
Ta có
\[\begin{split}\sum_{i=1}^N x_{ij} = \begin{pmatrix}
1 & 1 & \cdots & 1
\end{pmatrix} \cdot \begin{pmatrix}
x_{1j} \\ x_{2j} \\ \vdots \\ x_{Nj}
\end{pmatrix}.\end{split}\]
Ta cũng có
\[\begin{split}\sum_{i=1}^N x_{ij} x_{i1} = \begin{pmatrix}
x_{11} & x_{21} & \cdots & x_{N1}
\end{pmatrix} \cdot \begin{pmatrix}
x_{1j} \\ x_{2j} \\ \vdots \\ x_{Nj}
\end{pmatrix}.\end{split}\]
Cứ tương tự như vậy, ta xếp các dấu sigma thành dạng cột thì tương đương với
\[\begin{split}\begin{pmatrix}
* & \sum_{i=1}^N x_{ij} & * \\ * & \sum_{i=1}^N x_{ij} x_{i1} & * \\ \vdots & \vdots & \vdots \\ * & \sum_{i=1}^N x_{ij} x_{id} & *
\end{pmatrix} = \begin{pmatrix}
1 & 1 & \cdots & 1 \\ x_{11} & x_{21} & \cdots & x_{N1} \\ \cdots & \cdots & \ddots & \cdots \\ x_{1d} & x_{2d} & \cdots & x_{Nd}
\end{pmatrix} \cdot \begin{pmatrix}
* & x_{1j} & * \\ * & x_{2j} & * \\ \vdots & \vdots & \vdots \\ * & x_{Nj} & *
\end{pmatrix}.\end{split}\]
Ghép các cột theo thứ tự \(j\) từ \(0\) tới \(d\) ta có
\[\begin{split}\begin{pmatrix}
w_0 & w_1 & \cdots & w_d
\end{pmatrix} & \cdot \begin{pmatrix}
1 & 1 & \cdots & 1 \\ x_{11} & x_{21} & \cdots & x_{N1} \\ \cdots & \cdots & \ddots & \cdots \\ x_{1d} & x_{2d} & \cdots & x_{Nd}
\end{pmatrix} \\ & \times \begin{pmatrix}
1 & x_{11} & \cdots & x_{1d} \\ 1 & x_{21} & \cdots & x_{2d} \\ \cdots & \cdots & \ddots & \cdots \\ 1 & x_{N1} & \cdots & x_{Nd}
\end{pmatrix} \\ = \begin{pmatrix}
y_1 & y_2 & \cdots & y_N
\end{pmatrix} & \cdot \begin{pmatrix}
1 & x_{11} & \cdots & x_{1d} \\ 1 & x_{21} & \cdots & x_{2d} \\ \cdots & \cdots & \ddots & \cdots \\ 1 & x_{N1} & \cdots & x_{Nd}
\end{pmatrix}.\end{split}\]
Hay nói cách khác, nếu ta đặt \(\bm{w} = (w_0, w_1, \ldots, w_d)\) là ma trận hàng, \(\bm{X}\) là ma trận có các hàng là các input, thì phương trình trên được viết lại là \(\bm{w} \bm{X}^T \bm{X} = \bm{y} \bm{X}\).
Nếu đặt \(\bm{A} = \bm{X}^T \bm{X}\) và \(\bm{b} = \bm{y} \bm{X}\) thì đây là hệ phương trình theo các ẩn \(w_0\), \(w_1\), ..., \(w_d\). Tuy nhiên không phải lúc nào \(\bm{A}\) cũng khả nghịch nên chúng ta sẽ sử dụng một khái niệm gọi là giả nghịch đảo (hay pseudo-inverse) để tìm nghiệm cho hệ phương trình.
Kí hiệu \(\bm{A}^\dagger\) là giả nghịch đảo của ma trận \(\bm{A}\). Khi đó nghiệm của hệ phương trình là \(\bm{w} = \bm{b} \bm{A}^\dagger\).