【Muti-instance Learning】论文Multi-instance multi-label learning with application to scene class.（2006）

Z.-H. Zhou and M.-L. Zhang. Multi-instance multi-label learning with application to scene classification. In: Advances in Neural Information Processing Systems 19 (NIPS’06) (Vancouver, Canada), B. Schölkopf, J. C. Platt, and T. Hofmann, eds. Cambridge, MA: MIT Press, 2007, pp.1609-1616.

Abstract

  在本文中，我们对多实例多标签学习进行了形式化，其中每个训练示例不仅与多个实例相关，而且与多个类标签相关联。在许多实际任务中可能会发生这种问题，例如图像通常包含多个补丁，每个补丁都可以由特征向量描述，并且图像可以属于多个类别，因为可以用不同的方式识别其语义。我们分析了多实例多标签学习与传统监督学习，多实例学习和多标签学习的学习框架之间的关系。然后，我们提出了MIMLBOOST和MIMLSVM算法，它们在场景分类的应用中具有良好的性能。

1 Introduction

  在传统的监督学习中，对象由实例（或特征向量）表示并与类标签关联。正式地，让X代表实例空间（或特征空间），让Y代表类标签的集合。然后的任务是从给定的数据集{（x1，y1），（x2，y2），···，（xm，ym）}中学习一个函数f：X→Y，其中xi∈X是一个实例， yi∈Y是xi的已知标记。
  尽管上面的形式化是普遍的并且成功的，但是存在许多现实世界中的问题并不能很好地适合此框架，在现实世界中，现实世界的对象可能同时与多个实例和多个标签关联。例如，一个图像通常包含多个补丁，每个补丁可以由一个实例表示，而在图像分类中，这样的图像可以同时属于多个类别，例如图像。图像既可以属于山脉，也可以属于非洲。另一个示例是文本分类，其中文档通常包含多个部分，每个部分都可以表示为一个实例，并且如果从不同的角度（例如，从不同的角度来看），则可以将该文档视为属于不同的类别。文件可以归类为科学小说，朱尔斯·韦恩（Jules Verne）的著作，甚至是旅行书籍。 Web挖掘是另一个示例，其中每个链接都可以视为一个实例，而网页本身可以被识别为新闻页面，体育页面，足球页面等。
  为了解决此类问题，本文将多实例多标签学习（简称为MIML）形式化。在此学习框架中，一个训练示例由多个实例描述，并与多个类标签关联。正式地，让X表示实例空间，让Y表示类标签的集合。然后的任务是从给定的数据集{（X1，Y1），（X2，Y2），···，（Xm，Ym）}中学习一个函数fM IM L：2X→2Y，其中Xi⊆X是一个集合实例{x（i）1，x（i）2，···，x（i）ni}，x（i）j∈X（j = 1,2，···，ni）和Yi⊆ Y是一组标签{y（i）1，y（i）2，···，y（i）li}，y（i）k∈Y（k = 1,2，···，li） 。这里用Xi表示实例数，用Yi表示标签数。
  在分析了MIML与传统监督学习，多实例学习和多标签学习的框架之间的关系之后，我们提出了两种MIML算法，即MIMLBOOST和MIMLSVM。在场景分类中的应用表明，解决MIML框架中的一些实际问题比解决现有框架（如多实例学习和多标签学习）中的问题要好。

2 Multi-Instance Multi-Label Learning

  我们首先研究MIML与传统监督学习，多实例学习和多标签学习的框架之间的关系，然后开发一些解决方案。
  多实例学习[4]研究了由多个实例描述的真实对象与一个类标签相关联的问题。形式上，任务是从给定的数据集{（X1，y1），（X2，y2），…，（Xm，ym）}中学习函数fM IL：2X→{−1，+ 1}，其中Xi⊆X是一组实例{x（i）1，x（i）2，···，x（i）ni}，x（i）j∈X（j = 1,2，··· ，ni），yi∈{-1，+ 1}是Xi的标签。1多实例学习技术已成功应用于包括场景分类在内的各种应用程序[3，7]。
  多标签学习[8]研究了一个实例描述的现实世界对象与多个类标签相关联的问题。形式上，任务是从给定的数据集{（x1，Y1），（x2，Y2），··，（xm，Ym）}中学习一个函数fM LL：X→2Y，其中xi∈X是一个实例和Yi⊆Y的一组标签{y（i）1，y（i）2，···，y（i）li}，y（i）k∈Y（k = 1,2，··· ，li）.2多标签学习技术也已经成功地应用于场景分类[1]。
  实际上，多元学习框架是由代表真实世界对象的模棱两可产生的。多实例学习研究输入空间（或实例空间）中的歧义，其中对象具有许多替代输入描述，即实例；多标签学习研究输出空间（或标签空间）中的歧义，其中对象具有许多替代输出描述，即标签;而MIML同时考虑输入和输出空间中的歧义。我们在图1中说明了这些学习框架之间的差异。

  传统的监督学习显然是多实例学习的退化版本以及多标签学习的退化版本，而传统的监督学习，多实例学习和多标签学习都是MIML的退化版本。因此，我们可以使用多实例学习或多标签学习作为桥梁，通过在传统的有监督学习框架中确定MIML的等效性来解决它。
  解决方案1：使用多实例学习作为桥梁：我们可以将MIML学习任务（即学习功能fM IM L：2X→2Y）转换为多实例学习任务，即学习功能fM IL：2X ×Y→{−1，+ 1}。对于任何y∈Y，如果y∈Yi，则fM IL（Xi，y）= +1，否则为-1。可以根据Y ∗ = {y |argy∈Y[fM IL（X ∗，y）= +1]}确定新示例X ∗的适当标签。我们可以将此多实例学习任务进一步转换为传统的有监督学习任务，即在指定如何导出fM IL（Xi，y）的约束下学习函数fSISL：X×Y→{−1，+ 1}来自fSISL（x（i）j，y）（j = 1，···，ni）。对于任何y∈Y，如果y∈Yi，则fSISL（x（i）j，y）= +1，否则为-1。这里的约束可以是fM IL（Xi，y）= sign [Pni j = 1fSISL（x（i）j，y）]，已用于将多实例学习任务转换为传统的有监督学习任务[9] .3在这里也可以使用其他类型的约束。
  解决方案2：使用多标签学习作为桥梁：我们还可以将MIML学习任务（即学习功能fM IM L：2X→2Y）转换为多标签学习任务，即学习功能fM LL： Z→2Y。对于任何zi∈Z，如果zi =φ（Xi），φ：2X→Z，则fM LL（zi）= fM IM L（Xi）。可以根据Y ∗ = fM确定新示例X ∗的适当标签LL（φ（X ∗））。我们可以将该多标签学习任务进一步转换为传统的有监督学习任务，即学习函数fSISL：Z×Y→{−1，+ 1}。对于任何y∈Y，如果y∈Yi，则fSISL（zi，y）= +1，否则为-1。也就是说，fM LL（zi）= {y |argy∈Y[fSISL（zi，y）= +1]}。这里的映射可以通过构造聚类来实现，该聚类已用于将多实例包转换为传统的单实例[11]。注意，这里也可以使用其他类型的映射。

3 Algorithms

  在本节中，我们提出了两种解决MIML问题的算法：MIMLBOOST按照第2节中描述的第一个解决方案工作，而MIMLSVM按照第二个解决方案工作。

