Project

Discipline

graphical models; credal networks; imprecise probability; updating algorithm; credal classification; decision networks; algorithms; decision theory; classification

Lead
Lay summary
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.

Direct link to Lay Summary

Last update: 21.02.2013

Title	Year

Number	Title	Start	Funding scheme

Graph-based approaches to uncertainty and statistics usually fall under the headline of graphical models. These are very important, and widespread, models in Artificial Intelligence. In this proposal we focus on Bayesian networks, decision nets, and in particular on credal networks (Section 2.1.1).Bayesian networks mix graph and probabilities in order to compute inferences under uncertainty. Decision nets can be regarded as Bayesian nets extended to deal with decisions. These are precise-probability graphical models, in the sense that the probabilities used to build the model, as well as the probabilities computed by the model, cannot be subject to imprecision. Credal networks are instead an imprecise probability model: i.e., a credal net can be regarded as a set of Bayesian networks, or, in turn, a set of joint mass functions.Credal networks are very expressive models compared to Bayesian networks. Our research, for example, has shown that credal nets nicely unify a number of models and problems [11,8]. Moreover, credal nets have applications in pattern classification: the supervised data-mining task of learning a model from data that is later used to assign new objects to one of a number of pre-established categories. In this case, credal nets have given rise to the new paradigm called credal classification, which is important to do reliable predictions. 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. On our view, this is the most urgent problem to address in the field of credal nets. (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 (these two aspects are related as doing classification can be regarded as a special decision problem). (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, because we have not yet a clear and principled metric to empirically measure their performance. This is a fundamental problem credal classification is experiencing, and one that is very urgent, too, to give it credibility.By this proposal we want to overcome these problems, according to the following plan.(1) We will develop a fully polynomial-time approximation scheme (FPTAS) for credal networks (with bounded treewidth, and bounded maximum number of states per variable; see Section 2.3.1). We believe this algorithm, which has long been searched for, will be a turning point for research on credal networks: it will scale down the computational complexity of credal networks to a level (bigger, but still) similar to that of Bayesian networks. We will give both a theoretical proof and numerical experiments to show that the theoretical claims are effective in practice.(2) We will use the new algorithm to solve complex decision-theoretic problems and investigate applications to game theory (Section 2.3.2).(3) 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 (see Section 2.3.3). 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. Experimental tests will be carried out to validate the metric.