Two-stage Training for Learning from Label Proportions

1 Introduction

Learning from label proportions (LLP) is an important weakly supervised classification problem with only the label proportions in grouped data available. Still, training LLP aims to obtain an instance-level classifier for the newcome inputs. Successfully resolving LLP problems greatly contribute to many real-life applications: demographic classification [Ardehaly and Culotta, 2017], US presidential election [Sun et al., 2017], embryo implantation prediction [Hern´andez-Gonz´alez et al., 2018], spam filtering [Kuck and de Freitas, 2012], video event detection [Lai et al., 2014], visual attribute modeling [Chen et al., 2014; Yu et al., 2014a], and traffic flow prediction [Liebig et al., 2015].

∗Equal Contribution

†Corresponding Authors

On the one hand, the learnability of LLP strongly depends on the instances grouping and the proportions distribution in the bags. [Yu et al., 2014b] studied the instance-level empirical proportions risk minimization (EPRM) algorithm for LLP, w.r.t. the number, the size, and the prior label distribution of the bags. They proved that LLP is learnable with the EPRM principle and given the bound of expected learning risk.

On the other hand, EPRM strives to minimize bag-level label proportions error. Normally, this goal is achieved by minimizing Kullback-Leibler (KL) divergence between prior and posterior class distributions in each bag. However, baglevel proportional information hardly provides sufficient constraints to perfectly solve LLP, because too many instancelevel classifiers can satisfy proportional constraints exactly. In other words, when considering instance-level classification, LLP is ill-posed. As a consequence of the underdetermination, despite a number of achievements have been developed to resolve LLP accurately, it is still of great importance to design effective instance-level learning scheme to significantly improve the performance on high-dimensional data, e.g., images, merely with the proportional information.

In this paper, we challenge this issue through explicit weakly supervised clustering with proportions, instead of the inadequate bag-level KL divergence. To be concrete, unsupervised clustering is expected to discover data clusters specifically corresponding to classes. However, na¨ıvely applying clustering without supervision will result in a trivial solution to assign all the instances to one cluster, deviating from the semantics, i.e., classes. Fortunately, we can avoid this degeneration by imposing appropriate constraints on the cluster distribution [Caron et al., 2018]. For example, when there is no knowledge on labels, we impose discrete uniform distribution to labels, leading to equal clustering. Besides, in a semi-supervised learning protocol, the clustering result can be restricted with the help of labeled instances [Asano et al., 2020] as well. Similarly, in LLP scenario, we draw inspiration from this constrained clustering, to leverage label proportions to constrain cluster sizes. Specifically, we build a constrained optimization problem, regarding feasible solutions as pseudo-labels that accurately complying proportions.

In order to properly tackle the weak supervision, we cast our framework, called PLOT, by considering pseudo labeling and the classification within one objective, utilizing label proportions as the constraints. To implement the proposed schema, we alternately update the network parameters and the pseudo-labels, where optimal transport (OT) [Peyr´e et al., 2019] is employed to conduct the pseudo labeling process and standard cross-entropy minimization is adopted to train the network parameters. Besides, to recognize the resulting pseudo-label as noisy label to the unknown clean one, we spur a new line to propose a two-stage training strategy: Set our method as a following stage after other LLP solvers, and train the classification network with symmetric cross-entropy (SCE) [Wang et al., 2019] along with mixup dataset [Zhang et al., 2018] to combat the memorization of noisy labels and inject the robustness into the solution. We illustrate the proposed two-stage framework in Figure 1.

In summary, our main contributions are four-fold:

• We propose a novel LLP framework PLOT, which aims at meeting the exact proportions with a constrained optimization, and is an essentially orthogonal LLP treatment to the existing LLP algorithms;
• We conduct an alternate optimization process to solve the optimization on both the neural network classifier and pseudo labeling, by applying SCE to learn from the noisy pseudo-labels obtained with OT;
• Our framework is model-agnostic, and we demonstrate that it can easily fit for various deep-based LLP models as a post-hoc stage to further boost their performance;
• With lightly additional hyper-parameter and mixup data augmentation, our framework achieves state-of-the-art LLP performance on several benchmark datasets, based on the neural network pipeline with standard settings.

