SVM

线性支持向量机

有一个线性可分的数据集 $D=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$ 其中 $x_i\in {\mathbb{R}}^n$ 为特征向量，$y_i\in \{-1,+1\}$ 为类别标签。

目标是找到一个超平面 $w^{T}x+b=0$ 使得

• 当 $y_i=+1$ 时，$w^T{x}_i+b>0$
• 当 $y_i=-1$ 时，$w^T{x}_i+b<0$ 并且希望这个超平面距离样本点的间隔最大。

定义函数间隔：

$$\hat{\gamma }=\underset{i=1,\dots ,N}{\min }{\hat{\gamma }}_i$$

${\hat{\gamma }}_i=y_i(w^T{x}_i+b)$ 注意到当我们将 $w$ 和 $b$ 等比例放大时，超平面不变，但函数间隔会变大，因此需要先做一个归一化，定义几何间隔： $\gamma ={\min }_{i=1,..,N}{\gamma }_i$ ${\gamma }_i=\frac{y_i(w^T{x}_i+b)}{\Vert w\Vert }$ 则目标是 ${\max }_{w,b}\frac{\hat{\gamma }}{\Vert w\Vert }$

$\text{s.t.}{y}_i(w^T{x}_i+b)\ge \hat{\gamma },i=1,2,...,N$ 由于函数间隔可以任意缩放，不妨设 $\hat{\gamma }=1$ 因此目标是

$$\underset{w,b}{\max }\frac{1}{\Vert w\Vert }$$

又等价于

$$\underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }^2$$ $$\text{s.t. }{y}_i(w^T{x}_i+b)\ge 1$$

定义拉格朗日函数

$$L(w,b,\alpha )=\frac{1}{2}\Vert w{\Vert }^2+\sum _{i=1}^n{\alpha }_i(1-y_i(w\cdot x_i+b))$$

其中 ${\alpha }_i\ge 0,\alpha =({\alpha }_1,\dots ,{\alpha }_n{)}^T$

当满足约束条件时，

$$\underset{\alpha }{\max }L(w,b,\alpha )=\frac{1}{2}\Vert w{\Vert }^2$$

因此原问题等价于

$$\underset{w,b}{\min }\underset{\alpha }{\max }L(w,b,\alpha )$$

该问题满足强对偶性，可以交换 min 和 max 的顺序，求解其对偶问题：

$$\underset{\alpha }{\max }\underset{w,b}{\min }L(w,b,\alpha )$$

$\frac{\partial L}{\partial w}=w-{\sum }_{i=1}^N{\alpha }_i{y}_i{x}_i=0⟹w={\sum }_{i=1}^N{\alpha }_i{y}_i{x}_i$ $\frac{\partial L}{\partial b}=-{\sum }_{i=1}^N{\alpha }_i{y}_i=0⟹{\sum }_{i=1}^N{\alpha }_i{y}_i=0$ 代入得

$$\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(x_i^T{x}_j)+\sum _{i=1}^n{\alpha }_i-\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i^T{x}_j)-\sum _{i=1}^n{\alpha }_i{y}_{i}b\\ & =\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(x_i^T{x}_j)\end{array}$$

则问题变成 ${\min }_{\alpha }\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i^T{x}_j)-{\sum }_{i=1}^N{\alpha }_i$

$\text{s.t.}{\sum }_{i=1}^N{\alpha }_i{y}_i=0,{\alpha }_i\ge 0$ 这是一个标准的凸优化问题，可以直接求出最优解 ${\alpha }^{\ast }$

直观理解

从直观上理解，$\alpha$ 决定了一个点的重要性。 优化目标式分为两部分：

• 惩罚项：$\frac{1}{2}\sum \sum {\alpha }_i{\alpha }_j{y}_i{y}_j(x_i^T{x}_j)$，如果两个点内积很大，说明他们离的很近，如果是同类，则只需要一个当支持向量就行，${\alpha }_i{\alpha }_j$ 变小；如果是异类，说明它们是分界点非常重要，因此 ${\alpha }_i{\alpha }_j$ 变大
• 激励项：如果只有第一项，那么直接取所有 $\alpha$ 为 0 即可，因此需要加入激励，这一项希望找到的 $\alpha$ 越大越好
• 最终结果就是绝大多数的点的 $\alpha$ 会被压到 0，只剩少部分支持向量的 $\alpha$ 大于 0

约束条件可以理解为类似受力平衡，正负类的总“权重”应该相等

根据 KKT 条件，最优解必须满足约束 ${\alpha }_i^{\ast }[y_i(w^{\ast T}{x}_i+b^{\ast })-1]=0$ 与 ${\alpha }_i>0$ 对应的样本 $x_i$ 就是支持向量

