Approximating Propositional Knowledge with Affine Formulas
Approximating Propositional Knowledge with Affine Formulas
复制标题
用仿射公式逼近命题知识
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
B. Zanuttini
中科院分区：
文献类型：
--
作者：
B. Zanuttini
我们考虑使用仿射公式，即线性方程式模拟2的连接，以近似命题知识。这些公式非常接近CNF公式，并允许有效推理。此外，它们可以有效地最小化。我们表明，从示例中可以识别这类公式，可以识别pac-learnnn，即可以在多项式时间和最大的下界计算仿射的最小上限，并且在次指数时间内具有最大模型数量。所有这些结果都比Horn公式（通常被认为用于表示或近似命题知识）的结果更好。由于所有这些原因，我们认为仿射公式是近似命题知识的良好候选者。
We consider the use of affine formulas, i.e., conjonctions of linear equations modulo 2, for approximating propositional knowledge. These formulas are very close to CNF formulas, and allow for efficient reasoning; moreover, they can be minimized efficiently. We show that this class of formulas is identifiable and PAC-learnable from examples, that an affine least upper bound of a relation can be computed in polynomial time and a greatest lower bound with the maximum number of models in subexponential time. All these results are better than those for, e.g., Horn formulas, which are often considered for representing or approximating propositional knowledge. For all these reasons we argue that affine formulas are good candidates for approximating propositional knowledge.