🤖 machine learning

Complement Submodular Information Measures for Balanced and Robust Data Selection

本文介绍了互补子模信息（CSI），这是一类新的目标函数，通过量化所选子集与其补集之间的结构关系，实现具有近优贪心近似保证和卓越下游性能的平衡且鲁棒的数据选择。

原作者： Rishabh Iyer

发布于 2026-05-26

📖 1 分钟阅读☕ 轻松阅读

原作者： Rishabh Iyer

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你是一位博物馆策展人，任务是从 10,000 幅藏画中挑选一小部分，用于新展厅的展出。你的目标是从这 10,000 幅作品中选出“最佳”的 100 幅。

旧方法（标准次模优化）
传统上，策展人（或计算机算法）会审视他们已选中的画作，并问道：“这 100 幅画是否涵盖了所有不同的风格？它们是否多样？它们是否看起来像整个博物馆的‘平均值’？”

这种方法的缺陷在于，它忽略了留在储藏室里的画作（即“补集”）。

如果算法试图追求多样性，它可能会抓取几幅怪异、孤立的画作，这些画作与其他任何作品都截然不同，仅仅为了勾选“多样性”这一项。这些就像是“异常值”——格格不入的怪异异常值。
如果算法试图追求代表性，它可能只会挑选最著名、最受欢迎的画作（分布的“头部”），而忽略那些隐藏在后方、安静、稀有却美丽的杰作（分布的“尾部”）。

新方法（补集次模信息 - CSI）
本文提出了一种名为补集次模信息（Complement Submodular Information, CSI）的新策略。CSI 不再仅仅审视你选中的画作，而是强制你同时审视既包括你选中的画作，也包括你留下的画作。

这就像是一个天平。

标准方法只称量天平左侧的物品。
CSI则同时称量左侧和右侧的物品，确保天平保持平衡。

用通俗语言解释其工作原理

作者制定了一套数学“规则手册”（框架），改变了我们挑选数据的方式。其核心理念如下：

1. “双向”规则
当你挑选一幅画时，你不仅要问：“这幅画好吗？”还要问：“如果我选了这幅，剩下的画作状态是否依然良好？”

如果你选了一幅怪异的异常值，剩下的画作可能会显得极不平衡。CSI 会说：“不，不要选那个。”
如果你选了一幅代表稀有风格的画作，它能确保剩下的画作依然拥有良好的其他风格混合。CSI 会说：“是的，选那个。”

2. “异常值抑制器”
想象一袋弹珠。大多数是红色的，一些是蓝色的，还有一颗是发光的霓虹绿色，与其他任何颜色都不匹配。

旧算法可能会抓取那颗霓虹绿色的弹珠，因为它“与众不同”。
CSI则意识到，如果你拿走了那颗霓虹绿色的弹珠，袋子里剩下的部分就会显得奇怪地缺乏那种特定的“怪异感”。因此，它决定留下那颗霓虹绿色的弹珠，转而挑选一颗能帮助平衡红色弹珠的蓝色弹珠。它抑制了噪声。

3. “稀有宝石”发现者
想象一个图书馆，里面有 1,000 本关于猫的书，只有 5 本关于稀有、已灭绝蜥蜴的书。

旧算法可能会挑选 100 本关于猫的书，因为它们是“主要”内容。
CSI审视“被留下的猫书”，并意识到：“如果我不选一本蜥蜴书，剩下的图书馆里就完全没有蜥蜴了。”因此，它确保蜥蜴书被选中，从而保留了整个收藏的稀有结构。

“秘密武器”（简化后的数学部分）

本文证明，这种“双向”方法不仅仅是一个美好的想法；它在数学上是有效的。

他们表明，尽管这条新规则很棘手（并不总是“越多越好”），但其表现足够良好，以至于一种简单的、逐步的贪心方法（逐个挑选最佳下一项）仍然能找到非常好的解决方案。
他们在合成数据（人工实验）和真实数据（如数字图像、衣物和新闻文章）上对此进行了测试。

结果

当他们测试这种新方法时：

更好的平衡性：选定的数据组更加平衡。它们不仅抓取了热门内容或怪异异常值，而是获得了一种能代表整体故事的混合体。
更少的错误：在这些选定组上训练的模型在预测新事物时表现更好。
隐藏的模式：即使“稀有”组（如蜥蜴书）没有被标记或命名，CSI 方法也能自然地发现它们，因为它审视的是“被选中”组和“被留下”组之间的平衡。

总结类比

将数据集想象成一幅拼图。

标准方法试图抓取色彩最丰富的拼块来拼出一幅漂亮的图画，往往忽略了边缘拼块或形状奇怪的拼块。
CSI则审视你抓取的拼块以及你留在桌上的拼块。它确保你抓取的拼块能组成一幅完整的图画，而你留下的拼块也能组成一幅完整的图画。它防止你囤积“怪异”的拼块，或忽略那些“无聊”但必要的边缘拼块。

本文得出结论：通过关注划分的双方（你选中的部分和你留下的部分），你可以为机器学习获得更稳健、更平衡、更准确的数据选择。

技术摘要：用于平衡与鲁棒数据选择的互补子模信息度量

问题陈述

由于子模优化能够建模覆盖性、多样性和代表性，它已成为数据选择、检索和摘要的标准范式。经典的子模目标（例如设施选址、LogDet、集合覆盖）孤立地优化所选子集的效用。然而，在现代机器学习应用中——如训练/验证/测试集划分、基准构建和鲁棒子集选择——选择的质量往往 critically 取决于所选子集与剩余数据（即补集）之间的结构关系。

