Learning From Ambiguous Examples

Stephen V. KowalskiAAAI 1994

Abstract

Traditional inductive learning systems typically operate under the assumption that each training example possesses a single, unambiguous interpretation. In domains such as Natural Language Processing (NLP), this assumption is frequently violated, leading to either a combinatorial explosion of data or algorithmic failure. This paper introduces a framework that represents ambiguity directly using exclusive-OR logic and regular expressions. By employing a beam search guided by a formal subsumption operator, the system learns general hypotheses from "fuzzy" data without the computational burden of expanding every possible meaning into Disjunctive Normal Form (DNF).

Introduction

In the early 1990s, most inductive learning research focused on clean datasets where each attribute and classification was clearly defined. However, real-world data—particularly in the realm of Natural Language Processing—is inherently messy. A single word, such as "plant," can function as a noun (a factory or a shrub) or a verb (to place in the ground). When training a system to extract information from text, these ambiguities present a significant hurdle for classical algorithms.

The Problem with Traditional Learners

When faced with ambiguous examples, standard learners like ID3 encounter two primary obstacles:

  1. Combinatorial Explosion: If a system attempts to represent every possible combination of meanings for every word in a sentence, the number of training examples grows exponentially. This makes the learning process computationally intractable.
  2. Algorithmic Limitations: Standard learners are often ill-equipped to handle negated attribute values or the logical "either/or" scenarios that arise from ambiguity. Furthermore, an ambiguous example might follow multiple conflicting paths down a decision tree, leading to inconsistent classifications.

Stephen V. Kowalski addresses these issues by proposing a system that treats ambiguity as a first-class citizen in the data structure, rather than a problem to be solved prior to learning.

Methodology

Representation

The paper proposes a unified language to describe both training data and learned hypotheses, ensuring the learner and the data share the same structural logic. The system represents sentences as ordered lists of items using a regular-expression-based syntax:

  • Kleene stars (*): Wildcards representing any sequence of items.
  • Exclusive Disjunctions ($\oplus$): A set of possible interpretations where only one is valid (e.g., a word is either a singular noun or an adverb).

The Learning Algorithm

The system employs a beam search that progresses from general to specific expressions. The efficiency of this search is driven by a formal definition of subsumption. A hypothesis is considered a match for a training example if the hypothesis is more general than (or equal to) the example. By using a binary Boolean operator to evaluate this relationship, the system can navigate the search space without the need for exhaustive DNF expansion.

Experimental Evaluation

The system was evaluated using data from the Message Understanding Conference (MUC). Raw text sentences were passed through a dictionary-based pre-processor to generate ambiguous representations, tagging words with multiple potential parts of speech or meanings. The goal was to classify sentences based on their informational content, effectively inducing the rules of the domain.

Key Insights

  • Direct Learning: The research demonstrates that it is possible to broaden the scope of inductive learning by bypassing manual disambiguation. The learner can derive robust rules even when the input data is uncertain.
  • Symmetry of Language: Using the same regular-expression language for both examples and hypotheses simplifies the matching process. A hypothesis like "any sentence ending in a singular noun or an adverb" can be directly compared against a specific ambiguous sentence.
  • Efficiency: By avoiding the transformation of data into DNF, the system bypasses the combinatorial explosion that hampered previous attempts to handle multi-interpretation data.

Conclusion and Future Work

The algorithm successfully learned concepts from the MUC domain that were robust enough to serve as information extraction rules. While this symbolic, logic-based approach offers high interpretability, future work is needed to integrate the learner with active performance elements—systems that execute the extracted rules. Additionally, further research is required to determine how this symbolic approach scales compared to modern probabilistic methods when faced with the uncurated, high-noise datasets common in contemporary NLP.

Summary updated

BibTeX
@inproceedings{kowalski1994learning,
  author = {Stephen V. Kowalski},
  title = {{Learning From Ambiguous Examples}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}

Loading related content...

Figure