Learning Bayesian network structure: Towards the essential graph by integer linear programming tools

The basic idea of the geometric approach to learning a Bayesian network (BN) structure is to represent every BN structure by a certain vector. If the vector representative is chosen properly, it allows one to re-formulate the task of finding the global maximum of a score over BN structures as an integer linear programming (ILP) problem. Such a suitable zero-one vector representative is the characteristic imset, introduced by Studeny, Hemmecke and Lindner in 2010, in the proceedings of the 5th PGM workshop. In this paper, extensions of characteristic imsets are considered which additionally encode chain graphs without flags equivalent to acyclic directed graphs. The main contribution is a polyhedral description of the respective domain of the ILP problem, that is, by means of a set of linear inequalities. This theoretical result opens the way to the application of ILP software packages. The advantage of our approach is that, as a by-product of the ILP optimization procedure, one may get the essential graph, which is a traditional graphical BN representative. We also describe some computational experiments based on this idea.

Related papers:

title: Optimal Structure Identification With Greedy Search
abstract: In this paper we prove the so-called "Meek Conjecture". In particular, we show that if a DAG H is an independence map of another DAG G, then there exists a finite sequence of edge additions and covered edge reversals in G such that (1) after each edge modification H remains an independence map of G and (2) after all modifications G =H. As shown by Meek (1997), this result has an important consequence for Bayesian approaches to learning Bayesian networks from data: in the limit of large sample size, there exists a two-phase greedy search algorithm that---when applied to a particular sparsely-connected search space---provably identifies a perfect map of the generative distribution if that perfect map is a DAG. We provide a new implementation of the search space, using equivalence classes as states, for which all operators used in the greedy search can be scored efficiently using local functions of the nodes in the domain. Finally, using both synthetic and real-world datasets, we demonstrate that the two-phase greedy approach leads to good solutions when learning with finite sample sizes.

title: Probabilistic conditional independence structures
abstract: Probabilistic Conditional Independence Structures provides the mathematical description of probabilistic conditional independence structures; the author uses non-graphical methods of their description, and takes an algebraic approach. The monograph presents the methods of structural imsets and supermodular functions, and deals with independence implication and equivalence of structural imsets. Motivation, mathematical foundations and areas of application are included, and a rough overview of graphical methods is also given. In particular, the author has been careful to use suitable terminology, and presents the work so that it will be understood by both statisticians, and by researchers in artificial intelligence. The necessary elementary mathematical notions are recalled in an appendix.

title: A geometric view on learning Bayesian network structures
abstract: We recall the basic idea of an algebraic approach to learning Bayesian network (BN) structures, namely to represent every BN structure by a certain (uniquely determined) vector, called a standard imset. The main result of the paper is that the set of standard imsets is the set of vertices (=extreme points) of a certain polytope. Motivated by the geometric view, we introduce the concept of the geometric neighborhood for standard imsets, and, consequently, for BN structures. Then we show that it always includes the inclusion neighborhood, which was introduced earlier in connection with the greedy equivalence search (GES) algorithm. The third result is that the global optimum of an affine function over the polytope coincides with the local optimum relative to the geometric neighborhood. To illustrate the new concept by an example, we describe the geometric neighborhood in the case of three variables and show it differs from the inclusion neighborhood. This leads to a simple example of the failure of the GES algorithm if data are not ''generated'' from a perfectly Markovian distribution. The point is that one can avoid this failure if the search technique is based on the geometric neighborhood instead. We also found out what is the geometric neighborhood in the case of four and five variables.

title: Characteristic imset: a simple algebraic representative of a Bayesian network structure
abstract: First, we recall the basic idea of an algebraic and geometric approach to learning a Bayesian network (BN) structure proposed in (Studen y, Vomlel and Hemmecke, 2010): to represent every BN structure by a certain uniquely determined vector. The original proposal was to use a so-called standard imset which is a vector having integers as components, as an algebraic representative of a BN structure. In this paper we propose an even simpler algebraic representative called the characteristic imset. It is 0-1-vector obtained from the standard imset by an ane transformation. This implies that every reasonable quality criterion is an ane function of the characteristic imset. The characteristic imset is much closer to the graphical description: we establish a simple relation to any chain graph without ags that denes the BN structure. In particular, we are interested in the relation to the essential graph, which is a classic graphical BN structure representative. In the end, we discuss two special cases in which the use of characteristic imsets particularly simplies things: learning decomposable models and (undirected) forests.

title: Characteristic imsets for learning Bayesian network structure
abstract: The motivation for the paper is the geometric approach to learning Bayesian network (BN) structure. The basic idea of our approach is to represent every BN structure by a certain uniquely determined vector so that usual scores for learning BN structure become affine functions of the vector representative. The original proposal from Studeny et al. (2010)  was to use a special vector having integers as components, called the standard imset, as the representative. In this paper we introduce a new unique vector representative, called the characteristic imset, obtained from the standard imset by an affine transformation. Characteristic imsets are (shown to be) zero-one vectors and have many elegant properties, suitable for intended application of linear/integer programming methods to learning BN structure. They are much closer to the graphical description; we describe a simple transition between the characteristic imset and the essential graph, known as a traditional unique graphical representative of the BN structure. In the end, we relate our proposal to other recent approaches which apply linear programming methods in probabilistic reasoning.

title: Maximum likelihood pedigree reconstruction using integer programming
abstract: Pedigrees are ‘family trees’ relating groups of individuals which can usefully be seen as Bayesian networks. The problem of finding a maximum likelihood pedigree from genotypic data is encoded as an integer linear programming problem. Two methods of ensuring that pedigrees are acyclic are considered. Results on obtaining maximum likelihood pedigrees relating 20, 46 and 59 individuals are presented. Running times for larger pedigrees depend strongly on the data used but generally compare well with those in the literature. Solving is particularly fast when allele frequency is uniform.

title: Bayesian network learning with cutting planes
abstract: The problem of learning the structure of Bayesian networks from complete discrete data with a limit on parent set size is considered. Learning is cast explicitly as an optimisation problem where the goal is to find a BN structure which maximises log marginal likelihood (BDe score). Integer programming, specifically the SCIP framework, is used to solve this optimisation problem. Acyclicity constraints are added to the integer program (IP) during solving in the form of cutting planes. Finding good cutting planes is the key to the success of the approach—the search for such cutting planes is effected using a sub-IP. Results show that this is a particularly fast method for exact BN learning.

title: Structure learning of Bayesian networks using constraints
abstract: This paper addresses exact learning of Bayesian network structure from data and expert's knowledge based on score functions that are decomposable. First, it describes useful properties that strongly reduce the time and memory costs of many known methods such as hill-climbing, dynamic programming and sampling variable orderings. Secondly, a branch and bound algorithm is presented that integrates parameter and structural constraints with data in a way to guarantee global optimality with respect to the score function. It is an any-time procedure because, if stopped, it provides the best current solution and an estimation about how far it is from the global solution. We show empirically the advantages of the properties and the constraints, and the applicability of the algorithm to large data sets (up to one hundred variables) that cannot be handled by other current methods (limited to around 30 variables).

title: Efficient Structure Learning of Bayesian Networks using Constraints
abstract: This paper addresses the problem of learning Bayesian network structures from data based on score functions that are decomposable. It describes properties that strongly reduce the time and memory costs of many known methods without losing global optimality guarantees. These properties are derived for different score criteria such as Minimum Description Length (or Bayesian Information Criterion), Akaike Information Criterion and Bayesian Dirichlet Criterion. Then a branch-and-bound algorithm is presented that integrates structural constraints with data in a way to guarantee global optimality. As an example, structural constraints are used to map the problem of structure learning in Dynamic Bayesian networks into a corresponding augmented Bayesian network. Finally, we show empirically the benefits of using the properties with state-of-the-art methods and with the new algorithm, which is able to handle larger data sets than before.

