Next: Experiments
Up: Discrete variables of arbitrary
Previous: Computing cooccurrences
Our goal is to presort the mutual information values for all
that do not cooccur with . The following theorem
shows that this can be done exactly as before.
Theorem Let be discrete variables such that do
not cooccur with (i.e.
) in a given
dataset . Let be the number of datapoints for
which and respectively, and let be the
respective empirical mutual information values based on the sample
. Then
with equality only if is identically 0.
The proof of the theorem is given in the Appendix. The implication
of this theorem is that the ACCL algorithm can be extended to
variables taking more than two values by making only one (minor)
modification: the replacement of the scalar counts and
by the vectors
and, respectively, the contingency
tables
.
Figure 23:
Running time for the ACCL (full line)
and (dotted line) CHOWLIU algorithms versus number of vertices
for different values of the sparseness .

Figure 24:
Number of steps of the Kruskal algorithm versus domain size
measured for the ACCL algorithm for different values of .

Next: Experiments
Up: Discrete variables of arbitrary
Previous: Computing cooccurrences
Journal of Machine Learning Research
20001019