Algorithms and Complexity Results for Discrete Probabilistic Reasoning Tasks

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.

7