当前位置：网站首页>神经网络与深度学习-6- 支持向量机1 -PyTorch

神经网络与深度学习-6- 支持向量机1 -PyTorch

2022-07-26 09:18:00 【明朝百晓生】

前言

SVM (support vector machines) 是机器学习里面经典的二分类模型

它是定义在特征空间上间隔最大的线性模型

线性支持向量机和非线性支持向量机，硬间隔软间隔，SMO(序列最小最优算法)

参考文档<<统计学习方法>>

Gram 矩阵

浅谈「正定矩阵」和「半正定矩阵」 - 知乎

格拉姆矩阵是半正定的

线性可分支持向量机与硬间隔最大化
线性支持向量机与软间隔最大化
非线性支持向量机与核函数

一线性可分支持向量机与硬间隔最大化

1.1 线性可分支持向量机定义

给定线性可分数据集,通过间隔最大化或等价求解相应的凸二次规划问题

学习得到的分离超平面为

$w^{*}*x+b^{*}=0$

以及相应的分类决策函数

$f(x)=sign(w^{*}*x+ b^{*} )$

1.2 函数间隔几何间隔

一个点距离超平面远近可以表示分类预测的确信程度

函数间隔:

定义超平面(w,b)关于样本点 (x_i,y_i) 的函数间隔为

$\hat{r_i}=y_i(w *x_i+b)$

最小化(距离超平面最近的点）

$\hat{r}=min_{i=1,..N}\hat{r_i}$

几何间隔

定义超平面(w,b)关于样本点 (x_i,y_i) 的几何间隔为

$r_i=y_i*( \frac{w}{||w||} * x_i + \frac{1}{||w||}*b)$

$\hat{r}=min_{i=1,..N}\hat{r_i}$

当函数间隔和几何间隔相等

1.3 间隔最大化

对训练数据集找到几何间隔最大的超平面，不仅仅讲正负例分开，而且对最难分的实例点也有足够大的确信度讲它们分开

间隔最大化

线性可分SVM学习最优化问题

$min_{w,b}\frac{1}{2}||w||^2$

$s.t : y_i(w x_i+ b)-1\geq 0, i=1,2,...N$

等价于凸二次规划问题

min f(w): 凸函数
$st : \left\{\begin{matrix} g_i(w)\leq 0, i=1,2..k\\ h_i(w)=0,i=1,2,...l \end{matrix}\right.$
约束为凸函数+仿射函数

1.4 最大化间隔算法

输入：
线性可分数据集 $T=\begin{Bmatrix} (x_1,y_1) & (x_2,y_2) &... & (x_N,y_N) \end{Bmatrix}$
   $y_i \in \begin{Bmatrix} -1,+1 \end{Bmatrix}$
输出：
最大分离超平面和分类决策函数
step1:
构造求解约束最优化问题
   $min_{w,b} \frac{1}{2}||w||^2$
   $s.t: y_i (w x_i+b-1) \geq 0, i=1,2,..N$
step2: 分离超平面
   $w^{*}x+b^{*}=0$
step3: 分类决策函数
$f(x)=sign(w^{*} x +b^{*})$

1.5 学习对偶算法

定义拉格朗日函数

$L=\frac{1}{2}||w||^2-\sum_{i=1}^{N} \alpha_i y_i(wx_i+b)+\sum_{i=1}^{N} \alpha_i$

求解方法：

先对我w,b求极小，再对拉格朗日乘子求极大

1： $min_{w,b} L(w,b, \alpha)$

对w,b求偏导数后，再带入

$min_{w,b}L= -\frac{1}{2} \sum_{i}\sum_{j} \alpha_i \alpha_j y_i y_j x_i * x_j^T+\sum \alpha_i$

s.t

$\left\{\begin{matrix} \sum_{i} \alpha_i y_i=0 \\ \alpha_i \geq 0 \end{matrix}\right. i \in {0,1,..N}$

2 对 $\alpha$ 求极大值，对偶问题

$min_{\alpha} \frac{1}{2} \sum \alpha_i \alpha_j y_i y_j x_i x_j^T -\sum \alpha_i$

s.t:

$\begin{bmatrix} \sum_{i=1}^{N} \alpha_i y_i=0 \\ \alpha_i \geq 0 \end{bmatrix} i \in 0,1,...N$

3 利用KKT 条件求解

$\left\{\begin{matrix} \alpha_i^{*}(y_i(w^*x_i+b^*)-1)=0\\ y_i(w^*x_i+b^*)-1\geq 0 \end{matrix}\right.$
训练集中 $\alpha_i^*>0$ 的样本点的实例称为支持向量，在分类中起作用
$y_i(w^*x+b)-1>0:\alpha_i^* =0$
$y_i(w^*x+b^*)-1=0,\alpha^*>0$

$w^{*}=\sum_{i=1}^{N}\alpha_i^{*}y_i x_i$ ( $\alpha^{*}\geq 0$ )

$b^{*}=y_{j} - \sum_{i=1}^{N} \alpha_{i}^{*} y_i x_{i} * x_j^{T}$ , 其中 x_j 对应的 $\alpha_j^{*}>0$

线性可分支持向量机学习算法
输入：
线性可分数据集 $T=\begin{Bmatrix} (x_1,y_1) & (x_2,y_2) &... & (x_N,y_N) \end{Bmatrix}$
   $y_i \in \begin{Bmatrix} -1,+1 \end{Bmatrix}$
输出：
最大分离超平面和分类决策函数

构造并求解约束最优化问题
$min_{\alpha} \frac{1}{2}\sum_{i}\sum_{j} \alpha_i \alpha_j y_i y_j \left ( x_i,x_j \right )-\sum_{i} \alpha_i$
s.t
   $\sum_{i}\alpha_i y_i=0$
   $\alpha_i \geq 0,i =1,2..N$
计算
$w^{*}=\sum_i \alpha_i^{*}y_ix_i$
选择 $\alpha_j^{*}>0$ 的分量
   $b^{*}=y_j -\sum_{i}\alpha_i^{*}y_i(x_i,x_j)$
得到分离超平面
$w^{*} x+b^{*}=0$
分类决策函数：
$f(x)=sign(w^{*} x +b^{*})$

二线性支持向量机与软间隔最大化

对于训练数据集中有些特异点，函数间隔不能满足间隔大于等于1的约束条件，引入了松弛变量 $\epsilon_i$

2.1 凸二次规划原始问题

$min_{w,b,\epsilon } \frac{1}{2}||w||^2+C \sum_{i=1}^{N} \epsilon_i$

$s.t : \left\{\begin{matrix} y_i(wx_i+b)\geq 1-\varepsilon_i\\ \varepsilon_i \geq 0,i=1,2...,N \end{matrix}\right.$

2.2 学习对偶算法

原始问题的拉格朗日函数

$L=\frac{1}{2}||w||^2+C\sum_{i} \varepsilon_i-\sum_i \alpha_i (y_i(wx_i+b)+\varepsilon_i-1)-\sum_i u_i \varepsilon_i$

首先求L 对 w,b, $\varepsilon$ 求偏导数

$w=\sum_i \alpha_i y_i x_i$

$\sum_i \alpha_i y_i=0$

$\alpha_i+u_i=C$

带入，跟前面一样，得到对偶问题

$min_{\alpha} \frac{1}{2} \sum \alpha_i \alpha_j y_i y_j x_i x_j^T -\sum \alpha_i$

s.t

$\sum_i \alpha_i y_i=0$

$\alpha_i+u_i=C$

$\alpha_i \geq 0$

$u_i \geq 0$

定理设 $\alpha^{*}=(a_1^*,\alpha_2^*,....,\alpha_N^*)^T$ 是对偶问题的一个解，若存在 $\alpha^*$ 的一个分量 $0<\alpha_j^*<C$ ,

则原始问题的解可以按照下面求得：

$w^{*}=\sum_{i}\alpha_i^* y_i x_i$

b^*=y_j-w^*x_j

证明：

原始问题是凸二次规划问题，满足KKT条件

$\bigtriangledown_wL = w^*-\sum_{i}\alpha_i^*y_ix_i=0$

$\bigtriangledown_bL =\sum \alpha_i^*y_i=0$

$\bigtriangledown_{\varepsilon }L = C-\alpha^*-u^*=0$

$\alpha_i^*(y_i(w^*x_i+b)+\varepsilon_i-1)=0$

$u_i\varepsilon_i=0$

$y_i(w^*x+b^*)+\varepsilon_i^*-1\geq 0$

$\alpha_i^*\geq 0$

$u_i^*\geq 0$

2.3 学习算法

输入：
训练数据集 $T=\begin{Bmatrix} (x_1,y_1) &(x_2,y_2) & ... &(x_N,y_N) \end{Bmatrix}$ ,
其中    $x_i \in X,y_i =\begin{Bmatrix} -1 ,& +1 \end{Bmatrix},i=1,2...,N$
输出: 分离超平面和分类决策函数
1：选择惩罚因子C>0,构造求解凸二次规划问题
   $min_{\alpha}\sum_i\sum_j \alpha_i\alpha_j y_i y_j (x_i \bullet x_j)-\sum_i \alpha_i$
s.t
   $\sum_i \alpha_i y_i=0$
$0\leq \alpha_i\leq C$
2: 计算
   $w^{*}=\sum \alpha_i^{*}y_i x_i$
选择一个 $0<\alpha_j^*<C$
   $b_j=y_j-\sum_{i}y_i\alpha_i^{*}(x_i\bullet x_j)$
3: 得到分离超平面
   $w^{*}\bullet x+b^*=0$
4: 分类决策函数
$f(x)=sign(w^*\bullet x+b^*)$

2.4 支持向量

2.5 合页损失函数

这是另一种解释：最小化损失函数

$L=\sum_i [1-y_i(w \bullet x_i+b)]+\lambda ||w||^2$

第一项是合页损失（Hinge loss function）

L=[1-y(w x+b)]

$[z]=\left\{\begin{matrix} z,z>0\\ 0,z \leq 0 \end{matrix}\right.$

三非线性支持向量机与核函数

3.1 非线性分类问题

首先使用变换将原空间的数据映射到新空间;然后再新空间里面使用线性分类的学习方法从训练数据中学习到分类模型

3.2 核函数定义

设 $\chi$ 是输入空间（欧式空间的子集或者离散集合）,又设H为特征空间（希尔伯特空间）,

如果存在一个从 $\chi$ 到H的映射

$\phi(x): \chi \rightarrow H$

使得对都有 $x,z \in \chi$ ,函数 $K(x,z)=\phi(x)\bullet \phi(z)$

称

k(x,z) 为核函数

$\phi(x)$ 为映射函数

3.3 正定核

能成为和函数的充要条件就是核函数

假设K(x,z)是定义在 $\chi * \chi$ 上的对称函数,并且任意的 $x_1,x_2,...x_m \in \chi$
K(x,z)关于的Gram 矩阵是半正定的。可以根据K(x,z) 构成一个希尔伯特空间H
步骤：
首先定义 $\phi$ 并构成向量空间S
然后在S上定义内积构成内积空间
最后将S完备化构成希尔伯特空间
Gram 矩阵 - 知乎