Dual Relation Semi-Supervised Multi-Label Learning

Multi-label learning (MLL) solves the problem that one single sample corresponds to multiple labels. It is a challenging task due to the long-tail label distribution and the sophisticated label relations. Semi-supervised MLL methods utilize a small-scale labeled samples and large-scale unlabeled samples to enhance the performance. However, these approaches mainly focus on exploring the data distribution in feature space while ignoring mining the label relation inside of each instance. To this end, we proposed a Dual Relation Semisupervised Multi-label Learning (DRML) approach which jointly explores the feature distribution and the label relation simultaneously. A dual-classifier domain adaptation strategy is proposed to align features while generating pseudo labels to improve learning performance. A relation network is proposed to explore the relation knowledge. As a result, DRML effectively explores the feature-label and label-label relations in both labeled and unlabeled samples. It is an end-to-end model without any extra knowledge. Extensive experiments illustrate the effectiveness and efficiency of our method.


Introduction
Real-world objects could have multiple labels (e.g., colors, shapes, textures, and categories). Multi-label learning (MLL) was proposed to predict tens or hundreds of different labels for a single instance. MLL has become an attractive and emerging field (Boutell et al. 2004) as it can be applied in a lot of practical applications (e.g., data mining (Cong et al. 2018), image retrieval (Verma and Jawahar 2017) and image annotation (Verma and Jawahar 2017)).
There are two major challenges. First, the multi-label usually follows the long-tail distribution, which means that different labels appear in different frequencies. Some labels rarely show up (e.g., Fight and Fall down) while some labels are common (e.g., Daytime and Natural light). Technologically, deploying more samples in the training stage could solve this problem. However, it is not practical as the longtail label distribution characteristic, which means it is hard to collect a dataset with enough and balanced information. The scale of the available well-labeled datasets (Duygulu et al. 2002;Wah et al. 2011;Patterson and Hays 2012) is relatively small compared with single-label datasets. Second, the label relations are crucial to improve the MLL performance (Wu et al. 2018b). As illustrated in Figure 1. Some labels have negative relations (e.g., Sunny and Rainy) which are rare to show up together. While some labels have positive relations (e.g., Rainy and Wet) which usually appear together, and some labels have weak or no distinctive relations (e.g., Wet and Sunny). Unfortunately, few datasets have the relation information as prior knowledge. Besides, the relation map is manually defined and task-specific. It is difficult to extend to other MLL tasks, which limits the potential applications of these approaches.
Although there are not enough labeled samples, the related unlabeled samples are easy to get. Consequently, semi-supervised learning (Zhu, Ghahramani, and Lafferty 2003) came up and has achieved great progress in MLL tasks (Dong, Li, and Zhou 2018;Zhaomin et al. 2019). Conventional semi-supervised approaches mainly analyze the data in feature space. However, the distribution of the label and unlabeled features could be different which would affect the final performance. Moreover, most methods are inspired by the single-label classification approaches while ignoring  Figure 2: In our model, P (·) and the two classifiers (i.e., C 1 (·) and C 2 (·)) are designed to project samples from the original feature space to a latent subspace for reducing the distribution gap of labeled and unlabeled samples. The two initial predicted labels from C 1 (·) and C 2 (·) are forwarded to the intra-instance label relation network C R (·) to further explore the label relations and get final high accurate results. The reliable pseudo labels will be aligned to unlabeled data to increase the learning performance. All modules are optimized simultaneously which is suitable for a wide range of practical applications.
the relations between multiple labels (Nie, Xu, and Li 2012).
In this work, we propose a novel Dual Relation Multilabel Learning (DRML) in semi-supervised manner. DRML includes a novel domain adaptation co-training strategy and a label relation mining module in semi-supervised fashion. It explores both the instance similarity in feature space and the label-label relation in label space simultaneously. Specifically, deploy a two-classifier domain adaptation strategy to align the feature distribution in a latent space. Moreover, it further provides the pseudo label of unlabeled samples to enhance the training performance. Furthermore, a relation network is proposed to utilize the predictions from the two classifiers to learn the label relations. All modules are simultaneously optimized in an end-to-end manner to achieve the highest performance. The major contributions of our work are briefly listed as follows: • A two-classifier domain adaptation co-training strategy is proposed. It aligns the labeled and unlabeled samples in feature space to improve model accuracy and robustness.
• A label assignment strategy is proposed to generate pseudo labels to the unlabeled data. The assigned samples are further utilized in the training process.
• A graph-based relation network is proposed to learn the label relations for both labeled and unlabeled samples.
Our model fully utilizes the potential of a few networks which are simultaneously optimized in an end-to-end scenario. It is effective, efficient, and easy to extend to a wide of range of real-world semi-supervised applications.

Related Work
Multi-label Learning MLL recovers multiple labels from a single sample. A lot of real-world applications are related to such problem, including text classification (Ghamrawi and McCallum 2005), image annotation (Kang, Jin, and Sukthankar 2006), and video concept recognition (Qi et al. 2007). Due to the massive amount of label combinations, MLL is more challenging compared with the single-label learning. FastTag (Chen, Zheng, and Weinberger 2013) was proposed to eliminate the negative effect of label noise. (Ge, Yang, and Yu 2018) introduces a fusion approach for MLL. To couple relevant tasks, a modulation module is proposed in (Zhao et al. 2018). However, the scales of MLL (Von Ahn and Dabbish 2004; Duygulu et al. 2002) are relatively small which limits its potential performance. Semi-supervised learning could address this issue by utilizing a small-scale of labeled data and a large-scale of unlabeled data. However, these approaches assume the distribution between labeled and unlabeled data are similar, while large distribution difference could cause a dramatic performance decrease. Label relation information is another crucial aspect for MLL. (Zhaomin et al. 2019) uses a semantic label hierarchy as prior knowledge to improve MLL performance. (Wu et al. 2018a) implements a label semantic structure, which covers different labels and avoids label noise. However, building such kind of label relation knowledge required sophisticated semantic knowledge which is difficult and expensive to get. Moreover, the obtained knowledge is difficult to extend to other datasets. This issue dramatically limits the potential of this strategy for real-world applications. Label embedding (Tai and Lin 2012) explores the label relations by projecting them to a latent space. (Chen et al. 2018) studies the object relations using attention and RNN. Therefore, we proposed a semi-supervised MLL approach. It learns the label relations from both labeled and unlabeled instances. This makes the learned label relation knowledge more accurate and comprehensive.

Semi-supervised Learning
Semi-supervised learning (SSL) utilizes labeled as well as unlabeled sets in the training process (Zhu 2005). SSL aims to explore extra information from the unlabeled data to enhance the learning performance. (Zhu, Ghahramani, and Lafferty 2003) proposed a continuous relaxation based on the discrete Markov random fields. (Sindhwani, Niyogi, and Belkin 2005) presents a semi-supervised kernel that is suitable for all input space. (Nie, Xu, and Li 2012) introduces an initialization independent method by actively selecting the training set. (Can et al. 2019) deploys a co-training model to address the domain shift problem between source and target data. (Wang, Ding, and Fu 2018b; generates an distinctive subspace to measure the similarities across source and target frames. ) presents a new generative approach in clustering setting. (Levatić et al. 2017) deploys decision trees and random forests to improve the performance. (Levatić et al. 2018) proposes semi-supervised trees to handle high computational cost and performance degradation issues. However, most of the methods focus on exploring the feature distribution of the unlabeled data.
In MLL scenario, the label relation is crucial. How to explore the label relation from the unlabeled data is still not well explored. In our model, the pseudo label is assigned to unlabeled data and further utilized in the training process which hopefully explores the label relations from the unlabeled samples to enhance the performance.

The Proposed Approach Preliminaries & Motivation
are the unlabeled feature and label matrix. Specifically, our approach aims to explore X l , X u and Y l to recover Y u . Since there is feature distribution gap between X l and X u , thus, it is natural to learn the feature presentation in a latent subspace where the labeled and unlabeled data can be well aligned. Meanwhile, there are sophisticated relations residing across different labels. To this end, a simple but effective label relation network is proposed to automatically explore the label relation knowledge. These two strategies allow the model to fully utilize the feature-label mapping and label-label relation knowledge from the labeled and unlabeled samples.

