PaperlayerView exact revision on arXiv

Source-linked AI summary

HOUDINI: Lifelong Learning as Program Synthesis

Lazar Valkov, Dipak Chaudhari, Akash Srivastava, Charles Sutton, Swarat Chaudhuri

arXiv:1804.00218v2cs.LGcs.PLstat.ML

TL;DR

Learning procedures that combine perception and algorithmic reasoning requires reusing high-level concepts across tasks, while inducing differentiable program structure remains difficult. HOUDINI combines typed symbolic program search with gradient-based parameter learning and reports stronger high-level transfer than traditional and progressive transfer methods. Its experiments also find that types accelerate search.

  • Problem

    Inducing differentiable program structure is difficult, and prior approaches still require detailed hand-written templates even for simple tasks despite the potential for high-level transfer.

    Source: §1 · p. 1

  • Method

    HOUDINI searches strongly typed functional programs that compose reusable neural library functions, then tunes their parameters using gradient descent.

    Source: §1 · p. 2

  • Results

    HOUDINI transfers high-level concepts more effectively than progressive neural networks and traditional low-level transfer across benchmarks combining perception with counting, summing, and shortest-path tasks.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Typed functional program synthesis can select both pretrained functions to reuse and the architecture that combines them, supporting high-level concept transfer on lifelong learning tasks.

    Source: §5 · p. 9

    The learning setup assumes i.i.d. training samples and a known, shared input-output type for each task.

    Source: §3 · p. 4

Abstract

from arXiv · show

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.

1 Introduction

HOUDINI addresses the challenge of inducing differentiable programs that can transfer high-level concepts across tasks without detailed hand-written templates. It combines symbolic program search with gradient-based learning in a typed functional representation, and reports stronger transfer than low-level baselines.

1 Introduction

  • High-level transfer reuses library functions trained on earlier tasks, unlike standard deep-network transfer that reuses early layers.Prior differentiable-program methods still required detailed hand-written templates for even simple tasks.Source: §1 · p. 1
  • HOUDINI combines symbolic program search, which explores structural changes, with stochastic gradient descent, which learns program parameters.The synthesizer searches typed functional programs and selects library functions and architectures to combine.Source: §1 · p. 2
  • Typed functional programs compactly represent neural architectures, while types prune infeasible programs early in the search.Functional combinators can express recurrent networks and convolution over lists or graphs.Source: §1 · p. 2
  • A neural library lets HOUDINI freeze and selectively reuse successful network portions, addressing catastrophic forgetting and negative transfer.The synthesizer can choose which library functions to reuse as it learns successive tasks.Source: §1 · p. 2
  • HOUDINI transfers high-level concepts more effectively than progressive neural networks and traditional low-level transfer, while learning perception-and-algorithm tasks.The benchmarks include counting, summing, and shortest-path computation; the shortest-path program resembles Bellman-Ford but learns its relaxation function.Source: §1 · p. 2
  • The paper’s contributions include typed functional representations with tensor-dimension information and few-shot learning through modular transfer.The authors also propose symbolic program synthesis for transfer and lifelong learning.Source: §1 · p. 2

2 The HOUDINI Programming Language

HOUDINI represents differentiable networks as strongly typed functional programs built from neural library functions and higher-order combinators. This representation can express common architectures and procedural operations, including graph-based shortest-path computation.

2 The HOUDINI Programming Language

  • HOUDINI combines a typed higher-order functional language with symbolic program enumeration and gradient-based parameter tuning and evaluation.The synthesizer enumerates parameterized programs; the neural module trains their parameters and assesses solution quality.Source: §2 · p. 3
  • Types distinguish tensors by element type and dimensions, functions, and list or graph data structures.The implementation bounds tensor dimensions and supports list and graph ADTs whose elements have tensor types.Source: §2 · p. 3
  • Composition connects neural library functions, while map, fold, and convolution combinators express operations over lists and graphs.These constructs support compact representations of feedforward, recurrent, and graph-convolutional networks.Source: §2 · pp. 3–4
  • For grid shortest paths, graph convolution can represent Bellman-Ford relaxation, and HOUDINI can discover an approximation from data.The synthesized program combines graph convolution and mapping with image-processing and learned relaxation modules.Source: §2 · p. 4

3 Learning Algorithm

HOUDINI alternates type-directed program generation with stochastic gradient descent to train and evaluate candidate programs. For lifelong learning, it adds frozen trained modules to a growing library, allowing the synthesizer to reuse prior knowledge selectively.

