支持向量机

图来源：《机器学习》周志华著

超平面用方程表示为

w^Tx+b=0

，

\gamma=\frac{2}{||w||}

为间隔(margin)。我们需要找到具有最大间隔的划分超平面，故得到：

\underset{w,b}{argmin}\frac12||w||^2

s.t. y_i(w^Tx+b)>=1,i=1,2,...,m

1.问题求解：

(1)拉格朗日乘子法

定义拉格朗日函数
$L(w,b,\mu)=\frac{1}{2}||w||^2+\sum_{i=1}^{m}\mu_i(1-y_i(w^Tx+b))$ ，
KKT条件为：
$\begin{cases} \mu _{ i }>=0 \\ 1-y_{ i }(w^{ T }x+b)<=0 \\ \mu_i(1-y_i(w^Tx+b))=0\end{cases}$
求极值，则令
$\frac{\partial{L}}{\partial{w}}=w-\sum_{i=1}^{m}\mu_iy_ix_i=0$
$\frac{\partial{L}}{\partial{b}}=\sum_{i=1}^{m}\mu_iy_i=0$
得到：
$w=\sum_{i=1}^{m}\mu_iy_ix_i$
$\sum_{i=1}^{m}\mu_iy_i=0$
代入 $L(w,b,\mu)$ 消去 $w$ 和 $b$ ,得到原问题的对偶问题为
$\underset{\mu}{argmax} \sum_{i=1}^{m}\mu_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\mu_i\mu_jy_iy_jx_i^Tx_j$
$s.t. \sum_{i=1}^{m}\mu_iy_i=0,\mu_i>=0,i=1,2,...m$
由KKT条件得到：对于任意训练样本 $(x_i,y_i)$ 总有 $\mu_i=0$ 或 $y_i(w^Tx_i+b)=1$ ,这就意味着当 $\mu_i=0$ 时，该样本并不会对 $f(x)=w^Tx+b$ 产生而任何影响，当 $y_i(w^Tx_i+b)=1$ 时，此时意味着训练样本在最大间隔的边界上，该样本点称之为支持向量。

(2)对偶问题求解：

2.核函数

假设样本线性可分，即存在一个超平面对样本进行分类。而实际任务中，样本往往是非线性可分。此时，我们将 $x_i$ 映射到高维特征空间，在特征空间中找到超平面使得样本线性可分，记 $\phi(x_i)$ 为 $x_i$ 映射到高维特征空间所对应的特征向量。
因此，对应的模型可以表示为
$f(x)=w^T\phi(x)+b$
实际只需要求解如下函数：
$\underset{w,b}{argmin}\frac12||w||^2$
$s.t. y_i(w^T\phi(x_i)+b)>=1,i=1,2,...,m$
对偶问题为：
$\underset{\mu}{argmax} \sum_{i=1}^{m}\mu_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\mu_i\mu_jy_iy_j\phi(x_i)^T\phi(x_j)$
$s.t. \sum_{i=1}^{m}\mu_iy_i=0,\mu_i>=0,i=1,2,...m$
当特征空间维度很高时，计算 $\phi(x_i)^T\phi(x_j)$ 困难，故定义核函数 $k(.,.)$ 使得 $\phi(x_i)^T\phi(x_j)=k(x_i,x_j)$ ,
则对偶问题重写为：
$\underset{\mu}{argmax} \sum_{i=1}^{m}\mu_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\mu_i\mu_jy_iy_jk(x_i,x_j)$
$s.t. \sum_{i=1}^{m}\mu_iy_i=0,\mu_i>=0,i=1,2,...m$
求解该对偶问题得到
$f(x)=\sum_{i=1}^{m}\mu_iy_i\phi(x_i)^Tx+b$
$=\sum_{i=1}^{m}\mu_iy_ik(x_i,x)+b$

3.软间隔

图中红色样本是被分错的

前面介绍的支持向量机形式是要求所有样本均满足约束 $y_i(w^Tx+b)>=1,i=1,2,...,m$ ，即所有样本都必须划分正确，这称为"硬间隔" (hard margin)，而软间隔则是允许某些样本不满足约束。当然我们是希望这样不满足约束的样本越少越好。因此目标函数定义为
$\underset{w,b}{argmin}\frac{1}{2}||w||+C\sum_{i=1}^{m}l_{0/1}( y_i(w^Tx+b)-1)$ ,其中
$l_{0/1}(z)=\begin{cases} 1\quad ,if\quad z<0 \\ 0\quad ,otherwise \end{cases}$

由于 $l_{0/1}$ 非凸、非连续，常用其他损失函数替代，如下图所示:

三种常见的替代损失函数:hinge损失，指数损失，对率损失

采用hinge损失得到：

\underset{w,b}{argmin}\frac{1}{2}||w||^2+C\sum_{i=1}^{m}max(0, 1-y_i(w^Tx+b))

引入松弛变量得到:

软间隔支持向量机

$\underset{w,b}{argmin}\frac{1}{2}||w||^2+C\sum_{i=1}^{m}\xi_i$
$s.t. y_i(w^Tx+b)>=1-\xi_i,i=1,2,...,m$
$\xi_i>=0,i=1,2,...,m$
采用拉格朗日乘子法
$L(w,b,\alpha,\xi,\mu)=\frac{1}{2}||w||^2+C\sum_{i=1}^{m}\xi_i+\sum_{i=1}^{m}\alpha_i(1-\xi_i-y_i(w^Tx_i+b))-\sum_{i=1}^{m}\mu_i\xi_i$ ，求极值，令
$\frac{\partial{L}}{\partial{w}}=w-\sum_{i=1}^{m}\alpha_iy_ix_i=0 \Rightarrow w=\sum_{i=1}^{m}\alpha_iy_ix_i$
$\frac{\partial{L}}{\partial{b}}=\sum_{i=1}^{m}\alpha_iy_i=0$
$\frac{\partial{L}}{\partial{\xi_i}}=C-\alpha_i-\mu_i=0 \Rightarrow C=\alpha_i+\mu_i$
带入L得到原问题的对偶问题为:
$\underset{\alpha}{argmax}\sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j$
$s.t. \sum_{i=1}^{m}\alpha_iy_i=0$
$0<=\alpha_i<=C,i=1,2,...,m$
KKT条件要求:
$\begin{cases} \alpha _{ i }>=0, \mu_i>=0\\ 1-\xi_i-y_{ i }(w^{ T }x+b)<=0 \\\xi_i>=0\\ \alpha_{ i }(1-\xi_i-y_{ i }(w^{ T }x+b))=0 \\\mu_i\xi_i=0\end{cases}$
由此可得：

对于任意 $(x_i,y_i)$ ,当 $\alpha_i=0$ 时，该样本不会对 $f(x)$ 产生任何影响；当 $\alpha_i>0$ 时，必有 $y_{ i }(w^{ T }x+b)=1-\xi_i$ ,此时该样本是支持向量。当 $\alpha_i<C$ 时， $\mu_i>0$ ,则 $\xi_i=0$ ,此时样本处于最大间隔边界上，当 $\alpha_i=C$ 时， $\mu_i=0$ ，则 $\xi_i>0$ ；若 $\xi_i>1$ ,样本被错误分类;若 $\xi_i<1$ ,样本落在最大间隔内部。
软间隔支持向量机模型仅与支持向量有关。

4.支持向量回归

（1）考虑 $f(x)$ 与 $y$ 最多允许有 $\varepsilon$ 的误差
（2）构建宽度为 $2\varepsilon$ 的间隔带，如图：

落入间隔带的样本被认为是预测正确的

目标函数：

\underset{w,b}{argmin}\frac{1}{2}||w||+C\sum_{i=1}^{m}l_{\varepsilon}( f(x_i)-y_i)

l_{\varepsilon}(z)=\begin{cases} 0\quad ,if\quad |z|<=\varepsilon \\|z|-\varepsilon\quad ,otherwise \end{cases}

可允许间隔带两侧的松弛程度有所不同，故引入松弛变量

\xi

和

\overset{\wedge}{\xi}

,得到SVR问题：

\underset{w,b}{argmin}\frac{1}{2}||w||+C\sum_{i=1}^{m}(\xi_i+\overset{\wedge}{\xi}_i)

