svm.md

支持向量机

• 支持向量机
  • 优化目标
  • 大边界
  • 大边界分类背后的数学
  • 核函数
  • 使用SVM
  • 什么时候使用SVM

支持向量机（Support Vector Machine）是一个广泛应用于工业界和学术界的算法。 与逻辑回归和神经网络相比，SVM在学习复杂非线性方程时提供了一种更为清晰，更加强大的方式。

优化目标

为了描述SVM，我们先从逻辑回归开始展示如何一点一点修改来得到SVM：

在逻辑回归中我们已经熟悉了这里的假设函数形式，和右边的S型激励函数。 然而，为了解释一些数学知识。将用 z 表示 θ^Tx 。

看看逻辑回归做什么：

1. 对一个 y=1 的样本，希望 hθ(x) 趋近1。
   • 因为想要正确地将此样本分类，这就意味着当 hθ(x) 趋近于1时， θ^Tx >> 0 。
   • 因为由于 z 表示 θ^Tx ，当 z >> 0 ，即到了上图右图，逻辑回归的输出将趋近于1。
2. 对一个 y=0 的样本。希望 hθ(x) 趋近0。
   • 这对应于 θ^Tx << 0 ，或者就是 z << 0，因为对应的假设函数的输出值趋近0。

对于逻辑回归的代价函数，考虑两种情况：

1. 是 y 等于1的情况
   • y = - log((1/(1 + e^-z)))​
2. 是 y 等于0的情况
   • y = - (1-y) log(1- (1/(1 + e^-z)))​

现在开始建立SVM，我们从这里开始：

对代价函数 -log(1-((1)/(1+e^-z))) 做一点修改（如上图中紫色的曲线）。 由两条线段组成，即位于右边的水平部分和位于左边的直线部分。

• 左边的函数称为 cost₁(z)
• 右边的函数称为 cost₀(z) 。

因此，对于SVM，我们得到了这里的最小化问题，即:

和逻辑回归相比，有几点不同：

1. SVM代价函数公式里多了 C，少了 λ/m。如果把 C 当做是 1/λ，实际是优化目标等效的。因为对于一个最小化问题，在目标公式上乘除一个常量或加减一个常量都不影响求最优解。
2. 当获得参数 θ 时，直接用 θ^Tx 预测 y 的值。

大边界

从直观的角度看看优化目标，实际上是在做什么，以及SVM的假设函数将会学习什么，同时也会谈谈如何做些许修改，学习更加复杂、非线性的函数。

这是SVM模型的代价函数，横轴表示 z ：

• 左边显示关于 z 的代价函数 cost₁(z) ，用于正样本
• 右边显示关于 z 的代价函数 cost₀(z) ，用于负样本

现在考虑一下，最小化这些代价函数的必要条件是什么。

• 对一个正样本 y=1 ，只有 z >= 1 时，代价函数 cost₁(z) = 0，等同希望 θ^Tx >= 1 ；
• 对一个负样本 y=0 ，只有 z <= 1 时，代价函数 cost₀(z) = 0，等同希望 θ^Tx <= 1

这是SVM的一个性质：

• 如果 y = 1 ，（根据h的定义）仅要求 θ^Tx >= 0，就能将样本分出，这是因为如果 θ^Tx > 0 ，模型代价函数值为0。
• 如果 y = 0，仅需要 θ^Tx <= 0 就会将负例正确分离，

但是，SVM的要求更高，不仅要能正确分开样本。即

• 对于正例，不仅要求 θ^Tx > 0，需要的是比0值大很多，比如大于等于1；
• 对于负样本，不仅要求 θ^Tx < 0，还希望比0小很多，希望它小于等于-1

这就相当于在SVM中嵌入了一个额外的安全因子，或者说安全的间距因子。

让我们看一下，在SVM中，这个因子会导致什么结果。 具体而言，接下来考虑一个特例。将这个常数 C 设置成一个非常大的值。比如我们假设 C = 100000，然后观察SVM会给出什么结果？

如果 C 非常大，则最小化代价函数的时候，我们将会很希望找到一个使第一项为0的最优解。因此，让我们尝试在代价项的第一项为0的情形下理解该优化问题。比如我们可以把 C 设置成了非常大的常数，这将给我们一些关于SVM模型的直观感受。

这将遵从以下的约束：

• θ^Tx⁽ⁱ⁾ >= 1 ，如果 y⁽ⁱ⁾ 是等于1的
• θ^Tx⁽ⁱ⁾ <= -1 ，如果样本 i 是一个负样本

这样当你求解这个优化问题的时候，当你最小化这个关于变量 θ 的函数的时候，你会得到一个非常有趣的决策边界。

---

具体而言，如果你考察这样一个数据集，其中有正样本，也有负样本，可以看到这个数据集是线性可分的。我的意思是，存在一条直线把正负样本分开。当然有多条不同的直线，可以把正样本和负样本完全分开。

上图的例子，画了很多条决策边界，都可以将正样本和负样本分开。但绿色和红色的仅仅是勉强分开，看起来都不是特别好的选择。

而SVM将会选择这个黑色的决策边界，相较于之前我用粉色或者绿色画的决策界。 这条黑色的看起来好得多，黑线看起来是更稳健的决策界。在分离正样本和负样本上它显得的更好。

数学上来讲，这条黑线有更大的距离，这个距离叫做间距（margin）。

当画出这两条额外的蓝线，看到黑色的决策界和训练样本之间有更大的最短距离。 这个距离叫做SVM的间距，而这是SVM具有鲁棒性的原因，因为它努力用一个最大间距来分离样本。因此SVM有时被称为大间距分类器，而这其实是求解上面优化问题的结果。

---

上面的例子中将大间距分类器中的正则化因子常数 C 设置的非常大（100000），因此对这样的一个数据集，也许我们将选择这样的决策界，从而最大间距地分离开正样本和负样本。那么在让代价函数最小化的过程中，我们希望找出在 y=1 和 y=0 两种情况下都使得代价函数中左边的这一项尽量为零的参数。如果我们找到了这样的参数，则我们的最小化问题便转变成：

事实上，SVM现在要比这个大间距分类器所体现得更成熟，尤其是当你使用大间距分类器的时候，你的学习算法会受异常点(outlier)的影响。比如我们加入一个额外的正样本。如下图：

为了将样本用最大间距分开，也许最终会得到一条上图粉色的决策界 它仅仅基于一个异常值，就将决策界从黑线变到粉线，显然不合理。 但如果 C 设置的小一点，则最终仍会得到这条黑线。

C 的作用类似于 1/λ ， λ 是我们之前使用过的正则化参数。这只是 C 非常大的情形，或者等价地 λ 非常小的情形。 当 C 不是非常非常大的时候，它可以忽略掉一些异常点的影响，得到更好的决策界。甚至当数据不是线性可分的时候，SVM也可以给出好的结果。

回顾 C = ¹/_λ ，因此：

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

大边界分类背后的数学

先复习一下向量内积：假设有两个向量， u 和 v ，两个都是二维向量， u^Tv 的结果 u^Tv 也叫做向量 u 和 v 之间的内积。

向量 u

• 在横轴上，取值为 u₁ ；在纵轴上，取值为 u₂。
• ‖u‖ 表示 u 的范数，即 u 的长度，也是向量 u 的欧几里得长度。
• ‖u‖=sqrt(u₁²+u₂²) ，这是向量 u 的长度，是一个实数。

向量 v

• v 是另一个向量，它的两个分量 v1 和 v2 是已知的

u 和 v 之间的内积

• 计算内积方法1：

  • 将向量 v 投影到向量 u 上，我们做一个直角投影，或者说一个90度投影将其投影到 u 上，接下来我度量这条红线的长度。 称这条红线的长度为 p ，因此 p 就是长度，或者说是向量 v 投影到向量 u 上的量，我将它写下来， p 是 v 投影到向量 u 上的长度，因此可以将 u^Tv=p·‖u‖ ，或者说 u 的长度。

