💻
QMMMS的笔记
博客
  • QMMMS的笔记
  • agent
    • MCP的背景、原理和开发
    • Agent 历史与背景
    • Agentic Workflows
    • 环境检查与基础工具
    • Tool Call
    • 工具与运行时的值
    • temp
    • 处理 Tool Call error
    • trick
  • algorithm
    • 线性结构
    • 二叉树
    • 图
    • 查找
    • 排序
    • 动态规划
    • 优化方法
    • 数学
    • 迁移至Java
  • computer_composition
    • 系统总线
    • 存储器
    • 输入输出系统
    • 计算机的运算方法
    • 指令系统
    • 补充
  • computer_network
    • 引入
    • 应用层
    • 传输层
    • 网络层(数据平面)
    • 网络层(控制平面)
    • 链路层
    • 常见问答
    • 实验
  • database
    • SQL实战
    • 关系代数
    • 数据库设计
    • 规范化
    • 数据库基本概念
    • 查询原理
    • 数据库恢复技术
    • 并发控制
  • dev_tools
    • Git
    • Nginx
    • Spring
    • LangChain
    • PyTorch Cheat Sheet
    • MyBatis
    • MySQL Cheat Sheet
    • MySQL 补充
    • Redis
    • Docker
    • RocketMQ
    • Chrome
  • linux
    • Linux基础命令与使用
    • 文件与权限
    • 文件与目录操作
    • 权限属性高级
    • 命令与文件的查找
    • 文件压缩和打包
    • vim编辑器
    • shell变量
    • 命令补充
    • 数据流重定向
    • 管道命令
    • shell脚本
    • 用户管理
    • 用户间交流
    • 计划任务
    • 进程管理
    • 软件管理
    • 认识系统服务
    • 运维常用命令
    • 常用命令
  • llm
    • 大规模语言模型概述
    • 分布式训练概述
    • 有监督微调概述
    • 强化学习与LLM
    • LLM评估概述
    • 大模型应用
    • 理解大模型
    • 量化
    • 预训练
    • 上下文学习
  • machine_learning
    • 引入
    • 大致正确学习
    • 一致收敛
    • 偏差还是过拟合?
    • 可学习的充要条件
    • 非均匀可学习性
    • 计算复杂性
  • mathematics
    • 概率与统计基础
    • 线性代数基础
  • operating_system
    • 操作系统基本概念
    • 进程和线程
    • 同步,互斥与死锁
    • 内存管理
    • 文件系统
    • I/O系统
    • 保护与安全
    • 《现代操作系统》
  • statistical_learning
    • 统计学习引入
    • 线性回归
    • 分类
    • 重抽样方法
    • 线性模型选择与正则化
    • 非线性模型
    • 基于树的方法
    • 支持向量机
    • 无指导学习
    • 马尔科夫链和蒙托卡罗方法简明理解
    • R语言速查
  • deep_learning
    • basic_concepts
      • 逻辑回归与损失函数
      • 神经网络
      • 正则化、预处理、权重初始化
      • 优化算法
      • 机器学习策略
      • 复习:从计算机视觉的角度
      • 卷积神经网络
      • 深度卷积网络示例
      • 计算机视觉任务
      • 循环神经网络
      • 自然语言处理任务
      • 注意力
      • Transformers 家族
      • 显卡扫盲
      • 强化学习概述
    • semi-supervise
      • 半监督学习简介
      • Consistency Regularization
      • Proxy-label Methods
      • Holistic Methods
      • Generative Models
      • Graph-Based SSL
      • Self-Supervision for SSL
      • Other SSL methods
  • programming
    • cpp
      • STL
      • C++基础
      • 内存管理
      • 面向对象
    • java
      • 环境和介绍
      • 注释
      • String
      • 面向对象思想
      • Object
      • 包
      • 访问权限修饰符
      • 初始化块
      • 接口
      • 内部类
      • 注解
      • 枚举
      • 集合框架
      • List
      • Map
      • 泛型
      • 迭代
      • IO与流
      • 序列化
      • 异常
      • Lambda
      • Stream流
      • Socket
      • 缓冲
      • 命名规范
      • 拆箱装箱
      • 值传递
      • 深拷贝
      • 反射
      • JVM
      • 并发编程基础
    • python
      • 并发编程
      • 环境管理
  • software_engineering
    • basic_concepts
      • 系统分析与设计概述
      • 规划
      • 需求分析与原型设计
      • 项目管理
      • 建模
      • 数据库设计
      • 架构
      • 配置管理
      • 测试管理
      • 安全
      • 编码原则
      • 微服务
      • 补充内容
    • software_testing
      • CMMI基础
      • PPQA与SQA
      • 软件测试基础
      • 黑盒测试
      • 白盒测试
      • 集成测试
      • 系统测试
      • 测开面试补充
