We propose a graph-based method to tackle the dependency tree linearization task. We formulate the task as a Traveling Salesman Problem (TSP), and use a biaffine attention model to calculate the edge costs. We facilitate the decoding by solving the TSP for each subtree and combining the solution into a projective tree. We then design a transition system as post-processing, inspired by non-projective transition-based parsing, to obtain non-projective sentences. Our proposed method outperforms the state-of-the-art linearizer while being 10 times faster in training and decoding. Surface realization is the task of generating a sentence from a syntactic or semantic representation. In several shared tasks (Belz et al., 2011; Mille et al., 2018, 2019), the input representations are unordered dependency trees. The state-of-the-art system (Yu et al., 2019a) in the Surface Realization Shared Task 2019 (SR'19) takes a pipeline approach, where the first step is linearization, namely ordering the tokens in the dependency tree. They use a Tree-LSTM to encode each token with awareness of the whole tree, then apply the divide-and-conquer strategy to split the full tree into subtrees and find the optimal order for each subtree using beam search. Finally, the linearized subtrees are combined into a full projective tree. The general strategy is adapted from Bohnet et al. (2010). In this work, we tackle linearization decoding in a different way, by casting it as a Traveling Salesman Problem (TSP). Knight (1999) first formulated the word ordering of the target language in word-based machine translation as a TSP, where the words are the nodes to traverse, and the log probabilities of the bigrams are the edge costs. Several works have followed this formulation. Among others, Zaslavskiy et al. (2009) formulate the word ordering in phrase-based machine translation as a TSP, and show that it achieves better performance and speed than beam search decoding with the same bigram language model. Horvat and Byrne (2014) explore higher-order n -gram language models for TSP-based word ordering, which transforms into a much larger TSP graph. All of the aforementioned works operate on a bag of words without syntax , which is a TSP graph of non-trivial size with little information about the internal structure. Much effort has been put into incorporating more powerful decoding algorithms such as Integer Programming (Germann et al., 2001) and Dynamic Programming (Tillmann and Ney, 2003). Our work differs from the previous work on TSP-based word ordering in several aspects. (1) Linearization is a special case of word ordering with syntax , where we can use a tree-structured encoder to provide better representation of the tokens. (2) We adopt the divide-and-conquer strategy to break down the full tree into subtrees and order each subtree separately, which is faster and more reliable with an approximate decoder. (3) We apply deep biaffine attention (Dozat and Manning, 2016), which has yielded great improvements in dependency parsing, and reinterpret it as a bigram language model to compute edge costs for the TSP. In this paper, we solve the dependency tree linearization task as a TSP. With the help of Tree-LSTM to encode the tree and biaffine attention as a bigram language model, we can use a greedy TSP solver to linearize the tree effectively. Furthermore, the divide-and-conquer strategy greatly reduces the search space but introduces the projectivity restriction, which we remedy with a transition-based reordering system. As a result, the proposed linearizer outperforms the previous state-of-the-art model both in quality and speed. We follow the idea in Knight (1999) to treat linearization as a TSP. Under the TSP formulation, we need to calculate the cost from every node i to every other node j , which can be interpreted as the log likelihood of the bigram ( i, j ) . We use the biaffine attention model (Dozat and Manning, 2016) to obtain the costs, and use an off-the-shelf TSP solver, OR-Tools 1 , to decode the TSP. To facilitate the approximate decoding of this NP-hard problem, we follow the divide-and-conquer strategy in Bohnet et al. (2010) of splitting the tree into subtrees, and decoding each subtree separately. There are pros and cons of this approach: on the one hand, the search space is much smaller so that a greedy TSP solver can find good solutions in reasonable time; on the other hand, it restricts the output to be projective, i.e., nonprojective sentences can never be produced. To remedy the projectivity restriction, we introduce a post-processing step using a simple transition system with only two transitions, swap and shift , to sort the linearized projective trees into potentially non-projective ones. This system is an extention of our previous work (Yu et al., 2019a). We use the same encoder and hyperparameters (see Appendix A) and only experiment with the decoders. The code is available at the first author's web page. 2 As an overview, Figure 1 illustrates our pipeline for the linearization task, with an unordered dependency tree as input, and a linearized sentence as output, which is potentially non-projective, i.e., with crossing dependency arcs. To solve the task, we (1) divide the tree into subtrees, (2) linearize each subtree by solving a TSP, (3) combine the linearized subtrees into an projective tree, and (4) use the swap system to obtain a non-projective tree. To formulate the linearization task as a TSP, we use a node to represent each token in the tree, and an extra node with index 0 as both the origin and destination, which is interpreted as the boundaries in the output sequence. Figure 2 demonstrates a decoded TSP graph from its edge cost matrix, where the output sequence is  < s > let us get < s > . We use the routing solver of OR-Tools to solve the TSP given the edge costs. It is a generic optimization library, unlike the more specialized and optimized TSP solvers such as Concorde (Apple-gate et al., 2006), but it enables imposing extra word order constraints described in  2.6, and can be easily extended to other constraints. Among all the first solution strategies provided in OR-Tools, we found GLOBAL CHEAPEST ARC to perform the best, which selects a valid edge with the lowest cost at every step until a full path is found. For the sake of efficiency, we use the greedy metaheuristic GREEDY DESCENT to refine the first solutions, which converges to local optima in very short time. In practice, it works extremely well in combination with the greedy training described in  2.4. More advanced metaheuristics such as GUIDED LOCAL SEARCH (Voudouris and Tsang, 1999) could find better solutions, but also require much more decoding time, it is thus less practical for real-time generation tasks. We do not use it in the default setting, but include it in the analysis to demonstrate the effectiveness of the training. We use the biaffine attention model (Dozat and Manning, 2016) to calculate the TSP edge costs. First, we obtain the representation for each token by concatenating the embeddings of the features, then encode the tree information with a bidirectional Tree-LSTM, as described in Yu et al. (2019b): v  i = v ( lem ) i  v ( pos ) i  v ( dep ) i  v ( mor ) i (1) x i = Tree-LSTM ( v  0 ... v  n ) i (2) The parameters of the decoder consist of two Multi-Layer Perceptrons (MLP ( fr ) and MLP ( to ) ) and a biaffine matrix ( W ). We use the MLPs to obtain different views of the token representation as the first and second token in the bigram: h ( fr ) i = MLP ( fr ) ( x i ) (3) h ( to ) i = MLP ( to ) ( x i ) (4) We then apply the biaffine transformation on the vectors of the first word h ( fr ) i and the second word h ( to ) j to compute the score s i,j of each bigram ( i, j ) , where W is the weight matrix of size ( k + 1)  ( k + 1) , and k is the size of h fri and h toj : s i,j = ( h ( fr ) i  1)  W  ( h ( to ) j  1) (cid:62) (5) In the actual computation, we parallelize Equation 5, where S is the output score matrix of size n  n , and n is the number of tokens: S = ( H ( fr )  1 )  W  ( H ( to )  1 ) (cid:62) (6) Finally, we turn the score matrix into a nonnegative cost matrix for the TSP solver: C = max ( S )  S (7) Our model is inspired by the biaffine dependency parser of Dozat and Manning (2016), but stands in contrast in many aspects. They use a bidirectional LSTM to encode the sequential information of the tokens, and the biaffine attention itself does not model the sequence. Each cell s i,j in their output matrix S is interpreted as the score of a dependency arc ( i, j ) . They use a Maximal Spanning Tree algorithm to obtain a tree that maximizes the total score of the arcs in the tree. In the case of linearization, our input and output are the opposite to theirs. The input has no sequential but syntactic information, encoded by the bidirectional Tree-LSTM. Each cell s i,j in the output matrix S is interpreted as the score of the bigram ( i, j ) . We use a TSP solver to obtain a traversal of the tokens by minimizing the total edge costs, i.e., maximizing the total bigram scores. We use a greedy training objective to train the biaffine scoring model, namely we enforce the score of each bigram ( i, j ) in the correct sequence z to be higher than any other bigrams in the same row or in the same column in the matrix by a margin: L = (cid:88) ( i,j )  z ( (cid:88) j (cid:48) (cid:54) = j max(0 , 1 + s i,j (cid:48)  s i,j ) + (cid:88) i (cid:48) (cid:54) = i max(0 , 1 + s i (cid:48) ,j  s i,j )) (8) This objective aims to maximizing the score of each correct bigram ( i, j ) in both directions, essentially log P ( j | i ) and log P ( i | j ) , where the cells in the same row corresponds to all possible tokens following i , and the cells in the column corresponds to all possible tokens preceding j . The objective is greedy in the sense that it updates more than necessary to decode the correct path. We contrast it to the structured loss in most graph-based dependency parsers (McDonald et al., 2005; Kiperwasser and Goldberg, 2016), which updates the scores of the correct path z against the highest scoring incorrect path z (cid:48) : L (cid:48) = max(0 , 1+ max z (cid:48) (cid:54) = z (cid:88) ( i (cid:48) ,j (cid:48) )  z (cid:48) s i (cid:48) ,j (cid:48)  (cid:88) ( i,j )  z s i,j ) (9) The greedy objective for the TSP has two main advantages: (1) it does not require decoding during training, which saves training time; (2) it pushes the scores of each correct bigram to be the highest in the row and the column, which facilitates the greedy solver ( GLOBAL CHEAPEST ARC ) to find a good initial solution. In fact, if the objective reaches 0, the greedy solver is guaranteed to find the optimal solution, since at each step, the cheapest arc is always a correct bigram instead of any other bigram in the same row or column. If we directly linearize the full tree, the output is naturally unrestricted, i.e., possibly non-projective. However, when we linearize each subtree separately in order to reduce the search space, as in the proposed method, the reconstructed output is restricted to be projective (Bohnet et al., 2010). To relax the projectivity restriction, we design a transition system to reorder projective trees into non-projective trees as a post-processing step, inspired by Nivre (2009) but working in the opposite way. It is essentially a reduced version of their transition system, removing the attachment transitions and keeping only swap and shift . In the transition system (as shown in Table 1), a configuration consists of a stack  , which is initially empty, and a buffer  , which initially holds all input tokens. The shift transition moves the front of the buffer to the top of the stack, and the swap transition moves the top of the stack back to the second place in the buffer. When all tokens are moved from the buffer to the stack, the procedure terminates. To prevent the model predicting infinite shift swap loops, we only allow swap if the initial index of the top of the stack is smaller than the front of the buffer. The worst-case complexity of the sorting is quadratic to the number of tokens, however, since trees in natural language mostly only contain very few non-projective arcs, the transition system works in expected linear time, as shown in Nivre (2009). We then implement a model to predict the transitions given the configurations. We use two LSTMs to dynamically encode the stack from left to right ( LSTM  ) and the buffer from right to left ( LSTM  ). We then concatenate the two outputs and use a MLP to predict the next transition. When a shift is performed, we update LSTM  state with the vector of the shifted token as the new stack representation, and the new buffer representation is the LSTM  output of the new front token; when a swap is performed, the new stack representation is the LSTM  output of the new top token, and the new buffer representation is recalculated by feeding the now second and first token in the buffer to the LSTM  state of the third token. Figure 3 illustrates the model under the transition system, where the arrows to the right represent LSTM  , the arrows to the left represent LSTM  , and the arrows between the stack and the buffer represent the MLP. After each transition, little computation is needed to represent the new stack and buffer, marked with the red dashed line. The example illustrates the steps to modify the configuration [1 2 | 3 4 5 6] into [1 2 | 4 3 5 6]. Note that the transition system is sound and complete, which means there is always a sequence of transitions to sort any sequence into any reordering. In other words, the transition system on its own could also linearize the tree by taking a random permutation as input. However, due to the noisy input order, it is very difficult for the LSTM model to learn good representations for the stack and buffer and predict correct transitions (cf. Vinyals et al. (2015) for the discussion on encoding a set with an LSTM). In contrast, when we only use this system to reorder a linearized projective tree as postprocessing, where input sequence is meaningful and consistent, it is much easier to learn. Using the swap system as a post-processing step stands in contrast to Bohnet et al. (2012), where they pre-process the tree by lifting the arcs so that the correct word order could form a projective tree. These two approaches draw inspiration from the non-projective parsing in Nivre (2009) and the pseudo-projective parsing in Nivre and Nilsson (2005) respectively. We argue that our post-processing approach is more convenient since there is no need to change the syntactic annotation in the original tree, and it is much easier to evaluate the effectiveness of the sorting model. In the SR'19 dataset, some relative word order information is given, which indicates e.g. the order of the conjuncts in the coordination. Since the order in a coordination is generally arbitrary (at least syntactically), it will thus introduce randomness in the single reference evaluation. We believe that using such information leads to more accurate evaluation, and therefore by default always use these constraints in the comparison. The constraints does not specify direct adjacency, but only general precedence relations. For example, to order the nodes { 1 , 2 , 3 , 4 , 5 } with the constraint 2  3  1 and 4  5 , a valid sequence could be [2 , 4 , 3 , 5 , 1] , while [4 , 5 , 2 , 1 , 3] is invalid. To incorporate such constraints in the solver, we introduce an additional variable associated with each node in the routing problem, where the value is incremented by 1 after each step. In other words, if a node is visited in the n -th step, then the associated variable will have the value n . Then we add inequality constraints about those variables that are specified in the word order information into the routing problem and let the solver find the path that satisfies the constraints. In practice, the solver can always find a solution to linearize the subtrees with the constraints. However, it sometimes cannot find any solution to directly linearize the full tree within the time limit (1-10% of the cases depending on the treebank), because there are more nodes and more constraints in the full tree. In this case, we simply remove the constraints and rerun the solver. We use the datasets from the Surface Realization 2019 Shared Task (Mille et al., 2019) in our experiments, which includes 11 languages in 20 treebanks from the Universal Dependencies (Nivre et al., 2016). We experiment on the shallow track, i.e., all tokens in the output are present in the input tree. We only report the BLEU score (Pap-ineni et al., 2002) as the evaluation metric, since we mostly evaluate on the lemma level, where the metrics involving word forms are irrelevant. As baselines for the final evaluation, we use several available linearizers by Bohnet et al. (2010) (B10), Puduppully et al. (2016) (P16) and Yu et al. (2019a) (Y19). B10, P16 and our linearizer all use the same inflection and contraction models, trained with the same hyperparameters as in Y19, and we compare to the reported shared task results of Y19. Table 2 shows the performance of different linearizers, where beam is the baseline beam-search linearizer as in Yu et al. (2019b) with default hyperparameters, full is the TSP decoder on the full tree level, sub is the TSP decoder on the subtree level, and +swap is sub post-processed with reordering. We test the decoders under two conditions: without word order constraints ( -constraints ) and with word order constraints ( +constraints ). Columns 2-9 show the BLEU scores on lemmata on the development set, and in the last 4 columns are the BLEU scores on inflected and contracted word forms on the test sets with the official evaluation script of SR'19. While both only generating projective sentences, the sub decoder outperforms the baseline beam decoder by 0.6 BLEU points without word order constraints and 0.3 BLEU points with constraints. Note that the beam search decoder uses an LSTM to score the sequences, which is essentially an unlimited language model, while the TSP decoders only uses a bigram language model. While comparing the two TSP decoders, sub performs on average higher than full , while full performs better on treebanks with more nonprojective sentences, since it is not restricted. Without word order constraints, full even slightly outperforms sub . The reason that full performs relatively worse with constraints is that it sometimes has to remove the constraints to find a solution. The sub+swap decoder eliminates the projectivity restriction, closing the performance gap to full for non-projective treebanks, and it does not hurt the performance on the projective treebanks. In the last four columns we compare our sub+swap linearizer on the test set for the full pipeline with three external baselines, including the best system in the SR'19 shared task (Y19). Our system outperforms B10 and P16 by a large margin of 7 and 11 BLEU points. Note that their off-the-shelf systems are not designed to use word order constraints and morphological tags, which would account for a difference of about 3 points (see the effect of constraints in Table 2 and feature ablation in  3.7). Under the same condition, our system outperforms Y19 on most of the treebanks and on average by 0.7, because of (1) a better projective decoder and (2) the non-projective postprocessing step. Furthermore, our system is much faster than Y19, see the comparison in  3.8. To illustrate the characteristics of different TSP decoders, we analyze their performance on sentences with different lengths and percentages of non-projective arcs. Figure 4a shows the BLEU score of different TSP decoders with respect to the sentence length, averaged over all sentences in the development sets. The sub model performs quite stably across the sentences with different lengths, while the full model performs much worse on longer sentences. 3 This confirms our hypothesis that the divide-and-conquer strategy of the subtree decoder can reduce search errors for large TSP problems. Postprocessing with the swap system ( tsp+swap ) consistently improvements tsp across all sentence lengths. 3 Note that the very short sentences have even lower BLEU score, this is caused by the smoothing function in the BLEU evaluation, which gives a low score even for exact match. Figure 4b shows the BLEU score with respect to the percentage of non-projective arcs in the gold tree, averaged over all sentences in the development sets. Clearly, sub performs lower than full for sentences with more non-projective arcs due to the projectivity restriction, while the overall BLEU score of sub is higher, since 99% of the arcs and 90% of the sentences are projective. With the help of the swap system, sub+swap closes the gap to full on the non-projective sentences. In sum, the sub+swap model shows clear advantages over the other models since it is less prone to search error due to the reduced TSP size and free from the projectivity restriction, it is thus the best of both worlds. As described in  2.4, we use a greedy training objective to train the biaffine model, namely we calculate a hinge loss of the correct bigram against all other bigrams in the same row and in the same column. This is in contrast to the structured loss, which is calculated between the gold sequence and the predicted sequence. This contrast is similar to the two different training objective in Dozat and Manning (2016) against Kiperwasser and Goldberg (2016) for graph-based dependency parsing. We experiment with the structured loss, following Kiperwasser and Goldberg (2016), where we also apply loss augmented inference (Taskar et al., 2005), i.e., adding a constant for all the bigrams that are not in the gold sequence. We also experiment with only updating against the row or the column, which could be thought of as the bigram language model only in one direction, while updating against both is training a bidirectional language model. Table 3 shows the results, where we train the sub and full models with different objectives: row+col is the default one, row and col only update against the row or the column, and path updates the gold path against the predicted path. The results are clear: for both sub and full models, training on both directions is better than training on one direction, and the greedy objective is better than the structured objective. The gap between the bidirectional greedy objective and others is larger in full than in sub , since full solves a larger TSP, where the greedy training is even more important for effective greedy decoding. As discussed in  2.5, we use the transition system only for post-processing the linearized projective sentences, although the transition system itself is theoretically able to sort a random sequence. The question is whether the model is able to learn to handle the random input. We experiment with different training and testing scenarios of the sorting models. They are trained in three scenarios, namely to sort (1) gold projective sentences into correct (potentially non-projective) sentences, noted as gold ; (2) predicted projective sentences, where the sentences are obtained by 5-fold jackknifing on the training set using the sub model, noted as pred ; and (3) random sequences, where the input is always shuffled during training, noted as rand . The models are then applied to sort (1) gold projective sentences ( gold ); (2) predicted projective sentences from the sub model ( pred ); and (3) random permutation of the tokens ( rand ). In the main experiment, the way we use the transition system corresponds to the gold-pred scenario. Table 4 shows the BLEU scores on the development set averaged over all treebanks. We also show the change of BLEU scores from the input to the output (  BLEU ) in different scenarios. First, the gold model improves the input in all scenarios, especially the gold-pred scenario used in the main experiment brings 0.47 BLEU points improvement. Interestingly, the pred model from jackknifing does not improve the performance, while usually training on the data with erroneous prediction should prevent overfitting to the gold data. We conjecture the reason could be that the model is overfitting to fixing the particular errors in the predicted training data instead of learning to produce non-projective sentences. Purely using the transition system for linearization ( rand-rand ) works to some extent, but performs lower than the baseline by a large gap for several reasons. First, it imposes an arbitrary order in the input which is a suboptimal way to represent a bag of word. Second, learning to sort random permutation requires a lot more training instances to generalize. Finally, it takes on average O ( n 2 ) steps, which also increases the chance of error propagation. In contrast, sorting a projective tree does not have any of these disadvantages. Generally, when the training and testing scenarios are not aligned, the performance is always beam sub full swap +tree 85.55 85.85 85.03 71.36 -tree 78.31 74.17 35.82 19.74  -7.24 -11.68 -49.21 -51.62 Table 5: Comparing the decoders with and without the Tree-LSTM encoder. worse due to the mismatched bias of transitions. For example, gold-rand barely changes the random input since it mostly predicts shift , and rand-gold predicts swap too often such that the outcome is even worse than the input sentence. The success of the simple bigram language model and greedy TSP decoding relies heavily on the Tree-LSTM encoding. To demonstrate its importance, we remove the tree encoding for each linearizer, i.e., they only receive the token level features as the representation. We experiment with four linearizers: apart from beam , sub and full as in the main experiments, we also include the swap linearizer that is trained to sort random input sequences. The condition +tree is the default case, while in -tree we do not use the tree encoding. Note that in the latter case, beam and sub still use the tree information to split the tree into subtrees, while full and swap do not use the tree information in any way. The results are shown in Table 5. Without the tree encoder, the performance drop in sub is larger than beam , which suggests that sub is more dependent on the good representation of the Tree-LSTM encoder, since its scoring function is essentially a bigram language model, which would be much less expressive than the LSTM in beam if syntax is absent. This result draws an interesting analogy to the fact that first-order graph-based dependency parsers (Kiperwasser and Goldberg, 2016; Dozat and Manning, 2016) also outperform the transition-based counterparts with a simpler scoring model but without error propagation. The much larger drop in full and swap emphasizes the importance of the inductive bias introduced by the divide-and-conquer strategy, since natural languages are predominantly projective. Generally, the syntax ablation experiment highlights the crucial difference between our work and the original idea by Knight (1999), namely we use contextualized bigrams in our TSP model, which is much more expressive than the vanilla version. Consider the subtree with the words this and with in Figure 1, a vanilla bigram model would calculate a much higher score for with this than this with, while a contextualized bigram model could be aware that it is part of a rather special syntactic construction in English. To understand how much each feature contributes to the linearization task, we perform ablation experiments on the selection of features. In the default setting of our models, we use the lemma, UPOS, dependency relation, and morphological tags to encode each token. We experiment with turning off each feature for the sub linearizer, as well as only using one feature, and the results are in Table 6. The results suggest that the UPOS tags and morphological tags do not provide much additional information and could be dropped if simplicity is desired. In contrast, the lemmata and dependency relations are crucial to determine the word order, since the performance drops considerably without them. By default, we use a greedy TSP solver, which already yields satisfactory performance. We then make additional experiments with a more optimized metaheuristic (guided local search) to see if better performance can be gained in exchange for more decoding time. With the guided local search, we set the search limit to 1 second or 100 solutions for each subtree, and 10 seconds or 1000 solutions for the full tree. We also compare to the beam search linearizer with varying beam sizes from 1 to 64. The results are shown in Figure 5, where the decoding time is measured on a single CPU core. Generally, all greedy TSP solvers outperform the Pareto front of the beam search decoders. The greedy solver performs almost as well as the optimized solver for the subtree TSP (85.85 vs. 85.91), while it performs clearly worse for the full tree 10 2 10 3 80 82 84 86 b-1 b-2 b-4 b-8 b-16 b-32 b-64 sub-greedy sub-guided sub-greedy-swap full-greedy full-guided Time [ms/sentence] BLEU s c o r e Figure 5: The speed (on a log scale) and BLEU score for different decoders, where the dots are projective decoders, and the crosses are non-projective decoders. TSP (85.03 vs. 85.85). This contrast again demonstrates that the divide-and-conquer strategy indeed greatly simplifies the problem for the greedy solver. Post-processing with the swap system only slightly increase the decoding time (in total 50ms per sen-tence), but considerably improves the performance. In this paper, we revisit the idea of treating word ordering as a TSP, but unlike the common bag-of-words scenario, the words have an underlying syntactic structure. We demonstrate that with the Tree-LSTM encoder, the biaffine scoring model, the divide-and-conquer strategy, and a transition-based sorting system, we can linearize a dependency tree with high speed and quality and without the projectivity restriction. We show with various ablation experiments that all of the components are crucial for the success of the TSP-based linearizer. Our work emphasizes the importance of syntax in the word ordering task. We discussed many connections and similarities between linearization and parsing. We believe that quite generally, systems for solving one task can benefit from the other task's view on syntactic structure. One possibility to capitalize on these synergies is to explore data augmentation methods to select beneficial extra training data in an unsupervised fashion. This work was in part supported by funding from the Ministry of Science, Research and the Arts of the State of Baden-Wurttemberg (MWK), within the CLARIN-D research project.
objective method objective result objective abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain objective method method method objective method method abstain method abstain abstain method abstain method abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain method other other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain method abstain abstain abstain abstain method abstain method method method other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method other other method other other abstain other abstain other other method abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain result result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain result abstain abstain abstain result abstain abstain abstain abstain other abstain abstain abstain abstain objective result objective abstain objective abstain other