Giới thiệu chung

Như trong bài giới thiệu trước chúng ta đã biết về thuật toán PLA trong việc tạo ra một biến tuyến tính để phân chia các class và chúng ta đã biết rằng nếu thuật toán PLA tồn tại một mặt phẳng phân chia thì cũng sẽ có vô số các mặt phẳng phân chia. Như vậy dẫn tới mỗi lần chúng ta chạy PLA sẽ có thể ra một kết quả là một đường biên khác nhau mà không có một tiêu chuẩn nhận biết đường biên nào là tốt nhất. Với SVM (support vector machine) thì chúng ta đã khắc phục được nhược điểm này bằng cách xác định được trong tợp hợp các đường biên thì đường biên nào sẽ là đường biên tốt nhất dựa trên một tiêu chuẩn độ rộng của lề (margin):

Margin of SVM (source wikipedia)

Margin of SVM (source wikipedia)

Như chúng ta đã biết phương trình tuyến tính \(\mathbf{w}^T\mathbf{x} + b = 0\) với \(\mathbf{w} \in \mathbb{R}^{n}\) là vector hệ số ứng với các chiều của vector \(\mathbf{x} = [x_1,x_2,...,x_n] \in \mathbb{R}^{n}\), \(b\) là hệ số tự do trong không gian 2 chiều thì được gọi là đường thằng, không gian 3 chiều là mặt phẳng. Đối với những không gian lớn hơn 3 chiều chúng ta gọi chung là siêu phẳng (hyperplane).

Như hình vẽ trên ta thấy tồn tại vô số các siêu phẳng phân chia 2 class đen và trắng. Chúng ta xét một siêu phẳng bất kì là \(\mathbf{w}^T\mathbf{x} - b = 0\) (đổi dấu của \(b\) để trùng với nguồn wiki) là đường thẳng nét đậm trong hình. Khi thay đổi giá trị của b ta sẽ được những siêu phẳng song song nhau. Như vậy tồn tại một họ các siêu phẳng song song phân chia 2 class đen và trắng ứng với một bộ hệ số \(\mathbf{w}\). Chúng ta cần tìm ra một siêu phẳng là đại diện cho một bộ hệ số \(\mathbf{w}\) sao cho siêu phẳng này đánh giá đươc khoảng cách tới các điểm gần nhất của mỗi class. Nếu chúng ta lấy siêu phẳng trong họ các siêu phẳng này quá gần class màu đen thì sẽ không công bằng nếu đo khoảng cách từ class màu trắng tới biên và nếu chúng ta lấy siêu phẳng quá gần class màu trắng cũng sẽ không công bằng nếu đo khoảng cách từ class màu đen. Hay nói cách khác ta phải chọn siêu phẳng sao cho khoảng cách của nó tới các điểm gần nhất màu đen và màu trắng phải bằng nhau thì giá trị này mới đại diện cho độ đo khoảng cách ứng với bộ hệ số \(\mathbf{w}\). Khi đó vị trí của siêu phẳng chính là đường in đậm được minh họa trong hình. Ta tạm gọi các siêu phẳng này là siêu phẳng trung tâm. Độ lớn khoảng cách tại siêu phẳng trung tâm tới 1 điểm gần nhất thuộc class bên trái hoặc bên phải (lúc này 2 khoảng cách trái phải bằng nhau) được gọi là margin.
Nhắc lại kiến thức THPT, trong không gian 2 chiều khoảng cách từ 1 điểm tới 1 đường thẳng sẽ là:

\[\frac{|w_1x_1+w_2x_2+b|}{\sqrt{w_1^2 +w_2^2}}\] Trong không gian 3 chiều khoảng cách từ 1 điểm tới 1 mặt phẳng sẽ là:

\[\frac{|w_1x_1+w_2x_2+w_3x_3+b|}{\sqrt{w_1^2 +w_2^2+w_3^2}}\] Như vậy margin khoảng cách từ điểm gần nhất \(\mathbf{x_i}\) tới siêu phẳng trung tâm có giá trị bằng:

\[\frac{|\mathbf{w}^{T}\mathbf{x_i} + b|}{||\mathbf{w}||_2}\] Trong đó \(||\mathbf{w}||_2\) là bình phương của norm bậc 2.

Giả định rằng các điểm màu đen ứng với \(\mathbf{w}^{T}\mathbf{x} + b \geq 0\) được gán nhãn \(y = 1\) và các điểm màu trắng có giá trị \(\mathbf{w}^{T}\mathbf{x} + b < 0\) được gán nhãn \(y = -1\). Khi đó \(y_i(\mathbf{w}^T\mathbf{x_i}+b) = |\mathbf{w}^T\mathbf{x_i}+b|\). Giá trị của margin sẽ là:

\[\frac{y_i(\mathbf{w}^T\mathbf{x_i}+b)}{||\mathbf{w}||_2}\] Do với một bộ hệ số \((\mathbf{w}, b)\) của một siêu phẳng bất kì thì khi nhân các hệ số này với \(k\) nguyên dương bất kì ta cũng thu được siêu phẳng đó. Do đó ta hoàn toàn có thể điều chỉnh được các hệ số \((\mathbf{w},b)\) sao cho giá trị khoảng cách tại các điểm gần nhất tới siêu phẳng trung tâm bằng 1 hay nói cách khác ta có giả định tại điểm i gần nhất thì:

\[y_i(\mathbf{w}^T\mathbf{x_i}+b) = 1 \space (1)\]

Đối với các điểm cách xa siêu phẳng trung tâm hơn thì khoảng cách này lơn hơn nên: \[y(\mathbf{w}^T\mathbf{x}+b) \geq 1\]

Như vậy bài toán tối ưu margin có dạng như sau:

\[margin = \min_{i} \frac{y_i(\mathbf{w}^T\mathbf{x_i}+b)}{||\mathbf{w}||_2}\]

Do giá trị min đạt được tại điểm gần siêu phẳng trung tâm nhất nên đẳng thức (1) xảy ra. Do đó \[margin = \min\frac{1}{||\mathbf{w}||_2}\] Biểu diễn nghiệm tối ưu \((\mathbf{w}, b)\):

\[(\mathbf{w}, b) = \arg\min \frac{1}{||\mathbf{w}||_2}\] Thỏa mãn các điều kiện ràng buộc: \(y_i(\mathbf{w}^T\mathbf{x_i}+b) \geq 1, \forall i = \overline{1,n}\)

Bằng biến đổi để thu được hàm mục tiêu là hàm lồi ta có:

\[(\mathbf{w}, b) = \arg\max \frac{1}{2}||\mathbf{w}||_2^2\]

Thỏa mãn các điều kiện ràng buộc: \(1-y_i(\mathbf{w}^T\mathbf{x_i}+b) \leq 0, \forall i = \overline{1,n}\)

Hàm lagrangian của hàm mục tiêu:

\[\mathcal{L(\mathbf{w}, b, \mathbf{\lambda})} = \frac{1}{2}||\mathbf{w}||_2^2 + \sum_{i = 1}^{n}\lambda_i(1-y_i(\mathbf{w}^T\mathbf{x_i}+b))\]

Thỏa mãn các điều kiện ràng buộc: \[\begin{eqnarray} 1-y_i(\mathbf{w}^T\mathbf{x_i}+b) \leq 0, \forall i = \overline{1,n}&, &\\ \lambda_i \geq 0, \forall i = \overline{1,n} \end{eqnarray}\]

Theo phương pháp nhân tử lagrangian thì đạo hàm theo \(\mathbf{w}, b\) đều bằng 0. Điều này tương đương với:

\[\begin{eqnarray}\frac{\delta \mathcal{L(\mathbf{w}, b, \mathbf{\lambda})}}{\delta \mathbf{w}} &=& \mathbf{w}-\sum_{i=1}^{n}\lambda_iy_i\mathbf{x_i} = 0 \\ \frac{\delta \mathcal{L(\mathbf{w}, b, \mathbf{\lambda})}}{\delta b} &=& \mathbf{w}-\sum_{i=1}^{n}\lambda_iy_i = 0 \end{eqnarray}\]

