More Web Proxy on the site http://driver.im/

Article

Free access

Learning bayesian network structure from massive datasets: the «sparse candidate« algorithm

Authors:

Iftach Nachman,

Dana PeérAuthors Info & Claims

UAI'99: Proceedings of the Fifteenth conference on Uncertainty in artificial intelligence

Pages 206 - 215

Published: 30 July 1999 Publication History

PDF eReader Publisher Site

Abstract

Learning Bayesian networks is often cast as an optimization problem, where the computational task is to find a structure that maximizes a statistically motivated score. By and large, existing learning tools address this optimization problem using standard heuristic search techniques. Since the search space is extremely large, such search procedures can spend most of the time examining candidates that are extremely unreasonable. This problem becomes critical when we deal with data sets that are large either in the number of instances, or the number of attributes.

In this paper. we introduce an algorithm that achieves faster learning by restricting the search space. This iterative algorithm restricts the parents of each variable to belong to a small subset of candidates. We then search for a network that satisfies these constraints. The learned network is then used for selecting better candidates for the next iteration. We evaluate this algorithm both on synthetic and real-life data. Our results show that it is significantly faster than alternative search procedures without loss of quality in the learned structures

References

[1]

I. Beinlich, G. Suermondt, R. Chavez, and G. Cooper. Thc ALARM monitoring system. In Proc. 2'nd Euro. Conf. on AI and Med., 1989.

[2]

H. Bodlaender A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Computing, 25(6): 1305-1317, 1996.

Digital Library

[3]

R. Bouckaert, Bayesian Belief Networks: From Construction to Inference. PhD thesis. Utrecht University, The Netherlands. 1995.

[4]

X. Boyen. N. Friedman, and D. Koller. Discovering the structure of complex dynamic systems. In UAI '99. 1999.

Digital Library

[5]

D. M. Chickering. A transformational characterization of equivalent Bayesian network structurcs. In UAI'99. pp. 87-98. 1995.

Digital Library

[6]

D. M. Chickering. Learning Bayesian networks is NP-complete. In AI&STAT V. 1996.

[7]

D. M. Chickering. Learning equivalence classes of Bayesian network structure. In UAI'96, pp. 150-157, 1996.

Digital Library

[8]

C. K. Chow and C. N. Liu. Approximating discrete probability distributions with dependence trees. IEEE Trans. on Info. Theory. 14:462-467, 1968.

Digital Library

[9]

G. F. Cooper and E. Harskovits. A Bayesian method for the induction of probabilistic networks from data. Machine learning, 9:309-347, 1992.

[10]

T. H. Cormen, C.E. Leiserson, and R. L. Rivest. Introduction to Algorithms. 1990.

Digital Library

[11]

T. M. Cover and J. A. Thomas. Elements of Information theory. 1991.

Digital Library

[12]

K. J. Ezawa and T. Schucrmann. Fraud/uncollectable debt detection using a Bayesian network based learning system. In UAI'95, pp. 157-166. 1995.

Digital Library

[13]

N. Friedman, I. Nachman, and D. Peér On using bayesian networks to analyze whole-genome expression data. TR CS99-6 Hebrew University, 1999. In progress. See www.cs.huji.ac.il/abs/pmai2.

[14]

L. Getoor, N. Friedman. D. Kaller, and A. Pfeffer. Leaming probabilistic relational models, In IJCAI'99, 1999.

Digital Library

[15]

D. Heckerman. A tutorial on learning with Bayesian networks. In M. I. Jordan, editor. Learning in Grophical Models. 1998,

Digital Library

[16]

D. Heckerman, D. Geiger, and D. M. Chickering. Learning Bayesian networks: The combination of knowledge and statistical data. Machine Learning. 20: 197-243, 1995.

[17]

F. V. Jensen. An introduction to Bayesian Networks, 1996.

Digital Library

[18]

T. Jochims, A probabilistic analysis of the rocchio algorithm with tfidf for text categorization. In ICML, 1997.

Digital Library

[19]

W. Lam and F. Bacchus, Learning Bayesian belief networks: An approach based on the MDL principle. Comp. Int., 10:269-293, 1994.

[20]

A. W. Moore and M. S. Lee. Cached sufficient statistics for efficient machine learning with large datasets. J. AI. Res., 8:67-91, 1997.

Digital Library

[21]

J. Pearl and T. S. Verma. A theory of inferred causation. In KR '91, pp. 441- 452, 1991.

[22]

M. Sahami. Learning limited dependence bayesian classifiers. pp. 335-338, 1996.

[23]

P. T. Spellman, G. Sherlock, M. Q. Zhang, V. R. Iyer, K. Anders. M. B. Eisen, P. O. Brown. D. Botstein, and B. Futcher. Comprehensive identification of cell cycle-regulated genes of the yeast sacccharomyces cerevisiae by microarray hybridization. Mol. Biol. Cell. 9:3273-3297, 1998.

[24]

