Mauá, Denis Deratani and De Campos, Cassio Polpo and Benavoli, Alessio and Antonucci, Alessandro (2013) On the Complexity of Strong and Epistemic Credal Networks. In: 29th Conference on Uncertainty in Artificial Intelligence (UAI).
Full text not available from this repository.Abstract
Credal networks are graph-based statistical models whose parameters take values on a set, instead of being sharply specified as in traditional statistical models (e.g., Bayesian networks). The result of inferences with such models depends on the irrelevance/independence concept adopted. In this paper, we study the computational complexity of inferences under the concepts of epistemic irrelevance and strong independence. We strengthen complexity results by showing that inferences with strong independence are NP-hard even in credal trees with ternary variables, which indicates that tractable algorithms, including the existing one for epistemic trees, cannot be used for strong independence. We prove that the polynomial time of inferences in credal trees under epistemic irrelevance is not likely to extend to more general models, because the problem becomes NP-hard even in simple polytrees. These results draw a definite line between networks with efficient inferences and those where inferences are hard, and close several open questions regarding the computational complexity of such models.
| Item Type: | Article in conference proceedings or Presentation at a conference (Paper) |
|---|---|
| Additional Information: | (best student paper award, top 11% papers, plenary presentation) |
| Subjects: | Computer sciences |
| Department/unit: | Dipartimento tecnologie innovative > Istituto Dalle Molle di studi sull'intelligenza artificiale |
| Depositing User: | Cassio Polpo De Campos |
| Date Deposited: | 13 Mar 2014 14:35 |
| Last Modified: | 14 Mar 2014 06:43 |
| URI: | http://repository.supsi.ch/id/eprint/3909 |
Actions (login required)
 |
View Item |