James Cussens

JMLR Journal 2026 Journal Article

Learning Bayesian Network Classifiers to Minimize Class Variable Parameters

• Shouta Sugahara
• Koya Kato
• James Cussens
• Maomi Ueno

This study proposes and evaluates a novel Bayesian network classifier which can asymptotically estimate the true probability distribution of the class variable with the fewest class variable parameters among all structures for which the class variable has no parent. Moreover, to search for an optimal structure of the proposed classifier, we propose (1) a depth-first search based method and (2) an integer programming based method. The proposed methods are guaranteed to obtain the true probability distribution asymptotically while minimizing the number of class variable parameters. Comparative experiments using benchmark datasets demonstrate the effectiveness of the proposed method. [abs] [ pdf ][ bib ] &copy JMLR 2026. ( edit, beta )

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.

JAIR Journal 2017 Journal Article

Bayesian Network Structure Learning with Integer Programming: Polytopes, Facets and Complexity

• James Cussens
• Matti Järvisalo
• Janne H. Korhonen
• Mark Bartlett

The challenging task of learning structures of probabilistic graphical models is an important problem within modern AI research. Recent years have witnessed several major algorithmic advances in structure learning for Bayesian networks - arguably the most central class of graphical models - especially in what is known as the score-based setting. A successful generic approach to optimal Bayesian network structure learning (BNSL), based on integer programming (IP), is implemented in the GOBNILP system. Despite the recent algorithmic advances, current understanding of foundational aspects underlying the IP based approach to BNSL is still somewhat lacking. Understanding fundamental aspects of cutting planes and the related separation problem is important not only from a purely theoretical perspective, but also since it holds out the promise of further improving the efficiency of state-of-the-art approaches to solving BNSL exactly. In this paper, we make several theoretical contributions towards these goals: (i) we study the computational complexity of the separation problem, proving that the problem is NP-hard; (ii) we formalise and analyse the relationship between three key polytopes underlying the IP-based approach to BNSL; (iii) we study the facets of the three polytopes both from the theoretical and practical perspective, providing, via exhaustive computation, a complete enumeration of facets for low-dimensional family-variable polytopes; and, furthermore, (iv) we establish a tight connection of the BNSL problem to the acyclic subgraph problem.

IJCAI Conference 2017 Conference Paper

Bayesian Network Structure Learning with Integer Programming: Polytopes, Facets and Complexity (Extended Abstract)

• James Cussens
• Matti Järvisalo
• Janne H. Korhonen
• Mark Bartlett

Developing accurate algorithms for learning structures of probabilistic graphical models is an important problem within modern AI research. Here we focus on score-based structure learning for Bayesian networks as arguably the most central class of graphical models. A successful generic approach to optimal Bayesian network structure learning (BNSL), based on integer programming (IP), is implemented in the Gobnilp system. Despite the recent algorithmic advances, current understanding of foundational aspects underlying the IP based approach to BNSL is still somewhat lacking. In this paper, we provide theoretical contributions towards understanding fundamental aspects of cutting planes and the related separation problem in this context, ranging from NP-hardness results to analysis of polytopes and the related facets in connection to BNSL.

AIJ Journal 2017 Journal Article

Integer Linear Programming for the Bayesian network structure learning problem

• Mark Bartlett
• James Cussens

Bayesian networks are a commonly used method of representing conditional probability relationships between a set of variables in the form of a directed acyclic graph (DAG). Determination of the DAG which best explains observed data is an NP-hard problem [1]. This problem can be stated as a constrained optimisation problem using Integer Linear Programming (ILP). This paper explores how the performance of ILP-based Bayesian network learning can be improved through ILP techniques and in particular through the addition of non-essential, implied constraints. There are exponentially many such constraints that can be added to the problem. This paper explores how these constraints may best be generated and added as needed. The results show that using these constraints in the best discovered configuration can lead to a significant improvement in performance and show significant improvement in speed using a state-of-the-art Bayesian network structure learner.

UAI Conference 2013 Conference Paper

Advances in Bayesian Network Learning using Integer Programming

• James Cussens
• Mark Bartlett

We consider the problem of learning Bayesian networks (BNs) from complete discrete data. This problem of discrete optimisation is formulated as an integer program (IP). We describe the various steps we have taken to allow efficient solving of this IP. These are (i) efficient search for cutting planes, (ii) a fast greedy algorithm to find high-scoring (perhaps not optimal) BNs and (iii) tightening the linear relaxation of the IP. After relating this BN learning problem to set covering and the multidimensional 0-1 knapsack problem, we present our empirical results. These show improvements, sometimes dramatic, over earlier results.

UAI Conference 2011 Conference Paper

Bayesian network learning with cutting planes

• James Cussens

ECAI Conference 2010 Conference Paper

Instruction Cache Prediction Using Bayesian Networks

• Mark Bartlett
• Iain Bate
• James Cussens

Storing instructions in caches has led to dramatic increases in the speed at which programs can execute. However, this has also made it harder to reason about the time needed for execution in those domains where temporal behaviour of code is important. This paper presents a novel approach to predicting which instructions will be found in the cache when required using machine learning. More specifically, we demonstrate a method in which a Bayesian network is inferred from examples of a program running and is then used to predict the presence of instructions in the cache when the same program is run with unknown inputs.

UAI Conference 2008 Conference Paper

Bayesian network learning by compiling to weighted MAX-SAT

• James Cussens

The problem of learning discrete Bayesian networks from data is encoded as a weighted MAX-SAT problem and the MaxWalkSat local search algorithm is used to address it. For each dataset, the per-variable summands of the (BDeu) marginal likelihood for different choices of parents (‘family scores’) are computed prior to applying MaxWalkSat. Each permissible choice of parents for each variable is encoded as a distinct propositional atom and the associated family score encoded as a ‘soft’ weighted single-literal clause. Two approaches to enforcing acyclicity are considered: either by encoding the ancestor relation or by attaching a total order to each graph and encoding that. The latter approach gives better results. Learning experiments have been conducted on 21 synthetic datasets sampled from 7 BNs. The largest dataset has 10,000 datapoints and 60 variables producing (for the ‘ancestor’ encoding) a weighted CNF input file with 19,932 atoms and 269,367 clauses. For most datasets, MaxWalkSat quickly finds BNs with higher BDeu score than the ‘true’ BN. The effect of adding prior information is assessed. It is further shown that Bayesian model averaging can be effected by collecting BNs generated during the search.

ICML Conference 2005 Conference Paper

Tempering for Bayesian C&RT

• Nicos Angelopoulos
• James Cussens

UAI Conference 2003 Conference Paper

CLP(BN): Constraint Logic Programming for Probabilistic Knowledge

• Vítor Santos Costa
• David Page
• Maleeha Qazi
• James Cussens

We present CLP(BN), a novel approach that aims at expressing Bayesian networks through the constraint logic programming framework. Arguably, an important limitation of traditional Bayesian networks is that they are propositional, and thus cannot represent relations between multiple similar objects in multiple contexts. Several researchers have thus proposed first-order languages to describe such networks. Namely, one very successful example of this approach are the Probabilistic Relational Models (PRMs), that combine Bayesian networks with relational database technology. The key difficulty that we had to address when designing CLP(cal{BN}) is that logic based representations use ground terms to denote objects. With probabilitic data, we need to be able to uniquely represent an object whose value we are not sure about. We use {sl Skolem functions} as unique new symbols that uniquely represent objects with unknown value. The semantics of CLP(cal{BN}) programs then naturally follow from the general framework of constraint logic programming, as applied to a specific domain where we have probabilistic data. This paper introduces and defines CLP(cal{BN}), and it describes an implementation and initial experiments. The paper also shows how CLP(cal{BN}) relates to Probabilistic Relational Models (PRMs), Ngo and Haddawys Probabilistic Logic Programs, AND Kersting AND De Raedts Bayesian Logic Programs

UAI Conference 2001 Conference Paper

Markov Chain Monte Carlo using Tree-Based Priors on Model Structure

• Nicos Angelopoulos
• James Cussens

UAI Conference 2000 Conference Paper

Stochastic Logic Programs: Sampling, Inference and Applications

• James Cussens

UAI Conference 1999 Conference Paper

Loglinear models for first-order probabilistic reasoning

• James Cussens

Recent work on loglinear models in probabilistic constraint logic programming is applied to first-order probabilistic reasoning. Probabilities are defined directly on the *proofs* of atomic formulae, and by marginalisation on the atomic formulae themselves. We use Stochastic Logic Programs (SLPs) composed of labelled and unlabelled definite clauses to define the proof probabilities. We have a conservative extension of first-order reasoning, so that, for example, there is a one-one mapping between logical and random variables. We show how, in this framework, Inductive Logic Programming (ILP) can be used to induce the features of a loglinear model from data. We also compare the presented framework with other approaches to first-order probabilistic reasoning.

ICML Conference 1995 Conference Paper

A Bayesian Analysis of Algorithms for Learning Finite Functions

• James Cussens

AAAI Conference 1993 Conference Paper

Generating Explicit Orderings for Non-monotonic Logics

• James Cussens

For non-monotonic reasoning, explicit orderings over formulae offer an important solution to problems such as ‘ multiple extensions’. However, a criticism of such a solution is that it is not clear, in general, from where the orderings should be obtained. Here we show how orderings can be derived from statistical information about the domain which the formulae cover. For this we provide an overview of prioritized logics-a general class of logics that incorporate explicit orderings over formulae. This class of logics has been shown elsewhere to capture a wide variety of proof-theoretic approaches to non-monotonic reasoning, and in particular, to highlight the role of preferences-both implicit and explicit-in such proof theory. We take one particular prioritized logic, called SF logic, and describe an experimental approach for comparing this logic with an important example of a logic that does not use explicit orderings of preference-namely Horn clause logic with negation-as-failure. Finally, we present the results of this comparison, showing how SF logic is more skeptical and more accurate than negation-as-failure.