人工智能导论
AGuidetoArtificsialIntelligense.
通
L
版本：3.0
2020年10月
學
XTTnCM1TMLZGLNCE
第六章机器学习
6.1概述
6.2决策树学习
6.3贝叶斯学习
6.4统计学习
与
6.5聚类
6.6特征选择与表示学习
6.7其他学习方法
6.4统计学习
西安文通大學
XIANJIAOTONGUNIVERSITY
G.4.1统计学习理论
☆传统的统计学理论，即Fisher理论体系的前提条件
◆已知准确的样本分布函数
◆并且采样无穷多为
☆V.Vapnik提出小样本(有限样本)统计学习理论
◆小样本统计学习理论基于对学习错误(过学习，overfitting)和泛化能力之间关系的定量刻画，
◆不仅避免了对样本点分布的假设和数目要求
◆还产生了一种新的统计推断原理结构风险最小化原理。
☆函数估计模型
(1)G表示产生器，用于产生输入向量x;
的输出y,并且输入和输出遵从某个未知联合概率F(x,y);
决定了不同的学习函数。
★学习的问题就是从给定的函数集f(x,a),a∈A中选择出能最好地逼近训练器响应的函数。
期望风险
☆损失的数学期望值就称为风险泛函(riskfunctional),也称为期望风险。
☆学习的目标就是最小化风险泛函R(a),即风险最小化问题。
★L1损失函数，即绝对值损失函数
L(y,f(x,a)二x-fCx
★L2损失函数，即平方损失函数
L(y,f(x,a))FY十(X
★0-1损失函数
常见损失函数
常见损失函数
★对数损失函数，即对数似然损失函数，也常称之为交
叉熵损失函数
L(p(x,a))=-logp(x,a)
二分类时，即Dy∈{0.1}时
L(y,f(x,a)=-ylogp(x,a)1“log
★指数损失函数
★Hinge损失函数SVN的损失函数(1
经验风险
☆实际问题中，联合概率F(x,y)是未知的，所以就无法用风险泛函直接计算损失的期望值，也无法最小化。于是实践中常用算术平均代替数学期望，从而得到经验风险泛函
☆当N→∞时，经验风险Remp(a)才在概率意义下趋近于期望风险R(a)。传统的学习方法大多都是使经验风险最小化(EmpinicalriskminimizationERM)。
小样本统计学习理论
☆即使样本数目很大，也不能保证经验风险的最小值与期望风险的最小值相近。
☆所以统计学习理论就要研究在样本数目有限的情况下，经验风险与期望风险之间的关系。其核心内容包括一下4点：
◆在什么条件下，当样本数目趋于无穷时，经验风险Remp(a)最优5值趋于期望风险R(a)最优值(能够推广),其收敛速度又如何。
也就是在经验风险最小化原则下的学习一致性条件。
◆如何从经验风险估计出期望风险的上界，即关于统计学习方法推广性的界。
◆在对期望风险界估计的基础上选择预测函数的原则，即小样本归纳推理原则。
◆实现上述原则的具体方法。例如支持向量机(Supportvectormachine,SVM)就是一个具体的方法。
10
VC维
☆VC维的直观定义：
◆对一个指示函数集，如果存在h个样本能够被函数集中
本数目h。
☆所谓打散就是不管全部样本如何分布，总能在函数集中找到一个函数把所有样本正确地分为两类。
◆若对任意数目的样本都有函数能将窗们打散，则函数集的VC维是无穷大。
◆有界实函数的VC维可以通过用一定的阈值将它转化成指示函数来定义。
实数平面的VC维
☆实际上n维超平面的VC维是n+1。
Z1
0
☆定理6.2对于Rn中的m个点集，选择任何一个点作为原点，m个点能被超平面打散当且仅当剩余点的位置向量是线性独立的。
☆推论Rn中有向超平面集的VC维是n+1。
◆因为总能找出n+1个点，选择其中一个作为原点，剩余n个点的位置向量是线性独立的。但无法选择n+2个这样的点，因为在Rn中没有n+2个向量是线性独立的。
☆VC维反映了函数集的学习能力
◆VC维越大则学习机器越复杂，容量越大。
☆线性函数的VC维等于其自由参数的个数。
◆但是一般来说，函数集的VC维与其自由参数的个数不相同。
☆影响学习机器推广性能的是函数集的VC维一而不是其自由参数个数。
推广性。
结构风险
☆对于两类分类问题：
◆指示函数集中的所有函数(包括使经验风险最小的函数),经验风险Remp(a)和期望风险R(a)之间以至少1-η的概率满足如下关系：
R(a)≤R(a)+h(Ine2N