标准目标存在两个主要局限性：

代表性偏差：设施选址等目标可能过度关注主导区域或中心背景结构，而忽视稀有或“长尾”语义切片。
多样性偏差：LogDet 等目标可能激进地选择与其他数据高度不同的孤立离群点，从而无法保留连贯的稀有语义簇。

所解决的核心问题是缺乏对所选子集与其补集之间结构信息的显式保留，导致选择结果失衡，要么忽略长尾分布，要么包含噪声离群点。

方法论

互补子模信息 (CSI)

作者引入了互补子模信息 (CSI)，这是一个面向补感的统一子模目标框架。给定一个归一化的单调子模函数 $f: 2^V \to \mathbb{R}$ 和子集 $A \subseteq V$ ，CSI 目标定义为：
$I_f(A; V \setminus A) = f(A) + f(V \setminus A) - f(V)$
该公式作为子模互信息的补感类比。它通过鼓励在所选子集 ( $A$ ) 和剩余数据 ( $V \setminus A$ ) 上共同保留结构，来量化共享的结构信息。

具体实例

该框架衍生出几种经典子模函数的补感变体：

设施选址互补信息 (FLCI)：鼓励平衡的代表性划分。仅当某点同时被所选子集及其补集良好表示时，该点才做出贡献。
图割互补信息 (GCCI)：衡量跨划分边界的连通性，倾向于具有强跨划分交互的子集。
LogDet 互补信息 (LogDetCI)：在划分间共同保留多样性。它在两侧维持行列式体积，在保留连贯稀有簇的同时，抑制在补集中缺乏支持的孤立离群点。
概率集合覆盖 (PSCCI)、饱和覆盖 (SCCI) 和基于特征 (FBCI)：这些变体同样强制在两个划分上实现平衡的概率覆盖、局部邻域保留和语义特征激活。

优化与理论保证

CSI 目标是对称的且通常是非单调的。然而，作者证明，在受限曲率条件下，它们表现出近似单调性。

近似单调性：非单调性的程度由底层函数的受限曲率 $\kappa_k(f)$ 控制。
贪心近似：在这些条件下，标准贪心算法实现了近 $(1 - 1/e)$ 的近似保证。具体而言，如果 $A_g$ 是贪心解， $A^*$ 是最优解：
$I_f(A_g; V \setminus A_g) \geq \left(1 - \frac{1}{e}\right) I_f(A^*; V \setminus A^*) - \frac{k\epsilon}{e}$
其中 $\epsilon$ 受底层函数的曲率和最大边际增益限制。
效率：论文指出，高效的实现方式（例如记忆化、懒惰贪心、秩一行列式更新）使得 CSI 优化在计算上与标准子模优化相当。

主要贡献

统一框架：引入 CSI 作为面向补感的子模目标的系统框架。
理论分析：推导主要子模函数的补感变体，并证明在受限曲率下贪心优化的近 $(1 - 1/e)$ 近似保证。
实证验证：证明在鲁棒的隐藏切片感知子集选择中，CSI 目标显著优于经典子模目标和随机基线。

实验结果

合成实验

作者在包含不同大小高斯簇（模拟头部、中部和尾部语义区域）以及孤立离群点的合成数据集上评估了 CSI 目标。

指标：少数类覆盖率、离群点选择率以及所选/补集/全部分布之间的 KL 散度。
发现：
- 平衡保留：与标准对应物相比，CSI 变体（FLCI、LogDetCI、SCCI、FBCI）一致提高了稀有/尾部语义切片的覆盖率。
- 离群点抑制：虽然标准 LogDet 激进地选择离群点，但 LogDetCI 在保留稀有模式的同时，将离群点选择率降低了近三倍。
- 代表性平衡：FLCI 和 SCCI 在代表性覆盖和鲁棒性之间实现了卓越的平衡，最小化了所选子集与完整数据集之间的 KL 散度。
- 图割局限性：发现 GCCI 倾向于密集且高度连接的头部区域，而非平衡的语义覆盖，因此在此背景下不太适合代表性保留。

鲁棒隐藏切片感知子集选择

该框架在六个具有潜在语义切片和注入噪声的真实世界数据集（MNIST、FashionMNIST、CIFAR10、Digits、HAR、20Newsgroups）上进行了测试。

设置：在选择子集时无法访问切片标签（仅使用无监督聚类进行评估）。下游模型在这些子集上进行训练。
结果：CSI 目标（特别是 FLCI、LogDetCI 和 SCCI）在下游分类准确率方面始终优于随机选择、分层选择以及底层的标准子模目标。
洞察：性能提升归因于 CSI 能够保留连贯的稀有语义结构，同时抑制噪声和孤立离群点，而标准目标未能实现这种平衡。

意义与主张

论文声称，联合保留所选子集及其补集的结构信息，比单独优化子集能产生更平衡、更鲁棒的数据选择。这项工作的意义在于：

填补结构空白：超越孤立优化所选子集，显式建模其与补集的关系。
实际鲁棒性：提供了一种方法，自然地调节经典目标过度关注主导区域或选择离群点的倾向，从而在存在隐藏语义不平衡和噪声的情况下提高下游预测性能。
理论可靠性：确立尽管这些目标是非单调的，但它们仍然是可处理的，并具有强有力的理论近似保证。

作者得出结论，CSI 提供了一种统一的方法，以实现头部和尾部语义结构的平衡保留，使其特别适用于需要鲁棒子集选择和公平数据划分的应用。