Randomised Networks

## Randomised Networks

In order to see how the algorithm depends on the structure inherent in the network, we constructed a number of parametrized classes of networks. We explicitly constructed networks that display contextual independence, as if there is not contextual independence this algorithm degenerates to VE.

We have the following parameters for building random networks:

n
the number of variables
s
the number of splits (so there will be n+s confactors).
p
the probability that a predecessor variable that isn't in the context of a confactor will be in the table of the confactor.
The exact algorithm for constructing the examples is given in Appendix *.

The variable s controls the number of confactors, and p controls (probabilistically) the size of the tables. Figure *10 shows a scatter plot comparing the runtimes of CVE and VE for n=30 and p=0.2 and for three different values of s, 5, 10, and 15.

Scatterplot of runtimes (in seconds) of CVE (x-axis) and VE (y-axis) for randomised networks

While this may look reasonable, it should be noticed that the number of splits and the number of different variables in the splits is strongly correlated in these examples (see Appendix * for details). However, one of the properties of CVE is that if a variable does not appear in the body of any confactor, it is never added to the context of a constructed confactor. That is, a variable that only appears in tables, always stays in tables. Thus it may be conjectured that having fewer variables appearing in contexts may be good for efficiency.

We carried out another experiment to test this hypothesis. In this experiment, the networks were generated as before, however, when we went to split a context we attempted to first split it using a variable that appears in a different context before using a variable that didn't appear in a context. The full details of the algorithms to generate examples and some example data are given in Appendix *. Figure * shows a scatter plot of comparing the run times for CVE and VE for each of the generated examples. With this class of networks CVE is significantly faster than VE.

Scatterplot of runtimes (in seconds) of CVE (x-axis) and VE (y-axis) for random networks biased towards fewer different variables in the contexts.

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

 Randomised Networks