A spectral algorithm for latent junction trees.

For HMMs and latent trees, this rank condition can be expressed simply as requiring the conditional
probability tables of the underlying model to not be rank-deficient. However, junction trees encode sig-
nificantly more complex latent structures that introduce more subtle considerations. While we consider a
general characterization of such models where the observable representation to be future work, here try to
give some intuition on what types of latent structures the rank condition may fail.
First, the rank condition can fail is if there are not enough observed nodes/states, and thus #states(O i ) <
? i . Intuitively, this corresponds to a model where the latent space is too expressive and inherently represents
an intractable model (e.g. a set of n binary variables connected by a hidden node with 2 n states is equivalent
to a clique of size n).
However, there are more subtle considerations unique to non-tree models. In general, our method is not
limited to non-triangulated graphs (see the factorial HMM in Figure 3 of the main paper), but the process of
triangulation can introduce artificial dependencies that can lead to complications. Consider Figure 1(a) which
shows a DAG and its corresponding junction tree. To construct e P (C AD ), we may set P[O i , O
? i ] = P[D, F ]
based on the junction tree topology. However, in the original model before triangulation, D ? F because
of the v-structure. As a result, P[D, F ] does not have rank k h and thus cannot be inverted. However, note
that choosing P[O i , O
? i ] = P[D, E] is valid.
Finally consider Figure 1 (b), ignoring the orange nodes for now and assuming the variables are binary.
In this model, the hidden variables are largely redundant since integrating out A and B would simply give
a chain. F r 2
must be set to P[F | S r 2
] = P[F | AB]. If we think of A, B has just one large variable, then it is
clear that P[F | AB] = P[F | D]P[D | AB]. However, D only has two states while AB has 4, so P[F | AB] only has
rank 2. Now, consider adding the orange node. In this case we could set F r 2 to P[F, G | S r 2 ] = P[F, G | A, B]
whose matricized version has rank 4. Note that once the orange node has been added, integrating out A
and B no longer produces a simple chain, but a more complicated structure.
Thus, we believe that more rigorously characterizing the existence of the observable representation in
more detail, may shed light on the "intrinsic" complexity/redundancy of latent variable models in the context
of linear and tensor algebra.