Direct Importance Estimation with Model Selection
and Its Application to Covariate Shift Adaptation

Masashi Sugiyama
Tokyo Institute of Technology
sugi@cs.titech.ac.jp
Hisashi Kashima
IBM Researchhkashima@jp.ibm.com

Shinichi Nakajima
Nikon Corporation
nakajima.s@nikon.co.jp

Paul von Bünau
Technical University Berlin
buenau@cs.tu-berlin.deMotoaki Kawanabe
Fraunhofer FIRST
nabe@first.fhg.de

Abstract
A situation where training and test samples follow different input distributions iscalled covariate shift. Under covariate shift, standard learning methods such as
maximum likelihood estimation are no longer consistent—weighted variants according to the ratio of test and training input densities are consistent. Therefore,
accurately estimating the density ratio, called the importance, is one of the key issues in covariate shift adaptation. A naive approach to this task is to first estimate
training and test input densities separately and then estimate the importance bytaking the ratio of the estimated densities. However, this naive approach tends toperform poorly since density estimation is a hard task particularly in high dimensional cases. In this paper, we propose a direct importance estimation method that
does not involve density estimation. Our method is equipped with a natural crossvalidation procedure and hence tuning parameters such as the kernel width can beobjectively optimized. Simulations illustrate the usefulness of our approach.

1

Introduction

A common assumption in supervised learning is that training and test samples follow the same
distribution. However, this basic assumption is often violated in practice and then standard machinelearning methods do not work as desired. A situation where the input distribution P (x) is different
in the training and test phases but the conditional distribution of output values, P (y|x), remains
unchanged is called covariate shift [8]. In many real-world applications such as robot control [10],bioinformatics [1], spam filtering [3], brain-computer interfacing [9], or econometrics [5], covariate
shift is conceivable and thus learning under covariate shift is gathering a lot of attention these days.
The influence of covariate shift could be alleviated by weighting the log likelihood terms according
to the importance [8]: w(x) = pte (x)/ptr (x), where pte (x) and ptr (x) are test and training input
densities. Since the importance is usually unknown, the key issue of covariate shift adaptation is
how to accurately estimate the importance.
A naive approach to importance estimation would be to first estimate the training and test densities
separately from training and test input samples, and then estimate the importance by taking the ratioof the estimated densities. However, density estimation is known to be a hard problem particularly
in high-dimensional cases. Therefore, this naive approach may not be effective—directly estimating
the importance without estimating the densities would be more promising.
Following this spirit, the kernel mean matching (KMM) method has been proposed recently [6],which directly gives importance estimates without going through density estimation. KMM is shown1

to work well, given that tuning parameters such as the kernel width are chosen appropriately. Intuitively, model selection of importance estimation algorithms (such as KMM) is straightforward
by cross validation (CV) over the performance of subsequent learning algorithms. However, this ishighly unreliable since the ordinary CV score is heavily biased under covariate shift—for unbiased
estimation of the prediction performance of subsequent learning algorithms, the CV procedure itself
needs to be importance-weighted [9]. Since the importance weight has to have been fixed whenmodel selection is carried out by importance weighted CV, it can not be used for model selection ofimportance estimation algorithms.
The above fact implies that model selection of importance estimation algorithms should be performed within the importance estimation step in an unsupervised manner. However, since KMM
can only estimate the values of the importance at training input points, it can not be directly appliedin the CV framework; an out-of-sample extension is needed, but this seems to be an open researchissue currently.
In this paper, we propose a new importance estimation method which can overcome the above
problems, i.e., the proposed method directly estimates the importance without density estimationand is equipped with a natural model selection procedure. Our basic idea is to find an importanceestimate w(x)bsuch that the Kullback-Leibler divergence from the true test input density pte (x)to its estimate pbte (x) = w(x)pb
tr (x) is minimized. We propose an algorithm that can carry out
this minimization without explicitly modeling ptr (x) and pte (x). We call the proposed method the
Kullback-Leibler Importance Estimation Procedure (KLIEP). The optimization problem involved in
KLIEP is convex, so the unique global solution can be obtained. Furthermore, the solution tends tobe sparse, which contributes to reducing the computational cost in the test phase.
Since KLIEP is based on the minimization of the Kullback-Leibler divergence, its model selection
can be naturally carried out through a variant of likelihood CV, which is a standard model selection
technique in density estimation. A key advantage of our CV procedure is that, not the training
samples, but the test input samples are cross-validated. This highly contributes to improving themodel selection accuracy since the number of training samples is typically limited while test input
samples are abundantly available.
The simulation studies show that KLIEP tends to outperform existing approaches in importanceestimation including the logistic regression based method [2], and it contributes to improving theprediction performance in covariate shift scenarios.

2 New Importance Estimation Method
In this section, we propose a new importance estimation method.
2.1

Formulation and Notation

ntr
Let D ⊂ (Rd ) be the input domain and suppose we are given i.i.d. training input samples {xtri }i=1
te ntefrom a training input distribution with density ptr (x) and i.i.d. test input samples {xj }j=1 from atest input distribution with density pte (x). We assume that ptr (x) > 0 for all x ∈ D. Typically,
the number ntr of training samples is rather small, while the number nte of test input samples isvery large. The goal of this paper is to develop a method of estimating the importance w(x) fromntr
te nte{xtri }i=1 and {xj }j=1 :pte (x).
w(x) =
ptr (x)Our key restriction is that we avoid estimating densities pte (x) and ptr (x) when estimating theimportance w(x).

2.2

Kullback-Leibler Importance Estimation Procedure (KLIEP)

Let us model the importance w(x) by the following linear model:
w(x)
b
=

b
X
`=1

2

α` ϕ` (x),(1)

where {α` }b`=1 are parameters to be learned from data samples and {ϕ` (x)}b`=1 are basis functions
such thatϕ` (x) ≥ 0 for all x ∈ D and for ` = 1, 2, . . . , b.
ntr
te nteNote that b and {ϕ` (x)}b`=1 could be dependent on the samples {xtri }i=1 and {xj }j=1 , i.e., kernel
models are also allowed—we explain how the basis functions {ϕ` (x)}b`=1 are chosen in Section 2.3.
Using the model w(x),b
we can estimate the test input density pte (x) bypbte (x) = w(x)pb
tr (x).
We determine the parameters {α` }b`=1 in the model (1) so that the Kullback-Leibler divergence frompte (x) to pbte (x) is minimized:Z

pte (x)dx
w(x)pb
tr (x)ZD
Z
pte (x)=
pte (x) logdx −pte (x) log w(x)dx.
b
ptr (x)DD
pte (x) log

KL[pte (x)kb
pte (x)] =Since the first term in the last equation is independent of {α` }b`=1 , we ignore it and focus on thesecond term. We denote it by J:
Z
J=
pte (x) log w(x)dx
b
(2)
D
!
Ã
nte
nte
b
X
1 X
1 X
te
≈
log w(xb j )=logα` ϕ` (xtej ) ,nte j=1
nte j=1`=1

ntewhere the empirical approximation based on the test input samples {xtej }j=1 is used from the firstline to the second line above. This is our objective function to be maximized with respect to theparameters {α` }b`=1 , which is concave [4]. Note that the above objective function only involves thente
tr ntrtest input samples {xtej }j=1 , i.e., we did not use the training input samples {xi }i=1 yet. As showntr ntrbelow, {xi }i=1 will be used in the constraint.

w(x)bis an estimate of the importance w(x) which is non-negative by definition. Therefore, it isnatural to impose w(x)b
≥ 0 for all x ∈ D, which can be achieved by restrictingα` ≥ 0 for ` = 1, 2, . . . , b.
In addition to the non-negativity, w(x)bshould be properly normalized since pbte (x) (= w(x)pb
tr (x))
is a probability density function:ZZ1=pbte (x)dx =
w(x)p
b
(3)
tr (x)dx
D

≈

D

ntr
1 X

ntr i=1

n

w(x
b tr
i )=

b

tr X
1 X
α` ϕ` (xtri ),ntr i=1`=1

ntr
where the empirical approximation based on the training input samples {xtri }i=1 is used from thefirst line to the second line above.

Now our optimization criterion is summarized as follows.

Ã b
!
nte
X
X

maximize logα` ϕ` (xtej ){α` }b`=1

j=1

`=1
ntr X
b
X

subject toα` ϕ` (xtri ) = ntr and α1 , α2 , . . . , αb ≥ 0.

i=1 `=1

This is a convex optimization problem and the global solution can be obtained, e.g., by simply
performing gradient ascent and feasibility satisfaction iteratively. A pseudo code is described in
Figure 1-(a). Note that the solution {bα` }b`=1 tends to be sparse [4], which contributes to reducing thecomputational cost in the test phase. We refer to the above method as Kullback-Leibler Importance
Estimation Procedure (KLIEP).
3

Input: M = {mk | mk = {ϕ` (x)}b`=1 },ntr
te nte{xtri }i=1 , and {xj }j=1
Output: w(
b x)

ntr
te nteInput: m = {ϕ` (x)}b`=1 , {xtri }i=1 , and {xj }j=1
Output: w(
b x)

(k)

Aj,` ←− ϕ`P
(xte
j );
tr
tr
b` ←− n1tr ni=1 ϕ` (xi );Initialize (> 0) and ε (0 < ε ¿ 1);
Repeat until convergence←− + εA> (1./A );←− + (1 − b> )b/(b> b);←− max(0, );←− /(b> );
end
Pb
w(
b x) ←− `=1 α` ϕ` (x);

(k)

nte
te R
Split {xtej }j=1 into R disjoint subsets {Xr }r=1 ;for each model m ∈ M
for each split r = 1, . . . , R
ntr
tew
br (x) ←− KLIEP(m, {xtri }i=1 , {Xj }j6=r );P1b
Jr (m) ←− |X te | x∈X te log w
br (x);
r
r
end
PR
1
b
b
J(m)
←− R
r=1 Jr (m);endbmb ←− argmaxm∈M J(m);ntr
te ntew(b x) ←− KLIEP(m,b {xtri }i=1 , {xj }j=1 );(a) KLIEP main code(b) KLIEP with model selection

Figure 1: KLIEP algorithm in pseudo code. ‘./’ indicates the element-wise division and > denotes
the transpose. Inequalities and the ‘max’ operation for a vector are applied element-wise.
2.3

Model Selection by Likelihood Cross Validation

