On the Complexity of Bayesian Generalization

Yu-Zhe Shi*, Manjie Xu*, John E. Hopcroft, Kun He, Joshua B. Tenenbaum,

Song-Chun Zhu, Ying Nian Wu, Wenjuan Han, Yixin Zhu

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.

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.

Quantitative results of Representation vs. Complexity.

A landscape of similarity- and rule-based generalization over concepts with relatively high and low subjective complexity, considering both concept complexities and concept hierarchy. Bidirectional arrows denote the similarity judgment between concepts, wherein concepts linked by solid lines are more similar than those linked by dashed lines. Arrows denote rules over concepts. Rule-based generalization in basic-level generalizes given rules to unknown rules. Similarity shifts to rules when the sample hierarchy goes from superordinate-level to subordinate-level (e.g., from block to blue cylinder, from cat to angora cat). Rules shift to similarity as the sample hierarchy goes from subordinate-level to superordinate-level (e.g., from car on the road to car, from dalmatian to spot). We further notice a confusing similarity judgment between blue cylinder, blue cube, and green cylinder with distinct and shared attributes.

More clear Images and more details, please refer to our paper.