支持向量机/SVM（Support Vector Machine

作者: 大雄的学习人生 | 来源:发表于2018-08-23 23:59 被阅读216次

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

支持向量机/SVM（Support Vector Machine

算法释义

重要概念

函数间隔和几何间隔

SVM 基本形式

SVM 对偶形式

KTT 条件

SVM 学习算法

核函数

SVM 推广

软间隔的 SVM

多分类 SVM

回归 SVM

参考文献

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

Web前端之路

机器学习