Horn Approximations of Empirical Data
Horn Approximations of Empirical Data
复制标题
经验数据的霍恩近似
DOI：
10.1016/0004-3702(94)00072-9
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
B. Selman
中科院分区：
文献类型：
--
作者：
Henry A. Kautz;M. Kearns;B. Selman
正式的人工智能系统通常使用逻辑公式表示知识。然而，有时候，基于模型的表示比相应的基于公式的表示更紧凑，能够更快地进行推理。我们工作背后的中心思想是通过特征模型的子集来表示一个大的模型集。更具体地说，我们研究了霍恩理论的基于模型的表示，并表明存在可以由指数较小的特征模型集精确表示的大型霍恩理论。我们表明，基于一组特征模型的演绎只需要多项式时间，就像使用霍恩理论一样。更令人惊讶的是，使用一组特征模型可以在多项式时间内执行溯因，而使用Horn理论的溯因是np完全的。最后，我们讨论了生成最接近一般模型集的Horn理论的有效表示的算法。
Formal AI systems traditionally represent knowledge using logical formulas. Sometimes, however, a model-based representation is more compact and enables faster reasoning than the corresponding formula-based representation. The central idea behind our work is to represent a large set of models by a subset of characteristic models. More specifically, we examine model-based representations of Horn theories, and show that there are large Horn theories that can be exactly represented by an exponentially smaller set of characteristic models. We show that deduction based on a set of characteristic models requires only polynomial time, as it does using Horn theories. More surprisingly, abduction can be performed in polynomial time using a set of characteristic models, whereas abduction using Horn theories is NP-complete. Finally, we discuss algorithms for generating efficient representations of the Horn theory that best approximates a general set of models.