Automating the Analysis and Improvement of Dynamic Programming Algorithms with Applications to Natural Language Processing
Embargo until
Date
2023-07-20
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Johns Hopkins University
Abstract
This thesis develops a system for automatically analyzing and improving dynamic programs, such as those that have driven progress in natural language processing and computer science, more generally, for decades. Finding a correct program with the optimal asymptotic runtime can be unintuitive, time-consuming, and error-prone. This thesis aims to automate this laborious process. To this end, we develop an approach based on
(1) a high-level, domain-specific language called Dyna for concisely specifying dynamic programs
(2) a general-purpose solver to efficiently execute these programs
(3) a static analysis system that provides type analysis and worst-case time/space complexity analyses
(4) a rich collection of meaning-preserving transformations to programs, which systematizes the repeated insights of numerous authors when speeding up algorithms in the literature
(5) a search algorithm for identifying a good sequence of transformations that reduce the runtime complexity given an initial, correct program
We show that, in practice, automated search—like the mental search performed by human programmers—can find substantial improvements to the initial program. Empirically, we show that many speed-ups described in the NLP literature could have been discovered automatically by our system. We provide a freely available prototype system at https://github.com/timvieira/dyna-pi
Description
Keywords
program optimization, natural language processing, dynamic programming, semirings, databases, programming language