Year: 2021

Abstract:
A key goal of unsupervised representation learning is “inverting” a data generating process to recover its latent properties. Existing work that provably achieves this goal relies on strong assumptions on relationships between the latent variables (e.g., independence conditional on auxiliary information). In this paper, we take a very different perspective on the problem and ask, “Can we instead identify latent properties by leveraging knowledge of the mechanisms that govern their evolution?” We provide a complete characterization of the sources of non-identifiability as we vary knowledge about a set of possible mechanisms. In particular, we prove that if we know the exact mechanisms under which the latent properties evolve, then identification can be achieved up to any equivariances that are shared by the underlying mechanisms. We generalize this characterization to settings where we only know some hypothesis class over possible mechanisms, as well as settings where the mechanisms are stochastic. We demonstrate the power of this mechanismbased perspective by showing that we can leverage our results to generalize existing identifiable representation learning results.These results suggest that by exploiting inductive biases on mechanisms, it is possible to design a range of new identifiable representation learning approaches.

heading: 1 INTRODUCTION
text: Modern unsupervised representation learning techniques can generate images of our world with intricate detail (e.g. Karras et al., 2019; Song et al., 2020; Razavi et al., 2019), and yet, the latent representations from which these images are generated remain entangled and challenging to interpret (Schölkopf et al., 2021; Locatello et al., 2019). At the same time, the success of pre-trained transformers (Devlin et al., 2018; Brown et al., 2020) shows that advances in our ability to disentangle the underlying generative factors can lead to dramatic improvements in the sample complexity of downstream supervised tasks (Bengio & LeCun, 2007; Bengio et al., 2013). In order to consistently replicate this success, we need methods that can reliably invert the data generating process. This is a challenging task because unsupervised representation learning with independent and identically distributed (IID) data is hopelessly unidentified: even in the nice case in which observations are generated via some p(x|z), there exists an infinitely large class of possible latent distributions p̃(z|x) that are consistent with the observed marginal distribution, p(x), and only one of them corresponds to the true latent distribution p(z|x) (Locatello et al., 2019; Khemakhem et al., 2020a). If we want to build systems which are able to provably identify1 the true latent variables z that generated our observed data x = g(z) for some observation model g, then we need to exploit structural assumptions that constrain this set of possible distributions. Most of the prior work that can provide such guarantees was developed in the independent component analysis (ICA) literature. The key ICA assumption is that the latent factors are (conditionally) independent and non-Gaussian. Then, if the observation model, g : Z → X is linear and invertible, z = g−1(x) is identified (Comon, 1994), and for nonlinear g there are a number of recent approaches that leverage non-stationarity in the distributions over z to identify g−1 (Hyvarinen & Morioka, 2016; 2017; Hyvarinen et al., 2019;
1A problem is identified if there exists a unique solution in the infinite data limit and no constraints on model capacity.
Khemakhem et al., 2020a). These results give a tantalizing demonstration that representation learning with identification guarantees is possible, but the requirement that the latent factors are statistically (conditionally) independent is limiting2 (Higgins et al., 2018; Schölkopf et al., 2021).
In this paper we take a very different approach. We study how the mechanisms that govern an environment’s evolution constrain the set of possible latent representations that are consistent with the data. As a simple concrete example, consider the bouncing ball environment shown in Figure 1. The latent state can be completely described by a vector, z, containing the position, velocity and acceleration of the balls3, and given this latent state, the images, x, shown in Figure 1, are produced via some rendering engine g : Z → X . Our task is to leverage sequences of observations x1, . . . , xT and knowledge of m to recover z1, . . . , zT . If we can show that this task has a unique solution that is consistent with the observations and mechanisms, then the problem is identified.
Our main result is that when we know the true mechanism, m, the system is identified up to any equivariances of the mechanism; or equivalently, in Section 2.2 we prove that we can identify z up to any invertible transformation a : Z → Z that commutes with m, such that the composition m◦a = a◦m. For example, in the bouncing balls environment shown in Figure 1, the laws of physics are equivariant with respect to your choice of units of measurement—changing from representing z in meters to inches leaves the output of the mechanism unchanged up to a corresponding unit change— and hence we can only hope to identify z up to some scaling function a(z) which corresponds to an arbitrary choice of units of measurement. Interestingly, when the environment evolves according to multiple known mechanisms, the sources of non-identifiability are even further constrained: such a system is identified up to equivariances that are shared by all n mechanisms.
Perfectly knowing the true mechanisms and when they are applied is unlikely, but in Section 2.3 we show that we can relax that assumption to a setting where we instead know a hypothesis class of possible mechanisms that could have been applied. This weaker assumption leads to an additional
2As a simple example of dependence between latent variables, assume the bouncing balls shown in Figure 1 have different masses indicated by their colors. If the initial conditions were such that all the balls have the same momentum, then mass and velocity will be inversely correlated.
3A complete generative model of these images would also need to track the colors and shapes of the elements; we will return to this issue in the discussion of the results.
source of non-identifiability: the mechanisms in our hypothesis class can imitate each other if there exists an invertible transformation a such that for any two mechanisms m1 and m2 in our hypothesis class, m2 = a−1 ◦m1 ◦ a. For example, if we are in a setting where our hypothesis class includes both a product mechanism, m1(z) = ∏ i zi, and a sum mechanism, m2(z) = ∑ i zi, then m1 can
imitate m2 if a(z) = exp(z), since ∑ i zi = log( ∏ i exp(zi)). As before, this result is complete, in the sense that these two sources of non-identifiability—equivariance and imitation—are the only sources of non-identifiability in such systems. This gives us a natural way of thinking about the way knowledge of deterministic mechanisms constrains a representation learning task: with complete knowledge, the only source of non-identifiability is any equivariances inherent in the mechanism, but by allowing a hypothesis class of possible mechanisms, we introduce potential non-identifiability via imitation. That said, the relationship between the size of the hypothesis class and the size of the set of a’s that commute via imitation is not necessarily monotonic: for environments governed by multiple mechanisms, a larger hypothesis class can lead to fewer imitations.
Section 3, shows that we can derive analogous results for stochastic mechanisms, m(z, U), where the mechanism defines a conditional distribution p(zt+1|zt). This generalization gives us a way of comparing our mechanism-based perspective with existing identifiability results. We demonstrate this in Section 4 by showing that it is possible to view the distributional assumptions made in Klindt et al. (2020) as a particular choice of mechanism, and by doing so, we can leverage our theory to give alternative proofs of these results. This strategy required weaker distributional assumptions, thereby generalizing their result. Finally, we give a mechanism-based perspective on the related work in Section 5 and Section 6 concludes with a discussion of the open problems that need to be addressed in order to reliably leverage this approach in practice.

heading: 2 MECHANISM BASED IDENTIFICATION

heading: 2.1 DATA GENERATION PROCESS
text: The state of the system at time t ∈ {1, · · · , T} is given by zt ∈ Z ⊆ Rd. At each time t, we observe g(zt) = xt ∈ X ⊆ Rn, which is some transformation of the latent zt. We can think of g : Z → X as a function that transforms the (typically low dimensional) state variables to the (typically high dimensional) observed variables; for example, in the bouncing ball environment described in the introduction, g is the rendering engine that produces the images shown in Figure 1. We assume g is injective 4 with respect to Rn—i.e. g(z1) = g(z2) implies z1 = z2; or equivalently, any change to the underlying state, z, is reflected in some pixel-level change to the observation x—and we make g bijective by restricting its inverse g−1 to any x on the data manifold which we denote X (i.e. X is the image of g). The state transition from time t to t+ 1 is governed by a mechanism mt : Z → Z . There may be multiple mechanisms in a given environment. For example in Figure 1 the transition from z1 to z2 does not involve any collisions so the state evolves according to Newton’s first law of motion (Newton, 1687); the transition from z2 to z3 involves a collision between two of the balls that is described by Newton’s third law. Together mt and g describe the data-generation from time t to t+ 1 as follows, xt ← g(zt), zt+1 ← mt(zt). (1) If we fix the initial conditions, z0, this data generation process is deterministic. In Section 2.2, we provide results when the underlying mechanism is known and in Section 2.3, we we extend those results to the case when the mechanisms are not known. In Section 3, we extend our results to stochastic mechanisms, m(Zt, U) that take samples from some distribution U ∼ Uniform(0, 1) as input. These stochastic mechanisms can represent any conditional distribution P (Zt+1|Zt) over states.5

