支持向量机

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

支持向量机（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）等。