Deep Partial Multi-Label Learning with Graph Disambiguation

Our ultimate goal is to estimate a multi-label predictor $f:\mathcal{X}\mapsto[0,1]^{L}$ from $\mathcal{D}$. In this work, we assume that its output $\hat{\bm{y}}=f(\bm{x})$ satisfies the following properties,

1. 1.

   $\hat{\bm{y}}$ is close to the candidate vector $\bm{y}$;

2. 2.

   $\hat{\bm{y}}$ satisfies the instance-level similarity. That is, if two instances are close to each other, then their label vectors are likely to be close too;

3. 3.

   $\hat{\bm{y}}$ satisfies the label-level similarity. That is, if two labels co-occur in the training data frequently, then they tend to co-exist at many instances.

These properties coincide with our goals. The first property is natural since the only thing we can trust is the candidate label set. The second one has been widely adopted to disambiguate the ground-truth label from the false-positive labels. The last one exploits the label correlations to further promote the performance. In this paper, we adopt a graph-based model to achieve these goals. Generally speaking, the graph structure can be collected in various ways. One direct strategy is to use prior knowledge. For instance, for data mining tasks, social networks Qiu et al. (2018) can be used to depict instance similarity. The label similarity can also be estimated using an external knowledge graph Lee et al. (2018).

However, we notice that there is no available graph structure in existing public PML datasets. Hence, we propose to construct the instance graph $\bm{A}^{x}\in\mathbb{R}^{n\times n}$ and the label graph $\bm{A}^{y}\in\mathbb{R}^{L\times L}$ in a data-driven way. To obtain $\bm{A}^{x}$, we adopt a monomial kernel Iscen et al. (2017) as the distance metric and calculate a sparse instance affinity matrix $\bm{S}\in\mathbb{R}^{n\times n}$ with elements,

Here $\mathcal{N}_{k}(\bm{x}_{i})$ saves the indices of $k$-nearest neighbors of $\bm{x}_{i}$. $\rho>0$ controls the weights of similarity. Then, we get a symmetrized instance graph by $\bm{A}^{x}=\bm{S}+\bm{S}^{\top}$.

Inspired by HALE Lyu et al. (2020), we build the label graph $\bm{A}^{y}$ by means of the label co-occurrence statistics from the training data, whose elements are given by,

where $\mathbb{I}(\cdot)$ is an indicator function returning $1$ if the event is true and $0$ otherwise. It is worth noting that HALE simply calculates the average co-occurrence by dividing the instance number, which overlooks the existence of false-positive labels. In our method, we penalize it by the counts of instances that are assigned the labels as the candidates. In other words, if one label is assigned to too many instances, its co-occurrence statistics are less reliable.

Next, we impose the instance-level similarity property on the model output by means of a Laplacian regularizer,

where $\hat{\bm{Y}}=[\hat{\bm{y}}_{1},\ldots,\hat{\bm{y}}_{n}]^{\top}$ is the predicted label matrix. $\bm{L}_{x}=\bm{I}-\bm{D}_{x}^{-\frac{1}{2}}\bm{A}^{x}\bm{D}_{x}^{-\frac{1}{2}}$ is the Laplacian matrix of instance graph. $\bm{D}_{x}=\text{diag}[d_{1}^{x},\ldots,d_{n}^{x}]$ is a diagonal matrix with $d_{i}^{x}=\sum_{j=1}^{n}a^{x}_{ij}$. The objective in Eq. (1) enforces two data examples to have similar predicted labels if they have a large affinity score. Similarly, we can introduce the label-level similarity by,

Finally, we involve a candidate consistency term to get the following objective,

where $||\cdot||_{F}$ is the Frobenius norm. $\eta$, $\alpha$, and $\beta$ are all positive hyperparameters.

In summary, the main goal of our objective is to utilize the instance- and label-level similarity to recover reliable label confidences and address the problem of false positives, while simultaneously enjoying an extra performance improvement by exploiting label correlations.

If a linear model is adopted, the parameters can be directly obtained by optimizing $\mathcal{J}(f(\bm{X}),\bm{Y})$ with gradient descent. However, in deep models, it is not the case. When we update the model using a mini-batch of data, the instance-level manifold regularizer can involve unexpected gradient updating on the nearest neighbors of these data. Then, the training time will increase rapidly. To remedy this problem, we propose an efficient optimization framework for training a deep model from PML data. Specifically, we maintain a smooth pseudo-label matrix $\bm{Z}$, which minimizes the propagation error while being close to the model output $\hat{\bm{Y}}$. In the sequel, we elaborate the training procedure of our model. The training procedure is also summarized in Algorithm 1.