由 GitBook 提供支持
在本页
  • 可学习与有限性
  • 分割
  • VC 维度
  • PAC 学习的基本定理
在GitHub上编辑
  1. machine_learning

可学习的充要条件

可学习与有限性

复习一下,之前我们学过:

  • 只要损失函数是有界的,那么具有一般损失函数的不可知PAC模型中的任何有限类都是可学习的。

  • 假设类的样本复杂度上界由其大小的对数给出。

有限是可学习的充分条件,但是它是必要条件吗?换句话说,有界类是可学习的,那么无界类呢?事实上,不是必要条件,我们首先给出一个无限大小假设类的简单例子,该类是可学习的。

设 H\mathcal{H}H 为实数上的阈值函数类,即 H={ha:a∈R}\mathcal{H} = \{ h_a:a \in \mathbb{R}\}H={ha​:a∈R} ,其中 ha:R→{0,1}h_a : \mathbb{R} \to \{0, 1\}ha​:R→{0,1} 是一个函数,使得 ha(x)=1[x<a]h_a(x) = \mathbb{1}_{[x < a]}ha​(x)=1[x<a]​ 。显然,H \mathcal{H}H 是无限的。但是经过证明(证明略),可以得到结论:使用 ERM 规则,这个 H\mathcal{H}H 是 PAC 可学习的,其样本复杂度 mH(ϵ,δ)≤⌈log⁡(2/δ)/ϵ⌉m_{\mathcal{H}}(\epsilon, \delta) \leq \left\lceil \log(2/\delta)/\epsilon\right\rceilmH​(ϵ,δ)≤⌈log(2/δ)/ϵ⌉

分割

事实上,一种称为假设类的 VC 维度的性质,是充要条件。为了引出 VC 维度,我们先看两个概念。

定义 6.2(H \mathcal{H}H 在 CCC 上的限制) 设 H\mathcal{H}H 为从 X\mathcal{X}X 到 {0,1} 的函数类,设 C={c1,...cm}⊂XC=\{c_1, ... c_m\} \subset \mathcal{X}C={c1​,...cm​}⊂X。H \mathcal{H}H 在 CCC 上的限制 HC\mathcal{H}_CHC​ 是可以从 H\mathcal{H}H 派生的从 CCC 到 {0,1} 的函数集。即:

HC={(h(c1),…,h(cm)):h∈H}\mathcal{H}_C = \{(h(c_1), \ldots, h(c_m)) : h \in \mathcal{H}\}HC​={(h(c1​),…,h(cm​)):h∈H}

其中我们将每个从 CCC 到 {0,1} 的函数表示为 {0,1}∣C∣\{0,1\}^{|C|}{0,1}∣C∣ 中的一个向量

定义 6.3(分割): 如果H \mathcal{H}H 在 CCC 上的限制是从 CCC 到 {0,1} 的所有函数集,那么我们说 H\mathcal{H}H 分割集合 CCC。即 HC=2∣C∣\mathcal{H}_C = 2^{|C|}HC​=2∣C∣

例子:令 H\mathcal{H}H 为实数上的阈值函数(类似阶梯函数,但只有一个阶梯)类。取集合 C={c1}C=\{c_1\}C={c1​}。如果 a=c1+1a=c_1+1a=c1​+1 有 ha(c1)=1h_a(c_1)=1ha​(c1​)=1, a=c1−1a=c_1-1a=c1​−1 有 ha(c1)=0h_a(c_1)=0ha​(c1​)=0,那么,HC\mathcal{H}_CHC​ 是从 CCC 到 {0,1} 的所有函数集 {(0), (1)}, H\mathcal{H}H 分割集合 CCC

