Properties from mechanisms: an equivariance perspective on identifiable representation learning
Authors: Kartik Ahuja
Jason Hartford
Yoshua Bengio
Venue: ICLR 2022 Spotlight (2022)
Keywords: representation learning
equivariance
independent component analysis
ICA
autoencoders

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 mechanism-based 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.

Published as a conference paper at ICLR 2022
PROPERTIES FROM MECHANISMS:
AN EQUIVARIANCE PERSPECTIVE ON IDENTIFIABLE REPRESENTATION LEARNING
Kartik Ahuja", Jason Hartford'& Yoshua Bengio
Mila Quebec AI Institute, Université de Montréal
Quebec, Canada
[kartik. ahuja, jason. hart Ford, oogga quebec
ABSTRACT
A key goal of unsupervised representation learning "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 set of possible mechanisms. In particular, prove that if we know the exact mechanisms under which the latent properties evolve, then identification underlying mechanisms. We generalize this characterization to settings where we only know some hypothesis class over possible mechanisms, as well settings where the mechanisms are stochastic. We demonstrate the power of this mechanism- based 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.
be achieved up to any equivariances that are shared by the
INTRODUCTION
Modern unsupervised 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 (Schölkopf et al., 2021; Locatello et al., 2019). At the same time, the success pre-trained transformers (Radford et al., 10 Brown al., 2020) shows that advances in our ability to extract latent representations can lead to dramatic improvements in the sample complexity of downstream 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 into its underlying generative factors. This is a challenging task because unsupervised representation learning with independent and identically distributed data is hopelessly unidentified: even in the nice case in which observations, x, are generated with independent latent variables, p(z) II. p(2:), there exists an infinitely many distributions with independent latents p(z) that are consistent with the observed marginal distribution, p(z), and only one of them corresponds to the true latent distribution p(z) (Locatello et al., 2019; Khemakhem et al., 2020a).
If we want to build systems which are able to provably identify the true generative factors 2 that generated our observed data structural assumptions that constrain this set of possible distributions. Most of the prior work that can provide such guarantees was developed the independent component analysis (ICA) literature. The key ICA assumption is that the latent factors are (conditionally) independent and non-Gaussian. Then, the observation model, Z + X' is linear and invertible, 2 = =g (xx is identified (Comon,
g(x) for some observation model g. then we need to exploit
"cqual contribution, author order selected randomly.
A problem is identified if the generative factors are unique solution the infinite data limit.

---

Published as a conference paper at ICLR 2022
(2)
my(3s)
Latent representaaeen toaionniiaio Mecherism
Encooer
Decoder
8 (x))
g(4))
(x2)
k(t2
(1g)
8(3
8: mm (2)) =X
(1g)
8 my (x,)
Obeervation
X1
Idantity
12 (2x) #
35
Figure I: This simple data generating process illustrates that if we know the set of mechanisms that govern the evolution of an environment, this constrains the set of possible representations to any cquivariances of these mechanisms. At each time step. we observe an environment of bouncing balls in pixel space as images, 2₁. These images are produced by some rendering engine, 9, as a function of the true latent representation 2t. which in this case gives positions and velocities of each ball (illustrated by the location and length of the arrows in the latent representation). At each time step, the state evolves according to a mechanism, my. Any candidate model that is consistent with the observed data has to satisfy the observation identity. If encoder produces either the true representation (shown in green), or a representation transformed by some equivariance of the mechanism (e.g. the blue rotated representation) then the observation identity is satisfied. However, models that produce representations that are arbitrary transformations of the true representation (c.g. the pink warped representation) can be discarded as they consistent with the observation identity.
1994), and for nonlinear g there are number of recent approaches that leverage non-stationarity in the distributions over to identify g (Hyvarinen & Morioka, 2016; 2017; Hyvarinen et al., 2019; Khemakhem et al., 2020a). These results give tantalizing demonstration that representation learning with identification guarantees is possible, but the requirement that the latent factors are statistically (conditionally) independent is limiting² (Higgins et al., 2018; Schölkopf et al., 2021).
In this paper take very different approach. We study how the mechanisms that govern an environment's 's evolution constrain the set of possible latent representations that are consistent with the data. As simple concrete example, consider the bouncing ball environment shown in Figure 1. The latent state can be completely described by a vector, 2, containing the position, velocity and acceleration of the balls?, and given this latent state, the images, I, shown in Figure 1, are produced via some rendering engine Z + X. Our task is to leverage sequences of observations ......... TT and knowledge of m recover 2 ....... Zr. 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 any equivariances of the mechanism; or equivalently, in Section 2.2 we prove that we can identify up to any invertible transformation a : Z > Z that commutes with m, such that the composition moa = 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-channgine from representing in meters to inches leaves the output of the mechanism unchanged up to corresponding unit change- and hence we can only hope to identify 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 iinditiiiiibbiit are even further constrained: such a system is identified up equivariances that are shared by all mechanisms.
As 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 halls have the momentum, then mass and velocity will he inversely correlated.
A complete generative model of these images would also need to track the colors and shapes of the elements; will return this issue in the discussion of the results.
2

---

Published as a conference paper at ICLR 2022
Perfectly knowing the true mechanisms and when they applied is unlikely, but in Section 2.3 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 source of non-identifaability: the mechanisms in our hypothesis class can imitate each other if there exists an invertible transformation such that for any two mechanisms my and m2 in our hypothesis class, m2 = a my o a. For example, if we are in a setting where our hypothesis class includes both a product mechanism, m (2) = II 24, and sum mechanism, m2(2) = - 2i, then my can imitate m2 if (()) = exp(z), since Σ; 2 = [Il exp(z;)). As before, this result is complete, in the sense that these two sources of non-identifiability equivariance and imitation are the only sources of ron-identifiability in such systems. This gives us natural way of thinking about the way knowledge of deterministic mechanisms constrains representation learning task: with complete knowledge, the only source of ron-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, larger hypothesis class can lead to fewer imitations.
Section 3, shows that we can derive analogous results for stochastic mechanisms, m2 U). where the mechanism defines a conditional distribution p(=++1 [z) 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 pachanism-basse perspective on the related work in Section 5 and Section 6 concludes with discussion of the open problems that need to be addressed in order to reliably leverage this approach in practice.
2
MECHANISM BASED IDENTIFICATION
2.1 DATA GENERATION PROCESS
The state of the system time E f1...., T) is given by 2, E Z C Rd. At each time t. we observe g(&,) = 2, E X C R", which is some transformation of the latent 2,. We can think of : 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 is injective with respect to i...... g(x)) the underlying state, 2, is reflected in some pixel-level change to the observation x and we make bijective by restricting its inverse g=1 to any
g(2)) implies 21 22: equivalently, any change to
the data manifold which we denote X' (i.e. X' is the image of g). The state transition from time / to / + is governed by mechanism m,, Z + Z. There may be multiple mechanisms in given environment. For example in Figure 1 the transition from 21 to zg does not involve any collisions so the state evolves according to Newton's 's first law of motion (Newton, 1687); the transition from 22 to 23 involves a collision between two of the balls that is described by Newton's 's third law. Together me and g describe the data duta-generation from time to
t 2.+ as follows.
(1) If we fix the initial conditions, 2o. 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(Z,, U') that take samples from some distribution U ~ Uniform(O, 1) as input. These stochastic mechanisms can represent any conditional distribution P(Z (Austin (2015, Lemma 3.1))
It + (Z)),
2++1 +- mz())).
2.2 IDENTIFYING ENCODERS WHEN THE UNDERLYING MECHANISM IS KNOWN
We begin in the simplest version of the system described by equation (1): assume that at each time t the same mechanism m ZZ- + Z is used, and we know this mechanism. From these assumptions we
for hall collision example, if 7. equals position and velocity, we can achieve injectivity by frame stacking.
3

---

