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

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

支持向量机
SVM
支持向量机SVM（3）核函数、非线性支持向量机
穷则变，变则通：支持向量机
支持向量机SVM（2）线性支持向量机、软间隔最大化
统计机器学习-线性可分支持向量机与硬间隔最大化
07 SVM - 软间隔模型
支持向量机-QA
11 SVM - SMO - 序列最小优化算法
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)$ 称为样本点。再假设训练数据集是线性可分的。

线性可分：用一个超平面可以将正负例完全正确的划分在超平面两侧。

学习的目的是找到一个超平面：
$w^*\cdot x+b^*=0$
对于一个新的输入 $x$ 的分类决策函数为：
$f(x)=\mathrm{sign}(w^*\cdot x+b^*)$
满足条件的这样的超平面可能有很多个，但是支持向量机通过几何间隔在超平面的选择上加上了约束，即最大化几何间隔，使最后得到的超平面是唯一的。

函数间隔和几何间隔

函数间隔

一般来说，一个样本点到超平面的距离代表了支持向量机对这个样本分类的确信程度。由于当超平面确定，点到平面的距离公式
$\frac {|w\cdot x+b|}{||w||}$
的分母为一个常量，所以确信程度的大小由分子 $|w\cdot x+b|$ 决定。于是定义样本点 $(x_i,y_i)$ 的函数间隔：
$\hat \gamma_i=y_i(w\cdot x_i+b)\tag1$
对于 $T$ 中所有样本的函数间隔：
$\hat \gamma=\min_{i=1,\cdots N}\hat\gamma_i\tag2$
当超平面能够完全分类正确时 $y_i(w\cdot x_i+b)\geq0$ ，所以函数间隔代表确信程度最小样本的确信程度，最大化函数间隔就等于最大化支持向量机对样本分类的确信程度。在线性可分支持向量机中，这也称为硬间隔最大化。

几何间隔

由于对参数 $w$ 和 $b$ 成比例缩放，就可以改变函数间隔 $\hat\gamma$ 的大小，但这仍然表示同一个超平面。所以提出几何间隔 $\gamma$ 对 $w$ 规范化：
$\gamma_i=\frac{\hat \gamma_i}{||w||}\tag3$

$\gamma=\frac{\hat \gamma}{||w||}\tag4$

$||w||$ 代表 $w$ 的 $L2$ 范数。

重新定义问题

学习一个超平面：
$w\cdot x+b=0$
超平面的参数 $w$ 和 $b$ 需要满足条件
$\max_{w,b}\gamma\tag5$

$\mathrm{s.t.}\ \ y_i(\frac{w}{||w||}\cdot x_i+\frac{b}{||w||})\geq\gamma,\ \ i=1,2,\cdots,N\tag6$

根据公式(4)将(5)-(6)转化为关于函数间隔 $\hat\gamma$ 的表述方式：

$\max_{w,b}\frac{\hat\gamma}{||w||}\tag7$

$\mathrm{s.t.}\ \ y_i(w\cdot x_i+b)\geq\hat\gamma,\ \ i=1,2,\cdots,N\tag8$

由于函数间隔 $\hat\gamma$ 的取值不会影响最优化问题的解（参数 $w$ 和 $b$ 成比例缩放），所以取 $\hat\gamma=1$ 。而最大化 $\frac{1}{||w||}$ 等价于最小化 $\frac12||w||^2$ ，所以支持向量机最终可以表示成最优化问题：
$\min_{w,b}\ \ \frac12||w||^2\tag9$

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

这是一个凸二次规划问题，即目标函数 $f(w)=\frac12||w||^2$ 是二次函数，且约束函数 $g_i(w)=1-y_i(w\cdot x_i+b)$ 是仿射函数。

线性可分支持向量机学习算法--最大间隔法

输入：线性可分训练数据集 $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）构造并求解约束最优化问题：
$\min_{w,b}\ \ \frac12||w||^2$

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

求得最优解 $w^*$ ， $b^*$ 。

