（《机器学习》完整版系列）第12章 计算学习理论——12.4 有限假设空间不可分情形（退而求其次：不可知PAC可学习的）
在
H
\mathcal{H}
H有限但不可分时，在绝大多情况下（即排除情况（2）），学习算法
L
\mathfrak{L}
L无法学得目标概念
c
c
c的
ϵ
\epsilon
ϵ近似。
退而求其次，设
H
\mathcal{H}
H中泛化误差最小的假设
h
0
=
arg
min
h
∈
H
E
(
h
)
h_0=\mathop{\arg\min}\limits_{h\in \mathcal{H}}E(h)
h0=h∈HargminE(h)，则对
h
0
h_0
h0而言，“
H
\mathcal{H}
H是可学习的”。
不可分情形
不可分情形（即
c
∉
H
c \notin \mathcal{H}
c∈/H），由【西瓜书推论12.1 式(12.18)】（或由【西瓜书定理12.1 式(12.19)】同样证明）知，对任意的
h
h
h，有
P
(
E
^
(
h
)
−
ln
2
δ
2
m
⩽
E
(
h
)
⩽
E
^
(
h
)
+
ln
2
δ
2
m
)
⩾
1
−
δ
\begin{align} % P\left(E(h)\geqslant \hat E(h)-\sqrt{\frac{\ln \frac{2}{\delta }}{2m}}\right)&\geqslant P\left( \hat E(h)-\sqrt{\frac{\ln \frac{2}{\delta }}{2m}} \leqslant E(h)\leqslant \hat E(h)+\sqrt{\frac{\ln \frac{2}{\delta }}{2m}}\right) & \geqslant 1-\delta \tag{12.10} \end{align}
P
E^(h)−2mlnδ2⩽E(h)⩽E^(h)+2mlnδ2
⩾1−δ(12.10)
因 H \mathcal{H} H有限，故可取 h m = arg min h ∈ H E ^ ( h ) h_m=\mathop{\arg\min}\limits_{h \in \mathcal{H} }\hat E(h) hm=h∈HargminE^(h)，分两种情况讨论：
（1）当 ∃ m \exists m ∃m使得在 D m D_ m Dm上 E ^ ( h m ) − ln 2 δ 2 m > 0 \hat E(h_m)-\sqrt{\frac{\ln \frac{2}{\delta }}{2m}}>0 E^(hm)−2mlnδ2>0时
则
E
^
(
h
m
)
−
ln
2
δ
2
m
⩽
E
^
(
h
)
−
ln
2
δ
2
m
\hat E(h_m)-\sqrt{\frac{\ln \frac{2}{\delta }}{2m}} \leqslant \hat E(h)-\sqrt{\frac{\ln \frac{2}{\delta }}{2m}}
E^(hm)−2mlnδ2⩽E^(h)−2mlnδ2
将其代入式(12.10)，则有
P
(
E
^
(
h
m
)
−
ln
2
δ
2
m
⩽
E
(
h
)
⩽
E
^
(
h
)
+
ln
2
δ
2
m
)
⩾
1
−
δ
\begin{align} P\left( \hat E(h_m)-\sqrt{\frac{\ln \frac{2}{\delta }}{2m}} \leqslant E(h)\leqslant \hat E(h)+\sqrt{\frac{\ln \frac{2}{\delta }}{2m}}\right) & \geqslant 1-\delta \notag \end{align}
P
E^(hm)−2mlnδ2⩽E(h)⩽E^(h)+2mlnδ2
⩾1−δ
则有
P
(
E
^
(
h
m
)
−
ln
2
δ
2
m
⩽
E
(
h
)
)
⩾
P
(
E
^
(
h
m
)
−
ln
2
δ
2
m
⩽
E
(
h
)
⩽
E
^
(
h
)
+
ln
2
δ
2
m
)
⩾
1
−
δ
P
(
ϵ
m
⩽
E
(
h
)
)
⩾
1
−
δ
\begin{align} & \quad P\left( \hat E(h_m)-\sqrt{\frac{\ln \frac{2}{\delta }}{2m}} \leqslant E(h)\right)\notag \\ & \geqslant P\left( \hat E(h_m)-\sqrt{\frac{\ln \frac{2}{\delta }}{2m}} \leqslant E(h)\leqslant \hat E(h)+\sqrt{\frac{\ln \frac{2}{\delta }}{2m}}\right)\notag \\ & \geqslant 1-\delta \notag \\ P\left( \epsilon_m \leqslant E(h)\right) & \geqslant 1-\delta \tag{12.11} \end{align}
P(ϵm⩽E(h))P
E^(hm)−2mlnδ2⩽E(h)
⩾P
E^(hm)−2mlnδ2⩽E(h)⩽E^(h)+2mlnδ2
⩾1−δ⩾1−δ(12.11)
其中，
ϵ
m
=
E
^
(
h
m
)
−
ln
2
δ
2
m
\epsilon_m =\hat E(h_m)-\sqrt{\frac{\ln \frac{2}{\delta }}{2m}}
ϵm=E^(hm)−2mlnδ2（任意给定
0
<
δ
<
1
0<\delta <1
0<δ<1）。
注：这里用到两个技巧：上式用到“几乎成立”的不等式具有传递性；下式用到由集合的包含关系得到概率不等式。 这些技巧在第~\ref{ch12:tri}节我们还会见到。
由已设定的情况，有
0
<
ϵ
m
<
1
0<\epsilon_m <1
0<ϵm<1，令
0
<
ϵ
<
ϵ
m
\begin{align} 0<\epsilon <\epsilon_m \tag{12.12} \end{align}
0<ϵ<ϵm(12.12)
则由式(12.11)、式(12.12)有
P
(
E
(
h
)
>
ϵ
)
⩾
P
(
E
(
h
)
⩾
ϵ
m
)
⩾
1
−
δ
P
(
E
(
h
)
⩽
ϵ
)
⩽
δ
,
(
∀
h
∈
H
)
\begin{align} P\left( E(h) > \epsilon\right) & \geqslant P\left( E(h) \geqslant \epsilon_m \right)\notag \\ & \geqslant 1-\delta \notag \\ P\left( E(h) \leqslant \epsilon\right) & \leqslant \delta , \quad (\forall h \in \mathcal{H} ) \tag{12.13} \end{align}
P(E(h)>ϵ)P(E(h)⩽ϵ)⩾P(E(h)⩾ϵm)⩾1−δ⩽δ,(∀h∈H)(12.13)
由此可知，对于上述
ϵ
,
δ
\epsilon,\ \delta
ϵ, δ，在
D
m
D_m
Dm上不存在
h
h
h满足式(12.2)，否则与式(12.13)矛盾，即此时不满足【西瓜书定义12.1(12.9)】的PAC可学习的条件。
（2）当 ∀ m \forall m ∀m，在 D m D_ m Dm上都有 E ^ ( h m ) − ln 2 δ 2 m ⩽ 0 \hat E(h_m)-\sqrt{\frac{\ln \frac{2}{\delta }}{2m}}\leqslant 0 E^(hm)−2mlnδ2⩽0时（这里的“都”字是很难满足的，故通常忽略这一情形）
为清晰，将
E
^
(
h
m
)
=
min
E
^
(
h
)
\hat E(h_m)=\min \hat E(h)
E^(hm)=minE^(h)记
E
^
D
m
(
h
m
)
\hat E_{D_m}(h_m)
E^Dm(hm)，则有
0
<
E
^
D
m
(
h
m
)
⩽
ln
2
δ
2
m
→
0
,
(
若
m
→
∞
)
E
^
D
m
(
h
m
)
→
0
,
(
若
m
→
∞
)
\begin{align*} 0<\hat E_{D_m}(h_m) & \leqslant \sqrt{\frac{\ln \frac{2}{\delta }}{2m}}\rightarrow 0,\quad (\text{若}\ m\rightarrow \infty ) \\ \hat E_{D_m}(h_m) & \rightarrow 0,\quad (\text{若}\ m\rightarrow \infty ) \end{align*}
0<E^Dm(hm)E^Dm(hm)⩽2mlnδ2→0,(若 m→∞)→0,(若 m→∞)
则可从中选出趋于0的单调下降子序列：
{
{
E
^
m
i
(
h
m
i
)
}
i
=
0
∞
E
^
m
s
(
h
m
s
)
>
E
^
m
t
(
h
m
t
)
>
0
,
(
若
m
s
<
m
t
)
\begin{align} \begin{cases} \{\hat E_{m_i}(h_{m_i})\}_{i=0}^\infty \\ \hat E_{m_s}(h_{m_s})>\hat E_{m_t}(h_{m_t})>0,\quad (\text{若} \ m_s<m_t) \\ \end{cases} \tag{12.14} \end{align}
{{E^mi(hmi)}i=0∞E^ms(hms)>E^mt(hmt)>0,(若 ms<mt)(12.14)
因
H
\mathcal{H}
H有限，而序列(12.14)无限，故必有某
h
h
h（不妨设为
h
0
h_0
h0）会重复无限次，将这个子序列列出
{
{
E
^
m
i
(
h
0
)
}
i
=
0
∞
E
^
m
i
(
h
0
)
→
0
\begin{align} \begin{cases} \{\hat E_{m_i}(h_0)\}_{i=0}^\infty \\ \hat E_{m_i}(h_0)\rightarrow 0 \\ \end{cases} \tag{12.15} \end{align}
{{E^mi(h0)}i=0∞E^mi(h0)→0(12.15)
则有
E
^
m
i
(
h
0
)
=
1
m
i
∑
x
∈
D
m
i
I
(
h
0
(
x
)
≠
c
(
x
)
)
（由定义）
→
E
(
I
(
h
0
(
x
)
≠
c
(
x
)
)
)
（由大数定律）
=
E
(
h
0
)
（由定义）
\begin{align} \hat E_{m_i}(h_0) & =\frac{1}{m_i}\sum_{x \in D_{m_i}}\mathbb{I} (h_0(x)\neq c(x))\qquad \text{（由定义）}\notag \\ & \rightarrow \mathbb{E}\ (\mathbb{I} (h_0(x)\neq c(x)))\qquad \text{（由大数定律）}\notag \\ & =E(h_0) \qquad \text{（由定义）} \tag{12.16} \end{align}
E^mi(h0)=mi1x∈Dmi∑I(h0(x)=c(x))（由定义）→E (I(h0(x)=c(x)))（由大数定律）=E(h0)（由定义）(12.16)
由式(12.15)、式(12.16)得
E
(
h
0
)
=
0
E(h_0)=0
E(h0)=0。 即存在
h
0
h_0
h0满足【西瓜书定义12.1(12.9)】的PAC可学习的条件。
综上，在
H
\mathcal{H}
H有限但不可分时，在绝大多情况下（即排除情况（2）），学习算法
L
\mathfrak{L}
L无法学得目标概念
c
c
c的
ϵ
\epsilon
ϵ近似。
退而求其次，设
H
\mathcal{H}
H中泛化误差最小的假设
h
0
=
arg
min
h
∈
H
E
(
h
)
h_0=\mathop{\arg\min}\limits_{h\in \mathcal{H}}E(h)
h0=h∈HargminE(h)，则
h
0
∈
H
h_0\in \mathcal{H}
h0∈H，将
h
0
h_0
h0视为可分情形中的
c
c
c，则对
h
0
h_0
h0而言，“
H
\mathcal{H}
H是可学习的”，即能“找到”
h
0
h_0
h0的
ϵ
\epsilon
ϵ近似，这就是【西瓜书定义12.5】的不可知PAC可学习。
P
(
(
E
(
h
)
−
arg
min
h
∈
H
E
(
h
)
)
⩽
ϵ
)
⩾
1
−
δ
\begin{align} P((E(h)- \mathop{\arg\min}\limits_{h\in \mathcal{H}}E(h))\leqslant \epsilon)\geqslant 1-\delta \tag{12.17} \end{align}
P((E(h)−h∈HargminE(h))⩽ϵ)⩾1−δ(12.17)
以式(12.17)取代式(12.2)，其他设定都相同，则称假设空间
H
\mathcal{H}
H是不可知PAC可学习的。 同样，也有“高效”的定义，“高效”的学习算法才是我们关注的学习算法，其样本复杂度为满足要求的最小
m
m
m。
本文为原创，您可以：
- 点赞（支持博主）
- 收藏（待以后看）
- 转发（他考研或学习，正需要）
- 评论（或讨论）
- 引用（支持原创）
- 不侵权
上一篇：12.3 有限假设空间可分情形
下一篇：12.5 无限假设空间
相关文章
- 生产追溯系统-Wifi+传感器，实现计数器以及监控机器是否停止
- jenkins:用jenkins通过ssh部署jar包到远程linux机器（jdk 15 / jenkins 2.257）
- 机器学习之深度学习
- 机器学习笔记 - 理解计算图的概念
- Atiitt 常见机器算法 理解 总结 目录 1. 机器学习的核心是“使用算法解析数据，从中学习，然后对世界上的某件事情做出决定或预测”1 2. 1. 五大流派2 2.1. ①符号主义：使用
- ML与Optimality：最优化理论(GD随机梯度下降/QN拟牛顿法/CG共轭梯度法/L-BFGS/TR置信域/GA遗传算法/SA模拟退火算法)在机器学习中的简介、常用方法、案例应用之详细攻略
- AI：2020年6月23日北京智源大会演讲分享之机器学习专题论坛 ——09:05-09:45Yolanda Gil教授《Thoughtful AI: Forging A New Partnersh》
- Python之GUI：基于Python的GUI界面设计的一套AI课程学习(机器学习、深度学习、大数据、云计算等)推荐系统(包括语音生成、识别等前沿黑科技)
- XAI之GS：全局代理(Global Surrogate，对黑盒机器学习执行模型可解释性的技术)的简介、常用工具包、案例应用之详细攻略
- 机器学习（四十一）：遗传算法对机器学习（回归）模型寻优
- 【阶段三】Python机器学习24篇：机器学习项目实战：XGBoost回归模型
- 数学之路-python计算实战(16)-机器视觉-滤波去噪(邻域平均法滤波)
- 机器学习——贝叶斯分类器
- 机器学习——评估方法