On sensitivity of the MAP Bayesian network structure to the equivalent sample size parameter

BDeu marginal likelihood score is a popu-lar model selection criterion for selecting a Bayesian network structure based on sam-ple data. This non-informative scoring cri-terion assigns same score for network struc-tures that encode same independence state-ments. However, before applying the BDeu score, one must determine a single parame-ter, the equivalent sample size α. Unfortu-nately no generally accepted rule for deter-mining the α parameter has been suggested. This is disturbing, since in this paper we show through a series of concrete experiments that the solution of the network structure opti-mization problem is highly sensitive to the chosen α parameter value. Based on these results, we are able to give explanations for how and why this phenomenon happens, and discuss ideas for solving this problem.