（2）由此得到分离超平面：
$w^*\cdot x+b^*=0$
分类决策函数：
$f(x)=\mathrm{sign}(w^*\cdot x+b^*)$
这样的超平面存在且唯一，证明略。

支持向量和间隔边界

支持向量是使约束条件公式(10)等号成立的点，即
$w\cdot x_i+b=y_i$
对于正例 $y_i=+1$ ，支持向量在超平面
$H_1:w\cdot x+b=1$
对于负例 $y_i=-1$ ，支持向量在超平面
$H_2:w\cdot x+b=-1$
如图所示

间隔边界

落在 $H_1$ 和 $H_2$ 上的实例点称为支持向量， $H_1$ 和 $H_2$ 之间的距离称为间隔， $H_1$ 和 $H_2$ 称为间隔边界。在决定超平面时，只有支持向量起作用，所以这种模型叫做支持向量机。

学习的对偶算法

对于最优化问题(9)-(10)：
$\min_{w,b}\ \ \frac12||w||^2$

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

首先构建拉格朗日函数：
$L(w,b,a)=\frac12||w||^2-\sum_{i=1}^N\alpha_iy_i(w\cdot x_i+b)+\sum_{i=1}^N\alpha_i\tag{11}$
其中 $\alpha_i\geq0$ ，则原始问题为极小极大问题：
$\min_{w,b}\max_\alpha L(w,b,a)$
由拉格朗日对偶性改为求解原始问题的对偶问题：
$\max_\alpha\min_{w,b}L(w,b,a)$
首先求解对偶问题的内部极小问题：
$\min_{w,b}L(w,b,a)$
将拉格朗日函数分别对 $w$ ， $b$ 求偏导并令其等于0：
$\nabla_wL(w,b,\alpha)=w-\sum_{i=1}^N\alpha_iy_ix_i=0$

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

得到：
$w=\sum_{i=1}^N\alpha_iy_ix_i\tag{12}$

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

