【机器学习】四、计算学习理论

旧城等待， 2024-02-20 11:35 85阅读 0赞

### 1 基础知识 ###

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

对于二分类问题，给定样本集![在这里插入图片描述][ecd651c849aa4f6f9c1046d300c0a7f9.png]  
假设所有样本服从一个隐含未知的分布D DD，所有样本均独立同分布（independent and identically distributed）。

令h为样本到\{ − 1 , + 1 \} 上的一个映射，其泛化误差为  
![E ( h ; D ) = P x ∼ D ( h ( x ) ≠ y ) E(h;D)=P\_\{x\\sim D\}(h(x)\\neq y) E(h;D)=P x∼D  (h(x)   =y)][E _ h _ D _ _ P x _ D _ h _ x _ _ y _ E_h_D_P_x_sim D_h_x_neq y_ E_h_D_P x_D _ _h_x_ _ _ _y]

h在D 的经验误差为  
![在这里插入图片描述][762426adc4f340918afd755d5e2b942e.png]

由于D是D的独立同分布采样，因此h hh的经验误差的期望等于其泛化误差。 在上下文明确时，我们将E ( h ; D ) 和E ^ ( h ; D ) 分别简记为E ( h )和E ^ ( h ) 。 令ϵ为E ( h ) 的上限，即E ( h ) ≤ ϵ E(h)；我们通常用ϵ表示预先设定的学得模型所应满足的误差要求，亦称“误差参数”。

我们将研究经验误差和泛化误差之间的逼近程度；若h在数据集上的经验误差为0，则称h与D一致，否则称其不一致。对于任意两个映射h 1 , h 2 ∈ X → Y h\_1,h\_2，用不合（disagreement）来度量他们之间的差别：  
d ( h 1 , h 2 ) = P x ∼ D ( h 1 ( x ) ≠ h 2 ( x ) )  
我们将会用到几个常见的不等式：

Jensen不等式：对任意凸函数，有  
![f ( E ( X ) ) ≠ E ( f ( x ) ) f(E(X))\\neq E(f(x)) f(E(X))   =E(f(x))][f _ E _ X _ _ _ E _ f _ x _ _ f_E_X_neq E_f_x_ f_E_X_ _ _ _E_f_x]

Hoeffding不等式：若x 1 , x 2 , … , x m  
为m 个独立随机变量，且满足0 ≤ x i ≤ 1，对任意ϵ > 0，有  
![在这里插入图片描述][7d91a32bb706483a9909cf950e079701.png]

McDiarmid不等式：  
![在这里插入图片描述][5c80d86150d842dc907bef9cad79617d.png]

### 2 PAC学习 ###

概率近似正确理论（Probably Approximately Correct，PAC）：

首先介绍两个概念：

C：概念类。表示从样本空间到标记空间的映射，对任意样例，都能使得c ( x ) = y 。  
H ：假设类。学习算法会把认为可能的目标概念集中起来构成H。  
若c ∈ H ，则说明假设能将所有示例按真实标记一致的方式完全分开，称为该问题对学习算法而言是”可分的“；否则，称为”不可分的“  
对于训练集，我们希望学习算法学习到的模型所对应的假设h hh尽可能接近目标概念c。我们是希望以比较大的把握学得比较好的模型，也就是说，以较大的概率学得误差满足预设上限的模型，这就是"概率近似正确"的含义。形式化地说，令δ 表示置信度，可定义:

PAC辨识：对0 ≤ ϵ , δ < 1 ，所有的c ∈ C 和分布D ，若存在学习算法，其输出假设h ∈ H 满足：  
![P ( E ( h ) ≤ ϵ ) ≥ 1 − δ P(E(h)\\le \\epsilon)\\ge 1- \\delta P(E(h)≤ϵ)≥1−δ][P _ E _ h _ _ _ _ _ 1 _ _ P_E_h_le _epsilon_ge 1- _delta P_E_h_1]

![在这里插入图片描述][4cda7a01bad04b699b57d5c94ec0c5ba.png]

