- Ankur P. Parikh, Le Song, Mariya Ishteva, G. Teodoru, E. Xing. 2012. A Spectral Algorithm For Latent Junction Trees-Supplementary Material. Abstract: The observable representation exists only if there exist transformations F i = P[Oi|Si] with rank τi := kh × |Si| and P[O−i|Si] also has rank τi (so that P(Oi,Oi−) has rank τi). Thus, it is required that #states(Oi) ≥ #states(Si). This can either be achieved by either making Oi consist of a few high dimensional observations, or many smaller dimensional ones. In the case when #states(Oi) > #states(Si), we need to project F i to a lower dimensional space such that it can be inverted using a tensor U i. In this case, we define F i := P[Oi|Si] ×Oi U i]. Following this through the computation gives us that P̃(Cl) = P(Ol,Ol−) ×Ol− (P(Ol,Ol− ×Oi U i). A good choice of Ui can be obtained by performing a singular value decomposition of the matricized version of P(Oi,Oi−) (variables in Oi are arranged to rows and those in Oi− to columns). 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 significantly 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(Oi) < τ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 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 P̃(CAD), we may set P[Oi,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 kh and thus cannot be inverted. However, note that choosing P[Oi,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. Fr2 must be set to P[F |Sr2 ] = 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 Fr2 to P[F,G|Sr2 ] = 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.
