Đị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.

Bạn đang xem: Svm là gì

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.

Xem thêm: Tiêm Iv Là Gì ? Ký Hiệu Viết Tắt Các Đường Dùng Thuốc

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ớnCho 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-learnTa 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, X2y là mảng label của X.

Xem thêm: Điểm Tích Lũy Tiếng Anh Là Gì, Tìm Hiểu Thêm Về Tiếng Anh Tích Lũy In English

12345678910111213

import numpy as npfrom sklearn.svm import SVCX1 = <<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 + y2clf = 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

123456789101112131415161718192021222324252627282930313233 import matplotlib.pyplot as pltdef 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().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()

Bài viết liên quan

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *