大致正确学习

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

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

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

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

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

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

样本复杂度

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

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

mH(ϵ,δ)log(H/δ)ϵm_{\mathcal{H}}(\epsilon, \delta) \leq \left\lceil \frac{\log(|\mathcal{H}|/\delta)}{\epsilon} \right\rceil

去除可实现性假设

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

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

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

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

  • 每个域点的标签的条件概率 D((x,y)x)\mathcal{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\})

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}

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

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

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

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

LD(h)minhHLD(h)+ϵL_{\mathcal{D}}(h) \le \min_{h' \in \mathcal{H}} L_{\mathcal{D}}(h') + \epsilon

其他形式的任务

我们之前的例子都是西瓜甜不甜,模型是二分类的,只需要给出 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)^2

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

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

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

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

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

LS(h)=def1mi=1m(h,zi)L_{S}(h) \overset{\text{def}}{=} \frac{1}{m} \sum_{i=1}^{m} \ell(h, z_i)

例如,0-1 loss function:

01(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}

方差损失:

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

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

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

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

LD(h)minhHLD(h)+ϵL_{\mathcal{D}}(h) \leq \min_{h' \in \mathcal{H}} L_{\mathcal{D}}(h') + \epsilon

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

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

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

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

最后更新于