那么取集合 C={c1,c2}C=\{c_1, c_2\}C={c1​,c2​} (其中c1<c2c_1< c_2c1​<c2​)呢?所有可能标记组合为 (0,0),(0,1),(1,0),(1,1),但是如果 h(c1)=0h(c_1)=0h(c1​)=0,那么由于阈值函数性质,h(c2)=0h(c_2)=0h(c2​)=0 也必须是 0,因此,H \mathcal{H}H 不能实现所有组合。因此,集合 CCC 不被 H\mathcal{H}H 分割

回顾无免费午餐定理,当某些集合 CCC 被 H\mathcal{H}H 分割时,对手(指找到一个 H\mathcal{H}H 失败但有其他算法成功的方法)不受 H\mathcal{H}H 的限制,因为可以基于从 CCC 到 {0,1} 的任何目标函数构造一个分布,同时保持可实现性假设:

推论 6.4 : 设 H\mathcal{H}H 为从 X\mathcal{X}X 到 {0,1} 的函数类,令 mmm 为训练集大小。假设存在大小为 2m2m2m 的集合 C⊂XC \subset \mathcal{X}C⊂X,被 H\mathcal{H}H 分割。那么,对于任何学习算法 AAA ,存在一个X \mathcal{X}X 到 {0,1} 的分布 D\mathcal{D}D ,和一个预测函数 h∈Hh\in\mathcal{H}h∈H,使得 LD(h)=0L_{\mathcal{D}}(h)=0LD​(h)=0,但至少有1/7的概率S∼DmS\sim\mathcal{D}^mS∼Dm,使得 LD(A(S))≥1/8L_\mathcal{D}(A(S)) \geq 1/8LD​(A(S))≥1/8

推论 6.4 告诉我们,如果 H\mathcal{H}H 分割了大小为 2m2m2m 的集合 CCC,那么我们无法通过 mmm 个样本学习 H\mathcal{H}H (这和无免费午餐定理很像),因为这些实例的标签不会提供有关 CCC 其余实例标签的信息,而由于 H\mathcal{H}H 包含的可能太大(以致于能分割 CCC),无论剩下一半的标签是咋样的,都可以由 H\mathcal{H}H 中的某个假设解释

类似我想搜选择题的答案,搜题软件告诉我说:A、B、C、D 四个选项的可能性都是 25%

VC 维度

定义 6.5(VC 维度): 假设类 H\mathcal{H}H 的 VC 维度,记作 VCdim(H)\text{VCdim}(\mathcal{H})VCdim(H),是可以被 H\mathcal{H}H 分割的集合 C⊂XC \subset \mathcal{X}C⊂X 的最大大小。如果 H\mathcal{H}H 可以分割任意大的集合,我们称 H\mathcal{H}H 具有无限 VC 维度。

因此,推论 6.4 的直接结果是:

定理 6.6 :设 H\mathcal{H}H 是一个具有无限 VC 维度的类。那么,H\mathcal{H}H 不是 PAC 可学习的。

6.6 的证明 由于 H\mathcal{H}H 具有无限 VC 维度,对于任何训练集大小 mmm,存在一个大小为2m2m2m 的被分割集合,因此根据推论 6.4,得出该结论。

事实上,在本章后面将看到,定理6.6的反面也成立,即有限 VC 维度保证可学习性,

要证明 VCdim(H)=d\text{VCdim}(\mathcal{H})=dVCdim(H)=d,我们需要证明:

  1. 存在一个大小为 d 的集合 C,被 H\mathcal{H}H 分割

  2. 每个大小为 d+1 的集合 C 都不被 H\mathcal{H}H 分割

例如上面提到的,阈值函数类,存在大小为1的集合 C,被 H\mathcal{H}H 分割,每个大小为 2 的集合 C 都不被 H\mathcal{H}H 分割,那么它的 VCdim(H)=1\text{VCdim}(\mathcal{H})=1VCdim(H)=1

