Character-Level Chinese Dependency Parsing

The arc-standard model has been applied to joint segmentation, POS-tagging and dependency parsing [11], but with pseudo word structures. For unified processing of annotated word structures and fair comparison between character-level arc-eager and arc-standard systems, we define a different arc-standard transition system, consistent with our character-level arc-eager system.

In the word-based arc-standard model, the transition state includes a stack and a queue, where the stack contains a sequence of partially-parsed dependency trees, and the queue consists of unprocessed input words. Four actions are defined for state transition, including arc-left (AL, which creates a left arc between the top element $s_0$ and the second top element $s_1$ on the stack), arc-right (AR, which creates a right arc between $s_0$ and $s_1$), pop-root (PR, which defines the root node of a dependency tree when there is only one element on the stack and no element in the queue), and the last shift (SH, which shifts the first element $q_0$ of the queue onto the stack).

For character-level dependency parsing, there are two types of dependencies: inter-word dependencies and intra-word dependencies. To parse them with both character and word features, we extend the original transition actions into two categories, for inter-word dependencies and intra-word dependencies, respectively. The actions for inter-word dependencies include inter-word arc-left (${\text{AL}}_{\text{w}}$), inter-word arc-right (${\text{AR}}_{\text{w}}$), pop-root (PR) and inter-word shift (${\text{SH}}_{\text{w}}$). Their definitions are the same as the word-based model, with one exception that the inter-word shift operation has a parameter denoting the POS-tag of the incoming word, so that POS disambiguation is performed by the ${\text{SH}}_{\text{w}}$ action.

The actions for intra-word dependencies include intra-word arc-left (${\text{AL}}_{\text{c}}$), intra-word arc-right (${\text{AR}}_{\text{c}}$), pop-word (PW) and inter-word shift (${\text{SH}}_{\text{c}}$). The definitions of ${\text{AL}}_{\text{c}}$, ${\text{AR}}_{\text{c}}$ and ${\text{SH}}_{\text{c}}$ are the same as the word-based arc-standard model, while PW changes the top element on the stack into a full-word node, which can only take inter-word dependencies. One thing to note is that, due to variable word sizes in character-level parsing, the number of actions can vary between different sequences of actions corresponding to different analyses. We use the padding method [30], adding an IDLE action to finished transition action sequences, for better alignments between states in the beam.

In the character-level arc-standard transition system, each word is initialized by the action ${\text{SH}}_{\text{w}}$ with a POS tag, before being incrementally modified by a sequence of intra-word actions, and finally being completed by the action PW. The inter-word actions can be applied when all the elements on the stack are full-word nodes, while the intra-word actions can be applied when at least the top element on the stack is a partial-word node. For the actions ${\text{AL}}_{\text{c}}$ and ${\text{AR}}_{\text{c}}$ to be valid, the top two elements on the stack are both partial-word nodes. For the action PW to be valid, only the top element on the stack is a partial-word node. Figure a gives an example action sequence.

There are three types of features. The first two types are traditionally established features for the dependency parsing and joint word segmentation and POS-tagging tasks. We use the features proposed by Hatori et al. (2012). The word-level dependency parsing features are added when the inter-word actions are applied, and the features for joint word segmentation and POS-tagging are added when the actions PW, ${\text{SH}}_{\text{w}}$ and ${\text{SH}}_{\text{c}}$ are applied. Following the work of Hatori et al. (2012), we have a parameter $\alpha$ to adjust the weights for joint word segmentation and POS-tagging features. We apply word-based dependency parsing features to intra-word dependency parsing as well, by using subwords (the conjunction of characters spanning the head node) to replace words in word features. The third type of features is word-structure features. We extract the head character and the smallest subwords containing the head character from the intra-word dependencies (Section 2). Table 1 summarizes the features.

Similar to the arc-standard case, the state of a word-based arc-eager model consists of a stack and a queue, where the stack contains a sequence of partial dependency trees, and the queue consists of unprocessed input words. Unlike the arc-standard model, which builds dependencies on the top two elements on the stack, the arc-eager model builds dependencies between the top element of the stack and the first element of the queue. Five actions are defined for state transformation: arc-left (AL, which creates a left arc between the top element of the stack $s_0$ and the first element in the queue $q_0$, while popping $s_0$ off the stack), arc-right (AR, which creates a right arc between $s_0$ and $q_0$, while shifting $q_0$ from the queue onto the stack), pop-root (PR, which defines the ROOT node of the dependency tree when there is only one element on the stack and no element in the queue), reduce (RD, which pops $s_0$ off the stack), and shift (SH, which shifts $q_0$ onto the stack).

There is no previous work that exploits the arc-eager algorithm for jointly performing POS-tagging and dependency parsing. Since the first element of the queue can be shifted onto the stack by either SH or AR, it is more difficult to assign a POS tag to each word by using a single action. In this work, we make a change to the configuration state, adding a deque between the stack and the queue to save partial words with intra-word dependencies. We divide the transition actions into two categories, one for inter-word dependencies (${\text{AR}}_{\text{w}}$, ${\text{AL}}_{\text{w}}$, ${\text{SH}}_{\text{w}}$, ${\text{RD}}_{\text{w}}$ and PR) and the other for intra-word dependencies (${\text{AR}}_{\text{c}}$, ${\text{AL}}_{\text{c}}$, ${\text{SH}}_{\text{c}}$, ${\text{RD}}_{\text{c}}$ and PW), requiring that the intra-word actions be operated between the deque and the queue, while the inter-word actions be operated between the stack and the deque.

For character-level arc-eager dependency parsing, the inter-word actions are the same as the word-based methods. The actions ${\text{AL}}_{\text{c}}$ and ${\text{AR}}_{\text{c}}$ are the same as ${\text{AL}}_{\text{w}}$ and ${\text{AR}}_{\text{w}}$, except that they operate on characters, but the ${\text{SH}}_{\text{c}}$ operation has a parameter to denote the POS tag of a word. The PW action recognizes a full-word. We also have an IDLE action, for the same reason as the arc-standard model.

In the character-level arc-eager transition system, a word is formed in a similar way with that of character-level arc-standard algorithm. Each word is initialized by the action ${\text{SH}}_{\text{c}}$ with a POS tag, and then incrementally changed a sequence of intra-word actions, before being finalized by the action PW. All these actions operate between the queue and deque. For the action PW, only the first element in the deque (close to the queue) is a partial-word node. For the actions ${\text{AR}}_{\text{c}}$ and ${\text{AL}}_{\text{c}}$ to be valid, the first element in the deque must be a partial-word node. The action ${\text{SH}}_{\text{c}}$ have a POS tag when shifting the first character of a word,but does not have such a parameter when shifting the next characters of a word. For the action ${\text{SH}}_{\text{c}}$ with a POS tag to be valid, the first element in the deque must be a full-word node. Different from the arc-standard model, at any stage we can choose either the action ${\text{SH}}_{\text{c}}$ with a POS tag to initialize a new word on the deque, or the inter-word actions on the stack. In order to eliminate the ambiguity, we define a new parameter $t$ to limit the max size of the deque. If the deque is full with $t$ words, inter-word actions are performed; otherwise intra-word actions are performed. All the inter-word actions must be applied on full-word nodes between the stack an the deque. Figure b gives an example action sequence.

Similar to the arc-standard case, there are three types of features, with the first two types being traditionally established features for dependency parsing and joint word segmentation and POS-tagging. The dependency parsing features are taken from the work of Zhang and Nivre (2011), and the features for joint word segmentation and POS-tagging are taken from Zhang and Clark (2010)¹¹Since Hatori et al. (2012) also use Zhang and Clark (2010)’s features, the arc-standard and arc-eager character-level dependency parsing models have the same features for joint word segmentation and POS-tagging.. The word-level dependency parsing features are triggered when the inter-word actions are applied, while the features of joint word segmentation and POS-tagging are added when the actions ${\text{SH}}_{\text{c}}$, ${\text{AR}}_{\text{c}}$ and PW are applied. Again we use a parameter $\alpha$ to adjust the weights for joint word segmentation and POS-tagging features. The word-level features for dependency parsing are applied to intra-word dependency parsing as well, by using subwords to replace words. The third type of features is word-structure features, which are the same as those of the character-level arc-standard model, shown in Table 1.

We use the Chinese Penn Treebank 5.0, 6.0 and 7.0 to conduct the experiments, splitting the corpora into training, development and test sets according to previous work. Three different splitting methods are used, namely CTB50 by Zhang and Clark (2010), CTB60 by the official documentation of CTB 6.0, and CTB70 by Wang et al. (2011). The dataset statistics are shown in Table 2. We use the head rules of Zhang and Clark (2008) to convert phrase structures into dependency structures. The intra-word dependencies are extracted from the annotations of Zhang et al. (2013)²²https://github.com/zhangmeishan/wordstructures; their annotation was conducted on CTB 5.0, while we made annotations of the remainder of the CTB 7.0 words. We also make the annotations publicly available at the same site..

The standard measures of word-level precision, recall and F1 score are used to evaluate word segmentation, POS-tagging and dependency parsing, following Hatori et al. (2012). In addition, we use the same measures to evaluate intra-word dependencies, which indicate the performance of predicting word structures. A word’s structure is correct only if all the intra-word dependencies are all correctly recognized.

For the baseline, we have two different pipeline models. The first consists of a joint segmentation and POS-tagging model [26] and a word-based dependency parsing model using the arc-standard algorithm [12]. We name this model STD (pipe). The second consists of the same joint segmentation and POS-tagging model and a word-based dependency parsing model using the arc-eager algorithm [28]. We name this model EAG (pipe). For the pipeline models, we use a beam of size 16 for joint segmentation and POS-tagging, and a beam of size 64 for dependency parsing, according to previous work.

We study the following character-level dependency parsing models:

• •

  STD (real, pseudo): the arc-standard model with annotated intra-word dependencies and pseudo inter-word dependencies;

• •

  STD (pseudo, real): the arc-standard model with pseudo intra-word dependencies and real inter-word dependencies;

• •

  STD (real, real): the arc-standard model with annotated intra-word dependencies and real inter-word dependencies;

• •

  EAG (real, pseudo): the arc-eager model with annotated intra-word dependencies and pseudo inter-word dependencies;

• •

  EAG (pseudo, real): the arc-eager model with pseudo intra-word dependencies and real inter-word dependencies;

• •

  EAG (real, real): the arc-eager model with annotated intra-word dependencies and real inter-word dependencies.

The annotated intra-word dependencies refer to the dependencies extracted from annotated word structures, while the pseudo intra-word dependencies used in the above models are similar to those of Hatori et al. (2012). For a given word $w=c_1{c}_2\mathrm{\cdots }{c}_m$, the intra-word dependency structure is $c_1^{\curvearrowleft }{c}_2^{\curvearrowleft }{\mathrm{\cdots }}^{\curvearrowleft }{c}_m$³³We also tried similar structures with right arcs, which gave lower accuracies.. The real inter-word dependencies refer to the syntactic word-level dependencies by head-finding rules from CTB, while the pseudo inter-word dependencies refer to the word-level dependencies used by Zhao (2009) ($w_1^{\curvearrowleft }{w}_2^{\curvearrowleft }{\mathrm{\cdots }}^{\curvearrowleft }{w}_n$). The character-level models with annotated intra-word dependencies and pseudo inter-word dependencies are compared with the pipelines on word segmentation and POS-tagging accuracies, and are compared with the character-level models with annotated intra-word dependencies and real inter-word dependencies on word segmentation, POS-tagging and word-structure predicating accuracies. All the proposed models use a beam of size 64 after considering both speeds and accuracies.

Our development tests are designed for two purposes: adjusting the parameters for the two proposed character-level models and testing the effectiveness of the novel word-structure features. Tuning is conducted by maximizing word-level dependency accuracies. All the tests are conducted on the CTB60 data set.

Table 6 shows the final results on the CTB50, CTB60 and CTB70 data sets, respectively. The results demonstrate that the character-level dependency parsing models are significantly better than the corresponding word-based pipeline models, for both the arc-standard and arc-eager systems. Similar to the findings of Zhang et al. (2013), we find that the annotated word structures can give better accuracies than pseudo word structures. Another interesting finding is that, although the arc-eager algorithm achieves lower accuracies in the word-based pipeline models, it obtains comparative accuracies in the character-level models.

We also compare our results to those of Hatori et al. (2012), which is comparable to STD (pseudo, real) since similar arc-standard algorithms and features are used. The major difference is the set of transition actions. We rerun their system on the three datasets⁴⁴http://triplet.cc/. We use a different constituent-to-dependency conversion scheme in comparison with Hatori et al. (2012)’s work. . As shown in Table 6, our arc-standard system with pseudo word structures brings consistent better accuracies than their work on all the three data sets.

Both the pipelines and character-level models with pseudo inter-word dependencies perform word segmentation and POS-tagging jointly, without using real word-level syntactic information. A comparison between them (STD/EAG (pipe) vs. STD/EAG (real, pseudo)) reflects the effectiveness of annotated intra-word dependencies on segmentation and POS-tagging. We can see that both the arc-standard and arc-eager models with annotated intra-word dependencies can improve the segmentation accuracies by 0.3% and the POS-tagging accuracies by 0.5% on average on the three datasets. Similarly, a comparison between the character-level models with pseudo inter-word dependencies and the character-level models with real inter-word dependencies (STD/EAG (real, pseudo) vs. STD/EAG (real, real)) can reflect the effectiveness of annotated inter-word structures on morphology analysis. We can see that improved POS-tagging accuracies are achieved using the real inter-word dependencies when jointly performing inner- and inter-word dependencies. However, we find that the inter-word dependencies do not help the word-structure accuracies.

To better understand the character-level parsing models, we conduct error analysis in this section. All the experiments are conducted on the CTB60 test data sets. The new advantage of the character-level models is that one can parse the internal word structures of intra-word dependencies. Thus we are interested in their capabilities of predicting word structures. We study the word-structure accuracies in two aspects, including OOV, word length, POS tags and the parsing model.