Compositional Generalization (CG) embodies the ability to comprehend novel
combinations of familiar concepts, representing a significant cognitive leap in
human intellectual advancement. Despite its critical importance, the deep
neural network (DNN) faces challenges in addressing the compositional
generalization problem, prompting considerable research interest. However,
existing theories often rely on task-specific assumptions, constraining the
comprehensive understanding of CG. This study aims to explore compositional
generalization from a task-agnostic perspective, offering a complementary
viewpoint to task-specific analyses. The primary challenge is to define CG
without overly restricting its scope, a feat achieved by identifying its
fundamental characteristics and basing the definition on them. Using this
definition, we seek to answer the question "what does the ultimate solution to
CG look like?" through the following theoretical findings: 1) the first No Free
Lunch theorem in CG, indicating the absence of general solutions; 2) a novel
generalization bound applicable to any CG problem, specifying the conditions
for an effective CG solution; and 3) the introduction of the generative effect
to enhance understanding of CG problems and their solutions. This paper's
significance lies in providing a general theory for CG problems, which, when
combined with prior theorems under task-specific scenarios, can lead to a
comprehensive understanding of CG.

本研究从无任务偏见的视角探索了合成泛化问题，通过理论发现：1）在合成泛化中没有通用解决方案；2）提出了适用于任何合成泛化问题的新型泛化界限，指定了有效合成泛化解决方案的条件；和 3）引入生成效应以增强对合成泛化问题及其解决方案的理解，为合成泛化问题提供了一个普适理论，可以与特定任务场景下的先前定理相结合以全面理解合成泛化。

构成概括的一般理论

A General Theory for Compositional Generalization

Typical architectures of Generative AdversarialNetworks make use of a
unimodal latent distribution transformed by a continuous generator.
Consequently, the modeled distribution always has connected support which is
cumbersome when learning a disconnected set of manifolds. We formalize this
problem by establishing a no free lunch theorem for the disconnected manifold
learning stating an upper bound on the precision of the targeted distribution.
This is done by building on the necessary existence of a low-quality region
where the generator continuously samples data between two disconnected modes.
Finally, we derive a rejection sampling method based on the norm of generators
Jacobian and show its efficiency on several generators including BigGAN.

本研究探讨了生成对抗网络中的潜在分布问题，特别是在学习一个不连续的流形集合时。通过建立不连续流形学习的免费午餐定理，提出了用生成器雅可比的范数导出拒绝抽样方法，在 BigGAN 等生成器上取得了效果优异的结果。

学习非连通流形：无 GAN 领域

Learning disconnected manifolds: a no GANs land

The No Free Lunch theorems are often used to argue that domain specific
knowledge is required to design successful algorithms. We use algorithmic
information theory to argue the case for a universal bias allowing an algorithm
to succeed in all interesting problem domains. Additionally, we give a new
algorithm for off-line classification, inspired by Solomonoff induction, with
good performance on all structured problems under reasonable assumptions. This
includes a proof of the efficacy of the well-known heuristic of randomly
selecting training data in the hope of reducing misclassification rates.

应用算法信息理论证明普适偏好是成功算法的关键，提出以索洛蒙诺夫归纳为灵感的新离线分类算法，证明随机选择训练数据可有效降低误分类率。