机器学习第十一章——计算学习理论

一、基础知识

计算学习理论(computational learning theory)研究的是关于通过“计算”来进行“学习”的理论，即关于机器学习的理论基础，其目的是分析学习任务的困难本质，为学习算法提供理论保证，并根据分析结果指导算法设计。

给定样例 D假设 X中的所有样本服从一个隐含未知的分布D，D中所有样本都是独立地从这个分布上采样而得，即独立同分布(independent and identically distributed)样本令h为从X到Y的一个映射，其泛化误差为

$E(h ; \mathcal{D})=P_{\boldsymbol{x} \sim \mathcal{D}}(h(\boldsymbol{x}) \neq y)$

h在D上的经验误差为：

$\hat{E}(h;D)=\frac{1}{m}\sum ^{m}_{i=1}II (h(x_{i})\neq y_{i})$

我们会用到几个常用不等式：

Jensen不等式：对于凸函数f(x)，有

$f(E(X))\leqslant E(f(x))$

Hoeffding不等式：若有m个独立随机变量，且对任意的i∈[0,1]，则对任意ϵ>0，那么有

$P({1\over m}\sum ^m_{i=1}x_i-{1\over m}\sum ^m_{i=1}E(x_i)\geqslant \epsilon )\leqslant exp(-2m\epsilon ^2)$
$P(|{1\over m}\sum ^m_{i=1}x_i-{1\over m}\sum ^m_{i=1}E(x_i)|\geqslant \epsilon )\leqslant 2exp(-2m\epsilon ^2)$

McDiarmid不等式：若有m个独立随机变量，且对任意的i∈[0,1]，则有

$sup_{x_{1},...,x_{m}.{x}'_{i}}|f(x_{1},...,x_{m})-f(x_{1},...,x_{i-1},{x}'_{i},x_{i+1},..,x_{m})|\leqslant c_{i}$

二、PAC学习

概率近似正确(Probably ApproximatelyCorrect，简称PAC)：

概念(concept)：这是从样本空间 $\mathcal{X}$ 到标记空间 $\mathcal{Y}$ 的映射，它决定示例 $x$ 的真实标记 $y$ ,若对任何样例 $(x,y)$ 有 $c(x)= y$ 成立;所有我们希望学得的目标概念所构成的集合称为“概念类”(conceptclass),
假设空间（Hypothesis Space）：给定学习算法 $\mathfrak{L }$ ,它所考虑的所有可能概念的集合称为“假设空间”(hypothesis space)，用符号 $\mathcal{H}$ 表示．对于假设空间中的任一概念，用h表示，称为“假设”（hypothesis）。
可分性（Separability）：若目标概念c属于假设空间 $\mathcal{H}$ ，则称该问题对学习算法 $\mathfrak{L }$ 是可分的（separable）或一致的（consistent）。反之，若c不属于 $\mathcal{H}$ ，则称该问题对学习算法 $\mathfrak{L }$ 是不可分的（non-separable）或不一致的（non-consistent）。

定义：

PAC辨识（PAC Identify）：给定置信度t和误差参数e，若存在学习算法A，其输出假设h使得泛化误差E(h)小于e的概率大于置信空间1-t，则称学习算法能从假设空间H中PAC辨识概念类C。

PAC可学习（PAC Learnable）：若存在学习算法A和多项式函数poly(.,.,.,.)，使得对于任意m >= poly(1/e, 1/t, size(X), size(c))，A能从假设空间H中PAC辨识出概念类C，则称概念类C对假设空间H而言是PAC可学习的。

PAC学习算法（PAC Learning Algorithm）：若学习算法A使概念类C为PAC可学习，且A的运行时间也是多项式函数poly(1/e, 1/t, size(X), size(c))，则称A为概念类C的PAC学习算法。

样本复杂度（Sample Complexity）：满足PAC学习算法A所需的m >= poly(1/e, 1/t, size(X), size(c))中最小的m，称为算法A的样本复杂度。

三、有限假设空间

1可分情形

在可分情形中，目标概念 $c$ 存在于假设空间 $\mathcal{H}$ 中，即 $c\in \mathcal{H}$ 。这意味着假设空间 $\mathcal{H}$ 中存在至少一个假设，该假设能够完全按照目标概念的规则对所有示例进行正确分类或标记。

我们先估计泛化误差大于 $\epsilon$ 但在训练集上仍表现完美的假设出现的概率.假定 $h$ 的泛化误差大于 $\epsilon$ ,对分布 $\mathcal{D}$ 上随机采样而得的任何样例 $(x, y)$ ,有

$P(h(x)=y)=1-P(h(x)\neq y)=1-E(h)< 1-\epsilon$

由于 $D$ 包含 $m$ 个从 $\mathcal{D}$ 独立同分布采样而得的样例,因此, $h$ 与 $D$ 表现一致的概率为

$P((h(x_{1})=y_{1})\wedge ...\wedge (h(x_{m})=y_{m}))=(1-P(h(x)\neq y))^{m}< (1-\epsilon)^{m}$

保证泛化误差大于 $\epsilon$ ,且在训练集上表现完美的所有假设出现概率之和不大于 $\delta$ ,得：

$m\geqslant \frac{1}{\epsilon }(\ln |\mathcal{H}|+\ln \frac{1 }{\delta})$

2不可分情形

假定对于任何 $h\in \mathcal{H},\hat{E}(h)\neq 0$ ，由Hoeffding不等式推理得:

定理：若 $\mathcal{H}$ 为有限假设空间, $0<\delta <1$ ，则对任意 $h\in \mathcal{H}$ ,有

