Peter van Beek

AAAI Conference 2019 Conference Paper

Finding All Bayesian Network Structures within a Factor of Optimal

• Zhenyu A. Liao
• Charupriya Sharma
• James Cussens
• Peter van Beek

A Bayesian network is a widely used probabilistic graphical model with applications in knowledge discovery and prediction. Learning a Bayesian network (BN) from data can be cast as an optimization problem using the well-known score-andsearch approach. However, selecting a single model (i. e. , the best scoring BN) can be misleading or may not achieve the best possible accuracy. An alternative to committing to a single model is to perform some form of Bayesian or frequentist model averaging, where the space of possible BNs is sampled or enumerated in some fashion. Unfortunately, existing approaches for model averaging either severely restrict the structure of the Bayesian network or have only been shown to scale to networks with fewer than 30 random variables. In this paper, we propose a novel approach to model averaging inspired by performance guarantees in approximation algorithms. Our approach has two primary advantages. First, our approach only considers credible models in that they are optimal or near-optimal in score. Second, our approach is more efficient and scales to significantly larger Bayesian networks than existing approaches.

IJCAI Conference 2011 Conference Paper

An Empirical Study of Seeding Manipulations and Their Prevention

• Tyrel Russell
• Peter van Beek

It is well known that cheating occurs in sports. In cup competitions, a common type of sports competition, one method of cheating is in manipulating the seeding to unfairly advantage a particular team. Previous empirical and theoretical studies of seeding manipulation have focused on competitions with unrestricted seeding. However, real cup competitions often place restrictions on seedings to ensure fairness, wide geographic interest, and so on. In this paper, we perform an extensive empirical study of seeding manipulation under comprehensive and realistic sets of restrictions. A generalized random model of competition problems is proposed. This model creates a realistic range of problem instances that are used to identify the sets of seeding restrictions that are hard to manipulate in practice. We end with a discussion of the implications of this work and recommendations for organizing competitions so as to prevent or reduce the opportunities for manipulating the seeding.

AIJ Journal 2011 Journal Article

Book review

• Peter van Beek

IJCAI Conference 2003 Conference Paper

A Fast and Simple Algorithm for Bounds Consistency of the All Different Constraint

• Alejandro Ldpez-Ortiz
• Claude-Guy Quimper
• John Tromp
• Peter van Beek

In constraint programming one models a problem by stating constraints on acceptable solutions. The constraint model is then usually solved by interleaving backtracking search and constraint propagation. Previous studies have demonstrated that designing special purpose constraint propagators for commonly occurring constraints can significantly improve the efficiency of a constraint programming approach. In this paper we present a fast, simple algorithm for bounds consistency propagation of the alldifferent constraint. The algorithm has the same worst case behavior as the previous best algorithm but is much faster in practice. Using a variety of benchmark and random problems, we show that our algorithm outperforms existing bounds consistency algorithms and also outperforms—on problems with an easily identifiable property—state-ofthe-art commercial implementations of propagators for stronger forms of local consistency.

AIJ Journal 2002 Journal Article

Binary vs. non-binary constraints☆☆This paper includes results that first appeared in [1,4,23]. This research has been supported in part by the Canadian Government through their NSERC and IRIS programs, and by the EPSRC Advanced Research Fellowship program.

• Fahiem Bacchus
• Xinguang Chen
• Peter van Beek
• Toby Walsh

There are two well known transformations from non-binary constraints to binary constraints applicable to constraint satisfaction problems (CSPs) with finite domains: the dual transformation and the hidden (variable) transformation. We perform a detailed formal comparison of these two transformations. Our comparison focuses on two backtracking algorithms that maintain a local consistency property at each node in their search tree: the forward checking and maintaining arc consistency algorithms. We first compare local consistency techniques such as arc consistency in terms of their inferential power when they are applied to the original (non-binary) formulation and to each of its binary transformations. For example, we prove that enforcing arc consistency on the original formulation is equivalent to enforcing it on the hidden transformation. We then extend these results to the two backtracking algorithms. We are able to give either a theoretical bound on how much one formulation is better than another, or examples that show such a bound does not exist. For example, we prove that the performance of the forward checking algorithm applied to the hidden transformation of a problem is within a polynomial bound of the performance of the same algorithm applied to the dual transformation of the problem. Our results can be used to help decide if applying one of these transformations to all (or part) of a constraint satisfaction model would be beneficial.

AAAI Conference 1999 Conference Paper

