On the Distance Hypothesis in Tree-like Bayesian Networks

• Autorzy: Kłopotek M.

Warianty tytułu

PL

O hipotezie odległości w drzewiastych sieciach bayesowskich

• Języki publikacji: EN

Abstrakty

EN

Bayesian networks have many practical applications due to their capability to represent joint probability distribution in many variables in a compact way. Though there exist many algorithms for learning Bayesian networks from data, they are not satisfactory because the learned networks usually are not suitable for reasoning. So far only for tree-like and poly-tree Bayesian networks and also for so-called Structured Bayesian networks a satisfactory reasoning algorithms applicable directly for Bayesian networks have been invented. This radically increases the need for efficient learning algorithms for these classes of Bayesian networks. In fact, algorithms learning tree-like Bayesian networks have been created allowing for learning in case of large numbers of variables. The fastest algorithm, however, relies on the assumption of special node similarity measure properties. This paper defines and explores a definition of such a similarity measure. It is also demonstrated that this measure facilitates development of algorithms for learning Structured Bayesian Networks from data.

PL

Sieci bayesowskie mają wiele praktycznych zastosowań związanych z ich zdolnością do zwartej reprezentacji rozkładów prawdopodobieństwa w wielu zmiennych. Choć znanych jest wiele algorytmów uczących sieci bayesowskie z danych, nie są one satysfakcjonujące, ponieważ wynikowe struktury sieci na ogół nie nadają się do celów wnioskowania eksperckiego, z wyjątkiem sieci drzewiastych, polidrzewiastych oraz strukturalnych. Szybkie metody uczenia dla sieci drzewiastych opierają się na postulacie specjalnej postaci funkcji podobieństaw między zmiennymi. Niniejszy artykół pokazuje, że w istocie istnieje postulowana miara podobieństwa. Demonstruje również implikacje wynikające dla uczenia sieci strukturalnych z danych.

Słowa kluczowe

EN

Bayesian networks; tree-like networks; structured networks; fast learning; variable similarity

PL

sieci bayesowskie; sieci drzewiaste; strukturalizacja; szybkie uczenie; podobieństwo zmiennych

• Wydawca: Instytut Podstaw Informatyki PAN
• Czasopismo: Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk
• Rocznik: 2003
• Tom: Nr 952
• Strony: 1--14
• Opis fizyczny: Bibliogr. 41 poz., rys.

Twórcy

autor

Kłopotek M.

• Instytut Podstaw Informatyki Polskiej Akademii Nauk, 01-237 Warszawa, ul. Ordona 21,

Bibliografia

