Integrating Models of Discrimination and Characterization for Learning from Examples in Open Domains

IJCAI 1997

This paper tackles a fundamental challenge in machine learning: how to build models that can accurately classify data when the full range of possible categories isn't known beforehand. The authors propose a novel approach that combines two distinct learning strategies to improve classification performance, especially in "open domain" scenarios common in real-world applications.

TL;DR

This paper introduces a hybrid approach to machine learning classification that integrates discriminative and characteristic models. This combination significantly improves performance in "open domain" scenarios where not all possible categories are present in the training data, by first distinguishing known categories and then characterizing them against all possibilities.

What Problem Does This Paper Address?

Many standard machine learning algorithms, like decision trees (ID3, C4.5) or neural networks (backpropagation), are primarily discriminative. They learn to distinguish between the categories present in the training data. However, this leads to a critical flaw in real-world applications, often termed "open domains." In these scenarios, instances from categories not seen during training are frequently misclassified as one of the known categories, rather than being flagged as unknown. This is problematic because, in many applications (e.g., medical diagnosis, fraud detection), it's better to admit ignorance than to provide an incorrect classification. The paper addresses this by aiming to build models that can not only classify known categories accurately but also reliably reject instances belonging to unknown categories.

Methods

The core contribution is the integration of two learning paradigms:

  • Discriminators: Algorithms that learn to distinguish between categories present in the training set (e.g., ID3, IB1).
  • Characterizers: Algorithms that learn descriptions of categories that define their "acceptance region" against all possible categories.

The proposed method involves a two-phase learning process:

  1. Discrimination: First, a discriminative algorithm is used to learn how to separate the categories present in the training data.
  2. Characterization: Then, for each learned category (or "disjunct," e.g., a leaf in a decision tree), a characterization model is built. This characterizer defines an "acceptance region" for that category.

The paper introduces a novel characterization method called the SD (Statistical Distribution) approach. This method leverages statistical information about feature value distributions within each category. It has two versions:

  • Univariate SD: Computes explicit lower and upper limits for each numerical feature, controlling the degree of generalization (and thus the trade-off between rejection and misclassification) via an alpha ($\alpha$) parameter. This is suitable for integration with tree-based discriminators.
  • Multivariate SD: Uses a weighted distance from an instance to the category's "center" (mean vector and covariance matrix) to define an acceptance region. This is more powerful as it can capture covariation between features and is suitable for non-rule-based discriminators like nearest neighbors.

The paper also contrasts SD with the "maximum specific description" (Max) approach, which is simpler but more static and sensitive to noise.

Datasets

The paper evaluates its approach on several datasets:

  • Coin Sorting Application: Custom datasets describing Canadian and Hong Kong coins, with numerical features. These were chosen because existing manual rule-based systems struggled with them.
  • Iris Database: A standard benchmark dataset with three types of Iris plants (Setosa, Versicolor, Virginica) and numerical features. The experiments simulate open-domain scenarios by training on only two of the three classes and testing on all three.

The authors note that the UCI Repository lacks datasets specifically designed for open-domain evaluation (i.e., separate training and test sets with differing category sets), necessitating the simulation approach used for the Iris dataset.

Key Insights and Ideas

  • The "Open Domain" Problem is Pervasive: The paper highlights that most real-world applications are "open domains," where complete knowledge of all possible categories is rarely available. This makes standard discriminative models inherently limited.
  • Integration is Key: Combining discriminative and characteristic learning is a powerful strategy. Discriminators excel at separating known classes, while characterizers provide the crucial ability to reject unknown instances.
  • Controllable Generalization is Crucial: The proposed SD approach offers a significant advantage by allowing explicit control over the degree of generalization through the $\alpha$ parameter. This enables tuning the trade-off between rejecting unknown instances and misclassifying known ones, a critical requirement for practical applications.
  • Statistical Distributions Offer Robust Characterization: The SD approach, by leveraging statistical distributions of feature values, provides a more robust and flexible way to define acceptance regions compared to simpler methods like maximum specific descriptions.
  • Multivariate SD Captures Feature Interactions: The multivariate version of SD is particularly effective as it can model relationships between features, leading to tighter and more accurate acceptance regions.

Key Results

  • Coin Sorting: The integrated ID3-SDuni and IB1-SDmulti approaches significantly outperformed discriminators alone (ID3, IB1), maximum specific descriptions (ID3-Max), and the AQ15c system in the coin sorting task. For instance, IB1-SDmulti achieved perfect classification with no misclassifications of known coins and high rejection rates for foreign coins. The ability to control $\alpha$ was crucial for meeting specific application requirements (e.g., <0.5% misclassification of known coins).
  • Iris Dataset: Similar improvements were observed on the Iris dataset. IB1-SDmulti consistently outperformed ID3-Max and AQ15c, achieving better trade-offs between correct classifications and rejections. The paper notes that even for a relatively "easy" task like Iris classification, the open-domain setting presented challenges that the integrated approach effectively addressed.
  • SD vs. Max: The SD approach was found to be more noise-tolerant and offered better control over generalization compared to the maximum specific description method.

Limitations and Future Work

  • Numerical Features: A significant limitation of both univariate and multivariate SD approaches is that they are currently only applicable to numerical features.
  • Hybrid Approaches: The authors suggest a hybrid approach combining SD for numerical features with a method like "Max" for ordered or nominal features to extend applicability.
  • Future Work: The paper identifies several areas for future research:
  • Developing strategies for selecting appropriate discriminators and characterizers.
  • Creating characterizers that can control generalization for non-numeric features.
  • Further investigating the theoretical relationship between discrimination and characterization.

Summary updated

BibTeX
@inproceedings{1997integrating,
  title = {{Integrating Models of Discrimination and Characterization for Learning from Examples in Open Domains}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1997},
}
Figure