CPlan: A Constraint Programming Approach to Planning

• Peter van Beek
• Xinguang Chen
• University of Alberta

Constraint programming, a methodology for solving difficult combinatorial problems by representing them as constraint satisfaction problems, has shown that a general purpose search algorithm based on constraint propagation combined with an emphasis on modeling can solve large, practical scheduling problems. Given the success of constraint programming on scheduling problems and the similarity of scheduling to planning, the question arises, would a constraint programming approach work as well in planning? In this paper, we present evidencethat a constraint programming approach to planning does indeed work well and has the advantage in terms of time and space efficiency over the current state-of-the-art planners.

AIJ Journal 1997 Journal Article

A theoretical evaluation of selected backtracking algorithms

• Grzegorz Kondrak
• Peter van Beek

In recent years, many new backtracking algorithms for solving constraint satisfaction problems have been proposed. The algorithms are usually evaluated by empirical testing. This method, however, has its limitations. Our paper adopts a different, purely theoretical approach, which is based on characterizations of the sets of search tree nodes visited by the backtracking algorithms. A notion of inconsistency between instantiations and variables is introduced, and is shown to be a useful tool for characterizing such well-known concepts as backtrack, backjump, and domain annihilation. The characterizations enable us to: (a) prove the correctness of the algorithms, and (b) partially order the algorithms according to two standard performance measures: the number of nodes visited, and the number of consistency checks performed. Among other results, we prove the correctness of Backjumping and Conflict-Directed Backjumping, and show that Forward Checking never visits more nodes than Backjumping. Our approach leads us also to propose a modification to two hybrid backtracking algorithms, Backmarking with Backjumping (BMJ) and Backmarking with Conflict-Directed Backjumping (BM-CBJ), so that they always perform fewer consistency checks than the original algorithms.

TCS Journal 1997 Journal Article

Local and global relational consistency

• Rina Dechter
• Peter van Beek

Local consistency has proven to be an important concept in the theory and practice of constraint networks. In this paper, we present a new definition of local consistency, called relational consistency. The new definition is relation-based, in contrast with the previous definition of local consistency, which we characterize as variable-based. We show the conceptual power of the new definition by showing how it unifies known elimination operators such as resolution in theorem proving, joins in relational databases, and variable elimination for solving linear inequalities. Algorithms for enforcing various levels of relational consistency are introduced and analyzed. We also show the usefulness of the new definition in characterizing relationships between properties of constraint networks and the level of local consistency needed to ensure global consistency.

IJCAI Conference 1995 Conference Paper

A Theoretical Evaluation of Selected Backtracking Algorithms

• Grzegorz Kondrak
• Peter van Beek

In recent years, many new backtracking algorithms for solving constraint satisfaction problems have been proposed. The algorithms are usually evalu­ ated by empirical testing. This method, however, has its limitations. Our paper adopts a different, purely theoretical approach, which is based on char­ acterizations of the sets of search tree nodes visited by the backtracking algorithms. A notion of in­ consistency between instantiations and variables is introduced, and is shown to be a useful tool for char­ acterizing such well-known concepts as backtrack, backjump, and domain annihilation. The charac­ terizations enable us to: (a) prove the correctness of the algorithms, and (b) partially order the algo­ rithms according to two standard performance mea­ sures: the number of nodes visited, and the number of consistency checks performed. Among other re­ sults, we prove the correctness of Backjumping and Conflict-Directed Backjumping, and show that For­ ward Checking never visits more nodes than Backjumping. Our approach leads us also to propose a modification to two hybrid backtracking algo­ rithms, Backmarking with Backjumping (BMJ) and Backmarking with Conflict-Directed Backjumping (BM-CBJ), so that they always perform fewer con­ sistency checks than the original algorithms.

AAAI Conference 1994 Conference Paper

On the Inherent Level of LocalConsistency in Constraint Networks

• Peter van Beek

We present a new property called constraint looseneas and show how it can be used to estimate the level of local consistency of a binary constraint network. Specifically, we present a relationship between the looseness of the constraints, the size of the domains, and the inherent level of local consistency of a constraint network. The results we present are useful in two ways. First, a common method for finding solutions to a constraint network is to first preprocess the network by enforcing local consistency conditions, and then perform a backtracking search. Here, our results can be used in deciding which low-order local consistency techniques will not change a given constraint network and thus are not useful for preprocessing the network. Second, much previous work has identified conditions for when a certain level of local consistency is sufficient to guarantee a network is backtrack-free. Here, our results can be used in deciding which local consistency conditions, if any, still need to be enforced to achieve the specified level of local consistency. As well, we use the looseness property to develop an algorithm that can sometimes find an ordering of the variables such that a network is backtrack-free.

