SVM

图片发自简书App

Input: 设有数据集 $\mathcal{D} = \{x_i,y_i \}_{i=1}^m$ , 令 $X = [x_1^T; \cdots; x_m^T], y = [y_1; \cdots; y_m]$ , 其中 $y_i\in \{1,-1\}$

可以将数据集 $\mathcal{D}$ 看作线性空间中的点. 数据集 $\mathcal{D}$ 中的点 $x_i$ 到超平面 $y = x^Tw + b$ 的距离为
$\frac{|b + (x_j, w)|}{||w||}$

因而, 正负超平面的距离为
$d = \frac{2}{||w||}$

$d$ (被称为间隔, margin) 越大, 则各个样本对于自身类别的预测估计愈自信, 因而, 我们需要将 $d$ 最大化. 即
$\begin{cases} \displaystyle \max_{w,b} &\frac{2}{||w||}\\ s.t. &y_i(w^Tx_i + b) \geq 1, & i= 1,2,⋯,m \end{cases}$
等价于
$\begin{cases} \displaystyle \min_{w,b} &\frac{||w||^2}{2}\\ s.t.&y_i(w^Tx_i + b) \geq 1, & i= 1,2,⋯,m \end{cases}$

该问题可以通过拉格朗日乘子法求解:
引入拉格朗日乘子 $λ = \{λ_1,\cdots,λ_m\}, λ \succeq 0$ , 有
$L(w, b ,λ) = \frac{||w||^2}{2} + ∑_{i=1}^m λ_i(1-y_i(w^Tx_i+b))$

由 $\frac{∂L}{∂w}=0$ , $\frac{∂L}{∂b}=0$ 得
$\begin{cases} w = \sum_{i=1}^m λ_iy_ix_i = [x_1,\cdots,x_m][λ_1y_1;\cdots;λ_my_m] = X^T (λ \circ y)\\ 0 = \sum_{i=1}^m λ_iy_i = \vec{1}^T (λ \circ y) \end{cases}$

消去 $w,b$ , 得到 (7) 式的对偶问题

$\begin{cases} \displaystyle\max_{λ} & \vec{1}^Tλ - 0.5 (λ ∘ y)^T XX^T (λ ∘ y)\\ s.t. &\vec{1}^T (λ \circ y)=0, λ \succeq 0 \end{cases}$

为了更加高效解决 (9) 的问题, 人们提出了一种高效的算法: SMO. SMO 之所以高效, 恰由于在固定其他参数, 仅仅优化两个的参数的过程便将二次规划问题转换为具有闭式解的二次规划问题.

前面的讨论是建立在数据集是线性可分的情况下的, 对于线性不可分的情况, 我们可以引入核函数.

令 $φ(x)$ 表示将 $x$ 映射后的特征向量, 于是在特征空间中划分超平面所对应的模型可以表示为
$f(x) = w^T\phi(x) + b$
这样 (9) 便可转换为

$\begin{cases} \displaystyle\max_{λ} & \vec{1}^Tλ - 0.5 (λ ∘ y)^T \phi(X)\phi(X)^T (λ ∘ y)\\ s.t. &\vec{1}^T (λ \circ y)=0, λ \succeq 0 \end{cases}$

最后编辑于：2019.12.26 00:45:12

禁止转载，如需转载请通过简信或评论联系作者。

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

SVM

推荐阅读更多精彩内容