zbMATH — the first resource for mathematics

First-order probabilistic conditional logic and maximum entropy. (English) Zbl 1257.68133
The paper starts by pointing out the weaknesses of various formalisms that combine fragments of first-order logic and probability. Then the author introduces FO-PCL (first-order probabilistic conditional logic). The theories under consideration are referred to as knowledge bases, defined as finite pairs of the form \((\psi\wedge C\rightarrow\phi,\xi)\) with \(\xi\in[0,1]\) (the conditional probability), and \(\psi\) (the premise), \(C\) (the constraint) and \(\phi\) (the conclusion) formulas over a multi-sorted first-order language having no function symbol of arity 1 or more and having at most finitely many constants (\(\psi\) and \(\phi\) are omitted when they would be tautologies), and such that 5mm
all variables which occur free in \(C\) occur free in \(\psi\) or \(\phi\);
\(\psi\) and \(\varphi\) are Boolean combinations of atomic formulas, equality excluded;
\(C\) is a Boolean combination of equalities.
The following example is provided, which captures that one normally does not have a cold, but there is a small chance to catch one if one is susceptible to it, and a significant chance if one is in contact with someone who has it: \[ \begin{aligned} &(\text{cold}(U),0.01)\\ &(\text{susceptible}(U)\rightarrow\text{cold}(U), 0.1)\\ &(\text{cold}(V)\wedge\text{contact}(U,V)\wedge U\neq V\rightarrow\text{cold}(U), 0.6) \end{aligned} \] The semantics is defined w.r.t. the Herbrand interpretations, with a probabilistic distribution defined on the Herbrand base (the set of closed atoms). A probabilistic structure of this kind is a model of a knowledge base \(B\) if for all members \((\psi\wedge C\rightarrow\phi,\xi)\) of \(B\) and for all closed instances \(\overline{\psi}\wedge\overline{C}\rightarrow\overline{\phi}\) of \(\psi\wedge C\rightarrow\phi\), if \(\overline{C}\) is true in all Herbrand structures (where different constants denote different individuals) then the probability of \(\overline{\psi}\wedge\overline{\phi}\) is equal to \(\xi\) times the probability of \(\overline{\psi}\). The set of models of a knowledge base is a convex set, and the principle of maximal entropy is used to get the most unbiased model. This model is hard to compute in full generality, and the rest of the paper examines when and how the computation can be simplified, taking advantage of syntactic properties. The basic idea is to exploit the fact that some pairs of constants are equivalent w.r.t. the relations they have to themselves and to the other constants. The cold example illustrates the ideal situation of ‘parametric uniformity’, where for all members \((\psi\wedge C\rightarrow\phi,\xi)\) of \(B\), all closed instances \(\overline{\psi}\wedge\overline{C}\rightarrow\overline{\phi}\) of \(\psi\wedge C\rightarrow\phi\) such that \(\overline{C}\) is true in all Herbrand structures receive the same entropy-optimal parameter value. A different situation is illustrated with the ‘misanthrope’ example, which captures that people usually like those who like them, except for the misanthrope \(a\): \[ \begin{aligned} &(\text{likes}(a,V),0.05)\\ &(\text{likes}(U,V)\wedge U\neq V\rightarrow\text{likes}(V,U), 0.9) \end{aligned} \] If \(b\) and \(c\) are individuals, then \(b\) and \(c\) can be interchanged and have the same relations to themselves and to the other constants, whereas \(a\) cannot be interchanged with either \(b\) or \(c\), so there is only limited ‘parametric uniformity’.

68T27 Logic in artificial intelligence
68T37 Reasoning under uncertainty in the context of artificial intelligence
03B48 Probability and inductive logic
68T30 Knowledge representation
Full Text: DOI