Published as a conference paper at ICLR 2022
can derive an identity that describes how the observations 2, and 1++1 related,
1 m(()), 9 (1241) = g (Jte) Ie+1 g o m o -
(2)
may be helpful think of this identity as describing an autoencoder where we require that the encoder 1 (xxx) inverts the data generating process to produce some latent from Ft, and that the decoder has to reproduce It+1 from m= ); 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:² 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 (9 3-- .) with 9 G. their composition is the identity function, x = 9 o 9 o x. Because we assumed that the true g is bijective, we know that 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 (Ie, 2141), an analogous identity holds,
T++1 = 9 m m (xz)
(3)
Now suppose that we have access to observations xe from the entire set X, then the above identities have to hold for all Te; E X' with corresponding Ft+1 from equation 2, so we can conclude that the following functions are equal,
g o m o = go m mog
(4)
This relationship will hold for any of the possible decoders I (and corresponding encoders 5 g- that are observationally equivalent given our assumptions. We denote the set of all such decoders, 9 m e ". If Gia = {9} then we have shown that the problem is
Gia =( ğ E G. o m exactly identified, which means that if we manage to find a 9 that satisfies equation 2, then 9 = g: but if Gia, also includes other functions ğ # 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 iden- tified, consider a mechanism which is equivariant with respect some bijective transformation a 2 + 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 mechanies may be equivariant with respect to your choice of units of measurement, such that m(cz) = cm(2) for some scaling constant c. Similarly, if a mechanism transforms sets of items, any permutation of would lead to a corresponding permutation of the mechanism's 's output.
If we have a mechanism that is equivariant with respect to some transformation a (where is not identity map), that implies that there exists a function ğ f in Gia. so the problem is not exactly identified. We can see this as follows,
g o nomog o = -ooc-oooooop
go a moaog = ğ o m o g-
where the first equality uses the fact that a- a is the identity function, the second applies the definition of equivariance, and the final equality defines ğ == -gg o a and g- == a g This shows that if the mechanism is equivariant, an encoder, g can output a transformed ă = a(2). and the decoder, g. inverts this transformation before producing its output, thereby leaving the unchanged. If we denote the set of all equivariances of the mechanism {a a is a bijection, non-identification as, Goq (ō given that we are relying on the mechanism to constrain the encoder ğ 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 hon-identification when the mechanism known, and hence we recover the true z up to equivariances in the mechanism.
observed variables,
o m m o a), then we can define the set of all such sources of a-
EJ. This is natural source of non-identification:
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 E
a map a : 2 + Z.
Definition 1. Identifiability up to A. If the learned encoder g-1 and the true encoder g are related by some bijection a E A, such that g = a g (or equivalently ğ = o a -1, then ğ is said to learn g up to bijections in A. We denote this 9 ~ 9
*This is obviously strong aosumption-leamiiie autoencnders that perfectly reconstructed the data is not all bus focuses the discussion on the identification issues that remain after reconstruction is solved.
4

---

Published as a conference paper at ICLR 2022
Suppose, for example, A is family of 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 &, 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 y up to equivariances of m (ğ- ~e )ー
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 Gi = Geg. 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 autoencoder then the mechanism is the identity map, mn()) = 2, and its set of cquivariances E is any invertible function a, and hence Theorem I shows that the encoder essentially unconstrained. However, if the mechanism is any non-trivial function, m(=') of x for some x', 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, {mi...., mer }. where at each time 1 = (=x). 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 as M = U [m,]. J. Suppose El denotes the equivariances of m, E MM.. Define the equivariances that are shared across all the mechanisms ex N,E::
Corollary 1. If the data generation process follows equation 1, then the encoders that satisfy observation identity in equation for all m MM" identify true encoder 9 up to the equivariances shared across all the mechanisms in M E" (g ~g. 9
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 casier 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 and Corollary I, 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.
2.2.1 IDENTIFYING ENCODERS FOR AFFINE MECHANISMS
Theorem I shows that an encoder ğ 1 is identified up to any equivariances of the known mechanism, but given some mechanism, it does not tell us what equivariances may exhibit. This section gives an example of how might go about finding all sources of equivariance for given mechanism. We derive the equivariances for affine mechanisms, and in doing so we show conditions under which broadly
affine mechanisms lead to identification up to some fixed offset. Affine mechanisms 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²)) = Ma, + b, where M E IRddd is an invertible diagonalizable matrix (with eigendecomposition given as M = SAS-1, where S is the matrix of eigenvectors and A is a diagonal matrix of eigenvalues), b, E Id is the offset parameter at time t, and the analog of equation 2 is,
T1+1 = g ((Mg (2:) + b,).
We search for some encoder g-1 such that this relationship holds for all x and Define an offset function o(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 O when have at least two distinct offset terms be and a regularity condition (Assumption 2)."
A Assumption 1. In the data generation process in equation 1, we set m((2)) M + bb, where M is invertible and diagonalizable. We assume that the offset by takes at least d + 1 distinct values. which we denote by {b', ..... bdd+1. The set {b² -b'_--.-- -b!.... .bt..+++ bd++1 - b') of vectors linearly independent. Assumption 2. a Z + Z is analytic and satisfies the following assumption. For each component i E (1..... .d} of (2) and each b E Rdd. define the set St = (0 V,a,(z +2 = V (2) 73,, 2 e ). Each set Sij has a non-zero Lebesgue measure in 12d.
6 With the constraint that the encoder is the inverse of the decoder such that ğ bijective. 7 We conjecture that the regularity condition holds for all analytic functions and is thus not needed. Since we do not have proof of this claim, we include it an assumption.
5

---

Published as a conference paper at ICLR 2022
Theorem 2. If the data generation process follows equation 1 with affine mechanisms, m(z) M2, + by Assumptions 1, hold, the eigenvalues of the mechanism M are all distinct, and each component of S (b' - bb) is non-zero for some i * j. then the encoders that solve the observation identity in equation 4 identify true encoder g-1 up to offsets O such that g ~o g=1
The proof given in Section A.4 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).
2.3 IDENTIFYING ENCODERS WHEN THE MECHANISMS ARE NOT KNOWN
We have seen in the previous section that with complete knowledge the mechanisms under which a system evolves, can learn 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, 2++1 m2)))), but we assume that you only know some hypothesis class M of possible mechanisms which could have been used, without knowing which m, E .M is used at every time step.
A candidate solution now needs to propose both an encoder g and a mechanism mn E M for every (Iz, It41) pair such that,
r++1 = ÿ o m, og (2t))
As before, this relationship holds for all xy X, where #++1 is generated from me, so any candidate solution that is consistent with the x's that we observe must satisfy
g o me o g = 9 m4 og
(6)
We partition the hypothesis class of mechanisms, M = =M U M', into the mechanisms that are used at least once the evolution of the system, M (M- 1 and mechanisms which are hypothesized but not used, .M'. We define the set of all decoders 9 (with corresponding encoders g gー1) that solve equation across all the time steps as as Gi = {ō ğ is a bijection, for each m, e M 3 m, E M,, such that g o my og g ğ o my o g }.. This set looks very much like the set Gi that we defined in Section 2.2, but the fact that we have to select n E M rather than knowing the true m implies a new source of non-identifiability: imitator mechanisms.
Definition 2. Equivariances and imitators w.r.t M. Define a set of functions E that satisfy com- mutativity w.t. the set of mechanisms M in the following sense. The set & comprises of all the bijections, a(-), that satisfy the following condition. If for each mi E MM, 3 m2 E .M such that m2 m2 a, then E.
The set E consists of two types of elements. We illustrate this through an example of set M M = [m² mm². If a a bijection that commutes with both m² and m², i.e. a m m o a and a m= = m² o a, then a E E. From this we can see that & consists of elements in the intersection of the equivariances of the respective mechanisms. Alternatively, if satisfies a mi m2 and a o m2 = m2 o a, then we say m2 "imitates" mi and vice-versa because you can produce mi 's output from m2 for any z using the following relationship my a -1 m2 Further simplifcation of this yields that a² = a o a is an equivariance of both wi and m2. This example shows that when we know the list of mechanisms M = =M but do not know which mechanism is used, the set & can be expressed in terms of the equivariances of the mechanisms. For further details see the Appendix Section 1. Define the set of maps that are identified up E as Gen (ā g = goat 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 up equivariances and imitators w.r. M, E (ğ ~g g 11)
To prove the above theorem, follow similar strategy as in Theorem I and establish Gia Geq. 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 --1- any bijection that commutes with

---

Published as a conference paper at ICLR 2022
either is a source of non non-identifiability but they are different from the perspective of how should think about designing representation learning algorithms. Recall that M is composed of two sets of mechanisms, M = MM UM,, mechanisms in M that are used at least once in the evolution of the environment and those mechanisms in .M' which are hypothesized but never used. Equivariances dictated only by M which characterizes the evolution of the environment. Any increases to the number of distinct mechanisms in MM 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 function of both the mechanisms MM 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 in M. the size of the set of imitators can only grow; but interestingly, this is not always the case for mechanisms from M Recall that any & produces encoder of the form g a 9 for all imitations and equivariances among the mechanisms in M Because of this, it is possible that increasing the size of M reduces the number of imitators. For example, if there is some mechanism, m,, that does not commute with any non-trivial a in & (either by imitation or equivariance), then adding m, to MM will make the problem exactly identified. On the other hand, growing the size of the set of unused mechanisms, MM' can result in significant non-identifiability. For example, if M consisted of flexible class of functions (e.g. a multi-layer perceptron) then it would be easy to construct imitators of the form m1 = a o m2 o a.
the same transformation has to be used
For each E {1.-.. d+ 1}, m(=)) Mz, + by and z; 9(2x). We only know that the mechanism is affine and only the offset b, is changing, but parameters M and b, are not known. Let us construct the set & corresponding to the above setting. We can show that the set ε 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.
Illustrating Theorem 3. We consider the same setting as in Theorem 2.
STOCHASTIC MECHANISMS
The results thus far relied on the assumption that the evolution of 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 , -ー at a short enough time interval that there is no uncertainty about the system's 's evolution. To generalize to cases where there is some uncertainty about the latent state's evolution, now develop analogous identification results for stochastic mechanisms that induce conditional distributions over latent states. The systems evolves as
X₁ - g(Zt), Ze+1 + m.(Z,, Uz),
(7)
where each U, is noise with each component sampled independently from standard uniform distribu- tion Uniform (0, 1]. Z ~ Pz, my 2 x 00, 1j - 2, and the decoder g 2 + X' is a diffeommrphissm (i.e. a smooth bijection with an invertible Jacobian, see definition A. (Kass & Vos, 2011)).
In this section, we will focus on the case where the true mechanism is unknown; the case where mechanism is known a special case with no imitator, i.e., m, m, for all t. The goal is to search for an encoder g- which is diffeomorphism. that generates X,-1 = ğ o n (ā (xx),, Üt). where U, is a random vector with each component from Uniform(0. [0, 1]. In the deterministic case, we had required that any candidate encoder, 9 was point-wise consistent with the pairs of observations (I1+1, ax)). 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 such that the distribution of X Xx, Ia matches the distribution of X I, for all x, E X,
X = xT X = Zt
(8)
g (0 U.) d go me (n (xz), U.)
7

---

Published as a conference paper at ICLR 2022
Now, define the set of all candidate decoders (with corresponding encoders g0 that solve the above equation 8 as Rg. 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, before, these are the only sources of con-identifiabilityy In the special case where my is known, & defined below, only contains maps that result from equivariance. We continue to use the M - set of mechanisms that are used at least once in the evolution of the system and M - hyypohessss class of all the mechanisms.
Definition 3. Equivariance and imitators in distribution w.r.t M. Define set of functions E that satisfy commutativiyy w.r. the set of distributions M in the following sense. The set E comprises all the diffeomorphisns that satisfy the following condition: E & and only for each E MM,, 3 m E .M such that for all E 2, a m(z, U) m (a(z), U), where each component of U is sampled independently from Uniform(O, 1].
Define the set of maps that identify true 9 up to Ed as I = - "ō0=-go-',aEE"
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 up to the equivariances and imitators in distribution w.r.t M, ( ~e- g
To prove the above theorem, we follow a similar strategy as in Theorem 1 and establish 9 G 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 allowed to be stochastic, it allows we give an example of this in the next section.
generalize known results based on distributional assumptions;
4 A MECHANISM-BASED PERSPECTIVE ON EXISTING RESULTS
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-base perspective: they simply define particular kind of mechanism, which then implies identification up to the mechanism's '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 & (1.
Zr- = Zz Vz, V f(U.), U. Uniform [0, 1]a
where ff is an inverse CDF such that each component of V2 E Rd is sampled from the generalized Laplace distribution centred at zero with norm parameter a * 2, Z1 IPzz. 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 PP 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 from 2 and rather we work with + 2. Alternatively,
Klindt et al. (2020) we do not require analogous results to those Klindt et al. (2020); Hyvarinen & Morioka (2017) can be derived in settings where we do not know the distribution of V. but instead assume that observe X; often enough that the difference between Z, and Z is small. In particular, suppose that the data generation process follows equation 9 except each component of V, is an i.i.d. draw from non- Gaussian with zero mean and [V] < 8. Then as 5 + the true latent is identified up to permutation, sign-flip and offset. See Section A.9 for details.
5 RELATED WORKS
Non-linear independent component analysis (ICA) is a highly unidentified problem; several works (Hyvärinen& & Pajunen, 1999; Locatello 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;
8

---

Published as a conference paper at ICLR 2022
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 non-stationary time series without temporal dependence, then non- 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 Hälvä & 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 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 von Mises-Fisher distribution). In another line of work Locatello 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 non-linear ICA. The constraint is based on the observation that the decoder that gives rise to the image is composed of simpler functions that are mutually algorithmically independent: the authors exploit this inductive bias on the structure of to invert the data generation process. In another recent work von Kü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.
There is significant recent interest in leveraging equivariance assumptions to design more efficient deep network architectures; for 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(=), 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 the relationship between the symmetries of the environment and a model's representations, whereas we focus on how symmetries in the environment's 's transition function constrain the representation. The two perspectives are complementary, and in future work we hope to unify them.
Equivariance
6 DISCUSSION AND FUTURE WORK
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. Moving forward, a natural direction is to build methods founded on this theory. We describe two natural losses based on the identity gomoğ (xx)) = F4+1. i) Loss using observations:
We minimize next observation prediction error mil MeM E, B || I m h (X,)
where H. .M is the hypothesis class of functions for decoder and mechanisms respectively. ii) Loss us- ing latents: Alternatively, one could re-write the identity as g -1 = mog oor, and use square g(X..1) x(x_,))nngxx.. mmg(X.)
error or contrastive loss given as MEM Σ, E log (X.+1) mo)X.
where T represents other time instances, i.e., 7 + 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. In Appendix Section A.12 we share our initial results for the contrastive approach applied to 3d identification dataset (Zimmermann al., 2021).
9

