Machine Learning, Clustering and Polymorphy

Stephen Jose Hanson, Malcolm BauerUAI 1985

TL;DR

This paper introduces WITT, a novel conceptual clustering algorithm that models human categorization by embracing polymorphy and relative contrasts between categories, moving beyond traditional AI approaches that rely on strict necessary and sufficient feature rules. This approach demonstrates greater compatibility with human judgment and offers potential improvements for applications like expert systems and information retrieval.

What Problem Does This Paper Address?

Traditional Artificial Intelligence (AI) approaches to machine learning and conceptual clustering often operate under several assumptions that, according to the authors, are inconsistent with how humans actually categorize information. These assumptions include:

  • Necessary and Sufficient Features: Categories are defined by a strict set of features that must be present (necessary) and only those features (sufficient).
  • Equivalence Classes: Categories are treated as rigid sets where all members are equally representative.
  • Polymorphy as Noise: Categories with members lacking necessary or sufficient features are dismissed as uninteresting or erroneous.
  • Probability vs. Symbolism: Probabilistic measures are seen as incompatible with symbolic manipulation.
  • AI Assumptions Match Human Data: The above assumptions are believed to align with human categorization.

The authors argue that psychological research suggests humans are more flexible, relying on prototypical members, relative "contrasts" between categories, and polymorphous rules (where members don't need all features). This disconnect between AI models and human cognition limits the effectiveness of AI systems in areas that require human-like understanding, such as expert systems and information retrieval. The paper aims to bridge this gap by proposing a categorization scheme that better reflects human cognitive processes.

Methods

The paper introduces the WITT (What-If-Then-That) algorithm, a conceptual clustering program designed to model human categorization. WITT's approach is a generate-and-test algorithm with an escalation mechanism over category formation states. The core strategy involves:

  • Embracing Polymorphy: Unlike traditional methods, WITT explicitly allows for categories where members may not possess all defining features. This is managed through parameters controlling "cohesion" (how well members fit a category) and "distinctiveness" (how different a category is from others).
  • Relative Contrasts: Categories are formed by minimizing "variance" within a cluster and maximizing "contrasts" between different clusters, reflecting the psychological observation that humans often define categories in relation to others.
  • Prototypicality: WITT identifies "best" or prototypical members for each category.
  • Information-Theoretic Measures: The algorithm uses information-theoretic measures (like information loss) to identify dense regions in feature spaces, which are then used to form initial "protoseeds."
  • Iterative Refinement: WITT cycles through three states:
  • Object Hunting: Assigning objects to existing protoseeds.
  • Protoseed Hunting: Finding new dense regions to form new protoseeds.
  • Proto-Merge: Merging protoseeds if they are too close to maintain distinct identities.
  • Feature Selection Not Attempted: The current approach does not involve explicit feature selection, assuming input features are already relevant.

Datasets

The paper does not explicitly list or introduce new datasets for training or evaluation in the traditional machine learning sense. Instead, it uses:

  • Toy Examples: Figure 1 illustrates polymorphous categories with abstract shapes and colors. Figure 3 presents "disjoint cover" examples using toy train images.
  • Psychological Abstracts: Figure 4 lists seven psychological abstracts, each with a title, author, and keywords. These abstracts were used in a pilot experiment to compare human categorization with WITT's output. The abstracts were selected to have overlapping categories and varying degrees of necessary/sufficient features.

Key Insights and Ideas

  • Human Categorization is Flexible: The most significant insight is that human categorization is not strictly rule-based (necessary and sufficient features) but rather fluid, relying on prototypes, relative comparisons, and a tolerance for variation (polymorphy).
  • Polymorphy is Not Noise: WITT's success in modeling human categorization suggests that polymorphous rules are not errors but a fundamental aspect of how humans organize information.
  • Contrast is Key: Defining categories by their differences from other categories, rather than just their internal properties, is a more psychologically plausible approach.
  • AI Needs to Emulate Human Cognition: For AI systems to be truly effective in domains requiring nuanced understanding (like expert systems), they must move beyond rigid, symbolic logic and embrace more human-like cognitive processes.
  • Witt's Approach is More Comprehensible: Preliminary results suggest that WITT's output is more comprehensible to humans than categories generated by traditional conjunctive clustering algorithms.

Key Results

  • Human Subjects Struggle with Disjoint Cover: In a study using toy train examples, human subjects found it difficult to sort objects according to strict conjunctive rules (necessary and sufficient features) and instead tended to create categories with polymorphy.
  • WITT Matches Human Categorization: In a pilot experiment with psychological abstracts, WITT's categorization output was identical to two out of five human subjects and captured the general results and rationales provided by the subjects.
  • WITT's Output is Interpretable: WITT's output, represented as trees with keywords/descriptors forming polymorphous rules, was found to be more comprehensible than traditional clustering methods.
  • Preliminary Compatibility: The paper concludes that WITT is more compatible with and comprehensible to human subjects than conceptual clustering methods that enforce equivalence classes and disjoint covers.

Limitations and Future Work

  • Feature Selection Not Addressed: The current WITT algorithm does not perform feature selection, assuming the input features are already relevant. Future work could incorporate this.
  • Parameter Tuning: The level of polymorphy is a predefined parameter. Further research could explore how this parameter is learned or adapted.
  • Pilot Experimentation: The human studies are described as preliminary. More extensive empirical testing is needed to validate the findings across a wider range of domains and subjects.
  • Application Domains: While applications in expert systems and information retrieval are discussed, the paper suggests further exploration and implementation in these areas. The authors believe that WITT's approach could lead to more effective knowledge representation and retrieval systems.
  • Theoretical Framework: The paper lays the groundwork for a new theoretical framework for categorization, and future work could expand on this by exploring the implications for other AI tasks.

Summary updated

BibTeX
@inproceedings{hanson1985machine,
  author = {Stephen Jose Hanson and Malcolm Bauer},
  title = {{Machine Learning, Clustering and Polymorphy}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1985},
}
Figure