3 Learning Algorithm

  • The learner’s GENERATE module proposes programs and TUNE uses stochastic gradient descent; the final program is selected by validation loss.TUNE instantiates candidate parameters, while GENERATE searches the program space.Source: §3 · p. 5
  • Top-down refinement builds programs from partial programs in simplicity order, while an evolutionary strategy uses selection, crossover, and mutation.Both strategies preserve type safety; evolutionary operators replace subterms only with terms of the same type.Source: §3 · p. 5
  • Type constraints greatly reduce search because type-safe programs are a small fraction of programs of a given size.This benefit applies to both program-generation strategies.Source: §3 · p. 5
  • After each task, trained library functions used by the best program are added back with frozen parameters, while fresh untrained functions remain available.The library grows monotonically, preventing later tasks from updating the frozen parameters.Source: §3 · p. 5
  • Because trained and untrained library versions coexist, the synthesizer can choose whether to transfer prior knowledge to a new task.The paper describes this selective transfer as allowing HOUDINI to avoid negative transfer.Source: §3 · p. 5

4 Evaluation

HOUDINI is evaluated on lifelong task sequences combining image recognition with counting, summing, and shortest-path computation. The results report transfer across tasks and domains, graph-task performance, and the effect of typed search and synthesis strategy.

Task Sequences

  • The benchmark sequences distinguish low-level transfer, high-level concept reuse, cross-domain reuse, and longer learning without a favorable curriculum.The study also evaluates graph tasks and sums of digit images; classification uses error, while regression tasks use RMSE.Source: §4 · pp. 6–7

Results: Synthesized programs

  • HOUDINI synthesizes programs for every Figure 3 task within at most 22 minutes, and the GS2 examples include a shortest-path program with RMSE 6.91.For GS2, the reported synthesis times for Tasks 1, 2, and 3 are 0.35s, 1061s, and 1337s, respectively.Source: §4 · p. 7, Figure 4 · p. 7
  • For summing, HOUDINI’s top program maps a learned CNN feature extractor over the image list, then folds the transformed features to produce the sum.The authors report that this program greatly outperforms baselines, including with all training data; the counting and long-sequence evaluations limit the number of evaluated programs to 20, excluding foldl from those programs.Source: §4 · p. 7

Results: Transfer

  • Where transfer is possible, HOUDINI has much lower error than other transfer methods on counting sequences and outperforms baselines under limited-data settings.Across CS2 and CS3, it reuses counting networks across digit classes and from MNIST digits to NORB toy images; similar findings are reported for summing and the longer sequence LS.Source: §4 · pp. 7–8

Task Sequences

  • The CS1 sequence tests selective low-level transfer: HOUDINI reuses the correct digit-recognition module, whereas the low-level-transfer baseline cannot select which prior task to reuse.The evaluation includes recognition tasks followed by counting tasks, with five random instantiations for digit and toy sequences.Source: §4 · pp. 6, 8

Results: Transfer

  • On graph tasks, HOUDINI’s graph-convolutional program has significantly less error than a simple sequence model, a standalone baseline, and its evolutionary version.It also beats low-level transfer except on shortest path street in GS2; the GS2 program reuses a relaxation function learned on shortest path MNIST.Source: §4 · pp. 8–9, Table 2 · p. 9

Results: Typed vs. untyped synthesis

  • Typed synthesis generates far fewer candidate programs than untyped synthesis for CS1, where arity alone leaves too many candidates for manageable search.The evaluation varies target program sizes from 4 to 6.Source: §4 · p. 9, Table 1 · p. 9

Results: Top-Down vs. Evolutionary Synthesis

  • The top-down implementation of GENERATE outperformed the evolutionary implementation overall, while evolutionary search had high variance and often timed out without finding a solution.Timed-out evolutionary runs are excluded from the plots.Source: §4 · p. 9

5 Conclusion

HOUDINI uses symbolic search over differentiable functional programs to select both pretrained neural functions and their architecture. On lifelong tasks combining perception and algorithmic reasoning, it transfers high-level concepts.

5 Conclusion

  • HOUDINI is presented as the first neurosymbolic approach to synthesizing differentiable functional programs.Its symbolic search can select pretrained library functions and the architecture used to combine them.Source: §5 · p. 9
  • Across several lifelong tasks combining perceptual and algorithmic reasoning, HOUDINI accelerates learning by transferring high-level concepts.Source: §5 · p. 9
  • The approach represents deep networks as differentiable programs and uses functional programs to compactly represent popular deep architectures.Source: §5 · p. 9

A Assigning Types to HOUDINI Programs

HOUDINI assigns types to programs from the types of their constituent expressions and combinators. Programs without an assignable type are excluded from synthesis.

A Assigning Types to HOUDINI Programs

B Symbolic Program Synthesis

Symbolic synthesis searches the HOUDINI language for programs, using typed partial programs and neural evaluation. Its top-down and evolutionary procedures explore this program space differently.

B Symbolic Program Synthesis

