机器学习
C1 引言
一些学科和它们对机器学习的影响
- 人工智能：学习概念的符号表示；作为搜索问题的机器学习；作为提高问题求解能力的学习；利用先验的知识和训练数据一起引导学习。
- 贝叶斯方法：作为计算假设概率基础的贝叶斯法则；朴素贝叶斯；估计未观测到变量值的算法。
- 计算复杂性理论：不同学习任务中固有的复杂性的理论边界，以计算量，训练样例数量，出错数量衡量。
- 控制论：为了优化预定目标，学习对各种处理过程进行控制，学习预测被控制的过程的下一个状态。
- 信息论：熵和信息内容的度量；学习最小描述长度方法；编码假设时，对最佳训练序列的最佳编码及其关系。
- 哲学：奥卡姆的剃刀：最简单的假设是最好的；从观察到的数据泛化的理由分析。
- 心理学和神经生物学：实践的幂定律(power law of practice), 该定律指出对于很大范围内的学习问题，人们的反应速度随着时间次数的幂级提高；激发人工神经网络学习模式的神经生物学研究。
- 统计学：根据有限数据样本，对估计假设精度时出现的误差（例如偏差和方差）的刻画；置信区间，统计检验。
学习任务被简化为发现一个理想目标函数V的可操作描述，通常要完美学习这样一个V的可操作的形式是非常困难的。事实上，我们通常仅希望学习算法得到近似的目标函数，由于这个原因学习目标函数的过程常被称为函数逼近(function approximation).
这书的很多章节给出了一些基本表示（比如线性函数，逻辑描述，决策树，人工神经元网络）定义的假设空间的搜索算法。这些不同的假设表示法适合于学习不同的目标函数。对于其中的每一种假设表示法，对应的学习算法发挥不同内在结构的优势来组织对假设空间的搜索。自始至终，本书够贯穿着这种把学习问题视为搜索问题的看法，从而通过搜索策略和学习器探索的搜索空间的内在结构来刻画学习方法。
C2 概念学习和一般到特殊序
概念学习(concept learning)是指从有关某个布尔函数的输入输出训练样例中推断该布尔函数。概念学习可以看作是搜索预定义潜在假设空间的过程。
实例(instance), 训练样例(training examples), 正例(positive example), 反例(negative example), 所有可能假设(all possible hypotheses)
归纳学习假设：任一假设如果在足够大的训练样例集中很好地逼近目标函数，它也能在未见实例中很好地逼近目标函数。
由于归纳学习需要某种形式的预先假设，或称为归纳偏置(inductive bias), 我们可以用归纳偏置来描述不同学习方法的特征。 # 可以认为归纳偏置描述了这个算法本身在某方面的倾向
C3 决策树学习
通常决策树代表实例属性值约束的合取(conjunction)的析取式(disjunction). 从树根到树叶的每一条路径对影一族属性测试的合取，树本身对应这些合取的析取。
基本的ID3算法在搜索中不进行回溯，每当在树的某一层次上选择了一个属性进行测试，它不会再回溯重新考虑这个选择。所以它易受无回溯的爬山搜索中的常见风险影响：收敛到局部最优的答案，而不是全局最优。
奥卡姆剃刀(Occam's Razor): 优先选择拟合数据的最简单的假设。一种解释是简单假设的数量少于复杂假设的数量，所以找到一个简单的但是同时与训练数据拟合的假设的可能性较小。
决策树学习的实际问题包括：避免过度拟合数据，处理连续值的属性，属性选择度量标准，处理属性值不完整的训练数据，处理不同代价的属性，提高计算效率。处理连续值的属性可以通过对连续值进行分断或者是映射成为离散值来处理；属性不完整的训练数据可以为缺少值的属性安排最有可能的值，或者是按照概率来赋值；处理不同代价的属性是因为我们取得某些属性的难易程度不同，比如体温相对于血液化验结果更容易获得，在属性筛选方面需要考虑代价函数。
出现过度拟合(overfitting)一种可能原因是训练样例含有随机错误或噪声。当训练数据没有噪声时，过度拟合也可能发生，特别是当很少的样例被关联到叶子节点时。这种情况下，很可能是出现巧合的规律性，使得某些属性恰巧可以很好地被分割样例，但是却与实际的目标函数并无关系。 # 所以在做剪枝时需要减去一些叶子节点上很少的样例的节点。
有几种途径可以被用来避免决策树学习中的过度拟合，它们可以被分为两类：
- 及早停止树增长，在ID3算法完美分类训练数据之前就停止树增长。 # 一种启发式规则：最小描述长度(MDL, minimum description length)来指导是否停止树增长. 或者是利用卡方(chi-square)测试来估计进一步扩展节点能否改善整个实例分布上的性能，还是仅仅改善了当前的训练数据上的性能。
- 后修剪法(post-prune), 即允许树过度拟合，然后对整个树进行后修剪。# 通过判断合并某个节点是否能够改善验证数据来决定修剪, 称为错误率降低修剪(reduced-error pruning).
尽管第一种方法看起来更直接，但是对于过度拟合进行后修剪被证明在实践中更成功，因为第一种方法中精确地估计何时停止树增长很困难。
C4 人工神经网络
由于ANN(Artificial Neural Networks, ANN)只是在一定程度上受到生物神经系统的启发，所以ANN并未模拟生物神经系统中很多复杂特征，而且已经知道ANN很多特征也和生物系统也是不一致的。例如我们考虑的ANN每一个单元输出单一的不变值，然而生物神经元输出的是复杂的时序脉冲。
ANN基本组成单元是感知器(perceptron)变种：因为感知器的输出函数是有阈值并且不可导的sign(w' * x)，为了方便计算所以ANN基本单元输出变成无阈值并且连续可导(w' * x). 这样可以通过梯度下降方法来求解。多层网络的每层之间输出加上sigmoid单元。sigmoid函数有个特性导数很容易求解，s'(x) = s(x) * (1 - s(x)).
多层网络可以使用反向传播算法来求解。反向传播算法仅能保证收敛到误差E的某个局部极小值，不一定收敛到全局最小值。尽管缺乏对收敛到全局最小误差的保证，反向传播算法在实践中仍是非常有效的函数逼近算法。一个解释是可以考虑含有大量权值的网络，它对应着维度非常高的空间曲面。梯度下降中某个权陷入局部极小值时，其他权未必是局部极小值。网络的权越多，空间曲面越多，就越有可能为梯度下降提供更多的"逃逸曲线"，让梯度下降离开相对该单个权值的局部极小值。另外一个解释是，如果初始化权重为0时，sigmoid函数在0附近接近线性函数，不容易出现局部极小值；只有当权值增长一段时间之后，空间曲面才呈现高度非线性特征，这个时候才有比较多的局部极小值，而此时已经足够靠近全局最小值。为了缓解局部最小值情况，常见的启发式规则有：为梯度更新增加一个冲量项希望冲过狭窄的最小值；使用随机梯度下降而不是批量梯度下降；使用不同的随机权值来训练网络。
前馈网络的表征能力：
- 布尔函数：任何布尔函数都可以被具有两层单元的网络准确表示。
- 连续函数：任何有界连续函数可以由一个两层网络以任意小的误差逼近。
- 任意函数：任意函数可以被一个有三层单元的网络以任意精度逼近。
ANN的高级课题
- 其他可选的误差函数：1)增加权值惩罚项 2)交叉熵最小化
- 其他可选的误差最小化过程（不一定是反向传播算法）
- 递归网络以及动态修改网络结构
C6 贝叶斯学习
D表示数据集合，h表示假设
- P(h)称为h的先验概率(prior probability), 它反映了我们所拥有的关于h是正确假设的机会的背景知识
- P(D)代表训练数据D的先验概率，P(D|h)代表假设h成立时观察到数据D的概率。
- P(h|D)表示给定数据D时h成立的概率，称为h的后验概率(posterios probability), 也是我们要求解的对象
- 贝叶斯公式是P(h|D) = P(D|h) * P(h) / P(D).
- 对于P(h|D)最大的假设被称为极大后验假设(maximum a posterior, MAP)
- 如果P(h)和P(D)相同的话，那么MAP就是最大的P(D|h). P(D|h)被称为给定h时数据D的似然度(likelihood), 最大的P(D|h)称为极大似然(maximum likelihood, ML).
- 如果我们对于假设先验概率相同的话，那么ML == MAP
在特定的前提下，不管是使误差平方最小化，使交叉熵最小化，以及使用最小描述长度，都是在寻找极大似然假设。
MAP假设并不一定是最优分类器。考虑一个情况包含三个假设h1, h2, h3, 后验概率分别是0.4, 0.3, 0.3. 那么h1是MAP. 但是如果针对一个实例，h1预测+1, 而h2, h3预测-1. 那么实际上-1概率是0.6, 比+1(0.4)更有可能。我们可以通过对合并所有假设输出并且使用后验概率加权来预测结果，这样得到的假设是才是最优的(贝叶斯最优分类器, Bayes optimal classifier).
C8 基于实例的学习
应用k-近邻算法的一个实践问题是，实例之间的距离是根据实例的所有属性计算的。如果20个属性里面只有2个属性和分类相关，那么其余18个属性会误导分类。换句话说，近邻之间的距离会被大量的不相关属性所支配，这种由于存在很多不相关属性所导致的难题，有时被称为维度灾难(curse of dimensionality)。最近邻方法对这个问题特别敏感。
- 回归(regression): 逼近一个实数值的目标函数
- 残差(residual): 逼近目标函数时误差f(x) - y
- 核函数(kernel function): 一个距离函数，用来决定每个训练样例的权值
局部加权回归：局部只是目标函数逼近仅仅根据查询点附近的数据，加权指每个训练样例的贡献是由它与查询点间的距离加权的。局部线性加权回归则是：cost(x) = \SUM{x'表示x附近的k个近邻} (f(x') - y) ^ 2 * K(d(x', x)))
径向基函数(radial basis function, RBF): f(x) = w' * K(d(x', x)). 其中K为高斯核函数。径向基函数可以看做是一个两层的网络，第一层对输入做核函数映射，第二层对这些核函数做线性组合。理论上，只要以上高斯核函数数量足够多，那么RBF是可以逼近任何函数的。
消极学习延迟了如何从训练数据中泛化的决策，直到遇到一个新的查询案例才进行。积极学习则是在见到新的查询之前就做好泛化工作。消极学习方法可以对于每一个查询实例选择不同的假设（或目标函数的局部逼近），所以相当于可以通过很多局部逼近的组合（隐含地）表示目标函数；积极方法必须在训练时提交单个的全局逼近，一个覆盖整个实例空间的单一假设。当然积极方法可以使用合并了多个局部逼近的假设空间，就像RBF一样。然而，即使是这些合并的局部逼近，也不能使积极方法完全具有消极方法哪种针对未知查询作出假设的能力。