• 计算内积的方法2：

  • u^Tv 是 [u1 u2] 这个一行两列的矩阵乘以 v 。因此可以得到 u1×v1 + u2×v2 。
  • 其中 u^Tv = v^Tu
  • 等式中 u 的范数是一个实数， p 也是一个实数，因此 u^Tv 就是两个实数正常相乘。
    • 如果 u 和 v 间的夹角小于90度，那么 p 是正值。
    • 如果这个夹角大于90度，则 p 是负值。

根据线性代数的知识，方法2和方法1会给出同样的结果：

• u^Tv = v^Tu = p·‖u‖

--- 根据此前讨论，下图列出SVM的目标函数：

先忽略掉截距，令 _θ₀=0_ ，这样更容易画示意图。 将特征数 _n_ 置为2，仅有两个特征 _x₁,x₂_

看一下SVM的优化目标函数。当仅有两个特征，即 n=2 时，需要最小化 (¹/₂)(θ₁²+θ₂²) 。

现在我将要看看 θ^T、x ，更深入地理解它们的含义。给定参数向量 θ 给定一个样本 x ，这等于什么呢?

θ 和 x⁽ⁱ⁾ 就类似于 u 和 v 的向量，如下面的示意图：

上面的示意图里，用一红叉表示正样本 x⁽ⁱ⁾​（水平轴上取值为 x₁⁽ⁱ⁾​ ，在竖直轴上取值为 x₂⁽ⁱ⁾​）。

将 θ₁​ 画在横轴这里，将 θ₂​ 画在纵轴这里，那么内积 θ^Tx⁽ⁱ⁾

使用之前的方法，计算的方式是我将训练样本投影到参数向量 θ ，然后看这个线段的长度，图中红色。 将它称为 p⁽ⁱ⁾ 用来表示这是第 i 个训练样本在参数向量 θ 上的投影。根据之前的内容，知道

• θ^Tx⁽ⁱ⁾ = p × ‖θ‖，也等于
• θ₁ · x₁⁽ⁱ⁾+θ₂ · x₂⁽ⁱ⁾ 。

这两种方式是等价的，都可以用来计算 θ 和 x⁽ⁱ⁾ 之间的内积。

表达的意思是：这个 θ^Tx⁽ⁱ⁾ >= 1 或者 θ^Tx⁽ⁱ⁾ < -1 的约束是可以被 p⁽ⁱ⁾ · ‖θ‖ >= 1 代替。

---

现在考虑上图中的训练样本。继续使用之前的简化，即 θ₀=0 ，来看下SVM会选择什么样的决策界。

上图左图中绿色直线可以是一种边界的选择。假设SVM选择了这个决策边界。当然这是不好的选择，因为它的间距很小。这个决策界离训练样本的距离很近。我们来看一下为什么SVM不会选择它。

对于这样选择的参数 θ ，可以看到参数向量 θ 事实上是和决策界是90度正交的，因此这个绿色的决策界对应着一个参数向量 θ 。其中 θ₀=0 的简化仅仅意味着决策界必须通过原点 (0,0) 。

比如这个样本，假设它是第一个样本 x⁽¹⁾ ，如果考察这个样本到参数 θ 的投影，投影是图中很短的红线段，所以 p⁽¹⁾ 非常小。 类似地，这个样本如果它恰好是 x⁽²⁾ ，我的第二个训练样本，则它到 θ 的投影是图中粉色段，同样线段很短。即第二个样本到我的参数向量 θ 的投影。 注意的是，p⁽²⁾ 事实上是一个负值， p⁽²⁾ 在相反的方向，这个向量和参数向量 θ 的夹角大于90度，所以 p⁽²⁾ 的值小于0。

发现这些 p⁽ⁱ⁾ 将会是非常小的数，因此当考察优化目标函数时，对正样本而言，需要 p⁽ⁱ⁾ · ‖θ‖ >= 1 ，但如果 p⁽ⁱ⁾ 都非常小，意味着需要 θ 的范数非常大。 因为如果 p⁽¹⁾ 很小，而希望 p⁽¹⁾ · ‖θ‖ >= 1，令其实现的唯一的办法就是希望 θ 的范数大。 类似地，对于负样本而言我们需要 p⁽²⁾ · ‖θ‖ <= -1 。我们已经在这个样本中看到 p⁽²⁾ 会是一个非常小的数，因此唯一的办法就是 θ 的范数变大。

但是我们的目标函数是希望找到一个参数 θ ，它的范数是小的。这是矛盾的，因此，这个决策边界对应的参数向量 θ 不是个好的选择。

---

相反的，看一个不同的决策边界。 比如说，SVM选择了上图右图的决策边界，那条绿色的垂直线，情况会很不同。 绿色的决策界有一个垂直于它的向量 θ 。 如果考察你的数据在横轴 x 上的投影，比如之前提到的样本，x⁽¹⁾ ，当将它投影到横轴 x 上，或说投影到 θ 上，就会得到这样 p⁽¹⁾ （右图红色线段）。 另一个样本，x⁽²⁾ 做同样的投影，得到 p⁽²⁾ 的长度是负值（右图粉色线段）。 注意到 p⁽¹⁾ 和 p⁽²⁾ 投影长度长多了。 如果仍然要满足这些约束， P⁽ⁱ⁾ · ‖θ‖ > 1，则因为 p⁽¹⁾ 变大了， ‖θ‖ 就可以变小了。

因此意味着通过选择右图中的决策界，而非左图那个，SVM可以使参数 θ 的范数变小很多。也就是让代价函数变小。 因此，如果我们想令 θ 的范数变小，就能让SVM选择右边的决策界。

以上，就是SVM如何能有效地产生大间距分类的原因。

推广到有用非常多个样本的训练集，同样目标是希望正样本和负样本投影到 θ 上的 p 值大。做到这点的唯一方式是选择类似右图绿线做决策界。这是大间距决策界来区分开正样本和负样本这个间距的值。间距值是 p⁽¹⁾,p⁽²⁾,p⁽³⁾ 等等。 通过让间距变大，即通过 p⁽¹⁾,p⁽²⁾,p⁽³⁾ 等等的值，SVM最终可以找到一个较小的 θ 范数。 这正是SVM中最小化目标函数的目的。

以上就是为什么SVM最终会找到大间距分类器的原因。因为它试图极大化这些 p⁽ⁱ⁾ 的绝对值，它们是训练样本到决策边界的距离。

---

注意，之前的论述自始至终有一个简化假设，就是参数 θ₀ = 0 。

就像之前提到的， θ₀=0 的意思是我们让决策界通过原点。 如果你令 θ₀ != 0，含义是希望决策界不通过原点。 这里不做全部的推导。实际上，SVM产生大间距分类器的结论证明同样成立，证明方式是非常类似的，是上述证明的推广。

即便 θ₀ 不等于0，SVM要做的是优化目标函数对应着 C 值非常大的情况，但是可以说明的是，即便 θ₀ != 0，SVM仍然会找到正样本和负样本之间的大间距分隔。

核函数

之前讨论过可以使用高级数的多项式模型来解决无法用直线进行分隔的分类问题，如下图的分类问题：

为了获得上图所示的判定边界，我们的模型可能是 θ₀+θ₁x1+θ₂x2+θ₃x1x2+θ₄x1²+θ₅x2²+ ... 的形式。

我们可以用一系列的新的特征 f 来替换模型中的每一项。例如令： f₁ = x₁, f₂ = x₂, f₃ = x₁x₂, f₄ = x₁², f₅ = x₂²

...得到 h_θ(x) = θ₁f₁ + θ₂f₂ + ... + θ_nf_n 。然而，除了对原有的特征进行组合以外，有没有更好的方法来构造 f₁, f₂, f₃ ？

我们可以利用核函数来计算出新的特征。

---

