ビジネス・ユニットの名前

Direct Density Ratio Estimation
for Large-scale Covariate Shift Adaptation
Yuta Tsuboi (*), Hisashi Kashima, Shohei Hido,
IBM Research, Tokyo Research Laboratory* Nara Institute of Science and Technology

Steffen Bickel,
Max Planck Institute for Computer Science

Masashi Sugiyama
PSU_temp_0522

Tokyo Institute of Technology, Department of Computer Science

IBM Corporation
8/3/05

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
© 2008 IBM Corporation

SIAM Conference on Data Mining (SDM08)

ビジネス・ユニットの名前

Table of Contents
1. Motivation
Covariate shift situation
Direct density estimation methods
2. Proposed Method
LL-KLIEP: Log-linear model for KLIEP••

Log-linear model: natural modeling for density ratio function
Standard optimization techniques to learn a density ratio function
LL-KLIEP(LS): Another optimization technique for LL-KLIEPFor applications with large numbers of unlabeled test inputs

PSU_temp_0522

2

IBM Corporation I 8/4/05

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

SIAM Conference on Data Mining (SDM08)

ビジネス・ユニットの名前

Covariate shift situation

Training and test inputs x follow different distributions

p train (x)p test (x)p train ( y | x)

p test ( y | x)

Input distribution changes:
Functional relation remains unchanged:
Labeled training inputs from

Unlabeled test inputs fromp train (x)p test (x)p train (x)p test (x)Classification
under
Covariate
Shift
PSU_temp_0522

3

IBM Corporation I 8/4/05

p train (x) p test (x)

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

ビジネス・ユニットの名前

SIAM Conference on Data Mining (SDM08)

Examples of covariate shift situation
Domain Adaptation & Selective Sampling (Active Learning)
Domain adaptation of statistical classifiers– The data distribution in the test domain is different from that in the
training domain. (Note: the functional relation can also be changed)• E.g.: Spam filters can be trained on public collections of spam, but
are applied to an individual person's inbox. (Personalization)?
?
Domain A (train)

?

? ? ?
?
?

Domain B (test)

Selective sampling (active learning) of statistical classifiers– The learning algorithm can actively query the teacher for labels.
– Since the learner chooses the examples by design,
Selecting & Labelingthe data distribution of?
the labeled training examples is?
? ?
different from that of a sample pool.
?
PSU_temp_0522

train
4

IBM Corporation I 8/4/05

?

?
test

? ?

? ?

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

SIAM Conference on Data Mining (SDM08)

ビジネス・ユニットの名前

A common approach for covariate shift situation
Weighting the training examples by importance.
Density ratio (importance):wx

p test (x).
p train (x)Example: Importance Weighted Logistic Regression (IWLR)- Weighted Log-likelihood for Logistic Regression (LR)p test x p y | x pθ y | x dxdy

Labeled training inputs

LR modelwx

p test x
p train x
p y | x logpθ y | x dxdy
p train x
w x y fθ x

log 1 exp y f θ x

.

1

LR
IWLR

( x , y ) Z train

Training data

PSU_temp_0522

5Density ratio(Importance)

IBM Corporation I 8/4/05

Log-likelihoodwx1

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

SIAM Conference on Data Mining (SDM08)

ビジネス・ユニットの名前

We need to estimate the density ratio from samples.

Importance Estimation

Problem setting: i.i.d. training and test samples are
given
Training inputs:
Test inputs:

Dtr
Dte

N tr
i i 1

from Ptrain x

N te
i i 1

from Ptest xxxNaïve approach: estimate Ptrain x and Ptest x separately,
and take the ratio of the density estimates
However, density P x estimation is the hard problem
particularly in high dimensional cases.
PSU_temp_0522

6

IBM Corporation I 8/4/05

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

SIAM Conference on Data Mining (SDM08)

ビジネス・ユニットの名前

Table of Contents
1. Motivation
Covariate shift situation
Direct density estimation methods
2. Proposed Method
LL-KLIEP: Log-linear model for KLIEP••

Log-linear model: natural modeling for density ratio function
Standard optimization techniques to learn a density ratio function
LL-KLIEP(LS): Another optimization technique for LL-KLIEPFor applications with large numbers of unlabeled test inputs

PSU_temp_0522

7

IBM Corporation I 8/4/05

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

SIAM Conference on Data Mining (SDM08)

ビジネス・ユニットの名前

Modeling Density ratio by Log-linear Model
We use a log-linear model:

α: model parameter
ψ(x) : basis function< , > : inner productTraining data set– ŵ xtakes only non-negative values.

natural modeling for ratio （α and ψ(x) can be an arbitraryvalue）– The denominator guarantees p̂test x be a probability density
function
Test density is approximated by

PSU_temp_0522

8

Learn α so that
IBM Corporation I 8/4/05

p̂test x

ptest xapproximates ptest x

ptrain x

ptest xptrain xwell.

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

SIAM Conference on Data Mining (SDM08)

ビジネス・ユニットの名前

Kullback—Leibler (KL) Divergence
Minimize KL divergence between p test x and p̂ test x:

arg minKL p test x || p̂ test xαp̂ test x

p train x ŵ x

KL p test x || p̂ test x
p test x
p test x log
dxp̂ train x wˆ x
p test x
p test x log
dx
p train x

p test x log wˆ x dx

constant

relevant

PSU_temp_0522

9

IBM Corporation I 8/4/05

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

SIAM Conference on Data Mining (SDM08)

ビジネス・ユニットの名前

Kullback-Leibler Importance Estimation Procedure (KLIEP)
for Log-linear Models: LL-KLIEP
Thus, arg minKL pα

testx || p̂ test x

arg max p test x log wˆ x dx
α

Empirical approximation of objective function (LL-KLIEP)

Objective function
J LL KLIEP

Test data set

Training data set

αUnconstraint convex optimization:– standard gradient ascent method can be used.
PSU_temp_0522

10– unique global solution is available.
IBM Corporation I 8/4/05

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

SIAM Conference on Data Mining (SDM08)

ビジネス・ユニットの名前

Mean Matching via LL-KLIEP

Gradient of the objective function

J LL KLIEP αα1x
N test x Dtest

The mean of Test data1wx

N train x Dtrainx

The mean of Weighted Training data

At the optimum,
the mean x of test inputs = the mean w x

x of training inputs.

Finding w(x) matching the mean of two distributions.

PSU_temp_0522

11

IBM Corporation I 8/4/05

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

SIAM Conference on Data Mining (SDM08)

ビジネス・ユニットの名前

Samples were generated from two Gaussian distributions.
We used 100 Gaussian basis functions (Gaussian kernels)
centered at randomly chosen test input samples.

ψl xTraining and Test Densities

exp

x x

test 2l

2s 2

Estimated Importance

PSU_temp_0522

12

IBM Corporation I 8/4/05

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

SIAM Conference on Data Mining (SDM08)

ビジネス・ユニットの名前

Model selection of KLIEP/LL-KLIEP
Likelihood Cross Validation (LCV)The performance of KLIEP depends on the choice of the basis functions ψ x
How to choose hyper parameters, e.g., the kernel width s for Gaussian
kernels:
However, the correct value of importance for each x is not available forunknown distributions p train x and p test x
unsupervised learning setting
LCV: Select the model such that maximized
1. Divide test samples into R disjoint subsets:
2. Learn importance:
3. Evaluate a model by likelihood:

PSU_temp_0522

13

IBM Corporation I 8/4/05

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

SIAM Conference on Data Mining (SDM08)

ビジネス・ユニットの名前

Classification example under Covariate shift2-dimensional samples were generated from Gaussian
distributions
We used Importance Weighted Logistic
Regression (IWLR)

Correctclassification rateof LR is 99.1%
while that of IWLR
is 100%.
PSU_temp_0522

14

IBM Corporation I 8/4/05

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

SIAM Conference on Data Mining (SDM08)

ビジネス・ユニットの名前

Classification example under Covariate shift2-dimensional samples were generated from Gaussian
distributions
We used Importance Weighted
Logistic Regression (IWLR).

Correctclassification rateof LR is 97.2%
while that of IWLR
is 99.1%.
PSU_temp_0522

15

IBM Corporation I 8/4/05

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

SIAM Conference on Data Mining (SDM08)

ビジネス・ユニットの名前

Related Work of Density Ratio Estimationwx

p test (x).
p train (x)Kernel density estimator (KDE)– Separately estimate training and test input densities.
– Gaussian kernel width is chosen by likelihood cross-validation.
Kernel Mean Matching (KMM) (Huang et al., NIPS2006)– Direct importance estimation method in universal reproducing kernel
Hilbert spaces (RKHS)– There is no model selection method for kernel width.
Logistic regression (LogReg) (Beckel et al., ICML2007)– Classifier discriminating training and test input data.
– Gaussian kernel width is chosen by likelihood cross-validation.
Kullback-Leibler Importance Estimation Procedure (KLIEP) (Sugiyama
et al., NIPS2007)– Direct importance estimation method using KL Divergence.
– Gaussian kernel width is chosen by likelihood cross-validation.
PSU_temp_0522

