摘要：在学习机器学习前，我们引入 PAC 学习理论，该理论阐明了什么样的问题是可以被机器学习的. 而在介绍该理论之前，我们需要先搭建学习模型的基本框架，以建立机器学习与数学间的联系.
在学习机器学习前，我们引入 PAC 学习理论，该理论阐明了什么样的问题是可以被机器学习的. 而在介绍该理论之前，我们需要先搭建学习模型的基本框架，以建立机器学习与数学间的联系.
以监督学习为例，记 样本空间 X \mathcal{X} X 是由我们希望为其标注标签的全体点构成的集合；标记空间 Y \mathcal{Y} Y 是所有可能的标签构成的集合，学习模型的输入是一个多重集合 S = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x m , y m ) } ⊂ X × Y \mathcal{S} = { (\boldsymbol{x}_1, \space y_1), \space (\boldsymbol{x}_2, \space y_2), \space \dots, \space (\boldsymbol{x}_m, \space y_m) } \subset \mathcal{X} \times \m # # # # # #athcal{Y} S = {( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x m , y m )} ⊂ X × Y ，称为 训练集 .
Remark：\color{brown}{\textbf{Remark：}} Remark ：上述定义表明，训练集 S \mathcal{S} S 可包含重复的数据，也可包含若干样本点相同但标签不同的数据.
Example：\color{brown}{\textbf{Example：}} Example ：假设学习的目标是判断一个木瓜是否好吃，我们可以选择木瓜的颜色和软硬程度两个属性描述木瓜. 将木瓜的这两个属性映射到实数集 R \mathbb{R} R 上，便可以用一个二维向量 ( x 1 , x 2 ) (x_1, \space x_2) ( x 1 , x 2 ) 来描述一个木瓜，称为木瓜的 特征向量 . 此时样本空间定义为 X = R 2 \mathcal{X} = \mathbb{R}^2 X = R 2 ，标记空间可记为 Y = { 0 , 1 } \mathcal{Y} = {0, \space 1} Y = { 0 , 1 } ，其中 0 0 0 表示不好吃，1 1 1 表示好吃. 任意多重集合 S ⊂ X × Y \mathcal{S} \subset \mathcal{X} \times \mathcal{Y} S ⊂ X × Y 是一组训练集. “样本点相同但标签不同的数据”可以解释为当两个木瓜具有相同的属性时，其中一个好吃，另一个不好吃.
学习模型的输出称为 假设 ，一个假设是指一个映射 h : X → Y h: \mathcal{X} \rightarrow \mathcal{Y} h : X → Y ，对任意的 x ∈ X \boldsymbol{x} \in \mathcal{X} x ∈ X ，h ( x ) h(\boldsymbol{x}) h ( x ) 是学习模型对样本 x \boldsymbol{x} x 的标签预测.
假设实际上是对 概念 的近似，一个 概念 是指一个映射 c : X → Y c : \mathcal{X} \rightarrow \mathcal{Y} c : X → Y ，其代表了样本空间与标记空间的真实对应关系（在本文中我们假设这样的 c c c 存在，在以后我们将放宽该假设），假设 c c c 是我们希望学习到的“规律”. 概念的全体称为 概念类 ，记作 C \mathcal{C} C .
对学习模型的评估主要体现为对模型输出的假设的正确性评估，亦即学习模型的正确性是 h ( x ) = c ( x ) h(\boldsymbol{x}) = c(\boldsymbol{x}) h ( x ) = c ( x ) 的概率（不妨设 C = { c } \mathcal{C} = {c} C = { c } 是单点集）. 换句话说，学习模型的 误差 是 h ( x ) ≠ c ( x ) h(\boldsymbol{x}) \not= c(\boldsymbol{x}) h ( x ) = c ( x ) 的概率. 以二分类问题为例（即：Y = { 0 , 1 } \mathcal{Y} = { 0, \space 1} Y = { 0 , 1 } ），定义假设 h h h 的 泛化误差 为：
L D , c ( h ) = P x ∼ D [ h ( x ) ≠ c ( x ) ] , \begin{equation} L_{\mathcal{D}, c}(h) = \mathbb{P}_{\boldsymbol{x} \sim \mathcal{D}} \left[ h(\boldsymbol{x}) \not= c(\boldsymbol{x}) \right], \end{equation} L D , c ( h ) = P x ∼ D [ h ( x ) = c ( x ) ] ,
其中 D \mathcal{D} D 是样本空间 X \mathcal{X} X 的分布，下标 ( D , c ) (\mathcal{D}, \space c) ( D , c ) 表示泛化误差与样本空间的分布与概念有关，后续我们将省略该下标.
在实际应用中，我们并不清楚数据的真实分布 D \mathcal{D} D 和概念 c c c ，学习模型并不能直接计算出 L D , c ( h ) L_{\mathcal{D}, c}(h) L D , c ( h ) . 因此我们将目光从 ( D , c ) (\mathcal{D}, \space c) ( D , c ) 转移到 S \mathcal{S} S 上：由于 S \mathcal{S} S 中的样本是从 D \mathcal{D} D 中独立同分布取得的，且 c ( x i ) = y i c(\boldsymbol{x}_i) = y_i c ( x i ) = y i ，我们可以通过训练集来估计泛化误差. 定义假设 h h h 的 经验误差 为：
L S ( h ) = 1 m ∑ i = 1 m I [ h ( x i ) ≠ c ( x i ) ] . \begin{equation} L_{\mathcal{S}}(h) = \frac{1}{m}\sum\limits_{i = 1}^{m} \mathbb{I}\left[ h(\boldsymbol{x}_i) \not= c(\boldsymbol{x}_i) \right]. \end{equation} L S ( h ) = m 1 i = 1 ∑ m I [ h ( x i ) = c ( x i ) ] .
其中 m = ∣ S ∣ m = | \mathcal{S} | m = ∣ S ∣ ，下同. 容易证明成立 E [ L S ( h ) ] = L D , c ( h ) \mathbb{E}\left[ L_{\mathcal{S}}(h) \right] = L_{\mathcal{D}, c}(h) E [ L S ( h ) ] = L D , c ( h ) ，这说明泛化误差是经验误差的期望，经验误差是泛化误差的无偏估计. 通过最小化 L S ( h ) L_{\mathcal{S}}(h) L S ( h ) 获得最优假设 h h h 的过程称为 经验风险最小化 （Empirical Risk Minimization, ERM）. 形式上记为：
E R M ( S ) = arg min h L S ( h ) . \begin{equation} \mathrm{ERM}(\mathcal{S}) = \arg\min\limits_{h} L_{\mathcal{S}}(h). \end{equation} ERM ( S ) = ar g h min L S ( h ) .
最后，我们补充说明：对于任意两个假设 h 1 , h 2 h_1, \space h_2 h 1 , h 2 ，其之间的差别可用下式衡量：
d ( h 1 , h 2 ) = P x ∼ D [ h 1 ( x ) ≠ h 2 ( x ) ] . \begin{equation} d(h_1, \space h_2) = \mathbb{P}_{\boldsymbol{x} \sim \mathcal{D}}\left[ h_1(\boldsymbol{x}) \not= h_2(\boldsymbol{x}) \right]. \end{equation} d ( h 1 , h 2 ) = P x ∼ D [ h 1 ( x ) = h 2 ( x ) ] .
尽管 E R M \mathrm{ERM} ERM 看似合理，但在某些情况下，由 E R M \mathrm{ERM} ERM 得到的假设也会失败.
Example：\color{brown}{\textbf{Example：}} Example ：仍然考虑前文提到的木瓜分类问题，考虑如下预测：
h S ( x ) = { y i , ∃ i ∈ [ m ] , s.t. x = x i 0 , otherwise . \begin{equation} h_{\mathcal{S}}(\boldsymbol{x}) = \begin{cases} y_i, & \exist \space i \in [m], \text{ s.t. } \boldsymbol{x} = \boldsymbol{x}_i \ 0, & \text{otherwise} \end{cases}. \end{equation} h S ( x ) = { y i , 0 , ∃ i ∈ [ m ] , s.t. x = x i otherwise .
虽然对任意样本 S \mathcal{S} S ，成立 L S ( h S ) = 0 L_{\mathcal{S}}(h_{\mathcal{S}}) = 0 L S ( h S ) = 0 （这使得 E R M \mathrm{ERM} ERM 很有可能返回 h S h_{\mathcal{S}} h S ），但是 h S h_{\mathcal{S}} h S 在实际应用中不一定很理想（即 L D , c ( h S ) L_{\mathcal{D}, c}(h_{\mathcal{S}}) L D , c ( h S ) 可能很大），导致学习的效果较差. 这样的情况称为 过拟合 .
Remark：\color{brown}{\textbf{Remark：}} Remark ：上式定义的 h S ( x ) h_{\mathcal{S}}(\boldsymbol{x}) h S ( x ) 带有明显的“人工痕迹”. 事实上，若定义 p ( x ) = − ∏ y i = 1 ∥ x − x i ∥ 1 p(\boldsymbol{x}) = -\prod\limits_{y_i = 1} \parallel \boldsymbol{x} - \boldsymbol{x}i \parallel_1 p ( x ) = − y i = 1 ∏ ∥ x − x i ∥ 1 ，则 h S ( x ) = 1 h}(\boldsymbol{x}) = 1 h S ( x ) = 1 当且仅当 p ( x ) ≥ 0 p(\boldsymbol{x}) \geq 0 p ( x ) ≥ 0 . 这样定义的假设 h S ′ ( x ) = I [ p ( x ) ≥ 0 ] h'_{\mathcal{S}}(\boldsymbol{x}) = \mathbb{I}[p(\boldsymbol{x}) \geq 0] h S ′ ( x ) = I [ p ( x ) ≥ 0 ] 则十分自然，这也表明若使用全体多项式作为待选假设，E R M \mathrm{ERM} ERM 可能导致过拟合.
尽管 E R M \mathrm{ERM} ERM 可能导致过拟合，但相较于抛弃 E R M \mathrm{ERM} ERM ，更好的选择是对其进行修正. 我们可以预先为学习模型指定一个可选择的假设集合 H = { h } \mathcal{H} = {h} H = { h } ，称为 假设空间 . 对于给定的训练集 S \mathcal{S} S 和假设空间 H \mathcal{H} H ，E R M H \mathrm{ERM}_{\mathcal{H}} ERM H 要求在 H \mathcal{H} H 中寻找经验误差最小的假设，形式上记为：
E R M H ( S ) = arg min h ∈ H L S ( h ) . \begin{equation} \mathrm{ERM}{\mathcal{H}}(\mathcal{S}) = \arg\min\limits}} L_{\mathcal{S}}(h). \end{equation} ERM H ( S ) = ar g h ∈ H min L S ( h ) .
E R M H \mathrm{ERM}_{\mathcal{H}} ERM H 称为 带归纳偏置的经验风险最小化 （ERM with Inductive Bias）.
Example：\color{brown}{\textbf{Example：}} Example ：对于木瓜分类问题，我们可以选择 R 2 \mathbb{R}^2 R 2 下的矩形 [ a , b ] × [ c , d ] [a, \space b] \times [c, \space d] [ a , b ] × [ c , d ] 作为 假设空间 ：将矩形中的样本标记为 1 1 1 ，将其它的样本标记为 0 0 0 . 这样，我们更倾向于在一个特别的假设集合中选取合理的假设，可以在一定程度上避免过拟合.
显然，E R M H \mathrm{ERM}_{\mathcal{H}} ERM H 仍然不足以防止过拟合. 在学习理论中，一个基本的问题是：选择哪种假设空间不会导致过拟合？本系列博客将在后续章节中探讨该问题.
设假设空间为 H \mathcal{H} H ，概率近似学习理论 （PAC 学习理论，Probably Approximately Correct）关注的核心问题是：一个学习算法 L \mathfrak{L} L 好不好？要解决该问题，首先要定义什么是“好”的学习算法，我们依次从以下两个角度考虑：
算法返回的假设要否近似正确 ：算法得到的假设 h h h 的泛化误差要尽可能小，即：当给定 ε > 0 \varepsilon > 0 ε > 0 时，要求 L D , c ( h ) ≤ ε L_{\mathcal{D}, c}(h) \leq \varepsilon L D , c ( h ) ≤ ε ，我们称这样的假设是一个近似正确的假设；算法能以一定概率返回近似正确的假设 ：算法能以一定的概率下返回近似正确假设，即：对给定 δ ∈ ( 0 , 1 ) \delta \in (0, 1) δ ∈ ( 0 , 1 ) ，成立 P [ L D , c ( h ) ≤ ε ] ≥ 1 − δ \mathbb{P} \left[ L_{\mathcal{D}, c}(h) \leq \varepsilon \right] \geq 1 - \delta P [ L D , c ( h ) ≤ ε ] ≥ 1 − δ .Remark：\color{brown}{\textbf{Remark：}} Remark ：我们对第二点作进一步说明：E R M \mathrm{ERM} ERM 规则返回的假设 h h h 依赖于训练集 S \mathcal{S} S ，而 S \mathcal{S} S 可能对于分布 D \mathcal{D} D 不具有代表性（在 E R M H \mathrm{ERM}_{\mathcal{H}} ERM H 下，这会导致过拟合），使得算法难以返回近似正确的假设. 一般地，我们记训练集不具有代表性的概率为 δ \delta δ ，称 1 − δ 1 - \delta 1 − δ 为 置信参数 .
Example：\color{brown}{\textbf{Example：}} Example ：在木瓜的例子中，若训练集选取的木瓜都是深黄色且软烂的，学习模型便难以预测青色或较硬的木瓜是否好吃，这很容易导致学习模型返回的假设的泛化误差较大.
根据上述讨论，我们给出 PAC 辨识 的定义：
Def 1.1 PAC 辨识（PAC Identify）: \color{blue}{\textbf{Def 1.1 PAC 辨识（PAC Identify）: }} Def 1.1 PAC 辨识（ PAC Identify ） : 对给定的 0
P [ L D , c ( h ) ≤ ε ] ≥ 1 − δ , \begin{equation} \mathbb{P} \left[ L_{\mathcal{D}, c}(h) \leq \varepsilon \right] \geq 1 -
\end{equation} P [ L D , c ( h ) ≤ ε ] ≥ 1 − δ ,
则称学习算法 L \mathfrak{L} L 能从假设空间 H \mathcal{H} H 中 PAC 辨识 概念类 C \mathcal{C} C .
PAC 辨识保证了学习算法 L \mathfrak{L} L 能以较高概率（不小于 1 − δ 1 - \delta 1 − δ ）学得概念 c c c 的近似假设（误差至多为 ε \varepsilon ε ，称为 精度参数 ）.
接下来，我们要明晰概念类 C \mathcal{C} C 能否被学习算法 L \mathfrak{L} L 习得，我们给出 PAC 可学习 的定义：
Def 1.2 PAC 可学习（PAC Learnable）: \color{blue}{\textbf{Def 1.2 PAC 可学习（PAC Learnable）: }} Def 1.2 PAC 可学习（ PAC Learnable ） : 对 0 PAC 可学习 的.
多项式 m : ( 0 , 1 ) 2 → N m: (0, 1)^2 \rightarrow \mathbb{N} m : ( 0 , 1 ) 2 → N 决定了训练集的 采样复杂度 ，即保证学习模型返回概率近似正确假设所需的样本数量. 以下给出最简单的情况：当概念 c ∈ H c \in \mathcal{H} c ∈ H 且 ∣ H ∣
Proof：\color{brown}{\textbf{Proof：}} Proof ：既然有 c ∈ H c \in \mathcal{H} c ∈ H ，那么只需在算法中淘汰掉 H \mathcal{H} H 中与训练集 S \mathcal{S} S 不能完美匹配的假设，直至 H \mathcal{H} H 中仅剩一个假设，即得到 c c c . 通常情况下，由于训练集规模有限，假设空间中可能不止一个与 S \mathcal{S} S 匹配，且上述算法无法区分这些假设的优劣. 于是，我们要讨论的问题转换为：究竟需要多大规模的训练集，才能保证 c c c 是可以被以不小于 1 − δ 1 - \delta 1 − δ 的概率筛选出来？只需使：
P [ h ∈ H : L D , c ( h ) > ε ∧ L S ( h ) = 0 ] \varepsilon \land L_{\mathcal{S}}(h) = 0 \right] ε ∧ L S ( h ) = 0 ]
假设 h h h 的泛化误差大于 ε \varepsilon ε ，对分布 D \mathcal{D} D 上随机采样得到的任何样例 ( x , y ) (\boldsymbol{x}, y) ( x , y ) ，有：
P [ h ( x ) = y ] = 1 − P [ h ( x ) ≠ y ] = 1 − L D , c ( h )
\end{align} P [ h ( x ) = y ] = 1 − P [ h ( x ) = y ] = 1 − L D , c ( h )
故 h h h 在 S \mathcal{S} S 上表现完美的概率为：
P [ L S ( h ) = 0 ] = P [ h ( x i ) = y i , ∀ ( x i , y i ) ∈ S ] = ( P [ h ( x ) = y ] ) m
\end{align} P [ L S ( h ) = 0 ] = P [ h ( x i ) = y i , ∀ ( x i , y i ) ∈ S ] = ( P [ h ( x ) = y ] ) m
因此有：
P [ h ∈ H : L D , c ( h ) > ε ∧ L S ( h ) = 0 ] \varepsilon \land L_{\mathcal{S}}(h) = 0 \right]
\end{equation} P [ h ∈ H : L D , c ( h ) > ε ∧ L S ( h ) = 0 ]
令不等式右侧不大于 δ \delta δ ，得：
m ≥ 1 ε ( ln ∣ H ∣ +
m \geq \dfrac{1}{\varepsilon} \left( \ln \vert \mathcal{H} \vert +
\end{equation} m ≥ ε 1 ( ln ∣ H ∣ + ln δ 1 ) .
由此可见，概念 c c c 是 PAC 可学习的. □ \square □
在实际生活中，c ∈ H c \in \mathcal{H} c ∈ H 一般不成立. 我们需要对该过程进行进一步讨论（这里我们仍然认为 ∣ H ∣
Lem 1.3 Hoeffding 不等式: \color{blue}{\textbf{Lem 1.3 Hoeffding 不等式: }} Lem 1.3 Hoeffding 不等式 : 设 X 1 , X 2 , … , X n X_1, \space X_2, \space \dots, \space X_n X 1 , X 2 , … , X n 是独立同分布的随机变量，其中 X i ∈ [ a i , b i ] , i = 1 , 2 , … , n X_i \in [a_i, b_i], \space i = 1, \space 2, \space \dots, \space n X i ∈ [ a i , b i ] , i = 1 , 2 , … , n . 记这些随机变量的均值为 X ‾ = 1 n ∑ i = 1 n X i \overline{X} = \frac{1}{n}\sum\limits_{i = 1}^{n} X_i X = n 1 i = 1 ∑ n X i ，则对任意 ε > 0 \varepsilon > 0 ε > 0 ，成立：
P ( ∣ X ‾ − E ( X ‾ ) ∣ ≥ ε ) ≤ 2 exp ( − 2 ε 2 n 2 ∑ i = 1 n ( b i − a i ) 2 ) . \begin{equation} \mathbb{P} \left( \vert \overline{X} -
\end{equation} P ( ∣ X − E ( X ) ∣ ≥ ε ) ≤ 2 exp − i = 1 ∑ n ( b i − a i ) 2 2 ε 2 n 2 .
对于 PAC 学习理论，固定 h h h ，将 X ‾ = L S ( h ) \overline{X} = L_{\mathcal{S}}(h) X = L S ( h ) ，E ( X ‾ ) = L D , c ( h ) \mathbb{E} (\overline{X}) = L_{\mathcal{D}, c}(h) E ( X ) = L D , c ( h ) ，a i = 0 , b i = 1 ( i = 1 , 2 , … , n ) a_i = 0, \space b_i = 1 \space (i = 1, 2, \dots, n) a i = 0 , b i = 1 ( i = 1 , 2 , … , n ) 代入，得：
P ( ∣ L S ( h ) − L D , c ( h ) ∣ ≥ ε ) ≤ 2 exp ( − 2 m ε 2 ) . \begin{equation} \mathbb{P} \left( \vert L_{\mathcal{S}}(h) -
\end{equation} P ( ∣ L S ( h ) − L D , c ( h ) ∣ ≥ ε ) ≤ 2 exp ( − 2 m ε 2 ) .
类似前文的讨论，考虑：
P [ h ∈ H : ∣ L S ( h ) − L D , c ( h ) ∣ ≥ ε ] ≤ 2 ∣ H ∣ exp ( − 2 m ε 2 ) . \begin{equation} \mathbb{P}\left[ h \in \mathcal{H} : \vert L_{\mathcal{S}}(h) -
\end{equation} P [ h ∈ H : ∣ L S ( h ) − L D , c ( h ) ∣ ≥ ε ] ≤ 2∣ H ∣ exp ( − 2 m ε 2 ) .
令不等式右侧等于 δ \delta δ ，有：
ε = ln ∣ H ∣ +
\varepsilon = \sqrt{\frac{\ln \vert \mathcal{H} \vert +
\end{equation} ε = 2 m ln ∣ H ∣ + ln ( δ /2 ) ,
从而有：
P ( ∣ L S ( h ) − L D , c ( h ) ∣ ≤ ln ∣ H ∣ +
\mathbb{P} \left( \vert L_{\mathcal{S}}(h) -
\end{equation} P ( ∣ L S ( h ) − L D , c ( h ) ∣ ≤ 2 m ln ∣ H ∣ + ln ( δ /2 ) ) ≥ 1 − δ .
在上述推导中，我们并未给出也无法给出 P [ L D , c ( h ) ≤ ε ] \mathbb{P} \left[ L_{\mathcal{D}, c}(h) \leq \varepsilon \right] P [ L D , c ( h ) ≤ ε ] 的度量，但是当假设空间 H \mathcal{H} H 给定且有限时，其中必存在一个泛化误差最小的假设. 我们只需要找出该假设的近似假设即可，以此为目标的学习称为 不可知 PAC 可学习 .
Def 1.4 不可知 PAC 可学习（Agnostic PAC Learnable）: \color{blue}{\textbf{Def 1.4 不可知 PAC 可学习（Agnostic PAC Learnable）: }} Def 1.4 不可知 PAC 可学习（ Agnostic PAC Learnable ） : 对 0
P [ L D , c ( h ) − min h ′ ∈ H L D , c ( h ′ ) ≤ ε ] ≥ 1 − δ , \begin{equation} \mathbb{P} \left[ L_{\mathcal{D}, c}(h) -
\end{equation} P [ L D , c ( h ) − h ′ ∈ H min L D , c ( h ′ ) ≤ ε ] ≥ 1 − δ ,
则称概念类 C \mathcal{C} C 对假设空间 H \mathcal{H} H 是 不可知 PAC 可学习 的.
显然，PAC 可学习是不可知 PAC 可学习的特例（前者满足 min h ′ ∈ H L D , c ( h ′ ) = 0 \min\limits_{h' \in \mathcal{H}} L_{\mathcal{D}, c}(h') = 0 h ′ ∈ H min L D , c ( h ′ ) = 0 ）. 下面说明有限假设空间下概念类 C \mathcal{C} C 一定是不可知 PAC 可学习的.
Proof：\color{brown}{\textbf{Proof：}} Proof ：将 1 2 ε \frac{1}{2}\varepsilon 2 1 ε 代入式 ( 15 ) (15) ( 15 ) ，有：
P ( h ∈ H : ∣ L S ( h ) − L D , c ( h ) ∣ ≥ 1 2 ε ) ≤ 2 ∣ H ∣ exp ( − m ε 2 2 ) . \begin{equation} \mathbb{P} \left( h \in \mathcal{H} : \vert L_{\mathcal{S}}(h) -
\end{equation} P ( h ∈ H : ∣ L S ( h ) − L D , c ( h ) ∣ ≥ 2 1 ε ) ≤ 2∣ H ∣ exp ( − 2 m ε 2 ) .
记 h ∗ = arg min h ′ ∈ H L D , c ( h ′ ) h^ = \arg\min\limits_{h' \in \mathcal{H}} L_{\mathcal{D}, c}(h') h ∗ = ar g h ′ ∈ H min L D , c ( h ′ ) ，学习算法返回的假设为 h S h_{\mathcal{S}} h S ；记 ∣ L S ( h S ) − L D , c ( h S ) ∣ ≤ 1 2 ε \vert L_{\mathcal{S}}(h_{\mathcal{S}}) - L_{\mathcal{D}, c}(h_{\mathcal{S}}) \vert \leq \frac{1}{2} \varepsilon ∣ L S ( h S ) − L D , c ( h S ) ∣ ≤ 2 1 ε 为事件 A A A ，∣ L S ( h ∗ ) − L D , c ( h ∗ ) ∣ ≤ 1 2 ε \vert L_{\mathcal{S}}(h^) - L_{\mathcal{D}, c}(h^*) \vert \leq \frac{1}{2} \varepsilon ∣ L S ( h ∗ ) − L D , c ( h ∗ ) ∣ ≤ 2 1 ε 为事件 B B B ，则由 E R M \mathrm{ERM} ERM 规则可知，当 A A A 和 B B B 同时成立时：
L D , c ( h ∗ ) ≤ L D , c ( h S ) ≤ L S ( h S ) +
L_{\mathcal{D}, c}(h^*) \leq L_{\mathcal{D}, c}(h_{\mathcal{S}}) \leq L_{\mathcal{S}}(h_{\mathcal{S}}) +
\end{equation} L D , c ( h ∗ ) ≤ L D , c ( h S ) ≤ L S ( h S ) + 2 1 ε ≤ L S ( h ∗ ) + 2 1 ε ≤ L D , c ( h ∗ ) + ε .
由 P ( A ‾ ∪ B ‾ ) ≥ 0 \mathbb{P}(\overline{A} \cup \overline{B}) \geq 0 P ( A ∪ B ) ≥ 0 及 P ( A ‾ ) , P ( B ‾ ) ≤ 2 ∣ H ∣ exp ( − m ε 2 2 ) \mathbb{P}(\overline{A}), \space \mathbb{P}(\overline{B}) \leq 2 \vert \mathcal{H} \vert \exp\left( -\frac{m\varepsilon^2}{2} \right) P ( A ) , P ( B ) ≤ 2∣ H ∣ exp ( − 2 m ε 2 ) 可得：
P [ L D , c ( h S ) − L D , c ( h ∗ ) ≤ ε ] ≥ 1 − P ( A B ‾ ) = 1 +
\mathbb{P} \left[ L_{\mathcal{D}, c}(h_{\mathcal{S}}) -
\end{equation} P [ L D , c ( h S ) − L D , c ( h ∗ ) ≤ ε ] ≥ 1 − P ( A B ) = 1 + P ( A ∪ B ) − P ( A ) − P ( B ) ≥ 1 − 4∣ H ∣ exp ( − 2 m ε 2 ) ,
或等价地：
P [ L D , c ( h S ) − L D , c ( h ∗ ) ≥ ε ] ≤ 4 ∣ H ∣ exp ( − m ε 2 2 ) , \begin{equation} \mathbb{P} \left[ L_{\mathcal{D}, c}(h_{\mathcal{S}}) -
\end{equation} P [ L D , c ( h S ) − L D , c ( h ∗ ) ≥ ε ] ≤ 4∣ H ∣ exp ( − 2 m ε 2 ) ,
令不等式右边小于 δ \delta δ ，有：
m ≥ 2 ε 2 ( ln ( 4 ∣ H ∣ ) +
m \geq \frac{2}{\varepsilon^2} \left( \ln \left( 4\vert \mathcal{H} \vert \right) +
\end{equation} m ≥ ε 2 2 ( ln ( 4∣ H ∣ ) + ln δ 1 ) . □
综合上述讨论，我们给出如下结论：
Thm 1.5 有限假设空间是不可知 PAC 可学习的: \color{blue}{\textbf{Thm 1.5 有限假设空间是不可知 PAC 可学习的: }} Thm 1.5 有限假设空间是不可知 PAC 可学习的 : 假设空间 H \mathcal{H} H 是有限维的，当 c ∈ H c \in \mathcal{H} c ∈ H 时称假设空间 H \mathcal{H} H 是 可分的 ；否则称假设空间 H \mathcal{H} H 是 不可分的 . 当 H \mathcal{H} H 可分时，概念类 C \mathcal{C} C 一定是 PAC 可学习的（当然也是不可知 PAC 可学习的）；当 H \mathcal{H} H 不可分时，概念类 C \mathcal{C} C 一定是（退化为）不可知 PAC 可学习的.
截至目前，我们以二分类问题为例，在概念 c c c 存在的基础上给出了 PAC 可学习和不可知 PAC 可学习的定义，并且指出有限假设空间都是不可知 PAC 可学习的. 接下来，我们对该理论进行推广.
首先，我们考虑去除掉对概念 c c c 的依赖. 这样的操作是合理的，因为在现实生活中，样本与标签的对应关系往往并非确定性映射，而是概率性的对应关系.
Example：\color{brown}{\textbf{Example：}} Example ：在木瓜的例子中，具有同样属性的木瓜可能好吃也可能不好吃，“规律”实际应该表示在该属性下，木瓜好吃的概率和不好吃的概率，而非确定性的“木瓜要么好吃，要么不好吃”.
我们将样本空间的分布 D \mathcal{D} D 记为 D x \mathcal{D}_{\boldsymbol{x}} D x ，将 X × Y \mathcal{X} \times \mathcal{Y} X × Y 上的分布重新记为 D \mathcal{D} D ，称为样本空间和标记空间的 联合分布 . 在此基础上，我们重新定义假设 h h h 的泛化误差：
L D ( h ) = P ( x , y ) ∼ D [ h ( x ) ≠ y ] . \begin{equation} L_{\mathcal{D}}(h) = \mathbb{P}_{(\boldsymbol{x}, y) \sim \mathcal{D}} \left[ h(\boldsymbol{x}) \not= y \right]. \end{equation} L D ( h ) = P ( x , y ) ∼ D [ h ( x ) = y ] .
假设 h h h 的经验误差定义不变. 我们可将上述定义的 PAC 可辨识、PAC 可学习及不可知 PAC 可学习中的 L D , c L_{\mathcal{D}, c} L D , c 替换为 L D L_{\mathcal{D}} L D ，且仍然可以证明有限假设空间是不可知 PAC 可学习的.
其次，我们考虑将二分类的限定推广至多分类和回归问题，这需要我们进一步推广误差函数. 对于给定假设空间 H \mathcal{H} H 和定义域 Z \mathcal{Z} Z ，称 l : H × Z → R + \mathscr{l}: \mathcal{H} \times \mathcal{Z} \rightarrow \mathbb{R}_+ l : H × Z → R + 为问题的一个 损失函数 . 对于多分类问题，Z = X × Y \mathcal{Z} = \mathcal{X} \times \mathcal{Y} Z = X × Y ；对于回归问题，Z = X × R \mathcal{Z} = \mathcal{X} \times \mathbb{R} Z = X × R . 定义假设 h h h 的泛化误差与经验误差为：
L D ( h ) = E z ∼ D [ l ( h , z ) ] , L S ( h ) = 1 m ∑ i = 1 m l ( h , z ) . \begin{align} L_{\mathcal{D}}(h) &= \mathbb{E}{\boldsymbol{z} \sim \mathcal{D}} \left[ \mathscr{l}(h, \boldsymbol{z}) \right], \nonumber \ L}(h) &= \frac{1}{m} \sum\limits_{i = 1}^{m} \mathscr{l}(h, \boldsymbol{z}). \end{align} L D ( h ) L S ( h ) = E z ∼ D [ l ( h , z ) ] , = m 1 i = 1 ∑ m l ( h , z ) .
在分类问题和回归问题中，损失函数通常分别采用以下两种形式：
0 − 1 0-1 0 − 1 损失 ： Z = X × Y \mathcal{Z} = \mathcal{X} \times \mathcal{Y} Z = X × Y ，损失函数为： l 0 − 1 ( h , ( x , y ) ) = I ( h ( x ) ≠ y ) \mathscr{l}_{0-1}\left( h, (\boldsymbol{x}, y) \right) = \mathbb{I}(h(\boldsymbol{x}) \not= y) l 0 − 1 ( h , ( x , y ) ) = I ( h ( x ) = y ) ；平方损失 ： Z = X × R \mathcal{Z} = \mathcal{X} \times \mathbb{R} Z = X × R ，损失函数为： l s q ( h , ( x , y ) ) = ( h ( x ) − y ) 2 \mathscr{l}_{\mathrm{sq}}\left( h, (\boldsymbol{x}, y) \right) = \left( h(\boldsymbol{x}) - y \right)^2 l sq ( h , ( x , y ) ) = ( h ( x ) − y ) 2 .在此基础上，我们可以进一步推广 PAC 可学习及不可知 PAC 可学习的定义：
Def 1.2’ PAC 可学习（PAC Learnable）: \color{blue}{\textbf{Def 1.2' PAC 可学习（PAC Learnable）: }} Def 1.2’ PAC 可学习（ PAC Learnable ） : Q \mathfrak{Q} Q 是一个学习问题，若对任意给定的 0
P [ L D ( h ) ≤ ε ] ≥ 1 − δ , \begin{equation} \mathbb{P} \left[ L_{\mathcal{D}}(h) \leq \varepsilon \right] \geq 1 -
\end{equation} P [ L D ( h ) ≤ ε ] ≥ 1 − δ ,
则称问题 Q \mathfrak{Q} Q 对假设空间 H \mathcal{H} H 是 PAC 可学习 的.
Def 1.4’ 不可知 PAC 可学习（Agnostic PAC Learnable）: \color{blue}{\textbf{Def 1.4' 不可知 PAC 可学习（Agnostic PAC Learnable）: }} Def 1.4’ 不可知 PAC 可学习（ Agnostic PAC Learnable ） : Q \mathfrak{Q} Q 是一个学习问题，若对任意给定的 0
P [ L D ( h ) − min h ′ ∈ H L D ( h ′ ) ≤ ε ] ≥ 1 − δ , \begin{equation} \mathbb{P} \left[ L_{\mathcal{D}}(h) -
\end{equation} P [ L D ( h ) − h ′ ∈ H min L D ( h ′ ) ≤ ε ] ≥ 1 − δ ,
则称问题 Q \mathfrak{Q} Q 对假设空间 H \mathcal{H} H 是 不可知 PAC 可学习 的.
同样地，我们可以证明无论是多分类问题还是回归问题，有限假设空间都是不可知 PAC 可学习的，这只需注意到前文在证明有限假设空间总是不可知 PAC 可学习时，未使用到 L D L_{\mathcal{D}} L D 和 L S L_{\mathcal{S}} L S 的真实表达式和概念 c c c 的任何信息.
Lem 1.6 Markov 不等式: \color{blue}{\textbf{Lem 1.6 Markov 不等式: }} Lem 1.6 Markov 不等式 : 对任意非负随机变量 X X X 和任意给定实数 ε > 0 \varepsilon > 0 ε > 0 ，有：
P ( X > ε ) ≤ 1 ε E ( X ) . \begin{equation} \mathbb{P}(X > \varepsilon) \leq \dfrac{1}{\varepsilon} \mathbb{E}(X). \end{equation} P ( X > ε ) ≤ ε 1 E ( X ) .
Proof：\color{brown}{\textbf{Proof：}} Proof ：设 X X X 的概率密度函数为 f ( x ) f(x) f ( x ) ，则：
E ( X ) = ∫ 0 +
\mathbb{E}(X) = \int_{0}^{+\infty} x f(x) \mathrm{d}x &\geq \int_{\varepsilon}^{+\infty} x f(x) \mathrm{d}x \nonumber \ &\geq \varepsilon \int_{\varepsilon}^{+\infty} f(x) \mathrm{d}x \nonumber \ &= \varepsilon \mathbb{P}(X \geq \varepsilon). \end{align} E ( X ) = ∫ 0 + ∞ x f ( x ) d x ≥ ∫ ε + ∞ x f ( x ) d x ≥ ε ∫ ε + ∞ f ( x ) d x = ε P ( X ≥ ε ) .
两边同时除以 ε \varepsilon ε 即证. □ \square □
Lem 1.7 Hoeffding 引理: \color{blue}{\textbf{Lem 1.7 Hoeffding 引理: }} Lem 1.7 Hoeffding 引理 : 对任意随机变量 X X X ，若 X ∈ [ a , b ] X \in [a, \space b] X ∈ [ a , b ] 且 E ( X ) = 0 \mathbb{E}(X) = 0 E ( X ) = 0 ，则对任意实数 s s s 成立：
E ( e s X ) ≤ e 1 8 λ 2 ( b − a ) 2 . \begin{equation} \mathbb{E}(\mathrm{e}^{sX}) \leq \mathrm{e}^{\frac{1}{8}\lambda^2(b -
\end{equation} E ( e s X ) ≤ e 8 1 λ 2 ( b − a ) 2 .
Proof：\color{brown}{\textbf{Proof：}} Proof ：记 f ( X ) = e λ X f(X) = \mathrm{e}^{\lambda X} f ( X ) = e λ X ，则 f ′ ′ ( X ) = λ 2 e λ X > 0 f''(X) = \lambda^2\mathrm{e}^{\lambda X} > 0 f ′′ ( X ) = λ 2 e λ X > 0 ，因此 f ( x ) f(x) f ( x ) 是凸函数. 由凸函数性质，令 θ = b − X b − a ∈ ( 0 , 1 ) \theta = \frac{b - X}{b - a} \in (0, \space 1) θ = b − a b − X ∈ ( 0 , 1 ) ：
e λ X = f ( X ) = f ( θ a +
\mathrm{e}^{\lambda X} = f(X) &= f(\theta a + (1 - \theta) b) \geq \theta f(a) + (1 - \theta) f(b) \nonumber \ &= \dfrac{b -
\end{align} e λ X = f ( X ) = f ( θ a + ( 1 − θ ) b ) ≥ θ f ( a ) + ( 1 − θ ) f ( b ) = b − a b − X e λa + b − a X − a e λb ,
对不等式两边同时取期望，得：
E [ e λ X ] = b − E [ X ] b − a e λ a +
\mathbb{E}\left[\mathrm{e}^{\lambda X}\right] = \dfrac{b -
\end{align} E [ e λ X ] = b − a b − E [ X ] e λa + b − a E [ X ] − a e λb = b − a b e λa − a e λb .
只需证明：
b e λ a − a e λ b b − a ≤ e 1 8 λ 2 ( b − a ) 2 ⇔ ln ( b e λ a − a e λ b b − a ) ≤ 1 8 λ 2 ( b − a ) 2 . \begin{equation} \dfrac{b\mathrm{e}^{\lambda a} -
\end{equation} b − a b e λa − a e λb ≤ e 8 1 λ 2 ( b − a ) 2 ⇔ ln ( b − a b e λa − a e λb ) ≤ 8 1 λ 2 ( b − a ) 2 .
令 t = b − a t = b - a t = b − a ，则 b = t + a b = t + a b = t + a ，有：
ln ( b e λ a − a e λ b b − a ) = ln ( ( t +
\ln \left( \dfrac{b\mathrm{e}^{\lambda a} - a\mathrm{e}^{\lambda b}}{b - a} \right) &= \ln \left( \dfrac{(t + a)\mathrm{e}^{\lambda a} - a\mathrm{e}^{\lambda(t + a)}}{t} \right) \nonumber \ &= \lambda a +
\end{align} ln ( b − a b e λa − a e λb ) = ln ( t ( t + a ) e λa − a e λ ( t + a ) ) = λa + ln ( t + a − a e λ t ) − ln t .
记 φ ( u ) = λ a + ln ( t + a − a e u ) − ln t \varphi(u) = \lambda a + \ln \left( t + a - a\mathrm{e}^u \right) - \ln t φ ( u ) = λa + ln ( t + a − a e u ) − ln t ，则对目标不等式的证明等价于证明：
φ ( λ t ) ≤ 1 8 ( λ t ) 2 . \begin{equation} \varphi(\lambda t) \leq \dfrac{1}{8} (\lambda t)^2. \end{equation} φ ( λ t ) ≤ 8 1 ( λ t ) 2 .
易知 φ ∈ C ∞ \varphi \in C^{\infty} φ ∈ C ∞ ，对 φ ( u ) \varphi(u) φ ( u ) 进行二阶 Taylor 展开，得：
φ ( u ) = φ ( 0 ) +
\varphi(u) = \varphi(0) +
\end{equation} φ ( u ) = φ ( 0 ) + φ ′ ( 0 ) u + 2 1 φ ′′ ( α ) u 2 ,
其中 α ∈ ( 0 , u ) \alpha \in (0, \space u) α ∈ ( 0 , u ) ，容易计算：
φ ( 0 ) = λ a +
\varphi(0) &= \lambda a +
\varphi'(0) &= \dfrac{-a\mathrm{e}^{u}}{t +
\varphi''(\alpha) &= \dfrac{-a\mathrm{e}^{u}(t +
\end{align} φ ( 0 ) φ ′ ( 0 ) φ ′′ ( α ) = λa + ln ( t + a − a ) − ln t = λa , = t + a − a e u − a e u u = 0 = − t a , = ( t + a − a e u ) 2 − a e u ( t + α ) u = α = ( t + a − a e u ) 2 − a e u ⋅ ( 1 − ( t + a − a e u ) 2 − a e u ) u = α ≤ 4 1 .
将式 ( 37 ) (37) ( 37 ) 代入式 ( 36 ) (36) ( 36 ) ，得：
φ ( λ t ) ≤ λ a +
\varphi(\lambda t) \leq \lambda a +
\end{equation} φ ( λ t ) ≤ λa + ( − t a ⋅ λ t ) + 2 1 ⋅ 4 1 ( λ t ) 2 = 8 1 ( λ t ) 2 .
综上所述，不等式 ( 30 ) (30) ( 30 ) 得证. □ \square □
Lem 1.3 Hoeffding 不等式: \color{blue}{\textbf{Lem 1.3 Hoeffding 不等式: }} Lem 1.3 Hoeffding 不等式 : 设 X 1 , X 2 , … , X n X_1, \space X_2, \space \dots, \space X_n X 1 , X 2 , … , X n 是独立同分布的随机变量，其中 X i ∈ [ a i , b i ] , i = 1 , 2 , … , n X_i \in [a_i, b_i], \space i = 1, \space 2, \space \dots, \space n X i ∈ [ a i , b i ] , i = 1 , 2 , … , n . 记这些随机变量的均值为 X ‾ = 1 n ∑ i = 1 n X i \overline{X} = \frac{1}{n}\sum\limits_{i = 1}^{n} X_i X = n 1 i = 1 ∑ n X i ，则对任意 ε > 0 \varepsilon > 0 ε > 0 ，成立：
P ( ∣ X ‾ − E ( X ‾ ) ∣ ≥ ε ) ≤ 2 exp ( − 2 ε 2 n 2 ∑ i = 1 n ( b i − a i ) 2 ) . \begin{equation} \mathbb{P} \left( \vert \overline{X} -
\end{equation} P ( ∣ X − E ( X ) ∣ ≥ ε ) ≤ 2 exp − i = 1 ∑ n ( b i − a i ) 2 2 ε 2 n 2 .
Proof：\color{brown}{\textbf{Proof：}} Proof ：由 Markov 不等式，得：
P ( X ‾ − E ( X ‾ ) ≥ ε ) = P [ exp ( λ [ X ‾ − E ( X ‾ ) ] ) ≥ exp ( λ ε ) ] ≤ exp ( − λ ε ) ⋅ E [ exp ( λ [ X ‾ − E ( X ‾ ) ] ) ] , \begin{equation} \mathbb{P}\left( \overline{X} -
= \mathbb{P}\left[ \exp\left(\lambda[\overline{X} -
\leq \exp \left(-\lambda\varepsilon \right) \cdot \mathbb{E}\left[ \exp\left( \lambda[\overline{X} -
\end{equation} P ( X − E ( X ) ≥ ε ) = P [ exp ( λ [ X − E ( X )] ) ≥ exp ( λ ε ) ] ≤ exp ( − λ ε ) ⋅ E [ exp ( λ [ X − E ( X )] ) ] ,
其中：
E [ exp ( λ [ X ‾ − E ( X ‾ ) ] ) ] = ∏ i = 1 n E [ exp ( λ ⋅ X i − E ( X i ) n ) ] . \begin{equation} \mathbb{E}\left[ \exp\left( \lambda[\overline{X} -
\end{equation} E [ exp ( λ [ X − E ( X )] ) ] = i = 1 ∏ n E [ exp ( λ ⋅ n X i − E ( X i ) ) ] .
又因为 E [ X i − E ( X i ) n ] = 0 \mathbb{E}\left[ \frac{X_i - \mathbb{E}(X_i)}{n} \right] = 0 E [ n X i − E ( X i ) ] = 0 ，由 Hoeffding 引理可知：
E [ exp ( λ ⋅ X i − E ( X i ) n ) ] ≤ exp ( λ 2 ⋅ ( b i − a i ) 2 8 n 2 ) . \begin{equation} \mathbb{E}\left[ \exp\left( \lambda \cdot \dfrac{X_i -
\end{equation} E [ exp ( λ ⋅ n X i − E ( X i ) ) ] ≤ exp ( λ 2 ⋅ 8 n 2 ( b i − a i ) 2 ) .
于是有：
P ( X ‾ − E ( X ‾ ) ≥ ε ) ≤ exp ( − λ ε +
\mathbb{P}\left( \overline{X} -
\end{equation} P ( X − E ( X ) ≥ ε ) ≤ exp − λ ε + λ 2 ⋅ 8 n 2 i = 1 ∑ n ( b i − a i ) 2 .
由于式 ( 43 ) (43) ( 43 ) 对任意实数 λ \lambda λ 成立，取 λ 0 \lambda_0 λ 0 使不等式右侧指数项最小，得：
P ( X ‾ − E ( X ‾ ) ≥ ε ) ≤ exp ( − 2 ε 2 n 2 ∑ i = 1 n ( b i − a i ) 2 ) . \begin{equation} \mathbb{P}\left( \overline{X} -
\end{equation} P ( X − E ( X ) ≥ ε ) ≤ exp − i = 1 ∑ n ( b i − a i ) 2 2 ε 2 n 2 .
于是得到：
P ( ∣ X ‾ − E ( X ‾ ) ∣ ≥ ε ) ≤ 2 exp ( − 2 ε 2 n 2 ∑ i = 1 n ( b i − a i ) 2 ) . □ \begin{equation} \mathbb{P} \left( \vert \overline{X} -
\end{equation} P ( ∣ X − E ( X ) ∣ ≥ ε ) ≤ 2 exp − i = 1 ∑ n ( b i − a i ) 2 2 ε 2 n 2 . □
Thm 1.6 Bayes 最优假设: \color{blue}{\textbf{Thm 1.6 Bayes 最优假设: }} Thm 1.6 Bayes 最优假设 : 给定 X × { 0 , 1 } \mathcal{X} \times {0, \space 1} X × { 0 , 1 } 上的任意分布 D \mathcal{D} D ，将 X \mathcal{X} X 映射到 { 0 , 1 } {0, \space 1} { 0 , 1 } 上的最好的假设为：
B a y e s D ( x ) = { 1 , P ( x , y ) ∼ D ( y = 1 ∣ x ) ≥ 1 2 0 , otherwise . \begin{equation} \mathrm{Bayes}{\mathcal{D}}(\boldsymbol{x}) = \begin{cases} 1, & \mathbb{P}, y) \sim \mathcal{D}} \left( y = 1 \mid \boldsymbol{x} \right) \geq \dfrac{1}{2} \ 0, & \text{otherwise} \end{cases}. \end{equation} Bayes D ( x ) = ⎩ ⎨ ⎧ 1 , 0 , P ( x , y ) ∼ D ( y = 1 ∣ x ) ≥ 2 1 otherwise .
Proof：\color{brown}{\textbf{Proof：}} Proof ：设 h h h 是任意 X \mathcal{X} X 到 { 0 , 1 } {0, \space 1} { 0 , 1 } 上的假设，则：
L D ( h ) − L D ( B a y e s D ) = E ( x , y ) ∼ D [ I ( h ( x ) ≠ y ) ] − E ( x , y ) ∼ D [ I ( B a y e s D ( x ) ≠ y ) ] = E x ∼ D x ( E y ∣ x [ I ( h ( x ) ≠ y ) − I ( B a y e s D ( x ) ≠ y ) ] ) . \begin{align} L_{\mathcal{D}}(h) - L_{\mathcal{D}}(\mathrm{Bayes}{\mathcal{D}}) &= \mathbb{E}, y) \sim \mathcal{D}} [\mathbb{I}(h(\boldsymbol{x}) \not= y)] - \mathbb{E}{(\boldsymbol{x}, y) \sim \mathcal{D}} [\mathbb{I}(\mathrm{Bayes}}(\boldsymbol{x}) \not= y)] \nonumber \ &= \mathbb{E}{\boldsymbol{x} \sim\mathcal{D}}} \left( \mathbb{E}_{y \mid \boldsymbol{x}}\left[ \mathbb{I}(h(\boldsymbol{x}) \not= y) -
\end{align} L D ( h ) − L D ( Bayes D ) = E ( x , y ) ∼ D [ I ( h ( x ) = y )] − E ( x , y ) ∼ D [ I ( Bayes D ( x ) = y )] = E x ∼ D x ( E y ∣ x [ I ( h ( x ) = y ) − I ( Bayes D ( x ) = y ) ] ) .
对于任意 x ∈ D x \boldsymbol{x} \in \mathcal{D}_{\boldsymbol{x}} x ∈ D x ，定义：
Δ ( x ) = I ( h ( x ) ≠ y ) − I ( B a y e s D ( x ) ≠ y ) . \begin{equation} \Delta(\boldsymbol{x}) = \mathbb{I}(h(\boldsymbol{x}) \not= y) -
\end{equation} Δ ( x ) = I ( h ( x ) = y ) − I ( Bayes D ( x ) = y ) .
若 h ( x ) = B a y e s D ( x ) h(\boldsymbol{x}) = \mathrm{Bayes}{\mathcal{D}}(\boldsymbol{x}) h ( x ) = Bayes D ( x ) ，则 Δ ( x ) = 0 \Delta(\boldsymbol{x}) = 0 Δ ( x ) = 0 ；否则记 η ( x ) = P ( y = 1 ∣ x ) \eta(\boldsymbol{x}) = \mathbb{P}(y = 1 \mid \boldsymbol{x}) η ( x ) = P ( y = 1 ∣ x ) ，当 η ( x ) ≥ 1 2 \eta(\boldsymbol{x}) \geq \frac{1}{2} η ( x ) ≥ 2 1 时，B a y e s D ( x ) = 1 \mathrm{Bayes}}(\boldsymbol{x}) = 1 Bayes D ( x ) = 1 ，故 h ( x ) = 0 h(\boldsymbol{x}) = 0 h ( x ) = 0 ，有：
I ( h ( x ) ≠ y ) = I ( y = 1 ) , I ( B a y e s D ( x ) ≠ y ) = I ( y = 0 ) ⟹ Δ ( x ) = I ( y = 1 ) − I ( y = 0 ) = η ( x ) − [ 1 − η ( x ) ] = 2 η ( x ) − 1 ≥ 0. \begin{align} &\mathbb{I}(h(\boldsymbol{x}) \not= y) = \mathbb{I}(y = 1), \space \mathbb{I}(\mathrm{Bayes}_{\mathcal{D}}(\boldsymbol{x}) \not= y) = \mathbb{I}(y = 0) \nonumber \ \implies \Delta(\boldsymbol{x}) &= \mathbb{I}(y = 1) -
\end{align} ⟹ Δ ( x ) I ( h ( x ) = y ) = I ( y = 1 ) , I ( Bayes D ( x ) = y ) = I ( y = 0 ) = I ( y = 1 ) − I ( y = 0 ) = η ( x ) − [ 1 − η ( x )] = 2 η ( x ) − 1 ≥ 0.
同理，当 η ( x )
E y ∣ x [ Δ ( x ) ] ≥ 0 , ∀ x ∈ X , \begin{equation} \mathbb{E}_{y \mid \boldsymbol{x}} \left[ \Delta(\boldsymbol{x}) \right] \geq 0, \space \forall \boldsymbol{x} \in \mathcal{X}, \end{equation} E y ∣ x [ Δ ( x ) ] ≥ 0 , ∀ x ∈ X ,
即：
L D ( h ) − L D ( B a y e s D ) ≥ 0.
L_{\mathcal{D}}(h) -
\end{equation} L D ( h ) − L D ( Bayes D ) ≥ 0.
这说明 B a y e s D ( x ) \mathrm{Bayes}_{\mathcal{D}}(\boldsymbol{x}) Bayes D ( x ) 是 X \mathcal{X} X 到 { 0 , 1 } {0, \space 1} { 0 , 1 } 上的最优假设. □ \square □
Remark：\color{brown}{\textbf{Remark：}} Remark ：在实际应用中，由于不清楚真实分布 D \mathcal{D} D ，我们不能直接使用 B a y e s D ( x ) \mathrm{Bayes}_{\mathcal{D}}(\boldsymbol{x}) Bayes D ( x ) .
无限假设空间也可能是 PAC 可学习的，我们分别给出可列假设空间和连续假设空间上的例子：
Example 可列假设空间：\color{brown}{\textbf{Example 可列假设空间：}} Example 可列假设空间：考虑 X \mathcal{X} X 可列，Y = { 0 , 1 } \mathcal{Y} = {0, \space 1} Y = { 0 , 1 } ，令 H = { h z : z ∈ X , h z ( x ) = I ( x = z ) } ∪ { h − ≡ 0 } \mathcal{H} = { h_{\boldsymbol{z}} : \boldsymbol{z} \in \mathcal{X}, \space h_{\boldsymbol{z}}(\boldsymbol{x}) = \mathbb{I}(\boldsymbol{x} = \boldsymbol{z}) } \cup { h^- \equiv 0} H = { h z : z ∈ X , h z ( x ) = I ( x = z )} ∪ { h − ≡ 0 } ，则当 H \mathcal{H} H 可分时，问题是 PAC 可学习的.
Proof：\color{brown}{\textbf{Proof：}} Proof ：根据 E R M \mathrm{ERM} ERM 法则，构建如下算法：若训练集中全部样本点的标记为 0 0 0 ，则返回 h − h^- h − ，否则若存在样本点 z ∗ \boldsymbol{z}^ z ∗ 标记为 1 1 1 ，则返回 h z ∗ h_{\boldsymbol{z}^} h z ∗ . 若最优假设为 h − h^- h − ，算法显然会返回 h − h^- h − ，L D ( h − ) = 0 L_{\mathcal{D}}(h^-) = 0 L D ( h − ) = 0 ，问题是 PAC 可学习的；若最有假设为 h z ∗ h_{\boldsymbol{z}^} h z ∗ ，设取样到 z ∗ \boldsymbol{z}^ z ∗ 的概率为 p p p ，则训练集中不包含 p p p 的概率为 ( 1 − p ) m ≤ e − p m (1 - p)^m \leq \mathrm{e}^{-pm} ( 1 − p ) m ≤ e − p m ，令 e − p m ≤ δ \mathrm{e}^{-pm} \leq \delta e − p m ≤ δ ，得 m ≥ 1 p ln 1 δ m \geq \frac{1}{p} \ln \frac{1}{\delta} m ≥ p 1 ln δ 1 ，因而其也是 PAC 可学习的. □ \square □
Example 连续假设空间：\color{brown}{\textbf{Example 连续假设空间：}} Example 连续假设空间：考虑 X = R 2 \mathcal{X} = \mathbb{R}^2 X = R 2 ，Y = { 0 , 1 } \mathcal{Y} = {0, \space 1} Y = { 0 , 1 } ，令 H = { h r : r ∈ R + , h r ( x ) = I ( ∥ x ∥ ≤ r ) } \mathcal{H} = { h_r : r \in \mathbb{R}_+, \space h_r(\boldsymbol{x}) = \mathbb{I}(| \boldsymbol{x} | \leq r)} H = { h r : r ∈ R + , h r ( x ) = I ( ∥ x ∥ ≤ r )} ，则当 H \mathcal{H} H 可分时，问题是 PAC 可学习的.
Proof：\color{brown}{\textbf{Proof：}} Proof ：根据 E R M \mathrm{ERM} ERM 法则，构建算法返回的假设 h r ^ h_{\hat{r}} h r ^ 满足 r ^ \hat{r} r ^ 等于标记为 1 1 1 的样本的范数最大值. 设 X \mathcal{X} X 的密度函数为 f ( x ) f(\boldsymbol{x}) f ( x ) ，记 F ( r ) = ∫ ∥ x ∥ ≤ r f ( x ) d x F(r) = \int_{| \boldsymbol{x} | \leq r} f(\boldsymbol{x}) \mathrm{d}\boldsymbol{x} F ( r ) = ∫ ∥ x ∥ ≤ r f ( x ) d x ，最优假设为 h r ∗ h_{r^} h r ∗ ，则 r ^ ≤ r ∗ \hat{r} \leq r^ r ^ ≤ r ∗ ，则：
L D ( h r ^ ) = P x ∼ f [ h r ^ ( x ) ≠ h r ∗ ( x ) ] = F ( r ∗ ) − F ( r ^ ) . \begin{equation} L_{\mathcal{D}}(h_{\hat{r}}) = \mathbb{P}{\boldsymbol{x} \sim f} \left[ h}(\boldsymbol{x}) \not= h_{r^}(\boldsymbol{x}) \right] = F(r^) -
\end{equation} L D ( h r ^ ) = P x ∼ f [ h r ^ ( x ) = h r ∗ ( x ) ] = F ( r ∗ ) − F ( r ^ ) .
对于任意给定 ε ∈ ( 0 , 1 ) \varepsilon \in (0, \space 1) ε ∈ ( 0 , 1 ) ，只需让 F ( r ∗ ) − F ( r ^ ) ≤ ε F(r^) - F(\hat{r}) \leq \varepsilon F ( r ∗ ) − F ( r ^ ) ≤ ε . 若 F ( r ∗ ) ≤ ε F(r^) \leq \varepsilon F ( r ∗ ) ≤ ε ，不等式直接成立，不妨设 F ( r ∗ ) > ε F(r^) > \varepsilon F ( r ∗ ) > ε ，记 r ε r_{\varepsilon} r ε 满足 F ( r ε ) = F ( r ∗ ) − ε F(r_{\varepsilon}) = F(r^) - \varepsilon F ( r ε ) = F ( r ∗ ) − ε ，样本中标记为 1 1 1 的样本数为 m + m^+ m + ，则 m + ∼ B i n o m i a l ( m , F ( r ∗ ) ) m^+ \sim \mathrm{Binomial}(m, \space F(r^*)) m + ∼ Binomial ( m , F ( r ∗ )) ，且有：
P ( r ^
\mathbb{P}(\hat{r}
\end{equation} P ( r ^
对等式两边取期望，得：
P ( r ^
\mathbb{P}(\hat{r}
\end{equation} P ( r ^
根据二项分布的矩母函数，有：
E [ exp ( − ε m +
\mathbb{E} \left[ \exp\left( -\dfrac{\varepsilon m^+}{F(r^*)} \right)\right] = \left[ 1 -
\end{equation} E [ exp ( − F ( r ∗ ) ε m + ) ] = [ 1 − p ( 1 − e − q ) ] m ,
其中 p = F ( r ∗ ) p = F(r^) p = F ( r ∗ ) ，q = ε F ( r ∗ ) q = \frac{\varepsilon}{F(r^)} q = F ( r ∗ ) ε . 容易证明 e − q ≤ 1 − q + 1 2 q 2 \mathrm{e}^{-q} \leq 1 - q + \frac{1}{2} q^2 e − q ≤ 1 − q + 2 1 q 2 ，故 1 − e − q ≥ q − 1 2 q 2 ≥ 1 2 q 1 - \mathrm{e}^{-q} \geq q - \frac{1}{2}q^2 \geq \frac{1}{2}q 1 − e − q ≥ q − 2 1 q 2 ≥ 2 1 q （ 0 ≤ q ≤ 1 0 \leq q \leq 1 0 ≤ q ≤ 1 ），因此：
[ 1 − p ( 1 − e − q ) ] m ≤ [ 1 − p ( q 2 ) ] m ≤ ( 1 − 1 2 ε ) 2 ≤ exp ( − ε m 2 ) . \begin{equation} \left[ 1 -
\end{equation} [ 1 − p ( 1 − e − q ) ] m ≤ [ 1 − p ( 2 q ) ] m ≤ ( 1 − 2 1 ε ) 2 ≤ exp ( − 2 ε m ) .
故：
P ( r ^
令不等式右侧小于 δ \delta δ ，得：
m ≥ 2 ε ln 1 δ . \begin{equation} m \geq \dfrac{2}{\varepsilon} \ln \dfrac{1}{\delta}. \end{equation} m ≥ ε 2 ln δ 1 .
综上所述，该问题是 PAC 可学习的，且采样复杂度 m ≤ ⌈ 2 ε ln 1 δ ⌉ m \leq \Big\lceil \frac{2}{\varepsilon} \ln \frac{1}{\delta} \Big\rceil m ≤ ⌈ ε 2 ln δ 1 ⌉ . □ \square □
来源：墨码行者
