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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Chain Graphs: Interpretations, Expressiveness and Learning Algorithms
Linköping University, Department of Computer and Information Science, Database and information techniques. Linköping University, Faculty of Science & Engineering. (ADIT)
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 [en]
Chain Graphs, Probabilitstic Grapical Models
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:liu:diva-125921DOI: 10.3384/diss.diva-125921ISBN: 978-91-7685-818-9 (print)OAI: oai:DiVA.org:liu-125921DiVA: diva2:910177
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
List of papers
1. Chain Graphs and Gene Networks
Open this publication in new window or tab >>Chain Graphs and Gene Networks
2015 (English)In: Foundations of Biomedical Knowledge Representation: Methods and Applications / [ed] Arjen Hommersom and Peter J.F. Lucas, Springer, 2015, 159-178 p.Chapter in book (Refereed)
Abstract [en]

Chain graphs are graphs with possibly directed and undirected edges, and no semidirected cycle. They have been extensively studied as a formalism to represent probabilistic independence models, because they can model symmetric and asymmetric relationships between random variables. This allows chain graphs to represent a wider range of systems than Bayesian networks. This in turn allows for a more correct representation of systems that may contain both causal and non-causal relationships between its variables, like for example biological systems. In this chapter we give an overview of how to use chain graphs and what research exists on them today. We also give examples on how chain graphs can be used to model advanced systems, that are not well understood, such as gene networks.

Place, publisher, year, edition, pages
Springer, 2015
Series
Lecture Notes in Artificial Intelligence, ISSN 0302-9743 ; 9521
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-105813 (URN)10.1007/978-3-319-28007-3_10 (DOI)978-3-319-28006-6 (ISBN)978-3-319-28007-3 (ISBN)
Note

The previous status of this article was Manuscript.

Available from: 2014-04-08 Created: 2014-04-08 Last updated: 2016-03-29Bibliographically approved
2. Approximate Counting of Graphical Models Via MCMC Revisited
Open this publication in new window or tab >>Approximate Counting of Graphical Models Via MCMC Revisited
2015 (English)In: International Journal of Intelligent Systems, ISSN 0884-8173, E-ISSN 1098-111X, Vol. 30, no 3, 384-420 p.Article in journal (Refereed) Published
Abstract [en]

We apply MCMC sampling to approximately calculate some quantities, and discuss their implications for learning directed and acyclic graphs (DAGs) from data. Specifically, we calculate the approximate ratio of essential graphs (EGs) to DAGs for up to 31 nodes. Our ratios suggest that the average Markov equivalence class is small. We show that a large majority of the classes seem to have a size that is close to the average size. This suggests that one should not expect more than a moderate gain in efficiency when searching the space of EGs instead of the space of DAGs. We also calculate the approximate ratio of connected EGs to connected DAGs, of connected EGs to EGs, and of connected DAGs to DAGs. These new ratios are interesting because, as we will see, they suggest that some conjectures that appear in the literature do not hold. Furthermore, we prove that the latter ratio is asymptotically 1.

Finally, we calculate the approximate ratio of EGs to largest chain graphs for up to 25 nodes. Our ratios suggest that Lauritzen-Wermuth-Frydenberg chain graphs are considerably more expressive than DAGs. We also report similar approximate ratios and conclusions for multivariate regression chain graphs.

Place, publisher, year, edition, pages
Wiley-Blackwell, 2015
Keyword
MCMC sampling, Bayesian networks, Chain graphs, Lauritzen-Wermuth-Frydenberg interpretation, Multivariate regression interpretation
National Category
Computer and Information Science
Identifiers
urn:nbn:se:liu:diva-105815 (URN)10.1002/int.21704 (DOI)000348308600008 ()
Note

This work is funded by the Center for Industrial Information Technology (CENIIT) and a so-called career contract at Linkoping University, by the Swedish Research Council (ref. 2010-4808), and by FEDER funds and the Spanish Government (MICINN) through the projects TIN2010-20900-C04-03 and TIN2010-20900-C04-01.

Available from: 2014-04-08 Created: 2014-04-08 Last updated: 2017-12-05Bibliographically approved
3. Chain graph interpretations and their relations revisited
Open this publication in new window or tab >>Chain graph interpretations and their relations revisited
2015 (English)In: International Journal of Approximate Reasoning, ISSN 0888-613X, E-ISSN 1873-4731, Vol. 58, 39-56 p.Article in journal (Refereed) Published
Abstract [en]

In this paper we study how different theoretical concepts of Bayesian networks have been extended to chain graphs. Today there exist mainly three different interpretations of chain graphs in the literature. These are the Lauritzen-Wermuth-Frydenberg, the Andersson-Madigan-Perlman and the multivariate regression interpretations. The different chain graph interpretations have been studied independently and over time different theoretical concepts have been extended from Bayesian networks to also work for the different chain graph interpretations. This has however led to confusion regarding what concepts exist for what interpretation. In this article we do therefore study some of these concepts and how they have been extended to chain graphs as well as what results have been achieved so far. More importantly we do also identify when the concepts have not been extended and contribute within these areas. Specifically we study the following theoretical concepts: Unique representations of independence models, the split and merging operators, the conditions for when an independence model representable by one chain graph interpretation can be represented by another chain graph interpretation and finally the extension of Meeks conjecture to chain graphs. With our new results we give a coherent overview of how each of these concepts is extended for each of the different chain graph interpretations.

Place, publisher, year, edition, pages
Elsevier, 2015
Keyword
Chain graphs; Lauritzen-Wermuth-Frydenberg interpretation; Andersson-Madigan-Perlman interpretation; Multivariate regression interpretation
National Category
Computer and Information Science
Identifiers
urn:nbn:se:liu:diva-116826 (URN)10.1016/j.ijar.2014.12.001 (DOI)000350516100004 ()
Note

Funding Agencies|Center for Industrial Information Technology (CENIIT); Swedish Research Council [2010-4808]; FEDER funds; Spanish Government (MICINN) [TIN2010-20900-004-03]

Available from: 2015-04-07 Created: 2015-04-07 Last updated: 2017-12-04
4. On expressiveness of the chain graph interpretations
Open this publication in new window or tab >>On expressiveness of the chain graph interpretations
2016 (English)In: International Journal of Approximate Reasoning, ISSN 0888-613X, E-ISSN 1873-4731, Vol. 68, 91-107 p.Article in journal (Refereed) Published
Abstract [en]

In this article we study the expressiveness of the different chain graph interpretations. Chain graphs is a class of probabilistic graphical models that can contain two types of edges, representing different types of relationships between the variables in question. Chain graphs is also a superclass of directed acyclic graphs, i.e. Bayesian networks, and can thereby represent systems more accurately than this less expressive class of models. Today there do however exist several different ways of interpreting chain graphs and what conditional independences they encode, giving rise to different so-called chain graph interpretations. Previous research has approximated the number of representable independence models for the Lauritzen-Wermuth-Frydenberg and the multivariate regression chain graph interpretations using an MCMC based approach. In this article we use a similar approach to approximate the number of models representable by the latest chain graph interpretation in research, the Andersson-Madigan-Perlman interpretation. Moreover we summarize and compare the different chain graph interpretations with each other. Our results confirm previous results that directed acyclic graphs only can represent a small fraction of the models representable by chain graphs, even for a low number of nodes. The results also show that the Andersson-Madigan-Perlman and multivariate regression interpretations can represent about the same amount of models and twice the amount of models compared to the Lauritzen-Wermuth-Frydenberg interpretation. However, at the same time almost all models representable by the latter interpretation can only be represented by that interpretation while the former two have a large intersection in terms of representable models. (C) 2015 Elsevier Inc. All rights reserved.

Place, publisher, year, edition, pages
ELSEVIER SCIENCE INC, 2016
Keyword
Chain graphs; Lauritzen-Wermuth-Frydenberg interpretation; Andersson-Madigan-Perlman interpretation; Multivariate regression interpretation; MCMC sampling; Expressibility of probabilistic graphical models
National Category
Computer and Information Science
Identifiers
urn:nbn:se:liu:diva-124105 (URN)10.1016/j.ijar.2015.07.009 (DOI)000366774200008 ()
Note

Funding Agencies|Swedish Research Council [2010-4808]

Available from: 2016-01-25 Created: 2016-01-19 Last updated: 2017-11-30
5. Learning Multivariate Regression Chain Graphs under Faithfulness
Open this publication in new window or tab >>Learning Multivariate Regression Chain Graphs under Faithfulness
2012 (English)In: Proceedings of the 6th European Workshop on Probabilistic Graphical Models, Granada (Spain), 19-21 September, 2012 / [ed] Andrés Cano, Manuel Gémez.-Olmedo and Thomas D. Nielsen, 2012, 299-306 p.Conference paper, Published paper (Refereed)
Abstract [en]

This paper deals with multivariate regression chain graphs, which were introduced by Cox and Wermuth (1993, 1996) to represent linear causal models with correlated errors. Specifically, we present a constraint based algorithm for learning a chain graph a given probability distribution is faithful to. We also show that for each Markov equivalence class of multivariate regression chain graphs there exists a set of chain graphs with a unique minimal set of lines. Finally, we show that this set of lines can be identified from any member of the class by repeatedly splitting its connectivity components according to certain conditions.

Keyword
Chain Graph, Multivariate Regression Chain Graph, Learning, Bidirected Graph
National Category
Computer Systems
Identifiers
urn:nbn:se:liu:diva-80306 (URN)978-84-15536-57-4 (ISBN)
Conference
Sixth European Workshop on Probabilistic Graphical Models (PGM 2012), 19-21 September 2012, Granada, Spain
Available from: 2012-08-23 Created: 2012-08-23 Last updated: 2016-07-01Bibliographically approved
6. An inclusion optimal algorithm for chain graph structure learning: with supplement
Open this publication in new window or tab >>An inclusion optimal algorithm for chain graph structure learning: with supplement
2014 (English)In: Proceedings of the 17th International Conference on Arti-cial Intelligence and Statistics, 2014, 778-786 p.Conference paper, Published paper (Other academic)
Abstract [en]

This paper presents and proves an extension of Meek’s conjecture to chain graphs under the Lauritzen-Wermuth-Frydenberg interpretation. The proof of the conjecture leads to the development of a structure learning algorithm that finds an inclusion optimal chain graph for any given probability distribution satisfying the composition property. Finally, the new algorithm is experimentally evaluated.

Series
JMLR Workshop and Conference Proceedings, Vol. 33
Keyword
Chain Graph, Lauritzen-Wermuth-Frydenberg interpretation, Learning
National Category
Computer Systems
Identifiers
urn:nbn:se:liu:diva-105816 (URN)
Conference
17th International Conference on Artificial Intelligence and Statistics April 22-25, 2014, Reykjavik, Iceland
Available from: 2014-04-08 Created: 2014-04-08 Last updated: 2016-03-29Bibliographically approved
7. Learning Optimal Chain Graphs with Answer Set Programming
Open this publication in new window or tab >>Learning Optimal Chain Graphs with Answer Set Programming
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, Published 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
Keyword
Chain Graphs, Graph Structure Learning, Answer Set Programming
National Category
Other Mathematics
Identifiers
urn:nbn:se:liu:diva-120695 (URN)978-0-9966431-0-8 (ISBN)
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

Open Access in DiVA

fulltext(789 kB)142 downloads
File information
File name FULLTEXT01.pdfFile size 789 kBChecksum SHA-512
42d88810d6b3a6ee106c4aff0aea8950ba8af608d425166c37695d33ab96b5decc8ba00180c7b35cbc233edd73450c7a6842ef109287fef3b84ce0fa99269329
Type fulltextMimetype application/pdf
omslag(7039 kB)13 downloads
File information
File name COVER01.pdfFile size 7039 kBChecksum SHA-512
dd4483af7eb046deefe2f312c8abed1584928cbf6839c96890ea726cb5a50a93080ac5d18df90b60e6d492e019212dcf105afbd7e31301efd6ec9c7ca85c338c
Type coverMimetype application/pdf

Other links

Publisher's full text

Authority records BETA

Sonntag, Dag

Search in DiVA

By author/editor
Sonntag, Dag
By organisation
Database and information techniquesFaculty of Science & Engineering
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 142 downloads
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

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 3591 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf