Solving the Partial Label Learning Problem: An Instance-Based Approach

1 Introduction

Partial label learning deals with the problem where each training example is associated a set of candidate labels, among which only one label is assumed to be valid [Cour et al., 2011; Zhang, 2014]. The problem of learning from partial label examples naturally arises in a number of real-world scenarios such as web mining [Jie and Orabona, 2010], multimedia contents analysis [Cour et al., 2009; Zeng et al., 2013], ecoinformatics [Liu and Dietterich, 2012], etc. 1

Formally, let X = Rd be the d-dimensional input space and Y = {y1, y2, . . . , yq} be the output space with q possible class labels. Given the partial label training set D = {(xi, Si) | 1 ≤ i ≤ m}, where xi ∈ X is a d-dimensional feature vector (xi1, xi2, . . . , xid)⊤ and Si ⊆ Y is the set of candidate labels associated with xi, the task of partial label learning is to induce a multi-class classifier f : X → Y from D. In partial label learning, the ground-truth label yi for xi is assumed to reside in the candidate label set (i.e. yi ∈ Si) but unknown to the learning algorithm.

1 In some cases, partial label learning is also termed as ambiguous label learning [H¨ullermeier and Beringer, 2006; Chen et al., 2014], soft label learning [Cˆome et al., 2008] or superset label learning [Liu and Dietterich, 2014].

As the ground-truth label is not accessible, one intuitive strategy to learn from partial label examples is to treat each candidate label in an equal manner for model induction [Cour et al., 2011]. The final prediction is made by averaging the modeling outputs from all the candidate labels. However, one potential drawback of this strategy lies in that the essential output yielded by the ground-truth label (i.e. yi) would be overwhelmed by the non-informative outputs yielded by the false positive labels (i.e. Si \ {yi}). Furthermore, the overwhelming effect caused by the false positive labels would be more pronounced as the size of candidate label set increases.

In this paper, rather than employing the above averaging strategy, we aim to solve the partial label learning problem by disambiguating the candidate label set directly. Accordingly, a novel partial label learning approach named IPAL, i.e. Instance-based PArtial Label learning, is proposed. Firstly, an asymmetric weighted graph over the training examples is constructed by affinity relationship analysis. After that, IPAL tries to identify the valid label of each partial label example via an iterative label propagation procedure. During the testing phase, the unseen instance is classified based on minimum error reconstruction from its nearest neighbors. Experimental studies on controlled UCI data sets as well as real-world partial label data sets clearly validate the effectiveness of IPAL against the comparing approaches.

The rest of this paper is organized as follows. Section 2 briefly discusses related work. Section 3 presents the technical details of the proposed IPAL approach. Section 4 reports the results of comparative experiments. Finally, Section 5 summarizes the paper and indicates future research issues.

2 RelatedWork

Partial label learning can be regarded as a weakly-supervised learning framework, where the supervision information conveyed by the partial label training examples are implicit. Conceptually speaking, it lies between two ends of the supervision spectrum, i.e. the traditional supervised learning with explicit supervision and the unsupervised learning with blind supervision. Partial label learning is related to other wellstudied weakly-supervised learning frameworks, including semi-supervised learning, multi-instance learning and multilabel learning. Nonetheless, different types of weak supervision information are handled by these learning frameworks.

Semi-supervised learning [Chapelle et al., 2006; Zhu and Goldberg, 2009] learns from abundant unlabeled examples together with few labeled examples. For unlabeled data the ground-truth label assumes the whole label space, while for partial label data the ground-truth label is confined within the candidate label set. Multi-instance learning [Dietterich et al., 1997; Amores, 2013] learns from labeled training examples each represented by a bag of instances. For multiinstance data the labels are assigned at the level of bags, while for partial label data the labels are assigned at the level of instances. Multi-label learning [Tsoumakas et al., 2010; Zhang and Zhou, 2014] learns from training examples each associated with multiple labels. For multi-label data all the associated labels are valid ones, while for partial label data the associated labels are only candidate ones.

To learn from partial label examples, one intuitive strategy is to treat all the candidate labels in an equal manner and then average the outputs from all candidate labels for prediction. Following this strategy, a straightforward instance-based solution [H¨ullermeier and Beringer, 2006] is to make prediction for unseen instance x∗ in the following way: f(x∗ ) = argmaxy∈Y ∑i∈N(x∗ ) I(y ∈ Si). Here, I(·) is the indicator function and the predicted label for x∗ is determined by aggregating the votes from the candidate labels of its neighboring examples indexed in N(x∗ ). Besides the instancebased instantiation, another solution following the averaging strategy is to assume a parametric model F(x, y; θ) for discriminative learning [Cour et al., 2011]. Here, the averaged output from all candidate labels, i.e. 1 |Si | ∑y∈Si F(xi, y; θ), is distinguished from the outputs from non-candidate labels, i.e. F(xi, y; θ) (y /∈ Si).

Though the averaging strategy is intuitive and easy to be implemented, its effectiveness is largely affected by the false positive labels whose outputs would overwhelm the essential output yielded by the ground-truth label. Therefore, another strategy to learn from partial label examples is to disambiguate the candidate label set by identifying the ground-truth label. Existing approaches following this strategy view the ground-truth label as latent variable and make use of the Expectation-Maximization (EM) procedure [Dempster et al., 1977] to refine the estimation of latent variable iteratively. The objective function optimized by the EM procedure can be instantiated based on the maximum likelihood criterion: ∑mi=1 log (∑y∈Si F(xi, y; θ)) [Jin and Ghahramani, 2003; Grandvalet and Bengio, 2004; Liu and Dietterich, 2012], or the maximum margin criterion: ∑mi=1 (max y∈Si F (xi, y; θ) - max y /∈Si F (xi, y; θ)) [Nguyen

In the next section, a novel partial label learning approach following the disambiguation strategy will be introduced. Different from EM-based disambiguation, the proposed approach does not assume any parametric model while tries to disambiguate the candidate label set by utilizing instancebased techniques.

3 The IPAL Approach

During the disambiguation phase, IPAL learns from partial label examples in two basic phases, i.e. weighted graph construction and iterative label propagation.

Let D = {(xi, Si) | 1 ≤ i ≤ m} be the partial label training set, where xi ∈ X is a d-dimensional instance (xi1, xi2, . . . , xid)⊤ and Si ⊆ Y is the candidate label set associated with xi. In this paper, a weighted graph G = (V, E) is constructed over the set of training examples with V = {xi | 1 ≤ i ≤ m}. For each instance xi, let N(xi) denote the indexes of its k-nearest neighbors identified in the training set, where the distance between two instances is calculated with the popular Euclidean metric. Accordingly, the edges of graph G are set as E = {(xi, xj) | i ∈ N(xj), 1 ≤ i ̸= j ≤ m}. In other words, there would be an (directed) edge from node xi to node xj iff xi is among the k-nearest neighbors of xj .

From the set of edges E, one can simply specify an m×m weight matrix W = [wi,j]m×m as follows: wi,j = 1 if (xi, xj) ∈ E; otherwise, wi,j = 0. In order to encode finegrained influences of neighboring instances, IPAL chooses to determine the weights by conducting some affinity relationship analysis. Let wj = [wi1,j,wi2,j, . . . ,wik,j]⊤ (ia ∈ N(xj), 1 ≤ a ≤ k) denote the weight vector w.r.t. xj and its k-nearest neighbors, the influence of each neighboring instance xia on xj (i.e. wia,j) is modeled by solving the following optimization problem (OP):

As shown in OP (1), the weight vector wj is optimized by fitting a linear least square problem subject to the non-negativity constraints. Here, we do not impose extra regularization term (e.g. L1- or L2-norm of wj) in the objective function to accommodate more space for optimization.

For OP (1), its optimal solution ˆwj can be obtained by applying any off-the-shelf quadratic programming (QP) solver. To some extent, magnitude of the optimized weight ˆwia,j encodes the strength of affinity between xj and its neighboring instance xia . Accordingly, IPAL specifies the weight matrix W as follows: wi,j = ˆwi,j if (xi, xj) ∈ E; otherwise wi,j = 0. It is worth noting that W is an asymmetric weight matrix, which reflects the fact that the neighboring relationship is not necessarily symmetric. Furthermore, even when two instances xi and xj happen to be neighboring instance of each other, the influence fromxi to xj (i.e. wi,j) is generally different to that fromxj to xi (i.e. wj,i). 2

To facilitate subsequent iterative label propagation procedure, the weight matrix W is then normalized by column: H = WD-1 . Here, D = diag[d1, d2, . . . , dm] is a diagonal matrix with dj = ∑mi=1 wi,j . Let F = [fi,c]m×q be an m× q matrix with non-negative entries, where fi,c ≥ 0 corresponds to the labeling confidence of yc being the ground-truth label of xi. Based on the partial label training set, an initial (prior) labeling confidence matrix F(0) = P = [pi,c]m×q can be instantiated as follows:

2 Therefore, symmetric setup of the weight matrix such as wi,j = exp (- ||xi-xj ||2 2σ2 ) [Zhou et al., 2004; Zhu and Goldberg, 2009] won't suffice under this circumstance.

In other words, at the initialization step, the labeling confidence of xi is equally distributed over its candidate labels in Si. At the t-th iteration, F is updated by propagating labeling information along with the normalized weight matrix H:

Here, parameter α ∈ (0, 1) controls the relative amount of information inherited from label propagation and initial labeling. After that, ˜F(t) is re-scaled into F(t) by consulting the candidate label set of each training example:

As the iterative procedure terminates, one can disambiguate each partial label training example (xi, Si) based on the final labeling confidence matrix ˆF as follows: ˆ yi = argmaxyc∈Y ˆ fi,c. In this paper, IPAL further adopts the class mass normalization (CMN) mechanism [Zhu and Goldberg, 2009] to adjust the disambiguation output towards class prior distribution:

Here, nc = ∑mi=1 pi,c is the class mass of yc w.r.t. prior labeling confidence matrix P, and ˆnc = ∑mi=1 ˆ fi,c is the class mass of yc w.r.t. final labeling confidence matrix ˆF.

During the testing phase, the class label of an unseen instance x∗ is predicted based on the disambiguated training examples (xi, ˆ yi). The k-nearest neighbors of x∗ in the training set, i.e. N(x∗ ), are firstly identified. After that, the weight vector w∗ = [w∗ i1 , w∗ i2 , . . . , w∗ ik ]⊤ (ia ∈ N(x∗ ), 1 ≤ a ≤ k) w.r.t. x∗ and its k-nearest neighbors are determined by solving the same optimization problem as shown in OP (1) (replacing {xj,wj} with {x∗ ,w∗}). Thereafter, the unseen instance is classified based on the following minimum error reconstruction criterion:

Table 1 summarizes the complete procedure of the proposed IPAL approach. Given the partial label training set, an asymmetric weighted graph are constructed by conducting affinity relationship analysis between each instance and its k-nearest neighbors (Steps 1-8). After that, an iterative label propagation procedure is performed to disambiguate the candidate label set of each training example (Steps 9-19). Finally, the unseen instance is classified based on minimum error reconstruction from its k-nearest neighbors (Steps 20-22).

Table 1: The pseudo-code of IPAL.

Inputs:

• D : the partial label training set {(xi, Si) | 1 ≤ i ≤m} (xi ∈ X , Si ⊆ Y, X = Rd , Y = {y1, y2, . . . , yq})

k : the number of nearest neighbors considered

α : the balancing coefficient in (0, 1)

T : the number of iterations

x∗ : the unseen instance

Outputs:

y∗ : the predicted class label for x∗

Process:

• 1: Initialize weight matrixW= [wi,j]m×m with wi,j = 0;
• 2: for j = 1 to mdo
• 3: Identify the k-nearest neighbors N(xj) in D for xj ;
• 4: Determine the weight vector ˆwj = [ ˆwi1,j, . . . , ˆwik,j]⊤ w.r.t. xj and its k-nearest neighbors by solving OP (1);
• 5: for ia ∈ N(xj) do
• 6: Set wia,j = ˆwia,j;
• 7: end for
• 8: end for
• 9: Normalize weight matrix W by column: H = WD-1 ;
• 10: Set the initial labeling confidence matrix P according to Eq.(2);
• 11: Set F(0) = P;
• 12: for t = 1 to T do
• 13: Set ˜F(t) according to Eq.(3);
• 14: Re-scale ˜F(t) into F(t) according to Eq.(4);
• 15: end for
• 16: Set the final labeling confidence matrix ˆF = F(T) ;
• 17: for i = 1 to mdo
• 18: Disambiguate partial label example (xi, Si) into single-label example (xi, ˆ yi) according to Eq.(5);
• 19: end for
• 20: Identify the k-nearest neighbors N(x∗ ) in D for x∗ ;
• 21: Determine the weight vector w∗ = [w∗ i1 , . . . , w∗ ik ]⊤ w.r.t. x∗ and its k-nearest neighbors by solving OP (1);
• 22: Return the predicted class label y∗ according to Eq.(6).

4 Experiments

4.1 Experimental Setup

In this paper, two series of comparative experiments are conducted on controlled UCI data sets [Bache and Lichman, 2013] as well as real-world partial label data sets. Table 2 summarizes characteristics of these experimental data sets.

Following the popular controlling protocol [Cour et al., 2011; Liu and Dietterich, 2012; Zhang, 2014; Chen et al., 2014], an artificial partial label data set is generated from a multi-class UCI data set under different configurations of three controlling parameters p, r and ϵ. Here, p controls the proportion of examples which are partially labeled (i.e. |Si| > 1), r controls the number of false positive labels in the candidate label set (i.e. |Si| = r + 1), and ϵ controls the co-occurring probability between one extra candidate label and the ground-truth label. A total of 28 (4x7) parameter configurations considered in this paper are listed in Table 2.

The real-world partial label data sets are collected from several application domains including Lost [Cour et al., 2011], Soccer Player [Zeng et al., 2013] and Yahoo! News [Guillaumin et al., 2010] for automatic face naming from images or videos, MSRCv2 [Liu and Dietterich, 2012] for object classification, and BirdSong [Briggs et al., 2012] for bird song classification. The average number of candidate labels (Avg. #CLs) for each real-world data set is also listed in Table 2.

The performance of IPAL is compared against four stateof-the-art partial label learning algorithms, each configured with parameters suggested in respective literature:

• PL-KNN [H¨ullermeier and Beringer, 2006]: an instancebased approach to partial label learning by adopting the averaging strategy, where the number of nearest neighbors considered by PL-KNN is set to be 10;
• CLPL [Cour et al., 2011]: a parametric approach to partial label learning by adopting the averaging strategy, where the parametric model is set to be SVM with squared hinge loss;
• PL-SVM [Nguyen and Caruana, 2008]: a maximummargin approach to partial label learning by adopting the EM-based disambiguation strategy, where the regularization parameter is chosen among {10-3 , . . . , 103} via cross-validation;
• LSB-CMM [Liu and Dietterich, 2012]: a maximum likelihood approach to partial label learning by adopting the

EM-based disambiguation strategy, where the number of mixture components is set to be the number of class labels of each data set.

As shown in Table 1, parameters employed by IPAL are set as k = 10, α = 0.95 and T = 100. 3 In the rest of this section, ten-fold cross-validation is performed on each artificial as well as real-world partial label data set. Accordingly, the mean predictive accuracies (and also the standard deviations) are recorded for all comparing algorithms.

4.2 Experimental Results

Controlled UCI Data Sets

Figure 1 illustrates the classification accuracy of each comparing algorithm as the co-occurring probability ϵ varies from 0.1 to 0.7 with step-size 0.1 (p = 1, r = 1). One label y′ is designated as the extra candidate label for each class label y ∈ Y, where y′ is chosen to co-occur with y with probability ϵ when y is the ground-truth label. Otherwise, any other class label would be chosen to co-occur with y. Figures 2 to 4 illustrate the classification accuracy of each comparing algorithm as the proportion p varies from 0.1 to 0.7 with step-size 0.1 (r = 1, 2, 3). For any partially labeled example, along with the ground-truth label, r class labels in Y will be randomly picked up to constitute the candidate label set.

3 Sensitivity analysis on IPAL's parameter configuration is reported in Subsection 4.3.

As illustrated in Figures 1 to 4, the performance of IPAL is highly competitive to other comparing algorithms in most cases. Specifically, pairwise t-test at 0.05 significance level is conducted based on the results of ten-fold cross-validation. Table 3 summarizes the win/tie/loss counts between IPAL and the comparing algorithms. Out of the 112 statistical comparisons (28 configurations × 4 UCI data sets), it is shown that: 1) IPAL achieves superior performance against PL-KNN in 81.2% cases and has been outperformed by PL-KNN in only 13.4% cases; 2) IPAL achieves superior performance against CLPL and LSB-CMM in 94.6% and 80.3% cases respectively, and is comparable to both of them in the rest cases; 3) IPAL is shown to be inferior to PL-SVM in only 1 out of 112 cases, and outperforms PL-SVM in the rest cases.

