Discovering Latent Class Labels for Multi-Label Learning

1 Introduction

MLL [Zhang and Zhou, 2014; Gibaja and Ventura, 2015] deals with data examples with multiple class labels simultaneously. Many well-known approaches have been proposed to solve different problems of MLL, such as partial MLL [Wang et al., 2019; Xu et al., 2019], extreme MLL [Wei et al., 2019; Jain et al., 2019; Chen et al., 2019], missing labels [Yu et al., 2014; Yang et al., 2016; Tan et al., 2018], and multi-view MLL [Xing et al., 2018; Wu et al., 2019]. It is noted that existing approaches mainly assume that all the class labels are observed in advance. However, in some applications, some latent labels might be completely unobserved and hidden in the data, and below is a summary of two possible reasons:

1. Labeling Cost. In the big data era, it is difficult to provide a complete label set for a data, especially a largescale data with an extreme number of labels. Labelling efforts usually focus on the given set of target labels, while labels outside this set will not be considered.
2. Limitation of knowledge. For example, in medical diagnosis, possible diseases will be predicted according to

∗ corresponding authors

the patient's symptoms by the model constructed on the history data [Zhang et al., 2018]. However, complicated diseases may definitely exist but have not been discovered due to the limitation of human's knowledge.

Discovering and exploring the class labels hidden in the data may not only find interesting knowledge but also improve the performance on known labels [Pham et al., 2015; Zhu et al., 2017a]. Therefore, it is important to construct a robust model for MLL which can not only discover the latent labels but also could predict new data examples with both the known and latent labels simultaneously.

Approaches have been proposed to solve data classification with an unfixed label set, such as online learning for single-label learning (SLL) [Kuzborskij et al., 2013; Nguyen et al., 2016; Zhu et al., 2017b] and MLL [Hua and Qi, 2008; Xioufis et al., 2011; Zhu et al., 2018; Zhang et al., 2020], However, in the settings of online learning, novel labels are only induced by new instances, and they will not be discovered if they are hidden in the existing training data. MIMLNC [Pham et al., 2015] and DMNL [Zhu et al., 2017a] are two highly related studies on discovering new label(s) for multiinstance multi-label learning (MIMLL). MIMLNC is a probabilistic model to identify novel instances for MIMLL, but it assumes that all novel instances belong to a single new label. DMNL tries to discover multiple novel labels for MIMLL. It assumes that there are k novel labels, and the problem is formulated as a non-negative orthogonal constrained optimization problem which has a bag-dependent loss term and a bagindependent clustering regularization term. However, these two approaches cannot be applied to general single-instance MLL problems directly.

In this paper, a novel approach named DLCL is proposed for MLL which can not only discover the latent labels in the training data but also predict new instances with both the latent and known labels. On the one hand, we try to improve the performance of known labels by exploring the information provided by the discovered latent labels. On the other hand, we exploit the knowledge of known labels to guide the discovery of latent labels.

2 ProposedMethod

Let X∈Rd be the feature space, and ˆ Y=Y∪ ¯ Y be the label set, where Y={y1, ..., yq} and ¯ Y={yq+1, ..., yq+k} indicate the observed and latent labels respectively. X∈Rn×d indicates the data matrix, and ˆY=[Y, ¯Y]∈{0, 1}n×l represents the label matrix, where l=q+k. Y∈{0, 1}n×q and ¯Y∈{0, 1}n×k indicates the observed and latent label matrices respectively. If xi belongs to yj, then yij=1; otherwise yij=0.

2.1 Discovering Latent Class Labels

Problem Definition (Discovering Latent Class Labels for MLL). Given an MLL data set with q known labels, the problem of discovering latent class labels for MLL is to detect previously unknown labels (e.g., k latent labels) for each instance in the training set, and build a model which can predict unseen data examples with both the known and latent labels.

The aim is to construct a MLL model h : X → 2 ˆ Y , but ¯Y is unknown at first. Motivated by previous work on clustering based matrix factorization [Hu and Chen, 2019], we try to learn an approximate representation U ∈ {0, 1}n×l for the completed label matrix ˆY=[Y, ¯Y]. Since Y is known in advance, and thus the results of the first q columns of U should be consistent with that of known class labels. Therefore, the optimization problem can be defined as

where V ∈ Rl×d is the coefficient, and P ∈ Rl×q is a projection matrix which is composed of the first q columns of an l × l identity matrix. Once U is obtained, we can initialize ¯Y according to U, i.e., U(:,(q+1):l). Then, we can construct a MLL model with a squared loss as

where W=[w1, ...,wl] ∈ Rd×l is the coefficient matrix, and ℓ1-norm regularization is used to learn sparse labelspecific features [Zhang and Wu, 2015; Huang et al., 2016; Huang et al., 2018; Wei et al., 2019; Wu et al., 2019; Huang et al., 2019]. For the simplicity of optimization, the discrete constraint on the values of matrix U is relaxed to continuous, i.e., ∀ uij ∈ [0, 1].

It is worth noting that the latent labels may have correlations with known labels more or less, and thus it was expected that the performance on known labels and latent labels will be both boosted by exploiting the correlations between them. Thus, let C be the label correlation matrix. Each element cij indicates the value of correlation between the i-th and j-th labels, and is estimated by calculating the cosine similarity between ˆY:,i and ˆY:,j. Since ¯Y is unknown, the calculated correlations between known and latent labels may not be reliable enough. Thus, we introduce an extra matrix R ∈ Rl×l , and each element rij indicates the confidence of cij as

Then, we try to exploit the pairwise label correlation by modeling the Euclidean distance between any pair of model coefficient vectors. Specifically, if yi and yj have a strong correlation, their corresponding coefficients wi and wj will be similar, and thus the distance (i.e., dij=‖wi -wj‖2) will be small. Otherwise, the distance will be large. The fourth term of (2) was utilized to model pairwise label correlation.

3 Optimization

An alternating optimization strategy is adopted to solve problem (2), and L represents the objective function of it.

3.1 UpdateW

With U and V fixed, problem (2) reduces to

where L is graph Laplacian of the weighted correlation matrix C⊙R. Thus, the gradient w.r.t W can be calculated as

The ℓ1-norm regularization w.r.t W can be solved by the element-wise soft-threshold operator. According to the proximal gradient descend algorithm [Beck and Teboulle, 2009], W can be updated by

where W(t) = Wt + αt-1-1 αt (Wt -Wt-1). Lf is the Lipschitz constant, and an upper bound of it is shown in Theorem 1. For a sequence αt, it should satisfy the condition of α2 t -αt ≤ α2 t-1 , and proxϵ(a) is the element-wise operator which is defined as

Theorem 1 (Lipschitz Continuous Gradient). Given two arbitrary distinct parameters W1 and W2, we have

where γ = 2‖XT X‖22 +2‖λ3L‖22 and ∆W=W1-W2, and an approximate Lipschitz constant can be calculated by,

Proof. GivenW1 andW2, according to Eq. (5), we have

Algorithm 1 Training of DLCL

Input: Training data: X ∈ Rn×d , label matrix Y ∈ Rn×q ; Parameter: The non-negative weighting parameters λ1, λ2,

λ3, and λ4, the number of latent class labels k, and α;

Output: W, U, and V

• 1: α1 = 1.
• 2: InitializeW, U, and Vwith random value.
• 3: ¯Y =U(:,(q+1):l).
• 4: while stop criterion not reached do
• 5: Calculate C based on ˆY.
• 6: Let C=C⊙R, and then calculate L.
• 7: calculate Lf according to Eq. (8).
• 8: updateWaccording to Eq. (6).
• 9: update U according to Eq. (10).
• 10: update V according to Eq. (13).
• 11: search β∗ according to (14).
• 12: update ¯Y according to Eq. (15).
• 13: αt+1 ← 1+√4α2t +1 2
• 14: end while
• 15: returnW, U, and V

3.2 Update U

With W and V fixed, problem (2) becomes

Thus, the gradient w.r.t U can be calculated as

Therefore, we can obtain a closed-form solution for U as

Then, ∀ uij ∈ [0, 1] can be achieved by U = max(U, 0) and the min-max normalization over each column of U.

3.3 Update V

With U and W fixed, problem (2) is simplified as

Consequently, the gradient w.r.t V can be calculated by

Then, a closed-form solution for V can be obtained as

3.4 Update ˆY

In (2), ˆY=[Y, ¯Y] is the full label matrix, and ¯Y indicates the latent label matrix and is unknown in advance. Therefore, we need to update ¯Y after each iteration of the optimization. As aforementioned, U is an approximate representation of ˆY. Besides, we can also obtain a result from the classifier, i.e., XW, and it is expected that the useful information (i.e., label correlation) induced from the known label can lead to a good prediction on the latent labels. Therefore, we plan to update ¯Y according to both of U and XW with a balance weight β ∈ (0, 1). Since Y is known, we can search a proper value for β from {0.05, 0.1, ..., 0.95} according to (14).

Then, ¯Y can be updated by

4 Experiment

4.1 Experimental Setting

By surveying previous work on MLL, we noted that there is no previous work doing the same topic like us. MIMLNC [Pham et al., 2015] and DMNL [Zhu et al., 2017a] are the only two highly related studies on discovering novel labels, but these two approaches are tailored for MIMLL, and cannot be applied to general single-instance MLL directly. In order to verify the effectiveness of our proposed method, we compare DLCL with four state-of-the-art approaches in terms of their performance on known labels. Detailed configurations of them are summarized as: 1) BR [Boutell et al., 2004]: Binary Relevance. It learns a binary classifier (one-vs-rest) for each label independently, and Linear Regression is utilized as the base binary learner for it, and the regularization parameter is tuned in {10i |i = -2, ..., 2}. 2) MLkNN [Zhang and Zhou, 2007] 1 : A lazy learning approach to MLL, the number of nearest neighbors k is searched in{7, ..., 17}. 3) LLSF [Huang et al., 2016] 2 : Learning label-specific features for MLL, the regularization parameters are tuned in {2i |i = -10, ..., 10}. 4) KRAM [Jia and Zhang, 2019] 3 : Multi-dimensional classification via knn feature augmentation. The number of nearest neighbors k is searched in{7, ..., 17}. 5) DLCL: The proposed approach in this paper. Parameters λ1 and λ2 are tuned in {10i |i = 2, ..., 6}, λ3 is tuned in {2i |i = -2, ..., 4}, λ4 is tuned in {10i |i = -2, ..., 1}, and α is tuned in {0.4, 0.5, 0.6}. Parameter tuning for each of them is based on a 5-fold cross validation over the training data of each data set.

Table 1 shows a summarization of the twelve experimental data sets. We adopt six common evaluation metrics [Zhang and Zhou, 2014], i.e., Hamming Loss, Average Precision, One Error, Ranking Loss, Coverage, and Macro AUC, to evaluate the performance of the comparing algorithms on known labels. To evaluate the performance of our method on discovered latent labels, we adopt the following metric proposed in [Zhu et al., 2017a],

1 code: http://palm.seu.edu.cn/zhangml/files/ML-kNN.rar

2 code: http://www.escience.cn/people/huangjun/index.html

3 code: http://palm.seu.edu.cn/zhangml/files/KRAM.rar

where F(·) is the function of F-measure, and G indicates the ground-truth label matrix. Fnovel measures the average performance on detected multiple latent labels on the ground-truth label that best matches.

4.2 Experimental Results

For each data set, 80% of it are randomly generated as the training part and 20% for testing, which is repeated 10 times. Following the settings in previous work on discovering new labels for MIMLL [Pham et al., 2015; Zhu et al., 2017a], the first 70%, 80% and 90% labels are set be to known labels and the rest are taken as latent ones respectively. The average results of each comparing algorithm on the known labels are shown in Table 2. ↑ (↓) indicates the larger (smaller) the value, the better the performance. Best results are highlighted in bold face.

