AUTOMATICALLY COMPOSING REPRESENTATION TRANSFORMATIONS AS A MEANS FOR GENERALIZATION
A generally intelligent learner should generalize to more complex tasks than it has previously encountered, but the two common paradigms in machine learning -either training a separate learner per task or training a single learner for all tasks -both have difficulty with such generalization because they do not leverage the compositional structure of the task distribution. This paper introduces the compositional problem graph as a broadly applicable formalism to relate tasks of different complexity in terms of problems with shared subproblems. We propose the compositional generalization problem for measuring how readily old knowledge can be reused and hence built upon. As a first step for tackling compositional generalization, we introduce the compositional recursive learner, a domaingeneral framework for learning algorithmic procedures for composing representation transformations, producing a learner that reasons about what computation to execute by making analogies to previously seen problems. We show on a symbolic and a high-dimensional domain that our compositional approach can generalize to more complex problems than the learner has previously encountered, whereas baselines that are not explicitly compositional do not.
==== Summary ====
This paper proposes a model for learning problems that exhibit compositional and recursive structure, called Compositional Recursive Learner (CRL). The paper approaches the subject by first defining a problem as a transformation of an input representation x from a source domain t_x to a target domain t_y. If t_x = t_y then it is called a recursive problem, and otherwise a translational problem. A composite problem is the composition of such transformations. The key observation of the paper is that many real-world problems can be solved iteratively by either recursively transforming an instance of a problem to a simpler instance, or by translating it to a similar problem which we already know how to solve (e.g., translating a sentence from English to French through Spanish). The CRL model is essentially composed of two parts, a set of differential functions and a controller (policy) for selecting functions. At each step i, the controller observes the last intermediate computation x_i and the target domain t_y, and then selects a function and the subset of x_i to operate on. For each instance, the resulting compositional function is trained via back-propagation, and the controller is trained via policy gradient. Finally, the paper presents experiments on two synthetic datasets, translating an arithmetic expression written in one language to its outcome written in another language, and classifying MNIST digits that were distorted by an unknown random sequence of affine transformations. CRL is compared to RNN on the arithmetic task and shown to be able to generalize both to longer sequences and to unseen language pairs when trained on few examples, while RNN can achieve similar performance only using many more examples. On MNIST, it is qualitatively shown that CRL can usually (but not always) find the sequence of transformations to restore the digit to its canonical form.
==== Detailed Review ====
I generally like this article, as it contains a neat solution to a common problem that builds on and extends prior work. Specifically, the proposed CRL model is a natural evolution of previous attempts at solving problems via compositionally, e.g. Neural Programmer [1] that learns a policy for composing predefined commands, and Neural Module Networks [2] that learns the parameters of shared differential modules connected via deterministically defined structure (found via simple parse tree). The paper contains a careful review of the related works and highlights the similarities and differences from prior approaches. Though the experiments are mostly synthetic, the underlying method seems to be readily applicable to many real-world problems.
However, the true contributions of the paper are somewhat muddied by presenting CRL as more general than what is actually supported by the experiments. More specifically, the paper presents CRL as a general method for learning compositional problems by decomposing them into simpler sub-problems that are automatically discovered, but in practice, a far more limited version of CRL is used in the experiments, and the suggested translational capabilities of CRL, which are important for abstract sub-problem discovery, are not properly validated:
1. In both experiments, the building-block functions are hand-crafted to fit to the prior knowledge on the compositionally of the problem. For the arithmetic task, the functions are limited to operate each step just on a single window of encompassing 3 symbols (e.g., <number> <op> <number>,  <op> <number> <op>) and return a distribution over the possible symbols, which heavily forces the functions to represent simple evaluators for simple expressions of the form <number> <op> <number>. For the distorted MNIST task, the functions are limited to neural networks which choose the parameter of predetermined transformations (scaling, translation, or rotation) of the input. In both cases, CRL did not *found* sub-problems for reducing the complexity of the original instance but just had to *fine tune* loosely predefined sub-problems. Incorporating expert knowledge into the model like so is actually an elegant and useful trick for solving real problems, and it should be emphasized far clearly in the article. The story of “discovering subproblems” should be left for the discussion / future research section, because though it might be a small step towards that goal, it is not quite there yet.
2. The experiments very neatly show how recursive transformations offer a nice framework for simplifying an instance of a problem. However, the translation capabilities of the model are barely tested by the presented experiments, and it can be argued that all transformations used by the model are recursive in both experiments. First, only the arithmetic task has a translation aspect to it, i.e., the task is to read an expression in one language and then output the answer in a different language. Second, this problem is only weakly related to translation because it is possible to translate the symbols independently, word by word, as opposed to written language that has complex dependencies between words. Third, the authors report that in practice proper translation was only used in the very last operation for translating the computed value of the input expression to the requested language, and not as a method to translate one instance that we cannot solve into another that we can. Finally, all functions operate and return on all symbols and not ones limited to a specific language, and so by the paper’s own definition, these are all recursive problems and not translational ones.
In conclusion, I believe this paper should be accepted even with the above issues, mostly because the core method is novel, clearly explained, and appears to be very useful in practice. Nevertheless, I strongly suggest to the authors to revise their article to focus on the core qualities of their method that can be backed by their current experiments, and correctly frame the discussion on possible future capabilities as such.
[1] Reed et al. Neural Programmer-Interpreters. ICLR 2016.
[2] Andreas et al. Neural Module Networks. CVPR 2016.