多实例学习算法对于实例是可学习的吗？

paper：Are Multiple Instance Learning Algorithms Learnable for Instances?

0. TL; DR

作者基于PAC学习理论，构建了一个评估深度多实例学习（Deep MIL）算法的实例级可学习性（instance-level learnability）理论框架。研究发现，算法能否在实例级别学习，取决于其池化（Pooling）方式是否满足特定的理论条件。

在考虑实例间相互依赖的通用场景下，现有的主流池化方法中，只有Conjunctive-Pooling（在实例预测结果上进行加权聚合）是理论上可学习的。像 Embedding-Pooling（在特征层面聚合）和 Attention-Pooling（将注意力权重乘在特征上）这类流行方法，由于在预测单个实例时引入了其他实例的信息，污染了其假设空间，因此在理论上不具备实例级可学习性。

1. 背景介绍

在许多现实世界的机器学习任务中，获取精细的样本标签成本极高。以病理图像分析为例，一张全切片图像（WSI）可能包含数百万个细胞或组织图块，而病理学家通常只会给出整张切片的诊断结论，如“癌变”或“正常”。为每个图块都打上标签几乎是不可能的。

多实例学习（Multiple Instance Learning, MIL） 将数据组织成“包-实例”的层级结构，标签是在包级别给出的。MIL的初衷不仅是判断整个包的标签，更深层次的目标是利用这种弱监督信号，定位并识别出那些关键的正实例（例如，找到WSI中真正的癌变区域）。

目前缺乏一个理论框架来回答：一个给定的MIL算法，其实例级可学习性（instance-level learnability）能否得到保证？即一个在包级别表现优异的MIL算法，是否就意味着它也学会了如何正确地分类单个实例？如果设计的算法在理论上就无法学习实例标签，那么即使包级别的准确率再高，其在定位关键实例等下游任务上的表现也是不可靠的。

本文正是为了填补这一理论空白，旨在构建一个坚实的数学基础，以判断各种Deep MIL算法是否真正“可实例学习”。

2. 实例可学习性的理论框架

作者基于经典的PAC（Probably Approximately Correct）学习理论，构建了一个用于分析MIL实例级可学习性的理论框架。

2.1 实例级可学习性的定义

首先定义几个关键概念：

包风险 (Bag Risk, $R_{bag}$): 模型在包级别预测的期望损失。
实例风险 (Instance Risk, $R_{inst_i}$): 模型在第$i$个实例上预测的期望损失。
PAC可学习性: 指算法能够在给定足够多的样本后，以高概率（$1-\delta$）找到一个错误率足够小（$\le \epsilon$）的假设（模型）。

本文的所有讨论都基于一个前提假设：所研究的MIL算法在包级别是PAC可学习的。这个假设是合理的，因为如果一个算法连包都学不好，讨论它能否学好实例就失去了意义。基于此，作者给出了实例级可学习性的定义：

一个MIL算法是实例级可学习的，当且仅当它的包级PAC可学习性与实例级PAC可学习性是等价的。

\[P \left[ \left| R_{bag} - \inf R_{bag} \right| \le \epsilon \land \bigcap_{i=1}^n \left| R_{inst_i} - \inf R_{inst_i} \right| \le \epsilon \right] \ge 1-\delta\]

这个公式的直观解释是：模型能够以高概率同时保证包级别和所有实例级别的学习误差都很小。如果这个条件成立，那么只要保证了包级别的学习，实例级别的学习也就得到了保证。因此，该公式成为判断一个算法是否为实例级可学习的充要条件。

2.2 两种场景下的可学习性条件

为了推导更具普适性的结论，作者将问题分为两种场景：

独立包域空间 ($D_{XY}^{Ind}$): 假设包内所有实例在统计上是相互独立的。
通用包域空间 ($D_{XY}^{Gen}$): 不做任何独立性假设，允许实例间存在相互依赖关系。这是更贴近现实的场景。

针对这两种场景，作者分别推导出了实例级可学习的充要条件。

场景一：实例相互独立 ($D_{XY}^{Ind}$)

在实例相互独立的假设下，一个MIL算法是实例级可学习的，当且仅当其最优包风险等于所有实例的最优风险之和。

\[\inf R_{bag} = \sum_{i=1}^{N} \inf R_{inst_i}\]

直观理解: 如果实例间没有关联，那么整个包的“学习难度”（最优风险）就应该是所有单个实例“学习难度”的简单叠加。

场景二：实例存在依赖 ($D_{XY}^{Gen}$)

在实例间可能存在依赖的通用场景下，一个MIL算法是实例级可学习的，当且仅当其最优包风险等于所有实例最优风险的加权和。

\[\inf R_{bag} = \sum_{i=1}^{N} \alpha_i \inf R_{inst_i}, \quad \text{s.t.} \sum_{i=1}^{N} \alpha_i = 1, 0 \le \alpha_i \le 1\]

直观理解: 这里的权重 $\alpha_i$ 体现了不同实例对包标签的贡献度或重要性，从而捕捉了实例间的依赖关系。这正是注意力机制所做的事情。

2.3 分析现有Deep MIL池化方法

作者将现有的Deep MIL方法根据其池化（Pooling）机制分为了五类，并用上述理论逐一进行检验。

Instance-Pooling: 先对每个实例做预测，再对预测结果进行聚合（如max/mean pooling）。
- 结论: 在独立场景下 ($D_{XY}^{Ind}$) 可学习。因为它满足最优包风险是实例风险之和的条件。但在通用场景下不可学习。
Embedding-Pooling: 先将所有实例的特征向量聚合（如max/mean pooling）成一个包特征，再对这个包特征做预测。
- 结论: 不可实例学习。在预测第$i$个实例时，该方法实际上使用了由所有实例特征聚合而成的包特征。这意味着对实例$i$的预测引入了其他实例的信息，不满足预测实例$i$时引入的额外假设空间 $H_{add_i}$ 必须是其自身假设空间 $H_{inst_i}$ 的子集。
Attention-Pooling: 将注意力权重乘以实例的特征向量，然后进行加和聚合，最后做预测。
- 结论: 不可实例学习。原因与Embedding-Pooling类似。注意力权重通常是根据整个包的信息计算得出的。将这个权重乘在特征层面，同样意味着在为实例$i$构建表征时，引入了来自其他实例的信息。这违反了实例预测应主要依赖于自身特征的原则。
Additive-Pooling: 将注意力权重乘以实例特征，然后对每个加权后的特征分别做预测，最后将预测结果相加。
- 结论: 不可实例学习。尽管预测是分布到每个实例上，但乘法操作依然在特征层面，同样存在假设空间被污染的问题。
Conjunctive-Pooling: 先对每个实例独立地进行预测，然后将注意力权重乘以每个实例的预测结果，最后进行加权求和。
- 结论: 在通用场景下 ($D_{XY}^{Gen}$) 可实例学习。这是唯一一种将注意力机制作用于预测结果层面而非特征层面的方法。每个实例的初步预测 $p_i(f_i(X_i))$ 只依赖于自己的特征 $X_i$，保证了其假设空间的“纯净性”。最终的包预测 $g(X) = \sum \alpha_i \cdot p_i(f_i(X_i))$ 正好符合了通用场景下的可学习条件。

2.4 对位置依赖性的思考

论文进一步将该理论框架应用到了时间序列和图像等具有位置依赖性的数据上。

如果使用RNN等结构来提取实例特征，或者将位置编码（Positional Encoding）直接加到实例特征上进行预测，那么模型将不可实例学习。这两种方法都为预测实例$i$引入了来自其他位置（$j \neq i$）的信息，同样违反了实例假设空间纯净性的原则。

正确做法: 位置依赖等外部信息应该仅用于计算注意力权重 $\alpha_i$，而不应直接参与实例$i$自身特征的构建或预测过程。

3. 实验分析

作者通过一系列精心设计的实验，对上述理论推导进行了验证。

3.1 实验一：注意力在通用场景下的必要性

本实验的目的是验证在实例间存在依赖的通用场景 ($D_{XY}^{Gen}$)下，不使用注意力的算法（如Instance-Pooling）是否会失效。

作者构建一个合成的MNIST数据集，其中包的标签依赖于特定数字组合（例如，“包里同时有3和5”）。这强制模型学习实例间的关系。

结果表明，Instance-Pooling类方法（如mi-Net, Causal MIL）的性能非常差（F1分数在0.2-0.3左右）。而使用注意力机制的方法（Attention-Pooling, Conjunctive-Pooling等）则表现优异（F1分数在0.75以上）。在需要建模实例间关系的通用场景下，注意力机制是让模型在包级别可学习的必要条件。

3.2 实验二：不同池化方法的实例级学习能力

本实验的目的是验证哪种池化方法真正具备实例级学习能力。

在一个同时拥有包标签和实例标签的数据集上，比较不同算法在包级别和实例级别的性能差距。差距越小，说明实例级可学习性越好。

结果表明，Conjunctive-Pooling的包级别和实例级别的性能差距非常小（Macro-F1差距约0.15，AUROC几乎无差距）。Attention-Pooling / Additive-Pooling性能差距巨大。例如，Attention MIL的包级别AUROC为0.95，而实例级别骤降至0.73；TransMIL的Macro-F1差距更是高达0.63。

Conjunctive-Pooling确实是实例级可学习的，而那些在特征层面应用注意力的方法，尽管包级别性能很高，但实际上并没有学会如何准确分类单个实例。

3.3 实验三：位置依赖信息的正确用法

本实验的目的是验证如何正确地使用位置信息（如时间序列中的时序）才能不破坏实例级可学习性。

在一个时间序列分类数据集（WebTraffic）上，对比Conjunctive-Pooling在不同配置下的实例级预测性能。

Default: 不使用位置信息。
All: 将位置信息同时用于预测和注意力计算。
Att: 仅将位置信息用于注意力计算。
Predict: 仅将位置信息用于预测。

结果表明，Att配置（仅用于注意力）的性能最好（AOPCR=14.55, 17.50）。 Predict和All配置（用于预测）的性能甚至比Default（基线）还要差。

实验证明了将位置信息直接喂给预测器会“毒害”模型的实例学习能力。而将其作为一种上下文信息，仅用来指导注意力权重的分配，则能有效提升性能。