支持向量机

作者: 小王子特洛伊 | 来源:发表于2019-07-18 19:29 被阅读0次

【转载】pluskid的SVM系列博文
【机器学习实战】第6章支持向量机（Support Vector
SVM支持向量机
编程作业（六）
支持向量机-QA
支持向量机
机器学习——libSVM（一）
支持向量机&&聚类
支持向量机
【9%】100小时机器学习——支持向量机SVM

支持向量机（Support Vector Machine）是一种二元分类器，在学习非常复杂的非线性方程时，能够提供更加清晰和更加强大的方式，通常简称为 SVM。

优化目标

图中为逻辑回归的损失函数，稍加改造即为 SVM 的损失函数（粉色）。其中， $z=\theta^Tx$ ，当判断 y = 1 时，如果 z > 1， cost 1 = 0，如果 z < 0 则 cost 1 是一条负斜率的直线；当判断 y = 0 时，如果 z < -1，cost 0 = 0，如果 z > 0，则 cost 0 是一条正斜率的直线。

逻辑回归代价函数：
$min_\theta\frac{1}{m}\left[\sum_{i=1}^my^{(i)}(-logh_\theta(x^{(i)}))+(1-y^{(i)})(-log(1-h_\theta(x^{(i)}))) \right]+\frac{\lambda}{2m}\sum_{j=1}^n\theta_j^2$

SVM 代价函数：
$min_\theta C\sum_{i=1}^my^{(i)}cost_1(\theta^Tx^{(i)})+(1-y^{(i)})cost_0(\theta^Tx^{(i)}) +\frac{1}{2m}\sum_{j=1}^n\theta_j^2$

在 SVM 代价函数中，我们用 $cost_1(\theta^Tx^{(i)})$ 和 $cost_0(\theta^Tx^{(i)})$ 替换掉逻辑回归中的 $-logh_\theta(x^{(i)})$ 和 $-log(1-h_\theta(x^{(i)}))$ ，并去掉了 $\frac{1}{m}$ 项，这对优化目标不会产生影响。我们还去掉了正则化项中的 $\lambda$ ，并在公式第一部分加入了参数 $C$ ，其作用类似 $\frac{1}{\lambda}$ ，同样能够起到平衡数据拟合程度和参数惩罚力度的作用。

SVM 的假设函数可以直接输出分类结果，比如：
$h_\theta(x) \begin{cases} 1& \theta^Tx\geq0\\ 0 & \theta^Tx<0 \end{cases}$

大间距分类器

上面说到，使得正样本 $\theta^Tx \geq 0$ ，负样本 $\theta^Tx < 0$ ，即可实现分类，但 SVM 的代价函数为了把误差降到最小，需要正样本 $\theta^Tx \geq 1$ ，负样本 $\theta^Tx \leq -1$ ，SVM 比一般分类器要求更加严格，目的是要构建一个安全因子或者叫安全间距。

可以发现，黑色决策边界（Decision Boundary）与样本的最小间距（即与蓝色直线的距离）更大，这个距离就叫做支持向量机的间距（Margin），这使得支持向量机具有鲁棒性，它会尽量用大的间距去分离数据，因此支持向量机也被称为大间距分类器（Large Margin Classifier）。

决策边界会受 SVM 代价函数的系数 $C$ 的影响，如果 $C$ 较大，决策边界会尽力拟合训练数据，比如图中的异常点，从而决策边界会由黑色直线变为紫色直线。如果 $C$ 较小，决策边界就会忽略异常点的影响，甚至在数据不是线性可分的情况下也能得到比较好的结果。可以将 $C$ 比作 $\frac{1}{\lambda}$ ，增大 $C$ 即减小 $\lambda$ ，可以增强模型的拟合能力；减小 $C$ 即增大 $\lambda$ ，可以增强模型的泛化能力。

数学原理

