6.机器学习(2.概念学习)

1机器学习—概念学习2•归纳学习概念•概念学习定义•作为搜索的概念学习（搜索策略：偏序）•Find-S：寻找极大特殊假设•变形空间和候选消除算法•归纳偏置OUTLINE3•归纳学习也可以称作归纳推理或简称归纳，其任务是：给定函数f(未知)的实例集合，返回一个近似于f的函数h——h称为假设，所有h的集合称为假设空间•一个好的假设应该能够预测未见过的实例——这就是基本的归纳问题–问题实例——用一个单变量函数(近似目标函数)来拟合若干数据点，选择最高次数为k的多项式集合作为假设h的集合，即假设空间H归纳学习4x)(xf)(ax)(xf)(bx)(xf)(cx)(xf)(d数据拟合5•上图中显示了拟合两两一组数据的不同函数—与所有数据一致的函数称为一致假设•如何在多个一致假设之间进行选择？•答案—奥卡姆剃刀原则(Ockham’srazor)—优先选择与数据一致的最简单假设•原因—比数据本身更复杂的假设不能从数据中提取任何模式•此外，对于非确定性函数，在假设的复杂度和数据拟合度之间进行折中不可避免Ockham剃刀原则6•归纳学习概念•概念学习定义•作为搜索的概念学习（搜索策略：偏序）•Find-S：寻找极大特殊假设•变形空间和候选消除算法•归纳偏置OUTLINE7•概念学习–给定某一类别的若干正例和反例，从中获得该类别的一般定义。•搜索的观点–在预定义的假设空间中搜索假设，使其与训练样例有最佳的拟合。–利用假设空间的偏序结构•算法收敛到正确假设的条件概念学习8•概念学习的定义–给定一个样例集合以及每个样例是否属于某个概念的标注，怎样推断出该概念的一般定义。又称从样例中逼近布尔函数。–概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。概念学习9例子–enjoysport•目标概念，Aldo进行水上运动的日子，表示为布尔函数EnjoySport•任务目的，基于某天的各属性，预测EnjoySport的值•一个样例集，每个样例表示为属性的集合No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes表2-1目标概念EnjoySport的训练样例10•基本概念–实例x:每一个实例使用若干属性表示，相应属性值构成一个实例No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes例子–enjoysport11•基本概念–实例集X:概念定义在一个实例集合之上，这个集合表示为XNo.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes例子–enjoysport12•基本概念–目标概念c:待学习的概念或函数称为目标概念，记作cNo.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes例子–enjoysport13•基本概念–训练样例d:每个样例为X中的一个实例x以及他的目标概念值c(x)。表示为序偶x,c(x)注意：EnjoySport=yes时c(x)=1EnjoySport=no时c(x)=0No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes例子–enjoysport14•基本概念–正例:c(x)=1的实例被称为正例–反例:c(x)=0的实例被称为反例No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes例子–enjoysport15•基本概念–训练样例集D:训练样例的集合No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes例子–enjoysport16例子–enjoysport•基本概念–假设h:表示X上定义的布尔函数，即h：X{0,1}No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes假设h:Sunny,Warm,?,Strong,?,?问题：本例中怎样表示假设?实例的各属性约束的合取值17例子–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)20归纳学习假设•归纳学习假设–任一假设如果在足够大的训练样例集中很好地逼近目标函数，它也能在未见实例中很好的逼近目标函数21•归纳学习概念•概念学习定义•作为搜索的概念学习（搜索策略：偏序）•Find-S：寻找极大特殊假设•变形空间和候选消除算法•归纳偏置OUTLINE22作为搜索的概念学习•概念学习:–可以看作一个在假设空间上搜索的过程•学习:–训练样例假设空间选取假设的表示所隐含定义的整个空间目标：能够最好地拟合训练样例的假设23作为搜索的概念学习当假设的表示形式选定后，那么就隐含地为学习算法确定了所有假设的空间–E.g.EnjoySport的实例空间:•3X2X2X2X2X2=96–假设空间H中语法不同的假设:•5X4X4X4X4X4=5120–假设空间H中语义不同的假设：（去掉“空”）•4X3X3X3X3X3+1=9733+?+SkyAirTempHumidityWindWaterForecastEnjoySport32222224假设空间•假设的表示形式:–析取连接词（Disjunctiveconjunction）–线性等式（Linerequation）–其它方法•假设空间大小:–|H||X|25搜索策略•假设空间中彻底详尽的搜索需要一个策略（顺序）–Why?•如何对假设排序?–线性排序–偏序26假设的一般到特殊序•假设的一般到特殊序关系–考虑下面两个假设•h1=sunny,?,?,Strong,?,?•h2=Sunny,?,?,?,?,?–任何被h1划分为正例的实例都会被h2划分为正例，因此h2比h1更一般。•利用这个关系，无需列举所有假设，就能在无限的假设空间中进行彻底的搜索27假设的一般到特殊序•关系“更一般”的精确定义–任给实例x和假设h，说x满足h，当且仅当h(x)=1–令hj和hk是在X上定义的布尔函数，称hj比hk更一般，当且仅当(xX)[(hk(x)=1)(hj(x)=1)]–记为hjmore_general_than_or_equal_tohk，或hjghk28实例、假设和more_general_than关系x1=sunny,warm,high,strong,cool,samex2=sunny,warm,high,light,warm,same实例X假设集Hx1x2h1h2h3h1=sunny,?,?,strong,?,?h2=sunny,?,?,?,?,?h3=sunny,?,?,?,cool,?specificgeneral29•归纳学习概念•概念学习定义•作为搜索的概念学习（搜索策略：偏序）•Find-S：寻找极大特殊假设•变形空间和候选消除算法•归纳偏置OUTLINE30Find-s：寻找极大特殊假设算法•使用more_general_than偏序的搜索算法–从H中最特殊假设开始，然后在假设覆盖正例失败时将其一般化Specifichypothesis31Find-s算法Find-S算法1.将h初始化为H中最特殊假设2.对每个正例x–对h的每个属性约束ai如果x满足ai那么不做任何处理否则将h中ai替换为x满足的下一个更一般约束3.输出假设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,sameh2=sunny,warm,?,strong,warm,sameh3=sunny,warm,?,strong,warm,sameh4=sunny,warm,?,strong,?,?特殊一般x3h4x433Find-s的特点•Find-S算法演示了一种利用mo