SVM的一些“宏观（门外汉）”总结

Algorithm

1、SVM的基本思想

• SVM试图寻找一个超平面，将样本中的正例和反例分隔开。
• 但不是很敷衍地简单分开，而是需找使正例和反例之间的间隔margin最大的超平面。
• 换句话说，SVM的目标是寻找一个超平面，使得离超平面比较近的点能有更大的间距。不考虑所有的点都必须远离超平面，只关心求得的超平面能够让所有点中离它最近的点具有最大间距。

2、为什么SVM这么火？

• 如果是待解决的问题本身线性可分，或者数据质量很高，data set本身具备足够的知识供算法学习，那么SVM是多余的。
• 但恰恰相反：
  
  • 现实中的大多数问题，为线性不可分。
  • 要么是数据质量不够高、要么是data set含有的信息量不够。
• SVM应运而生：
  
  • SVM使用一个非线性映射Φ(x)将全部原始数据映射到另一个特征空间，在这个空间中，样本变得线性可分了。WHY：
    
    • 基于著名的Cover定理：将复杂的模式分类问题非线性地投射到高维空间将比投射到低维空间更可能线性可分的。
  • 也就是要找到一个所有样本映射到更高维的空间的映射。
    
    • 呵呵，要找到Φ(x)十分困难。SVM本身无法直接寻找和计算这种复杂的非线性变换。
    • 但是，伟大的数学家们很智慧地通过一种巧妙迂回的方法来间接实现这种非线性变换。即核函数，不仅具备这种超能力，同时又不会增加太多计算量的两全其美的方法。
  • SVM能够这么好用，存在一些源于上帝之手的巧合：
    
    • “碰巧”SVM里需要计算的地方数据向量总是以内积的形式出现；
    • “碰巧”存在能简化映射空间中的内积运算的核函数；
    • “碰巧”大部分的样本对决策边界的贡献为0；

3、概括概括，方便BB

• 支持向量机通过非线性变换将输入空间变换到一个高维的空间，在这个新的空间求最优分类面即最大间隔分类面，而这种非线性变换是通过定义适当的内积核函数来实现的。
• 乍看一下，是先有非线性映射，才去选择核函数。但实际操作是反过来的：
  
  • SVM的非线性映射取决于事先选定的核函数，比如选择RBF核与选择多项式核，所产生的非线性映射是不同的。
  • 也就是说，不同的核函数，对应了一种特有的非线性映射。
• 关于核函数：
  
  • 核函数和映射没有关系。核函数只是用来计算映射到高维空间之后的内积的一种简便方法。
  • 核函数的作用，是隐含着一个从低维空间到高维空间的映射，这个映射可以把低维空间中线性不可分的两类点变成线性可分的。
• SVM的核函数如何选取？
  
  • 从DataSet的角度分析：
    
    • 如果Feature的数量非常大，跟样本数量差不多，这时候选用LR或者是Linear Kernel的SVM； （例如文档分类）
    • 如果Feature的数量比较小，样本数量一般，不算大也不算小，选用SVM + Gaussian Kernel（RBF）；
    • 如果Feature的数量比较小，样本数量很多，需要手工添加一些feature变成第一种情况；
  • 从实验的角度分析：
    
    • 从拟合程度来讲，linear在线性可分的情况下和rbf想过差不多，在线性不可分的情况下rbf明显优于linear，poly在前两种情况下效果都不怎么好，但是在变化剧烈的情况下ploy稍微好点。
    • 从速度来讲，linear是最快的，poly的话因为参数很多，测试中最慢。
    • 从参数而言，linear简单易用，rbf, poly参数较多，但是调参好的话可以得到较好的结果。
  • 使用GMM核函数处理多分类的问题，the tuning-free GMM kernel performs(surprisingly) well compared to the best-tuned RBF kernel.（自己从底层，用Python写。）

4、几个重要的超参数

• “C”：代表的是在线性不可分的情况下，对分类错误的惩罚程度。(来自知乎大牛王赟的解答）
  
  • C值越大，分类器就越不愿意允许分类错误（“离群点”）。如果C值太大，分类器就会竭尽全力地在训练数据上少犯错误，而实际上这是不可能/没有意义的，于是就造成过拟合。
  • 而C值过小时，分类器就会过于“不在乎”分类错误，于是分类性能就会较差，此时会影响SVM对线性不可分数据的分类性能；
  • 所以一般会采用grid search来找到相对较优的C。
• “Gamma”：由于在线性不可分的情况下，我们很难知道到底映射到哪个维度，可以线性可分。所以我们会更倾向于选择“RBF核函数”，将data set映射到无穷维。此时除了要对C调参，还要对Gamma调参。
• 使用ACROA进行参数优化，自己用Python从底层写。

5、A Practical Guide to Support Vector Classification

5.1 Proposed Procedure

• Transform data to the format of an SVM package;
• Conduct simple scaling on the data;
• Consider the RBF kernel;
• Use cross-validation to find the best parameter;
• Use the best parameter C and γ to train the whole training set;
• Test

5.2 Data Preprocessing

• Categorical Feature
  
  • If there are categorical attributes, we first have to convert them into numeric data.
  • We recommend using m numbers to represent an m-category attribute.
  • For example, a three-category attribute such as {red, green, blue} can be represented as (0,0,1), (0,1,0), and (1,0,0).
• Scaling
  
  • The main advantage of scaling is to avoid attributes in greater numeric ranges dominating those in smaller numeric ranges.
  • we scaled the first attribute of training data from [−10, +10] to [−1, +1]. If the first attribute of testing data lies in the range [−11, +8], we must scale the testing data to [−1.1, +0.8]

5.3 Discussion

• In some situations the above proposed procedure is not good enough, so other techniques such as feature selection may be needed.
• Our experience indicates that the procedure works well for data which do not have many features. If there are thousands of attributes, there may be a need to choose a subset of them before giving the data to SVM.