一种基于非确定主动学习的多分类器训练方法及分类方法

摘要

本发明公开了一种基于非确定主动学习的多分类器训练方法及分类方法。本方法为：1)选取或初始化一多分类器；对未标注样本集中的每一样本，利用该多分类器计算该样本的总体信息量Info；所述总体信息量为：模型变更信息量与模型调优信息量之和；2)对该未标注样本集进行聚类，得到J个子类；3)从每个子类中选取总体信息量Info值最小的若干未标注样本；再从所选样本中选取K个样本进行标注后加入到已标注样本集L；4)将更新后的已标注集L作为训练数据重新训练该多分类器；5)迭代执行步骤1)～4)设定次数；然后利用最终得到的多分类器对未标注集进行分类。本发明实现样本信息量的综合评价，从而获得高效化、智能化的多分类器。

说明书

技术领域

本发明涉及一种基于非确定主动学习的多分类器训练方法及分类方法，属于软件工程技 术领域。

背景技术

数据分类一直是人们的研究热点，比如专利ZL 201010166225.6“一种基于在线学习的自 适应级联分类器训练方法”，专利ZL 200910076428.3“一种跨领域的文本情感分类器的训练 方法和分类方法”，专利ZL 200810094208.9“文档分类器生成方法和系统”。

在海量数据的分类问题中，“主动学习”(参考文献：McCallum and K.Nigam,“Employing  EM in pool-based active learning for text classification,”in Proc.of the 15th International  Conference on Machine Learning,1998,pp.350–358.)是一种高效利用专家标注的机器学习方 法，其主要思想是：由机器主动地、有针对性地选择最有信息的样本交给专家进行标注(向 专家提出查询)，从而在有限的样本标注量下获得尽可能大的分类性能提升，比如参考授权专 利：ZL 201210050383“基于主动学习和半监督学习的多类图像分类方法”；ZL 200810082814.9“用于使提升分类器适合于新样本的方法”。

在样本标注代价高且数量有限、而未标注样本多且易于获得的应用情境下，主动学习的 优势尤为明显。选择性采样策略是主动学习的关键环节。现有选择性采样策略大致包括以下 几种类型——(1)基于不确定度：将其当前模型最不确定如何进行分类的样本提交给专家标 注(参考文献：D.Lewis and W.Gale,“A sequential algorithm for training text classifiers,”In Proc. of the ACM SIGIR Conference on Research and Development in Information Retrieval,1994,pp. 3–12.)；(2)基于组合决策：从不同模型出发，采用投票模式，将分歧最大的样本提交给专 家标注(参考文献：H.S.Seung,M.Opper,and H.Sompolinsky,“Query by committee,”In Proc.of  theACM Workshop on Computational Learning Theory,1992,pp.287–294)；(3)基于期望误差 最小化：从决策理论出发，估计未标注样本被标注之后模型的期望误差，最终选择能够获得 最小期望误差的样本提交给专家标注(参考文献：Y.Guo and R.Greiner,“Optimistic active  learning using mutual information,”In Proc.of International Joint Conference on Artificial  Intelligence,2007,pp.823–829.)。

本发明文档的符号表示如下：样本用特征向量x表示；标注用y∈C^N＝{1,2,...,N}表示， 其中N表示类别数目；未标注集和已标注集分别用U和L表示；分类模型用后验概率表示，其中表示对应于已标注集L的N分类模型的参数。

传统主动学习方法中，类别数目N可以通过经验分析或先验知识预先获知，从而视为常 量，这类方法称为“确定主动学习”(DeterminateActive Learning，简称D-AL)。根据类别数目 的不同(N＝2或N>2)，相应的分类模型可以划分为两种——二分类(binary)和多分类 (multi-class)。二分类模型将样本分到两类中的一类，是一种被广泛研究和应用的基本分类 模型；多分类模型将样本分到多类中的一类，是二分类模型的一般化形式。多分类模型的构 建方式包括以下两种：

