【李航统计学习笔记】第七章：支持向量机

7.1支持向量机

线性可分支持向量机与间隔最大化

如何去找到一个最优的超平面？

找到一个超平面，这个超平面可以使得与它最近的样本点的距离必须大于其他所有超平面划分时与最近的样本点的距离。在SVM中，这叫间隔最大化。

基本思路：如果我们的样本点，是它在高维空间到低维空间的一个投影，总会从某一个维度开始，它变得线性可分了。

我们发现，高维中的超平面，映射到低维空间中时，可能会变成曲线或其他形式的划分形式。这也就是为什么，在svm中我们同样使用超平面来划分，但SVM可以划分非线形的数据集。它本质上仍然是线形超平面，不过是高维中的线形超平面。

那么升维一定线性可分吗？会不会升到无穷维了仍然线性不可分？不会！首先因为，我们的数据集一定是基于真实的某种分布，分为A类的样本和B类的样本一定在本质上有区别。只要有区别，就一定可以区分开来，一定在某个高维度上线性可分。

支持向量机

函数间隔：
$$\widetilde{{\gamma }_i}=y_i\left(w{x}_i+b\right)$$
几何间隔：
$${\gamma }_i=y_i\left(\frac{w}{\Vert w\Vert }{x}_i+\frac{b}{\Vert w\Vert }\right)=\frac{\widetilde{{\gamma }_i}}{\Vert w\Vert }$$
最大间隔分离超平面：
$$
\max _{w, b} \gamma\

\text { s.t. } \quad y_{i}\left(\frac{w}{|w|} \cdot x_{i}+\frac{b}{|w|}\right) \geqslant \gamma, \quad i=1,2, \cdots, N
$$

$$\begin{gathered} \underset{w,b}{\max }\frac{\hat{\gamma }}{\Vert w\Vert } \\ \text{s.t.}{y}_i\left(w\cdot x_i+b\right)⩾\hat{\gamma },i=1,2,\cdots ,N \end{gathered}$$

由于函数间隔可以任意缩放，我们令其为1：
$$\begin{gathered} \underset{w,b}{\max }\frac{1}{\Vert w\Vert } \\ \text{ s.t. }{y}_i\left(w\cdot x_i+b\right)⩾1,i=1,2,\cdots ,N \end{gathered}$$
因为最大化$\frac{1}{\Vert w\Vert }$等价于最小化$\frac{1}{2}\Vert w{\Vert }^2$,式子可以改写为
$$\begin{gathered} \underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }^2 \\ \text{ s.t. }{y}_i\left(w\cdot x_i+b\right)-1⩾0,i=1,2,\cdots ,N \end{gathered}$$
导入拉格朗日
$$\begin{gathered} \underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }^2 \\ \text{ s.t. }{y}_i\left(w\cdot x_i+b\right)-1⩾0,i=1,2,\cdots ,N \\ L(w,b,\alpha )=\frac{1}{2}\Vert w{\Vert }^2-\sum _{i=1}^N{\alpha }_i{y}_i\left(w\cdot x_i+b\right)+\sum _{i=1}^N{\alpha }_i \end{gathered}$$
目标从：
$$\underset{w,b}{\min }\underset{\alpha }{\max }L(w,b,\alpha )$$
转化为
$$\underset{\alpha }{\max }\underset{w,b}{\min }L(w,b,\alpha )$$

先求${\min }_{w,b}L(w,b,a)$

将拉格朗日函数$L(w,b,\alpha )$分别对$w,b$求偏导数并令其等于0.
∇ w L ( w , b , α ) = w − ∑ i = 1 N α i y i x i = 0 ∇ b L ( w , b , α ) = ∑ i = 1 N α i y i = 0

​∇w​L(w,b,α)=w−i=1∑N​αi​yi​xi​=0∇b​L(w,b,α)=i=1∑N​αi​yi​=0​
得
w = ∑ i = 1 N α i y i x i ∑ i = 1 N α i y i = 0

w=∑i=1Nαiyixi∑i=1Nαiyi=0" role="presentation" style="position: relative;">w=∑i=1Nαiyixi∑i=1Nαiyi=0$$\begin{array}{c}w=\sum _{i=1}^N{\alpha }_i{y}_i{x}_i\\ \sum _{i=1}^N{\alpha }_i{y}_i=0\end{array}$$

w=i=1∑N​αi​yi​xi​i=1∑N​αi​yi​=0​
将$w$代入拉格朗日函数并利用${\sum }_{i=1}^N{\alpha }_i{y}_i=0$, 得到
L ( w , b , α ) = 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) − ∑ i = 1 N α i y i ( ( ∑ j = 1 N α j y j x j ) ⋅ x i + b ) + ∑ i = 1 N α i = − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) + ∑ i = 1 N α i

L(w,b,α)=12∑i=1N∑j=1Nαiαjyiyj(xi⋅xj)−∑i=1Nαiyi((∑j=1Nαjyjxj)⋅xi+b)+∑i=1Nαi=−12∑i=1N∑j=1Nαiαjyiyj(xi⋅xj)+∑i=1Nαi" role="presentation" style="position: relative;">L(w,b,α)=12∑i=1N∑j=1Nαiαjyiyj(xi⋅xj)−∑i=1Nαiyi((∑j=1Nαjyjxj)⋅xi+b)+∑i=1Nαi=−12∑i=1N∑j=1Nαiαjyiyj(xi⋅xj)+∑i=1Nαi$$\begin{array}{rl}L(w,b,\alpha )& =\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j\left(x_i\cdot x_j\right)-\sum _{i=1}^N{\alpha }_i{y}_i\left(\left(\sum _{j=1}^N{\alpha }_j{y}_j{x}_j\right)\cdot x_i+b\right)+\sum _{i=1}^N{\alpha }_i\\ & =-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j\left(x_i\cdot x_j\right)+\sum _{i=1}^N{\alpha }_i\end{array}$$

L(w,b,α)​=21​i=1∑N​j=1∑N​αi​αj​yi​yj​(xi​⋅xj​)−i=1∑N​αi​yi​((j=1∑N​αj​yj​xj​)⋅xi​+b)+i=1∑N​αi​=−21​i=1∑N​j=1∑N​αi​αj​yi​yj​(xi​⋅xj​)+i=1∑N​αi​​
即
$$\underset{w,b}{\min }L(w,b,\alpha )=-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j\left(x_i\cdot x_j\right)+\sum _{i=1}^N{\alpha }_i$$

再求${\max }_{\alpha }L(w,b,\alpha )$

求${\min }_{w,b}L(w,b,\alpha )$对$\alpha$的极大，即是对偶问题
$$\begin{gathered} \underset{\alpha }{\max }-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j\left(x_i\cdot x_j\right)+\sum _{i=1}^N{\alpha }_i \\ \text{s.t.}\sum _{i=1}^N{\alpha }_i{y}_i=0 \\ {\alpha }_i⩾0,i=1,2,\cdots ,N \end{gathered}$$
然后将max转化为min
$$\begin{gathered} \underset{\alpha }{\min }\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j\left(x_i\cdot x_j\right)-\sum _{i=1}^N{\alpha }_i \\ \text{s.t.}\sum _{i=1}^N{\alpha }_i{y}_i=0 \\ {\alpha }_i⩾0,i=1,2,\cdots ,N \end{gathered}$$

接下来求解$\alpha$

软间隔最大化(maximum soft interval)

引入松弛变量
$$y_i\left(w\cdot x_i+b\right)⩾1-{\xi }_i$$
约束和目标也要修改
$$\begin{gathered} \underset{w,b,\xi }{\min }\frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^N{\xi }_i \\ \text{ s.t. }{y}_i\left(w\cdot x_i+b\right)⩾1-{\xi }_i,i=1,2,\cdots ,N \\ {\xi }_i⩾0,i=1,2,\cdots ,N \end{gathered}$$
最终结果为
$$\begin{gathered} \underset{\alpha }{\min }\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j\left(x_i\cdot x_j\right)-\sum _{i=1}^N{\alpha }_i \\ \text{ s.t. }\sum _{i=1}^N{\alpha }_i{y}_i=0 \\ 0⩽{\alpha }_i⩽C,i=1,2,\cdots ,N \end{gathered}$$
和上一个section不使用软间隔的情况一样一样，我们这里也面临求解$\alpha$的问题。

核函数

目前的问题：式子中间有 $x_i$ 和 $x_j$ 的点积，这个让人难受。例如在手写数字数据集Mnist中，训练集有6万个样本，6万乘6万勉强能接受。但每个样本时784维的，6万个样本两两做点积，是非常慢的。如果x是更高维度的呢?

1. 由于公式的需要，我们需要计算 $x_i$ 和 $x_j$ 的点积。
2. 此外，我们需要将样本映射到高维去，加入映射函数为 $\varphi (x)$ ， 那么 $\varphi \left(x_i\right)$ 和 $\varphi \left(x_j\right)$ 的维度数目进一步扩大，它们的点积会让运算变得及其复杂。 (因为维度太高了)
3. 我们希望存在一个函数 $K\left(x_i,x_j\right)=\varphi \left(x_i\right)\cdot \varphi \left(x_j\right)$ ，但函数 $K$ 的计算方式更简单。也就是说，我将样本通过函数升维得到 $\varphi \left(x_i\right)$ 和 $\varphi \left(x_j\right)$ ，接下来要计算它们的点积，能不能有个很简单的计算公式，计算出来的结果和 $\varphi \left(x_i\right)$. $\varphi \left(x_j\right)$ 一样? 那样我就不用再去算 $\varphi \left(x_i\right)\cdot \varphi \left(x_j\right)$ 的结果了，直接用简单方式计算不是更好吗?

