Analysis of Markov Boundary Induction in Bayesian Networks: A New View From Matroid Theory

• Autorzy: Feng D. , Chen F. , Xu W.
• Języki publikacji: EN

Abstrakty

EN

Learning Markov boundaries from data without having to learn a Bayesian network first can be viewed as a feature subset selection problem and has received much attention due to its significance in the wide applications of AI techniques. Popular constraint based methods suffer from high computational complexity and are usually unstable in spaces of high dimensionality. We propose a new perspective from matroid theory towards the discovery of Markov boundaries of random variable in the domain, and develop a learning algorithm which guarantees to recover the true Markov boundaries by a greedy learning algorithm. Then we use the precision matrix of the original distribution as a measure of independence to make our algorithm feasible in large scale problems, which is essentially an approximation of the probabilistic relations with Gaussians and can find possible variables in Markov boundaries with low computational complexity. Experimental results on standard Bayesian networks show that our analysis and approximation can efficiently and accurately identify Markov boundaries in complex networks from data.

Słowa kluczowe

EN

Markov boundary; conditional independence; matroid

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 107, nr 4
• Strony: 415--434
• Opis fizyczny: Bibliogr. 28 poz., tab., wykr.

Twórcy

autor

Feng D.

autor

Chen F.

autor

Xu W.

• National Laboratory for Information Science and Technology Tsinghua University Beijing, 100084, China,

Bibliografia

• [1] Cheng, J., Greiner, R., Kelly, J., Bell, D., Liu,W. R.: Learning Bayesian networks from data: An informationtheory based approach, Artificial Intelligence, 137(1-2), 2002, 43-90.
• [2] Chickering, D., Geiger, D., Heckerman, D.: Learning Bayesian networks: Search methods and experimental results, Preliminary papers of the fifth international workshop on Artificial Intelligence and Statistics, Fort Lauderdale, Florida: Society for Artificial Intelligence in Statistics, 1995.
• [3] Chickering, D. M.: Learning equivalence classes of Bayesian-network structures, Journal of Machine Learning Research, 2(3), 2002, 445-498.
• [4] Chickering, D. M., Heckerman, D., Meek, C.: Large-sample learning of Bayesian networks is NP-hard, Journal of Machine Learning Research, 5, 2004, 1287-1330.
• [5] Cooper, G. F., Herskovits, E.: A Bayesian method for the induction of probabilistic networks from data, Machine Learning, 9(4), 1992, 309-347.
• [6] Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to algorithms, MIT press Cambridge, MA, 2001.
• [7] Cowell, R. G., Dawid, A. P., Lauritzen, S. L., Spiegelhalter, D. J.: Probabilistic networks and expert systems, Springer Verlag, 1999.
• [8] Dash, D., Druzdzel, M.: A Robust Independence Test for Constraint-Based Learning of Causal Structure, Proceedings of the 19th Annual Conference on Uncertainty in Artificial Intelligence (UAI-03), Morgan Kaufmann, San Francisco, CA, 2003.
• [9] Deng, H., Clausi, D.: Gaussian MRF rotation-invariant features for image classification, Pattern Analysis and Machine Intelligence, IEEE Transactions on, 26(7), july 2004, 951 -955.
• [10] Drton, M., Sturmfels, B., Sullivant, S.: Lectures on algebraic statistics, Birkhauser, 2008.
• [11] Frey, B., Jojic, N.: A comparison of algorithms for inference and learning in probabilistic graphical models, Pattern Analysis and Machine Intelligence, IEEE Transactions on, 27(9), sept. 2005, 1392 -1416.
• [12] Heckerman, D., Chickering, D. M., Meek, C., Rounthwaite, R., Kadie, C.: Dependency networks for inference, collaborative filtering, and data visualization, Journal of Machine Learning Research, 1(1), 2000, 49-75.
• [13] Koller, D., Friedman, N.: Probabilistic Graphical Models: Principles and Techniques, MIT Press, 2009.
• [14] Krogh, A., Larsson, B., von Heijne, G., Sonnhammer, E.: Predicting transmembrane protein topology with a hidden Markov model- Application to complete genomes, JOURNAL OF MOLECULAR BIOLOGY, 305(3), JAN 19 2001, 567-580.
• [15] Margaritis, D., Thrun, S.: Bayesian network induction via local neighborhoods, Advances in Neural Information Processing Systems 12, 12, 2000, 505-511.
• [16] Matus, F.: Probabilistic Conditional Independence Structures And Matroid Theory: Background, International Journal of General Systems, 22(2), 1994, 185-196.
• [17] McEliece, R., MacKay, D., Cheng, J.-F.: Turbo decoding as an instance of Pearl's ldquo;belief propagation rdquo; algorithm, Selected Areas in Communications, IEEE Journal on, 16(2), feb 1998, 140 -152.
• [18] de Morais, S. R., Aussem, A.: A novel Markov boundary based feature subset selection algorithm, Neurocomputing, 73(4-6), 2010, 578 - 584.
• [19] Pearl, J.: Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1988.
• [20] Pena, J. M., Nilsson, R., Bjorkegren, J., Tegner, J.: Towards scalable and data efficient learning of Markov boundaries, International Journal of Approximate Reasoning, 45(2), JUL 2006, 211-232, 8th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, Barcelona, SPAIN, JUL 06-08, 2005.
• [21] Spirtes, P., Glymour, C.: An algorithm for fast recovery of sparse causal graphs, Technical Report 1, 1991.
• [22] Spirtes, P., Glymour, C., Scheines, R.: Causation, prediction, and search, The MIT Press, 2001.
• [23] Studeny, M.: Probabilistic conditional independence structures, 2005.
• [24] Tsumoto, S., Hirano, S.: Statistical Independence and Determinants in a Contingency Table Interpretation of Pearson Residuals based on Linear Algebra, FUNDAMENTA INFORMATICAE, 90(3), 2009, 251-267.
• [25] Verma, T., Pearl, J.: An algorithm for deciding if a set of observed independencies has a causal explanation, Proc. of the Eighth Conference on Uncertainty in Artificial Intelligence, 1992.
• [26] Wainwright, M. J., Jordan, M. I.: Graphical Models, Exponential Families, and Variational Inference, Now Publishers, 2008.
• [27] Welsh, D. J. A.: Matroid theory, Academic Press., 1976.
• [28] Whitney, H.: On the abstract properties of linear dependence, American Journal of Mathematics, 57, 1935, 509-533.