SVM

概述

支持向量机（Support Vector Machine）是一个分类算法，主要思想是间隔最大化。推导过程中将间隔最大化转化为带约束条件的凸优化问题，通过引入拉格朗日乘子法和对偶学习法来简化该优化问题，最后转为为拉格朗日乘子的带约束条件的优化问题。在整个推导过程中由于引入对偶学习很自然的引入了核方法。最后的优化问题通过SMO算法解决。

线性可分支持向量机

对于线性可分数据集，一定存在将数据集完全分离的超平面，假设某分离超平面是 $y=w^Tx+b$ ，某个数据点 $(x_i, y_i)$ 到超平面的函数距离为 $\hat{r_i}=|w^Tx_i+b| =y_i(w^Tx_i+b)$ ,当超平面和数据点确定时，超平面可由无数对（w,b）确定，函数距离会随着w，b的变化而变化，引入几何距离 $r_i=\frac{|w^Tx_i+b|}{||w||}=\frac{\hat{r_i}}{||w||}$ ，几何距离不随着（w,b）的变化变化。定义数据点到超平面的几何距离为 $r=\min_{i} r_i =\min_{i}\frac{\hat{r_i}}{||w||}$ .

SVM的思想是最大化数据点到超平面的距离，即 $\max_{w,b}r\\s.t. r_i\geq r, for \ i=1,2 \ldots n$

即

$\max_{w,b}\frac{\hat{r}}{||w||}\\s.t. \hat{r_i}\geq \hat{r}, for \ i=1,2 \ldots n$

因为平面和点固定时函数距离可取任意非负值，令 $\hat{r}=1$ 不会改变上面的优化问题，得

$\max_{w,b}\frac{1}{||w||}\\s.t. \hat{r_i}\geq 1, for\ i=1,2 \ldots n$

最大化 $\frac{1}{||w||}$ 等价于最小化 $\frac{1}{2}||w||^2$ ,得

$\min_{w,b}\frac{1}{2}||w||^2\\s.t. y_i(w^Tx_i+b)\geq 1, for\ i=1,2 \ldots n$

得到上面最优化问题的解 $(w^*, b^*)$ 后，间隔最大的分离超平面就是 $y={w^*}^Tx+b^*$ .

可以通过Lagrange Multiplier解上述问题，Lagrange Function为

$L(w,b,\alpha)=\frac{1}{2}||w||^2-\sum_{i=1}^n\alpha_i[y_i(w^Tx_i+b)-1]\\ s.t.\alpha_i\geq0, for \ i=1,2\ldots,n$

令 $\theta =\max_{\alpha, \alpha \geq0} L(w,b,\alpha)=\max_{\alpha, \alpha \geq0} \{\frac{1}{2}||w||^2-\sum_{i=1}^n\alpha_i[y_i(w^Tx_i+b)-1]\}$ ,可知在满足约束条件的情况下 $\theta =\frac{1}{2}||w||^2$ (如果有某个数据点违反了约束条件，即 $y_i(w^Tx_i+b)-1<0$ ),那么 $\theta$ 无穷大），优化问题变为

$\min_{w,b}\theta =\min_{w,b}\max_{\alpha, \alpha \geq0} L(w,b,\alpha)=\min_{w,b}\max_{\alpha, \alpha \geq0} \{\frac{1}{2}||w||^2-\sum_{i=1}^n\alpha_i[y_i(w^Tx_i+b)-1]\}=P^*$

该问题称为原始问题,对偶问题为

$\max_{\alpha, \alpha \geq0}\min_{w,b} L(w,b,\alpha)=\max_{\alpha, \alpha \geq0}\min_{w,b}\{\frac{1}{2}||w||^2-\sum_{i=1}^n\alpha_i[y_i(w^Tx_i+b)-1]\}=Q^*$ ，

且有 $Q^*\leq P^*$ .

最优化问题满足Slater条件即存在 $x_i$ 使得不等式严格成立，所以 $Q^*= P^*$ ，可以通过求解对偶问题来获得原始问题的解。

K.K.T条件是 $Q^*= P^*$ 的充分必要条件，表达为

$\triangledown_wL(w^*,b^*,\alpha^*)=0\\ \triangledown_bL(w^*,b^*,\alpha^*)=0\\ \triangledown_\alpha L(w^*,b^*,\alpha^*)=0\\ \alpha_i(y_i(w^Tx_i+b)-1)=0,for\ i=1,2\ldots,n\\ \alpha_i\geq0,for\ i=1,2\ldots,n\\ y_i(w^Tx_i+b)-1 \geq 0, for\ i=1,2\ldots,n$

求解 $\min_{w,b}L(w,b,\alpha)$ ,对w,b求偏导，有

$\frac{dL(w,b,\alpha)}{dw}=w-\sum_{i=1}^n\alpha_iy_ix_i =0$

$\frac{dL(w,b,\alpha)}{db}=-\sum_{i=1}^n\alpha_iy_i =0$

即

$w=\sum_{i=1}^n\alpha_iy_ix_i\\\sum_{i=1}^n\alpha_iy_i=0$

有

$\begin{align*}\min_{w,b} L(w,b,\alpha)&=\min_{w,b}\{\frac{1}{2}||w||^2-\sum_{i=1}^n\alpha_i[y_i(w^Tx_i+b)-1]\}\\&=\frac{1}{2}w^T(\sum_{i=1}^n\alpha_iy_ix_i)-w^T\sum_{i=1}^n\alpha_iy_ix_i -\sum_{i=1}^n\alpha_iy_ib+\sum_{i=1}^n\alpha_i \\&=\sum_{i=1}^n\alpha_i-\frac{1}{2}w^T(\sum_{i=1}^n\alpha_iy_ix_i)\\&=\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j(x_i\cdot x_j) \\&s.t. \sum_{i=1}^n\alpha_iy_i=0\\&\alpha_i\geq0, for \ i=1,2,\ldots, n\end{align*}$

优化问题变为

$\max_{\alpha}\sum_{i=1}^n\alpha_i-\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j(x_i\cdot x_j) \\s.t. \sum_{i=1}^n\alpha_iy_i=0\\\alpha_i\geq0, for \ i=1,2,\ldots, n$

该优化问题可以通过SMO有效求解。假设得到的最优解为 $\alpha^*$ ,则

$w^*=\sum_{i=1}^n\alpha^*_iy_ix_i=\sum_{i,\alpha^*_i\gt0}\alpha^*_iy_ix_i$

通过kkt条件， $b^*=\frac{1}{y_j}-{w^*}^Tx_j=y_j-\sum_{i=1}^n\alpha^*_iy_i(x_i\cdot x_j),for\ some\ \alpha^*_j\gt0$

分离超平面为 $y={w^*}^Tx+b^*=\sum_{i,\alpha^*_i\gt0}\alpha^*_iy_i(x_i\cdot x)+b^*$

通过推导过程可知，如果 $\alpha_i\gt 0$ ,则 $y_i(w^Tx_i+b)=1$ ，对应的实例 $x_i$ 是支持向量，位于间隔边界上。如果 $\alpha_i=0$ ，则实例 $x_i$ 位于正确分类的间隔边界外。

线性支持向量机

线性可分支持向量机不能处理线性不可分数据集，因此引入线性支持向量机。线性支持向量机在线性可分支持向量机的基础上引入松弛变量 $\xi$ 来处理离异点。

最优化问题变为

$\min_{w,b}\frac{1}{2}||w||^2+C\sum_{i=1}^n\xi_i\\ s.t.\ y_i(w^Tx_i+b)\geq 1-\xi_i, for \ i=1,2\ldots,n \\ \xi_i\geq 0, for \ i=1,2\ldots,n$

其中 $\sum_{i=1}^n\xi_i$ 是离异点偏差量的惩罚，C是常数超参，用来控制“间隔最大化”和“离异点偏差量最小”。

Lagrange function为

$L(w,b,\xi,\alpha,\beta)=\frac{1}{2}||w||^2+C\sum_{i=1}^n\xi_i-\sum_{i=1}^n\alpha_i(y_i(w^Tx_i+b) - (1-\xi_i))-\sum_{i=1}^n\beta_i\xi_i \\ s.t.\ \alpha_i\geq0, for \ i=1,2,\ldots,n\\\beta_i\geq0, for \ i=1,2,\ldots,n$

使用对偶学习法，先求内层最小化。L对w,b,\xi求导，有

$\frac{dL}{dw}=w-\sum_{i=1}^n\alpha_iy_ix_i=0\\ \frac{dL}{db}=-\sum_{i=1}^n\alpha_iy_i=0 \\ \frac{dL}{d\xi_i}=C-\alpha_i-\beta_i=0$

即

$w=\sum_{i=1}^n\alpha_iy_ix_i\\ \sum_{i=1}^n\alpha_iy_i=0\\ C -\alpha_i-\beta_i=0, for \ i=1,2,\ldots, n$

所以外层最大化的函数为

$\begin{align*}L(w,b,\xi,\alpha,\beta)&=\frac{1}{2}||w||^2+C\sum_{i=1}^n\xi_i-\sum_{i=1}^n\alpha_i(y_i(w^Tx_i+b) - (1-\xi_i))-\sum_{i=1}^n\beta_i\xi_i \\ &=\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+C\sum_{i=1}^n\xi_i-\sum_{i=1}^n\alpha_i\xi_i-\sum_{i=1}^n\beta_i\xi_i\\&=\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^n(C-\alpha_i-\beta_i)\xi_i\\\&=\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)\end{align*}\\ s.t. \sum_{i=1}^n\alpha_iy_i=0\\ \alpha_i\geq0, for \ i=1,2,\ldots,n\\ \beta_i\geq0, for \ i=1,2,\ldots,n\\C-\alpha_i-\beta_i=0, for \ i=1,2,\ldots,n$

约束条件可简化为

$\sum_{i=1}^n\alpha_iy_i=0\\0\leq\alpha_i\leq C, for \ i=1,2,\ldots,n$

解决该最优化问题后得到最优解 $\alpha^*$ ,则

$w^*=\sum_{i=1}^n\alpha^*_iy_ix_i=\sum_{i,\alpha^*_i\gt0}\alpha^*_iy_ix_i$

通过kkt条件， $b^*=\frac{1}{y_j}-{w^*}^Tx_j=y_j-\sum_{i=1}^n\alpha^*_iy_i(x_i\cdot x_j),for\ some\ 0 \lt\alpha^*_j\lt C$

最后得到分离超平面 $y={w^*}^Tx+b^*$

软间隔的支持向量在：间隔边界，间隔边界和分离超平面之间或分离超平面误分一侧。如果 $\alpha_i=0$ ,实例位于正确分类的间隔边界外；如果 $0\lt \alpha_i\lt C$ ,则 $\beta_i\gt0$ , $\xi_i=0$ , $y_i(w^Tx_i+b)=1$ ,实例刚好在间隔边界上，是支持向量；若 $\alpha_i=C$ ,则 $\beta=0$ , $\xi_i\gt0$ ,如果 $\xi_i<1$ ,实例位于分离超平面和间隔边界之间，如果 $\xi_i=1$ ,实例位于分离超平面上，如果 $\xi_i\gt1$ ，实例位于分离超平面误分一侧,都属于支持向量。

合页损失(hinge loss)函数： $Loss(x, y)=[k-distance(x, plane)]_+$ ,如果x到分离超平面的距离小于k，损失为两者的差，大于等于k时，为0.确保当距离足够大(k)时损失才为0.

从损失函数的角度看，支持向量机可看作是模型是 $y=sign(w^Tx+b)$ ,损失函数为

$Loss(x, y|w, b)=\sum_{i=1}^n[1-y_i(w^Tx_i+b)]_++\lambda ||w||^2$

的分类模型，损失函数第一项是经验损失，可以理解为当实例被正确划分且确信度够高（实例到分离超平面的距离大于等于1）时损失为0，否则损失为 $1-y(w^Tx+b)$ 。损失函数第二项是权重为 $\lambda$ 的正则项，w的 $L_2$ 范数。可以证明该损失函数与原来的最优化问题等价。令 $\xi_i\gt0,[1-y_i(w^Tx_i+b)]_+=[\xi_i]_+=\xi_i$ ,有

$Loss(x, y|w, b)=\sum_{i=1}^n\xi_i+\lambda||w||^2$

取 $\lambda=\frac{1}{2C}$ ,得到原来的最优化问题。

注：损失函数中第一项用函数距离是因为简单。假设超平面不变，成比例的增大w,b,损失函数会增大；成比例的减小w,b,对于正确分类的点损失函数可能会增大，错误分类的点损失函数会减小，此时最小距离有下界1，因此在某个临界的w,b后，成比例的减小w，b损失函数不会变小，需要改变超平面。效果和使用几何距离一样。

非线性支持向量机

在前面对偶学习法的推导中我们发现最优化的目标函数和决策函数都只涉及实例间的内积，因此可以用核方法替代这个内积，从而将输入空间扩展到更高维的特征空间，来处理更复杂的线性不可分数据集。

目标函数变为

$\max_{\alpha}\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_jK(x_i, x_j)$

决策函数变为

$f(x)=sign(\sum_{i,\alpha^*_i\gt0}\alpha^*_iy_iK(x_i, x)+b^*)$

这样做的思路是通过一个非线性变换将输入空间转换到特征空间，使输入空间线性不可分的数据在特征空间中线性可分，从而可以使用前面的线性支持向量机来解决问题。上面两个式子中，原来的 $(x_i\cdot x)$ 用 $K(x_i,x)$ 替换了，相当于隐式地将 $x_i$ 和 $x$ 转换到更高维的特征空间再计算内积，在这个特征空间里数据集可能是线性可分的。

SMO

【待更新】

最后编辑于：2018.12.13 12:15:38

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

SVM

概述

线性可分支持向量机

线性支持向量机

非线性支持向量机

SMO

推荐阅读更多精彩内容