Importance Weight Estimation and Generalization in Domain Adaptation under Label Shift

In supervised learning, we usually make predictions on an unlabeled target set by training a predictive model on a labeled source set. This is a sensible approach, especially when the source and target sets are expected to have i.i.d. samples from the same distribution. However, this assumption does not hold in many real-world applications. For example, oftentimes, predictions for medical diagnostics are based on data from a particular population (or the same population in a few years back) of patients and machines due to the limited variety of data that is available in the training phase. Let us consider the following hypothetical scenario. A classifier is trained to predict whether a patient has contracted a severe disease in country A based on the physical measurements and diagnosis (labeled source data) in country A. The disease is potentially even more prevalent in country B, where no experts are available to make a reliable diagnosis. Ergo, the following questions could be relevant in this scenario:

• •

  Suppose we send a group of volunteers to country B with a preliminary set of equipment to record measurements of patients’ symptoms. How can the data in country A and the new unlabeled data from country B be used to update the classifier to give good diagnostic predictions for patients in country B?

• •

  What if, along with the few diseases we are considering, we are also interested in predicting disease levels where the task is to predict continuous labels, therefore regression?

Similar problems arise in many other domains besides health care, but we will use the medical example throughout the paper for ease of presentation. In the above example, country A denotes the source domain, and country B denotes the target domain. In this example, the distribution of covariates-label in the source may differ from that of the target domain. Therefore, a predictor learned on the source domain might not carry on to the target domain. In the above hypothetical example, consider the case that given a person having a disease $y$, the distribution of their symptoms is similar in both source and target domains, but the proportion of people having different diseases differs.

Consider another example where the source domain is data of a city in Fall, and the target is the data of the same city, a few months later, in Spring. The disease distribution in Spring may differ from that of Fall, but given a person caught a disease, that person expresses similar symptoms in both seasons. In domain adaptation, the label shift is a class of problems where there is a shift in label distribution from source to the target domain, but the conditional distribution of covariates stays unchanged.

We used the medical example to motivate the setting. However, the label shift paradigm is a common in practice. For example, one can use image data of a population to train a model that later is required to adapt to the different demographic environment. In scientific application, to tackle inverse problems, e.g., sensing, or partial differential equations, one may learn an inverse map that maps an outcome to a source. However, later the model needs to be adapted to new distributions of sources in different applications.

In a generic label shift domain adaptation problem, we are given a set of labeled samples from the source domain but unlabeled samples from the target domain. In such settings, the task is to learn a model with low loss in the target domain. In this paper, we study two settings, $(i)$ categorical label spaces, $(ii)$ general normed label spaces. We propose a series of methods to estimate the importance weight from source to target domain for both of these settings. Prior works study categorical label spaces and propose to use a label classifier to estimate the importance weight vector, later used in empirical risk minimization (ERM), to learn a good classifier. Lipton et al. (2018) provides a method to estimate the importance weight vector and guarantee estimation error under strong assumptions that the error in the estimation of confusion matrix should be full rank, the confusion matrix should be a square matrix, the number of samples should be larger than an unknown quantity. Azizzadenesheli et al. (2019) propose another estimator and relax the assumptions in the prior work, but still based on label classifier. In this paper, we first relax the requirement to use a classifier to estimate the importance weight vector. This step improves the conditioning on the inverse operator (inverse of the transition operator from labels to predicted statistics) and exploits the spectrum of the forward operator appropriately. We propose a regularized estimator, which is an extension to Azizzadenesheli et al. (2019).

We further improve the analysis in Lipton et al. (2018) and propose a estimator using general functions (rather than being limited to classifier). For this estimator, we relax the requirement that the confusion matrix should be a square matrix and further relax the strong assumption that the error matrix is full rank. Note that, this analysis also applies to the case where classifiers are used for importance weight estimation and is considered as an improvement to Lipton et al. (2018). Moreover, this analysis results in an estimation bound as tight as the one for the regularized estimator.

For the case of $(ii)$ general normed label spaces, we propose two estimators to estimate the importance weight functions. The first estimator is based on the traditional approach used in inverse problems of compact operators, which directly estimates the inverse operator(Kress et al., 1989). Such an estimator requires the number of samples to be larger than an unknown quantity, which can be considered as a limitation of the traditional methods in inverse problems. The second approach is a novel approach based on regularized optimization in Hilbert spaces, and the derived bound holds for any number of samples. Therefore this approach has an advantage over the traditional approaches and has its own independent importance beyond domain adaptation. As mentioned before, such problems are common in partial differential equations and reinforcement learning.

For both of the proposed estimators, we provide concentration bound on our estimate based on a desirable norm and show that the estimation errors vanish as the number of samples grows. Finally, we deploy these importance weight estimates in importance weighted ERM and provide generalization guarantees of ERM in these settings. Using the existing generalization analysis based on Rademacher complexity, Rényi divergence, and MDFR Lemma in Azizzadenesheli et al. (2019), we show the generalization property of the importance weighted empirical risk minimization on the unseen target domain for both categorical and general normed label spaces.

Let $\mathcal{X}$ and $\mathcal{Y}$ be two sets, denoting the sets of covariates and labels, and $\mathcal{P}$ denote a space of measures on a measure space $(\mathcal{X}\times\mathcal{Y},\mathcal{F})$. For the product space of $\mathcal{X}\times\mathcal{Y}$, let $(\mathcal{X}\times\mathcal{Y},\mathcal{F},\mathbb{P})$ denote the probability space on the source domain, and respectively, $(\mathcal{X}\times\mathcal{Y},\mathcal{F},\mathbb{Q})$ denote the probability space on the target domain where $\mathbb{P},\mathbb{Q}\in\mathcal{P}$. For the label space $\mathcal{Y}$, let $\mathcal{F}_{\mathcal{Y}}\subset\mathcal{F}$, generated by subsets of $\mathcal{Y}$, denote the sub-$\sigma$-algebra of $\mathcal{F}$, with $\mathbb{P}_{\mathcal{Y}}$ and $\mathbb{Q}_{\mathcal{Y}}$ as restrictions of $\mathbb{P}$ and $\mathbb{Q}$ to $\mathcal{F}_{\mathcal{Y}}$. Similarly for $\mathcal{X}$, i.e., $\mathbb{P}_{\mathcal{X}}$ and $\mathbb{Q}_{\mathcal{X}}$ on $\mathcal{F}_{\mathcal{X}}$. We consider the setting where $\mathbb{Q}_{\mathcal{Y}}$ is absolutely continuous with respect to $\mathbb{P}_{\mathcal{Y}}$. We define the shift between source and target domains as a label shift type, if for any random variable $R:\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}$, integrable under $\mathbb{P}$, there exist a version for $\mathbb{E}_{\mathbb{P}}[R|\mathcal{F}_{\mathcal{Y}}]$ which is equal to a version of $\mathbb{E}_{\mathbb{Q}}[R|\mathcal{F}_{\mathcal{Y}}]$ almost surely.

When $\mathcal{X}$ and $\mathcal{Y}$ are normed space, for a given complex separable Hilbert space $\overline{\mathcal{H}}$ accompanied with inner product $\langle\cdot,\cdot\rangle$ and norm $\|\cdot\|$, let $\mathcal{T}$ denote a linear bounded operator $\mathcal{T}:\overline{\mathcal{H}}\rightarrow\overline{\mathcal{H}}$. We say an operator $\mathcal{T}$ is Hilbert-Schmidt if $\sum_{i\geq 1}\|\mathcal{T}e_{i}\|<\infty$ for any set of bases $e_{i}$ of $\overline{\mathcal{H}}$. Note that, the separability of $\overline{\mathcal{H}}$ is required to have countable bases. The space of Hilbert-Schmidt operators ($\mathcal{HS}$) is also a Hilbert space under inner product defined as $\langle\mathcal{T}_{1},\mathcal{T}_{2}\rangle_{\mathcal{HS}}=\sum_{i}\langle\mathcal{T}_{1}e_{i},\mathcal{T}_{2}e_{i}\rangle$ for $\mathcal{T}_{1},\mathcal{T}_{2}\in\mathcal{HS}$, and respectively $\|\cdot\|_{\mathcal{HS}}$ as the corresponding norm (Lang, 2012; Kress et al., 1989). We define a reproducing kernel Hilbert space (RKHS) $\mathcal{H}$, a Hilbert space of functions $h:\mathcal{Y}\rightarrow\mathbb{C}$, accompanied with a symmetric positive definite continuous reproducing kernel $\kappa:\mathcal{Y}\times\mathcal{Y}\rightarrow\mathbb{C}$, such that $\bar{\kappa}:=\sup_{y\in\mathcal{Y}}\kappa(y,y)$ is finite.

In this paper, in order to account for the shifts between source and target domains, we consider the exponent of the infinite and second order Rényi divergences, the notions deployed also in prior works (Cortes et al., 2010; Azizzadenesheli et al., 2019). For the restricted probabilities measures $\mathbb{P}_{\mathcal{Y}}$ and $\mathbb{Q}_{\mathcal{Y}}$, we have:

where $\frac{d\mathbb{Q}_{\mathcal{Y}}}{d\mathbb{P}_{\mathcal{Y}}}\in L^{1}(\mathbb{P}_{\mathcal{Y}})$, the importance weight function, is the Radon–Nikodym change of measure function, and $\mathbb{E}_{\mathbb{P}}$ and $\mathbb{E}_{\mathbb{Q}}$ denote expectation with respect to $\mathbb{P}$ and $\mathbb{Q}$ respectively. To simplify notation, let $\omega=\frac{d\mathbb{Q}_{\mathcal{Y}}}{d\mathbb{P}_{\mathcal{Y}}}$, denote the importance weight function.

In label shift setting, we are interested in the prediction task in the target domain. In other words, for a given loss function $\ell:\mathcal{Y}\times\mathcal{Y}\rightarrow[0,1]$, and a function class $\mathbb{F}$, we are interested in finding a function $f\in\mathbb{F}$, $f:\mathcal{X}\rightarrow\mathcal{Y}$ with small expected loss, ${L}(f,\mathbb{Q})=\mathbb{E}_{\mathbb{Q}}[\ell(Y,f(X))]$. We note that,

In the label shift setting, we have access to $n$ labeled data points from the source domain $D_{S}=\{x_{i},y_{i}\}_{i=1}^{n}$, but $m$ unlabeled samples form the target domain $D_{T}=\{x_{i}\}_{i=1}^{m}$ (see Table 1). In the case where we are provided with the importance weight function $\omega$, we could deploy importance weighted ERM on the source domain,

where $\widehat{\mathbb{P}}$ is the empirical measure induced by $D_{S}$, to obtain a prediction function $\widehat{f}$. However, in practice, we do not have access to $\omega$, and need to estimate it using the knowledge of $D_{S}$ and $D_{T}$. Having access to the data set $D_{S}$ of size $n$, we split the data set to two subsets. We randomly select $\alpha$ portion of the $D_{S}$, and use these $\alpha n$ samples and its corresponding empirical measure $\widehat{\mathbb{P}}_{\alpha n}$, along with samples in $D_{T}$ to estimate importance weight $\widehat{\omega}$, and utilize the remaining $(1-\alpha)n$ samples of $D_{S}$ for the importance weighted ERM to obtain $\widehat{f}$, i.e.,

We propose a series of methods to estimate $\widehat{\omega}$, up to their confidence bounds, and provide generalization guarantees for the importance weighted ERM of ${L}(f,\widehat{\mathbb{P}}_{(1-\alpha)n},\widehat{\omega})$.

We study estimation of importance weight functions in both classification and regression settings.

In this section we provide a series of methods to estimate the effective shift weight $\theta$.

We empirical study the performance of proposed importance weight estimators, in particular, E2, Eq. 7 for categorical, and E4, Eq 11 for normed spaces on synthetic data.

Prior works provide an empirical study for estimator in Eq. 7 when the $g$ function is a classifier. As discussed in subsection 4.1, and prescribed by the generalization in Theorem 4.2, allowing $g$ to be general form function might enhance the weight estimation. In the following, we provide comparisons in the estimation error of the estimator in Eq. 7, $1)$ when $g$ is a deep neural network classifier with a softmax layer in the last layer with output on a Simplex and trained using cross entropy loss, and $2)$ $g$ is a same neural network with no softmax layer, and trained using one hot encoding of label, therefore, output as corners of a Hyper Cube using L2 loss. We first study the case where the number of data points is fixed, but the number of classes varies Fig 1(left) with y-axis as the relative estimation error of importance weights. As indicated in Fig 1(left), using Hyper Cube provides a more consistent weight estimation compared with using Simplex. As the number of classes grows, we observe that both of these methods result in high error which is due to insufficient number of samples. In the second study, we keep the number of classes to be $20$, and increase the number of samples Fig 1(right) and observe Hyper Cube provides a much better samples complexity and recovers the importance weight with much fewer number of samples compared with Simplex .

In Fig. 2 we present the result when $\mathcal{Y}=\mathbb{R}$. In this case, we use GP regression methods to learn the mapping from $\mathcal{X}$ to $\mathcal{Y}$, and compute the quantities in Eq. 9. We use squared version of Eq. 11 to estimate $\omega$. The Fig. 2 express that, as the number of samples increases, the estimation error improves. Finally, we made the code available for further use²²2https://github.com/kazizzad/LabelShiftEstimator for further information. Please refer to appendix C for details.

