Complementary Classifier Induced Partial Label Learning

PLL is a representative weakly supervised learning framework, which learns from ambiguous supervision information. In PLL, an instance is associated with a set of labels, among which only one is valid. Since the ground-truth label of each sample is concealed in its candidate labels, which can not be directly accessible during the training phase, PLL is a quite challenging task.

To address the mentioned challenge, the key approach is candidate label disambiguation, i.e., (Feng and An, 2018), (Nguyen and Caruana, 2008), (Feng and An, 2019), (Zhang and Yu, 2015). The existing methods can be summarized into two categories: averaging-based approaches and identification-based approaches. For the averaging-based approaches (Hüllermeier and Beringer, 2005), (Cour et al., 2011), each candidate label of a training sample is treated in an equal manner and the model prediction is yielded by averaging the modeling outputs of the candidate labels. For example, PL-KNN (Hüllermeier and Beringer, 2005) averages the candidate labels of neighboring instances to make prediction. This strategy is intuitive, however, it may fail when false-positive labels dominate the candidate label set. For the identification-based approaches, (Wang et al., 2022), (Feng and An, 2019), (Feng and An, 2018), the valid label is considered as a latent variable and can be identified through an iterative optimization procedure. For instance, PL-AGGD (Wang et al., 2022) uses the feature matrix to construct a similarity graph, which is further utilized for generating labeling confidence of each candidate label.

In this paper, we summarize the following three kinds of priors that are important for disambiguation. The first is type is the correlations among instances, i.e., similar samples in the feature space may share a same label. The second kind of prior is the mapping from instances to the candidate labels, i.e., the mapping error of an instance to the valid label is small, while that to an incorrect label in the candidate label set is large. The last kind of information is non-candidate label set, which precisely describes a set of labels should not be assigned to a sample. Existing works mainly focus on the first two types of priors, while the valuable information in non-candidate labels (complementary labels) which is directly available and accurate is overlooked. Therefore, we will fully take advantage of above mentioned priors (especially the complementary labels) to achieve PLL.

Complementary-label learning (CLL) is another representative framework of weakly supervised learning (Feng et al., 2020), (Yu et al., 2018). In the traditional CLL (Ishida et al., 2017), an instance is associated with only one label, which indicates that this sample does not belong to. Although in this paper, complementary label information are adopted, it is quite different from that in the traditional complementary-label learning. First, in partial label learning the number of complementary labels of each sample is usually more than one, while an instance only has one complementary label in complementary-label learning. Additionally, the aim of complementary classifier in PLL is to assist the disambiguation of candidate labels, which is different from CLL. To the best of our knowledge, the information of complementary labels has been overlooked to some extent in previous PLL works, and our work is the first time to induce a complementary classifier to assist the construction of the ordinary classifier by an adversarial prior in PLL.

First, PL-CL uses a weight matrix $\mathbf{W}=[\mathbf{w}_{1},\mathbf{w}_{2},...,\mathbf{w}_{l}]\in\mathbb{R}^{q\times l}$ to map the instance matrix to the labeling confidence matrix $\mathbf{P}=[\mathbf{p}_{1},\mathbf{p}_{2},...,\mathbf{p}_{n}]^{\mathsf{T}}\in\mathbb{R}^{n\times l}$, where $\mathbf{p}_{i}\in\mathbb{R}^{l}$ is the labeling confidence vector corresponding to $\mathbf{x}_{i}$, and $p_{ij}$ represents the probability of the $j$-th label being the ground-truth label of $\mathbf{x}_{i}$. To be specific, PL-CL uses the following least squares loss to form the ordinary classifier:

where $\mathbf{b}=[b_{1},b_{2},...,b_{l}]\in\mathbb{R}^{l}$ is the bias term and $\mathbf{1}_{n}\in\mathbb{R}^{n}$ is an all ones vector. $\|\mathbf{W}\|_{F}$ denotes the Frobenius norm of the weight matrix, and minimizing $\|\mathbf{W}\|^{2}_{F}$ will control the complexity of the model. $\lambda$ is a hyper-parameter trading off these terms. As $\mathbf{P}$ represents the labeling confidence, it should be strictly non-negative, i.e., $p_{ij}\geq 0$ and $p_{ij}$ has a chance to be positive only when the $j$-th label lies in the candidate label set of $i$-th sample, i.e., we have $p_{ij}\leq y_{ij}$. Moreover, as each row of $\mathbf{P}$ indicates the labeling confidence of a certain sample, the sum of its elements should be equal to 1, i.e., $\sum_{j}p_{ij}=1$. The ideal state of $\mathbf{p}_{i}$ is one-hot, for there will only one ground-truth label. By minimizing Eq. (2), the ground-truth label is excepted to produce a smaller mapping error than the incorrect ones residing the candidate label set, and the correct label is likely to be selected.

Suppose matrix $\mathbf{Q}=[\mathbf{q}_{1},\mathbf{q}_{2},...,\mathbf{q}_{n}]\in\mathbb{R}^{n\times l}$ is the complementary-labeling confidence matrix where $q_{ij}$ denotes the confidence of the $j$-th label NOT being the ground-truth label of $\mathbf{x}_{i}$. Similar as the ordinary classifier, we construct a complementary classifier:

where $\hat{\mathbf{W}}\in\mathbb{R}^{q\times l}$ and $\hat{\mathbf{b}}\in\mathbb{R}^{l}$ are the weight matrix and bias for the complementary classifier. Different from $\mathbf{p}_{i}$, the ideal state of $\mathbf{q}_{i}$ is “zero-hot”, i.e., only one value in $\mathbf{q}_{i}$ is 0 with others 1, for there is only one ground-truth label in PLL. Therefore, we require $\hat{y}_{ij}\leq q_{ij}\leq 1,\forall i,j$, which means $0\leq q_{ij}\leq 1$ if the $j$-th label resides in the candidate label set, and $q_{ij}=1$, if $\hat{y}_{ij}=1$.

The ordinary classifier predicts which label should be assigned to an instance while the complementary classifier specifies a group of labels that should not be allocated to that instance. Therefore, an adversarial relationship exists between the outputs of the ordinary and complementary classifiers, i.e., a larger (resp. smaller) element in $\mathbf{P}$ implies a smaller (resp. larger) element in $\mathbf{Q}$, and vice versa. Besides, as the elements in both $\mathbf{Q}$ and $\mathbf{P}$ are non-negative and no more than 1, the above adversarial relationship can be formulated as $\mathbf{p}_{i}+\mathbf{q}_{i}=\mathbf{1}_{l}$. Taking the adversarial relationship into account, the complementary classifier becomes:

where $\mathbf{1}_{n\times l}\in\mathbb{R}^{n\times l}$ is an all ones matrix, and $\alpha$ and $\beta$ are two hyper-parameters. Different from the candidate label set, the complementary information in the non-candidate label set is directly accessible and accurate, by minimizing Eq. (4), the valuable information is passed to the labeling confidence matrix $\mathbf{P}$, which will further assist label disambiguation.

As suggested by (Hou et al., 2016), the label space and feature space of a data set lie in two different manifolds but with the similar local structure, i.e., if $\mathbf{x}_{i}$ and $\mathbf{x}_{j}$ are similar, their corresponding labeling confidence vector $\mathbf{p}_{i}$ and $\mathbf{p}_{j}$ should also be similar. To this end, we first construct a local non-negative similarity matrix $\mathbf{G}=[g_{ij}]_{n\times n}$ to capture the local manifold structure of the feature space, i.e.,

