层次化领域泛化

# 层次化域泛化 来源：https://arxiv.org/html/2607.16528 Chenxiao Yang1，Zhiyuan Li1，Shai Ben\-David2，Nathan Srebro1 1芝加哥丰田技术研究所 2滑铁卢大学 \{chenxiao,zhiyuanli,nati\}@ttic\.edu，shai@uwaterloo\.ca ###### 摘要 我们将层次化域泛化研究为从有限观测区域到整个实例空间的外推问题，用任意域层次结构替代独立同分布采样。我们表明，核心障碍不仅在于假设类的复杂度，还在于证据揭示所依据的训练/测试域划分。特别地，无论假设类多么小，或者训练规模多么大，总存在某种划分使得泛化对某些目标失效。这些结果表明，现代泛化理论必须将域结构视为一类对象。 ## 1引言 机器学习中的泛化概念深受Vapnik和Chervonenkis关于统计泛化理论的开创性工作(Vapnik and Chervonenkis,1971 (https://arxiv.org/html/2607.16528#bib.bib231))以及Valiant引入的二分类PAC模型(Valiant,1984 (https://arxiv.org/html/2607.16528#bib.bib205))的影响。在这些设定中，训练数据从某个未知的数据分布D\\mathcal\{D\}中独立同分布地抽取，学习器的输出在*相同*的D\\mathcal\{D\}上进行评估。一个成功的学习器需要在生成训练数据的分布（或在最近的域适应学习工作中相关的数据分布，例如Ben\-David等 (2006 (https://arxiv.org/html/2607.16528#bib.bib1))）上实现较低的期望误差。这一统计框架塑造了该领域四十年来对“泛化意味着什么”的理解。 相比之下，大语言模型时代要求一种经典框架未能捕捉的泛化：在非常大且固定的输入域（例如网络）上训练后，学习器应能推理——恢复底层规则——并在其训练域之外的相关输入上产生正确的输出。然而，一个在五位数加法上训练的模型可能完美拟合其训练数据，却在六位数上失败，这在实际中经常发生(Anil等,2022 (https://arxiv.org/html/2607.16528#bib.bib226); Lee等,2024 (https://arxiv.org/html/2607.16528#bib.bib227))。在这种情况下，它匹配了数据中的一种模式，而不是能够对任意长度数进行加法的规则。它未能*推理*。经典理论所谓的泛化，在多数科学家和哲学家使用这个词的意义上，实际上是插值（受某些先验知识的偏置或调节）。这越来越不足以捕捉许多实际感兴趣的学习任务。 推理要求外推，即域外泛化：从一种输入到另一种与训练数据共享某种受控（确定性）相似性的输入。我们将这种泛化形式形式化为沿着域层次结构进行精确识别。我们不再测量数据生成分布下的期望误差，而是要求学习器在整个实例空间Ω\\Omega上恢复目标函数。我们不再假设独立同分布观测模型，而是让可观测区域通过一个外部指定的层次结构X ̄=\(Xn\)n≥0\\bar\{\\mathcal\{X\}\}=\(\\mathcal\{X\}\_\{n\}\)\_\{n\\geq 0\}（有限累积域）增长，满足∅=X0⊊X1⊊X2⊊⋯\\emptyset=\\mathcal\{X\}\_\{0\}\\subsetneq\\mathcal\{X\}\_\{1\}\\subsetneq\\mathcal\{X\}\_\{2\}\\subsetneq\\cdots且⋃n≥1Xn=Ω\\bigcup\_\{n\\geq 1\}\\mathcal\{X\}\_\{n\}=\\Omega（因此Ω\\Omega是可数的）。在层次nn处，学习器观察到带标签的训练集\{\(x,f\(x\)\):x∈Xn\}\\\{\(x,f\(x\)\):x\\in\\mathcal\{X\}\_\{n\}\\\}，并在整个Ω\\Omega上进行评估；等价地，它必须从观测区域Xn\\mathcal\{X\}\_\{n\}外推到未观测的补集Ω∖Xn\\Omega\\setminus\\mathcal\{X\}\_\{n\}。实现这一目标的唯一方法是精确*识别*出ff。这捕捉了现代推理系统的一个常见目标：在较短输入上训练并泛化到较长输入(Anil等,2022 (https://arxiv.org/html/2607.16528#bib.bib226); Lee等,2024 (https://arxiv.org/html/2607.16528#bib.bib227); Zhou等,2024 (https://arxiv.org/html/2607.16528#bib.bib85))（又称长度泛化），在简单实例上训练并泛化到较难实例(Bengio等,2009 (https://arxiv.org/html/2607.16528#bib.bib237))，以及在有限视野任务上训练并泛化到更长视野任务(Abbe等,2023 (https://arxiv.org/html/2607.16528#bib.bib233); Yang等,2026b (https://arxiv.org/html/2607.16528#bib.bib186))。在逐点情况下，每个增量是单点集Xn∖Xn−1=\{xn\}\\mathcal\{X\}\_\{n\}\\setminus\\mathcal\{X\}\_\{n\-1\}=\\\{x\_\{n\}\\\}，因此Xn=\{x1,...,xn\}\\mathcal\{X\}\_\{n\}=\\\{x\_\{1\},\\ldots,x\_\{n\}\\\}，该模型恢复了Gold的极限识别范式中的呈现模型(Gold,1967 (https://arxiv.org/html/2607.16528#bib.bib219))。 核心问题是：给定一个层次结构X ̄\\bar\{\\mathcal\{X\}\}，学习器需要观测多少个层次NN才能在整个域Ω\\Omega上恢复目标f∈Hf\\in\\mathcal\{H\}？这个问题可以有不同强度的答案：所需的层次可能依赖于目标和层次结构两者，可能在层次结构固定后对所有目标是共同的，或者可能需要同时对目标和层次结构一致工作。答案取决于层次选择的统一程度。如果层次可以同时依赖于目标和层次结构，则H\\mathcal\{H\}的可数性正是充分必要条件。如果层次结构固定但同一层次必须适用于所有目标，则阈值变成H\\mathcal\{H\}的有限性。但如果层次必须相对于层次结构本身一致选择，情况就完全改变了：对于任何非平凡的假设类，这种保证只有在有限域情况下才可能（定理1 (https://arxiv.org/html/2607.16528#Thmtheorem1)、5 (https://arxiv.org/html/2607.16528#Thmtheorem5)和8 (https://arxiv.org/html/2607.16528#Thmtheorem8)）。 长度泛化给出了这个问题的具体固定层次实例。层次结构是字符串长度：在所有长度不超过NN的字符串上训练，并在更长的字符串上测试，询问这个观测到的前缀是否决定了目标规则。由于相关的类（如有有限编码的Transformer家族）是无限的，我们按复杂度对其进行分层：对于每个界ss，我们询问需要多少长度来识别复杂度不超过ss的每个目标。现有的非渐近长度泛化结果针对特定的表示类和复杂度尺度估计了这种子水平域复杂度(Chen等,2025 (https://arxiv.org/html/2607.16528#bib.bib114); Yang等,2026a (https://arxiv.org/html/2607.16528#bib.bib115))；定性和近似变体也符合相同的固定层次图景(Huang等,2025 (https://arxiv.org/html/2607.16528#bib.bib113); Izzo等,2026 (https://arxiv.org/html/2607.16528#bib.bib116))。对于一个固定层次结构，这类界有明确的解释：它们说明在目标被确定之前，必须沿着该层次结构训练多远。但这仍然未解答这个界反映的是模型类本身的属性，还是仅反映用于训练和测试的特定层次结构的属性。我们的无免费午餐结果表明，后一种依赖性是不可避免的。即使假设类和复杂度尺度固定，另一个层次结构也可能使有限切片界任意快地增长（定理12 (https://arxiv.org/html/2607.16528#Thmtheorem12)和6 (https://arxiv.org/html/2607.16528#S6.SS0.SSS0.Px2)）。因此，长度泛化界是关于长度层次结构的界，而不是对于任意域偏移的免层次结构保证。经典的“无免费午餐”定理警告，无限制的假设类不存在一致的学习保证(Shalev\-Shwartz and Ben\-David,2014 (https://arxiv.org/html/2607.16528#bib.bib9))。这里的障碍来自于经典理论中隐藏的第二个对象：决定什么先被观测到的层次结构。因此，域泛化保证是配对\(H,X ̄\)\(\\mathcal\{H\},\\bar\{\\mathcal\{X\}\}\)的性质，而不仅仅是H\\mathcal\{H\}的性质。 我们进一步扩展该框架，并将其与几种邻近的学习设置联系起来，包括在线学习和极限生成(Kleinberg and Mullainathan,2024 (https://arxiv.org/html/2607.16528#bib.bib220))。在线学习计数错误而不是识别层次，而极限生成要求比精确恢复更弱的输出。此外，允许误差，或用分布式的训练/测试采样替代层次结构，本身并不能消除困难：保证仍然需要关于观测区域与学习器评估区域之间结构关系的假设。然而，一旦我们将数据模型改为仅正例呈现，一致识别可以对无限类成立，并受正例区域之间重叠程度的控制。 组织结构。本文其余部分组织如下。第2节 (https://arxiv.org/html/2607.16528#S2)和3节 (https://arxiv.org/html/2607.16528#S3)引入基于层次结构的学习模型和主要的特征刻画定理。第4节 (https://arxiv.org/html/2607.16528#S4)和5节 (https://arxiv.org/html/2607.16528#S5)发展固定层次结构的定量视角，以长度泛化为核心示例。第6节 (https://arxiv.org/html/2607.16528#S6)展示为什么这些界不能独立于层次结构。第7节 (https://arxiv.org/html/2607.16528#S7)讨论向相关学习设置的扩展。 ## 2层次化域泛化 ### 2.1 设定 令Ω\\Omega为可数无限实例空间，令H⊆\{0,1\}Ω\\mathcal\{H\}\\subseteq\\\{0,1\\\}^\{\\Omega\}为二值假设类。¹¹有限域仅用作退化的比较情况，约定层次结构对于所有足够大的nn塌缩为Xn=Ω\\mathcal\{X\}\_\{n\}=\\Omega。二值取值范围仅为具体说明用；所有特征刻画可推广到任何有限标签空间。我们在可实现确定性标注设定下工作：未知目标f∈Hf\\in\\mathcal\{H\}为每个x∈Ωx\\in\\Omega生成标签f\(x\)∈\{0,1\}f\(x\)\\in\\\{0,1\\\}。对于任何子集X⊆Ω\\mathcal\{X\}\\subseteq\\Omega，记f\|Xf\|\_\{\\mathcal\{X\}\}为带标签的训练集\{\(x,f\(x\)\):x∈X\}\\\{\(x,f\(x\)\):x\\in\\mathcal\{X\}\\\}。为了建模域外泛化，我们必须指定Ω\\Omega的可观测部分如何增长。基本对象不是采样分布，而是一个预先确定的有限累积域序列，其标签对学习器可用。 ###### 定义1（域层次结构）。Ω\\Omega上的一个*层次结构*是一个由有限累积观测区域构成的 telescopic exhaustion X ̄=\(Xn\)n≥0\\bar\{\\mathcal\{X\}\}=\(\\mathcal\{X\}\_\{n\}\)\_\{n\\geq 0\}，满足 ∅=X0⊊X1⊊X2⊊⋯，\|Xn\|<∞对每个n，⋃n≥1Xn=Ω。\\emptyset=\\mathcal\{X\}\_\{0\}\\;\\subsetneq\\;\\mathcal\{X\}\_\{1\}\\;\\subsetneq\\;\\mathcal\{X\}\_\{2\}\\;\\subsetneq\\;\\cdots，\qquad\|\\mathcal\{X\}\_\{n\}\|<\\infty\\text\{ 对每个 \}n，\qquad\\bigcup\\nolimits\_\{n\\geq 1\}\\mathcal\{X\}\_\{n\}=\\Omega。\(1\) 对于n≥1n\\geq 1，记Δn:=Xn∖Xn−1\\Delta\_\{n\}:=\\mathcal\{X\}\_\{n\}\\setminus\\mathcal\{X\}\_\{n\-1\}为第nn层新揭示的增量。该定义有意对区域的排序方式保持开放态度。一个常见来源是外部指定的域序列，例如不同群体、人口统计子组、或基于干预的环境。另一个来源是根据输入的固有属性（如长度或难度）对Ω\\Omega进行排序，将较简单的输入放在较前的层次，较难的放在后面，如长度泛化和课程学习。当每个增量是单点集时，例如Δn=\{xn\}\\Delta\_\{n\}=\\\{x\_\{n\}\\\}，等价于Xn=\{x1,...,xn\}\\mathcal\{X\}\_\{n\}=\\\{x\_\{1\},\\ldots,x\_\{n\}\\\}，该层次结构恢复了Gold的极限识别设定(Gold,1967 (https://arxiv.org/html/2607.16528#bib.bib219))。 #### 层次化域泛化。一旦层次结构固定，第nn层将Ω\\Omega分割为观测区域Xn\\mathcal\{X\}\_\{n\}（学习器从中接收带标签的训练集f\|Xnf\|\_\{\\mathcal\{X\}\_\{n\}\}）和未观测的补集Ω∖Xn\\Omega\\setminus\\mathcal\{X\}\_\{n\}，后者相对于该层是域外的。学习器在整个Ω\\Omega上进行评估，因此成功需要从观测区域外推到层次结构中未见的部分。这种域内/域外划分仅由X ̄\\bar\{\\mathcal\{X\}\}决定，无需任何分布假设。我们将每个观测层次理想化为完全标注：在第nn层，学习器可以访问Xn\\mathcal\{X\}\_\{n\}上的所有标签。因此问题不在于学习器能否拟合观测区域，而在于该区域是否已经决定了其外的目标。 ###### 定义2（学习器）。学习算法是一个映射A:⋃X⊆Ω，\|X\|<∞\{0,1\}X→\{0,1\}ΩA:\\bigcup\_\{\\mathcal\{X\}\\subseteq\\Omega，\\ \|\\mathcal\{X\}\|<\\infty\}\\\{0,1\\\}^\{\\mathcal\{X\}\}\\to\\\{0,1\\\}^\{\\Omega\}，它以带标签的训练集f\|Xf\|\_\{\\mathcal\{X\}\}作为输入，并返回一个二值预测器A\(f\|X\)A\(f\|\_\{\\mathcal\{X\}\}\)。学习器可以在了解假设类H\\mathcal\{H\}的情况下选择。由于训练集由集合而非有序序列索引，AA看不到样本点被揭示的顺序——这与在线学习不同，在线学习中层内顺序本身可以携带信息。 ###### 定义3（域复杂度）。给定学习器AA，目标f∈Hf\\in\\mathcal\{H\}和层次结构X ̄\\bar\{\\mathcal\{X\}\}，AA关于ff沿X ̄\\bar\{\\mathcal\{X\}\}的*域复杂度*为 NAX ̄\(f\):=min⁡\{i∈N≥1:∀n≥i，A\(f\|Xn\)=f\}，N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\):=\\min\\big\\\{i\\in\\mathbb\{N\}\_\{\\geq 1\}:\\forall n\\geq i，\\;A\(f\|\_\{\\mathcal\{X\}\_\{n\}\}\)=f\\big\\\}，\(2\)如果不存在这样的有限ii，则值为∞\\infty。因此，NAX ̄\(f\)N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)是第一个这样的层次：对于所有n≥NAX ̄\(f\)n\\geq N\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)，在观测区域Xn\\mathcal\{X\}\_\{n\}上训练能够产生在整个Ω\\Omega上正确的假设，等价地，在层次结构中所有后续当前未观测的部分上正确。 ### 2.2 学习目标的层次 我们根据学习器、目标、层次结构和识别层次上量词的作用顺序来区分层次化域泛化的可能形式。前两个标准依赖于层次结构：在A1中，识别层次可以同时依赖于目标和层次结构；在A2中，它仍然可以依赖于层次结构，但必须对类中的所有目标是共同的。 ###### 定义4（A1：*非一致可识别性*）。如果存在一个学习算法AA满足以下性质：对于每个目标f∈Hf\\in\\mathcal\{H\}和每个层次结构X ̄\\bar\{\\mathcal\{X\}\}，存在一个有限NN使得NAX ̄\(f\)≤NN\_\{A\}^\{\\bar\{\\mathcal\{X\}\}\}\(f\)\\leq N，则称H\\mathcal\{H\}是*非一致可识别的*（A1）。 A2保留对层次结构的依赖性，但要求一个层次适用于所有目标。 ###### 定义5（A2：*目标一致可识别性*）。如果存在一个学习算法AA满足以下性质：对于每个层次结构X ̄\\bar\{\\mathcal\{X\}\}，存在一个有限NN使得