## Fast algorithms for robust classification with Bayesian nets

**Authors: **Alessandro Antonucci and Marco Zaffalon

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

**Year:** 2005.

**Details:** In Cozman, F. G. and Nau, R. and Seidenfeld, T. (Eds.), *Proceedings of the fourth International Symposium on Imprecise
Probabilities and Their Applications (ISIPTA'06)*. SIPTA, pp. 11-20.

A version similar to the published paper can be downloaded.