机器学习算法之支持向量机

数学描述

训练数据及标签：
$\{(x_1,y_1), (x_2,y_2), \cdots, (x_N,y_N)\}$
超平面(Hyper plane)线性模型：
$\omega^Tx + b = 0$
线性可分定义：
$\{(x_i,y_i)\}_{i=1,\cdots,N}$
$\exists(\omega,b)$ ,使得对 $\forall i=1,\cdots,N$
$\begin {cases} \omega^Tx_i+b \geq 0 & y_i=+1 \\ \omega^Tx_i+b < 0 & y_i=-1 \end {cases}$
综合上述公式：
$y_i(\omega^Tx_i+b) \geq 0$

SVM线性模型：

目标函数：
$\min\limits_{\omega,b} \frac{1}{2} \mid \mid \omega \mid \mid^2$
约束条件：
$y_i(\omega^Tx_i+b) \geq 1, \quad i=1,2,\cdots,m$
上述优化问题是凸优化问题（二次规划问题，Quadratic Programming）或者无解，或者只有一个极值

目标条件（Objective Function）是二次项
限制条件是一次项

性能指标：

距离超平面最近的几个训练样本点，称为支持向量（Support Vectors），两个异类支持向量到超平面的距离之和为间隔（Margin），即性能指标。

定理1：

$\omega^Tx+b=0$ 和 $a\omega^Tx+ab=0$ 表示同一超平面，其中 $a\in\Re^+$ 。即 $(\omega,b)$ 满足公式，则 $(a\omega,ab)$ 也满足公式

定理2：点到平面的距离公式

平面方程： $\omega_1x+\omega_2y+b=0$ ，则点 $(x_0,y_0)$ 到该平面的距离：
$d = \frac {|\omega_1x_0 + \omega_2 y_0 + b|} {\sqrt {\omega_1^2 + \omega_2^2}}$
向量 $x_0$ 到超平面的距离：
$d = \frac {|\omega^Tx_0 + b|}{||\omega||}$
于是， $\exists a$ 使得 $(a\omega,ab)$ 在支持向量 $x_0$ 上有 $|\omega^Tx_0+b|=1$ ，则此时支持向量到平面的距离：
$d = \frac {1}{||\omega||}$
$y_i(\omega^Tx_i + b) \geq 1, \quad i=1,2,\cdots,m$

SVM非线性模型：

处理方法：在线性模型的基础上，修改目标函数和限制条件，于是:
目标函数：
$\min \frac {1}{2}||\omega||^2 + C\sum_{i=1}^N \xi_i$
限制条件：
$y_i(\omega^Tx_i + b) \geq 1 - \xi_i$
$\xi_i \geq 0$
注：在线性模型中加上松弛变量 $\xi_i \geq 0$ 和 $y_i(\omega^Tx_i + b) \geq 1 - \xi_i$ 的意义是允许部分数据未被正确分类（即提高泛化能力），而当 $\xi_i$ 值过大时模型无法有效分类，于是需要对 $\xi_i$ 的值进行限制。对于 $\frac {1}{2}||\omega||^2 + C\sum_{i=1}^N \xi_i$ ，其中 $C$ 为事先设定的参数， $\xi_i$ 值越大，对应的目标函数值越大，则参数越不满足最小化的要求。

SVM非线性模型

处理方法：低维到高维映射

原始样本空间并不存在一个能正确划分两类样本的线性超平面
解决方法：将样本从原始空间映射到一个更高维的特征空间，使其在该特征空间内线性可分。
证明：在特征空间中对部分数据点进行随机标注，特征空间的维度越高，线性可分的概率越大。当在无限维特征空间中，线性可分的概率为1.
核函数：已知将原始空间映射到更高维空间可使样本集线性可分，接下来只需要找到一个符合条件的映射 $\phi(x)$ ，即可解决线性不可分问题。

通过公式推导可知，我们可以不知道无限维映射 $\phi(x)$ 的显示表达，只要知道存在一个核函数（kernel function）映射后的目标函数仍然有解
$K(x_1,x_2) = \phi(x_1)^T\phi(x_2)$

常用的核函数：

线性内核(Linear)
$K(x_1,x_2) = x_1^Tx_2$
高斯核(Rbf)
$K(x_1,x_2) = e^{-\frac{||x_1-x_2||^2}{2\sigma^2}}=\phi(x_1)^T\phi(x_2)$
多项式核(Ploy)
$K(x_1,x_2) = (x_1^Tx_2 + 1)^d = \phi(x_1)^T\phi(x_2)$
Tanh核
$K(x_1,x_2) = \tanh (\beta x_1^Tx_2 + b)$
$\tanh(x) = \frac {e^x - e^{-x}}{e^x + e^{-x}}$
$K(x_1,x_2)$ 能写成 $\phi(x_1)^T\phi(x_2)$ 的充要条件:

交换性：
$K(x_1,x_2) = K(x_2,x_1)$
半正定性
$\forall c_i,x_i(i=1,\cdots,N)$ ，有：
$\sum_{i=1}^N \sum_{j=1}^N c_ic_jK(x_i,x_j) \geq 0$

原问题和对偶问题理论介绍：

已知映射 $\phi(x)$ ，则原优化问题的目标函数：
$\min\frac {1}{2}||\omega||^2 + C\sum_{i=1}^N \xi_i$
限制条件：
$y_i(\omega^T\phi(x_i) + b) \geq 1-\xi_i(i=1,\cdots,N)$
当下的问题是，在已知核函数 $K(x_1,x_2)$ ，不知 $\phi(x)$ 的情况下，如何求解优化问题？

对偶理论

原问题(Prime Problem)目标函数：
$\min f(\omega)$
限制条件：
$g_i(\omega) \leq 0 (i=1,\cdots,K)$
$h_i(\omega) = 0 (i=1,\cdots,M)$
对偶问题(Dual Problem)目标函数：
$\max \theta(\alpha,\beta) = \inf _{\forall \omega}\{L(\omega,\alpha,\beta)\}$
其中：
$L(\omega,\alpha,\beta) = f(\omega) + \sum_{i=1}^K \alpha_ig_i(\omega) + \sum_{i=1}^M \beta_ih_i(\omega) = f(\omega) + \alpha^Tg(\omega) + \beta^Th(\omega)$
限制条件：
$\alpha_i \geq 0 (i=1,\cdots,K)$
$\inf _ {\omega}\{L(\omega,\alpha,\beta)\}$ 表示在限定 $\alpha,\beta$ 的条件下，遍历全部的 $\omega$ 的最小值。于是，每确定一组 $\alpha,\beta$ 值都能得到一个最小值，对偶问题的解就是所有最小值中的最大值。

定理1：

如果 $\omega^*$ 是原问题的解，而 $\alpha^*,\beta^*$ 是对偶问题的解，则有：
$f(\omega^*) \geq \theta(\alpha^*,\beta^*)$

定理2：

$G=f(\omega^*) - \theta(\alpha^*,\beta^*) \geq 0$ 叫做原问题与对偶问题的间距(Duality Gap)

定理3：强对偶定理

若 $f(\omega)$ 为凸函数，且 $g(\omega) = A\omega + b,h(\omega) = c\omega + d$ ，则此优化问题的原问题与对偶问题间距为0，即 $f(\omega^*) = \theta(\alpha^*,\beta^*)$

定理4：KKT条件

对于 $\forall i=1,\cdots,K$ ，或者 $\alpha_i^*=0$ ，或者 $g_i^*(\omega^*) = 0$

综合上述公式：

非线性模型的原问题(Prime Problem)目标函数：
$\min f(\omega)$
限制条件：
$g_i(\omega) \leq 0 \mid i=1,\cdots,K$
对偶问题(Dual Problem)目标函数：
$\max \theta (\alpha,\beta) = \inf_{\forall \omega}\{L(\omega,\alpha,\beta)\}$
其中：
$L(\omega,\alpha,\beta) = f(\omega) + \sum_{i=1}^K \alpha_ig_i(\omega) + \sum_{i=1}^M \beta_ih_i(\omega)$
限制条件：
$\alpha_i \geq 0 \mid i=1,\cdots,K$
KKT条件：

对于 $\forall i=1,\cdots,K$ ，或者 $\alpha_i^*=0$ ，或者 $g_i^*(\omega^*) = 0$

SVM非线性模型将SVM原问题化成对偶问题

改变原问题形式，满足强对偶定理
原问题的目标函数:
$\min \frac {1}{2} ||\omega||^2 - C\sum_{i=1}^N\xi_i$
限制条件：
$\begin {cases} 1+\xi_i-y_i\omega^T\phi(x_i) - y_ib \leq 0 \\ \xi_i \leq 0 \end {cases}$
对偶问题的目标函数:
$\max \theta (\alpha,\beta) = \inf_{\omega, \xi_i,b} \{\frac{1}{2}||\omega||^2 - C\sum_{i=1}^N\xi_i + \sum_{i=1}^N\beta_i\xi_i + \sum_{i=1}^N\alpha_i[1 + \xi_i - y_i\omega^T\phi(x_i) - y_ib]\}$
限制条件：
$\begin {cases} \alpha_i \geq 0 \mid i=1,\cdots,N \\ \beta_i \geq 0 \mid i=1,\cdots,N \end {cases}$

推导过程

$L(\omega,\alpha,\beta)$ 的极值点在偏导为0处，于是：
$\frac {\partial L}{\partial \omega} = 0 \rightarrow \omega = \sum_{i=1}^N \alpha_i y_i \phi(x_i)$
$\frac {\partial L}{\partial \xi_i} = 0 \rightarrow \beta_i + \alpha_i = C$
$\frac {\partial L}{\partial b} = 0 \rightarrow \sum_{i=1}^N \alpha_i y_i = 0$
处理 $\frac {1} {2} \mid \mid \omega \mid \mid ^2$ ，可得：
$\frac {1}{2} ||\omega||^2 = \frac {1}{2} \omega^T\omega = \frac {1}{2} (\sum_{i=1}^N \alpha_iy_i\phi(x_i))^T (\sum_{j=1}{N} \alpha_jy_j\phi(x_j)) = \frac {1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i\alpha_jy_iy_j\phi(x_i)^T\phi(x_j)$
对偶问题化简，目标函数：
$\max \theta(\alpha,\beta) = \sum_{i=1}^N \alpha_i - \frac {1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j K(x_i,x_j)$
限制条件：
$\begin {cases} 0 \leq \alpha_i \leq C \\ \sum_{i=1}^N \alpha_iy_i = 0 \end {cases}$
利用SMO算法求解上述最优化问题
注：正常流程是根据对偶问题的解求出参数 $\omega,\phi,b$ ，没必要
$\omega^T\phi(x) = \sum_{i=1}^T [\alpha_iy_i\phi(x_i)]^T\phi(x) = \sum_{i=1}^N \alpha_iy_i\phi(x_i)^T\phi(x) = \sum_{i=1}^N \alpha_iy_iK(x_i,x)$
利用KKT条件求 $b$ , $\forall i = 1, \cdots, N$
第一种情况：
要么 $\beta_i = 0$ ，要么 $\xi_i = 0$
第二种情况：
要么 $\alpha_i = 0$ ，要么 $1 + \xi_i - y_i\omega^T\phi(x_i)-y_ib=0$
于是，取一个 $0 < \alpha_i < C \rightarrow \beta_i = C - \alpha_i >0$ 。此时， $\beta_i \neq 0 \rightarrow \xi_i = 0$ ，同时， $\alpha_i \neq 0 \rightarrow 1 - y_i\omega^T\phi(x_i) - y_ib = 0$
最终解得：
$b = \frac {1 - y_i\omega^T\phi(x_i)}{y_i} = \frac {1 - y_i\sum_{j=1}^N \alpha_jy_jK(x_i,y_j)}{y_i}$

SVM算法流程：

训练流程：

输入：
$\{ (x_i, y_i) \} _{i=1,\cdots,N}$
目标函数：
$\max \theta(\alpha) = \sum_{i=1}^N \alpha_i - \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i\alpha_jy_iy_jK(x_i,x_j)$
限制条件：
$\begin {cases} 0 \leq \alpha_i \leq C \\ \sum_{i=1}^N \alpha_iy_i = 0 \end {cases}$
计算 $b$ ，找一个 $0<\alpha_i<C$
$b = \frac {1 - y_i \sum_{j=1}^N \alpha_jy_jK(x_i,x_j)}{y_i}$

SVM测试流程：

输入测试样本 $x$ ，其中：
$\begin{cases} \sum_{i=1}^N \alpha_iy_iK(x_i,x)+b \geq 0 & y = +1 \\ \sum_{i=1}^N \alpha_iy_iK(x_i,x)+b < 0 & y = -1 \end{cases}$

最后编辑于：2021.12.15 22:35:51

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

机器学习算法之支持向量机

数学描述

SVM线性模型：

性能指标：

定理1：

定理2：点到平面的距离公式

SVM非线性模型：

SVM非线性模型

常用的核函数：

原问题和对偶问题理论介绍：

对偶理论

定理1：

定理2：

定理3：强对偶定理

定理4：KKT条件

综合上述公式：

SVM非线性模型 将SVM原问题化成对偶问题

推导过程

SVM算法流程：

训练流程：

SVM测试流程：

推荐阅读更多精彩内容

SVM非线性模型将SVM原问题化成对偶问题