SVM

SVM算法中最重要的就是核函数，核函数选取的好坏将直接影响最终的分类效果。核函数是把线性不可分的低维特征映射到高维特征空间，把特征转化为线性可分。

符号逻辑回归

给定一些数据点，它们分别属于两个不同的类，现在要找到一个线性分类器把这些数据分成两类。如果用x表示数据点，用y表示类别（y可以取1或者-1，分别代表两个不同的类），一个线性分类器的学习目标便是要在n维的数据空间中找到一个超平面（hyper plane）

Logistic回归目的是从特征学习出一个0/1分类模型，而这个模型是将特性的线性组合作为自变量，由于自变量的取值范围是负无穷到正无穷。因此，使用logistic函数（或称作sigmoid函数）将自变量映射到(0,1)上，映射后的值被认为是属于y=1的概率。
假设函数

其中x是n维特征向量，函数g就是logistic函数。这个函数的图像是

函数间隔和几何间隔

在超平面wx+b=0确定的情况下，|wx+b|能够表示点x到距离超平面的远近，而通过观察wx+b的符号与类标记y的符号是否一致可判断分类是否正确，所以，可以用(y(w*x+b))的正负性来判定或表示分类的正确性。于此，我们便引出了函数间隔（functional margin）的概念。定义函数间隔（用表示）为：

而超平面(w，b)关于T中所有样本点(xi，yi)的函数间隔最小值（其中，x是特征，y是结果标签，i表示第i个样本），便为超平面(w, b)关于训练数据集T的函数间隔：

但这样定义的函数间隔有问题，即如果成比例的改变w和b（如将它们改成2w和2b），则函数间隔的值f(x)却变成了原来的2倍（虽然此时超平面没有改变），所以继续定义几何间隔：

SVM便是一种最大间隔分类器，通过选择超平面能够最大化这个“间隔”值，同时需满足一些条件，根据间隔的定义，有

SVM的目标便是最优这个约束不等式：

核函数

SVM的最有不等式将其转换成拉格朗日对偶问题后，可以得到

其中a为拉格朗日乘子。而分类函数则是

这里的形式的有趣之处在于，对于新点 x的预测，只需要计算它与训练数据点的内积即可（表示向量内积），这一点至关重要，是之后使用 Kernel 进行非线性推广的基本前提。此外，所谓 Supporting Vector 也在这里显示出来——事实上，所有非Supporting Vector 所对应的系数都是等于零的，因此对于新点的内积计算实际上只要针对少量的“支持向量”而不是所有的训练数据即可。
在对特征进行高维映射时，核函数可以直接通过输入并计算当前特征空间的特征，给出映射到高维空间后高维特征内积的结果，即直接在原来的低维空间中进行计算，而不需要显式地写出映射后的结果。核函数能简化映射空间中的内积运算——刚好“碰巧”的是，在我们的 SVM 里需要计算的地方数据向量总是以内积的形式出现的。因此，核函数的引用避开了直接在高维空间中进行计算，而结果却是等价的。

常见核函数

核函数的本质

1. 实际中，我们会经常遇到线性不可分的样例，此时，我们的常用做法是把样例特征映射到高维空间中去(如上文2.2节最开始的那幅图所示，映射到高维空间后，相关特征便被分开了，也就达到了分类的目的)；
2. 但进一步，如果凡是遇到线性不可分的样例，一律映射到高维空间，那么这个维度大小是会高到可怕的(如上文中19维乃至无穷维的例子)。那咋办呢？
3. 此时，核函数就隆重登场了，核函数的价值在于它虽然也是讲特征进行从低维到高维的转换，但核函数绝就绝在它事先在低维上进行计算，而将实质上的分类效果表现在了高维上，也就如上文所说的避免了直接在高维空间中的复杂计算。
   最后引用这里的一个例子举例说明下核函数解决非线性问题的直观效果。
   假设现在你是一个农场主，圈养了一批羊群，但为预防狼群袭击羊群，你需要搭建一个篱笆来把羊群围起来。但是篱笆应该建在哪里呢？你很可能需要依据牛群和狼群的位置建立一个“分类器”，比较下图这几种不同的分类器，我们可以看到SVM完成了一个很完美的解决方案。
   
   这个例子从侧面简单说明了SVM使用非线性分类器的优势，而逻辑模式以及决策树模式都是使用了直线方法。

Tips：

Q: 为什么逻辑回归时，y值的label是-1和1？
具体阐述如下：

• 对于二类问题，因为y只取两个值，这两个是可以任意取的，只要是取两个值就行；
• 支持向量机去求解二类问题，目标是求一个特征空间的超平面，而超平面分开的两类对应于超平面的函数值的符号是刚好相反的；
• 基于上述两种考虑，为了使问题足够简单，我们取y的值为1和-1；
• 在取定分类标签y为-1和1之后，那么，一个平面正确分类样本数据，就相当于用这个平面计算的那个y*f（x）>0；
• 而且这样一来，y*f（x）有明确的几何含义；

总而言之：二类问题的标签y是可以取任意两个值的，不管取怎样的值对于相同的样本点，只要分类相同，所有的y的不同取值都是等价的，之所以取某些特殊的值，只是因为这样一来计算会变得方便，理解变得容易。
举个例子，如你要是取y为1和2，比如原来取-1的现在取1，原来取1的现在取2 ， 这样一来，分类正确的判定标准变为（y-1.5）*f（X)>0 ， 故取1和-1只是为了计算简单方便，没有实质变化，更非一定必须取一正一负。

Q: SVM如何解决多分类问题 ？

• 第一种方法，每次仍然解一个两类分类的问题。比如我们有5个类别，第一次就把类别1的样本定为正样本，其余2，3，4，5的样本合起来定为负样本，这样得到一个两类分类器，它能够指出一篇文章是还是不是第1类的；第二次我们把类别2 的样本定为正样本，把1，3，4，5的样本合起来定为负样本，得到一个分类器，如此下去，我们可以得到5个这样的两类分类器（总是和类别的数目一致）。但有时也会出现两种很尴尬的情况，例如拿一篇文章问了一圈，每一个分类器都说它是属于它那一类的，或者每一个分类器都说它不是它那一类的，前者叫分类重叠现象，后者叫不可分类现象。分类重叠倒还好办，随便选一个结果都不至于太离谱，或者看看这篇文章到各个超平面的距离，哪个远就判给哪个。不可分类现象就着实难办了，只能把它分给第6个类别了……
• 第二种方案，还是每次选一个类的样本作正类样本，而负类样本则变成只选一个类，这就避免了偏斜。因此过程就是算出这样一些分类器，第一个只回答“是第1类还是第2类”，第二个只回答“是第1类还是第3类”，第三个只回答“是第1类还是第4类”，如此下去，这样的分类器应该有5 X 4/2=10个。在真正用来分类的时候，让每一个分类器都投上自己的一票，最后统计票数，如果类别“1”得票最多，就判这篇文章属于第1类。这种方法显然也会有分类重叠的现象，但不会有不可分类现象。看起来够好么？其实不然，想想分类一篇文章，我们调用了多少个分类器？10个，这还是类别数为5的时候，类别数如果是1000，要调用的分类器数目会上升至约500,000个。

Q: 当样本数量很少的情况下，应尽量避免使用非线性映射，因为样本有限的情况下，kernel map通常不准确，很有可能错误地划分类别空间，可能造成比线性模型更差的结果。
有关Liblinear和Libsvm各自的优势可以归纳如下：

• libsvm用来就解决通用典型的分类问题
• liblinear主要为大规模数据的线性模型设计

参考：

支持向量机通俗导论（理解SVM的三层境界） SVM算法入门