(1)一种直接的处理方法是将多分类模型转化为多个二分类模型。在训练阶段，针对每 个类别或每两个类别对，构建相应的二分类模型。在预测阶段，训练出的多个二分类模型通 过投票或融合的方式组合成一个总的分类模型。例如，对于每个类别c∈C^N，利用标注 y_c＝{0,1}指示样本x是否属于该类，逻辑回归可以用于二分类模型的构建：

$P(y_c=1|x;{\theta }_{L_c}^2)={\theta }_{{\theta }_{L_c}^2}\left(x\right)=\frac{1}{1+\exp (-{\left({\theta }_{L_c}^2\right)}^{T}x)}.$    公式(1)

最终的预测标注为后验概率最大的类别：

$y^{*}=\arg \underset{c\in C^N}{\max }P(y_c=1|x;{\theta }_{L_c}^2).$    公式(2)

(2)另一种处理方法将各类别综合考虑、统一建模。例如，给定样本x，softmax回归用 一个N维向量估计标注y取1～N中每一个值的概率，从而在一个统一的过程中同时对N个类别进 行建模：

$\left(\begin{array}{c}P(y=1|x;{\theta }_L^N)\\ P(y=2|x;{\theta }_L^N)\\ ...\\ P(y=N|x;{\theta }_L^N)\end{array}\right)=h_{{\theta }_L^N}\left(x\right)=\frac{1}{{\Sigma }_{i=1}^N\exp \left({\left({\theta }_L^N\right)}_i^{T}x\right)}\left(\begin{array}{c}\exp \left({\left({\theta }_L^N\right)}_1^{T}x\right)\\ \exp \left({\left({\theta }_L^N\right)}_2^{T}x\right)\\ ...\\ \exp \left({\left({\theta }_L^N\right)}_N^{T}x\right)\end{array}\right).$    公式(3)

由于样本属于各类的概率分布进行统一建模，结果具有直接可比性，向量中最大的元素对应 于最终的预测标注，因此该处理方法更加适用于多分类模型构建。

为了优化分类模型，传统的基于确定主动学习的多分类方法选取最有信息的样本提交给 专家进行标注，从而实现模型更新。最有信息样本的选取方法为：分别计算未标注集中每个 样本在标注后模型的期望误差，选取最小化期望误差的样本作为最有信息样本，公式化表示 如下：

$x_{D-\mathrm{AL}}^{*}=\underset{x\in U}{\arg \min }\underset{\tilde{y}\in C^N}{\Sigma }P\left(\tilde{y}\right|x;{\theta }_L^N)F(x,\tilde{y};{\theta }_L^N).$    公式(4)

其中，

$\left(\begin{array}{c}F(x,\tilde{y};{\theta }_L^N)=\underset{x_u\in U-x}{\Sigma }H\left(y_u\right|x_u;{\theta }_{L+(x,\tilde{y})}^N)\\ =\underset{x_u\in U-x}{\Sigma }(-\underset{{\tilde{y}}_u\in C^N}{\Sigma }P\left({\tilde{y}}_u\right|x_u;{\theta }_{L+(x,\tilde{y})}^N)·\log P\left({\tilde{y}}_u\right|x_u;{\theta }_{L+(x,\tilde{y})}^N))\end{array}\right).$    公式(5)

公式表示在给定现有模型参数和新标注样本的情况下，其它未标注样本x_u∈U-x的 信息熵之和；表示样本被标注之后新的已标注集。

根据公式选取出的最有信息样本通过人机交互的形式由专家进行标注，标注完成后 该样本从未标注集去除并加入已标注集。

对于基于确定主动学习的多分类方法，类别数目N事先已知，因而可以据此直接确定N分 类模型的形式，剩下的任务是通过确定主动学习选取和标注最有信息样本，从而在现有模型 框架下不断优化模型参数然而，在很多实际应用中，类别数目往往无法事先准确获知； 甚至在有些应用中，类别数目会随着时间推移不断变化。在上述情况下，类别数目N本身为 需要求解的变量，主动学习不仅需要优化现有模型参数同时还需要根据样本分布更新类 别数目N(即分类模型的形式)。