Real-World Data Sets

Table 4 reports the performance of each comparing algorithm on the real-world partial label data sets. Pairwise t-test at 0.05 significance level is conducted based on the results of ten-fold cross-validation, and the test outcomes between IPAL and other comparing algorithms are recorded.

As shown in Table 4, it is impressive that no algorithm has outperformed IPAL on the real-world data sets. Furthermore, we can also observe that: 1) IPAL achieves superior performance against PL-KNN on all data sets, which is also an instance-based approach to learning from partial label examples following the averaging strategy; 2) IPAL is comparable to CLPL and PL-SVM on the Lost data set, and achieves superior performance than both of them on the rest data sets; 3) IPAL is comparable to LSB-CMM on the Lost, BirdSong and Yahoo! News data sets, and achieves superior performance than LSB-CMM on the other two data sets.

4.3 Sensitivity Analysis

According to Table 1, IPAL learns from partial label examples by employing three parameters, i.e. k (number of nearest neighbors), α (balancing coefficient) and T (number of iterations). To study the sensitivity of IPAL w.r.t. them, Figure 5 illustrates how IPAL performs under different parameter configurations. For clarity of illustration, Lost and MSRCv2 are employed here for analysis purpose while similar observations can be made on other data sets. As shown in Figure 5, it is obvious that:

• The performance of IPAL improves slightly as k increases from 5 and becomes stable shortly after k reaches 8 (Figure 5(a));
• The performance of IPAL improves steadily as α increases from 0.3 (Figure 5(b)). These observations indicate that the amount of labeling information propagated from neighboring instances (i.e. the first term of Eq.(3)) plays a key role for the effectiveness of IPAL;
• The model of IPAL (labeling confidence matrix F) changes significantly in initial label propagation itera-

tions and becomes convergent when T reaches 20 (Figure 5(c)).

Therefore, the parameter configuration specified for IPAL in Subsection 4.1 (k = 10, α = 0.95, T = 100) naturally follows from the above analysis.

5 Conclusion

In this paper, the problem of partial label learning is studied where an instance-based approach named IPAL is proposed. Instead of employing the averaging strategy, IPAL aims to learn from partial label examples by directly disambiguating the candidate label via iterative label propagation. Extensive comparative studies clearly validate the effectiveness of IPAL.

In terms of label propagation, an important future work is to explore other ways to construct the weighted graph. For instance-based approach, it is also interesting to investigate better distance metric other than Euclidean distance for knearest neighbors identification.

Acknowledgments

The authors wish to thank the anonymous reviewers for their insightful comments and suggestions. This work was supported by the National Science Foundation of China (61175049, 61222309), and the MOE Program for New Century Excellent Talents in University (NCET-13-0130).