摘要

英文原文

In multi-instance learning, the training set comprises labeled bags that are composed of unlabeled instances, and the task is to predict the labels of unseen bags. This paper provides a survey on this topic. At first, it introduces the origin of multi-instance learning. Then, developments on the study of learnability, learningal gorithms, applications and extensions of multi-instance learning are reviewed. In particular, this paper employs a unified view to look into multi-instance learning algorithms. Some important issues to be addressed are also discussed

Keywords: Learning from Examples; Multi-Instance Learning; Supervised Learning

翻译

在多实例学习中，训练集包括由未经标签的 instances 组成的有标签 bags ，并且训练任务 是去预测未知 bags 的标签。这篇文章在这个课题进行了研究调查。首先，这篇文章介绍了 多实例学习的起源。然后，对多实例学习在可学习性、学习算法、应用和扩展等方面的研究进展 进行了综述。特别地，这篇文章使用一种统一的观点来研究多实例学习算法。一些需要被解 决的重要问题也被得到讨论。

文章信息

1. Author: Zhi-Hua Zhou
2. Title: Multi-Instance Learning: A Survey

文章框架

第一个部分为 Introduction 部分。首先引出介绍了机器学习的三种基本类别：supervised learning, unsupervised learning, and reinforcement learning。然后，对 multi-instance learning 诸如起源，训练数据及其特性和训练任务进行介绍。接下来，将 multi-instance learning 和机器学习的三种基本类别进行比较，并指出传统算法并不适用于解决 multi-instance learning 背景的问题。进一步，说明该算法发展的重要性和研究的必要性，也即本文目的。

第二个部分为 Drug Activity Prediction 部分，即介绍了 multi-instance 算法的起源。

第三个部分为 Learnability 部分。介绍了 multi-instance 算法的科学习性。

第四个部分为 Learning Algorithm 部分。介绍了除第二个部分提及的 APR 算法以外的 multi-instance 的五种算法的主要思想，其中这五种算法分别是 Diverse Density, Citation-kNN, ID3-MI, RIPPER-MI, and BP-MIP。

第五个部分为Application，介绍了 MIL 的相关应用。

第六个部分为 Extension 部分。首先，介绍了 MIL 在实数输出结果预测的相关情况。然后，点出了前面第四部分中算法应用场景与最初始问题 应用场景的不同，进一步规范 MIL 的定义。接下来，又对 multi-instance 问题进行分类。 最后，指出 multi-instance 可以作为命题和关系表征的关键、桥梁。

第七个部分为 Discussion 部分。首先，此处介绍了 multi-instance learning 发展的最 大问题，即可用于实验的真实数据集太少。然后，本文提及当前对传统算法调整得到 mult- instance learning 算法的发展成绩斐然，但仍需进一步提出问题易发展 MIL, 如怎么对未 标签 bags 中的 instance 进行数据标签。最后，对 MIL 进行一些讨论：MIL 在实数场景 中的应用、广义 MIL 的讨论，说明 MIL 的发展要同应用结合起来。

Drug Activity Prediction

在20世纪90年代中期，Dietterich 等人对药物活性预测这一问题上的研究催生出了 MIL。

1. 问题提出

在这项研究中，药物活性研究归为对分子的低能形状的研究。同一分子有不同低能形状， 当存在可以与目标领域紧密结合的低能形状时，该分子便可以作为药物。 Dietterich 等当时在进行研究时，只知道哪些分子可以作为药物，但并不清楚具体分子的哪种形状可以满 足目标。由此便提出了 MIL 的雏形：在这里，分子作为 bag，而分子形状作为 instance。

2. 数据获取

通过从同一位置射出的方向不同的162束射线，构造出分子的表面，所产生的162个参数以及 分子的其他参数便构成了分子的一种形状的特征向量，即得到了 instance 。

3. 算法提出

