iRe2f: Rethinking Effective Refinement in Language Structure Prediction via Efficient Iterative Retrospecting and Reasoning

1 Introduction

Language structure prediction is an important area of research in natural language processing (NLP), which involves using computational techniques to analyze and understand the complex structure of natural languages [Sun et al., 2021]. It is usually modeled as graph parsing, which involves analyzing the grammatical graph of a sentence or text, or identifying the relationships between words and phrases in a document.

Parsing involves analyzing and representing the grammatical structure of a sentence or text in a structured format like a tree or graph. A typical parser consists of an encoder, which vectorizes and contextualizes the input, and a decoder, which scores and generates the structured output. The initial parsing output, often referred to as the draft parse, may not be fully accurate or complete, as it is based on limited information and may contain errors or inconsistencies. Refinement is a process that aims to improve the accuracy and completeness of the parse by incorporating additional information and correcting any errors or inconsistencies. Refinement is important because it helps to improve the overall quality and reliability of the parse, which is critical for accurate language structure prediction.

Iterative refinement is a technique introduced by Lyu et al. that aims to capture interdependencies between dependents and corresponding labels in graph parsing tasks, which is used to refine the parsing graph through fault correction. The proposed framework takes the initial sequence representation H0 from the base parser, as well as the sequence and graph representations H(t-1) and G (t-1) from the latest iteration, as input. The refiner then reasons a new parsing graph G t based on this input:

The above refining process involves capturing missing interdependencies in the input draft parsing graph to reason better parsing graphs in each iteration. Mohammadshahi and Henderson further proposed using a graph-to-graph encoder to improve the performance of the refiner.

There is no doubt that iterative refiners can play a significant role in the performance improvement of graph parsing. However, the current implementation of refiners adds a significant computational burden to the parser, which goes against the original idea that refiners are only used to correct a small number of faults in the draft parses. Specifically, each iteration in current refiners involves repeating the encodingdecoding procedure in the base parser, with the only difference being the inclusion of a merging step between the representations from the initial output and previous iterations.

The inefficiency of current iterative refiners is due to the re-encoding procedure, which involves repeating the timeconsuming encoding process (such as BiLSTM in [Lyu et al., 2019a] or Graph Transformer in [Mohammadshahi and Henderson, 2021]) in each refining iteration. Motivated by the fact that errors in graph parsing is non-dominant, we propose an efficient refiner framework, IRE2 F, for graph parsing via iterative retrospecting and reasoning. As shown in Figure 1, our framework excludes the expensive encoder from the refiner. Instead of refining using H(t-1) and G (t-1) from the latest iteration, our framework directly learns a retrospecter with a shortcut Rt from G (t-1) to perform retrospecting and reasoning.

We compare the proposed IRE2 F refiner with previous state-of-the-art iterative refiners and a high-order refiner on various language structure prediction tasks. These tasks include dependency parsing for syntax, semantic dependency parsing and semantic role labeling for semantics. Our experiments demonstrate that IRE2 F reduces the computational burden in each refinement iteration to 10% while achieving comparable or better performances. It also has a simpler structure with significantly fewer parameters, indicating that the improvement is due to the refinement mechanism rather than a large number of extra parameters. We also find that combining IRE2 F with higher-order refinement leads to further improvement, demonstrating the benefits of multi-stage refinement.

2 RelatedWork

2.1 Language Structure Prediction

Early work in language structure prediction focused on developing rule-based systems [Bocharova, 2008], which involved manually defining the rules for analyzing and representing the structure of a language. More recently, there has been a shift towards the use of machine learning techniques for language structure prediction, such as statistical parsing [Nivre et al., 2009] and graph-based parsing [Chen and Manning, 2014; Li et al., 2022b].

