雅乐网

支持向量机（support vector machine，简称SVM），在处理一些复杂的非线性问题时相比逻辑回归和神经网络要更加简洁和强大，在工业界和学术界广泛应用。

最大间隔分类器（Large Margin Classification）

优化目标

先来回顾一下逻辑回归中的优化目标，实际上对其进行修改就可以得到SVM的优化目标。

逻辑回归中的假说函数如下

$$h(x) = g(\theta^T x) = \frac{1}{1 + e^{- \theta^T x}}$$

为了方便下面用\(z = \theta^T x\)

当y=1时，我们希望h(x)接近1，就要求z >> 0

当y=0时，我们希望h(x)进阶0，这要求z << 0

再来看一下逻辑回归中的代价函数

$$Cost(h(x), y) = -( y log(h(x)) + (1-y) log(1-h(x)) )$$

$$ = – y log(\frac{1}{1 + e^{- \theta^T x}}) – (1-y) log(1-\frac{1}{1 + e^{- \theta^T x}}) $$

上面逻辑回归中，当y=1时，如果\(\theta^T x >> 0\)，代价虽然很小，但不是0 ；y=1时的代价也不是准确的0。

SVM中修改了一下代价函数，使之由两条直线构成（图中红色）

这两个函数命名为cost1和cost0，下标分别对应y=1和y=0的情况。这样SVM中的代价函数如下：（注意图中横坐标\(z = \theta^T x\)）

$$Cost(h(x), y) = -( y cost_1(\theta^T x) + (1-y) cost_0(\theta^T x) )$$

回顾带正则化的逻辑回归中的代价函数

$$J(\theta) =\frac{1}{m} \left[ \sum_{i = 1}^{m} \left( y^{(i)} -log(h(x^{(i)})) + (1-y^{(i)}) -log\left(1-h(x^{(i)})\right) \right) \right] + \frac{\lambda}{2m} \sum_{j=1}^{n} \theta_j^2$$

用cost函数代替上式可以得到

$$J(\theta) =\frac{1}{m} \left[ \sum_{i = 1}^{m} \left( y^{(i)} cost_1(\theta^T x^{(i)}) + (1-y^{(i)}) cost_0(\theta^T x^{(i)}) \right) \right] + \frac{\lambda}{2m} \sum_{j=1}^{n} \theta_j^2$$

在SVM中，除了修改代价函数为cost函数外，还做了两点等价的修改：

1. 去掉因数\(\frac{1}{m}\)，这样对于求最值是没有影响的

2. 逻辑回归中用\(\lambda\)来调整正则化的程度，SVM中用C，并且放到前面一项。这相当于同时乘以\(\frac{1}{\lambda}\)，并令\(C = \frac{1}{\lambda}\)

这样，SVM中的代价函数如下：

$$J(\theta) = C \left[ \sum_{i = 1}^{m} \left( y^{(i)} cost_1(\theta^T x^{(i)}) + (1-y^{(i)}) cost_0(\theta^T x^{(i)}) \right) \right] + \frac{1}{2} \sum_{j=1}^{n} \theta_j^2$$

另外，SVM中的假设也不同于逻辑回归。逻辑回归中h(x)输出的是y=1的概率，一般大于0.5认为输出1；SVM中，h(x)的输出为1或者0

$$h_\theta(x) =\left\{
\begin{array}{c}
1  \text{　　if} \theta^T x \ge 0\\
0 \text{　　if} \theta^T x < 0
\end{array}
\right.$$

虽然输出时，是用0来比较的；但是训练的时候，确是按照1和-1来比较。因为代价函数中，y=1时，只有z>1代价才为0；y=0时，只有z<-1代价才为0

大间隔分类（Large Margin Classification）

支持向量机有的时候也被称为最大间隔分类器（Large Margin Classifier），因为SVM发现的边界与样本数据集之间有着较大的间隔。

上图中的黑色线边界更好，因为它和数据之间有较大的间隔。

这是由于，SVM的代价函数

$$J(\theta) = C \left[ \sum_{i = 1}^{m} \left( y^{(i)} cost_1(\theta^T x^{(i)}) + (1-y^{(i)}) cost_0(\theta^T x^{(i)}) \right) \right] + \frac{1}{2} \sum_{j=1}^{n} \theta_j^2$$

当y=1时，我们希望z > 1 ，而不是z > 0

当y=0时，我们希望z < -1，而不仅仅是z < 0

这样，SVM的要求更高，这相当于额外添加了一个安全的间距因子。

当参数合适时，可以保证代价函数中前一部分代价为0.那么最小化的问题就转化成了后面的一项的最小值

$$\frac{1}{2} \sum_{j=1}^{n} \theta_j^2$$

然而，此时也有逻辑回归未正则化时遇到的问题：某些异常的值会影响边界的选择

这时需要考虑正则化参数C，注意这里的C相当于逻辑回归中的\(\frac{1}{\lambda}\)

C 较大时，相当于λ较小，可能会导致过拟合（overfit），高方差（High variance）。

C 较小时，相当于λ较大，可能会导致欠拟合（underfit），高偏差（High bias）。

大间隔边界背后的数学原理

上面说到，参数合适的时候，只需要求下面式子的最小值

$$\frac{1}{2} \sum_{j=1}^{n} \theta_j^2$$

所谓的参数合适，是指

当\(y^{(i)} = 1\)时，有 \(\theta^T x^{(i)} \ge 1\)；

当\(y^{(i)} = 0\)时，有 \(\theta^T x^{(i)} \le -1\)；

先来回顾一下向量的知识：

假设我们有向量\(u = \begin{pmatrix}u_1\\u_2 \end{pmatrix}\)和向量\(v = \begin{pmatrix}v_1\\v_2 \end{pmatrix}\)

||u||表示向量u的长度，根据勾股定理，\(||u|| = \sqrt{u_1^2 + u_2^2}\)

再看上面要求的最小值，相当于求 \(||\theta||\)的最小值

再来回顾向量内积：

$$u \cdot v = u^T v = u_1v_1 + u_2v_2$$

从几何的角度，还等于v在u上的投影向量乘以||u||。（高中数学知识）

用向量p表示v在u上的投影向量，则有

$$u^T v = p \cdot ||u||$$

再来看参数合适时的条件

当\(y^{(i)} = 1\)时，有 \(\theta^T x^{(i)} \ge 1\)；

当\(y^{(i)} = 0\)时，有 \(\theta^T x^{(i)} \le -1\)；

把上面的\(\theta^T x^{(i)} \) 看做 \(u^T v\)。把\(x^{(i)}\)在 \(\theta\) 上的投影向量记作\(p^{(i)}\)，则需要

$$\theta^T x^{(i)} = p^{(i)} ||\theta||$$

的绝对值尽可能的大。（大于1或者小于-1）。然而我们要最小化\(||\theta||\)，那么只能让\(p^{(i)}\)尽可能的大。

如果不是大间隔分类的话

这个p向量是很小的。只有是大间隔分类的时候

这时p是较大的，这样\(\theta\)可以小一点。

核函数（Kernels）

高斯核函数（Gaussian Kernel）

之前处理需要用多项式回归的时候

假说模型可能是这样的

$$h(x) = \theta_0 + \theta_1 x_1 + \theta_2 x_2 + \theta_3 x_1^2 + \theta_4 x_1x_2 + \theta_5 x_2^2$$

我们令 \(f_1 = x_1 + f_2 = x_2 + f_3 = x_1^2 + f_4 = x_1x_2 + f_5 = x_2^2\)，上式可以写成下面的形式

$$h(x) = \theta_0 + \theta_1 f_1 + \theta_2 f_2 + \theta_3 f_3 + \theta_4 f_4 + \theta_5 f_5$$

这里的问题是，对于f，有没有更好的选择呢？

这里的核函数就是一个方法。

选定三个地标（landmarks）。（这里是三个点，如何选取见下节）

使用下面的公式重新得到特征

$$f_1 = similarity(x, l^{(1)}) = e^{- \frac{||x – l^{(1)}||^2}{2 \delta^2} }$$

$$f_2 = similarity(x, l^{(2)}) = e^{- \frac{||x – l^{(2)}||^2}{2 \delta^2} }$$

$$f_3 = similarity(x, l^{(3)}) = e^{- \frac{||x – l^{(3)}||^2}{2 \delta^2} }$$

这里的similarity函数就是核函数，具体的这里的这个核函数是高斯核函数。

高斯核函数中，e的指数部分，分子是x到l之间的距离的平方。这就有，当x接近l时，距离约为0，此时f也约为e的0次幂，大概是1；当x远离l时，距离无穷，e的负无穷次幂，大概是0。

\(\delta\)的选择可以影响函数变化的平缓：\(\delta\)是在分母上，它越小，整体变化越大(快)，图形越陡峭。

下面看一个实例，假设是：

$$h(x) = \theta_0 + \theta_1 f_1 + \theta_2 f_2 + \theta_3 f_3$$

其中\(\theta_0 = -0.5, \theta_1 = 1, \theta_2 = 1, \theta_3 = 0\)，也就是

$$h(x) = -0.5 + f_1 + f_2 + 0$$

当上式大于0时，我们预测结果为1；小于0时，预测结果为0。

看下面一个例子，当某个点x靠近l1时

x和l1的距离约为0，f1 = 1

x和l2，l3的距离较远，f2 = f3 = 0

此时有

$$h(x) = -0.5 + f_1 + f_2 + 0 = -0.5 + 1 + 0 + 0 = 0.5$$

结果大于0，预测y=1.

对于接近l2的点，结果也是类似的预测y=1。

再来看对于靠近l3的点，f1 = f2 = 0， f3 = 1

$$h(x) = -0.5 + 0 + 0 + 0 = -0.5$$

结果小于0，预测结果为0.

这样，这个假说的边界大致如下：

细节和实际应用

首先有个问题是，如何选定地标（landmarks）呢？一个简单的办法是，选择训练集中的所有点作为地标。如果训练集中有m个实例，我们就选m个地标，并且\(l^{(1)} = x^{(1)}, l^{(2)} = x^{(2)}, …, l^{(m)} = x^{(m)}\)。

$$f_1 = similarity(x, l^{(1)})$$

$$f_2 = similarity(x, l^{(2)})$$

$$…$$

额外令\(f_0 = 1\)，就可以得到f向量

对于训练集中的一个实例\((x^{(i)}, y^{(i)})\)

$$f_1^{(i)} = similarity(x^{(i)}, l^{(1)})$$

$$f_2^{(i)} = similarity(x^{(i)}, l^{(2)})$$

$$…$$

$$f_i^{(i)} = similarity(x^{(i)}, l^{(i)}) = e^0 = 1$$

$$…$$

$$f_m^{(i)} = similarity(x^{(i)}, l^{(m)})$$

这样，原本的\(x^{(i)}\)中包含n个特征，经过我们的转换后，\(f^{(i)}\)中包含了m个特征。

SVM中的假说：给你x，首先计算f，f包含m+1个特征。

当\(\theta^T f \ge 0\)时，就预测y=1.

那么怎么得到参数\(\theta\)呢？

首先看上面没有用高斯核函数时的代价函数

$$J(\theta) = C \left[ \sum_{i = 1}^{m} \left( y^{(i)} cost_1(\theta^T x^{(i)}) + (1-y^{(i)}) cost_0(\theta^T x^{(i)}) \right) \right] + \frac{1}{2} \sum_{j=1}^{n} \theta_j^2$$

现在，需要把\(\theta^T x^{(i)}\)换成\(\theta^T f^{(i)}\)就可以了。由于x和f的维数不同，这里参数也不同啦。特别的，使用高斯核函数后，特征数和训练集实例数是一样多的。下面的n也可以换成m。

$$J(\theta) = C \left[ \sum_{i = 1}^{m} \left( y^{(i)} cost_1(\theta^T f^{(i)}) + (1-y^{(i)}) cost_0(\theta^T f^{(i)}) \right) \right] + \frac{1}{2} \sum_{j=1}^{n} \theta_j^2$$

只要求出上面式子的最小值，就得到了参数\(\theta\)。

为了简化计算，一般后面一项 \(\theta^T theta\)要处理一下，变成\(\theta^T M \theta\)，这是为了提高计算效率。M矩阵的选择依赖于不同的核函数。一般软件包中都会包含这种数值优化技巧。

核函数也可以应用于逻辑回归，但是这时计算非常缓慢。只有在SVM中的核函数，才有这些优化方法，从而有很快的计算速度。

下面看一下SVM中的参数对结果的影响。

C较大时，相当于λ较小，可能会导致过拟合，高方差

C较小时，相当于λ较大，可能会导致欠拟合，高偏差

σ较大时，f变化更加平缓，这导致你的模型随着x的变化而缓慢变化，导致欠拟合，高偏差

σ较小时，f变化剧烈，导致过拟合，导致高方差

除了高斯核函数，还有其他核函数选择，这些和函数都应遵Mercer’s定理，以便使用计算优化技巧。不使用核函数又称为线性核函数。

使用SVM

如何选择逻辑回归和支持向量机呢？

下面是一些普遍使用的准则：

如果相较于m而言，n要大许多，即训练集数据量不够支持我们训练一个复杂的非线性模型，我们选用逻辑回归模型或者不带核函数的支持向量机。

如果n较小，而且m大小中等，例如n在1-1000之间，而m在10-10000之间，使用带高斯核函数的支持向量机。

如果n较小，而m较大，例如n在1-1000之间，而m大于50000，则使用支持向量机会非常慢，解决方案是创造、增加更多的特征，然后使用逻辑回归或不带核函数的支持向量机。

值得一提的是，神经网络在以上三种情况下都可能会有较好的表现，但是训练神经网络可能非常慢，选择支持向量机的原因主要在于它的代价函数是凸函数，不存在局部最小值。