前面讨论过在样本线性可分与不可分下的SVM，知道了不管是样本可分还是不可分，不管是狭义的还是广义的，它都是属于线性，那么我们应该如何构造非线性的SVM呢？本篇文章先不讲有关如何构造的问题，先来讨论下传统的广义线性判别函数，从它入手也正是为将来如何构造非线性的SVM打下良好基础。

       首先回顾下线性判别函数，不知道大家还有印象没，对于一个两类问题其形式为，根据线性代数知识，我们知道这是一个类似于一次函数的形式，但是如果一个两类问题的判别函数是二次函数呢，如图举例：

上图中，为了讨论方便，样本特征假设只有一维，且如果b<x<a，则决策为w2类，其余决策为w1类；

       毫无疑问，之前学过的线性判别函数无法对此做出决策，因此需要设计非线性分类器（不是要讲线性的判别函数么，怎么又回到非线性了，不要着急，继续往下学习）。

       对于上图，首先创建一个二次判别函数来实现分类决策：

                  (1)

那么明显有如下决策规则：

g(x)>0,决策为w1类；

g(x)<0,决策为w2类；

试着将公式（1）展开有：

                （2）

将x变换到另外一个特征空间y，即选择x到y的一个有效的映射，总能将公式（2）变成关于y的线性判别函数（这种变换很重要）：

                      (3)

其中，

                              （4）

                                （5）

我们把公式（3）称为广义的线性判别函数，a叫做广义权向量。

       下面，就来解释下这种变化：对于任意高次的判别函数g(x)，当然它也可以看成是对任意判别函数的泰勒级数展开，然后取其截尾后的逼近，对于任意这样的g(x)，总能够通过合适有效的变换，化作上述类似的线性判别函数来处理（需要注意的只是，变换后已不再是x的线性函数，而变成了y的线性函数），因此变换后的线性判别函数也被叫做广义线性判别函数，如此变换后，我们依然可以用线性判别函数来解决复杂问题，从而达到简化的目的，是不是很嗨森啊。

       然而，天下没有免费的午餐，这种简单是有代价的，那就是导致变换后的特征空间维数大大增加，从而陷入维数灾难（the curse of dimensionality），而且判别函数的参数数目也很大，如用广义线性判别函数来构造二次判别多项式，有：

变换前的特征空间是n维（对应上面的d）的，变换后的特征空间为：

                                                                                                                               n维

                                                                                                          n维

                                                                                                 n(n-1)/2维

       所以得到变换后的特征空间维数S=n+n+n(n-1)/2=n(n+3)/2，而对应的广义权向量的维数则为：N=n(n+3)/2+1

对应到上面一维的样本特征，公式（4）中明显有1(1+3)/2=2维，1可不计；而公式（5）中明显参数有1(1+3)/2+1=3；

       如果n非常大，或非线性多项式是高阶的，可想而知变换后有多么大，真是好大一个灾难啊。。而且参数也会非常多，这种惨重的代价一方面会使得计算变得非常复杂而不可行；另一方面，样本特征变换到高维空间，而样本数目并未增加，造成了高维空间中的特征稀疏，从而导致矩阵出现病态，最后算法可能因此而无法进行下去。

       面对这一维数灾难问题，是不是就无解了呢？并不是，如果我们可以对特征进行某种合理的变换，就可以通过在新的特征空间里求线性分类器的办法来实现在原空间里求非线性分类器，而SVM正是巧妙的采用了这一思路来避免高维计算的。

未完待续。。。。。