2020, Vol. 46
, 监督学习是机器学习领域的研究热点之一。在传统的监督学习框架中, 无论标记空间含有2个还是多个标记, 每个示例只被赋予一个标记, 该类问题被称为单标记学习问题。然而, 在真实应用中, 对象通常具有多义性。例如, 在新闻报道分类中[1-2], 一篇报道可能同时涉及“政治”“经济”和“人口”等多个语义概念。在图像分类中[3], 一张图像可能同时包含“日出”“大海”和“帆船”等多个子场景。在基因功能预测任务中[4], 一段基因序列可能同时具有“转录”“蛋白质合成”和“新陈代谢”等功能。上述3种问题均为多标记学习分类问题。在多标记学习框架中, 每个对象被赋予标记空间中的一组子集来表示其具有的多种语义信息, 对象的学习任务为预测出测试样本的所有相关类别标记。多标记学习分类问题利用数学模型可以描述为:假定X=$\mathbb{R}$d表示d维输入样本集的特征空间, Y={y1, y2, …, yq}表示由q个所有可能的概念标记组成的标记空间, 其学习目标是在给定的训练集D={(xi, Yi)|1≤i≤N}中学习一个映射函数h:x→2Y, 即多标记分类器, 使得对于一个未知标记集合的示例x, 该函数能够预测出其相关标记集合h(x)⊆Y。然而很多已有模型的输出是某个实值函数f:X×Y→R, f(·, ·)可以被转化为一个排序函数rankf(·, ·), 该排序函数将所有的实值输出f(xi, y)(y∈Y)映射到集合{y1, y2, …, yq}中, 如果f(xi, y1)>f(xi, y2), 则rankf(xi, y1) < rankf(xi, y2)。
目前, 针对多标记学习分类问题的多标记学习算法可大致分为问题转换方法和算法适应方法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属于有限数目的类别集合, 该算法的目标为最小化正则化经验风险损失, 即:
| $ {\mathop {{\rm{min}}}\limits_\mathit{\boldsymbol{w}} {\kern 1pt} {\kern 1pt} {R_{{\rm{reg}}}}(\mathit{\boldsymbol{w}}): = \lambda \varOmega (\mathit{\boldsymbol{w}}) + L(\mathit{\boldsymbol{w}})} $ | (1) |
| $ {L(\mathit{\boldsymbol{w}}): = \frac{1}{n}\sum\limits_{i = 1}^n l ({x_i},{y_i},\mathit{\boldsymbol{w}})} $ | (2) |
其中, Ω(·)为正则项, 其是一个单调增凸函数, L(·)用于计算模型在训练样本数据上的经验风险, λ为平衡参数, 用于平衡模型正则项与经验损失对目标函数的影响。多分类支持向量机(multiclass-SVM)利用模型参数的L2范数作为正则项, 即:
| $ {\varOmega (\mathit{\boldsymbol{w}}) = \frac{1}{2}\sum\limits_{j = 1}^q {{{\left\| {{\kern 1pt} {\mathit{\boldsymbol{w}}_j}{\kern 1pt} } \right\|}^2}} } $ | (3) |
在经验损失设置上, 损失函数l(xi, yi), w被设置为铰链损失, 即:
| $ {\rm{max}}(0,1 - [\mathit{\boldsymbol{w}}_{{y_i}}^{\rm{T}}\varPhi ({\mathit{\boldsymbol{x}}_i},{y_i}) - \mathop {{\rm{max}}}\limits_{{y_k} \ne {y_i}} {\kern 1pt} {\kern 1pt} \mathit{\boldsymbol{w}}_{{y_k}}^{\rm{T}}\varPhi ({\mathit{\boldsymbol{x}}_i},{y_k})]) $ | (4) |
其中, Φ(·, ·)为一个映射函数, 其将每一个示例-标记对(x, y)映射为:
| $ \varPhi (\mathit{\boldsymbol{x}},y) = \left[ {\begin{array}{*{20}{l}} {\mathit{\boldsymbol{x}} \cdot I(y = 1)}\\ {\mathit{\boldsymbol{x}} \cdot I(y = i)}\\ {\mathit{\boldsymbol{x}} \cdot I(y = |\mathit{\boldsymbol{Y}}|)} \end{array}} \right] $ | (5) |
其中, Ι(·)为指示函数。在multiclass-SVM中引入松弛变量ξi, 式(1)最小化问题可以转化为:
| $ \begin{array}{l} \begin{array}{*{20}{l}} {\mathop {{\rm{min}}}\limits_{\mathit{\boldsymbol{w}},\xi } \left( {\frac{\lambda }{2}\sum\limits_{j = 1}^q {{{\left\| {{\kern 1pt} {\mathit{\boldsymbol{w}}_j}{\kern 1pt} } \right\|}^2}} + \frac{1}{n}\sum\limits_{i = 1}^n {{\xi _i}} } \right)}\\ {{\rm{s}}{\rm{.}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{t}}{\rm{. }}} \end{array}\\ \begin{array}{*{20}{l}} {\forall ({\mathit{\boldsymbol{x}}_i},{y_i}) \in L}\\ {\mathit{\boldsymbol{w}}_{{y_i}}^{\rm{T}}\varPhi ({\mathit{\boldsymbol{x}}_i},{y_i}) - \mathop {{\rm{max}}}\limits_{{y_k} \ne {y_i}} (\mathit{\boldsymbol{w}}_{{y_k}}^{\rm{T}}\varPhi ({\mathit{\boldsymbol{x}}_i},{y_k})) \ge 1 - {\xi _i}}\\ {{\xi _i} \ge 0} \end{array} \end{array} $ | (6) |
传统二分类支持向量机问题的学习任务均被转化为有约束的二次规划问题, 该问题的最初形式为无约束、带有惩罚项的经验损失最小化问题, 且损失函数通常选择铰链损失, 可用如下的优化模型表示:
| $ {\mathop {{\rm{min}}}\limits_\mathit{\boldsymbol{w}} \frac{\lambda }{2}{{\left\| {{\kern 1pt} \mathit{\boldsymbol{w}}{\kern 1pt} } \right\|}^2} + \frac{1}{n}\sum\limits_{i = 1}^n l (\mathit{\boldsymbol{w}};({\mathit{\boldsymbol{x}}_i},{y_i}))} $ | (7) |
| $ {l(\mathit{\boldsymbol{w}};({\mathit{\boldsymbol{x}}_i},{y_i})) = {\rm{max}}(0,1 - {y_i}\langle \mathit{\boldsymbol{w}},{\mathit{\boldsymbol{x}}_i}\rangle )} $ | (8) |
其中, 〈w, xi〉表示向量w和xi的内积。
Pegasos算法是随机梯度下降方法在解决上述问题时的一个应用, 该算法不需要转化为对偶形式进行求解, 直接在原始的目标函数上通过选取合适的步长并采用随机梯度下降方法对参数进行学习。Pegasos算法主要分为梯度下降和投影2个阶段, 其主要思想如下:
在模型参数的初始值设置时, 令w1=0, 设置迭代轮数为T, 在Pegasos算法的每轮迭代t中, 随机选取一个训练样本(xit, yit, 将选取的训练样本近似代替式(7)所表示的目标函数, 如下:
| $ {\mathop {{\rm{min}}}\limits_\mathit{\boldsymbol{w}} \frac{\lambda }{2}{{\left\| {{\kern 1pt} \mathit{\boldsymbol{w}}{\kern 1pt} } \right\|}^2} + l(\mathit{\boldsymbol{w}};({\mathit{\boldsymbol{x}}_{{i_t}}},{y_{{i_t}}}))} $ | (9) |
上述近似目标函数的次梯度可用下式表示:
| $ {{\nabla _t} = \lambda {\mathit{\boldsymbol{w}}_t} - I[{y_{{i_t}}} \cdot \langle {\mathit{\boldsymbol{w}}_t},{\mathit{\boldsymbol{x}}_{{i_t}}}\rangle < 1]{y_{{i_t}}}{\mathit{\boldsymbol{x}}_{{i_t}}}} $ | (10) |
其中, I[yit·〈wt, xit〉 < 1]为指示函数。更新wt+1/2←wt-ηt▽t, 步长ηt=1/λt, 更新后的模型参数可表示如下:
| $ {{\mathit{\boldsymbol{w}}_{t + 1/2}} \leftarrow \left( {1 - \frac{1}{t}} \right){\mathit{\boldsymbol{w}}_t} + {\eta _t}(I[{y_{{i_t}}} \cdot \langle {\mathit{\boldsymbol{w}}_t},{\mathit{\boldsymbol{x}}_{{i_t}}}\rangle < 1]{y_{{i_t}}}{\mathit{\boldsymbol{x}}_{{i_t}}})} $ | (11) |
投影阶段的模型参数更新可以表示为:
| $ {{\mathit{\boldsymbol{w}}_{t + 1}} \leftarrow {\rm{min}}\left\{ {1,\frac{{1/\sqrt \lambda }}{{\left\| {{\kern 1pt} {\mathit{\boldsymbol{w}}_{t + 1/2}}{\kern 1pt} } \right\|}}} \right\}{\mathit{\boldsymbol{w}}_{t + 1/2}}} $ | (12) |
当迭代轮数达到T时, wT+1即为学习到的模型参数。
2 优化排序多标记学习算法 2.1 最小输出与最大输出间的间隔优化从上述多分类支持向量机可以看出, 由于多分类问题中的每个示例对象仅有一个真实标记, 如果将多分类问题作为一个标记间排序问题来对待, 该问题优化的是最相关标记与次相关标记之间的间隔。而在多标记学习分类问题中, 示例对象的标记数目为不定数, 因此本文首先将多标记学习分类问题转化为排序问题, 即示例与标记间的相关程度不同[21], 并假设在相关标记集合中标记与示例的相关程度也不同, 且相关性均大于不相关标记集合中的标记, 因此, 本文算法的优化目标为训练数据集中每个示例相关标记集合中最小输出与不相关标记集合中最大输出之间的差异, 并且算法引入松弛变量ξ={ξ1, ξ2, …, ξN}, 用来表示示例对象因没有满足上述间隔要求而产生的损失, 则该算法模型可表示为训练模型共包含q个线性分类器W={wj|wj∈$\mathbb{R}$d, 1≤j≤q}, 其中, 每个参数wj分别对应一个标记类别, 算法所求解的优化问题为:
| $ \begin{array}{l} \begin{array}{*{20}{l}} {\mathop {{\rm{min}}}\limits_{\mathit{\boldsymbol{W}},\xi } \frac{\lambda }{2}\sum\limits_{j = 1}^q {{{\left\| {{\kern 1pt} {\mathit{\boldsymbol{w}}_j}{\kern 1pt} } \right\|}^2}} + \frac{1}{N}\sum\limits_{i = 1}^N {{\xi _i}} }\\ {{\rm{s}}{\rm{. t}}{\rm{.}}} \end{array}\\ \begin{array}{*{20}{l}} {\mathop {{\rm{min}}}\limits_{{y_j} \in {\mathit{\boldsymbol{Y}}_i}} (\mathit{\boldsymbol{w}}_j^{\rm{T}} \cdot {\mathit{\boldsymbol{x}}_i}) - \mathop {\max }\limits_{{y_k} \in {\mathit{\boldsymbol{Y}}_i}} (\mathit{\boldsymbol{w}}_k^{\rm{T}} \cdot {\mathit{\boldsymbol{x}}_i}) \ge 1 - {\xi _i}}\\ {{\xi _i} \ge 0,\forall i \in \{ 1,2, \cdots ,N\} } \end{array} \end{array} $ | (13) |
在上述优化问题中, 目标函数的第一项为正则项约束, 用以衡量模型的复杂度, 第二项为损失函数, 衡量模型在不满足约束条件时的经验损失。约束条件度量了每个示例对象相关标记集合中最小输出与不相关标记集合中最大输出的间隔。
式(13)优化问题在本文中通过改进的次梯度Pegasos算法来解决, 可通过梯度下降与投影2个阶段实现。在每轮迭代中, 随机从训练数据集中抽取一个样本, 判断该样本是否满足式(14):
| $ \mathop {{\rm{min}}}\limits_{{y_j} \in {\mathit{\boldsymbol{Y}}_i}} [\mathit{\boldsymbol{w}}_j^T \cdot \alpha ({\mathit{\boldsymbol{x}}_i},{y_j})] - \mathop {{\rm{max}}}\limits_{{y_k} \notin {\mathit{\boldsymbol{Y}}_i}} [{\mathit{\boldsymbol{w}}_k} \cdot \alpha ({\mathit{\boldsymbol{x}}_i},{y_k})] \le 1 $ | (14) |
| $ \alpha (\mathit{\boldsymbol{x}},y) = \left[ {\begin{array}{*{20}{l}} {\mathit{\boldsymbol{x}} \cdot I(y = {y_1})}\\ {\mathit{\boldsymbol{x}} \cdot I(y = {y_i})}\\ {\mathit{\boldsymbol{x}} \cdot I(y = {y_q})} \end{array}} \right] $ | (15) |
根据梯度下降策略, 模型参数的更新为:
| $ {\mathit{\boldsymbol{w}}_{t + 1/2}} = (1 - {\eta _t}\lambda ){\mathit{\boldsymbol{w}}_t} - {\eta _t}[ - \alpha ({\mathit{\boldsymbol{x}}_i},y_i^*) + \alpha ({\mathit{\boldsymbol{x}}_i},{\bar y_i})] $ | (16) |
当不满足式(14)中的约束条件时, 参数更新策略则通过式(16)进行梯度下降, 此处, ηt=1/(λt)为每次迭代的变动步长, 其随着迭代次数的增加而减少, yi*表示示例的相关标记集合中最小输出对应的标记, yi表示示例的不相关标记集合中最大输出对应的标记。在投影阶段, 根据式(17)对w进行投影:
| $ {\mathit{\boldsymbol{w}}_{t + 1}} = {\rm{min}}\left\{ {1,\frac{{1/\sqrt \lambda }}{{\left\| {{\kern 1pt} {\mathit{\boldsymbol{w}}_{t + 1/2}}{\kern 1pt} } \right\|{\kern 1pt} {{\kern 1pt} _{\rm{F}}}}}} \right\}{\mathit{\boldsymbol{w}}_{t + 1/2}} $ | (17) |
在模型的预测阶段, 给定未知示例对象x, 模型预测出的标记集合为:
| $ h(\mathit{\boldsymbol{x}}) = {\rm{sign }}({f_1}(\mathit{\boldsymbol{x}}) - t(\mathit{\boldsymbol{x}}){f_2}(\mathit{\boldsymbol{x}}) - t(\mathit{\boldsymbol{x}}), \cdots ,{f_q}(\mathit{\boldsymbol{x}}) - t(\mathit{\boldsymbol{x}})) $ | (18) |
其中, t(x)为阈值函数, 本文通过文献[10]算法, 即学习一个线性回归函数来计算t(x)。
优化最小输出与最大输出的间隔损失的多标记学习算法具体步骤如下:
输入 训练数据集D, 平衡参数λ, 迭代终止次数T或迭代终止条件ε
输出 学习到的参数w
步骤1 初始化w, 使得‖w‖F≤1/
步骤2 随机从训练集中抽取一个样本, 检测该样本是否满足式(14)约束条件。
步骤3 若不满足约束条件, 则根据式(16)和式(17)更新w; 否则, 根据式(19)和式(17)更新w。
| $ {\mathit{\boldsymbol{w}}_{t + 1/2}} = (1 - {\eta _t}\lambda ){\mathit{\boldsymbol{w}}_t} $ | (19) |
步骤4 重复步骤2和步骤3, 直到满足判定条件‖▽w‖F≤ε或迭代次数大于T, 终止迭代计算并输出w。
2.2 改进的优化排序多标记学习算法本文2.1节算法只考虑优化示例对象相关标记集合最小输出与不相关标记集合最大输出之间的间隔, 该间隔也即距离分界面最近的标记输出之间的差异。然而, 上述算法对示例所拥有的全部标记信息利用不足, 同时易出现过拟合现象, 因此, 本节对该算法进行改进, 改进算法不仅优化上述间隔, 同时优化模型在示例相关标记集合中的平均输出与不相关标记集合中最大输出之间的间隔, 以及优化模型在示例相关标记集合中的最小输出与不相关标记集合中的平均输出之间的间隔。在上述模型的基础上, 再引入2个松弛变量ξ′={ξ′1, ξ′2, …, ξ′N}和υ′={υ′1, υ′2, …, υ′N}用来表示示例对象没有满足上述间隔要求所产生的损失, 则改进模型所求解的优化问题为:
| $ \begin{array}{l} \mathop {{\rm{min}}}\limits_{\mathit{\boldsymbol{W}},\xi ,{\xi ^\prime },{\nu ^\prime }} \frac{\lambda }{2}\sum\limits_{j = 1}^q {{{\left\| {{\kern 1pt} {\mathit{\boldsymbol{w}}_j}{\kern 1pt} } \right\|}^2}} + \frac{1}{N}\sum\limits_{i = 1}^N {({\xi _i} + \xi _i^\prime + {v_i}^\prime )} \\ {\rm{s}}{\rm{.}}{\kern 1pt} {\kern 1pt} {\rm{t}}{\rm{.}}\\ \mathop {{\rm{min}}}\limits_{{y_j} \in {\mathit{\boldsymbol{Y}}_i}} (\mathit{\boldsymbol{w}}_j^{\rm{T}} \cdot {\mathit{\boldsymbol{x}}_i}) - \mathop {{\rm{max}}}\limits_{{y_k} \notin {\mathit{\boldsymbol{Y}}_i}} (\mathit{\boldsymbol{w}}_k^{\rm{T}} \cdot {\mathit{\boldsymbol{x}}_i}) \ge 1 - {\xi _i}\\ \sum\limits_{{y_j} \in {\mathit{\boldsymbol{Y}}_i}} {(\mathit{\boldsymbol{w}}_j^{\rm{T}} \cdot {\mathit{\boldsymbol{x}}_i})} /|{\mathit{\boldsymbol{Y}}_i}| - \mathop {{\rm{max}}}\limits_{{y_k} \notin {\mathit{\boldsymbol{Y}}_i}} (\mathit{\boldsymbol{w}}_k^{\rm{T}} \cdot {\mathit{\boldsymbol{x}}_i}) \ge 1 - \xi _i^\prime \\ \mathop {{\rm{min}}}\limits_{{y_j} \in {\mathit{\boldsymbol{Y}}_i}} (\mathit{\boldsymbol{w}}_j^{\rm{T}} \cdot {\mathit{\boldsymbol{x}}_i}) - \sum\limits_{{y_k} \notin {\mathit{\boldsymbol{Y}}_i}} {(\mathit{\boldsymbol{w}}_k^{\rm{T}} \cdot {\mathit{\boldsymbol{x}}_i})/(q - |{\mathit{\boldsymbol{Y}}_i}|)} \ge 1 - v_i^\prime \\ {\xi _i} \ge 0,\xi _i^\prime \ge 0,v_i^\prime \ge 0,\forall i \in \{ 1,2, \cdots ,N\} \end{array} $ | (20) |
从上述优化问题可以看出, 当约束条件第一项成立时, 第二项与第三项显然成立; 当约束条件第一项不成立时, 第二项与第三项存在成立的可能性, 且在算法优化过程中的初始阶段, 可以对全部标记所对应的模型参数进行更新, 加快收敛速度。随着迭代次数的增加, 约束条件第二项及第三项在模型参数更新过程中所起的作用越来越小甚至不起作用, 同时第二项及第三项约束条件可以缓和过拟合现象, 该优化问题的求解同样采用改进的次梯度Pegasos算法。
2.3 算法分析由于问题转化方法均涉及改造训练样本数据的问题, 本文所提出的算法与问题转化方法的BR、CC、ECC和LP 4种算法相比, 不涉及改造样本数据, 较好地保留了训练样本数据的原有特征和标记信息。Rank-SVM算法优化每一个训练样本相关标记集合中标记输出与不相关标记集合中标记输出的间隔, 其每一个训练样本对应的约束函数数目为|Yi|·
为了验证本文算法的有效性, 使用来自开源项目Mulan[22]所提供的4个数据集, 其中, emotions来自于音乐情感分类领域, image与scene来自于自然场景分类领域, langlog来自于文本分类领域。数据集的统计信息如表 1所示。
|
下载CSV 表 1 实验数据集信息 Table 1 Experimental dataset information |
在多标记学习问题中, 常用的评价指标为海明损失(Hamming Loss, HL)、排序损失(Ranking Loss, RL)、最前端错误率(One-Error, OE)、覆盖率(Coverage rate, CV)和平均准确率(Average Precision, AP)。各指标具体如下:
1) HL指标考察样本在单个标记上的误分类情况, 即对某个示例对象而言, 不相关的标记被预测为相关或相关的标记被预测为不相关的情况。HL计算如下:
| $ \mathrm{HL}(h)=\frac{1}{N} \sum\limits_{i=1}^{N} \frac{1}{q}\left|h\left(x_{i}\right) \Delta \boldsymbol{Y}_{i}\right| $ | (21) |
2) RL指标考察在样本的语义标记排序序列中出现排序错误的情况。RL计算如下:
| $ {\rm{RL}} (f) = \frac{1}{N}\sum\limits_{i = 1}^N {\frac{{|f({\mathit{\boldsymbol{x}}_i},{y_1}) \le f({\mathit{\boldsymbol{x}}_i},{y_2}),({y_1},{y_2}) \in {\mathit{\boldsymbol{Y}}_i} \times {{\mathit{\boldsymbol{\bar Y}}}_i}|}}{{|{\mathit{\boldsymbol{Y}}_i}| \cdot |{{\mathit{\boldsymbol{\bar Y}}}_i}|}}} $ | (22) |
3) OE指标考察在样本的语义标记排序序列中, 序列最前端的标记不属于样本相关标记集合的情况。OE计算如下:
| $ \mathit{\boldsymbol{OE}}(f) = \frac{1}{N}\sum\limits_{i = 1}^N {\langle \mathop {{\rm{ argmax }}}\limits_{y \in \mathit{\boldsymbol{Y}}} {\kern 1pt} {\kern 1pt} f({\mathit{\boldsymbol{x}}_i},y) \notin {\mathit{\boldsymbol{Y}}_i}\rangle } $ | (23) |
4) CV指标考察在样本的语义标记排序序列中, 覆盖隶属于样本的所有相关标记所需的搜索深度。CV计算如下:
| $ {\rm{CV}}(f) = \frac{1}{N}\sum\limits_{i = 1}^N {\mathop {{\rm{max}}}\limits_{y \in {\mathit{\boldsymbol{Y}}_i}} } {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{ran}}{{\rm{k}}_f}({\mathit{\boldsymbol{x}}_i},y) - 1 $ | (24) |
5) AP指标考察在样本的语义标记排序序列中, 排在隶属于该样本的相关标记之前的标记仍属于样本相关标记集合的情况。AP计算如下:
| $ \begin{array}{*{20}{l}} { {\rm{AP}} (f) = }\\ {\frac{1}{N}\sum\limits_{i = 1}^N {\frac{1}{{{\mathit{\boldsymbol{Y}}_i}}}} \sum\limits_{y \in {\mathit{\boldsymbol{x}}_i}} {\frac{{|{y^\prime }| {\rm{ran}}{{\rm{k}}_f}({\mathit{\boldsymbol{x}}_i},{y^\prime }) \le {\rm{ran}}{{\rm{k}}_f}({\mathit{\boldsymbol{x}}_i},y),{y^\prime } \in {\mathit{\boldsymbol{Y}}_i}|}}{{ {\rm{ran}}{{\rm{k}}_f}({\mathit{\boldsymbol{x}}_i},y)}}} } \end{array} $ | (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次交叉验证后的均值, 以排除随机性, 最优结果加粗表示。
|
下载CSV 表 2 海明损失结果对比 Table 2 Comparison of Hamming loss results |
|
下载CSV 表 3 排序损失结果对比 Table 3 Comparison of ranking loss results |
|
下载CSV 表 4 最前端错误率结果对比 Table 4 Comparison of one-error results |
|
下载CSV 表 5 覆盖率结果对比 Table 5 Comparison of coverage rate results |
|
下载CSV 表 6 平均准确率结果对比 Table 6 Comparison of average precision results |
从表 2~表 6可以看出, 在4个多标记数据集中, 本文提出的2种算法的5个评价指标均取得了较好的效果, 与3种多标记学习算法相比, 评价指标结果接近, 表明本文2种算法可以实现多标记分类。实验结果也表明, 考虑相关标记集合的平均输出与不相关标记集合的平均输出, 即本文第2种算法在5种评价指标表现上均优于本文第1种算法, 表明考虑平均输出的算法能够提升基于间隔准则的分类器性能。
4 结束语受基于间隔准则的多分类支持向量机的启发, 本文通过优化示例相关标记集合中最小输出与不相关标记集合中最大输出的间隔损失, 以实现示例对应的标记集合排序。为了在模型参数训练过程中充分利用标记空间的全部标记信息, 进一步优化示例相关标记集合平均输出与不相关标记集合中最大输出的间隔损失, 以及示例相关标记集合中最小输出与不相关标记集合中平均输出的间隔损失。实验结果表明, 与ML-RBF、BP-MLL和ML-KNN多标记学习算法相比, 本文提出的2种算法在4个多标记数据集上均取得了相近的分类性能。本文假设训练样本与标记之间呈线性关系, 且算法未考虑标记之间存在的相关性, 下一步考虑将特征空间扩展到再生核希尔伯特空间中进行学习, 并结合标记之间的相关性来提高分类效果。
| [1] |
SCHAPIRE R E, SINGER Y. BoosTexter:a Boosting-based system for text categorization[J]. Machine Learning, 2000, 39(2/3): 135-168. DOI:10.1023/A:1007649029923 |
| [2] |
DE COMITÉ F, GILLERON R, TOMMASI M.Learning multi-label alternating decision trees from texts and data[M]//PETRA P.Machine learning and data mining in pattern recognition.Berlin, Germany: Springer, 2003: 35-49.
|
| [3] |
BOUTELL M R, LUO J B, SHEN X P, et al. Learning multi-label scene classification[J]. Pattern Recognition, 2004, 37(9): 1757-1771. DOI:10.1016/j.patcog.2004.03.009 |
| [4] |
BARUTCUOGLU Z, SCHAPIRE R E, TROYANSKAYA O G. Hierarchical multi-label prediction of gene function[J]. Bioinformatics, 2006, 22(7): 830-836. DOI:10.1093/bioinformatics/btk048 |
| [5] |
TSOUMAKAS G, KATAKIS I. Multi-label classification[J]. International Journal of Data Warehousing and Mining, 2007, 3(3): 1-13. |
| [6] |
ZHANG Minling, ZHOU Zhihua. A review on multi-label learning algorithms[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(8): 1819-1837. DOI:10.1109/TKDE.2013.39 |
| [7] |
READ J, PFAHRINGER B, HOLMES G, et al. Classifier chains for multi-label classification[J]. Machine Learning, 2011, 85(3): 333-359. DOI:10.1007/s10994-011-5256-5 |
| [8] |
CHEN Linlin, CHEN Degang. A classifier chain method for multi-label learning based on kernel alignment[J]. Journal of Nanjing University(Natural Sciences), 2018, 54(4): 67-74. (in Chinese) 陈琳琳, 陈德刚. 一种基于核对齐的分类器链的多标记学习算法[J]. 南京大学学报(自然科学版), 2018, 54(4): 67-74. |
| [9] |
TSOUMAKAS G, KATAKIS I, VLAHAVAS I. Random k-labelsets for multilabel classification[J]. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(7): 1079-1089. DOI:10.1109/TKDE.2010.164 |
| [10] |
ELISSEEFF A, WESTON J.A kernel method for multi-labelled classification[C]//Proceedings of the 14th International Conference on Neural Information Processing Systems.New York, USA: ACM Press, 2001: 681-687.
|
| [11] |
JIANG A W, WANG C H, ZHU Y P.Calibrated Rank-SVM for multi-label image categorization[C]//Proceedings of 2008 IEEE International Joint Conference on Neural Networks.Washington D.C., USA: IEEE Press, 2008: 15-26.
|
| [12] |
VAPNIK V. The nature of statistical learning theory[M]. Berlin, Germany: Springer, 1995.
|
| [13] |
ZHANG M L, ZHOU Z H. Multilabel neural networks with applications to functional genomics and text categorization[J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(10): 1338-1351. DOI:10.1109/TKDE.2006.162 |
| [14] |
GRODZICKI R, MANDZIUK J, WANG L P.Improved multilabel classification with neural networks[M]//GÜNTERRUDOLP H, THOMASJANSE N, SIMONLUCA S, et al.Parallel problem solving from nature-PPSN X.Berlin, Germany: Springer, 2008: 409-416.
|
| [15] |
ZHANG M L, ZHOU Z H. ML-KNN:a lazy learning approach to multi-label learning[J]. Pattern Recognition, 2007, 40(7): 2038-2048. DOI:10.1016/j.patcog.2006.12.019 |
| [16] |
ZHANG Minling. An improved multi-label lazy learning approach[J]. Journal of Computer Research and Development, 2012, 49(11): 2271-2282. (in Chinese) 张敏灵. 一种新型多标记懒惰学习算法[J]. 计算机研究与发展, 2012, 49(11): 2271-2282. |
| [17] |
SHALEV-SHWARTZ S, SINGER Y, SREBRO N, et al. Pegasos:primal estimated sub-gradient solver for SVM[J]. Mathematical Programming, 2011, 127(1): 3-30. DOI:10.1007/s10107-010-0420-4 |
| [18] |
ZHANG Shijiang, CHAI Jing. Partial label learning algorithm based on maximum margin[J]. Science Technology and Engineering, 2018, 18(28): 114-120. (in Chinese) 张仕将, 柴晶. 一种基于最大间隔的偏标记学习算法[J]. 科学技术与工程, 2018, 18(28): 114-120. |
| [19] |
CRAMMER K, SINGER Y. On the algorithmic implementation of multiclass kernel-based vector machines[J]. Journal of Machine Learning Research, 2002, 2(2): 265-292. |
| [20] |
TANG L, XUAN Q, XIONG R, et al. A multi-class large margin classifier[J]. Journal of Zhejiang University-Science A, 2009, 10(2): 253-262. DOI:10.1631/jzus.A0820122 |
| [21] |
LI Yukun, ZHANG Minling, GENG Xin.Leveraging implicit relative labeling-importance information for effective multi-label learning[C]//Proceedings of 2015 IEEE International Conference on Data Mining.Washington D.C., USA: IEEE Press, 2015: 123-156.
|
| [22] |
TSOUMAKAS G, VILCEK J, XIOUFITS E S.Mulan: a Java library for multi-label learning[EB/OL].[2019-03-10].http://mulan.sourceforge.net/datasets.html.
|
| [23] |
ZHANG Minling. ML-RBF:RBF neural networks for multi-label learning[J]. Neural Processing Letters, 2009, 29(2): 61-74. DOI:10.1007/s11063-009-9095-3 |