Conditional probability logic, lifted Bayesian networks, and almost sure quantifier elimination (Q2215958)

This paper tackles a prediction problem on finite but growing domains. To this end, lifted Bayesian networks are defined, which allow for the specification of probability distributions on arbitrary large domains. The conditional probabilities of the lifted Bayesian networks are defined by expressions of a conditional probability logic, \(CPL\). The key ingredient to the defined logic \(CPL\) is a rule, that allows one to express, that the conditional probability of some sentence given some other sentence is greater or equal than a threshold plus some other such conditional probability. The main result of the paper is a theorem showing that for all sentences \(\varphi\) in a set of formulas of \(CPL\) there exist quantifier-free formulae \(\varphi^*\) which are almost surely equivalent to \(\varphi\). Furthermore, the \(\varphi^*\) do not depend on the size of the underlying domain and can be found by an effective algorithm. The run time of the algorithm is shown to be relatively low in many cases. The structure of the paper is entirely standard. The first two sections introduce the topic, problem and main notation. The third section states the main results, which are proved in the fourth section. Section 5 concludes by discussing future possible works and some connections to related areas of research.