机器学习算法深度总结(4)-SVM

1. 间隔最大化分类

考虑二分类:
$f_{\omega,\gamma}(x) = \omega^Tx + \gamma$
$\omega$ 为分割样本的超平面的法线, $\gamma$ 为截距.

2018-08-29 at 上午9.27.png

对各样本间隔 $m_i=f_{\omega, \gamma}(x_i)y_i$ 为正时的 $\omega$ 和 $\gamma$ 学习.

闭集约束条件: $(\omega^Tx_i+\gamma)y_i \ge 1, \forall i = 1, \cdots, n$

以上 $\omega$ 和 $\gamma$ 存在时,称训练样本线性可分.

2. 硬间隔SVM

分割最充分的超平面为最优解, 对应正则化后的间隔的最小值:

2018-08-29 at 上午9.38.png

正则化间隔 $m_i$ :
$m_i = \frac{(\omega^Tx_i + \gamma)y_i}{\|\omega\|}$
$m_i$ 最小化:
$min\left\{\frac{(\omega^Tx_i + \gamma)y_i}{\|\omega\|}\right\}_{I=1}^n = \frac{1}{\|\omega\|}$

从几何学来讲, 间隔为两端的两个超平面 $\omega^Tx+\gamma=+1$ 和 $\omega^Tx+\gamma=-1$ 的间距的一半, 使这个间隔最大的超平面对应的分类器称为硬间隔支持向量机分类器:

3. 软间隔SVM

硬间隔SVM假定训练样本线性可分, 软件个SVM允许间隔计算出现少量误差:
$min_{\omega,\gamma,\varepsilon}\left[\frac{1}{2}\|\omega\|^2+C\sum_{i=1}^n\xi_i\right]\; 约束条件\;(\omega^Tx_i + \gamma)y_i \ge 1- \xi_i, \xi_i =\ge 0,\forall i=1,\cdots, n$

C>0是调整误差范围参数, C越大, $\sum_{i=1}^n\xi_i$ 越接近0, 软间隔SVM越接近硬间隔SVM.

通常的SVM指软间隔SVM.

2018-08-29 at 上午9.44.png

4. SVM求解

SVM最优化问题是目标函数为二次函数, 约束条件为线性的典型二次规划问题:

二次规划求解

导入拉格朗日变量:
$L( \omega, \gamma, \xi, \alpha, \beta) = \frac{1}{2}\|\omega\|^2 + C \sum_{i=1}^n\xi_i - \sum_{i=1}^n\alpha_i \left( ( \omega^T x_i+\gamma)y_i - 1 + \xi_i \right) - \sum_{i=1}^n\beta_i\xi_i$
考虑最优化问题等价表现形式--拉格朗日对偶问题:
$\underset{ \alpha, \beta}{max} \; \underset{ \omega, \gamma, \xi}{inf}\; L( \omega, \gamma, \xi, \alpha, \beta)\; s.t.\; \alpha \ge 0, \beta \ge 0$
根据最优解条件可得:
$\frac{\partial }{\partial \omega}L = 0 => \omega = \sum_{i=1}^n\alpha_iy_ix_i \\ \frac{\partial }{\partial \gamma}L = 0 => \sum_{i=1}^n\alpha_iy_i = 0 \\ \frac{\partial }{\partial \xi_i}L = 0 => \alpha_i + \beta_i = C, \forall i=1,\cdots,n$
消去松弛变量 $\xi_i$ 可得拉格朗日对偶问题如下公式:
$\hat \alpha = \underset{\alpha}{argmax}\left[\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j \right]\; 约束条件\;\sum_{i=1}^n\alpha_iy_i = 0, 0 \le \alpha_i \le C\;, \forall i = 1,\cdots,n$
上述最优化问题, 利用只有n个最优变量的二次规划问题, 求解比原始最优化问题跟高效. 原始的最优化问题:
$min_{\omega,\gamma,\xi}\left[\frac{1}{2}\|\omega\|^2+C\sum_{i=1}^n\xi_i\right]\; 约束条件\;(\omega^Tx_i + \gamma)y_i \ge 1- \xi_i, \xi_i =\ge 0,\forall i=1,\cdots, n$

拉格朗日对偶问题的解用 $\hat \alpha$ 表示, 则SVM的解 $\hat \omega$ 为:
$\hat\omega = \sum_{i=1}^n\hat \alpha_iy_i\mathbf x_i$
截距的解 $\hat \gamma$ :
$\hat \gamma = y_i - \sum_{j:\hat \alpha_i>0} \hat \alpha_jy_jx_i^Tx_j$

5. 稀疏性

KKT条件
对偶解的最优条件即KKT条件. 对偶变量和约束条件满足互补关系:
$\alpha_i(m_i-1+\xi_i) = 0,\beta_i\xi_i = 0,\forall i = 1, \cdots, n$
KKT条件:

KKT条件

6. 核映射

核映射非线性模型
核映射使得SVM可以应用于非线性模型. 使用非线性函数 $\psi$ 对输入样本 $\{x_i\}_{=1}^n$ 使用线性SVM分类器.这种特征空间内的线性分类器, 在输入空间是非线性分类器.

如果特征空间维数比输入空间维数d更高,则样本线性可分的可能性更大, 然而特征空间维数过大, 计算量也会响应增加.

核映射可显著降低计算量: 学习时, 线性SVM分类器样本空间输入只存在内积形式 $x_i^Tx_j=\langle x_i,x_j \rangle$ ; 非线性SVM分类器特征空间输入只存在内积形式 $\langle \psi(x_i), \psi(x_j) \rangle$

核映射优势:

通过核函数 $K( x,x')$ 定义内积 $\langle \psi(x_i), \psi(x_j)\rangle$ , 不需要知道特征变换 $\psi$ 具体是什么.
输入 $x$ 不是向量, 也可以正确分类.

常见的核函数:
多项式核函数
$K( x, x') = ( x^Tx' + c)^p$
高斯核函数
$K( x, x') = \exp\left(- \frac{\| x -x'\|^2}{2h^2}\right)$

核映射方法适用于只关注内积的任何算法, 如聚类分析, 降维,将现行算法轻松转化为非线性.

7. hinge损失的二乘求解

考虑将SVM分类作为最小二乘分类的扩展.
SVM分类器将0/1损失作为间隔 $m = f_\theta( x)y$ 的函数单调非增, 但是二乘 $L_2$ 损失不是单调非增, 直接应用有些不自然, 故考虑将如下Hinge损失作为代理损失:
$max\{0, 1-m\}$
Hinge损失在m<1时有线性递增趋势, 即分类错误时, 损失无穷递增

Hinge损失和0/1损失函数图像:

Hinge损失和0/1损失

Hinge损失最小化学习:
$min_{\theta} = \sum_{i=1}^nmax\{0, 1-f_{\theta}( x_i)y_i\}$

回顾线性分类问题和和模型分类问题
线性分类:
$f_{\omega, \gamma}(x) = \omega^Tx+\gamma = \sum_{i=1}^n\omega_ix_i + \gamma$

核模型分类问题:
$f_{\theta, \gamma} = \sum_{j=1}^n\theta_jK(x,x_j)+\gamma$

对核模型分类问题进行Hinge损失最小化学习, 引入核矩阵 $K_{i,j} = K(x_i, x_j)$ 的 $L_2$ 正则化项:
$\underset{\theta, \gamma}{min}[ C\sum_{i=1}^nmax\{0, 1- f_{\theta, \gamma}(x_i)y \} + \frac{1}{2}\sum_{i,j=1}^n\theta_i\theta_jK(x_i, x_j) ]$

最后编辑于：2018.10.13 17:35:23

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