一种基于多示例学习的新增类别检测方法

摘要

本发明公开一种基于多示例学习的新增类别检测方法，首先利用多示例学习中较为成熟的关键示例检测算法将多示例“包”中的关键示例抽取出来；之后，对于每个已知类别，将其对应的关键示例结合为一个“类别超包”，同时未被认定为关键示例的所有示例组成一个“元超包”；随后，包与超包之间的距离就可以通过后续的度量学习来确定。在实用阶段，对于已知类别的包，根据其距离最近的类别超包来判定其概念类别；而对于新增类别的包，由于不存在它对应的类别超包，距离它最近的超包则应为元超包，如此可以根据这一情形来判定其为新增类别。

说明书

技术领域

本发明涉及机器学习、应用技术，特别涉及多示例学习、新增类别监测技术、度量学习，是一种既可以对现有类别进行自动概念类别预测/分类，同时可对新增类别进行检测的鲁棒多示例学习算法。

背景技术

从样例中学习被认为是最有希望的机器学习途径。如果以训练样本的歧义性作为划分标准，则目前该领域的研究大致建立在三种学习框架下，即监督学习、非监督学习和强化学习。

监督学习通过对具有概念标记的训练例进行学习，以尽可能正确地对训练集之外的示例的概念标记进行预测。这里所有的训练样本都是有标记的，因此其歧义性最低。非监督学习通过对没有概念标记的训练例进行学习，以发现数据中隐藏的结构。这里所有的训练样本都是没有标记的，因此其歧义性最高。强化学习通过对没有概念标记、但与一个延迟奖赏或效用(可视为延迟的概念标记)相关联的训练例进行学习，以获得某种从状态到行动的映射。这里所有的训练样本都是有标记的，但与监督学习不同的是，标记是延迟的，因此强化学习的歧义性介于监督学习与非监督学习之间。

20世纪90年代中后期，研究者们在对药物活性预测问题的研究中，提出了多示例学习的概念。在此类学习中，训练集由若干个具有概念标记的“包”组成，每个包中包含若干没有概念标记的示例。若一个包中至少有一个示例隶属于某概念类别，则该包被标记为该类别；若一个包不属于某概念类别，则该包中的任意一个示例均不隶属该类别。通过对训练包的学习，希望学习系统尽可能正确地对训练集之外的包的概念标记进行预测。

与监督学习相比，多示例学习中的训练示例是没有概念标记的，这与监督学习中所有训练示例都有概念标记不同；与非监督学习相比，多示例学习中训练包是有概念标记的，这与非监督学习的训练样本中没有任何概念标记也不同；而与强化学习相比，多示例学习中又没有时效延迟的概念。更重要的是，在以往的各种学习框架中，一个样本就是一个示例，即样本和示例是一一对应关系；而在多示例学习中，一个样本(即包)包含了多个示例，即样本和示例是一对多的对应关系。因此，多示例学习中训练样本的歧义性与监督学习、非监督学习、强化学习的歧义性都不同，这就使得以往的学习方法难以很好地解决此类问题。由于多示例学习具有独特的性质和广泛的应用前景，属于以往机器学习研究的一个盲区，因此被认为是一种新的学习框架。

现有多示例学习算法的应用场景均是类别种类和数目固定的静态环境，而非概念类别可变的动态开放环境。如，在构建基于多示例学习的图像分类系统时，在训练阶段的数据集中仅包含“大象”、“狐狸”和“鸟”三种图像概念类别。而系统实用阶段则极可能出现新的图像类别，如“老虎”。此时，现有多示例学习算法只能简单的将属于新增类别的样例(如老虎的图片)错误地划分为已知类别的某一类(如“狐狸”)，这样就会使得系统在动态开放环境中失效。因此，多示例学习需要一种可对新增类别进行检测的鲁棒学习算法。

发明内容

