Cobweb: Concept Formation as Information Gain

1Introduction

Categorization lets a learner predict what it cannot observe. A child who files an animal under dog expects it to bark before it has barked. A theory of categorization must therefore explain two processes: how a learner forms categories from experience, and how it uses them to infer missing features.

Anderson (1991) answered both questions with a rational analysis. His model assumes that the environment divides into a flat set of categories, and it assigns each instance to the category most likely to have generated it. MacLellan et al. (2026) revise two of his assumptions. First, they adopt Corter and Gluck's (1992) hypothesis that a category is useful to the extent that it improves feature prediction, so a learner should form the categories that share the most information with the features of its experiences. Second, they assume that the environment is taxonomic rather than flat (Fisher & Langley, 1990). Fisher's (1987) Cobweb already embodies both commitments, and the authors instantiate the theory as a variant of it.

2Representation

Cobweb describes each instance as a set of attribute-value pairs, such as {shape: circle, color: red, size: small}. A concept summarizes the instances beneath it with one categorical distribution per attribute. It stores only counts: the number of instances it covers, \(n(C)\), and the number of those that take each value, \(n(C, a{=}v)\). It estimates probabilities with a uniform pseudocount \(\alpha\), the theory's single free parameter:

where \(|V_a|\) is the number of values of attribute \(a\) observed so far. The concepts form a tree. The root covers every instance, each leaf covers instances that agree on every attribute, and intermediate concepts form progressively more specific abstractions. Leaves therefore behave like stored exemplars, and intermediate concepts behave like prototypes; the theory needs no separate mechanism for either.

Figure 1 shows a hierarchy over eleven shapes. Select any concept to inspect its distributions.

3Learning

3.1The objective

Cobweb scores a partition of a parent concept \(P\) into children \(C_1, \dots, C_K\) by how much knowing the child reduces uncertainty about an instance's features:

where \(H(C)\) is the entropy of a concept's feature distributions, summed over attributes:

Because Cobweb treats attributes as independent within a concept, the bracketed term is the sum, over attributes, of the mutual information between each attribute and child membership. MacLellan et al. (2026) describe the operator choice as maximizing this quantity, the expected pointwise mutual information between concepts and instances. The reference implementation divides it by \(K\), as Fisher's original category utility does, so a partition cannot buy information by fragmenting into singletons.¹

3.2The four operators

Cobweb incorporates an instance by descending from the root. At each concept with children, it ranks the children by how well each accommodates the instance and evaluates four ways to restructure the partition:

1. insert adds the instance to the best child and descends into it;
2. create adds a new singleton child for the instance and stops;
3. merge joins the two best children under a new concept, adds the instance to it, and descends into it;
4. split removes the best child, promotes its children to the current level, and evaluates the level again.

Cobweb applies the operator whose resulting partition scores highest under Eq. 2. Insert and create build the hierarchy; merge and split repair it. The repair operators let later instances undo commitments that earlier, unrepresentative instances forced, which makes the hierarchy less sensitive to presentation order than a purely additive learner would be. Two boundary cases complete the procedure: an instance identical to a leaf increments that leaf, and an instance that reaches a different leaf turns that leaf into a concept with two children, the old leaf and the new instance.

Figure 2 steps through one decision for each operator.

4Prediction

Cobweb predicts a missing attribute by sorting the partial instance \(x\) through the hierarchy. The variant of MacLellan et al. (2026) replaces Fisher's single greedy descent with a best-first search that expands concepts in order of their pointwise mutual information with the instance:

Since \(p(x)\) is the same for every concept, the search ranks concepts by \(\log p(x \mid C)\), which is the sum of Eq. 1 over the observed attributes in log space. It expands at most max_nodes concepts (100 in every simulation of the paper) and predicts with a mixture of the expanded concepts' distributions, weighted by their normalized scores. A small budget commits the prediction to the first concepts the search reaches; a larger budget lets more specific concepts, down to the exemplars at the leaves, enter the mixture in proportion to how well they explain the instance.

5Psychological evidence

MacLellan et al. (2026) evaluate the theory against three classic studies. In every simulation, the category label enters training as one more attribute and is absent at test, so classification is simply the prediction of that attribute under Section 4. The simulations use the same number of participants as the original studies, max_nodes = 100, and one value of \(\alpha\) per study.

5.1Central tendency and frequency (Hayes-Roth & Hayes-Roth, 1977)

Participants classified 132 descriptions of fictional people into Club 1, Club 2, or Neither. Three attributes (age, education, and marital status) took four values each and determined membership; a last name and a hobby served as distractors. Two prototypes, coded 111 and 222, defined the clubs but never appeared in training. Training items differed from a prototype by one or two features, and the design crossed this distance with frequency: some one-feature transforms appeared ten times and others once. At test, participants rated 28 items for recognition and for club membership.

