×

zbMATH — the first resource for mathematics

Approximate credal network updating by linear programming with applications to decision making. (English) Zbl 1328.68225
Summary: Credal nets are probabilistic graphical models which extend Bayesian nets to cope with sets of distributions. An algorithm for approximate credal network updating is presented. The problem in its general formulation is a multilinear optimization task, which can be linearized by an appropriate rule for fixing all the local models apart from those of a single variable. This simple idea can be iterated and quickly leads to accurate inferences. A transformation is also derived to reduce decision making in credal networks based on the maximality criterion to updating. The decision task is proved to have the same complexity of standard inference, being NP\(^{\mathrm{PP}}\)-complete for general credal nets and NP-complete for polytrees. Similar results are derived for the E-admissibility criterion. Numerical experiments confirm a good performance of the method.

MSC:
68T37 Reasoning under uncertainty in the context of artificial intelligence
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
90C05 Linear programming
91B06 Decision theory
Software:
LibDAI
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Antonucci, A.; de Campos, C., Decision making by credal nets, (Proceedings of the International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC 2011), vol. 1, (2011), IEEE Hangzhou (China)), 201-204
[2] Cozman, F. G., Credal networks, Artif. Intell., 120, 199-233, (2000) · Zbl 0945.68163
[3] Pearl, J., Probabilistic reasoning in intelligent systems: networks of plausible inference, (1988), Morgan Kaufmann
[4] Shafer, G., A mathematical theory of evidence, (1976), Princeton University Press · Zbl 0359.62002
[5] Dubois, D.; Prade, H., Possibility theory: an approach to computerized processing of uncertainty, (1988), Plenum Press New York
[6] de Campos, C. P.; Cozman, F. G., Inference in credal networks using multilinear programming, (Proceedings of the Second Starting AI Researcher Symposium, (2004), IOS Press Amsterdam), 50-61
[7] de Campos, C. P.; Cozman, F. G., The inferential complexity of Bayesian and credal networks, (Proceedings of the 19th International Joint Conference on Artificial Intelligence, Edinburgh, (2005)), 1313-1318
[8] Koller, D.; Friedman, N. N., Probabilistic graphical models: principles and techniques, (2009), MIT Press
[9] da Rocha, J. C.F.; Cozman, F. G.; de Campos, C. P., Inference in polytrees with sets of probabilities, (Proceedings of the 19th Conference on Uncertainty in Artificial Intelligence, (2003)), 217-224
[10] Cano, A.; Gomez, M.; Moral, S.; Abellán, J., Hill-climbing and branch-and-bound algorithms for exact and approximate inference in credal networks, Int. J. Approx. Reason., 44, 3, 261-280, (2007) · Zbl 1116.68080
[11] de Campos, C. P.; Cozman, F. G., Inference in credal networks through integer programming, (Proceedings of the Fifth International Symposium on Imprecise Probability: Theories and Applications, Prague, (2007)), 145-154
[12] Antonucci, A.; Yi, S.; de Campos, C.; Zaffalon, M., Generalized loopy 2U: a new algorithm for approximate inference in credal networks, Int. J. Approx. Reason., 51, 5, 474-484, (2010)
[13] Mauá, D.; de Campos, C.; Zaffalon, M., Updating credal networks is approximable in polynomial time, Int. J. Approx. Reason., 53, 8, 1183-1199, (2012) · Zbl 1266.68178
[14] de Cooman, G.; Hermans, F.; Antonucci, A.; Zaffalon, M., Epistemic irrelevance in credal nets: the case of imprecise Markov trees, Int. J. Approx. Reason., 51, 9, 1029-1052, (2010) · Zbl 1348.68248
[15] Walley, P., Statistical reasoning with imprecise probabilities, (1991), Chapman and Hall · Zbl 0732.62004
[16] Levi, I., The enterprise of knowledge, (1980), MIT Press London
[17] Troffaes, M. C.M., Decision making under uncertainty using imprecise probabilities, Int. J. Approx. Reason., 45, 1, 17-29, (2007) · Zbl 1119.91028
[18] Antonucci, A.; Zaffalon, M., Decision-theoretic specification of credal networks: a unified language for uncertain modeling with sets of Bayesian networks, Int. J. Approx. Reason., 49, 2, 345-361, (2008) · Zbl 1191.68670
[19] Lukatskii, A. M.; Shapot, D. V., Problems in multilinear programming, Comput. Math. Math. Phys., 41, 5, 638-648, (2000) · Zbl 1044.90077
[20] Glover, F.; Kochenberger, G., Handbook of metaheuristics, International Series in Operations Research & Management Science, (2003), Kluwer Academic Publishers · Zbl 1058.90002
[21] Mauá, D.; de Campos, C.; Benavoli, A.; Antonucci, A., Probabilistic inference in credal networks: new complexity results, J. Artif. Intell. Res., 50, 603-637, (2014) · Zbl 1366.68329
[22] Charnes, A.; Cooper, W., Programs with linear fractional functions, Nav. Res. Logist. Q., 9, 181-196, (1962) · Zbl 0127.36901
[23] Mauá, D.; de Campos, C.; Zaffalon, M., The complexity of approximately solving influence diagrams, (Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence (UAI 2012), (2012)), 604-613
[24] Avis, D., Lrs: a revised implementation of the reverse search vertex enumeration algorithm, (Polytopes - Combinatorics and Computation, DMV Seminar Band 29, (2000)), 177-198 · Zbl 0960.68171
[25] Wallner, A., Extreme points of coherent probabilities in finite spaces, Int. J. Approx. Reason., 44, 3, 339-357, (2007) · Zbl 1114.60010
[26] de Bock, J.; de Cooman, G., Credal networks under epistemic irrelevance: the sets of desirable gambles approach, Int. J. Approx. Reason., 56 Part B, 178-207, (2015) · Zbl 1388.68264
[27] Cozman, F. G.; de Campos, C. P., Kuznetsov independence for interval-valued expectations and sets of probability distributions: properties and algorithms, Int. J. Approx. Reason., 55, 2, 666-682, (2014) · Zbl 1316.68174
[28] Corani, G.; Abellán, J.; Masegosa, A.; Moral, S.; Zaffalon, M., Classification, (Augustin, T.; Coolen, F.; de Cooman, G.; Troffaes, M., Introduction to Imprecise Probabilities, (2014), Wiley), 261-285
[29] Corani, G.; Antonucci, A.; Zaffalon, M., Bayesian networks with imprecise probabilities: theory and application to classification, (Holmes, D.; Jain, L., Data Mining: Foundations and Intelligent Paradigms, Intelligent Systems Reference Library, vol. 23, (2012), Springer Berlin/Heidelberg), 49-93 · Zbl 1231.68194
[30] Antonucci, A.; de Campos, C.; Zaffalon, M., Probabilistic graphical models, (Augustin, T.; Coolen, F.; de Cooman, G.; Troffaes, M., Introduction to Imprecise Probabilities, (2014), Wiley), 207-229 · Zbl 1298.68262
[31] Mooij, J. M., Libdai: a free and open source C++ library for discrete approximate inference in graphical models, J. Mach. Learn. Res., 11, 2169-2173, (2010) · Zbl 1242.62004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.