状态函数的含义及其基本特征是什么,态函数的特点是什么( 四 ) _生活百科

这部分内容思路比较凌乱，还需要先研究下《非线性规划》中的约束极值问题，再回头看看。KKT的总体思想是将极值会在可行域边界上取得，也就是不等式为0或等式约束里取得，而最优下降方向一般是这些等式的线性组合，其中每个元素要么是不等式为0的约束，要么是等式约束。对于在可行域边界内的点，对最优解不起作用，因此前面的系数为0 。
7 最优间隔分类器(optimal margin classifier)
重新回到SVM的优化问题:
我们将约束条件改写为:
从KKT条件得知只有函数间隔是1(离超平面最近的点)的线性约束式前面的系数，也就是说这些约束式，对于其他的不在线上的点( )，极值不会在他们所在的范围内取得，因此前面的系数 .注意每一个约束式实际就是一个训练样本。
看下面的图:
实线是最大间隔超平面，假设×号的是正例，圆圈的是负例。在虚线上的点就是函数间隔是1的点，那么他们前面的系数，其他点都是。这三个点称作支持向量。构造拉格朗日函数如下:
注意到这里只有没有是因为原问题中没有等式约束，只有不等式约束。
下面我们按照对偶问题的求解步骤来一步步进行，
首先求解的最小值，对于固定的，的最小值只与w和b有关。对w和b分别求偏导数。
并得到
将上式带回到拉格朗日函数中得到，此时得到的是该函数的最小值(目标函数是凸函数)
代入后，化简过程如下:
最后得到
由于最后一项是0，因此简化为
这里我们将向量内积表示为
此时的拉格朗日函数只包含了变量。然而我们求出了才能得到w和b 。
接着是极大化的过程，
前面提到过对偶问题和原问题满足的几个条件，首先由于目标函数和线性约束都是凸函数，而且这里不存在等式约束h 。存在w使得对于所有的i，。因此，一定存在使得是原问题的解，是对偶问题的解。在这里，求就是求了。
如果求出了，根据即可求出w(也是，原问题的解) 。然后
即可求出b 。即离超平面最近的正的函数间隔要等于离超平面最近的负的函数间隔。
关于上面的对偶问题如何求解，将留给下一篇中的SMO算法来阐明。
这里考虑另外一个问题，由于前面求解中得到
我们通篇考虑问题的出发点是，根据求解得到的，我们代入前式得到
也就是说，以前新来的要分类的样本首先根据w和b做一次线性运算，然后看求的结果是大于0还是小于0,来判断正例还是负例。现在有了，我们不需要求出w，只需将新来的样本和训练数据中的所有样本做内积和即可。那有人会说，与前面所有的样本都做运算是不是太耗时了?其实不然，我们从KKT条件中得到，只有支持向量的，其他情况。因此，我们只需求新来的样本和支持向量的内积，然后运算即可。这种写法为下面要提到的核函数(kernel)做了很好的铺垫。这是上篇，先写这么多了。
7 核函数(Kernels)
考虑我们最初在“线性回归”中提出的问题，特征是房子的面积x，这里的x是实数，结果y是房子的价格。假设我们从样本点的分布中看到x和y符合3次曲线，那么我们希望使用x的三次多项式来逼近这些样本点。那么首先需要将特征x扩展到三维，然后寻找特征和结果之间的模型。我们将这种特征变换称作特征映射(feature mapping) 。映射函数称作，在这个例子中
我们希望将得到的特征映射后的特征应用于SVM分类，而不是最初的特征。这样，我们需要将前面公式中的内积从，映射到。
至于为什么需要映射后的特征而不是最初的特征来参与计算，上面提到的(为了更好地拟合)是其中一个原因，另外的一个重要原因是样例可能存在线性不可分的情况，而将特征映射到高维空间后，往往就可分了。(在《数据挖掘导论》Pang-Ning Tan等人著的《支持向量机》那一章有个很好的例子说明)