Our Approach
Our model ( Figure 2) contains a projector P (·), two multilabel classifiers C 1 (·) and C 2 (·) and a label relation network C R (·). P (·) projects all the samples into a latent space Z, where Z l ∈ R dz×n l and Z u ∈ R dz×nu are the representations of X l and X u in subspace Z, d z is the dimension of Z. As mentioned above, the feature distributions of X l and X u could be different. Directly utilize the original features could cause a negative effect. Inspired by MDA (Saito et al. 2018), we designed a two-classifier domain adaptation framework which achieves domain adaptation and initial multi-label prediction simultaneously. For classification purpose, the loss functions of C 1 (·) and C 2 (·) are below, where L C represents the classification errors of C 1 (·) and C 2 (·). Meanwhile, the representation Z l and Z u are also optimized in the training process. Thus, C 1 (·), C 2 (·) and P (·) are simultaneously trained: By this way, the initial classification results could be obtained. Moreover, the two-classifier structure is able to train the projection P (·) for domain adaptation goal. It aims to align the distribution shift between X l and X u in the latent space Z. To achieve this goal, the projection and the classifiers are further trained in an adversarial way. First, when P (·) is fixed, the classifier C 1 (·) and C 2 (·) are optimized to maximize the classification difference of the unlabeled data X u . The prediction difference can be obtained by l 1 -norm which is shown below, where f 1 ∈ R d l ×1 and f 2 ∈ R d l ×1 are the predicted label vector from C 1 (·) and C 2 (·). f 1k and f 2k are the k-th entries of the label vector f 1 and f 2 . Both l 1 -and l 2 -norm could be deployed in Eq. (4) while we empirically found out l 1 -norm could achieve the best performance. It is a simple yet effective metric for measuring the prediction differences. Then, the objective of updating C 1 (·), C 2 (·) for maximizing classification difference can be written as follows: where L DA represents the classification difference. C 1 (·) and C 2 (·) are trained to maximize the classification differences of the unlabeled data, while it still needs to secure the classification performance on labeled samples. Thus, we add the L C term in the objective, and λ > 0 is the tradeoff parameter which balances the weight between classification difference and accuracy. On the other hand, P (·) tries to update the projection space which minimizes the unlabeled data classification difference. To this end, P (·) can be updated by the following function: Projection P (·), classifier C 1 (·) and C 2 (·) are alternately updated in an adversarial fashion based on Eq. (5) and Eq. (7). By this way, the labeled and unlabeled samples would be gradually aligned in the latent space Z, which could effectively reduce the negative influence of the distribution shift of labeled and unlabeled samples.
The outputs from both classifier C 1 (·) and C 2 (·) can be the final classification results. Averaging these two prediction results is an efficient strategy. However, as introduced before, label relation and trivial prediction differences are crucial to further improve the learning performance. To this end, we propose a simple but effective label-level relation network, C R (·), to automatically explore the label relation knowledge. As shown in Figure 2, after the predicted label f 1 and f 2 are obtained, we designed a label relation graph R i by multiplying f 1 and the transposition of f 2 as l ×1 vector and forwarded to a fully connected relation network C R (·). C R (·) further predicts the multi-label result based on R i . To this end, the objective of the relationship network is shown below: (8) where x i and y i ∈ R d l ×1 are a training sample and its ground truth multi-label vector of x i . In this framework, the elements in R i are the multiplication of each pair of the predicted labels, which could be considered as a dot-product similarity metric of the pairwise labels (including the similarity with itself). By this way, C R (·) explores the latent relation knowledge residing inside the training data based on the obtained similarities, and further refine the predicted label from C 1 (·) and C 2 (·) to improve performance. In the training procedure, C R (·) is trained simultaneously with the other networks which is shown as follow: where α is the trade-off parameter which balances the weight between initial prediction error and the relation network prediction error. Jointly optimizing C 1,2 (.) and C R (.) by combining their losses together could 1) control the training of C 1,2 (.) to predict initial labels and 2) intentionally force C R (.) to capture the label relations based on the initial labels from C 1,2 (.). This strategy balances the update processing between C 1,2 (.) and C R to further help each other in the training stage and achieve a promising performance at last. α is set to 0.5 as default. We have observed that slightly tuning α near 0.5 does increase the performance a little, and cross validation could be employed for automatic parameter tuning. Since the improvement is not significant, thus, we set α = 0.5 which avoids the parameter tuning procedure. C R (.) can be easily deployed for labeled samples. Meanwhile, in semi-supervised learning scenario, we assume that the unlabeled samples also include informative and comprehensive label relation knowledge. To this end, we utilize predicted labels from partial unlabeled samples as pseudo labels in the training process. By this way, C R (.) could further explore the correlation from the unlabeled samples and increase the learning performance. Since the prediction results of C 1 (·) and C 2 (·) are not reliable at the beginning of the training procedure. To this end, we first trained C 1 (·) and C 2 (·) for 50 to 100 iterations before we involve the pseudo label strategy in the complete training procedure.
Compared with single-label learning, we cannot simply determine the confidence of the predicted labels. To handle this problem, we fully utilize the two-classifier structure and measure the prediction differences between C 1 (·) and C 2 (·). Specifically, all target data are sent to C 1 (·), C 2 (·) and C R (·) and achieve the predictions. The prediction differences are   (6), we use l 2 -norm which is shown as follows: where z i is the i-th sample representation in space Z. Due to the difference among the datasets (e.g., feature scale, label numbers and labels formats), the pseudo label strategy is deployed a little differently for different datasets. Take CUB dataset (Wah et al. 2011) for example, we set a threshold value d = 1. If D(Z i ) ≤ d, we will select the testing instance x i with a pseudo label. For the other dataset, we select K samples with the lowest differences from the whole predictions. K is normally set to 10 to 20. After that, we give them the pseudo labels and add them to the training set for the next training loop. We deploy fully connected networks in our implementation. Other deep networks can be used to attain higher performance. In our implementation, P (·) is an one-layer fully-connected linear network. C 1 (·) and C 2 (·) are both one-layer fully-connected network with a Sigmoid activation after the last layer. C R (·) is an onelayer fully-connected network with Sigmoid activation after the last layer. Our model contains four networks which are jointly opti- mized in a minimax strategy, which brings in several advantages. First, it is an end-to-end model without the requirement of any other prior knowledge, which is easy to train and compatible for a lot of real-world applications. Second, the performance is stable and robust since the domain adaptation strategy is able to well align the distribution shift across the labeled and unlabeled data. Third, the label-level correlation is explored by the relation network in both labeled and unlabeled samples. Forth, our approach can be directly deployed for more testing data samples without any other optimization operations which are more simple and efficient compared with graph-based semi-supervised approaches.

