首页 > 代码库 > 机器学习技法(1)--Linear Support Vector Machine

机器学习技法(1)--Linear Support Vector Machine

线性支持向量机。

技术分享

在这种分类问题中,我们需要选一条最“胖”的线,而这条最胖的线就是margin largest的线。

技术分享

我们的优化目标就是最大化这个margin。也就是在最小化每一个点到这条线的距离。这个距离怎么计算呢?

技术分享

为了以后不会混淆,w0就不整合成向量w了,另外取一个新名字b。同样地,x0=1也就不用塞进x向量里了。

所以得出:h(x)=sign(wTx+b),而距离distance(x,b,w)满足wTx‘+b=0

技术分享

x‘和x‘‘是平面上的两个点,(x‘‘–x‘)是平面上的向量,如果这个平面上的向量和wT相乘结果是0,那么可以得出wT是垂直于这个平面的,wT是这个平面的法向量。

由此可以推导出距离的公式:

技术分享

这条线还必须得把y进行二元分类,也就是说对于每一个点(xn,yn),这条线都能达到wTxn+b和yn同号。利用同号的性质将绝对值符号拿掉。

技术分享

结合之前的公式,我们的优化目标就是:

技术分享

margin(b,w)表示点到线的距离,是由b和w来决定的,我们的目标就是把它最大化,也就是找到使得点到线的距离“最胖”的b和w;

every yn(wTxn+b)>0表示了每一个点(xn,yn)都可以有一个线将它们分开;

再加上一些放缩的技巧,使得yn(wTxn+b)的值为1,所以就简化了margin(b,w)。

技术分享

于是margin就被简化成:

技术分享

限制条件由yn(wTxn+b)=1放松成yn(wTxn+b)≥1,下图证明了即使把条件放松了,我们的解不会有什么影响。

技术分享

我们的最终需要优化的目标为:

技术分享

可以先把最大化的一个目标去掉倒数,换成是最小化的目标;为了后面方便计算,再乘个1/2。这个问题叫做标准问题。

先代入几个具体的例子看看情况:

技术分享

技术分享

画图之后:

技术分享

图中带方块的点就是支持向量。只有他们才能决定那条线的样子,其他的点没有也没啥关系。

那么,如果generalize这个题目该怎么解呢?

技术分享

用quadratic programming来解!


 

补充知识:https://en.wikipedia.org/wiki/Quadratic_programming

Quadratic programming (QP) is a special type of mathematical optimization problem--specifically, the problem of optimizing (either minimzing or maximizing) a quadratic function of several variables subject to linear constraints on these variables.

Problem formulation:

THe quadratic programming problem with n variables and m constraints can be formulated as follows. Given:

A real-valued, n-dimension vector c;

An n×n-dimensional real symmetric matrix Q;

An m×n-dimensional real matrix A;

An m-dimensional real vector b,

the objective of quadratic programming is to find an n-dimensional vector x, that will

minimize 1/2*Q*xTx + cTx, subject to Ax≤b

the notation Ax≤b means that every entry of the vector Ax is less than or equal to the corresponding entry of the vector b.


技术分享

将我们想求解的方程式调换成标准的二次规划问题的样式,QP的程序就会给我一个答案。

所以总结一下求解的过程:

技术分享

Hard-Margin的意思就是所有点都严格地被分开。如果没有这一条严格的线,就无解。

如果把线升高维度到一个hyperplane:

技术分享

SVM可以看作是一种正则化的解释:

技术分享

另一方面,SVM通过调整“胖瘦”的大小,其实可以间接地做VC Dimension的调节。

技术分享

技术分享

当我们通过Φ将线性不可分的数据升高维度到一个线性可分的维度的时候,我们用SVM就可以控制模型的复杂度。

总结:

技术分享

机器学习技法(1)--Linear Support Vector Machine