Weighted Empirical RiskMinimization: Transfer Learning based on Importance Sampling
Year: 2019

Abstract:
We consider statistical learning problems, when the distribution P′ of the training observations Z′ 1, . . . , Z ′ n differs from the distribution P involved in the risk one seeks to minimize (referred to as the test distribution) but is still defined on the same measurable space as P and dominates it. In the unrealistic case where the likelihood ratio Φ(z) = dP/dP′(z) is known, one may straightforwardly extends the Empirical Risk Minimization (ERM) approach to this specific transfer learning setup using the same idea as that behind Importance Sampling, by minimizing a weighted version of the empirical risk functional computed from the ’biased’ training data Z′ i with weights Φ(Z′ i ). Although the importance function Φ(z) is generally unknown in practice, we show that, in various situations frequently encountered in practice, it takes a simple form and can be directly estimated from the Z′ i ’s and some auxiliary information on the statistical population P. By means of linearization techniques, we then prove that the generalization capacity of the approach aforementioned is preserved when plugging the resulting estimates of the Φ(Z′ i )’s into the weighted empirical risk. Beyond these theoretical guarantees, numerical results provide strong empirical evidence of the relevance of the approach promoted in this article.

text: ′ n differs from the distribution P involved in the risk one
seeks to minimize (referred to as the test distribution) but is still defined on the same measurable space as P and dominates it. In the unrealistic case where the likelihood ratio Φ(z) = dP/dP′(z) is known, one may straightforwardly extends the Empirical Risk Minimization (ERM) approach to this specific transfer learning setup using the same idea as that behind Importance Sampling, by minimizing a weighted version of the empirical risk functional computed from the ’biased’ training data Z′i with weights Φ(Z′i ). Although the importance function Φ(z) is generally unknown in practice, we show that, in various situations frequently encountered in practice, it takes a simple form and can be directly estimated from the Z′i ’s and some auxiliary information on the statistical population P. By means of linearization techniques, we then prove that the generalization capacity of the approach aforementioned is preserved when plugging the resulting estimates of the Φ(Z′i )’s into the weighted empirical risk. Beyond these theoretical guarantees, numerical results provide strong empirical evidence of the relevance of the approach promoted in this article.
1 Introduction
Prediction problems are of major importance in statistical learning. The main paradigm of predictive learning is Empirical Risk Minimization (ERM in abbreviated form), see e.g. Devroye et al. (1996). In the standard setup, Z is a random variable (r.v. in short) that takes its values in a feature spaceZ with distribution P, Θ is a parameter space and ` : Θ ×Z → R+ is a (measurable) loss function. The risk is then defined by: ∀θ ∈ Θ, RP(θ) = EP [`(θ,Z)] , (1) and more generally for any measure Q onZ: RQ(θ) = ∫ Z `(θ, z)dQ(z). In most practical situations, the distribution P involved in the definition of the risk is unknown and learning is based on the sole observation of an independent and identically distributed (i.i.d.) sample Z1, . . . , Zn drawn from P and the risk (1) must be replaced by an empirical counterpart (or a possibly smoothed/penalized version of it), typically:
R̂P(θ) = 1 n n∑ i=1 `(θ,Zi) = RP̂n (θ), (2)
where P̂n = (1/n) ∑n
i=1 δZi is the empirical measure of P and δz denotes the Dirac measure at any point z. With the design of successful algorithms such as neural networks, support vector machines or boosting methods to perform ERM, the practice of predictive learning has recently received a significant attention and is now supported by a sound theory based on results in empirical process theory. The performance of minimizers of (2) can be indeed studied by means of concentration inequalities, quantifying the fluctuations of the maximal deviations supθ∈Θ |R̂P(θ) − RP(θ)| under various complexity assumptions for the functional class F = {`(θ, ·) : θ ∈ Θ} (e.g. VC dimension, metric entropies, Rademacher averages), see Boucheron et al. (2013) for instance. Although, in the Big Data era, the availability of massive digitized information to train predictive rules is an undeniable opportunity for the widespread deployment of machine-learning solutions, the poor control of the data acquisition process one is confronted with in many applications puts practicioners at risk of jeopardizing the generalization ability of the rules produced by the algorithms implemented. Bias
selection issues in machine-learning are now the subject of much attention in the literature, see Bolukbasi et al. (2016), Zhao et al. (2017), Burns et al. (2019), Liu et al. (2016) or Huang et al. (2007). In the context of face analysis, a research area including a broad range of applications such as face detection, face recognition or face attribute detection, machine learning algorithms trained with baised training data, e.g. in terms of gender or ethnicity, raise concerns about fairness in machine learning. Unfair algorithms may induce systemic undesired disadvantages for specific social groups, see Das et al. (2018) for further details. Several examples of bias in deep learning based face recognition systems are discussed in Nagpal et al. (2019).
Throughout the present article, we consider the case where the i.i.d. sample Z′1, . . . , Z ′ n available for training is not drawn from P but from another distribution P′, with respect to which P is absolutely continuous, and the goal pursued is to set theoretical grounds for the application of ideas behind Importance Sampling (IS in short) methodology to extend the ERM approach to this learning setup. We highlight that the problem under study is a very particular case of Transfer Learning (see e.g. Pan & Yang (2010), Ben-David et al. (2010) and Storkey (2009)), a research area currently receiving much attention in the literature and encompassing general situations where the information/knowledge one would like to transfer may take a form in the target space very different from that in the source space (referred to as domain adaptation).
Weighted ERM (WERM). In this paper, we investigate conditions guaranteeing that values for the parameter θ that nearly minimize (1) can be obtained through minimization of a weighted version of the empirical risk based on the Z′i ’s, namely
R̃w,n(θ) = RP̃w,n (θ), (3) where P̃w,n = (1/n) ∑n
i=1 wiδZ′i and w = (w1, . . . , wn) ∈ R n + is a certain weight vector. Of course, ideal
weights w∗ are given by the likelihood function Φ(z) = (dP/dP′)(z): w∗i = Φ(Z ′ i ) for i ∈ {1, . . . , n}. In this case, the quantity (3) is obviously an unbiased estimate of the true risk (1):
EP′ [ RP̃w∗ ,n (θ) ] = RP(θ), (4)
and generalization bounds for the RP-risk excess of minimizers of R̃w∗,n can be directly established by studying the concentration properties of the empirical process related to the Z′i ’s and the class of functions {Φ(·)`(θ, ·) : θ ∈ Θ} (see section 2 below). However, the importance function Φ is unknown in general, just like distribution P. It is the major purpose of this article to show that, in far from uncommon situations, the (ideal) weights w∗i can be estimated from the Z ′ i s combined with auxiliary information on the target population P. As shall be seen below, such favorable cases include in particular classification problems where class probabilities in the test stage differ from those in the training step, risk minimization in stratified populations (see Bekker & Davis (2018)), with strata statistically represented in a different manner in the test and training populations, positive-unlabeled learning (PU-learning, see e.g. du Plessis et al. (2014)). In each of these cases, we show that the stochastic process obtained by plugging the weight estimates in the weighted empirical risk functional (3) is much more complex than a simple empirical process (i.e. a collection of i.i.d. averages) but can be however studied by means of linearization techniques, in the spirit of the ERM extensions established in Clémençon et al. (2008) or Clémençon & Vayatis (2009). Learning rate bounds for minimizers of the corresponding risk estimate are proved and, beyond these theoretical guarantees, the performance of the weighted ERM approach is supported by convincing numerical results.
The article is structured as follows. In section 2, the ideal case where the importance function Φ is known is preliminarily considered and a first basic example where the optimal weights can be easily inferred and plugged into the risk without deteriorating the learning rate is discussed. The main results of the paper are stated in section 3, which shows that the methodology promoted can be applied to two important problems in practice, risk minimization in stratified populations and PU-learning, with generalization guarantees. Illustrative numerical experiments are displayed in section 4, while some concluding remarks are collected in section 5. Proofs and additional results are deferred to the Supplementary Material.
2 Importance Sampling - RiskMinimization with Biased Data
Here and throughout, the indicator function of any event E is denoted by I{E}, the sup norm of any bounded function h : Z → R by ||h||∞. We place ourselves in the framework of statistical learning
based on biased training data previously introduced. As a first go, we consider the unrealistic situation where the importance function Φ is known, insofar as we shall subsequently develop techniques aiming at mimicking the minimization of the ideally weighted empirical risk
R̃w∗,n(θ) = 1 n n∑ i=1 w∗i `(θ,Z ′ i ), (5)
namely the (unbiased) Importance Sampling estimator of (1) based on the instrumental data Z′1, . . . , Z ′ n. The following result describes the performance of minimizers θ̃ ∗ n of (5). Since the goal of this paper is to promote the main ideas of the approach rather than to state results with the highest level of generality due to space limitations, we assume throughout the article for simplicity that ` and Φ are both bounded functions. For σ1, . . . , σn independent Rademacher random variables (i.e. symmetric {−1, 1}-valued r.v.’s), independent from the Z′i ’s, we define the Rademacher average associated to the class of function F as R′n(F ) := Eσ [ supθ∈Θ 1 n
∣∣∣∑ni=1 σi`(θ,Z′i )∣∣∣] . This quantity can be bounded by metric entropy methods under appropriate complexity assumptions on the class F , it is for instance of order OP(1/ √ n) when F is a VC major class with finite VC dimension, see e.g. Boucheron et al. (2005). Lemma 1. With probability at least 1 − δ, we have: ∀n ≥ 1,
RP (̃θ∗n) −min θ∈Θ RP(θ) ≤ 4||Φ||∞E
[ R′n(F ) ] + 2||Φ||∞ sup
(θ,z)∈Θ×Z `(θ, z)
√ 2 log(1/δ)
n .
Of course, when P′ = P, we have Φ ≡ 1 and the bound stated above simply describes the performance of standard empirical risk minimizers. The proof is based on the standard bound
RP (̃θ∗n) −min θ∈Θ RP(θ) ≤ 2 sup
θ∈Θ ∣∣∣∣R̃w∗,n(θ) − E [R̃w∗,n(θ)]∣∣∣∣ , combined with basic concentration results for empirical processes, see the Supplementary Material for further details. Of course, the importance function Φ is generally unknown and must be estimated in practice. As illustrated by the elementary example below (related to binary classification, in the situation where the probability of occurence of a positive instance significantly differs in the training and test stages), in certain statistical learning problems with biased training distribution, Φ takes a simplistic form and can be easily estimated from the Z′i ’s combined with auxiliary information on P.
Binary classification with varying class probabilities. The flagship problem in supervised learning corresponds to the simplest situation, where Z = (X,Y), Y being a binary variable valued in {−1,+1} say, and the r.v. X takes its values in a measurable space X and models some information hopefully useful to predict Y . The parameter space Θ is a set G of measurable mappings (i.e. classifiers) g : X → {−1, +1} and the loss function is given by `(g, (x, y)) = I{g(x) , y} for all g in G and any (x, y) ∈ X × {−1, +1}. The distribution P of the random pair (X,Y) can be either described by X’s marginal distribution µ(dx) and the posterior probability η(x) = P{Y = +1 | X = x} or else by the triplet (p, F+, F−) where p = P{Y = +1} and Fσ(dx) is X’s conditional distribution given Y = σ1 with σ ∈ {−, +}. It is very common that the fraction of positive instances in the training dataset is significantly lower than the rate p expected in the test stage, supposed to be known here (see the Supplementary Material for the case where the rate p is only approximately known). We thus consider the case where the distribution P′ of the training data (X′1,Y ′ 1), . . . , (X ′ n,Y ′ n) is described by the triplet (p′, F+, F−) with p′ < p. The likelihood function takes the simple following form
Φ(x, y) = I{y = +1} p p′ + I{y = −1} 1 − p 1 − p′ de f = φ(y),
which reveals that it depends on the label y solely, and the ideally weighted empirical risk process is
R̃w∗,n(g) = p p′ 1 n ∑ i:Y ′i =1 I{g(X′i ) = −1} + 1 − p 1 − p′ 1 n ∑ i:Y ′i =−1 I{g(X′i ) = +1}. (6)
In general the theoretical rate p′ is unknown and one replaces (6) with
R̃ŵ∗,n(g) = p
n′+ ∑ i:Y ′i =1 I{g(X′i ) = −1} + 1 − p n′− ∑ i:Y ′i =−1 I{g(X′i ) = +1}, (7)
where n′+ = ∑n
i=1 I{Y ′i = +1} = n− n′−, ŵ∗i = φ̂(Y ′i ) and φ̂(y) = I{y = +1}np/n′+ + I{y = −1}n(1− p)/n′−. The stochastic process above is not a standard empirical process but a collection of sums of two ratios of basic averages. However, the following result provides a uniform control of the deviations between the ideally weighted empirical risk and that obtained by plugging the empirical weights into the latter. Lemma 2. Let ε ∈ (0, 1/2). Suppose that p′ ∈ (ε, 1−ε). For any δ ∈ (0, 1), we have with probability larger than 1 − δ:
sup g∈G ∣∣∣∣R̃ŵ∗,n(g) − R̃w∗,n(g)∣∣∣∣ ≤ 2 ε2 √ log(2/δ) 2n ,
as soon as n ≥ 2 log(2/δ)/ε2.
See the Appendix for the technical proof. Consequently, minimizing (7) nearly boils down to minimizing (6). Combining Lemmas 2 and 1, we immediately get the generalization bound stated in the result below. Corollary 1. Suppose that the hypotheses of Lemma 2 are fulfilled. Let g̃n be any minimizer of R̃ŵ∗,n over class G. We have with probability at least 1 − δ:
RP (̃gn) − inf g∈G RP(g) ≤ 2 max(p, 1 − p) ε
2E[R′n(G)] + √
2 log(2/δ) n  + 4ε2 √ log(4/δ) 2n ,
as soon as n ≥ 2 log(4/δ)/ε2; where R′n(G) = (1/n)Eσ[supg∈G | ∑n i=1 σiI{g(X′i ) , Y ′i }|].
Hence, some side information (i.e. knowledge of parameter p) has permitted to weight the training data in order to build an empirical risk functional that approximates the target risk and to show that minimization of this risk estimate yields prediction rules with optimal (in the minimax sense) learning rates. The purpose of the subsequent analysis is to show that this remains true for more general problems. Observe in addition that the bound in Corollary 1 deteriorates as ε decays to zero: the method used here is not intended to solve the few shot learning problem, where almost no training data with positive labels is available (i.e. p′ ≈ 0). As shall be seen in subsection 3.2, alternative estimators of the importance function must be considered in this situation. Remark 1. Although the quantity (7) can be viewed as a cost-sensitive version of the empirical classification risk based on the (X′i ,Y ′ i )’s (see e.g. Bach et al. (2006)), we point out that the goal pursued here is not to achieve an appropriate trade-off between type I and type II errors in the P′ classification problem as in biometric applications for instance (i.e. optimization of the (F+, F−)-ROC curve at a specific point) but to transfer knowledge gained in analyzing the biased data drawn from P′ to the classification problem related to distribution P.
Related work. We point out that the natural idea of using weights in ERM problems that mimic those induced by the importance function has already been used in Sugiyama et al. (2008) for covariate shift adaptation problems (i.e. supervised situations, where the conditional distribution of the output given the input information is the same in the training and test domains), when, in contrast to the framework considered here, a test sample is additionally available (a method for estimating directly the importance function based on Kullback-Leibler divergence minimization is proposed, avoiding estimation of the test density). Importance sampling estimators have been also considered in Garcke & Vanck (2014) in the setup of inductive transfer learning (the tasks between source and target are different, regardless of the similarities between source and target domains), where the authors have proposed two methods to approximate the importance function, among which one is again based on minimizing the Kullback-Leibler divergence between the two distributions. In Cortes et al. (2008), the sample selection bias is assumed to be independent from the label, which is not true under our stratum-shift assumption or for the PU learning problem (see section 3). Lemma 1 assumes that the exact importance function is known, as does Cortes et al. (2010). The next section introduces new results for more realistic settings where it has to be learned from the data.
3 Weighted Empirical RiskMinimization - Generalization Guarantees
Through two important and generic examples, relevant for many applications, we show that the approach sketched above can be applied to general situations, where appropriate auxiliary information on the target distribution is available, with generalization guarantees.
3.1 Statistical Learning from Biased Data in a Stratified Population
A natural extension of the simplistic problem considered in section 2 is multiclass classification in a stratified population. The random labels Y and Y ′ are supposed to take their values in {1, . . . , J} say, with J ≥ 1, and each labeled observation (X,Y) belongs to a certain random stratum S in {1, . . . , K} with K ≥ 1. Again, the distribution P of a random element Z = (X,Y, S ) may be described by the parameters {(p j,k, F j,k) : 1 ≤ j ≤ J, 1 ≤ k ≤ K} where F j,k is the conditional distribution of X given (Y, S ) = ( j, k) and p j,k = P(X,Y,S )∼P{Y = j, S = k}. Then, we have
dP(x, y, s) = J∑
j=1 K∑ k=1 I{y = j, s = k}p j,kdF j,k(x),
and considering a distribution P′ with F j,k ≡ F′j,k but possibly different class-stratum probabilities p′j,k, the likelihood function becomes
dP dP′
(x, y, s) = J∑
j=1 K∑ k=1 p j,k p′j,k I{y = j, s = k} de f= φ(y, s).
A more general framework can actually encompass this specific setup by defining ’meta-strata’ in {1, . . . , J} × {1, . . . , K}. Strata may often correspond to categorical input features in practice. The formalism introduced below is more general and includes the example considered in the preceding section, where strata are defined by labels.
Learning from biased stratified data. Consider a general mixture model, where distributions P and P′ are stratified over K ≥ 1 strata. Namely, Z = (X, S ) and Z′ = (X′, S ′) with auxiliary random variables S and S ′ (the strata) valued in {1, . . . , K}. We place ourselves in a stratum-shift context, assuming that the conditional distribution of X given S = k is the same as that of X′ given S ′ = k, denoted by Fk(dx), for any k ∈ {1, . . . , K}. However, stratum probabilities pk = P(S = k) and p′k = P(S
′ = k) may possibly be different. In this setup, the likelihood function depends only on the strata and can be expressed in a very simple form, as follows:
dP dP′
(x, s) = K∑
k=1
I{s = k} pk p′k de f = φ(s).
In this case, the ideally weighted empirical risk writes
R̃w∗,n(θ) = 1 n n∑ i=1 `(θ,Z′i ) K∑ k=1 I{S ′i = k} pk p′k .
If the strata probabilities pk’s for the test distribution are known, an empirical counterpart of the ideal empirical risk above is obtained by simply plugging estimates of the p′k’s computed from the training data:
R̃ŵ∗,n(θ) = n∑
i=1
`(θ,Z′i ) K∑
k=1
I{S ′i = k} pk n′k , (8)
with n′k = ∑n i=1 I{S ′i = k}, ŵ∗i = φ̂(S ′i ) and φ̂(s) = ∑K
k=1 I{s = k}npk/n′k. A bound for the excess of risk is given in Theorem 1, that can be viewed as a generalization of Corollary 1. Theorem 1. Let ε ∈ (0, 1/2) and assume that p′k ∈ (ε, 1−ε) for k = 1, . . . ,K. Let θ̃∗n be any minimizer of R̃ŵ∗,n as defined in (8) over class Θ. We have with probability at least 1 − δ:
RP (̃θ∗n) − inf θ∈Θ RP(θ) ≤ 2 maxk pk ε
2E[R′n(F )] + L √
2 log(2/δ) n  + 4Lε2 √ log(4K/δ) 2n ,
as soon as n ≥ 2 log(4K/δ)/ 2; where R′n(F ) = (1/n)Eσ[supθ∈Θ | ∑n i=1 σi`(θ,Z ′ i )|], and the loss is bounded by L = sup(θ,z)∈Θ×Z `(θ, z).
Just like in Corollary 1, the bound in Theorem 1 explodes when ε vanishes, which corresponds to the situation where a stratum k ∈ {1, . . . ,K} is very poorly represented in the training data, i.e. when p′k << pk. Again, as highlighted by the experiments carried out, reweighting the losses in a frequentist (ERM) approach guarantees good generalization properties in a specific setup only, where the training information, though biased, is sufficiently informative.
3.2 Positive-Unlabeled Learning
Relaxing the stratum-shift assumption made in the previous subsection, the importance function becomes more complex and writes:
Φ(x, s) = dP dP′
(x, s) = K∑
k=1
I{s = k} pk p′k dFk dF′k (x),
where Fk and F′k are respectively the conditional distributions of X given S = k and of X ′ given S ′ = k. The Positive-Unlabeled (PU) learning problem, which has recently been the subject of much attention (see e.g. du Plessis et al. (2014), Du Plessis et al. (2015), Kiryo et al. (2017)), provides a typical example of this situation. Re-using the notations introduced in section 2, in the PU problem, the testing and training distributions P and P′ are respectively described by the triplets (p, F+, F−) and (q, F+, F), where F = pF+ + (1 − p)F− is the marginal distribution of X. Hence, the objective pursued is to solve a binary classification task, based on the sole observation of a training sample pooling data with positive labels and unlabeled data, q denoting the theoretical fraction of positive data among the dataset. As noticed in du Plessis et al. (2014) (see also Du Plessis et al. (2015), Kiryo et al. (2017)), the likelihood/importance function can be expressed in a simple manner, as follows:
∀(x, y) ∈ X × {−1, +1}, Φ(x, y) = p q I{y = +1} + 1 1 − q I{y = −1} − p 1 − q dF+ dF (x)I{y = −1}. (9)
Based on an i.i.d. sample (X′1,Y ′ 1), . . . , (X ′ n,Y ′ n) drawn from P ′ combined with the knowledge of p (which can also be estimated from PU data, see e.g. Du Plessis & Sugiyama (2014)) and using that F− = (1/(1 − p))(F − pF+), one may obtain estimators of q, F+ and F by computing n′+/n = (1/n) ∑n i=1 I{Y ′i = +1}, F̂+ = (1/n′+) ∑n i=1 I{Y ′i = +1}δX′i and F̂ = (1/n ′ −) ∑n i=1 I{Y ′i = −1}δX′i . However, plugging these quantities into (9) do not permit to get a statistical version of the importance function, insofar as the probability measures F̂+ and F̂ are mutually singular with probability one, as soon as F+ is continuous. Of course, as proposed in du Plessis et al. (2014), one may use statistical methods (e.g. kernel smoothing) to build distribution estimators, that ensures absolute continuity but are subject to the curse of dimensionality. However, WERM can still be applied in this case, by observing that: ∀g ∈ G,
RP(g) = −p + EP′ [ 2p q I{g(X′) = −1, Y ′ = +1} + 1 1 − q I{g(X ′) = +1, Y ′ = −1} ] , (10)
which leads to the weighted empirical risk 2p n′+ ∑ i:Y ′i =+1 I{g(X′i ) = −1} + 1 n′− ∑ i:Y ′i =−1 I{g(X′i ) = +1}. (11)
Minimization of (11) yields rules g̃n whose generalization ability regarding the binary problem related to (p, F+, F−) can be guaranteed, as shown by the following result, the form of the weighted empirical risk in this case being quite similar to (7). Theorem 2. Let ε ∈ (0, 1/2). Suppose that q ∈ (ε, 1 − ε). Let g̃n be any minimizer of the weighted empirical risk (11) over class G. We have with probability at least 1 − δ:
RP (̃gn) − inf g∈G RP(g) ≤ 2 max(2p, 1) ε
2E[R′n(G)] + √
2 log(2/δ) n  + 4(2p + 1)ε2 √ log(4/δ) 2n ,
as soon as n ≥ 2 log(4/δ)/ε2; where R′n(G) = (1/n)Eσ[supg∈G | ∑n
i=1 σiI{g(X′i ) , Y ′i }|]. Remark 2. Let η(x) = P{Y = +1 | X = x} denote the posterior probability and recall that (dF+/dF−)(x) = ((1 − p)/p)(η(x)/(1 − η(x)). Observing that
Φ(x, y) = p q I{y = +1} + 1 − η(x) 1 − q I{y = −1}, (12)
in the case when an estimate η̂(x) of η(x) is available, one can perform WERM using the empirical weight function
Φ̂(x, y) = np n′+ I{y = +1} + 1 − η̂(x) 1 − n′+/n I{y = −1}. (13)

heading: A bound that describes how this approach generalizes, depending on the accuracy of estimate η̂, can be easily established, for more details refer to Theorem 3 in the Supplementary Material, where it is
text: also discussed how to exploit such formulas in order to design incremental WERM procedures.
4 Numerical Experiments
This section illustrates the impact of reweighting by the likelihood ratio on classification performances, as a special case of the general strategy presented in Section 2. A first simple illustration on known probability distributions highlights the impact of the shapes of the distributions on the importance of reweighting. This example illustrates in the infinite-sample case that separable or almost separable data do not require reweighting, in contrast to noisy data. Since the distribution shapes are unknown for real data, we infer that reweighting will have variable effectiveness, depending on the dataset. This illustration is deferred to the Appendix, as well as an experiment on reweighting for classification of MNIST dataset where bias is introduced in the distribution of the classes. We detail here a second experiment that uses the structure of ImageNet to illustrate reweighting with a stratified population and strata distribution bias or strata bias. The code of the experiments can be found at https://drive. google.com/drive/folders/1-tWJ4n4WyXuTza8dLPngyHSVprKUZFVJ?usp=sharing.
We focus on the learning from biased stratified data setting introduced in Section 3.1 by leveraging the ImageNet Large Scale Visual Recognition Challenge (ILSVRC); a well-known benchmark for the image classification task, see Russakovsky et al. (2014) for more details.
The challenge consists in learning a classifier from 1.3 million training images spread out over 1,000 classes. Performance is evaluated using the validation dataset of 50,000 images of ILSVRC as our test dataset. ImageNet is an image database organized according to the WordNet hierarchy, which groups nouns in sets of related words called synsets. In that context, images are examples of very precise nouns, e.g. flamingo, which are contained in a larger synset, e.g. bird.
The impact of reweighting in presence of strata bias is illustrated on the ILSVRC classification problem with broad significance synsets for strata. To do this, we encode the data using deep neural networks. Specifically our encoding is the flattened output of the last convolutional layer of the network ResNet50 introduced in He et al. (2015). It was trained for classification on the training dataset of ILSVRC. The encodings X1, . . . , Xn belong to a 2,048-dimensional space.
A total of 33 strata are derived from a list of high-level categories provided by ImageNet1. The construction of the strata is postponed to the Appendix. By default, strata probabilities pk and p′k for 1 ≤ k ≤ K are equivalent between training and testing datasets, meaning that reweighting by Φ would have little to no effect. Since our testing data is the validation data of ILSVRC, we have around 25 times more training than testing data. Introducing a strata bias parameter 0 ≤ γ ≤ 1, we set the strata train probabilities such that p′k = γ
1−bK/2c/k pk before renormalization and remove train instances so that the train set has the right distribution over strata; see the Appendix for more details on the generation of strata bias. When γ is close to one, there is little to no strata bias. In contrast, when γ approaches 0, strata bias is extreme.
1http://www.image-net.org/about-stats
The models used are a linear model and a multilayer perceptron (MLP) with one hidden layer; more details are given in the Appendix. We report better performance when reweighting using the strata information, compared to the case where the strata information is ignored, see fig. 1. For comparison, we added two reference experiments: one which reweights the train instances by the class probabilities, which we do not know in a stratified population experiment, and one with more data and no strata bias because it uses all of the ILSVRC train data. The dominance of the linear model over the MLP can be justified by the much higher number of parameters to estimate for the MLP.
5 Conclusion
In this paper, we have considered specific transfer learning problems, where the distribution of the test data P differs from that of the training data, P′, and is absolutely continuous with respect to the latter. This setup encompasses many situations in practice, where the data acquisition process is not perfectly controlled. In this situation, a simple change of measure shows that the target risk may be viewed as the expectation of a weighted version of the basic empirical risk, with ideal weights given by the importance function Φ = dP/dP′, unknown in practice. Throughout this article, we have shown that, in statistical learning problems corresponding to a wide variety of practical applications, these ideal weights can be replaced by statistical versions based solely on the training data combined with very simple information about the target distribution. The generalisation capacity of rules learnt from biased training data by minimization of the weighted empirical risk has been established, with learning bounds. These theoretical results are also illustrated with several numerical experiments.
References Francis Bach, David Heckerman, and Eric Horvitz. Considering cost asymmetry in learning classifiers,
2006.
Jessa Bekker and Jesse Davis. Beyond the selected completely at random assumption for learning from positive and unlabeled data. CoRR, abs/1809.03207, 2018. URL http://arxiv.org/abs/ 1809.03207.
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan. A theory of learning from different domains. Machine Learning, 79(1), 2010.
Tolga Bolukbasi, Kai-Wei Chang, James Zou, Venkatesh Saligrama, and Adam Kalai. Man is to computer programmer as woman is to homemaker? debiasing word embeddings. In NIPS, pp. 4349–4357, 2016.
Stéphane Boucheron, Olivier Bousquet, and Gàbor Lugosi. Theory of classification : a survey of some recent advances. ESAIM: Probability and Statistics, 9:323–375, 2005.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. OUP Oxford, 2013.
Kaylee Burns, Lisa Anne Hendricks, Kate Saenko, Trevor Darrell, and Anna Rohrbach. Women also snowboard: Overcoming bias in captioning models. 2019.
François Chollet et al. Keras. https://keras.io, 2015.
Stephan Clémençon and Nicolas Vayatis. Empirical performance maximization based on linear rank statistics. In NIPS, volume 3559 of Lecture Notes in Computer Science, pp. 1–15. Springer, 2009.
Stephan Clémençon and Nicolas Vayatis. Tree-Based Ranking Methods. IEEE Trans. on Inf. Theory, 5(9):4136–4156, 2009.
Stephan Clémençon, Gàbor Lugosi, and Nicolas Vayatis. Ranking and Empirical Minimization of U-Statistics. The Annals of Statistics, 36(2):844–874, 2008.
Corinna Cortes, Mehryar Mohri, Michael Riley, and Afshin Rostamizadeh. Sample selection bias correction theory. In International conference on algorithmic learning theory, pp. 38–53. Springer, 2008.
Corinna Cortes, Yishay Mansour, and Mehryar Mohri. Learning bounds for importance weighting. In Advances in neural information processing systems, pp. 442–450, 2010.
Abhijit Das, Antitza Dantcheva, and Francois Bremond. Mitigating bias in gender, age and ethnicity classification: a multi-task convolution neural network approach. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 0–0, 2018.
Luc Devroye, László Györfi, and Gábor Lugosi. A Probabilistic Theory of Pattern Recognition. Springer, 1996.
Marthinus Christoffel Du Plessis and Masashi Sugiyama. Class prior estimation from positive and unlabeled data. IEICE TRANSACTIONS on Information and Systems, 97(5):1358–1362, 2014.
Marthinus Christoffel du Plessis, Gang Niu, and Masashi Sugiyama. Analysis of learning from positive and unlabeled data. In NIPS, pp. 703–711, 2014.
Marthinus Christoffel Du Plessis, Gang Niu, and Masashi Sugiyama. Convex formulation for learning from positive and unlabeled data. In ICML, ICML’15, pp. 1386–1394. JMLR.org, 2015. URL http://dl.acm.org/citation.cfm?id=3045118.3045266.
Jochen Garcke and Thomas Vanck. Importance weighted inductive transfer learning for regression. In ECML PKDD, pp. 466–481. Springer, 2014.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. CoRR, abs/1512.03385, 2015. URL http://arxiv.org/abs/1512.03385.
Jiayuan Huang, Arthur Gretton, Karsten M Borgwardt, Bernhard Schölkopf, and Alexander J. Smola. Correcting sample selection bias by unlabeled data. In NIPS, pp. 601–608, 2007.
Ryuichi Kiryo, Gang Niu, Marthinus Christoffel du Plessis, and Masashi Sugiyama. Positiveunlabeled learning with non-negative risk estimator. In NIPS, pp. 1674–1684, 2017.
Zhen Liu, Jun-an Yang, Hui Liu, and Wei Wang. Transfer learning by sample selection bias correction and its application in communication specific emitter identification. JCM, 11:417–427, 2016.
Shruti Nagpal, Maneet Singh, Richa Singh, Mayank Vatsa, and Nalini Ratha. Deep learning for face recognition: Pride or prejudiced? arXiv preprint arXiv:1904.01219, 2019.
Sinno Jialin Pan and Qiang Yang. A survey on transfer learning. IEEE Transactions on Knowledge and Data Engineering, 22(10):1345–1359, Oct 2010. ISSN 1041-4347. doi: 10.1109/TKDE.2009.191.
Sebastian Ruder. An overview of gradient descent optimization algorithms. CoRR, abs/1609.04747, 2016. URL http://arxiv.org/abs/1609.04747.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael S. Bernstein, Alexander C. Berg, and FeiFei Li. Imagenet large scale visual recognition challenge. CoRR, abs/1409.0575, 2014. URL http://arxiv.org/abs/1409.0575.
Amos Storkey. When training and test sets are different: characterizing learning transfer. Dataset shift in machine learning, pp. 3–28, 2009.
Masashi Sugiyama, Shinichi Nakajima, Hisashi Kashima, Paul von Buenau, and Motoaki Kawanabe. Direct importance estimation with model selection and its application to covariate shift adaptation. In NIPS, pp. 1433–1440, 2008.
Jieyu Zhao, Tianlu Wang, Mark Yatskar, Vicente Ordonez, and Kai-Wei Chang. Men also like shopping: Reducing gender bias amplification using corpus-level constraints. In EMNLP, 2017.
Appendix - Technical Proofs
Here we detail the proofs of the results stated in the article and discuss their connection with related work.
Proof of Lemma 1
Let δ ∈ (0, 1). Applying the classic maximal deviation bound stated in Theorem 3.2 of Boucheron et al. (2005) to the bounded class K = {z ∈ Z 7→ Φ(z)l(θ, z) : θ ∈ Θ}, we obtain that, with probability at least 1 − δ:
sup θ∈Θ ∣∣∣∣R̃w∗,n(θ) − E [R̃w∗,n(θ)]∣∣∣∣ ≤ 2E [R′n(K)] + ||Φ||∞ sup (θ,z)∈Θ×Z |`(θ, z)| √ 2 log(1/δ) n .
In addition, by virtue of the contraction principle, we have R′n(K) ≤ ||Φ||∞R′n(F ) almost-surely. The desired result can be thus deduced from the bound above combined with the classic bound
RP(θ̃∗n) −min θ∈Θ RP(θ) ≤ 2 sup
θ∈Θ ∣∣∣∣R̃w∗,n(θ) − E [R̃w∗,n(θ)]∣∣∣∣ . Proof of Lemma 2
Apply twice the Taylor expansion
1 x = 1 a − x − a a2 + (x − a)2 xa2 ,
so as to get
1 n′+/n = 1 p′ − n
′ +/n − p′
p′2 + (n′+/n − p′)2 p′2n′+/n ,
1 n′−/n = 1 1 − p′ − n′−/n − 1 + p′ (1 − p′)2 + (n′−/n − 1 + p′)2 (1 − p′)2n′−/n .
This yields the decomposition
R̃ŵ∗,n(g) − R̃w∗,n(g) = − p
p′2 ( n′+ n − p′ ) 1 n n∑ i=1 I{g(X′i ) = −1, Y ′i = +1}
− 1 − p (1 − p′)2 ( n′− n − 1 + p′ ) 1 n n∑ i=1 I{g(X′i ) = +1, Y ′i = −1}+ p(n′+/n − p′)2 p′2n′+/n 1 n n∑ i=1 I{g(X′i ) = −1, Y ′i = +1}
+ (1 − p)(n′−/n − 1 + p′)2 (1 − p′)2n′−/n 1 n n∑ i=1 I{g(X′i ) = +1, Y ′i = −1}.
We deduce that∣∣∣∣R̃ŵ∗,n(g) − R̃w∗,n(g)∣∣∣∣ ≤ |n′+/n − p′| ε2 ( 1 + |n′+/n − p′| ( p n′+/n + 1 − p 1 − n′+/n )) .
By virtue of Hoeffding inequality, we obtain that, for any δ ∈ (0, 1), we have with probability larger than 1 − δ: ∣∣∣n′+/n − p′∣∣∣ ≤ √ log(2/δ)2n , so that, in particular, min{n′+/n, 1 − n′+/n} ≥ ε − √ log(2/δ)/(2n). This yields the desired result.
Proof of Corollary 1
Observe first that ||Φ||∞ ≤ max(p, 1 − p)/ε and
RP (̃gn) − inf g∈G RP(g) ≤ 2 sup
g∈G ∣∣∣∣R̃ŵ∗,n(g) − R̃w∗,n(g)∣∣∣∣ + 2 sup g∈G ∣∣∣∣R̃w∗,n(g) − RP(g)∣∣∣∣ . The result then directly follows from the application of Lemmas 1-2 combined with the union bound.
Proof of Theorem 1
Observe first that ||Φ||∞ ≤ maxk pk/ε and
RP (̃θ∗n) − inf θ∈Θ RP(θ) ≤ 2 sup
θ∈Θ ∣∣∣∣R̃ŵ∗,n(θ) − R̃w∗,n(θ)∣∣∣∣ + 2 sup θ∈Θ ∣∣∣∣R̃w∗,n(θ) − RP(θ)∣∣∣∣ . The result then directly follows from the application of Lemmas 1-3 combined with the union bound.
Lemma 3. Let ε ∈ (0, 1/2). Suppose that p′k ∈ (ε, 1 − ε) for k ∈ {1, . . . , K}. For any δ ∈ (0, 1), we have with probability larger than 1 − δ:
sup θ∈Θ ∣∣∣∣R̃ŵ∗,n(θ) − R̃w∗,n(θ)∣∣∣∣ ≤ 2L ε2 √ log(2K/δ) 2n ,
as soon as n ≥ 2 log(2K/δ)/ε2, where L = sup(θ,z)∈Θ×Z `(θ, z).
proof.
Apply the Taylor expansion 1 x = 1 a − x − a a2 + (x − a)2 xa2 ,
so as to get for all k ∈ {1, . . . ,K}
1 n′k/n = 1 p′k − n′k/n − p′k p′2k + (n′k/n − p′k)2 p′2k n ′ k/n .
This yields the decomposition
R̃ŵ∗,n(θ) − R̃w∗,n(θ) = 1 n n∑ i=1 `(θ,Z′i ) K∑ k=1 I{S ′i = k} − pk p′2k ( n′k n − p′k ) + pk(n′k/n − p′k)2 p′2k n ′ k/n  . We deduce that ∣∣∣∣R̃ŵ∗,n(θ) − R̃w∗,n(θ)∣∣∣∣ ≤ L
ε2 K∑ k=1 |n′k/n − p′k |pk ( 1 + |n′k/n − p′k | n′k/n ) .
By virtue of Hoeffding inequality, we obtain that, for any k ∈ {1, . . . ,K} and δ ∈ (0, 1), we have with probability larger than 1 − δ: ∣∣∣n′k/n − p′k∣∣∣ ≤ √ log(2/δ)
2n , so that, by a union bound, maxk{n′k/n} ≥ ε − √ log(2K/δ)/(2n). This yields the desired result.
Proof of Theorem 2
Observe first that ||Φ||∞ ≤ max(2p, 1)/ε and
RP (̃gn) − inf g∈G RP(g) ≤ 2 sup
g∈G ∣∣∣∣R̃ŵ∗,n(g) − R̃w∗,n(g)∣∣∣∣ + 2 sup g∈G ∣∣∣∣R̃w∗,n(g) − RP(g)∣∣∣∣ , with weighted empirical risk R̃w∗,n(g) defined in (11). The result then directly follows from the application of Lemmas 1-4 combined with the union bound. Lemma 4. Let ε ∈ (0, 1/2). Suppose that q ∈ (ε, 1− ε). For any δ ∈ (0, 1), we have with probability larger than 1 − δ:
sup g∈G ∣∣∣∣R̃ŵ∗,n(g) − R̃w∗,n(g)∣∣∣∣ ≤ 2(2p + 1) ε2 √ log(2/δ) 2n ,
as soon as n ≥ 2 log(2/δ)/ε2.
proof. Apply twice the Taylor expansion
1 x = 1 a − x − a a2 + (x − a)2 xa2 ,
so as to get
1 n′+/n = 1 q − n
′ +/n − q
q2 + (n′+/n − q)2 q2n′+/n ,
1 n′−/n = 1 1 − q − n′−/n − 1 + q (1 − q)2 + (n′−/n − 1 + q)2 (1 − q)2n′−/n .
This yields the decomposition
R̃ŵ∗,n(g) − R̃w∗,n(g) = − 2p q2 ( n′+ n − q ) 1 n n∑ i=1 I{g(X′i ) = −1, Y ′i = +1}
− 1 (1 − q)2 ( n′− n − 1 + q ) 1 n n∑ i=1 I{g(X′i ) = +1, Y ′i = −1}+ 2p(n′+/n − q)2 q2n′+/n 1 n n∑ i=1 I{g(X′i ) = −1, Y ′i = +1}
+ (n′−/n − 1 + q)2 (1 − q)2n′−/n 1 n n∑ i=1 I{g(X′i ) = +1, Y ′i = −1}.
We deduce that∣∣∣∣R̃ŵ∗,n(g) − R̃w∗,n(g)∣∣∣∣ ≤ |n′+/n − q| ε2 ( 2p + 1 + |n′+/n − q| ( 2p n′+/n + 1 1 − n′+/n )) .
By virtue of Hoeffding inequality, we obtain that, for any δ ∈ (0, 1), we have with probability larger than 1 − δ: ∣∣∣n′+/n − q∣∣∣ ≤ √ log(2/δ)2n , so that, in particular, min{n′+/n, 1 − n′+/n} ≥ ε − √ log(2/δ)/(2n). This yields the desired result.
Alternative approach for Positive-Unlabeled Learning
Theorem 3. Let ŵ∗i = Φ̂(X ′ i ,Y ′ i ) for all i ∈ {1, . . . , n} with Φ̂ defined in (13). Suppose that the hypotheses of Lemma 5 are fulfilled. Let g̃n be any minimizer of R̃ŵ∗,n over class G. We have with probability at least 1 − δ:
RP (̃gn)−inf g∈G RP(g) ≤ 2 max(p, 1 − p) ε
E[R′n(G)] + √
2 log(2/δ) n + 4ε2 √ log(4/δ) 2n +4 sup x∈X |̂η(x)−η(x)|,
as soon as n ≥ 2 log(4/δ)/ε2.
proof. Observe first that ||Φ||∞ ≤ maxk pk/ε and
RP (̃θ∗n) − inf θ∈Θ RP(θ) ≤ 2 sup
θ∈Θ ∣∣∣∣R̃ŵ∗,n(θ) − R̃w∗,n(θ)∣∣∣∣ + 2 sup θ∈Θ ∣∣∣∣R̃w∗,n(θ) − RP(θ)∣∣∣∣ . The result then directly follows from the application of Lemmas 1-5 combined with the union bound. Lemma 5. Let weights ŵ∗ be defined as in Theorem 3. Let ε ∈ (0, 1/2). Suppose that q ∈ (ε, 1 − ε). For any δ ∈ (0, 1), we have with probability larger than 1 − δ:
sup g∈G ∣∣∣∣R̃ŵ∗,n(g) − R̃w∗,n(g)∣∣∣∣ ≤ 2 ε2 √ log(2/δ) 2n + 2 sup x∈X |̂η(x) − η(x)|,
as soon as n ≥ 2 log(2/δ)/ε2.
proof.
Apply twice the Taylor expansion
1 x = 1 a − x − a a2 + (x − a)2 xa2 ,
so as to get
1 n′+/n = 1 q − n
′ +/n − q
q2 + (n′+/n − q)2 q2n′+/n ,
1 n′−/n = 1 1 − q − n′−/n − 1 + q (1 − q)2 + (n′−/n − 1 + q)2 (1 − q)2n′−/n .
This yields the decomposition
R̃ŵ∗,n(g) − R̃w∗,n(g) = − p q2 ( n′+ n − q ) 1 n n∑ i=1 I{g(X′i ) = −1, Y ′i = +1}
− 1 (1 − q)2 ( n′− n − 1 + q ) 1 n n∑ i=1 (1−η̂(X′i ))I{g(X′i ) = +1, Y ′i = −1}+ p(n′+/n − q)2 q2n′+/n 1 n n∑ i=1 I{g(X′i ) = −1, Y ′i = +1}
+ (n′−/n − 1 + q)2 (1 − q)2n′−/n 1 n n∑ i=1 (1−η̂(X′i ))I{g(X′i ) = +1, Y ′i = −1}+ 1 (1 − q)n n∑ i=1 (η(X′i )−η̂(X′i ))I{g(X′i ) = +1, Y ′i = −1}.
We deduce that∣∣∣∣R̃ŵ∗,n(g) − R̃w∗,n(g)∣∣∣∣ ≤ |n′+/n − q| ε2 ( 1 + |n′+/n − q| ( 1 n′+/n + 1 1 − n′+/n )) + n′−/n 1 − q supx∈X |̂η(x) − η(x)|.
By virtue of Hoeffding inequality, we obtain that, for any δ ∈ (0, 1), we have with probability larger than 1 − δ: ∣∣∣n′+/n − q∣∣∣ ≤ √ log(2/δ)2n , so that, in particular, min{n′+/n, 1 − n′+/n} ≥ ε − √ log(2/δ)/(2n). Moreover, still under this event, n′−/n ≤ 2(1 − q) if n ≥ log(2/δ)/(2ε2). This yields the desired result.
Appendix - Extension to IterativeWERM
As highlighted in Remark 2, the importance function can be expressed as a function of the ideal decision function in certain situations: Eq. (12) involves the regression function η(x), that defines the optimal (Bayes) classifier g∗(x) = 2I{η(x) ≥ 1/2} − 1. This simple observation paves the way for a possible incremental application of the WERM approach: in the case where the solution of the WERM problem considered outputs an estimate of the optimal decision function, it can be next re-used for defining and solving a novel WERM problem. Whereas binary classification based on PU data only aims at recovering a single level set of the posterior probability η(x), it is not the case of a more ambitious statistical learning problem, referred to as bipartite ranking, for which such an incremental version of WERM can be described.
Bipartite ranking based on PU data. In bipartite ranking, the statistical challenge consists of ranking all the instances x ∈ X through a scoring function s : X → R in the same order as the likelihood ratio Ψ(X) = (dF+/dF−)(X), or, equivalently, as the regression function η(x) = P{Y = +1 | X = x}, x ∈ X: the higher the score s(X), the more likely one should observe Y = +1. Let S = {s : X → R measurable} denotes the set of all scoring functions on the input space X. A classical way of measuring "how much stochastically larger" a distribution G on R than another one,H say, consists in drawing the "probability-probability plot":
t ∈ R 7→ (1 −H(t), 1 − G(t)), with the convention that possible jumps are connected by line segments (in order to guarantee the continuity of the curve). Equipped with this convention, this boils down to plot the graph of the mapping ROCH ,G : α ∈ (0, 1) 7→ ROCH ,G = 1 − G ◦ H−1(1 − α), where Γ−1(u) = inf{t ∈ R : Γ(t) ≥ u} denotes the pseudo-inverse of any cumulative distribution function Γ(t) on R. The closer to the left upper corner of the unit square [0, 1]2, the larger the distribution G is compared toH in a stochastic sense. This approach is known as ROC analysis. The gold standard for evaluating the ranking performance of a scoring function s is thus the ROC curve:
ROCs de f = ROCFs,−,Fs,+ ,
where Fs,+ and Fs,− denote the conditional distributions of s(X) given Y = +1 and given Y = −1 respectively, i.e. the images of class distributions F+ and F− by the mapping s(x). Indeed, it follows from a standard Neyman-Pearson argument that the ROC curve ROC∗ of strictly increasing transforms of η(x) is optimal with respect to this criterion in the sense that:
∀α ∈ (0, 1), ROCs(α) ≤ ROC∗(α), for any scoring function s. We set S∗ = {T ◦ η : T : (0, 1) :→ R}. A summary quantity of this functional criterion that is widely used in practice is the Area Under the ROC Curve (AUC in short), given by:
AUC(s) = ∫ 1 α=0 ROCs(α) dα,
for s ∈ S. Beyond its scalar nature, an attractive property of this criterion lies in the fact that it can be interpreted in a probabilistic manner, insofar as we have the relation: ∀s ∈ S,
AUC(s) = P { s(X) < s(X′) | (Y,Y ′) = (−1,+1)} + 1 2 P { s(X) = s(X′) | (Y,Y ′) = (−1,+1)} .
Denoting by (Xi,Yi), i ∈ {1, 2}, independent copies of the pair (X,Y) and placing ourselves in the situation where s(X)’s distribution is continuous, as observed in Clémençon et al. (2008), we have AUC(s) = 1 − LP(s)/(2p(1 − p)), where
LP(s) de f = P {(s(X1) − s(X2))(Y1 − Y2)) < 0} ,
is the ranking risk, the theoretical rate of discording pairs namely, that can be viewed as a pairwise classification risk. Hence, bipartite ranking can be formulated as the problem of learning a scoring function s that minimizes the ranking risk
LP(s) = EP′⊗P′ [
dP dP′ (X′1,Y ′ 1) dP dP′ (X′2,Y ′ 2) × I
{ (s(X′1) − s(X′2))(Y ′1 − Y ′2)) < 0 }] .
Now, using Eq. (12) and the fact that η = pΨ/(1 − p + pΨ), we have:
dP dP′ (x, y) = Φ(x, y) = p q I{y = +1}+1 − η(x) 1 − q I{y = −1} = p q I{y = +1}+ 1 − p (1 − q)(1 − p + pΨ(x)) I{y = −1}.
Therefore, it has been shown in Clémençon & Vayatis (2009) (see Corollary 5 therein) that for any s∗ in S∗,
dF+ dF− (X) = dFs∗,+ dFs∗,− (s∗(X)) almost-surely.
For any s candidate, setting Ψs(x) = dFs,+/dFs,−(s(x)), one can define
Φs(x, y) = p q I{y = +1} + 1 − p (1 − q)(1 − p + pΨs(s(x))) I{y = −1}.
From this formula, it is the easy to see how an incremental use of the WERM could be implemented.
• Start from an initial guess s for the optimal scoring functions (e.g. solve the empirical ranking risk minimization problem ignoring the bias issue)
• Estimate Φs from the (X′i ,Y ′i )’s and the knowledge of p, observing that one is not confronted with the curse of dimensionality in this case • Solve the Weighted Empirical Ranking Risk Minimization problem using the weight function
Φ̂s(x1, y1)Φ̂s(x2, y2),
which produces a new scoring function s and iterate.
Investigating the performance of such an incremental procedure will be the subject of future research.
Appendix - Inaccurate Prior Information about the Test Distribution
As noticed in section 2, it may happen that the rate of positive instances in the target population is approximately known only. Suppose that our guess for p is p̃ such that |p − p̃| ≤ ζ, with ζ ∈ (0, 1). Denote by P̃ the distribution over X × {−1,+1} under which X is drawn from p̃F+ + (1 − p̃)F− and such that P(X,Y)∼P̃{Y = 1 | X = x} = P(X,Y)∼P{Y = 1 | X = x} = η(x).
By a change of measure we have,
PP̃(Y , g(X)) = PP(Y , g(X)) + EP dP̃dP (X,Y) − 1  I{Y , g(X)} ,
which allows to bound the difference of the classification risks of g under P and P̃:∣∣∣RP̃(g) − RP(g)∣∣∣ ≤ EP ∣∣∣∣∣∣dP̃dP (X,Y) − 1 ∣∣∣∣∣∣  = 2| p̃ − p| ≤ 2ζ.
Appendix - Additional Numerical Experiments
In this Appendix, more details about the experiments carried out are provided.
Importance of reweighting for simple distributions
Introduce a random pair (X,Y) in [0, 1] × {−1,+1} where X | Y = +1 has for probability density function (pdf) f+(x) = (1 + α)xα, α > 0 and X | Y = −1 has for pdf f−(x) = (1 + β)(1 − x)β, β > 0. As in Section 2, the train and test datasets have different class probabilities p′ and p for Y = +1. The loss ` is defined as `(θ, z) = I{(x − θ)y ≥ 0} where θ > 0 is a learnt parameter. The true risk can be explicitely calculated. For θ > 0, we have
RP(θ) = pθ1+α + (1 − p)(1 − θ)1+β, and the optimal threshold θ∗p can be found by derivating the risk RP(θ). The derivative is zero when θ satisfies
p(1 + α)θα = (1 − p)(1 + β)(1 − θ)β. (14) Solving eq. (14) is straightforward for well-chosen values of α, β, which are detailed in fig. 4. The excess error E(p′, p) = RP(θ∗p′) − RP(θ∗p) for the diagonal entries of fig. 4 are plotted in fig. 5, in the infinite sample case.
The results of fig. 5 show that the optimum for the train distribution is significantly different from the optimum for the test distribution for the excess risk when the problem involves Bayes noise.
Generalities on real data experiments
Strategy to induce bias in balanced datasets In the two real data experiments described in the part concerning the MNIST experiment in the Appendix and in Section 4, the same strategy is used to induce class distribution bias or strata bias. Since both experiments involve a small test dataset, it
is kept intact, while we discard elements of the train dataset to induce bias between the train and test datasets. The bias is parameterized by a single parameter γ, such that when γ is close to one, there is little strata or class bias, while when γ approaches 0, bias is extreme.
The bias we induce is inspired by a power law, which is often used to model unequal distributions. Each value of a modality, i.e. a possible value of the stratum or class of an instance, is given by one of the values of the power law at random. Formally, the target train distribution {p′k}Kk=1 over a modality S ∈ {1, . . . ,K}, is defined for all 1 ≤ k ≤ K as
p′k = γ− bK/2c σ(k) pk∑K
l=1 γ − bK/2cσ(k) pk
,
where σ is a random permutation in {1, . . . ,K}. To generate a train dataset with modality distribution {p′k}Kk=1, we sample instances from the original train data setD◦n = {(X′i ,Y ′i , S ′i )}ni=1, where Y ′i is the class, S ′i is the modality. For MNIST experiment, S ′i = Y ′ i , while for Section 4, the value S ′ i is the stratum of the instance i. The output of the train dataset is notedDn, see Algorithm 1 for the detailed algorithm of the train dataset generation.
Algorithm 1 Biased training dataset generation Data: D◦n = {(X′i ,Y ′i , S ′i )}ni=1, {p′k}Kk=1 Result: Dn D← ∅ # Initialize the result index set. for k = 1, . . . ,K do Ik ← {i | 1 ≤ i ≤ n, S ′i = k} # Count the candidates for each modality. end msamp ← min(#I1, . . . , #IK) while msamp > 0 do
m1, . . . ,mK ←M(msamp, p1, . . . , pK) #M is the multinomial law. for k = 1, . . . ,K do
Dk ← RandSet(mk,Ik) # RandSet(n, X) is a random subset of n elements of X. Ik ← Ik \ Dk
end msamp ← min (#I1, . . . , #IK) D← D ∪ (
K⋃ k=1 Dk ) end Dn ← {(X′i ,Y ′i , S ′i ) | i ∈ D} ReturnDn
Models Both MNIST and ImageNet experiments compare two models: a linear model and a multilayer perceptron (MLP) with one hidden layer. Given a classification problem of input x of dimension d with K classes, precisely with d = 784,K = 10 for MNIST and d = 2048,K = 1000 for ImageNet data, a linear model simply learns the weights matrix W ∈ Rd×K and the bias vector b ∈ RK and outputs logits l = W>x + b. On the other hand, the MLP has a hidden layer of dimension h = b(d + K)/2c and learns the weights matrices W1 ∈ Rd,h,W2 ∈ {h,K} and bias vectors b1 ∈ Rh, b2 ∈ RK and outputs logits l = W>2 h(W>1 x + b1) + b2 where h is the ReLU function, i.e. h : x 7→ max(x, 0). The number of parameters for each dataset and each model is summarized in table 1.
The weight decay or l2 penalization for the linear model and MLP model are written, respectively
P = 1 2 ‖W‖ and P = 1 2 ‖W1‖ + 1 2 ‖W1‖.
Cost function The cost function is the Softmax Cross-Entropy (SCE), which is the most used classification loss in deep learning. Specifically, given logits l = (l1, . . . , lK) ∈ RK , the softmax function is γ : Rk → [0, 1]K with γ = (γ1, . . . , γK) and for all k ∈ {1, . . . ,K},
γk : l 7→ exp(lk)∑K j=0 exp(l j) .
Given an instance with logits l and ground truth class value y, the expression of the softmax crossentropy c(l, y) is
c(l, y) = K∑
k=1
I{y = k} log (γk(l)) .
The loss that is reweighted depending on the cases as described in Section 3 is this quantity c(l, y). The loss on the test set is never reweighted, since the test set is the target distribution. The weights and bias of the model that yield the logits are tuned using backpropagation on this loss averaged on random batches of B elements of the training data summed with the regularization term λ · P where λ is a hyperparameter that controls the strength of the regularization.
Preprocessing, optimization, parameters The images of ILSVRC were encoded using the implementation of ResNet50 provided by the library keras2, see Chollet et al. (2015), by taking the flattened output of the last convolutional layer.
Optimization is performed using a momentum batch gradient descent algorithm, which updates the parameters θt at timestep t with an update vector vt by performing the following operations:
vt = γvt−1 + η∇C(θt−1), θt = θt−1 − vt,
where η is the learning rate and γ is the momentum, as explained in Ruder (2016).
The parameters of the learning processes are summarized in fig. 6. The weight decay parameters λ were cross-validated by trying values on a logarithmic scale, e.g. for ImageNet {10−4, 10−3, 10−2, 10−1, 1} and then trying more fine-grained values between the two best results, e.g. for ImageNet 10−3 was best and 10−2 was second best so we tried {0.002, 0.003, 0.004, 0.005}. The standard deviation initialization of the weights was chosen by trial-and-error to avoid overflows. The learning rate was fixed after trying different values to have fast convergence while keeping good convergence properties.
Stratified information for ImageNet In this section, we detail the data preprocessing necessary to assign strata to the ILSVRC data. These were constructed using a list of 27 high-level categories found on the ImageNet website3 copied in Figure 7. Each ILSVRC image has a ground truth low
2https://keras.io/applications/ 3 http://www.image-net.org/about-stats
level synset, either from in the name of the training instance, or in the validation textfile for the validation dataset, that is provided by the ImageNet website. The ImageNet API 4 provides the hierarchy of synsets in the form of is-a relationships, e.g. a flamingo is a bird. Using this information, for each synset in the validation and training database, we gathered all of its ancestors in the hierarchy that were in the table fig. 7. Most of the synsets had only one ancestor, which then accounts for one stratum. Some of the synsets had no ancestors, or even several ancestors in the table, which accounts in for extra strata, either a no-category stratum or a strata composed of the union of several ancestors. The final distribution of the dataset over the created strata is summarized by Figure 8. Observe the presence of a no_strata stratum and of unions of two high-level synsets strata, e.g. n00015388_n01905661. A definition provided by the API of each of the synsets involved in the strata
is given in fig. 9.
Classes bias experiment forMNIST
The impact of the bias correction in the multi-class supervised learning setting described in Section 2 is illustrated on a widely used dataset for studying classification tasks: the MNIST dataset.
The MNIST dataset is composed of images X ∈ Rd of digits and labels being the value of the digits. In our experiment, we learn to predict the value of the digit so we have K = 10 classes corresponding to digits between 0 and 9. The dataset contains 60, 000 images for training and 10, 000 images for testing, all equally distributed within the classes. There is therefore no class bias between train and test samples in the original dataset.
Bias between classes is induced using the power law strategy described above. We deal with the classification task associated to (X,Y) with a linear model or a MLP with one hidden layer that optimizes the softmax cross-entropy (SCE) using momentum gradient descent. We compare the uniform weighting of each instance in the train set (corresponding to the case where there is no reweighting described in eq. (2)) with the reweighting of each instance using the proportion of each label Y for the train and test datasets as described in eq. (7). Precisions about the model and parameters are given in paragraph dealing with Preprocessing, optimization, parameters in the Appendix.
The optimization dynamics are summarized in fig. 10. We report the median over 100 runs of these values for the test set and a fixed random sample of the train set. For the test set, we represent 95% confidence-intervals in a lighter tone. The x-axis corresponds to the number of iterations of the learning process.
4http://image-net.org/download-API
For the uniform weights, we see that the misclassification rate is pretty low for the train set, but poor for the test set. By reweighting the instances, we see that we favor low error over the test set, which gives a miss probability reduced by half.

Review summaries:
This paper targets the transfer learning problem. It wants to construct the unbiased estimator of the true risk for the target domain based on data from the source domain. To have the unbiased estimator, samples in the source domain are weighted based on some auxiliary information of both the source domain data distribution and the target domain data distribution. Especially, similar to previous works, the paper first assumes P(Y=1) is known for the target domain, and give a generalization bound for learning on the target domain. Then they consider two more concrete problems, one is learning with stratified information when the conditional probability given the stratified information of the source domain is equal to that of the target domain. Then the paper considers PU learning. Generalization bounds are also given for these two problems. Finally, the paper shows some empirical results showing the reweighting effect of its proposal.