【笔记】机器学习基础 - Ch2. PAC Learning Framework

zhyh's blog / 2023-08-07 / 原文

🤔还在慢慢熟悉这种思维方式，更的会慢一点，希望没有理解错误🙏

2.1 PAC learning model

服从某个分布 \(\cal D\) 抽取样本 \(x\in \cal X\)；称一个映射 \(c:\cal X\to y\) 为概念 concept，称概念的集合 \(\cal C\) 为概念类 concept class。考虑这个概念类 \(\cal C\) 的“可学习性”。
现对于一个固定、未知的待学习目标概念 \(c\in \cal C\)，我们有一个假设概念 \(h\) 的集合 hypothesis set \(\cal H\) 以供选择（\(\cal H,C\) 不一定有交 coincide）。以 i.i.d. 抽取样本 \(S=(x _1,\dotsb, x _m)\) 同时得到标签 \((c(x _1),\dotsb, c(x _m))\)，据此以某种算法选择 \(h _S\in \cal H\)，并用泛化误差 generalization error 刻画 \(h _S\) 相对 \(c\) 的差距：

定义泛化误差 generalization error
假设概念 \(h\in \cal H\) 相对目标概念 \(c\in \cal C\) 的泛化误差 \(R(h)\)，为在给定分布 \(\cal D\) 以 i.i.d. 采样下两者映射结果不相等的概率（错误概率）：

\[R(h)={\mathbb P} _{x\sim \cal D}[h(x)\ne c(x)]={\mathbb E} _{x\sim \cal D}[1 _{h(x)\ne c(x)}] \]

但是 \(\cal D, c\) 都是未知的。我们考虑对 \(h\) 计算经验误差 empirical error \(\hat{R} _S(h)\)：

定义经验误差 empirical error
假设概念 \(h\in \cal H\) 相对目标概念 \(c\in \cal C\) 的经验误差 \(\hat{R} _S(h)\)，为在给定的样本 \(S=(x _1,\dotsb, x _m)\) 下两者映射结果不相等的频率：

\[\hat{R} _S(h)=\frac{1}{m}\sum _{i=1}^{m} 1 _{h (x _i)\ne c(x _i)} \]

可以证明，经验误差 \(\hat{R} _S(h)\) 当样本在分布 \(\cal D\) 以 i.i.d. 采样下的期望，等于泛化误差 \(R(h)\)：

\[{\mathbb{E}} _{S\sim \cal D ^m}[\hat{R} _S(h)]=R(h) \]

回到概念类 \(\cal C\) 的“可学习性”。
设表示 \(\cal X\) 任一元素的计算开销是 \(O(n)\)，表示 \(\cal C\) 任一元素的计算开销是 \(\text{size}(c)\)。对于已知的 \(\cal C\)，设计某个算法 \(\cal A\)：从 \(\cal D\) 中以 i.i.d. 采样带标签样本集 \(S\)，算法 \(\cal A\) 接受 \(S\) 并返回 \(h _S\)。
接下来定义 PAC (Probably Approximately Correct) 学习：

定义 PAC 学习 PAC-learning
称概念集合 concept class \(\cal C\) 是 PAC-learnable，若存在一个算法 \(\cal A\) 和一个多项式函数 \(poly(\cdot,\cdot,\cdot,\cdot)\)，使得 \(\forall \epsilon>0, \delta>0, \cal{D}, c\in \cal{C}\)，只要满足 \(m\ge poly(1/\epsilon, 1/\delta, n, \text{size}(c))\)，就有：

\[\mathbb{P} _{S\sim\cal D ^m}[R(h _S)\le\epsilon]\ge 1-\delta \]

即，只要样本容量 \(m\) 足够大，其喂给算法 \(\cal A\) 得到的 \(h _S\) 就能以至少 \(1-\delta\) 的概率、达到最多只有 \(\epsilon\) 的泛化误差（错误概率），因此称为 probably approximately correct。值得一提的是我们并没有对 \(\cal D\) 做出特别假设。此外若 \(n, \text{size}(c)\) 不需要特别讨论，比如常数，我们可以忽略之。
显然该式等价于 \(\mathbb{P} _{S\sim\cal D ^m}[R(h _S)>\epsilon]\le \delta\)。
有些时候，我们还可以用“泛化界” generalization bound 来等价地表达这种关系，若 \(m\ge poly(1/\epsilon, 1/\delta,\dotsb)\) 可以解得 \(\epsilon\ge poly'(1/m, 1/\delta,\dotsb)\)，结合 \(\mathbb{P} _{S\sim\cal D ^m}[R(h _S)>\epsilon]\le \delta\) 可以阐述为：
对于任意 \(\epsilon,\delta>0\)，以至少 \(1-\delta\) 的概率，会有 \(R(h _S)\le poly'(1/m, 1/\delta,\dotsb)\)
可见我们以一个上界限制住了 \(h _S\) 的泛化误差。观察该式，往往会发现当 \(m\) 变大，上界随之下降，这符合我们的认知。