概念学习和一般到特殊序
概念学习
概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数
每个属性的可能取值：
- ？：表示任意本属性可接受的值
- 明确指定的属性值
- ∅ \emptyset ∅：不接受任何值
⇒
\Rightarrow
⇒ 最一般的假设：
<
?
,
?
,
?
,
?
,
?
>
<?,?,?,?,?>
<?,?,?,?,?> 任何例子都是正例
⇒
\Rightarrow
⇒ 最特殊的假设：
<
∅
<\emptyset
<∅,
∅
\emptyset
∅,
∅
\emptyset
∅,
∅
\emptyset
∅,
∅
>
\emptyset>
∅> 任何例子都是反例
其他的一些概念：
- 目标概念：待学习的概念或函数，记作 c c c ， c ( x ) → c(x) \rightarrow c(x)→ {0,1}
- 正例 / 目标概念的成员： c ( x ) = 1 c(x)=1 c(x)=1的实例
- 反例 / 非目标概念的成员： c ( x ) = 0 c(x)=0 c(x)=0的实例
- 归纳学习假设：任意假设在足够大的训练样例集中很好地逼近目标函数，它也能在未见实例中很好地逼近目标函数
- h j h_j hj m o r e − g e n e r a l − t h a n − o r − e q u a l − t o more -general-than-or-equal-to more−general−than−or−equal−to h k h_k hk：令 h j h_j hj和 h k h_k hk为在X上定义的布尔函数，若 ( ∀ x ∈ X ) [ ( h k ( x ) = 1 ) → ( h j ( x ) = 1 ) ] (\forall x \in X)[(h_k(x)=1) \rightarrow (h_j(x)=1)] (∀x∈X)[(hk(x)=1)→(hj(x)=1)]，可记为 h j ≥ g h k h_j \geq_g h_k hj≥ghk
- 一致：一个假设 h h h与训练样例集合 D D D一致，当且仅当对 D D D中每一个样例 < x , c ( x ) > <x,c(x)> <x,c(x)>都有h(x)=c(x)，即： C o n s i s t e n t ( h , D ) = ( ∀ < x , c ( x ) > ∈ D ) h ( x ) = c ( x ) Consistent(h,D)=(\forall <x,c(x)> \in D) h(x)=c(x) Consistent(h,D)=(∀<x,c(x)>∈D)h(x)=c(x)
- 变型空间：记为 V S H , D VS_{H,D} VSH,D是 H H H中与训练样例 D D D一致的所有假设构成的子集，即： V S H , D = VS_{H,D}= VSH,D= { h ∈ D ∣ C o n s i s t e n t ( h , D ) h \in D |Consistent(h,D) h∈D∣Consistent(h,D) }
- 一般边界：是在 H H H中与 D D D相一致的极大一般成员的集合，即： G = G= G= { g ∈ H ∣ C o n s i s t e n t ( g , D ) ∧ ( ¬ ∃ g ′ ∈ H ) [ ( g ′ > g g ) ∧ C o n s i s t e n t ( g ′ , D ) ] g \in H|Consistent(g,D) \wedge (\neg \exists g' \in H)[(g' >_g g)\wedge Consistent(g',D)] g∈H∣Consistent(g,D)∧(¬∃g′∈H)[(g′>gg)∧Consistent(g′,D)]}
- 特殊边界：是在 H H H中与 D D D相一致的极大特殊成员的集合，即： S = S= S= { s ∈ H ∣ C o n s i s t e n t ( s , D ) ∧ ( ¬ ∃ s ′ ∈ H ) [ ( s > g s ′ ) ∧ C o n s i s t e n t ( s ′ , D ) ] s \in H|Consistent(s,D) \wedge (\neg \exists s' \in H)[(s >_g s')\wedge Consistent(s',D)] s∈H∣Consistent(s,D)∧(¬∃s′∈H)[(s>gs′)∧Consistent(s′,D)]}
例子
假设EnjoySport概念学习任务：
| 属性 | 可取值 |
|---|---|
| Sky | Sunny/Cloudy/Rainy |
| AirTemp | Warm/Cold |
| Humidity | Normal/High |
| Wind | Strong/Weak |
| Water | Warm/Cool |
| Forecast | Same/Change |
给出的示例：
| Example | Sky | AirTemp | Humidity | Wind | Water | Forecast | EnjoySport |
|---|---|---|---|---|---|---|---|
| 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 |
FIND-S算法：寻找极大特殊假设
1、将
h
h
h初始化为
H
H
H中最特殊的假设—
<
∅
<\emptyset
<∅,
∅
\emptyset
∅,
∅
\emptyset
∅,
∅
\emptyset
∅,
∅
>
\emptyset>
∅>
2、对每个正例
x
x
x：
对
h
h
h的每个属性约束
a
i
a_i
ai，如果
x
x
x满足
a
i
a_i
ai，则不作任何处理，
否则将
h
h
h中
a
i
a_i
ai替换为
x
x
x满足的下一个更一般约束
3、输出假设
h
h
h
e.g：
特点：对以属性约束的合取式描述的假设空间，
F
I
N
D
−
S
FIND-S
FIND−S保证输出为
H
H
H中与正例一致的最特殊的假设
仍需解决的问题：
- 学习过程是否手链到了正确的目标概念，无法确定该算法是否找到了唯一合适的假设，是否还有其他可能的假设
- 为什么要用最特殊的假设
- 训练样例是否相互一致
- 如果有多个极大特殊假设怎么办？
候选消除算法
F
I
N
D
−
S
FIND-S
FIND−S算法输出的是
H
H
H中能够拟合训练样例的多个假设中的一个；
候选消除算法中，输出的是与训练样例一致的所有假设的集合
列表后消除算法（LIST-THEN-ELIMINATE）
列表后消除算法
1、变型空间
V
e
r
s
i
o
n
S
p
a
c
e
←
VersionSpace \leftarrow
VersionSpace← 包含
H
H
H中所有假设的列表
2、对每个训练样例
<
x
,
c
(
x
)
>
<x,c(x)>
<x,c(x)>
从变型空间中逸出所有
h
(
x
)
≠
c
(
x
)
h(x) ≠ c(x)
h(x)=c(x)的假设
h
h
h
3、输出
V
e
r
s
i
o
n
S
p
a
c
e
VersionSpace
VersionSpace中的假设列表
使用变型空间的候选消除算法
1、将
G
G
G集合初始化为
H
H
H中极大一般假设 （例：
<
?
,
?
,
?
,
?
,
?
>
<?,?,?,?,?>
<?,?,?,?,?>）
将
S
S
S集合初始化为
H
H
H中极大特殊假设 （例：
<
∅
<\emptyset
<∅,
∅
\emptyset
∅,
∅
\emptyset
∅,
∅
\emptyset
∅,
∅
>
\emptyset>
∅>）
2、对每个训练样例
d
d
d，进行以下操作：
①如果
d
d
d是一正例
从
G
G
G中移去所有与
d
d
d不一致的假设；
对
S
S
S中每个与
d
d
d不一致的假设
s
s
s，从
S
S
S中移去
s
s
s；把
s
s
s的所有极小一般化式
h
h
h加入到
S
S
S中，其中
h
h
h与
d
d
d一致，且
G
G
G的某个成员比
h
h
h更一般；从
S
S
S中移去所有这样的假设：它比
S
S
S中另一假设更一般
②如果
d
d
d是一反例
从
S
S
S中移去所有与
d
d
d不一致的假设
对
G
G
G中每个与
d
d
d不一致的假设
g
g
g，从
G
G
G中移去
g
g
g；把
g
g
g的所有的极小特殊化式
h
h
h，加入到
G
G
G中，其中
h
h
h与
d
d
d一致，而且
S
S
S的某个成员比
h
h
h更特殊；从
G
G
G中移去所有这样的假设：它比
G
G
G中另一假设更特殊
e.g
初始化S0=
<
∅
<\emptyset
<∅,
∅
\emptyset
∅,
∅
\emptyset
∅,
∅
\emptyset
∅,
∅
>
\emptyset>
∅>
初始化G0=
<
?
,
?
,
?
,
?
,
?
>
<?,?,?,?,?>
<?,?,?,?,?>
①读入第一个例子
<
S
u
n
n
y
,
W
a
r
m
,
N
o
r
m
a
l
,
S
t
r
o
n
g
,
W
a
r
m
,
S
a
m
e
>
<Sunny,Warm,Normal,Strong,Warm,Same>
<Sunny,Warm,Normal,Strong,Warm,Same>，
E
n
j
o
y
S
p
o
r
t
=
Y
e
s
EnjoySport=Yes
EnjoySport=Yes，是正例
由于G中不存在与d不一致的假设，所以G1=G0
由于S0中的假设
<
∅
<\emptyset
<∅,
∅
\emptyset
∅,
∅
\emptyset
∅,
∅
\emptyset
∅,
∅
>
\emptyset>
∅>，与d不一致，所以先从S中移去该假设，并在S中加入更一般的假设
②读入<Sunny,Warm,High,Strong,Warm,Same>，EnjoySport=Yes，是正例
由于G1中不存在与d不一致的假设，所以G2=G1=G0
由于S1中的假设与d不一致，所以从S1中删除该假设，并在S中加入更一般的假设
③读入<Rainy,Cold,High,Strong,Warm,Change>，EnjoySport=No，是反例
由于S中不存在与d不一致的假设，S3=S2
由于G2的假设<?,?,?,?,?>与d不一致，从G2中移除该假设，并把g的所有极小特殊化式h加入到G中，且S中存在某个成员比h更特殊
④读入<Sunny,Warm,High,Strong,Cool,Change>，EnjoySport=Yes，是正例
由于G中删除假设<?,?,?,?,Same>
由于S3中的假设与d不一致，所以从S3中删除该假设，并在S3中加入更一般的假设
⇒
\Rightarrow
⇒ 最终的变型空间为：
中间那层为扩展
测试时采用投票法，如果两方投票相等，则类别未知