heading: 2.2 IDENTIFYING ENCODERS WHEN THE UNDERLYING MECHANISM IS KNOWN
text: We begin in the simplest version of the system described by equation (1): assume that at each time t the same mechanism m : Z → Z is used, and we know this mechanism. From these assumptions we
4for ball collision example, if Z equals position and velocity, we can achieve injectivity by frame stacking. 5For example, if Zt+1|Zt ∼ N (Zt, σ) then m(z, U) = z + σΦ−1(U) where Φ is the cumulative density of a standard Gaussian. Strictly, representing a joint (Zt+1, Zt) as (m(Zt, U), Zt) requires a restriction to nice spaces. See Austin (2015, Lemma 3.1).
can derive an identity that describes how the observations xt and xt+1 are related,
zt+1 = m(zt), g −1(xt+1) = m ◦ g−1(xt), xt+1 = g ◦m ◦ g−1(xt). (2)
It may be helpful to think of this identity as describing an autoencoder where we require that the encoder g−1(xt) inverts the data generating process to produce some latent zt from xt, and that the decoder has to reproduce xt+1 from m(zt); i.e. the representation transformed by the mechanism. Importantly, this identity describes the true data generating process, rather than some model of it. Our hypothesis class over the possible encoder / decoder functions is the set, G, of all bijective functions from Z → X . By assuming that bijectivity we are essentially assuming that the reconstuction task is solved:6 G is the set of all autoencoders that perfectly reproduce the data, such that for any x on the data manifold X , and any encoder / decoder pair (g̃−1, g̃) with g̃ ∈ G, their composition is the identity function, x = g̃ ◦ g̃−1 ◦ x. Because we assumed that the true g is bijective, we know that it is in our search space, G. We can constrain this set using our knowledge of the mechanism by only considering solutions that also satisfy the identity given in equation 2, such that for every pair of observations (xt, xt+1), an analogous identity holds,
xt+1 = g̃ ◦m ◦ g̃−1(xt) (3) Now suppose that we have access to observations xt from the entire set X , then the above identities have to hold for all xt,∈ X with corresponding xt+1 from equation 2, so we can conclude that the following functions are equal, g ◦m ◦ g−1 = g̃ ◦m ◦ g̃−1 (4) This relationship will hold for any of the possible decoders g̃ (and corresponding encoders g̃−1) that are observationally equivalent given our assumptions. We denote the set of all such decoders, Gid = {g̃ | g̃ ∈ G, g ◦m ◦ g−1 = g̃ ◦m ◦ g̃−1}. If Gid = {g} then we have shown that the problem is exactly identified, which means that if we manage to find a g̃ that satisfies equation 2, then g̃ = g; but if Gid, also includes other functions g̃ 6= g, then these functions are the sources of non-identifiability.
Equivariant mechanisms To see an example of a setting where the problem is not exactly identified, consider a mechanism which is equivariant with respect to some bijective transformation a : Z → Z . A mechanism m is said to be equivariant w.r.t a if a ◦ m = m ◦ a. For example, a mechanism derived from Newtonian mechanics may be equivariant with respect to your choice of units of measurement, such that m(cz) = cm(z) for some scaling constant c. Similarly, if a mechanism transforms sets of items, any permutation of z would lead to a corresponding permutation of the mechanism’s output.
If we have a mechanism that is equivariant with respect to some transformation a (where a is not identity map), that implies that there exists a function g̃ 6= g in Gid, so the problem is not exactly identified. We can see this as follows,
g ◦m ◦ g−1 = g ◦ a−1 ◦ a ◦m ◦ g−1 = g ◦ a−1 ◦m ◦ a ◦ g−1 = g̃ ◦m ◦ g̃−1
where the first equality uses the fact that a−1 ◦ a is the identity function, the second applies the definition of equivariance, and the final equality defines g̃ := g ◦ a−1 and g̃−1 := a ◦ g−1. This shows that if the mechanism is equivariant, an encoder, g̃−1, can output a transformed z̃ = a(z), and the decoder, g̃, inverts this transformation before producing its output, thereby leaving the observed variables, x, unchanged. If we denote the set of all equivariances of the mechanism E = {a | a is a bijection, a ◦ m = m ◦ a}, then we can define the set of all such sources of non-identification as, Geq = {g̃ | g̃ = g ◦ a−1, a ∈ E}. This is a natural source of non-identification: given that we are relying on the mechanism to constrain the encoder g̃−1, it is unsurprising we cannot prevent transformations that are not affected by the mechanism. The more interesting observation, which we will show below, is that this set is the only source of non-identification when the mechanism is known, and hence we recover the true z up to equivariances in the mechanism.
To state this theorem, we first define the notion of identifiability up to an equivalence class defined by a family of bijections A, where a ∈ A is a map a : Z → Z . Definition 1. Identifiability up to A. If the learned encoder g̃−1 and the true encoder g−1 are related by some bijection a ∈ A, such that g̃−1 = a ◦ g−1 (or equivalently g̃ = g ◦ a−1), then g̃−1 is said to learn g−1 up to bijections in A. We denote this g̃−1 ∼A g−1.
6This is obviously a strong assumption—learning autoencoders that perfectly reconstructed the data is not at all easy—but it focuses the discussion on the identification issues that remain after reconstruction is solved.
Suppose, for example, A is a family of a permutations. Identifiability up to A implies that the true latent variables will be recovered, but that they would not necessarily be ordered in the same way as they were in the original data generation process. In this setting where the mechanism, m, is known, the following theorem shows that A is just E , the set of equivariances of m. Theorem 1. If the data generation process follows equation 2, the encoders that solve the observation identity in equation 4 identify true encoder g−1 up to equivariances of m (g̃−1 ∼E g−1).
To prove the above theorem, we need to establish that the set of solutions to the identity in equation 4 and the set of maps derived from equivariances are equal Gid = Geq. The proof is given in Section A.1 of the appendix. From Theorem 1, we can derive a number of observations. First, notice that if we have a standard autoencoder7 then the mechanism is the identity map, m(z) = z, and its set of equivariances E is any invertible function a, and hence Theorem 1 shows that the encoder is essentially unconstrained. However, if the mechanism is any non-trivial function, m(z′) 6= z′ for some z′, then the space of possible encoders is significantly reduced to just those invertible transformations that commute with m. If the system involves multiple known mechanisms, {m1, . . . ,mT }, where at each time zt+1 = mt(zt), then the encoder is even further constrained. Define the set of all the mechanisms that are used at least once in the evolution of the system asM∗ = ∪Tt=1{mt}. Suppose E i denotes the equivariances of mi ∈ M∗. Define the equivariances that are shared across all the mechanisms as E∗ = ∩iE i; Corollary 1. If the data generation process follows equation 1, then the encoders that satisfy observation identity in equation 4 for all m ∈M∗ identify true encoder g−1 up to the equivariances shared across all the mechanisms inM∗, E∗ (g̃−1 ∼E∗ g−1).
The proof of the above claim is in Section A.3. This corollary implies a blessing that comes with more complex environments: if an object is transformed by multiple mechanisms which are diverse (in the sense that they share few equivariances), then it becomes easier to identify. Given access to inputs and outputs of a mechanism, if we cannot tell apart whether some transformation was applied to the input or the output, then the mechanism is equivariant with respect to the transformation. Together Theorem 1 and Corollary 1, state that we can learn to invert the data generation process but we cannot distinguish latents that were transformed by equivariances shared across the mechanisms.

heading: 2.2.1 IDENTIFYING ENCODERS FOR AFFINE MECHANISMS
text: Theorem 1 shows us that an encoder g̃−1 is identified up to any equivariances of the known mechanism, but given some mechanism, it does not tell us what equivariances it may exhibit. This section gives an example of how one might go about finding all sources of equivariance for a given mechanism. We derive the equivariances for affine mechanisms, and in doing so we show conditions under which affine mechanisms lead to identification up to some fixed offset. Affine mechanisms are broadly applicable because with a sufficiently short time interval, they approximate a wide variety of physical systems as the Euler discretization of some linear ordinary differential equation. In such systems, the mechanism is given by m(z) = Mzt + bt where M ∈ Rd×d is an invertible diagonalizable matrix (with eigendecomposition given as M = SΛS−1, where S is the matrix of eigenvectors and Λ is a diagonal matrix of eigenvalues), bt ∈ Rd is the offset parameter at time t, and the analog of equation 2 is,
xt+1 = g(Mg −1(xt) + bt).
We search for some encoder g̃−1 such that this relationship holds for all x and t. Define an offset function o(z) = z+ p, where the offset function shifts the latent by a vector p. Define O to be the set of all the offset functions. We show that the encoder is identified up to O when we have at least two distinct offset terms bt and a regularity condition (Assumption 2).8
Assumption 1. In the data generation process in equation 1, we set m(zt) = Mzt + bt, where M is invertible and diagonalizable. We assume that the offset bt takes at least d+ 1 distinct values, which we denote by {b1, · · · , bd+1}. The set {b2 − b1, · · · , bd+1 − b1} of vectors is linearly independent. Assumption 2. a : Z → Z is analytic and satisfies the following assumption. For each component i ∈ {1, · · · , d} of ai(z) and each b ∈ Rd, define the set Sij = {θ | ∇jai(z + b) = ∇jai(z) + ∇2jai(θ)b, z ∈ Rd}. Each set Sij has a non-zero Lebesgue measure in Rd.
7With the constraint that the encoder is the inverse of the decoder such that g̃−1 is bijective. 8We conjecture that the regularity condition holds for all analytic functions and is thus not needed. Since we
do not have a proof of this claim, we include it as an assumption.
Theorem 2. If the data generation process follows equation 1 with affine mechanisms, m(z) = Mzt + bt, Assumptions 1, 2 hold, the eigenvalues of the mechanism M are all distinct, and each component of S−1(bi − bj) is non-zero for some i 6= j, then the encoders that solve the observation identity in equation 4 identify true encoder g−1 up to offsets O such that g̃−1 ∼O g−1.
The proof is given in Section A.4 in the Appendix. The above theorem shows the power of using multiple mechanisms. It can be shown that if there is only one mechanism, then we cannot do better than linear identification. However, if we use two mechanisms as is the case in the above theorem, the constraint of shared equivariances (Theorem 1 and Corollary 1) enforces almost exact identifiability (only offset-based errors remain).

