Criticality in Dissimilar Decomposition and Undersampling of Random Datasets with Anomalies

技术摘要：异质分解与含有异常值的随机数据集欠采样的临界性

问题陈述
本文探讨了对包含与主要数据点深度关联的“异常值”的随机数据集进行分解和欠采样的挑战。这一场景的动机在于，当前大型语言模型（LLM）的训练数据集正日益普遍地包含大量的 AI 生成文本或图像数据。这些 AI 生成的样本被视为异常值，因为它们通过其来源（例如，由训练在相似数据上的前代 LLM 生成）与真实数据点相“关联”，而非独立的。核心问题在于理解这些关联型异常值如何影响“强不相似”（Strongly Dissimilar, SD）批次分解的最小规模，以及维持强不相似性所需的随机欠采样数据集的临界规模。

方法论
作者采用了一种结合图论和随机变量分析的概率框架：

• 建模： 将数据集建模为由 $n$ 个独立数据点组成的集合，其中 $n-v_0$ 个为“主要”点（服从分布 $p$ 的独立同分布数据），$v_0$ 个为“异常”点（具有不同的分布）。
• 定义：
  • 相似性： 通过函数 $\rho(x, y)$ 定义（例如特征一致性）。若 $\rho \le \lambda$，则两点为 $\lambda$-不相似。
  • 关联性（Linkage）： 使用二项随机图进行建模，其中边代表基于来源索引的两个数据点之间的“关联”，该关联与它们的实际数值无关。
  • 强不相似性 (SD)： 若两点既是 $\lambda$-不相似，且在关联图中不存在边（即未连接），则称其为 SD。
• 图构建： 构建一个“相似性图” $\Gamma$，若两个顶点对应的两个数据点是“强相似”的（即既相似又有关联），则存在一条边。
• 分析工具：
  • 分解： 利用与相似性图的最大顶点度 ($\Delta$) 和最大平均度 ($h_{av}$) 相关的界限来分析 SD 分解的最小规模 ($\tau_{SD}$)。论文利用了迭代稳定集提取技术。
  • 欠采样： 使用一阶和二阶矩方法（期望和方差估计）研究随机欠采样数据集（RUS）的性质，以确定采样子集不包含相似性图中边的概率。
  • 集中不等式： 使用 Chernoff 型界限和切比雪夫不等式来建立关于边存在性和稳定集规模的高概率结果。

主要贡献与结果

1. 分解规模中的相变（定理 1）：
   论文确立了关于随着异常值数量 ($v_0$) 变化，最小强不相似分解规模 ($\tau_{SD}$) 的相变现象：

• 低异常值区间： 当 $v_0$ 较小时（具体为 $v_0 = o(v_{low})$），最小分解规模主要由“主要”数据点决定。其规模大约随 $n \zeta_{low} q_{low} / \log n$ 缩放。
• 高异常值区间： 当 $v_0$ 超过某一阈值时（即使 $v_0 \ll n$），最小规模将关键性地取决于异常值。在此区间内，规模随 $v_0 p_{low} s_{low} / \log n$ 缩放。
  这表明，少量高度关联的异常值可以主导数据集分解的结构特性。

2. 随机欠采样的临界规模（定理 2）：
   论文确定了随机欠采样数据集保持强不相似性的高概率临界样本量 $t$：

• 亚临界区间： 如果样本量 $t$ 足够小（$t = o(t_{low})$），欠采样数据集以趋近于 1 的概率保持强不相似。
• 超临界区间： 如果 $t$ 超过特定阈值（$t \gg t_{up}$），数据集包含至少一对强相似点（违反 SD）的概率趋近于 1。
  这些临界阈值取决于主要数据点和异常数据点的极端相似性和关联概率。

3. 说明性示例：
   研究结果通过类别数据集进行了说明，其中总空间大小 $L$ 远大于数据集大小 $n$。论文推导了这些情况下的特定界限，展示了特征数量、相似性阈值与关联概率之间的相互作用如何决定临界性。

意义与主张
本文声称为理解 AI 生成数据（异常值）对数据集处理的影响提供了理论基础。具体而言：

• 它强调了与主要数据点关联的异常值可以诱发一种“奇异性”或“天网阈值”（Remark 2），即即使异常值的数量相对于总数据集规模微不足道，数据集的分解特性也会被异常值所接管。
• 它为在存在此类异常值的情况下，通过确定最小批次规模以确保平衡学习（不相似批次）提供了严格的界限。
• 它提供了随机欠采样的临界规模估计，确保缩减后的数据集能够保留强不相似性，这对于高效的模型训练至关重要。

该工作依赖于标准的着色技术和图论界限，但以自洽的方式呈现，未显式使用着色术语。结果是渐近性的，即当数据集规模 $n \to \infty$ 时，以高概率（$1 - o(1)$）成立。