人工智能与专家系统（2011）

1、1,第七章 机器学习,7.1 机器学习概述 7.2 机械式学习 7.3 解释学习 7.4 归纳学习 7.5 类比学习,2,机器学习,经典定义：利用经验改善系统自身的性能 T.Mitchell, Book 97 随着该领域的发展，主要做智能数据分析 典型任务：预测 例如：天气预报,3,机器学习的重要性,美国航空航天局JPL实验室的科学家在Science（2001年9月）上撰文指出：机器学习对科学研究的整个过程正起到越来越大的支持作用，该领域在今后的若干年内将取得稳定而快速的发展。,生物 信息学,计算 金融学,分子 生物学,行星 地质学,工业过程控制,机器人,遥感信 息处理,信息安全,机 器 学

2、习,4,重要性：例子网络安全,入侵检测： 是否是入侵？是何种入侵？,如何检测？ 历史数据：以往的正常访问模式及其表现、以往的入侵模式及其表现 对当前访问模式分类,这是一个典型的预测型机器学习问题 常用技术： 神经网络 决策树 支持向量机 k近邻 序列分析 聚类 ,5,重要性：例子生物信息学,常用技术： 神经网络 支持向量机 隐马尔可夫模型 k近邻 决策树 序列分析 聚类 ,6,7.1 机器学习概述,机器学习的概念 学习系统模型 机器学习分类 机器学习的研究历史 机器学习的研究目标,7, 机器学习的概念, 什么是学习 Simon认为：如果一个系统能够通过执行某种过程而改进它的性能，这就是学习。

3、Minsky认为：学习是在人们头脑中（心理内部）进行有用的变化。 当前关于机器学习的许多文献中大体认为：学习是系统积累经验以改善其自身性能的过程。,8, 机器学习的概念,（2）什么是机器学习 学习是获取知识、积累经验、改进性能、发现规律、适应环境的过程。其基本机制是设法将在一种情形下成功的表现行为转移到另一类似的新情形中去。 机器学习是使系统做一些适应性的变化，使得系统在下一次完成类似的任务时比前一次更有效 （3）人类学习与机器学习 人类学习是个漫长的过程 人类学习不存在复制的过程 人类学习可以遗忘 人类学习是逐渐积累的过程,9, 机器学习系统,如果一个系统能够从某个过程或环境的未知特征中学习

4、到有关信息，并能把学到的信息用于对未来的估计、分类、决策或控制，以便改进系统的性能，那么它就是一个学习系统。,10,学习系统基本构成,11,一个学习系统至少应具有以下几部分 环境：包括工作对象和外界条件 学习环节：它通过对环境的搜索获取外部信息，然后经分析、综合、类比、推理等思维过程获得知识，并竟这些知识送入知识库。 知识库：知识库的形式就是知识表达的形式。知识表达形式应具有 可表达性 推理难度 可修改性 可扩展性 执行环节, 机器学习系统,12,机器学习系统的条件和能力,具有适当的学习环境 具有一定的学习能力 能应用学到的知识求解问题 能提高系统的性能,13, 机器学习分类, 基于推理策略的

5、分类 机械学习 讲授学习 演绎学习 解释学习 类比学习 归纳学习 基于系统性的分类 归纳学习 分析学习 联结学习 遗传学习,14,1）有导师学习（监督学习）：输入数据中有导师信号，以概率函数、代数函数或人工神经网络为基函数模型，采用迭代计算方法，学习结果为函数。 2）无导师学习（非监督学习）：输入数据中无导师信号，采用聚类方法，学习结果为类别。典型的无导师学习有发现学习、聚类、竞争学习等。 3）强化学习（增强学习）：以环境反馈（奖/惩信号）作为输入，以统计和动态规划技术为指导的一种学习方法。,（3）基于学习方式的分类,15, 机器学习的研究历史, 神经元模型研究阶段：W.S.McCulloch

6、和W.Pitts（1943）的模拟神经元的理论。 符号概念获取研究阶段：60年代初进入 符号学习发展阶段：70年代中期 联结学习和符号学习共发展阶段：80年代以后 1980年，在卡内机-梅隆大学召开第一届机器学习国际研讨会； 1986年创刊第一本机器学习杂志Machine learning。,16,机器学习现在已经发展到一个新阶段 机器学习起源于人工智能对人类学习能力的追求，上一阶段的研究几乎完全局限在人工智能这一领域中（学习本身是目的） 而现在，机器学习已经开始进入了计算机科学的不同领域，甚至其他学科，成为一种支持技术、服务技术（学习本身是手段）,如果我们想做出重要的贡献， 首先需要把握住该

