text: We introduce precision-biased parsing: a parsing task which favors precision over recall by allowing the parser to abstain from decisions deemed uncertain. We focus on dependency-parsing and present an ensemble method which is capable of assigning parents to 84 of the text tokens while being over 96 accurate on these tokens. We use the precision-biased parsing task to solve the related high-quality parse-selection task: finding a subset of high-quality (accurate) trees in a large collection of parsed text. We present a method for choosing over a third of the input trees while keeping unlabeled dependency parsing accuracy of 97 on these trees. We also present a method which is not based on an ensemble but rather on directly predicting the risk associated with individual parser decisions. In addition to its efficiency, this method demonstrates that a parsing system can provide reasonable estimates of confidence in its predictions without relying on ensembles or aggregate corpus counts.
  @cite_13: We describe a parsing approach that makes use of the perceptron algorithm, in conjunction with dynamic programming methods, to recover full constituent-based parse trees. The formalism allows a rich set of parse-tree features, including PCFG-based features, bigram and trigram dependency features, and surface features. A severe challenge in applying such an approach to full syntactic parsing is the efficiency of the parsing algorithms involved. We show that efficient training is feasible, using a Tree Adjoining Grammar (TAG) based parsing formalism. A lower-order dependency parsing model is used to restrict the search space of the full model, thereby making it efficient. Experiments on the Penn WSJ treebank show that the model achieves state-of-the-art performance, for both constituent and dependency accuracy.
  @cite_10: A notable gap in research on statistical dependency parsing is a proper conditional probability distribution over nonprojective dependency trees for a given sentence. We exploit the Matrix Tree Theorem (Tutte, 1984) to derive an algorithm that efficiently sums the scores of all nonprojective trees in a sentence, permitting the definition of a conditional log-linear model over trees. While discriminative methods, such as those presented in (2005b), obtain very high accuracy on standard dependency parsing tasks and can be trained and applied without marginalization, “summing trees” permits some alternative techniques of interest. Using the summing algorithm, we present competitive experimental results on four nonprojective languages, for maximum conditional likelihood estimation, minimum Bayes-risk parsing, and hidden variable training.
summary: In contrast, we are primarily interested in selecting high-quality edges rather than complete parses. We view parse-selection as an extension of the precision-biased parsing task, and perform parse-selection based on the number of risky attachment decisions. Our assessment of the riskiness or reliability of a particular decision is not based on aggregate corpus counts nor on global features of the input sentence (though such kinds of information may be integrated in the future). In our first method, we adopt a committee-based approach, but apply it primarily for edge-selection. In the second method we present below, we investigate features which may help the parser assess edge riskiness. We note that the marginal edge probabilities obtained from a log-linear parsing model as in @cite_10 are not reliable predictors of edge riskiness: indeed, the pruning procedure used in @cite_13 consider edges with marginal scores of up to @math of the highest scoring edge as possible candidates in order to ensure sufficient coverage, indicating that such models may greatly overestimate the marginals of incorrect edges, while underestimating the marginal values of correct edges.