基于间隔准则的优化排序多标记学习算法

金亚洲,张正军,颜子寒,王雅萍

(南京理工大学 理学院,南京 210094)

0 概述

目前,针对多标记学习分类问题的多标记学习算法可大致分为问题转换方法和算法适应方法2类[5-6]。问题转换方法解决此类问题的思想是对多标记学习训练样本数据进行处理,将该问题转化为已知的学习问题,例如一个或多个单标记问题或者回归问题。算法适应方法解决此类问题的思想是对已有的传统监督学习算法进行改进或扩展,使其能够适应多标记数据的学习。

在问题转化方法的研究中,BR(Binary Relevance)算法[3]较简单,该算法将多标记学习问题转化为若干个独立的二分类问题,其计算复杂度较低,但由于忽略了标记之间内在的相关信息,因此泛化性能较差。分类器链(Classifier Chain,CC)算法[7-8]在BR算法的基础上,将独立的二分类器进行串联形成一条链,该算法考虑了标记之间的相关性等信息,但链表顺序直接影响最终的分类效果,且其考虑的相关性信息有时并不符合样本数据的标记本质相关性信息,文献[7]利用CC算法的集成框架ECC来缓解由随机确定链表顺序带来的不利影响。LP(Label Power-set)算法[9]是一种标记组合算法,其基本思想是将多标记数据集中每个唯一的标记集合均作为一个整体标记,训练和预测过程中的输入和预测输出均为一个整体标记,多标记学习问题即被转化为一个单标记多分类问题。但是,当标记空间较大时,LP算法的训练样本数据中标记集合对应的示例数量较少,会引起类不平衡问题,进而影响分类效果。

在算法适应方法的研究中,Rank-SVM算法[10-11]通过对传统的SVM算法[12]进行扩展,采用最大化间隔策略,通过一组线性分类器来最小化排序损失评价指标,并引入“核技巧”来处理非线性多标记问题。BP-MLL(Back-Propagation Multi-Label Learning)算法[13-14]基于经典的反向传播(Back-Propagation,BP)算法,通过采用一种新的误差函数从而适应于多标记问题,并使用梯度下降法更新网络中的参数。ML-KNN方法[15-16]基于传统的KNN方法,根据测试集中每个示例与训练集样本的相似度来确定其K个近邻,并通过最大后验概率(MAP)原理来预测样本的标记集合。

本文基于间隔准则提出2种优化的多标记学习算法,两者均可归纳为算法适应方法。第1种算法通过优化模型在相关标记集合中最小输出与不相关标记集合中最大输出的间隔损失来进行标记排序。考虑到该算法对标记信息利用不足的问题,第2种算法不仅优化上述间隔损失,同时还优化模型在相关标记集合中平均输出与不相关标记集合中最大输出的间隔损失,以及优化模型在相关标记集合中最小输出与不相关标记集合中平均输出的间隔损失,从而进行标记排序。上述2种算法均采用改进的次梯度Pegasos算法[17-18]进行参数学习,以提高分类效果。

1 相关工作

1.1 间隔准则

本文算法以基于间隔准则的多分类算法[19-20]为基础。在多分类算法中,令L={(x1,y1),(xn,yn)}表示训练集,其中,yi属于有限数目的类别集合,该算法的目标为最小化正则化经验风险损失,即:

(1)

(2)

其中,Ω(·)为正则项,其是一个单调增凸函数,L(·)用于计算模型在训练样本数据上的经验风险,λ为平衡参数,用于平衡模型正则项与经验损失对目标函数的影响。多分类支持向量机(multiclass-SVM)利用模型参数的L2范数作为正则项,即:

(3)

在经验损失设置上,损失函数l(xi,yi,w)被设置为铰链损失,即:

(4)

其中,Φ(·,·)为一个映射函数,其将每一个示例-标记对(x,y)映射为:

(5)

其中,Ι(·)为指示函数。在multiclass-SVM中引入松弛变量ξi,式(1)最小化问题可以转化为:

s.t.

∀(xi,yi)∈L

ξi≥0

