Learning Differentiable Programs with Admissible Neural Heuristics
Authors: Ameesh Shah, Eric Zhan, Jennifer Sun, Abhinav Verma, Yisong Yue, Swarat Chaudhuri
NeurIPS 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We instantiate our approach, called NEAR (abbreviation for Neural Admissible Relaxation), on top of two informed search algorithms: A and an iteratively deepened depth-first search with branch-and-bound pruning (IDS-BB). We evaluate the algorithms in the task of learning programmatic classifiers in three behavior classification applications. We show that the algorithms substantially outperform state-of-the-art methods for program learning, and can learn classifier programs that bear natural interpretations and are close to neural models in accuracy. |
| Researcher Affiliation | Academia | Ameesh Shah UC Berkeley ameesh@berkeley.edu Eric Zhan ezhan@caltech.edu Jennifer J. Sun jjsun@caltech.edu Abhinav Verma verma@utexas.edu Yisong Yue yyue@caltech.edu Swarat Chaudhuri swarat@cs.utexas.edu |
| Pseudocode | Yes | Algorithm 1: A* Search Input: Graph G with source u0 S := {u0}; f(u0) := 1; while S 6= ; do v := arg minu2S f(u); S := S \ {v}; if v is a goal node then return v, fv; else foreach child u of v do Compute g(u), h(u), f(u); S := S [ {u}; |
| Open Source Code | Yes | Our full implementation is available in [39]. [39] Ameesh Shah, Eric Zhan, and Jennifer Sun. Near code repository. https://github.com/trishullab/near, 2020. |
| Open Datasets | Yes | The CRIM13 dataset [5] contains trajectories for a pair of mice engaging in social behaviors... We use the Aggression and Boy-meets-Boy datasets within the Fly-vs.-Fly environment... [14]. We use a subset of the basketball dataset from [50] that tracks the movements of professional basketball players. |
| Dataset Splits | Yes | in total we have 12404 training, 3077 validation, and 2953 test trajectories. We have 5339 training, 594 validation, and 1048 test trajectories. In total, we have 18,000 trajectories for training, 2801 for validation, and 2693 for test. |
| Hardware Specification | No | Algorithms for each domain were run on the same machine to ensure consistency, and each non-NEAR baseline was set up such to have at least as much time as our NEAR-guided algorithms for their search procedures (see Appendix). The paper mentions 'same machine' but provides no specific hardware details (e.g., CPU/GPU models, memory). |
| Software Dependencies | No | The paper references standard machine learning techniques and provides a link to its implementation on GitHub, but it does not explicitly list specific software dependencies with version numbers within the text. |
| Experiment Setup | Yes | Here, σ is the sigmoid function and β is a temperature hyperparameter. Experiment hyperparameters are included in the appendix. |