16

IBM Corporation I 8/4/05

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

SIAM Conference on Data Mining (SDM08)

ビジネス・ユニットの名前

Experiments
varying input dimension
Mean NMSE over 100 trials.
KMM (s) denotes KMM withkernel width s
NMSE:
Normalized Mean Squared Error

KDE: Suffers from the curse ofdimensionality
KMM: Performance depends onkernel width

KLIEP, LogReg, and LL-KLIEP: Model selection by LCV works well

PSU_temp_0522

17

IBM Corporation I 8/4/05

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

SIAM Conference on Data Mining (SDM08)

ビジネス・ユニットの名前

Table of Contents
1. Motivation
Covariate shift situation
Direct density estimation methods
2. Proposed Method
LL-KLIEP: Log-linear model for KLIEP••

Log-linear model: natural modeling for density ratio function
Standard optimization techniques to learn a density ratio function
LL-KLIEP(LS): Another optimization technique for LL-KLIEPFor applications with large numbers of unlabeled test inputs

PSU_temp_0522

18

IBM Corporation I 8/4/05

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

SIAM Conference on Data Mining (SDM08)

ビジネス・ユニットの名前

Disadvantage: LL-KLIEP and previous methods require to use
all test inputs in their optimization procedure.
We need to iterate over all test inputs when computing the valuesof the objective function:

J LL KLIEP α

1α,
N test x Dtestx

Evaluation over Test data set

log

1log α,

N train x Dtrainx

Evaluation over Training data set

However, the gradient of the objective function requires theevaluation of all test samples once.

J LL KLIEP αα

Independent from α

PSU_temp_0522

191x
N test x Dtest

IBM Corporation I 8/4/05

1wx

N train x Dtrainx

Pre-computing the value

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

SIAM Conference on Data Mining (SDM08)

ビジネス・ユニットの名前

An optimization technique w/o the objective function evaluation

LL-KLIEP(LS1)

Idea: the derivative of the convex objective function to be zero at the
optimum point.
Minimizing a squared norm to measure the ‘magnitude’ of thederivative:

Objective function
for LL-KLIEP(LS1)J LL KLIEP(LS1)1
2J LL KLIEP αα2Computation time & memory size are independent of Ntest.
– However, the derivative is a quadratic function of the number ofparameters, which could be a bottleneck in high dimensional problems.

The partial derivative of LL-KLIEP(LS1)J LL KLIEP(LS1) αα

PSU_temp_0522

20

IBM Corporation I 8/4/05

2

J LL KLIEP α
2α

J LL KLIEP αα

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

ビジネス・ユニットの名前

SIAM Conference on Data Mining (SDM08)

LL-KLIEP(LS) for the high-dimensional data

LL-KLIEP(LS2)

Idea: representing the parameter α as a linear combination of
the training inputs (representer theorem (Wahba 1990)):
where

is a data-wise parameter.

– Now, the computation time is linear w.r.t. the number ofparameters, α (quadratic w.r.t. the number of the training
inputs, Ntrain).

PSU_temp_0522

21

IBM Corporation I 8/4/05

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

ビジネス・ユニットの名前

SIAM Conference on Data Mining (SDM08)

LL-KLIEP (LS): No iteration and no storage for Nte in
optimization
Well-suited to the applications with the large
amount of test samples

LL-KLIEP (LS1) : For lower-dimensional and large-scale training
data.
PSU_temp_0522

22

LL-KLIEP (LS2): For higher-dimensional and moderate-size training
data.
IBM Corporation I 8/4/05

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

SIAM Conference on Data Mining (SDM08)

ビジネス・ユニットの名前

Average computation time (including Pre-comp.)
over 100 trials

We varied the number of test inputs, and fixed the number of training inputs.

Lower-dimensional data

we used linear basis function
so that the number of bases is
equivalent to the input
dimension.
d: input dimension =#parameter,
Ntr: The number of training
inputs,Nte: The number of test inputs

The computation timeof LL-KLIEP(LS) is
independent from thenumber of test inputs.

PSU_temp_0522

23

IBM Corporation I 8/4/05

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

SIAM Conference on Data Mining (SDM08)

ビジネス・ユニットの名前

Average computation time (including Pre-comp.) over 100 trials

