Title: THE ROLE OF MINIMAL COMPLEXITY FUNCTIONS IN UNSUPERVISED LEARNING OF SEMANTIC MAPPINGS

Abstract: We discuss the feasibility of the following learning problem: given unmatched samples from two domains and nothing else, learn a mapping between the two, which preserves semantics. Due to the lack of paired samples and without any definition of the semantic information, the problem might seem ill-posed. Specifically, in typical cases, it seems possible to build infinitely many alternative mappings from every target mapping. This apparent ambiguity stands in sharp contrast to the recent empirical success in solving this problem. We identify the abstract notion of aligning two domains in a semantic way with concrete terms of minimal relative complexity. A theoretical framework for measuring the complexity of compositions of functions is developed in order to show that it is reasonable to expect the minimal complexity mapping to be unique. The measured complexity used is directly related to the depth of the neural networks being learned and a semantically aligned mapping could then be captured simply by learning using architectures that are not much bigger than the minimal architecture. Various predictions are made based on the hypothesis that semantic alignment can be captured by the minimal mapping. These are verified extensively. In addition, a new mapping algorithm is proposed and shown to lead to better mapping results.

1. INTRODUCTION:

Multiple recent reports (Xia et al., 2016; Kim et al., 2017; Zhu et al., 2017; Yi et al., 2017 ) convincingly demonstrated that one can learn to map between two domains that are each specified merely by a set of unlabeled examples. For example, given a set of unlabeled images of horses, and a set of unlabeled images of zebras, CycleGAN (Zhu et al., 2017) creates the analog zebra image for a new image of a horse and vice versa.

These recent methods employ two types of constraints. First, when mapping from one domain to another, the output has to be indistinguishable from the samples of the new domain. This is enforced using GANs (Goodfellow et al., 2014) and is applied at the distribution level: the mapping of horse images to the zebra domain should create images that are indistinguishable from the training images of zebras and vice versa. The second type of constraint enforces that for every single sample, transforming it to the other domain and back (by a composition of the mappings in the two directions) results in the original sample. This is enforced for each training sample from either domain: every training image of a horse (zebra), which is mapped to a zebra (horse) image and then back to the source domain, should be as similar as possible to the original input image.

In another example, taken from DiscoGAN (Kim et al., 2017) , a function is learned to map a handbag to a shoe of a similar style. One may wonder why striped bags are not mapped, for example, to shoes with a checkerboard pattern. If every striped pattern in either domain is mapped to a checkerboard pattern in the other and vice-versa, then both the distribution constraints and the circularity constraints might hold. The former could hold since both striped and checkerboard patterned objects would be generated. Circularity could hold since, for example, a striped object would be mapped to a checkerboard object in the other domain and then back to the original striped object.

One may claim that the distribution of striped bags is similar to those of striped shoes and that the distribution of checkerboard patterns is also the same in both domains. In this case, the alignment follows from fitting the shapes of the distributions. This explanation is unlikely, since no effort is being made to create handbags and shoes that have the same distributions of these properties, as well as many other properties.

Our work is dedicated to the alternative hypothesis that the target mapping is implicitly defined by being approximated by the lowest-complexity mapping that has a low discrepancy between the mapped samples and the target distribution, i.e., the property that even a good discriminator cannot distinguish between the generated samples and the target ones. In Sec. 2 we explore the inherent ambiguity of cross domain mapping. In Sec. 3, we present the hypothesis and two verifiable predictions, as well as a new unsupervised mapping algorithm. In Sec. 4, we show that the number of minimal complexity mappings is expected to be small. Sec. 5 verifies the various predictions. Some context to our work, including classical ideas such as Occam's Razor, MDL, and Kolmogorov complexity are discussed in Sec. 6.

2. THE UNSUPERVISED ALIGNMENT PROBLEM:

The learning algorithm is provided with only two unlabeled datasets: one includes i.i.d samples from the first distribution and the second includes i.i.d samples from the other distribution (all notations are listed in Appendix B, Tab. 5).

x i ∈ X A for i = 1 . . . m where x i i.i.d ∼ D A and X A denotes the space of domain A = (X A , D A )

x j ∈ X B for j = 1 . . . n where x j i.i.d ∼ D B and X B denotes the space of domain B = (X B , D B )

(1)

To semantically tie the two distributions together, a generative view can be taken. This view is well aligned with the success of GAN-based image generation, e.g., (Radford et al., 2015) , in mapping random input vectors into realistic-looking images. Let z ∈ X be a random vector that is distributed according to the distribution D Z and which we employ to denote the semantic essence of samples in X A and X B . We denote D A = y A • D Z and D B = y B • D Z , where the functions y A : X → X A and y B : X → X B (see Fig. 1 ), and f • D denotes the distribution of f (x), where x ∼ D. Following the circularity-based methods (Xia et al., 2016; Kim et al., 2017; Zhu et al., 2017; Yi et al., 2017) , we assume that both y A and y B are invertible.

The assumption of invertibility is further justified by the recent success of supervised pre-image computation methods (Dosovitskiy & Brox, 2016) . In unsupervised learning, given training samples, one may be expected to be able to recover the underlying properties of the generated samples, even with very weak supervision (Chen et al., 2016) . However, if the target function between domains A and B is not invertible, because for each member of A there are a few possible members of B (or vice versa), we can add a stochastic component to A that is responsible for choosing which member in B to take, given a member of A. For example, if A is a space of handbag images and B is a space of shoes, such that for every handbag, there are a few analogous shoes, then a stochastic variable can be added such that given a handbag, one shoe is selected among the different analog shoes.

We denote by y AB = y B • y -1 A , the function that maps the first domain to the second domain. It is semantic in the sense that it goes through the shared semantic space X . The goal of the learner is to fit a function h ∈ H, for some hypothesis class H that is closest to y AB ,

EQUATION

where It is not clear that such fitting is possible without further information. Assume, for example, that there is a natural order on the samples in X B . A mapping that transforms an input sample x ∈ X A to the sample that is next in order to y AB (x), could be just as feasible. More generally, one can permute the samples in X A by some function Π that replaces each sample with another sample that has a similar likelihood (see Def. 1 below) and learn h that satisfies h = y AB • Π. We call this difficulty "the alignment problem" and our work is dedicated to understanding the plausibility of learning despite this problem.

R D [f 1 , f 2 ] = E x∼D (f 1 (x), f 2 (x)),

In multiple recent contributions (Xia et al., 2016; Kim et al., 2017; Zhu et al., 2017; Yi et al., 2017) circularity is employed. Circularity requires the recovery of both y AB and y BA = y A • y -1 B simultaneously. Namely, functions h and h are learned jointly by minimizing the risk:

EQUATION

where disc

C (D 1 , D 2 ) = sup c1,c2∈C |R D1 [c 1 , c 2 ] -R D2 [c 1 , c 2 ]

| denotes the discrepancy between distributions D 1 and D 2 that is implemented with a GAN (Ganin et al., 2016) .

The first term in Eq. 3 ensures that the samples generated by mapping domain A to domain B follow the distribution of samples in domain B. The second term is the analog term for the mapping in the other direction. The last two terms ensure that mapping a sample from one domain to the second and back, results in the original sample.

While the circularity constraints, expressed as the last two terms in Eq. 3, are elegant and do not require additional supervision, for every invertible permutation Π of the samples in domain B (not to be confused with a permutation of the vector elements of the representation of samples in B) we have

EQUATION

EQUATION

Therefore, every circularity preserving pair h and h gives rise to many possible solutions of the form

h = h • Π and h = Π -1 • h . If Π happens to satisfy D B (x) ≈ D B (Π(x))

, then the discrepancy terms in Eq. 3 also remain largely unchanged. Circularity by itself cannot, therefore, explain the recent success of unsupervised mapping.

3. THE SIMPLICITY HYPOTHESIS:

Despite the availability of a large number of alternative hypotheses h that satisfy the constraints of Eq. 3, the methods of Xia et al. (2016) ; Kim et al. (2017) ; Zhu et al. (2017) ; Yi et al. (2017) enjoy empirical success, Why?

Our hypothesis is that the small-discrepancy mapping of the lowest complexity approximates the alignment of the target function. We further hypothesize that when performing research in unsupervised mapping, goldilock architectures are selected. These architectures are complex enough to allow small discrepancies but not complex enough to support mappings that are not minimal in complexity.

By doing so, one of the minimal-complexity low-discrepancy mappings is learned.

Figure 2 : An illustrative example where the two domains are line segments in R 2 . There are infinitely many mappings that preserve the uniform distribution on the two segments. However, only two stand out as "semantic". These are exactly the two mappings that can be captured by a neural network with only two hidden neurons and Leaky ReLU activations, i.e., by a function h(x) = σ a (W x + b), for a weight matrix W and the bias vector b.

3.1. AN ILLUSTRATIVE EXAMPLE:

In order to illustrate our hypothesis, we present a very simple toy example, depicted in Fig. 2 . Consider the domain A of uniformly distributed points (x 1 , x 2 ) ∈ R 2 , where 0 ≤ x 1 < 1 and x 2 = 0.5. Let B be a similar domain, except x 2 = 2. We are interested in learning the mapping y 2D AB ((x 1 , 0.5) ) = (x 1 , 2) . We note that there are infinitely many mappings from domain A to B that satisfy the constraints of Eq. 3.

However, when we learn the mapping using a neural network with one hidden layer of size 2, and Leaky ReLU activations 1 (Maas et al., 2013), y 2D

AB is one of only two options. In this case h

(x) = σ a (W x + b), for W ∈ R 2×2 ,b ∈ R 2 and

where σ a is applied per coordinate. The only admissible solutions are of the form

W b = 1 -2b 1 0 4 -2b 2 or W b = -1 1 -2b 1 0 4 -2b 2 and b = (b 1 , b 2 ) ,

which are identical, for every b, to y 2D AB or to an alternative y 2D AB ((x 1 , 0.5) ) = (1x 1 , 2) . Exactly the same situation holds for any pair of line segments in R d + . Therefore, by restricting the hypothesis space of h, we eliminate all alternative solutions, except two. These two are exactly the two mappings that would commonly be considered "more semantic" than any other mapping, and can be expressed as the simplest possible mapping through a shared one dimensional space. While this is an extreme example, we believe that the principle is general since limiting the complexity of the admissible solutions eliminates the solutions that are derived from y AB by permuting the samples in the space X A , because such mixing requires added complexity.

3.2. A COMPLEXITY MEASURE FOR FUNCTIONS:

In this work, we focus on functions of the form

f := F [W n+1 , ..., W 1 ] = W n+1 • σ • ... • σ • W 2 • σ • W 1 (5)

