Pierre Nodet

Vincent Lemaire

Alexis Bondu

Antoine Cornuéjols

Biquality Learning: a Framework to Design Algorithms Dealing with Closed-Set Distribution Shifts

Keywords: Biquality Learning, Distribution Shift, Weakly Supervised Learning, Dataset Shift, Machine Learning

Training machine learning models from data with weak supervision and dataset shifts is still challenging. Designing algorithms when these two situations arise has not been explored much, and existing algorithms cannot always handle the most complex distributional shifts. We think the biquality data setup is a suitable framework for designing such algorithms. Biquality Learning assumes that two datasets are available at training time: a trusted dataset sampled from the distribution of interest and the untrusted dataset with dataset shifts and weaknesses of supervision (aka distribution shifts). The trusted and untrusted datasets available at training time make designing algorithms dealing with any distribution shifts possible. We propose two methods, one inspired by the label noise literature and another by the covariate shift literature for biquality learning. We experiment with two novel methods to synthetically introduce concept drift and class-conditional shifts in real-world datasets across many of them. We opened some discussions and assessed that developing biquality learning algorithms robust to distributional changes remains an interesting problem for future research.

Introduction

Supervised machine learning has been studied and explored extensively during the last decades, and both theoretical and experimental solutions exist to accomplish this task [START_REF] Hastie | The elements of statistical learning: data mining, inference, and prediction[END_REF]. Weakly supervised machine learning (WSL) has not reached this state yet. WSL is the machine learning field where algorithms learn a model from data with weak supervision instead of strong supervision. Multiple weak supervisions have been identified in [START_REF] Zhou | A brief introduction to weakly supervised learning[END_REF] such as inaccurate supervision when samples are mislabeled, inexact supervision when labels are not adapted to the classification task, or incomplete supervision when labels are missing which reflects the inadequacy of the available labels in the real world. For every kind of weak supervision, assumptions are needed to design sound algorithms, especially on the corruption model, the generative process behind the weakness of supervision.

Weaknesses in supervision are one facet of weakly supervised learning, and dataset shifts are another. Dataset shifts happen when the data distribution observed at training time is different from what is expected from the data distribution at testing time [START_REF] Moreno-Torres | A unifying view on dataset shift in classification[END_REF]. This distribution change can take multiple forms, such as a change in the distribution of a single feature, a combination of features, or the concept to be learned. Thus, the common assumption that the training and testing data follow the same distributions is often violated in real-world applications. Again, designing algorithms to handle dataset shifts usually requires assumptions on the nature of the shift [START_REF] David | Impossibility theorems for domain adaptation[END_REF].

We believe that the biquality data setup proposed in [START_REF] Nodet | Importance reweighting for biquality learning[END_REF] is a suitable framework to design algorithms capable of handling both dataset shifts and weaknesses of supervision simultaneously.

Biquality Learning assumes that two datasets are available at training time: a trusted dataset D T and an untrusted dataset D U both composed of labeled samples (x i , y i ) ∈ X × Y. These datasets share the same features X T = X U and the same set of labels Y T = Y U , having a closed-set of features X and labels Y with K = |Y| classes. However, the two datasets differ in terms of the joint distribution P T (X, Y ) ̸ = P U (X, Y ) where the trusted distribution is the distribution of interest.

In practice, it is often the case that the trusted dataset is not large enough to learn an efficient model to estimate P T (X, Y ). By contrast, it is generally easy to get a large enough untrusted dataset that enables to correctly estimate P U (X, Y ). However, this data distribution could be completely different from the one of interest, P T (X, Y ). In the biquality data setup, there is no assumption on the difference in joint distribution between the two datasets, and it can cover a wide range of known problems. From the Bayes Formula: P(X, Y ) = P(X | Y )P(Y ) = P(Y | X)P(X) The Biquality Data setup typically occurs in three scenarios in practice.

1. The first scenario corresponds to the case where annotating samples is expansive to the point of being prohibitive to label an entire dataset, but labeling a small part of the dataset is doable. It is typically the case in Fraud Detection and in Cyber Security where labeling samples require complex forensics from domain experts. There, the rest of the dataset is usually labeled by hand-engineered rules which might not perfectly fit the classification task and the labels can not properly be trusted [START_REF] Ratner | Snorkel: Rapid training data creation with weak supervision[END_REF]. 2. The second scenario happens when there are data shifts during the labeling process over the course of time. For example in MLOps [START_REF] Kreuzberger | Machine learning operations (mlops): Overview, definition, and architecture[END_REF], when a model is first learned on clean data and then deployed in production, predictions can be used to learn an updated model [START_REF] Veeramachaneni | Ai2: Training a big data machine to defend[END_REF]; these predictions may be faulty and need to be dealt with. A second example in MLOps occurs when newly clean data is acquired to retrain a deployed model; the most recent clean data is considered trusted and the old clean data is considered untrusted when dataset shifts occurred [START_REF] Gama | A survey on concept drift adaptation[END_REF]. 3. The third scenario occurs when multiple annotators are responsible for dataset labeling. In natural language processing (NLP) products, for example, multiple annotators follow labeling guidelines to annotate verbatims. The efficiency of annotators to follow these guidelines may vary and might not be trusted. However, if one annotator can be trusted, all the other annotators can be set as untrusted and the biquality data setup may apply. Especially, considering each untrusted annotator against the trusted annotator can be viewed as a biquality learning task [START_REF] Yuen | A survey of crowdsourcing systems[END_REF].

Having the trusted and untrusted datasets available at training time makes it possible to design algorithms dealing with closed-set distribution shifts. If algorithms designed for biquality data with concept drift only have been explored recently [START_REF] Nodet | From Weakly Supervised Learning to Biquality Learning: an Introduction[END_REF], algorithms that deal with distribution shift are still behind. In this paper, we propose two biquality approaches that adapt methods from either the covariate shift literature or the concept drift literature in order to deal with both corruptions simultaneously.

