我们先对上一讲的对偶问题进行回顾. 线性svm的局限 由于线性svm最终的二次规划求解QP的复杂度依靠 d+1 个变量和N个条件的.当对非线性的数据进行使用时,要把x域映射的z域里.z域特征的维度一定是比x高的.因为你要处理非线性,一定是把低维数据映射到高维数据(x映射到z).有的时候,这一映射,特征就增加很多,甚至可以达到无限维的情况.则 d+1 就可能增加到无穷.那么在用线性的svm处理非线性且高维数据时,及时计算到天荒地老也计算不完. 对偶形式的svm 为了解决线性svm的问题,我们就希望设计一个svm,使得他不依赖转换后z域的特征变量数d. 于是我们考虑使用对偶的方法解决这个问题. 我们最终计算的结果为 这看起来不想线性svm那样,没有明确的z域变量 Φ(x) ,但其实在我们将该公式丢到二次规划的软件里时,他计算的 QD 的运算量其实就很受 d˜ 的影响.因为 QD 的每一个元素的计算公式为 这其实就用了z域变量z了.所以当映射后,特征变得很多,那么 zTz 计算量就会很大.即对偶形式的svm其实依然是考虑了z域变量z的特征数的,即考虑了 d˜ 的.这其实和线性svm一样.即
有的人问,将x映射到z,特征能够增加这么多吗? 我们假设x的维度为d,当我们将其映射到z域,我们就仅仅将1次方映射到2次方,所得的特征为 多吧!再就是对应相乘再相加就所得计算量非常复杂. 那么我们现在用 核函数 真正的解决z域特征问题.
我们现在解决对偶函数中计算运算量大的问题. 为了便于表达,我们还是以映射到2次方为例. 其实可以化简为 则我们只需计算维度小的x的内积,再把x的内积代进去,经过一次乘法2个加法就表示了 Φ(x) 的内积. x是d维的,那么复杂度为O(d),可是 Φ(x) 的内积的复杂度达到 O(D2) 所以我们就定义这个例子的核函数K为 我们不仅仅可以用核函数k简化 qm,n ,还可以简化b的求解和与w的内积,具体为以下三种情况可以化简 这样就把所有与z域变量发生内积的情况都换成了核函数 k(x,x′) .就避免了z域的特征数目. 则以上的化简和其复杂度可以总结为 则kernel SVM 有效的避免了z域的自由度 d˜ .还充分运用了支持向量来计算.
上面我们所将的二次多项式kernel仅仅是其中的一小部分,把其系数或者幂次改变后,依然是多项式核. 比如二次多项式如果改变其系数,就可以变形为 其中 改变了核,就改变了最大边界的定义.即会有不同的几何边界 我们把幂次改变后,也是多项式kernel函数
SVM+多项式kernel =多项式SVM
当多项式和的Q为1,左边系数为0,右边系数为1时,结果就是线性kernel函数 其实他就是我们讲的最基础的svm.用于处理线性可分的数据. 一般情况他是非常有效的,且计算迅速.也是最简单的形式. 所以,以后用SVM都应该先考虑线性的KERNEL函数.
如果我们的映射 Φ(x) 是无穷多维时该怎么办? 可以考虑高斯kernel 函数. 为什么他可以处理无穷多维呢??其推导公式为 可以发现,这里的 Φ(x) 是无穷多维的. 我们对上上图的k(x,x’)推广到一般形式,就是一般形式的高斯kernel 函数 则计算可化简为 不难发现,这里只用计算 αn 不为0的情况,而 αn 不为0的情况很少,所以计算量很少.再加上核函数的化简,使得计算量更少了. 注意:
当然,你可以自己设计一个核函数,可是你必须证明他是可行的,这就比较复杂了,不好弄啊!!!