7.计算学习理论

1.样本复杂度，计算复杂度，出错界限

样本复杂度

2.可能近似正确（PAC）

 

3.真实错误率

 训练错误率：

 样本错误率

 4.一致学习器

 变形空间：

 详尽变形空间：

 

训练样本数目

 

5.不可知学习和不一致学习

 hoeffding边界

 

 6.无限假设空间的样本复杂度

Vapnik-Chervonenkis维度

打散

 

 基于VC的样本复杂度

 神经网络的VC维

 

 7.学习的出错界限模型

FIND-S

HAVING

 最优出错界限

加权多数算法

 

误差