支持向量机

支持向量机(SVM)

范数(Norm)

范数常常被用来度量某个向量空间（或矩阵）中的每个向量的长度或大小。下文中提到的类似 $\Vert x \Vert$ 都指的是 2-范数（也就是通常意义下的距离）：

$$\Vert x \Vert_2=\sqrt{x_1^2+x_2^2+\cdots+x_n^2}$$

超平面(Hyperplane)

超平面表达式

超平面是 $n$ 维欧氏空间中 $n-1$ 维度的线性子空间，可以把线性空间分割成不相交的两部分。比如一个三维空间中的一个二维平面可以把这个三维空间分成两份；一个二维的平面可以被一条一维的直线分成两半。更多维的情况也可以有超平面的存在，只不过很难想象。

上图是一个三维平面 $\mathbb R^3$ 的截面图，$\omega~(\omega_1,\omega_2,\omega_3)$ 是过原点的平面 $x\cdot \omega=0$ 的法向量，现将这个平面沿着法向量 $\omega$ 向上移动一段距离。假设平移之后的新平面经过点 $a~ (\alpha,\beta,\gamma)$，新平面上的任意一点 $x~(x,y,z)$ 都有：

$$(\vec x-\vec a)\cdot\omega=0$$

可由整理得：

$$\begin{align} (\vec x-\vec a)\cdot\omega &= 0\\ (x-\alpha,y-\beta,z-\gamma)\cdot(\omega_1,\omega_2,\omega_3) &= 0\\ \omega_1x+\omega_2y+\omega_3z-(\omega_1\alpha+\omega_2\beta+\omega_3\gamma )&=0 \end{align}$$

因为 $a$ 是已知点，则令 $b=-(\omega_1\alpha+\omega_2\beta+\omega_3\gamma
)$，则：可得出超平面表达式：

$$\omega^Tx+b=0$$

可以看出，超平面公式可以用来表示所有法向量是 $\omega$ 的平面。

点到超平面的距离

图中 $x$ 为平面外的一点，$a~ (\alpha,\beta,\gamma)$ 还是超平面 $\omega^Tx+b=0$ 上的点，要求出点道明面对距离 $d$。

我们可以看出：

$$\cos\theta =\frac{d}{\Vert x-a\Vert}$$

而 $\theta$ 也是法向量 $\omega$ 与 $x-a$ 的夹角，所以：

$$|(x-a)\cdot\omega|=\Vert x-a\Vert\times\Vert\omega\Vert\times \cos\theta$$

前两个式子联立，再令 $b=-\omega^Ta$ 可得：

$$d =\frac{|\omega^Tx+b|}{\Vert\omega\Vert}$$

拉格朗日乘数法

高等数学用拉格朗日乘数法来求解的问题是这样的：

$$\begin{align} \min~~ &f(x)\\ \text {s.t.}~~&h_i(x)=0 \end{align}$$

解法是这样的：令

$$L(x,\beta_i)=f(x)+\sum_i [\beta_ih_i(x)]$$

再让所有未知数的偏导数为零：

$$\frac{\partial L}{\partial x}=0;~\frac{\partial L}{\partial \beta_i}=0$$

因为 $\frac{\partial L}{\partial \beta_i}=0$ 可以保障所有的约束条件都可以成立，那么通过求解上面的式子就可以求出最优结果。但是如果约束中还存在不等式，那么该如何求解极值，并且保证所有约束都成立呢？比如下面的问题：

假设 $f(x),g_i(x),h_j(x)$ 函数是在 $\mathbb R^n$ 上的连续可微函数，有最小化的约束问题：

$$\begin{align} \min ~~&f(x)\\ \text{s.t.} ~~&\begin{cases} g_i(x)\leq0 &(i=1,2,\dots m)\\ h_j(x)=0 &(j=1,2,\dots n) \end{cases} \end{align}$$

