Support Vector Machines

Support Vector Machines: Từ Linear đến Non-linear với Kernel Trick

Support Vector Machines Linear vs Non-linear

Giới thiệu

Support Vector Machine (SVM) là một trong những thuật toán học máy mạnh mẽ nhất được sử dụng rộng rãi trong nhiều bài toán phân loại và hồi quy. Trong bài viết này, chúng ta sẽ tìm hiểu chi tiết về SVM, từ mô hình tuyến tính đơn giản đến các biến thể phi tuyến phức tạp hơn thông qua kỹ thuật "kernel trick".

Support Vector Machines là gì?

SVM là một thuật toán học có giám sát (supervised learning) được phát triển bởi Vladimir Vapnik vào những năm 1990. Mục tiêu chính của SVM là tìm một siêu phẳng (hyperplane) tối ưu có thể phân tách dữ liệu thành các lớp khác nhau, đồng thời tối đa hóa khoảng cách (margin) từ siêu phẳng đến các điểm dữ liệu gần nhất của mỗi lớp.

Những điểm dữ liệu nằm gần siêu phẳng nhất được gọi là các "support vector", và chúng đóng vai trò quan trọng trong việc xác định vị trí của siêu phẳng. SVM có khả năng xử lý cả dữ liệu tuyến tính và phi tuyến tính, dữ liệu nhiều chiều, và thường tỏ ra hiệu quả ngay cả khi số lượng mẫu huấn luyện không quá lớn.

Linear SVM: Cơ sở của Support Vector Machines

Nguyên lý hoạt động

Linear SVM hoạt động dựa trên nguyên tắc tìm một siêu phẳng tuyến tính tối ưu để phân tách dữ liệu. Trong không gian hai chiều, siêu phẳng này chính là một đường thẳng.

Đường thẳng phân tách tối ưu được xác định bởi công thức:

w·x + b = 0

Trong đó:

  • w là vector hệ số pháp tuyến với siêu phẳng

  • x là vector đặc trưng đầu vào

  • b là hệ số điều chỉnh

Mục tiêu của SVM là tìm các giá trị w và b sao cho khoảng cách từ siêu phẳng đến các support vector là lớn nhất.

Tối ưu hóa trong Linear SVM

Bài toán tối ưu hóa trong SVM có thể được phát biểu như sau:

Tối thiểu hóa: ||w||²/2 Với ràng buộc: y_i(w·x_i + b) ≥ 1 với mọi i

Trong đó:

  • y_i là nhãn của điểm dữ liệu thứ i (thường là +1 hoặc -1)

  • x_i là vector đặc trưng của điểm dữ liệu thứ i

Bài toán này thường được giải quyết bằng các phương pháp tối ưu hóa như phương pháp nhân tử Lagrange.

Ưu và nhược điểm của Linear SVM

Ưu điểm:

  • Đơn giản và dễ hiểu

  • Hiệu quả với dữ liệu có thể phân tách tuyến tính

  • Ít rủi ro overfitting hơn so với một số thuật toán khác

Nhược điểm:

  • Không hiệu quả với dữ liệu không thể phân tách tuyến tính

  • Khó khăn trong việc xử lý tập dữ liệu lớn

  • Cần chuẩn hóa dữ liệu trước khi huấn luyện

Non-linear SVM: Mở rộng khả năng của SVM

Vấn đề với dữ liệu không phân tách tuyến tính

Trong thực tế, nhiều bộ dữ liệu không thể phân tách bằng một đường thẳng hoặc siêu phẳng tuyến tính. Ví dụ, dữ liệu có thể phân bố theo hình tròn, hình elip, hoặc các dạng phức tạp khác. Linear SVM không thể xử lý hiệu quả những trường hợp này.

Giải pháp: Kernel Trick

Kernel Trick là một kỹ thuật thông minh cho phép SVM xử lý dữ liệu phi tuyến tính mà không cần thực hiện các phép biến đổi phức tạp một cách rõ ràng. Ý tưởng chính là ánh xạ dữ liệu từ không gian đặc trưng ban đầu sang một không gian đặc trưng mới có số chiều cao hơn, nơi mà dữ liệu có thể được phân tách tuyến tính.

Thay vì tính toán trực tiếp các vector đặc trưng trong không gian mới (có thể rất tốn kém về mặt tính toán), kernel trick sử dụng các hàm kernel để tính toán tích vô hướng của các vector đặc trưng trong không gian mới mà không cần biểu diễn rõ ràng các vector này.

Các hàm kernel phổ biến

  1. Kernel tuyến tính (Linear Kernel):

    K(x, y) = x · y

  2. Kernel đa thức (Polynomial Kernel):

    K(x, y) = (γx · y + r)^d

    Trong đó γ, r và d là các tham số.

  3. Kernel Gaussian RBF (Radial Basis Function):

    K(x, y) = exp(-γ||x - y||²)

    Trong đó γ là tham số kiểm soát bán kính ảnh hưởng.

  4. Kernel sigmoid:

    K(x, y) = tanh(γx · y + r)

    Trong đó γ và r là các tham số.

Lựa chọn kernel phù hợp

Việc lựa chọn kernel phù hợp phụ thuộc vào bản chất của dữ liệu và bài toán cụ thể:

  • Linear Kernel: Phù hợp với dữ liệu có thể phân tách tuyến tính.

  • Polynomial Kernel: Tốt cho dữ liệu với ranh giới quyết định dạng đa thức, như hình bầu dục, hình tròn.

  • RBF Kernel: Rất linh hoạt và thường là lựa chọn mặc định khi không có kiến thức trước về dữ liệu.

  • Sigmoid Kernel: Thường được sử dụng trong các bài toán liên quan đến mạng neural.

