Seminar on Computational Learning and Adaptation

Incremental Learning of Bayesian Network Structures

Josep Roure
Robotics Institute
Carnegie Mellon University

Modern data-mining problems often involve streams of data that grow continuously over time. In these environments, incremental learning methods become particularly relevant, since they can revise existing models without beginning from scratch and without reprocessing data. In this talk, we present two general heuristics that let one convert batch hill-climbing algorithms for learning Bayesian networks into incremental ones, after which we justify their correctness. When new data are available, these heuristics use the operator sequence taken in previous learning steps to guess whether the current network structure should be updated and, if so, which part should be revised. For Bayesian networks, these operators involve adding, deleting,  or reversing an arc. We illustrate how one can transform four well-known batch methods for learning Bayesian network structures into incremental ones, and we show experimentally that they produce nearly the same structures as the batch versions. Our experiments  also show that the incremental algorithms are almost unaffected by  the order of the training data.

Return to the seminar schedule