给定一个训练样本 x ，我们利用 x 的各个特征与我们预先选定的地标(landmarks) l⁽¹⁾, l⁽²⁾, l⁽³⁾ 的近似程度来选取新的特征 f₁, f₂, f₃ 。

例如：

其中：

是实例 x 中所有特征与地标 l⁽¹⁾ 之间的距离的和。上例中的 similarity(x, l⁽¹⁾) 就是核函数，具体来讲，是高斯核函数（Gaussian Kernel），但是还有其他类型的核函数存在。（但是和高斯分布没什么关系，只是看起来像）

地标的不同决定了 x 和 l 之间的距离：

• 如果距离趋近0，那么 f ≈ e^-0 = 1
• 如果距离非常大，那么 f ≈ e^-∞ = 0

假设我们的训练样本含有两个特征 [x₁ x₂]，给定地标 l⁽¹⁾ 与不同的 σ，见下图：

图中水平左边为 x₁,x₂，z轴代表 f。可以总结出：

• 当 x 与 l⁽¹⁾ 重合时 f 才有最大值。
• 随着x的变化，f值改变的速率受到 σ² 的控制

举个例子，在上图中，有三个样本点：

1. 红色点的位置，因其离 l⁽¹⁾ 更近，但是离 l⁽²⁾ 和 l⁽³⁾ 较远，因此 f₁ 接近1，而 f₂ , f₃ 接近0。因此 h_θ(x) = θ₀ + θ₁f₁ + θ₂f₂ + θ₁f₃ > 0 ，因此预测 y=1 。
2. 同理可以求出，对于离 l⁽²⁾ 较近的绿色点，也预测 y=1
3. 但是对于蓝绿色的点，因为其离三个地标都较远，预测 y=0 。

图中红色的封闭曲线所表示的范围，便是依据一个单一的训练样本和选取的地标所得出的判定边界。预测时，采用的特征不是训练样本本身的特征，而是通过核函数计算出的新特征 f₁, f₂, f₃ 。

---

如何选择地标？

通常是根据训练集的数量选择地标的数量，即如果训练集中有 m 个样本，则选取 m 个地标，并且令: l⁽¹⁾ = x⁽¹⁾, l⁽²⁾ = x⁽²⁾, ....., l^(m) = x^(m) 。

这样做的好处在于：现在我们得到的新特征是建立在原有特征与训练集中所有其他特征之间距离的基础之上的，即：

下面将核函数运用到SVM中，修改SVM假设为：

• 给定 x ，计算新特征 f ，当 θ^T f >= 0 时，预测 y = 1 ，否则反之。
• 相应地修改代价函数为： Σ_j=1^n=mθ_j²=θ^Tθ

理论上讲，也可以在逻辑回归中使用核函数，但是上面使用 M 来简化计算的方法不适用与逻辑回归，因为计算将非常耗时。

在此不介绍最小化SVM的代价函数的方法，可以使用软件包（如liblinear, libsvm等）。在用这些软件包最小化代价函数之前，通常需要编写核函数，如果我们使用高斯核函数，那么在使用之前进行特征缩放是非常必要的。

下面是SVM的两个参数 C 和 σ 的影响： C=1/λ

• C 较大时，相当于 λ 较小，可能会导致过拟合，高方差；
• C 较小时，相当于 λ 较大，可能会导致低拟合，高偏差；
• σ 较大时，可能会导致低方差，高偏差；
• σ 较小时，可能会导致低偏差，高方差。

使用SVM

上面已经讨论了SVM理论，那如何运用SVM？ 已经介绍了SVM算法，但不建议自己写软件求解参数 θ ，就像今天很少人或者其实没有人考虑自己写代码来转换矩阵，或求一个数的平方根等。只是知道如何调用库函数来实现。 同样的，解决SVM最优化问题的软件很复杂，且已经有研究者做了很多年数值优化。 因此你提出好的软件库和好的软件包来做这样一些事儿。 然后强烈建议用高优化软件库中的一个，而不是尝试自己落实一些数据。 有许多好的软件库，用得最多的两个是liblinear和libsvm，但还要其他很多。

