13Máy vector hỗ trợ#

Quay lại perceptron ở Mục 6.2: trên dữ liệu tách được, nó dừng ở siêu phẳng tách đúng đầu tiên mà nó tìm được, trong khi có vô số siêu phẳng như vậy. Với phiên bản tách được của sáu sinh viên ở Mục 6.5, ba người ôn 1, 2, 3 giờ trượt và ba người ôn 4, 5, 6 giờ đỗ, nên mọi ngưỡng nằm giữa 3 và 4 giờ đều tách đúng. Perceptron xuất phát từ $w = 0$, duyệt lần lượt sáu người theo thứ tự, và dừng ở $w = 3$, hệ số chặn $-10$, tức ngưỡng $3\tfrac13$ giờ, cách sinh viên 3 chỉ một phần ba giờ. Máy vector hỗ trợ (support vector machine, SVM) đặt ra một tiêu chí để chọn giữa chúng: lấy siêu phẳng cách xa dữ liệu nhất. Tiêu chí đơn giản này dẫn tới một bài toán tối ưu có ràng buộc, và toàn bộ công cụ của Chương 11 và 12 giờ được dùng tới: bài toán là lồi, điều kiện bù chỉ ra những điểm quyết định nghiệm, và bài toán đối ngẫu mở đường cho kernel, cách để SVM vẽ được biên quyết định phi tuyến.

13.1Ý tưởng lề cực đại#

Khi dữ liệu tách được tuyến tính, có vô số siêu phẳng tách đúng hai lớp. Perceptron dừng ở siêu phẳng đầu tiên nó tìm được, và siêu phẳng đó có thể nằm sát một điểm dữ liệu. Một điểm mới ở gần điểm đó, chỉ lệch đi một chút vì nhiễu, có thể bị phân loại sai.

SVM chọn siêu phẳng có lề lớn nhất, tức khoảng cách từ siêu phẳng tới điểm dữ liệu gần nhất là lớn nhất. Siêu phẳng như vậy nằm "chính giữa" khoảng trống giữa hai lớp. Với sáu sinh viên tách được, đó là ngưỡng 3,5 giờ, cách đều sinh viên 3 và sinh viên 4 nửa giờ. Trực giác là biên càng xa dữ liệu thì càng chịu được nhiễu. Lý thuyết học thống kê (Vapnik, 1995) chính xác hoá trực giác này: với dữ liệu nằm trong hình cầu bán kính $R$, chiều VC của lớp các siêu phẳng có lề ít nhất $\gamma$ không vượt quá $\min\big(\lceil R^2/\gamma^2\rceil, d\big) + 1$. Khi lề đủ rộng, độ phức tạp của mô hình được kiểm soát bởi tỉ số $R/\gamma$ chứ không bởi số chiều. Tỉ số này cũng là đại lượng xuất hiện trong định lý Novikoff ở Mục 6.2.

13.2Bài toán tối ưu của SVM lề cứng#

Theo Định lý 2.1, khoảng cách từ $x_i$ tới siêu phẳng $w^\top x + b = 0$ là $|w^\top x_i + b|/\|w\|$. Siêu phẳng không đổi nếu nhân $w$ và $b$ với cùng một số dương, nên ta có thể chọn thang đo sao cho điểm gần nhất thoả $|w^\top x_i + b| = 1$. Khi đó mọi điểm thoả $y_i(w^\top x_i + b) \ge 1$, và khoảng cách giữa hai siêu phẳng $w^\top x + b = +1$ và $w^\top x + b = -1$, tức độ rộng của lề, bằng $2/\|w\|$.

Cực đại $2/\|w\|$ tương đương cực tiểu $\|w\|$, và tương đương cực tiểu $\tfrac12\|w\|^2$, dạng thuận tiện hơn vì khả vi.

Định nghĩa 13.1 (SVM lề cứng)

Với dữ liệu tách được tuyến tính, SVM lề cứng giải bài toán

$$\min_{w,b} \;\tfrac12\|w\|^2 \qquad\text{với}\qquad y_i(w^\top x_i + b) \ge 1, \quad i = 1, \dots, n.$$

Hàm mục tiêu là hàm bậc hai lồi với Hessian bằng ma trận đơn vị, còn các ràng buộc là affine. Đây là một bài toán quy hoạch toàn phương lồi ở đúng dạng chuẩn của Mục 12.1, nên có nghiệm duy nhất và mọi công cụ của Chương 12 đều áp dụng được.

