机器学习及进化计算

1、机器学习及进化计算授课：徐琴珍学时：36主要教材及参考书目教材：机器学习, Tom M. Mitchell著，曾华军，张银奎 等译，机械工业出版社。参考书目：贝叶斯方法，Tomas Leonaard, 机械工业出版社。进化计算， 王正志，薄涛，国防科技大学出版社。神经网络设计，Martin T. Hangan等，机械工业出版社。考核方式 平时考核：课堂讨论 选题：决策树、人工神经网络、评估假设、贝叶斯学习、计算学习理论(PAC相关内容等)、基于实例的学习(k-近邻，局部加权回归、RBF等)、遗传算法、学习规则集合(序列覆盖算法、学习一阶规则等)、学习分析、归纳和分析学习的结合、增强学习(Q 学

2、习、时间差分学习等) 期末考核第一讲 机器学习的基本概念第1章 引言 什么是机器学习？ 为什么进行机器学习？ 如何利用机器学习解决问题？什么是机器学习？直观地理解： 机器（计算机）的自我学习。例： 计算机能从医疗记录中学习，获取治疗新疾病的最有效方法； 住宅管理系统分析住户的用电模式，以降低能源消耗。 为什么进行机器学习？ 包括人工智能、概率统计、信息论、神经生物学等学科的发展为机器学习提供了丰富的素材； 不断增长的在线（实时）数据量； 可以有效地利用计算机的计算性能； 产业发展的推动； 机器学习适用的三大领域:机器学习适用的三大领域数据挖掘：用历史数据提高决策能力。例：医疗数据诊断知识(da

3、ta knowledge)人们无法手工操作实现，而应用软件却可以。例: 自动驾驶；语音识别个性定制程序。例：掌握用户兴趣的新闻广播员典型的数据挖掘实例数据：给定9714个病历记录，每条记录描述了怀孕及生产的信息每条病历记录包含215个特征数据特征Patient103 time=1Age: 23FirstPregnancy: noAnemia: noPreviousPrematureBirth: no Diabetes: noUltrasound: ?Elective CSection: ?Emergency CSection: ?.Patient103 time=2Age: 23FirstPr

4、egnancy: noAnemia: noPreviousPrematureBirth: noDiabetes: YES Ultrasound: abnormalEmergency CSection: ?Elective CSection: no.Patient103 time=nAge: 23FirstPregnancy: noAnemia: noPreviousPrematureBirth: noDiabetes: noElective CSection: noUltrasound: ?Emergency CSection: Yes.要求预测：未来病历中需要紧急剖腹产的病人如何利用机器学习

5、解决问题学习问题的标准描述（Section 1.1） 设计学习系统（Section 1.2)什么是学习问题？定义：对于某类任务T 和性能度量P ，如果一个计算机程序在T 上以P 衡量的性能随着经验E 而自我完善，那么我们称这个计算机程序在从经验E 学习。（例：水果分类, 手写字体的识别，机器人驾驶）广义理解：任何计算机程序通过经验来提高某任务处理性能的行为 。如何设计学习系统？(1)选择训练经验a) 训练经验能否为系统的决策提供直接或间接的反馈 ？(特征抽取、选择？)b) 学习器可以在多大程度上控制训练样例序列 ?(能否在线学习？)c) 训练样例的分布能多好地表示实例分布? 例：手写字体的识别

6、学习问题要学习的知识的确切类型对于这个目标知识的表示一种学习机制如何设计学习系统？(2)选择目标函数学习任务目标函数目标函数的逼近V: Feature statictarget output 选择目标函数的表示与学习机制有关：加权方式，推理方式等如何设计学习系统？(3)选择函数逼近算法(学习机制)估计训练值调整权值(或调整规则等)学习过程的设计流程决定训练经验类型决定目标函数的表示完成设计决定目标函数选择学习方法第2章 概念学习和一般到特殊序机器学习的中心问题：从特殊的训练样例中归纳出一般函数（一般概念）。在两分类问题中，概念学习的定义为： 从有关某个布尔函数的输入输出训练样例中，推断出该布尔

7、函数 。2.2.1 术语定义 实例(instance) 属性(attribute) 目标概念(target concept) : c(x) 训练样例(training examples) 正例(positive example) 、反例(negative example): c(x)=1 or 0 所有可能假设(all possible hypotheses) : H(c的所有可能假设,从中搜索h(x)=c(x)表2-1目标概念EnjoySport的正例和反例ExampleSkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormal

8、StrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes术语定义Find-S例2.2.2 归纳学习假设 归纳学习假设: 任一假设如果在足够大的训练样例集中很好地逼近目标函数，它也能在未见实例中很好地逼近目标函数。2.3作为搜索的概念学习 概念学习的过程即搜索的过程搜索范围：假设表示(H)所隐含定义的整个空间。搜索目标:寻找能最好地拟合训练样例的假设h。学习算法不同，假设空间搜索的策略也不同。 More general than

9、 or equal to定义：令hj 和hk 为在X上定义的布尔函数。定义一个more-general-than-or-equal-to关系，记做g。称hjg hk当且仅当(xX) ( hk (x) =1)( hj (x) =1)例：h1= h2=2.4 FIND-S: 寻找极大特殊假设表2-3 Find-S算法将h初始化为H中最特殊假设;对每个正例x;对h的每个属性约束ai 如果 x满足ai ,那么不做任何事 否则将h中ai替换为x满足的紧邻的更一般 约束输出假设h.例：学习器的一系列训练样例如表2-1所示， 则FIND-S的学习过程为： Step1.将h初始化为H中最特殊假设： h Ste

10、p2.与表2-1中第一个训练样例对比，每个属性都被替换成能拟合该例的值约束。 h Step3.第2个训练样例（仍为正例）使该算法进一步将h泛化: hStep4.第3个训练样例是一个反例，h不变依次对比样例，直到最后h泛化为： hFIND-S的困惑学习过程是否收敛到了正确的目标概念？- 无法确定收敛到了目标概念为什么要用极大特殊假设？-若有多个与训练样例一致的假设，Find-S只能找到极大特殊假设。训练样例是否相互一致？ -数据含噪若有多个极大特殊假设呢？-选择 2.5变型空间和候选消除算法一些术语及其表示(1)：一致：一个假设h与训练样例集合D一致(consistent)，当且仅当对D中每一个

11、样例，h(x)=c(x)。 Consistent(h,D)( D) h(x)=c(x)一些术语及其表示(2)：变型空间: 关于假设空间H和训练样例集D的变型空间(version space)，标记为VSH,D，是H中与训练样例D一致的所有假设构成的子集。 VSH,DhH | Consistent (h,D) 2.5.2列表后消除算法List-Then-Eliminate: 列出变型空间的其所有成员. 特点: 繁琐。表2-4 列表后消除算法变型空间VersionSpace包含H中所有假设的列表对每个训练样例 从变型空间中移除所有h(x)c(x)的假设h输出VersionSpace中的假设列表2.5.4 候选消除学习法候选消除：候选消除算法通过使用极大一般成员（G）和极大特殊成员（S）来表示变型空间。 表2-5 使用变型空间的候选消除算法（正例和反例同时影响S和G）将G集合初始化为H中极大一般假设将S集合初始化为H中极大特殊假设对每个训练样例d，进行以下操作：如果d是一正例从G中移去所有与d不一致的假设对S中每个与d不一致的假设s从S中移去s把s的所有的极小泛化式h加入到S中，其中h满足h与d一致，而且G的某个成员比h更一般从S中移去所有这样的假设：它比S中另一假设更一般如果d是一个反例从S中移去所有与d不一致的假设对G中