《机器学习》第三章 概念学习和一般到特殊序

第三章概念学习和一般到特殊序 3.1简介 定义:概念学习是指从有关某个布尔函数的输入输出训练 样例中推断出该布尔函数。 32概念学习任务 表3.1目标概念 Enjoy Sport的正例和反例 Example Sky AirTemp Humidit Wind Water Forecast EnjoySp ort SU unny Warm Normal Strong Warm Same Y Sunny Warm High Strong Warm Same Yes Rainy Cold High Strong W arm Change No Sunny Warm High Strong Cool Change Yes

Example Sky AirTemp Humidit Wind Water Forecast EnjoySp ort 1 Sunny Warm Normal Strong Warm Same Yes 2 Sunny Warm High Strong Warm Same Yes 3 Rainy Cold High Strong Warm Change No 4 Sunny Warm High Strong Cool Change Yes 表 3.1 目标概念EnjoySport的正例和反例 第三章 概念学习和一般到特殊序 3.1 简介 定义：概念学习是指从有关某个布尔函数的输入输出训练 样例中推断出该布尔函数。 3.2 概念学习任务

概念学习任务能被描述为:实例的集合、实例集合上的目标 函数、候选假设的集合以及训练例的集合。 归纳学习假设:任一假设如果在足够大的训练样例集中很好 地逼近目标函数,它也能在未见实例中很好地逼近目标函数。 33作为搜索的概念学习 EnjoySport的实例空间:3×2×2×2×2×2=96 假设空间:5×4×4×4×4×4=5120 1+4×3×3×3×3×3=973 假设的一般到特殊序 定义:令h和h为在X上定义的布尔函数。称h more general than or equal to hy(记作h>gh),当且仅当 (x∈X)(h2(x)=1)→>(h(x)=1)

概念学习任务能被描述为：实例的集合、实例集合上的目标 函数、候选假设的集合以及训练例的集合。 归纳学习假设：任一假设如果在足够大的训练样例集中很好 地逼近目标函数，它也能在未见实例中很好地逼近目标函数。 3.3 作为搜索的概念学习 EnjoySport的实例空间： 3×2×2 ×2 ×2 ×2=96 假设空间：5 ×4 ×4×4×4×4=5120 1+4 ×3×3 ×3 ×3 ×3=973 假设的一般到特殊序 定义：令hj和hk为在X上定义的布尔函数。称hj more_general_than_or_equal_to hk（记作 hj≥g hk），当且仅当 ( x X)[(h (x) 1) (h (x) 1)]   k = → j =

表3-2 Enjoysport概念学习任务 已知 实例集X可能的日子由下面的属性描述: Sky(可能取值为 Sunny, Cloudy和Rain) Air Temp(可取值为Warm和Cold) Humidity(可取值为 Normal和High) Wind(可取值为 Strong和Weak) Water(可取值为Warm和Co Forecast(可取值为Same和 Change) 假设集H:每个假设描述为6个属性 Sky, AirTemp, Humidity,wind, Water和 Forecast的值约 束的合取。约束可以为“?”(表示接受任意值), “φ”(表示拒绝所有值),或一特定值

已知： 实例集X:可能的日子由下面的属性描述： Sky（可能取值为Sunny,Cloudy和Rain) AirTemp(可取值为Warm和Cold) Humidity(可取值为Normal和High) Wind(可取值为Strong和Weak) Water(可取值为Warm和Cool) Forecast(可取值为Same和Change) 假设集H: 每个假设描述为6个属性 Sky,AirTemp,Humidity,Wind,Water和Forecast的值约 束的合取。约束可以为“？”（表示接受任意值）， “” （表示拒绝所有值），或一特定值 表3-2 EnjoySport 概念学习任务

目标概念c: EnjoySport: X→{0,1} 训练样例集D目标函数的正例和反例(见表2-1) 求解: H中的一假设h使对于X中任意x,h(x)=c(x) 实例集Ⅹ 假设集H 特殊 一般 图3-1实例假设和 more-general-than关系

目标概念c: EnjoySport: X→{0,1} 训练样例集D:目标函数的正例和反例（见表2-1) 求解： H中的一假设h,使对于X中任意x, h(x)=c(x) · ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● 实例集 X 假设集 H h1 h2 h3 特殊 一般 图3-1 实例 假设和more-general-than 关系

34 FIND-S:寻找极大特殊假设 表3.3FⅠNDS算法 1.将h初始化为H中最特殊假设 2.对每个正例x 对h的每个属性约束a1 如果x满足a1 那么不做任何处理 否则将h中a,替换为x满足的另一个更一般约束 3.输出假设h h- 第二个例子: h 第四个例子 h<<Sunny, Warm, ? Strong,?

1. 将h初始化为H中最特殊假设 2. 对每个正例x 对h的每个属性约束ai 如果x满足ai 那么不做任何处理 否则将h中ai替换为x满足的另一个更一般约束 3. 输出假设h 表3.3 FIND-S算法 3.4 FIND-S:寻找极大特殊假设 h 第一个例子: h  第二个例子: h  第四个例子: h 