Multi-label Datasets
We evaluate our model on six fine-grained multi-label datasets. ESP Game (Von Ahn and Dabbish 2004) has 18, 689 training images and 2, 081 testing images which is labeled by an ESP interactive gaming system. Corel5K (Duygulu et al. 2002) is an image dataset of the CDs. There are 4, 500 training samples and 499 testing samples. It is represented by a 260-dimensional semantic description vector in binary format. IAPRTC-12 (Grubinger et al. 2006) includes images of actions, animals, landscapes and other objects. It has 19, 627 training images and 1, 962 testing images. The label is represented by a 291dimensional vector in binary format. Each sample has 5.72 labels in average. CUB (Wah et al. 2011) has 8, 800 training images and 1, 440 testing images. This dataset contains 200 birds. The label information can be described by a 312-dimensional vector in binary format. Each instance has 31.39 labels in average. SUN (Patterson and Hays 2012) contains 12, 900 training images and 1, 440 testing images such as bakery, ballroom and balcony. There are 717 scene classes in total. These labels are assigned by multiple trained labors. Each instance has 6.31 labels in average. AWA (Lampert, Nickisch, and Harmeling 2014) contains 24, 295 training images and 6, 180 testing images. This dataset consists of 50 animal species. Each instance has 15 labels in average. We directly deploy the visual descriptors provided by (Guillaumin et al. 2009) for Corel5K, IAPRTC and ESP Game datasets. A pre-trained VGG Networks (Simonyan and Zisserman 2014) based on ImageNet is set as feature extractor for SUN, CUB and AWA datasets.

Experimental Setup
We evaluate our approach associated with several state-ofthe-art representative MLL methods. Least Square Regression (LR) directly learns a linear regression model from the feature space to the label spaces. Semi-Supervised Multi-Label Dimension Reduction (SSMLDR) (Guo et al. 2016) explores the information in both labeled and unlabeled data. To enhance the model robustness, it designs a specific label propagation strategy. Fast Image Tagging (FastTag) (Chen, Zheng, and Weinberger 2013) introduces two linear mappings to obtain the whole tags based on the incomplete tags. These two mappings are regularized in one loss function. Multi-Label learning using a Mixed Graph (ML-PGD) (Wu, Lyu, and Ghanem 2015) introduces a label dependencies model. It constructs a mixed graph and takes the similarity of instance level with class co-occurrence into consideration. Semantic AutoEncoder (SAE) (Kodirov, Xiang, and Gong 2017) introduces an effective auto-encoder model to recover labels. It also proposes an additional reconstruction constraint. Adaptive Graph Guided Embedding (AG2E) (Wang, Ding, and Fu 2018a) proposes an adaptive graph strategy. It jointly obtains the similarity graph and predicts multiple labels in a semi-supervised fashion.
Since C R (·) depends on the performance of C 1 (·) and C 2 (·), we train C 1 (·) and C 2 (·) for 50 epochs prior the training of other networks. When C 1 (·) and C 2 (·) become gradually stable, we begin to train C 1 (·), C 2 (·) and C R (·) simultaneously. We repeat the training procedure until C R (·) achieves a stable performance. After that, we add the pseudo label assignment section in the training procedure. Due to the difference label formats of the datasets, the pseudo label assignment approach is slightly different between different dataset. For CUB and AWA datasets, the pseudo label is the original output of C R (·). For SUN (Patterson and Hays 2012) dataset, the pseudo label is represented by the combinations of {0, 0.33, 0.66, 1} due to its unique label format. For other datasets, the pseudo label is binary.
We deploy the metrics proposed in (Guillaumin et al. 2009) for evaluation. The precision (Pre) P and the re-  , where t p is true-positive, f p is false-positive, and f n is falsenegative. For easy comparison, we calculate the F1-score, the harmonic mean of R and P , where F 1 = 2 P ×R P +R . The number of labels with a non-zero recall (N-R) value and the mean average precision (mAP) (Wu, Lyu, and Ghanem 2015) are further used for comprehensive evaluation. In all metrics, the higher value, the better performance.