where $\mathbf{0}_{n\times n}$ is an all zeros matrix with the size of $n\times n$. $\mathbf{G}^{\mathsf{T}}\mathbf{1}_{n}=\mathbf{1}_{n}$ will ensure that the sum of each column of $\mathbf{G}$ is 1, i.e., $\mathbf{G}$ is normalized. $\mathbf{U}=[u_{ij}]_{n\times n}$ denotes the $k$-nearest neighbors (KNN) location matrix, i.e., $u_{ij}=1$ if $\mathbf{x}_{i}$ belongs to the KNN of $\mathbf{x}_{j}$, otherwise $u_{ij}=0$. $\mathbf{0}_{n\times n}\leq\mathbf{G}\leq\mathbf{U}$ means that the elements of $\mathbf{G}$ will be no less than 0 and no more than the elements of $\mathbf{U}$ at the same location, which will ensure that one sample can only be reconstructed by its neighbors. We further assume the label space shares the same local structure as the feature space captured by $\mathbf{G}$, and use it to assist label disambiguation, i.e.,

By minimizing Eq. (6), the local manifold structure $\mathbf{G}$ will help produce a better $\mathbf{P}$. Finally, we combine Eqs. (5) and (6) together to jointly optimize the local structure $\mathbf{G}$ and the labeling confidence matrix $\mathbf{P}$, i.e.,

where $\gamma$ and $\mu$ are two hyper-parameters. By minimizing Eq. (7), the feature space and label space will be well communicated to achieve a better local consistency.

Based on the discussions above, the objective function of PL-CL is finally formulated as

where $\beta,\alpha,\gamma,\mu$ and $\lambda$ are the hyper-parameters balancing different terms. PL-CL comprehensively takes the information in the candidate-label set, the non-candidate label set, and the sample relationships into consideration to perform label disambiguation. As will be shown later, it is quite robust to all these hyper-parameters.

The most challenging issue in PLL is the inaccurate supervision. As the non-candidate labels precisely indicate whether an instance does not belong to a certain class, which can be regarded as a kind of accurate supervision, leveraging the non-candidate labels will certainly help PLL.

To the best of our knowledge, it is the first time to use the non-candidate labels to construct a complementary classifier in PLL to help label disambiguation. Moreover, the adversarial prior to introduce the complementary classifier is also novel in PLL.

With other variables fixed, problem (8) with respect to $\mathbf{W}$ and $\mathbf{b}$ can be reformulated as

which is a regularized least squares problem and the corresponding closed-form solution is

where $\mathbf{I}_{n\times n}$ is an identity matrix with the size of $n\times n$. Similarly, the problem (8) with respect to $\hat{\mathbf{W}}$ and $\hat{\mathbf{b}}$ is

which has a similar analytical solution as Eq. (9), i.e.,

where $\mathbf{M}=[\mathbf{m}_{1},\mathbf{m}_{2},...,\mathbf{m}_{n}]\in\mathbb{R}^{n\times l}$. The Lagrangian function of Eq. (13) is formulated as

where $\mathbf{A}\in\mathbb{R}^{n\times l}$ is the Lagrange multiplier. ${\rm tr}(\cdot)$ is the trace of a matrix. Based on the KKT conditions, we have

Define a kernel matrix $\mathbf{K}=\mathbf{\Phi}\mathbf{\Phi}^{\mathsf{T}}$ with its element $k_{ij}=\phi(\mathbf{x}_{i})\phi(\mathbf{x}_{j})=\mathcal{K}(\mathbf{x}_{i},\mathbf{x}_{j})$, where $\mathcal{K}(\cdot,\cdot)$ is the kernel function. For PL-CL, we use Gaussian function $\mathcal{K}(\mathbf{x}_{i},\mathbf{x}_{j})={\rm exp}(-\|\mathbf{x}_{i}-\mathbf{x}_{j}\|_{2}^{2}/(2\sigma^{2}))$ as the kernel function and set $\sigma$ to the average distance of all pairs of training instances. Then, we have

where $\mathbf{s}=\mathbf{1}_{n}^{\mathsf{T}}\left(\frac{1}{2\lambda}\mathbf{K}+\frac{1}{2}\mathbf{I}_{n\times n}\right)^{-1}$. We can also obtain $\mathbf{W}={\mathbf{\Phi}^{\mathsf{T}}\mathbf{A}}/{2\lambda}$ from Eq. (15). The output of the model can be denoted by $\mathbf{H}=\mathbf{\Phi}\mathbf{W}+\mathbf{1}_{n}\mathbf{b}^{\mathsf{T}}=\frac{1}{2\lambda}\mathbf{KA}+\mathbf{1}_{n}\mathbf{b}^{\mathsf{T}}$.

