string - 迭代发现定义向量条件的 bool 规则的算法

Question

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

因此，假设我们将“Ulysses”分成两半，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) 输入中的一个输入的规则不同。