跳到正文

CSCI4230

计算学习论

PAC 学习与 VC 理论、样本压缩、在线学习、提升法与统计查询、主动学习、含噪声的学习、密码学困难性及保形预测。

12 章 · 25 节EN · 繁 · 简
我的课程笔记

你的进度

0/ 25 节已标记完成

下一节: PAC 学习、有限假设类与 VC 维数

完成记录保存在此浏览器中。

这门课在网上

CSCI4230 笔记里的内容

定理卡
50
定义
34
反例
26
概念视角
8
思想史
2
证明透视
27

有思想史的节

这些思想史还没有放上时间线。

这门课的概念视角还没有记录到网上。

在知识图谱中打开这门课

数字只算这门课 25 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。

在网上定理卡 50 · 定义 34 · 反例 26 · 概念视角 8 · 思想史 2 · 证明透视 27

这些思想史还没有放上时间线。

这门课的概念视角还没有记录到网上。

在知识图谱中打开这门课

数字只算这门课 25 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。

第 1 章 · 5 节

PAC 学习

PAC 学习

定理 10 · 定义 6反例 5视角 2证明透视 6

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 1.1

    PAC 学习、有限假设类与 VC 维数

    用一致学习、奥卡姆(Occam)界与打散区分统计保证和计算效率。

  2. 1.2

    单调合取式的 PAC 学习

    构造删除式学习器并证明其分布无关的可实现情形 PAC 保证。

  3. 1.3

    从正样本学习坐标轴平行盒子

    构造一致学习器并证明适用于含原子分布的分布无关 PAC 保证。

  4. 1.4

    学习带符号文字的决策列表

    构造一致的决策列表学习器,并证明有限类 PAC 保证。

  5. 1.5

    固定宽度 DNF 的 PAC 学习

    以一致的删除算法学习固定宽度布尔(Boolean)析取合取式,并区分样本保证和运行时间保证。

第 2 章 · 5 节

VC 理论

VC 理论

定理 10 · 定义 5反例 5视角 1证明透视 5

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 2.1

    增长函数、VC 维数与一致收敛

    证明 Sauer–Shelah 计数界,并用对称化同时控制经验误差与总体误差。

  2. 2.2

    半空间与坐标轴平行盒子的 VC 维

    利用仿射相关和坐标极值证明几何打散界。

  3. 2.3

    未见样本点与 PAC 学习下界

    利用打散集合上的随机标签与稀有事件证明样本下界。

  4. 2.4

    由含噪标签得到的不可知学习下界

    通过把学习归约为二元检验,证明维数除以精度平方的样本下界。

  5. 2.5

    Rademacher 复杂度与一致泛化

    利用随机符号、对称化和有界差控制函数类。

第 3 章 · 1 节

模型选择

模型选择

定理 1 · 定义 1反例 1视角 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 3.1

    使用类权重的结构风险最小化

    为可数多个有限类建立同时成立的界,并证明依赖数据的模型选择的预言机不等式。

第 4 章 · 1 节

样本压缩

样本压缩

定理 2 · 定义 1反例 1视角 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 4.1

    样本压缩与泛化

    证明一致压缩界,计入指标和附加信息的代价,并构造阈值学习器。

第 5 章 · 4 节

在线学习

在线学习

定理 6 · 定义 6反例 4证明透视 5

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 5.1

    在线错误界与加权多数法

    证明可实现情形的折半保证与加权多数保证,再将逐次错误连接到期望总体误差。

  2. 5.2

    感知机更新与间隔错误界

    由几何可分性证明有限的错误次数界,并将其与统计风险保证区分开来。

  3. 5.3

    指数权重与相对专家的遗憾

    对有界损失的随机化全信息预测,推导加性遗憾上界。

  4. 5.4

    从在线学习到批量学习的高概率转换

    把序贯错误界转化为已保存预测器随机混合的风险保证。

第 6 章 · 2 节

提升法与统计查询

提升法与统计查询

定理 5 · 定义 3反例 3思想史 1证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 6.1

    提升法与统计查询

    分析加权投票的训练误差界,以及统计查询可从随机样本获得的信息精度。

  2. 6.2

    通过重加权将弱学习转化为强学习

    证明总体层面的 boosting 保证,并从新鲜样本模拟自适应的重加权分布。

第 7 章 · 2 节

统计查询

统计查询

定理 5 · 定义 4反例 2视角 2证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 7.1

    统计查询为何难以学习奇偶函数

    用正交性证明有限统计查询下界,并与使用单个有标签样本的学习方法比较。

  2. 7.2

    分类噪声下的统计查询

    从独立翻转的标签模拟自适应干净统计查询,并量化噪声代价。

第 8 章 · 1 节

主动学习

主动学习

定理 3 · 定义 2反例 1视角 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 8.1

    主动学习:查询与标签复杂度

    分析阈值的自适应标签请求,与被动样本比较,并辨明比较何时失效。

第 9 章 · 1 节

含噪声的学习

含噪声的学习

定理 2 · 定义 1反例 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 9.1

    带随机分类噪声的学习

    推导独立标签翻转的影响,证明有限类学习保证,并辨明噪声模型的作用。

第 10 章 · 1 节

密码学困难性

密码学困难性

定理 2 · 定义 2反例 1思想史 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 10.1

    伪随机函数与高效 PAC 学习的限制

    将假想的 PAC 学习器归约为预言机区分器,并处理有限定义域上的重复输入。

第 11 章 · 1 节

保形预测

有限样本预测集合及边际覆盖。

定理 2 · 定义 2反例 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 11.1

    分割保形预测与边际覆盖率

    证明有限样本秩保证,并区分边际和群组覆盖。

第 12 章 · 1 节

AdaBoost 提升法

在固定样本上推导自适应投票及训练误差界。

定理 2 · 定义 1反例 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 12.1

    AdaBoost:自适应权重、间隔与训练误差界

    推导自适应投票与归一化,证明有条件的有限训练误差界,并计算具体轮次。

Vercel 访问统计与公开页面性能测量分别征求同意,均非使用网站的必要条件。

网站功能存储(按需使用)

安全、登录和你选择的偏好会按需使用存储,与可选统计分开处理。

撤回会停止后续统计;需要卸载已加载的统计程序时,页面会刷新。已发送的数据不会因此删除。

查看 Cookie 与存储详情