Probabilistic Deduction with Conditional Constraints over Basic Events
<p>We show that probabilistic deduction with conditional constraints over basic events is NP-hard. We then focus on the special case of probabilistic deduction in conditional constraint trees. We elaborate very efficient and globally complete techniques for probabilistic deduction. More precis...
| Main Author: | |
|---|---|
| Format: | Conference item |
| Published: |
Morgan Kaufmann
1998
|
| _version_ | 1797083881976889344 |
|---|---|
| author | Lukasiewicz, T |
| author_facet | Lukasiewicz, T |
| author_sort | Lukasiewicz, T |
| collection | OXFORD |
| description | <p>We show that probabilistic deduction with conditional constraints over basic events is NP-hard. We then focus on the special case of probabilistic deduction in conditional constraint trees. We elaborate very efficient and globally complete techniques for probabilistic deduction. More precisely, for exact conditional constraint trees, we present a local approach to globally complete probabilistic deduction, which runs in linear time in the size of the conditional constraint trees. For general conditional constraint trees, we show that globally complete probabilistic deduction can be done by solving global nonlinear programs. We elaborate how these nonlinear programs can be transformed into equivalent linear programs, which are solvable in polynomial time in the size of the conditional constraint trees.</p> |
| first_indexed | 2024-03-07T01:47:46Z |
| format | Conference item |
| id | oxford-uuid:9901cc4d-b209-49cf-a55e-306f9a9a3ed2 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T01:47:46Z |
| publishDate | 1998 |
| publisher | Morgan Kaufmann |
| record_format | dspace |
| spelling | oxford-uuid:9901cc4d-b209-49cf-a55e-306f9a9a3ed22022-03-27T00:11:07ZProbabilistic Deduction with Conditional Constraints over Basic EventsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:9901cc4d-b209-49cf-a55e-306f9a9a3ed2Department of Computer ScienceMorgan Kaufmann1998Lukasiewicz, T<p>We show that probabilistic deduction with conditional constraints over basic events is NP-hard. We then focus on the special case of probabilistic deduction in conditional constraint trees. We elaborate very efficient and globally complete techniques for probabilistic deduction. More precisely, for exact conditional constraint trees, we present a local approach to globally complete probabilistic deduction, which runs in linear time in the size of the conditional constraint trees. For general conditional constraint trees, we show that globally complete probabilistic deduction can be done by solving global nonlinear programs. We elaborate how these nonlinear programs can be transformed into equivalent linear programs, which are solvable in polynomial time in the size of the conditional constraint trees.</p> |
| spellingShingle | Lukasiewicz, T Probabilistic Deduction with Conditional Constraints over Basic Events |
| title | Probabilistic Deduction with Conditional Constraints over Basic Events |
| title_full | Probabilistic Deduction with Conditional Constraints over Basic Events |
| title_fullStr | Probabilistic Deduction with Conditional Constraints over Basic Events |
| title_full_unstemmed | Probabilistic Deduction with Conditional Constraints over Basic Events |
| title_short | Probabilistic Deduction with Conditional Constraints over Basic Events |
| title_sort | probabilistic deduction with conditional constraints over basic events |
| work_keys_str_mv | AT lukasiewiczt probabilisticdeductionwithconditionalconstraintsoverbasicevents |