# Additive Decoders for Latent Variables Identification and Cartesian-Product
Extrapolation

Sébastien Lachapelle∗ &Divyat Mahajan∗ &Ioannis Mitliagkas† &Simon Lacoste-
Julien† Mila & DIRO, Université de Montréal

###### Abstract

We tackle the problems of latent variables identification and “out-of-support”
image generation in representation learning. We show that both are possible
for a class of decoders that we call additive, which are reminiscent of
decoders used for object-centric representation learning (OCRL) and well
suited for images that can be decomposed as a sum of object-specific images.
We provide conditions under which exactly solving the reconstruction problem
using an additive decoder is guaranteed to identify the blocks of latent
variables up to permutation and block-wise invertible transformations. This
guarantee relies only on very weak assumptions about the distribution of the
latent factors, which might present statistical dependencies and have an
almost arbitrarily shaped support. Our result provides a new setting where
nonlinear independent component analysis (ICA) is possible and adds to our
theoretical understanding of OCRL methods. We also show theoretically that
additive decoders can generate novel images by recombining observed factors of
variations in novel ways, an ability we refer to as Cartesian-product
extrapolation. We show empirically that additivity is crucial for both
identifiability and extrapolation on simulated data. ††∗ Equal contribution. †
Canada CIFAR AI Chair. ††Correspondence to: {lachaseb,
<EMAIL_ADDRESS>
###  1 Introduction

The integration of connectionist and symbolic approaches to artificial
intelligence has been proposed as a solution to the lack of robustness,
transferability, systematic generalization and interpretability of current
deep learning algorithms [38, 4, 9, 18, 14] with justifications rooted in
cognitive sciences [13, 20, 31] and causality [40, 45]. However, the problem
of extracting meaningful symbols grounded in low-level observations, e.g.
images, is still open. This problem is sometime referred to as disentanglement
[4, 34] or causal representation learning [45]. The question of
identifiability in representation learning, which originated in works on
nonlinear independent component analysis (ICA) [46, 22, 23, 25], has been the
focus of many recent efforts [35, 47, 19, 33, 3, 6, 29]. The mathematical
results of these works provide rigorous explanations for when and why symbolic
representations can be extracted from low-level observations. In a similar
spirit, Object-centric representation learning (OCRL) aims to learn a
representation in which the information about different objects are encoded
separately [12, 15, 7, 17, 11, 37, 10]. These approaches have shown impressive
results empirically, but the exact reason why they can perform this form of
segmentation without any supervision is poorly understood.

Figure 1: Left: Additive decoders model the additive structure of scenes
composed of multiple objects. Right: Additive decoders allow to generate novel
images never seen during training via Cartesian-product extrapolation
(Corollary 3). Purple regions correspond to latents/observations seen during
training. The blue regions correspond to the Cartesian-product extension. The
middle set is the manifold of images of balls. In this example, the learner
never saw both balls high, but these can be generated nevertheless thanks to
the additive nature of the scene. Details in Section 3.2.

####  1.1 Contributions

Our first contribution is an analysis of the identifiability of a class of
decoders we call additive (Definition 1). Essentially, a decoder
${\bm{f}}({\bm{z}})$ acting on a latent vector
${\bm{z}}\in{\mathbb{R}}^{d_{z}}$ to produce an observation ${\bm{x}}$ is said
to be additive if it can be written as
${\bm{f}}({\bm{z}})=\sum_{B\in{\mathcal{B}}}{\bm{f}}^{(B)}({\bm{z}}_{B})$
where ${\mathcal{B}}$ is a partition of $\\{1,\dots,d_{z}\\}$,
${\bm{f}}^{(B)}({\bm{z}}_{B})$ are “block-specific” decoders and the
${\bm{z}}_{B}$ are non-overlapping subvectors of ${\bm{z}}$. This class of
decoder is particularly well suited for images ${\bm{x}}$ that can be
expressed as a sum of images corresponding to different objects (left of
Figure 1). Unsurprisingly, this class of decoder bears similarity with the
decoding architectures used in OCRL (Section 2), which already showed
important successes at disentangling objects without any supervision. Our
identifiability results provide conditions under which exactly solving the
reconstruction problem with an additive decoder identifies the latent blocks
${\bm{z}}_{B}$ up to permutation and block-wise transformations (Theorems 1 &
2). We believe these results will be of interest to both the OCRL community,
as they partly explain the empirical success of these approaches, and to the
nonlinear ICA and disentanglement community, as it provides an important
special case where identifiability holds. This result relies on the block-
specific decoders being “sufficiently nonlinear” (Assumption 2) and requires
only very weak assumptions on the distribution of the ground-truth latent
factors of variations. In particular, these factors can be statistically
dependent and their support can be (almost) arbitrary.

Our second contribution is to show theoretically that additive decoders can
generate images never seen during training by recombining observed factors of
variations in novel ways (Corollary 3). To describe this ability, we coin the
term “Cartesian-product extrapolation” (right of Figure 1). We believe the
theoretical framework laid out in this work to understand “out-of-support”
generation is a step towards understanding theoretically why modern generative
models such as DALLE-2 [42] and Stable Diffusion [43] can be creative.

Both latent variables identification and Cartesian-product extrapolation are
validated experimentally on simulated data (Section 4). More specifically, we
observe that additivity is crucial for both by comparing against a non-
additive decoder which fails to disentangle and extrapolate.

Notation. Scalars are denoted in lower-case and vectors in lower-case bold,
e.g. $x\in{\mathbb{R}}$ and ${\bm{x}}\in{\mathbb{R}}^{n}$. We maintain an
analogous notation for scalar-valued and vector-valued functions, e.g. $f$ and
${\bm{f}}$. The $i$th coordinate of the vector ${\bm{x}}$ is denoted by
${\bm{x}}_{i}$. The first $n$ integers excluding $0$ is denoted by $[n]$.
Given a subset of indices $S\subseteq[n]$, ${\bm{x}}_{S}$ denotes the
subvector consisting of entries ${\bm{x}}_{i}$ for $i\in S$. Given a function
${\bm{f}}({\bm{x}}_{S})\in{\mathbb{R}}^{m}$ with input ${\bm{x}}_{S}$, the
derivative of ${\bm{f}}$ w.r.t. ${\bm{x}}_{i}$ is denoted by
$D_{i}{\bm{f}}({\bm{x}}_{S})\in{\mathbb{R}}^{m}$ and the second derivative
w.r.t. ${\bm{x}}_{i}$ and ${\bm{x}}_{i^{\prime}}$ is
$D^{2}_{i,i^{\prime}}{\bm{f}}({\bm{x}}_{S})\in{\mathbb{R}}^{m}$. See Table 2
in appendix for more.

Code: Our code repository can be found at this link.

###  2 Background & Literature review

Identifiability of latent variable models. The problem of latent variables
identification can be best explained with a simple example. Suppose
observations ${\bm{x}}\in{\mathbb{R}}^{d_{x}}$ are generated i.i.d. by first
sampling a latent vector ${\bm{z}}\in{\mathbb{R}}^{d_{z}}$ from a distribution
${\mathbb{P}}_{\bm{z}}$ and feeding it into a decoder function
${\bm{f}}:{\mathbb{R}}^{d_{z}}\rightarrow{\mathbb{R}}^{d_{x}}$, i.e.
${\bm{x}}={\bm{f}}({\bm{z}})$. By choosing an alternative model defined as
$\hat{\bm{f}}:={\bm{f}}\circ{\bm{v}}$ and
$\hat{\bm{z}}:={\bm{v}}^{-1}({\bm{z}})$ where
${\bm{v}}:{\mathbb{R}}^{d_{z}}\rightarrow{\mathbb{R}}^{d_{z}}$ is some
bijective transformation, it is easy to see that the distributions of
$\hat{\bm{x}}=\hat{\bm{f}}(\hat{\bm{z}})$ and ${\bm{x}}$ are the same since
$\hat{\bm{f}}(\hat{\bm{z}})={\bm{f}}\circ{\bm{v}}({\bm{v}}^{-1}({\bm{z}}))={\bm{f}}({\bm{z}})$.
The problem of identifiability is that, given only the distribution over
${\bm{x}}$, it is impossible to distinguish between the two models
$({\bm{f}},{\bm{z}})$ and $(\hat{\bm{f}},\hat{\bm{z}})$. This is problematic
when one wants to discover interpretable factors of variations since
${\bm{z}}$ and $\hat{\bm{z}}$ could be drastically different. There are
essentially two strategies to go around this problem: (i) restricting the
hypothesis class of decoders $\hat{\bm{f}}$ [46, 19, 6, 49], and/or (ii)
restricting/adding structure to the distribution of $\hat{\bm{z}}$ [23, 36,
30, 33]. By doing so, the hope is that the only bijective mapping ${\bm{v}}$
keeping $\hat{\bm{f}}$ and $\hat{\bm{z}}$ into their respective hypothesis
classes will be trivial indeterminacies such as permutations and element-wise
rescalings. Our contribution, which is to restrict the decoder function
$\hat{\bm{f}}$ to be additive (Definition 1), falls into the first category.
The restricted function classes for decoders proposed so far do not clearly
apply to images, unlike additive decoders which nicely captures their additive
nature. Moreover, the methods that do not restrict the decoder must instead
restrict/structure the distribution of the latent factors by assuming, e.g.,
sparse temporal dependencies [22, 27, 1, 28], conditionally independent latent
variables given an observed auxiliary variable [23, 25], that interventions
targetting the latents are observed [30, 33, 5, 2, 3], or that the support of
the latents is a Cartesian-product [48, 44]. In contrast, our result makes
very mild assumptions about the distribution of the latent factors, which can
present statistical dependencies, have an almost arbitrarily shaped support
and does not require any interventions. Additionally, none of these works
provide extrapolation guarantees as we do in Section 3.2.

Object-centric representation learning (OCRL). Lin et al. [32] classified OCRL
methods in two categories: scene mixture models [15, 16, 17, 37] & spatial-
attention models [12, 8, 7, 11]. Additive decoders can be seen as an
approximation to the decoding architectures used in the former category, which
typically consist of an object-specific decoder ${\bm{f}}^{(\text{obj})}$
acting on object-specific latent blocks ${\bm{z}}_{B}$ and “mixed” together
via a masking mechanism ${\bm{m}}^{(B)}({\bm{z}})$ which selects which pixel
belongs to which object. More precisely,

$\displaystyle{\bm{f}}({\bm{z}})=\sum_{B\in{\mathcal{B}}}{\bm{m}}^{(B)}({\bm{z}})\odot{\bm{f}}^{(\text{obj})}({\bm{z}}_{B})\
\text{, where}\
{\bm{m}}^{(B)}_{k}({\bm{z}})=\frac{\exp({\bm{a}}_{k}({\bm{z}}_{B}))}{\sum_{B^{\prime}\in{\mathcal{B}}}\exp({\bm{a}}_{k}({\bm{z}}_{B^{\prime}}))}\,,$
(1)

and where ${\mathcal{B}}$ is a partition of $[d_{z}]$ made of equal-size
blocks $B$ and ${\bm{a}}:{\mathbb{R}}^{|B|}\rightarrow{\mathbb{R}}^{d_{x}}$
outputs a score that is normalized via a softmax operation to obtain the masks
${\bm{m}}^{(B)}({\bm{z}})$. Many of these works also present some mechanism to
select dynamically how many objects are present in the scene and thus have a
variable-size representation ${\bm{z}}$, an important technical aspect we omit
in our analysis. Empirically, training these decoders based on some form of
reconstruction objective, probabilistic or not, yields latent blocks
${\bm{z}}_{B}$ that represent the information of individual objects
separately. We believe our work constitutes a step towards providing a
mathematically grounded explanation for why these approaches can perform this
form of disentanglement without supervision (Theorems 1 & 2). Many
architectural innovations in scene mixture models concern the encoder, but our
analysis focuses solely on the structure of the decoder ${\bm{f}}({\bm{z}})$,
which is a shared aspect across multiple methods. Generalization capabilities
of object-centric representations were studied empirically by Dittadi et al.
[10] but did not cover Cartesian-product extrapolation (Corollary 3) on which
we focus here.

Additive decoders are also closely related to the penalty introduced by
Peebles et al. [41] which consists in regularizing the Hessian of the decoder
to be diagonal. In Appendix A.2, we show that “additivity” and “diagonal
Hessian” are equivalent properties. They showed empirically that this penalty
can induce disentanglement on datasets such as CLEVR [24], which is a standard
benchmark for OCRL, but did not provide any formal justification. Our work
provides a rigorous explanation for these successes and highlights the link
between the diagonal Hessian penalty and OCRL.

###  3 Additive decoders for disentanglement & extrapolation

Our theoretical results assume the existence of some data-generating process
describing how the observations ${\bm{x}}$ are generated and, importantly,
what are the “natural” factors of variations.

######  Assumption 1 (Data-generating process).

The set of possible observations is given by a lower dimensional manifold
${\bm{f}}({\mathcal{Z}}^{\textnormal{test}})$ embedded in
${\mathbb{R}}^{d_{x}}$ where ${\mathcal{Z}}^{\textnormal{test}}$ is an open
set of ${\mathbb{R}}^{d_{z}}$ and
${\bm{f}}:{\mathcal{Z}}^{\textnormal{test}}\rightarrow{\mathbb{R}}^{d_{x}}$ is
a $C^{2}$-diffeomorphism onto its image. We will refer to ${\bm{f}}$ as the
_ground-truth decoder_. At training time, the observations are i.i.d. samples
given by ${\bm{x}}={\bm{f}}({\bm{z}})$ where ${\bm{z}}$ is distributed
according to the probability measure
${\mathbb{P}}^{\textnormal{train}}_{\bm{z}}$ with support
${\mathcal{Z}}^{\textnormal{train}}\subseteq{\mathcal{Z}}^{\textnormal{test}}$.
Throughout, we assume that ${\mathcal{Z}}^{\textnormal{train}}$ is regularly
closed (Definition 6).

Intuitively, the ground-truth decoder ${\bm{f}}$ is effectively relating the
“natural factors of variations” ${\bm{z}}$ to the observations ${\bm{x}}$ in a
one-to-one fashion. The map ${\bm{f}}$ is a $C^{2}$-diffeomorphism onto its
image, which means that it is $C^{2}$ (has continuous second derivative) and
that its inverse (restricted to the image of ${\bm{f}}$) is also $C^{2}$.
Analogous assumptions are very common in the literature on nonlinear ICA and
disentanglement [23, 25, 30, 1].

We emphasize the distinction between ${\mathcal{Z}}^{\textnormal{train}}$,
which corresponds to the observations seen during training, and
${\mathcal{Z}}^{\textnormal{test}}$, which corresponds to the set of all
possible images. The case where
${\mathcal{Z}}^{\textnormal{train}}\not={\mathcal{Z}}^{\textnormal{test}}$
will be of particular interest when discussing extrapolation in Section 3.2.
The “regularly closed” condition on ${\mathcal{Z}}^{\textnormal{train}}$ is
mild, as it is satisfied as soon as the distribution of ${\bm{z}}$ has a
density w.r.t. the Lebesgue measure on ${\mathbb{R}}^{d_{z}}$. It is violated,
for example, when ${\bm{z}}$ is a discrete random vector. Figure 2 illustrates
this assumption with simple examples.

Objective. Our analysis is based on the simple objective of reconstructing the
observations ${\bm{x}}$ by learning an encoder
$\hat{\bm{g}}:{\mathbb{R}}^{d_{x}}\rightarrow{\mathbb{R}}^{d_{z}}$ and a
decoder $\hat{\bm{f}}:{\mathbb{R}}^{d_{z}}\rightarrow{\mathbb{R}}^{d_{x}}$.
Note that we assumed implicitly that the dimensionality of the learned
representation matches the dimensionality of the ground-truth. We define the
set of latent codes the encoder can output when evaluated on the training
distribution:

$\displaystyle\hat{\mathcal{Z}}^{\textnormal{train}}:=\hat{\bm{g}}({\bm{f}}({\mathcal{Z}}^{\textnormal{train}}))\,.$
(2)

When the images of the ground-truth and learned decoders match, i.e.
${\bm{f}}({\mathcal{Z}}^{\textnormal{train}})=\hat{\bm{f}}(\hat{\mathcal{Z}}^{\textnormal{train}})$,
which happens when the reconstruction task is solved exactly, one can define
the map
${\bm{v}}:\hat{\mathcal{Z}}^{\textnormal{train}}\rightarrow{\mathcal{Z}}^{\textnormal{train}}$
as

$\displaystyle{\bm{v}}:={\bm{f}}^{-1}\circ\hat{\bm{f}}\,.$ (3)

This function is going to be crucial throughout the work, especially to define
${\mathcal{B}}$-disentanglement (Definition 3), as it relates the learned
representation to the ground-truth representation.

Before introducing our formal definition of additive decoders, we introduce
the following notation: Given a set
${\mathcal{Z}}\subseteq{\mathbb{R}}^{d_{z}}$ and a subset of indices
$B\subseteq[d_{z}]$, let us define ${\mathcal{Z}}_{B}$ to be the projection of
${\mathcal{Z}}$ onto dimensions labelled by the index set $B$. More formally,

$\displaystyle{\mathcal{Z}}_{B}:=\\{{\bm{z}}_{B}\mid{\bm{z}}\in\mathcal{Z}\\}\subseteq{\mathbb{R}}^{|B|}\,.$
(4)

Intuitively, we will say that a decoder is additive when its output is the
summation of the outputs of “object-specific” decoders that depend only on
each latent block ${\bm{z}}_{B}$. This captures the idea that an image can be
seen as the juxatoposition of multiple images which individually correspond to
objects in the scene or natural factors of variations (left of Figure 1). The
following definition makes this precise and slightly more general by adding an
extra invertible function $\sigma$ at the output.

######  Definition 1 ($(\sigma,{\mathcal{B}})$-additive function).

Let $\sigma:{\mathbb{R}}^{d_{x}}\rightarrow{\mathbb{R}}^{d_{x}}$ be an
invertible transformation and let ${\mathcal{B}}$ be a partition of
$[d_{z}]$111Without loss of generality, we assume that the partition
${\mathcal{B}}$ is contiguous, i.e. each $B\in{\mathcal{B}}$ can be written as
$B=\\{i+1,i+2,\dots,i+|B|\\}$.. A function
${\bm{f}}:{\mathcal{Z}}\rightarrow{\mathbb{R}}^{d_{x}}$ is said to be
$(\sigma,{\mathcal{B}})$-additive if there exist functions
${\bm{f}}^{(B)}:{\mathcal{Z}}_{B}\rightarrow{\mathbb{R}}^{d_{x}}$ for all
${B\in{\mathcal{B}}}$ such that

$\displaystyle\forall{\bm{z}}\in{\mathcal{Z}},{\bm{f}}({\bm{z}})=\sigma(\sum_{B\in{\mathcal{B}}}{\bm{f}}^{(B)}({\bm{z}}_{B}))\,.$
(5)

This additivity property will be central to our analysis as it will be the
driving force of identifiability (Theorem 1 & 2) and Cartesian-product
extrapolation (Corollary 3). Since $\sigma$ and ${\mathcal{B}}$ are fixed
throughout, we will simply say that a function is additive to mean that it is
$(\sigma,{\mathcal{B}})$-additive. Note that the presence of $\sigma$ allows a
wider applicability of the result. For example, one can obtain a
“multiplicative decoder” by taking $\sigma({\bm{x}}):=\exp({\bm{x}})$, where
$\exp$ is applied element-wise.

Differences with OCRL in practice. We point out that, although the additive
decoders make intuitive sense for OCRL, they are not expressive enough to
represent the “masked decoders” typically used in practice (Equation (1)). The
lack of additivity stems from the normalization in the masks
${\bm{m}}^{(B)}({\bm{z}})$. We hypothesize that studying the simpler additive
decoders might still reveal interesting phenomena present in modern OCRL
approaches due to their resemblance. Another difference is that, in practice,
the same object-specific decoder ${\bm{f}}^{(\text{obj})}$ is applied to every
latent block ${\bm{z}}_{B}$. Our theory allows for these functions to be
different, but also applies when functions are the same. Additionally, this
parameter sharing across ${\bm{f}}^{(B)}$ enables modern methods to have a
variable number of objects across samples, an important practical point our
theory does not cover.

####  3.1 Identifiability analysis

We now study the identifiability of additive decoders and show how they can
yield disentanglement. Our definition of disentanglement will rely on
partition-respecting permutations:

######  Definition 2 (Partition-respecting permutations).

Let ${\mathcal{B}}$ be a partition of $\\{1,...,d_{z}\\}$. A permutation $\pi$
over $\\{1,...,d_{z}\\}$ respects ${\mathcal{B}}$ if, for all
$B\in{\mathcal{B}},\ \pi(B)\in{\mathcal{B}}$.

Essentially, a permutation that respects ${\mathcal{B}}$ is one which can
permute blocks of ${\mathcal{B}}$ and permute elements within a block, but
cannot “mix” blocks together. We now introduce
${\mathcal{B}}$-disentanglement.

######  Definition 3 (${\mathcal{B}}$-disentanglement).

A learned decoder
$\hat{\bm{f}}:{\mathbb{R}}^{d_{z}}\rightarrow{\mathbb{R}}^{d_{x}}$ is said to
be ${\mathcal{B}}$-disentangled w.r.t. the ground-truth decoder ${\bm{f}}$
when
${\bm{f}}({\mathcal{Z}}^{\textnormal{train}})=\hat{\bm{f}}(\hat{\mathcal{Z}}^{\textnormal{train}})$
and the mapping ${\bm{v}}:={\bm{f}}^{-1}\circ\hat{\bm{f}}$ is a diffeomorphism
from $\hat{\mathcal{Z}}^{\textnormal{train}}$ to
${\mathcal{Z}}^{\textnormal{train}}$ satisfying the following property: there
exists a permutation $\pi$ respecting ${\mathcal{B}}$ such that, for all
$B\in{\mathcal{B}}$, there exists a function
$\bar{\bm{v}}_{\pi(B)}:\hat{\mathcal{Z}}^{\textnormal{train}}_{B}\rightarrow{\mathcal{Z}}^{\textnormal{train}}_{\pi(B)}$
such that, for all ${\bm{z}}\in\hat{\mathcal{Z}}^{\textnormal{train}}$,
${\bm{v}}_{\pi(B)}({\bm{z}})=\bar{\bm{v}}_{\pi(B)}({\bm{z}}_{B})$. In other
words, ${\bm{v}}_{\pi(B)}({\bm{z}})$ depends only on ${\bm{z}}_{B}$.

Thus, ${\mathcal{B}}$-disentanglement means that the blocks of latent
dimensions ${\bm{z}}_{B}$ are disentangled from one another, but that
variables within a given block might remain entangled.

######  Example 1.

To illustrate ${\mathcal{B}}$-disentanglement, imagine a scene consisting of
two balls moving around in 2D where the “ground-truth” representation is given
by ${\bm{z}}=(x^{1},y^{1},x^{2},y^{2})$ where ${\bm{z}}_{B_{1}}=(x^{1},y^{1})$
and ${\bm{z}}_{B_{2}}=(x^{2},y^{2})$ are the coordinates of each ball (here,
${\mathcal{B}}:=\\{\\{1,2\\},\\{3,4\\}\\}$). In that case, a learned
representation is ${\mathcal{B}}$-disentangled when the balls are disentangled
from one another. However, the basis in which the position of each ball is
represented might differ in both representations.

The first identifiability result (Theorem 1) shows a weaker form of
disentanglement we call local ${\mathcal{B}}$-disentanglement. It means the
Jacobian matrix of ${\bm{v}}$ has a “block-permutation” structure everywhere.

######  Definition 4 (Local ${\mathcal{B}}$-disentanglement).

A learned decoder
$\hat{\bm{f}}:{\mathbb{R}}^{d_{z}}\rightarrow{\mathbb{R}}^{d_{x}}$ is said to
be locally ${\mathcal{B}}$-disentangled w.r.t. the ground-truth decoder
${\bm{f}}$ when
${\bm{f}}({\mathcal{Z}}^{\textnormal{train}})=\hat{\bm{f}}(\hat{\mathcal{Z}}^{\textnormal{train}})$
and the mapping ${\bm{v}}:={\bm{f}}^{-1}\circ\hat{\bm{f}}$ is a diffeomorphism
from $\hat{\mathcal{Z}}^{\textnormal{train}}$ to
${\mathcal{Z}}^{\textnormal{train}}$ with a mapping
${\bm{v}}:\hat{\mathcal{Z}}^{\textnormal{train}}\rightarrow{\mathcal{Z}}^{\textnormal{train}}$
satisfying the following property: for all
${\bm{z}}\in\hat{\mathcal{Z}}^{\textnormal{train}}$, there exists a
permutation $\pi$ respecting ${\mathcal{B}}$ such that, for all
$B\in{\mathcal{B}}$, the columns of
$D{\bm{v}}_{\pi(B)}({\bm{z}})\in{\mathbb{R}}^{|B|\times d_{z}}$ outside block
$B$ are zero.

In Appendix A.3, we provide three examples where local disentanglement holds
but not global disentanglement. The first one illustrates how having a
disconnected support can allow for a permutation $\pi$ (from Definition 4)
that changes between disconnected regions of the support. The last two
examples show how, even if the permutation stays the same throughout the
support, we can still violate global disentanglement, even with a connected
support.

We now state the main identifiability result of this work which provides
conditions to guarantee local disentanglement. We will then see how to go from
local to global disentanglement in the subsequent Theorem 2. For pedagogical
reasons, we delay the formalization of the sufficient nonlinearity Assumption
2 on which the result crucially relies.

######  Theorem 1 (Local disentanglement via additive decoders).

Suppose that the data-generating process satisfies Assumption 1, that the
learned decoder
$\hat{\bm{f}}:{\mathbb{R}}^{d_{z}}\rightarrow{\mathbb{R}}^{d_{x}}$ is a
$C^{2}$-diffeomorphism, that the encoder
$\hat{\bm{g}}:{\mathbb{R}}^{d_{x}}\rightarrow{\mathbb{R}}^{d_{z}}$ is
continuous, that both ${\bm{f}}$ and $\hat{\bm{f}}$ are additive (Definition
1) and that ${\bm{f}}$ is sufficiently nonlinear as formalized by Assumption
2. Then, if $\hat{\bm{f}}$ and $\hat{\bm{g}}$ solve the reconstruction problem
on the training distribution, i.e.
${\mathbb{E}}^{\textnormal{train}}||{\bm{x}}-\hat{\bm{f}}(\hat{\bm{g}}({\bm{x}}))||^{2}=0$,
we have that $\hat{\bm{f}}$ is locally ${\mathcal{B}}$-disentangled w.r.t.
${\bm{f}}$ (Definition 4) .

The proof of Theorem 1, which can be found in Appendix A.4, is inspired from
Hyvärinen et al. [23]. The essential differences are that (i) they leverage
the additivity of the conditional log-density of ${\bm{z}}$ given an auxiliary
variable ${\bm{u}}$ (i.e. conditional independence) instead of the additivity
of the decoder function ${\bm{f}}$, (ii) we extend their proof techniques to
allow for “block” disentanglement, i.e. when ${\mathcal{B}}$ is not the
trivial partition $\\{\\{1\\},\dots,\\{d_{z}\\}\\}$, (iii) the asssumption
“sufficient variability” of the prior $p({\bm{z}}\mid{\bm{u}})$ of Hyvärinen
et al. [23] is replaced by an analogous assumption of “sufficient
nonlinearity” of the decoder ${\bm{f}}$ (Assumption 2), and (iv) we consider
much more general supports ${\mathcal{Z}}^{\textnormal{train}}$ which makes
the jump from local to global disentanglement less direct in our case.

Sufficient nonlinearity. The following assumption is key in proving Theorem 2,
as it requires that the ground-truth decoder is “sufficiently nonlinear”. This
is reminiscent of the “sufficient variability” assumptions found in the
nonlinear ICA litterature, which usually concerns the distribution of the
latent variable ${\bm{z}}$ as opposed to the decoder ${\bm{f}}$ [21, 22, 23,
25, 26, 30, 49]. We clarify this link in Appendix A.5 and provide intuitions
why sufficient nonlinearity can be satisfied when $d_{x}\gg d_{z}$.

######  Assumption 2 (Sufficient nonlinearity of ${\bm{f}}$).

Let $q:=d_{z}+\sum_{B\in{\mathcal{B}}}\frac{|B|(|B|+1)}{2}$. For all
${\bm{z}}\in{\mathcal{Z}}^{\textnormal{train}}$, ${\bm{f}}$ is such that the
following matrix has independent columns (i.e. full column-rank):

$\displaystyle{\bm{W}}({\bm{z}})$
$\displaystyle:=\left[\left[D_{i}{\bm{f}}^{(B)}({\bm{z}}_{B})\right]_{i\in B}\
\left[D^{2}_{i,i^{\prime}}{\bm{f}}^{(B)}({\bm{z}}_{B})\right]_{(i,i^{\prime})\in
B_{\leq}^{2}}\right]_{B\in{\mathcal{B}}}\in{\mathbb{R}}^{d_{x}\times q}\,,$
(6)

where $B^{2}_{\leq}:=B^{2}\cap\\{(i,i^{\prime})\mid i^{\prime}\leq i\\}$. Note
this implies $d_{x}\geq q$.

The following example shows that Theorem 1 does not contradict the
nonidentifiability of linear ICA.

######  Example 2 (Importance of Assumption 2).

Suppose ${\bm{f}}({\bm{z}})={\bm{A}}{\bm{z}}$ and take
$\hat{\bm{f}}({\bm{z}}):={\bm{f}}({\bm{V}}{\bm{z}})$ where
${\bm{A}}\in{\mathbb{R}}^{d_{x}\times d_{z}}$ is full rank and
${\bm{V}}\in{\mathbb{R}}^{d_{z}\times d_{z}}$ is invertible. By construction,
${\bm{v}}({\bm{z}}):={\bm{f}}^{-1}\circ\hat{\bm{f}}({\bm{z}})={\bm{V}}{\bm{z}}$.
Also, both ${\bm{f}}({\bm{z}})$ and $\hat{\bm{f}}({\bm{z}})$ are additive
since
${\bm{f}}({\bm{z}})=\sum_{B\in{\mathcal{B}}}{\bm{A}}_{\cdot,B}{\bm{z}}_{B}$
and
$\hat{\bm{f}}({\bm{z}})=\sum_{B\in{\mathcal{B}}}({\bm{A}}{\bm{V}})_{\cdot,B}{\bm{z}}_{B}$,
even if ${\bm{V}}$ does not have a “block-permutation structure”, i.e. no
disentanglement. The reason we cannot apply Theorem 1 here is because
Assumption 2 is not satisfied. Indeed, the second derivatives of
${\bm{f}}^{(B)}({\bm{z}}_{B}):={\bm{A}}_{\cdot,B}{\bm{z}}_{B}$ are all zero
and hence ${\bm{W}}({\bm{z}})$ cannot have full column-rank.

######  Example 3 (A sufficiently nonlinear ${\bm{f}}$).

In Appendix A.6 we show numerically that the function

$\displaystyle{\bm{f}}({\bm{z}}):=[{\bm{z}}_{1},{\bm{z}}_{1}^{2},{\bm{z}}_{1}^{3},{\bm{z}}_{1}^{4}]^{\top}+[({\bm{z}}_{2}+1),({\bm{z}}_{2}+1)^{2},({\bm{z}}_{2}+1)^{3},({\bm{z}}_{2}+1)^{4}]^{\top}$
(7)

is a diffeomorphism from the square $[-1,0]\times[0,1]$ to its image that
satisfies Assumption 2.

#####  3.1.1 From local to global disentanglement

The following result provides additional assumptions to guarantee global
disentanglement (Definition 3) as opposed to only local disentanglement
(Definition 4). See Appendix A.7 for its proof.

######  Theorem 2 (From local to global disentanglement).

Suppose that all the assumptions of Theorem 1 hold. Additionally, assume
${\mathcal{Z}}^{\textnormal{train}}$ is path-connected (Definition 8) and that
the block-specific decoders ${\bm{f}}^{(B)}$ and $\hat{\bm{f}}^{(B)}$ are
injective for all blocks $B\in{\mathcal{B}}$. Then, if $\hat{\bm{f}}$ and
$\hat{\bm{g}}$ solve the reconstruction problem on the training distribution,
i.e.
${\mathbb{E}}^{\textnormal{train}}||{\bm{x}}-\hat{\bm{f}}(\hat{\bm{g}}({\bm{x}}))||^{2}=0$,
we have that $\hat{\bm{f}}$ is (globally) ${\mathcal{B}}$-disentangled w.r.t.
${\bm{f}}$ (Definition 3) and, for all $B\in{\mathcal{B}}$,

$\displaystyle\hat{\bm{f}}^{(B)}({\bm{z}}_{B})={\bm{f}}^{(\pi(B))}(\bar{\bm{v}}_{\pi(B)}({\bm{z}}_{B}))+{\bm{c}}^{(B)}\text{,
for all }{\bm{z}}_{B}\in\hat{\mathcal{Z}}^{\textnormal{train}}_{B}\,,$ (8)

where the functions $\bar{\bm{v}}_{\pi(B)}$ are from Defintion 3 and the
vectors ${\bm{c}}^{(B)}\in{\mathbb{R}}^{d_{x}}$ are constants such that
$\sum_{B\in{\mathcal{B}}}{\bm{c}}^{(B)}=0$. We also have that the functions
$\bar{\bm{v}}_{\pi(B)}:\hat{\mathcal{Z}}_{B}^{\textnormal{train}}\rightarrow{\mathcal{Z}}_{\pi(B)}^{\textnormal{train}}$
are $C^{2}$-diffeomorphisms and have the following form:

$\displaystyle\bar{\bm{v}}_{\pi(B)}({\bm{z}}_{B})=({\bm{f}}^{\pi(B)})^{-1}(\hat{\bm{f}}^{(B)}({\bm{z}}_{B})-{\bm{c}}^{(B)}),\
\text{for all\ }{\bm{z}}_{B}\in\hat{\mathcal{Z}}^{\textnormal{train}}_{B}\,.$
(9)

Equation (8) in the above result shows that each block-specific learned
decoder $\hat{\bm{f}}^{(B)}$ is “imitating” a block-specific ground-truth
decoder ${\bm{f}}^{\pi(B)}$. Indeed, the “object-specific” image outputted by
the decoder $\hat{\bm{f}}^{(B)}$ evaluated at some
${\bm{z}}_{B}\in\hat{\mathcal{Z}}^{\textnormal{train}}_{B}$ is the same as the
image outputted by ${\bm{f}}^{(B)}$ evaluated at
${\bm{v}}({\bm{z}}_{B})\in{\mathcal{Z}}^{\textnormal{train}}_{B}$, up to an
additive constant vector ${\bm{c}}^{(B)}$. These constants cancel each other
out when taking the sum of the block-specific decoders.

Figure 2: Illustrating regularly closed sets (Definition 6) and path-connected
sets (Definition 8). Theorem 2 requires ${\mathcal{Z}}^{\textnormal{train}}$
to satisfy both properties.

Equation (9) provides an explicit form for the function
$\bar{\bm{v}}_{\pi(B)}$, which is essentially the learned block-specific
decoder composed with the inverse of the ground-truth block-specific decoder.

Additional assumptions to go from local to global. Assuming that the support
of ${\mathbb{P}}^{\textnormal{train}}_{\bm{z}}$,
${\mathcal{Z}}^{\textnormal{train}}$, is path-connected (see Definition 8 in
appendix) is useful since it prevents the permutation $\pi$ of Definition 4
from changing between two disconnected regions of
$\hat{\mathcal{Z}}^{\textnormal{train}}$. See Figure 2 for an illustration. In
Appendix A.8, we discuss the additional assumption that each ${\bm{f}}^{(B)}$
must be injective and show that, in general, it is not equivalent to the
assumption that $\sum_{B\in{\mathcal{B}}}{\bm{f}}^{(B)}$ is injective.

####  3.2 Cartesian-product extrapolation

Figure 3: Illustration of Definition 5.

In this section, we show how a learned additive decoder can be used to
generate images ${\bm{x}}$ that are “out of support” in the sense that
${\bm{x}}\not\in{\bm{f}}({\mathcal{Z}}^{\textnormal{train}})$, but that are
still on the manifold of “reasonable” images, i.e.
${\bm{x}}\in{\bm{f}}({\mathcal{Z}}^{\textnormal{test}})$.

To characterize the set of images the learned decoder can generate, we will
rely on the notion of “cartesian-product extension”, which we define next.

######  Definition 5 (Cartesian-product extension).

Given a set ${\mathcal{Z}}\subseteq{\mathbb{R}}^{d_{z}}$ and partition
${\mathcal{B}}$ of $[d_{z}]$, we define the Cartesian-product extension of
${\mathcal{Z}}$ as

$\displaystyle\textnormal{CPE}_{\mathcal{B}}({\mathcal{Z}}):=\prod_{B\in{\mathcal{B}}}{\mathcal{Z}}_{B}\,,\text{where
${\mathcal{Z}}_{B}:=\\{{\bm{z}}_{B}\mid{\bm{z}}\in{\mathcal{Z}}\\}$.}$ (10)

The above definition is illustrated in Figure 3. The Cartesian-product
extension of ${\mathcal{Z}}$, $\text{CPE}_{\mathcal{B}}({\mathcal{Z}})$, is
indeed an extension of ${\mathcal{Z}}$ since ${\mathcal{Z}}$ is typically a
proper subset of $\prod_{B\in{\mathcal{B}}}{\mathcal{Z}}_{\mathcal{B}}$.

Let us define
$\bar{\bm{v}}:\textnormal{CPE}_{\mathcal{B}}(\hat{\mathcal{Z}}^{\textnormal{train}})\rightarrow\textnormal{CPE}_{\mathcal{B}}({\mathcal{Z}}^{\textnormal{train}})$
to be the natural extension of the function
${\bm{v}}:\hat{\mathcal{Z}}^{\textnormal{train}}\rightarrow{\mathcal{Z}}^{\textnormal{train}}$.
More explicitly, $\bar{\bm{v}}$ is the “concatenation” of the functions
$\bar{\bm{v}}_{B}$ given in Definition 3:

$\displaystyle\bar{\bm{v}}({\bm{z}})^{\top}:=[\bar{\bm{v}}_{B_{1}}({\bm{z}}_{\pi^{-1}(B_{1})})^{\top}\cdots\bar{\bm{v}}_{B_{\ell}}({\bm{z}}_{\pi^{-1}(B_{\ell})})^{\top}]\,,$
(11)

where $\ell$ is the number of blocks in ${\mathcal{B}}$. This map is a
diffeomorphism because each $\bar{\bm{v}}_{\pi(B)}$ is a diffeomorphism from
$\hat{\mathcal{Z}}^{\textnormal{train}}_{B}$ to
${\mathcal{Z}}^{\textnormal{train}}_{\pi(B)}$ (Theorem 2).

We already know that
$\hat{\bm{f}}({\bm{z}})={\bm{f}}\circ\bar{\bm{v}}({\bm{z}})$ for all
${\bm{z}}\in\hat{\mathcal{Z}}^{\textnormal{train}}$. The following result
shows that this equality holds in fact on the larger set
$\textnormal{CPE}_{\mathcal{B}}(\hat{\mathcal{Z}}^{\textnormal{train}})$, the
Cartesian-product extension of $\hat{\mathcal{Z}}^{\textnormal{train}}$. See
right of Figure 1 for an illustration of the following corollary.

######  Corollary 3 (Cartesian-product extrapolation).

Suppose the assumptions of Theorem 2 holds. Then,

$\displaystyle\text{for all
${\bm{z}}\in\textnormal{CPE}_{\mathcal{B}}(\hat{\mathcal{Z}}^{\textnormal{train}})$,}\
\sigma(\sum_{B\in{\mathcal{B}}}\hat{\bm{f}}^{(B)}({\bm{z}}_{B}))=\sigma(\sum_{B\in{\mathcal{B}}}{\bm{f}}^{(\pi(B))}(\bar{\bm{v}}_{\pi(B)}({\bm{z}}_{B})))\,.$
(12)

Furthermore, if
$\textnormal{CPE}_{\mathcal{B}}({\mathcal{Z}}^{\textnormal{train}})\subseteq{\mathcal{Z}}^{\textnormal{test}}$,
then
$\hat{\bm{f}}(\textnormal{CPE}_{\mathcal{B}}(\hat{\mathcal{Z}}^{\textnormal{train}}))\subseteq{\bm{f}}({\mathcal{Z}}^{\textnormal{test}})$.

Equation (12) tells us that the learned decoder $\hat{\bm{f}}$ “imitates” the
ground-truth ${\bm{f}}$ not just over
$\hat{\mathcal{Z}}^{\textnormal{train}}$, but also over its Cartesian-product
extension. This is important since it guarantees that we can generate
observations never seen during training as follows: Choose a latent vector
${\bm{z}}^{\text{new}}$ that is in the Cartesian-product extension of
$\hat{\mathcal{Z}}^{\textnormal{train}}$, but not in
$\hat{\mathcal{Z}}^{\textnormal{train}}$ itself, i.e.
${\bm{z}}^{\text{new}}\in\textnormal{CPE}_{\mathcal{B}}(\hat{\mathcal{Z}}^{\textnormal{train}})\setminus\hat{\mathcal{Z}}^{\textnormal{train}}$.
Then, evaluate the learned decoder on ${\bm{z}}^{\text{new}}$ to get
${\bm{x}}^{\text{new}}:=\hat{\bm{f}}({\bm{z}}^{\text{new}})$. By Corollary 3,
we know that
${\bm{x}}^{\text{new}}={\bm{f}}\circ\bar{\bm{v}}({\bm{z}}^{\text{new}})$, i.e.
it is the observation one would have obtain by evaluating the ground-truth
decoder ${\bm{f}}$ on the point
$\bar{\bm{v}}({\bm{z}}^{\text{new}})\in\textnormal{CPE}_{\mathcal{B}}({\mathcal{Z}}^{\textnormal{train}})$.
In addition, this ${\bm{x}}^{\text{new}}$ has never been seen during training
since
$\bar{\bm{v}}({\bm{z}}^{\text{new}})\not\in\bar{\bm{v}}(\hat{\mathcal{Z}}^{\textnormal{train}})={\mathcal{Z}}^{\textnormal{train}}$.
The experiment of Figure 4 illustrates this procedure.

About the extra assumption
“$\textnormal{CPE}_{\mathcal{B}}({\mathcal{Z}}^{\textnormal{train}})\subseteq{\mathcal{Z}}^{\textnormal{test}}$”.
Recall that, in Assumption 1, we interpreted
${\bm{f}}({\mathcal{Z}}^{\textnormal{test}})$ to be the set of “reasonable”
observations ${\bm{x}}$, of which we only observe a subset
${\bm{f}}({\mathcal{Z}}^{\textnormal{train}})$. Under this interpretation,
${\mathcal{Z}}^{\textnormal{test}}$ is the set of reasonable values for the
vector ${\bm{z}}$ and the additional assumption that
$\textnormal{CPE}_{\mathcal{B}}({\mathcal{Z}}^{\textnormal{train}})\subseteq{\mathcal{Z}}^{\textnormal{test}}$
in Corollary 3 requires that the Cartesian-product extension of
${\mathcal{Z}}^{\textnormal{train}}$ consists only of reasonable values of
${\bm{z}}$. From this assumption, we can easily conclude that
$\hat{\bm{f}}(\textnormal{CPE}_{\mathcal{B}}(\hat{\mathcal{Z}}^{\textnormal{train}}))\subseteq{\bm{f}}({\mathcal{Z}}^{\textnormal{test}})$,
which can be interpreted as: “The novel observations ${\bm{x}}^{\text{new}}$
obtained via Cartesian-product extrapolation are reasonable”. Appendix A.10
describes an example where the assumption is violated, i.e.
$\textnormal{CPE}_{\mathcal{B}}({\mathcal{Z}}^{\textnormal{train}})\not\subseteq{\mathcal{Z}}^{\textnormal{test}}$.
The practical implication of this is that the new observations
${\bm{x}}^{\text{new}}$ obtained via Cartesian-product extrapolation might not
always be reasonable.

Disentanglement is not enough for extrapolation. To the best of our knowledge,
Corollary 3 is the first result that formalizes how disentanglement can induce
extrapolation. We believe it illustrates the fact that disentanglement alone
is not sufficient to enable extrapolation and that one needs to restrict the
hypothesis class of decoders in some way. Indeed, given a learned decoder
$\hat{\bm{f}}$ that is disentangled w.r.t. ${\bm{f}}$ on the training support
${\mathcal{Z}}^{\textnormal{train}}$, one cannot guarantee both decoders will
“agree” outside the training domain without further restricting $\hat{\bm{f}}$
and ${\bm{f}}$. This work has focused on “additivity”, but we believe other
types of restriction could correspond to other types of extrapolation.

| ScalarLatents | BlockLatents | BlockLatents
---|---|---|---
|  |  (independent ${\bm{z}}$) |  (dependent ${\bm{z}}$)
Decoders | RMSE | $\text{LMS}_{\text{Spear}}$ | $\text{RMSE}^{\text{OOS}}$ | $\text{LMS}_{\text{Spear}}^{\text{OOS}}$ | RMSE | $\text{LMS}_{\text{Tree}}$ | RMSE | $\text{LMS}_{\text{Tree}}$
Non-add. |  .01$\pm$.001 |  84.4$\pm$14.23 |  .11$\pm$.06 |  82.3$\pm$.07 |  .03$\pm$.01 |  70.2$\pm$17.5 |  .02$\pm$.005 |  87.4$\pm$6.7
Additive |  .01$\pm$.002 | 96.2$\pm$11.4 |  .02$\pm$.008 | 94.5$\pm$14.7 |  .02$\pm$.005 | 91.9$\pm$12.5 |  .02$\pm$.003 | 99.4$\pm$1.4
Table 1: Reporting reconstruction mean squared error (RMSE $\downarrow$) and
the Latent Matching Score (LMS $\uparrow$) for the three datasets considered:
ScalarLatents and BlockLatents with independent and dependent latents. Runs
were repeated with 10 random initializations. $\text{RMSE}^{\text{OOS}}$ and
$\text{LMS}_{\text{Spear}}^{\text{OOS}}$ are the same metric but evaluated out
of support (see Appendix B.3 for details). While the standard deviation is
high, the differences are still clear as can be seen in their box plot version
in Appendix B.4.

###  4 Experiments

We now present empirical validations of the theoretical results presented
earlier. To achieve this, we compare the ability of additive and non-additive
decoders to both identify ground-truth latent factors (Theorems 1 & 2) and
extrapolate (Corollary 3) when trained to solve the reconstruction task on
simple images ($64\times 64\times 3$) consisting of two balls moving in space
[2]. See Appendix B.1 for training details. We consider two datasets: one
where the two ball positions can only vary along the $y$-axis (ScalarLatents)
and one where the positions can vary along both the $x$ and $y$ axes
(BlockLatents).

ScalarLatents: The ground-truth latent vector ${\bm{z}}\in{\mathbb{R}}^{2}$ is
such that ${\bm{z}}_{1}$ and ${\bm{z}}_{2}$ corresponds to the height
(y-coordinate) of the first and second ball, respectively. Thus the partition
is simply ${\mathcal{B}}=\\{\\{1\\},\\{2\\}\\}$ (each object has only one
latent factor). This simple setting is interesting to study since the low
dimensionality of the latent space ($d_{z}=2$) allows for exhaustive
visualizations like Figure 4. To study Cartesian-product extrapolation
(Corollary 3), we sample the latent factor ${\bm{z}}$ uniformly from the
L-shaped support given by
${\mathcal{Z}}^{\textnormal{train}}:=[0,1]\times[0,1]\setminus[0.5,1]\times[0.5,1]$.
This means the training set does not contain images where both balls appear in
the upper half of the image.

BlockLatents: The ground-truth latent vector ${\bm{z}}\in{\mathbb{R}}^{4}$ is
such that ${\bm{z}}_{\\{1,2\\}}$ and ${\bm{z}}_{\\{3,4\\}}$ correspond to the
$xy$ position of the first and second ball, respectively (the partition is
simply ${\mathcal{B}}=\\{\\{1,2\\},\\{3,4\\}\\}$, i.e. each object has two
latent factors). Thus, this more challenging setting illustrates “block-
disentanglement”. The latent ${\bm{z}}$ is sampled uniformly from the
hypercube $[0,1]^{4}$ but the images presenting occlusion (when a ball is
behind another) are rejected from the dataset. We discuss how additive
decoders cannot model images presenting occlusion in Appendix A.11. We also
present an additional version of this dataset where we sample from the
hypercube $[0,1]^{4}$ with dependencies. See Appendix B.2 for more details
about data generation.

Evaluation metrics: To evaluate disentanglement, we compute a matrix of scores
$(s_{B,B^{\prime}})\in{\mathbb{R}}^{\ell\times\ell}$ where $\ell$ is the
number of blocks in ${\mathcal{B}}$ and $s_{B,B^{\prime}}$ is a score
measuring how well we can predict the ground-truth block ${\bm{z}}_{B}$ from
the learned latent block
$\hat{\bm{z}}_{B^{\prime}}=\hat{\bm{g}}_{B^{\prime}}({\bm{x}})$ outputted by
the encoder. The final Latent Matching Score (LMS) is computed as
$\textnormal{LMS}=\operatorname*{arg\,max}_{\pi\in\mathfrak{S}_{\mathcal{B}}}\frac{1}{\ell}\sum_{B\in{\mathcal{B}}}s_{B,\pi(B)}$,
where $\mathfrak{S}_{\mathcal{B}}$ is the set of permutations respecting
${\mathcal{B}}$ (Definition 2). When
${\mathcal{B}}:=\\{\\{1\\},\dots,\\{d_{z}\\}\\}$ and the score used is the
absolute value of the correlation, LMS is simply the mean correlation
coefficient (MCC), which is widely used in the nonlinear ICA literature [21,
22, 23, 25, 30]. Because our theory guarantees recovery of the latents only up
to invertible and potentially nonlinear transformations, we use the Spearman
correlation, which can capture nonlinear relationships unlike the Pearson
correlation. We denote this score by $\text{LMS}_{\text{Spear}}$ and will use
it in the dataset ScalarLatents. For the BlockLatents dataset, we cannot use
Spearman correlation (because ${\bm{z}}_{B}$ are two dimensional). Instead, we
take the score $s_{B,B^{\prime}}$ to be the $R^{2}$ score of a regression
tree. We denote this score by $\text{LMS}_{\text{tree}}$. There are subtleties
to take care of when one wants to evaluate $\text{LMS}_{\text{tree}}$ on a
non-additive model due to the fact that the learned representation does not
have a natural partition ${\mathcal{B}}$. We must thus search over partitions.
We discuss this and provide further details on the metrics in Appendix B.3.

####  4.1 Results

(a) Additive decoder

(b) Non-additive decoder

Figure 4:  Figure (a) shows the learned latent space,
$\hat{\mathcal{Z}}^{\textnormal{train}}$, and the corresponding reconstructed
images of the additive decoder with median $\text{LMS}_{\text{Spear}}$ among
runs performed on the ScalarLatents dataset. Figure (b) shows the same thing
for the non-additive decoder. The red dots correspond to latent factors used
to generate the images and the red square highlights extrapolated images.

(a) Additive Decoder

(b) Non-Additive Decoder

Figure 5: Latent responses for the case of independent latents in the
BlockLatent dataset. In each plot, we report the latent factors predicted from
multiple images where one ball moves along only one axis at a time. For the
additive case, at most two latents change, as it should, while more than two
latents change for the non-additive case. See Appendix B.5 for details.

Additivity is important for disentanglement. Table 1 shows that the additive
decoder obtains a much higher $\text{LMS}_{\text{Spear}}$ than its non-
additive counterpart on all three datasets considered, even if both decoders
have very small reconstruction errors. This is corroborated by the
visualizations of Figures 4 & 5. Appendix B.5 additionally shows object-
specific reconstructions for the BlockLatents dataset. We emphasize that
disentanglement is possible even when the latent factors are dependent (or
causally related), as shown on the ScalarLatents dataset (L-shaped support
implies dependencies) and on the BlockLatents dataset with dependencies (Table
1). Note that prior works have relied on interventions [3, 2, 5] or Cartesian-
product supports [48, 44] to deal with dependencies.

Additivity is important for Cartesian-product extrapolation. Figure 4
illustrates that the additive decoder can generate images that are outside the
training domain (both balls in upper half of the image) while its non-additive
counterpart cannot. Furthermore, Table 1 also corroborates this showing that
the “out-of-support” (OOS) reconstruction MSE and $\text{LMS}_{\text{Spear}}$
(evaluated only on the samples never seen during training) are significantly
better for the additive than for the non-additive decoder.

Importance of connected support. Theorem 2 required that the support of the
latent factors, ${\mathcal{Z}}^{\textnormal{train}}$, was path-connected.
Appendix B.6 shows experiments where this assumption is violated, which yields
lower $\text{LMS}_{\text{Spear}}$ for the additive decoder, thus highlighting
the importance of this assumption.

###  5 Conclusion

We provided an in-depth identifiability analysis of additive decoders, which
bears resemblance to standard decoders used in OCRL, and introduced a novel
theoretical framework showing how this architecture can generate reasonable
images never seen during training via “Cartesian-product extrapolation”. We
validated empirically both of these results and confirmed that additivity was
indeed crucial. By studying rigorously how disentanglement can induce
extrapolation, our work highlighted the necessity of restricting the decoder
to extrapolate and set the stage for future works to explore disentanglement
and extrapolation in other function classes such as masked decoders typically
used in OCRL. We believe this line of work has the potential of expanding our
understanding of creativity in generative models, ultimately resulting in
representations that generalizes better.

### Acknowledgements

This research was partially supported by the Canada CIFAR AI Chair Program, by
an IVADO excellence PhD scholarship and by Samsung Electronics Co., Ldt. The
experiments were in part enabled by computational resources provided by by
Calcul Québec (calculquebec.ca) and the Digital Research Alliance of Canada
(alliancecan.ca). Simon Lacoste-Julien is a CIFAR Associate Fellow in the
Learning in Machines & Brains program.

### References

  * Ahuja et al. [2022a] K. Ahuja, J. Hartford, and Y. Bengio.  Properties from mechanisms: an equivariance perspective on identifiable representation learning.  In _International Conference on Learning Representations_ , 2022a.
  * Ahuja et al. [2022b] K. Ahuja, J. Hartford, and Y. Bengio.  Weakly supervised representation learning with sparse perturbations, 2022b.
  * Ahuja et al. [2022c] K. Ahuja, Y. Wang, D. Mahajan, and Y. Bengio.  Interventional causal representation learning.  _arXiv preprint arXiv:2209.11924_ , 2022c.
  * Bengio et al. [2013] Y. Bengio, A. Courville, and P. Vincent.  Representation learning: A review and new perspectives.  _IEEE transactions on pattern analysis and machine intelligence_ , 2013.
  * Brehmer et al. [2022] J. Brehmer, P. De Haan, P. Lippe, and T. Cohen.  Weakly supervised causal representation learning.  In _Advances in Neural Information Processing Systems_ , 2022.
  * Buchholz et al. [2022] S. Buchholz, M. Besserve, and B. Schölkopf.  Function classes for identifiable nonlinear independent component analysis.  In _Advances in Neural Information Processing Systems_ , 2022.
  * Burgess et al. [2019] C. P. Burgess, L. Matthey, N. Watters, R. Kabra, I. Higgins, M. Botvinick, and A. Lerchner.  Monet: Unsupervised scene decomposition and representation, 2019.
  * Crawford and Pineau [2019] E. Crawford and J. Pineau.  Spatially invariant unsupervised object detection with convolutional neural networks.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2019\.
  * d’Avila Garcez and Lamb [2020] A. S. d’Avila Garcez and L. Lamb.  Neurosymbolic AI: The 3rd wave.  _ArXiv_ , abs/2012.05876, 2020.
  * Dittadi et al. [2022] A. Dittadi, S. S. Papa, M. De Vita, B. Schölkopf, O. Winther, and F. Locatello.  Generalization and robustness implications in object-centric learning.  In _Proceedings of the 39th International Conference on Machine Learning_ , 2022.
  * Engelcke et al. [2020] M. Engelcke, A. R. Kosiorek, O. P. Jones, and I. Posner.  Genesis: Generative scene inference and sampling with object-centric latent representations.  In _International Conference on Learning Representations_ , 2020.
  * Eslami et al. [2016] S. M. A. Eslami, N. Heess, T. Weber, Y. Tassa, D. Szepesvari, K. Kavukcuoglu, and G. E. Hinton.  Attend, infer, repeat: Fast scene understanding with generative models.  In _Advances in Neural Information Processing Systems_ , 2016.
  * Fodor and Pylyshyn [1988] J. A. Fodor and Z. W. Pylyshyn.  Connectionism and cognitive architecture: A critical analysis.  _Cognition_ , 1988.
  * Goyal and Bengio [2022] A. Goyal and Y. Bengio.  Inductive biases for deep learning of higher-level cognition.  _Proc. R. Soc. A 478: 20210068_ , 2022.
  * Greff et al. [2016] K. Greff, A. Rasmus, M. Berglund, T. Hao, H. Valpola, and J. Schmidhuber.  Tagger: Deep unsupervised perceptual grouping.  In _Advances in Neural Information Processing Systems_ , 2016.
  * Greff et al. [2017] K. Greff, S. van Steenkiste, and J. Schmidhuber.  Neural expectation maximization.  In _Advances in Neural Information Processing Systems_ , 2017.
  * Greff et al. [2019] K. Greff, R. L. Kaufman, R. Kabra, N. Watters, C. Burgess, D. Zoran, L. Matthey, M. Botvinick, and A. Lerchner.  Multi-object representation learning with iterative variational inference.  In _Proceedings of the 36th International Conference on Machine Learning_ , 2019.
  * Greff et al. [2020] K. Greff, S. van Steenkiste, and J. Schmidhuber.  On the binding problem in artificial neural networks.  _ArXiv_ , abs/2012.05208, 2020.
  * Gresele et al. [2021] L. Gresele, J. V. Kügelgen, V. Stimper, B. Schölkopf, and M. Besserve.  Independent mechanism analysis, a new concept?  In _Advances in Neural Information Processing Systems_ , 2021.
  * Harnad [1990] S. Harnad.  The symbol grounding problem.  _Physica D: Nonlinear Phenomena_ , 1990.
  * Hyvärinen and Morioka [2016] A. Hyvärinen and H. Morioka.  Unsupervised feature extraction by time-contrastive learning and nonlinear ica.  In _Advances in Neural Information Processing Systems_ , 2016.
  * Hyvärinen and Morioka [2017] A. Hyvärinen and H. Morioka.  Nonlinear ICA of Temporally Dependent Stationary Sources.  In _Proceedings of the 20th International Conference on Artificial Intelligence and Statistics_ , 2017.
  * Hyvärinen et al. [2019] A. Hyvärinen, H. Sasaki, and R. E. Turner.  Nonlinear ica using auxiliary variables and generalized contrastive learning.  In _AISTATS_. PMLR, 2019.
  * Johnson et al. [2016] J. Johnson, B. Hariharan, L. van der Maaten, L. Fei-Fei, C. L. Zitnick, and R. B. Girshick.  Clevr: A diagnostic dataset for compositional language and elementary visual reasoning.  _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016.
  * Khemakhem et al. [2020a] I. Khemakhem, D. Kingma, R. Monti, and A. Hyvärinen.  Variational autoencoders and nonlinear ica: A unifying framework.  In _Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics_ , 2020a.
  * Khemakhem et al. [2020b] I. Khemakhem, R. Monti, D. Kingma, and A. Hyvärinen.  Ice-beem: Identifiable conditional energy-based deep models based on nonlinear ica.  In _Advances in Neural Information Processing Systems_ , 2020b.
  * Klindt et al. [2021] D. A. Klindt, L. Schott, Y. Sharma, I. Ustyuzhaninov, W. Brendel, M. Bethge, and D. M. Paiton.  Towards nonlinear disentanglement in natural data with temporal sparse coding.  In _9th International Conference on Learning Representations_ , 2021\.
  * Lachapelle and Lacoste-Julien [2022] S. Lachapelle and S. Lacoste-Julien.  Partial disentanglement via mechanism sparsity.  In _UAI 2022 Workshop on Causal Representation Learning_ , 2022.
  * Lachapelle et al. [2022a] S. Lachapelle, T. Deleu, D. Mahajan, I. Mitliagkas, Y. Bengio, S. Lacoste-Julien, and Q. Bertrand.  Synergies between disentanglement and sparsity: a multi-task learning perspective, 2022a.
  * Lachapelle et al. [2022b] S. Lachapelle, P. Rodriguez Lopez, Y. Sharma, K. E. Everett, R. Le Priol, A. Lacoste, and S. Lacoste-Julien.  Disentanglement via mechanism sparsity regularization: A new principle for nonlinear ICA.  In _First Conference on Causal Learning and Reasoning_ , 2022b.
  * Lake et al. [2017] B. M. Lake, T. D. Ullman, J. B. Tenenbaum, and S. J. Gershman.  Building machines that learn and think like people.  _Behavioral and Brain Sciences_ , 2017.
  * Lin et al. [2020] Z. Lin, Y. Wu, S. V. Peri, W. Sun, G. Singh, F. Deng, J. Jiang, and S. Ahn.  Space: Unsupervised object-oriented scene representation via spatial attention and decomposition.  In _International Conference on Learning Representations_ , 2020.
  * Lippe et al. [2022] P. Lippe, S. Magliacane, S. Löwe, Y. M. Asano, T. Cohen, and E. Gavves.  CITRIS: Causal identifiability from temporal intervened sequences, 2022\.
  * Locatello et al. [2019] F. Locatello, S. Bauer, M. Lucic, G. Raetsch, S. Gelly, B. Schölkopf, and O. Bachem.  Challenging common assumptions in the unsupervised learning of disentangled representations.  In _Proceedings of the 36th International Conference on Machine Learning_ , 2019.
  * Locatello et al. [2020a] F. Locatello, B. Poole, G. Raetsch, B. Schölkopf, O. Bachem, and M. Tschannen.  Weakly-supervised disentanglement without compromises.  In _Proceedings of the 37th International Conference on Machine Learning_ , 2020a.
  * Locatello et al. [2020b] F. Locatello, M. Tschannen, S. Bauer, G. Rätsch, B. Schölkopf, and O. Bachem.  Disentangling factors of variations using few labels.  In _International Conference on Learning Representations_ , 2020b.
  * Locatello et al. [2020c] F. Locatello, D. Weissenborn, T. Unterthiner, A. Mahendran, G. Heigold, J. Uszkoreit, A. Dosovitskiy, and T. Kipf.  Object-centric learning with slot attention.  In _Advances in Neural Information Processing Systems_ , 2020c.
  * Marcus [2001] G. F. Marcus.  The algebraic mind : integrating connectionism and cognitive science, 2001\.
  * Munkres [2000] J. R. Munkres.  _Topology_.  Prentice Hall, Inc., 2 edition, 2000.
  * Pearl [2019] J. Pearl.  The seven tools of causal inference, with reflections on machine learning.  _Commun. ACM_ , 2019.
  * Peebles et al. [2020] W. Peebles, J. Peebles, J.-Y. Zhu, A. A. Efros, and A. Torralba.  The hessian penalty: A weak prior for unsupervised disentanglement.  In _Proceedings of European Conference on Computer Vision (ECCV)_ , 2020.
  * Ramesh et al. [2022] A. Ramesh, P. Dhariwal, A. Nichol, C. Chu, and M. Chen.  Hierarchical text-conditional image generation with clip latents.  _arXiv preprint arXiv:2204.06125_ , 2022.
  * Rombach et al. [2022] R. Rombach, A. Blattmann, D. Lorenz, P. Esser, and B. Ommer.  High-resolution image synthesis with latent diffusion models.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022.
  * Roth et al. [2023] K. Roth, M. Ibrahim, Z. Akata, P. Vincent, and D. Bouchacourt.  Disentanglement of correlated factors via hausdorff factorized support.  In _The Eleventh International Conference on Learning Representations_ , 2023.
  * Schölkopf et al. [2021] B. Schölkopf, F. Locatello, S. Bauer, N. R. Ke, N. Kalchbrenner, A. Goyal, and Y. Bengio.  Toward causal representation learning.  _Proceedings of the IEEE - Advances in Machine Learning and Deep Neural Networks_ , 2021.
  * Taleb and Jutten [1999] A. Taleb and C. Jutten.  Source separation in post-nonlinear mixtures.  _IEEE Transactions on Signal Processing_ , 1999.
  * Von Kügelgen et al. [2021] J. Von Kügelgen, Y. Sharma, L. Gresele, W. Brendel, B. Schölkopf, M. Besserve, and F. Locatello.  Self-supervised learning with data augmentations provably isolates content from style.  In _Thirty-Fifth Conference on Neural Information Processing Systems_ , 2021.
  * Wang and Jordan [2022] Y. Wang and M. I. Jordan.  Desiderata for representation learning: A causal perspective, 2022.
  * Zheng et al. [2022] Y. Zheng, I. Ng, and K. Zhang.  On the identifiability of nonlinear ICA: Sparsity and beyond.  In _Advances in Neural Information Processing Systems_ , 2022.

## Appendix

Table 2: Table of Notation. Calligraphic & indexing conventions
---
$[n]$ | $:=$ |  $\\{1,2,\dots,n\\}$
$x$ |  |  Scalar (random or not, depending on context)
${\bm{x}}$ |  |  Vector (random or not, depending on context)
${\bm{X}}$ |  |  Matrix
${\mathcal{X}}$ |  |  Set/Support
$f$ |  |  Scalar-valued function
${\bm{f}}$ |  |  Vector-valued function
$Df$, $D{\bm{f}}$ |  |  Jacobian of $f$ and ${\bm{f}}$
$D^{2}f$ |  |  Hessian of $f$
$B\subseteq[n]$ |  |  Subset of indices
$|B|$ |  |  Cardinality of the set $B$
${\bm{x}}_{B}$ |  |  Vector formed with the $i$th coordinates of ${\bm{x}}$, for all $i\in B$
${\bm{X}}_{B,B^{\prime}}$ |  |  Matrix formed with the entries $(i,j)\in B\times B^{\prime}$ of ${\bm{X}}$.
Given ${\mathcal{X}}\subseteq{\mathbb{R}}^{n}$, ${\mathcal{X}}_{B}$ | $:=$ |  $\\{{\bm{x}}_{B}\mid{\bm{x}}\in{\mathcal{X}}\\}$ (projection of ${\mathcal{X}}$)
Recurrent notation
${\bm{x}}\in{\mathbb{R}}^{d_{x}}$ |  |  Observation
${\bm{z}}\in{\mathbb{R}}^{d_{z}}$ |  |  Vector of latent factors of variations
${\mathcal{Z}}\subseteq{\mathbb{R}}^{d_{z}}$ |  |  Support of ${\bm{z}}$
${\bm{f}}:{\mathbb{R}}^{d_{z}}\rightarrow{\mathbb{R}}^{d_{x}}$ |  |  Ground-truth decoder function
$\tilde{\bm{f}}:{\mathbb{R}}^{d_{z}}\rightarrow{\mathbb{R}}^{d_{x}}$ |  |  Learned decoder function
${\mathcal{B}}$ |  |  A partition of $[d_{z}]$ (assumed contiguous w.l.o.g.)
$B\in{\mathcal{B}}$ |  |  A block of the partition ${\mathcal{B}}$
$B(i)\in{\mathcal{B}}$ |  |  The unique block of ${\mathcal{B}}$ that contains $i$
$\pi:[d_{z}]\rightarrow[d_{z}]$ |  |  A permutation
$S_{\mathcal{B}}$ | $:=$ |  $\bigcup_{B\in{\mathcal{B}}}B^{2}$
$S_{\mathcal{B}}^{c}$ | $:=$ |  $[d_{z}]^{2}\setminus S_{{\mathcal{B}}}$
${\mathbb{R}}^{d_{z}\times d_{z}}_{S_{\mathcal{B}}}$ | $:=$ |  $\\{{\bm{M}}\in{\mathbb{R}}^{d_{z}\times d_{z}}\mid(i,j)\not\in S_{\mathcal{B}}\implies{\bm{M}}_{i,j}=0\\}$
General topology
$\overline{{\mathcal{X}}}$ |  |  Closure of the subset ${\mathcal{X}}\subseteq{\mathbb{R}}^{n}$
${\mathcal{X}}^{\circ}$ |  |  Interior of the subset ${\mathcal{X}}\subseteq{\mathbb{R}}^{n}$

###  Appendix A Identifiability and Extrapolation Analysis

####  A.1 Useful definitions and lemmas

######  Definition 6 (Regularly closed sets).

A set ${\mathcal{Z}}\subseteq{\mathbb{R}}^{d_{z}}$ is regularly closed if
${\mathcal{Z}}=\overline{{\mathcal{Z}}^{\circ}}$, i.e. if it is equal to the
closure of its interior.

######  Definition 7 (Connected sets).

A set ${\mathcal{Z}}\subseteq{\mathbb{R}}^{d_{z}}$ is connected if it cannot
be written as a union of non-empty and disjoint open sets (in the subspace
topology).

######  Definition 8 (Path-connected sets).

A set ${\mathcal{Z}}\subseteq{\mathbb{R}}^{d_{z}}$ is path-connected if for
all pair of points ${\bm{z}}^{0},{\bm{z}}^{1}\in{\mathcal{Z}}$, there exists a
continuous map $\bm{{\phi}}:[0,1]\rightarrow{\mathcal{Z}}$ such that
$\bm{\phi}(0)={\bm{z}}^{0}$ and $\bm{\phi}(1)={\bm{z}}^{1}$. Such a map is
called a path between ${\bm{z}}^{0}$ and ${\bm{z}}^{1}$.

This lemma is taken from [30].

######  Lemma 4 (Sparsity pattern of an invertible matrix contains a
permutation).

