An SVM-based voting algorithm with application to parse reranking

An SVM Based Voting Algorithm with Application to Parse Reranking Libin Shen and Aravind K. Joshi Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104, USA {libin,joshi}@linc.cis.upenn.edu Abstract This paper introduces a novel Support Vec- tor Machines (SVMs) based voting algorithm for reranking, which provides a way to solve the sequential models indirectly. We have presented a risk formulation under the PAC framework for this voting algorithm. We have applied this algorithm to the parse reranking problem, and achieved labeled recall and pre- cision of 89.4%/89.8% on WSJ section 23 of Penn Treebank. 1 Introduction Support Vector Machines (SVMs) have been successfully used in many machine learning tasks. Unlike the error- driven algorithms, SVMs search for the hyperplane that separates a set of training samples that contain two dis- tinct classes and maximizes the margin between these two classes. The ability to maximize the margin is be- lieved to be the reason for SVMs’ superiority over other classifiers. In addition, SVMs can achieve high perfor- mance even with input data of high dimensional feature space, especially because of the use of the ”kernel trick”. However, the incorporation of SVMs into sequential models remains a problem. An obvious reason is that the output of an SVM is the distance to the separating hyperplane, but not a probability. A possible solution to this problem is to map SVMs’ results into probabili- ties through a Sigmoid function, and use Viterbi search to combine those probabilities (Platt, 1999). However, this approach conflicts with SVMs’ purpose of achieving the so-called global optimization1. First, this approach may constrain SVMs to local features because of the left- to-right scanning strategy. Furthermore, like other non- generative Markov models, it suffers from the so-called 1By global we mean the use of quadratic optimization in margin maximization. label bias problem, which means that the transitions leav- ing a given state compete only against each other, rather than against all other transitions in the model (Lafferty et al., 2001). Intuitively, it is the local normalization that results in the label bias problem. One way of using discriminative machine learning al- gorithms in sequential models is to rerank the n-best out- puts of a generative system. Reranking uses global fea- tures as well as local features, and does not make lo- cal normalization. If the output set is large enough, the reranking approach may help to alleviate the impact of the label bias problem, because the victim parses (i.e. those parses which get penalized due to the label bias problem) will have a chance to take part in the rerank- ing. In recent years, reranking techniques have been suc- cessfully applied to the so-called history-based models (Black et al., 1993), especially to parsing (Collins, 2000; Collins and Duffy, 2002). In a history-based model, the current decision depends on the decisions made previ- ously. Therefore, we may regard parsing as a special form of sequential model without losing generality. Collins (2000) has proposed two reranking algorithms to rerank the output …

Content truncated to 500 words