Polyhedral approaches to learning Bayesian networks

David Haws, James Cussens, Milan Studený

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

Learning Bayesian network structure is the NP-hard task of finding
a directed acyclic graph that best fits real data. Two integer vector encodings
exist – family variable and characteristic imset – which model the
solution space of BN structure. Each encoding yields a polytope, the familyvariable
and characteristic imset polytopes respectively. It has been shown
that learning BN structure using a decomposable and score equivalent scoring
criteria (such as BIC) is equivalent to optimizing a linear function over
either the family-variable or characteristic imset polytope. This monograph
is primarily intended for readers already familiar with BN but not familiar
with polyhedral approaches to learning BN. Thus, this monograph focuses on
the family-variable and characteristic imset polytopes, their known faces and
facets, and more importantly, deep connections between their faces and facets.
Specifically that many of the faces of the family variable polytope are superfluous
when learning BN structure. Sufficient background on Bayesian networks,
graphs, and polytopes are provided. The currently known faces and facets of
each polytope are described. Deep connections between many of the faces and
facets of family-variable and characteristic polytope are then summarized from
recent results. Lastly, a brief history and background on practical approaches
to learning BN structure using integer linear programming over both polytopes
is provided.
Original languageEnglish
Title of host publicationAlgebraic and Geometric Methods in Discrete Mathematics
Subtitle of host publicationContemporary Mathematics
Place of PublicationProvidence, RI
PublisherAmerican Mathematical Society
Pages155-188
Number of pages34
Volume685
ISBN (Electronic)978-1-4704-3743-5
DOIs
Publication statusPublished - 2017

Cite this