s.t. f(x_i)-y_i<=\varepsilon+\xi_i

y_i- f(x_i)<=\varepsilon+\overset{\wedge}{\xi}_i

\xi_i>=0,\overset{\wedge}{\xi}_i>=0,i=1,2,...,m

拉格朗日乘子法

L(w,b,\xi,\overset{\wedge}{\xi},\alpha,\overset{\wedge}{\alpha},\mu,\overset{\wedge}{\mu})=\frac{1}{2}||w||^2+C\sum_{i=1}^{m}(\xi_i+\overset{\wedge}{\xi}_i)

+\sum_{i=1}^{m}\alpha_i( f(x_i)-y_i-\varepsilon-\xi_i)+\sum_{i=1}^{m}\overset{\wedge}{\alpha}_i(y_i-f(x_i)-\varepsilon-\overset{\wedge}{\xi}_i)

-\sum_{i=1}^{m}\mu_i\xi_i-\sum_{i=1}^{m}\overset{\wedge}{\mu}_i\overset{\wedge}{\xi}_i

，求极值，令

\frac{\partial{L}}{\partial{w}}=w-\sum_{i=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)x_i=0 \Rightarrow w=\sum_{i=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)x_i

\frac{\partial{L}}{\partial{b}}=\sum_{i=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)=0

\frac{\partial{L}}{\partial{\xi_i}}=C-\alpha_i-\mu_i=0 \Rightarrow C=\alpha_i+\mu_i

\frac{\partial{L}}{\partial{\overset{\wedge}{\xi}_i}}=C-\overset{\wedge}{\alpha}_i-\overset{\wedge}{\mu}_i=0 \Rightarrow C=\overset{\wedge}{\alpha}_i+\overset{\wedge}{\mu}_i

代入L,得到SVR的对偶问题：

\underset{\alpha,\overset{\wedge}{\alpha}}{argmax}\sum_{i=1}^{m}y_i(\overset{\wedge}{\alpha}_i-\alpha_i)-\varepsilon(\overset{\wedge}{\alpha}_i+\alpha_i)

-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)(\overset{\wedge}{\alpha}_j-\alpha_j)x_i^Tx_j

s.t. \sum_{i=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)=0

0<=\alpha_i,\overset{\wedge}{\alpha}_i<=C,i=1,2,...,m

KKT条件为：

\begin{cases} \alpha_i(f(x_i)-y_i-\varepsilon-\xi_i)=0 \\ \overset{\wedge}{\alpha}_i(y_i-f(x_i)-\varepsilon-\overset{\wedge}{\xi}_i)=0 \\ \alpha_i \overset{\wedge}{\alpha}_i=0,\xi\overset{\wedge}{\xi}_i=0\\(C-\alpha_i)\xi=0,(C-\overset{\wedge}{\alpha}_i)\overset{\wedge}{\xi}_i=0 \end{cases}

当且仅当 $f(x_i)-y_i-\varepsilon-\xi_i=0$ , $\alpha_i$ 为非零；当且仅当 $y_i-f(x_i)-\varepsilon-\overset{\wedge}{\xi}_i=0$ , $\overset{\wedge}{\alpha}_i$ 为非零.换言之，样本 $(x_i,y_i)$ 没有落在 $\varepsilon$ -间隔带时， $\alpha_i$ 和 $\overset{\wedge}{\alpha}_i$ 为非零。此外， $f(x_i)-y_i-\varepsilon-\xi_i=0$ 和 $y_i-f(x_i)-\varepsilon-\overset{\wedge}{\xi}_i=0$ 不能同时成立。因此， $\alpha_i$ 和 $\overset{\wedge}{\alpha}_i$ 至少有一个为零。
由 $f(x)=\sum_{i=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)x_i^Tx+b$ 可知，只有 $(\overset{\wedge}{\alpha}_i-\alpha_i)$ 非零时， $(x_i,y_i)$ 为SVR的支持向量，且落在 $\varepsilon$ -间隔带之外。落在 $\varepsilon$ -间隔带中的样本，满足 $\alpha_i=\overset{\wedge}{\alpha}_i=0$

5.支持向量机与KNN

最后编辑于：2019.03.13 15:20:20

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