![PAC学习中一个关键因素是假设空间H的复杂度。H包含了学习算法所有可能输出的假设，若在PAC学习中假设空间与概念类完全相同，即H=C，这称为"恰PAC可学习" (properly PAC learnable)。直观地看，这意味着学习算法的能力与学习任务”恰好匹配“。 然而，这种让所有候选假设都来自概念类的要求看似合理，但却并不实际，因为在现实应用中我们对概念类C CC通常一无所知，更别说获得一个假设空间与概念类恰好相同的学习算法。显然，更重要的是研究假设空间与概念类不同的情形，即H ≠ C H\\neq CH   =C。 一般而言，H HH越大，其包含任意目标概念的可能性越大，但从中找到某个具体目标概念的难度也越大。∣ H ∣ |H|∣H∣有限时，我们称究为"有限假设空间"，否则称为"无限假设空间"。][PAC_H_H_PAC_H_C_PAC_ _properly PAC learnable_ _C CC_H _ C H_neq CH _ _ _C_ _H HH_ H _ _H_H]

### 3 有限假设空间 ###

3.1 可分情形  
![在这里插入图片描述][3c51905aa1004e4a990f2b807d0ae6ac.png]

3.2 不可分情形  
![在这里插入图片描述][d4c4e02ca3d84a0ab83057c8eb45310a.png]

### 4 VC维 ###

![在这里插入图片描述][2eece599b6d042ae812ae7f009ffbde1.png]

### 5 Rademacher复杂度 ###

![在这里插入图片描述][6df5647e8c9e4832ba2b1bf75a225eb0.png]

### 6 稳定性 ###

![在这里插入图片描述][b67ca91858d146aea36b009b22c829d3.png]

![在这里插入图片描述][02619ee0b0f644eca28ad783a6992d3c.png]

[ecd651c849aa4f6f9c1046d300c0a7f9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/6cf4059f0c224e519192d5cc4b8dbc0c.png
[E _ h _ D _ _ P x _ D _ h _ x _ _ y _ E_h_D_P_x_sim D_h_x_neq y_ E_h_D_P x_D _ _h_x_ _ _ _y]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/7ca618dda8fd4a5497bad201a1792da9.png
[762426adc4f340918afd755d5e2b942e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/94b1dc1e3e044b61955df7740a09ddb2.png
[f _ E _ X _ _ _ E _ f _ x _ _ f_E_X_neq E_f_x_ f_E_X_ _ _ _E_f_x]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/a719a215cfc342a1b104a7fdbcf8b97b.png
[7d91a32bb706483a9909cf950e079701.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/11d94abe214d4ef3b23d01720e69545a.png
[5c80d86150d842dc907bef9cad79617d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/460c99121c9f4b4fbb7574af1132ead5.png
[P _ E _ h _ _ _ _ _ 1 _ _ P_E_h_le _epsilon_ge 1- _delta P_E_h_1]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/dd9e724a75724a1988d186eaa10ebc73.png
[4cda7a01bad04b699b57d5c94ec0c5ba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/f6876555e4054cfabe9e3669e312eae7.png
[PAC_H_H_PAC_H_C_PAC_ _properly PAC learnable_ _C CC_H _ C H_neq CH _ _ _C_ _H HH_ H _ _H_H]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/76928809c8c147fcad5c8b80b73cb506.png
[3c51905aa1004e4a990f2b807d0ae6ac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/f539ab3296c4435ba43463e2288f3fb6.png
[d4c4e02ca3d84a0ab83057c8eb45310a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/47ca5b1064264fcaaa8dcd2fedf408e3.png
[2eece599b6d042ae812ae7f009ffbde1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/ac06b4ad812a424f823b88e97084d38a.png
[6df5647e8c9e4832ba2b1bf75a225eb0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/2dd91baf51d649d98948f4ae0e5e4d05.png
[b67ca91858d146aea36b009b22c829d3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/b58b89918e784e1da199d02cacea28af.png
[02619ee0b0f644eca28ad783a6992d3c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/0cf07c283da54e3f9738afd9a2ab49f9.png