Project

Back to overview

Credal networks made easy

English title Credal networks made easy
Applicant Zaffalon Marco
Number 134759
Funding scheme Project funding (Div. I-III)
Research institution Istituto Dalle Molle di studi sull’Intelligenza Artificiale (IDSIA) IDSIA USI-SUPSI
Institution of higher education University of Applied Sciences and Arts of Southern Switzerland - SUPSI
Main discipline Information Technology
Start/End 01.04.2011 - 31.08.2013
Approved amount 134'079.00
Show all

All Disciplines (2)

Discipline
Information Technology
Mathematics

Keywords (9)

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

Lay Summary (English)

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

Responsible applicant and co-applicants

Employees

Awards

Title Year
"Best paper award" of the 12th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (http://www.projects.science.uu.nl/ecsqaru/) for the paper: "Approximating credal network inferences by linear programming" by Antonucci, A., de Campos, C.P., Huber, D., Zaffalon, M. 2013
"Google best student paper award" of the 29th conference on Uncertainty in Artificial Intelligence (http://auai.org/uai2013/) for the paper: "On the complexity of strong and epistemic credal networks" by Mauà, D., de Campos, C., Benavoli, A., Antonucci, A. 2013

Associated projects

Number Title Start Funding scheme
118071 Credal Model Averaging for dealing with uncertainty in environmental models 01.10.2008 Project funding (Div. I-III)
109295 Uncertain reasoning under incompleteness 01.10.2005 Project funding (Div. I-III)
132252 Multi Model Inference for dealing with uncertainty in environmental models 01.10.2010 Project funding (Div. I-III)
121785 Ignorance, caution and the naive credal classifier 01.01.2009 Project funding (Div. I-III)
116674 Unifying graphical models by credal networks: algorithms and applications 01.03.2008 Project funding (Div. I-III)
116674 Unifying graphical models by credal networks: algorithms and applications 01.03.2008 Project funding (Div. I-III)
146606 Robust structure learning of Bayesian networks 01.01.2014 Project funding (Div. I-III)
137680 Learning under near-ignorance: models and methods 01.01.2012 Project funding (Div. I-III)
162188 Statistical learning and inference on big data with probabilistic graphical models 01.01.2016 South Korea
67961 Investigations on the theory and practice of credal classification 01.04.2003 Project funding (Div. I-III)

Abstract

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.
-