迭代发现定义向量条件的布尔规则的算法

Question

我感兴趣的是找到一种算法来迭代地发现定义向量条件的布尔规则。例如，假设向量是一本书中的所有字母，该规则旨在告诉你这本书是否是James Joyce写的，但我们不知道规则是什么，我们想要发现它。对于任何提交的向量，规则引擎将始终回答True或False。因此，例如，如果我们提交一个包含"Ulysses“中所有字符的向量数组，那么引擎可能会响应"True"，如果规则是一个好的规则。

因此，假设我们将“尤利西斯”分成两半，A和B，并将每一半分别提交给引擎。引擎对A的回答是True，但对B的回答是False。由此我们可以推断，无论规则寻找的是什么，都只能在A中找到。因此，现在我们再次将A分为两部分，A1和A2。这一次，引擎对这两个变量都显示为False。现在，我们可以推断规则中一定有AND条件，并且and条件的一个原子必须在A1中，另一个原子在A2中。例如，规则可能是：“如果向量中有单词'meatjuice‘和'carracarracarra’，则返回True。这与我们的测试结果一致，因为"meatjuice”在本书的第一个季度，而"carracarracarra“在第二个季度。”

通过连续划分我们的文本并重新提交给引擎，我们最终可以发现引擎正在使用的隐藏规则。

我怀疑已经有一种算法可以做到这一点，但我不知道它叫什么，也不知道如何找到它。

Answer 1

我将这个问题描述为使用成员查询学习单调DNF公式。Angluin (Queries and Concept Learning，1988)给出了一个与你的算法类似的算法，但它使用等价查询(即找到当前假设不起作用的示例)以及成员查询。另一个问题是，找到最后一个术语可能需要相当长的时间。例如，假设规则是

   (A1 && B1) || (A2 && B1) || ... || (An && B1)
|| (A1 && B2) || (A2 && B2) || ... || (An && B2)
|| (B1 && B2).

由前两行组成的假设仅与2^(n + 2)输入中恰好有一行的规则不同。