A hybrid incremental learning algorithm for Bayesian network structures is proposed. A polynomial time constraint-based technique is developed to build up a candidate parent-set for each variable, and then a search-and-score technique is employed to refine the current network structure under the guidance of those candidate parent-sets. Experiment
results show that the algorithm offers considerable computational savings while always obtaining slightly better results on model accuracy compared to the existing incremental algorithms. The more complex the real world problems are, the more significant the advantage on computational complexity the algorithm keeps over the existing incremental algorithms is.