Probabilistic Logic under Coherence: Complexity and Algorithms
Veronica Biazzo‚ Angelo Gilio‚ Thomas Lukasiewicz and Giuseppe Sanfilippo
We study probabilistic logic under the viewpoint of the coherence principle of de Finetti. In detail, we explore the relationship between coherence-based and classical model-theoretic probabilistic logic. Interestingly, we show that the notions of g-coherence and of g-coherent entailment can be expressed by combining notions in model-theoretic probabilistic logic with concepts from default reasoning. Using these results, we analyze the computational complexity of probabilistic reasoning under coherence. Moreover, we present new algorithms for deciding g-coherence and for computing tight g-coherent intervals, which reduce these tasks to standard reasoning tasks in model-theoretic probabilistic logic. Thus, efficient techniques for model-theoretic probabilistic reasoning can immediately be applied for probabilistic reasoning under coherence, for example, column generation techniques. We then describe two other interesting techniques for efficient model-theoretic probabilistic reasoning in the conjunctive case.