Partial Label Learning with Unlabeled Data

1 Introduction

Conventional supervised learning often assumes that each training instance is associated with a ground-truth label. However, in many real-world applications, one can only get access to a candidate label set associated with each training instance among which only one label is valid. For example, an episode of a video or TV serials may contain several characters and their faces may appear simultaneously in a screenshot. We have scripts and dialogues or subtitles which indicate that who is in the given screenshot. So that we can ambiguously name a face appeared in a screenshot by a candidate label set which contains the names appeared in the scripts and dialogues corresponding to it, but can not tell which face is associated with which name. In order to deal with this kind of training examples, partial label learning (PLL) has recently been proposed [Cour et al., 2011; Chen et al., 2014; Yu and Zhang, 2017] and attracted considerable attention, which has consequently resulted in a large number of PLL methods [H¨ullermeier and Beringer, 2006; Nguyen and Caruana, 2008; Liu and Dietterich, 2012; Zhang and Yu, 2015; Tang and Zhang, 2017].

In the previous studies on PLL, a basic assumption for training data is that all the candidate label sets are provided. However, in many real-world applications, such assumption is difficult to hold. Taking the above example again, although we can ambiguously label a face by a candidate label set which contains the names appeared in the scripts and dialogues, there still exist many screenshots that have no corresponding dialogues so that we have actually no label information for them. Similar situation occurs in many popular real-world applications such as web mining [Jie and Orabona, 2010], multimedia contents analysis [Zeng et al., 2013], ecoinformatics [Liu and Dietterich, 2012], etc.

It is evident that neither PLL nor semi-supervised learning (SSL) can tackle the problem concerned in this paper. For example, PLL ignores the use of large amount of unlabeled instances that could be very useful; while SSL assumes that the ground-truth single-label is accessible to each labeled training example, which is not the case in our situation. Note that the data scenario studies in the paper are quite different from previous work. We call this kind of problem semi-supervised partial label learning.

In this paper, a novel algorithm named SSPL (SemiSupervised Partial Label Learning), is proposed. It is crucial to disambiguate the candidate label sets of partial label examples at the same time as utilizing the data distribution information of unlabeled instances. In our method, an iterative label propagation procedure between partial labeled and unlabeled instances is employed to disambiguate the candidate label sets of partial label instances as well as assign valid labels to unlabeled instances. The label propagation procedure contains four phases. 1. Label propagation from partial label examples to unlabeled instances; 2. Label sets disambiguation of partial label examples; 3. Label set disambiguation of unlabeled instances; 4. Label propagation from unlabeled instances to partial label examples. The importance of unlabeled instances increases adaptively as the number of iteration increases, since they carry richer labeling information. Finally, unseen instances are classified based on the minimum reconstruction error on both partial label and unlabeled instances. Extensive experiments on real-world partial label data sets clearly show that SSPL achieves highly competitive performance against state-of-the-art approaches.

The rest of this paper is organized as follows. Section 2 discusses existing works. Section 3 presents technical details of the proposed SSPL approach. Section 4 reports comparative experiments. Finally, Section 5 concludes.

2 RelatedWork

The problem focused in this paper, i.e. semi-supervised partial label learning, is the intersection of PLL and SLL. Both PLL and SSL can be regarded as weakly supervised frameworks [Zhou, 2017] where label information conveyed by training examples is implicit or partially inaccessible.

One kind of strategy attempts to fitting widely-used learning techniques to partial label examples. For maximum likelihood techniques, the likelihood function is defined as the probability of observing each partial label training example over its candidate label set [Liu and Dietterich, 2012]. For maximum margin techniques, the classification margin over each partial label training example is defined by discriminative modeling outputs from candidate labels and noncandidate labels [Nguyen and Caruana, 2008; Yu and Zhang, 2017]. For instance-based techniques, the candidate label sets of neighbouring instances are merged via weighted voting for making prediction [H¨ullermeier and Beringer, 2006; Zhang and Yu, 2015]. Another kind of strategy aims to fit partial label examples to existing learning techniques. Following this, partial label examples can be transformed into binary examples via feature mapping [Chen et al., 2014], one-vsone decomposition [Wu and Zhang, 2018], or error-correcting outputs coded [Zhang et al., 2017]. However, PLL methods are not sufficient to learn from semi-supervised partial label examples well, because they ignore the data distribution information lie in the large amount of unlabeled data which is known to be very useful.

