FOURTH INTERNATIONAL SYMPOSIUM ON
IMPRECISE PROBABILITIES AND THEIR APPLICATIONS
Carnegie Mellon University
Pittsburgh, PA, USA
July 20-23 2005

ISIPTA'05 ELECTRONIC PROCEEDINGS

Alessandro Antonucci, Marco Zaffalon

Fast Algorithms for Robust Classification with Bayesian Nets

Abstract

We focus on a well-known classification task with expert systems based on Bayesian networks: predicting the state of a target variable given an incomplete observation of the other variables in the network, i.e., an observation of a subset of all the possible variables. To provide conclusions robust to near-ignorance about the process that prevents some of the variables from being observed, it has recently been derived a new rule, called conservative updating. With this paper we address the problem to efficiently compute the conservative updating rule for robust classification with Bayesian networks. We show first that the general problem is NP-hard, thus establishing a fundamental limit to the possibility to do robust classification efficiently. Then we define a wide subclass of Bayesian networks that does admit efficient computation. We show this by developing a new classification algorithm for such a class, which extends substantially the limits of efficient computation with respect to the previously existing algorithm.

Keywords. Bayesian networks, missing data, conservative updating rule, credal classification.

Paper Download

The paper is availabe in the following formats:

Authors addresses:

Alessandro Antonucci
c/o IDSIA
Galleria 2
CH-6928 Manno (Lugano)

Marco Zaffalon
Galleria 2
CH-6928 Manno
Switzerland

E-mail addresses:

Alessandro Antonucci alessandro@idsia.ch
Marco Zaffalon zaffalon@idsia.ch


[ back to the Proceedings of ISIPTA'05 home page 
Send any remarks to the following address: smc@decsai.ugr.es