Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
The Computational Complexity of Sensitivity Analysis and Parameter Tuning
Johan Kwisthout, Linda van der Gaag
Abstract:
While known algorithms for sensitivity analysis and parameter tuning in probabilistic networks have a running time that is exponential in the size of the network, the exact computational complexity of these problems has not been established as yet. In this paper we study several variants of the tuning problem and show that these problems are NPPP-complete in general. We further show that the problems remain NP-complete or PP-complete, for a number of restricted variants. These complexity results provide insight in whether or not recent achievements in sensitivity analysis and tuning can be extended to more general, practicable methods.
Keywords: null
Pages: 349-356
PS Link:
PDF Link: /papers/08/p349-kwisthout.pdf
BibTex:
@INPROCEEDINGS{Kwisthout08,
AUTHOR = "Johan Kwisthout and Linda van der Gaag",
TITLE = "The Computational Complexity of Sensitivity Analysis and Parameter Tuning",
BOOKTITLE = "Proceedings of the Twenty-Fourth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-08)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2008",
PAGES = "349--356"
}


hosted by DSL   •   site info   •   help