《机器学习课件》由会员分享，可在线阅读，更多相关《机器学习课件（41页珍藏版）》请在金锄头文库上搜索。
1、现代机器学习理论 主讲：张莉 第2章 概念学习和一般到特殊序1提纲n概念学习n给定某一类别的若干正例和反例，从中获得该类别 的一般定义n搜索的观点n在预定义的假设空间中搜索假设，使其与训练样例 有最佳的拟合n利用假设空间的偏序结构n算法收敛到正确假设的条件n归纳学习的本质，从训练数据中泛化的理由2简介n许多机器学习涉及到从特殊训练样例中得到一般 概念。n概念，可被看作一个对象或事件集合，它是从更 大的集合中选取的子集，或在这个较大集合中定义 的布尔函数。n概念学习问题的定义n问题：给定一个样例集合以及每个样例是否属于某 个概念的标注，怎样推断出该概念的一般定义。又称 从样例中逼近布尔函数n定义
2、：概念学习是指从有关某个布尔函数的输入输 出训练样例中推断出该布尔函数3概念学习任务n一个例子n目标概念，Aldo进行水上运动的日子，表示 为布尔函数EnjoySportn任务目的，基于某天的各属性，预测 EnjoySport的值n一个样例集，每个样例表示为属性的集合4概念学习任务（2）YesChangeCoolStrongHighWarmSunny4NoChangeWarmStrongHighColdRainy3YesSameWarmStrongHighWarmSunny2YesSameWarmStrongNormalWarmSunny1EnjoySportForecastWaterWind
3、HumidityAirTempSkyExample表2-1 目标概念EnjoySport的训练样例候选消除法变型空间例一般到特殊Find_S5概念学习任务（3）n表示假设的形式n一个简单的形式，实例的各属性约束(变量)的合取 式n令每个假设为6个约束(变量)的向量，每个约束(变量 )对应一个属性可取值范围，为n？任意本属性可接受的值n明确指定的属性值n 不接受任何值n假设的例子nn/ 所有的样例都是 正例n/ 所有的样例都是反例6EnjoySport概念学习任务n已知n实例集Xn每个实例x由6个属性描述，每个属性的取值 范围已确定n假设集Hn每个假设h描述为6个属性的取值约束的合取n目标概念c
4、n一个布尔函数，变量为实例n训练样例集Dn目标函数（或目标概念）的正例和反例n求解nH中的一假设h，使对于X中任意x，h(x)=c(x) 7术语定义n实例x和实例集Xn概念和目标概念cn训练样例x和训练样例集Dn正例，目标概念成员n反例，非目标概念成员n假设h和假设集H 机器学习的目标就是寻找一个假设h，使得对所有的 h，都有h(x)=c(x)8归纳学习假设n什么是归纳学习？n从特殊的样例得到普遍的规律n归纳n只能保证输出的假设能与训练样例相拟合n归纳假设的一个基本假定n对于未见实例最好的假设就是与训练数据最佳拟合 的假设n归纳学习假设n任一假设如果在足够大的训练样例集中很好地逼近 目标函数，
5、它也能在未见实例中很好地逼近目标函数 9作为搜索的概念学习n概念学习可以看作一个搜索的过程n搜索范围：假设的表示所隐含定义的整个空 间n搜索目标：能够最好地拟合训练样例的假设n当假设的表示形式选定后，那么就隐含地 为学习算法确定了所有假设的空间n例子EnjoySport的假设空间10假设的一般到特殊序n假设的一般到特殊序关系n考虑下面两个假设nh1=nh2=n任何被h1划分为正例的实例都会被h2划分为 正例，因此h2比h1更一般n利用这个关系，无需列举所有假设，就能 在无限的假设空间中进行彻底的搜索11假设的一般到特殊序（2）n关系“更一般”的精确定义n任给实例x和假设h，说x满足h，当且仅当
6、 h(x)=1n令hj和hk是在X上定义的布尔函数，称hj比hk 更一般，当且仅当(xX)(hk(x)=1)(hj(x)=1)n记为hj more_general_than_or_equal_to hk，或 hj g hk12假设的一般到特殊序（3）n“更一般”的严格情形nhj g hk，当且仅当， n“更特殊”关系的定义nhj g hk，当且仅当，hk g hjn以EnjoySport为例说明上面的定义n偏序的特点（区别于全序），全序上的搜索可以 是二分法，偏序的搜索比无序简单，比全序复杂。n这个偏序关系的定义与目标概念无关13Find-S：寻找极大特殊假设n使用more_general_t
7、han偏序的搜索算法n从H中最特殊假设开始，然后在假设覆盖正例失败 时将其一般化表2-3 Find-S算法将h初始化为H中最特殊假设对每个正例x对h的每个属性约束ai 如果x满足ai 那么不做任何处理 否则将h中ai替换为x满足的另一个更一般约束输出假设h 14Find-S：寻找极大特殊假设(2)nFind-S算法在例子EnjoySport上的应用nhnhnhn遇到反例，h不变（因为h已经能够正确地识 别反例）nh训练样本15Find-S：寻找极大特殊假设(3)nFind-S算法沿着偏序链搜索，每一步得到的假设 都是在那一点上与训练样例一致的最特殊的假设nFind-S的重要特点n对以属性约束的
8、合取式描述的假设空间H，保证 输出为H中与正例一致的最特殊的假设n存在的问题n是否收敛到了正确的目标概念？n为什么要用最特殊的假设？n训练样例是否相互一致？n如果有多个极大特殊假设怎么办？16变型空间和候选消除算法n候选消除算法（candidate-elimination）nFind-S算法的不足：输出的假设只是H中能够 拟合训练样例的多个假设中的一个n候选消除算法输出与训练样例一致的所有假 设的集合n候选消除算法在描述这一集合时不需要明确 列举所有成员n候选消除算法的应用，化学质谱分析、启发 式搜索的控制规则n候选消除算法的缺点，容错性能差17变型空间和候选消除算法（2）n“一致”的定义n一
9、个假设h与训练样例集合D一致，当且仅当对D中 每一个样例都有h(x)=c(x)，即 Consistent(h,D)(D)h(x)=c(x)n“一致”与“满足”的关系n变型空间（version space）n与训练样例一致的所有假设组成的集合n表示了目标概念的所有合理的变型n关于H和D的变型空间，记为VSH,D，是H中与训练 样例D一致的所有假设构成的子集 VSH,D=hH|Consistent(h,D)18变型空间和候选消除算法（3）n列表后消除(List then eliminate)算法 表示变型空间的一种方法是列出其所有成员n变型空间包含H中所有假设的列表n对每个训练样例，从变型空间中移
10、除所有 h(x)c(x)的假设n输出Version Space中的假设列表n优点n保证得到所有与训练数据一致的假设n缺点n非常繁琐地列出H中的所有假设，大多数实际的假 设空间无法做到 19变型空间和候选消除算法（4）n变型空间的更简洁表示n变型空间被表示为它的极大一般和极大特殊 的成员n这些成员形成了一般和特殊边界的集合，这 些边界在整个偏序结构中划分出变型空间n以EnjoySport为例20变型空间和候选消除算法（5）n形式化定义n极大一般n极大特殊n关于假设空间H和训练数据D的一般边界G ，是在H中与D相一致的极大一般成员的集合n关于假设空间H和训练数据D的特殊边界S ，是在H中与D相一致
11、的极大特殊成员的集合21变型空间和候选消除算法（6）变型空间表示定理： 令X为一任意的实例集合，H为X上定义的布尔假设 的集合。令c: X0,1为X上定义的任一目标概念， 并令D为任一训练样例集合。对所有的X, H, c, D以及良好定义的S和G： VSH,D=hH|(sS)( gG)(gghgs)22候选 消除 算法n初始化G和Sn如果d是一个正例n从G中移去所有与d不一致的假设n对S中每个与d不一致的假设sn从S中移去sn把s的所有的极小一般化式h加入到S中，其中h满 足nh与 d一致，而且G的某个成员比h更一般n从S中移去所有这样的假设：它比S中另一个假设 更一般n如果d是一个反例n从S
12、中移去所有与d不一致的假设n对G中每个与d不一致的假设gn从G中移去gn把g的所有的极小特殊化式h加入到G中，其中h满 足nh与d一致，而且S的某个成员比h更特殊n从G中移去所有这样的假设：它比G中另一个假设 更特殊23变型空间和候选消除算法（8）n算法举例（EnjoySport）n初始边界集合S0和G0训练样本变型空间例24变型空间和候选消除的说明n候选消除算法收敛到正确的假设n训练样例中没有错误nH中确实包含描述目标概念的正确假设n如果样例中存在错误n如果给定足够的训练数据，我们会发现S和 G边界收敛得到一个空的变型空间n如果目标概念不能由假设表示方式所描述n相似情况出现25变型空间和候选
13、消除（2）n下一步需要什么样的训练样例n一般来说，概念学习的最优查询策略，是产 生实例以满足当前变型空间中大约半数的假设 。这样，变型空间的大小可以在遇到每个新样 例时减半，正确的目标概念就可在只用 log2|VS|次实验后得到n查询实例n变型空间例26变型空间和候选消除（3）n怎样使用不完全学习概念n虽然图2-3的变型空间中仍包含多个假设， 即目标概念还未学习到，但是仍然有可能对新 样例进行一定可信度的分类n表2-6的例子27表2-6的例子?SameWarmStrongNormalColdSunnyD?SameWarmLightNormalWarmSunnyC?SameWarmLightNo
14、rmalColdRainyB?ChangeCoolStrongNormalWarmSunnyAEnjoySportForecastWaterWindHumidityAirTempSkyExample表2-6 待分新实例变型空间例28归纳偏置n有关候选消除算法的几个问题n如果目标概念不在假设空间中怎么办？n是否可设计一个包含所有假设的空间来解决 这一困难？n假设空间的大小对于算法推广到未见实例的 能力有什么影响？n假设空间的大小对所需训练样例的数量有什 么影响？无偏学习29归纳偏置（2）n一个有偏的假设空间n在EnjoySport这个例子中，假设空间限制为 只包含属性值的合取。（有偏）n这一限制
15、，导致假设空间不能够表示最简单 的析取形式的目标概念。NoChangeCoolStrongNormalWarmRainy3YesChangeCoolStrongNormalWarmCloudy2YesChangeCoolStrongNormalWarmSunny1EnjoySportForecastWaterWindHumidityAirTempSkyExample30归纳偏置（3）n无偏的学习器n为了保证目标概念在假设空间中，需要提供 一个假设空间，它能表达所有的可教授概念（ every teachable concept）;换言之，它能表达实例 集X的所有子集。n幂集：2|X|n问题：为什
16、么2.3节中合取假设空间只能表 示973个假设？31归纳偏置（4）nEnjoySport的无偏形式n带来的问题：概念学习算法无法从训练样例 中泛化。n要想获得单个目标概念，就必须提供X中所 有实例作为训练样例n使用2.6.3节讨论的部分学习的无效偏置问题32归纳偏置（5）n无偏学习的无用性n归纳学习的一个基本属性：学习器如果不对 目标概念的形式做预先的假定，它从根本上无 法对未见实例进行分类n归纳学习需要的预先假定，称为归纳偏置（ inductive bias）33归纳偏置的精确定义n nL的归纳偏置定义为前提集合B，使所有的新实例满足：n定义：考虑对于实例集合X的概念学习算法L。令c 为X上定义的任一概念，并令Dc为c的任意训练样例 集合， 表示经过Dc训练后L赋予实例xi的分类 。L的归纳偏置是最小断言集合B，它使任意目标概 念c和相应的训练样例Dc满足：34归纳偏置（6）n候选消除算法的归纳偏置ncHn3个有偏
