James D. Park

AIJ Journal 2004 Journal Article

A differential semantics for jointree algorithms

• James D. Park
• Adnan Darwiche

A new approach to inference in belief networks has been recently proposed, which is based on an algebraic representation of belief networks using multi-linear functions. According to this approach, belief network inference reduces to a simple process of evaluating and differentiating multi-linear functions. We show here that mainstream inference algorithms based on jointrees are a special case of the approach based on multi-linear functions, in a very precise sense. We use this result to prove new properties of jointree algorithms. We also discuss some practical and theoretical implications of this new finding.

IJCAI Conference 2003 Conference Paper

Causes and Explanations Revisited

• James D. Park

This paper reconsiders the notions of actual cause and explanation in functional causal models. We demonstrate that isomorphic causal models can generate intuitively different causal pronounce­ ments. This occurs because psychological factors not represented in the model determine what cri­ teria we use to determine causation. This par­ tially explains the difficulty encountered in previ­ ous attempts to define actual cause. Freed from trying fit all examples to match intuition directly (which is not possible using only the information in causal models), we provide definitions for cau­ sation matching the different causal criteria we in­ tuitively apply. This formulation avoids difficulties associated with previous definitions, and allows a more refined discussion of what constitutes a cause in a given situation. The definitions of actual cause also allow for more refined formulations of expla­ nation.

UAI Conference 2003 Conference Paper

Solving MAP Exactly using Systematic Search

• James D. Park
• Adnan Darwiche

MAP is the problem of finding a most probable instantiation of a set of variables in a Bayesian network given some evidence. Unlike computing posterior probabilities, or MPE (a special case of MAP), the time and space complexity of structural solutions for MAP are not only exponential in the network treewidth, but in a larger parameter known as the ``constrained' treewidth. In practice, this means that computing MAP can be orders of magnitude more expensive than computing posterior probabilities or MPE. This paper introduces a new, simple upper bound on the probability of a MAP solution, which admits a tradeoff between the bound quality and the time needed to compute it. The bound is shown to be generally much tighter than those of other methods of comparable complexity. We use this proposed upper bound to develop a branch-and-bound search algorithm for solving MAP exactly. Experimental results demonstrate that the search algorithm is able to solve many problems that are far beyond the reach of any structure-based method for MAP. For example, we show that the proposed algorithm can compute MAP exactly and efficiently for some networks whose constrained treewidth is more than 40

UAI Conference 2002 Conference Paper

MAP Complexity Results and Approximation Methods

• James D. Park

AAAI Conference 2002 Conference Paper

Using Weighted MAX-SAT Engines to Solve MPE

• James D. Park

Logical and probabilistic reasoning are closely related. Many examples in each group have natural analogs in the other. One example is the strong relationship between weighted MAX- SAT and MPE. This paper presents a simple reduction of MPE to weighted MAX-SAT. It also investigates approximating MPE by converting it to a weighted MAX-SAT problem, then using the incomplete methods for solving weighted MAX-SAT to generate a solution. We show that converting MPE problems to MAX-SAT problems and using a method designed for MAX-SAT to solve them often produces solutions that are vastly superior to the previous local search methods designed directly for the MPE problem.

UAI Conference 2001 Conference Paper

Approximating MAP using Local Search

• James D. Park
• Adnan Darwiche

MAP is the problem of finding a most probable instantiation of a set of variables in a Bayesian network, given evidence. Unlike computing marginals, posteriors, and MPE (a special case of MAP), the time and space complexity of MAP is not only exponential in the network treewidth, but also in a larger parameter known as the "constrained" treewidth. In practice, this means that computing MAP can be orders of magnitude more expensive than computingposteriors or MPE. Thus, practitioners generally avoid MAP computations, resorting instead to approximating them by the most likely value for each MAP variableseparately, or by MPE.We present a method for approximating MAP using local search. This method has space complexity which is exponential onlyin the treewidth, as is the complexity of each search step. We investigate the effectiveness of different local searchmethods and several initialization strategies and compare them to otherapproximation schemes.Experimental results show that local search provides a much more accurate approximation of MAP, while requiring few search steps.Practically, this means that the complexity of local search is often exponential only in treewidth as opposed to the constrained treewidth, making approximating MAP as efficient as other computations.