在 SVM 中我们会计算 $\theta^Tx$ ，暂且将 $\theta$ 记作 $u$ ，将 $x$ 记作 $v$ 。已知两个二维向量 $u=\left[ \begin{smallmatrix}u_1\\u_2\end{smallmatrix}\right]$ ， $v=\left[ \begin{smallmatrix}v_1\\v_2\end{smallmatrix}\right]$ 。 $u$ 的长度（欧几里得长度）等于 $u$ 的范数 $||u||$ 。根据毕达哥斯拉定理： $||u||=\sqrt{u_1^2+u_2^2}$ 。为了计算 $u^Tv$ ，需要将 $v$ 投影到向量 $u$ 上，所以需要做一个直角投影， $p$ 即为向量 $v$ 在向量 $u$ 上的投影长度，或者说量。 $u^Tv$ 就等于 $v$ 的投影长度 $p$ 乘以 $u$ 的长度（即 $u$ 的范数 $||u||$ ），即：
$u^T\cdot v =p\cdot ||u||$

$u^Tv$ 也等于 $u$ 和 $v$ 的内积：
$u^T\cdot v =u_1v_1+u_2v_2$

$p\cdot ||u|| =u_1v_1+u_2v_2$

值得注意的是， $p$ 和 $||u||$ 都为实数。当两个向量的夹角小于 90 度的时候， $p$ 为正值，当夹角大于 90 度的时候， $p$ 为负值。当然，也可以将 $u$ 投影到向量 $v$ 上，然后做相同的计算，可以得到相同的结果，即：
$v^T\cdot u=v_1u_1+v_2u_2=u^T\cdot v$

点到边界的距离

通常 SVM 的优化目标为 $min_\theta\frac{1}{2}\sum_{j=1}^n\theta_j^2$ ，为了简化目标，我们先忽略截距项，使 $\theta_0=0$ ，并使特征数 $n=2$ ，所以优化目标可以简化为：
$min_\theta\frac{1}{2}\sum_{j=1}^n\theta_j^2=\frac{1}{2}(\theta_1^2+\theta_2^2)=\frac{1}{2}(\sqrt{\theta_1^2+\theta_2^2})^2=\frac{1}{2}||\theta||^2$

因为对于任何实数 $w$ 来说， $w=(\sqrt{w})^2$ 。而 $\sqrt{\theta_1^2+\theta_2^2}$ 即为 $\theta$ 的范数 $||\theta||$ ，所以 SVM 的优化目标就是最小化 $||\theta||^2$ 。

当我们对某个训练样本 $x^{(i)}$ 进行预测时，需要计算 $\theta^Tx^{(i)}$ ，我们可以将样本 $x^{(i)}$ 映射到参数向量 $\theta$ 上，得到映射长度 $p$ ，而 $\theta^Tx^{(i)}=p \cdot ||\theta||=\theta_1x_1+\theta_2x_2$ ，那么，我们就可以根据 $p \cdot ||\theta||$ 进行预测，即：
$h_\theta(x) \begin{cases} 1& p \cdot ||\theta||\geq1\\ 0 & p \cdot ||\theta||\leq-1 \end{cases}$

上图绿色直线为 SVM 的决策边界，蓝色直线为参数向量 $\theta$ ， $\theta$ 垂直于决策边界，根据条件：
$h_\theta(x) \begin{cases} 1& p \cdot ||\theta||\geq1\\ 0 & p \cdot ||\theta||\leq-1 \end{cases}$

$p^{(1)}$ 和 $p^{(2)}$ 分别为正样本 $x_1$ 和负样本 $x_2$ 在参数向量 $\theta$ 上的投影长度，对于正样本 $x_1$ 来说， $p^{(1)}$ 越大越好，对于负样本 $x_2$ 来说， $p^{(2)}$ 越小越好。但是我们发现， $p^{(1)}$ 和 $p^{(2)}$ 都很短，说明 $p^{(1)}$ 很小， $p^{(2)}$ 很大，因为 $p^{(2)}$ 为负数。那么为了预测正确，我们就需要 $||\theta||$ 越大越好，但是我们的优化目标为 $min_\theta\frac{1}{2}\sum_{j=1}^n\theta_j^2=\frac{1}{2}||\theta||^2$ ，这意味着 SVM 会将 $||\theta||$ 最小化，可见想要将 $||\theta||$ 变大并不容易。

上图 SVM 的决策边界和参数向量 $\theta$ 发生了变化， $\theta$ 仍垂直于决策边界。可以发现，正样本 $x_1$ 和负样本 $x_2$ 在参数向量 $\theta$ 上的投影长度 $p^{(1)}$ 和 $p^{(2)}$ 都变长了，根据条件：
$h_\theta(x) \begin{cases} 1& p \cdot ||\theta||\geq1\\ 0 & p \cdot ||\theta||\leq-1 \end{cases}$

$p^{(i)}$ 增大了，即使减小 $||\theta||$ ， $p \cdot ||\theta||$ 仍可保持不变。也就是说，即使优化目标 $min_\theta\frac{1}{2}\sum_{j=1}^n\theta_j^2=\frac{1}{2}||\theta||^2$ ，将 $||\theta||$ 变小一些，SVM 仍然可以预测正确。所以相对第一条决策曲线，SVM 最终会选择第二条，这也是 SVM 为什么会产生大间距分类的原因，而且 SVM 的间距正是 $p^{(i)}$ 中最小的那一个，优化目标最小化 $||\theta||$ ，就是为了最大化间距 $p^{(i)}$ 。

上面推导过程始终让 $\theta_0=0$ ，这么做的目的是让决策边界通过原点，实际结果表明，无论 $\theta_0$ 是否等于 0，对大间距分类器的效果都不会产生太大影响。

核函数

为了拟合这种复杂的非线性决策边界，通常需要构建复杂的多项式特征集合，比如：
$f(x)=\theta_0+\theta_1x_1+\theta_2x_2+\theta_3x_1x_2+\theta_4x_1^2++\theta_5x_2^2+\cdots$

$h_\theta(x)=\begin{cases}1& f(x) \geq 0\\0& f(x) < 0\end{cases}$

现在我们用 $f_i$ 代表特征变量：
$f(x)=\theta_0+\theta_1f_1+\theta_2f_2+\theta_3f_3+\theta_4f_4+\theta_5f_5+\cdots$

现在的问题是，我们如何来构建更好的特征 $f_i$ 呢？

图中我们是手动选取的三个点 $l^{(1)}, l^{(2)},l^{(3)}$ ，称为标记。对于一个新样本 $x$ ，我们可以将 $x$ 和三个标记的相似度作为样本 $x$ 的特征，即：
$f_1=similarity(x,l^{(1)})=exp(-\frac{||x-l^{(1)}||^2}{2\sigma^2})\\ f_2=similarity(x,l^{(2)})=exp(-\frac{||x-l^{(2)}||^2}{2\sigma^2})\\ f_3=similarity(x,l^{(3)})=exp(-\frac{||x-l^{(3)}||^2}{2\sigma^2})$

其中

$exp(-\frac{||x-l^{(1)}||^2}{2\sigma^2})=exp(-\frac{\sum_{j=1}^n(x_j-l_j^{(1)})^2}{2\sigma^2})$

$||x-l^{(1)}||^2$ 表示样本 $x$ 与标记 $l^{(1)}$ 的欧式距离的平方（ $||w||$ 表示向量 $w$ 的长度）。而相似度函数 $similarity()$ 就是核函数，这里所用的核函数 $exp()$ 为高斯核函数，事实上还有很多其他的核函数，通常核函数用 $k()$ 表示。相似度公式的分子 $||x-l^{(1)}||^2$ 也可以写做向量 $x$ 和标记 $l$ 之间元素 $j\in(1,n)$ 对应的距离之和。