title: On Polyhedral Approximations of Polytopes for Learning Bayesian Networks
abstract: The motivation for this paper is the geometric approach to statistical learning Bayesian network (BN) structures. We review three vector encodings of BN structures. The first one has been used by Jaakkola et al. (9) and also by Cussens (4), the other two use special integral vectors formerly introduced, called imsets (18, 20). The topic is the comparison of outer polyhedral approx- imations of the corresponding polytopes. We show how to transform the inequalities suggested by Jaakkola et al. (9) into the framework of imsets. The result of our comparison is the observation that the implicit polyhedral approximation of the standard imset polytope suggested in (21) gives a tighter approximation than the (transformed) explicit polyhedral approximation from (9). As a consequence, we confirm a conjecture from (21) that the above-mentioned implicit polyhedral approximation of the standard imset polytope is an LP relaxation of that polytope. In the end, we review recent attempts to apply the methods of integer programming to learning BN structures and discuss the task of finding suitable explicit LP relaxation in the imset-based approach.

title: A characterization of Markov equivalence classes for acyclic digraphs
abstract: Undirected graphs and acyclic digraphs (ADGs), as well as their mutual extension to chain graphs, are widely used to describe dependencies among variables in multivariate distributions. In particular, the likelihood functions of ADG models admit convenient recursive factorizations that often allow explicit maximum likelihood estimates and that are well suited to building Bayesian networks for expert systems. Whereas the undirected graph associated with a dependence model is uniquely determined, there may, however, be many ADGs that determine the same dependence (= Markov) model. Thus, the family of all ADGs with a given set of vertices is naturally partitioned into Markov-equivalence classes, each class being associated with a unique statistical model. Statistical procedures, such as model selection or model averaging, that fail to take into account these equivalence classes, may incur substantial computational or other inefficiencies. Here it is shown that each Markov-equivalence class is uniquely determined by a single chain graph, the essential graph, that is itself simultaneously Markov equivalent to all ADGs in the equivalence class. Essential graphs are characterized, a polynomial-time algorithm for their construction is given, and their applications to model selection and other statistical questions are described.

title: Chapter 4 – Learning Bayesian Networks
abstract: This chapter addresses the problem of learning the parameters from data. It also discusses score-based structure learning and constraint-based structure learning. The method for learning all parameters in a Bayesian network follows readily from the method for learning a single parameter. The chapter presents a method for learning the probability of a binomial variable and extends this method to multinomial variables. It also provides guidelines for articulating the prior beliefs concerning probabilities. The chapter illustrates the constraint-based approach by showing how to learn a directed acyclic graph (DAG) faithful to a probability distribution. Structure learning consists of learning the DAG in a Bayesian network from data. It is necessary to know which DAG satisfies the Markov condition with the probability distribution P that is generating the data. The process of learning such a DAG is called “model selection.” A DAG includes a probability distribution P if the DAG does not entail any conditional independencies that are not in P. In score-based structure learning, a score is assigned to each DAG based on the data such that in the limit. After scoring the DAGs, the score are used, possibly along with prior probabilities, to learn a DAG. The most straightforward score, the Bayesian score, is the probability of the data D given the DAG. Once a DAG is learnt from data, the parameters can be known. The result will be a Bayesian network that can be used to do inference. In the constraint-based approach, a DAG is found for which the Markov condition entails all and only those conditional independencies that are in the probability distribution P of the variables of interest. The chapter applies structure learning to inferring causal influences from data and presents learning packages. It presents examples of learning Bayesian networks and of causal learning.

