Next: Experiments
Up: Discrete variables of arbitrary
Previous: Computing co-occurrences
Our goal is to presort the mutual information values
for all
that do not co-occur with
. The following theorem
shows that this can be done exactly as before.
Theorem Let
be discrete variables such that
do
not co-occur 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 co-occurrences
Journal of Machine Learning Research
2000-10-19