FⅠNDS算法存在的问题 1)学习过程是否找到了惟一合适的假设(即目标本身) 2)如果有多个与训练样例一致的假设, FIND-S只能找到最特殊 的 3)训练样例是否一致 4)如果有多个极大特殊怎么办 5)日标概念在假设空间不存在 3.5变型空间和候选消除算法 3.51表示 定义:一个假设h与训练样例集合D一致,当且仅当对D中的每 样例都有h(x)=c(x) Consistent(h, D=(V<X, C(x ED) h(x=c(x) 变型空间:候选消除算法能够表示与训练样例一致的所有假设。 在假设空间中的这一子集被称为关于假设空间H和样例D的变 型空间( version space

FIND-S算法存在的问题: 1)学习过程是否找到了惟一合适的假设(即目标本身) 2)如果有多个与训练样例一致的假设,FIND-S只能找到最特殊 的 3)训练样例是否一致 4)如果有多个极大特殊怎么办 5)目标概念在假设空间不存在 3.5 变型空间和候选消除算法 3.5.1 表示 定义: 一个假设h与训练样例集合D一致,当且仅当对D中的每一 样例都有h(x)=c(x)。 Consistent(h,D)(D) h(x)=c(x) 变型空间：候选消除算法能够表示与训练样例一致的所有假设。 在假设空间中的这一子集被称为关于假设空间H和样例D的变 型空间(version space)

定义:关于假设空间H和训练样例集D的变型空间,标记为 VSHD2是H中与训练样例D一致的所有假设构成的子集。 VSHd=h EHConsistent(h, D) 表3-4列表后消除算法 列表后消除算法 变型空间 ersionspaces←包含H中所有假设的列表 2.对每个训练例g)AConsistent(g boundary)S,是在H中与D相一致的极大特殊( maximally specifi)

定义：关于假设空间H和训练样例集D的变型空间，标记为 VSH,D,是H中与训练样例D一致的所有假设构成的子集。 VSH,D {h H|Consistent(h,D)} 列表后消除算法 1. 变型空间VersionSpace←包含H中所有假设的列表 2. 对每个训练例 从变型空间中移出所有h(x) ≠c(x)的假设h 3. 输出VersionSpace中的假设列表 表 3-4 列表后消除算法 3.5.3 变型空间的更简洁表示 定义：关于假设空间H和训练数据D的一般边界(general boundary)G,是在H中与D相一致的极大一般(maximally general) 成员的集合。 G{gH|Consistent(s,D)(g’ H)[(g’ >gg) Consistent(g’,D)]} 定义：关于假设空间H和训练数据D的特殊边界(specific boundary)S,是在H中与D相一致的极大特殊(maximally specific)

sUnny, Warm, ? Strong,?, ?> G:, 图3-2变型空间极其一般和特殊边界集合

{,} {} S: G: 图3-2 变型空间极其一般和特殊边界集合

成员的集合。 S=SEHIConsistent(s, D)a(ES' Ehi(sgS)Consistent(S, D)I) 3.55算法举例: 36关于变型空间和候选消除的说明 3.6.1候选消除算法是否会收敛到正确的假设 候选消除算法得到的变型空间能够收敛到描述目标概念的假 设的条件是(1)在训练样例中没有错误。(②2)H中确实包含描述 目标概念的正确假设 362下一步需要什么样的训练样例 <Sunny, Warm, Normal, Light, Warm, Same 概念学习的最优査询策略,是产生实例以满足当前变型空间 中大约半数的假设。正确的目标概念就可以在只用[og2S 次实验后得到

成员的集合。 S{sH|Consistent(s,D)(s’ H)[(s>g s’)Consistent(s’,D)]} 3.5.5 算法举例： 3.6 关于变型空间和候选消除的说明 3.6.1候选消除算法是否会收敛到正确的假设 候选消除算法得到的变型空间能够收敛到描述目标概念的假 设的条件是(1)在训练样例中没有错误。(2)H中确实包含描述 目标概念的正确假设。 3.6.2 下一步需要什么样的训练样例 概念学习的最优查询策略，是产生实例以满足当前变型空间 中大约半数的假设。正确的目标概念就可以在只用[log2 |VS|] 次实验后得到

表3-5使用变型空间的候选消除算法 将G集合初始化为H中极大一般假设 将S集合初始化为H中极大特殊假设 对每个训练例d进行以下操作: 如果是一正例 从G中移去所有与d不一致的假设 对S中每个与d不一致的假设s 从S中移去s 把s的所有的极小泛化式h加入到S中,其中h满足 h与d一致,而且G的某个成员比一般 从S中移去所有这样的假设:它比S中另一假设更一般 如果是一个反例 从S中移去所有与d不一致的假设 对G中每个与d不一致的假设g 从G中移去g 把g的所有的极小特殊化式h加入到G中,其中h满足 h与d一致,而且S的某个成员比h更特殊 从G中移去所有这样的假设:它比中另一假设更特殊

将G集合初始化为H中极大一般假设 将S集合初始化为H中极大特殊假设 对每个训练例d,进行以下操作： 如果是一正例 从G中移去所有与d不一致的假设 对S中每个与d不一致的假设s 从S中移去s 把s的所有的极小泛化式h加入到S中，其中h满足 • h与d一致，而且G的某个成员比一般 从S中移去所有这样的假设：它比S中另一假设更一般 如果是一个反例 从S中移去所有与d不一致的假设 对G中每个与d不一致的假设g 从G中移去g 把g的所有的极小特殊化式h加入到G中，其中h满足 h与d一致，而且S的某个成员比h更特殊 从G中移去所有这样的假设：它比中另一假设更特殊 表3-5 使用变型空间的候选消除算法