图解机器学习/第八章 支持向量机分类

间隔最大化分类

从线性2类别分类问题说明

$$f_{\omega,\gamma}(x) = \omega^{\intercal}x+\gamma$$

上式中的$\omega$为把正负样本分割开的超平面的法线，$\gamma$为截距。只要能够对各个训练样本的间隔$m_i=f_{\omega,\gamma}(x_i)y_i$为正时的$\omega$和$\gamma$进行学习，就可以利用这个模型对所有的训练样本进行正确的分类。

当存在满足条件的$\omega$和$\gamma$，使得$(\omega^{\intercal}x+\gamma)y_i \ge1 \quad \forall i=1,\dots,n$，称这样的训练样本为线性可分的样本，一般选取能够最充裕地把正样本和负样本进行分离的超平面作为最优解。“最充裕”是指与正则化后地间隔$m_i=(\omega^{\intercal}x+\gamma)y_i/||\omega||$地最大值对应的。从几何学上讲，间隔为两端的两个超平面$\omega^{\intercal}x+\gamma=+1$和$\omega^{\intercal}x+\gamma = -1$地间距的一半，使这个间隔最大的超平面对应的分类器，成为硬间隔支持向量机分类器。

软间隔支持向量机分类器的基本思路是，允许在间隔的计算中出现少许的误差$\xi=(\xi_1,\dots,\xi_n)^{\intercal}$

支持向量机分类器的求解方法

支持向量机分类器的最优化问题，是目标函数为二次函数、约束条件为线性的典型的二次规划问题。

二次规划问题，始于矩阵$F、G$以及向量$f、g$相对应的由下式定义的最优化问题

$$\mathop{min}_{\theta}[\frac{1}{2}\theta^{\intercal}F\theta+f^{\intercal}\theta)] \quad 约束条件 \quad G\theta \le g$$

这里把向量不等式$G\theta \le g$分解，表示为各个元素的不等式

$$\tbinom{a}{b} \le \tbinom{c}{d} \iff f(n)=\begin{cases} a\le c \\ b \le d \end{cases}$$

假定矩阵$F$是正定值（即所有的固有值都为正），当条件不充分，数值不稳定时，为$F$的对角元素加上一个特别小的正值，从而使其稳定性得以提高。

稀疏性

Karush-Kuhn-Tucker最优化条件，经常简称为KKT条件

可微分的凸函数$f:\mathbb{R}^d \rightarrow \mathbb{R}^p$的约束条件的最小化问题

$$\mathop{min}_t f(t) \quad 约束条件 \quad g(t) \le 0$$

的解，满足如下的KKT最优化条件

$$\frac{\partial L}{\partial t}=0,g(t)\le0, \lambda \ge 0, \lambda_{i}g_i(t)=0,\forall i=1,\dots,n$$

在上式中，$L(t,\lambda)=f(t)+\lambda^{\intercal}g(t)$为拉格朗日函数，$\lambda=(\lambda_1,\dots,\lambda_p)$为拉格朗日乘子。最后的条件式$\lambda_{i}g_i(t)=0$，是指参数$\lambda_i$和$g_i(t)$中至少一个为零，因此也将其称为互补性条件。

对偶变量和约束条件应该满足如下的互补条件

$$\alpha_i (m_i-1+\xi_i)=0,\beta_i\xi_i=0,\forall i =1,\dots,n$$

当$\alpha_i =0$时，训练样本$x_i$位于间隔边界上或边界内侧，可充裕地进行正确分类。当$0<\alpha_i < C$的时候，$x_i$刚好位于间隔边界上，可正确分类。当$\alpha_i =C$的时候，$x_i$位于间隔边界上或边界外侧，如果其间隔误差$\xi_i$大于1，则间隔为负，训练样本$x_i$就不能得到正确的分类。另外，如果训练样本$x_i$位于间隔边界内侧，就有$\alpha_i=0$如果位于间隔边界外侧，就有$\alpha_i=C$。

与$0<\alpha_i < C$相对应的训练样本$x_i$称为支持向量。

使用核映射的非线性模型

首先使用非线性函数$\psi$，对训练输入样本$\lbrace x_i \rbrace_{i=1}^n$的特征空间进行描述；然后，对特征空间内的训练输入样本$\lbrace \psi(x_i) \rbrace_{i=1}^n$，适用线性的支持向量机分类器。通过这种方式得到的特征空间内的线性分类器， 在原始的输入空间是非线性分类器。

如果选择比原始的输入维数d维数更高的空间作为特征空间，则训练样本为线性可分的可能性就比较高。然而，如果特征空间的维数过大的话，计算时间也会相应的增加。

利用核映射求解支持向量机分类器的非线性模型。直接通过核函数$K(x,x’)$定义内积$\langle \psi(x), \psi(x’) \rangle$数，而不需要明确地知道特征变换$\psi$是什么的方法，就称为核映射方法。如果核函数的值与特征空间的维数无关、相互独立，非线性支持向量机的全体学习时间就完全不依赖于特征空间的维数了，例如常用的多项式核函数以及高斯核函数。

核映射方法的另一个重要特征是，即使输入$x$不是向量，也可以正确地进行分类。

使用Hinge损失最小化学习来解释

使用如下Hinge损失作为代理损失

$$max \lbrace 0,1-m \rbrace$$

当$m \ge 1$的时候，与0/1损失相同，其损失为0，当$m < 1$的时候，其损失为$1-m > 0$。当其损失为正的时候，与$m$相关的函数有倾向于负的趋势。

使用Ramp损失的鲁棒学习

Hinge损失没有上界，因此当间隔比较大的负数值时，损失就会变得非常大。所以在训练样本中包含异常值的情况下，支持向量机分类器非常容易受影响。

Ramp损失：

$$min \lbrace 1,max(0,1-m) \rbrace = \begin{cases} 1 &\text{(m<0)} \\ 1-m, &\text{$(0 \le m\le1)$} \\ 0 &\text{(m>1)} \end{cases}$$

Ramp损失是指，在Hinge损失的左侧以范围1做截断的损失。因为Ramp有损失边界，对异常值有非常强的鲁棒性，但是Ramp损失为非凸函数，很难求得最优解。