将其代入(11)得到：
$\begin{align} L(w,b,\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_iy_i\Bigg(\bigg(\sum_{j=1}^N\alpha_jy_jx_j\bigg)\cdot x_i+b\Bigg)+\sum_{i=1}^N\alpha_i\\ &=\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-b\sum_{i=1}^N\alpha_iy_i+\sum_{i=1}^N\alpha_i\\ &=-\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 \end{align}$
于是对偶问题为：
$\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{14}$

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

$\alpha_i\geq0,\ \ i=1,2,\cdots,N$

对(14)的目标函数取相反数转化为极小问题：
$\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$

$\alpha_i\geq0,\ \ i=1,2,\cdots,N$

定理

设 $\alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_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$

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

$\alpha_i\geq0,\ \ i=1,2,\cdots,N$

的解，则存在下标 $j$ ，使得 $\alpha_j^*\gt0$ ，并按下式求得原始最优化问题
$\min_{w,b}\ \ \frac12||w||^2$

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

的解 $w^*$ ， $b^*$
$w^*=\sum_{i=1}^N\alpha_i^*y_ix_i\tag{16}$

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

证明

由于目标函数 $f(w)=\frac12||w||^2$ 和约束函数 $g_i(w)=1-y_i(w\cdot x_i+b)$ 是凸函数，且假设不等式约束 $g_i(w)$ 是严格可行的，则 $w^*$ ， $b^*$ ， $\alpha^*$ 分别原始问题和对偶问题的解的充分必要条件是 $w^*$ ， $b^*$ ， $\alpha^*$ 满足 $KKT$ 条件：
$\nabla_wL(w^*,b^*,\alpha^*)=w^*-\sum_{i=1}^N\alpha_i^*y_ix_i=0\tag{18}$

$\nabla_bL(w^*,b^*,\alpha^*)=-\sum_{i=1}^N\alpha_i^*y_i=0\tag{19}$

$\alpha_i^*g_i(w^*)=\alpha_i^*(1-y_i(w^*\cdot x_i+b^*))=0\tag{20}$

$g_i(w^*)=1-y_i(w^*\cdot x_i+b^*)\leq0\tag{21}$

$\alpha_i^*\geq0,\ \ i=1,2,\cdots,N\tag{22}$

由(18)得
$w^*=\sum_{i=1}^N\alpha_i^*y_ix_i$
由反证法，假设不存在下标 $j$ ，使得 $\alpha_j^*\gt0$ ，根据(22)，则 $\alpha^*=0$ ，代入(18)得到 $w^*=0$ ，超平面不存在，假设不成立。于是存在下标 $j$ ，使得 $\alpha_j^*\gt0$ ，根据(20)得到
$1-y_j(w^*\cdot x_j+b^*)=0$
根据 $y_j^2=1$ 得
$y_j(w^*\cdot x_j+b^*)=y_j^2$
解得
$b^*=y_j-w^*\cdot x_j$
将
$w^*=\sum_{i=1}^N\alpha_i^*y_ix_i$
代入得到
$b^*=y_j-\sum_{i=1}^N\alpha_i^*y_i(x_i\cdot x_j)$
证明完成。

线性可分支持向量机的对偶学习算法

输入：线性可分训练数据集 $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）构造并求解约束最优化问题
$\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$

$\alpha_i\geq0,\ \ i=1,2,\cdots,N$

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

（2）计算
$w^*=\sum_{i=1}^N\alpha_i^*y_ix_i$
并选择 $\alpha^*$ 的一个正分量 $\alpha_j^*\gt0$ ，计算
$b^*=y_j-\sum_{i=1}^N\alpha_i^*y_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$
可以知道对 $w^*$ 的结果有影响的样本点 $(x_i,y_i)$ ，其 $\alpha_i^*\neq0$ ，又因为 $\alpha_i^*\geq0$ ，所以 $\alpha_i^*\gt0$ ，根据 $KKT$ 条件：
$\alpha_i^*g_i(w^*)=\alpha_i^*(1-y_i(w^*\cdot x_i+b^*))=0$
所以
$1-y_i(w^*\cdot x_i+b^*)=0$
这样的样本点落在间隔边界上
$w^*\cdot x_i+b^*=\pm1$
与前面的描述相同。

支持向量机
支持向量机线性可分支持向量机与硬间隔最大化线性支持向量机与软间隔最大化非线性支持向量机与核函数序列最小最优...
SVM
二分类学习策略：间隔最大化-->求解凸二次规划分类线性可分-->硬间隔支持向量机近似线性可分-->软间隔支...
支持向量机SVM（3）核函数、非线性支持向量机
前面已经分别介绍了基于硬间隔最大化的线性可分支持向量机、基于软间隔最大化的线性支持向量机，这次来总结下使用核函数来...
穷则变，变则通：支持向量机
线性可分支持向量机通过硬间隔最大化求出划分超平面，解决线性分类问题；线性支持向量机通过软间隔最大化求出划分超平面...
支持向量机SVM（2）线性支持向量机、软间隔最大化
1 原理 1）背景线性可分支持向量机基于硬间隔最大化，所谓硬间隔最大化，我理解的就是指这个间隔最大化是被严格要...
统计机器学习-线性可分支持向量机与硬间隔最大化
考虑一个二分类问题。假设输入空间与特征空间为两个不同的空间。输入空间为欧氏空间或离散集合，特征空间为欧式空间或希尔...
07 SVM - 软间隔模型
六、硬间隔和软间隔模型之前两章介绍的内容是硬间隔模型：《05 SVM - 支持向量机 - 概念、线性可分》《06...
支持向量机-QA
Q1：SVM的类型有哪些？三类：线性可分支持向量机、线性支持向量机、非线性支持向量机线性可分支持向量机：当训练数...
11 SVM - SMO - 序列最小优化算法
05 SVM - 支持向量机 - 概念、线性可分06 SVM - 线性可分模型算法和案例07 SVM - 软间隔模...
svm
支持向量机是建立在统计学习理论基础之上的新一代机器学习算法，支持向量机的优势主要体现在解决线性不可分问题，它通过引...