十三、支持向量机SVM

SVM（Support Vector Machines）

近年已被深度学习所替代

SVM寻找区分两类的超平面（hyper plane），使边际（margin）最大

向量内积： $x.y = x_1y_1+x_2y_2+...+x_ny_n$

$x.y = ||x||||y||cos(\theta)$

范数： $||x|| = \sqrt{x.x} = \sqrt{x_1^2+x_2^2+..+x_n^2}$

当 $||x||\neq 0$ 时，可以求余弦相似度： $cos(\theta) = \frac{x.y}{||x||||y||}$

$w.x_1+b=1$

$w.x_2+b=-1$

$w.(x_1-x_2) = 2$

$||w||||x_1-x_2||cos(\theta) = 2$

$||w||*d = 2$

$d = \frac{2}{||w||}$

算法推论：

转化为凸优化问题：

$w.x+b\geq 1,则分类\ y=1$

$w.x+b \leq -1,则分类\ y=-1$

——》 $y(w.x+b)\geq 1$ ，求 $d = \frac{2}{||w||}$ 最大值，即求 $min \frac{||w||^2}{2}$

而凸优化问题一般有三种情况：

1、无约束优化问题： $min(f(x))$ 费马定理

2、带等式约束的优化问题： $minf(x)$

-拉格朗日乘子法：

s.t. $h_i(x) = 0, \ \ \ i=1,2,...,n$

$L(x,\lambda) = f(x)+\sum_{i=1}^{n}\lambda_ih_i(x)$

3、带不等式约束的优化问题： $minf(x)$

-KKT条件

s.t. $h_i(x) = 0,\ \ \ \ i=1,2,...,n$

$g_i(x)\leq 0,\ \ \ \ i=1,2,...,k$

$L(x,\lambda,v) = f(x)+\sum_{i=1}^{k}\lambda_ig_i(x)+\sum_{i=1}^{n}v_ih_i(x)$

而算法是在 $y(w.x+b)\geq 1$ 的条件下求 $min \frac{||w||^2}{2}$

实际上 $min \frac{||w||^2}{2}$ 存在时， $y(w.x+b)$ 取1，即属于第2种情况

广义拉格朗日乘子法：

$L(w,b,a) = \frac{1}{2}||w||^2 - \sum_{i=1}^{n} \alpha_i(y_i(w^Tx_i + b)-1)$

$\frac{\partial L}{\partial w} = 0 \rightarrow w = \sum_{i=1}^{n} \alpha_iy_ix_i$

$\frac{\partial L}{\partial b} = 0 \rightarrow \sum_{i=1}^{n} \alpha_iy_i = 0$

而KKT条件（Karush-Kuhn-Tucker最优化条件）

是拉格朗日乘子法的一种推广，可以处理有不等号的约束条件

进一步简化为对偶问题

$L(w,b,\alpha) = \frac{1}{2}||w||^2 - \sum_{i=1}^{n} \alpha_i(y_i(w^Tx_i + b)-1)$

上述问题可以改写成：

$min_{w,b}\ max_{a_i\geq 0}\ L(w,b,\alpha) = p^*$

可以等价为下列对偶问题：

$max_{a_i\geq 0}\ min_{w,b}\ L(w,b,\alpha) = d^*$

$L(w,b,\alpha) = \frac{1}{2}||w||^2 - \sum_{i=1}^{n} \alpha_i(y_i(w^Tx_i + b)-1)$

$\frac{\partial L}{\partial w} = 0 \rightarrow w = \sum_{i=1}^{n} \alpha_iy_ix_i$

$\frac{\partial L}{\partial b} = 0 \rightarrow \sum_{i=1}^{n} \alpha_iy_i = 0$

消除w，b——

$L(w,b,\alpha) = \sum_{i=1}^{n}\alpha_i - \frac{1}{2}\sum_{i,j=1}^{n}\alpha_i\alpha_jy_iy_jx_i^Tx_j$