可以引入广义拉格朗日函数解决问题，其中 $\lambda_i\geq0$，$\lambda_i,\beta_j$ 为拉格朗日乘子：

$$L(x,\lambda,\beta)=f(x)+\sum_{i=1}^m \lambda_ig_i(x)+\sum_{j=1}^n \beta_jh_j(x)$$

原来的问题就变成了：

$$\begin{align} \min_x~~&L(x,\lambda,\beta)\\ \text{s.t.}~~&\lambda_i\geq0 \end{align}$$

求解这个函数不仅只需要求解出 $x$，而且还需要知道 $\lambda_i,\beta_j$。我们可以不管 $x$，先将函数看作$\lambda_i,\beta_j$构成的函数，并且求其最大值，然后再将函数看作 $x$ 的最小值，这样对结果似乎不产生什么影响：

$$\min_x\{\max_{\lambda,\beta}L(x,\lambda,\beta)\}$$

那这么做有什么必要呢？可以通过求 $\max_{\lambda,\beta}L(x,\lambda,\beta)$ 来筛选掉那些不符合 $g_i(x)\leq0$ 约束的解。对拉格朗日函数 $L(x,\lambda,\beta)$ 而言，有两种情况可以讨论：

• 如果 $gi(x)>0$，且 $\lambda_i\geq0$，那么$\lambda_i$可以随便取值，$\max{\lambda,\beta}L(x,\lambda,\beta)$ 就是无穷大
• 如果 $gi(x)\leq0$，那么只有 $\lambda_i=0$ 的时候才能取最大值，那么拉格朗日方程就能化成 $\max{\lambda,\beta}L(x,\lambda,\beta)=f(x)+\sum_{j} \beta_jh_j(x)$

最后当我们求目标函数 $\minx{\max{\lambda,\beta}L(x,\lambda,\beta)}$ 的结果就是在求上面两种情况的最小值 $\minx{\infty,f(x)+\sum{j} \beta_jh_j(x)}$。显而易见，我们就可以求出最后的结果了。

对偶问题(Dual Problem)

如果这个拉格朗日函数极值不是那么好求解，我们可以将这个问题变成对偶问题(dual problem)再求解。

令 $\thetap(x)=\max{\lambda,\beta} L(x,\lambda,\beta)$；$\theta_d(\lambda,\beta)=\min_xL(x,\lambda,\beta)$，则 $\theta_p(x)$ 与 $\theta_d(\lambda,\beta)$ 互为对偶问题。

这里解释一下：

比如下面是一个线性规划问题和它的对偶问题：

$$\begin{align} &\max~~ z=2x_1+5x_2 &\min~~ w=2\lambda_1+3\lambda_2\\ &\text{s.t.} \begin{cases} ~~x_1+2x_2\leq2\\ 3x_1+4x_4\leq3\\ x_1,x_2\geq0 \end{cases} \qquad &\text{s.t.} \begin{cases} ~~\lambda_1+3\lambda_2\geq2\\ 2\lambda_1+4\lambda_4\geq5\\ \lambda_1,\lambda_2\geq0 \end{cases} \end{align}$$

如果我们把这两个问题都化成拉格朗日方程，则有：

$$\max_x z=2x_1+5x_2+\lambda_1(2-x_1-2x_2)+\lambda_2(3-3x_3-4x_2)\\ \min_\lambda w=2\lambda_1+3\lambda_2+x_1(2-\lambda_1-3\lambda_2)+x_2(5-2\lambda_3-4\lambda_2)$$

$z,w$ 是一样的，只不过自变量不同，所以有 $\maxxL(x,\lambda)$ 与 $\min\lambda L(x,\lambda)$ 互为对偶关系，并且 $x$ 与 $\lambda$ 互为对偶变量。

根据对偶问题的的弱对偶性可以得出下列的不等式：

$$\theta_d(\lambda,\beta)=\min_xL(x,\lambda,\beta)\leq L(x,\lambda,\beta)\leq \max_{\lambda,\beta} L(x,\lambda,\beta)=\theta_p(x)$$

