支持向量机/SVM（Support Vector Machine）

作者 : 开心源码本文共1738个字，预计阅读时间需要5分钟发布时间： 2022-05-12 共106人阅读

SVM，曾经是最为流行的机器学习算法，可以使用于分类问题、回归问题及异常点检测问题。不仅如此，SVM的算法动机可以通过计算学习理论或者者统计学习理论进行了解，使其有充分的理论保障。

算法释义

对于二分类问题，相似于感知机，SVM 算法要寻觅特征空间中的一个超平面将正反样本分开，但是SVM需要寻觅一个唯一的超平面使得离该平面最近的点的距离最大，也就是说 SVM 的解相当于感知机的解空间中泛化误差最小解。

重要概念

这里首先以硬间隔的二分类 SVM 详情，而后将其推广到软间隔分类、多分类和回归 SVM 。

函数间隔和几何间隔

函数间隔就是特征空间中点到超平面的距离，即：
$margin_f(x) = y(w^Tx + b)$
我们知道对于同一个超平面，可能有不同的表示，因而即便对于同一个超平面，不同的 w 的取值也会造成不同的函数间隔的值，所以我们需要用一个更能反映真是距离的变量，这里我们引入几何间隔的概念：
$margin_g(x) = \frac {y(w^Tx + b)} {||w||}$
通过使函数间隔除以 w 向量的二范数，几何间隔只和超平面和特征空间中的点有关，和超平面的表示方式无关。

SVM 基本形式

首先确定假设空间，即线性二元分类器：
$f(x) = sign(w^Tx + b)$

使用 margin_min 表示训练样本中离超平面最小的几何间隔，要使最小的几何间隔最大，相当于求下列函数：
$arg \max_{w} \left(\min_n { \frac {y(w^Tx_n + b)} {||w||}} \right)$

因为最小化问题与 ||w|| 的取值无关，可以将上式中的 ||w|| 提出：
$arg \max_{w} \left( \frac 1 {||w||} \min_n { {y(w^Tx_n + b)} } \right)$

内层的最小化问题就变成了最小化函数间隔，这里固定最小化之后的函数间隔为 1，从而原问题变为：
$\begin{align} &arg \max_{w} \frac 1 {||w||} \\ &s.t.\,\, y(w^Tx_n + b) ≥ 1, n = 1,2,...,N \end{align}$

按照通常习惯，把最大化问题改为最小化问题，为了便于求解，把二范数改为向量內积，最终得到 SVM 模型的基本形式，即：
$\begin{align} &arg \min_{w} \frac 1 2 w^Tw \\ &s.t.\,\, y_n(w^Tx_n + b) ≥ 1, n = 1,2,...,N \end{align}$

SVM 对偶形式

利使用拉格朗日乘子，把带条件的最优化问题，转变为不带条件的最优化问题，而后根据拉格朗日对偶性，得到极小极大问题的对偶形式，即极大极小问题（要使两个问题的解相等，那么要使解满足 KTT 条件）：
$\begin{align} &L(w, b, α) = \frac 1 2 w^Tw + \sum_{n=1}^N {α_n(1 - y_n(w^Tx_n + b))}, \\ &\min_{w,b} \max_{α} L(w, b, α) \\ &\max_{α} \min_{w,b} L(w, b, α) \end{align}$

对于内层的极小问题，令其对 w 和 b 的导数分别等于零，从而求得内层极小问题的解：
$\begin{align} & \nabla_w L(w, b, α) = w - \sum_{n=1}^N α_ny_nx_n = 0 \\ & \nabla_b L(w, b, α) = -\sum_{n=1}^N α_ny_n = 0 \\ & 解得：\\ & w = \sum_{n=1}^N α_ny_nx_n \\ & \sum_{n=1}^N α_ny_n = 0 \\ & 带入极大极小问题，然后加负号把最大化问题变为最小化问题：\\ & \min_{α} {\frac 1 2 \sum_{i=1}^N \sum_{j=1}^N α_iα_jy_iy_jx_i^Tx_j - \sum_{n=1}^Nα_n} \\ & s.t. \,\, \sum_{n=1}^N α_ny_n = 0 \\ & \,\,\,\,\,\,\,\,\,\,\,\, α_n≥0, n=1,2,...,N \end{align}$

KTT 条件

对于束缚最优化问题，其一般形式是：
$\begin {align} & \min_x f(x) \\ & s.t. \,\, c_i(x) ≤ 0, i=1,2,...,k \\ & \,\,\,\,\,\,\,\,\,\,\,\, h_j(x) = 0, j=1,2,...,l \end {align}$

加上拉格朗日乘子变成无束缚的最优化问题：
$\begin{align} &L(x, α, β) = f(x) + \sum_{i=1}^k {α_ic_i(x)} + \sum_{j=1}^l {β_jh_j(x)}, 其中α_i ≥ 0\\ &\min_{x} \max_{α, β} L(x, α, β) \\ &\max_{α, β} \min_{x} L(x, α, β) \end{align}$

上述极小极大问题的解要和极大极小问题的解一样，需要满足 KTT 条件：
$\begin{align} & \nabla_{x^*} L(x^*, α^*, β^*) = 0 \\ & α_i^*c_i(x^*) = 0, i=1,2,...,k \\ & c_i(x^*) ≤ 0, i=1,2,...,k \\ & α_i^* ≥ 0, i=1,2,...,k \\ & h_j(x^*) = 0, j=1,2,...,l \\ \end{align}$

在 SVM 中 KTT 条件即：
$\begin{align} & α_i^*(1-y_i(w^{*T}x_i + b)) = 0, i=1,2,...,N \\ & 1-y_i(w^{*T}x_i + b) ≤ 0, i=1,2,...,N \\ & α_i^* ≥ 0, i=1,2,...,N \\ \end{align}$

