NIPS-2023《Partial Label Learning with Dissimilarity Propagation guided Candidate Label Shrinkage》

核心思想

这篇论文提出了一种名为 DPCLS（Dissimilarity Propagation guided Candidate Label Shrinkage） 的新型部分标签学习（Partial Label Learning, PLL）方法。部分标签学习是一种弱监督学习框架，其中每个样本关联一组候选标签，但只有一个标签是真实的（ground-truth）。PLL 的核心挑战在于从候选标签集中识别出真实的标签（即标签消歧）。

DPCLS 的核心思想在于：

1. 利用标签空间和特征空间的信息：通过构建语义不相似矩阵（dissimilarity matrix）和相似矩阵（similarity matrix），并利用它们之间的对抗关系（adversarial relationship）来缩小标签置信度矩阵的解空间，从而提高标签消歧的准确性。
2. 不相似性传播：初始不相似矩阵基于候选标签集的补集构建，但较为稀疏。通过利用样本的局部几何结构（local geometric structure）传播不相似关系，生成更稠密的不相似矩阵。
3. 对抗先验：相似矩阵（基于标签置信度矩阵）和不相似矩阵之间的对抗关系被用来优化标签置信度矩阵，同时优化后的标签置信度矩阵反过来促进不相似矩阵的改进。
4. 非线性扩展：通过核方法扩展模型，捕捉特征空间中的非线性关系，提升模型的泛化能力。

目标函数

DPCLS 的目标函数综合了回归损失、正则化项、对抗项和不相似性传播正则化项，形式化定义如下：

$$\underset{W,F,D}{\min }{\Vert XW-F\Vert }_F^2+\lambda {\Vert W\Vert }_F^2+\alpha {\Vert D\odot F{F}^T\Vert }_1+\beta \text{Tr}(DL{D}^T)$$

约束条件：
$$F{1}_q=1_m,0_{m\times q}\le F\le Y,0_{m\times m}\le D\le 1_{m\times m},D_{ij}=D_{ij}^0,\text{if }{D}_{ij}^0=1$$

符号说明：

• $X\in {\mathbb{R}}^{m\times d}$：特征矩阵，$m$ 为样本数，$d$ 为特征维度。
• $F\in {\mathbb{R}}^{m\times q}$：标签置信度矩阵，$F_{ij}$ 表示第 $i$ 个样本的第 $j$ 个标签为真实标签的概率。
• $W\in {\mathbb{R}}^{d\times q}$：特征到标签置信度的映射矩阵。
• Y∈{0,1}m×qY \in \{0, 1\}^{m \times q}Y∈{0,1}m×q：部分标签矩阵，$Y_{ij}=1$ 表示第 $j$ 个标签是第 $i$ 个样本的候选标签。
• $D\in {\mathbb{R}}^{m\times m}$：优化的不相似矩阵，$D^0$ 为初始不相似矩阵。
• $L=D_S-S$：图拉普拉斯矩阵，$S$ 为基于特征空间局部几何结构的相似矩阵，$D_S$ 为 $S$ 的对角矩阵。
• $\lambda ,\alpha ,\beta$：超参数，分别控制正则化、对抗项和不相似性传播的权重。
• $\odot$：元素-wise 乘法，$\Vert \cdot {\Vert }_F$：Frobenius 范数，$\Vert \cdot {\Vert }_1$：$l_1$ 范数，$\text{Tr}(\cdot )$：矩阵迹。

目标函数组成部分：

1. 回归损失：${\Vert XW-F\Vert }_F^2$，确保特征矩阵 $X$ 通过线性映射 $W$ 能够准确预测标签置信度矩阵 $F$。
2. 正则化项：$\lambda {\Vert W\Vert }_F^2$，防止过拟合。
3. 对抗项：$\alpha {\Vert D\odot F{F}^T\Vert }_1$，利用不相似矩阵 $D$ 和相似矩阵 $F{F}^T$ 的对抗关系，缩小 $F$ 的解空间。
4. 不相似性传播正则化：$\beta \text{Tr}(DL{D}^T)$，通过图拉普拉斯矩阵 $L$ 确保特征空间中相似的样本具有相似的的不相似编码。

目标函数优化过程

为优化目标函数，论文采用 不精确增广拉格朗日乘子法（Inexact Augmented Lagrange Multiplier, IALM），通过引入辅助矩阵 $A=D$ 将问题分解为多个子问题，迭代求解。优化过程如下：

1. 引入辅助矩阵并构造增广拉格朗日函数

为便于优化，引入辅助矩阵 $A\in {\mathbb{R}}^{m\times m}$，并将目标函数重写为：

$$\underset{W,F,D,A}{\min }{\Vert XW-F\Vert }_F^2+\lambda {\Vert W\Vert }_F^2+\alpha {\Vert A\odot F{F}^T\Vert }_1+\beta \text{Tr}(DL{D}^T)$$