根据对偶问题的的强对偶性可以知道：如果原问题和对偶问题都具有可行解，那么对偶问题与原问题的最优解相等，也就是说：

$$\max_{\lambda,\beta}\{\min_xL(x,\lambda,\beta)\}= \min_x\{\max_{\lambda,\beta}L(x,\lambda,\beta)\}$$

KKT条件(Karush-Kuhn-Tucker Conditions)

KKT条件就是原问题和对偶问题拥有最优解的充要条件，也是在求解拉格朗日方程的时候需要遵守的约束：

$$\begin{cases} \nabla_xL(x,\lambda,\beta)=0\\ \nabla_\lambda L(x,\lambda,\beta)=0\\ \nabla_\beta L(x,\lambda,\beta)=0\\ \lambda_ig_i(x)=0~~~^*\\ \lambda_i\geq 0\\ g_i(x)\leq0\\ h_j(x)=0 \end{cases}$$

其中第四条是根据对偶问题的松弛互补性得出来的。

支持向量机模型

上面写的只是在推导SVM模型时需要的数学基础，下面要说的是SVM的基本模型。

在一个二分类的问题中，我们希望在样本空间中有一个超平面，能将不同类别的样本分开。在一个既定的样本训练集中，如何选择超平面才能更好的区分正\负样本呢？

我们想要选择在两类训练样本最中间，而且离两类样本都很远的超平面作为决策边界，就像图里的加粗的直线那样。那么这个决策边界所对应的结果鲁棒性是最高的，泛化能力最强。

鲁棒性(Robust)就是指在异常和危险情况下系统生存的能力，在这里就是指模型很稳定，泛化能力好。

于是我们可以用 $\omega^Tx+b=0$ 来表示这个超平面，那么样本空间中的任意一点到这个超平面的距离为：

$$d =\frac{|\omega^Tx+b|}{\Vert \omega\Vert}$$

超平面可以正确的对样本进行分类，那么会有：

$$\begin{cases} \omega^Tx^{(i)}+b\geq1\quad\quad& y^{(i)}=1\\ \omega^Tx^{(i)}+b\leq-1 &y^{(i)}=-1 \end{cases}$$

我们所需要寻找的就是在既定正负样本集的分解中存在的最大间隔 $\gamma$，可能这个间隔等于 $2\delta$ ，那么就有 $\omega^Tx^{(i)}+b\geq\delta$ 和 $\omega^Tx^{(i)}+b\leq-\delta$，可以通过线性变换将这个式子变换成上面的样子。

还有这里的负样本用 $-1$ 表示是因为在下面的计算中这样更简洁。

上图中圈出的样本点可以使上式中的等号成立，他们被叫做支持向量。我们所寻找的间隔(margin)，也就是两个超平面的距离可以表示为：

$$\gamma =\frac{2}{\Vert \omega\Vert}$$

支持向量机模型中需要寻找的具有最大间隔的决策超平面，也就需要满足下面的规划问题：

$$\begin{align} \max_{\omega,b}~~&\frac{2}{\Vert \omega\Vert}\\ \text{s.t.}~~&y^{(i)}(\omega^Tx^{(i)}+b)\geq1\quad i=1,2,\dots ,m \end{align}$$

可以把上面的规划问题转化成下面的样子：

$$\begin{align} \min_{\omega,b}~~&\frac{1}{2}\Vert \omega\Vert^2\\ \text{s.t.}~~&1-y^{(i)}(\omega^Tx^{(i)}+b)\leq0~~~~~i=1,2,\dots ,m \end{align}$$

使用拉格朗日乘数法，写出这个规划的拉格朗日函数 $L(\omega,b,\alpha)$：

$$L(\omega,b,\alpha)=\frac{1}{2}\Vert \omega\Vert^2+\sum_{i=1}^{m}\alpha_i(1-y^{(i)}(\omega^Tx^{(i)}+b))$$