发明目的：目前的多示例学习算法均只能对现有类别样例进行概念类别预测/分类，在有新增类别出现的场景下，现有算法只能将新增类别样例简单而错误的分为已知类别中的一种。针对上述问题，本发明首次提出并解决了多示例学习场景下的新增类别检测任务，将其形式化为一个度量学习的框架，并提出对应的多示例新类检测学习算法。具体来说，首先利用多示例学习中较为成熟的关键示例检测算法将多示例“包”中的关键示例抽取出来。这些所谓的“关键示例”就是指“包”中那些可以决定对应包的概念标记的示例。之后，对于每个已知类别，将其对应的关键示例结合为一个“类别超包”，同时未被认定为关键示例的所有示例组成一个“元超包”。随后，包与超包之间的距离就可以通过后续的度量学习来确定。其中，类别超包用于概念类别的分类，而元超包则用于新增类别的检测。在训练阶段，对于已知类的样例(包)，它有一部分关键示例在其对应的类别超包中，另外还有一部分示例在元超包中。但为了取得更好的分类判别能力，已知类的包与对应类别超包的距离应为最小，与元超包的距离次之，而与其它类别超包的距离应较大。在系统实用阶段，对于已知类别的包，可以根据其距离最近的类别超包来判定其概念类别；而对于新增类别的包，由于不存在它对应的类别超包，距离它最近的超包则应为元超包，如此可以根据这一情形来判定其为新增类别。

技术方案：一种基于多示例学习的新增类别检测方法，包括多示例学习分类模型训练步骤和分类模型预测步骤；

所述多示例分类模型训练步骤具体为：

步骤1.1，在现有的多示例数据上，利用已有的关键示例检测算法从每个多示例包X_i中抽取对应的关键示例；

步骤1.2，将隶属于同一概念类别的包所抽取出的关键示例组成“类别超包”S_c(c＝1,…,C)。另外，未被检测为关键示例的所有示例组成“元超包”S₀；

步骤1.3，定义包到超包的距离为：超包中的每个示例到包最短距离的加权和，其中，示例到包的最短距离为示例到包中示例的最小欧式距离，超包中每个示例的权重由度量学习根据训练数据训练而决定。所述超包既可以是类别超包，也可以是元超包。

步骤1.4，根据包到超包的距离，利用度量学习来学习所述权重。为了保证该系统有足够的分类判别能力和新类检测能力，在度量学习中需满足下列条件：(1)包到其对应类别超包的距离最小；(2)包到元超包的距离为第二小；(3)包到其它类别超包的距离大于前两者。在此基础上，进行模型的训练。

多示例分类模型预测步骤具体为：

步骤2.1，利用度量学习过程中得到的度量分别计算测试集中的多示例包到类别超包和元超包的距离；

步骤2.2，根据计算得到的距离判定测试集多示例包的概念类别。

所述从每个多示例包X_i中抽取对应的关键示例，具体为：根据多示例学习的假设，若包X_i隶属于概念类别c中，则X_i中至少有一个示例隶属c；若包X_i不隶属于概念类别c中，则X_i中任意一个示例都不隶属于c。在利用已有关键示例抽取算法后，包X_i中的示例即被分为关键示例(来指示包X_i的概念类别归属)和非关键示例。

所述将隶属于同一概念类别的包所抽取出的关键示例组成类别超包，具体为：在对同属于概念类别c的包抽取其关键示例后，将这些关键示例组成一个集合，记作其中为第i个关键示例，V_c为隶属于类别c的关键示例的数目，S_c即为概念类别c对应的类别超包。同样地，所有非关键示例组成的超包定义为元超包，记作其中为组成元超包的示例，即为元超包中第i个非关键示例。

所述包到超包的距离具体为其中V_k为超包S_k中的示例数目，C表示类别的个数，为在包X_i中的最近邻，表示超包S_k中的第v个示例，M_k为通过度量学习得到的参数(即从X_i到S_k的度量)。

所述度量学习来学习权重，是将包到超包的距离写作一个带约束的目标函数，通过传统交替优化的解法来求解得到所需参数。

