15th European Conference on Artificial Intelligence
  July 21-26 2002     Lyon     France  

ECAI-2002 Conference Paper

[PDF] [full paper] [prev] [tofc] [next]

Approximating Propositional Knowledge with Affine Formulas

Bruno Zanuttini

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.

Keywords: Knowledge Representation, Knowledge Acquisition, Machine Learning

Citation: Bruno Zanuttini: Approximating Propositional Knowledge with Affine Formulas. In F. van Harmelen (ed.): ECAI2002, Proceedings of the 15th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2002, pp.287-291.

[prev] [tofc] [next]

ECAI-2002 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the UniversitÚ Claude Bernard and INSA, Lyon, on behalf of Association Franšaise pour l'Intelligence Artificielle.