GOBNILP

[Benchmarks] [Papers using GOBNILP]

GOBNILP (Globally Optimal Bayesian Network learning using Integer Linear Programming) is a C program which learns Bayesian networks from local scores. The GOBNILP distribution provides a separate C program to generate BDeu local scores from complete discrete data. GOBNILP uses the SCIP framework for Constraint Integer Programming. Detailed information on installing, running, licence etc can be found in the:

• GOBNILP manual

which is also contained in the GOBNILP distribution.

GOBNILP has been developed by James Cussens and Mark Bartlett. It is supported by MRC grant A graphical model approach to pedigree construction using constrained optimisation (G1002312). Goblin 'P' logo courtesy of Robby Higgins.

Download GOBNILP

Benchmarks for the current version

GOBNILP has been developed using a set of local score files used originally in the paper Bayesian network learning with cutting planes. Most of these local score input files are in this gzipped tar file. The local score input files alarm, mirna, phen and wdbc were kindly sent to me by Tommi Jaakkola, the others I generated myself. More recently a couple of local score input files (developed by Mark Bartlett) for learning pedigrees have been used as part of the Pedigree Reconstruction using Integer Linear Programming project. GOBNILP 1.2 and upwards contains software for generating local scores from data. Where available the original data and the local scores generated from it are available from this directory. (This directory also contain some local score files where the data from which they were generated is not available.)

The following table provides a summary of benchmarking results for GOBNILP 1.2 and GOBNILP 1.3 using SCIP 2.1 (the recommended version of SCIP) and default parameter settings. All times are in seconds. The GOBNILP output for each of these runs is available from this directory. (Benchmark results for older GOBNILP versions are available here.) 'BN' is the name of the BN from which the data was originally generated. 'p' is the number of variables in the original dataset (and thus in the optimal BN). 'n' is the number of datapoints in the data. 'palim' is the limit on the size of parent sets in any learned BN. '|PaSets|' is the number of candidate parent sets generated by GOBNILP's local scoring algorithm - this is the size of the input to the main GOBNILP learning algorithm. 'Scoring' is the time taken to produce the local scores. 'Finding' is the time taken to find an optimal BN. 'Solving' is the time taken to solve the problem (find an optimal BN and prove that it is optimal.) A blank entry in 'Finding' indicates that GOBNILP failed to solve the problem. In such cases, if GOBNILP made at least some progress the 'Solving' column records how large the 'gap' was after the indicated number of seconds. If GOBNILP made no progress, then 'Solving' has the entry FAIL.

Benchmarks run on a single core of the following machine: Linux 3.0.18-x86_64 #1 SMP PREEMPT Thu Jan 26 12:54:10 GMT 2012 x86_64 Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00GHz GenuineIntel GNU/Linux. CPLEX 12.1.0.0 was used as the LP solver.

Papers using GOBNILP

• Waleed Alsanie. Learning Failure-free PRISM Programs. PhD Thesis, University of York, September 2012.
• Zhenxing Wang and Laiwan Chan. Learning Bayesian Networks from Markov Random Fields: An Efficient Algorithm for Linear Models. ACM Transactions on Knowledge Discovery from Data (TKDD). 6(3) 2012 10:1-10:31.
• Robert G. Cowell. A simple greedy algorithm for reconstructing pedigrees. Theoretical Population Biology. 83 (2013) 55-63.
• James Cussens. Bayesian network learning with cutting planes. In Fabio G. Cozman and Avi Pfeffer, editors, Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence (UAI 2011), pages 153-160, Barcelona, 2011. AUAI Press. This paper introduces the basic idea of the GOBNILP approach and uses a preliminary version of the software.

Last modified: Wed Apr 3 10:33:39 BST 2013