Title: Weighted Empirical Risk Minimization: Transfer Learning based on Importance Sampling

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.

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 space Z with distribution P, Θ is a parameter space and : Θ × Z → R + is a (measurable) loss function. The risk is then defined by: ∀θ ∈ Θ,

EQUATION

and more generally for any measure Q on Z: R Q (θ) = 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 Z 1 , . . . , Z n drawn from P and the risk (1) must be replaced by an empirical counterpart (or a possibly smoothed/penalized version of it), typically:

EQUATION

where P n = (1/n) n i=1 δ Z i 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 (θ) -R P (θ)| 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 (θ) = R P w,n (θ),

(3)

where P w,n = (1/n) n i=1 w i δ Z i and w = (w 1 , . . . , w n ) ∈ 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):

EQUATION

and generalization bounds for the R P -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 -Risk Minimization 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

EQUATION

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 n i=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 O P (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,

R P ( θ * n ) -min θ∈Θ R P (θ) ≤ 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

R P ( θ * n ) -min θ∈Θ R P (θ) ≤ 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

EQUATION

In general the theoretical rate p is unknown and one replaces (6) with

EQUATION

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(1p)/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 -δ:

R P ( g n ) -inf g∈G R P (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 σ [sup g∈G | n i=1 σ i I{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.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,k dF 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 F k (dx), for any k ∈ {1, . . . , K}. However, stratum probabilities p k = 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} p k 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} p k p k .

If the strata probabilities p k '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:

EQUATION

with

n k = n i=1 I{S i = k}, w * i = φ(S i ) and φ(s) = K k=1 I{s = k}np k /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 -δ:

R P ( θ * n ) -inf θ∈Θ R P (θ) ≤ 2 max k p k ε        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 << p k . 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} p k p k dF k dF k (x),

where 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 2017)), the likelihood/importance function can be expressed in a simple manner, as follows:

F

F = pF + + (1 -p)F -is the marginal distribution of X.

∀(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/(1p))(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,

EQUATION

which leads to the weighted empirical risk 2p

EQUATION

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 -δ:

EQUATION

)

in the case when an estimate η(x) of η(x) is available, one can perform WERM using the empirical weight function

EQUATION

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 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 X 1 , . . . , X n 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 p k 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-K/2 /k p k 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. 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.

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 → Φ(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

R P ( θ * n ) -min θ∈Θ R P (θ) ≤ 2 sup θ∈Θ R w * ,n (θ) -E R w * ,n (θ) .

Proof of Lemma 2:

Apply twice the Taylor expansion

1 x = 1 a - x -a a 2 + (x -a) 2 xa 2 , so as to get 1 n + /n = 1 p - n + /n -p p 2 + (n + /n -p ) 2 p 2 n + /n , 1 n -/n = 1 1 -p - n -/n -1 + p (1 -p ) 2 + (n -/n -1 + p ) 2 (1 -p ) 2 n -/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 2 n + /n 1 n n i=1 I{g(X i ) = -1, Y i = +1} + (1 -p)(n -/n -1 + p ) 2 (1 -p ) 2 n -/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, 1n + /n} ≥ εlog(2/δ)/(2n). This yields the desired result.

Proof of Corollary 1:

Observe first that ||Φ|| ∞ ≤ max(p, 1p)/ε and

R P ( g n ) -inf g∈G R P (g) ≤ 2 sup g∈G R w * ,n (g) -R w * ,n (g) + 2 sup g∈G R w * ,n (g) -R P (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 ||Φ|| ∞ ≤ max k p k /ε and

R P ( θ * n ) -inf θ∈Θ R P (θ) ≤ 2 sup θ∈Θ R w * ,n (θ) -R w * ,n (θ) + 2 sup θ∈Θ R w * ,n (θ) -R P (θ) .

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 a 2 + (x -a) 2 xa 2 ,

so as to get for all k ∈ {1, . . . , K}

1 n k /n = 1 p k - n k /n -p k p 2 k + (n k /n -p k ) 2 p 2 k 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}       - p k p 2 k n k n -p k + p k (n k /n -p k ) 2 p 2 k n k /n       .

We deduce that

R w * ,n (θ) -R w * ,n (θ) ≤ L ε 2 K k=1 |n k /n -p k |p k 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, max k {n k /n} ≥ εlog(2K/δ)/(2n). This yields the desired result.

Proof of Theorem 2:

Observe first that ||Φ|| ∞ ≤ max(2p, 1)/ε and

R P ( g n ) -inf g∈G R P (g) ≤ 2 sup g∈G R w * ,n (g) -R w * ,n (g) + 2 sup g∈G R w * ,n (g) -R P (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 a 2 + (x -a) 2 xa 2 , so as to get 1 n + /n = 1 q - n + /n -q q 2 + (n + /n -q) 2 q 2 n + /n , 1 n -/n = 1 1 -q - n -/n -1 + q (1 -q) 2 + (n -/n -1 + q) 2 (1 -q) 2 n -/n .

This yields the decomposition

R w * ,n (g) -R w * ,n (g) = - 2p q 2 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 q 2 n + /n 1 n n i=1 I{g(X i ) = -1, Y i = +1} + (n -/n -1 + q) 2 (1 -q) 2 n -/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, 1n + /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 -δ:

R P ( g n )-inf g∈G R P (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 ||Φ|| ∞ ≤ max k p k /ε and

R P ( θ * n ) -inf θ∈Θ R P (θ) ≤ 2 sup θ∈Θ R w * ,n (θ) -R w * ,n (θ) + 2 sup θ∈Θ R w * ,n (θ) -R P (θ) .

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 .

Apply twice the Taylor expansion

1 x = 1 a - x -a a 2 + (x -a) 2 xa 2 , so as to get 1 n + /n = 1 q - n + /n -q q 2 + (n + /n -q) 2 q 2 n + /n , 1 n -/n = 1 1 -q - n -/n -1 + q (1 -q) 2 + (n -/n -1 + q) 2 (1 -q) 2 n -/n .

This yields the decomposition

R w * ,n (g) -R w * ,n (g) = - p q 2 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 q 2 n + /n 1 n n i=1 I{g(X i ) = -1, Y i = +1} + (n -/n -1 + q) 2 (1 -q) 2 n -/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}. 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 sup x∈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, 1n + /n} ≥ εlog(2/δ)/(2n). Moreover, still under this event, n -/n ≤ 2(1q) if n ≥ log(2/δ)/(2ε 2 ). This yields the desired result.

Appendix -Extension to Iterative WERM:

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 → (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 ROC H,G : α ∈ (0, 1)

→ ROC H,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 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 is thus the ROC curve:

ROC s de f = ROC F s,-,F s,+ ,

where F s,+ and F s,-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), ROC s (α) ≤ 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 ROC s (α) 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) .

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

R P (θ) = pθ 1+α + (1 -p)(1 -θ) 1+β ,

and the optimal threshold θ * p can be found by derivating the risk R P (θ). The derivative is zero when θ satisfies

EQUATION

)

Solving eq. ( 14) is straightforward for well-chosen values of α, β, which are detailed in fig. (α, β)

(0, 0) (1/2, 1/2) (1, 1)

(2, 2) 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.

θ * p [0, 1] (1-p) 2 p 2 +(1-p) 2 1 -p √ 1-p √ p+ √ 1-p

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 } K k=1 over a modality S ∈ {1, . . . , K}, is defined for all 1 ≤ k ≤ K as

p k = γ -K/2 σ(k) p k K l=1 γ -K/2 σ(k) p k ,

where σ is a random permutation in {1, . . . , K}.

To generate a train dataset with modality distribution {p k } K k=1 , we sample instances from the original train data set

D • n = {(X i , Y i , S i )} n i=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 noted D n , 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 )} n i=1 , {p k } K k=1 Result: D n D ← ∅ # Initialize the result index set. for k = 1, . . . , K do I k ← {i | 1 ≤ i ≤ n, S i = k} # Count the candidates for each modality. end m samp ← min(#I 1 , . . . , #I K ) while m samp > 0 do m 1 , . . . , m K ← M(m samp , p 1 , . . . , p K ) # M is the multinomial law. for k = 1, . . . , K do D k ← RandSet(m k , I k ) # RandSet(n, X) is a random subset of n elements of X. I k ← I k \ D k end m samp ← min (#I 1 , . . . , #I K ) D ← D ∪ K k=1 D k end D n ← {(X i , Y i , S i ) | i ∈ D} Return D n Models Both MNIST

