多实例学习 (MIL) 综述：问题特性与应用

三、MIL 问题的关键特性分类

这篇综述的核心贡献是将 MIL 问题的特性系统地归纳为四大类（如原文中图 1 所示）：

1. 预测级别：任务是进行包级分类还是实例级分类？这是选择算法的首要决定因素。
2. 包组成：
   • 见证率：正包中正实例的比例。低见证率问题极具挑战。
   • 实例间关系：
     • 包内相似性：同一包内的实例可能非常相似（如来自同一分子的构象、同一张图片的相邻 patches）。
     • 实例共现：某些实例倾向于同时出现（如'鸟'和'天空'）。
     • 包/实例结构：实例间存在时空或语义上的结构（如视频中的时间序列、网页间的超链接）。
3. 数据分布：
   • 多模态正类分布：正类概念可能对应特征空间中的多个簇（如不同样子的'蚂蚁'）。
   • 非代表性负类分布：训练集中的负实例无法涵盖测试时可能遇到的所有负类模式（如一张'猫'的图片，背景可以是任何东西）。
4. 标签歧义性：
   • 标签噪声：bag-level 的标签可能存在错误，例如，一个被标记为'无猫'的图片可能实际上包含一个很小的、被忽略的猫。
   • 不同的标签空间：实例的语义标签可能与包的标签完全不同。例如，一个'斑马'包（bag-label）中的实例可能是一些无明确语义的纹理 patch（instance-label）。

以下对这四类关键特性分别讨论

特征 1：预测级别（Prediction Level）

本质区别：你要分类的是包还是示例？

关键发现：在正包中，只要找到一个正例，包标签就正确，因此包分类算法会主动"忽略"难以识别的正例，导致其示例分类性能极差。实验表明，包分类最优算法在示例任务上可能表现最差。

公式化代价差异：

• 包级 FN（假负）：漏检一个正例 → 若包中还有其他正例，可能不影响包判断
• 包级 FP（假正）：误检一个负例为正 → 整个负包被错误分类
• 示例级 FN/FP：每个示例的误判都直接计入损失

特征 2：包组成（Bag Composition）

2.1 见证率（Witness Rate, WR）

定义：正包中正例所占比例

• 高 WR（>50%）：正包几乎全是正例 → 退化为带噪声的监督学习
• 低 WR（<10%）：正包中仅 1-2 个正例 → 算法极易"迷失"

影响：当 WR 极低时，将包标签赋给所有实例（如 SI-SVM）会导致99% 的假正标签，严重污染训练集。专门处理低 WR 的方法包括：

• stMIL：修改 SVM 约束，只需找到一个正例即可
• miGraph：构建图结构，相似示例共享权重，降低稀有正例的影响

2.2 示例间关系

真实数据很少满足 i.i.d.假设，存在三类相关性：

a) 包内相似性：同一图像的 patch 因共享光照、背景而相似。若算法过度拟合这种相似性，可能学会"区分图像"而非"区分目标"。

• 缓解方法：特征选择（Relief-MI）或学习新表示空间，使同类示例距离近，而非同包示例距离近。

b) 共现关系：某些概念常一起出现（如"鸟"和"天空"）。这对包分类是机会（sky 提供上下文），对示例分类是干扰（天空被误认为鸟）。

c) 结构信息：视频帧有时序，网页有链接关系。图模型（miGraph）和 CRF 可捕捉此类结构。

特征 3：数据分布（Data Distribution）

3.1 正例多模态分布

传统方法（如 APR、Diverse Density）假设正例在特征空间单簇分布，但现实中同一概念可能有多个外观（如"蚂蚁"有红黑黄、有翅无翅等多种形态）。

解决方案：

• 原型法：MILES、DD-SVM 用多个原型点表示不同模态
• 分布法：BoW、miFV 将包编码为实例分布，天然处理多模态

3.2 负分布不可代表

在开放世界问题中（如网络图片背景无限多样），训练集无法覆盖所有负例分布。

建模正例区域而非负分布的方法更健壮，如：

• 单类 SVM：将正例作为目标类，其余全判负
• 距离法：APR、Citation-kNN 基于到正例中心的距离决策

实验显示，当测试负分布与训练差异>30% 时，包空间方法（如 EMD-SVM）显著优于实例空间方法。

