HOUDINI: Lifelong Learning as Program Synthesis
We present a neurosymbolic framework for the lifelong learning of algorithmic tasks that mix perception and procedural reasoning. Reusing high-level concepts across domains and learning complex procedures are key challenges in lifelong learning. We show that a program synthesis approach that combines gradient descent with combinatorial search over programs can be a more effective response to these challenges than purely neural methods. Our framework, called HOUDINI, represents neural networks as strongly typed, differentiable functional programs that use symbolic higher-order combinators to compose a library of neural functions. Our learning algorithm consists of: (1) a symbolic program synthesizer that performs a type-directed search over parameterized programs, and decides on the library functions to reuse, and the architectures to combine them, while learning a sequence of tasks; and (2) a neural module that trains these programs using stochastic gradient descent. We evaluate HOUDINI on three benchmarks that combine perception with the algorithmic tasks of counting, summing, and shortest-path computation. Our experiments show that HOUDINI transfers high-level concepts more effectively than traditional transfer learning and progressive neural networks, and that the typed representation of networks significantly accelerates the search.
The authors present an algorithm for transfer learning using a symbolic program synthesizer for finding the most adequate neural network architecture and selecting relevant neural network modules from previous tasks for transfer. The approach is heavily based on concepts from programming languages, but also studies the relevant concept of high-level transfer that is crucial for true lifelong learning. Results show how the algorithm is capable of selectively transferring (high- and low-level) knowledge in a meaningful way, and numerical results validate the significance of the approach.  The authors claim that their method targets the lifelong learning problem, but theirs is really a transfer learning approach. Solving catastrophic forgetting by completely freezing the network parameters precludes the method from being true lifelong learning, in which the learning of subsequent tasks affects the performance of earlier tasks. As a transfer learning method, it is quite interesting in that it selects which parts of the network of a previous task are useful to transfer over to a new task and with which combinator, allowing it to create the relevant transfer architecture via search.  This is apparently the first study of program synthesis for differentiable programs. The idea of using program search for transfer learning is novel, and provides an interesting avenue for future work, although the search methods themselves don't seem novel. The usage of type-based pruning dramatically reduces the search-space, which is the only way for this approach to be applicable in a realistic learning scenario.  The presentation is very complete, with a good amount of details on the proposed language and clear explanations on how these details are useful (and necessary) for learning. However, other details like the specific heuristic used for sorting the program search queue should be provided.  As for the learning algorithm, it seems unjustified to simply compare validation performance as a selection criterion for the network architecture, especially since in a transfer learning context it is many times infeasible to set aside a validation set. Since the approach is presented as solving an optimization problem, using the cost function as the selection criterion seems better.  The experimental setting was good, and discussing (and showing in the appendix) the actual programs learned by the approach was helpful to see the actual capabilities of the algorithm of transferring knowledge. I would have liked to see some randomized experiments where the sequences of tasks were not chosen specifically to highlight the algorithm's strengths, although it was good that many different sequences were used. It is unclear to me what dataset size was used for the actual programs learned by the method showed in the appendix; this should be specified.  I notice a couple of presentation issues. First, Figure 3 is actually a table, and should be presented as such. Second, all the appendices are referenced as Appendix, but it would be far more helpful if the actual appendix number were used. Figure 4 is presented almost 2 pages after it is first discussed, which makes it awkward to look for.  Typos: - Line 101: "Figure 1 gives shows..." - Line 274: "Leanrning a effective..."