heading: 2.3 IDENTIFYING ENCODERS WHEN THE MECHANISMS ARE NOT KNOWN
text: We have seen in the previous section that with complete knowledge of the mechanisms under which a system evolves, we can learn an encoder up to equivariances. In practice, however, we are unlikely to have such complete knowledge. In this section, the system still evolves according to some deterministic mechanism, zt+1 ← mt(zt), but we assume that you only know some hypothesis class M of possible mechanisms which could have been used, without knowing which mt ∈M is used at every time step.
A candidate solution now needs to propose both an encoder g̃−1 and a mechanism m̃t ∈M for every (xt, xt+1) pair such that, xt+1 = g̃ ◦ m̃t ◦ g̃−1(xt). (5) As before, this relationship holds for all xt ∈ X , where xt+1 is generated from mt, so any candidate solution that is consistent with the x’s that we observe must satisfy
g ◦mt ◦ g−1 = g̃ ◦ m̃t ◦ g̃−1. (6)
We partition the hypothesis class of mechanisms,M = M∗ ∪M′ , into the mechanisms that are used at least once in the evolution of the system,M∗ (M∗ = ∪Tt=1{mt}), and mechanisms which are hypothesized but not used,M′ . We define the set of all decoders g̃ (with corresponding encoders g̃−1) that solve equation 6 across all the time steps as as G̃id = {g̃ | g̃ is a bijection , for each mt ∈ M∗, ∃ m̃t ∈M, such that g ◦mt ◦ g−1 = g̃ ◦ m̃t ◦ g̃−1}. This set looks very much like the set Gid that we defined in Section 2.2, but the fact that we have to select m̃ ∈ M rather than knowing the true m implies a new source of non-identifiability: imitator mechanisms.
Definition 2. Equivariances and imitators w.r.tM. Define a set of functions Ẽ that satisfy commutativity w.r.t the set of mechanisms M in the following sense. The set Ẽ comprises of all the bijections, a(·), that satisfy the following condition. If for each m1 ∈ M∗, ∃ m2 ∈ M such that a ◦m1 = m2 ◦ a, then a ∈ Ẽ .
The set Ẽ consists of two types of elements. We illustrate this through an example of set M = M∗ = {m1,m2}. If a is a bijection that commutes with both m1 and m2, i.e., a ◦m1 = m1 ◦ a and a ◦m2 = m2 ◦ a, then a ∈ Ẽ . From this we can see that Ẽ consists of elements in the intersection of the equivariances of the respective mechanisms. Alternatively, if a satisfies a ◦m1 = m2 ◦ a and a ◦m2 = m1 ◦ a, then we say m2 “imitates” m1 and vice-versa because you can produce m1’s output from m2 for any z using the following relationship m1 = a−1 ◦m2 ◦ a. Further simplifcation of this yields that a2 = a ◦ a is an equivariance of both m1 and m2. This example shows that when we know the list of mechanismsM =M∗ but do not know which mechanism is used, the set Ẽ can be expressed in terms of the equivariances of the mechanisms. For further details see the Appendix Section A.11. Define the set of maps that are identified up to Ẽ as G̃eq = {g̃ | g̃ = g ◦ a−1, a ∈ Ẽ}. Theorem 3. If the data generation process follows equation 1, then the set of all the encoders that satisfy equation 6 identify true encoders g−1 up to equivariances and imitators w.r.t M, Ẽ (g̃−1 ∼Ẽ g−1).
To prove the above theorem, we follow a similar strategy as in Theorem 1 and establish G̃id = G̃eq. The proof of the above is in Section A.5 of the Appendix. Equivariances and imitators play similar roles in the way that they relax constraints on the encoder g̃−1—any bijection that commutes with
either is a source of non-identifiability—but they are different from the perspective of how we should think about designing representation learning algorithms. Recall thatM is composed of two sets of mechanisms,M =M∗ ∪M′ , mechanisms inM∗ that are used at least once in the evolution of the environment and those mechanisms inM′ which are hypothesized but never used. Equivariances are dictated only byM∗, which characterizes the evolution of the environment. Any increases to the number of distinct mechanisms inM∗ will potentially decrease the number of equivariances shared by all mechanisms. This can only be achieved by modifying the environment in some way, either through an explicit intervention that modifies its mechanisms or by collecting data from multiple environments with diverse set of mechanisms. For example, in the bouncing balls example given in Figure 1, one could change the environment by varying the mass of the balls or observing it under different gravity conditions; or one could intervene by, say, changing the shape of balls in the system such that you get a different bouncing mechanism.
Imitators, by contrast, are a function of both the mechanismsM∗ that were used and those that were hypothesized,M′ . An imitator is just some mechanism that can imitate another via some bijection, so one would expect that as we grow the number of mechanisms inM, the size of the set of imitators can only grow; but interestingly, this is not always the case for mechanisms fromM∗. Recall that any a ∈ Ẽ produces an encoder of the form g̃−1 = a ◦ g−1, so the same transformation has to be used for all imitations and equivariances among the mechanisms inM∗. Because of this, it is possible that increasing the size ofM∗ reduces the number of imitators. For example, if there is some mechanism, mi, that does not commute with any non-trivial a in Ẽ (either by imitation or equivariance), then adding mi toM∗ will make the problem exactly identified. On the other hand, growing the size of the set of unused mechanisms,M′ , can result in significant non-identifiability. For example, if M consisted of a flexible class of functions (e.g. a multi-layer perceptron) then it would be easy to construct imitators of the form m1 = a−1 ◦m2 ◦ a. Illustrating Theorem 3. We consider the same setting as in Theorem 2. For each t ∈ {1, · · · , d+1}, m(zt) = Mzt + bt and xt = g(zt). We only know that the mechanism is affine and only the offset bt is changing, but parameters M and bt are not known. Let us construct the set Ẽ corresponding to the above setting. We can show that the set Ẽ consists of affine functions (See the Appendix A.6 for details). From Theorem 3, we can thus conclude that for this data generation process even with very little knowledge of the mechanism, we get linear identifiability. This is weaker than the offset based identifiability in Theorem 2, but there we were required to know the entire affine mechanism.

heading: 3 STOCHASTIC MECHANISMS
text: The results thus far relied on the assumption that the evolution of a system could be described in terms of deterministic mechanisms. This deterministic approach models settings where the full latent state is observable (via some unknown encoder g−1) at a short enough time interval that there is no uncertainty about the system’s evolution. To generalize to cases where there is some uncertainty about the latent state’s evolution, we now develop analogous identification results for stochastic mechanisms that induce conditional distributions over latent states.The systems evolves as
Xt ← g(Zt), Zt+1 ← mt(Zt, Ut), (7) where each Ut is noise with each component sampled independently from standard uniform distribution Uniform[0, 1], Z1 ∼ PZ ,mt : Z×[0, 1]d → Z , and the decoder g : Z → X is a diffeomorphism (i.e. a smooth bijection with an invertible Jacobian, see definition A.1 (Kass & Vos, 2011)).
In this section, we will focus on the case where the true mechanism is unknown; the case where mechanism is known is a special case with no imitator, i.e., m̃t = mt for all t. The goal is to search for an encoder g̃−1, which is a diffeomorphism, that generates X̂t+1 = g̃ ◦ m̃t(g̃−1(xt), Ût), where Ût is a random vector with each component from Uniform[0, 1]. In the deterministic case, we had required that any candidate encoder, g̃−1, was point-wise consistent with the pairs of observations (xt+1, xt). Here, encoders are only required to match the observed conditional distributions. An encoder that is consistent with the observed data can be used to generate X̂t+1 such that the distribution of X̂t+1|Xt = xt matches the distribution of Xt+1|Xt = xt for all xt ∈ X ,
Xt+1|Xt = xt d = X̂t+1|Xt = xt g ◦mt ( g−1(xt), Ut ) d = g̃ ◦ m̃t ( g̃−1(xt), Ût ) (8)
Now, define the set of all candidate decoders g̃ (with corresponding encoders g̃−1) that solve the above equation 8 as Gsid. We can extend the notion of equivariance and imitation to the stochastic case by replacing equality in value by equality in distribution, and show that, as before, these are the only sources of non-identifiability. In the special case where mt is known, Ẽ s, defined below, only contains maps that result from equivariance. We continue to use theM∗ – set of mechanisms that are used at least once in the evolution of the system andM – hypothesis class of all the mechanisms. Definition 3. Equivariance and imitators in distribution w.r.tM. Define a set of functions E s that satisfy commutativity w.r.t the set of distributionsM in the following sense. The set E s comprises all the diffeomorphisms a that satisfy the following condition: a ∈ E s if and only if for each m ∈M∗, ∃ m′ ∈ M such that for all z ∈ Z , a ◦m(z, U) d= m′(a(z), U), where each component of U is sampled independently from Uniform[0, 1] .
Define the set of maps that identify true g up to E s as Gseq = {g̃|g̃ = g ◦ a−1, a ∈ E s} Theorem 4. If the data generation process follows equation 7, then the set of encoders that solve stochastic observation identity equation 8 identify the true g−1 up to the equivariances and imitators in distribution w.r.tM, E s(g̃−1 ∼Es g−1).
To prove the above theorem, we follow a similar strategy as in Theorem 1 and establish Gsid = Gseq. The proof of the above is provided in Section A.7 in the Appendix. Theorem 4 is consistent with the results that we developed for the deterministic case (Theorem 3), but because the mechanism is allowed to be stochastic, it allows us to generalize known results based on distributional assumptions; we give an example of this in the next section.

