问Find-S/候选淘汰算法的最小训练样本数？

EN

您需要两个正面示例：( 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指定了问题域，则将其替换为0，将Inf替换为10。

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

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

假设所有的范围都是a ≤ x ≤ b，a和b都是整数，那么...

在一维的情况下(只有x)，将有4个样本(a-1，a，b，b+1)可以证明这一点。

如果将其扩展到2维(x和y)，则应该是16个样本，即上面的x和y的(c-1，c，d，d+1)，以及所有可能的组合。

如果我不理解这个问题，请纠正我。