{'fraction_non_alphanumeric': 0.03062381852551985, 'fraction_numerical': 0.012896450325561857, 'mean_word_length': 4.886745796241345, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Memory-Based Dependency Parsing

This paper reports the results of experiments using memory-based learning to guide a deterministic dependency parser for unrestricted natural language text. Using data from a small treebank of Swedish, memory-based classifiers for predicting the next action of the parser are constructed. The accuracy of a classifier as such is evaluated on held-out data derived from the treebank, and its performance as a parser guide is evaluated by parsing the held-out portion of the treebank. The evaluation shows that memory-based learning gives a significant improvement over a previous probabilistic model based on maximum conditional likelihood estimation and that the inclusion of lexical features improves the accuracy even further.


Introduction
Deterministic dependency parsing has recently been proposed as a robust and efficient method for syntactic parsing of unrestricted natural language text (Yamada and Matsumoto, 2003;Nivre, 2003). Dependency parsing means that the goal of the parsing process is to construct a dependency graph, of the kind depicted in Figure 1. Deterministic parsing means that we always derive a single analysis for each input string. Moreover, this single analysis is derived in a monotonic fashion with no redundancy or backtracking, which makes it possible to parse natural language sentences in linear time (Nivre, 2003).
In this paper, we report experiments using memorybased learning (Daelemans, 1999) to guide the parser described in Nivre (2003), using data from a small treebank of Swedish (Einarsson, 1976). Unlike most previous work on data-driven dependency parsing (Eisner, 1996;Yamada and Matsumoto, 2003;Nivre, 2003), we assume that dependency graphs are labeled with dependency types, although the evaluation will give results for both labeled and unlabeled representations.
The paper is structured as follows. Section 2 gives the necessary background definitions and introduces the idea of guided parsing as well as memory-based learning. Section 3 describes the data used in the experiments, the evaluation metrics, and the models and algorithms used in the learning process. Results from the experiments are given in section 4, while conclusions and suggestions for further research are presented in section 5.

Dependency Graphs
The linguistic tradition of dependency grammar comprises a large and fairly diverse family of theories and formalisms that share certain basic assumptions about syntactic structure, in particular the assumption that syntactic structure consists of lexical nodes linked by binary relations called dependencies (see, e.g., Tesnière (1959), Sgall (1986), Mel'čuk (1988), Hudson (1990)). Thus, the common formal property of dependency structures, as compared to the representations based on constituency (or phrase structure), is the lack of nonterminal nodes.
In a dependency structure, every word token is dependent on at most one other word token, usually called its head or regent, which means that the structure can be represented as a directed graph, with nodes representing word tokens and arcs representing dependency relations. In addition, arcs may be labeled with specific dependency types. Figure 1 shows a labeled dependency graph for a simple Swedish sentence, where each word of the sentence is labeled with its part of speech and each arc labeled with a grammatical function.
Formally, we define dependency graphs in the following way: We write w i < w j to express that w i precedes w j in the string W (i.e., i < j); we write w i r → w j to say that there is an arc from w i to w j labeled r, and w i → w j to say that there is an arc from w i to w j (regardless of the label); we use → * to denote the reflexive and transitive closure of the unlabeled arc relation; and we use ↔ and ↔ * for the corresponding undirected relations, i.e. w i ↔ w j iff w i → w j or w j → w i . 3. A dependency graph D = (W, A) is well-formed iff the five conditions given in Figure 2 are satisfied.
For a more detailed discussion of dependency graphs and well-formedness conditions, the reader is referred to Nivre (2003).

Parsing Algorithm
The parsing algorithm presented in Nivre (2003) is in many ways similar to the basic shift-reduce algorithm for context-free grammars (Aho et al., 1986), although the parse actions are different given that no nonterminal symbols are used. Moreover, unlike the algorithm of Yamada and Matsumoto (2003), the algorithm considered here actually uses a blend of bottom-up and top-down processing, constructing left-dependencies bottom-up and rightdependencies top-down, in order to achieve incrementality. For a similar but nondeterministic approach to dependency parsing, see Obrebski (2003). Parser configurations are represented by triples S, I, A , where S is the stack (represented as a list), I is the list of (remaining) input tokens, and A is the (current) arc relation for the dependency graph. Given an input string W , the parser is initialized to nil, W, ∅ and terminates when it reaches a configuration S, nil, A (for any list S and set of arcs A). The input string W is accepted if the dependency graph D = (W, A) given at termination is well-formed; otherwise W is rejected. The behavior of the parser is defined by the transitions defined in Figure  3 (where w i , w j and w k are arbitrary word tokens, and r and r are arbitrary dependency relations): 1. The transition Left-Arc (LA) adds an arc w j r → w i from the next input token w j to the token w i on top of the stack and reduces (pops) w i from the stack.
2. The transition Right-Arc (RA) adds an arc w i r → w j from the token w i on top of the stack to the next input token w j , and shifts (pushes) w j onto the stack.
3. The transition Reduce (RE) reduces (pops) the token w i on top of the stack.
4. The transition Shift (SH) shifts (pushes) the next input token w i onto the stack.
The transitions Left-Arc and Right-Arc are subject to conditions that ensure that the graph conditions Unique label and Single head are satisfied. By contrast, the Reduce transition can only be applied if the token on top of the stack already has a head. For Shift, the only condition is that the input list is non-empty.
As it stands, this transition system is nondeterministic, since several transitions can often be applied to the same configuration. Thus, in order to get a deterministic parser, we need to introduce a mechanism for resolving transition conflicts. Regardless of which mechanism is used, the parser is guaranteed to terminate after at most 2n transitions, given an input string of length n (Nivre, 2003). This means that as long as transitions can be performed in constant time, the running time of the parser will be linear in the length of the input. Moreover, the parser is guaranteed to produce a dependency graph that is acyclic and projective (and satisfies the unique-label and single-head constraints). This means that the dependency graph given at termination is well-formed if and only if it is connected (Nivre, 2003).

Unique label
Figure 2: Well-formedness conditions on dependency graphs

Guided Parsing
One way of turning a nondeterministic parser into a deterministic one is to use a guide (or oracle) that can inform the parser at each nondeterministic choice point; cf. Kay (2000), Boullier (2003). Guided parsing is normally used to improve the efficiency of a nondeterministic parser, e.g. by letting a simpler (but more efficient) parser construct a first analysis that can be used to guide the choice of the more complex (but less efficient) parser. This is the approach taken, for example, in Boullier (2003). In our case, we rather want to use the guide to improve the accuracy of a deterministic parser, starting from a baseline of randomized choice. One way of doing this is to use a treebank, i.e. a corpus of analyzed sentences, to train a classifier that can predict the next transition (and dependency type) given the current configuration of the parser. However, in order to maintain the efficiency of the parser, the classifier must also be implemented in such a way that each transition can still be performed in constant time.
Previous work in this area includes the use of memorybased learning to guide a standard shift-reduce parser (Veenstra and Daelemans, 2000) and the use of support vector machines to guide a deterministic dependency parser (Yamada and Matsumoto, 2003). In the experiments reported in this paper, we apply memorybased learning within a deterministic dependency parsing framework.

Memory-Based Learning
Memory-based learning and problem solving is based on two fundamental principles: learning is the simple storage of experiences in memory, and solving a new problem is achieved by reusing solutions from similar previously solved problems (Daelemans, 1999). It is inspired by the nearest neighbor approach in statistical pattern recognition and artificial intelligence (Fix and Hodges, 1952), as well as the analogical modeling approach in linguistics (Skousen, 1989;Skousen, 1992). In machine learning terms, it can be characterized as a lazy learning method, since it defers processing of input until needed and processes input by combining stored data (Aha, 1997).
Memory-based learning has been successfully applied to a number of problems in natural language processing, such as grapheme-to-phoneme conversion, partof-speech tagging, prepositional-phrase attachment, and base noun phrase chunking (Daelemans et al., 2002). Most relevant in the present context is the use of memorybased learning to predict the actions of a shift-reduce parser, with promising results reported in Veenstra and Daelemans (2000).
The main reason for using memory-based learning in the present context is the flexibility offered by similaritybased extrapolation when classifying previously unseen configurations, since previous experiments with a probabilistic model has shown that a fixed back-off sequence does not work well in this case (Nivre, 2004). Moreover, the memory-based approach can easily handle multi-class classification, unlike the support vector machines used by Yamada and Matsumoto (2003).
For the experiments reported in this paper, we have used the software package TiMBL (Tilburg Memory Based Learner), which provides a variety of metrics, algorithms, and extra functions on top of the classical k nearest neighbor classification kernel, such as value distance metrics and distance weighted class voting (Daelemans et al., 2003).

Target Function and Approximation
The function we want to approximate is a mapping f from parser configurations to parser actions, where each action consists of a transition and (unless the transition is Shift or Reduce) a dependency type: Here Config is the set of all possible parser configurations and R is the set of dependency types as before. However, in order to make the problem tractable, we try to learn a functionf whose domain is a finite space of parser states, which are abstractions over configurations. For this purpose we define a number of features that can be used to define different models of parser state. The features used in this study are listed in Table 1.
The first five features (TOP-TOP.RIGHT) deal with properties of the token on top of the stack. In addition to the word form itself (TOP), we consider its part-of-speech (as assigned by an automatic part-of-speech tagger in a preprocessing phase), the dependency type by which it is related to its head (which may or may not be available in a given configuration depending on whether the head is to the left or to the right of the token in question), and the dependency types by which it is related to its leftmost and rightmost dependent, respectively (where the current rightmost dependent may or may not be the rightmost dependent in the complete dependency tree).
The following three features (NEXT-NEXT.LEFT) refer to properties of the next input token. In this case, there are no features corresponding to TOP.DEP and TOP.RIGHT, since the relevant dependencies can never be present at decision time. The final feature (LOOK) is a simple lookahead, using the part-of-speech of the next plus one input token.
In the experiments reported below, we have used two different parser state models, one called the lexical model, which includes all nine features, and one called the non-lexical model, where the two lexical features TOP and NEXT are omitted. For both these models, we have used memory-based learning with different parameter settings, as implemented TiMBL.
For comparison, we have included an earlier classifier that uses the same features as the non-lexical model, but where prediction is based on maximum conditional likelihood estimation. This classifier always predicts the most probable transition given the state and the most probable dependency type given the transition and the state, with conditional probabilities being estimated by the empirical distribution in the training data. Smoothing is performed only for zero frequency events, in which case the classifier backs off to more general models by omitting first the features TOP.LEFT and LOOK and then the features TOP.RIGHT and NEXT.LEFT; if even this does not help, the classifier predicts Reduce if permissible and Shift otherwise. This model, which we will refer to as the MCLE model, is described in more detail in Nivre (2004).

Data
It is standard practice in data-driven approaches to natural language parsing to use treebanks both for training and evaluation. Thus, the Penn Treebank of American English (Marcus et al., 1993) has been used to train and evaluate the best available parsers of unrestricted English text (Collins, 1999;Charniak, 2000). One problem when developing a parser for Swedish is that there is no comparable large-scale treebank available for Swedish.
For the experiments reported in this paper we have used a manually annotated corpus of written Swedish, created at Lund University in the 1970's and consisting mainly of informative texts from official sources (Einarsson, 1976). Although the original annotation scheme is an eclectic combination of constituent structure, dependency structure, and topological fields (Teleman, 1974), it has proven possible to convert the annotated sentences to dependency graphs with fairly high accuracy.
In the conversion process, we have reduced the original fine-grained classification of grammatical functions to a more restricted set of 16 dependency types, which are listed in Table 2. We have also replaced the original (manual) part-of-speech annotation by using the same automatic tagger that is used for preprocessing in the parser. This is a standard probabilistic tagger trained on the Stockholm-Umeå Corpus of written Swedish (SUC, 1997) and found to have an accuracy of 95-96% when tested on held-out data.
Since the function we want to learn is a mapping from parser states to transitions (and dependency types), the treebank data cannot be used directly as training and test The part-of-speech of the next plus one input token Table 1: Parser state features data. Instead, we have to simulate the parser on the treebank in order to derive, for each sentence, the transition sequence corresponding to the correct dependency tree. Given the result of this simulation, we can construct a data set consisting of pairs s, t , where s is a parser state and t is the correct transition from that state (including a dependency type if applicable). Unlike standard shiftreduce parsing, the simulation of the current algorithm is almost deterministic and is guaranteed to be correct if the input dependency tree is well-formed.
The complete converted treebank contains 6316 sentences and 97623 word tokens, which gives a mean sentence length of 15.5 words. The treebank has been divided into three non-overlapping data sets: 80% for training 10% for development/validation, and 10% for final testing (random samples). The results presented below are all from the validation set. (The final test set has not been used at all in the experiments reported in this paper.) When talking about test and validation data, we make a distinction between the sentence data, which refers to the original annotated sentences in the treebank, and the transition data, which refers to the transitions derived by simulating the parser on these sentences. While the sentence data for validation consists of 631 sentences, the corresponding transition data contains 15913 instances. For training, only transition data is relevant and the training data set contains 371977 instances.

Evaluation
The output of the memory-based learner is a classifier that predicts the next transition (including dependency type), given the current state of the parser. The quality of this classifier has been evaluated with respect to both prediction accuracy and parsing accuracy.
Prediction accuracy refers to the quality of the classifier as such, i.e. how well it predicts the next transition given the correct parser state, and is measured by the classification accuracy on unseen transition data (using a 0-1 loss function). We use McNemar's test for statistical significance.
Parsing accuracy refers to the quality of the classifier as a guide for the deterministic parser and is measured by the accuracy obtained when parsing unseen sentence data. More precisely, parsing accuracy is measured by the attachment score, which is a standard measure used in studies of dependency parsing (Eisner, 1996;. The attachment score is computed as the proportion of tokens (excluding punctuation) that are assigned the correct head (or no head if the token is a root). Since parsing is a sentence-level task, we believe that the overall attachment score should be computed as the mean attachment score per sentence, which gives an estimate of the expected attachment score for an arbitrary sentence. However, since most previous studies instead use the mean attachment score per word (Eisner, 1996;, we will give this measure as well. In order to measure label accuracy, we also define a labeled attachment score, where both the head and the label must be correct, but which is otherwise computed in the same way as the ordinary (unlabeled) attachment score. For parsing accuracy, we use a paired t-test for statistical significance. Table 3 shows the prediction accuracy achieved with memory-based learning for the lexical and non-lexical model, with two different parameter settings for the learner. The results in the first column were obtained with the default settings of the TiMBL package, in particular:
• The overlap distance metric.
• Features weighted by Gain Ratio (Quinlan, 1993   The second column shows the accuracy for the best parameter settings found in the experiments (averaged over both models), which differ from the default in the following respects: • Overlap metric replaced by the modified value distance metric (MVDM) (Stanfill and Waltz, 1986;Cost and Salzberg, 1993).
• No weighting of features.
For more information about the different parameters and settings, the reader is referred to Daelemans et al. (2003).
The results show that the lexical model performs consistently better than the non-lexical model, and that the difference increases with the optimization of the learning algorithm (all differences being significant at the .0001 level according to McNemar's test). This confirms previous results from statistical parsing indicating that lexical information is crucial for disambiguation (Collins, stances that are equally distant to the test instance. This is different from the original IB1 algorithm, as described in Aha et al. (1991Aha et al. ( ). 1999Charniak, 2000). As regards optimization, we may note that although there is a significant improvement for both models, the magnitude of the difference is relatively small. Table 4 shows the parsing accuracy obtained with the optimized versions of the MBL models (lexical and nonlexical), compared to the MCLE model described in section 3. We see that MBL outperforms the MCLE model even when limited to the same features (all differences again being significant at the .0001 level according to a paired t-test). This can probably be explained by the fact that the similarity-based smoothing built into the memory-based approach gives a better extrapolation than the fixed back-off sequence in the MCLE model. We also see that the lexical MBL model outperforms both the other models. If we compare the labeled attachment score to the prediction accuracy (which also takes dependency types into account), we observe a substantial drop (from 89.7 to 81.7 for the lexical model, from 87.4 to 76.5 for the non-lexical model), which is of course only to be expected. The unlabeled attachment score is naturally higher, and it is worth noting that the relative difference between the MBL lexical model and the other two models is much smaller. This indicates that the advantage of the lexical model mainly concerns the accuracy in predicting dependency type in addition to transition.  If we compare the results concerning parsing accuracy to those obtained for other languages (given that there are no comparable results available for Swedish), we note that the best unlabeled attachment score is lower than for English, where the best results are above 90% (attachment score per word) Yamada and Matsumoto, 2003), but higher than for Czech (Collins et al., 1999). This is encouraging, given that the size of the training set in our experiments is fairly small, only about 10% of the standard training set for the Penn Treebank. One reason why our results nevertheless compare reasonably well with those obtained with the much larger training set is probably that the conversion to dependency trees is more accurate for the Swedish treebank, given the explicit annotatation of grammatical functions. Moreover, the fact that our parser uses labeled dependencies is probably also significant, since the possibility of using information from previously assigned (labeled) dependencies during parsing seems to have a positive effect on accuracy (Nivre, 2004).

Model
Finally, it may be interesting to consider the accuracy for individual dependency types. Table 5 gives labeled precision, labeled recall and unlabeled attachment score for four of the most important types with the MBL lexical model. The results indicate that subjects have the highest accuracy, especially when labels are taken into account. Objects and predicative complements have comparable attachment accuracy, but are more often misclassified with respect to dependency type. For adverbial modifiers, finally, attachment accuracy is lower than for the other dependency types, which is largely due to the notorious PP-attachment problem.

Conclusion
In this paper we have shown that a combination of memory-based learning and deterministic dependency parsing can be used to construct a robust and efficient parser for unrestricted natural language text, achieving a parsing accuracy which is close to the state of the art even with relatively limited amounts of training data. Classifiers based on memory-based learning achieve higher parsing accuracy than previous probabilistic models, and the improvement increases if lexical information is added to the model.
Suggestions for further research includes the further exploration of alternative models and parameter settings, but also the combination of inductive and analytical learning to impose high-level linguistic constraints, and the development of new parsing methods (e.g. involving multiple passes over the data). In addition, it is important to evaluate the approach with respect to other languages and corpora in order to increase the comparability with other approaches.