Partial Multi-Label Optimal Margin Distribution Machine

1 Introduction

Multi-label learning is a supervised learning framework to cope with the problems where each instance is associated with more than one class label [Boutell et al., 2004; Zhang and Zhou, 2013; Gibaja and Ventura, 2015]. Existing multilabel learning methods heavily rely on the high quality labeled data, which can be hardly satisfied in many real-world applications, because precise annotations are quite expensive and even impossible in some restricted scenarios. Instead, a set of noisy candidate labels are usually accessible. To deal with such imprecisely labeled data, the partial multi-label learning [Xie and Huang, 2018; Chen et al., 2020], a unified framework of multi-label learning and partial label learning [Cour et al., 2011; Feng and An, 2019], comes into being.

A trivial way to partial multi-label learning is to directly apply the vanilla multi-label learning methods [Zhang and Zhou, 2007; Feng et al., 2019], but due to the presence of false positive labels, these methods are prone to be misled and generalize poorly on unseen data. One more sensible way is to adopt some elaborated disambiguation strategies to recover the ground-truth labels during training, which can be further divided into two groups. One is the low-rank models, which assumes the ground-truth label matrix is intrinsically low-rank, and the noisy label matrix is sparse [Sun et al., 2019], or shares some low-rank subspace with feature matrix [Yu et al., 2018]. Besides the low-rank and sparse decomposition on label matrix, the same assumption has also been made on the learner side [Xie and Huang, 2020], which leads to a joint learning of a low-rank multi-label classifier and a sparse noisy label identifier. However, the low-rank requirement sometimes is too rigorous to fulfill, and all these methods can hardly incorporate the non-linear kernels. The other is the confidence learning models, whose main idea is to evaluate the possibility of each label being a ground-truth. For example in [Zhang and Fang, 2020], an iterative label propagation is performed at first and only those with confidence value above the threshold are treated as credible labels to train the subsequent multi-label classifier; while in [Xie and Huang, 2018; Wang et al., 2019], some smooth assumptions that highly correlated labels share similar confidence values or closest instances have similar ground-truth labels are adopted, and the confidence is learned through utilizing the local topological structure.

∗Contact Author

In this paper, we propose the Partial Multi-Label Optimal margin Distribution Machine (PML-ODM), which recovers the ground-truth labels via explicit optimization of the distribution of ranking margin. It is the generalization of ODM [Zhang and Zhou, 2019], a newly proposed learning framework rooting in margin theory [Gao and Zhou, 2013], thus it inherits the superiority and performs significantly better than the minimum margin based counterparts. Besides, we propose a novel feature prototype representation which is adaptively updated during training to further enhance the disambiguation ability. Extensive empirical studies show that PML-ODM can effectively identify the ground-truth labels, and achieve excellent generalization performance. Our method belongs to the second group mentioned above, but enjoys three advantages compared with previous works:

• It is the first attempt to introduce the powerful margin distribution into partial multi-label learning, and achieves significantly better generalization performance.
• It proposes a novel method to adaptively update the fea-

ture prototype during training, rather than heuristically fixing it as constant ahead of time.

• It incorporates non-linear kernels to further enhance the generalization performance for linearly inseparable data.

The rest of paper is organized as follows. We first briefly introduce some preliminaries, and then detail the proposed method. After that, we derive the optimization procedure, followed by the empirical studies. Finally we conclude the paper with future work.

2 Preliminaries

For convenience, we first introduce some notations and terminologies used throughout the paper. We denote scalars with lower case letters (e.g., y), and vectors / matrix with boldface letters (e.g., x / X). Sets are designated by upper case letters (e.g., Y ), and in particular [n] ≜ {1, 2, . . . , n}.

Let X, Y,H denote the instance, label, hypothesis space respectively, and D = {(x1, ˆ Y1), (x2, ˆ Y2), . . . , (xm, ˆ Ym)} is a training set of size m drawn identically and independently (i.i.d.) according to some unknown distribution over X × Y . The feature mapping associated with some positive definite kernel κ(·, ·) is denoted by φ : X ↦→ H. The hypothesis h ∈ H is parameterized with n weight vectors w1, w2, . . . , wn ∈ H, each of which induces a scoring function x ↦→ w⊤ k φ(x) for k ∈ [n].

2.1 Optimal Margin Distribution Learning

Margin is one of the most essential concepts in machine learning. Roughly speaking, it indicates the confidence of learning results. The larger the margin, the more confidence we have on the learner, and a negative margin signifies a wrong prediction. Formally, it is a function mapping fromX ×Y ×H to R. Let ¯ Y = Y \ ˆ Y denotes the irrelevant label set. For single-label learning problems where ˆ Y = {y} is a singleton, it is defined as

that is the smallest difference of scores between the groundtruth label and irrelevant labels. Particularly for binary classification problem where Y = {1, 2}, Eqn. (1) reduces to a more common form γ(x, {y}, h) = ˆ yw⊤φ(x) where ˆ y = -2y + 3 ∈ {±1} and w = w1 - w2. For multi-label learning problem where | ˆ Y | ≥ 2, the following ranking margin is commonly considered,

that is the difference of scores between each relevant and irrelevant label pair.

Recent studies on margin theory [Gao and Zhou, 2013] demonstrate an upper bound characterizing the relationship between the generalization and margin distribution, and the subsequent study on lower bound [Grønlund et al., 2019] further proves that the upper bound is almost optimal up to a logarithmic factor, which means margin distribution is actually the essence of generalization. Inspired by these insightful works, a novel statistical learning framework named Optimal margin Distribution Machine (ODM) has appeared. Formally, it explicitly optimizes the distribution of margin by maximizing mean and minimizing variance simultaneously, that is

where Ω(h) is a regularization term to control model complexity, ¯ γ is the mean of margin, and α, λ are trading-off hyper-parameters. Note that the slack variables ξi and ϵi are deviations frommargin mean, thus the summation in the last term is exactly the margin variance.

Due to the excellent generalization performance shown on both binary and multi-class classification tasks [Zhang and Zhou, 2014; Zhang and Zhou, 2017], many works extend ODM to some general learning settings. For example in [Tan et al., 2020], a multi-label version of ODM is proposed. In addition to the cardinality, i.e., | ˆ Y |, the accuracy of supervision is also commonly considered, and for most inaccurate supervised learning settings, ODM has already owned corresponding adaptions, just to name a few, clustering in which no supervision is provided [Zhang and Zhou, 2018a], semi-supervised learning in which only a fraction of instances have labels [Zhang and Zhou, 2018b], and multi-instance learning in which one label is just associated with a collection of instances [Zhang and Jin, 2020; Luan et al., 2020]. Partial label learning [Xu et al., 2019] is also a kind of inaccurate supervised learning, in which supervision is redundant with irrelevant labels. By further mixing up with the cardinality leads to the partial multi-label learning, which is much more difficult since the number of groundtruth labels is also unknown.

3 ProposedMethod

In this section, we detail the PML-ODM. Following the same strategy in [Wang et al., 2019], we incorporate a confidence matrix to distinguish the ground-truth labels. To be specific, let pik ∈ [0, 1] denote the confidence that label k is a groundtruth label of xi, and P ∈ Rm×n denote the confidence matrix with pik as the (i, k)-th entry. Obviously, if k is an irrelevant label of xi, i.e., k ∈ ¯ Yi, we have pik = 0.

Different from multi-label learning in which ranking margin is only calculated for each relevant and irrelevant label pair, here we have two kinds of label pairs: 1) (k, l) ∈ ˆ Y × ¯ Y , i.e., one is a candidate label and the other is irrelevant; 2) (k, l) ∈ ˆ Y × ˆ Y , i.e., both are candidate labels. By putting the two kinds of label pairs together, and substituting the ranking margin into the formulation of ODM, we obtain:

where Zi = ˆ Yi × Y is the label pair set associated with xi, ˜ pikl = max(0, pik - pil) is the difference of confidence between label k and l, and the larger this value, the more important this label pair. From this perspective, ˜ pikl is actually an attention which can filter out unimportant label pairs.

If the confidence matrix P is given by users in advance or can be summarized from domain knowledge, Eqn. (3) turns to a convex optimization problem and can be solved similarly as ODM. However in general P is unavailable, thus we treat it as a variable and learn it jointly with the multi-label classifier. Following the formulation in [Xie and Huang, 2018], let qk denotes the feature prototype for the k-th class, we can obtain the following optimization problem:

where the constraint ∑k∈ˆ Yi pik ≥ 1 is to avoid the trivial solution P = 0. In [Xie and Huang, 2018], the feature prototype qk is simply set as the average of all instances with label k and kept unchanged in the subsequent training, which will undoubtedly hurt the generalization performance since the initialization involves noisy labels. Instead in this paper, we iteratively refine it. Specificly, given the current multi-label classifier, we can obtain the latest prediction yi = [yi1, yi2, . . . , yin] ∈ {0, 1}n for xi, and according to which we collect all instances with label k and calculate the feature prototype as a weighted sum of them:

where Vk = {i ∈ [m] | yik = 1} is the index set of instances with label k, and the weight coefficient cik is determined by

where Ni is the index set of xi's nearest neighbors, dt denotes the distance between xi and the neighbor xt, dmax = maxk∈Ni {dk} and dmin = mink∈Ni {dk}. The intuition behind Eqn. (6) is that the closer the instances, the more likely they share similar labels, which can also be regarded as the smooth constraint being able to avoid over-fitting.

By combining with Eqns. (3)-(4), we obtain the final formulation of PML-ODM:

Here we follow the same processing as ODM, i.e., scaling w to make the mean ¯ γ as 1, introducing hyper-parameters µ and θ to enhance the model's capability and flexibility, and using the ℓ2 regularization to control the model complexity.

Once we obtain the solution of Eqn. (7), i.e., w1, . . . ,wn, we can calculate the scores for any unseen data, but to predict whether a label is relevant or irrelevant, an extra threshold is required. Here we determine the threshold tk for any label k by minimizing the overall misclassification rate. To be specific, for any training instance (xi, ˆ Yi), if k ∈ ˆ Yi yet w⊤ k φ(xi) < tk, or k ∈ ¯ Yi yet w⊤ k φ(xi) > tk, a misclassification occurs. We determine tk by minimizing overall misclassification rate, which can be solved by sorting {w⊤ k φ(xi)}i∈[m]. Without loss of generality, let us assume w⊤ k φ(x1) ≤ w⊤ k φ(x2) ≤ · · · ≤ w⊤ k φ(xm), then tk can be determined by checking the middle value of m - 1 intervals [w⊤ k φ(xi), w⊤ k φ(xi+1)]i∈[m-1].

4 Optimization

Due to the coupling of P, ξ, ϵ in the second term, Eqn. (7) is difficult to optimize directly, thus we resort to the alternating optimization strategy, i.e., in each iteration, we first solve w, ξ, ϵ by fixing P, then update q as described previously, and finally solve P with the latest ξ, ϵ, q. As for initialization, we can first calculate cik as Eqn. (6) and appropriately scale it as pik; on the other hand qk can be initialized by Eqn. (5). The above steps are performed iteratively until convergence or the maximum number of iterations is reached. Algorithm 1 summarizes the whole procedure.

4.1 Subproblem

When fixing P, Eqn. (7) turns to a quadratic programming problem. Due to the underlying infinite dimensional feature mapping φ(·), it is usually cast in the dual form. By introducing the dual variables αikl and βikl, the Lagrangian function

Algorithm 1 PML-ODM

• 1: Input: data set D = {(xi, ˆ Yi)}i∈[m], hyper-parameters µ, θ, λ1, λ2, nearest neighbors number |N|, maximum iteration number T .
• 2: Initialize: confidencematrixP, feature prototype q, t ← 0.
• 3: while t < T and not converge do
• 4: Optimize w, ξ and ϵ by fixing P;
• 5: Obtain the indicator vector yi according to w;
• 6: Calculate weight coefficient ci as Eqn. (6);
• 7: Update qk as Eqn. (5);
• 8: Optimize P by fixing w, ξ and ϵ;
• 9: end while
• 10: Output: ws for s ∈ [n].

can be written as:

The partial derivatives of L w.r.t. ws, ξikl, ϵikl are

where d(s) ikl = 1k=s-1l=s. By setting these partial derivatives to zero, we have

i = [d(s) ikl ](k,l)∈Zi , By substituting into the Lagrangian function, we can obtain the dual problem:

where ei ∈ R|Zi| is the all one vector, and ˜P ∈ R|Zi|×|Zi| is the diagonal matrix with 1/˜ pikl as the diagonal element.

The dual problem is a convex quadratic programming. Notice that all the variables are decoupled and only have a lower bound constraint, therefore it can be efficiently solved by the coordinate descent method [Hsieh et al., 2008]. To be specific, in each iteration, only one variable is selected to minimize while other variables are kept as constants, and a closedform solution can be achieved, finally this procedure is repeated until convergence.

When fixing w, ξ and ϵ, Eqn. (7) turns to a linear programming problem, whose solution has already matured attribute to the intensive studies for decades. Thus we simply invoke the off-the-shelf solver Mosek, which integrates the effective interior point method.

5 Experiments

In this section, we empirically evaluate the effectiveness of our proposed method.

5.1 Setting

We conduct the experiments on eight real-world multi-label data sets 1 which come from a broad range of field. Since partial multi-label learning is a recently proposed learning framework, the customized public data sets are not available yet, thus for each data set, we randomly add η ∈ {1, 2, 3} noisy labels to candidate label set and repeat five times to performe the experiments. The average values as well as the standard deviations are recorded. All the data sets with their basic statistics are listed in Table 1.

To demonstrate the superiority of the proposed PMLODM, we compare it with two confidence learning models PAR-VLS and PAR-MAP [Zhang and Fang, 2020], and one low-rank model PML-LRS [Sun et al., 2019]. We also compare PML-ODM with the mlODM [Tan et al., 2020], the state-of-the-art multi-label learning method which also optimizes the margin distribution.

The parameters of PAR-VAL and PAR-MAP are set as suggested in its paper, i.e., balancing parameter α = 0.95 and credible label elicitation threshold t = 0.9. For our method k = 10 and the width of RBF kernel is selected from the set {2-10 , 2-9 , . . . , 23 }. For the ODM based method, the parameters µ and θ are selected from the set {0.1, 0.2, . . . , 0.9}. All the parameters are selected by 5-fold cross validation.

We take the Ranking Loss , Hamming Loss , Coverage , Average Precision , Macro-F1 and Micro-F1 as the performance evaluation metrics.

5.2 Results

Table 2 summarizes the performance of five methods on eight data sets in terms of six evaluation metrics. From the results we can see that our proposed PML-ODM outperforms most of the baselines and achieves best performance in most cases. Among the five methods, PML-ODM beats other methods on three data sets Emotions, Scene, Genbase in terms of nearly all the evaluation metrics, and on two data sets Medical and Flags in terms of Average Precision, Macro-F1 and Micro-F1. Compared to mlODM, PML-ODM is much more robust in resisting the noisy labels, and achieves better performance in most of the experiments.

1 http://palm.seu.edu.cn/zhangml/ and http://mulan.sourceforge. net/datasets-mlc.html

To verify the superiority of our proposed feature prototype, we compare PML-ODM with its variant PML-ODMf , which fixs the feature prototype as the average of all the instances. Experiments are performed on data sets Emotions, Scene, Flags, each of which contains 1 noisy label, and we take the Average Precision (AP) and One Error (OE) as evaluation metrics. As shown in Table 3, we can find that PML-ODM achieves higher Average Precision (AP) and lower One Error (OE) than PML-ODMf , which validates the superiority of our proposed feature prototype.

To analyze their relative performance, we also conduct the Friedman test. Table 4 shows the Friedman statistical results as well as the corresponding critical value with respect to six evaluation criteria, from the results we can find that all the Friedman statistical values are greater than the critical value which indicates that the performance of PML-ODM is remarkably different from other methods. For each criterion, the null hypothesis of distinguishable performance within the four baselines is rejected at 0.05 significance level.

Furthermore, the post-hoc Bonferroni-Dunn test is utilized to analyze the relative performance of our PML-ODM with other baselines. The control method is our PML-ODM, and the difference of average ranking between control method and other methods will be calibrated with the Critical Difference (CD). The PML-ODM is believed to have prominently different performance to another baselines if the average ranking gap is larger than one CD. Figure 1 displays the results of Bonferroni-Dunn test on six evaluation metrics. For each baselines, the average ranking in terms of each evaluation metric is marked on the axis, and for the methods whose distance to the control method are less than one CD, we use the thick line to connect them with PML-ODM. Obviously, PML-ODM significantly outperforms most of the baselines.

6 Conclusion

In this paper, we propose the Partial Multi-Label Optimal margin Distribution Machine (PML-ODM). To sum up, our contributions are threefold: 1) we first introduce the powerful margin distribution into partial multi-label learning; 2) we propose an ingenious method to adaptively refine the feature prototype during the training process rather than fixing it as constant; 3) we leverage non-linear kernels to further improve the generalization performance for linearly inseparable data. In the future, we will make some theoretical analysis on our proposed method.

Acknowledgments

This work was supported by NSFC (62006088).