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
Approximate Counting of Graphical Models Via MCMC Revisited
Linköping University, Department of Computer and Information Science, Database and information techniques. Linköping University, The Institute of Technology.
Linköping University, Department of Computer and Information Science, Database and information techniques. Linköping University, The Institute of Technology.
Dept. Computer Science and Artificial Intelligence, University of Granada, Spain.
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. Vol. 30, no 3, 384-420 p.
Keyword [en]
MCMC sampling, Bayesian networks, Chain graphs, Lauritzen-Wermuth-Frydenberg interpretation, Multivariate regression interpretation
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:liu:diva-105815DOI: 10.1002/int.21704ISI: 000348308600008OAI: oai:DiVA.org:liu-105815DiVA: diva2:710829
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
In thesis
1. A Study of Chain Graph Interpretations
Open this publication in new window or tab >>A Study of Chain Graph Interpretations
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:nbn:se:liu:diva-105024 (URN)10.3384/lic.diva-105024 (DOI)978-91-7519-377-9 (ISBN)
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
2. 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 (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

fulltext(537 kB)35 downloads
File information
File name FULLTEXT01.pdfFile size 537 kBChecksum SHA-512
fd53b63acee9de38bdd8e64c7b6f353fe21803df83f97ff49e3a991bb167a949c5906897a1f23d173325c838abe0cb283257a9e5ab51d62c6cec2dd96e980f91
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Authority records BETA

Sonntag, DagPeña, Jose M.

Search in DiVA

By author/editor
Sonntag, DagPeña, Jose M.
By organisation
Database and information techniquesThe Institute of Technology
In the same journal
International Journal of Intelligent Systems
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 35 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
urn-nbn

Altmetric score

doi
urn-nbn
Total: 146 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