heading: 4 A MECHANISM-BASED PERSPECTIVE ON EXISTING RESULTS
text: Our primary motivation for understanding how mechanistic knowledge can aid identification, is to develop methods that do not require independence assumptions over the latent variables. However, independence assumptions are not incompatible with the mechanism-based perspective: they simply define a particular kind of mechanism, which then implies identification up to the mechanism’s associated equivariances and imitators. We demonstrate this by re-deriving recent identification results from Klindt et al. (2020) using the mechanisms implied by their respective distributional assumptions. We begin by describing the data generation process used by Klindt et al. (2020) as a stochastic mechanism of the form of equation 7. For each t ∈ {1, · · · , T}
Zt+1 = Zt + Vt, Vt = f(Ut), Ut ∼ Uniform[0, 1]d (9)
where f is an inverse CDF such that each component of Vt ∈ Rd is sampled from the generalized Laplace distribution centred at zero with norm parameter α 6= 2, Z1 ∼ PZ . Next, we want to use Theorem 4 to derive all the solutions to the observation identity in equation 8. Theorem 5. If the data generation process follows equation 9, and PZ and the parameters defining f are known (same assumption as in Klindt et al. (2020)), then the solution to the stochastic observation identity equation 8 leads to identifying the true representations up to permutation, sign-flip and offset.
The proof is given in Section A.8 in the Appendix. The above theorem generalizes Theorem 1 from Klindt et al. (2020) as we do not require α < 2 and rather we work with α 6= 2. Alternatively, analogous results to those in Klindt et al. (2020); Hyvarinen & Morioka (2017) can be derived in settings where we do not know the distribution of Vt but instead assume that we observe Xt often enough that the difference between Zt and Zt+1 is small. In particular, suppose that the data generation process follows equation 9 except each component of Vt is an i.i.d. draw from a nonGaussian with zero mean and |Vt| < δ. Then as δ → 0 the true latent is identified up to permutation, sign-flip and offset. See Section A.9 for details.

heading: 5 RELATED WORKS
text: Non-linear independent component analysis (ICA) is a highly unidentified problem; several works (Hyvärinen & Pajunen, 1999; Locatello et al., 2019) have shown that it is impossible to invert the data generation process without placing restrictions on the data and models. In recent years, a lot of
progress has been made on the problem of non-linear identification. Hyvarinen & Morioka (2016; 2017) provide the first proofs for identification in non-linear ICA. Hyvarinen & Morioka (2016) showed that if the latent variables are mutually independent, with each component evolving in time following a non-stationary time series without temporal dependence, then non-linear identification is possible. Hyvarinen & Morioka (2017) showed that non-linear identification is also possible if the latent variables are mutually independent, with each component evolving in time following a stationary time series with temporal dependence. In Hälvä & Hyvarinen (2020), the authors combine non-stationarity (Hyvarinen & Morioka, 2016) and temporal dependency (Hyvarinen & Morioka, 2017) and extend identifiability guarantees in somewhat more general settings. Khemakhem et al. (2020a); Hyvarinen et al. (2019); Khemakhem et al. (2020b) further generalized the previous results; in these works instead of using time the authors require observation of auxiliary information. Klindt et al. (2020) departs from other non-linear ICA works as it explicitly exploits the sparsity in the transitions of the latent variables (further details on Klindt et al. (2020) can be found in the previous section.). In Zimmermann et al. (2021), the authors show that minimizing contrastive losses commonly used in self-supervised learning can also guarantee identification provided the data (contrastive pairs) follow a specific choice of data generation process (e.g., contrastive pair is generated from a von Mises-Fisher distribution). In another line of work Locatello et al. (2020); Shu et al. (2019), the authors study the role of weak supervision in assisting disetanglement. In a recent work, Gresele et al. (2021), propose to add new form of constraints to non-linear ICA. The constraint is based on the observation that the decoder g that gives rise to the image x is composed of simpler functions that are mutually algorithmically independent; the authors exploit this inductive bias on the structure of g to invert the data generation process. In another recent work von Kügelgen et al. (2021), the authors consider models where the latent variables are divided into two blocks – content and style block, where the latents are not necessarily independent. Using data augmentation on the style latents, the authors show block-wise identification for content block. In Section 4 we argued the existing distributional assumptions could be interpreted as particular choices of stochastic mechanisms; for more details, see Table 1 in the Appendix, where we describe the form of the respective mechanisms. In short, prior work has focused on identification guarantees under assumptions on the dependence between the different random variables, which is in sharp contrast to our approach, which focuses on identification under varying degrees of the knowledge of mechanisms that govern latent dynamics.
Equivariance There is significant recent interest in leveraging equivariance assumptions to design more efficient deep network architectures; for a recent survey, see Bronstein et al. (2021). The general recipe of this line of work is to design functions (deep network architectures) that enforce equivariances. Our setting inverts this recipe, in that we have some known function, m(z), and we are interested in finding all of its equivariances. The relationship between distributions and their equivariances has a long history in the statistics literature (see e.g. Eaton, 1989, and the references therein). Our characterization of stochastic equivariances was inspired by the functional representations given in Bloem-Reddy & Teh (2020). Finally, the importance of group symmetries in representation learning was discussed in Higgins et al. (2018). Higgins et al. focus on the relationship between the symmetries of the environment and a model’s representations, whereas we focus on how symmetries in the environment’s transition function constrain the representation. The two perspectives are complementary, and in future work we hope to unify them.

heading: 6 DISCUSSION AND LIMITATIONS
text: This paper has presented the first systematic study of how mechanisms governing the dynamics of high-level variables can be used to identify these variables from low-level observations, and up to what equivariances, which depend on the mechanisms. We show that this perspective is both powerful—yielding significant constraints in the space of possible representation—and that it generalizes many known approaches. There are, however, a number of open problems that need to be addressed to make this approach practical. First, we have not specified a particular loss function to select g̃; the observation identity immediately implies a reconstruction-based loss, but other losses such as contrastive losses may be more beneficial. Second, there is not yet a general approach to enforcing invertibility while mapping between different sized spaces, so maintaining bijectivity is a challenge. And finally, while we provide a characterization of identifiability when mechanisms are not known, a natural follow-up question is how to use those insights to build methods that allow one to learn both the mechanism and the representation. We are working on a follow-up based on the above directions. In Appendix Section A.12 we share our initial results on 3d identification dataset (Zimmermann et al., 2021)

heading: A APPENDIX

heading: A.1 PROOF OF THEOREM 1
text: Proof. First we show that Gid ⊆ Geq. Consider a g̃ ∈ Gid. For each x ∈ X
g ◦m ◦ g−1(x) = g̃ ◦m ◦ g̃−1(x) g̃−1 ◦ ( g ◦m ◦ g−1(x) ) = g̃−1 ◦ ( g̃ ◦m ◦ g̃−1(x) ) (Compose g̃−1 with both sides)
g̃−1 ◦ ( g ◦m ◦ g−1(x) ) = m ◦ g̃−1(x) (g̃−1 ◦ g̃(z) = z)
Since g is invertible we can substitute x in the above equation with x = g(z) and obtain for each z ∈ Z (
g̃−1 ◦ g ) ◦m ◦ ( g−1 ◦ g(z) ) = m ◦ ( g̃−1 ◦ g(z) ) ( g̃−1 ◦ g ) ◦m(z) = m ◦ ( g̃−1 ◦ g ) (z) (10)
Define g̃−1 ◦ g = a. Observe that a is invertible and from equation 10 we gather that a ∈ E . Also, since g̃ = g ◦ a−1, we can conclude that g̃ ∈ Geq, which proves the first part of the claim. For the second part, we show that Geq ⊆ Gid.
Consider a g̃ ∈ Geq = {g̃ | g̃ = g ◦ a−1, a ∈ E}. By definition, can express g̃ = g ◦ a−1. For each x ∈ X we write
g̃ ◦m ◦ g̃−1(x) = ( g ◦ a−1 ) ◦m ◦ ( g ◦ a−1 )−1 (x)
= ( g ◦ a−1 ) ◦m ◦ ( a ◦ g−1 ) (x)
= ( g ◦ a−1 ) ◦ a ◦m ◦ g−1(x)
= g ◦m ◦ g−1(x)
Observe that g̃ is both a bijection and satisfies the identity in equation 4. Therefore, g̃ ∈ Gid. This proves the second part of the claim. Therefore, Gid = Geq.

heading: A.2 LINEAR MECHANISM M AND LINEAR G.
text: The focus of the main text is on nonlinear identification, but in this section we show how the analysis for general functions g and m applies to the special case when g and m are linear and affine maps respectively. This special case is useful both as a concrete example, and as a stepping stone to
Theorem 2 (nonlinear g with affine m) which will reuse some of the same proof strategies. We write the data generation process as follows.
zt+1 = Mzt + b,
xt = Gzt, (11)
whereM ∈ Rd×d is a diagonalizable matrix describing the mechanism, b ∈ Rd is the offset parameter, G ∈ Rd×d is an invertible matrix determining how the data transforms from latent space to the observable space. We write the eigendecomposition of M as follows M = SΛS−1, where S is the matrix of eigenvectors and Λ is a diagonal matrix of the eigenvalues. On the same lines as the equation 2, we can obtain an identity between xt and xt+1 as follows.
zt+1 = Mzt + b
G−1xt+1 = MG −1xt + b
xt+1 = GMG −1xt +Gb
(12)
If the learner knows M and b, it tries to solve for an invertible G̃ that satisfies
xt+1 = G̃MG̃ −1xt + G̃b (13)
Theorem 6. If the data generation process follows equation 11 and the eigenvalues of the mechanism M are all distinct and each component of the vector S−1b is non-zero, then the only solution to the identity in equation 13 is the true mechanism G.
Proof. We take the difference of the equations 12 and 13 to get the following condition. For each xt ∈ Rd (GMG−1 − G̃MG̃−1)xt + (G− G̃)b = 0 (14) Because, equations 12 and 13 hold for all xt, we can substitute xt = 0 in the above to get
(G− G̃)b = 0 (15)
We plug the above condition in equation 15 back into equation 14 to get the following condition. For each xt ∈ Rd (GMG−1 − G̃MG̃−1)xt = 0 (16) If equation 16 holds for d linearly independent vectors xt ∈ Rd, then we can conclude that,
GMG−1 − G̃MG̃−1 = 0 G−1 ( GMG−1 − G̃MG̃−1 ) = 0
MG−1 −G−1G̃MG̃−1 = 0( MG−1 −G−1G̃MG̃−1 ) G̃ = 0
MG−1G̃ = G−1G̃M (17)
Let A = G−1G̃. We substitute A and the eigendecomposition of M (M = SΛS−1, where Λ = diag(λ1, · · · , λd)) in equation 17 to get
M = AMA−1
SΛS−1 = ASΛS−1A−1 Λ = ( S−1AS ) Λ ( S−1A−1S ) Λ = CΛC−1 (where C = S−1AS)
ΛC = CΛ (18)
We further simplify equation 18 and compare each element of the matrix ΛC and CΛ to get the following condition. For all i, j ∈ {1, · · · , d}
[ΛC]ij = Cijλi, [CΛ]ij = Cijλj
Cij(λi − λj) = 0 (19) Consider the above equation 19 for i 6= j to get
Cij(λi − λj) = 0 =⇒ Cij = 0 (we use the assumption that λi 6= λj) (20) From the above, it follows that C is a diagonal matrix. We obtain an expression for A in terms of C matrix below.
S−1AS = C
A = SCS−1 (21)
From equation 15 we get that
(G− G̃)b = 0 G̃=GA=⇒ (I −A)b = 0 Eqn. (21)=⇒ (I − SCS−1)b = 0 =⇒︸ ︷︷ ︸ Left multiply S−1 S−1b− CS−1b =⇒ (C − I)S−1b = 0 (22)
Since C is a diagonal matrix, we can simplify the above condition further to get (cii−1)(S−1b)i = 0. Since (S−1b)i 6= 0 =⇒ cii = 1, we obtain C = I =⇒ G−1G̃ = I =⇒ G = G̃.

heading: A.3 PROOF OF COROLLARY 1
text: Proof. This proof follows essentially the same strategy as the proof of Theorem 1 with a set of mechanisms,M∗ instead of a single mechanism m; we include it for completeness. First we show that G∗id ⊆ G∗eq. Consider a g̃ ∈ G∗id. For each x ∈ X and for each m ∈M∗
g ◦m ◦ g−1(x) = g̃ ◦m ◦ g̃−1(x), (23) and by following the same steps as the proof of Theorem 1, we can show that,(
g̃−1 ◦ g ) ◦m(z) = m ◦ ( g̃−1 ◦ g ) (z) (24)
As before, define g̃−1 ◦ g = a. Observe that a is invertible and from equation 24 we gather that a ∈ E∗. Also, since g̃ = g ◦ a−1, we can conclude that g̃ ∈ G∗eq, which proves the first part of the claim. In the second part, we need to show that G∗eq ⊆ G∗id.
Consider a g̃ ∈ G∗eq = {g̃ | g̃ = g ◦ a−1, a ∈ E∗}. By definition, can express g̃ = g ◦ a−1. For each x ∈ X and for each m ∈M∗ we write,
g̃ ◦m ◦ g̃−1(x) = ( g ◦ a−1 ) ◦m ◦ ( a ◦ g−1 ) (x) =(
g ◦ a−1 ) ◦ a ◦m ( g−1(x) ) (since a commutes with each m ∈M) =
g ◦m ◦ g−1(x) for all m (25)
Observe that g̃ is both a bijection and satisfies the observation identity in equation 4. Therefore, g̃ ∈ G∗id. This proves the second part of the claim. Therefore, G∗id = G∗eq.

