TRAVERSAL at PARSEME Shared Task 2018: Identification of Verbal Multiword Expressions Using a Discriminative Tree-Structured Model

Jakub WaszczukCOLING 2018

TL;DR

This paper presents TRAVERSAL, a system that achieved first place in the PARSEME Shared Task 2018 for identifying verbal multiword expressions (VMWEs). It frames VMWE identification as a tree labeling problem, leveraging a discriminative tree-structured model to achieve state-of-the-art results across multiple languages.

What Problem Does This Paper Address?

Verbal Multiword Expressions (VMWEs) are challenging to identify automatically because they often deviate from standard syntactic structures. These expressions, like "look up" or "give in," can be idiomatic, discontinuous, or have complex syntactic behavior. Existing methods often struggle with the variety and complexity of VMWEs, especially when they appear in different languages. The PARSEME shared task aimed to advance the automatic identification of these expressions across a wide range of languages, pushing the boundaries of natural language processing.

Methods

TRAVERSAL tackles VMWE identification by treating it as a tree labeling task. Given a dependency parse tree of a sentence, the system assigns one of two labels to each node: "MWE" or "not-MWE." The core innovation lies in how it models this labeling process.

  1. Tree-Structured Model: Instead of processing sentences linearly, TRAVERSAL operates on the dependency tree structure. This is crucial because VMWEs can be discontinuous, meaning their constituent words might not be adjacent in a linear sentence but are connected in the dependency tree.
  2. Hypergraph Encoding: The system encodes all possible labelings of a dependency tree into a hypergraph. Each path through this hypergraph corresponds to a unique labeling of the tree.
  3. Discriminative Logistic Regression: A multiclass logistic regression model is used to score these hyperpaths. This model learns to discriminate between plausible and implausible VMWE labelings by considering local contextual features (e.g., dependency labels, word forms, POS tags, and labels of adjacent nodes).
  4. Segmentation Heuristic: After labeling, a simple heuristic is used to determine the boundaries of VMWEs: adjacent nodes labeled as MWEs of the same category are assumed to form a single VMWE occurrence.

Datasets

The system was trained and evaluated on datasets from the PARSEME Shared Task 2018, which included treebanks annotated with VMWEs for 20 languages. The authors used Polish and French datasets to determine feature templates and then applied the system to all available languages for the shared task.

Key Insights and Ideas

  • Dependency Trees as the Right Structure: Framing VMWE identification as a tree labeling problem on dependency parses is highly effective, especially for handling discontinuous VMWEs.
  • Discriminative Modeling for Global Optimization: Using a discriminative model like logistic regression to score entire tree labelings (via hyperpaths) allows for finding the globally optimal labeling, rather than making local decisions that might not be globally consistent.
  • Feature Engineering is Key: The choice of features (unary, binary parent-child, binary sibling) significantly impacts performance, and careful selection based on development data is crucial.
  • Segmentation is a Separate, Simpler Problem: While labeling is complex, segmenting the identified MWEs can be handled with relatively simple heuristics, though this is acknowledged as a potential area for improvement.

Key Results

TRAVERSAL achieved first place in the general cross-lingual ranking of the PARSEME Shared Task 2018, excelling in both MWE-based F₁ and token-based F₁ evaluation measures. The paper reports strong performance across many languages, particularly Slavic and Romance languages. The system demonstrated robustness even on datasets with automatically derived dependencies. It performed particularly well on discontinuous VMWEs and inherently adpositional verbs.

Limitations and Future Work

The authors acknowledge that the MWE segmentation component is "rudimentary." Future work includes exploring more sophisticated joint MWE segmentation and labeling, incorporating external resources like MWE dictionaries and word embeddings, and investigating the use of ternary features. A more fine-grained error analysis is also planned to better understand the system's strengths and weaknesses.

Summary updated

BibTeX
@inproceedings{waszczuk2018traversal,
  author = {Jakub Waszczuk},
  title = {{TRAVERSAL at PARSEME Shared Task 2018: Identification of Verbal Multiword Expressions Using a Discriminative Tree-Structured Model}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2018},
}
Figure