Let ${\bm{L}}\in{\mathbb{R}}^{m\times m}$ be an invertible matrix. Then, there
exists a permutation $\sigma$ such that ${\bm{L}}_{i,\sigma(i)}\not=0$ for all
$i$.

###### Proof.

Since the matrix ${\bm{L}}$ is invertible, its determinant is non-zero, i.e.

$\displaystyle\det({\bm{L}}):=\sum_{\pi\in\mathfrak{S}_{m}}\text{sign}(\pi)\prod_{i=1}^{m}{\bm{L}}_{i,\pi(i)}\neq
0\,,$ (13)

where $\mathfrak{S}_{m}$ is the set of $m$-permutations. This equation implies
that at least one term of the sum is non-zero, meaning there exists
$\pi\in\mathfrak{S}_{m}$ such that for all $i\in[m]$, ${\bm{L}}_{i,\pi(i)}\neq
0$. ∎

######  Definition 9 (Aligned subspaces of ${\mathbb{R}}^{m\times n}$).

Given a subset $S\subseteq\\{1,...,m\\}\times\\{1,...,n\\}$, we define

$\displaystyle{\mathbb{R}}^{m\times
n}_{S}:=\\{{\bm{M}}\in{\mathbb{R}}^{m\times n}\mid(i,j)\not\in
S\implies{\bm{M}}_{i,j}=0\\}\,.$ (14)