The performance of KLIEP depends on the choice of basis functions {ϕ` (x)}b`=1 . Here we explain
how they can be appropriately chosen from data samples.
Since KLIEP is based on the maximization of the score J (see Eq.(2)), it would be natural to selectthe model such that J is maximized. The expectation over pte (x) involved in J can be numerically approximated by likelihood cross validation (LCV) as follows: First, divide the test samnte
te R
br (x) fromples {xtej }j=1 into R disjoint subsets {Xr }r=1 . Then obtain an importance estimate wte{Xj }j6=r and approximate the score J using Xrte as
X
1
Jbr =
log w
br (x).
te
|Xr |
te
x∈Xr

We repeat this procedure for r = 1, 2, . . . , R, compute the average of Jbr over all r, and use theaverage Jb as an estimate of J:
R
1 Xb
b
J=
Jr .
(4)
R r=1
For model selection, we compute Jb for all model candidates (the basis functions {ϕ` (x)}b`=1 in
b A pseudo code of the LCV procedure isthe current setting) and choose the one that minimizes J.
summarized in Figure 1-(b)One of the potential limitations of CV in general is that it is not reliable in small sample cases
since data splitting by CV further reduces the sample size. On the other hand, in our CV procedure,
the data splitting is performed over the test input samples, not over the training samples. Since wetypically have a large number of test input samples, our CV procedure does not suffer from the small
sample problem.
A good model may be chosen by the above CV procedure, given that a set of promising modelcandidates is prepared. As model candidates, we propose using a Gaussian kernel model centered atnte
the test input points {xtej }j=1 , i.e.,
w(x)
b
=

nte
X

α` Kσ (x, xte
` ),

`=1

where Kσ (x, x0 ) is the Gaussian kernel with kernel width σ:¾½
kx − x0 k2
0.
Kσ (x, x ) = exp −
2σ 2
4

(5)

nte
The reason why we chose the test input points {xtej }j=1 as the Gaussian centers, not the training
ntr
input points {xtri }i=1 , is as follows. By definition, the importance w(x) tends to take large values
if the training input density ptr (x) is small and the test input density pte (x) is large; conversely,
w(x) tends to be small (i.e., close to zero) if ptr (x) is large and pte (x) is small. When a function
is approximated by a Gaussian kernel model, many kernels may be needed in the region where theoutput of the target function is large; on the other hand, only a small number of kernels would beenough in the region where the output of the target function is close to zero. Following this heuristic,
we decided to allocate many kernels at high test input density regions, which can be achieved bynte
setting the Gaussian centers at the test input points {xtej }j=1 .
ntr
te nteAlternatively, we may locate (ntr +nte ) Gaussian kernels at both {xtri }i=1 and {xj }j=1 . However,in our preliminary experiments, this did not further improve the performance, but slightly increasednte
the computational cost. Since nte is typically very large, just using all the test input points {xtej }j=1
as Gaussian centers is already computationally rather demanding. To ease this problem, we practinte
cally propose using a subset of {xtej }j=1 as Gaussian centers for computational efficiency, i.e.,

w(x)
b
=

b
X

α` Kσ (x, c` ),

(6)

`=1
nte
where c` is a template point randomly chosen from {xtej }j=1 and b (≤ nte ) is a prefixed number.
In the rest of this paper, we fix the number of template points at

b = min(100, nte ),and optimize the kernel width σ by the above CV procedure.

3 Experiments
In this section, we compare the experimental performance of KLIEP and existing approaches.
3.1

Importance Estimation for Artificial Data Sets

Let ptr (x) be the d-dimensional Gaussian density with mean (0, 0, . . . , 0)> and covariance identityand pte (x) be the d-dimensional Gaussian density with mean (1, 0, . . . , 0)> and covariance identity.
The task is to estimate the importance at training input points:
wi = w(xtr
i )=

pte (xtri )trptr (xi )for i = 1, 2, . . . , ntr .

We compare the following methods:tr
KLIEP(σ): {wi }ni=1
are estimated by KLIEP with the Gaussian kernel model (6). Since the performance of KLIEP is dependent on the kernel width σ, we test several different values ofσ.

KLIEP(CV): The kernel width σ in KLIEP is chosen based on 5-fold LCV (see Section 2.3).
tr
KDE(CV): {wi }ni=1
are estimated through the kernel density estimator (KDE) with the Gaussian
kernel. The kernel widths for the training and test densities are chosen separately based on
5-fold likelihood cross-validation.
tr
KMM(σ): {wi }ni=1
are estimated by kernel mean matching (KMM) [6]. The performance of√KMM
is dependent
on tuning parameters such as B, ², and σ. We set B = 1000 and ² = ( ntr −√1)/ ntr following the paper [6], and test several different values of σ. We used the CPLEX
software for solving quadratic programs in the experiments.

LogReg(σ): Importance weights are estimated by logistic regression (LogReg) [2]. The Gaussian
kernels are used as basis functions. Since the performance of LogReg is dependent on the
kernel width σ, we test several different values of σ. We used the LIBLINEAR implementation of logistic regression for the experiments [7].
LogReg(CV): The kernel width σ in LogReg is chosen based on 5-fold CV.
5

−3

10

−4

10

KLIEP(0.5)
KLIEP(2)KLIEP(7)KLIEP(CV)KDE(CV)KMM(0.1)
KMM(1)
KMM(10)
LogReg(0.5)
LogReg(2)LogReg(7)LogReg(CV)−3

Average NMSE over 100 Trials (in Log Scale)

Average NMSE over 100 Trials (in Log Scale)

KLIEP(0.5)
KLIEP(2)KLIEP(7)KLIEP(CV)KDE(CV)KMM(0.1)
KMM(1)
KMM(10)
LogReg(0.5)
LogReg(2)LogReg(7)LogReg(CV)

−5

10

10

−4

10

−5

10

−6

10
−6

10

2

4

6

8
10
12
14
d (Input Dimension)

16

18

50

20

(a) When input dimension is changed

100
ntr (Number of Training Samples)

150(b) When training sample size is changed

Figure 2: NMSEs averaged over 100 trials in log scale.
We fixed the number of test input points at nte = 1000 and consider the following two settings forthe number ntr of training samples and the input dimension d:(a) ntr = 100 and d = 1, 2, . . . , 20,(b) d = 10 and ntr = 50, 60, . . . , 150.
We run the experiments 100 times for each d, each ntr , and each method, and evaluate the quality
trof the importance estimates {wbi }ni=1
by the normalized mean squared error (NMSE):
¶2
ntr µ
1 X
wi
w
bi
Pntr
NMSE =− Pntr.
0
ntr i=1
bi0
i0 =1 wi0 =1 wi
NMSEs averaged over 100 trials are plotted in log scale in Figure 2. Figure 2(a) shows that the errorof KDE(CV) sharply increases as the input dimension grows, while KLIEP, KMM, and LogReg
with appropriate kernel widths tend to give smaller errors than KDE(CV). This would be the fruitof directly estimating the importance without going through density estimation. The graph also
show that the performance of KLIEP, KMM, and LogReg is dependent on the kernel width σ—theresults of KLIEP(CV) and LogReg(CV) show that model selection is carried out reasonably welland KLIEP(CV) works significantly better than LogReg(CV).
Figure 2(b) shows that the errors of all methods tend to decrease as the number of training samples
grows. Again, KLIEP, KMM, and LogReg with appropriate kernel widths tend to give smaller
errors than KDE(CV). Model selection in KLIEP(CV) and LogReg(CV) works reasonably well and
KLIEP(CV) tends to give significantly smaller errors than LogReg(CV).
Overall, KLIEP(CV) is shown to be a useful method in importance estimation.
3.2

Covariate Shift Adaptation with Regression and Classification Benchmark Data Sets

Here we employ importance estimation methods for covariate shift adaptation in regression andclassification benchmark problems (see Table 1).
Each data set consists of input/output samples {(xk , yk )}nk=1 . We normalize all the input samples
te nten{xk }nk=1 into [0, 1]d and choose the test samples {(xtej , yj )}j=1 from the pool {(xk , yk )}k=1 as
follows. We randomly choose one sample (xk , yk ) from the pool and accept this with probabil(c)(c)
ity min(1, 4(xk )2 ), where xk is the c-th element of xk and c is randomly determined and fixedin each trial of experiments; then we remove xk from the pool regardless of its rejection or acceptance, and repeat this procedure until we accept nte samples. We choose the training samples
tr ntr{(xtr
i , yi )}i=1 uniformly from the rest. Intuitively, in this experiment, the test input density tends
6

(c)to be lower than the training input density when xk is small. We set the number of samples at
tr ntrte ntentr = 100 and nte = 500 for all data sets. Note that we only use {(xtri , yi )}i=1 and {xj }j=1
te
for training regressors or classifiers; the test output values {yjte }nj=1
are used only for evaluating thegeneralization performance.
We use the following kernel model for regression or classification:fb(x; θ) =t
Xθ` Kh (x, m` ),`=1where Kh (x, x0 ) is the Gaussian kernel (5) and m` is a template point randomly chosen fromnte
{xtej }j=1 . We set the number of kernels at t = 50. We learn the parameter θ by importanceweighted regularized least squares (IWRLS) [9]:
"n
#
tr
³
´2
X
tr
tr
tr
2
bIW RLS ≡ argminθw(xb) fb(x ; θ) − y+ λkθk .
(7)
i

θ

i

i

i=1

bIW RLS is analytically given by
The solution θb = (K > W
c K + λI)−1 K > Wc y,θ
where I is the identity matrix andy = (y1 , y2 , . . . , yntr )> ,Ki,` = Kh (xtr
i , m` ),c
W = diag (wb1 , w
b2 , . . . , wbn ) .
tr

The kernel width h and the regularization parameter λ in IWRLS (7) are chosen by 5-fold importanceweighted CV (IWCV) [9]. We compute the IWCV score by³´
X1
br (x), y ,
w(x)L
b
f
|Zrtr |
tr(x,y)∈Zr

where

½
L (b
y , y) =(by − y)2(Regression),1(1−sign{byy})(Classification).
2

We run the experiments 100 times for each data set and evaluate the mean test error:
te
³
´
1 X
te
L fb(xte),y.
jj
nte j=1n

The results are summarized in Table 1, where ‘Uniform’ denotes uniform weights, i.e., no importance weight is used. The table shows that KLIEP(CV) compares favorably with Uniform, implyingthat the importance weighted methods combined with KLIEP(CV) are useful for improving the prediction performance under covariate shift. KLIEP(CV) works much better than KDE(CV); actually
KDE(CV) tends to be worse than Uniform, which may be due to high dimensionality. We tested
10 different values of the kernel width σ for KMM and described three representative results in thetable. KLIEP(CV) is slightly better than KMM with the best kernel width. Finally, LogReg(CV)works reasonably well, but it sometimes performs poorly.
Overall, we conclude that the proposed KLIEP(CV) is a promising method for covariate shift adaptation.

4 Conclusions
In this paper, we addressed the problem of estimating the importance for covariate shift adaptation.
The proposed method, called KLIEP, does not involve density estimation so it is more advantageousthan a naive KDE-based approach particularly in high-dimensional problems. Compared with KMM
7

Table 1: Mean test error averaged over 100 trials. The numbers in the brackets are the standard deviation. All the error values are normalized so that the mean error by ‘Uniform’ (uniform weighting,or equivalently no importance weighting) is one. For each data set, the best method and comparable
ones based on the Wilcoxon signed rank test at the significance level 5% are described in bold face.
The upper half are regression data sets taken from DELVE and the lower half are classification data
sets taken from IDA. ‘KMM(σ)’ denotes KMM with kernel width σ.
Data

Dim

kin-8fhkin-8fmkin-8nhkin-8nmabaloneimage
ringnorm
twonorm
waveform
Average

8
8
8
8
7
18
20
20
21

KLIEP
KDE
KMM
KMM
KMM
LogReg(CV)(CV)(0.01)
(0.3)
(1)
(CV)
1.00(0.34) 0.95(0.31) 1.22(0.52) 1.00(0.34) 1.12(0.37) 1.59(0.53) 1.30(0.40)
1.00(0.39) 0.86(0.35) 1.12(0.57) 1.00(0.39) 0.98(0.46) 1.95(1.24) 1.29(0.58)
1.00(0.26) 0.99(0.22) 1.09(0.20) 1.00(0.27) 1.04(0.17) 1.16(0.25) 1.06(0.17)
1.00(0.30) 0.97(0.25) 1.14(0.26) 1.00(0.30) 1.09(0.23) 1.20(0.22) 1.13(0.25)
1.00(0.50) 0.94(0.67) 1.02(0.41) 1.01(0.51) 0.96(0.70) 0.93(0.39) 0.92(0.41)
1.00(0.51) 0.94(0.44) 0.98(0.45) 0.97(0.50) 0.97(0.45) 1.09(0.54) 0.99(0.48)
1.00(0.04) 0.99(0.06) 0.87(0.04) 1.00(0.04) 0.87(0.05) 0.87(0.05) 0.95(0.08)
1.00(0.58) 0.91(0.52) 1.16(0.71) 0.99(0.50) 0.86(0.55) 0.99(0.70) 0.94(0.59)
1.00(0.45) 0.93(0.34) 1.05(0.47) 1.00(0.44) 0.93(0.32) 0.98(0.31) 0.95(0.34)
1.00(0.38) 0.94(0.35) 1.07(0.40) 1.00(0.36) 0.98(0.37) 1.20(0.47) 1.06(0.37)
Uniform

which also directly gives importance estimates, KLIEP is practically more useful since it is equippedwith a model selection procedure. Our experiments highlighted these advantages and therefore
KLIEP is shown to be a promising method for covariate shift adaptation.
In KLIEP, we modeled the importance function by a linear (or kernel) model, which resulted in aconvex optimization problem with a sparse solution. However, our framework allows the use of any
models. An interesting future direction to pursue would be to search for a class of models which has
additional advantages.
Finally, the range of application of importance weights is not limited to covariate shift adaptation.
For example, the density ratio could be used for novelty detection. Exploring possible application
areas will be important future directions.
Acknowledgments
This work was supported by MEXT (17700142 and 18300057), the Okawa Foundation, the Microsoft CORE3 Project, and the IBM Faculty Award.

References[1] P. Baldi and S. Brunak. Bioinformatics: The Machine Learning Approach. MIT Press, Cambridge, 1998.
[2] S. Bickel, M. Brückner, and T. Scheffer. Discriminative learning for differing training and test distributions. In Proceedings of the 24th International Conference on Machine Learning, 2007.
[3] S. Bickel and T. Scheffer. Dirichlet-enhanced spam filtering based on biased samples. In B. Schölkopf,
J. Platt, and T. Hoffman, editors, Advances in Neural Information Processing Systems 19. MIT Press,
Cambridge, MA, 2007.
[4] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, Cambridge, 2004.
[5] J. J. Heckman. Sample selection bias as a specification error. Econometrica, 47(1):153–162, 1979.
[6] J. Huang, A. Smola, A. Gretton, K. M. Borgwardt, and B. Schölkopf. Correcting sample selection bias
by unlabeled data. In B. Schölkopf, J. Platt, and T. Hoffman, editors, Advances in Neural Information
Processing Systems 19, pages 601–608. MIT Press, Cambridge, MA, 2007.
[7] C.-J. Lin, R. C. Weng, and S. S. Keerthi. Trust region Newton method for large-scale logistic regression.
Technical report, Department of Computer Science, National Taiwan University, 2007.
[8] H. Shimodaira. Improving predictive inference under covariate shift by weighting the log-likelihood
function. Journal of Statistical Planning and Inference, 90(2):227–244, 2000.
[9] M. Sugiyama, M. Krauledat, and K.-R. Müller. Covariate shift adaptation by importance weighted crossvalidation. Journal of Machine Learning Research, 8:985–1005, May 2007.
[10] R. S. Sutton and G. A. Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA,
1998.

8