💻
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 提供支持
在本页
  • 样本复杂度
  • 去除可实现性假设
  • 其他形式的任务
  • 一般损失的不可知 PAC 可学习性
在GitHub上编辑
  1. machine_learning

大致正确学习

在前一章中,我们已经证明,对于一个有限的假设类,如果将 ERM 规则应用于足够大的训练样本(其大小独立于基础分布或标记函数),那么输出假设可能会是大致正确的。

更一般地,我们现在定义可能大致正确(PAC, Probably Approximately Correct)学习,一个假设类 H\mathcal{H}H 是 PAC 可学习的,那么:

  • 如果存在一个函数 mH:(0,1)2→Nm_{\mathcal{H}} : (0,1)^2 \to \mathbb{N}mH​:(0,1)2→N

  • 并存在一个具有以下性质的学习算法:对于每个 ϵ,δ∈(0,1)\epsilon, \delta \in (0,1)ϵ,δ∈(0,1) 和每个在 X\mathcal{X} X 上的分布 D\mathcal{D}D,以及对于每个标记函数 f:X→{0,1}f : \mathcal{X} \to \{0,1\}f:X→{0,1},可实现假设成立

  • 在运行学习算法时,需满足 m≥mH(ϵ,δ)m \geq m_{\mathcal{H}}(\epsilon, \delta)m≥mH​(ϵ,δ) 个由 D\mathcal{D}D 生成并由 f 标记的独立同分布样例

那么,算法可以返回一个假设 h\mathcal{h}h,使得以至少 1−δ1-\delta1−δ 的概率,有 L(D,f)(h)≤ϵL_{(\mathcal{D},f)}(h) \leq \epsilonL(D,f)​(h)≤ϵ

样本复杂度

其中,函数 mH:(0,1)2→Nm_{\mathcal{H}} : (0,1)^2 \to \mathbb{N}mH​:(0,1)2→N 决定了学习 H\mathcal{H}H 的样本复杂度,也就是说,需要多少样本才能保证一个可能大致正确的解决方案。样本复杂度是关于精度 ϵ\epsilonϵ 和置信度 δ\deltaδ 的函数。它还取决于假设类 H\mathcal{H}H 的属性(例如,对于一个有限类,我们已经表明样本复杂度取决于 H\mathcal{H}H 大小的对数)

注意,如果 H\mathcal{H}H 是 PAC 可学习的,那么有许多函数 mHm_HmH​ 满足 PAC 可学习性的定义中的要求。因此,为了精确起见,我们将学习 H\mathcal{H}H 的样本复杂度定义为“最小函数”,也就是说,对于任何 ϵ,δ\epsilon, \deltaϵ,δ,mH(ϵ,δ)m_{\mathcal{H}}(\epsilon, \delta)mH​(ϵ,δ)是满足具有精度和置信度的 PAC 学习要求的最小整数。即:

mH(ϵ,δ)≤⌈log⁡(∣H∣/δ)ϵ⌉m_{\mathcal{H}}(\epsilon, \delta) \leq \left\lceil \frac{\log(|\mathcal{H}|/\delta)}{\epsilon} \right\rceilmH​(ϵ,δ)≤⌈ϵlog(∣H∣/δ)​⌉

去除可实现性假设

现在我们尝试泛化 PAC。之前,我们要求学习算法满足可实现性假设,对于一对数据分布 D\mathcal{D}D 和标记函数 f 能够成功工作。现在,我们将放弃这一可实现性假设,允许函数存在误差,即不可知(agnostic) PAC 模型。

回忆一下,可实现性假设要求存在一个 h∗∈Hh^* \in \mathcal{H}h∗∈H,使得 Px∼D[h∗(x)=f(x)]=1\mathbb{P}_{x \sim \mathcal{D}}[h^*(x) = f(x)] = 1Px∼D​[h∗(x)=f(x)]=1

我们通过用更灵活的数据-标签生成分布替代“目标标记函数”来放松可实现性假设。正式地,让 D\mathcal{D}D 成为 X×Y\mathcal{X} \times \mathcal{Y}X×Y 上的概率分布,分别代表域集合和标签集合(通常我们考虑 Y={0,1}\mathcal{Y} = \{0,1\}Y={0,1})。也就是说,D \mathcal{D}D 是域点和标签的联合分布。这种分布可以视为由两部分组成:

  • 未标记域点的分布 Dx\mathcal{D}_xDx​(有时称为边缘分布)

  • 每个域点的标签的条件概率 D((x,y)∣x)\mathcal{D}((x,y)|x)D((x,y)∣x)