Đặt \(V = [y_1\mathbf{x_1}, y_2\mathbf{x_2},...,y_n\mathbf{x_n}] \in \mathbb{R}^{d \times n}\) với \(d\) là số chiều của siêu phẳng.

Từ đạo hàm theo \(\mathbf{w}\) ta có: \[\mathbf{w}=\sum_{i=1}^{n}\lambda_iy_i\mathbf{x_i} = \mathbf{V}\mathbf{\lambda} \Rightarrow \mathbf{w}^T = \mathbf{\lambda}^{T}\mathbf{V}^T\] Do đó: \[\frac{1}{2}||\mathbf{w}||_2^2 = \frac{1}{2}\mathbf{w}^T\mathbf{w} = \frac{1}{2} \mathbf{\lambda}^T\mathbf{V}^T\mathbf{V}\mathbf{\lambda} \space (2)\]

Ta cũng chứng được: \[\sum_{i = 1}^{n}\lambda_iy_i\mathbf{w}^T\mathbf{x_i} = \mathbf{w}^T\sum_{i = 1}^{n}\lambda_iy_i\mathbf{x_i} = \mathbf{w}^{T}\mathbf{w} = ||\mathbf{w}||_2^2 \space (3)\]

Từ đó suy ra:

\[\begin{eqnarray}\mathcal{L(\mathbf{w}, b, \mathbf{\lambda})} &=& \frac{1}{2}||\mathbf{w}||_2^2 + \sum_{i = 1}^{n}\lambda_i(1-y_i(\mathbf{w}^T\mathbf{x_i}+b)) \\ &=& \frac{1}{2}||\mathbf{w}||_2^2+ \sum_{i=1}^{n}\lambda_i - \sum_{i = 1}^{n}\lambda_iy_i(\mathbf{w}^T\mathbf{x_i}+b) \\ &=& \frac{1}{2}||\mathbf{w}||_2^2+ \sum_{i=1}^{n}\lambda_i - \sum_{i = 1}^{n}\lambda_iy_i\mathbf{w}^T\mathbf{x_i} - b\sum_{i=1}^n \lambda_iy_i \\ \end{eqnarray}\]

Từ phương trình đạo hàm theo \(b\) của hàm lagrangian và đẳng thức (3) ta có:

\[\begin{eqnarray}\mathcal{L(\mathbf{w}, b, \mathbf{\lambda})} &=& \frac{1}{2}||\mathbf{w}||_2^2+ \sum_{i=1}^{n}\lambda_i - ||\mathbf{w}||_2^2\\ &=& -\frac{1}{2}\mathbf{w}^T\mathbf{w} + \mathbf{1}^T\mathbf{\lambda} \end{eqnarray}\]

Tiếp tục thế (2) vào phương trình trên ta thu được:

\[\begin{eqnarray}\mathcal{L(\mathbf{w}, b, \mathbf{\lambda})} &=& -\frac{1}{2} \mathbf{\lambda}^T\mathbf{V}^T\mathbf{V}\mathbf{\lambda} + \mathbf{1}^T\mathbf{\lambda} \end{eqnarray} \space (3)\] Do \(\mathbf{V}^{T}\mathbf{V}\) là một ma trận nửa xác định dương (ma trận có tất cả các hệ số không âm) nên \(\mathcal{L(\mathbf{w}, b, \mathbf{\lambda})}\) là một hàm concave bậc 2 theo \(\mathbf{\lambda}\).

Nhắc lại một số định lý về tối ưu lồi:

\[\begin{eqnarray} \mathbf{x} &=& \arg \min_{\mathbf{x}} \frac{1}{2}\mathbf{x}^T\mathbf{Px} + \mathbf{q}^T\mathbf{x} + r \\ \text{subject to:}~ && \mathbf{Ax} = \mathbf{b} \end{eqnarray}\]

