来源

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 .

由此，训练类不平衡学习算法 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\}