RobustFill: Neural Program Learning under Noisy I/O

Abstract

The problem of automatically generating a computer program from some specification has been studied since the early days of AI. Recently, two competing approaches for automatic program learning have received significant attention: (1) neural program synthesis, where a neural network is conditioned on input/output (I/O) examples and learns to generate a program, and (2) neural program induction, where a neural network generates new outputs directly using a latent program representation. Here, for the first time, we directly compare both approaches on a large-scale, real-world learning task. We additionally contrast to rule-based program synthesis, which uses hand-crafted semantics to guide the program generation. Our neural models use a modified attention RNN to allow encoding of variable-sized sets of I/O pairs. Our best synthesis model achieves 92% accuracy on a real-world test set, compared to the 34% accuracy of the previous best neural synthesis approach. The synthesis model also outperforms a comparable induction model on this task, but we more importantly demonstrate that the strength of each approach is highly dependent on the evaluation metric and end-user application. Finally, we show that we can train our neural models to remain very robust to the type of noise expected in real-world data (e.g., typos), while a highly-engineered rule-based system fails entirely.

8 pages + 9 pages of supplementary material

References in corpus (10)

• Neural Machine Translation by Jointly Learning to Align and Translate
• Show, Attend and Tell: Neural Image Caption Generation with Visual Attention
• Grammar as a Foreign Language
• Learning to Execute
• Neural GPUs Learn Algorithms
• Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets
• Neural Turing Machines
• Neuro-Symbolic Program Synthesis
• TerpreT: A Probabilistic Programming Language for Program Induction
• Neural Random-Access Machines

Cited by in corpus (53)

• Competition-Level Code Generation with AlphaCode
• Learning to Infer and Execute 3D Shape Programs
• A Benchmark for Systematic Generalization in Grounded Language Understanding
• Learning Compositional Rules via Neural Program Synthesis
• Program Synthesis with Large Language Models
• TF-Coder: Program Synthesis for Tensor Manipulations
• Write, Execute, Assess: Program Synthesis with a REPL
• Learning Compositional Neural Programs with Recursive Tree Search and Planning
• Learning to Represent Programs with Property Signatures
• Show Your Work: Scratchpads for Intermediate Computation with Language Models
• ProTo: Program-Guided Transformer for Program-Guided Tasks
• Neural-Guided Symbolic Regression with Asymptotic Constraints
• SPoC: Search-based Pseudocode to Code
• Learning to Synthesize Programs as Interpretable and Generalizable Policies
• Neural Inverse Knitting: From Images to Manufacturing Instructions
• Imitation-Projected Programmatic Reinforcement Learning
• Neutaint: Efficient Dynamic Taint Analysis with Neural Networks
• Latent Programmer: Discrete Latent Codes for Program Synthesis
• Guiding High-Performance SAT Solvers with Unsat-Core Predictions
• Learning Task-General Representations with Generative Neuro-Symbolic Modeling
• BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration
• Neural Learning of One-of-Many Solutions for Combinatorial Problems in Structured Output Spaces
• Programmable Agents
• Learning to learn generative programs with Memoised Wake-Sleep
• Program Synthesis Guided Reinforcement Learning for Partially Observed Environments
• Robot Action Selection Learning via Layered Dimension Informed Program Synthesis
• Learning Fitness Functions for Machine Programming
• Intelligence, physics and information -- the tradeoff between accuracy and simplicity in machine learning
• Program Synthesis with Best-First Bottom-Up Search
• Data Generation for Neural Programming by Example
• Fixed Points in Cyber Space: Rethinking Optimal Evasion Attacks in the Age of AI-NIDS
• Benchmarking Multimodal Regex Synthesis with Complex Structures
• Towards Modular Algorithm Induction
• Adaptive Correlated Monte Carlo for Contextual Categorical Sequence Generation
• Gradient Descent over Metagrammars for Syntax-Guided Synthesis
• Data-Driven Synthesis of Provably Sound Side Channel Analyses
• PLANS: Robust Program Learning from Neurally Inferred Specifications
• Learning Execution through Neural Code Fusion
• Optimal Neural Program Synthesis from Multimodal Specifications
• Hierarchical Variational Imitation Learning of Control Programs
• Program Synthesis Over Noisy Data with Guarantees
• Learning Discrete Energy-based Models via Auxiliary-variable Local Exploration
• Type-driven Neural Programming by Example
• Biological Blueprints for Next Generation AI Systems
• Learning to Combine Per-Example Solutions for Neural Program Synthesis
• Inductive Program Synthesis over Noisy Datasets using Abstraction Refinement Based Optimization
• Latent Execution for Neural Program Synthesis
• Neural Program Generation Modulo Static Analysis
• Occam Learning Meets Synthesis Through Unification
• On Adversarial Robustness of Synthetic Code Generation
• Grammar Filtering For Syntax-Guided Synthesis
• Program Synthesis from Visual Specification
• Formal Fields: A Framework to Automate Code Generation Across Domains