Denis D. Mauá's PhD Thesis on Algorithms and Complexity Results for Discrete Probabilistic Reasoning Tasks

Posted on January 9, 2014 by Dennis D. Mauá
[ go back to blog ]

The Three Dots

My PhD thesis is about connecting three hard computational problems that arise in tasks involving graph-based probabilistic reasoning, namely, the problems of

• maximum a posteriori (MAP) inference in Bayesian networks,
• planning with influence diagrams, and
• belief updating in credal networks under strong independence (or simply strong credal networks).

Roughly speaking, in the MAP inference problem we seek the most probable explanation of a complex phenomena represented as a Bayesian network, a graph-based description of a multivariate joint probability distribution where nodes are identified with random variables and local conditional probability distributions. By extending a Bayesian network with actions and utilities, we get an influence diagram. The problem of planning with influence diagrams is to select a set of actions that maximizes expected utility. A (strong) credal network is a Bayesian network whose numerical parameters (the local conditional probability distributions) have been imprecisely specified as convex sets (instead point estimates). Belief updating in (strong) credal networks is the task of computing tight upper and lower bounds on the (conditional) probability of a certain event, and is largely equivalent to the problem of assessing the sensitivity of a probabilistic inference in a Bayesian network to global changes in the model parameters. The similarities and differences among these three problems are more easily captured by the following simple example in fault analysis.

Probabilistic Fault Analysis

Consider the simple electric circuit below, in which a light bulb is powered by a battery according to the state of four switches.

Suppose we are interested in estimating the probable causes of the light being off. By inspecting the circuit, we see that such an event could have been caused by a burned light bulb, a depleted battery, or simply because there is no power at the light bulb socket (among other causes that we ignore). The last event could have been caused by an interruption of the energy flow on the left or right trails; the trail on the left is interrupted only if both switches 1 and 2 are off. The right trail is interrupted if any of the switches 3 and 4 is off. Such a collection of intercausal reasonings can be graphically represented by the acyclic directed graph below.

If we assign to each node in that graph a conditional probability distribution of the corresponding event given its parent events (i.e., its immediate predecessors in the graph), the result is a fully specified Bayesian network. If instead, we associate a closed and convex set of probability distributions to each node and each configuration of its parents, we obtain a (separately specified) credal network. To get an influence diagram, we extend the Bayesian network with actions (for example, possible fixes or information gathering routines) and utilities (e.g., the costs of replacing the light bulb or the battery, or the loss caused by having no light), as in the figure below.

Connecting the dots

At first sight, these three problems seem connected only by means of their combinatorial or optimization nature, and by the use of graphs as a concise yet intuitive representation of complex phenomena. Nevertheless, correspondences between instances of these problems have long been noticed in the literature. For instance, it was previously known that belief updating in strong credal networks can be reduced to MAP inference in Bayesian networks [Cano, Cano & Moral, 1994] and vice-versa [De Campos & Cozman, 2005]. De Campos & Ji [2008] showed that planning with influence diagrams can be reduced to belief updating in credal networks, while the converse was proved by Antonucci & Zaffalon [2008]. In my thesis, and jointly with Cassio de Campos and Marco Zaffalon, we proved the last two missing correspondences, namely, that MAP inference and planning with influence diagrams can be reduced to one another. We now know that these three problems are strongly tied by their computational equivalences. These equivalences increase the algorithmic toolset available to each problem with the algorithms developed for the other problems, and allow us to derive bounds on the computational hardness of each problem. Moreover, they provide an interesting view of each problem instance by the perspective of the other corresponding problem instances. For example, Cano, Cano & Moral [1994] reduced belief updating in strong credal networks to MAP problem instances in order to use available algorithms for the latter. In a similar fashion, De Campos & Ji [2008] reduced planning in influence diagrams to belief updating in credal networks so that the former problem could be solved using algorithms designed for the latter. Antonucci & Zaffalon [2008] reduced belief updating in credal networks to planning in influence diagrams in order to provide a decision-theoretic view of credal networks. De Campos & Cozman [2005] showed NP-hardness of belief updating in strong credal networks by a reduction from MAP inference. More recently, we were able to show that a certain class of planning problems can be solved in polynomial time by reducing them into instances of credal belief updating that are known to be polynomial-time computable. Using the converse reduction, we were able to prove the NP- hardness of structurally very simple instances of credal belief updating. Notably, these correspondences allowed us to extend De Campos’ proof of polynomial-time approximability of MAP inference in Bayesian networks of bounded treewidth and variable cardinality to planning in influence diagrams and belief updating in strong credal networks. These are the first results concerning the approximability of these problems. On the more practical side, we were able to develop a unified algorithmic framework that approximately solves any of the problems in polynomial time when both treewidth and variable cardinality are small.

Conclusion

In summary, the main contributions of my work are:

• a state-of-the-art anytime algorithm for MAP inference;
• a state-of-the-art exact algorithm for strategy selection in influence diagrams;
• a proof of NP-hardness of strategy selection in polytree-shaped influence diagrams of bounded treewidth, even in the approximate case;
• an FPTAS for the strategy selection problem on diagrams of bounded treewidth and bounded cardinality;
• a proof of NP-hardness of strategy selection even in polytree-shaped diagrams with only binary variables, and a result of tractability of the case in which there is a single value node;
• a proof of NP-hardness of approximate belief updating in credal networks of bounded treewidth (and unbounded variable cardinality);
• an FPTAS for belief updating in strong credal networks of bounded treewidth and variable cardinality.

About the author

Denis D. Mauá is currently a Post-Doctoral Researcher at the Decision Making Lab of the University of São Paulo. He obtained his PhD in Informatics from the University of Lugano (Università della Svizzera italiana) in Sep., 2013. From Sep., 2009 and Dec., 2013 he was a Research Fellow at IDSIA’s Imprecise Probability Group.