Local score metrics

We use the following conventions to identify counts in the database $D$ and a network structure $B_S$. Let $r_i$ ($1\le i\le n$) be the cardinality of $x_i$. We use $q_i$ to denote the cardinality of the parent set of $x_i$ in $B_S$, that is, the number of different values to which the parents of $x_i$ can be instantiated. So, $q_i$ can be calculated as the product of cardinalities of nodes in $pa(x_i)$, $q_i=\prod_{x_j\in pa(x_i)}r_j$. Note $pa(x_i)=\emptyset$ implies $q_i=1$. We use $N_{ij}$ ($1\le i\le n$, $1\le j\le q_i$) to denote the number of records in $D$ for which $pa(x_i)$ takes its $j$th value.We use $N_{ijk}$ ($1\le i\le n$, $1\le j\le q_i$, $1\le k\le r_i$) to denote the number of records in $D$ for which $pa(x_i)$ takes its $j$th value and for which $x_i$ takes its $k$th value. So, $N_{ij}=\sum_{k=1}^{r_i}N_{ijk}$. We use $N$ to denote the number of records in $D$.

Let the entropy metric $H(B_S,D)$ of a network structure and database be defined as

$$H(B_S,D)=-N\sum_{i=1}^n\sum_{j=1}^{q_i}\sum_{k=1}^{r_i}\frac{N_{ijk}}{N}\log\frac{N_{ijk}}{N_{ij}}$$ (2)

and the number of parameters $K$ as

$$K=\sum_{i=1}^n(r_i-1)\cdot q_i$$ (3)

AIC metric The AIC metric $Q_{AIC}(B_S,D)$ of a Bayesian network structure $B_S$ for a database $D$ is

$$Q_{AIC}(B_S,D) = H(B_S,D)+K$$ (4)

A term $P(B_S)$ can be added [1] representing prior information over network structures, but will be ignored for simplicity in the Weka implementation.

MDL metric The minimum description length metric $Q_{MDL}(B_S,D)$ of a Bayesian network structure $B_S$ for a database $D$ is is defined as

$$Q_{MDL}(B_S,D) = H(B_S,D)+\frac{K}{2}\log N$$ (5)

Bayesian metric The Bayesian metric of a Bayesian network structure $B_D$ for a database $D$ is

$$Q_{Bayes}(B_S,D) = P(B_S)\prod_{i=0}^n\prod_{j=1}^{q_i}\frac... ...d_{k=1}^{r_i}\frac{\Gamma(N_{ijk}'+N_{ijk})}{\Gamma(N_{ijk}')}$$

where $P(B_S)$ is the prior on the network structure (taken to be constant hence ignored in the Weka implementation) and $\Gamma(.)$ the gamma-function. $N_{ij}'$ and $N_{ijk}'$ represent choices of priors on counts restricted by $N_{ij}'=\sum_{k=1}^{r_i}N_{ijk}'$. With $N_{ijk}'=1$ (and thus $N_{ij}'=r_i$), we obtain the K2 metric [5]

$$Q_{K2}(B_S,D) = P(B_S)\prod_{i=0}^n\prod_{j=1}^{q_i}\frac{(r_i-1)!}{(r_i-1+N_{ij})!} \prod_{k=1}^{r_i}N_{ijk}!$$

With $N_{ijk}'=1/r_i\cdot q_i$ (and thus $N_{ij}'=1/q_i$), we obtain the BDe metric [8].