14.1.3 VC维与学习一致性理论
对于二值分类问题，其目标函数f只有0和1两种取值，称这类函 数为指示函数。
?对于一个指示函数集的VC维是指能够被“打散”(即，被里的 函数按照所有可能的形式分开)的样本集合可能具有的最大样 本数(或称作样本集合的最大基数)，记作VC ? Dim(H) 。
?一般而言，VC维代表了机器的学习能力，其值越大表明其学 习机器的学习能力越强，但学习机器就越复杂。然而，目前还 没有通用的关于计算任意函数集的VC维的理论，只有对一些 特殊函数集的VC维可以准确知道。
?支持向量机从诞生至今才 10多年，发展史虽短，但 其理论研究和算法实现方面却都取得了突破性进展 ，有力地推动机器学习理论和技术的发展。这一切 与支持向量机具有较完备的统计学习理论基础的发 展背景是密不可分的。
? 统计方法是从事物的外在数量上的表现去推断该事物可能的 规律性，它主要考虑测试预想的假设和数据模型拟合，依赖 于显式的基本概率模型。
的估计值，学习的目标就是使经验风险Remp最小，强调利用经 验风险最小化（ ERM ）原则进行学习。但实际上，用ERM
原则代替最小化期望风险泛函，只是直观上合理的想当然做
法而已，理论依据并不充分，容易“过学习”(overfitting)。
it
overfitting
?对于指示函数集和概率分布函数，如果下列两序列概率地收敛
到同一极限，则称为经验风险最小一致性。
p
inf Remp (wl ) ? l???? ?
R(w).
w? ?
p
inf R(wl ) ? l???? ?
R(w),
w? ?
图14-3 经验风险最小一致性
?在VC维和学习一致理论基础上，Vapnik 等人证明了对二值分
2. 学习过程收敛速度的理论。如果学习过程的经验风险与实际风险趋向一致 ，那么它们间的接近速度随着训练样本数的增加是如何变化的。哪些因素 控制着它们接近的速度。
3. 控制学习过程泛化能力的理论。采用前两部分的结论改进学习过程。 4. 构造学习算法的理论。采用前三部分的结论，在分类和拟合问题中构造现
实的学习算法。
解释了机器学习中的过学习问题，并建立起适用于小样本数据的结构风险
数据挖掘原理与SPSS Clementine 应用宝典
? 元昌安 主编 邓 松 李文敬 刘海涛 编著
电子工业出版社
14.1支持向量机基础 14.1.1机器学习的基本问题 14.1.2经验风险最小化问题 14.1.3 VC维与学习一致性理论 14.1.4结构化风险最小化 14.2支持向量机的基本原理 14.2.1线性支持向量机 14.2.2广义线性支持向量机 14.2.3非线性支持向量机 14.2.3.1到高维空间的影射 14.2.3.2核函数
类问题，指示函数集中所有的函数，经验风险和实际风险之间 至少以概率满足如下关系:
?
lim P???R(w) ? Remp (w) ?
n? ? ? ??
H
(ln
2n H
? n
1)
?
ln
?
4
? ?? ? ?
?
1
?
?
??
其中，H ? VC ? Dim(? ) 是函数集的VC维，n是样本数。上式实质上
给出了ERM原则的泛化能力的界。在此基础上，Vapnik等人从理论角度
元昌安 主编 邓 松 李文敬 刘海涛 编著
电子工业出版社
14.1支持向量机基础
?支持向量机 (support vector machines) 是由贝尔实 验室研究者 Vapnik 于20世纪90年代最先提出的一种 新的机器学习理论，是建立在统计学习理论的 VC维 理论和结构风险最小原理基础上的，根据有限的样 本信息在模型的复杂性和学习能力之间寻求最佳折 衷，以期获得最好的推广能力。
其中 F (x, y) 联合概率分布是未知的，L( y, f (x, w)) 是用 对y进行预测时造成的损失，称为 损失函数。简单地 说，学习的目标就是求一映射函数 f(x , w) ，使之与实 际系统映射的差异最小。
14.1.2 经验风险最小化问题
学习机器产生的映射函数与实际系统的映射之间的差异可 以用单个样本点上的损失函数 L(y, f (x, w)) 来描述 。损失函数
14.3支持向量机的实现技术 14.3.1 chunking 算法 14.3.2 Decomposing 算法 14.3.3 SMO 算法 14.3.5 SMO 算法的特点和优势 14.4支持向量回归机 14.4.1不敏感损失函数 14.4.2支持向量回归机模型 14.5支持向量机的改进算法
2
数据挖掘原理与SPSS Clementine 应用宝典
在总体样本集上的数学期望，即为期望风险的泛函：
? min Remp (w)
?
1 n
n i?1
L(yi ,
f ( xi , w))
损失函数描述了映射函数与实际系统在总体集上的差异，将学习的目标变
成了最小化期望风险 R(w。) 在实际的问题中，R(w)无法直接的计算得到。
在传统的机器学习方法中，通常将经验风险作为期望风险
14.1.1机器学习的基本问题
?统计学习理论领域里把学习问题看作是利用有限数量的观测来
寻找待求的依赖关系的问题。而基于数据的机器学习问题，则 是根据已知样本估计数据之间的依赖关系，从而对未知或无法 测量的数据进行预测和判断。
?样本学习的一般模型
x y
G
S
LM
可见，学习问题就是从给定的函数集 ，选择出能够最好地逼近训练器响应的函数。
? 统计学习理论是针对小样本情况下的机器学习理论，它依据 算法的经验风险以及算法本身的构造推测它的实际风险，获 得了较好的算法泛化能力。统计学习理论将算法的训练过程 看作算法向训练样本学习的过程。
? 统计学习理论的4个部分：
1. 学习过程一致性的理论。一个基于经验风险最小化原则的学习过程满足什 么条件，它的经验风险与实际风险趋向一致。
?机器学习的目标可以形式化的表示为：根据 n个独立 同分布的观测样本 (x1,y1 ),???, (xn ,y，n )在一组函数 f(x , w 0 ) 中求出一个最优函数 f(x, w) ，使其对未知样本进行估 计时，最小化期望风险泛函。
R(w) ? ?L( y, f (x, w))dF (x, y)