Safe Weakly Supervised Learning

1 Introduction

Machine learning has achieved great success in numerous tasks, particularly in supervised learning such as classification and regression. But most successful techniques, such as deep learning [LeCun et al., 2015], require ground-truth labels to be given for a big training data set. It is noteworthy that in many tasks, however, it can be difficult to attain strong supervision due to the fact that the hand-labeled data sets are time-consuming and expensive to collect. Thus, it is desirable for machine learning techniques to be able to work well with weakly supervised data [Zhou, 2017].

Compared to the data in traditional supervised learning, weakly supervised data does not have a large amount of precise label information. Specifically, three types of weakly supervised data commonly exist [Zhou, 2017].

• Incomplete supervised data, i.e., only a small subset of training data is given with labels whereas the other data remain unlabeled. For example, in image categorization, it is easy to get a huge number of images fro the Internet, whereas only a small subset of images can be annotated due to the annotation cost.Representative techniques for this situation are semi-supervised learning [Chapelle et
• al., 2006], which aims to learn a prediction model by leveraging a number of unlabeled data.
• Inexact supervised data, i.e., only coarse-grained labels are given. Reconsider the image categorization task, it is desirable to have every object in the images annotated, however, usually we only have image-level labels rather than object-level labels. One representative technique for this scenario is multi-instance learning [Carbonneau et al., 2018], which aims to improve the performance by considering the coarse-grained label information.
• Inaccurate supervised data, i.e., the given labels have not always been ground-truth. Such situation occurs in various tasks when the annotator is careless or weary, or the annotator is not an expert. For this type of label information, label noise learning techniques are one main paradigm to learn a promising prediction from noisy label [Fr´enay and Verleysen, 2014].

In traditional machine learning, it is often expected that machine learning techniques, such as supervised learning, with the usage of more data will be able to improve learning performance. Such observation, however, no longer holds for weakly supervised learning. There are many studies [Li and Zhou, 2015; Li et al., 2017; Guo and Li, 2018; Oliver et al., 2018] reporting that the usage of weakly supervised data may sometimes lead to performance degradation, that is, the learning performance is even worse than that of baseline methods without using weakly supervised data. More specifically, semi-supervised learning using unlabeled data may be worse than vanilla supervised learning with only limited labeled data [Li and Zhou, 2015; Li et al., 2016]. Multi-instance learning may be outperformed by the naive learning methods which simply assign the coarse-grained label to a bag of instances [Carbonneau et al., 2018]. Label noise learning may be worse than that of learning from a small amount of high-quality labeled data [Fr´enay and Verleysen, 2014]. Such phenomena undoubtedly go against of the expectation of WSL and limits its effectiveness in a large number of practical tasks.

Building a safe WSL, that is to say, WSL using extra weakly supervised data will not be inferior to a simple supervised learning model, it the Holy Grail of WSL [Chapelle et al., 2006; Li and Zhou, 2015; Zhou, 2017]. Since the problem was pointed out in [Cozman et al., 2003], there are many attempts trying to solve this important and challenging problem. In this article, we will review the recent developments on safe WSL, and share our contributions on two aspects of safe WSL:

• For WSL with in-distribution data, we proposed a general ensemble scheme that maximize the performance gain in the worse-case to improve the safeness of WSL.
• For WSL with out-of-distribution (OOD) data, we give a particular focus on SSL with unseen class unlabeled data and propose a bi-level optimization based framework to alleviate the potential performance hurt caused by OOD unlabeled examples.

We will also discuss some open challenges in real-world applications that may have been less noticed and desire more attentions.

2 SafeWSL with In-Distribution Data

WSL with in-distribution data, i.e., all supervised data and weakly supervised data are drawn from a same distribution, is the most natural situation. [Cozman et al., 2003] pointed out that WSL could suffer performance degradation problem with in-distribution data. There are multiple reasons, for example, the adopted assumption of WSL algorithm is not suitable for the data distribution [Chapelle et al., 2006]; there are many candidate large-margin decision boundaries existing in semisupervised support vector machine (SVM) and prior knowledge is insufficient to help choose the best one [Li and Zhou, 2015], and so on.

