- 70 views
- 55 downloads
NeuroSketcher: Synthesizing Non-Differentiable Programs with Non-Differentiable Loss Functions
-
- Author / Creator
- Emireddy, Thirupathi Reddy
-
Programmatic hypotheses offer valuable properties, such as generalizability and interpretability. However, such hypotheses can be elusive, as one finds them by searching over large spaces of programs. Recent work showed that neural networks can be used to guide the search in the programmatic space by filling in the “holes” of the program sketches considered in the search. Despite its promising results, this approach requires that the synthesized programs and the loss function be differentiable, which can severely limit its use in practice. In this dissertation, we overcome this weakness with a two-step search. The first search uses an abstraction of the original language where non differentiable operations of the language are replaced with neural networks, thus resulting in a language of differentiable programs. The second search, which is not neural-guided, completes the promising sketches generated in the first search by searching in the original language space while optimizing for any loss function, including non-differentiable ones. We use our approach to synthesize programmatic heuristic functions for two permutation sorting problems: the Pancake and the Topspin puzzles. Our method discovered heuristic functions for the Pancake and Topspin puzzles that outperform some of the best known heuristics for these domains. Due to their programmatic representation, we can prove that search algorithms using our heuristic functions are guaranteed to find bounded-suboptimal solutions.
-
- Subjects / Keywords
-
- Graduation date
- Fall 2023
-
- Type of Item
- Thesis
-
- Degree
- Master of Science
-
- License
- This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.