在高斯核函数之外还有其他选择，如：

• 多项式核函数（PolynomialKernel）
• 字符串核函数（Stringkernel）
• 卡方核函数（chi-squarekernel）
• 直方图交集核函数（histogramintersectionkernel）
• 等等...

这些核函数的目标也都是根据训练集和地标之间的距离来构建新特征，这些核函数需要满足Mercer's定理，才能被SVM的优化软件正确处理。

---

多类分类问题

假设利用之前介绍的一对多方法来解决多类分类问题。 如果一共有 k 个类，则需要 k 个模型，以及 k 个参数向量 θ 。 也可以训练 k 个SVM来解决多类分类问题。 但是大多数SVM软件包都有内置的多类分类功能。

尽管不用写SVM的优化软件，但需要：

1. 提出参数 C 的选择。我们在之前讨论过误差/方差在这方面的性质。

2. 选择内核参数或想要使用的相似函数，其中一个选择是：

   • 选择不需要任何内核参数，没有内核参数的理念，也叫线性核函数。因此，如果有人说他使用了线性核的SVM，这就意味这他使用了不带有核函数的SVM。

什么时候使用SVM

从逻辑回归模型，得到了SVM模型，在两者之间，应该如何选择呢？

下面是一些普遍使用的准则： n 为特征数， m 为训练样本数

1. n >> m 而言，即训练集数据量不够支持训练一个复杂的非线性模型，我们选用逻辑回归模型或者不带核函数的SVM。（可能没有足够的数据训练一个非线性函数，但是对于线性函数是ok的）

2. n 较小， m 中等大小，例如 n 在1-1000之间，而 m 在10-10000之间，使用高斯核函数的SVM。

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

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

SVM包会工作得很好，但它们仍然有些慢。 当有非常大的训练集，用核函数的SVM可能很慢。 可以考虑创建更多的特征变量 n ，然后用逻辑回归或不带核函数的SVM。

对于逻辑回归或者不带核函数的SVM，经常把他俩把它们放在一起讨论是有原因的：

• 逻辑回归和不带核函数的SVM它们都是非常相似的算法，不管是逻辑回归还是不带核函数的SVM，通常都会做相似的事情，并给出相似的结果。但是根据你实现的情况，其中一个可能会比另一个更有效。在另一些问题上，可能一个有效，另一个效果不好。
• 但随着SVM的复杂度增加，当使用不同的内核函数学习复杂的非线性函数时，如当有多达1万（10,000）的样本时，也可能是5万（50,000），特征变量的数量相当大。不带核函数的SVM就会表现得相当突出。

---

那神经网络呢？ 对于所有的这些问题，一个设计得好的神经网络可能会非常有效。 但有个 缺点是神经网络训练起来可能会特别慢。

一个非常好的SVM实现包，它可能会运行得比较快比神经网络快很多。 此外，SVM的优化问题是一种凸优化问题。因此，好的SVM优化软件包总是会找到全局最小值，或者接近它的值。对于SVM你不需要担心局部最优。

在实际应用中，局部最优不是神经网络所需要解决的一个重大问题，所以这是你在使用SVM的时候不需要太去担心的一个问题。

算法确实很重要，但是通常更加重要的是数据量、有多熟练是否擅长做误差分析和排除学习算法，指出如何设定新的特征变量和找出其他能决定学习算法的变量等方面，通常这些方面会比你使用逻辑回归还是SVM这方面更加重要。

当然SVM仍然被广泛认为是一种最强大的学习算法。实际上SVM与逻辑回归、神经网络一起构建了一个很好的机器学习算法武器库。

Jupyter Notebook编程练习

• 推荐访问Google Drive的共享，直接在Google Colab在线运行ipynb文件：
  • Google Drive: 6.svm
• 不能翻墙的朋友，可以访问GitHub下载：
  • GitHub: 6.svm

阅读推荐

• 支持向量机SVM - by Jerrylead
• 支持向量机系列 - by pluskid

回到顶部