统计学习方法第七章支持向量机（2）——线性支持向量机

7.2 线性支持向量机

假设给定一个特征空间上的训练数据集

$$T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$$

其中 $x_i\in{\cal X}=\mathbb{R}^n$，$y_i\in{\cal Y}=\{+1,-1\}$，$i=1,2,\cdots,N$。再假设训练数据集不是线性可分的。通常情况是，训练数据中有一些特异点（outlier），将这些特异点除去后，剩下大部分的样本点组成的集合是线性可分的。

线性不可分意味着某些样本点 $(x_i,y_i)$ 不能满足函数间隔大于等于 1 的约束条件，为了解决这个问题，可以对每个样本点 $(x_i,y_i)$ 引进一个松弛变量 $\xi_i\geq0$，使函数间隔加上松弛变量大于等于 1。这样，约束条件变为

$$y_i(w\cdot x_i+b)\geq1-\xi_i$$

同时，对每个松弛变量支付一个代价，目标函数由原来的 $\frac{1}{2}\|w\|^2$ 变成

$$\frac{1}{2}\|w\|^2+C\sum_{i=1}^N\xi_i$$

这里，$C>0$ 称为惩罚参数。一般由应用问题决定，$C$ 值大时对误分类的惩罚增加，$C$ 值小时对误分类的惩罚减小。

线性不可分的线性支持向量机的学习问题变成如下凸二次规划（convex quadratic programming）问题（原始问题）：

$$\min_{w,b,\xi}\ \frac{1}{2}\|w\|^2+C\sum_{i=1}^N\xi_i\\ \text{s.t.}\ \ \ \ \begin{eqnarray} y_i\left(w\cdot x_i+b\right) &\geq& 1-\xi_i,\ i=1,2,\cdots,N \\ \xi_i &\geq& 0,\ i=1,2,\cdots,N \end{eqnarray}$$

原始问题关于 $(w,b,\xi)$ 的解是存在的。可以证明 $w$ 的解是唯一的，但 $b$ 的解可能不唯一，而是存在于一个区间。

定义 7.5（线性支持向量机）对于给定的线性不可分的训练数据集，通过求解下面的凸二次规划问题

即软间隔最大化问题，得到的分离超平面为
$$w^\star\cdot x+b^\star=0$$
以及相应的分类决策函数
$$f(x)=\text{sign}(w^\star\cdot x+b^\star)$$
称为线性支持向量机。

7.2.2 学习的对偶算法

定义拉格朗日函数：

$$L(w,b,\xi,\alpha,\mu)=\frac{1}{2}\|w\|^2+C\sum_{i=1}^N\xi_i-\sum_{i=1}^N\alpha_iy_i(w\cdot x_i+b) \\ +\sum_{i=1}^N\alpha_i-\sum_{i=1}^N\alpha_i\xi_i-\sum_{i=1}^N\mu_i\xi_i$$

其中，$\alpha_i\geq0$，$\mu_i\geq0$。

根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题：

$$\max_{\alpha,\mu}\min_{w,b,\xi}L(w,b,\xi,\alpha,\mu)$$

$\blacksquare$ 求 $\min_{w,b,\xi}L(w,b,\alpha,\mu)$

求偏导并令偏导为 0

$$\nabla_wL(w,b,\xi,\alpha,\mu)=w-\sum_{i=1}^N\alpha_iy_ix_i=0 \\ \nabla_bL(w,b,\xi,\alpha,\mu)=-\sum_{i=1}^N\alpha_iy_i=0 \\ \nabla_{\xi_i} L(w,b,\xi,\alpha,\mu)=C-\alpha_i-\mu_i=0$$

得

$$w=\sum_{i=1}^N\alpha_iy_ix_i \\ \sum_{i=1}^N\alpha_iy_i=0 \\ C-\alpha_i-\mu_i=0$$

利用上面三式，得

$$L(w,b,\xi,\alpha,\mu)=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i$$

即

$$\min_{w,b,\xi}L(w,b,\xi,\alpha,\mu)=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i$$

$\blacksquare$ 求 $\min_{w,b,\xi}L(w,b,\xi,\alpha,\mu)$ 对 $\alpha$，$\mu$ 的极大

即是求对偶问题

$$\max_{\alpha,\mu} -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i \\ \text{s.t.}\ \ \ \ \begin{eqnarray} \sum_{i=1}^N\alpha_iy_i &=& 0 \\ C-\alpha_i &-& \mu_i = 0 \\ \alpha_i \geq 0\ i &=& 1,2,\cdots,N \\ \mu_i\geq0\ i &=& 1,2,\cdots,N \end{eqnarray}$$

也就是下面等价的最小化问题

$$\min_{\alpha} \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha_i \\ \text{s.t.}\ \ \ \ \begin{eqnarray} \sum_{i=1}^N\alpha_iy_i &=& 0 \\ 0\leq\alpha_i\leq C,\ i &=& 1,2,\cdots,N \end{eqnarray}$$

原始最优化问题和对偶最优化问题满足拉格朗日对偶性定理 2 的条件，所以存在 $w^\star$，$b^\star$ 和 $\alpha^\star$ 使 $w^\star$，$b^\star$是原始问题的解，$\alpha^\star$是对偶问题的解。