特征 4：标签歧义（Label Ambiguity）

4.1 标签噪声

标准假设下，负包被错误标记为正会导致灾难：正概念区域被迫包含负例，模型崩溃。

鲁棒方法：

• 分布表示：EMD-SVM、miGraph 将包编码为直方图，单个噪声点影响有限
• 阈值假设：要求正包中至少有θ个正例，而非至少 1 个

实验表明，当 30% 包标签错误时，嵌入空间方法性能稳定，而实例空间方法（mi-SVM）迅速降至随机水平。

4.2 不同标签空间

包标签"汽车" vs. 示例标签"轮胎/车窗/大灯"，两者语义层次不同。此时标准假设失效，因为无法为示例分配明确类别。

解决方案：必须使用集体假设，将实例映射到无监督发现的"词汇"（如 BoW 模型），在词汇分布层面分类。

四、现有方法分类与典型算法

根据算法在何种空间进行操作，MIL 方法可分为三大类：

1. 实例空间方法（Instance-Space）

这类方法的核心是先学习一个实例级分类器 $f(x)$，然后通过聚合策略（如取最大概率）得到包标签。

• 思想：直接求解实例标签的歧义性问题。
• 特点：
  • 天然适合实例分类任务。
  • 对于包分类，当见证率较低时，容易因关注单个实例而忽略其他有用信息。
  • 适合用于 WR 较高、标签干净的实例分类任务
• 典型方法：
  • APR：寻找特征空间中的一个轴平行矩形，使其包含每个正包至少一个实例，且不包含任何负包实例。
  • Diverse Density (DD) & EM-DD：在特征空间中寻找一个点，该点距离至少一个正包实例'近'，而距离所有负包实例'远'。EM-DD 使用期望最大化算法来优化这个过程。
  • MI-SVM 和 mi-SVM：基于 SVM 的转换方法。
    • mi-SVM：将所有实例初始化为其包标签，然后迭代地训练 SVM 并根据 SVM 的输出更新实例标签，同时约束正包中必须至少有一个正实例。
    • MI-SVM：在每次迭代中，只将每个正包中'最像正例'的那个实例（如 SVM 得分最高的）视为正实例用于下一次训练。
  • MIL-Boost：将 Boosting 框架与 MIL 损失函数结合，通过梯度提升来训练一个强大的实例分类器。

2. 包空间方法（Bag-Space）

这类方法不显式地对单个实例进行分类，而是将每个包视为一个整体，通过度量包与包之间的距离或相似性来进行分类。

• 思想：绕过实例标签的歧义，在更高层次上比较包的整体特性。
• 特点：
  • 通常在包分类任务上表现优异。
  • 善于处理集体假设和包内实例复杂的关系。
  • 大多数方法无法直接进行实例分类。
• 典型方法：
  • Citation-kNN：使用 Hausdorff 距离等度量来计算包之间的距离，并借鉴'引用'和'参考文献'的思想进行 kNN 分类。
  • MInD：将每个包表示为一个向量，其元素是该包与训练集中所有其他包的（不）相似度，然后使用标准分类器（如 SVM）对该向量进行分类。
  • NSK-SVM：使用归一化集核，计算两个包之间所有实例对相似度的平均值，并将其作为 SVM 的核函数。

3. 嵌入空间方法

这类方法将每个包映射成一个固定长度的特征向量，这个向量是对包内容的总结。然后，任何标准的监督学习算法都可以应用于这些嵌入向量。

• 思想：将 MIL 问题转化为标准的监督学习问题。
• 特点：
  • 计算效率高，尤其适用于大规模数据。
  • 嵌入向量的设计至关重要，它决定了方法能否捕捉到包的关键信息。
