SVM推导步骤

SVM（Support Vector Machine，支持向量机）是最经典的分类算法，本文主要整理（为了应付考试）SVM的推导方式，不包含SMO算法求解最后的约束。

借鉴博客：
https://cuijiahua.com/blog/2017/11/ml_8_svm_1.html

https://www.cnblogs.com/90zeng/p/Lagrange_duality.html

一般的，SVM就是一个分类器，只是相对于传统的线性分类器，它添加了一个支持向量的概念。这样相对于传统分类器可能存在的多个解，SVM由于约束的存在一般只有单解，并且表现更好。

从图片上解释，对于一组数据，传统的线性分类器使用一条直线将数据分类，而SVM在使用直线的同时要求数据点距离这条直线的最小距离最大，也就是说分类器和数据之间要有足够大的“间隔”。这样做的好处是很明显的，越大的“间隔”代表了更大的转圜空间，在得到新的数据之后更容易将其正确分类。

而SVM的工作就是求解这个最大间隔，也就是最优化问题。对于线性可分的数据，可以直接套用线性规划的知识进行推导，但如果数据线性不可分，就需要核函数进行数据升维，进行超平面分类。

二分类问题的数据点

传统的线性分类器

SVM的分类方式，要求“间隔”最大

下面是具体的建模推导过程：

一·决策面方程

我们现在二维场景下考虑分类方程，所以决策面也就是决策线。

考虑在二维场景下，我们描述一条直线的方法是：

$y=ax+b$

简单替换，将 $y$ 替换为 $x_2$ ，将 $x$ 替换为 $x_1$ ，简单获得以下公式：

$x_2=ax_1+b$

=> $ax_1-x_2+b=0$

将上述公式转换为向量形式：

$[a,-1][\begin{array}{c} x_1 \\ x_2\end{array}] +b=0$

也就是 $\omega ^Tx+\gamma =0, 其中，\omega=[a,-1]^T,x=[x_1,x_2]^T$

这个式子的几何意义是原式子的法向量。而如果我们将上述式子推广到高维空间，就是我们需要的决策面方程。也就是：

$\omega ^Tx+\gamma =0, 其中，\omega=[\omega_1, \dots, \omega_n]^T,x=[x_1,\dots,x_n]^T$

二·分类间隔方程

在获取决策面方程之后，我们需要获知决策面方程中的 $\omega$ 和 $\gamma$ 的具体值，而求解这个值的核心就是靠分类间隔方程所施加的约束条件。

首先我们需要副系以下间隔的含义，在SVM中，“间隔”指的是分类器距离样本点的最小距离，我们需要找一个使这个最小距离最大的分类器作为我们的最优解。因此我们的约束条件是很好想到的，高中学过的距离公式：

$\begin{equation} \left\{ \begin{array}{**lr**} d=\frac{Ax_0+By_0+C}{\sqrt{A^2+B^2} } , & \\点(x_0,y_0),直线Ax+By+C=0\end{array} \right. \end{equation}$

而在超平面上，只需要简单的推广以上公式，结合我们之前获得的决策面方程，

$\omega ^Tx+\gamma =0, 其中，\omega=[\omega_1, \dots, \omega_n]^T,x=[x_1,\dots,x_n]^T$

我们不难得到，在我们所得到的直线（超平面上），某个样本与其的距离是：

$d=\frac{|\omega^Tx+\gamma|}{||\omega||}$

分母是指 $\omega$ 的二范数，也就是平方和求导。这样我们的问题就转化为，求最大的 $W$ ，其中 $W=2d$ ，也就是求 $\max \limits_{}d$ 。

三·约束条件

获取了上述分类间隔方程，但是这个方程只是来评判我们的分类器是否是好的，我们并不能确定

（1）分类器是否能正确分类

（2）如何选择正确的支持向量点

这两个问题是限制我们随意计算 $d$ 的限制条件，在SVM中，以下列方式处理这些限制条件。

首先仍然只考虑线性可分的二分类情况，在这种情况下只有两类数据，我们对这两类数据分别赋值为1和-1，也就是：

$y=\begin{equation} \left\{ \begin{array}{**lr**} 1 , 数据属于第一类& \\-1.数据属于第二类\end{array} \right. \end{equation}$

分类还是很直观的，事实上我们在有监督学习里面基本也这么赋值。这样赋值之后，假设我们所得到的分类器可以正确分类两类数据，那么我们的分类器可以得出什么结果？不难得到以下形式：

$y=\begin{equation} \left\{ \begin{array}{**lr**} \omega^T+\gamma>0, y_i=1& \\\omega^T+\gamma<0, y_i=-1\end{array} \right. \end{equation}$

如果我们严格一点（或者说运气很好），我们得到的分类器是SVM的最优解，那么根据上面的距离公式，我们可以简化得到：

$\begin{equation} \left\{ \begin{array}{**lr**} \frac{|\omega^Tx+\gamma|}{||\omega||}\ge d, y_i=1& \\\frac{|\omega^Tx+\gamma|}{||\omega||}\le -d, y_i=-1\end{array} \right. \end{equation}$

$\Rightarrow \begin{equation} \left\{ \begin{array}{**lr**} \omega_d^Tx+\gamma_d\ge 1, y_i=1& \\\omega_d^Tx+\gamma_d\le 1, y_i=-1\end{array} \right. \end{equation}$

其中：

$\omega_d^T=\frac{\omega}{||\omega||d}$ $\gamma_d=\frac{\gamma}{||\omega||d}$

分母都是标量，所以除以 $d$ 并不影响原式子的几何含义，也就是法向量。那么我们事实上拿掉这个 $d$

也不会影响最后的结果。最后对以上式子进行整理，即可获得一个不等式：

$y_i(\omega^Tx+\gamma)\ge 1, \forall x_i$

这里的 $\omega$ 与上文中的 $\omega$ 在数值上不同，但是在几何意义上是一样的。

四·优化问题描述

在三中，我们考虑了如果我们的分类器可以正确分类，我们的公式要如何进行约束，那么现在我们需要解决第二个问题了，如果选取支持向量点？

这个问题比较好考虑，支持向量点有一个特征，那就是对于一个支持向量点 $x_i$ ,必然有

$|\omega^Tx_i+\gamma| = 1$

那么在我们预先定义好的距离公式 $d=\frac{|\omega^Tx+\gamma|}{||\omega||}$ 中，我们发现带入上式子的结果，有

$d=\frac{1}{||\omega||}$

那么我们对 $d$ 的最大值约束就变化为对 $\omega$ 的最小值约束，也就是求解 $min\frac{1}{2}||\omega||^2,其中y_i(\omega^Tx_i+b)\ge 1,i=1,2,\dots,n$

五·求解准备

在得到上述式子之后，我们发现这是一个带有不等式约束的规划问题，为了解决这种问题，我们一般采用构造拉格朗日函数的方法，使用对偶性解决问题。

5.1·拉格朗日函数

首先，我们先要从宏观的视野上了解一下拉格朗日对偶问题出现的原因和背景。

我们知道我们要求解的是最小化问题，所以一个直观的想法是如果我能够构造一个函数，使得该函数在可行解区域内与原目标函数完全一致，而在可行解区域外的数值非常大，甚至是无穷大，那么这个没有约束条件的新目标函数的优化问题就与原来有约束条件的原始目标函数的优化问题是等价的问题。

这就是使用拉格朗日方程的目的，它将约束条件放到目标函数中，从而将有约束优化问题转换为无约束优化问题。

随后，人们又发现，使用拉格朗日获得的函数，使用求导的方法求解依然困难。进而，需要对问题再进行一次转换，即使用一个数学技巧：拉格朗日对偶。

所以，显而易见的是，我们在拉格朗日优化我们的问题这个道路上，需要进行下面二个步骤：

将有约束的原始目标函数转换为无约束的新构造的拉格朗日目标函数

使用拉格朗日对偶性，将不易求解的优化问题转化为易求解的优化

下面，进行第一步：将有约束的原始目标函数转换为无约束的新构造的拉格朗日目标函数

先写下原始式子：

$min\frac{1}{2}||\omega||^2,其中y_i(\omega^Tx_i+b)\ge 1,i=1,2,\dots,n$

我们首先将其变形，将其变为如下格式：

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

其中 $\alpha_i \ge 0$ 被称为拉格朗日乘子，当然虽然名字很吓唬人，事实上它是我们随意引入的一个参数。这个参数是用来构造等价问题的。

我们令 $\theta(\omega,b)=\max \limits_ {\alpha_i \ge 0}\ L(\omega,b,\alpha)$ 。

也就是当前这个方程和 $\alpha_i$ 无关，当某个点 $x_i$ 不在可行解区域中，也就是 $y_i(\omega^Tx_i+b) < 1$ ,我们将 $\alpha_i$ 设置为无穷大，显然此时 $\theta(\omega,b)$ 也是无穷大的。而当该点在可行域区域内， $y_i(\omega^Tx_i+b) \ge 1$ ，那么 $\max \limits_ {\alpha_i \ge 0}\ L(\omega,b,\alpha)$ 的结果显然是 $\frac{1}{2}||\omega||^2$ （因为后半部分必然大于等于0，那么为了保证最大，当然是等于0）。这样， $\theta(\omega,b)$ 就可以转化为：

$\theta(\omega,b)=\begin{equation} \left\{ \begin{array}{**lr**} \frac{1}{2}||\omega||^2, x_i在可行域\\+\infty，x_i不在可行域\end{array} \right. \end{equation}$

显然在可行域内， $\theta$ 是一个凸函数，是必然有极小值的，因此问题被转化为求此函数的最小值，也就是：

$\min \limits_{\omega,b}\theta(\omega,b)=\min \limits_{\omega,b}\max\limits_{\alpha_i\ge0}L(\omega,b,\alpha)=p^*$

这个式子事实上也不好求，因为内层的 $max$ 仍然带有不等式的限制条件，因此我们要使用拉格朗日对偶方法将其转化为易求的对偶形式。

5.2 拉格朗日对偶及其证明

拉格朗日对偶的定义如下：

以我们刚刚获得的式子 $\min \limits_{\omega,b}\theta(\omega,b)=\min \limits_{\omega,b}\max\limits_{\alpha_i\ge0}L(\omega,b,\alpha)=p^*$ 为例，我们先针对 $\alpha$ 作为未知数构造一个函数：

$\theta(\alpha)=\min \limits_{\omega,b}L(\omega,b,\alpha)$

考虑其极大化，也就是 $\max\limits_{\alpha;\alpha_i\ge0}\theta(\alpha)=\max\limits_{\alpha;\alpha_i\ge0}\min \limits_{\omega,b}L(\omega,b,\alpha)$

这个问题就是原始问题的对偶问题了。假设我们使 $\max\limits_{\alpha;\alpha_i\ge0}\theta(\alpha)=\max\limits_{\alpha;\alpha_i\ge0}\min \limits_{\omega,b}L(\omega,b,\alpha)=d^*$

则可以证明 $d^*\le p^*$

证明方式：对于任意的 $\alpha,\omega和b$ ，有 $\theta_d(\alpha)=\min\limits_{\omega,b}L(\omega,b,\alpha)\le L(\omega,b,\alpha)\le \max\limits_{\alpha\ge 0}L(\omega,b,\alpha)\le \theta_p(\omega,b)$

不难推论，当 $d^*=p^*$ 时，此时 $\omega^*,b^*,\alpha^*$ 均为最优解。

那么如何使得上述相等情况成立呢？这就需要满足KKT条件。

5.3·KKT条件

KKT条件的全称是Karush-Kuhn-Tucker条件，KKT条件是说最优值条件必须满足以下条件：

条件一：经过拉格朗日函数处理之后的新目标函数L(w,b,α)对x求导为零：

条件二：h(x) = 0；

条件三：α*g(x) = 0；

我们的式子已经满足此条件，具体的嘛……反正我也不懂，先记下来以后补= =

六·最终结果

已知 $\max\limits_{\alpha;\alpha_i\ge0}\theta(\alpha)=\max\limits_{\alpha;\alpha_i\ge0}\min \limits_{\omega,b}L(\omega,b,\alpha)=d^*$

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

首先固定 $\alpha$ ,针对内层最小化求导，可以得到：

$\frac{\alpha L}{\alpha \omega}=0 \Rightarrow \omega=\sum_{i=1}^n \alpha_iy_ix_i$

$\frac{\alpha L}{\alpha b}=0 \Rightarrow \sum_{i=1}^n \alpha_iy_i=0$

带入原式：

$\begin{equation}\begin{aligned}L(\omega,b,\alpha)&=\frac{1}{2}||\omega||^2-\sum_{i=1}^n \alpha_i[y_i(\omega^Tx_i+b-1) ] \\&=\frac{1}{2}\omega^T\omega-\omega^T\sum_{i=1}^n\alpha_iy_ix_i-b\sum_{i=1}^n\alpha_iy_i+ \sum_{i=1}^n\alpha_i \\&=\frac{1}{2}\omega^T\sum_{i=1}^n\alpha_iy_ix_i-\omega^T\sum_{i=1}^n\alpha_ix_iy_i-b*0+\sum_{i=1}^n\alpha_i\\&=\sum_{i=1}^n\alpha_i-\frac{1}{2}(\sum_{i=1}^n\alpha_iy_ix_i)^T\sum_{i=1}^n\alpha_iy_ix_i\\&=\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j\end{aligned}\end{equation}$

此时只有一个参数， $\alpha_i$

然后我们计算外层的最大化，

$\max\limits_{\alpha}\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j\\s.t.\ \alpha_i \ge0, \ \ i =1,2,\dots,n\\\sum_{i=1}^n\alpha_iy_i=0$

现在我们的优化问题变成了如上的形式。对于这个问题，我们有更高效的优化算法，即序列最小优化（SMO）算法。我们通过这个优化算法能得到α，再根据α，我们就可以求解出w和b，进而求得我们最初的目的：找到超平面，即"决策平面"。

七·非线性与核函数

前面六个部分都是建立在数据线性可分的情况之下，而当数据不可分时，我们需要使用一些方法将其升维，使其在高维空间成为可分的。

总体而言，经过SMO计算出 $\alpha$ 之后，可以得到最后的方程：

$f(x) = \sum_{i=1}^n\alpha_iy_ix_i^Tx + b$

使用内积表示它：

$f(x) = \sum_{i=1}^n\alpha_iy_i<x_i,x> + b$

如果数据是不可分的，我们使用一个非线性映射（不管这个映射是什么样的，事实上往往不知道这是什么映射，映射获得的结果也可能无法计算）将数据映射到高维空间，使其在高维空间可分，则上式可以改写为：

$f(x) = \sum_{i=1}^n\alpha_iy_i<\phi (x_i),\phi(x)> + b$

其中 $\phi(x)$ 是一个映射，它表示输入空间到特征空间的映射。

这种映射结果，牵扯到高维空间的内积运算，而高维空间维度越高我们需要的计算量就越大，有时候甚至是无限维的，导致不能直接计算。因此我们定义了一个核函数(kernel function)，其本质是在输入空间的一个函数 $\kappa$ ，我们如果可以使得 $\kappa(x_i, x)=<\phi(x_i),\phi(x)>$ ，那么计算就可以局限在输入空间的低纬度，减少计算资源的消耗。

所以直接就给出一个定义：核是一个函数k，对所有x,z∈X，满足k(x,z)=<ϕ(xi),ϕ(x)>，这里ϕ(·)是从原始输入空间X到内积空间F的映射。

在实际使用中，有多种比较常见的核函数形式（所以核函数实际上都是一种近似）：

常用的核函数

最后编辑于：2018.12.26 08:57:57

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