人工智能通识基础与应用课件

人工智能通识基础与应用第2章机器学习目录2.1机器学习概述OverviewofMachineLearning.2.2归纳学习InductiveLearning.2.3类比学习analogicallearning.2.1机器学习概述OverviewofMachineLearning.2.1.1简单的学习模型

学习是一个有特定目的的知识获取过程，可以在这个过程中通过获取知识、积累经验、发现规律，使系统性能得到改进，实现系统的自我完善和环境的自适应。下图给出了简单的学习模型。2.1.2什么是机器学习

机器学习是研究机器模拟人类的学习活动，获取知识和技能的理论和方法，从不同程度上改善系统性能的学科。机器学习的任务目标、方法和策略，主要是从学习算法，和机器学习程序方面来体现的。学习算法机器学习程序机器学习的任务目标、方法和策略2.1.2什么是机器学习总的来说机器学习研究的目标有三个，即人类学习过程的认知模型、通用学习算法以及面向任务的专用学习系统。（1）人类学习过程的认知模型。研究人类学习机理的认知模型，这种研究对人类的教育，对开发机器学习系统都有重要的意义。（2）通用学习算法。基于对人类学习过程的研究，探索不同的学习方法，有助于建立不依赖于特定应用领域的通用学习算法。（3）面向任务的专用学习系统。这一目标聚焦于解决具体的实际问题，即开发专门针对某些任务的学习系统。2.1.3机器学习知识点梳理机器学习基本概念假设空间损失函数所谓假设空间，就是在机器学习中函数构成的空间。由输入空间到输出空间的映射集合是假设空间，模型就属于该集合。损失函数用于量化模型预测值与真实值的差异，其值为非负实数值。在实际应用中，损失函数连接了学习准则与优化问题，通过最小化损失函数可求解并评估模型性能。2.1.4机器学习的研究概况机器学习的热烈时期，主要研究“有无知识的学习”。这类方法主要是研究系统的执行能力。这个阶段最具有代表性的研究是塞缪尔的下棋程序，但这种机器学习的方法还远远不能满足人们的需要.机器学习的冷静时期，主要研究将各个领域的知识植入系统里。本阶段的研究目的是通过机器模拟人类学习的过程，同时还采用了图结构及其逻辑结构方面的知识进行系统化的描述。机器学习的复兴时期。人们开始把学习单个概念扩展到学习多个概念，探索不同的学习策略和学习方法，而且还开始把学习系统与各种应用结合起来。取得了很大的成功。多浅层机器学习模型相继问世，诸如逻辑回归，支持向量机等，这些机器学习算法的共性是数学模型为凸代价函数的最优化问题，理论分析相对简单，容易从训练样本中学习到内在模式，来完对象识别，人物分配等初级智能工作。20世纪50年代中叶至60年代中叶20世纪60年代中叶至70年代中叶20世纪70年代中叶至80年代中叶20世纪80年代中叶至90年代中叶20世纪90年代中叶到现在机器学习领域飞速发展，机器学习热潮到来。2006年，机器学习领域泰斗GeoffreyHintonRuslanSalakhutdinov发表文章，提出了深度学习模型。2012年，Hinton研究团队采用深度学习模型赢得了计算机视觉领域最具有影响力的ImageNet比赛冠军，标志着深度学习进入第二阶段。2.2归纳学习InductiveLearning.2.2.1归纳学习的基本概念基本概念：归纳学习是从大量的经验数据中归纳抽取出一般的判定规则和模式，也就是从特殊情况推导出一般规则的学习方法。归纳学习的目标是形成合理的、能解释已知事实和预见新事实的一般性结论。归纳学习由于依赖于经验数据，因此又称为经验学习。由于归纳依赖于数据间的相似性，所以归纳学习也被称为基于相似性的学习。2.2.1归纳学习的基本概念在机器学习领域，一般将归纳学习问题描述为使用训练实例引导一般规则的搜索问题。全体可能的实例构成实例空间；全体可能的一般规则构成规则空间。在规则空间中搜索要求的规则，从实例空间中选出一些示教的例子，来解决规则空间中某些规则的二义性问题，这就是基于规则空间和实例空间的学习。2.2.1归纳学习的基本概念归纳学习方法可以划分为单概念学习和多概念学习两类。概念是指用某种描述语言表示的谓词，当描述语言应用于概念的正实例时，谓词为真；应用于概念的负实例时，则为假。从而概念谓词将实例空间划分为正、反两个子集。单概念学习的目的：从概念空间(即规则空间)中寻找某个与实例空间一致的概念。多概念学习的目的：从概念空间中找出若干概念进行描述，对于每一个概念描述，实例空间中均有相应的空间与之对应。2.2.2变型空间方法变型空间(LearningbyVersionSpace)方法是米切尔(TMitchell)于20世纪80年代早期提出的一种基于数据驱动的学习方法。例如，TRUE表示没有任何条件，是最一般的概念，∃xCLUBS(x)是比TRUE特殊的概念，∃x∃y(CLUBS(x)∧HE-ARTS(y))是比上述两个概念更特殊的概念，上述这些概念形成了一种偏序的关系。偏序集的最大元素称为零描，它表示只要规则空间中存在真正的概念描述，则零描述为真，相当于在规则空间中恒真的概念描述。偏序集中的极小元素为所有训练实例。概念：2.2.2变型空间方法

变型空间方法包含整个概念的规则空间，可以将初始的假设规则看成集合H，它是与迄今为止所得到的所有训练实例相一致的概念的集合。根据示教例子中的信息，对H进行泛化和特化处理，逐步缩小集合H，最后使H收敛为只含有要求的规则。H由两个子集G和S所限定，G中的元素表示H中最一般的概念，S中的元素表示H中最特殊的概念。H还可以看作是由G、S及G与S之间的元素构成的，即：H＝G∪S∪{k|S＜k＜G}其中，“＜”表示变型空间中的偏序关系。下图给出了一个变型空间排序关系的表示。2.2.2变型空间方法

变型空间方法的初始集G是空间中最上面的一个点(最一般的概念)，初始集S是最下面直线上的点(示教例子)，初始集H就是整个空间。在搜索过程中，G集不断缩小，逐渐下移(进行特殊化)，S集合不断扩大，逐渐上移(进行一般化)。H集逐步缩小，最后H收敛为只含有一个概念时，就发现了所要学习的概念。在变型空间中这种学习算法称为候选项删除算法。候选项删除算法的一般流程如下：（1）初始化H集为整个概念空间。G集合只包含零描述，S集合包含空间中所有最特殊的概念。在实际处理中，S集初始化为第一个正例。（2）接受一个新的训练实例。如果实例为正例，则从G集中删除所有不覆盖该例的概念，更新S集合，尽可能小地对S集进行泛化，以覆盖新的正实例。（3）如果实例为反例，则从S集中删除所有覆盖这个反例的概念，更新G集，尽可能小地特化G集中的元素，以便它们不覆盖这个反例。(４)如果G≠S，则重复步骤(２)，否则输出H集。2.2.3决策树方法1966年，亨特(E.B.Hunt)等提出了概念学习系统(ConceptLearningSystem，CLS)，这是一种早期的基于决策树的归纳学习系统。1979年，基于CLS系统，昆兰等提出了ID3算法。该算法不仅能方便地表示属性值的信息结构，而且能从大量实例数据中有效地生成相应的决策树模型。

1、决策树及其构造方法：在CLS的决策树中，节点对应于待分类对象的属性，由某一节点引出的弧对应于这一属性可能取的值，叶节点对应于分类的结果。下面介绍如何生成决策树。2.2.3决策树方法一般地，设给定训练集为TR，TR的元素由特征向量及其分类结果表示，分类对象的属性表AttrList为{A１，A２，···，An}，全部分类结果构成的集合Class为{C1，C2，···，Cm}，n≥１，m≥２。对于每一个属性Ai，其值域都为ValueType(Ai)。值域可以是离散的，也可以是连续的。这样，TR的一个元素就可以表示成＜X，C＞的形式，其中X＝(a1，a2，···，an)，其中，ai对应于实例中第i个属性的取值，C∈Class为实例X的分类结果。构造决策树的CLS算法可简单地描述如下：

一棵决策树包含一个根节点、若干个内部节点和若干个叶节点。叶节点对应于决策结果；其他每个节点则对应于一个属性测试;每个节点包含的样本集合根据属性测试的结果被划分到子节点;根节点包含样本全集。从根节点到每个叶节点的路径对应了一个判断测试的序列。从一棵空树出发，不断地从决策表选取属性加入树的生长过程，直到决策树可以满足分类要求为止。其中每一条从根节点(对最终分类结果贡献最大的属性)到叶节点(最终分类结果)的路径都代表一条决策的规则。CLS算法存在的主要问题是，在新增属性选取时有很大的随机性。决策树的结构如下图：2.2.3决策树方法决策树的生成是一个递归的过程，有以下三种情形不会再分类。当前节点包含的样本全属于同一类别。当前属性集为空。当前节点的样本集合为空。2.2.3决策树方法大多数决策树算法是一种核心算法的变体。决策树核心算法采用自顶向下的贪婪搜索策略去遍历可能的决策树空间，这种算法是ID3算法和后继的CA.5算法的基础。ID3算法：ID3算法是基本的决策树算法，它通过自顶向下构造决策树来进行学习。构造过程是从“哪一个属性将在树的根节点被测试?”这个问题开始的。它是一种基于信息熵的决策树分类学习算法，以信息增益和信息熵作为对象分类的衡量标准，是一种自顶向下增长树的贪婪算法，在每个节点选取能最好地分类样例的属性，继续这个过程直到这棵树能完美分类训练样例或所有的属性都已被使用过。它也可以说是CLS算法的最大改进算法，该算法不仅摒弃了属性选择的随机性，还利用信息熵的下降速度作为属性选择的度量。2、基本的决策树算法2.2.3决策树方法CA.5算法是基于ID3算法的改进，其中改进的内容主要包括：使用信息增益率替换信息增益下降度作为属性选择的标准；在决策树构造的同时进行剪枝操作，避免出现树的过度拟合情况；可以对不完整属性和连续型数据进行处理，提升了算法的普适性。ID3与CA.5比较：

优点：结构简单、学习能力强、分类速度快，而且还适合大规模数据分类。

缺点：（1）决策树的知识表示没有规则，难以理解。（2）不能处理未知属性值的情况，另外对噪声问题也没有好的处理办法。（3）倾向于选择那些取值比较多的属性，而在实际的应用过程中往往取值比较多的属性对分类没有太大的价值，因为它不能对连续属性进行处理，对噪声数据比较敏感，而且还要计算每一个属性的信息增益值，计算代价较高。2.3类比学习analogicallearning.类比学习概念：类比学习是根据两个对象之间在某些方面的相同性或相似性，推出它们在其他方面也可能相同或相似的学习方法。归纳学习需要大量的训练实例，而类比学习从单个训练实例就可以完成学习，所以它是一种有效的学习方法。2.3.1相似性类比学习通过比较两个事物或情境，在某一抽象层面上找到它们的相似关系，并基于这种相似性，将一个事物或情境的相关知识经过适当整理或变换后应用到另一个事物或情境上，从而获得对后者的新理解。在类比学习中，一般把当前所面临的对象或情形称为目标对象(TargetObject)，把记忆的对象或情形称为源对象(BaseObject)。若在类比学习中遇到某一问题时，可以先回忆以前提出的相似性问题，通过对该问题解法的检索、分析和调整，得出新问题的解决方法。类比学习是一种基于知识或经验的学习。2.3.1相似性对类比问题的求解可以描述为：已知问题A，求解结果B，现给定一个新问题A′，A′与A在特定的度量下是相似的，可以通过求解结果B来求出问题A′的求解结果B′。具体流程如图，β反映B与A之间的依赖关系，称为因果关系。α表示源领域(SourceDomain)A与目标领域(TargetDomain)A′之间的相似关系，由此可以推出，B′与A′之间的依赖关系β′。2.3.1相似性类比学习的过程：（1）联想搜索匹配。对于一个给定的新问题，根据问题的描述(已知条件)提取问题的特征，并用特征到问题空间中搜索，找出相似的老问题有关的知识，并对新、老问题进行部分匹配。（2）检验相似程度。判断老问题的已知条件与新问题的相似程度，以检验类比的可行性。如果它们之间的相似度达到规定的阈值，则类比匹配成功。（3）修正变换求解。从老问题的解中抽取有关新问题的知识，经过合理的规则变换与调整，得到新问题的解。当多个老问题经检查都满足时，还会产生冲突求解的问题。（4）更新知识库。将新问题和求解加入知识库，将新、老问题之间的共同特征组成泛化的情节知识，而将它们的差异作为检索问题的索引。2.3.2转换类比类比学习的一般问题求解程序是基于“手段-目的”分析(Means-EndsAnalysis，MEA)方法。问题求解模型由两部分组成：问题空间和问题求解动作。问题空间包括：其一，是一组由可能的问题组合所构成的状态集；其二，包含一个初始状态，同时设有两个或更多的目标状态（为了简便起见，这里暂且假定只有一个目标状态）；其三，配备了一组变换规则集（也可称作操作符），只要满足预置条件，就能依靠这些规则集将一个状态转变为另一个状态；其四，有着用于计算两个状态之间差别的函数，该函数一般是在比较当前状态和目标状态时发挥作用，进而得出二者之间的差别；其五，具备一个索引函数，其功能在于对可用的变换规则进行编序，以此来最大程度地减少差别；其六，包含一组全局路径限制，目标路径必须符合这些条件才能得到有效解，而且路径限制从本质上来说，是以部分解序列作为基础的，并非基于单个的状态或者操作符；其七，还有一个差别表，其用途是指示在何种情况下可以使用何种变换规则。2.3.2转换类比在问题空间上使用S-MEA算法进行问题求解操作，S-MEA算法的基本步骤如下：（1）比较当前状态和目标状态，得出差别。（2）选择合适的规则(或算子)，以减少两个状态之间的差别。（3）尽可能应用转换规则，直至完成状态转换。否则保存当前状态，并将S-MEA算法递归地用于其他子问题，直到该子问题确认不能满足该规则的前提条件为止。（4）当子问题求解后，恢复被保存的当前状态，再继续求解原来的问题。2.3.3基于案例的推理在基于案例的推理(Case-BasedReasoning)中，最初是由于目标案例的某些特殊性质使得记忆中的源案例能够被联想到，但它是粗糙的，不一定正确。在初次检索完成之后，要去验证它们之间的可类比性，而这会促使对两个类似体的更多细节展开进一步检索，以探寻它们之间更深层次的可类比性以及存在的差异。右图给出了基于案例推理的一般框架。2.3.3基于案例的推理在基于案例的推理中，主要关心的问题有以下几个方面。（1）案例表示。基于案例推理方法的效率和案例表示紧密相关。案例表示所涉及的几个问题为:选择什么信息存放在一个案例中;如何选择合适的案例内容描述结构;案例库如何组织和索。其中，对于那些数量达到成千上万且十分复杂的案例，组织和索引问题尤为重要。（2）分析模型。分析模型用于分析目标案例，从中识别和抽取检索源案例库的信息。（3）案例检索。利用信息的检索从源案例库中检索并选择潜在可用的源案例。基于案例推理的方法和人类解决问题的方式很近似。一般在遇到一个新问题时，首先从记忆或案例库中回忆出与当前问题相关的最佳案例，后面所有的工作能否发挥出应有的作用，很大程度上依赖于这一阶段得到的案例质量的高低，因此这一步非常关键。事实上，案例匹配不是精确的，只能是部分匹配或近似匹配，所以这就要求有一个相似度的评价标准。若该标准定义得好，会使得检索出的案例十分有用，否则将会严重影响后面的过程。（4）类比映射。寻找目标案例与源案例之间的对应关系。2.3.3基于案例的推理（5）类比转换。转换源案例中与目标案例相关的信息，使之在目标案例的求解过程中发挥作用。涉及对源案例的求解方案的修改就是把检索到的源案例的解答用于新问题或新案例中。解答的问题一般是：源案例与目标案例之间有何不同之处;源案例中的哪些部分可以用于目标案例。对于简单的分类问题，仅需要把源案例的分类结果直接用于目标案例，无须考虑它们之间的差别，因为实际案例检索已经完成了这项工作。对于求解之类的问题，则需要根据它们之间的不同，对再次使用的解进行调整。（6）解释过程。当转换过的源案例的求解方案应用到目标案例时，对出现的失败做出解释，给出失败的因果分析报告。有时候也需要对成功做出解释。基于解释的索引是一种重要的方法。（7）案例修补。有些案例修补类似于类比转换，它们之间的区别在于修补过程的输入是解决方案和一个失败的报告，可能还包含一个解释。当复用阶段产生的求解结果不理想时，需要对其进行修补。修补的第一步是对复用的求解结果进行评估，如果成功，则不必修补，否则需要对错误采取修补措施。2.3.3基于案例的推理（8）类比验证。验证目标案例和源案例进行类比的有效性。（9）案例保存。新问题得到了解决，就形成了一个可能用于将来情形与之相似的问题，这时有必要把新问题加入案例库中。案例保存既是学习的过程，也是知识获取的过程。在决定选取案例的哪些信息进行保留时，一般要考虑以下三点：和问题有关的特征描述;问题的求解结果;解答成功或失败的原因及解释。把新案例加入案例库中，需要对它建立有效的索引，使其能被有效地回忆。索引应在与该案例有关时能回忆得出，与该案例无关时不应回忆得出。为此，可能要对案例库的索引内容甚至结构进行调整。2.3.4迁移学习迁移学习（TransferLearning）旨在借助在一个环境里所学到的知识，助力新环境中的学习任务。在传统的分类学习当中，为确保经过训练所得到的分类模型具备准确性以及高可靠性，通常会设立两个基本假设：其一，用于学习的训练样本与新的测试样本要满足独立同分布这一条件；其二，必须要有数量足够且可供利用的训练样本，这样才能通过学习得到一个良好的分类模型。不过，在实际应用过程中可以发现，要想满足这两个条件常常是比较困难的。而迁移学习则是利用已有的知识，针对不同却又相互关联的领域问题展开求解，它对传统机器学习中的那两个基本假设进行了放宽处理，其目的在于迁移已有的知识，以此来解决目标领域中仅有少量标签样本数据的问题。2.3.4迁移学习根据源领域与目标领域、源任务与目标任务是否相同等问题，可以将迁移学