• [Cercoue et al., 1997] Cercone N.. Wong S.K.M., Xiang Y.: A 'microscopic' study of minimum entropy search in learning decomposable Markov networks. Machine Learning, 1997, vol. 26, nr 1..65-92
• [Cerquides 1999] J. Cerquides: “Applying General Bayesian Techniques to Improve (TAN) Induction”, in "Knowledge Discovery and Data Mining", pp 292-296, 1999, http://citeseer.ni.nec.com/cerquides99applving.html
• [Cheng et al., 1997] Cheng J., Bell D.A. and Liu W.: Learning belief networks from data: an information theory based approach. Proceedings of die Sixth ACM Int. Conf. on Information and Knowledge Management, 1997.
• [Cheng et al., 1997b] J. Cheng, D.A. Bell and W. Liu An algorithm for Bayesian belief network construction from data, Proceedings of Al & STAT'97, Ft. Lauderdale, Florida, 1997.
• [Cheng, Greiner] J. Cheng, R. Geiner: Learning Bayesian belief network classifiers: algorithms and system Canadian Imperial Bank of Commerce.
• [Chickering], D.M.Chickering: A transformational characterization of equivalent Bayesian network structures . Computer Science Department,University of California at Los Angeles.
• (Chow, Liu, 1968] C.K.Chow, C.N.Liu: Approximating discrete probability distributions with dependence trees, IEEF. Transactions on Information Theory, Vol. IT-14, No.3, (1968), 462-467
• [Cooper, 1990] Cooper G. The computational complexity of probabilistic inference using Bayesian belief networks Artif. Intell. 42,1990, 395-405.
• [Chou, Wagner, 1973] C.K.Chou, T.J.Wagner: Consistency of an estimate of tree-dependent probability distribution, IEEE Transactions on Information Theory, IT-19, (1973), 369- 371
• [Friedman et al] N.Friedman, I. Nachman. D. Peer: Learning Bayesian network structure from massive dataseys: The “sparse candidate" algorithm. Institute of Computer Science. Hebrew University Jerusalem.
• [Friedman et al. 1997] N. Friedman, D. Geiger, M. Goldszmidt Bayesian Network Classifiers (1997). Machine Learning vol. 29, pp. 131 http://citeseer.nj.nec.com/friedman97bayesian.html
• [Geiger et al., 1990] Geiger D., Verma T., Pearl J.: D- Separation: From theorems to algorithms. M.Henrion, et.al eds.. Uncertainty in Artificial Intelligence 5, Elsevier 139- 148
• [Huang et al.] K.Huang, I. King, M.R.Lyu: Constructing a large node Chow/Liu tree based on frequent itemsets. Dept, of Computer Science and Engineering. The Chinese University of Hong Kong.
• [Hwang et al.] K.B. Hwang, J.W.Lee, S.W. Chung, B.T. Zhang: Construction of large-scale Bayesian networks by local to global search. School of Computer Science and Engineering. Seoul National University, Korea.
• [Inza et al] Inza, M. Merino, P. Larranaga, J. Quiroga, B. Sierra, M. Girala, Feature Subset Selection by Genetic Algorithms and Estimation of Distribution Algorithms. A Case Study in the Survival of Cirrhotic Patients Treated with TIPS. Artificial Intelligence in Medicine (in press) http://citesecr.ni.nec.com/345995.html
• [Jensen, 1996] Jensen J., An Introduction to Raxesian Networks. Springer Verlag, 1996
• [Klopotek, 1999] Klopotek M.A.: Partial Dependency Separation - a new concept for expressing dependence/ independence relations in causal networks. Demonstratio Mathematica. Vol XXXII No 1.1999. pp. 207-226.
• [Klopotek. 2000] Klopotek M.A.: On a Deficiency of the FCI Algorithm Learning Bayesian Networks from Data. Demonstratio Mathenmtica. Vol. XXXIII, 2000. No. 1. pp. 181-194.
• [Klopotek. 2000b] Klopotek M.A.: Fast Restricted Causal Inference. Demonstratio Mathematica, Vol.XXXlIl, No.2, 2000. pp. 419-442
• [Klopotek, Wierzchon 2000] Klopotek M.A., Wierzchon S.T.: Partial D-Separation for Discovery of Bayesian Networks from Data. R. Trappl, ed:Cybernetics and Systems. Proc. EMCSR'2000, 25-28.4.2000, Vienna, Austrian Society for Cybernetics, Vol. 2, pp. 707-712.
• [Klopotek, 2001] Klopotek M.A.: Inteligentne wyszukiwarki internetowe. Akademicka Oficyna Wydawnicza Exit, Warszawa 2001, ISBN 83-87674-31-1. chapter 8.9.
• [Klopotek et al.. 2001] Kłopotek M.A., Wierzchoń ST.. Michalewicz M., Bednarczyk M., Pawłowski W., Wsowski A.: Bayesian network mining system. M A. Kłopotek, M. Michalewicz, S.T. Wierzchoń. eds. Intelligent Information Systems 2001. Physica/Springer Verlag. 2001, 180-193
• (Klopotek. 2002] Klopotek M.A., Well-Structured Program Graphs and the issue of local computations. Proc. Intelligent Inf. Systems Conf., Sopot. 3-6 June 2002. In: M.A.Kłopotek, S.T.Wierzchoń, M.Michalewicz(eds): Intellivent Information Systems 2002. Advances in Soft Computing. Physica/Springer Verlag, Heidelberg New York 2002. ISBN-3-7908-1509-8, pp. 365-36S
• [Klopotek, 2002b] M.A.Kłopotek: Structure and Reasoning in Bayesian Networks . ICS PAS Reports Nr 941 Warszawa, February 2002
• [Klopotek, 2002c] M.A.Kłopotek: Reasoning in Structured Bayesian Networks TO APPPEAR IN Rutkowski, L.. Kacprzyk, J, (Eds.) "Neural Networks and Soft Computing" Proceedings of the Sixth International Conference on Neural Network and Soft Computing, Zakopane, Poland, June 11-15, 2002, Springer-Verlag 2003. ISBN 3-7908-0005-8.
• [Klopotek. 2002d] M.A.Kłopotek: A New Space-Saving Bayesian Tice Construction Method for High Dimensional Data Denwnstratio Mathematica, Vol. 35, No. 3 (2002)pp. 671-684
• [Klopotek, 2002e] M.A.K'opotek: Space Saving Approach to Fitting Tree Distributions to High-Dimensional Sparse Data, in: M.A.Kłopotek, J.Tchórzewski eds: Sztuczna inteligencja. Materiały V Konferencji Naukowej. Wydawnictwo Akademii Podlaskiej. Siedlce 2002 ISBN 83-7051-190-2, pp.13-18
• [Klopotek, 20020 M.A.Kłopotek: A New Bayesian Tree Learning Method with Reduced Time and Space Complexity. Fundamenta Informaticae, 49lno 412002. IOS Press, pp. 349-367.
• [Klopotek, 2002g] M.A.Kłopotek: Minig Bayesian Networks Structure for Large Sets of Variables, in M.S.Hacid, Z.W.Ras, D.A. Zighed, Y. Kodratoff (eds): Foundations of Intelligent Systems Lecture Notes in Artificial Intelligence 2366, Springer-Verlag, pp. 114-122
• [Koller, Pfeffer, 1997] Koller D.. Pfeffer A.: Object-Oriented Bayesian Networks. Proc. of the 13th Conf. on Uncertainty in Artificial Intelligence (UA1-97), 1997,302-313
• [Laurizen, 1988] Lauritzen, S.L., and Spiegelhalter, D.J. Local computations with probabilities on graphical structures and their application to expert systems. J. R. Statist. Soc. B- 50(1988)157-224
• [Meila, 2000] M. Meila: An accelerated Chow and Liu algorithm: fitting tree distributions to high-dimensional sparse data, http://citeseer.ni.nec.coin/363584.html
• [Meila, Jordan, 2000] M. Meila, M. Jordan: Learning with mixtures of trees. Journal of Machine Learning Research, Volume 1 (2000) http://citesecr.ni.nec.com/mcila001eaming.html, http://www.ai.mit.edu/projects/jmlr/papers/volumel/meilaO 0a/htm!/nieila00a.html
• [Pearl, 1988] Pearl J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Mateo CA, 1988 [Shachter, 1990] Shachter B.D.: Evidence absorption and propagation through evidence reversals. In M. Henrion. B.D. Shachter, L.N. Kanal, J.F. Lemmer (eds): Uncertainty in Artificial Intelligence 5, Elsevier Science Publishers B.V (1990), 173- 190
• [Shafer, 1996] Shafer, G.: Probabilistic Expert Systems, SIAM CBMS-NSF Regional Conference Series in Applied Mathematics, Philadelphia, 1996, vol. 67
• [Spirtes et al., 1993] Spirtes P., Glymour C., Scheines R : Causation, Prediction and Search, Lecture Notes in Statistics 81, Springer-Verlag, 1993.
• [Suzuki, 1993] J. Suzuki, "Learning Bayesian Belief Networks based on the Minimum Descripion length Principle: Basic Properties", IEICE Trans, on Foundamentals, Vol. E82-A, Oct. 1999, and the conference paper in UA1-93. http://www.math.sei.osaka- u. ac.jp/~suzuki/net.html
• [Valiveti, Oommen, 1989] R.S. Valiveti, B.J. Oommen: The use of chi-squared statistics in determining dependence tree, Technical Report SCS-TR-153, School of Computer Science,Carleton University, Ottawa, Ontario, March (1989).
• [Valiveti, Oommen, 1992] R.S.Valiveti, B.J.Oommen: On using the chi-squared statistics for determining statistic dependence, t Pattern Recognition Vol. 25 No. 11 (1992), 1389-1400.
• [Wierzchon, 1996] Wierzchon S.T.: Methods of Representation and rocessing of Uncertauin Information in the Dempster-shafer Theory (in Polish), Publisher: Institute of Computer Science, Polish Academy of Sciences, Warsaw, Poland, 1996,
• [Wierzchon, Klopotek, 2002] Wierzchon S.T., Klopotek M.A : Evidential Reasoning. An Interpretative Investigation. Wvdawnictwo Akademii Podlaskiej. Siedlce, 2002 PL ISSN 0860-2719, 304 pages.