机器学习算法汇总大全PPT学习课件.ppt

2016.112016.11机器学习机器学习(Machine Learning)报告建议内容报告建议内容q基本概念以及数学定义基本概念以及数学定义q基本性质及其物理意义基本性质及其物理意义q具体算法应用（详细举例讲解）具体算法应用（详细举例讲解）q该算法与其他类似算法的分析比较该算法与其他类似算法的分析比较q可能的发展方向可能的发展方向q附参考文献附参考文献2机器学习机器学习机器学习机器学习，TomM.MitchellTomM.Mitchell（汤姆（汤姆（汤姆（汤姆 米米米米切尔）著，曾华军，张银华等译，机械工切尔）著，曾华军，张银华等译，机械工切尔）著，曾华军，张银华等译，机械工切尔）著，曾华军，张银华等译，机械工业出版社，业出版社，业出版社，业出版社，20032003年年年年 。参考书参考书其它参考书其它参考书qq机器学习及其应用机器学习及其应用机器学习及其应用机器学习及其应用，周志华，王钰主编，清，周志华，王钰主编，清，周志华，王钰主编，清，周志华，王钰主编，清华大学出版社，华大学出版社，华大学出版社，华大学出版社，20092009。qq神经网络与机器学习神经网络与机器学习神经网络与机器学习神经网络与机器学习，SimonHaykinSimonHaykin著，著，著，著，机械工业出版社，机械工业出版社，机械工业出版社，机械工业出版社，20102010。qq机器学习导论机器学习导论机器学习导论机器学习导论，EthemAlpaydinEthemAlpaydin著，机械著，机械著，机械著，机械工业出版社，工业出版社，工业出版社，工业出版社，20092009。qqMachineLearningMachineLearning AProbabilisticPerspectiveAProbabilisticPerspectiveKevinP.KevinP.Murphy,2012Murphy,2012第第1章章 引引 言言什么是机器学习什么是机器学习 【经典定义经典定义】：计算机程序如何随着经验积：计算机程序如何随着经验积累自动提高性能，系统自我改进的过程。累自动提高性能，系统自我改进的过程。或：计算机利用经验改善系统自身性能的或：计算机利用经验改善系统自身性能的行为。行为。米切尔米切尔随着该领域的发展，主要做随着该领域的发展，主要做智能数据分析智能数据分析智能数据分析智能数据分析。学习与智能学习与智能学习现象学习现象语言、文字的认知识别语言、文字的认知识别图像、场景、自然物体的认知识别图像、场景、自然物体的认知识别规则规则（eg下雨天要带雨伞）下雨天要带雨伞）复杂的推理、判断能力（智能）复杂的推理、判断能力（智能）好人与坏人？好人与坏人？好猫与坏猫？好猫与坏猫？数据数据知识知识认知认知推理推理决策决策识别识别学习学习什么是机器学习？什么是机器学习？使得计算机具备和人类一样的学习能力使得计算机具备和人类一样的学习能力决策决策推理推理认知认知识别识别等智能等智能给定数据（样本、实例）和一定的学习规则，给定数据（样本、实例）和一定的学习规则，从数据中获取知识的能力从数据中获取知识的能力机器学习与人工智能机器学习与人工智能q自然智慧的伟大与奥妙自然智慧的伟大与奥妙举例：婴儿的认知能力（声音、人脸、汽车举例：婴儿的认知能力（声音、人脸、汽车）重要的二个特点重要的二个特点：容错性，推广能力（举一反三）容错性，推广能力（举一反三）q机器智能：希望用机器实现部分智能机器智能：希望用机器实现部分智能q基于数据的机器学习问题（引自清华张学工教基于数据的机器学习问题（引自清华张学工教授）授）根据已知样本估计数据之间的依赖关系，从而对未根据已知样本估计数据之间的依赖关系，从而对未知或无法测量的数据进行预测和判断知或无法测量的数据进行预测和判断关键：推广能力关键：推广能力什么是机器学习什么是机器学习q中科院王珏研究员给出的定义：中科院王珏研究员给出的定义：令令W是给定世界的有限或无限所有观测对象的集是给定世界的有限或无限所有观测对象的集合，由于我们的观测能力有限，我们只能获得这合，由于我们的观测能力有限，我们只能获得这个世界的一个子集个世界的一个子集，称为样本集。机器学，称为样本集。机器学习就是根据这个样本集，推算这个世界习就是根据这个样本集，推算这个世界W的模型，的模型，使它对这个世界（尽可能地）为真。使它对这个世界（尽可能地）为真。q三个重要的理论问题：三个重要的理论问题：一致：一致：W与与Q有相同的性质。有相同的性质。eg.i.i.d划分：设样本定义于划分：设样本定义于d维空间，要寻找在这个空间维空间，要寻找在这个空间上的决策分界面上的决策分界面泛化（推广能力）：对未知样本的判断能力泛化（推广能力）：对未知样本的判断能力WhatWhats is the Learning Problem?s is the Learning Problem?qLearning=ImprovingwithexperienceatsometaskImproveovertaskTWithrespecttoperformancemeasurementPBasedonexperienceEqExample:中国象棋中国象棋任务任务T：下中国象棋：下中国象棋性能目标性能目标P：比赛中击败对手（的百分比）：比赛中击败对手（的百分比）训练经验训练经验E：和自己进行对弈，或者看棋谱：和自己进行对弈，或者看棋谱Ref：机器学习机器学习（曾华军等译）（曾华军等译）PedroPedro对学习理解对学习理解Machine LearningMachine Learning引用自引用自CMUDr.EricXing的的LectureNotes机器学习的重要性！机器学习的重要性！qScience2001年论文：年论文：每个科学领域的科学过程都有它自己的特点，但是，每个科学领域的科学过程都有它自己的特点，但是，观观观观察、创立假设、根据决定性实验或观察的检验、可理解检察、创立假设、根据决定性实验或观察的检验、可理解检察、创立假设、根据决定性实验或观察的检验、可理解检察、创立假设、根据决定性实验或观察的检验、可理解检验的模型或理论，是各个学科所共有的验的模型或理论，是各个学科所共有的验的模型或理论，是各个学科所共有的验的模型或理论，是各个学科所共有的。对这个抽象的科。对这个抽象的科学过程的每一个环节，机器学习都有相应的发展，我们相学过程的每一个环节，机器学习都有相应的发展，我们相信它将导致科学方法中从假设生成、模型构造到决定性实信它将导致科学方法中从假设生成、模型构造到决定性实验这些所有环节的合适的、部分的自动化。当前机器学习验这些所有环节的合适的、部分的自动化。当前机器学习研究在一些基本论题上取得令人印象深刻的进展，我们预研究在一些基本论题上取得令人印象深刻的进展，我们预期机器学习研究在今后若干年中将有稳定的进展！期机器学习研究在今后若干年中将有稳定的进展！”在稍早前，在稍早前，2000年年Science还发表了另外还发表了另外3篇篇ML方面方面的论文的论文“TheManifoldWayofPerceptron”,“Aglobalgeometricframeworkfornonlineardimensionalityreduction”,”Nonlineardimensionalityreductionbylocally”Mjolsness,D DeCoste,Machine Learning for Science:State of the Art and Future Prospects-Science,2001:2051-2055.受到令人惊讶受到令人惊讶的重视！的重视！机器学习的重要性机器学习的重要性摘自南京大学周志华教授摘自南京大学周志华教授生物信息学计算金融学分子生物学行星地质学工业过程控制机器人遥感信息处理信息安全机 器 学 习多学科交叉多学科交叉qq机器学习机器学习机器学习机器学习也是一个多学科交叉的产物，它吸取了也是一个多学科交叉的产物，它吸取了也是一个多学科交叉的产物，它吸取了也是一个多学科交叉的产物，它吸取了人工智能、概率统计、神经生物学、认知科学、人工智能、概率统计、神经生物学、认知科学、人工智能、概率统计、神经生物学、认知科学、人工智能、概率统计、神经生物学、认知科学、信息论、控制论、计算复杂性理论、哲学等学科信息论、控制论、计算复杂性理论、哲学等学科信息论、控制论、计算复杂性理论、哲学等学科信息论、控制论、计算复杂性理论、哲学等学科的成果。的成果。的成果。的成果。qq实践证明，实践证明，实践证明，实践证明，机器学习机器学习机器学习机器学习在很多应用领域发挥了重要在很多应用领域发挥了重要在很多应用领域发挥了重要在很多应用领域发挥了重要的实用价值，特别是在数据挖掘、语音识别、图的实用价值，特别是在数据挖掘、语音识别、图的实用价值，特别是在数据挖掘、语音识别、图的实用价值，特别是在数据挖掘、语音识别、图像处理、机器人、车辆自动驾驶、生物信息学、像处理、机器人、车辆自动驾驶、生物信息学、像处理、机器人、车辆自动驾驶、生物信息学、像处理、机器人、车辆自动驾驶、生物信息学、信息安全、遥感信息处理、计算金融学、工业过信息安全、遥感信息处理、计算金融学、工业过信息安全、遥感信息处理、计算金融学、工业过信息安全、遥感信息处理、计算金融学、工业过程控制。程控制。程控制。程控制。重要性：例子网络安全入侵检测：是否是入侵？是何种入侵？如何检测？历史数据：以往的正常访问模式及其表现、以往的入侵模式及其表现对当前访问模式分类这是一个典型的预测型机器学习问题常用技术：神经网络 决策树支持向量机 k近邻序列分析 聚类 搜索引擎搜索引擎摘自南京大学周志华教授摘自南京大学周志华教授重要性：例子生物信息学常用技术：神经网络 支持向量机隐马尔可夫模型k近邻 决策树序列分析 聚类 重要性：例子数据驱动控制相关学科对相关学科对MLML的影响的影响q人工智能：人工智能：学习的概念符号表示学习的概念符号表示qBayes方法方法q统计学：统计学：统计学习理论统计学习理论(SLT)q计算复杂性理论计算复杂性理论q控制论控制论q信息论：最小描述长度信息论：最小描述长度q哲学：哲学：“OccamsRazor原则原则”，“没有免费午餐没有免费午餐”q心理学和神经生物学：心理学和神经生物学：NeuralNetworks（神经网络）（神经网络）机器学习目前主要的一些研究领域机器学习目前主要的一些研究领域q符号机器学习符号机器学习Eg.决策树，决策树，ID3，q计算学习理论（统计学习理论）计算学习理论（统计学习理论）PAC，SVMq监督学习，非监督学习，半监督学习监督学习，非监督学习，半监督学习q集群机器学习集群机器学习EnsembleLearning，Boostingq流行（流行（Manifold）学习）学习q强化学习强化学习qRanking学习学习q聚类学习聚类学习MLML的发展历史的发展历史(1)(1)q1950s：神经科学的理论基础：神经科学的理论基础James关于神经元是相互连接的发现关于神经元是相互连接的发现McCullon&Pitts的神经元模型的神经元模型Hebb学习律（相互连接强弱度的变换规则）学习律（相互连接强弱度的变换规则）q1960s：感知器（：感知器（Perceptron）时代）时代1957年年Rosenblatt首次提出首次提出MLML的发展历史的发展历史(2)(2)q1969年：年：Perceptron出版，提出著名出版，提出著名的的XOR问题问题q1970s：符号主义，逻辑推理：符号主义，逻辑推理q1980s：MLP+BP算法成功解决算法成功解决XOR问题，问题，从此进入神经网络时代（连接主义）从此进入神经网络时代（连接主义）q1960s-1970s:统计学习理论创立统计学习理论创立VC维的基本概念维的基本概念结构风险最小化原则结构风险最小化原则概率空间的大数定律概率空间的大数定律MLML的发展历史的发展历史(3)(3)q1990s：统计学习理论的发展及完善：统计学习理论的发展及完善典型代表：典型代表：SVM（Vapnik，Bell实验室）实验室）结构风险最小化结构风险最小化最小描述长度原则最小描述长度原则小样本问题小样本问题核函数、核空间变化核函数、核空间变化PAC理论下的弱可学习理论的建立理论下的弱可学习理论的建立支持向量机支持向量机MLML的发展历史的发展历史(4)(4)q2000s：各种机器学习理论及算法得以充分发展：各种机器学习理论及算法得以充分发展符号机器学习符号机器学习计算机器学习（统计学习理论，典型例子：计算机器学习（统计学习理论，典型例子：SVM）集群机器学习（典型代表：集群机器学习（典型代表：Boosting）强化机器学习强化机器学习流行机器学习流行机器学习监督学习，非监督学习监督学习，非监督学习半监督学习、半监督学习、.未来发展趋势未来发展趋势q机器实际上是一个应用驱动的学科，其根本的驱动力机器实际上是一个应用驱动的学科，其根本的驱动力是：是：“更多、更好地解决实际问题更多、更好地解决实际问题”q由于近由于近20年的飞速发展，机器学习已经具备了一定的年的飞速发展，机器学习已经具备了一定的解决实际问题的能力，似乎逐渐开始成为一种基础性、解决实际问题的能力，似乎逐渐开始成为一种基础性、透明化的透明化的“支持技术、服务技术支持技术、服务技术”基础性：在众多的学科领域都得以应用（基础性：在众多的学科领域都得以应用（“无所不在无所不在”）透明化：用户看不见机器学习，看见的是防火墙、生物信透明化：用户看不见机器学习，看见的是防火墙、生物信息、搜索引擎；（息、搜索引擎；（“无所不在无所不在”）“机器更好用了机器更好用了”(正如正如CALO的一些描述：的一些描述：“youwontleavehomewithoutit”；”embodiedasasoftwareenvironmentthattranscendsworkstations,PDAs,cellphones,”)讨论议题讨论议题q机器学习的主要策略与基本结构机器学习的主要策略与基本结构机器学习的主要策略机器学习的主要策略机器学习系统的基本结构机器学习系统的基本结构机器学习系统的基本结构机器学习系统的基本结构 q我们以西蒙的学习定义做为出发点，建立起下图我们以西蒙的学习定义做为出发点，建立起下图1.1所示的简单的学习模型，然后通过对这个简单所示的简单的学习模型，然后通过对这个简单模型的讨论，总结出设计学习系统应当注意的某模型的讨论，总结出设计学习系统应当注意的某些总的原则。些总的原则。图图图图 1.1 1.1 学习系统的基本结构学习系统的基本结构学习系统的基本结构学习系统的基本结构 学习问题的标准描述学习问题的标准描述qq定义定义如果一个计算机针对某类任务如果一个计算机针对某类任务如果一个计算机针对某类任务如果一个计算机针对某类任务T T，用，用，用，用P P来衡量性能，来衡量性能，来衡量性能，来衡量性能，根据经验根据经验根据经验根据经验E E来自我完善，那么我们称这个计算机程来自我完善，那么我们称这个计算机程来自我完善，那么我们称这个计算机程来自我完善，那么我们称这个计算机程序在从经验序在从经验序在从经验序在从经验E E中学习，针对某类任务中学习，针对某类任务中学习，针对某类任务中学习，针对某类任务T T，它的性能用，它的性能用，它的性能用，它的性能用P P来衡量。来衡量。来衡量。来衡量。qq西洋跳棋学习问题的解释西洋跳棋学习问题的解释E E，和自己下棋，和自己下棋，和自己下棋，和自己下棋T T，参与比赛，参与比赛，参与比赛，参与比赛P P，比赛成绩（或赢棋能力，击败对手的百分比），比赛成绩（或赢棋能力，击败对手的百分比），比赛成绩（或赢棋能力，击败对手的百分比），比赛成绩（或赢棋能力，击败对手的百分比）qq手写识别学习问题手写识别学习问题qq机器人驾驶学习问题机器人驾驶学习问题学习问题的标准描述（学习问题的标准描述（2 2）qq定义太宽泛定义太宽泛甚至包括了以非常直接的方式通过经验自我甚至包括了以非常直接的方式通过经验自我甚至包括了以非常直接的方式通过经验自我甚至包括了以非常直接的方式通过经验自我提高的计算机程序提高的计算机程序提高的计算机程序提高的计算机程序qq实际的机器学习问题往往比较复杂实际的机器学习问题往往比较复杂定义一类问题定义一类问题定义一类问题定义一类问题探索解决这类问题的方法探索解决这类问题的方法探索解决这类问题的方法探索解决这类问题的方法理解学习问题的基本结构和过程理解学习问题的基本结构和过程理解学习问题的基本结构和过程理解学习问题的基本结构和过程有监督学习有监督学习q有监督的学习方法有监督的学习方法在样本标签已知的情况下，可以统计出各类训练样本不同在样本标签已知的情况下，可以统计出各类训练样本不同的描述量，如其概率分布，或在特征空间分布的区域等，的描述量，如其概率分布，或在特征空间分布的区域等，利用这些参数进行分类器设计，称为有监督的学习方法。利用这些参数进行分类器设计，称为有监督的学习方法。无监督学习无监督学习q无监督学习无监督学习然而在实际应用中，不少情况下无法预先知道样本的标签，然而在实际应用中，不少情况下无法预先知道样本的标签，也就是说没有训练样本也就是说没有训练样本因而只能从原先没有样本标签的样本集开始进行分类器设因而只能从原先没有样本标签的样本集开始进行分类器设计，这就是通常说的无监督学习方法。计，这就是通常说的无监督学习方法。q对一个具体问题来说有监督与无监督的作法是不相对一个具体问题来说有监督与无监督的作法是不相同的同的有监督学习有监督学习x1x2无监督学习无监督学习x1x2机器学习的问题机器学习的问题存在什么样的算法能从特定的训练数据学习一般的目标函数呢？如存在什么样的算法能从特定的训练数据学习一般的目标函数呢？如存在什么样的算法能从特定的训练数据学习一般的目标函数呢？如存在什么样的算法能从特定的训练数据学习一般的目标函数呢？如果提供了充足的训练数据，什么样的条件下，会使特定的算法收敛果提供了充足的训练数据，什么样的条件下，会使特定的算法收敛果提供了充足的训练数据，什么样的条件下，会使特定的算法收敛果提供了充足的训练数据，什么样的条件下，会使特定的算法收敛到期望的函数？哪个算法对哪些问题和表示的性能最好？到期望的函数？哪个算法对哪些问题和表示的性能最好？到期望的函数？哪个算法对哪些问题和表示的性能最好？到期望的函数？哪个算法对哪些问题和表示的性能最好？多少训练数据是充足的？怎样找到学习到假设的置信度与训练数据多少训练数据是充足的？怎样找到学习到假设的置信度与训练数据多少训练数据是充足的？怎样找到学习到假设的置信度与训练数据多少训练数据是充足的？怎样找到学习到假设的置信度与训练数据的数量及提供给学习器的假设空间特性之间的一般关系？的数量及提供给学习器的假设空间特性之间的一般关系？的数量及提供给学习器的假设空间特性之间的一般关系？的数量及提供给学习器的假设空间特性之间的一般关系？学习器拥有的先验知识是怎样引导从样例进行泛化的过程的？当先学习器拥有的先验知识是怎样引导从样例进行泛化的过程的？当先学习器拥有的先验知识是怎样引导从样例进行泛化的过程的？当先学习器拥有的先验知识是怎样引导从样例进行泛化的过程的？当先验知识仅仅是近似正确时，它们会有帮助吗？验知识仅仅是近似正确时，它们会有帮助吗？验知识仅仅是近似正确时，它们会有帮助吗？验知识仅仅是近似正确时，它们会有帮助吗？关于选择有效的后验训练经验，什么样的策略最好？这个策略的选关于选择有效的后验训练经验，什么样的策略最好？这个策略的选关于选择有效的后验训练经验，什么样的策略最好？这个策略的选关于选择有效的后验训练经验，什么样的策略最好？这个策略的选择会如何影响学习问题的复杂性。择会如何影响学习问题的复杂性。择会如何影响学习问题的复杂性。择会如何影响学习问题的复杂性。怎样把学习任务简化为一个或多个函数逼近问题？换一种方式，系怎样把学习任务简化为一个或多个函数逼近问题？换一种方式，系怎样把学习任务简化为一个或多个函数逼近问题？换一种方式，系怎样把学习任务简化为一个或多个函数逼近问题？换一种方式，系统该试图学习哪些函数？这个过程本身能自动完成吗？统该试图学习哪些函数？这个过程本身能自动完成吗？统该试图学习哪些函数？这个过程本身能自动完成吗？统该试图学习哪些函数？这个过程本身能自动完成吗？学习器怎样自动地改变表示法来提高表示和学习目标函数的能力？学习器怎样自动地改变表示法来提高表示和学习目标函数的能力？学习器怎样自动地改变表示法来提高表示和学习目标函数的能力？学习器怎样自动地改变表示法来提高表示和学习目标函数的能力？课程内容简介课程内容简介qq第第第第2 2章，基于符号和逻辑表示的章，基于符号和逻辑表示的章，基于符号和逻辑表示的章，基于符号和逻辑表示的概念学习概念学习概念学习概念学习（简介简介简介简介）qq第第第第3 3章，章，章，章，决策树决策树决策树决策树qq第第第第4 4章，章，章，章，回归模型与神经网络回归模型与神经网络回归模型与神经网络回归模型与神经网络qq第第第第5 5章，章，章，章，评估假设评估假设评估假设评估假设qq第第第第6 6章，章，章，章，贝叶斯理论（贝叶斯理论（贝叶斯理论（贝叶斯理论（混合模型与混合模型与混合模型与混合模型与EMEM算法算法算法算法）qq第第第第7 7章，章，章，章，基于实例的学习（基于实例的学习（基于实例的学习（基于实例的学习（核函数与径向基函数网络核函数与径向基函数网络核函数与径向基函数网络核函数与径向基函数网络）qq第第第第8 8章，章，章，章，马尔科夫与隐马尔可夫模型马尔科夫与隐马尔可夫模型马尔科夫与隐马尔可夫模型马尔科夫与隐马尔可夫模型qq第第第第9 9章，章，章，章，支持向量机（支持向量机（支持向量机（支持向量机（线性判别与线性判别与线性判别与线性判别与SVMSVM）qq第第第第1010章，章，章，章，增强学习增强学习增强学习增强学习参考期刊与会议参考期刊与会议qq相关杂志相关杂志相关杂志相关杂志MachineLearningMachineLearningNeuralComputationNeuralComputationJournaloftheAmericanStatisticalAssociationJournaloftheAmericanStatisticalAssociationIEEEtransactionsonPatternAnalysis&MachineIEEEtransactionsonPatternAnalysis&MachineIntelligenceIntelligenceqq国际会议国际会议国际会议国际会议国际机器学习会议国际机器学习会议国际机器学习会议国际机器学习会议ICMLICML神经信息处理系统会议神经信息处理系统会议神经信息处理系统会议神经信息处理系统会议NIPSNIPS计算学习理论会议计算学习理论会议计算学习理论会议计算学习理论会议CCLTCCLT国际遗传算法会议国际遗传算法会议国际遗传算法会议国际遗传算法会议ICGAICGA参考学术期刊及国际会议参考学术期刊及国际会议一些网络资源一些网络资源 (1)(1)http:/machine-AAAIMachineLearningTopics：www.aaai.org/AITopics/html/machine.html-SupportVectorMachines：http:/www.support-vector-machines.org/index.html一些网络资源一些网络资源(2)(2)qhttp:/www.cs.cmu.edu/tom/10701_sp11/lectures.shtmlMachineLearning(Spring2011)CMUTomMitchellVideoLecture&SlidesqMachineLearningResources:http:/ 概念学习和一般到特殊序概念学习和一般到特殊序简介简介q许多机器学习涉及到从特殊训练样例中得到一般概念。许多机器学习涉及到从特殊训练样例中得到一般概念。qq概念概念概念概念，可被看作一个对象或事件集合，它是从更大的，可被看作一个对象或事件集合，它是从更大的集合中选取的子集，或在这个较大集合中定义的布尔集合中选取的子集，或在这个较大集合中定义的布尔函数。函数。qq概念学习问题概念学习问题概念学习问题概念学习问题的定义的定义给定一个样例集合以及每个样例是否属于某个概念的标注，给定一个样例集合以及每个样例是否属于某个概念的标注，怎样推断出该怎样推断出该概念的一般定义概念的一般定义概念的一般定义概念的一般定义。又称从样例中逼近布尔函。又称从样例中逼近布尔函数。数。概念学习是指从有关某个布尔函数的输入输出训练样例中概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。推断出该布尔函数。概念学习任务概念学习任务q一个例子一个例子目标概念目标概念Aldo进行水上运动的日子，表示为布尔函数进行水上运动的日子，表示为布尔函数EnjoySport任务目的任务目的基于某天的各属性，预测基于某天的各属性，预测EnjoySport的值的值给定一个样例集给定一个样例集D每个样例表示为每个样例表示为6个属性的集合个属性的集合概念学习任务（概念学习任务（2）YesChangeCoolStrongHighWarmSunny4NoChangeWarmStrongHighColdRainy3YesSameWarmStrongHighWarmSunny2YesSameWarmStrongNormalWarmSunny1EnjoySportForecastWaterWindHumidityAirTempSkyExample表表2-1 目标概念目标概念EnjoySport的训练样例的训练样例概念学习任务（概念学习任务（3）q表示表示假设假设假设假设的形式（目标函数的表示）的形式（目标函数的表示）一个简单的形式，一个简单的形式，实例实例实例实例的各属性约束的的各属性约束的合取式合取式合取式合取式令每个假设为令每个假设为6个约束（或变量）的向量，每个约个约束（或变量）的向量，每个约束对应一个属性可取值范围，为束对应一个属性可取值范围，为？任意本属性可接受的值？任意本属性可接受的值明确指定的属性值明确指定的属性值 不接受任何值不接受任何值假设的例子假设的例子/所有的样例都是正例所有的样例都是正例/所有的样例都是反例所有的样例都是反例概念学习任务（概念学习任务（4）形式化描述形式化描述形式化描述形式化描述：q已知已知实例集实例集X每个实例每个实例x由由6个属性描述，每个属性的取值范围已确定个属性描述，每个属性的取值范围已确定假设集假设集H每个假设每个假设h描述为描述为6个属性的取值约束的合取个属性的取值约束的合取目标概念目标概念c一个布尔函数，变量为实例一个布尔函数，变量为实例训练样例集训练样例集D目标函数（或目标概念）的正例和反例目标函数（或目标概念）的正例和反例q求解求解H中的一假设中的一假设h，使对于，使对于X中任意中任意x，h(x)=c(x)术语定义术语定义q实例实例xq实例集实例集Xq概念概念q目标概念目标概念cq训练样例训练样例xq训练样例集训练样例集Dq正例，目标概念成员正例，目标概念成员q反例，非目标概念成员反例，非目标概念成员q假设假设hq假设集假设集H机器学习的目标机器学习的目标机器学习的目标机器学习的目标就是寻找一个假设就是寻找一个假设h，使得对所有的，使得对所有的h，都有，都有h(x)=c(x)归纳归纳归纳归纳学习假设学习假设q什么是归纳学习？什么是归纳学习？从特殊的样例得到普遍的规律（从特殊的样例得到普遍的规律（从特殊到一般从特殊到一般从特殊到一般从特殊到一般）q归纳归纳只能保证输出的假设能与训练样例相拟合只能保证输出的假设能与训练样例相拟合q归纳假设的一个基本假定归纳假设的一个基本假定对于未见实例最好的假设就是对于未见实例最好的假设就是与训练数据最佳拟合的假与训练数据最佳拟合的假与训练数据最佳拟合的假与训练数据最佳拟合的假设设设设q归纳学习假设归纳学习假设任一假设如果在足够大的训练样例集中很好地逼近目标任一假设如果在足够大的训练样例集中很好地逼近目标函数，它也能在未见实例中很好地逼近目标函数。函数，它也能在未见实例中很好地逼近目标函数。作为作为搜索搜索搜索搜索的概念学习的概念学习q概念学习可以看作一个概念学习可以看作一个搜索的过程搜索的过程搜索的过程搜索的过程搜索范围：假设的表示所隐含定义的整个空间搜索范围：假设的表示所隐含定义的整个空间搜索目标：能够最好地拟合训练样例的假设搜索目标：能够最好地拟合训练样例的假设q当假设的表示形式选定后，那么就隐含地为学习算当假设的表示形式选定后，那么就隐含地为学习算法确定了所有假设的空间法确定了所有假设的空间例子例子EnjoySport的假设空间，如果属性的假设空间，如果属性Sky有有3种可能种可能的值，而的值，而AirTemp、Humidity、Wind、Water和和Forecast都只有两种可能值。都只有两种可能值。实例空间X：包含322222=96种不同的实例假设空间H包含544444=5120种语法不同语法不同的假设由于：包含有符号的假设将每个实例都分类为反例。因此，语义语义不同不同的假设只有1+433333=973个。假设的一般到特殊序假设的一般到特殊序q假设的一般到特殊序关系假设的一般到特殊序关系考虑下面两个假设考虑下面两个假设h1=h2=任何被任何被h1划分为正例的实例都会被划分为正例的实例都会被h2划分为正例，因此划分为正例，因此h2比比h1更一般。更一般。q利用这个关系，无需列举所有假设，就能在无限的假设空间中进行彻底利用这个关系，无需列举所有假设，就能在无限的假设空间中进行彻底的搜索的搜索假设的一般到特殊序（假设的一般到特殊序（2）q关系关系“更一般更一般”的精确定义的精确定义任给实例任给实例x和假设和假设h，说，说x满足满足h，当且仅当，当且仅当h(x)=1令令hj和和hk是在是在X上定义的布尔函数，称上定义的布尔函数，称hj比比hk更一般，当且仅当更一般，当且仅当(x X)(hk(x)=1)(hj(x)=1)记为记为hjmore_general_than_or_equal_tohk，或，或hj ghk假设的一般到特殊序（假设的一般到特殊序（3）q“更一般更一般”的严格情形的严格情形hjghk，当且仅当，当且仅当，(hj ghk)(hk ghj)q“更特殊更特殊”关系的定义关系的定义hj ghk，当且仅当，当且仅当，hk ghjq以以EnjoySport为例说明上面的定义为例说明上面的定义q偏序的特点（区别于全序），全序上的搜索可偏序的特点（区别于全序），全序上的搜索可以是二分法，偏序的搜索比无序简单，比全序以是二分法，偏序的搜索比无序简单，比全序复杂。复杂。q这个偏序关系的定义与目标概念无关这个偏序关系的定义与目标概念无关h1=h2=h3=x1=x2=Find-S：寻找极大特殊假设：寻找极大特殊假设q使用使用more_general_than偏序的搜索算法偏序的搜索算法从从H中最特殊假设开始，然后在假设覆盖正例失败时将其一般化中最特殊假设开始，然后在假设覆盖正例失败时将其一般化Find-SFind-S算法算法算法算法1.将将h初始化为初始化为H中最特殊假设中最特殊假设2.对每个正例对每个正例x对对h的每个属性约束的每个属性约束ai如果如果x满足满足ai那么不做任何处理那么不做任何处理否则将否则将h中中ai替换为替换为x满足的另一个更一般约束满足的另一个更一般约束3.输出假设输出假设hFind-S：寻找极大特殊假设（：寻找极大特殊假设（2）qFind-S算法在例子算法在例子EnjoySport上的应用上的应用hhh遇到反例，遇到反例，h不变（因为不变（因为h已经能够正确地识别反例）已经能够正确地识别反例）hFind-S：寻找极大特殊假设（：寻找极大特殊假设（3）qFind-S算法演示了一种利用算法演示了一种利用more_general_than偏序来搜偏序来搜索假设空间的方法，沿着偏序链，从较特殊的假设逐渐转移索假设空间的方法，沿着偏序链，从较特殊的假设逐渐转移到较一般的假设。因此，每一步得到的假设都是在那一点上到较一般的假设。因此，每一步得到的假设都是在那一点上与训练样例一致的最特殊的假设。与训练样例一致的最特殊的假设。qFind-S的重要特点：对以属性约束的合取式描述的假设空间的重要特点：对以属性约束的合取式描述的假设空间H，保证输出为，保证输出为H中与正例一致的最特殊的假设。中与正例一致的最特殊的假设。q存在的问题存在的问题是否收敛到了正确的目标概念？是否收敛到了正确的目标概念？为什么要用最特殊的假设？为什么要用最特殊的假设？训练样例是否相互一致？训练样例是否相互一致？如果有多个极大特殊假设怎么办？如果有多个极大特殊假设怎么办？变型空间和候选消除算法变型空间和候选消除算法变型空间和候选消除算法变型空间和候选消除算法q候选消除算法概说候选消除算法概说概念学习的另一种方法，概念学习的另一种方法，候选消除算法候选消除算法候选消除算法候选消除算法（candidate-elimination）Find-S算法的不足，输出的假设只是算法的不足，输出的假设只是H中能够拟合训练样例的多个假中能够拟合训练样例的多个假设中的设中的一个一个一个一个候选消除算法输出与训练样例一致的候选消除算法输出与训练样例一致的所有假设的集合所有假设的集合所有假设的集合所有假设的集合候选消除算法在描述这一集合时不需要明确列举所有成员候选消除算法在描述这一集合时不需要明确列举所有成员利用利用more_general_than偏序结构，可以维护一个一致假设集合的偏序结构，可以维护一个一致假设集合的简洁表示简洁表示候选消除算法的应用：候选消除算法的应用：化学质谱分析化学质谱分析化学质谱分析化学质谱分析、启发式搜索的控制规则启发式搜索的控制规则启发式搜索的控制规则启发式搜索的控制规则候选消除算法的缺点：容错性能差候选消除算法的缺点：容错性能差变型空间和候选消除算法（变型空间和候选消除算法（2）q“一致一致”的定义的定义一个假设一个假设h与训练样例集合与训练样例集合D一致，当且仅当对一致，当且仅当对D中每一中每一个样例个样例都有都有h(x)=c(x)，即，即Consistent(h,D)(D)h(x)=c(x)“一致一致”与与“满足满足”的关系的关系q变型空间（变型空间（VersionSpace）与训练样例与训练样例一致一致一致一致的所有假设组成的集合的所有假设组成的集合表示了目标概念的所有合理的变型表示了目标概念的所有合理的变型q关于关于H和和D的变型空间，记为的变型空间，记为VSH,D，是，是H中与训练样例中与训练样例D一一致的所有假设构成的子集致的所有假设构成的子集VSH,D=h H|Consistent(h,D)变型空间和候选消除算法（变型空间和候选消除算法（3）q列表后消除算法列表后消除算法表示变型空间的一种方法是列出其所有成员表示变型空间的一种方法是列出其所有成员变型空间变型空间包含包含H中所有假设的列表中所有假设的列表对每个训练样例对每个训练样例，从变型空间中移除所有，从变型空间中移除所有h(x)c(x)的假设的假设输出输出VersionSpace中的假设列表中的假设列表q优点优点保证得到所有与训练数据一致的假设保证得到所有与训练数据一致的假设q缺点缺点非常繁琐地列出非常繁琐地列出H中的所有假设，大多数实际的假设空间无法做到中的所有假设，大多数实际的假设空间无法做到变型空间和候选消除算法（变型空间和候选消除算法（4）qq变型空间变型空间变型空间变型空间的更简洁表示的更简洁表示变型空间被表示为它的极大一般和极大特殊的成员变型空间被表示为它的极大一般和极大特殊