Some attempts have been devoted to this problem [Li and Zhou, 2015; Loog, 2015; Li et al., 2017; Krijthe and Loog, 2017]. For example, [Li and Zhou, 2015] builds safe semisupervised SVMs through optimizing the worst-case performance gain given a set of candidate low-density separators. [Loog, 2015] proposes to maximize the likelihood gain over a supervised model in the worst-case for generative models. [Balsubramani and Freund, 2015] proposes to learn a robust prediction given that the ground-truth label assignment is restricted to a specific candidate set. [Wei et al., 2018] study safe multi-label learning of weakly labeled data. They optimize multi-label evaluation metrics (F1 score and Top-k precision) given that the ground-truth label assignment is realized by a convex combination of base multi-label learners. More introductions can be found in our recent summary [Li and Liang, 2019].

To address this problem, we propose a general ensemble learning scheme, SAFEW (SAFE Weakly supervised learning) [Li et al., 2021], which learning prediction by integrating multiple weakly supervised learners. Specifically, we propose a maximin framework, which maximize the performance gain in the worse case. Suppose we have obtained b predictions {f1, · · · , fb} generated by baseweakly supervised learners, let f0 denote the prediction of baseline approaches, i.e., directly supervised learning with only limited labeled data. Our ultimate goal is here to derive a safe prediction f = g({f1, · · · , fb}, f0), which often outperforms the baseline f0, meanwhile it would not be worse than f0. In other words, we wold like to maximize the performance gain between our prediction and the baseline prediction.

By assuming that the ground-truth label assignment f ∗ can be realized as a convex combination of base learners, specifically, f ∗ = ∑bi=1 αifi where α = [α1; α2; · · · ; αb] ≥ 0 be the weight of base learners and ∑bi=1 αi = 1, then we have the following objective function:

This is in line with our goal that is to find a prediction f that maximizes the performance gain against the baseline f0.

In practice, however, on may be hard to know about the precise weight of base learners. We further assume that α is from a convex set M to make the proposal more practical, where M captures the priors knowledge about the importance of base learners. Without any further information to locate the weight of base learners, to guarantee the safeness, we aim to optimize the worse-case performance gain, since, intuitively, the algorithm would be robust as long as the good performance is guaranteed in the worst case. Then we obtain a general formulation for weakly supervised data as,

We have the following theorem to guarantees the safeness of our proposal for commonly used convex loss functions in both classification and regression tasks, e.g., hinge loss, cross-entropy loss, mean-square loss, etc.

Theorem 1. Suppose the ground-truth f ∗ can be constructed by base learners, i.e., f ∗ ∈ {f| ∑bi=1 αifi, α ∈ M}. Let ˆf and ˆα be the optimal solution to Eq.(2). We have ℓ(ˆf , f ∗ ) ≤ ℓ(f0, f ∗ ) and ˆf has already achieved the maximal performance gain against f0.

Theorem 1 show that Eq.(2) is a reasonable formulation for our purpose, that is, the derived optimal solution ˆf from Eq.(2) often outperforms f0 and it would not get any worse than f0.

The objective formulation can be globally and efficiently addressed via a simple convex quadratic program or linear program. For example, with mean square loss, the objective can be equivalently written as

where F ∈ Rb×b is a linear kernel matrix of fi's, i.e., Fij = f ⊤ i fj, ∀1 ≤ i, j ≤ b and v = [2f ⊤ 1 f0; . . . ; 2f ⊤ b f0]. Since F is positive semi-definite, Eq.(3) is convex and can be efficiently solved. After solving the optimal solution α∗ , the optimal ¯f = ∑bi=1 α∗ i fi can be obtained.

Moreover, the optimization can be written as a geometric projection problem. Specifically, let Ω = {f | ∑bi=1 αifi, α ∈ M}, ¯f can be rewritten as,

which learns a projection of f0 onto the convex set Ω. Figure 1 illustrates the intuition of our proposed method via the viewpoint of geometric projection.

