研究噪声数据下生成新正例的理论条件，发现有限噪声不影响生成能力。
Generation from Noisy Examples
- 在噪声正例流中设计生成器，识别并忽略干扰样本
- 有限和可数假设类在噪声下仍可完美生成新正例
- 为噪声环境中的生成模型提供理论边界，适合理论研究者
我们继续研究生成任务的学习理论基础，将 Kleinberg 和 Mullainathan [2024] 以及 Li 等 [2024] 的无噪声结果扩展至包含噪声样本的场景。在无噪声设定中，对手从二元假设类中选择一个假设，并向生成器提供其正例序列，目标是让生成器最终输出未见过的新正例。在噪声设定中，对手同样选择一个假设及其正例序列，但在向生成器发送前插入有限数量的负例。生成器不知哪些是噪声，但仍需最终输出新的、未见过的正例。本文给出了二元假设类在噪声下可生成的充要条件，针对生成所需观察的不同数量的唯一示例。有趣的是，对于有限和可数类，有限噪声的存在几乎不影响生成能力。
原文摘要 · Abstract (English)
We continue to study the learning-theoretic foundations of generation by extending the results from Kleinberg and Mullainathan [2024] and Li et al. [2024] to account for noisy example streams. In the noiseless setting of Kleinberg and Mullainathan [2024] and Li et al. [2024], an adversary picks a hypothesis from a binary hypothesis class and provides a generator with a sequence of its positive examples. The goal of the generator is to eventually output new, unseen positive examples. In the noisy setting, an adversary still picks a hypothesis and a sequence of its positive examples. But, before presenting the stream to the generator, the adversary inserts a finite number of negative examples. Unaware of which examples are noisy, the goal of the generator is to still eventually output new, unseen positive examples. In this paper, we provide necessary and sufficient conditions for when a binary hypothesis class can be noisily generatable. We provide such conditions with respect to various constraints on the number of distinct examples that need to be seen before perfect generation of positive examples. Interestingly, for finite and countable classes we show that generatability is largely unaffected by the presence of a finite number of noisy examples.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。