Randomised NetworksEmpirical ResultsA Pseudo-Natural Example

A Pseudo-Natural Example

While it may seem that we should be able to test whether CVE is worthwhile for natural examples by comparing it to VE for standard examples, it isn't obvious that this is meaningful. With the table-based representations, there is a huge overhead for adding a new parent to a variable, however there is no overhead for making a complex function for how a variable depends on its existing parents. Thus, without the availability of effective algorithms that exploit contextual independence where there is a small overhead for adding a variable to restricted contexts, it is arguable that builders of models will tend to be reluctant to add variables, but will tend to overfit the function for how a variable depends on its parents. As all models are approximations it makes sense to consider approximations to standard models. As we are not testing the approximations [10][26], we will pretend these are the real models.

In this section we produce evidence that there exists networks for which CVE is better than VE. The sole purpose of this experiment it to demonstrate that there potentially are problems where it is worthwhile using CVE. We use an instance of the water network [17] from the Bayesian network repository8 where we approximated the conditional probabilities to create contextual independencies. Full details of how the examples were constructed are in Appendix *. We collapsed probabilities that were within 0.05 of each other to create confactors. The water network has 32 variables and the tabular representation has a table size of 11018 (after removing variables from tables that made a difference of less that 0.05). The contextual belief network representation we constructed had 41 confactors and a total table size of 5834.

Scatterplot of runtimes (in msecs) of CVE (x-axis) and VE (y-axis) for the water network. Full details are in Appendix *.
 

Figure * shows a scatter plot of 60 runs of random queries9. There were 20 runs each for 0, 5 and 10 observed variables. The raw data is presented in Appendix *. The first thing to notice is that, as the number of observations increases, inference becomes much faster. CVE was often significantly faster than VE. There are a few cases where CVE was much worse than VE; essentially, given the elimination ordering, the context-specific independence didn't save us anything in these example, but we had to pay the overhead of having variables in the context.

David Poole and Nevin Lianwen Zhang,Exploiting Contextual Independence In Probabilistic Inference, Journal of Artificial Intelligence Research, 18, 2003, 263-313.

Randomised NetworksEmpirical ResultsA Pseudo-Natural Example