1 Introduction
Due to the simplicity and running efficiency, shift-reduce parsing has been studied extensively for a variety of grammars, ranging from constituency parsing (Sagae and Lavie Reference Sagae and Lavie2005, Reference Sagae and Lavie2006; Zhang and Clark Reference Zhang and Clark2009) through dependency parsing (Yamada and Matsumoto Reference Yamada and Matsumoto2003; Nivre Reference Nivre2004; Huang, Jiang and Liu Reference Huang, Jiang and Liu2009b) to Combinatory Categorial Grammar parsing (Zhang and Clark Reference Zhang and Clark2011). In dependency and Combinatory Categorial Grammar parsing, shift-reduce parsing is among the best-performing algorithms (Huang and Sagae Reference Huang and Sagae2010; Zhang and Clark Reference Zhang and Clark2011). However, compared with commonly used statistical parsers, such as the Charniak–Johnson re-ranking parser (Charniak and Johnson Reference Charniak and Johnson2005) and the Berkeley parser (Petrov and Klein Reference Petrov and Klein2007), there still exists room to improve the performance of shift-reduce constituency parsers.
Prior efforts on improving shift-reduce constituency parsing focus on the following two directions. One direction is to design better training and decoding algorithms. For example, in the respect of decoding, Sagae and Lavie (Reference Sagae and Lavie2006) proposed the best-first search strategy to expand the search space. In the respect of training, Zhang and Clark (Reference Zhang and Clark2009) replaced local classifiers with a global learning algorithm. The other direction is to enrich feature representations for better shift-reduce constituency parsing (Sagae and Lavie Reference Sagae and Lavie2005; Sagae and Lavie Reference Sagae and Lavie2006; Wang, Sagae and Mitamura Reference Wang, Sagae and Mitamura2006; Zhang and Clark Reference Zhang and Clark2009). All the previous works listed above discuss shift-reduce parsing in the setting of supervised learning. In this paper we instead focus on semi-supervised shift-reduce constituency parsing, which, to the best of our knowledge, has not been studied before. Specifically, considering that shift-reduce parsers typically take part-of-speech (POS) tagging as a preliminary step and the performance of shift-reduce parsers is heavily dependent on the quality of input POS tags,Footnote 1 we propose a two-stage approach: We first improve POS taggers to supply syntactic parsers with better POS tags and then enrich feature representation of a baseline shift-reduce parser. Both stages improve performance by utilizing large-scale unlabeled data.
In the respect of POS tagging preprocessing, most previous work on shift-reduce parsing simply utilizes off-the-shelf POS taggers. In terms of the performance metric of per-token accuracy, those POS taggers seem difficult to improve further, especially for languages that have been extensively studied, for example English (Manning Reference Manning2011). However, if we go beyond stand-alone POS taggers, we find that parsers such as the Berkeley parser can also be used to assign POS tags (together with parse trees) to sentences. Moreover, POS tags supplied by the parsers give rise to substantially higher shift-reduce parsing accuracy than POS tags coming from state-of-the-art POS taggers (see Section 6.1.1). Although it is practically insignificant to utilize a parser, say the Berkeley parser, to feed POS tags to a shift-reduce parser, we can actually use such parsers to help construct better POS taggers for shift-reduce parsing. Hereafter, parsers that integrate POS tagging and syntactic parsing in a single step are referred to as integrated parser, examples of which include the Berkeley and Bikel parsers (Bikel Reference Bikel2004).Footnote 2 Briefly, our approach to improving POS taggers is to train a stand-alone POS tagger on the output of integrated parsers on large-scale unlabeled data.
To improve shift-reduce parsers, one natural idea is to follow the direction of our approach to POS tagging, that is, to train a shift-reduce parser on the combination of human-labeled training data and auto-parsed data produced by integrated parsers. However, such an approach is extremely time-consuming for shift-reduce parsers that require to parse training sentences repeatedly (the baseline parser used in this paper is one such instance). Thus, the approach proposed in this paper is to mine information from auto-parsed data in an off-line manner and then enrich feature representation based on the obtained information. Specifically, we use the information of lexical head–modifierFootnote 3 relations (also known as lexical dependencies) (Collins Reference Collins1996). Previous work on other constituency parsers has shown the effectiveness of lexical dependency information on disambiguating syntactic structures (Collins Reference Collins1996, Reference Collins1997; Eisner and Satta Reference Eisner and Satta1999). But in shift-reduce constituency parsing such information is not fully used. For instance, Zhang and Clark (Reference Zhang and Clark2009) encoded lexical information as features but ignored dependency information between words. Sagae and Lavie (Reference Sagae and Lavie2005) and Wang et al. (Reference Wang, Sagae and Mitamura2006) only incorporated as features the most recently recognized (left and right) modifiers of some designated words. By contrast, this paper defines features thatexplicitly encode the information of whether words in an input sentence tend to have head–modifier relations. Moreover, we propose to obtain lexical dependency information from large-scale auto-parsed data instead of human-labeled treebank data because lexical dependencies obtained from the latter source suffer from data sparseness (Section 5.2.1). We focus on bigram and trigram lexical dependencies from automatically parsed trees. Based on the extracted lexical dependencies, we design a set of features to enhance the baseline parser.
The two-stage approach described above can be regarded as a variant of the uptraining approach (Petrov et al. Reference Petrov, Chang, Ringgaard and Alshawi2010) where auto-parsed data produced by the Berkeley parser is used as additional training data to improve POS taggers and shift-reduce parsers for dependency parsing. The most significant difference between our work and that of Petrov et al. (Reference Petrov, Chang, Ringgaard and Alshawi2010) lies in the second stage: We do not simply combine auto-parsed data to improve shift-reduce parsing; we instead extract partial information from auto-parsed data. In addition, it is notable that the approach to improving shift-reduce parsing is actually independent of the parsers that are used to generate auto-parsed data. In this paper we choose to utilize the same auto-parsed data as with POS tagging for the purpose of consistency. Experimental results show that our approach can improve shift-reduce constituency parsing to 90.9 percent on English and 82.2 percent on Chinese. In addition, our parser outperforms previously reported shift-reduce constituency parsers while maintaining the efficiency.
The remainder of this paper is organized as follows. Section 2 discusses in detail the related work. In Section 3 we describe the baseline parser and baseline features that are used in this paper. Section 4 presents the approach to improving POS taggers and the shift-reduce baseline parser. Section 5 introduces experimental setup and Section 6 presents the detailed experimental results. Finally, we conclude our work in Section 7.
2 Related work
Semi-supervised approaches to POS tagging have been widely studied. Merialdo (Reference Merialdo1994) attempted to improve a Hidden Markov Model-based tagger with expectation maximization. However, the results that Merialdo (Reference Merialdo1994) have achieved are negative. Wang et al. (Reference Wang, Huang and Harper2007) studied co-training with two distinct POS taggers but their approach seems to achieve positive results only when human-labeled training set is small in size. More recently, alternative methods based on system combination were proposed. Suzuki and Isozaki (Reference Suzuki and Isozaki2008) proposed an extension of semi-supervised conditional random fields by combining supervised and unsupervised probability models. Søgaard (Reference Søgaard2010) studied system combination in a tri-training framework. Clark, Curran and Osborne (Reference Clark, Curran and Osborne2003) adopted the self-training approach and achieved positive results only when human-labeled data are limited. Huang, Eidelman, and Harper (Reference Huang, Eidelman and Harper2009a) reported positive results using self-training of a hidden Markov model POS tagger. Unlike the previous work, this paper adopts the uptraining approach which improves stand-alone POS taggers with the aid of integrated POS taggers. The uptraining approach was first proposed in Petrov et al. (Reference Petrov, Chang, Ringgaard and Alshawi2010), where the Berkeley parser was used to improve dependency parsers in a target domain. In this paper we adapt the approach to in-domain POS tagging.
Shift-reduce parsing has been widely studied due to its simplicity and efficiency. For constituency parsing, Sagae and Lavie (Reference Sagae and Lavie2005) proposed a classifier-based shift-reduce parser which was extended with the best-first search strategy in Sagae and Lavie (Reference Sagae and Lavie2006). Wang et al. (Reference Wang, Sagae and Mitamura2006) adapted the parser in Sagae and Lavie (Reference Sagae and Lavie2005) to Chinese parsing and compared some representative classifiers. Zhang and Clark (Reference Zhang and Clark2009) proposed a global learning algorithm to replace local classifiers. Shift-reduce parsing was also widely applied to parsing with other grammars (Nivre Reference Nivre2004; Huang et al. Reference Huang, Jiang and Liu2009b; Huang and Sagae Reference Huang and Sagae2010; Zhang and Clark Reference Zhang and Clark2011). In this paper we focus on constituency parsing, especially on improving Zhang and Clark (Reference Zhang and Clark2009) with a semi-supervised approach. To the best of our knowledge, semi-supervised shift-reduce constituency parsing has not been studied before. In this respect, self-training (and its variant, the uptraining approach) is the most successful approach (McClosky, Charniak and Johnson Reference McClosky, Charniak and Johnson2006; Huang and Harper Reference Huang and Harper2009; Huang, Harper and Petrov Reference Petrov2010; Petrov et al. Reference Petrov, Chang, Ringgaard and Alshawi2010). The difference between self-training and our approach is that we use partial information derived from auto-parsed data instead of entire automatically parsed trees. Chen et al. (Reference Chen, Kazama, Uchimoto and Torisawa2012a) and Noord (Reference Noord2007) exploited lexical dependencies from unlabeled data for dependency and Head-driven Phrase Structure Grammar parsing respectively. In this paper we for the first time use lexical dependency information for advancing state-of-the-art shift-reduce constituency parsers. It is worth emphasizing that although we follow the approach of Chen et al. (Reference Chen, Kazama, Uchimoto and Torisawa2012a) for lexical dependency extraction, new features proposed in this paper are different from the features proposed in Chen et al. (Reference Chen, Kazama, Uchimoto and Torisawa2012a) because lexical dependencies are used for different parsers. Specifically, Chen et al. (Reference Chen, Kazama, Uchimoto and Torisawa2012a) aims to improve a graph-based dependency parser whereas this paper focuses on a transition-based constituency parser.
3 Baseline parser
The baseline parser used in this paper is the beam-search shift-reduce parser (Zhang and Clark Reference Zhang and Clark2009). To our knowledge, this parser achieves the best performance among all the shift-reduce constituency parsers that have been reported before.
3.1 The shift-reduce parsing process
The shift-reduce process in the baseline parser assumes binary-branching trees, so binarization and debinarization are required for transforming training data and parsing output respectively (Zhang and Clark Reference Zhang and Clark2009). Given an input sentence (words and POS tags), any possible parse tree yielding the sentence corresponds exactly to one sequence of states. Formally, each state in the sequence is denoted by a tuple 〈S, Q〉, where S is a stack containing partial parses that have been recognized and Q is a queue of word-POS pairs that remain unprocessed. In particular, the initial state is 〈φ, w 1 . . . wn〉, where S is empty and Q contains the entire input sentence. The final state is 〈S, φ〉, where S contains a single parse tree with a pre-designated root label and Q is empty. Thus, the shift-reduce parsing process is a transition process from the initial state to the final state by performing a sequence of the following actions:
• shift, which moves a pair of word and POS tag from the head of the queue to the stack. Here the queue is required to be non-empty.
• reduce-unary-X, which extends the top item on the stack by applying a unary rule and then replaces the top item with the newly generated constituent. Here X represents a treebank phrase label, such as NP, which is to be used as the root label of the new constituent.
• reduce-binary-{L/R}-X, which moves top two items out of the stack and pushes a new item onto the stack. The new item has X as its root label and consists of two children with the first popped item becoming the right child and the second popped item becoming the left child. The switch L/R indicates whether the left (L) or the right (R) child becomes the head child.
• terminate, which pops the root node off the stack and ends parsing. This action is applicable only when the stack contains a single parse and the queue is empty.
3.2 Beam-search extension
The shift-reduce parsing process described above can be extended with beam search, as presented in Algorithm 1. The algorithm starts by initializing a beam of size K with the initial state. In each iteration after the initialization, states are popped in turn out of the beam. For each popped state, all applicable actions are then evaluated with respect to the state. Scored action-state pairs are sorted in a temporary priority queue. When the beam gets empty, the top K highest scored action-state pairs are fetched from the priority queue and next states corresponding to the action-state pairs are inserted back into the beam. If the highest scored state in the beam is a final state, it will be returned as the parsing result; else the iteration continues. The algorithm has a time complexity of O(nK), where n is the sentence length and K is the beam width.
Beam-search shift-reduce parsing
3.3 Model and learning algorithm
To score an action A with respect to a state Y=〈S, Q〉, we use a linear model as defined by
\begin{equation}
Score(\langle A, Y \rangle) = \overrightarrow{w} \cdot \Phi (\langle A, Y \rangle) = \sum _i \lambda _i f_i(\langle A, Y \rangle)
\end{equation}
Generalized perceptron is an online learning algorithm that learns one instance at a time. The basic procedure is to use the beam-search parsing algorithm (Algorithm 1) to parse the yield of a gold parse tree. Whenever the gold partial parse is pruned from the beam, parameters will be updated immediately and the learner moves to the next training instance. Such a strategy is known as ‘early-update’ (Collins and Roark Reference Collins and Roark2004). Finally, model parameters are set to be an average of the weight vectors obtained during online learning.
3.4 Baseline features
Features used in the baseline parser are similar to those used in Zhang and Clark (Reference Zhang and Clark2009). For convenience of reference, we repeat the features in Table 1, where the symbol Si represents the ith item from the top of the stack S and the symbol Qi denotes the ith item from the front end of the queue Q. The symbol w represents the lexical head for an item; c represents the label for an item; and t denotes POS of a lexical head. Note that Zhang and Clak (Reference Zhang and Clark2009) also used bracket-related and separator features for Chinese parsing, which have been removed in the latest release of their parser. So in this paper we choose to ignore such language-specific features.
A summary of baseline feature templates, where Si represents the ith item in stack S and Qi denotes the ith item in queue Q from the front end
4 Our approach to better POS tagging and syntactic parsing
4.1 Uptraining of POS taggers
The uptraining approach to improving a POS tagger proceeds in the following two steps. The corresponding pipeline is depicted in Figure 1.
• Build an integrated parser on human-labeled training data and then use the parser to automatically process unlabeled data. This way we get a set of auto-tagged data.
• Merge human-labeled training data and auto-tagged data to get a data set on which we train a POS tagger.
The pipeline for uptraining of stand-alone POS taggers.
It is noteworthy that although the focus of this paper is on shift-reduce parsing, the uptraining approach to improving POS taggers can benefit other parsers that take POS tagging as a pre-processing step, e.g. the chunking-based parser (Tsuruoka, Tsujii and Ananiadou Reference Tsuruoka, Tsujii and Ananiadou2009). Moreover, our approach requires labeled parse trees be available for training integrated parsers. Such a requirement seems to be a severe limitation at first sight. But it is not a real problem since we restrict our discussion of improving POS taggers in the context of syntactic parsing.
The uptraining approach described above is very similar to the ideas of standard self-training (Clark et al. Reference Clark, Curran and Osborne2003), with the difference that we use an integrated parser rather than a POS tagger to assign POS tags to unlabeled data. In addition, our approach aims to improve POS taggers for better syntactic parsing rather than higher POS tagging accuracy. In this sense, the approach has a philosophy similar to targeted self-training (Katz-Brown et al. Reference Katz-Brown, Petrov, McDonald, Och, Talbot, Ichikawa, Seno and Kazawa2011).
4.2 Enriching feature representation of shift-reduce parsing
4.2.1 Motivation
We first empirically analyze major sources of shift-reduce parsing errors with the parsing results of the baseline parser on the English development set. The baseline parser and a POS tagger are trained on the same human-labeled training data. Regarding the parsing results, we are especially concerned with first mistakes that the baseline parser makes because future mistakes are often caused by previous ones. There are 944 first mistakes in total in the parsing results. Table 2 shows the types and ratios of the top five most frequent first mistakes. Cases 1–2 consist of conflicts between shift and reduce actions. Case 3 comprises conflicts between reduce-binary and reduce-unary actions. Mistakes in cases 4–5 are caused by wrong choices of labels, where the symbols X, X1, and X2 refer to treebank phrase labels, and the symbol X* denotes a temporary label introduced when a constituent with label X is binarized. We note in Table 2 that action conflicts between shift and reduce-binary are the largest source of parsing errors, which cover nearly half of first mistakes.
Types and ratios of first mistakes made by the baseline parser on the English development set
Intuitively, lexical dependency information is beneficial to resolving shift and reduce-binary conflicts. In the following, we use a real example to make clear the intuition. Figure 2 illustrates the shift-reduce parsing process of the baseline parser on a sentence with auto-assigned POS tags. The baseline parser proceeds correctly until it reaches the state in Figure 2(a). At that point, there is a conflict between reduce-binary (Figure 2(b)) and shift (Figure 2(c)) actions. We find that the baseline parser wrongly chooses the reduce-binary action because the word bore is (incorrectly) tagged as a verb.Footnote 4 The baseline parser tends to group the words preceding a verb as a constituent. However, if the parser is informed that the words a and bore have a lexical dependency relationship, the parser may correct its choice and switch to the shift action. In addition, we find that the human-labeled data used to train the baseline parser do not contain lexical dependencies between a and bore. We can see that extracting lexical dependencies solely from human-labeled training data has a data sparseness problem. This motivates us to utilize unlabeled data as an additional source for lexical dependency extraction.
An example of shift-reduce conflicts illustrating how lexical dependency information helps to disambiguate the conflicts.
4.2.2 Data preprocessing
We propose to extract lexical dependencies from auto-parsed data. In principle, any parser, including the baseline parser of this paper, can be used to process unlabeled data to obtain automatically parsed trees. However, since we have produced large-scale auto-parsed in the POS tagging step by using integrated parsers, we will continue to use the same set of auto-parsed data. To simplify the extraction process, we convert automatically parsed constituency trees into dependency trees with Penn2Malt (or other conversion tools).Footnote 5 Given an input sentence x, we denote by y a dependency tree for x, and by H(y) a set that includes the words that have at least one dependent. For each xh∈H(y), we have a dependency structure Dh = (xLk . . ., x L1, xh, x R1 . . . xRm), where xLk . . . x L1 and x R1 . . . xRm are dependents of the head xh. Either k and m may be zero.
4.2.3 Extraction of lexical dependencies
After the conversion from constituency trees to dependency trees, the following lexical dependencies are read off from resulting dependency trees.
Bigram lexical dependencies: If two words are connected by an arc in a dependency tree, we claim these two words maintain a bigram lexical dependency. For pairs of words that have dependencies, we make a record of the words as well as their head–modifier relations. Formally, bigram lexical dependencies are denoted as 〈w 1, w 2, L/R〉, where L/R indicates the direction of the dependency arc that connects w 1 and w 2. Moreover, lexical dependencies are word-order sensitive, that is, 〈w 1, w 2, L〉 is regarded to be different from 〈w 2, w 1, R〉. Bigram lexical dependencies extracted from a dependency structure Dh can be represented as 〈xLi, xh, R〉 and 〈xh, xRi, L〉.
Trigram lexical dependencies: Trigram lexical dependencies encode a head–modifier relationship among three words. As with bigram lexical dependencies, trigram lexical dependencies are also word-order sensitive. Although there exist distinct types of trigram lexical dependencies (Koo and Collins Reference Koo and Collins2010), in this paper we only consider the type of trigram lexical dependency that has the first or the last word be the head and that requires the other two words to be siblings among all the modifiers of the head. Note that the two sibling modifiers are not necessary to be continuous in sentences. Among the types of trigram lexical dependencies we have experimented, this type is the only one that achieves positive effect on parsing accuracy. Such lexical dependencies can be represented formally as 〈w 1, w 2, w 3, L/R〉. Here the switch L/R indicates the head among the three words. Specifically, the symbol L specifies w 1 to be the head and the symbol R designates w 3 to be the head. In addition, we also consider the special case that w 2 is NONE, which indicates that w 1 (w 3) is the rightmost (leftmost) modifier of w 3 (w 1). Trigram lexical dependencies extracted from a dependency structure Dh can be represented as 〈xLi, x Li−1, xh, R〉 and 〈xh, x Ri−1, xRi, L〉.
4.2.4 Proposed features
After extracting all lexical dependencies, we group bigram and trigram lexical dependencies separately into three categories according to their frequencies. Specifically, if a dependency relation is among top-10 percent most frequent records, then it receives the group tag high frequency (HF); if it is in top-20 percent, then we use the tag Middle Frequency (MF); else we use the tag Low Frequency (LF). Formally, the group strategy can be described as follows:
\begin{equation*}
GR(r) = \left\lbrace \begin{array}{l@{\quad}l}HF & \textnormal {if}\ r \in {top\text{-}10\text{percent}} \\
MF & \textnormal {else if}\ r \in {top\text{-}20\text{percent}}\\
LF & \textnormal {otherwise} \end{array} \right.
\end{equation*}
Based on the bigram and trigram lexical dependency lists, we propose a set of dependency features which is described in detail in the following. Here si denotes the ith item from the top of the stack S, and qi is the ith item from the front end of the queue Q. In addition, siw (sit) refers to the head word (POS) of si and qiw (qit) refers to the word (POS) of qi.
Bigram dependency features: Bigram dependency features have a generic form of f L/R(w 1, w 2), which returns a group tag (HF, MF, or LF) if the lexical dependency 〈w 1, w 2, L/R〉 is found in the bigram lexical dependency list; else it returns NULL. The above feature template is instantiated into three pairs of features: {fL(s 1w, s 0w), fR(s 1w, s 0w)}, {fL(s 0w, q 0w), fR(s 0w, q 0w)}, and {fL(s 1w, q 0w), fR(s 1w, q 0w)}.
We also combine the above features with POS tags of w 1 and w 2. Thus, we have three more pairs of features in the generic form of f L/R(w 1, w 2)○t(w 1)○t(w 2), where t(wi) represents the POS tag of the word wi. All the bigram dependency features are listed in Table 3.
New features designed on the basis of lexical dependencies. Here the symbol w represents a word and the symbol t represents a POS tag
Trigram dependency features: Trigram dependency features have the generic form of f L/R(w 1, w 2, w 3). In this paper this feature template is instantiated into two pairs of features. The feature function fL(s 1w, s 1rdw, s 0w) returns a group tag if 〈s 1w, s 1rdw, s 0w, L〉 is found in the trigram lexical dependency list, where s 1rdw denotes the rightmost modifier of s 1w that has been recognized so far during the shift-reduce parsing process. Note that s 1rdw might be NONE if no right modifiers have been recognized for s 1w. The other trigram dependency features, fR(s 1w, s 0ldw, s 0w), fL(s 0w, s 0rdw, q 0w), and fR(s 0w, NONE, q 0w), can be explained in a similar way. As with bigram dependency features, POS tags are combined with the above features to obtain richer feature representations. Trigram dependency features used in the paper are summarized in Table 3.
4.2.5 Parsing with proposed features
To use the proposed dependency features, we only need to update the scoring function defined in (1) (Section 2.3). The new scoring function is shown in the following:
\begin{equation}
Score^\prime (\langle A, Y \rangle) = \sum _i \lambda _i f_i(\langle A, Y \rangle) + \sum _j\lambda ^d_j f^d_j
\end{equation}
5 Experimental setup
5.1 Data preparation
For English experiments, our labeled data came from the Wall Street Journal (WSJ) corpus of the Penn Treebank (Marcus, Santorini and Marcinkiewiz Reference Marcus, Santorini and Marcinkiewiz1993). Following the divisions adopted in Charniak and Johnson (Reference Charniak and Johnson2005), we used sections 2–21 as training data, section 24 for system development, and section 23 for performance evaluation. In terms of English unlabeled data, we used the TIPSTER corpus (LDC93T3A), which contains news articles from various sources, although we only used Wall Street Journal articles.
For Chinese experiments, we used Chinese Treebank (CTB) version 5.1 (Xue et al. 2005) as labeled data. Specifically, articles 001–270 and 440–1151 were used as training data, articles 271–300 were used for evaluation, and articles 301–325 were used for development data. In respect of Chinese unlabeled data, we utilized the corpus of Chinese Gigaword (LDC2003T09) after some basic cleanups.
We conducted necessary preprocessing on English and Chinese unlabeled data before they were used. Specifically, we applied OpenNLP for English sentence boundary detection and tokenization.Footnote 6 For the Chinese unlabeled data, we retained sentences that come from the body of documents, and then conducted sentence boundary detection simply according to sentence ending punctuations, including Chinese full stops, exclamation marks, and question marks. In addition, raw sentences were automatically segmented with a Conditional Random Field-based word segmenter, which achieves a segmentation accuracy of 97.2 percent on the testing data of CTB 5.1.
Table 4 contains detailed statistics of all the data used in the experiments.
Data statistics, including the number of words and sentences, together with average sentence length.* The numbers are approximate due to the use of automatic preprocessing techniques
5.2 POS taggers and integrated parsers
In principle, a shift-reduce parser can be pipelined with any POS taggers. In this paper we adopted representative POS taggers for English and Chinese experiments respectively. Specifically, for English experiments, LAPOS (Tsuruoka, Miyao and Kazama Reference Tsuruoka, Miyao and Kazama2011) was applied which has the trait of looking ahead to POS tags to the right of the prediction position. Hereafter, the LAPOS POS tagger is referred to as POS-LAPOS. For experiments on Chinese data, we applied the Stanford POS tagger (Toutanova et al. Reference Toutanova, Klein, Manning and Singer2003). Hereafter, we refer to this POS tagger simply as POS-Stanford.
With respect to integrated parsers, we used the Berkeley parser as well as the emulation of Collins parsing model 2 (Collins Reference Collins1999) in the Bikel parser. The parsers represent two important research directions in the field of constituency paring: unlexicalized PCFG with latent annotations, and lexicalized PCFG respectively. Moreover, these two parsers have distinct performance levels in POS tagging and syntactic parsing. Thus, we can empirically study the effect of performance of integrated parsers on the results of our approach. In the experiments of POS tagging, the POS tagging components in the Berkeley and Bikel parsers are regarded as a kind of POS taggers (called integrated POS tagger) and are referred to as POS-Berkeley and POS-Bikel respectively. In contrast, tagging systems, such as POS-LAPOS and POS-Stanford, are named as stand-alone POS taggers or simply as POS taggers.
5.3 Performance scoring
We measured tagging accuracy of POS taggers with per-token accuracy, which is defined to be the ratio of correctly tagged words over all the words in a test set. For performance evaluation of syntactic parsing, we used EVALB to provide bracket scoring as well as complete match scoring.Footnote 7 For significance tests, we adopted the comparator to compute p-value.Footnote 8 When we use significance testing to compare two results, we run compare.pl five times and then report the average of the obtained five p-values.
5.4 Running parameters
We set the beam size of the shift-reduce parser to 16 in both training and decoding phases which maintains a good trade-off between parsing efficiency and accuracy (Zhang and Clark Reference Zhang and Clark2009). With respect to the iteration number of perceptron learning, we tuned the parameter on the development sets and finally set the value to twenty-one for both English and Chinese experiments. In the respect of stand-alone POS taggers and integrated parsers, we used default parameter settings.
6 Experimental results
6.1 Improved POS tagging
We compared our approach to POS tagging with other representative approaches. POS taggers that were experimented are summarized in the following:
1. Supervised training: It trains POS taggers solely on human-labeled training data. Specifically, we trained POS-LAPOS (POS-Stanford) on human-labeled English (Chinese) training data and obtained a POS tagger named Base-LAPOS (Base-Stanford). The integrated POS taggers, POS-Berkeley and POS-Bikel, were applied to both English and Chinese POS tagging. We always refer to the resulting POS taggers as Base-Berkeley and Base-Bikel regardless of the specific language.
2. Standard self-training: It applies a base POS tagger to process unlabeled data and retrain the POS tagger on the combination of human-labeled training data and automatically tagged data. For English and Chinese POS tagging, Base-LAPOS and Base-Stanford are used as the base tagger respectively. The resulting self-trained taggers are referred to as Self-LAPOS and Self-Stanford.
3. Uptraining: It trains POS-LAPOS on the combination of labeled training data and auto-labeled POS data generated by Base-Berkeley (Base-Bikel) on unlabeled data. The resulting tagger is referred to as Berkeley-LAPOS (Bikel-LAPOS). For Chinese POS tagging, we replaced POS-LAPOS with POS-Stanford and the resulting Chinese POS taggers are referred to as Berkeley-Stanford and Bikel-Stanford.
When merging human-labeled data and auto-tagged data in the data combination, we simply gave our human-labeled training data a relative weight of one.
6.1.1 Stand-alone POS tagger versus integrated POS tagger
Table 5 shows the comparative results of stand-alone and integrated POS taggers in the setting of supervised learning. We evaluated POS taggers on the English and Chinese test sets by using the metrics of per-token accuracy as well as parsing accuracy of the baseline parser. As the results show, the integrated POS taggers achieve lower per-token accuracy than the stand-alone POS tagger does on the English test set, but they generate POS tags that result in higher parsing F1-scores (≥ 0.7 percent). On Chinese data, the integrated POS taggers also provide better POS tags for syntactic parsing. In this sense, we can infer that integrated POS taggers are ‘better’ than stand-alone taggers. The reason is that integrated POS taggers use syntactic information as high-level constraints during assigning POS tags. So it is feasible to utilize an integrated POS tagger to improve a stand-alone POS tagger for better syntactic parsing.
Comparative results between stand-alone and integrated POS taggers on section 23 of the WSJ corpus and the CTB 5.1 test set
6.1.2 Uptraining versus self-training
Table 6 shows the results of Berkeley-LAPOS (uptraining) and Self-LAPOS (self-training) on the English development set. This experiment serves the following two purposes: (1) To demonstrate the advantage of uptraining over standard self-training in improving POS taggers for better syntactic parsing, and (2) to show the effect of different sizes of auto-tagged data that are used in uptraining. From the results we can see that the self-training approach has trivial effect on both POS tagging and parsing accuracy. Such results coincide with previous work on self-training for POS tagging (Clark et al. Reference Clark, Curran and Osborne2003). On the contrary, the uptraining approach achieves substantial improvements on parsing accuracy. Specifically, after 500k auto-tagged sentences are added, the approach improves parsing accuracy by 0.4 percent. We also decide the optimal size of auto-tagged sentences to be 1,500k because it achieves the highest parsing score when parsing scores are accurate to two decimal places. On the other hand, we note that uptraining with auto-tagged data causes POS tagging accuracy to regress. One major cause lies in tagging errors contained in auto-tagged data. In Section 6.1.4 we will analyze the reason why the uptraining approach improves parsing accuracy but degrades POS tagging accuracy.
Comparative results between uptraining (Berkeley-LAPOS) and standard self-training (Self-LAPOS) on section 24 of the WSJ corpus
A similar experiment was conducted on the Chinese development set by using the POS taggers Berkeley-Stanford and Self-Stanford. The results are shown in Table 7. We can see that the uptraining approach improves parsing accuracy substantially by 0.9 percent, and it also outperforms the self-training approach. In addition, Berkeley-Stanford achieves the highest paring accuracy when 500k auto-tagged sentences are added.
Comparative results between uptraining (Berkeley-Stanford) and standard self-training (Self-Stanford) on the CTB 5.1 development set
6.1.3 POS tagging results on testing data
Table 8 presents the results of the uptraining approach on the English and Chinese test sets. We used 1,500k and 500k auto-tagged sentences for English and Chinese experiments respectively. Moreover, we compared two different integrated POS taggers: POS-Berkeley and POS-Bikel. From the English results we can see that uptraining with POS-Berkeley improves parsing accuracy by 0.7 percent in F1-score (from 89.4 to 90.1 percent; significant at the level of p<10−3). Moreover, although POS-Bikel has lower tagging and parsing accuracy than POS-Berkeley, uptraining with POS-Bikel also achieves an improvement of 0.6 percent (from 89.4 to 90.0 percent; significant at the level of p<10−3). Given that the improvement is close to that achieved by POS-Berkeley, the property that the parsers integrate POS tagging and syntactic parsing together seems to be more important than the accuracy of the parsers.
Final results of uptraining of POS tagging on section 23 of the WSJ corpus and the CTB 5.1 test set
In contrast to experimental results on English, the uptraining approach achieves bigger improvements on Chinese (≥ 1.0 percent; significant at the level of p<10−3). One possible reason is that the Chinese baseline POS tagger (Base-Stanford) has more room left for further performance improvements than the English baseline POS tagger (Base-LAPOS).
6.1.4 Additional analysis
The results on the testing data show that the uptraining approach either decreases per-token accuracy or only achieves trivial improvements in per-token accuracy. However, the approach benefits syntactic parsing consistently. It is of interest to examine the reasons for such a phenomenon. To this end, we took Chinese POS tagging as a case study and compared the results of uptraining with 500k auto-tagged sentences with the results of the baseline POS tagger. The comparative results are shown in Table 9, where the row labels are correct POS tags and the column labels represent automatically assigned POS tags. For example, the numbers [NN, VV] = 57/36 in the table refer to the frequency that words of POS tag NN were incorrectly assigned to VV: the number 57 preceding the backslash is the result of uptraining, while the number 36 behind the backslash is the result of the baseline POS tagger.
Confusion matrix of POS tagging results on the CTB 5.1 test set
From the results we can see that Chinese POS tagging has severe errors between the following POS: NN–VV, DEC–DEG, NN–JJ, and NN–NR. The uptraining approach has different effect on the POS pairs. Specifically, the approach has positive effect on disambiguating NN–VV and DEG–DEC but has negative effect on disambiguating NN–NR and NN–JJ. These POS have distinct effect on subsequent parsing accuracy. To simplify the analysis, we chose from the test set the sentences that have only one POS modification caused by the uptraining approach. Among the seventy-eight sentences that have been picked up, twenty-five sentences contain alternations between NN and NR. Among the twenty-five sentences, we found that parsing accuracy of thirteen sentences remained unchanged; parsing accuracy on five sentences was improved; and parsing accuracy on seven sentences was decreased. In contrast, nineteen sentences of the seventy-eight sentences contain alternations between NN and VV, among which parsing accuracy on fourteen sentences is increased, while parsing accuracy on the other five sentences is decreased. We can see that, for the subsequent syntactic parsing task, the errors between NN and VV have more serious effect than the errors between NN and NR. The uptraining approach is able to reduce POS tagging errors that have significant effect on subsequent syntactic parsing.
6.2 Improved shift-reduce parsing
This section is devoted to showing the effectiveness of our approach to improving the baseline shift-reduce parser. To simplify the discussion, the results presented in this section are based on the baseline POS taggers, i.e. Base-LAPOS and Base-Stanford.
6.2.1 Comparison of different sources
Table 10 shows comparative results on English and Chinese development sets with lexical dependencies obtained from different sources. We experimented with four different settings: no lexical dependency information was used (Baseline), lexical dependencies were solely from human-labeled training data (Human-Labeled), lexical dependencies were solely from auto-parsed data (Auto-Parsed), and lexical dependencies were from the combination of human-labeled and auto-parsed data (Combined). For the latter three settings, all the dependency features listed in Table 3 were incorporated. In the data combination, we simply gave our human-labeled training data a relative weight of one. Note that in this and the following experiments, auto-parsed data were produced on the whole sets of unlabeled data.
Comparative results on English and Chinese development sets with lexical dependencies extracted from diverse sources
From the results we can see that although lexical dependency information from human-labeled training data can improve the performance on both English and Chinese, the improvement on Chinese is moderate (0.1 percent in F1-score). One reason is that lexical dependencies from human-labeled training data have a sparseness problem. In contrast, the use of large-scale auto-parsed data brings on much bigger improvements (0.8 percent F1-score on English and 1.1 percent F1-score on Chinese). In addition, we find that data combination has trivial effect on performance. One possible reason is that lexical dependencies from human-labeled training data are overwhelmed by those from auto-parsed data. We will leave further discussions on data combination to our future work and focus on the setting of obtaining lexical dependencies from auto-parsed data.
6.2.2 Effect of different features
Table 11 shows the results on the English test set, where the two types of dependency features were added incrementally to the baseline parser. As the results show, both bigram and trigram dependency features have positive effect on the parsing accuracy. Specifically, on the whole test set the overall improvement over the baseline parser is 0.9 percent in F1-score, where bigram dependency features contribute an absolute 0.6 percent improvement and trigram dependency features further improve the performance by 0.3 percent over the results of using bigram dependency features. Significance tests show that the overall improvement on the whole test set is statistically significant on the level of p<10−4.
Main results on section 23 of the WSJ corpus using POS tags automatically assigned by Base-LAPOS and lexical dependencies extracted from auto-parsed data. Two types of dependency features are added incrementally
In parallel to the results on the English test set, Table 12 shows the results on the Chinese test set, using auto-assigned POS tags and lexical dependencies extracted from auto-parsed data. From the results on the whole test set we can see that dependency features contribute a bigger absolute improvement on Chinese than that on English (1.1 percent versus 0.9 percent). One possible reason is that the size of Chinese unlabeled data used in the paper is much bigger. Significance tests show that the overall improvement induced by bigram and trigram dependency features on the whole test is statistically significant on the level of p<10−3. These results indicate that the new features are very effective.
Main results on the CTB 5.1 test set using POS tags automatically assigned by Base-Stanford and lexical dependencies extracted from auto-parsed data. Two types of dependency features are added incrementally
6.2.3 Additional analysis
We performed several types of analysis, focusing on English, to investigate the effect of different sizes of human-labeled training data and auto-parsed data, as well as how lexical dependency information changes the distribution of first mistakes made by the baseline parser.
Effect of different sizes of labeled and unlabeled Data: We studied the effect of varying sizes of human-labeled training data by randomly sampling from sections 2–21. Meanwhile, we always used the whole set of auto-parsed data. The results are depicted in Figure 3(a). As the results show, auto-parsed data improve parsing accuracy even when the human-labeled training data are small in size. In addition, by using our approach, a fraction of sections 2–21 plus the whole set of auto-parsed data is sufficient to achieve the F1-scores obtained by the parser trained solely on the whole sections 2–21.
Results with varying sizes of human-labeled training data and unlabeled data.
We also examined the effect of varying sizes of unlabeled data. In this experiment, we used sections 2–21 as human-labeled training data and changed the size of unlabeled data through random sampling. The results are depicted in Figure 3(b). From the results we can see that improvements achieved by using unlabeled data are enlarged with the increment of the size of unlabeled data until the performance finally levels off.
Reduction on first mistakes: The baseline parser made 1,522 first mistakes on the English test set. We analyzed how our approach changed the first mistakes. We grouped the changes into four cases. No-Change (1,090) refers to the case that the baseline and our parser make the same first mistakes at the same positions. In the case of Correct (249), first mistakes made by the baseline parser are corrected by our parser. Wrong (121) means that our parser makes first mistakes earlier than the baseline parser. Finally, Others (47) refers to the case that our parser and the baseline parser make first mistakes of different types at the same positions. In addition, we are especially interested in how our approach reduces first mistakes of the type shift versus reduce-binary. So we compared the numbers of the first mistakes of this type in the Correct and Wrong cases, which are 168 and 78 respectively.
6.3 Final results
We combined the efforts on improving POS tagging and shift-reduce parsing, and obtained the final results on the English and Chinese test sets. Table 13 shows the comparison of our parser with a large body of representative related work. Here all the related work except Ratnaparkhi (Reference Ratnaparkhi1997), Sagae and Lavie (Reference Sagae and Lavie2005), Sagae and Lavie (Reference Sagae and Lavie2006), and Carreras, Collins and Koo (Reference Carreras, Collins and Koo2008) utilized integrated POS taggers. With regard to the exceptions, Ratnaparkhi (Reference Ratnaparkhi1997) adopted a Maximum Entropy-based POS tagger (Ratnaparkhi Reference Ratnaparkhi1996); Sagae and Laive (Reference Sagae and Lavie2005) and Sagae and Lavie (Reference Sagae and Lavie2006) used SVMTool whose tagging accuracy on section 23 of the WSJ corpus is 97.1 percent;Footnote 9 Carreras et al. (Reference Carreras, Collins and Koo2008) took as input the POS tags assigned by the Collins parser (Collins Reference Collins1997). For fair comparison, here we disregarded parsers that are based on combination methods such as Petrov (Reference Petrov2010) and Zhang et al. (Reference Zhang, Zhang, Tan and Li2009). Following the taxonomy adopted in Huang et al. (Reference Huang, Harper and Petrov2010), we grouped the related work into single parsers (SINGLE), discriminative reranking approaches (RE), and self-training (SELF). Note that self-trained parsers in the table were built on distinct sets of unlabeled data. Specifically, McClosky et al. (Reference McClosky, Charniak and Johnson2006) made use of 2,000k sentences from the North American News Text corpus, NANC (Graff Reference Graff1995); Huang and Harper (Reference Huang and Harper2009) sampled 210k sentences from the BLLIP corpus; Huang et al. (Reference Huang, Harper and Petrov2010) partitioned 1,769,055 BLLIP sentences into ten equally sized subsets and used a single subset to achieve accuracy in Table 13. From the results we can see that our parser outperforms all the single parsers listed in the table except Carreras et al. (Reference Carreras, Collins and Koo2008). However, compared with Carreras et al. (Reference Carreras, Collins and Koo2008), our parser has much smaller time-complexity: O(nK) versus O(n 3G), where K is the beam size used in our parser and G is the grammar constant in Carreras et al. (Reference Carreras, Collins and Koo2008). Compared with reranking and self-training parsers, our parser has relatively low parsing accuracy. But the reranking and self-training techniques are actually complementary with our approach, so we might enhance our parser with these techniques in the future.
Comparison with related work on section 23 of the WSJ corpus with POS tags automatically assigned by Berkeley-LAPOS.* The parsers are based on shift-reduce parsing.† The results are of self-training with a single latent annotation grammar
Comparing Chinese constituency parsers is difficult in the sense that previously reported results were achieved frequently on different versions of CTB and/or with different data split standards. Zhang and Clark (Reference Zhang and Clark2009) presented a detailed comparison between the baseline parser of this paper and a large body of related work on CTB 2.0. Here we only compared our parser with the parsers available on the web for Chinese parsing, as shown in Table 14. From the results we can see that on Chinese parsing our parser outperforms Bikel (Reference Bikel2004) and Charniak (Reference Charniak2000) by 1.6 percent and 1.4 percent respectively. However, our parser lags behind Petrov and Klein (Reference Petrov and Klein2007) and the reranking parser (Charniak and Johnson Reference Charniak and Johnson2005).
Comparison with related work on the test set of CTB 5.1 with POS tags automatically assigned by Berkeley-Stanford.* Huang (Reference Huang2009) adapted the parsers to Chinese parsing on CTB 5.1.† We run the parser on CTB 5.1 to get the results
Table 15 shows the comparison of running time between our parser and the single parsers listed in Table 13. For completeness, we also measured the running time of the baseline parser. This experiment was conducted on an Intel processor of 2.93 GHz and 8 GB memory. From the comparison we can see that incorporating lexical dependency features incurs additional running overhead (by comparing the running time of our parser and the baseline parser), but our parser still has an obvious advantage over other parsers. It should be noted that the running time of the classifier-based Sagae–Laive parsers (Sagae and Lavie Reference Sagae and Lavie2005, Reference Sagae and Lavie2006) was evaluated on different hardware, which is much longer than the running time of our parsers. However, we note that time complexity of the parsers of Sagae and Lavie (Reference Sagae and Lavie2005) is linear, smaller than that of our parsers (O(n) versus O(kn)). The long running time of Sagae and Lavie (Reference Sagae and Lavie2005) in Table 15 is largely attributed to the use of support vector machines. Sagae and Laive (Reference Sagae and Lavie2006) reported the running time of a Maximum Entropy-based Implementation of Sagae and Lavie (Reference Sagae and Lavie2005), which is less then 1 min, close to the running time of our parsers. Taking into consideration the tradeoff between parsing accuracy and running speed, our parser is a suitable choice for practical applications on massive data, for example parsing the whole web.
Comparison of running time on section 23 of the WSJ corpus where the time for loading models is excluded.* The results of SVM-based shift-reduce parsing are with greedy search.† The results of MaxEnt-based shift-reduce parser are with best-first search.‡ Time is reported by authors by running on different hardware
7 Conclusion and future work
We have presented a semi-supervised approach to improving shift-reduce constituency parsing from two aspects. In respect of POS tagging, we enhanced POS taggers targeted at syntactic parsing by using auto-tagged POS data produced by integrated parsers; in respect of shift-reduce parsing, lexical dependency information extracted from auto-parsed data was utilized, based on which a set of new features was proposed and integrated into the shift-reduce parser. Our approach succeeded to construct POS taggers that can provide better POS tags for syntactic parsing and well addressed the action conflict problem. We evaluated the approach on English and Chinese data. The results show that our new parsers provide comparable accuracies with state-of-the-art parsers while maintaining the advantage in parsing speed.
There are many ways in which this research can be continued. First, we are concerned with the generalization of lexical dependencies. To this end, we propose to combine POS with words to obtain generalized dependencies. We can also use semantic classes of words to generalize dependencies. Second, we will experiment the shift-reduce parser proposed in this paper for bitext parsing (Zhao et al. Reference Zhao, Song, Kit and Zhou2009; Chen et al. Reference Chen, Kazama, Zhang, Tsuruoka, Zhang, Wang, Torisawa and Li2012b). In bitext parsing, bilingual information can be used as additional information to further improve shift-reduce parsing. Intuitively, bilingual information and dependency information are complementary in disambiguating shift-reduce actions. All these will be conducted in our future work.
Acknowledgments
This work was supported in part by the National Science Foundation of China (61073140; 61272376; 61100089), Specialized Research Fund for the Doctoral Program of Higher Education (20100042110031), and the Fundamental Research Funds for the Central Universities (N110404012; N100204002).