SLL [Zhu and Goldberg, 2009; Li and Liang, 2019] aims to induce a classifier f : X ↦→ Y from both labeled and unlabeled examples. There are four major categories of SLL approaches, i.e. generative methods [Miller and Uyar, 1997], graph-based methods [Blum and Chawla, 2001], low-density separation methods [Joachims, 1999] and disagreement-based methods [Zhou and Li, 2010]. Apparently, although SSL had taken the unlabeled instances into account, it still lacks of the ability of learning from partial label examples associated with candidate label sets.

Semi-supervised partial label learning is also related to other 'mixed' cases under weakly supervised learning frameworks such as multi-instance multi-label learning [Zhou et al., 2012], multi-instance active learning [Settles et al., 2008], semi-supervised multi-label learning [Kong et al., 2013], learning from incomplete and inaccurate supervision [Zhang et al., 2019] and semi-supervised weak-label learning [Dong et al., 2018]. It is worth noting that the data scenario studied in this paper looks similar to the semi-supervised multi-label learning. However, multi-label learning focuses on exploiting the label relationship among providing labels while PLL aims to disambiguate them.

Algorithm 1 A simple solution

Inputs:

• Dp:

the partial label training set {(xi, Si) | 1 ≤ i ≤ p}

Du:

the unlabeled training set {xi | p + 1 ≤ i ≤ p + u}

P: PLL algorithm

S: SSL learning algorithm

• x∗ : the unseen instance

Outputs:

• y∗ : the predicted class label for x∗

Process:

• 1: Disambiguate the partial label training examples (xi, Si) in Dp into single-label example (xi, ˆ yi) with PLL algorithm ˆ y ←P(Dp) ;
• 2: Train a multi-class classifier with labeled and unlabeled examples by SSL algorithm C ← S(Dl,Du), here Dl denotes {(xi, ˆ yi) | 1 ≤ i ≤ p};
• 3: Predict the unseen instance with C.

3 The ProposedMethod

3.1 Problem Statement and Notation

In the original PLL, let X = Rd be the d-dimensional instance space and Y = {y1, y2, . . . , yq} be the label space with q class labels. Formally, the partial label training set can be written as D = {(xi, Si)|1 ≤ i ≤ m}, where xi ∈ X is a ddimensional feature vector (xi1, xi2, . . . , xid)T and Si ⊆ Y is the associated candidate label set. Following the key assumption of PLL, the ground-truth label yi for xi is concealed in its candidate label set (i.e. yi ∈ Si) and therefore cannot be accessed by the learning algorithm.

In the semi-supervised partial label learning, the training set consists of not only partial label examples Dp = {(xi, Si)|1 ≤ i ≤ m} but also unlabeled instances Du = {xi|1 ≤ i ≤ m}. Given the semi-supervised partial label training set D = {Dp ∪ Du}, semi-supervised partial label learning aims to induce a classification model f : X ↦→ Y fromD such that for any unseen instance, f predicts its label.

3.2 A Simple Solution

The main difficulty of semi-supervised partial label learning lies in that the learning algorithm is required to disambiguating the candidate label sets of partial label examples and at the same time exploiting the data distribution information of unlabeled data. An intuitive solution is to disambiguate the candidate label sets of partial label training examples, i.e., picks up the valid single-label from candidate label set. Then, the problem is transformed into a simple SSL problem, which can be solved by a number of well-studied learning algorithms. Algorithm 1 summarizes the procedure for such a simple solution.

In the algorithm above, the label set disambiguation procedure and the exploitation of unlabeled data are completely separated. The unlabeled instances can not help improving the disambiguation accuracy of partial label examples. To address this critical limitation, in the proposed SSPL approach, an iterative label propagation procedure between partial label examples and unlabeled instances is employed to put them into a framework. In the following sections, the weighted graph construction procedure, which is necessary for label propagation, is first introduced and then the iterative label propagation algorithm.

