机器学习--概念学习和一般到特殊资料课件

2024/7/11第第2章章 概念学习和一般到特殊序概念学习和一般到特殊序n2.12.1简介简介n2.22.2概念学习任务概念学习任务n2.32.3作为搜索的概念学习作为搜索的概念学习n2.4Find2.4FindS S：寻找极大特殊假设：寻找极大特殊假设n2.52.5变型空间和候选消除算法变型空间和候选消除算法n2.62.6关于变型空间和候选消除算法的说明关于变型空间和候选消除算法的说明n2.72.7归纳偏置归纳偏置n2.82.8小结小结2024/7/122.12.1简介简介n 概念：概念：每个概念可被看作一个每个概念可被看作一个对象或事件集合对象或事件集合。它是从更大的集合中选取的子集它是从更大的集合中选取的子集(如从动物的集合中如从动物的集合中选取鸟类选取鸟类)或者是在较大集合中定义的布尔函数或者是在较大集合中定义的布尔函数(如在动物集合如在动物集合中定义的函数，它对鸟类产生中定义的函数，它对鸟类产生truetrue并对其他动物产生并对其他动物产生false)false)。n归纳学习归纳学习：从特殊的训练样例（关于某概念的正例和：从特殊的训练样例（关于某概念的正例和反例）中归纳出一般的概念描述（函数），它的一般操反例）中归纳出一般的概念描述（函数），它的一般操作是作是泛化和特化泛化和特化。这也是。这也是机器学习的中心问题机器学习的中心问题。2024/7/132.2 2.2 概念学习任务概念学习任务n概念学习概念学习：是归纳学习的一种，指从有关某个布：是归纳学习的一种，指从有关某个布尔函数尔函数f f（未知）的输入输出训练样例中（未知）的输入输出训练样例中推断推断出该出该布尔函数布尔函数f f，或从样例中，或从样例中逼近逼近布尔函数布尔函数f f。n概念学习任务概念学习任务被描述为被描述为:实例的集合实例的集合X:X:由各种属性值确定的元组由各种属性值确定的元组候选假设候选假设H H的集合的集合实例集合上的目标函数实例集合上的目标函数c c（概念）（概念）训练样例的集合训练样例的集合D D2024/7/14目标概念EnjoySport的正例和反例Example Sky AirTemp Humidity Wind Water Forecast EnjoySport 1 Sunny Warm Normal Strong Warm Same Yes 2 Sunny Warm High Strong Warm Same Yes 3 Rainy Cold High Strong Warm Change No 4 Sunny Warm High Strong Cool Change Yes概念学习例：概念学习例：目标概念：目标概念：“AldoAldo进行水上运动的日子进行水上运动的日子”，即使，即使Enjoysport=YesEnjoysport=Yes的日子的日子日子的样例日子的样例（训练样例）：（训练样例）：2024/7/152.2 2.2 概念学习任务概念学习任务候选假设的形式：候选假设的形式：实例的各属性的合取式，每个属性可取值：实例的各属性的合取式，每个属性可取值：由由“?”表示任意本属性可接受的值表示任意本属性可接受的值明确明确指定的属性值指定的属性值(如如Warm)由由“”表示不接受任何值表示不接受任何值如：如：判定判定AldoAldo只在寒冷和潮湿的日子里进行水上运动只在寒冷和潮湿的日子里进行水上运动(并与其他属并与其他属性无关性无关)，这样的假设可表示为，这样的假设可表示为:最一般的假设最一般的假设是每一天都是正例，可表示为是每一天都是正例，可表示为:而而最特殊的假设最特殊的假设即每一天都是反例，表示为即每一天都是反例，表示为:已知已知:实例集实例集X X:可能的日子，每个日子由下面的属性描述可能的日子，每个日子由下面的属性描述:Sky(可取值为可取值为Sunny,Cloudy和和Rainy)AirTemp(可取值为可取值为Warm和和Cold)Humidity(可取值为可取值为Normal和和High)Wind(可取值为可取值为Strong和和Weak)Water可取值为可取值为Warm和和Cool)Forecast(可取值为可取值为Same和和Change)假设集假设集H H:每个假设描述为上述每个假设描述为上述6 6个属性的值约束的合取。约束可以个属性的值约束的合取。约束可以为为“?”，(表示接受任意值表示接受任意值)，“”(表示拒绝所有值表示拒绝所有值)，或一特，或一特定值。定值。目标概念目标概念c c:EnjoySport:X:EnjoySport:X0,10,1训练样例集训练样例集D D:目标函数的正例和反例目标函数的正例和反例求解求解:H H中的一假设中的一假设h h，使对于，使对于X X中任意中任意x,x,使使 h(x)=c(x)h(x)=c(x)EnjoySportEnjoySport概念学习任务概念学习任务2024/7/172.2.1 2.2.1 术语定义术语定义n概念定义在概念定义在实例实例集合之上，这个集合表示为集合之上，这个集合表示为X X，由其各属性，由其各属性的取值来确定。的取值来确定。n待学习的概念或函数称为待学习的概念或函数称为目标概念目标概念，记做，记做c c。c c是定义在实例是定义在实例集即集即X X上的任意布尔函数上的任意布尔函数c:Xc:X0,1 0,1。n训练样例训练样例为为X X中的一个实例中的一个实例x x以及它的目标概念值以及它的目标概念值c(x)c(x)。c(x)=1c(x)=1的实例称为的实例称为正例正例，或称为，或称为目标概念的成员目标概念的成员；c(x)=0c(x)=0的实例称为的实例称为反例反例，或称为，或称为非目标概念的成员。非目标概念的成员。训练样例用训练样例用 x c(x)表示，表示，训练样例集合用训练样例集合用D D表示。表示。n所有可能所有可能假设的集合假设的集合H H是为确定目标概念是为确定目标概念所考虑所考虑的范围。的范围。h h H H：X X 0,1 0,1，机器学习的目标机器学习的目标就是寻找一个就是寻找一个h h，使对所，使对所 有的有的x x，h(x)=c(x)h(x)=c(x)。2024/7/182.2.2 2.2.2 归纳学习假设归纳学习假设n归纳学习算法最多能归纳学习算法最多能保证保证输出的假设与训练数据相输出的假设与训练数据相拟合。（归纳保假，演绎保真）拟合。（归纳保假，演绎保真）n归纳学习假设归纳学习假设：任一假设如果在足够大的训练样例：任一假设如果在足够大的训练样例集中很好地逼近目标函数，它也能在未见实例中很集中很好地逼近目标函数，它也能在未见实例中很好地逼近目标函数好地逼近目标函数。2024/7/192.3 2.3 作为搜索的概念学习作为搜索的概念学习n概念学习可以看作是一个概念学习可以看作是一个搜索过程搜索过程，范围范围是假设所隐含定义是假设所隐含定义的整个空间。的整个空间。搜索的目标搜索的目标是为了寻找是为了寻找最好地拟合最好地拟合训练样例的训练样例的假设。假设。n按各属性的取值：按各属性的取值：实例集合实例集合包含包含322222=96322222=96种不同的实例；种不同的实例；假设空间假设空间包含包含544444=5120544444=5120种语法不同的假设；种语法不同的假设；而语义不同的假设只有而语义不同的假设只有1 1433333=973433333=973种。种。n假设空间假设空间搜索策略搜索策略感兴趣的是非常大或无限大的假设空间，感兴趣的是非常大或无限大的假设空间，以找到最佳拟合训练数据的假设。以找到最佳拟合训练数据的假设。2024/7/110假设的一般到特殊序假设的一般到特殊序两个实例：两个实例：h hl l=Sunny=?h h2 2=Sunny=?任何被任何被h hl l划分为正例的实例都会被划分为正例的实例都会被h h2 2划分为正例，因此，我们划分为正例，因此，我们说说h h2 2比比h h1 1更一般。更一般。定义定义:令令h hj j和和h hk k为在为在X X上定义的布尔函数。称上定义的布尔函数。称“h hj j和比和比h hk k更一般更一般”：h hj j more_general_than_or_equal_tomore_general_than_or_equal_to h hk k(记作记作h hj j g gh hk k)，当且仅当当且仅当(x x X X)(h)(hk k(x)=1)(x)=1)(h(hj j(x)=1)(x)=1)有必要考虑一假设严格地比另一假设更一般的情形：有必要考虑一假设严格地比另一假设更一般的情形：h hj j more_general_thanmore_general_than h hk,k,(记作记作h hj j g gh hk k)，当且仅当当且仅当h hj j g gh hk k)h hj j g gh hk k 最后，还可以定义逆向的关系最后，还可以定义逆向的关系“比比更特殊更特殊”为：为：h hj jmore_specific_thanmore_specific_than h hk,k,当且仅当当且仅当h hk k more_general_thanmore_general_than h hj j。2024/7/111实例、假设和实例、假设和more-general-than关系关系x1=x1=x2=x2=h1=h1=h2h2h3h32024/7/1122.4 FindS：寻找极大特殊假设：寻找极大特殊假设思路：思路：n从从H H中中最特殊假设最特殊假设开始，然后在该假设覆盖正例失败开始，然后在该假设覆盖正例失败时将其一般化时将其一般化(当一假设能正确地划分一个正例时，当一假设能正确地划分一个正例时，称该假设称该假设“覆盖覆盖”该正例该正例)。nFIND-SFIND-S算法简单地忽略每一个反例算法简单地忽略每一个反例!注意注意，这时假，这时假设设h h仍然与新的反例仍然与新的反例一致一致(即即h h能将反例正确地划分为能将反例正确地划分为反例反例)，因此不需要对，因此不需要对h h作任何更改。作任何更改。2024/7/1132.4 FindS：寻找极大特殊假设：寻找极大特殊假设Find-S算法算法1 1.将将h h初始化为初始化为H H中最特殊假设中最特殊假设2 2.对每个正例对每个正例x x（循环循环）对对h h的每个属性约束的每个属性约束a ai i 如果如果x x满足满足a ai i 那么那么不做任何处理不做任何处理 否则否则将将h h中中a ai i替换为替换为x x满足的更一般的约束满足的更一般的约束3 3.输出假设输出假设h h2024/7/114例例:假定给予学习器的一系列训练样例如表假定给予学习器的一系列训练样例如表2-12-1所示。所示。Example Sky AirTemp Humidity Wind Water Forecast EnjoySport 1 Sunny Warm Normal Strong Warm Same Yes 2 Sunny Warm High Strong Warm Same Yes 3 Rainy Cold High Strong Warm Change No 4 Sunny Warm High Strong Cool Change Yes2.4 FindS：寻找极大特殊假设：寻找极大特殊假设2024/7/1152.4 FindS：寻找极大特殊假设：寻找极大特殊假设例例:假定给予学习器的一系列训练样例如表假定给予学习器的一系列训练样例如表2-12-1所示。所示。nFIND-SFIND-S的第一步是将的第一步是将h h初始化为初始化为H H中最特殊的假设中最特殊的假设:h h n观察第一个训练样例时，它刚好是个正例，这时的观察第一个训练样例时，它刚好是个正例，这时的h h太特殊了。太特殊了。每个属性应该都被替换成能拟合该例的下一个更一般的值约束：每个属性应该都被替换成能拟合该例的下一个更一般的值约束：h h Sunny Samen第第2 2个训练样例个训练样例(仍然为正例仍然为正例)迫使该算法进一步将迫使该算法进一步将h h一般化。这一般化。这样假设变为样假设变为:h h Sunny Samen处理第处理第3 3个训练样例，这是一个反例，个训练样例，这是一个反例，h h不变。不变。n第第4 4个正例使得个正例使得h h更一般更一般:h h Sunny?2024/7/1162024/7/1172.4FindS：寻找极大特殊假设：寻找极大特殊假设 Find-SFind-S算法的算法的重要特点是重要特点是:对以属性约束的合取式描述的假设空间对以属性约束的合取式描述的假设空间(如，如，EnjoySportEnjoySport中中的的H),Find-SH),Find-S保证输出为保证输出为H H中与正例一致的最特殊的假设。中与正例一致的最特殊的假设。只只要正确的目标概念包含在要正确的目标概念包含在H H中，并且训练数据都是正确的，最终中，并且训练数据都是正确的，最终的假设也与所有反例一致。的假设也与所有反例一致。Find-SFind-S算法仍存在一些未算法仍存在一些未解决的问题解决的问题:学习过程学习过程是否收敛是否收敛到了正确的目标概念到了正确的目标概念?（还有其它假设？）（还有其它假设？）为什么要为什么要用最特殊的用最特殊的假设。（不用更一般的？）假设。（不用更一般的？）训练样例是否相互训练样例是否相互一致一致?（有噪声？）（有噪声？）如果有如果有多个极大特殊假设多个极大特殊假设怎么办怎么办?（可能会有多个）（可能会有多个）2024/7/1182.5 变型空间和候选消除算法变型空间和候选消除算法 概念学习的另一种途径即概念学习的另一种途径即候选消除候选消除(CANDIDATE-ELIMINATION)算法算法。能解决能解决Find-SFind-S中的若干不足中的若干不足之处。之处。Find-SFind-S输出的假设只是输出的假设只是H H中能够拟合训练样例的多个假设中的一个。而在候选消除算中能够拟合训练样例的多个假设中的一个。而在候选消除算法中，输出的是与训练样例一致的法中，输出的是与训练样例一致的所有假设所有假设的集合。的集合。值得值得注意注意的是，候选消除算法在描述这一集合时不需要明的是，候选消除算法在描述这一集合时不需要明确列举其所有成员。（而是用特殊和一般边界确定的一个假确列举其所有成员。（而是用特殊和一般边界确定的一个假设的集合）这也归功于设的集合）这也归功于more-general-thanmore-general-than偏序结构。偏序结构。2024/7/1192.5 变型空间和候选消除算法变型空间和候选消除算法一一.表示表示定义定义:一个一个假设假设h h与训练样例集合与训练样例集合D D一致一致，当且仅当对，当且仅当对D D中每一个样中每一个样例例都有：都有：h(x)=c(x)h(x)=c(x)即：即：Consistent(h,D)Consistent(h,D)(D)h(x)=c(x)D)h(x)=c(x)）注意注意:这里定义的这里定义的一致一致与前面定义的与前面定义的满足满足不同。一个样例不同。一个样例x x在在h(xh(x）1 1时称为时称为满足满足假设假设h h，不论，不论x x是目标概念的正例还是反例。然而，是目标概念的正例还是反例。然而，这一样例是否与这一样例是否与h h一致一致则与目标概念有关，即是否则与目标概念有关，即是否h(x)=c(x)h(x)=c(x)。候。候选消除算法能够选消除算法能够表示与训练样例一致的所有假设表示与训练样例一致的所有假设。定义定义:关于假设空间关于假设空间H H和训练样例集和训练样例集D D的的变型空间变型空间，标记为，标记为VSVSH,DH,D，是，是H H中与训练样例中与训练样例D D一致的所有假设构成的子集。一致的所有假设构成的子集。VSVSH,DH,Dhh H|H|Consistent(h,D)Consistent(h,D)2024/7/1202.5 变型空间和候选消除算法变型空间和候选消除算法 原则上，只要假设空间是有限的，就可使用列表后消除算原则上，只要假设空间是有限的，就可使用列表后消除算法。它具有很多优点，如能保证得到与训练数据一致的所有假法。它具有很多优点，如能保证得到与训练数据一致的所有假设。但是，这一算法要求非常繁琐地设。但是，这一算法要求非常繁琐地列出列出H H中所有假设中所有假设，这对，这对于大多数实际的假设空间是于大多数实际的假设空间是不现实的不现实的要求。要求。二二.列表后消除算法列表后消除算法1.1.变型空间变型空间VersionSpaceVersionSpace包含包含H H中中所有假设所有假设的列表的列表2.2.对对每个每个训练样例训练样例 从变型空间中移除所有从变型空间中移除所有h(x)h(x)c(x)c(x)的假设的假设h h3.3.输出输出VersionSpaceVersionSpace中的假设列表中的假设列表 2024/7/1212.5 变型空间和候选消除算法变型空间和候选消除算法三三.变型空间的更简洁表示变型空间的更简洁表示 为说明变型空间的这种表示，对于表为说明变型空间的这种表示，对于表2-1中给定的中给定的4个训个训练样例，练样例，FIND-S输出假设输出假设:h 实际上，这只是实际上，这只是H中与训练样例一致的所有中与训练样例一致的所有6个假设之一。个假设之一。2024/7/1222.5 变型空间和候选消除算法变型空间和候选消除算法全部全部六个假设的变型空间：六个假设的变型空间：变型空间及其一般和特殊边界集合变型空间及其一般和特殊边界集合2024/7/1232.5 变型空间和候选消除算法变型空间和候选消除算法定义定义:关于假设空间关于假设空间H H和训练数据和训练数据D D的一般边界的一般边界(general(general boundary)Gboundary)G，是在，是在H H中与中与D D相一致的相一致的极大一般极大一般(maximally(maximally general)general)成员成员的集合。的集合。定义定义:关于假设空间关于假设空间H H和训练数据和训练数据D D的特殊边界的特殊边界(specific(specific boundary)Sboundary)S，是在，是在H H中与中与D D相一致的相一致的极大特殊极大特殊(maximally(maximally specific)specific)成员成员的集合。的集合。2024/7/1242.5 变型空间和候选消除算法变型空间和候选消除算法定理定理2.1:2.1:变型空间表示定理变型空间表示定理 令令X为一任意的实例集合，为一任意的实例集合，H为为X上定义的布尔假设的上定义的布尔假设的集合。令集合。令c:X 0,1为为X上定义的任一目标概念，并令上定义的任一目标概念，并令D为为任一训练样例的集合任一训练样例的集合。对所有的。对所有的X,H,c,D以及良以及良好定义的好定义的S和和G:2024/7/125 使用变型空间的候选消除学习算法使用变型空间的候选消除学习算法将将G G集合初始化为集合初始化为H H中极大一般假设中极大一般假设 G G0 0=将将S S集合初始化为集合初始化为H H中极大特殊假设中极大特殊假设 S S0 0=对每个训练样例对每个训练样例d d，进行以下操作，进行以下操作:如果如果d d是一正例是一正例 从从G G中移去所有与中移去所有与d d不一致的假设不一致的假设 对对S S中每个与中每个与d d不一致的假设不一致的假设s s 从从S S中移去中移去s s 把把s s的所有的的所有的极小一般化式（泛化）极小一般化式（泛化）h h加人到加人到S S中，其中中，其中h h满足满足 h h与与d d一致，而且一致，而且G G的某个成员比的某个成员比h h更一般更一般 从从S S中移去所有这样的假设中移去所有这样的假设:它比它比S S中另一假设更一般中另一假设更一般如果如果d d是一个反例是一个反例 从从S S中移去所有与中移去所有与d d不一致的假设不一致的假设 对对G G中每个与中每个与d d不一致的假设不一致的假设g g 从从G G中移去中移去g g 把把g g的所有的的所有的极小特殊化式极小特殊化式h h加人到加人到G G中，其中中，其中h h满足满足 h h与与d d一致，而且一致，而且S S的某个成员比的某个成员比h h更特殊更特殊 从从G G中移去所有这样的假设中移去所有这样的假设:它比它比G G中另一假设更特殊中另一假设更特殊2024/7/126算法举例：算法举例：训练样例训练样例:1.,EnjoySport=Yes1.,EnjoySport=Yes2.,EnjoySport=Yes2.,EnjoySport=Yes 候选消除算法步骤候选消除算法步骤1 12024/7/1272.5 变型空间和候选消除算法变型空间和候选消除算法训练样例训练样例:3.Rainy,Cold,3.,EnjoySport=No,Change,EnjoySport=No 候选消除算法步骤候选消除算法步骤2 22024/7/1282.5 变型空间和候选消除算法变型空间和候选消除算法 训练样例训练样例:4.,EnjoySport=Yes4.,EnjoySport=Yes 候选消除算法步骤候选消除算法步骤3 32024/7/1292.5 变型空间和候选消除算法变型空间和候选消除算法 EnjoySport概念学习问题中的最终的变型空间概念学习问题中的最终的变型空间2024/7/1302.6关于变型空间和候选消除算法的说明关于变型空间和候选消除算法的说明一、候选消除算法是否会收敛到正确的假设一、候选消除算法是否会收敛到正确的假设 由候选消除算法得到的变型空间能够由候选消除算法得到的变型空间能够收敛到描述目标概念的假收敛到描述目标概念的假设的条件设的条件是是:(1)(1)在训练样例中没有错误。在训练样例中没有错误。(2)(2)H H中确实包含描述目中确实包含描述目标概念的正确假设。当标概念的正确假设。当S S和和G G边界集合边界集合收敛到单个的可确定的假设收敛到单个的可确定的假设时，时，目标概念才真正获得。目标概念才真正获得。如果如果训练数据中包含错误训练数据中包含错误,算法肯定会从变型空间中删除正确的目算法肯定会从变型空间中删除正确的目标概念。如果给定足够的训练数据，最终，我们会发现标概念。如果给定足够的训练数据，最终，我们会发现S S和和G G边界收边界收敛得到一个空的变型空间，从而得知训练数据有误。敛得到一个空的变型空间，从而得知训练数据有误。训练样例正确，但训练样例正确，但目标概念不能由假设表示方式所描述目标概念不能由假设表示方式所描述(比如目标比如目标概念是某几个属性特征的析取概念是某几个属性特征的析取)。目前，我们目前，我们只考虑只考虑样例数据是正确的并且目标概念确实在假设空样例数据是正确的并且目标概念确实在假设空间中。间中。2024/7/1312.6关于变型空间和候选消除算法的说明关于变型空间和候选消除算法的说明二、下一步需要什么样的训练样例二、下一步需要什么样的训练样例 学习器应试图在当前变型空间中选择假设，以进一步划分学习器应试图在当前变型空间中选择假设，以进一步划分该空间。因此，该空间。因此，需要选择的实例需满足需要选择的实例需满足:它能被变型空间中一些它能被变型空间中一些假设分类为正例，另一些分类为反例。其中一个这样的实例是假设分类为正例，另一些分类为反例。其中一个这样的实例是:SunnySame注意注意:这一实例满足变型空间的这一实例满足变型空间的6 6个假设中的个假设中的3 3个。如果施教者将个。如果施教者将实例划分为正例，变型空间的实例划分为正例，变型空间的S S边界就需要被一般化。相反，边界就需要被一般化。相反，G G边界需要被特殊化。无论哪种情况，边界需要被特殊化。无论哪种情况，机器将能够学到更多的知机器将能够学到更多的知识，识，以确定目标概念并将变型空间缩小到原来的一半。以确定目标概念并将变型空间缩小到原来的一半。一般来说，概念学习的一般来说，概念学习的最优查询策略最优查询策略，是产生实例以满足，是产生实例以满足当前变型空间中大约半数的假设。这样，变型空间的大小可以当前变型空间中大约半数的假设。这样，变型空间的大小可以在遇到每个新样例时减半，正确的目标概念就可在只用在遇到每个新样例时减半，正确的目标概念就可在只用loglog2 2l l VS|VS|次实验后得到。次实验后得到。2024/7/1322.6关于变型空间和候选消除算法的说明关于变型空间和候选消除算法的说明三、怎样使用不完全学习概念三、怎样使用不完全学习概念 机器现在要对未见过的实例进行分类。虽然目标概念还未完全机器现在要对未见过的实例进行分类。虽然目标概念还未完全学习到，但是仍然有可能对新样例进行一定可信度的分类。学习到，但是仍然有可能对新样例进行一定可信度的分类。待分类的新实例待分类的新实例Instance Sky AirTemp Humidity Wind Water Forecast EujoySport A Sunny Warm Normal Strong Cool Change?B Rainy Cold Normal Light Warm Same?C Sunny Warm Normal Light Warm Same?D Sunny Cold Normal Strong Warm Same?2024/7/1332.6关于变型空间和候选消除算法的说明关于变型空间和候选消除算法的说明注意，注意，实例实例A A不在训练样例中，但不在训练样例中，但当前变型空间中每个假设都将其当前变型空间中每个假设都将其分类为正例分类为正例。不管变型空间中哪个假设最终成为目标概念，它都会。不管变型空间中哪个假设最终成为目标概念，它都会将其划分为正例。将其划分为正例。实例实例B B被变型空间中的每个假设划分为反例（实例被变型空间中的每个假设划分为反例（实例B B不满足不满足G G中的所中的所有成员），所以这个实例可被放心地划分为反例。有成员），所以这个实例可被放心地划分为反例。实例实例C C的情况有所不同。变型空间中半数的假设划分其为正例，半的情况有所不同。变型空间中半数的假设划分其为正例，半数划分为反例。因此，学习器无法可信地分类这一样例，除非提供数划分为反例。因此，学习器无法可信地分类这一样例，除非提供更多的训练样例。更多的训练样例。实例实例D D在变型空间中被两个假设分为正例，被其他在变型空间中被两个假设分为正例，被其他4 4个假设分为反例。个假设分为反例。这个例子的分类可信度比实例这个例子的分类可信度比实例A A和和B B要小。投票选举要倾向于反例分要小。投票选举要倾向于反例分类，所以我们可以输出拥有最大票数的分类。类，所以我们可以输出拥有最大票数的分类。2024/7/134 2.7 2.7 归纳偏置归纳偏置 在给定在给定正确的训练样例正确的训练样例并且保证并且保证初始假设空间包含目标概初始假设空间包含目标概念念时，候选消除算法可以收敛到目标概念。时，候选消除算法可以收敛到目标概念。如果目标概念不在假设空间中怎么办如果目标概念不在假设空间中怎么办?是否可设计一个包含是否可设计一个包含所有假设的空间来解决这一困难所有假设的空间来解决这一困难?假设空间的大小对于算法推广到未见实例的能力有什么影响假设空间的大小对于算法推广到未见实例的能力有什么影响?假设空间的大小对所需训练样例的数量有什么影响假设空间的大小对所需训练样例的数量有什么影响?这些都是归纳推理中的一些基本问题。这里我们在候选消除这些都是归纳推理中的一些基本问题。这里我们在候选消除算法中考察这些问题。然而，此处分析中得到的结论可以应算法中考察这些问题。然而，此处分析中得到的结论可以应用于任意的概念学习系统。用于任意的概念学习系统。2024/7/135 2.7 2.7 归纳偏置归纳偏置一、一个有偏的假设空间一、一个有偏的假设空间 如果想保证假设空间包含目标概念，一个明显的方法是如果想保证假设空间包含目标概念，一个明显的方法是扩扩大假设空间大假设空间。使每个可能的假设都包含在内。使每个可能的假设都包含在内。再一次使用再一次使用EnjoySportEnjoySport这个例子，我们将假设空间限制为只包这个例子，我们将假设空间限制为只包含属性值的合取。由于这一限制，假设空间不能够表示最简单含属性值的合取。由于这一限制，假设空间不能够表示最简单的析取形式的目标概念，如的析取形式的目标概念，如“Sky=SunnySky=Sunny或或SkySkyCloudyCloudy”。实。实际上，如果给定以下三个训练样例，它们来自于该析取式假设，际上，如果给定以下三个训练样例，它们来自于该析取式假设，我们的算法将得到一个空的变型空间。我们的算法将得到一个空的变型空间。之所以不存在与这之所以不存在与这3 3个样例一致的假设的原因是，与前两个样例一个样例一致的假设的原因是，与前两个样例一致，并且能在给定假设空间致，并且能在给定假设空间H H中表示的最特殊的假设是中表示的最特殊的假设是:S S2 2:?:Change它将第它将第3 3个样例错误地划为正例。问题在于，我们使学习器偏向于个样例错误地划为正例。问题在于，我们使学习器偏向于只考虑合取的假设，这里需要表示能力更强的假设空间。只考虑合取的假设，这里需要表示能力更强的假设空间。2024/7/137 2.7 归纳偏置归纳偏置二、无偏的学习器二、无偏的学习器 为了保证目标概念在假设空间中，需要提供一个假设空间，为了保证目标概念在假设空间中，需要提供一个假设空间，它能表达所有的可教授概念它能表达所有的可教授概念(every teachable concept)(every teachable concept)。换。换言之，它言之，它能够表达实例集能够表达实例集X X的所有可能的子集的所有可能的子集。一般我们把集合。一般我们把集合X X的所有子集的集合称为的所有子集的集合称为X X的幂集的幂集。例如，在例如，在EnjoySportEnjoySport学习任务中，使用学习任务中，使用6 6种属性描述的实例空间种属性描述的实例空间X X的大小为的大小为9696。在这一实例空间上可定义。在这一实例空间上可定义2 29696，或大约是，或大约是10102828个不个不同的目标概念，这也是学习器所需要学习的目标概念数目。同的目标概念，这也是学习器所需要学习的目标概念数目。2024/7/138 2.7 归纳偏置归纳偏置二、无偏的学习器二、无偏的学习器 现在将现在将EnjoySportEnjoySport学习任务重新定义为一种无偏的形学习任务重新定义为一种无偏的形式。方法是定义一个新的假设空间式。方法是定义一个新的假设空间H H，它能表示实例的每，它能表示实例的每一个子集，也就是把一个子集，也就是把H H对应到对应到X X的幂集。定义的幂集。定义H H的一种办的一种办法是，允许使用前面的假设的任意析取、合取和否定式。法是，允许使用前面的假设的任意析取、合取和否定式。例如目标概念例如目标概念“Sky=SunnySky=Sunny或或Sky=CloudySky=Cloudy”可被描述为可被描述为:Sunny?Cloudy?2024/7/139 2.7 归纳偏置归纳偏置二、无偏的学习器二、无偏的学习器 虽然这个假设空间排除了表达能力的问题，它又产生了一虽然这个假设空间排除了表达能力的问题，它又产生了一个新的、同样个新的、同样困难的问题困难的问题:概念学习算法将完全无法从训练样例概念学习算法将完全无法从训练样例中泛化中泛化!其原因如下其原因如下:假定我们给学习器提供了假定我们给学习器提供了3 3个正例个正例(x(x1 1，x x2 2，x x3 3)以及两个反以及两个反例例(x(x4 4，x x5 5)。这时，变型空间的。这时，变型空间的S S边界包含的假设正好是三个正边界包含的假设正好是三个正例的析取例的析取:S:(x:S:(x1 1 x x2 2 x x3 3)因为这是能覆盖因为这是能覆盖3 3个正例的最特殊假设。相似地，个正例的最特殊假设。相似地，G G边界将边界将由那些刚好能排除掉反例的那些假设组成。由那些刚好能排除掉反例的那些假设组成。G:G:(x(x4 4 x x5 5)2024/7/140 2.7 归纳偏置归纳偏置无偏的学习器的问题无偏的学习器的问题 在该假设表示方法中，在该假设表示方法中，S S边界总是所有正例的析取式，边界总是所有正例的析取式，G G边边界总是所有反例的析取的否定式。这样能够由界总是所有反例的析取的否定式。这样能够由S S和和G G无歧义地分无歧义地分类的，只有已见到的训练样例本身。要想获得单个目标概念，类的，只有已见到的训练样例本身。要想获得单个目标概念，就必须就必须提供提供X X中所有的实例作为训练样例中所有的实例作为训练样例。避免这一问题的方法可以使用此部分学习的变型空间，遗避免这一问题的方法可以使用此部分学习的变型空间，遗憾的是，能够产生一致投票的只有那些已见过的训练样例。对憾的是，能够产生一致投票的只有那些已见过的训练样例。对其他的实例，投票没有任何效果其他的实例，投票没有任何效果:每一个未见过的实例都会被每一个未见过的实例都会被变型空间中刚好半数的假设划分为正例，而被另一半划分为反变型空间中刚好半数的假设划分为正例，而被另一半划分为反例。例。2024/7/141 2.7 归纳偏置归纳偏置三、无偏学习的无用性三、无偏学习的无用性定义定义:考虑对于实例集合考虑对于实例集合X X的概念学习算法的概念学习算法L L。令。令c c为为X X上定义上定义的任一概念，并令的任一概念，并令D Dc c=为为c c的任意训练样例集的任意训练样例集合。令合。令L(xL(xi i,D,Dc c)表示经过数据表示经过数据D Dc c的训练后的训练后L L赋予实例赋予实例x xi i的分类。的分类。L L的的归纳偏置是最小断言集合归纳偏置是最小断言集合B B，它使任意目标，它使任意目标概念概念c c和相应的训练样例和相应的训练样例D Dc c满足满足:2024/7/142 2.7 归纳偏置归纳偏置候选消除算法的归纳偏置：候选消除算法的归纳偏置：为什么为什么L(xL(xi i,D,Dc c)这一分类这一分类可由可由B=cB=c HH、数据数据D Dc c和和实例实例x xi i演绎派生演绎派生?首先，首先，如果假定目标概念如果假定目标概念c c H H，那么可演绎派生出，那么可演绎派生出c c VSVSH,DcH,Dc。这。这一派生的条件还包括变型空间一派生的条件还包括变型空间VSVSH,DcH,Dc的定义的定义(即即H H中是与中是与D Dc c一致的所一致的所有假设集合有假设集合)以及对以及对D Dc c=x=c(x)的定义的定义(即与目标概念一致的训即与目标概念一致的训练数据练数据)。其次，其次，由于由于L(xL(xi i,D,Dc c)是一分类，它定义为变型空间中所有假设的是一分类，它定义为变型空间中所有假设的一致投票。因此，如果一致投票。因此，如果L L输出分类输出分类L(xL(xi i,D,Dc c)，那么，那么VSVSH,DcH,Dc中每一假设中每一假设必将产生同样的分类，包括假设必将产生同样的分类，包括假设c c VSVSH,Dc H,Dc。因此。因此,c(x,c(xi i)=L(x)=L(xi i,D,Dc c)。即即:候选消除算法的归纳偏置候选消除算法的归纳偏置:目标概念包含在给定的假设空间目标概念包含在给定的假设空间H H中中,B=c,B=c HH。2024/7/143 2.7 归纳偏置归纳偏置学习算法的有偏程度学习算法的有偏程度学习算法的一个特征学习算法的一个特征以下以下3 3个学习算法，按其有偏程度个学习算法，按其有偏程度从弱到强从弱到强进行排序进行排序:1)1)机械式学习器机械式学习器(ROTE-LEARNER):(ROTE-LEARNER):没有归纳偏置没有归纳偏置。对于新实例所做。对于新实例所做的分类能从已观察到的训练样例中演绎派生，不需要附加前提。的分类能从已观察到的训练样例中演绎派生，不需要附加前提。2)2)候选消除算法候选消除算法:候选消除算法有较强的归纳偏置候选消除算法有较强的归纳偏置:即即目标概念须目标概念须在假设空间中才能表示在假设空间中才能表示。由于它是有偏的，所以能够对机械式学。由于它是有偏的，所以能够对机械式学习器不能分类的实例进行分类。当然分类的正确性也完全依赖于习器不能分类的实例进行分类。当然分类的正确性也完全依赖于归纳偏置的正确性。归纳偏置的正确性。3)3)FIND-S:FIND-S:FINDFIND一一S S算法有更强的归纳偏置，除了算法有更强的归纳偏置，除了假定目标概念须假定目标概念须在假设空间中在假设空间中，它还有另一额外的归纳偏置前提，它还有另一额外的归纳偏置前提:任何实例，除非任何实例，除非它的逆实例可由其他知识逻辑推出，否则它为反例。它的逆实例可由其他知识逻辑推出，否则它为反例。2024/7/144 2.7 归纳偏置归纳偏置 用等价的演绎系统来模拟归纳系统用等价的演绎系统来模拟归纳系统2024/7/145归纳偏置的表现形式归纳偏置的表现形式 在研究归纳推理方法时，有必要牢记在研究归纳推理方法时，有必要牢记归纳偏置的存在及其归纳偏置的存在及其强度强度。一种算法如果有偏性越强，那它的归纳能力越强，可以。一种算法如果有偏性越强，那它的归纳能力越强，可以分类更多的未见实例。其分类更多的未见实例。其表现表现可能不同：可能不同：某些归纳偏置是对类别的假定某些归纳偏置是对类别的假定，以确定目标概念的范围。如，以确定目标概念的范围。如“假设空间假设空间H H包含目标概念包含目标概念”。某些归纳偏置只是对假设进行排序某些归纳偏置只是对假设进行排序，以描述偏好程度，比如，以描述偏好程度，比如“偏向于特殊假设，而不是一般假设。偏向于特殊假设，而不是一般假设。”某些偏置隐含在学习器中不可更改某些偏置隐含在学习器中不可更改，如这里所讨论的例子。，如这里所讨论的例子。明确表示归纳偏置明确表示归纳偏置的系统，它们将偏置表示为断言的集合并的系统，它们将偏置表示为断言的集合并可由学习器操纵。可由学习器操纵。2024/7/146概念学习可看作是概念学习可看作是搜索预定义潜在假设空间的过程搜索预定义潜在假设空间的过程。假设的假设的一般到特殊偏序结构一般到特殊偏序结构可以定义在任何概念学习问题中，可以定义在任何概念学习问题中，它提供了一种有用的结构以便于假设空间的搜索。它提供了一种有用的结构以便于假设空间的搜索。FIND-SFIND-S算法算法使用一般到特殊序，在偏序结构的一个分支上执行使用一般到特殊序，在偏序结构的一个分支上执行一般到特殊搜索，以寻找与样例一致的最特殊假设。一般到特殊搜索，以寻找与样例一致的最特殊假设。候选消除算法候选消除算法利用一般到特殊序，通过渐进地计算极大特殊假利用一般到特殊序，通过渐进地计算极大特殊假设集合设集合S S和极大一般假设集合和极大一般假设集合G G计算变型空间计算变型空间(即所有与训练数据即所有与训练数据一致的假设集一致的假设集)。本章要点本章要点2024/7/147含有多个假设的变型空间可以用来含有多个假设的变型空间可以用来判断学习器判断学习器是否已收敛到是否已收敛到了目标概念了目标概念;判断训练数据判断训练数据是否不一致是否不一致;产生查询以进一步精化产生查询以进一步精化变型空间以及确定未见过的实例是否能用不完全学习到的概念变型空间以及确定未见过的实例是否能用不完全学习到的概念来无歧义地分类。来无歧义地分类。变型空间和候选消除算法为研究概念学习提供了一种有用的变型空间和候选消除算法为研究概念学习提供了一种有用的框架，然而这一算法框架，然而这一算法缺少健壮缺少健壮性。性。归纳学习算法能够归纳学习算法能够对未见数据进行分类对未见数据进行分类，是因为它们在选择，是因为它们在选择一致的假设的过程中隐含的归纳偏置。一致的假设的过程中隐含的归纳偏置。无偏的学习器无偏的学习器无法对未见样例进行归纳。无法对未见样例进行归纳。本章要点本章要点谢谢！