text: <PAPER>
  	<S sid="0">Deterministic Dependency Parsing Of English Text</S><ABSTRACT>
  		<S sid="1" ssid="1">This paper presents a deterministic dependency parser based on memory-based learning, which parses English text in linear time.</S>
  		<S sid="2" ssid="2">When trainedand evaluated on the Wall Street Journal sec tion of the Penn Treebank, the parser achieves a maximum attachment score of 87.1%.</S>
  		<S sid="3" ssid="3">Unlikemost previous systems, the parser produces la beled dependency graphs, using as arc labels a combination of bracket labels and grammaticalrole labels taken from the Penn Treebank II annotation scheme.</S>
  		<S sid="4" ssid="4">The best overall accuracy ob tained for identifying both the correct head and the correct arc label is 86.0%, when restricted to grammatical role labels (7 labels), and 84.4% for the maximum set (50 labels).</S>
  	</ABSTRACT>
  	<SECTION title="Introduction" number="1">
  			<S sid="5" ssid="5">There has been a steadily increasing interest in syntactic parsing based on dependency analysis in re cent years.</S>
  			<S sid="6" ssid="6">One important reason seems to be thatdependency parsing offers a good compromise be tween the conflicting demands of analysis depth, on the one hand, and robustness and efficiency, on the other.</S>
  			<S sid="7" ssid="7">Thus, whereas a complete dependency structure provides a fully disambiguated analysisof a sentence, this analysis is typically less complex than in frameworks based on constituent analysis and can therefore often be computed determin istically with reasonable accuracy.</S>
  			<S sid="8" ssid="8">Deterministicmethods for dependency parsing have now been ap plied to a variety of languages, including Japanese (Kudo and Matsumoto, 2000), English (Yamada and Matsumoto, 2003), Turkish (Oflazer, 2003), and Swedish (Nivre et al, 2004).</S>
  			<S sid="9" ssid="9">For English, the interest in dependency parsing has been weaker than for other languages.</S>
  			<S sid="10" ssid="10">To some extent, this can probably be explained by the strong tradition of constituent analysis in Anglo-American linguistics, but this trend has been reinforced by the fact that the major treebank of American English,the Penn Treebank (Marcus et al, 1993), is anno tated primarily with constituent analysis.</S>
  			<S sid="11" ssid="11">On the other hand, the best available parsers trained on thePenn Treebank, those of Collins (1997) and Charniak (2000), use statistical models for disambigua tion that make crucial use of dependency relations.</S>
  			<S sid="12" ssid="12">Moreover, the deterministic dependency parser of Yamada and Matsumoto (2003), when trained on the Penn Treebank, gives a dependency accuracy that is almost as good as that of Collins (1997) and Charniak (2000).</S>
  			<S sid="13" ssid="13">The parser described in this paper is similar to that of Yamada and Matsumoto (2003) in that it uses a deterministic parsing algorithm in combination with a classifier induced from a treebank.</S>
  			<S sid="14" ssid="14">However, there are also important differences between the twoapproaches.</S>
  			<S sid="15" ssid="15">First of all, whereas Yamada and Matsumoto employs a strict bottom-up algorithm (es sentially shift-reduce parsing) with multiple passes over the input, the present parser uses the algorithmproposed in Nivre (2003), which combines bottom up and top-down processing in a single pass in order to achieve incrementality.</S>
  			<S sid="16" ssid="16">This also means that the time complexity of the algorithm used here is linearin the size of the input, while the algorithm of Ya mada and Matsumoto is quadratic in the worst case.</S>
  			<S sid="17" ssid="17">Another difference is that Yamada and Matsumoto use support vector machines (Vapnik, 1995), whilewe instead rely on memory-based learning (Daele mans, 1999).</S>
  			<S sid="18" ssid="18">Most importantly, however, the parser presented in this paper constructs labeled dependency graphs, i.e. dependency graphs where arcs are labeled with dependency types.</S>
  			<S sid="19" ssid="19">As far as we know, this makesit different from all previous systems for dependency parsing applied to the Penn Treebank (Eis ner, 1996; Yamada and Matsumoto, 2003), althoughthere are systems that extract labeled grammatical relations based on shallow parsing, e.g. Buchholz (2002).</S>
  			<S sid="20" ssid="20">The fact that we are working with labeled dependency graphs is also one of the motivations for choosing memory-based learning over sup port vector machines, since we require a multi-class classifier.</S>
  			<S sid="21" ssid="21">Even though it is possible to use SVMfor multi-class classification, this can get cumber some when the number of classes is large.</S>
  			<S sid="22" ssid="22">(For the The   ? DEP finger-pointing   ? NP-SBJ has already   ? ADVP begun   ? VP . ?   DEP Figure 1: Dependency graph for English sentenceunlabeled dependency parser of Yamada and Matsumoto (2003) the classification problem only in volves three classes.)</S>
  			<S sid="23" ssid="23">The parsing methodology investigated here haspreviously been applied to Swedish, where promis ing results were obtained with a relatively smalltreebank (approximately 5000 sentences for train ing), resulting in an attachment score of 84.7% and a labeled accuracy of 80.6% (Nivre et al, 2004).1 However, since there are no comparable resultsavailable for Swedish, it is difficult to assess the significance of these findings, which is one of the reasons why we want to apply the method to a bench mark corpus such as the the Penn Treebank, even though the annotation in this corpus is not ideal for labeled dependency parsing.The paper is structured as follows.</S>
  			<S sid="24" ssid="24">Section 2 describes the parsing algorithm, while section 3 ex plains how memory-based learning is used to guidethe parser.</S>
  			<S sid="25" ssid="25">Experimental results are reported in sec tion 4, and conclusions are stated in section 5.</S>
  	</SECTION>
  	<SECTION title="Deterministic Dependency Parsing. " number="2">
  			<S sid="26" ssid="1">In dependency parsing the goal of the parsing pro cess is to construct a labeled dependency graph of the kind depicted in Figure 1.</S>
  			<S sid="27" ssid="2">In formal terms, we define dependency graphs as follows: 1.</S>
  			<S sid="28" ssid="3">Let R = {r1, . . .</S>
  			<S sid="29" ssid="4">, rm} be the set of permissible.</S>
  			<S sid="30" ssid="5">dependency types (arc labels).</S>
  			<S sid="31" ssid="6">2.</S>
  			<S sid="32" ssid="7">A dependency graph for a string of words W = w1?</S>
  			<S sid="33" ssid="8">?wn is a labeled directed graph D = (W,A), where (a) W is the set of nodes, i.e. word tokens in the input string, (b) A is a set of labeled arcs (wi, r, wj) (wi, wj ? W , r ? R), (c) for every wj ? W , there is at most one arc (wi, r, wj) ? A.1The attachment score only considers whether a word is as signed the correct head; the labeled accuracy score in additionrequires that it is assigned the correct dependency type; cf.</S>
  			<S sid="34" ssid="9">sec tion 4.</S>
  			<S sid="35" ssid="10">acyclic, projective and connected.</S>
  			<S sid="36" ssid="11">For a more detailed discussion of dependency graphs and well-formedness conditions, the reader is referred to Nivre (2003).The parsing algorithm used here was first de fined for unlabeled dependency parsing in Nivre (2003) and subsequently extended to labeled graphsin Nivre et al (2004).</S>
  			<S sid="37" ssid="12">Parser configurations are rep resented 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.</S>
  			<S sid="38" ssid="13">(Since in a dependencygraph the set of nodes is given by the input tokens, only the arcs need to be represented explicitly.)</S>
  			<S sid="39" ssid="14">Given an input string W , the parser is initial ized to ?nil,W, ??2 and terminates when it reaches a configuration ?S,nil, A?</S>
  			<S sid="40" ssid="15">(for any list S and set ofarcs A).</S>
  			<S sid="41" ssid="16">The input string W is accepted if the de pendency graph D = (W,A) given at termination is well-formed; otherwise W is rejected.</S>
  			<S sid="42" ssid="17">Given an arbitrary configuration of the parser, there are four possible transitions to the next configuration (where t is the token on top of the stack, n is the next input token, w is any word, and r, r?</S>
  			<S sid="43" ssid="18">R): 1.</S>
  			<S sid="44" ssid="19">Left-Arc: In a configuration ?t|S,n|I,A?, if.</S>
  			<S sid="45" ssid="20">there is no arc (w, r, t) ? A, extend A with(n, r?, t) and pop the stack, giving the configu ration ?S,n|I,A?{(n, r?, t)}?.</S>
  			<S sid="46" ssid="21">2.</S>
  			<S sid="47" ssid="22">Right-Arc: In a configuration ?t|S,n|I,A?, if.</S>
  			<S sid="48" ssid="23">there is no arc (w, r, n) ? A, extend A with (t, r?, n) and push n onto the stack, giving the configuration ?n|t|S,I,A?{(t, r?, n)}?.</S>
  	</SECTION>
  	<SECTION title="Reduce: In a configuration ?t|S,I,A?, if there. " number="3">
  			<S sid="49" ssid="1">is an arc (w, r, t)?A, pop the stack, giving the configuration ?S,I,A?.</S>
  	</SECTION>
  	<SECTION title="Shift: In a configuration ?S,n|I,A?, push. " number="4">
  			<S sid="50" ssid="1">n onto the stack, giving the configuration ?n|S,I,A?.</S>
  			<S sid="51" ssid="2">2We use nil to denote the empty list and a|A to denote a list with head a and tail A. TH.POS   ? T.DEP . . .</S>
  			<S sid="52" ssid="3">TL.POS   ? TL.DEP . . .</S>
  			<S sid="53" ssid="4">T.POS T.LEX   ? TR.DEP . . .</S>
  			<S sid="54" ssid="5">TR.POS . . .</S>
  			<S sid="55" ssid="6">NL.POS   ? NL.DEP . . .</S>
  			<S sid="56" ssid="7">N.POS N.LEX L1.POS L2.POS L3.POS T = Top of the stack N = Next input token TL = Leftmost dependent of T TR = Rightmost dependent of T NL = Leftmost dependent of N Li = Next plus i input token X.LEX = Word form of X X.POS = Part-of-speech of X X.DEP = Dependency type of X Figure 2: Parser state featuresAfter initialization, the parser is guaranteed to ter minate after at most 2n transitions, given an input string of length n (Nivre, 2003).</S>
  			<S sid="57" ssid="8">Moreover, the parser always constructs a dependency graph that isacyclic and projective.</S>
  			<S sid="58" ssid="9">This means that the depen dency graph given at termination is well-formed if and only if it is connected (Nivre, 2003).</S>
  			<S sid="59" ssid="10">Otherwise, it is a set of connected components, each of which is a well-formed dependency graph for a substring of the original input.The transition system defined above is nondeterministic in itself, since several transitions can often be applied in a given configuration.</S>
  			<S sid="60" ssid="11">To con struct deterministic parsers based on this system,we use classifiers trained on treebank data in or der to predict the next transition (and dependency type) given the current configuration of the parser.</S>
  			<S sid="61" ssid="12">In this way, our approach can be seen as a form ofhistory-based parsing (Black et al, 1992; Mager man, 1995).</S>
  			<S sid="62" ssid="13">In the experiments reported here, we use memory-based learning to train our classifiers.</S>
  			<S sid="63" ssid="14">3 Memory-Based Learning.</S>
  			<S sid="64" ssid="15">Memory-based learning and problem solving is based on two fundamental principles: learning is thesimple storage of experiences in memory, and solv ing a new problem is achieved by reusing solutionsfrom similar previously solved problems (Daele mans, 1999).</S>
  			<S sid="65" ssid="16">It is inspired by the nearest neighborapproach in statistical pattern recognition and arti ficial intelligence (Fix and Hodges, 1952), as well as the analogical modeling approach in linguistics(Skousen, 1989; Skousen, 1992).</S>
  			<S sid="66" ssid="17">In machine learning terms, it can be characterized as a lazy learning method, since it defers processing of input un til needed and processes input by combining stored data (Aha, 1997).</S>
  			<S sid="67" ssid="18">Memory-based learning has been successfully applied to a number of problems in natural languageprocessing, such as grapheme-to-phoneme conver sion, part-of-speech tagging, prepositional-phraseattachment, and base noun phrase chunking (Daele mans et al, 2002).</S>
  			<S sid="68" ssid="19">Previous work on memory-based learning for deterministic parsing includes Veenstra and Daelemans (2000) and Nivre et al (2004).</S>
  			<S sid="69" ssid="20">For the experiments reported in this paper, we have used the software package TiMBL (TilburgMemory Based Learner), which provides a vari ety 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).The function we want to approximate is a map ping f from configurations to parser actions, where each action consists of a transition and (except for Shift and Reduce) a dependency type: f : Config ? {LA,RA,RE,SH} ?</S>
  			<S sid="70" ssid="21">(R ? {nil}) Here Config is the set of all configurations and R is the set of dependency types.</S>
  			<S sid="71" ssid="22">In order to make theproblem tractable, we approximate f with a func tion f?</S>
  			<S sid="72" ssid="23">whose domain is a finite space of parser states, which are abstractions over configurations.</S>
  			<S sid="73" ssid="24">For this purpose we define a number of features that can be used to define different models of parser state.</S>
  			<S sid="74" ssid="25">Figure 2 illustrates the features that are used to define parser states in the present study.</S>
  			<S sid="75" ssid="26">The two central elements in any configuration are the token on top of the stack (T) and the next input token(N), the tokens which may be connected by a de pendency arc in the next configuration.</S>
  			<S sid="76" ssid="27">For these tokens, we consider both the word form (T.LEX, N.LEX) and the part-of-speech (T.POS, N.POS), as assigned by an automatic part-of-speech tagger ina preprocessing phase.</S>
  			<S sid="77" ssid="28">Next, we consider a selection of dependencies that may be present in the cur rent arc relation, namely those linking T to its head (TH) and its leftmost and rightmost dependent (TL, TR), and that linking N to its leftmost dependent (NL),3 considering both the dependency type (arclabel) and the part-of-speech of the head or depen dent.</S>
  			<S sid="78" ssid="29">Finally, we use a lookahead of three tokens, considering only their parts-of-speech.</S>
  			<S sid="79" ssid="30">We have experimented with two different statemodels, one that incorporates all the features depicted in Figure 2 (Model 1), and one that ex cludes the parts-of-speech of TH, TL, TR, NL (Model 2).</S>
  			<S sid="80" ssid="31">Models similar to model 2 have been found towork well for datasets with a rich annotation of de pendency types, such as the Swedish dependency treebank derived from Einarsson (1976), where the extra part-of-speech features are largely redundant (Nivre et al, 2004).</S>
  			<S sid="81" ssid="32">Model 1 can be expected towork better for datasets with less informative dependency annotation, such as dependency trees ex tracted from the Penn Treebank, where the extra part-of-speech features may compensate for the lack of information in arc labels.</S>
  			<S sid="82" ssid="33">The learning algorithm used is the IB1 algorithm (Aha et al, 1991) with k = 5, i.e. classification basedon 5 nearest neighbors.4 Distances are measured us ing the modified value difference metric (MVDM) (Stanfill and Waltz, 1986; Cost and Salzberg, 1993) for instances with a frequency of at least 3 (andthe simple overlap metric otherwise), and classifica tion is based on distance weighted class voting with inverse distance weighting (Dudani, 1976).</S>
  			<S sid="83" ssid="34">Thesesettings are the result of extensive experiments partially reported in Nivre et al (2004).</S>
  			<S sid="84" ssid="35">For more infor mation about the different parameters and settings, see Daelemans et al (2003).</S>
  			<S sid="85" ssid="36">4 Experiments.</S>
  			<S sid="86" ssid="37">The data set used for experimental evaluation is the standard data set from the Wall Street Journal section of the Penn Treebank, with sections 2?21 3Given the parsing algorithm, N can never have a head or a right dependent in the current configuration.4In TiMBL, the value of k in fact refers to k nearest dis tances rather than k nearest neighbors, which means that, evenwith k = 1, the nearest neighbor set can contain several instances that are equally distant to the test instance.</S>
  			<S sid="87" ssid="38">This is dif ferent from the original IB1 algorithm, as described in Aha et al.</S>
  			<S sid="88" ssid="39">(1991).</S>
  			<S sid="89" ssid="40">used for training and section 23 for testing (Collins,1999; Charniak, 2000).</S>
  			<S sid="90" ssid="41">The data has been converted to dependency trees using head rules (Magerman, 1995; Collins, 1996).</S>
  			<S sid="91" ssid="42">We are grateful to Ya mada and Matsumoto for letting us use their rule set, which is a slight modification of the rules used byCollins (1999).</S>
  			<S sid="92" ssid="43">This permits us to make exact com parisons with the parser of Yamada and Matsumoto (2003), but also the parsers of Collins (1997) and Charniak (2000), which are evaluated on the same data set in Yamada and Matsumoto (2003).One problem that we had to face is that the standard conversion of phrase structure trees to de pendency trees gives unlabeled dependency trees, whereas our parser requires labeled trees.</S>
  			<S sid="93" ssid="44">Since the annotation scheme of the Penn Treebank does notinclude dependency types, there is no straightfor ward way to derive such labels.</S>
  			<S sid="94" ssid="45">We have therefore experimented with two different sets of labels, none of which corresponds to dependency types in a strict sense.</S>
  			<S sid="95" ssid="46">The first set consists of the function tags forgrammatical roles according to the Penn II annota tion guidelines (Bies et al, 1995); we call this set G.The second set consists of the ordinary bracket la bels (S, NP, VP, etc.), combined with function tags for grammatical roles, giving composite labels such as NP-SBJ; we call this set B. We assign labels to arcs by letting each (non-root) word that heads aphrase P in the original phrase structure have its in coming edge labeled with the label of P (modulo the set of labels used).</S>
  			<S sid="96" ssid="47">In both sets, we also includea default label DEP for arcs that would not other wise get a label.</S>
  			<S sid="97" ssid="48">This gives a total of 7 labels in the G set and 50 labels in the B set.</S>
  			<S sid="98" ssid="49">Figure 1 shows a converted dependency tree using the B labels; in the corresponding tree with G labels NP-SBJ would be replaced by SBJ, ADVP and VP by DEP.</S>
  			<S sid="99" ssid="50">We use the following metrics for evaluation: 1.</S>
  			<S sid="100" ssid="51">Unlabeled attachment score (UAS): The pro-.</S>
  			<S sid="101" ssid="52">portion of words that are assigned the correct head (or no head if the word is a root) (Eisner, 1996; Collins et al, 1999).</S>
  			<S sid="102" ssid="53">2.</S>
  			<S sid="103" ssid="54">Labeled attachment score (LAS): The pro-.</S>
  			<S sid="104" ssid="55">portion of words that are assigned the correct head and dependency type (or no head if the word is a root) (Nivre et al, 2004).</S>
  			<S sid="105" ssid="56">3.</S>
  			<S sid="106" ssid="57">Dependency accuracy (DA): The proportion.</S>
  			<S sid="107" ssid="58">of non-root words that are assigned the correct head (Yamada and Matsumoto, 2003).</S>
  			<S sid="108" ssid="59">4.</S>
  			<S sid="109" ssid="60">Root accuracy (RA): The proportion of root.</S>
  			<S sid="110" ssid="61">words that are analyzed as such (Yamada and Matsumoto, 2003).</S>
  	</SECTION>
  	<SECTION title="Complete match (CM): The proportion of. " number="5">
  			<S sid="111" ssid="1">sentences whose unlabeled dependency structure is completely correct (Yamada and Mat sumoto, 2003).</S>
  			<S sid="112" ssid="2">All metrics except CM are calculated as meanscores per word, and punctuation tokens are con sistently excluded.Table 1 shows the attachment score, both unla beled and labeled, for the two different state models with the two different label sets.</S>
  			<S sid="113" ssid="3">First of all, we see that Model 1 gives better accuracy than Model 2 with the smaller label set G, which confirms our expectations that the added part-of-speech featuresare helpful when the dependency labels are less informative.</S>
  			<S sid="114" ssid="4">Conversely, we see that Model 2 outper forms Model 1 with the larger label set B, which is consistent with the hypothesis that part-of-speech features become redundant as dependency labels get more informative.</S>
  			<S sid="115" ssid="5">It is interesting to note that this effect holds even in the case where the dependencylabels are mostly derived from phrase structure cate gories.</S>
  			<S sid="116" ssid="6">We can also see that the unlabeled attachment score improves, for both models, when the set of dependency labels is extended.</S>
  			<S sid="117" ssid="7">On the other hand, the labeled attachment score drops, but it must beremembered that these scores are not really comparable, since the number of classes in the classifi cation problem increases from 7 to 50 as we move from the G set to the B set.</S>
  			<S sid="118" ssid="8">Therefore, we have also included the labeled attachment score restricted to the G set for the parser using the B set (BG), and wesee then that the attachment score improves, espe cially for Model 2.</S>
  			<S sid="119" ssid="9">(All differences are significant beyond the .01 level; McNemar?s test.)</S>
  			<S sid="120" ssid="10">Table 2 shows the dependency accuracy, root accuracy and complete match scores for our best parser (Model 2 with label set B) in comparison with Collins (1997) (Model 3), Charniak (2000), and Yamada and Matsumoto (2003).5 It is clear that, with respect to unlabeled accuracy, our parser does not quite reach state-of-the-art performance, evenif we limit the competition to deterministic meth ods such as that of Yamada and Matsumoto (2003).</S>
  			<S sid="121" ssid="11">We believe that there are mainly three reasons for this.</S>
  			<S sid="122" ssid="12">First of all, the part-of-speech tagger used for preprocessing in our experiments has a loweraccuracy than the one used by Yamada and Mat sumoto (2003) (96.1% vs. 97.1%).</S>
  			<S sid="123" ssid="13">Although this is not a very interesting explanation, it undoubtedly accounts for part of the difference.</S>
  			<S sid="124" ssid="14">Secondly, since 5The information in the first three rows is taken directly from Yamada and Matsumoto (2003).our parser makes crucial use of dependency type in formation in predicting the next action of the parser, it is very likely that it suffers from the lack of realdependency labels in the converted treebank.</S>
  			<S sid="125" ssid="15">Indi rect support for this assumption can be gained fromprevious experiments with Swedish data, where al most the same accuracy (85% unlabeled attachment score) has been achieved with a treebank whichis much smaller but which contains proper depen dency annotation (Nivre et al, 2004).</S>
  			<S sid="126" ssid="16">A third important factor is the relatively low rootaccuracy of our parser, which may reflect a weak ness in the one-pass parsing strategy with respect tothe global structure of complex sentences.</S>
  			<S sid="127" ssid="17">It is note worthy that our parser has lower root accuracy than dependency accuracy, whereas the inverse holds for all the other parsers.</S>
  			<S sid="128" ssid="18">The problem becomes even more visible when we consider the dependency and root accuracy for sentences of different lengths, as shown in Table 3.</S>
  			<S sid="129" ssid="19">Here we see that for really short sentences (up to 10 words) root accuracy is indeedhigher than dependency accuracy, but while depen dency accuracy degrades gracefully with sentence length, the root accuracy drops more drastically (which also very clearly affects the complete match score).</S>
  			<S sid="130" ssid="20">This may be taken to suggest that some kind of preprocessing in the form of clausing may help to improve overall accuracy.Turning finally to the assessment of labeled de pendency accuracy, we are not aware of any strictlycomparable results for the given data set, but Buch holz (2002) reports a labeled accuracy of 72.6% for the assignment of grammatical relations using a cascade of memory-based processors.</S>
  			<S sid="131" ssid="21">This can be compared with a labeled attachment score of 84.4% for Model 2 with our B set, which is of about the same size as the set used by Buchholz, although the labels are not the same.</S>
  			<S sid="132" ssid="22">In another study, Blaheta and Charniak (2000) report an F-measure of 98.9% for the assignment of Penn Treebank grammatical role labels (our G set) to phrases that were correctly parsed by the parser described in Charniak (2000).</S>
  			<S sid="133" ssid="23">If null labels (corresponding to our DEP labels) areexcluded, the F-score drops to 95.7%.</S>
  			<S sid="134" ssid="24">The corre sponding F-measures for our best parser (Model 2, BG) are 99.0% and 94.7%.</S>
  			<S sid="135" ssid="25">For the larger B set, our best parser achieves an F-measure of 96.9% (DEP labels included), which can be compared with 97.0% for a similar (but larger) set of labels inCollins (1999).6 Although none of the previous re sults on labeling accuracy is strictly comparable to ours, it nevertheless seems fair to conclude that the 6This F-measure is based on the recall and precision figures reported in Figure 7.15 in Collins (1999).</S>
  			<S sid="136" ssid="26">Model 1 Model 2 G B BG G B BG UAS 86.4 86.7 85.8 87.1 LAS 85.3 84.0 85.5 84.6 84.4 86.0 Table 1: Parsing accuracy: Attachment score (BG = evaluation of B restricted to G labels) DA RA CM Charniak 92.1 95.2 45.2 Collins 91.5 95.2 43.3 Yamada  Matsumoto 90.3 91.6 38.4 Nivre  Scholz 87.3 84.3 30.4 Table 2: Comparison with related work (Yamada and Matsumoto, 2003) labeling accuracy of the present parser is close to the state of the art, even if its capacity to derive correct structures is not.</S>
  			<S sid="137" ssid="27">5 Conclusion.</S>
  			<S sid="138" ssid="28">This paper has explored the application of a data driven dependency parser to English text, using data from the Penn Treebank.</S>
  			<S sid="139" ssid="29">The parser is deterministic and uses a linear-time parsing algorithm, guided bymemory-based classifiers, to construct labeled de pendency structures incrementally in one pass over the input.</S>
  			<S sid="140" ssid="30">Given the difficulty of extracting labeled dependencies from a phrase structure treebank with limited functional annotation, the accuracy attainedis fairly respectable.</S>
  			<S sid="141" ssid="31">And although the structural ac curacy falls short of the best available parsers, the labeling accuracy appears to be competitive.The most important weakness is the limited ac curacy in identifying the root node of a sentence, especially for longer sentences.</S>
  			<S sid="142" ssid="32">We conjecture that an improvement in this area could lead to a boost in overall performance.</S>
  			<S sid="143" ssid="33">Another important issue to investigate further is the influence of different kinds of arc labels, and in particular labels that are based on a proper dependency grammar.</S>
  			<S sid="144" ssid="34">In thefuture, we therefore want to perform more experi ments with genuine dependency treebanks like the Prague Dependency Treebank (Hajic, 1998) and the Danish Dependency Treebank (Kromann, 2003).</S>
  			<S sid="145" ssid="35">We also want to apply dependency-based evaluation schemes such as the ones proposed by Lin (1998) and Carroll et al (1998).</S>
  			<S sid="146" ssid="36">Acknowledgements The work presented in this paper has been supportedby a grant from the Swedish Research Council (621 2002-4207).</S>
  			<S sid="147" ssid="37">The memory-based classifiers used in the experiments have been constructed using theTilburg Memory-Based Learner (TiMBL) (Daelemans et al, 2003).</S>
  			<S sid="148" ssid="38">The conversion of the Penn Tree bank to dependency trees has been performed using head rules kindly provided by Hiroyasu Yamada and Yuji Matsumoto.</S>
  	</SECTION>
  </PAPER>
  