Imprecise Probabilistic Graphical Models: Equivalent Representations, Inference Algorithms and Applications


Author: Alessandro Antonucci

Abstract: Credal networks are probabilistic graphical models that extend Bayesian nets to deal with imprecision in probability, and can actually be regarded as sets of Bayesian nets. Credal nets appear to be powerful means to represent and deal with many important and challenging problems in uncertain reasoning. The counterpart of having more freedom in the modeling phase is an increased inferential complexity of inferences, e.g., the so-called belief updating becomes a hard task even on relatively simple topologies. In this thesis, I start my investigation on credal networks by considering equivalent representations of those models. More specifically, I first deliver a new graphical language, which is called decision-theoretic being inspired by the formalism of decision graphs, for a unified representation of credal networks of any kind. I also present another representation, which is called binarization, being in fact a reformulation of a credal network solely based on binary variables. Remarkably, I prove that if a credal net is first reformulated by its decision-theoretic representation and then by the corresponding binarization, the resulting representation is completely equivalent. An equivalence relation between Bayesian and credal nets, when the reason for the missingness of some of the variables in the Bayesian nets is unknown, is also provided. The developed equivalent representations are applied to inference problems. First, I show that, by a decision-theoretic formulation, the algorithms that have been already designed for credal networks, which are mostly referred to a specific class of models, called separately specified nets, can be generalized to credal networks of any kind. Similar formalisms are also employed to solve inference and classification problems with missing observations. I also present a state-ofthe- art updating algorithm which is based on the equivalent binary representation. This algorithm, called GL2U, offers an efficient procedure for approximate updating of general credal nets. The quality of the overall approximation is investigated by promising numerical experiments. As a further theoretical investigation, I consider a classification problem for Bayesian networks for which a hardness proof together with a fast algorithm for a subclass of models is provided. Finally, two real-world applications of credal networks are presented. First, I consider a military identification problem, consisting in the detection of the goal of an intruder entering a no-fly area. The problem, together with the necessary fusion of the information gathered by the sensors is mapped by our techniques into a credal network updating task. The solution is then obtained by the GL2U algorithm. The second application is an environmental model for hazard assessment of debris flows by credal networks. A credal network evaluates the level of risk, corresponding to the observed values of the triggering factors, for this specific natural hazard. For some factors, whose observations are more difficult, the corresponding soft evidential information is embedded by our formalism into the structure of the network. This model is employed for extensive numerical analysis on the Swiss territory.

Year: 2008.

Details: Ph.D. thesis, Università della Svizzera Italiana.

A version similar to the published paper can be downloaded.