
## 6.2 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 A.

The variable s controls the number of confactors, and p controls (probabilistically) the size of the tables. Figure 1110 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.

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 A 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 A. Figure 12 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.

## 7. Comparison With Other Proposals

In this section we compare CVE with other proposals for exploiting context-specific information.

The belief network with the conditional probability table of Figure 1 (i.e., with the contextual independence shown in Figure 4) is particularly illuminating because other algorithms do very badly on it. Under the elimination ordering B, D, C, A, Y, Z, to find the marginal on E, the most complicated confactor multiset created is the confactor multiset for E after eliminating B (see Example 14) with a total table size of 16. Observations simplify the algorithm as they mean fewer partial evaluations.

In contrast, VE requires a factor with table size 64 after B is eliminated. Clique tree propagation constructs two cliques, one containing Y, Z, A, B,C, D of size 26 = 64, and the other containing A, B, C, D, E of size 32. Neither takes the structure of the conditional probabilities into account.

Note however, that VE and clique tree propagation manipulate tables which can be indexed much faster than we can manipulate confactors. There are cases where the total size of the tables of the 10. Note that all of these results are statistically significant. The least significant is the s = 10 plot that, using the matchedsample t-test (also known as the paired t-test), is significant to the 0.05 level for the logarithm of the runtimes. The logarithm is appropriate as the difference in the logarithms corresponds to the multiplicative speedup.