It is noteworthy that, compared with previous studies in [Li and Zhou, 2015; Balsubramani and Freund, 2015; Li et al., 2017], the SAFEW framework brings multiple advantages to safe WSL. i) It can be shown that the proposal is probably safe as long as the ground-truth label assignment can be expressed as a convex combination of base learners. In contrast to [Li and Zhou, 2015] which requires that the ground-truth is one of the base learners, the condition in Theorem 1 is looser and more practical. ii) Prior knowledge related to the weight of base learners can be easily embedded in this framework. iii) The framework is readily applicable for many loss functions in both classification and regression, which is more general in contrast to [Li et al., 2017] that focuses on regression. iv) The proposed formulation can be globally and efficiently addressed and have intuitive geometry interpretation.

3 SafeWSL with OODData

Previous WSL studies are based on a basic assumption that labeled data and weakly supervised data come from the same distribution. Such an assumption is difficult to hold in many practical applications, among which one common case is that OOD unlabeled data that contains classes that are not seen in the labeled set occurs for SSL. For example, in medical diagnosis, unlabeled medical images often contain different foci from the diseases to be diagnosed. Faced with the OOD weakly supervised data, WSL no longer works well and may even be accompanied by severe performance degradation [Oliver et al., 2018].

Efforts on safe WSL with OOD data remains to be limited. We have made particularly efforts to safe SSL problem and proposes a simple and effective safe deep SSL framework DS3L (Deep Safe Semi-Supervised Learning) [Guo et al., 2020].

Specifically, in SSL scenarios, we are given a set of training data from an unknown distribution, which includes n labeled instances Dl = {(x1, y1), · · · , (xn, yn)} and m unlabeled instances Du = {xn+1, · · · , xn+m}. x ∈ X ∈ RD , y ∈ Y = {1, · · · ,C} where D is the number of input dimension and C is the number of output class in labeled data.

The goal of SSL is to learn a model h(x; θ) : {X;Θ} → Y parameterized by θ ∈ Θ from training data to minimize the generalization risk R(h) = E(X,Y )[ℓ(h(X; θ), Y )], where ℓ : Y × Y → R refers to certain loss function, e.g., mean squared error or cross entropy loss.

The way SSL utilizes unlabeled data structures is usually through the introduction of regularization. The objective of SSL is typically formulated as following:

where Ω(x; θ) refers to the regularization term, e.g., entropyminimization regularization [Grandvalet and Bengio, 2005], consistency regularization [Sohn et al., 2020].

Different from the existing SSL techniques which use all unlabeled data, DS3L uses it selectively and keeps tracking the effect of the supervised learning model to prevent performance hazards. Meanwhile, DS3L uses beneficial unlabeled data as much as possible to improve performance, preventing performance gains from being too conservative.

On one hand, DS3L uses the unlabeled selectively. The main methodology is to design a weighting function w : RD → R parameterized by α ∈ Bd that maps an instance to a weight. Then, DS3L tries to find the optimal ˆ θ(α) that minimizes the corresponding weighted empirical risk,

where ˆ θ(α) is denoted as the model trained with the weight function paramaterized by α.

On the other hand, DS3L keeps tracking supervised performance to prevent performance degradation. Specifically, DS3L requires that the model returned by the weighted empirical risk process should maximize the generalization performance, i.e.,

In real practice, the distribution is unknown, similar to the empirical risk minimization, DS3L tries to find the optimal parameters ˆα such that the model returned by optimizing the weighted instance loss, should also have a good performance on the labeled data which acts as an unbiased and reliable estimation of the underlying distribution, i.e.,

To simplify the notation, we denote ˆ θ(α) as ˆ θ. Taking both the Eq.(6) and Eq.(8) into consideration, the objective of our framework can be formulated as the following bi-level optimization problem,

Eq.(9) can be understood by two stages: first, DS3L seeks the optimal model parameter ˆ θ via the weighted empirical risk minimization, then evaluates it on n labeled instances and optimizes the weight function parameter α to make the learned ˆ θ to achieve better reliable performance. Moreover, the bi-level optimization can be efficiently solved via stochastic gradient descent methods [Ren et al., 2018].

In order to show the safeness of DS3L, we analyze the empirical risk of DS3L compared with the simple supervised method and obtain the following theorem,

