Graphical models provide a unified framework for modeling and reasoning about complex tasks. Example tasks include probabilistic inference and sequential decision making under uncertainty. Influence diagrams extend Bayesian networks with decision variables and utility functions to model the interaction between an agent and a system aiming to capture the agent's preferences. The standard task is to compute the maximum expected utility (MEU) over the influence diagram and a corresponding maximizing sequence of policies. However, finding the MEU is intractable, and it is one of the most challenging tasks in graphical models. Therefore, the goal of this dissertation is the development of decomposition bounds for influence diagrams. Computing upper bounds on the MEU is desirable also because upper bounds can facilitate anytime-solutions by acting as heuristics to guide search or sampling-based methods. Most earlier approaches for upper bounding the MEU relied on polynomial reductions to other standard tasks in graphical models. However, such reductions are ineffective in practice since they highly inflate the problem size that needs to be solved. In this dissertation, we present two direct bounding methods for IDs. The first builds on the algebraic framework for influence diagrams, called valuation algebra. Using this framework, we extend two earlier decomposition bounds to the MEU task. The second method provides upper bounds by exploiting an exponentiated utility form of the MEU which can be bounded by a conventional task (i.e., marginal MAP) over a standard probabilistic graphical model. This enables the use of two variational decomposition bounds for the well known marginal MAP task, yielding what we call exponentiated utility bounds for the MEU. For both cases (using valuation algebra and using exponentiated utilities), we present two kinds of message passing algorithms derived from bounding schemes on the marginal MAP task. One is the generalized dual decomposition algorithm, which propagates messages over a join-graph decomposition of an ID. The other is a weighted mini-bucket algorithm that propagates messages over the mini-bucket tree decomposition. We evaluated all the algorithms empirically and compared them against earlier approaches over four synthetic benchmark domains. The empirical evaluation results show that our direct bounding schemes generate upper bounds that are orders of magnitude tighter than previous methods. In addition, the exponentiated schemes turn out to be, overall, far more effective. We also evaluated our algorithms on the well-known system administration domain and observed that one of the exponentiated algorithms exhibited a remarkable performance generating upper bounds that are within a factor of two from the exact MEU.

This paper presents distributed algorithms for performing truth-maintenance and belief revision tasks on singly-connected structures. We show that on such models the JTMS tasks of belief revision and consistency maintenance are linear in the size of the knowledge-base. The ATMS task remains exponential with a reduced exponent - the branching degree of the network. The single-connected model, while restrictive, is useful for three reasons. First, efficient algorithms on single-connected models can be utilized in more general structures by employing well-known clustering techniques. Second, these algorithms can serve as approximations or as heuristics in algorithms that perform truth-maintenance on general problems. Finally, the analysis provides insights for understanding the sources of the computational difficulties associated with both JTMS and ATMS.

Graphical models are a well-known convenient tool to describe complex interactions between variables. A graphical model defines a function over many variables that factors over an underlying graph structure. One of the popular tasks over graphical models is that of combinatorial optimization. Although many algorithms have been developed with this task in mind, the vast majority are designed to find an optimal solution, minimum or maximum, of an objective function. In many applications, however, it is desirable to obtain not just a single optimal solution, but a set of the first m best solutions for some integer m.

The main part of this dissertation focuses on this problem, which we call the m-best optimization task. We show that the m-best task can be expressed within the unifying framework of semirings, making known inference algorithms defined, and their correctness and completeness for the m-best task immediately implied. We subsequently describe elim-m-opt, a new bucket elimination algorithm for solving the m-best task, provide algorithms for its defining combination and marginalization operators and analyze its worst-case performance. An extension of the algorithm to the mini-bucket framework provides bounds for each of the m best solutions.

Subsequently, we extend existing search algorithms to the m-best task. We present a new algorithm m-A* and prove that all A*’s desirable properties, including soundness, completeness and optimal efficiency, are maintained. Since best-first algorithms require extensive memory, we also extend the memory-efficient depth-first branch and bound to the m-best task. We adapt both algorithms to optimization tasks over graphical models (e.g., Weighted Constraint Satisfaction Problems and Most Probable Explanation in Bayesian networks), and provide complexity analysis and an empirical evaluation. Our experiments with 5 variants of best-first search and depth-first branch and bound search confirm that the best-first approach is largely superior when memory is available, but branch and bound is more robust. We also demonstrate that both styles of search benefit greatly from the heuristic evaluation function with increased accuracy.

