Probabilistic Constraint Logic Theories

Probabilistic logic models are used ever more often to deal with the uncertain relations typical of the real world. However, these models usually require expensive inference procedures. Very recently the problem of identifying tractable languages has come to the fore. In this paper we consider the models used by the learning from interpretations ILP setting, namely sets of integrity constraints, and propose a probabilistic version of them. A semantics in the style of the distribution semantics is adopted, where each integrity constraint is annotated with a probability. These probabilistic constraint logic models assign a probability of being positive to interpretations. This probability can be computed in a time that is logarithmic in the number of ground instantiations of violated constraints. This formalism can be used as the target language in learning systems and for declaratively specifying the behavior of a system. In the latter case, inference corresponds to computing the probability of compliance of a system's behavior to the model.