[ML] Hồi Quy Tuyến Tính (Linear Regression) - Hai's Blog

Học có giám sát (Supervised Learning) được chia ra làm 2 dạng lớn là hồi quy (regression) và phân loại (classification) dựa trên tập dữ liệu mẫu - tập huấn luyện (training data). Với bài đầu tiên này ta sẽ bắt đầu bằng bài toán hồi quy mà cụ thể là hồi quy tuyến tính (linear regression).

Mục lục

• 1. Định nghĩa
• 2. Mô hình
• 3. Chọn hàm cơ bản
  • 3.1. Giữ nguyên đầu vào
  • 3.2. Chuẩn hoá đầu vào
  • 3.3. Đa thức hoá
  • 3.4. Sử dụng hàm Gaussian
  • 3.5. Sử dụng hàm sigmoid
• 4. Ước lượng tham số
• 5. Lập trình
  • 5.1. Ví dụ 1
  • 5.2. Ví dụ 2
• 6. Kết luận

1. Định nghĩa

Mục tiêu của giải thuật hồi quy tuyến tính là dự đoán giá trị của một hoặc nhiều biến mục tiêu liên tục (continuous target variable) $y$ dựa trên một véc-to đầu vào $\mathbf{x}$.

Ví dụ: dự đoán giá nhà ở Hà Nội dựa vào thông tin về diện tích, vị trí, năm xây dựng của ngôi nhà thì $t$ ở đây sẽ là giá nhà và $\mathbf{x}=(x_1,x_2,x_3)$ với $x_1$ là diện tích, $x_2$ là vị trí và $x_3$ là năm xây dựng.

Nếu bạn còn nhớ thì đây chính là phương pháp phân tích hồi quy của xác suất thống kê. Mọi lý thuyết cơ bản của phương pháp này vẫn được giữa nguyên nhưng khi áp dụng cho máy tính thì về mặt cài đặt có thay đổi đôi chút.

Về cơ bản thì ta sẽ có một tập huấn luyện chứa các cặp $(\mathbf{x}^{(i)},y^{(i)})$ tương ứng và nhiệm vụ của ta là phải tìm giá trị $\hat{y}$ ứng với một đầu vào $\mathbf{x}$ mới. Để làm điều này ta cần tìm được quan hệ giữa $\mathbf{x}$ và $y$ để từ đó đưa ra được dự đoán. Hay nói cách trừu tượng hơn là ta cần vẽ được một đường quan hệ thể hiện mối quan hệ trong tập dữ liệu.

Như hình minh họa phía trên thì ta có thể vẽ được một đường màu xanh y=3+4x để thể hiện quan hệ giữa x và y dựa vào các điểm dữ liệu huấn luyện đã biết. Thuật toán hồi quy tuyến tính sẽ giúp ta tự động tìm được đường màu xanh đó để từ đó ta có thể dự đoán được y cho một x chưa từng xuất hiện bao giờ.

Lưu ý về kí hiệu: xem danh sách kí hiệu tại đây.

2. Mô hình

Mô hình đơn giản nhất là mô hình kết hợp tuyến tính của các biến đầu vào: $$y(\mathbf{x},\theta)=\theta_0+\theta_1x_1+…+\theta_{k-1}x_{k-1} ~~~(2.1)$$ trong đó $\mathbf{x}\in\mathbb{R}^{k-1}$ là véc-to biến đầu vào và $\theta\in\mathbb{R}^k$ là véc-to trọng số tương ứng. Thường $\theta$ được gọi là tham số của mô hình. Giá trị của tham số sẽ được ước lượng bằng cách sử dụng các cặp giá trị $(\mathbf{x}^{(i)},y^{(i)})$ của tập huấn luyện.

Thực ra mô hình tuyến tính là chỉ cần ở mức tuyến tính giữa tham số $\theta$ và $y$ là đủ. Và mình cho rằng tên gọi tuyến tính là xuất phát giữa $\theta$ và $y$, chứ không phải giữa $\mathbf{x}$ và $y$. Nói cách khác, ta có thể kết hợp các $\mathbf{x}$ một cách phi tuyến trước khi hợp với $\theta$ để được $y$. Một cách đơn giản là sử dụng hàm phi tuyến cho $\mathbf{x}$ như sau: $$y(\mathbf{x},\theta)=\theta_0+\theta_1\phi_1(\mathbf{x})+…+\theta_{n-1}\phi_{n-1}(\mathbf{x}) ~~~(2.2)$$

$\theta_0$ được gọi là độ lệch (bias) nhằm cắt đi mức độ chênh lệch giữa mô hình và thực tế. Các hàm phi tuyến $\phi_i(\mathbf{x})$ này được gọi là các hàm cơ bản (basic function). Thường người ta sẽ đặt $\phi_0(\mathbf{x})=1$ và viết lại công thức trên như sau: $$y(\mathbf{x},\theta)=\sum_{i=0}^{n-1}\theta_i\phi_i(\mathbf{x})=\theta^{\intercal}\phi(\mathbf{x}) ~~~(2.3)$$

Như quy ước thì tất cả các véc-to nếu không nói gì thì ta ngầm định với nhau rằng nó là véc-to cột nên ta có được cách viết nhân ma trận như trên.

3. Chọn hàm cơ bản

Việc chọn hàm cơ bản $\phi(\mathbf{x})$ cũng chính là chọn tính năng cho đầu vào rất quan trọng trong học máy. Ngoài ra việc chọn ra sao còn ảnh hưởng tới tốc độ và bộ nhớ để tính toán nữa. Ở đây tôi chỉ để cập tới 1 vài cách đơn giản để chọn hàm cơ bản mà thôi.

3.1. Giữ nguyên đầu vào

Giữ nguyên đầu vào có ý là không thay đổi giá trị đầu vào, tức: $$\phi(\mathbf{x})=\mathbf{x}$$

Thường người ta sẽ gom các đầu vào thành một ma trận $\mathbf{X}\in\mathbb{R}^{m\times n}$: $$\mathbf{X}=[\mathbf{x}_1,\mathbf{x}_2,…,\mathbf{x}_m]^{\intercal}$$

Mỗi hàng của ma trận chứa 1 mẫu và mỗi cột sẽ chứa các thuộc tính đầu vào.

3.2. Chuẩn hoá đầu vào

Là phương pháp co giãn các thuộc tính về khoảng $[min,max]$ nào đó (thường là $[-1,1]$ hoặc $[-0.5,0.5]$) dựa vào kì vọng và độ lệch chuẩn của chúng. $$x_i=\frac{x_i-\mu_i}{s_i}$$

Trong đó, $\mu_i$ là trung bình, còn $s_i$ là độ lệch chuẩn của tính năng $i$. Đôi lúc người ta cũng có thể lấy $s_i$ là khoảng rộng chuẩn $s_i=max-min$.

Việc này không làm mất tính chất phân phối của chúng nên không ảnh hưởng tới kết quả học. Nhưng lại giúp cho việc học trở lên dễ dàng hơn vì các thuộc tính gần như cùng khoảng nhỏ với nhau. Phương pháp này còn có tên khác là chuẩn hoá trung bình (mean normalization).

3.3. Đa thức hoá

Sử dụng đa thức bậc cao để làm đầu vào: $$\phi_i(\mathbf{x})=\mathbf{x}^i$$

Với các bài toán hồi quy tuyến tính thì phương pháp này rất hay được sử dụng.

3.4. Sử dụng hàm Gaussian

$$\phi_i(\mathbf{x})=\exp\Bigg(-\frac{(\mathbf{x}-\mu_i)^2}{2s^2}\Bigg)$$

$\mu_i$ ở đây sẽ chỉ định vị trí trung bình cho đầu vào còn $s$ sẽ chỉ định độ phân tán cho đầu vào. Việc sử dụng hàm này sẽ giúp ta có được đầu vào theo phân phối chuẩn.

3.5. Sử dụng hàm sigmoid

Tương tự như hàm Gaussian, ta có thể sử dụng hàm sigmoid để biến đổi đầu vào: $$\phi_i(\mathbf{x})=\sigma\Bigg(-\frac{\mathbf{x}-\mu_i}{s}\Bigg)$$

Hàm sigmoid được sử dụng là sigmoid chuẩn: $$\sigma(z)=\frac{1}{1+\exp(-z)}$$

Một biến thể khác là sử dụng $tanh$ vì nó khá gần với $sigmoid$: $$tanh(z)=2\sigma(2z)-1$$

4. Ước lượng tham số

Giả sử ta có $m$ cặp dữ liệu huấn luyện $(\mathbf{x}_i, y_i)~~~,i=\overline{1,m}$ được tổ chức tương ứng bằng $\mathbf{X}=[\mathbf{x}_1,\mathbf{x}_2,…,\mathbf{x}_m]^{\intercal}, \mathbf{y}=[y_1,y_2,…,y_m]^{\intercal}$ và $\mathbf{\hat{y}}\in\mathbb{R}^m$ là kết quả dự đoán tương ứng. Ta có thể đánh giá mức độ chênh lệch kết quả $\hat{y}$ và $y$ bằng một hàm lỗi (lost function) như sau:

$$ \begin{aligned} J(\theta) &= \frac{1}{2m}\sum_{i=1}^m(\hat{y}_i-y_i)^2 \cr\ &= \frac{1}{2m}\sum_{i=1}^m\Big(\theta^{\intercal}\phi(\mathbf{x}_i)-y_i\Big)^2 &(3.1) \end{aligned} $$

Công thức trên thể hiện trung bình của độ lệch (khoảng cách) giữa các điểm dữ liệu thực tế và kết quả dự đoán sau khi ta ước lượng tham số. Còn tại sao ta lại chia cho 2 thì tôi sẽ giải thích sau. Hàm lỗi còn có tên gọi khác là hàm lỗi bình phương (squared error function) hoặc hàm lỗi trung bình bình phương (mean squared error function) hoặc hàm chi phí (cost function).

Không cần giải thích ta cũng có thể hiểu với nhau rằng tham số tốt nhất là tham số giúp cho hàm lỗi $J$ đạt giá trị nhỏ nhất. $$\hat\theta=\arg\min_{\theta}J(\theta) ~~~(3.2)$$ Kết quả tối ưu nhất là $\mathbf{\hat{y}}=\mathbf{y}$, tức là $J(\theta)=0$. Để giải quyết bài toán này ta có thể sử dụng đạo hàm của $J(\theta)$ và tìm $\theta$ sao cho $J(\theta)^{\prime}=0$. $$ \begin{aligned} \ &0 = \frac{1}{m}\sum_{i=1}^m(\theta^{\intercal}\phi(\mathbf{x}_i)-y_i)\phi(\mathbf{x}_i)^{\intercal} &(3.3) \cr\iff& \sum_{i=1}^m\theta^{\intercal}\phi(\mathbf{x}_i)\phi(\mathbf{x}_i)^{\intercal} = \sum_{i=1}^my_i\phi(\mathbf{x}_i)^{\intercal}&(3.4) \cr\iff&\theta = (\Phi^{\intercal}\Phi)^{-1}\Phi^{\intercal}\mathbf{y} &(3.5) \end{aligned} $$

Đây chính là công thức chuẩn (normal equation) của bài toán ta cần giải. Trong đó ma trận $\Phi\in\mathbb{R}^{m\times n}$ được gọi là ma trận mẫu (design matrix), ta có thể hiểu nó đơn giản là tập mẫu của ta: $$\Phi= \begin{bmatrix} \phi_0(\mathbf{x}_1)&\phi_1(\mathbf{x}_1)&…&\phi_{n-1}(\mathbf{x}_1)\cr \phi_0(\mathbf{x}_2)&\phi_1(\mathbf{x}_2)&…&\phi_{n-1}(\mathbf{x}_2)\cr \vdots&\vdots&\ddots&\vdots\cr \phi_0(\mathbf{x}_m)&\phi_1(\mathbf{x}_m)&…&\phi_{n-1}(\mathbf{x}_m) \end{bmatrix} $$

Để ý rằng ở ma trận $\Phi$ ta sắp mỗi dữ liệu huấn luyện theo hàng ($m$ hàng) và các thuộc tính của chúng theo cột ($n$ cột). Các thuộc tính ở đây được biến đổi bằng các hàm $\phi_i(\mathbf{x}_j)$. Và lưu ý rằng như đã đặt phía trên $\phi_0(\mathbf{x_j}) = 1$ với mọi $j=\overline{1,m}$.

Ở phép lấy đạo hàm (3.3) ta thấy rằng mẫu số 2 bị triệt tiêu và giúp bỏ đi được thừa số 2 khi tính đạo hàm. Đấy chính là lý do mà người ta để mẫu số 2 cho hàm lỗi.

