Learning with Bounded Treewidth

Methods

Goal: structure learning of Bayesian networks with bounded treewidth.

Motivation: the complexity of exact inference in Bayesian networks is exponential to the treewidth of the graph.

Proposed methods

  • Mixed Integer Linear Programming: an exact method that combines the integer programming formulation of BN structure learning with a novel approach to empose the treewidth constraint. The exact algorithm can exactly learn the BN structure with 30 nodes.
  • Heuristic search: an approximate algorithm based on the family of k-trees. Propose an efficient algorithm for search for k-trees, and then learn the structure of the BN as a subgraph of the k-tree. Propose the hill climbing and A* search algorithms. The approximate algorithm can scale up to network with 100 nodes.

    Publications

    Articles in journals

    Siqi Nie, Cassio P. de Campos, and Qiang Ji, "Efficient Learning of Bayesian Networks with Bounded Tree-width," International Journal of Approximate Reasoning (IJAR), 2016. [link]

    Articles in conference proceedings

    Siqi Nie, Cassio P. de Campos, and Qiang Ji, "Learning Bayesian Networks with Bounded Tree-width via Guided Search," in AAAI Conference on Artificial Intelligence (AAAI), 2016. Oral Presentation. [PDF] [supp]

    Siqi Nie, Cassio P. de Campos, and Qiang Ji, "Learning Bounded Tree-width Bayesian Networks via Sampling," in Proceedings of the 13th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU), 2015. [PDF]

    Siqi Nie, Denis D. Mauá, Cassio P. de Campos, and Qiang Ji, "Advances in Learning Bayesian Networks of Bounded Treewidth," in Advances in Neural Information Processing Systems (NIPS), 2014. Spotlight Presentation. [PDF] [supp] [arXiv]