######  Definition 10 (Useful sets).

Given a partition ${\mathcal{B}}$ of $[d]$, we define

$\displaystyle S_{\mathcal{B}}:=\bigcup_{B\in{\mathcal{B}}}B^{2}\ \ \ \ \
S_{\mathcal{B}}^{c}:=\\{1,\dots,d_{z}\\}^{2}\setminus S_{\mathcal{B}}$ (15)

######  Definition 11 ($C^{k}$-diffeomorphism).

Let ${\mathcal{Z}}\subseteq{\mathbb{R}}^{d_{z}}$ and
${\mathcal{X}}\subseteq{\mathbb{R}}^{d_{x}}$. A map
${\bm{f}}:{\mathcal{Z}}\rightarrow{\mathcal{X}}$ is said to be a
$C^{k}$-diffeomorphism if it is bijective, $C^{2}$ and has a $C^{2}$ inverse.

######  Definition 12 ($C^{k}$-diffeomorphism onto its image).

Let ${\mathcal{Z}}\subseteq{\mathbb{R}}^{d_{z}}$. A map
${\bm{f}}:{\mathcal{Z}}\rightarrow{\mathbb{R}}^{d_{x}}$ is said to be a
$C^{k}$-diffeomorphism onto its image if the restriction ${\bm{f}}$ to its
image, i.e. $\tilde{\bm{f}}:{\mathcal{Z}}\rightarrow{\bm{f}}({\mathcal{Z}})$,
is a $C^{k}$-diffeomorphism.

