1、2016.112016.11机器学习机器学习(Machine Learning)q基本概念以及数学定义基本概念以及数学定义q基本性质及其物理意义基本性质及其物理意义q具体算法应用（详细举例讲解）具体算法应用（详细举例讲解）q该算法与其他类似算法的分析比较该算法与其他类似算法的分析比较q可能的发展方向可能的发展方向q附参考文献附参考文献2什么是机器学习什么是机器学习 【经典定义经典定义】：计算机程序如何随着经验积：计算机程序如何随着经验积累自动提高性能，系统自我改进的过程。累自动提高性能，系统自我改进的过程。或：计算机利用经验改善系统自身性能的或：计算机利用经验改善系统自身性能的行为。行为。米切
2、尔米切尔随着该领域的发展，主要做随着该领域的发展，主要做 学习现象学习现象语言、文字的认知识别语言、文字的认知识别图像、场景、自然物体的认知识别图像、场景、自然物体的认知识别规则规则（eg 下雨天要带雨伞）下雨天要带雨伞）复杂的推理、判断能力（智能）复杂的推理、判断能力（智能）好人与坏人？好人与坏人？好猫与坏猫？好猫与坏猫？数据数据知识知识认知认知推理推理决策决策识别识别学习学习 使得计算机具备和人类一样的学习能力使得计算机具备和人类一样的学习能力决策决策推理推理认知认知识别识别 等智能等智能 给定数据（样本、实例）和一定的学习规则，给定数据（样本、实例）和一定的学习规则，从数据中获取知识的能
3、力从数据中获取知识的能力q自然智慧的伟大与奥妙自然智慧的伟大与奥妙举例：婴儿的认知能力（声音、人脸、汽车举例：婴儿的认知能力（声音、人脸、汽车）重要的二个特点重要的二个特点：容错性，推广能力（举一反三）容错性，推广能力（举一反三）q机器智能：希望用机器实现部分智能机器智能：希望用机器实现部分智能q基于数据的机器学习问题（引自清华张学工教基于数据的机器学习问题（引自清华张学工教授）授）根据已知样本估计数据之间的依赖关系，从而对未根据已知样本估计数据之间的依赖关系，从而对未知或无法测量的数据进行预测和判断知或无法测量的数据进行预测和判断关键：推广能力关键：推广能力q中科院王珏研究员给出的定义：中科
4、院王珏研究员给出的定义：令令W是给定世界的有限或无限所有观测对象的集是给定世界的有限或无限所有观测对象的集合，由于我们的观测能力有限，我们只能获得这合，由于我们的观测能力有限，我们只能获得这个世界的一个子集个世界的一个子集 ，称为样本集。机器学，称为样本集。机器学习就是根据这个样本集，推算这个世界习就是根据这个样本集，推算这个世界W的模型的模型，使它对这个世界（尽可能地）为真。，使它对这个世界（尽可能地）为真。q三个重要的理论问题：三个重要的理论问题：一致：一致：W与与Q有相同的性质。有相同的性质。eg.i.i.d划分：设样本定义于划分：设样本定义于d维空间，要寻找在这个空维空间，要寻找在这个
5、空间上的决策分界面间上的决策分界面泛化（推广能力）：对未知样本的判断能力泛化（推广能力）：对未知样本的判断能力WQ qLearning=Improving with experience at some taskImprove over task TWith respect to performance measurement PBased on experience EqExample:中国象棋中国象棋任务任务T：下中国象棋：下中国象棋 性能目标性能目标P：比赛中击败对手（的百分比）：比赛中击败对手（的百分比）训练经验训练经验E：和自己进行对弈，或者看棋谱：和自己进行对弈，或者看棋谱Ref：
6、机器学习机器学习（曾华军等译）（曾华军等译）引用自引用自CMU Dr.Eric Xing的的Lecture Notes机器学习的研究意义机器学习的研究意义qScience2001年论文：年论文：每个科学领域的科学过程都有它自己的特点，但是，每个科学领域的科学过程都有它自己的特点，但是，。对这个抽象的科。对这个抽象的科学过程的每一个环节，机器学习都有相应的发展，我们相学过程的每一个环节，机器学习都有相应的发展，我们相信它将导致科学方法中从假设生成、模型构造到决定性实信它将导致科学方法中从假设生成、模型构造到决定性实验这些所有环节的合适的、部分的自动化。当前机器学习验这些所有环节的合适的、部分的自
7、动化。当前机器学习研究在一些基本论题上取得令人印象深刻的进展，我们预研究在一些基本论题上取得令人印象深刻的进展，我们预期机器学习研究在今后若干年中将有稳定的进展！期机器学习研究在今后若干年中将有稳定的进展！”在稍早前，在稍早前，2000年年Science还发表了另外还发表了另外3篇篇ML方面方面的论文的论文“The Manifold Way of Perceptron”,“A global geometric framework for nonlinear dimensionality reduction”,”Nonlinear dimensionality reduction by loca
8、lly”Mjolsness,D DeCoste,Machine Learning for Science:State of the Art and Future Prospects-Science,2001:2051-2055.受到令人惊讶受到令人惊讶的重视！的重视！摘自南京大学周志华教授摘自南京大学周志华教授生物信息学计算金融学分子生物学行星地质学工业过程控制机器人遥感信息处理信息安全机 器 学 习重要性：例子网络安全入侵检测：是否是入侵？是何种入侵？如何检测？历史数据：以往的正常访问模式及其表现、以往的入侵模式及其表现对当前访问模式分类这是一个典型的预测型机器学习问题常用技术：神经网络 决
9、策树支持向量机 k近邻序列分析 聚类 摘自南京大学周志华教授摘自南京大学周志华教授重要性：例子生物信息学常用技术：神经网络 支持向量机隐马尔可夫模型k近邻 决策树序列分析 聚类 重要性：例子数据驱动控制q人工智能：人工智能：学习的概念符号表示学习的概念符号表示qBayes 方法方法q统计学：统计学：统计学习理论统计学习理论(SLT)q计算复杂性理论计算复杂性理论q控制论控制论q信息论：最小描述长度信息论：最小描述长度q哲学：哲学：“Occams Razor原则原则”，“没有免费午餐没有免费午餐”q心理学和神经生物学：心理学和神经生物学：Neural Networks（神经网络）（神经网络）q符
10、号机器学习符号机器学习Eg.决策树，决策树，ID3，q计算学习理论（统计学习理论）计算学习理论（统计学习理论）PAC，SVMq监督学习，非监督学习，半监督学习监督学习，非监督学习，半监督学习q集群机器学习集群机器学习Ensemble Learning，Boostingq流行（流行（Manifold）学习）学习q强化学习强化学习qRanking学习学习q聚类学习聚类学习qhttp:/en.wikipedia.org/wiki/Machine_Learning机器学习简要发展历史回顾机器学习简要发展历史回顾q1950s：神经科学的理论基础：神经科学的理论基础James关于神经元是相互连接的发现关于
11、神经元是相互连接的发现McCullon&Pitts的神经元模型的神经元模型Hebb 学习律（相互连接强弱度的变换规则）学习律（相互连接强弱度的变换规则）q1960s：感知器（：感知器（Perceptron）时代）时代1957年年Rosenblatt首次提出首次提出q1969年：年：Perceptron出版，提出著名出版，提出著名的的XOR问题问题q1970s：符号主义，逻辑推理：符号主义，逻辑推理q1980s：MLP+BP算法成功解决算法成功解决XOR问题问题，从此进入神经网络时代（连接主义），从此进入神经网络时代（连接主义）q1960s-1970s:统计学习理论创立统计学习理论创立VC维的基
12、本概念维的基本概念结构风险最小化原则结构风险最小化原则概率空间的大数定律概率空间的大数定律q1990s：统计学习理论的发展及完善：统计学习理论的发展及完善典型代表：典型代表：SVM（Vapnik，Bell实验室）实验室）结构风险最小化结构风险最小化最小描述长度原则最小描述长度原则小样本问题小样本问题核函数、核空间变化核函数、核空间变化PAC理论下的弱可学习理论的建立理论下的弱可学习理论的建立支持向量机支持向量机q2000s：各种机器学习理论及算法得以充分发展：各种机器学习理论及算法得以充分发展符号机器学习符号机器学习计算机器学习（统计学习理论，典型例子：计算机器学习（统计学习理论，典型例子：S
13、VM）集群机器学习（典型代表：集群机器学习（典型代表：Boosting）强化机器学习强化机器学习流行机器学习流行机器学习监督学习，非监督学习监督学习，非监督学习半监督学习、半监督学习、.q机器实际上是一个应用驱动的学科，其根本的驱动力机器实际上是一个应用驱动的学科，其根本的驱动力是：是：“更多、更好地解决实际问题更多、更好地解决实际问题”q由于近由于近20年的飞速发展，机器学习已经具备了一定的年的飞速发展，机器学习已经具备了一定的解决实际问题的能力，似乎逐渐开始成为一种基础性解决实际问题的能力，似乎逐渐开始成为一种基础性、透明化的、透明化的“支持技术、服务技术支持技术、服务技术”基础性：在众多
14、的学科领域都得以应用（基础性：在众多的学科领域都得以应用（“无所不在无所不在”）透明化：用户看不见机器学习，看见的是防火墙、生物信透明化：用户看不见机器学习，看见的是防火墙、生物信息、搜索引擎；（息、搜索引擎；（“无所不在无所不在”）“机器更好用了机器更好用了”(正如正如CALO的一些描述：的一些描述：“you wont leave home without it”；”embodied as a software environment that transcends workstations,PDAs,cell phones,”)q机器学习的主要策略与基本结构机器学习的主要策略与基本结构 机
15、器学习的主要策略机器学习的主要策略 机器学习系统的基本结构机器学习系统的基本结构 q我们以西蒙的学习定义做为出发点，建立起下图我们以西蒙的学习定义做为出发点，建立起下图1.1所示的简单的学习模型，然后通过对这个简单所示的简单的学习模型，然后通过对这个简单模型的讨论，总结出设计学习系统应当注意的某模型的讨论，总结出设计学习系统应当注意的某些总的原则。些总的原则。q有监督的学习方法有监督的学习方法在样本标签已知的情况下，可以统计出各类训练样本不在样本标签已知的情况下，可以统计出各类训练样本不同的描述量，如其概率分布，或在特征空间分布的区域同的描述量，如其概率分布，或在特征空间分布的区域等，利用这些
16、参数进行分类器设计，称为有监督的学习等，利用这些参数进行分类器设计，称为有监督的学习方法。方法。q无监督学习无监督学习然而在实际应用中，不少情况下无法预先知道样本的标然而在实际应用中，不少情况下无法预先知道样本的标签，也就是说没有训练样本签，也就是说没有训练样本因而只能从原先没有样本标签的样本集开始进行分类器因而只能从原先没有样本标签的样本集开始进行分类器设计，这就是通常说的无监督学习方法。设计，这就是通常说的无监督学习方法。q对一个具体问题来说有监督与无监督的作法是不相对一个具体问题来说有监督与无监督的作法是不相同的同的x1x2x1x2http:/machine- AAAI Machine
17、Learning Topics：www.aaai.org/AITopics/html/machine.html-Support Vector Machines：http:/www.support-vector-machines.org/index.html qhttp:/www.cs.cmu.edu/tom/10701_sp11/lectures.shtmlMachine Learning(Spring 2011)CMUTom MitchellVideo Lecture&SlidesqMachine Learning Resources:http:/ Weka：Data Mining(ML)s
18、oftware in Java:http:/www.cs.waikato.ac.nz/ml/weka/LibSVM-A Library for Support Vector Machines：www.csie.ntu.edu.tw/cjlin/libsvm MLC+:http:/ library of C+classes for supervised machine learning UCI-Machine Learning information,software and databases:http:/archive.ics.uci.edu/ml/qKernal Machines:http
19、:/www.kernel-machines.org/qhttp:/mloss.org/software/:Machine Learning Open Source Softwareqhttp:/www3.ntu.edu.sg/home/aswduch/ai-ml.html q数据挖掘研究院：数据挖掘研究院：http:/ 概念学习和一般到特殊序概念学习和一般到特殊序简介简介q许多机器学习涉及到从特殊训练样例中得到一般概念。许多机器学习涉及到从特殊训练样例中得到一般概念。，可被看作一个对象或事件集合，它是从更大的，可被看作一个对象或事件集合，它是从更大的集合中选取的子集，或在这个较大集合中定义的布
20、尔集合中选取的子集，或在这个较大集合中定义的布尔函数。函数。的定义的定义给定一个样例集合以及每个样例是否属于某个概念的标注，给定一个样例集合以及每个样例是否属于某个概念的标注，怎样推断出该怎样推断出该。又称从样例中逼近布尔函。又称从样例中逼近布尔函数。数。概念学习是指从有关某个布尔函数的输入输出训练样例中概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。推断出该布尔函数。概念学习任务概念学习任务q一个例子一个例子目标概念目标概念Aldo进行水上运动的日子，表示为布尔函数进行水上运动的日子，表示为布尔函数EnjoySport任务目的任务目的基于某天的各属性，预测基于某天的各属性
21、，预测EnjoySport的值的值给定一个样例集给定一个样例集D每个样例表示为每个样例表示为6个属性的集合个属性的集合概念学习任务（概念学习任务（2）YesChangeCoolStrongHighWarmSunny4NoChangeWarmStrongHighColdRainy3YesSameWarmStrongHighWarmSunny2YesSameWarmStrongNormalWarmSunny1EnjoySportForecastWaterWindHumidityAirTempSkyExample表表2-1 目标概念目标概念EnjoySport的训练样例的训练样例概念学习任务（概念学
22、习任务（3）q表示表示的形式（目标函数的表示）的形式（目标函数的表示）一个简单的形式，一个简单的形式，的各属性约束的的各属性约束的令每个假设为令每个假设为6个约束（或变量）的向量，每个约个约束（或变量）的向量，每个约束对应一个属性可取值范围，为束对应一个属性可取值范围，为？任意本属性可接受的值？任意本属性可接受的值明确指定的属性值明确指定的属性值 不接受任何值不接受任何值假设的例子假设的例子/所有的样例都是正例所有的样例都是正例/所有的样例都是反例所有的样例都是反例概念学习任务（概念学习任务（4）q已知已知实例集实例集X每个实例每个实例x由由6个属性描述，每个属性的取值范围已确定个属性描述，每
23、个属性的取值范围已确定假设集假设集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就是寻找一个假设就是
24、寻找一个假设h，使得对所有的，使得对所有的h，都有，都有h(x)=c(x)学习假设学习假设q什么是归纳学习？什么是归纳学习？从特殊的样例得到普遍的规律（从特殊的样例得到普遍的规律（）q归纳归纳只能保证输出的假设能与训练样例相拟合只能保证输出的假设能与训练样例相拟合q归纳假设的一个基本假定归纳假设的一个基本假定对于未见实例最好的假设就是对于未见实例最好的假设就是q归纳学习假设归纳学习假设任一假设如果在足够大的训练样例集中很好地逼近目标任一假设如果在足够大的训练样例集中很好地逼近目标函数，它也能在未见实例中很好地逼近目标函数。函数，它也能在未见实例中很好地逼近目标函数。作为作为的概念学习的概念学习
25、q概念学习可以看作一个概念学习可以看作一个搜索范围：假设的表示所隐含定义的整个空间搜索范围：假设的表示所隐含定义的整个空间搜索目标：能够最好地拟合训练样例的假设搜索目标：能够最好地拟合训练样例的假设q当假设的表示形式选定后，那么就隐含地为学习算当假设的表示形式选定后，那么就隐含地为学习算法确定了所有假设的空间法确定了所有假设的空间例子例子EnjoySport的假设空间，如果属性的假设空间，如果属性Sky有有3种可能种可能的值，而的值，而AirTemp、Humidity、Wind、Water和和 Forecast都只有两种可能值。都只有两种可能值。实例空间X：包含322222=96种不同的实例假
26、设空间H 包含544444=5120种语法不同语法不同的假设 由于：包含有符号的假设将每个实例都分类为反例。因此，语义语义不同不同的假设只有1+433333=973个。假设的一般到特殊序假设的一般到特殊序q假设的一般到特殊序关系假设的一般到特殊序关系考虑下面两个假设考虑下面两个假设h1=h2=任何被任何被h1划分为正例的实例都会被划分为正例的实例都会被h2划分为正例，因此划分为正例，因此h2比比h1更一般。更一般。q利用这个关系，无需列举所有假设，就能在无限的假设空间中进行彻底利用这个关系，无需列举所有假设，就能在无限的假设空间中进行彻底的搜索的搜索假设的一般到特殊序（假设的一般到特殊序（2）
27、q关系关系“更一般更一般”的精确定义的精确定义任给实例任给实例x和假设和假设h，说，说x满足满足h，当且仅当，当且仅当h(x)=1令令hj和和hk是在是在X上定义的布尔函数，称上定义的布尔函数，称hj比比hk更一般，当且仅当更一般，当且仅当(x X)(hk(x)=1)(hj(x)=1)记为记为hj more_general_than_or_equal_to hk，或，或hj g hk假设的一般到特殊序（假设的一般到特殊序（3）q“更一般更一般”的严格情形的严格情形hj g hk，当且仅当，当且仅当，(hj g hk)(hk g hj)q“更特殊更特殊”关系的定义关系的定义hj g hk，当且仅
28、当，当且仅当，hk g hjq以以EnjoySport为例说明上面的定义为例说明上面的定义q偏序的特点（区别于全序），全序上的搜索可偏序的特点（区别于全序），全序上的搜索可以是二分法，偏序的搜索比无序简单，比全序以是二分法，偏序的搜索比无序简单，比全序复杂。复杂。q这个偏序关系的定义与目标概念无关这个偏序关系的定义与目标概念无关h1=h2=h3=x1=x2=Find-S：寻找极大特殊假设：寻找极大特殊假设q使用使用more_general_than偏序的搜索算法偏序的搜索算法从从H中最特殊假设开始，然后在假设覆盖正例失败时将其一般化中最特殊假设开始，然后在假设覆盖正例失败时将其一般化将将h初始
29、化为初始化为H中最特殊假设中最特殊假设对每个正例对每个正例x对对h的每个属性约束的每个属性约束ai如果如果x满足满足ai那么不做任何处理那么不做任何处理否则将否则将h中中ai替换为替换为x满足的另一个更一般约束满足的另一个更一般约束1.输出假设输出假设hFind-S：寻找极大特殊假设（：寻找极大特殊假设（2）qFind-S算法在例子算法在例子EnjoySport上的应用上的应用hhh遇到反例，遇到反例，h不变（因为不变（因为h已经能够正确地识别反例）已经能够正确地识别反例）hFind-S：寻找极大特殊假设（：寻找极大特殊假设（3）qFind-S算法演示了一种利用算法演示了一种利用more_ge
30、neral_than偏序来搜偏序来搜索假设空间的方法，沿着偏序链，从较特殊的假设逐渐转索假设空间的方法，沿着偏序链，从较特殊的假设逐渐转移到较一般的假设。因此，每一步得到的假设都是在那一移到较一般的假设。因此，每一步得到的假设都是在那一点上与训练样例一致的最特殊的假设。点上与训练样例一致的最特殊的假设。qFind-S的重要特点：对以属性约束的合取式描述的假设空的重要特点：对以属性约束的合取式描述的假设空间间H，保证输出为，保证输出为H中与正例一致的最特殊的假设。中与正例一致的最特殊的假设。q存在的问题存在的问题是否收敛到了正确的目标概念？是否收敛到了正确的目标概念？为什么要用最特殊的假设？为什
31、么要用最特殊的假设？训练样例是否相互一致？训练样例是否相互一致？如果有多个极大特殊假设怎么办？如果有多个极大特殊假设怎么办？q候选消除算法概说候选消除算法概说概念学习的另一种方法，概念学习的另一种方法，（candidate-elimination）Find-S算法的不足，输出的假设只是算法的不足，输出的假设只是H中能够拟合训练样例的多个假中能够拟合训练样例的多个假设中的设中的候选消除算法输出与训练样例一致的候选消除算法输出与训练样例一致的候选消除算法在描述这一集合时不需要明确列举所有成员候选消除算法在描述这一集合时不需要明确列举所有成员利用利用more_general_than偏序结构，可以维
32、护一个一致假设集合的偏序结构，可以维护一个一致假设集合的简洁表示简洁表示候选消除算法的应用：候选消除算法的应用：、候选消除算法的缺点：容错性能差候选消除算法的缺点：容错性能差变型空间和候选消除算法（变型空间和候选消除算法（2）q“一致一致”的定义的定义一个假设一个假设h与训练样例集合与训练样例集合D一致，当且仅当对一致，当且仅当对D中每一中每一个样例个样例都有都有h(x)=c(x)，即，即Consistent(h,D)(D)h(x)=c(x)“一致一致”与与“满足满足”的关系的关系q变型空间（变型空间（Version Space）与训练样例与训练样例的所有假设组成的集合的所有假设组成的集合表示
33、了目标概念的所有合理的变型表示了目标概念的所有合理的变型q关于关于H和和D的变型空间，记为的变型空间，记为VSH,D，是，是H中与训练样例中与训练样例D一一致的所有假设构成的子集致的所有假设构成的子集VSH,D=h H|Consistent(h,D)变型空间和候选消除算法（变型空间和候选消除算法（3）q列表后消除算法列表后消除算法表示变型空间的一种方法是列出其所有成员表示变型空间的一种方法是列出其所有成员变型空间变型空间包含包含H中所有假设的列表中所有假设的列表对每个训练样例对每个训练样例，从变型空间中移除所有，从变型空间中移除所有h(x)c(x)的假设的假设输出输出Version Space
34、中的假设列表中的假设列表q优点优点保证得到所有与训练数据一致的假设保证得到所有与训练数据一致的假设q缺点缺点非常繁琐地列出非常繁琐地列出H中的所有假设，大多数实际的假设空间无法做到中的所有假设，大多数实际的假设空间无法做到变型空间和候选消除算法（变型空间和候选消除算法（4）的更简洁表示的更简洁表示变型空间被表示为它的极大一般和极大特殊的成员变型空间被表示为它的极大一般和极大特殊的成员这些成员形成了一般和特殊边界的集合，这些边界在整个偏序结构中划分出这些成员形成了一般和特殊边界的集合，这些边界在整个偏序结构中划分出变型空间变型空间以以EnjoySport为例为例变型空间和候选消除算法（变型空间和
35、候选消除算法（5）q形式化定义形式化定义极大一般极大一般极大特殊极大特殊关于假设空间关于假设空间H和训练数据和训练数据D的的一般边界一般边界G，是在，是在H中与中与D相一致的极大一般成员的集合相一致的极大一般成员的集合关于假设空间关于假设空间H和训练数据和训练数据D的的特殊边界特殊边界S，是在，是在H中与中与D相一致的极大特殊成员的集合相一致的极大特殊成员的集合变型空间和候选消除算法（变型空间和候选消除算法（6）:令令X为一任意的实例集合，为一任意的实例集合，H为为X上定义的上定义的布尔假设的集合。令布尔假设的集合。令c:X0,1为为X上定义的任一目标概念，上定义的任一目标概念，并令并令D为任
36、一训练样例集合为任一训练样例集合。对所有的。对所有的X,H,c,D以以及良好定义的及良好定义的S和和G：VSH,D=h H|(s S)(g G)(g gh gs)证明：只需证明：证明：只需证明：1）每一个满足上式右边的）每一个满足上式右边的h都在都在VSH,D中，中，2）VSH,D的每个成员都满足都满足等式右边。的每个成员都满足都满足等式右边。变型空间和候选消除算法（变型空间和候选消除算法（7）q候选消除算法候选消除算法初始化初始化G和和S如果如果d是一个正例是一个正例从从G中移去所有与中移去所有与d不一致的假设不一致的假设对对S中每个与中每个与d不一致的假设不一致的假设s 从从S中移去中移去
37、s 把把s的所有的极小泛化式的所有的极小泛化式h加入到加入到S中，其中中，其中h满足满足h与与 d一致，而且一致，而且G的某个成员比的某个成员比h更一般更一般 从从S中移去所有这样的假设：它比中移去所有这样的假设：它比S中另一个假设更一般中另一个假设更一般如果如果d是一个反例是一个反例从从S中移去所有与中移去所有与d不一致的假设不一致的假设对对G中每个与中每个与d不一致的假设不一致的假设g 从从G中移去中移去g 把把g的所有的极小特殊化式的所有的极小特殊化式h加入到加入到G中，其中中，其中h满足满足h与与d一致，而且一致，而且S的某个成员比的某个成员比h更特殊更特殊 从从G中移去所有这样的假设
38、：它比中移去所有这样的假设：它比G中另一个假设更特殊中另一个假设更特殊变型空间和候选消除算法（变型空间和候选消除算法（8）q算法举例算法举例S1:S2:G3:S2 S3:S4:G4:G0 G1:G0 G1 G2:图图2-7 最终变型空间最终变型空间变型空间和候选消除的说明变型空间和候选消除的说明q候选消除算法收敛到正确的假设候选消除算法收敛到正确的假设训练样例中没有错误训练样例中没有错误H中确实包含描述目标概念的正确假设中确实包含描述目标概念的正确假设q如果样例中存在错误如果样例中存在错误如果给定足够的训练数据，我们会发现如果给定足够的训练数据，我们会发现S和和G边界收敛边界收敛得到一个空的变
39、型空间得到一个空的变型空间q如果目标概念不能由假设表示方式所描述如果目标概念不能由假设表示方式所描述比如是约束的析取比如是约束的析取 变型空间和候选消除（变型空间和候选消除（2）q下一步需要什么样的训练样例下一步需要什么样的训练样例一般来说，概念学习的一般来说，概念学习的，是产生实例以满足当前变型空间中大约半数，是产生实例以满足当前变型空间中大约半数的假设。这样，变型空间的大小可以在遇到每个新样例时减半，正确的目标概念就的假设。这样，变型空间的大小可以在遇到每个新样例时减半，正确的目标概念就可在只用可在只用log2|VS|次实验后得到。次实验后得到。变型空间和候选消除（变型空间和候选消除（3）
40、q怎样使用不完全学习概念怎样使用不完全学习概念虽然图虽然图2-7的变型空间中仍包含多个假设，即目标概念还未学习到，但是仍然有可能的变型空间中仍包含多个假设，即目标概念还未学习到，但是仍然有可能对新样例进行一定可信度的分类。对新样例进行一定可信度的分类。待分类的新实例待分类的新实例概念的应用概念的应用概念的应用概念的应用q判断是否是正例判断是否是正例判断是否满足判断是否满足S中的每个假设中的每个假设q判断是否是反例判断是否是反例判断是否不满足判断是否不满足G中的每个假设中的每个假设归纳偏置归纳偏置q有关候选消除算法的几个问题有关候选消除算法的几个问题如果目标概念不在假设空间中怎么办？如果目标概念
41、不在假设空间中怎么办？是否可设计一个包含所有假设的空间来解决这一困难？是否可设计一个包含所有假设的空间来解决这一困难？假设空间的大小对于算法推广到未见实例的能力有什么影响？假设空间的大小对于算法推广到未见实例的能力有什么影响？假设空间的大小对所需训练样例的数量有什么影响？假设空间的大小对所需训练样例的数量有什么影响？归纳偏置（归纳偏置（2）q一个有偏的假设空间一个有偏的假设空间在在EnjoySport这个例子中，假设空间限制为只包含属性值的合取。（有偏）这个例子中，假设空间限制为只包含属性值的合取。（有偏）这一限制，导致假设空间不能够表示最简单的析取形式的目标概念。这一限制，导致假设空间不能够
42、表示最简单的析取形式的目标概念。归纳偏置（归纳偏置（3）q无偏的学习器无偏的学习器为了保证目标概念在假设空间中，需要提供一个假设空间，它能表达所有的可教授为了保证目标概念在假设空间中，需要提供一个假设空间，它能表达所有的可教授概念。换言之，它能表达实例集概念。换言之，它能表达实例集X的所有子集。的所有子集。q问题：为什么问题：为什么2.3节中合取假设空间只能表示节中合取假设空间只能表示973个假设？个假设？归纳偏置（归纳偏置（4）qEnjoySport的无偏形式的无偏形式带来的问题：概念学习算法无法从训练样例中泛化。带来的问题：概念学习算法无法从训练样例中泛化。要想获得单个目标概念，就必须提供
43、要想获得单个目标概念，就必须提供X中所有实例作为训练样例中所有实例作为训练样例使用使用2.6.3节讨论的部分学习的无效节讨论的部分学习的无效归纳偏置（归纳偏置（5）q无偏学习的无用性无偏学习的无用性归纳学习的一个基本属性：学习器如果不对目标概念的形式做预先的假定，归纳学习的一个基本属性：学习器如果不对目标概念的形式做预先的假定，它从根本上无法对未见实例进行分类它从根本上无法对未见实例进行分类归纳学习需要的预先假定，称为归纳偏置归纳学习需要的预先假定，称为归纳偏置归纳偏置（归纳偏置（6）q归纳偏置的精确定义归纳偏置的精确定义(Dc xi)L(xi,Dc)需要在需要在Dc xi上附加怎样的前提，以
44、使上附加怎样的前提，以使L(xi,Dc)能够演绎派生。能够演绎派生。L的归纳偏置定义为前提集合的归纳偏置定义为前提集合B，使所有的新实例满足：，使所有的新实例满足：(B Dc xi)L(xi,Dc)考虑对于实例集合考虑对于实例集合X的概念学习算法的概念学习算法L。令。令c为为X上定义的任上定义的任一概念，并令一概念，并令Dc为为c的任意训练样例集合，的任意训练样例集合，L(xi,Dc)表示经表示经过过Dc训练后训练后L赋予实例赋予实例xi的分类。的分类。L的归纳偏置是最小断言集的归纳偏置是最小断言集合合B，它使任意目标概念，它使任意目标概念c和相应的训练样例和相应的训练样例Dc满足：满足：xi
45、 X(B Dc xi)L(xi,Dc)归纳偏置（归纳偏置（6）q候选消除算法的归纳偏置候选消除算法的归纳偏置c HInductive Systems and Equivalent Deductive Systems(归纳归纳与演绎与演绎)归纳偏置（归纳偏置（7）q3个有偏程度不同的归纳学习算法个有偏程度不同的归纳学习算法机械式机械式候选消除算法候选消除算法Find-Sq一种算法的有偏性越强，它的归纳能力越强，可以分类更多的未见实例。一种算法的有偏性越强，它的归纳能力越强，可以分类更多的未见实例。q某些归纳偏置隐含在学习器中，有些表示为断言集合，可由学习器操作。某些归纳偏置隐含在学习器中，有些表
46、示为断言集合，可由学习器操作。小结小结概念学习可看作概念学习可看作的过程的过程;假设的一般到特殊假设的一般到特殊可以定义在任何概念学习问题中，可以定义在任何概念学习问题中，这种结构便于假设空间的搜索这种结构便于假设空间的搜索;使用一般到特殊序，在偏序结构的一个分支上执行使用一般到特殊序，在偏序结构的一个分支上执行一般到特殊搜索，寻找一个与样例一致的最特殊假设一般到特殊搜索，寻找一个与样例一致的最特殊假设;利用一般到特殊序，通过渐近地计算极大特殊假利用一般到特殊序，通过渐近地计算极大特殊假设集合和极大一般假设集合发现变型空间；设集合和极大一般假设集合发现变型空间；候选消除算法候选消除算法，后面会
47、描述一些学习算法，它们能，后面会描述一些学习算法，它们能够处理有噪声的数据和目标概念无法在假设空间中表示的情况够处理有噪声的数据和目标概念无法在假设空间中表示的情况归纳学习算法归纳学习算法，候选消除算法的偏置是：目标，候选消除算法的偏置是：目标概念可以在假设空间中找到。输出的假设和对新实例的分类可概念可以在假设空间中找到。输出的假设和对新实例的分类可由归纳偏置和训练样例演绎推出由归纳偏置和训练样例演绎推出思考题思考题q2-1.解释为什么解释为什么EnjoySport学习任务的假设空间的大小为学习任务的假设空间的大小为973。如果增加一属。如果增加一属性性WaterCurrent，可取值，可取值
48、Light、Moderate和和Strong，那么可能的实例数和，那么可能的实例数和可能的假设数将会增加多少？推广到一般，增加一新属性可能的假设数将会增加多少？推广到一般，增加一新属性A，有，有k种取值，实种取值，实例数和假设数将会增加多少？例数和假设数将会增加多少？思考题思考题q2-2 在候选消除算法中，如果训练样例按在候选消除算法中，如果训练样例按EnjoySport例子中的逆序出现，请例子中的逆序出现，请分步给出分步给出S和和G边界集合。尝试对训练样例排序，以使边界集合。尝试对训练样例排序，以使EnjoySport例子中的所例子中的所有有S和和G集合的中间结果的大小之和为最小？集合的中间
49、结果的大小之和为最小？YesChangeCoolStrongHighWarmSunny4NoChangeWarmStrongHighColdRainy3YesSameWarmStrongHighWarmSunny2YesSameWarmStrongNormalWarmSunny1EnjoySportForecastWaterWindHumidityAirTempSkyExample思考题思考题q2-3 实现实现Find-S算法和候选消除算法。验证它是否可成功地产生算法和候选消除算法。验证它是否可成功地产生EnjoySport例子中各步骤结果。例子中各步骤结果。第第3章章 决策树学习决策树学习(
50、Decision-Tree Algorithm)排名排名主题主题算法算法得票数得票数发表时间发表时间作者作者陈述陈述人人1分类C4.5611993Quinlan,J.RHiroshi Motoda2聚类k-Means 601967MacQueen,J.BJoydeep Ghosh3统计学习SVM 581995Vapnik,V.NQiangYang4关联分析Apriori 521994Rakesh Agrawal Christos Faloutsos5统计学习EM482000McLachlan,GJoydeep Ghosh 6链接挖掘PageRank461998Brin,S.Christos F