P. Spirtes. C. Glymour, and R. Scheines. Causation, prediction, and search. 1993.

Cited By

Orr LBalazinska MSuciu DMaier DPottinger RDoan ATan WAlawini ANgo H(2020)Sample Debiasing in the Themis Open World Database SystemProceedings of the 2020 ACM SIGMOD International Conference on Management of Data10.1145/3318464.3380606(257-268)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3318464.3380606
Barik AHonorio JWallach HLarochelle HBeygelzimer Ad'Alché-Buc FFox E(2019)Learning Bayesian networks with low rank conditional probability tablesProceedings of the 33rd International Conference on Neural Information Processing Systems10.5555/3454287.3455091(8964-8973)Online publication date: 8-Dec-2019
https://dl.acm.org/doi/10.5555/3454287.3455091
Xu SJia BLiang F(2019)Learning moral graphs in construction of high-dimensional bayesian networks for mixed dataNeural Computation10.1162/neco_a_0119031:6(1183-1214)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1162/neco_a_01190
Show More Cited By

Index Terms

Learning bayesian network structure from massive datasets: the «sparse candidate« algorithm
1. Computing methodologies
  1. Artificial intelligence
    1. Knowledge representation and reasoning
      1. Probabilistic reasoning
      2. Vagueness and fuzzy logic
  2. Machine learning
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Generalized Bayesian Structure Learning from Noisy Datasets
Database Systems for Advanced Applications
Abstract
In recent years, with the open data movement around the world, more and more open data sets are available. But, the quality of the datasets poses issues for learning models. This study focuses on learning the Bayesian network structure from data ...
Clustering massive datasets
Machine learning as massive search

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

UAI'99: Proceedings of the Fifteenth conference on Uncertainty in artificial intelligence

July 1999

703 pages

ISBN:1558606149

Editors:
Kathryn B. Laskey
George Mason University, Fairfax, Virginia
,
Henri Prade
Institut de Recherche en Informatique de Toulouse, Toulouse, France

Sponsors

Rockwell Science Center: Rockwell Science Center
HUGIN: Hugin Expert A/S
Information Extraction and Transportation
Microsoft Research: Microsoft Research
AT&T: AT&T Labs Research

Publisher

Morgan Kaufmann Publishers Inc.

San Francisco, CA, United States

Publication History

Published: 30 July 1999

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

93
Total Citations
View Citations
149
Total Downloads

Downloads (Last 12 months)57
Downloads (Last 6 weeks)15

Reflects downloads up to 30 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Orr LBalazinska MSuciu DMaier DPottinger RDoan ATan WAlawini ANgo H(2020)Sample Debiasing in the Themis Open World Database SystemProceedings of the 2020 ACM SIGMOD International Conference on Management of Data10.1145/3318464.3380606(257-268)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3318464.3380606
Barik AHonorio JWallach HLarochelle HBeygelzimer Ad'Alché-Buc FFox E(2019)Learning Bayesian networks with low rank conditional probability tablesProceedings of the 33rd International Conference on Neural Information Processing Systems10.5555/3454287.3455091(8964-8973)Online publication date: 8-Dec-2019
https://dl.acm.org/doi/10.5555/3454287.3455091
Xu SJia BLiang F(2019)Learning moral graphs in construction of high-dimensional bayesian networks for mixed dataNeural Computation10.1162/neco_a_0119031:6(1183-1214)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1162/neco_a_01190
Contaldi CVafaee FNelson P(2019)Bayesian network hybrid learning using an elite-guided genetic algorithmArtificial Intelligence Review10.1007/s10462-018-9615-552:1(245-272)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s10462-018-9615-5
Orphanou KThierens DBosman PTakadama K(2018)Learning bayesian network structures with GOMEAProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205502(1007-1014)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205502
Li SWang B(2018)Hybrid Parrallel Bayesian Network Structure Learning from Massive Data Using MapReduceJournal of Signal Processing Systems10.1007/s11265-017-1275-190:8-9(1115-1121)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s11265-017-1275-1
Khanteymoori AOlyaee MAbbaszadeh OValian M(2018)A novel method for Bayesian networks structure learning based on Breeding Swarm algorithmSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-017-2557-z22:9(3049-3060)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s00500-017-2557-z
Park GRaskutti G(2017)Learning quadratic variance function (QVF) DAG models via overdispersion scoring (ODS)The Journal of Machine Learning Research10.5555/3122009.324208118:1(8300-8342)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.5555/3122009.3242081
Contaldi CVafaee FNelson PBosman P(2017)The role of crossover operator in bayesian network structure learning performanceProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071240(769-776)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071240
Wang RAzab AEnck WLi NNing PChen XShen WCheng YKarri RSinanoglu OSadeghi AYi X(2017)SPOKEProceedings of the 2017 ACM on Asia Conference on Computer and Communications Security10.1145/3052973.3052991(612-624)Online publication date: 2-Apr-2017
https://dl.acm.org/doi/10.1145/3052973.3052991
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten