SVM

Lề lớn nhất

Gán nhãn $y_i \in \{-1, +1\}$. Một siêu phẳng $\mathbf{w}^\top\mathbf{x} + b = 0$ phân loại đúng mọi điểm khi $y_i(\mathbf{w}^\top\mathbf{x}_i + b) > 0$. Khoảng cách từ $\mathbf{x}_i$ đến siêu phẳng là

Vì nhân $\mathbf{w}$ và $b$ với cùng một số dương không đổi siêu phẳng, ta chuẩn hóa sao cho các điểm gần nhất thỏa $y_i(\mathbf{w}^\top\mathbf{x}_i + b) = 1$. Khi đó độ rộng lề (margin) giữa hai phía là $2/\lVert\mathbf{w}\rVert$; chẳng hạn $\mathbf{w} = (3, 4)$ có $\lVert\mathbf{w}\rVert = 5$, nên lề rộng $2/5 = 0.4$. Cực đại lề tương đương

Đây là bài toán tối ưu lồi bậc hai: khi dữ liệu tách được thì có nghiệm, và không có cực tiểu địa phương nào để mắc kẹt. Các điểm nằm đúng trên biên lề là vector hỗ trợ (support vectors): chỉ chúng quyết định vị trí vạch, bỏ các điểm khác đi thì vạch không đổi. (Với lề mềm ở mục sau, vector hỗ trợ còn gồm cả các điểm nằm trong lề hoặc bị phân loại sai.)

Lề mềm và hinge loss

Dữ liệu thật hiếm khi tách được hoàn toàn. Lề mềm (soft margin) cho phép vi phạm, có trả giá:

Số hạng thứ hai là hinge loss: bằng 0 nếu điểm nằm đúng phía và ngoài lề, tăng tuyến tính nếu lấn vào lề hoặc sang phía sai. Lại là “phạt + lỗi”, chỉ khác là hệ số đặt ở phía lỗi: $C$ lớn thì ít chịu vi phạm, lề hẹp, dễ overfit; $C$ nhỏ thì lề rộng, mô hình đơn giản hơn.

Lấy siêu phẳng $\mathbf{w} = (3, 4)$, $b = -10$ và ba điểm:

• Điểm $(2, 1)$: $3\cdot2 + 4\cdot1 - 10 = 0$, nằm đúng trên siêu phẳng.
• Điểm $(3, 2)$ nhãn $+1$: $f = 7$, khoảng cách $7/5 = 1.4$, $y f = 7 \ge 1$, hinge loss bằng 0.
• Điểm $(2, 1.1)$ nhãn $+1$: $f = 0.4$, nằm đúng phía nhưng trong lề, hinge loss $= 1 - 0.4 = 0.6$.

So với logistic regression ở bài 2.3, hai mô hình chỉ khác hàm mất mát. Log loss không bao giờ bằng 0, nên mọi điểm đều góp tiếng nói. Hinge loss bằng 0 với điểm “an toàn”, nên chỉ các điểm gần ranh giới mới quan trọng.

Mẹo kernel

Muốn ranh giới cong, cách thô là ánh xạ $\mathbf{x}$ sang không gian đặc trưng lớn hơn $\phi(\mathbf{x})$ rồi chạy SVM tuyến tính ở đó. Điều đặc biệt là dạng đối ngẫu (dual) của bài toán SVM chỉ dùng dữ liệu qua tích vô hướng $\phi(\mathbf{x}_i)^\top\phi(\mathbf{x}_j)$. Nếu có hàm $k$ tính thẳng tích đó, gọi là kernel, thì không bao giờ phải tạo $\phi$:

Ví dụ với $\mathbf{x}, \mathbf{z} \in \R^2$ và $\phi(\mathbf{x}) = \left(x_1^2,\ \sqrt{2}\,x_1x_2,\ x_2^2\right)$:

Một phép nhân vô hướng rồi bình phương thay cho việc lập và nhân hai vector ba chiều. Với kernel RBF (Gaussian)

không gian đặc trưng tương ứng có vô hạn chiều, vậy mà tính kernel chỉ tốn $O(d)$.

Hàm dự đoán khi đó có dạng $f(\mathbf{x}) = \sum_{i \in SV} \alpha_i y_i\, k(\mathbf{x}_i, \mathbf{x}) + b$: một tổng có trọng số theo độ giống giữa điểm mới và các vector hỗ trợ. Nhìn kỹ thì giống kNN có trọng số, nhưng trọng số được học bằng tối ưu. Với RBF và $\gamma = 0.1$, hai điểm $(1, 2)$ và $(4, 6)$ có $\lVert\mathbf{x} - \mathbf{z}\rVert^2 = 25$ nên $k = e^{-2.5} \approx 0.082$. Một điểm test ở rất xa mọi vector hỗ trợ có mọi $k$ gần 0, nên $f$ gần bằng $b$ và dấu của $b$ quyết định nhãn.

Hai tham số C và γ

Với kernel RBF, $\gamma$ quy định “tầm ảnh hưởng” của mỗi vector hỗ trợ. $\gamma$ lớn thì mỗi điểm chỉ ảnh hưởng vùng rất nhỏ quanh nó, ranh giới uốn lượn theo từng điểm. $\gamma$ nhỏ thì ranh giới mượt gần như tuyến tính. Cùng với $C$, đây là hai núm cần dò, luôn trên lưới logarit, ví dụ $C \in \{0.1, 1, 10, 100\}$ và $\gamma \in \{10^{-3}, \dots, 1\}$.

SVM RBF nhạy với khoảng cách; khi các cột khác đơn vị, hãy chuẩn hóa trong Pipeline và kiểm bằng validation.

Chi phí và giới hạn

• Huấn luyện SVM có kernel tốn khoảng $O(n^2)$ đến $O(n^3)$ theo số mẫu. Quá vài chục nghìn mẫu là bắt đầu đuối.
• Với dữ liệu lớn, thưa, nhiều chiều như văn bản, dùng SVM tuyến tính (LinearSVC): rất nhanh và rất tốt.
• SVM không cho xác suất. SVC(probability=True) hiệu chỉnh thêm bằng Platt scaling, chậm hơn và không hoàn hảo.

Đọc score trước khi đọc xác suất

Với $\mathbf w=(3,4)$, $b=-10$, $\lVert\mathbf w\rVert=5$. Mỗi điểm có score $f(\mathbf x)=\mathbf w^\top\mathbf x+b$; dấu quyết định phía của vạch, còn $\lvert f\rvert/5$ mới là khoảng cách hình học. Score 7 không có nghĩa xác suất 70%, vì score có đơn vị phụ thuộc cách đặt $\mathbf w$. Hinge loss lại dùng nhãn có dấu $y\in\{-1,+1\}$; nếu lấy nhãn 0/1 nhân vào công thức, mọi mẫu lớp 0 đều có loss 1, là một lỗi âm thầm.

import numpy as np

w_margin = np.array([3., 4.])
b_margin = -10.
points_margin = np.array([[2., 1.], [3., 2.], [2., 1.1]])
labels_signed = np.array([1., 1., 1.])
scores = points_margin @ w_margin + b_margin
distances = np.abs(scores) / np.linalg.norm(w_margin)
hinge = np.maximum(0., 1. - labels_signed * scores)
print("score:", scores.round(3).tolist())
print("khoảng cách:", distances.round(3).tolist())
print("hinge:", hinge.round(3).tolist())

Kết quảscore: [0.0, 7.0, 0.4]
khoảng cách: [0.0, 1.4, 0.08]
hinge: [1.0, 0.0, 0.6]

Dòng thứ ba tách hai khái niệm: điểm score 0.4 được phân loại đúng phía nhưng vẫn chịu loss 0.6 vì nằm trong lề; điểm score 7 thì loss 0. Điểm nằm ngay trên vạch có score 0, cần quy ước phá hòa khi biến thành nhãn. Thư viện lo phần ấy, nhưng code tay cần ghi rõ.

Kiểm mẹo kernel bằng số

Ta kiểm ví dụ polynomial trong bài bằng cả hai cách: dựng đặc trưng ba chiều rồi tính tích vô hướng, và bình phương tích vô hướng hai chiều.

x_kernel = np.array([1., 2.])
z_kernel = np.array([3., 4.])
def phi2(v):
    a, b = v
    return np.array([a * a, np.sqrt(2.) * a * b, b * b])

print(round(float(phi2(x_kernel) @ phi2(z_kernel)), 6))
print(float((x_kernel @ z_kernel) ** 2))
assert np.allclose(phi2(x_kernel) @ phi2(z_kernel), (x_kernel @ z_kernel) ** 2)

Kết quả121.0
121.0

Hai dòng cùng bằng 121. Ta tính được kernel mà không dựng từng tọa độ của không gian lớn hơn. Cái giá chuyển sang số mẫu: kernel SVM làm việc với quan hệ giữa các cặp mẫu, nên thời gian và bộ nhớ tăng nhanh theo $n$. Hãy đo trên một phần nhỏ dữ liệu trước khi fit cả bộ.

Dùng thư viện

from sklearn.datasets import make_moons
from sklearn.model_selection import GridSearchCV
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC

X, y = make_moons(n_samples=500, noise=0.25, random_state=0)
model = make_pipeline(StandardScaler(), SVC(kernel="rbf"))
grid = GridSearchCV(model, {"svc__C": [0.1, 1, 10, 100], "svc__gamma": [0.01, 0.1, 1, 10]}, cv=5)
grid.fit(X, y)
print(grid.best_params_, round(grid.best_score_, 3))
print("số vector hỗ trợ:", grid.best_estimator_[-1].n_support_.sum(), "trên", len(X))

Kết quả{'svc__C': 1, 'svc__gamma': 10} 0.936
số vector hỗ trợ: 221 trên 500