支持向量机算法 SVM

作者:kamidox

支持向量机算法 SVM 是 Support Vector Machine 的缩写,它是工业和学术界都有广泛应用的强大的算法。

从逻辑回归算法谈起

逻辑回归算法的预测函数

逻辑回归算法的预测函数称为 Sigmoid Function ,如下图:

contacts_structure

这意味着,针对 y=1,我们希望预测值 h(x)1,那么只要 z=θTx0 即可。相同的道理,针对 y=0,我们希望预测值 h(x)0,那么只要 z=θTx0 即可。

逻辑回归算法的成本函数

回顾之前的知识,逻辑回归算法的成本函数如下

J(θ)=1m[i=1my(i)log(hθ(x(i)))+(1y(i))log(1hθ(x(i)))]+λ2mj=1nθ2j

如果我们去掉 1m 和累加器,同时暂时不考虑正则项,则可以得到另外一个样式的成本函数:

J(θ)=y(i)log(hθ(x(i)))(1y(i))log(1hθ(x(i)))

y(i)=1 时,1y(i)=0,故这一式子再简化为:

J(θ)=y(i)log(hθ(x(i)))=log(11+ez)

把上述函数以成本 J 为纵坐标,z 为横坐标,画出来的函数曲线如下:

cost 1

从图中可以看到,针对 y=1 的情况,如果 z=θTx1 时,成本将很小。支持向量机的原理,就是简化逻辑回归算法的成本函数,以 z=1 为分界线,当 z<1 时,把成本函数简化为一条斜线,当 z>=1 时,直接把成本简化为 0。如上图洋红色所示。

相同的道理,针对y(i)=0 时,变形后的逻辑回归算法成本函数简化为:

J(θ)=(1y(i))log(1hθ(x(i)))=log(111+ez)

把上述函数以成本 J 为纵坐标,z 为横坐标,画出来的函数曲线如下:

cost 1

从图中可以看到,针对 y=0 的情况,如果 z=θTx1 时,成本将很小。支持向量机的原理,就是简化逻辑回归算法的成本函数,以 z=1 为分界线,当 z<1 时,把成本函数简化为 0,当 z>=1 时,把成本简化一条斜线。如上图洋红色所示。

支持向量机算法的成本函数

根据上面的定义,支持向量机把成本函数分成两部分,一部分是针对 y=1 的情况,它是一个以 z=1 为分界点的折线。另外一部分是针对 y=0 的情况,它是以 z=1 为分界点的折线。我们把这两个情况合并起来,并把正则项加上去,就得到支持向量机的成本函数:

J(θ)=C[i=1my(i)cost1(θTx(i))+(1y(i))cost0(θTx(i))]+12j=1nθ2j

这就是用在支持向量机算法里的成本函数。这里的参数 C 越大,正则项的比重就越小,就容易造成过拟合。反之,如果 C 越小,正则项的比重就越大,就容易造成欠拟合。

支持向量机的预测函数

我们定义支持向量机的预测函数如下:

hθ(x)=1,0,if θTx >= 1if θTx <= -1

这里和逻辑回归算法比较,针对逻辑回归算法,其正负样本分界线为 θTx=0,即 θTx>0 时为正样本,当 θTx<0 时为负样本。而支持向量机的分类预测函数要求更严格,它要求 θTx>=1 时为正样本,θTx<=1 时为负样本。根据支持向量机的成本函数图形,只有这样成本才最小,即成本为零。如下图所示:

svm cost

大间距分类算法

支持向量机也称为大间距分类算法。大间距的意思是,用 SVM 算法计算出来的分界线会保留对类别最大的间距,即有足够的余量。

我们看一个比较极端的情况,假设我们选取一个很大的值作为参数 C 的值,那么为了让成本最小,我们必须让成本函数的前半部分为 0,这样成本函数就只剩下:

J(θ)=12j=1nθ2j

求解这个函数的结果,就会让我们获得一个较大间距的分类算法。如下图所示,假设我们有个分类问题。那么洋红色和绿色的都可以是合法的分界线,但 SVM 可以得到黑色的分界线,即确保到两个类别有最大的间距。

svm decision boundary

为什么求解 J(θ)=12nj=1θ2j 会得到最大间距的分界线呢?这个我们留到下面详细解释。

我们接着看下图,如果我们的参数 C 很大,那么可能发生过拟合,即左下角的一个异常的红色样例 X 可能会导致决策界从黑色线变成洋红色线。但实际上,直观地来理解,这样的转变是不合理的,我们仍然希望得到黑色的决策界。这个时候,我们可以调整参数 C ,让 C 的值不要太大,这样就不会被左下角的红色 X 异常样例的干扰,照样得到黑色的决策边界。

svm overfitting

与逻辑回归算法类比,C 相当于 1λ。通过调整 C 可以让 SVM 算法不至于过拟合,也不至于欠拟合。

从数学角度理解大间距分类算法

向量内积的几何含义

假设 u, v 是一个二维列向量,那么 uTv 表示向量 v 在 向量 u 上的投影的长度。可以通过在二维平面上画出向量 u 和向量 v 来更清楚地看这个关系。

vector inner product

uTv=u1v1+u2v2=pu

其中 p 就是 v 在 u 上的投影的长度,它是有符号的实数;u 是向量 u 的范数,即向量 u 的长度,其值为 u21+u22

从数学上理解为什么支持向量机会把类别边界的间距做到最大

假设我们只有两个特征,即 n = 2,则 J(θ)=12nj=1θ2j 简化为:

J(θ)=12(θ21+θ22)=12(θ21+θ22)2=12θ2

回到 SVM 算法的预测函数:

hθ(x)=1,0,if θTx >= 1if θTx <= -1

即当预测为正样本时,我们需要 θTx>=1,这个式子可以理解为向量内积,它的几何含义是x 在 θ 上的投影的长度大于等于 1,即 pθ>=1。如下图所示:

theta and x inner product

而我们的算法求解目标是使 J(θ)=12θ2 最小,所以 SVM 算法的求解目标就是要让 p 尽可能最大。即使所有的训练样例点 xi 到参数向量 θ 的投影长度最大。在几何上,决策边界和参数 θ 是正交的。如下图所示:

svm decision boundary

绿色线为决策边界,绿色线为 θ 所代表的向量。那么 SVM 的求解目标就是让各个训练样例的点 xiθ 上的投影长度最大。上图中,我们可以试着换一个决策边界,试着画出训练样例到这个新的决策边界所决定的参数 θ 的投影长度,即可理解为什么 SVM 可以让决策边界得到最大的间距。

发表评论

0个评论

我要留言×

技术领域:

我要留言×

留言成功,我们将在审核后加至投票列表中!

提示x

人工智能机器学习知识库已成功保存至我的图谱现在你可以用它来管理自己的知识内容了

删除图谱提示×

你保存在该图谱下的知识内容也会被删除,建议你先将内容移到其他图谱中。你确定要删除知识图谱及其内容吗?

删除节点提示×

无法删除该知识节点,因该节点下仍保存有相关知识内容!

删除节点提示×

你确定要删除该知识节点吗?