Results on Known Labels. Friedman test [Demˇ sar, 2006] is employed to conduct performance analysis among the comparing approaches, and the result of it is shown in Table 3. As shown in Table 3, the null hypothesis that all the comparing algorithms perform equivalently is clearly rejected in terms of all the evaluation metrics at significance level α = 0.05, Consequently, the Nemenyi test [Demˇ sar, 2006] is adopted to analyse the relative performance among them. For Nemenyi test, the critical difference CD=qα√ k(k+1) 6N =1.0167 (k=5, N=36) with qα=2.728 at significance level α=0.05, where k is the number of algorithms and N (16 × 3) is the number of data sets. The CD diagrams of DLCL w.r.t to the comparing algorithms on each evaluation metric are shown in Figure 1. In each sub-figure, any comparing algorithm whose average rank is within one CD to that of DLCL is connected. Otherwise, any algorithm not connected with DLCL is considered to have significant different performance between them. According to these experimental results, the following observations can be made: 1) The proposed method DLCL significantly outperforms the comparing algorithms in terms of ranking loss, average precision, coverage, and AUC. Besides, DLCL statistically outperforms the comparing algorithms in terms of hamming loss and one error. These results definitely demonstrate the effectiveness of our method on MLL. 2) KRAM and MLkNN algorithms are all constructed based on the information of k nearest neighbors of each instance. It is worth noting that these two algorithms achieve worse performance on those data with a large number of labels (e.g., l≥100) than on those data with a small number of labels. One possible reason might be that the k nearest neighbors can not provide sufficient information for model construction when many labels are hidden in the data. These results verify the importance of discovering latent class labels for MLL.

Results on Latent Labels. Table 4 shows the results of DLCL on discovered latent class labels according to Fnovel. It is clearly indicated that DLCL can discover the latent labels for MLL, and DLCL significantly outperforms RS(Randomly Setting) when q = 70l% and k = 30l%. For some data sets, the results of Fnovel differ extremely under different ratios of latent labels. The possible reason might be that the difficulties of prediction of different labels are different. On the other hand, we want to know what latent labels have we discov-

k

Figure 3: Parameter analysis on DLCL over stackex-chemistry.

ered. We try to describe the meaning of them by the learned labels-specific features which are indicated by the non-zero entities of each column of W. Table 5 shows the results of the five best matched labels over the stackex-cs data set with q = 70l% and k = 30l%. It is noted that the names of top five matched labels are the occurred among the top 20 features or homologous with them, and most of features have a strong semantic correlation with the name of labels.

4.3 Parameter and Convergence Analysis

The number of Latent labels k and correlation confidence α. For arts, the first 20 and the rest 6 labels are set as known and latent labels respectively. Figure 2 shows the average results of DLCL over 10 repetitions with different values of k and α. The result (i.e., Macro AUC) on known labels is improved by discovering latent labels (i.e., k > 0), and the Fnovel decreases with the increasing of k. The larger the number of latent labels, the harder it is to discover them. Therefore, we could set k to be a relative small value and run DLCL multiple times. It is also noted that the performance of latent labels can be significantly improved with the help of known labels and the improvement on known labels is slightly with the help of latent labels by exploiting their correlations (i.e., α > 0). The known labels are observed in advance and can be considered as a teacher to guide the prediction on latent labels.

Analysis on regularization parameters. The average results (i.e, Average Precision) of DLCL with different values of λ1, λ2, λ3, and λ4 over stackex-chemistry are shown in Figure 3, and similar results were also obtained for the other data sets. It is noted that the performance of DLCL is insensitive to the parameters, and also the optimal performance is usually achieved at some intermediate values of each parameter.

Convergence. Figure 4 demonstrates two examples of the convergence curves of DLCL. It is noted that the values of the objective function are non-increasing and drop sharply around 15 iterations on corel5k and stackex-cs data sets.

5 Conclusion

In this paper, a novel approach named DLCL is proposed for MLL which can not only discover the latent labels in the training data but also predict new instances with these latent labels and known labels simultaneously. The experimental results demonstrate that the performance of latent labels can be significantly improved with the help of known labels and the performance of known labels can be improved with the help of latent labels by exploiting their correlations. Extensive experiments with other state-of-the-art MLL approaches have show a competitive performance of DLCL.

Acknowledgement

This work is supported by JST KAKENHI: 191400000190, JST-AIP: JPMJCR19U4, and NSFC: 61806005.