在木瓜的例子中,前者确定了木瓜的颜色和硬度落在某些颜色-硬度值域中的概率,后者表示某个颜色和硬度的木瓜是美味的概率

重新定义 true error:

LD(h)=defP(x,y)∼D[h(x)≠y]=defD({(x,y):h(x)≠y})L_{\mathcal{D}}(h) \overset{\text{def}}{=} \mathbb{P}_{(x,y) \sim \mathcal{D}}[h(x) \neq y] \overset{\text{def}}{=} \mathcal{D}(\{(x,y) : h(x) \neq y\})LD​(h)=defP(x,y)∼D​[h(x)=y]=defD({(x,y):h(x)=y})

empirical risk 因为只知道训练集,本来就不知道数据的分布,所以与原来一致:

LS(h)=def∣{i∈[m]:h(xi)≠yi}∣mL_{S}(h) \overset{\text{def}}{=} \frac{\left|\{i \in [m] : h(x_i) \neq y_i\}\right|}{m}LS​(h)=defm∣{i∈[m]:h(xi​)=yi​}∣​

我们的目标还是最小化LD(h)L_{\mathcal{D}}(h)LD​(h),实际上,可以证明,最优的标签预测函数,即贝叶斯最优预测器 fDf_{\mathcal{D}}fD​ 是:

fD(x)={1if P[y=1∣x]≥1/20otherwisef_{\mathcal{D}}(x) = \begin{cases} 1 & \text{if } \mathbb{P}[y = 1 | x] \ge 1/2 \\ 0 & \text{otherwise} \end{cases}fD​(x)={10​if P[y=1∣x]≥1/2otherwise​

没有比它错误率更低的分类器了,然而,由于不知道 D\mathcal{D}D,没法得到它。我们现在可以给出不可知 PAC 可学习性的正式定义:

当存在一个函数 mH:(0,1)2→Nm_{\mathcal{H}} : (0,1)^2 \to \mathbb{N}mH​:(0,1)2→N 和一个学习算法,具有以下性质时,一个假设类 H\mathcal{H}H 是不可知 PAC 可学习的:于每一个 ϵ,δ∈(0,1)\epsilon, \delta \in (0,1)ϵ,δ∈(0,1) 和每一个在 X×Y\mathcal{X} \times \mathcal{Y}X×Y 上的分布 D\mathcal{D}D,当在由 D\mathcal{D}D 生成的 m≥mH(ϵ,δ)m\geq m_{\mathcal{H}}(\epsilon, \delta)m≥mH​(ϵ,δ) 个独立同分布的样本上运行学习算法时,该算法返回一个假设 hhh,使得在至少 1−δ1-\delta1−δ 的概率下:

LD(h)≤min⁡h′∈HLD(h′)+ϵL_{\mathcal{D}}(h) \le \min_{h' \in \mathcal{H}} L_{\mathcal{D}}(h') + \epsilonLD​(h)≤h′∈Hmin​LD​(h′)+ϵ

其他形式的任务

我们之前的例子都是西瓜甜不甜,模型是二分类的,只需要给出 0/1。其他任务类型包括:

  • 多分类

  • 回归,LD(h)=defE(x,y)∼D(h(x)−y)2L_{\mathcal{D}}(h) \overset{\text{def}}{=} \mathbb{E}_{(x,y) \sim \mathcal{D}} (h(x) - y)^2LD​(h)=defE(x,y)∼D​(h(x)−y)2

现在我们泛化模型损失loss:

给定任意集合 H\mathcal{H}H 和某个域 ZZZ,令损失函数 ℓ\ellℓ 为从 H×Z\mathcal{H} \times ZH×Z 到非负实数集的任意函数(ℓ:H×Z→R+\ell : \mathcal{H} \times Z \to \mathbb{R}_{+}ℓ:H×Z→R+​ )注意,对于预测问题,我们有 Z=X×YZ=\mathcal{X} \times \mathcal{Y}Z=X×Y。然而,我们对损失函数的概念超出了预测任务的范围,因此允许 X×Y\mathcal{X} \times \mathcal{Y}X×Y 是任何示例域

我们现在定义风险函数(risk function)为一个分类器 h∈Hh \in \mathcal{H}h∈H 在概率分布D\mathcal{D}D 下的期望损失:

LD(h)=defEz∼D[ℓ(h,z)]L_{\mathcal{D}}(h) \overset{\text{def}}{=} \mathbb{E}_{z \sim \mathcal{D}} [\ell(h, z)]LD​(h)=defEz∼D​[ℓ(h,z)]

同样,我们定义经验风险为给定样本 S={z1,...zm}∈ZmS=\{z_1,...z_m\} \in Z^mS={z1​,...zm​}∈Zm 的期望损失,即:

LS(h)=def1m∑i=1mℓ(h,zi)L_{S}(h) \overset{\text{def}}{=} \frac{1}{m} \sum_{i=1}^{m} \ell(h, z_i)LS​(h)=defm1​i=1∑m​ℓ(h,zi​)

例如,0-1 loss function:

ℓ0−1(h,(x,y))=def{0if h(x)=y1if h(x)≠y\ell_{0-1}(h, (x, y)) \overset{\text{def}}{=} \begin{cases} 0 & \text{if } h(x) = y \\ 1 & \text{if } h(x) \neq y \end{cases}ℓ0−1​(h,(x,y))=def{01​if h(x)=yif h(x)=y​

方差损失:

ℓsq(h,(x,y))=def(h(x)−y)2\ell_{\text{sq}}(h, (x, y)) \overset{\text{def}}{=} (h(x) - y)^2ℓsq​(h,(x,y))=def(h(x)−y)2

一般损失的不可知 PAC 可学习性

现在我们将上面两个章节结合起来,得出一个假设类 H\mathcal{H}H 在一般损失函数 ℓ:H×Z→R+\ell : \mathcal{H} \times Z \to \mathbb{R}_{+}ℓ:H×Z→R+​ 下是 Agnostic PAC Learnable的定义:

存在一个函数 mH:(0,1)2→Nm_{\mathcal{H}} : (0, 1)^2 \to \mathbb{N}mH​:(0,1)2→N,和一个具有以下性质的学习算法:对于每个 ϵ,δ∈(0,1)\epsilon, \delta \in (0, 1)ϵ,δ∈(0,1) 和在 ZZZ 上的分布 D\mathcal{D}D,当在由 D\mathcal{D}D 生成的至少 m≥mH(ϵ,δ)m \geq m_{\mathcal{H}}(\epsilon, \delta)m≥mH​(ϵ,δ) 个独立同分布样本上运行学习算法时,算法返回h∈Hh \in \mathcal{H}h∈H,使得以至少 1−δ1 - \delta1−δ的概率,满足

LD(h)≤min⁡h′∈HLD(h′)+ϵL_{\mathcal{D}}(h) \leq \min_{h' \in \mathcal{H}} L_{\mathcal{D}}(h') + \epsilonLD​(h)≤h′∈Hmin​LD​(h′)+ϵ

其中,LD(h)=EZ∼D[ℓ(h,z)]L_{\mathcal{D}}(h) = \mathbb{E}_{Z \sim \mathcal{D}}[\ell(h, z)]LD​(h)=EZ∼D​[ℓ(h,z)]

可测性(Measurability)的说明:在上述定义中,对于每个 h∈Hh \in \mathcal{H}h∈H ,我们将函数 ℓ(h,⋅):Z→R+\ell(h, \cdot) : Z \to \mathbb{R}_+ℓ(h,⋅):Z→R+​ 视为随机变量,并定义LD(h)L_D(h)LD​(h) 为该随机变量的期望值。为此,我们需要要求函数 ℓ(h,⋅)\ell(h, \cdot)ℓ(h,⋅) 是可测的。

形式上,我们假设存在一个 ZZZ 的子集的 σ\sigmaσ-代数,该代数上定义了概率 D\mathcal{D}D,并且 R+\mathbb{R}_+R+​ 中每个初始区间的原像(preimage)都在这个 σ\sigmaσ-代数中。

在使用 0-1 损失的二分类情况下,σ\sigmaσ-代数是关于 X×{0,1}\mathcal{X} \times \{0, 1\}X×{0,1} 的,并且我们关于 ℓ\ellℓ 的假设等价于假设对于每个 hhh,集合 {(x,h(x)):x∈X}\{(x, h(x)) : x \in \mathcal{X}\}{(x,h(x)):x∈X} 在这个 σ\sigmaσ-代数中。

上一页引入下一页一致收敛

最后更新于6个月前