统计学习方法笔记08

李航. 统计学习方法[M]. 清华大学出版社, 2012.

第7章支持向量机

7.1 线性可分支持向量机与软间隔最大化

感知机利用误分类最小的策略，求得分离超平面，这时的解有无穷多个；线性可分支持向量机利用间隔最大化求分离超平面，解是唯一的。

函数间隔的定义

对于给定的训练数据集T和超平面 $(\omega,b)$ ，定义超平面关于样本点 $(x_i,y_i)$ 的函数间隔为

$\hat{\gamma_i}=y_i(\omega\cdot x_i+b)$

定义超平面关于数据集T的函数间隔为超平面关于T中所有样本点的函数间隔之最小值，即

$\hat{\gamma}=\min_{i=1,\dots,N}\hat{\gamma_i}$

几何间隔的定义

对于给定的训练数据集T和超平面 $(\omega,b)$ ，定义超平面关于样本点 $(x_i,y_i)$ 的几何间隔为

$\gamma_i = y_i \left( \dfrac{\omega}{||\omega||}\cdot x_i + \dfrac{b}{||\omega||} \right)$

定义超平面关于数据集T的几何间隔为超平面关于T中所有样本点的几何间隔之最小值，即

$\gamma = \min_{i=1,\dots,N} \gamma_i$

线性可分支持向量机学习的最优化问题：(令函数间隔 $\hat{\gamma}=1$ )

$\begin{aligned}& \min_{\omega} \dfrac{1}{2} ||\omega||^2 \\& \text{s.t.} \quad y_i(\omega\cdot x_i+b)-1\geq 0， i=1,2,\dots,N\end{aligned}$

求解上述最优化问题的解 $(\omega^*,b^*)$ ，即可得到最大间隔分离超平面 $\omega^*\cdot x+b^*=0$ 和分类决策函数 $f(x)=sign(\omega^*\cdot x+b^*)$ 。

最大间隔分离超平面的存在唯一性

若训练数据集T线性可分，则可将训练数据集中的样本点完全正确分开的最大间隔分离超平面存在且唯一。

在线性可分的情况下，训练数据集的样本点中与分离超平面最近的样本点的实例称为支持向量(support vector)。支持向量是满足 $y_i(\omega\cdot x_i+b)-1=0$ 的点。

正例点与负例点中的支持向量所在的两个超平面之间的距离称为间隔(margin)。间隔依赖于分离超平面的法向量，等于 $\dfrac{2}{||\omega||}$ 。

线性可分支持向量机学习算法

输入：线性可分训练集 $T=\{(x_i,y_i)\}$ ，其中 $x_i\in\mathbb{R}^n$ ， $y_i\in\{-1,+1\}$ ， $i=1,\dots,N$

输出：分离超平面和分类决策函数

(1) 构造并求解约束最优化问题

$\begin{aligned}\min_{\alpha} \quad & \dfrac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j(x_i\cdot x_j) - \sum_{i=1}^N \alpha_i \\\text{s.t.} \quad & \sum_{i=1}^N \alpha_i y_i = 0 \\& \alpha_i \geq 0, i=1,2,\dots,N\end{aligned}$

(2) 计算 $\omega^*=\sum_{i=1}^N \alpha_i^* y_ix_i$ ，并选择 $\alpha^*$ 的一个正分量 $\alpha_j^* > 0$ ，计算

$b^* = y_j - \sum_{i=1}^N \alpha^* y_i (x_i\cdot x_j)$

(3) 求得分离超平面 $\omega^*\cdot x+b^*=0$ 和分类决策函数 $f(x)=sign(\omega^*\cdot x+b^*)$ 。

7.2 线性支持向量机与软间隔最大化

通常情况是，训练数据中有一些特异点(outlier)，将这些特异点除去后，剩下大部分的样本点组合成的集合是线性可分的。

线性不可分的线性支持向量机的学习问题的凸二次规划(convex quadratic programming)问题（原始问题）为：

$\begin{aligned}\min_{\omega,b,\xi} \quad & \dfrac{1}{2}||\omega||^2 + C\sum_{i=1}^N \xi_i \\\text{s.t.} \quad & y_i(\omega\cdot x_i+b) \geq 1-\xi_i ,\quad i=1,2,\dots,N \\& \xi_i\geq 0, \quad i=1,2,\dots,N\end{aligned}$

线性支持向量机

对于给定的线性不可分的训练数据集，通过求解上述凸二次规划问题，得到的分离超平面为 $\omega^*\cdot x+b^*=0$ 以及相应的分类决策函数 $f(x)=sign(\omega^*\cdot x+b^*)$ 称为线性支持向量机。

对偶问题及其解

线性不可分凸二次规划问题的对偶问题是：

$\begin{equation}\begin{aligned}\min_{\alpha} \quad & \dfrac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j(x_i\cdot x_j) - \sum_{i=1}^N \alpha_i \\\text{s.t.} \quad & \sum_{i=1}^N \alpha_i y_i = 0 \\& 0 \leq \alpha_i \leq C, i=1,2,\dots,N\end{aligned}\end{equation}$

设 $\alpha^*=(\alpha_1^*,\dots,\alpha_N^*)^T$ 是上述对偶问题的一个解，若存在 $\alpha^*$ 的一个分量 $\alpha_j^* \in (0,C)$ ，则原始问题的解可按下式求得：

$\omega^* = \sum_{i=1}^N \alpha_i^* y_i x_i$

$b^* = y_j - \sum_{i=1}^N y_i \alpha_i^*(x_i\cdot x_j)$

支持向量

在线性不可分的情况下，对偶问题的解 $\alpha^*=(\alpha_1^*,\dots,\alpha_N^*)^T$ 中对应于 $\alpha_i^*>0$ 的样本点 $(x_i,y_i)$ 的实例 $x_i$ 称为支持向量（软间隔的支持向量）。

线性支持向量机原始最优化问题等价于以下最优化问题

$\min_{\omega,b} \sum_{i=1}^N [1-y_i(\omega\cdot x_i+b)]_+ + \lambda ||\omega||^2$

其中目标函数的第1项是经验损失或经验风险，函数 $L(y(\omega\cdot x+b))=[1-y(\omega\cdot x+b)]_+$ 称为合页损失函数(hinge loss function)。下标“+”相当于取正值的relu函数。合页损失函数对学习有更高的要求。

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

统计学习方法笔记08

第7章 支持向量机

7.1 线性可分支持向量机与软间隔最大化

7.2 线性支持向量机与软间隔最大化

推荐阅读更多精彩内容

第7章支持向量机