1. 支持向量机模型的数学推导

1.1.超平面

首先展示二维和三维空间的两个简单的例子 $$\begin{gathered} 二维：w_1{x}_1+w_2{x}_2+b=0 \\ 三维：w_1{x}_1+w_2{x}_2+w_3{x}_3+b=0 \end{gathered}$$ 那么，我们一般化，可以得到 $$w^{T}x+b=0$$ $$w={\left(\begin{array}{c}{w}_1\\ w_2\\ ⋮\\ w_d\end{array}\right)}_{d\times 1}x={\left(\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_d\end{array}\right)}_{d\times 1}$$ 超平面有以下三个性质：

原点到超平面的距离 $$dist(0,H)=\frac{|b|}{||w||}$$判断任意一点$X_0$和超平面的相对位置 $$\begin{gathered} w^T{x}_0+b>0⟹aboveH \\ {w}^T{x}_0+b<0⟹belowH \\ {w}^T{x}_0+b=0⟹onH \end{gathered}$$任意一点$X_0$到超平面的距离 $$dist(x_0,H)=\frac{w^T{x}_0+b}{||w||}$$

1.2.二分类问题

现在我们面临的是一个二分类的问题，数据集为 $$D=\{(x_i,y_i),x_i\in R^d,y_i=\pm 1\}$$ 如果存在一个超平面$W^{T}X+b=0$能够将它们正确分类的话，那么 $$f^{\ast }(x)=sgn(w^{T}x+b)=\{\begin{array}{r}+1(w^{T}x+b>0)\\ -1(w^{T}x+b<0)\end{array}$$ 需要优化的参数是$W^T$和$b$。定义$margin$是离超平面最近的点到超平面的距离，我们需要最大化这个距离，且需要一个约束条件保证了这个超平面能够正确将点分类。由于一旦满足约束条件，均方误差就为0，所以采用最小化均方误差是无意义的。因此，我们的目标优化函数是 $$\{\begin{array}{l}{\max }_{w,b}{\min }_{i=1,2,\cdots ,N}\frac{|w^T{x}_i+b|}{||w||}\\ s.t.y_i(w^T{x}_i+b)>0\forall i\end{array}(1)$$

1.3.支持向量机模型的数学推导¹

首先转化一下约束条件： $$\begin{array}{rl}{y}_i(w^T{x}_i+b)& \ge \min y_i(w^T{x}_i+b)\\ & =\underset{1,2,\cdots ,N}{\min }|w^T{x}_i+b|\end{array}$$ 令 $$\lambda =\frac{1}{{\min }_{1,2,\cdots ,N}|w^T{x}_i+b|}$$ 那么目标函数 $$\begin{array}{rl}\underset{w,b}{\max }\underset{i=1,2,\cdots ,N}{\min }\frac{|w^T{x}_i+b|}{||w||}& =\underset{w,b}{\max }\frac{1}{\lambda ||w||}\lambda \underset{i=1,2,\cdots ,N}{\min }|w^T{x}_i+b|\\ & =\underset{w,b}{\max }\frac{1}{\lambda ||w||}\end{array}$$ 因此，化简到这一阶段，我们的目标优化函数变为

$$\{\begin{array}{l}{\max }_{w,b}\frac{1}{\lambda ||w||}\\ s.t.y_i(w^T{x}_i+b)\ge \frac{1}{\lambda }\forall i\end{array}(2)$$ 接下来我们定义 $$\begin{gathered} \tilde{w}=\lambda w \\ \tilde{b}=\lambda b \end{gathered}$$ 所以 $$\{\begin{array}{l}{\max }_{\tilde{w},\tilde{b}}\frac{1}{||\tilde{w}||}\\ s.t.y_i({\tilde{w}}^T{x}_i+\tilde{b})\ge 1\forall i\end{array}(3)$$ 然后，我们去掉$\sim$，目标优化函数更新为 $$\begin{gathered} \{\begin{array}{l}{\max }_{w,b}\frac{1}{||w||}\\ s.t.y_i(w^T{x}_i+b)\ge 1\forall i\end{array}(4) \\ \{\begin{array}{l}{\min }_{w,b}\frac{1}{2}||w|{|}^2\\ s.t.1-y_i(w^T{x}_i+b)\le 0\forall i\end{array}(5) \end{gathered}$$ $(5)$是我们的带约束的原问题，也就是$primalproblem$。然后，我们运用拉格朗日乘数法 $$\begin{gathered} \{\begin{array}{l}z=(w,b)\\ F(z)=\frac{1}{2}||w|{|}^2\\ G_i(z)=1-y_i(w^T{x}_i+b)\end{array} \\ ⟹L(w,b,\mu )=\frac{1}{2}||w|{|}^2+\sum _{i=1}^N{\mu }_i(1-y_i(w^T{x}_i+b)) \\ ⟹\{\begin{array}{l}{\min }_{w,b}{\max }_{\mu }L(w,b,\mu )\\ s.t.{\mu }_i\ge 0\forall i\end{array}(6) \end{gathered}$$ 这样$(6)$就是不带约束条件的原问题。由于目标优化函数是凸二次函数，并且约束条件是线性的，所以满足强对偶关的条件。其对偶问题是 $$\{\begin{array}{l}ma{x}_{\mu }{\min }_{w,b}L(w,b,\mu )\\ s.t.{\mu }_i\ge 0\forall i\end{array}(7)$$ 所以 $$\begin{array}{rl}\frac{\partial L(w,b,\mu )}{\partial b}& =\frac{\partial \left({\sum }_{i=1}^N{\mu }_i\right(1-y_i(w^T{x}_i+b)\left)\right)}{\partial b}=0(8)\\ \frac{\partial L(w,b,\mu )}{\partial w}& =\frac{\partial (\frac{1}{2}{w}^{T}w+{\sum }_{i=1}^N{\mu }_i-{\sum }_{i=1}^N{\mu }_i{y}_i{w}^T{x}_i-{\sum }_{i=1}^N{\mu }_i{y}_{i}b)}{\partial w}=0(9)\end{array}$$ 由$(8)$得到 $$\sum _{i=1}^N{\mu }_i{y}_i=0(10)$$ 将$(10)$带入$(9)$中，得到 $$\begin{gathered} \frac{\partial L}{\partial w}=w-\sum _{i=1}^N{\mu }_i{y}_i{x}_i=0 \\ ⟹w=\sum _{i=1}^N{\mu }_i{y}_i{x}_i(11) \end{gathered}$$ 然后将$(10)$和$(11)$带入$L(w,b,\mu )$中，得到 $$\begin{array}{rl}L(w,b,\mu )& =\frac{1}{2}(\sum _{i=1}^N{\mu }_i{y}_i{x}_i{)}^T(\sum _{i=1}^N{\mu }_i{y}_i{x}_i)-\sum _{i=1}^N{\mu }_i{y}_i(\sum _{i=1}^N{\mu }_i{y}_i{x}_i{)}^T{x}_i+\sum _{i=1}^N{\mu }_i\\ & =\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\mu }_i{\mu }_j{y}_i{y}_j{x}_i{x}_j-\sum _{i=1}^N\sum _{j=1}^N{\mu }_i{\mu }_j{y}_i{y}_j{x}_j^T{x}_i+\sum _{i=1}^N{\mu }_i\\ & =\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\mu }_i{\mu }_j{y}_i{y}_j{x}_i{x}_j-\sum _{i=1}^N\sum _{j=1}^N{\mu }_i{\mu }_j{y}_i{y}_j{x}_i^T{x}_j+\sum _{i=1}^N{\mu }_i\\ & =-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\mu }_i{\mu }_j{y}_i{y}_j{x}_i{x}_j+\sum _{i=1}^N{\mu }_i\end{array}$$ 现在我们的优化目标变为 $$\begin{gathered} \{\begin{array}{l}{\min }_{\mu }-\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\mu }_i{\mu }_j{y}_i{y}_j{x}_i{x}_j+{\sum }_{i=1}^N{\mu }_i\\ s.t.{\mu }_i\ge 0\forall i\\ s.t.{\sum }_{i=1}^N{\mu }_i{y}_i=0\end{array}(12) \\ ⟹\frac{\partial (-\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\mu }_i{\mu }_j{y}_i{y}_j{x}_i{x}_j+{\sum }_{i=1}^N{\mu }_i)}{\partial \mu }=0(13) \end{gathered}$$ 由$(13)$得到$\hat{\mu }$，然后带入$(11)$中得到$\hat{w}$，又由于 $$\exists (x_k,y_k)s.t.1-y_k(w^T{x}_k+b)=0$$ 所以 $$\begin{gathered} y_k^2(w^T{x}_k+b)=y_k \\ ⟹(w^T{x}_k+b)=y_k \\ ⟹b=y_k-(\sum _{i=1}^N{\mu }_i{y}_i{x}_i{)}^T{x}_k(14) \end{gathered}$$ 将$\hat{\mu }$带入$(14)$中得到$\hat{b}$。此时$\hat{w}$和$\hat{b}$都已经求出，于是 $$\hat{f}(x)=sgn(\hat{w}x+\hat{b})$$

1.4. 简单支持向量机模型的例子

数据点$x_1$$x_2$$y$A1.01.5+1B1.52.4+1C1.51.0-1

下面我们用python绘制出这些点在二维平面的位置。

import matplotlib.pyplot as plt import numpy as np x = np.linspace(0, 3, 100) y = x plt.title("Data Points") plt.xlim(xmax=3, xmin=0) plt.ylim(ymax=3, ymin=0) plt.xlabel("x1") plt.ylabel("x2") plt.plot([1.0, 1.5],[1.5, 2.4],'ro') plt.plot([1.5],[1.0],'bo') plt.plot(x, y, c='green') plt.annotate(text='A', xy=(1.0, 1.5)) plt.annotate(text='B', xy=(1.5, 2.4)) plt.annotate(text='C', xy=(1.5, 1.0)) plt.show()

如果仅仅用肉眼观察，选择一条直线来区分红色的点和蓝色的点，那么这条直线应该与x=y相接近，也就是绿色的线。

我们将数据代入式(8)， $$\begin{array}{r}\frac{\partial (-\frac{1}{2}{\sum }_{i=1}^3{\sum }_{j=1}^3{\mu }_i{\mu }_j{y}_i{y}_j{x}_i{x}_j+{\sum }_{i=1}^3{\mu }_i)}{\partial \mu }=0\end{array}$$

$$\begin{array}{rl}-\frac{1}{2}\sum _{i=1}^3\sum _{j=1}^3{\mu }_i{\mu }_j{y}_i{y}_j{x}_i{x}_j+\sum _{i=1}^3{\mu }_i& =-\frac{1}{2}\sum _{i=1}^3({\mu }_i{\mu }_1{y}_i{y}_1{x}_i{x}_1+{\mu }_i{\mu }_2{y}_i{y}_2{x}_i{x}_2+{\mu }_i{\mu }_3{y}_i{y}_3{x}_i{x}_3)+\sum _{i=1}^3{\mu }_i\\ & =-\frac{1}{2}({\mu }_1{\mu }_1{y}_1{y}_1{x}_1{x}_1+{\mu }_1{\mu }_2{y}_1{y}_2{x}_1{x}_2+{\mu }_1{\mu }_3{y}_1{y}_3{x}_1{x}_3+{\mu }_2{\mu }_1{y}_2{y}_1{x}_2{x}_1+{\mu }_2{\mu }_2{y}_2{y}_2{x}_2{x}_2+{\mu }_2{\mu }_3{y}_2{y}_3{x}_2{x}_3+{\mu }_3{\mu }_1{y}_3{y}_1{x}_3{x}_1+{\mu }_3{\mu }_2{y}_3{y}_2{x}_3{x}_2+{\mu }_3{\mu }_3{y}_3{y}_3{x}_3{x}_3)+{\mu }_1+{\mu }_2+{\mu }_3\end{array}$$ 对${\mu }_1$，${\mu }_2$和${\mu }_3$求导得到 $$\begin{gathered} -\frac{1}{2}(2y_1{y}_1{x}_1{x}_1{\mu }_1+{\mu }_2{y}_1{y}_2{x}_1{x}_2+{\mu }_3{y}_1{y}_3{x}_1{x}_3+{\mu }_2{y}_2{y}_1{x}_2{x}_1+{\mu }_3{y}_3{y}_1{x}_3{x}_1)+1=0(15) \\ -\frac{1}{2}({\mu }_1{y}_1{y}_2{x}_1{x}_2+{\mu }_1{y}_2{y}_1{x}_2{x}_1+2{\mu }_2{y}_2{y}_2{x}_2{x}_2+{\mu }_3{y}_2{y}_3{x}_2{x}_3+{\mu }_3{y}_3{y}_2{x}_3{x}_2)+1=0(16) \\ -\frac{1}{2}({\mu }_1{y}_1{y}_3{x}_1{x}_3+{\mu }_2{y}_2{y}_3{x}_2{x}_3+{\mu }_1{y}_3{y}_1{x}_3{x}_1+{\mu }_2{y}_3{y}_2{x}_3{x}_2+2{\mu }_3{y}_3{y}_3{x}_3{x}_3)+1=0(17) \end{gathered}$$

---

该推导过程参考新加坡国立大学“Foundations of Machine Learning”课程和bilibili的up主“shuhuai008”的视频。 ↩︎