机器学习复习大纲.docx
6页
第一章1. 机器学习涉及学科(八大学科)：人工智能、概率和统计、计算复杂性理论、控制论、信 息论、心理学和神经生物学、哲学2. 学习定义对于某类任务T和性能度量P，如果一个计算机程序在T上以P衡量的性能随着经验E 而自我完善，那么我们称这个计算机程序在从经验E中学习3. 设计一个学习系统(五个步骤)：① 选择训练经验 ②选择目标函数 ③选择目标函数的表示 ④选择函数逼近算法 ⑤最终设 计4. 最终设计(四个模块)① 执行系统：用学会的目标函数来解决给定的任务② 鉴定器：以对弈的路线或历史记录作为输入，输出目标函数的一系列训练样例③ 泛化器：以训练样例为输入，产生一个输出假设，作为它对目标函数的估计④ 实验生成器：以当前的假设作为输入，输出一个新的问题，供执行系统去探索第二章1. 概念学习：是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数题型设计：计算实例、语法不同、语义不同的假设个数(P17页)FIND-S寻找极大特殊假设2. “一致”的定义:一个假设h与训练样例集合D 一致，当且仅当对D中每一个样例
这样，变型空间的大小可以在遇到每个新样例时减半，正确的目标概念就可在只用l og2IVSI 次实验后得到4. X的幕集:一般来说在集合X上定义的相异子集数目(X幕集的大小)为2|x|，其中|X|是X 的元素数目5. 归纳学习需要的预先假定，称为归纳偏置可以用归纳偏执来描述不同学习方法的特征第三章1. 决策树学习是应用最广的归纳推理算法之一，是一种逼近离散值函数的方法2. 决策树适用问题的特征：① 实例由“属性-值”对表示② 目标函数具有离散的输出值③ 可能需要析取的描述④ 训练数据可以包含错误⑤ 训练数据可以包含缺少属性值的实例.*****题型设计：画决策树(习题3-1)3. 用熵度量样例的均一性嫡刻画了任意样例集的纯度，给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类的嫡为Entropy(s) = -p log p — p log p㊉ 2 ㊉ 一 2 —4. 用信息增益度量期望的熵降低Gain(S, A) = Entropy(S) - £ Entropy(S )I S I v一个属性的信息增益是由于使用这个属性分割样例而导致的期望嫡降低v eValues (A)*****题型设计：求嫡和信息增益(习题3-2)5. 过度拟合定义：给定一个假设空间H, 一个假设heH,如果存在其他的假设h'eH,使得在训练样例 上h的错误率比h'小，但在整个实例分布上h'的错误率比h小，那么就说假设h过度拟合训 练数据。
6. 避免过度拟合的两种途径：①及早停止树增长②后修剪法第五章1. 当给定的数据集有限时，要学习一个概念并估计其将来的精度，存在两个很关键的困难：① 估计的偏差②估计的方差2. 样本错误率和真实错误率1 f (x)丰 h(x) 0 o th erwise定义：假设h关于目标函数f和数据样本S的样本错误率(标记为errors(h))error (h) = —^ 5 (f (x),h(x)) 6 (f (x),h(x))=s nxeS定义：假设h关于目标函数f和分布D的真实错误率(标记为errorD(h))error (h) = Pr[ f (x)h(x)]D xeD3.定义zN为计算N%置信区间的常数(取值见表5-1)，计算errorD(h^TN%置信区间的一般 表达式(公式5.1)为：(^)+ i error (h)(1 - error (h))n\ n4. 定义：针对任意参数p的估计量Y的估计偏差是：E[Y]-p如果估计偏差为0,称Y为p的无偏估计量5. 通常描述某估计的不确定性的方法是使用置信区间，真实的值以一定的概率落入该区间 中，这样的估计称为置信区间估计定义：某个参数p的N%置信区间是一个以N%的概率包含p的区间*****题型设计：求置信区间、单侧和双侧边界(习题5-3)第六章1. 贝叶斯学习方法的特性① 观察到的每个训练样例可以增量地降低或升高某假设的估计概率。
而其他算法会在某个假 设与任一样例不一致时完全去掉该假设② 先验知识可以与观察数据一起决定假设的最终概率，先验知识的形式是：1)每个候选假 设的先验概率；2)每个可能假设在可观察数据上的概率分布③ 贝叶斯方法可允许假设做出不确定性的预测④ 新的实例分类可由多个假设一起做出预测，用它们的概率来加权⑤ 即使在贝叶斯方法计算复杂度较高时，它们仍可作为一个最优的决策标准衡量其他方法2. 最佳假设：一种方法是把它定义为在给定数据D以及H中不同假设的先验概率的有关知 识下的最可能假设用P(h)表示在没有训练数据前假设h拥有的初始概率P(h)被称为h的先验概率类似地，P(D)表示训练数据D的先验概率，P(Dlh)表示假设h成立时D的概率机器学习中，我们关心的是P(hlD)，即给定D时h的成立的概率，称为h的后验概率3. 贝叶斯公式提供了从先验概率P(h)、P(D)和P(Dlh)计算后验概率P(hlD)的方法：P (h l D) = P(D | 岫) P( D)4. 学习器在候选假设集合H中寻找给定数据D时可能性最大的假设h，h被称为极大后验假设(Maximum A Posteriori, MAP). 一P (D l h) P (h) h = arg max P(h l D) = arg max = arg max P(D l h)P(h)heH heH P (D) heH5. P(Dlh)常被称为给定h时数据D的似然度，而使P(Dlh)最大的假设被称为极大似然假设(Maximum Likelihood Posteriori, MLP)h = arg max P(D l h)heH贝叶斯推理的结果很大程度上依赖于先验概率，另外不是完全接受或拒绝假设，只是在 观察到较多的数据后增大或减小了假设的可能性。
6. —致学习器：如果某个学习器输出的假设在训练样例上为0错误率，则称为一致学习器如果H上有均匀的先验概率，且训练数据是确定性和无噪声的，任意一致 学习器将输出一个MAP假设7. 通过简单的贝叶斯分析，可以表明在特定前提下，任一学习算法如果使输出的假设预测和 训练数据之间的误差平方和最小化，它将输出一极大似然假设8. 最小描述长度准则(Minimum Description Length, MDL)MDL准则提供了一种方法在假设的复杂性和假设产生错误的数量之间进行折中，它有可能 选择一个较短的产生少量错误的假设，而不是完美地分类训练数据的较长的假设上面讨论自然给出了一种处理数据过度拟合的方法题型设计：贝叶斯最优分类器(P125页)9. 朴素贝叶斯分类器基于一个简单的假定：在给定目标值时属性值之间相互条件独立只要条件独立性得到满足，朴素贝叶斯分类vNB等于MAP分类，否则是近似10. EM算法：期望最大化第八章1・k-近邻算法*****题型设计：计算几个点之间的距离2. 来自统计模式识别领域的术语回归：逼近一个实数值的目标函数残差：逼近目标函数时的误差核函数：一个距离函数，用来决定每个训练样例的权值，就是使wi=K(d(xi,xq))的函数K3. 局部加权回归的名称解释局部：目标函数的逼近仅仅根据查询点附近的数据加权：每个训练样例的贡献由它与查询点间的距离加权得到回归：表示逼近实数值函数的问题4・k-近邻算法和局部加权回归具有三个共同的关键特性：① 消极学习方法② 通过分析相似的实例来分类新的查询实例，而忽略与查询极其不同的实例③ 实例表示为n维欧氏空间中的实数点基于案例的推理（Case-Based Reasoning, CBR）满足前2个原则，但不满足第3个5. 消极方法和积极方法的差异：① 计算时间的差异消极算法在训练时需要较少的计算，但在预测新查询的目标值时需要更多的计算时间② 对新查询的分类的差异（归纳偏置的差异）消极方法在决定如何从训练数据D中泛化时考虑查询实例xq，积极方法在见到xq之前，就完成了泛化 9 9核心观点：消极学习可以通过很多局部逼近的组合表示目标函数，积极学习必须在训练时提交单个的全局逼近第九章1. GA：遗传算法2. 最常见的算子是交叉和变异*****题型设计：单点交叉、两点交叉和均匀交叉的3. 选择假设的概率计算方法① 适应度比例选择（或称轮盘赌选择）：选择某假设的概率是通过这个假设的适应度与当前群体中其他成员的适应度的比值得到的② 锦标赛选择：先从当前群体中随机选取两个假设，再按照事先定义的概率p选择适应度较高的假设，按照概率1-p选择适应度较低的假设③ 排序选择:当前群体中的假设按适应度排序，某假设的概率与它在排序列表中的位置成比例，而不是与适应度成比例4. 遗传算法应用中的一个难题：拥挤问题拥挤：群体中某个体适应度大大高于其他个体，因此它迅速繁殖，以至于此个体和与它相似 的个体占据了群体的绝大部分。
拥挤降低了群体的多样性，从而减慢了进化的进程降低拥挤的策略：① 使用锦标赛选择或排序选择，而不用适应度比例轮盘赌选择② 适应度共享，根据群体中与某个体相似的个体数量，减小该个体的适应度，对可重组生成后代的个体种类进行限制，比如受到生物进化的启示③ 通过只允许最相似的个体重组，可以在群体中促成相似的个体聚类，形成亚种，按空间分布个体，只允许相邻的个体重组第十三章1. 增强学习问题与普通函数逼近问题有几个重要的不同：延迟回报：施教者只在机器人执行其序列动作时提供一个序列立即回报值，因此面临一个时间信用分配的问题：确定最终回报的生成应归功于序列中哪一个动作探索：学习器面临一个权衡过程，是选择探索未知的状态和动作，还是选择利用它已经学习过、会产生高回报的状态和动作部分可观察状态：机器人的传感器只能感知环境的部分状态终生学习：使得有可能使用先前获得的经验或知识在学习新任务时减小样本复杂度2. MDP:马尔可夫决策过程3. Q学习：Q函数*****题型设计：求累计回报，状态V*，以及最优策略（习题13-2）。