Note: Differentiability is typically defined for functions that have an open
domain in ${\mathbb{R}}^{n}$. However, in the definition above, the set
${\mathcal{Z}}$ might not be open in ${\mathbb{R}}^{d_{z}}$ and
${\bm{f}}({\mathcal{Z}})$ might not be open in ${\mathbb{R}}^{d_{x}}$
(${\bm{f}}({\mathcal{Z}})$ is the domain of ${\bm{f}}^{-1}$). In the case of
an arbitrary domain $A$, it is customary to say that a function
${\bm{f}}:A\subseteq{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}^{m}$ is $C^{k}$ if
there exists a $C^{k}$ function ${\bm{g}}$ defined on an open set
$U\subseteq{\mathbb{R}}^{n}$ that contains $A$ such that
${\bm{g}}\big{|}_{A}={\bm{f}}$ (i.e. ${\bm{g}}$ extends ${\bm{f}}$).

####  A.2 Relationship between additive decoders and the diagonal Hessian
penalty

######  Proposition 5 (Equivalence between additivity and diagonal Hessian).

Let ${\bm{f}}:{\mathbb{R}}^{d_{z}}\rightarrow{\mathbb{R}}^{d_{x}}$ be a
$C^{2}$ function. Then,

${\bm{f}}({\bm{z}})=\sum_{B\in{\mathcal{B}}}{\bm{f}}^{(B)}({\bm{z}}_{B})\text{
with ${\bm{f}}^{(B)}$ being $C^{2}$}\iff\begin{array}[]{l}\forall
k\in[d_{x}],\ {\bm{z}}\in{\mathcal{Z}},\ \ D^{2}{\bm{f}}_{k}({\bm{z}})\text{
is }\\\ \text{block diagonal with blocks in ${\mathcal{B}}$}.\end{array}$ (16)

###### Proof.

We start by showing the “$\implies$” direction. Let $B$ and $B^{\prime}$ be
two distinct blocks of ${\mathcal{B}}$. Let $i\in B$ and $i^{\prime}\in
B^{\prime}$. We can compute the derivative of ${\bm{f}}_{k}$ w.r.t.
${\bm{z}}_{i}$:

$\displaystyle
D_{i}{\bm{f}}_{k}({\bm{z}})=\sum_{\bar{B}\in{\mathcal{B}}}D_{i}{\bm{f}}_{k}^{(\bar{B})}({\bm{z}}_{\bar{B}})=D_{i}{\bm{f}}_{k}^{(B)}(z_{B})\,,$
(17)

where the last equality holds because $i\in B$ and not in any other block
$\bar{B}$. Furthermore,

$\displaystyle
D^{2}_{i,i^{\prime}}{\bm{f}}_{k}({\bm{z}})=D^{2}_{i,i^{\prime}}{\bm{f}}^{(B)}_{k}({\bm{z}}_{B})=0\,,$
(18)

where the last equality holds because $i^{\prime}\not\in B$. This shows that
$D^{2}{\bm{f}}_{k}({\bm{z}})$ is block diagonal.

We now show the “$\impliedby$” direction. Fix $k\in[d_{x}]$,
$B\in{\mathcal{B}}$. We know that $D^{2}_{B,B^{c}}{\bm{f}}_{k}({\bm{z}})=0$
for all ${\bm{z}}\in{\mathbb{R}}^{d_{z}}$. Fix
${\bm{z}}\in{\mathbb{R}}^{d_{z}}$. Consider a continuously differentiable path
$\bm{{\phi}}:[0,1]\rightarrow{\mathbb{R}}^{|B^{c}|}$ such that
$\bm{\phi}(0)=0$ and $\bm{\phi}(1)={\bm{z}}_{B^{c}}$. As
$D^{2}_{B,B^{c}}{\bm{f}}_{k}({\bm{z}})$ is a continuous function of
${\bm{z}}$, we can use the fundamental theorem of calculus for line integrals
to get that

$\displaystyle
D_{B}{\bm{f}}_{k}({\bm{z}}_{B},{\bm{z}}_{B^{c}})-D_{B}{\bm{f}}_{k}({\bm{z}}_{B},0)=\int_{0}^{1}\underbrace{D^{2}_{B,B^{c}}{\bm{f}}_{k}({\bm{z}}_{B},\bm{\phi}(t))}_{=0}\bm{\phi}^{\prime}(t)dt=0\,,$
(19)

(where
$D^{2}_{B,B^{c}}{\bm{f}}_{k}({\bm{z}}_{B},\bm{\phi}(t))\bm{\phi}^{\prime}(t)$
denotes a matrix-vector product) which implies that

$\displaystyle
D_{B}{\bm{f}}_{k}({\bm{z}})=D_{B}{\bm{f}}_{k}({\bm{z}}_{B},0)\,.$ (20)

And the above equality holds for all $B\in{\mathcal{B}}$ and all
${\bm{z}}\in{\mathbb{R}}^{d_{z}}$.

Choose an arbitrary ${\bm{z}}\in{\mathbb{R}}^{d_{z}}$. Consider a continously
differentiable path $\bm{\psi}:[0,1]\rightarrow{\mathbb{R}}^{d_{z}}$ such that
$\bm{\psi}(0)=0$ and $\bm{\psi}(1)={\bm{z}}$. By applying the fundamental
theorem of calculus for line integrals once more, we have that

$\displaystyle{\bm{f}}_{k}({\bm{z}})-{\bm{f}}_{k}(0)$
$\displaystyle=\int_{0}^{1}D{\bm{f}}_{k}(\bm{\psi}(t))\bm{\psi}^{\prime}(t)dt$
(21)
$\displaystyle=\int_{0}^{1}\sum_{B\in{\mathcal{B}}}D_{B}{\bm{f}}_{k}(\bm{\psi}(t))\bm{\psi}^{\prime}_{B}(t)dt$
(22)
$\displaystyle=\sum_{B\in{\mathcal{B}}}\int_{0}^{1}D_{B}{\bm{f}}_{k}(\bm{\psi}(t))\bm{\psi}^{\prime}_{B}(t)dt$
(23)
$\displaystyle=\sum_{B\in{\mathcal{B}}}\int_{0}^{1}D_{B}{\bm{f}}_{k}(\bm{\psi}_{B}(t),0)\bm{\psi}^{\prime}_{B}(t)dt\,,$
(24)

where the last equality holds by (20). We can further apply the fundamental
theorem of calculus for line integrals to each term
$\int_{0}^{1}D_{B}{\bm{f}}_{k}(\bm{\psi}_{B}(t),0)\bm{\psi}^{\prime}_{B}(t)dt$
to get

$\displaystyle{\bm{f}}_{k}({\bm{z}})-{\bm{f}}_{k}(0)$
$\displaystyle=\sum_{B\in{\mathcal{B}}}({\bm{f}}_{k}({\bm{z}}_{B},0)-{\bm{f}}_{k}(0,0))$
(25) $\displaystyle\implies{\bm{f}}_{k}({\bm{z}})$
$\displaystyle={\bm{f}}_{k}(0)+\sum_{B\in{\mathcal{B}}}({\bm{f}}_{k}({\bm{z}}_{B},0)-{\bm{f}}_{k}(0))$
(26)
$\displaystyle=\sum_{B\in{\mathcal{B}}}\underbrace{\left({\bm{f}}_{k}({\bm{z}}_{B},0)-\frac{|{\mathcal{B}}|-1}{|{\mathcal{B}}|}{\bm{f}}_{k}(0)\right)}_{{\bm{f}}_{k}^{(B)}({\bm{z}}_{B}):=}\,.$
(27)

and since ${\bm{z}}$ was arbitrary, the above holds for all
${\bm{z}}\in{\mathbb{R}}^{d_{z}}$. Note that the functions
${\bm{f}}_{k}^{(B)}({\bm{z}}_{B})$ must be $C^{2}$ because ${\bm{f}}_{k}$ is
$C^{2}$. This concludes the proof. ∎

####  A.3 Examples of local but non-global disentanglement

In this section, we provide examples of mapping
${\bm{v}}:\hat{\mathcal{Z}}^{\textnormal{train}}\rightarrow{\mathcal{Z}}^{\textnormal{train}}$
that satisfy the local disentanglement property of Definition 4, but not the
global disentanglement property of Definition 3. Note that these notions are
defined for pairs of decoders ${\bm{f}}$ and $\hat{\bm{f}}$, but here we
construct directly the function ${\bm{v}}$ which is usually defined as
${\bm{f}}^{-1}\circ\hat{\bm{f}}$. However, given ${\bm{v}}$ we can always
define ${\bm{f}}$ and $\hat{\bm{f}}$ to be such that
${\bm{f}}^{-1}\circ\hat{\bm{f}}={\bm{v}}$: Simply take
${\bm{f}}({\bm{z}}):=[{\bm{z}}_{1},\dots,{\bm{z}}_{d_{z}},0,\dots,0]^{\top}\in{\mathbb{R}}^{d_{x}}$
and $\hat{\bm{f}}:={\bm{f}}\circ{\bm{v}}$. This construction however yields a
decoder ${\bm{f}}$ that is not sufficiently nonlinear (Assumption 2). Clearly
the mappings ${\bm{v}}$ that we provide in the following examples cannot be
written as compositions of decoders ${\bm{f}}^{-1}\circ\hat{\bm{f}}$ where
${\bm{f}}$ and $\hat{\bm{f}}$ satisfy all assumptions of Theorem 2, as this
would contradict the theorem. In Examples 4 & 5, the path-connected assumption
of Theorem 2 is violated. In Example 6, it is less obvious to see which
assumptions would be violated.

######  Example 4 (Disconnected support with changing permutation).

Let ${\bm{v}}:\hat{\mathcal{Z}}\rightarrow{\mathbb{R}}^{2}$ s.t.
$\hat{\mathcal{Z}}=\hat{\mathcal{Z}}^{(1)}\cup\hat{\mathcal{Z}}^{(2)}\subseteq{\mathbb{R}}^{2}$
where
$\hat{\mathcal{Z}}^{(1)}=\\{{\bm{z}}\in{\mathbb{R}}^{2}\mid{\bm{z}}_{1}\leq 0\
\text{and}\ {\bm{z}}_{2}\leq 0\\}$ and
$\hat{\mathcal{Z}}^{(2)}=\\{{\bm{z}}\in{\mathbb{R}}^{2}\mid{\bm{z}}_{1}\geq 1\
\text{and}\ {\bm{z}}_{2}\geq 1\\}$. Assume

$\displaystyle{\bm{v}}({\bm{z}}):=\begin{cases}({\bm{z}}_{1},{\bm{z}}_{2}),&\text{if}\
{\bm{z}}\in\hat{\mathcal{Z}}^{(1)}\\\ ({\bm{z}}_{2},{\bm{z}}_{1}),&\text{if}\
{\bm{z}}\in\hat{\mathcal{Z}}^{(2)}\\\ \end{cases}\,.$ (28)

Step 1: ${\bm{v}}$ is a diffeomorphism. We first show it is injective. Suppose
${\bm{v}}({\bm{z}}^{1})={\bm{v}}({\bm{z}}^{2})$ for some
${\bm{z}}^{1},{\bm{z}}^{2}\in\hat{\mathcal{Z}}$. It implies that both
${\bm{z}}_{1}$ and ${\bm{z}}_{2}$ are in the same region
$\hat{\mathcal{Z}}^{(i)}$. To see this, assume w.l.o.g. that
${\bm{z}}^{1}\in{\mathcal{Z}}^{(1)}$ and ${\bm{z}}^{2}\in{\mathcal{Z}}^{(2)}$.
This means
${\bm{v}}({\bm{z}}^{1})={\bm{v}}({\bm{z}}^{2})\implies({\bm{z}}^{1}_{1},{\bm{z}}^{1}_{2})=({\bm{z}}^{2}_{2},{\bm{z}}^{2}_{1})$,
which is a contradiction since ${\bm{z}}^{1}_{1}\leq 0$ and
${\bm{z}}^{2}_{2}\geq 1$. Because ${\bm{z}}^{1}$ and ${\bm{z}}^{2}$ are in the
same region, we have
${\bm{v}}({\bm{z}}^{1})={\bm{v}}({\bm{z}}^{2})\implies{\bm{z}}^{1}={\bm{z}}^{2}$.
Since ${\bm{v}}$ is injective, it is also bijective on its image.

