An Improved Algorithm for Learning to Perform Exception-Tolerant Abduction
An Improved Algorithm for Learning to Perform Exception-Tolerant Abduction
复制标题
一种改进的学习执行异常容忍推断的算法
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Brendan Juba
中科院分区：
文献类型：
--
作者：
Mengxue Zhang;Tushar Mathew;Brendan Juba
从观察到的或假设的情况推断出这种情况的合理原因或解释被称为外展。对于许多任务，通过机器学习获取必要的知识已被广泛发现是非常有效的。然而，学到的知识的语义比通常的经典语义弱，这需要新的配方的许多任务。我们专注于最近推出的制定的溯因推理任务，从而适应机器学习的语义。一个关键问题是，我们不能期望我们的原因或解释是完美的，它们必须容忍一些错误，因为世界比我们的形式化所允许的要复杂得多。这是资格问题的一个版本，在机器学习中，这被称为不可知学习。在Juba的工作中，引入了学习进行溯因推理的任务，给出了一个算法来产生容忍这种例外的k-DNF解释：如果最佳可能的k-DNF解释不能以概率ε证明条件，则该算法被保证找到不能以至多O（nkε）的概率证明条件的k-DNF解释，其中n是用于描述域的命题属性的数量。在这里，我们提出了一个改进的算法，这项任务。当最好的k-DNF以概率ε失败时，我们的算法找到以最多O（nk/2ε）的概率失败的k-DNF（即，抑制n和1/ε中的对数因子）。我们还研究了这种新算法的经验优势，在两个测试域，一个解释条件产生的“嘈杂”的k-DNF规则，另一个解释条件，实际上是由一个线性阈值规则产生的。
Inference from an observed or hypothesized condition to a plausible cause or explanation for this condition is known as abduction. For many tasks, the acquisition of the necessary knowledge by machine learning has been widely found to be highly effective. However, the semantics of learned knowledge are weaker than the usual classical semantics, and this necessitates new formulations of many tasks. We focus on a recently introduced formulation of the abductive inference task that is thus adapted to the semantics of machine learning. A key problem is that we cannot expect that our causes or explanations will be perfect, and they must tolerate some error due to the world being more complicated than our formalization allows. This is a version of the qualification problem, and in machine learning, this is known as agnostic learning. In the work by Juba that introduced the task of learning to make abductive inferences, an algorithm is given for producing k-DNF explanations that tolerates such exceptions: if the best possible k-DNF explanation fails to justify the condition with probability ε, then the algorithm is promised to find a k-DNF explanation that fails to justify the condition with probability at most O(nkε), where n is the number of propositional attributes used to describe the domain. Here, we present an improved algorithm for this task. When the best k- DNF fails with probability ε, our algorithm finds a k-DNF that fails with probability at most O ̃(nk/2ε) (i.e., suppressing logarithmic factors in n and 1/ε). We also examine the empirical advantage of this new algorithm over the previous algorithm in two test domains, one of explaining conditions generated by a “noisy” k-DNF rule, and another of explaining conditions that are actually generated by a linear threshold rule.