【论文阅读笔记】多实例学习手段 Diverse Density（DD）：在特征空间中寻找正概念的坐标

本文介绍1998年由Maron和Lozano-Pérez提出的多实例学习通用框架——Diverse Density哪一个），负包仅含负实例。Diverse Density凭借最大化"正包交集与负包并集之差"的概率密度来定位目标概念。就是。该框架解除一个特殊学习场景：训练材料以"包"（bag）为单位标记，正包涵盖至少一个正实例（但不知道具体

Maron, Oded, and Tomás Lozano-Pérez. “A framework for multiple-instance learning.”Advances in neural information processing systems10 (1997).

文章目录

• • 一、多实例学习
  • • 1.1 从监督学习到多实例学习
    • 1.2 问题的挑战性
  • 二、Diverse Density
  • • 2.1 从几何直觉到概率建模
    • 2.2 概率模型构建
  • 三、算法完成
  • • 3.1 优化策略
    • 3.2 特征权重学习
    • 3.3 扩展到复杂概念
  • 四、实验
  • • 4.1 合成材料集
    • 4.2 Musk药物活性数据集
    • 4.3 人物图像识别
    • 4.4 股票基本面分析
  • 五、总结

一、多实例学习

1.1 从监督学习到多实例学习

传统监督学习中，每个训练样本都有明确标签。然而许多现实场景无法给出如此精确的标签。考虑药物分子活性预测问题：

• 一个药物分子可采取多种三维形状（构象）
• 只要至少一种形状能与目标蛋白结合，该分子就是"有效"的（正例）
• 若分子所有可能形状都无法结合，则标记为负例
• 哪一种形状导致了结合就是但我们不知道具体

这引出多实例学习（Multiple-Instance Learning, MIL）框架：

• 包（Bag）：一个分子对应一个包，包含其所有可能形状（实例）
• 标签：包级标签（正/负），而非实例级标签
• 目标：学习一个能正确判别单个实例（形状）的分类器

形式化定义：

• 给定训练集 $\{B_i,y_i{\}}_{i=1}^N$，其中 $B_i=\{{\mathbf{x}}_{i1},{\mathbf{x}}_{i2},...,{\mathbf{x}}_{i,n_i}\}$ 是第 $i$ 个包
• $y_i\in \{0,1\}$ 是包标签：
  • $y_i=1$（正包）：$\exists {\mathbf{x}}_{ij}\in B_i$ 是正实例
  • $y_i=0$（负包）：$\forall {\mathbf{x}}_{ij}\in B_i$ 都是负实例
• 目标：学习概念$c:\mathcal{X}\to \{0,1\}$，使其对实例分类的误差最小

1.2 问题的挑战性

这个问题比有噪声监督学习更困难，因为：

• 噪声比例无界：正包中可能99%的实例都是负的，仅含一个正实例
• 标签歧义正例就是：无法直接获知哪个实例
• 分布未知：通常只知道有限采样，无法获知包内实例的完整分布

二、Diverse Density

2.1 从几何直觉到概率建模

关键观察特征空间中的单个点就是：若目标概念$\mathbf{t}$，则：

• 每个正包 $B^{+}$ 应至少包含一个靠近$\mathbf{t}$ 的实例
• 所有负包 $B^{-}$ 应不包含任何靠近$\mathbf{t}$ 的实例

如图1(a)所示，若分子形状轨迹在$\mathbf{t}$处相交，则该点即为目标概念。但实际只能获得离散采样点（图1(b)），因此问题转化为：寻找被多个正包覆盖且远离负实例的高密度区域。

区别于普通密度：图1(b)中区域B虽有高密度，但可能来自同一正包的多个实例；我们关注的是来自不同正包的多样性覆盖，故称 Diverse Density。

2.2 概率模型构建

假设目标概念为单点$\mathbf{t}$，Diverse Density定义为在该点观察到训练数据的似然：

$$\text{DD}(\mathbf{t})=\mathrm{Pr}\left(\underset{i}{\bigwedge }{B}_i^{+}\wedge \underset{j}{\bigwedge }{B}_j^{-}\mid \mathbf{t}\right)$$

其中 $B_i^{+}$ 表示第 $i$ 个正包，$B_j^{-}$ 表示第 $j$ 个负包。

推导过程：

1. 贝叶斯视角：在无信息先验下，最大化后验概率等价于最大化似然：

$${\mathbf{t}}^{\ast }=\arg \underset{\mathbf{t}}{\max }\mathrm{Pr}\left(\{B_i\}\mid \mathbf{t}\right)$$

2. 条件独立性假设：给定 $\mathbf{t}$，各包标签条件独立：

$$\mathrm{Pr}\left(\{B_i\}\mid \mathbf{t}\right)=\prod _{i:y_i=1}\mathrm{Pr}(B_i^{+}\mid \mathbf{t})\cdot \prod _{j:y_j=0}\mathrm{Pr}(B_j^{-}\mid \mathbf{t})$$

3. Noisy-OR模型：对正包，"包为正"的概率等于"至少一个实例触发概念"的概率。采用Noisy-OR建模：

$$\mathrm{Pr}(B_i^{+}\mid \mathbf{t})=1-\prod _{\mathbf{x}\in B_i^{+}}\left(1-\mathrm{Pr}(\mathbf{t}\mid \mathbf{x})\right)$$

类似地，负包要求所有实例都不触发概念：

$$\mathrm{Pr}(B_j^{-}\mid \mathbf{t})=\prod _{\mathbf{x}\in B_j^{-}}\left(1-\mathrm{Pr}(\mathbf{t}\mid \mathbf{x})\right)$$

4. 实例-概念相似度：定义单个实例$\mathbf{x}$ 触发概念 $\mathbf{t}$的概率为距离衰减函数：

$$\mathrm{Pr}(\mathbf{t}\mid \mathbf{x})=\exp \left(-\Vert \mathbf{x}-\mathbf{t}{\Vert }^2\right)$$

实际使用加权距离：

$$\mathrm{Pr}(\mathbf{t}\mid \mathbf{x})=\exp \left(-\sum _{k=1}^d{w}_k(x_k-t_k{)}^2\right)$$

其中 $\mathbf{w}=[w_1,...,w_d]$是特征权重向量。

最终Diverse Density公式：

$$\text{DD}(\mathbf{t},\mathbf{w})=\prod _{i:y_i=1}\left[1-\prod _{\mathbf{x}\in B_i^{+}}\left(1-e^{-{\sum }_k{w}_k(x_k-t_k{)}^2}\right)\right]\cdot \prod _{j:y_j=0}\left[\prod _{\mathbf{x}\in B_j^{-}}\left(1-e^{-{\sum }_k{w}_k(x_k-t_k{)}^2}\right)\right]$$

公式解释：

• 正包项：$1-\prod (1-p)$表示"至少一个实例接近$\mathbf{t}$"
• 负包项：$\prod (1-p)$表示"所有实例都远离$\mathbf{t}$"
• 指数项：距离越近，贡献越大；距离为0时概率为1
• 特征权重 $w_k$：自动学习各维度重要性

三、算法构建

3.1 优化策略

目标是最大化$\text{DD}(\mathbf{t},\mathbf{w})$，面临挑战：

• 非凸函数，存在多个局部极大值
• 搜索空间随维度指数增长

实用启发式技巧：

1. 初始化：从每个正实例启动梯度上升。直观理解：真实概念${\mathbf{t}}^{\ast }$附近的正实例会强烈贡献于DD峰值，从这些点出发易收敛到全局最优。
2. 梯度计算：对 $\log \text{DD}$求导，数值稳定性更好
3. 特征权重优化：交替优化 $\mathbf{t}$ 和 $\mathbf{w}$，或联合优化

3.2 特征权重学习

原始公式中 $\Vert \mathbf{x}-\mathbf{t}{\Vert }^2$假设各特征同等重要。实际中需学习权重：

$$\mathrm{Pr}(\mathbf{t}\mid \mathbf{x})=\exp \left(-(\mathbf{x}-\mathbf{t}{)}^T\text{diag}(\mathbf{w})(\mathbf{x}-\mathbf{t})\right)=\exp \left(-\sum _{k=1}^d{w}_k(x_k-t_k{)}^2\right)$$

优化后通常少于一半特征获得非零权重，搭建自动特征选择。权重越大，该维度上距离惩罚越严格。

3.3 扩展到麻烦概念

