Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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
Counting Markov equivalence classes by number of immoralities
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
2017 (English)In: Uncertainty in Artificial Intelligence - Proceedings of the 33rd Conference, UAI 2017, AUAI Press Corvallis , 2017Conference paper (Refereed)
Abstract [en]

Two directed acyclic graphs (DAGs) are called Markov equivalent if and only if they have the same underlying undirected graph (i.e. skeleton) and the same set of immoralities. When using observational data alone and typical identifiability assumptions, such as faithfulness, a DAG model can only be determined up to Markov equivalence. Therefore, it is desirable to understand the size and number of Markov equivalence classes (MECs) combinatorially. In this paper, we address this enumerative question using a pair of generating functions that encode the number and size of MECs on a skeleton G, and in doing so we connect this problem to classical problems in combinatorial optimization. The first generating function is a graph polynomial that counts the number of MECs on G by their number of immoralities. Using connections to the independent set problem, we show that computing a DAG on G with the maximum possible number of immoralities is NP-hard. The second generating function counts the MECs on G according to their size. Via computer enumeration, we show that this generating function is distinct for every connected graph on p nodes for all p < 10.

Place, publisher, year, edition, pages
AUAI Press Corvallis , 2017.
National Category
Probability Theory and Statistics
Identifiers
URN: urn:nbn:se:kth:diva-218574Scopus ID: 2-s2.0-85031099729OAI: oai:DiVA.org:kth-218574DiVA, id: diva2:1161422
Conference
33rd Conference on Uncertainty in Artificial Intelligence, UAI 2017, Sydney, Australia, 11 August 2017 through 15 August 2017
Note

QC 20171130

Available from: 2017-11-30 Created: 2017-11-30 Last updated: 2017-11-30Bibliographically approved

Open Access in DiVA

No full text in DiVA

Scopus

Authority records BETA

Solus, Liam

Search in DiVA

By author/editor
Solus, Liam
By organisation
Mathematics (Dept.)
Probability Theory and Statistics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 2 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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