为表述清楚起见，本发明文档中将现有N分类模型下模型参数的优化称为“模型调 优”，将类别数目N的更新进而导致的模型重建称为“模型变更”。传统的基于确定主动学习的 多分类方法仅仅关注模型调优而忽略了模型变更，因此只适用于类别数目已知的应用场景； 而在类别数目不确定的情况下，基于确定主动学习的多分类方法局限于现有N分类模型下样 本信息量的评估，却无法准确描述和拟合样本数据的真实分布，从而无法实现分类性能的有 效提升。

发明内容

本发明的目的在于提供一种基于非确定主动学习的多分类器训练方法及分类方法，一方 面对样本在现有模型框架下优化模型参数的能力进行评估，另一方面对该样本引入新的类别 从而触发模型重建的可能性进行评估，通过综合考虑模型调优和模型变更两方面因素，实现 样本信息量的综合评价，从而获得高效化、智能化的海量数据分类模型。

1、所提供的基于非确定主动学习的多分类方法，分别从模型变更和模型调优两个方面度 量样本的信息量，一方面对样本在现有模型框架下优化模型参数的能力进行评估，另一方面 对样本标注为新的类别从而触发模型重建的可能性进行评估，通过综合两方面因素，实现样 本信息量的综合评价，按此评价标准选择信息量最大的样本进行标注，可以保证有限样本标 注量下分类效果的最优化，从而获得高效化、智能化的海量数据分类模型。

2、所提供的样本信息量计算方法，不仅考虑样本被标注为现有各类别的概率，而且考虑 样本被标注为新类别的概率，形成样本信息量的统一化、综合性计算方法。

3、所提供的基于聚类的样本批量选取方法，在对未标注集中样本进行聚类的基础上，批 量选取最有信息的样本集，在保证样本信息量的同时避免了信息冗余。

本发明的技术方案为：

一种基于非确定主动学习的多分类器训练方法，其步骤为：

1)选取或初始化一多分类器；对未标注样本集中的每一样本，利用该多分类器计算该样 本的总体信息量Info；所述总体信息量为：模型变更信息量与模型调优信息量之和；

2)对该未标注样本集进行聚类，得到J个子类；

3)从每个子类中选取总体信息量Info值最小的若干未标注样本；再从所选未标注样本中 选取K个样本进行标注后加入到已标注样本集L；

4)将更新后的已标注样本集L作为训练数据重新训练该多分类器。

一种基于非确定主动学习的多分类器分类方法，其步骤为：

1)选取或初始化一多分类器；对未标注样本集中的每一样本，利用该多分类器计算该样 本的总体信息量Info；所述总体信息量为：模型变更信息量与模型调优信息量之和；

2)对该未标注样本集进行聚类，得到J个子类；

3)从每个子类中选取总体信息量Info值最小的若干未标注样本；再从所选样本中选取K 个样本进行标注后加入到已标注样本集L；

4)将更新后的已标注集L作为训练数据重新训练该多分类器；

5)迭代执行步骤1)～4)设定次数；然后利用最终得到的多分类器对未标注集进行分类。

进一步的，所述模型变更信息量为：从该未标注样本集中选取一样本a并将该样本的标 注类别设定为新类别；然后利用该多分类器计算去除该样本a后的该未标注样本集关于该新 类别的信息熵，将该信息熵作为该样本a的模型变更信息量；所述模型调优信息量的计算方 法为：从该未标注样本集中选取一样本a并将该样本的标注类别设定为该多分类器中的一个 类别；然后利用更新后的该多分类器计算去除该样本a的该未标注样本集关于每个已有类别 的信息熵加权和，作为该样本a的模型调优信息量。

