Learning BayesianNetwork Structur e fr om Massive Datasets: The “SparseCandidate” Algorithm
LearningBayesiannetworksis often castas an optimizationproblem,wherethe computational task is to find a structurethat maximizesa statistically motivatedscore.By andlarge,existing learningtoolsaddressthis optimizationproblem usingstandardheuristicsearchtechniques. Since the searchspaceis extremelylarge, suchsearch procedurescanspendmostof thetimeexamining candidatesthatareextremelyunreasonable. This problembecomescriticalwhenwedealwith data sets that are large either in the numberof instances, or thenumberof attributes. In this paper , we introducean algorithm that achievesfasterlearningby restrictingthesearch space.This iterative algorithmrestrictsthe parentsof eachvariableto belongto a small subsetof candidates. We thensearchfor a network that satisfiestheseconstraints.The learnednetwork is thenusedfor selectingbettercandidates for thenext iteration.We evaluatethis algorithm bothon synthetic andreal-life data.Our results show thatit is significantlyfasterthanalternati ve searchprocedureswithout lossof quality in the learnedstructures.