Định nghĩa

Support Vector Machine (SVM) là một thuật toán thuộc nhóm Supervised Learning (Học có giám sát) dùng để phân chia dữ liệu (Classification) thành các nhóm riêng biệt.

Hình dung ta có bộ data gồm các điểm xanh và đỏ đặt trên cùng một mặt phẳng.
Ta có thể tìm được đường thẳng để phân chia riêng biệt các bộ điểm xanh và đỏ như hình bên dưới.

Với những bộ data phức tạp hơn mà không thể tìm được đường thẳng để phân chia thì sao?

Ta cần dùng thuật toán để ánh xạ bộ data đó vào không gian nhiều chiều hơn (n chiều), từ đó tìm ra siêu mặt phẳng (hyperplane) để phân chia.
Ví dụ trong hình bên dưới là việc ánh xạ tập data từ không gian 2 chiều sang không gian 3 chiều.

Tối ưu trong thuật toán SVM

Quay lại bài toán với không gian 2 chiều. Ở ví dụ trong hình đầu tiên, ta thấy có thể tìm được rất nhiều các đường thẳng để phân chia 2 bộ điểm xanh, đỏ.

Vậy đường thẳng như thế nào được coi là tối ưu?
Nhìn bằng mắt thường ta có thể thấy, đường tối ưu là đường tạo cho ta có cảm giác 2 lớp dữ liệu nằm cách xa nhau và cách xa đường đó nhất.

Tuy nhiên tính toán sự tối ưu bằng toán học, trong SVM sử dụng thuật ngữ Margin.

Margin

Margin là khoảng cách giữa siêu phẳng (trong trường hợp không gian 2 chiều là đường thẳng) đến 2 điểm dữ liệu gần nhất tương ứng với 2 phân lớp.

SVM cố gắng tối ưu thuật toán bằng các tìm cách maximize giá trị margin này, từ đó tìm ra siêu phẳng đẹp nhất để phân 2 lớp dữ liệu.

Support Vectors

Bài toán của chúng ta trở thành tìm ra 2 đường biên của 2 lớp dữ liệu (ở hình bên trên là 2 đường xanh lá cây) sao cho khoảng cách giữa 2 đường này là lớn nhất.
Đường biên của lớp xanh sẽ đi qua một (hoặc một vài) điểm xanh.
Đường biên của lớp đỏ sẽ đi qua một (hoặc một vài) điểm đỏ.
Các điểm xanh, đỏ nằm trên 2 đường biên được gọi là các support vector, vì chúng có nhiệm vụ support để tìm ra siêu phẳng.
Đó cũng là lý do của tên gọi thuật toán Support Vector Machine.

Cách tính Margin

Trong bài toán không gian 2 chiều, ta giả sử đường thẳng phân chia cần tìm có phương trình là:
$w_1x_1 + w_2x_2 + b = 0$.

Thật ra ta hoàn toàn có thể dùng phương trình đường thẳng hay sử dụng là $ax + by + c = 0$ để tính toán cho quen thuộc. Ở đây ta dùng các giá trị $w_1$, $w_2$, $x_1$, $x_2$ để sau này dễ dàng tổng quát lên không gian nhiều chiều hơn.

Giả sử 2 đường thẳng đi qua các support vector của 2 lớp dữ liệu lần lượt là:
$w_1x_1 + w_2x_2 + b = 1$
$w_1x_1 + w_2x_2 + b = -1$

Vì sao lại là $1$ và $-1$

Ban đầu mình rất băn khoăn về 2 con số này. Sau mới hiểu ra đây chỉ là một phép toán dịch chuyển đường thẳng cơ bản, do mình dốt toán quá mà không hiểu.
Giả sử nếu ta tìm được phương trình 3 đường thẳng tương ứng là:
$2x_1 + 3x_2 + 5 = 0$
$2x_1 + 3x_2 + 9 = 0$
$2x_1 + 3x_2 + 1 = 0$
Vậy ta chỉ cần chia tất cả cho 4 để thu được phương trình như định nghĩa:
$\frac{1}{2}x_1 + \frac{3}{4}x_2 + \frac{5}{4} = 0$
$\frac{1}{2}x_1 + \frac{3}{4}x_2 + \frac{5}{4} = 1$
$\frac{1}{2}x_1 + \frac{3}{4}x_2 + \frac{5}{4} = -1$

Với không gian 2 chiều

Margin giữa 2 đường thẳng được tính bằng công thức:
$\text{margin} = \frac{2}{\sqrt{w_1^2 + w_2^2}}$

Với không gian nhiều chiều

Tổng quát lên không gian nhiều chiều, cần tìm phương trình siêu phẳng có phương trình: $\mathbf{w}^T\mathbf{x} + b = 0$.
Margin sẽ được tính bằng công thức:
$\text{margin} = \frac{2}{||\mathbf{w}||}$

Bài toán tìm Margin cực đại

Bài toán tìm Margin cực đại là một Quadratic Programming, được giải bằng cách giải bài toán đối ngẫu Lagrange (Lagrange dual problem).
Do chỉ là dân tay ngang, lại vốn dốt toán, nên chỉ tìm hiểu đến đây, chi tiết cách giải bài toán này mình xin bỏ qua.

Hiện nay có nhiều thư viện để giải bài toán này như CVOPT, trên thực tế ta chỉ cần sử dụng các thư viện có sẵn cho an toàn thay vì tự cài đặt.

Soft Margin

Để tránh overfitting, nhiều khi để muốn có margin cao, ta chấp nhận việc một vài data có thể không được chia chính xác (ví dụ như 1 bóng xanh bị lọt sang vùng của bóng đỏ). Data này được gọi là nhiễu.

Margin trong trường hợp này gọi là Soft Margin.
Hard Margin ám chỉ việc tìm dc Margin mà không nhiễu (tất cả các data đều thoả mãn sự phân chia).

Với các bái toán thực tế, việc tìm được Hard Margin nhiều khi là bất khả thi, vì thế việc chấp nhận sai lệch ở một mức độ chấp nhận được là vô cùng cần thiết.

Trong cài đặt SVM, người ta giới thiệu tham số $C$ với quy ước:

$C = \infty$
Không cho phép sai lệch, đồng nghĩa với Hard Margin.
$C$ lớn
Cho phép sai lệch nhỏ, thu được Margin nhỏ.
$C$ nhỏ
Cho phép sai lệch lớn, thu được Margin lớn.

Tuỳ bài toán cụ thể mà ta cần điểu chỉnh tham số $C$ này để thu được kết quả tốt nhất.

Ví dụ

Để hiểu rõ thêm ta cùng xét một ví dụ đơn giản.

Ta có 2 lớp dữ liệu như sau:
Positive events $(x_1, x_2) = [(1, 3), (3, 3), (4, 0)]$
Negative events $(x_1, x_2) = [(0, 0), (1, 2), (2, 0)]$

Chạy thử bằng thư viện Scikit-learn

Scikit-learn cung cấp sẵn thư viện để giải SVM là SVC.

Nếu chưa có thư viện này trong máy, ta có thể cài đặt đơn giản bằng pip (thay bằng pip3 nếu muốn cài cho Python 3).

pip install scikit-learn

Ta chỉ cần code một vài dòng đơn giản là có thể chạy thử được thư viện này.

Ở đây ta define 2 lớp dữ liệu: X1 có nhãn positive (1), X2 có nhãn negative (-1).
X là mảng chứa cả 2 lớp dữ liệu X1, X2 y là mảng label của X.

import numpy as np
from sklearn.svm import SVC

X1 = [[1,3], [3,3], [4,0], [3,0], [2, 2]]
y1 = [1, 1, 1, 1, 1]
X2 = [[0,0], [1,1], [1,2], [2,0]]
y2 = [-1, -1, -1, -1]
X = np.array(X1 + X2)
y = y1 + y2

