统计机器学习-线性支持向量机与软间隔最大化

2020-06-22 本文已影响0人又双叒叕苟了一天

假设给定一个特征空间上的训练数据集
$T= \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$
其中， $x_i\in\mathcal X=\textbf R^n$ ， $y_i\in\mathcal Y=\{+1,-1 \}$ ， $i=1,2,\cdots,N$ ， $x_i$ 为第 $i$ 个特征向量，也称为实例， $y_i$ 为 $x_i$ 的类标记，当 $y_i=+1$ 时，称 $x_i$ 为正例；当 $y_i=-1$ 时，称 $x_i$ 为负例， $(x_i,y_i)$ 称为样本点。再假设训练数据集不是线性可分的。通常情况是，训练数据中有一些特异点，将这些特异点除去后，剩下大部分的样本点组成的集合是线性可分的。

线性不可分意味着某些样本点 $(x_i,y_i)$ 不能满足函数间隔大于等于1的约束条件。为了解决这个问题，可以对每个样本点 $(x_i,y_i)$ 引进一个松弛变量 $\xi_i\geq0$ ，使函数间隔加上松弛变量大于等于1。这样，约束条件变为
$1-\xi_i-y_i(w\cdot x_i+b)\leq0$
目标函数由原来的最小化 $\frac12||w||^2$ 变成最小化
$\frac12||w||^2+C\sum_{i=1}^N\xi_i$
$C$ 是对误分类的惩罚， $C$ 越大，对误分类惩罚越大。相对于线性可分支持向量机的硬间隔最大化，这叫做软间隔最大化。

于是线性不可分支持向量机的学习的原始问题为凸二次规划问题：
$\min_{w,b,\xi}\frac12||w||^2+C\sum_{i=1}^N\xi_i\tag1$

$\mathrm{s.t.}\ \ 1-\xi_i-y_i(w\cdot x_i+b)\leq0,\ \ i=1,2,\cdots,N\tag2$

$-\xi_i\leq0,\ \ i=1,2,\cdots,N\tag3$

可以证明 $w$ 的解是唯一的，但 $b$ 的解可能不唯一，而是存在于一个区间。证明略。

假如 $w^*$ ， $b^*$ 是最优化问题(1)-(3)的解，则得到的超平面为
$w^*\cdot x+b^*=0\tag4$
分类决策函数为
$f(x)=\mathrm{sign}(w^*\cdot x+b^*)\tag5$
称为线性支持向量机。

对偶的学习算法

由原始问题(1)-(3)，首先构建拉格朗日函数
$L(w,b,\xi,\alpha,\mu)=\frac12||w||^2+C\sum_{i=1}^N\xi_i+\sum_{i=1}^N\alpha_i(1-\xi_i-y_i(w\cdot x_i+b))-\sum_{i=1}^N\mu_i\xi_i\tag6$
其中 $\alpha_i\geq0$ ， $\mu_i\geq0$ ，于是原始问题可以写成
$\min_{w,b,\xi}\max_{\alpha,\mu}L(w,b,\xi,\alpha,\mu)$
则对偶问题为
$\max_{\alpha,\mu}\min_{w,b,\xi}L(w,b,\xi,\alpha,\mu)$
首先求解内部极小化问题，求 $L(w,b,\xi,\alpha,\mu)$ 对 $w$ ， $b$ ， $\xi$ 的偏导并使其等于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}=C-\alpha_i-\mu_i=0$

得
$w=\sum_{i=1}^N\alpha_iy_ix_i\tag7$

$\sum_{i=1}^N\alpha_iy_i=0\tag8$

$C-\alpha_i-\mu_i=0\tag9$

将公式(7)-(9)代入(6)得到
$L(w,b,\xi,\alpha,\mu)=-\frac12\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$
于是原始的问题(1)-(3)的对偶问题可以写成
$\max_{\alpha}-\frac12\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 \tag{10}$

$\mathrm{s.t.}\ \ \sum_{i=1}^N\alpha_iy_i=0\tag{11}$

$C-\alpha_i-\mu_i=0\tag{12}$

$\alpha_i\geq0\tag{13}$

$\mu_i\geq0,\ \ i=1,2,\cdots,N\tag{14}$

对其进一步改写，由公式(12)得
$\mu_i=C-\alpha_i$
代入公式(14)得
$\alpha_i\leq C$
所以公式(12)-(14)可以简写为
$0\leq\alpha_i\leq C,\ \ i=1,2,\cdots,N$
再对目标函数取相反数，得到对偶问题
$\min_{\alpha}\frac12\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 \tag{15}$