Neural dependency parsing has become the dominant approach for language structure prediction and can be divided into two main categories: transition-based parsers and graphbased parsers. Transition-based neural parsers use a word buffer and a word stack to monotonically decide the next action to take , while graph-based parsers assign global scores to edges and labels in order to directly construct the full dependency graph in one-shot. Early graph-based neural parsers such as [Kiperwasser and Goldberg, 2016] and [Hashimoto et al., 2016] used BiLSTMs and MLPs to contextualize and compute the global scores on the possible pair representations. Since the introduction of the deep biaffine attention by [Dozat and Manning, 2017], dot product with bias mechanism have been widely used in dependency parsing. Similar to syntactic dependency parsing, graph-based parsers have also been successfully applied to semantic dependency parsing [Peng et al., 2017; Dozat and Manning, 2018; Jia et al., 2020; Kurita and Søgaard, 2019].

2.2 Refinement

Iterative refinement has been shown to be effective in language generation tasks such as machine translation [Lee et al., 2020] and long text generation [Hua and Wang, 2020], which is resulted from helping understanding complex sequence [Li et al., 2022a]. In natural language understanding tasks, iterative refinement is often used for label annotation. In the work of [Gui et al., 2020], researchers used a variational structure to evaluate the uncertainty of labels annotated in the first run and leveraged this uncertainty information to guide the refinement runs to only correct labels with high uncertainty and avoid changing labels with low uncertainty.

In language structure prediction, there are two styles of iterative refinement for graph-based parsers. In [Lyu et al., 2019a], intermediate representations are extracted and passed to subsequent iterations without being decoded into explicit graphs or trees. While in [Mohammadshahi and Henderson, 2021], graphs decoded from the base parser or refiner are combined with the sentence as new inputs and fed through a Transformer encoder to generate new representations. In this work, we adopt the former style of refinement and design a novel refiner framework via efficient retrospecting and reasoning on the intermediate representations.

3 IRE2 F Framework

Our IRE2 F framework, like the general refiner framework, consists of both a base parser and refinement components. The base parser is responsible for encoding of the input and initial parsing, while the refinement component focuses on correcting any errors or faults in the initial parsing or encoding and improving the overall structure of the output. The refinement component takes the output of the base parser, as well as additional input information, and uses it to iteratively refine the structure until it meets the desired criteria.

3.1 Base Parser

To create a base parser for the initial parsing, we follow the model structure of biaffine parser (BIAF) proposed in [Dozat and Manning, 2017]. Given an input sentence with n words X, we first embed the words and their linguistic features Xfeat. We also obtain pre-trained contextualized representations from a pre-trained language model (PLM) to a strong baseline. Finally, we concatenate these representations to obtain the initial representation H0 :

where ⊕ refers to the concatenation operation, and EMBED(·) represents the randomly initialized embedding layer.

The BiLSTM has a long history of being a successful choice for encoding sequential data and has been widely used in various language structure prediction tasks, demonstrating strong performance. Therefore, we chose to use the BiLSTM as the encoder for our base model. In our work, we contextualize the initial representations H0 using a stacked multi-layer BiLSTM encoder to produce C. We then project C using two linear layers to obtain head and dependent role-specific representations CH and CD.

where WHbase and WDbase are learnable weight parameters, bHbase and bDbase are bias items.

In language structure prediction as graph parsing, relationships between words are modeled as scores of edges between graph nodes. Therefore, performing pair scoring on rolespecific representations is fundamental to enable graph reasoning. Biaffine attention mechanism has demonstrated excellent pair scoring ability since it was proposed. Therefore, in the base parser, we fed head and dependent representations into a biaffine attention scorer to get the scores for the existence and label of each possible edge.

where WB ∈ Rd×(c+1)×d ,WH,WD ∈ R(c+1)×d , and b is a bias item. Here c refers to the number of relationship categories, d is the dimension of input representations. The (c+1) is due to the introduction of a null relation, and S is recognized as the graph representation which can be further decoded to a graph G.

3.2 Rethinking Refinement

The refinement methods in the literature can be divided into three categories: Sequence RepresentationDriven, Joint Sequence-Structure Representation-Driven, and Higher-Order Representation-Driven.

Sequence Representation-Driven (SRD) focuses on tuning the graph representation generated by the base parser based on the iteratively-updated sequence representation to achieve the purpose of refinement. It involves using the output of the base model as input to the refinement process, and then updating the representation based on this draft parses and iterative encoding.

In [Lyu et al., 2019a], the predicted logits from the previous iteration are merged with re-encoded representations in the current iteration. For example, in iteration t, this process involves using a BiLSTM encoder to re-contextualize the initial representation H0 to C t , which is then projected to C tH and C tD as in the base parser. The refiner merges the current representation of the parsing graph St in the iteration t with C tH , C tD using specific merge operations (like multiple linear projections) into a tuned graph representation ˜ S t ∈ Rn×n×d :

where MERGE(·) is the process of combining the previous parsing output S (t-1) with the current step's representataions C tH and C tD during the interative refinement process. In [Lyu et al., 2019a], this is achieved by summing up the probability mass of all labels in S (t-1) and fusing them through a linear layer projection, which is then added to C tH and C tD . ˜ S t is further mapped by a linear projection into S t ∈ Rn×n×(c+1) .

where WG,t and bG,t are learnable parameters.

Joint Sequence-Structure Representation-Driven (JSSRD) focuses on completely re-encoding the decoded draft parse and the input sequence to obtain a new joint representation to identify errors or faults in the graph for refinement. In the proposed method of [Mohammadshahi and Henderson, 2021], the draft graph from the base parser or last iteration is passed through a graph-informed Transformer encoder to produce updated representations, which is then used to produce the new parsing graph. This differs from the approach in [Lyu et al., 2019a], which only considers the representations from the base parser and the previous iteration in the refinement process, rather than the draft graph itself.

where GRAPHTRANSF(·) involves encoding the previous parsing graph to obtain new representations. In [Mohammadshahi and Henderson, 2021], it is implemented as a RecursiveNon-autoregressiveGraph-to-Graph Transformer. C tH and C tD are then scored into S t and decoded to graph Gt as in the base biaffine parser.

Higher-Order Representation-Driven (HORD) involves incorporating higher-order information, such as interdependencies between graph edges, into the graph representations for refinement to improve the base model's performance [Li et al., 2020]. [Wang et al., 2019] proposed a refiner with second-order features, which inducts based on second-order relationships among edges. The refiner uses Variational Inference (VI) for utilizing second-order representations into the graph representations to further improve the final parsing performance.

Specifically, the second-order refiner predicts three secondorder representations between words: siblings, co-parents, and grandparents. To get these representations, second-order refiner introduces a triaffine attention mechanism for scoring:

Similar to graph representations, second-order representations V sib , V cop and V grp are extracted on the role-specific sequence representations:

where C λ = WλsoC + bλso , λ ∈ H, D, B, and B indicates the role of both head and dependent. Then these second-order representations are used to refine the first-order graph representations by Mean Field Variational Inference [Wang et al., 2019] to form final graph representations:

3.3 Retrospecting viaMessage Passing

In the methods SRD, JSSRD, and HORD, the sequence representation, joint sequence-structure representation, and highorder representation are used to guide the refinement of the graph representation, respectively, by re-encoding or additional scoring. However, this leads to a heavily increased computational cost relative to the base parser. To address this issue, we propose a new approach that uses message passing in graph representation learning to retrospect the draft graph representation, allowing for the update of the graph representation without the need for re-encoding or additional complex computations on the graph or sequence representation.

Specifically, the proposed retrospecting mechanism updates the graph representations by commuting between headdependent related representations, allowing for a shortcut between related words based on the parsed graph in previous iterations. The process for refining graph representations using retrospective message passing involves taking head and dependent representations and parsing graph representations from the previous iteration as input. A relation-aware attention mechanism integrates the graph representations into relation-aware sequence representations, which involves a soft embedding process to transform relationship logits into relation features. Relation features are then fused with rolespecific sequence features using element-wise product operations to obtain relation-aware sequence features, allowing head and dependent representations to interact with label features. Then, the message passing is finished by passing relation-aware sequence representations to inform about heads and dependents. The resulting relation-aware sequence representation is then used to reason a new graph representation, merged with the input graph representation using a shortcut mechanism to produce the output graph representation for the current iteration. The proposed approach enables considering the previous parsing graph when refining the current one.

