机器学习中的有限假设集合保证：一致与不一致情形下的学习界限
机器学习中的有限假设集合保证：一致与不一致情形下的学习界限
机器学习中的有限假设集合保证是理解算法泛化能力的关键。本文从一致和不一致两种情况出发，通过严谨的数学推导，探讨了有限假设集合的学习界限，并给出了具体的实例说明。
1. 一致情形下的学习界限
定理 2.1 学习界限 —— 假设有限且一致的情形
设H为从X到Y的函数集合，并且是有限的。设A是一个学习算法，对于任意目标概念c ∈ H和i.i.d.的样本S，该算法返回一个一致的假设hS，即：R^(hS) = 0。∀ϵ, δ > 0，如果我们想成立PrS∼Dm[R(hS) ≤ ϵ] ≥ 1 − δ。
则m必须满足：
m ≥ 1/ϵ(log|H| + log(1/δ)). (2.8)
该样本复杂度结果可以等价地表示为以下形式的泛化界限：对∀ϵ, δ > 0，有至少1 − δ的概率会成立：
R(hS) ≤ 1/m(log|H| + log(1/δ)). (2.9)
m越大越好，|H|越小越好
证明：固定ϵ > 0。我们将界定以下事件的概率：某个h ∈ H是一致的，并且其误差超过了ϵ，即：
注意到(1 − ϵ)^m ≤ e^(-ϵm)。
为了满足：Pr(∃h ∈ H : R^(h) = 0 ∧ R(h) > ϵ) ≤ δ,
令|H|e^(-ϵm) ≤ δ。取对数，得到：
m ≥ 1/ϵ(log|H| + log(1/δ)).
定理表明，当假设集合H是有限时，一个一致的算法A是一个PAC学习算法，因为由 (2.8) 给出的样本复杂度由1/ϵ和1/δ的多项式控制。正如 (2.9) 所示，一致假设的泛化误差上界随样本大小m增大而减小，随着|H|的增大而增大。
例子：布尔字面的合取
设Cn是由最多n个布尔字面组成的合取的概念类。一个布尔字面可以是变量xi（其中i ∈ [1, n]）或它的否定x̄i。
例如，当n = 4时，合取式：x1 ∧ x̄2 ∧ x4表明第一个分量和第四个分量必须为1，第二个分量必须为0。向量(1, 0, 0, 1)是这个概念的一个正例，而向量(1, 0, 0, 0)是一个负例。一个正例(1, 0, 0, 1)意味着目标概念不能包含字面x̄1和x̄3，并且不能包含字面x2和x4。
上图展示了一个n = 6，一致假设的例子，对该样本，算法返回的假设是：x̄1 ∧ x2 ∧ x5 ∧ x6。
因为每个字面可以被正向包含、否定包含或不包含，|H| = |Cn| = 3^n。将此结果代入到样本复杂度的界中，可以得到∀ϵ, δ > 0的样本复杂度界:
m ≥ 1/ϵ((log3)n + log(1/δ))
因此，由最多n个布尔字面组成的合取类是PAC可学习的，计算复杂度也是多项式的。
例子：通用概念类
考虑布尔向量集合X = {0, 1}^n，其中每个向量有n个分量。设Un为由X的所有子集组成的概念类。这个概念类是PAC可学习的吗？
为了保证一致假设，假设类必须包含概念类，因此：
|H| ≥ |Un|=2^(2^n)
定理 2.1 给出了以下样本复杂度下界：
m ≥ 1/ϵ((log2)2^n + log(1/δ)).
右边的式子是关于n的指数级，并非多项式。因此这个通用概念类不是PAC可学习的。
2. 不一致情形下的学习界限
推论 2.1
固定ϵ > 0，设S表示大小为m的独立同分布样本。则对于任意假设h : X → {0, 1}，以下不等式成立：
PrS∼Dm[R^(h) - R(h) ≥ ϵ] ≤ exp(-2mϵ^2)
PrS∼Dm[R^(h) - R(h) ≤ -ϵ] ≤ exp(-2mϵ^2)
这意味着以下双侧不等式成立：
PrS∼Dm[|R^(h) - R(h)| ≥ ϵ] ≤ 2exp(-2mϵ^2)
推论 2.2 泛化界 —— 单一假设
固定一个假设：h : X → {0, 1}，对于任意δ > 0，以下不等式以至少1 − δ的概率成立：
R(h) ≤ R^(h) + sqrt(log(2/δ)/(2m)). (2.17)
例子：扔硬币
假设抛掷一个带偏的硬币，正面朝上的概率为p。令假设h为总是正面朝上。则真实误差率为R(h) = p，经验误差为R^(h) = p^。其中，其中p^是基于独立同分布抽取的训练样本中正面的经验概率。因此，推论 2.2 保证以下不等式以至少1 − δ的概率成立：
|p - p^| ≤ sqrt(log(2/δ)/(2m)). (2.18)
因此，如果选择δ = 0.02，并使用大小为 500 的样本，那么以至少 98% 的概率，可以保证p^的以下近似质量：
|p - p^| ≤ sqrt(log(10)/1000) ≈ 0.048. (2.19)
定理2.2 学习界限 —— 假设有限且不一致的情形
设H为一个有限的假设集合。那么，对于任意δ > 0，以下不等式以至少1 − δ的概率成立：
∀h ∈ H, R(h) ≤ R^(h) + sqrt((log|H| + log(2/δ))/(2m)). (2.20)
证明：设h1, …, h|H|为H的元素。对每个假设应用推论 2.2，可得：
Pr[∃h ∈ H, |R^(h) - R(h)| > ϵ] = Pr[|R^(h1) - R(h1)| > ϵ ∨ … ∨ |R^(h|H|) - R(h|H|)| > ϵ]
≤ ∑h∈H Pr[|R^(h) - R(h)| > ϵ]
≤ 2|H|exp(-2mϵ^2).
令右侧等于δ并解出ϵ，完成证明。
定义（泛化PAC学习）
设H为一个假设集合。算法A是一个泛化PAC学习算法，如果存在一个多项式函数poly(⋅, ⋅, ⋅)，使得对于任意ϵ > 0和δ > 0，以及定义在X × Y上的所有分布D，当样本大小满足：
m ≥ poly(1/ϵ, 1/δ, n, size(c)),
以下不等式成立：
PrS∼Dm[R(hS) - minh∈H R(h) ≤ ϵ] ≥ 1 − δ.
如果算法A的运行时间进一步满足poly(1/ϵ, 1/δ, n, size(c))，那么它被称为一个高效的泛化PAC学习算法。