定义：不可知PAC可学习(agnostic PAC learnable):令 $m$ 表示从分布 $\mathcal{D}$ 中独立同分布采样得到的样例数目， $0 <\epsilon ,\delta < 1$ ，对所有分布 $\mathcal{D}$ ,若存在学习算法 $\mathfrak{L }$ 和多项式函数poly(·, ·,·,·)，使得对于任何m ≥poly(1/e,1/6,size(a), size(c)), $\mathfrak{L }$ 能从假设空间 $\mathcal{H}$ 中输出满足下式的假设 $h$ :

$P(E(h)-\min_{{h}'\in \mathcal{H}}E({h}')\leqslant \epsilon )\geqslant 1-\delta$

则称假设空间 $\mathcal{H}$ 是不可知PAC可学习的.

四、VC维

增长函数(growth function)：对所有 $m\in \mathbb{N}$ ,假设空间 $\mathcal{H}$ 的增长函数 $\Pi _{\mathcal{H}}(m)$ 为 $\Pi _{\mathcal{H}}(m)=\max_{\left \{ x_{1},...,x_{m} \right \}\subseteq \mathcal{X}}|\left \{ (h(x_{1}),...h(x_{m}))|h\in \mathcal{H})\right \}|$

对分(dichotomy):对二分类问题来说, $\mathcal{H}$ 中的假设对D中示例赋予标记的每种可能结果称为对D的一种“对分”．

打散(shattering):若假设空间 $\mathcal{H}$ 能实现示例集D上的所有对分,即 $\Pi _{\mathcal{H}}(m)=2^{m}$ ，则称示例集D能被假设空间 $\mathcal{H}$ “打散”.

VC维:假设空间 $\mathcal{H}$ 的VC维是能被 $\mathcal{H}$ 打散的最大示例集的大小，即

$VC(\mathcal{H})=\max\left \{ m:\Pi_{\mathcal{H}} (m)=2^{m} \right \}$

$VC(\mathcal{H})=d$ 表明存在大小为d的示例集能被假设空间 $\mathcal{H}$ 打散.

通常这样来计算 $\mathcal{H}$ 的.VC维:若存在大小为d的示例集能被 $\mathcal{H}$ 打散,但不存在任何大小为d＋1的示例集能被 $\mathcal{H}$ 打散,则H的VC维是d.例：

定理：

若假设空间 $\mathcal{H}$ 的VC维为.d,则对任意 $m > d,0<\delta <1$ 和 $h\in \mathcal{H}$ 有
任何VC维有限的假设空间 $\mathcal{H}$ 都是(不可知)PAC可学习的.

五、Rademacher复杂度

Rademacher复杂度(Rademacher complexity)是另一种刻画假设空间复杂度的途径,与VC维不同的是,它在一定程度上考虑了数据分布.

定义：

函数空间 $\mathcal{F}$ 关于 $Z$ 的经验Rademacher复杂度

函数空间 $\mathcal{F}$ 关于 $\mathcal{Z}$ 上分布 $\mathcal{D}$ 的Rademacher复杂度

定理:

对实值函数空间 $\mathcal{F}:\mathcal{Z}\rightarrow [0,1]$ 根据分布 $\mathcal{D}$ 从 $\mathcal{Z}$ 中独立同分布采样得到示例集 $Z=\left \{ z_{1},z_{2},...,z_{m} \right \},z_{i}\in \mathcal{Z},0< \delta < 1$ ,对任意 $f\in \mathcal{F}$ ，以至少 $1-\delta$ 的概率有

对假设空间 $\mathcal{H}:\mathcal{X}\rightarrow \left \{ -1,+1 \right \}$ ,根据分布 $\mathcal{D}$ 从 $\mathcal{X}$ 中独立同分布采样得到示例集 $D=\left \{ x_{1},x_{2},...,x_{m} \right \},x_{i}\in \mathcal{X},0< \delta < 1$ ,对任意 $h\in \mathcal{H}$ ,以至少 $1-\delta$ 的概率有

假设空间 $\mathcal{H}$ 的Rademacher 复杂度 $R_{m}(\mathcal{H})$ 与增长函数 $\Pi _{\mathcal{H}}(m)$ 满足

$R_{m}(\mathcal{H})\leqslant \sqrt{\frac{2\ln \Pi _{\mathcal{H}}(m)}{m}}$

六、稳定性

算法的“稳定性”考察的是算法在输入发生变化时,输出是否会随之发生较大的变化.学习算法的输入是训练集,因此下面我们先定义训练集的两种变化.

移除： $D^{\setminus i}$ ，表示移除D中第i个样例得到的集合 $D^{\setminus i}=\left \{ z_{1}, z_{2},..., z_{i-1}, z_{i+1},..., z_{m} \right \}$
替换： $D^{i}$ ，表示替换D中第i个样本得到的集合 $D^{ i}=\left \{ z_{1}, z_{2},..., z_{i-1},{z}'_{i} z_{i+1},..., z_{m} \right \}$

损失函数刻画了预测标记和真实标记的差别：

泛化损失: $\ell(\mathfrak{L} ,D)=\mathbb{E}_{x\in \mathcal{X},z=(x,y)}[\ell(\mathfrak{L}_{D},z)]$
经验损失: $\hat{\ell}(\mathfrak{L} ,D)=\frac{1}{m}\sum_{i=1}^{m}\ell(\mathfrak{L}_{D},z_{i})$
留一(leave-one-out)损失: $\ell_{loo}(\mathfrak{L} ,D)=\frac{1}{m}\sum_{i=1}^{m}\ell(\mathfrak{L}_{D^{\setminus i}},z_{i})$