所述在模型预测步骤中，利用训练过程中得到的分类器计算包到超包的距离，具体为：将在模型训练步骤中学习到的度量M_k带入即可得到包到各个超包的距离。

所述根据计算得到的距离判定测试集多示例包的概念类别，具体为：若包到某类别超包S_c的距离最近，则该包隶属于概念类别c；若包到元超包S₀的距离最近，则该包隶属于新增的概念类别。

有益效果：与现有技术相比，本发明所提供的利用构造超包和度量学习来判定已知类别多示例包同时检测新增类别的方法，在实施过程中能够充分利用有标记数据训练多示例学习分类器，适用于有新增类别出现的场景，可对已知类别多示例数据分类，同时可以检测新增类别。另外，在无新增类别出现的场景下，本发明所述方法仍可取得优良表现。

附图说明

图1为本发明实施例的多示例分类模型训练工作流程图；

图2为本发明实施例的多示例分类模型预测工作流程图。

具体实施方式

下面结合具体实施例，进一步阐明本发明，应理解这些实施例仅用于说明本发明而不用于限制本发明的范围，在阅读了本发明之后，本领域技术人员对本发明的各种等价形式的修改均落于本申请所附权利要求所限定的范围。

如图1-2所示，基于多示例学习的新增类别检测方法，包括多示例学习分类模型训练步骤和分类模型预测步骤；

如图1所示，所述多示例分类模型训练步骤具体为：

步骤1.1，在现有的多示例数据上，利用已有的关键示例检测算法从每个多示例包X_i中抽取对应的关键示例；“关键示例”就是指“包”中那些可以决定对应包的概念标记的示例。

从每个多示例包X_i中抽取对应的关键示例，具体为：根据多示例学习的假设，若包X_i隶属于概念类别c中，则X_i中至少有一个示例隶属c；若包X_i不隶属于概念类别c中，则X_i中任意一个示例都不隶属于c。在利用已有关键示例抽取算法后，包X_i中的示例即被分为关键示例(来指示包X_i的概念类别归属)和非关键示例。

步骤1.2，将隶属于同一概念类别的包所抽取出的关键示例组成“类别超包”S_c(c＝1,…,C)。另外，未被检测为关键示例的所有示例组成“元超包”S₀；

将隶属于同一概念类别的包所抽取出的关键示例组成类别超包，具体为：在对同属于概念类别c的包抽取其关键示例后，将这些关键示例组成一个集合，记作其中为第i个关键示例，V_c为隶属于类别c的关键示例的数目，S_c即为概念类别c对应的类别超包。同样地，所有非关键示例组成的超包定义为元超包，记作

步骤1.3，定义包到超包的距离为：超包中的每个示例到包最短距离的加权和，其中，示例到包的最短距离为示例到包中示例的最小欧式距离，超包中每个示例的权重由度量学习根据训练数据训练而决定。

所述包到超包的距离具体为其中V_k为超包S_k中的示例数目，为在包X_i中的最近邻，M_k为通过度量学习得到的参数(即从X_i到S_k的度量)，C表示类别的个数，表示超包S_k中的第v个示例。

度量学习来学习权重，是将包到超包的距离写作一个带约束的目标函数，通过传统交替优化的解法来求解得到所需参数。

步骤1.4，根据包到超包的距离，利用度量学习来学习所述权重。为了保证该系统有足够的分类判别能力和新类检测能力，在度量学习中需满足下列条件：(1)包到其对应类别超包的距离最小；(2)包到元超包的距离为第二小；(3)包到其它类别超包的距离大于前两者。在此基础上，进行模型的训练。

如图2所示，多示例分类模型预测步骤具体为：

步骤2.1，利用训练过程中得到的度量分别计算测试集中的多示例包到类别超包和元超包的距离；将在模型训练步骤中学习到的度量M_k带入即可得到包到各个超包的距离。

步骤2.2，根据计算得到的距离判定测试集多示例包的概念类别：若包到某类别超包S_c的距离最近，则该包隶属于概念类别c；若包到元超包S₀的距离最近，则该包隶属于新增的概念类别。