第七章 计算机学习理论7.1 简介在研究机器学习的过程中,学习器应遵循什么样的规则?是否能够独立于学习算法确定学习问题中固有的难度?能否知道为保证成功的学习有多少训练样例是必要的和充足的?如果学习器被允许想施教者提出查询,而不是观察训练集的随机样本,会对所需样例数目有怎样的影响?能否刻画出学习器在学习目标函数前回有多少次出错?能否刻画出一类学习问题中固有的计算复杂度?在这里我们着重讨论只给定目标函数的训练样例和候选假设空间的条件下,对该未知的目标函数的归纳学习问题.主要要解决的问题如:需要多少训练样例才足以成功的学习到目标函数以及学习器在达到目标前会出多少次错.后面将对以上的问题提出定量的上下界,这基于学习问题的如下属性:学习器所考虑的假设空间的大小和复杂度目标概念须近似到怎样的精度学习器输出成功的假设的可能性训练样例提供给学习器的方式 我们学习本章的目标的就是为了回答以下的问题:样本复杂度:学习器要收敛到成功假设(以较高的概率),需要多少的训练样例?计算复杂度:学习器要收敛到成功假设(以较高的概率)需要多大计算量?出错界限:在成功收敛到一个假设前,学习器对训练样例的错误分类有多少次?
