...Proof:

Thanks to an anonymous reviewer for helping us to simplify this proof.

...by:

Note that the base combination operators under the summations are indexed. With each convergent variable is an associated operator, and we always use the binary operator that is associated with the corresponding convergent variable. In the examples, for ease of exposition, we will use one base combination operator. Where there is more than one type of base combination operator (e.g., we may use `or', `sum' and `max' for different variables in the same network), we have to keep track of which operators are associated with which convergent variables. This will, however, complicate the description.

...additions.

This is exactly the same number of operations required to determine 418#418 using clique-tree propagation on the same network. The clique tree for Figure 3(3) has three cliques, one containing 419#419, one containing 420#420, and once containing 421#421. The first clique contains 8 elements; to construct it requires 422#422 multiplications. The message that needs to be sent to the third clique is the marginal on 423#423 which is obtained by summing out 424#424 and 425#425. Similarly for the second clique. The third clique again has 8 elements and requires 12 multiplications to construct. In order to extract 426#426 from this clique, we need to sum out 427#427 and 428#428. This shown one reason why VE1 can be more efficient that CTP or VE ; VE1 never constructs a factor with three variables for this example. Note however, that an advantage of CTP is that the cost of building the cliques can be amortized over many queries.

...produce

Note that we need to produce two variables both of which represent ``noisy'' 438#438. We need two variables as the noise applied in each case is independent. Note that if there was no noise in the network --- if 439#439 --- we only need to create one variable, but also 440#440 and 441#441 would be the same variable (or at least be perfectly correlated). In this case we would need a more complicated example to show our point.

...networks

Obtained from ftp://camis.stanford.edu/pub/pradhan. The file names are CPCS
[0]-LM-
[0]SM-
[0]K0-
[0]V1.0.txt and CPCS
[0]-networks
[0]/std1.
[0]08.5.

David Poole
Fri Dec 6 15:09:32 PST 1996