机器学习入门 11-2 SVM背后的最优化问题

全文字数：3944字

阅读时间：18分钟

前言

本系列是《玩转机器学习教程》一个整理的视频笔记。本小节从SVM算法的基本思想推导成最终的最优化数学表达式，将机器学习的思想转换为数学上能够求解的最优化问题。SVM算法是一个有限定条件的最优化问题。

a

SVM背后的最优化问题

SVM算法的本质就是最大化margin，在二分类任务中margin定义为这两个类别的支撑向量所决定的两根直线的距离。本小节以二分类任务为例。

▲最大化margin其实就是最大化d

上一小节提到对于两个类别的SVM算法最终得到的最优决策边界就是两个类别的支撑向量所决定的两根直线中间区域中间位置的那根直线，因此最优决策边界和两根直线之间都有一个称为d的距离，显然margin = 2d，因此SVM算法最大化margin可以转换成最大化d，找到d的数学表达式同样可以求解这个问题。接下来就来看看如何用数学表达式来表达d。

首先来回忆一个高中解析几何的知识：一个点到一根直线的距离。

▲二维平面上点到直线的距离公式

二维平面中求点(x, y)到直线Ax + By + C = 0的距离公式如上图所示，这里需要注意此时的直线方程没有使用斜截式y = kx + b的形式，而是使用一般线性方程来表示，这是因为斜截式y = kx + b的方程形式有一定的局限性。使用斜截式y = kx + b表示的直线不能和x轴垂直（或不能和y轴平行），此时斜率k等于正无穷是用斜截式y = kx + b的形式表达不了的，但是使用一般直线方程Ax + By + C = 0的形式就可以表达。

现在将点到直线的距离公式推广到n维空间。

▲扩展到n维空间点到直线的距离

无论是线性回归算法还是逻辑回归算法都将直线方程表示为θT * xb = 0的形式，此时的θ中第一个元素为θ0，而xb其实就是在样本特征的前面添加一个值为1的元素。这一小节将直线方程表达成wT * x + b = 0的形式，相当于将θ中第一个元素θ0乘以xb中第一个元素值1这一项单独拿出来，将这一项用字母b来表示并称为截距，所有样本特征前面的系数用w来表示，w其实就是weight权重的意思，实际上相当于给x特征向量中每一个特征附加上一个权值。如果样本有n个特征，则θ中有(n + 1)个元素，而相对应的权重w有n个元素，b是一个元素的截距。换句话说，θ向量中的元素就是截距b和权重w的组合。

这一小节为什么要使用wT * x + b = 0的这种形式来表示直线方程呢？在上面二维平面中点到直线的距离公式中分母的位置是根号下A方加B方。换句话说，分母和直线方程中的截距C是没有关系的，这一点同样可以拓展到n维空间中。假设此时n维空间中有一点x，x到wT * x + b = 0这根直线的距离公式如下图所示。

▲n维空间中x到wT*x+b直线的距离

其中w模的计算方式为w向量中每一个维度的元素平方和之后再开根号。通过这个式子可以看出，其实在二维空间中点到直线的距离公式就是n维空间中点到直线距离公式的一种特殊形式，当n维空间中点到直线的距离公式中的n设置为2时即可得到二维空间中点到直线的距离公式。

下面就可以将上面n维空间中点到直线的距离公式的知识点代入SVM算法的思路中。在二分类问题中，假设SVM算法得到的最优决策边界的表达式为wT * x + b = 0，那些距离最优决策边界最近的样本点到最优决策边界的距离为d，换句话说所有样本点到这个最优决策边界的距离都应该大于等于d，将这个想法转换为数学表达式的话得到的公式如下图右部分所示。

▲所有样本点到最优决策边界的距离都应该大于等于d

前面在处理二分类任务中将二分类的类别分别设置为0和1，这一小节为了方便后续的计算将两个类别的值分别设置1和-1，不过这两个类别在数学上取什么值其实并没有多大的影响，设置不同值的目的仅仅是将两个类别区分开。

对于类别值为1的这一类中任取一个样本xi，第i个样本对应的类别值为1，即yi = 1。将所有类别值为1的样本点代入点到直线的距离公式中的话一定是大于等于d的。具体公式如下图所示。

▲类别值为1的样本点到最优决策边界的距离公式

这里将点到直线的距离公式中分子位置的绝对值去掉了，这是因为对于yi = 1的这些样本点来说，代入直线方程以后是位于大于0的那一侧，因此能够保证这些类别值为1的样本点代入直线方程之后都是大于等于0的。

对于类别值为-1的这一类中任取一个样本xi，第i个样本对应的类别值为-1，即yi = -1。将所有类别值为-1的样本点代入点到直线的距离公式中的话一定是小于等于-d的。具体公式如下图所示。

▲类别值为-1的样本点到最优决策边界的距离公式

此时所有类别值为-1的样本点都在最优决策边界的另外一侧，所以将这些样本点代入直线方程之后都小于0。与此同时，希望这些样本点到直线的距离同样是大于等于d，因此将点到直线的距离公式中分子的绝对值去掉之后将大于等于改成小于等于符号并且将d改成-d。

将上面的两个不等式稍微变形一下，将这两个不等式的两边同时除以一个d，具体变形后的式子如下所示。