Với sáu sinh viên tách được, mỗi người có một ràng buộc $y_i(w x_i + b) \ge 1$, với $y_i = -1$ cho người trượt và $+1$ cho người đỗ. Hai ràng buộc chặt nhất thuộc về hai người gần ngưỡng nhất: sinh viên 4 cần $4w + b \ge 1$, sinh viên 3 cần $3w + b \le -1$. Trừ hai bất đẳng thức cho nhau được $w \ge 2$. Muốn $\tfrac12 w^2$ nhỏ nhất thì lấy $w = 2$, kéo theo $b = -7$. Biên $2x - 7 = 0$ nằm ở 3,5 giờ, và lề rộng $2/w = 1$ giờ, đúng khoảng trống từ 3 tới 4 giờ. Bốn người còn lại thoả ràng buộc với dư: sinh viên 2 và 5 có $y_i(w x_i + b) = 3$, sinh viên 1 và 6 có 5.

13.3Bài toán đối ngẫu và vector hỗ trợ#

Viết ràng buộc ở dạng chuẩn, $1 - y_i(w^\top x_i + b) \le 0$, và lập hàm Lagrange:

$$\mathcal{L}(w, b, \alpha) = \tfrac12\|w\|^2 + \sum_{i=1}^n \alpha_i\big[1 - y_i(w^\top x_i + b)\big], \qquad \alpha_i \ge 0.$$

Cho đạo hàm theo $w$ và $b$ bằng 0, ta được

$$\begin{aligned} \nabla_w \mathcal{L} &= w - \sum_i \alpha_i y_i x_i = 0 \;\Longrightarrow\; w = \sum_{i}\alpha_i y_i x_i, \\ \frac{\partial\mathcal{L}}{\partial b} &= -\sum_i \alpha_i y_i = 0. \end{aligned}$$

Thay $w$ trở lại hàm Lagrange, số hạng chứa $b$ biến mất nhờ $\sum_i \alpha_i y_i = 0$, và ta được bài toán đối ngẫu.

Định lý 13.1 (Bài toán đối ngẫu của SVM lề cứng)

$$\begin{aligned} \max_{\alpha} \quad & \sum_i \alpha_i - \tfrac12\sum_{i,j}\alpha_i\alpha_j y_i y_j \, x_i^\top x_j \\ \text{với} \quad & \alpha_i \ge 0, \quad \sum_i\alpha_i y_i = 0. \end{aligned}$$

Từ nghiệm $\alpha^*$, trọng số là $w^* = \sum_i \alpha_i^* y_i x_i$, và bộ phân loại là $f(x) = \sum_i \alpha_i^* y_i\, x_i^\top x + b^*$.

Từ định lý rút ra ngay hai điều. Điều thứ nhất là $w^*$ là tổ hợp tuyến tính của các điểm dữ liệu, với trọng số $\alpha_i^* y_i$. Điều thứ hai đến từ điều kiện bù (Mục 12.4): $\alpha_i^*\,[1 - y_i(w^{*\top} x_i + b^*)] = 0$, nên $\alpha_i^* > 0$ chỉ có thể xảy ra với những điểm có $y_i(w^{*\top} x_i + b^*) = 1$, tức nằm đúng trên lề. Các điểm đó gọi là vector hỗ trợ. Mọi điểm khác có $\alpha_i^* = 0$ và không đóng góp gì vào $w^*$.

Hệ số chặn $b^*$ tính được từ một vector hỗ trợ bất kỳ: vì $y_s(w^{*\top} x_s + b^*) = 1$ và $y_s^2 = 1$, ta có $b^* = y_s - w^{*\top} x_s$. Trên thực tế người ta lấy trung bình trên mọi vector hỗ trợ để giảm sai số số học.

Với sáu sinh viên tách được, chỉ sinh viên 3 và 4 nằm trên lề, nên chỉ $\alpha_3$ và $\alpha_4$ có thể khác 0. Điều kiện $\sum_i \alpha_i y_i = 0$ cho $\alpha_3 = \alpha_4$, và $w = \alpha_4 \cdot 4 - \alpha_3 \cdot 3 = \alpha_4$. Vì $w = 2$, ta được $\alpha_3 = \alpha_4 = 2$. Giá trị bài toán đối ngẫu là $\alpha_3 + \alpha_4 - \tfrac12 w^2 = 4 - 2 = 2$, bằng giá trị $\tfrac12 w^2 = 2$ của bài toán gốc, và hệ số chặn tính từ sinh viên 4 là $b = 1 - 2 \cdot 4 = -7$. Bốn sinh viên còn lại có $\alpha_i = 0$: bỏ họ khỏi dữ liệu, nghiệm không đổi.

Thí nghiệm giải SVM bằng thư viện libsvm (qua scikit-learn) trên 120 điểm tách được, rồi kiểm tra các khẳng định trên từ nghiệm đối ngẫu:

Dung lai w tu nghiem doi ngau: lech so voi coef_ cua sklearn = 0.000e+00
Vector ho tro co thoa y_i(w.x_i + b) = 1 khong? lech lon nhat = 2.523e-08
So vector ho tro: 3 tren 120 diem (2.5%)

Doi ngau manh:
  gia tri bai toan goc  0.5*||w||^2  = 1.1037868651
  gia tri bai toan doi ngau          = 1.1037868254
  khe doi ngau                       = 3.961e-08
Le = 2/||w|| = 1.346085; khoang cach nho nhat tu diem toi sieu phang x 2 = 1.346085

Kết quả khớp với lý thuyết ở cả bốn điểm: công thức $w = \sum_i\alpha_i y_i x_i$ cho đúng vector trọng số của thư viện; các vector hỗ trợ nằm trên lề với sai lệch $2{,}5\times10^{-8}$; khe đối ngẫu bằng $4{,}0\times10^{-8}$, tức bằng 0 trong phạm vi dung sai của bộ giải; và độ rộng lề $2/\|w\|$ đúng bằng hai lần khoảng cách từ điểm gần nhất tới siêu phẳng.

Chỉ 3 trong 120 điểm là vector hỗ trợ. Bỏ 117 điểm còn lại khỏi tập huấn luyện và huấn luyện lại thì nghiệm không đổi. Tính thưa này của SVM là hệ quả trực tiếp của điều kiện bù.

13.4SVM lề mềm#

Bài toán ở Định nghĩa 13.1 vô nghiệm khi dữ liệu không tách được tuyến tính, và ngay cả khi tách được, một điểm nhiễu nằm lẫn sang lớp kia có thể ép lề hẹp lại rất nhiều. SVM lề mềm (Cortes và Vapnik, 1995) cho phép vi phạm lề nhưng tính giá cho mỗi vi phạm.

Định nghĩa 13.2 (SVM lề mềm)

Với các biến bù $\xi_i \ge 0$ và tham số $C > 0$:

$$\begin{aligned} \min_{w,b,\xi} \quad & \tfrac12\|w\|^2 + C\sum_{i=1}^n \xi_i \\ \text{với} \quad & y_i(w^\top x_i + b) \ge 1 - \xi_i, \quad \xi_i \ge 0. \end{aligned}$$

Biến bù $\xi_i$ đo mức vi phạm của điểm thứ $i$: $\xi_i = 0$ nếu điểm nằm ngoài lề và đúng phía, $0 < \xi_i \le 1$ nếu điểm nằm trong lề nhưng vẫn đúng phía, $\xi_i > 1$ nếu điểm bị phân loại sai. Tại nghiệm tối ưu, $\xi_i = \max(0, 1 - y_i(w^\top x_i + b))$, đúng bằng mất mát hinge ở Mục 6.1. Do đó bài toán tương đương với

$$\min_{w,b}\; \tfrac12\|w\|^2 + C\sum_{i=1}^n \max\big(0,\ 1 - y_i(w^\top x_i + b)\big),$$

tức mất mát hinge cộng regularization $\ell_2$. Cách viết này cho thấy SVM lề mềm nằm trong cùng khung với hồi quy logistic có regularization: cùng mô hình tuyến tính, cùng thành phần phạt $\|w\|^2$, khác nhau ở hàm mất mát. Tham số $C$ đóng vai trò nghịch đảo của hệ số regularization: $C$ lớn nghĩa là phạt vi phạm nặng, tức regularization yếu.

Bài toán đối ngẫu của SVM lề mềm giống hệt Định lý 13.1, chỉ thêm chặn trên $\alpha_i \le C$. Điều kiện KKT chia các điểm dữ liệu thành ba nhóm, như bảng dưới.

Sáu sinh viên ban đầu, với sinh viên 3 đỗ và sinh viên 4 trượt, có đủ cả ba nhóm. Dữ liệu này không tách được nên SVM lề cứng vô nghiệm. Với lề mềm và mọi $C \ge 1/3$, nghiệm là $w = 2/3$, $b = -7/3$: biên vẫn ở 3,5 giờ, hai mép lề ở 2 giờ và 5 giờ, lề rộng 3 giờ. Sinh viên 1 và 6 nằm ngoài lề, $y_i f(x_i) = 5/3$, nên $\alpha_i = 0$. Sinh viên 2 và 5 nằm đúng trên mép lề, $y_i f(x_i) = 1$, với $0 < \alpha_i < C$; ở $C = 1$ thì $\alpha_i \approx 0{,}556$. Sinh viên 3 và 4 nằm sai phía, $y_i f(x_i) = -1/3$, nên $\alpha_i = C$. Tăng $C$ thêm nữa không đổi nghiệm, vì tăng $w$ chỉ làm lề hẹp lại mà không cứu được sinh viên 3 và 4: không ngưỡng nào phân loại đúng cả hai người. Ngược lại, khi $C$ nhỏ thì vi phạm rẻ và lề rộng ra: ở $C = 0{,}1$, $w = 0{,}4$, hai mép lề ở 1 giờ và 6 giờ, và cả sáu sinh viên đều là vector hỗ trợ.

