search - Find-S/候选消除算法的训练样例最少数量？

Question

考虑由 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算法什么时候才能说目标概念被准确学习，最优的查询策略是什么？

我还想知道候选人淘汰的答案。

提前致谢。

Answer 1

您需要两个正面示例:(2,6)(2 <= x <= 2, 6 <= y <= 6)然后 (4,9)(2 <= x <= 4, 6 <= y <= 9)这就是 S 集的完成，这是 FIND-S 教学/学习的答案的结束

通过候选消除，我们需要给出反例来构建G集。我们需要四个反例来定义矩形的四个边界:

• G 开头为 (-Inf <= x <= Inf, -Inf <= y <= Inf)

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

• (-Inf <= x <= Inf, 6 <= y <= Inf)

添加 (3,10)-

• (-Inf <= x <= Inf, 6 <= y <= 9)

添加 (1,7)-

• (2 <= x <= Inf, 6 <= y <= 9)

添加 (5,7)-

• (2 <= x <= 4, 6 <= y <= 9)

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

这是输入训练示例的最佳顺序。最糟糕的顺序是首先执行 G 集，因为您将创建四个不同的候选假设，这些假设将与第二个示例合并为三个，然后与第三个示例合并为一个。像米切尔书中那样用树来说明 C-E 是很有用的，也许还可以在每个树旁边画出假设图。

这个答案在这里得到了确认: http://ssdi.di.fct.unl.pt/scl/docs/exercises/Clemens%20Dubslaff%20hm4.pdf