next up previous contents
Next: Search algorithms Up: Local score based structure Previous: Local score based structure   Contents


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

\begin{displaymath}
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}}
\end{displaymath} (2)

and the number of parameters $K$ as
\begin{displaymath}
K=\sum_{i=1}^n(r_i-1)\cdot q_i
\end{displaymath} (3)

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

\begin{displaymath}
Q_{AIC}(B_S,D) = H(B_S,D)+K
\end{displaymath} (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


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

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

\begin{displaymath}
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}')}
\end{displaymath}

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]

\begin{displaymath}
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}!
\end{displaymath}

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


next up previous contents
Next: Search algorithms Up: Local score based structure Previous: Local score based structure   Contents
Remco Bouckaert 2008-05-12