- Thanks to an anonymous reviewer for helping us to simplify this proof.
- 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.
- 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.
- 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.
- Obtained from
ftp://camis.stanford.edu/pub/pradhan. The file names are
V1.0.txt and CPCS
Fri Dec 6 15:09:32 PST 1996