这是我西瓜书的学习笔记，不定期更新！

第六章支持向量机

6.1 支持向量机的基本型

Tips 1：点到超平面的距离公式

给定超平面 $W^{\top}x+b=0$ 后，计算某一点 $A=x_{i}$ 到该平面的距离推导：

设距离为$r$ , 则可以通过下面的等式解出$r$ :

$W^\top(x_i-r*\frac{W}{\|W\|})+b=0 \tag{6.1}\label{pluginpoint}$

这是因为$A$在超平面上的投影点$B$可以表示为：

$x_i - r*\frac{W}{\|W\|} \tag{6.2}\label{projection}$

这里的几何意义很明显。不再赘述。

所以整理方程$\eqref{pluginpoint}$可以得到：

$r=\frac{|W^\top x_i+b|}{\|W\|} \tag{6.3}\label{distance}$

Tips 2：间隔的概念

假设所有点都已经能被超平面$l:W^\top x + b = 0$分类正确，那么对所有点$x_i$都有对应的$\epsilon_i>0$，使得下式成立：

$\left\{ \begin{aligned} W^\top x_i + b \ge +\epsilon_i, y_i = +1\\ W^\top x_i + b \le -\epsilon_i, y_i = -1 \end{aligned} \right.$

通过在上述不等式中，首先对$W$和$b$施加适当的旋转变换，而后同时除以 $\min\limits_{i}\epsilon_i$ 就总能使得下式成立：

$\left\{ \begin{aligned} W^\top x_i + b \ge +1, y_i=+1\\ W^\top x_i + b \le -1, y_i=-1 \end{aligned} \right. \tag{6.4}\label{normlize}$

下面着重考察那些使得上述不等式取得等号的数据点，假设$x_{i_{n}}^+$在超平面$l^+:W^\top x + b = +1$上；$x_{i_{m}}^-$在超平面$l^-:W^\top x + b = -1$上。那么显然这两个点是所有数据点中里分离超平面$W^\top x + b = 0$最近的两个点。那么我们就可以定义“间隔”这样一个概念：$l^+$与$l^-$之间的距离称为“间隔”（margin），这里我们记作$\gamma$。显然$l^+$与$l^-$之间的距离为$l^+$到$l$的距离加上$l$到$l^-$的距离（也就是$x_{i_{n}}^+$到$l$的距离加上$x_{i_{m}}^-$到$l$的距离）。

根据距离公式$\eqref{distance}$，$x_{i_{n}}^+$到$l$的距离为：

$r^+ = \frac{|W^\top x_{i_{n}}^++b|}{\|W\|}=\frac{|+1|}{\|W\|} \tag{6.5}\label{r+}$

上式第二个等号是因为$x_{i_{n}}^+$落在了$l^+$上，所以可以将$|W^\top x_{i_{n}}^++b|=1$代入上式。

同理我们有

$r^- = \frac{|W^\top x_{i_{m}}^-+b|}{\|W\|}=\frac{|-1|}{\|W\|} \tag{6.6}\label{r-}$

所以间隔$\gamma=\frac{2}{|W|}$。

Tips 3: 支持向量机基本型的导出

支持向量机建模的想法在于要最大化找到的那个超平面所对应的“间隔”。显然，这样找到的超平面在小样本下会有更加鲁棒的表现。那么原始的优化问题就会写成下面的形式：

$\begin{aligned} \max\limits_{W,b}&\ \ \frac{2}{\|W\|}\\ s.t.&\ \ y_{i}(W^\top x_i + b)\ge1, i=1,\cdots,m \end{aligned} \tag{6.7}\label{originaloptimization}$

考虑到上面的优化问题并不是凸函数，不能方便的求解，考虑将最大化$\frac{2}{|W|}$改为最小化$\frac{1}{2}|W|^2$。这两个优化问题在数学上等价，也就是同解。所以我们导出了支持向量机的基本型，也称之为原问题：

$\begin{aligned} \min\limits_{W,b}&\ \ \frac{1}{2}\|W\|^2\\ s.t.&\ \ y_{i}(W^\top x_i + b)\ge1, i=1,\cdots,m \end{aligned} \tag{6.8}\label{primal}$

其实在这里已经可以通过代码包来解这个优化问题了！只是解起来，效率会低一些。

6.2 支持向量机原问题的对偶问题

Tips 1: 为什么研究对偶问题和 KKT 条件

对于初次接触优化问题的同学而言，对偶问题一般显得莫名奇妙。最直接的问题是，我们为什么要研究对偶问题？进一步地，有的人可能还知道我们还要搞一个KKT条件，研究那个又干嘛？

这几个问题在支持向量机的背景下还是很好回答的，逻辑是这样的：在支持向量机的案例下，对偶问题的解还是原问题的解，并且对偶问题比原问题$\eqref{primal}$要好解决；为什么对偶问题的解会是原问题的解呢？因为对偶问题的解满足原问题的KKT条件；为什么对偶问题好解决呢？因为在研究对偶问题过程中可以通过原问题的KKT条件去除掉大多数的数据点，找到对最优解起作用的那几个数据点，并只利用它们进行计算，从而降低了问题的难度。这个逻辑大家先接收下，下面我一步一步的show出来。

首先来一大串定义，大家背住就好！

高数中学过带等式约束的优化问题，可以利用拉格朗日数乘法消去等式约束。同样的，不等式约束也可以利用类似的技巧消去。在消去的过程中，我们会得到拉格朗日函数。这个拉格朗日函数是我们构造对偶问题的基础！大家第一步起手式要练扎实，都是靠背的功夫！

Tips 2: 如何导出对偶问题

首先针对原问题$\eqref{primal}$，我们定义它的拉格朗日函数：

$L(\alpha_i,W,b)=\frac{1}{2}\|W\|^2+\sum_{i=1}^{m}\alpha_i\left[1-y_i(W^\top x_i+b)\right] \tag{6.9}\label{largerange}$

其中要求$\alpha_i\ge0$。

接着对固定的$\alpha_i$，通过对$W,b$求拉格朗日函数的最小值，我们定义对偶函数：

$g(\alpha_i)=\min_{W,b}\ L(\alpha_i,W,b)\tag{6.10}$

上述求最小值的过程要求我们对$W,b$同时求偏导：

$\begin{aligned} W-\sum_{i=1}^{m}\alpha_iy_ix_i&=0\\ \sum_{i=1}^{m}\alpha_iy_i&=0 \end{aligned}\tag{6.11}\label{min}$

解得$W=\sum_{i=1}^{m}\alpha_iy_ix_i$。将这些结果带回到$\eqref{largerange}$ 可以得到详细的对偶函数：

$\begin{aligned} g(\alpha_i)&=\sum_{i=1}^{m}\alpha_{i}-\frac{1}{2}\sum_{j=1}^{m}\alpha_jy_j\left(\sum_{i}^{m}\alpha_iy_{i}x_i^\top\right)x_j\\ &=\sum_{i=1}^{m}\alpha_{i}-\frac{1}{2}\sum_{j=1}^{m}\sum_{i=1}^{m}\alpha_jy_j\alpha_iy_{i}x_i^\top x_j \end{aligned}\tag{6.12}\label{dualfun}$

对偶问题就是最大化对偶函数：

$\begin{aligned} \max_{\alpha_i}&\ \ g(\alpha_i)=\sum_{i=1}^{m}\alpha_{i}-\frac{1}{2}\sum_{j=1}^{m}\sum_{i}^{m}\alpha_jy_j\alpha_iy_{i}x_i^\top x_j\\ s.t.&\ \ \sum_{i=1}^{m}\alpha_iy_i=0\\ &\ \ \alpha_i\geq0, i=1,2,\cdots,m \end{aligned}\tag{6.13}\label{dualpro}$

上面的对偶问题解出$\alpha_{i}$后再带回到$\eqref{min}$，就可以得到$W,b$。这里有一个问题，为什么这样得到的$W,b$就是原问题的最优解？下面的KKT条件会Show出这一点！

Tips 3: KKT条件的作用

下面来show一下KKT条件到底有什么用。

首先明确一点，上述对偶问题和KKT条件没有必然联系。我们不涉及对偶问题也可以讨论原问题的KKT条件。这一个Tips就是要show一下原问题的KKT条件是如何帮助回答上面两个问题的：为什么支持向量机中对偶问题与原问题同解；为什么对偶问题更容易解决。

其次，下面对原问题的KKT条件展开讨论：

在我们求解原问题$\eqref{primal}$时，会通过拉格朗日乘子法构造出拉格朗日函数$L(\alpha_i, W, b)$，并且解下面的优化问题（在凸函数的背景下—$\frac{1}{2}|W|^2$显然是凸函数—这个优化问题的解和原问题同解）：

$\begin{aligned} \min\limits_{\alpha_i,W,b}&\ \ L(\alpha_i,W,b)=\frac{1}{2}\|W\|^2+\sum_{i=1}^{m}\alpha_i\left[1-y_i(W^\top x_i+b)\right]\\ s.t.&\ \ \alpha_i\geq0,\ i=1,2,\cdots,m \end{aligned}\tag{6.14}\label{largerangianpro}$

这个问题和对偶问题长的很像，但确实不是对偶问题23333。此时根据KKT条件的定义，我们就可以对上面的优化问题$\eqref{largerangianpro}$列出它的KKT条件（最优解必须满足的条件），同时因为同解的缘故，原问题的解也必然满足：

$\left\{ \begin{aligned} \frac{\partial L(\alpha_i,W,b)}{\partial W}=W-\sum_{i=1}^{m}\alpha_iy_ix_i&=0\\ \frac{\partial L(\alpha_i,W,b)}{\partial b}=\sum_{i=1}^{m}\alpha_iy_i&=0\\ \alpha_i\left[1-y_i(W^\top x_i+b)\right]&=0\\ y_i(W^\top x_i+b)&\geq1\\ \alpha_i&\geq0\\ \end{aligned} \right.$

通过观察可以发现上述第一条和第二条等式就是对偶问题构造过程中要求满足的条件$\eqref{min}$；第3条与第4条为什么满足还没观察出来。

嘿嘿嘿，乘着电脑在安装软件，我来看看西瓜书。

第六章 支持向量机