3.1 MIML BOOST

  给定任何集合Ω，让|Ω|表示其大小，即in中的元素数；给定任何谓词π，如果π成立，则[[π]]为1，否则为0；给定（Xi，Yi），对于任何y∈Y，如果y∈Yi，则令Ψ（Xi，y）= +1，否则让-1（-1），其中Ψ是函数Ψ：2X×Y→{−1，+ 1} 。表1给出了MIMLBOOST算法。
  第一步，将每个MIML示例（Xu，Yu）（u = 1,2，···，m）转换为| Y |的集合。多实例袋的数量，即{[（Xu，y1），Ψ（Xu，y1）]，[（Xu，y2），Ψ（Xu，y2）]，···，[（Xu，y | Y |），Ψ（Xu，y | Y |）]}}。请注意，[（Xu，yv），Ψ（Xu，yv）]（v = 1,2，···，| Y |）是标记的多实例袋，其中（Xu，yv）是包含数量为的袋。实例，即{（x（u）1，yv），（x（u）2，yv），··，（x（u）nu，yv）}和Ψ（Xu，yv）∈{+1 ，−1}是这个袋子的标签。
  因此，原始MIML数据集将转换为包含m×| Y |的多实例数据集。袋数，即{[（X1，y1），Ψ（X1，y1）]，···，[（X1，y | Y |），Ψ（X1，y | Y |）]，[（X2， y1），Ψ（X2，y1）]，···，[（Xm，y | Y |），Ψ（Xm，y | Y |）]}}。令[[X（i），y（i）），Ψ（X（i），y（i））]表示这些m×| Y |的第i个。袋数，即（X（1），y（1））表示（X1，y1），···，（X（| Y |），y（| Y |））表示（X1，y | Y |），···，（X（m×| Y |），y（m×| Y |））表示（Xm，y | Y |），其中（X（i），y（i））包含实例个数，即{（x（i）1，y（i）），（x（i）2，y（i）），…，（x（i）ni，y（i））}。
  然后，可以从数据集中学习多实例学习函数fM IL，因为fM IM L（X ∗）= {y |argy∈Y（sign [fM IL（X ∗，y） ] = +1）}。在这里，我们使用MIBOOSTING [9]实现fM IL。
  
  

3.2 MIMLSVM

  
  

4 Application to Scene Classification

  数据集由2,000种自然场景图像组成，这些图像分别属于沙漠，山脉，海洋，日落和树木，如表3所示。一些图像来自COREL图像集合，而另一些则来自Internet。超过22％的图像同时属于多个类别。

4.1 Comparison with Multi-Label Learning Algorithms

  由于场景分类任务已通过多标签学习算法成功解决[1]，因此我们将MIML算法与已建立的多标签学习算法ADABOOST.MH [8]和MLSVM [1]进行了比较。前者是成功的多标签学习系统BOOSTEXTER的核心[8]，而后者则在场景分类中取得了出色的表现[1]。
  对于MIMLBOOST和MIMLSVM，每个图像都表示为由SBN方法生成的九个实例的包[7]。在这里，每个实例实际上对应于一个图像补丁，并且可以通过更好的图像补丁生成方法获得更好的性能。对于ADABOOST.MH和MLSVM，每个图像都表示为通过连接MIMLBOOST或MIMLSVM实例获得的特征向量。高斯内核LIBSVM [2]用于实现MLSVM，其中交叉训练策略用于构建分类器，而T-Criterion用于标记图像[1]。 MIMLSVM算法也使用高斯内核实现，而参数k设置为训练图像数量的20％。4请注意，MIMLBOOST步骤3a中使用的实例级预测变量也是高斯内核LIBSVM（默认参数）。
  由于ADABOOST.MH和MLSVM会进行多标签预测，因此此处比较的算法的性能是根据五个多标签评估指标进行评估的，如表4至表7所示，其中“↓”表示“越小越好”，而“↑”表示“越大越好”。这些评估指标的详细信息可以在[8]中找到。表中进行了十倍交叉验证，并在表中给出了“平均值±标准差”，其中每种算法获得的最佳性能都以粗体显示。请注意，由于在每个增强回合中，MIMLBOOST执行的操作都比ADABOOST.MH多，为公平起见，ADABOOST.MH使用的增强回合设置为MIMLBOOST使用的增强回合的十倍，因此它们的时间成本是可比的。

  比较表4到表7，我们可以发现MIMLBOOST和MIMLSVM明显比ADABOOST.MH和MLSVM好。令人印象深刻的是，显着性水平为.05的成对t检验显示，在所有评估指标上，MIMLBOOST的最差表现（5个助推回合）甚至比ADABOOST.MH的最佳性能（250个助推回合）还要好得多，并且就覆盖率而言，其性能明显优于MLSVM的最佳性能（γ= 2），同时在其余指标上具有可比性； MIMLSVM的较差性能（γ= .5）甚至可以与MLSVM的最佳性能相媲美，并且在所有评估指标上均明显优于ADABOOST.MH的最佳性能。这些观察结果证实，将场景分类任务规范化为要通过MIMLBOOST或MIMLSVM解决的MIML问题比将其规范化为要通过ADABOOST.MH或MLSVM解决的多标签学习问题更好。

4.2 Comparison with Multi-Instance Learning Algorithms

  由于场景分类任务已通过多实例学习算法成功解决[7]，因此我们将MIML算法与已建立的多实例学习算法DIVERSE DENSITY [7]和EM-DD [10]进行了比较。前者是最有影响力的多实例学习算法之一，在场景分类中取得了出色的表现[7]，而后者在多实例基准测试中取得了出色的表现[10]。
  在这里，所有比较的算法都使用相同的输入表示。也就是说，每个图像都表示为由SBN方法[7]生成的九个实例的包。根据获得最佳性能的设置来设置DIVERSE DENSITY和EM-DD的参数[7，10]。如第4.1节所述实现MIMLBOOST和MIMLSVM算法，其中MIMLBOOST具有25个增强循环，而MIMLSVM则γ= .2。
  由于DIVERSE DENSITY和EM-DD可以进行单标签预测，因此根据预测精度（即测试集的分类精度）评估比较算法的性能。请注意，对于MIMLBOOST和MIMLSVM，排名最高的类别被视为单标签预测。进行了十倍交叉验证，表8中给出了“平均值±标准差”，其中每个图像类别的最佳性能都以粗体显示。请注意，除了每个类别的预测准确性外，还显示了总体准确性，用“总体”表示。
  从表8中可以发现，MIMLBOOST在沙漠和树木的图像类上实现了最佳性能，而MIMLSVM在其余图像类上实现了最佳性能。总体而言，MIMLSVM实现了最佳性能。显着性水平为.05的成对t检验表明，MILMSVM的总体性能与MIMLBOOST相当，两者均明显优于DIVERSE DENSITY和EM-DD。这些观察结果证实，将场景分类任务规范化为要通过MIMLBOOST或MIMLSVM解决的MIML问题比将其规范化为要通过DIVERSE DENSITY或EM-DD解决的多实例学习问题更好。

5 Conclusion

  在本文中，我们将多实例多标签学习形式化，其中一个示例同时与多个实例和多个标签关联。尽管有一些调查与对象关联的替代输入描述或替代输出描述的歧义的著作，但这是同时研究这两种歧义的第一篇著作。我们表明，使用多实例学习或多标签学习作为桥梁，可以通过在传统的有监督学习框架中确定其等效性来解决MIML问题。所提出的算法MIMLBOOST和MIMLSVM在场景分类中的应用取得了良好的性能。一个有趣的未来问题是开发其他流行的机器学习算法的MIML版本。此外，仍然存在一个未解决的问题，即是否可以通过利用实例与标签之间的连接来直接解决MIML。发现实例和标签之间的关系也很有趣。通过弄清混合的联系，也许我们可以更深入地了解歧义。