约束：
$$F{1}_q=1_m,0_{m\times q}\le F\le Y,D=A,0_{m\times m}\le A\le 1_{m\times m},A_{ij}=D_{ij}^0,\text{if }{D}_{ij}^0=1$$

增广拉格朗日函数为：

$$\underset{W,F,D,A}{\min }{\Vert XW-F\Vert }_F^2+\lambda {\Vert W\Vert }_F^2+\alpha {\Vert A\odot F{F}^T\Vert }_1+\beta \text{Tr}(DL{D}^T)+⟨\Phi ,D-A⟩+\frac{\mu }{2}{\Vert D-A\Vert }_F^2$$

其中，$\Phi \in {\mathbb{R}}^{m\times m}$ 为拉格朗日乘子矩阵，$\mu \ge 0$ 为惩罚参数，$⟨\cdot ,\cdot ⟩$ 表示矩阵内积。

2. 子问题分解与优化

优化过程通过交替优化以下子问题完成：

（1）W 子问题：
$$\underset{W}{\min }{\Vert XW-F\Vert }_F^2+\lambda {\Vert W\Vert }_F^2$$
这是一个标准的正则化最小二乘问题，闭式解为：
$$W=(X^{T}X+\lambda I{)}^{-1}{X}^{T}F$$

核扩展版本：
为捕捉非线性关系，引入核函数 $\varphi (\cdot )$，将 $W$ 表示为 $W=\varphi (X{)}^{T}H$，其中 $H\in {\mathbb{R}}^{m\times q}$ 为权重矩阵，核矩阵 $K=\varphi (X)\varphi (X{)}^T$。目标函数变为：
$$\underset{H,b}{\min }{\Vert KH+1_m{b}^T-F\Vert }_F^2+\lambda \text{Tr}(H^{T}KH)$$
求解 $H$ 和偏置 $b$：
$$H={\left(K+\lambda I_{m\times m}-\frac{1}{m}{1}_m{1}_m^{T}K\right)}^{-1}\left(F-\frac{1}{m}{1}_m{1}_m^{T}F\right),b=\frac{1}{m}\left(F^T{1}_m-H^T{K}^T{1}_m\right)$$

（2）F 子问题：
$$\underset{F}{\min }{\Vert F-P\Vert }_F^2+\alpha {\Vert A\odot F{F}^T\Vert }_1,\text{s.t.}F{1}_q=1_m,0_{m\times q}\le F\le Y$$
其中 $P=KH+1_m{b}^T$。这是一个带约束的二次规划（QP）问题，可通过标准 QP 工具求解。

（3）D 子问题：
$$\underset{D}{\min }\beta \text{Tr}(DL{D}^T)+\frac{\mu }{2}{\Vert D-A+\frac{\Phi }{\mu }\Vert }_F^2$$
令一阶导数为零，得到闭式解：
$$D=\left(\mu A-\Phi \right){\left(2\beta L+\mu I_{m\times m}\right)}^{-1}$$

（4）A 子问题：
$$\underset{A}{\min }\alpha {\Vert A\odot F{F}^T\Vert }_1+\frac{\mu }{2}{\Vert D-A+\frac{\Phi }{\mu }\Vert }_F^2,\text{s.t.}{0}_{m\times m}\le A\le 1_{m\times m},A_{ij}=D_{ij}^0,\text{if }{D}_{ij}^0=1$$
此问题可按元素分解求解：
$$A=T\left(T_1\left(T_0\left(\frac{\mu D+\Phi -\alpha F{F}^T}{\mu }\right)\right)\right)$$
其中，$T(C_{ij})=1$（若 $D_{ij}^0=1$），$T_1(C_{ij})=\min (1,C_{ij})$，$T_0(C_{ij})=\max (0,C_{ij})$。

（5）更新拉格朗日乘子和惩罚参数：
$$\Phi \leftarrow \Phi +\mu (D-A),\mu \leftarrow \min (1.1\mu ,{\mu }_{\text{max}})$$
其中，${\mu }_{\text{max}}=10^{10}$。

3. 终止条件

迭代直到满足收敛条件：${\Vert D-A\Vert }_{\infty }<10^{-8}$，其中 ${\Vert \cdot \Vert }_{\infty }$ 表示矩阵的无穷范数。

4. 预测

对于测试样本 $\hat{x}$，预测标签为：
$$\hat{y}=\arg \underset{k}{\max }\sum _{i=1}^m{H}_{ik}K(\hat{x},x_i)+b_k$$

主要贡献点

