SVM

SVM

作者: 水之心 | 来源:发表于2018-08-16 20:03 被阅读9次

SVM

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}$

相关文章

网友评论

机器学习中的数学

本文标题：SVM

本文链接：https://www.haomeiwen.com/subject/quaobftx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

栏目导航

机器学习中的数学

热点阅读

机器学习中的数学

关于我们|服务条款|联系我们|SVM|投稿指南|网站地图|RSS订阅|排版工具|手机版

提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网版权所有

备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！