The Jacobian of ${\bm{v}}$ is given by

$\displaystyle D{\bm{v}}({\bm{z}}):=\begin{cases}\begin{bmatrix}1&0\\\
0&1\end{bmatrix},&\text{if}\ {\bm{z}}\in\hat{\mathcal{Z}}^{(1)}\\\
\begin{bmatrix}0&1\\\ 1&0\end{bmatrix},&\text{if}\
{\bm{z}}\in\hat{\mathcal{Z}}^{(2)}\\\ \end{cases}\,,$ (29)

which is full rank everywhere. Hence ${\bm{v}}$ is a diffeomorphism onto its
image.

Step 2: ${\bm{v}}$ is locally disentangled. By (29), the Jacobian
$D{\bm{v}}({\bm{z}})$ is everywhere a permutation matrix, hence ${\bm{v}}$ is
locally disentangled.

Step 3: ${\bm{v}}$ is not globally disentangled. That is because
${\bm{v}}_{1}({\bm{z}}_{1},{\bm{z}}_{2})$ depends on both ${\bm{z}}_{1}$ and
${\bm{z}}_{2}$. Indeed, if ${\bm{z}}_{2}=0$, we have that
${\bm{v}}_{1}(-1,0)=-1\not=0={\bm{v}}_{1}(0,0)$. Also, if ${\bm{z}}_{1}=1$, we
have that ${\bm{v}}_{1}(1,1)=1\not=2={\bm{v}}_{1}(1,2)$.

######  Example 5 (Disconnected support with fixed permutation).

Let ${\bm{v}}:\hat{\mathcal{Z}}\rightarrow{\mathbb{R}}^{2}$ s.t.
$\hat{\mathcal{Z}}=\hat{\mathcal{Z}}^{(1)}\cup\hat{\mathcal{Z}}^{(2)}\subseteq{\mathbb{R}}^{2}$
where
$\hat{\mathcal{Z}}^{(1)}=\\{{\bm{z}}\in{\mathbb{R}}^{2}\mid{\bm{z}}_{2}\leq
0\\}$ and
$\hat{\mathcal{Z}}^{(2)}=\\{{\bm{z}}\in{\mathbb{R}}^{2}\mid{\bm{z}}_{2}\geq
1\\}$. Assume
${\bm{v}}({\bm{z}}):={\bm{z}}+\mathbbm{1}({\bm{z}}\in\hat{\mathcal{Z}}^{(2)})$.

Step 1: ${\bm{v}}$ is a diffeomorphism. We now show that ${\bm{v}}$ is
injective. Take ${\bm{z}}^{1},{\bm{z}}^{2}\in\hat{\mathcal{Z}}$ such that
${\bm{v}}({\bm{z}}^{1})={\bm{v}}({\bm{z}}^{2})$. The points ${\bm{z}}^{1}$ and
${\bm{z}}^{2}$ must belong to the same ${\mathcal{Z}}^{(i)}$ since otherwise
we have that ${\bm{z}}^{1}={\bm{z}}^{2}+\mathbbm{1}$ (assuming w.l.o.g. that
${\bm{z}}^{1}\in{\mathcal{Z}}^{(1)}$ and
${\bm{z}}^{2}\in{\mathcal{Z}}^{(2)}$), which implies that
$0\geq{\bm{z}}^{1}_{2}={\bm{z}}^{2}_{2}+1\geq 2$, which is a contradiction.
Since both ${\bm{z}}^{1}$ and ${\bm{z}}^{2}$ are in the same region, we have
that
$\mathbbm{1}({\bm{z}}^{1}\in\hat{\mathcal{Z}}^{(2)})=\mathbbm{1}({\bm{z}}^{2}\in\hat{\mathcal{Z}}^{(2)})$,
which implies that

$\displaystyle{\bm{v}}({\bm{z}}^{1})$ $\displaystyle={\bm{v}}({\bm{z}}^{2})\,$
(30)
$\displaystyle{\bm{z}}^{1}+\mathbbm{1}({\bm{z}}^{1}\in\hat{\mathcal{Z}}^{(2)})$
$\displaystyle={\bm{z}}^{2}+\mathbbm{1}({\bm{z}}^{2}\in\hat{\mathcal{Z}}^{(2)})\,$
(31)
$\displaystyle{\bm{z}}^{1}+\mathbbm{1}({\bm{z}}^{1}\in\hat{\mathcal{Z}}^{(2)})$
$\displaystyle={\bm{z}}^{2}+\mathbbm{1}({\bm{z}}^{1}\in\hat{\mathcal{Z}}^{(2)})\,$
(32) $\displaystyle{\bm{z}}^{1}$ $\displaystyle={\bm{z}}^{2}\,,$ (33)

which means ${\bm{v}}$ is injective. This, of course, means that it is
bijective on its image, which we denote by
${\mathcal{Z}}:={\bm{v}}(\hat{\mathcal{Z}})$.

The Jacobian of ${\bm{v}}$ is $D{\bm{v}}({\bm{z}})={\bm{I}}$ which is
invertible everywhere on $\hat{\mathcal{Z}}$. Hence, ${\bm{v}}$ is a
diffeomorphism from $\hat{\mathcal{Z}}$ to ${\mathcal{Z}}$.

Step 2: ${\bm{v}}$ is locally disentangled. This is clear since
$D{\bm{v}}({\bm{z}})={\bm{I}}$ everywhere.

Step 3: ${\bm{v}}$ is not globally disentangled. Indeed, the function
${\bm{v}}_{1}({\bm{z}}_{1},{\bm{z}}_{2})={\bm{z}}_{1}+\mathbbm{1}({\bm{z}}\in\hat{\mathcal{Z}}^{(2)})$
is not constant in ${\bm{z}}_{2}$.

Figure 6: Illustration of
$\hat{\mathcal{Z}}=\hat{\mathcal{Z}}^{(b)}\cup\hat{\mathcal{Z}}^{(o)}$ in
Example 6 where $\hat{\mathcal{Z}}^{(b)}$ is the blue region and
$\hat{\mathcal{Z}}^{(o)}$ is the orange region. The two black dots correspond
to $(-1/2,-1/2)$ and $(1/2,-1/2)$, where the function
${\bm{v}}_{2}({\bm{z}}_{1},{\bm{z}}_{2})$ is evaluated to show that it is not
constant in ${\bm{z}}_{1}$.

######  Example 6 (Connected support).

Let ${\bm{v}}:\hat{\mathcal{Z}}\rightarrow{\mathbb{R}}^{2}$ s.t.
$\hat{\mathcal{Z}}=\hat{\mathcal{Z}}^{(b)}\cup\hat{\mathcal{Z}}^{(o)}$ where
$\hat{\mathcal{Z}}^{(b)}$ and $\hat{\mathcal{Z}}^{(o)}$ are respectively the
blue and orange regions of Figure 6. Both regions contain their boundaries.
The function ${\bm{v}}$ is defined as follows:

$\displaystyle{\bm{v}}_{1}({\bm{z}})$ $\displaystyle:={\bm{z}}_{1}$ (34)
$\displaystyle{\bm{v}}_{2}({\bm{z}})$
$\displaystyle:=\begin{cases}\frac{({\bm{z}}_{2}+1)^{2}+1}{2},&\text{if}\
{\bm{z}}\in\hat{\mathcal{Z}}^{(b)}\\\ e^{{\bm{z}}_{2}},&\text{if}\
{\bm{z}}\in\hat{\mathcal{Z}}^{(o)}\end{cases}\,.$ (35)

We must now verify that ${\bm{v}}_{2}({\bm{z}})$ is $C^{2}$ at the frontier
between $\hat{\mathcal{Z}}^{(b)}$ and $\hat{\mathcal{Z}}^{(o)}$, i.e. when
${\bm{z}}\in[1/4,1]\times\\{0\\}$.

${\bm{v}}_{2}({\bm{z}})$ is continuous since

$\displaystyle\left.\frac{({\bm{z}}_{2}+1)^{2}+1}{2}\right|_{{\bm{z}}_{2}=0}=1=\left.e^{{\bm{z}}_{2}}\right|_{{{\bm{z}}_{2}=0}}\,.$
(36)

${\bm{v}}_{2}({\bm{z}})$ is $C^{1}$ since

$\displaystyle\left(\left.\frac{({\bm{z}}_{2}+1)^{2}+1}{2}\right)^{\prime}\right|_{{\bm{z}}_{2}=0}=\left.({\bm{z}}_{2}+1)\right|_{{\bm{z}}_{2}=0}=1=\left.e^{{\bm{z}}_{2}}\right|_{{{\bm{z}}_{2}=0}}=\left.(e^{{\bm{z}}_{2}})^{\prime}\right|_{{{\bm{z}}_{2}=0}}\,.$
(37)

${\bm{v}}_{2}({\bm{z}})$ is $C^{2}$ since

$\displaystyle\left(\left.\frac{({\bm{z}}_{2}+1)^{2}+1}{2}\right)^{\prime\prime}\right|_{{\bm{z}}_{2}=0}=\left.1\right|_{{\bm{z}}_{2}=0}=1=\left.e^{{\bm{z}}_{2}}\right|_{{{\bm{z}}_{2}=0}}=\left.(e^{{\bm{z}}_{2}})^{\prime\prime}\right|_{{{\bm{z}}_{2}=0}}\,.$
(38)

The Jacobian of ${\bm{v}}$ is

$\displaystyle D{\bm{v}}({\bm{z}}):=\begin{cases}\begin{bmatrix}1&0\\\
0&{\bm{z}}_{2}+1\end{bmatrix},\ \text{if}\
{\bm{z}}\in\hat{\mathcal{Z}}^{(b)}\\\ \begin{bmatrix}1&0\\\
0&e^{{\bm{z}}_{2}}\end{bmatrix},\ \text{if}\
{\bm{z}}\in\hat{\mathcal{Z}}^{(o)}\end{cases}\,,$ (39)

which is invertible and a permutation-scaling matrix everywhere on
$\hat{\mathcal{Z}}$. Thus local disentanglement holds.

However, ${\bm{v}}_{2}({\bm{z}}_{1},{\bm{z}}_{2})$ is not constant in
${\bm{z}}_{1}$. Indeed,

$\displaystyle{\bm{v}}_{2}(-\frac{1}{2},-\frac{1}{2})=\left.\frac{({\bm{z}}_{2}+1)^{2}+1}{2}\right|_{{\bm{z}}_{2}=-1/2}=\frac{5}{8}\not=e^{-1/2}={\bm{v}}_{2}(\frac{1}{2},-\frac{1}{2})\,.$
(40)

Thus global disentanglement does not hold.

####  A.4 Proof of Theorem 1

######  Proposition 6.

Suppose that the data-generating process satisfies Assumption 1, that the
learned decoder
$\hat{\bm{f}}:{\mathbb{R}}^{d_{z}}\rightarrow{\mathbb{R}}^{d_{x}}$ is a
$C^{2}$-diffeomorphism onto its image and that the encoder
$\hat{\bm{g}}:{\mathbb{R}}^{d_{x}}\rightarrow{\mathbb{R}}^{d_{z}}$ is
continuous. Then, if $\hat{\bm{f}}$ and $\hat{\bm{g}}$ solve the
reconstruction problem on the training distribution, i.e.
${\mathbb{E}}^{\textnormal{train}}||{\bm{x}}-\hat{\bm{f}}(\hat{\bm{g}}({\bm{x}}))||^{2}=0$,
we have that
${\bm{f}}({\mathcal{Z}}^{\textnormal{train}})=\hat{\bm{f}}(\hat{\mathcal{Z}}^{\textnormal{train}})$
and the map ${\bm{v}}:={\bm{f}}^{-1}\circ\hat{\bm{f}}$ is a
$C^{2}$-diffeomorphism from $\hat{\mathcal{Z}}^{\textnormal{train}}$ to
${\mathcal{Z}}^{\textnormal{train}}$.

###### Proof.

First note that

$\displaystyle{\mathbb{E}}^{\textnormal{train}}||{\bm{x}}-\hat{\bm{f}}(\hat{\bm{g}}({\bm{x}}))||^{2}={\mathbb{E}}^{\textnormal{train}}||{\bm{f}}({\bm{z}})-\hat{\bm{f}}(\hat{\bm{g}}({\bm{f}}({\bm{z}})))||^{2}=0\,,$
(41)

which implies that, for ${\mathbb{P}}_{\bm{z}}$-almost every
${\bm{z}}\in{\mathcal{Z}}^{\textnormal{train}}$,

${\bm{f}}({\bm{z}})=\hat{\bm{f}}(\hat{\bm{g}}({\bm{f}}({\bm{z}})))\,.$

But since the functions on both sides of the equations are continuous, the
equality holds for all ${\bm{z}}\in{\mathcal{Z}}^{\textnormal{train}}$. This
implies that
${\bm{f}}({\mathcal{Z}}^{\textnormal{train}})=\hat{\bm{f}}\circ\hat{\bm{g}}\circ{\bm{f}}({\mathcal{Z}}^{\textnormal{train}})=\hat{\bm{f}}(\hat{\mathcal{Z}}^{\textnormal{train}})$.

Let ${\bm{h}}:=\hat{\bm{g}}\circ{\bm{f}}$. Since $\hat{\bm{f}}$ is a
$C^{2}$-diffeomorphism on its image, we have

$\displaystyle\hat{\bm{f}}^{-1}\circ{\bm{f}}({\bm{z}})={\bm{h}}({\bm{z}})\,,$
(42)

which is a composition of $C^{2}$-diffeomorphisms and is thus itself a
$C^{2}$-diffeomorphism from ${\mathcal{Z}}^{\textnormal{train}}$ to
${\bm{h}}({\mathcal{Z}}^{\textnormal{train}})=\hat{\mathcal{Z}}^{\textnormal{train}}$.
This concludes the proof, since, ${\bm{v}}={\bm{h}}^{-1}$. ∎

The following technical lemma can be skipped at first read.

######  Lemma 7.

Let ${\bm{f}}:{\mathbb{R}}^{d_{z}}\rightarrow{\mathbb{R}}^{d_{x}}$ and
$\tilde{\bm{f}}:{\mathbb{R}}^{d_{z}}\rightarrow{\mathbb{R}}^{d_{x}}$ be two
$C^{2}$ functions such that, for all ${\bm{z}}\in{\mathcal{Z}}$,
${\bm{f}}({\bm{z}})=\tilde{\bm{f}}({\bm{z}})$. Then, for all
${\bm{z}}\in\overline{{\mathcal{Z}}^{\circ}}$,
$D{\bm{f}}({\bm{z}})=D\tilde{{\bm{f}}}({\bm{z}})$ and for all $k$,
$D^{2}{\bm{f}}_{k}({\bm{z}})$ = $D^{2}\tilde{\bm{f}}_{k}({\bm{z}})$.

###### Proof.

The derivative is defined only on the interior of a domain, hence

$\displaystyle\forall{\bm{z}}\in{\mathcal{Z}}^{\circ},D{\bm{f}}({\bm{z}})$
$\displaystyle=D\tilde{\bm{f}}({\bm{z}})$ (43)

Choose ${\bm{z}}_{0}\in\overline{{\mathcal{Z}}^{\circ}}$. Because
${\bm{z}}_{0}$ is in the closure of ${\mathcal{Z}}^{\circ}$, there exists a
sequence $\\{{\bm{z}}_{k}\\}_{k=1}^{\infty}\subseteq{\mathcal{Z}}^{\circ}$
such that $\lim_{k\to\infty}{\bm{z}}_{k}={\bm{z}}_{0}$. Of course we have

$\displaystyle\lim_{k\to\infty}D{\bm{f}}({\bm{z}}_{k})$
$\displaystyle=\lim_{k\to\infty}D\tilde{\bm{f}}({\bm{z}}_{k})$ (44)
$\displaystyle D{\bm{f}}({\bm{z}}_{0})$
$\displaystyle=D\tilde{\bm{f}}({\bm{z}}_{0})\,,$ (45)

where the last step holds because the derivative itself is continuous. Hence
the derivatives are equal on $\overline{{\mathcal{Z}}^{\circ}}$. Because
${\bm{f}}$ and $\tilde{\bm{f}}$ are $C^{2}$, their derivatives are $C^{1}$. We
can thus apply a similar argument to show that their second derivatives are
equal on $\overline{\overline{{\mathcal{Z}}^{\circ}}^{\circ}}$, which can be
shown to be equal to $\overline{{\mathcal{Z}}^{\circ}}$. ∎

See 1

###### Proof.

We can apply Proposition 6 and have that the map
${\bm{v}}:={\bm{f}}^{-1}\circ\hat{\bm{f}}$ is a $C^{2}$-diffeomorphism from
$\hat{\mathcal{Z}}^{\textnormal{train}}$ to
${\mathcal{Z}}^{\textnormal{train}}$. This allows one to write

$\displaystyle{\bm{f}}\circ{\bm{v}}({\bm{z}})$
$\displaystyle=\hat{\bm{f}}({\bm{z}})\
\forall{\bm{z}}\in\hat{\mathcal{Z}}^{\textnormal{train}}$ (46)
$\displaystyle\sigma(\sum_{B\in{\mathcal{B}}}{\bm{f}}^{(B)}({\bm{v}}_{B}({\bm{z}})))$
$\displaystyle=\sigma(\sum_{B\in{\mathcal{B}}}\hat{\bm{f}}^{(B)}({\bm{z}}_{B}))$
(47)
$\displaystyle\sum_{B\in{\mathcal{B}}}{\bm{f}}^{(B)}({\bm{v}}_{B}({\bm{z}}))$
$\displaystyle=\sum_{B\in{\mathcal{B}}}\hat{\bm{f}}^{(B)}({\bm{z}}_{B})\
\forall{\bm{z}}\in\hat{\mathcal{Z}}^{\textnormal{train}}\,.$ (48)

Since ${\mathcal{Z}}^{\textnormal{train}}$ is regularly closed and is
diffeomorphic to $\hat{\mathcal{Z}}^{\textnormal{train}}$,
$\hat{\mathcal{Z}}^{\textnormal{train}}$ must also be regularly closed
(topological properties are preserved by diffeomorphisms). Moreover by Lemma
7, Equation (48) implies the first and second derivatives are equal over
$\overline{(\hat{\mathcal{Z}}^{\textnormal{train}})^{\circ}}$ (the closure of
the interior of $\hat{\mathcal{Z}}^{\textnormal{train}}$). But since
$\hat{\mathcal{Z}}^{\textnormal{train}}$ is regularly closed, we have
$\overline{(\hat{\mathcal{Z}}^{\textnormal{train}})^{\circ}}=\hat{\mathcal{Z}}^{\textnormal{train}}$
and thus the first and second derivatives are equal on
$\hat{\mathcal{Z}}^{\textnormal{train}}$.

Let ${\bm{z}}\in\hat{\mathcal{Z}}^{\textnormal{train}}$. Choose some
$J\in{\mathcal{B}}$ and some $j\in J$. Differentiate both sides of the above
equation with respect to ${\bm{z}}_{j}$, which yields:

$\displaystyle\sum_{B\in{\mathcal{B}}}\sum_{i\in
B}D_{i}{\bm{f}}^{(B)}({\bm{v}}_{B}({\bm{z}}))D_{j}{\bm{v}}_{i}({\bm{z}})$
$\displaystyle=D_{j}\hat{\bm{f}}^{(J)}({\bm{z}}_{J})\,.$ (49)

Choose $J^{\prime}\in{\mathcal{B}}\setminus\\{J\\}$ and $j^{\prime}\in
J^{\prime}$. Differentiating the above w.r.t. ${\bm{z}}_{j^{\prime}}$ yields

$\displaystyle\sum_{B\in{\mathcal{B}}}\sum_{i\in
B}\left[D_{i}{\bm{f}}^{(B)}({\bm{v}}_{B}({\bm{z}}))D^{2}_{j,j^{\prime}}{\bm{v}}_{i}({\bm{z}})+\sum_{i^{\prime}\in
B}D^{2}_{i,i^{\prime}}{\bm{f}}^{(B)}({\bm{v}}_{B}({\bm{z}}))D_{j^{\prime}}{\bm{v}}_{i^{\prime}}({\bm{z}})D_{j}{\bm{v}}_{i}({\bm{z}})\right]$
$\displaystyle=0$ $\displaystyle\sum_{B\in{\mathcal{B}}}\bigg{[}\sum_{i\in
B}\Big{[}D_{i}{\bm{f}}^{(B)}({\bm{v}}_{B}({\bm{z}}))D^{2}_{j,j^{\prime}}{\bm{v}}_{i}({\bm{z}})+D^{2}_{i,i}{\bm{f}}^{(B)}({\bm{v}}_{B}({\bm{z}}))D_{j^{\prime}}{\bm{v}}_{i}({\bm{z}})D_{j}{\bm{v}}_{i}({\bm{z}})\Big{]}\bigg{.}+\quad$
$\displaystyle\bigg{.}\sum_{(i,i^{\prime})\in
B^{2}_{<}}D^{2}_{i,i^{\prime}}{\bm{f}}^{(B)}({\bm{v}}_{B}({\bm{z}}))(D_{j^{\prime}}{\bm{v}}_{i^{\prime}}({\bm{z}})D_{j}{\bm{v}}_{i}({\bm{z}})+D_{j^{\prime}}{\bm{v}}_{i}({\bm{z}})D_{j}{\bm{v}}_{i^{\prime}}({\bm{z}}))\bigg{]}$
$\displaystyle=0\,,$ (50)