求出 ${\alpha }^{\ast }$ 后可计算 $w^{\ast }$ 和 $b^{\ast }$ $w^{\ast }={\sum }_{i=1}^N{\alpha }_i^{\ast }{y}_i{x}_i$ 选择一个支持向量 $x_j$，有 $y_j(w^{\ast T}{x}_j+b^{\ast })=1$，而 $y_j^2=1$，因此 $b^{\ast }=y_j-w^{\ast T}{x}_j=y_j-{\sum }_{i=1}^N{\alpha }_i^{\ast }{y}_i(x_i^T{x}_j)$

• 直观上讲，$w^{\ast }$ 是超平面的法向量，设正负类加权得到的向量分别是 $v_{+}$ 和 $v_{-}$，则 $w^{\ast }=v_{+}-v_{-}$，即正类中心指向负类中心
• 所有支持向量都严格地位于间隔边界上

最后，决策函数为 $f(x)=sign(w^{\ast }\cdot x+b^{\ast })$

软间隔

实际情况中，样本可能并不是完全线性可分，某些点不满足函数间隔大于等于 1 的条件。因此引入松弛变量 ${\xi }_i$ $y_i(w^T{x}_i+b)\ge 1-{\xi }_i$ 为了使 ${\xi }_i$ 尽可能小，优化目标增加惩罚项： ${\min }_{w,b,\xi }\frac{1}{2}\Vert w{\Vert }^2+C{\sum }_{i=1}^N{\xi }_i$ 其中 $C>0$ 是惩罚参数，C 越大对误分类的惩罚越高

通过类似的对偶变换，有对偶问题为 ${\min }_{\alpha }\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i^T{x}_j)-{\sum }_{i=1}^N{\alpha }_i$ $\text{s.t.}{\sum }_{i=1}^N{\alpha }_i{y}_i=0,0\le {\alpha }_i\le C$ 求得最优解 ${\alpha }^{\ast }$，然后同样方法计算 $w^{\ast }$ 和 $b^{\ast }$，计算 $b^{\ast }$ 时要找 $0<{\alpha }^{\ast }<C$ 的点。

$C$ 趋于无穷时，条件 $0\le {\alpha }_i\le C$ 变为 ${\alpha }_i\ge 0$，和无软间隔时相同。 此处可以将 $0\le {\alpha }_i\le C$ 理解为限制噪点的重要性，如果没有这个限制，一个在异类中的离群点的 $\alpha$ 趋于无穷大时优化目标会不断减小，导致无法优化。

• 若 $0<{\alpha }_i<C$，则 ${\xi }_i=0$，$x_i$ 在间隔边界上
• 若 ${\alpha }_i^{\ast }=C,0<{\xi }_i<1$，则分类正确，$x_i$ 在间隔边界和分离超平面之间
• 若 ${\alpha }_i^{\ast }=C,{\xi }_i=1$，则 $x_i$ 在超平面上
• 若 ${\alpha }_i^{\ast }=C,{\xi }_i>1$，则 $x_i$ 被误分类，${\xi }_i=2$ 时恰好位于对立类的间隔边界上，${\xi }_i>2$ 时跨越了对立类的间隔边界

线性不可分

解决方法：使用非线性映射，在高维空间构造线性分类面

定义一个非线性映射 $\varphi$ 将 $x$ 映射到高维空间中。但是这会导致维度爆炸，当映射到更高次幂时，维度数成指数级上升。

然而，注意到最终的对偶问题中需要的是高维向量的内积，因此可以直接定义一个在低维空间中可以计算的核函数使它的输出正好等于高维空间中的内积。

问题转化为 ${\min }_{\alpha }\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(x_i,x_j)-{\sum }_{i=1}^N{\alpha }_i$ $\text{s.t.}{\sum }_{i=1}^N{\alpha }_i{y}_i=0,0\le {\alpha }_i\le C$ 求得最优解 ${\alpha }^{\ast }$，计算 $w^{\ast }$ 和 $b^{\ast }$ $w^{\ast }={\sum }_{i=1}^N{\alpha }_i^{\ast }{y}_i\varphi (x_i)$

$$b^{\ast }=y_j-\sum _{i=1}^n{\alpha }_i^{\ast }{y}_{i}K(x_i,x_j)$$

此处虽然 $w^{\ast }$ 中包含 $\varphi$，但是在实际应用决策函数时会被抵消成 $K$

$$sign(w^{\ast }\varphi (x)+b^{\ast })=sign\left(\sum _{i=1}^n{\alpha }_i^{\ast }{y}_{i}K(x_i,x)+b^{\ast }\right)$$

• 多项式核函数：$K(x,z)=(xz+1{)}^p$
• 高斯核函数：$K(x,z)=\exp (-\Vert x-z{\Vert }^2/2{\sigma }^2)$，由泰勒展开可以证明，等价于两个无限维向量的内积
• 树形核函数：

$$K(x,y)=\{\begin{array}{l}\begin{array}{rlr}& 0,& r_1\ne r_2\\ & 1+K(x[r_1],y[r_2]),& otherwise\end{array}\end{array}$$

多分类问题

有几种方法：

• 一对多：某类为正例，其余为负例
• 一对一：任意两类构造一个 SVM，分类时投票决定类别
• 层次法：所有类组合成树状结构