Ví dụ thực tiễn và cách triển khai

Ví dụ Python với scikit-learn

from sklearn import svm
from sklearn.datasets import make_circles
from sklearn.model_selection import train_test_split
import matplotlib.pyplot as plt
import numpy as np

# Tạo dữ liệu mẫu không phân tách tuyến tính (hình tròn đồng tâm)
X, y = make_circles(n_samples=1000, noise=0.1, factor=0.5, random_state=42)

# Chia dữ liệu thành tập huấn luyện và kiểm tra
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# Huấn luyện mô hình SVM với kernel tuyến tính
linear_svm = svm.SVC(kernel='linear')
linear_svm.fit(X_train, y_train)
linear_score = linear_svm.score(X_test, y_test)

# Huấn luyện mô hình SVM với kernel RBF
rbf_svm = svm.SVC(kernel='rbf')
rbf_svm.fit(X_train, y_train)
rbf_score = rbf_svm.score(X_test, y_test)

print(f"Độ chính xác của Linear SVM: {linear_score:.4f}")
print(f"Độ chính xác của RBF SVM: {rbf_score:.4f}")

# Vẽ đồ thị kết quả
h = 0.02
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h))

plt.figure(figsize=(12, 5))

# Plot Linear SVM
plt.subplot(1, 2, 1)
Z = linear_svm.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
plt.contourf(xx, yy, Z, cmap=plt.cm.coolwarm, alpha=0.8)
plt.scatter(X[:, 0], X[:, 1], c=y, cmap=plt.cm.coolwarm, s=20, edgecolors='k')
plt.title(f'Linear SVM (Accuracy: {linear_score:.4f})')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')

# Plot RBF SVM
plt.subplot(1, 2, 2)
Z = rbf_svm.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
plt.contourf(xx, yy, Z, cmap=plt.cm.coolwarm, alpha=0.8)
plt.scatter(X[:, 0], X[:, 1], c=y, cmap=plt.cm.coolwarm, s=20, edgecolors='k')
plt.title(f'RBF SVM (Accuracy: {rbf_score:.4f})')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')

plt.tight_layout()
plt.show()

Tối ưu hóa hiệu suất SVM

Lựa chọn tham số

Các tham số quan trọng cần điều chỉnh trong SVM:

  1. C: Tham số điều chỉnh mức độ phạt cho các điểm bị phân loại sai. C lớn có thể dẫn đến overfitting, C nhỏ có thể gây underfitting.

  2. gamma: Tham số của các kernel phi tuyến tính như RBF, kiểm soát ảnh hưởng của từng mẫu huấn luyện. gamma lớn có thể dẫn đến overfitting.

  3. degree: Bậc của kernel đa thức.

Grid Search và Cross-Validation

Để tìm bộ tham số tối ưu, chúng ta có thể sử dụng Grid Search kết hợp với K-fold Cross-Validation:

from sklearn.model_selection import GridSearchCV

# Định nghĩa lưới tham số cần tìm kiếm
param_grid = {
    'C': [0.1, 1, 10, 100],
    'gamma': [0.001, 0.01, 0.1, 1],
    'kernel': ['rbf', 'poly', 'sigmoid']
}

# Sử dụng Grid Search với 5-fold Cross-Validation
grid = GridSearchCV(svm.SVC(), param_grid, cv=5)
grid.fit(X_train, y_train)

print(f"Tham số tốt nhất: {grid.best_params_}")
print(f"Độ chính xác tốt nhất: {grid.best_score_:.4f}")

Ứng dụng thực tế của SVM

SVM được ứng dụng rộng rãi trong nhiều lĩnh vực:

  1. Nhận dạng hình ảnh và phân loại văn bản

  2. Phát hiện gian lận và bất thường

  3. Chẩn đoán y tế và phân loại protein

  4. Dự đoán thời tiết và phân tích tài chính

  5. Nhận dạng chữ viết tay và biểu cảm khuôn mặt

Kết luận

Support Vector Machine là một thuật toán học máy mạnh mẽ và linh hoạt. Với Linear SVM, chúng ta có thể giải quyết các bài toán phân loại tuyến tính một cách hiệu quả. Với sự hỗ trợ của kernel trick, Non-linear SVM mở rộng khả năng xử lý để giải quyết các bài toán phân loại phức tạp hơn.

Mặc dù có những thuật toán mới như Deep Learning đang ngày càng phổ biến, SVM vẫn là một công cụ quan trọng trong bộ công cụ của các chuyên gia học máy, đặc biệt là trong các trường hợp có dữ liệu huấn luyện hạn chế hoặc khi cần một mô hình có thể diễn giải được.

Hy vọng bài viết này đã cung cấp cho bạn một cái nhìn tổng quan và chi tiết về Support Vector Machines, từ nguyên lý cơ bản đến các kỹ thuật nâng cao và ứng dụng thực tiễn.

Tài liệu tham khảo

  1. Vapnik, V. N. (1995). The Nature of Statistical Learning Theory. Springer-Verlag.

  2. Cristianini, N., & Shawe-Taylor, J. (2000). An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. Cambridge University Press.

  3. Schölkopf, B., & Smola, A. J. (2002). Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press.

  4. Documentation scikit-learn: https://scikit-learn.org/stable/modules/svm.html

PreviousDecision Trees và Random ForestsNextK-Nearest Neighbors và K-Means

Last updated