Towards using the chordal graph polytope in learning decomposable models

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985556%3A_____%2F17%3A00475614" target="_blank" >RIV/67985556:_____/17:00475614 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.ijar.2017.06.001" target="_blank" >http://dx.doi.org/10.1016/j.ijar.2017.06.001</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.ijar.2017.06.001" target="_blank" >10.1016/j.ijar.2017.06.001</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Towards using the chordal graph polytope in learning decomposable models

Popis výsledku v původním jazyce

The motivation for this paper is the integer linear programming (ILP) approach to learning the structure of a decomposable graphical model. We have chosen to represent decomposable models by means of special zero-one vectors, named characteristic imsets. Our approach leads to the study of a special polytope, defined as the convex hull of all characteristic imsets for chordal graphs, named the chordal graph polytope. In this theoretical paper, we introduce a class of clutter inequalities (valid for the vectors in the polytope) and show that all of them are facet-defining for the polytope. We dare to conjecture that they lead to a complete polyhedral description of the polytope. Finally, we propose a linear programming method to solve the separation problem with these inequalities for the use in a cutting plane approach.

Název v anglickém jazyce

Towards using the chordal graph polytope in learning decomposable models

Popis výsledku anglicky

The motivation for this paper is the integer linear programming (ILP) approach to learning the structure of a decomposable graphical model. We have chosen to represent decomposable models by means of special zero-one vectors, named characteristic imsets. Our approach leads to the study of a special polytope, defined as the convex hull of all characteristic imsets for chordal graphs, named the chordal graph polytope. In this theoretical paper, we introduce a class of clutter inequalities (valid for the vectors in the polytope) and show that all of them are facet-defining for the polytope. We dare to conjecture that they lead to a complete polyhedral description of the polytope. Finally, we propose a linear programming method to solve the separation problem with these inequalities for the use in a cutting plane approach.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10103 - Statistics and probability

Projekt

<a href="/cs/project/GA16-12010S" target="_blank" >GA16-12010S: Struktury podmíněné nezávislosti: kombinatorické a optimalizační metody</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2017

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 periodika

International Journal of Approximate Reasoning

ISSN

0888-613X

e-ISSN

—

Svazek periodika

88

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

23

Strana od-do

259-281

Kód UT WoS článku

000407655600014

EID výsledku v databázi Scopus

2-s2.0-85021109619