Automatic Extraction of New Words from Japanese Texts using Generalized Forward-Backward Search

Masaaki NagataEMNLP 1996

Abstract

In languages like Japanese, word segmentation is a prerequisite for most natural language processing tasks. However, the presence of out-of-vocabulary (OOV) words often leads to segmentation errors. This paper introduces a robust statistical framework for identifying new words by treating extraction as a search for high-probability substrings across all possible segmentations of a sentence. By utilizing a generalized Forward-Backward search to calculate the "expected frequency" of substrings, the system can identify likely new vocabulary even when initial segmentation is ambiguous.

Introduction: The Segmentation Challenge

Unlike English, Japanese text lacks explicit word boundaries (spaces). This makes word segmentation—deciding where one word ends and the next begins—the fundamental hurdle for downstream NLP tasks. Traditional systems rely on pre-defined dictionaries, but language is dynamic; new technical terms, slang, and proper nouns appear constantly. When a segmenter encounters an unknown word, it often misidentifies surrounding words, creating a "hallucination" of known but incorrect short words.

The core innovation presented by Masaaki Nagata is the Generalized Forward-Backward Search. This method breaks the dependency on a fixed dictionary by modeling unknown words statistically.

The Statistical Word Model

Instead of ignoring unknown words, the authors define a model where an OOV word's probability is decomposed into:

  1. Word Length: Modeled using a Poisson distribution.
  2. Spelling: Modeled using a character-based bigram model to capture the "look and feel" of Japanese words.

N-Best Approximation and Expected Frequency

Calculating every possible segmentation is computationally prohibitive. The authors employ an N-best word segmenter to identify the top $N$ most likely interpretations of a sentence.

Figure 1: Example of N-best word segmentation hypotheses for a sentence containing unknown words.

By summing the probabilities of a specific substring across these N-best segmentations, the system calculates its expected frequency. If a substring appears frequently across a corpus but is absent from the dictionary, it is flagged as a potential "new word."

Figure 4: Calculation of expected frequency by summing probabilities across multiple segmentation hypotheses.

Experimental Evaluation

The authors utilized the EDR Japanese Corpus Version 1.0, containing approximately 5 million words. 90% of the corpus was used for training, with the remainder reserved for testing segmentation and extraction accuracy.

Key Results

  • Segmentation Accuracy: The system achieved a 94.7% recall and 89.9% precision using a word bigram model.
  • New Word Extraction: On a test set with a 2.1% OOV rate, the system achieved 43.7% recall and 52.3% precision for extracting entirely new words.

The study found that a simple word bigram model often outperformed more complex Part-of-Speech (POS) trigram models, suggesting that local context is more reliable than deep grammatical structures when processing noisy, unknown input.

Conclusion and Future Work

The proposed method effectively accounts for uncertainty by using expected frequency rather than binary counts. While successful, the system faced challenges with very long transliterated foreign words (Katakana) and numeral fragmentation. Future research will investigate the minimum "seed" dictionary size required and methods for automatically assigning Parts-of-Speech to newly extracted terms.

Summary updated

BibTeX
@inproceedings{nagata1996automatic,
  author = {Masaaki Nagata},
  title = {{Automatic Extraction of New Words from Japanese Texts using Generalized Forward-Backward Search}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {1996},
}
Figure