机器学习2概念学习优秀公开课件

1机器学习

—概念学习

2归纳学习概念概念学习定义作为搜索的概念学习（搜索策略：偏序）Find-S：寻找极大特殊假设变形空间和候选消除算法归纳偏置OUTLINE3归纳学习也可以称作归纳推理或简称归纳，其任务是：给定函数f(未知)的实例集合，返回一个近似于f的函数h——h称为假设，所有h的集合称为假设空间一个好的假设应该能够预测未见过的实例——这就是基本的归纳问题问题实例——用一个单变量函数(近似目标函数)来拟合若干数据点，选择最高次数为k的多项式集合作为假设h的集合，即假设空间H归纳学习5上图中显示了拟合两两一组数据的不同函数—与所有数据一致的函数称为一致假设如何在多个一致假设之间进行选择？答案—奥卡姆剃刀原则(Ockham’srazor)—优先选择与数据一致的最简单假设原因—比数据本身更复杂的假设不能从数据中提取任何模式此外，对于非确定性函数，在假设的复杂度和数据拟合度之间进行折中不可避免Ockham剃刀原则6归纳学习概念概念学习定义作为搜索的概念学习（搜索策略：偏序）Find-S：寻找极大特殊假设变形空间和候选消除算法归纳偏置OUTLINE7概念学习给定某一类别的若干正例和反例，从中获得该类别的一般定义。搜索的观点在预定义的假设空间中搜索假设，使其与训练样例有最佳的拟合。利用假设空间的偏序结构算法收敛到正确假设的条件概念学习9例子–enjoysport目标概念，Aldo进行水上运动的日子，表示为布尔函数EnjoySport任务目的，基于某天的各属性，预测EnjoySport的值一个样例集，每个样例表示为属性的集合No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes表2-1目标概念EnjoySport的训练样例10基本概念实例x

:每一个实例使用若干属性表示，相应属性值构成一个实例No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes例子–enjoysport11基本概念实例集X

:概念定义在一个实例集合之上，这个集合表示为X

No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes例子–enjoysport13基本概念训练样例d:每个样例为X中的一个实例x以及他的目标概念值c(x)。表示为序偶<x,c(x)>

注意：EnjoySport=yes时c(x)=1 EnjoySport=no时c(x)=0No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes例子–enjoysport14基本概念正例:c(x)=1的实例被称为正例反例:c(x)=0的实例被称为反例No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes例子–enjoysport15基本概念训练样例集D:训练样例的集合No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes例子–enjoysport17例子–enjoysport基本概念假设h:

<Sunny,Warm,?,Strong,?,?>No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes明确指定的属性值任意本属性可接受的值不接受任何值:18例子–enjoysport基本概念假设集合H:所有可能假设的集合No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes19例子–enjoysport已知:实例集–X假设集–H目标概念–c:X{0,1}训练样例–D求解（学习目标）:H中的一假设h，使对于X中任意x，h(x)=c(x)

21归纳学习概念概念学习定义作为搜索的概念学习（搜索策略：偏序）Find-S：寻找极大特殊假设变形空间和候选消除算法归纳偏置OUTLINE22作为搜索的概念学习概念学习:可以看作一个在假设空间上搜索的过程学习:训练样例假设空间选取假设的表示所隐含定义的整个空间目标：能够最好地拟合训练样例的假设23作为搜索的概念学习当假设的表示形式选定后，那么就隐含地为学习算法确定了所有假设的空间E.g.EnjoySport的实例空间:

3X2X2X2X2X2=96假设空间H中语法不同的假设:5X4X4X4X4X4=5120假设空间H中语义不同的假设：（去掉“空”）4X3X3X3X3X3+1=9733+?+SkyAirTempHumidityWindWaterForecastEnjoySport32222225搜索策略假设空间中彻底详尽的搜索需要一个策略（顺序）Why?如何对假设排序?线性排序偏序26假设的一般到特殊序假设的一般到特殊序关系考虑下面两个假设h1=<sunny,?,?,Strong,?,?>h2=<Sunny,?,?,?,?,?>任何被h1划分为正例的实例都会被h2划分为正例，因此h2比h1更一般。利用这个关系，无需列举所有假设，就能在无限的假设空间中进行彻底的搜索29归纳学习概念概念学习定义作为搜索的概念学习（搜索策略：偏序）Find-S：寻找极大特殊假设变形空间和候选消除算法归纳偏置OUTLINE30Find-s：寻找极大特殊假设算法使用more_general_than偏序的搜索算法从H中最特殊假设开始，然后在假设覆盖正例失败时将其一般化Specifichypothesis31Find-s算法Find-S算法将h初始化为H中最特殊假设对每个正例x对h的每个属性约束ai

如果x满足ai

那么不做任何处理否则将h中ai替换为x满足的下一个更一般 约束输出假设h32Find-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>,+实例X假设集Hx1x2h0h1h2,3h0=<,,,,,>h1=<sunny,warm,normal,strong,warm,same>h2=<sunny,warm,?,strong,warm,same>h3=<sunny,warm,?,strong,warm,same>h4=<sunny,warm,?,strong,?,?>特殊一般x3h4x433Find-s的特点Find-S算法演示了一种利用more_general_than偏序来搜索假设空间的方法，沿着偏序链，从较特殊的假设逐渐转移到较一般的假设。因此，每一步得到的假设都是在那一点上与训练样例一致的最特殊的假设。Find-S的重要特点：对以属性约束的合取式描述的假设空间H，保证输出为H中与正例一致的最特殊的假设。34Find-s存在问题存在的问题是否收敛到了正确的目标概念？Find-s找到了与训练样例一致的假设，但无法确定它是否找到了唯一合适的假设（即目标概念本身）。或者说是否还有其它的假设为什么要用最特殊的假设？如果有多个与D一致的假设，它只找到最特殊的假设训练样例是否相互一致？D中出现错误将严重破坏Find-s算法如果有多个极大特殊假设怎么办？35归纳学习概念概念学习定义作为搜索的概念学习（搜索策略：偏序）Find-S：寻找极大特殊假设变形空间和候选消除算法归纳偏置OUTLINE36变形空间和候选消除算法候选消除算法概述概念学习的另一种方法，候选消除算法（candidate-elimination）Find-S算法的不足，输出的假设只是H中能够拟合训练样例的多个假设中的一个候选消除算法输出与训练样例一致的所有假设的集合候选消除算法在描述这一集合时不需要明确列举所有成员，利用more_general_than偏序结构，可以维护一个一致假设集合的简洁表示37变形空间和候选消除算法候选消除算法的应用，化学质谱分析、启发式搜索的控制规则候选消除算法的缺点，容错性能差38变形空间和候选消除算法输出与训练样例一致的所有假设的集合“一致”的定义一个假设h与训练样例集合D一致，当且仅当对D中每一个样例<x,c(x)>都有h(x)=c(x)，即Consistent(h,D)(<x,c(x)>D)h(x)=c(x)39变形空间和候选消除算法变形空间VSH,D关于H和D的变型空间，记为VSH,D，是假设空间H中与训练样例D一致的所有假设构成的子集VSH,D

{h

H|Consistent(h,D)}versionspaceSG40变形空间示例{<Sunny,Warm,?,Strong,?,?>}S:{<Sunny,?,?,?,?,?>,<?,Warm,?,?,?,?>}G:<Sunny,?,?,Strong,?,?><Sunny,Warm,?,?,?,?><?,Warm,?,Strong,?,?>41列表后消除算法列表后消除算法：表示变型空间的一种方法是列出其所有成员算法：变型空间VSH,D

包含H中所有假设的列表对每个训练样例<x,c(x)>从变型空间中移除所有h(x)c(x)的假设输出VSH,D中的假设列表42列表后消除算法优点保证得到所有与训练数据一致的假设缺点非常繁琐地列出H中的所有假设，大多数实际的假设空间无法做到43候选消除算法变型空间的更简洁表示变型空间被表示为它的极大一般和极大特殊的成员这些成员形成了一般和特殊边界的集合，这些边界在整个偏序结构中划分出变型空间。关于假设空间H和训练数据D的一般边界G，是在H中与D相一致的极大一般成员的集合关于假设空间H和训练数据D的特殊边界S，是在H中与D相一致的极大特殊成员的集合44候选消除算法——算法描述初始化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中另一个假设更特殊45候选消除算法——示例极大一般极大特殊{<sunny,warm,normal,strong,warm,same>}正例{<sunny,warm,high,strong,warm,same>}正例s1G1s2{<sunny,warm,?,strong,warm,same>}G2{<rainy,cold,high,strong,warm,change>}反例specific46候选消除算法——示例极大一般极大特殊{<sunny,warm,normal,strong,warm,same>}正例{<sunny,warm,high,strong,warm,same>}正例s1G1s2{<sunny,warm,?,strong,warm,same>}G2{<rainy,cold,high,strong,warm,change>}反例specific47极大一般极大特殊{<sunny,warm,normal,strong,warm,same>}正例{<sunny,warm,high,strong,warm,same>}正例s1G1s2,s3{<sunny,warm,?,strong,warm,same>}G2G3{<sunny,?,?,?,?,?><?,warm,?,?,?,?><?,?,?,?,?,same>}{<sunny,warm,high,strong,cool,change>}正例候选消除算法——示例48极大一般极大特殊{<sunny,warm,normal,strong,warm,same>}正例{<sunny,warm,high,strong,warm,same>}正例s1G1s2,s3{<sunny,warm,?,strong,warm,same>}G2G4{<sunny,warm,?,strong,?,?>}S4候选消除算法——示例{<sunny,?,?,?,?,?><?,warm,?,?,?,?>}正例49S

边界覆盖了正例相关的信息，因此正例不需要保留G

边界覆盖了反例相关的信息，因此反例不需要保留训练样例使用顺序不会影响算法结果（变形空间），但会影响算法效率正例使S边界一般化，反例使G边界特殊化.如果S和G覆盖同样的假设，则假设空间中只有一个与训练数据一致的假设.如果S和G

变为空(二者有一个为空，另一个必为空)，那么假设空间中没有与训练数据一致的假设.候选消除算法特点50练习考虑积木世界的以下属性和属性值：颜色={黄色，蓝色，绿色}；形状={圆锥形，球形，长方形}；硬度={硬，软}

尺寸={大，小}训练样例如下（“+”表示正例，“-”表示反例）

(黄色，圆锥形，软，大，+)(蓝色，长方形，软，小，-)(黄色，球形，软，小，+)(黄色，圆锥形，硬，大，+)(黄色，长方形，软，大，+)(绿色，球形，硬，大，-)

(蓝色，圆锥形，软，大，-)问题：采用变形空间法，学习概念：黄色积木51变型空间和候选消除算法的说明(1)候选消除算法收敛到正确的假设，当且仅当训练样例中没有错误H中确实包含描述目标概念的正确假设如果样例中存在错误如果给定足够的训练数据，我们会发现S和G边界收敛得到一个空的变型空间如果目标概念不能由假设表示方式所描述相似情况出现52变型空间和候选消除算法的说明(2)下一步需要什么样的训练样例一般来说，概念学习的最优查询策略，是产生实例以满足当前变型空间中大约半数的假设。这样，变型空间的大小可以在遇到每个新样例时减半，正确的目标概念就可在只用log2|VS|次实验后得到。53变型空间和候选消除算法的说明(3)怎样使用不完全学习概念若变型空间中仍包含多个假设，即目标概念还未学习到，但是仍然有可能对新样例进行一定可信度的分类。54示例——对未见实例分类{<Sunny,Warm,?,Strong,?,?>}S:{<Sunny,?,?,?,?,?>,<?,Warm,?,?,?,?>}G:<Sunny,?,?,Strong,?,?><Sunny,Warm,?,?,?,?><?,Warm,?,Strong,?,?><SunnyWarmNormalStrongCoolChange>6+----------------------------------------------------------------<SunnyWarmNormalLightWarmSame>3+3-----------------------------------------------------------------<SunnyColdNormalStrongWarmSame>2+4-55归纳学习概念概念学习定义作为搜索的概念学习（搜索策略：偏序）Find-S：寻找极大特殊假设变形空间和候选消除算法归纳偏置OUTLINE56归纳偏置有关候选消除算法的几个问题如果目标概念不在假设空间中怎么办？是否可设计一个包含所有假设的空间来解决这一困难？假设空间的大小对于算法推广到未见实例的能力有什么影响？假设空间的大小对所需训练样例的数量有什么影响？57归纳偏置一个有偏的假设空间在EnjoySport这个例子中，假设空间限制为只包含属性值的合取。（有偏）这一限制，导致假设空间不能够表示最简单的析取形式的目标概念。例如下面实例No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmHighStrongWarmSameYes2CloudyWarmHighStrongWarmSameYes3RainyWarmHighStrongWarmSameNo从1、2得<？WarmHighStrongWarmSame>与样例一致的最特殊的假设，它仍然过于一般化了58归纳偏置无偏的学习器为了保证目标概念在假设空间中，需要提供一个假设空间，它能表达所有的可教授概念。换言之，它能表达实例集X的所有子集。