第12章 统计学习理论
主讲人：李君宝
哈尔滨工业大学
1. 统计学习理论
2. 支持向量机 3. 核方法
1.统计学习理论
【机器学习问题的基本表示】
用三个部分来描述机器学习的一般模型： (1) 产生器(Generator)，产生随机向量x，它们是从固定但未知的概率 分布函数F(x) 中独立抽取的。 (2) 训练器(Supervisor)，对每个输入向量x返回一个输出值y，产生输 出的根据是同样固定但未知的条件分布函数F(y|x)。 (3) 学习机器(Learning Machine)，能够实现一定的函数集.
5
【统计学习方法概述】
近百年来，统计学得到极大的发展。我们可用下面的框 架粗略地刻划统计学发展的过程： 1900-1920 数据描述 1920-1940 统计模型的曙光 1940-1960 数理统计时代 – 随机模型假设的挑战 – 松弛结构模型假设 1990-1999 建模复杂的数据结构
• • •
8
【风险】
• 学习机LM输出
ˆ 与输入x之间可以看作是一个函数关系： y
ˆ f x y
• 一般要将函数 f x 限定在特定一组函数 f x, w 中求取。 • 定义风险： L y, f x, w • 均方误差： L y, f x, w y f x, w • 似然函数： L p x, w ln p x, w
1 Remp w L yi , f xi , w n i 1
• 求取最优参数w*，使得经验风险Remp(w*)最小。 • 当学习过程具有一致性时，统计学有如下关系：
n
lim P sup Remp w R w 0, 0
n w
【统计学习理论的核心思想】
• 学习的目标在于推广:
期望风险最小 <-->推广能力最大
• 有限样本条件下，学习机器的推广性取决于两个因素：
–经验风险（学习误差） –函数集的复杂性（容量）
【VC维】
• 打散：如果存在一个有h个样本的样本集能够被一个函数集 中的函数按照所有可能的2h种形式分为两类，则称函数集 能够将样本数为h的样本集打散；


【期望风险与经验风险的关系】
期望风险R(w*) R(w*) 经验风险Remp(w*)
Remp w R w
n
【函数集的VC维与推广性的界】
• 统计学习的推广能力不仅同训练样本数n有关系， 而且同学习机的函数集选择有关系，“简单”函 数集合推广能力强，“复杂”函数集合推广能力 差。
• • 统计学习理论 • –系统地研究有限样本下机器学习的原理与方法的理论 • – 始于1960s：
【统计学习的基本内容】
• ERM学习过程一致的充分必要条件是什么？ – 当样本无穷多时，经验风险最小的解是否收敛与期望风险最 小的解，条件是什么 • 学习过程收敛的速度有多快？ – 随着样本数目的增加，这种收敛的速度有多快 • 如何控制学习过程的收敛速度（推广能力）？ – 新的学习原理：如何设计学习机器才能得到更快的收敛速 度，即有限样本下更好的推广能力 • 怎样构造能够控制推广能力的算法？ –新的学习算法：在理论和原则下的实用学习方法：
• 传统方法: 统计学在解决机器学习问题中起着基础 性的作用。传统的统计学所研究的主要是渐近理论 ，即当样本趋向于无穷多时的统计性质。统计方法 主要考虑测试预想的假设和数据模型拟合。它依赖 于显式的基本概率模型。 模糊集
粗糙集
•
•
•
支持向量机
7
【统计学习方法概述】
系统S为研究对象，通过一系列的观 测样本来求得学习机LM，使得LM 的输出 能够尽量准确的预测S的输
输入 x 系统（S）
输出 y
学习机（LM）
ˆ 预测输出 y
出y。(x1,y1)，(x2,y2)，…，(xn,yn)
【统计学习方法概述】
统计方法是从事物的外在数量上的表现去推断该事物 可能的规律性。科学规律性的东西一般总是隐藏得比较深 ，最初总是通过其数量表现并由统计分析看出一些线索， 然后提出一定的假说或学说，作进一步深入的理论研究。 当理论研究 提出一定的结论时，往往还需要在实践中加以 验证。就是说，观测一些自然现象或专门安排的实验所得 资料，是否与理论相符、在多大的程度上相符、偏离可能 是朝哪个方向等问题，都需要用统计分析的方法处理。
2
【期望风险】
• y与x之间存在一定的依赖关系，可以用一个未 知的联合概率F(x,y)描述。 • 期望风险定义为：
R w L y, f x, w dF x, y
• 统计学习的目的就是要寻找到一个最优的函数 f(x,w*)，使得R(w*)最小。
【经验风险】
• 期望风险一般来说无法计算，在工程上转而计算 经验风险：
统计方法处理过程可以分为三个阶段： • （1）搜集数据：采样、实验设计
•
•
（2）分析数据：建模、知识发现、可视化
（3）进行推理：预测、分类
常见的统计方法有:
回归分析（多元回归、自回归等） 判别分析（贝叶斯判别、费歇尔判别、非参数判别等） 聚类分析（系统聚类、动态聚类等） 探索性分析（主元分析法、相关分析法等）等。
VC维：如果函数集能够打散h个样本的样本集，而不能打散 h+1个样本的样本集，则称函数集的VC维为h。 1. d维空间中线性函数的VC维：h = d+1； 2. 正弦函数集合{sin(wx)}的VC维：h = ∞。
【推广性的界】
• 函数集合的VC维描述了函数的复杂程度，利用VC 维可以确定推广性的界，下列不等式右半部分至少 以概率1-h成立：
• 当函数集过于“复杂”时，很容易产生“过学习 ”现象：对于训练样本风险很小，而对非训练样 本风险却很大。
【过学习】
经验风险最小化≠ 期望风险最小化（错误率最小化） 学习机器的复杂性不但与问题背后的模型有关，还要与有限的 学习样本相适应.
【统计学习的起源】
• 基于传统统计学的机器学习/模式识别方法的局限 • –传统统计学研究的主要是渐进特性 • –传统模式识别方法多直接或间接假设样本充分多