你的进度
0/ 25 节已标记完成
下一节: PAC 学习、有限假设类与 VC 维数
完成记录保存在此浏览器中。
这门课在网上
CSCI4230 笔记里的内容
- 定理卡
- 50
- 定义
- 34
- 反例
- 26
- 概念视角
- 8
- 思想史
- 2
- 证明透视
- 27
数字只算这门课 25 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。
在网上定理卡 50 · 定义 34 · 反例 26 · 概念视角 8 · 思想史 2 · 证明透视 27
第 1 章 · 5 节
PAC 学习
PAC 学习
- 1.1
PAC 学习、有限假设类与 VC 维数
用一致学习、奥卡姆(Occam)界与打散区分统计保证和计算效率。
- 1.2
单调合取式的 PAC 学习
构造删除式学习器并证明其分布无关的可实现情形 PAC 保证。
- 1.3
从正样本学习坐标轴平行盒子
构造一致学习器并证明适用于含原子分布的分布无关 PAC 保证。
- 1.4
学习带符号文字的决策列表
构造一致的决策列表学习器,并证明有限类 PAC 保证。
- 1.5
固定宽度 DNF 的 PAC 学习
以一致的删除算法学习固定宽度布尔(Boolean)析取合取式,并区分样本保证和运行时间保证。
第 2 章 · 5 节
VC 理论
VC 理论
- 2.1
增长函数、VC 维数与一致收敛
证明 Sauer–Shelah 计数界,并用对称化同时控制经验误差与总体误差。
- 2.2
半空间与坐标轴平行盒子的 VC 维
利用仿射相关和坐标极值证明几何打散界。
- 2.3
未见样本点与 PAC 学习下界
利用打散集合上的随机标签与稀有事件证明样本下界。
- 2.4
由含噪标签得到的不可知学习下界
通过把学习归约为二元检验,证明维数除以精度平方的样本下界。
- 2.5
Rademacher 复杂度与一致泛化
利用随机符号、对称化和有界差控制函数类。
第 3 章 · 1 节
模型选择
模型选择
- 3.1
使用类权重的结构风险最小化
为可数多个有限类建立同时成立的界,并证明依赖数据的模型选择的预言机不等式。
第 4 章 · 1 节
样本压缩
样本压缩
- 4.1
样本压缩与泛化
证明一致压缩界,计入指标和附加信息的代价,并构造阈值学习器。
第 5 章 · 4 节
在线学习
在线学习
- 5.1
在线错误界与加权多数法
证明可实现情形的折半保证与加权多数保证,再将逐次错误连接到期望总体误差。
- 5.2
感知机更新与间隔错误界
由几何可分性证明有限的错误次数界,并将其与统计风险保证区分开来。
- 5.3
指数权重与相对专家的遗憾
对有界损失的随机化全信息预测,推导加性遗憾上界。
- 5.4
从在线学习到批量学习的高概率转换
把序贯错误界转化为已保存预测器随机混合的风险保证。
第 6 章 · 2 节
提升法与统计查询
提升法与统计查询
- 6.1
提升法与统计查询
分析加权投票的训练误差界,以及统计查询可从随机样本获得的信息精度。
- 6.2
通过重加权将弱学习转化为强学习
证明总体层面的 boosting 保证,并从新鲜样本模拟自适应的重加权分布。
第 7 章 · 2 节
统计查询
统计查询
- 7.1
统计查询为何难以学习奇偶函数
用正交性证明有限统计查询下界,并与使用单个有标签样本的学习方法比较。
- 7.2
分类噪声下的统计查询
从独立翻转的标签模拟自适应干净统计查询,并量化噪声代价。
第 8 章 · 1 节
主动学习
主动学习
- 8.1
主动学习:查询与标签复杂度
分析阈值的自适应标签请求,与被动样本比较,并辨明比较何时失效。
第 9 章 · 1 节
含噪声的学习
含噪声的学习
- 9.1
带随机分类噪声的学习
推导独立标签翻转的影响,证明有限类学习保证,并辨明噪声模型的作用。
第 10 章 · 1 节
密码学困难性
密码学困难性
- 10.1
伪随机函数与高效 PAC 学习的限制
将假想的 PAC 学习器归约为预言机区分器,并处理有限定义域上的重复输入。
第 11 章 · 1 节
保形预测
有限样本预测集合及边际覆盖。
- 11.1
分割保形预测与边际覆盖率
证明有限样本秩保证,并区分边际和群组覆盖。
第 12 章 · 1 节
AdaBoost 提升法
在固定样本上推导自适应投票及训练误差界。
- 12.1
AdaBoost:自适应权重、间隔与训练误差界
推导自适应投票与归一化,证明有条件的有限训练误差界,并计算具体轮次。