机器学习机器学习 概念学习概念学习 1机器学习2概念学习归纳学习概念概念学习定义作为搜索的概念学习（搜索策略：偏序）Find-S：寻找极大特殊假设变形空间和候选消除算法归纳偏置OUTLINE2机器学习2概念学习归纳学习也可以称作归纳推理或简称归纳，其任务是：给定函数f(未知)的实例集合，返回一个近似于f的函数hh称为假设，所有h的集合称为假设空间一个好的假设应该能够预测未见过的实例这就是基本的归纳问题问题实例用一个单变量函数(近似目标函数)来拟合若干数据点，选择最高次数为k的多项式集合作为假设h的集合，即假设空间H归纳学习3机器学习2概念学习数据拟合4机器学习2概念学习上图中显示了拟合两两一组数据的不同函数与所有数据一致的函数称为一致假设如何在多个一致假设之间进行选择？答案奥卡姆剃刀原则(Ockhams razor)优先选择与数据一致的最简单假设原因比数据本身更复杂的假设不能从数据中提取任何模式此外，对于非确定性函数，在假设的复杂度和数据拟合度之间进行折中不可避免Ockham剃刀原则5机器学习2概念学习归纳学习概念概念学习定义作为搜索的概念学习（搜索策略：偏序）Find-S：寻找极大特殊假设变形空间和候选消除算法归纳偏置OUTLINE6机器学习2概念学习概念学习给定某一类别的若干正例和反例，从中获得该类别的一般定义。搜索的观点在预定义的假设空间中搜索假设，使其与训练样例有最佳的拟合。利用假设空间的偏序结构算法收敛到正确假设的条件概念学习7机器学习2概念学习概念学习的定义给定一个样例集合以及每个样例是否属于某个概念的标注，怎样推断出该概念的一般定义。又称从样例中逼近布尔函数。概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。概念学习8机器学习2概念学习例子 enjoy sport目标概念，Aldo进行水上运动的日子，表示为布尔函数EnjoySport任务目的，基于某天的各属性，预测EnjoySport的值一个样例集，每个样例表示为属性的集合No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes表2-1 目标概念EnjoySport的训练样例9机器学习2概念学习基本概念实例 x : 每一个实例使用若干属性表示，相应属性值构成一个实例No.SkyAirTempHumidityWindWaterForecast EnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes例子 enjoy sport10机器学习2概念学习基本概念实例集 X : 概念定义在一个实例集合之上，这个集合表示为X No.SkyAirTempHumidityWindWaterForecast EnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes例子 enjoy sport11机器学习2概念学习基本概念目标概念 c: 待学习的概念或函数称为目标概念，记作cNo.SkyAirTempHumidityWindWaterForecast EnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes例子 enjoy sport12机器学习2概念学习基本概念训练样例 d: 每个样例为X中的一个实例x以及他的目标概念值c(x)。表示为序偶 注意：EnjoySport=yes时c(x)=1 EnjoySport=no时c(x)=0No.SkyAirTempHumidityWindWaterForecast EnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes例子 enjoy sport13机器学习2概念学习基本概念正例: c(x)=1的实例被称为正例反例: c(x)=0的实例被称为反例No.SkyAirTempHumidityWindWaterForecast EnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes例子 enjoy sport14机器学习2概念学习基本概念训练样例集 D: 训练样例的集合No.SkyAirTempHumidityWindWaterForecast EnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes例子 enjoy sport15机器学习2概念学习例子 enjoy sport基本概念假设 h: 表示X上定义的布尔函数，即h：X 0,1No.SkyAirTempHumidityWindWaterForecast EnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes假设假设 h: 问题：本例中怎样表示假设? 实例的各属性约束的合取值16机器学习2概念学习例子 enjoy sport基本概念假设 h: No.SkyAirTempHumidityWindWaterForecast EnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes明确指定的属性值明确指定的属性值任意本属性可接受的值任意本属性可接受的值不接受任何值不接受任何值: 17机器学习2概念学习例子 enjoy sport基本概念假设集合 H: 所有可能假设的集合No.SkyAirTempHumidityWindWaterForecast EnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes18机器学习2概念学习例子 enjoy sport已知:实例集 X假设集 H目标概念 c: X0,1训练样例 D求解（学习目标）:H中的一假设h，使对于X中任意x，h(x)=c(x) 19机器学习2概念学习归纳学习假设归纳学习假设任一假设如果在足够大的训练样例集中很好地逼近目标函数，它也能在未见实例中很好的逼近目标函数20机器学习2概念学习归纳学习概念概念学习定义作为搜索的概念学习（搜索策略：偏序）Find-S：寻找极大特殊假设变形空间和候选消除算法归纳偏置OUTLINE21机器学习2概念学习作为搜索的概念学习概念学习:可以看作一个在假设空间上搜索的过程学习:训练样例 假设空间选取假设的表示所隐含定义假设的表示所隐含定义的整个空间的整个空间目标： 能够最好地拟合训练样例的假设22机器学习2概念学习作为搜索的概念学习当假设的表示形式选定后，那么就隐含地为学习算法确定了所有假设的空间E.g. EnjoySport的实例空间: 3X2X2X2X2X2=96假设空间H中语法不同的假设: 5X4X4X4X4X4=5120假设空间H中语义不同的假设： （去掉“空”） 4X3X3X3X3X3+1=9733+?+SkyAirTemp Humidity Wind WaterForecastEnjoySport32222223机器学习2概念学习假设空间假设的表示形式:析取连接词（Disjunctive conjunction）线性等式（Liner equation）其它方法假设空间大小:|H| |X|24机器学习2概念学习搜索策略假设空间中彻底详尽的搜索需要一个策略（顺序）Why?如何对假设排序?线性排序偏序25机器学习2概念学习假设的一般到特殊序假设的一般到特殊序关系考虑下面两个假设h1=h2=任何被h1划分为正例的实例都会被h2划分为正例，因此h2比h1更一般。利用这个关系，无需列举所有假设，就能在无限的假设空间中进行彻底的搜索26机器学习2概念学习假设的一般到特殊序关系“更一般”的精确定义任给实例x和假设h，说x满足h，当且仅当h(x)=1令hj和hk是在X上定义的布尔函数，称hj比hk更一般，当且仅当(xX)(hk(x)=1)(hj(x)=1)记为hj more_general_than_or_equal_to hk ，或hj g hk27机器学习2概念学习实例、假设和more_general_than关系x1=x2=实例实例X假设集假设集 Hx1x2h1h2h3h1=h2=h3=specificgeneral28机器学习2概念学习归纳学习概念概念学习定义作为搜索的概念学习（搜索策略：偏序）Find-S：寻找极大特殊假设变形空间和候选消除算法归纳偏置OUTLINE29机器学习2概念学习Find-s：寻找极大特殊假设算法使用more_general_than偏序的搜索算法从H中最特殊假设开始，然后在假设覆盖正例失败时将其一般化Specific hypothesis30机器学习2概念学习Find-s算法Find-S算法1.将h初始化为H中最特殊假设2.对每个正例x对h的每个属性约束ai 如果x满足ai 那么不做任何处理 否则将h中ai替换为x满足的下一个更一般约束3.输出假设h31机器学习2概念学习Find-s中的假设空间搜索x1=, +x2=, +x3=, - x4=, +实例实例 X假设集假设集 Hx1x2h0h1h2,3h0= h1=h2=h3=h4=特殊特殊一般一般x3h4x432机器学习2概念学习Find-s的特点Find-S算法演示了一种利用more_general_than偏序来搜索假设空间的方法，沿着偏序链，从较特殊的假设逐渐转移到较一般的假设。因此，每一步得到的假设都是在那一点上与训练样例一致的最特殊的假设。Find-S的重要特点：对以属性约束的合取式描述的假设空间H，保证输出为H中与正例一致的最特殊的假设。33机器学习2概念学习Find-s存在问题存在的问题是否收敛到了正确的目标概念？Find-s找到了与训练样例一致的假设，但无法确定它是否找到了唯一合适的假设（即目标概念本身）。或者说是否还有其它的假设为什么要用最特殊的假设？如果有多个与D一致的假设，它只找到最特殊的假设训练样例是否相互一致？D中出现错误将严重破坏Find-s算法如果有多个极大特殊假设怎么办？34机器学习2概念学习归纳学习概念概念学习定义作为搜索的概念学习（搜索策略：偏序）Find-S：寻找极大特殊假设变形空间和候选消除算法归纳偏置OUTLINE35机器学习2概念学习变形空间和候选消除算法候选消除算法概述概念学习的另一种方法，候选消除算法（candidate-elimination）Find-S算法的不足，输出的假设只是H中能够拟合训练样例的多个假设中的一个候选消除算法输出与训练样例一致的所有假设的集合候选消除算法在描述这一集合时不需要明确列举所有成员，利用more_general_than偏序结构，可以维护一个一致假设集合的简洁表示36机器学习2概念学习变形空间和候选消除算法候选消除算法的应用，化学质谱分析、启发式搜索的控制规则候选消除算法的缺点，容错性能差37机器学习2概念学习变形空间和候选消除算法输出与训练样例一致的所有假设的集合“一致”的定义一个假设h与训练样例集合D一致，当且仅当对D中每一个样例都有h(x)=c(x)，即Consistent(h,D)(D) h(x)=c(x)38机器学习2概念学习变形空间和候选消除算法变形空间 VSH,D关于H和D的变型空间，记为VSH,D，是假设空间H中与训练样例D一致的所有假设构成的子集VSH,D h H|Consistent(h,D)versionspaceSG39机器学习2概念学习变形空间示例S:,G: 40机器学习2概念学习列表后消除算法列表后消除算法：表示变型空间的一种方法是列出其所有成员算法：变型空间VSH,D 包含H中所有假设的列表对每个训练样例从变型空间中移除所有h(x)c(x)的假设输出VSH,D中的假设列表41机器学习2概念学习列表后消除算法优点保证得到所有与训练数据一致的假设缺点非常繁琐地列出H中的所有假设，大多数实际的假设空间无法做到42机器学习2概念学习候选消除算法变型空间的更简洁表示变型空间被表示为它的极大一般和极大特殊的成员这些成员形成了一般和特殊边界的集合，这些边界在整 个偏序结构中划分出变型空间。关于假设空间H和训练数据D的一般边界G，是在H中与D相一致的极大一般成员的集合关于假设空间H和训练数据D的特殊边界S，是在H中与D相一致的极大特殊成员的集合43机器学习2概念学习候选消除算法算法描述初始化G和S如果d是一个正例从G中移去所有与d不一致的假设对S中每个与d不一致的假设s从S中移去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中移去所有这样的假设：它比G中另一个假设更特殊44机器学习2概念学习候选消除算法示例极大一般极大一般极大特殊极大特殊正例正例正例正例s1G1s2G2反例反例specific45机器学习2概念学习候选消除算法示例极大一般极大一般极大特殊极大特殊正例正例正例正例s1G1s2G2反例反例specific46机器学习2概念学习极大一般极大一般极大特殊极大特殊正例正例正例正例s1G1s2, s3G2G3 正例正例候选消除算法示例47机器学习2概念学习极大一般极大一般极大特殊极大特殊正例正例正例正例s1G1s2, s3G2G4S4候选消除算法示例 正例正例48机器学习2概念学习S 边界覆盖了正例相关的信息，因此正例不需要保留G 边界覆盖了反例相关的信息，因此反例不需要保留训练样例使用顺序不会影响算法结果（变形空间），但会影响算法效率正例使S边界一般化，反例使G边界特殊化.如果S和G覆盖同样的假设，则假设空间中只有一个与训练数据一致的假设.如果S和G 变为空(二者有一个为空，另一个必为空)，那么假设空间中没有与训练数据一致的假设.候选消除算法特点49机器学习2概念学习练习考虑积木世界的以下属性和属性值：颜色=黄色，蓝色，绿色； 形状=圆锥形，球形，长方形； 硬度=硬，软 尺寸=大，小训练样例如下（“+”表示正例，“-”表示反例） (黄色，圆锥形，软，大，+) (蓝色，长方形，软，小，-) (黄色，球形，软，小，+) (黄色，圆锥形，硬，大，+) (黄色，长方形，软，大，+) (绿色，球形，硬，大，-) (蓝色，圆锥形，软，大，-)问题：采用变形空间法，学习概念：黄色积木50机器学习2概念学习变型空间和候选消除算法的说明(1)候选消除算法收敛到正确的假设，当且仅当训练样例中没有错误H中确实包含描述目标概念的正确假设如果样例中存在错误如果给定足够的训练数据，我们会发现S和G边界收敛得到一个空的变型空间如果目标概念不能由假设表示方式所描述相似情况出现51机器学习2概念学习变型空间和候选消除算法的说明(2)下一步需要什么样的训练样例一般来说，概念学习的最优查询策略，是产生实例以满足当前变型空间中大约半数的假设。这样，变型空间的大小可以在遇到每个新样例时减半，正确的目标概念就可在只用log2|VS|次实验后得到。52机器学习2概念学习变型空间和候选消除算法的说明(3)怎样使用不完全学习概念若变型空间中仍包含多个假设，即目标概念还未学习到，但是仍然有可能对新样例进行一定可信度的分类。53机器学习2概念学习示例对未见实例分类S:,G: 6+- 3+3- 2+4-54机器学习2概念学习归纳学习概念概念学习定义作为搜索的概念学习（搜索策略：偏序）Find-S：寻找极大特殊假设变形空间和候选消除算法归纳偏置OUTLINE55机器学习2概念学习归纳偏置有关候选消除算法的几个问题如果目标概念不在假设空间中怎么办？是否可设计一个包含所有假设的空间来解决这一困难？假设空间的大小对于算法推广到未见实例的能力有什么影响？假设空间的大小对所需训练样例的数量有什么影响？56机器学习2概念学习归纳偏置一个有偏的假设空间在EnjoySport这个例子中，假设空间限制为只包含属性值的合取。（有偏）这一限制，导致假设空间不能够表示最简单的析取形式的目标概念。例如下面实例No.SkyAirTempHumidityWind Water ForecastEnjoySport1 Sunny WarmHighStrong WarmSameYes2 Cloudy WarmHighStrong WarmSameYes3Rainy WarmHighStrong WarmSameNo从从1、2得得与样例与样例一致的最特殊的假设，它仍然过于一般化了一致的最特殊的假设，它仍然过于一般化了57机器学习2概念学习归纳偏置无偏的学习器为了保证目标概念在假设空间中，需要提供一个假设空间，它能表达所有的可教授概念。换言之，它能表达实例集X的所有子集。EnjoySport的无偏形式带来的问题：概念学习算法无法从训练样例中泛化。要想获得单个目标概念，就必须提供X中所有实例作为训练样例58机器学习2概念学习归纳偏置无偏学习的无用性归纳学习的一个基本属性：学习器如果不对目标概念的形式做预先的假定，它从根本上无法对未见实例进行分类归纳学习需要的预先假定，称为归纳偏置59机器学习2概念学习归纳偏置归纳偏置的精确定义(Dcxi)L(xi,Dc) 需要在Dcxi上附加怎样的前提，以使L(xi,Dc) 能够演绎派生。L的归纳偏置定义为前提集合B，使所有的新实例满足：(BDcxi)L(xi,Dc) 考虑对于实例集合X的概念学习算法L。令c为X上定义的任一概念，并令Dc为c的任意训练样例集合，L(xi,Dc) 表示经过Dc训练后，学习算法L赋予新的实例xi的分类。L的归纳偏置是最小断言集合B，它使任意目标概念c和相应的训练样例Dc满足：xiX(BDcxi)L(xi,Dc)60机器学习2概念学习用用等等价价的的演演绎绎系系统统来来模模拟拟归归纳纳系系统统候选消除算法使用假设空间H归纳系统对新实例分类或“无法分类”训练样例新实例定理证明器等价的演绎系统对新实例分类或“无法分类”训练样例新实例断言:H包含目标概念被明确化的归纳偏置61机器学习2概念学习归纳偏置候选消除算法的归纳偏置cH即：目标概念c包括在假设空间H中(相当于有解)2个有偏程度不同的归纳学习算法机械式候选消除算法一种算法的有偏性越强，它的归纳能力越强，可以分类更多的未见实例。某些归纳偏置隐含在学习器中，有些表示为断言集合，可由学习器操作。62机器学习2概念学习总结概念学习可看作搜索预定义潜在假设空间的过程假设的一般到特殊偏序结构可以定义在任何概念学习问题中，这种结构便于假设空间的搜索Find-S算法使用一般到特殊序，在偏序结构的一个分支上执行一般到特殊搜索，寻找一个与样例一致的最特殊假设候选消除算法利用一般到特殊序，通过渐进地计算极大特殊假设集合和极大一般假设集合发现变型空间候选消除算法缺少健壮性，无法处理有噪声的数据和目标概念无法在假设空间中表示的情况归纳学习算法隐含了归纳偏置，候选消除算法的偏置是：目标概念可以在假设空间中找到。输出的假设和对新实例的分类可由归纳偏置和训练样例演绎推出63机器学习2概念学习