Multiple biquality learning algorithm designs have been identified in [START_REF] Nodet | Importance reweighting for biquality learning[END_REF]. They have been divided into three main families based on how they modify instances to correct the global learning procedure. Untrusted instances can be (i) relabeled correctly, (ii) modified in the feature space, or (iii) reweighted such that the untrusted dataset seems sampled from the trusted distribution P T (X, Y ). We propose here two corresponding algorithms for the third case of importance reweighting.

In Section 2, a brief state-of-the-art relates what has already been achieved in biquality learning. Then, Section 3 further focuses on the state-of-the-art of importance reweighting on biquality learning. Section 4 and Section 5 introduce our proposals to use classifiers to reweight untrusted instances for biquality learning with distribution shifts. Then, Section 6 describes the experiments that evaluate the efficiency of our proposed approaches on real datasets and corruptions. Section 7 presents the results of the proposed experiments. Finally, Section 8 open some discussions about the presented results before concluding.

Related work

Machine learning algorithms on biquality data have been developed in many different sub-domains of weakly supervised learning. Some of these sub-domains are robust learning to label noise, learning under covariate shift, or transfer learning. Because these subdomains expect different corruptions, not all algorithms designed for some subcases of biquality learning will work in a more general setting with distribution shifts.

For example, Gold Loss Correction (GLC) [START_REF] Hendrycks | Using trusted data to train deep networks on labels corrupted by severe noise[END_REF] and Importance Reweighting for Biquality Learning (IRBL) [START_REF] Nodet | Importance reweighting for biquality learning[END_REF] are algorithms designed to specifically deal with a concept drift between the trusted and the untrusted datasets. GLC, on the one hand, corrects the learning procedure on the untrusted dataset using a noise transition matrix between the trusted and untrusted concept. IRBL, on the other hand, reweight untrusted instances using an estimation of the ratio of both concepts. These algorithms are not theoretically designed to handle covariate shift; nevertheless, they could be empirically efficient on this task and serve as a reference.

Another group of algorithms, such as Kernel Mean Matching (KMM) [START_REF] Gretton | Covariate shift by kernel mean matching[END_REF], and Probabilistic Density Ratio Estimation (PDR) [START_REF] Bickel | Discriminative learning for differing training and test distributions[END_REF], only deals with covariate shift between the two datasets. These algorithms seek to reweight untrusted instances such that the distribution of features between the two datasets is equivalent. KMM minimizes the difference of the features mean in a reproducing kernel Hilbert space. PDR learns the classification task of predicting if an instance is untrusted or not and uses the predicted probability of being an untrusted instance as the weight. These algorithms are not designed to handle concept drift and will serve as references too.

However, a recent proposal aims to adapt these algorithms to the biquality framework with distribution shift [START_REF] Fang | Rethinking importance weighting for deep learning under distribution shift[END_REF]. They proposed to use one density ratio estimation algorithm per class, which, when combined, corrects the distribution shift. They also proposed to transform the joint density ratio estimation problem by combining the features and labels of the data into a new feature space that allows for a single density ratio estimation algorithm. These adapted algorithms will also serve as competitors.

Finally, recent approaches such as Learning to Reweight (L2RW) [START_REF] Ren | Learning to reweight examples for robust deep learning[END_REF], or Meta-Weight-Net (MWNet) [START_REF] Shu | Meta-weight-net: Learning an explicit mapping for sample weighting[END_REF] based on deep learning and meta-learning have not been tested in this paper. Indeed, they require a class of algorithms with a differentiable and incremental learning procedure that does not fit most popular families of classifiers, such as gradient boosting trees. They are left to be tested in future works.

Biquality Data is not a new setup per see, as previous work exists on this setup going back to [START_REF] Jiang | Mentornet: Learning datadriven curriculum for very deep neural networks on corrupted labels[END_REF] to the best of our knowledge. Each previous work was carried out in different sub-domains of weakly supervised learning and thus achieved different goals based on different setups [START_REF] Hendrycks | Using trusted data to train deep networks on labels corrupted by severe noise[END_REF][START_REF] Shu | Meta-weight-net: Learning an explicit mapping for sample weighting[END_REF][START_REF] Ren | Learning to reweight examples for robust deep learning[END_REF][START_REF] Zheng | Meta label correction for noisy label learning[END_REF][START_REF] Jiang | Mentornet: Learning datadriven curriculum for very deep neural networks on corrupted labels[END_REF]. These setups used different terms, definitions, hypotheses, and requirements but still sought to solve the same fundamental problem of biquality learning. Only recently, some efforts have been done to provide clear and concise definitions of the biquality learning framework [START_REF] Nodet | Importance reweighting for biquality learning[END_REF]. We propose in this paper to extend it to include dataset shifts. This extension is, to the best of our knowledge, a new problem to tackle that few tried already [START_REF] Fang | Rethinking importance weighting for deep learning under distribution shift[END_REF], limiting existing prior literature.

Reweighting for distribution shift

The previous Section introduced the most common algorithms used in machine learning for biquality data. Most of them are based on instance reweighting, and specifically, on estimating the Radon-Nikodym Derivative (RND) [START_REF] Nikodym | Sur une généralisation des intégrales de m. j. radon[END_REF] of P T (X, Y ) with respect to P U (X, Y ).

Theorem 1 (Radon-Nikdoym-Lebesgue theorem [START_REF] Rudin | Analyse réelle et complexe[END_REF]). Let µ and ν two positive σ-finite measures defined on a measurable space (X, A) with ν being absolutely continuous with respect to µ. Then there exists a unique positive measurable function f defined on X such that:

∀A ∈ A, ν(A) = A f dµ (2)
Typically, machine learning datasets form measurable spaces, and probability densities are positive finite measures on these measurable spaces. Assuming that P T (X, Y ) is absolutely continuous with respect to P U (X, Y ), then the RND exists, is unique and equals to dP T (X,Y ) dP U (X,Y ) . Equation 3shows that minimizing the reweighted empirical risk by the RND on the untrusted data is equivalent to minimizing the empirical risk on trusted data.

R (X,Y )∼T,L (f ) = E (X,Y )∼T [L(f (X), Y )] = L(f (X), Y ) dP T (X, Y ) = dP T (X, Y ) dP U (X, Y ) L(f (X), Y ) dP U (X, Y ) = E (X,Y )∼U [ P T (X, Y ) P U (X, Y ) L(f (X), Y )] = E (X,Y )∼U [βL(f (X), Y )] = R (X,Y )∼U,βL (f ) (3)
However, estimating the RND can be a difficult task, especially in the case of distribution shift where the joint distribution ratio β needs to be estimated. Proposals have been made to ease this estimation.

A first proposal has been made in IRBL [START_REF] Nodet | Importance reweighting for biquality learning[END_REF] which focused first on the concept drift between datasets using the Bayes Formula:

β(X, Y ) = P T (X, Y ) P U (X, Y ) = P T (Y | X)P T (X) P U (Y | X)P U (X) (4)
Their proposed algorithm is based on the decomposition of the joint density ratio estimation task into three sub-tasks. The first one is to estimate the trusted concept P T (Y | X), and is done by learning a classifier on the trusted dataset. The second task is to estimate the untrusted concept P U (Y | X), which is done by learning a classifier on the untrusted dataset. And the third task about density ratio estimation P T (X) P U (X) was skipped as no covariate shift was introduced in their benchmark, but it is a well known and solved machine learning task [START_REF] Sugiyama | Density ratio estimation in machine learning[END_REF].

A second proposal has been made in [START_REF] Fang | Rethinking importance weighting for deep learning under distribution shift[END_REF] which focused on the covariate shift between datasets using the Bayes Formula differently:

β(X, Y ) = P T (X, Y ) P U (X, Y ) = P T (X | Y )P T (Y ) P U (X | Y )P U (Y ) (5)
In their proposed algorithm, the joint density ratio estimation task has been decomposed into K-tasks where K is the number of classes to predict. For each class, only samples of the given class are selected on both datasets, such that the samples are drawn from the P(X | Y ) distribution. Then, a density ratio estimation procedure usually employed to estimate P T (X) P U (X) is learned on these sub-datasets to estimate P T (X|Y ) P U (X|Y ) , effectively handling distribution shift from Equation 5. As it uses K density ratio algorithms, this generic approach will be named K-DensityRatio (K-DR) in the rest of the paper.

Finally, a last approach is to focus on the density ratio estimation task by finding a deterministic and invertible transformation f as proposed in [START_REF] Fang | Rethinking importance weighting for deep learning under distribution shift[END_REF]:

β(X, Y ) = P T (X, Y ) P U (X, Y ) = P T (Z) P U (Z) , Z = f (X, Y ) (6)
An example of such transformation [START_REF] Fang | Rethinking importance weighting for deep learning under distribution shift[END_REF] is the classification loss of a model learned on the biquality data. One density ratio estimation procedure is done on these new features Z to directly estimate P T (Z) P U (Z) . IRBL has experimentally proved to efficiently solve the biquality learning task on tabular data [START_REF] Nodet | Importance reweighting for biquality learning[END_REF]. However, the experiments were conducted on corruptions only affecting the untrusted concept P(Y | X) and not the joint distribution P(X, Y ). We propose here to adapt IRBL to handle distribution shifts by solving the third task of density ratio estimation with a probabilistic classifier. Moreover, we propose a new version of K-DR using probabilistic classifiers to solve the K density ratio estimation tasks. This proposition is driven by the desire to reuse efficient tricks from IRBL and to rely on a non parametric approach by contrast to the original proposal [START_REF] Fang | Rethinking importance weighting for deep learning under distribution shift[END_REF].

First proposed approach: IRBL2

Importance Reweighting for Biquality Learning (IRBL) [START_REF] Nodet | Importance reweighting for biquality learning[END_REF] is a biquality learning algorithm designed to handle closed-set concept-drift. The algorithm is based on using two probabilistic classifiers: first, to estimate both concepts P T (Y | X) and P U (Y | X) and, second, using these classifiers' outputs to estimate the RND between both data distributions. In the particular case of label noise, especially instance dependent label noise, it has been shown to be the best approach experimentally on a wide variety of datasets.

We propose to adapt it to handle covariate shift by estimating the ratio

P T (X)
P U (X) by using a third probabilistic classifier based on Discriminative Learning [START_REF] Bickel | Discriminative learning for differing training and test distributions[END_REF]. This algorithm works by defining a new supervised classification task by learning to predict if a sample is trusted or untrusted by only using its features.

If there exists covariate shift between the datasets, the classifier should be able to discriminate between the two datasets.

Let's introduce S as the new target:

s i (x i ) = 0, if x i ∈ D U 1, if x i ∈ D T (7)
Estimating P(S | X) allows us to estimate P T (X) P U (X) directly without estimating both distributions:

P T (X) P U (X) = P(X | S = 1) P(X | S = 0) = P(S = 1 | X)P(X) P(S = 1) × P(S = 0) P(S = 0 | X)P(X) = P(S = 1 | X) 1 -P(S = 1 | X) × 1 -P(S = 1) P(S = 1) (8)
Combining Equation 4and 8 :

P T (Y | X)P T (X) P U (Y | X)P U (X) = P T (Y | X) P U (Y | X) × P(S = 1 | X) 1 -P(S = 1 | X) × 1 -P(S = 1) P(S = 1) (9)
We propose to estimate Equation 9 by learning probabilistic classifiers f ∈ F to estimate each of its terms. A probabilistic classifier f T is learned on

D T to estimate P T (Y | X), f U is learned on D U to estimate P U (Y | X), and f S is learned on {(x, s(x)) | ∀x ∈ D T ∪ D U } to estimate P U (S | X), leading to the following Algorithm 1.
Algorithm 1: Importance Reweighting for Biquality Learning 2 (IRBL2)

Input: Trusted Dataset DT , Untrusted Dataset DU , Probabilistic Classifier Family F Learn fU ∈ F on DU Learn fT ∈ F on DT Learn fS ∈ F on {(x, s(x)) | ∀x ∈ DT ∪ DU } for (xi, yi) ∈ DU do β(xi, yi) = f T (x i )y i f U (x i )y i f S (x i ) 1 |D T | |D U | f S (x i ) 0 for (xi, yi) ∈ DT do β(xi, yi) = 1
Learn f ∈ F on DT ∪ DU with weights β Output: f 5 Second proposed approach: K-PDR K-DensityRatio (K-DR) [START_REF] Fang | Rethinking importance weighting for deep learning under distribution shift[END_REF] is an alternative approach to design a biquality learning algorithm able to handle distribution shift. The focus is made on the covariate shift between the two datasets. It handles the covariate shift in a class conditional fashion to deal with distribution shifts by using covariate shift correction once per class.

From Equation 5, K-DR evaluates the ratio P T (X|Y ) P U (X|Y ) with density ratio estimation algorithms. To do so, it first samples data from the X | Y distribution by selecting only samples from a given class k ∈ [ [1, K]] in both datasets D T and D U . Then, it uses density ratio estimation algorithms e ∈ E on these subdatasets to estimate P T (X|Y =k) P U (X|Y =k) independently k times. The class priors P T (Y ) and P U (Y ) are estimated empirically from both training sets. See Algorithm 2.

Algorithm 2: K-DensityRatio (K-DR)

Input: Trusted Dataset DT , Untrusted Dataset DU , Density Ratio Estimator Family E, Probabilistic Classifier Familiy F for k ∈ [[1, K]] do Let D k T = {∀(x, y) ∈ DT | y = k} Let D k U = {∀(x, y) ∈ DU | y = k} Learn e k ∈ E on D k T and D k U for (xi, yi) ∈ DU do β(xi, yi) = e y i (xi) |D y i T | |D T | |D U | |D y i U | for (xi, yi) ∈ DT do β(xi, yi) = 1 Learn f ∈ F on DT ∪ DU with weights β Output: f
In [START_REF] Fang | Rethinking importance weighting for deep learning under distribution shift[END_REF] Kernel Mean Matching (KMM) [START_REF] Huang | Correcting sample selection bias by unlabeled data[END_REF][START_REF] Gretton | Covariate shift by kernel mean matching[END_REF] has been used as the Density Ratio algorithm e to handle covariate shift. Empirically, KMM is an algorithm that matches with quadratic programming [START_REF] Wright | Continuous optimization (nonlinear and linear programming)[END_REF] the mean of both datasets in a feature space induced by a kernel k on the domain X × X :

min βi 1 |D U | |D U | i=0 β i Φ(x i ) - 1 |D T | |D T | i=0 Φ(x i ) H s.t. 0 ≤ β i ≤ B 1 |D U | |D U | i=0 β i -1 < ϵ (10)
where Φ : X → H denotes the canonical feature map, H is the reproducing kernel Hilbert space induced by the kernel k, | • | H is the norm on H and B and ϵ are regularization and normalization constraints.

As such, KMM is a parametric algorithm based on kernels. We propose to use instead a probabilistic classifier to handle covariate shift, in the same fashion as in Equations 7 and 8 to make a non-parametric version of K-DR as shown in Equation 8.b.

P T (X | Y )P T (Y ) P U (X | Y )P U (Y ) = P(X | Y, S = 1) P(X | Y, S = 0) × P(Y | S = 1) P(Y | S = 0) = P(S = 1 | X, Y )P(X, Y ) P(Y | S = 1)P(S = 1) × P(Y | S = 0)P(S = 0) P(S = 0 | X, Y )P(X, Y ) × P(Y | S = 1) P(Y | S = 0) = P(S = 1 | X, Y ) 1 -P(S = 1 | X, Y ) × 1 -P(S = 1) P(S = 1) (8.b)
The main advantage of the non-parametric approach is that it does not require assumptions about the data distribution, which may not be satisfied in many real-world datasets and could lead to poor performances. Moreover, the scalability of K-PDR is better than the scalability of K-KMM both in space and time complexity. K-PDR has K times the same complexity as the complexity of learning the chosen probabilistic classifier, which is

O(K × |X | × |D k u | log(|D k u |)) for Decisions Trees [6]. Meanwhile, K-KMM memory complexity is O(|D k u | 2 + |D k u | × |D k t |)
to sequentially build matrices necessary for the quadratic program, and a worst-case time complexity of O(K ×|D k u | 3 ) to solve the quadratic program [START_REF] Ye | An extension of karmarkar's projective algorithm for convex quadratic programming[END_REF]. Finally, the proposed approach is even more flexible than the previous one, as any family of machine learning classifiers could be used instead of kernels. This leads to Algorithm 3. Algorithm 3: K-Probabilistic Density Ratio (K-PDR)