分别对 $\omega,b$ 求偏导，令其为 $0$ 可以得到：

$$\begin{align} \omega-\sum_{i=1}^{m}\alpha_iy^{(i)}x^{(i)}&=0\\ \sum_{i=1}^{m}\alpha_iy^{(i)}&=0 \end{align}$$

带入 $L(\omega,b,\alpha)$ 中，可以消去 $\omega,b$：

$$\begin{align} \min _{\omega,b}L(\omega,b,\alpha)=&\frac{1}{2}\Vert \omega\Vert^2+\sum_{i=1}^{m}\alpha_i(1-y^{(i)}(\omega^Tx^{(i)}+b))\\ =&\frac{1}{2}\omega^T\omega+\sum_{i=1}^{m}\alpha_i-\sum_{i=1}^{m}\alpha_iy^{(i)}\omega^Tx^{(i)}+\sum_{i=1}^{m}\alpha_ib\\ =&\frac{1}{2}\sum_{j=1}^{m}\alpha_j(y^{(j)}x^{(j)})^T\sum_{i=1}^{m}\alpha_iy^{(i)}x^{(i)} +\sum_{i=1}^{m}\alpha_i\\&-\sum_{i=1}^{m}\alpha_iy^{(i)}\Bigr(\sum_{j=1}^{m}\alpha_j(y^{(j)}x^{(j)})^T\Bigr)x^{(i)} \\ =&\sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m} \alpha_i\alpha_jy^{(i)}y^{(j)}x^{(i)^T}x^{(j)} \end{align}$$

根据之前提到的对偶问题，可以得出：

$$\min_{\omega,b}L(\omega,b,\alpha)=\min_{\omega,b}\{\max_\alpha L(\omega,b,\alpha)\}=\max_{\alpha}\{\min_{\omega,b} L(\omega,b,\alpha)\}$$

那么求出下式对偶问题的解，就相当于求出原问题的最优解：

$$\begin{align} \max_\alpha~~&\sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m} \alpha_i\alpha_jy^{(i)}y^{(j)}x^{(i)^T}x^{(j)}\\ \text{s.t.}~~& \sum_{i=1}^{m}\alpha_iy^{(i)}=0\\ &\alpha\geq0\qquad i=1,2,\dots ,m \end{align}$$

求解上面的的规划问题，可以运用SMO(Sequential Minimal Optimization)算法。先选取一对要更新的变量 $\alpha_i$ 和 $\alpha_j$；再固定除了$\alpha_i$ 和 $\alpha_j$ 之外的其他参数求解上面的式子获得更新后的 $\alpha_i$ 和 $\alpha_j$。

上面选取的 $\alpha_i$ 和 $\alpha_j$ 中有一个不满足KKT条件，目标函数值就会在迭代后减小。于是我们就可以将 $\alpha_i$ 选取为最不满足KKT条件的变量，$\alpha_j$ 选取为能使目标函数更改最大的变量，这样就可以最快的最优化目标函数值。但是这样又很麻烦，所以SMO采用的是：选取的 $\alpha_i$ 和 $\alpha_j$ 所对应的样本点间隔最大，那么这样就可以对目标函数进行最大的变化。

解出 $\alpha$ 后，就可以将 $\alpha$ 代入，求解出模型：

$$f(x)=\omega^Tx+b=\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)^T}x+b$$

上述过程需要满足KKT条件，也就是：

$$\begin{cases} \alpha_i(1-y^{(i)}(\omega^Tx^{(i)}+b))=0~~~^*\\ \alpha_i\geq 0\\ 1-y^{(i)}(\omega^Tx^{(i)}+b))\leq0\\ \end{cases}$$

