Computer Vision

[Image Classification] Support Vector Machines

Xin chào, trong bài viết này chúng ta sẽ tìm hiểu về Support Vector Machines (SVM) – một thuật toán được sử dụng phổ biến trong Machine Learning để phân loại dữ liệu, cũng như tìm cách áp dụng Support Vector Classifier.


HIỂU VỀ SUPPORT VECTOR MACHINES

LINEAR SEPARABILITY

Trước hết chúng ta cần tìm hiểu về khái niệm linear separability (phân chia tuyến tính). Một dataset gồm class #1 và class #2 được coi là có thể phân chia tuyến tính nếu tồn tại một đường thẳng hoặc mặt phẳng hoặc siêu mặt phẳng để phân tách class #1 và class #2 thành hai vùng riêng biệt, xem Figure 1.

Figure_1

Figure 1 – Linearly separable datasets

Nói một cách tổng quát, một Decision Boundary (ranh giới quyết định) sẽ được dùng để phân tách các class dữ liệu. Trong không gian 2 chiều (2-D) như ở Figure 1, đó đơn giản là một đường thẳng. Trong không gian 3 chiều (3-D) thì đó sẽ là một mặt phẳng. Đối với không gian có nhiều chiều hơn nữa thì đó sẽ là một siêu mặt phẳng.

Không quan trọng là đường thẳng, mặt phẳng hay siêu mặt phẳng, Decision Boundary giúp chúng ta có thể quyết định là một phần tử thuộc class #1 hay class #2. Một phần tử càng nằm cách ra ranh giới thì xác suất nó thuộc class tương ứng càng lớn.

Figure_1

Figure 2 – Decision Boundary

Nhìn vào Figure 2 chúng ta thấy rằng có thể tồn tại nhiều Decision Boundary, vậy cái nào trong số chúng sẽ cho kết quả phân loại tốt nhất? Theo cảm tính thì chắc chắn chúng ta sẽ đoán là đường thẳng màu đen trong số ba đường thẳng trên. Cảm nhận của chúng ta là chính xác, vì đường thẳng màu đen nằm cách đều so với vùng phân bố của hai class, điều này giúp giảm nguy cơ phân loại nhầm class.

Vậy làm sao để tìm được Decision Boundary phù hợp nhất? Để giải quyết vấn đề này chúng ta cần kiến thức sâu về toán học. Tuy nhiên, bài viết này chỉ nhằm giới thiệu cách ứng dụng chứ không phải nghiên cứu về Machine Learning nên chúng ta sẽ không tìm hiểu sâu hơn. Do đó chúng ta không cần lo lắng về vấn đề này nữa vì bộ thư viện scikit-learn sẽ giải quyết nó. Để tìm hiểu sâu hơn về nền tảng toán học của SVM, các bạn có thể tham khảo blog machinelearningcoban của anh Vũ Hữu Tiệp.

KERNEL SVM

Đầu tiên hãy xem xét hai class #1 và #2 ở Figure 3 và vẽ một đường thẳng để phân tách chúng trong không gian 2 chiều.

Figure_2

Figure 3 – Non-linearly separable datasets

Chắc chắn là không thể vẽ được đường thẳng nào như thế rồi. Hãy nhớ lại phần trước, chúng ta đã đề cập rằng Decision Boundary có thể là đường thẳng, mặt phẳng hoặc siêu mặt phẳng, tùy vào số chiều không gian mà chúng ta chọn. Vậy thì thử chuyển các datasets này sang không gian 3 chiều xem nào.

3D

Figure 4 – Datasets in 3D space

Như Figure 4, chúng ta đã chuyển các datasets từ không gian 2 chiều sang không gian 3 chiều bằng cách thêm chiều thứ 3 là một hàm số của 2 chiều còn lại với phương trình z = x^{2} + y^{2}. Lúc này hai class #1 và #2 sẽ dễ dàng được phân tách bởi một mặt phẳng.

Dưới đây là một minh họa sinh động hơn mình tham khảo từ blog machinelearningcoban của anh Vũ Hữu Tiệp.

Để biểu diễn lại các datasets chúng ta cần tìm một function K (còn gọi là Kernel Matrix). Giả sử chúng ta có bốn Feature Vector là A, B, C và D. Với function K chúng ta có thể tạo một Feature Vector mới để biểu diễn mối quan hệ giữa A và các vector còn lại trong không gian mới:

A' = [K(A, A), K(A, B), K(A, C), K(A, D)]

Vector A’ biểu diễn mối quan hệ giữa A với chính nó và các vector B, C, D sau khi áp dụng function K.

Tương tự với các vector B, C và D, ta có:

B' = [K(B, A), K(B, B), K(B, C), K(B, D)]

C' = [K(C, A), K(C, B), K(C, C), K(C, D)]

D' = [K(D, A), K(D, B), K(D, C), K(D, D)]

Bây giờ thay vì sử dụng các Feature Vector A, B, C, D để training, chúng ta sẽ sử dụng các Vector A’, B’, C’ và D’.

MỘT SỐ KERNEL THÔNG DỤNG

Với x, y là các Feature Vector, ta có:

Linear:

K(x, y) = x.y

Scikit-learn: SVC(kernel=”linear”)

Polynomial:

K(x, y) = (x.y + c)^{d}

Scikit-learn: SVC(kernel=”poly”, degree, coef0)

Sigmoid:

K(x, y) = tanh(\gamma.x.y + c)

Scikit-learn: SVC(kernel=”sigmoid”, gamma, coef0)

Radial basis function (RBF):

K(x, y) = exp(-\gamma ||x - y||^{2})

Scikit-learn: SVC(kernel=”rbf”, gamma)

Để đạt được kết quả tốt nhất chúng ta cần phải chọn được các tham số \gamma và c cho phù hợp.

SVM MỞ RỘNG CHO MULTIPLE CLASSES

Cho đến nay chúng ta chỉ mới tìm hiểu về phân tách hai class dữ liệu, vậy nếu có N class dữ liệu thì sao? Câu trả lời là phương pháp one-against-one, tức là nếu có N class dữ liệu thì chúng ta sẽ train \frac{N(N-1)}{2} bộ classifier để phân tách riêng từng cặp class dữ liệu, ví dụ: class #1 vs. class #2, class #1 vs. class #3, …, class #n-1 vs class #n.

Một phương pháp khác là one-against-all được sử dụng trong Linear SVM. Nếu có N class dữ liệu, chúng ta sẽ train N bộ classifier để phân tách từng class dữ liệu với phần còn lại, ví dụ: class #1 vs. not class #1, class #2 vs. not class #2,…, class #n vs. not class #n.


ÁP DỤNG SVM ĐỂ GIẢI QUYẾT BÀI TOÁN XOR

svm

Figure 5 – Bài toán XOR

Chắc chắn là chúng ta không thể vẽ một đường thẳng để phân tách hai class dữ liệu trên trong không gian hai chiều, vậy thì hãy sử dụng Kernel Matrix để biểu diễn lại mối quan hệ giữa chúng.

Source code: svm.py

from sklearn.metrics import classification_report
from sklearn.svm import SVC
import numpy as np
import sklearn
from sklearn.model_selection import train_test_split
from matplotlib import pyplot as plt

topleft = np.random.uniform(size=(100,2)) + np.array([-1.0, 1.0])
topright = np.random.uniform(size=(100,2)) + np.array([1.0, 1.0])
botleft = np.random.uniform(size=(100,2)) + np.array([-1.0, -1.0])
botright = np.random.uniform(size=(100,2)) + np.array([1.0, -1.0])

plt.figure()
plt.scatter(topleft[:,0],topleft[:,1], color='r', marker='o', alpha=0.5, label="class #1")
plt.scatter(topright[:,0],topright[:,1], color='b', marker='s', alpha=0.5, label="class #2")
plt.scatter(botright[:,0],botright[:,1], color='r', marker='o', alpha=0.5)
plt.scatter(botleft[:,0],botleft[:,1], color='b', marker='s', alpha=0.5)
plt.legend()

X = np.vstack([topleft, topright, botright, botleft])
Y = np.hstack([[1]*len(topleft), [-1]*len(topright), [1]*len(botright), [-1]*len(botleft)])

(trainData, testData, trainLabels, testLabels) = train_test_split(X, Y, test_size=0.25, random_state=42)

print("[RESULT] SVM with Linear Kernel")
model = SVC(kernel="linear")
model.fit(trainData, trainLabels)
print(classification_report(testLabels, model.predict(testData)))

print("[RESULTS] SVM with Polynomial Kernel")
model = SVC(kernel="poly", degree=2, coef0=1)
model.fit(trainData, trainLabels)
print(classification_report(testLabels, model.predict(testData)))

plt.show()

Giải thích:
– Để áp dụng Support Vector Machines vào phân loại dữ liệu, chúng ta sử dụng class SVC trong thư viện scikit-learn;
– Dòng 8-11: tạo dữ liệu mô phỏng bài toán XOR;
– Dòng 13-18: vẽ đồ thị phân bố của dữ liệu;
– Dòng 20, 21: ghép các class dữ liệu thành một tập hợp lớn và gán label cho class #1 là 1, class #2 là -1;
– Dòng 26-28: tạo bộ classifier với Kernel là một hàm Linear và đánh giá kết quả;
– Dòng 31-33: tạo bộ classifier với Kernel là một hàm Polynomial có degree=2, coef0=1: K(x, y) = (x.y + 1)^2.

Output:

result

Với kết quả nhận được chúng ta thấy rằng, khi sử dụng Linear Kernel, kết quả nhận được chỉ là 82% chính xác, trong khi đó Polynomial Kernel cho độ chính xác đến 100%. Trong các ứng dụng thực tế, chúng ta sẽ phải thử qua nhiều kernel và tham số để chọn ra phương án tốt nhất.


SUMMARY

Qua bài viết này chúng ta đã có cái nhìn tổng quát về Support Vector Machine và cách áp dụng vào Computer Vision. Cảm ơn các bạn đã theo dõi bài viết.

Thân ái và quyết thắng.

Reference:
[1] Support Vector Machine.
[2] sklearn.svm.SVC.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s