Unlike the leading previously developed m-best schemes that utilize LP-relaxation techniques, e.g., algorithms by Fromer and Globerson (2009) and Batra (2012), our algorithms always guarantee solution optimality. We will show that, when the number of required solutions is small, our m-best search schemes are quite competitive with these related algorithms in terms of runtime, while for a larger number of required solutions our methods are by far superior.

The second part of this thesis focuses on finding approximate solutions to optimization problems. Unfortunately solving exactly optimization problems over complex models, that represent intricate dependencies occurring in real life domains, can often be infeasible within practical time and space limits. Many approximation schemes exist, but most of them do not come with any solution sub-optimality guarantees. We apply the ideas of weighted heuristic search, popular in path-finding, to graphical models, yielding new search algorithms that not only provide sub-optimality bounds, but also utilize extra available time and space to improve the accuracy of the solution in an anytime manner and, if resources are available, eventually terminate with an optimal solution. We report on a significant empirical evaluation, demonstrating the usefulness of weighted best-first search as approximation anytime schemes (that have sub-optimality bounds) and compare against one of the best depth-first branch and bound solvers to date. We also investigate the impact of different heuristic functions on the behavior of the algorithms.

Additionally, we explore several algorithms taking advantage of two common approaches for bounding MPE queries in graphical models: mini-bucket elimination and message-passing updates for linear programming relaxations. Each method offers a useful perspective for the other; our hybrid approaches attempt to balance the advantage of each. We demonstrate the power of our hybrid algorithms through extensive empirical evaluation. Most notably, a branch and bound search guided by the heuristic functions calculated by our new scheme won the first place in the 2011 Pascal2 inference challenge.

We present the results of an empirical study of several constraint satisfaction search algorithms and heuristics. Using a random problem generator that allows us to create instances with given characteristics, we show how the relative performance of various search methods varies with the number of variables, the tightness of the constraints, and the sparseness of the constraint graph. A version of backjumping using a dynamic variable ordering heuristic is shown to be extremely effective on a wide range of problems. We conducted our experiments with problem instances drawn from the 50% satisfiable range.

This paper presents several investigations into the prospects for identifying meaningful structures in empirical data, namely, structures permitting effective organization of the data to meet requirements of future queries. We propose a general framework whereby the notion of identifiability is given a precise formal definition similar to that of learnability. Using this framework, we then explore if a tractable procedure exists for deciding whether a given relation is decomposable into a constraint network or a CNF theory with desirable topology and, if the answer is positive, identifying the desired decomposition. Finally, we address the problem of expressing a given relation as a Horn theory and, if this is impossible, finding the best k-Horn approximation to the given relation. We show that both problems can be solved in time polynomial in the length of the data.

This paper presents an experimental evaluation of two orthogonal schemes for preprocessing constraint satisfaction problems (CSPs). The first of these schemes involves a class of local consistency techniques that includes directional arc consistency, directional path consistency, and adaptive consistency. The other scheme concerns the prearrangement of variables in a linear order to facilitate an efficient search. In the first series of experiments, we evaluated the effect of each of the local consistency techniques on backtracking and its common enhancement, backjumping. Surprizingly, although adaptive consistency has the best worst-case complexity bounds, we have found that it exhibits the worst performance, unless the constraint graph was very sparse. Directional arc consistency (followed by either backjumping or backtracking) and backjumping (without any pre-processing) outperformed all other techniques; moreover, the former dominated the latter in computationally intensive situations. The second series of experiments suggests that maximum cardinality and minimum width arc the best pre-ordering (i.e., static ordering) strategies, while dynamic search rearrangement is superior to all the preorderings studied.

The paper presents algorithm directional resolution, a variation on the original Davis-Putnam algorithm, and analyzes its worst-case behavior as a function of the topological structure of the theories. The notions of induced width and diversity are shown to play a key role in bounding the complexity of the procedure. The importance of our analysis lies in highlighting structure-based tractable classes of satisfiability and in providing theoretical guarantees on the time and space complexity of the algorithm. Contrary to previous assessments, we show that for many theories directional resolution could be an effective procedure. Our empirical tests confirm theoretical prediction, showing that on problems with special structures, like chains, directional resolution greatly outperforms one of the most effective satisfiability algorithm known to date, namely the popular Davis-Putnam procedure.