Thí nghiệm trên hai lớp chồng lấn nhau, với năm giá trị $C$, đếm số điểm trong từng nhóm.

Với $C$ nhỏ, vi phạm rẻ nên lề rộng (5,61) và rất nhiều điểm vi phạm lề: ở $C = 0{,}003$, cả 114 vector hỗ trợ đều là điểm vi phạm, không điểm nào nằm đúng trên lề. Với $C$ lớn, vi phạm đắt nên lề hẹp lại (1,73) và số vector hỗ trợ giảm còn 45. Từ $C = 3$ trở lên nghiệm gần như không đổi, vì các điểm vi phạm còn lại là những điểm nằm sâu trong vùng chồng lấn, không siêu phẳng nào tránh được, giống sinh viên 3 và 4 ở trên.

Sai số kiểm tra chỉ dao động trong khoảng 0,173 tới 0,180, tức $C$ ảnh hưởng ít tới chất lượng trong thí nghiệm này. Điều đó phản ánh bản chất của dữ liệu: biên tối ưu ở đây vốn là tuyến tính, và SVM tuyến tính không đủ linh hoạt để overfitting đáng kể. Với kernel phi tuyến, mô hình linh hoạt hơn nhiều, và $C$ trở thành siêu tham số quan trọng cần chọn bằng cross-validation.

13.5Kernel#

Bài toán đối ngẫu ở Định lý 13.1 và bộ phân loại $f(x) = \sum_i \alpha_i y_i\, x_i^\top x + b$ chỉ dùng dữ liệu qua các tích vô hướng. Giả sử ta muốn biến đổi dữ liệu sang một không gian đặc trưng mới bằng ánh xạ $\varphi$, chẳng hạn thêm các đặc trưng bậc hai, rồi chạy SVM tuyến tính trong không gian mới. Khi đó ta chỉ cần tính được tích vô hướng trong không gian mới:

$$K(x, x') = \varphi(x)^\top \varphi(x').$$

Hàm $K$ gọi là kernel. Nếu $K$ tính được trực tiếp từ $x$ và $x'$ mà không cần tính $\varphi$, ta làm việc được trong không gian đặc trưng mà không bao giờ phải dựng nó. Kỹ thuật này gọi là thủ thuật kernel (kernel trick).

Ví dụ 13.1

Với $x \in \mathbb{R}^2$, xét $K(x, z) = (x^\top z)^2$. Khai triển:

$$\begin{aligned} (x_1 z_1 + x_2 z_2)^2 &= x_1^2 z_1^2 + 2x_1x_2 z_1z_2 + x_2^2 z_2^2 \\ &= \varphi(x)^\top\varphi(z), \qquad \varphi(x) = \big(x_1^2,\ \sqrt2\,x_1x_2,\ x_2^2\big). \end{aligned}$$

Tính $K$ trực tiếp tốn một tích vô hướng hai chiều và một phép bình phương. Chẳng hạn với $x = (1, 2)$ và $z = (3, -1)$: $x^\top z = 1$ nên $K(x, z) = 1$; còn $\varphi(x) = (1;\ 2\sqrt2;\ 4)$ và $\varphi(z) = (9;\ -3\sqrt2;\ 1)$ cho $\varphi(x)^\top\varphi(z) = 9 - 12 + 4 = 1$. Với $x \in \mathbb{R}^d$ và kernel đa thức bậc $p$, không gian đặc trưng có số chiều cỡ $d^p$, trong khi $K$ vẫn chỉ tốn $O(d)$.

Không phải hàm hai biến nào cũng là một kernel. Điều kiện cần và đủ, theo định lý Mercer, là với mọi tập điểm $x_1, \dots, x_n$, ma trận kernel $[K(x_i, x_j)]_{i,j}$ đối xứng và nửa xác định dương. Điều kiện này bảo đảm bài toán đối ngẫu vẫn lồi. Bảng dưới liệt kê ba kernel thông dụng.