heading: A.4 PROOF OF THEOREM 2
text: Proof. We showed in Theorem 1 that the only source of non-identifiability are the bijections, a, in the set E ; our task here is to explicitly find all of these bijections for affine mechanisms. If a ∈ E , then it satisfies a ◦m = m ◦ a. We replace m with the affine mechanism to obtain the following condition. For each z ∈ Rd
a(Mz + b) = Ma(z) + b (26)
Next, recall that a : Rd → Rd; we take gradient of the function in the LHS and RHS of the above equation 26 separately w.r.t z. Consider the jth component of a(Mz + b) denoted as aj(Mz + b). We first take the gradient of aj(Mz + b) w.r.t z
∇zaj(Mz + b) = (dy dz )T ∇yaj(y), (27)
where y = Mz + b, ∇yaj(y) is the gradient of aj w.r.t y and dydz denotes the Jacobian of y w.r.t z. We simplify the above further to get
∇zaj(Mz + b) = MT∇yaj(y) = MT∇yaj(Mz + b) (28)
We can write the above for each component of a as follows.
[ ∇za1(Mz + b), · · · ,∇zad(Mz + b) ] = [ MT∇ya1(Mz + b), · · · ,MT∇yad(Mz + b) ] = MT[∇ya1(Mz + b), · · · ,∇yad(Mz + b)] = MTJT(Mz + b), (29)
where J(Mz + b) is the Jacobian of a computed at Mz + b. Next, we take the gradient of the jth component of the RHS in equation 26 and let mj denote the jth column of M ,
∇z [ mTj a(z) + bj ] = ∑ i mji∇zai(z) = [ ∇a1(z), · · · ,∇ad(z) ]  mj1 mj2
... mjd  (30) We can write the above for each component in the RHS of equation 26 as follows
[ ∇z [ mT1 a(z)+b1 ] , · · · ,∇z [ mTda(z)+bd ]] = [ ∇a1(z), · · · ,∇ad(z) ]  m11, · · · ,md1 m12, · · · ,md2
... ...
m1d, · · · ,mdd  = JT(z)MT (31)
We equate the gradient of LHS and RHS in equation 26 using the expressions derived in equation 29 and equation 31 to obtain
a(Mz + b) = Ma(z) + b =⇒ MTJT(Mz + b)− JT(z)MT = 0 (32)
We write the same expression at another offset b ′ 6= b below
a(Mz + b ′ ) = Ma(z) + b =⇒ MTJT(Mz + b ′ )− JT(z)MT = 0 (33)
Taking the difference of equation 32 and equation 33 we get MTJT(Mz + b) = MTJT(Mz + b ′ ). Since M is invertible, we get J(Mz + b) = J(Mz + b ′ ). Consider row j of this identity. For each z ∈ Rd
∇aj(Mz+b)−∇aj(Mz+b ′ ) = 0 =⇒ ∇aj(z̃)−∇aj(z̃+b ′ −b) = 0 =⇒  ∇21aj(θ1) ∇22aj(θ2)
... ∇2daj(θd)  (b−b′) = 0 (34)
where ∇2aj is the Hessian of aj and ∇2kaj(θk) corresponds to the kth row of the Hessian matrix. Note that in the above expansion there is a different θk for each row (mean value theorem applied
to each component of ∇aj yields a different point θk on the line joinining z̃ and z̃ + b− b ′ . From Assumption 2 and based on the fact that M is invertible, it follows that∇2kaj(θk)(b− b ′ ) = 0 over a measurable set. Since aj is analytic ∇2kaj(z)(b − b ′ ) is also analytic. Therefore, from (Mityagin, 2015), we can conclude that ∇2kaj(z)(b − b ′ ) = 0 for all z. We can make the same argument for each component k and conclude that ∇2aj(z)(b − b ′ ) = 0. From Assumption 1, it follows that ∇2aj(z)(bj − b1) = 0 for all j ∈ {2, · · · , d + 1} and since the set {b2 − b1, · · · , bd+1 − b1} is linearly independent∇2aj(z) = 0 for all z. This implies a(z) = Az + p. Plug a(z) = Az + p into a(Mz + b) = Ma(z) + b to get
A(Mz + b) + p = MA(z + p) + b =⇒ (AM −MA)z + (A− I)b+ (I −M)p = 0 (35) We write the same expression for offset b ′
A(Mz + b ′ ) + p = MA(z + p) + b ′ =⇒ (AM −MA)z + (A− I)b ′ + (I −M)p = 0 (36)
We take the difference of equation 35 and equation 36 to get
(A− I)(b− b ′ ) = 0 (37)
Substitute z = 0 in equation 35 to get (A− I)b+ (I −M)p = 0 (38)
Substitute the above condition in equation 38 into equation 35 to get the following. For each z (AM −MA)z = 0 (39)
We can now leverage the proofs from the linear setting in Section A.2. The above equation 39 is the same as equation 17 and the equation 37 is the same as equation 22, with b replaced by b− b′ . Following the same analysis as before, we get that latent variables are exactly identified; we show all the steps below for completeness. By choosing d linearly independent z and substituting in equation 39 we get the following,
MA = AM
M = AMA−1,
SΛS−1 = ASΛS−1A−1, Λ = ( S−1AS ) Λ ( S−1A−1S ) ,
Λ = CΛC−1,
ΛC = CΛ,
(40)
where C = S−1AS, M = SΛS−1, Λ = diag ( λ1, · · · , λd ) . We further simplify equation 18
and compare each element of the matrix ΛC and CΛ to get the following condition. For all i, j ∈ {1, · · · , d}
[ΛC]ij = Cijλi, [CΛ]ij = Cijλj Cij(λi − λj) = 0 (41)
Consider the above equation 41 for i 6= j to get Cij(λi − λj) = 0 =⇒ Cij = 0 (we use the assumption that λi 6= λj) (42)
From the above, it follows that C is a diagonal matrix. We obtain an expression for A in terms of C matrix below.
S−1AS = C A = SCS−1 (43)
From equation 37 we get that
(G− G̃)(b− b ′ ) = 0 G̃=GA =⇒ (I −A)(b− b ′ ) = 0 =⇒ (I − SCS−1)b = 0
=⇒︸ ︷︷ ︸ Left multiply S−1 S−1(b− b ′ )− CS−1(b− b ′ ) =⇒ (C − I)S−1(b− b ′ ) = 0 (44)
Since C is a diagonal matrix, we can simplify the above condition further to get (cii − 1)(S−1(b− b ′ ))i = 0. Since (S−1(b−b ′ ))i 6= 0 =⇒ cii = 1, we obtainC = I =⇒ A = I =⇒ a(z) = z+p. This proves that the latents are identified up to an offset.

heading: A.5 PROOF OF THEOREM 3
text: Proof. We first show that G̃id ⊆ G̃eq. Consider a g̃ ∈ G̃id. We rewrite equation 6 below. For all x ∈ X g ◦mt ◦ g−1(x) = g̃ ◦ m̃t ◦ g̃−1(x) (g̃−1 ◦ g) ◦ (mt ◦ g−1(x)) = m̃t ◦ g̃−1(x) (45)
Since g is bijective, we can write x = g(z) to get
(g̃−1 ◦ g) ◦mt(z) = m̃t ◦ g̃−1 ◦ g(z) (46) Since the above equality holds for all z ∈ Z we can conclude that
(g̃−1 ◦ g) ◦mt = m̃t ◦ (g̃−1 ◦ g), a ◦mt = m̃t ◦ a,
(47)
The above conclusion in equation 47 holds for all mt ∈ M∗. Therefore, a in equation 47 and {m̃t}Tt=1 (where m̃t ∈M) together satisfy the condition that for all m ∈M∗, a◦m = m̃◦a, where m̃ ∈M. We can rewrite g̃−1 ◦ g = a as g̃ = g ◦ a−1. From this it follows that g̃ ∈ G̃eq. This proves the first part of the theorem.
Now let us consider the second part of the theorem. Consider a g̃ ∈ G̃eq. We can write g̃ = g ◦ a−1, where a ∈ Ẽ . At time t, some mechanism mt ∈ M∗ is used to transform the latents. Since a ∈ Ẽ , select the mechanism m̃t ∈M for which a ◦mt = m̃t ◦ a and as a consequence g ◦mt ◦ g−1 = g ◦ a−1 ◦ m̃t ◦ a ◦ g−1 = g̃ ◦ m̃t ◦ g̃−1 (48) In the first equality above, we use a ◦mt = m̃t ◦ a and in the second equality we use the definition of g̃. We can repeat the above exercise for all t and corresponding mt using the same a. Therefore, g̃ is in G̃id. This shows the second part of the theorem, i.e., G̃eq ⊆ G̃id.
A.6 LEVERAGING THEOREM 3 WHEN MECHANISM IS LINEAR AND g IS NON-LINEAR
We write the data generation process as follows. For each t ∈ {1, · · · , d+ 1}
zt+1 = Mtzt + bt,
xt = g(zt), (49)
Let us construct the set Ẽ corresponding to the above setting. For each z ∈ Rd,
a(Mz + b) = M ′ a(z) + b̃ =⇒ MTJT(Mz + b)− JT(z)M ′,T = 0,
a(Mz + b ′ ) = M ′ a(z) + b̃ ′ =⇒ MTJT(Mz + b ′ )− JT(z)M ′,T = 0, (50)
where (M, b) and (M, b ′ ) are the true mechanisms and (M ′ , b ′ ) and (M ′, b̃ ′ ) are the imtitating mechanisms chosen by the learner, J is the Jacobian of a. Note here the learner only exploits the knowledge that b changes to b̃, which is why it keeps M ′ fixed and only changes the offset. We take the difference of the RHS in the above two equations to get
MTJT(Mz + b) = MTJT(Mz + b ′ ) (51)
Since M is invertible we get J(Mz + b) − J(Mz + b′) = 0 for all z. We can follow the same justification as was used in equation 33 to conclude that J(z) is constant and a is thus an affine map. We substitue the affine map a(z) = Az + p back into equation 50 to get the following. For all z
AMz +Abj + p = M ′ Az + b ′,j +M ′ p (52)
Substitute z = 0 to get b ′,j = Abj + p−M ′p. Substitute this condition back into the above equation, we get AM = M ′ A =⇒ M ′ = AMA−1.

heading: A.7 PROOF OF THEOREM 4
text: Before stating the proof of Theorem 4, we state two existing results that we use.
Result 1. (Change of variables formula (DeGroot, 2012)) Given a continuous random variable X ∈ Rd with pdf pX and its transformation Y = f(X), where f : Rd → Rd is a diffeomorphism,9 then pY (f(x))|det(Jf (x))| = pX(x), where Jf is the Jacobian of f computed at x. Lemma 1. If X and Y are two continuous random variables that take values in Rd that are equal in distribution, i.e., X d= Y . If f : Rd → Rd is a diffeomorphism, then f(X) d= f(Y ).
Proof. Since X and Y are equal in distribution, they have the same pdfs, i.e. pX(x) = pY (x) for all x ∈ Rd. We can use the change of variables formula in Resut 1 above to get the following. Let W = f(X), pX(f−1(w))|det(Jf−1(w))| = pW (w) and let V = f(Y ), pY (f−1(v))|det(Jf−1(v))| = pV (v). Comparing the two expressions when w = v we get pW (w) = pV (w). This proves the result.
We stated Result 1 and Lemma 1 for continuous random variables. When the random variables are discrete, Lemma 1 holds for any function f . Lemma 2. (Kass & Vos, 2011) If f : Z → Z and g : Z → Z are diffeomorphisms, then f ◦ g is a diffeomorphism.
Proof. We first show that Gsid ⊆ Gseq.
From the observation identity in equation 8 we get that g̃, {m̃t}Tt=1 satisfy the following for all t ∈ {1, · · · , T}
g ◦mt ( g−1(xt), Ut ) d = g̃ ◦ m̃t ( g̃−1(xt), Ût )( g̃−1 ◦ g ) ◦mt ( g−1(xt), Ut ) d = m̃t ( g̃−1(xt), Ût
) (53) In the second step in the above equation, we transformed the random variables in the first step using the same transform g̃−1. g̃−1 is a diffeomorphism; we compose both sides of the first step LHS and RHS with g̃−1. We use Lemma 1 to get from the first step to the second step in the above equation equation 53. In the above equation xt is a fixed value and the only source of randomness is from Ut in LHS and Ût in the RHS. We substitute xt = g(zt) to further simplify the above expression in equation 53
( g̃−1 ◦ g ) ◦mt ( g−1 ◦ g(zt), Ut ) d = m̃t ( g̃−1 ◦ g(zt), Ût ) ( g̃−1 ◦ g ) ◦mt ( zt, ut ) d = m̃t ( g̃−1 ◦ g(zt), Ût
) (54) Substitute a = g̃−1 ◦ g in the above to get the following
a ◦mt ( zt, Ut ) d = m̃t ( a(zt), Ût ) a ◦mt ( zt, Ut ) d = m̃t ( a(zt), Ut
) (55) From Lemma 2 it follows that a in the above is a diffeomorphism. Since we assume that ∪Tt=1{mt} = M∗ it follows that a in equation 47 and {m̃t}Tt=1 (where m̃t ∈M) together satisfy the condition for membership in E s. Since g̃ = g ◦ a−1 we obtain that g̃ ∈ Gseq.
We now show that Gseq ⊆ Gsid. Consider a g̃ ∈ Gseq. We use g̃ = g ◦ a−1, where a ∈ E s to simplify the following random variable
9http://math.mit.edu/˜larsh/teaching/F2007/handouts/changeofvariables. pdf
g ◦mt(g−1(xt), Ut) = ( g ◦ a−1 ◦ a ) ◦mt(g−1(xt), Ut) = g̃ ◦ a ◦mt(g−1(xt), Ut) (56)
Since a ∈ E s we have a ◦mt(g−1(t), Ut ) d = m̃t ( a ◦ g−1(xt), Ut ) From Lemma 2 it follows that g̃ is a diffeomorphism. From Lemma 1 it follows that
g̃ ◦ a ◦mt(g−1(xt), Ut) d = g̃ ◦ m̃t(a ◦ g−1(xt), Ut) = g̃ ◦ m̃t(g̃−1(xt), Ut) (57)
Combining equation 56 and equation 57 and using the fact that Ût d = Ut we get
g ◦mt(g−1(xt), Ut) d = g̃ ◦ m̃t(g̃−1(xt), Ut) d = g̃ ◦ m̃t(g̃−1(xt), Ût) (58)
From the definition of E s it follows with the same choice of a the condition continues to hold for all mt ∈M∗. Therefore, g̃ ∈ Gsid. This proves the second part of the theorem.

heading: A.8 PROOF OF THEOREM 5
text: Proof. In Theorem 4, we showed that all the solutions to the observation identity in equation 8 can be characterized in terms of the equivariances in distribution defined by the set E s. Let us analyze the set E s for the class of mechanisms considered in Klindt et al. (2020). Consider a a ∈ E s. For each z ∈ Rd
a(z + V ) d = a(z) + V̂ , (59)
Define Ŷ = a(z) + V̂ . Since V̂ d= V we write the probability density function (pdf) of Ŷ as
fŶ (y) = fV (y − a(z)) (60)
Define Y = a(z + V ). a : Rd → Rd is a diffeomorphism. We use the change of variables result (Result 1) to write the pdf Y as follows. For each y ∈ Rd
fY (y) = 1∣∣∣det(J(a−1(y)))∣∣∣fV
( a−1(y)− z ) , (61)
where J(a−1(y)) is the Jacobian of a computed at a−1(y), and det is the determinant.
We substitute equation 60 and equation 61 in the equivariance condition in equation 59 to obtain the following. For each y ∈ Rd
Y d = Ŷ
fV (y − a(z)) = fV (a −1(y)− z) |det(J(a−1(y)))|
fV (a(w)− a(z)) = fV (w − z) |det(J(w))| ,
(62)
where w = a−1(y). In the above we equated the conditionals for each z, we now equate the marginals.
g ◦ (Z + V ) d= g̃ ◦ (Ẑ + V̂ )
a ◦ (Z + V ) d= Ẑ + V̂ (63)
We follow Klindt et al. (2020) and assume Ẑ d= Z and V̂ d= V . Therefore, Z + V d= Ẑ + V̂ . We use this condition to restate equation 63 as
a ◦ (Z + V ) d= Z + V =⇒ a(W ) d= W, (64) where W = Z + V . We translate equation 64 into the condition on the pdfs as follows. For each w ∈ Rd
fW (w)|det(J(w))| = fW (w) =⇒ |det(J(w))| = 1 (65)
Substituting the above equation equation 65 into equation 62 we get
fV (a(w)− a(z)) = fV (w − z) |det(J(w))| =⇒ fV (a(w)− a(z)) = fV (w − z)
‖a(w)− a(z)‖α = ‖w − z‖α, (66)
where in the last condition in the above expression we exploit the fact that fV is a generalized Laplacian distribution. From Mazur-Ulam theorem Nica (2013) it follows that a is affine. We now write a as a matrix A with offset vector q and simplify the condition in equation 59.
For each z ∈ Rd we have A(z + V ) + q d = Az + V̂ + q
=⇒ AV d= V̂ =⇒ E[AV V TAT] = E[V̂ V̂ T] =⇒ AAT = I
(67)
Since A is a square matrix and AAT it follows that ATA = I. Therefore, A is an orthonormal matrix. Observe that all the elements of V̂ are independent. Since AV d= V̂ it follows that all the elements of AV are also independent. Define AV = Q. Observe that A is an orthonormal matrix that is multiplied with a vector V with all independent elements (each of which is non-Gaussian as α 6= 2) and outputs a vector that has all independent components. From Theorem 11 in Comon (1994) we get that A is a composition of permutation and scaling. Since A is also orthonormal, each term in the diagonal scaling matrix can only be 1 or −1. Therefore, A = ΠΛ, where Π is a permutation matrix and Λ is a diagonal matrix with +1,−1 elements. Finally, a(z) = ΠΛz + q.

heading: A.9 ALTERNATIVE IDENTIFICATION RESULT FOR SMALL TRANSITIONS
text: In this section, we analyze time series models similar to one in Hyvarinen & Morioka (2017) under the condition that the transitions are small in magnitude to arrive at permutation and scaling based identification. Let us analyze the set E s for this class of mechanisms. We assume that the learner knows that the mechanism is additive, and that the noise components are all independent. In the analysis below we consider bijections that are analytic (each component of the bijection is an analytic function). Consider an a ∈ E s
a(z + V ) d = a(z) + V̂ . (68)
We write the first-order approximation of the above identity below
a(z) + J(z)V d = a(z) + V̂
J(z)V d = V̂
(69)
where V d
6= V̂ . Note that the set of solutions a to equation 68 and equation 69 become equal in the limit of δ → 0, where δ is the bound on each component of |V |. We analyze the solution to equation 69 below.
E[(J(z)V )(J(z)V )T] = J(z)E[V V T]J(z)T = σ2J(z)J(z)T
σ2E[V̂ V̂ T] = σ2I σ2J(z)J(z)T = σ2I =⇒ J(z)J(z)T = I =⇒ J(z)TJ(z) = I
(70)
Since J(z)V d= V̂ and each component of V̂ is independent, we can deduce that all the components of J(z)V are independent as well. From Theorem 11 in Comon (1994), we can deduce that J(z) is composed of permutation times a diagonal matrix. Since the matrix is orthonormal, each scaling component can only be±1. We can apply this same analysis at another point z̃ in the neighborhood of z and continue to find that the jacobian matrix is a permutation times diagonal matrix (that describes sign flips). Note that the permutation matrix times scaling used to express the Jacobian cannot change between the points z̃ and z (if it does change then that violates the Jacobian’s continuity). Since the Jacobian is equal to a fixed permutation times a fixed scaling matrix over a neighborhood, we can extend this to the entire space (here we use the fact that the a is analytic and Mityagin (2015)). As a result, a is of the form ΠΛz + q, where Π is a permutation matrix, Λ is a diagonal matrix.

heading: A.10 ANALYZING AUXILIARY INFORMATION MODELS
text: We now discuss how our machinery can be used in models when auxiliary information is available (Khemakhem et al. (2020a)) to arrive at permutation and scaling based identification. We define the data generation process compatible with Khemakhem et al. (2020a). Suppose the latent Z is generated from a mechanism m : O× [0, 1]d that takes as input some observed auxiliary information O and uniform independent noise vector U ∈ [0, 1]d:
Z ← m(O,U), X ← g(Z), (71)
where g : Z → X is a bijection. Suppose the learner knows the mechanism. The learner selects g̃ and outputs X̂ = g̃ ◦m(o, Ũ), where Ũ is a random vector with each component sampled independently from Uniform[0, 1]. The learner’s goal is to match
X̂|O = o d= X|O = o g ◦m(o, U) d= g̃ ◦m(o, Ũ). (72)
for all possible observations o ∈ O. Define the set of solutions to equation equation 72 as Goid. Consider bijection a s.t. the following identity holds for all o ∈ O
a ◦m(o, U) d= m(o, Ũ) (73)
Define the set of all bijections a that satisfy the condition in equation equation 73 as Eoeq. The set Eoeq consists of intersection of measure preserving transformations of Z|O = o. Define the set of g̃ that are identifiable up to Eoeq as Goeq = {g̃ | g̃ = g ◦ a−1, a ∈ Eoeq}. Theorem 7. If the data is generated as described in equation 71, then the set of solutions to the identity in equation 72 identify true g up to intersection of all the measure preserving maps in Eoeq (g̃−1 ∼Eoeq g −1)
Proof. Consider a g̃ ∈ Goid.
g ◦m(o, U) d= g̃ ◦m(o, Ũ)
g̃−1 ◦ g ◦m(o, U) d= m(o, ũ)
a ◦m(o, U) d= m(o, Ũ)
(74)
From the above it follows that g̃ ∈ Goeq. Consider a g̃ ∈ Goeq.
g ◦m(o, U) = g ◦ a−1 ◦ a ◦m(o, U) d= g̃ ◦ m(o, Ũ) (75)
From the above it follows that g̃ ∈ Goid. This completes the proof.
Let us consider additive mechanisms of the form m(o, U) = m̄(o) + U , where U has independent components. Suppose the learner knows that the mechanism is additive and the noise has independent
components. The learner solves the following identity.
g ◦ (m̄(o) + U) d= g̃ ◦ (m̄ ′ (o) + Ũ)
g̃−1 ◦ g(m̄(o) + U) d= m̄ ′ (o) + Ũ
a(m̄(o) + U) d = m̄ ′ (o) + Ũ
(76)
Suppose that the absolute value of each component of U is really small and bounded by δ. We can use the first-order Taylor expansion and obtain
a(m̄(o)) + J(m̄(o))U d = m̄ ′ (o) + Ũ , (77)
where J is the Jacobian of a. Suppose the noise has zero mean. Take the expectation w.r.t. U and Ũ on the two sides respectively to get a(m̄(o)) = m̄ ′ (o). Substitute this back into the equation we
get that J(m̄(o))U d= Ũ . We can now follow the analysis that we carried out after equation 69 and conclude that a is equal to permutation times a scaling matrix along with some offset.
A.11 ANALYZING Ẽ WHENM =M∗
In this section, we analyze imitators when we know the set of mechanisms that are deployed, we do not know which mechanism is used when. If a ∈ Ẽ andM =M∗. From the definition of a, it follows that for each m ∈ M∗, ∃ m′ ∈ M∗ such that a ◦m = m′ ◦ a. We claim that two distinct m ∈M∗ cannot share the same m′ (imitator). Suppose there was a common m′ imitating m and m̃.
a ◦m = m ′ ◦ a
a ◦ m̃ = m ′ ◦ a
(78)
We take the difference of the above two equations to get a ◦m = a ◦ m̃ (79)
Since a is a bijection, we can conclude that m = m̃, which is a contradiction of the fact that m and m̃ are distinct.
This claim implies that for a given a there is an injective map fromM∗ toM∗. If the setM∗ is finite, then from Pigeonhole principle it follows that this injective map is a bijection.
Let us index the mechanismM∗ = {m1, · · · ,mn}. We call the bijection map π :M∗ →M∗
Consider the element i. We claim ∃ l ∈ {1, · · · , n} πl(i) = i. We write the chain starting from i as i→ π(i)→ π2(i), · · · , πk(i). Since the chain (π(i)→ π2(i), · · · , πk(i)) has n steps there have to be at least two elements that are equal. Suppose p > q and πp(i) = πq(i)
πp(i) = πq(i) =⇒ πp−1(i) = πq−1(i) =⇒ · · · ..πp−q(i) = i (80) In the above at each step we use the fact that π is a bijection and that shows the claim that πl(i) = i. We now use this observation to carry out the following simplification
mi = a−1 ◦mπ(i) ◦ a
mπ(i) = a−1 ◦mπ 2(i) ◦ a
...
mπ k(i) = a−1 ◦mi ◦ a
(81)
Substituting the second equation mπ(i) into first, and then the third mπ 2(i) and so on we get
mi = a−k ◦mi ◦ ak (82)
Therefore, for each mi, ∃ k such that ak is its equivariance.
To summarize, if a ∈ Ẽ andM =M∗, whereM is a finite set, then for each mechanism m ∈M, ∃k ∈ {1, · · · , |M|} such that ak is its equivariance.

heading: A.12 TRANSLATING IDENTITY INTO LOSS FUNCTIONS AND PRELIMINARY EXPERIMENTS
text: We describe two natural loss choices that fall out based on the identity that we want to solve g̃ ◦m ◦ g̃−1(xt) = xt+1.
• Autoencoder based loss. The identity above immediately implies an autoencoder-style algorithm where one minimizes a reconstruction loss of the form
min g̃∈H,h̃∈H,m̃∈M ∑ t E [ ‖Xt+1 − g̃ ◦ m̃ ◦ h̃(Xt)‖2 ] (83)
whereH is the hypothesis class of functions for g̃ andM is the hypothesis class of mechanisms.
• Contrastive loss. Alternatively, one could re-write the observation identity as g−1 ◦xt+1 = m ◦ g−1 ◦ xt and use a contrastive loss as follows
min g̃ ∑ t E [ − log ( g̃(Xt+1)Tm̃g̃(Xt) g̃(Xt+1)Tm̃g̃(Xt) + ∑ τ g̃(Xτ ) Tm̃g̃(Xt) )] (84)
where τ represents other time instances, i.e., τ 6= t+ 1. The positive pair in the contrastive loss is formed by the adjacent time instances and the negative pair is formed by non-adjacent time instances. Identifying which of these two losses works better in practice is an important empirical question. Note how in both the losses above, we have explicitly not enforced invertibility for the learned g.
We present our initial experiments on 3dIdent dataset from [Zimmerman et al. 2021], using the contrastive loss described above. With contrastive pairs generated by a (fixed) random orthogonal matrix U applied to the latents, we obtain the following values for linear disentanglement score (R2 of the predictions of the true representation using a linear model). We report median scores over 10 seeds.
• Standard contrastive learning. Linear disentanglement score of 0.29 • Contrastive leveraging with exact mechanism knowledge. Leveraging the true U as the
mechanism in the contrastive loss achieves a median score of 0.76. • Contrastive leveraging with some knowledge of mechanism If we use a random orthog-
onal matrix Ũ 6= U , that achieves a median score of 0.64. The random matrix can be interpreted as sampling a random m from the hypothesis classM; it seems likely that better results are possible by optimizing overM.

Review summaries:
This work gives several identifiability results for representation learning from sequences of observed variables when the mechanism governing the underlying latent variables is known, and the observation renderer is bijective. The identifiability of an inverse renderer is shown to depend only upon the equivariances of the mechanism(s) governing the evolution of the underlying latent variables. Extensions are given to the case of a known mechanism class and to stochastic mechanisms.   

The paper uses the knowledge of generating mechanisms to identify latent representation for given data. It contributes to the question of identifiability in unsupervised learning. It relaxes the knowledge of generating mechanism to unknown mechanism, and also from deterministic mechanism to probabilistic mechanism. 

**Scope.** The paper studies unsupervised/weakly-supervised representation learning from an identifiability perspective. The considered problem setting is that observations $x_t$ are generated from some bijective function $g$ applied to latent codes $z_t$, $x_t=g(z_t)$; and that we have access to successive observations $..., x_t, x_{t+1}, ...$ which are related through shared *mechanisms* $m_t$ dictating the dynamics in the latent space, $z_{t+1}=m_t(z_t)$. The paper then provides a (purely) theoretical analysis regarding the identifiability of $g$ given (partial) knowledge of the mechanisms $m_t$. In particular, the identifiability class of $g$ is derived in terms of *equivariances* of the mechanisms.  **Results.** For the case of a single known mechanism $m$, it is shown that $g$ can be recovered only up to equivariances of $m$, i.e., up to bijections $a$ that commute with $m$, meaning that any learnt function $g'$ relates to the true $g$ via $g'=g\circ a$ for some $a$. This result is strengthened when multiple distinct known mechanisms govern the dynamics, where identifiability is obtained up to shared equivariances, i.e., such $a$ that commute with all $m_t$. When the relevant mechanisms are not known, non-identifiability issues increase with the size of the hypothesis class which is attributed to the presence of so-called *imitators*, transformations that give rise to the same behaviour as some mechanism when combined with another mechanism. Finally, a result is presented for the case of stochastic mechanisms which give rise to conditional transition distributions $p(z_{t+1}|z_t)$: here, equivariance and imitation are relaxed to hold only in distribution. The insights are used to re-derive a known identifiability result by Klindt et al. (2020).