9 papers
An Exploration of Left-Corner Transformations
Andreas Opedal, Eleftheria Tsipidi, Tiago Pimentel +2
The left-corner transformation (Rosenkrantz and Lewis, 1970) is used to remove left recursion from context-free grammars, which is an important step towards making the grammar pars…
Exact Paired-Permutation Testing for Structured Test Statistics
Ran Zmigrod, Tim Vieira, Ryan Cotterell
Significance testing -- especially the paired-permutation test -- has played a vital role in developing NLP systems to provide confidence that the difference in performance between…
Searching for More Efficient Dynamic Programs
Tim Vieira, Ryan Cotterell, Jason Eisner
Computational models of human language often involve combinatorial problems. For instance, a probabilistic parser may marginalize over exponentially many trees to make predictions.…
On Finding the -best Non-projective Dependency Trees
Ran Zmigrod, Tim Vieira, Ryan Cotterell
The connection between the maximum spanning tree in a directed graph and the best dependency tree of a sentence has been exploited by the NLP community. However, for many dependenc…
Evaluation of Logic Programs with Built-Ins and Aggregation: A Calculus for Bag Relations
Matthew Francis-Landau, Tim Vieira, Jason Eisner
We present a scheme for translating logic programs, which may use aggregation and arithmetic, into algebraic expressions that denote bag relations over ground terms of the Herbrand…
Please Mind the Root: Decoding Arborescences for Dependency Parsing
Ran Zmigrod, Tim Vieira, Ryan Cotterell
The connection between dependency trees and spanning trees is exploited by the NLP community to train and to decode graph-based dependency parsers. However, the NLP literature has…