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

第三章概念学习和一般到特殊序 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 =

已知: 实例集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的值约 束的合取。约束可以为“?2”(表示接受任意值), “φ”(表示拒绝所有值),或一特定值

 已知： 实例集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的值约 束的合取。约束可以为“？”（表示接受任意值）， “” （表示拒绝所有值），或一特定值

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

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

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 

表列表后消除算法 列表后消除算法 1.变型空间 ersion Space←包含H中所有假设的列表 2.对每个训练例 从变型空间中移出所有h(x)(x)的假设h 3.输出Ⅴ ersion space中的假设列表

列表后消除算法 1. 变型空间VersionSpace←包含H中所有假设的列表 2. 对每个训练例 从变型空间中移出所有h(x) ≠c(x)的假设h 3. 输出VersionSpace中的假设列表 表 列表后消除算法

sUnny, Warm, ? Strong,?, ?> G:

{,} {} S: 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中移去所有这样的假设:它比中另一假设更特殊

将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中移去所有这样的假设：它比中另一假设更特殊

S0: oooo ool S1:(Sunny, Warm, Normal, Strong, Warm, Same>j S2:) GO.GlG2 }

S0: {} ,       S1: {} S2: {} G0,G1,G2: {}

S2S3 k) G3:{}

{} { {} S2,S3: G3: G2: