## 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.

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 language | English |
---|---|

Title of host publication | Algebraic and Geometric Methods in Discrete Mathematics |

Subtitle of host publication | Contemporary Mathematics |

Place of Publication | Providence, RI |

Publisher | American Mathematical Society |

Pages | 155-188 |

Number of pages | 34 |

Volume | 685 |

ISBN (Electronic) | 978-1-4704-3743-5 |

DOIs | |

Publication status | Published - 2017 |