假如样本 $x$ 和标记 $l^{(1)}$ 距离特别近，意味着 $||x-l^{(1)}||^2\approx0$ ，那么 $f_1\approx exp(-\frac{0^2}{2\sigma^2})\approx1$ ；假如样本 $x$ 和标记 $l^{(1)}$ 距离特别远，意味着 $||x-l^{(1)}||^2$ 为一个很大的数，记作 $bignum$ ，那么 $f_1\approx exp(-\frac{(bignum)^2}{2\sigma^2})\approx0$ 。因此，这些特征做的就是衡量样本与每个标记的相似度，如果样本接近标记，那么特征变量接近 1；如果样本远离标记，那么特征变量接近 0。每个标记都着影响着一个特征变量的取值。

上图是 $f_1$ 值随 $x$ 点坐标变化的曲面图和等高线图。假设标记 $f_1=exp(-\frac{||x-l^{(1)}||^2}{2\sigma^2})$ ， $l^{(1)}=\left[ \begin{smallmatrix} 3 \\ 5 \end{smallmatrix} \right ]$ ， $\sigma^2=1$ ，当样本 $x$ 接近标记 $l^{(1)}$ 时， $f_1\approx1$ ，当样本 $x$ 远离标记 $l^{(1)}$ 时， $f_1\approx0$ 。所以从图中可以直观的感受到， $f_1$ 表示着样本与标记距离的远近程度。

我们也可以通过改变分母的值，观察核函数的变化。如果减小分母的值，比如 $\sigma^2=0.5$ ，可以发现，突起的宽度变窄了，等高线也收缩了，随着 $x$ 从顶点向周围移动（即 $x$ 与 $l^{(1)}$ 的距离变大）， $f_1$ 从 1 下降到 0 的速度更快了。相反，如果增大分母的值，比如等于 $\sigma^2=0.5$ ，可以发现，突起的宽度变宽了，等高线也扩张了，随着 $x$ 从顶点向周围移动（即 $x$ 与 $l^{(1)}$ 的距离变大）， $f_1$ 从 1 下降到 0 的速度更慢了。

若我们的假设函数 $h_\theta(x)=\theta_0+\theta_1f_1+\theta_2f_2+\theta_3f_3$ ，参数值 $\theta_0=-0.5,\theta_1=1,\theta_2=1,\theta_3=0$ ，对于一个新样本（粉红色），我们需要计算 $h_\theta(x)$ 值进行预测。由于该正样本接近 $l^{(1)}$ ，远离 $l^{(2)}$ 和 $l^{(3)}$ ，所以 $f_1\approx1,f_2\approx0,f_3\approx0$ 。那么，根据公式可以计算得出 $h_\theta(x)=-0.5+1=0.5\geq0$ ，所以我们的预测结果 y = 1。

再取一个样本（绿色）做相似计算，由于该样本接近 $l^{(2)}$ ，所以 $f_2\approx1,f_1\approx0,f_3\approx0$ ，根据公式可以计算得出 $h_\theta(x)=-0.5+1=0.5\geq0$ ，预测结果也是 y = 1。

再取一个样本（蓝色）做相似计算，由于该样本距离 $l^{(1)}, l^{(2)}, l^{(3)}$ 都很远，所以 $f_1, f_2, f_3$ 都接近 0。那么，根据公式可以计算得出 $h_\theta(x)=-0.5<0$ ，所以我们的预测结果 y = 0。

当训练集所有样本都完成计算，我们会得到一个决策边界（橘红色），在边界区域内，样本的预测结果为 1，在边界区域外，样本的预测结果为 0，这就是通过定义标记点和核函数来得到新的特征变量，从而训练出非常复杂的非线性决策边界的方法。

那么，我们该如何选择标记点和核函数呢？

标记点选取

通常我们是直接将训练样本点作为标记点。 $m$ 个样本的训练集就可以获得 $m$ 个标记 $l^{(i)},_{i\in(1,m)}$ 。这样一来，特征向量基本上是在描述样本距离每一个训练集样本的距离。

对于一个样本 $x^{(i)}$ ，需要计算 $x^{(i)}$ 和每一个标记（样本）的距离：
$f_1^{(i)}=similarity(x^{(i)},l^{(1)})\\ f_2^{(i)}=similarity(x^{(i)},l^{(2)})\\ \vdots\\ f_m^{(i)}=similarity(x^{(i)},l^{(m)})$

并将 $m$ 个特征加截距项合并为一个 $m+1$ 维的特征向量 $f$ ：
$f=\left[ \begin{matrix} f_0\\ f_1 \\ f_2 \\ \vdots \\f_m \end{matrix} \right ]$

其中， $f_0=1$ 为截距项，由于特征向量 $f$ 是 $m+1$ 维的，所以参数 $\theta$ 也是 $m+1$ 维的，这时，我们就可以根据假设函数进行预测了：
$h_\theta(x)=\theta_0f_0+\theta_1f_1+\theta_2f_2+\cdots+\theta_mf_m$

以上是我们假设已知参数 $\theta$ 来选择特征的过程，那么，我们如何选择参数 $\theta$ 呢？我们可以先随机选取 $\theta$ ，然后通过最小化代价函数来拟合参数 $\theta$ 。

带有原始特征的代价函数：
$min_\theta C\sum_{i=1}^my^{(i)}cost_1(\theta^Tx^{(i)})+(1-y^{(i)})cost_0(\theta^Tx^{(i)})$

将新特征带入代价函数并加入正则项：
$min_\theta C\sum_{i=1}^my^{(i)}cost_1(\theta^Tf^{(i)})+(1-y^{(i)})cost_0(\theta^Tf^{(i)})+\frac{1}{2}\sum_{j=1}^n\theta_j^2$

我们不对截距项 $\theta_0$ 进行正则化，所以 $n=m$ ，忽略 $\theta_0$ 之后， $\sum_j^m\theta_j^2=\theta^T\theta=||\theta||^2$ ，其中 $\theta^T\theta$ 可以由 $\theta^TM\theta$ 代替， $M$ 为一个相对较小矩阵，具体大小取决于所采用的核函数，这是 $\theta^T\theta$ 的一种优化计算方式，可以提升了 SVM 的计算效率，从而使得 SVM 可以应用于更大的数据集。因为在大规模数据的情况下， $\theta^T\theta$ 的计算量将十分庞大。

事实上，核函数定义特征向量，标记点等技术也可以应用于其他机器学习算法，比如逻辑回归等。但应用于 SVM 的计算技巧不能很好地推广到其他算法，所以将核函数应用到逻辑回归上，计算将十分缓慢。相比之下，SVM 能很好的与核函数以及这些计算技巧结合。

参数优化：

关于如何选择 SVM 优化目标中的参数 $C$ 和 $\sigma^2$ ，可以采用偏差方差折中。

我们知道 $C$ 的作用相当于 $\frac{1}{\lambda}$ ，所以较大的 $C$ （即较小的 $\lambda$ ）代表低偏差，高方差，容易过拟合；较小的 $C$ （即较大的 $\lambda$ ）代表高偏差，低方差，容易欠拟合。

较大的 $\sigma^2$ ，代表平滑的函数曲线，模型变化幅度小，高偏差，低方差；

较小的 $\sigma^2$ ，代表陡峭的函数曲线，模型变化幅度大，低偏差，高方差。

核函数选取

有以下核函数可供选择：

