Honey, I shrunk the hypothesis space (through logical preprocessing)
本文介绍了一种利用答案集编程进行逻辑预处理的方案，通过从归纳逻辑编程系统的假设空间中剔除不可能规则，从而在保持跨领域预测准确性的同时大幅缩短学习时长。
原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。 阅读完整免责声明
想象一下，你正在教一个机器人如何玩一款新游戏。你给机器人一本规则书（背景知识）以及一些关于好棋和坏棋的示例（训练数据）。机器人的任务是编写一套属于自己的规则来赢得游戏。
问题在于，机器人过于急切。它试图写出它能想到的每一个可能的规则，甚至包括那些明显荒谬的。它可能会尝试写出一条规则：“如果一个数字既是偶数又是奇数，那么你就赢了。”由于没有任何数字既是偶数又是奇数，这条规则毫无用处。但机器人此时还并不知道这一点，因此它浪费数小时去检查它。
本文介绍了一种巧妙的“预检查”系统，称为Shrinker。将 Shrinker 想象成一位非常严格的编辑，在机器人开始编写之前就审视其规则书。这位编辑会说：“停！我们确切知道，基于我们所处宇宙的规则，某些词语组合永远无法成立。让我们立即将这些划掉，以免机器人浪费时间。”
以下是论文如何运用四种类型的“无用规则”来解释这一剔除过程：
1. 不可能规则（不可满足）
想象一条规则说：“如果一个正方形是圆的，那么你就赢了。”
在我们的世界里，正方形绝不可能是圆的。这是一种逻辑上的不可能。
类比： 这就像试图用水来建造房屋。无论你多么努力，它永远无法立起来。
Shrinker 的做法： 它审视背景知识（我们已知为真的事实），并意识到：“嘿，‘正方形’和‘圆形’是互斥的。”它在机器人考虑这些规则之前，就删除了任何试图将它们结合起来的规则。
2. 冗余规则（蕴含可约）
想象一条规则说：“如果一个数字是大于 2 的质数，并且它是奇数，那么你就赢了。”
好吧，如果一个数字是大于 2 的质数，它必然是奇数。你不需要再说“并且它是奇数”，因为这已经蕴含在其中了。这就像说：“如果你是一个单身汉，并且你未婚，那么你就赢了。”成为单身汉就意味着你未婚。
类比： 这就像收拾行李箱，你放了一件“冬大衣”，然后又放了一件“厚夹克”，并说：“另外，我还需要一件厚夹克。”你只需要其中一件；第二件只是额外的负担。
Shrinker 的做法： 它识别出这些“额外负担”的词语并将其移除，使规则更简短，检查速度更快。
3. “一次性”规则（召回可约）
想象一条规则说：“如果一个人的母亲叫 Alice，并且同一个人的母亲叫 Bob，那么你就赢了。”
在现实世界中，一个人通常只有一位生物学母亲。如果背景知识表明一个人有一位母亲，那么这位母亲是唯一的。你不能为同一个位置指定两位不同的母亲。
类比： 这就像一把锁只有一把钥匙。如果你试图同时用两把不同的钥匙去开锁，你立刻就会知道出了问题。
Shrinker 的做法： 它计算事物发生的次数。如果它知道一个人只能有一位母亲，它就会删除任何试图为同一个人列出两位不同母亲的规则。
4. “恒真”规则（单例可约）
想象一条规则说：“如果一个列表有长度，那么你就赢了。”
好吧，每个列表都有长度。这是生活的事实。检查一个列表是否有长度，就像检查一条鱼是否有水一样。这总是成立的，因此它无助于区分获胜的棋步和失败的棋步。
类比： 这就像一名保安在检查一栋建筑是否有屋顶。每栋建筑都有屋顶，所以这项检查无法告诉保安这栋建筑是否安全。这是浪费时间。
Shrinker 的做法： 它识别出这些“恒真”的检查并将其移除，因为它们对决策过程没有任何价值。
结果：巨大的速度提升
论文在从视觉推理谜题到学习棋盘游戏规则的各种任务上测试了这位"Shrinker"编辑。
- 没有 Shrinker： 机器人（一种名为 Popper 的归纳逻辑编程系统）有时需要10 小时才能找到正确答案，因为它在数百万条无用、不可能或冗余的规则中筛选。
- 有了 Shrinker： 编辑仅花费10 秒就划掉了荒谬内容。随后，机器人只需搜索剩余的合理规则。在许多情况下，机器人仅用2 秒就找到了答案。
核心结论
论文声称，通过在学习开始之前利用逻辑推理清理规则书中的“垃圾”，他们可以将学习过程加快高达1,800 倍，而不会损失任何准确性。他们证明，他们从未丢弃任何“好”规则；他们只丢弃那些绝不可能成为最佳解决方案的“坏”规则。
文中提到的重要局限性：
论文指出，这种方法在背景知识有限（如事实列表）且假设未写入的内容为假（“封闭世界”）时效果最佳。如果世界是无限的或充满噪声的，这位特定的编辑可能会感到困惑。但在他们测试的任务中，这是一个巨大的成功。
您所在领域的论文太多了？
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要，使用您的语言。