title: Locally averaged Bayesian Dirichlet metrics for learning the structure and the parameters of Bayesian networks
abstract: The marginal likelihood of the data computed using Bayesian score metrics is at the core of score+search methods when learning Bayesian networks from data. However, common formulations of those Bayesian score metrics rely on free parameters which are hard to assess. Recent theoretical and experimental works have also shown that the commonly employed BDe score metric is strongly biased by the particular assignments of its free parameter known as the equivalent sample size. This sensitivity means that poor choices of this parameter lead to inferred BN models whose structure and parameters do not properly represent the distribution generating the data even for large sample sizes. In this paper we argue that the problem is that the BDe metric is based on assumptions about the BN model parameters distribution assumed to generate the data which are too strict and do not hold in real settings. To overcome this issue we introduce here an approach that tries to marginalize the meta-parameter locally, aiming to embrace a wider set of assumptions about these parameters. It is shown experimentally that this approach offers a robust performance, as good as that of the standard BDe metric with an optimum selection of its free parameter and, in consequence, this method prevents the choice of wrong settings for this widely applied Bayesian score metric.

title: Branching rules revisited
abstract: We present a new generalization called reliability branching of today's state-of-the-art strong branching and pseudocost branching strategies for linear programming based branch-and-bound algorithms. After reviewing commonly used branching strategies and performing extensive computational studies we compare different parameter settings and show the superiority of our proposed new strategy.

title: Integer Linear Programming Approach to Learning Bayesian Network Structure: towards the Essential Graph
abstract: The basic idea of a geometric approach to learning a Bayesian network (BN) structure is to represent every BN structure by a certain vector. If the vector representative is chosen properly, it allows one to re-formulate the task of finding the global maximum of a score over BN structures as an integer linear programming (ILP) problem. Suitable such a zero- one vector representative is the characteristic imset, introduced in (Studeny, Hemmecke and Lindner, 2010). In this paper, extensions of characteristic imsets are considered which additionally encode chain graphs without flags equivalent to acyclic directed graphs. The main contribution is the polyhedral description (= in terms of a set of linear inequalities) of the respective domain of the ILP problem. It is just a theoretical result, but it opens the way to the application of ILP software packages in the area of learning a BN structure. The advantage of this approach is that, as a by-product of the ILP optimization procedure, one may get the essential graph, which is a traditional graphical BN representative.

title: Computer Codes for Problems of Integer Programming
abstract: Publisher Summary This chapter presents computer codes for the problems of integer programming. The term “integer programming” covers a wide spectrum of models, which can be characterized by mixed integer programming (MIP) at one end and combinatorial programming at the other end. The interest of those working in commercial organizations is currently focused at the MIP end of the spectrum—indeed on problems, which are basically large linear programming (LP) systems with relatively few integer variables. The chapter presents a “consumer research” report on the different products and also the methods for solving pure integer problems—frequently with special combinatorial structures. Thus, in a consumer report, one has to bear in mind, which consumers are intended for each code. The code should be capable of obtaining a guaranteed optimum solution. A large and complex problem may not be capable of yielding an optimum integer solution within feasible cost and time limits on any code so that the user has in fact to be content with a significant solution obtained by heuristic methods.

title: A Computational Study of Search Strategies for Mixed Integer Programming
abstract: The branch-and-bound procedure for solving mixed integer programming (MIP) problems using linear programming relaxations has been used with great success for decades. Over the years, a variety of researchers have studied ways of making the basic algorithm more effective. Breakthroughs in the fields of computer hardware, computer software, and mathematics have led to increasing success at solving larger and larger MIP instances. The goal of this article is to survey many of the results regarding branch-and-bound search strategies and evaluate them again in light of the other advances that have taken place over the years. In addition, novel search strategies are presented and shown to often perform better than those currently used in practice.

title: Maximum likelihood pedigree reconstruction using integer programming
abstract: Pedigrees are ‘family trees’ relating groups of individuals which can usefully be seen as Bayesian networks. The problem of finding a maximum likelihood pedigree from genotypic data is encoded as an integer linear programming problem. Two methods of ensuring that pedigrees are acyclic are considered. Results on obtaining maximum likelihood pedigrees relating 20, 46 and 59 individuals are presented. Running times for larger pedigrees depend strongly on the data used but generally compare well with those in the literature. Solving is particularly fast when allele frequency is uniform.