Empirical Knowledge Representation Generation Using N-Gram Clustering

Robin CollierAAAI 1994

Abstract

In the early 1990s, the scalability of Information Extraction (IE) and Information Retrieval (IR) systems was significantly hindered by the requirement for manually engineered templates. This paper proposes a stochastic alternative: a method for automatically generating domain-specific semantic representations from text corpora using n-gram clustering. By identifying frequently occurring and widely distributed phrases, the system groups related paragraphs into conceptual templates, effectively building a knowledge base without human intervention.

Introduction

During the formative years of Information Extraction, systems relied heavily on "key templates"—predefined structures that dictated the specific types of information a system should extract from a document. While effective in narrow applications, these templates created a development bottleneck. Every new domain required significant human expertise and time to engineer the necessary rules.

While contemporary research, such as the AutoSlog system, attempted to automate dictionary generation, this work argues for a more purely stochastic approach. Rather than relying on manual engineering or heavy linguistic parsing, the goal is to develop a system capable of analyzing a corpus and autonomously identifying the underlying conceptual structures.

Methodology: The Six-Step Algorithm

The proposed architecture utilizes a series of data structures to map a corpus into a numeric representation, allowing for the identification of patterns through statistical distribution. The process follows six primary stages:

  1. Word-to-Integer Mapping: To facilitate computational efficiency, every unique word in the corpus is assigned a unique integer identifier.
  2. Conversion: The source text is converted into a numeric stream. Pointers are established to maintain the original word order, allowing the system to reference the source text during analysis.
  3. Phrase Length Identification: The system scans the numeric stream to identify the longest phrases (n-grams) that appear multiple times across the corpus.
  4. N-gram Filtering: The system identifies the "n-best" n-grams. This selection is based on a combination of frequency (how often they appear) and distribution (how widely they are spread across different sections of the corpus).
  5. Paragraph Weighting: Each paragraph is assigned a weight based on the quality and frequency of the n-grams it contains. This step identifies which segments of text are most representative of specific concepts.
  6. Clustering: Finally, the system identifies clusters of paragraphs that share correlating n-grams. These clusters represent the "schematic structures" or conceptual templates inherent to the domain.

Key Architectural Insights

Structure from Distribution

The core thesis of this approach is that semantic similarity can be inferred from the statistical distribution of n-grams. If specific phrases consistently appear together across disparate paragraphs, those paragraphs likely share a conceptual template. This allows the system to move from raw text to a structured representation of knowledge without requiring a pre-defined ontology.

Dynamic Knowledge Updating

Unlike static models, this system is designed for "live" environments. When new text is introduced, the system can check for novel concepts and dynamically update its knowledge base. This ensures that the generated representation evolves alongside the corpus.

Efficiency via Data Structures

To optimize the identification of repeating patterns, the system utilizes data structures that group identical words together, ordered by group size. While this results in a temporary loss of word order within the primary array, the secondary pointer-based structure allows the system to reconstruct the sequence when necessary. This trade-off was specifically designed to handle the computational constraints of identifying long-range correlations in large datasets.

Discussion and Future Work

As a proof-of-concept architecture presented in the AAAI-94 Student Abstract proceedings, this work focuses on the framework rather than benchmarked quantitative results. The qualitative success of the system lies in its ability to identify useful clusters of n-grams that correlate across paragraphs, providing a roadmap for domain specialists to navigate massive knowledge bases.

However, several challenges remain. The author acknowledges the need for a rigorous evaluation of the quality of the generated representations. One proposed method for validation is a "Turing-like" test: comparing the system’s output directly against representations generated by a panel of human experts. Additionally, while the data structures are optimized, the computational complexity of correlating n-grams across massive corpora remains a significant hurdle for the hardware of the era. Future research will focus on refining these statistical filters to improve the precision of the generated templates.

Summary updated

BibTeX
@inproceedings{collier1994empirical,
  author = {Robin Collier},
  title = {{Empirical Knowledge Representation Generation Using N-Gram Clustering}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure