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

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

最后编辑于：2019.01.02 19:49:59

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 213,752评论 6赞 493
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 91,100评论 3赞 387
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 159,244评论 0赞 349
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,099评论 1赞 286
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,210评论 6赞 385
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,307评论 1赞 292
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,346评论 3赞 412
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,133评论 0赞 269
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,546评论 1赞 306
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,849评论 2赞 328
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,019评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,702评论 4赞 337
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,331评论 3赞 319
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,030评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,260评论 1赞 267
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,871评论 2赞 365
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,898评论 2赞 351