上面的星式可以说明：当 $y^{(i)}(\omega^Tx^{(i)}+b)=1$ 时，也就时样本点 $i$ 为支持向量时，$\alpha_i$ 不必为 $0$，那么这个样本就会对决策边界产生影响；相反地，如果 $y^{(k)}(\omega^Tx^{(k)}+b)\neq1$ 时，$\alpha_k=0$，那么这个样本点 $k$ 就不要会对决策边界产生影响。换句话说，最终的支持向量机模型只与支持向量有关。

软间隔支持向量机(Soft Margin SVM)

软间隔支持向量机与上面的比较僵硬的模型相比，要求条件变得不那么严苛，并不需要把每个训练集中的样本点都准确的分隔开，而允许样本点存在一些噪声。当你观察样本点绝的他们大致可分，而界限不那么明显时，就会用到软间隔SVM模型，它允许样本集中某些样本点不符合约束 $y^{(i)}(\omega^Tx^{(i)}+b)\geq1$。

如上图中不符合约束的点存在：

$$\begin{cases} \omega^Tx^{(s)}+b<1\quad ~~~y^{(s)}=1\\ \omega^Tx^{(t)}+b>-1\quad y^{(t)}=-1 \end{cases}$$

那么目标函数（或者说损失函数）就可以写为：

$$\min_{\omega,b}\frac{1}{2}\Vert \omega\Vert^2+C\sum_{i=1}^m\ell_{hinge}(y^{(i)}(\omega^Tx^{(i)}+b))$$

其中 $C>0$ 是一个常数， $\ell_{hinge}$是“hinge损失函数”：

$$\ell_{hinge}(z)=\max\{0,1-z\}$$

可以将目标函数理解成逻辑回归中损失函数的变形：

$$\begin{align} &\min _\theta J(\theta) = \frac{1}{m}\sum_{i=1}^m Cost(h_\theta(x^{(i)})-y^{(i)})^2+\frac{\lambda}{m}\sum_{j=1}^n\theta_j^2\\ \Rightarrow&\min _{\omega,b}L= C\sum_{i=1}^m\ell_{hinge}(y^{(i)}(\omega^Tx^{(i)}+b))+\frac{1}{2}\Vert \omega\Vert^2 \end{align}$$

正则化程度越大，则$C$越小。

引入松弛变量(slack variables) $\xi_i$，令不满足约束的样本点 $(x^{(s)},y^{(s)})$ 使 $y^{(s)}(\omega^Tx^{(s)}+b)+\xi_s=1$ ，则可以将规划问题重写为：

$$\begin{align} \min_{\omega,b,\xi_i}~~&\frac{1}{2}\Vert \omega\Vert^2+C\sum_{i=1}^m\xi_i\\ \text{s.t.}~~& \begin{cases} y^{(i)}(\omega^Tx^{(i)}+b)\geq1-\xi_i\\ \xi_i\geq0~~~~~~~~~~~~~i=1,2,\dots ,m \end{cases} \end{align}$$

写出拉格朗日函数：

$$\begin{align} L(\omega,b,\alpha,\xi,\mu)=&\frac{1}{2}\Vert \omega\Vert^2+C\sum_{i=1}^m\xi_i+\sum_{i=1}^{m}\alpha_i(1-\xi_i-y^{(i)}(\omega^Tx^{(i)}+b))\\&-\sum_{i=1}^{m}\mu_i\xi_i \end{align}$$

分别对$\omega,b,\xi_i$求偏导，令其为$0$可以得到：

$$\begin{align} \omega-\sum_{i=1}^{m}\alpha_iy^{(i)}x^{(i)}&=0\\\sum_{i=1}^{m}\alpha_iy^{(i)}&=0\\ C-\alpha_i-\mu_i&=0 \end{align}$$

代入拉格朗日函数就可以得到原问题的对偶问题：

$$\begin{align} \max_\alpha~~&\sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m} \alpha_i\alpha_jy^{(i)}y^{(j)}x^{(i)^T}x^{(j)}\\ \text{s.t.}~~& \begin{cases} \sum_{i=1}^{m}\alpha_iy^{(i)}=0\\ 0\leq\alpha\leq C~~~~~~~~~~~~~i=1,2,\dots ,m \end{cases} \end{align}$$

