多示例学习是20世纪90年代由Dietterich等^[1]提出的，用于预测药物分子活性，其目的是判断药物分子是否为麝香分子。多示例学习是由监督学习算法演变出的一种方法，是机器学习的其中一个分支，但它与监督学习又有所区别。传统监督学习是学习一个一对一的映射关系，训练单元为图像，每一张图像具有一个分类标记。与此不同，多示例学习把一张图片看作一个包，通过图像切割方式把图像分为若干个内容区域，每一个内容区域看作一个示例。在多示例学习中，一个包含有多个示例，只有包的分类标签已知，而示例的分类标签未知。通过对这些数据的学习，建立一种多对一的映射。在传统监督学习中，一个示例对应一个分类标签；在多示例学习中，多个示例(即包)对应一个分类标签。在多示例学习中，如果一个包中有一个或以上的示例是正类别，这个包就被标记为正；只有当包中的所有示例都不是正类别，该包才会被标记为负。这与传统的监督学习、半监督学习和非监督学习不同，它是以多示例包为训练单元的学习问题，而以往的学习方法难以很好地解决此类问题。为此，多示例问题引起了国内外研究者的高度关注^[2-3]，多示例学习已经广泛地应用于药物活性分子预测^[4]、图像分类^[5]、目标追踪^[6]、文本分类^[7]、蛋白质家族预测^[8]等领域。

现有的多示例学习算法主要针对二分类学习问题，例如文献[2]提出了一种基于抗噪声的多任务多示例学习算法(Multi-task Multi-instance Anti-noise Learning, MtMiAnL) ，通过对多示例包中的示例进行加权处理，降低噪声数据在训练过程中的影响，并进行多任务处理。MtMiAnL算法分为多示例加权阶段和目标函数多任务化阶段，对多示例加权后的目标函数用支持向量机(Support Vector Machine, SVM) 进行学习，再从单任务学习环境扩展到多任务学习环境。文献[9]将Multipe-instance Learning(MIL)的约束引入SVM的目标函数中，以使分类风险最小化，再通过求解目标函数，得到分类超平面。其中，mi-SVM是示例层面的SVM算法，MI-SVM是包层面的SVM算法。mi-SVM算法给每个正包中的样本赋予一个伪标签，然后训练一个带多示例约束的SVM分类器。而MI-SVM算法是从每个正包中选出一个最有可能为正示例的示例代表正包，把这些示例和负包中的示例放在一起，训练SVM分类器。

但是，对于单分类方面的多示例学习算法的研究还比较少。单分类(One-Class Classification，OCC) 是机器学习领域一个重要的研究内容，常用的两种方法是单类支持向量机(One-Class Support Vector Machine，OCSVM) ^[10]和支持向量数据描述(Support Vector Data Description，SVDD) ^[11]。OCSVM算法是以传统SVM算法为基础提出的一种解决异常检测问题的核方法，其思想是将正常数据在高维特征空间中的像与原点以最大间隔分开，因为在训练集中没有任何异常数据的信息，因此将原点看作是异常数据的代表。SVDD则是在特征空间中使用最小超球将正常数据的像包围起来。文献[12]提出了Positive Multiple Instance (PMI) 算法解决了仅给定一组多示例包的情况下学习分类器的问题。该算法假设数据集中正包的正示例在很多方面都很相似，从而通过一分类支持向量机，在特征空间构建一个紧凑的正示例簇，负示例则位于这个正示例簇之外。PMI算法分为两步进行：训练和查询。训练步骤是将只用正包去训练模型的学习问题转化为一类分类问题得到分类器。如果包中示例级别标签未给出，PMI 算法将终止并输出模型；否则，转到查询步骤。查询步骤是从先前训练的分类器正面标记的示例中选择一个示例查询其标签。如果查询的示例为负，则移除分类器标记为“正”的示例并返回训练步骤；否则，PMI算法输出模型并终止。文献[13]提出Robust Principal Component Analysis (RPCA) 算法来解决单分类多示例问题。该算法是假设正示例在一个较低维度的子空间，而负示例位于具有较高维度的另一个子空间。在这个假设下，问题变成了从每个包中，挑出几个正示例，把所有示例作为一个整体组合成一个矩阵，然后学习一个低秩的正示例子空间模型，并采用k-均值迭代极小化的思想来求解一个近似解。

PMI和RPCA算法都是针对单个核的单分类多示例学习模型，但是没有考虑多示例问题。目前，还没有基于多核学习的单分类多示例学习算法的研究。相比单核学习，多核学习有更准确、更强大的映射能力或者分类能力。针对单核方法局限性的问题，在支持向量数据描述的基础上，本文提出了一种基于多核学习的单分类多示例算法(Multiple-kernel One-class Multiple-instance Learning Algorithm, MOML) 。该算法基于观测到的多个示例数据，将观测到的数据用不同的核函数进行映射。由于在多示例学习中，示例的标签在包中是未知的，采用一种迭代启发式算法对包中示例迭代更新，并训练分类器，尽可能使正示例包含在球体分类器中。

1 相关工作 1.1 多示例学习

多示例学习大体可以分为3类：基于示例的多示例学习方法^[9,14]、基于包的多示例学习方法^[9,15]和基于嵌入空间的多示例学习算法^[16]。基于示例的多示例学习方法把包中的不同示例当作训练单元，通过建立示例级别的分类器来对包的分类标签进行预测。与此不同，基于包的多示例学习方法把整个多示例包当作训练单元，直接建立包级别的分类器，对未知的多示例包进行预测。基于嵌入空间的多示例学习算法使用一种特征提取方法将每个示例转换为一个特征向量。然后，将每个示例的特征向量组合成一个示例向量。这些示例向量被送入一个嵌入器，以转换为低维度的嵌入向量。最后，使用一个分类器对这些嵌入向量进行分类，以确定它们属于正示例或负示例。本文方法属于基于示例的多示例学习方法，因此，下面将对该类方法中的经典算法——mi-SVM^[9]进行介绍。

假设有$ n $个多示例包$ \{\left({B}_{1},{Y}_{1}\right) ,\cdots ,{(B}_{n},{Y}_{n}) \} $，其中，$ {B}_{i} $表示第$ i $个多示例包，$ {Y}_{i}\in \{1,\mathrm{ }-1\} $表示$ {B}_{i} $的分类标签。每一个多示例包$ {B}_{i} $含若干个示例$ {\boldsymbol{x}}_{ij}(j\in {B}_{i}) $。这里，令$ {y}_{ij} $表示示例$ {\boldsymbol{x}}_{ij} $的分类标签。在多示例学习中，只有多示例包$ {B}_{i} $的分类标签$ {Y}_{i} $已知，而示例$ {\boldsymbol{x}}_{ij} $的分类标签$ {y}_{ij} $未知。mi-SVM 算法通过识别包中单个示例的分类标签，保证每个正包至少包含一个正示例，而负包所有示例都是负示例。mi-SVM 的目标函数可以写成如下形式。

$ \underset{\left\{{y}_{\mathit{ij}}\right\}}{\rm{min}}\underset{{\boldsymbol{\omega }},b,\xi }{\rm{min}}\frac{1}{2}{\|{\boldsymbol{\omega }}\|}^{2}+C\sum _{ij}{\xi }_{ij} ,$

$ {\rm{s}}.{\rm{t}}.\left\{ \begin{array}{l} {y}_{ij}(<{{{\omega }},{\boldsymbol{x}}_{ij}}>+b) 1-{\xi }_{ij},\forall {x}_{ij}\in {B}_{i}\\ \displaystyle\sum\limits_{j \in {B_i}}\frac{{y}_{ij}+1}{2}\geqslant1,\forall {Y}_{i}=1\\ \displaystyle\sum\limits_{j \in {B_i}}\frac{{y}_{ij}+1}{2}=0,\forall {Y}_{i}=-1\\ {\xi }_{ij}\geqslant0\end{array} \right. $

(1)

式中：$ \boldsymbol{\omega } $为权重向量，$ b $为偏差，$ C $为正则化参数，$ {\xi }_{i} $为示例的松弛变量。$ \displaystyle\sum _{i\in I}\dfrac{{y}_{i}+1}{2}\geqslant1 $表示是正包中至少有一个示例为正，而$ \displaystyle\sum _{j\in {B}_{i}}\dfrac{{y}_{ij}+1}{2}=0 $表示该包中所有示例都为负。

mi-SVM算法主要解决多示例学习的二分类问题，而且是单核学习方法，因此，本文将参考mi-SVM算法的基本思想，提出面向多核单分类的多示例学习算法。也就是说，根据初始化包中的正示例来优化目标函数以建立分类器。然后，根据上一步得到的分类器对包中正示例的标签进行更新。

1.2 多核学习

核方法^[17]是解决非线性模式分析问题的一种有效方法，但是在实际应用中，单一核函数构成的核机器并不能满足复杂的数据需求，考虑组合核函数以获得更好的结果是一种必然的选择。多核模型^[18-19]是一类灵活性更强的基于核的学习模型，将不同特性的多个核函数进行组合，就会得到包含各个单核函数的总体特性的多核函数。多核函数形成的方式让多核函数具有更加准确、更加强大的映射能力或者分类能力，特别是对于实际应用中样本数据具有比较复杂分布结构的分类、回归等学习问题，多核学习的优点非常明显。

在多核学习算法中，Localized Multiple Kernel Support Vector Data Description (LMSVDD) ^[20]算法是一种经典的单分类多核学习算法。假设有$ n $个正类样本${[\boldsymbol{x}}_{1},\cdots ,{\boldsymbol{x}}_{n}]$，其中，一个基核对应于一个映射函数，而且不同基核分配不同的权重，样本$\boldsymbol{x}$通过函数映射后可以表示为${\displaystyle\sum }_{p=1}^{m}{{\eta }_{p}\left({\boldsymbol{x}}_{i}\right) {\phi }_{p}(\boldsymbol{x}}_{i})$，其目标函数可以写成如下形式。

$\begin{split} &\qquad\qquad \underset{R,{\boldsymbol{a}},\xi ,{\eta }_{p}\left({\boldsymbol{x}}_{i}\right) }{\mathrm{m}\mathrm{i}\mathrm{n}}{R}^{2}+C{\displaystyle\sum }_{i=1}^{N}{\xi }_{i},\\ &{\rm{s}}.{\rm{t}}.\left\{ \begin{array}{l} \displaystyle\sum\limits_{p=1}^{m}{\|{\eta }_{p}\left({\boldsymbol{x}}_{i}\right) {\phi }_{p}\left({\boldsymbol{x}}_{i}\right) -{\boldsymbol{a}}\|}^{2}\leqslant{R}^{2}+{\xi }_{i}\\ {\xi }_{i}\ge 0,\forall i\in 1,\cdots ,n \end{array} \right. \end{split} $

(2)

式中：$ \boldsymbol{a} $为超球体的球心，$ R $为超球体的球体半径，$ {\xi }_{i} $为松弛变量。LMSVDD算法的决策函数是$ f\left(\boldsymbol{x}\right) = \mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}({{\left|\right|\eta }_{p}\left({\boldsymbol{x}}_{i}\right) {\phi }_{p}\left({\boldsymbol{x}}_{i}\right) -\boldsymbol{a}\left|\right|}^{2}-{R}^{2}) $，若 $ f\left(\boldsymbol{x}\right) \leqslant0 $返回值为1，说明$ \boldsymbol{x} $是一个正示例；若$ f\left(\boldsymbol{x}\right) > 0 $返回−1，表示$ \boldsymbol{x} $是负示例。

LMSVDD 算法解决了单示例分类的问题，构造最小的超球体来包围这些正示例，但是没有考虑多示例问题。在单示例学习中，一个示例对应一个标签。但在多示例学习中，只有包的标签是已知的，而示例的标签是未知的。因此，本文将支持向量数据描述(Support Vector Data Description, SVDD) ^[11]扩展到多核单分类多示例学习算法。采用包中示例迭代更新的方案，将最有可能的正示例包含在球体分类器中。首先，根据初始化包中的正示例来优化目标函数以此建立分类器。然后，根据上一步得到的分类器对包中的正示例的标签进行更新。

2 基于多核学习的单分类多示例算法 2.1 相关定义

为了便于描述本文算法(MOML) ，先引入相关的定义，假设一类多示例训练集包含$ n $个正包$ {\{B}_{1},\cdots ,{B}_{n}\} $，其中$ {B}_{\mathit{i}}(i=1,\cdots ,n) $表示训练集中的第$ i $个包。每个包都有多个示例，其中$ {\boldsymbol{x}}_{ij} $代表第$ i $个包中的第$ j $个示例。在MOML算法中，训练集只有正类包，每个正包中至少有一个是正示例，且包中示例的标签是未知的。假设包中每个示例可以由$ m $个特征表示，例如：示例$ \boldsymbol{x} $可表示为$ [{\boldsymbol{x}}^{1},{\boldsymbol{x}}^{2},\cdots ,{\boldsymbol{x}}^{m}] $。每个特征通过映射函数$ {\phi }_{p}\left(\boldsymbol{x}\right) (p=1,\cdots ,m) $映射到特征空间。

针对多核支持向量数据描述算法^[21-22]也无法对多示例数据进行学习的问题，本文通过约束条件的引入，结合支持向量数据描述提出了多核单分类多示例学习算法，该算法是将多个示例数据通过多个不同的核函数多核映射到特征空间，在特征空间中通过支持向量数据描述算法构建球形分类器，其目标函数可以写成如下形式。

$\begin{split} &\qquad\qquad \underset{{\xi }_{\mathit{ij}}\ge 0}{\rm{min}}{R}^{2}+C \displaystyle\sum\limits_{i=1}^{n}\sum\limits_{j\in {B}_{i}}{U}_{ij}{\xi }_{ij},\\ &{\rm{s}}.{\rm{t}}.\left\{ \begin{array}{l} {R}^{2}-{\bigg\|\displaystyle\sum\limits_{m=1}^{p}{\phi }_{m}({\boldsymbol{x}}_{ij}) -\boldsymbol{a}\bigg\|^{2}}\geqslant{\xi }_{ij}\\ \displaystyle\sum\limits_{j\in {B}_{i}}{U}_{ij}=1,\;{U}_{ij}\in \left\{\mathrm{0,1}\right\},\;j\in {B}_{i} \end{array} \right. \end{split} $

(3)

式中：$ \boldsymbol{a} $为超球体的球心，$ R $为超球体的球体半径，$ C $为正则化参数，$ {\xi }_{ij} $为松弛变量；$ m $为第$ m $个基核，p为基核的数量，$ {U}_{ij} $为第$ i $个包中的示例$ {\boldsymbol{x}}_{ij} $是否为正示例，$ {\xi }_{ij} $为示例$ {\boldsymbol{x}}_{ij} $的训练误差。

2.2 优化过程

式(3)构建了一个球心为$ \boldsymbol{a} $，半径为$ R $的超球体，首先，最小化球半径$ {R}^{2} $，表示该超球体应该尽量紧密。其次，在式(3)的第1个约束中，$ {\phi }_{m}\left({\boldsymbol{x}}_{ij}\right) $是示例$ {\boldsymbol{x}}_{ij} $在第$ m $个基核上的特征映射。可以看出，这里使用了示例$ {\boldsymbol{x}}_{ij} $在$ p $个基核上的特征映射之和，即$ {\displaystyle\sum }_{m=1}^{p}{\phi }_{m}\left({\boldsymbol{x}}_{ij}\right) $，表示$ {\boldsymbol{x}}_{ij} $的最终特征映射。因此，第1个约束的含义为，示例$ {\boldsymbol{x}}_{ij} $在$ p $个基核上的特征映射之和，应包含在超球体里面。其次，在式(3)的第2个约束中，$ {U}_{ij}\in \left\{\mathrm{0,1}\right\} $为未知量，表示了示例$ {\boldsymbol{x}}_{\mathit{i}\mathit{j}} $是否为正示例。如果$ {U}_{ij}=1 $成立，则意味着这个示例$ {\boldsymbol{x}}_{ij} $为正示例。如果$ {U}_{ij}=0 $，则表示该示例为负示例。根据多示例学习的定义，每一个正包都含有正示例，但是具体示例的分类标签未知。因此，第2个约束$ {\displaystyle\sum }_{j\in {B}_{i}}{U}_{ij}=1 $表示，每一个正包$ {B}_{i} $包含一个正示例。最后，可以使用训练所得的紧密超球体对未知包的分类标签进行判断。如果包中有示例落入超球体内，则该包为正包，否则该包为负包。

在式(3)中，$ \boldsymbol{a} $，$ R $，$ {\xi }_{ij} $和$ {U}_{ij} $为未知量。为了求解这些未知量，采用了迭代优化框架。首先，初始化包中的正示例，考虑了多核学习，通过多个核函数将示例映射到特征空间，在特征空间再建立一个包围正示例的最紧密的球体分类器。每个包都至少有一个正示例。包中具体的示例标签是不知道的。因此，首先初始化每个包中的正示例，并固定$ {U}_{ij} $的值。也就是说在每个包中随机选择一个示例作为正示例，并将其对应的$ {U}_{ij} $值设置为1。把这些正示例(即$ {U}_{ij}=1 $)组合成一个新集合$ {\boldsymbol{X}}_{\mathrm{p}\mathrm{o}\mathrm{s}}=\{{\boldsymbol{x}}_{1},\cdots ,{\boldsymbol{x}}_{n}\} $，其中$ {\boldsymbol{x}}_{1} $表示第1个包中的正示例。$ {\boldsymbol{X}}_{\mathrm{p}\mathrm{o}\mathrm{s}} $集合中正示例$ {U}_{ij} $的值为1，将包中其他示例的$ {U}_{ij} $值设置为0，这些就被认为是正包中的负示例。这样可以确保每个包至少有一个正示例。

若正包中示例的$ {U}_{ij} $值被确定，对正包中正示例构建分类器，对目标函数进行优化，得到能尽量包围$ {\boldsymbol{X}}_{\mathrm{p}\mathrm{o}\mathrm{s}} $集合的紧凑的正示例超球体。式(3)可以转化为关于$ R $，$ \boldsymbol{a} $，$ {\xi }_{i} $的凸优化问题。

$\begin{split} &\qquad\qquad \underset{{\xi }_{i}\ge 0}{\mathrm{m}\mathrm{i}\mathrm{n}}{R}^{2}+C\displaystyle\sum\limits_{{\boldsymbol{x}}_{i}\in {X}_{\mathrm{p}\mathrm{o}\mathrm{s}}}{\xi }_{i},\\ &{\rm{s}}.{\rm{t}}.\;{R}^{2}-{\bigg\|\displaystyle\sum\limits_{m=1}^{p}{\phi }_{m}\left({\boldsymbol{x}}_{i}\right) -\boldsymbol{a}\bigg\|^{2}}\geqslant{\xi }_{i},{\boldsymbol{x}}_{i}\in {\mathit{X}}_{\mathrm{p}\mathrm{o}\mathrm{s}} \end{split} $

(4)

利用Lagrange算法对式(4)求解得到

$\begin{split} &L\left(R,\boldsymbol{a},{\alpha }_{i},{\gamma }_{i},{\xi }_{i}\right) ={R}^{2}+C\displaystyle\sum\limits_{{\boldsymbol{x}}_{i}\in {\boldsymbol{X}}_{\mathrm{p}\mathrm{o}\mathrm{s}}}{\xi }_{i}-\displaystyle\sum\limits_{{\boldsymbol{x}}_{i}\in {\boldsymbol{X}}_{\mathrm{p}\mathrm{o}\mathrm{s}}}{\gamma }_{i}{\xi }_{i}-\\ &\qquad \displaystyle\sum\limits_{{\boldsymbol{x}}_{i}\in {{\boldsymbol{X}}}_{\mathrm{p}\mathrm{o}\mathrm{s}}}{\alpha }_{i}\left({R}^{2}+{\xi }_{i}-{\left\|\displaystyle\sum\limits_{m=1}^{p}{\phi }_{m}({\boldsymbol{x}}_{i}) -\boldsymbol{a}\right\|}^{2}\right) \end{split} $

(5)

式中：$ {\alpha }_{i}\geqslant0 $和$ {\gamma }_{i}\geqslant0 $为拉格朗日乘子，分别对$ R $，$ \boldsymbol{a} $，$ {\xi }_{i} $求偏导得到

$ \begin{array}{c}\displaystyle\sum\limits_{{\boldsymbol{x}}_{i}\in {{\boldsymbol{X}}}_{\mathrm{p}\mathrm{o}\mathrm{s}}}{\alpha }_{i}=1 \end{array} $

(6)

$ \begin{array}{c}{\boldsymbol{a}}=\displaystyle\sum\limits_{{\boldsymbol{x}}_{i}\in {{\boldsymbol{X}}}_{\mathrm{p}\mathrm{o}\mathrm{s}}}\sum\limits_{m=1}^{p}{\alpha }_{i}{\phi }_{m}\left({\boldsymbol{x}}_{i}\right) \end{array} $

(7)

$ \begin{array}{c}C-{\alpha }_{i}-{\gamma }_{i}=0 \end{array} $

(8)

将式(6)~(8)代入式(5)转换为对偶问题得到

$\begin{split} &\underset{\boldsymbol{\alpha }}{\mathrm{m}\mathrm{a}\mathrm{x}}\displaystyle\sum\limits_{{\boldsymbol{x}}_{i}\in {{\boldsymbol{X}}}_{\mathrm{p}\mathrm{o}\mathrm{s}}}\displaystyle\sum\limits_{m=1}^{p}{\alpha }_{i}\left\langle{{\phi }_{m}\left({\boldsymbol{x}}_{i}\right) ,{\phi }_{m}\left({\boldsymbol{x}}_{i}\right) }\right\rangle+\\ &\displaystyle\sum\limits_{\scriptstyle{{\boldsymbol{x}}_i} \in {{\boldsymbol{X}}_{{\rm{pos}}}}\atop \scriptstyle{{\boldsymbol{x}}_k} \in {{\boldsymbol{X}}_{{\rm{pos}}}}}\displaystyle\sum\limits_{m=1}^{p}{\alpha }_{i}{\alpha }_{k}\left\langle{{\phi }_{m}\left({\boldsymbol{x}}_{i}\right) ,{\phi }_{m}\left({\boldsymbol{x}}_{k}\right) }\right\rangle ,\\ &\qquad \mathrm{s}.\mathrm{t}.\displaystyle\sum\limits_{{\boldsymbol{x}}_{i}\in {{\boldsymbol{X}}}_{\mathrm{p}\mathrm{o}\mathrm{s}}}{\alpha }_{i}=1,C\geqslant{\alpha }_{i}\geqslant0 \end{split} $

(9)

式(9)包含内积$ \left\langle{{\phi }_{m}\left({\boldsymbol{x}}_{i}\right) ,{\phi }_{m}\left({\boldsymbol{x}}_{k}\right) }\right\rangle $，根据Mercer定理，$ {K}_{m}\left({\boldsymbol{x}}_{i},{\boldsymbol{x}}_{k}\right) =\left\langle{{\phi }_{m}\left({\boldsymbol{x}}_{i}\right) ,{\phi }_{m}\left({\boldsymbol{x}}_{k}\right) }\right\rangle $，式(9)将高维特征空间的内积运算转化为核函数运算得到

$ \begin{split} &\underset{\boldsymbol{\alpha }}{\mathrm{m}\mathrm{a}\mathrm{x}}\displaystyle\sum\limits_{{\boldsymbol{x}}_{i}\in {\boldsymbol{X}}_{\mathrm{p}\mathrm{o}\mathrm{s}}}\displaystyle\sum\limits_{m=1}^{p}{\alpha }_{i}{K}_{m}\left({\boldsymbol{x}}_{i},{\boldsymbol{x}}_{\mathit{i}}\right) +\\ &\displaystyle\sum\limits_{\scriptstyle{{\boldsymbol{x}}_i} \in {{\boldsymbol{X}}_{{\rm{pos}}}}\atop \scriptstyle{{\boldsymbol{x}}_k} \in {{\boldsymbol{X}}_{{\rm{pos}}}}}\displaystyle\sum\limits_{m=1}^{p}{\alpha }_{i}{\alpha }_{k}{K}_{m}\left({\boldsymbol{x}}_{i},{\boldsymbol{x}}_{k}\right),\\ & \mathrm{s}.\mathrm{t}.\displaystyle\sum\limits_{{\boldsymbol{x}}_{i}\in {\boldsymbol{X}}_{\mathrm{p}\mathrm{o}\mathrm{s}}}{\alpha }_{i}=1,C\geqslant{\alpha }_{i}\geqslant0 \end{split}$

(10)

训练完包围$ {\boldsymbol{X}}_{\mathrm{p}\mathrm{o}\mathrm{s}} $集合的紧凑的正示例超球体后，固定该分类器，对包中的正示例的标签进行更新。用上述求解得到的参数更新包中示例$ {U}_{ij} $的值，式(3)可以转化为

$ \begin{split} &{\rm{min}}\;\;C\displaystyle\sum\limits_{i=1}^{n}\displaystyle\sum\limits_{j\in {B}_{i}}{U}_{ij}{\xi }_{ij},\\ &\displaystyle\sum\limits_{j\in {{{B}}}_{i}}{U}_{ij}=1,{U}_{ij}\in \left\{\mathrm{0,1}\right\} \end{split} $

(11)

式(11)中，重新计算每个正包中离球心最近的示例。在每个包中选择误差最小的示例作为正示例。因为相比于同一个包中的其他示例，误差最小的示例更有可能是正示例。因此，离球心最近的示例作为正示例并将$ {U}_{ij} $的值设置为1，更新集合$ {\boldsymbol{X}}_{\mathrm{p}\mathrm{o}\mathrm{s}} $的示例，从而再构建分类器，不断迭代优化直至目标函数收敛。

当算法终止时，得到分类器。假设$ {\overline{B}}_{i} $是一个测试包，$ {\overline{\boldsymbol{x}}}_{ij} $是该包中的示例，这个包决策函数为

$f({\overline{B}}_{i}) = {\rm{sgn}}\; \underset{j\in {\overline{B}}_{i}}{\mathrm{m}\mathrm{i}\mathrm{n}}\left({R}^{2}-{\bigg\|\displaystyle\sum _{m=1}^{p}{\varPhi}_{m}({\overline{\boldsymbol{x}}}_{ij}) -\boldsymbol{a}\bigg\|^{2}}\right) $

(12)

在式(12)中，计算包$ {\overline{B}}_{i} $中的示例到超球体的最小距离，获取潜在正示例代表，从而可定位图像中的潜在对象位置；如果有$ f({\overline{B}}_{i}) \geqslant0 $，这个包预测为正包；否则，预测为负包。

综合上述分析，MOML算法的步骤如算法1所示。

算法1　MOML算法

输入：$ { {B}_{\mathit{i}}\left(i=1,\cdots ,n\right) ,C,\epsilon} $。

输出：$ { R,\boldsymbol{a},{U}_{ij}} $。

(a) 初始化每个包中的正示例，将示例组成一个新集合$ { {\boldsymbol{X}}_{\mathrm{p}\mathrm{o}\mathrm{s}}} $。

(b) 将 $ { {\boldsymbol{X}}_{\mathrm{p}\mathrm{o}\mathrm{s}}} $集合中正示例$ {{U}_{ij}} $的值设置为1，将包中其他示例的$ { {U}_{ij}} $值设置为0。

(c) 将已知约束代入式(3)，根据式(4)对目标函数进行优化解出$ {\mathit{\alpha },R,\boldsymbol{a}} $。

(d) 将$ { R,\boldsymbol{a}} $重新代入表达式(3)更新$ { {U}_{ij}} $。

(e) 根据$ {{U}_{ij}} $更新正示例集合$ { {\boldsymbol{X}}_{\mathrm{p}\mathrm{o}\mathrm{s}}} $

(f) 重复步骤2~5直至算法收敛。

3 实验结果 3.1 对比方法

由于没有关于多核单分类多示例学习的研究，为了说明算法的有效性，主要将MOML算法与KOCSVM^[23]、LMSVDD^[20]和PMI^[12]进行比较。

(1) KOCSVM是一种用于单示例的单核一分类方法，在非线性变换的特征空间中拟合一个紧超球体，以包含大多数目标示例。

(2) LMSVDD是一种用于单示例学习的多核一分类方法。为每个内核的输入空间的不同区域分配不同的权重，并使用加权核的组合来学习SVDD分类器。

(3) PMI是一种用于多示例的单核一分类方法，假设数据集中正包的正示例在很多方面都很相似，从而通过一分类支持向量机，在特征空间构建一个紧凑的正示例簇。

3.2 实验环境和实验数据

为了验证MOML算法的有效性，使用Corel、VOC 2007和Messidor数据集进行实验。程序运行的个人计算机配置为2.4 GHz，内存为32 GB，操作系统为Win 10，程序开发平台是MTALABR2018b，编程语言为Matlab。

Corel数据集是科雷尔(Corel) 公司收集整理的较为丰富的图像库，是多示例学习算法最常用的图像分类数据集。该数据集有20个类，其中包括花、大象和日落等。每个类有100张大小相等的图像，每个图像都视为一个包，每个图像分割成几个区域^[16]，其中每个区域视为一个示例。

VOC 2007数据集^[24]是计算机视觉挑战赛PASCAL VOC2007 (VOC 2007) 中的数据集。VOC 2007的数据集由9 963张图像和20个类别组成，其中，类别包括鸟、猫、狗、飞机等。这个数据集是一个多标签数据集，其中一些图像被标注不止一个标签。根据文献[25]的做法将其转换为单标签数据集，例如：在“鸟”这个标签分类中，通过选择数据集中所有带有“鸟”这个标签的图像作为正包，同时选择没有“鸟”的图像作为负包来进行分类。因此，可以获得20个单标签子数据集。与上述数据集类似，每个图像都被视为一个包，每一段都被视为一个示例。每个示例都是由1 764个维度表示。

Messidor数据集^[26]是对糖尿病视网膜病变筛查的一个图像分类数据集。该数据集由654名糖尿病患者和546名健康者的1 200张眼底图像组成。图像的原始大小介于1 440×960和2 304×1 536像素之间，如文献[25]中所述，实验中每个图像都被重新缩放为700×700像素。将每个图像分割为135×135像素，通过提取该像素的特征构造一个示例，属于同一诊断图像的一组示例被视为一个包。如果包中包含目标疾病，则包的标签为1，否则为−1。

3.3 实验设置

AUC(Area Under ROC Curve) ^[27]是机器学习领域中分类模型使用的主要离线评测指标之一，广泛应用于单分类学习算法的评价。因此，本文采用AUC作为模型的评价指标。AUC的计算公式为

$ \mathrm{A}\mathrm{U}\mathrm{C}=\frac{\displaystyle{\sum} _{i\in \mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{e}\mathrm{C}\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{s}}{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}}_{i}-\dfrac{M(1+M) }{2}}{M\times N} $

(13)

式中：$ {\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}}_{i} $为第$ i $个正样本在排序表中的序号，$\displaystyle{\sum}_{i\in \mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{e}\mathrm{C}\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{s}}{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}}_{i}$为正样本排列序号的加和，M和N分别为测试集中正样本的个数和负样本的个数。由公式可以看出，当正例在排序表中的序号越高时，计算所得的AUC值也越大。

实验使用10折交叉验证方法进行，衡量MOML算法的有效性和稳定性。在每次实验中，将多示例数据集平均分成10份，其中9份用做训练集，剩下的1份用做测试集。10份样本轮流作为测试集，算法重复执行10次，实验最终取10次验证的平均值为10折交叉验证的最终精度。

本文实验使用了高斯核。对于MOML算法和LMSVDD算法，其为多核学习算法，核参数进行线性平均采样，采样范围为$ {2}^{-7}s $和$ {2}^{7}s $，其中$ s $是成对距离的平均值；正则化参数在$ \{{2}^{-7},{2}^{-6},\cdots ,{2}^{6},{2}^{7}\} $中选择。对于KOCSVM算法，高斯核参数在$ \{-15,-10,-5,0,5, 1\mathrm{0,1}5\} $中选择，正则化参数在$ \{0.01,\mathrm{0.06,0.11},\cdots ,0.41\} $ 中选择。对于PMI算法，高斯核函数的参数在$ \{{2}^{-4}, {2}^{-3},\cdots ,{2}^{3},{2}^{4}\} $中选择，正则化参数在$ \{0.01,\mathrm{0.06}, \mathrm{0.11},\cdots , 0.41\} $中选择。

3.4 实验结果

如表1~3所示，MOML算法是针对多核多示例学习，实验结果比其他3个单分类算法(KOCSVM、LMSVDD和PMI) 的精度都高，验证了MOML算法的有效性。相比于KOCSVM和PMI，MOML运用多核方法更能适应于不同的数据分布，数据在新的组合空间中能够得到更加准确、合理的表达，比单核构建的分类器准确率高。相比于LMSVDD，MOML能更好地处理多示例数据集，分类正确率得到了保障。反观另外3种算法，它们都没有很好地保持分类准确率。因此，MOML在只使用正包的情况下，可以更好地挖掘图片的信息，大幅度减少人工标记示例的时间，降低标记带来的成本支出。

4 结论

本文在支持向量数据描述的基础上，提出了一种基于多核学习的单分类多示例学习算法，该算法采用迭代优化框架不断更新包中的正示例。在优化算法过程中，首先初始化包中的正示例，考虑了多核学习，将示例通过多个核函数映射到特征空间中，以建立球形分类器，然后根据所建立的分类器不断更新包中正示例的标签。在3个数据集上的对比实验证明本文所提出的算法比单核多示例方法具有更好的性能，准确率明显得到提高，有更优的泛化能力，这对多示例学习问题具有重要的意义。