liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Learning Optimal Chain Graphs with Answer Set Programming
Linköping University, Department of Computer and Information Science, Database and information techniques. Linköping University, Faculty of Science & Engineering. (ADIT)
Helsinki Institute for Information Technology HIIT; Department of Computer Science, University of Helsinki, Finland.
Linköping University, Department of Computer and Information Science, Database and information techniques. Linköping University, Faculty of Science & Engineering. (ADIT)
Helsinki Institute for Information Technology HIIT; Department of Computer Science, University of Helsinki, Finland.
2015 (English)In: Proceedings of the Thirty-First Conference (2015) Uncertainty In Artificial Intelligence / [ed] Marina Meila and Tom Heskes, AUAI Press , 2015, 822-831 p.Conference paper (Refereed)
Abstract [en]

Learning an optimal chain graph from data is an important hard computational problem. We present a new approach to solve this problem for various objective functions without making any assumption on the probability distribution at hand. Our approach is based on encoding the learning problem declaratively using the answer set programming (ASP) paradigm. Empirical results show that our approach provides at least as accurate solutions as the best solutions provided by the existing algorithms, and overall provides better accuracy than any single previous algorithm.

Place, publisher, year, edition, pages
AUAI Press , 2015. 822-831 p.
Keyword [en]
Chain Graphs, Graph Structure Learning, Answer Set Programming
National Category
Other Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-120695ISBN: 978-0-9966431-0-8OAI: oai:DiVA.org:liu-120695DiVA: diva2:847849
Conference
Conference on Uncertainty in Artificial Intelligence : July 12‑16, 2015, Amsterdam, Netherlands
Funder
Swedish Research Council, 2010-4808
Available from: 2015-08-21 Created: 2015-08-21 Last updated: 2016-05-24Bibliographically approved
In thesis
1. Chain Graphs: Interpretations, Expressiveness and Learning Algorithms
Open this publication in new window or tab >>Chain Graphs: Interpretations, Expressiveness and Learning Algorithms
2016 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Probabilistic graphical models are currently one of the most commonly used architectures for modelling and reasoning with uncertainty. The most widely used subclass of these models is directed acyclic graphs, also known as Bayesian networks, which are used in a wide range of applications both in research and industry. Directed acyclic graphs do, however, have a major limitation, which is that only asymmetric relationships, namely cause and effect relationships, can be modelled between their variables. A class of probabilistic graphical models that tries to address this shortcoming is chain graphs, which include two types of edges in the models representing both symmetric and asymmetric relationships between the variables. This allows for a wider range of independence models to be modelled and depending on how the second edge is interpreted, we also have different so-called chain graph interpretations.

Although chain graphs were first introduced in the late eighties, most research on probabilistic graphical models naturally started in the least complex subclasses, such as directed acyclic graphs and undirected graphs. The field of chain graphs has therefore been relatively dormant. However, due to the maturity of the research field of probabilistic graphical models and the rise of more data-driven approaches to system modelling, chain graphs have recently received renewed interest in research. In this thesis we provide an introduction to chain graphs where we incorporate the progress made in the field. More specifically, we study the three chain graph interpretations that exist in research in terms of their separation criteria, their possible parametrizations and the intuition behind their edges. In addition to this we also compare the expressivity of the interpretations in terms of representable independence models as well as propose new structure learning algorithms to learn chain graph models from data.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2016. 44 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1748
Keyword
Chain Graphs, Probabilitstic Grapical Models
National Category
Computer Systems
Identifiers
urn:nbn:se:liu:diva-125921 (URN)10.3384/diss.diva-125921 (DOI)978-91-7685-818-9 (Print) (ISBN)
Public defence
2016-04-29, Visionen, B-House, Entrance 27, Campus Valla, Linköping, 13:15 (English)
Opponent
Supervisors
Funder
Swedish Research Council, 2010-4808
Available from: 2016-03-29 Created: 2016-03-08 Last updated: 2016-03-29Bibliographically approved

Open Access in DiVA

No full text

Other links

UAI 2015 Paper 189

Search in DiVA

By author/editor
Sonntag, DagPeña, Jose
By organisation
Database and information techniquesFaculty of Science & Engineering
Other Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 99 hits
ReferencesLink to record
Permanent link

Direct link