Weighted Empirical Risk Minimization: Transfer Learning based on Importance Sampling
Authors: Robin Vogel
Mastane Achab
Charles Tillier
Stéphan Clémençon
Venue:  (2020)
Keywords: statistical learning theory
importance sampling
positive unlabeled (PU) learning
selection bias

Abstract: We consider statistical learning problems, when the distribution $P'$ of the training observations $Z'_1,\; \ldots,\; Z'_n$ differs from the distribution $P$ involved in the risk one seeks to minimize (referred to as the \textit{test distribution}) but is still defined on the same measurable space as $P$ and dominates it. In the unrealistic case where the likelihood ratio $\Phi(z)=dP/dP'(z)$ is known, one may straightforwardly extends the Empirical Risk Minimization (ERM) approach to this specific \textit{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 $\Phi(Z'_i)$. Although the \textit{importance function} $\Phi(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 $\Phi(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.

Under review as a conference paper at ICLR 2020
WEIGHTED EMPIRICAL RISK MINIMIZATION: TRANSFER LEARNING BASED ON IMPORTANCE SAMPLING
Anonymous authors Paper under double-blind review
ABSTRACT
We consider statistical learning problems, when the distribution P' of the training observations Zi, Z 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. the unrealistic case where the likelihood ratio (b()) = (P)) 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 with weights OZZ)) Although the importance function O(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 ss 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 D(Z)'s '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.
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 al. (199)..
In the standard setup, Z is random variable (r.v. in short) that takes its values in a feature space Z with distribution P. θ is a parameter space and f O x Z R, is (measurable) loss function. The risk is then defined by: VO e O
R₂(0) = Bp [((0, Z)),
(1)
and more generally for any measure Q on Z: Ro(0) = Sf ((0, =))((2) 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 and the risk (T) must be replaced by an empirical counterpart (or a possibly smoothed/penalized version of it), typically:
R₂(()) Σ ((0.7) = =Rp, (0).
(2)
where P,, = (1/n) 6z, is the empirical measure of and 6, denotes the Dirac measure at any point z. With the design of successful algorithms such 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 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 supae Rp(()) - Ry(()) under various complexity assumptions for the functional class F |E(0, -): : d E O (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-learml 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

---

Under review as a conference paper at ICLR 2020
selection issues in machine-leariing are now the subject of much attention in the literature, see Bolukbasi et al. (216)) Zhao et al. (2017), Burns et al. (2019), [L et al. (2016) or Huang et al. (2007) including a broad range of applications such as face
In the context of face analysis, research detection, face recognition or face attribute detection, machine learning algorithms trained with baised training data, e.g. in terms of gender ethnicity, raise concerns about fairness in machine learning. Unfair algorithms may induce systemic undesired disadvantages for specific social groups, see Das ct 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,, Z, 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 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 a very particular case of Transfer Learning (see e.g. Pan & Yang 2010), Beno),BBBBDaaaa BendDavid et al. (2010) and Storkey (2009)), research area currently receiving much attention in the literature and encompassing general situations where the ieformmtiio/knowlleee would like to transfer may take form in the target space very different from that in the source space (referred to as domain adaptation).
one
Weighted ERM (WERM). In this paper, investigate conditions guaranteeing that values for the parameter / that nearly minimize (T) can be obtained through minimization of a weighted version of the empirical risk based on the Zj's, namely
(0) Rp... (0).
(3)
where Pw. = (1/n) Σi= w7oz and (W,, wr,) R", is a certain weight vector. Of course, ideal weights w" are given by the likelihood function ((z) (dP/dP")()) w/ ((Z,) for i e (1, .... n).
In this case, the quantity (3) is obviously an unbiased estimate of the true risk (
Er [R. (0) Rr(()).
(4)
and generalization bounds for the Rp-risk excess of minimizers of Rw can be directly established by studying the concentration properties of the empirical process related to the 7 and the class of functions ((()) .) # E O) (see section 2 below). However, the importance function &b is unknown in general, just like distribution P. the major purpose of this article show that, in far from uncommon situationn, the (ideal) weights wt can be estimated from the Z/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 [Beker Davis (208)), with strata statistically represented in different manner in the test and training populations, positive-unlabeled learning (PU-learning, see e.g. du Plessis et al.) (2014)). In each 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 +b 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 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-Icarning, with generalization guarantees. Illustrative numerical experiments are displayed in section 4 while some concluding remarks are collected section 5 Proofs and additional results are deferred to the Supplementary Material.
2 IMPORTANCE SAMPLING RISK MINIMIZATION WITH BIASED DATA
Here and throughout, the indicator function of any event & is denoted by I(8). the sup norm of any bounded function h Z - IR by |l We place ourselves in the framework of statistical learning
2

---

Under review as a conference paper at ICLR 2020
based on biased training data previously introduced. As 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
1 H
Rw J (0)
w E(0, Z,).
(5)
namely the (unbiased) Importance Sampling estimator of based on the instrumental data 7, Zz The following result describes the performance of minimizers ff 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 e and T are both bounded functions. For dT, ..... oT independent Rademacher random variables (i.e. symmetric [-1, 1J-valued r.v's), independent from the Z,'s, we define the Rademacher average associated to the class of function FF R2(F)) == E. [suPaee _ Σ> o,,( (() This quantity can be bounded by metric entropy methods under appropriate complexity assumptions on the class F, it is for instance of order Oz(1/ vn) when F is a VC major class with finite VC dimension, see e.g. Boucheron al. (2005).
Lemma 1. With probability at least 1 - 6, we have: Vn 2 1,
2 log(1/0)
Rr(O,)) min Ry(0) 4||0
+ 21
sup E(0,2) (Z
Of course, when P = P. we have += = I and the bound stated above simply describes the performance of standard empirical risk minimizers. The proof is based on the standard bound
R min (()) s sup 6E
Re (0) deG
E Ren (e (0)
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 simplistic form and can be easily estimated from the Z 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 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 8:X- 1-1, +1) and the loss function is given by ((g, (x, = Mgg(x) yt for all g in G and any (x,y) E 1-11 +1). The distribution P of the random pair (X, Y) can be either described by X's marginal distribution j(dx) and the posterior probability n7x) = P(Y +1 | X = x) or else by the triplet (p, F., F-) where p = PlY +1} and F (dx) is X's conditional distribution given Y = 0ll with o f-, +). 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,, ri). .... (X,, Y,) is described by the triplet (p', F., F_) with p' < p. The likelihood function takes the simple following form
(xx,)) y) = I(y +1] +1 2 I[y = -1) -1) 11
1
P----- def (6y).
which reveals that it depends on the label solely, and the ideally weighted empirical risk process is
_1 Σ Ig(x)) -11 +|+ 1- 1-p1 Σ Ug(x) = +1).
Rw (g)g In general the theoretical rate p' is unknown and one replaces 6 with
(6)
D' -
(g)) P Σ n² =Y
lg(X)) = -] 1- n'
Σ
Mg(X==+1] - +1)
3

---

Under review as a conference paper at ICLR 2020
where ni, = Ei. IY;; = =YY) and p(y) I[y fly= +1/mp/n|,+ +Iyy -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 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' E (E. 1-8). For any E (0, 1), we have with probability larger than - 6:
log(2/6)
sup geg
RS (g() Rur (n()) S
8
2n
as soon 2 2 log(2/8)/62
See the Appendix for the technical proof. Consequently, minimizing 7 nearly boils down to minimizing (6). Combining Lemmas and the result below.
we immediately get the generalization bound stated in
Corollary 1. Suppose that the hypotheses of Lemma are fulfilled. Let En be any minimizer of Rir over class G. We have with probability at least 1 6:
2 max(p. 1-p)
1og(2/8)
log(4/8)
Rg( inf Rp(g)= Ge
S
2 (BI++
n
g
2n
as soon as 2 2 log(4/0)/ where R²(G)) (1/ (1/n)E, E (ggg(X) Yill
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 to show that this remains true for more general problems. Observe in addition that the bound in Corollary [1 deteriorates 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.
decays to zero: the
Remark 1. Although the quantity (7) can be viewed as a cost-sensitive version of the empirical classification risk based on the (X, Yj)'s (see e.g. Bach et al. (2006)), we point out that the goal pursued here not to achieve an appropriate trade-off between type I and rype Il errors in the P classification problem as in biometric applications for inslance (i.e. optimization of the (F,, (G.FF. F-R-ROC curve at a specific point) but to transfer knowledge gained in analyzing the biased data drawn from P' to the classification problem related 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 (Sugyyaaa et al. (2008) for covariate shift adaptation problems (i.e. supervised situations, where the conditional distribution of the output given the input information 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-Leible 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 for the PU learning problem (see section 3). Lemmal [T Jssummes that the exact importance function 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 RISK MINIMIZATION GENERALIZATION GUARANTEES
Through two important and generic examples, relevant for many applications, 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.
4

---

Under review as a conference paper at ICLR 2020
3.1 STATISTICAL LEARNING FROM BIASED DATA A STRATIFIED POPULATION
A natural extension of the simplistic problem considered in section is multiclass classification in stratified population. The random labels Y and Y' are supposed take their values in (1, J) say, with / 2 1, and each labeled observation (X, Y) belongs to a certain random stratum S in (1, .... K] with 1. Again, the distribution P of a random element Z (X. Y.S) may be described by the parameters (( F F 13 J. 1 1 k I K} where F is the conditional distribution of X given (Y.S) (j. and PI PoxrS--(Y j.S = k). Then, we have
dP(x,y,)) Σ
My j. k) (x(),
and considering a distribution Pt with J Fjx but possibly different class probabilities Pj the likelihood function becomes
K
dP dPd ().
ΣΣ
PM il j.s= def p6y s).
P'jx
more general framework can actually encompass this specific setup by defining 'meta-strata" in (1, .... J/ x {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 defined by labels.
Learning from biased stratified data. Consider a general mixture model, where distributions and P' are stratified over K 1 strata. Namely, (X, and Z' (X",S') with auxiliary random variables S and S' (the strata) valued in (1, assuming that the conditional distribution of X given K). However, stratum probabilities Ps = P(S = k) and P/- P(S k) may possibly be different. In this setup. the likelihood function depends only on the strata and can be expressed in very simple form, as follows:
K). We place ourselves in a stratum-shjf context,
is the same that of X' given S'
denoted by (dx), for any & E (1,
dP d (x,
Σ I[s 2)
Ps def d(s).
PN
In this case, the ideally weighted empirical risk writes
R.
Σ E(0, Z
I(S = Pt P/
If the strata probabilities P '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 's computed from the training data:
10) RS
40, ().
aS k)
P
E=1
1=1
with ni. Σx ISS = w/ HSS)) and ((s) = Σ
I[s = k)mpx/n(
bound for the excess of risk given in Theorem T that can be viewed as a generalization of Corollary |
Theorem 1. Let E (0, 1/2) and assume that P E (8, (or 1,..., K. Let 6r be any minimizer
of Riv as defined in (8) over class Q We have with probability least - 6:
2 max; Ps
2B(R, 2 (og(2/0)
4L
log(4K/0)
Rp(0")
inf Rp(O)= S 8c0)
2
2n
as soon as (ogg(4//)) where R2(FF) (1/N)B,[Suppe)) Σn 0,0 Z,I,, and the loss is bounded by L sup ((0,z).
Just like in Corollary D the bound in Theorem T explodes when vanishes, which corresponds to the situation where a stratum & (1...., K) is very poorly represented in the training data, í.e. when P << Pt. Again, highlighted by the experiments carried out, reweighting the losses in frequentist (ERM) approach guarantees good generalization properties a specific setup only, where the training information, though biased, is sufficiently informative.
5

---

Under review as a conference paper at ICLR 2020
3.2 POSITIVE- UULLBEEED LEARNING
Relaxing the stratum-shift assumption made in the previous subsection, the importance function becomes more complex and writes:
dP
k) Ps dFF (x), k=1 P dFF
Φ(x,s) dp (x,
where F5 and F2, are respectively the conditional distributions of X given S = k and of X' given S' k. The Positive-Unlabeles (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. (2077)) provides a typical example of this situation. Re-using the notations introduced in section the testing and training distributions P and P are respectively described by the triplets (p, F.) and (q, F., F), where F = pF. + (1- is the marginal distribution X. Hence, the objective pursued is to solve binary classification task, based the sole observation of training sample pooling data with positive labels and unlabeled data, denoting the theoretical fraction of positive data among the dataset. As noticed in du Plessis al. (2014) (see also Du Plessis et al. (2015), Kiryo function can be expressed in a simple manner, as follows: dF 1 - Mly -1] I- q dF (x)lly 11.
the PU problem.
et al. (2077), the
((x.)) X (-1, +1), Φ(x. y) Muy +1] --
4
Based on an i.i.d. sample (x, K7), of p (which can also be estimated from PU data, see e.g. Du Plessis & Sugiyama (2044) and using that F_ (1/(1 (F pF-), one may obtain estimators of q. F. and F by computing n²,/n= (1/m) 1 UY; +1), F, (1/n',) Σ HY,; = +1J0x; and == (1/n() Σn= I[Y; -1 However, plugging these quantities into ( do not permit to get a statistical version the importance function, insofar as the probability measures F. and F are mutually singular with probability one, as soon F. is continuous. Of course, as proposed in du Plessis et al. (2014), methods (e.g. kernel smoothing) to build distribution estimators, that ensures absolute continuity but subject to the curse of dimensionality. However, WERM can still be applied in this case, by observing that: Vg E G,
(X", Y drawn from p" combined with the knowledge
+11,
may statistical
22
Il((())) = 11, Y' = +1] + 1-q
Rp(g) -p + Ep
Hg((x)) = +1, Y' = =-1]
(10)
which leads the weighted empirical risk
2p
Σ [lxxx)= n1 6Y
Σ Mg(x)) = + +1).
-11
(11)
R BP
Minimization of (1T) yields rules 8n 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 this case being quite similar to (
Theorem 2. Lei & E (0, 1/2). Suppose that E (E, 1) Let En be any minimizer of the weighted
empirical risk 11 over class G. We have with probability at least 1- 8:
2 max(2p, 1) 2B(R
2log(2/0)
4(2p 1)
log(4/0)
Rp(ga) inf Rp(g) - geG
6²
2n
as soon as n 2 2 ( where R,(G) = (1 (I/p)) EE (g((( # YJII-
Remark 2. Let 17x)) = PIY +1 X = x) denote the posterior probability and recall that (dF+/dF-)Ge /x) ((1 (L1)pp))((())((111 - -x))). Observing that
Φ(x,y) - +1)
1 - nイxx
1 1-q Ily=
(12)
q
in the case when an estimate TTxx) of 17x) is available, one can perform WERM using the empirical weight function
(x. y) = nP "h -y - Ily=
1- 77x)
(13)
nt.
1- nnn
A bound that describes how this approach generalizes, depending the accuracy of estimate can be easily established, for more details refer to Theorem 3 in the Supplementary Material, where is also discussed how to exploit such formulas in order to design incremental WERM procedures.

---

Under review as a conference paper at ICLR 2020
4 NUMERICAL EXPERIMENTS
This section illustrates the impact of reweighting by the likelihood ratio classification performances. as a special case of the general strategy presented Section 2 first simple illustration on known probability distributions highlights the impact of the shapes of the distributions the importance of reweighting. This example illustrates in the safipe case that separable or almost separable data do not require reweighting. in contrast 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 the Appendix, as well
experiment 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 illustrate reweighting with stratified population and strata distribution bias or strata bias. The code of the experiments can be found at https://ddt /drive /r
google. wwt/criin/////eee
[W]]
We focus on the learning from biased stratified data setting introduced in Section 3.] by leveraging the ImageNet Large Scale Visual Recognition Challenge (ILSVRC); well-known benchmark for the image classification task, see Ruusakkvsky 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 test dataset. ImageNet 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, c.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 network ResNet50 introduced in He et al.] (2015). was trained for classification on the training dataset of ILSVRC. The encodings XI..... X,, belong a -is-dimmnsiooal space.
encoding is the flattened output of the last convolutional layer of the
total of 33 strata are derived from a list of high-level categories provided by ImageNe The construction of the strata is postponed to the Appendix. By default, strata probabilities pa and pl for 1 S k I 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 S S 1, we set the strata train probabilities such that P = --K:/Jjj ps 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 strata bias. When y is close to one, there is little to no strata bias. contrast, when y approaches O, strata bias is extreme. Model
Reweighting
miss rate
top-5 error
Train Test
Unif. T =1
0.344
0.130
0.25
Linear
Strata /
0.329
0. 0.120
0.20
Probability
Class +
0.328
0.119
0.15
No bias
0.297
0.102
0.10
Unif. T =
0.371
0.143
0.05
MLP
Strata
0.364
0.138
0.00
Class O
0.363
0.138
Strata
No bias
0.316
0.111
Comparison of ps 's and pç's.
Table of results.
Figure 1: Results for the strata reweighting experiment with ImageNet.
http://ww. wmwge net. www..iiagenee..or/bbbbtittoe stats
7

---

Under review as a conference paper at ICLR 2020
3.0
0.45
0.200
Train Test
Train
Train
0.40
Test
0.175
Test
0.150
Tap 5 errar
2.0
0.100
0.25
1.5
Unif.
Strata
0.20
Strata
Unif.
0.050
0.075
Unif.
Strata
Class
0.15
Class
Class
1.0
No bias
No bias
No bias
0.10
0.000
10000
20000
0
10000
20000
10000
20000
Dynamics for the SCE.
Dynamics for the miss rate.
Dynamics for the top-5 emror
Figure 2: Dynamics for the linear model for the strata reweighting experiment with ImageNet.
Train Test
Train
Train
0.40
Test
0.175
Test
2.5
0.150
0.35
2.0
Miss rate
0.30
Top-5 5 error
0.125
0.100
0.25
Unif.
Unif.
0.075
Unir.
Strala
0.20
Strala
0.050
Strata
kar Ay
Class
0.025
1.0
0.000
10000
20000
10000
20000
10000
20000
Dynamics for the SCE.
Dynamics for the miss rate.
Dynamics for the top-5 error.
Figure 3: Dynamics for the MLP model for the strata reweighting experiment with ImageNet.
The models used are a linear model and 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. [] For comparison, we added two reference experiments: one which reweights the train instances by the class probabilities, which we do not know in 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 lincar 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, simple change of measure shows that the target risk may be viewed as the expectation given by the importance function 4 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.
weighted version of the basic empirical risk, with ideal weights
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Francis Bach, David Heckerman, and Eric Horvitz. Considering cost asymmetry in learning classifiers, 2006.
Jessa Bekker and Jesse Davis. Beyond the selected completely random assumption for learning from positive and unlabeled data. CoRR, abs/ abs/1809.03207, 2018. URL http:hht:///axiv..oo wwtpeiiii.rr//bbbo / 1809.03207
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wort- man 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 survey of some recent advances. ESAIM: Probability and Statisties, 9:323-375, 2005.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymp- totic Theory of Independence. OUP Oxford, 2013.
Kaylee Burn,, 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.It 2015.
Stephan Clémençon and Nicolas Vayatis. Empirical performance maximization based on linear rank statistics, In NIP,, 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-4155 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-87) 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.
Abbijit 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, 1355:133 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. ICML, ICML' 15, pp. 1386-1333 1394. JMLR.org. 2015. URL
http://dl acm. www.iiatiiniiiiccoooom..ooo ctt.::omn.c...mmmmmo000005511111
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.03388, 2015. wtt.hhtp///aaxi.or///baaaa
03385

---

Under review as a conference paper at ICLR 2020
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. Positive- unlabeled 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: 1rXXiv:904.000 0022// 2019.
Sinno Jialin Pan and Qiang Yang. A survey transfer learning. IEEE Transactions Knowledge and Data Engineering, (2(10):1345-1355 Oct 2010. ISSN 1041-4347. doi: 10.1109/TKDE222001191
Sebastian Ruder. An overview of gradient descent optimization algorithms. CoRR, abs/1609.0474) 2016. URLpttt:://rxxii.rrg abs 1609. 04747
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang. Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg. and Fei- Fei Li. Imagenet large scale visual recognition challenge. CoRR, hes//140.0075, 2014. URL http://arxiv org abs//499. 0575
Amos Storkey. When training and test sets 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 Kei-Wei Chang. Men also like shopping: Reducing gender bias amplification using corpus-level constraints. In EMNLP, 2017. 2017.
APPENDIX TECHNICAL PROOFS
Here detail the proofs of the results stated in the article and discuss their connection with related work.
PROOF LEMMA 1
Let ö E (0, 1). Applying the classic maximal deviation bound stated in Theorem 3.2 of Boucheron al. 2005) the bounded class K {z Z ((2)l(0,2) :
O), we obtain that, with
probability at least 1 ô:
V log((1/0)
sup
R (0) 8EB
Rw (0) 2E (2()
|| sup (C(0.z) z)1 (Zzexx
n
In addition, by virtue of the contraction principle, we have K,KK S (, almost-surely. The desired result can be thus deduced from the bound above combined with the classic bound
R₂(0,)
min Rp()) s 2 sup R (0) R (+)) AEO
AeG
PROoF LEMMA 2
Apply twice the Taylor expansion
X-
(x 2)
d
xa²
10

---

Under review as a conference paper at ICLR 2020
so to get
1
nl,/n D'
p²² + (n/,/n p¹)²
n///n
p'
p2nnr/n
n''nn - 1 p'
+ (n'In-1 p') (1 (1-p')nn'
n'/nn
1 1- p'
(1 - p')
This yields the decomposition
p
n/4
1 R p¹
Rw (g) (1)))
[g((;)) = Y +11
p²2
n
11 im1
1 1- p
nn'
Mg((x)) = +1, v/ = = p(n, /n - p')²
Σ
1 + p¹
1g(()) = -1, 1/ =
(1 p')
p2
E=1
1=1
(1 p)( /n + p¹)²
Hg(()) = +1, --
(1- 11p'>'''/1
We deduce that
Rw (g)) - R8)
In_/nn p'l
| In,n/n [1+
p'l
P
+
1-p
8²
nt,/n
nt,/n
By virtue of Hoeffding inequality, we obtain that, for any ō E (0, 1), we have with probability larger than 1 6:
log(2/0)
h4//np'1 p'|=
2n
so that, in partieular, min(x(, /n, 1 1 n2,/n)) vlog(2/0)((2n), This yields the desired result.
PROOF OF COROLLARY M
Observe first that ||o]|oo S max(p, p)/E and
Rp inf Rg(g) S sup
Riz (g() Ro n(0) 2 sup
Rw- Ro(x)
gEg
gEG
geg
The result then directly follows from the application of Lemmas
12 combined with the union bound.
PROoF THEOREM 1
Observe first that || S max Pk/E and
R₂(O,) inf Rp( s 2 sup 8ee
(0) (0) + 2 sup (0)) Rr(O/. 6e0
He
The result then directly follows from the application of Lemmas
1 combined with the union bound.
Lemma 3. Let & E (0, 1/2). Suppose that P/ E (8, 1- for ke (1, K). For any 5 E (0, 1), we have with probability larger than 1 ō:
2L
log(2K/0)
sup RS (0) Ru S 6
82
2n
as soon as 2 2log(2K/0)/ where L = sup z).
PROOF.
Apply the Taylor expansion
x-a
(x 2)
x
d
xa²
11

---

Under review as a conference paper at ICLR 2020
to get for all & E (l.....KK) K)
1
nn/n Pk
(n//n- -PP
ngin
Pk
Pk
This yields the decomposition
K Z2)
pulri/n /n pb)
Ri (0) Rw
Σ
[10,
11S; k)
Pk
pt
11
km1
Pk
n
We deduce that
Re (0) Ra (0)
L
In pŠlPx
(1+
Ing/n PQl
n/g1n
By virtue of Hoefiding inequality, we obtain that, for any & E (I...., and 5 E (0, 1), we have with probability larger than 1 1-d 6:
log(2/0)
b6/n Pál -
2n
so that, by a union bound, maxg(nf/m) /n) 2 8- (log(2k/0)/(2n) This yields the desired result.
PROOF OF THEOREM 2
Observe first that ||0]lso S max(2p, 1)/8 and
Rp(ga) inf Rp(g) s sup gEG
R ((8) geG
2 sup ( Ro(x)
geg
with weighted empirical risk (g) defined in The result then directly follows from the application of Lemmas] combined with the union bound.
Lemma 4. Let e (0, 1/2). Suppose that q E (e. 1-8). 8). For any 6 (0, 1), we have with probability larger than 1 - 6:
R Rg)) Ro) 2(2p+1)
log(2/6)
sup gEgi
as soon 2 2
PROOF.
Apply twice the Taylor expansion
x-
(x a) xa²
x
d²
So to get
1
n
(n',/n 9)
nt,/n
q
q²
n |n
n'/nn +
(n'_/n nn- + 9)2 222
n'/nn
1-q q
(1 (1-6) 9)
This yields the decomposition
2p
n'
Rw (g) Ry (g)
q
llg(X)) -1, Y, +11
q²
1=1
n'
Ig((X) = +1, r -11 2p(n', /n 9)
+
Hg((') = -1, =
(1 2)²
g2n'/In /n
(n - 9)
Mg((() +1, +1, =
(1 1 i=1
12

---

Under review as a conference paper at ICLR 2020
We deduce that
R Ry d(0)
w//n-
2p 2p + I/,/n q
2p
1
8²
n/,/n
n',
By virtue of Hoeffding inequality, we obtain that, for any ò E (0, 1), we have with probability larger than 1 d
1/4//n - of log(2/5)
2n
so that, in particular, min(n',/n /n, 1 - n1,/n) -- vlog(2/0)((2n). This yields the desired result.
ALTERNATIVE APPROACH FOR POSITIVE- UNIARREE LEARNING
OX, fj all i E [I....,n) n) with T defined (13). Suppose that the hypotheses of Lemma are fulfilled. Let gn be any minimizer of Rir n class G. We have with probability at least
Theorem 3. Let W
max p. 1 pp)
2 12g(2
log(4/6)
(- Rp(g) gEG
BIR
+4 sup (7)xx)
2n
xeX
as soon as n 2 2 log(4/0))/²
PROOF.
Observe first that ||0]|co 3 max; ps/E and
Rp
inf RP) s 2 sup ( (0) + 2 sup (w) Ro(0). Ae
REG
The result then directly follows from the application of Lemmas 15 combined with the union bound.
Lemma S. Let weights w be defined as in Theorem 3 Let & E (0, 1/2). Suppose that E (8, 1 8). For any ö (0, 1), we have with probability larger than 1 5:
log(2/6)
sup REG
RS (8) (Rw-n(()) s
+ 2 sup [7(xx) - 77(x)b
8
2n
xeX
as soon n 2
PROOF.
Apply twice the Taylor expansion
x- a
(x a)²
xa²
so as to get
n1, /
(n',/n /n 9)2
nt,/n
4
q²
n2n1__1 In'/n
n'_ nn/n- +
(n'_/n 9)²
n'nnn
1
1-4
q
(1 (1- 9)
(1- nn'
This yields the decomposition
n'
- - I(((X)) 1 Y +11
Rw (g) Ry (g)
q
q²
n'
Σ
(1-7(x = +1, Y - pln /n- 9)
Σ II(())= =1, =1)
+
(1 9)2 n
g'n'/In
1=1
(n' /n - + 2)
Σ (1-Txx))]((X} +1, -1+ 1
(xXX)) = +1. =--1))
(1 - n''nn
q)n
i=1
i=1
13

---

Under review as a conference paper at ICLR 2020
We deduce that
Ri (g) R (00) |n Iw//n-g
(1+Inn/nn
n''n"
n1,/n + 1 1 nt, nl_/n\
sup nj(x) 17(x))
6²
1-q
xe
By virtue of Hoeffding inequality, we obtain that, for any d E (0, 1), we have with probability larger than 1 -
log(2/0)
|/4/n- - -/=
2n
so that, in partieular, min(n'_/n, 1 nl//n) | 2 8- vlog(2/0)((2n)) Moreover, still under this event, nn/n 2(1 9) if log(2/8)/(26). This yields the desired result.
APPENDIX EXTENSION TO ITERATIVE WERM
As highlighted in Remark 2, the importance function be expressed function of the ideal decision function in certain situations: Eq. (12) involves the regression function r7(x), that defines the optimal (Bayes) classifier g' (xx) (I(n)x)) 2 1/2] 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 single level set of the posterior probability 77(x), is not the case of 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 E X through scoring function likelihood ratio 4(X)= (dF=/dF_)(K
functinn s : X R the same order as the or, equivalently, as the regression function 17(x) = P(Y = x X: the higher the score s(X), the more likely one should observe
+1. Let S= : R. measurable) denotes the set of all scoring functions the imput space X. A classical way of measuring "how much stochastically larger" a distribution G on RR than another one, H say, consists in drawing the "probability probability
"probabilityprrobbblity plot":
e R + (1 H(), G-G()).
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 : a E (0, ROCHg -00
where (4) = infir E R : r()) 2 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, 1J2. the larger the
distribution & is compared to H in a stochastic sense. This approach is known as ROC analysis. The gold standard for evaluating the ranking performance of a scoring function s thus the ROC curve:
ROC, ROC
where Fs,+ and F,.- denote the conditional distributions of s(X) given +1 and given -1 respectively, f.e. the images of class distributions F, and F_ by the mapping s(x). Indeed, it follows from a standard Ssyman-Pearson argument that the ROC curve ROC* of strictly increasing transforms of yy(x) is optimal with respect to this criterion in the sense that:
Va (0, 1), ROC, ROC
for any scoring function s. We set [T o n T: 1) :- RJ. 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) = ' ROC,(a) dax
for E S. Beyond its scalar nature, attractive property of this criterion lies in the fact that it can be interpreted a probabilistic manner, insofar as we have the relation: Vs E S,
AUC(s) = P < ( + P( = s(X') 1 (X,Y)) (-1,+1))
--1,
14

---

Under review as a conference paper at ICLR 2020
Denoting by (X,, Y,), i E {1, 2), independent copies of the pair (X. 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) Lp(s)/(2((1 p)), where
Ly(s) def - -
Y2)) < 0),
is the ranking risk. the theoretical rate of discording pairs namely, that be viewed as pairwise classification risk. Hence, bipartite ranking can be formulated as the problem of learning a scoring function that minimizes the ranking risk
dP (X
dP 11) dp (X2, Y2) x ((((())) -(xss((()))))) s(x)) Y2)) < <0
Lp(s) = Epap
dp dp
Now, using Eq. 12 and the fact that p - p pP)) we have:
dPb (x,y) (xx 1iy
dP
1 - (xx) [[y - - +1|
1-p
Ily -1), 1).
1 q
q) - + pT(x))
Therefore, it has been shown in Clémençon & Vayatis 2009) (see Corollary 5 therein) that for any s* S
dF dFr.t (s (x)( almost-surely. dF_ (X) dF
dF+
For any s candidate, setting Vx(x) //FFF (,d,F,,s(555 (s(x)), one can define
0,(x,) PIly +1) (1 - (1 p pYY,(s(x))) I(y=-1)
1-p
From this formula, it is the easy to see how an incremental use of WERM could be implemented.
Start from initial guess for the optimal scoring functions (e.g. solve the empirical ranking risk minimization problem ignoring the bias issue)
Estimate o from the (X', Y,''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
( y1 (2).
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 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 Ip - pl S L. with & E (0, 1). Denote by P the distribution over X x +1, under which X is drawn from pf, + (1 - F) and such that (x
x] Po X x] n7x)).
By change of measure we have,
dP {ap (x, r)
(x 11) s(X)]]
Pp(Y # g(X) = PP(Y g(X)) + Bp
which allows bound the difference of the classification risks of g under and P:
dP (X.
- & Ep
2 p 24.
dp
APPENDIX - ADDITIONAL NUMERICAL EXPERIMENTS
In this Appendix, more details about the experiments carried out provided.
15

---

Under review as a conference paper at ICLR 2020
IMPORTANCE REWEIGHTING
DISTRIBUTIONS
Introduce a random pair (X, Y) in [0, lJ x (-1,+1) where X Y = +1 has for probability density function (pdf) (x(
arxx", 0 and X x|y=-! has for pdf f-(x) (1 + (011 B 0. As in Section 2 the train and test datasets have different class probabilities p' and for Y +1. The
loss l defined as ((0,2) [[(x d)y O) where 0 learnt parameter.
The true risk can be explicitely calculated. For 0 O, we have
Ry(()= p0 p)(1 0)
and the optimal threshold 6r be found by derivating the risk (p) The derivative is when 0 satisfies
p(1 a') (1 p) +1) 0f
(14)
Solving eq. (14) is straightforward for well-chosen values of a, which are detailed in fig. The
excess eтror E(p'. p) Rp(O,)) Rx((t)) for the diagonal entries of fig. are plotted in fig. the infinite sample case.
(a.
(0.0) 0) (1/2,122)
(1,1)
(2,2)
(--p
VI-p Npt
[0. 1]
p'-(1-p)
1-
1-p
Figure 4: Optimal parameters 8" for different values of ar,..
D,
0.5, 35-00 0.5
1,8-1
2,8 2
1.50
1.04
1.25
2.5
1.00
0.75
0.50
1.0
0.25
0.0
0.0
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.0
0.2
0.4
0.6
0.8
1.0
a 0-000-m0
a 0 0.5
a= 1,8-1
a= 2=2.8m2
0.8
0.8
0.8
0.8
0.6
0.6
0.6
0.6
0.0
0.50
6.0
0.50 0.75
6.0
0.50
0.75
0.0
0.50
0.75
Figure 5: Pdf's and values of the excess risk E(p', p) for different values of a,
The results of fig. 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 the Appendix and Section 4 the same strategy used to induce class distribution bias or strata bias. Since both experiments involve small test dataset, it
16

---

Under review as a conference paper at ICLR 2020
is kept intact, while we discard elements of the train dataset induce bias between the train and test datasets. The bias is parameterized by single parameter y, such that when is close to one, there is little strata class bias, while when y approaches 0, bias is extreme.
The bias we induce inspired by a power law, which is often used to model unequal distributions. Each value of modality, Lee. possible value of the stratum class of an instance, is given by one of the values of the power law at random. Formally, the target train distribution (p) K over a modality k=1
(I.....K] K), defined for all s kk K
Pk
Pk
Σ
where or is random permutation in (1...., K).
To generate a train dataset with modality distribution (p% we sample instances from the original train data set De ((X; Vi S S'D where Y; is the class, S is the modality. For MNIST experiment, S = Y, while for Section 4 the value S is the stratum of the instance The output of the train dataset is noted Dr, see Algorithm| for the detailed algorithm of the train dataset generation.
Algorithm Biased training dataset generation
Data: D. ((X;, YY SD)) (p//ke
Result: Dn
D
Initialize the result index set.
for k I....., K do
Ia fillsis n. k]
# Count the candidates for each modality.
end
Msamp < min(#I I........ #Ik)
while Msxpmpp 0 do
m1..... mgg Mmm- Pl..... Pk)
# M is the multinomial law.
for k = I, I...., K do
D RandSet(m,, II)
# RandSSt(n, X) is a random subset of elements of X.
I - I Dx Di
end
Msamp <- min ( #Ix)
K U D2
D DU
end
D, - 10X, S D
Return Dn
Models Both MNIST and ImageNet experiments compare two models: a linear model and multilayer perceptron (MLP) with one hidden layer. Given a classification problem of input x of dimension d with classes, precisely with 784, K = 10 for MNIST and 2048, = 1000 for ImageNet data, linear model simply learns the weights matrix W Raxk and the bias vector b E R and outputs logits = W x b. On the other hand, the ML. has a hidden layer of dimension h 1(d + K)/2] and learns the weights matrices W1 Rdd.A W₂2 (h, K) and bias vectors bi RA, RR,b, b2 E K and outputs logits = w,J h(WT x + bi) + b2 where / is the ReLU function, i.e. h max(x, 0). The number of parameters for each dataset and each model is summarized in table
The weight decay or 12 penalization for the linear model and MLP model are written, respectively
p = 2 [|WI and p = 2 11 || lW
Cost function The cost function is the Softmax Cross- pooos-Entropy (SCE), which is the most used classification loss in deep learning. Specifically, given logits / (4.....Ikg) R& the softmax function is y & [0. 1]x with y (y1...., yx) and for all & (1, exp(k)
7v 1 1 E1= exp(l))
17

---

Under review as a conference paper at ICLR 2020
Model
Database
Linear
MLP
MNIST
7,850
315,625
ImageNet
2,049,000
4,647.676
Table 1: Number of parameters for each model.
Experiment
MNIST Section
ImageNet Section 4
Net weights std init oro
0.01
0.01
Weight decay A Unif
0.01
0.002
Weight decay Strata
X
0.003
Weight decay 2 Class
0.01
0,003
Weight decay Sym data Learning rate 7)
X
0.001
0.01
0.001
Momentum
0.9
0,9
Batch size B
1,000
1,000
MLP hidden layer size
397
1,524
Figure 6: Parameters of the MNIST and ImageNet experiments: Section 5 and Section 4
Given an instance with logits / and ground truth class value y, the expression of the softmax cross- entropy c(l.y) is
dl.y) Σ fly ko (rx())).
The loss that is reweighted depending on the cases as described in Section iis this quantity c(l, 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 elements of the training data summed with the regularization term d where is a hyperparameter that controls the strength of the regularization.
Preprocessing, optimization, parameters The images of ILSVRC were encoded using the im- 2 plementation of ResNet50 provided by the library keras see Chollet et al. (2015), by taking the flattened output of the last convolutional layer.
Optimization is performed using momentum batch gradient descent algorithm, which updates the parameters 6, timestep with an update vector v, by performing the following operations:
y?;- + +
= 6-1-11 V,,
where 77 the learning rate and is the momentum, explained in Ruder 2016).
The parameters the learning processes are summarized in fig. 6 The weight decay pa- rameters 1 were vrlss-valddated by trying values (10-1, 10-3, 10-2 10-1 1) and then trying more fine-grained values between the two best results, e.g. for ImageNet 1 was best and 10 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-one error to avoid overflows. The learning rate was fixed after trying different values have fast convergence while keeping good convergence properties.
logarithmic scale, e.g. for ImageNet
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 website copied in Figure] 7 Each ILSVRC image has a ground truth low
Phttps//keras.ooapppiaaaai
http::/www. image-maeeeeee net. www.//bbouotsseeeoeeooooooeeeeee
18

---

Under review as a conference paper at ICLR 2020
categories
synset
images per synset
Total images
amphibian
94
591
56K
animal
3822
732
2799K
appliance
51
1164
59K
bird
856
949
812K
covering
946
819
774K
device
2385
675
1610K
fabric
262
690
181K
fish
566
494
280K
flower
462
735
339K
food
1495
670
1001K K
fruit
309
607
188K
fungus
303
453
137K
furniture
187
1043
195K
geological formation
151
838
127K
invertebrate
728
573
417K
mammal
1138
821
934K
musical instrument
157
891
140K
plant
1666
600
999K
reptile
268
707
190K
sport
166
1207
200K
structure
1239
763
946K
tool
316
551
174K
tree
993
568
564K
utensil
86
912
78K
vegetable
176
764
135K
vehicle
481
778
374K
person
2035
468
952K
Figure 7: Original categories used to construct the strata for the experiment of Section
19

---

Under review as a conference paper at ICLR 2020
level synset, either from in the name of the training instance, in the validation textfile for the validation dataset, that is provided by the ImageNet website. The ImageNet API 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 for extra strata, either 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 g Observe the presence of no_ strata stratum and of unions of two high-level synsets strata, e-g. 000005388_m01905500 A definition provided by the API of each of the synsets involved in the strata
no
instances (thousands)
250000
200000
150000
100000
50000
84419810 oo Sasgee
Paeee ou
O80E TEW
ELEY E500
I 199506 You BRESTOOD
09
TOO 1
9891 pettrrou EOU
524.0 11500
$22
15P20Z10V
LE367iZOu
13399 Crou
2.9 Spou
EESS0 SOEEE you 1000 T2 CoEpEE Eou Eou
POEEEEE E4100pu
5,00
O00TT000BEE OB0ERTE EQU DOD--9ET G0ES BESTODDU
38E51000
you
you
Figure& 8: Distribution of the ImageNet train dataset over the created strata which definitions are given in fig.
given in fig.
CLASSES BIAS EXPERIMENT FOR MNIST
The impact of the bias correction in the multi-class supervised learning setting described in Section 2 is illustrated widely used dataset for studying classification tasks: the MNIST dataset.
The MNIST dataset is composed of images X e Rd of digits and labels being the value of the digits. In our experiment, learn predict the value of the digit so have K = 10 classes corresponding to digits between 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 linear model or 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 values for the test set and fixed random sample of the train set. For the test set, represent 95% confidence-interval in a lighter tone. The x-axis corresponds to the number of iterations of the learning process.
We report the median over 100 runs of these
20

---

Under review as a conference paper at ICLR 2020
Strata name
Definition
n00015388
n01861778
animal, animate being, beast (...) mammal, mammalian
no strata
n03183080
device
n03122748
covering
n04524313
vehicle
n00015388
n01905661
animal, animate being, beast (...)
invertebrate bird
500015388
n01503061
animal, animate being, beast (...) structure, construction animal, animate being, beast (...) device furniture, piece of furniture, (...) fruit animal, animate being, beast (...) vegetable, veggie, veg
n04341686
n00015388
n01661091
reptile, reptilian musical instrument, instrument
n03183080
n03800933
n03405725
n13134947
538815388
n02512053
fish geological formation, formation sports equipment
n07707451
n04451818
tool appliance
n02729837
n09287968
n04285144
100015388
n01627424
animal, animate being, beast (...) amphibian foodstuff, food product fungus
n07566340
2992868
n04516672
utensil
n03309808
fabric, cloth, material, textile animal, animate being, beast (...)
n00015388
n00017222
n11669921
plant, flora, plant life appliance
flower
n02729837
n03183080
device
n03183080
n04451818
device
tool
n03122748
n03183080
covering
device
n04285146
n04524313
sports equipment
vehicle
104341686
n04524313
structure, construction
vehicle
n07566340
n07707451
foodstuff, food product
vegetable, veggie, veg
n03183080
n04524313
device
vehicle
Figure 9: Definitions of the strata created for the experiments in Section 4 which frequencies
given in fig.
21

---

Under review as a conference paper at ICLR 2020
0.650
0.15
Train
Train
0.625
Test
Test
0.600
0.13
0.575
Miss rate
0.12
0.550
0.525
0.500
0.10
0.20
Test
Train
Uniform Weighted
0.09
Weighted
Unifarm
0.450
0.08
Probability
0.15
5000
10000
15000
5000
10000
15000
Linear model: cost.
Linear model: miss rate.
0.05
0.600
0.10
Train
Train
0.00
0.575
Test
Test
2
5
8
0.550
0.525
Miss rate
0.08
0.500
Comparison of pk's and pf,'.
Uniform
0.06
Uni forform
Weighted
Weighted
0.100
0.05
5000
10000
15000
5000
10000
15000
MLP model: cost.
MLP model: miss rate.
Figure 10: Dynamics for the class reweighting experiment with MNIST.
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 miss probability reduced by half.
22


Reviews:
[{"review_id": "SkgpaoVCKr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors consider the problem of a mismatch between the distribution of the training observations and the test distribution (a transfer learning setup). The paper seems technically sound but it is not easy to read. Even Section 2 it is difficult to read.\n \n-  Main drawback: Please define the weights w_i of Eq. (5) in Section 2. \n\n- I have a question: is it possible to extend your work considering Multiple Importance Sampling and Generalized  Multiple Importance Sampling  schemes? please discuss.\n\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "HyeE_uUstB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper aims to show that we can estimate a density ratio for using the importance weighted ERM from the given sample and some auxiliary information on the population. Several learning bounds were proven to promote the use of importance weighted ERM.\n\n========================================================\nClarity:\nThis paper is mathematically concise and understandable overall. Here, I list some comments on the clarity.\n\n1. I found that the word auxiliary information has been used extensively from the very beginning when referring to the estimation of the density ratio. However, there is no explanation what kind of auxiliary information we need to achieve this goal until page 5, where the authors discussed about strata random variable as the additional information (if I didn't make a mistake). I believe there is a better way to introduce the intuition about what kind of auxiliary information is sufficient to make learning possible.\n\n2. For the proposed PU-learning setting (case-control) by du Plessis et al. 2014, the assumption is the marginal density unlabeled data is identical to the test marginal density and the positive data is drawn from the class-conditional probability p(x|y=1). I am not sure if it's appropriate to discuss about it in page 2, where authors want to discuss about the situation where the train stage and test stage have different class probabilities.\n\n3. In page 3, authors suggested that \n\"it is very common that the fraction of positive instances in the training dataset is significantly lower than the test set (p' < p), supposed to be known here\". I have two questions about this.\n3.1 Does this mean we suppose to know p', p, or both? I am aware that the appendix discussed about when p is misspecified.\n3.2  I am not convinced that it is common that p' < p. It maybe nice to cite some findings or provide more explanation why it is the case. \n\n4. In page 4, authors mentioned few shot learning problem, then describe that it is a scenario where almost no training data with positive labels is available. Is this the same problem setting as the well-known few-shot learning one? In my recognition, few-shot learning is the scenario where we want to learn from small data, e.g., p can be 0.5 but we have a very small number of data but balanced (n_pos=n_neg). Instead of few-shot, I feel it might be better to use the word like \"extreme class prior or extreme class probability scenario\".\n\n5. In page 3, I'm not sure why authors suddenly focused on binary classification with varying class probabilities. A bit of introduction or motivation would be helpful. As far as I understand this is learning from class-prior shift scenario (or class-prior change), which also has been considered in the literature. Authors may consider citing some work in this line and discuss the difference in the findings of the proposed results and the existing work.\n\n========================================================\nComments:\nMy impression is the novelty of this paper is modest. It is known that importance weighted ERM is unbiased and consistent to the true risk. I believe there exists theoretical analysis of learning under using WERM, especially in the situation where the weight is importance weight function is known. For Lemma 2 and Corollary 1, it is suggest that p' should not be too small but also the author suggested that p' < p. I would like to know more about the setting the authors described here, e.g., what is the example of the practical p' and p. \n\n1. Eq. (11) is identical to the proposed unbiased risk estimator of PU-learning in du Plessis et al. (NeurIPS2014). It would be better to clarify that they are equivalent (Eq. (3) of PU-learning in du Plessis et al. (NeurIPS2014)). They also provided a generalization error bound and the analysis when p is misspecified. More theoretical analysis of this empirical risk estimator for case-control PU learning (e.g., estimation error bound) can also be found in the following paper:\n\nNiu et al. Theoretical Comparisons of Positive-Unlabeled Learning against Positive-Negative Learning, NeurIPS2016.\n\n2. How many trials were run in the experiments? It would be nice to see the standard error not only the mean result. It is known that importance weighting method can have high variance and it might be expected that WERM may have high variance yet have better performance. It would be helpful to explain how to read the table, e.g., what is No Bias, top-5 error. Why half of the table are in gray?\n\nAlthough the paper is well-written overall. I found that it is difficult to quantify a novelty of this paper. I believe the goal, as suggested by page 2, is to \"set theoretical grounds for the application of ideas behind weighted ERM\". As the author suggested, this approach has been studied quite extensively both theoretically and experimentally. It would be helpful to explain what is new and the relationship of the proposed methods or bounds with the existing work to highlight the novelty of this paper.\n\nFor these reasons, I vote a weak reject for this paper.\n\n========================================================\nPotential typos:\n1. There are \"du Plessis et al.\" and \"Du Plessis et al.\" in this paper. This indicates the same person and it should be better to use only one convention (I think du Plessis is preferable).\n\n=========================================================\nAfter Rebuttal:\nThanks for the reader for clarifying my several questions. I have read the rebuttal.\nHowever, I feel that in the current form, I would like to stay with the same evaluation. The clarification of the difference between theoretical results is definitely crucial to highlight the novelty of the paper. I would like to add more comments on the PU learning part. I hope the authors find the comments useful.\n\n1. du Plessis et al. (ICML 2015) \"Convex formulation for learning from positive and unlabeled data\", which was already cited in the paper, suggested that if we replace the 0-1 loss to a loss that does not have the symmetric property (e.g., logistic, squared), the form of the unbiased estimator can be different from Eq. (11) in this submitted paper (please see the paper for more details).\n \n2. Although we obtain an unbiased risk estimator by the WERM-like method, in deep learning, minimizing such a risk may lead to overfitting, as we can see from Eq. (11) that although it is a cost-sensitive risk, it still treats all unlabeled data as negative. If we have a complex enough model, to minimize the risk, a classifier may classify all unlabeled data to negative, which undoubtedly leads to overfitting. This is discussed in Kiryo et al. (NeurIPS 2017), which also has been already cited in the submitted paper too.\n\nNext, I would like to add more comments on the experiment.\n\nFor the experiments, I appreciate the authors' effort to do experiments on such a big dataset. In that case, it may be nice to also include an experiment on a smaller dataset, e.g., MNIST, which I believe this has already been conducted but it was in the appendix, to the main body of the paper as well to strengthen the experimental results in the paper. \n\nI think the writing in the experiment section can be improved. For example, I don't see the first paragraph, which has lots of texts, contains much information. Also, instead of suggesting a reader to see Figure 1 for comparison, we may use more space to interpret the result. If I didn't miss it, Figure 2 and Figure 3 were never explained or referred to in the main body. In that case, we may consider removing these figures and adding the result on MNIST dataset. \n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1gYfQuTYH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nThe paper is a theoretical study of transfer learning, and a generalization of other learning problems including transfer learning, learning from stratified data and PU learning. It assumes that when some auxiliary information is known, generalization bound can be given by only minimizing a reweighted loss of the biased source domain data. However, the auxiliary information proposed in this paper is difficult to be got. Thus, the practical use of this paper may be limited. The paper also lacks discussion with related theoretical work (such as generalization bound of PU learning). Due to these reasons, I rate a weak reject for the paper.\n\nIn Sec. 2, to have an unbiased risk estimator as well as a generalization bound, the prior probability P(Y=1) should be known. However, the paper fails to provide any practical way to estimate this value. Although in the auxiliary part, some results when such a value cannot be accurately estimated are given, estimation methods are also required for the method to be practical. Moreover, such as result is already studied in Sugiyama et al. (2008). Thus, the novelty of this part is limited. \n\nIn Sec. 3.1, the paper focuses on the learning from stratified data problem, when some stratified information s for the data are given. The paper further assumes P(x|S=k) = P(x’|S’=k). First, in a general learning problem, no matter transfer learning or not, only information of x and y is available. To justify that the information s is available, some real applications should be given as motivations. Moreover, the assumption on the stratified data, i.e. P(x|S=k) = P(x’|S’=k) and P(S=k) \\neq P(S’=k) should also be justified. \n\nIn Sec. 3.2, the generalization bound of PU learning is also studied before in for example [Niu et al., Theoretical Comparisons of Positive-Unlabeled Learning against Positive-Negative Learning. NIPS 2016]. Discussion on the relationship between these theoretical results should be given. Also, in the experimental part, there is no empirical results comparing the proposed method with the existing PU learning methods. Since one of the main contributions of this paper is on PU learning, empirical studies should also be provided to show the superior of the proposed method. \n\n----------------------------\nThe rebuttal is subjective (without enough support but expressions such as \"we believe\", \"there is no point\") and fails to address my concern. I will not raise my score.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper aims to address transfer learning by importance weighted ERM that estimates a density ratio from the given sample and some auxiliary information on the population. Several learning bounds were proven to promote the use of importance weighted ERM.

Reviewers and AC feel that the novelty of this paper is modest given the rich relevant literature and the practical use of this paper may be limited. The discussion with related theoretical work such as generalization bound of PU learning can be expanded significantly. The presentation can be largely improved, especially in the experiment part. The rebuttal is somewhat subjective and unconvincing to address the concerns.

Hence I recommend rejection.
Decision: Reject