支持向量机-算法概述

作者: shenny_ | 来源:发表于2020-02-20 00:17 被阅读0次

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

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

距离的定义：基于最大间隔分隔数据

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

image

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

w'和w''在超平面上：w^Tx' = -b; W^Tx'' = -b
法向量与w'和w''的向量垂直： $[w^T (x^{''} - x^{'})] = 0$

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

image

优化目标：找到一条线（w和b）,是的离该线最近的点能够最远

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

$y(x)=w^{T}\phi(x)+b \Rightarrow \begin{aligned}y(x_{i})>0 &\Leftrightarrow y_{i}=+1\\ y(x_{i})<0&\Leftrightarrow y_{i}=-1\end{aligned} \Rightarrow y(i) \cdot y(x_{i})>0$ 这里的φ（x）我们可以先暂时理解为x

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

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

目标函数: $argmax_{w,b}\left\{ \frac{1}{||w||} min[y_{i} \cdot (w^{T} \cdot \phi(x_{i} + b))] \right \}$

求解目标函数

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

放缩变换

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

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

当前目标： $max_{w,b} \frac{1}{||w||}$ ，约束条件： $y_{i} \cdot (w^{T} \cdot \phi(x_{i}) + b) >= 1$

函数变换

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

转换函数 $\Rightarrow min_{w,b} \frac{1}{2}w^{2}$

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

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

求解拉格朗日乘子法

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

$min L(x, \lambda,w)=f_{0}(x) + \Sigma{\lambda_{i}f_{i}(x)} + \Sigma{v_{i}h_{i}(x)}$

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

$L(w,b,\alpha)= \frac{1}{2}||w||^{2} - \Sigma{\alpha_{i}(y_{i}(w^{T} \cdot \phi(x_i) +b)-1)}$ 约束条件: ${y_i(w^T \cdot \Phi(x_i) + b)>=1}$

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

对w求偏导: $\frac{\partial L}{\partial w}=0 \Rightarrow w=\sum\limits_{1-n} {\alpha_{i}y_{i}\Phi(x_n)}$

对b求偏导: $\frac{\partial L}{\partial b}=0 \Rightarrow 0=\sum\limits_{1-n}{\alpha_{i}y_{i}}$

我们带入原式即得：

$L(w,b,\alpha)= \frac{1}{2}||w||^{2} - \Sigma{\alpha_{i}(y_{i}(w^{T} \cdot \phi(x_i) +b)-1)}$

其中： $w=\sum\limits_{1-n} {\alpha_{i}y_{i}\Phi(x_n)}$ ; $0=\sum\limits_{1-n}{\alpha_{i}y_{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}$

$=\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})$ 完成了第一步求解minL(w,b,α)

$=\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)$ 求解该式的极值

继续求解

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

即： $\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}$ ; 条件： $\sum\limits_{i=1}\limits^n \alpha_i yi = 0; \alpha_i >= 0$