$max_{\alpha_i\geq 0}\ min_{w,b}\ L(w,b,\alpha) = max_\alpha\ [\sum_{i=1}^{k}\alpha_i - \frac{1}{2}\sum_{i,j=1}^{k}\alpha_i\alpha_jy_iy_jx_i^Tx_j]$

s.t. $\sum_{i=1}^{k}\alpha_iy_i = 0,\ \ \ \alpha_i \geq 0,i=1,2,...,n$

$min_\alpha[\frac{1}{2}\sum_{i,j=1}^{k}\alpha_i\alpha_jy_iy_jx_i^Tx_j - \sum_{i=1}^{k}\alpha_i] = min_\alpha[\frac{1}{2}\sum_{i,j=1}^{k}\alpha_i\alpha_jy_iy_j(x_i.x_j) - \sum_{i=1}^{k}\alpha_i]$

s.t. $\sum_{i=1}^{k}\alpha_iy_i = 0,\ \ \ \alpha_i \geq 0,i=1,2,...,n$

由此可得最优解 $\alpha^*$ ，带入后得

$w^* = \sum_{i=1}^{n}\alpha_i^*y_ix_i,\ \ \ \ b^* = y_i-(w^*)^Tx_i$

SMO算法

针对线性SVM和稀疏数据时性能更优

$min_\alpha[\frac{1}{2}\sum_{i,j=1}^{k}\alpha_i\alpha_jy_iy_jx_i^Tx_j - \sum_{i=1}^{k}\alpha_i] = min_\alpha[\frac{1}{2}\sum_{i,j=1}^{k}\alpha_i\alpha_jy_iy_j(x_i.x_j) - \sum_{i=1}^{k}\alpha_i]$

s.t. $\sum_{i=1}^{k}\alpha_iy_i = 0,\ \ \ \alpha_i \geq 0,i=1,2,...,n$

s.t. $C\geq \alpha_i \geq 0,\ \ \ i=1,2,...,n$

基本思路是先根据约束条件随机给 $\alpha$ 赋值，然后每次选举两个 $\alpha$ ，调节这两个 $\alpha$ 使得目标函数最小。然后再选取两个 $\alpha$ ，调节 $\alpha$ 使得目标函数最小。以此类推

线性不可分的情况

引入松弛变量与惩罚函数

松弛变量 $\varepsilon$

$y_i(w_i.x_i+b)\geq 1-\varepsilon _i,\ \ \varepsilon _i\geq 0$

约束条件没有体现错误分类的点要尽量接近分类边界

惩罚函数 $C\sum_{i=1}^{n}\varepsilon _i$

$min\frac{||w||^2}{2}+C\sum_{i=1}^{n}\varepsilon _i$

使得分错的点越少越好，距离分类边界越近越好

线性不可分下的对偶问题：

——》 $min_\alpha[\frac{1}{2}\sum_{i,j=1}^{k}\alpha_i\alpha_jy_iy_jx_i^Tx_j - \sum_{i=1}^{k}\alpha_i] = min_\alpha[\frac{1}{2}\sum_{i,j=1}^{k}\alpha_i\alpha_jy_iy_j(x_i.x_j) - \sum_{i=1}^{k}\alpha_i]$

s.t. $\sum_{i=1}^{k}\alpha_iy_i = 0,\ \ \ \alpha_i \geq 0,i=1,2,...,n$

s.t. $C\geq \alpha_i \geq 0,\ \ \ i=1,2,...,n$

eg：

可知目标函数为： $min_\alpha f(\alpha)$ ， s.t. $\alpha_1+\alpha_2 - \alpha_3=0$ ， $\alpha_i\geq 0,i=1,2,3$

其中 $f(\alpha) = \frac{1}{2}\sum_{i,j=1}^{3}\alpha_i\alpha_jy_iy_j(x_i.x_j) - \sum_{i=1}^{3}\alpha_i$

$=\frac{1}{2}(18\alpha_1^2+25\alpha_2^2+2\alpha_3^2+42\alpha_1\alpha_2 - 12\alpha_1\alpha_3-14\alpha_2\alpha_3) - \alpha_1-\alpha_2-\alpha_3$

