A Rational Account of Categorization Based on Information Theory

1. Problem Statement

The paper addresses the challenge of modeling human categorization behavior through Rational Analysis. While previous rational analyses (e.g., Anderson, 1991) have successfully modeled human learning by assuming humans minimize mean-squared predictive error within a Bayesian framework, the authors argue that these models rely on specific assumptions about environmental structure (flat partitions) and objectives that may not fully capture the complexity of human cognition.

The core problem is to develop a new theory of categorization that:

1. Adopts a different objective function based on information theory rather than predictive error minimization.
2. Assumes a taxonomic (hierarchical) structure for categories rather than flat, disjoint partitions.
3. Can account for classic experimental findings regarding central tendencies, non-linearly separable categories, and the transition between prototype and exemplar theories.

2. Methodology

Theoretical Framework

The authors propose a rational analysis grounded in Information Theory:

• Objective: Humans learn categories that maximize the Mutual Information (MI) between the category labels and the features of their experiences. This operationalizes Corter and Gluck's (1992) "Category Utility" hypothesis, which posits that a category is useful if it improves the prediction of an instance's features given its label.
• Environment Structure: Categories are assumed to be organized hierarchically (taxonomically), allowing for nested concepts rather than a flat set of disjoint classes.
• Constraints: The system maintains a single hypothesis about category structure, which is incrementally updated after each new experience.

Implementation: Modified Cobweb System

The theory is instantiated using a variant of Fisher's (1987) Cobweb system, a well-known conceptual clustering algorithm. Key modifications include:

• Representation: Instances are attribute-value lists. Concepts are organized in a hierarchy and store probability distributions (categorical for discrete, normal for continuous) over feature values.
• Inference (Prediction):
  • Instead of Fisher's original mechanism, the system uses Best-First Search to expand nodes.
  • The expansion criterion is Pointwise Mutual Information (PMI): $PMI(c, x) = \log \frac{p(x|c)}{p(x)}$.
  • The system expands nodes with the highest PMI up to a limit (max_nodes = 100).
  • Final predictions are a weighted combination of predictions from all activated nodes, weighted by their normalized PMI scores.
• Learning (Taxonomy Update):
  • The system sorts new examples into the hierarchy using a greedy approach.
  • It evaluates four operations (insert, create new node, merge, split) and selects the one that maximizes the expected future mutual information $E_{x,c}[PMI(x,c)]$, which is equivalent to maximizing the mutual information $I(X, C)$ between instances and categories.
  • Feature distributions are updated incrementally.
• Parameters: The system uses a smoothing parameter $\alpha$ (pseudo-counts) and a max_nodes limit for inference depth.

Experimental Evaluation

The authors tested their model against data from three classic categorization experiments:

1. Hayes-Roth & Hayes-Roth (1977): Investigating central tendencies (prototype effects) and recognition.
2. Medin & Schaffer (1978): Experiments 1 and 2, focusing on non-linearly and linearly separable categories to compare against Independent Cue and Context models.
3. Smith & Minda (1998): Experiment 2, examining the transition from prototype-like to exemplar-like behavior over time.

3. Key Contributions

1. New Rational Objective: The paper shifts the rational analysis objective from minimizing predictive error (Anderson, 1991) to maximizing mutual information between categories and features.
2. Hierarchical Assumption: It explicitly incorporates a taxonomic (hierarchical) view of category structure, moving beyond flat partitions.
3. Unified Mechanism: The proposed Cobweb variant demonstrates the ability to exhibit both prototype behavior (abstracting general rules) and exemplar behavior (memorizing specific instances) depending on the learning stage and parameter settings, resolving a long-standing debate in the field.
4. Competitive Performance: The model achieves performance comparable to or better than established models (Rational Model of Categorization, Context Model, Independent Cue Model, and Hierarchical Dirichlet Process) without requiring the extensive parameter tuning often needed by those models.

4. Results

• Central Tendencies (Hayes-Roth & Hayes-Roth):

  • The model successfully predicted that prototypes (even unseen during training) would have the highest classification accuracy.
  • It correctly ranked items by their distance from the prototype (1-transform items > 2-transform items).
  • It replicated the finding that classification accuracy for 1-transform items was independent of training frequency, while recognition (log-likelihood) increased with frequency.

• Non-Linearly & Linearly Separable Categories (Medin & Schaffer):

  • Experiment 1: The model achieved a Spearman rank correlation of 0.95 with human data, outperforming Anderson's Rational Model of Categorization (RMC) (0.91). It correctly predicted that "exception" items would be harder to classify than prototypes.
  • Experiment 2: The model successfully predicted that Item 7 would be classified more accurately than Item 4, a result that favors the Context Model over the Independent Cue Model. The model's predictions were nearly identical to the Context Model.

• Prototype-Exemplar Transition (Smith & Minda):

  • The model successfully reproduced the phase transition observed in human data.
  • Early Learning: The system behaved like a prototype theorist, misclassifying "exception" items initially because it relied on the dominant category structure.
  • Late Learning: As exposure increased, the system formed distinct concepts for the exceptions, shifting to exemplar-like behavior and correctly classifying them.
  • The authors noted that the smoothing parameter $\alpha$ controls this transition; higher $\alpha$ values (e.g., 2.0) delayed the formation of exception-specific concepts, mimicking the human learning curve.

5. Significance

This paper provides a compelling alternative to existing rational analyses of categorization. By grounding the theory in Information Theory and hierarchical structures, it offers a more flexible framework that naturally explains:

• Why humans generalize to prototypes.
• Why humans can switch to exemplar-based processing for exceptions.
• How categorization performance scales with experience.

The results suggest that human categorization may be driven by a fundamental drive to maximize the information gain provided by category labels, rather than just minimizing prediction error. This approach unifies previously competing theories (prototype vs. exemplar) under a single computational mechanism, offering a promising path toward a unified theory of concept learning.