The Role of Minimal Complexity Functions in Unsupervised Learning of\n Semantic Mappings

Abstract

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