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

Proceedings of the Human Language Technology Conference of the North American Chapter of the ACL, pages 351–358, New York, June 2006. c⃝2006 Association for Computational Linguistics A Better -Best List: Practical Determinization of Weighted Finite Tree Automata Jonathan May Information Sciences Institute University of Southern California Marina del Rey, CA 90292 jonmay@isi.edu Kevin Knight Information Sciences Institute University of Southern California Marina del Rey, CA 90292 knight@isi.edu Abstract 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 on two large-scale tasks. 1 Introduction A useful tool in natural language processing tasks such as translation, speech recognition, parsing, etc., is the ranked list of results. Modern systems typ- ically produce competing partial results internally and return only the top-scoring complete result to the user. They are, however, also capable of pro- ducing lists of runners-up, and such lists have many practical uses: The lists may be inspected to determine the quality of runners-up and motivate model changes. The lists may be re-ranked with extra knowledge sources that are difficult to ap- ply during the main search. The lists may be used with annotation and a tuning process, such as in (Collins and Roark, 2004), to iteratively alter feature weights and improve results. Figure 1 shows the best 10 English translation parse trees obtained from a syntax-based translation system based on (Galley, et. al., 2004). Notice that the same tree occurs multiple times in this list. This repetition is quite characteristic of the output of ranked lists. It occurs because many systems, such as the ones proposed by (Bod, 1992), (Galley, et. al., 2004), and (Langkilde and Knight, 1998) represent their result space in terms of weighted partial results of various sizes that may be assembled in multiple ways. There is in general more than one way to as- semble the partial results to derive the same com- plete result. Thus, the -best list of results is really an -best list of derivations. When list-based tasks, such as the ones mentioned above, take as input the top results for some con- stant , the effect of repetition on these tasks is dele- terious. A list with many repetitions suffers from a lack of useful information, hampering diagnostics. Repeated results prevent alternatives that would be highly ranked in a secondary reranking system from even being considered. And a list of fewer unique trees than expected can cause overfitting when this list is used to tune. Furthermore, the actual weight of obtaining any particular tree is split among its repeti- tions, distorting the actual relative weights between trees. (Mohri, 1997) encountered …

Content truncated to 500 words