PaperlayerView exact revision on arXiv

Source-linked AI summary

On Sensitivity of the MAP Bayesian Network Structure to the Equivalent Sample Size Parameter

Tomi Silander, Petri Kontkanen, Petri Myllymaki

arXiv:1206.5293v1cs.LGstat.ML

TL;DR

BDeu structure learning requires choosing an equivalent sample size α, for which no generally accepted rule exists. The paper uses experiments to study α's effect on MAP structures and explain how it arises. It finds that MAP structure selection can be highly sensitive to α, while exploring integration over α as one alternative.

  • Problem

    BDeu requires choosing an equivalent sample size α, but no generally accepted rule for selecting it has been suggested.

    Source: §1 · p. 1

  • Method

    The paper runs experiments on α's effect on MAP structures, analyzes how α affects arc emergence, and explores maximizing or integrating out α.

    Source: §1 · p. 1, §2 · p. 2, §5.1 · p. 6

  • Results

    The MAP structure can be highly sensitive to α, and integrating α out yields models that are MAP for reasonable α values between 1 and 100 in the reported datasets.

    Source: §1 · p. 1, §5.1 · p. 7

  • Takeaways & Limitations

    The authors advise recognizing MAP model-selection brittleness rather than choosing a convenient α value such as 1.0 without further consideration.

    Source: §6 · pp. 7–8

    The authors find no definite answer for choosing α, and integrating it out still requires a prior distribution whose effect on model selection remains for further study.

    Source: §6 · p. 8

Abstract

from arXiv · show

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.

1 INTRODUCTION

BDeu structure learning requires choosing an equivalent sample size α, but no generally accepted uninformative value is available. The paper examines how α affects the MAP structure, while emphasizing that its aim is awareness of this sensitivity, not evaluation of scoring criteria.

1 INTRODUCTION

  • No generally accepted uninformative α value exists for the popular BDeu score used to learn Bayesian-network structures from complete discrete data.BDeu assigns equal scores to structures encoding the same independence statements.Source: §1 · p. 1
  • The MAP structure can change substantially with α, despite α not being linked to the structure prior.The paper frames this sensitivity as a concern because α still changes the most probable structure.Source: §1 · p. 1
  • The authors report no previous systematic empirical study of α's role, while advances in exact structure learning make systematic study possible.They suggest the problem's computational hardness and focus on heuristics may help explain the lack of prior study.Source: §1 · p. 1
  • The engineering view evaluates models by task-specific behavior, where different structures may perform equally well on prediction or classification.The paper contrasts this with the scientific view of selecting the model most likely true, for which BDeu is often used.Source: §1 · p. 1
  • The authors aim to raise awareness of MAP-structure sensitivity to α, not to criticize or compare scoring criteria.They note BDeu's connection to prequential model selection, reported predictive performance of MAP selection, and the computational infeasibility of averaging over all structures.Source: §1 · p. 1

2 BDeu SCORE

The BDeu score selects the structure with the highest marginal likelihood under likelihood-equivalent, uniform structure priors. Its equivalent-sample construction sets Dirichlet hyperparameters from α, which encodes prior strength for uniform conditional distributions.

2 BDeu SCORE

  • The network's qualitative structure specifies conditional independences, while its quantitative component specifies the joint probability distribution.The paper studies learning the qualitative structure; its α parameter is related to priors on quantitative parameters.Source: §2 · p. 2
  • A network structure is a DAG whose parent sets specify incoming arcs, and its independence statements may be encoded by multiple different DAGs.Likelihood equivalence requires structures encoding the same independence assumptions to be equally probable.Source: §2 · p. 2
  • Under independent Dirichlet priors, observing counts N_ijk updates each conditional distribution's parameters by adding those counts to its prior hyperparameters.Likelihood equivalence constrains these conditional multinomial parameters to follow Dirichlet distributions.Source: §2 · p. 2
  • Equal Dirichlet hyperparameters express an expectation of equiprobable outcomes, with larger values expressing a stronger prior belief in equiprobability.When all hyperparameters are 1.0, the Dirichlet distribution is uniform over possible parameter vectors.Source: §2 · p. 2
  • The equivalent-sample method sets each conditional Dirichlet hyperparameter to α/(r_i q_i), distributing α across the variable's outcomes and parent configurations.Here r_i is the number of possible values of variable V_i, and q_i is the number of parent configurations, or 1 when it has no parents.Source: §2 · p. 2
  • With uniform priors over structures or equivalence classes, maximizing BDeu is equivalent to maximizing the posterior probability of the network structure.The learning task is to find the structure maximizing BDeu, or its logarithm.Source: §2 · p. 3

3 EXPERIMENTS

Across the experiments, changing α could produce different MAP structures even at realistic values, while the structural changes were not always monotonic. The results show substantial sensitivity, but not every dataset yielded every possible arc count.

3 EXPERIMENTS

  • The experiments used the bene software and 20 UCI data sets; continuous variables were discretized into three equal-width bins, and missing values were imputed by random draws from empirical distributions.The datasets were varied over α to examine changes in the globally optimal Bayesian network structure.Source: §3 · p. 3

