Paper · 2013-02-20 · cs.AI
Learning Bayesian Networks: A Unification for Discrete and Gaussian Domains
Scores Bayesian network structures from data plus prior beliefs with one metric (Be), built on likelihood equivalence, parameter independence and modularity. It gives BDe for discrete variables (Dirichlet priors) and BGe for Gaussian variables (normal-Wishart priors). No experiments; results are closed-form metrics and consistency proofs.
Bayesian networkBayesian scoring metricstructure-learningbayesian-networksdirichlet-priornormal-wishart-prior
AI-compiled by claude-haiku-5-5 on 2026-11-12, not yet reviewed by a human. Every claim cites its source; check it when a detail matters.
In plain words
Suppose you want a graph that shows which quantities influence which others, and you have both some data and some expert beliefs. This paper gives a rule for scoring a candidate graph: a higher score means the graph explains the data and the beliefs better. The score is a probability-based number, so graphs can be compared against each other and against an empty graph.
The authors handle two kinds of quantities: categories and measurements that follow a bell-shaped spread. Their earlier work treated these separately with different formulas. Here one rule is derived from a few general assumptions, and it reduces to a concrete formula for each kind. The beliefs enter as a starting prior plus a number saying how many imaginary cases those beliefs are worth.
The rule rests on a shared principle: two graphs that imply exactly the same independence statements should get the same score. Keeping that principle makes the scores consistent with each other, and the paper checks that the assumptions do not contradict one another.
TL;DR
The paper derives a Bayesian score for learning the structure of a Bayesian network from data and prior knowledge. Its general metric (Be) needs only likelihood equivalence, parameter independence and modularity, with complete data. Two closed forms follow: BDe for discrete variables with Dirichlet priors, and BGe for Gaussian variables with normal-Wishart priors. The paper reports no experiments, so its results are formulas and proofs, not measured accuracy.
Problem
Ranking candidate network structures needs a score for each one. Summing over all structures is impractical, so only a small set of high-posterior structures is scored §2. Writing the score requires a prior over the parameters of every structure, and assessing such a prior for each structure separately is impractical §3. The earlier discrete and Gaussian papers reached their scores by different routes, which made the parallels hard to see §1. The closed forms also assume complete data, with no missing values §4, Assumption 6.
Method
Overview: the score of a structure S is its relative posterior p(D, H_S | ξ), up to the normalising constant. A Bayes factor against a reference structure such as the empty graph gives the same ranking §2 eq. 8. The pieces are: a random-sample assumption §2; four prior assumptions §3; a general Be metric for complete data §4; and closed forms for discrete (BDe) and Gaussian (BGe) variables §5.
-
Random sample. Given the structure hypothesis H_S, each variable's observations are drawn with parameters that depend only on its own parents §2 eq. 11. For discrete variables this is the conditional table entry for the child given its parent configuration eq. 9. For Gaussian variables the child is normal with mean m_i plus a weighted sum of its parents and variance v_i eq. 10.
-
Gaussian networks. A multivariate normal factorises into conditional normals, one per variable, with coefficients b_ji on each arc and conditional variances v_i §1 eq. 2 eq. 3. The paper writes these as intercepts m_i with m_i = mu_i minus the sum of b_ji times mu_j eq. 5 eq. 6. The precision matrix W is recovered recursively from v and B, starting from W(1) = 1/v_1 eq. 4. Equation 7 gives the example for the structure x1 -> x3 <- x2.
-
Assumptions on the priors.
- A2, likelihood equivalence: equivalent structures induce the same prior over the joint parameters §3.
- A3, structure possibility: every complete structure has positive prior probability §3.
- A4, global parameter independence: the parameter sets of different variables are independent §3.
- A5, parameter modularity: a variable's parameter prior depends only on its parent set, not on the rest of the structure §3. The paper presents these as abstractions of assumptions earlier work made explicitly or implicitly §3.
-
Priors for every structure from one complete structure. Starting from a density over the parameters of one complete structure H_sc, A2 to A5 fix the prior for every other structure §3, Theorem 2. For two binary variables the construction changes variables to the local parameters, with Jacobian theta_x (1 - theta_x) for x -> y and theta_y (1 - theta_y) for y -> x eq. 12 eq. 13. The empty graph then takes each marginal from the modular parameter densities of the two directed structures §3. The flow is summarised in fig. 1, which is described here and not reproduced.
-
Be metric (Assumptions 1 to 6). For any structure S and any complete H_sc: p(D, H_S | ξ) = p(H_S | ξ) times the product over children i of p(D^{Pi_i, x_i} | H_sc, ξ) divided by p(D^{Pi_i} | H_sc, ξ) §4 Theorem 6 eq. 14. Here D^X is the database projected onto the variables X §4. Lemmas 3 to 5 provide posterior parameter independence, posterior modularity, and the marginal rule that lets a projection be taken before conditioning §4. Theorem 1, Chickering's arc-reversal characterisation of equivalent structures, is the tool for the proof that likelihood equivalence holds §1 Theorem 1 §7.3 Theorem 14.
-
BDe, discrete variables. The joint parameter vector has a Dirichlet prior whose exponent for each joint state is N' times its prior probability, minus 1 §5.1 eq. 15. Marginals of a Dirichlet are Dirichlet eq. 16, and the standard Dirichlet-multinomial marginal is given in eq. 17. Combining these with the Be metric gives Theorem 7 §5.1 eq. 18. The counts N_ijk are the number of cases where x_i = k and its parents are in configuration j. The prior counts are N'_ijk = N' times p(x_i = k, Pi_i = j | H_sc, ξ), with N'_ij the sum over k §5.1 eq. 19.
-
BGe, Gaussian variables. The prior is normal-Wishart. Conditional on W, the mean is normal with mean mu_0 and precision N'_mu times W. W itself is Wishart with N'_tau degrees of freedom and scale matrix T_0 §5.2 eq. 20. Given data, the posterior mean is (N'_mu mu_0 + m xbar_m) / (N'_mu + m) and the posterior scale matrix is T_m = T_0 + S_m + (N'_mu m / (N'_mu + m)) (mu_0 - xbar_m) (mu_0 - xbar_m)' §5.2 eq. 21 eq. 22. The marginal over a subset X with l variables is Theorem 8 §5.2 eq. 23, with the multivariate gamma factor c(l, v) given by eq. 24. Its degrees of freedom are nu = N'_tau - n + l, where n is the number of variables in the full domain §5.2. This is the corrected form, marked red in the source.
-
Mixed discrete and continuous domains. Put the discrete variables before the continuous ones in the ordering. Use the BDe term for discrete variables and the BGe term for continuous variables, one normal-Wishart prior per discrete state §5.2.
-
Assessing the priors. For discrete domains, the joint over the first case is assessed with a prior network conditioned on H_sc, plus the effective sample size N' §6. For Gaussian domains two effective sizes are needed: N'_mu > 0 and N'_tau > n - 1, plus a prior network. The details and examples are in the 1994 Gaussian paper, not in this one §6.
-
Consistency. The Dirichlet assumption is consistent with likelihood equivalence and global parameter independence: the Jacobian from the joint parameters to the complete-structure parameters is eq. 25 (Theorem 9), and the conditional parameters then have Dirichlet densities with summed counts N'{x_i|x_1..x{i-1}} eq. 26 eq. 27 eq. 28 (Theorem 10). For the normal-Wishart case, the Jacobian from W to (v, B) is the product of v_i to the power minus (i + 1) eq. 29 eq. 31 (Theorem 11); the mean Jacobian is 1 (Theorem 12); and the joint density factorises over i eq. 32 eq. 33 eq. 34 (Theorem 13). Theorem 14 §7.3 then shows the Be metric is likelihood equivalent for all structures, not only complete ones.
Pseudocode, BDe score for a whole structure §5.1 eq. 18 eq. 19:
# BDe log score of one structure [§5.1] [eq. 18]
# counts[i][j, k] = N_ijk; prior[i][j, k] = N'_ijk [eq. 19]
# Output: log p(D, H_S | xi), with log p(H_S | xi) added in
def bde_log_score(counts, prior, log_structure_prior):
total = log_structure_prior # log p(H_S | xi) [§2]
for child in range(len(counts)):
# N'_ij and N_ij: sums over the child states k [eq. 19]
prior_per_config = prior[child].sum(axis=1)
count_per_config = counts[child].sum(axis=1)
# Gamma(N'_ij) / Gamma(N'_ij + N_ij), product over configurations j
total += gammaln(prior_per_config).sum()
total -= gammaln(prior_per_config + count_per_config).sum()
# Gamma(N'_ijk + N_ijk) / Gamma(N'_ijk), product over j and k
total += gammaln(prior[child] + counts[child]).sum()
total -= gammaln(prior[child]).sum()
return totalPseudocode, BGe score for a whole structure §4 Theorem 6 §5.2 eq. 14 eq. 23:
# BGe log score of one structure [§4] [eq. 14] [§5.2]
# parents[i] lists the parent indices of x_i; prior holds the constants
# of [§5.2] (mu0, T0, N'_mu, N'_tau)
def bge_log_score(data, parents, prior, log_structure_prior):
total = log_structure_prior # log p(H_S | xi) [§2]
for child in range(data.shape[1]):
# Child-with-parents term divided by parents-only term [eq. 14]
with_child = bge_log_term(
data, parents[child] + [child], prior)
parents_only = bge_log_term(data, parents[child], prior)
total += with_child - parents_only
return total
# log p(D^X | H_sc, xi) for the subset X [§5.2] [eq. 23]
# The empty subset returns 0 (see Pitfalls)
def bge_log_term(data, subset, prior):
if len(subset) == 0:
return 0.0
m = data.shape[0] # number of cases
n = data.shape[1] # variables in the full domain
l = len(subset) # |X|
# Marginal Wishart degrees of freedom: N'_tau - n + l [§5.2] (red)
nu = prior.n_tau - n + l
tau_m = posterior_tau(data, prior) # full n x n [eq. 22]
tau_m_x = tau_m[np.ix_(subset, subset)] # submatrix M^X [§5.2]
tau0_x = prior.tau0[np.ix_(subset, subset)]
log_p = -0.5 * l * m * np.log(np.pi)
log_p += 0.5 * l * np.log(prior.n_mu / (prior.n_mu + m))
log_p += log_c(l, m + nu) - log_c(l, nu)
log_p += 0.5 * nu * logdet(tau0_x)
log_p -= 0.5 * (m + nu) * logdet(tau_m_x)
return log_p
# Posterior scale matrix T_m [§5.2] [eq. 22]
# S_m is the scatter matrix; its formula is not written in this paper
def posterior_tau(data, prior):
m = data.shape[0]
mean = data.mean(axis=0) # sample mean xbar_m [§5.2]
scatter = scatter_matrix(data) # S_m, see Pitfalls
shift = prior.mu0 - mean
weight = prior.n_mu * m / (prior.n_mu + m)
return prior.tau0 + scatter + weight * np.outer(shift, shift)
# Log of c(l, v) = product over i = 1..l of Gamma((v + 1 - i) / 2) [eq. 24]
def log_c(l, v):
return sum(gammaln((v + 1 - i) / 2) for i in range(1, l + 1))Key equations, stated in the form the paper gives them:
\mathrm{BDe}:\quad p(D, H_S \mid \xi) = p(H_S \mid \xi) \prod_{i} \prod_{j} \frac{\Gamma(N'_{ij})}{\Gamma(N'_{ij} + N_{ij})} \prod_{k} \frac{\Gamma(N'_{ijk} + N_{ijk})}{\Gamma(N'_{ijk})} eq. 18
\mathrm{BGe}:\quad p(D^X \mid H_{sc}, \xi) = \pi^{-lm/2} \left(\frac{N'_\mu}{N'_\mu + m}\right)^{l/2} \frac{c(l, m + \nu)}{c(l, \nu)} |T_0^X|^{\nu/2} |T_m^X|^{-(m+\nu)/2}, \quad \nu = N'_\tau - n + l eq. 23
Hyperparameters
The paper gives no default values. Every constant below is an input that the user must assess.
| Name | Value | Where | Notes |
|---|---|---|---|
| Effective sample size N' (discrete) | not stated | §5.1 §6 | Assessed separately; the paper refers to §6 for its methods |
| Gaussian mean prior size N'_mu | > 0 | §5.2 | Effective sample size for the normal component |
| Gaussian Wishart degrees of freedom N'_tau | > n - 1 | §5.2 §6 | Effective sample size for the Wishart component |
| Prior mean mu_0 | not stated | §5.2 | Assessed through a prior network §6 |
| Prior scale matrix T_0 | positive definite | §5.2 | No construction given beyond the prior network §6 |
| Structure prior p(H_S | xi) | not stated | §2 | Assessed elsewhere; the score is defined up to this factor |
| Reference complete structure H_sc | any complete structure | §4 §7.3 | Likelihood equivalence [Theorem 14] |
| Positive prior on complete structures | p(H_sc | xi) > 0 | §3 Assumption 3 | Needed for the construction |
| Missing data | none allowed in closed forms | §4 Assumption 6 | Missing data is not formulated |
Results
The paper reports no experiments and no benchmark numbers. Its results are formulas and proofs, so none of them are author-reported measurements.
| Result | What it gives | Source |
|---|---|---|
| Be metric, general | Score of any structure from complete-structure marginals | §4 Theorem 6 eq. 14 |
| Prior from a complete structure | Priors for every structure from one density | §3 Theorem 2 |
| BDe closed form (discrete) | Gamma-function score per child and parent configuration | §5.1 Theorem 7 eq. 18 eq. 19 |
| BGe closed form (Gaussian) | Marginal term for a subset with l variables | §5.2 Theorem 8 eq. 23 eq. 24 |
| Consistency of the Dirichlet assumption | Conditional parameters are Dirichlet | §7.1 Theorems 9 and 10 eq. 25 eq. 28 |
| Consistency of the normal-Wishart assumption | Factorisation over variables | §7.2 Theorems 11 to 13 eq. 29 eq. 34 |
| Likelihood equivalence for all structures | Equivalent structures get equal scores | §7.3 Theorem 14 |
Paper vs code
No official code.
What I searched: the paper text and its bibliography contain no repository link. The only linked item is arXiv:1302.6808, the 1994 Gaussian paper (bibliography). No project page is linked. GitHub searches: "BGe score Bayesian network" returned one hit, MIX-GBN, which is a third-party BGe score for tied-covariance mixture models with no license and no connection to the authors. "Heckerman Geiger Bayesian network structure learning" returned no results. "BDe metric" returned no relevant repositories. None of these is an official implementation.
Pitfalls
- Red and blue marks. The source marks corrections in red, taken from a 2014 addendum by Kuipers, Moffa and Heckerman, and other updates in blue [abstract]. The corrected marginal degrees of freedom are N'_tau - n + l, as in the Theorem 8 statement and eq. 23 §5.2. Code or notes written from older text may use a different exponent (inference, not stated in the paper). Use the corrected form.
- Scatter matrix undefined. The paper introduces S_m as the sample scatter matrix §5.2 but never writes its formula. The paper defers the Gaussian formula to the 1994 paper §5.2. Confirm the definition before implementing it.
- Notation drift. The proof of Theorem 13 writes the Wishart degrees of freedom as alpha in eq. 33, while the statement uses N'_tau §7.2. Read alpha as N'_tau.
- Empty parent sets. Eq. 14 divides by p(D^{Pi_i} | H_sc, xi), but the paper never defines D^empty. Root nodes need this term to equal 1, which the code above assumes (inference). Check your own implementation.
- Zero prior cells. The BDe closed form takes Gamma(0) in the denominator when any N'_ijk is zero. Assumption 3 requires positive prior on complete structures, so the prior should keep every cell positive (inference from §3 and eq. 18).
- Complete data only. The closed forms assume no missing values §4. The paper mentions filling in, EM and Gibbs sampling as routes to incomplete data but does not develop any of them §4.
- Causal vs acausal. For acausal networks the paper says to score equivalence classes rather than single structures §3. For causal networks the hypothesis definition changes, so hypothesis equivalence fails, and likelihood equivalence becomes an assumption that the authors find reasonable in many domains §3.
- Overlapping hypotheses. Hypotheses from different equivalence classes overlap, but only on a set of measure zero, so eq. 8 can be used unchanged §3 footnote.
- Reference structure. Eq. 14 holds for any complete H_sc, but each closed form takes the prior of the chosen H_sc as input §4 §5. Choosing a different reference changes the prior that is being assumed, even though the score is invariant by Theorem 14 §7.3.
- Numerics. The paper gives products of Gamma functions and determinants. For many variables these overflow, so implementations usually compute logs. The paper gives no numerical guidance (the pseudocode above is in logs).
- No validation. Nothing here measures structure recovery, predictive accuracy or runtime. Test any implementation on a known network before relying on it.
- Prior network conditioning. The prior network is conditioned on the complete reference structure, which the authors call an unusual aspect of the assessment §6.
Lineage
- Builds on: Heckerman, Geiger and Chickering (1994) for the discrete BDe metric §5.1; Geiger and Heckerman (1994), arXiv:1302.6808, for the Gaussian BGe metric §5.2 §6; Shachter and Kenley (1989) for the Gaussian network transformation §1; Verma and Pearl (1990) for network equivalence §1; Spiegelhalter and Lauritzen (1990) for global parameter independence §3.
- Unifies: the paper merges the two 1994 approaches into one metric §1.
- Corrected by: the 2014 addendum by Kuipers, Moffa and Heckerman, whose corrections are incorporated in this version [abstract]. The 2021 arXiv v3 is the version fetched here.
- Compared against: none. The paper reports no experiments.
- Superseded by: not known from content in this wiki.
Source and license
Adapted from “Learning Bayesian Networks: A Unification for Discrete and Gaussian Domains” by David Heckerman, Dan Geiger (arXiv:1302.4957), used under CC BY 4.0. Changes: condensed and restructured for implementation, with tables, equations and algorithms taken from the paper and its code, each cited to its source. Not affiliated with or endorsed by the authors.