Integer linear programming approach to learning Bayesian network structure: towards the essential graph

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985556%3A_____%2F12%3A00381536" target="_blank" >RIV/67985556:_____/12:00381536 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Integer linear programming approach to learning Bayesian network structure: towards the essential graph

Popis výsledku v původním jazyce

The basic idea of a geometric approach to learning a Bayesian network (BN) structure is to represent every BN structure by a certain vector. This may allow 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 2010. In this paper, extensions of characteristic imsets are considered which additionally encode chain graphs without flagsequivalent to acyclic directed graphs. The main contribution is the polyhedral description of the respective domain of the ILP problem. 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.

Název v anglickém jazyce

Integer linear programming approach to learning Bayesian network structure: towards the essential graph

Popis výsledku anglicky

The basic idea of a geometric approach to learning a Bayesian network (BN) structure is to represent every BN structure by a certain vector. This may allow 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 2010. In this paper, extensions of characteristic imsets are considered which additionally encode chain graphs without flagsequivalent to acyclic directed graphs. The main contribution is the polyhedral description of the respective domain of the ILP problem. 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.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA201%2F08%2F0539" target="_blank" >GA201/08/0539: Struktury podmíněné nezávislosti: grafické a algebraické přístupy</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2012

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 6th European Workshop on Graphical Models

ISBN

978-84-15536-57-4

ISSN

—

e-ISSN

—

Počet stran výsledku

8

Strana od-do

307-314

Název nakladatele

DESCAI, University of Granada

Místo vydání

Granada

Místo konání akce

Granada

Datum konání akce

19. 9. 2012

Typ akce podle státní příslušnosti

EUR - Evropská akce

Kód UT WoS článku

—