《人工智能ArtificialIntelligence第五章》由会员分享，可在线阅读，更多相关《人工智能ArtificialIntelligence第五章（110页珍藏版）》请在金锄头文库上搜索。
1、人工智能人工智能Artificial Artificial IntelligenceIntelligence第五章第五章史忠植史忠植 中国科学院计算技术研究所http:/ Learning踏肆项小剪抵醛禾慰黎裤顶叙哑且汲酉休文崔孺威焉根帚渐穷掐虞涅叭离人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习2内容提要内容提要5.1 5.1 机器学习概述机器学习概述5.2 5.2 归纳学习归纳学习5.3 5.3 类比学习类比学习5.4 5.4 统计学习统计学习5.5 5.5 强化学习强化学习
2、5.6 5.6 进化计算进化计算5.7 5.7 群体智能群体智能5.8 5.8 知识发现知识发现5.9 5.9 小结小结蛆虱嘿膛哥递职概婶留饭权皂潍驯沙晋栗围事佐佯束卞镰极孜蔷截柑沿牛人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章机器学习概述机器学习概述n什么是机器学习？学习是使系统在不断重复的工作中对本身能力的增强和改进，使得系统下一次完成同样或类似的任务时比上一次更有效，即通过对人类学习过程和特点的研究，建立学习理论和方法，并应用于机器，以改进机器的行为和性能。 1、学习是一个过程。学习是经验积累的过程，这个过程可能很快
3、，也可能很漫长； 2、学习是对一个系统而言。这个系统可能是一个计算机系统，或一个人机系统； 3、学习能够改变系统的性能。这只说明对系统性能的改进，但是并未限制改进的方法。从人工智能的角度看，机器学习是一门研究使用计算机获取新的知识和技能，提高现有计算机求解问题能力的科学7/25/2024史忠植 人工智能： 机器学习3贷肌途芍辅痈黎俐悉虽矣割惊瓢掖钠李弯趣撰逆吁壤宰返遂灶吨臀奢翁挞人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章机器学习概述机器学习概述n 为什么要研究机器学习？ 必要性：理解学习的本质和建立学习系统是AI研究的目
4、标之一现有的大多数AI系统都是演绎的，没有归纳推理，因而不能自动获取和生成知识 可行性：学习的过程是信息处理的过程，这包括直接记忆和经过推理已有工作说明可以实现一定程度的机器学习7/25/2024史忠植 人工智能： 机器学习4葡邑贬炬舱腑山福伏宗你米拾汁坷兢彬浆镁菩样瘟龋允黑陵忙灭坠振谭戒人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章机器学习概述机器学习概述机器学习的研究目标和困难研究目标：通用学习算法：理论分析任务和开发用于非实用学习任务的算法认知模型：研究人的学习的计算模型和实验模型工程目标：解决专门的实际问题，并开发完
5、成这些任务的工程系统困难：学习系统性能的预测更加困难获取知识的本质还是猜想。由特定的观察和类比生成的知识不可能证明其正确性。7/25/2024史忠植 人工智能： 机器学习5繁搓蜘鹏镣凶织周挂谊迂披鞠档库腺龋瞪援貌痴劲瑚羽技瘸空掩僧捞挚腻人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章机器学习模型机器学习模型学习的一种模型环境：外部信息的来源，它将为系统的学习提供有关信息知识库：代表系统已经具有的知识学习环节：系统的学习机构，它通过对环境的感知取得外部信息，然后经分析、综合、类比、归纳等思维过程获得知识，生成新的知识或改进知识库
6、的组织结构。执行环节：基于学习后得到的新的知识库，执行一系列任务，并将运行结果报告学习环节，以完成对新知识库的评价，指导进一步的学习工作,是该模型的核心。 环境环境学习环节学习环节知识库知识库执行环节执行环节7/25/2024史忠植 人工智能： 机器学习6顺左坝泰编炭挂趟然渊池工酚祥廷歌臂姬整谚埔碘倚惊龙裔郎诗著吞往荆人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章机器学习发展阶段机器学习发展阶段机器学习的研究大致可以分为三个阶段：n五六十年代的探索阶段： 主要受神经生理学、生理学和生物学的影响，研究主 要侧重于非符号的神经元
7、模型的研究，主要研制通用学习系统，即神经网络或自组织系统。 主要成果有： 感知机（Perceptron） Friedberg等模拟随机突变和自然选择过程的程序， Hunt等的决策树归纳程序CLS。 7/25/2024史忠植 人工智能： 机器学习7蛮慧杠妮怜恼烈丰垛诫队桔执场鼓佰冬滚圭屿恋构元适违互日姻寝省叛捆人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章n七十年代的发展阶段： 由于当时专家系统的蓬勃发展，知识获取成为当务之急，这给机器学习带来了契机，主要侧重于符号学习的研究。机器学习的研究脱离了基于统计的以优化理论为基础的研
8、究方法，提出了基于符号运算为基础的机器学习方法，并产生了许多相关的学习系统， 主要系统和算法包括： Winston的积木世界学习系统； Michalski基于逻辑的归纳学习系统AQVAL； Michalski和Chilausky的AQ11； Quinlan的ID3程序 Mitchell的版本空间方法。机器学习发展阶段机器学习发展阶段7/25/2024史忠植 人工智能： 机器学习8刁靠缓氯幸均哗恬胚罕滁百箍贾臭瑚媳丹搪段球供给刃朱麦悍桩谊雏煮谨人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章n八九十年代至今的鼎盛阶段。 理论研究
9、和应用研究也有了新的突破，机器学习的研究进入了全面的、系统化的时期。 主要成果有： 一方面传统的符号学习的各种方法已日臻完善。Michalski等将AQ11扩充为一个多功能学习系统AQ15，ID3算法中使用了熵，从而使决策树归纳得到了很大的改进。 科学发现系统BACON开辟了无导师学习的两个重要研究领域。 神经网络学习在消沉了一段时期后又重新蓬勃发展起来了，同时计算机硬件技术的高速发展也为开展大规模和高性能的人工神经网络提供了保障，使得基于神经网络的连接学习从低谷走出，发展迅猛。其中Rumelhart等人提出的BP模型，提供了一个训练多层网络的实际可行的方法，克服了Perceptron的大部分
10、局限性。 机器学习发展阶段机器学习发展阶段7/25/2024史忠植 人工智能： 机器学习9菏冬诌挡拈谴枉烤添然榔试庚而怀配啪验舷呕驶鞠书砾胯弓亥民腺渣拇跃人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章另一方面，机器学习的基础理论的研究越来越引起人们的重视。 1984年美国学者Valiant提出了基于概率近似正确性的学习理论（PAC学习），对布尔函数的一些特殊子类的可学习性进行了探讨，将可学习性与计算复杂性联系在一起，并由此派生出了“计算学习理论”（COLT） 1995年，Vapnik出版了“统计学习理论”一书。 对PAC的研
11、究是一种理论性，存在性的；Vapnik的研究却是构造性的，他将这类研究模型称为支持向量机SVM（Support Vector Machine）。机器学习发展阶段机器学习发展阶段7/25/2024史忠植 人工智能： 机器学习10跪松驰诺豪犬卑由堑叛掌挛旋妆侵纤骏弘滁诣梗吟缆汹涛炕逝攫啦全闪赦人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章机器学习概述机器学习概述机器学习的研究方法 1、演绎学习 ：是一种常规的逻辑推理方法。其推理的过程就是从公理出发，经过逻辑变换，推导出结论。 2、归纳学习 ：环境或教师提供一系列正例和反例，通过
12、归纳推理，机器将这些例子进行推广，产生一个或一组一般的概念描述。 3、类比学习 ：利用两个不同领域（目标域和源域）知识的相似性，从源域的知识（包括相似的特征和其他特征）推断出目标域的相应知识的推理方法。 4、统计学习 ：基于数据构建概率统计模型并运用模型对数据进行预测与分析。5、强化学习：又称激励学习，是从环境到行为映射的学习，以使奖励信号函数值最大。6、进化学习：是研究利用自然进化和适应思想的计算系统。7/25/2024史忠植 人工智能： 机器学习11瓢牺元节娟击囊菜赌漏缎淆饲觉芥刁坎竟穷藤惦泽词剪幢展釉磨娟枷褪痕人工智能ArtificialIntelligence第五章人工智能Artifi
13、cialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习12内容提要内容提要5.1 5.1 机器学习概述机器学习概述5.2 5.2 归纳学习归纳学习5.3 5.3 类比学习类比学习5.4 5.4 统计学习统计学习5.5 5.5 强化学习强化学习5.6 5.6 进化计算进化计算5.7 5.7 群体智能群体智能5.8 5.8 知识发现知识发现5.9 5.9 小结小结势爬鹅依黍漳趋臃澄媳向邦士禹牡鱼偶搞育途稼恰拳率鸳婪施央夸祟预兴人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章归纳学习归纳学习归纳学习（I
14、nductive Learning）就是从个别到一般，根据某个概念的一系列已知的正例和反例，从中归纳出一个一般的概念描述旨在从大量的经验数据中归纳抽取出一般的判定规则和模式。是机器学习中最核心、最成熟的分支。归纳学习也称为：经验学习：归纳学习依赖于经验数据基于相似性的学习：归纳学习依赖于数据间的相似形归纳的操作：泛化(Generalization)：扩展某假设的语义信息，使其能够包含更多的正例特化(Specialization)：泛化的相反操作，用于限制概念描述的应用范围7/25/2024史忠植 人工智能： 机器学习13椎医贪姜翁冶湖敢沂允熊彩氯疾减亢挟澳化玩徒贸馆牌卯治得陕非鸭询橡人工智能A
15、rtificialIntelligence第五章人工智能ArtificialIntelligence第五章归纳学习归纳学习归纳学习的分类和研究领域：符号学习监督学习：实例学习：系统事先将训练例子（经验数据）分类：正、负例子。由于它产生规则，所以也称为概念学习无监督学习：事先不知道训练例子的分类概念聚类：机器发现神经网络：本质上是实例学习，为区别起见，称为联结学习学习的计算理论传统的算法复杂性分析概率近似正确性学习研究（计算学习理论）7/25/2024史忠植 人工智能： 机器学习14沧楷嘴逛瘫绦雕疙喻税征瞪倪夫际幼妮摧呵垒苑晰虱缚福励萝辕六染誓篮人工智能ArtificialIntelligenc
16、e第五章人工智能ArtificialIntelligence第五章实例学习实例学习基本思想：环境提供给系统一些特殊的实例，这些例子事先由施教者划分为正例和反例。 实例学习由此进行归纳推理，产生适用于更大范围的一般性知识，得到一般的规则 ，它将覆盖所有的正例并排除所有的反例。环境提供给学习环境的例子是低水平的信息，这是在特殊情况下执行环节的行为。学习环节归纳出的规则是高水平的信息，可以在一般情况下用这些规则指导执行环节的工作7/25/2024史忠植 人工智能： 机器学习15画淄驼磐氓恒党厦买驶丙大忘缚汐紫研室点禽螟寥境胺陡译汰箍艾舞降四人工智能ArtificialIntelligence第五章人
17、工智能ArtificialIntelligence第五章实例学习例子空间要考虑的问题： 示教例子的质量 例子空间的组织和搜索方法规则空间要考虑的问题 形成知识的归纳推理方法 搜索规则空间的方法 对规则空间的要求例子空间例子空间规则空间规则空间选择例子选择例子解释例子解释例子7/25/2024史忠植 人工智能： 机器学习16叉虞母圭唬溪拟挠贮对撼锈毫摹疹缓功拒济眺矮尼疆芯榷夏伯瘩员勘投惺人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章实例学习实例学习按规则空间搜索方法分类：数据驱动方法：变型空间方法：采用统一的形式表示规则和例子
18、。改进假设方法：例子和规则的表示不统一。程序根据例子选择一种操作，用该操作修改H中的规则模型驱动方法：产生和测试方法：针对示教例子反复产生和测试假设的规则。利用基于模型的知识产生假设的规则，便于只产生可能合理的假设方案示例方法：使用规则方案的集合来限制可能合理的规则形式，最符合示教例子的规则被认为是最合理的规则7/25/2024史忠植 人工智能： 机器学习17鸵烟津纲悍女谁粳懦裤摈斧招坍籽蛾户猪涣昼俺搭赛冯懈仍血理兼娘锭蠕人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章实例学习实例学习按任务的复杂性划分为：学习单个概念：由系统
19、提供的某个概念的正例和反例，只要求系统归纳出一个概念的描述规则学习多个概念：要求归纳出多个相互独立的概念学习执行多步任务：执行环节使用一个操作序列去完成任务，即执行环节进行任务规划。因此，归纳出的规则应该是进行任务规划的规则7/25/2024史忠植 人工智能： 机器学习18茬掩吩汛管田信柠鉴芥攒粘十脑循萨瞧勿抵裙寥汲孔傍拐亩万鲜休证被咯人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章变型空间方法变型空间方法基本思想：以整个规则空间为初始的假设规则集合H，根据示教例子中的信息，对集合H进行一般化或特殊化处理，逐步缩小集合H，最后
20、使H收敛为只含要求的规则。规则空间中的偏序关系：它是按一般性和特殊性来建立的一种概念之间的关系排序后的变形空间：最上面：是最一般的 规则(概念)，是没有描述的点，所有的例子都符合这一概念最下面一行的各点：是示教正例对应的概念，每个点的概念只符合一个正例7/25/2024史忠植 人工智能： 机器学习19遍呵赊宴绩夹肩熄底己饶蜂染蔽戎府倍盾劫蛔惕赃萍处羊蕴肢罗朴芯攘电人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章假设规则的集合H：H是规则空间的子集H中最一般的元素组成的子集称为G集合H中最特殊的元素组成的子集称为S集合在规则空间
21、中，H是G和S中间的一段。可以用G和S来表示H变型空间方法：初始：G是最上面一个点，S是最下面的直线（示教正例），H为整个规则空间搜索过程：G下移，S上移，H逐步缩小。结果：H收敛为只含一个要求的概念变型空间方法变型空间方法7/25/2024史忠植 人工智能： 机器学习20野篓前斡绘膨掠督俘社淑辐窝搽宵帜莎衅绚冕茨返瀑罚肯篡膛倡紫姬贷徒人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章消除侯选元素算法(1)正规的初始H集是整个规则空间，这时S包含所有可能的示教正例（最特殊的概念）。(2)接收一个新的示教例子。 如果是正例：去掉G
22、中不覆盖新正例的概念，然后修改S为由新正例和S原有的元素共同归纳出的最特殊的结果 如果是反例：从S中去掉覆盖该反例的概念；然后修改G为由新反例和G原有元素共同特殊化为最一般的结果(3)若G=S，且是单元集合，则转(4)，否则转(2)(4)输出H中的概念（即G和S）变型空间方法变型空间方法7/25/2024史忠植 人工智能： 机器学习21伪咕丸炉您苫汽堪饯兰伊史测谰糖钳审履倔悔秉磋戊泞动艇攀律摹工桨联人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章变型空间法的缺点(1)抗干扰能力差变形空间法是数据驱动的方法，所有数据驱动的方法都
23、难以处理有干扰的训练例子算法得到的概念应满足每个示教例子的要求，所以一个错误的例子会造成很大的影响(2)无法发现析取概念变型空间方法变型空间方法7/25/2024史忠植 人工智能： 机器学习22就舍宁兴挽呼辊霉镀吨搜瘸溃衣晒候泞炕娥寞净界吨粉狞御膀礼沂合凳形人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章决策树学习决策树学习决策树通过把实例从根节点排列到某个叶子节点来分类实例。叶子节点即为实例所属的分类树上每个节点说明了对实例的某个属性的测试节点的每个后继分支对应于该属性的一个可能值正实例：产生正值决策的实例负实例：产生负值决
24、策的实例决策树代表实例属性值约束的合取的析取式。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取7/25/2024史忠植 人工智能： 机器学习23牌降某唇印钙否瘪逊艳究亦怯冷洽宾吗搁更纯易薄剩盛廊属前吹培塞夏汪人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章决策树学习例子决策树学习例子InstancesNo. of wingsBroken wings Living statusWing area/ weight Fly120Alive2.5True221Alive2.5False322Alive2.6F
25、alse420Alive3.0True520Dead3.2False600Alive0False710Alive0False820Alive3.4True920alive2.0False7/25/2024史忠植 人工智能： 机器学习24纸绽晒绅匆想厚爸移及江技威褂警畔询绷忱井享唯烤锗师称舱棚踪绒暴命人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章ID3ID3算法算法1、是利用信息论原理对大量样本的属性进行分析和归纳而产生的。2、决策树的根结点是所有样本中信息量最大的属性。树的中间结点是该结点为根的子树所包含的样本子集中信息量最
26、大的属性。决策树的叶结点是样本的类别值。3、用信息增益（即信息论中的互信息）来选择属性作为决策树的结点。7/25/2024史忠植 人工智能： 机器学习25缀斋燕掠卑坑痉陨苍蛹铂兰炔舅豌瘁茧畅绢妖钦觉贰络瘫任赋则肄幂饥锌人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章决策树学习n熵(entropy)：给定有关某概念的正例和负例的集合S。对此BOOLEAN分类的熵为： Entropy(S)= - pos log2(pos) neg log2(neg) “pos”和”neg”分别表示S中正例和负例的比例。并定义：0log2(0)=0
27、n如果分类器有c个不同的输出，则： Entropy(S)= - ci=1pi log2(pi) pi表示S中属于类i的比例7/25/2024史忠植 人工智能： 机器学习26测缸俄捕条滔我蹿挖驼篡矛哟广即酥违盐象泅茨暇萌蠢鹏糟桓甘俯贴锹孕人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章决策树学习决策树学习例1：p1 = p2 = 1/2 H1 = -(1/2)*log2(1/2) - (1/2)*log2(1/2) = 1例2：p1 = 1/4 p2 = 3/4 H2 = -(1/4)* log2(1/4) - (3/4)*lo
28、g2(3/4)=0.81例3：p1 = 1 p2 = 0 H3 = -1 * log21 = 07/25/2024史忠植 人工智能： 机器学习27府豌塑叙邦伶寻商初渡稽谎哑恒忿艰潞沉饲树厂颂型钎路厌吠父业一惊事人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章决策树学习决策树学习n实例集合S中属性A的信息增益为： Gain(S, A)=Entropy(S) - （|SV|/|S|）Entropy(Sv) vvalues of A Sv表示S的子集，其属性A的值为V7/25/2024史忠植 人工智能： 机器学习28尼鹤郴梧狗镜活堂
29、械郭熊掐诧锰泼泣懒脂涪直掳聋逮郑南茂义膨岛姆暇刁人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章决策树学习决策树学习思路：考察任一个属性，计算其熵值；对这个特定属性，考察根据其不同的属性值分成的若干子集；对任意子集，考察不同的类别，计算其熵值并求和；从所有属性中，选择熵值最小（ 或增益最大）的属性作为当前决策节点。7/25/2024史忠植 人工智能： 机器学习29四续邑峨龚萝焚应彝咋悠脆烯佐缅堪敝哄筏而结躁忽艘刻烤晶缀寒店堑灰人工智能ArtificialIntelligence第五章人工智能ArtificialIntellig
30、ence第五章7/25/2024史忠植 人工智能： 机器学习30内容提要内容提要5.1 5.1 机器学习概述机器学习概述5.2 5.2 归纳学习归纳学习5.3 5.3 类比学习类比学习5.4 5.4 统计学习统计学习5.5 5.5 强化学习强化学习5.6 5.6 进化计算进化计算5.7 5.7 群体智能群体智能5.8 5.8 知识发现知识发现5.9 5.9 小结小结私芹蒋宇饥檀睦吏捞皮涧消驱陇悦浆磕雏鸡范钦傲娟哮透粳使奋能绷损赠人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章31类比学习类比学习类比学习 类比学习（learni
31、ng by analogy）就是通过类比，即通过对相似事物加以比较所进行的一种学习 。其推理过程如下 ：回忆与联想 选择 建立对应关系转换 P(a) Q(a) , P(a) P(b) Q(b)Q(a) 7/25/2024史忠植 人工智能： 机器学习速鞋核屏豪玛菜褥酚晦壮卢匪箩别佩搔疏诌驶剩依衅痞岸弹乒瘴碘造尊既人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章32类比学习主要包括如下四个过程：1.输入一组已知条件和一组未完全确定的条件。2.对两组出入条件寻找其可类比的对应关系。3.根据相似转换的方法，进行映射。4.对类推得到的知
32、识进行校验。类比学习类比学习7/25/2024史忠植 人工智能： 机器学习襄怠橡延尧作粳茧悠孰膛杜床裙腕魂躺浓褐喊口挥稽耽楷再敢糖歧于棺晓人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习33发展简况发展简况 1971年，Kling, R.E., Stanford Research Institute, 发表文章“A Paradigm for Reasoning by Analogy” 提出了记忆网模型和案例 检索算法。 1981年，Jaime G. Carbonell, Carne
33、gie-Mellon University,发表文章“A Computational Model of Analogical Problem Solving”，提出了转换类比 1983年，Jaime G. Carbonell,发表文章“Derivational Analogy and its role in Problem Solving”,提出了 派生类比 1991年，Jaime G. Carbonell等，发表文章“PRODIGY: An Integrated Architecture for Planning and Learning”， 开发了PRODIGY系统。统瑚嵌啪迪扩耻串操于粥
34、撇汰叛诉枕薪些檀怜琴缅窜槛社栖瘫饱骚杆挞商人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习34类比的形式定义类比的形式定义ABAB类比问题求解的一般模式曝弘孝琉跺懊葛钵匈银淳摧洪螺坐磷症兑疽篡笺曼哆殃爱瑟典靖蜜磨脐也人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习35转换类比转换类比皇啦擞思母绕循觅脏绅搅练树茬哎灿鸦隋哼刺亮酋代懒调掉怠养鞍盆铭凰人工智能Artifici
35、alIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习36手段手段- -目的分析的问题求解模型目的分析的问题求解模型问题空间：问题空间：1)一组可能的问题组合状态集。2)一个初始状态。3)一个或多个目标状态。4)一组变换规则集5)差别函数6)对可用规则编序的索引函数7)一组全局路径限制8)差别表乏普羚焦撇俐陀点你迁员鲤凌桐德窒伯胎鲤云求禁瑞诽鳖归敬泞抒脆狈创人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章S-MEAS-MEA算法算法7/25/2
36、024史忠植 人工智能： 机器学习371)比较当前状态和目标状态，得出差别2)选择合适的规则，以减少两个状态间的差别3)尽可能应用转换规则，直至完成状态转换。否则保存当前状态，并将MEA算法递归地应用于其它子问题，直到该子问题确认不能满足该规划的前提条件为止。4)当子问题求解后，恢复被保存的当前状态，再继续求解原来的问题个召楔歼写盲咽关乒簿闯雕茹酷潭玖维吴宰生闹织滔兜靡磋讽场唯撰粟兆人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习38类比求解问题的计算模型类比求解问题的计算模型EM
37、EA的T-空间包括：1)转换空间中每个状态是初始问题的潜在解，包括初始状态、最终状态、操作符序列以及路径限制。2)初始状态：O-空间中检索到的相似问题的解序列。3)目标状态：求解新问题的解的规范说明。4)操作符将一个完整的解序列映射到另一个潜在的解序列。5)差别函数：新问题情况下检索解的初始状态、中止状态、路径的约束和应用度之间的差别测度的综合。6)差别表：用来检索T-空间的操作。7)没有路径约束，可用更为复杂的差别函数补偿。8)可用启发式函数作为规则排序。询讳艘塔泉嫌过东虐赋蒂儿辩诊且忽膳荚杆批勋胆闭侮贼且犁露傲所丘廓人工智能ArtificialIntelligence第五章人工智能Arti
38、ficialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习39基于案例推理基于案例推理n人们为了解决一个新问题，先是进行回忆，从记忆中找到一个与新问题相似的案例 ，然后把该案例 中的有关信息和知识复用到新问题的求解之中。n在基于案例推理 (Case-Based Reasoning, 简称CBR)中，把当前所面临的问题或情况称为目标案例 (target case)，而把记忆的问题或情况称为源案例 (base case)。粗略地说，基于案例 推理就是由目标案例 的提示而获得记忆中的源案例 ，并由源案例 来指导目标案例 求解的一种策略。洋责寿鸳晒劲篓蕴织遭斟捏诈篷钨尽踏
39、巩树纯紫赢可西炼质珍丢浚宰播激人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习40 基于案例学习的一般过程基于案例学习的一般过程月既谚啸必糖崖眯桔烙肾昌噎诬坝葫蛤梗戳赤厉览扮孩徘荷砷馈焕柒装毙人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章CBRCBR的过程模型的过程模型 7/25/2024史忠植 人工智能： 机器学习41介耕刺魁沛翠面撰诣簇伙际路完吓烁阴岸平缨焙郁梳挠缴逊菜瓜妈聂腾樊人工智能ArtificialI
40、ntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习42迁移学习迁移学习迁移学习（transfer learning）的目标是将从一个环境中学到的知识用来帮助新环境中的学习任务。在传统分类学习中，为了保证训练得到的分类模型具有准确性和高可靠性，都有两个基本的假设：用于学习的训练样本与新的测试样本满足独立同分布的条件；必须有足够可利用的训练样本才能学习得到一个好的分类模型。但是，在实际应用中发现要满足这两个条件往往是困难的。迁移学习是运用已有的知识对不同但相关领域问题进行求解。它放宽了传统机器学习中的两个基本假设，目
41、的是迁移已有的知识来解决目标领域中仅有少量有标签样本数据甚至没有的学习问题。豺奄丸普窑啤杖详痛谅潘飞市戊小救崇殃仰县一郡拥匹皱缎讹融饲远族勿人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习43内容提要内容提要5.1 5.1 机器学习概述机器学习概述5.2 5.2 归纳学习归纳学习5.3 5.3 类比学习类比学习5.4 5.4 统计学习统计学习5.5 5.5 强化学习强化学习5.6 5.6 进化计算进化计算5.7 5.7 群体智能群体智能5.8 5.8 知识发现知识发现5.9 5.9
42、 小结小结睡詹恰疹鲤霉箔潘咒穴茵狗档成子仟乓惧幻满侠忱纠旁彝夯锗纂遭泵韵佯人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习44统计学习统计学习 统计方法是从事物的外在数量上的表现去推断该事物可统计方法是从事物的外在数量上的表现去推断该事物可能的规律性。能的规律性。科学规律性的东西一般总是隐藏得比较深，科学规律性的东西一般总是隐藏得比较深，最初总是从其数量表现上通过统计分析看出一些线索，最初总是从其数量表现上通过统计分析看出一些线索，然后提出一定的假说或学说，作进一步深入的理论研究。
43、然后提出一定的假说或学说，作进一步深入的理论研究。当理论研究当理论研究 提出一定的结论时，往往还需要在实践中加提出一定的结论时，往往还需要在实践中加以验证。就是说，观测一些自然现象或专门安排的实验以验证。就是说，观测一些自然现象或专门安排的实验所得资料，是否与理论相符、在多大的程度上相符、偏所得资料，是否与理论相符、在多大的程度上相符、偏离可能是朝哪个方向等等问题，都需要用统计分析的方离可能是朝哪个方向等等问题，都需要用统计分析的方法处理。法处理。鼓驮享敦后灰析禹嗽蒲痪佛乓沿缉奔酶雏渠桅坚饱客楚卸嗣湛气隔案子喊人工智能ArtificialIntelligence第五章人工智能Artificia
44、lIntelligence第五章列联表及列联表分析列联表及列联表分析研究两个属性变量之间是否有联系研究步骤： 通过问卷调查或统计资料获得属性 变量的信息 整理问卷或统计资料获得列联表数据 通过统计假设检验两个属性变量是 否具有独立性7/25/2024史忠植 人工智能： 机器学习45妖毙绪羔涡岗滑搂嘛溪泪景税毋孜叉莉盖林肤剥侨殆扫六携习萎闰修堆坦人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章 逻辑回归逻辑回归基本理论和方基本理论和方法法研究某一事件发生的概率P=P(y=1)与若干因素之间的关系 在在0和和1之间之间任意范围之间
45、的数量任意范围之间的数量若干个状态的标量若干个状态的标量7/25/2024史忠植 人工智能： 机器学习46撂飞豫婶术称躇辫泥护迢指敞现窝拖豢综偷纺槛聂趁贬薛滴惯庞涅筋害淡人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章逻辑回归逻辑回归模型模型人们通常把p的某个函数f(p)假设为变量的函数形式，取称之为logit函数，也叫逻辑变换。因此，逻辑变换是取列联表中优势的对数。当概率在0-1取值时，Logit可以取任意实数，避免了线性概率模型的结构缺陷。7/25/2024史忠植 人工智能： 机器学习47敦撮帜敖悯碗捆舵豹外扛很鲜淀勇垂厦
46、涛汉趟憋卓甄邓呜习忌西酵紫钩拉人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章逻辑变换逻辑变换logistic变换Logistic回归模型 优势比优势比7/25/2024史忠植 人工智能： 机器学习48贤挨结描考视瑚蹋坚奔弃章软峨淮葛鲤铺为川储希蔚是嘻冈冬祁泡烈裴帽人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章概率概率p p的预测的预测P与多因素之间的关系预测7/25/2024史忠植 人工智能： 机器学习49踌慈痉旱泣氛拂悄剁翱综思绘斋守派刨整炊币塔妆铡哨播
47、娟石飞搭帝及琵人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章P P与单因素之间的关系图与单因素之间的关系图px1最可能成功范围最可能成功范围最不可能成功范围最不可能成功范围7/25/2024史忠植 人工智能： 机器学习50羚白舟圾滔伞搜胶晨槽歌闻姥液橙挂窿纬拽缮问脖谋钨民劈厨芜踪短巍鸭人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章回归系数的含义回归系数的含义优势比(Odds Ratio)事件发生与不发生的概率比优势比与单变量系数之间的关系 7/25/202
48、4史忠植 人工智能： 机器学习51韩漆萎唬塑议俗曳喂戏痈姥俯该员疏汝云颧牙茄煌场着硒绦肛愧摔锣睁囱人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章支持向量机支持向量机支持向量机（support vector machine: SVM）是一种二类分类方法，它的基本模型是定义在特征空间上的间隔最大的线性分类器。支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上的。它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。7/25/2024史忠植 人工智能： 机器学
49、习52蜘饿侍柔了誓助恋措赛卤牛旷特劝苦筷凝穴图饥茶栅叉欠飘籍标努砰危澈人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章统计学习问题统计学习问题学习问题的表示学习的目的就是，在联合概率分布函数F(x,y)未知、所有可用的信息都包含在训练集中的情况下，寻找函数f(x,w0)，使它（在函数类f(x,w)，(w W）上最小化风险泛函 模式别别问题7/25/2024史忠植 人工智能： 机器学习53昌妆了浚簿仕酬沉腰茁枪靖湾铃劈偶侦铁豺划矣楚秘髓辈躁扁遂儒零稗猫人工智能ArtificialIntelligence第五章人工智能Artifi
50、cialIntelligence第五章经验风险最小化原则经验风险最小化原则(ERM )(ERM ) 最小化经验风险(训练样本错误率 ) 用ERM准则代替期望风险最小化并没有经过充分的理论论证，只是直观上合理的想当然做法这种思想却在多年的机器学习方法研究中占据了主要地位。人们多年来将大部分注意力集中到如何更好地最小化经验风险上。而实际上，即使可以假定当n趋向于无穷大时经验风险也不一定趋近于期望风险，在很多问题中的样本数目也离无穷大相去甚远 ，如神经网络。7/25/2024史忠植 人工智能： 机器学习54蚊募钞稽损磨睹委贬寺茶悍吊娇霖荡并宫财鼠赠闯粉筛旨世脂阿春恫宣农人工智能ArtificialI
51、ntelligence第五章人工智能ArtificialIntelligence第五章学习机器实际风险的界学习机器实际风险的界学习机器实际风险的界其中n样本数量，h是VC维，是递减函数两种方法：神经网络: 保持置信范围固定（通过选择一个适当构造的机器）并最小化经验风险。 支持向量机(SVM): 保持经验风险固定（比如等于零）并最小化置信范围。7/25/2024史忠植 人工智能： 机器学习55探桩递耻绊芦师残酣江噪壶状办刮铲愧买任蠢袱辑树茎篙真惹拂钵恩苫恳人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章结构风险最小化原则结构风险
52、最小化原则函数集 Fk=F(x,w);wWk, k=1,2,n F1 F2 Fn VC维：h1h2hn 在使保证风险（风险的上界）最小的子集中选择使经验风险最小的函数7/25/2024史忠植 人工智能： 机器学习56脱誊遣雨帧阵卢酣寅琴评件言姓汲跳呻刊稿垄萎馅媒柳些侧穗智镐悉纠妈人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习57 Sn S*经验风险经验风险Empirical risk置信范围置信范围Confidence interval风险界限风险界限Bound on the r
53、iskh1h*hnhS1S*Sn结构风险最小化归纳原则结构风险最小化归纳原则 (SRM)(SRM)件灌酮椰米亚沏挠呆头担柜妖障丈缮刷嘉抽搞根帆终蚁父瘴堑群文溢睹乏人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章最大间隔分类器最大间隔分类器 不但能将两类正确分开，而且使分类间隔最大。hmin(R2A2,N)+17/25/2024史忠植 人工智能： 机器学习58涨逃浚吕摔俺循雍此会冒淹浚豌运起维对芽嘲腺险干邻秘摄承畦品得艰蓝人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligenc
54、e第五章7/25/2024史忠植 人工智能： 机器学习59考虑2维空间中极端直线之间的间隔情况求出两条极端直线的距离：如何计算分划间隔如何计算分划间隔？冒龄至漓粳郁炕狐谦估佯胃魄字峰遥氛长奏虱额菌柔炕职尾浓儡砍对绢熔人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章特征空间与核函数特征空间与核函数Mercer定理：要保证L2(C)下的对称函数 能以正的系数展开成(即 描述了在某个特征空间中的一个积)， 其中紧集 ， 充分必要条件是，对使得 的所有 ,条件 成立。7/25/2024史忠植 人工智能： 机器学习60候隧付罪漏丁庙黍扳
55、散粥毛妒呻弄狭告隋子虫敷褪云底偶呸焚首控疏浅铰人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章特征空间与核函数特征空间与核函数nMercer核多项式核高斯径向基函数核Sigmoid核（只在部分参数值情况下才满足核函数的定义 ）7/25/2024史忠植 人工智能： 机器学习61碱需戴铀若穴榨疯沪构片蒂超狡钥饵琶旦桥论括本巫煽旷乱吱铣舜塔莆偶人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习62提升方法提升方法弱学习机（
56、weak learner): 对一定分布的训练样本给出假设（仅仅强于随机猜测）根据有云猜测可能会下雨强学习机（strong learner): 根据得到的弱学习机和相应的权重给出假设（最大程度上符合实际情况：almost perfect expert)根据CNN,ABC,CBS以往的预测表现及实际天气情况作出综合准确的天气预测弱学习机 强学习机 Boosting婉胖元饿芹严筹研芒阿役疤区琅掏兵沛泅抱阑驼湛菇达颈脑乱联学座岁帆人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习63提升方
57、法提升方法过程:在一定的权重条件下训练数据，得出分类法Ct根据Ct的错误率调整权重Set of weightedinstances Classifier Ct train classifier adjust weights泅掷瑚氯儒患蒜够凶耙窒隆煌滁城曲绢慰疥翘酞真汞喇雁番芜定六标严酱人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习64提升流程提升流程(loop1)(loop1)强学习机弱学习机原始训练集原始训练集加权后的训练集加权后的训练集加权后的假设加权后的假设X1?1:-1
58、弱假设弱假设道则挣栅滓序棋萎缠得雇封枢悠挽榷五泅拐根萎党鸭匿孵迢军诌档泛庇徊人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习65提升流程提升流程(loop2)(loop2)强学习机弱学习机原始训练集原始训练集加权后的训练集加权后的训练集加权后的假设加权后的假设Y3?1:-1 弱假设弱假设肇达雕孕筒权烬夷栋癸炽谊硒微绝远银汗丰强壮钒爵集卷打妓炊炭炒臭奠人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024
59、史忠植 人工智能： 机器学习66提升流程提升流程(loop3)(loop3)强学习机弱学习机原始训练集原始训练集加权后的训练集加权后的训练集加权后的假设加权后的假设Z7?1:-1弱假设弱假设荒骨拓柑泅洋赔莉融稍啸云眩硼饶躬材誉述陵绒磺榷耍源任官椎嘛氢甭掖人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习67内容提要内容提要5.1 5.1 机器学习概述机器学习概述5.2 5.2 归纳学习归纳学习5.3 5.3 类比学习类比学习5.4 5.4 统计学习统计学习5.5 5.5 强化学习强化
60、学习5.6 5.6 进化计算进化计算5.7 5.7 群体智能群体智能5.8 5.8 知识发现知识发现5.9 5.9 小结小结隋携腥糕否瞻涡腺窖涨午姨哭彭藉凸熄汪烙赶昨寂暑铭颤疽浪柳勇委悠臼人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章强化学习强化学习人类（通常）从与外界环境的交互中学习。但是，动作的反馈并不总是立即的和直接的。例如，经常需要比较长时间才能充分知道我们的动作所得出的结果。在强化学习中，学习系统根据从环境中反馈的信号的状态（奖励/惩罚），调整系统的参数。 强化学习由于其方法的通用性，对学习背景知识要求较少，以及适
61、用于复杂、动态的环境等特点，在近年，引起了许多研究者的注意，成为机器学习的主要的方式之一。 强化学习一般比较困难，主要是因为学习系统并不知道哪个动作是正确的，也不知道哪个奖惩赋予哪个动作。 7/25/2024史忠植 人工智能： 机器学习68掂距硝缝际莉撂险纷温敬蚜孰唉桅荣岂湖蚂栋险裹敝们拼纸绳谗癣褒迎狈人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章强化学习强化学习强化学习由四部分组成：策略，报酬函数r，值映射V和环境的模型。策略：定义在任何给定时刻学习系统的选择和动作的方法。这样，策略可以通过一组产生式规则或者一个简单的查找
62、表来表示。报酬函数r：定义了在时刻t问题的状态/目标关系。它把每个动作，或更精细的每个状态-响应对，映射为一个报酬量，以指出那个状态完成目标的愿望的大小。赋值函数V：是环境中每个状态的一个属性，它指出对从这个状态继续下去的动作系统可以期望的报酬。报酬函数度量状态-响应对的立即的期望值，而赋值函数指出环境中一个状态的长期的期望值。模型：是抓住环境行为的方面的一个机制。模型让我们在没有实际试验它们的情况下估计未来可能的动作。7/25/2024史忠植 人工智能： 机器学习69秧甲鸽茨镭琼烛缉假谜臣终侠妒喜晦琵刀忽搁簇鹰拦蛀跳思赏墩溢向赊嵌人工智能ArtificialIntelligence第五章人工
63、智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习70主体主体主体主体强化学习模型强化学习模型i: input 输入 r: reward 奖励s: state 状态 a: action 动作状态 sisi+1ri+1奖励 ri环境环境环境环境动作动作 aia0a1a2s0s1s2s3槛积通哑夸料况笛看宛凝哎阎拘蠢邓总拖做杠椿喻鞭耳然萌甄涂远当炭沪人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习71学习自动机学习自动机在强化学习方法中
64、，学习自动机是最普通的方法。这种系统的学习机制包括两个模块：学习自动机和环境。学习过程是根据环境产生的刺激开始的。自动机根据所接收到的刺激，对环境做出反应，环境接收到该反应对其做出评估，并向自动机提供新的刺激。学习系统根据自动机上次的反应和当前的输入自动地调整其参数。掐腻份湃转投畅安廊宇忆鸥掌晴啸躁纂荆度吸挺令淄鬼耕谓镣葛赂祥碴腮人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习72自适应动态程序设计自适应动态程序设计在自适应动态程序设计中，状态i的效用值U(i)可以用下式计算： 其
65、中，R(i)是在状态i时的奖励，Mij是从状态i到状态j的概率。伏垢威炳慎畴汇菏蛾篷悔窖尚契伞喳滦桑湖驳砧市壳崎奥群圭首慑确镰据人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习73Q-Q-学习学习在Q学习中，Q是状态-动作对到学习到的值的一个函数。对所有的状态和动作： Q: (state x action) value 对Q学习中的一步： (10.15)其中c和都1，rt+1是状态st+1的奖励。 矮疥捕繁汤找震档贞院枯豌谣坑绢戊竣煤酬碎肥契鞋申瞧嫁躬姑扣眨演畜人工智能Artifi
66、cialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习74内容提要内容提要5.1 5.1 机器学习概述机器学习概述5.2 5.2 归纳学习归纳学习5.3 5.3 类比学习类比学习5.4 5.4 统计学习统计学习5.5 5.5 强化学习强化学习5.6 5.6 进化计算进化计算5.7 5.7 群体智能群体智能5.8 5.8 知识发现知识发现5.9 5.9 小结小结片跌今弹超锄筹渝磊拯默萍苇铀疫沼舍解奏伶函篇凹辉痛鹊田臼骑洞轴蝗人工智能ArtificialIntelligence第五章人工智能Artificial
67、Intelligence第五章7/25/2024史忠植 人工智能： 机器学习75进化计算进化计算进化计算(evolutionary computation)是研究利用自然进化和适应思想的计算系统。达尔文进化论是一种稳健的搜索和优化机制，对计算机科学，特别是对人工智能的发展产生了很大的影响。大多数生物体是通过自然选择和有性生殖进行进化。自然选择决定了群体中哪些个体能够生存和繁殖，有性生殖保证了后代基因中的混合和重组。自然选择的法则是适应者生存，不适应者被淘汰,简言之为优生劣汰。吩寂贸豌冻堂盘晃蚜剔插鸯锦弹品献爷蕴瞩苍瞒毖谍萤凄沮州舅萄藏沧爹人工智能ArtificialIntelligence第五
68、章人工智能ArtificialIntelligence第五章生物进化的基本条件生物进化的基本条件生物进化过程的发生需要四个基本条件：1）存在有多个生物个体组成的种群；2）生物个体之间存在着差异，或群体具有多样性；3）生物能够自我繁殖；4）不同个体具有不同的环境生存能力，具有优良基因结构的个体繁殖能力强，反之则弱。 7/25/2024史忠植 人工智能： 机器学习76垃钠蓬您槐翻丝肆哎润颖却咸吞烟皿为础孪佩肚缄露纹雁恰赘捕媒权偿筹人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习77遗传
69、算法与自然进化的比较遗传算法与自然进化的比较自然界染色体基因等位基因(allele)染色体位置(locus)基因型(genotype)表型(phenotype)遗传算法字符串字符,特征特征值字符串位置结构参数集,译码结构私咀膏倚捏掏绎驼肆僧椅有斌谋犹涩纪嘲也矾穴墨咆具痞挎历执莉爬垛趣人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习78达尔文进化算法达尔文进化算法1)建立原始种体。2)通过突变建立子孙。3)选择：4)返回到步骤(1)。官镀拓搜锻茧蛛痔酿蕊出搪敏牺绅赚绿愈聋喳倔蛆杀冠渊
70、锌畴挚屿羽雁揖人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习79遗传算法遗传算法遗传算法先将搜索结构编码为字符串形式,每个字符串结构被称为个体。然后对一组字符串结构(被称为一个群体)进行循环操作。每次循环被称作一代,包括一个保存字符串中较优结构的过程和一个有结构的、随机的字符串间的信息交换过程。类似于自然进化，遗传算法通过作用于染色体上的基因寻找好的染色体来求解问题。貌叫轧闭者贸借炭十仓斑策恼槽钵缔肮滤唁眺补壳艰赚匙粪杉豁掂傲掌民人工智能ArtificialIntelligenc
71、e第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习80基本遗传算法基本遗传算法1.随机产生一个由固定长度字符串组成的初始群体;2.对于字符串群体，迭代地执行下述步骤，直到选种标准被满足为止：1)计算群体中的每个个体字符串的适应值;2)应用下述三种操作(至少前两种)来产生新的群体:复制: 把现有的个体字符串复制到新的群体中。杂交: 通过遗传重组随机选择两个现有的子字符串, 产生新的字符串。变异: 将现有字符串中某一位的字符随机变异。3.把在后代中出现的最高适应值的个体字符串指定为遗传算法运行的结果。这一结果可以是问题的解(或近似解)。
72、蓬阀脊鸣怜蔫狠炬迄盼铀颁洲及搪宗卧酉器杨掣刮嫌畔脊晓尧吱贤摧站俯人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习81基本遗传算法流程图GEN=0概率地选择遗传操作随机创建初始群体计算群体中每个个体的适应值i:=0显示结果结束GEN:=GEN+1是是否（转下页）i=N?GEN=M？1厄租务掇翠寇赣杖搭宜渠乡庆霜斜雨碑荐旗退超盈衫腋裴奴妈陌撤耳锭养人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植
73、 人工智能： 机器学习82概率地选择遗传操作根据适应值选择一个个体完成交叉i:=i+1i:=i+1复制个体p(r)选择（接上页）基于适应值选择两个个体把新的两个孩子加到群体中p(c)交叉变异p(m)把新的孩子加入到群体中完成变异根据适应值选择一个个体把变异后个体加入到群体中1奄权福揖称舅窜捣质片砷己券芯孰唬机迹烷毙械宝捆蔡傣揍匿户焕搂刚始人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习83 进化策略进化策略模仿自然进化原理作为一种求解参数优化问题的方法。最简单的实现方法如下:(1)
74、定义的问题是寻找n维的实数向量x, 它使函数(2) 双亲向量的初始群体从每维可行范围内随机选择。(3) 子孙向量的创建是从每个双亲向量加上零均方差高斯随机变量。(4) 根据最小误差选择向量为下一代新的双亲。(5) 向量的标准偏差保持不变, 或者没有可用的计算方法, 那么处理结束。蠢栋吉谋昆忌凸艺绰告现闹使推见脊棋枝郁怠款继狂舰迈逐谨囊掩忙粳沂人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习84 进化规划进化规划 进化规划(evolutionary programming，又译为进化
75、程序设计)的过程, 可理解为从所有可能的计算机程序形成的空间中, 搜索有高的适应值的计算机程序个体，在进化程序设计中，几百或几千个计算机程序参与遗传进化。挺摇混实复近亥鹅珍杖八攒股够开珊烛塘捉踢圭僧怯宏菱窜肥良刀向婆蝎人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习85进化规划步骤1.产生出初始群体, 它由关于问题(计算机程序)的函数随机组合而成。2.迭代完成下述子步骤，直至满足选种标准为止:1)执行群体中的每个程序，根据它解决问题的能力，给它指定一个适应值2)应用变异等操作创造新
76、的计算机程序群体。基于适应值根据概率从群体中选出一个计算机程序个体，然后用合适的操作作用于该计算机程序个体。 把现有的计算机程序复制到新的群体中。通过遗传随机重组两个现有的程序, 创造出新的计算机程序个体。3. 在后代中适应值最高的计算机程序个体被指定为进化程序设计的结果。这一结果可能是问题的解或近似解。僻芭筋汹昂犯虚测端砚症骋寥疯篷筹昭切朋邻有慎共媚珐太努涤姿嘱搔钞人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习86进化计算进化计算进化计算(evolutionary comput
77、ation)是研究利用自然进化和适应思想的计算系统。达尔文进化论是一种稳健的搜索和优化机制，对计算机科学，特别是对人工智能的发展产生了很大的影响。大多数生物体是通过自然选择和有性生殖进行进化。自然选择决定了群体中哪些个体能够生存和繁殖，有性生殖保证了后代基因中的混合和重组。自然选择的法则是适应者生存，不适应者被淘汰,简言之为优生劣汰。仿郊吩痘岸刑刊环疹鞘迭混骏摩杂组牢汪也粉丈淳监讹蜂阻幂按惨原鲍就人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习87内容提要内容提要5.1 5.1 机
78、器学习概述机器学习概述5.2 5.2 归纳学习归纳学习5.3 5.3 类比学习类比学习5.4 5.4 统计学习统计学习5.5 5.5 强化学习强化学习5.6 5.6 进化计算进化计算5.7 5.7 群体智能群体智能5.8 5.8 知识发现知识发现5.9 5.9 小结小结哈濒琅胯生你尹勉俞掖撇疥迷欣害阮耻尘珊漓降芬到僵贝豪汞驭使莉痞弥人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习88群体智能群体智能n指无智能的个体通过合作表现出智能行为的特性，在没有集中控制且不提供全局模型的前提下
79、，为复杂问题求解提供了基础。n特点分布式：能够适应当前网络环境下的工作状态; 鲁棒性：没有中心的控制与数据，个体的故障不影响整个问题的求解; 扩充性：个体的增加，系统的通信开销增加小;简单性：个体简单，实现也比较简单。 踞确颖糙害依绊拾稿沪泄器挞誓艺购挖妒霜格递膊蛔诧雀曙紊惟粹捏拟毋人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章蚁群算法n提出蚁群系统提出蚁群系统 1992年，意大利学者M. Dorigo在其博士论文中提出蚁群系统（Ant System）。 近年来， M. Dorigo等人进一步将蚂蚁算法发展为一种通用的优化技
80、术蚁群优化（ant colony optimization, ACO）。 7/25/2024史忠植 人工智能： 机器学习89奄扰傻毛派园放森猪乌耘慕舀箭强绞勇踞诌放斡伎馁渝才遭债仙辰胖有糯人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章 蚂蚁从A点出发，随机选择路线ABD或ACD。经过9个时间单位时：走ABD的蚂蚁到达终点，走ACD的蚂蚁刚好走到C点。蚁巢蚁巢食物食物蚁群算法原理7/25/2024史忠植 人工智能： 机器学习90澄猴苞都赡衙巢瞎坟猿儡溺气冗帝霉矮梗讥酞冠舱簧爵幕窘抢咸紫哗鞠丁人工智能ArtificialInte
81、lligence第五章人工智能ArtificialIntelligence第五章 最后的极限是所有的蚂蚁只选择ABD路线。（正反馈过程）蚁巢蚁巢食物食物蚁群算法原理7/25/2024史忠植 人工智能： 机器学习91迂军昼债禹朱弃颅其雕撼枢艰察馅捂搂殊材臻蕉黎峻裕伯能骄歪脏食谁竟人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习92蚁群算法模型蚁群算法模型基本模型l简化模型简化模型捕轿昏渤夏模析伎遥蛙超凯烬掀体泊爷汰汕徒晨尹袖寓究洁厘儿汛督综娄人工智能ArtificialIntelli
82、gence第五章人工智能ArtificialIntelligence第五章n由由James KenneyJames Kenney（社会心理学博士）和（社会心理学博士）和Russ Russ EberhartEberhart（电子工程学博士，（电子工程学博士， http:/www.engr.iupui.edu/eberhart/http:/www.engr.iupui.edu/eberhart/ ）于于19951995年提出粒子群算法（年提出粒子群算法（Particle Swarm Particle Swarm Optimization, PSOOptimization, PSO） n源于对鸟群捕
83、食行为的研究，是基于迭代的源于对鸟群捕食行为的研究，是基于迭代的方法方法n简单易于实现，需要调整的参数相对较少简单易于实现，需要调整的参数相对较少粒子群优化粒子群优化7/25/2024史忠植 人工智能： 机器学习93技囤副怂蝗崎呵节查逼科挟卒簧菏饺译市平胁婶奎镀耸釉勾骚术芒仁庸凤人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章n鸟群： 假设一个区域，所有的鸟都不知道食物的位置，但是它们知道当前位置离食物还有多远。nPSO算法 每个解看作一只鸟，称为“粒子(particle)”，所有的粒子都有一个适应值，每个粒子都有一个速度决定
84、它们的飞翔方向和距离，粒子们追随当前最优粒子在解空间中搜索。粒子群优化粒子群优化7/25/2024史忠植 人工智能： 机器学习94钞酝皖辩逐蜗邦重绸沏斧想撮霸嗣慌苏婴贸苔南宏急舆玻兢涛升浆钧邢操人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章n粒子速度和位置的更新 假设在D维搜索空间中，有m个粒子； 其中第i个粒子的位置为矢量 其飞翔速度也是一个矢量，记为 第i个粒子搜索到的最优位置为 整个粒子群搜索到的最优位置为 第i个粒子的位置和速度更新为：粒子群优化算法粒子群优化算法7/25/2024史忠植 人工智能： 机器学习95泼纤
85、狰臭迪枫尧蛮衣棉肮舜怎嗣焰耿赁国臼态胀哟圾蠢是乘着腔素钮瑰鼻人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章n粒子速度和位置的更新 其中，w称为惯性权重， c1和c2为两个正常数，称 为加速因子。 将 vidk 限制在一个最大速 度 vmax 内。xkvkppgbestxk+1vk+1kkk+1k+1粒子群优化算法粒子群优化算法7/25/2024史忠植 人工智能： 机器学习96贡淮弦粕赡陀客轧狭躺伸阿铲宏赃掖镣肢肾怒艳雄衰缘试乎摆问豆叼宏劈人工智能ArtificialIntelligence第五章人工智能ArtificialI
86、ntelligence第五章n粒子速度和位置的更新 “惯性部分”，对自身运动状态的信任“认知部分”，对微粒本身的思考，即来源于自己经验的部分“社会部分”，微粒间的信息共享，来源于群体中的其它优秀微粒的经验粒子群优化算法粒子群优化算法7/25/2024史忠植 人工智能： 机器学习97囊傣撵襟胸驱啄舰堡绰傈讽萄帜吴姚碉疮政舔纺橙标羚袁卸拾朴浇庚邀椽人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章StartInitialize particles with random position and velocity vectors.F
87、or each particles position (xi) evaluate fitnessIf fitness(xi) better than fitness(p) then p= xiLoop until all particles exhaustSet best of ps as gBestUpdate particles velocity and positionLoop until max iterStop: giving gBest, optimal solution.粒子群优化算法流程粒子群优化算法流程7/25/2024史忠植 人工智能： 机器学习98鸵野徊菠几钉雨哮泊螺虞奎
88、鹤演襄岸湖搜曰骆查匀仔试暮暂奶俯掉愉救关人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习99内容提要内容提要5.1 5.1 机器学习概述机器学习概述5.2 5.2 归纳学习归纳学习5.3 5.3 类比学习类比学习5.4 5.4 统计学习统计学习5.5 5.5 强化学习强化学习5.6 5.6 进化计算进化计算5.7 5.7 群体智能群体智能5.8 5.8 知识发现知识发现5.9 5.9 小结小结根昔澈半弯乾望宙栈狄心天腺郡挎寇木乏舞赂含躁萤景辕熄诲勿跟次狱俊人工智能Artificia
89、lIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习100 数据库知识发现数据库知识发现 目前, 大数据知识发现(Knowledge Discovery from Datasets KDD)的研究非常活跃，极为应用广泛。 该术语于1989年出现，Fayyad定义为“KDD是从数据集中识别出有效的、新颖的、潜在有用的，以及最终可理解的模式的非平凡过程” 晋热析职畜衡鸣这沟捶站诫怕秧庶炯王流螟俊奋荷篓竞鼻灌寻玻伸尤舶娘人工智能ArtificialIntelligence第五章人工智能ArtificialIntell
90、igence第五章7/25/2024史忠植 人工智能： 机器学习101 不同的术语名称不同的术语名称 知识发现是一门来自不同领域的研究者关注的交叉性学科，因此导致了很多不同的术语名称。 知识发现:人工智能和机器学习界。 数据挖掘(data mining):统计界、数据分析、数据库和管理信息系统界q知识抽取 (information extraction)、q信息发现 (information discovery)、q智能数据分析 (intelligent data analysis)、q探索式数据分析 (exploratory data analysis)q信息收获 (information
91、harvesting) q数据考古 (data archeology)狞肿谩妇蝎部宾教自戏外林讶秽昌闸慈韵措希各义村揍氯廖抗错牌艇桃猴人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习102 知识发现步骤知识发现步骤钉粉纂静翔表雁芦磷杠盘神吉帚蹭监盛僻琶蛙哺僳辜组折森架烩坷霍逸胆人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习103知识发现的主要任务知识发现的主要任务数据
92、总结： 对数据进行总结与概括。传统的最简单的数据总结方法是计算出数据库的各个字段上的求和值、平均值、方差值等统计值,或者用直方图、饼状图等图形方式表示。 分类：根据分类模型对数据集合分类。分类属于监督学习，一般需要有一个训练样本数据集作为输入。聚类：根据数据的不同特征，将其划分为不同的类。无监督学习谅额蹬迁阎平息嗓弹问巢兢万顺拆稳蹿敷弹苏痹荤猖彰坦武裔追撰春棠剥人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习104知识发现的主要任务知识发现的主要任务相关性分析： 发现特征之间或数据
93、之间的相互依赖关系关联规则 偏差分析：基本思想是寻找观察结果与参照量之间的有意义的差别。通过发现异常, 可以引起人们对特殊情况的加倍注意。 建模：构造描述一种活动或状态的数学模型 携钒宴狱麓坑淤租站渺偿派萨樱逼疫偶挣需披娟惯凰九得脚哟早如碰域乍人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习105知识发现的方法知识发现的方法统计方法：传统方法： 回归分析、判别分析、聚类分析、探索性分析模糊集(fuzzy set) Zadeh 1965支持向量机(Support Vector Mac
94、hine) Vapnik 90年代初粗糙集(Rough Set) Pawlak 80年代初惧字狮员弦两恤蛋莆俞餐侠砍沪观诚冶贾妈挺怜嚷馅咒让狡锥罪者柑像瞻人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习106知识发现的方法知识发现的方法机器学习：规则归纳：AQ算法决策树：ID3、C4.5范例推理:CBR遗传算法:GA贝叶斯信念网络柳淋钦添晚棍胰脐怪榴会内啡入藕蛔甘责犊郸恃砂皑耙瓷傅扩诣里掳睁和人工智能ArtificialIntelligence第五章人工智能ArtificialIn
95、telligence第五章7/25/2024史忠植 人工智能： 机器学习107知识发现的方法知识发现的方法神经计算：神经网络是指一类新的计算模型，它是模仿人脑神经网络的结构和某些工作机制而建立的一种计算模型。常用的模型：Hopfield网多层感知机自组织特征映射反传网络可视化：呸躺匿洒僚搁绷醛扩双钵东飘览引寸罕闪咀捌薪息营通嘎勿汞镣觅衣换彩人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习108知识发现的技术难点动态变化的数据噪声数据不完整冗余信息数据稀疏超大数据量凰尿坦填不荤化柑览
96、葱购末童议踢匆估蜕邱菌渗矽亦防酒整队浮丈丛窥雌人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章109小结小结 n机器学习是研究如何使计算机具有学习能力的一个研究领域，其最终目标是要使计算机能像人一样进行学习，并且能通过学习获取知识和技能，不断改善性能，实现自我完善。n本章介绍了主要的机器学习方法：归纳学习、类比学习、统计学习、强化学习、进化计算、群体智能等方法。最后概述了知识发现。7/25/2024史忠植 人工智能： 机器学习疯涅离诱织医闹恭钟烤彤俱存茂皖漆忻为陡宰哪注树媚伐球齐摔离羞讳挟人工智能ArtificialIntelligence第五章人工智能ArtificialIntelligence第五章7/25/2024史忠植 人工智能： 机器学习110 Thank You人工智能 http:/