进一步的，计算所述模型变更信息量的方法为：首先根据具有N个类别训练数据的已标 注样本集L构建一个N+1多分类器；然后对于去除该样本a后的该未标注样本集中每一样本 x，将其不属于现有N个类别中任何一类的概率定义为该样本x属于第N+1个类别的概率； 然后利用该多分类器计算去除该样本a后的该未标注样本集关于该新类别的信息熵，作为该 样本a的模型变更信息量。

进一步的，计算所述模型变更信息量的方法为：首先根据具有N个类别训练数据的已标 注样本集L构建一个二分类器，其中，将现有N个类别合并为一个类别A，将现有N个类别 以外的其它类别归为另一类别B；然后对于去除该样本a后的该未标注样本集中每一样本x， 将其不属于现有N个类别中任何一类的概率定义为该样本x属于类别B的概率；然后利用该 多分类器计算去除该样本a后的该未标注样本集关于该新类别的信息熵，作为该样本a的模 型变更信息量。

进一步的，计算所述模型变更信息量的方法为：首先根据具有N个类别训练数据的已标 注样本集L构建一个一元分类器；然后对于去除该样本a后的该未标注样本集中每一样本x， 将其不属于现有N个类别中任何一类的概率定义为样本x为离群点的概率；然后利用该多分 类器计算去除该样本a后的该未标注样本集关于该新类别的信息熵，作为该样本a的模型变 更信息量。

本发明的主要内容包括：

对于类别数目不确定的分类问题，类别数目N的取值为当前已标注集中样本不同标注的 个数，随着已标注集的扩展，类别数目N随之调整。图1是类别数目不确定的分类模型构建过 程示例：图1(1)中，初始的已标注集仅仅包含A、B两个已标注样本，分别属于类别1、类别2， 因此相应的分类模型为二分类模型；图1(2)中，样本C被标注为类别1并加入已标注集，由于 没有新标注加入，因此分类模型仍然为二分类模型；图1(3)中，样本D被标注为类别3并加入 已标注集，由于新标注(类别3)的出现，分类模型变更为三分类模型。

图1也表明了模型调优与模型变更这两个因素对于分类模型优化同样重要，不可偏废。图 1(1)中，如果仅仅从现有二分类模型出发，样本C比样本D的信息量更大(因为样本C距离分 类面更近，从而具有更大的不确定度)；然而事实上，样本D对于分类模型的优化更有意义(因 为样本D的标注不仅有助于模型参数更新，同时也引入了新标注信息，进而将模型重建为更 加契合数据真实分布的三分类模型)。

1、样本信息量度量

本发明提供的基于非确定主动学习的多分类方法将样本信息量有机融合到一个统一的框 架下，实现样本信息量的综合有效度量。

该方法从信息论出发，基于如下分析：(1)当一个样本被标注为新类别并加入已标注集， 该样本向现有模型中引入了之前未曾建模的全新信息，从而增加了现有模型对于未标注样本 的全局估计的不确定性，从信息论的角度，该样本会增加未标注集的总体信息熵；(2)当一 个样本被标注为某个已知类别并加入已标注集，该样本为现有模型更好地拟合数据分布提供 了新的约束条件，从信息论的角度，该样本往往会降低未标注集的总体信息熵。

基于上述分析，基于非确定主动学习的多分类方法从模型变更和模型调优两个方面度量 样本的信息量：

(1)样本的“模型变更信息量”定义为：假设该样本被标注为新类别的情况下，利用该多 分类器计算除去该样本的未标注集关于新类别的信息熵；公式化表示如下：

${\mathrm{Info}}_{\mathrm{up}\mathrm{grad}e}(x;{\phi }_L,{\theta }_L^N)=P(y\notin C^N|x;{\phi }_L)F(x,N+1;{\theta }_L^{N+1}).$    公式(6)

Info_upgrade与样本信息量正相关。公式中，为样本x在现有模型下被标注为新类 别(即不属于现有N个类别中任何一类)的概率，φ_L为该概率模型的参数。

(2)样本的“模型调优信息量”定义为：假设该样本被标注为已有N个类别中的一个，利 用该多分类器计算除去该样本的未标注集关于每个已有类别的信息熵加权和；公式化表示如 下：

$\left(\begin{array}{c}{\mathrm{Info}}_{\mathrm{update}}(x;{\phi }_L,{\theta }_L^N)=P(y\in C^N|x;{\phi }_L)\underset{\tilde{y}\in C^N}{\Sigma }P\left(\tilde{y}\right|x;{\theta }_L^N)F(x,\tilde{y};{\theta }_L^N)\\ =(1-P(y\notin C^N|x;{\phi }_L))\underset{\tilde{y}\in C^N}{\Sigma }P\left(\tilde{y}\right|x;{\theta }_L^N)F(x,\tilde{y};{\theta }_L^N)\end{array}\right).$    公式(7)

Info_update与样本信息量负相关。

基于非确定主动学习的多分类方法，将样本的模型变更信息量和模型调优信息量有机结 合成为一个综合性度量；根据各自特点，重点监测Info_upgrade值显著高和Info_update值显著低的样 本；公式化表示如下(但不限于该表示形式)：

$x_{\mathrm{IMC}-\mathrm{AL}}^{*}=\underset{x\in U}{\arg \min }\mathrm{Info}(x;{\phi }_L,{\theta }_L^N).$    公式(8)

其中，

$\left(\begin{array}{c}\mathrm{Info}(x;{\phi }_L,{\theta }_L^N)=\log [{\mathrm{Info}}_{\mathrm{update}}(x;{\phi }_L,{\theta }_L^N)=\underset{x\in U}{\min }{\mathrm{Info}}_{\mathrm{update}}(x;{\phi }_L,{\theta }_L^N)+\sigma ]\\ +\lambda \log [-({\mathrm{Info}}_{\mathrm{up}\mathrm{grad}e}(x;{\phi }_L,{\theta }_L^N)-\underset{x\in U}{\max }{\mathrm{Info}}_{\mathrm{up}\mathrm{grad}e}(x;{\phi }_L,{\theta }_L^N))+\sigma ]\end{array}\right).$    公式(9)

Info为样本总信息量。公式中，λ是调整Info_upgrade和Info_update之间相对权重的参数，σ是为了 避免计算结果出现-∞而人为加上的一个非常小的常量(如e^-10)，即根据公式(8)选择信息 量最大的若干个样本进行标注。

2、样本新类别概率计算

在公式中，样本x不属于现有N个类别中任何一类的概率的计算有多种方 法。给定现有已标注集L和N分类模型及其模型参数上述概率的计算方法包括但不限于以 下三种：

(1)基于已标注集L构建一个N+1分类模型，从而将样本x不属于现有N个类别中任何一 类的概率定义为样本x属于第N+1个类别的概率。公式化表示如下：

$P(y\notin C^N|x;{\phi }_L)=P(y=N+1|x;{\theta }_L^{N+1}).$    公式(10)

(2)基于已标注集L构建一个二分类模型，将现有N个类别合并为一个类别“+1”，将现 有N个类别以外的其它类别归为“-1”，从而将样本x不属于现有N个类别中任何一类的概率定义 为样本x属于类别“-1”的概率。公式化表示如下：

$P(y\notin C^N|x;{\phi }_L)=P(y=-1|x;{\theta }_L^2).$    公式(11)

(3)基于已标注集L构建一元分类模型，该分类模型旨在从只包含一种类别的已标注集 中训练分类器用以识别同类样本或检测离群样本，常用方法包括单类支持向量机(OC-SVM)。 本方法将现有N个类别合并为一个类别，将OC-SVM输出值通过sigmoid函数转化为概率形式， 从而将样本x不属于现有N个类别中任何一类的概率定义为样本x为离群点的概率。公式化表示 如下：

