资源描述：
《机器学习汇总》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
彭开香2015.9机器学习(MachineLearning) 平时（10分）课堂出席讨论阅读相关资料，提交报告一份（20分）提交形式（中文科技论文形式电子版）针对某一算法（可以是综述，也可以是算法推导与仿真）考试（70分）课程考核方式 报告建议内容基本概念以及数学定义基本性质及其物理意义具体算法应用（详细举例讲解）该算法与其他类似算法的分析比较可能的发展方向附参考文献3 课件邮箱邮箱：ml_ustb2013@163.com密码：ustb20134 《机器学习》，TomM.Mitchell（汤姆·米切尔）著，曾华军，张银华等译，机械工业出版社，2003年。参考书 其它参考书《机器学习及其应用》，周志华，王钰主编，清华大学出版社，2009。《神经网络与机器学习》，SimonHaykin著，机械工业出版社，2010。《机器学习导论》，EthemAlpaydin著，机械工业出版社，2009。《MachineLearning——AProbabilisticPerspective》KevinP.Murphy,2012 第1章引言什么是机器学习【经典定义】：计算机程序如何随着经验积累自动提高性能，系统自我改进的过程。或：计算机利用经验改善系统自身性能的行为。——米切尔随着该领域的发展，主要做智能数据分析。 学习与智能学习现象语言、文字的认知识别图像、场景、自然物体的认知识别规则（eg下雨天要带雨伞）复杂的推理、判断能力（智能）好人与坏人？好猫与坏猫？数据知识认知推理决策识别学习 什么是机器学习？使得计算机具备和人类一样的学习能力决策推理认知识别……等智能给定数据（样本、实例）和一定的学习规则，从数据中获取知识的能力 机器学习与人工智能自然智慧的伟大与奥妙举例：婴儿的认知能力（声音、人脸、汽车…）重要的二个特点：容错性，推广能力（举一反三）机器智能：希望用机器实现部分智能基于数据的机器学习问题（引自清华张学工教授）根据已知样本估计数据之间的依赖关系，从而对未知或无法测量的数据进行预测和判断关键：推广能力 什么是机器学习中科院王珏研究员给出的定义：令W是给定世界的有限或无限所有观测对象的集合，由于我们的观测能力有限，我们只能获得这个世界的一个子集，称为样本集。机器学习就是根据这个样本集，推算这个世界W的模型，使它对这个世界（尽可能地）为真。三个重要的理论问题：一致：W与Q有相同的性质。eg.i.i.d划分：设样本定义于d维空间，要寻找在这个空间上的决策分界面泛化（推广能力）：对未知样本的判断能力 What’sistheLearningProblem?Learning=ImprovingwithexperienceatsometaskImproveovertaskTWithrespecttoperformancemeasurementPBasedonexperienceEExample:中国象棋任务T：下中国象棋性能目标P：比赛中击败对手（的百分比）训练经验E：和自己进行对弈，或者看棋谱Ref：《机器学习》（曾华军等译） Pedro对学习理解 MachineLearning引用自CMUDr.EricXing的LectureNotes 机器学习的研究意义 机器学习的重要性！《Science》2001年论文：…每个科学领域的科学过程都有它自己的特点，但是，观察、创立假设、根据决定性实验或观察的检验、可理解检验的模型或理论，是各个学科所共有的。对这个抽象的科学过程的每一个环节，机器学习都有相应的发展，我们相信它将导致科学方法中从假设生成、模型构造到决定性实验这些所有环节的合适的、部分的自动化。当前机器学习研究在一些基本论题上取得令人印象深刻的进展，我们预期机器学习研究在今后若干年中将有稳定的进展！”在稍早前，2000年《Science》还发表了另外3篇ML方面的论文“TheManifoldWayofPerceptron”,“Aglobalgeometricframeworkfornonlineardimensionalityreduction”,”Nonlineardimensionalityreductionbylocally…”Mjolsness,DDeCoste,MachineLearningforScience:StateoftheArtandFutureProspects-Science,2001:2051-2055.受到令人惊讶的重视！ 机器学习的重要性摘自南京大学周志华教授生物信息学计算金融学分子生物学行星地质学……工业过程控制机器人……遥感信息处理信息安全机器学习 多学科交叉机器学习也是一个多学科交叉的产物，它吸取了人工智能、概率统计、神经生物学、认知科学、信息论、控制论、计算复杂性理论、哲学等学科的成果。实践证明，机器学习在很多应用领域发挥了重要的实用价值，特别是在数据挖掘、语音识别、图像处理、机器人、车辆自动驾驶、生物信息学、信息安全、遥感信息处理、计算金融学、工业过程控制。 重要性：例子—网络安全入侵检测：是否是入侵？是何种入侵？如何检测？历史数据：以往的正常访问模式及其表现、以往的入侵模式及其表现……对当前访问模式分类这是一个典型的预测型机器学习问题常用技术：神经网络决策树支持向量机k近邻序列分析聚类………… 搜索引擎摘自南京大学周志华教授 重要性：例子—生物信息学常用技术：神经网络支持向量机隐马尔可夫模型k近邻决策树序列分析聚类………… 重要性：例子—数据驱动控制 相关学科对ML的影响人工智能：学习的概念符号表示Bayes方法统计学：统计学习理论(SLT)计算复杂性理论控制论信息论：最小描述长度哲学：“Occam’sRazor原则”，“没有免费午餐”心理学和神经生物学：NeuralNetworks（神经网络） 机器学习目前主要的一些研究领域符号机器学习Eg.决策树，ID3，…计算学习理论（统计学习理论）PAC，SVM监督学习，非监督学习，半监督学习集群机器学习EnsembleLearning，Boosting流行（Manifold）学习强化学习Ranking学习聚类学习… MachineLearningTopicsfromWikihttp://en.wikipedia.org/wiki/Machine_Learning 机器学习简要发展历史回顾 ML的发展历史(1)1950s：神经科学的理论基础James关于神经元是相互连接的发现McCullon&Pitts的神经元模型Hebb学习律（相互连接强弱度的变换规则）1960s：感知器（Perceptron）时代1957年Rosenblatt首次提出 ML的发展历史(2)1969年：《Perceptron》出版，提出著名的XOR问题1970s：符号主义，逻辑推理1980s：MLP+BP算法成功解决XOR问题，从此进入神经网络时代（连接主义）1960s-1970s:统计学习理论创立VC维的基本概念结构风险最小化原则概率空间的大数定律 ML的发展历史(3)1990s：统计学习理论的发展及完善典型代表：SVM（Vapnik，Bell实验室）结构风险最小化最小描述长度原则小样本问题核函数、核空间变化PAC理论下的弱可学习理论的建立支持向量机… ML的发展历史(4)2000s：各种机器学习理论及算法得以充分发展符号机器学习计算机器学习（统计学习理论，典型例子：SVM）集群机器学习（典型代表：Boosting）强化机器学习流行机器学习监督学习，非监督学习半监督学习、…. 未来发展趋势机器实际上是一个应用驱动的学科，其根本的驱动力是：“更多、更好地解决实际问题”由于近20年的飞速发展，机器学习已经具备了一定的解决实际问题的能力，似乎逐渐开始成为一种基础性、透明化的“支持技术、服务技术”基础性：在众多的学科领域都得以应用（“无所不在”）透明化：用户看不见机器学习，看见的是防火墙、生物信息、搜索引擎；（“无所不在”）“机器更好用了”(正如CALO的一些描述：“youwon’tleavehomewithoutit”；”embodiedasasoftwareenvironmentthattranscendsworkstations,PDA’s,cellphones,…”) 讨论议题机器学习的主要策略与基本结构机器学习的主要策略机器学习系统的基本结构 机器学习系统的基本结构我们以西蒙的学习定义做为出发点，建立起下图1.1所示的简单的学习模型，然后通过对这个简单模型的讨论，总结出设计学习系统应当注意的某些总的原则。图1.1学习系统的基本结构 学习问题的标准描述定义如果一个计算机针对某类任务T，用P来衡量性能，根据经验E来自我完善，那么我们称这个计算机程序在从经验E中学习，针对某类任务T，它的性能用P来衡量。西洋跳棋学习问题的解释E，和自己下棋T，参与比赛P，比赛成绩（或赢棋能力，击败对手的百分比）手写识别学习问题机器人驾驶学习问题 学习问题的标准描述（2）定义太宽泛甚至包括了以非常直接的方式通过经验自我提高的计算机程序实际的机器学习问题往往比较复杂定义一类问题探索解决这类问题的方法理解学习问题的基本结构和过程 有监督学习有监督的学习方法在样本标签已知的情况下，可以统计出各类训练样本不同的描述量，如其概率分布，或在特征空间分布的区域等，利用这些参数进行分类器设计，称为有监督的学习方法。 无监督学习无监督学习然而在实际应用中，不少情况下无法预先知道样本的标签，也就是说没有训练样本因而只能从原先没有样本标签的样本集开始进行分类器设计，这就是通常说的无监督学习方法。对一个具体问题来说有监督与无监督的作法是不相同的 有监督学习x1x2 无监督学习x1x2 机器学习的问题存在什么样的算法能从特定的训练数据学习一般的目标函数呢？如果提供了充足的训练数据，什么样的条件下，会使特定的算法收敛到期望的函数？哪个算法对哪些问题和表示的性能最好？多少训练数据是充足的？怎样找到学习到假设的置信度与训练数据的数量及提供给学习器的假设空间特性之间的一般关系？学习器拥有的先验知识是怎样引导从样例进行泛化的过程的？当先验知识仅仅是近似正确时，它们会有帮助吗？关于选择有效的后验训练经验，什么样的策略最好？这个策略的选择会如何影响学习问题的复杂性。怎样把学习任务简化为一个或多个函数逼近问题？换一种方式，系统该试图学习哪些函数？这个过程本身能自动完成吗？学习器怎样自动地改变表示法来提高表示和学习目标函数的能力？ 课程内容简介第2章，基于符号和逻辑表示的概念学习（简介）第3章，决策树第4章，回归模型与神经网络第5章，评估假设第6章，贝叶斯理论（混合模型与EM算法）第7章，基于实例的学习（核函数与径向基函数网络）第8章，马尔科夫与隐马尔可夫模型第9章，支持向量机（线性判别与SVM）第10章，增强学习 参考期刊与会议相关杂志MachineLearningNeuralComputationJournaloftheAmericanStatisticalAssociationIEEEtransactionsonPatternAnalysis&MachineIntelligence国际会议国际机器学习会议ICML神经信息处理系统会议NIPS计算学习理论会议CCLT国际遗传算法会议ICGA 参考学术期刊及国际会议 一些网络资源(1)http://machine-learning.martinsewell.comAAAIMachineLearningTopics：www.aaai.org/AITopics/html/machine.html-SupportVectorMachines：http://www.support-vector-machines.org/index.html 一些网络资源(2)http://www.cs.cmu.edu/~tom/10701_sp11/lectures.shtmlMachineLearning(Spring2011)@CMUTomMitchellVideoLecture&SlidesMachineLearningResources:http://home.earthlink.net/~dwaha/research/machine-learning.html 一些网络资源(3)Weka：DataMining(ML)softwareinJava:http://www.cs.waikato.ac.nz/ml/weka/LibSVM--ALibraryforSupportVectorMachines：www.csie.ntu.edu.tw/~cjlin/libsvmMLC++:http://www.sgi.com/tech/mlc/:AlibraryofC++classesforsupervisedmachinelearningUCI-MachineLearninginformation,softwareanddatabases:http://archive.ics.uci.edu/ml/ 一些网络资源(4)KernalMachines:http://www.kernel-machines.org/http://mloss.org/software/:MachineLearningOpenSourceSoftwarehttp://www3.ntu.edu.sg/home/aswduch/ai-ml.html数据挖掘研究院：http://www.chinakdd.com/ 概念学习给定某一类别的若干正例和反例，从中获得该类别的一般定义。搜索的观点在预定义的假设空间中搜索假设，使其与训练样例有最佳的拟合。利用假设空间的偏序结构算法收敛到正确假设的条件?归纳学习的本质，从训练数据中泛化的理由?第2章概念学习和一般到特殊序 简介许多机器学习涉及到从特殊训练样例中得到一般概念。概念，可被看作一个对象或事件集合，它是从更大的集合中选取的子集，或在这个较大集合中定义的布尔函数。概念学习问题的定义给定一个样例集合以及每个样例是否属于某个概念的标注，怎样推断出该概念的一般定义。又称从样例中逼近布尔函数。概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。 概念学习任务一个例子目标概念Aldo进行水上运动的日子，表示为布尔函数EnjoySport任务目的基于某天的各属性，预测EnjoySport的值给定一个样例集D每个样例表示为6个属性的集合 概念学习任务（2）YesChangeCoolStrongHighWarmSunny4NoChangeWarmStrongHighColdRainy3YesSameWarmStrongHighWarmSunny2YesSameWarmStrongNormalWarmSunny1EnjoySportForecastWaterWindHumidityAirTempSkyExample表2-1目标概念EnjoySport的训练样例 概念学习任务（3）表示假设的形式（目标函数的表示）一个简单的形式，实例的各属性约束的合取式令每个假设为6个约束（或变量）的向量，每个约束对应一个属性可取值范围，为？任意本属性可接受的值明确指定的属性值不接受任何值假设的例子//所有的样例都是正例<,,,,,>//所有的样例都是反例 概念学习任务（4）形式化描述：已知实例集X每个实例x由6个属性描述，每个属性的取值范围已确定假设集H每个假设h描述为6个属性的取值约束的合取目标概念c一个布尔函数，变量为实例训练样例集D目标函数（或目标概念）的正例和反例求解H中的一假设h，使对于X中任意x，h(x)=c(x) 术语定义实例x实例集X概念目标概念c训练样例x训练样例集D正例，目标概念成员反例，非目标概念成员假设h假设集H机器学习的目标就是寻找一个假设h，使得对所有的h，都有h(x)=c(x) 归纳学习假设什么是归纳学习？从特殊的样例得到普遍的规律（从特殊到一般）归纳只能保证输出的假设能与训练样例相拟合归纳假设的一个基本假定对于未见实例最好的假设就是与训练数据最佳拟合的假设归纳学习假设任一假设如果在足够大的训练样例集中很好地逼近目标函数，它也能在未见实例中很好地逼近目标函数。 作为搜索的概念学习概念学习可以看作一个搜索的过程搜索范围：假设的表示所隐含定义的整个空间搜索目标：能够最好地拟合训练样例的假设当假设的表示形式选定后，那么就隐含地为学习算法确定了所有假设的空间例子EnjoySport的假设空间，如果属性Sky有3种可能的值，而AirTemp、Humidity、Wind、Water和Forecast都只有两种可能值。实例空间X：包含3×2×2×2×2×2=96种不同的实例假设空间H包含5×4×4×4×4×4=5120种语法不同的假设由于：包含有符号的假设将每个实例都分类为反例。因此，语义不同的假设只有1+4×3×3×3×3×3=973个。 假设的一般到特殊序假设的一般到特殊序关系考虑下面两个假设h1=h2=任何被h1划分为正例的实例都会被h2划分为正例，因此h2比h1更一般。利用这个关系，无需列举所有假设，就能在无限的假设空间中进行彻底的搜索 假设的一般到特殊序（2）关系“更一般”的精确定义任给实例x和假设h，说x满足h，当且仅当h(x)=1令hj和hk是在X上定义的布尔函数，称hj比hk更一般，当且仅当(xX)[(hk(x)=1)(hj(x)=1)]记为hjmore_general_than_or_equal_tohk，或hjghk 假设的一般到特殊序（3）“更一般”的严格情形hj>ghk，当且仅当，(hjghk)(hkghj)“更特殊”关系的定义hjghk，当且仅当，hkghj以EnjoySport为例说明上面的定义偏序的特点（区别于全序），全序上的搜索可以是二分法，偏序的搜索比无序简单，比全序复杂。这个偏序关系的定义与目标概念无关 h1=h2=h3=x1=x2= Find-S：寻找极大特殊假设使用more_general_than偏序的搜索算法从H中最特殊假设开始，然后在假设覆盖正例失败时将其一般化Find-S算法将h初始化为H中最特殊假设对每个正例x对h的每个属性约束ai如果x满足ai那么不做任何处理否则将h中ai替换为x满足的另一个更一般约束输出假设h Find-S：寻找极大特殊假设（2）Find-S算法在例子EnjoySport上的应用h<,,,,,>hh遇到反例，h不变（因为h已经能够正确地识别反例）h Find-S：寻找极大特殊假设（3）Find-S算法演示了一种利用more_general_than偏序来搜索假设空间的方法，沿着偏序链，从较特殊的假设逐渐转移到较一般的假设。因此，每一步得到的假设都是在那一点上与训练样例一致的最特殊的假设。Find-S的重要特点：对以属性约束的合取式描述的假设空间H，保证输出为H中与正例一致的最特殊的假设。存在的问题是否收敛到了正确的目标概念？为什么要用最特殊的假设？训练样例是否相互一致？如果有多个极大特殊假设怎么办？ 变型空间和候选消除算法候选消除算法概说概念学习的另一种方法，候选消除算法（candidate-elimination）Find-S算法的不足，输出的假设只是H中能够拟合训练样例的多个假设中的一个候选消除算法输出与训练样例一致的所有假设的集合候选消除算法在描述这一集合时不需要明确列举所有成员利用more_general_than偏序结构，可以维护一个一致假设集合的简洁表示候选消除算法的应用：化学质谱分析、启发式搜索的控制规则候选消除算法的缺点：容错性能差 变型空间和候选消除算法（2）“一致”的定义一个假设h与训练样例集合D一致，当且仅当对D中每一个样例都有h(x)=c(x)，即Consistent(h,D)(D)h(x)=c(x)“一致”与“满足”的关系变型空间（VersionSpace）与训练样例一致的所有假设组成的集合表示了目标概念的所有合理的变型关于H和D的变型空间，记为VSH,D，是H中与训练样例D一致的所有假设构成的子集VSH,D={hH|Consistent(h,D)} 变型空间和候选消除算法（3）列表后消除算法表示变型空间的一种方法是列出其所有成员变型空间包含H中所有假设的列表对每个训练样例，从变型空间中移除所有h(x)c(x)的假设输出VersionSpace中的假设列表优点保证得到所有与训练数据一致的假设缺点非常繁琐地列出H中的所有假设，大多数实际的假设空间无法做到 变型空间和候选消除算法（4）变型空间的更简洁表示变型空间被表示为它的极大一般和极大特殊的成员这些成员形成了一般和特殊边界的集合，这些边界在整个偏序结构中划分出变型空间以EnjoySport为例 变型空间和候选消除算法（5）形式化定义极大一般极大特殊关于假设空间H和训练数据D的一般边界G，是在H中与D相一致的极大一般成员的集合关于假设空间H和训练数据D的特殊边界S，是在H中与D相一致的极大特殊成员的集合 变型空间和候选消除算法（6）变型空间表示定理:令X为一任意的实例集合，H为X上定义的布尔假设的集合。令c:X{0,1}为X上定义的任一目标概念，并令D为任一训练样例集合{}。对所有的X,H,c,D以及良好定义的S和G：VSH,D={hH|(sS)(gG)(gghgs)}证明：只需证明：1）每一个满足上式右边的h都在VSH,D中，2）VSH,D的每个成员都满足都满足等式右边。… 变型空间和候选消除算法（7）候选消除算法初始化G和S如果d是一个正例从G中移去所有与d不一致的假设对S中每个与d不一致的假设s从S中移去s把s的所有的极小泛化式h加入到S中，其中h满足h与d一致，而且G的某个成员比h更一般从S中移去所有这样的假设：它比S中另一个假设更一般如果d是一个反例从S中移去所有与d不一致的假设对G中每个与d不一致的假设g从G中移去g把g的所有的极小特殊化式h加入到G中，其中h满足h与d一致，而且S的某个成员比h更特殊从G中移去所有这样的假设：它比G中另一个假设更特殊 变型空间和候选消除算法（8）算法举例{}{}S1:S2:{}G3:S2S3:{}S4:{}G4:G0G1:G0G1G2: 图2-7最终变型空间 变型空间和候选消除的说明候选消除算法收敛到正确的假设训练样例中没有错误H中确实包含描述目标概念的正确假设如果样例中存在错误如果给定足够的训练数据，我们会发现S和G边界收敛得到一个空的变型空间如果目标概念不能由假设表示方式所描述比如是约束的析取∨ 变型空间和候选消除（2）下一步需要什么样的训练样例一般来说，概念学习的最优查询策略，是产生实例以满足当前变型空间中大约半数的假设。这样，变型空间的大小可以在遇到每个新样例时减半，正确的目标概念就可在只用log2|VS|次实验后得到。 变型空间和候选消除（3）怎样使用不完全学习概念虽然图2-7的变型空间中仍包含多个假设，即目标概念还未学习到，但是仍然有可能对新样例进行一定可信度的分类。待分类的新实例 概念的应用 概念的应用判断是否是正例判断是否满足S中的每个假设判断是否是反例判断是否不满足G中的每个假设 归纳偏置有关候选消除算法的几个问题如果目标概念不在假设空间中怎么办？是否可设计一个包含所有假设的空间来解决这一困难？假设空间的大小对于算法推广到未见实例的能力有什么影响？假设空间的大小对所需训练样例的数量有什么影响？ 归纳偏置（2）一个有偏的假设空间在EnjoySport这个例子中，假设空间限制为只包含属性值的合取。（有偏）这一限制，导致假设空间不能够表示最简单的析取形式的目标概念。 归纳偏置（3）无偏的学习器为了保证目标概念在假设空间中，需要提供一个假设空间，它能表达所有的可教授概念。换言之，它能表达实例集X的所有子集。问题：为什么2.3节中合取假设空间只能表示973个假设？ 归纳偏置（4）EnjoySport的无偏形式带来的问题：概念学习算法无法从训练样例中泛化。要想获得单个目标概念，就必须提供X中所有实例作为训练样例使用2.6.3节讨论的部分学习的无效 归纳偏置（5）无偏学习的无用性归纳学习的一个基本属性：学习器如果不对目标概念的形式做预先的假定，它从根本上无法对未见实例进行分类归纳学习需要的预先假定，称为归纳偏置 归纳偏置（6）归纳偏置的精确定义(Dcxi)L(xi,Dc)需要在Dcxi上附加怎样的前提，以使L(xi,Dc)能够演绎派生。L的归纳偏置定义为前提集合B，使所有的新实例满足：(BDcxi)├L(xi,Dc)考虑对于实例集合X的概念学习算法L。令c为X上定义的任一概念，并令Dc为c的任意训练样例集合，L(xi,Dc)表示经过Dc训练后L赋予实例xi的分类。L的归纳偏置是最小断言集合B，它使任意目标概念c和相应的训练样例Dc满足：xiX[(BDcxi)├L(xi,Dc)] 归纳偏置（6）候选消除算法的归纳偏置{cH}InductiveSystemsandEquivalentDeductiveSystems(归纳与演绎) 归纳偏置（7）3个有偏程度不同的归纳学习算法机械式候选消除算法Find-S一种算法的有偏性越强，它的归纳能力越强，可以分类更多的未见实例。某些归纳偏置隐含在学习器中，有些表示为断言集合，可由学习器操作。 小结主要内容概念学习可看作搜索预定义潜在假设空间的过程;假设的一般到特殊偏序结构可以定义在任何概念学习问题中，这种结构便于假设空间的搜索;Find-S算法使用一般到特殊序，在偏序结构的一个分支上执行一般到特殊搜索，寻找一个与样例一致的最特殊假设;候选消除算法利用一般到特殊序，通过渐近地计算极大特殊假设集合和极大一般假设集合发现变型空间；候选消除算法缺少健壮性，后面会描述一些学习算法，它们能够处理有噪声的数据和目标概念无法在假设空间中表示的情况归纳学习算法隐含了归纳偏置，候选消除算法的偏置是：目标概念可以在假设空间中找到。输出的假设和对新实例的分类可由归纳偏置和训练样例演绎推出 思考题2-1.解释为什么EnjoySport学习任务的假设空间的大小为973。如果增加一属性WaterCurrent，可取值Light、Moderate和Strong，那么可能的实例数和可能的假设数将会增加多少？推广到一般，增加一新属性A，有k种取值，实例数和假设数将会增加多少？ 思考题2-2在候选消除算法中，如果训练样例按EnjoySport例子中的逆序出现，请分步给出S和G边界集合。尝试对训练样例排序，以使EnjoySport例子中的所有S和G集合的中间结果的大小之和为最小？YesChangeCoolStrongHighWarmSunny4NoChangeWarmStrongHighColdRainy3YesSameWarmStrongHighWarmSunny2YesSameWarmStrongNormalWarmSunny1EnjoySportForecastWaterWindHumidityAirTempSkyExample 思考题2-3实现Find-S算法和候选消除算法。验证它是否可成功地产生EnjoySport例子中各步骤结果。 第3章决策树学习(Decision-TreeAlgorithm) 排名主题算法得票数发表时间作者陈述人1分类C4.5611993Quinlan,J.RHiroshiMotoda2聚类k-Means601967MacQueen,J.BJoydeepGhosh3统计学习SVM581995Vapnik,V.NQiangYang4关联分析Apriori521994RakeshAgrawalChristosFaloutsos5统计学习EM482000McLachlan,GJoydeepGhosh6链接挖掘PageRank461998Brin,S.ChristosFaloutsos7集装与推进AdaBoost451997Freund,Y.Zhi-HuaZhou8分类kNN451996Hastie,TVipinKumar9分类NaïveBayes452001Hand,D.JQiangYang10分类CART341984L.BreimanDanSteinberg共有145人参加了ICDM2006Panel(会议的专题讨论),并对18种候选算法进行投票，选出了机器学习10大算法ICDM2006会议的算法投票结果 概论决策树学习是应用最广的归纳推理算法之一是一种逼近离散值函数的方法很好的健壮性能够学习析取表达式ID3,Assistant,C4.5搜索一个完整表示的假设空间归纳偏置是优先选择较小的树决策树表示了多个if-then规则 提纲决策树定义适用问题特征基本ID3算法决策树学习的归纳偏置训练数据的过度拟合… 决策树基本概念关于分类问题分类（Classification）任务就是通过学习获得一个目标函数（TargetFunction）f,将每个属性集x映射到一个预先定义好的类标号y。分类任务的输入数据是记录的集合，每条记录也称为实例或者样例。用元组(X,y)表示，其中，X是属性集合，y是一个特殊的属性，指出样例的类标号（也称为分类属性或者目标属性） 决策树基本概念关于分类问题名称体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标号人类恒温毛发是否否是否哺乳动物海龟冷血鳞片否半否是否爬行类鸽子恒温羽毛否否是是否鸟类鲸恒温毛发是是否否否哺乳类Xy分类与回归分类目标属性y是离散的，回归目标属性y是连续的 决策树基本概念解决分类问题的一般方法通过以上对分类问题一般方法的描述，可以看出分类问题一般包括两个步骤：1、模型构建（归纳）通过对训练集合的归纳，建立分类模型。2、预测应用（推论）根据建立的分类模型，对测试集合进行测试。 决策树基本概念解决分类问题的一般方法TIDA1A2A3类1Y100LN2N125SN3Y400LY4N415MN学习算法学习模型模型应用模型TIDA1A2A3类1Y100L？2N125S？3Y400L？4N415M？训练集（类标号已知）检验集（类标号未知）归纳推论 决策树表示法内部节点(包括根节点)指定了对实例的某个属性的测试节点的每个后继分支对应于该属性的一个可能值叶子节点即为实例所属的分类决策树代表实例属性值约束的合取的析取式图3-1概念PlayTennis的决策树OutlookHumidityWindNoYesNoYesYesSunnyRainyOvercastHighNormalStrongWeak 决策树学习的适用问题适用问题的特征实例由“属性-值”对表示目标函数具有离散的输出值可能需要析取的描述训练数据可以包含错误训练数据可以包含缺少属性值的实例问题举例医学中的应用（如根据疾病分类患者、疾病分析与预测）根据起因分类设备故障（故障诊断）根据拖欠支付的可能性分类贷款申请分类问题核心任务是把样例分类到各可能的离散值对应的类别 基本的决策树学习算法ID3大多数决策树学习算法是一种核心算法的变体采用自顶向下的贪婪搜索遍历可能的决策树空间ID3是这种算法的代表该方法使用信息增益度选择测试属性。 ID3算法通过自顶向下构造决策树来进行学习。构造过程：ID3算法的核心问题是选取在树的每个节点要测试的属性。选择根节点－使用统计测试确定每一个实例属性单独分类训练样例的能力，分类能力最好的属性被选作树的根节点为根节点属性的每个可能值产生一个分支，并把训练样例排列到适当的分支重复上面的过程，用每个分支节点关联的训练样例来选取在该点被测试的最佳属性，直到满足以下两个条件中的任一个:1）所有的属性已经被这条路径包括；2）与这个节点关联的所有训练样例具有相同的目标属性值 表3-1用于学习布尔函数的ID3算法ID3(Examples,Target_attribute,Attributes)创建树的root节点如果Examples都为正,返回label=+的单节点树root如果Examples都为反,返回label=-的单节点树root如果Attributes为空，那么返回单节点root，label=Examples中最普遍的Target_attribute值否则开始AAttributes中分类examples能力最好的属性root的决策属性A对于A的每个可能值vi在root下加一个新的分支对应测试A=vi令Examplesvi为Examples中满足A属性值为vi的子集如果Examplesvi为空在这个新分支下加一个叶子节点，节点的label=Examples中最普遍的Target_attribute值否则在新分支下加一个子树ID3（Examplesvi,Target_attribute,Attributes-{A}）结束返回root 最佳分类属性信息增益(InformationGain)用来衡量给定的属性区分训练样例的能力ID3算法在增长树的每一步使用信息增益从候选属性中选择属性用熵度量样例的均一性给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类的熵为信息论中对熵的一种解释，熵确定了要编码集合S中任意成员的分类所需要的最少二进制位数更一般地，如果目标属性具有c个不同的值，那么S相对于c个状态的分类的熵定义为Entropy(S)= S的所有成员属于同一类，Entropy(S)=0；S的正反样例数量相等，Entropy(S)=1；S的正反样例数量不等，熵介于0，1之间 抛一枚均匀硬币的信息熵是多少？解：出现正面与反面的概率均为0.5，信息熵是 用信息增益度量期望的熵降低属性的信息增益，由于使用这个属性分割样例而导致的期望熵降低一个属性A相对样例集合S的信息增益Gain(S,A)被定义为：Values(A)是属性A所有可能值的集合，Sv是S中属性A的值为v的子集Gain(S,A)是在知道属性A的值后可以节省的二进制位数； :+:+::2+,2:E=1sizebigsmall1+,11+,1E=1E=1Gain=1(0.51+0.51)=02+,2:E=1colorredblue2+,10+,1E=0.918E=0Gain=1(0.750.918+0.250)=0.3112+,2:E=1shapecirclesquare2+,10+,1E=0.918E=0Gain=1(0.750.918+0.250)=0.311计算属性的信息增益 DayOutlookTemperatureHumidityWindPlayTennisD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainyMildHighWeakYesD5RainyCoolNormalWeakYesD6RainyCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainyMildNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainyMildHighStrongNo表3-2目标概念PlayTennis的训练样例 HumidityS：[9+,5-]E(S)=0.940HighNormal[3+,4-]E=0.985[6+,1-]E=0.592Gain(S,Humidity)=0.940-(7/14)*0.985-(7/14)*0.592=0.151WindS：[9+,5-]E(S)=0.940WeakStrong[6+,2-]E=0.811[3+,3-]E=1Gain(S,Wind)=0.940-(8/14)*0.811-(6/14)*1=0.048计算属性的信息增益 112考虑表3-2的训练数据所代表的学习任务。创建决策树的根节点。计算每一个候选属性的信息增益，然后选择信息增益最高的一个。Gain（S，Outlook）＝0.246Gain（S，Humidity）＝0.151Gain（S，Wind）＝0.048Gain（S，Temperature）＝0.029根据信息增益标准，属性Outlook被选作根节点的决策属性，并为它的每一个可能值（Sunny、Overcast和Rainy）在根节点下创建分支，得到部分决策树显示在图3-4中。对非终端的后继节点再重复前面的过程以选择一个新的属性来分割训练样例，这一次仅使用与这个节点关联的训练样例，直到满足结束条件。ID3算法示例 DayOutlookTemperatureHumidityWindPlayTennisD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainyMildHighWeakYesD5RainyCoolNormalWeakYesD6RainyCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainyMildNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainyMildHighStrongNo表3-2目标概念PlayTennis的训练样例 114ID3算法步骤1OutlookSunnyRainyOvercast[D1,D2,…,D14][9+,5-][D1,D2,D8,D9,D11][2+,3-][D3,D7,D12,D13][4+,0-][D4,D5,D6,D10,D14][3+,2-]Gain(S,Outlook)=0.246Gain(S,Humidity)=0.151Gain(S,Wind)=0.048Gain(S,Temperature)=0.029 Outlook??YesSunnyOvercastRainD1,2,8,9,11D3,7,12,13D4,5,6,11,14D1~14[9+,5-][2+,3-][4+,0-][3+,2-]什么属性？ID3算法第一步后形成的部分决策树 116ID3算法步骤2HumidityWindHighNormal[D1,D2,D8][0+,3-][D9,D11][2+,0-]StrongWeak[D6,D14][0+,2-][D4,D4,D10][3+,0-]NoYesNoYesYesOutlookSunnyRainyOvercast[D1,D2,…,D14][9+,5-][D1,D2,D8,D9,D11][2+,3-][D3,D7,D12,D13][4+,0-][D4,D5,D6,D10,D14][3+,2-]Gain(SSunny,Humidity)=0.970Gain(SSunny,Temperature)=0.570Gain(SSunny,Wind)=0.019Gain(SRain,Humidity)=0.019Gain(SRain,Temperature)=0.019Gain(SRain,Wind)=0.970 117决策树学习中的假设空间搜索ID3算法搜索的假设空间就是可能的决策树的集合。ID3以爬山算法遍历这个假设空间，引导这种爬山搜索的评估函数是信息增益度量。观察ID3的搜索空间和搜索策略，认识到这个算法的优势和不足：假设空间包含所有的决策树，它是关于现有属性的有限离散值函数的一个完整空间维护单一的当前假设（不同于上章变型空间候选消除算法），不能判断有多少个其他的决策树也与现有的训练数据一致不进行回溯，可能收敛到局部最优每一步都使用当前所有的训练样例，不同于基于单独的训练样例递增作出决定，容错性增强 决策树学习的归纳偏置ID3的搜索策略优先选择较短的树选择那些信息增益高的属性离根节点较近的树很难准确刻画ID3的归纳偏置近似的ID3的归纳偏置较短的树比较长的树优先近似在于ID3得到局部最优，而不一定是全局最优一个精确具有这个归纳偏置的算法，BFS-ID3更贴切近似的归纳偏置较短的树比较长的树优先，信息增益高的属性更靠近根节点的树优先 限定偏置和优选偏置ID3和候选消除算法的比较ID3的搜索范围是一个完整的假设空间，但不彻底地搜索这个空间候选消除算法的搜索范围是不完整的假设空间，但彻底地搜索这个空间ID3的归纳偏置完全是搜索策略排序假设的结果，来自搜索策略候选消除算法完全是假设表示的表达能力的结果，来自对搜索空间的定义 限定偏置和优选偏置优选偏置（搜索偏置）ID3的归纳偏置是对某种假设胜过其他假设的一种优选，对最终可列举的假设没有硬性限制限定偏置（语言偏置）候选消除算法的偏置是对待考虑假设的一种限定通常优选偏置比限定偏置更符合归纳学习的需要优选偏置和限定偏置的结合考虑第1章下棋的例子（优选偏置和限定偏置） 为什么短的假设优先?ID3的归纳偏置的哲学基础奥坎姆剃刀优先选择拟合数据的最简单的假设科学上的例子物理学家优先选择行星运动的简单假设；简单假设的数量远比复杂假设的数量少；简单假设对训练样例的针对性更小，更像是泛化的规律，而不是训练样例的另一种描述。 奥坎姆剃刀设想你是在一条积雪的街上行走。在你前面有一个人带着一顶黑色的高筒礼帽。街对面站着一群男孩，觉得这顶礼帽是个很好的目标，其中一个扔雪球一下击中了帽子。让我们举出两种解释来说明这顶帽子的随后遭遇。第一，在帽子受击的一刹那，一队天使疾飞而下，出其不意地把帽子从那人头上揭走了。第二，雪球把帽子击落了。我们将选择？？种解释。这就是科学上普遍适用的所谓“节俭律”的简单说明。这条定律的意义，就在于说明，最可能的解释就是最好的解释，有时这条定律又被称为奥坎姆剃刀 为什么短的假设优先奥坎姆剃刀的困难可以定义很多小的假设集合，根据什么相信有短描述的决策树组成的小假设集合比其他可定义的小假设集合更适当？假设的规模由学习器内部使用的特定表示决定从生物进化的观点看内部表示和奥坎姆剃刀原则 决策树学习的常见问题决策树学习的实际问题确定决策树增长的深度处理连续值的属性选择一个适当的属性筛选度量标准处理属性值不完整的训练数据处理不同代价的属性提高计算效率针对这些问题，ID3被扩展成C4.5 避免过度拟合数据过度拟合对于一个假设，当存在其它的假设对训练样例的拟合比它差，但事实上在实例的整个分布上表现得却更好时，我们说这个假设过度拟合训练样例。定义：给定一个假设空间H，一个假设hH，如果存在其它的假设h’H，使得在训练样例上h的错误率比h’小，但在整个实例分布上h’的错误率比h小，那么就说假设h过度拟合训练数据。树的规模accuracyontrainingdataontestdata 避免过度拟合数据（2）导致过度拟合的原因（1）一种可能原因是训练样例含有随机错误或噪声SunnyHotNormalStrongPlayTennis＝No 避免过度拟合数据（3）导致过度拟合的原因（2）当训练数据没有噪声时，过度拟合也有可能发生，特别是当少量的样例被关联到叶子节点时，很可能出现巧合的规律性，使得一些属性恰巧可以很好地分割样例，但却与实际的目标函数并无关系。过度拟合使决策树的精度降低（10～25）％ 避免过度拟合数据（4）避免过度拟合的方法及早停止树增长后修剪法两种方法的特点第一种方法更直观第一种方法中，精确地估计何时停止树增长很困难第二种方法被证明在实践中更成功 避免过度拟合数据（5）避免过度拟合的关键使用什么样的准则来确定最终正确树的规模解决方法使用与训练样例截然不同的一套分离的样例，来评估通过后修剪方法从树上修剪节点的效用。使用所有可用数据进行训练，但进行统计测试来估计扩展（或修剪）一个特定的节点是否有可能改善在训练集合外的实例上的性能。使用一个明确的标准来衡量训练样例和决策树的复杂度，当这个编码的长度最小时停止树增长。 避免过度拟合数据（6）方法评述第一种方法是最普通的，常被称为训练和验证集法。可用数据分成两个样例集合：训练集合，形成学习到的假设验证集合，评估这个假设在后续数据上的精度方法的动机：即使学习器可能会被训练集合误导，但验证集合不大可能表现出同样的随机波动验证集合应该足够大，以便它本身可提供具有统计意义的实例样本。常见的做法是，样例的三分之二作训练集合，三分之一作验证集合。 错误率降低修剪将树上的每一个节点作为修剪的候选对象修剪步骤删除以此节点为根的子树，使它成为叶结点把和该节点关联的训练样例的最常见分类赋给它反复修剪节点，每次总是选取那些删除后可以最大提高决策树在验证集合上的精度的节点继续修剪，直到进一步的修剪是有害的为止数据分成3个子集训练样例，形成决策树验证样例，修剪决策树测试样例，精度的无偏估计如果有大量的数据可供使用，那么使用分离的数据集合来引导修剪 决策树学习中错误率降低的修剪效果 规则后修剪从训练集合推导出决策树，增长决策树直到尽可能好地拟合训练数据，允许过度拟合发生将决策树转化为等价的规则集合，方法是为从根节点到叶节点的每一条路径创建一条规则通过删除不会导致估计精度降低的前件来修剪每一条规则按照修剪过的规则的估计精度对它们进行排序，并按这样的顺序应用这些规则来分类后来的实例 规则后修剪（2）例子if(outlook=sunny)(Humidity=High)thenPlayTennis=Noif(outlook=sunny)(Humidity=Normal)thenPlayTennis=Yes…考虑删除先行词(outlook=sunny)或(Humidity=High)选择使估计精度有最大提升的步骤考虑修剪第二个前件作为进一步的修剪步骤 规则后修剪（3）规则精度估计方法使用与训练集不相交的验证集基于训练集合本身被C4.5使用，使用一种保守估计来弥补训练数据有利于当前规则的估计偏置过程先计算规则在它应用的训练样例上的精度然后假定此估计精度为二项式分布，并计算它的标准差对于一个给定的置信区间，采用下界估计作为规则性能的度量评论对于大的数据集，保守预测非常接近观察精度，随着数据集合的减小，离观察精度越来越远不是统计有效（此概念第5章介绍），但是实践中发现有效 规则后修剪（4）把决策树转化成规则集的好处可以区分决策节点使用的不同上下文消除了根节点附近的属性测试和叶节点附近的属性测试的区别提高了可读性 合并连续值属性ID3被限制为取离散值的属性学习到的决策树要预测的目标属性必须是离散的树的决策节点的属性也必须是离散的简单删除上面第2个限制的方法通过动态地定义新的离散值属性来实现，即先把连续值属性的值域分割为离散的区间集合 合并连续值属性（2）例子，Temperature应该定义什么样的基于阈值的布尔属性选择产生最大信息增益的阈值按照连续属性排列样例，确定目标分类不同的相邻实例产生一组候选阈值，它们的值是相应的A值之间的中间值可以证明产生最大信息增益的c值位于这样的边界中（Fayyad1991）通过计算与每个候选阈值关联的信息增益评估这些候选值方法的扩展连续的属性分割成多个区间，而不是单一阈值的两个空间 属性选择的其它度量标准信息增益度量存在一个内在偏置，偏向具有较多值的属性避免方法，其它度量，比如增益比率增益比率通过加入一个被称作分裂信息的项来惩罚多值属性，分裂信息用来衡量属性分裂数据的广度和均匀性SplitInformation(S,A)=GainRatio(S,A)=分裂信息项阻碍选择值为均匀分布的属性问题，当某个SiS。解决方法：采用一些启发式规则，比如仅对增益高过平均值的属性应用增益比率测试 属性选择的其它度量标准（2）基于距离的度量定义了数据划分间的一种距离尺度计算每个属性产生的划分与理想划分间的距离选择最接近完美划分的属性LopezdeMantaras定义了这个距离度量，证明了它不偏向有大量值的属性此外Mingers实验，不同的属性选择度量对最终精度的影响小于后修剪的程度和方法的影响 缺少属性值的训练样例例子，医学领域经常需要根据此属性值已知的实例来估计这个缺少的属性值为了评估属性A是否是决策节点n的最佳测试属性，要计算决策树在该节点的信息增益Gain(S,A)。假定是S中的一个训练样例，并且其属性A的值A(x)未知 缺少属性值的训练样例（2）处理缺少属性值的策略一种策略是赋给它节点n的训练样例中该属性的最常见值另一种策略是赋给它节点n的被分类为c(x)的训练样例中该属性的最常见值更复杂的策略，为A的每个可能值赋予一个概率，而不是简单地将最常见的值赋给A(x) 处理不同代价的属性实例的属性可能与代价相关优先选择尽可能使用低代价属性的决策树，仅当需要产生可靠的分类时才依赖高代价属性通过引入一个代价项到属性选择度量中，可以使ID3算法考虑属性代价Tan和Schlimmer的例子 C4.5改进的具体方面用信息增益率来选择属性克服了用信息增益来选择属性时偏向选择值多的属性的不足。可以处理连续数值型属性采用了一种后剪枝方法对于缺失值的处理 145 小结和补充读物决策树学习为概念学习和学习其他离散值的函数提供了一个实用的方法ID3算法贪婪算法从根向下推断决策树搜索完整的假设空间归纳偏置，较小的树过度拟合问题ID3算法的扩展 参考C4.5Tutorialhttp://www2.cs.uregina.ca/~dbd/cs831/notes/ml/dtrees/c4.5/tutorial.htmlBuildingClassificationModelsID3andC4.5http://www.cis.temple.edu/~ingargio/cis587/readings/id3-c45.html 第4章人工神经网络（ANN） 概述人工神经网络提供了一种普遍且实用的方法从样例中学习值为实数、离散值或向量的函数反向传播算法，使用梯度下降来调节网络参数以最佳拟合由输入—输出对组成的训练集合人工神经网络对于训练数据中的错误健壮性很好人工神经网络已被成功应用到很多领域，例如视觉场景分析，语音识别，机器人控制，工业过程控制 生物学动机ANN受到生物学的启发，生物的学习系统是由相互连接的神经元组成的异常复杂的网络。ANN系统的一个动机就是获得这种基于分布表示的高度并行算法ANN并未模拟生物神经系统中的很多复杂特征ANN的研究分为两个方向使用ANN研究和模拟生物学习过程获得高效的机器学习算法，不管这种算法是否反映了生物过程属于后一个研究方向 适合神经网络学习的问题训练集合为含有噪声的复杂传感器数据，例如来自摄像机和麦克风，工业过程各类传感器数据需要较多符号表示的问题，例如决策树学习的任务，能够取得和决策树学习大体相当的结果反向传播算法是最常用的ANN学习技术 反向传播算法适合问题的特征实例是用很多“属性-值”对表示的目标函数的输出可能是离散值、实数值或者由若干实数属性或离散属性组成的向量训练数据可能包含错误可容忍长时间的训练可能需要快速求出目标函数值人类能否理解学到的目标函数是不重要的 提纲讨论训练单个单元的学习算法介绍组成神经网络的几种主要单元感知器（perceptron）线性单元（linearunit）sigmoid单元（sigmoidunit）给出训练多层网络的反向传播算法讨论几个一般性问题ANN的表征能力假设空间搜索的本质特征过度拟合问题反向传播算法的变体 感知器一种类型的ANN系统是以感知器为基础感知器以一个实数值向量作为输入，计算这些输入的线性组合，如果结果大于某个阈值，就输出1，否则输出-1其中每个wi是一个实数常量，或叫做权值，用来决定输入xi对感知器输出的贡献率。特别地，w0是阈值。 感知器（2）两种简化形式，附加一个常量输入x0=1，前面的不等式写成或写成向量形式为了简短起见，把感知器函数写为其中， 感知器（3）学习一个感知器意味着选择权w0,…,wn的值。所以感知器学习要考虑的候选假设空间H就是所有可能的实数值权向量的集合 感知器的表征能力可以把感知器看作是n维实例空间（即点空间）中的超平面决策面对于超平面一侧的实例，感知器输出1，对于另一侧的实例，输出-1这个决策超平面方程是可以被某个超平面分割的样例集合，称为线性可分样例集合 感知器的表征能力（2）单独的感知器可以用来表示很多布尔函数感知器可以表示所有的原子布尔函数：与、或、与非、或非然而，一些布尔函数无法用单一的感知器表示，例如异或 感知器的表征能力（3）因为所有的布尔函数都可表示为基于原子函数的互连单元的某个网络，因此，感知器网络可以表示所有的布尔函数。事实上，只需要两层深度的网络，比如表示析取范式注意，要把一个AND感知器的输入求反只要简单地改变相应输入权的符号因为感知器网络可以表示大量的函数，而单独的单元不能做到这一点，所以感兴趣的是学习感知器组成的多层网络 感知器训练法则虽然目的是学习由多个单元互连的网络，但还是要从如何学习单个感知器的权值开始单个感知器的学习任务，决定一个权向量，它可以使感知器对于给定的训练样例输出正确的1或-1主要考虑两种算法感知器法则delta法则这两种算法保证收敛到可接受的假设，在不同的条件下收敛到的假设略有不同这两种算法提供了学习多个单元构成的网络的基础 感知器法则算法过程从随机的权值开始反复应用这个感知器到每个训练样例，只要它误分类样例就修改感知器的权值重复这个过程，直到感知器正确分类所有的训练样例感知器训练法则其中 感知器法则（2）为什么这个更新法则会成功收敛到正确的权值呢？一些例子能说明收敛过程可以证明（Minskey&Papert1969）如果训练样例线性可分，并且使用了充分小的否则，不能保证收敛的前提条件：训练样例线性可分 梯度下降和delta法则delta法则克服感知器法则的不足，在线性不可分的训练样本上，收敛到目标概念的最佳近似delta法则的关键思想是:使用梯度下降来搜索可能的权向量的假设空间，以找到最佳拟合训练样例的权向量delta法则为反向传播算法提供了基础，而反向传播算法能够学习多个单元的互连网络对于包含多种不同类型的连续参数化假设的假设空间，梯度下降是必须遍历这样的空间的所有算法的基础 梯度下降和delta法则（2）把delta训练法则理解为训练一个无阈值的感知器指定一个度量标准来衡量假设相对于训练样例的训练误差第6章给出了选择这种E定义的一种贝叶斯论证，在一定条件下，使E最小化的假设就是H中最可能的假设 可视化假设空间根据E的定义，误差曲面是一个抛物面，存在一个单一全局最小值梯度下降搜索从一个任意的初始权向量开始，然后沿误差曲面最陡峭下降的方向，以很小的步伐反复修改这个向量，直到得到全局的最小误差点 梯度下降法则的推导如何发现沿误差曲面最陡峭下降的方向？通过计算E相对向量的每个分量的导数，这个向量导数被称为E对于的梯度，记作当梯度被解释为权空间的一个向量时，它确定了使E最陡峭上升的方向，所以这个向量的反方向给出了最陡峭下降的方向梯度训练法则其中，也可写成分量形式： 梯度下降法则的推导（2）需要一个高效的方法在每一步都计算这个梯度梯度下降权值更新法则（式4.7） 梯度下降法则的推导（3）训练线性单元的梯度下降算法Gradient-Descent(training_examples,)training_examples中每个训练样例形式为序偶<,t>，是输入值向量，t是目标输出值，是学习速率初始化每个wi为某个小的随机值遇到终止条件之前，做以下操作初始化每个wi为0对于训练样例training_examples中的每个<,t>，做把实例输入到此单元，计算输出o对于线性单元的每个权增量wi，做wiwi+(t-o)xi对于线性单元的每个权wi，做wiwi+wi 梯度下降法则的推导（4）梯度下降算法如下选取一个初始的随机权向量应用线性单元到所有的训练样例，根据公式4.7计算每个权值的更新权值因为误差曲面仅包含一个全局的最小值，所以无论训练样例是否线性可分，算法都会收敛到具有最小误差的权向量，条件是使用足够小的学习速率算法的一种常用改进方法是随着梯度下降步数的增加逐渐减小学习速率（变学习率） 梯度下降的随机近似梯度下降是一种重要的通用学习范型，它是搜索庞大假设空间或无限假设空间一种策略梯度下降应用于满足以下条件的任何情况假设空间包含连续参数化的假设误差对于这些假设参数可微梯度下降的主要实践问题有时收敛过程可能非常慢如果在误差曲面上有多个局部极小值，那么不能保证找到全局最小值 梯度下降的随机近似（2）随机梯度下降（或称增量梯度下降）根据某个单独样例的误差增量计算权值更新，得到近似的梯度下降搜索（随机取一个样例）对梯度下降算法的修改wi(t-o)xi，wiwi+wi可以看作为每个单独的训练样例定义不同的误差函数在迭代所有训练样例时，这些权值更新的序列给出了对于原来误差函数的梯度下降的一个合理近似通过使下降速率的值足够小，可以使随机梯度下降以任意程度接近于真实梯度下降 梯度下降的随机近似（3）标准梯度下降和随机梯度下降之间的关键区别标准梯度下降是在权值更新前对所有样例汇总误差，而随机梯度下降的权值是通过考查每个训练样例来更新的在标准梯度下降中，权值更新的每一步对多个样例求和，需要更多的计算标准梯度下降，由于使用真正的梯度，标准梯度下降对于每一次权值更新经常使用比随机梯度下降大的步长如果标准误差曲面有多个局部极小值，随机梯度下降有时可能避免陷入这些局部极小值实践中，标准和随机梯度下降方法都被广泛应用 梯度下降的随机近似（4）delta法则（增量法则），又称LMS法则、Adaline法则、Windrow-Hoff法则增量法则与感知器法则的相似和区别delta法则可以学习非阈值线性单元的权，也可以用来训练有阈值的感知器单元。如果非阈值输出能够被训练到完美拟合这些值，那么阈值输出也会完美拟合它们即使不能完美地拟合目标值，只要线性单元的输出具有正确的符号，阈值输出就会正确拟合目标值尽管这个过程会得到使线性单元输出的误差最小化的权值，但这些权值不能保证阈值输出的误差最小化 感知器学习小结感知器法则和delta法则的关键差异前者根据阈值化的感知器输出的误差更新权值后者根据输入的非阈值化线性组合的误差来更新权值这个差异带来不同的收敛特性前者经过有限次的迭代收敛到一个能理想分类训练数据的假设，条件是训练样例线性可分后者可能经过极长的时间，渐近收敛到最小误差假设，但无论训练样例是否线性可分都会收敛 感知器学习小结（2）学习权向量的第3种方法是线性规划线性规划是解线性不等式方程组的一种通用的有效方法这种方法仅当训练样例线性可分时有解Duda和Hart给出了一种更巧妙的适合非线性可分的情况的方法更大的问题是，无法扩展到训练多层网络，而delta法则可以很容易扩展到多层网络 多层网络和反向传播算法多层网络能够表示种类繁多的非线性曲面典型的多层网络outputhiddeninputactivation 可微阈值单元使用什么类型的单元来构建多层网络？多个线性单元的连接仍产生线性函数，而我们希望构建表征非线性函数的网络感知器单元可以构建非线性函数，但它的不连续阈值使它不可微，不适合梯度下降算法我们需要的单元满足的条件输出是输入的非线性函数输出是输入的可微函数Sigmoid单元，类似于感知器单元，但基于一个平滑的可微阈值函数 可微阈值单元（2）sigmoid单元先计算它的输入的线性组合，然后应用到一个阈值上，阈值输出是输入的连续函数其中 可微阈值单元（3）sigmoid函数也称logistic函数挤压函数输出范围是0到1单调递增导数很容易用函数本身表示sigmoid函数的变型其他易计算导数的可微函数增加陡峭性双曲正切函数netjTj01 反向传播算法用来学习多层网络的权值采用梯度下降方法试图最小化网络输出值和目标值之间的误差平方网络的误差定义公式，对所有网络输出的误差求和 反向传播算法（2）反向传播算法面临的学习任务搜索一个巨大的假设空间，这个空间由网络中所有的单元的所有可能的权值定义，得到与前面类似的误差曲面在多层网络中，误差曲面可能有多个局部极小值，梯度下降仅能保证收敛到局部极小值尽管有这个障碍，已经发现对于实践中很多应用，反向传播算法都产生了出色的结果 反向传播算法（3）包含两层sigmoid单元的前馈网络的反向传播算法BackPropagation(training_examples,,nin,nout,nhidden)training_examples是序偶<,>的集合，是网络输入值向量，是目标输出值。是学习速率，nin是网络输入的数量，nhidden是隐藏层单元数，nout是输出单元数创建具有nin个输入，nhidden个隐层，nout个输出单元的网络初始化所有的网络权值为小的，从单元i到单元j的输入表示为xji，单元i到单元j的权值表示为wji。随机值在遇到终止条件前对于训练样例training_examples中的每个<,>：把输入沿网络前向传播把实例输入网络，并计算网络中每个单元u的输出ou使误差沿网络反向传播对于网络的每个输出单元k，计算它的误差项kok(1-ok)(tk-ok)对于网络的每个隐层单元h，计算它的误差项更新每个网络权值wjiwji+wji，其中wji=jxji 反向传播算法（4）前面给出的反向传播算法适用于包含两层sigmoid单元的分层前馈网络，并且每一层的单元与前一层的所有单元相连。是反向传播算法的增量梯度下降（或随机梯度下降）版本使用的符号做了如下扩展网络中每个节点被赋予一个序号，这里的节点要么是网络的输入，要么是网络中某个单元的输出xji表示节点i到单元j的输入，wji表示对应的权值n表示与单元n相关联的误差项。 算法解释从建立一个具有期望数量的隐层单元和输出单元的网络并初始化所有的网络的权值为小的随机数开始给定一个固定的网络结构，算法的主循环就对训练样例进行反复的迭代对于每一个训练样例，它应用目前的网络到这个样例，计算出对这个样例网络输出的误差，然后更新网络中所有的权值对这样的梯度下降步骤进行迭代，直到网络的性能达到可接受的精度为止 反向传播算法的梯度下降法则算法中的梯度下降权更新法则与delta训练法则相似类似delta法则，依照以下三者来更新每一个权学习速率该权值涉及的输入值xji该单元的输出误差不同于delta法则的地方delta法则中的误差项被替换成一个更复杂的误差项j 反向传播算法的误差项输出单元k的误差项k与delta法则中的(tk-ok)相似，但乘上了sigmoid挤压函数的导数ok(1-ok)。隐层单元h的误差项因为训练样例仅对网络的输出提供了目标值tk，所以缺少直接的目标值来计算隐层单元的误差值采取以下的间接方法计算隐层单元的误差项：对受隐层单元h影响的每一个单元的误差k进行加权求和，每个误差k权值为wkh，wkh就是从隐层单元h到输出单元k的权值。这个权值刻画了隐层单元h对于输出单元k的误差应负责的程度。 算法解释（2）算法随着每个训练样例的出现而递增地更新权，这一点与梯度下降的随机近似算法一致要取得误差E的真实梯度，需要在修改权值之前对所有训练样例的jxji值求和在典型的应用中，权值的更新迭代会被重复上千次有很多终止条件可以用来停止这个过程迭代的次数到了一个固定值时停止当在训练样例上的误差降到某个阈值以下在分离的验证样例集合上的误差符合某个标准终止条件很重要，太少的迭代无法有效地降低误差，太多的迭代会导致对训练数据的过度拟合 增加冲量项因为反向传播算法的应用如此广泛，所以已经开发出了很多反向传播算法的变体修改权值更新法则，使第n次迭代时的权值的更新部分地依赖于发生在第n-1次迭代时的更新，比如wji(n)=jxji+wji(n-1)右侧第一项就是前面算法中的权值更新法则，第二项被称为冲量项梯度下降的搜索轨迹就像一个球沿误差曲面滚下，冲量使球从一次迭代到下一次迭代时以同样的方向滚动冲量有时会使这个球滚过误差曲面的局部极小值或平坦区域冲量也具有在梯度不变的区域逐渐增大搜索步长的效果，从而加快收敛 学习任意的无环网络算法可以简单地推广到任意深度的前馈网络第m层的单元r的r值由更深的第m+1层值根据下式计算将这个算法推广到任何有向无环结构也同样简单，而不论网络中的单元是否被排列在统一的层上，计算任意内部单元的的法则是：，Downstream(r)是在网络中单元r的直接下游单元的集合，即输入中包括r的输出的所有单元 反向传播法则的推导随机梯度下降算法迭代处理训练样例，每次处理一个，对于每个训练样例d，利用关于这个样例的误差Ed的梯度修改权值 符号说明xji，单元j的第i个输入wji，与xji相关联的权值netj，单元j的输入的加权和oj，单元j计算出的输出tj，单元j的目标输出，sigmoid函数outputs，网络最后一层的输出单元的集合Downstream(j)，单元j的输出到达的单元的集合 随机梯度下降法则的推导分情况讨论 的推导输出单元 随机梯度下降法则的推导（２）隐层单元 收敛性和局部极小值对于多层网络，误差曲面可能含有多个不同的局部极小值，梯度下降可能陷入这些局部极小值中的任何一个对于多层网络，反向传播算法仅能保证收敛到误差E的某个局部极小值，不一定收敛到全局最小误差尽管缺乏对收敛到全局最小误差的保证，反向传播算法在实践中仍是非常有效的函数逼近算法 收敛性和局部极小值（２）网络的权越多，误差曲面的维数越多，也就越可能为梯度下降提供更多的逃逸路线考虑随着训练中迭代次数的增加网络权值的演化方式如果把网络的权值初始化为接近于0的值，那么在早期的梯度下降步骤中，网络将表现为一个非常平滑的函数，近似为输入的线性函数，这是因为sigmoid函数本身在权值靠近0时接近线性仅当权值增长一定时间后，它们才会到达可以表示高度非线性网络函数的程度，可以预期在这个能表示更复杂函数的权空间区域存在更多的局部极小值但是当权到达这一点时，它们已经足够靠近全局最小值，即便它是这个区域的局部最小值也是可以接受的 收敛性和局部极小值（3）用来缓解局部极小值问题的启发式规则为梯度更新法则加一个冲量，可以带动梯度下降过程，冲过狭窄的局部极小值（原则上，也可能冲过狭窄的全局最小值）使用随机的梯度下降而不是真正的梯度下降。随机近似对于每个训练样例沿一个不同的误差曲面有效下降，这些不同的误差曲面通常有不同的局部极小值，这使得下降过程不太可能陷入一个局部极小值使用同样的数据训练多个网络，但用不同的随机权值初始化每个网络。如果不同的训练产生不同的局部极小值，那么对分离的验证集合性能最好的那个网络将被选中，或者保留所有的网络，输出是所有网络输出的平均值 前馈网络的表征能力布尔函数：任何布尔函数可以被具有两层单元的网络准确表示，尽管在最坏情况下所需隐层单元的数量随着网络输入数量的增加成指数级增长。考虑下面的通用方案：对于每一个可能的输入向量，创建不同的隐层单元，并设置它的权值使当且仅当这个特定的向量输入到网络时该单元被激活，这样就产生了一个对于任意输入仅有一个单元被激活的隐藏层，然后把输出单元实现为一个仅由所希望的输入模式激活的或门。 前馈网络的表征能力（2）连续函数：每个有界的连续函数可以由一个两层的网络以任意小的误差逼近。这个结论适用于在隐藏层使用sigmoid单元、在输出层使用（非阈值）线性单元的网络。所需的隐层单元数量依赖于要逼近的函数。任意函数：任意函数可以被一个有三层单元的网络以任意精度逼近。两个隐藏层使用sigmoid单元，输出层使用线性单元，每层所需单元数不确定。证明方法：首先说明任意函数可以被许多局部化函数的线性组合逼近，这些局部化函数的值除了某个小范围外都为0；然后说明两层的sigmoid单元足以产生良好的局部逼近注意：梯度下降从一个初始值开始，因此搜索范围里的网络权向量可能不包含所有的权向量 假设空间搜索和归纳偏置反向传播算法的假设空间是n个网络权值形成的n维欧氏空间。这个空间是连续的，与决策树学习和其它基于离散表示的方法的假设空间不同假设空间的连续性以及误差E关于假设的连续参数可微，导致了一个定义良好的误差梯度，为最佳假设的搜索提供了一个非常有用的结构。精确地刻画出反向传播学习的归纳偏置是有难度的，它依赖于梯度下降搜索和权空间覆盖可表征函数空间的方式的相互作用性把这一偏置粗略地刻画为在数据点之间平滑插值。如果给定两个正例，它们之间没有反例，反向传播算法会倾向于把这两点之间的点也标记为正例 隐藏层表示反向传播算法的一个迷人特性是：它能够在网络内部的隐藏层发现有用的中间表示训练样例仅包含网络输入和输出，权值调节的过程可以自由地设置权值，来定义任何隐层单元表示，这些隐层单元表示在使误差E达到最小时最有效。引导反向传播算法定义新的隐藏层特征，这些特征在输入中没有明确表示出来，但能捕捉输入实例中与学习目标函数最相关的特征多层网络在隐藏层自动发现有用表示的能力是ANN学习的一个关键特性。允许学习器创造出设计者没有明确引入的特征。网络中使用的单元层越多，就可以创造出越复杂的特征 目标函数 泛化、过度拟合和停止判据权值更新算法的终止条件一种选择是，对训练样例的误差降低至某个预先定义的阈值之下这不是一个好的策略，因为反向传播算法容易过度拟合训练样例，降低对于其他未见实例的泛化精度泛化精度：网络拟合训练数据外的实例的精度必须小心不要过早停止训练 errorontrainingdataontestdata0#trainingepochs尽管在训练样例上的误差持续下降，但在验证样例上测量到的误差先下降，后上升。因为这些权值拟合了训练样例的“特异性”，而这个特异性对于样例的一般分布没有代表性。ANN中大量的权值参数为拟合这样的“特异性”提供了很大的自由度 过度拟合为什么过度拟合发生在迭代的后期，而不是早期？设想网络的权值是被初始化为小随机值的，使用这些几乎一样的权值仅能描述非常平滑的决策面随着训练的进行，一些权值开始增长，以降低在训练数据上的误差，同时学习到的决策面的复杂度也在增加如果权值调整迭代次数足够多，反向传播算法可能会产生过度复杂的决策面，拟合了训练数据中的噪声和训练样例中没有代表性的特征 过度拟合解决方法权值衰减它在每次迭代过程中以某个小因子降低每个权值，这等效于修改E的定义，加入一个与网络权值的总量相应的惩罚项，此方法的动机是保持权值较小，从而使学习过程向着复杂决策面的反方向偏置验证数据一个最成功的方法是在训练数据外再为算法提供一套验证数据，应该使用在验证集合上产生最小误差的迭代次数，不是总能明显地确定验证集合何时达到最小误差 过度拟合解决方法（2）一般而言，过度拟合是一个棘手的问题交叉验证方法在可获得额外的数据提供验证集合时工作得很好，但是小训练集合的过度拟合问题更为严重k-fold交叉验证把训练样例分成k份，然后进行k次交叉验证过程，每次使用不同的一份作为验证集合，其余k-1份合并作为训练集合。每个样例会在一次实验中被用作验证样例，在k-1次实验中被用作训练样例每次实验中，使用上面讨论的交叉验证过程来决定在验证集合上取得最佳性能的迭代次数，然后计算这些迭代次数的均值最后，运行一次反向传播算法，训练所有m个实例并迭代次 隐层单元个数的确定较少的隐层单元可防止网络过度拟合数据应用交叉验证方法确定隐层单元数errorontrainingdataontestdata0#hiddenunits 举例：人脸识别训练样例20个不同人的摄影图像每个人大约32张图像不同的表情快乐、沮丧、愤怒、中性不同的方向左、右、正前、上不同的穿戴是否带眼镜共624幅灰度图像分辨率为120×128，每个像素使用0（黑）到255（白）的灰度值描述任务：学习图像中人脸的朝向 共搜集624幅灰度图像，训练了240幅图像样例后，独立测试集合的精度达90％，20个不同的人 人脸识别——设计要素输入编码ANN的输入必然是图像的某种表示，那么设计的关键是如何编码这幅图像例如，可以对图像进行预处理，分解出边缘、亮度一致的区域或其他局部图像特征，然后把这些特征输入网络，问题是导致每幅图像有不同数量的特征参数，而ANN具有固定数量的输入单元把图像编码成固定的30×32像素的亮度值，每个像素对应一个网络输入，把范围是0到255的亮度值按比例线性缩放到0到1的区间内，以使网络输入和隐层单元、输出单元在同样的区间取值。 人脸识别——设计要素（2）输出编码ANN必须输出4个值中的一个来表示输入图像中人脸的朝向可以使用单一的输出单元来编码这4种情况这里使用4个不同的输出单元，每一个对应4种可能朝向中的一种，取具有最高值的输出作为网络的预测值。称为1-of-n输出编码选择1-of-n的原因为网络表示目标函数提供了更大的自由度最高值输出和次高值输出间的差异可以作为对网络预测的置信度 人脸识别——设计要素（3）输出单元的目标值一个显而易见的方法，<1,0,0,0>...这里使用的方法，<0.9,0.1,0.1,0.1>...避免使用0和1作为目标值的原因sigmoid单元对于有限权值不能产生这样的输出如果企图训练网络来准确匹配目标值0和1，梯度下降将会迫使权值无限增长0.1和0.9是sigmoid单元在有限权值情况下可以完成的 人脸识别——设计要素（4）网络结构图网络包含多少个单元以及如何互连？最普遍的结构是分层网络，一层的每个单元向前连接到下一层的每一个单元目前采用了包含两层sigmoid单元的标准结构隐藏单元的数量3个，达到90%的精度，训练时间约5分钟30个，提高1~2个百分点，训练时间约1个小时实践发现，需要某个最小数量的隐藏单元来精确地学习目标函数，并且超过这个数量的多余的隐藏单元不会显著地提高泛化精度如果没有使用交叉验证，那么增加隐藏单元数量经常会增加过度拟合训练数据的倾向，从而降低泛化精度 人脸识别——设计要素（5）学习算法的其他参数学习速率设定为0.3，冲量设定为0.3太小会产生大体相当的泛化精度，但需要更长的训练时间太大，训练将不能收敛到一个具有可接受误差的网络使用完全的梯度下降输出单元的权值被初始化为小的随机值输入单元的权值被初始化为0训练的迭代次数的选择可以通过分割可用的数据为训练集合和验证集合来实现最终选择的网络是对验证集合精度最高的网络最终报告的精度是在没有对训练产生任何影响的第三个集合——测试集合上测量得到的 学习到的隐藏层表示图中紧挨人脸图像下的4个矩形，每个矩形描绘了网络中4个输出单元中的一个权值，每个矩形中的4个小方形表示和这个输出单元关联的4个权值隐藏单元的权值显示在输出单元的下边，每个隐藏单元接受所有30×32个像素输入。与这些输入关联的30×32个权值被显示在它们对应的像素的位置针对每一个训练样例，梯度下降迭代100次后的网络权值显示在图的下部。 其它可选的误差函数为权值增加一个惩罚项把一个随着权向量幅度增长的项加入到E中，这导致梯度下降搜寻较小的权值向量，从而减小过度拟合的风险，等价于使用权衰减策略对误差增加一项目标函数的斜率或导数某些情况下，训练信息中不仅有目标值，而且还有关于目标函数的导数 其它可选的误差函数（2）使网络对目标值的交叉熵最小化比如根据借贷申请者的年龄和存款余额，预测他是否会还贷，目标函数最好以申请者还贷的概率的形式输出，而不是输出明确的0和1。在这种情况下，可以证明最小化交叉熵的网络可以给出最好的概率估计。交叉熵定义如下：第6章讨论了何时及为什么最可能的网络假设就是使交叉熵最小化的假设，并推导了相应的sigmoid单元的梯度下降权值调整法则，还描述了在什么条件下最可能的假设就是使误差平方和最小化的假设。 其他可选的误差函数（3）通过权值共享改变有效误差函数把与不同单元或输入相关联的权“捆绑在一起”，强迫不同的网络权值取一致的值，通常是为了实施人类设计者事先知道的某个约束约束了假设的潜在空间，减小了过度拟合的风险实现方法，首先在共享权值的每个单元分别更新各个权值，然后取这些权值的平均，再用这个平均值替换每个需要共享的权值。被共享的权值比没有共享的权值更有效地适应一个不同的误差函数 其它可选的误差最小化过程梯度下降是搜寻使误差函数最小化的假设的最通用的方法之一，但不是最高效的不妨把权值更新方法看作是要决定这样两个问题：选择一个改变当前权值向量的方向（梯度的负值）选择要移动的距离（学习速率）线搜索，每当选定了一条确定权值更新方向的路线，那么权更新的距离是通过沿这条线寻找误差函数的最小值来选择的共轭梯度，进行一系列线搜索来搜索误差曲面的最小值，这一系列搜索的第一步仍然使用梯度的反方向，在后来的每一步中，选择使误差梯度分量刚好为0并保持为0的方向像共轭梯度这样的方法对最终网络的泛化误差没有明显的影响，唯一可能的影响是，不同的误差最小化过程会陷入不同的局部最小值 递归网络递归网络是有如下特征的人工神经网络适用于时序数据使用网络单元在时间t的输出作为其它单元在时间t+1的输入递归网络支持在网络中使用某种形式的有向环考虑一个时序预测任务根据当天的经济指标x(t)，预测下一天的股票平均市值y(t+1)训练一个前馈网络预测输出y(t+1)，图4-11a 递归网络预测y(t+1)时，考虑任意过去的时间窗内的信息，图4-11b图4-11b那样的递归网络可以使用反向传播算法的简单变体来训练把递归网络拷贝成几份，用不同拷贝间的连接替换掉反馈环，这个大的网络不再包含回路，所以可以直接使用反向传播算法来训练实践中，我们仅保留一份递归网络和权值集合的拷贝，在训练了展开的网络后，可以取不同拷贝中权值的平均值作为最终网络的对应的权值实践中，递归网络比没有反馈环的网络更难以训练，泛化的可靠性也不如后者，然而它们仍因较强的表征力而保持着重要性 动态修改网络结构动态增长或压缩网络单元和单元间连接的数量从一个不包含隐藏单元的网络开始，然后根据需要增加隐藏单元来增长网络，直到训练误差下降到某个可接受的水平级联相关算法，每当加入一个新的隐藏单元，它的输入包括所有原始的网络输入和已经存在的隐藏单元的输出，网络以这种方式增长，积聚隐藏单元，直到网络的残余误差下降到某个可接受的水平由于每一步仅有一层网络在被训练，级联相关算法显著减少了训练时间算法的一个实际困难是，因为算法可以无限制地增加单元，很容易过度拟合训练数据。 动态修改网络结构从一个复杂的网络开始修剪掉某些连接判断某个权是否无关紧要的一种方法是看它的值是否接近0在实践中更加成功的方法是考虑这个权值的一个小的变化对误差的影响（连接的显著性）最不显著的连接被拆除，重复这个过程，直到遇到某个终止条件为止（最优脑损伤法）一般而言，动态修改网络结构的方法能否稳定地提高反向传播算法的泛化精度还有待研究 小结人工神经网络为学习实数值和向量值函数提供了一种实际的方法，对于连续值和离散值的属性都可以使用，并且对训练数据中的噪声具有很好的健壮性。反向传播算法是最常见的网络学习算法反向传播算法考虑的假设空间是固定连接的有权网络所能表示的所有函数的空间包含3层单元的前馈网络能够以任意精度逼近任意函数，只要每一层有足够数量的单元。即使是一个实际大小的网络也能够表示很大范围的高度非线性函数反向传播算法使用梯度下降方法搜索可能假设的空间，迭代减小网络的误差以拟合训练数据 小结（2）梯度下降收敛到训练误差相对网络权值的局部极小值。只要训练误差是假设参数的可微函数，梯度下降可用来搜索很多连续参数构成的假设空间反向传播算法能够创造出网络输入中没有明确出现的特征。交叉验证方法可以用来估计梯度下降搜索的合适终止点，从而最小化过度拟合的风险其他ANN学习算法，递归网络方法训练包含有向环的网络，级联相关算法改变权和网络结构 补充读物本书其他与ANN学习相关的章节第6章给出了选择最小化误差平方和的贝叶斯论证，以及在某些情况下，用最小化交叉熵代替最小化误差平方和的方法第7章讨论了为可靠学习布尔函数所需要的训练实例数量的理论结果，以及某些类型网络的VC维第5章讨论了过度拟合和避免过度拟合的方法第12章讨论了使用以前知识来提高泛化精度的方法 补充读物（2）发展历程McCulloch&PittsWidrow&HoffRosenblattMinsky&PapertRumelhart&McClelland;Parker教科书Duda&HartWindrow&StearnsRumelhart&McClelland 第5章算法的评估与比较(EvaluatingHypotheses) 概述对学习算法的精度进行评估是机器学习中的基本问题本章用统计方法估计算法精度，主要解决以下三个问题：已知一个假设在有限数据样本上观察到的精度，怎样估计它在其它实例上的精度？即如何评估一个学习算法在给定问题上的期望误差率？如果一个算法在某些数据样本上好于另一个，那么一般情况下该算法是否更准确？即给定两个学习算法，如何就给定应用来判断一个算法的误差率比另一个低。当数据有限时，怎样高效地利用这些数据，通过它们既能学习到假设，还能估计其精度？统计的方法，结合有关数据基准分布的假定，可以用有限数据样本上的观察精度来逼近整个数据分布上的真实精度。 动机对学习到的假设进行尽可能准确地性能评估十分重要为了知道是否可以使用该假设是许多学习方法的重要组成部分当给定的数据集有限时，要学习一个概念并估计其将来的精度，存在两个很关键的困难：估计的困难使用与训练样例和假设无关的测试样例估计的方差即使假设精度在独立的无偏测试样例上测量，得到的精度仍可能与真实精度不同。测试样例越少，产生的方差越大重点讨论对学到的假设的评估、对两个假设精度的比较、两个学习算法精度的比较 学习问题的框架有一所有可能实例的空间X，其中定义了多个目标函数，假定X中不同实例具有不同的出现频率。一种合适的建模方式是，假定存在一未知的概率分布D，它定义了X中每一实例出现的概率。学习任务是在假设空间上学习一个目标概念，训练样例的每一个实例按照分布D独立地抽取，然后连同正确的目标值提供给学习器。 评估假设的问题给定假设h和包含若干按D分布抽取的样例的数据集，如何针对将来按同样分布抽取的实例，得到对h的精度最好估计这一精度估计的可能的误差是多少 样本错误率和真实错误率定义：假设h关于目标函数f和数据样本S的样本错误率（标记为errors(h)）定义：假设h关于目标函数f和分布D的真实错误率（标记为errorD(h)） 样本错误率和真实错误率（2）想知道的是假设的真实误差，因为这是在分类未来样例时可以预料到的误差。能测量的只是样本错误率，因为样本数据是我们知道的。要考虑的问题是：样本错误率在何种程度上提供了对真实错误率的估计？ 离散值假设的置信区间先考虑离散值假设的情况，比如：样本S包含n个样例，它们的抽取按照概率分布D，抽取过程是相互独立的，并且不依赖于假设hn>=30假设h在这n个样例上犯了r个错误根据上面的条件，统计理论可以给出以下断言：没有其它信息的话，真实错误率errorD(h)最可能的值是样本错误率errorS(h)=r/n有大约95%的可能性，真实错误率处于下面的区间内： 举例说明数据样本S包含n=40个样例，并且假设h在这些数据上产生了r=12个错误，这样样本错误率为errorS(h)=12/40=0.3如果没有更多的信息，对真实错误率errorD(h)的最好的估计即为0.3如果另外收集40个随机抽取的样例S’，样本错误率errorS’(h)将与原来的errorS(h)存在一些差别如果不断重复这一实验，每次抽取一个包含40样例的样本，将会发现约95%的实验中计算所得的区间包含真实错误率将上面的区间称为errorD(h)的95%置信区间估计 置信区间表达式的推广常数1.96是由95%这一置信度确定的定义zN为计算N%置信区间的常数（取值见下），计算errorD(h)的N%置信区间的一般表达式（公式5.1）为：（5.1）可以求得同样情况下的68%置信区间，从直觉上可以看出68%置信区间要小于95%置信区间，因为减小了要求errorD(h)落入的概率confidencelevel50%68%80%90%95%98%99%z-score0.671.001.281.641.962.332.58 置信区间表达式的推广（2）公式5.1只能应用于离散值假设，它假定样本S抽取的分布与将来的数据抽取的分布相同，并且假定数据不依赖于所测试的假设；公式5.1只提供了近似的置信区间，这一近似在至少包含30个样例，并且errorS(h)不太靠近0或1时很接近真实情况判断这种近似是否接近真实的更精确规则是： 统计学中的基本定义和概念随机变量某随机变量Y的概率分布随机变量Y的期望值或均值随机变量的方差Y的标准差二项分布正态分布中心极限定理估计量Y的估计偏差N%置信区间 错误率估计和二项比例估计样本错误率和真实错误率之间的差异与数据样本大小的依赖关系如何？给定从总体中随机抽取的某些样本的观察比例，估计某个属性在总体的比例此处，感兴趣的属性是：假设h对实例错误分类 错误率估计和二项比例估计（2）测量样本错误率相当于在作一个有随机输出的实验从分布D中随机抽取n个独立的实例，形成样本S，然后测量样本错误率errorS(h)将实验重复多次，每次抽取大小为n的不同的样本Si，得到不同的，取决于Si的组成中的随机差异被称为一随机变量，一般情况下，可以将随机变量看成一个有随机输出的实验。随机变量值即为随机实验的观察输出 错误率估计和二项比例估计（3）设想要运行k个这样的随机实验，得到k个随机变量值，以图表的形式显示观察到的每个错误率值的频率；当k不断增长，该图表将呈现二项分布。 二项分布有一非均质硬币，要估计在抛硬币时出现正面的概率p；投掷硬币n次并计算出现正面的次数r，那么p的一个合理估计是r/n；如果重新进行一次实验，生成一个新的n次抛硬币的集合，出现正面的次数r可能与前不同，得到对p的另一个估计；二项分布描述的是对任一可能的r值，这个正面概率为p的硬币抛掷n次恰好出现r次正面的概率。 二项分布（2）从抛掷硬币的随机样本中估计p与在实例的随机样本上测试h以估计errorD(h)是相同的问题一次硬币抛掷对应于从D中抽取一个实例并测试它是否被h误分类一次随机抛掷出现正面的概率p对应于随机抽取的实例被误分类的概率errorD(h)二项分布给出了一个一般形式的概率分布，无论用于表示n次硬币出现正面的次数还是在n个样例中假设出错的次数二项分布的具体形式依赖于样本大小n以及概率p或errorD(h) 应用二项分布的条件有一基本实验，其输出可被描述为一随机变量Y，随机变量Y有两种取值在实验的任一次尝试中Y=1的概率为常数p，它与其它实验尝试无关，因此Y=0的概率为1-pp为预先未知，面临的问题是如何估计基本实验的n次独立尝试按序列执行，生成一个独立同分布的随机变量序列随机变量R表示n次实验中出现Yi=1的次数，它取特定值r的概率由二项分布给出（5.2） 均值期望值是重复采样随机变量得到的值的平均定义：考虑随机变量Y可能的取值为y1...yn，Y的期望值E[Y]定义如下：如果随机变量Y服从二项分布，那么可得E[Y]=np 方差方差描述的是概率分布的宽度或散度，描述了随机变量与其均值之间的差有多大定义：随机变量Y的方差Var[Y]定义如下：描述了从Y的一个观察值估计其均值E[Y]的误差平方的期望随机变量Y的标准差Y若随机变量Y服从二项分布，则方差和标准差分别为：Var[Y]=np(1-p) 估计量、偏差和方差回到问题：我们得出了随机变量errorS(h)服从二项分布，那么errorS(h)和errorD(h)之间可能的差异是多少？用5.2式定义的二项分布，可得errorS(h)=r/nerrorD(h)=p统计学中将errorS(h)称为errorD(h)的一个估计量估计量是用来估计总体的某一参数的随机变量，最关心的是它平均来说是否能产生正确估计 估计量、偏差和方差（2）估计偏差衡量估计量的期望值同真实参数值之间的差异定义：针对任意参数p的估计量Y的估计偏差是：E[Y]-p如果估计偏差为0，称Y为p的无偏估计量，在此情况下，由多次重复实验生成的Y的多个随机值的平均将收敛于p由于errorS(h)服从二项分布，因此errorS(h)是errorD(h)的一个无偏估计量 估计量、偏差和方差（3）对估计偏差的补充说明：要使errorS(h)是errorD(h)的无偏估计，假设h和样本S必须独立选取估计偏差不能与第2章介绍的学习器的归纳偏置相混淆估计量的另一重要属性是它的方差，给定多个无偏估计量，选取其中方差最小的由方差的定义，所选择的应为参数值和估计值之间期望平方误差最小的 估计量、偏差和方差（4）一个例子n=40个随机样例r=12个错误errorS(h)的标准差一般地，若在n个随机选取的样本中有r个错误，errorS(h)的标准差是：近似地(5.9) 置信区间通常描述某估计的不确定性的方法是使用置信区间，真实的值以一定的概率落入该区间中，这样的估计称为置信区间估计定义：某个参数p的N%置信区间是一个以N%的概率包含p的区间由于估计量errorS(h)服从二项分布，这一分布的均值为errorD(h)，标准差可由式5.9计算，因此，为计算95%置信区间，只需要找到一个以errorD(h)为中心的区间，它的宽度足以包含该分布全部概率的95%这提供了一个包围errorD(h)的区间，使errorS(h)有95%机会落入其中，同样它也指定了errorD(h)有95%的机会落入包围errorS(h)的区间的大小 置信区间（2）对于二项分布，计算置信区间很烦琐，多数情况下，计算它的近似值对于足够大的样本，二项分布可以由正态分布来近似，而正态分布的置信区间容易得到如果随机变量Y服从均值为，标准差为的一个正态分布，那么Y的任一观察值y有N%的机会落入下面的区间相似地，均值有N%的机会落入下面的区间 置信区间（3）式子5.1的三步推导过程errorS(h)遵从二项分布，其均值为errorD(h)，标准差如式5.9所示对于足够大的样本n，二项分布非常近似于正态分布式5.1告诉我们如何根据正态分布的均值求出N%置信区间式子5.1的推导中有两个近似估计errorS(h)的标准差，我们将errorD(h)近似为errorS(h)用正态分布近似二项分布统计学的一般规则表明，这两个近似在n>=30或np(1-p)>=5时工作得很好，对于较小的n值，最好使用列表的形式给出二项分布的具体值 双侧和单侧边界上述的置信区间是双侧的，有时用到单侧边界例如问题“errorD(h)至多为U的概率”，在只要限定h的最大错误率，而不在乎真实错误率是否小于估计错误率时，很自然提出这种问题由于正态分布关于其均值对称，因此，任意正态分布上的双侧置信区间能够转换为相应的单侧区间，置信度为原来的两倍由一个有下界L和上界U的100(1-)%置信区间，可得到一个下界为L且无上界的100(1-/2)%置信区间，也得到一个有上界U且无下界的100(1-/2)%置信区间 80%双侧置信区间均值为0，标准差为1的正态分布90%单侧置信区间 推导置信区间的一般方法前面介绍的是针对一特定情况推导置信区间估计：基于独立抽取的n个样本，估计离散值假设的errorD(h)下面介绍的方法是在许多估计问题中用到的通用的方法基于大小为n的随机抽取样本的均值，来估计总体均值的问题 通用的过程的步骤确定基准总体中要估计的参数p，例如errorD(h)定义一个估计量Y（如errorS(h)），它的选择应为最小方差的无偏估计量确定控制估计量Y的概率分布DY，包括其均值和方差通过寻找阈值L和U确定N%置信区间，以使这个按DY分布的随机变量有N%机会落入L和U之间 思考题如果假设h在n=65的独立抽取样本上出现r=10个错误，真实错误率的90%置信区间是多少？95%的单侧置信区间（上界）是多少？90%的单侧区间是多少？ 中心极限定理考虑如下的一般框架在n个独立抽取的且服从同样概率分布的随机变量Y1...Yn中观察试验值令代表每一变量Yi服从的未知分布的均值，并令代表标准差，称这些变量Yi为独立同分布随机变量为了估计Yi服从的分布的均值，我们计算样本的均值中心极限定理说明在n时，所服从的概率分布为一正态分布，而不论Yi本身服从什么样的分布服从的分布均值为，而标准差为 中心极限定理（2）定理5.1（中心极限定理）考虑独立同分布的随机变量Y1...Yn的集合，它们服从一任意的概率分布，均值为，有限方差为2，定义样本均值为，当n时，式子服从正态分布，均值为0且标准差为1.中心极限定理说明在不知道独立的Yi所服从的基准分布的情况下，我们可以得知样本均值的分布形式，说明了怎样使用的均值和方差来确定独立的Yi的均值和方差中心极限定理说明了任意样本均值的估计量服从的分布在n足够大时可以近似为正态分布 两个假设错误率间的差异问题：考虑某离散目标函数的两个假设h1和h2，h1在一拥有n1个随机抽取的样例的样本S1上测试，h2在一拥有n2个从相同分布中抽取的样例的样本S2上测试，要估计这两个假设的真实错误率间的差异d=errorD(h1)-errorD(h2) 两个假设错误率间的差异（2）使用5.4节中描述的四个步骤来推导d的置信区间估计确定待估计的参数，如上所述的d定义一估计量，是d的无偏估计量，即E[]=d。由于对于较大的n1和n2，errorS1(h1)和errorS2(h2)都近似遵从正态分布，两个正态分布的差仍为正态分布，方差为两个正态分布的方差的和（5.12）现在知道了服从均值为d、方差为2的正态分布，因此d的N%置信区间是（5.13） 两个假设错误率间的差异（3）上面分析的是h1和h2在相互独立的数据样本上测试的情况，如果在同一个样本上测试h1和h2，那么也可以使用公式5.13计算置信区间这种情况下的方差通常小于式子5.12给出的方差，这是因为单个样本消除了两个样本组合带来的随机差异，这样，由式子5.13给出的置信区间一般来说偏于保守，但结果是正确的 假设检验有时感兴趣的是某个特定猜想正确的概率，而不是对某参数的置信区间估计。比如：errorD(h1)>errorD(h2)的可能性有多大？例子，假定分别用大小为100的独立样本S1和S2测量h1和h2的样本错误率为0.30和0.20，给定，问errorD(h1)>errorD(h2)的概率是多少？d>0的概率是多少？概率Pr(d>0)等于对d的过高估计不大于0.1的概率，也就是这个概率为落入单侧区间errorD(h2)的概率约为95%。使用统计学术语表述为：接受errorD(h1)>errorD(h2)假设的置信度是95% 学习算法比较有时感兴趣的是比较两个学习算法的性能，而不是两个具体的假设本身如何近似地检验多个学习算法？如何确定两个算法之间的差异在统计上是有意义的？假定有LA和LB两个算法，要确定为了学习一特定目标函数f，平均来说那个算法更好定义“平均”的一种合理方法是，从一基准实例分布中抽取包含n个样例的训练集合，在所有这样的集合中测量两个算法的平均性能，即（5.14） 学习算法比较（2）在实际的学习算法比较中，我们只有一个有限的样本D0，把它分割成训练集合S0和测试集合T0，使用下式比较两个学习到的假设的准确度（5.15）上式与5.14有两个重要的不同使用errorT0(h)来近似errorD(h)错误率的差异测量是在一个训练集合S0上，而不是在从分布D中抽取的所有样本S上计算的期望值改进5.15式的一种方法是，将数据D0多次分割为不相交的训练和测试集合，然后在其中计算这些不同的实验的错误率的平均值 学习算法比较（3）K-Fold交叉验证RandomlypartitiondataDintokdisjointequal-sizedsubsetsP1…PkForifrom1tokdo:UsePiforthetestsetandremainingdatafortrainingSi=(D–Pi)hA=LA(Si)hB=LB(Si)δi=errorPi(hA)–errorPi(hB)Returntheaveragedifferenceinerror:(5-17) 学习算法比较（4）算法返回的可看作下式的估计（5.17）估计式5.17的近似的N%置信区间可表示成（5.18），其中tN,k-1是一常数，其意义类似于前面的zN，第一个下标表示所需的置信度，第二个下标表示自由度，常记作v，它与生成随机变量的值时独立的随机事件数目相关。而代表所服从的概率分布的标准差的估计，定义如下:(5.19)注意当自由度v时，tN,v的值趋向常数zN。 t分布类似于正态分布的钟形分布，但更宽且矮，以反映使用近似真实的标准差时带来的更大方差。 学习算法比较（5）这里描述的比较学习算法的过程要在同样的测试集合上测试两个假设，这与前面描述的比较两个用独立测试集合评估过的假设不同。使用相同样本来测试假设被称为配对测试，配对测试通常会产生更紧密的置信区间，因为在配对测试中任意的差异都来源于假设之间的差异。若假设在分开的数据样本上的测试，两个样本错误率之间的差异也可能部分来源于两个样本组成的不同。 配对t测试前面主要讨论给定固定数据集时比较两个学习算法的过程，并论证公式5.18和5.19为了理解5.18中的置信区间，考虑一下的估计问题给定一系列独立同分布的随机变量Y1…Yk的观察值要估计这些Yi所服从的概率分布的均值使用的估计量为样本均值 配对t测试（2）这一基于样本均值估计分布均值的问题非常普遍（比如，早先的用errorS(h)估计errorD(h)）由式5.18和5.19描述的t测试应用于该问题的一特殊情形，即每个单独的Yi都遵循正态分布考虑前面比较学习算法的过程的一个理想化形式，假定不是拥有固定样本数据D0，而是从基准实例分布中抽取新的训练样例，使每一次循环需要的训练集Si和测试集Ti是从基准实例分布中抽取这一理想化方法能很好地匹配上面的估计问题，该过程所测量的i对应独立同分布的随机变量Yi，其分布的均值对应两学习算法错误率的期望差异。 配对t测试（3）测试集Ti至少包含30个样例，因此，单独的i将近似遵循正态分布，因此，我们也要求Yi服从近似的正态分布，样本均值也遵循正态分布由此，可以考虑使用前面的计算置信区间的表达式。然而，该公式要求我们知道这个分布的标准差，但这个标准差未知t测试正好用于这样的情形，即估计一系列独立同正态分布的随机变量的样本均值当k趋近于无穷时，t分布趋近于正态分布，即tN,k-1趋近于zN，因为样本规模k增加时，收敛到真实的标准差，并且当标准差确切已知时可使用zN。 实际考虑上面的讨论说明了在使用样本均值来估计一个包含k个独立同正态分布的随机变量的样本均值时，可使用式5.18来估计置信区间；这个结论假定对于目标函数的样例可进行无限存取，实际问题是随机变量之间并不独立，因为它们基于从有限子集中抽取的相互重叠的训练样例；当只有一个有限的数据样本可用时，有几种重叠采用的方法。前面描述了k-fold方法(交叉检验)随机抽取至少有30个样例的测试集合，剩余样例组成训练集合，重复这一过程直到足够的次数 实际考虑（2）随机方法的好处是能够重复无数次，以减少置信区间到需要的宽度，而k-fold方法受限于样例的总数随机方法的缺点是，测试集合不再被看作是从基准实例分布中独立抽取，而k-fold交叉验证生成的测试集合是独立的，因为一个实例只在测试集合中出现一次概括而言，统计学模型在数据有限时很少能完美地匹配学习算法验证中的所有约束。然而，它们确实提供了近似的置信区间。 小结统计理论提供了一个基础，从而基于在数据样本S上的观察错误率，估计真实错误率。估计置信区间的问题可通过一待估计的参数以及相对应的估计量来完成。由于估计量是一个随机变量，它可由其服从的概率分布来描述。置信区间的计算可通过确定该分布下包含所需概率质量的区间来描述。估计假设精度中的一种可能误差为估计偏差。如果Y为对某参数p的估计量，Y的估计偏差为Y的期望值和p之间的差 小结（2）估计产生误差的第二种原因是估计方差。即使对于无偏估计，估计量的观察值也可能在各实验中不同，估计量分布的方差描述了该估计与真实值的不同有多大。方差在数据样本增大时降低。比较两个学习算法效果的问题在数据和时间无限时是一个相对容易的估计问题，但在资源有限时要困难得多。本章描述的一种途径是在可用数据的不同子集上运行学习算法，在剩余数据上测试学到的假设，然后取这些结果的平均值。本章考虑的多数情况中，推导置信区间需要多个假定和近似。近似计算分布的方差，以及假定实例从一固定不变的概率分布中生成。 思考题要测试一个假设h，其errorD(h)已知在0.2到0.6的范围内。要保证95%双侧置信区间的宽度小于0.1，最少应搜索的样例数是多少？ 补充读物Billingsleyetal.提供了对统计学的一个很简明的介绍，详尽讨论本章涉及的一些问题DeGroot、Casella&Berger、Duda&Hart在数值模式识别领域提出了对这些问题的解决方法Segreetal.、Etzioni&Etzioni、Gordon&Segre讨论了评估学习算法的统计意义测试Gemanetal.讨论了在同时最小化偏差和最小化方差之间作出的折中。Dietterich讨论了在不同训练测试数据分割下使用配对差异t测试带来的风险 第6章贝叶斯学习与EM算法(BayesianLearningandEMAlgorithm) 概述贝叶斯推理提供了一种概率手段，基于如下的假定：待考察的量遵循某概率分布，且可根据这些概率及已观察到的数据进行推理，以作出最优的决策。贝叶斯推理为衡量多个假设的置信度提供了定量的方法。贝叶斯推理为直接操作概率的学习算法提供了基础，也为其它算法的分析提供了理论框架。 简介贝叶斯学习算法与机器学习相关的两个原因：贝叶斯学习算法能够计算显示的假设概率，比如朴素贝叶斯分类器；贝叶斯方法为理解多数学习算法提供了一种有效的手段，而这些算法不一定直接操纵概率数据，比如：Find-S候选消除算法神经网络学习：选择使误差平方和最小化的神经网络推导出另一种误差函数：交叉熵可分析决策树的归纳偏置可考察最小描述长度原则 贝叶斯学习方法的特性观察到的每个训练样例可以增量地降低或升高某假设的估计概率。而其它算法会在某个假设与任一样例不一致时完全去掉该假设；（最大优点）先验知识可以与观察数据一起决定假设的最终概率，先验知识的形式是：1）每个候选假设的先验概率；2）每个可能假设在可观察数据上的概率分布；贝叶斯方法可允许假设做出不确定性的预测；新的实例分类可由多个假设一起做出预测，用它们的概率来加权；即使在贝叶斯方法计算复杂度较高时，它们仍可作为一个最优的决策标准衡量其它方法； 贝叶斯方法的难度难度之一：需要概率的初始知识，当概率预先未知时，可以基于背景知识、预先准备好的数据以及基准分布的假定来估计这些概率；难度之二：一般情况下，确定贝叶斯最优假设的计算代价比较大（在某些特定情形下，这种计算代价可以大大降低）。 内容安排介绍贝叶斯理论；定义极大似然假设（ML）和极大后验概率假设（MAP）；将此概率框架应用于分析前面章节的相关问题和学习算法；介绍几种直接操作概率的学习算法；贝叶斯最优分类器Gibbs算法朴素贝叶斯分类器讨论EM算法，一类参数估计的方法。 统计推断中可用的三种信息美籍波兰统计学家耐曼(E.L.Lehmann1894－1981)高度概括了在统计推断中可用的三种信息：1．总体信息，即总体分布或所属分布族给我们的信息。譬如“总体视察指数分布”或“总体是正态分布”在统计推断中都发挥重要作用，只要有总体信息，就要想方设法在统计推断中使用2．样本信息，即样本提供我们的信息，这是任一种统计推断中都需要 3．先验信息，即在抽样之前有关统计推断的一些信息。譬如，在估计某产品的不合格率时，假如工厂保存了过去抽检这种产品质量的资料，这些资料（包括历史数据）有时估计该产品的不合格率是有好处的。这些资料所提供的信息就是一种先验信息。又如某工程师根据自己多年积累的经验对正在设计的某种彩电的平均寿命所提供的估计也是一种先验信息。由于这种信息是在“试验之前”就已有的，故称为先验信息。 假设Ⅰ随机变量X有一个密度函数p（x；θ），其中θ是一个参数，不同的θ对应不同的密度函数，故从贝叶斯观点看，p（x；θ）是在给定后θ是个条件密度函数，因此记为p（x│θ）更恰当一些。这个条件密度能提供我们的有关的θ信息就是总体信息。假设Ⅱ当给定θ后，从总体p（x│θ）中随机抽取一个样本,该样本中含有θ的有关信息。这种信息就是样本信息。贝叶斯公式的密度函数形式 假设Ⅲ对参数θ已经积累了很多资料，经过分析、整理和加工，可以获得一些有关θ的有用信息，这种信息就是先验信息。参数θ不是永远固定在一个值上，而是一个事先不能确定的量。从贝叶斯观点来看，未知参数θ是一个随机变量。而描述这个随机变量的分布可从先验信息中归纳出来，这个分布称为先验分布，其密度函数用π（θ）表示。 前面的分析总结如下：人们根据先验信息对参数θ已有一个认识，这个认识就是先验分布π（θ）。通过试验，获得样本。从而对θ的先验分布进行调整，调整的方法就是使用上面的贝叶斯公式，调整的结果就是后验分布。后验分布是三种信息的综合。获得后验分布使人们对θ的认识又前进一步，可看出，获得样本的的效果是把我们对θ的认识由π（θ）调整到。所以对θ的统计推断就应建立在后验分布的基础上。 贝叶斯法则机器学习的任务：在给定训练数据D时，确定假设空间H中的最佳假设。最佳假设：一种方法是把它定义为在给定数据D以及H中不同假设的先验概率的有关知识下的最可能假设。贝叶斯理论提供了一种计算假设概率的方法，基于假设的先验概率、给定假设下观察到不同数据的概率以及观察到的数据本身。 先验概率和后验概率用P(h)表示在没有训练数据前假设h拥有的初始概率。P(h)被称为h的先验概率；先验概率反映了关于h是一正确假设的机会的背景知识；如果没有这一先验知识，可以简单地将每一候选假设赋予相同的先验概率；类似地，P(D)表示训练数据D的先验概率，P(D|h)表示假设h成立时D的概率；机器学习中，我们关心的是P(h|D)，即给定D时h的成立的概率，称为h的后验概率。 贝叶斯公式贝叶斯公式提供了从先验概率P(h)、P(D)和P(D|h)计算后验概率P(h|D)的方法；(6.1)P(h|D)随着P(h)和P(D|h)的增长而增长，随着P(D)的增长而减少，即如果D独立于h时被观察到的可能性越大，那么D对h的支持度越小。 极大后验假设学习器在候选假设集合H中寻找给定数据D时可能性最大的假设h，h被称为极大后验假设（MAP）；确定MAP的方法是用贝叶斯公式计算每个候选假设的后验概率，计算式如下：(6.2)最后一步，去掉了P(D)，因为它是不依赖于h的常量。 极大似然假设在某些情况下，可假定H中每个假设有相同的先验概率，这样式子6.2可以进一步简化，只需考虑P(D|h)来寻找极大可能假设。P(D|h)常被称为给定h时数据D的似然度，而使P(D|h)最大的假设被称为极大似然假设：假设空间H可扩展为任意的互斥命题集合，只要这些命题的概率之和为1。 举例：一个医疗诊断问题有两个可选的假设：病人有癌症、病人无癌症可用数据来自化验结果：正+和负-有先验知识：在所有人口中，患病率是0.008对确实有病的患者的化验准确率为98%，对确实无病的患者的化验准确率为97%总结如下P(cancer)=0.008,P(cancer)=0.992P(+|cancer)=0.98,P(-|cancer)=0.02P(+|cancer)=0.03,P(-|cancer)=0.97 举例：一个医疗诊断问题（2）问题：假定有一个新病人，化验结果为正，是否应将病人断定为有癌症？求后验概率P(cancer|+)和P(cancer|+)利用式子6.2找到极大后验假设P(+|cancer)P(cancer)=0.0078P(+|cancer)P(cancer)=0.0298hMAP=cancer确切的后验概率可将上面的结果归一化以使它们的和为1P(canner|+)=0.0078/(0.0078+0.0298)=0.21P(cancer|+)=0.79贝叶斯推理的结果很大程度上依赖于先验概率，另外不是完全接受或拒绝假设，只是在观察到较多的数据后增大或减小了假设的可能性 基本概率公式表乘法规则：P(AB)=P(A|B)P(B)=P(B|A)P(A)加法规则：P(AB)=P(A)+P(B)-P(AB)贝叶斯法则：P(h|D)=P(D|h)P(h)/P(D)全概率法则：如果事件A1...An互斥，且满足，则 贝叶斯法则和概念学习贝叶斯法则为计算给定训练数据下任一假设的后验概率提供了原则性方法，因此可以直接将其作为一个基本的学习方法：计算每个假设的概率，再输出其中概率最大的。这个方法称为Brute-Force贝叶斯概念学习算法。将上面方法与第2章介绍的概念学习算法比较，可以看到：在特定条件下，它们学习得到相同的假设，不同的是第2章的方法不明确计算概率，而且效率更高。 Brute-Force贝叶斯概念学习概念学习问题：有限假设空间H定义在实例空间X上，任务是学习某个目标概念c。Brute-ForceMAP学习算法对于H中每个假设h，计算后验概率输出有最高后验概率的假设上面算法需要较大计算量，因为它要计算每个假设的后验概率，对于大的假设空间显得不切实际，但是它提供了一个标准以判断其它概念学习算法的性能 特定情况下的MAP假设假定训练数据D是无噪声的，即di=c(xi)目标概念c包含在假设空间H中每个假设的先验概率相同求得由于所有假设的概率之和是1，因此由于训练数据无噪声，那么给定假设h时，与h一致的D的概率为1，不一致的概率为0，因此 特定情况下的MAP假设（2）考虑Brute-ForceMAP算法的第一步h与D不一致，h与D一致，，VSH,D是关于D的变型空间（见第2章，即与D一致的假设集） 特定情况下的MAP假设（3）P(D)的推导P(D)图6-1假设的概率演化情况如图6-1所示，初始时所有假设具有相同的概率，当训练数据逐步出现后，不一致假设的概率变为0，而整个概率的和为1，它们均匀分布到剩余的一致假设中每个与D一致的假设都是MAP假设hP(h|D1,D2)P(h)P(h|D1)hh MAP假设和一致学习器一致学习器：如果某个学习器输出的假设在训练样例上为0错误率，则称为一致学习器；如果H上有均匀的先验概率，且训练数据是确定性和无噪声的，任意一致学习器将输出一个MAP假设；Find-S算法按照特殊到一般的顺序搜索假设空间H，并输出一个极大特殊的一致假设，因此可知在上面定义的P(h)和P(D|h)概率分布下，它输出MAP假设；更一般地，对于先验概率偏袒于更特殊假设的任何概率分布，Find-S输出的假设都是MAP假设。 MAP假设和一致学习器（2）贝叶斯框架提出了一种刻画学习算法行为的方法，即便该学习算法不进行概率操作，通过确定算法输出最优假设时使用的概率分布P(h)和P(D|h)，可以刻画出算法具有最优行为时的隐含假定；使用贝叶斯方法刻画学习算法，与揭示学习器中的归纳偏置在思想上是类似的；在第2章，将学习算法的归纳偏置定义为断言集合B，通过它可充分地演绎推断出学习器所执行的归纳推理结果，即学习器的输出是由其输入和隐含的归纳偏置所演绎得出的。 MAP假设和一致学习器（3）贝叶斯解释对于描述学习算法中的隐含假定提供了另一种方法，用基于贝叶斯理论的一个等效的概率推理系统来建模；贝叶斯解释隐含的假定形式为：H上的先验概率由P(h)分布给出，数据拒绝或接受假设的强度由P(D|h)给出；在已知这些假定的概率分布后，一个基于贝叶斯理论的概率推理系统将产生等效于Find-S、候选消除等算法的输入-输出行为； 极大似然和最小误差平方假设（1）前面分析表明：某些学习算法即使没有显示地使用贝叶斯规则，或以某种形式计算概率，但它们输出的结果符合贝叶斯原理，是一个MAP假设；通过简单的贝叶斯分析，可以表明在特定前提下，任一学习算法如果使输出的假设预测和训练数据之间的误差平方和最小化，它将输出一极大似然假设；上面结论的意义是，对于许多神经网络和曲线拟合的方法，如果它们试图在训练数据上使误差平方和最小化，此结论提供了基于贝叶斯的理论依据。 极大似然和最小误差平方假设（2）问题框架：学习器L工作在实例空间X和假设空间H上，H中的假设为X上定义的某种实数值函数；L面临的问题是学习一个从H中抽取出的未知目标函数f，给定m个训练样例的集合，每个样例的目标值被某随机噪声干扰，此随机噪声服从正态分布；更精确地讲，每个训练样例是序偶，di=f(xi)+ei，ei是代表噪声的随机变量，假定ei的值是独立抽取的，并且它们的分布服从0均值的正态分布；学习器的任务是在所有假设有相等的先验概率前提下，输出极大似然假设（即ML假设）； 极大似然和最小误差平方假设（3）用一个简单情况，即线性函数来说明问题。如图所示，实线表示线性目标函数f，实点表示有噪声的训练样例集，虚线对应有最小平方训练误差的假设hML，即极大似然假设。对于e这样的连续变量上的概率，使用概率密度表示概率分布，它在所有值上的积分为1，用小写的p表示。有限概率P有时又称为概率质量；概率密度函数： 极大似然和最小误差平方假设（4）假定有一固定的训练实例集合，因此只考虑相应的目标值序列D=，这里di=f(xi)+ei。假定训练样例是相互独立的，给定h时，可将P(D|h)写成各p(di|h)的积如果误差ei服从0均值和未知方差2的正态分布，那么每个di服从均值为f(xi)，方差不变的正态分布。因此，p(di|h)可写为方差2、均值f(xi)的正态分布；使用第5章中的正态分布公式并将相应的参数代入，由于概率di的表达式是在h为目标函数f的正确描述条件下的，所以替换=f(xi)=h(xi) 极大似然和最小误差平方假设（5）hML上式说明了极大似然假设等价于使训练值和假设预测值之间的误差的平方和最小的那个假设；这个结论的前提是：训练值等于真实目标值加上随机噪声，其中随机噪声从一个均值为0的正态分布中独立抽取。 采用正态分布的合理性数学计算的简洁性；对许多物理系统的噪声都有良好的近似；第5章中心极限定理显示，足够多的独立同分布随机变量的和服从正态分布；由许多独立同分布的因素的和所生成的噪声将成为正态分布（当然，现实中不同的分量对噪声的贡献也许不是同分布的）；使误差平方最小化的方法经常被用于神经网络、曲线拟合及其他许多实函数逼近的算法中；上面的分析只考虑了训练样例的目标值中的噪声，而没有考虑实例属性值的噪声。 用于预测概率的极大似然假设问题框架：学习一个不确定性函数f:X{0,1}，它有两个离散的值输出；这种不可预测性来源于未能观察到的因素，导致目标函数的输出是输入的概率函数。学习得到的神经网络（或其它实函数学习器）的输出是f(x)=1的概率，表示为：f’:X[0,1]，即f’=P(f(x)=1) 用于预测概率的极大似然假设（2）Brute-Force法首先收集对x的每个可能值观察到的1和0的频率，然后训练神经网络，对每个x输出目标频率可以直接从f的训练样例中训练神经网络，而且能推导出f’的极大似然假设D={...} 用于预测概率的极大似然假设（3）hML（6.13）式子6.13与熵函数的一般式相似，因此它的负值常称为交叉熵 在神经网络中梯度搜索以达到似然最大化前面讨论了利用式子6.13求极大似然假设，现用G(h,D)表示，为神经网络学习推导一个权值训练法则，使用梯度上升法使G(h,D)最大化考虑简单的情况，假定神经网络从一个单层的sigmoid单元建立，则 在神经网络中梯度搜索以达到似然最大化（2）因为要使P(D|h)最大化而不是最小化，因此执行梯度上升搜索，而不是梯度下降搜索。与反向传播更新法则对比使误差平方最小化的法则寻找到极大似然假设的前提是：训练数据可以由目标函数值加上正态分布噪声来模拟使交叉熵最小化的法则寻找极大似然假设基于的前提是：观察到的布尔值为输入实例的概率函数 最小描述长度准则奥坎姆剃刀可以概括为：为观察到的数据选择最短的解释；此处给出一个贝叶斯分析，提出最小描述长度准则，根据信息论中的基本概念来解释hMAP的定义(6.16)上式可以解释为在特定的假设编码表示方案上“优先选择短的假设” 最小描述长度准则（2）信息论中的编码理论设想要为随机传送的消息设计一个编码，其中遇到消息i的概率是pi感兴趣的是，使得传输随机信息所需的最小期望传送位数的编码直观上，为使期望的编码长度最小，可能性大的消息应该赋予较短的编码Shannon&Weaver证明了最优编码对消息i的编码长度为-log2pi使用代码C来编码消息i所需的位数被称为消息i关于C的描述长度，记为LC(i) 最小描述长度准则（3）使用编码理论的结论来解释等式6.16-log2P(h)是在假设空间H的最优编码下h的描述长度。换言之，这是假设h使用其最优表示时的大小，CH为假设空间H的最优编码-log2P(D|h)是在给定假设h时，训练数据D的描述长度，，CD|h是假定发送者和接送者都知道假设h时描述数据D的最优编码因此式子6.16显示，hMAP是使假设描述长度和给定假设下数据描述长度之和最小化的假设最小描述长度准则： 最小描述长度准则（4）如果选择C1为假设的最优编码CH，C2为最优编码CD|h，那么hMDL=hMAP可将MDL准则想象为选择最短的方法来重新编码训练数据，其中不仅计算假设的大小，并且计算给定假设时编码数据的附加开销将MDL准则应用于决策树，如何选择假设和数据的表示C1和C2?对于C1，很自然地选择某种明确的决策树编码方法，其中描述长度随着树中节点和边的增长而增加对于C2，如果训练分类f(xi)与假设的预计相同，那么就不需要传输有关这些样例的任何信息；如果不同，则要传输更正消息 最小描述长度准则（5）MDL准则提供了一种方法在假设的复杂性和假设产生错误的数量之间进行折中，它有可能选择一个较短的产生少量错误的假设，而不是完美地分类训练数据的较长的假设上面讨论自然给出了一种处理数据过度拟合的方法Quinlan&Rivest描述了应用MDL准则选择决策树大小的几个实验，报告指出，基于MDL的方法产生的决策树的精度相当于第3章中讨论的标准树修剪方法 分类问题？能否利用MAP解决分类问题？假设类别为Ci，其后验概率公式如何表述？如何选取判别函数？假设p(x|Ci)为高斯分布，其参数如何求取？先验概率P（Ci）如何求取？ 贝叶斯最优分类器前面我们讨论的问题是：给定训练数据，最可能的假设是什么？另一个相关的更有意义的问题是：给定训练数据，对新实例的最可能的分类是什么？显然，第二个问题的解决可以将第一个问题的结果（MAP）应用到新实例上得到，还存在更好的算法？ 贝叶斯最优分类器（2）例子考虑一个包含三个假设h1,h2,h3的假设空间。假定已知训练数据时三个假设的后验概率分别是0.4,0.3,0.3，因此h1为MAP假设。若一新实例x被h1分类为正，被h2和h3分类为反计算所有假设，x为正例的概率为0.4，为反例的概率为0.6因此，这时最可能的分类与MAP假设生成的分类不同——矛盾！ 贝叶斯最优分类器（3）一般而言，新实例的最可能分类可通过合并所有假设的预测得到，用后验概率来加权。如果新实例的可能分类可取某集合V中的任一值vj，那么概率P(vj|D)表示新实例分类为vj的概率新实例的最优分类为使P(vj|D)最大的vj值，贝叶斯最优分类器为：（6.18) 贝叶斯最优分类器（4）例子已知：新实例的可能分类集合为V={+,-}P(h1|D)=0.4,P(-|h1)=0,P(+|h1)=1P(h2|D)=0.3,P(-|h2)=1,P(+|h2)=0P(h3|D)=0.3,P(-|h3)=1,P(+|h2)=0因此： 贝叶斯最优分类器（5）贝叶斯最优分类器在给定可用数据、假设空间及这些假设的先验概率下使新实例被正确分类的可能性达到最大；贝叶斯最优分类器的一个属性：它所做的分类可以对应于H中不存在的假设；使用式子6.18来分类X中的每个实例，按此定义的实例标注不一定对应于H中的任一单个假设h对实例的标注；将贝叶斯分类器看成是不同于假设空间H的另一空间H’，在其上应用贝叶斯公式。H’有效地包含了一组假设，它能在H中多个假设的线性组合所作的预言中进行比较。 Gibbs算法贝叶斯最优分类器能从给定训练数据中获得最好的性能，但算法的开销很大；一个替代的、非最优的方法是Gibbs算法，定义如下：按照H上的后验概率分布，从H中随机选择假设h使用h来预言下一个实例x的分类在一定条件下，Gibbs算法的误分类率的期望值最多为贝叶斯最优分类器的两倍。确切地讲，期望值是在随机抽取的目标概念上作出的，抽取过程按照学习器假定的先验概率对概念学习问题的一个启示：如果学习器假定H上有均匀的先验概率，而且如果目标概念实际上也按该分布抽取，那么当前变型空间中随机抽取的假设对下一实例分类的期望误差最多为贝叶斯分类器的两倍 朴素贝叶斯分类器应用的学习任务：每个实例x可由属性值的合取描述，而目标函数f(x)从某有限集合V中取值;贝叶斯方法的新实例分类目标是在给定描述实例的属性值下，得到最可能的目标值vMAP使用贝叶斯公式变化上式(6.19) 朴素贝叶斯分类器（2）基于训练数据估计式(6.19)中的两个数据项的值估计P(vj)很容易：计算每个目标值vj出现在训练数据中的频率；估计P(a1,..,an|vj)遇到数据稀疏问题，除非有一个非常大的训练数据集，否则无法获得可靠的估计朴素贝叶斯分类器引入一个简单的假定避免数据稀疏问题：在给定目标值时，属性值之间相互条件独立，即(6.20) 朴素贝叶斯分类器（3）朴素贝叶斯分类器的定义：从训练数据中估计不同P(ai|vj)项的数量比要估计P(a1,...,an|vj)项所需的量小得多；只要条件独立性得到满足，朴素贝叶斯分类vNB等于MAP分类，否则是近似；朴素贝叶斯分类器与前面已介绍的学习方法的一个区别：没有明确地搜索可能假设空间的过程（假设的形成不需要搜索，只是简单地计算训练样例中不同数据组合的出现频率） 朴素贝叶斯分类器（4）举例表3-2提供了目标概念PlayTennis的14个训练样例，给新实例分类根据表3-2，可以计算出上式需要的概率值P(yes)=9/14=0.64P(no)=5/14=0.36P(strong|yes)=3/9=0.33P(strong|no)=3/5=0.60...求vNBP(yes)P(sunny|yes)P(cool|yes)P(high|yes)P(strong|yes)=0.0053P(no)P(sunny|no)P(cool|no)P(high|no)P(strong|no)=0.0206vNB=no 朴素贝叶斯分类器（5）估计概率通过在全部事件基础上观察某事件出现的比例来估计概率当样本很小时，采用平滑技术，m-估计p是将要确定的概率的先验估计，而m是一称为等效样本大小的常量；在缺少其它信息时，选择p的一种典型的方法是均匀概率，比如某属性有k个可能值，那么p=1/k；m被称为等效样本大小的原因是：式子6.22可被解释为将n个实际的观察扩大，加上m个按p分布的虚拟样本。(6.22) 举例：学习分类文本利用贝叶斯方法学习目标概念，然后用于文本自动过滤，比如：我感兴趣的电子新闻稿讨论机器学习的因特网页问题框架：实例空间X包含了所有的文本文档，给定某未知目标函数f(x)的一组训练样例，f(x)的值来自某有限集合V（作为示例，此处令V={like,dislike}）基于朴素贝叶斯的分类方法是文本分类最有效方法。 举例：学习分类文本（2）应用朴素贝叶斯分类器的两个主要设计问题：怎样将任意文档表示为属性值的形式如何估计朴素贝叶斯分类器所需的概率表示文档的方法给定一个文本文档，对每个单词的位置定义一个属性，该属性的值为在此位置上找到的英文单词假定我们共有1000个训练文档，其中700个分类为dislike，300个分类为like，现在要对下面的新文档进行分类：ThisisanexampledocumentforthenaiveBayesclassifier.Thisdocumentcontainsonlyoneparagraph,ortwosentences. 举例：学习分类文本（3）计算式注意此处贝叶斯分类器隐含的独立性假设并不成立。通常，某个位置上出现某个单词的概率与前后位置上出现的单词是相关的虽然此处独立性假设不精确，但别无选择，否则要计算的概率项极为庞大。实践中，朴素贝叶斯学习器在许多文本分类问题中性能非常好。 举例：学习分类文本（4）需要估计概率项P(vi)和P(ai=wk|vi)。前一项可基于每一类在训练数据中的比例很容易得到，后一项含三个参数，出现数据稀疏问题再引入一个假定以减少需要估计的概率项的数量：假定单词wk出现的概率独立于单词所在的位置，即P(ai=wk|vi)=P(wk|vj)作此假定的一个主要优点在于：使可用于估计每个所需概率的样例数增加了，因此增加了估计的可靠程度采纳m-估计方法，即有统一的先验概率并且m等于词汇表的大小，因此 表6-2用于学习和分类文本的朴素贝叶斯算法Learn_Naive_Bayes_Text(Examples,V)Examples为一组文本文档以及它们的目标值。V为所有可能目标值的集合。此函数作用是学习概率项P(wk|vj)和P(vj)。收集Examples中所有的单词、标点符号以及其他记号Vocabulary在Examples中任意文本文档中出现的所有单词及记号的集合计算所需要的概率项P(vj)和P(wk|vj)对V中每个目标值vjdocsjExamples中目标值为vj的文档子集P(vj)|docsj|/|Examples|Textj将docsj中所有成员连接起来建立的单个文档n在Textj中不同单词位置的总数对Vocabulary中每个单词wknk单词wk出现在Textj中的次数P(wk|vj)(nk+1)/(n+|Vocabulary|) 用于学习和分类文本的朴素贝叶斯算法（2）Classify_Naive_Bayes_Text(Doc)对文档Doc返回其估计的目标值，ai代表在Doc中的第i个位置上出现的单词positions在Doc中的所有单词位置，它包含能在Vocabulary中找到的记号返回vNB， 应用样例Joachims将此算法用于新闻组文章的分类每一篇文章的分类是该文章所属的新闻组名称；20个新闻组，每个新闻组有1000篇文章，共2万个文档；2/3作为训练样例，1/3进行性能测量；词汇表不包含最常用词（比如the、of）和罕见词（数据集中出现次数少于3）；分类精度由随机分类5％提高到89％。Lang用此算法学习目标概念“我感兴趣的新闻组文章”NewsWeeder系统，让用户阅读新闻组文章并为其评分，然后使用这些评分的文章作为训练样例，来预测后续文章哪些是用户感兴趣的；每天向用户展示前10%的自动评分文章，它建立的文章序列中包含的用户感兴趣的文章比通常高3~4倍。 贝叶斯信念网朴素贝叶斯分类器假定各个属性取值在给定目标值v下是条件独立的，从而化简了最优贝叶斯分类的计算复杂度。但在多数情况下，这一条件独立假定过于严格；贝叶斯信念网描述的是一组变量所遵从的概率分布，它通过一组条件概率来指定一组条件独立性假设；贝叶斯信念网采用联合概率分布，它允许在变量的子集间定义类条件独立性，它提供因果关系图形。因此，贝叶斯信念网提供了一种中间的方法，它比朴素贝叶斯分类器的限制更少，又比在所有变量中计算条件依赖更可行。 贝叶斯信念网（2）贝叶斯信念网描述了一组变量上的概率分布；考虑一任意的随机变量集合Y1...Yn，其中每个Yi可取的值集合为V(Yi)；变量集合Y的联合空间为叉乘V(Y1)...V(Yn)；在此联合空间上的概率分布称为联合概率分布，联合概率分布指定了元组的每个可能的变量约束的概率；贝叶斯信念网则对一组变量描述了联合概率分布。 条件独立性精确定义条件独立性令X,Y和Z为3个离散值随机变量，当给定Z值时X服从的概率分布独立于Y的值，称X在给定Z时条件独立于Y，即上式通常简写成P(X|Y,Z)=P(X|Z)扩展到变量集合下面等式成立时，称变量集合X1...Xl在给定变量集合Z1...Zn时条件独立于变量集合Y1...Ym条件独立性与朴素贝叶斯分类器的之间的关系 贝叶斯信念网的表示贝叶斯信念网（简称贝叶斯网）表示一组变量的联合概率分布一般地说，贝叶斯网表示联合概率分布的方法是指定一组条件独立性假定（有向无环图）以及一组局部条件概率集合下页图，联合空间中每个变量在贝叶斯网中表示为一个节点，每个变量需要两种类型的信息网络弧表示断言“此变量在给定其直接前驱时条件独立于其非后继”每个变量有一个条件概率表，描述了该变量在给定其立即前驱时的概率分布 StormBusTourGroupLightningThunderForestFireCampfireS,BS,┐B┐S,B┐S,┐BC0.40.10.80.2┐C0.60.90.20.8Campfire 贝叶斯信念网的表示（2）对网络变量的元组赋以所希望的值(y1...yn)的联合概率计算公式如下：所有变量的局部条件概率表以及由网络所描述的一组条件独立假定，描述了该网络的整个联合概率分布 贝叶斯信念网的推理可以用贝叶斯网在给定其它变量的观察值时推理出某些目标变量的值由于所处理的是随机变量，所以一般不会赋予目标变量一个确切的值真正需要推理的是目标变量的概率分布，它指定了在给予其他变量的观察值条件下，目标变量取每一个可能值的概率在网络中所有其它变量都确切知道的情况下，这一推理步骤很简单一般来说，贝叶斯网络可用于在知道某些变量的值或分布时计算网络中另一部分变量的概率分布 学习贝叶斯信念网从训练数据中学到贝叶斯信念网，有多种讨论的框架：网络结构可以预先给出，或由训练数据中得到所有的网络变量可以直接从每个训练样例中观察到，或某些变量不能观察到如果网络结构已知且变量可以从训练样例中完全获得，那么得到条件概率表就比较简单；如果网络结构已知，但只有一部分变量值能在数据中观察到，学习问题就困难多了。这类似于在人工神经网络中学习隐层单元的权值；Russell（1995）提出了一个简单的梯度上升过程以学习条件概率表中的项，相当于对表项搜索极大似然假设。 贝叶斯网的梯度上升训练令wijk代表条件概率表的一个表项，即在给定父节点Ui取值uik时，网络变量Yi值为yij的概率例如图6-3，wijk为最右上方的表项，那么Yi为变量Campfire，Ui是其父节点的元组，yij=True，且uik=S,BS,┐B┐S,B┐S,┐BC0.40.10.80.2┐C0.60.90.20.8Campfire 贝叶斯网的梯度上升训练（2）lnP(D|h)的梯度由对每个wijk求导数得到例如，为计算图6-3中表右上方的表项的lnP(D|h)的导数，需要对D中每个训练样例d计算P(Campfire=True,Storm=False,BusTourGroup=False|d)当训练样例中无法观察到这些变量时，这些概率可用标准的贝叶斯网从d中观察到的变量中推理得到这些量能够很容易地从贝叶斯网推理过程中得到，几乎不需要附加的开销(6.25) 贝叶斯网的梯度上升训练（3）式子6.25的推导用Ph(D)来表示P(D|h)假定在数据集D中的各样例d都是独立抽取的 贝叶斯网的梯度上升训练（4）更新权值归一化处理，保持在区间[0,1]之间，且jwijk对所有i,k保持为1这个算法只保证找到局部最优解，替代梯度上升的一个算法是EM算法 学习贝叶斯网的结构如果贝叶斯网的结构未知，那么需要学习贝叶斯网的结构Cooper&Herskovits提出了一个贝叶斯评分尺度，以便从不同网络中进行选择Cooper&Herskovits提出了算法K2，启发式算法，用于在数据完全可观察时学习网络结构基于约束的学习贝叶斯网络结构：从数据中推导出独立和相关的关系，然后用这些关系来构造贝叶斯网 EM算法EM（ExpectationMaximizationalgorithm）期望最大化算法；处理存在未观察到变量的问题比如，如果某些变量有时能观察到，有时不能，那么可以用观察到该变量的实例去预测未观察到的实例中的变量的值EM算法可用于变量的值从来没有被直接观察到的情形，只要这些变量所遵循的概率分布的形式已知用于马尔可夫模型的训练，估计HMM的参数；可用于混合模型的参数估计（如GMM）用于贝叶斯网的训练聚类分析方法 单变量数据样本Sampling 极大似然（ML）Sampling给定x,它是和2函数目的是将其最大化. 取对数的极大似然函数将该最大化变换为对数形式只需使且 对数似然函数求极大值 对数似然函数求极大值 数据缺失SamplingMissingdata E-Step令为tth迭代的估计值 E-Step令为tth迭代的估计值 M-Step令为tth迭代的估计值 混合模型如果采集的数据是属于混合模型情况；可描述成以下形式：且 混合模型令yi{1,…,M}代表数据源于那个模型. 混合模型其中yi{1,…,M}代表数据源于那个模型. 混合模型 混合模型 混合模型给定x和,y的条件概率可被计算. 完整数据的似然函数 期望g:估计 期望g:估计 期望当yil为0 期望 期望 期望1 最大化给定初始估计值g,需要找到合适参数,使得期望最大化实际上,就是反复迭代. 混合高斯模型高斯模型为d维，第j个模型可表示为:该GMM有M个模型: 目标混合模型其中，最大化: 目标混合模型其中最大化:仅与l相关.仅与l相关. 求l由于有l的约束,为典型求条件极值问题，故引入拉格朗日乘子,并构成以下等式. 求l1N1 求l 求lOnlyneedtomaximizethisterm考虑GMMunrelated 求lOnlyneedtomaximizethisterm因此,需最大化:unrelated为什么?主要是基于矩阵代数知识. 求l因此,需最大化: 小结针对高斯混合模型GMM的EM算法给定初始估计值g,寻找新的参数new如下：不收敛 估计k个高斯分布的均值考虑D是一个实例集合，它由k个不同正态分布的混合所得分布生成每个实例使用一个两步骤的过程形成：首先，随机选择k个正态分布中的一个其次，随机变量xi按照此选择的分布生成考虑一个简单情形：单个正态分布的选择基于均匀的概率进行，且k个正态分布有相同的方差学习任务：输出一个假设h=<1...k>，描述k个分布中每个分布的均值，找到极大似然假设，即使得p(D|h)最大化的假设 估计k个高斯分布的均值（2）当给定从一个正态分布中抽取的数据实例x1,...,xm时，很容易计算该分布的均值的极大似然假设，它是前面介绍的最小误差平方假设的一个特例，表示如下然而，现在的问题涉及k个不同正态分布，而且不知道哪个实例是哪个分布产生的。这是一个涉及隐藏变量的典型例子；对于图6-4的例子，每个实例的完整描述是三元组，其中xi是第i个实例的观测值，zi1和zi2表示哪个正态分布被用来产生xi，是隐藏变量(6.27,28) 图6-4由两个具有相等方差的正态分布混合生成的例子 估计k个高斯分布的均值（3）如果zi1和zi2的值可知，就可用式子6.27来解决，否则使用EM算法EM算法根据当前假设<1...k>，不断地再估计隐藏变量zij的期望值，然后用这些隐藏变量的期望值重新计算极大似然假设以图6-4为例，先将假设初始化为h=<1,2>计算每个隐藏变量zij的期望值E[zij]，假定当前假设h=<1,2>成立计算一个新的极大似然假设h’=<’1,’2>，假定每个隐藏变量zij所取值是第一步得到的期望值E[zij]。将假设替换为h’=<’1,’2>，然后循环 两个步骤的计算式E[zij]正是实例xi由第j个正态分布生成的概率第二步，使用第一步得到的E[zij]来导出一新的极大似然假设 两个步骤的计算式（2）第二步中的表达式类似于式6.28，只是变成了加权样本均值EM算法的要点：当前的假设用于估计未知变量，而这些变量的期望值再被用于改进假设可以证明：算法的每一次循环中，EM算法能使似然P(D|h)增加，除非P(D|h)达到局部最大，因此算法收敛到一个局部最大似然假设 EM算法的一般表述EM算法可用于许多问题框架：其中需要估计一组描述基准概率分布的参数，只给定了由此分布产生的全部数据中能观察到的一部分。上面的二均值问题中，感兴趣的参数是=<1,2>，全部数据是三元组，而只能观察到xi一般地，令待估计参数是，全部数据Y=XZ，其中X是可观察数据，Z是未观察数据。Z可看作一个随机变量，它的概率分布依赖于参数和已知数据XY也是一个随机变量，因为它由随机变量Z定义 EM算法的一般表述（2）EM算法通过搜寻使E[lnP(Y|h’)]最大的h’来寻找极大似然假设h’，其合理性是：P(Y|h’)是给定假设h’下全部数据Y的似然度，因此找到使得这个值最大的h’是合理的对数lnP(Y|h’)最大化也使P(Y|h’)最大化由于Y是一个随机变量，因此P(Y|h’)无法计算，转而计算它的期望值E[lnP(Y|h’)]Y的概率分布由待估计的参数决定，EM算法使用当前假设h代替实际参数，来估计Y的概率分布定义函数Q(h’|h)=E[lnP(Y|h’)|h,X] EM算法的一般表述（3）EM算法的一般形式，重复下面的步骤，直至收敛估计（E）步骤：使用当前假设h和观察到的数据X来估计Y上的概率分布以计算Q(h’|h)Q(h’|h)E[lnP(Y|h’)|h,X]最大化（M）步骤：将假设h替换为使Q函数最大化的假设h’hargmaxh’Q(h’|h)当函数Q连续时，EM算法收敛到似然函数P(Y|h’)的一个不动点，它保证收敛到一个局部最大值 k均值算法K-Means算法输入：聚类个数k，以及包含n个数据对象的数据输出：满足方差最小标准的k个聚类。处理流程：从n个数据对象任意选择k个对象作为初始聚类中心；根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；重新计算每个（有变化）聚类的均值（中心对象）；循环上述两步直到每个聚类不再发生变化为止。 K均值(k-Means)算法的推导问题框架要估计k个正态分布的均值=<1...k>观察到的数据是X={}隐藏变量Z={}表示k个正态分布中哪一个生成xi用于K均值问题的表达式Q(h’|h)的推导单个实例的概率 K均值算法的推导（2）所有实例的概率的对数计算期望值 K均值算法的推导（3）求使Q函数最大的假设解上式得到另外 小结概率学习方法利用关于不同假设的先验概率，以及在给定假设时观察到不同数据的概率的知识贝叶斯方法提供了概率学习方法的基础，基于这些先验和数据观察假定，赋予每个假设一个后验概率贝叶斯方法确定的极大后验概率假设是最可能成为最优假设的假设贝叶斯最优分类器将所有假设的预测结合起来，并用后验概率加权，以计算对新实例的最可能分类朴素贝叶斯分类器增加了简化假定：属性值在给定实例的分类时条件独立贝叶斯信念网能够表示属性的子集上的一组条件独立性假定 小结（2）贝叶斯推理框架可对其他不直接应用贝叶斯公式的学习方法的分析提供理论基础最小描述长度准则建议选取这样的假设，它使假设的描述长度和给定假设下数据的描述长度的和最小化。贝叶斯公式和信息论中的基本结论提供了此准则的根据EM算法提供了一个通用的算法，在存在隐藏变量时进行学习。算法开始于一个任意的初始假设，然后迭代地计算隐藏变量的期望值，再重新计算极大似然假设，这个过程收敛到一个局部极大似然假设和隐藏变量的估计值 补充读物Casella&Berger1990在概率和统计方面的介绍性文章Maisel1971,Speigel1991的快速参考书籍Duda&Hart1973对贝叶斯分类器和最小平方误差分类器的介绍Domigos&Pazzani1996分析了朴素贝叶斯分类器输出最优分类的条件Cestnik1990讨论了m-估计Michieetal.1994将不同贝叶斯方法与决策树等其他算法进行比较Chauvin&Rumelhart1995提供了基于反向传播算法的神经网络的贝叶斯分析Rissanen11983,1989讨论了最小描述长度准则Quinlan&Rivest1989描述了利用最小描述长度准则避免决策树过度拟合的方法
