泰州论坛:SVM家族(一)

admin 3个月前 (07-20) 科技 60 1

目录
  • SVM家族简史
  • SVM是什么?
  • 感知机模子
  • 最大距离
  • 最大距离的数学解
  • 回到SVM最优化问题

SVM家族简史

故事要从20世纪50年代提及,1957年,一个叫做感知器的模子被提出,

1963年, Vapnik and Chervonenkis, 提出了最大距离分类器,SVM降生了。

1992年,Vapnik 将核方式用于SVM,使SVM可以处置线性不可分数据

1995年,Corts和Vapnik引入了软距离,允许SVM犯一些错

最强版SVM泛起了,它将各式武学集于一身,软距离、核方式、……,

1996年,SVR(support vector regression)降生,svm家族又添一员,回归义务也不在话下。至此,SVM家族成为机械学习界顶级家族之一。关于SVM家族其他成员,可以参阅这里。

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家族(一) 第1张

对感知机来说,后三个超平面都是对应的解。显然最后一个是更优的解,然则感知机并不知道,SVM登场了。SVM说,既然距离更大的超平面对应更优解,那我就盘算距离。

怎么盘算距离?

可以用点到直线距离,对超平面

若何找到最优超平面?

超平面和距离是直接相关的。

泰州论坛:SVM家族(一) 第2张

  • 若是有一个超平面,可以凭据样本盘算距离
  • 若是有两个超平面界定了一个距离,我们可以找到第三个超平面

以是 寻找最大距离 = 寻找最优超平面

若何找到最大距离?

​ 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\)线性可分的

    泰州论坛:SVM家族(一) 第3张

    对于分类超平面 \(\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: 最大化两个超平面之间的距离

    最大化两个超平面之间距离,怎么盘算距离?怎么最大化距离?

    若何盘算两个超平面之间距离?

    泰州论坛:SVM家族(一) 第4张

    \(H_0,H_1\) 划分为 \(\bold w \cdot \bold x+b=1,\bold w \cdot \bold x+b=−1\)

    如果 \(x_0\) 为线上的点,\(m\) 记为两线间距离。我们的目的:求 $ m$

    泰州论坛:SVM家族(一) 第5张

    若是存在一个向量 \(\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。

    泰州论坛:SVM家族(一) 第6张

    对于无约束最小值为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} \]

      上述等式约束问题怎么解?猜猜这是谁

      泰州论坛:SVM家族(一) 第7张

    拉格朗日乘法

    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)

    三步法:

    1. 对每个约束乘以拉格朗日乘子,构建拉格朗日函数 \(L\)
    2. 求拉格朗日函数梯度
    3. 令梯度 \(\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} \]

    泰州论坛:SVM家族(一) 第8张

    凭据目的函数和约束函数,我们可以画出等高线

    泰州论坛:SVM家族(一) 第9张

    将两张图合并到一起会发生什么(玄色箭头示意目的函数梯度偏向,白色箭头示意约束函数梯度偏向)

    泰州论坛:SVM家族(一) 第10张

    回到约束函数 \(g(x,y)=x+y-1=0\),我们找一找它在哪,当\(x=0\)\(y=1\),当 \(y=0\)\(x=1\),找到了,在这里

    泰州论坛:SVM家族(一) 第11张

    发现什么了?目的函数在约束函数处的梯度偏向相同!它们相切了,而且只有一个点处的梯度偏向完全相同,这个点就是目的函数在约束下的的极小值

    why?如果你处在上图最上面的箭头位置(值为 \(v\)),在约束条件下,只能在蓝线上移动,你只能实验向左或者向右找到更小的值。ok,先实验向左走,发现值变大了(梯度偏向也是左,梯度指向函数上升最快的偏向),以是应该向右走,直到走到切点处。此时,发现无论向谁人偏向走,值都市变大,因此,你找到了极小值。

    • 数学示意

      若何表达在极小值处,目的函数和约束函数梯度偏向相同

      \[\nabla f(x, y)=\lambda \nabla g(x, y) \]

      \(\lambda\) 干啥?由于他们只是梯度偏向相同,巨细不一定相等。 \(\lambda\) 称为拉格朗日乘子。

      (注重 \(\lambda\) 若是是负数,两个梯度偏向变为平行,可以同时求极大极小值,见例1.)

    现在我们知道拉格朗日乘法为什么可以求等式约束问题,那怎么求?

    • 找到知足\(\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} \]

    为什么呢?由于可行域。看图就知道了,在等式约束部门\(x+y-1=0\) 时,可行域在直线上;当\(x+y-1 \geq 0\) 时,可行域在右上角,\(\lambda\) 大于0示意梯度偏向指向可行域;同理可知小于即是的情形。然后和等式约束求解历程一样就可以了。关于拉格朗日对约束问题例子,推荐阅读[3].

    泰州论坛:SVM家族(一) 第12张

    我们在来看看对偶问题

    • 对偶问题

      In mathematical optimization theory, duality means that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem (the duality principle). The solution to the dual problem provides a lower bound to the solution of the primal (minimization) problem. (Wikipedia)

      “对偶问题是原问题的下界”,下界是啥?

      给定一个部门有序聚集 \(R\) ,若是存在一个元素小于或即是 \(R\) 的子集的每个元素,该元素就可以称为下界。百度百科

      举个栗子:

      给定 \(R\) 的一个子集:\(S = \{2,4,8,12\}\)

      1.  1 小于 $S$ 中每个元素, 1 可以是一个下界
      2.  2 小于即是$S$ 中每个元素, 2 也可以是一个下界
      

      由于 2 大于其他的下界,被称为 下确界 (最大下界)。下界有无限个,但最大下界是唯一的。

      回到对偶问题

      若是原问题是一个极小问题,对偶问题可以将其转化为求极大问题。极大问题的解就对应原极小问题的下界。有点不解其意,继续看

      泰州论坛:SVM家族(一) 第13张

      上图原问题是一个极小问题, \(P\) 是极小点。对偶问题是一个极大问题, \(D\) 是极大点。很明显, \(D\) 是一个下界。 \(P-D\) 被称为对偶距离,若是 \(P-D>0\) 对应弱对偶性。若是 \(P-D=0\) 对应强对偶性。

      泰州论坛:SVM家族(一) 第14张

回到SVM最优化问题

为了求解利便,将等式(4)改写为凸二次型优化问题(convex quadratic optimization problem),

\[\begin{aligned}&\underset{\mathbf{w}, b}{\operatorname{minimize}} \frac{1}{2}\|\mathbf{w}\|^{2}\\&\text { subject to } y_{i}\left(\mathbf{w} \cdot \mathbf{x}_{i}\right)+b-1 \geq 0, \quad i=1, \ldots, m\end{aligned}\tag{5} \]

凭据拉格朗日乘数法:

\[\mathcal{L}(\mathbf{w}, b, \alpha)= \frac{1}{2}\|\mathbf{w}\|^{2}-\sum_{i=1}^{m} \alpha_{i}\left[y_{i}\left(\mathbf{w} \cdot \mathbf{x}_{i}+b\right)-1\right]\\= \frac{1}{2}\mathbf{w}\mathbf{w}-\sum_{i=1}^{m} \alpha_{i}\left[y_{i}\left(\mathbf{w} \cdot \mathbf{x}_{i}+b\right)-1\right]\tag{6} \]

可以转化为:

\[\begin{aligned}&\min _{\mathbf{w}, b} \max _{\alpha} \mathcal{L}(\mathbf{w}, b, \alpha)\\&\text { subject to } \quad \alpha_{i} \geq 0, \quad i=1, \ldots, m\end{aligned} \]

为什么原问题酿成极大极小问题了?这里有多个注释,直观来看,我们要$ min \ \mathcal{L}(\mathbf{w}, b, \alpha)$ ,由于后一项 \(\alpha >0,y_{i}\left(\mathbf{w} \cdot \mathbf{x}_{i}+b\right)-1 \geq0\),正数减正数,后一项越大对应整体值越小。

求解上述极大极小问题,求导:

\[\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\tag{7} \]

将(7)带回到(6)

\[\begin{aligned}&\frac{1}{2}\sum_{i=1}^{m} \alpha_{i}y_{i}\mathbf{x}_{i}\sum_{j=1}^{m} \alpha_{i}y_{i}\mathbf{x}_{i}-\sum_{i=1}^{m} \alpha_{i}\left[y_{i}\left((\sum_{j=1}^{m} \alpha_{i}y_{i}\mathbf{x}_{i}) \cdot \mathbf{x}_{i}+b\right)-1\right]\\&=\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_{i}\alpha_jy_{i}y_j\mathbf{x}_{i}\mathbf{x}_{j}-\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_{i}\alpha_jy_{i}y_j\mathbf{x}_{i}\mathbf{x}_{j}-b\sum_{i=1}^{m}\alpha_{i}y_{i}+\sum_{i=1}^{m}\alpha_{i}\\&=\sum_{i=1}^{m}\alpha_{i}-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_{i}\alpha_jy_{i}y_j\mathbf{x}_{i}\mathbf{x}_{j}-b\sum_{i=1}^{m}\alpha_{i}y_{i}\\&=\sum_{i=1}^{m}\alpha_{i}-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_{i}\alpha_jy_{i}y_j\mathbf{x}_{i}\mathbf{x}_{j}\end{aligned} \]

只剩下 \(\alpha\) 了, 凭据Wolfe dual problem:

\[\underset{\alpha}{maxmize}=\sum_{i=1}^{m}\alpha_{i}-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_{i}\alpha_jy_{i}y_j\mathbf{x}_{i}\mathbf{x}_{j}\\s.t.\ \alpha_i \geq0\\\sum_{i=1}^{m} \alpha_{i}y_{i}=0\tag{8} \]

  • KKT 条件

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 \]

回到式(8),同乘 -1 转化为极小问题

\[\underset{\alpha}{minmize}=\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_{i}\alpha_jy_{i}y_j\mathbf{x}_{i}\mathbf{x}_{j} - \sum_{i=1}^{m}\alpha_{i}\\s.t.\ \alpha_i \leq0\\\sum_{i=1}^{m} \alpha_{i}y_{i}=0\tag{9} \]

到此为止,我们只是给出了SVM最大距离的目的函数,若何优化求解,引入软距离,核方式,敬请期待。

迎接留言

references:

[1] http://www.robots.ox.ac.uk/~az/lectures/ml/lect2.pdf

[2] https://www.svm-tutorial.com/

[3] http://www.engr.mun.ca/~baxter/Publications/LagrangeForSVMs.pdf

,

诚信在线

诚信在线(www.hoteluniformcustom.com)现已开放诚信在线手机版下载。游戏公平、公开、公正,用实力赢取信誉。

皇冠体育声明:该文看法仅代表作者自己,与本平台无关。转载请注明:泰州论坛:SVM家族(一)

网友评论

  • (*)

最新评论

  • allbet登陆网址 2020-07-20 00:01:05 回复

    Sunbet授权的官方网站——Sunbet声誉最高。Sunbet开户无任何限制,Sunbet回馈多多,各种游戏模式让您享受刺激与美妙!Sunbet24小时为您服务!各方面都可以

    1

文章归档

站点信息

  • 文章总数:755
  • 页面总数:0
  • 分类总数:8
  • 标签总数:1285
  • 评论总数:395
  • 浏览总数:23318