Modeling Reduplication with 2-way Finite-State Transducers

Hossep Dolatian, Jeffrey HeinzEMNLP 2018

TL;DR

This paper introduces a novel approach to modeling reduplication, a common but challenging linguistic phenomenon, using 2-way finite-state transducers (2-way FSTs). Unlike traditional finite-state methods that struggle with the unbounded nature of reduplication, 2-way FSTs offer a more expressive and linguistically motivated solution, capable of capturing the full typology of reduplication without state explosion.

What Problem Does This Paper Address?

Reduplication, the repetition of a part or all of a word (e.g., "walk-walk" for a continuous action), is a widespread morphological process across languages. While computational linguists often use finite-state transducers (FSTs) to model morphology, standard 1-way FSTs face significant challenges with reduplication. Specifically, they cannot easily handle the "unbounded copying" required for total reduplication (repeating an entire word) and tend to suffer from a "state explosion" when trying to model partial reduplication (repeating only a part of a word). This has led to either approximations or the use of more complex, non-finite-state formalisms. The authors aim to show that a less commonly used type of FST, the 2-way FST, can elegantly and comprehensively model reduplication.

Methods

The core of this paper is the introduction and application of 2-way finite-state transducers (2-way FSTs). Unlike standard 1-way FSTs, which can only move forward on the input tape, 2-way FSTs can move both forward and backward on the input tape. This bidirectional movement on the input, while still only moving forward on the output tape, grants them increased expressive power. The authors formally define 2-way FSTs and then demonstrate their utility by constructing models for two key types of reduplication:

  • Total Reduplication: This is modeled by having the 2-way FST read the input tape once to produce the first copy of the word, then move back to the beginning of the input tape to read it again and produce the second copy.
  • Partial Reduplication: The paper shows how 2-way FSTs can handle more complex partial reduplication, including cases with phonological modifications to the reduplicated part, by leveraging their ability to move back and forth on the input to identify and copy specific segments.

The authors emphasize that these 2-way FST models are deterministic and do not suffer from state explosion, making them practical for computational implementation.

Datasets

The paper does not introduce new datasets for training or evaluation. Instead, it draws upon existing linguistic literature and databases to exemplify the typology of reduplication. The authors mention the RedTyp database, which they constructed, containing entries for 138 reduplicative processes from 91 languages. This database serves as a benchmark for the empirical coverage of their approach, with 57 distinct 2-way FSTs designed to model these processes.

Key Insights and Ideas

  • 2-way FSTs elegantly solve the "unbounded copying" problem: The ability to reread the input tape allows 2-way FSTs to naturally model total reduplication without needing to hardcode or approximate infinite repetitions.
  • No state explosion for partial reduplication: Unlike 1-way FSTs, the complexity of 2-way FSTs for partial reduplication is not dependent on the size of the alphabet, making them more scalable and efficient.
  • Linguistic Motivation: The authors argue that 2-way FSTs align better with linguistic theories of reduplication, particularly those focusing on "origin semantics" (where segments in the output are traced back to their source in the input). 2-way FSTs naturally associate segments of the reduplicant with identical segments in the base, mirroring theoretical accounts.
  • Practicality and Conciseness: The constructed 2-way FST models are shown to be concise (e.g., averaging 8.8 states in the RedTyp database) and convenient for describing and modeling reduplicative morphology.

Key Results

  • The paper demonstrates that 2-way FSTs can model virtually the entire typology of reduplication, including total and various forms of partial reduplication, without approximation.
  • The authors successfully constructed 57 distinct 2-way FSTs for the RedTyp database, showcasing the practical applicability of their approach.
  • They argue that 2-way FSTs are empirically adequate, practically convenient, and linguistically motivated for modeling reduplication, contrasting them with the limitations of 1-way FSTs.

Limitations and Future Work

  • Marginal Cases: The authors acknowledge two marginal cases of reduplication in the literature that are difficult to model with 2-way FSTs without making specific assumptions about suppletive allomorphs or banning homophonies.
  • Over-generation: 2-way FSTs can sometimes "over-generate," modeling unattested types of reduplication (e.g., reversing words). This can be addressed by restricting the class of 2-way FSTs or by not expecting exact models of human cognition.
  • Morphological Analysis: While the paper focuses on generation (input to output), the inverse problem of morphological analysis (output to input) using 2-way FSTs remains an open question, though non-deterministic 2-way FSTs are suggested as a potential route.
  • Integration into NLP Systems: A significant future direction is integrating 2-way FSTs into existing NLP platforms like xfst, foma, and open-fst.
  • Subclasses of 2-way FSTs: Investigating specific subclasses of 2-way FSTs could lead to tighter fits with reduplicative typology and enable better learning algorithms.
  • Copying in Other Linguistic Domains: The authors propose exploring whether 2-way FSTs can model copying phenomena in other areas of linguistics, such as syntax.

Summary updated

BibTeX
@inproceedings{dolatian2018modeling,
  author = {Hossep Dolatian and Jeffrey Heinz},
  title = {{Modeling Reduplication with 2-way Finite-State Transducers}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2018},
}

Loading related content...

Figure