目录
SVM 家族简史
SVM 是什么?
感知机模型
最大间隔
最大间隔的数学解
回到 SVM 最优化问题
SVM 家族简史
故事要从 20 世纪 50 年代说起, 1957 年, 一个叫做感知器的模型被提出,
1963 年, Vapnik https://en.wikipedia.org/wiki/Vladimir_Vapnik and https://en.wikipedia.org/wiki/Alexey_Chervonenkis , 提出了最大间隔分类器, SVM 诞生了.
1992 年, Vapnik 将核方法用于 SVM, 使 SVM 可以处理线性不可分数据
1995 年, Corts 和 Vapnik 引入了软间隔, 允许 SVM 犯一些错
最强版 SVM 出现了, 它将各式武学集于一身, 软间隔, 核方法,......,
1996 年, SVR(support vector regression)诞生, svm 家族又添一员, 回归任务也不在话下. 至此, SVM 家族成为机器学习界顶级家族之一. 关于 SVM 家族其他成员, 可以参阅这里 http://www.svms.org/history.html .
SVM 是什么?
是一种监督学习分类算法, 可以用于分类 / 回归任务
SVM 目标: 寻找最优分割超平面以最大化训练数据的间隔
什么是超平面?
在一维空间, 超平面是一个点
二维空间, 超平面是一条线
三维空间, 超平面是一个平面
更多维空间, 称为超平面
什么是最优分割超平面?
尽可能远离每一个类别的样本点的超平面
首先, 可以正确的将训练数据分类
其次, 拥有更好的泛化能力
那么如何找到这个最优超平面呢? 根据间隔
什么是间隔?
给定一个超平面, 超平面到最近的样本点之间的距离的 2 倍称为间隔.
在最初的 SVM 中, 间隔是一个强定义, 即硬间隔, 间隔之间不允许存在任何样本.(当数据中存在噪音时, 会产生一些问题, 所以后来软间隔被引入)
显然, 间隔 B 小于间隔 A. 可知:
如果超平面越接近样本点, 对应的间隔越小
超平面离样本点越远, 间隔越大
所以最优超平面对应最大间隔, SVM 就是围绕着这个间隔展开, 如何计算这个间隔?
感知机模型
感知机是什么?
是一种二元线性分类器
利用梯度下降法对损失函数进行极小化, 求出可将训练数据进行线性划分的分离超平面
感知机如何找到分离超平面?
定义目标函数, 优化求解
对分类超平面 $ f(x_i)=w^\top x+b$
初始化 \(w\)
循环对每个样本执行
\(\mathbf{w} \leftarrow \mathbf{w}+\alpha \operatorname{sign}\left(f\left(\mathbf{x}_{i}\right)\right) \mathbf{x}_{i}\) 如果 \(x_i\) 被误分类
直到所有数据被正确分类
最大间隔
对感知机来说, 后三个超平面都是对应的解. 显然最后一个是更优的解, 但是感知机并不知道, SVM 登场了. SVM 说, 既然间隔更大的超平面对应更优解, 那我就计算间隔.
怎么计算间隔?
可以用点到直线距离, 对超平面
如何找到最优超平面?
超平面和间隔是直接相关的.
如果有一个超平面, 可以根据样本计算间隔
如果有两个超平面界定了一个间隔, 我们可以找到第三个超平面
所以 寻找最大间隔 = 寻找最优超平面
如何找到最大间隔?
step1: 需要有 label 的数据集
step2: 选择两个超平面划分数据, 并且超平面之间没有数据
step3: 最大化两个超平面之间的距离(即为间隔)
说起来很简单, 下面我们从数学角度看如何求解这一问题.
step1: 数据集
样本 \(x_i\), 对应的 label \(y_i\in \{-1,1\}\), 含有 \(n\) 个样本的数据集表示为 \(D\)
$ D={(x_i,y_i)∣x_i∈R^p,y_i∈{−1,1}}$
step2: 选择两个超平面
假设数据 \(D\)是线性可分的
对于分类超平面 \(\bold w \cdot \bold x+b=0\) , 记为 \(H_0\), 选择另外两个超平面 \(H_1,H_2\) , 满足 \(H_0\)到 \(H_1\) 和 \(H_2\)等距, 分别定义如下:
\[\bold w \cdot \bold x+b = \delta\\ \bold w \cdot \bold x+b = -\delta \]
但是 \(\delta\) 是多少? 不确定. 为了简化问题, 我们假设 \(\delta=1\) , 为了确保两个超平面之间没有数据, 必须满足以下约束:
\[\bold w \cdot \bold x_i+b≥1,\qquad if \ y_i =1\\ \bold w \cdot \bold x_i+b≤−1,\quad if \ y_i=-1 \tag{1} \]
将式(1) 两边同时乘以 \(y_i\):
\[\bold y_i(\bold w \cdot \bold x_i+b)\geq 1,\qquad for \ 1 \leq i \leq n\tag{2} \]
step3: 最大化两个超平面之间的距离
最大化两个超平面之间距离, 怎么计算距离? 怎么最大化距离?
如何计算两个超平面之间距离?
记 \(H_0,H_1\) 分别为 \(\bold w \cdot \bold x+b=1,\bold w \cdot \bold x+b=−1\)
假如 \(x_0\) 为线上的点,\(m\) 记为两线间距离. 我们的目标: 求 $ m$
如果存在一个向量 \(\bold k\) , 满足 \(||\bold k||=m\) , 同时垂直于 \(H_1\), 我们就能在 \(H_1\) 找到对应的点 \(z_0\). 现在我们看看怎么找这个点?
首先定义 \(\bold u = \frac{\bold w}{\bold{||w||}}\) 为 \(\bold w\) 的单位向量, 单位向量模长等于 1, 即 \(\bold{||u||}=1\). 对一个标量乘以一个向量得到的结果是向量, 所以我们将 \(m\) 和单位向量 \(\bold{||u||}\) 的乘积记为 \(\bold k\).
\[\bold k = m\bold u=m \frac{\bold w}{\bold{||w||}} \]
根据向量加法 \(\bold z_0 = \bold x_0 + \bold k\), 如上图. 我们找到了 \(\bold x_0\) 对应的 \(\bold {z_0}\). 现在
\[\bold w \cdot \bold{z_0}+b=1 \\ \bold w \cdot (\bold{x_0+k})+b=1 \\ \bold w \cdot (\bold{x_0}+m \frac{\bold w}{\bold{||w||}})+b=1 \\ \bold w \cdot \bold{x_0}+m \frac{\bold {w \cdot w}} {\bold{||w||}}+b=1 \\ \bold w \cdot \bold{x_0}+m \frac{\bold {||w||^2 }} {\bold{||w||}}+b=1 \\ \bold w \cdot \bold{x_0}+m {\bold{||w||}}+b=1 \\ \bold w \cdot \bold{x_0}+b=1-m {\bold{||w||}} \\ \]
因为 \(\bold w \cdot \bold x_0+b=−1\), 所以
\[-1 = 1-m {\bold{||w||}} \\ m {\bold{||w||}} = 2 \\ m = \frac{2}{\bold{||w||}} \tag{3} \]
我们计算出了 \(m\) !!! 两个超平面之间的距离.
最大化间隔
上面我们只做了一件事, 计算间隔. 现在我们看看怎么最大化它
显然上述问题等价于:
\[minmize \ \bold{||w||} \\s.t.\quad y_i(\bold{w \cdot x_i}+b) \geq 1 \quad for \ i=1,2,\cdots,n\tag{4} \]
求解上述问题, 得到最优解, 我们就找到了最优超平面.
最大间隔的数学解
再探问题(4), 这是一个带不等式约束的最优化问题, 而且是 \(n\) 个约束(\(n\) 个点都需要满足). 这个问题很头疼, 好吧. 我们先偷个懒, 如果是无约束问题怎么求.
无约束问题最小化
对无约束问题, 表示为 \(f(\bold w)=\bold{||w||}\), 我们如何求函数 \(f\) 的局部极小值? 求导.
如果 \(f\) 二阶可导, 在点 \(\bold x^*\) 满足 \(\partial f(\bold x)=0, \partial^2f(\bold x^*)>0\), 则在 \(\bold {x}^*\) 处函数取极小值. 注意:\(\bold x\) 是一个向量, 导数为 0, 对应每个维度皆为 0.
对于无约束最小值为 0, 等式约束下最小值为 4.
等式约束
单个约束
假如有等式约束问题如下
\[\begin{array}{ll} \underset{x}{\operatorname{minimize}} & f(x) \\ \text { subject to } & g(x)=0 \end{array} \]
上面的问题相当于定义了一个可行域, 使得解只能在可行域内. 上图中表示可行域只有一个点, 因此问题很简单.
多个约束
对于带有多个等式约束的问题, 所有的约束必须都满足
\[\begin{array}{cl}\underset{\mathbf{x}}{\operatorname{minimize}} & f(\mathbf{x}) \\\text { subject to } & g(\bold x)=0 \\& h(\mathbf{x})=0\end{array} \]
上述等式约束问题怎么解? 猜猜这是谁
拉格朗日乘法
In mathematical optimization, the method of Lagrange multipliers is a strategy for finding the local maxima and minima of a function subject to equality constraints. (Wikipedia https://en.wikipedia.org/wiki/Lagrange_multiplier )
三步法:
对每个约束乘以拉格朗日乘子, 构建拉格朗日函数 \(L\)
求拉格朗日函数梯度
令梯度 \(\nabla L(\mathbf{x}, \alpha)=0\)
为什么拉格朗日乘法可以解等式约束问题? 我们来看看
\[\begin{array}{ll}\underset{x, y}{\operatorname{minimize}} & f(x, y)=x^{2}+y^{2} \\\text { subject to } & g_{i}(x, y)=x+y-1=0\end{array} \]
根据目标函数和约束函数, 我们可以画出等高线
将两张图合并到一起会发生什么(黑色箭头表示目标函数梯度方向, 白色箭头表示约束函数梯度方向)
回到约束函数 \(g(x,y)=x+y-1=0\), 我们找一找它在哪, 当 \(x=0\) 时 \(y=1\), 当 \(y=0\) 时 \(x=1\), 找到了, 在这里
发现什么了? 目标函数在约束函数处的梯度方向相同! 它们相切了, 而且只有一个点处的梯度方向完全相同, 这个点就是目标函数在约束下的的极小值.
why? 假如你处在上图最上面的箭头位置(值为 \(v\)), 在约束条件下, 只能在蓝线上移动, 你只能尝试向左或者向右找到更小的值. ok, 先尝试向左走, 发现值变大了(梯度方向也是左, 梯度指向函数上升最快的方向), 所以应该向右走, 直到走到切点处. 此时, 发现无论向那个方向走, 值都会变大, 因此, 你找到了极小值.
数学表示
如何表达在极小值处, 目标函数和约束函数梯度方向相同
\[\nabla f(x, y)=\lambda \nabla g(x, y) \]
乘 \(\lambda\) 干啥? 因为他们只是梯度方向相同, 大小不一定相等. \(\lambda\) 称为拉格朗日乘子.
(注意 \(\lambda\) 如果是负数, 两个梯度方向变为平行, 可以同时求极大极小值, 见例 1 https://en.wikipedia.org/wiki/Lagrange_multiplier .)
现在我们知道拉格朗日乘法为什么可以求等式约束问题, 那怎么求?
找到满足 \(\nabla f(x, y)=\lambda \nabla g(x, y)\) 的 \((x,y)\)
显然,\(\nabla f(x, y) - \lambda \nabla g(x, y)=0\), 定义函数 \(L\) 有:
\[L(x,y,\lambda ) = f(x,y)-\lambda g(x,y) \]
求导:
\[\nabla L(x, y, \lambda)=\nabla f(x, y)-\lambda \nabla g(x, y) \]
当导数为 0 时就找到了对应 \(f\) 和 \(g\) 梯度方向平行的点.
回到定义, 拉格朗日乘法只能解决等式约束问题, 那对下面的不等式约束问题怎么办?
不等式约束
\[\begin{array}{cl}\underset{\mathbf{x}}{\operatorname{minimize}} & f(\mathbf{x}) \\\text { subject to } & g(\bold x) \geq0\end{array} \]
Don't worry! 总有办法
对不等式约束问题, 同样可以使用拉格朗日乘数, 满足如下条件:
\[\begin{aligned}&g(x) \geq 0 \Rightarrow \lambda \geq 0\\&g(x) \leq 0 \Rightarrow \lambda \leq 0\\&g(x)=0 \Rightarrow \lambda \text { is unconstrained }\end{aligned} \]
- The KKT conditions are first-order necessary conditions for a solution of an optimization problem to be optimal
- \[\nabla \bold w L = \bold w- \sum_{
- i=1
- }^{
- m
- } \alpha_{
- i
- }y_{
- i
- }\mathbf{
- x
- }_{
- i
- }=0\\\frac{
- \partial L
- } {
- \partial b
- } = - \sum_{
- i=1
- }^{
- m
- } \alpha_{
- i
- }y_{
- i
- }=0\\y_{
- i
- }\left(\mathbf{
- w
- } \cdot \mathbf{
- x
- }_{
- i
- }\right)+b-1 \geq 0, \quad i=1, \ldots, m\\\alpha_i \geq0\\\alpha_i [y_{
- i
- }\left(\mathbf{
- w
- } \cdot \mathbf{
- x
- }_{
- i
- }\right)+b-1]=0 \]
来源: https://www.cnblogs.com/gongyanzh/p/12775231.html