Direct Density Ratio Estimation forLarge-scale Covariate Shift Adaptation
Yuta Tsuboi

Hisashi Kashima

Shohei Hido∗

Steﬀen Bickel†

Masashi Sugiyama‡

tribution of output values, p(y|x), remains unchanged
is called covariate shift [19]. In many real-world applications such as robot control [25, 18], bioinformatics [1, 5], spam ﬁltering [4], natural language processing [14], brain-computer interfacing [28, 22], or econometrics [12], covariate shift is likely. Covariate shift
is also naturally induced in selective sampling or active learning scenarios [8, 7, 27, 15, 21]. For this reason, learning under covariate shift is receiving a lot of
attention these days in the machine learning community (such as in the NIPS2006 workshop [6] and theECML2006 workshop [2]).
Under covariate shift, standard learning methods
such as maximum likelihood estimation are no longer
consistent, i.e., they do not produce the optimal solution
even when the number of training samples tends to beinﬁnity. Thus, there exists an estimation bias inducedby covariate shift. It has been shown that the bias
Keywords
can be asymptotically canceled by weighting the log
Covariate Shift, Importance Weight, Massive Unlabeled
likelihood terms according to the importance [9, 19, 29]:
Data, KLIEP
pte (x)w(x) =,
ptr (x)1 Introduction
Abstract

Covariate shift is a situation in supervised learning wheretraining and test inputs follow diﬀerent distributions eventhough the functional relation remains unchanged. A common approach to compensating for the bias caused by covariate shift is to reweight the training samples according toimportance, which is the ratio of test and training densities.
We propose a novel method that allows us to directly estimate the importance from samples without going throughthe hard task of density estimation. An advantage of the
proposed method is that the computation time is nearly independent of the number of test input samples, which ishighly beneﬁcial in recent applications with large numbersof unlabeled samples. We demonstrate through experimentsthat the proposed method is computationally more eﬃcientthan existing approaches with comparable accuracy.

An assumption that is commonly imposed—either explicitly or implicitly—in virtually all supervised learning methods is that the training and test samples follow
the same probability distribution. However, this fundamental assumption is often violated in practice, causing
standard machine learning methods not to work as expected. In this paper, we address supervised learning
problems in the absence of this fundamental assumption.
If the training and test distributions share nothingin common, we may not be able to learn anything about
the test distribution from the training samples. For ameaningful discussion, the training and test distributions should be related to each other in some sense. A
situation where the input distribution p(x) is diﬀerent
in the training and test phases but the conditional dis∗ Tokyo Research Laboratory, IBM Research.
† Max Planck Institute for Computer Science‡ Department of Computer Science, Tokyo Institute of Technology.

where pte (x) and ptr (x) are the test and training input
densities. Since the importance is usually unknown inreality, the central issue of practical covariate shift adaptation is how to accurately estimate the importance1 .
A naive approach to importance estimation is toﬁrst estimate the training and test densities separately
1 Covariate shift matters in parameter learning only when themodel used for function learning is misspeciﬁed (i.e., the model
is so simple that the true learning target function cannot be
expressed) [19]. When the model is correctly (or overly) speciﬁed,
the ordinary maximum likelihood estimation is still consistent.
On this basis, there is a criticism that importance weighting is
not needed, but just the use of a suﬃciently complex model cansettle the problem. However, overly complex models result inlarge estimation variances, and so in practice we need to choose
a complex enough but not overly complex model. To choose suchan appropriate model, we usually use a model selection techniquesuch as cross validation (CV). However, the ordinary CV scoreis biased due to covariate shift and we still need to importanceweight the CV score (or any other model selection criteria) for
unbiasedness [19, 29, 23, 22]. For this reason, estimating theimportance is indispensable when covariate shift occurs.

from the training and test input samples, and then estimate the importance by taking the ratio of the estimated densities. However, density estimation is known
to be a hard problem particularly in high dimensional
cases [10]. Therefore, this naive approach is usually
ineﬀective—directly estimating the importance without
estimating the densities is more promising. Therefore,
several methods that allow us to directly obtain importance estimates without going through density estimation have been proposed recently, such as kernel mean
matching (KMM) [13], the logistic regression based
method (LogReg) [3], and the Kullback-Leibler Importance Estimation Procedure (KLIEP) [24].
KMM is based on a special property of universal
reproducing kernel Hilbert spaces (Gaussian reproducing
kernel Hilbert spaces are typical examples) [20] andKMM allows us to directly obtain the importanceestimates at the training input points. Since the
KMM optimization problem is formulated as a convex
quadratic programming problem, it leads to a uniqueglobal solution. KMM has been shown to work well,
as long as the kernel parameters such as the Gaussian
width are chosen appropriately. However, to the best of
our knowledge, there is no reliable method to determine
the Gaussian width and the regularization parameterin the KMM algorithm2 . Therefore, the lack of model
selection procedures is a critical limitation of KMM inpractical applications.
LogReg builds a probabilistic classiﬁer that separates training input samples from test input samples,
and the importance can be directly estimated by LogReg. The maximum likelihood estimation of the LogReg can be formulated as a convex optimization problem, so the unique global optimal solution can be obtained. In addition, since LogReg only solves a standard supervised classiﬁcation problem, the tuning parameters such as the kernel width and the regularization parameter can be optimized by the standard CV
procedure. This is a very useful property in practice.
KLIEP tries to match an importance-based estimation of the test input distribution to the true test input distribution in terms of the Kullback-Leibler diver2 Intuitively, it seems possible to optimize the kernel width andthe regularization parameter simply by using CV for the performance of subsequent learning algorithms. However, this is highly
unreliable since the ordinary CV score is biased under covariate
shift. For unbiased estimation of the prediction performance ofsubsequent learning algorithms, the CV procedure itself needs tobe importance-weighted [29, 22]. Since the importance weight has
to have been ﬁxed when model selection is carried out using theimportance weighted CV, it cannot be used for model selectionof importance estimation algorithms. Note that once the importance weight has been ﬁxed, the importance-weighted CV can beused for model selection of subsequent learning algorithms.

gence. KLIEP solves this matching problem in a nonparametric fashion. The training and test input distributions are not parameterized, but only the importanceis parameterized. The KLIEP optimization problem isconvex and therefore a unique global optimal solution
can be obtained. Furthermore, the global solution tends
to be sparse, so it is computationally eﬃcient in the test
phase. Since KLIEP is based on the minimization of
the Kullback-Leibler divergence, the model selection of
KLIEP, such as the choice of the kernel width and theregularization parameter, can be carried out naturally
through the likelihood CV procedure [10], so no open
tuning parameter remains.
As reviewed above, LogReg and KLIEP seem tohave advantages over KMM, since they are equippedwith built-in model selection procedures. On the other
hand, from the viewpoint of scalability, all three of themethods have limitations—in recent applications suchas spam ﬁltering [4] and information retrieval [11], thenumber of test (unlabeled) samples are enormous. The
purpose of this paper is to develop a computationallyeﬃcient covariate shift adaptation method that can deal
with large sets of unlabeled data.
Our new method is primarily based on KLIEP. The
key diﬀerence is that the original KLIEP uses a linearlyparameterized function for modeling the importance,
while we adopt a log-linear model. By deﬁnition,
the log-linear model only takes non-negative values.
This allows us to reformulate the KLIEP optimization
problem as an unconstrained convex problem. Then
we develop a new scalable estimation procedure whose
computation time is nearly independent of the numberof test samples. More precisely, we need to scan a large
number of test samples only once to compute a summary
statistic in the beginning (this pre-computation can be
carried out in linear time and constant storage space).
The main optimization procedure does not use thetest samples themselves, but only uses the summary
statistic. Therefore, the computation time of the main
optimization procedure is independent of the number oftest samples.
The experiments show that the proposed method
is computationally much more eﬃcient than the existing approaches. Therefore the range of application ofcovariate shift adaptation can be greatly enlarged towards large-scale problems. As regards estimation accuracy, we experimentally show that the performanceof the proposed method is comparable to the best existing methods for small and middle sized problems (since
the existing methods cannot be applied to large-scale
problems due to the computational costs). Thus the
proposed method can be a useful alternative to the existing covariate shift adaptation methods.

function, such as the squared loss in a regression caseIn this section, we formulate the supervised learning or the zero-one loss in a classiﬁcation case.
In supervised learning under covariate shift, theproblem under covariate shift and brieﬂy review existing
following
quantity called the test domain importancetechniques for covariate shift adaptation.
plays an important role:2

Problem Formulation

2.1 Supervised learning under covariate shift.
Let x ∈ X ⊂ <d be an input variable and y ∈ Y be
an output variable. Y is a real space in regression cases
or a set of categories in classiﬁcation cases. In standard
supervised learning frameworks, it is assumed that x is
independently drawn from an input distribution and yis independently drawn from a conditional distribution
both in training and test phases. In contrast, here we
consider a situation called covariate shift [19], i.e., theinput distribution diﬀers in the training and test phases,
but the conditional distribution remains unchanged.
Suppose we have independent and identically distrtributed (i.i.d.) training input samples Dtr = {xi }N
i=1
from a distribution with strictly positive density ptr (x),teand test input samples Dte = {xi }N
i=1 from a distribution with density pte (x). In addition to the input samtr
ples, suppose we have training output samples {yi }N
i=1
drawn from the conditional distribution with conditional density p(y|x = xi ), respectively. Typically, thenumber Ntr of training samples is rather small due tothe high labeling cost, while the number Nte of test
input samples is very large since they are often easily
available. We denote training sample pairs of input andtroutput as Ztr = {zi | zi = (xi , yi )}N
i=1 .
We use the following linear model:(2.1)

fθ (x) = hθ, φ(x)i ,where θ is the parameter vector, φ(x) : X → <t is abasis function of x, and hu, vi denotes the Euclidean
inner product between vector u and v: hu, vi =Pd
l=1 ul vl . Note that this model can contain a bias
parameter by just including a constant basis functionin φ(x). Throughout the paper, we suppose that thislinear model is not generally speciﬁed correctly, i.e., thetrue input-output function is not necessarily includedin the above linear model. Since we do not know thetrue function class in practice, dealing with misspeciﬁed
models is quite realistic.
The goal of supervised learning is to learn theparameter θ so that the output values for the test inputs
can be accurately predicted. Thus our error metric(which is usually called the generalization error ) is given
by
ZZ
(2.2)
Loss(x, y, fθ (x))pte (x)p(y|x)dxdy,
where Loss(x, y, fθ (x)) : X × Y × Y → < is a loss

(2.3)

w(x) =

pte (x).
ptr (x)The importance can be used for adjusting the diﬀerence
between the training and test input distributions: forany function A(x),
Z
Z
(2.4)
A(x)pte (x)dx = A(x)w(x)ptr (x)dx.
2.2 Parameter learning under covariate shift.
Here we review two typical parameter learning methods
under covariate shift: one is importance weighted leastsquares (IWLS) for regression and the other is importance weighted logistic regression (IWLR) for classiﬁcation.
IWLS: A standard learning method in regression
scenarios would be ordinary least squares (LS):X
2θ̂LS ≡ argmin (fθ (x) − y)  .
θ(x,y)∈Ztr

LS is known to be consistent under a usual setting.
However, it is no longer consistent for misspeciﬁed models under covariate shift. Instead, IWLS is consistent [19]:
(2.5)


X
2
w(x) (fθ (x) − y) + λkθk2  ,θ̂IWLS ≡ argmin θ(x,y)∈Ztr

where the importance w(x) is used as weights. Here
we also added a penalty term λkθk2 for regularization,
where λ is a regularization parameter.
For the linear model (2.1), the above optimization
problem is convex and the unique global solution θ̂IWLS
can be computed in a closed-form asθ̂IWLS = (Φ> W Φ + λI)−1 Φ> W y,where I is the identity matrix,
Φi,l = φl (xi ), y = (y1 , y2 , . . . , yNtr )> , andW = diag(w1 , w2 , . . . , wNtr ).
IWLR: For simplicity, we focus on the two-classcase, i.e. Y = {−1, 1}; we note that it is straightforward
to extend all of the discussions in this paper to multiclass cases.

Let us model the posterior probability of class ygiven x using a parametric model fθ (x) aspθ (y|x) =(2.6)

exp(yfθ (x)).
1 + exp(yfθ (x))

Then a test input sample x is classiﬁed by choosing themost probable class:(2.7)

ŷ = argmax pθ (y|x).
y(IWCV) has been proposed for model selection undercovariate shift [22]. It has been proved that IWCV
gives an unbiased estimate of the generalization error
even under the covariate shift.
Here, let us brieﬂy describe the IWCV procedure.
tr
We ﬁrst divide the training samples {zi }Ni=1 into R
r R
disjoint subsets {Z }r=1 . Then we learn a functionfθr (x) from {Z j }j6=r by IWLS/IWLR and compute its
mean test error for the remaining samples Z r :1|Z r |

X2

w(x) (fθr (x) − y) ,(regression)
A standard learning method for the above proba(x,y)∈Z r
bilistic classiﬁcation scenarios would be ordinary logisticX
1
w(x)I(ŷ = y), (classiﬁcation)
regression (LR):|Z r |(x,y)∈Z rXθ̂LR ≡ argmin (log (1 + exp (yfθ (x))) −yfθ (x)) . where I(·) denotes the indicator function. We repeatθthis procedure for r = 1, 2, . . . , R and choose the model(x,y)∈Ztr
such that the average of the above mean test error is
Similar to the case of LS, LR is consistent under a usual minimized.
setting, but is no longer consistent for misspeciﬁed models under covariate shift. Instead, IWLR is consistent: 3 Importance Estimation
As we have seen in the previous section, the importance(2.8) θ̂IWLR ≡ argmin
w(x) plays a central role in covariate shift adaptation.
θ However, the importance is unknown in practice so weXneed to estimate it from samples.
w(x) (log (1+ exp (yfθ (x))) −yfθ (x)) +λkθk2  .
Direct importance estimation methods that do not(x,y)∈Ztr
involve density estimation steps have been developed
recently [13, 3, 24]. Here we review one of those
Here we also added a penalty term λkθk2 for regulardirect methods called the Kullback-Leibler Importanceization, where λ is a regularization parameter.
Estimation Procedure (KLIEP) [24]. Other methods
This optimization problem is known to be convex
will be reviewed in Section 6.
and a unique optimal solution can be computed using
standard non-linear optimization techniques such as a
3.1 KLIEP. Let us model w(x) with the following
gradient ascent method or some variants of the Newton
linear model:
method. The gradient of the above objective function
is given by(3.10)
ŵ(x) = hα, ψ(x)i ,X

where α ∈ <b is a model parameter vector. Since theimportance should be non-negative by deﬁnition, we(x,y)∈Ztr
suppose that both α and ψ(x) are non-negative.
Using the importance estimation ŵ(x), we can
2.3 Model selection under covariate shift. In
the above learning methods, the choice of model param- estimate the test input density pte (x) byeters such as the basis functions φ and the regularizationp̂te (x) = ptr (x)ŵ(x).
parameter λ heavily aﬀects the prediction performance. (3.11)
This problem is called model selection and is one of the
Now we learn the parameter α so that the Kullbackkey concerns in machine learning.
Leibler divergence from pte (x) to p̂te (x) is minimized:
A popular model selection method in the machineZ
learning community would be cross validation (CV).
pte (x)KL[pte (x)||p̂te (x)] =pte (x) log
dx
The performance of CV is guaranteed in the senseptr (x)ŵ(x)Dthat it gives an unbiased estimate of the generalization
error. However, this useful theoretical property is no (3.12)ZZ
pte (x)longer true under covariate shift [29]. To cope with this=pte (x) logdx −pte (x) log ŵ(x)dx.
ptr (x)DD
problem, a variant of CV called importance weighted CV(2.9)w(x) (ypθ (y|x)φ(x) − yφ(x)) + 2λθ.

Since the ﬁrst term in Eq.(3.12) is independent of α, we
ignore it and focus on the second term, which we denote
by JKLIEP :(3.13)Z
1 X
JKLIEP =pte (x) log ŵ(x)dx ≈log ŵ(x),NteDtraining samples, but the test input samples are crossvalidated. This contributes greatly to improving themodel selection accuracy, since the number of training
samples is typically limited while there are lots of test
input samples available.
As basis functions, it is suggested to use Gaussianx∈Dtekernels centered at a subset of the test input points
where an empirical approximation based on the test Dte [24]:input samples is used. This is the objective function¾½
kx − xl k2
to be maximized. The value of ŵ(x) should be properly (3.16),
Ks (x, xl ) = exp −2s2
normalized since it is a probability density function:

where xl ∈ Dte is a template test sample and s is
the kernel width. This is a heuristic to allocate many
kernels at high test input density regions since manyx∈Dtr
kernels may be needed in the region where the outputof the target function is large. In the original paper,
where the empirical approximation based on the trainthe number of Gaussian centers was ﬁxed at Nte /10
ing samples is used.
for computational eﬃciency and the kernel width s was
Then the resulting optimization problem is exchosen by LCV.
pressed as(3.14)ZZ
1 X
p̂te (x)dx =ptr (x)ŵ(x)dx ≈1=ŵ(x),
Ntr
D
D

maximizeX

log hα, ψ(x)i

4

KLIEP for Log-linear Models

