支持向量机-算法概述

​ 我的微信公众号： s406205391; 欢迎大家一起学习，一起进步！！！

​ 有些人认为，支持向量机（SVM）是最好的现成的分类器，这里说的“现成”指的是分类器不加修改即可直接使用。同时，这就意味着在数据上应用基本形式的SVM分类器就可以得到低错误率的结果。SVM能够对训练集之外的数据点做出很好的分类决策。

​

​ 假设在一个平面上有如下两组数据，我们可以用如下一条直线将两组数据分隔开（我们将上述可以把数据集分隔开的直线称为分隔超平面）。图左和图右两条直线均可有效的将数据分隔开。那么，哪一条直线的分隔效果更好呢？很明显图右的直线分隔效果更好，因为它距离两组数据的距离相对于图左直线更远。支持向量就是离分隔超平面最近的那些点。

​ 那么，我们在设计分类器之前，就先得学会如何计算支持向量到分隔超平面之间的距离。假设由图点x是分隔超平面的支持向量，w是超平面上的法向量，w’和w’'是超平面上的两个点。我们定义超平面方程为wTx+b=0。那么我们可以得到两个等式：

w’和w’‘在超平面上：wTx’ = -b; WTx’’ = -b

法向量与w’和w’'的向量垂直：[wT(x′′−x′)]=0[w^T (x^{''} - x^{'})] = 0[wT(x′′−x′)]=0

