计算学习理论基础
计算学习理论基础
基础知识
与计算理论类似,机器学习也有PAC可辨识,PAC可学习,高效PAC可学习的概念。
有限假设空间
在有限假设空间情形下,可以对PAC学习的样本复杂度在可分,不可分,不可知情形下做出估计。
VC维
增长函数
对于假设空间H,对于m个样本给出的最多标记情形数目称为假设空间的增长函数。
打散和VC维
若
那么,VC为定义为能打散的最大样本集大小。
例题
例1
例2
例3
例4
例题来自西瓜书例题或者习题,不是很困难,证明一下可以加强理解。
相关结论
也容易证明,可以作为练习。
Rademacher复杂度及与稳定性,VC维之间的联系
Rademacher复杂度是考虑了数据分布的复杂度。与稳定性,VC维之间存在联系。
定义为
计算学习理论基础部分还有VC维的例题还没仔细推导。