一种新颖的多实例学习算法与应用

侯 勇，陈章宝，张傲林

(1.蚌埠学院 计算机工程学院，安徽 蚌埠 233030；2.蚌埠学院 电子与电气工程学院，安徽 蚌埠 233030；3.蚌埠学院 经济与管理学院，安徽 蚌埠 233030)

针对训练实例标签的不完全了解的问题，提出了多实例学习(MIL)作为监督学习的变体。在监督学习中，每个训练实例都分配离散或实际价值标签。相比之下，在MIL中，标签仅分配给实例包。在二进制情况下，如果包中至少有一个实例为正，则将此包标记为正；如果包中的所有实例均为负，则该包标记为负，包中各个实例上没有标签。MIL的目标是根据标记的包，将未标记的包或实例进行分类。

1 知识准备

MIL的研究源于预测药物分子活性水平的问题。 之后，提出了许多MIL方法，例如学习轴平行概念[1]，多样化密度[2]，扩展引文kNN[3]等。 它们已被应用于图像概念学习，文本分类及股票市场预测等。 学习轴并行概念学习算法[3]是为解决MIL问题而提出的一类算法。其思想是在特征空间中找到轴平行超矩形(APR)，使APR应包含每个正包中的至少一个实例，同时排除负包中的所有实例，以此来表示目标概念。文献[3]提出了三种算法来发现此APR，分别是“标准”算法，“由外而内”算法与“由内而外”算法。

期望最大化多样密度算法(EM-DD)，是将这种EM样式风格的方法与DD算法相结合。EM-DD从初始猜测概念点t(可以使用原始DD算法获取)开始，然后重复执行以下两个步骤：在 E 步骤中，使用概念t的当前假设，在给定生成模型的情况下，从每个包中选取最可能的实例;在 M 步骤中，通过最大化转换后的DD来估计新概念t′，在E步骤中，使用梯度搜索，并在选定的实例上定义此转换后的DD。然后，用新概念t′替换旧概念t，并重复两个步骤，直到算法收敛。通过删除原始DD算法中的noise-or(或softmax)部分，EM-DD将多实例问题转换为单实例问题，这有助于避免陷入局部最大值，而且能够大大降低优化函数和计算时间的复杂性。

扩展引文算法(citation-kNN)是k最近邻(k-NN)基础上，定义了包之间的距离-Hausdorff距离。是解决MIL问题的有效方法。最小的Hausdorff距离用作包级距离度量标准，Hausdorff距离定义为每个包中任意两个实例之间的最短距离。

(1)

其中A和B表示两个包，并且ai和bj是每个包中的实例。使用此包级距离，我们可以使用 k-NN 算法预测未标记包的标签。

用于解决MIL问题的支持向量机算法分为mi-SVM与MI-SVM。mi-SVM用于实例级分类，MI-SVM用于包级分类。mi-SVM 明确将标签实例标签yi作为未观察到的隐藏变量，受其包标签YI定义的约束。目标是在未知实例标签和线性或内核区分函数上共同最大化通常的实例裕量，如下所示：

mi-SVM

(2)

约束的第二部分强制实例标签和包标签之间的关系。相比之下，MI-SVM的目的是使包边距最大化，因此在正包的情况下，被定义为“最大正”实例的边距；在负包的情况下，被定义为“最小负”实例的边距，表示如下：

MI-SVM

(3)

st.∀I:YImaxiI(〈w,xi〉+b)≥1-ξI,ξI≥0

在MI-SVM中，每个包中只有一个实例很重要，因为它决定了包的边距，适用于仅涉及包标签的任务。mi-SVM适用于用户关心实例标签的任务。

用于解决MIL问题的多决策树(C4.5-M)扩展了C4.5决策树算法。C4.5-M将信息获取和熵的概念扩展到MIL框架中。假设S是属于u(S)个正包和v(S)个负包的实例集合，F是被视为分裂准则的特征，并且是特征F的值为v的实例的集合。扩展信息增益和熵定义为：

(4)

(5)

C4.5-M树生长的终止取决于u和v所测量实例的纯度。如果树叶下的所有实例都来自正包，则将其标记为正，否则标记为负。为了对包进行分类，其所有实例都通过多决策树传递。如果其中一个实例达到一个正叶子，则包被分类为正，否则将其标记为负。

传统的多实例学习算法是为离散输出而设计的，主要针对二进制类别标签。在实值MIL算法需要根据训练数据预测包的实值标签，其中训练数据包括标有实值输出的包与所有未标记的实例。典型的实值MIL算法包括实值DD算法，多实例回归与kNN等。

实值DD算法关键的修改是对P(t|Bi)估计，定义如下：

P(t|Bi)=(1-|li-Label(Bi|t)|)/Z

(6)

(7)

其中，包Bi的真实标签是li，它是[0,1]内的真实值，且没有大的损失，Z是归一化常数，Label(Bi|t)是概念点t收到的标签Bi。请注意，当Ii∈{0,1}时，这简化为标准DD算法，只能用于二进制标签设置的MIL问题求解。

多实例回归[4]假设数据和实值输出之间的线性模型，并加上均值为零的加性高斯噪声。它还假定每个包中只有一个主实例负责该包的实值标签。因此，该算法旨在找到超平面Y=Xa，使得

(8)

其中Xip是bag的主实例，L是一个误差函数，用于测量超平面的优劣，此超平面由关于实例的参数a定义。在不知道每个包的Xip情况下，该方法进一步假定主实例是“最适合”当前超平面的实例。在此假设下，超平面可以定义为：

(9)

L-误差函数可以采用多种形式，例如平方误差L(yi,Xij,a=(yi-Xija)2。由于上述方程公式中的内侧最小化，没有封闭形式的解，寻找最优超平面被证明是NP难问题。此处，使用类似期望最大化的方法查找当前超平面下每个包的主实例(E 步)，并且以交错方式用主实例拟合超平面(M 步)。

除上述方法外，还提出了其他几种MIL方法。例如，在文献[5]中揭示了MIL方法与其对应的监督学习方法之间的关系，如DD与贝叶斯分类器，并暗示，如果监督学习方法能够把区分实例集中转移到区分包上，则此方法也适用于解决MIL问题。文献[6]还建议使用集成方法(例如bagging)来组合多个MIL学习器。

2 多实例学习算法在图像分类检索中应用

多实例学习算法的应用广泛，主要应用领域包括图像检索分类，药物活性预测和文本分类。

最初MIL工作[7]的动机是确定药物分子能否与目标蛋白相结合，用于解决药物活性预测问题。文献[8]在提出的两个基准数据集-Musk1和Musk2上，通过将分子建模为包，其形状建模为包中的实例，应用MIL算法来学习分子的正确形状，确定结合，从而预测新分子能否与目标蛋白质结合。实验结果表明MIL方法明显优于常规的单实例监督学习方法，其原因在于后者没有考虑到MIL问题的多实例性质。

图像检索和图像分类成功的关键是能够识别图像中预期的目标对象。图像可能包含多个(可能是异构的)对象，这一事实使情况变得更加复杂。因此，如果对整个图像的全局描述过于粗糙，将无法实现良好的分类和检索精度。即使提供了相关图像，识别实例图像中的哪些对象是否相关仍然是监督学习设置中的一个难题。但是，此问题非常适合 MIL 设置：每个图像都可以看作是一包，分割出的片段被建模为实例，并且表示目标对象的概念点可以通过 MIL 算法学习。

在文献[9]和[10]中，应用MIL对基于内容的图像检索进行了一些初步研究工作。类似于文档，图像可以视为包含不同视觉对象的区域包。假设用户正在用图像检索系统搜寻目标对象，如果图像中只有一个区域具有目标对象，则图像将被视为相关，而其他区域可以是相关的或不相关的。因此，构建基于相关区域局部特征的图像分类器优于建立在相关图像全局特征上的图像分类器，尽管后者是当前大多数图像检索系统正在做的事情。由于很少提供区域供用户评估，因此区域上的标签是未知的。文献[10]为 MIL 算法提供了完美的应用，这有助于相关区域的识别，并构建一个性能更好的模型进行图像相关性的判断。

文献[11]将 Corel 图像库中的自然场景图片划分为大小固定的子图像，并使用DD算法将其分为语义类。在基于内容的图像检索中，文献[12]应用DD和EM-DD算法进行图像检索，并进行了比较。此项研究使用k均值分割算法来生成更有意义的图像区域，而不是将图像划分为固定大小的区域。遗憾的是，目前没有结论性的结果表明MIL方法优于传统方法。

3 DD算法的改进

作为解决多实例学习问题的基础通用框架-多样密度(DD)方法的主要思想是在特征空间中找到最佳概念点，该概念点至少靠近每个正包中的一个实例，并且同时远离负包中的实例。 最佳概念点定义为具有最大多样性密度的概念点，用于衡量在该点附近有多少个不同的正包，以及负实例离该点的距离。

(10)

通过进一步假设，包在给定概念点t的条件下是独立的，这分解为：

(11)

在统一的先验假设下，再次使用贝叶斯规则，这等效于：

(12)

这就是“多样化密度”的一般定义。 鉴于包的布尔标签(例如正包标签是1，负包标签是0)是其实例标签的“逻辑”或运算结果，可以使用noise-or模型实例化：

(13)

(14)

(15)

其中非负比例因子Wk反映了不同特征的相关程度。 在没有针对上述最大化问题的近似形式解决方案的情况下，可使用梯度上升方法在特征空间中，搜索具有(局部)最大多样化密度的概念点。 通常，使用每个正包中的实例作为起点来重复搜索。

DD已被广泛用于解决各种MIL问题。 比如应用于药物活性估计，自然场景分类和图像检索等。目前，已经提出了DD方法的多个扩展，其中之一旨在学习比单点更复杂的概念。 例如，可以通过最大化以下内容来学习两分类概念：

(16)

本文通过引入核密度估计，改进DD算法。核密度估计定义如下。

核密度估计：令{xi∈Rd}i=1,…,N为一组从未知概率密度函数(pdf)f(x)提取的样本，独立且分布均匀，则其密度估计为[13]：

(17)

KDE通过使用所谓的核函数K(·)分别对样本加权来概括直方图。 与使用离散条柱块的直方图相比，KDE函数的连续性有助于简化数学分析。 此外，如果核函数是可微的，则可以识别局部模式(高密度区域)，而无需评估pdf的整体格局情况。这种方法已经直接应用于聚类开发。

内核函数在估计质量中起着重要作用。 例如，Epanechnikov核由于其渐近性质，在渐进平均积分平方误差(AMISE)方面是最佳的，尽管它不可微。

根据核函数的定义，一旦核函数的数学形式固定，带宽矩阵H就是影响KDE平滑度的参数。 在一维空间中，剩余模式很少的情况下，较小的带宽会导致KDE出现许多局部峰值，而较大的带宽会平滑细节。 已经开发了制定准则，用以指导最佳带宽的选择。 例如，除了上面提到的AMISE，另一种常用的度量是最小均方平方误差，定义如下。

(18)

然而，由于f(x)在实践中总是未知的，因此直接使用这种标准是令人望而却步的。因此，已经开发了许多数据驱动方法，能够根据给定的样本选择经验性的“好”H。

如果H不是固定的，而是允许其适应数据分布而变化，则该方法称为自适应核密度估计(AKDE)。 可变H的灵活性既可以减少稀疏区域中平滑不足的方差，也可以减少稠密区域中平滑过度的方差，这是固定H的常见问题。实现此目标的想法非常简单： 将小窗口用于密集区域，而在稀疏区域，用大窗口。在这种情况下，k-NN是一种常用的策略，以使H适应分布的局部密度。从形式上讲，使用k-NN策略的AKDE可以写成

(19)

其中，用x到第k个最近邻居的距离动态确定Hx。显然，k越大，估计值越平滑。改进DD算法的框架如下所示。

(20)

其中

(21)

(22)

(23)

(24)

(25)

公式(20)是目标函数定义，公式(22)是正包核密度估计，公式(23)是负包核密度估计，公式(24)是，公式(25)是高斯核，同时公式(25)也是实例包的Euclidean距离。

(26)

(27)

(28)

实例包的Euclidean距离定义为

dist(x,Bi)=minbi,j∈Bi{‖x-bi,j‖2}

(29)

整合公式(21)与公式(27)、(28)，可得出x处正包的改进的多样性密度估计(iDD)由边界局部决定，该边界包含至少每个正包中的一个实例。 在存在多个子概念的情况下，iDD仍会生成正确的估计，每个估计都对应于目标函数的局部最大值。

改进的DD算法iDD，包括iDD训练方法与iDD预测方法。

iDD训练算法过程如下所示。

输入：训练次数Nrun。用于训练的包B。标度S。

输出：目标分类度量T，长度与包的实例数量相同。标度矩阵S。函数极值fval。

采用信任区域(trust-region)[15]，顺序二次规划 (SQP)[16]与主动集算法(Active-Set)[17]方法对目标函数(20)，进行训练优化,得到最终结果。

(30)

最终训练结果可表示为公式(31)。

(31)

iDD预测算法过程如下所示。

输入：相关参数包括：阈值Θ，训练出来的分类目标矩阵T，待预测的包B={B1，B2，…，Bn}，一共n个包。标量矩阵S，集成方式ensemble，运行次数Nitera。

(2)依据下列公式(32)，预测第k个包的实例概率。

(32)

其中

(3)依据下列公式(33)，预测第k个包的实例标签。

(33)

其中

Θ={θ，θ，…，θ}

(4)依据下列公式(34)，预测包的概率。

(34)

(5)依据下列公式(35), 预测包的实例标签。

(35)

预测出包的标签。其中第k个包的标签是该包实例标签的最大值。

4 图像检索实验

图像检索的目的就是根据用户所提供的样本从大量的图像数据集中检索出符合用户需要的相似性图像。随着用户检索要求的逐渐提高，使得检索的难度变大以及检索的侧重点有所改变。根据用户的需要，我们首先要处理图像，提取出图像的相关特征，然后使用多实例学习的方法训练，最后从大量的图像数据集中检索出目标图像(见图1)。

图1 图像检索流程

实验中，检索过程主要分为两个步骤:首先利用多样性密度算法学习目标概念；然后计算目标概念和测试数据集图像包中最相似实例间的距离，作为图像的相似度。

f1(x1,x2,x3,x4)=c1

(36)

f2=k1*x2+k2*x3+k3*x4=c2

(37)

f=f1+f2

(38)

其中，f是图像检索时间。x1是图像包的数量，x2是选择的图像数量，x3是图像包中的实例数量，x4是实例的维数。c1，c2，k1，k2，k3是大于0的常数。由于f1与f2都是固定的，所以检索时间f也是固定的。

通过公式 (36)、(37)、(38)分析可知，检索时间是固定的，与检索精确度无关。检索时间与检索精确度之间没有必然的关联性,检索时间减少并不一定意味着检索精确度会下降，两者是相对独立的不同的性能指标。

实验采用Corel图像库，Corel图像库在图像检索领域中很流行。具体而言，我们执行三个检索任务，对“汽车”、“蜥蜴”和“落日”的图像进行检索分类。对于每个任务，所用的测试数据集包含200张图像，其中相关图像100张，另外100张图像不相关。使用Blobworld系统[18]将所有图像分割为一组区域，对每个区域的颜色、纹理和形状特征，提取一个 320维特征向量进行表示。分割后，每个检索任务的实例(区域)数分别为 1390、1319 和 1219。我们使用两种 MIL 算法：mi-SVM 和Citation-kNN，并将它们的性能与使用全局图像特征的标准SVM性能进行了比较。表1至表3报告了这些算法，在采用 10 倍交叉验证时的检索准确度。

表1 检索“蜥蜴”图像的算法性能比较

表2 检索“落日”图像的算法性能比较

表3 检索“汽车”图像的算法性能比较

如实验结果所示，在局部特征上运行的MIL算法与在全局图像特征上运行的SVM相比具有可比的性能。 具体来说，在“蜥蜴”数据集上，MIL算法的性能均优于SVM(单实例)的性能，但幅度不大，但在其他两个数据集上，MIL算法中的iDD算法所实现的精确度最高。 在不同的MIL算法中，除了iDD算法性能略高于mi-SVM算法，还发现具有线性核的mi-SVM也是此图像检索应用的不错选择，它可以在corel数据集上实现最高或接近最高性能。 尽管运行时间较长，但Citaton-kNN性能比mi-SVM稍差。

5 结论

多实例学习自正式推出以来，已获得适度普及。许多受监督的学习方法已针对 MIL 设置进行了调整或扩展。MIL在经验上证明是成功的标签模糊性学习问题，而退出受监督或半监督的学习方法是成功的。然而，它的持续成功取决于MIL作为主要选择的应用的重要性和受欢迎程度。在本文中，提出了改进的DD算法iDD，在图像检索数据集进行的实验，证明了iDD算法在图像检索应用中的优秀潜力。但是，图像检索实验仍受数据集的大小和种类以及所测试参数设置范围的限制。我们计划在未来的工作中，引进深度学习算法，以便在更多的图像检索应用中，取得更高的性能。