With efficient approximate decoding, perceptron training on the whole Treebank becomes practical, which can be done in about a day even with a Python implementation.

This result confirms that our feature set design is appropriate, and the averaged perceptron learner is a reasonable candidate for reranking.

We use the development set to determine the optimal number of iterations for averaged perceptron , and report the F1 score on the test set.

column is for feature extraction, and training column shows the number of perceptron iterations that achieved best results on the dev set, and average time per iteration.

3.1 Generic Reranking with the Perceptron

In this work we use the averaged perceptron algorithm (Collins, 2002) since it is an online algorithm much simpler and orders of magnitude faster than Boosting and MaxEnt methods.

Shown in Pseudocode l, the perceptron algorithm makes several passes over the whole training data, and in each iteration, for each sentence 3,, it tries to predict a best parse 3),- among the candidates cand(si) using the current weight setting.

his parser, and Wenbin Jiang for guidance on perceptron averaging.

We trained the parsers using the averaged perceptron (Freund and Schapire, 1999; Collins, 2002), which represents a balance between strong performance and fast training times.

of iterations of perceptron training, we performed up to 30 iterations and chose the iteration which optimized accuracy on the development set.

12Due to the sparsity of the perceptron updates, however, only a small fraction of the possible features were active in our trained models.

For this reason we choose as a ranking algorithm the Perceptron which is both accurate and efficient and can be trained with online protocols.

Specifically, we implement the ranking Perceptron proposed by Shen and J oshi (2005), which reduces the ranking problem to a binary classification problem.

For regularization purposes, we use as a final model the average of all Perceptron models posited