机器学习（四）：SVM

机器学习系列主要为 我在国科大研一期间，在《机器学习方法与应用》课程中所学知识概述，以及课后补充学习的内容。

----------------------------------------------------------------------------------------------------------------------------------
支持向量机（Support Vector Machine）：通俗来讲，它是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，即支持向量机的学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。起决定性作用的样本为支持向量，距离决策边界最近。不仅具有坚实的统计学理论基础，还可以很好地应用于高维数据、避免维度灾难问题。它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并且能够推广应用到函数拟合等其他机器学习问题中。支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度，Accuracy）和学习能力（即无措的识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力。

最大边缘超平面：超平面可将两类数据分开，每个超平面都对应着一对平行的超平面，超平面之间的间隔称为超平面的边缘。边缘最大的超平面称为最大边缘超平面。决策边缘越小，决策边界任何轻微的扰动，都可能对分类结果产生较大的影响。具有较大边缘的决策边界比那些具有较小边缘的决策边界具有更好的泛化误差。

线性支持向量机：根据结构风险最小化原理，设计最大化决策边界的边缘的线性分类器，以确保最坏情况下的泛化误差最小。

VC维（Vapnik-Chervonenkis demension）：定义为一组函数，如平面、直线等在空间打散（任意分类）样本的能力。例如，直线的VC维为3，当4个样本点时，无法任意分类。可以简单的理解为问题的复杂程度，VC维越高，一个问题就越复杂。

结构风险最小原理：真实风险 <=  结构风险  =  经验风险（分类器在给定样本上的误差） + 置信风险（多大程度可以信息分类器在未知样本上分类结果）

置信风险：样本数量越大，置信风险越小；VC维越大，推广能力越差，置信风险会变大

核函数：核函数的基本作用就是接收两个低维空间里的向量，能够计算出经过某个变换后在高纬空间里的向量内积值

 

多个类别：

a.一对多法（one-versus-rest,简称1-v-r SVMs)：训练时依次把某个类别的样本归为一类,其他剩余的样本归为另一类，这样k个类别的样本就构造出了k个SVM。分类时将未知样本分类为具有最大分类函数值的那类。

b.一对一法（one-versus-one,简称1-v-1 SVMs）：在任意两类样本之间设计一个SVM，因此k个类别的样本就需要设计k(k-1)/2个SVM。当对一个未知样本进行分类时，最后得票最多的类别即为该未知样本的类别。

c.层次支持向量机（H-SVMs）：层次分类法首先将所有类别分成两个子类，再将子类进一步划分成两个次级子类，如此循环，直到得到一个单独的类别为止。