再来一个例子,设 H\mathcal{H}H 为实数上的区间类,即 H={ha,b:a,b∈R,a<b}\mathcal{H}=\{h_{a,b}:a,b\in \mathbb{R},a<b\}H={ha,b​:a,b∈R,a<b},其中 ha,b(x)=1x∈(a,b)h_{a,b}(x) = \mathbb{1}_{x \in (a,b)}ha,b​(x)=1x∈(a,b)​

  • 取集合 C={c1,c2},c1=1,c2=2C=\{c_1, c_2\},c_1=1,c_2=2C={c1​,c2​},c1​=1,c2​=2。那么,H \mathcal{H}H 分割集合 CCC,因为能取到 (0,0),(0,1),(1,0),(1,1),因此 VCdim(H)≥2\text{VCdim}(\mathcal{H})\geq 2VCdim(H)≥2

  • 现在取任意集合 C={c1,c2,c3}C=\{c_1, c_2, c_3\}C={c1​,c2​,c3​} 并假设 c1<c2<c3c_1< c_2<c_3c1​<c2​<c3​。那么,(1,0,1) 不能通过区间获得,因此 H\mathcal{H}H 不分割集合 CCC ,VCdim(H)<3\text{VCdim}(\mathcal{H}) < 3VCdim(H)<3

因此我们得出结论 VCdim(H)=2\text{VCdim}(\mathcal{H})=2VCdim(H)=2

再来一个例子,H={hθ:θ∈R}\mathcal{H} = \{h_\theta : \theta \in \mathbb{R}\}H={hθ​:θ∈R}, hθ(x)=⌈0.5sin⁡(θx)⌉h_\theta(x) = \lceil 0.5 \sin(\theta x)\rceil hθ​(x)=⌈0.5sin(θx)⌉,可以证明 VCdim(H)=∞\text{VCdim}(\mathcal{H})= \inftyVCdim(H)=∞

设 H\mathcal{H}H 为有限类。那么显然,对于任意集合 C,我们有 ∣HC∣≤∣H∣|\mathcal{H}_C| \leq |\mathcal{H}|∣HC​∣≤∣H∣,因此,如果 ∣H∣<2∣C∣|\mathcal{H}| < 2^{|C|}∣H∣<2∣C∣,C 不能被分割,这意味着VCdim(H)≤log⁡2(∣H∣)\text{VCdim}(\mathcal{H}) \leq \log_2(|\mathcal{H}|)VCdim(H)≤log2​(∣H∣)

对于阈值函数类,如果 X={1,2,...k}\mathcal{X}=\{1,2,...k\}X={1,2,...k} ,那么 log⁡2(∣H∣)=log⁡2(k)\log_2(|\mathcal{H}|) = \log_2(k)log2​(∣H∣)=log2​(k),而 VCdim(H)=1\text{VCdim}(\mathcal{H})=1VCdim(H)=1

PAC 学习的基本定理

定理 6.7(统计学习的基本定理)(证明略):设 H\mathcal{H}H 为从 X\mathcal{X}X 到 {0,1} 的函数的假设类,并让损失函数为 0-1 损失。那么,以下条件是等价的:

  1. H\mathcal{H}H 具有一致收敛性

  2. 任何 ERM 规则都是 H\mathcal{H}H 的成功不可知 PAC 学习器

  3. H\mathcal{H}H 是不可知 PAC 可学习的

  4. H\mathcal{H}H 是 PAC 可学习的

  5. 任何 ERM 规则都是 H\mathcal{H}H 的成功 PAC 学习器

  6. H\mathcal{H}H 具有有限 VC 维度

我们为二元分类任务陈述了基本定理。类似的结果适用于其他学习问题,例如绝对损失或平方损失的回归。然而,该定理并不适用于所有学习任务:

  • 即使一致收敛性属性不成立,学习有时也是可能的

  • 即使ERM 规则失败,但其他学习规则可以实现可学习性

上一页偏差还是过拟合?下一页非均匀可学习性

最后更新于6个月前