---

Published as a conference paper at ICLR 2022
REFERENCES
Tim Austin. Exchangeable random measures. Annales de I'Institut Henri Poincaré, Probabilités el Statistiques, 51)., Aug 2015. ISSN 0246-0203. doi: 10. 10.1214/13-ahpp584. URL http:
//dx.dof org / 10. 1214 10114/13-220 13-AIHP584,
Yoshua Bengio and Yann LeCun. Scaling learning algorithms towards AL. In Large Scale Kernel Machines. MIT Press, 2007.
Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE transactions on pattern analysis and machine intelligence, 35(8):1798-1822 2013.
Benjamin Bloem-Reddy and Yee Whye Teh. Probabilistic symmetries and invariant neural networks. J. Mach. Learn. Res., 21:90-1, 2020.
Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Velickovic. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. CoRR, 1WW2104.13478, 2021. URL https: // //aaxivvorg//aaeeeeeeee abs 2104. 13478.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Hlerbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. CoRR, abs/2005.14165 141655, 2020. URL https:ttp//.mmm / arxiv org/ abs 2005.14156
Pierre Comon. Independent component analysis, new concept? Signal processing, 36(3):287-314 1994.
Morris H DeGroot. Probability and statistics. Pearson, 2012.
Morris Eaton. Group invariance applications statistics. In Regional conference series in Probability and Statistics, pp. i-133. JSTOR, 1989.
Luigi Gresele, Paul K Rubenstein, Arash Mehrjou, Francesco Locatello, and Bernhard Schölkopf.
The incomplete rosetta stone problem: Identifiability results for multi-view nonlinear ica. In Uncertainty in Artificial Intelligence, pp. 217-227. PMLR, 2020.
Luigi Gresele. Julius von Kügelgen, Vincent Stimper, Bernhard Schölkopf. and Michel Besserve. Independent mechanism analysis, new concept? arXiv preprint arXiv:2106.05200, 2021.
Hermanni Hälvä and Aapo Hyvarinen. Hidden markov nonlinear ica: Unsupervised learning from nonstationary time series. In Conference Uncertainty in Artificial Intelligence, pp. 939-948. PMLR, 2020.
Irina Higgins, David Amos, David Pfau, Sebastien Racaniere, Loic Matthey, Danilo Rezende, and Alexander Lerchner. Towards a definition of disentangled representations. arXiv preprint arxiv=1812.000 2018.
Aapo Hyvarinen and Hiroshi Morioka. Unsupervised feature extraction by time-contrastive learning
and nonlinear ica. Advances in Neural Information Processing Systems, 29:3765-3773, 2016.
Aapo Hyvarinen and Hiroshi Morioka. Nonlinear ica of temporally dependent stationary sources, In Artificial Intelligence and Statistics, pp. 460-469. PMLR, 2017.
Aapo Hyvärinen and Petteri Pajunen. Nonlinear independent component analysis: Existence and uniqueness results. Neural networks. 12(3):429-439, 1999.
Aapo Hyvarinen, Hiroaki Sasaki, and Richard Turne. Nonlinear ica using auxiliary variables and generalized contrastive learning. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 859-868. PMLR, 2019.
10

