[数据结构与算法] ＜机器学习＞支持向量机(SVM)理论

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

-> 数据结构与算法 -> ＜机器学习＞支持向量机(SVM)理论 -> 正文阅读

[数据结构与算法]＜机器学习＞支持向量机(SVM)理论

1、概念

支持向量机（support vector machines，SVM）是一种二类分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器；同时，支持向量机包括的核技巧使它成为实质上的非线性分类器。支持向量机的学习策略就是间隔最大化，可形式化为一个求解凸二次规划（convex quadratic programming）的问题，也等价于正则化的合页损失函数的最小化问题。支持向量机的学习算法是求解凸二次规划的最优化算法。

假设给定一个特征空间上的训练数据集
$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$
其中， $x_i\in\chi=R^n$ ， $y_i\in\Upsilon=\{+1,-1\}$ ， $i = 1, 2, . . . N$ ， $x_i$ 为第 $i$ 个特征向量，也称为实例， $y_i$ 为 $x_i$ 的类标记，当 $y_i=+1$ 时，称 $x_i$ 为正例；当 $y_i＝-1$ 时，称 $x_i$ 为负例， $x_i，y_i)$ 称为样本点。

2、线性可分支持向量机

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

2.1、函数间隔和几何间隔
（1）（函数间隔） 对于给定的训练数据集 $T$ 和超平面 $(w, b)$ ，定义超平面 $(w, b)$ 关于样本点 $x_i,y_i)$ 的函数间隔为
$\hat{\gamma_i}=y_i(w\cdot x_i+b)$
定义超平面 $(w, b)$ 关于训练数据集 $T$ 的函数间隔为超平面 $(w, b)$ 关于 $T$ 中所有样本点 $x_i，y_i)$ 的函数间隔之最小值，即
$\hat{\gamma}=\underset{i=1,...N}{min} \hat{\gamma_i}$
函数间隔可以表示分类预测的正确性及确信度。但是选择分离超平面时，只有函数间隔还不够。因为只要成比例地改变 $w$ 和 $b$ ，例如将它们改为 $2 w$ 和 $2 b$ ，超平面并没有改变，但函数间隔却成为原来的2倍。这一事实启示我们，可以对分离超平面的法向量 $w$ 加某些约束，如规范化， $||\omega||＝ 1$ ，使得间隔是确定的。这时函数间隔成为几何间隔。

（2）（几何间隔） 对于给定的训练数据集 $T$ 和超平面 $(w, b)$ ，定义超平面 $(w, b)$ 关于样本点 $x_i,y_i)$ 的几何间隔为
$\gamma_i=y_i(\frac{\omega}{||\omega||}\cdot x_i + \frac{b}{||\omega||})$
定义超平面 $(w, b)$ 关于训练数据集 $T$ 的几何间隔为超平面 $(w, b)$ 关于 $T$ 中所有样本点 $x_i,y_i)$ 的几何间隔之最小值，即
${\gamma}=\underset{i=1,...N}{min} {\gamma_i}$
2.2、间隔最大化
下面考虑如何求得一个几何间隔最大的分离超平面，即最大间隔分离超平面。具体地，这个问题可以表示为下面的约束最优化问题：
$\underset{\omega,b}{max}\ \gamma$
$s.t.\qquad y_i(\frac{\omega}{||\omega||}\cdot x_i + \frac{b}{||\omega||})\geq\gamma,\quad i=1,2,...,N$
考虑几何间隔和函数间隔的关系，可将这个问题改写为
$\underset{\omega,b}{max} \quad \frac{\hat{\gamma}}{||\omega||}$
$\qquad y_i(w\cdot x_i+b)\geq\hat{\gamma}, \quad i=1,2,...,N$
函数间隔 $\hat{\gamma}$ 的取值并不影响最优化问题的解。事实上，假设将 $w$ 和 $b$ 按比例改变为 $\lambda w$ 和 $\lambda b$ ，这时函数间隔成为 $\lambda \hat{\gamma}$ 。函数间隔的这一改变对上面最优化问题的不等式约束没有影响，对目标函数的优化也没有影响，这样，就取 $\hat{\gamma}=1$ ，将 $\hat{\gamma}=1$ 代入上面的最优化问题，注意到最大化 $\frac{1}{||\omega||}$ 和最小化 $\frac{1}{2}{||\omega||}^2$ 是等价的，于是引出线性可分支持向量机学习算法。

