统计学习方法

SVM

支持向量机大家耳熟能详，应该没人反对向量机吧

线性可分支持向量机（硬）

本节讨论线性可分数据集的情形

感知机

数据集$\set{(x_i,y_i)},y_i\in \set{-1,1}$是线性可分的，指存在一个平面：
$$
w^\ast \cdot x+b^\ast =0
$$
能将标签是$-1$和$1$的数据点划分开

当$x$从该平面的一侧变到另一侧时，$w^\ast \cdot x+b^\ast$会从正的变到负的（或相反），它的符号，就表征了数据点在哪一侧，也就是属于哪类

很自然的，这种决策用数学表达就是：
$$
f(x)=\text{sign}(w^\ast \cdot x+b^\ast)
$$

这就是感知机（perceptron）。不过，可能存在很多个平面都能够将两类点分开，因此感知机不唯一

两种间隔

加上限制—“最大化间隔”，这能让平面唯一确定下来，在直观上让该平面离两类数据点都“比较远”。最大化间隔的感知机也就是线性可分支持向量机

在此之前，需先弄清楚间隔是什么

几何间隔 其实就是点到平面的距离。平面$w^\ast \cdot x+b^\ast =0$的单位法向量为$\frac{w^\ast}{\Vert w^\ast\Vert}$，设某点$x’$恰好在该平面上，那么$x_i$到它的向量就是$x’-x_i$，$x_i$到平面的距离就是该向量与平面法向量的内积，再取绝对值：

$$
\gamma_i:=\left\vert \frac{w^\ast}{\Vert w^\ast\Vert}\cdot (x’-x_i)\right\vert=\left\vert \frac{-b^\ast}{\Vert w^\ast\Vert}-\frac{w^\ast}{\Vert w^\ast\Vert}\cdot x_i\right\vert=\frac{y_i}{\Vert w^\ast \Vert}(w^\ast\cdot x_i+b^\ast)
$$

最后一步把绝对值摘掉，用了$y_i$是$\pm 1$能够自动调整正负这一事实

而对于某个数据集，它到该平面的几何间隔就定义为其中所有点到平面几何间隔的最小值$\gamma :=\min\limits_i \gamma_i$

函数间隔 和几何间隔差不多，只不过把$\Vert w^\ast\Vert$这个调整比例的系数都去掉了，这样更简单：

$$
\hat{\gamma}_i:=y_i(w^\ast\cdot x_i+b^\ast)
$$

同样，数据集到该平面的函数间隔$\hat{\gamma} :=\min\limits_i \hat{\gamma}_i$

问题的形式化描述

目标：让感知机用的平面恰是“数据集到该平面几何间隔最大”的那个平面

$$
\begin{align*}
&\max_{w,b} \gamma
\newline
&\text{s.t. }\frac{y_i}{\Vert w \Vert}(w\cdot x_i+b) \geq \gamma \quad \forall i
\end{align*}
$$

由于集合间隔和函数间隔就差一个$\Vert w\Vert$，所以该问题也就是：

$$
\begin{align*}
&\max_{w,b} \frac{\hat{\gamma}}{\Vert w\Vert}
\newline
&\text{s.t. }y_i(w\cdot x_i+b) \geq \hat{\gamma}
\end{align*}
$$

可以看出，若$\hat{\gamma}$和$\Vert w\Vert$同时变大10倍，问题并不会变，决定问题的是它们的比值！因此不妨直接令$\hat{\gamma}=1$，原问题：
$$
\begin{align*}
&\max_{w,b} \frac{1}{\Vert w\Vert}
\newline
&\text{s.t. }y_i(w\cdot x_i+b) \geq 1 \quad \forall i
\end{align*}
$$

再等效为：

$$
\begin{align*}
&\min_{w,b} \frac{1}{2}\Vert w \Vert^2
\newline
&\text{s.t. }y_i(w\cdot x_i+b)-1 \geq 0 \quad \forall i
\end{align*}
$$

这样清爽许多！这里目标函数和取这个形式，是因为它求导后比较好看

对偶变形与求解

上述就是在约束条件$y_i(w\cdot x_i+b)-1 \geq 0$下的优化问题，使用Lagrange乘数法，乘子$\alpha=(\alpha_1,\alpha_2\dots)$，构建：

$$
L(w,b,\alpha)=\frac{1}{2}\Vert w \Vert^2 -\sum_{i=1}^N \alpha_i (y_i(w\cdot x_i+b)-1)
$$

原始问题：$\min\limits_{w,b}\max\limits_{\alpha} L(w,b,\alpha)$
对偶问题：$\max\limits_{\alpha}\min\limits_{w,b} L(w,b,\alpha)$

在此处，原始问题的求解可转化为对偶问题的求解（原因参见对偶章节，此处为强对偶）

现在开始求对偶问题吧！先求内部$\min\limits_{w,b} L(w,b,\alpha)$，即对$w,b$偏导并令之为零：

$$
\begin{align*}
\nabla_w L&=w-\sum_{i=1}^N \alpha_i y_i x_i = 0
\newline
\nabla_b L&=-\sum_{i=1}^N \alpha_i y_i = 0
\end{align*}
$$

解出：$w= \sum\limits_{i=1}^N \alpha_i y_i x_i$，还得到等式$\sum\limits_{i=1}^N \alpha_i y_i = 0$，把这两者代回Lagrange函数：