here, W 1 , ..., W n+1 are invertible linear transformations from R M to itself. In addition, σ is a non-linear element-wise activation function. We will mainly focus on σ that is Leaky ReLU with parameter 0 < a = 1. In addition, for any function f , we define the complexity of f , denoted by C(f ) as the minimal number n such that there are invertible linear transformations W 1 , ..., W n+1 that satisfy f = F [W n+1 , ..., W 1 ].

Our function complexity framework, therefore, measures the complexity of a function as the depth of a neural network which implements it, or the shallowest network, if there are multiple such networks.

In other words, we use the number of layers of a network as a proxy for the Kolmogorov complexity of functions, using layers in lieu of the primitives of the universal Turing machines, which is natural for studying functions that can be computed by feedforward neural networks.

Note that capacity is typically controlled by means of norm regularization, which is optimized during training. Here, the architecture is bounded to a certain number of layers. This measure of complexity is intuitive and provides a clear and stable stratification of functions.

Norm capacity (for norms larger than zero) are not effective in comparing functions of different architectures. In Sec. 5, we demonstrate that the L1 and L2 norms of the desired mapping are within the range of norms that are obtained when employing bigger or smaller architectures. Other ways to define the complexity of functions, such as the VC-dimension (Vapnik & Chervonenkis, 1971b) and Rademacher complexity (Bartlett & Mendelson, 2003) , are not suitable for measuring the complexity of individual functions, since their natural application is in measuring the capacity of classes of functions.

3.3. CONSEQUENCES OF THE SIMPLICITY HYPOTHESIS:

The simplicity hypothesis leads to concrete predictions, which are verified in Sec. 5. The first one states that in contrast to the current common wisdom, one can learn a semantically aligned mapping between two spaces without any matching samples and even without circularity.

Prediction 1. When learning with a small enough network in an unsupervised way a mapping between domains that share common characteristics, the GAN constraint in the target domain is sufficient to obtain a semantically aligned mapping.

The strongest clue that helps identify the alignment of the semantic mapping from the other mappings is the suitable complexity of the network that is learned. A network with a complexity that is too low cannot replicate the target distribution, when taking inputs in the source domain (high discrepancy).

A network that has a complexity that is too high, would not learn the minimal complexity mapping, since it could be distracted by other alignment solutions.

We believe that the success of the recent methods results from selecting the architecture used in an appropriate way. For example, DiscoGAN (Kim et al., 2017) employs either eight or ten layers, depending on the dataset. We make the following prediction:

Prediction 2. When learning in an unsupervised way a mapping between domains, the complexity of the network needs to be carefully adjusted.

This prediction is also surprising, since in supervised learning, extra depth is not as detrimental, if at all. As far as we know, this is the first time that this clear distinction between supervised and unsupervised learning is made2 .

3.4. ALIGNMENT WITH NON-MINIMAL ARCHITECTURES:

If the simplicity hypothesis is correct, then in order to capture the target alignment, one would need to learn with the minimal complexity architecture that supports a small discrepancy. However, deeper architectures can lead to even smaller discrepancies and to better outcomes.

In order to enjoy both the alignment provided by our hypothesis and the improved output quality, we propose to find a function h of a non-minimal complexity k 2 that minimizes the following objective function

EQUATION

where k 1 is the minimal complexity for mapping with low discrepancy between domain A and domain B. In other words, we suggest to find a function h that is both a high complexity mapping from domain A to B and is close to a function of low complexity that has low discrepancy.

There are alternative ways to implement an algorithm that minimizes the objective function presented in Eq. 6. Assuming, based on this equation, that for h that minimizes the objective function, the corresponding g * = arg inf

g s.t C(g)=k1

R D A [h, g] has a (relatively) small discrepancy, leads to a two-step algorithm. The algorithm first finds a function g that has small complexity and small discrepancy and then finds h of a larger complexity that is close to g. This is implemented in Alg. 1. Note that in the first step, k 1 is being estimated, for example, by gradually increasing its value, until g with a discrepancy lower than a threshold 0 is found. We suggest to use a liberal threshold, since the goal of the network g is to provide alignment and not the lowest possible discrepancy. disc(g • D A , D B ).

2: Train g of complexity k 1 to minimize disc(g

• D A , D B ). 3: Train h of complexity k 2 to minimize disc(h • D A , D B ) + λR D A [h, g].

4. COUNTING MINIMAL COMPLEXITY MAPPINGS:

Recall, from Sec. 2, that disc is the discrepancy distance, which is based on the optimal discriminator. Also discussed were the functions Π, that switches between members in the domain B that have similar probabilities. These are defined using the discrepancy distance as follows (simplified version; the definitions and results of this section are stated more broadly in Appendix A): Definition 1 (Density preserving mapping). Let X = (X , D X ) be a domain. A 0 -density preserving mapping over X (or an 0 -DPM for short) is a function

Π such that disc(Π • D X , D X ) ≤ 0 (7)

We denote the set of all 0 -DPMs of complexity k by DPM 0 (X; k)

:= Π disc(Π • D X , D X ) ≤ 0 and C(Π) = k .

Below, we define a similarity relation between functions that reflects whether the two are similar. In this way, we are able to bound the number of different (non-similar) minimal complexity mappings by the number of different DPMs.

Definition 2. Let D be a distribution. We denote f

D ∼ 0 g, if C(f ) = C(g) and there are mini- mal decompositions: f = F [W n+1 , ..., W 1 ] and g = F [V n+1 , ..., V 1 ] such that: ∀i ∈ [n + 1] : disc(F [W i , ..., W 1 ] • D, F [V i , ..., V 1 ] • D) ≤ 0 .

Put differently, two functions of the same complexity have this relation, if for every step of their processing, the activations of the matching functions are similar.

The defined relation is reflexive and symmetric, but not transitive. Therefore, there are many different ways to partition the space of functions into disjoint subsets such that in each subset, any two functions have the closeness property. We count the number of functions as the minimal number of subsets required in order to cover the entire space. This quantity is denoted by N(U, ∼ U ) where U is the set and ∼ U is the closeness relation. The formal presentation is in Def. 9, which slightly generalizes the notion of covering numbers (Anthony & Bartlett, 2009) .

Informally, the following theorem states that the number of minimal low-discrepancy mappings is upper bounded by both the number of DPMs of a certain size over D A and over D B . This result is useful, since DPMs are expected to be rare in real-world domains. When imagining mapping a space to itself, in a way that preserves the distribution, one first considers symmetries. Near-perfect symmetries are rare in natural domains, and when these occur, e.g., (Kim et al., 2017) , they form wellunderstood ambiguities. Another option that can be considered is that of replacing specific samples in domain B with other samples of the same probability. However, these very local discontinuous mappings are of very high complexity, since this complexity is required for reducing the modeling error for discontinuous functions. One can also consider replacing larger sub-domains with other sub-domains such that the distribution is preserved. This could be possible, for example, if the distribution within the sub-domains is almost uniform (unlikely), or if it is estimated inaccurately due to the limitations of the training set.

We, therefore, make the following prediction. Prediction 3. The number of DPMs of low complexity is small.

Given two domains A and B, there is a certain complexity C 0 A,B , which is the minimal complexity of the networks needed in order to achieve discrepancy smaller than 0 for mapping the distribution D A to the distribution D B . The set of minimal complexity mappings, i.e., mappings of complexity C 0 A,B that achieve 0 discrepancy is denoted by

H 0 (A, B) := h C(h) ≤ C 0 A,B and disc(h • D A , D B ) ≤ 0 .

The following theorem shows that the covering number of this set is similar to the covering number of the DPMs. Therefore, if prediction 3 above holds, the number of minimal low-discrepancy mappings is small. Theorem 1 (Informal). Let σ be a Leaky ReLU with parameter 0 < a = 1 and assume identifiability. Let 0 , 1 and 2 < 1 be three positive constants and A = (X A , D A ) and B = (X B , D B ) are two domains. Then,

EQUATION

Proof. See Appendix D.

The theorem assumes identifiability. In the context of neural networks, the general question of uniqueness up to invariants, also known as identifiability, is an open question. Several authors have made progress in this area for different neural network architectures. The most notable work has been done by Fefferman & Markel (1993) that proves identifiability for σ = tanh. Furthermore, the representation is unique up to some invariants. Other works (Williamson & Helmke, 1995; F. Albertini & Maillot, 1993; Kurková & Kainen, 2014; Sussmann, 1992) prove such uniqueness for neural networks with only one hidden layer and various activation functions. Similarly, in Lem. 3 in the Appendix, we show that identifiability holds for Leaky ReLU networks with one hidden layer.

5. EXPERIMENTS:

The first group of experiments is dedicated to test the validity of the three predictions made, in order to give further support to the simplicity hypothesis. Next, we evaluate the success of the proposed algorithm in comparison to the DiscoGAN method of Kim et al. (2017) .

We chose to experiment with the DiscoGAN architecture since it focuses on semantic tasks that contain a lesser component of texture or style transfer. The CycleGAN architecture of Zhu et al. (2017) inherits much from the style transfer architecture of Pix2Pix Isola et al. (2017) , and the discrepancy term is based on a patch-based analysis, which introduces local constraints that could mask the added freedom introduced by adding layers. In addition, the U-net architecture of Ronneberger et al. (2015) used by Isola et al. (2017) deviates from the connectivity pattern of our model.

Experiments in this architecture and with the architecture of DualGAN (Yi et al., 2017) , which focuses on tasks similar to CycleGAN, and shares many of the architectural choices, including U-nets and the use of patches, are left for future work.

5.1. EMPIRICAL VALIDATION OF THE PREDICTIONS:

Prediction 1 states that since the unsupervised mapping methods are aimed at learning minimal complexity low discrepancy functions, GANs are sufficient. In the literature (Zhu et al., 2017; Kim et al., 2017) , learning a mapping h : X A → X B , based only on the GAN constraint on B, is presented as a failing baseline. In (Yi et al., 2017) , among many non-semantic mappings obtained by the GAN baseline, one can find images of GANs that are successful. However, this goes unnoticed.

In order to validate the prediction that a purely GAN based solution is viable, we conducted a series of experiments using the DiscoGAN architecture and GAN loss only. We consider image domains A and B, where

X A = X B = R 3×64×64 .

In DiscoGAN, the generator is built of: (i) an encoder consisting of convolutional layers with 4 × 4 filters followed by Leaky ReLU activation units and (ii) a decoder consisting of deconvolutional layers with 4 × 4 filters followed by a ReLU activation units. Sigmoid is used for the output layer.

Between four to five convolutional/deconvolutional layers are used, depending on the domains used in A and B (we match the published code architecture per dataset). The discriminator is similar to the encoder, but has an additional convolutional layer as the first layer and a sigmoid output unit.

The first set of experiments considers the CelebA face dataset. Transformations are learned between the subset of images labeled as male and those labeled as female, as well as from blond to black hair and eyeglasses to no eyeglasses. The results are shown in Fig. 3 , 4, and 5, (resp.). It is evident that the output image is highly related to the input images.

In the case of mapping handbags to shoes, as seen in Fig. 6 , the GAN does not provide a meaningful solution. However, in the case of edges to shoes and vice versa (Fig. 7 ), the GAN solution is successful.

In Prediction 2, we predict that the selection of the right number of layers is crucial in unsupervised learning. Using fewer layers than needed, will not support the modeling of the target alignment between the domains. In contrast, adding superfluous layers would mean that more and more alternative mappings obscure the target transformation.

In (Kim et al., 2017) , 8 or 10 layers are employed (counting both convolution and deconvolution) depending on the experiment. In our experiment, we vary the number of layers and inspect the influence on the results. The experiments are also repeated for the Wasserstein GAN loss (using the same architecture) in Appendix E.

These experiments were done on the CelebA gender conversion task, where 8 layers are employed in the experiments of (Kim et al., 2017) . Using the public implementation and adding and removing layers, we obtain the results in Fig. 8 -13. Note that since the encoder and the decoder parts of the learned network are symmetrical, the number of layers is always even. As can be seen, changing the number of layers has a dramatic effect on the results. The best results are obtained at 6 or 8 layers with 6 having the best alignment and 8 having better discrepancy. The results degrade quickly, as one deviates from the optimal value. Using fewer layers, the GAN fails to produce images of the desired class. Adding layers, the semantic alignment is lost, just as expected.

Note that Kim et al. (2017) have preferred low discrepancy over alignment in their choice. In other words, the selected architecture of size k = 8 presents acceptable images at the price of lower alignment compared to an architecture of size k -2. This is probably a result of ambiguity that is already present at the size k architecture. On the other hand, the smaller architecture of size k -2 does not produce images of extremely low discrepancy, and there is no architecture that benefits both, an extremely low discrepancy and high alignment. This is observed for example in Fig. 8 where females are translated to males. For 4 layers the discrepancy is too low and the mapping fails to produce images of males. For 6 layers, the discrepancy is relatively low and the alignment is at its highest. For 8 layers, the discrepancy is at its lowest value, nevertheless, the alignment is worse.

While our discrete notion of complexity seems to be highly related to the quality of the results, the norm of the weights do not seem to point to a clear architecture, as shown in Tab. 2(a). Since the table compares the norms of architectures of different sizes, we also approximated the functions using networks of a fixed depth k = 18 and then measured the norm. These results are presented in Tab. 2(b). In both cases, the optimal depth, which is 6 or 8, does not appear to have a be an optimum in any of the measurements.

Prediction 3 states that there are only a handful of DPMs, except for the identity function. In order to verify it, we trained a DiscoGAN from a distribution A to itself with an added loss of the form -x∈A |xh(x)|. In our experiment, testing network complexities from 2 to 12, we could not find a DPM, see Fig. 16 and Tab. 3. For lower complexities, the identity was learned despite the added loss. For higher complexities, the network learned the identity while changing the background color.

For even higher complexities, other mapping emerged. However, these mappings did not satisfy the circularity constraint, and are unlikely to be DPMs.

5.2. RESULTS FOR ALG. 1:

The goal of Alg. 1 is to find a well-aligned solution with higher complexity than the minimal solution and potentially smaller discrepancy. It has two stages. In the first one, k 1 , which is the minimal complexity that leads to a low discrepancy, is identified. This follows a set of experiments that are similar to the one that is captured, for example, by Fig. 2 . To demonstrate robustness, we select a single value of k 1 across all experiments. Specifically, we use k 1 = 6, which, as discussed above, typically leads to a low (but not very low) discrepancy, while the alignment is still unambiguous.

Once g is trained, we proceed to the next step of optimizing a second network of complexity k 2 . Note that while the first function (g) uses the complete DiscoGAN architecture, the second network (h) only employs a one-directional mapping, since alignment is obtained by g. Figs. 21-29 depict the obtained results, for a varying number of layers. First, the result obtained by the DiscoGAN method with k 1 is displayed. The results of applying Alg. 1 are then displayed for a varying k 2 .

As can be seen, our algorithm leads to more sophisticated mappings. Kim et al. (2017) have noted that their solutions are, at many times, related to texture or style transfer and, for example, geometric transformations are not well captured. The new method is able to better capture such complex transformations. Consider the case of mapping male to female in Fig. 20 , first row. A man with a beard is mapped to a female image. While for g the beard is still somewhat present, it is not so for h with k 2 > k 1 . On the female to male mappings in Fig. 21 it is evident in most mappings that g produces a more blurred image, while h is more coherent for k 2 > k 1 . Another example is in the blond to black hair mapping in Fig. 22 . In the 5th row, the style transfer nature of g is evident, since it maps a red object behind the head together with the whole blond hair, producing an unrealistic black hair. h of complexity k 2 = 8 is able to separate that object from the hair, and in k 2 > 8 it produces realistic looking black hair. This kind of transformation requires more than a simple style transfer.

On the edges to shoes and edges to handbags mappings of Fig. 26 and Fig. 28 , while the general structure is clearly present, it is significantly sharpened by mapping h with k 2 > k 1 .

For the face datasets, we also employ face descriptors in order to learn whether the mapping is semantic. Namely, we can check if the identity is preserved post mapping by comparing the VGG face descriptors of Parkhi et al. (2015) . One can assume that two images that match will have many similar features and so the VGG representation will be similar. The cosine similarities are used, as is commonly done.

In addition, we train a linear classifier in the space of the VGG face descriptors in order to distinguish between Male/Female, Eyeglasses/No-eyeglasses, and Blond/Black. This way, we can check, beyond discrepancy, that the mapping indeed transforms between the domains. The training samples in domains A and B are used to train this classifier, which is then applied to a set of test images before and after mapping, measuring the accuracy. The higher the accuracy, the better the separation.

Tab. 4 presents the results for both the k 1 layers network g, alternative networks g of higher complexity (shown as baseline only), and the network h trained using Alg. 1. We expect the alignment of g to be best at complexity k 1 , and worse due to the loss of discrepancy for alternative network g with complexity k > k 1 . We expect this loss of alignment to be resolved for networks h trained with Alg. 1.

In the experiments of black to blond hair and blond to black hair mappings, we note that h with k 2 = 8 has the best descriptor similarity, and very good separation accuracy and discrepancy. Higher values of k 2 are best in terms of separation accuracy and discrepancy, but lose somewhat in descriptor similarity. A similar situation occurs for male to female and female to male mappings and in eyeglasses to non-eyeglasses, where k 2 = 8 results in the best similarity score and higher values of k 2 result in better separation accuracy and discrepancy.

It is interesting to note, that the distance between g and h is also minimal for k 2 = 8. Perhaps, with more effective optimization, higher complexities could also maintain similarity, while delivering lower discrepancies.

6. DISCUSSION:

Our stratified complexity model is related to structural risk minimization (SRM) by Vapnik & Chervonenkis (1971a) , which employs a hierarchy of nested subsets of hypothesis classes in order of increasing complexity. In our stratification, which is based on the number of layers, the complexity classes are not necessarily nested. A major emphasis in SRM is the dependence on the number of samples: the algorithm selects the hypothesis from one of the nested hypothesis classes depending on the amount of training data. In our case, one can expect higher values of k 2 to be beneficial as the number of training samples grows. However, the exact characterization of this relation is left for future work.

Alg. 1 can be seen as a form of distillation. The first step of the algorithm finds the minimal complexity for mapping between the two domains and obtains the first generator. Then, a second generator, with a large complexity, is trained while being encouraged to output images which are close to the output of the first generator. This resembles the distillation methods proposed by Hinton et al. (2015) and later analyzed by Hand & Voroninski (2017) .

Since the method depicted in Alg. 1 optimizes, among other things, the architecture of the network, our method is somewhat related to work that learn the network's structure during training, e.g., (Saxena & Verbeek, 2016; Wen et al., 2016; Liu et al., 2015; Feng & Darrell, 2015; Lebedev & Lempitsky, 2016) . This body of work, which deals exclusively with supervised learning, optimizes the networks loss by modifying both the parameters and the hyperparameters. For GAN based loss, this would not work, since with more capacity, one can reduce the discrepancy but quickly lose the alignment.

Indeed, we point to a key difference between supervised learning and unsupervised learning. While in the former, deeper networks, which can learn even random labels, work well (Zhang et al., 2017) , unsupervised learning requires a careful control of the network capacity. This realization, which echoes the application of MDL for model selection in unsupervised learning (Zemel, 1994) , was overshadowed by the overgeneralized belief that deeper networks lead to higher accuracy.

The limitations of unsupervised based learning that are due to symmetry, are also a part of our model. For example, the mapping of cars in one pose to cars in the mirrored pose that sometimes happens in (Kim et al., 2017) , is similar in nature to the mapping of x to 1x in the simple example given in Sec. 3.1. Such symmetries occur when we can divide y AB into two functions y AB = y 2 • y 1 such that a function W is a linear mapping and also a DPM of y 1 • D A and, therefore,

D B ≈ y 2 • W • y 1 .

While we focus on unsupervised learning, the emergence of semantics when learning with a restricted capacity is widely applicable, such as with autoencoders, transfer learning, semi-supervised learning and elsewhere. As an extreme example, Sutskever et al. (2015) present empirical evidence that a meaningful mapper can be learned, even from very few examples, if the network trained is kept small.

7. CONCLUSION:

The recent success in mapping between two domains in an unsupervised way and without any existing knowledge, other than network hyperparameters, is nothing less than extraordinary and has far reaching consequences. As far as we know, nothing in the existing machine learning or cognitive science literature suggests that this would be possible.

We provide an intuitive definition of function complexity and employ it in order to identify minimal complexity mappings, which we conjecture play a pivotal role in this success. If our hypothesis is correct, simply by training networks that are not too complex, the target mapping stands out from all other alternative mappings.

Our analysis leads directly to a new unsupervised cross domain mapping algorithm that is able to avoid the ambiguity of such mapping, yet enjoy the expressiveness of deep neural networks.

The experiments demonstrate that the analogies become richer in details and more complex, while maintaining the alignment.

We show that the number of low-discrepancy mappings that are of low-complexity is expected to be small. Our main proof is based on the assumption of identifiability, which constitutes an open question. We hope that there would be a renewed interest in this problem, which has been open for decades for networks with more than a single hidden layer and is unexplored for modern activation functions. --------Number of layers: --------Input op 4 6 8 10 12 14

h h • h h h • h h h • h h h • h h h • h h h • h

Figure 14 : Results for mapping Males to itself (B=A) using a DiscoGAN architecture and enforcing that the mapping is not the identity mapping. The odd rows present the learned mapping h, and the even rows present the full cycle h • h.

--------Number of layers: --------Input op 4 6 8 10 12 14

h h • h h h • h h h • h h h • h h h • h h h • h

Figure 15 : Results for mapping the Females to itself (B=A) using a DiscoGAN architecture and enforcing that the mapping is not the identity mapping. The odd rows present the learned mapping h, and the even rows present the full cycle h • h.

--------Number of layers: --------Input op 4 6 8 10 12 14

h h • h h h • h h h • h h h • h h h • h h h • h

Figure 16 : Results for mapping shoe edges to itself (B=A) using a DiscoGAN architecture and enforcing that the mapping is not the identity mapping. The odd rows present the learned mapping h, and the even rows present the full cycle h • h.

--------Number of layers: --------Input op 4 6 8 10 12 14

h h • h h h • h h h • h h h • h h h • h h h • h

Figure 17 : Results for mapping handbag edges to itself (B=A), using a DiscoGAN architecture and enforcing that the mapping is not the identity mapping. The odd rows present the learned mapping h, and the even rows present the full cycle h • h.

--------Number of layers: --------Input op 4 6 8 10 12 14

h h • h h h • h h h • h h h • h h h • h h h • h

Figure 18 : Results for mapping handbags to itself (B=A), using a DiscoGAN architecture and enforcing that the mapping is not the identity mapping. The odd rows present the learned mapping h, and the even rows present the full cycle h • h.

--------Number of layers: --------Input op 4 6 8 10 12 14

h h • h h h • h h h • h h h • h h h • h h h • h

Figure 19 : Results for mapping shoes to itself (B=A) using a DiscoGAN architecture and enforcing that the mapping is not the identity mapping. The odd rows present the learned mapping h, and the even rows present the full cycle h • h. A A GENERALIZED AND FORMAL STATEMENT OF THE RESULTS

For brevity, we have not presented our results in the most general way. For example, in Def. 1, we did not bound the complexity of the discriminators. For the same reason, some of our terms were described and not yet formally defined.

A.1 A COMPLEXITY MEASURE FOR FUNCTIONS:

In order to model the composition of neural networks, we define a complexity measurement that assigns a value based on the number of simple functions that make up a complex function. 

• N = ∞ n=0 C n (where, C n = {p n • ... • p 1 |p 1 , ..., p n ∈ C} and C 0 = {Id}). • Every function in C is invertible.

A SCM partitions a set of invertible functions into disjoint complexity classes,

C0 := p ∈ N ∀ n ∈ N, q ∈ C n : p • q, q • p, p -1 • q, q • p -1 ∈ C n Cn := C n \ n-1 i=0 C i ∪ C0 (9)

When considering simple functions p i that are layers in a neural network, each complexity class contains the functions that are implemented by networks of n hidden layers. In addition, we denote the complexity of a function p:

EQUATION

If the complexity of a function p equals n, then any appropriate decomposition p = p n • ... • p 1 will be called a minimal decomposition of p. According to this measurement, the complexity of a function p is determined by the minimal number of primitive functions required in order to represent it.

In this work, we focus our attention on SCMs that represent the architectures of fully connected neural networks with layers of a fixed size, i.e., Definition 4 (NN-SCM). A NN-SCM is a SCM N = SCM[C] that satisfies the following conditions:

• C = W 2 • σ • W 1 W 1 , W 2 ∈ R M ×M and W 1 , W 2 are invertible . Here, W 1 , W 2 denote

both linear transformations and the associated matrix forms.

• σ is a non-linear element-wise activation function.

For brevity, we denote N := SCM[σ] to refer to a NN-SCM with the activation function σ.

The NN-SCM with the Leaky ReLU activation function is of a particular interest, since (Kim et al., 2017; Zhu et al., 2017) employ it as the main activation function (plain ReLUs and tanh are also used). In the NN-SCM framework, to specify the function obtained by a decomposition

W n • σ • W n-1 • σ • ... • σ • W 1 we simply write: F [W n , ..., W 1 ] := W n • σ • W n-1 • σ • ... • σ • W 1 (11)

It is useful to characterize the effect of inversion on the complexity of functions, since, for example, we consider both h = Π • h and h = Π -1 • h . The following lemma states that, in the case of NN-SCM with σ that is the Leaky ReLU, the complexity of the inverse function is the same as that of the original function.

Lemma 1. Let N = SCM[σ] be a NN-SCM with σ that is the Leaky ReLU with parameter 0 < a = 1.

Then, for any u ∈ N , C(u -1 ) = C(u).

Proof. First, we denote C (p) the minimal number n such that there are invertible linear mappings W 1 , ..., W n+1 such that p = F [W n+1 , ..., W 1 ] (if p = Id then C (p) = 0). This complexity measure is similar to the complexity measure C. For a function p such that C(p) = 0, we have, C(p) = C (p). Nevertheless, for p such that C(p) = 0, it is not necessarily true that C (p) = 0. For example, if p = Id is an invertible linear mapping, we have,

C(p) = 0 and C (p) = 2. Let p = F [W 2 , W 1 ] = W 2 • σ • W 1 be any function such that C(p) = 1.

We consider that:

EQUATION

In particular,

C (p -1 ) ≤ 1. If C (p -1 ) = 0, then, Id = -W -1 1 • σ • -W -1

2 /a and, therefore, σ is a linear mapping -in contradiction. Thus, C (p -1 ) = 1.

Next, we would like to show that for any u ∈ N ,

EQUATION

In particular,

EQUATION

Therefore, by Lem. 7, 

C (u -1 ) ≤ C (F [Id, W 1 ] -1 ) + ... + C (F [Id, W n-1 ] -1 ) + C (F [W n+1 , W n ] -1 ) = n (17) On the other hand, if v = u -1 , n = C (u) = C (v -1 ) ≤ C (v) = C (u -1 ) ≤ n and C (u -1 ) = C (u).

A.2 MINIMAL COMPLEXITY MAPPINGS:

Based on our simplicity hypothesis, we present a definition of a minimal complexity mapping that is both intuitive and well-defined in concrete complexity terms. Given two distributions D A and D B , a minimal complexity mapping f : X A → X B between domains A and B is a mapping that has minimal complexity among the functions h :

X A → X B that satisfy h • D A ≈ D B .

Consider, again, the example of a line segment in R M (Sec. 3.1) and the semantic space of the interval, [0, 1] ⊂ R. The two linear mappings, which map either segment ends to 0 and the other to 1 are minimal, when using f that are ReLU based neural networks. Other mappings to this segment are possible, simply by permuting points on the segment in R M . However, these alternative mappings have higher complexity, since the two mappings above are the only ones with the minimal possible complexity.

In order to measure the distance between h • D A and D B , we use the discrepancy distance, disc D .

In this work, we focus on classes of discriminators D of the form D m := {u|C(u) ≤ m} for some m ∈ N. In addition, for simplicity, we will write disc m := disc Dm .

Definition 5 (Minimal complexity mappings).

Let N = SCM[C]. Let A = (X A , D A ) and B = (X B , D B

) be two domains. We define the (m, 0 )-minimal complexity between A and B as:

EQUATION

The set of (m, 0 )-minimal complexity mappings between A and B is:

EQUATION

We note that for any fixed 0 > 0, the sequence {C 0 A,B } ∞ m=0 is monotonically increasing as m tends to infinity. In addition, we assume that for every two distributions of interest, D I and D J , and an error rate 0 > 0, there is a function of finite complexity such that disc ∞ (h • D I , D J ) ≤ 0 . Therefore, the sequence {C m, 0 A,B } ∞ m=0 is upper bounded by C(h) for all m ∈ N ∪ {0}. In particular, there is a minimal value m 0 > 0 such that C m, 0 A,B = C m0, 0 A,B for all m ≥ m 0 . We denote: E 0 A,B := m 0 and C 0 A,B := C m0, 0 A,B . For simplicity, sometimes we will assume that m = ∞. In this case, we will write H 0 (A, B) := H 0 (A, B; ∞).

A.3 IDENTIFIABILITY:

Every neural network implementation gives rise to many alternative implementations by performing simple operations, such as permuting the units of any hidden layer, and then permuting back as part of the linear mapping in the next layer. Therefore, it is first required to identify and address the set of transformations that could be inconsequential to the function which the network computes.

Definition 6 (Invariant set). Let N = SCM[σ] be a NN-SCM. The invariant set Invariant(N ) is the set of all τ : R M → R M that satisfy the following conditions:

• τ : R M → R M is an invertible linear transformation. • σ • τ = τ • σ.

Functions in Invariant(N ) are called invariants or invariant functions.

For example, for neural networks with the tanh activation function, the set of invariant functions contains the linear transformations that take vectors, permute them and multiply each coordinate by ±1. Formally, each τ = [ 1 • e π(1) , ..., M • e π(M ) ] where e i is the i'th standard basis vector, π is a permutation over [M ] and i ∈ {±1} (Fefferman & Markel, 1993) .

In the following lemma, we characterize the set of all invariant functions for σ that is Leaky ReLU with parameter 0 < a = 1.

Lemma 2. Let N = SCM[σ] with σ be Leaky ReLU with parameter 0 < a = 1. Then,

EQUATION

Here, e i denotes the i'th standard basis vector in R M and Sym M is the set of permutations of [M ].

Proof. Let τ be an invertible linear mapping satisfying σ • τ = τ • σ. We consider that for all i ∈ [M ] and vector x; σ( τ i , x ) = τ i , σ(x) , where τ i is the i'th row of τ and τ i,j is the (i, j) entry of τ . For x = e j , we have:

EQUATION

For x = -e j , we have:

EQUATION

If τ i,j < 0, then the first equation leads to contradiction. Otherwise, the equations are both satisfied.

Finally, for x = e je k , we have:

EQUATION

If τ i,j -τ i,k = 0, then, τ i,j -aτ i,k = 0 and since a = 1, 0, we have,

τ i,j = τ i,k = 0. If τ i,j -τ i,k ≥ 0, then, τ i,j -τ i,k = τ i,j -aτ i,k that gives τ i,k = 0. If τ i,j -τ i,k ≤ 0, then, a(τ i,j -τ i,k ) = τ i,j -aτ i,k

that yields τ i,j = 0. Therefore, for each i ∈ [M ] there is at most one entry τ i,j that is not 0. If for all j ∈ [M ], τ i,j = 0, then the mapping τ is not invertible, in contradiction. Therefore, for each i ∈ [M ] there is exactly one entry τ i,j > 0 (it is non-negative as shown above). Finally, if there are i 1 = i 2 such that τ i1,j , τ i2,j = 0 then the matrix is invertible. Therefore, τ is a member of the set defined in Eq. 20. In addition, it is easy to see that every member of the noted set satisfies the conditions of the invariant set. Thus, we obtain the desired equation.

Our analysis is made much simpler, if every function has invariant representation up to a sequence of manipulations using invariant functions that do not change the essence of the processing at each layer.

Assumption 1 (Identifiability). Let N = SCM[σ] with σ that is Leaky ReLU with 0 < a = 1. Then, every function p ∈ N is identifiable (with respect to Invariant(N )), i.e., for any two minimal decompositions,

p = F [W n+1 , ..., W 1 ] = F [V n+1 , ..., V 1 ],

there are invariants τ 1 , ..., τ n ∈ Invariant(N ) such that:

EQUATION

Uniqueness up to invariants, also known as identifiability, forms an open question. Fefferman & Markel (1993) proved identifiability for the tanh activation function. Other works (Williamson & Helmke, 1995; F. Albertini & Maillot, 1993; Kurková & Kainen, 2014; Sussmann, 1992) prove such uniqueness for neural networks with only one hidden layer and various classical activation functions.

In the following lemma, we show that identifiability holds for Leaky ReLU networks with only one hidden layer.

Lemma 3. Let N = SCM[σ] with σ that is Leaky ReLU with parameter 0 < a = 1. Any function p such that C(p) = 1 is identifiable, i.e, if p = F [W 2 , W 1 ] = F [V 2 , V 1 ], then, W 1 = τ • V 1 and W 2 = V 2 • τ -1 for some τ ∈ Invariant(N ).

Proof. An alternative representation of the equation is:

EQUATION

We would like to prove that if σ

EQUATION

In particular, if v i is the i'th row of V (similarly u i ) and x = e j :

EQUATION

where v i,j is the (i, j) entry of V (similarly u i,j ). Similarly, for x = -e j :

EQUATION

If u i,j is negative, we obtain: au i,j = v i,j (the first equation) and -u i,j = -av i,j (the second equation) that yields a = 1 in contradiction. Therefore, u i,j ≥ 0 and u i,j = v i,j (the second equation).

We conclude that

W 1 • V -1 1 = W -1 2 • V 2 := τ . Finally, since (σ • W 1 • V -1 1 ) = (W -1 2 • V 2 • σ) we have σ • τ = τ • σ and τ is invertible linear mapping. Differently said, W 1 = τ • V 1 and W 2 = V 2 • τ -1 such that τ ∈ Invariant(N ).

As far as we know, there are no other results continuing the identifiability line of work for activation functions such as Leaky ReLU. Uniqueness, which is stronger than identifiability, since it means that even multiple representations with different number of layers do not exist, does not hold for these activation functions. To see this, note that for every M × M invertible linear mapping W , the following holds:

EQUATION

)

where σ is the Leaky ReLU activation function with parameter a. We conjecture that for networks with Leaky ReLU activations identifiability holds, or at least for networks with a fixed number of neurons per layer. In addition to identifiability, we make the following assumption, which states that almost all mappings are non-degenerate.

Assumption 2. Let N = SCM[σ] with σ that is Leaky ReLU with parameter 0 < a = 1. Assume that the set of (W 1 , ..

., W n+1 ) ∈ R M ×M ×m such that C(F [W n+1 , ..., W 1 ]) = n is dense in R M ×M ×m .

In the unsupervised alignment problem, the algorithms provided with only two unmatched datasets of samples from the domains A and B and the task is to learn a well-aligned function between them. Since we hypothesize that the alignment of the target mapping is typically captured by the lowest complexity low-discrepancy we develop the machinery needed in order to show that such mappings are rare.

Recall that disc m is the discrepancy distance for discriminators of complexity up to m. In Sec. 2, we have discussed the functions Π which replaces between members the domain B that have similar probabilities. Formally, these are defined using the discrepancy distance.

Definition 7 (Density preserving mapping). Let N = SCM[C] and X = (X , D X ) a domain. A (m, 0 )-density preserving mapping over X (or an (m, 0 )-DPM for short) is a function Π such that

disc m (Π • D X , D X ) ≤ 0 (30)

We denote the set of all (m, 0 )-DPMs of complexity k by DPM 0 (X; m, k)

:= Π disc m (Π • D X , D X ) ≤ 0 and C(Π) = k .

We would like to bound the number of mappings that are both low-discrepancy and low-complexity by the number of DPMs. We consider that there are infinitely many DPMs. For example, if we perturb the weights of a minimal representation of a DPM, Π, we obtain a new DPM. Therefore, we define a similarity relation between functions that reflects whether the two are similar. In this way, we are able to bound the number of different (non-similar) minimal-complexity mappings by the number of different DPMs.

Definition 8 (Closeness between pairs of distributions or functions).

Let N = SCM[σ]. • We denote D 1 ∼ m, 0 D 2 ⇐⇒ disc m (D 1 , D 2 ) ≤ 0 . • We denote f D ∼ m, 0 g, if C(f ) = C(g) =:

n and there are minimal decompositions:

f = F [W n+1 , ..., W 1 ] and g = F [V n+1 , ..., V 1 ] such that ∀i ∈ [n + 1] : F [W i , ..., W 1 ] • D ∼ m, 0 F [V i , ..., V 1 ] • D.

The defined relation is reflexive and symmetric, but not transitive. Therefore, there are many different ways to partition the space of functions into disjoint subsets such that in each subset, any two functions are similar. We count the number of functions up to the similarity as the minimal number of subsets required in order to cover the entire space. This idea is presented in Def. 9, which slightly generalizes the notion of covering numbers (Anthony & Bartlett, 2009) .

Definition 9 (Covering number). Let (U, ∼ U ) be a set and a reflexive and symmetric relation. A covering of (U, ∼ U ), is a tuple (U, ≡ U ) such that: ≡ U is an equivalence relation and

u 1 ≡ U u 2 =⇒ u 1 ∼ U u 2 .

The covering number of (U, ∼ U ), denoted by N(U, ∼ U ), is:

EQUATION

Here, U/ ≡ U is the quotient set of U by ≡ U .

Thm. 1 below states that the number of low discrepancy mappings of complexity C 0 A,B is upper bounded by the number of DPMs of size 2C 0 A,B . By prediction 3, the number of such DPMs is small. The theorem employs the following weak assumption. In Lem. 19, we prove that this assumption holds for the case of a continuous risk if the discriminators have bounded weights. Theorem 1. Let N = SCM[σ] σ that is ReLU with parameter 0 < a = 1. Assume Assumptions 1, 2 and 3. Let 0 , 1 and 2 be three constants such that 0 < 1 /4 and 2 < 1 -4 0 be three positive constants and A = (X A , D A ) and B (X B , D B ) are two domains. Then, N H 0 (A, B),

EQUATION

Proof. See Sec. D.

B SUMMARY OF NOTATION:

Tab. 5 lists the symbols used in our work. Functions from the space to the domains, y A : X → X A and y

B : X → X B D Z A distribution over a feature space X y AB , y BA y AB = y B • y -1 A and y BA = y A • y -1 B Loss function : R × R → R R D [f 1 , f 2 ] The risk function R D [f 1 , f 2 ] = E x∼D (f 1 (x), f 2 (x))

where is a loss function and

D is a distribution disc D (D 1 , D 2 )

The discrepancy between two distributions D 1 and D

2 , i.e, disc D (D 1 , D 2 ) = sup c1,c2∈D |R D1 [c 1 , c 2 ] -R D2 [c 1 , c 2 ]| σ A non-linear element-wise activation function C A class of functions; in most cases C = {W 2 • σ • W 1 | W 1 , W 2 ∈ R M ×M are invertible linear transformation} F [W n , ..., W 1 ] F [W n , ..., W 1 ] = W n • σ • W n • σ • ... • σ • W 2 • σ • W 1 N = SCM[C]

A SCM specified by a class of functions C (see Def. 3)

N = SCM[σ]

A NN-SCM specified by the activation function σ (see Def. 4)

C(p)

The complexity of a function p (see Eqs. 9, 10) Invariant(N )

The invariant set of N (see Def. The (m, 0 )-minimal complexity between A and B (see Def. 5)

C 0 A,B , E 0 A,B C 0 A,B = max m≥1 C m, 0 A,B and E 0 A,B = arg min m [C m, 0 A,B = C 0 A,B ] H 0 (A, B; m)

The set of ( 0 , m)-minimal complexity mappings between A and B (see

Def. 5) H 0 (A, B) H 0 (A, B) = H 0 (A, B; ∞) S 1 • S 2 A composition of sets, S 1 • S 2 = {s 1 • s 2 |s 1 ∈ S 1 and s 2 ∈ S 2 } D 1 ∼ m, D 2 , D 1 ∼ D 2 disc m (D 1 , D 2 ) ≤ and disc(D 1 , D 2 ) ≤ (see Def. 8) f D ∼ m, g, f D ∼ g disc m (f • D, g • D) ≤ and disc(f • D, g • D) ≤ (see Def. 8) N(U, ∼ U )

The covering number of U with respect to relation ∼ U on U (see Def.9) X :← x

x is assigned to X

In particular, there is some > 0 and an increasing sequence {k j } ∞ j=1 ⊂ N such that Q kj > for all j ∈ N. With no loss of generality, we can assume that k j = j (otherwise, we replace the original sequence with the new one). Since (

V kj 1 , ..., V kj m , U kj 1 , ..., U kj m ) ∈ G 2m E and G 2m E is compact in R M ×M ×2m

, by the Bolzano-Weierstrass theorem, it has a converging subsequence. With no loss of generality, we can assume that (V kj 1 , ..., V kj m , U kj 1 , ..., U kj m ) converges (otherwise, we replace it with a converging sub-sequence):

EQUATION

In particular,

EQUATION

By Assumption 4, the function R 

D1 [F [X m+n , ..., X 1 ], F [Y m+n , ..., Y 1 ]] is continuous. Therefore, RD 1 F [V k j m , ..., V k j 2 , V k j 1 • Wn, Wn-1, ..., W1], F [U k j m , ..., U k j 2 , U k j 1 • Wn, Wn-1, ..., W1] -RD 1 [F [Vm, ..., V2, V1

-RD 1 F [V k j m , ..., V k j 2 , V k j 1 • W k j n , W k j n-1 , ..., W k j 1 ], F [U k j m , ..., U k j 2 , U k j 1 • W k j n , W k j n-1 , ..., W k j 1 ] → 0 (96)

Therefore, by the triangle inequality,

Q k j = RD 1 F [V k j m , ..., V k j 2 V k j 1 • Wn, Wn-1, ..., W1], F [U j m , ..., U k j 2 , U k j 1 • Wn, Wn-1, ..., W1] -RD 1 F [V k j m , ..., V k j 2 , V k j 1 • W k j n , W k j n-1 , ..., W k j 1 ], F [U k j m , ...U k j 2 , U k j 1 • W k j n , W k j n-1 , ..., W k j 1 ] → 0 (97)

in contradiction. Thus, we conclude that:

EQUATION

] be two minimal decompositions. Assume Assumptions 2 and 3. Then, there are functions f = F [ Wn+1 , ..., W1 ] and ḡ = F [ Vn+1 , ..., V1 ] such that:

• C( f • g) = 2n. • ∀j ∈ [n + 1] : disc m (F [ Wj , ..., W1 ] • D, F [W j , ..., W 1 ] • D) ≤ . • ∀j ∈ [n + 1] : disc m (F [ Vj , ..., V1 ] • D, F [V j , ..., V 1 ] • D) ≤ . Proof. We consider that f • g = F [W n+1 , ..., W 2 , W 1 • V n+1 , V n , ..., V 1 ]. By Assumption 2, for each δ > 0, there are f = F [ Wn+1 , ..., W1 ] and ḡ = F [ Vn+1 , ..., V1 ] such that C( f • ḡ) = 2n and for all j ∈ [n + 1]: || Wj -W j ||, || Vj -V j || ≤ δ. By Assumption. 3, for each > 0, there is a small enough δ > 0 such that: f = F [ Wn+1 , ..., W1 ] and ḡ = F [ Vn+1 , ..., V1 ] such that for all j ∈ [n + 1]: || Wj -W j ||, || Vj -V j || ≤ δ, we have: • ∀j ∈ [n + 1] : disc m (F [ Wj , ..., W1 ] • D, F [W j , ..., W 1 ] • D) ≤ . • ∀j ∈ [n + 1] : disc m (F [ Vj , ..., V1 ] • D, F [V j , ..., V 1 ] • D) ≤ .

In particular, for any > 0, there are functions f = F [ Wn+1 , ..., W1 ] and ḡ = F [ Vn+1 , ..., V1 ] with the desired properties. 

f = F [W n+1 , ..., W 1 ] there is a minimal decomposition g = F [V n+1 , ..., V 1 ] such that: ∀i ∈ [n + 1] : F [W i , ..., W 1 ] • D ∼ m, F [V i , ..., V 1 ] • D (99) Proof. Since f D ∼ m, g there are minimal decompositions f = F [W n+1 , ..., W 1 ] and g = F [V n+1 , ..., V 1 ] such that: ∀i ∈ [n + 1] : F [W i , ..., W 1 ] • D ∼ m, F [V i , ..., V 1 ] • D (100) By Assumption 1, W 1 = τ 1 • W 1 , for all i = 2, ..., n: W i = τ i • W i • τ -1 i-1 and W n+1 = W n+1 • τ -1

n . Therefore, we define a minimal decomposition for g as follows:

g = F [V n+1 , ..., V 1 ] such that V 1 = τ 1 • V 1 , for all i = 2, ..., n: V i = τ i • V i • τ -1 i-1 and V n+1 = V n+1 • τ -1

n . This is a minimal decomposition of g, since each invariant function is an invertible linear mapping and commutes with σ. By Lem. 9 we have:

EQUATION

Therefore, by Lem. 4, since C(τ i ) = 0, we have:

∀i ∈ [n] :disc m (F [W i , ..., W 1 ] • D, F [V i , ..., V 1 ] • D) ≤ disc m (τ i • F [W i , ..., W 1 ] • D, τ i • F [V i , ..., V 1 ] • D) ≤ (102) Alternatively, ∀i ∈ [n] : F [W i , ..., W 1 ] • D ∼ F [V i , ..., V 1 ] • D (103) Since F [W n+1 , ..., W 1 = f = F [W n+1 , ..., W 1 ] and F [V n+1 , ..., V 1 ] = g = F [V n+1 , ..., V 1 ] we also have F [W n+1 , ..., W 1 ] • D ∼ m, F [V n+1 , ..., V 1 ] • D.

Lemma 22. Let N = SCM[σ] with σ that is Leaky ReLU with parameter 0 < a = 1. We have:

f D A ∼ k, 1 f , f D A ∼ k, f and f D A ∼ k, f =⇒ f D A ∼ k, 1-2 f (104)

Proof. Assume by contradiction that f

EQUATION

Therefore, by the triangle inequality, we arrive to a contradiction:

disc k (F [W i , ..., W 1 ] • D A , F [W i , ..., W 1 ] • D A ) ≤disc k (F [ Wi , ..., W1 ] • D A , F [W i , ..., W 1 ] • D A ) + disc k (F [ Wi , ..., W1 ] • D A , F [W i , ..., W 1 ] • D A ) ≤disc k (F [ Wi , ..., W1 ] • D A , F [ W i , ..., W 1 ] • D A ) + disc k (F [ Wi , ..., W1 ] • D A , F [W i , ..., W 1 ] • D A ) + disc k (F [ W i , ..., W 1 ] • D A , F [W i , ..., W 1 ] • D A ) ≤( 1 -2 ) + + = 1 (108) Lemma 23. Let N = SCM[σ] with σ that is a Leaky ReLU with parameter 0 < a = 1. Let A = (X A , D A ) and B = (X B , D B ) are two domains. We have: N H 0 (A, B), D A ∼ 1+2 0 ≤ N H 0 (B, A), D B ∼ 1 (109)

Proof. We would like to show that the function G

EQUATION

and by Lem. 1 and Lem. 13,

C(G(h)) = C(h -1 ) = C(h) = C 0 A,B = C 0 B,A . Therefore, G(h) ∈ H 0 (B, A). Next, we would like to prove that for all h 1 , h 2 ∈ H 0 (A, B): G(h 1 ) D B ∼ 1 G(h 2 ) =⇒ h 1 D A ∼ 1 +2 0 h 2 . We define G(f, g) = f • ḡ-1 .

Part 2: In this part, we show that:

g) ∈ (H 0 (A, B; m)) 2 =⇒ G(f, g) ∈ DPM 2 0+2 D B ; k, 0 A,B (117) By Part 1, C( f • ḡ-1 ) = 2n = 2C 0 A,B .

In addition, by the first item of Lem. 5, for D

EQUATION

Since f ∈ H 0 (A, B; m):

EQUATION

In addition, by the third item of Lem. 5, for h :← ḡ and m ≥ t + C 0 A,B ≥ t + C(ḡ -1 ), we have:

EQUATION

Finally, disc k ( f • ḡ-1 • D B , D B ) ≤ 2 0 + 2 and we conclude that:

EQUATION

Part 3: In this part, we show that G is an embedding. It requires showing that

EQUATION

Assume by contradiction that G(f, g)

D B ∼ m, 2

G(f , g ) and that (f, g)

D A ∼ k, 1

(f , g ). Then, we have

EQUATION

We denote G(f, g) = f • ḡ-1 and G(f , g ) = f • (ḡ ) -1 (see Part 1). 

Assume that f:

there is an index i ∈ [n + 1] such that:

EQUATION

The option i = n + 1 is not a possibility, since: A,B ≥ t + C(F [( V i+1 ) -1 /a, ..., ( V n ) -1 /a, -( V n+1 ) -1 /a]), we have:

EQUATION

disct F [ V -1 i+1 /a, ..., V -1 n /a, -V -1 n+1 /a] • DB, F [( V i+1 ) -1 /a, ..., ( V n ) -1 /a, -(

V n+1 ) -1 /a] • ḡ • DA ≤ discm F [ V -1 i+1 /a, ..., V -1 n /a, -V -1 n+1 /a] • DB, F [( V i+1 ) -1 /a, ..., ( V n ) -1 /a, -( V n+1 ) -1 /a] • DB + discm(ḡ • DA, DB) ≤ discm F [ V -1 i+1 /a, ..., V -1 n /a, -V -1 n+1 /a] • DB, F [( V i+1 ) -1 /a, ..., ( V n ) -1 /a, -( V n+1 ) -1 /a] • DB + 0 + (137)

Finally,

EQUATION

In particular,

EQUATION

Alternatively, for any minimal decompositions f • ḡ-1 = F [ Wn+1, ..., W2, -W1 • V1, V -1 2 /a, ..., V -1 n /a, -V -1 n+1 /a] and f • (ḡ ) -1 = F [ Wn+1, ..., W2, -W1 • ( V 1 ) -1 , ( V 2 ) -1 /a, ..., ( V n ) -1 /a, -( V n+1 ) -1 /a] (140) there are right partial functions

EQUATION

such that Eq. 139 holds, in contradiction to F (f, g)

D B ∼ m, 2 F (f , g ).

Part 3: Finally, by Lem. 17 and Lem. 14, N H 0 (A, B; m),

EQUATION

Alternatively, for all 0 , 1 , 2 , such that < min{( 1 -2 0 -2 )/4, 2 /2}, N H 0 (A, B; m), . Therefore, by the monotone convergence theorem, the limit lim →0 q exists and upper bounds N H 0 (A, B; m),

EQUATION

D A ∼ k, 1

.

Theorem 1. Let N = SCM[σ] with σ that is Leaky ReLU with parameter 0 < a = 1. Assume Assumptions 1, 2 and 3. Let 0 , 1 and 2 be three constants such that 0 < 1 /4 and 2 < 1 -4 0 be three positive 

E WASSERSTEIN GAN RESULTS:

It is interesting to check whether the predictions made are valid for other forms of discrepancy such as the one used in the Wasserstein GAN Arjovsky et al. (2017) (WGAN) . This is done below for Prediction 2, which predicts that the selection of the right number of layers is crucial in unsupervised learning. In the WGAN experiment, we employ the architecture of (Kim et al., 2017) and vary the number of layers and inspect the influence on the results. For the generator, the architecture is identical while for WGAN's critic, the last sigmoid layer is removed. These experiments were done on the CelebA dataset, obtaining the results in Fig. 30 -35.

Note that since the encoder and the decoder parts of the learned network are symmetrical, the number of layers is always even. As can be seen, changing the number of layers has a dramatic effect on the results. The best overall results are obtained at 6 layers. Using fewer layers, WGAN often fails to produce images of the desired class. Adding layers, the semantic alignment is lost, as expected.

:

σa(x) = Ind[x < 0]ax + Ind[x ≥ 0]x, for the indicator function Ind[q] which maps a true value to one, zero otherwise.

The MDL literature was developed when people believed that small hypothesis classes are desired for both supervised and unsupervised learning.

Figures and Tables:

Figure 1: The mappings between the domains A, B, and Z.

Figure 3: Results for celebA Male to Female transfer (a) Input (b) The mapping obtained by the GAN loss without additional losses.

Figure 4: Same as Fig. 3 for black to blond hair conversion.

Figure 5: Same as Fig. 3 for eyeglasses to no eyeglasses conversion.

Figure 6: Same as Fig. 3 for handbag to shoes and shoes to handbag mapping.

Figure 7: Same as Fig. 3 for edges to shoes and shoes to edges conversion.

Figure 8: Results for celebA Male to Female transfer for networks with different number of layers.

Figure20: Results for Alg. 1 on Male2Female dataset for mapping male to female. Shown is a minimal complexity mapping g that has low discrepancy, and various mappings h obtained by the method.

Figure 23: Results for Alg. 1 on celebA dataset for mapping black to blond. Shown is a minimal complexity mapping g that has low discrepancy, and various mappings h obtained by the method.

Figure24: Results for Alg. 1 on Eyeglasses dataset for mapping eyeglasses to no eyeglasses. Shown is a minimal complexity mapping g that has low discrepancy, and various mappings h obtained by the method.

Figure 25: Results for Alg. 1 on Eyeglasses dataset for mapping no eyeglasses to eyeglasses. Shown is a minimal complexity mapping g that has low discrepancy, and various mappings h obtained by the method.

Figure 26: Results for Alg. 1 on Edges2Handbags dataset for mapping edges to handbags. Shown is a minimal complexity mapping g that has low discrepancy, and various mappings h obtained by the method.

Figure 28: Results for on Edges2Shoes dataset for mapping to shoes. Shown are a minimal complexity mapping g has low discrepancy, and various mappings h obtained by the method.

Stratified complexity model (SCM)). A stratified complexity model N := SCM[C] is hypothesis class of functions p : R M → R M specified by a set of functions C. Every function p in N has an appropriate decomposition:

Finally, we would like to show that for every u ∈ N , we have: C(u -1 ) = C(u). If C(u) = 0, then, by Lem. 11, C(u -1 ) = 0. On the other hand, if C(u) = 0, then, by Lem. 11, C(u -1 ) = 0 and by the above: C(u) = C (u) = C (u -1 ) = C(u).

Let N = SCM[σ] with σ that is Leaky ReLU with parameter 0 < a = 1. For every m > 0 (possibly ∞) and n > 0, the function disc m (F [W n , ..., W 1 ] • D 1 , D 2 ) is continuous as a function of the weights of W 1 , ..., W n ∈ R M ×M .

6) τ An invariant function (see Def. 6) D m D m = {u|C(u) ≤ m} disc m , disc disc m := disc Dm and disc := disc D∞ C m, 0 A,B

Let N = SCM[σ] with σ that is Leaky ReLU with parameter 0 < a = 1. Assume Assumption 1. Let f D ∼ m,g. Then, for every minimal decomposition

particular, for every two decompositions:f = F [ Wn+1 , ..., W1 ] and f = F [ W n+1 , ..., W 1 ]

126)By the first item of Lem. 5, forD 1 :← D A , D 2 :← ḡ-1 • D B , D 3 :← F [ W i , ..., W 1 ] • D A , p :← F [ Wi , ..., W1 ] and t ≥ k + C 0 A,B ≥ k + C(F [ Wi , ...,W1]), we have:disc k (F [ Wi, ..., W1] • DA, F [ W i , ..., W 1 ] • DA) ≤ disct(F [ Wi, ..., W1] • ḡ-1 • DB, F [ W i , ..., W 1 ] • DA) + disct(ḡ -1 • DB, DA) ≤ disct(F [ Wi, ..., W1] • ḡ-1 • DB, F [ W i , ..., W 1 ] • DA) + 0 (127)Again, by the first item of Lem. 5, forD 1 :← D A , D 2 :← (g ) -1 • D B , D 3 :← F [ Wi , ..., W1 ] • g -1 • D B , p :← F [ W i , ..., W 1 ] and m ≥ t + C 0 A,B ≥ t + C(F [ W i , ..., W 1 ]), we have: disct(F [ Wi, ..., W1] • ḡ-1 • DB, F [ W i , ..., W 1 ] • DA) ≤discm(F [ Wi, ..., W1] • ḡ-1 • DB, F [ W i , ..., W 1 ] • (ḡ ) -1 • DB) + discm((ḡ ) -1 • DB, DA) ≤discm(F [ Wi, ..., W1] • g -1 • DB, F [ W i , ..., W 1 ] • (g ) -1 • DB) + 0(128)Again, by Lem. 5, for D1 :← ḡ • D A , D 2 :← D B D 3 :← F [ V -1 i+1 /a, ..., V -1 n /a, -V -1 n+1 /a] D B , m ≥ t + C 0

conference paper at ICLR 2018In particular, we can replace with /2 in the inequality. By Lem. 18, the function q = N DPM 2 0+ k,

constants and A = (X A , D A ) and B = (X B , D B ) are two domains. Then, By Lem. 2, with m = k = ∞, we have: N H 0 (A, B), in the RHS of Eqs. 144 and 145 are limits of positive integers, we have: N H 0 (A, B),

Comparing the VGG descriptor similarity, separation accuracy and discrepancy for varying complexity k k = 4 k = 6 k = 8 k = 10 k = 12 k = 14

Table content: <table><tr><td>Male to Female</td><td colspan="2">Discrepancy 0.527 0.203 0.091</td><td>0.094</td><td>0.083</td><td>0.086</td></tr><tr><td/><td>Similarity</td><td>0.301 0.269 0.103</td><td>0.106</td><td>0.089</td><td>0.100</td></tr><tr><td/><td>Separation</td><td>0.938 0.932 0.940</td><td>0.940</td><td>0.940</td><td>0.938</td></tr><tr><td>Female to Male</td><td colspan="2">Discrepancy 0.882 0.122 0.150</td><td>0.075</td><td>0.076</td><td>0.091</td></tr><tr><td/><td>Similarity</td><td>0.303 0.260 0.110</td><td>0.105</td><td>0.093</td><td>0.100</td></tr><tr><td/><td>Separation</td><td>0.798 0.865 0.860</td><td>0.87</td><td>0.857</td><td>0.866</td></tr><tr><td>Blond to Black Hair</td><td colspan="2">Discrepancy 0.467 0.214 0.092</td><td>0.097</td><td>0.094</td><td>0.081</td></tr><tr><td/><td>Similarity</td><td>0.365 0.287 0.240</td><td>0.106</td><td>0.091</td><td>0.0870</td></tr><tr><td/><td>Separation</td><td>0.903 0.925 0.922</td><td>0.917</td><td>0.922</td><td>0.923</td></tr><tr><td>Black to Blond Hair</td><td colspan="2">Discrepancy 0.663 0.264 0.073</td><td>0.094</td><td>0.084</td><td>0.076</td></tr><tr><td/><td>Similarity</td><td>0.337 0.270 0.240</td><td>0.106</td><td>0.087</td><td>0.085</td></tr><tr><td/><td>Separation</td><td>0.941 0.941 0.911</td><td>0.916</td><td>0.915</td><td>0.917</td></tr><tr><td colspan="3">Eyeglasses to Non-Eyeglasses Discrepancy 0.323 0.159 0.071</td><td>0.082</td><td>0.083</td><td>0.081</td></tr><tr><td/><td>Similarity</td><td>0.470 0.391 0.347</td><td>0.114</td><td>0.125</td><td>0.146</td></tr><tr><td/><td>Separation</td><td>0.786 0.785 0.828</td><td>0.843</td><td>0.849</td><td>0.828</td></tr><tr><td colspan="3">Non Eyeglasses to Eyeglasses Discrepancy 0.577 0.518 0.236</td><td>0.263</td><td>0.093</td><td>0.085</td></tr><tr><td/><td>Similarity</td><td>0.452 0.373 0.364</td><td>0.105</td><td>0.108</td><td>0.127</td></tr><tr><td/><td>Septation</td><td>0.748 0.749 0.766</td><td>0.848</td><td>0.832</td><td>0.840</td></tr></table>

(a) Norms of the various mappings h for mapping Males to Females using the DiscoGAN architecture. (b) Norms of 18-layer networks that approximates the mappings obtained with a varying number of layers.

Table content: <table><tr><td/><td colspan="5">----Number of layers ----</td></tr><tr><td>Norm</td><td>4</td><td>6</td><td>8</td><td>10</td><td>12</td></tr><tr><td>A to B L1 norm</td><td colspan="5">6382 23530 36920 44670 71930</td></tr><tr><td colspan="2">Average L1 norm per layer 1064</td><td>2353</td><td>2637</td><td>2482</td><td>3270</td></tr><tr><td>L2 norm</td><td colspan="5">18.25 29.24 28.44 31.72 36.57</td></tr><tr><td colspan="6">Average L2 norm per layer 7.084 8.353 7.154 6.708 7.009</td></tr><tr><td>B to A L1 norm</td><td colspan="5">6311 21240 31090 37380 64500</td></tr><tr><td colspan="2">Average L1 norm per layer 1052</td><td>2124</td><td>2221</td><td>2077</td><td>2932</td></tr><tr><td>L2 norm</td><td colspan="5">18.36 26.79 25.85 28.36 34.99</td></tr><tr><td colspan="6">Average L2 norm per layer 7.161 7.757 6.552 6.058 6.771</td></tr><tr><td/><td>(a)</td><td/><td/><td/><td/></tr><tr><td/><td colspan="5">----Number of layers ----</td></tr><tr><td>Norm</td><td>4</td><td>6</td><td>8</td><td>10</td><td>12</td></tr><tr><td>A to B L1 norm</td><td colspan="5">317200 228700 356500 247200 164200</td></tr><tr><td>Average L1 norm per layer</td><td>9329</td><td>6726</td><td>10485</td><td>7271</td><td>4829</td></tr><tr><td>L2 norm</td><td>528.1</td><td>401.7</td><td>559.6</td><td>410.1</td><td>346.8</td></tr><tr><td>Average L2 norm per layer</td><td>3.031</td><td>2.284</td><td>3.242</td><td>2.257</td><td>1.890</td></tr><tr><td>B to A L1 norm</td><td colspan="5">316900 194500 353900 171500 228900</td></tr><tr><td>Average L1 norm per layer</td><td>9323</td><td>5719</td><td>10410</td><td>5045</td><td>6733</td></tr><tr><td>L2 norm</td><td>523.2</td><td>375.9</td><td>555.7</td><td>346.5</td><td>373.3</td></tr><tr><td>Average L2 norm per layer</td><td>3.003</td><td>2.029</td><td>3.210</td><td>1.921</td><td>2.289</td></tr><tr><td/><td>(b)</td><td/><td/><td/><td/></tr></table>

Seeking DPMs: the distance from the identity and the discrepancy (GAN loss) for various numbers of layers, where training a DiscoGAN from a dataset to itself.

Table content: <table><tr><td>----Number of layers: ----</td></tr></table>

Results for Alg. 1 for different datasets. VGG Similarity is given in the first column. The second column gives the separation value using the linear classifier. In the third column, we measure the discrepancy of the mapping. The last column provides the distance of h to g, where applicable.

Table content: <table><tr><td>Dataset</td><td colspan="4">f Complexity Descriptor Separation</td><td>Discrepancy</td><td>Distance</td></tr><tr><td colspan="2">Male to Female g</td><td>k 1 = 6</td><td>Similarity 0.267</td><td colspan="3">Accuracy disc(f • D A , D B ) R D A [h, g] 0.928 0.230 -</td></tr><tr><td/><td>g</td><td>k = 8</td><td>0.280</td><td>0.938</td><td>0.077</td><td>-</td></tr><tr><td/><td>g</td><td>k = 10</td><td>0.106</td><td>0.940</td><td>0.094</td><td>-</td></tr><tr><td/><td>g</td><td>k = 12</td><td>0.089</td><td>0.940</td><td>0.083</td><td>-</td></tr><tr><td/><td>h</td><td>k 2 = 8</td><td>0.316</td><td>0.933</td><td>0.087</td><td>0.054</td></tr><tr><td/><td>h</td><td>k 2 = 10</td><td>0.204</td><td>0.937</td><td>0.109</td><td>0.075</td></tr><tr><td/><td>h</td><td>k 2 = 12</td><td>0.197</td><td>0.941</td><td>0.127</td><td>0.077</td></tr><tr><td colspan="2">Female to Male g</td><td>k 1 = 6</td><td>0.268</td><td>0.848</td><td>0.310</td><td>-</td></tr><tr><td/><td>g</td><td>k = 8</td><td>0.260</td><td>0.848</td><td>0.107</td><td>-</td></tr><tr><td/><td>g</td><td>k = 10</td><td>0.105</td><td>0.870</td><td>0.075</td><td>-</td></tr><tr><td/><td>g</td><td>k = 12</td><td>0.093</td><td>0.857</td><td>0.076</td><td>-</td></tr><tr><td/><td>h</td><td>k 2 = 8</td><td>0.304</td><td>0.878</td><td>0.107</td><td>0.056</td></tr><tr><td/><td>h</td><td>k 2 = 10</td><td>0.215</td><td>0.884</td><td>0.082</td><td>0.083</td></tr><tr><td/><td>h</td><td>k 2 = 12</td><td>0.214</td><td>0.883</td><td>0.073</td><td>0.082</td></tr><tr><td>Blond to</td><td>g</td><td>k 1 = 6</td><td>0.287</td><td>0.925</td><td>0.214</td><td>-</td></tr><tr><td>Black Hair</td><td>g</td><td>k = 8</td><td>0.24</td><td>0.922</td><td>0.092</td><td>-</td></tr><tr><td/><td>g</td><td>k = 10</td><td>0.106</td><td>0.917</td><td>0.097</td><td>-</td></tr><tr><td/><td>g</td><td>k = 12</td><td>0.091</td><td>0.922</td><td>0.094</td><td>-</td></tr><tr><td/><td>h</td><td>k 2 = 8</td><td>0.293</td><td>0.926</td><td>0.136</td><td>0.152</td></tr><tr><td/><td>h</td><td>k 2 = 10</td><td>0.197</td><td>0.926</td><td>0.225</td><td>0.161</td></tr><tr><td/><td>h</td><td>k 2 = 12</td><td>0.199</td><td>0.928</td><td>0.092</td><td>0.161</td></tr><tr><td>Black to</td><td>g</td><td>k 1 = 6</td><td>0.270</td><td>0.941</td><td>0.264</td><td>-</td></tr><tr><td>Blond Hair</td><td>g</td><td>k = 8</td><td>0.24</td><td>0.911</td><td>0.073</td><td>-</td></tr><tr><td/><td>g</td><td>k = 10</td><td>0.106</td><td>0.916</td><td>0.094</td><td>-</td></tr><tr><td/><td>g</td><td>k = 12</td><td>0.087</td><td>0.915</td><td>0.084</td><td>-</td></tr><tr><td/><td>h</td><td>k 2 = 8</td><td>0.287</td><td>0.938</td><td>0.077</td><td>0.146</td></tr><tr><td/><td>h</td><td>k 2 = 10</td><td>0.179</td><td>0.946</td><td>0.165</td><td>0.149</td></tr><tr><td/><td>h</td><td>k 2 = 12</td><td>0.180</td><td>0.952</td><td>0.168</td><td>0.152</td></tr><tr><td>Eyeglasses to</td><td/><td/><td/><td/><td/><td/></tr><tr><td colspan="2">Non-Eyeglasses g</td><td>k 1 = 6</td><td>0.391</td><td>0.785</td><td>0.159</td><td>-</td></tr><tr><td/><td>g</td><td>k = 8</td><td>0.347</td><td>0.828</td><td>0.071</td><td>-</td></tr><tr><td/><td>g</td><td>k = 10</td><td>0.114</td><td>0.843</td><td>0.082</td><td>-</td></tr><tr><td/><td>g</td><td>k = 12</td><td>0.125</td><td>0.849</td><td>0.083</td><td>-</td></tr><tr><td/><td>h</td><td>k 2 = 8</td><td>0.391</td><td>0.786</td><td>0.097</td><td>0.058</td></tr><tr><td/><td>h</td><td>k 2 = 10</td><td>0.283</td><td>0.847</td><td>0.180</td><td>0.083</td></tr><tr><td/><td>h</td><td>k 2 = 12</td><td>0.274</td><td>0.860</td><td>0.148</td><td>0.081</td></tr><tr><td>Non-Eyeglasses</td><td/><td/><td/><td/><td/><td/></tr><tr><td>to Eyeglasses</td><td>g</td><td>k 1 = 6</td><td>0.373</td><td>0.749</td><td>0.518</td><td>-</td></tr><tr><td/><td>g</td><td>k = 8</td><td>0.364</td><td>0.766</td><td>0.236</td><td>-</td></tr><tr><td/><td>g</td><td>k = 10</td><td>0.105</td><td>0.848</td><td>0.263</td><td>-</td></tr><tr><td/><td>g</td><td>k = 12</td><td>0.108</td><td>0.832</td><td>0.093</td><td>-</td></tr><tr><td/><td>h</td><td>k 2 = 8</td><td>0.389</td><td>0.780</td><td>0.300</td><td>0.063</td></tr><tr><td/><td>h</td><td>k 2 = 10</td><td>0.272</td><td>0.807</td><td>0.370</td><td>0.083</td></tr><tr><td/><td>h</td><td>k 2 = 12</td><td>0.282</td><td>0.803</td><td>0.409</td><td>0.081</td></tr></table>

The sample spaces of A and B (resp.) D A , D B Distributions over X A and X B (resp.) A, B Two domains; Specified by (X A , D A ) and (X B , D B ) (resp.) y A , y B

Table content: <table><tr><td/><td>: Summary Notation</td></tr><tr><td>Symbol</td><td>Explanation</td></tr><tr><td/><td>A feature space</td></tr><tr><td>X A , X B</td><td/></tr></table>

Peer review (iclr2018):
 The paper addresses the problem of learning mappings between different domains without any supervision. It belongs to the recent family of papers based on GANs. The paper states three conjectures (predictions in the paper): 1. GAN are sufficient to learn « semantic mappings » in an unsupervised way, if the considered networks are small enough 2. Controlling the complexity of the network, i.e. the number of the layers, is crucial to come up with what is called « semantic » mappings when learning in an unsupervised way. More precisely there is tradeoff to achieve between the complexity of the model and its simplicity. A rich model is required in order to minimize the discrepancy between the distributions of the domains, while a not too complex model is necessary to avoid mappings that are not « meaningful ». To this aim, the authors introduce a new notion of function complexity which can be seen as a proxy of Kolmogorov complexity. The introduced notion is very simple and intuitive and is defined as the depth of a network which is necessary to implement the considered function. Based on this definition, and assuming identifiability (i.e. uniqueness up to invariants), and for networks with Leaky ReLU activations, the authors prove that if the number of mappings which preserve a degree of discrepancy (density preserving in the text) is small, then the set of « minimal » mappings of complexity C that achieve the same degree of discrepancy is also small. This result is related to the third conjecture of the paper that is : 3. the number of the number of mappings which preserve a degree of discrepancy is small. The authors also prove a byproduct result stating that identifiability holds for Leaky ReLU networks with one hidden layer. The paper comes with a series of experiments to empirically « demonstrate » the conjectures. The paper is well written. The different ideas are clearly stated and discussed, and hence open interesting questions and debates. Some of these questions that need to be addressed IMHO: - A critical general question: if the addressed problem is the alignment between e.g. images and not image generation, why not formalizing the problem as a similarity search one (using e.g. EMD or any other transport metric). The alignment task hence reduces to computing a ranking from this similarity. I have the impression that we use a jackhammer to break a small brick here (no offence). But maybe that I’m missing something here. - Several works consider the size and the depth of the network as hyper-parameters to optimize, and this is not new. What is the actual contribution of the paper w.r.t. to this body of work? - It is considered that the GAN are trained without any problem, and therefore work in an optimal regime. But the training of the GAN is in itself a problem. How does this affect the paper statements and results? - Are the results still valid for another measure of discrepancy based for instance on another measure, e.g. Wasserstein? Some minor remarks : - p3: the following sentence is not clear « Our hypothesis is that the lowest complexity small discrepancy mapping approximates the alignment of the target semantic function. » - p6: is used (after Def. 2) before being defined. - p7: build->built Section II : A diagram explaining the different mappings (h_A, h_B, h_AB, etc.) and their spaces (D_A, D_B, D_Z) would greatly help the understanding. Papers *s pros : - clarity - technical results cons: - doubts about the interest and originality The authors provided detailed and convincing answers to my questions. I thank them for that. My scores were changed accrodingly.