(6)

1.2 Pegasos算法

传统二分类支持向量机问题的学习任务均被转化为有约束的二次规划问题,该问题的最初形式为无约束、带有惩罚项的经验损失最小化问题,且损失函数通常选择铰链损失,可用如下的优化模型表示:

(7)

l(w;(xi,yi))=max(0,1-yi〈w,xi〉)

(8)

其中,〈w,xi〉表示向量w和xi的内积。

Pegasos算法是随机梯度下降方法在解决上述问题时的一个应用,该算法不需要转化为对偶形式进行求解,直接在原始的目标函数上通过选取合适的步长并采用随机梯度下降方法对参数进行学习。Pegasos算法主要分为梯度下降和投影2个阶段,其主要思想如下:

在模型参数的初始值设置时,令w1=0,设置迭代轮数为T,在Pegasos算法的每轮迭代t中,随机选取一个训练样本(xit,yit),将选取的训练样本近似代替式(7)所表示的目标函数,如下:

(9)

上述近似目标函数的次梯度可用下式表示:

(10)

其中,I[yit·〈wt,xit〉<1]为指示函数。更新wt+1/2←wt-ηtt,步长ηt=1/(λt),更新后的模型参数可表示如下:

(11)

投影阶段的模型参数更新可以表示为:

(12)

当迭代轮数达到T时,wT+1即为学习到的模型参数。

2 优化排序多标记学习算法

2.1 最小输出与最大输出间的间隔优化

s.t.

ξi≥0,∀i∈{1,2,…,N}

(13)

在上述优化问题中,目标函数的第一项为正则项约束,用以衡量模型的复杂度,第二项为损失函数,衡量模型在不满足约束条件时的经验损失。约束条件度量了每个示例对象相关标记集合中最小输出与不相关标记集合中最大输出的间隔。

式(13)优化问题在本文中通过改进的次梯度Pegasos算法来解决,可通过梯度下降与投影2个阶段实现。在每轮迭代中,随机从训练数据集中抽取一个样本,判断该样本是否满足式(14):

(14)

(15)

根据梯度下降策略,模型参数的更新为:

(16)

(17)

在模型的预测阶段,给定未知示例对象x,模型预测出的标记集合为:

h(x)=sign(f1(x)-t(x),f2(x)-t(x),…,fq(x)-t(x))

(18)

其中,t(x)为阈值函数,本文通过文献[10]算法,即学习一个线性回归函数来计算t(x)。

优化最小输出与最大输出的间隔损失的多标记学习算法具体步骤如下:

输入训练数据集D,平衡参数λ,迭代终止次数T或迭代终止条件ε

输出学习到的参数w

步骤2随机从训练集中抽取一个样本,检测该样本是否满足式(14)约束条件。

步骤3若不满足约束条件,则根据式(16)和式(17)更新w;否则,根据式(19)和式(17)更新w。

wt+1/2=(1-ηtλ)wt

(19)

步骤4重复步骤2和步骤3,直到满足判定条件‖w‖F≤ε或迭代次数大于T,终止迭代计算并输出w。

2.2 改进的优化排序多标记学习算法

本文2.1节算法只考虑优化示例对象相关标记集合最小输出与不相关标记集合最大输出之间的间隔,该间隔也即距离分界面最近的标记输出之间的差异。然而,上述算法对示例所拥有的全部标记信息利用不足,同时易出现过拟合现象,因此,本节对该算法进行改进,改进算法不仅优化上述间隔,同时优化模型在示例相关标记集合中的平均输出与不相关标记集合中最大输出之间的间隔,以及优化模型在示例相关标记集合中的最小输出与不相关标记集合中的平均输出之间的间隔。在上述模型的基础上,再引入2个松弛变量ξ′={ξ′1,ξ′2,…,ξ′N}和υ′={υ′1,υ′2,…,υ′N}用来表示示例对象没有满足上述间隔要求所产生的损失,则改进模型所求解的优化问题为:

s.t.

ξi≥0,ξ′i≥0,υ′i≥0,∀i∈{1,2,…,N}

(20)

从上述优化问题可以看出,当约束条件第一项成立时,第二项与第三项显然成立;当约束条件第一项不成立时,第二项与第三项存在成立的可能性,且在算法优化过程中的初始阶段,可以对全部标记所对应的模型参数进行更新,加快收敛速度。随着迭代次数的增加,约束条件第二项及第三项在模型参数更新过程中所起的作用越来越小甚至不起作用,同时第二项及第三项约束条件可以缓和过拟合现象,该优化问题的求解同样采用改进的次梯度Pegasos算法。

2.3 算法分析

3 实验结果与分析

3.1 实验设置

为了验证本文算法的有效性,使用来自开源项目Mulan[22]所提供的4个数据集,其中,emotions来自于音乐情感分类领域,image与scene来自于自然场景分类领域,langlog来自于文本分类领域。数据集的统计信息如表1所示。

表1 实验数据集信息

在多标记学习问题中,常用的评价指标为海明损失(Hamming Loss,HL)、排序损失(Ranking Loss,RL)、最前端错误率(One-Error,OE)、覆盖率(Coverage rate,CV)和平均准确率(Average Precision,AP)。各指标具体如下:

1)HL指标考察样本在单个标记上的误分类情况,即对某个示例对象而言,不相关的标记被预测为相关或相关的标记被预测为不相关的情况。HL计算如下:

(21)

2)RL指标考察在样本的语义标记排序序列中出现排序错误的情况。RL计算如下:

(22)

3)OE指标考察在样本的语义标记排序序列中,序列最前端的标记不属于样本相关标记集合的情况。OE计算如下:

(23)

4)CV指标考察在样本的语义标记排序序列中,覆盖隶属于样本的所有相关标记所需的搜索深度。CV计算如下:

(24)

5)AP指标考察在样本的语义标记排序序列中,排在隶属于该样本的相关标记之前的标记仍属于样本相关标记集合的情况。AP计算如下:

(25)

在分类器效果评估中,HL、RL、OE和CV 4个评价指标的指标值越小,则算法性能越优,AP评价指标的指标值越大,则算法性能越优。

3.2 结果分析

本文将提出的第1种算法表示为Proposed1,第2种算法表示为Proposed2,平衡参数λ的取值范围为{0.001,0.01,0.1,1,10,100},将本文2种算法与现有的多标记学习算法ML-RBF[23]、BP-MLL[13]和ML-KNN[15]进行对比,实验结果如表2～表6所示,其中,结果均为3次交叉验证后的均值,以排除随机性,最优结果加粗表示。

表2 海明损失结果对比

表3 排序损失结果对比

表4 最前端错误率结果对比

表5 覆盖率结果对比

表6 平均准确率结果对比

从表2～表6可以看出,在4个多标记数据集中,本文提出的2种算法的5个评价指标均取得了较好的效果,与3种多标记学习算法相比,评价指标结果接近,表明本文2种算法可以实现多标记分类。实验结果也表明,考虑相关标记集合的平均输出与不相关标记集合的平均输出,即本文第2种算法在5种评价指标表现上均优于本文第1种算法,表明考虑平均输出的算法能够提升基于间隔准则的分类器性能。

4 结束语

受基于间隔准则的多分类支持向量机的启发,本文通过优化示例相关标记集合中最小输出与不相关标记集合中最大输出的间隔损失,以实现示例对应的标记集合排序。为了在模型参数训练过程中充分利用标记空间的全部标记信息,进一步优化示例相关标记集合平均输出与不相关标记集合中最大输出的间隔损失,以及示例相关标记集合中最小输出与不相关标记集合中平均输出的间隔损失。实验结果表明,与ML-RBF、BP-MLL和ML-KNN多标记学习算法相比,本文提出的2种算法在4个多标记数据集上均取得了相近的分类性能。本文假设训练样本与标记之间呈线性关系,且算法未考虑标记之间存在的相关性,下一步考虑将特征空间扩展到再生核希尔伯特空间中进行学习,并结合标记之间的相关性来提高分类效果。