Probabilistic Logic under Coherence: Complexity and Algorithms
<p>In previous work, 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 expres...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Published: |
2005
|
| _version_ | 1797071860840529920 |
|---|---|
| author | Biazzo, V Gilio, A Lukasiewicz, T Sanfilippo, G |
| author_facet | Biazzo, V Gilio, A Lukasiewicz, T Sanfilippo, G |
| author_sort | Biazzo, V |
| collection | OXFORD |
| description | <p>In previous work, 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.</p> |
| first_indexed | 2024-03-06T22:59:21Z |
| format | Journal article |
| id | oxford-uuid:618a33c3-a662-4ed7-8f68-5a67bc640244 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T22:59:21Z |
| publishDate | 2005 |
| record_format | dspace |
| spelling | oxford-uuid:618a33c3-a662-4ed7-8f68-5a67bc6402442022-03-26T18:00:41ZProbabilistic Logic under Coherence: Complexity and AlgorithmsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:618a33c3-a662-4ed7-8f68-5a67bc640244Department of Computer Science2005Biazzo, VGilio, ALukasiewicz, TSanfilippo, G<p>In previous work, 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.</p> |
| spellingShingle | Biazzo, V Gilio, A Lukasiewicz, T Sanfilippo, G Probabilistic Logic under Coherence: Complexity and Algorithms |
| title | Probabilistic Logic under Coherence: Complexity and Algorithms |
| title_full | Probabilistic Logic under Coherence: Complexity and Algorithms |
| title_fullStr | Probabilistic Logic under Coherence: Complexity and Algorithms |
| title_full_unstemmed | Probabilistic Logic under Coherence: Complexity and Algorithms |
| title_short | Probabilistic Logic under Coherence: Complexity and Algorithms |
| title_sort | probabilistic logic under coherence complexity and algorithms |
| work_keys_str_mv | AT biazzov probabilisticlogicundercoherencecomplexityandalgorithms AT gilioa probabilisticlogicundercoherencecomplexityandalgorithms AT lukasiewiczt probabilisticlogicundercoherencecomplexityandalgorithms AT sanfilippog probabilisticlogicundercoherencecomplexityandalgorithms |