SVM 学习算法

(1) 构造求解束缚最优化问题：
$\begin{align} & \min_{α} {\frac 1 2 \sum_{i=1}^N \sum_{j=1}^N α_iα_jy_iy_jx_i^Tx_j - \sum_{n=1}^Nα_n} \\ & s.t. \,\, \sum_{n=1}^N α_ny_n = 0 \\ & \,\,\,\,\,\,\,\,\,\,\,\, α_n≥0, n=1,2,...,N \end{align}$

(2) 通过 α 的解求出 w, b 的解：
$\begin{align} & w^* = \sum_{n=1}^N α^*_ny_nx_n \\ & 根据\,KTT\,条件，选择α^*一个不为零的分量α^*_j > 0：\\ & b^* = y_j - w^*x_j = y_i - \sum_{n=1}^N α^*_ny_nx_n^Tx_j \end{align}$

(3) 求得分类决策函数：
$f(x) = sign(w^{*T}x + b^*)$

核函数

对于线性可分的问题，我们可以直接用原始的 SVM 进行分类，但是很多时候训练集数据是线性不可分的，这个时候我可以考虑用特征转换，把输入特征空间通过映射函数 Φ 映射到另一个特征空间：
$\phi(x)： X \rightarrow H$
然而很多时候寻觅一个合适的映射函数 Φ 是很困难的，而且寻觅到 Φ 之后还需要先做特征转换，再求转换后的特征的内积，那有没有更简单的办法呢？首先定义核函数：
$\kappa(x_i, x_j) = \phi(x_i) · \phi(x_j)$
我们能不能在只有核函数 κ 不知道映射函数 Φ 的情况下，求 SVM 呢？注意看我们求解特征转换后的 SVM 的形式：
$\begin{align} & \min_{α} {\frac 1 2 \sum_{i=1}^N \sum_{j=1}^N α_iα_jy_iy_j \kappa(x_i, x_j) - \sum_{n=1}^Nα_n} \\ & s.t. \,\, \sum_{n=1}^N α_ny_n = 0 \\ & \,\,\,\,\,\,\,\,\,\,\,\, α_n≥0, n=1,2,...,N \end{align}$

而且解出来的分类决策函数：
$f(x) = sign( \sum_{n=1}^N α^*_ny_n \kappa(x_n, x) + b^*)$

不难发现，上述过程中映射函数 Φ 仿佛消失了，那是不是说明我们只要要定义一个核函数，即可以解 SVM 了呢？其实不然，由于我们还要保证这样的核函数是能够映射的，换句话说，必需要存在某种映射关系使得该核函数存在。而这种保证的充要条件就是核函数必需为正定核，这里就不开展了。
常见的核函数有
(1) 多项式核函数( p 次多项式核)：
$\kappa(x_i, x_j) = (x_i^Tx_j + 1)^p$
(2) 高斯核函数：
$\kappa(x_i, x_j) = e^{-\frac {||x_i - x_j||^2} {2σ^2} }$

SVM 推广

软间隔的 SVM

有时候训练集数据近似线性可分但是不是线性可分的，也有的时候由于噪点的存在，使得 SVM 的结果存在过拟合，这个时候即可以用软间隔的 SVM，所谓软间隔，就是在原始 SVM 的假设上稍稍放宽其限制条件，让某些点的函数间隔可以小于1，即在束缚条件上加一个松弛变量：
$y_n=(w^Tx_n+b) ≥ 1 - ξ_n$

这里 ξ_n ≥ 0，而后对于每一个松弛变量，支付一个代价 ξ_n，故将目标函数变为：
$\frac 1 2 w^Tx + C \sum_{n=1}^N ξ_n$

从而，软间隔的 SVM 有如下基本形式：
$\begin{align} &arg \min_{w} \frac 1 2 w^Tw + C \sum_{n=1}^N ξ_n \\ &s.t.\,\, y_n(w^Tx_n + b) ≥ 1 - ξ_n, n = 1,2,...,N \\ & \,\,\,\,\,\,\,\,\,\,\,\, ξ_n ≥ 0, n = 1,2,...,N \end{align}$

将其转换为拉格朗日对偶问题，有：
$\begin{align} & \min_{α} {\frac 1 2 \sum_{i=1}^N \sum_{j=1}^N α_iα_jy_iy_jx_i^Tx_j - \sum_{n=1}^Nα_n} \\ & s.t. \,\, \sum_{n=1}^N α_ny_n = 0 \\ & \,\,\,\,\,\,\,\,\,\,\,\, C≥α_n≥0, n=1,2,...,N \end{align}$

在软间隔 SVM 中 KTT 条件为：
$\begin{align} & α_i^*(1-y_i(w^{*T}x_i + b) - ξ_i) = 0, i=1,2,...,N \\ & 1-y_i(w^{*T}x_i + b) - ξ_i ≤ 0, i=1,2,...,N \\ & α_i^* ≥ 0, i=1,2,...,N \\ \end{align}$

多分类 SVM

One versus the rest （一对剩余）
假如有 K 个类别，那么训练 K 个二分类 SVM 分类器，而后综合这 K 个训练器的预测结果给出预测
One versus one （一对一）
假如有 K 个类别，那么每两个类的样本和到一块训练 1 个二分类 SVM 分类器，一共 K (K – 1) / 2个分类器，而后综合这些训练器的预测结果给出预测

回归 SVM

pass

参考文献

《Pattern Recognition and Machine Learning》，Bishop

说明
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是摆设，本站源码仅提供给会员学习使用！
7. 如遇到加密压缩包，请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 支持向量机/SVM（Support Vector Machine）

分享到：