5th International Symposium on Imprecise Probability: Theories and Applications Prague Czech Republic

Description

5th International Symposium on Imprecise Probability: Theories and Applications, Prague, Czech Republic, 2007 Credal Nets with Probabilities Estimated with an Extreme Imprecise Dirichlet Model A. Cano, M. Gomez-Olmedo, S. Moral Dpto. Ciencias de la Computacion Universidad de Granada 18071 - Granada (Spain) (acu,mgomez,smc)@decsai.ugr.es Abstract The propagation of probabilities in credal networks when probabilities are estimated with a global impre- cise Dirichlet model is an important open problem. Only Zaffalon [21] has proposed an algorithm for the Naive classifier. The main difficulty is that, in gen- eral, computing upper and lower probability intervals implies the resolution of an optimization of a fraction of two polynomials. In the case of the Naive credal classifier, Zaffalon has shown that the function is a convex function of only one parameter, but there is not a similar result for general credal sets. In this pa- per, we propose the use of an imprecise global model, but we restrict the distributions to only the most ex- treme ones. The result is a model giving rise that in the case of estimating a conditional probability under independence relationships, it can produce smaller in- tervals than the global general model. Its main ad- vantage is that the optimization problem is simpler, and available procedures can be directly applied, as the ones proposed in [7].

• variable dx


• conditional probabilities


• decision variable


• when considering


• global application


• treme ones


• conditional probability


• credal networks

Sujets

• Conditional probability
• multiplication

Informations

• Publié par: pefav
• Nombre de lectures: 21
• Langue: English

Extrait

5th International Symposium on Imprecise Probability: Theories and Applications, Prague, Czech Republic, 2007

Credal Nets with Probabilities Estimated with an Extreme Imprecise Dirichlet Model

A. Cano, M. GómezOlmedo, S. Moral Dpto. Ciencias de la Computación Universidad de Granada 18071  Granada (Spain) (acu,mgomez,smc)@decsai.ugr.es

Abstract The propagation of probabilities in credal networks when probabilities are estimated with a global impre cise Dirichlet model is an important open problem. Only Zaffalon [21] has proposed an algorithm for the Naive classifier. The main difficulty is that, in gen eral, computing upper and lower probability intervals implies the resolution of an optimization of a fraction of two polynomials. In the case of the Naive credal classifier, Zaffalon has shown that the function is a convex function of only one parameter, but there is not a similar result for general credal sets. In this pa per, we propose the use of an imprecise global model, but we restrict the distributions to only the most ex treme ones. The result is a model giving rise that in the case of estimating a conditional probability under independence relationships, it can produce smaller in tervals than the global general model. Its main ad vantage is that the optimization problem is simpler, and available procedures can be directly applied, as the ones proposed in [7].

Keywords.Locally specified credal networks, global imprecise Dirichlet model, propagation algorithms, probability trees.

1

Introduction

Credal networks[12] are an extension ofBayesian net workswhere instead of having a joint precise global probability distribution we have a closed and convex set of possible distributions (acredal set[15]). This credal set produces a conditional credal set for each variable given its parents. There are two basic possi bilities:

•The credal net isseparately specifiedthe[12], i.e. set of joint probability distributions is obtained by specifying a credal set of conditional prob ability distributions for each variable and each configuration of its parents, and then the joint

credal set is the convex hull of the probability distributions obtained by multiplying the condi tional probability distributions resulting by se lecting one element from each conditional credal set (the joint credal set is thestrong extensionof the local conditional credal sets [12]). •The credal net isglobally specified, when only the joint credal set is given.

Most of the effort to design algorithms for compu tation in credal networks has been devoted to the case of separately specified credal nets. In general, this computation is equivalent to the resolution of a combinatorial optimization problem. One of the most promising approaches is based on the branch andbound technique [17, 7]. Also, there are several approximate algorithms, as the ones based on the sim ulated annealing technique [6] or the ones based on making the variables binaries in order to apply the efficient 2U algorithm [13, 3].

There is less work for globally specified credal net works. Preliminary models were proposed by Coz man [11, 12], but he followed a robust statistics methodology, considering credal sets that were neigh borhoods of standard Bayesian networks. Recently, Antonucci and Zaffalon [2] have proposed a general method based on the use of auxiliary variables as in [5] to transform a globally specified credal network into a separately specified one. This allows the appli cation of existing algorithms for separately specified networks to cases that initially were nonseparately given.

However, the Antonucci and Zaffalon [2] transforma tion can not directly solve some important imprecise networks that can arise in practice. This is the case of credal nets in which conditional probabilities are es timated from a database of observations with an im precise global Dirichlet model (IDM) [20]. The main problem is that in this situation we need auxiliary variables with infinite values (as the parameters can