$P(y\notin C^N|x;{\phi }_L)=\frac{1}{1+\exp (-{\mathrm{Ourput}}_{\mathrm{OC}-\mathrm{SVM}}(y=\mathrm{outlier}|x;L))}.$    公式(12)。

3、基于聚类的样本批量选取机制

实际应用中，为了保证方法执行效率，每次选出的最有信息样本不是一个而是一批(如 K个样本)。如果仅仅根据公式选取Info值最小的K个样本，会不可避免地引入冗余信息，从而 导致分类效率的下降。

本发明提供一种改进的样本批量选取方法——基于聚类的样本批量选取方法：(1)将未 标注集中的样本聚为J(J≥K)类，聚类方法包括但不限于K-means、K-medoids、谱聚类 等；(2)在每一类中，根据公式选取最有信息的样本，获得样本数为J的样本集；(3)在上 述样本集中，根据公式选取最有信息(Info值最小)的K个样本。J是大于等于K的数用于 处理信息冗余。

依据本发明方法选取K个最有信息样本之后：(1)对选取出的K个样本进行人工标注； (2)将标注后的K个样本从未标注集中去除，并加入已标注集；(3)基于新的已标注集， 根据公式(3)训练新的分类模型，从而获得分类结果。

与现有技术相比，本发明的积极效果为：

本发明所提供的基于非确定主动学习的多分类方法，分别从模型变更和模型调优两个方 面度量样本的信息量，一方面对样本在现有模型框架下优化模型参数的能力进行评估，另一 方面对该样本引入新的类别从而触发模型重建的可能性进行评估，通过综合两方面因素，实 现样本信息量的综合、全面评价，从而为高效利用有限的标注样本获得最优化的海量数据分 类结果提供了一种智能化解决方案。

附图说明

图1为类别数目不确定的分类模型构建过程示例；其中，

(1)初始的已标注集仅仅包含A、B两个已标注样本，

(2)样本C被标注为类别1并加入已标注集，

(3)样本D被标注为类别3并加入已标注集；

图2为本发明提供的基于非确定主动学习的多分类方法流程图。

具体实施方式

以下结合附图对本发明的原理和特征进行描述，所举实例只用于解释本发明，并非用于 限定本发明的范围。

实例基于非确定主动学习的多分类方法

本发明提供的基于非确定主动学习的多分类方法通过循环迭代过程实现分类模型的逐步 优化。

设每轮循环迭代需要标注K个样本，在每轮循环迭代内部执行以下流程：

方法执行结束后，设循环迭代次数为M，则通过人机交互由专家标注的样本总量为 K×M。

以图像分类为例，图像样本用颜色直方图、小波纹理等组成的特征向量x表示；初始已 标注集中图像包括汽车、轮船、飞机、老虎、大象共5类，分别用数字1～5表示，则图像标 注用y＝{1,2,…,5}表示；未标注图像构成未标注集U，已标注图像构成已标注集L表示；分 类模型用后验概率P(y|x；θ_L)表示。

为了提升分类模型的性能，需要选择一些未标注图像进行标注，并利用新的标注信息更 新现有模型，假设每次模型更新需要新标注K＝5个图像样本，迭代执行如下流程：

1)计算未标注图像样本的总体信息量Info(即该样本的模型变更信息量与模型 调优信息量之和)；

2)将未标注图像聚为J＝10个子类；从每个子类中选择Info值最小的一个图像 样本，共得到10个图像样本；在选出的10个图像样本中，选择Info值最小的5个图像 样本；

3)标注选出的5个图像样本，并加入已标注集；

4)将新的已标注集L作为训练数据重新训练图像分类模型；

5)用更新后的分类模型对未标注集进行分类，进而获得改进的图像分类结果。

本发明提供的基于非确定主动学习的多分类方法能够在类别数目不确定的情况下，利用 有限的样本标注量获得最优化的分类效果。