Unsupervised Learning of Morphology for English and Inuktitut

Howard Johnson, Joel MartinNAACL 2003

TL;DR

This paper introduces a simple, unsupervised method for learning word morphology by identifying "hubs" in a word automaton. This technique achieves performance comparable to more complex methods for English and shows promise for agglutinative languages like Inuktitut, offering a more generalizable approach to morphological analysis.

What Problem Does This Paper Address?

Understanding word structure, or morphology, is crucial for natural language processing. Specifically, identifying morpheme boundaries (like the split between a root and a suffix) is a fundamental challenge. Traditional methods often require large amounts of labeled data or rely on complex algorithms. This paper tackles the problem of unsupervised morphological analysis, aiming to discover these boundaries without pre-existing linguistic knowledge, and proposes a method that is both simple and potentially more generalizable to diverse language structures.

Methods

The core of the proposed method lies in identifying "hubs" within a word automaton.

  1. Trie Construction: A standard trie (a tree-like data structure for storing strings) is built from a corpus of words.
  2. DFA Minimization: The trie is then converted into a minimal, deterministic finite automaton (DFA). This process merges nodes that represent identical continuations of prefixes, simplifying the automaton.
  3. Hub Identification: A "hub" is defined as a node in this minimal DFA with both an in-degree greater than one and an out-degree greater than one. These hubs are hypothesized to mark morpheme boundaries.
  4. Stretched Hubs: The authors also consider "stretched hubs," which are direct descendants of high in-degree nodes along a single path.
  5. Node Merging (HubMorph): To handle cases where a signature (a set of suffixes for a root) appears only once, a simple node merging technique is proposed. This involves merging final states with hubs or stretched hubs that have an in-degree greater than two, which increases the automaton's coverage but may introduce non-words.

Datasets

The primary dataset used for evaluation is the text of "Tom Sawyer." The authors compare their system's performance against a gold standard division of the distinct words in this novel, which was based on dictionary entries and the judgment of two English speakers.

Key Insights and Ideas

  • Hubs as Morpheme Boundaries: The central idea is that nodes with multiple incoming and outgoing paths in a word automaton naturally represent points where different morphemes can combine.
  • Simplicity and Generality: The proposed hub-identification technique is remarkably simple compared to existing methods, yet it achieves competitive performance. This suggests that a fundamental structural property of language (represented by hubs) can be a powerful signal for morphological analysis.
  • Potential for Agglutinative Languages: The authors highlight that this approach is more general than previous signature-based methods and holds promise for languages with complex morphology, like Inuktitut, where a single word can be composed of many morphemes.
  • Trade-off in Node Merging: The simple node merging strategy effectively increases recall by allowing more word divisions but at the cost of potentially lower precision due to the inclusion of non-words.

Key Results

  • For English, the "HubMorph" system (combining hub searching and node merging) achieved performance comparable to a more complex system called "Linguistica."
  • Specifically, HubMorph achieved a precision of 0.9215 and a recall of 0.5904 on the "Tom Sawyer" dataset.
  • Hub-searching alone also performed well, with a precision of 0.9189 and a recall of 0.4451.
  • For Inuktitut, the system achieved a precision of 31.8% and a recall of 8.1%, indicating that while the approach is promising, further refinement is needed for such complex languages.

Limitations and Future Work

  • Handling Rare Signatures: The simple node merging technique is a first step to address rare signatures but can lead to the inclusion of non-words.
  • Complexity in Inuktitut: For languages like Inuktitut, which have many morphemes per word and complex internal structures (infixes, suffixes, no clear prefixes), detecting divisions accurately is challenging. The current method struggles with the sheer number of potential divisions and the lack of clear prefixes.
  • Dialectal Variation: Spelling variations and dialectal differences in languages like Inuktitut pose an additional challenge for unsupervised learning.
  • Future Work: The authors plan to generalize their hub-automaton approach to handle more complex morphologies, potentially by incorporating semantic cues or more sophisticated merging strategies. They believe hub-automata can form the basis of a general solution for a wide range of languages.

Summary updated

BibTeX
@inproceedings{johnson2003unsupervised,
  author = {Howard Johnson and Joel Martin},
  title = {{Unsupervised Learning of Morphology for English and Inuktitut}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2003},
}
Figure