We employe a total of twelve synthetic as well as real-world datasets for comparative studies. Specifically, the synthetic ones are generated from the widely-used multi-label learning datasets. A total of nine benchmark multi-label datasets¹¹1http://mulan.sourceforge.net/datasets-mlc.html are used for synthetic PML datasets generation, including Emotions, Birds, Medical, Image, Bibtex, Corel5K, Eurlex-dc, Eurlex-sm, NUS-WIDE. Note that NUS-WIDE is a large-scale dataset, and we preprocess it as in Lyu et al. (2020). For each data example in MLL datasets, we randomly select $r$ irrelevant labels and aggregate them with the ground-truth labels to obtain a candidate set. For example, given an instance $\bm{x}_{i}$ and its ground-truth label set $\tilde{S}_{i}$, we select $r$ labels from its complementary set $\mathcal{Y}-\tilde{S}_{i}$. If there are less than $r$ irrelevant labels, i.e. $|\mathcal{Y}-\tilde{S}_{i}|<r$, we simply set the whole training set $\mathcal{Y}$ as the candidate set for $\bm{x}_{i}$. Following the experimental settings in Lyu et al. (2020), we choose $r\in\{1,2,3\}$, resulting in $27$ $(3\times 9)$ synthetic datasets. Furthermore, we conducted experiments on three real-world PML datasets Zhang and Fang (2021), including Music-emotion, Music-style, Mirflickr. These three datasets are derived from the image retrieval task Huiskes and Lew (2008), where the candidate labels are collected from web users and then further verified by human annotators to determine the ground-truth labels.

We choose six benchmark methods for comparative studies, including two MLL methods ML-KNN Zhang and Zhou (2007), GLOCAL Zhu et al. (2018), and four state-of-the-art PML methods PML-NI Xie and Huang (2022), PARTICLE Zhang and Fang (2021), HALE Lyu et al. (2020), and PML-lc Xie and Huang (2018). In particular, PARTICLE and HALE are two advanced graph-based PML methods. PARTICLE Zhang and Fang (2021) adopts an instance-level label propagation algorithm to disambiguate the candidate labels. HALE Lyu et al. (2020) regards the denoising procedure as a graph-matching procedure.

The parameter setups for the used methods are as follows. We fix $k=10$ for all $k$NN-based methods, including PLAIN. For the baselines, we fix or fine-tune the hyperparameters as the suggested configurations in respective papers. For our PLAIN method, the deep model is comprised of three fully-connected layers. The hidden sizes are set as $[64,64]$ for those datasets with less than $64$ labels, and $[256,256]$ for those datasets with more than $64$ and less than $256$ labels. For the remaining datasets, we set the hidden sizes as $[512,512]$. The trade-off parameters $\alpha$ and $\beta$ are hand-tuned from $\{0.001,0.01,0.1\}$. $\eta$ is selected from $\{0.1,1,10\}$. Following Iscen et al. (2017), we set $\rho=3$. We train our deep model via stochastic gradient descent and empirically set the learning rate as $0.01$ for both propagation and deep model training procedures. The number of maximum iterations is set as $T=200$ for small-scale datasets and $T=50$ for the large-scale NUS-WIDE dataset. Besides, weight decay is applied with a rate of $5e^{-5}$ to avoid overfitting.

For performance measure, we use three widely-used multi-label metrics, ranking loss, average precision and hamming loss Zhang and Zhou (2014). Finally, we perform ten-fold cross-validation on each dataset and the mean metric values as well as the standard deviations are reported.

Table 1 reports the experimental results on real-world datasets. Table 3 lists the results on synthetic datasets, where the parameter is configured with $r=3$. The results of $r=1,2$ are consistent with those of $r=3$ and thus are omitted. To better understand the superiority of the proposed method, we summarize the win/tie/loss counts on all synthetic datasets in Table 2. We also report the statistical testing results in Appendix B for analyzing the relative performance amongst competing algorithms. Based on these results, we can draw the following observations:

• •

  The proposed PLAIN method significantly outperforms all other competing approaches. For example, on the Music-emotion and Mirflicker datasets, in terms of average precision, PLAIN achieved results superior to those of the best baselines by $\bm{6.07}$% and $\bm{6.94}$% respectively.

• •

  According to Table 2, out of 486 statistical comparisons, six competing algorithms, and three evaluation metrics, PLAIN beats the competing methods in $\bm{82.30}$% cases. In particular, PLAIN wins or ties the baselines in $\bm{95.68}$% cases regarding average precision.

• •

  ML-KNN and GLOCAL obtain inferior performance on many datasets, such as Medical and Eurlex-dc. The reason is that these tailored MLL models regard all the candidate labels as the ground-truth and thus tend to overfit the false-positive labels.

• •

  Two PML methods PML-NI and HALE are strong baselines. In particular, PML-NI achieved the second-best results on most datasets. However, PLAIN performs significantly better than them, since their performance is restricted to the linear classifier.

• •

  On large-scale dataset NUS-WIDE, PLAIN still outperforms other methods on all evaluation metrics. It demonstrates the effectiveness of PLAIN in handling high-volume of data.