Find-S/候选消除算法所需的最小训练样本数?

考虑实例空间为 x, y 平面上的整数点，其中 0 ≤ x, y ≤ 10，假设集由矩形构成（即形式为 (a ≤ x ≤ b, c ≤ y ≤ d)，其中 0 ≤ a, b, c, d ≤ 10）。

为了使 Find-S 算法能够完美学习到一个特定的目标概念（例如，(2 ≤ x ≤ 4, 6 ≤ y ≤ 9)），需要提供的最小训练样本数是多少？在 Find-S 算法的情况下，我们什么时候可以说目标概念被精确地学习到了？最佳的查询策略是什么？

我还想知道候选消除算法的答案。

提前感谢。

回答：

你需要两个正例：(2,6) (2 <= x <= 2, 6 <= y <= 6) 然后 (4,9) (2 <= x <= 4, 6 <= y <= 9)。这样就完成了 S 集合，这也是使用 FIND-S 进行教学/学习的答案的结尾。

对于候选消除算法，我们需要提供负例来构建 G 集合。我们需要四个负例来定义矩形的四个边界：

添加 (3,5)-，我们得到假设：

添加 (3,10)-

添加 (1,7)-

添加 (5,7)-

所以现在 S=G={(2 <= x <= 4, 6 <= y <= 9)}。由于 S=G，它已经完美地学习了该概念。我在不同的格式中见过这个问题。如果问题域指定了这一点，则将 -Inf 替换为 0，将 Inf 替换为 10。

这是输入训练样本的最佳顺序。最坏的顺序是首先构建 G 集合，因为您将创建四个不同的候选假设，它们将通过第二个示例合并为三个，然后通过第三个示例合并为一个。使用 Mitchell 书中的树来解释 C-E 很有用，也许可以在每个假设旁边绘制假设图。

学技术