机器学习是设计算法，在假设集合里，根据给定数据集，选出与实际模式最为相近的假设（可能与相同，也可能不同）。
那什么情况下学习是可行的？即保证和是相似的。

1. 数据集内的表现约等于;
2. 在数据集外的表现约等于在数据集内的表现。

结合1、2可保证，由算法在给定数据集上学习到的（即数据集内的表现约等于）在数据集外的表现也约等于，即与相似。

一、如何保证2？

数据集内表现相同的多个假设在数据集外的部分数据上表现相差极大，即学习效果极差。

图1.1 数据集内外表现的差异

霍夫丁不等式：有一个装有绿色小球和橘色小球的罐子（假设球数无限），从中进行次有放回的取球实验，在这次实验中取出橘色小球的频率为，只要足够大，就可以用来估计即罐子中橘色小球的实际概率。

图1.2 霍夫丁不等式1
图1.3 霍夫丁不等式2

将霍夫丁不等式与学习相联系。当选定时，只要里样本数足够大且样本点独立同分布，就能保证在整个输入空间里的表现（异常点的概率）与数据集内的表现（里异常点的频率）在一定的概率范围内近似相等。

图1.4 与学习过程的联系

注意，实际是面向整个输入空间的，即数据集内和数据集外。

图1.5 数据集内外表现的联系
图1.6 h与f概率近似相等

二、如何保证1？

根据在中选出使得小的。

图2.1 h的选择

注意，2的保证是在给定的情况下，即的选择只有1个。
但是，1的保证需要在中进行选择，如果的，即有很多个，可能有限也可能无限，那么2的保证是否会受到影响呢？
坏数据：对于一个，使得在该数据内外表现差异很大的数据认为是坏数据。
可以理解为霍夫丁不等式的左式中概率衡量的事件：和的差异大于容忍度，即对于一个，存在坏数据的概率小于等于霍夫丁的右式。
对于一个输入空间，能够产生的用于训练的数据有很多个，若对于一个，给定的数据刚好就是坏数据的概率是小于等于霍夫丁的右式的；若有个，给定的数据是其中某个的坏数据的概率是小于等于数据为的坏数据的概率+数据为的坏数据的概率+数据为的坏数据的概率+......+数据为的坏数据的概率。本质是求并集（小于等于的原因是有可能存在交集）。这里的实际是，即的。

图2.2 坏数据
图2.3 坏数据出现的概率上限

只要是有限值、足够大，不等式的右式就能足够小。
所以，
只要假设集大小有限、足够大 ------ 保证和的差异在容忍度内，
根据在中挑选出 ------ 保证小，
就能说学习是PAC可能的。

图2.4 统计学习流程

但是，如果输入空间是无限的，那理论上对应的的数量也是无限的，即当无限大时，该怎么办呢？