• 计算学习理论研究的是关于通过计算来进行学习的理论,目的是分析学习任务的困难本质,为学习算法提供理论保证,并提供分析结果指导算法设计.
  • 计算学习理论中最基本的是概率近似正确(Probably Approximately Correct,PCA)学习理论.由此可以得到PAC辨识,PAC可学习,PAC学习算法,样本复杂度等概念.
  • 有限假设空间的可分情形都是PAC可学习的.对于不可分情形,可以得到不可知PAC可学习的概念,即在假设空间的所有假设中找到最好的一个.
  • 对二分类问题来说,假设空间中的假设对数据集中示例赋予标记的每种可能结果称为对数据集的一种对分.若假设空间能实现数据集上的所有对分,则称数据集能被假设空间打散.假设空间的VC维是能被假设空间打散的最大数据集的大小.
  • 算法的稳定性考察的是算法在输入发生变化时,输出是否会随之发生较大的变化.