机器学习 笔记

第十二章 计算学习理论

机器学习

Posted by RavenZhao on October 14, 2018

第十二章 计算学习理论

12.1 基础知识

  • 计算学习理论（computational learning theory）研究的是关于通过“计算”来进行“学习”的理论，即关于机器学习的理论基础。
    • 目的：分析学习任务的困难本质，为学习算法提供理论保证，并根据分析结果指导算法设计。
  • 给定样例集$D={(x_1,y_1),(x_2,y_2),…,(x_m,y_m)},x_i\in\mathcal{X}$，在二分类问题中，$y_i\in\mathcal{Y}={-1,+1}$。假设$\mathcal{X}$中的所有样本服从一个隐含未知的分布$\mathcal{D}$，$\mathcal{D}$中所有样本都是独立地从这个分布上采样而得，即独立同分布（independent and identically distributed，简称i.i.d.）样本。
    • 令$h$为从$\mathcal{X}$到$\mathcal{Y}$的一个映射，其泛化误差为$E(h;D)=P_{x\sim D}(h(x)\neq y)$
    • $h$在$D$上的经验误差为$\hat{E}(h;D)=\frac1m\sum_{i=1}^m\prod(h(x_i)\neq y_i)$
    • 由于$D$是$\mathcal{D}$的独立同分布采样，因此$h$的经验误差的期望等于其泛化误差。
    • 通常用$\epsilon$表示预先设定的学得模型所应满足的误差要求，亦称“误差参数”。

12.2 PAC学习

  • 计算学习理论中最基本的是概率近似正确（Probably Approximately Correct，简称PAC）学习理论。

  • 令$c$表示“概念”（concept），这是从样本空间$\mathcal{X}$到标记空间$\mathcal{Y}$的映射，它决定示例$x$的真实标记$y$，若对任何样例$(x,y)$有$c(x)=y$成立，则称$c$为目标概念。

    • 希望学得的目标概念所构成的集合成为“概念类”（concept class），记为$C$。

  • 给定学习算法$\mathcal{L}$，它所考虑的所有可能概念的集合成为“假设空间”（hypothesis space），用符号$\mathcal{H}$表示。

    • 学习算法通常事先并不知道概念类的真实存在，因此$\mathcal{H}$和$\mathcal{C}$通常不同。
    • 学习算法会把自认为可能的目标概念集中起来构成$\mathcal{H}$，对$h\in\mathcal{H}$，由于并不能确定它是否真是目标概念，因此成为“假设”（hypothesis）。假设$h$也是从样本空间$\mathcal{X}$到标记空间$\mathcal{Y}$的映射。
    • 若目标概念$c\in\mathcal{H}$，则$\mathcal{H}$中存在假设能将所有示例按与真实标记一致的方式完全分开，我们称该问题与学习算法$\mathcal{L}$是“可分的”（separable），亦称“一致的”（consistent）
    • 若$c\notin\mathcal{H}$，则$\mathcal{H}$中不存在任何假设能将所有示例完全正确分开，称该问题对学习算法$\mathcal{L}$是“不可分的”（non-separable），亦称“不一致的”（non-consistent）

  • 给定训练集$D$，希望基于学习算法$\mathcal{L}$学得的模型所对应的假设$h$尽可能接近目标概念$c$。令$\delta$表示置信度

    • PAC辨识（PAC Identify）：对$0<\epsilon,\delta<1$，所有$c\in\mathcal{C}$和分部$D$，若存在学习算法$\mathcal{L}$，其输出假设$h\in\mathcal{H}$满足$P(E(h))\leq\epsilon\geq1-\delta$，则称学习算法$\mathcal{L}$能从假设空间$\mathcal{H}$中PAC辨识概念类$\mathcal{C}$

    • PAC可学习（PAC Learnable）：令$m$表示从分部$\mathcal{D}$中独立同分布采样得到的样例数目，$0<\epsilon,\delta<1$，对所有分部$\mathcal{D}$，若存在学习算法$\mathcal{L}$和多项式函数$poly(·,·,·,·)$，使得对任何$m\geq poly(1/\epsilon,1/\delta,size(x),size(c))$，$\mathcal{L}$能从假设空间$\mathcal{H}$中PAC辨识概念类$\mathcal{C}$，则称概念类$\mathcal{C}$对假设空间$\mathcal{H}$而言是PAC可学习的，有时也简称概念类$\mathcal{C}$是PAC可学习的。

    • 样本复杂度（Sample Complexity）：满足PAC学习算法$\mathcal{L}$所需的$m\geq poly(1/\epsilon,1/\delta,size(x),size(c))$中最小的$m$，称为学习算法$\mathcal{L}$的样本复杂度。

  • PAC学习中一个关键因素是假设空间$\mathcal{H}$的复杂度。$\mathcal{H}$包含了学习算法$\mathcal{L}$所有可能输出的假设

    • 若在PAC学习中假设空间与概念类完全相同，即$\mathcal{H}=\mathcal{C}$，这称为“恰PAC可学习”（properly PAC learnable）。意味着学习算法的能力与学习任务“恰好匹配”。
    • 实际中，我们对概念类$\mathcal{C}$通常一无所知，$\mathcal{H}\neq\mathcal{C}$。一般而言，$\mathcal{H}$越大，包含任意目标概念的可能性越大，从中找到某个具体目标概念的难度越大。
    • $\lvert\mathcal{H}\rvert$有限时，称$\mathcal{H}$为“有限假设空间”，否则成为“无限假设空间”。

12.3 有限假设空间

12.3.1 可分情形

  • 可分情形意味着目标概念$c$属于假设空间$\mathcal{H}$，即$c\in\mathcal{H}$。
  • 给定包含$m$个样本的训练集$D$，找出满足误差参数的假设：
    • 既然$D$中样例标记都是目标概念$c$赋予的，并且$c$存在与假设空间$\mathcal{H}$中，那么任何在训练集$D$上出现的标记错误的假设肯定不是目标概念$c$。
    • 只需要保留与$D$一致的假设，删除不一致的假设。
    • 若训练集$D$足够大，可不断借助$D$中的样例剔除不一致的假设，直到$\mathcal{H}$中仅剩下一个假设为止，这个假设就是概念目标$c$。
    • 由于训练集规模有限，假设空间$\mathcal{H}$中可能存在不止一个与$D$一致的“等效”假设，无法进一步区分其优劣。
  • 需要多少样本才能学得目标概念$c$的有效近似：
    • 对PAC学习来说，只要训练集的规模能使学习算法$\mathcal{L}$以概率$1-\delta$找到目标假设的$\epsilon$近似即可。
    • 先估计泛化误差大于$\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)\and\cdots\and(h(x_m)=y_m))=(1-P(h(x)\neq y))^m<(1-\epsilon)^m$
    • 我们事先并不知道学习算法$\mathcal{L}$会输出$\mathcal{H}$中的哪个假设，但仅需保证泛化误差大于$\epsilon$，且在训练集上表现完美的所有假设出现概率之和不大于$\delta$即可：$P(h\in\mathcal{H}:E(h)>\epsilon\and\hat E(h)=0)<\lvert\mathcal{H}\rvert(1-\epsilon)^m<\lvert\mathcal{H}\rvert e^{-me}$
      • 令$\lvert\mathcal{H}\rvert e^{-me}\leq\delta$，得到$m\geq\frac1\epsilon(ln\lvert\mathcal{H}\rvert +ln\frac1\delta)$
  • 有限假设空间$\mathcal{H}$都是PAC可学习的，所需样例数目如上式所示。输出假设$h$的泛化误差随样例数目的增多而收敛到0，收敛速率为$O(\frac1m)$

12.3.2 不可分情形

  • 对较为困难的学习问题，目标概念$c$往往不存在与假设空间$\mathcal{H}$中。

  • 假定对于任何$h\in\mathcal{H},\hat E(h)\neq0$，也就是说，$\mathcal{H}$中的任意一个假设都会在训练集上出现或多或少的错误，由Hoeffding不等式易知：

    • 引理 若训练集$D$包含$m$个从分布$\mathcal{D}$上独立同分布采样而得的样例，$0<\epsilon<1$，则对任意$h\in\mathcal{H}$，有：$P(\hat E(h)-E(h)\geq\epsilon)\leq exp(-2m\epsilon^2)$，$P(E(h)-\hat E(h)\geq\epsilon)\leq exp(-2m\epsilon^2)$,$P(\lvert E(h)-\hat E(h)\rvert\geq\epsilon)\leq 2exp(-2m\epsilon^2)$

    • 推断 若训练集$D$包含$m$个从分布$\mathcal{D}$上独立同分布采样而得的样例，$0<\epsilon<1$，则对任意$h\in\mathcal{H}$，下式以至少$1-\delta$的概率成立：$\hat E(h)-\sqrt{\frac{ln(2/\delta)}{2m}}\leq E(h)\leq\hat E(h)+\sqrt{\frac{ln(2/\delta)}{2m}}$。该式表明，样例数目$m$较大时，$h$的经验误差是其泛化误差很好的近似

    • 对于有限假设空间$\mathcal{H}$，有：

      • 定理 若$\mathcal{H}$为有限假设空间，$0<\delta<1$，则对任意$h\in\mathcal{H}$，有$P(\lvert E(h)-\hat E(h)\rvert\leq\sqrt{\frac{ln\lvert\mathcal{H}\rvert+ln(2/\delta)}{2m}})\geq 1-\delta$

  • 不可知PAC学习（agnostic PAC learnable）：令$m$表示从分布$\mathcal{D}$中独立同分布采样得到的样例数目，$0<\epsilon,\delta<1$，对所有分布$\mathcal{D}$，若存在学习算法$\mathcal{L}$和多项式函数$poly(·,·,·,·)$，使得对于任何$m\geq poly(1/\epsilon,1/\delta,size(x),size(c))$，$\mathcal{L}$能从假设空间$\mathcal{H}$中输出满足下式的假设$h$：$P(E(h)-\mathop{min}\limits_{h’\in\mathcal{H}}E(h’)\leq\epsilon)\geq 1-\delta$，则称假设空间$\mathcal{H}$是不可知PAC可学习的。

12.4 VC维

  • 现实学习任务通常是无限假设空间，对此种情形的可学习性进行研究，需度量假设空间的复杂度，最常见的办法是考虑假设空间的“VC维”（Vapnik-Chervonenkis dimension）
  • 增长函数（growth function）：表示假设空间$\mathcal{H}$对m个示例所能赋予标记的最大可能结果数。
    • $\mathcal{H}$对示例所能赋予标记的可能结果数越大，$\mathcal{H}$的表示能力越强，对学习的适应能力越强。
    • 增长函数描述了假设空间$\mathcal{H}$的表示能力
CATALOG
    FEATURED TAGS
    机器学习 笔记 Coursera Java Python