Input: Trusted Dataset DT , Untrusted Dataset DU , Probabilistic Classifier Familiy F for k ∈ [[1, K]] do Let D k T = {∀(x, y) ∈ DT | y = k} Let D k U = {∀(x, y) ∈ DU | y = k} Learn f k S ∈ F on {(x, s(x)) | ∀x ∈ D k T ∪ D k U } for (xi, yi) ∈ DU do β(xi, yi) = f y i S (x i ) 1 f y i S (x i ) 0 |D U | |D T | for (xi, yi) ∈ DT do β(xi, yi) = 1 Learn f ∈ F on DT ∪ DU with weights β Output: f 6 Experiments
Benchmarking biquality learning algorithms means evaluating their efficiency and resilience on both dataset shifts and weaknesses of supervision in a joint manner. Introducing these corruptions synthetically in usual public multi-class classification datasets allows a fine-grained and controlled evaluation of these algorithms.

From Equation 1, introducing distribution shift can be done in four ways: by introducing covariate shift, concept drift, class-conditional shift, or prior shift. Especially modifying both concept drift and covariate shift or class-conditional shift and prior shift at the same time leads to particularly complex distribution shifts. Table 1 sums up the hierarchy of distribution shift sources. We chose two methods to synthetically generate distribution shifts, one in each sub-tree of distribution shift sources: concept drift and class-conditional shift. We propose two novel ways to generate such shifts in real-world datasets that are detailed in the following Subsection 6.1 and Subsection 6.2.

Concept Drift

Concept drift corresponds to changes in the decision boundary P(Y | X) of a classifier in some parts of the feature space X .

To synthetically generate concept drift in real-world datasets, we propose to model the feature space with a Decision Tree classifier [START_REF] Breiman | Classification and regression trees[END_REF] learned on the original dataset D, such that each leaf of the decision tree will correspond to a patch of the dataset grid. By restricting the minimum samples per leaf in the decision tree, here set as 10% of the dataset per class, we will be able to control the finesse of the grid.

Then in each leaf of the decision tree, we are going to change the class distribution, essentially by generating noisy labels Ỹ from clean labels Y thanks to a transition matrix T, such that

∀(i, j) ∈ [[1, K]] 2 , T i,j = P( Ỹ = j | Y = i).
We chose to restrict the transition matrix to a permutation matrix P, meaning that each clean class will be associated in a bijective way with a noisy class, different from the clean class. These permutation matrices P will be generated randomly once per dataset. For example, for three-class classification, one of these permutation matrices could be the following:

P =   0 1 0 0 0 1 1 0 0  
To decide how much concept drift will occur, we rank the leaves in the decision tree by their purity, starting from the purest leaves, and chose enough leaves such that r% of the untrusted dataset fall in these leaves. These samples will be given a noisy label, and the rest of the samples will be left untouched.

The benefits of this methodology are twofold:

-Having all samples assigned the same noisy label given their class in a whole subspace of the feature space will avoid the class overlap usually created with uniform (completely at random) label noise. -Choosing to add label noise in the purest leaves of the decision tree first creates new patterns in otherwise completely clean and easy parts of the dataset.

Class-Conditional Shift

Class-conditional shift corresponds to changes in the feature distribution P(X), with different changes per class P(X | Y ).

To synthetically generate class-conditional shift in a real-world dataset, we propose to split the original dataset

D into sub-datasets D k , such that ∀k ∈ [[1, K]], D k = {(x, y) ∈ D | y = k},
where D k corresponds to samples from the same class k out of all the classes K.

For each sub-dataset, we train a K-Means [START_REF] Lloyd | Least squares quantization in pcm[END_REF] clustering to learn a division of the feature space X given the class k. The number of clusters is chosen by cross-validation to maximize the average silhouette score [START_REF] Rousseeuw | Silhouettes: A graphical aid to the interpretation and validation of cluster analysis[END_REF].

Then we sub-sample some of these clusters to modify the class-conditional distribution P(X | Y = k). We sort the clusters by their size and separate them in two groups of equal size. The group formed by the smallest clusters will be subsampled according to a subsampling ratio ρ. The group formed by the biggest clusters will be left untouched. For example, if the number of clusters for a class is 4 and ρ = 10, the two smallest clusters will be subsampled by a ratio of 10, the two biggests will not be subsampled.

A higher ρ will lead to more data being missing in the untrusted dataset, especially samples in sparse regions of the feature space, represented by small clusters.

The final size of the untrusted dataset relative to the non-sub-sampled untrusted dataset is reported for each scenario in Table 5 in the Appendices.

Illustration on a Toy Dataset

We propose to first see the experimental protocol on a toy dataset with two features to visualize better how the corruption mechanisms will act. We chose the two moons dataset, composed of two croissant-shaped classes that are almost linearly separable.

Figure 1 shows that a Support Vector classifier [START_REF] Boser | A training algorithm for optimal margin classifiers[END_REF] with a Polynomial kernel of degree 3 can adequately separate the two classes. Now we can apply our synthetic corruptions to this dataset and see the effect on the decision boundary of the Support Vector classifier.

The proposed synthetic corruptions affect the learned decision boundary of the Support Vector classifier but each in their own way. The concept drift dramatically changes the decision boundary, and the classifier cannot recognize the two original croissants illustrated in Figure 2. Instead, it emphasizes the new class patterns created with the noisy patches. The class-conditional shift, however, does not inherently change the shape of the decision boundary. We can still see that the classifier somewhat separates the two croissants. However, the margin is way tighter on the yellow croissant. This classifier would fail to classify some data points that would be considered out-of-distribution for the corrupted dataset but completely normal in the original dataset. Now that we verified that the synthetic corruptions produce the expected effects on classifiers, we can look at how the previous method of the state-ofthe-art can correct these corrupted datasets, especially IRBL and PDR that are expected to work only on concept drift or covariate shift, and our two proposed algorithm, IRBL2, and K-PDR, that should work on distribution shifts. We propose to keep 5% of the origin two moons dataset as trusted data that will be left untouched and corrupt the rest of the dataset with both corruptions. and with a more transparent color. The markers' sizes are proportional to the weights given by the corresponding algorithm.

In Figure 3, we can see the limitations of IRBL and PDR. IRBL can detect samples belonging to the wrong part of the feature space given their label but cannot take into account the uncertainty of some patches of the feature space that are not present in the trusted dataset. For example, in the top part of the dataset, there is a zone where no trusted points exist for the purple moon. IRBL do not takes that into account and re-weights equally all these, as long as they are from the correct color, purple. Meanwhile, PDR does re-weight the samples differently depending if they belong to the trusted distribution, but indifferently depending on the sample color.

In the second part of Figure 3, we can observe that IRBL2 and K-PDR can handle both cases and, thus, distribution shift. Their re-weighting schemes are reasonably similar, and to assess which one is better, we need to benchmark them on a broader range of real-world datasets.

Datasets

We randomly picked supervised classification datasets, see Table 2, from different sources: UCI [START_REF] Dua | Uci machine learning repository[END_REF], libsvm [START_REF] Chang | Libsvm: a library for support vector machines[END_REF], active learning challenge [START_REF] Guyon | Datasets of the active learning challenge[END_REF] and openML [START_REF] Vanschoren | Openml: Networked science in machine learning[END_REF]. A part of these datasets comes from past challenges in active learning, where high performances with a low number of labeled samples have proved challenging to obtain, which makes leveraging the untrusted dataset necessary. With this choice of datasets, an extensive range of class ratios, number of classes, number of features, and dataset sizes are covered. Each dataset is first jumbled, then split in a stratified fashion with 80% of samples used for training set, and 20% used for the test set.

Each training set is again split in a stratified fashion into a trusted and untrusted set with a ratio of trusted p. To find a ratio of trusted data that is coherent between all datasets, we compute a learning curve on the training set and choose a ratio of trusted data such that the classifier's performance is equal to p% of the classifier learned on the entire training set. The actual ratio of trusted data for each dataset is provided in Table 4 in the Appendices.

Finally, we synthetically corrupt the untrusted set with the methods described earlier in this Section.

Competitors

We compare IRBL2 and K-PDR against multiple state-of-the-art competitors and baselines :

-K-KMM, the original version of K-DR using KMM as proposed in [START_REF] Fang | Rethinking importance weighting for deep learning under distribution shift[END_REF]; -IRBL [START_REF] Nodet | Importance reweighting for biquality learning[END_REF], which is IRBL2 without covariate shift correction; -PDR [START_REF] Bickel | Discriminative learning for differing training and test distributions[END_REF] the covariate-shift only baseline; -Trusted-Only baseline, when the model is learned using only the trusted dataset; -No-Correction baseline, when the model is learned on both datasets without correction applied.

For every competitors, we use the same probabilistic classifier family, histogrambased gradient boosting (HGBT) trees [START_REF] Ke | Lightgbm: A highly efficient gradient boosting decision tree[END_REF] from Scikit-Learn [START_REF] Pedregosa | Scikit-learn: Machine learning in python[END_REF] with their default hyperparameters, each time an algorithm required a base classifier. When it required a well-calibrated classifier, the HGBT trees where calibrated thanks to an Isotonic Regression [START_REF] Zadrozny | Obtaining calibrated probability estimates from decision trees and naive bayesian classifiers[END_REF] from Scikit-Learn using Zadrozny's heuristic [START_REF] Zadrozny | Transforming classifier scores into accurate multiclass probability estimates[END_REF] for multiclass calibration.

For KMM and K-KMM we use the Radial Basis Function (RBF) kernel [START_REF] Vert | A primer on kernel methods[END_REF] with the default γ = 1 |X | value from Scikit-Learn. In order to scale KMM to the bigger datasets, we used an ensembling version [START_REF] Miao | Ensemble kernel mean matching[END_REF] of the original KMM algorithm with a batch size of 100.

Results

We conducted the previously defined experiments of the proposed datasets with the label noise strength r varying from 0% to 50% of the dataset and the maximum cluster subsampling ρ from 1 to 100. We also tested three different values for the ratio of trusted data p equals to 25%, 50%, and 75%. The predictive performance we used in these experiments is Cohen's kappa coefficient κ [START_REF] Cohen | A coefficient of agreement for nominal scales[END_REF]. It is a measure of agreement between assignments relative to the agreement between two random assignments and is fitted to evaluate classifier performance in unbalanced settings. Before looking at the whole grid of experiments over r and ρ, we can look at the two axes independently to independently analyze the impact of concept drift and class-conditional shift.

The primary metric to analyze to assess the efficiency of biquality learning algorithms is the evolution of the predictive performance κ given the corruption strength (ρ or r). For example, having a constant predictive performance given the corruption strength means being robust to this corruption.

We propose to illustrate this function by plotting the averaged predictive performance over all datasets for all tested corruption strength and ratio of trusted data.

Figure 4 shows that with very few trusted data, p = 0.25, biquality-learning algorithms have trouble differentiating themselves from one another and with baselines, showing their limitations on low trusted data regimes. However, p = 0.25 leads to having around only thousandths of the data as trusted, which we consider to be a particularly pessimistic scenario in practice. With more trusted data, some competitors start to pull apart, especially K-PDR on classconditional shift and IRBL and IRBL2 on concept drift.

In order to summarize these plots, we propose to compute the area under the curve (AUC) of the previous error curves, which is primarily a fancier average when the data points are not evenly spaced. This AUC is then normalized by the domain length we integrate the curve on. Table 3 mostly confirmed what could be observed in Figure 4, but more particularly highlights the mere improvements brought by IRBL2 over IRBL with both corruptions.

As the previous comparison are made using averaged predictive measures that might not be relatable from one dataset to the other, we propose in a second time to compute the average ranking instead thanks to critical diagrams presented in Figure 5 as a more robust way to compare competitors.

