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 G of the Bayesian network,

  • DL(PโˆฃG)DL(P|G) represents the number of bits required to represent the set of probability tables P.

DL(B)=DL(G)+DL(PโˆฃG)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)}

where

  • 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 G

  • and PaiP{a_i} is the number of parents of the random variable Xi{X_i}.

Calculating DL(P|G)

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

DL(PโˆฃG)=โˆ‘in(โˆjโˆฅPaiโˆฅSjร—(Siโˆ’1)ร—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)}

where

  • 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)=logโก2(N)2DL(p) = \frac{{{{\log }_2}(N)}}{2}

Last updated

Logo

Bayesia USA

info@bayesia.us

Bayesia S.A.S.

info@bayesia.com

Bayesia Singapore

info@bayesia.com.sg

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