với \(P\) là ma trân nửa xác định dương (có các hệ số không âm) thì bài toán tối ưu là Strict convex.

Khi Strong duality xảy ra thì nghiệm của bài toán gốc và bài toán đối ngẫu đều phải thỏa mãn hệ điều kiện Karush-Kuhn-Tucker (KKT):

  1. Mọi ràng buộc của bài toán gốc đều phải thỏa mãn.

  2. Các hệ số \(\lambda_i \geq 0\).

  3. Đối với các ràng buộc dạng bất đẳng thức dạng \(f_i(\mathbf{x})\leq 0\) thì tích của hệ số \(\lambda_i f_i(\mathbf{x}) = 0\).

  4. Đạo hàm của hàm lagrangian theo các nhân tử lagrangian \(\lambda_i\) và các biến số \((\mathbf{w},b)\) phải bằng 0.

Đối với trường hợp hàm mục tiêu là lồi thì điều kiện KKT vừa là điều kiện cần và đủ.

Theo một định lý về tối ưu hóa lồi (có lẽ nằm ngoài nội dung trình bày ở đây, chúng ta tạm chấp nhận điều này) nếu hàm đối ngẫu là hàm strictly convex và điều kiện slater thỏa mãn thì bài toán tối ưu hóa là strong duality. Khi điều kiện strong duality được thỏa mãn thì hệ điều kiện KKT là điều kiện cần và đủ của bài toán tức là nghiệm optimal value sẽ là nghiệm của hệ điều kiện KKT. Đối với bài toán của chúng ta đều thỏa mãn điều kiện slater và strictly convex nên nghiệm của bài toán chính là nghiệm của hệ điều kiện KKT.

Hệ điều kiện KKT đối với bài toán SVM:

  1. \(1 - y_i(\mathbf{w}^T\mathbf{x_i}+b) \leq 0, \forall i = \overline{1,n}\)

  2. \(\lambda_i \geq 0, \forall i = \overline{1,n}\)

  3. \(\lambda_i(1 - y_i(\mathbf{w}^T\mathbf{x_i}+b)) = 0, \forall i = \overline{1,n}\) Từ đó suy ra \(\lambda_i = 0\) hoặc \(1 - y_i(\mathbf{w}^T\mathbf{x_i}+b) = 0\). Thông thường số lượng \(1 - y_i(\mathbf{w}^T\mathbf{x_i}+b) = 0\) là rất ít và những điểm thuộc tợp hợp này sẽ được gọi chung là support vector.


  4. \[\begin{eqnarray}\frac{\delta \mathcal{L(\mathbf{w}, b, \mathbf{\lambda})}}{\delta \mathbf{w}} &=& \mathbf{w}-\sum_{i=1}^{n}\lambda_iy_i\mathbf{x_i} = 0 \\ \frac{\delta \mathcal{L(\mathbf{w}, b, \mathbf{\lambda})}}{\delta b} &=& \mathbf{w}-\sum_{i=1}^{n}\lambda_iy_i = 0 \end{eqnarray}\]

Mấu chốt của bài toán là tìm lời giải cho \(\mathcal{L(\mathbf{w}, b, \mathbf{\lambda})}\) có dạng strict concave được biến đổi từ (3):

\[\begin{eqnarray}\mathbf{\lambda} &=& \arg \max_\lambda (-\frac{1}{2} \mathbf{\lambda}^T\mathbf{V}^T\mathbf{V}\mathbf{\lambda} + \mathbf{1}^T\mathbf{\lambda}) \end{eqnarray}\]

Thỏa mãn: \[\lambda_i \geq 0,\forall i = \overline{1,n} \]

Từ optimal value \(\lambda\) vừa tìm được thế vào phương trình đạo hàm theo \(b\) để tìm được \(b\) và đạo hàm theo \(\mathbf{w}\) để tìm được \(\mathbf{w}\). Từ đó ta sẽ tìm được siêu phẳng trung tâm.