▲变形后的不等式

由于d表示距离所以为正数，因此不等式两边同时除以d后不等式符号不变。对于变换后的两个不等式中的分母都变成了w的模乘以d。

仔细看上面的这个式子，对于这个式子来说，w是一个n维向量，但是w的模是一个数，与此同时d也是一个数。换句话说，两个不等式的分母都是一个具体的常数，对于两个不等式的分子来说想象成将w向量中的每一个元素都除以分母的这个常数加上截距b除以分母的这个常数。此时将新的向量w称为wd，新的截距b称为bd，对应的式子如下图所示。

▲将分母融合到分子变换的两个不等式

此时：

• 如果样本yi = 1的时候就将这个样本xi代入不等式大于等于1的式子中；
• 如果样本yi = -1的时候就将这个样本xi代入不等式小于等于-1的式子中；

换句话说在我们图中的上下两根直线的直线方程分别是上面两个不等式等于1和等于-1的情况。

▲SVM直线的表达式

最初假设SVM算法的最优决策边界就是两根直线中间位置的那根直线wT*x + b =0。通过前面的一系列推导，最优决策边界上下两侧的直线方程参数都是wb和bd，它们与w和b参数之间相差除以w模乘以d的常数，而对于中间那根最优决策边界的直线方程来说，直线方程的右侧等于0，所以对于这根直线方程来说可以左右两侧同时除以w的模乘以d这个常数。

▲SVM直线的表达式

此时将中间这根直线方程也转换成了wd和bd的参数，和原来wT*x + b = 0的直线方程仅仅相差一个常数，因此两个式子是等价的。比如2x + y = 0所表示的直线方程和4x + 2y = 0所表示的直线方程是同一根直线。

现在这些直线方程的参数全都是用wd和bd，wd是一个含有n个元素的向量，bd是一个数。既然这些直线方程都使用wd和bd这两个未知量来表达，因此这里重新将这两个未知量命名为w和d，这样做的目的是方便后续的计算书写。将wd和bd重新命名为w和d后的结果如下图所示。

▲将wd和bd重新命名为w和d

这里需要注意，此时更改后的w和d和一开始式子中所写的w和d从理论上看已经不是同一个数了，它们之间相差一个系数。现在使用的这个w和d只是一个代替之前式子中的wd和bd的符号而已。

对于支撑向量机SVM来说，相当于求出了上面两个不等式所表达条件的情况下，相应的w和b是多少。这两个不等式使用起来很不方便，所以这里使用一个小技巧将这两个不等式合并成一个不等式。这个技巧和之前在逻辑回归中使用的技巧非常相似。

▲两个不等式合并成一个不等式

yi = 1的不等式大于等于1，而yi = -1的不等式小于等于-1。

• 对于yi = 1时的不等式，左侧乘以1（yi）以后不等式不变；
• 对于yi = -1时的不等式，左侧乘以-1（yi）以后不等式方向改变，并且不等式右侧的-1变成1；

两个不等式乘上对应的yi值之后的数学表达式一致，因此可以将两个不等式融合成了一个不等式。总的来说，SVM算法中的所有数据样本点都应该满足融合后的那一个不等式。

不要忘记最终目标是要最大化d，d代表的是支撑向量到决策边界的距离。

▲d的表达式

上面式子中的x是某一个支撑向量，通过之前的推导可以看出代入支撑向量，直线方程要么等于1要么等于-1。换句话说，对于任意的支撑向量要么是红色类别的支撑向量要么是蓝色类别的支撑向量，不论是那一个类别的支撑向量取绝对值之后的结果都为1，所以此时最大化的目标变成了最大化w模分之一。

▲最大化w模分之一

最大化w模分之一相当于最小化w模。在具体求解这个问题的时候，通常最小化的目标不是w的模，而是最小化1/2乘以w模的平方，这样写可以方便后续的求导。

▲最终最小化1/2w模的平方

因此整个支撑向量机算法变成了最优化目标函数1/2乘以w模的平方，不过在这里有一个限定条件，这个条件就是对于所有的数据样本点需要满足yi * (wT * xi + b) ≥ 1。

▲支撑向量机有条件的最优化问题

通常在有条件的最优化问题的表达中在限定条件的前面加上s.t.（such that）。线性回归和逻辑回归算法中的最优化都是没有限定条件的全局最优化问题，而对于SVM算法来说最优化问题是一个有限定条件的最优化问题。加不加限定条件在最优化的领域中求解问题的方法是大不相同的。

• 如果没有任何限定条件的全局最优化问题只需要对目标函数求导数，并将导数等于0求得对应目标函数的极值点，极值点的位置就是目标函数取最大值或者最小值的位置；
• 如果有限定条件的最优化问题求解的方式比较复杂，比如使用拉普拉斯算子，但是这些方法对数学的要求比较高；

b

小结

本小节从SVM算法的思想一直推导到最后一个具体形式的数学表达式，将机器学习算法转变成一个在数学上求解最优化的问题。本小节介绍的最优化问题其实解决的是Hard Margin SVM的问题，此时处理的数据是线性可分的。大多数情况下数据不是线性可分的，此时就必须使用Soft Margin SVM。下一小节将会介绍Soft Margin SVM。