cjmcv

VC维

对一个指标函数集，如果存在H个样本能够被函数集中的函数按所有可能的2的H次方种形式分开，则称函数集能够把H个样本打散；函数集的VC维就是它能打散的最大样本数目H。若对任意数目的样本都有函数能将它们打散，则函数集的VC维是无穷大，有界实函数的VC维可以通过用一定的阈值将它转化成指示函数来定义。

VC维反映了函数集的学习能力，VC维越大则学习机器越复杂（容量越大），学习能力越强，但推广能力越差，置信风险也越大（即过学习）。遗憾的是，目前尚没有通用的关于任意函数集VC维计算的理论，只对一些特殊的函数集知道其VC维。例如在N维空间中线形分类器和线形实函数的VC维是N+1。

例子：http://www.tuicool.com/articles/JjaMfe , 如圆只能分开两个点，为2维； 直线只能分开三个点，为3维；（2D线性判别为3维）

结构风险最小化原则（Structural Risk Minimization, SRM）

所谓的结构风险最小化就是在保证分类精度（经验风险）的同时，降低学习机器的 VC 维，可以使学习机器在整个样本集上的期望风险得到控制。即把函数集构造为一个函数子集序列,使各个子集置信范围的大小进行排列，也就是按照VC维的大小排列；在每个子集中寻找最小经验风险,在子集间折衷考虑经验风险和置信范围,取得实际风险的最小。 例如：神经网络中出现的过学习问题是因为神经网络在学习过程中选择的模型具有太高的VC维。

在SRM原则下，一个分类器的设计过程分为两步：1、选择分类器的模型，使其VC维较小，即置信范围小； 2、对模型进行参数估计，使经验风险最小。

置信风险的影响因素有：训练样本数目和分类函数的VC维。训练样本数目，即样本越多，置信风险就可以比较小；VC维越大，问题的解的种类就越多，推广能力就越差，置信风险也就越大。因此，增加样本数，降低VC维，才能降低置信风险。 而一般的分类函数，需要提高VC维，即样本的特征数据量，来降低经验风险，如多项式分类函数。如此就会导致置信风险变高，结构风险也相应变高。过度学习即overfit，就是置信风险变高的缘故。

结构化风险 = 经验风险 + 置信风险；经验风险 = 分类器在给定样本上的误差；置信风险 = 分类器在未知文本上分类的结果的误差。

Mercer定理

核函数的确定并不困难，满足Mercer定理的函数都可以作为核函数。常用的核函数有：线性核函数，多项式核函数，径向基核函数，Sigmoid核函数和复合核函数。Mercer定理只是告诉我们对于有的空间是否存在一个候选的核是积核，因此是否能被支持向量机采用。重要性在于对于可用核的数量进行了限制。内积核被称为Mercer核。

定义：对于任意给定的对称函数K(x,y)，它是某个特征空间中的内积运算的充分必要条件是对于任意的不恒为0的函数g(x)，且 ，有 。上式给出了一个函数成为核函数的充要条件。

目前获得应用的核函数主要有以下形式：

对偶定理

原问题是处理凸代价函数和线性约束的。

对偶问题：任何一个求极大化的线性规划问题都有一个求极小化的线性规划问题与之对应，反之亦然，如果我们把其中一个叫原问题，则另一个就叫做它的对偶问题，并称这一对互相联系的两个问题为一对对偶问题。在求出一个问题解的同时，也给出了另一个问题的解。

1. 如果原问题有最优解，对偶问题也有最优解，并且相应的最优值是相同的。

2. 为了使得w0为原问题的一个最优解和a0为对偶问题的一个最优解的充分必要条件是w0对原问题是可行的.

支持向量机和神经网络的比较

• 神经网络是个“黑匣子”，优化目标是基于经验风险最小化（即存在过学习，泛化能力不足），易陷入局部最优，训练结果不太稳定，一般需要大样本；

• 支持向量机有严格的理论和数学基础，基于结构风险最小化原则, 泛化能力优于前者，算法具有全局最优性, 是针对小样本统计的理论，通过核函数构造线性判别函数。（一种通用的前馈网络）