B.1 Synthesis Using Top-down Iterative Refinement

  • Top-down refinement starts from a typed hole, expands it with grammar productions, and queues type-safe partial programs according to a heuristic that favors simpler programs.Complete programs are sent to the neural module for parameter learning; expansions that fail the hole’s type are rejected.Source: §B.1 · p. 13

B.2 Evolutionary Synthesis

  • Evolutionary synthesis maintains a population of type-safe programs, scores them by tuned loss, then selects, crosses over, and mutates programs.Crossover and mutation exchange or replace subterms only with terms of the same type, preserving type consistency.Source: §B.2 · pp. 13–14

C Details of Experimental Setup

The experiments use task-specific MLP, CNN, or RNN library modules and compare standalone, low-level-transfer, and progressive-network baselines. Training data, sequence lengths, epochs, and early stopping vary by task.

Library architectures

  • MLPs use one 1024-unit hidden layer, CNNs use two convolutional layers, and RNN modules use 100-dimensional LSTMs.Each task's input and output types determine the module family and output activation.Source: C Details of Experimental Setup · p. 14

Baselines

  • The counting standalone baseline composes an MLP, CNN, and RNN in a map-based architecture.For graph tasks, the RNN baseline maps an MLP-CNN regression module over grid images, linearizes the grid row-wise, then processes it with a 100-unit LSTM.Source: C Details of Experimental Setup · p. 14

Data and training

  • List-task training uses lengths 2–5 and tests lengths 6–8 to evaluate generalization to longer sequences.These tasks use 12,000 training and 2,100 test points; list-related tasks train for 20 epochs, while regression tasks train for 1,000.Source: C Details of Experimental Setup · p. 14
  • Shortest-path training uses 3×3 and 4×4 grids, with testing on 5×5 grids.The specified training sets contain 70,000 3×3 grids and 1,000,000 4×4 grids; testing uses 10,000 5×5 grids, with five training epochs.Source: C Details of Experimental Setup · p. 14
  • For GS2 Task 3, low-level transfer requires matching MNIST and GTSRB image dimensions, so both inputs are resized to 28×28×3.The transferred regression function was learned in GS2 Task 1.Source: C Details of Experimental Setup · p. 14

Evaluation

D Programs Discovered in Experiments

The experiments report selected programs and their test errors, while the counting example illustrates how a learned neural module can be reused from the library in a later task.

Program and error reporting

  • Tables 3–24 report the top three programs and test classification errors or RMSE for most task sequences.Programs are ordered by validation performance, and the reported programs were evaluated on all training data.Source: D Programs Discovered in Experiments · p. 14, Table 3 · p. 15
  • In Table 3, CE denotes classification error and RMSE denotes root mean square error.The table covers Counting Sequence 1.Source: Table 3 · p. 15

Program reuse

  • After a task, its trained neural module enters the library and can be reused in subsequent tasks.For CS1 Task 3, the top-performing counting program combines the Task 1 library module with a newly trained module.Source: D Programs Discovered in Experiments · p. 15

E Summing Experiment

In the summing sequence, HOUDINI learns the digit-sum task using a fold operation, whereas standalone, low-level-transfer, and progressive-network methods perform poorly. The figure identifies this experiment as lifelong learning for summing.

Summing Sequence

  • HOUDINI learns the digit-sum function easily with a synthesized program using foldl, while standalone, low-level transfer, and progressive networks perform poorly.The first task, MNIST classification, is solved equally well by all competing methods.Source: E Summing Experiment · p. 15, Figure 6 · p. 15
  • A standalone-with-fold baseline reuses HOUDINI's program but trains its parameter from random initialization.Source: E Summing Experiment · p. 15
  • The sequence is designed to test low-level transfer of a multiclass classifier and the advantage of foldl in this setting.Source: E Summing Experiment · p. 15

F Full Experimental Results on Counting Tasks

The full counting-task results include early and later tasks across several sequences. Early tasks with little relevant transferable information show similar performance across methods.

Full counting-task results

  • On early tasks such as CS1 Tasks 1 and 2, methods perform similarly because little relevant information can be transferred.For these tasks, HOUDINI returns a single library function.Source: F Full Experimental Results on… · p. 15
  • The section presents results for all tasks in the counting sequences, extending beyond the later transfer-capable tasks emphasized in the paper.Source: F Full Experimental Results on… · p. 15
  • Figure 7 depicts lifelong learning for CS1 and is described as demonstrating low-level transfer of perceptual recognizers.Source: Figure 7 · p. 22

G Results on Longer Task Sequence LS

On the longer LS task sequence, HOUDINI performs much better than other methods on regression tasks, where earlier tasks offer transfer opportunities. On classification tasks, all methods perform similarly, with no opportunity to transfer from earlier tasks.

G Results on Longer Task Sequence LS

Related papers

Loading 1804.00218v2…