The data dissociate the two tasks. The unseen prototypes drew the most confident classifications, and confidence fell with distance from the prototype whatever the frequency. Recognition instead tracked frequency: items seen ten times felt more familiar than items seen once, and more familiar than the prototypes.

Cobweb reproduces both patterns. MacLellan et al. (2026) trained 54 simulated participants with \(\alpha = 1\) and modeled recognition as the weighted log-likelihood of each test item over the expanded concepts. Model and human rankings of the item types correlate at Spearman \(\rho = 0.96\) for classification and \(\rho = 0.95\) for recognition. The hierarchy explains the dissociation. Frequent items build heavily weighted leaves, which raise the likelihood that drives recognition. Classification, however, draws on intermediate concepts whose label distributions pool the whole cluster, and the prototype matches the cluster's members better than any single member does. The one discrepancy concerns the Club 2 prototype, which the model finds less familiar than participants did; the authors note that the human recognition scores pool a condition in which participants saw the prototypes in advance.

5.2Exemplar similarity over prototype distance (Medin & Schaffer, 1978)

Medin and Schaffer (1978) designed their experiments to separate two accounts of classification. Independent cue models, prototype models among them, add up independently weighted features, so an item's standing depends on its distance from the category's central tendency. Their context model instead compares an item to stored exemplars multiplicatively, so an item that closely resembles several members of one category and none of the other wins even when it lies farther from the prototype.

Experiment 2 used geometric forms that varied in form, size, color, and position, each binary. Items 4 (1110) and 7 (1010) set the accounts against each other. Under any weighting of the features, item 4 lies at least as close as item 7 to the Category A prototype 1111, so independent cue models favor item 4. Item 7, however, differs by one feature from two A exemplars and from no B exemplar, whereas item 4 differs by one feature from one A exemplar and two B exemplars. Participants classified item 7 more accurately (0.88 against 0.78), as the context model predicts. They also classified the never-studied prototype better than any studied A item (0.94).

Cobweb predicts both effects without a separate exemplar store: its leaves are the exemplars, and its search weights them by likelihood. With \(\alpha = 0.1\), it reaches the training criterion in two runs on average and orders all 16 items like participants do at \(\rho = 0.96\), equal to the context model. In Experiment 1, it reproduces all four main effects and fits better than Anderson's rational model (\(\rho = 0.95\) against 0.91).

5.3The prototype-to-exemplar transition (Smith & Minda, 1998)

Smith and Minda (1998) argued that learners move from prototype to exemplar representations as learning proceeds. In their Experiment 2, participants learned 14 six-letter nonsense words in two categories that no linear boundary separates. Each category had a prototype (000000 or 111111), five standard items one feature from it, and one exception that shares a single feature with its own prototype and five with the other. Participants trained for 40 blocks, grouped into ten segments. They classified prototypes and standard items correctly from the start but misclassified the exceptions through the first three segments; accuracy on the exceptions began to rise near segment 4 and passed chance about halfway through training.

Cobweb shows the same transition, and its tree exposes the mechanism. Early in training, the prior \(\alpha\) dominates small concepts, so each exception folds into the large concept of the prototype it resembles, and the model behaves like a prototype learner. As exposures accumulate, the evidence for each exception overpowers the prior, Cobweb forms a distinct concept for it, and classification follows the exemplar. The value of \(\alpha\) sets the timing. Below about 0.6, Cobweb classifies the exceptions correctly from the first segment; at \(\alpha = 1\), it improves gradually, much like the hierarchical Dirichlet process of Griffiths et al. (2007); at \(\alpha = 2\), the value used in the paper, it shows a phase change with no early improvement.

6Discussion

The simulations support a compact claim: a learner that greedily maximizes the information its concepts carry, within a taxonomy, reproduces effects that earlier accounts explained with separate mechanisms. Prototype effects arise from intermediate concepts, exemplar effects from leaves, frequency effects from counts, and the transition between regimes from the competition between the prior and accumulating evidence. The theory achieves this with one free parameter, where the context model fits an attention weight to every dimension.

The evaluation has limits that the authors acknowledge. Only aggregate human data were available, so every fit compares averaged scores. The value of \(\alpha\) differed across studies (1, 0.1, and 2), each chosen from a few candidates. The Smith and Minda account is qualitative. Ablations that test the taxonomic and information-theoretic assumptions separately, and experiments where the theory's predictions diverge from its competitors', remain future work.

7Applications

The same operators extend to continuous attributes. Cobweb/4V (Barari et al., 2024) replaces each categorical distribution with a diagonal Gaussian and measures uncertainty by differential entropy, \(U(C) = \tfrac{1}{2}\sum_{d} \log(2\pi e\, \sigma^2_{C,d})\), so a good partition is one that reduces variance. Two recent papers apply this variant to sentence embeddings from pretrained transformers.

7.1Hierarchical semantic retrieval

Dense retrieval ranks documents by the dot product between their embeddings and a query's. Gupta, Singaravadivelan, and Wang (2025) instead insert document embeddings into a Cobweb/4V tree and rank its leaves by a coarse-to-fine traversal. Cobweb-BFS runs best-first search from the root and ranks leaves in the order it reaches them; Cobweb-PathSum scores each leaf by the summed log scores of the concepts on its path from the root. Neither method fixes a number of clusters, and both expose intermediate prototypes that summarize the documents beneath them.

Diagonal Gaussians assume independent dimensions, which contrastively trained embeddings violate. The authors therefore whiten embeddings with PCA and ICA before insertion, and this step proves decisive (Table 1). With whitening, Cobweb matches exact dot-product search on RoBERTa and T5 embeddings. On anisotropic GPT-2 embeddings, where dot product nearly fails, Cobweb retrieves substantially better. PathSum runs 20 to 100 times faster than BFS, although both remain far slower than FAISS.

7.2Lifelong hierarchical topic modeling

Topic models typically fix the number of topics in advance and train in batch, and their incremental variants either keep that number fixed or forget earlier structure. CobwebTM (Singaravadivelan, Gupta, Wang, & MacLellan, 2026) inserts each incoming document embedding into a Cobweb/4V tree and labels every concept with the c-TF-IDF words of the documents beneath it. The root covers the corpus, intermediate concepts form increasingly specific topics, and the tree grows wherever new documents demand it. Each insertion adjusts only the concepts along one path, so earlier topics persist: the model has no fixed topic capacity and does not forget catastrophically. Figure 7 sketches this behavior on a stream of news.

On three streaming corpora, CobwebTM attains the highest final coherence of every incremental method and near-perfect agreement between the topic assignments of consecutive batches (Table 2). When the evaluation withholds an entire category and then streams it in, CobwebTM creates a topic for it, as the batch re-fit baselines do, while the other incremental methods fail. On hierarchical benchmarks, it attains the highest NPMI on 20 Newsgroups, AG News, and Stack Exchange. Its limitations mirror its design: topic words come from post hoc aggregation rather than from the tree itself, quality depends on the encoder, and results depend on the order in which documents arrive.

Both applications rely on the properties that make Cobweb a plausible account of human learning. It learns incrementally, it determines the breadth and depth of its hierarchy from the data rather than from a fixed parameter, and every concept it forms remains inspectable as a prototype of the instances beneath it.

References

1. Anderson, J. R. (1991). The adaptive nature of human categorization. Psychological Review, 98(3), 409–429.
2. Barari, N., Lian, X., & MacLellan, C. J. (2024). Incremental concept formation over visual images without catastrophic forgetting. Advances in Cognitive Systems.
3. Corter, J. E., & Gluck, M. A. (1992). Explaining basic categories: Feature predictability and information. Psychological Bulletin, 111(2), 291–303.
4. Fisher, D. H. (1987). Knowledge acquisition via incremental conceptual clustering. Machine Learning, 2(2), 139–172.
5. Fisher, D. H., & Langley, P. (1990). The structure and formation of natural categories. Psychology of Learning and Motivation, 26, 241–284.
6. Griffiths, T. L., Canini, K. R., Sanborn, A. N., & Navarro, D. J. (2007). Unifying rational models of categorization via the hierarchical Dirichlet process. Proceedings of the Annual Meeting of the Cognitive Science Society.
7. Gupta, A., Singaravadivelan, K., & Wang, Z. (2025). Hierarchical semantic retrieval with Cobweb. Advances in Cognitive Systems, 12. arXiv:2510.02539.
8. Hayes-Roth, B., & Hayes-Roth, F. (1977). Concept learning and the recognition and classification of exemplars. Journal of Verbal Learning and Verbal Behavior, 16(3), 321–338.
9. MacLellan, C. J., Singaravadivelan, K., Lian, X., Wang, Z., & Langley, P. (2026). A rational account of categorization based on information theory. Proceedings of the Annual Meeting of the Cognitive Science Society. arXiv:2603.29895.
10. Medin, D. L., & Schaffer, M. M. (1978). Context theory of classification learning. Psychological Review, 85(3), 207–238.
11. Singaravadivelan, K., Gupta, A., Wang, Z., & MacLellan, C. J. (2026). CobwebTM: Probabilistic concept formation for lifelong and hierarchical topic modeling. In Findings of the Association for Computational Linguistics: ACL 2026 (pp. 35140–35155). ACL Anthology.
12. Smith, J. D., & Minda, J. P. (1998). Prototypes in the mist: The early epochs of category learning. Journal of Experimental Psychology: Learning, Memory, and Cognition, 24(6), 1411–1436.

Code: Teachable-AI-Lab/cobweb (the algorithm) and Teachable-AI-Lab/cobweb-psych (the experiments).