第2章_概念学习

Date:20.12.2019File:ML1.1MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering•概念学习–给定某一类别的若干正例和反例，从中获得该类别的一般定义。•搜索的观点–在预定义的假设空间中搜索假设，使其与训练样例有最佳的拟合。–利用假设空间的偏序结构•算法收敛到正确假设的条件?•归纳学习的本质，从训练数据中泛化的理由?第2章概念学习和一般到特殊序Date:20.12.2019File:ML1.2MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering简介•许多机器学习涉及到从特殊训练样例中得到一般概念。•概念，可被看作一个对象或事件集合，它是从更大的集合中选取的子集，或在这个较大集合中定义的布尔函数。•概念学习问题的定义–给定一个样例集合以及每个样例是否属于某个概念的标注，怎样推断出该概念的一般定义。又称从样例中逼近布尔函数。–概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。Date:20.12.2019File:ML1.3MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering概念学习任务•一个例子–目标概念•Aldo进行水上运动的日子，表示为布尔函数EnjoySport–任务目的•基于某天的各属性，预测EnjoySport的值–给定一个样例集D•每个样例表示为6个属性的集合Date:20.12.2019File:ML1.4MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering概念学习任务（2）YesChangeCoolStrongHighWarmSunny4NoChangeWarmStrongHighColdRainy3YesSameWarmStrongHighWarmSunny2YesSameWarmStrongNormalWarmSunny1EnjoySportForecastWaterWindHumidityAirTempSkyExample表2-1目标概念EnjoySport的训练样例Date:20.12.2019File:ML1.5MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering概念学习任务（3）•表示假设的形式（目标函数的表示）–一个简单的形式，实例的各属性约束的合取式–令每个假设为6个约束（或变量）的向量，每个约束对应一个属性可取值范围，为•？任意本属性可接受的值•明确指定的属性值•不接受任何值–假设的例子•?,Cold,High,?,?,?•?,?,?,?,?,?//所有的样例都是正例•,,,,,//所有的样例都是反例Date:20.12.2019File:ML1.6MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering概念学习任务（4）形式化描述：•已知–实例集X•每个实例x由6个属性描述，每个属性的取值范围已确定–假设集H•每个假设h描述为6个属性的取值约束的合取–目标概念c•一个布尔函数，变量为实例–训练样例集D•目标函数（或目标概念）的正例和反例•求解–H中的一假设h，使对于X中任意x，h(x)=c(x)Date:20.12.2019File:ML1.7MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering术语定义•实例x•实例集X•概念•目标概念c•训练样例x•训练样例集D•正例，目标概念成员•反例，非目标概念成员•假设h•假设集H机器学习的目标就是寻找一个假设h，使得对所有的h，都有h(x)=c(x)Date:20.12.2019File:ML1.8MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering归纳学习假设•什么是归纳学习？–从特殊的样例得到普遍的规律（从特殊到一般）•归纳–只能保证输出的假设能与训练样例相拟合•归纳假设的一个基本假定–对于未见实例最好的假设就是与训练数据最佳拟合的假设•归纳学习假设–任一假设如果在足够大的训练样例集中很好地逼近目标函数，它也能在未见实例中很好地逼近目标函数。Date:20.12.2019File:ML1.9MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering作为搜索的概念学习•概念学习可以看作一个搜索的过程–搜索范围：假设的表示所隐含定义的整个空间–搜索目标：能够最好地拟合训练样例的假设•当假设的表示形式选定后，那么就隐含地为学习算法确定了所有假设的空间–例子EnjoySport的假设空间，如果属性Sky有3种可能的值，而AirTemp、Humidity、Wind、Water和Forecast都只有两种可能值。•实例空间X：包含3×2×2×2×2×2=96种不同的实例•假设空间H–包含5×4×4×4×4×4=5120种语法不同的假设–由于：包含有符号的假设将每个实例都分类为反例。因此，语义不同的假设只有1+4×3×3×3×3×3=973个。Date:20.12.2019File:ML1.10MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering假设的一般到特殊序•假设的一般到特殊序关系–考虑下面两个假设•h1=sunny,?,?,Strong,?,?•h2=Sunny,?,?,?,?,?–任何被h1划分为正例的实例都会被h2划分为正例，因此h2比h1更一般。•利用这个关系，无需列举所有假设，就能在无限的假设空间中进行彻底的搜索Date:20.12.2019File:ML1.11MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering假设的一般到特殊序（2）•关系“更一般”的精确定义–任给实例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ghkDate:20.12.2019File:ML1.12MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering假设的一般到特殊序（3）•“更一般”的严格情形–hjghk，当且仅当，(hjghk)(hkghj)•“更特殊”关系的定义–hjghk，当且仅当，hkghj•以EnjoySport为例说明上面的定义•偏序的特点（区别于全序），全序上的搜索可以是二分法，偏序的搜索比无序简单，比全序复杂。•这个偏序关系的定义与目标概念无关Date:20.12.2019File:ML1.13MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineeringh1=Sunny??Strong??h2=Sunny?????h3=Sunny????Cool?x1=SunnyWarmHighStrongCoolSamex2=SunnyWarmHighLightWarmSameDate:20.12.2019File:ML1.14MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineeringFind-S：寻找极大特殊假设•使用more_general_than偏序的搜索算法–从H中最特殊假设开始，然后在假设覆盖正例失败时将其一般化Find-S算法1.将h初始化为H中最特殊假设2.对每个正例x–对h的每个属性约束ai如果x满足ai那么不做任何处理否则将h中ai替换为x满足的另一个更一般约束3.输出假设hDate:20.12.2019File:ML1.15MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineeringFind-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,?,?Date:20.12.2019File:ML1.16MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineeringDate:20.12.2019File:ML1.17MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineeringFind-S：寻找极大特殊假设（3）•Find-S算法演示了一种利用more_general_than偏序来搜索假设空间的方法，沿着偏序链，从较特殊的假设逐渐转移到较一般的假设。因此，每一步得到的假设都是在那一点上与训练样例一致的最特殊的假设。•Find-S的重要特点：对以属性约束的合取式描述的假设空间H，保证输出为H中与正例一致的最特殊的假设。•存在的问题–是否收敛到了正确的目标概念？–为什么要用最特殊的假设？–训练样例是否相互一致？–如果有多个极大特殊假设怎么办？Date:20.12.2019File:ML1.18MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering变型空间和候选消除算法•候选消除算法概说–概念学习的另一种方法，候选消除算法（candidate-elimination）–Find-S算法的不足，输出的假设只是H中能够拟合训练样例的多个假设中的一个–候选消除算法输出与训练样例一致的所有假设的集合–候选消除算法在描述这一集合时不需要明确列举所有成员–利用more_general_than偏序结构，可以维护一个一致假设集合的简洁表示–候选消除算法的应用：化学质谱分析、启发式搜索的控制规则–候选消除算法的缺点：容错性能差Date:20.12.2019File:ML1.19MachineLearningPengKaixiang2015.Allrightsreserved.Machi