As the optimization problem regarding $\hat{\mathbf{W}}$ and $\hat{\mathbf{b}}$ has the same form as problem (13), similarly, we have

where $\hat{\mathbf{s}}=\mathbf{1}_{n}^{\mathsf{T}}\left(\frac{\alpha}{2\lambda}\mathbf{K}+\frac{1}{2}\mathbf{I}_{n\times n}\right)^{-1}$, and the output of the complementary classifier is defined as $\hat{\mathbf{H}}=\frac{\alpha}{2\lambda}\mathbf{K}\hat{\mathbf{A}}+\mathbf{1}_{n}\hat{\mathbf{b}}^{\mathsf{T}}$.

Fixing other variables, the $\mathbf{Q}$-subproblem can be equivalently rewritten as

where the solution is

$\mathcal{T}_{1}$, $\mathcal{T}_{\hat{\mathbf{Y}}}$ are two thresholding operators in element-wise, i.e., $\mathcal{T}_{1}(m):=\min\{1,m\}$ with $m$ being a scalar and $\mathcal{T}_{\hat{\mathbf{Y}}}(m):=\max\{\hat{{y}}_{ij},m\}$.

Fixing other variables, the $\mathbf{G}$-subproblem is rewritten as

Notice that each column of $\mathbf{G}$ is independent to other columns, therefore we can solve the $\mathbf{G}$-subproblem column by column. To solve the $i$-th column of $\mathbf{G}$, we have

As there are only $k$ non-zero elements in $\mathbf{G}_{\cdot i}$ that are supposed to be updated, which corresponds to the reconstruction coefficients of $\mathbf{x}_{i}$ by its top-$k$ neighbors, let $\hat{\mathbf{g}}_{i}\in\mathbb{R}^{k}$ denote the vector of these elements. Let $\mathcal{N}_{i}$ be the set of the indexes of these neighbors corresponding to $\hat{\mathbf{g}}_{i}$. Define matrix $\mathbf{D}^{x_{i}}=[\mathbf{x}_{i}-\mathbf{x}_{\mathcal{N}_{i(1)}},\mathbf{x}_{i}-\mathbf{x}_{\mathcal{N}_{i(2)}},...,\mathbf{x}_{i}-\mathbf{x}_{\mathcal{N}_{i(k)}}]^{\mathsf{T}}\in\mathbb{R}^{k\times l}$ and $\mathbf{D}^{p_{i}}=[\mathbf{p}_{i}-\mathbf{p}_{\mathcal{N}_{i(1)}},\mathbf{p}_{i}-\mathbf{p}_{\mathcal{N}_{i(2)}},...,\mathbf{p}_{i}-\mathbf{p}_{\mathcal{N}_{i(k)}}]^{\mathsf{T}}\in\mathbb{R}^{k\times l}$, let Gram matrices $\mathbf{B}^{x_{i}}=\mathbf{D}^{x_{i}}(\mathbf{D}^{x_{i}})^{\mathsf{T}}\in\mathbb{R}^{k\times k}$ and $\mathbf{B}^{p_{i}}=\mathbf{D}^{p_{i}}(\mathbf{D}^{p_{i}})^{\mathsf{T}}\in\mathbb{R}^{k\times k}$, we can transform the problem in Eq. (21) into the following form:

The optimization problem in Eq. (22) is a standard Quadratic Programming (QP) problem, and can be solved by off-the-shelf QP tools. $\mathbf{G}$ is updated by concatenating all the solved $\hat{\mathbf{g}}_{i}$ together.

With other variables fixed, the $\mathbf{P}$-subproblem is

and we rewrite the problem in Eq. (23) into the following form:

In order to solve the problem (24), we denote $\widetilde{\mathbf{p}}={\rm vec}\left(\mathbf{P}\right)\in[0,1]^{nl}$, where ${\rm vec}(\cdot)$ is the vectorization operator. Similarly, $\widetilde{\mathbf{o}}={\rm vec}\left(\frac{\mathbf{H}+\beta(\mathbf{E}-\mathbf{Q})}{1+\beta}\right)\in\mathbb{R}^{nl}$ and $\widetilde{\mathbf{y}}={\rm vec}(\mathbf{Y})\in\{0,1\}^{nl}$. Let $\mathbf{T}=2(\mathbf{I}_{n\times n}-\mathbf{G})(\mathbf{I}_{n\times n}-\mathbf{G})^{\mathsf{T}}\in\mathbb{R}^{n\times n}$ be a square matrix. Based on these notations, the optimization problem (24) can be written as

where $\mathbf{C}\in\mathbb{R}^{nl\times nl}$ is defined as:

As the problem in Eq. (25) is a standard QP problem, it can be solved by off-the-shelf QP tools.

As a summary, PL-CL first initializes $\mathbf{G}$ and $\mathbf{P}$ by solving problems (5) and (6) respectively, and initializes $\mathbf{Q}$ as:

Then, PL-CL iteratively and alternatively updates one variable with the other fixed until the model converges. For an unseen instance $\mathbf{x}^{\ast}$, the predicted label $y^{\ast}$ is

The pseudo code of PL-CL is summarized in Algorithm 1.

The complexity for solving $\mathbf{W}$, $\mathbf{b}$, $\hat{\mathbf{W}}$ and $\hat{\mathbf{b}}$ is $O(n^{3})+O(nql)$, that for updating $\mathbf{Q}$ is $O(nl)$, and complexities for updating $\mathbf{G}$ and $\mathbf{P}$ are $O(nk^{3})$ and $O(n^{3}q^{3})$. Therefor the overall complexity of PL-CL is $O(n^{3}+nql+nl+nk^{3}+n^{3}q^{3})$.

In order to validate the effectiveness of PL-CL, we compared it with six state-of-the-art PLL approaches:

• •

  PL-AGGD (Wang et al., 2022): a PLL approach which constructs a similarity graph and further uses that graph to realize disambiguation [hyper-parameter configurations: $k=10$, $T=20$, $\lambda=1$, $\mu=1$, $\gamma=0.05$];

• •

  SURE (Feng and An, 2019): a self-guided retraining based approach which maximizes an infinity norm regularization on the modeling outputs to realize disambiguation [hyper-parameter configurations: $\lambda$ and $\beta$ $\in\{0.001,0.01,0.05,0.1,0.3,0.5,1\}$];

• •

  LALO (Feng and An, 2018): an identification-based approach with constrained local consistency to differentiate the candidate labels [hyper-parameter configurations: $k=10$, $\lambda=0.05$, $\mu=0.005$];

• •

  IPAL (Zhang and Yu, 2015): an instance-based algorithm which identifies the valid label via an iterative label propagation procedure [hyper-parameter configurations: $\alpha=0.95$, $k=10$, $T=100$];

• •

  PLDA (Wang and Zhang, 2022): a dimensionality reduction approach for partial label learning [hyper-parameter configurations: PL-KNN];

• •

  PL-KNN (Hüllermeier and Beringer, 2005): an averaging-based method that averages the neighbors’ candidate labels to make prediction on an unseen sample [hyper-parameter configurations: $k=10$].

For PL-CL, we set $k=10$, $\lambda=0.03$ , $\gamma$, $\mu$, $\alpha$ and $\beta$ were chosen from $\{0.001,0.01,0.1,0.2,0.5,1,1.5,2,4\}$. The kernel functions of SURE, PL-AGGD and LALO were the same as that of PL-CL. All the hyper-parameter configurations of each method were set according to the original paper. Ten runs of 50%/50% random train/test splits were performed, and the averaged accuracy with standard deviations on test data sets were recorded for all the comparing algorithms.