$\mathrm{s.t.}\ \ \sum_{i=1}^N\alpha_iy_i=0\tag{16}$

$0\leq\alpha_i\leq C,\ \ i=1,2,\cdots,N\tag{17}$

定理

设 $\alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_N^*)$ 是对偶问题(15)-(17)的一个解，若存在 $\alpha^*$ 的一个分量 $\alpha_j^*$ ， $0\lt\alpha_j^*\lt C$ ，则原始问题(1)-(3)的解 $w^*$ , $b^*$ 可按下式得到：
$w^*=\sum_{i=1}^N\alpha_i^*y_ix_i\tag{18}$

$b^*=y_j-\sum_{i=1}^Ny_i\alpha_i^*(x_i\cdot x_j)\tag{19}$

证明略。

于是分离超平面可以写成
$\sum_{i=1}^N\alpha_i^*y_i(x\cdot x_i)+b^*=0$
分类决策函数
$f(x)=\mathrm{sign}\bigg(\sum_{i=1}^N\alpha_i^*y(x\cdot x_i)+b^*\bigg)$

线性支持向量机学习算法

输入：训练数据集 $T= \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N) \}$ ，其中， $x_i\in\mathcal X=\textbf R^n$ ， $y_i\in\mathcal Y=\{-1,+1\}$ ， $i=1,2,\cdots,N$ ；

输出：分离超平面和分类决策函数。

（1）选择惩罚参数 $C\gt0$ ，构造并求解凸二次规划问题
$\min_{\alpha}\frac12\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$

$\mathrm{s.t.}\ \ \sum_{i=1}^N\alpha_iy_i=0$

$0\leq\alpha_i\leq C,\ \ i=1,2,\cdots,N$

求的最优解 $\alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_N^*)$ 。

（2）计算 $w^*=\sum_{i=1}^N\alpha_iy_ix_i$

选择 $\alpha^*$ 的一个分量 $\alpha_j^*$ 适合条件 $0\lt\alpha_j^*\lt C$ ，计算
$b^*=y_j-\sum_{i=1}^Ny_i\alpha_i^*(x_i\cdot x_j)$
（3）求得分离超平面
$w^*\cdot x+b^*=0$
分类决策函数：
$f(x)=\mathrm{sign}(w^*\cdot x)+b^*$

支持向量

由公式
$w^*=\sum_{i=1}^N\alpha_i^*y_ix_i$
得知 $\alpha_i^*\neq0$ 的样本点 $x_i$ 能够影响支持向量机的参数。而 $0\leq\alpha_i^*\leq C$ ，所以支持向量为 $0\lt\alpha_i^*\leq C$ 的样本点 $x_i$ 。这些支持向量分布在间隔边界上、间隔边界与分离超平面之间或者在分离超平面误分一侧。若 $\alpha_i^*\lt C$ ，则 $\xi_i=0$ （由 $KKT$ 条件可以推出，由于 $\xi^*$ 的结果不影响分离超平面，所以一般也不去算，其计算过程略），支持向量恰好落在间隔边界上；若 $\alpha_i^*=C$ ， $0\lt\xi_i\lt1$ ，则分类正确，支持向量在间隔边界与分离超平面之间；若 $\alpha_i^*=C$ ， $\xi_i=1$ ，则 $x_i$ 在分离超平面上；若 $\alpha_i^*=C$ ， $\xi_i\gt1$ ，则 $x_i$ 在分离超平面误分一侧。

合页损失函数

线性支持向量机的学习还等价于最小化以下目标函数：
$\min_{w,b}\sum_{i=1}^N[1-y_i(w\cdot x_i+b)]_++\lambda||w||^2\tag{20}$
证明过程略。其中目标函数的第一项是经验损失或经验风险，第二项是正则化项。函数
$L(y(w\cdot x+b))=[1-y(w\cdot x+b)]_+$
称为合页损失函数。下标"+"表示 $ReLU$ 函数，由于函数形状像一个合页，故名合页损失函数。合页损失函数相比感知机的0-1损失，不仅要求分类正确，还要求确信度足够高时（函数间隔大于等于1）损失才是0，所以支持向量机的学习比感知机有更高的要求。

统计机器学习-线性支持向量机与软间隔最大化

对偶的学习算法

定理

线性支持向量机学习算法

支持向量

合页损失函数

猜你喜欢

热点阅读