定理 7.3 设 $\alpha^\star=\left(\alpha_1^\star,\alpha_2^\star,\cdots,\alpha_N^\star\right)^\text{T}$ 是对偶最优问题的解，则存在下标 $j$，使得 $0<\alpha_i^\star<C$，并且可按下式求得原始最优化问题的解

$$w^\star=\sum_{i=1}^N\alpha_i^\star y_ix_i \\ b^\star=y_j-\sum_{i=1}^N\alpha_i^\star y_i(x_i\cdot x_j)$$

由此定理可知，分离超平面可以写成

$$\sum_{i=1}^N\alpha_i^\star y_i(x\cdot x_i)+b^\star=0$$

分类决策函数可以写成

$$f(x)=\text{sign}\left(\sum_{i=1}^N\alpha_i^\star y_i(x\cdot x_i)+b^\star\right)$$

分类决策函数只依赖于输入 $x$ 和训练样本输入的内积。上式称为线性支持向量机的对偶形式。

算法 7.3（线性支持向量机学习算法）
输入：线性可分训练数据集 $T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$，其中 $x_i\in{\cal X}=\mathbb{R}^n$，$y_i\in{\cal Y}=\{+1,-1\}$，$i=1,2,\cdots,N$
输出：分离超平面和分类决策函数
(1) 选择惩罚参数 $C>0$，构造并求解约束最优化问题

求得最优解 $\alpha^\star=\left(\alpha_1^\star,\alpha_2^\star,\cdots,\alpha_N^\star\right)^\text{T}$
(2) 计算
$$w^\star=\sum_{i=1}^N\alpha_i^\star y_ix_i$$
并选择 $\alpha^\star$ 的一个分量满足 $0<\alpha_i^\star<C$，计算
$$b^\star=y_j-\sum_{i=1}^N\alpha_i^\star y_i(x_i\cdot x_j)$$
(3) 求得分离超平面
$$\sum_{i=1}^N\alpha_i^\star y_i(x\cdot x_i)+b^\star=0$$
分类决策函数
$$f(x)=\text{sign}\left(\sum_{i=1}^N\alpha_i^\star y_i(x\cdot x_i)+b^\star\right)$$

7.2.3 支持向量

在线性不可分的情况下，将对偶问题的解

$$\alpha^\star=\left(\alpha_1^\star,\alpha_2^\star,\cdots,\alpha_N^\star\right)^\text{T}$$

中对应于 $\alpha_i^\star>0$ 的样本点 $(x_i,y_i)$ 的实例 $x_i$ 称为支持向量（软间隔的支持向量）。实例 $x_i$ 到间隔边界的距离是

$$\frac{\xi_i}{\|w\|}$$

若 $\alpha_i^\star<C$，则 $\xi_i=0$，支持向量 $x_i$ 正好落在间隔边界上
若 $\alpha_i^\star=C$ 且 $\xi_i=0$，则分类正确，支持向量 $x_i$ 正好落在间隔边界上
若 $\alpha_i^\star=C$ 且 $0<\xi_i<1$，则分类正确，支持向量 $x_i$ 在间隔边界和分离超平面之间
若 $\alpha_i^\star=C$ 且 $\xi_i=1$，则支持向量 $x_i$ 在分离超平面上
若 $\alpha_i^\star=C$ 且 $\xi_i>1$，则分类错误，支持向量 $x_i$ 位于分离超平面误分类一侧

7.2.4 合页损失函数

线性支持向量机学习还有另外一种解释，就是最小化以下目标函数：

$$\sum_{i=1}^N[1-y_i(w\cdot x_i+b)]_++\lambda\|w\|^2$$

目标函数的第一项是经验损失或经验风险，函数

$$L(y(w\cdot x+b))=[1-y(w\cdot x+b)]_+$$

称为合页损失函数（hinge loss function）。下标 “+” 表示以下取正值的函数：

$$[z]_+=\begin{cases} z, & z>0 \\ 0, & z\leq0\end{cases}$$

也就是说当样本被正确分类且函数间隔（确信度）大于 1 时，损失是 0。目标函数的第二项是系数为 $\lambda$ 的 $w$ 的 $L_2$ 范数，是正则化项。

定理 7.4 线性支持向量机原始优化问题

等价于最优化问题
$$\min_{w,b}\sum_{i=1}^N[1-y_i(w\cdot x_i+b)]_++\lambda\|w\|^2$$

下图中绘制了合页损失函数。图中还画出了 0-1 损失函数，可以认为 0-1 损失函数是二类分类问题的真正的损失函数，而合页损失函数是 0-1 损失函数的上界。由于 0-1 损失函数不是连续可导的，直接优化由其构成的目标函数比较困难，可以认为线性支持向量机是优化由 0-1 损失函数的上界（合页损失函数）构成的目标函数，这时的上界损失函数又称为代理损失函数（surrogate loss function）。

合页损失函数

相比于感知机损失函数，合页损失函数不仅要求正确分类，而且确信度足够高时损失才为 0，也就是说，合页损失函数对学习有更高的要求。

统计学习方法第七章支持向量机（2）——线性支持向量机

7.2 线性支持向量机

7.2.2 学习的对偶算法

7.2.3 支持向量

7.2.4 合页损失函数

发布日期

最后更新

分类

标签