机器学习
候选消除算法计算包含 H 中所有与观察到的训练示例序列一致的假设的版本空间。
- 将 G 初始化为 H 中最大一般假设的集合。
- 将 S 初始化为 H 中最大特殊假设的集合。
- 对于每个训练示例 d，执行以下操作：
- 如果 d 是正例：
- 从 G 中移除任何与 d 不一致的假设。
- 对于 S 中与 d 不一致的每个假设 s：
- 从 S 中移除 s。
- 向 S 中添加 s 的所有最小泛化 h，使得：
- h 与 d 一致；并且
- G 中的某个成员比 h 更一般。
- 从 S 中移除任何比 S 中另一个假设更一般的假设。
- 如果 d 是负例：
- 从 S 中移除任何与 d 不一致的假设。
- 对于 G 中与 d 不一致的每个假设 g：
- 从 G 中移除 g。
- 向 G 中添加 g 的所有最小特殊化 h，使得：
- h 与 d 一致；并且
- S 中的某个成员比 h 更特殊。
- 从 G 中移除任何比 G 中另一个假设更不一般的假设。
- 如果 d 是正例：
使用版本空间的候选消除算法
The CANDIDATE-ELIMINTION algorithm computes the version space containing all hypotheses
from H that are consistent with an observed sequence of training examples.
Initialize G to the set of maximally general hypotheses in H Initialize S to the set of maximally specific
hypotheses in H For each training example d, do
• If d is a positive example
•
Remove from G any hypothesis inconsistent with d
•
For each hypothesis s in S that is not consistent with d
•
Remove s from S
•
Add to S all minimal generalizations h of s such that
•
h is consistent with d, and some member of G is more general than h
•
Remove from S any hypothesis that is more general than another hypothesis in S
• If d is a negative example
• Remove from S any hypothesis inconsistent with d
• For each hypothesis g in G that is not consistent with d
• Remove g from G
•
Add to G all minimal specializations h of g such that
•
h is consistent with d, and some member of S is more specific than h
•
Remove from G any hypothesis that is less general than another hypothesis in G
CANDIDATE- ELIMINTION algorithm using version spaces