The Nemenyi test [START_REF] Nemenyi | Distribution-free multiple comparisons[END_REF] is used to rank the approaches in terms of AUC of the predictive metric over the corruption strength. The Nemenyi test consists of two successive steps. First, the Friedman test is applied to the AUC of competing approaches to determine whether their overall performance is similar. Second, if not, the post-hoc test is applied to determine groups of approaches whose overall performance is significantly different from that of the other groups. Figure 5 confirms all previous observations. K-PDR seems to be the best approach on class-conditional noise but is still somewhat robust to label noise, especially at medium and high levels of trusted data ratio as its able to detach from PDR in terms of average rank in these situtations. IRBL and IRBL2 seem to be the best approaches for learning with label noise, even though they struggle with a low ratio of trusted data. However, IRBL2 struggles to improve IRBL performances on class-conditional shifts.

Finally, to study the combined effect of both axes, we extend the experiments on a grid with varying strength of label noise r and sub-sampling ρ.

Figure 6 presents six graphics, each reporting the Wilcoxon test that evaluates one competitor against another based on the accuracy over all datasets. These graphics form a grid with the horizontal axis representing the label noise strength r and the vertical axis representing the sub-sampling ratio ρ. On each point of a grid (r, ρ), a Wilcoxon rank-signed test [START_REF] Wilcoxon | Individual comparisons by ranking methods[END_REF] is conducted on two competitors for all datasets to determine if there is a significant difference in accuracy between them. If the first competitor wins, "•" is placed on the grid at this location, "•" and "•" indicate a tie or a loss, respectively. indicate respectively a win, a tie, or a loss of the first competitor compared to the second competitor, the vertical axis is r, and the horizontal axis is ρ.

Figure 6 allows a point-wise analysis between different competitors, but most notably, it uses a robust statistical test to draw statistically significant conclusions. IRBL2 is not able to improve on IRBL in all tested cases, as seen by the numerous number of ties. K-PDR is a better approach than K-KMM as the only times K-PDR loses to K-KMM, K-KMM get also beaten by the Trusted Only baseline (see Figure 7 in Appendices). Finally, IRBL2 (or IRBL) is a better approach than K-PDR when untrusted data are noisy as soon as there is enough trusted data such that the trusted concept can be learned accurately enough to reweight untrusted samples.

Discussions

The previously presented results can be quite underwhelming for both proposed methods, so we propose to discuss these results in this section.

First, results showed that K-PDR could substantially improve on K-KMM, proving the advantage of using classifiers instead of kernels, which are more powerful tools as they require fewer assumptions about the data distribution and are fitter for learning from heterogeneous data such as tabular data. It also highlights a typical result in real-life ML applications where non-parametric methods work better than parametric methods.

Secondly, results showed no improvements brought by IRBL2 over IRBL on class-conditional shift. Indeed, IRBL might already be able to take into account the uncertainty about P(X) provided by PDR in the predicted probabilities P(Y | X) thanks to well-calibrated classifiers, nullifying the effect of IRBL2. For example, in unusual regions of the trusted feature space seen in the untrusted dataset, the value of P T (Y | X) might tend to be around 1 K to account the classifier uncertainty and will assign low weights to such samples already without the aid of a specific classifier for that. Meanwhile, K-PDR was clearly able to improve from PDR on label noise corruptions.

Furthermore, the proposed experiments for class-conditional shifts might only reproduce some cases of dataset shifts, especially shifts with out-of-distribution data [START_REF] Yang | Generalized out-of-distribution detection: A survey[END_REF]. With the proposed design of synthetic class-conditional shift in our per-class cluster sub-sampling, we did not introduce data points in foreign feature spaces. In our experiments, all points from the untrusted dataset are indistribution. We only under-represented some sub-populations. This corruption could lead to biased models for individuals from minority groups. However, it is a more manageable situation to deal with than having different groups in the trusted and untrusted dataset. Moreover, the chosen evaluation metric, Cohen's kappa κ, might not be able to detect such biases, as this metric only evaluates predictive performance.

Finally, the calibration efficiency of the HGBT trees in these experiments greatly impacts the efficiency of every tested biquality-learning algorithm. This benchmark has not explored different calibration techniques other than Isotonic Regression.

Obviously, this benchmark is not a definitive answer to the problem as we could have extended the experiments to other corruptions in real-world untrusted datasets, such as data poisoning [START_REF] Steinhardt | Certified defenses for data poisoning attacks[END_REF] or class imbalance [START_REF] Japkowicz | The class imbalance problem: A systematic study[END_REF].

Conclusion

In this paper, we have shown the capabilities of the biquality learning framework to design algorithms able to handle closed-set distribution shifts by having access to a trusted and untrusted dataset at training time. We proposed two biquality learning algorithms, IRBL2 and K-PDR, inspired respectively by the label noise and the covariate shift literature. We reviewed distribution shift sources and their hierarchy and proposed two novel methods to synthetically create concept drift and class-conditional shifts in real-world datasets. Throughout extensive experiments, we benchmarked many competitors from the state-of-the-art. We opened some discussions on the results and assessed that the development of biquality learning algorithms robust to distributional changes of closed sets, despite the presented results, remains an interesting problem for future research in this area. Table 5: Table of conversion between ρ and the actual ratio between the number of samples after and before subsampling (actual). •" indicate respectively a win, a tie, or a loss of the first competitor compared to the second competitor, the vertical axis is r, and the horizontal axis is ρ.

A Additional Tables

  ) distribution shift covers covariate shift P T (X) ̸ = P U (X), concept drift P T (Y | X) ̸ = P U (Y | X), class-conditional shift P T (X | Y ) ̸ = P U (X | Y ) and prior shift P T (Y ) ̸ = P U (Y ).

cleanFig. 1 :

 1 Fig.1: Two moons dataset with the decision boundary of a Support Vector Machine classifier using a polynomial kernel.

Fig. 2 :

 2 Fig. 2: Corrupted two moons dataset with the decision boundary of a Support Vector Machine classifier using a polynomial kernel.

Fig. 3 :

 3 Fig. 3: Trusted and untrusted two moons dataset. Trusted data points are represented with a □ marker and untrusted data points are represented with a ⃝and with a more transparent color. The markers' sizes are proportional to the weights given by the corresponding algorithm.

Fig. 4 :

 4 Fig.4: Average Cohen's kappa κ with different corruption strengths (noise ratio r, or cluster imbalance ρ) and ratio of trusted data p over all datasets. The first row corresponds to experiments without noise (r = 0), and the second row corresponds to experiments without cluster imbalance (ρ = 0). Each column corresponds to a different case of ratio of trusted data (p = 0.25, p = 0.5, p = 0.75).

Fig. 5 :

 5 Fig. 5: Critical diagrams with different ratio of trusted data p over all datasets. The first row corresponds to experiments without noise (r = 0), and the second row corresponds to experiments without cluster imbalance (ρ = 0). Each column corresponds to a different case of ratio of trusted data (p = 0.25, p = 0.5, p = 0.75).

Fig. 6 :

 6 Fig.6: Results of the Wilcoxon signed rank test computed on all datasets. Each figure compares one competitor versus another for a given trusted data ratio. Figures in the same row are the same competitors against different cases of trusted data ratio: p = 0.25, p = 0.5, p = 0.75. In each figure"•", "•" and "•" indicate respectively a win, a tie, or a loss of the first competitor compared to the second competitor, the vertical axis is r, and the horizontal axis is ρ.

Fig. 7 :

 7 Fig. 7: Additional results of the Wilcoxon signed rank test computed on all datasets. Each figure compares one competitor versus another for a given trusted data ratio. Figures in the samerow are the same competitors against different cases of trusted data ratio: p = 0.25, p = 0.5, p = 0.75. In each figure"•", "•" and "•" indicate respectively a win, a tie, or a loss of the first competitor compared to the second competitor, the vertical axis is r, and the horizontal axis is ρ.

Table 1 :

 1 Hierarchy of Distribution Shift sources

		Distribution Shift
		P(X, Y )
	P(Y | X)P(X)	P(X | Y )P(Y )
	Concept Drift Covariate Shift Class-Conditional Shift Prior Shift
	P(Y | X)	P(X)	P(X | Y )	P(Y )

Table 2 :

 2 Multi-class classification datasets used for the evaluation. Columns: number of samples (|D|), number of features (|X |), number of classes (|Y|), and ratio of the number of samples from the minority class over the number of samples from the majority class (min).

	Datasets	|D|	|X | |Y| min	Datasets	|D| |X | |Y| min
	eeg	15K	14 2 0.81	ad	3.28K 1558 2 0.16
	ibn-sina	20.7K	92 2 0.61	nomao	34.5K 118 2 0.40
	zebra	61.5K 154 2 0.05	click	39.9K	9 2 0.20
	musk	6.6K	167 2 0.18	jm1	10.9K 21 2 0.24
	phishing	11.1K	30 2 0.80	pendigits	11K 16 10 0.92
	spam	4.6K	57 2 0.65	japanese-vowels	9.96K 14 9 0.48
	ijcnn1	192K	22 2 0.11	gas-drift	13.9K 128 6 0.55
	hiva	42.7K 1617 2 0.04	connect-4	67.6K 42 3 0.15
	svmguide3	1.24K	22 2 0.31	satimage	6.43K 36 6 0.41
	web	37K	123 2 0.32	dna	3.19K 180 3 0.46
	mushroom	8.12K	22 2 0.93	first-ord-theo-prov 6.12K 51 6 0.19
	skin-seg	245K	3 2 0.26	artificial-chars	10.2K	7 10 0.42
	mozilla4	15.5K	5 2 0.49	splice	3.19K 60 3 0.46
	electricity	45.3K	8 2 0.74	har	10.3K 561 6 0.72
	bank-marketing 45.2K	16 2 0.13	usps	9.3K 256 10 0.46
	magic-telescope 19K	10 2 0.54	mnist	70K 784 10 0.80
	phoeneme	5.4K	5 2 0.42	letter	20K 16 26 0.90
	poker	1.03M 10 2 1.00	isolet	7.8K 617 26 0.99

Table 3 :

 3 Averaged area under the Cohen's kappa κ curve for all datasets.

		p IRBL IRBL2 K-KMM K-PDR No Corr. PDR Trusted
	r = 0	0.25 0.676 0.675 0.575 0.50 0.699 0.698 0.610 0.75 0.722 0.722 0.658	0.694 0.693 0.709 0.700 0.729 0.719	0.624 0.266 0.630 0.484 0.718 0.619
	ρ = 0	0.25 0.457 0.457 0.444 0.50 0.515 0.515 0.476 0.75 0.630 0.630 0.534	0.457 0.459 0.474 0.462 0.539 0.486	0.422 0.266 0.461 0.484 0.486 0.619

0.809

Availability of data and materials

All data used in this study are available publicly online on openML: https: //www.openml.org/

Code availability

Code is available at the following url: https://github.com/pierrenodet/blds

Declarations

Funding Pierre Nodet, Vincent Lemaire, Alexis Bondu, and Antoine Cornuéjols received funding from Orange SA.

Competing Interests

Pierre Nodet, Vincent Lemaire, and Alexis Bondu have received research support from Orange SA. Antoine Cornuéjols has received research support from AgroParisTech and Orange SA.

Ethics approval

Not Applicable.

Consent to participate

All authors have read and approved the final manuscript.

Consent for publication

Not Applicable.

Authors' contributions

Pierre Nodet, Vincent Lemaire, Alexis Bondu, and Antoine Cornuéjols contributed to the manuscript equally.