3.1 HOW MUCH CAN THE MAP STRUCTURE VARY

  • For Yeast, varying α from 2e-20 to 34000 produced MAP networks with every arc count from 0 to 36.The Yeast data had 9 variables and 1,484 data vectors; across 20 data sets, many—but not all—showed considerable arc-count variation.Source: §3.1 · p. 3

3.2 NATURE OF VARIATION

  • Larger α values tended to produce more arcs, but the trend was non-monotonic, and α could change a network’s independence model without changing its arc count.For Post Operative, α values 50 and 55 produced 15 and 14 arcs; in Thyroid, changing α from 2 to 3 changed a V-structure while leaving the skeleton unchanged.Source: §3.2 · p. 4

3.3 VARIATION WITH REALISTIC VALUES OF α

  • In the Liver data, eight α values from 0.01 to 13 yielded eight different MAP models with 1 to 8 arcs; the reported BDeu-score curves cover α from 1 to 6.The score difference of 5 corresponds to a marginal likelihood ratio of about 150.Source: §3.3 · p. 4, Figure 2 · p. 4
  • On Breast Cancer Wisconsin, α values 1.00, 1.02, and 1.04 yielded MAP structures with 12, 13, and 14 arcs; Adult yielded 28, 29, 31, and 33 arcs at α values 2, 4, 8, and 16.The Adult data set had 32,561 records.Source: §3.3 · pp. 4–5

4 THE REASON FOR AN ARC

An arc’s BDeu score balances histogram gains against an α-dependent complexity penalty. In the V3-to-V8 example, increasing α from 1.00 to 1.02 shifts that balance enough to justify the arc.

4 THE REASON FOR AN ARC

  • The denominator penalizes adding a parent, with a larger K imposing a greater penalty, but increasing α makes that penalty smaller.Figure 4 plots the denominator change against α qiri for different K values.Source: §4 · p. 5, Figure 4 · p. 5
  • The numerator’s log Beta terms favor small, informative histograms, while the denominator penalty makes the net effect of an even split negative.Figure 5 compares log Beta values for histograms of different entropies and multipliers.Source: §4 · p. 6, Figure 5 · p. 6
  • Adding V3 as a parent splits V8’s two histograms into three each, and zero sufficient statistics make one gain behave unusually.The original histograms are (446, 12, 0) and (77, 105, 59); the resulting numerator change is shown in Figure 6. Zero counts yield Gamma terms depending only on fractions of α, consistent with earlier asymptotic findings.Source: §4 · p. 6, Figure 6 · p. 6
  • −0.09 at α=1.00 became 0.02 at α=1.02, justifying the V3-to-V8 arc.The calculation combines two histogram-splitting penalties with gains from splitting two histograms.Source: §4 · p. 6

5 THE “BEST MAP MODEL”

The section examines integrating out α and comparing that result with choosing a single α. In the experiments, integrated models were also MAP models for reasonable α values, while the choice of α prior remains consequential.

  • Integrating out α is computationally impractical for large datasets, described as having around 30 or more variables, because structure learning is NP-hard and demanding.The authors note that heuristic search is necessary for large datasets.Source: §5.1 · p. 6
  • The experiments use a uniform prior on α from 1 to 100 because the integral has no known closed form and numerical integration is costly.The study limits candidate models to those produced across that α range.Source: §5.1 · p. 7
  • For Glass, the MAP model at α = 5 (also α = 6) had the highest posterior probability when α was integrated out.Figure 7 shows posterior probabilities for 10 of the 22 structures found over α values 1–100.Source: Figure 7 · p. 7, §5.1 · p. 7
  • Across the datasets, the model selected by integrating out α was also the MAP model for reasonable α values.The maximizing α selected the same model as integration in all datasets studied.Source: §5.1 · p. 7
  • The prequential-score-maximizing α ranged from 2 for Iris to 51 for Tic-tac-toe, and α = 1 appeared slightly too small.The authors suggest the average number of values per variable as a possible choice when forced to select α, but find no easy heuristic.Source: §5.1 · p. 7
  • Maximizing α is an extreme integration case in which one α value has probability 1, so the prior distribution for α is itself a model-selection question.The authors suggest that very informative priors may also affect the MAP structure.Source: §5.1 · p. 7

6 DISCUSSION

The discussion emphasizes that BDeu-based MAP structures can be highly sensitive to α, so a convenient fixed value can leave model selection brittle. It recommends checking nearby structures and α values while noting that practical and Bayesian questions remain unresolved.

  • The authors report that BDeu-based MAP structures can be very sensitive to α, making a convenient default such as α = 1.0 a potentially brittle choice.They recommend being aware of that brittleness rather than adopting a convenient value without further examination.Source: §6 · pp. 7–8
  • Checking arc deletions, additions, or reversals around a learned structure across α values may reveal different MAP structures.The authors propose this as a practical check when learning only one structure is necessary.Source: §6 · p. 7
  • The two studied ways of choosing α give no definite answer, and integrating it out raises unresolved questions about its prior and predictive consequences.The authors state that comparing which method yields better predictions remains future work.Source: §6 · p. 8
  • The alternative NML criterion avoids an explicit parameter prior and is score equivalent, but efficient computation is available only for restricted network structures.The authors describe BIC and AIC as parameter-free but asymptotic approximations.Source: §6 · p. 8
Loading 1206.5293v1…