---

Published as a conference paper at ICLR 2022
Tero Karras, Samuli Laine, and Timo Aila. A style-based generator architecture for generative adversarial networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Patter Recognition, pp. 4401-4410, 2019.
Robert E Kass and Paul W Vos. Geometrical foundations of d'asymptotii inference, volume 908. John Wiley & Sons, 2011.
Ilyes Khemakhem, Diederik Kingma, Ricardo Monti, and Aapo Hyvarinen. Variational autoencoders and nonlinear ica: A unifying framework. International Conference on Artificial Intelligence and Statistics, pp. 2207-2217. PMLR, 2020a.
Ilyes Khemakhem, Ricardo Pio Monti, Diederik P Kingma, and Aapo Hyvärinen. Ice-beem: Identifiable conditional energy-based deep models based on nonlinear ica. arXiv preprint arXiv:2002.1153/ 15537, 2020b.
David Klindt, Lukas Schott, Yash Sharma, Ivan Ustyuzhaninov, Wieland Brendel, Matthias Bethge, and Dylan Paiton. Towards nonlinear disentanglement in natural data with temporal sparse coding. arXiv preprint vrXiv22077.109300 2020.
Francesco Locatello, Stefan Bauer, Mario Lucie, Gunnar Raetsch, Sylvain Gelly, Bernhard Schölkopf, and Olivier Bachem. Challenging common assumptions in the unsupervised learning of disentan- gled representations. In International Conference on Machine Learning, pp. 4114-4124. PMLR, 2019.
Francesco Locatello, Ben Poole, Gunnar Rätsch, Bemhard Schölkopf, Olivier Bachem, and Michael Tschannen. Weakly-supervised disentanglement without compromises. In International Conference on Machine Learning, pp. 6348-638 6359, PMLR, 2020.
Boris Mityagin. The zero set of real analytic function. arXiv preprint arXiv: 2015.
Isaac Newton. Newton's 's Principia: : the Mathematical Principles of Natural Philosophy. 1687.
Bogdan Nica. The mazur-ulam theorem. arXiv preprint arXiv: 330.23800, 2013.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning, pp. 8748 8748-8763. PMLR, 2021.
Ali Razavi, Aaron van den Oord, and Oriol Vinyals. Generating diverse high-fidelity images with vq-vae-2. In Advances in neural information processing systems, pp. 14866-14876, 2019.
Bernhard Schölkopf, Francesco Locatello, Stefan Bauer, Nan Rosemary Ke, Nal Kalchbrenner, Anirudh Goyal, and Yoshua Bengio. Toward causal representation learning. Proceedings of the IEFE, 109(5):612-634 2021.
doi: 10. 00.1009//PRC...221133535//
Rui Shu, Yining Chen, Abhishek Kumar, Stefano Ermon, and Ben Poole. Weakly supervised disentanglement with guarantees. arXiv preprint arXiv:1910.09777 2019.
Yang Song. Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. International Conference Learning Representations, 2020.
Julius Kügelgenn, Yash Sharma, Luigi Gresele, Wieland Brendel, Bernhard Schölkopf, Michel Besserve, and Francesco Locatello. Self-supervised learning with data augmentations provably isolates content from style. arXiv preprint arXiv:2106.046111 2021.
Roland Zimmermann, Yash Sharma, Steffen Schneider, Mathhis Bethge, and Wieland Brendel. Contrastive learning inverts the data generating process. arXiv preprint arXiv:2 102.0800,,,, 2021.
11

---

