Literature
Display
← All papers

Neurally-Guided Structure Inference

Sidi Lu · Jiayuan Mao · Joshua B. Tenenbaum · Jiajun Wu

· ICML 2019 ↗

Reasoning7 min text · CondensedOriginal paper ↗
Contents

At a glance

NG-SI uses a neural network to choose grammar rules within a recursive structure-inference procedure. Expert-designed algorithms then decompose the input so the same inference routine can operate on each component. The goal is to avoid evaluating every rule without requiring a neural network to predict an entire deep structure at once.

Experiments cover probabilistic matrix decomposition and parsing a synthetic programming language. The method is faster than the tested search baselines and generalizes better than the tested neural sequence/tree baselines to deeper structures. Its performance still depends on the supplied grammar, decomposition procedures, training distribution, and rule-selection accuracy.

1. Introduction

Many data structures can be expressed by composing a small set of primitives. Exhaustively evaluating candidate structures is expensive, while directly predicting a whole structure can fail outside the training complexity range. NG-SI places learned guidance at each local expansion, preserving the recursive organization of search. Figure 1 contrasts the three approaches.

figure 1
Figure 1. The illustrative flowcharts for (a) search-based algorithms, (b) data-driven algorithms, and (c) the proposed NG-SI. NG-SI uses a neural network (a data-driven module) to guide a hierarchical, layer-wise search process. It outperforms search-based and data-driven alternatives in both inference robustness and efficiency.

2. Structure inference

Structure inference jointly seeks an explanatory structure and the parameters associated with it. The paper assumes that a domain-specific grammar and primitive operations are already available.

2.1. Problem formulation

A matrix can, for example, have low-rank structure whose factors themselves exhibit clustering. The grammar expresses such nested structure; terminals describe primitives and production rules combine them. Figure 2 retains the numerical decomposition example.

The task is inference within a supplied language. The algorithm does not discover the language’s primitives or production rules from scratch.

figure 2
Figure 2. An example of the hierarchical matrix decomposition.

2.2. Prior work

Earlier work spans explicit search, amortized neural prediction, and learned search guidance. The proposed distinction is amortizing rule selection at each level while retaining expert-defined recursive decomposition.

Data-driven structure inference

Sequence, tree, and program-prediction models learn mappings from labeled examples. They amortize inference but can struggle when test sequences are longer or structures are deeper than training examples. This motivates reusing a local predictor recursively.

3. Neurally-guided structure inference

Algorithm 1 recursively selects a rule, decomposes the input into components corresponding to its nonterminal symbols, and invokes itself on each component. A neural guider implements rule selection. The displayed algorithm is greedy; beam-search extensions are possible but are not the pseudocode shown.

Recursion permits reusing known rules at greater depth. It does not guarantee that the neural guider chooses correctly on arbitrary inputs, or that a greedy choice recovers the globally best structure.

Function Infer(D, Type):
    rule ← SelectRule(D, Type)
    for each non-terminal symbol s in rule do
        C_s ← DecomposeData(D, rule, s)
        Replace s in rule with Infer(C_s, s)
    return rule

4. Matrix decomposition

The first application reuses a probabilistic matrix grammar to infer combinations of low rank, clustering, temporal structure, binary factors, and Gaussian scale mixtures.

4.1. Problem formulation

The start symbol G represents an independent Gaussian matrix. Other primitives include multinomial cluster labels M, binary factors B, and cumulative matrices C. Production rules combine these into richer distributions; for example, MG + G describes cluster centers plus Gaussian noise. Table 1 retains the complete grammar, including transpose and elementwise-product notation.

table 1
Table 1. Production rules in the context-free DSL for structure inference. The left-most column indicates the type of the production rules.

4.2. Method

A convolutional guider recognizes the local pattern associated with each candidate rule. The existing symbolic algorithms fit the selected decomposition, and the existing variational score ranks candidate structures. Thus the speedup concerns choosing and evaluating rules within an inherited inference framework.

Neural guider

The guider predicts local refinements such as low-rank products, row or column clustering, temporal structure, binary factors, or Gaussian scale mixtures. It is trained on rule labels, rather than on complete arbitrarily deep matrix structures.

Training

Training matrices are synthesized online: sample a grammar rule, sample its component matrices, compose them, and use the chosen rule as the target. After training, the guider is fixed during structure inference.

Hyperparameters

Inputs are described as zero-padded to 200×200 with a second channel marking valid entries. The model trains for 100,000 iterations with batch size 100 and Adam at learning rate 0.0001; the reported decay parameters are both 0.9.

The main text calls the guider eight-layer, while the complete supplementary table lists nine convolutional operations. The original architecture is retained so this discrepancy remains visible.

4.3. Experiments

Synthetic evaluation uses ten matrix structures with 200×200 observations and hidden dimension 10. Real-data examples use walking-motion measurements and natural-image patches, with search depths up to three. The real datasets have no ground-truth structure.

Baselines

The search comparison is the inherited matrix-inference procedure [15]. The learned baseline, Mat2Seq, uses a convolutional encoder and recurrent decoder to generate a full structure, trained on the same synthetic data as the local guider. This design makes extrapolation from local-rule training a central part of the comparison.

Accuracy

NG-SI recovers eight of the ten tested synthetic structures. It confuses dependent Gaussian scale mixtures with sparse coding, a limitation shared with the variational ranking score, and fails on the linear dynamical-system case. The authors attribute the latter partly to imbalanced training for temporally dependent rules.

On real data, inferred structures mostly agree with the search baseline but can vary across seeds or fall back to simpler structures. Agreement is evidence of consistency with that baseline, not proof of a correct latent structure. Table 2 preserves all reported outcomes across three runs, including disagreements.

table 2
Table 2. Search results of our approach and several baselines. We denote exp(f(G)) ◦G as s(f(G)). We run each model for three times with different random seeds. If the results produced by three runs disagree, we include all possible outcomes in the table, separated by / . See the main text for a detailed analysis.
figure 3
Figure 3. We compare the running time for structure inference of (Grosse et al., 2012) and NG-SI. For all experiments, we set the standard deviation for the input noise to 1. Remarkably, the speed of NG-SI is 3× ∼39× faster than the baseline.

Efficiency

Across the synthetic structures, reported speedups are 3–39×. On a dependent scale-mixture example, depth-one/two/three searches take 2, 12, and 43 minutes versus 16, 92, and 337 minutes for the search baseline, or about 8× faster. Table 3 retains the machine specification and each depth’s timing.

table 3
Table 3. Running time needed for the search of structures of different depths. Our algorithm consistently outperforms the baseline in efficiency. We ran all experiments on a machine with an Intel Xeon E5645 CPU and a GTX 1080 Ti GPU.

Rule similarity discovery

The guider’s average classification probabilities show confusion between structurally related rules, such as clustering and binary factors. Figure 4 preserves the matrix and colored highlights. This is an empirical pattern in learned predictions, rather than a formal metric proving semantic similarity.

figure 4
Figure 4. Visualization of the similarities between production rules for expanding a “G” node. The similarities are implicitly learned by our neural guider. We manually highlight some entries indicating pairs of similar production rules. Red squares: Clustering vs. Binary factor; blue squares: Binary factor vs. Markov Chain; green squares: Clustering (mixture of Gaussian) vs. Gaussian.

4.4. Inspecting GANs

An exploratory example probes intermediate features of a multilayer generative adversarial network trained to produce dependent scale-mixture data. The inferred structures tend to become more elaborate across layers. Table 4 preserves the architecture and alternative inferred structures.

The generator uses a 128-dimensional Gaussian input and 256-dimensional hidden layers, trained for 10,000 generator updates with four discriminator updates per step. This demonstration suggests an interpretive tool; it does not establish that inferred structures uniquely identify how a general GAN computes.

table 4
Table 4. The architecture and the discovered structures from the intermediate features of an MLP-GAN’s generator. We run this experiment multiple times and show the top-ranked structures for each layer.

5. Program parsing

The second application maps programs in a synthetic WHILE language into abstract syntax trees. It tests whether learned local rule selection can extrapolate to longer programs and deeper compositions.

5.1. Problem formulation

The supplied grammar contains 73 rules covering arithmetic, assignment, conditions, and loops. The input is a program string and the target is its syntax tree. Figure 5 keeps the example program and tree together. This evaluates parsing a known formal language, not discovering program semantics from execution alone.

figure 5
Figure 5. A sample code in the WHILE language (left) and its corresponding AST (right).

5.2. Model

A 256-dimensional unidirectional gated recurrent unit encodes the current code string. A linear classifier predicts its top-level rule; hand-coded procedures split the string into the required components, which are parsed recursively. These decomposition routines are important supplied structure.

Training

Programs are generated from the grammar, and every subtree’s corresponding substring becomes a training example. Training limits tree depth to below nine and uses short programs. The task description says length below 15, while the later curriculum description ends at 15; the paper does not reconcile that boundary wording.

Hyperparameters

The parser trains with batch size 64 and Adam at learning rate 0.0001, with both reported decay parameters 0.9. A curriculum increases program length and depth, beginning at length 5 and ending at 15; the full curriculum is repeated three times.

5.3. Experiments

Evaluation varies syntax-tree depth from 6 to 11 and program length from 15 to 30. Very deep trees have a minimum possible length, so not every grid combination is valid.

Baselines

Seq2Seq predicts a preorder serialization of the syntax tree; Seq2Tree expands a tree top-down. Both use attention and 256-dimensional recurrent encoders. Teacher forcing and matching optimizer settings train the neural baselines. An additional search baseline uses iterative-deepening depth-first enumeration until it finds a tree reproducing the input.

Results

NG-SI retains high parsing accuracy across the tested deeper and longer programs, while both neural baselines deteriorate sharply outside training lengths. Figure 6 retains all six depth panels and their individual failure points. The paper’s broad claim of robustness to arbitrary complexity goes beyond this finite test grid.

All three neural methods run in under one second per instance. At fixed depth six, exhaustive search is exact for programs of length at most 24 but exceeds the one-hour limit for longer programs on the reported single-threaded machine.

figure 6
Figure 6. The performance of NG-SI and the baselines (Seq2Seq and Seq2Tree) on test programs with different AST depths (6 to 11) and different lengths (15 to 30). Deep programs (depth ≥10) have a minimal length larger than 15: Figure 6(e) and Figure 6(f)

6. Conclusion

Neural local-rule selection can substantially reduce a structured search’s cost while keeping useful compositional generalization. The evidence covers two supplied grammars and relies on hand-designed decomposition procedures. Incorrect local decisions, distribution imbalance, noisy data, and imperfect ranking scores remain failure modes.

Acknowledgments

The authors thank Xinyun Chen and acknowledge support from the Center for Brains, Minds and Machines, US research funding, and Facebook.

Supplement: neural-guider architecture

The complete supplementary architecture table is retained, including padding, all nine convolutional operations, two normalization stages, flattening, and the final classifier.

Supplementary network architecture table
Supplementary Table 1. Network architecture of the CNN-based neural guider.
Concept demonstration

Open image ↗