Cognitive Classification

AAAI 1999

TL;DR

This paper introduces "Cognitive Classification," a novel algorithm designed for classification tasks with small, noisy, or dynamic datasets, common in real-world decision-making. It mimics human cognitive processes by deriving case-specific rules from a small subset of similar examples, focusing on the most informative features, and then applying a logical semantic measure to make a decision. This approach demonstrates superior performance on challenging datasets compared to traditional decision tree and neural network methods, especially when training data is scarce.

What Problem Does This Paper Address?

Traditional machine learning classification algorithms, like C4.5, often struggle with real-world data that is small, incomplete, noisy, or constantly changing. In such scenarios, the quality of the data encoding and the inherent noise can overwhelm the classification method itself. This is particularly problematic in domains where collecting large, clean datasets is impractical or prohibitively expensive. The authors aim to bridge this gap by developing a "frugal" classification algorithm that is computationally efficient and effective even with limited data, drawing inspiration from human categorization strategies.

Methods

The proposed "Cognitive Classification" algorithm operates in two main stages:

  1. Filtering (Mimicking Subconscious Recall):
    • Similarity-based Exemplar Selection: The algorithm first retrieves a subset of training examples from memory that are "similar enough" to the current observation. Similarity is measured by the count of common constants in the encoded features.
  2. Feature Relevance Focusing: It then focuses on the most relevant features within these selected exemplars. This is achieved by identifying predicates (features) that convey the highest "relative information" about distinguishing between potential categories. The paper proposes using expected relative entropy as a measure for this.
  3. Deductive Reasoning (Mimicking Conscious Thought):
    • Rule Derivation: Case-specific rules are derived from the filtered exemplars. These rules are generalizations of the exemplar formulae, where identifiers are replaced by variables. The "strength" of a rule is determined by the number of times its generalized form appears in the filtered recall set.
  4. Information-based Rule Selection: A logical semantic information measure is used to assess how much information each derived rule provides about the possible categories, given the observation. The algorithm selects only the most informative rules (typically one or two) to form a "working knowledge base."
    • Hypothesis Testing: The final classification decision is made by assigning the entity to the category for which the selected rules provide the maximal logical semantic information relative to the observation. Ties are broken by considering more features or, in the reported implementation, by the order of rule encounter.

Datasets

The paper evaluates the Cognitive Classification algorithm on standard datasets from the UCI Repository of Machine Learning Databases:

  • Mushroom: Chosen for its susceptibility to conventional techniques.
  • German Credit: Described as moderately difficult.
  • Cleveland Heart: Noted for producing high fractional error rates.

The authors used specific configurations for these datasets, including training sets of 20 examples and test sets of 100 examples, with 5 runs for each. They also mention using a training set of 200 for Mushroom and 500 for Heart and Credit for comparison with C4.5.

Key Insights and Ideas

  • Frugality as a Virtue: The core idea is that for many real-world problems, a "frugal" approach (using minimal data and computation) is not just acceptable but necessary and can lead to surprisingly good results.
  • Mimicking Human Cognition: The algorithm's design is directly inspired by how humans might categorize: a rapid, subconscious filtering of relevant memories followed by a more deliberate, logical deduction.
  • Information-Theoretic Feature Selection: Using measures like relative entropy to identify the most informative features is a powerful way to cut through noise and focus on what truly matters for discrimination.
  • Case-Specific Rule Generation: Generating rules on-the-fly for each observation, rather than building a single, static classifier, allows for adaptation to dynamic or noisy data.
  • The Power of Small Data: The results strongly suggest that with the right approach, small datasets can be leveraged effectively, outperforming methods that rely on large amounts of data.

Key Results

The Cognitive Classification algorithm demonstrated strong performance, particularly on small training sets:

  • Outperforms Standard Classifiers on Small Data: On training sets of 20 examples, it outperformed standard decision tree (CART) and neural network (NeuroShell) classifiers on the UCI datasets.
  • Competitive with Large-Scale Training: On the difficult Cleveland Heart dataset, it achieved comparable performance to classifiers trained on hundreds of examples, using only a training set of 20.
  • Efficiency: The algorithm is designed to be computationally frugal, building a new, simple classifier for each observation.

Limitations and Future Work

The authors acknowledge several areas for future work:

  • Extensive Testing: The algorithm needs to be rigorously tested on datasets similar to those it's designed for, as well as more complex data involving first-order logic.
  • Memory Model: For larger datasets, a more sophisticated model of long-term memory retention is needed, perhaps involving a library of "good" exemplars per category, rather than retaining all past experiences.
  • Attribute Weighting: The current approach treats all attributes equally. Future work could explore modeling how humans treat different categories differently by encoding typical vs. distinguishing features, or allowing users to weight features.
  • Anchoring Effects: The impact of anchoring (prior beliefs influencing decision-making) on classification performance needs further investigation.
  • More Sophisticated Tie-Breaking: While simple tie-breaking was used, more advanced methods could be explored, such as picking the most probable category based on the derived rules.

Summary updated

BibTeX
@inproceedings{1999cognitive,
  title = {{Cognitive Classification}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure