Leveraging Latent Label Distributions for Partial Label Learning

1 Introduction

Partial label (PL) learning is a specific type of weakly supervised learning [Cour et al., 2011], in which each instance is associated with a set of candidate labels. However, only one of the candidate labels is the ground-truth label, which is concealed in the training process. This learning problem is also termed as ambiguous label learning [H¨ullermeier and Beringer, 2006; Zeng et al., 2013; Chen et al., 2014; Chen et al., 2017] or superset label learning [Liu and Dietterich, 2012; Liu and Dietterich, 2014; H¨ullermeier and Cheng, 2015; Gong et al., 2017]. Since precisely labeled data are too expensive to be collected in reality, partial label learning has various application domains, such as ecoinformatics [Liu and Dietterich, 2012], image annotation [Cour et al., 2009; Zeng et al., 2013] and web mining [Luo and Orabona, 2010], etc.

Formally speaking, suppose we have m training examples X = [x1, x2, · · · , xm]⊤ ∈ Rm×n with n dimensions, and their candidate label sets are denoted by {S1, S2, · · · , Sm}, respectively. The ground-truth labels of these m examples are {y1, y2, · · · , ym} with yi ∈ Si (i ∈ [m]), while they are not directly accessible in the model training. Given the label space denoted by Y = {1, 2, · · · , l}, the task of partial label learning is to learn a function: f : X → Y from the imprecisely labeled training set D = {(xi, Si)|i ∈ [m]} to accurately predict the label of the test example.

To learn with such PL examples, the key is how to properly deal with the candidate labels. To this end, there are mainly two learning frameworks, including the averagebased framework and the identification-based framework. For the average-based framework, each candidate label is treated equally in the model training [Cour et al., 2011; Zhang et al., 2016]. For the identification-based framework, the ground-truth label is considered as a latent variable hidden in the indiscriminate candidate label set [Jin andGhahramani, 2003; Liu and Dietterich, 2012; Chen et al., 2014; Nguyen and Caruana, 2008; Yu and Zhang, 2016]. They all make predictions by aggregating the modeling outputs of the candidate labels without discrimination, while the confidence of each candidate label being the ground-truth label is regrettably ignored. As a consequence, these approaches may be suboptimal, since each candidate label normally makes different contributions to the model training.

To address this problem, we formalize the different labeling confidence levels of the candidate labels as the latent label distributions, and propose the LALO (partial label learning with LAtent Label distributiOns) approach. LALO first introduces a novel unified framework that estimates the latent label distributions while training the model simultaneously, and then presents a biconvex formulation with constrained local consistency, finally adopts an alternating method to solve this optimization problem. On the one hand, the inductive model is discriminatively trained by minimizing the least squares loss of fitting the latent label distributions. On the other hand, the latent label distributions are regularized by the modeling outputs via a constrained label propagation procedure specifically for the PL properties. Through the mutual promotion of the model training and the label propagation, the groundtruth label can be identified by optimally estimating the label distributions. The effectiveness of LALO is validated by experiments on 4 controlled UCI datasets and 5 real-world datasets.

The rest of this paper is organized as follows. Section 2

briefly reviews related work. Section 3 introduces the LALO approach. Section 4 presents the technical details of the alternating optimization method. Section 5 reports the experimental results of comparative studies. In the end, Section 6 concludes this paper and discusses future research issues.

2 RelatedWork

Due to the difficulty in dealing with ambiguous labeling information of PL examples, there are only two common partial label learning frameworks, including the average-based framework and the identification-based framework.

The average-based framework normally treats each candidate label equally in the model training, and averages the modeling outputs of all the candidate labels for predictions. Following this framework, some instance-based approaches [H¨ullermeier and Beringer, 2006; Zhang and Yu, 2015] predict a test instance by averaging the candidate labeling information of its neighbors. In addition, some parametric approaches assume a parametric model F(xi, y; θ) [Cour et al., 2011; Zhang et al., 2016] that discriminates the average modeling output of the candidate labels from that of the noncandidate labels, i.e., max(∑mi=1 ( 1 |Si | ∑y∈Si F(xi, y; θ) -

1 | ˆ Si | ∑y∈ ˆ Si F(xi, y; θ))) where Si and ˆ Si denote the candidate and non-candidate label set respectively. Although this framework is intuitive, the obvious drawback is that the ground-truth label may be overwhelmed by other candidate (false positive) labels without discrimination.

Instead of maximizing the average modeling output of all the candidate labels, the identification-based framework aims at directly maximizing the modeling output of exactly one candidate label, which is distinguished as the ground-truth label. Existing approaches following this framework consider the ground-truth label as a latent variable determined by yi = argmaxy∈Si F(xi, y; θ). Generally, the objective function is optimized according to the maximum likelihood criterion: max(∑mi=1 log(∑y∈Si 1 |Si| F(xi, y, θ))) [Jin and Ghahramani, 2003; Liu and Dietterich, 2012] or the maximum margin criterion: max(∑mi=1 (maxy∈Si 1 |Si| F(xi, y; θ) -

maxy∈ ˆ Si 1 | ˆ Si| F(xi, y; θ))) [Nguyen and Caruana, 2008; Yu and Zhang, 2016]. Because of indiscriminately targeting the ground-truth label within the candidate label set, the identification-based framework is sensitive to the false positive labels that co-occur with the ground-truth label.

In a nutshell, the above learning frameworks train the model with the modeling outputs of the candidate labels indiscriminate (i.e., the same weight 1 |Si| ), while the different labeling confidence levels of the candidate labels are regrettably ignored. To address this problem, a novel unified partial label learning framework will be introduced in the next section. Following this framework, a biconvex formulation is presented to estimate the latent label distributions while training the model simultaneously.

3 The LALOApproach

For each training example, we receive a feature vector xi ∈ Rn and its corresponding label vector yi ∈ {0, 1}l with l labels. Suppose m denotes the number of training examples, X ∈ Rm×n and Y ∈ {0, 1}m×l are the instance matrix and label matrix, respectively. In this setting, yij = 1 means the i-th training sample is assigned the j-th label.

Existing partial label learning frameworks indiscriminately train the model with noise-corrupted label matrix Y ∈ {0, 1}m×l , in which the labeling confidence of each candidate label is not discriminated. However, each candidate normally makes different contributions to the model training. To capture the labeling confidence (relative importance) of each candidate label, we propose to train the model with the latent label distributions. Specifically, for a training example xi ∈ Rn , its latent label distribution is denoted by pi ∈ [0, 1]l . By arranging the label distributions of m training examples, we form the label distribution matrix P = [p1, p2, · · · , pm]⊤ ∈ [0, 1]m×l . By substituting Y ∈ {0, 1}m×l with P ∈ [0, 1]m×l , we thus propose a novel unified framework that estimates the latent label distributions while training the model simultaneously:

where L denotes the prescribed loss function, Ω controls the complexity of the model f , Ψ aims to guarantee an accurate estimation of the label distribution matrix P, and λ, µ are parameters trading off these three terms.

Unlike the average-based framework and the identificationbased framework, our proposed framework naturally treats the modeling outputs of the candidate labels in a discriminative manner due to the label distribution matrix P, which can indicate the different contributions of the candidate labels. To optimally estimate P, we assume it should have the following property: local consistency, i.e., nearby (similar) instances are supposed to have similar label distributions. Specifically, if the i-th instance xi is similar to the j-th instance xj, their corresponding label distributions pi and pj should also be similar. In order to characterize the similarity between instances, we construct the similarity matrix S = [sij ]m×m by the symmetry-favored k-NN graph [Liu and Chang, 2009]. Specifically, sij = exp(-‖xi -xj‖22 /σ2 ) if j ∈ Ni, otherwise sij = 0. The set Ni saves the indices of the knearest neighbors of xi, and the parameter σ is defined by σ = ∑mi=1 ‖xi - xik ‖2 /m where xik denotes the k-th nearest neighbor of xi. To ensure that S is symmetric, we finally set S = S + S⊤. In this way, we define Ψ(P) as follows:

where dii = ∑j sij is the degree of the vertex xi in the graph corresponding to the similarity matrix, and 0m×l ∈ {0}m×l . The first constraint formalizes the labeling confidence levels of all the labels as label distributions. The second constraint guarantees that the ground-truth label is strictly in the candidate label set, and the labeling confidence of each noncandidate label must be 0. Following the above settings, we propose to train the model by minimizing the least squares loss of fitting the label distributions:

where W ∈ Rn×l and b ∈ Rl are the model parameters. For the regularization term to control the model complexity, we adopt the widely-used squared Frobenius norm of W:

Finally, to further facilitate a kernel extension for the general nonlinear case, we present the formulation as a constrained optimization problem:

where zi = φ(xi) and φ(·) : Rn → Rh is a feature mapping that maps the feature space to some higher (maybe infinite) dimensional Hilbert space with h dimensions.

4 Alternating Optimization

Obviously, the optimization problem (5) is a biconvex problem [Gorski et al., 2007], and we solve this problem in an alternating way. Specifically, we first optimize the objective function with respective to W and b when P is fixed, and then optimize the objective function with respective to P when W and b are both fixed. This procedure is repeated until convergence or the maximum number of iterations is reached.

Updating W and b

When P ∈ Rm×l is fixed, the optimization problem (5) with respective to W and b can be stated as follows:

where Ξ = [e1, e2, · · · , em]⊤ ∈ Rm×l , tr(·) is the trace norm operator with the property tr (W⊤W) = ‖W‖2F , and 1m = [1, 1, · · · , 1]⊤ ∈ Rm. Then, the Lagrangian of this problem can be expressed as:

where A = [a1, a2, · · · , am]⊤ ∈ Rm×l is the matrix that stores the Lagrange multipliers. In this way, the following equations will be induced according to the KKT conditions:

Above linear equations can be solved by following steps:

Here, we define the positive definite matrix H by H = 1 2λ K + 12 Im×m and K = ZZ⊤ ∈ Rm×m is given by its elements kij = φ(xi)φ(xj)⊤ = K(xi, xj), where K(·, ·) is the kernel function. For LALO, Gaussian kernel K(xi, xj) = exp(-‖xi -xj‖22 /(2σ′2 )) is employed with σ′ set to the average distance of all pairs of training examples. The matrix Im×m is an identity matrix with m rows and m columns. Then we can obtain:

For computational convenience, we define s = 1⊤mH-1 ∈ R1×m, and the results are reported as follows:

Updating P

When W and b are fixed, the modeling output matrix Q ∈ Rm×l is denoted by Q= ZW+1mb⊤ = 1 2λ KA + 1mb⊤, then Ξ = P - Q. By eliminating Ξ, we can obtain:

Here, this optimization problem is actually a constrained label propagation problem [Zhou et al., 2004], where µ specifies the relative amount of labeling information from the neighbor points and the modeling outputs. The first constraint guarantees that a label distribution is consistently assigned to each instance in the process of label propagation. The second constraint guarantees that labels are only propagated among candidate labels. While in semi-supervised settings [Zhu and Goldberg, 2009], labels are normally propagated from labeled examples to unlabeled examples. In addition, traditional label propagation problems normally treat the observed label matrix Y as the initial label matrix. In contrast, since the observed label matrix Y is a noise-corrupted version in partial label learning, we take the modeling output matrix Q as the initial label matrix for each optimization iteration, thereby adjusting the confidence level of each candidate label iteratively. The optimization problem (12) can be reformulated as a standard Quadratic Programming (QP) problem, which can be solved by any off-the-shelf QP tools. The detailed information is given in Appendix A.

Algorithm 1 The LALO Algorithm

Inputs:

D: the PL training set D = {(X,Y)}

k: the number of nearest neighbors used for the similarity matrix

λ, µ: the parameters trading off each term in the loss function

Output:

y: the predicted label for the test example x

Process:

• 1: construct the similarity matrix by the symmetry-favored k-NN graph;
• 2: calculate the kernel matrix K= [K(xi, xj)]m×m;
• 3: initialize P according to (13);
• 4: repeat
• 5: update b and A according to (11);
• 6: update Q= 1 2λ KA + 1mb⊤;
• 7: calculate ˜p by solving (16) with a general QP procedure;
• 8: update P by reshaping ˜p ∈ Rml into P ∈ Rm×l ;
• 9: until convergence or the maximum number of iterations.
• 10: return the predicted label y according to (14).

At the beginning of the alternating optimization, we initialize the label distribution matrix P = [pij ]m×l as follows:

After ˜p is figured out, we can easily obtain the label distribution matrix P by reshaping ˜p ∈ Rml into P ∈ Rm×l . After the completion of the optimization process, the predicted label y of the test example x by LALO is given as follows:

The pseudo code of LALO is presented in Algorithm 1. Since the proposed formulation (5) is biconvex, it can be solved by the alternating optimization method with guaranteed convergence [Gorski et al., 2007], and we set the maximum number of iterations as 50.

5 Experiments

5.1 Experimental Setup

In this section, we conduct extensive experiments on artificial (i.e., controlled UCI datasets) and real-world datasets to evaluate the performance of LALO. The main characteristics of these datasets are reported in Table 1.

Following the widely-used controlling protocol [Chen et al., 2014; Cour et al., 2011; Liu and Dietterich, 2012; Yu and Zhang, 2016; Zhang and Yu, 2015; Zhang et al., 2016; Zhang et al., 2017], each UCI dataset is controlled by three parameters p, r and ϵ to generate artificial PL datasets. Here, p controls the proportion of training examples that are partially labeled, r controls the number of false positive labels within the candidate label set, and ϵ controls the co-occurring probability of a specific false positive label and the groundtruth label.

In addition, we have also collected 5 real-world PL datasets 1 , including Soccer Player [Zeng et al., 2013], Lost [Cour et al., 2011], Yahoo! News [Guillaumin et al., 2010], FGNET [Panis and Lanitis, 2014], and MSCRCv2 [Liu and Dietterich, 2012]. These real-world datasets come from several application domains. For automatic face naming (Lost, Soccer Player and Yahoo! News), each face cropped from an image or a video frame is considered as an instance and the names extracted from the corresponding image captions or video subtitles work as candidate labels. For objective classification (MSRCv2), image segments are considered as instances and objects appearing in the same image work as candidate labels. For facial age estimation (FG-NET), each human face is represented as an instance, and the age annotations obtained by crowdsouring are candidate labels. Besides, the average number of the candidate labels (Avg. CLs) for each real-world dataset is also recorded in Table 1.

The performance of LALO is compared with five state-ofthe-art partial label learning algorithms, each configured with recommended parameters according to the respective literature:

• PL-KNN [H¨ullermeier and Beringer, 2006]: an knearest neighbor approach following the average-based framework. (Recommended configuration: k = 10).
• CLPL [Cour et al., 2011]: a parametric approach following the average-based framework. (Recommended configuration: SVMwith squared hinge loss).
• IPAL [Zhang and Yu, 2015]: an instance-based approach following the average-based framework. (Recommended configuration: α = 0.95, k = 10, T = 100)
• PL-SVM [Nguyen and Caruana, 2008]: a maximum margin approach following the identificationbased framework. (Recommended configuration: regularization parameter pool with {10-3 , · · · , 103 }).
• LSB-CMM [Liu and Dietterich, 2012]: a maximum likelihood approach following the identification-based framework. (Recommended configuration: l mixture components).

The parameters employed by LALO are set as k = 10, λ = 0.05, µ = 0.005. The sensitivity analysis of LALO's parameter configuration is conducted in Subsection 5.3. On each artificial and real-world dataset, ten runs of 50%/50% random train/test splits are performed, and the averaged accuracies (with standard deviations) are recorded for all algorithms. In addition, we use the t-test at 0.05 significance level for two independent samples to investigate whether LALO is significantly superior/inferior to the comparing algorithms for all experiments.

5.2 Experimental Results

Controlled UCI Datasets

Figure 1 reports the classification accuracy of each algorithm as ϵ ranges from 0.1 to 0.7 with step size 0.1 when p and r are both fixed at 1. For each ground-truth label y ∈ Y, one extra label y′ ̸= y is selected as the coupled label that co-occurs with y in the candidate label set with probability ϵ, and any other label is chosen to be the false positive label with the probability 1 - ϵ. Figure 2 reports the classification accuracy of each algorithm as p ranges from 0.1 to 0.7 with step size 0.1 when r is set to 1. In this setting, r labels are randomly selected as the false positive labels in the candidate label set for the PL examples. In addition, we also do experiments on controlled UCI datasets as p ranges from 0.1 to 0.7 with r set to 2 and 3. Due to the limited space, these results are not reported here 2 , while they are quite similar to that in Figure 2 (r = 1).

1 These data sets are publicly avaible at: http://cse.seu.edu.cn/ PersonalPage/zhangml/Resources.htm#partial data

As shown in Figure 1 to 2, LALO outperforms the comparing algorithms in most cases. Besides, the detailed win/tie/loss counts between LALO and other comparing algorithms are recorded in Table 2. Out of the 112 results (4 UCI datasets×28 configurations), we can find that LALO can achieve superior or at least comparable performance against all comparing algorithms in most cases, and lose to them in only a few cases.

2 Figures and code package for LALO are publicly available at: https://sites.google.com/site/ramber1995paper/publications

Real-World Datasets

The predictive accuracy of each algorithm on real-world datasets is recorded in Table 3. Note that the average number of candidate labels (Avg. CLs) of the dataset FG-NET is quite large, which causes an extremely low classification accuracy of each algorithm. For better evaluation of this facial age estimation task, two extra experiments are conducted on the dataset FG-NET where a test example is considered to be correctly classified if the difference between the predicted age and the ground-truth age is no more than 3 years

(MAE3) or 5 years (MAE5). As shown in Table 3, it is obvious that LALO significantly outperforms all the counterpart algorithms on these real-world datasets except for CLPL on Lost, PL-SVM on Yahoo! News, and IPAL on MSRCv2 and Soccer Player, and LALO is never significantly outperformed by any comparing algorithm.

5.3 Sensitivity Analysis

We also study the sensitivity of LALO with respect to its three parameters λ, µ and k. Figure 3 shows the performance of LALO under different parameter configurations. From Figure 3, we can easily find that the parameter configuration specified for LALO in Subsection 5.1 (λ = 0.05, µ = 0.005, k = 10) naturally follows the sensitivity curves. In addition, Figure 3 also reports the difference of the label distribution matrix P between two successive iterations. We can easily observe that ∥∥P(t) -P(t-1)∥∥2F gradually decreases to 0 as t increases. Therefore, the convergence of LALO is demonstrated.

6 Conclusion

In this paper, we propose a novel unified partial label learning framework and present a biconvex formulation to leverage the latent label distributions for the model training. Extensive experimental results validate the effectiveness of the proposed approach named LALO. Since LALO serves as a bridge between the model training and label propagation, this work can be naturally extended to inductive semi-supervised learning based on label propagation. Besides, it is also interesting to exploit the consistency of the feature space and the label space in other manners.

Acknowledgements

The authors want to thank Prof. Min-Ling Zhang for help on the controlled UCI datasets and the comparing algorithms. This work was supported by MOE, NRF, and NTU.

A Quadratic Programming Formulation

To solve the problem (12), we let ˜p = vec(P) ∈ [0, 1]ml where vec(·) is the vectorization operator. Likewise, ˜q = vec(Q) ∈ Rml and ˜y = vec(Y) ∈ {0, 1}ml . To deal with the equality constraint using ˜p, we pick up the indices of ˜p by defining a set C = {C0, C1, · · · , Cm-1} as follows:

Using these notations, the problem (12) can be written as:

where ˜f = -2˜q, and ˜H ∈ Rml×ml is defined as follows:

Here, ˜T is a square matrix defined by ˜T = 2((µ+1)Im×mµD- 12 SD- 12 ) ∈ Rm×m where D is a diagonal matrix with its diagonal element defined by dii = ∑j sij. In this way, the optimization problem (16) can be efficiently solved by any off-the-shelf QP toolbox.