Support Vector Machine - SVM là một phương pháp học có giám sát trong các mô hình nhận dạng mẫu. Nó không chỉ hoạt động tốt với các dữ liệu được phân tách tuyến tính mà còn tốt với cả dữ liệu phân tách phi tuyến. Với nhiều bài toán, SVM mang lại kết quả tốt như mạng nơ-ron với hiệu quả sử dụng tài nguyên tốt hơn hẳn.

Mục lục

1. Phương pháp SVM

Như đã biết, với bài toán phân loại nhị phân tuyến tính ta cần vẽ được mặt phân tách (với không gian 2 chiều thì mặt phẳng này là đường phân tách): $\mathbf{w}^{\intercal}\mathbf{x}+b=0$ để phân biệt được dữ liệu. Khi đó dấu của hàm ước lượng $H=\{\mathbf{x} \mapsto\mathrm{sgn}(\mathbf{w}^{\intercal}\mathbf{x}+b)~~~;\mathbf{w}\in\mathbb{R}^N,b\in\mathbb{R}\}$ sẽ thể hiện được điểm dữ liệu $\mathbf{x}$ nằm ở cụm dữ liệu nào.

Mặt phân cách dữ liệu

Nếu để ý thì ta có thể có nhiều mặt phân tách thoả mãn được việc này và đương nhiên là nếu chọn được mặt mà phân tách tốt thì kết quả phân loại của ta sẽ tốt hơn. Một lẽ rất tự nhiên là dường như mặt nằm vừa khít giữa 2 cụm dữ liệu sao cho nằm xa các tập dữ liệu nhất là mặt tốt nhất.

Max Margin

SVM chính là một biện pháp để thực hiện được phép lấy mặt phẳng như vậy.

Để xác định mặt phẳng kẹp giữa đó, trước tiên ta cần phải xác định được 2 mặt biên gốc như 2 đường nét đứt ở trên. Các điểm dữ liệu gần với mặt biên gốc này nhất có thể xác định bằng:

$$\min{\vert\mathbf{w}^{\intercal}\mathbf{x}+b\vert}$$

Để dễ dàng cho việc tính toán thì người ta sẽ chọn $\mathbf{w}$ và $b$ sao cho các điểm gần nhất (mặt biên gốc) thoả mãn: $\vert\mathbf{w}^{\intercal}\mathbf{x}+b\vert=1$, tức là: $$\min{\vert\mathbf{w}^{\intercal}\mathbf{x}+b\vert}=1$$

Đương nhiên là có thể tồn tại nhiều cặp đôi mặt biên gốc như vậy và tồn tại nhiều mặt phân đôi kẹp giữa các mặt biên gốc đó. Nên ta phải tìm cách xác định được mặt kẹp giữa tốt nhất bằng cách lấy cặp có khoảng cách xa nhau nhất. Lẽ này là đương nhiên bởi cặp có khoảng cách xa nhất đồng nghĩa với chuyện tập dữ liệu được phân cách xa nhất.

Như vậy, ta có thể thiết lập thông số tính khoảng cách đó bằng phép lấy độ rộng biên từ mặt biên gốc tới mặt phân tách cần tìm. $$\rho=\min\dfrac{\vert\mathbf{w}^{\intercal}\mathbf{x}+b\vert}{\Vert\mathbf{w}\Vert}=\dfrac{1}{\Vert\mathbf{w}\Vert}$$

Bài toán của ta bây giờ sẽ là cần xác định $\mathbf{w}$ và $b$ sao cho $\rho$ đạt lớn nhất và các điểm dữ liệu $y_i(\mathbf{w}^{\intercal}\mathbf{x}_i+b)\ge 1$. $\rho$ đạt lớn nhất đồng nghĩa với việc $\Vert\mathbf{w}\Vert$ đạt nhỏ nhất. Tức là: $$ \begin{aligned} (\mathbf{w},b)&=\arg\min_{\mathbf{w},b}\frac{1}{2}\Vert\mathbf{w}\Vert^2 \cr \text{subject to}~~~&y_i(\mathbf{w}^{\intercal}\mathbf{x}_i+b)\ge 1, i\in[1,m] \end{aligned} $$

Ở đây, $m$ là số lượng các điểm dữ liệu $(\mathbf{x}_i,y_i)$ còn việc lấy bình phương và chia đôi nhằm dễ dàng tính toán và tối ưu lồi.

Bài toán này có thể giải thông qua bài toán đối ngẫu của nó và sử dụng phương pháp nhân tử Lagrance. Lúc này, ta sẽ cần tìm các giá trị $\lambda$ như sau: $$ \begin{aligned} \lambda&=\arg\max_\lambda\sum_{i=1}^m\lambda_i-\frac{1}{2}\sum_{i,j=1}^m\lambda_i\lambda_jy_iy_j\mathbf{x}_i^{\intercal}\mathbf{x}_j \cr \text{subject to}~~~&\lambda_i\ge 0 \land \sum_{i=1}^m\lambda_iy_i=0, i\in[1,m] \end{aligned} $$