3.3 Weighted Graph Construction

To realize the process of labeling information propagation from the source training set S = {xi | 1 ≤ i ≤ s} to the target training set T = {xi | 1 ≤ i ≤ t}, a weighted directed bipartite graph G = (U, V,E) is constructed over S and T . While vertex set U corresponds to the instances in the source training set and vertex set V corresponds to the instances in target training set. Edge set E contains the directed edges from U to V (note that E only consists of this kind of edges but not, e.g., edges from U to U or from U to U). For each instance xi in the target training set, its k-nearest neighbours N(xi) in the source training set are identified. Accordingly, the edges of graph G are set as E = {(xj , xi) | xj ∈ N(xi), 1 ≤ i ≤ t}.

From the graph G constructed above, we can simply specify a t × s weight matrix W = [wi,j ]t×s where wi,j ≥ 0 if (xj, xi) ∈ E and wi,j = 0 otherwise. In order to capture the fine-grained influences between instances, in this paper, we employed the weights calculation method applied in the IPAL approach [Zhang and Yu, 2015], which determines the weights by solving an novel optimization problem (OP). Let ˆ wi = [ ˆ wi,j1 , . . . , ˆ wi,jk ]T (ja ∈ N(xi), 1 ≤ a ≤ k) denotes the weight vector of xi in the target training set and its k-nearest neighbours N(xi) in the source training set, the influences of the instances xja in N(xi) to xi can be calculated by solving the following OP:

As shown in OP(1), the weight vector is optimized by fitting a linear least square problem subject to the non-negativity constraints, which can be obtained easily by a quadratic programming solver. Then the weight matrix W is normalized by row: ˜W = D-1W. Here, D = diag[d1, d2, . . . , dt] is a diagonal matrix with di = ∑sj=1 wi,j . Algorithm 2 summarizes the procedure of weighted graph construction.

3.4 Iterative Label Propagation

To facilitate the iterative label propagation procedure, four normalized weight matrix are constructed corresponding to the four phases in the label propagation procedure respectively. Specifically, H =WGC(Dp, Du, k) is used for the label propagation fromDp (source training set) to Du (target training set). J =WGC(Dp, Dp, k) is used for the label propagation fromDp to itself, i.e., label set disambiguation of partial label examples in Dp. K =WGC(Du, Du, k) is used for the label propagation fromDu to itself. L =WGC(Du, Dp, k) is used for the label propagation fromDu to Dp.

In the SSPL approach, labeling confidence matrix for partial label training examples and unlabeled instances, i.e.

Algorithm 2 WGC (weighted graph construction) procedure

Inputs:

S: the source training set {xi | 1 ≤ i ≤ s}

T : the target training set {xi | 1 ≤ i ≤ t}

k: the number of nearest neighbour considered Outputs:

˜W: the normalized weight matrix

Process:

• 1: Initialize weight matrixW= [wi,j]t×s;
• 2: for i = 1 to t do
• 3: Identify the k-nearest neighbours N(xi) in the source training set S for xi in the target training set T ;
• 4: Determine the weight vector ˆ wi = [ ˆ wi,j1 , . . . , ˆ wi,jk ]T w.r.t. xj and N(xi) by solving OP(1);
• 5: for ja ∈ N(xi) do
• 6: Set wi,ja = ˆ wi,ja ;
• 7: end for
• 8: end for
• 9: Normalize weight matrixWby column: ˜W=D-1W.

Fp = [fi,c]p×q and Fu = [fi,c]u×q are introduced, where fi,c ≥ 0 corresponds to the probability of label yc being the ground-truth label of instance xi. For partial label examples, the labeling confidence matrix can be initialized with Fp = P = [pi,c]p×q .

For unlabeled instances, the labeling confidence matrix can be initialized with Fu = U = [ui,c]u×q .

In other words, at the initialization step, for partial label examples, the probability of a label being the ground-truth label of instance xi is distributed over its candidate labels in Si. And for unlabeled instances, the probability is distributed over all q labels in Y.