Theorem 2. Let θSL be the supervised model, i.e., θSL = argminθ∈Θ ∑ni=1 ℓ(h(xi; θ), yi). Define the empirical risk as:

Then we have the empirical risk of ˆ θ returned by DS3L to be never worse than θSL that is learned from merely labeled data, i.e., ˆR(ˆ θ) ≤ ˆR(θSL).

Theorem 2 reveals that compared with previous SSL methods, DS3L can achieve safeness in terms of empirical risk, i.e., the performance is not worse than its supervised counterpart, with the learned α.

We further analyze the generalization risk of DS3L to better understand the effect of the parameter dimension and the size of labeled data to α and drive the following theorem,

Theorem3. Assume that the loss function is λ-Lipschitz continuous w.r.t. α. Let α ∈ Bd be the parameter of example weighting function w in a d-dimensional unit ball. Let n be the labeled data size. Define the generalization risk as:

Let α∗ = arg maxα∈Bd R(ˆ θ(α)) be the optimal parameter in the unit ball, and ˆα = argmaxα∈A ˆR(ˆ θ(α)) be the empirically optima among a candidate set A. With probability at least 1 - δ we have,

Theorem 3 establishes that DS3L approaches the optimal weight in the order O(√d ln(n)/n). Based on theorem 2 and theorem 3, from both the safeness and generalization, it is reasonable to expect that DS3L can achieve better generalization performance compared with baseline supervised learning methods.

4 Open Problems

Although significant progress has been made in safe WSL with in-distribution data and out-of-distribution data, there still remain many open problems in this area.

• Safe WSL in dynamic environments. Learning in dynamic environments is far more difficult than in static ones. The challenges come from distribution drift, new class emerging, feature space change, and so on. There are some studies trying to tackle these problems [Da

et al., 2014], however, the issue of safeness remains an open problem for weakly-supervised learning in dynamic environments, e.g., an interesting problem is when the unlabeled data are useful in online learning.

• Automated safe WSL [Feurer et al., 2015]. AutoML, which seeks to build an appropriate machine learning model for an unseen dataset in an automatic manner (without human intervention), has received increasing attention recently. However, existing AutoML systems focus on supervised learning, and existing AutoML techniques could not directly be used for the automated WSL problem. Efforts on automated WSL, remain limited right now. Automated WSL introduces some new challenges, e.g., various meta-features extracted from limited number of supervised data are no longer available and suitable; the use of auxiliary weakly supervised examples may sometimes even be outperformed by direct supervised learning. Therefore, safeness if one of the crucial aspects of AutoWSL, since it is not desirable to have an automated yet performance degenerated WSL system. [Li et al., 2019] first present an automated learning system for SSL. They incorporate metalearning with enhanced meta-features to help searching well-perform instantiations, and a large margin separation method to fine-tune the hyper-parameters as well as alleviate performance deterioration. More efforts are expected to be devoted to this direction.
• Safe deep WSL. Although we have introduced SAFEW and other related methods that aim to solve the safe WSL problemwith in-distribution data. However, current safe WSL studies typically work on shallow models such as support vector machines, logistic regression, linear regression, etc. Applying WSL techniques to deep neural networks has attracted much attention in recent years for the promising results achieved by deep models. However, studies of safe WSL with deep neural networks remain to be limited. It is expected to design an efficient scheme for safe deep WSL.
• Safe imbalanced WSL. Previous WSL studies typically assume a balanced class distribution in both labeled sets and unlabeled sets. However, it is well-known that realworld dataset is often imbalanced or long-tailed. The performance of previous WSL studies is seriously decreased when the class distribution is imbalanced since their predictions are biased toward majority classes and result in low recall on minority classes [Kim et al., 2020]. There are some efforts begin to address the imbalanced SSL problem [Kim et al., 2020]. But how to achieve safe performance for imbalanced WSL is still under study and remains an open problem.

Acknowledgments

This work was partially supported by NSFC (61772262), and the Collaborative Innovation Center of Novel Software Technology and Industrialization. The author would like to thanks Lan-Zhe Guo for improving the paper.