这个简便方式，就是核函数

在SVM中，我们通常使用高斯核
$$K(x,z)=\exp \left(-\frac{\Vert x-z{\Vert }^2}{2{\sigma }^2}\right)$$
在计算$x$和$z$的点积时，直接用这个公式替代就行了。

所以我们有
$$\begin{gathered} \underset{\alpha }{\min }\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_{j}K\left(x_i,x_j\right)-\sum _{i=1}^N{\alpha }_i \\ \text{s.t.}\sum _{i=1}^N{\alpha }_i{y}_i=0 \\ 0⩽{\alpha }_i⩽C,i=1,2,\cdots ,N \end{gathered}$$

序列最小最优化算法

现在我们只剩下$\alpha$需要求解。而且我们求解出来的$\alpha$一定要让整个结果满足KKT条件。如果不满足，那一定不是最优解。所以我们可以每次不断调整$\alpha$的值，直到所有$\alpha$都满足KKT条件，这时候我们一定得到了最优解。如何调整呢？可以用序列最小最优化算法，也就是SMO。

假设整个式子有N个$\alpha =({\alpha }_1,{\alpha }_2,{\alpha }_3,\cdots ,{\alpha }_N)$,先固定了其他${\alpha }_i$，找${\alpha }_1$。先让${\alpha }_1$满足KKT条件。但是如果固定除${\alpha }_1$以外的所有${\alpha }_i$,等于也固定了${\alpha }_1$。
$${\alpha }_1=-y_1\sum _{i=2}^N{\alpha }_i{y}_i$$
所以我们每次选择优化两个${\alpha }_i$
$${\alpha }_1{y}_1+{\alpha }_2{y}_2=-\sum _{i=3}^N{y}_i{\alpha }_i$$
进一步，因为原式中目前只有${\alpha }_1$和${\alpha }_2$两个变量，我们将其他作为常数去除。
$$\begin{gathered} \underset{\alpha }{\min }\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_{j}K\left(x_i,x_j\right)-\sum _{i=1}^N{\alpha }_i \\ \text{ s.t. }\sum _{i=1}^N{\alpha }_i{y}_i=0 \\ 0⩽{\alpha }_i⩽C,i=1,2,\cdots ,N \end{gathered}$$

整理一下
min ⁡ α 1 , α 2 W ( α 1 , α 2 ) = 1 2 K 11 α 1 2 + 1 2 K 22 α 2 2 + y 1 y 2 K 12 α 1 α 2 − ( α 1 + α 2 ) + y 1 α 1 ∑ i = 3 N y i α i K i 1 + y 2 α 2 ∑ i = 3 N y i α i K i 2  s.t.  α 1 y 1 + α 2 y 2 = − ∑ i = 3 N y i α i = ζ 0 ⩽ α i ⩽ C , i = 1 , 2

α1​,α2​min​W(α1​,α2​)=​21​K11​α12​+21​K22​α22​+y1​y2​K12​α1​α2​−(α1​+α2​)+y1​α1​i=3∑N​yi​αi​Ki1​+y2​α2​i=3∑N​yi​αi​Ki2​ s.t. α1​y1​+α2​y2​=−i=3∑N​yi​αi​=ζ0⩽αi​⩽C,i=1,2​
目前可知，${\alpha }_i$一定在0到C之间。我们已知：
$$\sum {\alpha }_i{y}_i=0$$
有
$${\alpha }_1{y}_1+{\alpha }_1{y}_2=-\sum _{i=3}^m{\alpha }_i{y}_i=\zeta$$
(to be continued)

总结

1. SVM让人头秀。
2. SVM首先从最大间隔出发，设计了可构造最优超平面的线形模型。
3. 考虑到存在噪音或有部分点让人很为难，添加了软间隔。 变成了具有软间隔功能的线形模型。
4. 通过对数据的升维，使得模型变成了非线形。可以用于非线形数据集。
5. 升维后无穷维的点积运算难以实现，引入了核函数简化运算。

7.2 间隔分离最大化的存在唯一性

证明存在性

由于训练数据集线性可分，所以算法一定存在可行解。又由于目标函数又下界， 所以最优化问题必有解。吕于训练数据中既有正类点又有负类点，所以$(w,b)=(0,b)$ 不是最优化的可行解，因此最优解必定满足w不等于 0 ，由此可知分离超平面的存在性。

证明唯一性

(To be continued)