# On the Complexity of Bayesian Generalization

arXiv: https://arxiv.org/abs/2211.11033 · HTML: https://mlsanity.com/paper/2211.11033/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 86 references that are in the map.
- First posted on arXiv 20 Nov 2022.

## Builds on (most cited first, 25 of 25)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [CLEVR: A Diagnostic Dataset for Compositional Language and Elementary Visual Reasoning](https://mlsanity.com/paper/1612.06890/) (2016)
- [Deep Learning and the Information Bottleneck Principle](https://mlsanity.com/paper/1503.02406/) (2015)
- [Zero-Shot Learning -- A Comprehensive Evaluation of the Good, the Bad and the Ugly](https://mlsanity.com/paper/1707.00600/) (2017)
- [Understanding the Role of Individual Units in a Deep Neural Network](https://mlsanity.com/paper/2009.05041/) (2020)
- [RAVEN: A Dataset for Relational and Analogical Visual rEasoNing](https://mlsanity.com/paper/1903.02741/) (2019)
- [A Theory of Generative ConvNet](https://mlsanity.com/paper/1602.03264/) (2016)
- [DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning](https://mlsanity.com/paper/2006.08381/) (2020)
- [Order-Embeddings of Images and Language](https://mlsanity.com/paper/1511.06361/) (2015)
- [A Benchmark for Systematic Generalization in Grounded Language Understanding](https://mlsanity.com/paper/2003.05161/) (2020)
- [Analogies Explained: Towards Understanding Word Embeddings](https://mlsanity.com/paper/1901.09813/) (2019)
- [Dark, Beyond Deep: A Paradigm Shift to Cognitive AI with Humanlike Common Sense](https://mlsanity.com/paper/2004.09044/) (2020)
- [Learning Perceptual Inference by Contrasting](https://mlsanity.com/paper/1912.00086/) (2019)
- [Abstract Spatial-Temporal Reasoning via Probabilistic Abduction and Execution](https://mlsanity.com/paper/2103.14230/) (2021)
- [ACRE: Abstract Causal REasoning Beyond Covariation](https://mlsanity.com/paper/2103.14232/) (2021)
- [Learning Algebraic Representation for Systematic Generalization in Abstract Reasoning](https://mlsanity.com/paper/2111.12990/) (2021)
- [Emergent Graphical Conventions in a Visual Communication Game](https://mlsanity.com/paper/2111.14210/) (2021)
- [HALMA: Humanlike Abstraction Learning Meets Affordance in Rapid Problem Solving](https://mlsanity.com/paper/2102.11344/) (2021)
- [Neural-Symbolic Recursive Machine for Systematic Generalization](https://mlsanity.com/paper/2210.01603/) (2022)
- [An Overview of Distance and Similarity Functions for Structured Data](https://mlsanity.com/paper/2002.07420/) (2020)
- [A Tale of Three Probabilistic Families: Discriminative, Descriptive and Generative Models](https://mlsanity.com/paper/1810.04261/) (2018)
- [Representation Learning: A Statistical Perspective](https://mlsanity.com/paper/1911.11374/) (2019)
- [A Minimalist Dataset for Systematic Generalization of Perception, Syntax, and Semantics](https://mlsanity.com/paper/2103.01403/) (2021)

## Built on by (most cited first, 3 of 3)

- [Hierarchically Encapsulated Representation for Protocol Design in Self-Driving Labs](https://mlsanity.com/paper/2504.03810/) (2025)
- [Targeted control of fast prototyping through domain-specific interface](https://mlsanity.com/paper/2506.11070/) (2025)
- [Automated Constraint Specification for Job Scheduling by Regulating Generative Model with Domain-Specific Representation](https://mlsanity.com/paper/2510.02679/) (2025)

## Abstract (arXiv)

We consider concept generalization at a large scale in the diverse and natural visual spectrum. Established computational modes (i.e., rule-based or similarity-based) are primarily studied isolated and focus on confined and abstract problem spaces. In this work, we study these two modes when the problem space scales up, and the complexity of concepts becomes diverse. Specifically, at the representational  level, we seek to answer how the complexity varies when a visual concept is mapped to the representation space. Prior psychology literature has shown that two types of complexities (i.e., subjective complexity and visual complexity) (Griffiths and Tenenbaum, 2003) build an inverted-U relation (Donderi, 2006; Sun and Firestone, 2021). Leveraging Representativeness of Attribute (RoA), we computationally confirm the following observation: Models use attributes with high RoA to describe visual concepts, and the description length falls in an inverted-U relation with the increment in visual complexity. At the computational  level, we aim to answer how the complexity of representation affects the shift between the rule- and similarity-based generalization. We hypothesize that category-conditioned visual modeling estimates the co-occurrence frequency between visual and categorical attributes, thus potentially serving as the prior for the natural visual world. Experimental results show that representations with relatively high subjective complexity outperform those with relatively low subjective complexity in the rule-based generalization, while the trend is the opposite in the similarity-based generalization.