支持向量机SVM——原理及相关数学推导系列一

（一）前言

支持向量机比较适合于高维数据，可以减缓维数灾难问题；也非常适用于小样本，建模只需要“支持向量”即可。
支持向量机的思想非常简单，就是可以找到一个超平面使得不同类别的数据可以尽量分开，并且为了增加测试集分类的鲁棒性（robust），希望这个超平面与各类别距离最近的数据点均越远越好。

定义1.1：测试样本(x,y)的类别预测规则，如下：
$y=\begin{cases} 1 \ \ \ \ ,w^T x + b >0 \\ -1 \ ,w^T x + b <0 \end{cases}$
上面的式子可以统一为 $y(w^Tx+b) > 0$ .

（二）线性可分的SVM

基本原理

因为下面要计算点到超平面的距离，所以这里给出距离公式，假设超平面S为 $w^Tx + b = 0$ ，某个点p到S的距离定义如下。

定义2.1
$distance(p, S) = \frac{|w^Tx + b|} {||w||}$
根据SVM的思想：
1.在所有点的类都分对的条件下，即 $y_i(w^Tx_i + b) > 0$
2.希望每类中最近的点离分割面的距离越远越好。设这个最近的距离是C，那么SVM问题可以定义如下：
定义2.1：最大边缘分类器
$\begin{align*} &\max_{w,b}\ C \\ &s.t. y_i(w^Tx_i + b)/||w|| \geq C \end{align*}$
其中， $i=1,2, \dots,N$
对定义2.1中的不等式的左右均乘以 $||w||$ ，并且令 $C=1/||w||$ ，那么上述等式就可以转化为
定义2.2
$\begin{align*} &\max_{w,b} \ 1/||w|| \\ &s.t.y_i(w^Tx_i + b) \geq 1 \end{align*}$
其中， $i=1,2,\dots,N$
在数学中，带根号的式子不太好处理，并且处理最大化问题可以转化为处理最小化问题（定义2.2中需要最大化的式子是正数，所以与其等价的最小化问题即为其倒数），那么定义2.2可以重新定义为2.3.
定义2.3
$\begin{align*} &\min_{w,b} \ \frac{1}{2}w^Tw \\ &s.t. y_i(w^T x_i + b) \geq 1 \end{align*}$
其中， $i =1,2,\dots,N$

对偶问题

为了求解定义2.3中的未知参数，下面我们将改问题转化为其对偶形式。
首先，解释下定义2.3是如何和定义2.4等价的。在定义2.3中
1.当 $y_i (w^Tx_i + b) < 1$ 时，即点分类错误。那么 $1- y_i (w^Tx_i + b) > 0$ ，要想让定义2.4中的 $\alpha_i \geq 0$ 使得式子最大化，那么式子将变为无穷大，即无解。

2.当 $y_i (w^Tx_i + b) \geq 1$ 时，即点分类正确。那么 $1- y_i(w^T x_i + b) \leq 0$ ，此时，要想让定义2.4中的 $\alpha_i \geq 0$ 使得式子最大化，那么 $\alpha_i (1-y_i(w^Tx_i + b))$ 只能为零。即为最小化 $\frac{1}{2}w^T w$ 。
总结一下：定义2.4有解，就是在 $y_i(w^T x_i + b) \geq 1$ 时去最小化 $\frac{1}{2}w^T w$ 。是不是和定义2.3在处理同一个问题？

定义2.4
$\min_{w,b}\max_{\alpha_i \geq 0}L(w,b) = \min_{w,b}\max_{\alpha_i \geq 0}\frac{1}{2}w^T w + \sum_{i=1}^{N} \alpha_i(1-y_i(w^Tx_i + b))$
其中， $i =1,2,\dots,N$
那么在数学上，定义2.4有一个下限，我们可以通过这个下限去求解得到超平面。即 $\min_{w,b} \max_{\alpha_i \geq 0} L(w,b) \geq \max_{\alpha_i \geq 0}\min_{w,b}L(w,b,\alpha)$ 所以将我们的问题重新定义为2.5。
定义2.5
$\max_{\alpha_i \geq 0} \min_{w,b}L(w,b,\alpha)=\max_{\alpha_i \geq 0}\min_{w,b}\frac{1}{2}w^Tw + \sum_{i=1}^{N} \alpha_i(1-y_i(w^Tx_i + b))$
其中， $i =1,2,\dots,N$
定义2.5里面的最小化问题很好解，即为求 $||w||$ 和 $b$ 的偏导数，令其为零。
$\begin{align*} & \frac{\partial L(w,b,\alpha)}{\partial w} = w - \sum_{i=1}^{N}\alpha_iy_ix_i=0 \\ &\frac{\partial L(w,b,\alpha)}{\partial b} = -\sum_{i=1}^{N}\alpha_iy_i = 0 \end{align*}$
将解出的 $||w||$ 和 $b$ 代入到定义2.5中得到：
$\begin{align*} &\frac{1}{2}w^T w + \sum_{i=1}^{N}\alpha_i(1-y_i(w^Tx_i + b)) \\ =& \frac{1}{2}w^T w - w^T w +\sum_{i=1}^{N}\alpha_i + \sum_{i=1}^{N}\alpha_i y_i b \\ =&\sum_{i=1}^{N}\alpha_i - \frac{1}{2}w^T w \\ =& \sum_{i=1}^{N}\alpha_i - \frac{1}{2}\sum_{j=1}^{N}\sum_{i=1}^{N}\alpha_i y_i \alpha_j y_j x_i^T x_j \end{align*}$

终于推导完成了！！！最后再将最大化求解等价转化为最小化问题求解即为定义2.6。它是个关于 $\alpha$ 的函数，即为一个二次规划问题，推荐大家一个软件，在做规划的时候非常实用，这个软件就是lingo啦。

定义2.6
$\min_{\alpha \geq 0} \frac{1}{2} \sum_{j=1}^{N}\sum_{i=1}^{N}\alpha_i y_i \alpha_j y_j x_i^T x_j - \sum_{i=1}^{N}\alpha_i$
细心的你应该发现了，上述推导过程中有一系列条件，来保证有解。这些条件合在一起即为KKT条件：

1. $y_i(w^T x_i + b) \geq1$
2. $\alpha \geq0$
3. $w= \sum_{i=1}^{N} \alpha_i y_ix_i$ , $\sum_{i=1}^{N}\alpha_iy_i =0$
4. $\alpha_i (1 - y_i(w^T x_i + b)) = 0$

超平面求解以及支持向量的解释

根据上面得到的 $\alpha$ ，我们可以反代回偏导数为0的式子中，求解 $| |w||$ 和 $b$ 即
$w= \sum_{i=1}^{N}\alpha_iy_ix_i$ ，其中 $b$ 的求解需要用到KKT条件中的第4个条件，当 $\alpha_i > 0$ 时，则 $b = y_i - w^T x_i$ ，对于不同的 $\alpha_i$ 会有不同的 $b$ 的估计值，所以一般最后对于 $b$ 的估计，会取这些估计值的平均值。
那么也就是说，在求解 $b$ 时，我们只用到了 $\alpha_i > 0$ 的那些点，而根据KKT条件，当 $\alpha_i > 0$ 时， $1 - y_i(w^T x_i + b)=0$ ，这些点均在分割线上，而这些点正是支持向量。

分割线示意图.png

如果有任何错误，欢迎批评指正！
欢迎点赞，系列二会更新非线性可分的SVM或者kernel

最后编辑于：2021.07.12 21:43:46

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

支持向量机SVM——原理及相关数学推导 系列一