机器学习算法_支持向量机SVM(1)

SVM支持向量机

简介

SVM(support vector machine)是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使其区别于感知机，感知机只是找到一个分离超平面。

SVM是非线性分类器
学习策略：间隔最大化，等价于求解凸二次规划问题或者说正则化的合页损失函数的最小化问题
学习算法：求解凸二次规划的最优化算法

线性可分支持向量机

思想

学习目标：在特征空间中找到一个分离超平面S，由 $w \bullet x+b=0$ 决定，将实例分成不同的正类和负类
$w$ 是法向量， $b$ 是截距。法向量指向的那侧是正类，另一侧是负类
通过间隔最大化求出的分离超平面具有唯一性

定义线性可分支持向量机

分离超平面 $w^* \bullet x+b^* =0$
分类决策函数
- 到决策函数的距离大于1，表示正类
- 到决策函数的距离小于1，表示负类

函数间隔和几何间隔

一个点到分离超平面的距离可以表示分类预测的确信程度。通常使用 $|w \bullet x+b|$ 来表示点x到超平面的远近

$w \bullet x+b > 0，y = +1$ 或者 $w \bullet x+b < 0，y = -1$ 都表示将将数据正确分类：即 $w \bullet x+b$ 和类标记 $y$ 的符号是一致的
在给定数据集T，超平面 $(w,b)$ 关于样本点 $(x_i,y_i)$ 的函数间隔： $\hat \gamma_i=y_i(w \bullet x_i+b)$ 定义：超平面 $(w,b)$ 关于训练数据集T的函数间隔，为所有T中样本点的函数间隔的最小值： $\hat \gamma=\mathop {\min}\limits_{i=1,2,...,N} \hat \gamma_i$

函数间隔表示分类预测的准确性和确信度。当 $w,b$ 成比例的变化时，超平面并没有变化，因此需要规范化，加上 $||w||$ ，此时变成了几何间隔。

$几何间隔=\frac {函数间隔} {||w||}$

点到超平面的距离

设样本点A到超平面 $(w,b)$ 的距离为 $\gamma_i$

如果点在超平面正的一侧，即： $y_i = +1$ ，距离为： $\gamma_i=\frac {w \bullet x_i+b} {||w||}$
如果点在超平面负的一侧，即： $y_i = -1$ ，距离为： $\gamma_i=-(\frac {w \bullet x_i+b} {||w||})$

统一地：当样本点被超平面正确分类时，点到超平面的距离为 $\gamma_i=y_i(\frac {w \bullet x_i+b} {||w||})$ 那么，当 $||w||=1$ 时候，函数间隔和几何间隔是相等的。

如果 $w,b$ 等比例的变化，函数间隔相应的变化，但是几何间隔是不变的

间隔最大化

支持向量机学习的基本思想是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。几何间隔最大的分离超平面是唯一的。这里的间隔最大化称之为硬间隔最大化。

硬间隔最大化不仅能够将正负实例点分开，还能将最难分的实例点（距离超平面最近的点）也能分开，对应的模型为 $\mathop {\max} \limits_{w,b}\gamma$
$s.t. \qquad y_i({w \bullet x_i+b}{||w||}) \geq {\gamma}$ 意思：

最大化几何间隔
约束条件表示的是超平面关于每个训练样本点的距离至少是 $\gamma$

根据函数间隔和几何间隔的关系 ${\gamma}=\frac {\hat \gamma}{||w||}$ ，模型还可以表示为： $\mathop {\max} \limits_{w,b}\frac {\hat \gamma}{||w||}$
$s.t. \qquad y_i(w \bullet x_i+b) \geq {\hat \gamma}$

函数间隔不影响模型，就取 $\hat \gamma=1$ ，那么最小化 $\frac {1}{||w||}$ 和最小化 $\frac{1}{2}||w||^2$ 等价（ $\frac{1}{2}$ 方便求导）

线性可分支持向量机的最优化问题可以表示为凸二次优化问题：

最小化法向量： $\mathop \min \limits_{w,b}\frac{1}{2} ||w||^2$

约束条件： $s.t. \qquad y_i(w \bullet x_i+b) \geq 0,i=1,2,...,N$ 求解出上述两个的式子的解 $w^*,b^*$ 就可以求出分离超平面 $w^* \bullet x+b^*$ 和决策函数 $f(x)=sign(w^* \bullet x+b^*)$

对偶问题

将线性可分支持向量机的最优化问题，通过拉格朗日对偶性，转换成求解对偶问题，得到对偶问题的最优解

对偶问题更好求解
自然引入核函数，推广到非线性支持向量机

如何构建对偶形式：

引入拉格朗日乘子 $alpha_i \geq 0, i=1,2,3...,N$ ，构建拉格朗日函数： $L(w,b,\alpha)=\frac{1}{2}||w||^2 - \sum^N_{i=1}\alpha_iy_i(w \bullet x_i+b)+\sum ^N_{i=1}\alpha_i$ 其中 $\alpha=(\alpha_1,\alpha_2,...,\alpha_N)^T$ 为拉格朗日乘子向量
原始问题的对偶问题是极大极小问题 $\mathop \max \limits_a \mathop \min \limits_{b,\alpha} L(w,b,\alpha)$
$L$ 先对 $w,b$ 求解极小，再对 $\alpha$ 求解极大值
具体过程见 $P_{120}-P_{123}$

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