2 RelatedWork

To our knowledge, four end-to-end pipelines have been proposed for LLP, with deep neural networks as the backbone architecture. Specifically, DLLP [Ardehaly and Culotta, 2017] is the first end-to-end LLP algorithm, with the KL divergence of prior and posterior proportions as the objective. Although DLLP can learn a competent instance-level classifier, it is hardly in accordance with the proportions in training data, especially with large bag sizes (e.g., >64). In order to "guess" instance labels that are consistent to proportions [Yu et al.,

2013], [Dulac-Arnold et al., 2019] perform convex relaxation to labeling variables and first recognize it as an OT problem. Aiming at end-to-end training, they instead impose inexact labeling with KL divergence similar to DLLP, and efficiently solve the resulting unbalanced OT problem with entropic regularization. However, the KL divergence results in inaccurate labeling, thus introduces additional noise to pseudo-labels compared to accurate labeling. We discuss the differences between their work and our work in Section 6.

Recently, LLP-GAN [Liu et al., 2019] greatly improves DLLP with adversarial mechanism. In detail, the discriminator is designed as a (K+1)-way classifier, where the first K classes indicate the real ones, and the (K+1)th class accounts for the generated one. The main insight is to produce better representation with adversarial learning, thus boosting the downstream discriminative tasks. In spite of substantial performance improvement compared with previous methods, LLP-GAN suffers from training instability, which inherits the characteristics from GANs [Gui et al., 2020]. Besides, in order to obtain satisfactory results, it requires subtle network design and hyper-parameters selection. Similarly, based on visual adversarial training [Miyato et al., 2018] in semisupervised learning, [Tsai and Lin, 2020] introduce consistency regularization, and propose LLP-VAT, while the KL divergence on the proportions is intact in the loss.

However, KL divergence based methods hardly delivery classifiers abiding the proportions on training data. When performing alternate update, this inexact labeling exaggerates the label noise, especially with entropic regularization. In contrast, we address this problem with a constrained optimization to exactly follow the proportions. Furthermore, the diversity in unlabeled data demonstrates useful behavior for classification [Lu et al., 2018]. Based on the great capacity of deep models, unsupervised representation learning is achievable and appealing as a promising step towards discriminative tasks. For example, aligning the clustering with semantic classes can successfully improve image classification and segmentation [Ji et al., 2019]. [Asano et al., 2020] apply (entropic constrained) optimal transport (OT) to learn representation with a self-labeling mechanism. Following their seminal framework, in this paper, we propose an OT based LLP algorithm, and further develop detailed techniques.

3 Preliminaries

In order to clearly describe how to leverage OT for LLP, we first introduce several preliminaries for both OT and LLP. More details are in Appendix due to the space limitation.

3.1 Optimal Transport via Kantorovich Relaxation

Define two discrete measures on two arbitrary sets X and Y, respectively: α = ∑ni=1 aiδxi , β = ∑mj=1 bjδyj , where a= (ai)ni=1 ∈Σn , b = (bj)mj=1 ∈Σm, and Σs is probability simplex, i.e., Σs = {a ∈ Rs+∣∣ ∑si=1 ai = 1}, , ∀s ∈ Z+. To achieve mass splitting in Kantorovich relaxation, instead of permutation σ or surjective map T, we use coupling matrix P ∈ Rn×m + with Pij as the mass flowing from xi to yj. Admissible couplings give a simpler characterization than maps in Monge problem: Suppose a ∈ Σn , b ∈ Σm, we denote U(a, b) = {P ∈ Rn×m + | P1m = a, Pᵀ1n = b}, where 1n represents n-dimensional all ones column vector. Hence, U(a, b) stands for the set of all Kantorovich mappings. Similar to Monge problem, let 〈·, ·〉 be the Frobenius dot-product, given a, b ∈ Σn and a cost matrix C, the Kantorovich's optimal transport (OT) problem is a linear programming as

3.2 Entropic Regularization of Optimal Transport

The solution of the original OT problem (1) is non-unique and tends to be sparse, i.e., arriving at certain vertex of the polytope U(a, b). To form a more "blurred" prediction, [Cuturi, 2013] propose the entropic regularization for OT problem. To be specific, the discrete entropy of a coupling matrix P is well-known as H(P) = - ∑i,j Pij log(Pij).

Remark 1 ([Peyr´e et al., 2019]). The entropic function H(·) is 1-strongly concave, due to the negative definite Hessian matrix: ∂ 2H(P) = -diag(1./P) and Pij ⩽ 1, ∀i, j.

Note that the rank-1 matrix abᵀ is an admissible coupling, and H(P)⩽H(a)+H(b)=H(abᵀ ). The entropic regularization of OT adds -H(·) to original OT (1) as:

which is a constrained minimization problem of an ε-convex function (Remark 1), thus has a unique minimum. More importantly, the entropic constraint guarantees a computationally efficient process to find the solution, as a consequence of restricting the search for low cost joint probabilities within sufficient smooth tables [Cuturi, 2013]. Apparently, if ε→+∞, the solution of entropic regularized OT (2) is abᵀ . In addition, the solution of (2) converges to that of the original OT (1) as ε → 0.

3.3 Learning fromLabel Proportions

In LLP problem, because the label proportions are available, we can restrict the instance-level self-labeling procedure with these proportional information using an OT framework. Before further discussion, we fist give the formal formulation for LLP by directly considering a multi-class problem with K classes in this paper. With no prior knowledge, we further suppose that the training data consist of N randomly generated disjoint bags. Consequently, the training data can be expressed as D = {(Bi, pi)}mi=1 , where Bi = {xi,j}ni j=1 denotes the instances in the ith bag, and Bi ∩ Bj = ∅, ∀i ̸= j. The pi ∈ [0, 1]K and ni are the known ground-truth label proportions and the bag size of the ith bag, respectively.

4 Approach

4.1 Linking OT to LLP (PLOT)

[Asano et al., 2020] introduce a self-labeling framework to leverage equal clustering to learn discriminative representation on unsupervised data and achieve classification. In LLP problem, although the class distribution is not uniform within each bag, we can easily modify the admissible couplings in

(1) to fit in the proportional information. Consequently, with pyi as the proportion of class y in bag i, we have

Note that (3) is a constrained optimization and the labels should strictly comply with the proportions in each bag. Nevertheless, (3) will be combinatorial if imposing one-hot labeling in q , thus is very difficult to optimize. Fortunately, as we will point out, (3) is a typical OT problem, thus can be solved relatively efficiently to arrive at a sparse (one-hot) solution.

For better explanation, we rewrite (3) in a matrix fashion. Formally, let Qi = (Qijk ) ∈ RK×ni + ,Qijk = q(k|xi,j)/ni, and Pi = (P i jk ) ∈ RK×ni + , P i jk = pφ(k|xi,j)/ni. In addition, denote Q = diag{Qi }mi=1 , P = diag{Pi }mi=1 , and p = (pᵀ1 , pᵀ2 , · · · , pᵀm)ᵀ , b = (1ᵀn1 /n1, 1ᵀn2 /n2, · · · , 1ᵀnm /nm)ᵀ . Define U (p, b) = {Q ∈ RmK×N + | Q1N =p, Qᵀ1mK =b}. Accordingly, we have an equivalent OT problem for (3) as:

On the other hand, with λ→+∞, we can instead solve the entropic regularized OT problem to accelerate the process of convergence, as well as attaining unique non-sparse solution.

4.2 Alternating Optimization