2.3、线性可分支持向量机学习算法——最大间隔法
输入：线性可分训练数据集分类决策函数 $T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$ ，其中， $x_i\in\chi=R^n$ ， $y_i\in\Upsilon=\{+1,-1\}$ ， $i = 1, 2, . . . N$
输出：最大间隔分离超平面和分类决策函数。
（1）构造并求解约束最优化问题：
$\underset{\omega,b}{max} \quad \frac{1}{2}{||\omega||}^2$
$\qquad y_i(w\cdot x_i+b)-1\geq 0 ，\quad i=1,2,...,N$
求得最优解： $w^*$ , $b^*$ 。
（2）由此得到分离超平面：
$\omega^*\cdot x+b^*=0$
分类决策函数
$f(x)=sign(\omega^*\cdot x+b^*)$

3、学习的对偶算法

为了求解上述线性可分支持向量机的最优化问题，将它作为原始最优化问题，应用拉格朗日对偶性，通过求解对偶问题得到原始问题的最优解，这就是线性可分支持向量机的对偶算法（dual algorithm）。
这样做的优点，一是对偶问题往往更容易求解；二是自然引入核函数，进而推广到非线性分类问题。

3.1、拉格朗日函数
假设 $f (x)$ , $c_i(x)$ , $h_j(x)$ 是定义在 $R^n$ 上的连续可微函数。考虑约束最优化问题
$\underset{x\in R^n}{min} \quad f(x)$
$\qquad c_i(x)\leq 0， \quad i=1,2,...,k$
$\qquad h_j(x)=0 ，j=1,2,...,l$
称此约束最优化问题为原始最优化问题或原始问题。引进广义拉格朗日函数：
$L(x,\alpha,\beta)=f(x)+\sum_{i=1}^{k} \alpha_i c_i(x)+\sum_{j=1}^{l}\beta_j h_j(x)$
这里， $x＝(x^{(1)},x^{(2)},…,x^{(n)})^T\in R^n$ , $\alpha_i$ , $\beta_j$ 是拉格朗日乘子， $\alpha_i≥0$ 。

3.2、求解线性可分支持向量机的最优化问题（对偶算法）
对每一个不等式约束 $y_i(w\cdot x_i+b)-1\geq 0$ 引进拉格朗日乘子 $\alpha_i\geq 0$ ， $i = 1, 2, . . ., N$ ,定义拉格朗日函数：
$L(\omega,b,\alpha)=\frac{1}{2}{||\omega||}^2+\sum_{i=1}^{N}\alpha_i (1-y_i(w\cdot x_i+b))$
其中， $\alpha=(\alpha_1,\alpha_2,...,\alpha_N)^T$ 为拉格朗日乘子向量。

