Show simple item record

dc.contributor.author
Vieira, Tim
dc.contributor.author
Cotterell, Ryan
dc.contributor.author
Eisner, Jason
dc.contributor.editor
Moens, Marie-Francine
dc.contributor.editor
Huang, Xuanjing
dc.contributor.editor
Specia, Lucia
dc.contributor.editor
Yih, Scott Wen-tau
dc.date.accessioned
2022-06-15T12:44:41Z
dc.date.available
2021-12-06T19:29:41Z
dc.date.available
2021-12-07T13:53:54Z
dc.date.available
2022-06-15T12:44:41Z
dc.date.issued
2021-11
dc.identifier.isbn
978-1-955917-10-0
en_US
dc.identifier.other
10.18653/v1/2021.findings-emnlp.322
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/518987
dc.identifier.doi
10.3929/ethz-b-000518987
dc.description.abstract
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 speed-ups described in the NLP literature could have been discovered automatically by our system.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Association for Computational Linguistics
en_US
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
dc.title
Searching for More Efficient Dynamic Programs
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 4.0 International
ethz.book.title
Findings of the Association for Computational Linguistics: EMNLP 2021
en_US
ethz.pages.start
3812
en_US
ethz.pages.end
3830
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
2021 Conference on Empirical Methods in Natural Language Processing (EMNLP 2021)
en_US
ethz.event.location
Punta Cana, Dominican Republic
en_US
ethz.event.date
November 7-11, 2021
en_US
ethz.publication.place
Stroudsburg, PA
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02661 - Institut für Maschinelles Lernen / Institute for Machine Learning::09682 - Cotterell, Ryan / Cotterell, Ryan
en_US
ethz.date.deposited
2021-12-06T19:29:47Z
ethz.source
BATCH
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2021-12-07T13:54:00Z
ethz.rosetta.lastUpdated
2022-03-29T16:28:55Z
ethz.rosetta.exportRequired
true
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Searching%20for%20More%20Efficient%20Dynamic%20Programs&rft.date=2021-11&rft.spage=3812&rft.epage=3830&rft.au=Vieira,%20Tim&Cotterell,%20Ryan&Eisner,%20Jason&rft.isbn=978-1-955917-10-0&rft.genre=proceeding&rft_id=info:doi/10.18653/v1/2021.findings-emnlp.322&rft.btitle=Findings%20of%20the%20Association%20for%20Computational%20Linguistics:%20EMNLP%202021
 Search print copy at ETH Library

Files in this item

Thumbnail

Publication type

Show simple item record