where $B^{2}_{<}:=B^{2}\cap\\{(i,i^{\prime})\mid i^{\prime}<i\\}$. For the
sake of notational conciseness, we are going to refer to $S_{\mathcal{B}}$ and
$S_{\mathcal{B}}^{c}$ as $S$ and $S^{c}$ (Definition 10). Also, define

$\displaystyle S_{<}:=\bigcup_{B\in{\mathcal{B}}}B^{2}_{<}\,.$ (51)

Let us define the vectors

$\displaystyle\forall i\in\\{1,...d_{z}\\},\ \vec{a}_{i}({\bm{z}})$
$\displaystyle:=(D^{2}_{j,j^{\prime}}{\bm{v}}_{i}({\bm{z}}))_{(j,j^{\prime})\in
S^{c}}$ (52) $\displaystyle\forall i\in\\{1,...d_{z}\\},\
\vec{b}_{i}({\bm{z}})$
$\displaystyle:=(D_{j^{\prime}}{\bm{v}}_{i}({\bm{z}})D_{j}{\bm{v}}_{i}({\bm{z}}))_{(j,j^{\prime})\in
S^{c}}$ (53) $\displaystyle\forall B\in{\mathcal{B}},\
\forall(i,i^{\prime})\in B^{2}_{<},\ \vec{c}_{i,i^{\prime}}({\bm{z}})$
$\displaystyle:=(D_{j^{\prime}}{\bm{v}}_{i^{\prime}}({\bm{z}})D_{j}{\bm{v}}_{i}({\bm{z}})+D_{j^{\prime}}{\bm{v}}_{i}({\bm{z}})D_{j}{\bm{v}}_{i^{\prime}}({\bm{z}}))_{(j,j^{\prime})\in
S^{c}}$ (54)

This allows us to rewrite, for all $k\in\\{1,...,d_{x}\\}$

$\displaystyle\sum_{B\in{\mathcal{B}}}\left[\sum_{i\in
B}\left[D_{i}{\bm{f}}_{k}^{(B)}({\bm{v}}_{B}({\bm{z}}))\vec{a}_{i}({\bm{z}})+D^{2}_{i,i}{\bm{f}}_{k}^{(B)}({\bm{v}}_{B}({\bm{z}}))\vec{b}_{i}({\bm{z}})\right]+\sum_{(i,i^{\prime})\in
B^{2}_{<}}D^{2}_{i,i^{\prime}}{\bm{f}}_{k}^{(B)}({\bm{v}}_{B}({\bm{z}}))\vec{c}_{i,i^{\prime}}({\bm{z}})\right]$
$\displaystyle=0\,.$ (55)

We define

$\displaystyle{\bm{w}}({\bm{z}},k)$
$\displaystyle:=((D_{i}{\bm{f}}_{k}^{(B)}({\bm{z}}_{B}))_{i\in
B},(D^{2}_{i,i}{\bm{f}}_{k}^{(B)}({\bm{z}}_{B}))_{i\in
B},(D^{2}_{i,i^{\prime}}{\bm{f}}_{k}^{(B)}({\bm{z}}_{B}))_{(i,i^{\prime})\in
B_{<}^{2}})_{B\in{\mathcal{B}}}$ (56) $\displaystyle{\bm{M}}({\bm{z}})$
$\displaystyle:=[[\vec{a}_{i}({\bm{z}})]_{i\in
B},[\vec{b}_{i}({\bm{z}})]_{i\in
B},[\vec{c}_{i,i^{\prime}}({\bm{z}})]_{(i,i^{\prime})\in
B_{<}^{2}}]_{B\in{\mathcal{B}}}\,,$ (57)

which allows us to write, for all $k\in\\{1,...,d_{z}\\}$

$\displaystyle{\bm{M}}({\bm{z}}){\bm{w}}({\bm{v}}({\bm{z}}),k)=0\,.$ (58)

We can now recognize that the matrix ${\bm{W}}({\bm{v}}({\bm{z}}))$ of
Assumption 2 is given by

$\displaystyle{\bm{W}}({\bm{v}}({\bm{z}}))^{\top}=\left[{\bm{w}}({\bm{v}}({\bm{z}}),1)\
\dots\ {\bm{w}}({\bm{v}}({\bm{z}}),d_{x})\right]\,$ (59)

which allows us to write

$\displaystyle{\bm{M}}({\bm{z}}){\bm{W}}({\bm{v}}({\bm{z}}))^{\top}=0$ (60)
$\displaystyle{\bm{W}}({\bm{v}}({\bm{z}})){\bm{M}}({\bm{z}})^{\top}=0$ (61)

Since ${\bm{W}}({\bm{v}}({\bm{z}}))$ has full column-rank (by Assumption 2 and
the fact that ${\bm{v}}({\bm{z}})\in{\mathcal{Z}}^{\textnormal{train}}$),
there exists $q$ rows that are linearly independent. Let $K$ be the index set
of these rows. This means ${\bm{W}}({\bm{v}}({\bm{z}}))_{K,\cdot}$ is an
invertible matrix. We can thus write

$\displaystyle{\bm{W}}({\bm{v}}({\bm{z}}))_{K,\cdot}{\bm{M}}({\bm{z}})^{\top}$
$\displaystyle=0$ (62)
$\displaystyle({\bm{W}}({\bm{v}}({\bm{z}}))_{K,\cdot})^{-1}{\bm{W}}({\bm{v}}({\bm{z}}))_{K,\cdot}{\bm{M}}({\bm{z}})^{\top}$
$\displaystyle=({\bm{W}}({\bm{v}}({\bm{z}}))_{K,\cdot})^{-1}0$ (63)
$\displaystyle{\bm{M}}({\bm{z}})^{\top}$ $\displaystyle=0\,,$ (64)

which means, in particular, that, $\forall i\in\\{1,\dots,d_{z}\\}$,
$\vec{b}_{i}({\bm{z}})=0$, i.e.,

$\displaystyle\forall i\in\\{1,\dots,d_{z}\\},\forall(j,j^{\prime})\in
S^{c},D_{j}{\bm{v}}_{i}({\bm{z}})D_{j^{\prime}}{\bm{v}}_{i}({\bm{z}})=0\ $
(65)

Since the ${\bm{v}}$ is a diffeomorphism, its Jacobian matrix
$D{\bm{v}}({\bm{z}})$ is invertible everywhere. By Lemma 4, this means there
exists a permutation $\pi$ such that, for all $j$,
$D_{j}{\bm{v}}_{\pi(j)}({\bm{z}})\not=0$. This and (65) imply that

$\displaystyle\forall(j,j^{\prime})\in S^{c},\ \
D_{j}{\bm{v}}_{\pi(j^{\prime})}({\bm{z}})\underbrace{D_{j^{\prime}}{\bm{v}}_{\pi(j^{\prime})}({\bm{z}})}_{\not=0}$
$\displaystyle=0,$ (66) $\displaystyle\implies\forall(j,j^{\prime})\in S^{c},\
\ D_{j}{\bm{v}}_{\pi(j^{\prime})}({\bm{z}})$ $\displaystyle=0\,.$ (67)

To show that $D{\bm{v}}({\bm{z}})$ is a ${\mathcal{B}}$-block permutation
matrix, the only thing left to show is that $\pi$ respects ${\mathcal{B}}$.
For this, we use the fact that, $\forall
B\in{\mathcal{B}},\forall(i,i^{\prime})\in B^{2}_{<}$,
$\vec{c}_{i,i^{\prime}}({\bm{z}})=0$ (recall ${\bm{M}}({\bm{z}})=0$). Because
$\vec{c}_{i,i^{\prime}}({\bm{z}})=\vec{c}_{i^{\prime},i}({\bm{z}})$, we can
write

$\displaystyle\forall(i,i^{\prime})\in S\ \text{s.t.}\
i\not=i^{\prime},\forall(j,j^{\prime})\in
S^{c},D_{j^{\prime}}{\bm{v}}_{i^{\prime}}({\bm{z}})D_{j}{\bm{v}}_{i}({\bm{z}})+D_{j^{\prime}}{\bm{v}}_{i}({\bm{z}})D_{j}{\bm{v}}_{i^{\prime}}({\bm{z}})=0\,.$
(68)

We now show that if $(j,j^{\prime})\in S^{c}$ (indices belong to different
blocks), then $(\pi(j),\pi(j^{\prime}))\in S^{c}$ (they also belong to
different blocks). Assume this is false, i.e. there exists
$(j_{0},j^{\prime}_{0})\in S^{c}$ such that
$(\pi(j_{0}),\pi(j^{\prime}_{0}))\in S$. Then we can apply (68) (with
$i:=\pi(j_{0})$ and $i^{\prime}:=\pi(j^{\prime}_{0})$) and get

$\displaystyle\underbrace{D_{j_{0}^{\prime}}{\bm{v}}_{\pi(j_{0}^{\prime})}({\bm{z}})D_{j_{0}}{\bm{v}}_{\pi(j_{0})}({\bm{z}})}_{\not=0}+D_{j^{\prime}_{0}}{\bm{v}}_{\pi(j_{0})}({\bm{z}})D_{j_{0}}{\bm{v}}_{\pi(j^{\prime}_{0})}({\bm{z}})=0\,,$
(69)

where the left term in the sum is different of 0 because of the definition of
$\pi$. This implies that

$\displaystyle
D_{j_{0}^{\prime}}{\bm{v}}_{\pi(j_{0})}({\bm{z}})D_{j_{0}}{\bm{v}}_{\pi(j^{\prime}_{0})}({\bm{z}})\not=0\,,$
(70)

otherwise (69) cannot hold. But (70) contradicts (67). Thus, we have that,

$\displaystyle(j,j^{\prime})\in S^{c}\implies(\pi(j),\pi(j^{\prime}))\in
S^{c}\,.$ (71)

The contraposed is

$\displaystyle(\pi(j),\pi(j^{\prime}))\in S\implies(j,j^{\prime})\in S$ (72)
$\displaystyle(j,j^{\prime})\in S\implies(\pi^{-1}(j),\pi^{-1}(j^{\prime}))\in
S\,.$ (73)

From the above, it is clear that $\pi^{-1}$ respects ${\mathcal{B}}$ which
implies that $\pi$ respects ${\mathcal{B}}$ (Lemma 8). Thus
$D{\bm{v}}({\bm{z}})$ is a ${\mathcal{B}}$-block permutation matrix. ∎

######  Lemma 8 (${\mathcal{B}}$-respecting permutations form a group).

Let ${\mathcal{B}}$ be a partition of $\\{1,\dots,d_{z}\\}$ and let $\pi$ and
$\bar{\pi}$ be a permutation of $\\{1,\dots,d_{z}\\}$ that respect
${\mathcal{B}}$. The following holds:

  1. 1.

The identity permutation $e$ respects ${\mathcal{B}}$.

  2. 2.

The composition $\pi\circ\bar{\pi}$ respects ${\mathcal{B}}$.

  3. 3.

The inverse permutation $\pi^{-1}$ respects ${\mathcal{B}}$.

###### Proof.

The first statement is trivial, since for all $B\in{\mathcal{B}}$,
$e(B)=B\in{\mathcal{B}}$.

The second statement follows since for all $B\in{\mathcal{B}}$,
$\bar{\pi}(B)\in{\mathcal{B}}$ and thus $\pi(\bar{\pi}(B))\in{\mathcal{B}}$.

We now prove the third statement. Let $B\in{\mathcal{B}}$. Since $\pi$ is
surjective and respects ${\mathcal{B}}$, there exists a
$B^{\prime}\in{\mathcal{B}}$ such that $\pi(B^{\prime})=B$. Thus,
$\pi^{-1}(B)=\pi^{-1}(\pi(B^{\prime}))=B^{\prime}\in{\mathcal{B}}$. ∎

####  A.5 Sufficient nonlinearity v.s. sufficient variability in nonlinear ICA
with auxiliary variables

In Section 3.1, we introduced the “sufficient nonlinearity” condition
(Assumption 2) and highlighted its resemblance to the “sufficient variability”
assumptions often found in the nonlinear ICA literature [21, 22, 23, 25, 26,
30, 49]. We now clarify this connection. To make the discussion more concrete,
we consider the sufficient variability assumption found in Hyvärinen et al.
[23]. In this work, the latent variable ${\bm{z}}$ is assumed to be
distributed according to

$\displaystyle
p({\bm{z}}\mid{\bm{u}}):=\prod_{i=1}^{d_{z}}p_{i}({\bm{z}}_{i}\mid{\bm{u}})\,.$
(74)

In other words, the latent factors ${\bm{z}}_{i}$ are mutually conditionally
independent given an observed auxiliary variable ${\bm{u}}$. Define

$\displaystyle{\bm{w}}({\bm{z}},{\bm{u}}):=\left(\left(\frac{\partial}{\partial{\bm{z}}_{i}}\log
p_{i}({\bm{z}}_{i}\mid{\bm{u}})\right)_{i\in[d_{z}]}\
\left(\frac{\partial^{2}}{\partial{\bm{z}}_{i}^{2}}\log
p_{i}({\bm{z}}_{i}\mid{\bm{u}})\right)_{i\in[d_{z}]}\right)\in{\mathbb{R}}^{2d_{z}}\,.$
(75)

We now recall the assumption of sufficient variability of Hyvärinen et al.
[23]:

######  Assumption 3 (Assumption of variability from Hyvärinen et al. [23,
Theorem 1]).

For any ${\bm{z}}\in{\mathbb{R}}^{d_{z}}$, there exists $2d_{z}+1$ values of
${\bm{u}}$, denoted by
${\bm{u}}^{(0)},{\bm{u}}^{(1)},\dots,{\bm{u}}^{(2d_{z})}$ such that the
$2d_{z}$ vectors

$\displaystyle{\bm{w}}({\bm{z}},{\bm{u}}^{(1)})-{\bm{w}}({\bm{z}},{\bm{u}}^{(0)}),\dots,{\bm{w}}({\bm{z}},{\bm{u}}^{(2d_{z})})-{\bm{w}}({\bm{z}},{\bm{u}}^{(0)})\,$
(76)

are linearly independent.

To emphasize the resemblance with our assumption of sufficient nonlinearity,
we rewrite it in the special case where the partition
${\mathcal{B}}:=\\{\\{1\\},\dots,\\{d_{z}\\}\\}$. Note that, in that case,
$q:=d_{z}+\sum_{B\in{\mathcal{B}}}\frac{|B|(|B|+1)}{2}=2d_{z}$.

######  Assumption 4 (Sufficient nonlinearity (trivial partition)).

For all ${\bm{z}}\in{\mathcal{Z}}^{\textnormal{train}}$, ${\bm{f}}$ is such
that the following matrix has independent columns (i.e. full column-rank):

$\displaystyle{\bm{W}}({\bm{z}})$
$\displaystyle:=\left[\left[D_{i}{\bm{f}}^{(i)}({\bm{z}}_{i})\right]_{i\in[d_{z}]}\
\left[D^{2}_{i,i}{\bm{f}}^{(i)}({\bm{z}}_{i})\right]_{i\in[d_{z}]}\right]\in{\mathbb{R}}^{d_{x}\times
2d_{z}}\,.$ (77)

One can already see the resemblance between Assumptions 3 & 4, e.g. both have
something to do with first and second derivatives. To make the connection even
more explicit, define ${\bm{w}}({\bm{z}},k)$ to be the $k$th row of
${\bm{W}}({\bm{z}})$ (do not conflate with ${\bm{w}}({\bm{z}},{\bm{u}})$).
Also, recall the basic fact from linear algebra that the column-rank is always
equal to the row-rank. This means that ${\bm{W}}({\bm{z}})$ is full column-
rank if and only if there exists $k_{1}$, …, $k_{2d_{z}}\in[d_{x}]$ such that
the vectors ${\bm{w}}({\bm{z}},k_{1}),\dots,{\bm{w}}({\bm{z}},k_{2d_{z}})$ are
linearly independent. It is then easy to see the correspondance between
${\bm{w}}({\bm{z}},k)$ and
${\bm{w}}({\bm{z}},{\bm{u}})-{\bm{w}}({\bm{z}},{\bm{u}}^{(0)})$ (from
Assumption 3) and between the pixel index $k\in[d_{x}]$ and the auxiliary
variable ${\bm{u}}$.

####  A.6 Example of a sufficiently nonlinear additive decoder

######  Example 7 (A sufficiently nonlinear ${\bm{f}}$ \- Example 3
continued).

Consider the additive function

$\displaystyle{\bm{f}}({\bm{z}}):=\begin{bmatrix}{\bm{z}}_{1}\\\
{\bm{z}}_{1}^{2}\\\ {\bm{z}}_{1}^{3}\\\
{\bm{z}}_{1}^{4}\end{bmatrix}+\begin{bmatrix}({\bm{z}}_{2}+1)\\\
({\bm{z}}_{2}+1)^{2}\\\ ({\bm{z}}_{2}+1)^{3}\\\
({\bm{z}}_{2}+1)^{4}\end{bmatrix}\,.$ (78)

We will provide a numerical verification that this function is a
diffeomorphism from the square $[-1,0]\times[0,1]$ to its image that satisfies
Assumption 2.

The Jacobian of ${\bm{f}}$ is given by

$\displaystyle D{\bm{f}}({\bm{z}})=\begin{bmatrix}1&1\\\
2{\bm{z}}_{1}&2({\bm{z}}_{2}+1)\\\ 3{\bm{z}}_{1}^{2}&3({\bm{z}}_{2}+1)^{2}\\\
4{\bm{z}}_{1}^{3}&4({\bm{z}}_{2}+1)^{3}\\\ \end{bmatrix}\,,$ (79)

and the matrix ${\bm{W}}({\bm{z}})$ from Assumption 2 is given by

$\displaystyle{\bm{W}}({\bm{z}})=\begin{bmatrix}1&0&1&0\\\
2{\bm{z}}_{1}&2&2({\bm{z}}_{2}+1)&2\\\
3{\bm{z}}_{1}^{2}&6{\bm{z}}_{1}&3({\bm{z}}_{2}+1)^{2}&6({\bm{z}}_{2}+1)\\\
4{\bm{z}}_{1}^{3}&12{\bm{z}}_{1}^{2}&4({\bm{z}}_{2}+1)^{3}&12({\bm{z}}_{2}+1)^{2}\end{bmatrix}\,.$
(80)

Figure 7 presents a numerical verification that ${\bm{f}}$ is injective, has a
full rank Jacobian and satisfies Assumption 2. Injective ${\bm{f}}$ with full
rank Jacobian is enough to conclude that ${\bm{f}}$ is a diffeomorphism onto
its image.

Figure 7: Numerical verification that
${\bm{f}}:[-1,0]\times[0,1]\rightarrow{\mathbb{R}}^{4}$ from Example 7 is
injective (left), has a full rank Jacobian (middle) and satisfies Assumption 2
(right). The left figure shows that ${\bm{f}}$ is injective on the square
$[-1,0]\times[0,1]$ since one can recover ${\bm{z}}$ uniquely by knowing the
values of ${\bm{f}}_{1}({\bm{z}})$ and ${\bm{f}}_{2}({\bm{z}})$, i.e. knowing
the level sets. The middle figure reports the
$\det(D{\bm{f}}({\bm{z}})^{\top}D{\bm{f}}({\bm{z}}))$ and shows that it is
nonzero in the square $[-1,0]\times[0,1]$, which means the Jacobian is full
rank. The right figure shows the determinant of the matrix
${\bm{W}}({\bm{z}})$ (from Assumption 2), we can see that it is nonzero
everywhere on the square $[-1,0]\times[0,1]$.

####  A.7 Proof of Theorem 2

We start with a simple definition:

######  Definition 13 (${\mathcal{B}}$-block permutation matrices).

A matrix ${\bm{A}}\in{\mathbb{R}}^{d\times d}$ is a ${\mathcal{B}}$-block
permutation matrix if it is invertible and can be written as
${\bm{A}}={\bm{C}}{\bm{P}}_{\pi}$ where ${\bm{P}}_{\pi}$ is the matrix
representing the ${\mathcal{B}}$-respecting permutation $\pi$
($P_{\pi}{\bm{e}}_{i}={\bm{e}}_{\pi(i)}$) and
${\bm{C}}\in{\mathbb{R}}^{d\times d}_{S_{\mathcal{B}}}$ (See Definitions 9 &
10).

The following technical lemma leverages continuity and path-connectedness to
show that the block-permutation structure must remain the same across the
whole domain. It can be skipped at first read.

######  Lemma 9.

Let ${\mathcal{C}}$ be a connected subset of some topological space and let
${\bm{M}}:{\mathcal{C}}\rightarrow{\mathbb{R}}^{d\times d}$ be a continuous
function. Suppose that, for all $c\in{\mathcal{C}}$, ${\bm{M}}(c)$ is a
${\mathcal{B}}$-block permutation matrix (Definition 13). Then, there exists a
${\mathcal{B}}$-respecting permutation $\pi$ such that for all
$c\in{\mathcal{C}}$ and all distinct $B,B^{\prime}\in{\mathcal{B}}$,
${\bm{M}}(c)_{\pi(B^{\prime}),B}=0$.

###### Proof.