7、领域发展的脉搏。,17, 机器学习目标有三个，即 通用学习算法：这个方向的研究是理论分析和开发用于非实用的学习任务算法。 认知模型：这是研究人类学习机制和思维方法。 (3) 工程目标：这个研究目标就是解决专门的实际问题，并开发完成这些任务的工程系统。, 机器学习的研究目标,18,实例学习例子,训练实例集合: 1.(乌鸦w1，羽毛黑); 2.(乌鸦w2，羽毛浅黑); 3.(麻雀w3，羽毛灰); 4.(鸽子w4，羽毛白); 5.( 乌鸦w5，羽毛白);6.(乌鸦w6，羽毛黑)； 7.(乌鸦w7，羽毛黑); 8.(燕子w8，羽毛灰) 根据训练实例集合提出规则(假设）: 乌鸦(x)黑（羽毛） 黑（羽毛

8、） 乌鸦(x) 归纳： (乌鸦，黑色的羽毛) 可信度：4/5=0.8,19,7.2 机械式学习 (Rote Learning),机械学习是最简单的机器学习方法。 机械学习就是记忆学习，即把新的知识存储起来，供需要时检索调用，而不需要计算和推理。 机械学习又是最基本的学习过程。任何学习系统都必须记住它们获取的知识。 其实质是用存储空间来换取处理时间。,20,机械学习基本思想,可把学习系统的执行部分抽象地看成某个函数， 该函数在得到自变量输入值之后，计算并输出函数值。 机械学习在存储器中简单地记忆存储对,21,当需要 执行部分就从存储器中把 简单地检索出来而不是重新计算它。 这种简单的学习模式如下

9、：,机械学习基本思想,22,例如我们可以在大量病例的基础上归纳总结出治疗的一般规律，形成规则，当遇见一个新病例时，我们就使用规则去处理它，而不必参照以前的众多病例推断解决办法。化简的目的，主要是为了提高工作效率。,23,机械学习的主要问题,存储组织信息 环境的稳定性与存储信息的适用性问题 存储与计算之间的权衡,24,7.3 解释学习,Explanation-Based Learning, 简称EBL，是20世纪80年代中兴起的机器学习方法，它是一种演绎学习方法。 解释学习是通过运用相关的领域知识及一个训练实例来对某一目标概念进行学习，从而构造解释并产生相应的知识，以便用于指导以后求解类似问题。

10、,25,解释学习,1983年美国Illinois大学的DeJong提出。 1986年, Mitchell, Keller 和 Kedar-Cabelli 提出了解释的泛化(Explanation-Based Generalization, 简称EBG)的统一框架, 1986年DeJong 和Mooney提出全局取代解释泛化Explanation Generalization using Global Substitutions, 缩写EGGS) 方法 1987年卡耐基-梅隆大学的Minton 和 Carbonell提出解释特化 (Explanation-Based Specialization

11、，简写EBS)学习方法,26,（1）解释学习的过程,利用基于解释的方法对训练实例进行分析与解释，以说明它是目标概念的一个实例。 对实例的结构进行概括性解释，建立该训练实例的解释结构以满足所学概念的定义；解释结构的各个叶节点应符合可操作标准，且使这种解释比最初的例子适用于更大的一类例子。 从解释结构中识别出训练实例的特性，并从中得到更大一类例子的概括性描述，获取一般控制知识。,27,EBL的效率,选择一条通用规则 太多规则 - 推理太慢 目标驱动 - 极大地提高了速度 尽可能的通用 可操作性 - 一个子目标是可操作的，意思是容易解决 可操作性和通用性之间的平衡 对EBL学习效率的实验分析,28,

12、（2 ） 解释学习模型,概念描述空间,概念空间,例子空间,D1 不可操作的,可操作 D2,C1,I1,I2,I3,解释学习的空间描述,29,例子,目标概念：一对物体，SAFE-TO-STACK(x,y)，其中STACK(x,y)NOT(FRAGILE(y)LIGHTER(x,y)。 训练实例： ON(OBJ1,OBJ2) ISA(OBJ1,BOX) ISA(OBJ2,ENDTABLE) COLOR(OBJ1,RED) COLOR(OBJ2,BLUE) VOLUME(OBJ1,1) DENSITY(OBJ1,.1) ,30,领域知识： VOLUME(p1,v1)DENSITY(p1,d1)WEI

13、GHT(p1,v1*d1) WEIGHT(p1,w1)WEIGHT(p2,w2)LESS(w1,w2)LIGHTER(p1,p2) ISA(p1,ENDTABLE)WEIGHT(p1,5)(default) LESS(.1,5) 可操作标准：概念定义必须要用描述实例中的谓词，或者选自领域知识易于评测的谓词。 确定： 训练实例的泛化是对目标概念给以充分定义，并且满足可操作性标准。,31,知识库中的领域知识是把一个物体放置到另一个物体上的安全性标准则：,32,SAFE-TO-STACK(OBJ1,OBJ2)解释树,33,7.4 归纳学习（ inductive learning ）,归纳学习是 研究

14、最广的一种符号学习（symbolic learning）方法 ，它表示从例子设想出假设的过程。 在进行归纳学习时，学习者从所提供的事实或观察到的假设进行归纳推理，获得某个概念。 归纳推理是个从部分到全体，从特殊到一般的推理过程。,34,（1）归纳推理的方法,归纳是指从个别到一般，从部分到整体的一类推论行为。归纳推理是应用归纳方法所进行的推理，即从足够多的事例中归纳出一般性的知识，它是一种从个别到一般的推理。 在进行归纳时，多数情况下不可能考察全部有关的事例，因而归纳出的结论不能绝对保证它的正确性，只能以某种程度相信它为真，这是归纳推理的一个重要特征。,35,归纳推理的方法,枚举归纳 联想归纳

15、类比归纳 逆推理归纳,36, 枚举归纳,设a1，a2，是某类事物中的具体事物，若已知a1，a2，an，都有属性P，并且没有发现反例，当n足够大时，就可得出 “A中所有事物都有属性P”的结论。这是一种从个别事例归纳出一般性知识的方法，“A中所有事物都有属性P”是通过归纳得到的新知识。,37, 联想归纳,若已知两个事物a与b有n个属性相似或相同，即： a具有属性Pl，b也具有属性Pl； a具有属性P2，b也具有属性P2； a具有属性Pn，b也具有属性Pn。 且发现a具有属性Pn+1，则当n足够大时，可归纳出：b也具有属性Pn+1这一新知识。,38, 类比归纳,设A，B分别是两类事物的集合： A=a

16、1，a2， B=b1，b2， 并设ai与bi总是成对地出现，且当ai有属性P时，bi就有属性Q与之对应，即 P（ai）Q（bi） i=1，2， 则当A与B中有一对新元素出现时（设为A中的，及B中的 ），若已知 有属性P，就可得出 有属性Q，即,39, 逆推理归纳,一种由结论成立而推出前提以某种置信度成立的归纳方法。日常生活及科学研究中经常使用这种方法进行归纳推理。一般模式是：(a) 若H为真时，则HE必为真或以置信度cf1成立。(b) 观察到E成立或以置信度cf2成立。(c) 则H以某种置信度(cf)成立。,40,（2）归纳学习方法,归纳学习是应用归纳推理进行学习的一类方法，按其有无教师指导可

17、分为示例学习及观察与发现学习。 示例学习 观察与发现学习,41,示例学习,示例学习（Learning from examples）又称为实例学习或从例子中学习，它是通过从环境中取得若干与某概念有关的例子，经归纳得出一般性概念的学习方法。,42,示例学习,学习过程是：首先从示例空间（环境）中选择合适的训练示例，然后经解释归纳出一般性的知识，最后再从示例空间中选择更多的示例对它进行验证，直到得到可实用的知识为止。,43,示例学习的学习模型,44,实例学习例子,训练实例集合: 1.(乌鸦w1，羽毛黑); 2.(乌鸦w2，羽毛浅黑); 3.(麻雀w3，羽毛灰); 4.(鸽子w4，羽毛白); 5.( 乌

18、鸦w5，羽毛白);6.(乌鸦w6，羽毛黑)； 7.(乌鸦w7，羽毛黑); 8.(燕子w8，羽毛灰) 根据训练实例集合提出规则(假设）: 乌鸦(x)黑（羽毛） 黑（羽毛） 乌鸦(x) 归纳： (乌鸦，黑色的羽毛) 可信度：4/5=0.8,45,观察与发现学习,观察与发现 学习（Learning from observation and discovery）分为观察学习与机器发现两种。前者用于对事例进行概念聚类，形成概念描述；后者用于发现规律，产生定律或规则。,46,概念聚类,概念聚类 是观察学习研究中的一个 重要技术，是由米卡尔斯基（RSMichalski）在1980年首先提出来的，其基本思想是

19、把事例按一定的方式和准则进行分组，如划分为不同的类，不同的层次等，使不同的组代表不同的概念，并且对每一个组进行特征概括，得到一个概念的语义符号描述。,47,实 例,对如下事例： 喜鹊、麻雀、布谷鸟、乌鸦、鸡、鸭、鹅 可根据它们是否家养分为如下两类： 鸟喜鹊，麻雀，布谷鸟，乌鸦 家禽鸡、鸭、鹅,48,实 例,“鸟”和“家禽”就是由分类得到的新概念，而且根据相应动物的特征还可得知： “鸟有羽毛、有翅膀、会飞、会叫、野生” “家禽有羽毛、有翅膀、不会飞、会叫、家养” 如果把它们的共同特性抽取出来，就可以进一步形成“鸟类”的概念,49,机器发现,机器发现是指从观察的事例或经验数据中归纳出规律或规则，这

20、是最困难且最富创造性的一种学习。 可分为经验发现与知识发现两种，前者指从经验数据中发现规律和定律，后者是指从已观察的事例中发现新的知识。,50,知识发现的发展和定义,知识发现的产生和发展 知识发现最早是于1989年8月在第11届国际人工智能联合会议的专题讨论会上提出。随着互联网的发展，网上设立了不少研究KDD的网站、论坛和报导。在研究的基础上，也出现一些KDD产品和应用系统，引起企业界的关注。 定义：数据库中的知识发现是从大量数据中辨识出有效的、新颖的、潜在有用的、并可被理解的模式的高级处理过程。,51,数据集：是指一个有关事实F的集合，是用来描述事物有关方面信息，是进一步发现知识的原材料。

21、新颖：经过知识发现提取出的模式必须是新颖的。 潜在有用：提取出的模式应该是有意义的，这可以通过某些函数的值来衡量。 可被人理解：知识发现的一个目标就是将数据库中隐含的模式以容易被人理解的形式表现出来，从而帮助人们更好地了解数据库中所包含的信息。 模式 高级过程,52,知识发现的处理过程,数据选择：根据用户的需求从数据库中提取与KDD相关的数据。 数据预处理：主要是对上述数据进行再加工，检查数据的完整性及数据的一致性，对丢失的数据利用统计方法进行填补，形成发掘数据库。 数据变换：即从发掘数据库里选择数据。 数据挖掘：根据用户要求，确定KDD的目标是发现何种类型的知识。 知识评价：这一过程主要用于

22、对所获得的规则进行价值评定，以决定所得的规则是否存入基础知识库。,53,知识发现的步骤（三步曲）,数据收集 与准备,数据分析与算法实现,知识和模式,数据预处理,数据建模与挖掘,结果解释与评价,54,知识发现的方法,统计方法 统计方法是从事物的外在数量上的表现去推断该事物可能的规律性。 机器学习方法 (1) 规则归纳。规则反映数据项中某些属性或数据集中某些数据项之间的统计相关性。 (2) 决策树。决策树的每一个非终叶节点表示所考虑的数据项的测试或决策。 (3) 贝叶斯网络。贝叶斯网络是概率分布的图表示。 (4) 遗传算法。在求解过程中，通过最好解的选择和彼此组合，使期望解的集合愈来愈好。 神经计

23、算方法 可视化方法 可视化（visualization）就是把数据、信息和知识转化为可视的表示形式的过程。,55, 关联规则, 决策树技术, 贝叶斯网络, 遗传算法, 人工神经网络, 粗糙集方法,知识发现的技术方法,56,知识发现的应用,知识发现已在许多领域得到应用，且应用领域越来越广。现在，知识发现已在银行业、保险业、零售业、医疗保健、工程和制造业、科学研究、卫星观察和娱乐业等行业和部门得到成功应用，为人们的科学决策提供很大帮助。,57,购物篮分析商品搭配与货物布局 ，优化库存与网站设计； 客户关系管理客户服务 、客户保留、客户识别 ； 市场营销商品促销、交叉销售； 信用评估与欺诈检测。,58,留住最有价值客户,数据挖掘可以,59,沃尔玛是世界第一大零售集团公司，最近一个财政年度销售额2880亿美元，员工超过160万，全球拥有4500多家连锁店，每周光临沃尔玛的顾客近1.4亿人次！ 最核心竞争力是RetailLink系统（采用数据挖掘技术）,60,五角大楼 与saffron科技公司（从事数据挖掘） 合作研究和开发情报。 伊拉克战争，美国利用数据挖掘等技术制定“联合一体化目标清单”，包括针对伊领导集团及相关的目标4559个。 运用数据挖掘，对武器性能进行评估和模拟，对作战方案进行论证