For example, in the semantic role labeling task shown in Figure 3, the shortcut informs the predicate 'said' that it has an 'A0' argument 'Showalter' in the refining iteration. As a result, the predicate 'said' is able to successfully reason the missing 'AM-DIS' argument 'But' thanks to the relationship between arguments 'But' and the shortcut-identified 'Showalter'. In other words, 'Showalter' and 'But' are parts of a sentence that have a local relationship, 'But' serves to connect the clause containing 'Showalter' with the implied contrasting clause. The shortcut mechanism updates the representation using the draft parse and establishes a connection between 'Showalter' and 'said'. The updated representation is subsequently used to further refine the tree in the next iteration, making it easier to reason about the connection between 'But' and 'said'.

In Figure 2, we illustrate the process for refining graph representations using retrospective message passing. In iteration t, our refinement takes the head and dependent representations, C (t-1) H and C (t-1) D , as well as the parsing graph representations from the previous iteration, S(t-1) , as input. We employ a relation-aware attention mechanism to integrate the graph representations into relation-aware sequence representations, which involves a soft embedding process to transform relationship logits into relationship features.

where i, j refers to the edge from i-th word to j-th word. Qi,j,k thus represents the probability of the k-th label on the edge. WkE is the embedding for k-th label. The final output E (t-1) i,j is a sum of all label embeddings weighted by their existing probabilities on the edge.

We then fuse relation features with role-specific sequence features using element-wise product operations to obtain relation-aware sequence features. This allows head and dependent representations to interact with label features.

where × represents the element-wise product operation. I H , I D represents the interaction results of relation features with their heads and dependents.

We further apply layer normalization, a feedforward network (FFN), and residual connection to the relation-aware sequence representations, as done in [Vaswani et al., 2017], to improve the learning efficiency and reduce the risk of overfitting. These techniques enable the model to learn more complex relationships between the input and output, and improve optimization and generalization by learning the residual mapping between the input and output.

After the above process, message passing is finished by passing I H to inform CD about its heads and passing I D to CH to inform about its dependents.

The resulting relation-aware sequence representation is then used to reason a new graph representation, merged with the input graph representation using a shortcut mechanism to produce the output graph representation for iteration t. This allows us to consider the previous parsing graph when refining the current one.

where Ht represents the sequence representation in the t-th iteration, H0 denotes the input embeddings, and SHORTCUT(·) is implemented as element-wise addition.

4 Experiments

4.1 Datasets

We conducted experiments on three language structure prediction tasks: syntactic dependency parsing (SynDP), semantic dependency parsing (SemDP) and semantic role labeling (SRL).

SynDP We evaluate our proposed framework on traditional treebanks for English (PTB-3.3 [Marcus et al., 1993]) and Chinese (CTB-5.1 [Xue et al., 2002]) and also on the multilingual benchmark of universal dependency treebanks v2.3, in which 12 languages are selected following [Mohammadshahi and Henderson, 2021] for comparison with previous systems.

SemDP We conduct experiments on the datasets from SemEval-2015 shared task [Oepen et al., 2015], which includes three subtasks: DELPH-IN MRS-Derived Bi-Lexical Dependencies (DM), Enju Predicate-Argument Structures (PAS), and Prague Semantic Dependencies (PSD). Each subtask includes test sets in two domains: in-domain (ID) and out-of-domain (OOD).

SRL In our experiments on SRL, we use the CoNLL09 shared task [Hajic et al., 2009] which includes datasets in 7 languages [Li et al., 2021].

4.2 Configurations

We use the hyperparameter setup from [Dozat and Manning, 2017] and [Dozat and Manning, 2018] for SynDP and SemDP, respectively. For English datasets, we use GloVe [Pennington et al., 2014] as pre-trained word embeddings, and fasttext [Bojanowski et al., 2017] for other languages. We also include lemma and part-of-speech features, which are embedded using randomly initialized embedding layer. For character features, we encode the sequence using a character BiLSTM. We use bert-large-uncased as the pre-trained language model for English and bert-base-multilingual-cased for other languages, except for Chinese which uses bert-base-chinese.

We implemented the SRD and JSSRD refiners based on the methods described in [Lyu et al., 2019a] and [Mohammadshahi and Henderson, 2021]. For SynDP, we implemented the HORD refiner following the method in [Wang and Tu, 2020], for SemDP, we implemented it based on the method in [Wang et al., 2019], and for SRL, we implemented it based on the method in [Li et al., 2020]. The number of iterations in the refiners was determined through experiments on PTB for SynDP, PAS for SemDP, and CoNLL09-En for SRL.

In the refinement training, we use the sum of the loss between the golden edges and labels with scores from all iterations as the total loss. For SemDP and SRL tasks, we use binary cross-entropy loss for edges and cross-entropy loss for labels. For SynDP, we use cross-entropy loss for both edges and labels. We train the model using Adam optimizer [Kingma and Ba, 2015] with a decaying learning rate. The code is available at https://github.com/zcli-charlie/iRe2f.

4.3 Results

SynDP According to the results in Table 1 on SynDP, our baseline models performed well and were comparable to previously reported results. Comparing our IRE2 F with SRD, JSSRD and HORD, our IRE2 F achieves better refinement performance on the same strong BIAF baseline, illustrating the effectiveness of our method. The full model with IRE2 F achieved competitive results with previous best models 1 without stronger pre-trained language model and complex model designs. This demonstrates that our retrospecting refinement is a general and effective mechanism that can be applied to SynDP.

In addition, since the contributions of HORD and SRD, JSSRD, and IRE2 F are independent, we further combine them. The experimental results show that the model combining the two refinement mechanisms has been further improved compared to using a single method. This suggests that the improvement brought about by the refinement of SRD, JSSRD and IRE2 F does not solely depend on the high-order information present in the graph, but also on better graph representation learning.

Furthermore, we conducted experiments on universal dependency treebanks to verify the effectiveness of our refinement framework on multilingual scenarios. We compared the performance of IRE2 F with other iterative refiners, and the results are presented in Table 2. These experiments showed that our proposed IRE2 F framework outperforms other iterative refiners and is able to achieve superior results on multiple languages.

SDP Table 3 shows the comparison of our models with previous state-of-the-art methods. We first test the performance of the baseline biaffine model and various refinements including SRD, JSSRD, HORD, and IRE2 F. We find that all these refinements lead to performance gains and are comparable to previously reported results. However, based on the BiAF baseline, our IRE2 F framework brings about the biggest parsing performance improvement. Furthermore, our model can achieve further improvement on the stronger second-order baseline, which again indicates that IRE2 F refinement is orthogonal to high-order refinement. The results reached by our full model, which combines IRE2 F and HORD refinements, have set new state-of-the-arts on all SemDP datasets.

SRL We report in Table 4 the results on pre-identified predicates setting for 7 languages on the SRL task. BIAF+IRE2 F and BIAF+HORD have improved the parsing performance compared to the baseline BIAF, which reflects the importance of refinement in this task. Furthermore, superimposing IRE2 F on top of HORD shows even greater improvements in all seven languages compared to the BIAF baseline. Among them, ca, es, and en languages have the greatest improvement. This is because the proportion of second-order structures in these languages is small, so HORD brings limited improvement, and the effectiveness of our IRE2 F comes from graph representation learning, which can still play a role.

Computing Efficiency To demonstrate the computational efficiency advantages of IRE2 F compared to existing refinements, we selected the DM task in SemDP to compare model parameters and efficiency. The results are shown in Table 5. The models with +SRD, +JSSRD, +HORD, +IRE2 F have consistent base parameters with the BiAF baseline, and the introduction of refinement brings additional parameters. Among them, IRE2 F has the least additional parameters, about 90% less than the previous minimum SRD, which is related to its mechanism of directly updating the graph representation based on retrospecting without re-encoding. Correspondingly, IRE2 F has the least decrease in training and inference speed compared to the baseline, while JSSRD has the most decrease, which may be due to the need to perform additional MFVI in high-order reasoning. By comparing with +SRD, +JSSRD, +HORD, we conclude that IRE2 F is an efficient refinement framework.

1 It is worth noting that the results reported in the table are based on the BERT pre-training model only, and stronger pre-training models have not been considered as they are not our focus.

5 Further Analysis 5.1 Ablation Study

We present an ablation study of the structural design of IRE2 F in Table 6. After removing the SHORTCUT, the parsing performance drops significantly, even lower than the BIAF baseline. This illustrates that in the iterative refinement process of IRE2 F, it is crucial to update the graph representation gradually, which can reduce the difficulty of graph representation learning. Removing RELATTN also resulted in a decrease in performance, which demonstrates that the graph representation is not only dependent on the edges, but the relationship between edges is also crucial for refinement. The removal of FFN and RESIDUAL makes IRE2 F unable to be successfully trained, indicating that it is helpful to effectively learns complex representations and overcomes the limitations like vanishing gradient problem.

5.2 Different Iterations

IRE2 F performs iterative refinement of graph representations. We show in Table 7 the effect of the number of iterations on the parsing performance of SynDP and SemDP tasks. Compared to no refinement, even one round of refinement can achieve better results. Further increasing the number of iterative rounds leads to an improvement in parsing performance. However, the optimal number of iterations for different tasks varies depending on the complexity of the parsing graph. The number of iterative rounds should not be as high as possible. After the effect of refinement and improvement reaches a the optimal, continuing to increase will not bring about any further improvement or may even result in a decline.

5.3 More Discussion for Longer Sentences

In the iterative refinement method, both [Lyu et al., 2019a] and [Mohammadshahi and Henderson, 2021] have compared the performance of using iterative refinement on different dependency distances, and it is indeed true that iterative refinement can improve the parsing accuracy of instances with longer dependency distances. Additionally, we also conducted separate statistics on the UD v2.3 test set based on sequences of different lengths. From the statistical results shown in Figure 4, there is indeed a trend of greater improvement for longer sequences, but it is not a perfect match. On the one hand, sequences with longer lengths have greater dependency distances, but they are not entirely consistent. On the other hand, sequences of different lengths have different proportions in the test set, which can lead to bias in certain length intervals.

6 Conclusion and FutureWork

In this paper, we presented an efficient refinement framework, IRE2 F, for language structure prediction tasks. IRE2 F performs refinement by iteratively retrospecting and reasoning on the graph representations directly, without the need for re-encoding. By introducing the novel relation-aware attention, our structure achieved significant improvement. Furthermore, our proposed IRE2 F can also be combined with other refinement frameworks like HORD for further improvement. Through various experiments, we demonstrated that IRE2 F outperforms existing state-of-the-art refinement frameworks in terms of performance and computational efficiency. Since our refinement approach is orthogonal to the choice of base parser, we evaluated our proposed method using only the biaffine parser. This parser is widely used and is a strong foundation for graph parsing. However, we anticipate that our approach can be applied to other base parsers as well, which would demonstrate its generalization ability for future work. We also plan to investigate its performance with other base parsers.

Acknowledgements

Corresponding author: Hai Zhao. Zuchao Li and Letian Peng made equal contributions to this work. This work was supported by the Special Fund of Hubei Luojia Laboratory under Grant 220100014. Hai Zhao was funded by the Key Projects of National Natural Science Foundation of China (U1836222 and 61733011). We thank the anonymous reviewers for their careful reading of our manuscript and their many insightful comments and suggestions.