ai-7ml-p基于解释学习

概述

实例学习

基于解释的学习

决策树学习

神经网络学习.第六章机器学习Machine

Learning第六章机器学习Machine

Learning

概述

实例学习

基于解释的学习

决策树学习

神经网络学习.机器学习—概述

1、 机器学习？

2、机器学习基本形式

3、机器学习学科

4、为什么要研究机器学习

5、机器学习发展历史

6、机器学习模型

7、机器学习方法的分类

8、机器学习研究目的机器学习—概述

1、 机器学习？

机器学习？

知识发现-knowledgediscovery

data mining数据挖掘

pattern

discovery

模式发现（模式识别）

data

dredging (扑捞)

data archeology（考古）机器学习—概述

1、机器学习？机器学习—概述

1、机器学习？

Simon（1983）：学习就是系统中的变化，这种变化使系统比以前更有效地去做同样的工作。

Minsky (1985)：学习是在 头脑中（心里 ）进行有用的变化。

“利用经验来改善计算机系统自身的性能”。“在不直接针对问题进行编

的情况下，赋予计算机学习能力的一个研究领域。”

是人工智能的

研究领域之一，

其最初的研究

是为了让计算机系统具有人的学习能力以便实现人工智能。

学习是一种具有多视觉、多侧面的现象。学习的过有：获取新的陈述性知识、通过教育或实践掌握并发展机械技能和认知能力、将新知识组织成为通用化和有效的表达形式、借助观察和实验发现新的事实和新的理论。

Machine

Learning,是一门专门研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身性能的学科。机器学习—概述

2、基本形式

知识获取和技能求精。学习的本质就是获取新的知识。包括物理系统和行为的描述和建模，构造客观现实的表示。——知识获取

通过实践逐渐改造机制和认知并掌握技能。例：学骑自行车，学游泳，学开车等。这些技能包括意识的或机制的协调。这种改进又是通过反复实践和从失败的行为中纠正偏差来进行的。——技能求精机器学习—概述知识获取的本质是一个自觉的过

其结果是产生新的符号知识结构和智力模型。而技能求精则是下意识地借助于反复地实践来实现的。本章只涉及学习的知识获取问题。机器学习—概述

3、机器学习学科

早起的研究：Rosenblatt的感知机模型（1956）,Widrow的Madline(1960),Samuel的符号机器学

965），Minsky的“Perception”的专著（69,88）。

1983，R.S. Michalski的《机器学习：通往人工智能的途径》

1986，Machine

Learning

杂志创刊，《ArtificialIn ligence》 了机器学习专辑

1990年，MIT

《机器学习:风范与方法》一书

1997,《Machine

Learning》,Tom

M.Mitc ,

以后迅速发展。

2000

,<Journal

of

Machine

Learning

Research>机器学习—概述.序号简称全称1AIArtificial

In

ligenceElsevierom/artificial-in

ligence/2TPAMIIEEETrans

on

Patternysis

and

MachineIn

ligenceIEEE/portal/web/tpami/home3IJCVInternational

Journal

ofComputer

VisionSpringerhttp:/

/journ

al/112634JMLRJournal

of

MachiLearning

ResearIT

Press

3、机器学习学科期刊A-人工智能与模式识别CCF机器学习—概述.

3、机器学习学科会议A-人工智能与模式识别CCF序号会议简称会议全称1AAAIAAAI

Conference

on

ArtificialAAAIInligence2CVPRIEEE

Conference

on

ComputerVision

andPattern

RecognitionIEEEpr13/3ICCVInternationalConference

onComputer

VisionIEEE4ICMLInternationalConference

onMachine

LearningACM5IJCAIInternational

Joint

Conference

onArtificial

In

ligenceMorganKaufmann机器学习—概述

3、机器学习学科

机器学习与数据挖掘

“经验”在计算机系统中主要是以数据的形式存在的,数据库是主要的数据源，数据挖掘因此而重要了，知识发现。数据挖掘就是试图从海量数据中找出有用的知识。

如沃尔玛公司（Wal-Mart

）“买尿布的人很可能会买啤酒”

数据挖掘又可以视为机器学习和数据库的交叉，它主要利用机器学习界提供的技术来分析海量数据，利用数据库界提供的技术来管理海量数据。

机器学习理论成果已在多、计算机图形学、计算机网络、操作系统、工等众多领域中发挥作用。尤其在计算机视觉和自然语言处理中。如十大人造（人工眼、人工耳等）。1.手指

器2.人工眼睛3.人工胰腺4.闻疾病的鼻子5.3D

打印耳朵6.微型人脑7.思想控制仿生腿、8.触感人造手、9.在培养皿中跳动的心脏、10、十大人造机器学习—概述

4、为什么要研究机器学习？

人工智能主要是为了研究人的智能，模仿其机理将其应用于工的科学。在这个过中必然会问道：“人类怎样做才能获取这种知识（或特殊技能）？”。

很难想象一个没有学习功能的系统可以称为智能系统。机器学习—概述

4、为什么要研究机器学习？

当前人工智能研究的热点之一就是机器学

习。包括学习的计算理论和构造学习系统。现在的人工智能系统还完全没有或仅有很

有限的学习能力。

系统中的知识由人工编送入系统，知识中的错误也不能自动改正。也就是说，现有的大多数人工智能是演绎的、没有归纳推理，因而不能自动获取和生成知识。机器学习—概述4、为什么要研究机器学习？

未来的计算机将有自动获取知识的能力，它们直接由书本学习，通过与人谈话学习，通过观察学习。它们通过实践自我完善，克服人的 少、效率低、注意力分散、难以传送所获取的知识等局限性。一台计算机获取的知识很容易 给任何其它机器（ 的移植）。难：学习后知识库发生了什么变化，系统功能的变化的

。

归纳学习：现有的归纳推理只保证假，不保证真，归纳是从特殊到一般。演绎推理保真。而且，归纳的结论是无限多的，其中相当多是

，给生成的知识带来不可靠性。如“麻雀会飞”,“燕子会飞”等归纳“鸟会飞(鸵鸟不会飞)”。

“万有引力”归纳学习依赖于经验数据,因此又称为经验学习。机器目前很难观察什么重要、什么有意义。机器学习—概述4、为什么要研究机器学习？

实现的

：实现一个具有自主学习的系统，很难。机器学习—概述

5、发展历史

人工智能的发展历 看机器学习人工智能研究处于“推理期”，给机器赋予逻辑推理能力，机器就能具有智能。有A.

Newell和H.

Simon的“逻辑理论家”

序以及此后的“通用问题求解”

序等，

“逻辑理论家” 序在1952年证明了著名数学家

（Bertrand

Russell，1872—1970）和

的名著《数学原理》中的38条定理，在1963年证明了全部的52条定理，而且定理2.85甚至比

和

证明得更巧妙。A.Newell和H.

Simon因此获得了1975年

。

20世纪70年代中期开始，人工智能进入了“知识期”，E.A.

Feigenbaum作为“知识工 之父在1994年获得了

。机器学习—概述

5、发展历史

人工智能的发展历

看机器学习

20世纪50年代，主要集中在基于神经网络的连接主义学习方面，代表性工作主要有F.Rosenblatt的感知机、B.Widrow的Adaline系统等，20世纪6、70年代，以决策理论为基础的统计学习技术以及强化学习技术等得到发展，代表性工作有A.L.

Samuel的跳棋 序以及N.J.Nilson的“学习机器”等，20多年后红极一时的统计学习理论，在这一时期，基于逻辑或图结构表示的符号学习技术也开始出现，代表性工作有P.Winston的“结构学习系统”、R.S.

Michalski等人的“基于逻辑的归纳学习系统”、E.B.

Hunt等人的“概念学习系统”等。机器学习—概述

5、发展历史

人工智能的发展历

看机器学习

“它使得任何人离任何问题的答案之间的距离只有点击一下鼠标这么远”2004年3月，在斯坦福大学的参DARPA（国防部先进研究计划局）组织的自动驾驶车辆竞赛中，，成功地在7小时内走完了212公里路机器学习—概述

5、发展历史

神经系统模型和决策理论50年

始。其特点是对开始与无初始结构和面向作业知识的通用学习系统感

。包括构造多种具有随机或部分随机的初始结构的基于神经模型的机器。这些系 般称为神经网络或自组织系统。由于当时计算机技术状态，多停留在理论和硬件上。这些元件类似于神经元，他们实现简单的逻辑功能。………机器学习—概述

5、发展历史

神经系统模型和决策理论1965年左右，神经网络经验模式导致了模式识别这一新学科以及机器学习的决策理论方法。这种方法中学习就是从给定的一组经过选择的例子中获得判断函数，有线性的、多项式的、或相关的形式。当时，Samuel( 1959-1963)的跳棋序是最著名的成功的学习系统之一。达到了跳棋大师的水平。机器学习—概述

5、发展历史

符号概念获取1975年左右

。这类学习过通过分析一些概念的正例和反例构造出这些概念的符号表示。表示的形式一般是逻辑表达式、决策树、产生式规则或语义网络。代表有Winston（顿）的ARCH系统。机器学习—概述

5、发展历史

知识加强和论域 学习此方法是70年代中期开始，沿着符号主义路线进行的。在原有基础上逐步加强、侧重于专业的 性。强调使用面向任务的知识和它对学习过 的引导作用。系统包括预先确定的概念、知识结构、论域约束、启发式规则和论域有关的变换。系统在开始并不具有所有的属性或概念，在学习过 中系统应得到一些新的属性或概念。没有 学习方法。许多系统体现出上述途径的组合。机器学习—概述

5、发展历史

机器学习进入新阶段的重要表现：（近十年）（1）

机器学习已成为新的边缘科学并在高校形成一门课它综合应用心理学、生物学和神经生理学以及数学、自动化和计算机科学形成机器学习理论基础。机器学习—概述

5、发展历史

机器学习进入新阶段的重要表现：（近十年）（2）结合各种学习方法，取长补短的多种形式的集成学习系统的研究正在兴起。特别是连接学习，符号学习的耦合可以更好地解决连续性信号处理中知识与技能的获取与求精问题而受到重视。机器学习—概述

5、发展历史

机器学习进入新阶段的重要表现：（近十年）（3）机器学习与人工智能各种基础问题的统一性观点正在形成。如通用问题求解例如：学习与问题求解结合进行，知识表达便于学习的观点产生了通用智能系统的组块学习。类比学习与问题求解结合的基于案例学习已成为经验学习的重要方向。机器学习—概述分析学习用于设计综合性

系统。遗传算法与强化学

工 控制中有较好的应用前景。与符号系统耦合的神经网络连接学习将在企业的智能管理与智能机器人运动规划中发挥作用。

5、发展历史

机器学习进入新阶段的重要表现：（近十年）（4）各种学习方法的应用范围不断扩大，一部分已形成商品。归纳学习的知识获取工具已在

分类性

系统中广泛应用。连接学 声、图、文识别中占优势。机器学习—概述

5、发展历史

机器学习进入新阶段的重要表现：（近十年）（5）与机器学习有关的学术活动空前活跃。国际上除每年一次的机器学习研究会外，还有计算机学习理论会议及遗传算议。机器学习

—

概述

6、机器学习模型

学习是建立理论、形成假设和进行归纳推理的过

整个过包括：信息的、知识的处理两部分环境学习环节知识库执行环节机器学习

—

概述

7、分类：按学习策略

机械式学习，直接输入新知识（学习）学习者不需要进行任何推理或知识转换，将知识直接装进机器中。

根据示教学习（传授学习、指点学习）从老师或其它有结构的事物获取知识。要求学习者将输入语言的知识转换成它本身的内部表示形式。并把新的信息和它原有的知识有机地结合为一体。……….机器学习

—

概述……….

通过类推学习（演绎学习）学习者找出现有知识中所要产生的新概念或技能十分类似的部分。将它们转换或扩大成适合新情况的形式，从而取得新的事实或技能。

从例子中学习（归纳学习）给学习者提供某一概念的一组正例和反例，学习者归纳出一个总的概念描述，使它适合于所有的正例且排除所有的反例。（目前研究较多的

法）……….而实现类比机器学习

—

概述……….

类比学习演绎学习与归纳学习的组合。匹配不同论域的描述、确定公共的结构。以此作为类比的基础。例如对原子中的原子核认识推广到系行星的认识。总之，寻找公共子结构是归纳推理，是

演绎推理

。机器学习

—

概述

8、研究目的

希望得到通用的算法

研究了解学习知识的模型、认知模型

解决实际问题的知识库与系统，达到工

目标

研究特点

不可

性第六章机器学习

概述

实例学习

基于解释的学习

决策树学习

神经网络学习第六章机器学习

概述

实例学习

基于解释的学习

决策树学习

神经网络学习实例学习

概述

50年代兴起的实例学习是归纳学习的一种。目前实例学

某些系统中的应用已成为机器学习实践的先导。

环境提供给系些特殊的实例，这些实例事先由施教者划分为正例和反例。实例学习系统由此进行归纳推理得到一般规则。例如“狗”,“桥”等概念的建立。

环境提供给学习环节的正例和反例是低水平的信息，这是特殊情况下执行环节的行为。学习环节归纳出的规则是高水平的信息，可以在一般情况下用这些规则指导执行环节的工作。实例学习

实例学习的两个空间模型例子空间规则空间选择例子解释例子(例化)(泛化)现象（实例）本质（概念）“狗”实例学习例子空间规则空间选择例子解释例子(例化)取实例空间为所有的人。、(泛化)、}“

