Abstract
We develop a computationally efficient method to determine the interaction structure in a multidimensional binary sample. We use an interaction model based on orthogonal functions, and give a result on independence properties in this model. Using this result we develop an efficient approximation algorithm for estimating the parameters in a given undirected model. To find the best model, we use a heuristic search algorithm in which the structure is determined incrementally. We also give an algorithm for reconstructing the causal directions, if such exist. We demonstrate that together these algorithms are capable of discovering almost all of the true structure for a problem with 121 variables, including many of the directions.
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
Badsberg, J. H. (1991) A Guide to CoCo. Technical Report 91-43, Institute for Electronic Systems, University of Aalborg.
Beinlich, I., Suermondt, H., Chavez, R., and Cooper, G. (1989) The ALARM monitoring system: A case study with two probabilistic inference techniques for belief networks. Technical Report KSL-88-84, Knowledge Systems Laboratory, Stanford University.
Cooper, G. and Herskovits, E. (1991) A Bayesian Method for the Induction of Probabilistic Networks from Data. Technical Report KSL-91-02, Knowledge Systems Laboratory, Stanford University.
Darroch, J. N., Lauritzen, S. L. and Speed, T. P. (1980) Markov fields and log-linear models for contingency tables. Annals of Statistics, 8, 522–39.
Goodman, L. A. (1970) The multivariate analysis of qualitative data: Interaction among multiple classifications. Journal of the American Statistical Association, 65, 226–56.
Haberman, S. J. (1974) The Analysis of Frequency Data. The University of Chicago Press.
Herskovits, E. and Cooper, G. (1990) Kutato: An Entropy-Driven System for Construction of Probabilistic Expert Systems from Databases. Technical Report KSL-90-22, Knowledge Systems Laboratory, Stanford University.
Lauritzen, S. L. (1982) Lectures on Contingency Tables. Aalborg University Press.
Lauritzen, S. L. and Spiegelhalter, D. S. (1988) Local computations with probabilities on graphical structures and their application to expert systems. Journal of the Royal Statistical Society, Series B, 50.
Moussouris, J. (1974) Gibbs and Markov random systems with constraints. Journal of Statistical Physics, 10, 11–33.
Ott, J. and Kronmal, R. A. (1976) Some classification procedures for multivariate binary data using orthogonal functions. Journal of the American Statistical Association, 71, 391–9.
Pearl, J. (1988) Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann.
Plackett, R. L. (1974) The Analysis of Categorical Data. London: Griffin & Co.
Rissanen, J. (1983) A universal prior for integers and estimation by minimum description length. Annals of Statistics, 11, No. 2, 416–31.
Spirtes, P., Glymour, C. and Scheines, R. (1992) Causation, Prediction and Search. Book manuscript. Department of Philosophy, Carnegie Mellon University.
Wedelin, D. (1993) Efficient Algorithms for Probabilistic Inference, Combinatorial Optimization and the Discovery of Causal Structure from Data, Ph.D. Thesis, Department of Computer Science, Chalmers University of Technology.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Wedelin, D. Efficient estimation and model selection in large graphical models. Stat Comput 6, 313–323 (1996). https://doi.org/10.1007/BF00143552
Issue Date:
DOI: https://doi.org/10.1007/BF00143552