​ 我们要求点到直线的距离，其实也就是求向量（x - x’）与法向量w的单位向量的投影（內积）。那么公式即为：distance(x,b,w)=∣wT∣∣w∣∣(x−x′)∣=1∣∣w∣∣∣wTx+b∣distance(x, b, w) = |\frac{w^{T}}{||w||}(x-x^{'})| = \frac{1}{||w||}|w^{T}x+b|distance(x,b,w)=∣∣∣w∣∣wT​(x−x′)∣=∣∣w∣∣1​∣wTx+b∣ 因为w’是随机找的一个点，因此必然可以约分，将w’约分完之后，即可得到最终的表达式。

​ 有了距离公式，那么也有了我们机器学习的优化方向：让支持向量与超平面的距离最远。在做SVM机器学习的时候，我们首先需要定义标签，即将我们的训练数据进行分类。在这里，为了后期计算方便，我们将数据分类两类，分别用1和-1表示。那么就有了如下的决策方程：

y(x)=wTϕ(x)+b⇒y(xi)>0⇔yi=+1y(xi)<0⇔yi=−1⇒y(i)⋅y(xi)>0y(x)=w^{T}\phi(x)+b \Rightarrow \begin{aligned}y(x_{i})>0 &\Leftrightarrow y_{i}=+1\\ y(x_{i})0y(x)=wTϕ(x)+b⇒y(xi​)>0y(xi​)0 这里的φ（x）我们可以先暂时理解为x

将距离公式带入到决策方程，可得：yi⋅(wT⋅ϕ(xi)+b)∣∣w∣∣\frac{y_{i} \cdot (w^{T} \cdot \phi(x_{i}) + b)}{||w||}∣∣w∣∣yi​⋅(wT⋅ϕ(xi​)+b)​ (由于yi⋅y(xi)>0y_{i} \cdot y(x_{i})>0yi​⋅y(xi​)>0, 所有将绝对值展开，公式依旧成立。)

对于该决策方程，我们设计优化目标，找到一条离支持向量的点最远的直线，优化目标如下：

目标函数: argmaxw,b{1∣∣w∣∣min[yi⋅(wT⋅ϕ(xi+b))]}argmax_{w,b}\left\{ \frac{1}{||w||} min[y_{i} \cdot (w^{T} \cdot \phi(x_{i} + b))] \right \}argmaxw,b​{∣∣w∣∣1​min[yi​⋅(wT⋅ϕ(xi​+b))]}

​ 上述的目标函数看起来很复杂，通俗的将，大括号内的意思即为，找到在整个样本中，距离决策边界距离最小的样本。大括号外面即，找到与这些这些样本距离最大的线。

放缩变换

​ 对于决策方程，不太好求解，我们这里可以做一下变换。我们通过放缩变换使得：对于决策方程（w,b）,其结果∣y∣>=1⇒yi⋅(wT⋅ϕ(xi)+b)>=1|y|>=1 \Rightarrow y_{i} \cdot (w^{T} \cdot \phi(x_{i}) + b) >= 1∣y∣>=1⇒yi​⋅(wT⋅ϕ(xi​)+b)>=1 (之前我们认为恒大于0，现在更严格了一些)

由于yi⋅(wT⋅ϕ(xi)+b)>=1y_{i} \cdot (w^{T} \cdot \phi(x_{i}) + b) >= 1yi​⋅(wT⋅ϕ(xi​)+b)>=1 , 那么，其最小值就为1，那么，我们只需要考虑argmaxw,b1∣∣w∣∣argmax_{w,b} \frac{1}{||w||}argmaxw,b​∣∣w∣∣1​。

当前目标：maxw,b1∣∣w∣∣max_{w,b} \frac{1}{||w||}maxw,b​∣∣w∣∣1​，约束条件：yi⋅(wT⋅ϕ(xi)+b)>=1y_{i} \cdot (w^{T} \cdot \phi(x_{i}) + b) >= 1yi​⋅(wT⋅ϕ(xi​)+b)>=1

函数变换

​ 对于上述目标函数，我们适当转换一下，方便求解。我们可以将上述函数的求最大值问题，改为求极小值问题：

转换函数 ⇒minw,b12w2\Rightarrow min_{w,b} \frac{1}{2}w^{2}⇒minw,b​21​w2

​ 转换思路为：先将1∣∣w∣∣\frac{1}{||w||}∣∣w∣∣1​转换成其倒数，再取其平方，再添加一个常规项1/2。虽然做了如下操作之后，最后得到的点的值会发生变换，但是，取到的点是不变的。

对于这个函数，我们可以用拉格朗日乘子法求解。

​ 拉格朗日乘子法是专门用来求解带约束条件的问题的。他的基本公式为：

​ minL(x,λ,w)=f0(x)+Σλifi(x)+Σvihi(x)min L(x, \lambda,w)=f_{0}(x) + \Sigma{\lambda_{i}f_{i}(x)} + \Sigma{v_{i}h_{i}(x)}minL(x,λ,w)=f0​(x)+Σλi​fi​(x)+Σvi​hi​(x)

​ 把我们的方程代入，即得：

​ L(w,b,α)=12∣∣w∣∣2−Σαi(yi(wT⋅ϕ(xi)+b)−1)L(w,b,\alpha)= \frac{1}{2}||w||^{2} - \Sigma{\alpha_{i}(y_{i}(w^{T} \cdot \phi(x_i) +b)-1)}L(w,b,α)=21​∣∣w∣∣2−Σαi​(yi​(wT⋅ϕ(xi​)+b)−1) 约束条件:yi(wT⋅Φ(xi)+b)>=1{y_i(w^T \cdot \Phi(x_i) + b)>=1}yi​(wT⋅Φ(xi​)+b)>=1

​ 上式有三个未知量，w, α,b。如果我们能求得这三个变量之间的关系，即可得到方程的解。我们分别对w和b求偏导，得：

​ 对w求偏导:∂L∂w=0⇒w=∑1−nαiyiΦ(xn)\frac{\partial L}{\partial w}=0 \Rightarrow w=\sum\limits_{1-n} {\alpha_{i}y_{i}\Phi(x_n)}∂w∂L​=0⇒w=1−n∑​αi​yi​Φ(xn​)

​ 对b求偏导:∂L∂b=0⇒0=∑1−nαiyi\frac{\partial L}{\partial b}=0 \Rightarrow 0=\sum\limits_{1-n}{\alpha_{i}y_{i}}∂b∂L​=0⇒0=1−n∑​αi​yi​

​ 我们带入原式即得：

​ L(w,b,α)=12∣∣w∣∣2−Σαi(yi(wT⋅ϕ(xi)+b)−1)L(w,b,\alpha)= \frac{1}{2}||w||^{2} - \Sigma{\alpha_{i}(y_{i}(w^{T} \cdot \phi(x_i) +b)-1)}L(w,b,α)=21​∣∣w∣∣2−Σαi​(yi​(wT⋅ϕ(xi​)+b)−1)

​ 其中：w=∑1−nαiyiΦ(xn)w=\sum\limits_{1-n} {\alpha_{i}y_{i}\Phi(x_n)}w=1−n∑​αi​yi​Φ(xn​); 0=∑1−nαiyi0=\sum\limits_{1-n}{\alpha_{i}y_{i}}0=1−n∑​αi​yi​

​ =12wTw−wT∑i=1nαiyiΦ(xi)−b∑i=1nαiyi+∑i=1nαi=\frac{1}{2}w^{T}w-w^{T}\sum\limits_{i=1}\limits^{n}\alpha_{i}y_{i}\Phi(x_{i}) - b\sum\limits_{i=1}\limits^{n}\alpha_{i}y_{i} + \sum\limits_{i=1}\limits^{n}\alpha_{i}=21​wTw−wTi=1∑n​αi​yi​Φ(xi​)−bi=1∑n​αi​yi​+i=1∑n​αi​

​ =∑i=1nαi−12(∑i=1nαiyiΦ(xi)T∑i=1nαiyiΦ(xi)=\sum\limits_{i=1}\limits^{n}\alpha_{i} - \frac{1}{2}(\sum\limits_{i=1}\limits^{n}\alpha_{i}y_{i}\Phi(x_{i})^T\sum\limits_{i=1}\limits^{n}\alpha_{i}y_{i}\Phi(x_{i})=i=1∑n​αi​−21​(i=1∑n​αi​yi​Φ(xi​)Ti=1∑n​αi​yi​Φ(xi​) 完成了第一步求解minL(w,b,α)

​ =∑i=1nαi−12∑i=1,j=1nαiαjyiyjΦT(xi)ΦT(xj)=\sum\limits_{i=1}\limits^{n}\alpha_{i} - \frac{1}{2}\sum\limits_{i=1,j=1}\limits^{n}\alpha_{i}\alpha_{j}y_i y_j \Phi^T(x_i)\Phi^T(x_j)=i=1∑n​αi​−21​i=1,j=1∑n​αi​αj​yi​yj​ΦT(xi​)ΦT(xj​) 求解该式的极值

继续求解

​ 我们需要求解上式的极大值，添加一个符号，我们转换为求解该式的极小值。

即： 12∑i=1,j=1nαiαjyiyjΦT(xi)ΦT(xj)−∑i=1nαi\frac{1}{2}\sum\limits_{i=1,j=1}\limits^{n}\alpha_{i}\alpha_{j}y_i y_j \Phi^T(x_i)\Phi^T(x_j) - \sum\limits_{i=1}\limits^{n}\alpha_{i}21​i=1,j=1∑n​αi​αj​yi​yj​ΦT(xi​)ΦT(xj​)−i=1∑n​αi​; 条件：∑i=1nαiyi=0;αi>=0\sum\limits_{i=1}\limits^n \alpha_i yi = 0; \alpha_i >= 0i=1∑n​αi​yi=0;αi​>=0

实例求解

我们现在以一个实例，求解上述方程。

​ 我们将上面数据代入即可得：

对α1和α2求偏导即可得: α1=1.5\alpha_1 = 1.5α1​=1.5; $ \alpha_2 = -1$

这里，α2小于0，不满足约束条件，所以应该在边界上。此时α1=0或者α2=0.

将α结果代入求解：w=∑i=1nαiyi∣Phi(xn)w=\sum\limits_{i=1}\limits^n \alpha_i y_i |Phi(x_n)w=i=1∑n​αi​yi​∣Phi(xn​); 平面方程为：0.5x1+0.5x2−2=00.5x_1 + 0.5x_2 -2 = 00.5x1​+0.5x2​−2=0

​ 核函数即为了解决低维不可分问题，通过核函数将我们的数据转换到高维的层面，这里就不多介绍了。我们最常用的一个核函数即为高斯核函数。

支持向量机 算法