从学习理论视角揭示生成与预测的内在矛盾
Generation through the lens of learning theory
- 提出统一与非统一生成的新框架，用闭包维数刻画可生成性
- 证明生成性与可预测性互不兼容：有些类可生成但不可预测
- 扩展至提示生成场景，给出完整可提示生成的判定条件
本文从统计学习理论角度研究生成问题。首先，将Gold [1967]、Angluin [1979]、Angluin [1980]和Kleinberg与Mullainathan [2024]的成果形式化为抽象样本空间上的二值假设类。接着，将Kleinberg与Mullainathan [2024]的生成概念拓展至两种新设定：均匀生成与非均匀生成，并给出假设类可均匀生成与非均匀生成的完整刻画。该刻画基于一种新的组合维度——闭包维数（Closure dimension）。在此基础上，我们比较了生成性与可预测性（由PAC学习和在线学习捕捉）的关系，证明两者在某些假设类上互不相容：存在可生成但不可预测的类，也存在可预测但不可生成的类。最后，我们将结果推广至提示生成场景，给出了假设类可提示生成的完全刻画，部分推广了Kleinberg与Mullainathan [2024]的工作。
原文摘要 · Abstract (English)
We study generation through the lens of statistical learning theory. First, we abstract and formalize the results of Gold [1967], Angluin [1979], Angluin [1980] and Kleinberg and Mullainathan [2024] in terms of a binary hypothesis class defined over an abstract example space. Then, we extend the notion of "generation" from Kleinberg and Mullainathan [2024] to two new settings, we call "uniform" and "non-uniform" generation, and provide a characterization of which hypothesis classes are uniformly and non-uniformly generatable. As is standard in learning theory, our characterizations are in terms of the finiteness of a new combinatorial dimension termed the Closure dimension. By doing so, we are able to compare generatability with predictability (captured via PAC and online learnability) and show that these two properties of hypothesis classes are incompatible -- there are classes that are generatable but not predictable and vice versa. Finally, we extend our results to capture prompted generation and give a complete characterization of which classes are prompt generatable, generalizing some of the work by Kleinberg and Mullainathan [2024].
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。