FⅠNDS算法存在的问题 1)学习过程是否找到了惟一合适的假设(即目标本身) 2)如果有多个与训练样例一致的假设, FIND-S只能找到最特殊 的 3)训练样例是否一致 4)如果有多个极大特殊怎么办 5)日标概念在假设空间不存在 3.5变型空间和候选消除算法 3.51表示 定义:一个假设h与训练样例集合D一致,当且仅当对D中的每 样例<xc(x)>都有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中的每一 样例<x,c(x)>都有h(x)=c(x)。 Consistent(h,D)(<x,c(x)>D) h(x)=c(x) 变型空间：候选消除算法能够表示与训练样例一致的所有假设。 在假设空间中的这一子集被称为关于假设空间H和样例D的变 型空间(version space)
定义:关于假设空间H和训练样例集D的变型空间,标记为 VSHD2是H中与训练样例D一致的所有假设构成的子集。 VSHd=h EHConsistent(h, D) 表3-4列表后消除算法 列表后消除算法 变型空间 ersionspaces←包含H中所有假设的列表 2.对每个训练例<x,c(x) 从变型空间中移出所有h(x)(x)的假设h 3.输出 Versionspace中的假设列表 353变型空间的更简洁表示 定义:关于假设空间H和训练数据D的一般边界( general boundary)G,是在H中与D相一致的极大一般( maximally general 成员的集合 定义:关于假设空间H和训练数据D的特殊边界(ec、D)]} G=gEHConsistent(s, D)aGg Edig>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. 对每个训练例<x,c(x)> 从变型空间中移出所有h(x) ≠c(x)的假设h 3. 输出VersionSpace中的假设列表 表 3-4 列表后消除算法 3.5.3 变型空间的更简洁表示 定义：关于假设空间H和训练数据D的一般边界(general boundary)G,是在H中与D相一致的极大一般(maximally general) 成员的集合。 G{gH|Consistent(s,D)(g’ H)[(g’ >gg) Consistent(g’,D)]} 定义：关于假设空间H和训练数据D的特殊边界(specific boundary)S,是在H中与D相一致的极大特殊(maximally specific)
sUnny, Warm, ? Strong,?, ?> <Sunny, ? ? Strong,?,?> <Sunny, Warm, ? ?,? ? <?,Warm,?, Strong,?, ?> G:<Sunny, ? 22. 22>,<2, Warm, ? 22.2> 图3-2变型空间极其一般和特殊边界集合
{<Sunny,?,?,?,??>,<?,Warm,?,?,?,?>} {<Sunny,Warm,?,Strong,?,?>} <Sunny,?,?,Strong,?,?> <Sunny,Warm,?,?,?,?> <?,Warm,?,Strong,?,?> 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{sH|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 下一步需要什么样的训练样例 <Sunny,Warm,Normal,Light,Warm,Same> 概念学习的最优查询策略，是产生实例以满足当前变型空间 中大约半数的假设。正确的目标概念就可以在只用[log2 |VS|] 次实验后得到