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
A Study of Chain Graph Interpretations
Linköping University, Department of Computer and Information Science, Database and information techniques. Linköping University, The Institute of Technology. (ADIT)
2014 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

Probabilistic graphical models are today one of the most well used architectures for modelling and reasoning about knowledge with uncertainty. The most widely used subclass of these models is Bayesian networks that has found a wide range of applications both in industry and research. Bayesian networks do however have a major limitation which is that only asymmetric relationships, namely cause and eect relationships, can be modelled between its variables. A class of probabilistic graphical models that has tried to solve this shortcoming is chain graphs. It is achieved by including two types of edges in the models, representing both symmetric and asymmetric relationships between the connected variables. This allows for a wider range of independence models to be modelled. Depending on how the second edge is interpreted this has also given rise to dierent chain graph interpretations.

Although chain graphs were first presented in the late eighties the field has been relatively dormant and most research has been focused on Bayesian networks. This was until recently when chain graphs got renewed interest. The research on chain graphs has thereafter extended many of the ideas from Bayesian networks and in this thesis we study what this new surge of research has been focused on and what results have been achieved. Moreover we do also discuss what areas that we think are most important to focus on in further research.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2014. , 161 p.
Series
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1647
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:liu:diva-105024DOI: 10.3384/lic.diva-105024ISBN: 978-91-7519-377-9 (print)OAI: oai:DiVA.org:liu-105024DiVA: diva2:706317
Presentation
2014-04-29, Alan Turing, Hus E, Campus Valla, Linköping University, Linköping, 13:15 (English)
Opponent
Supervisors
Funder
Swedish Research Council, 2010-4808
Available from: 2014-04-08 Created: 2014-03-06 Last updated: 2014-04-08Bibliographically 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. Chain Graph Interpretations and Their Relations, Extended Version
Open this publication in new window or tab >>Chain Graph Interpretations and Their Relations, Extended Version
2013 (English)In: Proceedings of the 12th European Conference, ECSQARU 2013, Utrecht, The Netherlands, July 8-10, 2013 / [ed] Linda C. van der Gaag, Springer Berlin/Heidelberg, 2013, 510-521 p.Conference paper, Published paper (Refereed)
Abstract [en]

This paper deals with different chain graph interpretations and the relations between them in terms of representable independence models. Specifically, we study the Lauritzen-Wermuth-Frydenberg, Andersson-Madigan-Perlman and multivariate regression interpretations and present the necessary and sufficient conditions for when a chain graph of one interpretation can be perfectly translated into a chain graph of another interpretation. Moreover, we also present a feasible split for the Andersson-Madigan-Perlman interpretation with similar features as the feasible splits presented for the other two interpretations.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2013
Series
Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online) ; Vol. 7958
Keyword
Chain Graphs, Lauritzen-Wermuth-Frydenberg interpretation, Andersson-Madigan-Perlman interpretation, multivariate regression interpretation
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-105814 (URN)10.1007/978-3-642-39091-3_43 (DOI)978-3-642-39090-6 (ISBN)978-3-642-39091-3 (ISBN)
Conference
The 12th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty July 7th -10th, Utrecht, The Netherlands
Note

Awarded best student paper award at ECSQARU 2013.

Available from: 2014-04-08 Created: 2014-04-08 Last updated: 2015-05-28Bibliographically approved
3. 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
4. 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
5. 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

Open Access in DiVA

A Study of Chain Graph Interpretations(1567 kB)504 downloads
File information
File name FULLTEXT02.pdfFile size 1567 kBChecksum SHA-512
8d188840cc821c81628741271a973c0743a9efef418d043c3842e875cc3566b3603f54b25dfc278bb7b5e81cf88160e132a9ae5810fa22c8509a6385d176a650
Type fulltextMimetype application/pdf
omslag(132 kB)21 downloads
File information
File name COVER01.pdfFile size 132 kBChecksum SHA-512
053c8a98e3c9178d219a369144ca622d3024621e19d31fb5bf31335ed7204d3d7d2bd6344ec27d374b2e63cd1c549149056907a4b4cd02ca7af5a85f8ba97462
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 techniquesThe Institute of Technology
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 504 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: 379 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