KKT条件要求如下：

$$\begin{cases} \alpha_i\geq 0;\quad \mu_i\geq 0;\quad\xi_i\geq 0\\ \mu_i\xi_i=0\\ \alpha_i(1-\xi_i-y^{(i)}(\omega^Tx^{(i)}+b))=0\\ 1-\xi_i-y^{(i)}(\omega^Tx^{(i)}+b))\leq0\\ \end{cases}$$

当 $\alpha_i=0$ 时，则$i$样本点不会对模型产生影响；当 $\alpha_i>0$ 时，$1-\xi_i-y^{(i)}(\omega^Tx^{(i)}+b)=0$，则 $i$ 样本点是支持向量：当 $\alpha<C$ 时，$\mu_i\neq0$，$\xi_i=0$，样本点落在边界上；当 $\alpha=C$ 时，$\mu_i=0$：若 $\xi_i\leq1$，则样本点被正确分类；反之，若 $\xi_i\geq1$，则样本点分类错误，损失函数就会大大增加。

核函数(Kernel Function)

如果一个二分类问题不是线性可分的，不存在可以把两类样本点分开超平面，那么问题可以通过利用核函数来解决。

如果某个二维的样本集在不是线性可分，那么可以将这个二维样本集通过某个映射函数 $\phi(x)$ 将二维的样本点映射到三维空间中。在三维的样本空间中，就可以找到一个合适的划分超平面。而且如果问题的属性有限，也就是样本维度有限，那么上述的步骤是可以推广到更多维度的。

令 $\phi(x)$ 表示将 $x\in\mathbb{R}^n$ 映射至 $n+1$ 维空间中的特征向量，那么这个可以划分样本的超平面可以表示为

$$f(x)=\omega^T\phi(x)+b$$

那么根据上面写到的SVM计算过程，则可以将分类问题抽象成规划问题：

$$\begin{align} \min_{\omega,b}~~&\frac{1}{2}\Vert \omega\Vert^2\\ \text{s.t.}~~&1-y^{(i)}(\omega^T\phi(x^{(i)})+b)\leq0~~~~~i=1,2,\dots ,m \end{align}$$

还有最后需要求解的对偶问题：

$$\begin{align}\max_\alpha~~&\sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m} \alpha_i\alpha_jy^{(i)}y^{(j)}\phi(x^{(i)})^T\phi(x^{(j)})\\ \text{s.t.}~~& \begin{cases} \sum_{i=1}^{m}\alpha_iy^{(i)}=0,\\ \alpha\geq0,\qquad i=1,2,\dots ,m \end{cases} \end{align}$$

上述问题中的 $\phi(x^{(i)})^T\phi(x^{(j)})$ 很难计算，我们可以设想一个核函数 $\kappa(x^{(i)},x^{(j)})$ (kernel function)，令

$$\kappa(x^{(i)},x^{(j)})=\phi(x^{(i)})^T\phi(x^{(j)})$$

那么上面的对偶问题可以重写为：

$$\begin{align}\max_\alpha~~&\sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m} \alpha_i\alpha_jy^{(i)}y^{(j)}\kappa(x^{(i)},x^{(j)})\\ \text{s.t.}~~& \begin{cases} \sum_{i=1}^{m}\alpha_iy^{(i)}=0,\\ \alpha\geq0,~~~~~~~~~~~~~i=1,2,\dots ,m \end{cases} \end{align}$$

最后可以求得：

$$f(x)=\omega^Tx+b=\sum_{i=1}^m\alpha_iy^{(i)}\kappa(x^{(i)},x)+b$$

核函数有很多种，比如常用的高斯核函数(Gaussian kernel)：

$$\kappa(x^{(i)},x^{(j)})=\exp(-\frac{\Vert x^{(i)}-x^{(j)} \Vert ^2}{2\sigma^2})$$