The computational complexity of sensitivity analysis and parameter tuning

Johan Kwisthout, Linda C. van der Gaag
Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, PMLR R6:349-356, 2008.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR6-kwisthout08a, title = {The computational complexity of sensitivity analysis and parameter tuning}, author = {Kwisthout, Johan and van der Gaag, Linda C.}, booktitle = {Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence}, pages = {349--356}, year = {2008}, editor = {McAllester, David A. and Myllymäki, Petri}, volume = {R6}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r6/main/assets/kwisthout08a/kwisthout08a.pdf}, url = {https://proceedings.mlr.press/r6/kwisthout08a.html}, 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.}, note = {Reissued by PMLR on 09 October 2024.} }
Endnote
%0 Conference Paper %T The computational complexity of sensitivity analysis and parameter tuning %A Johan Kwisthout %A Linda C. van der Gaag %B Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2008 %E David A. McAllester %E Petri Myllymäki %F pmlr-vR6-kwisthout08a %I PMLR %P 349--356 %U https://proceedings.mlr.press/r6/kwisthout08a.html %V R6 %X 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. %Z Reissued by PMLR on 09 October 2024.
APA
Kwisthout, J. & van der Gaag, L.C.. (2008). The computational complexity of sensitivity analysis and parameter tuning. Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R6:349-356 Available from https://proceedings.mlr.press/r6/kwisthout08a.html. Reissued by PMLR on 09 October 2024.

Related Material