1. 提出对抗先验：通过相似矩阵 $F{F}^T$ 和不相似矩阵 $D$ 的对抗关系，缩小标签置信度矩阵 $F$ 的解空间，提高标签消歧的准确性。
2. 不相似性传播：通过利用特征空间的局部几何结构，增强初始稀疏的不相似矩阵 $D^0$，生成更稠密的 $D$，从而捕捉更丰富的样本间关系。
3. 核扩展：将线性模型扩展为核方法，捕捉特征空间中的非线性关系，提升模型的泛化能力。
4. 理论保证：通过 Rademacher 复杂度和误差界分析，证明了模型的泛化性能和对抗先验的合理性（Theorem 1 和 Theorem 2）。
5. 优越的实验表现：在10个合成数据集和7个真实世界数据集上，DPCLS 显著优于8种浅层 PLL 方法和3种深度 PLL 方法，展示了其鲁棒性和竞争力。

算法实现过程

论文提供了 DPCLS 的伪代码（Algorithm 1），以下是详细的实现步骤：

输入

• 部分标签训练集 $D=\{(x_i,S_i)|1\le i\le m\}$。
• 超参数：$\lambda$（正则化权重，设为 0.05），$\alpha$（对抗项权重，从 {0.001,0.01}\{0.001, 0.01\}{0.001,0.01} 中选择），$\beta$（不相似性传播权重，设为 0.001），$k$（k-近邻数，设为 10）。
• 测试样本 $\hat{x}$。

输出

• 测试样本的预测标签 $\hat{y}$。

算法步骤