Published as a conference paper at ICLR 2022
Approach
Assumptions
Time contrastive (Hyvarinen Morioka, Ze U1, each U/ independent and non-stationary
2016)
Permutation contrastive (Hyvarinen & Each Z/41 (Z) U/). stationary and quasi-Gaussian Morioka, 2017)
Slow VAE (Klindt et al., 2020)
Z++1 + Ze + f(U),, each f(U)) is independent and gener-
alized Laplace
Conditional VAE (Khemakhem al., 2020a;
Z m(O, U'. all components of Z are independent condi-
Hyvarinen al., 2019)
tional on Q
Independently modulated component analysis
mOO, U') m has special structures allowing relax conditional independence
(Khemakhee et al., 2020b)
Contrastive learning (Zimmermann al.,
7 m U), is such that 7 conditional Mises-
2021)
Fisher
Multi-view ICA (Gresele et al., 2020)
Z1 f m Zo. U), Xo + go X1 + (1))), all compo-
nents of Zp and U are independent
Table I: Table comparing different works and the assumptions made for identifiability.
A APPENDIX
A.1 PROOF OF THEOREM 1
Proof. First we show that Gia C Geq.
Consider ÿ E Gid. For each E X'
gomog 9 (x) = go (x)
g gomoog (x) -goo (ğomog (w))
(Compose g-1 with both sides)
ğ (x)) m (z)
g(z) 2)
Since is invertible substitute in the above equation with = g(2) and obtain for each 2 E
0 og)
g(2))
(g g(2))
(olog) m(2)
g 9 (2)
(10)
Define g o a. Observe that a is invertible and from equation 10 we gather that a E E. Also, since ÿ = g
we can conclude that ğ E Geq. which proves the first part of the claim. For the
second part, we show that Gog C Gid-
Consider 7 E Geg l g goa EE By definition, can express z = =goa" For each x E X we write
(x) gomoğ (x) = (goa omo 1) (x)
(gon)
(gon oaomog (x)
goomor o (z)
Observe that ğ is both a bijection and satisfies the identity in equation 4. Therefore, ğ E Gia. This proves the second part the claim. Therefore, Gia 9eq
A.2 LINEAR MECHANISM M AND LINEAR
The focus of the main text is nonlinear identification, but in this section show how the analysis for general functions and m applics to the special case when g and m are linear and affine maps respectively. This special useful both concrete example, and stepping stone to
12

---

Published as a conference paper at ICLR 2022
Theorem (nonlinear g with affine m) which will reuse some of the same proof strategies. We write the data generation process as follows.
-++1 M2.
(II)
Gz
where M E Rddd is diagonalizable matrix describing the mechanism, E R& is the offset parameter, G Raxd is an invertible matrix determining how the data transforms from latent space to the observable space. We write the cigendecomposition of M follows M SAS-1, where S is the matrix of eigenvectors and A is a diagonal matrix of the eigenvalues. On the same lines as the equation
obtain identity between Fz and I++1 follows.
2t41 Mz 2t +
G r1+1 = MG-1xp Iz +
(12)
T++1 GMG- x + Gb
the learner knows M and b, it tries to solve for an invertible Ō that satisfies
T++1 = GMG-1 + Gb
(13)
Theorem 6. If the data generation process follows equation Il and the eigenvalues of the mechanism M are all distinct and each component of the vector S b is non-zero, then the only solution 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 Tt Rd
(GMG-1- GM + (G G)6 0
(14)
Because, equations 12 and 13 hold for all 24, we can substitute x; = 0 in the above to get
(G GD 0
(15)
We plug the above condition in equation 15 back into equation 14 to get the following condition. For each 24 e Rd
(GMG - G-G =
(16)
If equation 16 holds for linearly independent vectors E Rd, then we can conclude that,
GMG-1-GMC - -
G "GMG-1-
MG-1 - G- -G-CMM =
(MG-1- -C'-Mã 1)6 )==0
MG-16= G-
(17)
Let A G-1G. We substitute A and the eigendecomposition (M SAS-1, where
diag 'i, ... Xa)) in equation 17 get
M AMA-1
SAS ASAS-1A-1
(S- (S-1AS) AS-AAA(S----1S
CAC
(where = SS-AAS)
AC CA
(18)
13

---

Published as a conference paper at ICLR 2022
We further simplify equation 18 and compare each element of the matrix AC and CA to get the following condition. For all j, E {1,-.. .. (1,....d]) .d] dd
[AC]y CiyAs, [CAl, Ciyu3 Ci - -2)) =0
(19)
Consider the above equation 19 for i # get
CA - A²) 0 Cj = 0 (we use the assumption that X # X
(20)
From the above, it follows that C' is diagonal matrix. We obtain expression for A in terms of C matrix below.
AS = C = SCS-1
(21)
From equation 15 we get that
(G G)b= G=GA (1 A)b 0 Eqn. (21)
(1- SC5--5
S - CS = (C-
(22)
Left multiply S-1
Since C is a diagonal matrix, simplify the above condition further to get (ca ()((S)b)) 0. obtain C
Since (S-1b); +
G G- =
= G = G.
Cai
A.3 PROOF OF COROLLARY
Proof. This proof follows essentially the same strategy the proof of Theorem with a set of mechanisms, M instead of single mechanism m; we include it for completeness. First we show that G% S Pzq.
Consider ğ E G For each x E X and for each m E M
g (x) = g m (x)
(23)
and by following the same steps as the proof of Theorem can show that,
[ ogg) m()) m (g
(24)
As before, define gー E E*. Also, since ğ = g a a1 we can conclude that Gēg. which proves the first part of the claim. In the second part, we need to show that Geg S Gia
Observe that is invertible and from equation 24 we gather that
Consider a G tō ÿ goatt, EEEE). By definition, can express -g - For each x and for each m M we write.
g (x) (goa oomo (aog
(goa o c (x)) (since commutes with each M) gom (x) for all
(25)
Observe that ğ is both bijection and satisfies the observation identity in equation 4. Therefore, g E Gig This proves second part of the claim. Therefore, G -
A.4 PROOF OF THBOREM 2
Proof. We showed in Theorem that the only source of non-identifiabiiity 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 E, then it satisfies a m = m o a. We replace m with the affine mechanism to obtain the following condition. For each E Rd
14

---

Published as a conference paper at ICLR 2022
( + MM(2) +
(26)
Next, recall that Rd R we take gradient of the function in the LHS and RHS of the above
equation 26 separately w.r. 2. Consider the jth component of a(M2 + b) denoted as ay (M + b).
We first take the gradient of az (Mz + b) w.r.t
dy dz
V
V
(27)
where y = Mz + (y) is the gradient of aj w.r.t y and dे denotes the Jacobian of y w.r. 2. We simplify the above further to get
M Vyas( VV.MVVVV,
M M Vya
(28)
We can write the above for each component of a as follows.
V (MMa(Mz+ + b), V Vsaa(M= + +b] [MTv 10 ()) .M poooao==> +6] MMIV ya (M* b.. Vyaa(Mz b)] M J ((M=+++z)))
(29)
where J(M= + b) is the Jacobian computed at Mr + Next, we take the gradient of the jth component of the RHS in equation 26 and let m, denote the 7th column of M,
m
My²
V=[maa(22 + b,] =
Σ Em = (z). Vaa(=)]
(30)
Mjj_
We can write the above for each component in the RHS of equation 26 as follows
Mm mi
m12.
maz
V. V=(m[a(2)tbb)... ... V. bb
[Voi(z), Vaa(=)]
(2)
mids
mad_
(31)
We equate the gradient of LHS and RHS in equation 26 using the expressions derived in equation 29 and equation 31 to obtain
al M b) Ma(=) +b M J +)) J=(MM -0
(32)
We write the same expression at another offset b' * below
aMM +b) Ma(2) + M (M2++6)) J===(=" =0
(33)
Taking the difference of equation 32 and equation 33 we get MT JT b) = (M=
Since M is invertible, get J[Mz + b) (M b'). Consider row j of this identity. For each z E R
Via
(2a)(O2)
(M.MMM2))-Vo =0 - Vo-(6)-Vo,(3tb-bb) =0 -0-
(b-
0
(oa)(
(34)
where Vña is the Hessian of a, and (iay(0)) corresponds to the 4thh row of the Hessian matrix. Note that in the above expansion there is different 0₂ for each row (mean value theorem applied
15

---

Published as a conference paper at ICLR 2022
to each component of Va, yields different point 0g the line joinining 2 and 2 b.. From Assumption 2 and based on the fact that M is invertible, follows that (O)) (6))'))6))))) 6') 0 over measurable set. Since a is analytic (z) b') is also analytic. Therefore, from (Mityagin, 2015), we can conclude that (z) - b) = 0 for all z. We can make the same argument for each component l and conclude that (=) b') 0. From Assumption it follows that (=))(=)(b> - b²) 0 for all j 12.... d 1} and since the set {b2 b² ,... _5++1 b²} is linearly independent (z) = 0 for all This implies a(z) A= + p. Plug a(z) A= + y into a(M= b) = Ma(=) to get
A(M + b) + = MA(=+p) + = (AM - MA)z + (A 1)b + (1 M)p 0 (35)
We write the same expression for offset b'
A(M + b') + p M + p) + = (AM MA)² + (A- 1)6 + (1 M)p (36)
We take the difference of equation 35 and equation 36 to get
(A [) - =0
(37)
Substitute = = in equation 35 to get
(A-1)b + MM) =0
(38)
Substitute the above condition in equation 38 into equation 35 get the following. For each z
(AM - MA)= 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 and the equation 37 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 and substituting in equation 39 we get the following,
MA = AM
M AMA
SAS = ASAS-1AT
A = (S-'AS) (5-'AS)A(551)) (SS-'AA'S))
(40)
A = CAC
AC = CA,
where C = S-1 AS, M = SAS-1, diag ' .da). We further simplify equation 18 and compare each element of the matrix AC and CA get the following condition. For all i E (1....,d
[AC]s = Cty.i ICA]g CıfAs CA - (x))
(41)
Consider the above equation 41 for i # j to get
Ci Aς) = > Cj = 0 (we use the assumption that A; * A1)
(42)
From the above, it follows that C' is diagonal matrix. We obtain expression for A in terms of C matrix below.
S-LAS=
(43)
A= SCS-
From equation 37 we get that
(G - G) -0 G=GA -I- A) - b')= =0 = (I- SCS-1 00
=
S- (b-(6-
CS -6 (b-)
-C- 11---1(---6 =0
(44)
Left multiply S-1
Since C' is diagonal matrix, we can simplify the above condition further to get (ca - 1)(S-1
6 b')), = 0. Since (S-1(b-b')) + 0 - C = 1, we obtain C I = A = a(2) = 2tp.
This proves that the latents identified up to offset.
16

---

Published as a conference paper at ICLR 2022
A.5 PROOF OF THEOREM 3
Proof. We first show that Gia C Geq. Consider / E Gia. We rewrite equation 6 below. For all æ E X
g m g (x) go m. o (z) g) (m+ o g (x:) m. 0
(45)
Since g is bijective, we can write g(z) get
(g o g) o m²(2)= = m o "g وー g(()
(46)
Since the above equality holds for all = Z we can conclude that
(g 1 g) m4 m (g o)).
(47)
a o m = m o a,
The above conclusion in equation 47 holds for all my E M Therefore, a in equation 47 and {ma)?= (where m E MM together satisfy the condition that for all E M a = m a, where i E M. We can rewrite h 9 9 go aa From this follows that ý 9eq. This proves the first part of the theorem.
Now let us consider the second part of the theorem. Consider a I E Seq. We can write a a- where a E &. At time t. some mechanism m, E MM is used to transform the latents. Since a E E, select the mechanism m E M for which o m, = m, o and as a consequence
g m og = agoa m, o a
g o m, og
(48)
In the first equality above, we of ÿ. We can repeat the above exercise for all i. and corresponding my using the same a. Therefore, ğ in Gia- This shows the second part of the theorem, i.e., Geq S Gia-
My m, and in the second equality
the definition
A.6 LEVERAGING THEOREM 3 WHENN MECHANNSSM IS LINEAR AND g IS NON-LINEAR
We write the data generation process as follows. For each t E (1,....,. d+1}
2111 M + be,
(49)
It = g(2)),
Let us construct the set & corresponding to the above setting. For each Rdd.
a(Mz + = =
= 0,
a(Mz + 6') = M a(2)())+
M -MM O,
(50)
where (M, b) and (M, b') are the true mechanisms and (M', 6') and (M', 8') are the imtitating mechanisms chosen by the learner, J is the Jacobian of Note here the learner only exploits the knowledge that 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
MT J (M + b) M JT JTM2++
(51)
Since M is invertible we get J(M² + b) - J(Mz + b') = for all 2. We can follow the same justification was used in equation 33 conclude that J(z) ) is constant and is thus an affine map. We substitue the affine map a(z) = Az + back into equation 50 to get the following. For all =
AM + Ab + +p= = M' A2 + 1 + M'
(52)
Substitute to get b's Ab +p- M' p. Substitute this condition back into the above equation, get AM M' A = M -
17

---

Published as a conference paper at ICLR 2022
A.7 PROOF OF THEOREM 4
Before stating the proof of Theorem 4, we state two existing results that we use.
Result (Change of variables formula (DeGroot, 2012)) Given continuous random variable
X E IRdd with pdf px and its transformation Y f(X), where f: IR + R24 is a diffeomorphism; then py (f(=))det(J){()) = px (z), where Jy is the Jacobian of f computed z.
Lemma 1. If X and Y are two continuous random variables that take values in R that are equal in distribution, ie., X 2 Y. Iff Rd TR& is diffeomorphism, then f(X) _ f(Y).
Proof. Since X and Y are equal in distribution, they have the same pdfs, i.e. (x( py (x) for all a E Rd. We can use the change of variables formula in Resut 1 above to get the following. Let W =
((X), px(s--(w)) (et()) (w))) = pw (w) and let V [(Y), (f- (e)]d (v)) =
(v)).. Comparing the two expressions when w = v we get pw (w) = pv(w). This proves the result.
O
We stated Result and Lemma for continuous random variables. When the random variables are discrete. Lemma holds for any function f.
Lemma 2. (Kass & Vos, 2011) If 2 + Z and g Z Z diffeomorphisms, then f o g is diffeomorphism.
Proof. We first show that 0 S geg-
From the observation identity in equation 8 we get that g. {m=]]= satisfy the following for all t e f1,",,
go (x1), Ui) _ g m. (a) U,) (g ( oml ( (xx), U.) - mr (xx)
(53)
In the second step the above equation, we transformed the random variables in the first step using compose both sides of the first step LHS and RHS with ğ We use Lemma to get from the first step to the second step in the above equation equation 53. In the above equation H, is a fixed value and the only source of randomness is from U, in LHS and U, in the RHS. We substitute 2, = g(ze) to further simplify the above expression in equation 53
the same transform 8-1 9-
1 is diffeomorphism;
[ o g) me o g(())), o
= m m g(zt), (()))),)))
(54)
[ o mi ( u.) 2 me mi g(xx), Ui)
Substitute a = =g- y in the above to get the following
a me Ex, Us) my (a(x)) (.)))))
(55)
a come memmazz E2, U.) m. (a(z)),U))
From Lemma 2 follows that in the above is diffeomorphism. Since assume that _f_ {m+} M" follows that a in equation 47 and (ma i (where my E MM together satisfy the condition for membership in 8 Since 9 = g o we obtain that ī Geg
We now show that Gü C Gi Consider ğ Go We use = goa where e 8 simplify the following random variable
mit http:://ttttt..eeee/..eeee/////r
pdf
18