clf = SVC(kernel='linear', C=1E10)
clf.fit(X, y)
print clf.support_vectors_

Ở đoạn code trên ta chọn kernel là linear ám chỉ đường thẳng trong không gian chiều. Chú ý có thể chọn nhiều kernel khác phức tạp hơn, nhưng vì mục đích test, ta chọn linear để chạy cho nhanh.
Ta set C giả trị 1E10 hiểu là một giá trị cực lớn, mục đích để tìm Hard Margin.

Kết quả mảng các support vectors được in ra như sau:

[[1. 2.]
 [1. 3.]
 [3. 0.]]

Ta thêm hàm sau đây, sử dụng thư viện matplotlib để mô phỏng ra dạng đồ thị cho dễ nhìn

import matplotlib.pyplot as plt

def plot_svc_decision_function(clf, ax=None, plot_support=True):
    """Plot the decision function for a 2D SVC"""
    if ax is None:
        ax = plt.gca()
    xlim = ax.get_xlim()
    ylim = ax.get_ylim()

    # create grid to evaluate model
    x = np.linspace(xlim[0], xlim[1], 30)
    y = np.linspace(ylim[0], ylim[1], 30)
    Y, X = np.meshgrid(y, x)
    xy = np.vstack([X.ravel(), Y.ravel()]).T
    P = clf.decision_function(xy).reshape(X.shape)

    # plot decision boundary and margins
    ax.contour(X, Y, P, colors='k',
               levels=[-1, 0, 1], alpha=0.5,
               linestyles=['--', '-', '--'])

    # plot support vectors
    if plot_support:
        ax.scatter(clf.support_vectors_[:, 0],
                   clf.support_vectors_[:, 1],
                   s=300, linewidth=1, facecolors='none');
    ax.set_xlim(xlim)
    ax.set_ylim(ylim)


plt.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='brg');
plot_svc_decision_function(clf)
plt.show()

Đồ thị sẽ được in ra như hình dưới:

Điều chỉnh tham số C

Ta thử thay $C$ bằng 1 số nhỏ hơn, giả dụ C=5. Ta sẽ thu được Margin lớn hơn mà đường phân chia vẫn đúng với tât cả dữ liệu (hình bên dưới).

Trong bài toán thực tế, việc điều chỉnh số $C$ là rất quan trọng, giúp cho hàm phần chia của ta thêm phần linh hoạt.

Tối ưu tham số C

Scikit learn cung cấp công cụ để tính toán tham số C tối ưu là GridSearchCV.
Chỉ cần thêm vài dòng lệnh như dưới ta có thể tìm được số C tối ưu với tập data ví dụ:

from sklearn.model_selection import GridSearchCV

parameter_candidates = [
  {'C': [0.001, 0.01, 0.1, 1, 5, 10, 100, 1000], 'kernel': ['linear']},
]

clf = GridSearchCV(estimator=SVC(), param_grid=parameter_candidates, n_jobs=-1)
clf.fit(X, y)
print('Best score:', clf.best_score_)
print('Best C:',clf.best_estimator_.C)

Chú ý biến parameter_candidates chứa các tham số cần tối ưu để thực hiện thử.
Ở đây do muốn test trên không gian 2 chiều, ta fix kernel là linear và thử tham số C trong tập 7 giá trị: [0.001, 0.01, 0.1, 1, 5, 10, 100, 1000].

Sau khi chạy đoạn code trên, ta thấy in ra màn hình:

Best score: 0.7777777777777778
Best C: 1

Thay C=1 vào đoạn code ban đầu, ta thấy in ra đồ thị như hình dưới. Đường phần chia 2 lớp dữ liệu có vẻ là đẹp nhất trong các trường hợp ta đã thử.

Trong các bài sau, ta sẽ áp dụng SVM vào giải bài toán mang tính thực tế hơn.

Áp dụng SVM vào bài toán phân nhóm chữ số viết tay

Support Vector Machine (SVM) là gì?