Searching for More Efficient Dynamic Programs
This work addresses the time-consuming and error-prone process of optimizing algorithms for researchers and practitioners in natural language processing, though it is incremental as it builds on existing transformation techniques.
The paper tackles the problem of manually optimizing dynamic programming algorithms for combinatorial problems in computational linguistics, such as parsing, by automating the search for more efficient programs through semantics-preserving transformations. The result is a system that can automatically discover substantial speed-ups, empirically matching many improvements described in the NLP literature.
Computational models of human language often involve combinatorial problems. For instance, a probabilistic parser may marginalize over exponentially many trees to make predictions. Algorithms for such problems often employ dynamic programming and are not always unique. Finding one with optimal asymptotic runtime can be unintuitive, time-consuming, and error-prone. Our work aims to automate this laborious process. Given an initial correct declarative program, we search for a sequence of semantics-preserving transformations to improve its running time as much as possible. To this end, we describe a set of program transformations, a simple metric for assessing the efficiency of a transformed program, and a heuristic search procedure to improve this metric. 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 common speed-ups described in the NLP literature could have been discovered automatically by our system.