---

Published as a conference paper at ICLR 2022
o mmllll = (goa-'o o0))) mils m Uz) = goao (x)),
(56)
Since E E we have
()) mr (x)),
(mx),U;)
From Lemma it follows that ÿ is a diffeomorphissm. From Lemma it follows that
joaom U.) _ 9 o U4) 9 m mr (x)))
(57)
Combining equation 56 and equation 57 and using the fact that U, _ U2 get
go (x:), _ g m, (. (xx). U,) g m (ğ (0 (xt), Úi)
(58)
From the definition of 8x it follows with the same choice of the condition continues to hold for all my E M Therefore, E P. This proves the second part of the theorem.
A.8 PROOF OF THEOREM 5
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², Let us analyze the set Ed for the class of mechanisms considered in Klindt et al. (2020). Consider a E E*, For each E Rd
a(=+V) - V) a<z)) +V,
(59)
Define Y =a(2) V. Since V V we write the probability density function (pdf) of Ý as
(v)
(60)
Define VV=+V). a Rd Rd is diffcomorphism. We use the change of variables result (Result 1) to write the pdf Y as follows. For each IRd
fv = det (v)) fv(a
22),
(61)
where J(a-1(y) is the Jacobian of a computed at a (y), and det is the determinant.
We substitute equation 60 and equation 61 in the equivariance condition in equation 59 obtain the following. For each E RRd
Y =
fv(y a(2)) fv(a (2)a-(()) 2) [det(J (y)))
(62)
fv(w - 2)
fv(a(w) a(z)) [de((J(w))
where w = (y). In the above we equated the conditionals for each 2, we now equate the marginals.
g _ go (2+ a (Z + V) 7 +
(63)
19

---

Published as a conference paper at ICLR 2022
We follow Klindt et al. (2020) and assume 2 _ Z and V _ V. Therefore, + _ 2 V. We use this condition to restate equation 63
(Z + V) Z + = aW) W
(64)
where W = Z + V. We translate equation 64 into the condition on the pdfs as follows. For each IRd
Jw [w(w)]de([[((()) = [ww(w) [det(J(w)))
(65)
Substituting the above equation equation 65 into equation 62 get
fv(a(w) a(z)) = fv( - 2) [et(] (w())
= (v(a(w)-a(a) fv(w - 2)
(66)
[a(w)) - d(=)]la || =1la:
where in the last condition in the above expression we exploit the fact that fv generalized Laplacian distribution. From Mazur-Ulam theorem Nica (2013) it follows that a is affine. We now write matrix with offset vector q and simplify the condition in equation 59.
For each 2 E Rd we have
A(z + +V A Ae + V +q B[AVV'A"|=E[11>
AV _ V AA =1
(67)
Since A is a square matrix and AA it follows that A = Therefore, A is an orthonormal matrix. Observe that all the elements of V are independent. Since AV á 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 a * 2) and outputs vector that has all independent components. From Theorem 11 in Comon (1994) get that A is a composition of permutation and scaling. Since A is also orthonormal, each term the diagonal scaling matrix can only be 1 or 11 Therefore, A IIA, where II a permutation matrix and A is diagonal matrix with +1, -1 elements. Finally, a a(2) = 1IAz +
A.9 ALTERNATIVE IDENTIFICATION RESULT FOR SMALL TRANSITIONS
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 Ex 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
al= va-vii V) - a(2) + +V. We write the first-order approximation of the above identity below
(68)
a(2) + J(z)V _ aa()+++ +V
(69)
J(z)V $ V
where V 1 V. Note that the set of solutions to equation 68 and equation 69 become equal in the limit of 5 + O, where 5 the bound on each component of [V]. We analyze the solution to equation 69 below.
(e -
of "E
(70)
)²((z)((=)T =o = J(z)((=) =1
=1 - J(z) =
20

---

Published as a conference paper at ICLR 2022
Since J(2) _ 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 ((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 2 in the neighborhood of and continue to find that the jacobian matrix is permutation times diagonal matrix (that describes sign flips). Note that the permutation matrix times scaling used express the Jacobian cannot change between the points Σ and = (if it does change then that violates the Jacobian's '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 is analytic and Mityagin (2015)). As result, a is of the form ITA= + q: where TT a permutation matrix, A is diagonal matrix.
A. ANALYZING AUXILIARY INFORMATION MODELS
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 : x [o, 1]d that takes as input some observed auxiliary information O and uniform independent noise vector U E 1]
7 - (0,U),
(71)
X gZ),
where 2 +> X' is bijection. Suppose the learner knows the mechanism. The learner selects ğ and outputs X= ğ m((o, Ú). where Ü is random vector with each component sampled independently from Uniform (0, 1). The learner's goal is to match
110 = o x|0
(72)
g gg U).
for all possible observations O. Define the set of solutions to equation equation 72 as 9 Consider bijection a s.t. the following identity holds for all o E O
a a aom(o, U) d m(o, Ú) Define the set of all bijections a that satisfy the condition in equation equation 73 as E The set E consists of intersection of measure preserving transformations of 2 o. Define the set of ğ that are identifiable up to E as 9og = قg g go a E }
(73)
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 up intersection of all the measure preserving maps in Eo (g NEe )
Proof. Consider áğ Ca
g gom(o, _ g m(a, Ú)
g e aogom(a. U) _ m(o,ū) ū)
(74)
aom(o, U) _ m(o, Ú)
From the above it follows that ğ Go Consider a و E 9
g o m(, U) = g a oa m(o U) go m(o, Ú)
(75)
From the above it follows that ğ Gg- This completes the proof.
Let us consider additive mechanisms of the form m(o, U) = mo) + 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.
go (mi() - U) d go (m (o) + 0)
g g + U)= _ m m'(() + Ū
(76)
a(m(o) +U) _ m'(o) +Ū
21

---

Published as a conference paper at ICLR 2022
Suppose that the absolute value of each component of U is really small and bounded by 8. We can use the first-order Taylor expansion and obtain
a(m())) J(m(o)) = m (o) + Ü,
(77)
where J is the Jacobian of Suppose the noise has zero mean. Take the expectation w.r.t. and U on the two sides respectively get a(m(o)) m (o). Substitute this back into the equation we get that U U. We 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 & WHEN M MM
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 and M = -M*. From the definition of it follows that for each m E M m E MM such that m m o a. We claim that two distinct E M cannot share the same (imitator). Suppose there was a common m imitating and m.
a m = m
(78)
m We take the difference of the above two equations to get
a o m a m
(79)
Since a is a bijection, we can conclude that m = m, which a contradiction of the fact that m and mn are distinct.
This claim implies that for a given a there is an injective map from M to M the set M is finite, then from Pigeonhole principle follows that this injective map is bijection.
Let us index the mechanism M = {m²,... ... m²) }. We call the bijection map т MM + M
Consider the element i. We claim 31 E {1..... nn n (i) i. We write the chain starting from as i i- x1) + (1). ,² (i). Since the chain (I - n (1) ... TT (f)) has n steps there have to be least two elements that equal. Suppose p and (1) (1)
(1) (1)
n (1) = x--1
(80)
In the above each step the fact that is bijection and that shows the claim that r' i. We now use this observation to carry out the following simplification
m a m a(i) oa m (1) = a' m (1)
(81)
m=* ==(()) (1) = -a m'
Substituting the second equation (x) into first, and then the third m= and so on we get
m² a o m² o h
(82)
Therefore, for each m', 3 k such that a is its equivariance.
To summarize, a E E and M = M where M is finite set, then for each mechanism m E M, 3K E (1,.... IMI such that & its equivariance.
A.12 TRANSLATING IDENTITY INTO LOSS FUNCTIONS AND PRELIMINARY EXPERIMENTS
We restate the loss choices based identity ğ m o g (xt) st+1 below.
22

---

Published as a conference paper at ICLR 2022
Loss based observations. The identity above immediately implies autoencoder-style algorithm where one minimizes a reconstruction loss of the form
ΣE[1x go m h(x,)1
min AEH, MEM
(83)
where H is the hypothesis class of functions for ğ and M is the hypothesis class of mecha- nisms.
Loss based on latents. Alternatively, one could re-write the observation identity as g Tt41 m g 3t and use contrastive loss as follows
g(X++1 ) (X,
min ΣE
E - log g(X++1) ( mig( (1) + Σ, " (
(84)
where represents other time instances, i.., o 1. The positive pair in the contrastive loss is formed by the adjacent time instances and the negative pair is formed by non non-adjacent time instances. Identifying which of these two losses works better in practice an important empirical question. Note how in both the losses above, we have explicitly not enforced invertibility for the learned
We present our initial experiments on 3dIdent dataset from [Zimmerman al. 2021], using the contrastive loss described above. With contrastive pairs generated by (fixed) random orthogonal matrix U applied the latents, we obtain the following values for linear disentanglement score (R² of the predictions of the true representation using 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 the contrastive loss achieves median score 0.76.
Contrastive leveraging with some knowledge mechanism If use a random orthog- onal matrix U * U, that achieves a median score of 0.64. The random matrix can be interpreted as sampling a random m from the hypothesis class M; it seems likely that better results are possible by optimizing over M.
23


Reviews:
[{"review_id": "tUzeR3M4RwW", "reviewer": "Reviewer_muVw", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is an insightful theory paper. Rather than making arbitrary independence assumptions on the latents, it considers the true data-generating mechanism and attempts to recover the latent based on assumptions on knowledge of the mechanism. While some of the results are intuitively mentioned in prior empirical work and may be obvious (i.e., the latents are unidentifiable upto scaling constant), I think the paper extends it to provide a strong result when there are multiple mechanisms at play: in that case, identification may become easier (cor 1). The constraints are shared and should be satisfied across all mechanisms. \n\nTo connect with realistic situations, I liked the extension to the unknown mechanism and stochastic mechanisms. Although I have to say that I did not check the appendix for proof, so I would defer to other reviewers on the theoretical validity.\n\nMy main feedback is on the relevance of this formulation to representation learning tasks:\n1. Besides the balls example, can the authors provide ML tasks where the time-based mechanism would make sense? I presume it is not useful for images, but applicable to videos. What about natural language? Is there a similar mechanism? I'm trying to understand the empirical problems where mechanism-based characterization can help.\n2. I would have liked to see a simple implementation of the idea (even a toy one would suffice). In the balls example, would following the proposed method recover the Newton's laws coefficients, given some representation of the image/state?  I'm guessing you will need to assume a reconstruction loss, but for a simple problem, that choice should not matter.\n3. Finally, the assumption of invertible function is a limitation, as the authors note.\n\n\n", "summary_of_the_paper": "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. ", "summary_of_the_review": "Good theoretical insights, can have better connection to practice", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "cWV-bkAGh86", "reviewer": "Reviewer_bAsz", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Strengths\n\n+ This idea that an identified low-level mechanism can be used to disentangle high-dimensional observations is to my knowledge novel. It seems quite applicable particularly in control from pixel inputs. \n+ I checked the first couple of proofs in the appendix to get a feel for the techniques used. They looked correct. \n+ The main figure is helpful and very clear. \n+ The examples that are given, for example, the linear mechanism setting and the equivariances of affine mechanisms, are very helpful for understanding. \n+ Using the identifiability results to give a result from previous work was a nice illustration of the generality of the setup. \n\n# Weaknesses\n\n- No algorithm is proposed that actually uses the identifiability results, even in the simplest setting where the mechanism is totally known. I understand that this is not the focus of this paper, though it would have been nice to demonstrate the utility of these results and show that the assumptions are reasonable. \n- I think the bijectivity assumption is not unreasonable here but could have been better justified. One might argue that the assumption does not allow us to consider, for example, acceleration in the latent state (since a change in acceleration is not reflected in a single image). Injectivity is also assumed in the block MDP literature but is justified by the (common practice in RL) of frame-stacking, which would result in injectivity holding for variables like acceleration. The proofs I looked at leaned heavily into the bijectivity assumption. \n- I think a big part of the interest in disentanglement comes from not only learning the representation but also how the latent variables evolve.   This aspect is lost here since we either assume a known mechanism or assume a class of possible mechanisms but do not try to identify the mechanism. Nevertheless, I think the approach is still valuable because it 1) seems quite orthogonal to other works which try to make use of, say, conditioning on side information 2) seems to be potentially practical in simple control settings with high-dimensional observations. \n- The bijectivity and known mechanism assumption means some of the early theorems are not too surprising. This does not mean that they are not valuable, however. \n- It was not clear to me if similar results could be obtained if the observations are observed with additive noise. \n\n# Questions\n- Can more related works beyond the Klindt 2020 paper be explained within this framework? If not, why? \n\n# Minor points:\n- \"the success of pre-trained of\" typo. \n- Figure 1: can be made clearer on the diagram that the red latent representation does not give a correct prediction of the next observations.\n- \"we also have have to\"  typo\n- A1 contains no text. It should reference the associated table. \n\n", "summary_of_the_paper": "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. \n\n", "summary_of_the_review": "I think this is an exciting direction of work that runs orthogonally to a lot of the recent advances in disentanglement, by assuming knowledge of the underlying mechanism rather than independence and distribution assumptions on the latent variables. Presentation of an algorithm or some basic experiments to justify the feasibility of the new setting would substantially strengthen the paper. However, I think the identifiability results are useful enough for follow-up work that they have merit on their own. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "PcsIT5_qNYa", "reviewer": "Reviewer_7um5", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths.**\n- By approaching the problem through the lens of equivariances of the underlying mechanism(s) relating subsequent observations, the paper provides an interesting perspective on an important topic (identifiable representation learning) that (as far as I can tell) is novel. \n- The emphasis on non-iid observations related through some shared latent dynamics shares a common ground with many of the recent results in the literature (discussed in section 5) which makes it conceptually appealing. The lack of independence assumptions is also refreshing and makes this work of potential interest for causal representation learning. \n- The theoretical results seem sound (though I only checked the proofs of Thm.1 and Corollary 1 in detail)\n- The paper is well written and, despite being quite technical in nature, accessible and not too hard to follow; the organisational structure and succession of results make sense. I particularly liked the motivating bouncing balls example which is picked up repeatedly, especially in the first half of the paper, to illustrate assumptions or conditions (this was very helpful and could perhaps feature more prominently in the latter part of the paper). \n- Related work and limitations are adequately discussed in sections 5 and 6. \n\n**Weaknesses.**\n(some of these are also acknowledged by the authors, see section 6)\n- The paper assumes the reconstruction task to be solved and assumes invertibility not only for true $g$ but also for the learnt model; both of these are limitations in practice, and it would be nice to discuss how some insights from the paper may translate into practical learning rules.\n- The paper does not present any empirical results or experimental analysis. This is partly justified by being clearly a theory paper, but some aspects could also be probed empirically: e.g., by rendering some data using one of multiple known mechanisms, training a (Slow)VAE-type model that has access to this knowledge about mechanisms, and checking how the learnt decoder compares to the true one.\n- While it is pointed out that not knowing the exact mechanism and using a larger hypothesis class can be a source of non identifiability, it would be nice to quantify this somehow, either theoretically (e.g., as a function of the capacity of the function class) or empirically.\n- Some statements (e.g., Theorem 1) are a bit hard to parse, and others seem to be slightly imprecise (e.g., the definition of $\\tilde{\\mathcal{G}}_{id}$ after eq. (6): isn't this missing the qualifiers $\\forall t, \\exists \\tilde{m}_t$? and the set $\\mathcal{E}$ defined on p.4 depends on $m$ which should probably be highlighted notationally)\n\n**Other comments / suggestions.**\n- Regarding the section on stochastic mechanisms, I was wondering whether there could be a connection to measure-preserving maps / automorphisms which are a common source of nonidentifiability in nonlinear ICA?\n- Since the paper clearly tries to make an effort on discussing connections to existing results, it may be worth also comparing with and discussing the following works which seem relevant as they also revolve around deriving identifiability results for learning from multi-view data:\n- - [Gre19] The Incomplete Rosetta Stone Problem: Identifiability Results for Multi-View Nonlinear ICA. Luigi Gresele, Paul K. Rubenstein, Arash Mehrjou, Francesco Locatello, Bernhard Schölkopf. https://arxiv.org/abs/1905.06642\n- - [Von21] Self-Supervised Learning with Data Augmentations Provably Isolates Content from Style. Julius von Kügelgen, Yash Sharma, Luigi Gresele, Wieland Brendel, Bernhard Schölkopf, Michel Besserve, Francesco Locatello. https://arxiv.org/abs/2106.04619\n- The notation for composition is not consistently used: sometimes $a\\circ g(x)$ is used, sometimes $a\\circ g\\circ x$\n\n**Typos.**\n- p.3, 1st para: \"have have\"\n- p.4 1st para: \"any an encoder\"\n- p.4 after eq. (3): \"the follow functions\"\n- p.4 after eq. (4): \"that that\"\n- p.5 sec 2.2.1, 1st sentence: missing a pronoun like \"it\"\n- p.7 1st para: \"it's\" --> \"its\"; same sentence: \"diverse SET of\"; next sentence: \"in THE bouncing\"\n- p.8 1st sentence: shouldn't this refer to eq. (8) instead of (7)?\n- p.8, after Thm. 4: \"consistent WITH the\"\n- p.12, A.2: eq. 12 misses two equality signs at the start of the second and third line; the reference after eq. (12) I believe should be to equation (4), not (2)\n\n\n", "summary_of_the_paper": "**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.\n\n**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).", "summary_of_the_review": "Overall, this is an interesting paper and a valuable contribution to ICLR. I think that the lack of empirical results and experiments is justified by the theoretical contribution. Subject to some of the further improvements in aspects of the presentation, as well as discussion of additional related work suggested in my main review, I recommend acceptance. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides new insights about how to identify latent variable distributions, making explicit assumptions about invariances. A lot of this is studied in the literature of non-linear ICA, although the emphasis here is on dropping the "I". I think more could be said about how allowing for dependencies among latents truly change the nature of the problem since any distribution can be built out of independent latents, by some more explicit contrast against the recent references given by the reviewers. In any case, the role of allowing for dependencies in the context of the invariances adopted is discussed, and despite no experimentation, the theoretical results are of general interest to the ICLR community and a worthwhile contribution to be discussed among researchers in this field.
Decision: Accept (Spotlight)