Việc giải $\lambda$ có thể được thực hiện bằng phương pháp quy hoạch động bậc 2 (Quadratic Programing). Với Python ta có thể sử dụng thư viện CVOPT. Sau khi tìm được $\lambda$ thì ta có các tham số: $$ \begin{aligned} \mathbf{w}&=\sum_{i=1}^m\lambda_iy_i\mathbf{x}_i \cr b&=y_i-\sum_{j=1}^m\lambda_jy_j\mathbf{x}_j^{\intercal}\mathbf{x}_i \end{aligned} $$

Ở đây, $(\mathbf{x}_i, y_i)$ là một điểm dữ liệu bất kì nào đó nằm trên đường biên gốc. Điểm dữ liệu này còn được gọi là Support Vector. Tên của phương pháp SVM cũng từ đây mà ra. Tuy nhiên, thường người ta tính $b$ bằng phép lấy trung bình tổng của tất cả các $b_i$. Giả sử, ta có tập $\mathbb{S}$ các Support Vectors thì: $$b=\frac{1}{\vert \mathbb{S}\vert}\sum_{i\in\mathbb{S}}\Bigg(y_i-\sum_{j=1}^m\lambda_jy_j\mathbf{x}_j^{\intercal}\mathbf{x}_i\Bigg)$$

Khi đó, một điểm dữ liệu mới sẽ được phân loại dựa theo: $$h(\mathbf{x})=\mathrm{sgn}\Bigg(\sum_{i=1}^m\lambda_iy_i\mathbf{x_i}^{\intercal}\mathbf{x}+b\Bigg)$$

Như vậy, chỉ cần các điểm Support Vector trên đường biên gốc là ta có thể ước lượng được các tham số tối ưu cho bài toán. Việc này rất có lợi khi tính toán giúp phương pháp này tiết kiệm được tài nguyên thực thi.

2. Dữ liệu chồng nhau và phương pháp biên mềm

Trong thực tế tập dữ liệu thường không được sạch như trên mà thường có nhiễu. Nhiễu ở đây là dạng dữ liệu chồng chéo lên nhau như hình bên dưới.

Non-linear data

Với dạng dữ liệu như vậy thì mặt phân tách tìm được sẽ khó mà tối ưu được, thậm chí là không tìm được mặt phân tách luôn. Giờ vấn đề đặt ra là làm sao triệt được các nhiễu này. Tức là tính toán bỏ qua được các nhiễu này khi huấn luyện.

Một cách hình thức, các điểm nhiễu là những điểm mà không đảm bảo điều kiện $y_i(\mathbf{w}^{\intercal}\mathbf{x}+b)\ge 1$. Khi đó bằng phép thêm biến lùi (Slack Variables) $\xi_i\ge 0$ sao cho ra có được ràng buộc: $$y_i(\mathbf{w}^{\intercal}\mathbf{x}+b)\ge 1-\xi_i$$

Giờ, hàm mục tiêu tối ưu được viết lại như sau: $$ \begin{aligned} (\mathbf{w},b,\xi)&=\arg\min_{\mathbf{w},b}\frac{1}{2}\Vert\mathbf{w}\Vert^2 + C\sum_{i=1}^m\xi_i \cr \text{subject to}~~~&\xi_i\ge 0 \land y_i(\mathbf{w}^{\intercal}\mathbf{x}_i+b)\ge 1-\xi_i ~~~, i\in[1,m] \end{aligned} $$

$C$ ở đây là hệ số cân bằng giữa nhiễu và không nhiễu. Nếu $C$ càng lớn thì các nhiễu càng nhiều điểm được coi là nhiễu hơn tức là nhiễu được coi trọng hơn.

Giải bài toán này, nghiệm tương tự như cách tính ở trên chỉ khác một điều là tập các điểm support vectors $\mathbb{S}$ được mở rộng thêm tới các điểm $(\mathbf{x}_i,y_i)$ ra miễn sao nó thoả mãn điều kiện: $$0<\lambda_i<C$$

Tức là: $$ \begin{aligned} \lambda&=\arg\max_\lambda\sum_{i=1}^m\lambda_i-\frac{1}{2}\sum_{i,j=1}^m\lambda_i\lambda_jy_iy_j\mathbf{x}_i^{\intercal}\mathbf{x}_j \cr \text{subject to}~~~&0\le\lambda_i\le C \land \sum_{i=1}^m\lambda_iy_i=0, i\in[1,m] \end{aligned} $$

Khi đó, tham số được ước lượng như sau: $$ \begin{aligned} \mathbf{w}&=\sum_{i=1}^m\lambda_iy_i\mathbf{x}_i \cr b&=\frac{1}{\vert \mathbb{S}\vert}\sum_{i\in\mathbb{S}}\Bigg(y_i-\sum_{j=1}^m\lambda_jy_j\mathbf{x}_j^{\intercal}\mathbf{x}_i\Bigg) ~~~\text{for }x_i\text{ with } 0<\lambda_i<C \end{aligned} $$

Với tập $\mathbb{S}$ mở rộng như vậy người ta gọi phương pháp này là phương pháp biên mềm (Soft-Margin SVM). Còn phương pháp truyền thống là biên cứng (Hard-Margin SVM).

