SIGKDD-2023《Complementary Classifier Induced Partial Label Learning》

核心思想

论文的核心思想是针对部分标签学习（Partial Label Learning, PLL）问题提出一种新型方法PL-CL（Partial Label learning based on Complementary Learning）。在PLL中，每个训练样本关联一个候选标签集，其中只有一个是真实的ground-truth标签，而现有方法的主要挑战是消歧（disambiguation），即从候选标签集中识别出真实标签。现有工作通常忽略了非候选标签集（即互补标签，complementary labels）的价值，这些标签精确地指示了样本不属于的类别集。

论文创新性地利用非候选标签诱导一个互补分类器（complementary classifier），该分类器与传统PLL的普通分类器（ordinary classifier）形成对抗关系（adversarial relationship），从而消除候选标签集中的假阳性标签。同时，假设特征空间和标签空间共享相同的局部拓扑结构（local topological structure），通过一个动态图（dynamic graph）捕捉这种结构一致性，进一步辅助消歧。整体框架如论文图1所示：候选标签生成普通分类器，非候选标签生成互补分类器，通过对抗约束和图正则化实现优化。该方法充分利用实例间相关性、实例到候选标签的映射以及非候选标签的准确信息，提升PLL的性能。

目标函数

论文的目标函数是基于最小化损失的形式化，综合考虑普通分类器、互补分类器、对抗关系以及图正则化。完整的目标函数如下：

$$\underset{W,b,\hat{W},\hat{b},P,Q,G}{\min }{\Vert XW+1_n{b}^T-P\Vert }_F^2+\beta {\Vert 1_{n\times l}-P-Q\Vert }_F^2+\alpha {\Vert X\hat{W}+1_n{\hat{b}}^T-Q\Vert }_F^2+\mu {\Vert P^T-P^{T}G\Vert }_F^2+\gamma {\Vert X^T-X^{T}G\Vert }_F^2+\lambda \left({\Vert W\Vert }_F^2+{\Vert \hat{W}\Vert }_F^2\right)$$

约束条件：

$$P{1}_q=1_n,0_{n\times l}\le P\le Y,\hat{Y}\le Q\le 1_{n\times l}$$

$$G^T{1}_n=1_n,0_{n\times n}\le G\le U$$

其中：

• $X\in {\mathbb{R}}^{n\times q}$ 是实例矩阵（$n$个样本，$q$维特征）。
• Y∈{0,1}n×lY \in \{0,1\}^{n \times l}Y∈{0,1}n×l 是部分标签矩阵（$l$个类别），$\hat{Y}=1_{n\times l}-Y$ 是互补标签矩阵。
• $P\in {\mathbb{R}}^{n\times l}$ 是标签置信矩阵（labeling confidence matrix），$p_{ij}$ 表示第$j$个标签是第$i$个样本真实标签的概率。
• $Q\in {\mathbb{R}}^{n\times l}$ 是互补标签置信矩阵，$q_{ij}$ 表示第$j$个标签不是第$i$个样本真实标签的置信度。
• $G\in {\mathbb{R}}^{n\times n}$ 是局部相似性图矩阵，捕捉特征和标签空间的局部结构。
• $W,\hat{W}\in {\mathbb{R}}^{q\times l}$ 和 $b,\hat{b}\in {\mathbb{R}}^l$ 分别是普通分类器和互补分类器的权重和偏置。
• $U$ 是$k$-最近邻位置矩阵，$1_n$ 是全1向量，${\Vert \cdot \Vert }_F$ 是Frobenius范数。
• $\alpha ,\beta ,\gamma ,\mu ,\lambda$ 是超参数，用于平衡不同项。

函数分解：

• 第一项：普通分类器的最小二乘损失。
• 第二项：对抗损失，确保$P+Q=1_{n\times l}$。
• 第三项：互补分类器的损失。
• 第四、五项：图正则化，确保特征和标签空间的局部一致性。
• 第六项：正则化控制模型复杂度。

目标函数详细的优化过程

优化采用交替迭代（alternating optimization）方式，逐个变量固定其他变量求解，直到收敛。论文引入核扩展（kernel extension）以处理非线性关系，使用高斯核$K(x_i,x_j)=\exp (-{\Vert x_i-x_j\Vert }_2^2/(2{\sigma }^2))$，其中$\sigma$为训练样本平均距离。定义输出矩阵$H=\Phi W+1_n{b}^T$ 和 $\hat{H}=\Phi \hat{W}+1_n{\hat{b}}^T$，其中$\Phi$是核映射后的特征矩阵，核矩阵$K=\Phi {\Phi }^T$。

1. 更新 $W,b$ 和 $\hat{W},\hat{b}$：

   • 对于普通分类器：求解 ${\min }_{W,b}{\Vert XW+1_n{b}^T-P\Vert }_F^2+\lambda {\Vert W\Vert }_F^2$。
   • 核版本使用拉格朗日乘子$A$，通过KKT条件得：
     $$A={\left(\frac{1}{2\lambda }K+\frac{1}{2}{I}_{n\times n}\right)}^{-1}\left(P-1_n{b}^T\right),b={\frac{sP}{s{1}_n}}^T$$
     其中$s=1_n^T{\left(\frac{1}{2\lambda }K+\frac{1}{2}{I}_{n\times n}\right)}^{-1}$。
   • 类似地更新$\hat{A},\hat{b}$，替换$P$为$Q$，$\lambda$为$\lambda /\alpha$。

2. 更新 $Q$：

   • 子问题：${\min }_Q{\Vert Q-\frac{\alpha \hat{H}+\beta (1_{n\times l}-P)}{\alpha +\beta }\Vert }_F^2$，s.t. $\hat{Y}\le Q\le 1_{n\times l}$。
   • 解：元素-wise阈值操作
     $$Q=T_1\left(T_{\hat{Y}}\left(\frac{\alpha \hat{H}+\beta (1_{n\times l}-P)}{\alpha +\beta }\right)\right)$$
     其中T1(m)=min⁡{1,m}T_1(m) = \min\{1, m\}T1​(m)=min{1,m}，TY^(m)=max⁡{y^ij,m}T_{\hat{Y}}(m) = \max\{\hat{y}_{ij}, m\}TY^​(m)=max{y^​ij​,m}。

3. 更新 $G$：

   • 子问题：${\min }_G\gamma {\Vert X^T-X^{T}G\Vert }_F^2+\mu {\Vert P^T-P^{T}G\Vert }_F^2$，s.t. $G^T{1}_n=1_n,0_{n\times n}\le G\le U$。
   • 列-by-列求解，对于第$i$列${\hat{g}}_i$（仅更新$k$最近邻系数）：转化为二次规划（QP）
     $$\underset{{\hat{g}}_i}{\min }{\hat{g}}_i^T(\gamma B_{x_i}+\mu B_{p_i}){\hat{g}}_i,\text{s.t.}{\hat{g}}_i^T{1}_k=1,0_k\le {\hat{g}}_i\le 1_k$$
     其中$B_{x_i},B_{p_i}$是Gram矩阵，使用QP求解器。

4. 更新 $P$：

   • 子问题：${\min }_P{\Vert P-\frac{H+\beta (1_{n\times l}-Q)}{1+\beta }\Vert }_F^2+\frac{\mu }{1+\beta }{\Vert P^T-P^{T}G\Vert }_F^2$，s.t. $P{1}_q=1_n,0_{n\times l}\le P\le Y$。
   • 向量化后转化为QP：${\min }_{\vec{p}}\frac{1}{2}{\vec{p}}^T(C+\frac{2(1+\beta )}{\mu }{I}_{nl\times nl})\vec{p}-\frac{2(1+\beta )}{\mu }{\vec{o}}^T\vec{p}$，s.t. 行和约束，使用QP求解器。其中$C$是块对角矩阵基于$(I-G)(I-G{)}^T$。

复杂度：总体为$O(n^3+nql+nl+n{k}^3+n^3{q}^3)$。

主要的贡献点

1. 首次引入互补分类器：在PLL文献中首次提出利用非候选标签诱导互补分类器，该分类器提供准确的负信息，帮助消除候选集中的假阳性标签。
2. 对抗项设计：提出对抗损失$\beta {\Vert 1_{n\times l}-P-Q\Vert }_F^2$，将互补分类器的信息传递到普通分类器，指导消歧过程。
3. 自适应图正则化：引入动态图$G$捕捉特征和标签空间的局部一致性，提升鲁棒性。
4. 实验验证：在4个控制UCI数据集和6个真实世界数据集上显著优于SOTA方法（如PL-AGGD、SURE等），并通过消融研究证实互补分类器和图结构的有效性。胜率达92.1%以上，且对超参数鲁棒。

算法的实现过程

算法实现基于伪代码（Algorithm 1），采用迭代优化框架。输入：部分标签数据$D$，超参数$\alpha ,\beta ,\mu ,\gamma ,\lambda$，测试样本$x^{\ast }$。输出：$x^{\ast }$的预测标签$y^{\ast }$。

1. 初始化：

   • 初始化$G$：求解${\min }_G{\Vert X^T-X^{T}G\Vert }_F^2$，s.t. $G^T{1}_n=1_n,0_{n\times n}\le G\le U$（基于$k$-NN的重构）。
   • 初始化$P$：求解${\min }_P{\Vert P^T-P^{T}G\Vert }_F^2$，s.t. $P{1}_q=1_n,0_{n\times l}\le P\le Y$。
   • 初始化$Q$：对于每个$q_{ij}$，如果$y_{ij}=0$则$q_{ij}=1/(l-{\sum }_j{y}_{ij})$，否则$q_{ij}=0$。

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

   • 更新$A,b$：使用公式(16)计算普通分类器的核参数。
   • 更新$\hat{A},\hat{b}$：使用公式(17)计算互补分类器的核参数。
   • 更新$Q$：使用公式(19)的阈值操作。
   • 更新$G$：列-by-列QP求解公式(22)。
   • 更新$P$：QP求解公式(25)。

3. 预测新样本：

   • 对于未见样本$x^{\ast }$，计算预测：
     $$y^{\ast }=\arg \underset{k}{\max }\sum _{i=1}^n\frac{1}{2\lambda }{A}_{ik}K(x^{\ast },x_i)+b_k$$

实现细节：在实践中，使用QP求解器（如CVXOPT或Gurobi）处理QP子问题。核矩阵$K$预计算以加速。收敛标准可设为目标函数变化小于阈值或最大迭代次数。实验中$k=10$，超参数通过网格搜索选择。