As shown above, KLIEP has its own model selection
procedure and has been shown to work well in imporsubject tohα, ψ(x)i = Ntr and α ≥ 0,tance estimation [24]. However, it has a weakness inx∈Dtr
computation time. In each step of gradient ascent, thesummation over all test input samples needs to be comwhich is convex. Thus the global solution can beputed, which is prohibitively slow in large-scale probobtained by iteratively performing gradient ascent andlems. The main contribution of this paper is to extend
feasibility satisfaction.
KLIEP so that it can deal with large sets of test input
data.
3.2 Model selection by likelihood CV. The performance of KLIEP depends on the choice of the basis
4.1 LL-KLIEP. In the original KLIEP, a linearlyfunctions ψ(x) (and possibly an additional regularizaparameterized model (3.10) is used for modeling thetion parameter). Since KLIEP is based on the maximportance function. Here, we propose using a (norimization of the score JKLIEP , it would be natural tomalized) log-linear model3 for modeling the importanceselect the model such that JKLIEP is maximized. The
w(x) asexpectation over pte (x) involved in JKLIEP can be numerically approximated by likelihood CV (LCV) [10] as
exp(hα, ψ(x)i)ŵ(x) = 1 P,
follows: First, divide the test samples Dte into R disjoint (4.17)
0x0 ∈Dtr exp(hα, ψ(x )i)r R
Ntr}r=1 . Then, obtain an importance estimate
subsets {Dtet Rŵr (x) from {Dte}t6=r and approximate the score JKLIEP where the denominator guarantees the normalizationr
using Dte as
constraint (3.14). By deﬁnition, the log-linear modelα(3.15)x∈Dte

XrJˆKLIEP=X
1ŵr (x).
r|Dte |rx∈Dte

This procedure is repeated for r = 1, 2, . . . , R andrchoose the model such that the average of JˆKLIEP
for
all r is maximized.
One of the potential general limitations of CV isthat it is not reliable in small sample cases, since data
splitting by CV further reduces the sample size. A
key advantage of the LCV procedure is that, not the

takes only non-negative values. Therefore, we no longer
3 The log-linear model can have numerical problems since it
contains an exponential function. To cope with this problem, we
do not directly compute the value of ŵ(x), but we compute it in
the exponential of the logarithmic domain, i.e.,
1 X
exp(log ŵ(x)) = exp(hα, ψ(x)i − log
exp(hα, ψ(x)i)).
Ntr x∈Dtr

To further stabilize the computation, we compute the logarithmicsum of the exponential functions aslog(exp(a) + exp(b)) = log(1 + exp(b − a)),where we pick the smaller exponent as b.

need the non-negative constraint for the parameter (and 4.2 LL-KLIEP(LS). Here, we introduce anotherthe basis functions). Then the optimization problem optimization technique for LL-KLIEP that enables us
becomes unconstrained :to overcome the above weakness. Our basic idea is toencourage the derivative of the convex objective funcmaximize JLL−KLIEP (α),
tion to be zero. We use a squared norm to measure theα‘magnitude’ of the derivative (4.20):
where
°
°2
∂(α) °
1°°
° .
(4.21)
LS (α) = °
°
1 X
2
∂α
JLL−KLIEP (α) =log ŵ(x)Ntex∈Dte
The partial derivative of Eq.(4.21) with respect to(4.18)
α is expressed as
1 X
1 X
=
hα, ψ(x)i − log
exp(hα, ψ(x)i).
∂ 2 (α) ∂(α)∂LS (α)
Nte
Ntr
=
.
(4.22)
x∈Dte
x∈Dtr
∂α
∂ 2 α ∂αBelow, we refer to this method as LL-KLIEP (log-linear This means that the computational complexity of the
2
KLIEP). In practice, we may add a penalty term for above derivative is O(b Ntr ), which is independent of
N
.
Also,
the
requiredstorage space is independent ofteregularization:
Nte : Ω(b2 + cNtr ). We refer to this approach as LLKLIEP(LS1) below.
||α||2(4.19)
(α) = JLL−KLIEP (α) −,2The computation time and storage space of LL2σ
KLIEP(LS1) are quadratic functions of the number
where σ 2 is a regularization parameter.
of parameters b, which could be a bottleneck in highAn advantage of LL-KLIEP over the original dimensional problems. To cope with this problem, we
KLIEP is its computational eﬃciency. The gradient of make use of the representer theorem [26]. Our idea is(α) can be computed as
to represent the parameter α as a linear combination of
the input samples:
∂(α)
1 X
X
=
ψ(x)
α=
ψ(x)βx ,
∂α
Nte
x∈Dte

−

X

x∈Dtr

(4.20) =F −αexp(hα, ψ(x)i)ψ(x) − 20σx0 ∈Dte exp(hα, ψ(x )i)Xαŵ(x)ψ(x) − 2 ,
σ

P

1
Ntr

x∈Dtr

where {βx }x∈Dtr is a data-wise parameter.
Eq.(4.21) can be rewritten as(4.23)

x∈Dtr

where
F =

1 X
ψ(x).
Nte
x∈Dte

This means that once we pre-compute the value of F , wedo not need to use the test samples when we compute
the gradient. This contributes greatly to reducing thecomputation time when the number of test samples islarge. In addition, we do not need to store all of the test
samples in memory since we only need the value of F .
The required storage capacity is only Ω(cNtr ), where cis the average number of non-zero basis entries.
Although the above optimization procedure may be
more eﬃcient than original KLIEP, there still exists a
potential weakness: we still need to use all test samples
when computing the values of JLL−KLIEP (α) or (α).
The value of JLL−KLIEP (α) is needed we choose a model
by LCV, and the value of (α) is often utilized in line
search or in the stopping criterion.

ThenLS ({βx }x∈Dtr ) =°°2XX ψ(x)βx °1°°°
ψ(x)ω(x) −
°F −
° ,
2°
σ2 °
x∈Dtr

x∈Dtr

where

P
exp( x0 ∈Dtr K(x, x0 )βx0 )P(4.24) ω(x) = P,00
00x00 ∈Dtr exp(
x0 ∈Dtr K(x , x )βx )K(x, x0 ) = hψ(x), ψ(x0 )i .
The partial derivative of Eq.(4.23) with respect to βx
is:(4.25)∂LS ({βx }x∈Dtr )
=
∂βx
*
µ
¶
X
βx0
0
0
F−
ψ(x ) ω(x ) − 2 ,σ0x ∈DtrX
x0 ∈Dtrψ(x)ω(x0 )ψ(x0 ) hϕ(x0 ), ψ(x)i −σ2+,

Table 1: Computational complexity and space requirements.

KLIEP
LL-KLIEP
LL-KLIEP(LS1)
LL-KLIEP(LS2)

Computational complexity
Pre. Comp. (once)
Objective
Derivative
0
O(bNtr + bNte ) O(bNtr + bNte )O(bNte )O(bNtr + bNte )O(bNtr )O(bNte )O(bNtr )O(b2 Ntr )2
2
O(bNte )O(bNtr)O(bNtr)P
where ϕ(x) = x0 ∈Dtr ω(x0 )ψ(x0 ) − ψ(x). We refer tothis approach as LL-KLIEP(LS2).
The computation of LL-KLIEP(LS2) requires
2
2
O(bNtr) time and Ω(Ntr+cNtr ) space. The computation
time is linear with respect to the number of parameters
b and the storage space is independent of b. This is asigniﬁcant improvement over the direct computation of
the partial derivative in Eq.(4.22).
For LL-KLIEP(LS), LCV can also be computedrvery eﬃciently. In each validation set using Dte, we
can compute the validation error as
°
°2
°
°
X
°
°
r
JˆLL-KLIEP(LS)= °F r −ŵr (x)ψ(x)° ,
°
°
x∈Dtr

where
Fr =

X
1
ψ(x).
r |
|Dte
r
x∈Dte

Note that, once the mean basis vectors F r are calculatedr
for all R disjoint subsets of Dte , JˆLL-KLIEP(LS)can ber
evaluated independently of the size of the test data Dte.
The computational complexity and storage space ofeach method are summarized in Table 1.

Space requirement
Objective
DerivativeΩ(cNtr + cNte ) Ω(cNtr + cNte )Ω(cNtr + cNte )Ω(cNtr )Ω(cNtr )Ω(b2 + cNtr )2Ω(cNtr )Ω(Ntr+ cNtr )Table 2: Speciﬁcations of illustrative classiﬁcation data.

Fig. 2(a)µΣFig. 2(b)µΣTraining ptr (x, y)y=0
y=1(-1,-1)(3,-1)„«
0.25 00
4(-1,0)
(4,2)
„
«
0.75
0
0
1.5

Test pte (x, y)y=0
y=1(0,3.5)(4,2.5)
„
«
0.25
0
0
0.25
(0,2)
(3,1)
„
«
0.75 0.5
0.01 0.1

the true importance w(x) and an estimated importanceŵ(x) by using LL-KLIEP, where the hyper-parameterssuch as the Gaussian width and the regularization
parameter are selected by LCV. We also tested LLKLIEP(LS1) and LL-KLIEP(LS2), but we omit theirgraphs since their solutions are are almost identical to
the solution of LL-KLIEP.
Figure 1(c) depicts the values of the true JLL−KLIEP(see Eq.(4.18)) and its estimate by 5-fold LCV. The
means, the 25 percentiles, and the 75 percentiles overeach validation are plotted as functions of the kernel
width s for σ = 1. We also plot the normalized meansquared error of the estimated importance:(5.26)
Ã
!2
1 X
ŵ(x)
w(x)
P
NMSE =−P.
00Ntr
x0 ∈Dtr ŵ(x )x0 ∈Dtr w(x )5 Illustrative Examples
In this section, we illustrate the behavior of the prox∈Dtr
posed LL-KLIEP and show how it can be applied incovariate shift adaptation.
The graph shows that LCV gives a very good estimate
of JLL−KLIEP and also NMSE.
5.1 Regression under covariate shift. Let us conFigure 1(d) shows the true learning target function
sider an illustrative regression problem of learningand functions learned by ordinary LS and IWLS witha linear basis function, such as φ(x) = (1, x)> (secf (x) = sinc(x).
tion 2.2). The regularization parameter λ was selected
Let the training and test input densities be ptr (x) = by CV for LS and IWCV for IWLS (section 2.3). The
N (x; 1, 12 ) and pte (x) = N (x; 1, 0.52 ), where results show that the learned function using IWLS goesN (x; µ, σ 2 ) denotes the Gaussian density with mean µ reasonably well through the test samples, while that ofand variance σ 2 . We create the training output value ordinary LS overﬁts the training samples. Note that theNt rtr{yi }Ni=1 as yi = f (xi ) + ²i , where the noise {²i }i=1 has output of the test samples are not used to obtain the2density N (²; 0, 0.25 ). Let the number of training sam- learned functions.
ples be Ntr = 200 and the number of test samples be
Nte = 1000. These settings imply that we are consider- 5.2 Classiﬁcation under covariate shift. Next,
let us consider two illustrative binary classiﬁcation probing an extrapolation problem (see Figure 1(a)).
We used 100 Gaussian basis functions centered at lems, where two-dimensional samples were generated
randomly chosen test input samples. Figure 1(b) shows from Gaussian distributions (see Table 2 and Figure 2).

1.0

sinc(x)LS
IWLS
Training
Test

0.5
0.0

f(x)

2e−04

−0.5

1e−04

0.5

−0.5

0.0

0.5

1.0

1.5

2.0

2.5

3.0

−0.5

x

0.0

0.5

1.0

1.5

2.0

2.5

3.0

0.5

1.0

x

(a) Training and test densities

−1.0

0e+00

0

0.0

0.4

0.2

1

NMSE

0.6

J

2

0.4

w (x)

0.6

0.7

3

0.8

3e−04

J(CV)
J
NMSE

0.8

True w(x)LL−KLIEP

1.5

4e−04

0.9

4

1.0

Pte(x)
Ptr(x)

1.5

2.0

2.5

−0.5

0.0

0.5

Kernel Width(b) Estimated importance

1.0

1.5

2.0

2.5

3.0

x

(c) Model selection curve(d) True and learned functions

6

6

Figure 1: Regression under covariate shift.

4
0

x2

2

Training(class 0)
Training(class 1)
Test(class 0)
Test(class 1)

−2

−2

0

x2

2

4

Training(class 0)
Training(class 1)
Test(class 0)
Test(class 1)

OPT
LR
IWLR
−2

0

2

4

6

OPT
LR
IWLR
−2

(a) pte (x) is linearly x1
shifted from ptr (x).

0

2

4

6

x1
(b) pte (x) is rotatedfrom ptr (x).

Figure 2: Classiﬁcation examples under covariate shift.
These data sets correspond to a ‘linear shift’ and a ‘nonlinear shift’ (rotation).
Let the number of the training samples be Ntr =200 and that of the test samples be Nte = 1000 (only 500
test samples are plotted for clarity). We used LR/IWLR
for the training classiﬁers (see section 2.2), and employed CV/IWCV for the regularization parameter tuning (see section 2.3). We used a linear basis function for
IWLR: φ(x) = (1, x> )> .
Figure 2 shows the decision boundaries obtainedby LR+CV and IWLR+IWCV. For references, we also
show ‘OPT’, which is the optimal decision boundary obtained using the test input-output samples. For the data
set depicted in Figure 2(a), the correct classiﬁcation
rate of LR+CV is 99.1% while that of IWLR+IWCV is100%. For the data set depicted in Figure 2(b), the correct classiﬁcation rate of LR+CV is 97.2% while that of
IWLR+IWCV is 99.1%. Thus, for both cases, the prediction performance is improved by importance weighting.
6 Discussion
In this section, we compare the proposed LL-KLIEP
with existing importance estimation approaches.

Gaussian kernel, KDE is expressed as(6.27)

p̂(x) =NX
1
Ks (x, xl ),(2πs2 )d/2 N l=1

where Ks (x, x0 ) is the Gaussian kernel (3.16). The
performance of KDE depends on the choice of the kernel
width s, which can be optimized by LCV [10]. Note that
LCV corresponds to choosing s such that the KullbackLeibler divergence from p(x) to p̂(x) is minimized.
KDE can be used for importance estimation by ﬁrst
trobtaining p̂tr (x) and p̂te (x) separately from {xi }N
i=1
Nte
and {xi }i=1 and then estimating the importance asŵ(x) = p̂te (x)/p̂tr (x). A potential limitation of thisapproach is that KDE suﬀers from the curse of dimensionality [10], since the number of samples needed tomaintain the same approximation quality grows exponentially as the dimension of the input space increases.
This is particularly critical when estimating ptr (x) since
the number of training input samples is typically limited. In addition, model selection by LCV is unreliablein such cases, since data splitting in the CV procedure
further reduces the sample size. Therefore, in highdimensional cases LL-KLIEP may be more reliable thanthe KDE-based approach.

6.1 Kernel density estimator. The kernel density
estimator (KDE) is a non-parametric technique to es- 6.2 Kernel mean matching. The kernel mean
matching (KMM) method avoids density estimation andtimate a density p(x) from samples {xl }N
l=1 . For the
directly gives an estimate of the importance at the train-ing input points [13]. The basic idea of KMM is to ﬁndw(x) such that the maximum diﬀerence of the meansof nonlinearly transformed samples drawn from pte (x)and ŵ(x)ptr (x) is minimized in some feature space F:
2

min

sup

w(x)

f :f ∈F ,kf kF =1

kEte [f (x)] − Etr [w(x)f (x)]kF

subject to Etr [w(x)] = 1 and w(x) ≥ 0.

optimizes the parameter {βx }x∈Dtr in the importancemodel (4.24). Thus, LL-KLIEP(LS2) learns the entire
importance function and therefore it allows us to interpolate the value of the importance function at any
input point. This interpolation property is a signiﬁcantadvantage over KMM since it allows us to use LCV formodel selection. Therefore, LL-KLIEP(LS2) may be regarded as an extension of KMM.

It has been shown [13] that the solution of this problem
agrees with the true importance if F is a universal 6.3 Logistic regression discriminating training
reproducing kernel Hilbert space [20]. The Gaussian and test input data. Another method to directly
kernel (3.16) is known to induce a universal reproducing estimate the importance weights is to use a probabilistic
kernel Hilbert space and an empirical version of the classiﬁer. Let us assign a selector variable δ = −1 toabove problem is expressed by the following quadratic the training input samples and δ = 1 to the test input
samples. This means that the training and test input
program.
 densities are written asXX1
ptr (x) = p(x|δ = −1), pte (x) = p(x|δ = 1).
min w(x)w(x0 )Kσ (x, x0 ) −w(x)κ(x)
{w(x)}x∈Dtr 2 0
x,x ∈Dtrx∈Dtr
A simple calculation shows that the importance can be
¯
¯
¯ X
¯
expressed in terms of δ as [3]:¯¯subject to ¯
w(x) − Ntr ¯ ≤ Ntr ², and
¯
¯
x∈Dtr
p(δ = −1) p(δ = 1|x)(6.28).
w(x) =
0 ≤ w(x) ≤ B for all x ∈ Dtr ,p(δ = 1) p(δ = −1|x)where
κ(x) =Ntr X
Kσ (x, x0 ).
Nte 0x ∈DteB (≥ 0) and ² (≥ 0) are tuning parameters. The
solution {w(x)}x∈Dtr is an estimate of the importanceat the training input points.
Since KMM does not require density estimates, it
is expected to work well even in high dimensional cases.
However, the performance is dependent on the tuning
parameters B, ², and σ and they cannot be optimized
easily, e.g., by CV, since estimates of the importance
are available only at the training input points. Thus,
an out-of-sample extension is needed to apply KMM in
the CV framework, but this currently seems to be an
open research issue.
Here, we show that LL-KLIEP(LS2) (see Eq.(4.23))
has a tight connection to KMM. Up to irrelevant constants, Eq.(4.23) without a regularizer can be expressedasX
1 X
w(x)w(x0 )Kσ (x, x0 ) −w(x)κ(x),20x,x ∈Dtr

The probability ratio p(δ = −1)/p(δ = 1) may be simply
estimated using the ratio of the numbers of training andtest input samples. The conditional probability p(δ|x)
may be learned by discriminating between the test input
samples and the training input samples using LR, whereδ plays the role of a class variable (cf. Eq.(2.6)). Let us
train the LR model by regularized maximum likelihood
estimation. The objective function to be maximized isgiven by(6.29)−

LR(α) =
Xx∈Dte ∪DtrX

δx hα, ψ(x)ix∈Dte ∪Dtr

log(1 + exp(δx hα, ψ(x)i)) −||α||2,2σ 2where the ﬁrst term is the main likelihood term, thesecond term is a normalizer, , and the third term is aregularizer. Since this is a convex optimization problem,
the global solution can be obtained by standard nonlinear optimization methods. The gradient of theobjective function is given asx∈Dtr(6.30)
which is exactly the same form as the objective function
X
X||α||2∂LR(α)
of KMM. Thus, KMM and LL-KLIEP(LS2) share a=δx ψ(x) −δx pα (δx |x)ψ(x)−
.
∂α
2σ 2
common objective function, although they are derivedx∈Dte ∪Dtr
x∈Dte ∪Dtr
from very diﬀerent frameworks.
However, KMM and LL-KLIEP(LS2) still have a Then the importance estimate is given bysigniﬁcant diﬀerence—KMM directly optimizes the imNtr
ŵ(x) =
exp(hα, ψ(x)i).
portance values {w(x)}x∈Dtr , while LL-KLIEP(LS2) (6.31)
Nte

7 Experiments
In this section, we experimentally compare the performance of LL-KLIEP with existing methods.

0.001200.00072
0.000480.00024

Mean NMSE

0.00096

LL−KLIEP
KLIEP
KDE
KMM(0.1)
KMM(1.0)
LogReg0.00000

We refer to this approach as LogReg.
Eq.(6.31) shows that the function model of theimportance in LogReg is actually the same as that of
LL-KLIEP except for a scaling factor (cf. Eq.(4.17)).
However, the optimization criteria of LL-KLIEP and
LogReg are diﬀerent—in LL-KLIEP, the summation istaken only over the training or test input samples but
not both, while the summation in LogReg is over boththe training and test input samples. This diﬀerence issigniﬁcant since LogReg does not allow us to use thecomputational trick we proposed in Section 4.2. Thus
LL-KLIEP has the advantage in computation time andstorage space consumption over LogReg.

2

4

6

8

10

12

14

16

18

20

Input Dimension

Figure 3: Mean NMSE over 100 trials.
denotes KMM with kernel width s.

‘KMM(s)’perhaps because the original KLIEP does not contain a
7.1 Toy experiments. Let ptr (x) = N (0d , Id ) and regularizer; we believe that the performance of KLIEP
pte (x) = N ((1, 0, . . . , 0)> , 0.752 Id ). The task is to could be improved by adding a regularizer as used inestimate the importance at the training input points:
LL-KLIEP and LogReg. KMM also works reasonably
well, as long as that the kernel width s is chosen
w(x) = pte (x)/ptr (x) for x ∈ Dtr .
appropriately. However, the performance of KMM is
We compared LL-KLIEP, LL-KLIEP(LS1), LL- highly dependent on s and determining its appropriate
KLIEP(LS2), KLIEP, KDE, KMM, and LogReg. For value may be diﬃcult. Overall, the accuracy of LLLL-KLIEP, LL-KLIEP(LS1), and LL-KLIEP(LS2), we KLIEP is comparable to the best existing approaches.
Next, we compare the computational cost of LLused 5-fold LCV to choose the regularization parameterσ and the kernel width s. For KLIEP, we use 5-fold KLIEP, LL-KLIEP(LS1), and LL-KLIEP(LS2). We
LCV to choose the kernel width s. For KDE, we used ﬁxed the number of training input points at Ntr = 100
5-fold LCV to choose the kernel widths for the training and changed the input dimension d = 10, 100, 1000 and2
3
6
and test√ densities.√ For KMM, we used B = 1000 and the number of test samples Nte = 10 , 10 , . . . , 10 .
² = ( Ntr − 1)/ Ntr following the suggestion in the In this experiment, we used linear basis function sooriginal KMM paper [13]. We tested two diﬀerent val- that the number of bases is equivalent to the input
ues of the kernel width (s = 0.1 and s = 1.0) for KMM dimension. We repeated the experiments 100 times
Rsince there is no reliable method to determine the ker- for each Nte and d on the PC server with an Intel°R°
nel width. For LogReg, we used 5-fold CV to choose the Xeon 3.6GHz ×2. All of them are implemented on R
(http://www.r-project.org).
regularization parameter σ and the kernel width s.
Figure 4 shows the average elapsed times for LLWe ﬁxed the number of test and training input
samples at Nte = 1000 and Ntr = 100, and varied KLIEP, LL-KLIEP(LS1), and LL-KLIEP(LS2). Notethe input dimension d = 2, 4, . . . , 20. We ran the that these results include the pre-computation times
simulation 100 times for each d, and evaluated the for the test samples. When d = 1000, the result
estimation accuracy of {w(x)}x∈Dtr by the mean NMSE of Nte = 106 was excluded for LL-KLIEP and LLKLIEP(LS2) because of the large memory requirements.
(see Eq.(5.26)).
The mean NMSE over 100 trials is plotted in The results show that the computational cost of LLFigure 3. We omitted the graphs of LL-KLIEP(LS1) KLIEP increases as the amount of test data Nte grows,
and LL-KLIEP(LS2) since they are almost identical but the computational cost of LL-KLIEP(LS) is nearly
to the solution of LL-KLIEP. Figure 3 shows that the independent of the number of test data Nte . Thiserror of KDE sharply increases as the input dimension is in good agreement with our theoretical analysis in
grows, while LL-KLIEP, KLIEP, and LogReg tend to Section 4.2. As we expected, LL-KLIEP is faster thangive much smaller errors than KDE. This would be LL-KLIEP(LS) when the number of test samples isthe fruit of directly estimating the importance without small, LL-KLIEP(LS1) is faster than LL-KLIEP(LS2)going through density estimation. The results of LL- for lower dimensional data, and LL-KLIEP(LS2) is
KLIEP and LogReg are slightly better than KLIEP, advantageous for high dimensional problem.

103

104

105

of Test=Samples(a) d =Number
10, N
100

tr

106

10

LL−KLIEPLL−KLIEP(LS1)LL−KLIEP(LS2)

10−2

10
10

−2

10−2
102

1

Elapsed Time (ms)

10−1

1

Elapsed Time (ms)10

LL−KLIEPLL−KLIEP(LS1)LL−KLIEP(LS2)

−1

1
10−1

Elapsed Time (ms)10

LL−KLIEPLL−KLIEP(LS1)LL−KLIEP(LS2)

102

103

104

105

106

102

Numberof Test(b) d =
100,
N Samples
= 100

tr

103

104

105

106

Numberof Test(c) d =
1000,
NSamples= 100

trFigure 4: Average computation time over 100 trials. The x (horizontal) axis represents the number of test samples(Nte ), and the y (vertical) axis represents the elapsed time (millisecond), respectively.
7.2 Covariate shift adaptation with regression
and classiﬁcation benchmark data sets. Finally,
we tested the importance estimation methods for covariate shift adaptation in regression and classiﬁcation
benchmark problems (see Table 7.2).
Each data set consists of input/output samples{(xi , yi )}N
i=1 . We normalized all of the input samplesd{xi }Ni=1 into [0, 1] and chose the test samples Zte =Nte{(xj , yj )}j=1 from the pool {xi }N
i=1 with probability
(c)

(c)

min(1, 4(xi )2 ), where xi was the c-th element ofxi and i was randomly determined and ﬁxed in eachtrtrial. We chose the training samples Ztr = {(xj , yj )}N
j=1
uniformly from the rest. In this experiment, the test
input density tends to be lower than the training input(c)density when xi is small. We set the number ofsamples at Ntr = 100 and Nte = 500 for all of the datasets.
We used IWLS for regression problems and IWRL
for classiﬁcation problems. Their basis functions arelinear: φ(x) = (1, x> )> .
We ran the experiments 100 times for each data set
and evaluated the mean test error :X(7.32)(fθ (x) − y)2 , (regression)(7.33)

X(x,y)∈Zte

I(sign(fθ (x)) = y), (classiﬁcation)

estimation methods LL-KLIEP, KLIEP, and LogReg
tend to outperform Uniform. KMM also works well
given that the kernel width is chosen appropriately—
but choosing the appropriate kernel width is diﬃcult inpractice without prior knowledge.
Over all, we found that LL-KLIEP is highly scalable
to large sets of test data while the accuracy is comparable to the best existing methods.
8

Conclusions

In this paper, we addressed the problem of estimating
the importance for covariate shift adaptation. We proposed a scalable direct importance estimation method
called LL-KLIEP. The computation time of LL-KLIEP
is nearly independent of the amount of test data, which
is a signiﬁcant advantage over existing approahes when
we deal with large numbers of test samples. Our experiments highlighted this advantage and we experimentally
conﬁrmed that the accuracy of the proposed method iscomparable to the best existing methods. Therefore theproposed method is a promising method for large-scalecovariate shift adaptation.
9

Acknowledgments

We thank the members of the T-PRIMAL group formany helpful discussions related to this work.

(x,y)∈Zte

where fθ (x) is deﬁned in Eq.(2.1). We compared the References
importance estimation methods used in Section 7.1.
The results are summarized in Table 7.2, where[1] P. Baldi and S. Brunak. Bioinformatics: The Machine“Uniform” denotes uniform weights, i.e., no importance
Learning Approach. MIT Press, Cambridge, 1998.
weight is used. The table shows that LL-KLIEP[2] S. Bickel. ECML 2006 discovery challenge workshop,
compares favorably with Uniform, implying that the2006.
importance weighted methods are useful for improving[3] S. Bickel, M. Brückner, and T. Scheﬀer. Discriminative
the prediction performance under covariate shift. KDE
learning for diﬀering training and test distributions.
tends to be worse than Uniform, which may be due
In Proceedings of the 24th international conference onto the high dimensionality. The direct importance
Machine learning, pages 81 – 88. ACM Press, 2007.

Table 3: Mean test error averaged over 100 trials. The numbers in the brackets are the standard deviation. All
the error values are normalized by that of Uniform (no importance weighting). The ﬁrst 5 are regression data setstaken from DELVE [16] and the next is a classiﬁcation data taken from IDA [17]. ‘# of better’ is the number ofdata sets for which each method performed better than uniform. ‘KMM(s)’ denotes KMM with kernel width s.
Data
Dim
Uniform
LL-KLIEP
KLIEP
KDE
KMM(0.1)
KMM(1.0)
LogRegkin-8fh
8 1.000(0.013) 0.998(0.013) 0.998(0.013) 1.102(0.023) 1.000(0.013) 2.436(0.202) 0.998(0.013)
kin-8fm
8 1.000(0.009) 0.998(0.009) 0.999(0.009) 1.0848(0.013) 0.999(0.009) 2.675(0.173) 0.998(0.009)
kin-8nh
8 1.000(0.115) 0.999(0.114) 1.000(0.115) 1.053(0.155) 1.001(0.116) 1.8416(1.400) 0.999(0.114)
kin-8nm
8 1.000(0.100) 0.998(0.097) 0.998(0.099) 1.047(0.135) 0.998(0.100) 2.116(2.515) 0.997(0.098)
abalone
7 1.000(1.747) 0.998(1.709) 0.992(1.645) 1.023(1.912) 1.902(18.337) 3.593(57.134) 0.988(1.591)
twonorm
20 1.000(0.021) 0.994(0.021) 0.997(0.022) 1.001(0.021) 1.001(0.021) 1.002(0.020) 0.998(0.021)# of better
–
6
5
0
2
0
6
[4] S. Bickel and T. Scheﬀer. Dirichlet-enhanced spamﬁltering based on biased samples. In Advances in
Neural Information Processing Systems. MIT Press,
Cambridge, MA, 2007.
[5] K. M. Borgwardt, A. Gretton, M. J. Rasch, H.-P.
Kriegel, B. Schölkopf, and A. J. Smola. Integrating
structured biological data by kernel maximum mean
discrepancy. Bioinformatics, 22(14):e49–e57, 2006.
[6] J. Q. Candela, N. Lawrence, A. Schwaighofer, and
M. Sugiyama. NIPS 2006 workshop on learning whentest and training inputs have diﬀerent distributions,
2006.
[7] D. A. Cohn, Z. Ghahramani, and M. I. Jordan. Active
learning with statistical models. Journal of Artiﬁcial
Intelligence Research, 4:129–145, 1996.
[8] V. V. Fedorov. Theory of Optimal Experiments. Academic Press, New York, 1972.
[9] G. S. Fishman. Monte Carlo: Concepts, Algorithms,
and Applications. Springer-Verlag, Berlin, 1996.
[10] W. Härdle, M. Müller, S. Sperlich, and A. Werwatz.
Nonparametric and Semiparametric Models. Springer
Series in Statistics. Springer, Berlin, 2004.
[11] D. Hawking, E. Voorhees, N. Craswell, and P. Bailey.
Overview of the trec-8 web track. In Proceedings of theEighth Text REtrieval Conference, pages 131–150.
[12] J. J. Heckman. Sample selection bias as a speciﬁcation
error. Econometrica, 47(1):153–162, 1979.
[13] J. Huang, A. J. Smola, A. Gretton, K. M. Borgwardt,
and B. Schölkopf. Correcting sample selection bias byunlabeled data. In Advances in Neural Information
Processing Systems, pages 601–608, Cambridge, MA,
2007. MIT Press.
[14] J. Jiang and C. Zhai. Instance weighting for domain
adaptation in nlp. In Proceedings of the 45th Annual
Meeting of the Association for Computational Linguistics, pages 264–271, 2007.
[15] T. Kanamori and H. Shimodaira. Active learning algorithm using the maximum weighted log-likelihood estimator. Journal of Statistical Planning and Inference,
116(1):149–162, 2003.
[16] C. E. Rasmussen, R. M. Neal, G. E. Hinton, D. V.
Camp, M. Revow, Z. Ghahramani, R. Kustra, andR. Tibshirani. The delve manual, 1996.
[17] G. Rätsch, T. Onoda, and K.-R. Müller. Soft margins

for adaboost. Machine Learning, pages 287–320, 2001.
[18] C. R. Shelton. Importance Sampling for Reinforcement
Learning with Multiple Objectives. PhD thesis, Massachusetts Institute of Technology, 2001.
[19] H. Shimodaira. Improving predictive inference undercovariate shift by weighting the log-likelihood function. Journal of Statistical Planning and Inference,90(2):227–244, 2000.
[20] I. Steinwart. On the inﬂuence of the kernel on theconsistency of support vector machines. Journal of
Machine Learning Research, 2:67–93, 2001.
[21] M. Sugiyama. Active learning in approximately linear
regression based on conditional expectation of generalization error. Journal of Machine Learning Research,
7:141–166, Jan. 2006.
[22] M. Sugiyama, M. Krauledat, and K.-R. Müller. Covariate shift adaptation by importance weighted cross validation. Journal of Machine Learning Research, 8:985–
1005, May 2007.
[23] M. Sugiyama and K.-R. Müller. Input-dependent
estimation of generalization error under covariate shift.
Statistics & Decisions, 23(4):249–279, 2005.
[24] M. Sugiyama, S. Nakajima, H. Kashima, P. von Bünau,
and M. Kawanabe. Direct importance estimation
with model selection and its application to covariate
shift adaptation. In Advances in Neural Information
Processing Systems, Cambridge, MA, 2008. MIT Press.
[25] R. S. Sutton and G. A. Barto. Reinforcement Learning:
An Introduction. MIT Press, Cambridge, MA, 1998.
[26] G. Wahba. Spline Model for Observational Data. Society for Industrial and Applied Mathematics, Philadelphia and Pennsylvania, 1990.
[27] D. P. Wiens. Robust weights and designs for biased
regression models: Least squares and generalized Mestimation. Journal of Statistical Planning and Inference, 83(2):395–412, 2000.
[28] J. R. Wolpaw, N. Birbaumer, D. J. McFarland,
G. Pfurtscheller, and T. M. Vaughan. Brain-computerinterfaces for communication and control. Clinical
Neurophysiology, 113(6):767–791, 2002.
[29] B. Zadrozny. Learning and evaluating classiﬁers undersample selection bias. In Proceedings of the 21stInternational Conference on Machine Learning, New
York, NY, 2004. ACM Press.