6533b827fe1ef96bd1285d33
RESEARCH PRODUCT
Probabilistic Logic under Coherence: Complexity and Algorithms
Veronica BiazzoThomas LukasiewiczGiuseppe SanfilippoAngelo Giliosubject
conditional probability assessmentSettore MAT/06 - Probabilita' E Statistica MatematicaDivergence-from-randomness modelalgorithmsprobabilistic logicConditional probability assessments; probabilistic logic; g-coherence; g-coherent entailment; complexity and algorithms.Artificial IntelligenceProbabilistic logic networkprobabilistic logic under coherenceConditional probability assessmentsProbabilistic analysis of algorithmsNon-monotonic logicconditional constraintMathematicsg-coherent entailmentConditional probability assessments probabilistic logic g-coherence g-coherent entailment complexity and algorithms.Reasoning systemcomputational complexitymodel-theoretic probabilistic logicApplied Mathematicscomplexity and algorithmsProbabilistic logiclogical constraintProbabilistic argumentationg-coherenceconditional probability assessment logical constraint conditional constraint probabilistic logic under coherence model-theoretic probabilistic logic g-coherence g-coherent entailment computational complexity algorithmsProbabilistic CTLalgorithms; computational complexity; conditional constraint; conditional probability assessment; g-coherence; g-coherent entailment; logical constraint; model-theoretic probabilistic logic; probabilistic logic under coherenceAlgorithmdescription
In previous work [V. Biazzo, A. Gilio, T. Lukasiewicz and G. Sanfilippo, Probabilistic logic under coherence, model-theoretic probabilistic logic, and default reasoning in System P, Journal of Applied Non-Classical Logics 12(2) (2002) 189---213.], we have explored the relationship between probabilistic reasoning under coherence and model-theoretic probabilistic reasoning. In particular, we have shown that the notions of g-coherence and of g-coherent entailment in probabilistic reasoning under coherence can be expressed by combining notions in model-theoretic probabilistic reasoning with concepts from default reasoning. In this paper, we continue this line of research. Based on the above semantic results, we draw a precise picture of the computational complexity of probabilistic reasoning under coherence. Moreover, we introduce transformations for probabilistic reasoning under coherence, which reduce an instance of deciding g-coherence or of computing tight intervals under g-coherent entailment to a smaller problem instance, and which can be done very efficiently. Furthermore, we present new algorithms for deciding g-coherence and for computing tight intervals under g-coherent entailment, which reformulate previous algorithms using terminology from default reasoning. They are based on reductions to standard problems in model-theoretic probabilistic reasoning, which in turn can be reduced to linear optimization problems. Hence, efficient techniques for model-theoretic probabilistic reasoning can immediately be applied for probabilistic reasoning under coherence (for example, column generation techniques). We describe several such techniques, which transform problem instances in model-theoretic probabilistic reasoning into smaller problem instances. We also describe a technique for obtaining a reduced set of variables for the associated linear optimization problems in the conjunctive case, and give new characterizations of this reduced set as a set of non-decomposable variables, and using the concept of random gain.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2005-10-01 | Annals of Mathematics and Artificial Intelligence |