$$
\begin{align*}
L&=\frac{1}{2} \sum\limits_{j=1}^N \sum\limits_{i=1}^N \alpha_j\alpha_i y_j y_i(x_j \cdot x_i)-\sum_{i=1}^N \alpha_i (y_i( \sum\limits_{j=1}^N \alpha_j y_j x_j \cdot x_i+b)-1)
\newline
&=-\frac{1}{2} \sum\limits_{j=1}^N \sum\limits_{i=1}^N \alpha_j\alpha_i y_j y_i(x_j \cdot x_i)+\sum_{i=1}^N \alpha_i
\end{align*}
$$

离最终目标，只剩求解外部的极大问题，把极大问题的目标函数取个负号，又写成极小问题如下：
$$
\begin{align*}
&\min_\alpha \frac{1}{2} \sum\limits_{j=1}^N \sum\limits_{i=1}^N \alpha_j\alpha_i y_j y_i(x_j \cdot x_i)-\sum_{i=1}^N \alpha_i
\newline
&\text{s.t. }\sum_{i=1}^N \alpha_i y_i = 0 \quad \alpha_i\geq 0 \quad \forall i
\end{align*}
$$

这就是历经重重变形得来的，求解“几何间隔最大化”的等价问题！

设法解出这个问题后，利用$w= \sum\limits_{i=1}^N \alpha_i y_i x_i$公式得到$w^\ast$，这样平面的法方向已经定下来了，还剩$b$未定，$b$这个量能够让平面上下平移，一个重要观察是，这个上下平移的量的多少最终是被数据点中距离分离平面最近的那几个决定的，这些点就叫支持向量！

这些点上，约束$y_i(w\cdot x_i+b)-1 \geq 0$的重担压在了它们的身上，变成$y_i(w\cdot x_i+b)-1 = 0$，是“支撑”点，因此得名。其余点其实都是打酱油的，去掉几个其余的点，平面不变，因为顶梁柱还在

由此，可以用支持向量倒推出$b$的值：先找$\alpha_j\neq 0$，那么第$j$个不等式约束就是起作用的，是等式约束，那么：

$$
y_j(w^\ast \cdot x_j +b^\ast )-1=0
$$

解出$b^\ast$即可

线性支持向量机（软）

再讨论数据集非线性可分的情况，不存在一个平面能够完全分离两类，这时候“间隔”的概念又要拓展：

软间隔

因为线性不可分即是说$y_i(w\cdot x_i+b) \geq 1$不可能所有$i$都满足，那宽容一点，改成$y_i(w\cdot x_i+b) \geq 1-\xi$，但是也要为体现由于宽容带来的惩罚

由此，原问题写为：

$$
\begin{align*}
&\min_{w,b,\xi} \frac{1}{2}\Vert w \Vert^2+C\sum_{i=1}^N \xi_i
\newline
&\text{s.t. }y_i(w\cdot x_i+b)-1+\xi_i \geq 0 \quad \xi_i\geq 0\quad \forall i
\end{align*}
$$

这称作软间隔最大化问题，$C\gt 0$是惩罚系数

对偶问题与求解

同样可以得到

$$
\begin{align*}
&\min_\alpha \frac{1}{2} \sum\limits_{j=1}^N \sum\limits_{i=1}^N \alpha_j\alpha_i y_j y_i(x_j \cdot x_i)-\sum_{i=1}^N \alpha_i
\newline
&\text{s.t. }\sum_{i=1}^N \alpha_i y_i = 0 \quad 0 \leq \alpha_i \leq C \quad \forall i
\end{align*}
$$

解出$\alpha$后，仍然用$w= \sum\limits_{i=1}^N \alpha_i y_i x_i$公式得到$w^\ast$，不过$b^\ast$就可能不唯一了

此时的支持向量，就是对应的$\alpha_j>0$的那些数据点$x_j$

非线性支持向量机

之前，我们一直用的是欧式空间中的一个平面去划分数据点，倘若数据点的边界是弯弯的，一个平面显然不能分的很好

你可能会想，是不是不该在欧式空间中求解？如果把数据点映射到一个新的赋范线性空间中去，会不会分布的就非常好了，能用新空间中的平面来划分？

假设已经映射到新的空间中了，在新的空间中用先前线性支持向量机的算法，算到对偶问题为止，应该会得到：

$$
\begin{align*}
&\min_\alpha \frac{1}{2} \sum\limits_{j=1}^N \sum\limits_{i=1}^N \alpha_j\alpha_i y_j y_iK(x_j,x_i)-\sum_{i=1}^N \alpha_i
\newline
&\text{s.t. }\sum_{i=1}^N \alpha_i y_i = 0 \quad 0 \leq \alpha_i \leq C \quad \forall i
\end{align*}
$$

其中$K(x_j,x_i)$是$x_i\mapsto x_i’,x_j\mapsto x_j’$后，新空间里的$x_j’$与$x_i’$的内积。$K$就称之为核函数。所以，对于求解来说，原空间到新空间的映射的表达式不重要，核函数才重要

核函数可以自己选，比如选$K(x_i,x_j)=(x_i\cdot x_j +1)^p$，总之，选定以后，就是已知的值了，因为数据点都是有的，可以算出来，这样问题仍然和原本的线性支持向量机无异