An Order-Independent Algorithm for Learning Chain Graphs

Authors

  • Mohammad Ali Javidian Purdue University
  • Marco Valtorta
  • Pooyan Jamshidi

DOI:

https://doi.org/10.32473/flairs.v34i1.128365

Keywords:

Probabilistic graphical models, Learning algorithms, Chain graphs, Bayesian networks

Abstract

LWF chain graphs combine directed acyclic graphs and undirected graphs. We propose a PC-like algorithm, called PC4LWF, that finds the structure of chain graphs under the faithfulness assumption to resolve the problem of scalability of the proposed algorithm by Studeny (1997). We prove that PC4LWF is order dependent, in the sense that the output can depend on the order in which the variables are given. This order dependence can be very pronounced in high-dimensional settings. We propose two modifications of the PC4LWF algorithm that remove part or all of this order dependence. Simulation results with different sample sizes, network sizes, and p-values demonstrate the competitive performance of the PC4LWF algorithms in comparison with the LCD algorithm proposed by Ma et al. (2008) in low-dimensional settings and improved performance (with regard to error measures) in high-dimensional settings.

Downloads

Published

2021-04-18

How to Cite

Javidian, M. A., Valtorta, M., & Jamshidi, P. (2021). An Order-Independent Algorithm for Learning Chain Graphs. The International FLAIRS Conference Proceedings, 34. https://doi.org/10.32473/flairs.v34i1.128365

Issue

Section

Special Track: Uncertain Reasoning