”“科学家”“中国科学家”,“？？？”,已故名人、现象（实例）本质（概念）、、，正例集={

、

、反例集={逊，

，}、，实例学习－两个空间模型例：取实例空间为所有的人。、张，正例集={

、

、

、光斗}反例集={

、

、

、，

}学到的概念可以 人”,或“科学家”,“中国科学家”，等。而中国当代科学家，名人、已故名人、

、曾在20世纪生活过的人，等是不可能学到的。学到的概念可能是不唯一的，除非正例集和反例集加起来正好等于整个实例空间。实例学习－两个空间模型

描述

例子空间的描述语言可以描述所有例子；规则空间的描述语言可以描述所有规则。

例如：纸牌，同花5张正例：集合{(2,c),(3,c),(5,c),(J,c),(A,c)},其中c，草花club规则：描述一手牌的全部谓词表达式的集合。符号：SUIT(花色)，RANK（点数）常量：A,

2,3,…,10.

J,Q,K,

clubs(草花),diamonds(方块),hearts（红桃）,spades(黑桃)合取连接词∧，存在量词所以有规则：对c1,c2,c3,c4,c5

c1

c2

c3

c4

c5(SUIT(c1,

*)∧SUIT(c2,

*)∧SUIT(c3,

*)∧SUIT(c4,*)∧SUIT(c5,*)

)实例学习－两个空间模型

例子空间

示教例子的质量：不能有错，同时提供正例和反例，逐步分批由选择地送入。

选择的条件：最有力地划分规则空间；证实肯定假设规则的集合；否定假设规则的集合。实例学习－两个空间模型

解释例子（泛化）

解释例子的目的是从例子中提出用于搜索空间的信息。把示教例子变换成易于进行符号归纳的形式。（有时很难）

例如：Winston的积木世界中的“拱”的概念。BCA实例学习－两个空间模型

规则空间（最根本，真正学习的部分）

定义：一套符号来规定表示规则的算符、术语，所有的描述都在其中。

归纳方法：从特殊到一般的推理常量化为变量。从几个正例中找到共性的部分改成变量。去掉条件。同上例。去掉牌点数这个条件增加选择（析取）。例有人脸的牌。从RANK(c1,J),RANK(c2,K)推出还有RANK(c3,Q)曲线拟合。几组值，解方

或用最小二乘法拟

一条曲线或曲面。实例学习－两个空间模型（规则空间）不管是去掉还是增加，都是扩大范围。把已有的知识总结归纳推广。但是越快越强的方法越容易出错。原因是归纳推理方法是保假不保真。实际上没有很严格的具体方法。因此，用归纳方法的过就是搜索过找到包含在少数例子中的正确信息。归纳出错就要回溯。要经常检验，用新例子去否定归纳出的错误规则。即解释例子和选择例子的反复，反复于例子空间和规则空间之间。实例学习－两个空间模型（规则空间）

对规则空间的要求规则空间表达能力与规则空间搜索难度。

谓词才可以增减；有状态空间才能拟合。不同的归纳方法要求不同

的规则表示方法。如果规则空间描述的语言的表达能力较

弱，可以使用的归纳方法就比较少，规则空间的搜索范围

就比较小，搜索就比较容易。但解决的问题就较少。因此，设计是在规则空间表达能力与规则空间搜索难度之间进行

权衡。表示与例子的一致。如相差很大，解释例子和选择例子的过

就很复杂。引入新术语（规则空间）。当表示语言不能描述学习过中产生的新状态时，要产生新的术语。实例学习－两个空间模型（规则空间）

搜索规则空间的方法最终的目的是为了搜索，先建立一个假设空间，在其中进行搜索。搜索方法：怎样改进假设规则集，以便求得要求的规则。变形空间法Version-space：数据驱动改进假设法Hypothesis-refinement：数据驱动产生与测试Generate

and

Test：模型驱动方案示例法Schema

Instantiation：模型驱动

选择例子。选择合适的例子，以能更好的搜索。实例学习

实例学习的分类（三种分类）搜索方法、论域、任务复杂

（1）按搜索方法分类：变形空间法；改进假设法；产生与测试法；方案示例法等等。

（2）按论域分类：系统理论和模式分析数字表示：多用于电子工知识：多项式、矩阵；系统：自适应系统；任务：模式分类、自适应控制、滤波等。符号表示：AI领域主要研究对象。知识：符号的特征向量、一阶谓词、产生式规则、语义网络、框架理论、多项式等；实例学习－实例学习的分类

（3）按任务复杂

度分类：学习单个概念：最基本的学习多个概念：归纳出多个相互独立的概念学习执行多步任务：一个操作序列去完成任务，即执行环节对任务要规划。实例学习

学习单个概念

概念：采用谓词逻辑的知识表示时，一个概念就是一个谓词公式。学习单个概念就是给系个概念的若干正例和反例，系统由此归纳出表示这个概念的谓词公式。

过给定：概念的表示语言；正例和反例寻找：一条规则。要覆盖全部正例，可以不覆盖全部反例。概念学习例子目标概念：“适于运动员进行水上运动项目的天气情况”，表示为

函数EnjoySport任务目的：基于某天的有关属性，EnjoySport函数的值任务的学习空间：样例集，每个样例表示为属性的集合实例学习

目标概念c

训练样例x

训练样例集D={x1,x2,...xn}

正例（yes），目标概念成员

反例(no)，非目标概念成员

假设h

假设（空间）集H={h1,h2...hn}机器学习的目标就是寻找一个（组）假设h，使得对所有的训练样例x，都有h(x)=c(x)

假设与概念一致实例学习-术语定义目标概念EnjoySport的训练样例ExampleOutlookAirTempHumidityWindWaterForecastEnjoySportDay

1SunnyWarmNormalStrongWarmSameYesDay

2Day

3SunnyRainyWarmColdHighHighWeakStrongWarmWarmSameChangeYesNoDay

4SunnyWarmHighStrongCoolChangeYesDay

5RainyWarmNormalWeakWarmChangeNo训练样例集

D={Day1,Day2,...Dayn}

每个训练样例

x有六个属性实例学习实例学习

表示假设的形式

一个简单的形式，具体实例的各属性约束的合取式

令每个假设为6个约束（或变量）的向量，每个约束对应一个属性可取值范围，可以为？任意本属性可接收的值明确指定的属性值；如Cold，High，strong

，weak。

不接受任何值样例都是反例，任何条件都满足不了

假设的例子<?,

?,

?,

?,

?,

?><

,

,

,

,

,

>//所有的样例都是正例，没有指定任何条件//所有的样例都是反例，任何条件都满足不了<Sunny,Warm,?,?,?,?> //阳光灿烂，气温高<Sunny,

Warm,

High,?,

?,

?><?,

Cold,

High,

?,

?,

?>//阳光灿烂，气温高，湿度偏高//气温冷，湿度偏高EnjoySport概念学习的任务

已知

实例x每个实例x由6个属性描述，每个属性的取值范围已确定

假设集H每个假设h描述为6个属性的取值约束的合取

目标概念c函数，变量为实例

训练样例集D目标函数（或目标概念）的正例和反例

求解

H中的任一假设h，使对于任意实例x，h(x)=c(x)实例（归纳）学习过

实例学习

从特殊的训练样例中得到普遍的规律

归纳

保证输出的假设能与训练样例相拟合

归纳假设的一个基本假定（偏置）

对于未见实例最好的假设就是与训练数据最佳拟合的假设

归纳学习假设

任一假设如果在足够大的训练样例集中很好地近目标函数，它也能在未见实例中很好地近目标函数。假设从一般到特殊的转化

假设的一般到特殊

考虑下面两个假设h1=<sunny,

?,

?,

Strong,

?,

?>h2=<Sunny,

?,

?,

?,

?,

?>h3=<Sunny,

?,

?,

,

?,

?>

任何被h1划分为正例的实例都会被h2划分为正例，因此h2比h1更一般(h1比h2更特殊)。

利用这个关系，无需列举所有假设，就能在无限的假设空间中进行彻底的搜索假设从一般到特殊的转化（2）

关系“更一般”的精确定义

任给实例x和假设h，x满足h，当且仅当h(x)=1

令hj和hk是在X上定义的 函数，称hj比hk更一般，当且仅当(xX)[(hk(x)=1)(hj(x)=1)]

记为hjmore_general_than_or_equal_tohk，或hj

g

hk显然“g

“是一种关系中的一类“偏序关系”。（自反、 称、可传递；在某一集合上可能存在四类八种特殊元素）称性假设从一般到特殊的转化（3）

“更一般”的严格情形hj

>g

hk，当且仅当，(hj

g

hk)

(hk

g

hj)

“更特殊”关系的定义hj

g

hk，当且仅当，hk

g

hj

以EnjoySport为例说明上面的定义hk=<sunny,

?,

?,

Strong,

?,?>hj

=<Sunny,?,

?,

?,

?,

?>hj

>g

hkhk

g

hjhj

“更一般”hkhk“更特殊”hjx1x1

=<sunny,

warm,high,

Strong,

warm,

same>high,

weak,

warm,

same>x2=<

sunny,

cold,….….实例、假设与更一般实例X假设集Hx3h2h3h1x2h2“更一般”h13h

==<sunny,

?,?,

?,

?,

?>h1=<sunny,

?,?,

?,cool,

same>h2=<sunny,

?,?,

?,cool,

?>h3

“更一般”h2h3

“更一般”h1实例学习的方法Find-S算法：寻找极大特殊假设（1）

使用more_general_than偏序的搜索算法

从H中最特殊假设(最小假设)开始，然后在假设覆盖正例失败时将其一般化Find-S算法1.2.3.将h初始化为H中最特殊假设对每个正例x对h的每个属性约束ai如果x满足ai,那么不做任何处理否则将h中ai替换为x满足的另一个更一般约束输出假设hFind-S：寻找极大特殊假设（2）

Find-S算法在例子EnjoySport上的应用

h<,

,

,

,

,

>最特出假设

h<Sunny,Warm,Normal,Strong,Warm,Same>

泛化

h<Sunny,Warm,?,Strong,Warm,Same>

泛化

遇到反例，h不变（因为h已经能够正确地识别反例）

h<Sunny,

Warm,

?,

Strong,

?,

?>极大特殊假设ExampleOutlookAirTempHumidityWindWaterForecastEnjoySportDay

1SunnyWarmNormalStrongWarmSameYesDay

2Day

3SunnyRainyWarmColdHighHighStrongStrongWarmWarmSameChangeYesNoDay

4SunnyWarmHighStrongCoolChangeYesDay

5RainyWarmNormalWeakWarmChangeNo实例X假设集Hx2x1h0h1特殊一般x3h4x4Find-S：寻找极大特殊假设x1=<sunny,

warm,

normal,

strong,

warm,

same>,

+x2=<sunny,

warm,

high,

strong,

warm,

same>,

+x3=<rainy,

cold,

high,

strong,

warm,

change>,

-x4=<sunny,

warm,

high,

strong,

cool,

change>,

+h0=<

,

,

,

,

,

>h1=<sunny,

warm,

normal,

strong,

warm,same>h2=<sunny,

warm,

?,

strong,

warm,

same>h3=<sunny,

warm,

?,

strong,

warm,

same>h4=<sunny,

warm,

?,strong,

?,

?>h2

,h3Find-S：寻找极大特殊假设（3）

Find-S算法演示了一种利用more_general_than偏序来搜索假设空间的方法，沿着偏序链，从较特殊的假设逐渐转移到较一般的假设。因此，每一步得到的假设都是在那一点上与训练样例一致的最特殊的假设。

Find-S的重要特点：对以属性约束的合取式描述的假设空间H，保证输出为H中与正例一致的最特殊的假设。

存在的问题?

是否收敛到了正确的目标概念？（还有其它假设吗？）

为什么要用最特殊的假设？（为什么不用更一般？）

训练样例是否相互一致？学习方法的健壮性（数据有噪声）

如果有多个极大特殊假设怎么办？多概念下的学习？实例学习的方法：变型空间和候选消除算法

候选消除算法概述

概念学习的另

法，候选消除算法（Candidate-Elimination）

Find-S算法的不足，输出的假设只是H中能够拟合训练样例的多个假设中的一个；

候选消除算法输出与训练样例一致的所有假设的集合；

候选消除算法在描述这一集合时不需要明确列举所有成员；

利用more_general_than偏序结构，可以 一个一致假设集合表示；

候选消除算法可用于启发式搜索控制规则来表示;

候选消除算法的缺点，容错性能差;变型空间和候选消除算法

“一致”的定义

一个假设h与训练样例集合D一致，当且仅当对D中每一个样例<x,c(x)>都有h(x)=c(x)，即：Consistent(h,D)(<x,c(x)>D)h(x)=c(x)“一致”与“满足”的关系；

变型(版本)空间VS（Version

Space）

与训练样例一致的所有假设组成的集合

表示了目标概念的所有合理的变型(版本)

关于H和D的变型空间，记为VSH,D，是H中与训练样例D一致的所有假设构成的子集：VSH,D={hH|Consistent(h,D)}变型空间和候选消除算法

先列表后消除法能表示变型空间的

法是列出其所有成员；

变型空间VS

包含H中所有假设的列表；

对每个训练样例<x,c(x)>，从变型空间中移除所有h(x)c(x)的假设；

输出VS中的假设列表；

优点

保证得到所有与训练数据一致的假设；

缺点

非常繁琐地列出H中的所有假设，大多数实际的假设空间无法做到。变型空间和候选消除算法

全部六个假设的变型空间变型空间及一般特殊边界{<Sunny,

Warm,

?,

Strong,

?,

?>}S:{<Sunny,

?,

?,

?,

?,

?>,

or <?,

Warm,

?,

?,

?,

?>}G:<Sunny,?,?,Strong,?,?><Sunny,

Warm,?,?,?,?><?,Warm,?,Strong,?,?>极大一般极大特殊寻找到的极大特殊假设：h4=<sunny,

warm,

?,strong,

?,

?>S={h4,

…}G={h…}变型空间和候选消除算法

变型空间的更简洁表示

变型空间被表示为它的极大一般g和极大特殊s的成员；

这些成员形成了一般和特殊边界的集合，这些边界在整个偏序结构中划分出变型空间；gsVSH,D变型空间Version

Space训练例子GS更特殊更一般VSH,D变型空间方法以整个规则空间为初始的假设规则集合H,VSH,D=H。依据训练例子中的信息，它对集合H进行泛化或特化处理，逐步缩小集合H。最后使H收敛为只含有要求的规则。由于被搜索的空间H逐步缩小，故称为变型空间。变型空间方法的初始G集是最上面的一个点（最一般的概念），初始S集是最下面的直线上的点（训练正例），初始H集是整个规则空间。在搜索过

中，G集逐步下移（进行特例化），S

集逐步上移（进行泛化），H

逐步缩小。最后H收敛为满足要求的概念。初始变型空间(x

y)(sm

y)(lg

y)(x

squ)(x

cir)(x

tri)(sm

squ)(lg

squ)(sm

cir)(lg

cir)(sm

tri)(lg

tri)例化泛化gs第一个训练实例(sm

cir)(x

y)(sm

y)(lg

y)(x

squ)(x

cir)(x

tri)(sm

squ)(lg

squ)(sm

cir)(lg

cir)(sm

tri)(lg

tri)第二个训练实例(lg,tri)(x

y)(sm

y)(lg

y)(x

squ)(x

cir)(x

tri)(sm

squ)(lg

squ)(sm

cir)(lg

cir)(sm

tri)(lg

tri)第三个训练实例(lg,cir)(x

y)(sm

y)(lg

y)(x

squ)(x

cir)(x

tri)(sm

squ)(lg

squ)(sm

cir)(lg

cir)(sm

tri)(lg

tri)变型空间和候选消除算法

搜索：使用一个可能合理的假设规则的集合

H，H是规则空间的子集，是规则空间中间的一段。

H中最一般的元素组成的子集称为G集合，最特殊的元素组成的子集称为S集合。（H是上界G和下界S之间的一段。）

学习基本思想：尽可能合理的进行特殊化和一般化处理，通过搜索减小H，找到一个假设规则。

具体方法：消除候选元素法。变型空间和候选消除算法

形式化定义

极大一般:更一般中的极大者(元)-下确界

极大特殊:更特殊中的极小者(元)-上确界

关于假设空间H和训练数据D的一般边界G，是在H中与D相一致的极大一般成员的集合

关于假设空间H和训练数据D的特殊边界S，是在H中与D相一致的极大特殊成员的集合变型空间和候选消除算法变型空间定理：令X为一任意的实例集合，H为X上定义的布尔假设的集合。令c:X{0,1}为X上定义的任一目标概念，并令D为任一训练样例集合{<x,c(x)>}。对所有的X,H,c,

D以及定义的S和G：VSH,D={hH|(sS)(

gG)(gghgs)}变型空间中的任意假设h一定更一般特殊边界S而更特殊一般边界G变型空间和候选消除算法

将G集合初始化为H中极大一般假设G0=｛<,,,,,>｝

将S集合初始化为H中极大特出假设S0=｛<?,?,?,?,?,?>｝候选消除算法（candidate-elimination

）

初始化G和S

如果d是一个正例从G中移去所有与d不一致的假设对S中每个与d不一致的假设s从S中移去s把s的所有的极小一般（泛化）式h加入到S中，其中h满足h与d一致，而且G的某个成员比h更一般

如果d是一个反例从S中移去所有与d不一致的假设对G中每个与d不一致的假设g从G中移去g把g的所有的极小特殊式（例化）h加入到G中，其中h满足h与d一致，而且S的某个成员比h更特殊ExampleOutlookAirTempHumidityWindWaterForecastEnjoySportDay

1SunnyWarmNormalStrongWarmSameYesDay

2Day

3SunnyRainyWarmColdHighHighStrongStrongWarmWarmSameChangeYesNoDay

4SunnyWarmHighStrongCoolChangeYes变型空间和候选消除算法算法举例，训练样例day1,day2,正例,只修改S对于样例day1,极小一般（泛化）式h加入到S中对于样例day2,极小一般（泛化）式h加入到S中对于样例day1

，day2,G不做变化极大一般极大特殊{<sunny,

warm,

normal,

strong,

warm,

same>}s1s2{<sunny,

warm,

?,

strong,

warm,

same>}G1

G2{<rainy,

cold,

high,

strong,

warm,

change>}specificExampleOutlookAirTempHumidityWindWaterForecastEnjoySportDay

1SunnyWarmNormalStrongWarmSameYesDay

2Day

3SunnyRainyWarmColdHighHighStrongStrongWarmWarmSameChangeYesNoDay

4SunnyWarmHighStrongCoolChangeYes变型空间和候选消除算法训练样例day3,反例,只修改G对于样例day3,S不做修改对于样例day3,

g的所有极小特殊式（例化）h加入到G中极大一般极大特殊{<sunny,

warm,

?,

strong,

warm,

same>}s1G3s2G2{<?,

?,

?,

?,

?,

?>}{<sunny,

?,

?,

?,

?,

?>,

<?,

warm,

?,

?,

?,

?>,

<?,

?,

?,

?,

?,

same>}ExampleOutlookAirTempHumidityWindWaterForecastEnjoySportDay

1SunnyWarmNormalStrongWarmSameYesDay

2Day

3SunnyRainyWarmColdHighHighStrongStrongWarmWarmSameChangeYesNoDay

4SunnyWarmHighStrongCoolChangeYes变型空间和候选消除算法训练样例day4,正例,只修改S对于样例day4,G不做修改对于样例day4,极小一般（泛化）式h加入到S中{<sunny,

warm,

?,

strong,

warm,

same>

}{<sunny,

?,

?,

?,

?,

?>,

<?,

warm,

?,

?,

?,

?>,

<?,

?,

?,

?,

?,

same>}s3{<sunny,

warm,

?,

strong,

?,

?

>}s4G3{<sunny,

?,

?,

?,

?,

?>,<?,

warm,

?,

?,

?,?>

}G4极大一般极大特殊变型空间和候选消除算法学习得到的最终的变形空间{<Sunny,

Warm,

?,

Strong,

?,

?>}S:{<Sunny,

?,

?,

?,

?,

?>, <?,

Warm,

?,

?,

?,

?>，<?,

?,

?,

?,

?,

same>}G:<Sunny,?,?,Strong,?,?><Sunny,Warm,?,?,?,?><?,Warm,?,Strong,?,?>极大一般极大特殊

学习的过和结论S是规则充分条件，G是规则必要条件的集合。学习结束时找到的应是充分必要条件。正例的主要工作是对S一般化，反例是对G特殊化。搜索的过是在例子的引导下，数据驱动。遵循的是变量优先的原则。正例去掉G中不符合的概念，然后修改S,归纳出最特殊的结果,尽量少改S。反例去掉S中符合的概念，然后修改G,做特殊化得到最一般的结果,尽量少改G.GS更特殊更一般VSH,D

变形空间法的优缺点：搜索空间太大，有可能引起计算

问题（规则总地来说是越扩越多）性差，所有数据驱动方法的通病。解决方法：例子一组一组地给。采用析取规则，即此算法不可能发现“或”的关系。归纳偏置

有关候选消除算法的几个问题

如果目标概念不在假设空间中怎么办？

是否可设计一个包含所有假设的空间来解决这一？

假设空间的大小对于算法推广到未见实例的能力有什么影响？

假设空间的大小对所需训练样例的数量有什么影响？归纳学习需要的预先假定，称为归纳偏置归纳偏置（2）

一个有偏的假设空间

在EnjoySport这个例子中，假设空间限制为只包含属性值的合取。（肯定有偏）

因为这一限制，导致假设空间不能够表示简单一些的析取形式的目标概念。归纳偏置（3）无偏的学习器

为了保证目标概念在假设空间中，需要提供一个假设空间，它能表达所有的可教授概念。换言之，它能表达实例集X的所有子集。EnjoySport的无偏形式

带来的问题：概念学习算法无法从训练样例中泛化。

要想获得单个目标概念，就必须提供X中所有实例作为训练样例归纳偏置（4）

无偏学习的无用性

归纳学习的一个基本属性：学习器如果不对目标概念的形式做预先的假定，它从根本上无法对未见实例进行分类实例学习的改进

改进假设方法

也是数据驱动的方法。用改进操作来修改规则空间中的假设。然后根据示教例子用启发式方法选择这些操作。

优点：能发现实质变量间关系

缺点：仅能在特殊情况下才能使用操作。变量的选样，对例子的提供很敏感实例学习的改进

产生与测试方法

模型驱动的方法。

优点：比变形空间法更快，量更少，抗干扰。即使例子中有干扰，就选覆盖大多数例子的规则即可。

缺点：没有很完善的模型指导修剪和结束搜索。同时，因为修剪所以不完备，不一定能找到全部合格的概念。而且一次需要全部例子，不适合于逐步学习。实例学习的改进

方案示例方法

模型驱动的方法。常用于理解性任务。如：图像、语音、自然语言理解。

优点：可以很快找到要求规则， 性好

缺点：难以划分出几种方案。有的规则不能被现有的方案覆盖。每个方案要专门研究，使用不同的解释方法。实例学

结

概念学习可看作搜索预定义潜在假设空间的过

假设的一般到特殊偏序结构可以定义在任何概念学习问题中，这种结构便于假设空间的搜索；

Find-S算法使用一般到特殊序关系，在偏序结构的一个分支上执行一般到特殊搜索，寻找一个与样例一致的最特殊假设；

候选消除算法利用一般到特殊的过通过渐进地计算极大特殊假设集合S和极大一般假设集合G发现变型空间；

候选消除算法缺少健壮性；

归纳学习算法隐含了归纳偏置，候选消除算法的偏置是：目标概念可以在假设空间中找到-所以又称限定偏置。输出的假设和对新实例的分类可由归纳偏置和训练样例演绎推出。第六章机器学习

概述

实例学习

基于解释的学习

决策树学习

神经网络学习第六章机器学习

概述

实例学习

基于解释的