Domain adaptation is study of adapting to a new domain (target) under minimal access to labeled or unlabeled data from it (Ben-David et al., 2010). In standard supervised learning, the source and target follow the same measure  Vapnik (1999); Bartlett and Mendelson (2002). In the case of arbitrary shifts in the measures, Ben-David et al. (2010) introduces a notion of H-divergence to derive generalization analysis, where the multiple sources setting has been studied (Crammer et al., 2008). Robustness against distributional shifts has been widely studied in the literature which does not make explicit modeling assumptions on the shift Esfahani and Kuhn (2018); Namkoong and Duchi (2016)). Moreover, under the covariate shift, adversarial approaches have been studied to developed robust model (Liu and Ziebart, 2014; Chen et al., 2016) where robustness is achieve only against very small changes in distributions to maintain sufficient performance.

When the shift between two domain is not unstructured, the problem of covariate shift and label shifts have been considered. These settings become apparent in the context of casualty (Schölkopf et al., 2012). In this setting, $(i)$ the covariates causes the label (reward in contextual bandit), denoted as causal direction, and $(ii)$ the label can cause the symptoms (disease causes symptoms), denoted as anti-causal direction. When there is a shift in the measures, the knowledge of $\frac{d\mathbb{P}}{d\mathbb{Q}}$ can be deployed for importance weighted risk minimizing. In the setting of covariate shift, when $\frac{d\mathbb{P}_{\mathcal{X}}}{d\mathbb{Q}_{\mathcal{X}}}$ are known to the learner, the generalization power of importance weighted empirical risk minimization has been studied (Zadrozny, 2004; Cortes et al., 2010; Cortes and Mohri, 2014; Shimodaira, 2000). When $\frac{d\mathbb{P}_{\mathcal{X}}}{d\mathbb{Q}_{\mathcal{X}}}$ is not known, kernel methods have been deployed (Huang et al., 2007; Gretton et al., 2009, 2012; Zhang et al., 2013; Zaremba et al., 2013; Shimodaira, 2000). Such approaches fall short in high dimensional setting, especially images.

Under some regularity condition, a measure over the covariates can be seen as a mixture of covariate conditional distribution. Prior works use this observation and under a strong assumption of pairwise mutual irreducibility (Scott et al., 2013) show that, using Neyman-Pearson criterion (Blanchard et al., 2010), the mixture weights can be recovered for special cases Sanderson and Scott (2014); Ramaswamy et al. (2016); Iyer et al. (2014) which impose strong assumptions and computational challenges. In the presence of label shift, Bayesian methods are among others method that impose complicated computation requirements, e.g., (Storkey, 2009; Chan and Ng, 2005) require computing posterior of label distribution for a given prior, treats the out come of a classifier as a probably distribution over labels, and and suffers from lack of generalization guarantees.

To address these challenges in label shift, also known as target shift (Zhang et al., 2013), and prior probability shift (Moreno-Torres et al., 2012; Kull and Flach, 2014; Hofer, 2015; Tasche, 2017), a work by Lipton et al. (2018) propose black box correction method which is applicable to a wide range of label shift problems and drawn from the classical grouping problemBuck et al. (1966); Forman (2008); Saerens et al. (2002). The authors provide a way to estimate the importance weights and use it for importance weighted empirical risk minimization. Following this idea, Azizzadenesheli et al. (2019) relaxes the assumptions required in (Lipton et al., 2018) such as burning period, and full-rank assumption error matrix, and propose a regularized optimization method to estimate the importance weights up to a confidence interval. Using this confidence interval, Azizzadenesheli et al. (2019) propose a novel analysis based on the second moment of importance weights and provides a first generalization guarantee for label shift. We utilize these development in our paper.

Under label shift setting, when the target domain has a balanced label distribution, but the source has imbalanced, Cao et al. (2019) proposes a margin based method to improve the generalization bound on the target domain. Calibration has been deployed for label shift problem (Shrikumar and Kundaje, 2019), where it is later shown to be connected with importance weight approach (Garg et al., 2020). Recently, Kalan et al. (2020) provides an study of transfer learning in the framework of deep neural networks, and Shui et al. (2020) extend the H-divergence based guarantees to entropy based bounds.

In this paper, we study label shift and consider two cases of categorical and normed spaces of labels. We propose a suite of methods to estimate the importance weight from source to target domain only using unlabeled samples from the target and labeled samples from the source. We show that using such estimates results in desirable generalization properties.

In our motivation examples, we discussed a medical setting where we use labeled data from a source country and send a group of volunteers to a target country with enough expertise and equipment to gather statistics of symptoms. Our task is to learn a good predictor for the target domain. Now consider a case that we have access to a limited number of specialists in the target country who can dedicate their time to diagnose patients. In case the diseases are not deadly, Which patients will we send to the doctors to be diagnosed with a goal to gain a good predictor with a few numbers of queries? In future work, we plan to study this setting where we need to actively decide whom to be diagnosed/investigated. This is an active learning domain adaptation under the label shift setting.