Mieczysław Alojzy Kłopotek

A New Space-Saving Bayesian Tree Construction Method for High Dimensional Spaces

925

Abstract

Bayesian networks have many practical applications due to their capability to represent joint probability distribution in many variables in a compact way. There exist efficient reasoning methods for Bayesian networks. Many algorithms for learning Bayesian networks from empirical data have been developed.

A well-known problem with Bayesian networks is the practical limitation for the number of variables for which a Bayesian network can be learned in reasonable time. A remarkable exception here is the Chow/Liu algorithm learning tree-like Bayesian networks. However, also this algorithm has an important limitation, related to space consumption. The space required is quadratic in the number of variables. The paper presents a novel algorithm overcoming this limitation for the tree-like class of Bayesian networks. The new algorithm space consumption grows linearly with the number of variables while the execution time is comparable with the Chow/Liu algorithm. This opens new perspectives in construction of Bayesian networks from data containing thousands and more variables, e.g. in automatic text categorization.

Keywords : machine learning, Bayesian networks, Chow/Liu algorithm, spatial complexity.