A Procedure for Multi-Class Discrimination and some Linguistic Applications

Vladimir Pericliev, Raul E. Valdes-PerezACL 1998

TL;DR

This paper introduces MPD, a novel computational tool for multi-class discrimination that prioritizes concise and intelligible class descriptions over pure prediction accuracy. By employing three simplicity criteria and allowing for derived features, MPD offers a more linguistically intuitive approach to knowledge discovery, demonstrated through applications in lexicology, phonology, and language typology.

What Problem Does This Paper Address?

Traditional machine learning approaches to multi-class discrimination, like ID3 and C4.5, primarily focus on predicting outcomes for unseen data. While effective for prediction, their generated class descriptions (profiles) are often complex, disjunctive, and difficult for humans to understand. This lack of intelligibility is a significant drawback in fields like linguistics, where the goal is often to uncover and understand the underlying structure and relationships between concepts. The paper addresses this by proposing a method that explicitly aims for parsimonious, conjunctive, and comprehensive class descriptions, making the learned knowledge more accessible and interpretable to domain experts.

Methods

The core of the paper is the Maximally Parsimonious Discrimination (MPD) program. MPD distinguishes itself through several key methodological choices:

  • Three Simplicity Criteria:
    1. Minimize overall features: Selects feature sets with the smallest cardinality.
  • Minimize profiles: Chooses the shortest profiles for each class given an overall feature set.
  • Maximize coordination: Ensures coherence between class profiles within a discrimination model, especially when multiple equally simple alternatives exist.
  • Derived Features: MPD can automatically create new features by combining existing ones (e.g., Boolean features P and Q can form P AND Q, P OR Q, P IFF Q, etc.; nominal features M and N can form MxN; numeric features X and Y can form X*Y). This allows for more expressive and potentially simpler contrasts.
  • Global Optimization: Unlike greedy search methods, MPD uses global optimization to find the best feature sets and profiles, aiming for optimal simplicity.
  • Handling of Missing Values: Missing values are handled gracefully by ignoring them without needing imputation or discarding instances, and can even be treated as a distinct feature value for nominal features.
  • Absolute and Partial Contrasts: MPD can distinguish between absolute contrasts (where all instances of different classes are clearly separated) and partial contrasts (where a small percentage of instances can be removed to achieve separation), offering flexibility.

Datasets

The paper demonstrates MPD's capabilities using several linguistic datasets:

  • Bulgarian translational equivalents of the English verb "feed": Used to illustrate learning translational equivalents based on verb case frames.
  • Kinship terminologies: Applied to datasets from over 20 languages, including Bulgarian and English, to perform componential analysis.
  • Russian phonemic system: Data from Cherry et al. (1953) consisting of 42 Russian phonemes described by 11 binary features.
  • Greenberg's (1966) word order universals: A dataset of 30 languages with 15 features (4 nominal, 11 binary) to discover linguistic typologies.
  • CHILDES database (English aphasic patients): Transcripts of verbal responses from control subjects and patients with anomia, Broca's disorder, Wernicke's disorder, and nonfluents, coded with linguistic errors.

Key Insights and Ideas

  • Intelligibility as a Primary Goal: The paper strongly advocates for making learned models understandable to humans, particularly in fields like linguistics, where the output is often for expert interpretation rather than automated action.
  • Derived Features Enhance Expressiveness: The ability to automatically generate new features is crucial for capturing complex interactions and creating more concise, intuitive contrasts that might not be apparent from primitive features alone.
  • Parsimony Leads to Unique Solutions: The strict application of parsimony criteria (minimizing features and profiles) can significantly reduce the vast number of potential discrimination models, often leading to a single, most appropriate solution.
  • Linguistic Intuition Aligns with Computational Goals: The paper highlights how the desired properties of linguistic analysis (parsimony, conjunctiveness, comprehensiveness) align well with the computational goals of MPD.
  • Flexibility in Application Types: MPD can be adapted for different learning scenarios (human-readable vs. machine-readable output, prediction vs. no prediction), with different heuristic hierarchies becoming more suitable for each type.

Key Results

  • Linguistics Applications:
    • Lexicology (Kinship): MPD successfully found parsimonious and conjunctive models for kinship terminologies across numerous languages, improving upon or confirming classical analyses.
  • Phonology: For Russian phonemes, MPD confirmed the necessity of 11 primitive features but found simpler profiles than a previous study, averaging 6.14 components per phoneme.
  • Language Typology: In analyzing Greenberg's word order universals, MPD found that only 12 out of 435 pairwise discriminations were impossible, using a minimal set of 8 features.
  • Speech Pathology (Aphasia): MPD achieved successful discrimination of aphasic patients, with derived features and partial contrasts proving essential for handling complex cases and achieving more interpretable profiles.
  • Efficiency: The paper notes that MPD's global optimization, while computationally expensive, is implemented with heuristics to manage combinatorics.

Limitations and Future Work

  • Inability to Handle Inherently Disjunctive Concepts: The paper acknowledges that MPD struggles with concepts that are fundamentally disjunctive, which can be a limitation in certain tasks.
  • Trade-offs for Conciseness: Users might sometimes need to sacrifice conciseness (e.g., by choosing simpler primitive features over more complex derived ones) to avoid combinatorial problems.
  • Future Work: The authors express their ongoing focus on finding novel application areas for MPD. They also mention the potential for using MPD's output for classification rules and have explored its application on non-linguistic datasets like the LED-24 dataset.

Summary updated

BibTeX
@inproceedings{pericliev1998procedure,
  author = {Vladimir Pericliev and Raul E. Valdes-Perez},
  title = {{A Procedure for Multi-Class Discrimination and some Linguistic Applications}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1998},
}
Figure