I. Support Vector Machine

Trong machine learning, support vector machine là supervised learning model (học có giám sát) được sử dụng khá phổ biến với tư tưởng chính là phân nhóm hoặc hồi qui model. Nếu chúng ta có một nhóm các quan sát nào đó được phân về 2 hay nhiều category thì SVM sẽ phân chia một observation mới vào một trong các category dựa trên kết quả trả về từ model. Khác với logistic, SVM (Support Vector Machine) là một lớp model non-probability khi nó phân loại observation hoàn toàn không dựa trên xác xuất. SVM model sẽ biểu diễn mỗi quan sát như một điểm trong không gian, các category sẽ đại diện cho một vùng space trong không gian đó và được chia cắt bởi các biên sao cho khoảng gap giữa chúng là lớn nhất. Dựa vào loại của biên là linear hay nound-linear mà machine learning phát triển thành nhiều phương pháp khác nhau cho SVM bao gồm:

Bài viết này sẽ giới thiệu về phương pháp maximal margin classifier là phương pháp nền tảng cơ bản nhất của SVM.

II. Maximal margin classifier

Giả sử chúng ta có một không gian p chiều. Tư tưởng của SVM là phân chia một train dataset thành thành các category dựa vào các siêu phẳng p-1 chiều. Chẳng như hình minh họa sau:

Siêu phẳng phân chia train data

Siêu phẳng phân chia train data

Chúng ta có thể thấy có 2 category khác nhau được minh họa bằng chấm tròn hoặc vuông. Mỗi một siêu phẳng H1,H2,H3 đều có thể phân loại các catergory cùng loại về một phía của siêu phẳng. Và trên thực tế có vô số siêu phẳng có thể phân loại chính xác model như thế. Vậy tiêu chí nào để lựa chọn được một siêu phẳng phân loại tốt nhất? Thuật toán Maximal margin classifier được xây dựng để nhằm tối đa hóa độ rộng của một Margin sao cho khoảng cách giữa các siêu phẳng đó với điểm gần nhất của mỗi category là lớn nhất.

Margin của siêu phẳng

Margin của siêu phẳng

Margin là phần không gian nằm giữa 2 đường thẳng H3’ và H3’‘trong hình vẽ. H3 là siêu phẳng phân loại và siêu phẳng này sẽ cách đều 2 biên của margin có nghĩa là độ dài các vector từ H3 về 2 phía H3’ và H3’’ là bằng nhau. Siêu phẳng được lựa chọn là siêu phẳng có độ rộng Margin là lớn nhất. Việc giải bài toán này sẽ tương đương với việc giải bài toán tối ưu sau:

Xét n observations \[x_{1},x_{2},...,x_{n} \in R^{p}\] với các category tương ứng \[y_{1},y_{2},...,y_{n} \in \{-1,1\}\]Tìm giá trị lớn nhất của độ rộng margin siêu phẳng thỏa mãn:

\[ \underset{\beta_{0},\beta_{1},...,\beta_{n}}{Max} M \]

\[ \sum_{i = 1}^{p}{\beta_{i}^{2}}=1 \] \[ y_{i}(\beta_{0}+\beta_{1}x_{i1}+\beta_{2}x_{i2}+...+\beta_{n}x_{in}) \geq M \quad \quad \forall \quad i=\overline{1,n} \] Việc giải bài toán trên đã được thực hiện bởi các nhà toán học. Chúng ta sẽ không đề cập ở đây, R package e1071 đã được lập trình sẵn để giải quyết bài toán này.

III. So sánh phương pháp Linear regression và SVM

Tạo một mẫu random traindata với tên là “khanh” chứa 2 biến x và y.

x = seq(1,20,1)
y = c(1,2,3,5,7,19,23,27,30,31,34,36,39,45,47,49,53,59,61,65)
khanh <- data.frame(x,y)
head(khanh,6)
##   x  y
## 1 1  1
## 2 2  2
## 3 3  3
## 4 4  5
## 5 5  7
## 6 6 19