The reason this result is not trivial, is that, even if ${\bm{M}}(c)$ is a
${\mathcal{B}}$-block permutation for all $c$, the permutation might change
for different $c$. The goal of this lemma is to show that, if ${\mathcal{C}}$
is connected and the map ${\bm{M}}(\cdot)$ is continuous, then one can find a
single permutation that works for all $c\in{\mathcal{C}}$.

First, since ${\mathcal{C}}$ is connected and ${\bm{M}}$ is continuous, its
image, ${\bm{M}}({\mathcal{C}})$, must be connected (by [39, Theorem 23.5]).

Second, from the hypothesis of the lemma, we know that

$\displaystyle{\bm{M}}({\mathcal{C}})\subseteq{\mathcal{A}}:=\left(\bigcup_{\pi\in\mathfrak{S}({\mathcal{B}})}{\mathbb{R}}^{d\times
d}_{S_{\mathcal{B}}}{\bm{P}}_{\pi}\right)\setminus\\{\text{singular
matrices}\\}\,,$ (81)

where $\mathfrak{S}({\mathcal{B}})$ is the set of ${\mathcal{B}}$-respecting
permutations and ${\mathbb{R}}^{d\times
d}_{S_{\mathcal{B}}}{\bm{P}}_{\pi}=\\{{\bm{M}}{\bm{P}}_{\pi}\mid{\bm{M}}\in{\mathbb{R}}_{S_{\mathcal{B}}}^{d\times
d}\\}$. We can rewrite the set ${\mathcal{A}}$ above as

$\displaystyle{\mathcal{A}}=\bigcup_{\pi\in\mathfrak{S}({\mathcal{B}})}\left({\mathbb{R}}^{d\times
d}_{S_{\mathcal{B}}}{\bm{P}}_{\pi}\setminus\\{\text{singular
matrices}\\}\right)\,,$ (82)

We now define an equivalence relation $\sim$ over ${\mathcal{B}}$-respecting
permutation: $\pi\sim\pi^{\prime}$ iff for all $B\in{\mathcal{B}}$,
$\pi(B)=\pi^{\prime}(B)$. In other words, two ${\mathcal{B}}$-respecting
permutations are equivalent if they send every block to the same block (note
that they can permute elements of a given block differently). We notice that

$\displaystyle\pi\sim\pi^{\prime}\implies{\mathbb{R}}^{d\times
d}_{S_{\mathcal{B}}}{\bm{P}}_{\pi}={\mathbb{R}}^{d\times
d}_{S_{\mathcal{B}}}{\bm{P}}_{\pi^{\prime}}\,.$ (83)

Let $\mathfrak{S}({\mathcal{B}})/\sim$ be the set of equivalence classes
induce by $\sim$ and let $\Pi$ stand for one such equivalence class. Thanks to
(83), we can define, for all $\Pi\in\mathfrak{S}({\mathcal{B}})/\sim$, the
following set:

$\displaystyle V_{\Pi}:={\mathbb{R}}^{d\times
d}_{S_{\mathcal{B}}}{\bm{P}}_{\pi}\setminus\\{\text{singular matrices}\\},\
\text{for some $\pi\in\Pi$}\,,$ (84)

where the specific choice of $\pi\in\Pi$ is arbitrary (any
$\pi^{\prime}\in\Pi$ would yield the same definition, by (83)). This
construction allows us to write

$\displaystyle{\mathcal{A}}=\bigcup_{\Pi\in\mathfrak{S}({\mathcal{B}})/\sim}V_{\Pi}\,,$
(85)

We now show that $\\{V_{\Pi}\\}_{\Pi\in\mathfrak{S}({\mathcal{B}})/\sim}$
forms a partition of ${\mathcal{A}}$. Choose two distinct equivalence classes
of permutations $\Pi$ and $\Pi^{\prime}$ and let $\pi\in\Pi$ and
$\pi^{\prime}\in\Pi^{\prime}$ be representatives. We note that

$\displaystyle{\mathbb{R}}^{d\times
d}_{S_{\mathcal{B}}}{\bm{P}}_{\pi}\cap{\mathbb{R}}^{d\times
d}_{S_{\mathcal{B}}}{\bm{P}}_{\pi^{\prime}}\subseteq\\{\text{singular
matrices}\\}\,,$ (86)

since any matrix that is both in ${\mathbb{R}}^{d\times
d}_{S_{\mathcal{B}}}{\bm{P}}_{\pi}$ and ${\mathbb{R}}^{d\times
d}_{S_{\mathcal{B}}}{\bm{P}}_{\pi^{\prime}}$ must have at least one row filled
with zeros. This implies that

$\displaystyle V_{\Pi}\cap V_{\Pi^{\prime}}=\emptyset\,,$ (87)

which shows that $\\{V_{\Pi}\\}_{\Pi\in\mathfrak{S}({\mathcal{B}})/\sim}$ is
indeed a partition of ${\mathcal{A}}$.

Each $V_{\Pi}$ is closed in ${\mathcal{A}}$ (wrt the relative topology) since

$\displaystyle V_{\Pi}={\mathbb{R}}^{d\times
d}_{S_{\mathcal{B}}}{\bm{P}}_{\pi}\setminus\\{\text{singular
matrices}\\}={\mathcal{A}}\cap\underbrace{{\mathbb{R}}^{d\times
d}_{S_{\mathcal{B}}}{\bm{P}}_{\pi}}_{\text{closed in ${\mathbb{R}}^{d\times
d}$}}.$ (88)

Moreover, $V_{\Pi}$ is open in ${\mathcal{A}}$, since

$\displaystyle
V_{\Pi}={\mathcal{A}}\setminus\underbrace{\bigcup_{\Pi^{\prime}\not=\Pi}V_{\Pi^{\prime}}}_{\text{closed
in ${\mathcal{A}}$}}\,.$ (89)

Thus, for any $\Pi\in\mathfrak{S}({\mathcal{B}})/\sim$, the sets $V_{\Pi}$ and
$\bigcup_{\Pi^{\prime}\not=\Pi}V_{\Pi^{\prime}}$ forms a separation (see [39,
Section 23]). Since ${\bm{M}}({\mathcal{C}})$ is a connected subset of
${\mathcal{A}}$, it must lie completely in $V_{\Pi}$ or
$\bigcup_{\Pi^{\prime}\not=\Pi}V_{\Pi^{\prime}}$, by [39, Lemma 23.2]. Since
this is true for all $\Pi$, it must follow that there exists a $\Pi^{*}$ such
that ${\bm{M}}({\mathcal{C}})\subseteq\Pi^{*}$, which completes the proof. ∎

See 2

###### Proof.

Step 1 - Showing the permutation $\pi$ does not change for different
${\bm{z}}$. Theorem 1 showed local ${\mathcal{B}}$-disentanglement, i.e. for
all ${\bm{z}}\in\hat{\mathcal{Z}}^{\textnormal{train}}$, $D{\bm{v}}({\bm{z}})$
has a ${\mathcal{B}}$-block permutation structure. The first step towards
showing global disentanglement is to show that this block structure is the
same for all ${\bm{z}}\in\hat{\mathcal{Z}}^{\textnormal{train}}$ (a priori,
$\pi$ could be different for different ${\bm{z}}$). Since ${\bm{v}}$ is
$C^{2}$, its Jacobian $D{\bm{v}}({\bm{z}})$ is continuous. Since
${\mathcal{Z}}^{\textnormal{train}}$ is path-connected,
$\hat{\mathcal{Z}}^{\textnormal{train}}$ must also be since both sets are
diffeomorphic. By Lemma 9, this means the ${\mathcal{B}}$-block permutation
structure of $D{\bm{v}}({\bm{z}})$ is the same for all
${\bm{z}}\in\hat{\mathcal{Z}}^{\textnormal{train}}$ (implicitly using the fact
that path-connected implies connected). In other words, for all
${\bm{z}}\in\hat{\mathcal{Z}}^{\textnormal{train}}$ and all distinct
$B,B^{\prime}\in{\mathcal{B}}$, $D_{B}{\bm{v}}_{\pi(B^{\prime})}({\bm{z}})=0$.

Step 1 - Linking object-specific decoders. We now show that, for all
$B\in{\mathcal{B}}$,
$\hat{\bm{f}}^{(B)}({\bm{z}}_{B})={\bm{f}}^{(\pi(B))}({\bm{v}}_{\pi(B)}({\bm{z}}))+{\bm{c}}^{(B)}$
for all ${\bm{z}}\in\hat{\mathcal{Z}}^{\textnormal{train}}$. To do this, we
rewrite (49) as

$\displaystyle
D\hat{\bm{f}}^{(J)}({\bm{z}}_{J})=\sum_{B\in{\mathcal{B}}}D{\bm{f}}^{(B)}({\bm{v}}_{B}({\bm{z}}))D_{J}{\bm{v}}_{B}({\bm{z}})\,,$
(90)

but because $B\not=\pi(J)\implies D_{J}{\bm{v}}_{B}({\bm{z}})=0$ (block-
permutation structure), we get

$\displaystyle
D\hat{\bm{f}}^{(J)}({\bm{z}}_{J})=D{\bm{f}}^{(\pi(J))}({\bm{v}}_{\pi(J)}({\bm{z}}))D_{J}{\bm{v}}_{\pi(J)}({\bm{z}})\,.$
(91)

The above holds for all $J\in{\mathcal{B}}$. We simply change $J$ by $B$ in
the following equation.

$\displaystyle
D\hat{\bm{f}}^{(B)}({\bm{z}}_{B})=D{\bm{f}}^{(\pi(B))}({\bm{v}}_{\pi(B)}({\bm{z}}))D_{B}{\bm{v}}_{\pi(B)}({\bm{z}})\,.$
(92)

Now notice that the r.h.s. of the above equation is equal to
$D({\bm{f}}^{(\pi(B))}\circ{\bm{v}}_{\pi(B)})$. We can thus write

$\displaystyle
D\hat{\bm{f}}^{(B)}({\bm{z}}_{B})=D({\bm{f}}^{(\pi(B))}\circ{\bm{v}}_{\pi(B)})({\bm{z}})\,,\text{for
all }{\bm{z}}\in\hat{\mathcal{Z}}^{\textnormal{train}}\,.$ (93)

Now choose distinct
${\bm{z}},{\bm{z}}^{0}\in\hat{\mathcal{Z}}^{\textnormal{train}}$. Since
${\mathcal{Z}}^{\textnormal{train}}$ is path-connected,
$\hat{\mathcal{Z}}^{\textnormal{train}}$ also is since they are diffeomorphic.
Hence, there exists a continuously differentiable function
$\bm{\phi}:[0,1]\rightarrow\hat{\mathcal{Z}}^{\textnormal{train}}$ such that
$\bm{\phi}(0)={\bm{z}}^{0}$ and $\bm{\phi}(1)={\bm{z}}$. We can now use (93)
together with the gradient theorem, a.k.a. the fundamental theorem of calculus
for line integrals, to show the following

$\displaystyle\int_{0}^{1}D\hat{\bm{f}}^{(B)}(\bm{\phi}_{B}({\bm{z}}))\cdot\bm{\phi}_{B}(t)dt$
$\displaystyle=\int_{0}^{1}D({\bm{f}}^{(\pi(B))}\circ{\bm{v}}_{\pi(B)})(\bm{\phi}({\bm{z}}))\cdot\bm{\phi}(t)dt$
(94)
$\displaystyle\hat{\bm{f}}^{(B)}({\bm{z}}_{B})-\hat{\bm{f}}^{(B)}({\bm{z}}_{B}^{0})$
$\displaystyle={\bm{f}}^{(\pi(B))}\circ{\bm{v}}_{\pi(B)}({\bm{z}})-{\bm{f}}^{(\pi(B))}\circ{\bm{v}}_{\pi(B)}({\bm{z}}^{0})$
(95) $\displaystyle\hat{\bm{f}}^{(B)}({\bm{z}}_{B})$
$\displaystyle={\bm{f}}^{(\pi(B))}\circ{\bm{v}}_{\pi(B)}({\bm{z}})+\underbrace{(\hat{\bm{f}}^{(B)}({\bm{z}}_{B}^{0})-{\bm{f}}^{(\pi(B))}\circ{\bm{v}}_{\pi(B)}({\bm{z}}^{0}))}_{\text{constant
in ${\bm{z}}$}}$ (96) $\displaystyle\hat{\bm{f}}^{(B)}({\bm{z}}_{B})$
$\displaystyle={\bm{f}}^{(\pi(B))}\circ{\bm{v}}_{\pi(B)}({\bm{z}})+{\bm{c}}^{(B)}\,,$
(97)

which holds for all ${\bm{z}}\in\hat{\mathcal{Z}}^{\textnormal{train}}$.

We now show that $\sum_{B\in{\mathcal{B}}}{\bm{c}}^{(B)}=0$. Take some
${\bm{z}}^{0}\in{\mathcal{Z}}^{\textnormal{train}}$. Equations (48) & (97)
tell us that

$\displaystyle\sum_{B\in{\mathcal{B}}}{\bm{f}}^{(B)}({\bm{v}}_{B}({\bm{z}}^{0}))$
$\displaystyle=\sum_{B\in{\mathcal{B}}}\hat{\bm{f}}^{(B)}({\bm{z}}^{0}_{B})$
(98)
$\displaystyle=\sum_{B\in{\mathcal{B}}}{\bm{f}}^{(\pi(B))}({\bm{v}}_{\pi(B)}({\bm{z}}^{0}))+\sum_{B\in{\mathcal{B}}}{\bm{c}}^{(B)}$
(99)
$\displaystyle=\sum_{B\in{\mathcal{B}}}{\bm{f}}^{(B)}({\bm{v}}_{B}({\bm{z}}^{0}))+\sum_{B\in{\mathcal{B}}}{\bm{c}}^{(B)}$
(100) $\displaystyle\implies 0$
$\displaystyle=\sum_{B\in{\mathcal{B}}}{\bm{c}}^{(B)}$ (101)

Step 2 - From local to global disentanglement. By assumption, the functions
${\bm{f}}^{(B)}:{\mathcal{Z}}^{\textnormal{train}}_{B}\rightarrow{\mathbb{R}}^{d_{x}}$
are injective. This will allow us to show that ${\bm{v}}_{\pi(B)}({\bm{z}})$
depends only on ${\bm{z}}_{B}$. We proceed by contradiction. Suppose there
exists
$({\bm{z}}_{B},{\bm{z}}_{B^{c}})\in\hat{\mathcal{Z}}^{\textnormal{train}}$ and
${\bm{z}}^{0}_{B^{c}}$ such that
$({\bm{z}}_{B},{\bm{z}}^{0}_{B^{c}})\in\hat{\mathcal{Z}}^{\textnormal{train}}$
and
${\bm{v}}_{\pi(B)}({\bm{z}}_{B},{\bm{z}}_{B^{c}})\not={\bm{v}}_{\pi(B)}({\bm{z}}_{B},{\bm{z}}^{0}_{B^{c}})$.
This means

${\bm{f}}^{(\pi(B))}\circ{\bm{v}}_{\pi(B)}({\bm{z}}_{B},{\bm{z}}_{B})+{\bm{c}}^{(B)}=\hat{\bm{f}}^{(B)}({\bm{z}}_{B})={\bm{f}}^{(\pi(B))}\circ{\bm{v}}_{\pi(B)}({\bm{z}}_{B},{\bm{z}}^{0}_{B})+{\bm{c}}^{(B)}$
${\bm{f}}^{(\pi(B))}({\bm{v}}_{\pi(B)}({\bm{z}}_{B},{\bm{z}}_{B}))={\bm{f}}^{(\pi(B))}({\bm{v}}_{\pi(B)}({\bm{z}}_{B},{\bm{z}}^{0}_{B}))$

which is a contradiction with the fact that ${\bm{f}}^{(\pi(B))}$ is
injective. Hence, ${\bm{v}}_{\pi(B)}({\bm{z}})$ depends only on
${\bm{z}}_{B}$. We also get an explicit form for ${\bm{v}}_{\pi(B)}$:

$\displaystyle({\bm{f}}^{\pi(B)})^{-1}(\hat{\bm{f}}^{(B)}({\bm{z}}_{B})-{\bm{c}}^{(B)})$
$\displaystyle={\bm{v}}_{\pi(B)}({\bm{z}})\text{ for all
}{\bm{z}}\in{\mathcal{Z}}^{\textnormal{train}}\,.$ (102)

We define the map
$\bar{\bm{v}}_{\pi(B)}({\bm{z}}_{B}):=({\bm{f}}^{\pi(B)})^{-1}(\hat{\bm{f}}^{(B)}({\bm{z}}_{B})-{\bm{c}}^{(B)})$
which is from $\hat{\mathcal{Z}}^{\textnormal{train}}_{B}$ to
${\mathcal{Z}}^{\textnormal{train}}_{\pi(B)}$. This allows us to rewrite (97)
as

$\displaystyle\hat{\bm{f}}^{(B)}({\bm{z}}_{B})$
$\displaystyle={\bm{f}}^{(\pi(B))}\circ\bar{\bm{v}}_{\pi(B)}({\bm{z}}_{B})+{\bm{c}}^{(B)}\,,\text{
for all }{\bm{z}}_{B}\in{\mathcal{Z}}^{\textnormal{train}}_{B}\,.$ (103)

Because $\hat{\bm{f}}^{(B)}$ is also injective, we must have that
$\bar{\bm{v}}_{\pi(B)}:\hat{\mathcal{Z}}^{\textnormal{train}}_{B}\rightarrow{\mathcal{Z}}^{\textnormal{train}}_{\pi(B)}$
is injective as well.

We now show that $\bar{\bm{v}}_{\pi(B)}$ is surjective. Choose some
${\bm{z}}_{\pi(B)}\in{\mathcal{Z}}^{\textnormal{train}}_{\pi(B)}$. We can
always find ${\bm{z}}_{\pi(B)^{c}}$ such that
$({\bm{z}}_{\pi(B)},{\bm{z}}_{\pi(B)^{c}})\in{\mathcal{Z}}^{\textnormal{train}}$.
Because
${\bm{v}}:\hat{\mathcal{Z}}^{\textnormal{train}}\rightarrow{\mathcal{Z}}^{\textnormal{train}}$
is surjective (it is a diffeomorphism), there exists a
${\bm{z}}^{0}\in\hat{\mathcal{Z}}^{\textnormal{train}}$ such that
${\bm{v}}({\bm{z}}^{0})=({\bm{z}}_{\pi(B)},{\bm{z}}_{\pi(B)^{c}})$. By (102),
we have that

$\displaystyle\bar{\bm{v}}_{\pi(B)}({\bm{z}}^{0}_{B})={\bm{v}}_{\pi(B)}({\bm{z}}^{0})\,.$
(104)

which means $\bar{\bm{v}}_{\pi(B)}({\bm{z}}^{0}_{B})={\bm{z}}_{\pi(B)}$.

We thus have that $\bar{\bm{v}}_{\pi(B)}$ is bijective. It is a diffeomorphism
because

$\displaystyle\det D\bar{\bm{v}}_{\pi(B)}({\bm{z}}_{B})=\det
D_{B}{\bm{v}}_{\pi(B)}({\bm{z}})\not=0\
\forall{\bm{z}}\in\hat{\mathcal{Z}}^{\textnormal{train}}$ (105)

where the first equality holds by (102) and the second holds because
${\bm{v}}$ is a diffeomorphism and has block-permutation structure, which
means it has a nonzero determinant everywhere on
$\hat{\mathcal{Z}}^{\textnormal{train}}$ and is equal to the product of the
determinants of its blocks, which implies each block $D_{B}{\bm{v}}_{\pi(B)}$
must have nonzero determinant everywhere.

Since
$\bar{\bm{v}}_{\pi(B)}:\hat{\mathcal{Z}}_{B}^{\textnormal{train}}\rightarrow{\mathcal{Z}}^{\textnormal{train}}_{\pi(B)}$
bijective and has invertible Jacobian everywhere, it must be a diffeomorphism.
∎

####  A.8 Injectivity of object-specific decoders v.s. injectivity of their
sum

We want to explore the relationship between the injectivity of individual
object-specific decoders ${\bm{f}}^{(B)}$ and the injectivity of their sum,
i.e. $\sum_{B\in{\mathcal{B}}}{\bm{f}}^{(B)}$.

We first show the simple fact that having each ${\bm{f}}^{(B)}$ injective is
not sufficient to have $\sum_{B\in{\mathcal{B}}}{\bm{f}}^{(B)}$ injective.
Take ${\bm{f}}^{(B)}({\bm{z}}_{B})={\bm{W}}^{(B)}{\bm{z}}_{B}$ where
${\bm{W}}^{(B)}\in{\mathbb{R}}^{d_{x}\times|B|}$ has full column-rank for all
$B\in{\mathcal{B}}$. We have that

$\displaystyle\sum_{B\in{\mathcal{B}}}{\bm{f}}^{(B)}({\bm{z}}_{B})=\sum_{B\in{\mathcal{B}}}{\bm{W}}^{(B)}{\bm{z}}_{B}=[{\bm{W}}^{(B_{1})}\
\cdots\ {\bm{W}}^{(B_{\ell})}]{\bm{z}}\,,$ (106)

where it is clear that the matrix $[{\bm{W}}^{(B_{1})}\ \cdots\
{\bm{W}}^{(B_{\ell})}]\in{\mathbb{R}}^{d_{x}\times d_{z}}$ is not necessarily
injective even if each ${\bm{W}}^{(B)}$ is. This is the case, for instance, if
all ${\bm{W}}^{(B)}$ have the same image.

We now provide conditions such that $\sum_{B\in{\mathcal{B}}}{\bm{f}}^{(B)}$
injective implies each ${\bm{f}}^{(B)}$ injective. We start with a simple
lemma:

######  Lemma 10.

If $g\circ h$ is injective, then $h$ is injective.

###### Proof.

By contradiction, assume that $h$ is not injective. Then, there exists
distinct $x_{1},x_{2}\in\text{Dom}(h)$ such that $h(x_{1})=h(x_{2})$. This
implies $g\circ h(x_{1})=g\circ h(x_{2})$, which violates injectivity of
$g\circ h$. ∎

The following Lemma provides a condition on the domain of the function
$\sum_{B\in{\mathcal{B}}}{\bm{f}}^{(B)}$,
${\mathcal{Z}}^{\textnormal{train}}$, so that its injectivity implies
injectivity of the functions ${\bm{f}}^{(B)}$.

######  Lemma 11.

Assume that, for all $B\in{\mathcal{B}}$ and for all distinct
${\bm{z}}_{B},{\bm{z}}^{\prime}_{B}\in{\mathcal{Z}}^{\textnormal{train}}_{B}$,
there exists ${\bm{z}}_{B^{c}}$ such that
$({\bm{z}}_{B},{\bm{z}}_{B^{c}}),({\bm{z}}^{\prime}_{B},{\bm{z}}_{B^{c}})\in{\mathcal{Z}}^{\textnormal{train}}$.
Then, whenever $\sum_{B\in{\mathcal{B}}}{\bm{f}}^{(B)}$ is injective, each
${\bm{f}}^{(B)}$ must be injective.

###### Proof.

Notice that
${\bm{f}}({\bm{z}}):=\sum_{B\in{\mathcal{B}}}{\bm{f}}^{(B)}({\bm{z}}_{B})$ can
be written as ${\bm{f}}:=\text{SumBlocks}\circ\bar{\bm{f}}({\bm{z}})$ where

$\displaystyle\bar{\bm{f}}({\bm{z}}):=\begin{bmatrix}{\bm{f}}^{(B_{1})}({\bm{z}}_{B_{1}})\\\
\vdots\\\ {\bm{f}}^{(B_{\ell})}({\bm{z}}_{B_{\ell}})\end{bmatrix}\,,\text{ and
}\text{SumBlocks}({\bm{x}}^{(B_{1})},\dots,{\bm{x}}^{(B_{\ell})}):=\sum_{B\in{\mathcal{B}}}{\bm{x}}^{(B)}$
(107)

Since ${\bm{f}}$ is injective, by Lemma 10 $\bar{\bm{f}}$ must be injective.

We now show that each ${\bm{f}}^{(B)}$ must also be injective. Take
${\bm{z}}_{B},{\bm{z}}^{\prime}_{B}\in{\mathcal{Z}}^{\textnormal{train}}_{B}$
such that
${\bm{f}}^{(B)}({\bm{z}}_{B})={\bm{f}}^{(B)}({\bm{z}}^{\prime}_{B})$. By
assumption, we know there exists a ${\bm{z}}_{B^{c}}$ s.t.
$({\bm{z}}_{B},{\bm{z}}_{B^{c}})$ and
$({\bm{z}}^{\prime}_{B},{\bm{z}}_{B^{c}})$ are in
${\mathcal{Z}}^{\textnormal{train}}$. By construction, we have that
$\bar{\bm{f}}(({\bm{z}}_{B},{\bm{z}}_{B^{c}}))=\bar{\bm{f}}(({\bm{z}}^{\prime}_{B},{\bm{z}}_{B^{c}}))$.
By injectivity of $\bar{\bm{f}}$, we have that
$({\bm{z}}_{B},{\bm{z}}_{B^{c}})\not=({\bm{z}}^{\prime}_{B},{\bm{z}}_{B^{c}})$,
which implies ${\bm{z}}_{B}\not={\bm{z}}^{\prime}_{B}$, i.e. ${\bm{f}}^{(B)}$
is injective. ∎

####  A.9 Proof of Corollary 3

See 3

###### Proof.

Pick ${\bm{z}}\in\textnormal{CPE}(\hat{\mathcal{Z}}^{\textnormal{train}})$. By
definition, this means that, for all $B\in{\mathcal{B}}$,
${\bm{z}}_{B}\in\hat{\mathcal{Z}}^{\textnormal{train}}_{B}$. We thus have
that, for all $B\in{\mathcal{B}}$,

$\displaystyle\hat{\bm{f}}^{(B)}({\bm{z}}_{B})$
$\displaystyle={\bm{f}}^{(\pi(B))}\circ\bar{\bm{v}}_{\pi(B)}({\bm{z}}_{B})+{\bm{c}}^{(B)}\,.$
(108)

We can thus sum over $B$ to obtain

$\displaystyle\sum_{B\in{\mathcal{B}}}\hat{\bm{f}}^{(B)}({\bm{z}}_{B})$
$\displaystyle=\sum_{B\in{\mathcal{B}}}{\bm{f}}^{(\pi(B))}\circ\bar{\bm{v}}_{\pi(B)}({\bm{z}}_{B})+\underbrace{\sum_{B\in{\mathcal{B}}}{\bm{c}}^{(B)}}_{=0}\,.$
(109)

Since ${\bm{z}}\in\textnormal{CPE}(\hat{\mathcal{Z}}^{\textnormal{train}})$
was arbitrary, we have

$\displaystyle\text{for all
}{\bm{z}}\in\textnormal{CPE}(\hat{\mathcal{Z}}^{\textnormal{train}}),\
\sum_{B\in{\mathcal{B}}}\hat{\bm{f}}^{(B)}({\bm{z}}_{B})$
$\displaystyle=\sum_{B\in{\mathcal{B}}}{\bm{f}}^{(\pi(B))}\circ\bar{\bm{v}}_{\pi(B)}({\bm{z}}_{B})$
(110)
$\displaystyle\sigma(\sum_{B\in{\mathcal{B}}}\hat{\bm{f}}^{(B)}({\bm{z}}_{B}))$
$\displaystyle=\sigma(\sum_{B\in{\mathcal{B}}}{\bm{f}}^{(\pi(B))}\circ\bar{\bm{v}}_{\pi(B)}({\bm{z}}_{B}))$
(111)
$\displaystyle\hat{\bm{f}}({\bm{z}})={\bm{f}}\circ\bar{\bm{v}}({\bm{z}})\,,$
(112)

where
$\bar{\bm{v}}:\textnormal{CPE}_{\mathcal{B}}(\hat{\mathcal{Z}}^{\textnormal{train}})\rightarrow\textnormal{CPE}_{\mathcal{B}}({\mathcal{Z}}^{\textnormal{train}})$
is defined as

$\displaystyle\bar{\bm{v}}({\bm{z}}):=\begin{bmatrix}\bar{\bm{v}}_{B_{1}}({\bm{z}}_{\pi^{-1}(B_{1})})\\\
\vdots\\\
\bar{\bm{v}}_{B_{\ell}}({\bm{z}}_{\pi^{-1}(B_{\ell})})\end{bmatrix}\,,$ (113)

The map $\bar{\bm{v}}$ is a diffeomorphism since each $\bar{\bm{v}}_{\pi(B)}$
is a diffeomorphism from $\hat{\mathcal{Z}}^{\textnormal{train}}_{B}$ to
${\mathcal{Z}}^{\textnormal{train}}_{\pi(B)}$.

By (112) we get

$\displaystyle\hat{\bm{f}}(\textnormal{CPE}_{\mathcal{B}}(\hat{\mathcal{Z}}^{\textnormal{train}}))={\bm{f}}\circ\bar{\bm{v}}(\textnormal{CPE}_{\mathcal{B}}(\hat{\mathcal{Z}}^{\textnormal{train}}))\,,$
(114)

and since the map $\bar{\bm{v}}$ is surjective we have
$\bar{\bm{v}}(\textnormal{CPE}_{\mathcal{B}}(\hat{\mathcal{Z}}^{\textnormal{train}}))=\textnormal{CPE}_{\mathcal{B}}({\mathcal{Z}}^{\textnormal{train}})$
and thus

$\displaystyle\hat{\bm{f}}(\textnormal{CPE}_{\mathcal{B}}(\hat{\mathcal{Z}}^{\textnormal{train}}))={\bm{f}}(\textnormal{CPE}_{\mathcal{B}}({\mathcal{Z}}^{\textnormal{train}}))\,.$
(115)

Hence if
$\textnormal{CPE}_{\mathcal{B}}({\mathcal{Z}}^{\textnormal{train}})\subseteq{\mathcal{Z}}^{\textnormal{test}}$,
then
${\bm{f}}(\textnormal{CPE}_{\mathcal{B}}({\mathcal{Z}}^{\textnormal{train}}))\subseteq{\bm{f}}({\mathcal{Z}}^{\textnormal{test}})$.
∎

####  A.10 Will all extrapolated images make sense?

Here is a minimal example where the assumption
$\textnormal{CPE}_{\mathcal{B}}({\mathcal{Z}}^{\textnormal{train}})\not\subseteq{\mathcal{Z}}^{\textnormal{test}}$
is violated.

######  Example 8 (Violation of
$\textnormal{CPE}_{\mathcal{B}}({\mathcal{Z}}^{\textnormal{train}})\not\subseteq{\mathcal{Z}}^{\textnormal{test}}$).

Imagine ${\bm{z}}=({\bm{z}}_{1},{\bm{z}}_{2})$ where ${\bm{z}}_{1}$ and
${\bm{z}}_{2}$ are the $x$-positions of two distinct balls. It does not make
sense to have two balls occupying the same location in space and thus whenever
${\bm{z}}_{1}={\bm{z}}_{2}$ we have
$({\bm{z}}_{1},{\bm{z}}_{2})\not\in{\mathcal{Z}}^{\textnormal{test}}$. But if
$(1,2)$ and $(2,1)$ are both in ${\mathcal{Z}}^{\textnormal{train}}$, it
implies that $(1,1)$ and $(2,2)$ are in
$\textnormal{CPE}({\mathcal{Z}}^{\textnormal{train}})$, which is a violation
of
$\textnormal{CPE}_{\mathcal{B}}({\mathcal{Z}}^{\textnormal{train}})\subseteq{\mathcal{Z}}^{\textnormal{test}}$.

####  A.11 Additive decoders cannot model occlusion

We now explain why additive decoders cannot model occlusion. Occlusion occurs
when an object is partially hidden behind another one. Intuitively, the issue
is the following: Consider two images consisting of two objects, A and B (each
image shows both objects). In both images, the position of object A is the
same and in exactly one of the images, object B partially occludes object A.
Since the position of object $A$ did not change, its corresponding latent
block ${\bm{z}}_{A}$ is also unchanged between both images. However, the
pixels occupied by object A do change between both images because of
occlusion. The issue is that, because of additivity, ${\bm{z}}_{A}$ and
${\bm{z}}_{B}$ cannot interact to make some pixels that belonged to object A
“disappear” to be replaced by pixels of object B. In practice, object-centric
representation learning methods rely a masking mechanism which allows
interactions between ${\bm{z}}_{A}$ and ${\bm{z}}_{B}$ (See Equation 1 in
Section 2). This highlights the importance of studying this class of decoders
in future work.

###  Appendix B Experiments

####  B.1 Training Details

###### Loss Function.

We use the standard reconstruction objective of mean squared error loss
between the ground truth data and the reconstructed/generated data.

###### Hyperparameters.

For both the ScalarLatents and the BlockLatents dataset, we used the Adam
optimizer with the hyperparameters defined below. We also use early stopping
with patience 1000, i.e, the training stops if the reconstruction loss on the
validation dataset does not improve consecutively for 1000 epochs. Note that
we maintain consistent hyperparameters across both the Additive decoder and
the Non-Additive decoder method.

  * •

Batch Size: $64$

  * •

Learning Rate: $5\times 10^{-4}$

  * •

Weight Decay: $5\times 10^{-4}$

  * •

Total Epochs: $5000$

###### Model Architecture.

We use the following architectures for Encoder and Decoder across both the
datasets (ScalarLatents, BlockLatents). Note that for the ScalarLatents
dataset we train with latent dimension $d_{z}=2$, and for the BlockLatents
dataset we train with latent dimension $d_{z}=4$, which corresponds to the
dimensionalities of the ground-truth data generating process for both
datasets.

Encoder Architecture:

  * •

RestNet-18 Architecture till the penultimate layer ($512$ dimensional feature
output)

  * •

Stack of 6 fully-connected layer blocks, with each block consisting of Linear
Layer ( dimensions: $512\times 512$), Batch Normalization layer, and Leaky
ReLU activation (negative slope: $0.1$).

  * •

Final Linear Layer (dimension: $512\times d_{z}$) followed by Batch
Normalization Layer to output the latent representation.

Decoder Architecture (Non-additive):

  * •

Fully connected layer block with input as latent representation, consisting of
Linear Layer (dimension: $d_{z}\times 512$), Batch Normalization layer, and
Leaky ReLU activation (negative slope: $0.1$).

  * •

Stack of 6 fully-connected layer blocks, with each block consisting of Linear
Layer ( dimensions: $512\times 512$), Batch Normalization layer, and Leaky
ReLU activation (negative slope: $0.1$).

  * •

Series of DeConvolutional layers, where each DeConvolutional layer is follwed
by Leaky ReLU (negative slope: $0.01$) activation.

    * –

DeConvolution Layer ($c_{in}$: $64$, $c_{out}$: $64$, kernel: $4$; stride:
$2$; padding: $1$)

    * –

DeConvolution Layer ($c_{in}$: $64$, $c_{out}$: $32$, kernel: $4$; stride:
$2$; padding: $1$)

    * –

DeConvolution Layer ($c_{in}$: $32$, $c_{out}$: $32$, kernel: $4$; stride:
$2$; padding: $1$)

    * –

DeConvolution Layer ($c_{in}$: $32$, $c_{out}$: $3$, kernel: $4$; stride: $2$;
padding: $1$)

Decoder Architecture (Additive): Recall that an additive decoder has the form
${\bm{f}}({\bm{z}})=\sum_{B\in{\mathcal{B}}}{\bm{f}}^{(B)}({\bm{z}}_{B})$.
Each ${\bm{f}}^{(B)}$ has the same architecture as the one presented above for
the non-additive case, but the input has dimensionality $|B|$ (which is 1 or
2, depending on the dataset). Note that we do not share parameters among the
functions ${\bm{f}}^{(B)}$.

####  B.2 Datasets Details

We use the moving balls environment from Ahuja et al. [2] with images of
dimension $64\times 64\times 3$, with latent vector (${\bm{z}}$) representing
the position coordinates of each balls. We consider only two balls, hence,
${\bm{z}}\in{\mathbb{R}}^{4}$ with the partition
${\mathcal{B}}=\\{\\{1,2\\},\\{3,4\\}\\}$ where $({\bm{z}}_{1},{\bm{z}}_{2})$
and $({\bm{z}}_{3},{\bm{z}}_{4})$ correspond to the first and second ball,
respectively. The rendered images have pixels in the range [0, 255], which we
normalize with the mean and standard deviation per channel of the ImageNet
dataset.

###### ScalarLatents Dataset.

We fix the x-coordinate of each ball with separation between them along the
x-axis, i.e., ${\bm{z}}_{1}=0.25$ and ${\bm{z}}_{3}=0.75$. We sample the
y-coordinate of the first ball from a continuous uniform distribution as
follows: ${\bm{z}}_{2}\sim$ Uniform(0, 1). Then we sample the y-coordinate of
the second ball as per the following scheme:

${\bm{z}}_{4}\sim\begin{cases}\text{Uniform}(0,1)&\text{if}\;{\bm{z}}_{2}\leq
0.5\\\ \text{Uniform}(0,0.5)&\text{else}\end{cases}$

We can ignore the x-coordinate of each ball (${\bm{z}}_{1},{\bm{z}}_{3}$) as
they are fixed and considering only the y-coordinate of each ball
(${\bm{z}}_{2},{\bm{z}}_{4}$) as the effective latent variables. Hence, this
leads to the L-shaped latent support, i.e.,
${\mathcal{Z}}^{\textnormal{train}}:=[0,1]\times[0,1]\setminus[0.5,1]\times[0.5,1]$.

We use $50k$ samples for the test dataset, while we use $10k$ samples for the
train dataset along with $2.5k$ samples ($25\%$ of the train sample size) for
the validation dataset.

###### BlockLatents Dataset.

For this dataset, we allow the balls to move in both the x, y directions, but
we rejected the images that present occlusion, i.e. when one ball hides
another one. For the case of independent latents, we sample each latent
component independently and identically distributed according to a uniform
distribution over $(0,1)$, i.e. $z_{i}\sim$ Uniform(0, 1).222Note that, in the
independent latents case, the latents are not actually independent because of
the rejection step which prevents occlusion from happening.

For the case of dependent latents, we sample the latents corresponding to the
first ball similarly from the same continuous uniform distribution, i.e,
$z_{1},z_{2}\sim$ Uniform (0, 1). However, the latents of the second ball are
a function of the latents of the first ball, as described in what follows:

${\bm{z}}_{3}\sim\begin{cases}\text{Uniform}(0,0.5)&\text{if}\;1.25\times({\bm{z}}_{1}^{2}+{\bm{z}}_{2}^{2})\geq
1.0\\\
\text{Uniform}(0.5,1)&\text{if}\;1.25\times({\bm{z}}_{1}^{2}+{\bm{z}}_{2}^{2})<1.0\end{cases}$

${\bm{z}}_{4}\sim\begin{cases}\text{Uniform}(0.5,1)&\text{if}\;1.25\times({\bm{z}}_{1}^{2}+{\bm{z}}_{2}^{2})\geq
1.0\\\
\text{Uniform}(0,0.5)&\text{if}\;1.25\times({\bm{z}}_{1}^{2}+{\bm{z}}_{2}^{2})<1.0\end{cases}$

Intuitively, this means the second ball will be placed in either the top-left
or the bottom-right quadrant based on the position of the first ball.

Finally, as mentioned above, for both the independent and dependent latents
case, we perform rejection sampling to remove data points where the two balls
collide with each other which leads to occlusion. This is performed as a
simple comparison among the distance between the center of the balls and the
diameter of the balls.

Note that our dependent BlockLatent setup is same as the non-linear SCM case
from Ahuja et al. [3].

We use $50k$ samples for both the train and the test dataset, along with
$12.5k$ samples ($25\%$ of the train sample size) for the validation dataset.

###### Disconnected Support Dataset.

For this dataset, we have similar setup as the ScalarLatents dataset; we fix
the x-coordinates of both the balls (${\bm{z}}_{1}=0.25$, ${\bm{z}}_{3}=0.75$)
and only vary the y-coordinates (${\bm{z}}_{2},{\bm{z}}_{4}$) of each ball. We
sample the y-coordinate of the first ball (${\bm{z}}_{2}$) from a continuous
uniform distribution as follows: ${\bm{z}}_{2}\sim$ Uniform(0, 1). Then we
sample the y-coordinate of the second ball (${\bm{z}}_{4}$) from either of the
following continuous uniform distribution with equal probability; Uniform(0,
0.25) and Uniform(0.75, 1). The sampling of ${\bm{z}}_{4}$ from distributions
with no support overlap leads to disconnected regions in the latent support,
i.e.,
${\mathcal{Z}}^{\textnormal{train}}:=[0,1]\times[0,1]\setminus[0.25,0.75]\times[0.25,0.75]$.

We use $50k$ samples for the test dataset, while we use $10k$ samples for the
train dataset along with $2.5k$ samples ($25\%$ of the train sample size) for
the validation dataset.

####  B.3 Evaluation Metrics

Recall that, to evaluate disentanglement, we compute a matrix of scores
$(s_{B,B^{\prime}})\in{\mathbb{R}}^{\ell\times\ell}$ where $\ell$ is the
number of blocks in ${\mathcal{B}}$ and $s_{B,B^{\prime}}$ is a score
measuring how well we can predict the ground-truth block ${\bm{z}}_{B}$ from
the learned latent block
$\hat{\bm{z}}_{B^{\prime}}=\hat{\bm{g}}_{B^{\prime}}({\bm{x}})$ outputted by
the encoder. The final Latent Matching Score (LMS) is computed as
$\textnormal{LMS}=\operatorname*{arg\,max}_{\pi\in\mathfrak{S}_{\mathcal{B}}}\frac{1}{\ell}\sum_{B\in{\mathcal{B}}}s_{B,\pi(B)}$,
where $\mathfrak{S}_{\mathcal{B}}$ is the set of permutations respecting
${\mathcal{B}}$ (Definition 2). These scores are always computed on the test
set.

###### Metric $\text{LMS}_{\text{Spear}}$:

As mentioned in the main paper, this metric is used for the ScalarLatents
dataset where each block is 1-dimensional. Hence, this metric is almost the
same as the mean correlation coefficient (MCC), which is widely used in the
nonlinear ICA literature [21, 22, 23, 25, 30], with the only difference that
we use Spearman correlation instead of Pearson correlation as a score
$s_{B,B^{\prime}}$. The Spearman correlation can capture nonlinear monotonous
relations, unlike Pearson which can only capture linear dependencies. We favor
Spearman over Pearson because our identifiability result (Theorem 2)
guarantees we can recover the latents only up to permutation and element-wise
invertible transformations, which can be nonlinear.