支持向量机（Support Vector Machine）08

First

由于博客公式的限制我还没有找到在合适的简书内给公式编号的方案，大家可以在我个人的博客中看带公式编号的这篇文章，点这里。SVM算法大概是，学到现在最难的算法了，牵扯了拉格朗日的细节问题，这些问题在学高数做题的时候都没有深入思考过。

SVM的优点和缺点

优点：泛化错误率低，计算开销不大，结果易解释
缺点：对参数调节和核函数的选择敏感，原始分类器不加修改仅适用于处理二类问题。
数据类型：数值型和标称型数据。

SVM算法原理

首先我们都知道，为了划分二维的数据需要一根线，划分三维数据需要一个面。这里线是一维，面是二维，同理继续推出对N维的数据需要使用N-1维的对象进行分割，线性回归和SVM本质都是通过找这个超平面来达到分类的效果。

具体的来说SVM是在优化线性回归中的 $kx+b$ 模型。在线性回归中只需要考虑有一个分割超平面能进行分类即可，而SVM则想找出所有能分类的分割超平面中最优的超平面，即所有点都到分割超平面的距离最大，而支持向量指的就是离超平面最近的那些点。

超平面的公式为公式2.1。所以点A到分割超平面的距离为公式2.2。这里我们为了方便计算引入类别标签为-1和+1。所以保证所有的最小间隔的点最大化的公式为公式2.3。
注1：-1和+1是为了保证预测正确的时候， $y(x_i)*label_i$ 都是一个很大的正值。
注2： $arg\ max_{w,b}$ 的含义是，得到w和b使得后面式子取最大值
$y(x) = w^TX+b$

$\frac{|w^TX+b|}{||w||}$

$arg\ max_{w,b}\{min_i(label_i*(w^Tx_i+b)*\frac{1}{||w||})\}$

显然我们不能直接求解上面的式子。需要化简下它。由于公式2.1在正确预测时，同 $label$ 的乘积大于1。所以我们可以拆分公式2.3为公式2.4，约束条件为公式2.5。
注：这里的约束条件公式2.5中，要对每一个式子前都要加系数，即拉格朗日数乘子 $\alpha_i$ 。
$arg\ min_{w,b}\ ||w||$
$st.\ \ label_i*(w^Tx_i+b) \geq 1$
对为了方便求导计算在公式2.4前加上 $\frac{1}{2}$ 这个系数。之后使用拉格朗日乘子法得到公式2.6，并进行计算。根据KKT条件中的偏导数等于0得到公式2.7和公式2.8。
祝：这里需要注意的是拉格朗日数乘子的正负号，这个同不等式的符号有关

$L(w,b,\alpha)= \frac{1}{2}||w||^2-\sum_{i=1}^n\alpha_i*[label_i*(w^Tx_i+b)-1]$
$\sum_{i=1}^{n}\alpha_i label_i x_i = w$
$\sum_{i=1}^{n}\alpha_i label_i = 0$
将公式2.7，公式2.8代入公式2.6化简，再根据对偶问题得到最终公式2.9，根据KKT，其约束条件为公式2.10。
注1：KKT条件在SMO算法中统一进行讲解。
注2：b是由公式2.8消掉的。
注3：在拉格朗日乘子法应用在这里，我们可以把 $||w||$ ，写作 $max_\alpha\ L(w,b,\alpha)$ ，所以原式可以写作 $min_{w,b}\ max_\alpha\ L(w,b,\alpha)$ ，根据对偶问题，就可以变成 $max_\alpha\ min_{w,b}\ L(w,b,\alpha)$ ，这也是能把公式2.7和公式2.8代入公式2.6的原因，也是公式2.9种是 $max_\alpha$ 的原因。具体证明在KKT中的附上的博客中。
$max_\alpha\ \sum_{i=1}^{n}\alpha_i - \frac{1}{2}\sum_{i,j=1}^{m}label_i*label_j*a_i*a_j\langle x_i·x_j\rangle$

$\alpha_i \geq 0\ \ 且\ \sum_{i=1}^{m}\alpha_i*label_i = 0$

注：这里 $\langle x_i·x_j\rangle$ 是两者向量积的运算，是从 $x_i^T*x_j$ 得到的。
这么看来我们算出了 $\alpha$ 就能算出超平面，所以SVM的工作就是算出这些 $\alpha$ ，而SMO算法就是求 $\alpha$ 的典型算法。

对SVM引入线性不可分

由于数据都不那么干净，所以我们不应该假设数据能够100%的线性可分。我们通过对判定的公式，公式2.5，引入松弛变量 $\xi_i\geq 0$ ，得到其引入了松弛因子的形式，如下公式3.1。
$y_i(w*x_i+b)\geq1-\xi_i$
同时对于目标函数公式2.4也需要调整，我们将 $\xi$ 引入目标函数并对其设置权值，得到公式3.2，也因此其约束条件变为公式3.1，公式3.2。
$min_{w,b}\frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i$
$\begin{split} st.\ \ \ &y_i(w*x_i+b)\geq 1 - \xi_i\\ &\xi \geq 0 \end{split}$
故拉格朗日函数 $L(w,b,\xi,\alpha,\mu)$ 为如下公式3.3，其中 $\alpha$ ， $\mu$ 为拉格朗日数乘子。
$L(w,b,\xi,\alpha,\mu)=\frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i-\sum_{i=1}^n\alpha_i*[label_i*(w^Tx_i+b)-1+\xi_i]-\sum_{i=1}^n\mu_i\xi_i$
和之前的操作一样，对其进行求偏导操作后，类似的得到了相同的公式2.7，公式2.8，不同的是这里对 $\xi$ 的求到后对 $\alpha$ 有了限制，得到了公式3.4，由于 $\mu\geq0$ 所以有 $\alpha_i$ 的取值范围 $0 \leq \alpha_i \leq C$ 。
注：注意这里的 $\alpha$ 取值，之后SMO会用
$C-\alpha_i-\mu_i = 0$
最终目标函数还是同之前推到的相同，即公式2.9，约束条件中只有 $\alpha$ 的取值变为了， $0 \leq \alpha_i \leq C$ 。这样有了目标函数了以后，之后可以根据梯度下降算法求得最终的 $\alpha$

SMO（Sequential Minimal Optimization）

KKT条件

求 $f(x)$ 极值的时候我们这里讨论三种情况。

没有约束条件：
有一个等式 $h(x)$ 的约束条件：
使用拉格朗日乘子法（Lagrange Multiplier），也就是我们在高数中求极值常用的。设置一个拉格朗日系数 $\alpha_1$ ，得到如下公式，之后对 $x$ 和 $\alpha_1$ 用求导的方式求极值即可。
$L(x, \alpha) = f(x) + \alpha*h(x)$
含有不等式的约束条件：
当约束条件中有不等式时，就需要用到KKT条件。同样地，把所有的不等式约束 $g(x)\leq0$ 、等式约束 $h(x)=0$ 和目标函数 $f(x)$ 全部写为一个式子如下公式。
$L(x,\alpha_1, \alpha_2)= f(x) + \alpha_1*g(x)+\alpha_2*h(x)$
KKT条件是说最优值必须满足以下条件：
1. $L(x, \alpha) = f(x) + \alpha(x)$ 对 $x$ ， $\alpha_1$ ， $\alpha_2$ 求导为零。
2. $h(x)=0$ 。
3. $g(x)*\alpha_1=0$ 。
  其中第三个式子非常有趣，因为 $g(x)\leq$ 0 ，如果要满足这个等式，必须有 $a = 0$ 或者 $g(x) = 0$ 。这是SVM的很多重要性质的来源。同时 $f(x)$ 也可以写作 $max_{\alpha_1,\alpha_2}\ L(x,\alpha_1,\alpha_2)$ ，这个则是SMO求解中的一个关键性质。详细的论述参考这篇博客。

SMO算法细节

SMO算法综述

