机器学习及进化计算.ppt

1,机器学习及进化计算,授课：徐琴珍学时：36,2,主要教材及参考书目,教材：机器学习,TomM.Mitchell著，曾华军，张银奎等译，机械工业出版社。参考书目：贝叶斯方法，TomasLeonaard,机械工业出版社。进化计算，王正志，薄涛，国防科技大学出版社。神经网络设计，MartinT.Hangan等，机械工业出版社。,3,考核方式,平时考核：课堂讨论选题：决策树、人工神经网络、评估假设、贝叶斯学习、计算学习理论(PAC相关内容等)、基于实例的学习(k-近邻，局部加权回归、RBF等)、遗传算法、学习规则集合(序列覆盖算法、学习一阶规则等)、学习分析、归纳和分析学习的结合、增强学习(Q学习、时间差分学习等)期末考核,4,第一讲机器学习的基本概念第1章引言,什么是机器学习？为什么进行机器学习？如何利用机器学习解决问题？,5,什么是机器学习？,直观地理解：机器（计算机）的自我学习。例：计算机能从医疗记录中学习，获取治疗新疾病的最有效方法；住宅管理系统分析住户的用电模式，以降低能源消耗。,6,为什么进行机器学习？,包括人工智能、概率统计、信息论、神经生物学等学科的发展为机器学习提供了丰富的素材；不断增长的在线（实时）数据量；可以有效地利用计算机的计算性能；产业发展的推动；机器学习适用的三大领域:,7,机器学习适用的三大领域,数据挖掘：用历史数据提高决策能力。例：医疗数据诊断知识(dataknowledge)人们无法手工操作实现，而应用软件却可以。例:自动驾驶；语音识别个性定制程序。例：掌握用户兴趣的新闻广播员,8,典型的数据挖掘实例,数据：给定9714个病历记录，每条记录描述了怀孕及生产的信息每条病历记录包含215个特征,9,数据特征,要求预测：未来病历中需要紧急剖腹产的病人,10,如何利用机器学习解决问题,学习问题的标准描述（Section1.1）设计学习系统（Section1.2),11,什么是学习问题？,定义：对于某类任务T和性能度量P，如果一个计算机程序在T上以P衡量的性能随着经验E而自我完善，那么我们称这个计算机程序在从经验E学习。（例：水果分类,手写字体的识别，机器人驾驶）广义理解：任何计算机程序通过经验来提高某任务处理性能的行为。,12,如何设计学习系统？(1),选择训练经验a)训练经验能否为系统的决策提供直接或间接的反馈？(特征抽取、选择？)b)学习器可以在多大程度上控制训练样例序列?(能否在线学习？)c)训练样例的分布能多好地表示实例分布?,13,例：手写字体的识别学习问题要学习的知识的确切类型对于这个目标知识的表示一种学习机制,14,如何设计学习系统？(2),选择目标函数学习任务目标函数目标函数的逼近V:Featurestatictargetoutput选择目标函数的表示与学习机制有关：加权方式，推理方式等,15,如何设计学习系统？(3),选择函数逼近算法(学习机制)估计训练值调整权值(或调整规则等),16,学习过程的设计流程,决定训练经验类型,决定目标函数的表示,完成设计,决定目标函数,选择学习方法,17,第2章概念学习和一般到特殊序,机器学习的中心问题：从特殊的训练样例中归纳出一般函数（一般概念）。在两分类问题中，概念学习的定义为：从有关某个布尔函数的输入输出训练样例中，推断出该布尔函数。,18,2.2.1术语定义,实例(instance)属性(attribute)目标概念(targetconcept):c(x)训练样例(trainingexamples)正例(positiveexample)、反例(negativeexample):c(x)=1or0所有可能假设(allpossiblehypotheses):H(c的所有可能假设,从中搜索h(x)=c(x),19,表2-1目标概念EnjoySport的正例和反例,术语定义,Find-S例,20,2.2.2归纳学习假设,归纳学习假设:任一假设如果在足够大的训练样例集中很好地逼近目标函数，它也能在未见实例中很好地逼近目标函数。,21,2.3作为搜索的概念学习,概念学习的过程即搜索的过程搜索范围：假设表示(H)所隐含定义的整个空间。搜索目标:寻找能最好地拟合训练样例的假设h。学习算法不同，假设空间搜索的策略也不同。,22,Moregeneralthanorequalto,定义：令hj和hk为在X上定义的布尔函数。定义一个more-general-than-or-equal-to关系，记做g。称hjghk当且仅当(xX)(hk(x)=1)(hj(x)=1)例：h1=h2=,23,2.4FIND-S:寻找极大特殊假设,表2-3Find-S算法,24,例：学习器的一系列训练样例如表2-1所示，则FIND-S的学习过程为：Step1.将h初始化为H中最特殊假设：hStep2.与表2-1中第一个训练样例对比，每个属性都被替换成能拟合该例的值约束。h,25,Step3.第2个训练样例（仍为正例）使该算法进一步将h泛化:hStep4.第3个训练样例是一个反例，h不变依次对比样例，直到最后h泛化为：h,26,FIND-S的困惑,学习过程是否收敛到了正确的目标概念？-无法确定收敛到了目标概念为什么要用极大特殊假设？-若有多个与训练样例一致的假设，Find-S只能找到极大特殊假设。训练样例是否相互一致？-数据含噪若有多个极大特殊假设呢？-选择,27,2.5变型空间和候选消除算法,一些术语及其表示(1)：一致：一个假设h与训练样例集合D一致(consistent)，当且仅当对D中每一个样例，h(x)=c(x)。Consistent(h,D)(D)h(x)=c(x),28,一些术语及其表示(2)：变型空间:关于假设空间H和训练样例集D的变型空间(versionspace)，标记为VSH,D，是H中与训练样例D一致的所有假设构成的子集。VSH,DhH|Consistent(h,D),29,2.5.2列表后消除算法,List-Then-Eliminate:列出变型空间的其所有成员.特点:繁琐。,表2-4列表后消除算法,30,2.5.4候选消除学习法,候选消除：候选消除算法通过使用极大一般成员（G）和极大特殊成员（S）来表示变型空间。,31,表2-