Interactive Word Completion for Plains Cree

William Lane, Atticus Harrigan, Antti ArppeACL 2022 · DOI

Abstract This paper presents an interactive morph-based word completion tool for Plains Cree, a polysynthetic language where words often encompass the complexity of entire sentences. By utilizing Finite State Transducers (FSTs) and corpus-based ranking strategies, the system assists users in building complex words incrementally. Evaluation results indicate that a Prefix Weighted FST (pWFST) ranking significantly improves suggestion accuracy, placing the target completion in the top 10 for 64.9% of queries, outperforming more complex neural language models.

Introduction

In polysynthetic languages like Plains Cree (nêhiyawêwin), words function as complex units of meaning, often equivalent to entire sentences in English. This structural complexity poses significant challenges for standard Natural Language Processing (NLP) tools. While English word completion typically involves predicting the remainder of a single lexeme, Plains Cree requires a system capable of navigating a vast "combinatorial explosion" of potential morphemes.

Researchers have developed an interactive word completion tool designed specifically for these linguistic properties. Rather than suggesting entire words, the system employs a morph-based completion approach, guiding users through the construction of words one morpheme at a time. This method helps language learners master complex morphotactics—the rules governing how units of meaning combine—and morphophonology—the spelling changes that occur at morpheme boundaries.

Methodology and System Design

The core of the system relies on Finite State Transducers (FSTs). While FSTs are standard for morphological analysis, the Plains Cree model is exceptionally robust, reflecting over eight years of development. This maturity, however, introduces a "search space" problem: a short prefix can correspond to thousands of valid grammatical continuations.

To address this, the researchers implemented a "fuzzy" search that allows users to type without diacritics (e.g., typing 'a' instead of 'â'), which the system then corrects. The interface, as seen in the Plains Cree Word Builder, suggests the next logical morpheme boundary to help the user incrementally build the target word.

The Plains Cree Word Builder interface demonstrating incremental word construction and morpheme suggestions.

Ranking Strategies

To make the thousands of FST-generated possibilities manageable for a user, the team evaluated several ranking schemes:

  • Prefix Weighted FST (pWFST): Uses corpus-based prefix frequencies to prioritize suggestions.
  • Transition Weighted FST (tWFST): A memory-efficient alternative that weights transitions between states.
  • Transformer Language Model (LM): A character-based neural model used to rerank the top 500 FST candidates.

Surprisingly, the simpler pWFST outperformed the neural Transformer model. This suggests that in low-resource language contexts, direct lexical statistics from a representative corpus can be more effective than the probability distributions of complex language models.

Evaluation and Results

The system was evaluated using the AWB corpus, a collection of approximately 243,000 morphosyntactically-tagged words. The primary metric was the rank of the "target" completion within the suggested list. Without ranking, only 38.4% of queries placed the correct completion in the top 10. With the pWFST ranking, this figure rose to 64.9%.

Analysis of the rank of valid completions relative to the length of the input prefix, showing improved accuracy as more characters are entered.

As shown in the performance analysis, the rank of the valid completion generally improves as the prefix length increases, though the system remains effective even with relatively short inputs. Qualitatively, the tool proved highly effective at assisting learners with complex circumfixes—markers that appear at both the start and end of a word—by providing orthographic confidence in real-time.

Conclusion and Future Directions

The interactive word completion tool represents a significant step in supporting polysynthetic language learners. While the pWFST model is the most accurate, its large file size (>100MB) presents challenges for mobile deployment, where the smaller tWFST model may be preferable.

Future work will focus on expanding the training corpus to include more modern vocabulary and conducting extrinsic user testing with the Cree community to evaluate the tool's impact on language acquisition and daily communication.

Summary updated

BibTeX
@inproceedings{lane2022interactive,
  author = {William Lane and Atticus Harrigan and Antti Arppe},
  title = {{Interactive Word Completion for Plains Cree}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2022},
  doi = {10.18653/v1/2022.acl-long.232},
}
Figure