next up previous contents
Next: Missing values Up: Learning Bayesian Networks Previous: Unknown Structure

An Example of Learning a Network from a Database

We illustrate how to learn a Bayesian network from a database with an example[*]. We have a database D which is given in Tab 3.1. We have four objects with three features , and the features can take the values T for true or F for false .


 
 
Table 3.1: A simple database.
Object A B C
1 T F T
2 T T T
3 F T T
4 F T T

First, we generate a hypothesis space of all possible structures of the network. Some of the possible structures are shown in Fig 3.6.


  
Figure 3.6: Some Possible Structures of the Network.
\begin{figure}
\begin{center}

\scalebox {0.4}{\includegraphics*[02cm,16cm][28cm,28cm]{modspac.eps}}

\end{center}\end{figure}

Then we calculate the likelihood of each model given the database, the sample likelihood:

\begin{displaymath}
P(sample \mid S_m,\theta_m) = \prod_{i}P(object_i \mid S_m,\theta_m)
\end{displaymath}

Where Sm is a structure, $\theta_m$ the parameters for the structure. Then, if we look at structure d from Fig 3.6, we get:

which with $\theta_d$ computed from the whole database[*]:

Then:

\begin{displaymath}
P(object_1 \mid S_d,\theta_d) = \frac{1}{4}
\end{displaymath}

These values are computed for all i and for all models, and then compared to find the best fitting model. Doing it this way involves vast computation, and finding a Bayesian network structure is indeed NP-complete. This situation was pretty simple, since we had only three features, and none of them had missing values.


next up previous contents
Next: Missing values Up: Learning Bayesian Networks Previous: Unknown Structure
Torgeir Dingsoyr
2/26/1998