来源
Binary relevance for multi-label learning – Zhang, Li, Liu, Geng, 2018, [Frontiers of Computer Science]
传统的二元相关性方法
1、 二元相关性方法依赖概念的简洁。它是一个一阶方法,忽略了标签间的相关性,其计算复杂度与标签空间的大小呈线性关系。
2、 它是一种问题转换法。它可以将多标签问题转化为二元分类问题。
3、 它优化了宏平均(Macro-average)的多标签指标。
4、 它能轻易地适应缺失标签的训练集。
提升二元相关性方法的泛化能力的两个方法
1、开发标签间的相关关系。
2、研究标签内在属性,例如标签不平衡状态、标签间的相对重要性。
标签间相关关系开发
1、 假设随机标签相关的链结构,如分类器链算法。
2、 假设全序标签相关的堆栈结构,如堆栈式集成分类器算法。
3、 假设标签相关性剪枝的控制结构,LEAD算法。
链式结构
核心思想:分类器链是一种高阶算法,按照特定顺序排列分类器的顺序,将这一个分类器的结果 y^\ast
作为 x
的额外特征来训练,得到新的训练集。
一般的分类器链算法:
利用多标签训练集的m
个训练数据\left(x,y_i\right)
:
\mathcal{D}_\mathcal{j}=\{\left(x^i,y_j^i\right)\mid1\le i\le m\}
按算法指定顺序\pi
生成训练数据:
\mathcal{D}_{\pi\left(\mathcal{j}\right)}=\left\{\left(\left[\boldsymbol{x}^{i},y_{\pi\left(1\right)}^i,\ldots,y_{\pi\left(j-1\right)}^i\right],y_{\pi\left(j\right)}^i\right)\mid1\le i\le m\right\}
在 q
个分类中,按照特定顺序 \pi
训练分类器,对每个数据应用二元学习算法 \mathcal{B}
:
g_\pi\left(j\right):\mapsto\mathcal{B}\left(\mathcal{D}_\pi\left(j\right)\right)
例如,对于第 j\left(1\le j\le q\right)
个分类器,按照一定的顺序先由 \left(x,y_1\right)
训练出 y_1
的分类器,再利用\left(x,y_1,y_2\right)
训练 y_3
的分类器,以此类推,从\ \left(x,y_1,\ldots,y_n\right)
得到最后的分类器。其中y_1,y_2,\ldots,y_q
的生成顺序\pi根据具体算法而定。g_{\pi\left(j\right)}
同时决定了标签\lambda_j
与其他标签的相关性。
输入一个未知向量x^\ast
,按照顺序 \pi
应用分类器 g_j
算法将预测输出标签空间 \mathcal{Y}
内的 Y^\ast
,输出概率,最终得出所有的分类标签:
\eta_{\pi\left(1\right)}^{x^\ast}=sign\left[g_{\pi\left(1\right)}\left(x^\ast\right)\right]
\\
\eta_{\pi\left(j\right)}^{x^\ast}=sign\left[g_{\pi\left(j\right)}\left(\left[x^\ast,\eta_{\pi\left(1\right)}^{x^\ast},\ldots,\eta_{\pi\left(j-1\right)}^{x^\ast}\right]\right)\right]
\\
Y^\ast=\left\{\lambda_{\pi\left(j\right)}\mid\eta_{\pi\left(j\right)}^{x^\ast}=+1,1\le j\le q\right\}
还值得注意的是,先前分类器中发生的预测错误将沿着链结构传播到后续分类器,并且如果容易出错的分类标签碰巧放置在起始链接位置,则这些不良影响会变得更加明显。在训练阶段,我们用的是y真值,而在预测阶段,我们用的是分类器给出的值,纠正这种差异的办法是,统一都用分类器给出的值。从概率论的视角来说,分类器链通过条件概率预测结果:
p\left(y\mid x\right)=\prod_{j=1}^{q}{p\left(y_{\pi\left(j\right)}\mid x,y_{\pi\left(1\right)},\ldots,y_{\pi\left(j-1\right)}\right)}
堆栈结构
核心思想:堆叠式的分类器算法假设标签间皆存在相关关系,利用的是标签间的全序结构,集成所有基础分类器来得到标签关系。
堆叠式分类器算法:
利用训练集数据训练 j
个基础分类器 g_j
,它是数据集在通过学习算法生成的映射:
\mathcal{D}_\mathcal{j}=\{\left(x^i,y_j^i\right)\mid1\le i\le m\} \\
g_j:\mapsto\mathcal{B}\left(\mathcal{D}_{\left(\mathcal{j}\right)}\right)
利用训练集数据和基础分类器的结果 \mathcal{D}_j^M
,训练 j
个元分类器 \ g_j^M
:
\mathcal{D}_j^M=\left\{\left(\left[x^i,sign\left[g_2\left(x^i\right)\right],\ldots,sign\left[g_q\left(x^i\right)\right]\right],y_j^i\right)\mid1\le i\le m\right\}
利用 g_j^M
和 g_j
推导出结果标签集:
Y^\ast=\left\{\lambda_j\mid g_j^M\left(\tau^{x^\ast}\right)>0,1\le j\le q\right\}
\\
\text{where }\tau^{x^\ast}=\left[x^\ast,sign\left[g_1\left(x^\ast\right)\right],\ldots,sign\left[g_q\left(x^\ast\right)\right]\right]
评价:同样,与分类器链类似,训练阶段使用真值而预测阶段使用分类器预测值,会让输入空间造成差异。最好是统一训练和预测的y值。除了元分类器输出结果,还能汇总元分类器和基础分类器来输出预测结果。除了使用二元标签分配作为额外的堆叠功能外,还可以采用特定技术来生成量身定制的堆叠功能,如判别分析和规则学习。
贝叶斯网络
贝叶斯网络利用DAG表述条件概率模型。图中的节点代表随机变量,可以是可观察到的变量,或隐变量、未知参数等。认为有因果关系(或非条件独立)的变量或命题则用箭头来连接。若两个节点间以一个单箭头连接在一起,表示其中一个节点是“因(parents)”,另一个是“果(children)”,两节点就会产生一个条件概率值。总而言之,连接两个节点的箭头代表此两个随机变量是具有因果关系,或者非条件独立。假设节点E直接影响到节点H,即E→H,则用从E指向H的箭头建立结点E到结点H的有向弧(E,H),权值(即连接强度)用条件概率P(H|E)来表示。把某个研究系统中涉及的随机变量,根据是否条件独立绘制在一个有向图中,就形成了贝叶斯网络。其主要用来描述随机变量之间的条件依赖,用圆圈表示随机变量(random variables),用箭头表示条件依赖(conditional dependencies)。
对于任意的随机变量,其联合概率可由各自的局部条件概率分布相乘而得出:
p\left(y\mid x\right)=\prod_{j=1}^{q}{p\left(y_i\mid p a_j,x\right)}
恰好可以应用在开发标签间关系上。
导致图结构难以生成的原因:
1、 混合类型,x
是连续变量,标签 y
是离散变量。
2、 计算复杂度很高
LEAD算法
核心思想:估计特征的影响以简化贝叶斯网络的生成过程。
LEAD一般算法:
按照独立按每个标签训练各自的二元分类器 g_j
。
根据训练集 \mathcal{D}_\mathcal{j}
的每个 x
进行计算,对每个标签引入误差随机变量:
e_j=y_j-sign\left(g_j\left(x\right)\right)
使用现成的工具的贝叶斯学习算法,根据误差随机变量建立贝叶斯网络结构。
\mathcal{G}\gets\mathcal{L}\left(e_1,e_2,\ldots,e_q\right)
类似于之前两种结构的训练过程,按照网络结构得到每个标签的特定分类器组合,输入特征,训练二元模型:
\eta_{\pi^G\left(1\right)}^{x^\ast}=sign\left[g_{\pi^G\left(1\right)}^G\left(x^\ast\right)\right]
\\
\eta_{\pi^G\left(j\right)}^{x^\ast}=sign\left[g_{\pi^G\left(j\right)}^G\left(\left[x^\ast,\left\langle\eta_a^{x^\ast}\right\rangle_{y_a\in p a_nG_{\left(j\right)}}\right]\right)\right]
\\
g_j^\mathcal{G}:\mapsto\mathcal{B}\left(\mathcal{D}_\mathcal{j}^\mathcal{G}\right)
按照贝叶斯网络的图结构确定分类器排序,依次判断每个标签:
Y^\ast=\left\{\lambda_{\pi^G\left(j\right)}\mid\eta_{\pi^G\left(j\right)}^{x^\ast}=+1,1\le j\le q\right\}
标签间关系剪枝还有其他方法:
1、 基于树的贝叶斯网络,用作简化的DAG,通过修剪(最多)有一个父标签的标签来考虑二阶关系。
2、 通过为堆叠的元分类器,修剪基分类器的不相关输出,堆栈式结构的改造能满足受控的标签间相关关系开发。
3、带有易错预测的标签甚至可以从标签池中过滤掉,以进行相关关系开发。
标签内在属性开发的算法
关注训练集标签不平衡问题
标签空间中存在大量标签时,标签数量不平衡现象大量存在。不平衡指标为:
ImR_j=\frac{max\left(\left|\mathcal{D}_\mathcal{j}^+\right|,\left|\mathcal{D}_\mathcal{j}^-\right|\right)}{min\left(\left|\mathcal{D}_\mathcal{j}^+\right|,\left|\mathcal{D}_\mathcal{j}^-\right|\right)}
现有方法采用二元相关性算法作为学习过程的中间步骤,来解决标签不平衡问题,例如过采样、欠采样、阈值决策边界。然而它们忽略了利用标签间的相关性。
COCOA算法
交叉解耦聚集(cross-coupling aggregation),高阶方法,利用标签相关性研究标签失衡问题。在训练阶段,成对标签耦合用以开发标签关系。在判别阶段,由类不平衡学习算法生成的聚集分类器,研究标签类不平衡。
一般算法描述:
对于每个标签j进行如下步骤:
按类不平衡的二元学习算法,训练常规的二元分类器 g_j^I
。
\mathcal{D}_\mathcal{j}=\{\left(x^i,y_j^i\right)\mid1\le i\le m\}
\\
g_j^I:\mapsto\mathcal{B}^I\left(\mathcal{D}_{\left(\mathcal{j}\right)}\right)
生成一个K标签随机子集 J_K\subset\mathcal{Y}\left\{\lambda_j\right\}
对于每个 \lambda_k\in J_K
,每个成对标签,有三元训练集
\mathcal{D}^{\boldsymbol{tri}} = \{ \boldsymbol{x}^i , \psi^{\boldsymbol{tri}}(\boldsymbol{y}^i , \lambda_j, \lambda_k )) \mid 1 \le i \le m \}
\\
\text{where }
\psi^{\boldsymbol{tri}}(\boldsymbol{y}^i , \lambda_j, \lambda_k ) =
\left \{
\begin{aligned}
0, & \text{ if } y_j^i = -1 \text{ and } y_k^i = -1 \\
+1, & \text{ if } y_j^i = -1 \text{ and } y_k^i = +1 \\
+2, & \text{ if } y_j^i = +1
\end{aligned}
\right .
\left(y_j^i,y_k^i\right) |
+1, +1 | +1, -1 | -1, +1 | -1, -1 |
---|---|---|---|---|
2 | 2 | 1 | 0 |
由此,训练类不平衡学习算法 g_{jk}^I:\gets\mathcal{M}^I\left(\mathcal{D}_{jk}^{tri}\right)
至此,训练结束,通过判别算法计算标签
Y^\ast=\left\{\lambda_j\mid f_j\left(x^\ast\right)>t_j,1\le j\le q\right\}
\\
\text{where }f_j\left(x^\ast\right)=g_j^I\left(x^\ast\right)+\sum_{\lambda_k\in J_K}{g_{jk}^I\left(x^\ast,+2\right)}
通过 K+1
个分类器判断是否是正类。阈值 t_j
可通过F度量判断和某些经验指标确定。
精确率是针对我们预测结果而言的,它表示的是预测为正的样本中有多少是真正的正样本。那么预测为正就有两种可能了,一种就是把正类预测为正类(TP),另一种就是把负类预测为正类(FP),也就是
P=\frac{TP}{TP+FP}
而召回率是针对我们原来的样本而言的,它表示的是样本中的正例有多少被预测正确了。那也有两种可能,一种是把原来的正类预测成正类(TP),另一种就是把原来的正类预测为负类(FN)。
R=\frac{TP}{TP+FN}
在信息检索领域,精确率和召回率又被称为查准率和查全率,
查准率=检索出的相关信息量 / 检索出的信息总量 \
查全率=检索出的相关信息量 / 系统中的相关信息总量
F 度量为
F = \frac{2\times P\times R}{P+R}
关注标签相对重要性
以往的多标签方法都默认标签之间都有同等的重要性,然而,现实场景中相关性标签,重要性常常是不同的,而且不能从训练集中获得其信息。如下图,显示了一个多标签自然场景图像,其相关的标签重要性递减:天空 ? 水 ? 云 ? 建筑物 ? 行人。类似的情况也适用于其他类型的多标签对象,例如具有不同主题重要性的多类别文档,具有不同表达水平的多功能基因等。
也有一些利用辅助信息的算法,如每个标签的全序排序的定序尺度、相关标签的全排序、所有标签的重要性分布、对未标记实体查询标签的Oracle反馈。但在标准的多标签学习问题中,唯一可用的信息只有实体与标签的相关性。通过利用隐式的标签相对重要性,多标签学习的泛化能力可以进一步增强。
RELIAB算法
算法一般性描述:
第一阶段计算相对重要性 \mathcal{U}=\{\mu_{x_i}^{\lambda_i}|1\le i\le m,1\le j\le q\}
构建全连接图 G=\left(V,E\right)
,其中 V=\{x^i|1\le i\le m\}
,为图构建相似度矩阵 W=\left[w_{ik}\right]_{m\times m}
,其中i
不等于k
时,该标签与其他标签比较,通过高斯核函数计算相似
\forall_{i, k=1}^{m}: w_{i k}=\left\{\begin{array}{cl}
\exp \left(-\frac{\left\|x^{i}-x^{k}\right\|_{2}^{2}}{2 \sigma^{2}}\right), & \text { if } i \neq k \\
0, & \text { if } i=k
\end{array}\right.
得出标签传播矩阵
P=D^{-\frac{1}{2}}WD^{-\frac{1}{2}} \\
\text{ where }D=diag\left[d_1,d_2,\ldots,d_m\right]\mathrm{\ with\ }d_i=\sum_{k=1}^{m}w_{ik}
初始化标签重要性矩阵 R=\left[r_{ij}\right]_{m\times q}
R^{\left(0\right)}=\Phi=\left[\phi_{ij}\right]_{m\times q}
迭代传播标签重要性矩阵
R^{\left(t\right)}=\alpha PR^{\left(t-1\right)}+\left(1-\alpha\right)\Phi
最终R收敛于 R^\ast
,得出标签相对重要性
\forall1\le i\le m,\forall1\le j\le q:\mu_{x_i}^{\lambda_j}=\frac{r_{ij}^\ast}{\sum_{j=1}^{q}r_{ij}^\ast}
第二阶段,选择最大熵模型参数化多标签预测变量
f_j\left(x\right)=\frac{1}{Z\left(x\right)}\exp{\left(\theta_j^\top x\right)}\left(1\le j\le q\right)
\\
\mathrm{\ where\ }Z\left(x\right)=\sum_{j=1}^{q}exp\left(\theta_j^\top x\right)
最大化目标函数以得出参数
V\left(\Theta,\mathcal{U},\mathcal{D}\right)=V_{dis}\left(\Theta,\mathcal{U}\right)+\beta\cdot V_{emp}\left(\Theta,\mathcal{D}\right)
第一项的 V_{dis}\left(\Theta,\mathcal{U}\right)
评估预测模型的效果与相对标签重要性信息 \mathcal{U}
的拟合程度(如通过Kullback-Leibler
散度),第二项评估预测模型 \Theta
在训练集 \mathcal{D}
上的分类能力(如经验排序损失)。\beta
是平衡目标函数这两项的正则化参数。
最后,对任意新样本 x^\ast
输出结果标签 Y^\ast
Y^\ast=\{\lambda_j|f_j\left(x^\ast\right)>t\left(x^\ast\right),1\le j\le q\}