## Contact

Swiss National Science Foundation (SNSF)

Wildhainweg 3P.O. Box

CH-3001 Bern

Phone +41 31 308 22 22

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 |

Discipline |
---|

Information Technology |

Mathematics |

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 |

Name | Institute |
---|

Name | Institute |
---|

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 |

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

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.

Swiss National Science Foundation (SNSF)

Wildhainweg 3P.O. Box

CH-3001 Bern

Phone +41 31 308 22 22

Enter and manage your applications

Receive the latest news from us regularly with the SNSF Newsletter.

Continue© SNSF 2021