SVM推导步骤

作者: Xuang123 | 来源:发表于2018-12-24 16:58 被阅读0次

SVM推导步骤
2018-05-14
SVM推导
推导svm
SVM推导过程 - 草稿
SVM面试级推导
超详细白板推导：从模型和优化 2 个角度详解 SVM 核函数
机器学习小组第十周打卡
2019-01-25
SVM入门笔记

SVM（Support Vector Machine，支持向量机）是最经典的分类算法，本文主要整理（为了应付考试）SVM的推导方式，不包含SMO算法求解最后的约束。

借鉴博客：
https://cuijiahua.com/blog/2017/11/ml_8_svm_1.html

https://www.cnblogs.com/90zeng/p/Lagrange_duality.html

一般的，SVM就是一个分类器，只是相对于传统的线性分类器，它添加了一个支持向量的概念。这样相对于传统分类器可能存在的多个解，SVM由于约束的存在一般只有单解，并且表现更好。

从图片上解释，对于一组数据，传统的线性分类器使用一条直线将数据分类，而SVM在使用直线的同时要求数据点距离这条直线的最小距离最大，也就是说分类器和数据之间要有足够大的“间隔”。这样做的好处是很明显的，越大的“间隔”代表了更大的转圜空间，在得到新的数据之后更容易将其正确分类。

而SVM的工作就是求解这个最大间隔，也就是最优化问题。对于线性可分的数据，可以直接套用线性规划的知识进行推导，但如果数据线性不可分，就需要核函数进行数据升维，进行超平面分类。

二分类问题的数据点

传统的线性分类器

SVM的分类方式，要求“间隔”最大

下面是具体的建模推导过程：

一·决策面方程

我们现在二维场景下考虑分类方程，所以决策面也就是决策线。

考虑在二维场景下，我们描述一条直线的方法是：

$y=ax+b$

简单替换，将 $y$ 替换为 $x_2$ ，将 $x$ 替换为 $x_1$ ，简单获得以下公式：

$x_2=ax_1+b$

=> $ax_1-x_2+b=0$

将上述公式转换为向量形式：

$[a,-1][\begin{array}{c} x_1 \\ x_2\end{array}] +b=0$

也就是 $\omega ^Tx+\gamma =0, 其中，\omega=[a,-1]^T,x=[x_1,x_2]^T$

这个式子的几何意义是原式子的法向量。而如果我们将上述式子推广到高维空间，就是我们需要的决策面方程。也就是：

$\omega ^Tx+\gamma =0, 其中，\omega=[\omega_1, \dots, \omega_n]^T,x=[x_1,\dots,x_n]^T$

二·分类间隔方程

在获取决策面方程之后，我们需要获知决策面方程中的 $\omega$ 和 $\gamma$ 的具体值，而求解这个值的核心就是靠分类间隔方程所施加的约束条件。

首先我们需要副系以下间隔的含义，在SVM中，“间隔”指的是分类器距离样本点的最小距离，我们需要找一个使这个最小距离最大的分类器作为我们的最优解。因此我们的约束条件是很好想到的，高中学过的距离公式：

$\begin{equation} \left\{ \begin{array}{**lr**} d=\frac{Ax_0+By_0+C}{\sqrt{A^2+B^2} } , & \\点(x_0,y_0),直线Ax+By+C=0\end{array} \right. \end{equation}$

而在超平面上，只需要简单的推广以上公式，结合我们之前获得的决策面方程，

$\omega ^Tx+\gamma =0, 其中，\omega=[\omega_1, \dots, \omega_n]^T,x=[x_1,\dots,x_n]^T$

我们不难得到，在我们所得到的直线（超平面上），某个样本与其的距离是：

$d=\frac{|\omega^Tx+\gamma|}{||\omega||}$

分母是指 $\omega$ 的二范数，也就是平方和求导。这样我们的问题就转化为，求最大的 $W$ ，其中 $W=2d$ ，也就是求 $\max \limits_{}d$ 。

三·约束条件

获取了上述分类间隔方程，但是这个方程只是来评判我们的分类器是否是好的，我们并不能确定

（1）分类器是否能正确分类

（2）如何选择正确的支持向量点

这两个问题是限制我们随意计算 $d$ 的限制条件，在SVM中，以下列方式处理这些限制条件。

首先仍然只考虑线性可分的二分类情况，在这种情况下只有两类数据，我们对这两类数据分别赋值为1和-1，也就是：

$y=\begin{equation} \left\{ \begin{array}{**lr**} 1 , 数据属于第一类& \\-1.数据属于第二类\end{array} \right. \end{equation}$

分类还是很直观的，事实上我们在有监督学习里面基本也这么赋值。这样赋值之后，假设我们所得到的分类器可以正确分类两类数据，那么我们的分类器可以得出什么结果？不难得到以下形式：

$y=\begin{equation} \left\{ \begin{array}{**lr**} \omega^T+\gamma>0, y_i=1& \\\omega^T+\gamma<0, y_i=-1\end{array} \right. \end{equation}$

如果我们严格一点（或者说运气很好），我们得到的分类器是SVM的最优解，那么根据上面的距离公式，我们可以简化得到：

$\begin{equation} \left\{ \begin{array}{**lr**} \frac{|\omega^Tx+\gamma|}{||\omega||}\ge d, y_i=1& \\\frac{|\omega^Tx+\gamma|}{||\omega||}\le -d, y_i=-1\end{array} \right. \end{equation}$ $\Rightarrow \begin{equation} \left\{ \begin{array}{**lr**} \omega_d^Tx+\gamma_d\ge 1, y_i=1& \\\omega_d^Tx+\gamma_d\le 1, y_i=-1\end{array} \right. \end{equation}$

其中：

$\omega_d^T=\frac{\omega}{||\omega||d}$ $\gamma_d=\frac{\gamma}{||\omega||d}$

分母都是标量，所以除以 $d$ 并不影响原式子的几何含义，也就是法向量。那么我们事实上拿掉这个 $d$

也不会影响最后的结果。最后对以上式子进行整理，即可获得一个不等式：

$y_i(\omega^Tx+\gamma)\ge 1, \forall x_i$

这里的 $\omega$ 与上文中的 $\omega$ 在数值上不同，但是在几何意义上是一样的。

四·优化问题描述

在三中，我们考虑了如果我们的分类器可以正确分类，我们的公式要如何进行约束，那么现在我们需要解决第二个问题了，如果选取支持向量点？

这个问题比较好考虑，支持向量点有一个特征，那就是对于一个支持向量点 $x_i$ ,必然有

$|\omega^Tx_i+\gamma| = 1$

那么在我们预先定义好的距离公式 $d=\frac{|\omega^Tx+\gamma|}{||\omega||}$ 中，我们发现带入上式子的结果，有

$d=\frac{1}{||\omega||}$

那么我们对 $d$ 的最大值约束就变化为对 $\omega$ 的最小值约束，也就是求解 $min\frac{1}{2}||\omega||^2,其中y_i(\omega^Tx_i+b)\ge 1,i=1,2,\dots,n$

五·求解准备

在得到上述式子之后，我们发现这是一个带有不等式约束的规划问题，为了解决这种问题，我们一般采用构造拉格朗日函数的方法，使用对偶性解决问题。

5.1·拉格朗日函数

首先，我们先要从宏观的视野上了解一下拉格朗日对偶问题出现的原因和背景。

我们知道我们要求解的是最小化问题，所以一个直观的想法是如果我能够构造一个函数，使得该函数在可行解区域内与原目标函数完全一致，而在可行解区域外的数值非常大，甚至是无穷大，那么这个没有约束条件的新目标函数的优化问题就与原来有约束条件的原始目标函数的优化问题是等价的问题。

这就是使用拉格朗日方程的目的，它将约束条件放到目标函数中，从而将有约束优化问题转换为无约束优化问题。

随后，人们又发现，使用拉格朗日获得的函数，使用求导的方法求解依然困难。进而，需要对问题再进行一次转换，即使用一个数学技巧：拉格朗日对偶。

所以，显而易见的是，我们在拉格朗日优化我们的问题这个道路上，需要进行下面二个步骤：

将有约束的原始目标函数转换为无约束的新构造的拉格朗日目标函数

使用拉格朗日对偶性，将不易求解的优化问题转化为易求解的优化

下面，进行第一步：将有约束的原始目标函数转换为无约束的新构造的拉格朗日目标函数

先写下原始式子：

$min\frac{1}{2}||\omega||^2,其中y_i(\omega^Tx_i+b)\ge 1,i=1,2,\dots,n$

我们首先将其变形，将其变为如下格式：

$L(\omega,b,\alpha)=\frac{1}{2}||\omega||^2-\sum_{i=1}^n \alpha_i[y_i(\omega^Tx_i+b)-1]$

其中 $\alpha_i \ge 0$ 被称为拉格朗日乘子，当然虽然名字很吓唬人，事实上它是我们随意引入的一个参数。这个参数是用来构造等价问题的。

我们令 $\theta(\omega,b)=\max \limits_ {\alpha_i \ge 0}\ L(\omega,b,\alpha)$ 。

也就是当前这个方程和 $\alpha_i$ 无关，当某个点 $x_i$ 不在可行解区域中，也就是 $y_i(\omega^Tx_i+b) < 1$ ,我们将 $\alpha_i$ 设置为无穷大，显然此时 $\theta(\omega,b)$ 也是无穷大的。而当该点在可行域区域内， $y_i(\omega^Tx_i+b) \ge 1$ ，那么 $\max \limits_ {\alpha_i \ge 0}\ L(\omega,b,\alpha)$ 的结果显然是 $\frac{1}{2}||\omega||^2$ （因为后半部分必然大于等于0，那么为了保证最大，当然是等于0）。这样， $\theta(\omega,b)$ 就可以转化为：

$\theta(\omega,b)=\begin{equation} \left\{ \begin{array}{**lr**} \frac{1}{2}||\omega||^2, x_i在可行域\\+\infty，x_i不在可行域\end{array} \right. \end{equation}$

显然在可行域内， $\theta$ 是一个凸函数，是必然有极小值的，因此问题被转化为求此函数的最小值，也就是：

$\min \limits_{\omega,b}\theta(\omega,b)=\min \limits_{\omega,b}\max\limits_{\alpha_i\ge0}L(\omega,b,\alpha)=p^*$

这个式子事实上也不好求，因为内层的 $max$ 仍然带有不等式的限制条件，因此我们要使用拉格朗日对偶方法将其转化为易求的对偶形式。

5.2 拉格朗日对偶及其证明

拉格朗日对偶的定义如下：

以我们刚刚获得的式子 $\min \limits_{\omega,b}\theta(\omega,b)=\min \limits_{\omega,b}\max\limits_{\alpha_i\ge0}L(\omega,b,\alpha)=p^*$ 为例，我们先针对 $\alpha$ 作为未知数构造一个函数：

$\theta(\alpha)=\min \limits_{\omega,b}L(\omega,b,\alpha)$

考虑其极大化，也就是 $\max\limits_{\alpha;\alpha_i\ge0}\theta(\alpha)=\max\limits_{\alpha;\alpha_i\ge0}\min \limits_{\omega,b}L(\omega,b,\alpha)$

这个问题就是原始问题的对偶问题了。假设我们使 $\max\limits_{\alpha;\alpha_i\ge0}\theta(\alpha)=\max\limits_{\alpha;\alpha_i\ge0}\min \limits_{\omega,b}L(\omega,b,\alpha)=d^*$

则可以证明 $d^*\le p^*$

证明方式：对于任意的 $\alpha,\omega和b$ ，有 $\theta_d(\alpha)=\min\limits_{\omega,b}L(\omega,b,\alpha)\le L(\omega,b,\alpha)\le \max\limits_{\alpha\ge 0}L(\omega,b,\alpha)\le \theta_p(\omega,b)$

不难推论，当 $d^*=p^*$ 时，此时 $\omega^*,b^*,\alpha^*$ 均为最优解。

那么如何使得上述相等情况成立呢？这就需要满足KKT条件。

5.3·KKT条件

KKT条件的全称是Karush-Kuhn-Tucker条件，KKT条件是说最优值条件必须满足以下条件：

条件一：经过拉格朗日函数处理之后的新目标函数L(w,b,α)对x求导为零：

条件二：h(x) = 0；

条件三：α*g(x) = 0；

我们的式子已经满足此条件，具体的嘛……反正我也不懂，先记下来以后补= =

六·最终结果

已知 $\max\limits_{\alpha;\alpha_i\ge0}\theta(\alpha)=\max\limits_{\alpha;\alpha_i\ge0}\min \limits_{\omega,b}L(\omega,b,\alpha)=d^*$

$L(\omega,b,\alpha)=\frac{1}{2}||\omega||^2-\sum_{i=1}^n \alpha_i[y_i(\omega^Tx_i+b)-1]$

首先固定 $\alpha$ ,针对内层最小化求导，可以得到：

$\frac{\alpha L}{\alpha \omega}=0 \Rightarrow \omega=\sum_{i=1}^n \alpha_iy_ix_i$

$\frac{\alpha L}{\alpha b}=0 \Rightarrow \sum_{i=1}^n \alpha_iy_i=0$

带入原式：

$\begin{equation}\begin{aligned}L(\omega,b,\alpha)&=\frac{1}{2}||\omega||^2-\sum_{i=1}^n \alpha_i[y_i(\omega^Tx_i+b-1) ] \\&=\frac{1}{2}\omega^T\omega-\omega^T\sum_{i=1}^n\alpha_iy_ix_i-b\sum_{i=1}^n\alpha_iy_i+ \sum_{i=1}^n\alpha_i \\&=\frac{1}{2}\omega^T\sum_{i=1}^n\alpha_iy_ix_i-\omega^T\sum_{i=1}^n\alpha_ix_iy_i-b*0+\sum_{i=1}^n\alpha_i\\&=\sum_{i=1}^n\alpha_i-\frac{1}{2}(\sum_{i=1}^n\alpha_iy_ix_i)^T\sum_{i=1}^n\alpha_iy_ix_i\\&=\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j\end{aligned}\end{equation}$

此时只有一个参数， $\alpha_i$

然后我们计算外层的最大化，

$\max\limits_{\alpha}\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j\\s.t.\ \alpha_i \ge0, \ \ i =1,2,\dots,n\\\sum_{i=1}^n\alpha_iy_i=0$

现在我们的优化问题变成了如上的形式。对于这个问题，我们有更高效的优化算法，即序列最小优化（SMO）算法。我们通过这个优化算法能得到α，再根据α，我们就可以求解出w和b，进而求得我们最初的目的：找到超平面，即"决策平面"。

七·非线性与核函数

前面六个部分都是建立在数据线性可分的情况之下，而当数据不可分时，我们需要使用一些方法将其升维，使其在高维空间成为可分的。

总体而言，经过SMO计算出 $\alpha$ 之后，可以得到最后的方程：

$f(x) = \sum_{i=1}^n\alpha_iy_ix_i^Tx + b$

使用内积表示它：

$f(x) = \sum_{i=1}^n\alpha_iy_i<x_i,x> + b$

如果数据是不可分的，我们使用一个非线性映射（不管这个映射是什么样的，事实上往往不知道这是什么映射，映射获得的结果也可能无法计算）将数据映射到高维空间，使其在高维空间可分，则上式可以改写为：

$f(x) = \sum_{i=1}^n\alpha_iy_i<\phi (x_i),\phi(x)> + b$

其中 $\phi(x)$ 是一个映射，它表示输入空间到特征空间的映射。

这种映射结果，牵扯到高维空间的内积运算，而高维空间维度越高我们需要的计算量就越大，有时候甚至是无限维的，导致不能直接计算。因此我们定义了一个核函数(kernel function)，其本质是在输入空间的一个函数 $\kappa$ ，我们如果可以使得 $\kappa(x_i, x)=<\phi(x_i),\phi(x)>$ ，那么计算就可以局限在输入空间的低纬度，减少计算资源的消耗。

所以直接就给出一个定义：核是一个函数k，对所有x,z∈X，满足k(x,z)=<ϕ(xi),ϕ(x)>，这里ϕ(·)是从原始输入空间X到内积空间F的映射。

在实际使用中，有多种比较常见的核函数形式（所以核函数实际上都是一种近似）：

常用的核函数

SVM推导步骤
SVM（Support Vector Machine，支持向量机）是最经典的分类算法，本文主要整理（为了应付考试）...
2018-05-14
SVM手动推导
SVM推导
SVM推导参考链接。问题分析：给定一个标注的数据集(x_{i},y_{i}), i=1,2,3,4……N，其中...
推导svm
梯度垂直于等高线，指向函数变化最快的方向，指向极大值点方向约束条件为等式求极值先来看个简单求极值例子先看下图...
SVM推导过程 - 草稿
title: SVM推导过程 date: 2019-03-12 08:25:33 tags: [svm, ml] ...
SVM面试级推导
序 SVM是面试中常问的模型之一，本次记录一下应对面试时SVM如何进行较为清晰和简洁的推导 SVM面试级推导（自写...
超详细白板推导：从模型和优化 2 个角度详解 SVM 核函数
在 SVM 白板推导| 由最大间隔化目标演化的损失函数推导过程中白板手推了 SVM 的原理，并介绍了硬间隔核函数...
机器学习小组第十周打卡
学习目标知识点描述：致敬真神：支持向量机学习目标： SVM算法原理及数学推导 SVM算法中的核函数 SVM算法...
2019-01-25
写出 svm 原始问题转换至其对偶问题的数学推导过程： 1 导包： from sklearn import svm...
SVM入门笔记
本文不是一篇正式的tutorial，只是帮助回忆和理解SVM推导的笔记。此文章会长期更新。分类问题 SVM（su...