21
$\begingroup$

I understand the theory behind Bayesian networks, and am wondering what it takes to build one in practice. Let's say for this example, that I have a Bayesian (directed) network of 100 discrete random variables; each variable can take one of up to 10 values.

Do I store all the nodes in a DAG, and for each node store its Conditional Probability Table (CPT)? Are there other data structures I should make use of to ensure efficient computation of values when some CPTs change (apart from those used by a DAG)?

$\endgroup$
  • $\begingroup$ I am using in memory sqlite database for storing CP tables, since DBs are expected to have efficient algorithms and data structures to deal with tables. Works fine! :) $\endgroup$ – Pratik Deoghare Mar 21 '12 at 11:19
  • $\begingroup$ Please define what you mean by efficient (memory, performance, etc) and include your constraints. Without those this could easily end up a contest for the most efficient which will degrade to cryptic code I'd never want to have to deal with in day to day work. $\endgroup$ – Justin Bozonier Mar 21 '12 at 11:36
  • 1
    $\begingroup$ @JustinBozonier requires less memory and is fast? $\endgroup$ – Pratik Deoghare Mar 21 '12 at 12:13
12
$\begingroup$

The "best" data structure probably depends on what particular problem you're trying to solve with it. Here's one approach that I've seen (and have used myself), which simply stores all the information and leaves it up to the algorithm what to do with it.

  1. First you index the nodes by unique integers, 0 through n-1. Then you simply store, for each node, the list of its parents as an array of integers --- in C++, for instance, you could have a std::vector<std::vector<int> >: first vector over nodes, second vector lists the respective parents). That captures the entire DAG structure.

  2. Furthermore, since each node has exactly one conditional probability table associated with it, you could index those with the same integer IDs. For each probability table you need to store its scope, i.e. the set of random variables its defined over. Secondly you'd probably have one large list of floating point numbers that contains the actual conditional probabilities (and you'll want to make sure you get the indexing right). To give a C++ example again, something like this could do:

    struct CondProbTable {
        std::vector<int> scope;    // list of random variables the CPT is defined over
        std::vector<double> table; // appropriately sized and indexed table of
                                   // conditional probabilities
    };
    

    With that, you could use a std::vector<CondProbTable> to store all your CPTs.

Again, this basically only stores the Bayes net, it does not assume anything about what you want to do with it. Including the CPT scope in CondProbTable is somewhat redundant, since it could be inferred from the list of parent nodes described under point 1.

$\endgroup$
0
$\begingroup$

Basically discrete CPT are hypermatrixes, and you should look at them in this way.

A quite common way to represent an hypermatrix is to use an hashtable using string index. e.g. in 2 dimensions t[1][2] would be t.get("1_2")

More memory efficient solution are possible: If the hypermatrix is sparse, you could use special sparse representation (e.g. Fuchs 72), if it has structure you could use ADD (algrebraic decision diagram), or logic-based rules.

Your last question is not very clear, however if you expected your CPT to change often, the probably you'll be better off with a flat representation of the CPT with either a table or an hashtable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.