PaperlayerView exact revision on arXiv

Source-linked AI summary

Yara Parser: A Fast and Accurate Dependency Parser

Mohammad Sadegh Rasooli, Joel Tetreault

arXiv:1503.06733v2cs.CL

TL;DR

Dependency parsing is important for downstream NLP applications, motivating a parser that combines accuracy, speed, and practical flexibility. The paper introduces Yara, an arc-eager transition-based parser using beam search, and reports high WSJ accuracy alongside fast parsing, while noting limitations for some data settings.

  • Problem

    Dependency parsers support important NLP applications, creating a need for accurate and fast parsing tools.

  • Method

    Yara is an open-source transition-based dependency parser using the arc-eager algorithm, beam search, configurable features, and static or dynamic oracles.

  • Results

    Yara is reported as very fast and accurate, with performance close to state-of-the-art on WSJ data.

  • Takeaways & Limitations

    Yara is intended for downstream tasks and can be tuned for different languages and tasks through flexible settings.

  • Takeaways & Limitations

    Yara can only be trained on projective trees, causing some accuracy loss for non-projective languages.

Abstract

from arXiv · show

Dependency parsers are among the most crucial tools in natural language processing as they have many important applications in downstream tasks such as information retrieval, machine translation and knowledge acquisition. We introduce the Yara Parser, a fast and accurate open-source dependency parser based on the arc-eager algorithm and beam search. It achieves an unlabeled accuracy of 93.32 on the standard WSJ test set which ranks it among the top dependency parsers. At its fastest, Yara can parse about 4000 sentences per second when in greedy mode (1 beam). When optimizing for accuracy (using 64 beams and Brown cluster features), Yara can parse 45 sentences per second. The parser can be trained on any syntactic dependency treebank and different options are provided in order to make it more flexible and tunable for specific tasks. It is released with the Apache version 2.0 license and can be used for both commercial and academic purposes. The parser can be found at https://github.com/yahoo/YaraParser.

1 Introduction

Dependency parsing represents syntactic dependencies among words and supports important NLP applications. Yara is introduced as a fast, accurate, open-source dependency parser evaluated on the standard English WSJ test set.

  • Dependency trees explicitly represent syntactic dependencies among words in a sentence.
  • Graph-based and transition-based models are the two main approaches to dependency parsing.
  • Yara is presented as a newly released dependency parser that combines high accuracy with high speed.
  • The report evaluates Yara on the standard English WSJ test set and provides technical, experimental, and usage details.

2 Using Yara in Practice

This section introduces ways to train and use Yara from the command line or API, including an NLP pipeline for parsing text files.

  • Yara can be trained and used from the command line or through an API.
  • The section also introduces a simple NLP pipeline that parses text files.
  • Yara’s default settings are expected to provide the best practical accuracy, while training iterations depend on the data and feature settings.

2.1 Data format

Yara uses the CoNLL 2006 dependency format for training and testing, while reading only selected columns from each tabular sentence representation.

  • Yara uses the CoNLL 2006 dependency format for both training and testing.
  • Each word occupies one tab-delimited line, and sentences are separated by a blank line.
  • Yara uses columns for word number, word form, coarse-grained POS tag, head, and dependency label.

2.2 Training and Model Selection

Yara training uses a jar-based command-line workflow with configurable data, model, punctuation, clustering, beam, iteration, oracle, case, labeling, threading, and root-position options.

  • Training workflow: Yara trains from CoNLL files using specified training, development, and model-file paths.
  • Training workflow: Model checkpoints are saved for each training iteration, allowing selection of a preferred model using development data or prior knowledge.
  • Configurable options: Brown cluster features, beam width, training iterations, labeled versus unlabeled parsing, and lowercasing are configurable options.
  • Configurable options: Oracle choice, update strategy, thread count, and root placement can be selected through static, early, random, nt, and root_first options.
  • Task-specific settings: A user-specified punctuation-tag file lets Yara adapt punctuation handling to the task instead of relying only on hard-coded rules.
  • Practical configurations: Fast training and parsing configurations use basic features and beam:1, while Brown clusters and larger beams support accuracy-oriented settings.
  • Practical configurations: The JVM -Xmx option can increase memory for datasets requiring more than Java’s default allocation.

2.3 Test and Evaluation

Yara accepts CoNLL or tagged test files and produces CoNLL output, with command-line parsing and evaluation workflows.

  • The test file can be either a CoNLL file or a POS tagged file, and the output is produced in CoNLL format.
  • The parser provides separate command-line commands for parsing CoNLL files and tagged files.
  • Tagged input separates words and tags with a delimiter, using underscore by default or a user-specified delimiter.
  • Evaluation requires both the gold file and parsed file to use CoNLL format.
  • An end-to-end German example using a small amount of training data is available in Yara’s GitHub repository.

2.4 Parsing a Partial Tree

Yara supports constrained parsing of partial dependency trees by completing unknown dependencies while preserving the supplied dependencies.

  • Yara parses partial trees by returning a dependency tree consistent with the provided gold dependencies.
  • Unknown dependencies are represented with “-1” as the head in the CoNLL format.
  • Figure 1 illustrates a partial dependency tree before and after constrained parsing.
  • The constrained-parsing mode is invoked with the parse_partial command and input, output, and model files.

2.5 Yara Pipeline

Yara provides an application pipeline that combines tokenization, sentence delimiting, and POS tagging with dependency parsing.

  • The pipeline uses the OpenNLP tokenizer and sentence delimiter together with Yara’s POS tagger.
  • Users must download language-specific sentence-boundary and word-tokenizer models from OpenNLP, or train new models there.
  • The pipeline supports changing the number of parsing threads through the nt:[#nt] option.
  • Command-line pipeline usage specifies input and output files plus parsing, POS, tokenizer, and sentence-detector model paths.

2.6 Pipeline API usage

The Yara API and pipeline expose multiple parsing entry points, returning structured parse results or CoNLL output for files, raw text, sentences, tokenized sentences, and tagged sentences.

  • The pipeline offers an easier interface than the direct Yara API and lets users set the number of parsing threads.
  • ParseResult contains words, POS tags, dependency labels and heads, plus normalized tagging and parsing scores.
  • File parsing requires parser, POS, tokenizer, and sentence-boundary models and writes results in CoNLL format.
  • Raw text is parsed through YaraPipeline.parseText after initializing the required model information.
  • Individual sentences can be parsed with YaraPipeline.parseSentence, whose ParseResult can be converted to CoNLL output.
  • Pre-tokenized sentences use parseTokenizedSentence, while pre-tagged sentences use parseTaggedSentence with word and tag arrays.

3 Yara Technical Details

Yara combines arc-eager transition-based parsing with beam search, flexible training choices, and configurable features and execution options. Its technical design includes unshift handling, oracle and update variants, speed–accuracy trade-offs, and support for specialized parsing workflows.

  • Parsing and search: Yara uses arc-eager transitions with beam search to reduce local decision errors, while greedy search corresponds to a beam size of one.The parser supports configurable beam width and uses the same search procedure for training and decoding.
  • Configuration and extensions: Yara allows tuning across roughly 128 setting combinations, including root position, feature set, update method, oracle selection, beam width, and Brown-cluster use.The final root position is the default, and users can select unlabeled parsing, partial parsing, multithreading, model iteration, scoring, or lowercasing options.
  • Arc-eager extensions: The unshift action returns the first stack word to the buffer when the root is initial, preserving the tree constraint and slightly improving performance.The original algorithm could connect remaining stack words directly to the root, especially during greedy parsing.
  • Training updates: Yara supports early and max-violation beam updates, with max-violation updating weights at the beam state where the classifier makes its worst mistake against the gold action.The default setting uses max-violation update, while early update is available as an option.
  • Oracle choices: Yara supports static and dynamic oracles, including a highest-scoring zero-cost oracle option that becomes the default because experiments found slightly better results.Dynamic oracles allow the learner to choose among valid action sequences reaching the same gold tree.
  • Features: The extended feature set and Brown word-cluster features improve performance at the expense of speed, while basic local features provide a faster alternative with lower accuracy.Brown features use cluster representations for words in the buffer and stack, including prefixes and full cluster bit strings.

4 Experiments

Yara is evaluated on WSJ and Persian dependency data, with experiments examining accuracy, parser comparisons, and the speed–performance effects of beam size. The Persian evaluation also measures performance when training data includes non-projective trees.

  • 4.1 Parsing WSJ Data: The WSJ data use the traditional train–development–test split, automatic POS tags, Brown cluster resources, and eight parser threads on a 20-core machine.The experiments use Yara version 0.2; the POS tagger uses 10-way jack-knifing on the training data.
  • 4.1 Parsing WSJ Data: WSJ experiments vary beam size and Brown cluster features, compare Yara with prior parsers, and report UAS, LAS, and sentences per second.Accuracy scores ignore punctuation, and Yara’s accuracy is reported as very close to the state of the art.
  • 4.1 Parsing WSJ Data: Changing the beam size from 64 to 8 can speed parsing by a factor of three with a small relative loss in performance.After beam size eight, performance changes less than in the comparison between beam sizes one and two.
  • 4.2 Parsing Non-Projective Languages: Persian: Compared with the Mate parser, Yara has a 1.35% gap in unlabeled accuracy on the Persian treebank.The paper relates this gap to the presence of non-projective trees and arcs in the training data.

5 Conclusion and Future Work

The paper presents Yara as a fast, accurate, open-source dependency parser and identifies non-projectivity handling and continuous-value features as future extensions.

  • 5 Conclusion and Future Work: Yara is presented as a fast and accurate open-source dependency parser intended for use in different downstream tasks.The conclusion also highlights its flexible license.
  • 5 Conclusion and Future Work: Brown cluster assignments are slightly limited for multi-word verbs because the clusters are trained on single words.The paper notes that this mismatch can cause a slight loss in performance.
Loading 1503.06733v2…