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

作者: 又双叒叕苟了一天 | 来源:发表于2020-06-22 23:22 被阅读0次

支持向量机
穷则变，变则通：支持向量机
支持向量机SVM（3）核函数、非线性支持向量机
SVM
统计机器学习-线性支持向量机与软间隔最大化
11 SVM - SMO - 序列最小优化算法
支持向量机SVM（2）线性支持向量机、软间隔最大化
TensorFlow HOWTO 2.1 支持向量分类（软间隔）
07 SVM - 软间隔模型
统计机器学习-线性可分支持向量机与硬间隔最大化

假设给定一个特征空间上的训练数据集
$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，所以支持向量机的学习比感知机有更高的要求。

支持向量机
支持向量机线性可分支持向量机与硬间隔最大化线性支持向量机与软间隔最大化非线性支持向量机与核函数序列最小最优...
穷则变，变则通：支持向量机
线性可分支持向量机通过硬间隔最大化求出划分超平面，解决线性分类问题；线性支持向量机通过软间隔最大化求出划分超平面...
支持向量机SVM（3）核函数、非线性支持向量机
前面已经分别介绍了基于硬间隔最大化的线性可分支持向量机、基于软间隔最大化的线性支持向量机，这次来总结下使用核函数来...
SVM
二分类学习策略：间隔最大化-->求解凸二次规划分类线性可分-->硬间隔支持向量机近似线性可分-->软间隔支...
统计机器学习-线性支持向量机与软间隔最大化
假设给定一个特征空间上的训练数据集其中，，，，为第个特征向量，也称为实例，为的类标记，当时，称为正例；当时，称为负...
11 SVM - SMO - 序列最小优化算法
05 SVM - 支持向量机 - 概念、线性可分06 SVM - 线性可分模型算法和案例07 SVM - 软间隔模...
支持向量机SVM（2）线性支持向量机、软间隔最大化
1 原理 1）背景线性可分支持向量机基于硬间隔最大化，所谓硬间隔最大化，我理解的就是指这个间隔最大化是被严格要...
TensorFlow HOWTO 2.1 支持向量分类（软间隔）
在传统机器学习方法，支持向量机算是比较厉害的方法，但是计算过程非常复杂。软间隔支持向量机通过减弱了其约束，使计算变...
07 SVM - 软间隔模型
六、硬间隔和软间隔模型之前两章介绍的内容是硬间隔模型：《05 SVM - 支持向量机 - 概念、线性可分》《06...
统计机器学习-线性可分支持向量机与硬间隔最大化
考虑一个二分类问题。假设输入空间与特征空间为两个不同的空间。输入空间为欧氏空间或离散集合，特征空间为欧式空间或希尔...