  BDeu marginal likelihood score is a popular model selection criterion for
selecting a Bayesian network structure based on sample data. This
non-informative scoring criterion assigns same score for network structures
that encode same independence statements. However, before applying the BDeu
score, one must determine a single parameter, the equivalent sample size alpha.
Unfortunately no generally accepted rule for determining the alpha 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
optimization problem is highly sensitive to the chosen alpha 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.
