当前课程知识点：大数据机器学习 > 第十四章 计算学习理论 > 3. 有限假设空间 > 3.有限假设空间
我们这里着重介绍
有限假设空间的情形
有限假设空间的可分情形
就意味着目标概念c
是属于假设空间H的
也就是c属于H
我们给定包含M个样例的训练集
那么
如何找出满足误差条件的那个真实的假设呢
容易想到一种最简单的学习策略
我们只需要在学习的时候
保留那些与数据集D一致的假设
然后呢去剔除那些与训练集D不一致的假设
这样我们不断的去处理
若训练集足够大的时候
我们就可以不断借助D中的样例
剔除不一致的假设
直到样本空间中
只剩下一个目标假设为止
这个假设呢就是目标概念C
通常情况下
由于训练集规模是有限的
所以达不到刚才我们所说的效果
而且假设空间当中
可能存在不只一个和训练集D一致的假设
对于这些等效的假设
我们没有办法根据现有的训练数据集
来对他们的优劣好坏做进一步的区分
因为他们都是由一个数据集学习得来的
那么问题就来了
那么到底需要多少的样例才能学得到
我们想要的目标概念C呢
我们先估计泛化误差大于ε
但在训练集上仍然表现完美的
假设出现的概率
就是说在训练集上表现完美
但是它的泛化误差
是大于我们的期望的误差的
假定H它的泛化误差大于ε
对于分布D上随机采样
而得到的任何样例
都有（见上图）
由于数据集D包含M个
从独立同分布采样而得到的样例
因此
H于D表现一致的概率为
（见上图）
我们事先并不知道
学习算法L会输出L中的哪个假设
那么
我们仅需要保证泛化误差大于ε
且在训练集上表现完美的所有假设
出现概率之和不大于δ就可以了
（见上图）
我们令该式不大于δ
（见上图）
由该不等式可以知道
有限假设空间H都是PAC可学习的
所需的样例的数目
是由该式子可以得到
对于有限空间不可分的情形
也就是目标概念C
往往不存在于假设空间H当中
这就比较麻烦
我们假定对于任何的
假设是属于假设空间的
经验误差不等于0
也就是说
H中的任意一个假设
都会在训练集上出现或多或少的错误
这样呢
我们就可以由刚才
Hoeffding 不等式去推导得到引理
如果训练集D包含M个从分布D上
独立同分布采样而得到的样例
ε大于零小于一
则对任意的h属于H
（见上图）
这个不等式对于我们判断泛化误差
和经验误差的差别是非常有帮助的
如果训练集D包含M个从分布D上
独立同分布采样而得到的样例
0 < ε < 1
则对任意的h属于假设空间H
该式以至少 1-δ的概率成立
这个推论就表明
样例数目M较大的时候
H的经验误差是其泛化误差很好的近似
那么 如果
假设空间H为有限的假设空间
也就是 0 < ε< 1的话
那么
对任意的假设H属于假设空间的话
有下式是成立的
好 学习了刚才的这些知识
我们下面要介绍是叫不可知学习
这个说法听起来怪怪的
但是如果大家理解了
也就不觉得奇怪了
显然
当目标概念C不属于H的时候
也就是不在假设空间H的里边
那么 学习算法L
是无法学得目标概念C的ε近似
但是呢
假如 当假设空间H给定的时候
在这个空间当中啊
必定会存在一个泛化误差最小的假设
这个假设呢虽然不是目标概念
但是
我们找出这个假设的ε近似
也不失为一个较好的方法和目标
再假设空间H中泛化误差最小的假设
是符合 argmin Eh
这样呢 以此为目标
就可以将PAC学习推广到
C不属于H的情形
这就称为不可知学习
下面介绍不可知PAC学习
刚才我们已经介绍了不可知学习
那么
把不可知PAC结合起来
我们令M表示从分布当中独立同分布采样
得到的样例的数目
εδ大于零小于一
对所有分布D
若存在学习算法L和多项式函数 poly
使得对于任何的M
（见上图）
L呢能从假设空间H中
输出满足下式的假设
（见上图）
则称假设空间H是不可知PAC可学习的
-1.机器学习定义和典型应用
-2.机器学习和人工智能的关系
-3.深度学习方法和其它人工智能方法的共性和差异
-4.机器学习和数据挖掘的关系
-5.机器学习和统计学习的关系
-6.机器学习的发展历程
-7.大数据机器学习的主要特点
-第一章 概述--7.大数据机器学习的主要特点
-1机器学习的基本术语
-2.监督学习
--2.监督学习
-3.假设空间
--3.假设空间
-4.学习方法三要素
-第二章 机器学习基本概念--4.学习方法三要素
-5.奥卡姆剃刀定理
-6.没有免费的午餐定理
-7.训练误差和测试误差
-8.过拟合与模型选择
-第二章 机器学习基本概念--8.过拟合与模型选择
-9.泛化能力
--9.泛化能力
-10.生成模型和判别模型
-1.留出法
--1.留出法
-2.交叉验证法
--2.交叉验证法
-3.自助法
--3.自助法
-4.性能度量
--4.性能度量
-5.PR曲线
--5.PR曲线
-6.ROC和AUC曲线
-第三章 模型性能评估--6.ROC和AUC曲线
-7.代价敏感错误率
-8.假设检验
--8.假设检验
-9.T检验
--9.T检验
-10.偏差和方差
--10.偏差和方差
-1.感知机模型
--1.感知机模型
-第四章 感知机--1.感知机模型
-2.感知机学习策略
-3.感知机学习算法
-第四章 感知机--3.感知机学习算法
-1.原型聚类描述
--1.原型聚类描述
-第五章 聚类--1.原型聚类描述
-2.性能度量
--2.性能度量
-第五章 聚类--2.性能度量
-3.1原型聚类 k均值算法
-3.2 原型聚类 学习向量算法
-3.3 原型聚类 密度聚类
-第五章 聚类--3.3 原型聚类 密度聚类
-3.4原型聚类 层次聚类
-1.综述
--1.综述
-2.概率图模型
--2.概率图模型
-第六章 贝叶斯分类器及图模型--2.概率图模型
-3.贝叶斯网络
--3.贝叶斯网络
-第六章 贝叶斯分类器及图模型--3.贝叶斯网络
-4.朴素贝叶斯分类器
-第六章 贝叶斯分类器及图模型--4.朴素贝叶斯分类器
-5.半朴素贝叶斯分类器
-第六章 贝叶斯分类器及图模型--5.半朴素贝叶斯分类器
-6.贝叶斯网络结构学习推断
-7.吉布斯采样
--7.吉布斯采样
-第六章 贝叶斯分类器及图模型--7.吉布斯采样
-开头
--开头
-1.决策树模型与学习基本概念
-2.信息量和熵
--2.信息量和熵
-第七章 决策树和随机森林--2.信息量和熵
-3.决策树的生成
--3.决策树的生成
-4.决策树的减枝
--4.决策树的减枝
-5.CART算法
--5.CART算法
-6.随机森林
--6.随机森林
-简介
--简介
-1.逻辑斯谛回归模型
-第八章 逻辑斯谛回归与最大熵模型--1.逻辑斯谛回归模型
-2.最大熵模型
--2.最大熵模型
-3.模型学习的最优化方法
-第八章 逻辑斯谛回归与最大熵模型--3.模型学习的最优化方法
-1.开头
--1.开头
-2.SVM简介
--2.SVM简介
-3.线性可分支持向量机
-第九章 SVM--3.线性可分支持向量机
-4. 凸优化问题的基本概念
-第九章 SVM--4. 凸优化问题的基本概念
-5.支持向量的确切定义
-6.线性支持向量机
-第九章 SVM--6.线性支持向量机
-svm相关拓展资料
-开头
--开头
-第十章 核方法与非线性SVM--开头
-1.泛函基础知识
--1.泛函基础知识
-第十章 核方法与非线性SVM--1.泛函基础知识
-2. 核函数和非线性支持向量机
-第十章 核方法与非线性SVM--2. 核函数和非线性支持向量机
-3. 序列最小最优化算法
-第十章 核方法与非线性SVM--3. 序列最小最优化算法
-开头
--开头
-1. k近邻学习
--1. k近邻学习
-第十一章 降维与度量学习--1. k近邻学习
-2. 降维嵌入
--2.降维嵌入
-第十一章 降维与度量学习--2. 降维嵌入
-3. 主成分分析
--3.主要成分分析
-第十一章 降维与度量学习--3. 主成分分析
-4. 核化线性降维
--4.核化线性降维
-5. 流型学习和度量学习
-1. 提升方法Adaboost算法
-第十二章 提升方法--1. 提升方法Adaboost算法
-2. Adaboost算法的训练误差分析
-3. Adaboost算法的解释
-4. Adaboost的实现
-第十二章 提升方法--4. Adaboost的实现
-adaboost拓展资料
-开头
--开头
-1. 问题提出
--1. 问题提出
-2. EM算法的引入
-3. EM算法的收敛性
-4. EM算法在高斯混合模型学习中的应用
-5. EM算法的推广
-第十三章 EM算法及混合高斯模型--3. EM算法的收敛性
-开头
--开头
-1. 计算学习理论的基础知识
-第十四章 计算学习理论--1. 计算学习理论的基础知识
-2. 概率近似正确学习理论
-3. 有限假设空间
--3.有限假设空间
-4. VC维
--4. VC维
-第十四章 计算学习理论--4. VC维
-5. 学习稳定性
--5. 学习稳定性
-开头
--开头
-1. 隐马尔科夫模型的基本概念
-第十五章 隐马尔可夫模型--1. 隐马尔科夫模型的基本概念
-2. 概率计算算法
-3. 学习算法
--3.学习算法
-第十五章 隐马尔可夫模型--3. 学习算法
-4预测算法
--4. 预测算法
-第十五章 隐马尔可夫模型--4预测算法
-开头
--开头
-1.概率无向图模型
-第十六章 条件随机场--1.概率无向图模型
-2.条件随机场的定义与形式
-第十六章 条件随机场--2.条件随机场的定义与形式
-3.条件随机场的计算问题
-4.条件随机场的学习算法
-5.条件随机场的预测算法
-第十六章 条件随机场--5.条件随机场的预测算法
-开头
--开头
-1.精确推断法：变量消去法和信念传播法
-第十七章 概率图模型的学习与推断--1.精确推断法：变量消去法和信念传播法
-2.近似推断法：MCMC和变分推断
-第十七章 概率图模型的学习与推断--2.近似推断法：MCMC和变分推断
-1.神经网络的发展历程
-2.神经网络的基本概念以及常见的神经网络(一）
-第十八章 神经网络和深度学习--2.神经网络的基本概念以及常见的神经网络(一）
-3.神经网络的基本概念以及常见的神经网络(二）
-4.玻尔兹曼机
--4.玻尔兹曼机
-5.深度学习
--5.深度学习
-第十八章 神经网络和深度学习--5.深度学习
-1. 深度学习简介和架构设计
-2. 计算图形式的反向传播算法
-3.深度学习的正则化方法（一）
-4.深度学习的正则化方法（二）
-1.深度学习的优化问题
-第二十章 深度学习优化方法--1.深度学习的优化问题
-2.神经网络优化的挑战
-3.神经网络的优化算法
-第二十章 深度学习优化方法--3.神经网络的优化算法
-4.相关策略
--4.相关策略
-第二十章 深度学习优化方法--4.相关策略