Vẽ đồ thị dataset

plot(khanh,pch = 16)

Chúng ta sẽ so sánh hiệu quả dự báo giữa model Linear regression và model SVM.

1. Model Linear regression model.

Biểu diễn giá trị dự báo của Linear regression model và giá trị actual trên cùng một đồ thị.

#Linear regression
model <- lm(y~x, khanh)
#predict model
pred <- predict(model,khanh)
plot(khanh, pch = 16)
points(khanh$x,pred,pch = 4, col = "blue")

Tính sai số dự báo RMSE

#predict value of model
error_lm <- khanh$y - pred
RMSE_lm <- sqrt(mean(error_lm^2))
RMSE_lm
## [1] 2.462226

Sai số dự báo của model linear regression là 2.46

2. Model SVM model.

#load package e1071
library(e1071)
model_svm <- svm(y~x,khanh)
#predict model
pred_svm <- predict(model_svm,khanh)
#plot svm result with linear regression result

plot(khanh, pch = 16)
points(khanh$x,pred,pch = 4, col = "blue")
points(khanh$x,pred_svm,pch = 1, col = "red")

Kết quả trực quan cho ta thấy phương pháp SVM đưa ra kết quả chính xác hơn khi các chấm tròn màu trằng là giá trị dự báo từ SVM gần các chấm đen là giá trị được dự báo y hơn là các điểm x là giá trị dự báo từ Linear regression.

Tính sai số dự báo.

error_svm <- khanh$y - pred_svm
RMSE_svm <- sqrt(mean(error_svm^2))
RMSE_svm
## [1] 2.234611

Sai số dự báo của model chỉ là 2.23 so với 2.46 từ model linear regression. Điều đó cho thấy model dự báo SVM có mức độ chính xác dự báo tốt hơn linear regression rất nhiều ngay cả khi mối quan hệ của các giá trị dự báo và được dự báo có dạng tuyến tính.

3. Lựa chon SVM model phù hợp nhất.

Chúng ta có thể cải thiện SVM model bằng phương pháp tune để tạo ra nhiều model theo phương pháp SVM và lựa chọn ra model có RMSE là thấp nhất. Chúng ta sẽ xác định các gí trị cho tham số cost và epsilon = 0.1. Một cách đơn giản để thử cho mỗi giá trị của epsilon trong khoảng (0,1) với giá trị khoảng cách của nó là 0.01, bằng cách này chúng ta sẽ tạo ra 101 value của epsilon và 8 value của cost. Như vậy chúng ta sẽ có tổng cộng 808 model và tìm ra model phù hợp nhất. Do hồi qui nhiều model nên code sẽ cần phải chạy lâu một chút tùy theo tốc độ xử lý máy của bạn.

svm_tune <- tune(svm, y~x, data = khanh,
                 ranges = list(epsilon = seq(0,1,0.01),cost = 2^(2:9)))


print(svm_tune)
## 
## Parameter tuning of 'svm':
## 
## - sampling method: 10-fold cross validation 
## 
## - best parameters:
##  epsilon cost
##        0  128
## 
## - best performance: 3.564411
best_mod <- svm_tune$best.model
best_mod_pred <- predict(best_mod,khanh)
error_best_mod <- best_mod_pred - khanh$y
best_mod_RMSE <- sqrt(mean(error_best_mod^2))
best_mod_RMSE
## [1] 1.152312

Model dự báo tốt nhất có kết quả bình quân sai số chuẩn chỉ là 1.1 đơn vị và tốt hơn nhiều so với kết quả của model svm ban đầu.

Biểu diễn đồ thị của giá trị dự báo và giá trị actual từ model dự báo tốt nhất.

plot(khanh,pch =16)
points(khanh$x,best_mod_pred,pch = 1,col = "blue")

các giá trị actual và dự báo thực tế lệch nhau không quá lớn cho thấy kết quả dự báo là rất khớp.