Dietterich 提出了三种 axis-parallel rectangle (APR) 算法以解决药物活性预测问题。
首先是 GFS elim-count APR 算法。该算法首先定义一个包围所有 positive bags 的 APR, 然后通过贪婪地逐步缩小 APR 直到得到只剩下 positive bags 的 APR。对于每个 negative bags 中的 instance, 该算法计算舍弃其所需要附带的舍弃所有 positive bags 的 instance 的数量，并每次选择舍弃最少的( negative bags 的) instance 进行剔除。
然后是 GFS kde APR 算法，该算法与 GFS elim-count APR 算法不同的地方在于，进行剔除 步骤时，该算法还多考虑了不同 positive bags 中被 APR 覆盖的instances 的数量：通过 使用损失函数控制剔除过程以使得每个 positive bags 中至少有一个 instance 得到保留在 APR 中。
最后是 iterated-discrim APR 算法。该算法首先使用 greedy backfitting 算法去识别一个 APR, 且每个 positive bags 中至少有一个 instance 保留在该 APR 中。然后，该算法使用 此 APR 进一步获得最有识别力的特征。最后，核密度估计被使用以进一步泛化模型。

Learnability

在 multi-instance learning 框架下的 ARP的 PAC-learnability 结论总结如下表：其中 $1-\varepsilon$和$\delta$表示 accuracy 和 confidence，$d$和$n$分别表示 APR 的维度和每个 bag 中的 instance 数量。同时，这里$\tilde{O}$表示对数项已经被包含。

Work	Sample complexity	Running time	Main assumptions
Long & Tan	$O(\frac{d^2n^6}{\varepsilon}\log\frac{nd}{\varepsilon\delta})$	$O(\frac{d^5n^{12}}{\varepsilon^{20}}\log^2\frac{nd}{\varepsilon \delta})$	independent instances, product distribution, $n$is constant
Auer et al.	$O(\frac{d^2n^2}{\varepsilon^2}\log\frac{d}{\delta})$	$\tilde{O}(\frac{d^3n^2}{\varepsilon^2})$	independent instances, $n$ is constant
Blum & Kalai	$\tilde{O}(\frac{d^2n}{\varepsilon})$	$\tilde{O}(\frac{d^3n^2}{\varepsilon^2})$	independent instances, $n$ is constant

这些工作丰富了计算机 learning 理论，展示了一些 multi-instance learning 算法设计的 insight。

Learning Algorithm

supervised learning 和 multi-instance learning 的主要区别是能否(较好地)识别instances。

目前大部分现存的 multi-instance learning 算法均是从 supervised learning algorithm 改进而得到的：将 supervised learning algorithms 的 focuses 从识别 instances 转移到 识别 bags。此处主要介绍检验了五种算法。具体详见：

Multi-Instance Learning: A Survey-Learning Algorithm

Application

在将 Multi-instance Learning 应用到实际中时，需要关注两个重点问题。第一个是合适的 multi-instance learning 的 algorithm 的选择。第二个是如何将现实问题转化为 multi-instance representation，即决定什么是 bag，什么是instance，我们称这些转化方法为 bag generators。 这两个问题后者更重要。
对于 multi-instance 的应用：$Maron$ 和 $Lozano-P\acute{e}rez$¹提出了两种应用： 一种是从一系列图片中对一个人进行简单的描述，另一种是股票的选择；$Maron$和$Ratan$ ²将 Diversity Density 应用到了 natural scene classification 这一 image understanding task 中；$Yang$和$Lonzano-P\acute{e}rez$³则扩展了 Diverse Density algorithm并将其 应用到了基于内容的图像检索问题中；Zhou等人⁴也应用 Diverse Density 到基于内容的 图像检索问题中，但他们同时发展了一种名字为 ImaBag 的 bag generator；最近，Zhou 等人⁵又应用 multi-instance learning 到一种特定的网页挖掘任务即 web index page recommendation 中去；multi-instance learning 也被应用到机器人控制中去⁶，具体为 landmark matching；此外，$Weiss$和$Hirsh$⁷提出了将 event prediction 转化为 multi-instance 问题，而$Ruffo$⁸也应用 multi-instance decision tree 到诸如 password checking, intrusion detection, network management等computer security 问题中。