The iterative label propagation procedure contains four phases: 1. label propagation from partial label examples to unlabeled instances; 2. label sets disambiguation of partial label examples; 3. label set disambiguation of unlabeled instances; 4. label propagation from unlabeled instances to partial label examples.

During the iteration, labeling confidence matrix Fp and Fu are updated according to the following equations.

Algorithm 3 The proposed SSPL approach

Inputs:

Outputs:

y∗ : the predicted class label for x∗

Process:

• 1: Construct normalized weight matrix H, J, K and L according to the WGC procedure in Table 2;
• 2: Initialize the label confidence matrix Fp and Fu according to Eq.(2) and Eq.(3);
• 3: for t = 1 to T do
• 4: Set Fu according to Eq.(4);
• 5: Set ˜Fp according to Eq.(5);
• 6: Re-scale ˜Fp to Fp according to Eq.(8);
• 7: Set Fu according to Eq.(6);
• 8: Set ˜Fp according to Eq.(7);
• 9: Re-scale ˜Fp to Fp according to Eq.(8);
• 10: end for
• 11: for i = 1 to p do
• 12: Disambiguate partial label example (xi, Si) into single label example (xi, ˆ yi) according to Eq.(9);
• 13: end for
• 14: for i = p+1 to p+u do
• 15: Assign valid label ˆ yi for unlabeled instance xi according to Eq.(9);
• 16: end for
• 17: Identify the k-nearest neighbours of x∗ in theDp andDu, i.e. Np(x∗ ) and Nu(x∗ );
• 18: Determine the weight vectors w∗ and θ∗ w.r.t. x∗ and its k-nearest neighbours in Dp and Du by solving OP(1);
• 19: Return the predicted class label y∗ according to Eq.(10).

Here, parameters α and β are used to balance the importance of partial label examples and unlabeled instances. As partial label examples carry more labeling information than unlabeled ones i.e. more important than unlabeled instances, α is always larger than β. In the SSPL approach, parameter β is set to zero at the beginning of the iteration as the unlabeled instances carrying no labeling information. As the iteration goes on, the unlabeled instances carry more labeling information and β increases and finally approaches to the pre-defined upper bound ˜ β. Parameter α is set to be a constant.

The labeling confidence matrix of partial label examples, i.e., ˜Fp, needs to be re-scaled into Fp after updated by propagating labeling information from Fp and Fu after phase2 and phase4. The re-scale operation clears the probability of labels outside of the candidate label set being the ground-truth label of partial label examples and then normalize sum of the labeling probability of an instance into one.

Finally, we can pick up the valid labels of partial label and unlabeled instances based on the final labeling confidence matrix Fp and Fu. Here, the SSPL approach adjusts the final label confidence towards the class prior distribution using the famous class mass normalization mechanism [Zhu and Goldberg, 2009]

Here, nc = ∑pi=1 yi,c is the prior distribution of yc in the initial labeling confidence matrix P, and ˜ nc = ∑p+u i=1 fi,c is the class mass of yc in the final labeling confidence matrix i.e. Fp and Fu.

During the testing phase, the class label of an unseen instance x∗ is predicted based on the minimum reconstruction error criterion on the disambiguated training examples, i.e. the disambiguated partial label examples {(xi, ˆ yi) | 1 ≤ i ≤ p} and disambiguated unlabeled instances {(xi, ˆ yi) | p+1 ≤ i ≤ p+u}. Firstly, the k-nearest neighbours of x∗ in Dp and Du i.e. Np(x∗ ) and Nu(x∗ ) are identified separately. After that, the weight vectors w∗ = [w∗ i1 , w∗ i2 , . . . , w∗ ik ]T (ia ∈ Np(x∗ ), 1 ≤ a ≤ k) and θ∗ = [θ∗ i1 , θ∗ i2 , . . . , θ∗ ik ]T (ib ∈ Nu(x∗ ), 1 ≤ a ≤ k) are determined w.r.t. x∗ and its k-nearest neighbours in Dp and Du by solving the same optimization problem OP(1). Finally, the unseen instance is classified based on the following equation:

Here, r is the tuning parameter weighting the reconstruction error on partial label and unlabeled instances.

Algorithm 3 summarizes the complete procedure of the proposed SSPL approach. Given the semi-supervised partial label training set, four normalized weight matrix are constructed over Dp and Du (Step 1). After that, label confidence matrix Fp and Fu are initialized and updated by iterative label propagation (Steps 2-10). Then, the SSPL approach picks up the valid labels of training examples according to Fp and Fu (Steps 11-16). Finally, unseen instances are classified based on the minimum reconstruction error of disambiguated training examples (Steps 17-19).

4 Experiments

In this section, we compare the performances of the proposed SSPL approaches with several state-of-the-art PLL algorithms on various real-world tasks including: automatic face naming, object classification and bird song classification.

p = 0.05

p = 0.10

p = 0.15

p = 0.20

p = 0.30

p = 0.40

p = 0.50

SSPL

0.493±0.000 0.500±0.000 0.500±0.000 0.506±0.000 0.510±0.000 0.517±0.000 0.523±0.000

IPAL

0.489±0.000 0.492±0.000 0.500±0.000 0.503±0.000 0.511±0.000 0.512±0.000 0.520±0.000

PL-KNN 0.489±0.000 0.491±0.000 0.491±0.000 0.490±0.000 0.491±0.000 0.492±0.000 0.492±0.000

CLPL

0.348±0.000· 0.280±0.001· 0.250±0.000· 0.254±0.000· 0.278±0.000· 0.331±0.000· 0.385±0.000·

PL-SVM 0.468±0.000· 0.465±0.001 0.439±0.007 0.465±0.001 0.478±0.000· 0.482±0.000· 0.480±0.000·

p = 0.05

p = 0.10

p = 0.15

p = 0.20

p = 0.30

p = 0.40

p = 0.50

SSPL

0.428±0.000 0.474±0.000 0.497±0.000 0.514±0.000 0.536±0.000 0.556±0.000 0.566±0.000

IPAL

0.380±0.000· 0.437±0.000· 0.454±0.000· 0.477±0.000· 0.511±0.000· 0.529±0.000· 0.552±0.000·

PL-KNN 0.312±0.000· 0.351±0.000· 0.368±0.000· 0.375±0.000· 0.404±0.000· 0.424±0.000· 0.435±0.000·

CLPL

0.408±0.000· 0.465±0.000· 0.499±0.000 0.525±0.000 0.554±0.000◦ 0.572±0.000 0.588±0.000◦

PL-SVM 0.245±0.004· 0.260±0.004· 0.230±0.004· 0.248±0.003· 0.243±0.003· 0.273±0.005· 0.251±0.001·

Table 4: Characteristic of the real-world partial label data sets.

4.1 Experimental Setup

The performance of SSPL is compared against five state-ofthe-art PLL algorithms, each configured with parameters suggested in respective literature:

• IPAL [Zhang and Yu, 2015] disambiguate the candidate label set via an iterative label propagation procedure [suggested configuration: k = 10, α = 0.95, T = 100]
• PL-KNN [H¨ullermeier and Beringer, 2006] which adapts k-nearest neighbor technique to learn from partial label examples via weighted voting [suggested configuration:

k = 10];

• CLPL [Cour et al., 2011] which transforms PLL into binary learning problem via feature mapping with convex loss optimization [suggested configuration: SVM with squared hinge loss];
• PL-SVM [Nguyen and Caruana, 2008] which adapts maximum margin technique to learn from PL data via l2 regularization [suggested configuration: regularization parameter pool with {10-3 , . . . , 103 }];

For each data set, we consider the percentage of partial label examples in the whole training set by randomly sampling p ∈ {0.05, 0.10, 0.15, 0.20, 0.30, 0.40, 0.50} instances from the whole training set with their candidate label sets and the other with no labeling information. For compared methods, only sampled partial label examples and their candidate label sets are provided. That is because PLL algorithms can not exploit from unlabeled data. According to the experiments conducted by us, using unlabeled data directly (simply view unlabeled instance as partial label example with its candidate label set equals to the whole label space Y) always hurt the performance of PLL algorithms.

