Abstract
We introduce a novel class of labeled directed acyclic graph (LDAG) models for finite sets of discrete variables. LDAGs generalize earlier proposals for allowing local structures in the conditional probability distribution of a node, such that unrestricted label sets determine which edges can be deleted from the underlying directed acyclic graph (DAG) for a given context. Several properties of these models are derived, including a generalization of the concept of Markov equivalence classes. Efficient Bayesian learning of LDAGs is enabled by introducing an LDAG-based factorization of the Dirichlet prior for the model parameters, such that the marginal likelihood can be calculated analytically. In addition, we develop a novel prior distribution for the model structures that can appropriately penalize a model for its labeling complexity. A non-reversible Markov chain Monte Carlo algorithm combined with a greedy hill climbing approach is used for illustrating the useful properties of LDAG models for both real and synthetic data sets.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Andersson S, Madigan D, Perlman M (1997) A characterization of Markov equivalence classes for acyclic digraphs. Ann Stat 25:505–541
Boutilier C, Friedman N, Goldszmidt M, Koller D (1996) Context-specific independence in Bayesian networks. In: Proceedings of the twelfth annual conference on uncertainty in artificial intelligence, Morgan Kaufmann, San Francisco, pp 115–123
Buntine W (1991) Theory refinement on Bayesian networks. In: Proceedings of the seventh conference on uncertainty in artificial intelligence, Morgan Kaufmann, San Francisco, pp 52–60
Chickering DM, Heckerman D, Meek C (1997) A Bayesian approach to learning Bayesian networks with local structure. In: Proceedings of thirteenth conference on uncertainty in artificial intelligence, Morgan Kaufmann, San Francisco
Cooper G, Herskovitz E (1992) A Bayesian method for the induction of probabilistic networks from data. Mach Learn 9:309–347
Corander J (2003) Labelled graphical models. Scand J Stat 30:493–508
Corander J, Gyllenberg M, Koski T (2006) Bayesian model learning based on a parallel MCMC strategy. Stat Comput 16:355–362
Corander J, Ekdahl M, Koski T (2008) Parallel interacting MCMC for learning of topologies of graphical models. Data Min Knowl Discov 17:431–456
Eriksen PS (1999) Context specific interaction models. AAlborg University, Tech. rep.
Friedman N, Goldszmidt M (1996) Learning Bayesian networks with local structure. In: Proceedings of the twelfth annual conference on uncertainty in artificial intelligence, Morgan Kaufmann, San Francisco, pp 252–262
Geiger D, Heckerman D (1996) Knowledge representation and inference in similarity networks and Bayesian multinets. Artif Intell 82:45–74
Heckerman D (1991) Probabilistic similarity networks. MIT Press, Cambridge
Heckerman D, Geiger D, Chickering D (1995) Learning Bayesian networks: the combination of knowledge and statistical data. Mach Learn 20:197–243
Højsgaard S (2003) Split models for contingency tables. Comput Stat Data Anal 42:621–645
Højsgaard S (2004) Statistical inference in context specific interaction models for contingency tables. Scand J Stat 31:143–158
Koller D, Friedman N (2009) Probabilistic graphical models: principles and techniques. MIT Press, Cambridge
Koski T, Noble J (2009) Bayesian networks. An introduction. Wiley, Chippenham, Wiltshire
Marttinen P, Corander J (2009) Bayesian learning of graphical vector autoregressions with unequal lag-lengths. Mach Learn 75:217–243
Pagallo G, Haussler D (1990) Boolean feature discovery in empirical learning. Mach Learn 5:71–99
Pearl J (1988) Probabilistic reasoning in intelligent systems. Morgan Kaufmann, San Francisco
Poole D (1997) Probabilistic partial evaluation: Exploiting rule structure in probabilistic inference. In: Proceedings of the 15th international joint conference on artificial intelligence, pp 1284–1291
Poole D, Zhang N (2003) Exploiting contextual independence in probabilistic inference. J Artif Intell Res 18:263–313
Robinson R (1977) Counting unlabelled acyclic digraphs. Springer Lect Notes Math 622:28–43
Silander T, Kontkanen P, Myllymäki P (2007) On sensitivity of the MAP Bayesian network structure to the equivalent sample size parameter. In: Proceedings of the 23rd conference on uncertainty in artificial intelligence, AUAI Press, Corvallis, pp 360–367
Whittaker J (1990) Graphical models in applied multivariate statistics. Wiley, New York
Zhang N, Poole D (1999) On the role of context-specific independence in probabilistic inference. In: Proceedings of the 16th international joint conference on artificial intelligence, pp 1288–1293
Acknowledgments
JP and HN were supported by the Foundation of Åbo Akademi University, as part of the grant for the Center of Excellence in Optimization and Systems Engineering. JC was supported by ERC grant 239784 and AoF grant 251170. The authors would like thank the AE and the three anonymous reviewers for their comments and suggestions that led to a significant improvement of the original manuscript. We would also like to thank Jarno Lintusaari for his comments during the revision phase.
Author information
Authors and Affiliations
Corresponding author
Additional information
Responsible editor: Kristian Kersting.
Rights and permissions
About this article
Cite this article
Pensar, J., Nyman, H., Koski, T. et al. Labeled directed acyclic graphs: a generalization of context-specific independence in directed graphical models. Data Min Knowl Disc 29, 503–533 (2015). https://doi.org/10.1007/s10618-014-0355-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10618-014-0355-0