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. Multiple recent reports (Xia et al., 2016; BID13 BID12 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 BID9 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 BID13 , 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. 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 BID11 and later analyzed by BID10 .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; BID7 BID15 . 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 BID13 , is similar in nature to the mapping of x to 1 − x 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, DISPLAYFORM0 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. FORMULA0 present empirical evidence that a meaningful mapper can be learned, even from very few examples, if the network trained is kept small. 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. FIG1 : 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.
Our hypothesis is that given two domains, the lowest complexity mapping that has a low discrepancy approximates the target mapping. The paper addresses the problem of learning mappings between different domains without any supervision, stating three conjectures. Demonstrates that in unsupervised learning on unaligned data it is possible to learn the between domains mapping using GAN only without a reconstruction loss.