As shown in Table 3, parameters employed by SSPL are set as k = 10, α = 0.70, ˜ β = 0.25, r = 0.7 and T = 100. In the rest of this section, five-fold cross-validation is performed on each real-world data set and in each training fold, the partial label instances are randomly sampled for three times. Accordingly, the mean predictive accuracies (and also the standard deviations) are recorded for all comparing algorithms.

4.2 Automatic Face Naming Task

In the automatic face naming task, our goal is to label the faces appeared in video or news images by the ground-truth names of characters or concerned people. For example, an episode of a video contains several characters and their faces may appear simultaneously in a screenshot. The scripts and dialogues are provided indicating which characters are in the screenshot, which forms the candidate label sets of the corresponding faces. Moreover, it is often the case that in a news collection every image is accompanied by a short textual description. Such a news image may contain several faces and the associated description will indicate the names of the people appeared in this image, which forms the candidate label sets of the faces. Three data sets are adopted for this task: Lost [Cour et al., 2011], Soccer Player [Zeng et al., 2013] and Yahoo!News [Guillaumin et al., 2010], each contains 1122, 17472 and 22991 face images across 16, 171 and 219 classes respectively. The average amount of candidate label sets for a single label are 2.23, 2.09 and 1.91. Please refer to Table 4 for details.

Pairwise t-test at 0.05 significance level is conducted based on the five-fold cross-validation and three-time random sampling, where the test outcomes between SSPL and the comparing approaches are also recorded.

As shown in Table 1, we can observe that SSPL achieves highly comparable performances to all the state-of-the-art PLL algorithms. Furthermore, we can also find that: 1) On all the three data sets in this task, SSPL outperforms PLKNN and PL-SVM at all subtasks; 2) SSPL achieves statistically superior performances to PL-KNN and PL-SVM on Lost and Yahoo!News and statistically superior to IPAL on Yahoo!News; 3) SSPL achieves comparable performances to CLPL on Lost and Yahoo!News while outperforms it on Soccer Player.

4.3 Object Classification Task

In this task, every image is segmented to several compact regions, and the labels of segmented regions, which are provided manually, forms the candidate label set of the image. Among the candidate label set, the label of the most dominant region is selected as the ground-truth single-label. Our goal is to predict the unseen images. MSRCv2 [Liu and Dietterich, 2012] data set is adopted for this task. This data set contains 1758 images with totally 23 classes. The average amount of candidate label sets for a single label is 3.16.

Results are presented in Table 2, from which we can observe that SSPL also achieves highly comparable performances to all the compared methods. Specifically, SSPL achieves the best performances on 6 of 7 subtasks (IPAL obtains the best performance when p = 0.05) and statistically superior to PL-KNN, CLPL and PL-SVM on most subtasks.

4.4 Bird Song Classification Task

The BirdSong [Briggs et al., 2012] data set is adopted for this task. BirdSong is collected from 548 bird sound records. Each record is consisted of 1-40 syllables, leading to totally 4998 syllables included in the data set. The bird species appeared in every record are manually annotated, which forms the candidate label sets of every syllable. We need to identity which syllable is from which kind of bird.

Results are reported in Table 3. It is impressive to observe that the proposed SSPL approach significantly outperforms all the compared algorithms. The SSPL approach achieves the best performances on all subtasks. Moreover, SSPL is statistically superior to IPAL on 3 subtasks and superior to PL-KNN, CLPL and PL-SVM on all subtasks.

5 Conclusion

In this paper, we consider a new learning setup called semisupervised partial label learning where the training set consists of two kinds of weak supervision, i.e., partial label data and unlabeled data. We propose an iterative label propagation method, which can process two kinds of weakly supervised data simultaneously by jointly propagating label between partial labeled and unlabeled instances, and derive a good label assignment. The experimental results show that our method is superior to approaches that only considering one kind of weak supervision. In future, we consider scaling up our model to large-scale data, and consider weak supervision data in dynamic environments.

Acknowledgments

This research was supported by the National Key R&D Program of China (2018YFB1004300) and the National Natural Science Foundation of China (61772262).