从今天起开始总结暑假所学知识

监督学习

使用样例来合成计算机程序的过程称为学习方法，其中样例由输入或者输出给出时，称为监督学习。有关输入和输出的函数关系成为训练数据。

输入和输出通常反映了把输入映射到输出的一种函数关系，当输入到输出存在内在函数时，该函数称为目标函数。由学习算法输出对目标函数的估计称为学习问题的解（对于分类问题，被称为决策函数）。存在一系列候选函数可把输入空间映射到输出域，选择一组或者一类候选函数，它们称为假设集合。例如：决策树是通过构造二叉树而产生假设，树的内部节点是简单的决策函数，而叶节点是输出值。因此把假设集合或者假设空间的选择看作学习过程的关键因素，而从训练数据中学习并从假设空间中选择假设的算法是第二个重要因素，它称为学习算法。

在输出时，有二元输出的问题成为二类问题，有多个类别的问题称为多类问题，而实数值输出的问题称为回归问题，在学习中，二类问题通常作为最简单的情形率先被考虑。

非监督学习及其他

非监督学习其数据不包含输出值，学习的任务是理解数据产生的过程，还有一些学习模型考虑了学习器与其环境复杂的交互过程，例如:针对一特定输入向系统查询其输出，关于该过程中如何影响学习器能力的研究称为查询学习。更复杂的交互在强化学习中考虑，这里学习器拥有一组可任意执行的动作，学习器通过执行这些动作尝试达到较高回报的状态。相关学习方法也可应用于强化学习中，前提是将最有动作看作是学习器当前状态的一个函数输出，这样会产生相当的复杂性，因为输出的质量只能在动作的后果清晰后才能被间接衡量。

学习模型的另一方面的问题是训练数据如何产生及如何输入到学习器。例如，批量学习和在线学习之间存在明显的区别，前者在学习的一开始就把所有的输入提供给学习器，后者则让学习器一次只能接收一个样例，并在接收正确输出前给出自己对输出的估计，在线学习中学习器根据每个新样例更新当前假设，学习器的质量由学习期间产生的总错误数量来衡量。

学习和泛型

在线学习算法的质量可由其训练阶段的出错总数来衡量。至于衡量批量学习中所产生假设的质量，早期的学习算法致力于通过学习产生简单的符号表示，它可由专家来理解和验证。学习的目标是输出一个假设以正确分类训练数据，早期的学习算法目标也是寻找对数据的精确拟合，这样寻找的假设称为一致假设。生成可验证的一致假设存在两个问题。

待学习的目标函数可能没有简单的表示，因此不能很容易的加以验证。

通常训练的数据是有噪声的，不能保证存在一个目标函数能够正确的映射训练数据。

对于机器学习研究者来说，他们感兴趣的数据将越来越多的属于这个类型，使得上面的质量衡量标准难以实现，即使能够找到与训练数据一致的假设也可能无法对未见数据进行分类。一个假设正确分类训练集之外数据的能力称为泛化性，这正是要优化的属性。

研究目标转移到泛化，就不再要求对假设看作真实目标函数的正确表示。如果一个假设能够给出正确的输出，它就满足泛化性的准则，在这种意义上泛化性成为一个功能性准则而不是描述性准则，同时该准则不再限制假设的规模以及含义，它们今后可以是任意的。

提高泛化性

泛化性准则对于学习算法附加了另一种约束，这一点可以由一种极端情形下的机械式学习来充分证明，许多经典的机器学习算法能够表示任意函数，并且对于困难的训练数据集会得到一个类似机械式学习器的假设，所谓机械式学习器是指能够正确分类训练数据，但对所有未见数据会做出根本无关联性额度预测。例如：决策树有可能过度增长直到针对每个训练样例只有一个叶子节点，为了得到一致假设而使假设过度复杂称为过拟合，控制此问题的一种方法是限制假设的规模，例如对于决策树可进行修剪操作。这种采用的方法是为了获得另一种平衡，它涉及泛化误差率上的统计边界，这些边界通常依赖于分类器间隔这样的变量，并引发最优化该变量的算法，该途径的缺点在于此算法不会好于统计结果，因此能避免基于错误直觉的启发式方法带来的危险。

算法设计基于统计结果这一点并非意味着忽略解决此类优化问题的计算复杂度，所感兴趣的技术需要拥有可伸缩性，它应该能凑够玩具世界的问题到包含上万条记录 的真实数据集的问题，只有通过对计算复杂度的原则性分析，才能避免满足于那些只在小样本上表现良好，却对大训练集完全失效的启发式规则，计算复杂度理论研究了两类问题，第一类问题是是否存在算法能够在输入规模的多项式时间内运行的问题，第二类问题是如果存在这样的算法，任意解是否能在多项式时间内检验，也就是能不能在多项式时间内求解的问题，后一类问题即为NP完全问题，通常认为这些问题不能有效求解。

贝叶斯分析的出发点是假设 集合上的先验分布，它描述了学习器对于数据特定假设的似然性的先验理念。只要能假定这样的先验分布，再加上数据如何被噪声干扰的模型，原则上就有可能在给定训练集合的情况下估计最可能的假设，甚至于可以在可能假设的集合上做加权平均。

如果不对所有可能的假设（即对输入空间到输出域的所有可能的目标函）的集合加以限制，学习是不能完成的，因为训练数据本身无法对未见样例进行分类，如果放宽限制，使得可以在看到数据后再自由的选择假设集合，这同样也会产生问题，因为可能会简单的假定正确的假设具有任意先验概率。在此意义上所有学习系统必须做出贝叶斯模型的先验假定，它称为学习偏置。