In the proposed learning framework, the network parameters φ = (ϕ, θ) and self-labels Q are alternately updated. Now, we further describe the details as follows.

Training the Network with Fixed Q. Because the crossentropy is differentiable w.r.t. the network parameters φ = (ϕ, θ), we can directly conduct common optimizer, e.g., Adam, on the objective in (3) by fixing Q.

Updating the Labels Qwith Fixed φ. When the model is fixed, the label assignment matrix Q are obtained by OT or entropic regularized OT. When performing original OT, the solution Q∗ is with 0/1 binary elements. However, entropic regularized OT produces Q∗ with all elements in [0,1]. In practice, we employ two strategies for label update: hard labeling and soft labeling. In hard labeling, we update Q as:

In soft labeling, we directly use the labels obtained by entropic regularized OT. In the experimental part, we provide the performance comparison on hard and soft labeling.

4.3 Two-stage Training for LLP

In practice, we consider to perform the clustering in every single bag, with the proportions as the constraint for instances number in each cluster. In detail, we conduct the constrained OT problem (4) w.r.t. Qi and Pi , with minor revision on U(p, b), i.e., U(pi, bi), where bi = 1ni /ni. On the other hand, we can instead solve the entropic regularized OT problem (5) with the same revision as (7) to accelerate the training, as well as obtain non-sparse solution to perform soft labeling:

Our two-stage training process uses KL-divergence based LLP training as the first stage, and supervised learning with pseudo-labels generated by OT as the second stage. In order to reduce the memorization of corrupt pseudo-labels, we incorporate symmetric cross-entropy (SCE) [Wang et al., 2019] in second stage. Let LCE be cross-entropy H(p, q), we denote LRCE as reverse cross-entropy H(q, p) defined as:

Accordingly, the SCE is defined as

To further improve the performance, we apply mixup [Zhang et al., 2018] to any two pairs (xi, yi) and (xj, yj), i.e., x=λxi+(1-λ)xj and y=λyi+(1-λ)yj, to obtain a new data point (x, y). The detailed training process of the second stage is shown in Algorithm 1.

5 Numerical Experiments

In order to demonstrate OL-LLP is model-agnostic, in this section, we conduct quantitative and qualitative studies with extensive experiments, to show the improvement of former LLP methods, when using PLOT as the second training stage. We use two benchmark datasets: CIFAR-10 and CIFAR-100. The comparisons are performed on three recently proposed algorithms DLLP [Ardehaly and Culotta, 2017], LLP-VAT [Tsai and Lin, 2020], and LLP-GAN [Liu et al., 2019].

5.1 Synthetic Datasets Study

We first evaluate our approach with a toy example. In detail, we choose the well-known "two-moon" dataset to obtain the performance of DLLP and LLP-GAN, as well as their combination with PLOT as the second training stage. A 3-hiddenlayer neural network with ReLU activation is employed. We conduct the experiment with the same bag setting, where 40 bags are generated with each containing 50 points.

The results are visualized in Figure 2, with different classes in red and green, respectively. For DLLP in Figure 2(a), blobs of data is mis-classified for both categories, while the portion of errors reduces when incorporating PLOT to DLLP in Figure 2(b). When it comes to stronger baseline LLPGAN in Figure 2(c), only the tails of both categories are misclassified. However, only visible two green points are misclassified to red at the tail in Figure 2(d), whose results are obtained by conducting OP-LLP training as the second stage to

Algorithm 1 Second Stage Pseudo Labeling with OT (PLOT)

Require:

The LLP training data D={(Bi, pi)}mi=1 ;

The initialization of the network parameters: φ = (ϕ, θ); The block diagonal matrix Q = diag{Qi }mi=1 as the pseudo-labels obtained in the first-stage.

Ensure:

• 1: for each epoch over D and the pseudo-labels Q do
• 2: Sample one mini-batch of training bags BD from D and the corresponding pseudo-labels fromQ
• 3: for each mini-batch do
• 4: Train network based on SCE with the pseudo-labels to update the parameters φ = (ϕ, θ).
• 5: end for
• 6: Update the pseudo labeling matrix Q = diag{Qi }mi=1 through the OT or entropic regularized OT.
• 7: end for
• 8: return The appropriate values of φ = (ϕ, θ).

with PLOT on the "two moons" dataset. (Best viewed in color)

LLP-GAN. It effectively demonstrates that our second stage can further boost the performance of other LLP solvers. In practice, solving OT can be regarded as a complementary refinement for the solution of minimizing the KL divergence.

5.2 Experimental Setting

Label Proportions Generation. As there is no off-theshelf LLP datasets, we first generate LLP datasets with the label proportions using four supervised benchmark datasets. Following the setting from [Liu et al., 2019], we construct four kinds of bags, with bag sizes of 16, 32, 64, and 128, respectively. In order to avoid the influence of different label distributions, the bag setting is fixed across different methods.

Training Setting. We choose a conv-based 13-layer maxpooling network as the backbone for all methods. The architecture details is given in Appendix A.6. Meanwhile, Adam optimizer is used with β1 =0.5 and β2 =0.999. The initial learning rate is 1e-4, divided by 2 every 100 epochs. Random horizontal flip and random crop with padding to the original images is employed as data augmentation. The hyperparameters for SCE is the same as [Wang et al., 2019].

5.3 Comparison with the State-of-the-arts

In this section, we provide the overall accuracy comparison between our approach and three SoTA methods: DLLP, LLPGAN, and LLP-VAT, on CIFAR-10 and CIFAR-100. Specifically, our method divides the training into two phases, where the first phase is to train the three KL-divergence based models as the teacher model, and the second stage is to update the student model based on the pseudo-labels obtained in the first step, followed by solving the OT with the proportional information in an alternate manner, described in Algorithm 1. In practice, note that our approach is model-agnostic, which means the first stage can be any deep learning based model, and our model can boost their performance by attaining local solutions with significantly better performance.

For fair comparison, in Tabel 1 we provide the results on CIFAR-10 without mixup [Zhang et al., 2018]. For the first glance, since bigger bag size contains less supervision when the training data is fixed, the accuracies of all the methods decrease along with the increase of bag size. Nevertheless, the performance of all methods can efficiently improve when combining with the proposed second-stage training. Note that the improvement is more obvious with bag sizes of 64 and 128, which is more challenging compared with smaller bag sizes. For example, the accuracy of LLP-GAN + PLOT with bag size 128 reaches 79.08, even superior to the previous SoTA result with bag size 64. Furthermore, this combination can approximately achieve a similar performance to the fully supervised scenario with small bag sizes, e.g., 16. In general, we can further draw a conclusion: Algorithm with the best performance in the first stage consistently results in the best performance when introducing PLOT as the second stage.

When it comes to harder CIFAR-100 in Table 2, we have similar results: Our method can considerably boost other LLP methods to reach new state-of-the-art results. In particular, our method reaches an accuracy rate of 43.44 with bag size 128, which is much higher than all the previous state-of-thearts. This indicates that incorporating the OT based pseudolabels mechanism to learn label proportions is of higher efficiency. In practice, the proportion of pseudo labeling can be intact to the real proportions through the optimal transport, thus improving the total accuracy of training data.

Note that the improvement for LLP-VAT is relatively limited compared to DLLP and LLP-GAN when incorporating our post-hoc training, especially for bag sizes of 16 and 32. A main reason is the key idea for noise reduction in network prediction is coincident in both methods, although different mechanisms are applied: LLP-VAT leverages the prediction consistency with adversarial samples as regularization, while our recipe is to obtain pseudo-labels with OT, then employs SCE and mixup as the post-hoc noise reduction techniques.

The motivation behind our approach is the predicted labels of training data can be further refined by optimal transport, so as to fulfill better pseudo labeling. To show this, we provide the accuracy curves for CIFAR-10 and CIFAR-100 with bag size 64 in Figure 3, where TD, TD OT, and TD OT 5 denote the accuracies without OT, with OT, and with the average of the last five pseudo-labels with OT (i.e., ensembles), respectively. It demonstrates that the accuracy can significantly improve after involving optimal transport. In particular, the advantage is more obvious for CIFAR-100, by a larger margin between TD and TD OT. Meanwhile, the accuracy can further improve by using the average of the last five OT pseudolabels as the final pseudo-label in every OT labeling phase.

5.4 Ablation Study

In this section, we carry out ablation study on key components introduced in PLOT. All the experiments are conducted on the dataset CIFAR-10 with the bag size 64. More specifically, our analysis mainly focuses on the difference between cross-entropy and symmetric cross-entropy. Furthermore, we evaluate the effect of mixup augmentation to our model when updating network parameters with above losses.

The final results are shown in Table 3. The baseline is the performance of DLLP in the first stage. The LCE and LSCE means that the model is trained without optimal transport, merely using the mean of instance-level predictions in the previous five epochs as pseudo-labels. This strategy can also improve the performance slightly. In particular, compared with LCE, LSCE provides a 2% higher performance improvement. On the other hand, the accuracy can be further increased when employing the pseudo-labels generated by OT. In particular, SCE is considerably effective, in contrast to CE, mainly due to its robustness to label noise.

Besides, mixup can further improve the performance significantly, which is mainly because of the following two reasons. On one hand, it reduces the memorization of corrupt labels, similar to SCE. On the other hand, it can impose more generalization on the network with the convex combination of a pair of examples, as well as their pseudo-labels.

5.5 Hard-label vs. Soft-label

In our model, we can employ two strategies to update the label: the hard labeling with the sparse original OT solution and the soft labeling with entropic regularized OT solution. The detailed process is shown in (6). In order to better demonstrate the difference between the hard-labels and soft-labels in our approach, we adopt CIFAR-10 and CIFAR-100 to conduct comparison on the performance with different bag sizes. Specifically, the solution of the first stage is fixed for both hard and soft labeling for fair comparison. The results are shown in Figure 4, where we provide the convergence curve of the second stage under different pseudo labelings.

From the result, we observe that it reach a comparable performance with hard and soft labelings for CIFAR-10 and CIFAR-100. Intuitively, the soft-labels are more informative than the hard labels. However, it does not necessarily lead to better performance due to the potential noisy labeling. On the other hand, the solution of the original OT tends to be sparse, and with less noise. We reckon this as the main reason of the comparable performance of two psuedo labeling strategies.

6 Discussion and Conclusion

In this paper, we study the challenge in existing LLP methods, and point out the minimization on KL divergence between the prior and posterior class distributions is inadequate to comply with the label proportions exactly. From this perspective, we propose a second stage for existing LLP solver with a framework to combine instance-level classification and pseudo labeling, and alternately optimize these two objectives.

Compared with existing LLP solvers, especially [Dulac- Arnold et al., 2019], our improvements are four-fold. First, we introduce exact pseudo labeling to convert the unconstrained KL divergence minimization into a constrained one, so that the labeling can strictly meet the proportions and avoid suboptimal solutions. Second, although the pseudo-labels can be efficiently found by Sinkhorn's algorithm for entropic regularized OT (or linear programming for OT), we instead recognize the resulting supervised learning with pseudo-labels as a noisy label problem, due to the uncertainty introduced by the proportional information. Accordingly, we apply mix-up data augmentation and use SCE instead of CE as the differentiable loss function, which can be minimized with any line search optimizer (e.g., Adam). Third, we propose a two-stage LLP training by integrating PLOT as the second phase, and elaborately demonstrate that our framework can further improve the performance of DLLP, LLP-VAT, and LLP-GAN with extensive experiments, thus is model-agnostic. Lastly, instead of directly using the pseudo-labels, we empirically study the difference between hard and soft labeling strategies, and provide suggestions for practical usage.