5. Lập trình

Chém gió loằng ngoằng mãi rồi, giờ phải bắt tay vào code thử xem đúng hay sai.

5.1. Ví dụ 1

Ví dụ khởi động này tôi sẽ lấy dữ liệu đơn giản $y=3+4x$ để làm việc. Trước tiên tôi đã chuẩn bị tập dữ liệu huấn luyện gồm 100 cặp dữ liệu được sinh ra theo nhiễu của hàm $y=3+4x$ tại Repo trên Github.

Ở đây tôi sẽ sử dụng các thư viện pandas (xử lý dữ liệu), mathplotlib (đồ hình dữ liệu) và numpy (thao tác toán học) để làm việc:

123	import pandas as pd import numpy as np import matplotlib.pyplot as plt

Dữ liệu của ta chỉ có 1 chiều nên dễ dàng đồ hình hoá, việc này cũng giúp ta ước lượng được đôi chút việc chọn các tiêu chí ràng buộc cho mô hình của ta.

12345678910111213

# load data df = pd.read_csv(DATA_FILE_NAME) # plot data df.plot(x='x', y='y', legend=False, marker='o', style='o', mec='b', mfc='w') # expected line plt.plot(df.values[:,0], df.values[:,1], color='g') plt.xlabel('x'); plt.ylabel('y'); plt.show() # extract X, y X = df.values[:,0] y = df.values[:,2] # number of training examples m = y.size

Nhìn vào biểu đồ của dữ liệu ta có thể nghĩ rằng $x$ ở đây tuyến tính với $y$, tức là ta có thể chọn $\Phi\in\mathbb{R}^{m\times 2}$ với $\phi_1(\mathbf{x_j})=\mathbf{x_j}$. Lúc này ta sẽ có: $$\Phi= \begin{bmatrix} 1&\mathbf{x}_1\cr 1&\mathbf{x}_2\cr \vdots&\vdots&\cr 1&\mathbf{x}_m\cr \end{bmatrix} $$ Như vậy $\Phi$ lúc này đơn giản là bằng với ma trận $\mathbf{X}$ có thêm cột $1$ ở đầu: $$\Phi=\mathbf{X}= \begin{bmatrix} 1&x_1\cr 1&x_2\cr \vdots&\vdots&\cr 1&x_m\cr \end{bmatrix} $$

Lúc này ta có thể viết lại $y$ như sau: $$y=\theta^{\intercal}\mathbf{X}$$

1	X = np.concatenate((np.ones((m,1)), X.reshape(-1,1)), axis=1)

Do $(\Phi^{\intercal}\Phi)$ có thể không khả nghịch nên ta có thể sử dụng phép giả nghịch đảo để làm việc:

1	theta = np.dot(np.linalg.pinv(np.dot(X.T, X)), np.dot(X.T, y))

Phép trên sẽ cho ta kết quả: theta=[-577.17310612, 4.16001358], tức: $$ \begin{cases} \theta_0=-577.17310612\cr \theta_1=4.16001358 \end{cases} $$ Giờ ta sẽ tính kết quả ước lượng và mô phỏng lên hình vẽ xem sao.

123	y_hat = np.dot(X, theta) plt.plot(df.values[:,0], y_hat, color='r') plt.xlabel('x'); plt.ylabel('y'); plt.show()

Ở hình trên, đường màu xanh là đường mà ta mong muốn đạt được còn đường màu đỏ mà mô hình ước lượng được. Như vậy ta thấy rằng $\theta_1$ khá khớp còn $\theta_0$ lại lệch rất nhiều, nhưng kết quả lại khá khớp với tập dữ liệu đang có. Nên ta có thể kì vọng rằng nếu gia tăng khoảng dữ liệu thì công thức chuẩn sẽ cho ta kết quả hợp lý hơn.

Toàn bộ mã nguồn đầy đủ của phần này tôi có để trên Github và ngoài ra còn thêm các phần thực hiện bằng thư viện scikit-learn và TensorFlow để kiểm chứng kết quả đạt được nữa. Cụ thể bạn có xem trên Github hoặc dễ dàng hơn với IPython.

5.2. Ví dụ 2

Phần này ta sẽ phức tạp vấn đề lên 1 chút bằng cách lấy $y=\sin(2\pi x)$. Tương tự như trên tôi đã chuẩn bị dữ liệu trên trên Repo đó. Cụ thể nó sẽ được mô phỏng như sau:

Thấy đường loằng ngoằng kia ta có thể dự đoán rằng nó được tạo bởi đa thức của các biến $x$ như sau: $$y=\theta_0+\theta_1x+\theta_2x^2+…+\theta_nx^n$$

Hay nói cách khác thì $\phi_i(\mathbf{x_j})=\mathbf{x_j}^j$. Ở đây ta chọn lấy $n=3$, ta sẽ có: $$\Phi= \begin{bmatrix} 1&\mathbf{x}_1&\mathbf{x}_1^2&\mathbf{x}_1^3\cr 1&\mathbf{x}_2&\mathbf{x}_2^2&\mathbf{x}_2^3\cr \vdots&\vdots&\vdots&\vdots&\cr 1&\mathbf{x}_m&\mathbf{x}_m^2&\mathbf{x}_m^3\cr \end{bmatrix}$$

Do $\mathbf{x}$ chỉ có 1 phần tử $x$ nên ta có thể viết lại $\Phi$ như sau: $$\Phi= \begin{bmatrix} 1&x_1&x_1^2&x_1^3\cr 1&x_2&x_2^2&x_2^3\cr \vdots&\vdots&\vdots&\vdots&\cr 1&x_m&x_m^2&x_m^3\cr \end{bmatrix}$$

Từ đây ta có thể tính được $\theta=[-0.18829466, 12.07512913, -35.05777051, 23.38720567]$, hay: $$ \begin{cases} \theta_0=-0.18829466\cr \theta_1=12.07512913\cr \theta_2=-35.05777051\cr \theta_3=23.38720567 \end{cases} $$

Kết quả ước lượng có thể được mô hình hoá như sau:

Kết quả lần này cũng khá khớp với dữ liệu mẫu mà ta có được. Nếu bạn quan tâm tới mã nguồn cụ thể thì xem trên Github nhé.

6. Kết luận

Thuật toán hồi quy tuyến tính (linear regression) thuộc vào nhóm học có giám sát (supervised learning) là được mô hình hoá bằng: $$y(\mathbf{x},\theta)=\theta^{\intercal}\phi(\mathbf{x})$$ Khi khảo sát tìm tham số của mô hình ta có thể giải quyết thông qua việc tối thiểu hoá hàm lỗi (loss function): $$J(\theta)=\dfrac{1}{2m}\displaystyle\sum_{i=1}^m\Big(\theta^{\intercal}\phi(\mathbf{x}_i)-y_i\Big)^2$$ Hàm lỗi này thể hiện trung bình độ lệch giữa kết quả ước lượng và kết quả thực tế. Việc lấy bình phương giúp ta có thể dễ dàng tối ưu được bằng cách lấy đạo hàm vì nó có đạo hàm tại mọi điểm! Qua phép đạo hàm ta có được công thức chuẩn (normal equation) cho tham số: $$\hat\theta = (\Phi^{\intercal}\Phi)^{-1}\Phi^{\intercal}\mathbf{y}$$ Trong đó $\Phi\in\mathbb{R}^{m\times n}$: $$\Phi= \begin{bmatrix} \phi_0(\mathbf{x}_1)&\phi_1(\mathbf{x}_1)&…&\phi_{n-1}(\mathbf{x}_1)\cr \phi_0(\mathbf{x}_2)&\phi_1(\mathbf{x}_2)&…&\phi_{n-1}(\mathbf{x}_2)\cr \vdots&\vdots&\ddots&\vdots\cr \phi_0(\mathbf{x}_m)&\phi_1(\mathbf{x}_m)&…&\phi_{n-1}(\mathbf{x}_m) \end{bmatrix} $$

Khi lập trình với python ta có thể giải quyết việc $(\Phi^{\intercal}\Phi)$ không khả nghịch bằng cách sử dụng giả nghịch đảo để tính toán:

np.linalg.pinv(np.dot(X.T, X))

Mặc dù công thức chuẩn có thể tính được tham số nhưng với tập dữ liệu mà lớn thì khả năng sẽ không khít được với bộ nhớ của máy tính, nên trong thực tế người ta thường sử dụng phương pháp đạo hàm để tối ưu. Vậy phương pháp này là gì thì ta sẽ cùng xem xét ở bài viết sau.