根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题：
所以，为了得到对偶问题的解，需要先求 $L(\omega,b,\alpha)$ 对 $\omega,b$ 的极小，再求对 $\alpha$ 的极大。
（1）求 $\underset{\omega,b}{min} L(\omega,b,\alpha)$
将拉格朗日函数 $L(\omega,b,\alpha)$ 分别对 $\omega,b$ 求偏导数并令其等于0。
$\nabla_{\omega}{L(\omega,b,\alpha)}=\omega-\sum_{i=1}^{N} \alpha_i y_i x_i=0$
$\nabla_{b}{L(\omega,b,\alpha)}=\sum_{i=1}^{N} \alpha_iy_i=0$
得
$\omega=\sum_{i=1}^{N}\alpha_i y_i x_i$
$\sum_{i=1}^{N}\alpha_i y_i=0$
代入拉格朗日函数，即得
$\underset{\omega,b}{min} L(\omega,b,\alpha)=-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N}\alpha_i\alpha_j y_i y_j (x_i\cdot x_j) +\sum_{i=1}^{N}\alpha_i$
（2）求 $\underset{\omega,b}{min} L(\omega,b,\alpha)$ 对 $\alpha$ 的极大值，即是对偶问题
$\underset{\alpha}{max} \ -\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N}\alpha_i\alpha_j y_i y_j (x_i\cdot x_j) +\sum_{i=1}^{N}\alpha_i$
$\qquad \sum_{i=1}^{N}\alpha_i y_i=0$
$\qquad \alpha_i\geq0，i=1,2,...,N$
将上述目标函数由求极大转换成求极小，就得到下面与之等价的对偶最优化问题：
$\underset{\alpha}{min} \quad \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N}\alpha_i\alpha_j y_i y_j (x_i\cdot x_j) -\sum_{i=1}^{N}\alpha_i$
$\qquad \sum_{i=1}^{N}\alpha_i y_i=0$
$\qquad \alpha_i\geq0，i=1,2,...,N$
3.3、优化问题满足KKT条件
对线性可分训练数据集，假设对偶最优化问题对 $\alpha$ 的解为 $\alpha^*=(\alpha_1^*,\alpha_2^*,...,\alpha_N^*)^T$ ,可以由 $\alpha^*$ 求得原始最优化问题对 $(\omega^*,b^*)$ 的解 $\omega^*$ , $b^*$ 。
KKT条件如下：
$\nabla_{\omega}{L(\omega^*,b^*,\alpha^*)}=\omega^*-\sum_{i=1}^{N} \alpha_i^* y_i x_i=0$
$\nabla_{b}{L(\omega^*,b^*,\alpha^*)}=\sum_{i=1}^{N} \alpha_i^* y_i=0$
$\alpha_i^*(y_i(\omega^*\cdot x_i+b^*)-1)=0，i=1,2,...,N$
$y_i(\omega^*\cdot x_i+b^*)-1\geq 0，i=1,2,...,N$
$\alpha_i^*\geq 0$
由此得
$\omega^*=\sum_{i=1}^{N}\alpha_i^* y_i x_i$
其中至少有一个 $\alpha^*>0$ ，对此 $j$ 有
$y_j(\omega^*\cdot x_j+b^*)-1=0$
又 $y_j^2=1$ ，即得
$b^*=y_j-\sum_{i=1}^{N}\alpha_i^* y_i(x_i\cdot x_j)$
3.4、线性可分支持向量机学习算法
输入：线性可分训练数据集分类决策函数 $T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$ ，其中， $x_i\in\chi=R^n$ ， $y_i\in\Upsilon=\{+1,-1\}$ ， $i = 1, 2, . . . N$
输出：最大间隔分离超平面和分类决策函数。
（1）构造并求解约束最优化问题：
$\underset{\alpha}{min} \quad \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N}\alpha_i\alpha_j y_i y_j (x_i\cdot x_j) -\sum_{i=1}^{N}\alpha_i$
$\quad \sum_{i=1}^{N}\alpha_i y_i=0$
$\alpha_i\geq0，i=1,2,...,N$
求得最优解 $\alpha^*=(\alpha_1^*,\alpha_2^*,...,\alpha_N^*)^T$
（2）计算
$\omega^*=\sum_{i=1}^{N}\alpha_i^* y_i x_i$
并选择 $\alpha^*$ 的一个正分量 $\alpha_j^*>0$ ，计算
$b^*=y_j-\sum_{i=1}^{N}\alpha_i^* y_i(x_i\cdot x_j)$
（3）求得分离超平面
$\omega^*\cdot x+b^*=0$
分类决策函数：
$f(x)=sign(\omega^*\cdot x+b^*)$