We varied the number of test inputs, and fixed the number of training inputs.

d: input dimension = #parameter,
Ntr: The number of training inputs, Nte: The number of test inputs

Moderate-dimensional data

Higher-dimensional data

PSU_temp_0522

24

IBM Corporation I 8/4/05

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

ビジネス・ユニットの名前

SIAM Conference on Data Mining (SDM08)

Conclusion

We proposed a density ratio estimation method called
LL-KLIEP.
We also proposed a scalable optimization techniquefor LL-KLIEP, in which all the test inputs are iterated
once.
– The computation time is nearly independent of theamount of test data
– The memory requirement is independent of theamount of test data.

PSU_temp_0522

25

IBM Corporation I 8/4/05

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

ビジネス・ユニットの名前

SIAM Conference on Data Mining (SDM08)

Thank you!

PSU_temp_0522

26

IBM Corporation I 8/4/05

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

SIAM Conference on Data Mining (SDM08)

ビジネス・ユニットの名前

KLIEP/LL-KLIEP objective functions
KLIEP has a log form in the evaluation of test inputs.

J KLEIP α
subject to

J KLEIP αα

1log α, ψ x ,N test x Dtest
1
N train x Dtrainα, ψ x1, and α 01ψx
N test x Dtest α, ψ x

LL-KLIEP has a linear form in the evaluation of test inputs.

J LL KLEIP α
PSU_temp_0522

27

IBM Corporation I 8/4/05

1α, ψ xN test x Dtest

log

1

exp α, ψ x

N train x Dtrain

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

SIAM Conference on Data Mining (SDM08)

ビジネス・ユニットの名前

Kullback-Leibler Importance Estimation Procedure(KLIEP) for Log-linear Models: LL-KLIEP
Regularized version of LL-KLIEP
regularizer

Gradient of the objective function
1
N trainAt the optimum,
the mean x of test inputs = the mean w x

PSU_temp_0522

28

IBM Corporation I 8/4/05

wx

x of training inputs.

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

SIAM Conference on Data Mining (SDM08)

ビジネス・ユニットの名前

LL-KLIEP(LS) for the high-dimensional data

LL-KLIEP(LS2)

Idea: representing the parameter α as a linear combination of
the training inputs (representer theorem (Wahba 1990)):
where

is a data-wise parameter.

Objective function for LL-KLIEP(LS2)where– Now, the computation time is linear w.r.t. the number of parameters(quadratic w.r.t. the number of the training inputs).

PSU_temp_0522

29

IBM Corporation I 8/4/05

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

SIAM Conference on Data Mining (SDM08)

ビジネス・ユニットの名前

Related work: Kernel Mean Matching (KMM)

LL-KLIEP (LS2) without a regularizer has the same form as

the objective function of KMM.
Moment matching method:

Objective function for KMM

The objective function of LL-KLIEP (LS2):

Disadvantage of KMM.
The estimates of w(x) areonly available for training
samples Cannot optimize
hyper parameters by CV

PSU_temp_0522

30

IBM Corporation I 8/4/05

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

ビジネス・ユニットの名前

SIAM Conference on Data Mining (SDM08)

Related work: Logistic regression (LogReg)
Classifier discriminating training and test input data
Selector variable δ = -1 to the training input samples and δ = 1 to thetest input samples:

Importance can be
The conditional probability p(δjx) 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.

Empirical estimation

Objective function: regularized maximum likelihood estimation
PSU_temp_0522

31

Disadvantage: summation over both training and test samples in CV.
IBM Corporation I 8/4/05

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

SIAM Conference on Data Mining (SDM08)

ビジネス・ユニットの名前

Related work:
Kernel density estimator (KDE)
Estimating

ptrain x and ptest x

separately.

KDE: non-parametric density estimator

KDE suffers from the curse of dimensionality

PSU_temp_0522

32

IBM Corporation I 8/4/05

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation

SIAM Conference on Data Mining (SDM08)

ビジネス・ユニットの名前

An example of supervised learning under covariate shift

Importance weighted logistic regression (IWLR)
Logistic Regression (LR) : binary caseLR classifier
Training LR:
Density ratio is used as weights in the log-likelihood
function

PSU_temp_0522

33

Training data
IBM Corporation I 8/4/05

Density ratio

Log-likelihood

Regularizer
λ：a hyper parameter

この文書のデータの利用または公開には、最終ページに記載されている制限事項が適用されます。
Direct Density Ratio
Estimation for Large-scale Covariate Shift Adaptation © 2008 IBM Corporation