施 伟,黄红蓝,冯旸赫,刘 忠
(国防科技大学系统工程学院,湖南 长沙 410073)
有监督学习是利用标记样本不断调整模型参数以达到性能要求的过程。随着技术进步,能够获取大规模样本数据,提高模型预测性能。然而,即使是对相关领域内的专家来说,给数据加上标签也常常是一项昂贵和耗时的任务。文献[1]中使用的数据集收录了总计367 835字的实验样本,用于军事文本的命名实体识别实验。在文献[2]所研究的航天遥感图像场景分类问题中,一个普通规模的数据集包含31 500张涉及45类场景类别的图像样本,每个样本至少包含196 608个像素。丰富的图像变化、类内多样性和类间相似性使得标注这类数据集更具挑战性。
为解决这类问题,主动学习方法应运而生,用于对未标注数据集的自动标注。文献[3-4]中的策略倾向选择具有最大不确定性的样例交给专家进行标注,使用尽量少的样例获得尽可能高的分类性能。文献[5-6]中的基于专家委员会投票的查询策略是训练一个分类器委员会,并选择最具分歧的实例来分析查询,是一种从随机输入流中过滤信息的方法。上述主动学习策略都属于短视主动学习的范畴,共同的缺点是只根据已标注实例的信息和基于此训练出的分类器来选择将要查询的实例,忽略了大量未标注实例的分布信息。
鉴于上述算法的缺陷,另一类算法试图从大量未标记实例中获取信息,建立一个对问题域中不可见的实例具有良好泛化性能的分类器。比如文献[7]中总结了一种减小数据集样本标注前后泛化误差的方法。与之相似的方法是通过减少模型方差来间接最小化泛化误差,比如文献[8-9]。文献[10]利用未标注样本的先验概率p(x)作为不确定度的权值。文献[11]使用了相似的框架,使用余弦度来测量信息密度。
与查询单个实例的方法不同,批量模式的主动学习方法会选择一批样本进行查询。当批处理规模较小时,又衍生出一类小样本主动学习方法[12-13],该方法认为批量设置越小,选择标准更新越快,越能促进学习性能的提升。
也有一类不需要真实标签对样本进行标注的主动学习方法[14-15],这类方法试图最小化统计模型的期望方差,并在计算这类方差时省略标签信息。但是,因为这种方法没有真正利用样本的标签信息,只关注具有代表性的实例,因此即使标注的实例具有有效信息,仍不被算法利用。文献[16]通过引入多个伪标注器,一定程度上改善了这类小样本主动学习方法的性能,但本质上仍存在上述缺点。
然而当前主流的主动学习方法[5,17-19]都需要很强的计算能力,导致主动学习很难应用于数据量过大的现实问题。因此,迫切需要一种有效的方法解决这类问题。有一些研究试图将聚类算法与主动学习相结合的尝试。比如,文献[20]将分类和聚类结合,避免同一聚类中的样本被重复标记,但该方法局限于线性逻辑回归,仅证明了聚类信息的优越性。文献[21]提出谱聚类和K均值聚类组合的方法,通过提取有代表性的特征向量,辅助支持向量机进行分类,但计算量很大,并未考虑算法效率。文献[22]提出模糊核聚类的方法,但该方法只是为了筛选出日志数据的冗余样本。文献[23]直接将最具代表性的聚类样本分类结果作为聚类的标签。文献[24]引入随机森林概念,重点在于对聚类算法的创新。
本文提出一种基于子抽样的主动学习(subsampling-based active learning,SBAL)算法,整合了无监督聚类算法和传统主动学习方法。首先,采用无监督聚类算法对数据集进行粗略的聚类。然后,提取聚类结果的部分子类别,即所谓的子抽样,减少单次计算的样本数据规模。最后,应用主动学习方法,对子抽样进行分类标注。经过多次迭代,实现对原始数据集的全部分类标注。所提算法在Binary Alphadigits和OMNIGLOT两个标准数据集上进行了实验,实验结果证明,所提算法能打破传统主动学习方法不能处理大规模数据集分类标注问题的局限性。算法的创新点在于除了将无监督聚类与主动学习算法相融合,还在二者之间增加了子抽样操作,该操作能够显著降低算法的时间复杂度,在保证实验准确率的基础上减少实验耗时,从而更加高效地处理大规模数据集的分类问题。
为解决主动学习无法处理大规模数据标注的问题,在进行主动学习前,引入一个无监督聚类的环节。本文框架使用的是K均值聚类算法[25-27],主要包含以下4个步骤。
步骤 1K值的选择:随机选取K个样本作为初始的聚类中心,聚类中心的数量由用户给出,记为K。实际问题中,往往已知样本类别总数,因此在进行聚类处理时,将K值设定为样本类别总数。
步骤 2距离度量:在将对象点分类到距离聚类中心最近的簇中时,需要用到最近邻的度量策略。在欧氏空间中采用的是欧式距离,在处理文档对象时,采用余弦相似度函数,有时候也采用曼哈顿距离为度量,需要根据不同情况进行选择。设第i个样本为xi,第j个聚类的质心为Centerj,数据点xi到质心Centerj的距离为dist(xi,Centerj),以下是不同类型的距离公式。
欧氏距离:
(1)
余弦相似度:
(2)
式中,A与B分别表示xi和Centerj向量。其中,分子为A与B的点乘,分母为二者各自的L2范数相乘。
曼哈顿距离:
(3)
用以标明两个点在标准坐标系上的绝对轴距总和。
步骤 3新质心的计算:经过步骤2,得到K个新的类,每个样本都被分到K个类中之一。之后,样本的质心就会失效,需要计算每个类的新质心。对于分类后产生的K个类,所有样本点的坐标均值即为新质心。假设第j个类包含的数据点有xj1,xj2,…,xjm,则新质心的坐标为
(4)
步骤 4判断算法是否停止:当两次迭代差值ΔJ小于迭代终止阈值δ,或是达到设定的最大迭代次数itermax时,算法停止。否则,循环执行步骤2~步骤4。
K均值算法虽然有效,但是容易受到初始质心设置的影响。一般情况下,在对样本数据分布状况不可知的情况下,初始质心的设定是随机的,所以算法容易陷入局部最优。通常会进行大量重复实验,寻找效果最优的初始设定。
经过对原始数据集的无监督聚类后,得到聚类结果
L={L1,L2,…,LK}
(5)
式中,L是全部子类的集合;Lh表示第h个聚类,h∈[1,K]且h∈Z。
根据需要,随机在集合L中选择p个元素,组成新的集合。子集设为
Lsub,p={Ls1,Ls2,…,Lsp}
(6)
式中,p表示选取的子类个数,p∈[1,K]且p∈Z。
将Lsub,p作为新的未标记数据集,供主动学习算法使用。因为主动学习的性能受数据集影响较大,所以p值需要根据实际情况进行选择,合适的p值会带来性能的提升。
原理上,所有主动学习方法均可以应用本算法流程,但本框架只采用以下5种当前主流的主动学习算法进行设计。
(1) 随机抽样
在抽取的每个子集上均匀随机抽取指定数量的样本作为训练数据,随机抽样的方法常作为所有主动学习方法的基准线。
(2) 不确定性采样[17,28]
采用基于信息熵的不确定性采样作为查询样本的标准:
(7)
(3) 基于专家委员会投票的查询[5,29]
该方法旨在寻找与当前子集上标记训练数据一致的最小化的版本空间。本文采用“袋装”查询的方法,“袋装”是从输入样本中重新采样,得到一个固定的分布,通过对得到的假设的输出进行平均,得到最终的假设。该方法基于预测误差,由“偏差”和“方差”两部分组成,“偏差”是输入数据大小所必需的估计误差,“方差”是具体数据存在的统计差异。“袋装”可以隔离这两个因素,并且可以最小化误差的方差。假设每个子集上一共进行T次查询,因此,在第t时刻查询的样本为
(8)
(9)
(4) 密度加权[18,30]
采用子抽样的方法对基于图的密度加权方法进行改进。基于图的密度加权方法通过构建k近邻的图结构来描述样本间的关系,并用邻接矩阵来表示。每个子集上构建的图结构是对称的,其中两个样本之间的权重表示为
(10)
式中,Wi j表示邻接矩阵;Pi j表示第i个样本属于第j类的概率值;σ表示整体样本分布方差。为了区分具有多个权重较小的领域的数据点,通过边的数量对这些权值进行归一化处理,查询样本的计算公式为
(11)
(5) 基于学习的主动学习[19]
对于每一个子集,模型训练一个回归器,通过将查询选择过程表述为回归问题,预测每个子集上的候选样本的期望误差缩减。在每个子集上,通过选择样本进行标签查询:
(12)
式中,t表示当前迭代查询次数;Ut表示当前子集上未标记的数据集合;g(·)表示一个回归函数,可以预测在给定分类器状态下注释特定样本的潜在误差缩减;Φt表示当前子集上参数化的分类器;Ψx表示当前子集上未标记样本的特征参数。
SBAL算法标准框架的流程图如图1所示。SBAL算法集成了多个子方法,是对主动学习算法解决分类问题的改进,其主要思想如下:因为性能优秀的主动学习算法,都有着极大的计算量,很大程度上限制了实验数据集的规模。当遇到大数据集的实际问题时,就很难直接使用现有主动学习算法训练分类器。为解决这一问题,第一步,对原始数据集无监督聚类,虽然其分类效果不如主动学习算法,但是可以初步实现数据集的大致分类。第二步,随机选取一部分子类作为原始数据集的子抽样,通过对聚类结果子抽样,缩小单次计算的样本数规模,进而简化主动学习方法的处理难度。第三步,将子抽样数据集作为未标注数据集,由主动学习算法进行训练,完成标注。重复执行第二步和第三步,实现全部样本的标注。
算法的时间复杂度很大程度上反映了算法的效率,是衡量算法优劣的一个重要指标。本节旨在分析时间复杂度,证明采用本文算法相较于传统采样算法,性能有所提升。
为便于分析,假设整个样本集的数据规模为n,当n足够大时,样本大致均匀分布于m类,每类包含m/n个样本。使用SBAL算法时,子抽样集所包含的种类数为M,样本规模为nM/m。因为相较于主动学习算法,K均值聚类算法的时间复杂度O(n)较低,且实现简便,可在实验预处理阶段获得,因此可以忽略。本节只需对主动学习阶段采样策略的算法复杂度进行分析。
图1 SBAL算法标准框架流程图Fig.1 Flow chart of SBAL algorithm standard framework
1.5.1 基于随机抽样的查询策略
传统随机采样直接在全部未标注样本集中随机选取采样点,时间复杂度为O(n)。当采用SBAL算法后,每个子集的数据规模为nM/m,子集数目为m/M,因此时间复杂度为O(n)。虽然时间复杂度相同,但随机抽样策略的实验性能较差,很少应用。因此比较复杂度的意义不大。
1.5.2 基于不确定性采样的查询策略
采用SBAL算法后,单个子抽样集计算的时间复杂度仅为O(M3n/m),经过重复抽样后,复杂度增加为O(M2n)。可以看出当数据集规模十分巨大,类别数目m较多时,采用小规模子抽样,可得到M2≪m2,使时间复杂度较大程度的降低。
1.5.3 基于专家委员会投票的查询策略
假设专家委员会成员数为c。该算法需要首先计算所有委员会成员类条件概率,时间频度为T(n,m,c)=((m+1)c+3)m,再计算两个条件概率分布的信息度量,时间频度为T(n,m,c)=(((m+1)c+3)m)c,遍历所有样本后为T(n,m,c)=(((m+1)c+3)m)cn,经整理,时间复杂度为O(m2c2n)。
当采用SBAL算法时,单个子抽样集计算的时间复杂度仅为O(M3c2n/m),经过重复抽样后,复杂度增加为O(M2c2n)。同理,根据样本规模较大的特点,有M2≪m2,算法时间复杂度减少。
1.5.4 基于密度加权的查询策略
使用密度加权的查询策略,既要计算样本的信息量,又要计算样本在样本空间中的密度信息,用于对信息量加权。信息量的计算与基于不确定性的查询策略无异,时间频度为T(n,m)=m(m+3),密度信息的计算时间频度为T(n,m)=n,遍历全部样本点的总时间频度为T(n,m)=m(m+3)nn,则时间复杂度为O(m2n2)。
采用SBAL算法,单个子抽样集计算时间频度为T(n,m)=(nM/m)2(M+3)M,复杂度为O(M4n2/m2),经过重复抽样后,时间复杂度变为O((M3/m)n2),显然在M≪m时,可得M3/m≪m2,使用SBAL算法相较于原算法复杂度也有所降低。
1.5.5 基于学习的查询策略
本方法不同于传统查询策略的是,通过训练回归器在训练中选择能够减少泛化误差的未标记样本进行查询,然而不同的问题,样本的特征参数Ψx会随之变化,分类器的回归函数g(·)也有所不同。
该策略虽然没有固定公式用于定量分析时间复杂度,但可以定性分析。该策略通过使用简单的特征(如分类器输出的方差或特定数据点可能的预测标签概率分布)训练分类器的回归函数。这一计算过程需要计算每个未标注样本作为候选查询样本的期望误差缩减,时间复杂度至少为O(n),此时,采用SBAL算法的时间复杂度也为O(n)。如果在计算期望误差缩减时,选取更为复杂的函数,一旦原始策略时间复杂度成指数增加,那么采用SBAL算法的优势将会明显,M≪m的条件会使算法时间复杂度大幅度减少。
将模型中5种基于子抽样的经典主动学习方法应用到多类别数据标注的问题上,对基于子抽样的经典主动学习在多类别数据上的性能进行实验研究。
2.1.1 Binary Alphadigits
Binary Alphadigits数据集[31]是一个手写字符图像数据集,数据集中共有36类手写字符,分别由26个大写英文字母“A”至“Z”和10个数字字符“0”至“9”组成。数据集中每类字符由39个二值图片组成,将每个样本图像补0扩大为20像素×20像素,因此每张图片可以用一个400维的向量表示。数据集图片如图2所示。
图2 Binary Alphadigits数据集图片Fig.2 Image of Binary Alphadigits dataset
2.1.2 OMNIGLOT数据集
OMNIGLOT数据集[32]也是一个手写字符图像数据集。数据集是由50种不同字母组成的1 623类不同的手写字符。每一类字符都是由不同的20个人通过亚马逊公司的Mechanical Turk在线绘制的,一共32 460个样本。每个图像大小为105像素×105像素,在实验中,将每个样本图像压缩为28像素×28像素,因此每张图片可以用一个784维的向量来表示。与Binary Alphadigits数据集相比,OMNIGLOT数据集更加复杂,因为数据集中的类别数量巨大,同时每类仅有少量样本。因此,OMNIGLOT数据集成为了小样本学习的标准数据集。数据集中的部分图片如图3所示。
图3 OMNIGLOT 数据集图片Fig.3 Image of OMNIGLOT dataset
在实验中,对每种主动学习算法,都采用子抽样的方法,令其从数据集中选择p类样本组成实验子集Lsub,p,其中p={3,5,8}。这里子集中的样本很可能是不平衡的,可能一类存在很多样本,而另一类可能样本数很少甚至没有。这种设置增加了实验难度。由于主动学习算法需要标记样本作为初始样本,所以在每一个子集中都给定p个已标记样本作为初始样本,这些初始样本分别来自不同的类别。对于无监督聚类后的数据集,抽取10 000个子集,即进行10 000次随机实验。其中,在每个子集上,按照80%为训练集,剩余20%为测试集的方式划分数据集。
2.3.1 Binary Alphadigits实验结果
迭代结果如图4所示。其中,横轴为查询次数(将初始给定标记样本的数目作为横轴的初始值),纵轴为性能指标准确率。在每一组实验中都将最大查询次数设置为总样本数的80%,即最终使整个训练集都被查询。从图4中可以看出,在Binary Alphadigits数据集上,随着查询次数的增多,各个算法的准确率都在上升,不同算法的准确率有所不同。由于每个回合(每个子集)上,给定每个算法的初始标记样本数相同,因此各个算法初始时在测试集上的分类准确率相同。同样,在回合结束时,由于最大查询数目等于整个测试集的样本数,所以对于不同算法,最终都将查询完整个测试集后算法才停止该回合,因此所有算法最终的准确率也一致。
图4 Binary Alphadigits数据集的算法性能对比Fig.4 Algorithm performance comparison of Binary Alphadigits dataset
各个算法的平均准确率如表1所示。根据表1中的结果,在Binary Alphadigits数据集上,基于不确定性采样的主动学习模型的平均性能最好,达到的平均准确率最高。结合图4可知,基于密度加权的主动学习算法在查询样本数较少的情况下能够达到较高的准确率,但是随着查询数的增多,分类性能却提升不多,使得最终的平均准确率与随机抽样的方法相差不大。随着每个子集上需要判别的类别数的增多,各个主动学习算法在Binary Alphadigits数据集上的平均准确率都有不同程度的下降。但在子抽样集包含3类样本时,所有算法的准确率都达到了83%以上,相较于传统主动学习算法直接处理这类样本的实验准确率有较大提升,证明本文提出的主动学习框架是有效的。
表1 Binary Alphadigits数据集实验结果Table 1 Experimental results of Binary Alphadigits dataset
2.3.2 OMNIGLOT实验结果
相较于Binary Alphadigits数据集,OMNIGLOT数据集具有更多的类别数和每类更少的样本数,因此对于传统的主动学习方法来说是一个更大的挑战。不同算法在OMNIGLOT数据集上的性能曲线如图5所示。每回合的查询样本数从p开始,到总样本数的80%结束。从图5中可以看出,在OMNIGLOT数据集上,随着查询次数的增加,各个算法的准确率均有不同程度的提高。基于专委会投票查询的主动学习模型的平均性能最好,达到的平均准确率最高。基于密度加权的主动学习模型表现最差,低于随机抽样方法的准确率基线。
图5 OMNIGLOT数据集的算法性能对比Fig.5 Algorithm performance comparison of OMNIGLOT dataset
OMNIGLOT数据集上各个算法的实验结果如表2所示。
表2 OMNIGLOT数据集实验结果Table 2 Experimental results of OMNIGLOT dataset
根据表2可知,基于专委会投票查询的主动学习模型的平均性能最好,达到的平均准确率最高。基于密度加权的主动学习模型表现最差,低于随机抽样的主动学习方法的准确率基线。随着每个子集上需要判别的类别数的增多,各个主动学习算法的平均准确率下降明显。在子抽样包含3类样本时,所有算法的平均准确率都在70%以上,但在8分类问题中所有算法的平均准确率都低于60%,结合图5,即使对整个测试集进行标注,以上几种主动学习算法在测试集上的准确率也不超过65%。结果表明,由于数据集过大且有效信息不足,不依靠本文提出的标准框架,单纯以传统主动学习算法将根本无法解决这类问题。另外,本文提出的主动学习框架虽然能够一定程度上解决传统主动学习算法难以处理大规模数据集多类别分类问题,但框架性能对p值较为敏感,只有合适的p值才能较大程度提高算法性能。
在第2.3节充分展示本文算法性能的基础上,本节从实验准确率和耗时两个方面,对比SBAL算法和原始主动学习算法之间的性能差异。对比实验采用与第2.3节相同的数据集作为实验对象,实验的基本设置不变,区别在于主动学习的采样策略是否使用本文所提出的子抽样方法。
2.4.1 Binary Alphadigits实验
在分别使用原始采样策略和子抽样采样策略条件下,不同算法的实验准确率以及总耗时,如表3所示。其中,子抽样策略取p=3,抽取100个子集。
表3 Binary Alphadigits数据集对比实验结果Table 3 Comparative experimental results of Binary Alphadigits dataset
由于抽取100个子集后,子抽样策略的实验准确率已经高于原始策略,因此,为突出耗时差异,抽取子集数不采用第2.3节实验的10 000个。表3数据可以反映出,SBAL算法对比传统主动学习算法,性能有所提高,准确率提升12%~19%不等,总耗时缩减为原始算法的1/5左右。相比较而言,本文算法的耗时相当可观,在同样的实验条件和设置下,算法性能均优于原始算法。
2.4.2 OMNIGLOT实验
由于该数据集样本数量过大,且每个样本是784维的向量,经实验发现,处理这种规模的数据,使用传统主动学习的方法已经超出了计算机最大的处理能力。因此,为通过具体实验数值展示算法优劣性,不断减少数据集规模,最终发现当数据集规模删减为100类样本,共2 000个样本时,原始算法才能正常运行。具体实验结果如表4所示。在OMNIGLOT数据集上的实验充分证明,当数据量过大时,传统主动学习根本无法有效运行,然而使用SBAL算法可以正常运行。通过删减数据集规模,虽然传统算法能够勉强运行,但结果显示其准确率已经十分低,根本无法用于实际问题。相较而言,SBAL算法准确率提高了123%~195%,耗时缩减为原始策略的1/50。
表4 OMNIGLOT数据集对比实验结果Table 4 Comparative experimental results OMNIGLOT dataset
2.4.3 性能对比分析
对比实验的目的,在于比较采用SBAL算法框架和原始算法之间的性能差异。突出本文算法在同样的实验条件和设置下,算法性能的优越性。经过实验验证,当处理数据规模巨大,分类数量繁多的问题时,传统主动学习算法不仅需要更强的计算能力,还会耗费大量的计算时间,甚至不能有效运行,且准确率几乎不可以接受。当采用本文所提出的SBAL算法框架后,实验准确率有较大提升,并且实验耗时有显著缩减。
为了分析p取值对实验结果的影响,考察了在不同p值选择下,实验准确率的变化。
如图6所示,从整体上看,实验准确率会随着p值的增大而波动降低。当p取值接近2时,不同算法的准确率普遍最高,大约为85%。因为子抽样类别数为2时,即使无监督聚类结果不准确,也不会带来大量的错误分类样本,有利于主动学习算法对样本的准确标注。但随着p值增加,无监督聚类的准确率对实验结果的影响显著增加,因为聚类算法的性能缺陷,必然会引入错误分类的样本,而样本类别数增加也会使得主动学习算法更难准确标注样本类别,综合两个因素,实验准确率的确应该呈递减趋势而变化。
图6 Binary Alphadigits数据集下p值对实验准确率的影响Fig.6 Influence of the p-value on the accuracy of experiment in the Binary Alphadigits dataset
图7所示是OMNIGLOT数据集下,实验准确率的变化趋势图。在OMNIGLOT数据集上的实验结果更为明显,当p值初始取最小值2时,实验准确率最高,大致为85%。随着p值增大,实验准确率迅速降低,当p=5时,准确率已经降为60%左右。当p=25时,准确率降低速度趋缓,并大致在30%~40%波动。剖析导致实验准确率如此变化的原因,和图6实验大同小异。由于p值较小时,即便无监督聚类结果存在偏差,对主动学习标注来说,并不会造成过大影响。但随着p值增大,既会导致无监督聚类错误标注的样本对实验准确率影响增大,又会因为类别数增多,导致主动学习阶段本身错误率增加。
图7 OMNIGLOT数据集下p值对实验准确率的影响Fig.7 Influence of the p-value on the accuracy of experiment inthe OMNIGLOT datasets
针对传统主动学习方法在多类别数据集标注上的应用局限性,本文提出了面向多类别数据分类问题的子抽样主动学习方法。该方法提出一个标准框架,将无监督聚类算法、子抽样和主动学习方法进行整合,通过对聚类结果子抽样,缩小单次计算的数据集规模,进而简化主动学习方法的处理难度。所提方法在Binary Alphadigits和OMNIGLOT数据集上进行了实验检验,结果证明,本文提出的SBAL标准框架可以有效处理大规模数据集多类别分类问题,算法性能对比实验结果显示,SBAL算法的实验性能高于传统主动学习算法,但框架性能对p值敏感,现有实验结果表明,当p值较小时,算法平均准确率更高。
本文方法具有通用性,可以更换聚类算法和主动学习算法,对不同数据集也有较好的泛化性能,适用于多种实际应用背景,应用前景广泛,能够有效化解训练数据标注缺失的问题。但仍有亟待解决的问题和需要研究的方向:
(1) 本文框架只是对传统主动学习算法的部分改进,没有从本质上突破其精度上限。所以,如何构建全新的算法模型,解决数据标注难题,仍将是未来需要研究的方向。
(2) 本文实验虽然得出了框架性能受p值影响的定性结论,但还未给出其定量关系,研究p值对实验性能影响的定量关系,将会有效推动本文框架的实用性。
(3) 本文框架是解决大规模数据集多类别分类问题的一次有效尝试,虽然相较于传统主动学习算法,性能有了较大提升,但从其平均准确率看,还达不到工程应用的标准,完善算法流程,进一步提高实验准确率,也将是下一步的研究方向。