This paper describes practical issues in the framework-independent evaluation of deep and shallow parsers. We focus on the use of two dependency-based syntactic representation formats in parser evaluation, namely, Carroll et al. (1998)'s Grammatical Relations and de Marneffe et al. (2006)'s Stanford Dependency scheme. Our approach is to convert the output of parsers into these two formats, and measure the accuracy of the resulting converted output. Through the evaluation of an HPSG parser and Penn Treebank phrase structure parsers, we found that mapping between different representation schemes is a non-trivial task that results in lossy conversions that may obscure important differences between different parsing approaches. We discuss sources of disagreements in the representation of syntactic structures in the two dependency-based formats, indicating possible directions for improved framework-independent parser evaluation.

@inproceedings{Miyao:2007, author = {Miyao, Yusuke and Sagae, Kenji and Tsujii, Jun'ichi}, title = {Towards Framework-Independent Evaluation of Deep Linguistic Parsers}, editor = {Copestake, Ann}, booktitle = {Proceedings of the GEAF 2007 Workshop}, series = {CSLI Studies in Computational Linguistics Online}, publisher = {CSLI Publications}, year = {2007}, pages = {21 pages}, url = {http://www.cs.cmu.edu/~sagae/docs/geaf07miyaoetal.pdf}, keywords = {parsers evaluation}, abstract = {This paper describes practical issues in the framework-independent evaluation of deep and shallow parsers. We focus on the use of two dependency-based syntactic representation formats in parser evaluation, namely, Carroll et al. (1998)'s Grammatical Relations and de Marneffe et al. (2006)'s Stanford Dependency scheme. Our approach is to convert the output of parsers into these two formats, and measure the accuracy of the resulting converted output. Through the evaluation of an HPSG parser and Penn Treebank phrase structure parsers, we found that mapping between different representation schemes is a non-trivial task that results in lossy conversions that may obscure important differences between different parsing approaches. We discuss sources of disagreements in the representation of syntactic structures in the two dependency-based formats, indicating possible directions for improved framework-independent parser evaluation.} }

%0 = inproceedings %A = Miyao, Yusuke and Sagae, Kenji and Tsujii, Jun'ichi %B = Proceedings of the GEAF 2007 Workshop %D = 2007 %I = CSLI Publications %T = Towards Framework-Independent Evaluation of Deep Linguistic Parsers %U = http://www.cs.cmu.edu/~sagae/docs/geaf07miyaoetal.pdf

We present a novel framework that combines strengths from surface syntactic parsing and deep syntactic parsing to increase deep parsing accuracy, specifically by combining dependency and HPSG parsing. We show that by using surface dependencies to constrain the application of wide-coverage HPSG rules, we can benefit from a number of parsing techniques designed for high-accuracy dependency parsing, while actually performing deep syntactic analysis. Our framework results in a 1.4% absolute improvement over a state-of-the-art approach for wide coverage HPSG parsing.

@inproceedings{Sagae:2007, author = {Sagae, Kenji and Miyao, Yusuke and Tsujii, Jun'ichi}, title = {HPSG Parsing with Shallow Dependency Constraints}, booktitle = {Proc. ACL 2007}, year = {2007}, pages = {624-631}, url = {http://www-tsujii.is.s.u-tokyo.ac.jp/enju/}, keywords = {HPSG parsers}, abstract = {We present a novel framework that combines strengths from surface syntactic parsing and deep syntactic parsing to increase deep parsing accuracy, specifically by combining dependency and HPSG parsing. We show that by using surface dependencies to constrain the application of wide-coverage HPSG rules, we can benefit from a number of parsing techniques designed for high-accuracy dependency parsing, while actually performing deep syntactic analysis. Our framework results in a 1.4% absolute improvement over a state-of-the-art approach for wide coverage HPSG parsing.} }

%0 = inproceedings %A = Sagae, Kenji and Miyao, Yusuke and Tsujii, Jun'ichi %B = Proc. ACL 2007 %D = 2007 %T = HPSG Parsing with Shallow Dependency Constraints %U = http://www-tsujii.is.s.u-tokyo.ac.jp/enju/

@inproceedings{Marneffe:2006, author = {de Marneffe, Marie-Catherine and MacCartney, Bill and Manning, Christopher D.}, title = {Generating Typed Dependency Parses from Phrase Structure Trees}, booktitle = {LREC}, year = {2006}, url = {http://nlp.stanford.edu/pubs/LREC06_dependencies.pdf}, keywords = {dependencies constituency parsers} }

%0 = inproceedings %A = de Marneffe, Marie-Catherine and MacCartney, Bill and Manning, Christopher D. %B = LREC %D = 2006 %T = Generating Typed Dependency Parses from Phrase Structure Trees %U = http://nlp.stanford.edu/pubs/LREC06_dependencies.pdf

We present an evaluation of Link Grammar and Connexor Machinese Syntax, two major broad-coverage dependency parsers, on a custom hand-annotated corpus consisting of sentences regarding protein-protein interactions. In the evaluation, we apply the notion of an interaction subgraph, which is the subgraph of a dependency graph expressing a protein-protein interaction. We measure the performance of the parsers for recovery of individual dependencies, fully correct parses, and interaction subgraphs. For Link Grammar, an open system that can be inspected in detail, we further perform a comprehensive failure analysis, report specific causes of error, and suggest potential modifications to the grammar. We find that both parsers perform worse on biomedical English than previously reported on general English. While Connexor Machinese Syntax significantly outperforms Link Grammar, the failure analysis suggests specific ways in which the latter could be modified for better performance in the domain.

@article{Pyysalo:2006, author = {Pyysalo, Sampo and Ginter, Filip and Pahikkala, Tapio and Boberg, Jorma and Jarvinen, Jouni and Salakoski, Tapio}, title = {Evaluation of two dependency parsers on biomedical corpus targeted at protein-protein interactions}, booktitle = {Recent Advances in Natural Language Processing for Biomedical Applications Special Issue}, journal = {International Journal of Medical Informatics}, year = {2006}, volume = {75}, number = {6}, pages = {430--442}, url = {http://dx.doi.org/10.1016/j.ijmedinf.2005.06.009}, doi = {10.1016/j.ijmedinf.2005.06.009}, keywords = {parsers biomedicine evaluation}, abstract = {We present an evaluation of Link Grammar and Connexor Machinese Syntax, two major broad-coverage dependency parsers, on a custom hand-annotated corpus consisting of sentences regarding protein-protein interactions. In the evaluation, we apply the notion of an interaction subgraph, which is the subgraph of a dependency graph expressing a protein-protein interaction. We measure the performance of the parsers for recovery of individual dependencies, fully correct parses, and interaction subgraphs. For Link Grammar, an open system that can be inspected in detail, we further perform a comprehensive failure analysis, report specific causes of error, and suggest potential modifications to the grammar. We find that both parsers perform worse on biomedical English than previously reported on general English. While Connexor Machinese Syntax significantly outperforms Link Grammar, the failure analysis suggests specific ways in which the latter could be modified for better performance in the domain.} }

%0 = article %A = Pyysalo, Sampo and Ginter, Filip and Pahikkala, Tapio and Boberg, Jorma and Jarvinen, Jouni and Salakoski, Tapio %B = Recent Advances in Natural Language Processing for Biomedical Applications Special Issue %D = 2006 %T = Evaluation of two dependency parsers on biomedical corpus targeted at protein-protein interactions %U = http://dx.doi.org/10.1016/j.ijmedinf.2005.06.009

This paper describes a method of semi-automatically acquiring an English HPSG grammar from the Penn Treebank. First, heuristic rules are employed to annotate the treebank with partially-specified derivation trees. Lexical entries are automatically extracted from the annotated corpus by inversely applying schemata to partially-specified derivation trees.

@inproceedings{Miyao:2004, author = {Miyao, Yusuke and Ninomiya, Takashi and Tsujii, Jun'ichi}, title = {Corpus-oriented Grammar Development for Acquiring a Head-driven Phrase Structure Grammar from the Penn Treebank}, booktitle = {Proceedings of IJCNLP-04}, address = {8 pages}, year = {2004}, url = {http://www-tsujii.is.s.u-tokyo.ac.jp/~yusuke/paper/ijcnlp04.pdf}, keywords = {HPSG parsers}, abstract = {This paper describes a method of semi-automatically acquiring an English HPSG grammar from the Penn Treebank. First, heuristic rules are employed to annotate the treebank with partially-specified derivation trees. Lexical entries are automatically extracted from the annotated corpus by inversely applying schemata to partially-specified derivation trees.} }

%0 = inproceedings %A = Miyao, Yusuke and Ninomiya, Takashi and Tsujii, Jun'ichi %B = Proceedings of IJCNLP-04 %C = 8 pages %D = 2004 %T = Corpus-oriented Grammar Development for Acquiring a Head-driven Phrase Structure Grammar from the Penn Treebank %U = http://www-tsujii.is.s.u-tokyo.ac.jp/~yusuke/paper/ijcnlp04.pdf

A wide range of parser and/or grammar evaluation methods have been reported in the literature. However, in most cases these evaluations take the parsers independently (intrinsic evaluations), and only in a few cases has the effect of different parsers in real applications been measured (extrinsic evaluations). This paper compares two evaluations of the Link Grammar parser and the Conexor Functional Dependency Grammar parser. The parsing systems, despite both being dependency-based, return different types of dependencies, making a direct comparison impossible. In the intrinsic evaluation, the accuracy of the parsers is compared independently by converting the dependencies into grammatical relations and using the methodology of Carroll:1998 for parser comparison. In the extrinsic evaluation, the parsers' impact in a practical application is compared within the context of answer extraction. The differences in the results are significant.

@inproceedings{Moll'a:2003b, author = {Mollá, Diego and Hutchinson, Ben}, title = {Intrinsic versus Extrinsic Evaluations of Parsing Systems}, booktitle = {Proc. European Association for Computational Linguistics (EACL), workshop on Evaluation Initiatives in Natural Language Processing}, publisher = {ACL}, address = {Budapest}, year = {2003}, pages = {43-50}, keywords = {parsers evaluation AnswerFinder gram_rels molla_publication}, abstract = {A wide range of parser and/or grammar evaluation methods have been reported in the literature. However, in most cases these evaluations take the parsers independently (intrinsic evaluations), and only in a few cases has the effect of different parsers in real applications been measured (extrinsic evaluations). This paper compares two evaluations of the Link Grammar parser and the Conexor Functional Dependency Grammar parser. The parsing systems, despite both being dependency-based, return different types of dependencies, making a direct comparison impossible. In the intrinsic evaluation, the accuracy of the parsers is compared independently by converting the dependencies into grammatical relations and using the methodology of Carroll:1998 for parser comparison. In the extrinsic evaluation, the parsers' impact in a practical application is compared within the context of answer extraction. The differences in the results are significant.} }

%0 = inproceedings %A = Mollá, Diego and Hutchinson, Ben %B = Proc. European Association for Computational Linguistics (EACL), workshop on Evaluation Initiatives in Natural Language Processing %C = Budapest %D = 2003 %I = ACL %T = Intrinsic versus Extrinsic Evaluations of Parsing Systems

Many extensions to text-based, data-intensive knowledge management approaches, such as Information Retrieval or Data Mining, focus on integrating the impressive recent advances in language technology. For this, they need fast, robust parsers that deliver linguistic data which is meaningful for the subsequent processing stages. This paper introduces such a parsing system. Its output is a hierarchical structure of syntactic relations, functional dependency structures ...

@inproceedings{Schneider:2003, author = {Schneider, Gerold}, title = {Extracting and Using Trace-Free Functional Dependencies from the Penn Treebank to Reduce Parsing Complexity}, booktitle = {Proc. Workshop on Treebanks and Linguistic Theories (TLT 2003)}, year = {2003}, url = {http://w3.msi.vxu.se/rics/TLT2003/}, keywords = {dependencies parsers}, abstract = {Many extensions to text-based, data-intensive knowledge management approaches, such as Information Retrieval or Data Mining, focus on integrating the impressive recent advances in language technology. For this, they need fast, robust parsers that deliver linguistic data which is meaningful for the subsequent processing stages. This paper introduces such a parsing system. Its output is a hierarchical structure of syntactic relations, functional dependency structures ...} }

%0 = inproceedings %A = Schneider, Gerold %B = Proc. Workshop on Treebanks and Linguistic Theories (TLT 2003) %D = 2003 %T = Extracting and Using Trace-Free Functional Dependencies from the Penn Treebank to Reduce Parsing Complexity %U = http://w3.msi.vxu.se/rics/TLT2003/

A wide variety of parser and/or grammar evaluation methods have been reported in the literature. However, in most cases these evaluations take the parsers independently (in vitro evaluations), and only in a few cases has the effect of different parsers in real applications been measured (in vivo evaluations). This paper compares two evaluations of the Link Grammar parser and the Conexor Functional Dependency Grammar parser. The parsing systems, despite both being dependency-based, return different types of dependencies, making a direct comparison impossible. In the first evaluation, the accuracy of the parsers is compared in vitro by converting the dependencies into grammatical relations and using the methodology of Carroll:1998 for parser comparison. In the second evaluation, the parsers' impact in a practical application is compared in vivo within the context of answer extraction. The differences in the results are significant and raise questions on the usefulness of purely in vitro evaluations.

@unpublished{Molla:anlp02:preparation, author = {Mollá, Diego and Hutchinson, Ben}, title = {In Vitro and In Vivo Evaluations of Parsing Systems Within the Context of Answer Extraction}, year = {2002}, note = {In preparation}, keywords = {AnswerFinder parsers evaluation gram_rels molla_publication}, abstract = {A wide variety of parser and/or grammar evaluation methods have been reported in the literature. However, in most cases these evaluations take the parsers independently (in vitro evaluations), and only in a few cases has the effect of different parsers in real applications been measured (in vivo evaluations). This paper compares two evaluations of the Link Grammar parser and the Conexor Functional Dependency Grammar parser. The parsing systems, despite both being dependency-based, return different types of dependencies, making a direct comparison impossible. In the first evaluation, the accuracy of the parsers is compared in vitro by converting the dependencies into grammatical relations and using the methodology of Carroll:1998 for parser comparison. In the second evaluation, the parsers' impact in a practical application is compared in vivo within the context of answer extraction. The differences in the results are significant and raise questions on the usefulness of purely in vitro evaluations.} }

%0 = unpublished %A = Mollá, Diego and Hutchinson, Ben %D = 2002 %T = In Vitro and In Vivo Evaluations of Parsing Systems Within the Context of Answer Extraction

@techreport{Conexor:2002, author = {Oy, Conexor}, title = {Conexor Functional Dependency Grammar 3.7 --- User's Manual}, year = {2002}, keywords = {parsers DG} }

%0 = techreport %A = Oy, Conexor %D = 2002 %T = Conexor Functional Dependency Grammar 3.7 --- User's Manual

... The thesis argues that a test suite for a broad coverage natural language parser must necessarily be systematic, broad in its coverage of phenomena tested, and corpus-like in its coverage of phenomenon interaction. A test suite of example sentences extracted from Quirk et al.'s comprehensive English grammar is proposed, and the results of evaluating DIPETT on that suite are compared with the evaluation results on a publicly available test suite, TSNLP (Test Suites for Natural Language Processing).

@mastersthesis{Scarlett:2000:2, author = {Scarlett, Elizabeth}, title = {An Evaluation of a Rule-Based Parser of English Sentences}, school = {University of Ottawa}, year = {2000}, url = {http://www.site.uottawa.ca/scarlett/}, keywords = {parsers evaluation}, abstract = {... The thesis argues that a test suite for a broad coverage natural language parser must necessarily be systematic, broad in its coverage of phenomena tested, and corpus-like in its coverage of phenomenon interaction. A test suite of example sentences extracted from Quirk et al.'s comprehensive English grammar is proposed, and the results of evaluating DIPETT on that suite are compared with the evaluation results on a publicly available test suite, TSNLP (Test Suites for Natural Language Processing).} }

%0 = mastersthesis %A = Scarlett, Elizabeth %D = 2000 %T = An Evaluation of a Rule-Based Parser of English Sentences %U = http://www.site.uottawa.ca/scarlett/

We show a diagnostic evaluation of DIPETT, a broad-coverage parser of English sentences. We consider the TSNLP suite as a diagnostic tool, and propose an alternative broader-coverage test suite of test sentences extracted from Quirk et al. We compare the diagnostic effectiveness of the two suites, and draw a few general conclusions. The evaluation results were used to make significant improvements to DIPETT.

@inproceedings{Scarlett:2000, author = {Scarlett, Elizabeth and Szpkowicz, Stan}, title = {The Power of the TSNLP: Lessons from a Diagnostic Evaluation of a Broad-Coverage Parser}, booktitle = {Proc. Thirteenth Canadian Conference on Artificial Intelligence}, address = {Montreal}, year = {2000}, url = {http://www.site.uottawa.ca/scarlett/}, keywords = {parsers evaluation}, abstract = {We show a diagnostic evaluation of DIPETT, a broad-coverage parser of English sentences. We consider the TSNLP suite as a diagnostic tool, and propose an alternative broader-coverage test suite of test sentences extracted from Quirk et al. We compare the diagnostic effectiveness of the two suites, and draw a few general conclusions. The evaluation results were used to make significant improvements to DIPETT.} }

%0 = inproceedings %A = Scarlett, Elizabeth and Szpkowicz, Stan %B = Proc. Thirteenth Canadian Conference on Artificial Intelligence %C = Montreal %D = 2000 %T = The Power of the TSNLP: Lessons from a Diagnostic Evaluation of a Broad-Coverage Parser %U = http://www.site.uottawa.ca/scarlett/

Three state-of-the-art statistical parsers are combined to produce more accurate parses, as well as new bounds on achievable Treebank parsing accuracy. Two general approaches are presented and two combination techniques are described for each approach. Both parametric and non-parametric models are explored. The resulting parsers surpass the best previously published performance results for the Penn Treebank.

@inproceedings{Henderson:1999, author = {Henderson, John C. and Brill, Eric}, title = {Exploiting Diversity in Natural Language Processing: Combining Parsers}, booktitle = {Proc. EMNLP-99}, address = {College Park, Maryland}, year = {1999}, pages = {187-194}, note = {Also in arXiv:cs.CL/0006003}, url = {http://xxx.lanl.gov/abs/cs.CL/0006003}, keywords = {parsers}, abstract = {Three state-of-the-art statistical parsers are combined to produce more accurate parses, as well as new bounds on achievable Treebank parsing accuracy. Two general approaches are presented and two combination techniques are described for each approach. Both parametric and non-parametric models are explored. The resulting parsers surpass the best previously published performance results for the Penn Treebank.} }

%0 = inproceedings %A = Henderson, John C. and Brill, Eric %B = Proc. EMNLP-99 %C = College Park, Maryland %D = 1999 %T = Exploiting Diversity in Natural Language Processing: Combining Parsers %U = http://xxx.lanl.gov/abs/cs.CL/0006003

This paper examines efficient predictive broad-coverage parsing without dynamic programming. In contrast to bottom-up methods, depth-first top-down parsing produces partial parses that are fully connected trees spanning the entire left context, from which any kind of non-local dependency or partial semantic interpretation can in principle be read. We contrast two predictive parsing approaches, top-down and left-corner parsing, and find both to be viable. In addition, we find that enhancement with non-local information not only improves parser accuracy, but also substantially improves the search efficiency.

@inproceedings{Roark:1999, author = {Roark, Brian and Johnson, Mark}, title = {Efficient Probabilistic Top-down and Left-corner Parsing}, booktitle = {Proc. ACL'99}, year = {1999}, pages = {421-428}, note = {http://arXiv.org/abs/cs/0008017}, url = {http://arXiv.org/abs/cs/0008017}, keywords = {parsers statistic_nlp}, abstract = {This paper examines efficient predictive broad-coverage parsing without dynamic programming. In contrast to bottom-up methods, depth-first top-down parsing produces partial parses that are fully connected trees spanning the entire left context, from which any kind of non-local dependency or partial semantic interpretation can in principle be read. We contrast two predictive parsing approaches, top-down and left-corner parsing, and find both to be viable. In addition, we find that enhancement with non-local information not only improves parser accuracy, but also substantially improves the search efficiency.} }

%0 = inproceedings %A = Roark, Brian and Johnson, Mark %B = Proc. ACL'99 %D = 1999 %T = Efficient Probabilistic Top-down and Left-corner Parsing %U = http://arXiv.org/abs/cs/0008017

@inproceedings{Jaervinen:1998, author = {Järvinen, Timo and Tapanainen, Pasi}, title = {Towards an Implementable Dependency Grammar}, booktitle = {Proc. of COLING-ACL. Workshop: Processing of Dependency Grammars}, year = {1998}, keywords = {DG parsers} }

%0 = inproceedings %A = Järvinen, Timo and Tapanainen, Pasi %B = Proc. of COLING-ACL. Workshop: Processing of Dependency Grammars %D = 1998 %T = Towards an Implementable Dependency Grammar

@inproceedings{Lin:1998, author = {Lin, Dekang}, title = {Dependency-based Evaluation of MINIPAR}, booktitle = {Proc. Workshop on the Evaluation of Parsing Systems}, series = {Granada}, year = {1998}, keywords = {parsers DG} }

%0 = inproceedings %A = Lin, Dekang %B = Proc. Workshop on the Evaluation of Parsing Systems %D = 1998 %T = Dependency-based Evaluation of MINIPAR

@misc{Schneider:Nov:1998, author = {Schneider, Gerold}, title = {Functional Non-Projective Parsing with Dependency Grammar (DG)}, year = {1998}, keywords = {DG parsers} }

%0 = misc %A = Schneider, Gerold %D = 1998 %T = Functional Non-Projective Parsing with Dependency Grammar (DG)

@techreport{Jaervinen:1997, author = {Järvinen, Timo and Tapanainen, Pasi}, title = {A Dependency Parser for English}, address = {Helsinki}, year = {1997}, number = {TR-1}, url = {http://www.ling.helsinki.fi/tapanain/dg/doc/TR-1/}, keywords = {DG parsers} }

%0 = techreport %A = Järvinen, Timo and Tapanainen, Pasi %C = Helsinki %D = 1997 %T = A Dependency Parser for English %U = http://www.ling.helsinki.fi/tapanain/dg/doc/TR-1/

@inproceedings{Tapanainen:1997, author = {Tapanainen, Pasi and Järvinen, Timo}, title = {A Non-Projective Dependency Parser}, booktitle = {Proc. ANLP-97}, year = {1997}, url = {http://www.conexor.fi/anlp97/anlp97.html}, keywords = {DG parsers} }

%0 = inproceedings %A = Tapanainen, Pasi and Järvinen, Timo %B = Proc. ANLP-97 %D = 1997 %T = A Non-Projective Dependency Parser %U = http://www.conexor.fi/anlp97/anlp97.html

Charts constitute a natural uniform architecture for parsing and generation provided string position is replaced by a notion more appropriate to logical forms and that measures are taken to curtail generation paths containing semantically incomplete phrases.

@inproceedings{Kay:1996, author = {Kay, Martin}, title = {Chart Generation}, booktitle = {Proc. 34th Annual Meeting of the ACL}, address = {Santa Cruz, CA}, year = {1996}, pages = {200-204}, keywords = {parsers flat_semantics generation}, abstract = {Charts constitute a natural uniform architecture for parsing and generation provided string position is replaced by a notion more appropriate to logical forms and that measures are taken to curtail generation paths containing semantically incomplete phrases.} }

%0 = inproceedings %A = Kay, Martin %B = Proc. 34th Annual Meeting of the ACL %C = Santa Cruz, CA %D = 1996 %T = Chart Generation

@article{Tomita:1987, author = {Tomita, Masaru}, title = {An Efficient Augmented-Context-Free Parsing Algorithm}, journal = {Computational Linguistics}, year = {1987}, volume = {12}, number = {1-2}, pages = {31-46}, keywords = {parsers} }

%0 = article %A = Tomita, Masaru %D = 1987 %T = An Efficient Augmented-Context-Free Parsing Algorithm