3. Dữ liệu phân tách phi tuyến và phương pháp kernel

Như các bài trước đã đề cập tới việc sử dụng hàm cơ bản $\Phi(\mathbf{x})$ để tạo đặc trưng cho tập dữ liệu nhằm nâng được chiều của dữ liệu ban đầu. Bằng các hàm cơ bản này, ta có thể tạo các mặt cong phân tách cho phù hợp với các điểm dữ liệu không phân tách tuyến tính.

Khi đó tối ưu biên mềm được viết dưới dạng: $$ \begin{aligned} \lambda&=\arg\max_\lambda\sum_{i=1}^m\lambda_i-\frac{1}{2}\sum_{i,j=1}^m\lambda_i\lambda_jy_iy_j\Phi(\mathbf{x}_i)^{\intercal}\Phi(\mathbf{x}_j) \cr \text{subject to}~~~&0\le\lambda_i\le C \land \sum_{i=1}^m\lambda_iy_i=0, i\in[1,m] \end{aligned} $$

Đặt hàm Kernel $K(\mathbf{x}_i,\mathbf{x}_j)=\Phi(\mathbf{x}_i)^{\intercal}\Phi(\mathbf{x}_j)$, ta có:

$$ \begin{aligned} \lambda&=\arg\max_\lambda\sum_{i=1}^m\lambda_i-\frac{1}{2}\sum_{i,j=1}^m\lambda_i\lambda_jy_iy_jK(\mathbf{x}_i,\mathbf{x}_j) \cr \text{subject to}~~~&0\le\lambda_i\le C \land \sum_{i=1}^m\lambda_iy_i=0, i\in[1,m] \end{aligned} $$

Khi đó tham số tương ứng sẽ là: $$ \begin{aligned} \mathbf{w}&=\sum_{i=1}^m\lambda_iy_i\Phi(\mathbf{x}_i) \cr b&=\frac{1}{\vert \mathbb{S}\vert}\sum_{i\in\mathbb{S}}\Bigg(y_i-\sum_{j=1}^m\lambda_jy_jK(\mathbf{x}_i,\mathbf{x}_j)\Bigg) ~~~\text{for }x_i\text{ with } 0<\lambda_i<C \end{aligned} $$

Điểm dữ liệu mới được phân lớp với: $$h(\mathbf{x})=\mathrm{sgn}\Bigg(\sum_{i=1}^m\lambda_iy_i\Phi(\mathbf{x_i})^{\intercal}\Phi(\mathbf{x})+b\Bigg)=\mathrm{sgn}\Bigg(\sum_{i=1}^m\lambda_iy_iK(\mathbf{x}_i,\mathbf{x})+b\Bigg)$$

Như vậy, chỉ cần hàm Kernel $K(\mathbf{x}_i,\mathbf{x}_j)$ để tính tích vô hướng giữa các điểm dữ liệu trong không gian mới là ta có thể ước lượng được một điểm mới nằm trong phân lớp nào.

Việc sử dụng hàm Kernel ở đây sẽ giúp giảm được công số tính từng hàm $\Phi$ và tích vô hướng giữa chúng. Nó có thể tính được cho bất kì không gian nào rất hiệu quả. Kể cả các không gian với số chiều vô hạn. Bởi nó chỉ cần tính tích vô hương giữa các điểm dữ liệu mà thôi. Tất nhiên để làm được điều đó thì Kernel phải thoả mãn điều kiện Mercer.

Khi làm việc người ta thường chọn một hàm Kernel thông dụng sau:

4. Kết luận

Phương pháp SVM là một cách hiệu quả cho bài toán phân lớp mà chỉ sử dụng một lượng ít dữ liệu là các điểm support vectors nằm trên đường biên gốc và phần mở rộng. Giả sử $\mathbb{S}$ là tập các điểm support vectors, ta cần tìm $\lambda$ như sau: $$ \begin{aligned} \lambda&=\arg\max_\lambda\sum_{i=1}^m\lambda_i-\frac{1}{2}\sum_{i,j=1}^m\lambda_i\lambda_jy_iy_jK(\mathbf{x}_i,\mathbf{x}_j) \cr \text{subject to}~~~&0\le\lambda_i\le C \land \sum_{i=1}^m\lambda_iy_i=0, i\in[1,m] \end{aligned} $$

Và hàm đánh giá điểm dữ liệu mới được thể hiện: $$h(\mathbf{x})=\mathrm{sgn}\Bigg(\sum_{i=1}^m\lambda_iy_iK(\mathbf{x}_i,\mathbf{x})+b\Bigg)$$

Trong đó $K(\mathbf{x}_i,\mathbf{x}_j)$ là hàm Kernel thoả mãn điều kiện điều kiện Mercer. Nếu hàm Kernel là một hàm tuyến tính thì ta có thể coi là giữ nguyên không gian dữ liệu ban đầu, còn không ta có thể nghĩ rằng ta đang chiếu các điểm dữ liệu qua một không gian có số chiều lớn hơn.