On the Complexity of Bayesian Generalization

• URL: http://arxiv.org/abs/2211.11033v2
• Date: Tue, 22 Nov 2022 07:02:30 GMT
• Title: On the Complexity of Bayesian Generalization
• Authors: Yu-Zhe Shi, Manjie Xu, John E. Hopcroft, Kun He, Joshua B. Tenenbaum, Song-Chun Zhu, Ying Nian Wu, Wenjuan Han, Yixin Zhu
• Abstract summary: We consider concept generalization at a large scale in the diverse and natural visual spectrum. We study two modes when the problem space scales up, and the $complexity$ of concepts becomes diverse.
• Score: 141.21610899086392
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• A Complexity-Based Theory of Compositionality [53.025566128892066]
  In AI, compositional representations can enable a powerful form of out-of-distribution generalization. Here, we propose a formal definition of compositionality that accounts for and extends our intuitions about compositionality. The definition is conceptually simple, quantitative, grounded in algorithmic information theory, and applicable to any representation.
  arXiv  Detail & Related papers  (2024-10-18T18:37:27Z)
• Multi-scale structural complexity as a quantitative measure of visual complexity [1.3499500088995464]
  We suggest adopting the multi-scale structural complexity (MSSC) measure, an approach that defines structural complexity of an object as the amount of dissimilarities between distinct scales in its hierarchical organization. We demonstrate that MSSC correlates with subjective complexity on par with other computational complexity measures, while being more intuitive by definition, consistent across categories of images, and easier to compute.
  arXiv  Detail & Related papers  (2024-08-07T20:26:35Z)
• Deep Regression Representation Learning with Topology [57.203857643599875]
  We study how the effectiveness of a regression representation is influenced by its topology. We introduce PH-Reg, a regularizer that matches the intrinsic dimension and topology of the feature space with the target space. Experiments on synthetic and real-world regression tasks demonstrate the benefits of PH-Reg.
  arXiv  Detail & Related papers  (2024-04-22T06:28:41Z)
• Skews in the Phenomenon Space Hinder Generalization in Text-to-Image Generation [59.138470433237615]
  We introduce statistical metrics that quantify both the linguistic and visual skew of a dataset for relational learning. We show that systematically controlled metrics are strongly predictive of generalization performance. This work informs an important direction towards quality-enhancing the data diversity or balance to scaling up the absolute size.
  arXiv  Detail & Related papers  (2024-03-25T03:18:39Z)
• Simplicity in Complexity : Explaining Visual Complexity using Deep Segmentation Models [6.324765782436764]
  We propose to model complexity using segment-based representations of images. We find that complexity is well-explained by a simple linear model with these two features across six diverse image-sets.
  arXiv  Detail & Related papers  (2024-03-05T17:21:31Z)
• Systematic Visual Reasoning through Object-Centric Relational Abstraction [5.914610036560008]
  We introduce OCRA, a model that extracts explicit representations of both objects and abstract relations. It achieves strong systematic generalizations in tasks involving complex visual displays.
  arXiv  Detail & Related papers  (2023-06-04T22:47:17Z)
• Vector-based Representation is the Key: A Study on Disentanglement and Compositional Generalization [77.57425909520167]
  We show that it is possible to achieve both good concept recognition and novel concept composition. We propose a method to reform the scalar-based disentanglement works to be vector-based to increase both capabilities.
  arXiv  Detail & Related papers  (2023-05-29T13:05:15Z)
• Bayes Complexity of Learners vs Overfitting [4.873362301533825]
  We show that a new notion of complexity of functions governs a PAC Bayes-like generalization bound. In contrast to previous works, our notion naturally generalizes to neural networks with several layers. An upper-bound we derive allows to show a separation in the number of samples needed for good generalization between 2 and 4-layer neural networks.
  arXiv  Detail & Related papers  (2023-03-13T13:07:02Z)
• DIFFormer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusion [66.21290235237808]
  We introduce an energy constrained diffusion model which encodes a batch of instances from a dataset into evolutionary states. We provide rigorous theory that implies closed-form optimal estimates for the pairwise diffusion strength among arbitrary instance pairs. Experiments highlight the wide applicability of our model as a general-purpose encoder backbone with superior performance in various tasks.
  arXiv  Detail & Related papers  (2023-01-23T15:18:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.