• 典型方法：
  • MILES：从训练集中选择一组原型实例。每个包被表示为一个向量，向量中的每个元素是该包与一个原型实例的最大相似度。然后使用 1-范数 SVM 进行分类和原型选择。
  • CCE：首先对实例空间进行聚类。每个包被表示为一个二进制向量，指示哪些聚类中心至少被该包中的一个实例所覆盖。通过使用不同数量的聚类来构建分类器集成。
  • BoW-SVM：与文本处理中的词袋模型类似。首先通过聚类（如 k-means）在实例空间构建一个'视觉词典'。然后，每个实例被分配给最近的词，包被表示为词频直方图，最后用 SVM 分类。
  • EMD-SVM：将包视为分布，使用推土机距离来衡量两个包（分布）之间的差异，并基于此构造 SVM 核。
  • miGraph：考虑实例间的非独立同分布关系。为每个包构建一个图，节点是实例，边表示实例相似性。通过图核来比较包的相似性，并降低大簇中实例的权重。

五、实验与关键结论

该综述通过大量实验比较了 16 种代表性算法，得出了一些重要结论：

1. 实例分类 vs. 包分类：
   • 一个算法在包分类上表现好，绝不意味着它在实例分类上也表现好。这是两种不同的任务。
   • 对于实例分类，当见证率不是极低时，简单地将包标签分配给所有实例（如 SI-SVM）然后使用标准监督学习，其效果可能与复杂的 MIL 方法相当甚至更好。
   • 对于包分类，包空间和嵌入方法通常在较高见证率下表现更好。
   • 对于包含 N 个示例的包，包分类的 FN 代价为 $1/N$，FP 代价为 1。这种代价不对称性导致优化包损失的算法天然偏向高召回、低精度，不适合示例任务。
2. 见证率的影响：
   • 所有方法的性能都随见证率的降低而下降。
   • 在低见证率下，MI-SVM（只关注每个包中最正实例）等策略相对更有效。
3. 负类分布的变化：
   • 当测试集的负类分布与训练集不同时，包空间方法（特别是基于距离的如 C-kNN）通常更具鲁棒性。因为它们的决策更多依赖于正包之间的内在相似性，而非负类的绝对特征。
4. 标签噪声：
   • 嵌入方法（如 EMD-SVM, MInD）对标签噪声最不敏感。因为它们将包编码为特征向量，本质上是在学习包的总体统计特性，对个别异常实例不敏感。
   • 实例空间方法（如 mi-SVM, MIL-Boost）对标签噪声非常敏感，因为它们严重依赖正确的包标签来识别'纯净'的正类概念。
5. 评估指标：
   • 仅使用 AUC 评估是不够的。一些方法能学习到好的排序函数（高 AUC），但决策阈值选择不佳，导致准确率很低。应同时报告 AUC 和基于准确性的指标（如 F1 分数）。

六、未来研究方向与挑战

基于对现状的分析，文章指出了以下有前景的未来研究方向：

1. 拓展任务边界：目前研究主要集中在分类任务上，MIL 回归（如预测疾病严重程度）和MIL 聚类（如发现视频中的重复动作模式）探索不足。
2. 专注于实例分类的方法：需要设计真正为实例分类目标优化的新算法，而不是将其作为包分类的副产品。
3. 处理正包与未标注包：在许多推荐系统等场景中，我们只有用户喜欢的物品（正包）和大量未标注的物品包。如何在这种设定下进行 MIL 学习是一个挑战。
4. 深入利用包内结构：当前大多数方法忽略了实例间的复杂结构（时空、语义）。图神经网络等新技术为建模这种结构提供了可能。
5. 解决类不平衡问题：MIL 问题中实例级别的类不平衡通常非常严重，需要专门的研究。
6. 主动学习：如何智能地选择最具信息量的实例请专家标注，以高效提升模型性能。
7. 表征学习：如何为 MIL 设计端到端的深度学习模型，自动学习对包和实例分类最有效的特征表示，是一个热门且重要的方向。
8. 多模态 MIL：当包内的实例来自不同模态（如图像、音频、文本）时，如何有效地进行融合和学习。

七、总结

这篇关于多实例学习的综述为我们提供了一个清晰的路线图。它告诉我们，MIL 不是一个单一的问题，而是一个由预测级别、包组成、数据分布和标签歧义性四个维度的特性所定义的问题谱系。没有一种方法能在所有情况下都表现最佳。选择或设计 MIL 算法时，必须首先考虑手头问题所具有的具体特性。这项工作为未来 MIL 的研究奠定了坚实的基础，有望推动该领域从'什么算法在某个数据集上效果好'的经验主义，走向'为什么这个算法对这类问题有效'的原理性理解。