Partial Label Learning by Semantic Difference Maximization

1 Introduction

Partial label (PL) learning [Jin and Ghahramani, 2003; Cour et al., 2011] belongs to the family of weakly supervised learning frameworks. It aims to deal with the problem that each instance is provided with a set of candidate labels, only one of which is the ground-truth label. Partial label learning is also termed as ambiguous label learning [H¨ullermeier and Beringer, 2006; Zeng et al., 2013; Chen et al., 2014; Chen et al., 2018] and superset label learning [Liu and Dietterich, 2012; Liu and Dietterich, 2014; Gong et al., 2018]. As a result of the difficulty in collecting perfect data with completely correct labels in many real-world scenarios, partial label learning has been applied to various domains. Examples include automatic face naming [Zeng et al., 2013], object detection [Liu and Dietterich, 2012], and web mining [Luo and Orabona, 2010].

Formally speaking, let X = Rn be the n-dimensional feature space and Y = {1, 2, · · · , l} be the label space including l labels. Suppose the PL dataset is denoted by D = {(xi, Si)}mi=1 where xi ∈ X is an n-dimensional feature vector and Si ⊆ Y is the corresponding candidate label set where the ground-truth label yi must be in this candidate label set, i.e., yi ∈ Si. Given such data, the goal of partial label learning is to train a multi-class classification model f : X → Y that tries to correctly predict the label of a test instance.

Due to the semantic ambiguities conveyed by the label space, the key of partial label learning is to disambiguate the candidate label set, thereby targeting the ground-truth label. To achieve this, most of the existing disambiguation-based approaches normally follow two typical strategies, including the average-based strategy [H¨ullermeier and Beringer, 2006; Cour et al., 2011] and identification-based strategy [Jin and Ghahramani, 2003; Liu and Dietterich, 2012; Zhang and Yu, 2015; Zhang et al., 2016; Tang and Zhang, 2017; Gong et al., 2018]. The average-based strategy treats each candidate label equally, and makes the final prediction by averaging the modeling outputs of candidate labels. The identification-based strategy aims to handle the candidate labels with discrimination, and usually employ an iterative process to gradually update the confidence of each candidate label.

By taking into account the different confidences of candidate labels, the identification-based strategy generally outperforms the average-based strategy, thereby having attracted increasing attention. Most approaches [Zhang and Yu, 2015; Zhang et al., 2016; Feng and An, 2018; Gong et al., 2018] following this strategy normally leverage the topological information in feature space to derive the confidence of each candidate label. Specifically, the conjecture that nearby (similar) instances are supposed to have the same label is widely used by these approaches. However, it is still unclear whether we can directly extract useful information in label space to help with the derivation of the confidences of candidate labels. This paper gives a positive answer to this question for the first time. There is a key observation that if two instances do not share any common candidate labels, they cannot have the same ground-truth label. For example, suppose there are two instances x1 and x2 whose corresponding label vectors are given as y1 = [1, 1, 0, 0] and y2 = [0, 0, 1, 1]. Without knowing the ground-truth label of the each instance, we can still easily find that x1 and x2 cannot have the same groundtruth label, since they do not share any common candidate labels.

By exploiting such dissimilarity relationships from label space, we propose a novel partial label learning approach called SDIM (Semantic DIfference Maximization), which aims to maximize the latent semantic differences of the two instances whose ground-truth labels are definitely different, while training the desired model simultaneously, thereby continually enlarging the gap of label confidences between two instances of different classes. The effectiveness of SIDM is clearly demonstrated by extensive experiments on 4 artificial and 6 real-world PL datasets.

2 RelatedWork

The key of effective partial label learning is to disambiguate the candidate labels. Existing disambiguation-based approaches mainly follow two strategies: the average-based strategy and the identification-based strategy.

The average-based strategy assumes that each candidate label contributes equally to model training, and the final prediction is made by averaging the modeling outputs of all the candidate labels. Following this strategy, instance-based approaches [H¨ullermeier and Beringer, 2006; Gong et al., 2018] predict the label of a test instance x by averaging the outputs of its nearest neighbors, i.e., argmaxy∈Y ∑xi∈N(x) I(y ∈ Si) where N(x) is the set of neighbors of x. In addition, parametric approaches aim to train a parametric model [Cour et al., 2011; Zhang et al., 2016] that is able to differentiate the average modeling output of candidate labels (F (xi, y; θ), y ∈ Si) from that of non-candidate labels (F(xi, ˆ y; θ), ˆ y ∈ ˆ Si), where ˆ Si is the set of non-candidate labels and ˆ y ∈ Si is a non-candidate label. Obviously, the average-based strategy is simple and clear, while it may suffer from the problem that without discrimination of candidate labels, the ground-truth label could be overwhelmed by the other false positive labels.

To address the drawback of the average-based strategy, the identification-based strategy tries to handle the candidate labels with discrimination, and derive different confidences of candidate labels. Following this strategy, conventional approaches aim to optimize the objective function according to the maximum likelihood criterion [Jin and Ghahramani, 2003] or the maximum margin criterion [Nguyen and Caruana, 2008]. Recently, there have been increasing interests [Zhang and Yu, 2015; Zhang et al., 2016; Feng and An, 2018; Gong et al., 2018] in leveraging the topological information in feature space to derive the confidence of each candidate label. These approaches normally iteratively update the confidences of candidate labels based on the widely used assumption that nearby (similar) instances are supposed to have the same label. One potential drawback of the identificationbased strategy lies in that if the differentiated label is a false positive label, it would have a dramatically malignant influence on the follow-up model training. In addition, because of the redundant and noisy features naturally exist in feature space, the extracted topological information may be misleading. Hence there is an important question, i.e., whether we can extract useful information from label space to help with the iterative process of updating the confidences of candidate labels?

In this paper, a novel partial label learning approach called SDIM will be introduced, which provides a positive answer to the above question.

3 Preliminaries

Following the conventional notations used in Introduction, we denote the feature matrix and the label matrix given in the PL dataset by X = [x1, x2, · · · , xm]⊤ ∈ Rm×n and Y = [y1, y2, · · · , ym]⊤ ∈ {0, 1}m×l , respectively. Here, yij = 1 means that the j-th label is in the candidate label set of the instance xi (i.e., j ∈ Si), otherwise the j-th label is a noncandidate label of xi. In addition, we introduce the partial label confidence matrix P = [p1, p2, · · · , pm] ∈ [0, 1]m×l where pi represents the label confidence vector of xi.

Note that many approaches [Zhang and Yu, 2015; Zhang et al., 2016; Feng and An, 2018; Gong et al., 2018; Feng and An, 2019] have introduced or defined such partial label confidence matrix P. As the partial label confidence matrix P is not directly accessible from PL training examples, in this paper, we carefully illustrate some requirements for P. Intuitively, since each candidate label has the potential to be the ground-truth label, the confidence of each candidate label should be in [0, 1]. While the confidence of each noncandidate label should be strictly 0, as non-candidate labels can never be the ground-truth label. We can use the constraint 0 ≤ P ≤ Y to compactly represent such logic. Moreover, since there is only one ground-truth label for each instance, competitive relationships naturally exist in the candidate label set. Therefore, we also assume that each label confidence vector pi should be normalized, i.e., ∑j pij = 1. Such constraint implicitly shows that once the confidence of certain candidate label is enlarged, the confidences of other labels would be decreased. Based on the above descriptions of P, we present the formal definition of partial label confidence matrix as follows.

Definition 1 (Partial Label Confidence Matrix). Given the label matrix Y in the partial label dataset, we define the partial label confidence matrix P as:

• candidacy: 0 ≤ pi ≤ yi, ∀i ∈ [m]
• normalization: ∑j pij = 1, ∀i ∈ [m]

where [m] := {1, 2, · · · ,m}. By compact representation, we also define a partial label simplex as ∆ := {P ∈ [0, 1]m×l : P ≤ Y, P1l = 1m} where 1m is a vector of size m with all of its elements equal to 1, thus P ∈ ∆.

4 Approach

As stated before, SDIM aims to maximize the latent semantic differences of the two instances whose ground-truth labels are definitely different while model training. Formally, suppose xi and xj have different ground-truth labels, i.e., y⊤ i yj = 0, the gap between the label confidence vectors pi and pj should be maximized. In this paper, we adopt the widely-used Euclidean distance. Therefore, our goal is to maximize ‖pi -pj‖22 , if y⊤ i yj = 0. Here, we dig more about why our proposed regularization approach can work. Suppose yi = [1, 1, 0, 0] and yj = [0, 0, 1, 1], we have pi = [pi1, pi2, 0, 0] and pj = [0, 0, pj3, pj4] (according to Definition 1). If pi1, pi2 = 0.5, and pj3, pj4 = 0.5, we could get ‖pi -pj‖22 = 1. While if pi1 = 1, pi2 = 0 and pj3 = 1, pj4 = 0 (the values could be exchanged), we would obtain ‖pi - pj‖22 = 2. In this way, it would be clearly observed that ‖pi -pj‖22 hits the lowest value when the confidence of each candidate label is equal to 0.5. While ‖pi - pj‖22 gradually increases when the confidence of each candidate label approaches to 0 or 1. As a result, such regularization approach would enhance the discrimination abilities to disambiguate the candidate labels, and the obtained confidence vectors pi and pj would be more confident, thereby reducing the label ambiguities.

For better representation, we introduce an indicating matrix R = [rij]m×m, indicating whether two instances definitely have different ground-truth labels:

In this way, we present our proposed regularization approach as follows:

where L = diag(R1) - R is the Laplacian matrix, and tr(·) is the trace operator. Note that our proposed regularization approach aims to maximize the convex objective, which is diametrically opposed to the common convex manifold regularization [Belkin et al., 2006] that minimizes the convex objective. In other words, problem (2) is not a convex problem.

By integrating the proposed regularization term into the widely-used model, we obtain the final optimization problem:

whereW∈ Rn×l is the model parameter. Note that in problem (3), we aim to learn from the partial label confidence matrix P while updating P simultaneously. Such two tasks would be mutually promoted. Due to the difficulty in optimizing the two variables W and P together, we adopt the simple alternating optimization method, which enables us to iteratively optimize one variable with the other fixed.

4.1 Model Training

With P fixed, problem (3) with respect to W reduces to:

which is the common linear regression model. Simple closedform solution could be easily obtained:

where In×n is an identity matrix whose scale is n×n. However, such linear model may not be able to deal with the complex nonlinear case. To solve this problem, we adopt a kernel extension to train a kernel ridge regression model. Specifically, we resort to a feature mapping φ(·) : Rn → RH, which maps the original feature space (X) to some higher dimensional Hilbert space (φ(X)). By representor theorem [Sch¨olkopf et al., 2002], the model parameter W can be represented by a linear combination of the input features φ(X), i.e., W = φ(X)⊤A where A = [aij]m×l is the matrix storing the weights. Hence φ(X)W = KA where K = φ(X)φ(X)⊤ ∈ Rm×m is the kernel matrix with each element kij = φ(xi)⊤φ(xj) = κ(xi, xj), and κ(·, ·) denotes the kernel function. By incorporating such kernel extension, problem (4) can be stated as:

where we have used the property of the trace operator, i.e., ‖W‖2F = tr(W⊤W) = tr(A⊤KA). Setting the gradient w.r.t. A to 0, the closed-form solution is reported as:

In this paper, we adopt the popular Gaussian kernel function κ(xi, xj) = exp((xi - xj)/2σ2 ) with σ set to the averaged pairwise Euclidean distances of instances.

4.2 Confidence Updating

With A fixed, we denote by the modeling output Q = φ(X)W = KA, thus problem (3) w.r.t. P reduces to:

Note that in problem (8), the first term is convex, while the last term is concave. Therefore, problem (8) is a constrained convex-concave problem [Yuille and Rangarajan, 2003; Sriperumbudur and Lanckriet, 2009]. Fortunately, since the constraints are linear, we can directly employ the ConvexConCave Procedure (CCCP) [Yuille and Rangarajan, 2003] to update P. CCCP can be regarded as a majorizationminimization algorithm [Sriperumbudur et al., 2011; Gong et al., 2018] that optimizes the original nonconvex problem by solving a sequence of convex problems. Specifically, problem (8) can be regarded as the difference between two convex functions C1 = 12 ‖P-Q‖2F and C2 = β2 tr(P⊤LP). In each iteration, C2 is replaced by its first order Taylor approximation ˜ C2, and problem (8) can be approximated by C1 - ˜ C2, which becomes a convex problem. Theoretical analyses show that CCCP converges to a local minima [Sriperumbudur and Lanckriet, 2009].

For our problem, we denote by P(i) the updated value of P at the i-th iteration, and linearize C2 at P(i) by its Taylor approximation:

Algorithm 1 The SDIM Algorithm

Inputs:

• D: the PL training set {(X,Y)}
• λ, β: the regularization parameters
• x: the unseen test instance

Output:

y: the predicted label for the test instance x

• 1: construct the indicating matrix R= [rij]m×m by (1);
• 2: construct the kernel matrix K = [κ(xi, xj)]m×m using Gaussian kernel function;
• 3: initialize P by (13);
• 4: repeat
• 5: update A= [aij]m×l by (7);
• 6: update Q=KA;
• 7: updatePby solving (12) with a general QP procedure;
• 8: until convergence or the maximum number of iterations.
• 9: return the predicted label y according to (14).

Since the variable is P, the last term in (9) can be removed, and the approximated objective function for updating P is:

Here, we will show that problem (10) is actually a standard Quadratic Programming (QP) problem. Let us vectorize P ∈ Rm×l , Q ∈ Rm×l , and Y ∈ Rm×l to ˆp ∈ Rml , ˆq ∈ Rml , and ˆy ∈ Rml . To copy with the equality constraint using ˆp, we specially pick up the indices of ˆp by defining a set Z = {Z0,Z1, · · · ,Zm-1} as follows:

Thus problem (10) can be equivalent to:

where H = Iml×ml, f = -ˆq-βGˆp(i) , and G = Im×m⊗L where ⊗ is the Kronecker product. In this way, any off-theshelf QP toolbox can be used to solve problem (12). By iteratively solving a sequence of QP problems, we can eventually get local optimal ˆp. Finally, by reshaping ˆp ∈ Rml to P ∈ Rm×l , we can obtain the eventually updated partial label confidence matrix P.

Since the variables A and P are alternatively updated, we can simply always update P for one step (for one QP problem) after updating A. Thus the iterative process of updating P is kept, while the optimization efficiency is improved.

For the 0-th iteration, P(0) = [p(0) ij ]m×l is initialized as:

After the completion of the whole optimization process, SDIM gives the predicted label y of the test instance x by:

The pseudo code of SDIM is presented in Algorithm 1.

5 Experiments

In this section, we conduct extensive experiments on artficial and real-world datasets to demonstrate the effectiveness of our proposed approach.

5.1 Comparing Algorithms

We compare our approach with six state-of-the-art partial label learning approaches, each configured with suggested hyperparameters in accordance with the respective literature:

• PLKNN [H¨ullermeier and Beringer, 2006]: a kNN approach following the average-based strategy [default configuration: k ∈ {5, 6, · · · , 10}];
• CLPL [Cour et al., 2011]: a convex approach following the average-based strategy [default configuration: SVM with squared hinge loss];
• IPAL [Zhang and Yu, 2015]: an approach following the identification-based strategy that leverages the structural information in feature space [default configuration: α ∈ {0, 0.1, · · · , 1}, k ∈ {5, 6, · · · , 10}];
• PL-SVM [Nguyen and Caruana, 2008]: a maximum margin approach following the identification-based strategy [default configuration: λ ∈ {10-3 , · · · , 103 }];
• PLALOC [Wu and Zhang, 2018]: a disambiguation-free approach that adapts the binary decomposition [default configuration: µ = 10]
• ECOC [Zhang et al., 2017]: a disambiguation-free approach based on the coding-decoding procedure [default configuration: L = log2(l)]

For our approach, λ is searched in {0.001, 0.005, · · · , 0.5} and β is searched in {0.00001, 0.00005, 0.0001, · · · , 0.1}. For all the approaches, parameters are selected by five-fold cross-validation on the training set. For each dataset, we perform ten-fold cross-validation, and report the resulting mean prediction accuracies and the standard deviations.

5.2 Experiments on Controlled UCI Datasets

Table 1 reports the characteristics of four UCI datasets used in our experiments. Following the widely-used controlling protocol [Zhang and Yu, 2015; Zhang et al., 2016;

Tang and Zhang, 2017; Feng and An, 2018; Wu and Zhang, 2018], we generate the artificial partial label datasets by using two contorlling parameters p and r. Here, p controls the proportion of instances that have candidate labels, and r controls the number of false positive labels, in other words, |Si| = r+1. All the candidate labels are randomly generated.

Figure 1, Figure 2, and Figure 3 report the classification accuracy of each approach as p ranges from 0.1 to 0.7 with step size 0.1, when r = 1, r = 2, and r = 3, respectively. As shown in these figures, SDIM outperforms other comparing algorithms in most cases. It is worth noting that candidate labels are randomly generated, there might be the case that many pairs of examples share at least one common candidate labels. In this case, Our proposed method may achieve mediocre performance. However, such case is really rare since experimental results demonstrate that our method can achieve the best performance in more than 75 cases out of the 84 cases.

5.3 Experiments on Real-World Datasets

Table 2 summaries the characteristics of the real-world partial label datasets from various task domains, which also includes the average number of candidate labels per instance (Avg. CLs). Note that the BirdSong dataset is normalized using the Z-scores by convention. The mean accuracy with standard deviation of each approach on each real-world dataset is reported in Table 3. It is worthy noting that all the approaches achieve extremely poor performance on the FGNET dataset, because its Avg. CLs is very large. For better evaluation of such task, we resort to conventional mean absolute error (MAE). Specifically, for FG-NET (MAE3/MAE5), a test example is considered correctly classified if the MAE between the predicted age and the real age is no more than 3/5 years. The experimental results of FG-NET(MAE3) and FG-NET(MAE5) are also recorded in Table 3. From Table 3, we can observe that: 1) SDIM statistically outperforms PLKNN on all the real-world datasets; 2) Out of the 48 cases (6 comparing algorithms and 8 tasks), SDIM statistically outperforms other algorithms in 85.4% cases; 3) It is worthy noting that SDIM is never statistically inferior to any comparing algorithms.

Further Analysis

There are two tradeoff parameters for SDIM. We conduct sensitivity analysis by varying one parameter, while keeping the other fixed at the best setting. Figure 4(a) and 4(b) show the performance of SDIM w.r.t. λ and β, respectively. As can be seen from Figure 4(a), when performance of SDIM is relatively poor when λ is too small or too big. Such observation agrees with the intuition that it is important to control the model complexity for avoiding overfitting or underfitting. Note that β controls our proposed regularization term, i.e., the importance of semantic difference maximization. From Figure 4(b), we can also find that when β is very small, the importance of semantic difference maximization is hardly considered, thus SDIM achieves relatively low prediction accuracy. As β increases, the importance of semantic difference maximization will gradually be taken into consideration, hence the prediction accuracy starts to increase. Such observation clearly confirms the effectiveness of our SDIM approach. However, if β is overly large, the classification accuracy will drop. This is because the objective function focuses too much on maximizing the semantic differences while ignoring the importance of model training. It is also worth noting that when β is extremely small (even without the proposed regularization term), SDIM still achieves satisfied performance. Which means, the reduced version of SDIM (i.e., kernel regression with confidence updating) provides a strong baseline. This observation also agrees with [Feng and An, 2018; Feng and An, 2019].

Figure 4(c) and Figure 4(d) illustrate the convergence of SDIM on Lost and MSRCv2, according to the difference of the value of the objective function (3) between two successive iterations. It can be easily observed that the loss converges within a few iterations. Hence the convergence of SDIM is demonstrated.

6 Conclusion

This paper gives the first attempt to leverage the dissimilarity relationships from label space for dealing with label ambiguities. A novel partial label learning approach called SDIM is proposed to maximize the latent semantic differences while training the desired model simultaneously. Extensive experimental results demonstrate the effectiveness of SDIM.

Contrary to conventional approaches that leverage the similarities in feature space to disambiguate the candidate labels, SDIM resorts to the dissimilarities in label space. Hence a question naturally arises on how similarities and dissimilarities can be combined together for enhancing partial label learning performance. We leave this as future work.

Acknowledgements

This work was supported by MOE, NRF, and NTU.