Phương pháp phân loại theo lề của SVM tuyến tính (lề cứng/lề mềm)
1. Tổng quan
A. Định nghĩa
Máy vector hỗ trợ (SVM, Support Vector Machine) là mô hình phân loại học có giám sát, trong vô số ranh giới quyết định (siêu phẳng) chia tách hai lớp, chọn siêu phẳng tối đa hóa lề (Margin) — khoảng cách giữa ranh giới và các điểm dữ liệu gần nó nhất (vector hỗ trợ).
Có vô số ranh giới kiểu perceptron "chỉ cần chia được là xong", nhưng vấn đề là ranh giới nào sẽ tổng quát hóa tốt nhất cho dữ liệu mới. Hiểu biết then chốt của SVM là "ranh giới càng cách xa cả hai lớp càng nhiều (= lề càng rộng) thì càng ổn định, không phân loại sai dù dữ liệu biến động đôi chút". Tức là tối đa hóa lề có căn cứ nguyên lý nhằm giảm cận trên của sai số tổng quát hóa (tối thiểu hóa rủi ro cấu trúc, SRM).
B. Bối cảnh xuất hiện và sự cần thiết
Dữ liệu thực tế thường có nhiễu đo lường và sự chồng lấn giữa các lớp, đặc biệt trong tình huống nhiều chiều·ít mẫu khi số đặc trưng nhiều hơn số mẫu (phân loại gen·văn bản, v.v.) thì rủi ro quá khớp (overfitting) rất lớn. SVM lấy lề làm hàm mục tiêu tường minh và xác định ranh giới quyết định chỉ bằng số ít dữ liệu biên gọi là vector hỗ trợ, nên cho hiệu năng phân loại vững chắc trong những môi trường như vậy. Tuy nhiên, vì không thể xử lý cùng một cách tình huống lý tưởng tách được hoàn toàn và tình huống thực tế lẫn nhiễu, phân loại theo lề được chia thành hai nhánh lề cứng và lề mềm.
C. Khái niệm cốt lõi
| Khái niệm | Giải thích | Vì sao quan trọng |
|---|---|---|
| Siêu phẳng (Hyperplane) | Ranh giới quyết định được định nghĩa bởi $w^\top x + b = 0$ | Mặt chuẩn của phân loại |
| Lề (Margin) | Khoảng cách giữa siêu phẳng và dữ liệu gần nhất ($2/\lVert w\rVert$) | Càng rộng thì tổng quát hóa↑ |
| Vector hỗ trợ | Số ít dữ liệu nằm trên biên lề và xác định siêu phẳng | Chỉ những điểm này ảnh hưởng tới nghiệm |
Độ rộng lề là $2/\lVert w\rVert$, nên tối đa hóa lề trở thành bài toán quy hoạch toàn phương lồi (QP) tối thiểu hóa $\lVert w\rVert$ (hoặc $\tfrac12\lVert w\rVert^2$). Dữ liệu không phải vector hỗ trợ dù nhiều đến đâu cũng không làm thay đổi nghiệm, và đây là lý do SVM không nhạy với vài điểm ngoại lai nhưng lại nhạy với dữ liệu gần ranh giới.
2. Hai phương pháp phân loại theo lề
flowchart LR
H[Lề cứng<br/>tách tuyến tính hoàn toàn·không cho phép phân loại sai]
S[Lề mềm<br/>cho phép phân loại sai bằng biến slack ξ·kiểm soát bằng C]
Khác biệt giữa hai phương pháp đến từ "tuân thủ ràng buộc nghiêm ngặt đến mức nào". Lề cứng tuyệt đối không vi phạm ràng buộc rằng mọi điểm phải nằm ngoài lề, còn lề mềm cho phép vi phạm ràng buộc này nhưng bắt trả giá (hình phạt).
A. Lề cứng (Hard Margin)
Siêu phẳng lề cực đại tách tuyến tính hoàn toàn mọi dữ liệu mà không có một phân loại sai hay xâm phạm lề nào.
Lề cứng tối thiểu hóa $\tfrac12\lVert w\rVert^2$ dưới ràng buộc mạnh $y_i(w^\top x_i + b) \ge 1$ với mọi điểm $i$. Vấn đề là ràng buộc này chỉ được thỏa mãn khi dữ liệu thực sự tách được tuyến tính, và chỉ cần một điểm nhiễu hay ngoại lai lọt sang phía bên kia là nghiệm hoàn toàn không tồn tại. Ngay cả khi tách được, một điểm ngoại lai sát ranh giới cũng có thể làm méo mó lớn toàn bộ lề, nên hầu như không được dùng cho dữ liệu thực tế.
| Hạng mục | Nội dung |
|---|---|
| Điều kiện | Tách được tuyến tính (không nhiễu·không chồng lấn) |
| Mục tiêu | $\min \tfrac12\lVert w\rVert^2$ s.t. mọi điểm nằm ngoài lề |
| Giới hạn | Rất nhạy với ngoại lai·nhiễu, không có nghiệm khi không tách được |
B. Lề mềm (Soft Margin)
Cho phép mức độ mỗi dữ liệu xâm phạm lề·bị phân loại sai bằng biến slack $\xi_i \ge 0$, áp hình phạt $C$ lên tổng của chúng để kiểm soát, đồng thời tối đa hóa lề.
Lề mềm đổi hàm mục tiêu thành $\min \tfrac12\lVert w\rVert^2 + C\sum_i \xi_i$ và nới lỏng ràng buộc thành $y_i(w^\top x_i+b) \ge 1-\xi_i$. Tức là dùng $C$ để cân đo hai mục tiêu xung đột "lề rộng" và "ít phân loại sai". Nhờ đó, ngay cả với dữ liệu lẫn nhiễu hoặc không tách được hoàn toàn, nghiệm luôn tồn tại và có được tính vững trước ngoại lai.
| Hạng mục | Nội dung |
|---|---|
| Điều kiện | Áp dụng được cả cho dữ liệu có nhiễu·chồng lấn (dữ liệu thực tế) |
| Mục tiêu | Tối đa hóa lề + tối thiểu hóa hình phạt phân loại sai ($C\sum\xi_i$) |
| Tham số $C$ | Lớn → kìm hãm mạnh phân loại sai (lề↓·quá khớp↑), nhỏ → lề↑·tổng quát hóa↑ (rủi ro dưới khớp) |
$C$ là tay nắm của cán cân độ lệch-phương sai (bias-variance). Khi $C$ rất lớn, mô hình tiến gần lề cứng, cố khớp cả ngoại lai nên phương sai tăng; khi $C$ nhỏ, mô hình bỏ qua một số phân loại sai nên lề rộng ra và độ lệch tăng. Ví dụ, với dữ liệu hai lớp chồng lấn đôi chút, nếu đặt $C$ lớn như 100 thì ranh giới trở nên ngoằn ngoèo do cố tách bằng được vài điểm chồng lấn, còn với $C=1$ thì các điểm đó được hấp thụ bằng slack và thu được ranh giới trơn.
3. So sánh
| Tiêu chí | Lề cứng | Lề mềm |
|---|---|---|
| Phân loại sai | Không cho phép ($\xi=0$) | Cho phép ($\xi \ge 0$) |
| Khả năng chịu nhiễu | Yếu (nghiệm sụp đổ vì ngoại lai) | Mạnh (hấp thụ bằng slack) |
| Tính tồn tại nghiệm | Chỉ khi tách được tuyến tính | Luôn tồn tại |
| Áp dụng | Dữ liệu lý thuyết·tách hoàn toàn | Dữ liệu thực tế (thông dụng) |
Lý do căn bản của khác biệt là có cho phép vi phạm ràng buộc hay không. Lề cứng tuyệt đối không được vi phạm ràng buộc nên toàn bộ nghiệm bị chi phối bởi vị trí của một điểm dữ liệu, còn lề mềm quy đổi vi phạm thành chi phí để hấp thụ nên có thể dùng $C$ để nén ảnh hưởng của số ít ngoại lai.
4. Những điểm cần cân nhắc và hàm ý
- Mặc định trong thực tế là lề mềm: hầu như không có dữ liệu nào không nhiễu, nên dùng lề mềm và tinh chỉnh $C$ bằng kiểm định chéo để cân bằng độ lệch-phương sai.
- Bài toán phi tuyến dùng thủ thuật kernel: khi không thể tách tuyến tính, nếu ánh xạ dữ liệu lên không gian nhiều chiều bằng kernel RBF·đa thức thì ranh giới phi tuyến trong không gian gốc có thể được xử lý như siêu phẳng tuyến tính trong không gian nhiều chiều. Khi đó khái niệm lề vẫn được giữ nguyên.
- Đánh đổi giữa điểm mạnh và giới hạn: vững chắc với dữ liệu nhiều chiều·ít mẫu và có nghiệm duy nhất (tối ưu lồi), nhưng khi số mẫu vượt quá vài trăm nghìn thì chi phí huấn luyện QP ($O(n^2)\sim O(n^3)$) trở nên lớn, và SGD·các mô hình dựa trên cây có thể thực dụng hơn.
- Liên kết: nếu cần đầu ra xác suất thì dùng Platt scaling, phân loại đa lớp thì mở rộng bằng One-vs-Rest/One-vs-One.
Tóm tắt một câu: SVM tuyến tính tối đa hóa lề ($2/\lVert w\rVert$) tới các vector hỗ trợ, được chia thành lề cứng (không cho phép phân loại sai·nghiệm sụp đổ vì ngoại lai) và lề mềm (cho phép phân loại sai bằng slack $\xi$, kiểm soát độ lệch-phương sai bằng $C$), và trong thực tế vốn nhiều nhiễu thì lề mềm được dùng làm mặc định cùng với thủ thuật kernel.