Algorithms and Complexity Results for Discrete Probabilistic Reasoning Tasks

You are cordially invited to attend the PhD Dissertation Defense of Denis MAUÀ on Tuesday, September 17th 2013 at 16h30 in room A32 (Red building)
 
Abstract:
Many solutions to problems in machine learning and artificial intelligence  involve solving a combinatorial optimization problem over discrete variables whose  functional dependence is conveniently represented by a graph. This thesis addresses three types of these combinatorial optimization problems, namely,  the maximum a posteriori inference in discrete probabilistic  graphical models, the selection of optimal strategies for limited memory influence diagrams, and the computation of upper and lower  probability bounds in credal networks.
 
These three problems arise out of seemingly very different situations, and  one might believe that they share no more than the graph-based specification  of their inputs or the underlying probabilistic treatment of uncertainty.   However, correspondences among instances of these problems have long been  noticed in the literature. For instance, the computation of probability  bounds in credal networks can be reduced either to the problem of maximum a  posteriori inference in graphical models, or to the selection of optimal strategies in limited memory influence diagrams. Conversely, both the maximum a posteriori inference and the strategy selection problems can be reduced to the computation of a probability bound in a credal network. These reductions suggest that much insight can be gained by carrying out a joint  study of the practical and theoretical computational complexity of these three problems.

This thesis describes algorithms and complexity results for these three classes of problems. In particular, we develop a new anytime algorithm for  the maximum a posteriori problem. Not only the algorithm is of practical relevance, as we show that it compares favorably against a state-of-the-art  method, but it is the base of the proof of polynomial-time approximability of the two other problems. We characterize the tractability of the strategy selection problem according to the input parameters, and we show that the strategy selection problem can be solved in polynomial time in singly connected diagrams over binary variables and univariate utility functions, and that relaxing any of these assumptions makes the problem NP-hard to solve or even approximate within any bound.

We also investigate the theoretical complexity of computing upper and lower probability bounds in credal networks. We show that the complexity of the problem depends on the irrelevance concept adopted, but is in general NP-hard even in polytree-shaped networks, and even in trees if we assume strong independence. We also show that there is a particular type of inference that can be solved in polynomial time in imprecise hidden Markov models, whether we assume epistemic irrelevance or strong independence.

Dissertation Committee:

• Prof. Jürgen Schmidhuber, Università della Svizzera italiana, Switzerland (Research Advisor)
• Prof. Fabio Crestani, Università della Svizzera italiana, Switzerland (Internal Member)
• Prof. Fabian Kuhn, Università della Svizzera italiana, Switzerland (Internal Member)
• Prof. Thomas D. Nielsen, Aalborg University, Denmark (External Member)
• Prof. Serafin Moral, University of Granada, Spain (External Member)