机器学习笔记6: 支持向量机(上)

2018-04-15 本文已影响83人 secondplayer

在接下来的两篇文章里，我们会着重介绍支持向量机(Support Vector Machine)算法，以下简称为SVM。SVM可以称得上是监督学习里最优秀的算法了，在诸如文本分类，图像识别，生物序列分析等领域有很多的应用。

本篇文章首先介绍间隔(margin)的概念，然后给出最优间隔分类器(optimal margin classifier)的定义，同时将该问题转化为一个凸优化(convex optimization)问题，随后补充介绍拉格朗日对偶性(Lagrange duality)的知识，并由此推导出最优间隔分类器的对偶问题。

符号表示

为了使SVM的描述更简单，我们需要对之前的符号表示做一些修改。对于一个二元线性分类器，特征向量是x，输出分类是y。之前y的取值是0和1，现在我们把取值修改为-1和1。之前假设函数h(x)是以θ作为参数，即：

现在我们使用w和b作为参数，即：

其中，如果z >= 0，那么g(z) = 1，否则g(z) = -1。用w和b表示可以显式地让我们把截距(intercept)b从其他参数中分离出来。对比两种h(x)的定义，b相当于原来的θ₀，w相当于剩余的参数[θ₁, θ₂, ..., θ_n]^T。

注意，由于g(z)的定义变了，现在我们的分类器可以直接输出1或者-1，而不是像逻辑回归那样先求出y = 1的概率，再根据概率预测输出。

函数间隔和几何间隔

下图是一个线性分类器的图示，图中显示了训练集的两个分类数据(分别用圈和叉表示)，以及一个决策边界(decision boundary)将两类数据分割开。图中的直线是w^Tx + b = 0，也被称为超平面(hyperplane)。

图中有三个点A、B和C，其中A离超平面最远，C离超平面最近，因而我们认为A比C有更大的可能性属于叉的分类。那么，我们应该确定这个超平面呢？从直觉上看，这个超平面应该使每个点离超平面的间隔都尽可能大。

为了确定这个超平面，我们需要正式给出间隔(margin)的定义。对于训练数据(x⁽ⁱ⁾, y⁽ⁱ⁾)，我们定义它与超平面(w, b)的函数间隔(functional margin)为：

如果y⁽ⁱ⁾ = 1，那么w^Tx + b必须是正数，并且w^Tx + b越大，函数间隔越大；相反地，如果y⁽ⁱ⁾ = -1，那么w^Tx + b必须是负数，并且w^Tx + b越小，函数间隔越大。因而函数间隔越大，分类预测的可信度越高。

有了单个训练数据的函数间隔的定义，我们可以定义整个训练数据集的函数间隔是所有训练数据的函数间隔的最小值，即：

函数间隔虽然可以表示分类预测的可信度，但它有一个缺点：如果我们成比例地增大w和b(比如把w和b替换成2w和2b)，那么函数间隔的值也会成比例地增大，然而超平面本身并没有改变，因此这样是无意义的。直觉上看，我们需要对参数作一些约束，比如限制||w|| = 1，而这就引出了几何间隔(geometric margin)的定义。

几何间隔实际上就是数据点到超平面的垂直距离，比如上图中点A的几何间隔就是A到超平面的距离AB，根据平面几何的知识可以求出数据点(x⁽ⁱ⁾, y⁽ⁱ⁾)到超平面(w, b)的距离为：

上式就是几何间隔的定义。可以看到，如果||w|| = 1，那么几何间隔就等于函数间隔。

另外如果我们任意缩放w和b，那么几何间隔并不会随之改变。

同样地，整个训练数据集的几何间隔是所有训练数据的几何间隔的最小值，即：

一般地，函数间隔和几何间隔有如下关系：

最优间隔分类器的定义

上面我们讨论到，寻找最优超平面的条件应该使每个点离超平面的间隔都尽可能大，因而最优超平面也被称为最优间隔分类器(optimal margin classifier)。并且由于“任意缩放w和b，几何间隔并不会随之改变”，上述讨论中的间隔应该使用几何间隔，所以最优间隔分类器问题可以定义为：

这个优化问题解决起来比较棘手，因为目标函数是非凸函数，我们没有办法用现成的软件可以解决这个问题。再次考虑“任意缩放w和b，几何间隔并不会随之改变”这个结论，我们可以对该问题增加一个约束：函数间隔等于1，并且最大化1 / ||w||等价于最小化||w||² ，那么问题被转化为：

这样我们就把原始问题转化成了一个凸优化问题，而这个问题可以用现成的二次规划(quadratic programming)软件来求解。

拉格朗日对偶性

这一部分我们介绍拉格朗日对偶性(Lagrange duality)，其核心思想是通过拉格朗日对偶性可以将原始问题转化为对偶问题，而对偶问题通常比较容易求解。

考虑如下优化问题：

即最小化函数f(w)，并且满足l个等式约束(equality constraint)条件h_i(w) = 0。定义拉格朗日算子(Lagrangian)：

即等于原始目标函数加上约束函数的线性组合，其中β_i是拉格朗日乘数(Lagrange multipliers)。分别求L关于w和β的偏导数即可求出原始问题的解：

上述的优化问题只包含等式约束，而更广义的优化问题还包含不等式约束(equality constraint)。下面我们定义这个广义优化问题，也称为原始优化问题(primal optimization problem)：

即最小化函数f(w)，并且满足l个等式约束条件h_i(w) = 0和k个不等式约束条件g_i(w) <= 0。定义广义拉格朗日算子(generalized Lagrangian)：

其中α_i和β_i是拉格朗日乘数。定义：

下标p表示原始(primal)问题，可以证明：

因此当w满足原始约束条件时，原问题等价为：

为了后面表述方便，定义p^*是原始问题的最优解：

我们再考虑另一个稍微不同的问题，定义：

下标D表示对偶(dual)问题，注意在原始问题中是关于参数α和β求最优解，而对偶问题是关于参数w求最优解。定义对偶优化问题(dual optimization problem)：

和原始优化问题相比，对偶优化问题把max和min的顺序交换了一下。同样为了表述方便，定义d^*是对偶问题的最优解：

原始问题与对偶问题的关系如下：

事实上一个函数的max min值总是小于等于它的min max值，这里我们不作证明。而在某些情况下，我们有：

这种情况下求解原始问题等价于求解对偶问题。下面我们不加证明地给出使得p^* = d^*成立的条件。

假设f和g_i是凸函数，h_i是仿射(affine)函数(即存在a_i和b_i使得h_i(w) = a_i^Tw + b_i)，并且g_i是严格可执行的(strictly feasible)(即存在w使得对于所有g_i(w)<0都成立)。在上述条件下，存在w^*，α^*，β^*，其中w^*是原始问题的解，α^*，β^*是对偶问题的解，并且满足：