Conditional probability logic, lifted Bayesian networks, and almost sure quantifier elimination (Q2215958)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Conditional probability logic, lifted Bayesian networks, and almost sure quantifier elimination |
scientific article |
Statements
Conditional probability logic, lifted Bayesian networks, and almost sure quantifier elimination (English)
0 references
15 December 2020
0 references
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.
0 references
logic
0 references
finite model theory
0 references
almost sure elimination of quantifiers
0 references
artificial intelligence
0 references
machine learning
0 references
graphical models
0 references
0 references