1 ∈ R d,h , W 2 ∈ {h, K} and bias vectors b 1 ∈ R h , b 2 ∈ R K and outputs logits l = W 2 h(W 1 x + b 1 ) + b 2

where h is the ReLU function, i.e. h : x → 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 W 1 + 1 2 W 1 .

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 = (l 1 , . . . , l K ) ∈ R K , the softmax function is γ : R k → [0, 1] K with γ = (γ 1 , . . . , γ K ) and for all k ∈ {1, . . . , K}, A definition provided by the API of each of the synsets involved in the strata n 0 0 0 1 5 3 8 8 _ n 0 1 8 6 1 7 7 8 n o _ s t r a t a n 0 3 1 8 3 0 8 0 n 0 3 1 2 2 7 4 8 n 0 4 5 2 4 3 1 3 n 0 0 0 1 5 3 8 8 _ n 0 1 9 0 5 6 6 1 n 0 0 0 1 5 3 8 8 _ n 0 1 5 0 3 0 6 1 n 0 4 3 4 1 6 8 6 n 0 0 0 1 5 3 8 8 _ n 0 1 6 6 1 0 9 1 n 0 3 1 8 3 0 8 0 _ n 0 3 8 0 0 9 3 3 n 0 3 4 0 5 7 2 5 n 1 3 1 3 4 9 4 7 n 0 0 0 1 5 3 8 8 _ n 0 2 5 1 2 0 5 3 n 0 7 7 0 7 4 5 1 n 0 4 4 5 1 8 1 8 n 0 2 7 2 9 8 3 7 n 0 9 2 8 7 9 6 8 n 0 4 2 8 5 1 4 6 n 0 7 5 6 6 3 4 0 n 0 0 0 1 5 3 8 8 _ n 0 1 6 2 7 4 2 4 n 1 2 9 9 2 8 6 8 n 0 4 5 1 6 6 7 2 n 0 3 3 0 9 8 0 8 n 0 0 0 1 5 3 8 8 n 0 2 7 2 9 8 3 7 _ n 0 3 1 8 3 0 8 0 n 0 0 0 1 7 2 2 2 _ n 1 1 6 6 9 9 2 1 n 0 3 1 8 3 0 8 0 _ n 0 4 4 5 1 8 1 8 n 0 3 1 8 3 0 8 0 _ n 0 4 5 2 4 3 1 3 n 0 4 3 4 1 6 8 6 _ n 0 4 5 2 4 3 1 3 n 0 7 5 6 6 3 4 0 _ n 0 7 7 0 7 4 5 1 n 0 4 2 8 5 1 4 6 _ n 0 4 5 2 4 3 1 3 n 0 3 1 2 2 7 4 8 _ n 0 3 1 8 3 0 8 0 strata Classes bias experiment for MNIST 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.

γ k : l → exp(l k ) K j=0 exp(l j

The MNIST dataset is composed of images X ∈ R d 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. 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.

:

Weighted Empirical Risk Minimization -Generalization GuaranteesThrough 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.

http://www.image-net.org/about-stats

https://keras.io/applications/

http://www.image-net.org/about-stats

http://image-net.org/download-API

Figures and Tables:

k 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. (

Figure 1: Results for the strata reweighting experiment with ImageNet.

Figure 2: Dynamics for the linear model for the strata reweighting experiment with ImageNet.

Figure 3: Dynamics for the MLP model for the strata reweighting experiment with ImageNet.

4. The excess error E(p , p) = R P (θ * p ) -R P (θ * p ) for the diagonal entries of fig. 4 are plotted in fig. 5, in the infinite sample case.

Figure 4: Optimal parameters θ * for different values of α, β.

Figure 5: Pdf's and values of the excess risk E(p , p) for different values of α, β.

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 ∈ R d×K and the bias vector b ∈ R K and outputs logits l = W x + b. On the other hand, the MLP has a hidden layer of dimension h = (d + K)/2 and learns the weights matrices W

Figure 8: Distribution of the ImageNet train dataset over the created strata which definitions are given in fig. 9 .

Figure 9: Definitions of the strata created for the experiments in Section 4, which frequencies are given in fig. 8.

Figure 10: Dynamics for the class reweighting experiment with MNIST.

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. (

Table content: <table/>

Comparison of p k 's and p k 's.

Table content: <table><tr><td/><td/><td/><td colspan="4">Model Reweighting miss rate top-5 error</td></tr><tr><td>Probability</td><td>0.15 0.25 0.20 0.10 0.05</td><td>Train Test</td><td>Linear MLP</td><td>Unif. Φ = 1 Strata Φ Class Φ No bias Unif. Φ = 1 Strata Φ</td><td>0.344 0.329 0.328 0.297 0.371 0.364</td><td>0.130 0.120 0.119 0.102 0.143 0.138</td></tr><tr><td/><td>0.00</td><td>Strata</td><td/><td>Class Φ</td><td>0.363</td><td>0.138</td></tr><tr><td/><td/><td/><td/><td>No bias</td><td>0.316</td><td>0.111</td></tr><tr><td/><td/><td/><td/><td colspan="2">Table of results.</td><td/></tr></table>

) Original categories used to construct the strata for the experiment of Section 4. 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 Figure8. Observe the presence of a no_strata stratum and of unions of two high-level synsets strata, e.g. n00015388_n01905661.

Table content: <table><tr><td>categories</td><td colspan="3"># synset # images per synset Total # images</td></tr><tr><td>amphibian</td><td>94</td><td>591</td><td>56K</td></tr><tr><td>animal</td><td>3822</td><td>732</td><td>2799K</td></tr><tr><td>appliance</td><td>51</td><td>1164</td><td>59K</td></tr><tr><td>bird</td><td>856</td><td>949</td><td>812K</td></tr><tr><td>covering</td><td>946</td><td>819</td><td>774K</td></tr><tr><td>device</td><td>2385</td><td>675</td><td>1610K</td></tr><tr><td>fabric</td><td>262</td><td>690</td><td>181K</td></tr><tr><td>fish</td><td>566</td><td>494</td><td>280K</td></tr><tr><td>flower</td><td>462</td><td>735</td><td>339K</td></tr><tr><td>food</td><td>1495</td><td>670</td><td>1001K</td></tr><tr><td>fruit</td><td>309</td><td>607</td><td>188K</td></tr><tr><td>fungus</td><td>303</td><td>453</td><td>137K</td></tr><tr><td>furniture</td><td>187</td><td>1043</td><td>195K</td></tr><tr><td>geological formation</td><td>151</td><td>838</td><td>127K</td></tr><tr><td>invertebrate</td><td>728</td><td>573</td><td>417K</td></tr><tr><td>mammal</td><td>1138</td><td>821</td><td>934K</td></tr><tr><td>musical instrument</td><td>157</td><td>891</td><td>140K</td></tr><tr><td>plant</td><td>1666</td><td>600</td><td>999K</td></tr><tr><td>reptile</td><td>268</td><td>707</td><td>190K</td></tr><tr><td>sport</td><td>166</td><td>1207</td><td>200K</td></tr><tr><td>structure</td><td>1239</td><td>763</td><td>946K</td></tr><tr><td>tool</td><td>316</td><td>551</td><td>174K</td></tr><tr><td>tree</td><td>993</td><td>568</td><td>564K</td></tr><tr><td>utensil</td><td>86</td><td>912</td><td>78K</td></tr><tr><td>vegetable</td><td>176</td><td>764</td><td>135K</td></tr><tr><td>vehicle</td><td>481</td><td>778</td><td>374K</td></tr><tr><td>person</td><td>2035</td><td>468</td><td>952K</td></tr><tr><td>Figure 7:</td><td/><td/><td/></tr><tr><td/><td/><td>.</td><td/></tr></table>

Peer review (iclr2020):
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. ======================================================== Clarity: This paper is mathematically concise and understandable overall. Here, I list some comments on the clarity. 1. 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. 2. 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. 3. In page 3, authors suggested that *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. 3.1 Does this mean we suppose to know p*, p, or both? I am aware that the appendix discussed about when p is misspecified. 3.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. 4. 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*. 5. 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. ======================================================== Comments: My 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. 1. 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: Niu et al. Theoretical Comparisons of Positive-Unlabeled Learning against Positive-Negative Learning, NeurIPS2016. 2. 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? Although 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. For these reasons, I vote a weak reject for this paper. ======================================================== Potential typos: 1. 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). ========================================================= After Rebuttal: Thanks for the reader for clarifying my several questions. I have read the rebuttal. However, 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. 1. 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). 2. 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. Next, I would like to add more comments on the experiment. For 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. I 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.