[数据结构与算法] 统计学习方法第七章—

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 统计学习方法第七章——支持向量机 -> 正文阅读

[数据结构与算法]统计学习方法第七章——支持向量机

7.1线性可分支持向量机和硬间隔最大化

7.1.1 线性可分支持向量机

给定线性可分训练集，通过间隔最大化或等价地求解相应的凸二次规划问题学习得到的分离超平面为
$w^*\cdot x+b^*=0$
以及相应的分类决策函数
$f(X)=sign(w^*\cdot x+b^*=0)$
称为线性可分支持向量机。

7.1.2 函数间隔和几何间隔

首先要知道点到超平面 $w\cdot x+b=0$ 的距离 $d=\frac{|w\cdot x+b|}{||w||}$ （推导见这里）

函数间隔为：
${\hat{\gamma}}_i=y_i(w\cdot x_i+b)$
所有样本点 $x_i,y_i)$ 的函数间隔之间的最小值，即
$\hat{\gamma}=\underset{i=1,\cdots ,N}{min}\hat{\gamma}_i$
函数间隔可以表示分类预测的正确性及确信度。但是选择分离超平面时, 只有函数间隔还不够。因为只要成比例地改变 $w$ 和 $b$ , 例如将它们改为 $2 w$ 和 $2 b$ , 超平面并没有改变，但函数间隔却变成了原来的2倍。 ${\hat{\gamma}}_i=y_i(2w\cdot x_i+2b)=2y_i(w\cdot x_i+b)$ ，这一事实启示我们，可以对分离超平面的法向量 $w$ 加某些约束，如规范化， $∣ ∣ w ∣ ∣ = 1$ ，这时函数间隔就变成了几何间隔。
${\gamma}_i=y_i(\frac{w}{||w||}\cdot x_i+\frac{b}{||w||})$
所有样本点 $x_i, y_i)$ 的几何间隔的最小值，即
$\gamma = \underset{i=1,\cdots ,N}{min}{\gamma}_i$
当 $∣ ∣ w ∣ ∣ = 1$ 时，函数间隔和几何间隔相等，如果超平面参数 $w$ 和b成比例地改变（超平面并没有改变），函数间隔也按此比例改变，而几何间隔不变。

7.1.3 间隔最大化

最大间隔分离超平面的存在唯一性，存在性书上证明很容易看懂，下面来证明唯一性。

假设存在两个最优解 $w^*_1,b^*_1)$ 和 $w^*_2,b^*_2)$ 。显然 $w^*_1||=||w^*_2||=c$ ，其中c是一个常数。令

$w=\frac{w_{1}^{*}+w_{2}^{*}}{2}, b=\frac{b_{1}^{*}+b_{2}^{*}}{2}$ , 易知 $(w, b)$ 也是解。
$c\leqslant ||\frac{w^*_1+w^*_2}{2}||\leqslant \frac{1}{2}||w^*_1||+\frac{1}{2}||w^*_2||=c$
所以 $||w||=\frac{1}{2}||w^*_1||+\frac{1}{2}||w^*_2||$ ，因此 $w^*_1=\lambda w^*_2, |\lambda|=1$ ，若 $\lambda=-1，则w=0$ 不符合题意，所以 $w^*_1=w^*_2$ 。下面再证 $b^*_1=b^*_2$ 。设 $x_{1}^{\prime}$ 和 $x_{2}^{\prime}$ 是集合 $\left\{x_{i} \mid y_{i}=+1\right\}$ 中分别对应于 $\left(w^{*}, b_{1}^{*}\right)$ 和 $\left(w^{*}, b_{2}^{*}\right)$ 使得问题的不等式等号成立的点, $x_{1}^{\prime \prime}$ 和 $x_{2}^{\prime \prime}$ 是集合 $\left\{x_{i} \mid y_{i}=-1\right\}$ 中分别对应于 $\left(w^{*}, b_{1}^{*}\right)$ 和 $\left(w^{*}, b_{2}^{*}\right)$ 使得问题的不等式等号成立的点。