Paper: A Better N-Best List: Practical Determinization Of Weighted Finite Tree Automata

ACL ID N06-1045
Title A Better N-Best List: Practical Determinization Of Weighted Finite Tree Automata
Venue Human Language Technologies
Session Main Conference
Year 2006
Authors

Ranked lists of output trees from syn- tactic statistical NLP applications fre- quently contain multiple repeated entries. This redundancy leads to misrepresenta- tion of tree weight and reduced informa- tion for debugging and tuning purposes. It is chiefly due to nondeterminism in the weighted automata that produce the re- sults. We introduce an algorithm that de- terminizes such automata while preserv- ing proper weights, returning the sum of the weight of all multiply derived trees. We also demonstrate our algorithm’s ef- fectiveness ontwo large-scale tasks.