Định nghĩaSupport 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. Show 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. 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. Tối ưu trong thuật toán SVMQuay 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? 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. MarginMargin 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 VectorsBà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. Cách tính MarginTrong 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à:
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à:
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. Với không gian 2 chiềuMargin giữa 2 đường thẳng được tính bằng công thức: Với không gian nhiều chiềuTổ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$. Bài toán tìm Margin cực đạiBà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). 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. 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:
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: Chạy thử bằng thư viện Scikit-learnScikit-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). 2 3 4 5 6 7 8 9 10 11 12 13 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. 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 12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 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ố CTa 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ố CScikit learn cung cấp công cụ để tính toán tham số C tối ưu là GridSearchCV. 2 3 4 5 6 7 8 9 10 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ử. Sau khi chạy đoạn code trên, ta thấy in ra màn hình: Best score: 0.7777777777777778 Best C: 1Thay 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.
|