然后，将 $\alpha_3 = \alpha_1+\alpha_2$ 带入目标函数，得到一个关于 $\alpha_1$ 和 $\alpha_2$ 的函数

$S(\alpha_1,\alpha_2) = 4\alpha_1^2+\frac{13}{2}\alpha_2^2+10\alpha_1\alpha_2-2\alpha_1-2\alpha_2$

对 $\alpha_1，\alpha_2$ 求偏导，并令其为0

可知 $S(\alpha_1,\alpha_2)$ 在（1.5，-1）处取极值

而（1.5，-1）不满足 $\alpha_i\geq 0$ 的约束条件，可推断最小值在边界上达到

经计算，

当 $\alpha_1=0$ 时， $S(\alpha_1=0,\alpha_2=\frac{2}{13})=-0.1538$

当 $\alpha_2=0$ 时， $S(\alpha_1=\frac{1}{4},\alpha_2=0)=-0.25$

所以， $S(\alpha_1,\alpha_2)$ 在 $\alpha_1=\frac{1}{4},\alpha_2=0$ 时取最小值

此时可算出 $\alpha_3 = \alpha_1+\alpha_2=\frac{1}{4}$

所以， $\alpha_1,\alpha_3$ 不等于0，所以对应点 $x_1$ 和 $x_3$ 就应该是支持向量

进而

$w^* = \sum_{i=1}^{3}\alpha_i^*y_ix_i = \frac{1}{4}*(3,3)-\frac{1}{4}*(1,1)=(\frac{1}{2},\frac{1}{2})$

即 $w_1 = w_2 = 0.5$ 。进而有

$b^* = 1-(w_1,w_2).(3,3)=-2$

因此最大间隔分类超平面为

$\frac{1}{2}x_1+\frac{1}{2}x_2-2=0$

分类决策函数为

$f(x) = sign(\frac{1}{2}x_1+\frac{1}{2}x_2-2)$

非线性的情况

把低维空间的非线性问题映射到高维空间，变成求解线性问题

映射举例：

3维输入向量 $x=(x_1,x_2,x_3)$

转化到6维空间 $Z$ 中去：

$\phi _1(x) = x_1,\phi _2(x) = x_2,\phi _3(x) = x_3,$

$\phi _4(x) = (x_1)^2,\phi _5(x) = x_1x_2\ and\phi _3(x) = x_1x_3$

新的决策超平面 $d(Z) = WZ+b$ ，其中 $W$ 和 $Z$ 是向量，这个超平面是线性的，解出 $W$ 和 $b$ 之间，并且带回原方程

$d(Z) = W_1x_1+W_2x_2+W_3x_3+W_4(x_1)^2+W_5x_1x_2+W_6x_1x_3+b$

$=W_1Z_1+W_2Z_2+W_3Z_3+W_4Z_4+W_5Z_5+W_6Z_6+b$

存在的问题：

1、维度灾难

2、如何选择合理的非线性转换

核函数

我们可以构造核函数使得运算结果等同于非线性映射，同时运算量要远远小于非线性映射

$K(x_i,x_j) = \phi (x_i).\phi (x_j)$

h次多项式核函数： $K(x_i,x_j) =(x_i,x_j+1)^h$

高斯径向基函数核函数： $K(x_i,x_j) =e^{\frac{-||x_i-x_j||^2}{2\sigma ^2}}$

S型核函数： $K(x_i,x_j) =tanh(kx_i.x_j-\delta )$

SVM优点

-算法复杂度由支持向量的个数决定，而非数据维度，所以不太易产生overfitting

-SVM训练出来的模型完全依赖于支持向量（Support Vectors）即使训练集里面所有非支持向量的点都被去除，重复训练过程，结果仍会一样

-一个SVM如果训练得出的支持向量个数比较小，SVM训练出的模型比较容易泛化

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

十三、支持向量机SVM

SVM（Support Vector Machines）

SMO算法

线性不可分的情况

非线性的情况

SVM优点

推荐阅读更多精彩内容