AAAI Conference 1992 Conference Paper

On the Minimality and Decomposability of Constraint Networks

• Peter van Beek

Constraint networks have been shown to be useful in formulating such diverse problems as scene labeling, natural language parsing, and temporal reasoning. Given a constraint network, we often wish to (i) find a solution that satisfies the constraints and (ii) find the corresponding minimal network where the constraints are as explicit as possible. Both tasks are known t. o be NP-complete in the general case. Task (i) is usually solved using a backtracking algorithm, and task (ii) is often solved only approximately by enforcing various levels of local consistency. In this paper, we identify a property of binary constraints called rozu convesity and show its usefulness in deciding when a form of local consistency called path consistency is sufficient to guarantee a network is both minimal and decomposable. Decomposable networks have the property that a solution can be found without backtracking. We show that the row convexity property can be tested for efficiently and we show, by examining applications of constraint networks discussed in the literature, that our results are useful in practice. Thus, we identify a large class of constraint networks for which we can solve both tasks (i) and (ii) efficiently.

AIJ Journal 1992 Journal Article

Reasoning about qualitative temporal information

• Peter van Beek

Representing and reasoning about incomplete and indefinite qualitative temporal information is an essential part of many artificial intelligence tasks. An interval-based framework and a point-based framework have been proposed for representing such temporal information. In this paper, we address two fundamental reasoning tasks that arise in applications of these frameworks: Given possibly indefinite and incomplete knowledge of the relationships between some intervals or points, (i) find a scenario that is consistent with the information provided, and (ii) find the feasible relations between all pairs of intervals or points. For the point-based framework and a restricted version of the interval-based framework, we give computationally efficient procedures for finding a consistent scenario and for finding the feasible relations. Our algorithms are marked improvements over the previously known algorithms. In particular, we develop an O(n 2)-time algorithm for finding one consistent scenario that is an O(n) improvement over the previously known algorithm, where n is the number of intervals or points, and we develop an algorithm for finding all the feasible relations that is of far more practical use than the previously known algorithm. For the unrestricted version of the interval-based framework, finding a consistent scenario and finding the feasible relations have been shown to be NP-complete. We show how the results for the point algebra aid in the design of a backtracking algorithm for finding one consistent scenario that is shown to be useful in practice for planning problems.

IJCAI Conference 1991 Conference Paper

Resolving Plan Ambiguity for Cooperative Response Generation

• Peter van Beek
• Robin Cohen

AIIM Journal 1991 Journal Article

Temporal query processing with indefinite information

• Peter van Beek

Time is an important aspect of information in medical domains. In this paper, we adopt Allen's influential interval algebra framework for representing temporal information. The interval algebra allows the representation of indefinite and incomplete information which is necessary in many applications. However, answering interesting queries in this framework has been shown to be almost assuredly intractable. We show that when the representation language is sufficiently restricted we can develop efficient algorithms for answering interesting classes of queries including: (i) determining whether a formula involving temporal relations between events is possibly true and necessarily true; and (ii) answering aggregation questions where the set of all events that satisfy a formula are retrieved. We also show, by examining applications of the interval algebra discussed in the literature, that our restriction on the representation language often is not overly restrictive in practice.

AAAI Conference 1990 Conference Paper

Reasoning about Qualitative Temporal Information

• Peter van Beek

Interval and point algebras have been proposed for representing qualitative temporal information about the relationships between pairs of intervals and pairs of points, respectively. In this paper, we address two related reasoning tasks that arise in these algebras: Given (possibly indefinite) knowledge of the relationships between some intervals or points, (1) find one or more scenarios that are consistent with the information provided, and (2) find all the feasible relations between every pair of intervals or points. Solutions to these problems have applications in natural language processing, planning, and a knowledge representation language. We define computationally efficient procedures for solving these tasks for the point algebra and for a corresponding subset of the interval algebra. Our algorithms are marked improvements over the previously known algorithms. We also show how the results for the point algebra aid in the design of a backtracking algorithm for the full interval algebra that is useful in practice.

IJCAI Conference 1989 Conference Paper

Approximation Algorithms for Temporal Reasoning

• Peter van Beek