论文标题
有条件的概率逻辑，提升贝叶斯网络以及几乎确定的量词消除
Conditional probability logic, lifted bayesian networks and almost sure quantifier elimination
论文作者
论文摘要
我们引入了一种形式的逻辑语言，称为条件概率逻辑（CPL），该语言扩展了一阶逻辑并可以表达概率，条件概率以及可以比较条件概率的概率。从直觉上讲，尽管正式细节是不同的，但CPL可以表达与人工智能界所考虑的某些语言相同的陈述。我们还考虑了一种精确概念提升贝叶斯网络的概念的方法，在该贝叶斯网络中，该概念是一种用于机器学习，数据挖掘和人工智能的概率图形模型。一个自然而然的贝叶斯网络（从此处定义的意义上）确定了所有结构集（在一阶逻辑的意义上）的概率分布，该概率分布均以通用的有限域$ d $。我们的主要结果是，对于每个“非关键” cpl-Formula $φ（\ bar {x}）$，都有一个无量词的公式$φ^*（\ bar {x}）$，“几乎肯定是“等同于$φ（\ bar {x}）$作为$ d $的cartinatity $ d $ to infinity to infinity to infinity to infinity to infinity to infinity to infinity to infinity to infinity to Interinity to Interinity to infinity。 This is relevant for the problem of making probabilistic inferences on large domains $D$, because (a) the problem of evaluating, by "brute force", the probability of $φ(\bar{x})$ being true for some sequence $\bar{d}$ of elements from $D$ has, in general, (highly) exponential time complexity in the cardinality of $D$, and (b) the corresponding probability for the无量词$φ^*（\ bar {x}）$仅取决于提起的贝叶斯网络，而不取决于$ d $。主要结果有两种推论，其中之一是非监视CPL形式的收敛定律（和零法则）。
We introduce a formal logical language, called conditional probability logic (CPL), which extends first-order logic and which can express probabilities, conditional probabilities and which can compare conditional probabilities. Intuitively speaking, although formal details are different, CPL can express the same kind of statements as some languages which have been considered in the artificial intelligence community. We also consider a way of making precise the notion of lifted Bayesian network, where this notion is a type of (lifted) probabilistic graphical model used in machine learning, data mining and artificial intelligence. A lifted Bayesian network (in the sense defined here) determines, in a natural way, a probability distribution on the set of all structures (in the sense of first-order logic) with a common finite domain $D$. Our main result is that for every "noncritical" CPL-formula $φ(\bar{x})$ there is a quantifier-free formula $φ^*(\bar{x})$ which is "almost surely" equivalent to $φ(\bar{x})$ as the cardinality of $D$ tends towards infinity. This is relevant for the problem of making probabilistic inferences on large domains $D$, because (a) the problem of evaluating, by "brute force", the probability of $φ(\bar{x})$ being true for some sequence $\bar{d}$ of elements from $D$ has, in general, (highly) exponential time complexity in the cardinality of $D$, and (b) the corresponding probability for the quantifier-free $φ^*(\bar{x})$ depends only on the lifted Bayesian network and not on $D$. The main result has two corollaries, one of which is a convergence law (and zero-one law) for noncritial CPL-formulas.