线性核函数（Linear Kernel）
线性核函数就是不使用核函数，适用于有大量样本特征，少量样本的情况，这时我们需要拟合一个线性的决策边界，因为样本数量不足很容易过拟合。
高斯核函数（Gaussian kernel）
需要选择合适的 $sigma^2$ 参数，适用于少量特征，大量样本的情况，可以拟合出非常复杂的非线性决策边界。
注意：使用高斯核函数需要做特征变换（归一化或标准化）来确保 SVM 在计算样本与标记的距离时，不同的特征变量的差异标准是一致的。
多项式核函数（Polynomial Kernel）
$k(x,l)=(x^Tl+c)^d$ ，其中 $c,d$ 为自定义参数，比如 $k(x,l)=(x^Tl)^2$ 或 $k(x,l)=(x^Tl+1)^3$
可以发现， $x$ 和 $l$ 的内积值可能会很大，适用于 $x$ 和 $l$ 都是严格的非负数时，可用保证 $x$ 和 $l$ 的内积值永远为正数。
其他核函数：字符串核函数（String Kernel）、直方相交核函数（Histogram Intersection Kernel）、卡方核函数（Chi-Square Kernel）等。

注意：通常我们只用线性核函数或高斯核函数，而且不是所有的相似函数都是有效的核函数，核函数需要满足一个技术条件是：必须符合莫塞尔定理。因为 SVM 为了有效的求解参数 $\theta$ ，使用了很多数值优化技巧，默塞尔定理确保了 SVM 的优化方法有效。

多分类

很多 SVM 软件包已经实现并内置了多分类函数。也可以和逻辑回归多分类一样，假设有 $k$ 个分类，对每个分类分别进行预测，选择预测值 $(\theta^{(i)})^Tx,_{i\in(1,k)}$ 最大的作为正确分类。

如何选择逻辑回归还是支持向量机

当特征数 $n$ 远大于样本数 $m$ 时，比如 $n=1000,m=10$ ，通常建议使用逻辑回归或线性 SVM，因为没有足够的数据来拟合复杂的非线性函数。

当特征数很小，而样本数适中时，比如 $n\in(1,1000),m\in(10,10000)$ ，使用线性 SVM 比逻辑回归更好。

当样本数远大于特征数时，比如 $n\in(1,1000),m\in(50000,5000000)$ ，通常建议使用逻辑回归或者线性 SVM，因为当数据量超过百万时，高斯核函数的计算会非常慢。

可以发现，逻辑回归和线性核函数非常相似，对于神经网络来说，以上所有情况都适用，前提是结构设计良好的话，但可能训练起来会比 SVM 更慢，而且需要解决局部最优问题，而 SVM 的优化问题属于凸优化，不用担心局部最优问题。

参考

https://study.163.com/course/introduction/1004570029.htm

【转载】pluskid的SVM系列博文
基本篇：支持向量机: Maximum Margin Classifier —— 支持向量机简介。支持向量机: Su...
【机器学习实战】第6章支持向量机（Support Vector
第6章支持向量机支持向量机概述支持向量机(Support Vector Machines, SVM)：是一...
SVM支持向量机
线性支持向量机# 径向支持向量机# 最优参数##
编程作业（六）
支持向量机支持向量机本部分练习，我们将在2D示例数据集上使用支持向量机。通过在这些数据集上使用支持向量机，将帮...
支持向量机-QA
Q1：SVM的类型有哪些？三类：线性可分支持向量机、线性支持向量机、非线性支持向量机线性可分支持向量机：当训练数...
支持向量机
支持向量机线性可分支持向量机与硬间隔最大化线性支持向量机与软间隔最大化非线性支持向量机与核函数序列最小最优...
机器学习——libSVM（一）
一、什么是支持向量机支持向量机（Support Vector Machine,SVM）也称为支持向量网络。是一类...
支持向量机&&聚类
支持向量机SVM（Support Vector Machine）一、支持向量机的原理 Support Vecto...
支持向量机
问题 1. 支持向量机是如何进行数据分类？ 2. 支持向量机求解过程 3. 支持向量机是怎么对线性不...
【9%】100小时机器学习——支持向量机SVM
支持向量机