Credal networks made easy

Graph-based approaches to uncertainty and statistics usually fall under the headline of graphical models. We focus in particular on Bayesian networks, decision nets, and credal networks. The former are precise probability models, the latter is based on imprecise probability (i.e., they can be regarded as sets of Bayesian nets). Credal networks are very expressive models. However, there are important open problems that limit the application of credal nets: (i) there is no truly efficient algorithm for credal nets that can give guarantees on the quality of the (approximate) solutions provided. (ii) Such an algorithm could lead to address and solve many important problems, such as decision-theoretic problems, and also to the development of new models for classification. (iii) When we focus in particular on classification, we find another key issue: we are limited in our understanding of the quality of the predictions made by credal classifiers (i.e., imprecise probability-based classifiers), because we have not yet a clear and principled metric to empirically measure their performance. By this proposal we want to overcome these problems, according to the following plan. - We will develop a fully polynomial-time approximation scheme for credal networks (with bounded treewidth, and bounded maximum number of states per variable). - We will use the new algorithm to solve complex decision-theoretic problems. - We will derive a principled new metric for credal classifiers. We will provide the first metric for credal classifiers that is derived from general principles and some reasonable assumptions . The metric will output a single number to measure the prediction of a classifier, and will apply to credal classifiers as well as to traditional classifiers.