Kernel RBF cho giá trị gần 1 khi hai điểm gần nhau và gần 0 khi chúng xa nhau, nên có thể hiểu nó như một thước đo độ giống nhau. Tham số $\gamma$ quyết định "gần" là bao xa: $\gamma$ lớn làm mỗi điểm chỉ ảnh hưởng một vùng rất nhỏ quanh nó, biên quyết định uốn lượn theo từng điểm và dễ overfitting; $\gamma$ nhỏ làm biên trơn. Không gian đặc trưng của kernel RBF có vô hạn chiều, nhưng mỗi lần tính kernel chỉ tốn $O(d)$.

Thí nghiệm trên dữ liệu hai đường tròn đồng tâm, loại dữ liệu không tách được bằng bất kỳ đường thẳng nào, cho kết quả sau.

Kernel đa thức bậc 2 đạt độ chính xác tuyệt đối vì không gian đặc trưng của nó chứa $x_1^2$ và $x_2^2$, nên chứa $x_1^2 + x_2^2$, bình phương khoảng cách tới tâm, đúng là đại lượng phân biệt hai đường tròn. Ví dụ này minh hoạ một nguyên tắc chung: chọn kernel là đưa vào mô hình một giả thiết về dạng của biên quyết định.

13.6SVM nhiều lớp và chi phí tính toán#

SVM được thiết kế cho hai lớp. Có ba cách mở rộng sang $K$ lớp, tóm tắt trong bảng dưới.

Điểm yếu thật sự của SVM với kernel là chi phí tính toán. Huấn luyện cần làm việc với ma trận kernel $n \times n$, và các thuật toán thực tế như SMO có chi phí trong khoảng $O(n^2)$ tới $O(n^3)$ tuỳ dữ liệu. Khi dự đoán, phải tính kernel giữa điểm mới và mọi vector hỗ trợ, mà số vector hỗ trợ thường tăng tuyến tính theo $n$ khi dữ liệu chồng lấn. Với $n$ cỡ hàng triệu, cả hai chi phí đều quá lớn, trong khi mỗi epoch của SGD trên mạng nơ-ron chỉ tốn chi phí tuyến tính theo $n$. Vì vậy SVM với kernel ít được dùng cho dữ liệu rất lớn, và lý do không nằm ở độ chính xác.

SVM vẫn là lựa chọn tốt khi số điểm dữ liệu vừa phải, tới vài chục nghìn, số đặc trưng lớn so với số điểm, và cần một mô hình mạnh với ít siêu tham số. Với dữ liệu văn bản biểu diễn bằng vector TF-IDF, SVM tuyến tính đến nay vẫn là một mô hình cơ sở rất khó vượt qua.

13.7Tóm tắt#

SVM chọn siêu phẳng có lề lớn nhất, và với thang đo chọn sao cho điểm gần nhất có $|w^\top x + b| = 1$, bài toán trở thành cực tiểu $\tfrac12\|w\|^2$ dưới các ràng buộc affine, một bài toán lồi. Với sáu sinh viên tách được, SVM đặt ngưỡng ở 3,5 giờ với $w = 2$, $b = -7$, trong khi perceptron dừng ở $3\tfrac13$ giờ. Bài toán đối ngẫu cho $w = \sum_i \alpha_i y_i x_i$, và điều kiện bù làm $\alpha_i$ bằng 0 với mọi điểm không nằm trên lề, nên chỉ vài vector hỗ trợ quyết định nghiệm: sinh viên 3 và 4 với $\alpha_3 = \alpha_4 = 2$ trong ví dụ, 3 trên 120 điểm trong thí nghiệm, với khe đối ngẫu cỡ $4 \times 10^{-8}$. SVM lề mềm thêm biến bù và tương đương với mất mát hinge cộng regularization $\ell_2$, với $C$ là nghịch đảo của cường độ regularization; trên sáu sinh viên ban đầu, nó chia các điểm thành ba nhóm của điều kiện KKT, với sinh viên 3 và 4 vi phạm lề ở mọi $C$. Vì bài toán đối ngẫu chỉ dùng tích vô hướng, thay tích vô hướng bằng kernel cho biên phi tuyến mà không phải dựng không gian đặc trưng. Điểm yếu của SVM với kernel là chi phí tăng nhanh theo số điểm dữ liệu.

Mười ba chương đầu đều làm việc với dữ liệu có nhãn. Ba chương còn lại chuyển sang dữ liệu không có nhãn, bắt đầu bằng câu hỏi: trong hàng trăm đặc trưng, những hướng nào thật sự mang thông tin? Chương 14 trả lời bằng PCA.