1. 初始化：

   • 根据公式 (2) 构造初始不相似矩阵 $D^0$：
     $$D_{ij}^0=\{\begin{array}{ll}1,& \text{if }{y}_i{y}_j^T=0\\ 0,& \text{otherwise}\end{array}$$
   • 构造核矩阵 $K$，使用 RBF 核：$K(x_i,x_j)=\exp \left(-\frac{\Vert x_i-x_j{\Vert }_2^2}{2{\sigma }^2}\right)$。
   • 初始化 $D=A=\Phi =0_{m\times m}$，$\mu =10^{-4}$。

2. 迭代优化（直到收敛）：

   • 更新 $H$ 和 $b$：根据公式 (11) 计算核扩展模型的权重和偏置：
     $$H={\left(K+\lambda I_{m\times m}-\frac{1}{m}{1}_m{1}_m^{T}K\right)}^{-1}\left(F-\frac{1}{m}{1}_m{1}_m^{T}F\right),b=\frac{1}{m}\left(F^T{1}_m-H^T{K}^T{1}_m\right)$$
   • 更新 $F$：通过求解公式 (12) 的二次规划问题，更新标签置信度矩阵 $F$。
   • 更新 $D$：根据公式 (14) 计算不相似矩阵：
     $$D=\left(\mu A-\Phi \right){\left(2\beta L+\mu I_{m\times m}\right)}^{-1}$$
   • 更新 $A$：根据公式 (16) 按元素更新辅助矩阵 $A$：
     $$A=T\left(T_1\left(T_0\left(\frac{\mu D+\Phi -\alpha F{F}^T}{\mu }\right)\right)\right)$$
   • 更新 $\Phi$ 和 $\mu$：根据公式 (17) 更新拉格朗日乘子和惩罚参数：
     $$\Phi \leftarrow \Phi +\mu (D-A),\mu \leftarrow \min (1.1\mu ,10^{10})$$
   • 检查收敛条件：若 ${\Vert D-A\Vert }_{\infty }<10^{-8}$，则停止迭代。

3. 预测：

   • 对于测试样本 $\hat{x}$，根据公式 (18) 计算预测标签：
     $$\hat{y}=\arg \underset{k}{\max }\sum _{i=1}^m{H}_{ik}K(\hat{x},x_i)+b_k$$

超参数设置

• $\lambda =0.05$：控制模型复杂度，防止过拟合。
• α∈{0.001,0.01}\alpha \in \{0.001, 0.01\}α∈{0.001,0.01}：控制对抗项的权重。
• $\beta =0.001$：控制不相似性传播的权重。
• $k=10$：k-近邻数，用于构造局部几何矩阵 $S$。

计算复杂度

• 主要计算开销来自矩阵求逆（步骤 4 和 6，复杂度 $O(m^3)$）和二次规划（步骤 5，复杂度 $O(m^3{q}^3)$）。
• 总复杂度为每轮迭代 $O(2m^3+m^2+m^3{q}^3)$。

总结

DPCLS 提出了一种创新的 PLL 方法，通过结合对抗先验、不相似性传播和核扩展，有效提高了标签消歧的准确性。其目标函数综合了回归损失、对抗项和不相似性传播正则化，通过 IALM 优化实现了高效求解。实验结果表明，DPCLS 在合成和真实数据集上均显著优于现有方法，展现了其鲁棒性和竞争力。理论分析进一步验证了模型的泛化能力和对抗先验的合理性。算法实现清晰，代码公开，易于复现和扩展。

$0_{m\times q}\le F\le Y$约束

这个约束 $0_{m\times q}\le F\le Y$ 是部分标签学习（Partial Label Learning, PLL）中一个非常关键且富有洞察力的硬性约束（hard constraint）。它在模型中扮演着核心角色，确保了学习过程的合理性和有效性。我们来深入理解其含义和作用。

1. 符号解释

• $F\in {\mathbb{R}}^{m\times q}$: 这是模型要学习的核心输出——标签置信度矩阵（Label Confidence Matrix）。
  • $F_{ij}$ 表示第 $i$ 个样本属于第 $j$ 个类别的置信度或概率。它的值域通常在 $[0,1]$ 之间。
• Y∈{0,1}m×qY \in \{0, 1\}^{m \times q}Y∈{0,1}m×q: 这是给定的部分标签矩阵（Partial Label Matrix）。
  • $Y_{ij}=1$ 表示第 $j$ 个类别是第 $i$ 个样本的候选标签之一。
  • $Y_{ij}=0$ 表示第 $j$ 个类别不在第 $i$ 个样本的候选标签集中。
• $0_{m\times q}$: 这是一个所有元素都为0的 $m\times q$ 矩阵，作为下界。

2. 约束的两部分解析

这个不等式约束实际上包含了两个独立但紧密相关的子约束：

2.1 下界约束: $F\ge 0_{m\times q}$

• 数学含义: 对于所有的 $i,j$，有 $F_{ij}\ge 0$。
• 实际意义: 这个约束确保了任何样本对任何类别的置信度都不能为负数。这是概率或置信度的基本要求。例如，不可能说一个样本属于某个类别的“置信度”是 -0.3。

2.2 上界约束: $F\le Y$

• 数学含义: 对于所有的 $i,j$，有 $F_{ij}\le Y_{ij}$。

• 实际意义: 这是该约束最精妙、最关键的部分。它蕴含了以下两条重要信息：

  (a) 非候选标签的置信度必须为0

  • 如果 $Y_{ij}=0$，那么根据上界约束，$F_{ij}\le 0$。
  • 结合下界约束 $F_{ij}\ge 0$，我们可以得出：$F_{ij}=0$。
  • 结论: 模型绝对不能为那些不在候选集中的类别分配任何正的置信度。这保证了模型的预测结果始终符合已知的监督信息。如果一个类别根本不在候选集中，那它就不可能是真实标签。

  (b) 候选标签的置信度可以是[0, 1]之间的任意值

  • 如果 $Y_{ij}=1$，那么上界约束变为 $F_{ij}\le 1$。
  • 结合下界约束 $F_{ij}\ge 0$，我们得到 $0\le F_{ij}\le 1$。
  • 结论: 模型可以自由地为候选集中的每一个类别分配一个介于0到1之间的置信度。这个置信度反映了模型认为该类别是真实标签的可能性。最终的真实标签将是这些候选标签中置信度最高的那个。

3. 综合理解与核心作用

综合来看，约束 $0_{m\times q}\le F\le Y$ 的作用可以总结为：

1. 强制性地将搜索空间限制在可行域内: 它定义了一个严格有效的解空间。任何违反此约束的解（例如，为非候选标签赋予正置信度）都是无效的，会被直接排除。
2. 利用已知的弱监督信号: 这个约束充分利用了部分标签提供的信息。它告诉模型：“你只能在这些候选标签中进行选择，其他选项是不可能的。” 这极大地缩小了模型需要探索的范围。
3. 实现标签消歧的核心机制: 这个约束是整个PLL算法的基石。它迫使模型必须从有限的候选标签中进行区分。通过优化目标函数（如最小化重构误差），模型会倾向于让真实标签的置信度远高于错误标签的置信度，从而完成“消歧”任务。
4. 保证模型输出的合理性: 它确保了模型的输出 $F$ 是一个有意义的概率分布（虽然每行的和不一定为1，但每行的元素都在[0,1]区间内，并且只在候选标签上非零）。

4. 与另一个常见约束的对比

有时你会看到类似的约束：$F\ge 0$ 和 $F{1}_q=1_m$ （其中 $1_q$ 和 $1_m$ 分别是 $q$ 维和 $m$ 维的全1向量）。

• $F{1}_q=1_m$: 这个约束要求每个样本的标签置信度向量之和为1。这使得 $F$ 成为一个标准的概率分布矩阵。
• $F\le Y$: 这个约束则更强调可行性，即模型的输出必须与已知的候选标签集一致。

在论文《Jia 等 - Partial Label Learning with Dissimilarity Propagation guided Candidate Label Shrinkage.pdf》中，作者同时使用了这两个约束（见公式(1)）。$F \leq Y$ 确保了输出的可行性，而 $F1_q = 1_m$ 则进一步规范化了置信度，使其成为一个概率分布。两者结合，既保证了模型的预测结果在逻辑上是合理的（只考虑候选标签），又使得置信度具有可比性（总和为1）。

好的，我们来举一个具体的例子，直观地理解部分标签学习（PLL）中的约束 $0_{m\times q}\le F\le Y$。

1. 问题设定

假设我们有一个非常小的图像分类任务：

• 类别 (Classes): 3 个类别：猫 (Cat)、狗 (Dog)、鸟 (Bird)。所以 $q=3$。
• 训练样本 (Samples): 3 个样本：样本1、样本2、样本3。所以 $m=3$。
• 部分标签信息 (Partial Labels):
  • 样本1 看起来像猫，但也可能像狗。它的候选标签集是 {猫, 狗}。
  • 样本2 看起来像鸟，但也可能像猫。它的候选标签集是 {鸟, 猫}。
  • 样本3 看起来像狗，但也可能像鸟。它的候选标签集是 {狗, 鸟}。

2. 构造部分标签矩阵 $Y$

根据上述信息，我们可以构造部分标签矩阵 $Y$。矩阵的每一行对应一个样本，每一列对应一个类别。如果某个类别在样本的候选集中，对应位置为1，否则为0。

3. 理解约束 $0_{m\times q}\le F\le Y$

我们的目标是学习一个标签置信度矩阵 $F$，其中 $F_{ij}$ 表示模型认为第 $i$ 个样本属于第 $j$ 个类别的置信度。

约束 $0_{3\times 3}\le F\le Y$ 对 $F$ 的所有元素施加了严格的限制。我们来逐行分析：

• 对于 样本1 (第一行):

  • 候选标签是 {猫, 狗}，非候选标签是 {鸟}。
  • 约束 $F\le Y$ 意味着：
    • $F_{11}\le Y_{11}=1$ (猫的置信度 ≤ 1)
    • $F_{12}\le Y_{12}=1$ (狗的置信度 ≤ 1)
    • $F_{13}\le Y_{13}=0$ (鸟的置信度 ≤ 0)
  • 结合 $F\ge 0$，我们得到：
    • $0\le F_{11}\le 1$ (猫的置信度在0到1之间)
    • $0\le F_{12}\le 1$ (狗的置信度在0到1之间)
    • $F_{13}=0$ (鸟的置信度必须为0！)
  • 结论: 模型可以自由地在“猫”和“狗”之间分配置信度，但必须完全排除“鸟”这个选项。一个有效的 $F$ 的第一行可能是 $[0.8,0.2,0]$ 或 $[0.3,0.7,0]$。

• 对于 样本2 (第二行):

  • 候选标签是 {鸟, 猫}，非候选标签是 {狗}。
  • 约束 $F\le Y$ 意味着：
    • $F_{21}\le 1$ (猫的置信度 ≤ 1)
    • $F_{22}\le 0$ (狗的置信度 ≤ 0)
    • $F_{23}\le 1$ (鸟的置信度 ≤ 1)
  • 结合 $F\ge 0$，我们得到：
    • $0\le F_{21}\le 1$ (猫的置信度在0到1之间)
    • $F_{22}=0$ (狗的置信度必须为0！)
    • $0\le F_{23}\le 1$ (鸟的置信度在0到1之间)
  • 结论: 模型只能在“鸟”和“猫”之间分配置信度，必须完全排除“狗”这个选项。一个有效的 $F$ 的第二行可能是 $[0.1,0,0.9]$ 或 $[0.6,0,0.4]$。

• 对于 样本3 (第三行):

  • 候选标签是 {狗, 鸟}，非候选标签是 {猫}。
  • 约束 $F\le Y$ 意味着：
    • $F_{31}\le 0$ (猫的置信度 ≤ 0)
    • $F_{32}\le 1$ (狗的置信度 ≤ 1)
    • $F_{33}\le 1$ (鸟的置信度 ≤ 1)
  • 结合 $F\ge 0$，我们得到：
    • $F_{31}=0$ (猫的置信度必须为0！)
    • $0\le F_{32}\le 1$ (狗的置信度在0到1之间)
    • $0\le F_{33}\le 1$ (鸟的置信度在0到1之间)
  • 结论: 模型只能在“狗”和“鸟”之间分配置信度，必须完全排除“猫”这个选项。一个有效的 $F$ 的第三行可能是 $[0,0.9,0.1]$ 或 $[0,0.4,0.6]$。

4. 一个完整的有效 $F$ 示例

一个满足所有约束的 $F$ 矩阵可能是：

$$F=\left[\begin{array}{ccc}0.8& 0.2& 0\\ 0.1& 0& 0.9\\ 0& 0.9& 0.1\end{array}\right]$$

5. 为什么这个约束至关重要？

这个例子清晰地展示了该约束的威力：

1. 强制可行性 (Enforces Feasibility): 它确保了模型的预测永远不会违反已知的事实。在这个例子中，模型永远不会说“样本1”是“鸟”，因为这与标注信息相矛盾。
2. 指导学习过程 (Guides Learning): 它将一个开放的、可能有 $q$ 个选择的问题，变成了一个在 $|S_i|$ 个候选标签中进行选择的封闭问题。模型的“注意力”被强制集中在正确的子集上。
3. 实现标签消歧 (Enables Label Disambiguation): 通过优化目标函数（如最小化 $||XW-F|{|}_F^2$），模型会倾向于让真实标签的置信度接近1，而让错误的候选标签的置信度接近0。例如，在 $F$ 中，样本1 的“猫”置信度(0.8)远高于“狗”置信度(0.2)，这表明模型认为“猫”更可能是真实标签。

总结: 约束 $0_{m\times q}\le F\le Y$ 是PLL模型的“安全护栏”和“导航仪”。它利用不精确的监督信息（候选集）来定义一个精确的可行解空间，从而使得从噪声数据中学习出准确模型成为可能。

基于差异性传播的候选标签收缩的数学原理。

这部分的核心思想是利用标签空间（label space）中的信息来构建一个语义差异性矩阵 $D_0$，并利用这个矩阵与模型学习到的相似性矩阵 $F{F}^T$ 之间存在的对抗性关系（adversarial relationship），来指导和约束模型的学习过程，从而更有效地进行标签消歧（label disambiguation）。

1. 构建语义差异性矩阵 $D_0$

首先，论文从给定的部分标签矩阵 $Y$ 出发，构造了一个关键的辅助矩阵 $D_0\in {\mathbb{R}}^{m\times m}$。

• 定义 (公式2):
  $$D_{0ij}=\{\begin{array}{ll}1,& \text{if }{y}_i^T{y}_j=0\\ 0,& \text{otherwise}\end{array}$$

• 数学解释:

  • $y_i^T{y}_j$ 是两个行向量 $y_i$ 和 $y_j$ 的内积。由于 $Y$ 是一个二值矩阵（0或1），$y_i^T{y}_j$ 的结果就是它们在所有类别上共同为1的个数，即它们候选标签集的交集大小 $|S_i\cap S_j|$。
  • 因此，$y_i^T{y}_j=0$ 意味着 $S_i\cap S_j=\varnothing$，即样本 $x_i$ 和 $x_j$ 的候选标签集完全没有交集。
  • 在这种情况下，这两个样本的真实标签不可能相同（因为真实标签必须在各自的候选集中），所以它们必然属于不同的类别。
  • 相反，如果 $y_i^T{y}_j>0$，则说明它们有共同的候选标签，因此它们有可能属于同一个类别。

• 核心意义: $D_0$ 矩阵捕捉了样本间绝对的、确定性的语义差异性。$D_{0ij}=1$ 表示 $x_i$ 和 $x_j$ 必须属于不同类；$D_{0ij}=0$ 表示它们可能属于同一类。这提供了一个非常强的、来自标签空间的先验知识。

2. 构建相似性矩阵 $F{F}^T$

这是模型需要学习的输出之一。假设 $F\in {\mathbb{R}}^{m\times q}$ 是一个标签置信度矩阵（Label Confidence Matrix），其中 $F_{ik}$ 表示样本 $x_i$ 属于类别 $k$ 的置信度。

• 定义: 计算 $F{F}^T$。
• 数学解释: $(F{F}^T{)}_{ij}$ 是第 $i$ 个样本的置信度向量 $f_i$ 和第 $j$ 个样本的置信度向量 $f_j$ 的内积：
  $$(F{F}^T{)}_{ij}=f_i^T{f}_j=\sum _{k=1}^q{F}_{ik}{F}_{jk}$$
• 核心意义: $F{F}^T$ 可以被看作是一个相似性矩阵。它的元素 $(F{F}^T{)}_{ij}$ 越大，表示样本 $x_i$ 和 $x_j$ 在模型预测的标签分布上越相似，因此它们属于同一类的可能性越大。

3. 对抗性先验 (Adversarial Prior)

这是该方法最精妙、最具创新性的部分。

• 观察: $D_0$ 和 $F{F}^T$ 之间存在一种天然的对抗性（adversarial）关系：
  • 如果 $D_{0ij}=1$，这意味着 $x_i$ 和 $x_j$ 必须属于不同类，那么它们的相似性 $(F{F}^T{)}_{ij}$ 应该尽可能小（理想情况下为0）。
  • 如果 $D_{0ij}=0$，这意味着 $x_i$ 和 $x_j$ 可能属于同类，那么它们的相似性 $(F{F}^T{)}_{ij}$ 应该尽可能大。
• 总结: $D_0$ 中的“1”（表示必须不同）应该对应 $F{F}^T$ 中的“0”（表示不相似）；$D_0$ 中的“0”（表示可能相同）应该对应 $F{F}^T$ 中的“大值”（表示相似）。这就是所谓的“对抗性关系”。

4. 利用对抗性先验进行约束 (公式3)

为了将这种对抗性关系融入到模型训练中，论文提出了一个优化目标：

$$\underset{F}{\min }{\Vert D_0\odot F{F}^T\Vert }_1$$

其中：

• $\odot$ 是矩阵的逐元素乘法（Hadamard product）。

• $\Vert \cdot {\Vert }_1$ 是矩阵的 $l_1$ 范数，即矩阵所有元素的绝对值之和。

• 数学解释:

  • $D_0\odot F{F}^T$ 的结果是一个新的矩阵，其元素为 $D_{0ij}\cdot (F{F}^T{)}_{ij}$。
  • 当 $D_{0ij}=1$ 时，$(D_0\odot F{F}^T{)}_{ij}=(F{F}^T{)}_{ij}$。
  • 当 $D_{0ij}=0$ 时，$(D_0\odot F{F}^T{)}_{ij}=0$。
  • 因此，${\Vert D_0\odot F{F}^T\Vert }_1={\sum }_{i,j}{D}_{0ij}\cdot (F{F}^T{)}_{ij}$。这个和只包含了那些 $D_{0ij}=1$ 的项，也就是那些必须属于不同类的样本对之间的相似性。

• 优化目标: 最小化这个和，意味着要让所有“必须不同”的样本对 $(x_i,x_j)$ 之间的相似性 $(F{F}^T{)}_{ij}$ 尽可能小。换句话说，模型被强制要求：对于任何两个候选标签集完全不相交的样本，它们在模型预测上的相似性必须很低。

• 作用: 这个约束极大地缩小了模型解空间。它迫使模型在学习过程中，不仅要考虑特征空间的几何结构，还必须满足这个来自标签空间的强约束。这有助于模型更准确地识别出真实的标签，因为错误的标签会违反这个对抗性关系。

5. 为什么直接最小化公式(3)不够？

论文指出，虽然公式(3)是一个很好的先验，但直接使用它效果不佳。原因如下：

1. 信息不对称: $D_0$ 是从候选标签集 $Y$ 推断出来的，它只有在 $y_i^T{y}_j=0$ 时才为1，否则为0。而 $F$ 是一个连续变量，且受到 $F\le Y$ 的约束。
2. 互补性: 正如论文所述，“$D_0$ 和 $F{F}^T$ 的正元素的位置是互补的”。具体来说：
   • $D_{0ij}=1$ 当且仅当 $y_i^T{y}_j=0$。
   • $F$ 被约束为 $F\le Y$，所以 $(F{F}^T{)}_{ij}>0$ 通常发生在 $y_i^T{y}_j>0$ 的时候（因为只有在这种情况下，$F$ 才能同时在 $i$ 和 $j$ 行有非零值）。
3. 结果: 这导致 $D_0$ 和 $F{F}^T$ 的正元素自然地出现在不同的位置。即使不施加任何额外的约束，这个互补性也会自动成立。因此，仅仅最小化公式(3)并不能带来额外的收益，因为它已经隐含地满足了。

6. 如何解决这个问题？——引入“差异性传播”

为了解决上述问题，论文提出了“差异性传播”（Dissimilarity Propagation）机制。其核心思想是：

1. 初始差异性 ($D_0$): 从标签空间获得一个初始的、局部的差异性信息。
2. 传播与增强: 利用样本在特征空间中的局部几何结构（通过构建一个图 $S$ 来表示），将这种局部的差异性信息传播到全局。例如，如果样本 $x_i$ 和 $x_j$ 很相似（在特征空间中接近），并且 $x_i$ 与另一个样本 $x_k$ 有很强的差异性，那么 $x_j$ 也应该与 $x_k$ 有较强的差异性。
3. 最终差异性 ($D$): 经过传播后的差异性矩阵 $D$ 包含了更丰富、更全局的信息，比初始的 $D_0$ 更强大。
4. 应用约束: 将最终的 $D$ 用于指导相似性矩阵 $A$ 的学习，形成一个新的约束 ${\min }_A\Vert D\odot A{\Vert }_1$，从而更有效地引导模型学习。

总结: 这部分的数学原理通过构建一个基于标签空间的语义差异性矩阵 $D_0$，并利用它与模型预测相似性 $F{F}^T$ 之间的对抗性关系，提出了一种强大的先验。尽管直接应用这个先验存在局限性，但其核心思想——利用标签空间信息来约束模型学习——是极具洞察力的，并通过后续的“差异性传播”机制得到了有效的实现。

好的，我们来详细解析这个公式在论文《Partial Label Learning with Dissimilarity Propagation guided Candidate Label Shrinkage》中的含义和作用。

公式解读

公式 $D_{ij}=D_{0ij}$, if $D_{0ij}=1$ 是一个条件赋值语句（conditional assignment），它定义了如何从初始的语义差异性矩阵 $D_0$ 构造出最终的、经过传播和增强的差异性矩阵 $D$。

• $D_0$: 这是论文中通过公式(2)构建的初始语义差异性矩阵。如前所述，$D_{0ij}=1$ 表示样本 $x_i$ 和 $x_j$ 的候选标签集完全没有交集（$y_i^T{y}_j=0$），因此它们必须属于不同的类别。
• $D$: 这是论文要构造的最终差异性矩阵。它不仅仅包含 $D_0$ 中的信息，还融合了从特征空间（数据的几何结构）中传播过来的差异性信息。

2. 数学原理与实现过程

这个公式的核心思想是：将初始的、基于标签空间的“确定性”差异性信息（$D_0=1$）作为最终差异性矩阵 $D$ 的“种子”或“锚点”。

具体来说，这个公式的实现过程可以理解为：

1. 初始化: 首先，根据部分标签矩阵 $Y$ 计算出初始的语义差异性矩阵 $D_0$。
2. 传播 (Propagation): 接着，论文会利用样本在特征空间中的局部几何结构（例如，通过构建一个图，其中边的权重表示样本间的相似度）来对 $D_0$ 进行“传播”。这个过程类似于热传导或消息传递。其基本逻辑是：
   • 如果两个样本 $x_i$ 和 $x_j$ 在特征空间中非常接近（即它们是邻居），并且 $x_i$ 与另一个样本 $x_k$ 有很强的差异性（$D_{0ik}=1$），那么 $x_j$ 也应该与 $x_k$ 有较强的差异性。
   • 这个传播过程会生成一个中间的、经过传播的差异性矩阵，我们称之为 $\tilde{D}$。$\tilde{D}$ 比 $D_0$ 更丰富，因为它包含了全局性的差异性信息。
3. 选择与保留 (Selection and Retention): 最后，应用公式 $D_{ij}=D_{0ij}$, if $D_{0ij}=1$。这一步的作用是：
   • 对于那些在 $D_0$ 中已经明确为“必须不同”的样本对 $(i,j)$（即 $D_{0ij}=1$），我们强制地将 $D_{ij}$ 设置为 1。这保证了所有来自标签空间的、确定性的信息在最终的 $D$ 矩阵中得到完全保留和优先考虑。
   • 对于其他所有样本对 $(i,j)$（即 $D_{0ij}=0$），这个公式没有直接赋值。这些位置的 $D_{ij}$ 值将由传播过程生成的 ${\tilde{D}}_{ij}$ 决定。这意味着，对于那些候选标签集有交集的样本对，我们允许模型利用特征空间的几何结构来推断它们之间的相对差异性。

3. 为什么这样做？

这种设计策略非常巧妙，主要有以下几个原因：

1. 确保关键信息不丢失: 标签空间提供的“必须不同”的信息是最强、最可靠的先验知识。通过这个公式，作者确保了这些“硬性约束”不会在传播过程中被稀释或覆盖。这是整个方法的基础。
2. 结合两种信息源: 它成功地将两种不同来源的信息结合起来：
   • 标签空间信息 ($D_0$): 提供了确定性的约束（必须不同）。
   • 特征空间信息 (传播过程): 提供了可能性的推断（可能不同，程度如何）。
   • 最终的 $D$ 矩阵是两者的融合：它既包含了绝对的约束，又包含了通过几何结构推断出的、更精细的相对差异性。
3. 引导学习过程: 最终的 $D$ 矩阵被用于优化目标函数（如最小化 $\Vert D\odot F{F}^T{\Vert }_1$）。由于 $D$ 中的“1”代表了“必须不同”，而 $F{F}^T$ 的元素代表了预测的相似性，这个目标函数会迫使模型让所有“必须不同”的样本对之间的预测相似性尽可能小。这为模型学习提供了一个强有力的、基于语义的指导。

4. 总结

公式 $D_{ij}=D_{0ij}$, if $D_{0ij}=1$ 可以看作是一个信息融合与优先级设定的规则。它确保了从标签空间获得的、关于“样本必须不同”的最强先验信息，在最终的差异性矩阵 $D$ 中得到了完全的保留和优先级提升。同时，它允许模型利用特征空间的几何结构来填充和细化那些不确定的区域（即 $D_{0ij}=0$ 的区域）。这种设计使得最终的 $D$ 矩阵既能捕捉到数据的语义差异，又能利用其几何结构，从而为后续的标签消歧任务提供了更强大、更全面的指导。