单点假设过强。Diverse Density可自然扩展到析取概念（disjunctive concept）：

$$\text{DD}({\mathbf{t}}_1,{\mathbf{t}}_2,\mathbf{w})=\prod _{i:y_i=1}\max \left\{\mathrm{Pr}(B_i^{+}\mid {\mathbf{t}}_1),\mathrm{Pr}(B_i^{+}\mid {\mathbf{t}}_2)\right\}\cdot \prod _{j:y_j=0}\left[\mathrm{Pr}(B_j^{-}\mid {\mathbf{t}}_1)\cdot \mathrm{Pr}(B_j^{-}\mid {\mathbf{t}}_2)\right]$$

即正包可被任一概念点解释，负包必须同时远离所有概念点。

四、实验

4.1 合成数据集

实验设计：

• 5个正包 + 5个负包，每包50个实例
• 实例从 $[0,100]\times [0,100]$均匀随机采样
• 真实概念：中心5×5正方形区域
• 标记规则：若包中至少一个实例落入正方形则标记为正

结果对比：

• 普通密度（图3a）：正负实例叠加后密度分布平滑，峰值不明显，难以定位
• Diverse Density（图3b）：在目标区域出现尖锐全局峰值，显著优于普通密度

关键发现：正负包来自相同底层分布，仅在高Diverse Density区域有差异，验证了方法对分布重叠挑战的有效性。

4.2 Musk药物活性资料集

数据集特性：

• Musk-1：较小，分子数和每分子实例数较少
• Musk-2：较大，更多构象采样
• 每个实例：166维特征向量（描述分子表面形状）
• 任务：预测分子是否具有"麝香"气味

实验协议：

1. 随机保留1/10作为测试集
2. 训练集上从每个正实例启动梯度上升
3. 通过留一法确定最优距离阈值
4. 测试时：若包中存在实例与${\mathbf{t}}^{\ast }$的加权距离小于阈值，则判为正

性能对比（20次运行平均）：

Musk-1数据集	准确率	Musk-2数据集	准确率
iterated-discrim APR*	92.4%	iterated-discrim APR*	89.2%
GFS elim-kde APR	91.3%	MULTINST	84.0%
Diverse Density	88.9%	Diverse Density	82.5%
MULTINST	76.7%	GFS elim-kde APR	80.4%

*注：iterated-discrim APR参数调优使用了测试集信息，属于性能上界

分析：Diverse Density无需参数调优即可达到与先进方法相当的效果，且自动将约50%特征权重置零，实现隐式特征选择。

4.3 人物图像识别

问题设定：从标记"包含目标人物"的图像中学习人物描述。

多实例转化：

• 每幅图像视为一个包
• 对图像采样54个子图像（不同位置/尺度）作为实例
• 正包：至少一个子图像包含目标人物
• 负包：所有子图像都不囊括目标人物

实例表示：将子图像分三层（头、躯干、腿），每层提取主导颜色，形成紧凑颜色特征。

结果：即使训练图像中始终包含两人（目标人物+干扰者），算法仍能学习到目标人物的稳定描述（图4）。该方法后续扩展至自然场景分类与图像检索。

4.4 股票基本面分析

业务洞察：月度高收益股票中，仅少数因基本面优良，多数为随机波动。

多实例建模：

• 正包：每月收益率最高的100只股票（假设至少一只基本面驱动）
• 负包：每月收益率最低的5只股票（全部非基本面驱动）
• 实例：17维特征向量（动量、市盈率、市净率等）

实验设计：

• 内容：1978-1997年600只美股，GMO公司献出
• 协议：5次运行，每次用10年资料训练，下1年数据测试

结果（按与${\mathbf{t}}^{\ast }$距离分十组）：

• 第一组（最近）：平均收益显著为正，超越GMO基准预测器
• 第十组（最远）：平均收益显著为负，低于基准
• 单调性：收益随距离单调递减，验证概念有效性

五、总结

本文首次将多实例学习形式化为概率密度最大化问题，提出Diverse Density度量；并基于Noisy-OR和梯度上升的实用优化方法，承受自动特征权重学习；这一方法对包内高噪声率、特征冗余、分布重叠等问题表现稳健，在药物发现领域，计算机视觉、金融分析等场景都实验验证了有效性。