Calculating Complexity Dl B

Calculating Complexity: DL(B)

Description Length of the Bayesian Network — DL(B)

DL(B)DL(B) is the number of bits required to represent a Bayesian network. We can break down this value into the sum of two components:

  • DL(G)DL(G), which stands for the number of bits required to represent the graph GG of the Bayesian network,
  • DL(PG)DL(P|G) represents the number of bits required to represent the set of probability tables PP.

DL(B)=DL(G)+DL(PG)DL(B) = DL(G) + DL(P|G)

Calculating DL(G)

To calculate DL(G)DL(G), we need to determine the number of nodes and the number of their parent nodes.

DL(G) = \sum\limits_i^n {\left( {{{\log }_2}(n) + {{\log }_2}\left( {\begin{array}{*{20}{c}} n\\ {\left\| {P{a_i}} \right\|} \end{array}} \right)} \right)}


  • n is the number of random variables (nodes): X1,...,Xn{X_1},...,{X_n}
  • PaiP{a_i} is the set of the random variables that are parents of Xi{X_i} in graph GG
  • and PaiP{a_i} is the number of parents of the random variable Xi{X_i}.

Calculating DL(P|G)

Computing DL(PG)DL(P|G) is straightforward as it is proportional to the number of cells in all probability tables.

DL(PG)=in(jPaiSj×(Si1)×DL(p))DL(P|G) = \sum\limits_i^n {\left( {\prod\limits_j^{\left\| {P{a_i}} \right\|} {{S_j} \times ({S_i} - 1) \times DL(p)} } \right)}


  • Si{{S}_{i}} is the number of states of the random variable Xi{X_i}
  • pp is the probability associated with the cell.

As the probability p cannot be known prior to learning the network, we use the following classical heuristic in BayesiaLab:

DL(p)=log2(N)2DL(p) = \frac{{{{\log }_2}(N)}}{2}

For North America

Bayesia USA

4235 Hillsboro Pike
Suite 300-688
Nashville, TN 37215, USA

+1 888-386-8383

Head Office

Bayesia S.A.S.

Parc Ceres, Batiment N 21
rue Ferdinand Buisson
53810 Change, France

For Asia/Pacific

Bayesia Singapore

1 Fusionopolis Place
#03-20 Galaxis
Singapore 138522

Copyright © 2024 Bayesia S.A.S., Bayesia USA, LLC, and Bayesia Singapore Pte. Ltd. All Rights Reserved.