Conventional & Zero-shot MLL
The result of conventional MLL is shown in Table 1. Our approach surpasses other baselines in most evaluations. Furthermore, (Wu, Lyu, and Ghanem 2015) proposes an augmented label set for Corel5K and ESP Game datasets. It increases average label number of Corel5K from 3.40 to 4.84, and the ESP from 4.69 to 7.27. We evaluate our model based on these label sets. The results (Table 2) indicates that our approach still achieves the best performance in most of the matrices.
We further apply our method to zero-shot MLL scenario which means the classes in training and testing sets are non-overlapping, while they still share same the multi-labels (e.g., horse and Zebra). It is more difficult because of the larger distribution gap between the two sets. We evaluate our approach based on SUN, CUB and AWA datasets. The default training and testing splits are provided. The specific splits are 645/72, 40/10 and 150/50 respectively. For CUB, there are 4 different ways to split. We test the model once for each split and calculate the average performance. For SUN and AWA datasets, we test the model for 5 times and calculate the mean performance. Table 3 indicates that our approach outperforms other methods which demonstrates that our approach is accurate and robust. In the real world, this is helpful since collecting the images from all possible classes is impossible. We also notice that our approach cannot achieve the highest performance in AWA dataset. We consider this in the following reasons. 1), AWA samples that belong to the same class share only one consistent semantic description, thus, it is difficult to comprehensively learn the feature-label relations; 2), there are limited relation information learned by CDN due to the consistent label issue.

Ablation Study
We run our model with and without CDN and the domain adaptation strategy on CUB dataset. Figure 3 illustrates the performance with the iteration increasing and details are introduced in the caption. The result illustrates that all the strategies can effectively improve the performance respectively, and the combination of all the proposed approaches do help each other and dramatically improve/stabilize the performance. We further visualize the original and projected features of 10 labelled (blue circle) and 10 unlabelled(yellow circle) classes from CUB dataset (Figure 4) by t-SNE (Van Der Maaten 2014). It illustrates that two distribution gap becomes smaller which demonstrates the effectiveness of the domain adaptation strategy. Figure 5 shows the time consumption of each method in the test stage. Due to the simple feed-forward network struc-  Figure 6: Samples of recovered labels from SUN dataset. Black font denotes correct prediction. Blue font denotes labels that do not exist in the ground truth but match our judgments. Red font denotes incorrect prediction.

37
Shopping 18 45 Figure 7: Image retrieval result of SUN dataset in the zero-shot scenario. Each row shows the images with the highest corresponding label scores. Green and red boxes indicate correct and incorrect retrieval, respectively. For each target label, we show incorrect retrieval result and its score rankings on the image right corner.
ture and the usage of GPU acceleration, even if the computational cost is a little higher, our approach only spends an average of 0.12 seconds to infer 2081 test samples which is the second fastest method. It indicates that our approach fits well for large-scale real-world applications.

Image Retrieval
The goal of Image retrieval is to find the images from a large dataset which contain one or more specific labels. We obtain the labels of each candidate image using our well-trained model then rank the labels by the predicted scores. We still deployed the zero-shot split setting since it is a more practical setting for most real-world applications. Figure 7 shows the images extracted from the dataset based on specific labels. We select incorrect results and mark the images with the ranking numbers on the bottom corner. We can see that most images are correctly retrieved with only a few errors. First, the adjective and verb labels are easier to retrieve than noun labels. And noun labels are easier to make a mistake when the image has a similar label and similar color (e.g., ice and running water). Second, the model always retrieval the scene from very similar class. Such as Asphalt, the model prefers to retrieve all field scenes on the road and in the airport. We can study these in the future.

Image Annotation
We evaluate image annotation performance on SUN dataset in Figure 6. We set different colors to indicate different labels and details can be found in the caption. We observe that most recovered labels are correct in our experiment. Under some circumstances, our model even discovered "new" labels. This proves that our approach is robust, effective and is able to recover the vast majority of labels with high accuracy. Furthermore, our model can discover the missing and error labels of the ground truth.