第十讲-机器学习ppt课件

机器学习机器学习机器学习1什么是机器学习？什么是机器学习？l人工智能大师人工智能大师Herb Simon这样定义学习：这样定义学习：学习：系统在不断重复的工作中对本身能力的学习：系统在不断重复的工作中对本身能力的增强或改进，使得系统在下一次执行相同任务增强或改进，使得系统在下一次执行相同任务或类似任务（指的是具有相同分布的任务）时，或类似任务（指的是具有相同分布的任务）时，比现在做的更好或效率更高。比现在做的更好或效率更高。机器学习：通过经验提高系统自身的性能的机器学习：通过经验提高系统自身的性能的过程（系统自我改进）。过程（系统自我改进）。什么是机器学习？人工智能大师Herb Simon这样定义学习2机器学习的重要性机器学习的重要性l 机器学习是人工智能的主要核心研究领域之机器学习是人工智能的主要核心研究领域之一一,也是现代智能系统的关键环节和瓶颈。也是现代智能系统的关键环节和瓶颈。l 很难想象很难想象:一个没有学习功能的系统是能被一个没有学习功能的系统是能被称为是具有智能的系统。称为是具有智能的系统。机器学习的重要性3第十讲-机器学习ppt课件4第十讲-机器学习ppt课件5第十讲-机器学习ppt课件6信息检索（信息检索（Information Retrieval)信息检索（Information Retrieval)7第十讲-机器学习ppt课件8第十讲-机器学习ppt课件9第十讲-机器学习ppt课件105511机器学习的任务机器学习的任务l令令W W是这个给定世界的有限或无限所有对象的集是这个给定世界的有限或无限所有对象的集合，由于观察能力的限制，我们只能获得这个合，由于观察能力的限制，我们只能获得这个世界的一个有限的子集世界的一个有限的子集Q Q W W，称为样本集。，称为样本集。l 机器学习就是根据这个有限样本集机器学习就是根据这个有限样本集Q Q，推算这，推算这个世界的模型，使得其对这个世界为真。个世界的模型，使得其对这个世界为真。机器学习的任务令W是这个给定世界的有限或无限所有对象的集合，12机器学习的三要素机器学习的三要素l一致性假设：机器学习的条件。一致性假设：机器学习的条件。l样本空间划分：决定模型对样本集合的样本空间划分：决定模型对样本集合的有效性。有效性。l泛化能力：决定模型对世界的有效性。泛化能力：决定模型对世界的有效性。机器学习的三要素一致性假设：机器学习的条件。13要素要素1：一致性假设：一致性假设l假设世界假设世界W与样本集与样本集Q具有某种相同的性质。具有某种相同的性质。l原则上说，存在各种各样的一致性假设。原则上说，存在各种各样的一致性假设。l在统计意义下，一般假设：在统计意义下，一般假设：lW与与Q具有同分布。或，具有同分布。或，l给定世界给定世界W的所有对象独立同分布。的所有对象独立同分布。要素1：一致性假设假设世界W与样本集Q具有某种相同的性质。14要素要素2：对样本空间的划分：对样本空间的划分l样本集合模型样本集合模型：将样本集放到一个将样本集放到一个n维空间，寻找一个超维空间，寻找一个超平面平面(等价关系等价关系)，使，使得问题决定的不同对得问题决定的不同对象被划分在不相交的象被划分在不相交的区域。区域。要素2：对样本空间的划分样本集合模型：15要素要素3：泛化能力泛化能力l泛化能力：学习的目的是学到隐含在数据对背泛化能力：学习的目的是学到隐含在数据对背后的规律后的规律,对具有同一规律的学习集以外的数对具有同一规律的学习集以外的数据据,该神经网络仍具有正确的响应能力该神经网络仍具有正确的响应能力,称为泛称为泛化能力化能力.l通过机器学习方法，从给定有限样本集合计算通过机器学习方法，从给定有限样本集合计算一个模型，泛化能力是这个模型对世界为真程一个模型，泛化能力是这个模型对世界为真程度的指标。度的指标。要素3：泛化能力泛化能力：学习的目的是学到隐含在数据对背16关于三要素关于三要素l不同时期，研究的侧重点不同不同时期，研究的侧重点不同l划分划分:早期研究主要集中在该要素上早期研究主要集中在该要素上l泛化能力泛化能力(在多项式划分在多项式划分):80):80年代以来的近期年代以来的近期研究研究l一致性假设一致性假设:未来必须考虑（未来必须考虑（Transfer Transfer learninglearning）关于三要素不同时期，研究的侧重点不同17Transfer learninglTransfer learning 这一概念是由这一概念是由 DARPA（美国国防高级研究计划局）在（美国国防高级研究计划局）在2005年正式提出来的一项研究计划。年正式提出来的一项研究计划。lTransfer Learning 是指系统能够将在先前是指系统能够将在先前任务中学到的知识或技能应用于一个新任务中学到的知识或技能应用于一个新的任务或新的领域。的任务或新的领域。Transfer learningTransfer lear18传统机器学习传统机器学习&转移学习转移学习传统机器学习&转移学习19Transfer Learning=“举一反三举一反三”l我们人类也具有这样的能力，比如我们学会了我们人类也具有这样的能力，比如我们学会了国际象棋，就可以将下棋的方法应用于跳棋，国际象棋，就可以将下棋的方法应用于跳棋，或者说学起跳棋来会更容易一些；学会了或者说学起跳棋来会更容易一些；学会了C+，可以把它的一些思想用在学习，可以把它的一些思想用在学习Java中；再比中；再比如某人原来是学物理的，后来学习计算机时，如某人原来是学物理的，后来学习计算机时，总习惯把物理中的某些思想和概念用于计算机总习惯把物理中的某些思想和概念用于计算机科学中。用我们通俗的话总结，就是科学中。用我们通俗的话总结，就是l传统机器学习传统机器学习=“种瓜得瓜，种豆得豆种瓜得瓜，种豆得豆”l迁移学习迁移学习=“举一反三举一反三”Transfer Learning=“举一反三”我们人类20机器学习是多学科的交叉机器学习是多学科的交叉机器学习是多学科的交叉21机器学习学科机器学习学科l19831983年，年，R.S.MichalskiR.S.Michalski等人撰写机器学习：等人撰写机器学习：通往人工智能的途径一书通往人工智能的途径一书l 1986 1986年，年，Machine LearningMachine Learning杂志创刊杂志创刊l19971997年以年以Tom MitchellTom Mitchell的经典教科书的经典教科书machine learning中都没有贯穿始终的基中都没有贯穿始终的基础体系，只不个是不同方法和技术的罗列础体系，只不个是不同方法和技术的罗列l机器学习还非常年轻、很不成熟机器学习还非常年轻、很不成熟机器学习学科1983年，R.S.Michalski等人撰写22机器学习的分类机器学习的分类l传统上，大致可分为传统上，大致可分为4 4类：类：l归纳学习归纳学习l解释学习解释学习l遗传学习（遗传学习（GA)GA)l连接学习连接学习(神经网络）神经网络）机器学习的分类传统上，大致可分为4类：23归纳学习归纳学习l是从某一概念的分类例子集出发归纳出一般的是从某一概念的分类例子集出发归纳出一般的概念描述。概念描述。l这是目前研究得最多的学习方法，其学习目的这是目前研究得最多的学习方法，其学习目的是为了获得新的概念、构造新的规则或发现新是为了获得新的概念、构造新的规则或发现新的理论。的理论。l这种方法要求大量的训练例，而且归纳性能受这种方法要求大量的训练例，而且归纳性能受到描述语言、概念类型、信噪比、实例空间分到描述语言、概念类型、信噪比、实例空间分布、归纳模式等的影响。布、归纳模式等的影响。归纳学习是从某一概念的分类例子集出发归纳出一般的概念描述。24解释学习解释学习l（分析学习）是从完善的领域理论出发演绎出（分析学习）是从完善的领域理论出发演绎出有助于更有效地利用领域理论的规则。其学习有助于更有效地利用领域理论的规则。其学习目的是提高系统性能，而不是修改领域理论。目的是提高系统性能，而不是修改领域理论。l它与归纳学习相反，只需要少量的训练例，但它与归纳学习相反，只需要少量的训练例，但要求有完善的领域理论，而且学习效果也与例要求有完善的领域理论，而且学习效果也与例子表示形式、学习方法（正例学习或反例学习）子表示形式、学习方法（正例学习或反例学习）、概括程度等有关。、概括程度等有关。解释学习（分析学习）是从完善的领域理论出发演绎出有助于更有效25机器学习面临的挑战机器学习面临的挑战l随着应用的不断深入随着应用的不断深入,出现了很多被传统机器出现了很多被传统机器学习研究忽视、但非常重要的问题（下面将以学习研究忽视、但非常重要的问题（下面将以医疗和金融为代表来举几个例子）医疗和金融为代表来举几个例子）l机器学习正与众多学科领域产生了交叉，交叉机器学习正与众多学科领域产生了交叉，交叉领域越多领域越多,问题也越多问题也越多,也正是大有可为处也正是大有可为处.机器学习面临的挑战随着应用的不断深入,出现了很多被传统机器26例子1：代价敏感问题l医疗：以癌症诊断为例，医疗：以癌症诊断为例，“将病人误诊为健康将病人误诊为健康人的代价人的代价”与与“将健康人误诊为病人的代价将健康人误诊为病人的代价”是不同的。是不同的。l金融：以信用卡盗用检测为例，金融：以信用卡盗用检测为例，“将盗用误认将盗用误认为正常使用的代价为正常使用的代价”与与“将正常使用误认为盗将正常使用误认为盗用的代价用的代价”是不同的。是不同的。l传统的传统的MLML技术基本上只考虑同一代价技术基本上只考虑同一代价l如何处理代价敏感性？如何处理代价敏感性？l在教科书中找不到现成的答案。在教科书中找不到现成的答案。例子1：代价敏感问题医疗：以癌症诊断为例，“将病人误诊为健康27例子2：不平衡数据问题l医疗：以癌症诊断为例，医疗：以癌症诊断为例，“健康人健康人”样本远远样本远远多于多于“病人病人”样本。样本。l金融：以信用卡盗用检测为例，金融：以信用卡盗用检测为例，“正常使用正常使用”样本远远多于样本远远多于“被盗用被盗用”样本。样本。l传统的传统的MLML技术基本上只考虑平衡数据技术基本上只考虑平衡数据l如何处理数据不平衡性？如何处理数据不平衡性？l在教科书中找不到现成的答案在教科书中找不到现成的答案例子2：不平衡数据问题医疗：以癌症诊断为例，“健康人”样本远28例子3：可理解性问题l医疗：以乳腺癌诊断为例，需要向病人解释医疗：以乳腺癌诊断为例，需要向病人解释“为什么做出这样的诊断为什么做出这样的诊断”l金融：以信用卡盗用检测为例，需要向保安部金融：以信用卡盗用检测为例，需要向保安部门解释门解释“为什么这是正在被盗用的卡为什么这是正在被盗用的卡”l传统的传统的MLML技术基本上只考虑泛化不考虑理解技术基本上只考虑泛化不考虑理解l如何处理可理解性？如何处理可理解性？l在教科书中找不到现成的答案在教科书中找不到现成的答案例子3：可理解性问题医疗：以乳腺癌诊断为例，需要向病人解释“29机器学习的最新进展机器学习的最新进展l 算法驱动算法驱动(建模与数据分析建模与数据分析)l 应用驱动应用驱动机器学习的最新进展30算法驱动算法驱动l海量非线性数据海量非线性数据(10(108-108-10)l算法的泛化能力考虑算法的泛化能力考虑l学习结果数据的解释学习结果数据的解释l代价加权的处理方法代价加权的处理方法l不同数据类型的学习方法不同数据类型的学习方法算法驱动31应用驱动应用驱动l自然语言分析、网络与电信数据分析、图像数自然语言分析、网络与电信数据分析、图像数据分析、金融与经济数据分析、零售业数据分据分析、金融与经济数据分析、零售业数据分析、情报分析。析、情报分析。l Web Web信息的有效获取信息的有效获取(新一代搜索引擎新一代搜索引擎)。由此。由此导导 致各种学习任务：数据流学习、多实例学习致各种学习任务：数据流学习、多实例学习(部分放弃独立同分布条件部分放弃独立同分布条件)、RankingRanking学习、蛋学习、蛋白质功能分析白质功能分析,DNA,DNA数据分析，数据分析，.它们需要使用各种不同方法，解决实际问题。它们需要使用各种不同方法，解决实际问题。应用驱动自然语言分析、网络与电信数据分析、图像数据分析、金32应用驱动机器学习应用驱动机器学习l 流形机器学习流形机器学习l半监督机器学习半监督机器学习l多实例机器学习多实例机器学习lRankingRanking机器学习机器学习l数据流机器学习数据流机器学习l图模型机器学习图模型机器学习l应用驱动机器学习 流形机器学习33 流形机器学习流形机器学习高维数据的低维表示高维数据的低维表示l流形（流形（manifoldmanifold）就是一般的几何对象的总称。比如人，）就是一般的几何对象的总称。比如人，有中国人、美国人等等；流形就包括各种维数的曲线曲有中国人、美国人等等；流形就包括各种维数的曲线曲面等。和一般的降维分析一样，流形学习把一组在高维面等。和一般的降维分析一样，流形学习把一组在高维空间中的数据在低维空间中重新表示。空间中的数据在低维空间中重新表示。l比如在基于内容的图像检索中，当特征向量的维数非常比如在基于内容的图像检索中，当特征向量的维数非常高时，建立图像特征库时的存储高维特征的空间复杂度高时，建立图像特征库时的存储高维特征的空间复杂度和度量图像之间相似性的运算复杂度都将非常的高。和度量图像之间相似性的运算复杂度都将非常的高。l线性方法线性方法l PCA(Principal Component Analysis)PCA(Principal Component Analysis)l ICA(Independent Component Analysis)ICA(Independent Component Analysis)l非线性方法非线性方法l LLE(Local linear Embeding)(Roweis,LLE(Local linear Embeding)(Roweis,Science,2000)Science,2000)l Isomap(Tenenbaum,Science,2000)Isomap(Tenenbaum,Science,2000)流形机器学习高维数据的低维表示流形（manifold）34l比较常用的降维算法比如比较常用的降维算法比如PCAPCA，是针对线性分布的，是针对线性分布的高维数据进行降维的算法，并且有局部最优的问高维数据进行降维的算法，并且有局部最优的问题。而题。而LLELLE（Local Linear EmbeddingLocal Linear Embedding）算法则针）算法则针对于非线性数据。对于非线性数据。在这个例子里，用在这个例子里，用LLE LLE 进行降维成功的体进行降维成功的体现了数据内在的局部分布结构，而用现了数据内在的局部分布结构，而用PCA PCA 映射则会将映射则会将高维空间里的远点映射到低维空间后变成了近邻点。高维空间里的远点映射到低维空间后变成了近邻点。比较常用的降维算法比如PCA，是针对线性分布的高维数据进行降35半监督机器学习半监督机器学习l半监督的学习半监督的学习:有少量训练样本有少量训练样本,学习机以从训学习机以从训练样本获得的知识为基础练样本获得的知识为基础,结合测试样本的分结合测试样本的分布情况逐步修正已有知识布情况逐步修正已有知识,并判断测试样本的并判断测试样本的类别。类别。半监督机器学习半监督的学习:有少量训练样本,学习机以从训练样36多示例机器学习多示例机器学习l 传统的机器学习中，一个对象有一个描述，传统的机器学习中，一个对象有一个描述，而在一些实际问题中，一个对象可能同时有多而在一些实际问题中，一个对象可能同时有多个描述，到底哪个描述是决定对象性质个描述，到底哪个描述是决定对象性质(例如例如类别类别)的，却并不知道。解决这种的，却并不知道。解决这种“对象：描对象：描述：类别述：类别”之间之间1:N:11:N:1关系的学习就是多示例关系的学习就是多示例学习学习多示例机器学习 传统的机器学习中，一个对象有一个描述，而在一37Ranking机器学习机器学习l其原始说法是其原始说法是learning for rankinglearning for rankingl问题主要来自信息检索，假设用户的需求不能问题主要来自信息检索，假设用户的需求不能简单地表示为简单地表示为“喜欢喜欢”或或“不喜欢不喜欢”，而需要，而需要将将“喜欢喜欢”表示为一个顺序，问题是如何通过表示为一个顺序，问题是如何通过学习，获得关于这个学习，获得关于这个“喜欢喜欢”顺序的模型。顺序的模型。Ranking机器学习其原始说法是learning for 38第十讲-机器学习ppt课件39数据流机器学习数据流机器学习l在网络数据分析与处理中，有一类问题，在网络数据分析与处理中，有一类问题，从一个用户节点上流过的数据，大多数从一个用户节点上流过的数据，大多数是无意义的，由于数据量极大，不能全是无意义的，由于数据量极大，不能全部存储，因此，只能简单判断流过的文部存储，因此，只能简单判断流过的文件是否有用，而无法细致分析件是否有用，而无法细致分析l如何学习一个模型可以完成这个任务，如何学习一个模型可以完成这个任务，同时可以增量学习，以保证可以从数据同时可以增量学习，以保证可以从数据流中不断改善流中不断改善(或适应或适应)用户需求的模型用户需求的模型数据流机器学习在网络数据分析与处理中，有一类问题，从一个用户40研究现状研究现状l主要以任务为驱动力主要以任务为驱动力,学习方法有待创新学习方法有待创新l以上这些机器学习方式还处于实验观察以上这些机器学习方式还处于实验观察阶段，缺乏坚实的理论基础阶段，缺乏坚实的理论基础l实际应用效果仍有待研究实际应用效果仍有待研究研究现状41当前机器学习所面临情况是：当前机器学习所面临情况是：l数据复杂、海量，用户需求多样化。从而数据复杂、海量，用户需求多样化。从而,要要求：求：(1)(1)需要科学和高效的问题表示，以便将其学习建需要科学和高效的问题表示，以便将其学习建立在科学的基础上立在科学的基础上(2)(2)应用驱动成为必然应用驱动成为必然,从而针对某个或某类应用从而针对某个或某类应用给出特定的学习方法将不断涌现给出特定的学习方法将不断涌现(3)(3)对机器学习的检验问题只能在应用中检验自己对机器学习的检验问题只能在应用中检验自己(4)(4)对机器学习的结果的解释对机器学习的结果的解释,将逐渐受到重视将逐渐受到重视当前机器学习所面临情况是：数据复杂、海量，用户需求多样化。从42 现在我们逐一讨论几种比较现在我们逐一讨论几种比较常用的学习算法常用的学习算法 现在我们逐一讨论几种比较常用的学习算法43 7.3 机械学习机械学习l机械学习（机械学习（Rote LearningRote Learning）又称为记忆学习或死记硬背式的学习。这种学习方法直接记忆或存储环境提供的新知识，并在以后通过对知识库的检索来直接使用这些知识，而不再需要进行任何的计算和推导。7.3 机械学习机械学习（44l机械学习是一种基本的学习过程，虽然它没有足够的能力独立完成智能学习，但存储对于任何智能型的程序来说，都是必要的和基本的。记忆学习是任何学习系统的一部分，任何学习系统都要将它所获取的知识存储在知识库中，以便使用这些知识。机械学习是一种基本的学习过程，虽然它没有足够的能力独立完成智45机械学习的过程机械学习的过程 l执行机构每解决一个问题，系统就记住这个问题和它的解。简单的机械学习模型：f存储存储输入输出知识联想对执行单元机械学习的过程 执行机构每解决一个问题，系统就记住这个问题和46例子：汽车修理成本估算系统例子：汽车修理成本估算系统 l输入：有关待修理汽车的描述，包括制造厂家、出厂日期、车型、汽车损坏的部位以及它的损坏程度l输出：该汽车的修理成本 例子：汽车修理成本估算系统 输入：有关待修理汽车的描述，包括47例子：汽车修理成本估算系统例子：汽车修理成本估算系统l为了进行估算，系统必须在其知识库中查找同一厂家，同一出厂日期、同一车型、同样损坏情况的汽车，然后把知识库中对应的数据作为修理成本的估算数据输出给用户。如果在系统的知识库中没有找到这样的汽车，则系统将请求用户给出大致的费用并进行确认，系统则会将该车的描述和经过确认的估算费用存储到知识库中，以便将来查找使用。例子：汽车修理成本估算系统为了进行估算，系统必须在其知识库中48数据化简级别图数据化简级别图l莱纳特(Lenat)，海斯罗思(Hayes Roth)和克拉尔(Klahr)等人于1979年提出：可以把机械学习看成是数据化简分级中的第一级。机械学习与计算、归纳和推理之间的关系如下图所示。数据化简级别图莱纳特(Lenat)，海斯罗思(Hayes 49存储计算推导归纳算法与理论机械记忆搜索规则可以在大量病例的基础上归纳总结出治疗的一般规律，形成规则，当遇见个新病例时，就使用规则去处理它，而不必再重新推断解决办法，提高了工作效率。在机械学习中，我们忽略计算过程，只记忆计算的输入输出，这样就把计算问题化简成另外存储问题。数据化简级别图数据化简级别图 例如，第一次解一个一元二次方程的时候，必须使用很长的一段推导才能得出解方程的求根公式。但是一旦有了求根公式，以后再解一元二次方程时，就不必重复以前的推导过程，可以直接使用求根公式计算出根，这样就把推导问题简化成计 算问题存储计算推导归纳算法与理论机械记忆搜索规则可以在大量病例的基50机械学习要注意的问题机械学习要注意的问题l存储组织信息l如何存储？使得 检索时间 Q(a)P(a)-Q(a)(2)(2)推广：推广：,P(x ,P(x）-Q(x)-Q(x)(3),P(x (3),P(x）-Q(x)-Q(x)(4)(4)利用假言推理，利用假言推理，P(b)P(b)，P(x P(x）-Q(x)-Q(x)，得出得出b b具有性质具有性质Q Q。类比学习形式已知：aS与bT具有相似的性质P，a还具有性55类比学习研究类型类比学习研究类型l问题求解型已知因果关系S1:A-B,现有AA,A,则可能有BB满足A-BA-B求解一个新问题时，先回忆以前是否求解过类似问题，若是，则以此为依据求解新问题。用来推断一个不完全确定的事物可能还有的其他属性l预测推理型l传统的类比法l因果关系型类比学习研究类型问题求解型已知因果关系S1:A-B,求解一56 7.6 解释学习解释学习 l基于解释的学习(Explanation-based learning,EBL)解释学习兴起于20世纪80年代中期，根据任务所在领域知识和正在学习的概念知识，对当前实例进行分析和求解，得出一个表征求解过程的因果解释树，以获取新的知识。7.6 解释学习 基于解释的学习(57l 例如，学生根据教师提供的目标概念、该概念的一个例子、领域理论及可操作准则，首先构造一个解释来说明为什该例子满足目标概念，然后将解释推广为目标概念的一个满足可操作准则的充分条件。l EBL已被广泛应用于知识库求精和改善系统的性能。著名的EBL系统有迪乔恩（G.DeJong）的GENESIS,米切尔（T.Mitchell）的LEXII和LEAP,以及明顿（S.Minton）等的PRODIGY。例如，学生根据教师提供的目标概念、该概念的一个例58解释学习的一般性描述解释学习的一般性描述l米切尔提出了一个解释学习的统一算法EBG,建立了基于解释的概括过程，并用知识的逻辑表示和演绎推理进行问题求解。其一般性描述为：给定：领域知识DT 目标概念TC 训练实例TE 操作性准则OC 找出：满足OC的关于TC的充分条件目标概念新规则操作准则训练例子知识库解释学习的一般性描述米切尔提出了一个解释学习的统一算法EBG59l系统进行学习时，首先运用领域知识DT找出训练实例TE为什么是目标概念TC的实例的解释，然后根据操作性准则OC对解释进行推广，从而得到关于目标概念TC的一个一般性描述，即一个可供以后使用的形式化表示的一般性知识。系统进行学习时，首先运用领域知识DT找出训练实例TE为什么是60解释学习的学习过程与算法解释学习的学习过程与算法EBG算法可概括为两步：1.构造解释 运用领域知识进行演绎，证明提供给系统的训练实例为什么是满足目标概念的一个实例。例如：设要学习的目标概念是“一个物体（Obj1）可以安全地放置在另一个物体（Obj2）上”，即 Safe-To-Stack(Obj1,obj2)解释学习的学习过程与算法EBG算法可概括为两步：61l训练实例为描述物体Obj1与Obj2的下述事实：On(Obj1,Obj2)Isa(Obj1,book of AI)Isa(Obj2,table)Volume(Obj1,1)Density(Obj1,0.1)l 领域知识是把一个物体放置在另一个物体上面的安全性准则：Fragile(y)Safe-To-Stack(x,y)Lighter(x,y)Safe-To-Stack(x,y)Volume(p,v)Density(p,d)*(v,d,w)Weight(p,w)Isa(p,table)Weight(p,15)Weight(p1,w1)Weight(p2,w2)Smaller(w1,w2)Lighter(p1,p2)训练实例为描述物体Obj1与Obj2的下述事实：62Safe-To-Stack(Obj1,obj2)Lighter(Obj1,obj2)Weight(Obj1,0.1)Weight(Obj2,15)Smaller(0.1,15)Isa(Obj2,table)Voume(Obj1,1)Density(Obj1,0.1)*(1,0.1,0.1)图1 Safe-To-Stack(Obj1,obj2)解释结构 这是一个由目标概念引导的逆向推理，最终得到了一个解释结构。Safe-To-Stack(Obj1,obj2)Lighte632.获取一般性的知识 任务：对上一步得到的解释结构进行一般化的处理，从而得到关于目标概念的一般性知识。方法：将常量换成变量，并把某些不重要的信息去掉，只保留求解问题必须的关键信息。图2为图1的一般化解释结构，可以得到如下一般性知识：Volume(O1,v1)Density(O1,d1)*(v1,d1,w1)Isa(O2,table)Smaller(w1,15)Safe-To-Stack(Obj1,obj2)2.获取一般性的知识64Safe-To-Stack(O1,O2)Lighter(O1,O2)Weight(O1,w1)Weight(O2,15)Smaller(w1,15)Isa(O2,table)Voume(O1,v1)Density(O1,d1)*(v1,d1,w1)图2 Safe-To-Stack(O1,O2)一般化解释结构 以后求解类似问题时，就可以直接利用这个知识进行求解，提到了系统求解问题的效率。Safe-To-Stack(O1,O2)Lighter(O165领域知识的完善性领域知识的完善性l领域知识对证明的形成起着重要的作用，只有完善的领域知识才能产生正确的学习描述。但是，不完善是难以避免的，此时有可能出现如下两种极端情况：1.构造不出解释 2.构造出了多种解释l解决办法：1.最根本的办法是提供完善的领域知识2.学习系统也应具有测试和修正不完善知识的能力，使问题能尽早地被发现，尽快地被修正。领域知识的完善性领域知识对证明的形成起着重要的作用，只有完善66 7.7 神经学习神经学习l我们先简单回顾一下神经网络的基本原理。7.7 神经学习我们先简单回67人工神经元的基本构成人工神经元的基本构成InputsignalSynapticweightsSummingfunctionActivationfunctionLocalFieldvOutputox1x2xnw2wnw1w0 x0=+1 人工神经元模拟生物神经元的一阶特性人工神经元模拟生物神经元的一阶特性。l输入：输入：X=X=（x1x1，x2x2，xnxn）l联接权：联接权：W=W=（w1w1，w2w2，wnwn）T Tl网络输入：网络输入：net=xiwinet=xiwil向量形式：向量形式：net=XWnet=XWl激活函数：激活函数：f fl网络输出：网络输出：o=f o=f（netnet）人工神经元的基本构成InputSynapticSumming681一组突触和联结，联结具有权值 W1,W2,Wn2通过加法器功能，将计算输入的权值之和 net=xiwi3激励函数限制神经元输出的幅度o=f（net）一组突触和联结，联结具有权值 69典型激励函数典型激励函数netooc线性函数（线性函数（Liner Function）f（net）=k*net+c-net o 非线性斜面函数（非线性斜面函数（Ramp Function）a+b o(0,c)netac=a+b/2 S形函数（Sigmoid）典型激励函数netooc线性函数（Liner Functio70神经网络常见三大类模型神经网络常见三大类模型 神经网络中常见三大类模型：前向神经网络；反馈神经网络；自组织神经网络。l前向神经网络各神经元接受前一层的输入并输出给下一层，无反馈，常见的有BP神经网络和RBF径向基神经网络。l反馈神经网络，其输入数据决定反馈系统的初始状态，然后系统经过一系列的状态转移后逐渐收敛于平衡状态，即为反馈神经网络经过计算后的输出结果。神经网络常见三大类模型 神经网络中常见三大类模71自组织神经网络是一种无教师学习神经网络，可以模拟人类根据过去经验自动适应无法预测的环境变化，通常利用竞争原则进行学习，可以通过学习提取一组数据中的重要特征或某种内在规律性。对生物神经系统的观察可以发现局部相关作用可以导致整体的某种有序性，自组织神经网络。即基于这种原理。即基于这种原理。x1x2xny1y2ynx1x2xny1y2yn自组织神经网络是一种无教师学习神经网络，可以模拟人类根据过72x1x2xny1y2ynx1x2x3x4y1y2y3y4x1x2xny1y2yn前馈内层互联网络x1x2x3x73学习算法上的分类学习算法上的分类 在人工神经网络中，权是一个反映信息存储的关键量，在人工神经网络中，权是一个反映信息存储的关键量，在结构和转换函数定了以后，如何设计权使网络达到一定在结构和转换函数定了以后，如何设计权使网络达到一定的要求这是人工神经网络必不可少的部分，大多数神经网的要求这是人工神经网络必不可少的部分，大多数神经网络权的设计是通过学习得到的，目前可分为下列几种。络权的设计是通过学习得到的，目前可分为下列几种。死记式学习死记式学习 网络的权是事先设计的，值是固定的。网络的权是事先设计的，值是固定的。学习律学习律 这种方法是用已知例子作为教师对网络的权进行学习。这种方法是用已知例子作为教师对网络的权进行学习。设设 为已知的输入、输出例子，为已知的输入、输出例子，为为n n和和m m维矢量，维矢量，学习算法上的分类 在人工神经网络中，权是一个反映信息74，把，把 作为神经网络的输入，作为神经网络的输入，在权的作用下，可计算出实际神经网络的在权的作用下，可计算出实际神经网络的输出为输出为设任一个输入神经元设任一个输入神经元 q 到到 的权为的权为wqj则其权的改变量为则其权的改变量为其中其中 为步长，为步长，为误差，为误差，为第为第 q 个神经元的个神经元的输出，输出，函数是根据不同的情况而定，多数人工神经网络函数是根据不同的情况而定，多数人工神经网络；。，把 作为神经网络的输入，在权的作用下，可计算出实75自组织的学习和自组织的学习和Hebbian学习律学习律两个神经元之间的连接权，正比于两个神经元之间的连接权，正比于两个神经元的活动值，如两个神经元的活动值，如 ，表示两个神经元的输出值，则他们之间的权的变化为表示两个神经元的输出值，则他们之间的权的变化为这里这里 为步长或常数。为步长或常数。自组织的学习和Hebbian学习律两个神经元之间的连接权，76相近学习相近学习设设 为从神经元为从神经元i i到神经元到神经元j j的权，的权，为为i i 神经元的输出，则神经元的输出，则 在这个学习中，使在这个学习中，使 十分逼近十分逼近 的值。的值。如如KohonenKohonen和和ARTART等都采用这类学习方法。等都采用这类学习方法。相近学习设 为从神经元i到神经元j的权，为i 神经元的77非线性变换单元组成的前馈网络非线性变换单元组成的前馈网络 （简称（简称B-P网络）网络）网络的结构与数学描述网络的结构与数学描述1u0ikjlx0 x1xn-1y0y1ym-11/2X0X0非线性变换单元组成的前馈网络 网络的结构与数学描述图a:78B-P网络是完成网络是完成n维空间向量对维空间向量对m维空间的近似映照。维空间的近似映照。（F为近似映照函数）为近似映照函数）(1)(2)B-P网络是完成n维空间向量对m维空间的近似映照。(1)(279 如果输入第如果输入第P1个样本对个样本对通过一定方式训练后，得到一组权通过一定方式训练后，得到一组权包括网络中所有的权和阈值，此时包括网络中所有的权和阈值，此时的解不是唯一的，而是在权空间中的一个范围，也可为的解不是唯一的，而是在权空间中的一个范围，也可为几个范围。对于所有的学习样本几个范围。对于所有的学习样本P1=1,2,P都可以满足：都可以满足：各自的解为各自的解为W1，W2，WP，通过对样本集的学习，得到，通过对样本集的学习，得到满足所有样本正确映照的解为满足所有样本正确映照的解为 如果输入第P1个样本对通过一定方式训练后，得到一组权80学习的过程就是求解学习的过程就是求解W的过程，因为的过程，因为学习不一定要求很精确，所以得到的学习不一定要求很精确，所以得到的是一种近似解。是一种近似解。B-P的学习算法的学习算法去，令：去，令：；为了方便起见，在图为了方便起见，在图a的网络中，把阈值写入连接权中的网络中，把阈值写入连接权中；则方程（；则方程（2）改为）改为(2a)(2c)(2b)学习的过程就是求解W的过程，因为 B-P的学习算法去，令81B-P算法属于算法属于 学习律，是一种有教师的学习算法。学习律，是一种有教师的学习算法。第第P1样本输入到图样本输入到图a所示的网络，得到输出所示的网络，得到输出yl，l=0,1,m-1，其误差为各输出单元误，其误差为各输出单元误差之和，满足：差之和，满足：对于对于P个样本的学习，其总误差为个样本的学习，其总误差为(3)这里用梯度法可以使总的误差向减小的方向变化，这里用梯度法可以使总的误差向减小的方向变化，直到直到E总总=0为止，这种学习方式其矢量为止，这种学习方式其矢量W能够稳定能够稳定到一个解，但并不保证是到一个解，但并不保证是E总总的全局最小解，可能是的全局最小解，可能是一个局部极小解。一个局部极小解。B-P算法属于 学习律，是一种有教师的学习算法。对于P82具体学习算法的解析式推导如下：具体学习算法的解析式推导如下：令令n0为迭代次数，根据（为迭代次数，根据（3）式和）式和梯度算法，可得到每一层的权的梯度算法，可得到每一层的权的迭代公式为迭代公式为(4a)(4c)(4b)具体学习算法的解析式推导如下：令n0为迭代次数，根据（3）式83从(4a)式可以看出，是第k 个神经元与输出层第 l个神经元之间的连接权，它只与输出层中一个神经元有关，将(3)式代入(4a)中的第二项，利用公式(1)得：(5)这里这里从(4a)式可以看出，是第k 个神经元与输出层第 l个神84为为P1样本输入网络时，样本输入网络时，的输出值。的输出值。(6)将将(6)、(5)代入代入(4a)，得：，得：这里的这里的为P1样本输入网络时，的输出值。(6)将(6)85对于中间隐层，根据对于中间隐层，根据(4b)式有：式有：而而对于中间隐层，根据(4b)式有：而86其中：其中：所以所以是与输出层中每个神经元都有关系。是与输出层中每个神经元都有关系。其中：所以注意：是与输出层中每个神经元都有关系。87同理可得同理可得其中：其中：同理可得其中：88BP算法（反向传播算法）算法（反向传播算法）1985年，发展了BP网络学习算法，包括正向传播和反向传播，正向传播过程中，输入信息从输入层经隐单元逐层处理传向输出层，每层神经元状态仅影响下一层神经元的状态，如图：BP算法（反向传播算法）1985年，发展了BP网络学习算法89如在输出层得不到期望的输出，则转入反向传播，将误差信号沿原来的通路返回，修改各层神经元的权值使误差信号最小，如图：如在输出层得不到期望的输出，则转入反向传播，将误差信号沿原90反向传播学习示例反向传播学习示例 熟人学习问题熟人学习问题H1H2ARobertRaquelRomeoJoanJamesJuliet问题就是要修正网问题就是要修正网络的权值，从某个络的权值，从某个初试值集合开始，初试值集合开始，直到所有判断都是直到所有判断都是一致的一致的l假设正好有两个输入为1值，而其余输入为0值。H1和H2为隐节点，具有与门作用。该网络的目标是要确定对应于输入的两个人是否相识。该网络的任务为学习上面一组3人中的任何一人是下面一组3人中任何一人的熟人。如果网络的输出大于0.9，那么就判断这两个人为相识；如果输出小于0.1，就判断为不相识；其它结果被认为是模糊不定的。节点A为熟人。反向传播学习示例 熟人学习问题H1H2ARobertRaq91表1 BP网络学习经验数据表1 BP网络学习经验数据92表2 训练NN时观察到的权值变化第一个初始阈值为0.10.1，第二个为0.20.2，其他的每次递增0.10.1，直到1.11.1。通过BPBP算法改变初始值，直到所有输出均方误差在0.10.1内为止。当所有采样输人产生一个合适的输出值时的阈值和权值表2 训练NN时观察到的权值变化第一个初始阈值为0.1，第93图1 认识熟人问题的学习试验结果权值变化周期均方误差这个网络大约经过了这个网络大约经过了255255次权值修正后，网络次权值修正后，网络性能才变得满意，即均方误差性能才变得满意，即均方误差0.10.1。图1 认识熟人问题的学习试验结果权值变化周期均方误差这个网94图2 学习行为与比率参数的关系权值变化周期均方误差比率参数r r是用来调节权值变化调节权值变化的一个参数。r r值越大越有利于提高学习速度，但又不能太大，以免使输出过分地超出期望值而引起超调。图2 学习行为与比率参数的关系权值变化周期均方误差比率参数r95BP算法的不足：算法的不足：l收敛速度非常慢，且随着训练样例维数增加，网络性能变差。l不完备的算法，可能出现局部极小问题l网络中隐节点个数的选取尚无理论指导l新样例的加入会影响已学习过的样例BP算法的不足：收敛速度非常慢，且随着训练样例维数增加，网络96 基于基于Hopfield网络的学习网络的学习l1982年，JHopfield提出了可用作联想存储器的互连网络，这个网络称为Hopfield网络模型，也称Hopfield模型。1984年，他又提出连续时间神经网络模型。这两种模型的许多重要特性是密切相关的。一般在进行计算机仿真时采用离散模型，而在用硬件实现时则采用连续模型。基于Hopfield网络的学习1982年，JH97联想存储器联想存储器Associative Memory l Nature of associative memoryl part of information givenl the rest of the pattern is recalled 联想存储器Associative Memory Nat98联想存储器网络的几点要素lHopfield提出，如果把神经网络的各平衡点设想为存储于该网络的信息，而且网络的收敛性保证系统的动态特性随时间而达到稳定，那么这种网络称为联想存储器。l1.联想存储网络可以由一个状态向量 v=(v1,v2,vm)来表示2.网络有一组稳定的状态向量v1,v2,vn.3.网络总是从任意的初始状态v，随着能量函数E的减少吸引到某个稳定状态联想存储器网络的几点要素Hopfield提出，如果把神经网络99优化问题（能量函数优化问题（能量函数E）这表明若函数E是有界函数，Hopfield网络总是吸引到E函数的局部最小值上。通过适当地选取Wij的值和外部输入信号Ii，就可以将优化问题匹配到神经网络上。对E求微分（省略推导过程）得优化问题（能量函数E）这表明若函数E是有100优化问题（能量函数优化问题（能量函数E）l在实际应用中，任何一个系统，如果其优化问题可以用能量函数E(t)作为目标函数，那么，总可以用连续Hopfield网络对其进行求解。由于引入能量函数E(t)，Hopfield使神经网络和问题优化直接对应。利用神经网络进行优化计算，就是在神经网络这一动力系统给出初始的估计点，即初始条件；然后随网络的运动传递而找到相应极小点。这样，大量的优化问题都可以用连续的Hopfield网来求解。优化问题（能量函数E）在实际应用中，任何一个系统，如果其优101离散离散Hopfield神经网络神经网络l三个神经元组成的Hopfield网络离散Hopfield神经网络三个神经元组成的Hopfield102l霍普菲尔特提出的离散网络模型是一个离散时间系统，每个神经元只有两种状态，可用1和-1，或者1和0表示，由连接权值wij所构成的矩阵是一个零对角的对称矩阵，即霍普菲尔特提出的离散网络模型是一个离散时间系统，每个神经元只103l在该网络中，每当有信息进入输入层时，在输入层不做任何计算，直接将输入信息分布地传递给下一层各有关节点。若用Xj(t)表示节点j在时刻t的状态则该节点在下一时刻(即t+1)的状态由下式决定：这里 为从节点i到节点j的连接权值，为节点j的阈值在该网络中，每当有信息进入输入层时，在输入层不做任何计算，直104l整个网络的状态用X(t)表示，它是由各节点的状态所构成的向量。对于上图，若假设输出层只有两个节点，并用1和0分别表示每个节点的状态，则整个网络共有四种状态，分别为：00，01，10，11整个网络的状态用X(t)表示，它是由各节点的状态所构成的向量105110111001011100000010101三个神经元的八个状态 种状态，每个状态是一个三位的二进制数，如图所示。在该图中，立方体的每一个顶角代表一个网络状态。l如果假设输出层有三个节点，则整个网络共有八110111001011100000010101三个神经元的106l一般来说，如果在输出层有n个神经元，则网络就有2n个状态，它可以与一个n维超立体的顶角相联系。当有一个输入向量输入到网络后，网络的迭代过程就不断地从一个项角转向另一个顶角，直至稳定于一个顶角为止。如果网络的输入不完全或只有部分正确，则网络将稳定于所期望顶角附近的一个顶角那里。一般来说，如果在输出层有n个神经元，则网络就有2n个状态，它107Hopfield模型算法模型算法1.设置互连权值 其中，为s类样例的第i个分量，它可以为+1或-1(0)，样例类别数为m，节点数为nHopfield模型算法设置互连权值 其中，为s类样例1082.未知类别样本初始化 yi(0)=xi 0in-1 其中,yi（t）为节点i在t时刻的输出，当t0时，yi(0)就是节点i的初始值，xi为输入样本的第i个分量。3.迭代直到收敛 该过程将一直重复进行，直到进一步的迭代不再改变节点的输出为止。4.转2继续。2.未知类别样本初始化 该过程将一直重复进行，直到109Hopfield网络的不足网络的不足l很难精确分析网络的性能l其动力学行为比较简单Hopfield网络的不足很难精确分析网络的性能110 7.8 知识发现知识发现 产生的前提：从大量数据中找出隐藏在其中的、有用的信息和规律；计算机技术和信息技术的发展使其有能力处理这样大量的数据。7.8 知识发现 产生111成功例子成功例子l 零售业的沃尔马“啤酒与尿布”规律l Googlel 中国宝山钢铁公司1995年开始利用数据挖掘技术提高热轧产品质量、合理配矿l 中国铁道部1998年开始利用数据挖掘技术分析春运期间的铁路客流量，挖掘影响铁路客运总量的关键因素 成功例子 零售业的沃尔马“啤酒与尿布”规律112知识发现的发展过程知识发现的发展过程l八十年代人工智能（AI）研究项目失败后，转入实际应用时提出的。l 1989年国际上第一次关于数据挖掘与知识发现的研讨会在美国的底特律召开，在此次会议上第一次提出了知识发现（Knowledge Discovery in Database,KDD）一词。l 1995年，在加拿大召开了第一届KDD和DM国际学术会议。会议对KDD做了确切的定义。l 从九十年代中后期开始，KDD和DM已成为研究的热点和焦点。知识发现的发展过程八十年代人工智能（AI）研究项目失败后，113知识发现的定义知识发现的定义l 数据库中的知识发现是从大量数据中辨识出有效的、新颖的、潜在行用的、并可被理解的模式的高级处理过程。是有关事实的集合，是进一步发现知识的原材料经知识发现提取出的知识必须是新颖的，这可以通过两个途径来衡量：通过对当前得到的数据和以前的数据或期望得到的数据的比较来判断该模式的新颖程度二是通过其内部所包含的知识，对比发现的模式与已有的模式的关系来判断提取出的模式应该是有意义的，这可以通过某些函数的值来衡量知识发现的目的就是将数据库中隐含的模式以容易被人理解的形式表现出来，从而使人们更好地了解数据库中所包含的信息。如果一个表达式比列举数据集中的元素的描述方法更为简单时，才可称为模式。如“如果成绩在8190之问，则成绩优良”可称为个模式，而“如果成绩为8l，8283，84，85，8687，88，89或9D，则成绩优良”就不能称为个模式。知识发现的定义 数据库中的知识发现是从大量数据中辨识出有效的114知识发现处理过程知识发现处理过程 下面我们介绍两类较具代表性的处理过程模型l多处理阶段过程模型（1）多处理阶段模型将数据库中的知识发现看做是一个多阶段的处理过程，图1是费亚得Usama M.Fayyad等人给出的处理模型。知识发现处理过程 下面我们介绍两类较具代表性的处理115图1 费亚得的知识处理模型图1 费亚得的知识处理模型116l在图1处理模型中，KDD处理过程共分为九个处理阶段，这九个处理阶段分别是数据准备、数据选择、数据预处理、数据缩减、KDD目标确定、挖掘算法确定、数据挖掘、模式解释及知识评价。每个处理阶段KDD系统会提供处理工具完成相应的工作。在对挖掘的知识进行评测后，根据结果可以决定是否重新进行某些处理过程，在处理的任意阶段都可以返回以前的阶段进行再处理。在图1处理模型中，KDD处理过程共分为九个处理阶段，这九个处117l多处理阶段过程模型（2）l下面我们介绍的数据挖掘处理过程模型是George H.John 在他的博士论文中提出的，虽然在某些地方与费亚得给出的处理模型有一些区别，但这种区别主要表现在对整个处理过程的组织和表达方式上，在内容上两者并没有非常本质的区别。多处理阶段过程模型（2）118AnalyseResultsEngineeringCleanExtractDataalgorithmRun MiningDataDataEngineeringalgorithmDefine the problem图2 John的知识处理模型AnalyseResultsEngineeringClean119l以用户为中心的处理模型 Brachman&Anand从用户的角度对KDD处理过程进行了分析。他们认为数据库中的知识发现应该更着重于对用户进行知识发现的整个过程的支持，而不是仅仅限于在数据挖掘的一个阶段上。通过对很多KDD用户在实际工作中遇到的问题的了解，他们发现用户的很大一部分工作量是与数据库的交互上。所以他们在开发数据挖掘系统IMACS(Interactive Marketing Analysis and Classification System)时特别强调对用户与