by Veronica Biazzo, Angelo Gilio, Thomas Lukasiewicz, Giuseppe Sanfilippo
Abstract:
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.
Reference:
Veronica Biazzo, Angelo Gilio, Thomas Lukasiewicz, Giuseppe Sanfilippo, "Probabilistic logic under coherence: complexity and algorithms.", In Ann. Math. Artif. Intell., vol. 45, no. 1-2, pp. 35-81, 2005.
Bibtex Entry:
@ARTICLE{2005BGLS-AMAI,
author = {Veronica Biazzo and Angelo Gilio and Thomas Lukasiewicz and Giuseppe
Sanfilippo},
title = {Probabilistic logic under coherence: complexity and algorithms.},
journal = {Ann. Math. Artif. Intell.},
year = {2005},
volume = {45},
pages = {35-81},
number = {1-2},
note = {ISSN 1012-2443},
abstract = {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.},
doi = {10.1007/s10472-005-9005-y},
issn = {1012-2443},
mrclass = {68T37 (03B48)},
mrnumber = {2220432 (2007a:68065)},
scopus = {{2-s2.0-32544435240}},
url = {http://dx.doi.org/10.1007/s10472-005-9005-y},
wos = {{WOS:000235267600003}}
}