由于原来直接通过梯度下降进行求解速度太慢，所以1996年，John Platt依靠KKT的特性，将大优化问题变成了多个小优化问题来求解，成为了SVM中最常用的求解思路。
其思路如下：

Loop：
1. 选取一对 $\alpha_i$ ， $\alpha_j$ 作为变量，其余看为常数
2. 如果这对满足以下两个条件，使用梯度下降算法改变他们的值。
  - 两者都在间隔边界外
  - 两者都没有在进行过区间化处理，或者不在边界上
3. 当满足了KKT条件，即 $\sum_{i=1}^N\alpha_iy_i=0$ 和 $0\leq \alpha_i \leq C$ 。
  注：这里可以这么理解， $\alpha_i$ 从之前的公式中我们可以大致理解为是每一个样本的权值，我们这些操作可以理解为通过操作 $\alpha$ 把所有的样本点尽量的放在间隔边界上。

算法推导

我们接下来要做的是，通过类似梯度下降的方式来求的最优的 $\alpha$ 值。正如上一节所说的，SMO的本质是大优化问题画小优化问题。所以从目标函数公式2.9中，随意取出两个 $\alpha$ ，为了表达方便，不妨直接取 $\alpha_1$ 和 $\alpha_2$ ，同时对公式2.9前加负号取反之后，化简如下式4.1，其中 $\kappa_{ij}$ 代表 $\langle x_i·x_j\rangle$ 。
$\begin{split} min_{\alpha_1, \alpha_2}W(\alpha_1,\alpha_2) &=\frac{1}{2}\kappa_{11}\alpha_1^2+\frac{1}{2}\kappa_{22}\alpha_2^2+y_1y_2\alpha_1\alpha_2\kappa_{12}-(\alpha_1+\alpha_2)\\ &+y_1\alpha_1\sum_{i=3}^Ny_i\alpha_i\kappa_{i1}+y_2\alpha_2\sum_{i=3}^Ny_i\alpha_i\kappa_{i2}\\ \end{split}$
$\begin{split} st. \ \ &\alpha_1y_1+\alpha_2y_2=-\sum_{i=3}^Ny_i\alpha_i\\ &0\leq\alpha_i\leq C \end{split}$
由于我们已经把不是 $\alpha_1$ 和 $\alpha_2$ 的参数看作常量，所以在进行求偏导进行梯度下降算法的时候就不需要考虑公式4.1中第二行的式子。通过这个式子中约束条件的等式就可以得到仅含 $\alpha_j$ 的式子，对其进行梯度下降算法，得到如下公式4.2：
$g(x)=\sum_{i=1}^Ny_i\alpha_i\kappa(x_i,x)+b$
$\eta = \kappa_{11}+\kappa_{22}-2\kappa_{12} = ||x_1-x2||^2$
$E_i = g(x_i)-y_i = (\sum_{j=1}^Ny_j\alpha_j\kappa_{ji}+b)-y_i$
$\alpha_i = \frac{\xi-\alpha_j y_j}{y_i}$
$\alpha_j^{new}=\alpha_j^{old}+\frac{y_j(E_i-E_j)}{\eta}\ \ \ 公式4.2$
这时候我们已经找到了两个的 $alpha$ 的新值了，不过我们不能确定这两个新值是否还满足KKT条件。所以我们根据KKT条件中 $\alpha$ 的取值，设置了L和H来防止新值不满足KKT，即 $L\leq\alpha_i,\alpha_j \leq H$ ，其中L，H的公式如下公式4.3和公式4.4得到：
$if\ y_i \neq y_j\ \ \ L=max(0,\alpha_j-\alpha_i),\ H=min(C,C+\alpha_j-\alpha_i)$
$if\ y_i = y_j\ \ \ L=max(0,\alpha_j+\alpha_i-C),\ H=min(C,\alpha_j+\alpha_i)$
LH的细节推到，在这个博客中详细的说明了LH是怎么推出来的。

最后编辑于：2018.08.22 22:30:36

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