NIPS2007, Vancouver, Canada

Dec.3-8, 2007

Direct Importance Estimation withModel Selection and Its Application
to Covariate Shift Adaptation
Masashi Sugiyama
Tokyo Institute of Technology, Tokyo, Japan
Shinichi Nakajima
Nikon Corporation, Saitama, Japan
Hisashi Kashima
IBM Research, Kanagawa, Japan
Paul von Bünau
Technical University Berlin, Berlin, Germany
Motoaki Kawanabe
Fraunhofer FIRST, Berlin, Germany

Abstract

2When training and test samples follow different input distributions(i.e., the situation called covariate shift), the maximum likelihood
estimator is known to lose its consistency. For regaining
consistency, the log-likelihood terms need to be weighted
according to the importance (i.e., the ratio of test and training
input densities). Thus, accurately estimating the importance is oneof the key tasks in covariate shift adaptation. A naive approach is
to first estimate training and test input densities and then estimate
the importance by the ratio of the density estimates. However,since density estimation is a hard problem, this approach tends toperform poorly especially in high dimensional cases. In this paper,
we propose a direct importance estimation method that does not
require the input density estimates. Our method is equipped with anatural model selection procedure so tuning parameters such as
the kernel width can be objectively optimized. This is anadvantage over a recently developed method of direct importanceestimation. Simulations illustrate the usefulness of our approach.

Common Assumption
in Supervised LearningIn supervised learning, we always assume
Training and test samples are
drawn from the same distribution

Is this assumption really true?

Not Always True!

3Face Recognition
We tend to collect easy-to-gathersamples for training.
z Training: less women in research labsz Test: almost 50-50 in general

The Yale Face Database B4

5Survey SamplingThose who have strong opinions tend
to reply to questionnaires.
z Training: extreme opinionsz Test: most people are neutral

Poor!

Neutral

Excellent!

Brain-Computer Interface
Sample generation mechanism varies.
z Input: EEG signals
z Output: “left” or “right” commands
z Different mental conditions between training(sleepy…) and test (exciting!) phases maychange the EEG signals.

Figure provided by Fraunhofer FIRST, Berlin, Germany

6

Robot Control
by Reinforcement Learning
Updating a robot’s behavior
causes a distribution change.

Khepera Robot7

Covariate Shift8

However, no chance for generalization
if training and test samples havenothing in common.
We need a (reasonable) constraint
Covariate shift
zInput distribution changes:

zFunctional relation remains unchanged:

Illustration of Covariate Shift(Weak) extrapolation:
Predict output values outside training region
Trainingsamples

Testsamples
Truefunction
Learnedfunction

910Bias and VarianceGeneralization error (expected test error):

Bias
Variance: expectation over samples

BiasVarianceModel Specification
Model is said to be correctly specified if

In practice, our model may not be correct.
Therefore, we need to explicitly deal with
misspecified models!

11

Ordinary Least-Squares (OLS) 12

If model is correct:z OLS minimizes bias

asymptoticallyIf model is misspecified:z OLS does not minimize

bias even asymptotically.

We want to reduce bias!

Importance-Weighted LS (IWLS)13:Importance:Assumed strictly positive

Even for misspedified models,
IWLS minimizes bias
asymptotically.
We need to estimate theimportance in practice.

Importance Estimation14

Setting: training and test inputs are givenNaïve approach: estimate
andseparately, and take the ratio of thedensity estimatesNaïve approach does not work well sincedensity estimation is hard in high dimensions.

Modeling Importance Function 15
We use a linear model:Test density is approximated byLearn
so thatapproximates

well.

Kullback-Leibler Divergence 16(constant)(relevant)Learning Importance Function 17
ThusSince(objective function)
is density,(constraint)

18
KLIEP (Kullback-Leibler
Importance Estimation Procedure)Convexity: unique global solution is available
Sparse solution: prediction is fast!

Examples19Model Selection of KLIEP

20

How to choose tuning parameters (such as
Gaussian width)?
Likelihood cross-validation:z Divide test samples.
z Estimate the likelihood usingintoz Learn importance from

This gives an unbiased
estimate of KL (up toan irrelevant constant).

.

and.

Illustrative Experiments: Setup 21
Kernel density estimator (KDE):z Separately estimate training and test input densities.
z Gaussian kernel width is chosen by likelihoodcross-validation.

Kernel mean matching (KMM): (Huang et al., NIPS2006)z Direct importance estimation method using

universal reproducing kernel Hilbert spaces
z There is no model selection method for kernel
width; we test several different widths.

Input distributions: standard Gaussian withz Training: mean (0,0,…,0)z Test:mean (1,0,…,0)22Illustrative Experiments: Results

KDE: Suffers from the curse of dimensionality
KMM: Performance depends on kernel width
KLIEP: Model selection by LCV works well

Regression/Classification

Goal: givenpredict.
Gaussian kernel model:

23,

Regularized IWLS:

Importance is estimated by KLIEP with LCV.
are chosen by importance-weighted(Sugiyama et al., JMLR2007)
cross-validation.

24

Results

Classification

Regression

Normalized test error(mean and standard deviation over 100 trials)
DataDim

Uniform

KLIEP(LCV) KDE(LCV) KMM(0.01) KMM(0.3)

Kin-8fh

81.00(0.34)

0.95(0.31)

1.22(0.52)

1.00(0.34)

0.97(0.34) 1.47(0.24)

Kin-8fm

81.00(0.39)

0.86(0.35)

1.12(0.57)

1.00(0.39)

0.93(0.39) 1.72(0.35)

Kin-8nh8

1.00(0.26)

0.99(0.22)

1.09(0.20)

1.00(0.26)

1.00(0.22) 1.15(0.25)

Kin-8nm81.00(0.30)

0.97(0.25)

1.14(0.26)

1.00(0.30)

1.00(0.29) 1.19(0.22)

Abalone7

1.00(0.50)

0.94(0.67)

1.02(0.41)

0.99(0.50)

1.03(0.74) 0.93(0.40)

Image

18

1.00(0.50)

0.92(0.41)

0.98(0.44)

0.97(0.50)

0.98(0.46) 1.06(0.50)

Ringnorm20

1.00(0.04)

0.99(0.06)

0.87(0.04)

1.00(0.04)

0.96(0.07) 0.88(0.06)

Twonorm20

1.00(0.58)

0.91(0.52)

1.16(0.71)

0.98(0.50)

0.82(0.52) 0.97(0.62)

Waveform

21

1.00(0.45)

0.93(0.34)

1.05(0.47)

1.00(0.45)

0.94(0.34) 1.00(0.33)

KMM(1)

Red: Best method and comparable ones by Wilcoxon
signed rank test at significance level 5%