Neurocomputing, vol.80, pp.93-101, 2012.

1

Importance-Weighted Least-Squares Probabilistic
Classifier for Covariate Shift Adaptation with
Application to Human Activity Recognition
Hirotaka Hachiya
Tokyo Institute of Technology, Tokyo, Japanhachiya@sg.cs.titech.ac.jp
Masashi Sugiyama
Tokyo Institute of Technology, Tokyo, Japansugi@cs.titech.ac.jp
http://sugiyama-www.cs.titech.ac.jp/~sugi/
Naonori Ueda
NTT Communication Science Laboratories, Kyoto, Japanueda@cslab.kecl.ntt.co.jp

Abstract
Human activity recognition from accelerometric data (e.g., obtained by smart phones)
is gathering a great deal of attention since it can be used for various purposes suchas remote health-care. However, since collecting labeled data is bothersome for newusers, it is desirable to utilize data obtained from existing users. In this paper, weformulate this adaptation problem as learning under covariate shift, and propose
a computationally eﬃcient probabilistic classiﬁcation method based on adaptive
importance sampling. The usefulness of the proposed method is demonstrated inreal-world human activity recognition.

1

Introduction

Human activity recognition from accelerometric data (e.g., obtained by smart phones)
is gathering a great deal of attention recently [1, 2, 11], since it can be used for various
purposes such as remote health-care [10, 25, 17] and worker behavior monitoring [34]. To
construct a good classiﬁer for activity recognition, users are required to prepare accelerometric data with activity labels for various types of actions such as walking, running, andbicycle riding. However, since gathering labeled data is costly, this initial data-collection

Importance-Weighted Least-Squares Probabilistic Classifier

2phase prevents new users from using the activity recognition system. Thus, overcoming
such a new user problem is an important challenge for increasing the practical usabilityof the human activity recognition system.
Since unlabeled data are relatively easy to gather, we can typically use labeled dataobtained from existing users and unlabeled data obtained from a new user for developing
the new user’s activity classiﬁer. Such a situation is commonly called semi-supervised
learning, and various learning methods that utilize unlabeled samples have been proposedso far [5]. However, such semi-supervised learning methods tend to perform poorly if
unlabeled test data have a signiﬁcantly diﬀerent distribution from the labeled training
data. Unfortunately, this is a typical situation in human activity recognition since motion
patterns (and thus distributions of motion data) depend heavily on users.
To cope with the diﬀering distributions, several approaches have been explored [21,19]. Popular lines of research include re-weighting samples according to the importance[23, 12, 30, 13, 6, 27] and learning feature representation that is common to training andtest data [4, 8, 3, 9, 18]. In this paper, we focus on the sample re-weighting approach, andpropose a new probabilistic classiﬁcation method that is computationally very eﬃcient.
Our proposed approach combines a probabilistic classiﬁcation method called least-squares
probabilistic classiﬁer [26, 33] with the sample re-weighting approach [23, 13]. Throughexperiments on real-world human activity recognition, we demonstrate the usefulness of
our proposed approach.
The rest of this paper is organized as follows. In Section 2, we formulate a classiﬁcation
problem, and describe our proposed method called the importance-weighted least-squares
probabilistic classiﬁer (IWLSPC). In Section 3, we discuss the relation between proposedand existing approaches. Experimental results are reported in Section 4, demonstrating the eﬀectiveness of the proposed IWLSPC algorithm in real-world human activity
recognition. Finally, we conclude in Section 5 by summarizing our contributions.

2

Learning under Covariate Shift

In this paper, we consider the classiﬁcation problem under covariate shift [23, 27], i.e.,the distributions of input points change between the training and test phases, but theconditional distribution of class labels given input points remains unchanged. In thissection, we ﬁrst formulate the classiﬁcation problem under covariate shift, and then giveour proposed method called the importance-weighted least-squares probabilistic classiﬁer(IWLSPC).

2.1

Problem Formulationdtr
tr NtrSuppose we are given labeled training samples {(xtrn , yn )}n=1 , where xn ∈ R (d denotes
the input dimensionality) is a training input point drawn independently from a probability
distribution with density ptr (x), and yntr ∈ {1, . . . , c} (c denotes the number of classes) isa training label following a conditional probability distribution with density p(y|x = xtr
n ).

Importance-Weighted Least-Squares Probabilistic Classifier3

In addition to the labeled training samples, suppose we are given unlabeled test input
Ntetedpoints {xten }n=1 , where xn (∈ R ) is a test input point drawn independently from aprobability distribution with density pte (x). Note that pte (x) ̸= ptr (x) in general, andthus the input distributions are diﬀerent between the training and test phases.
Our goal is to learn a classiﬁer that predicts a class label y te for a test input point xte .

2.2

Importance-Weighted Least-Squares Probabilistic Classifier

Here, we describe our proposed method called the importance-weighted least-squares probabilistic classiﬁer (IWLSPC), which combines a probabilistic classiﬁcation method called
least-squares probabilistic classiﬁer [26, 33] with the covariate shift adaptation technique[23, 13].
The goal of probabilistic classiﬁcation is to estimate the class-posterior probabilityp(y|x). Let us model the class-posterior probability p(y|x) byp(y|x; θy ) ≡Nte∑θy,n K(x, xte
n ),

n=1

where θy = (θy,1 , . . . , θy,Nte )⊤ is the parameter vector and K(x, x′ ) is a kernel function.
Below, we focus on the Gaussian kernel:()∥x − x′ ∥2′K(x, x ) = exp −,2σ 2where σ denotes the Gaussian kernel width. We determine the parameter θy so that thefollowing squared error Jy is minimized:∫)2
1 (Jy (θy ) ≡p(y|x; θy ) − p(y|x) pte (x)dx2∫1=p(y|x; θy )2 pte (x)dx2∫− p(y|x; θy )p(y|x)pte (x)dx + C
1= θy⊤ Qθy − qy⊤ θy + C,2
where C is a constant independent of the parameter θy , and Q is the Nte × Nte matrix
and qy = (qy,1 , . . . , qy,Nte )⊤ is the Nte -dimensional vector deﬁned as∫teQn,n′ ≡ K(x, xten )K(x, xn′ )pte (x)dx,∫
qy,n ≡ K(x, xten )p(y|x)pte (x)dx.

Importance-Weighted Least-Squares Probabilistic Classifier

4Here, we approximate Q and qy using the adaptive importance sampling technique [23]as follows. First, using the importance weight deﬁned asw(x) ≡

pte (x),ptr (x)(1)

we express Q and qy in terms of the training distribution as∫
teQn,n′ = K(x, xten )K(x, xn′ )ptr (x)w(x)dx,∫
qy,n = K(x, xten )p(y|x)ptr (x)w(x)dx∫= p(y) K(x, xten )ptr (x|y)w(x)dx,
where ptr (x|y) denotes the training input density for class y. Then, based on the above
tr Ntrexpressions, Q and qy are approximated using the training samples {(xtrn , yn )}n=1 as
follows1 :
Ntr
1 ∑
te
te
te
tr ν
b
Qn,n′ ≡
K(xtrn′′ , xn )K(xn′′ , xn′ )w(xn′′ ) ,Ntr n′′ =1
1 ∑
te
tr ν
qby,n ≡
K(xtrn′ , xn )w(xn′ ) ,Ntr ′ trn :yn′ =y

(y)

(y)

where the class-prior probability p(y) was estimated by Ntr /Ntr , and Ntr denotes thenumber of training samples with label y. ν (0 ≤ ν ≤ 1) is the ﬂattening parameter, which
controls the bias-variance trade-oﬀ in importance sampling [23]. More speciﬁcally, if ν isclose to 1, the importance weights are used as they are; then the bias gets smaller, but
the variance tends to be larger. On the other hand, if ν is close to 0, the importanceweights tend to be one (i.e., ﬂat). Then the bias is larger, but the variance is smaller.
Consequently, we arrive at the following optimization problem:
]
[
λ
1
⊤
⊤
⊤
b y − qb θy + θ θy ,
θby ≡ arg min θy Qθ
y
2
2 y
θy
where λ2 θy⊤ θy is a regularization term to avoid over-ﬁtting and λ (≥ 0) is the regularization
parameter. Then, the IWLSPC solution is given analytically asb + λINte )−1 qby ,θby = (Q1

Nte
When ν = 1, Q may be approximated directly using the test input samples {xten }n=1 as
te
∑
te
te
te
b n,n′ ≡ 1QK(xten′′ , xn )K(xn′′ , xn′ ).
Nte ′′

Nn =1

Importance-Weighted Least-Squares Probabilistic Classifier

5

where INte denotes the Nte -dimensional identity matrix. Since the class-posterior probability is non-negative by deﬁnition, we modify the solution as
( N
)
te
∑
1
pb(y|x) ≡ max 0,
θby,n K(x, xte
n) ,
Z
n=1
if Z ≡

( ∑
)
Nte b
te
max
0,
θ
K(x,
x
)
> 0; otherwise, pb(y|x) ≡ 1/c.
ny=1n=1 y,n∑c

The learned class-posterior probability pb(y|x) allows us to predict the class label y teof a new test sample xte byybte ≡ arg max pb(y|xte ),ywith conﬁdence pb(by te |xte ).
When pte (x) = ptr (x), the above IWLSPC is reduced to the original LSPC [26, 33].
Thus, IWLSPC can be regarded as a natural extension of LSPC to covariate shift situations.
The performance of IWLSPC depends on the choice of the regularization parameter
λ, the Gaussian kernel width σ, and the ﬂattening parameter ν. Thus, model selection is
critical in practice, and cross-validation (CV) is a popular choice for this purpose. However, under covariate shift, ordinary CV is highly biased due to the diﬀering distributions.
To cope with this problem, a variant of CV called importance-weighted CV (IWCV) has
been proposed [28], which is still almost unbiased even under covariate shift. We will use
IWCV for model selection of IWLSPC in our experiments. A brief review of IWCV isprovided in A.
Ntr
IWLSPC (and IWCV) requires the values of the importance {w(xtrn )}n=1 , which areunknown in practice. So far, various methods for estimating the importance has beendeveloped [24, 7, 20, 12, 30, 13, 29]. Among them, the method called unconstrained
least-squares importance ﬁtting (uLSIF) [13] was shown to be superior since it achieves
the optimal convergence rate [14], it possesses the optimal numerical stability [15], andits solution can be computed analytically. For this reason, we will employ uLSIF in our
experiments. A brief review of uLSIF is provided in B.
A MATLAB implementation of IWLSPC is available from‘http://sugiyama-www.cs.titech.ac.jp/~hachiya/software/IWLSPC/’.

3

Related Works

In this section, we review two related works: Laplacian regularized least-squares (LapRLS)
and importance-weighted kernel logistic regression (IWKLR). These two methods will be
regarded as baselines for experimental performance comparison in Section 4.

Importance-Weighted Least-Squares Probabilistic Classifier

3.1

6

Laplacian Regularized Least-Squares

Laplacian regularized least-squares (LapRLS) is a standard semi-supervised learning
method which tries to impose smoothness over non-linear data manifold [5]. Let us consider a binary classiﬁcation problem where y ∈ {+1, −1}. LapRLS uses a kernel model
for class prediction2 :Nte∑k(x; θ) ≡θn K(x, xte
n ).
n=1

The parameter θ is determined as
[
]
Ntr (
N
)
∑
∑
2
1
tr
min
k(xtr
+ λθ ⊤ θ + η
Ln,n′ k(xn ; θ)k(xn′ ; θ) ,n ; θ) − ynθ
Ntr n=1n,n′ =1
where the ﬁrst term is the goodness of ﬁt, the second term is the ℓ2 -regularizer to avoid
over-ﬁtting, and the third term is the Laplacian regularizer to impose smoothness overdata manifold. N ≡ Ntr + Nte , L ≡ D − W is the N × N graph Laplacian matrix, W isan aﬃnity matrix deﬁned by)(∥xn − xn′ ∥2
Wn,n′ ≡ exp −
,
2τ 2
tr
te
te
(x1 , . . . , xN ) ≡ (xtr
1 , . . . , xNtr , x1 , . . . , xNte ),τ is an aﬃnity-controlling parameter, and D is the diagonal matrix given by Dn,n ≡∑Nn′ =1 Wn,n′ .
The solution of LapRLS can be analytically computed since the optimization problem is an unconstrained quadratic program. However, covariate shift is not taken into
account in LapRLS, and thus it will not perform well if training and test distributions
are signiﬁcantly diﬀerent.

3.2

Importance-Weighted Kernel Logistic Regression

Kernel logistic regression (KLR) is a popular probabilistic classiﬁer, which learns theclass-posterior probability p(y|x) by a kernel logistic model:
)
(∑
Nte
te
exp
n=1 θy,n K(x, xn )),(∑p(y|x; θ) ≡ ∑Ntec′ ,n K(x, xte )
θ
exp
′
y
n
n=1
y =1
where θ = (θ1,1 , . . . , θc,Nte )⊤ . The importance-weighted KLR (IWKLR) method determines the parameter θ by maximizing the penalized importance-weighted log-likelihood
Ntr
Note that, in the original LapRLS, kernel basis functions are located at training input points {xtrn }n=1 .
te NteHere, we locate them at test input points {xn }n=1 for being consistent with other methods.
2

Importance-Weighted Least-Squares Probabilistic Classifier[32, 35]:
max
θ

[N
tr
∑

7

]
ν
tr tr
⊤
w(xtr
n ) log p(yn |xn ; θ) − λθ θ .

n=1

The above objective function is concave with respect to θ, and thus the unique maximizer can be obtained by standard optimization techniques such as gradient methodsand (quasi-) Newton methods. Although sophisticated optimization toolboxes are readily
available, training a large-scale IWKLR model is still computationally challenging since
it requires to optimize the all-class parameter θ of dimension c × Nte at once. On theother hand, IWLSPC optimizes the class-wise parameter θy of dimension Nte separately
c times.

4

Experiments

In this section, we experimentally compare the performance of the proposed and existing
methods.

4.1

Setup

We compare the performance of the following six classiﬁcation methods:• LapRLS+IWCV: a semi-supervised learning method described in Section 3.1. The
hyper-parameters σ, τ , λ, and η are selected by IWCV (see A).
• LapRLS+CV: a semi-supervised learning method described in Section 3.1. The
hyper-parameters σ, τ , λ, and η are selected by ordinary CV (i.e., no importanceweighting).
• IWKLR+IWCV: a probabilistic classiﬁer described in Section 3.2. The hyperparameters σ, λ, and ν are selected by IWCV. We use a MATLAB implementation of a limited-memory BFGS (Broyden-Fletcher-Goldfarb-Shanno) quasi-Newton
method included in the minFunc package [22] for optimization.
• KLR+CV: IWKLR+IWCV with all importance weights set to 1, i.e., ptr (x) = pte (x)is assumed.
• IWLSPC+IWCV: our proposed method described in Section 2.2.
parameters σ, λ, and ν are selected by IWCV.

The hyper-• LSPC+CV: IWLSPC+IWCV with all importance weights set to 1, i.e., ptr (x) =pte (x) is assumed.
Importance weights are estimated by uLSIF (see B), and the number of kernel basis
functions is ﬁxed to 200 by random sampling from Nte kernels. Training and test input

Importance-Weighted Least-Squares Probabilistic Classifier

8

Tr +1
Tr −1
Te +1
Te −1

6

4

x(2)

2

0

−2

−4
−4

−2

0

2

4

6

x(1)

Figure 1: Toy data. The optimal decision boundary is described by the solid line. ’◦’ and’×’ denote positive and negative training samples, while ’2’ and ’+’ denote positive andnegative test samples. Note that the test samples are treated as unlabeled when training
a classiﬁer, and their labels are used only for evaluating the test performance.
samples are normalized in the element-wise manner so that each element has mean zeroand unit variance. The hyper-parameters are chosen fromσ, τ ∈ {0.1m, 0.2m, 0.5m, m, 2m, 3m},λ, η ∈ {10−2 , 10−1.5 , 10−1 , 10−0.5 , 100 },ν ∈ {0, 0.2, 0.4, 0.6, 0.8, 1},
where m is the median distance among test input samples:
(
)
Nte
te
te
m ≡ median {∥xn − xn′ ∥}n,n′ =1 .
The conﬁguration of the computer used in experiments is as follows: Ubuntu 9.10,
Intel(R) Xeon(R) 2.93GHz, 2 CPUs and 24GB RAM.

4.2

Toy Classification Problem

Let us consider a binary classiﬁcation problem on the two-dimensional input space. We
deﬁne the class-posterior probabilities given input x by()
1 1
p(y = +1|x) = + tanh x(1) + min(0, x(2) ) ,2 2
p(y = −1|x) = 1 − p(y = +1|x),where x = (x(1) , x(2) )⊤ . The optimal decision boundary is the set of all x such that1p(y = +1|x) = p(y = −1|x) = .
2

Importance-Weighted Least-Squares Probabilistic Classifier

9

Table 1: Mean misclassiﬁcation rates [%] and standard deviation (in parentheses) averaged
over 50 trials for toy data with 2 dimensional input space. A number in bold face indicatesthe fact that the method is the best or comparable to the best one in terms of the mean
misclassiﬁcation rate by the t-test at the signiﬁcance level 5%.
Ntr
1000
2000

LapRLS+CV
18.6(6.4)
17.6(6.3)

LapRLS+IWCV
16.5(6.8)
15.7(7.0)

KLR+CV
17.5(3.7)
17.7(4.1)

IWKLR
+IWCV
15.2(5.4)
14.1(6.3)

LSPC+CV
16.6(3.4)
17.2(3.1)

IWLSPC+IWCV
15.2(5.5)
13.3(5.8)

Table 2: Mean computation time [s] and standard deviation (in parentheses) averaged over
50 trials for toy data with 2 dimensional input space. A number in bold face indicatesthe fact that the method is the best or comparable to the best one in terms of the mean
computation time by the t-test at the signiﬁcance level 5%.
Ntr
1000
2000

LapRLS+CV
2.5(0.6)
4.2(0.9)

LapRLS+IWCV
3.5(2.1)
4.9(3.0)

KLR+CV
3.5(1.1)
9.1(2.4)

IWKLR
+IWCV
3.0(1.1)
7.6(2.3)

LSPC+CV
0.6(0.2)
1.2(0.3)

IWLSPC+IWCV
0.5(0.3)
1.3(0.4)

Let the training and test input densities be])])( [ ] [
( [ ] [
1
1
−2 1 02 1 0+ N x;,
ptr (x) = N x;
,
,
0 2
3
3 0 2
2
2
( [ ] [])
( [ ] [
])
1
1
0
1 0
3
1 0
pte (x) = N x;,
+ N x;,,−1 0 1−1 0 12
2where N (x; µ, Σ) denotes the multivariate normal density with respect to x, with mean
µ and covariance matrix Σ.
Ntr
tr Ntr
We create training input points {xtrn }n=1 following ptr (x) and training labels {yn }n=1
te Ntefollowing p(y|xtrn ). Similarly, we create Nte = 1000 test input points {xn }n=1 followingtetepte (x) and test labels {ynte }N
n=1 following p(y|xn ). Examples of training and test samples,
and the optimal decision boundary are illustrated in Figure 1. The graph shows that the
optimal decision boundary sharply turns at the origin. This is an extrapolation problem
where training samples are distributed in the upper half of the graph and test samples are
distributed in the lower half. If the decision boundary is naively estimated from training
data, test data may not be classiﬁed correctly. This is a typical example of covariate shift.
The experiments are repeated 50 times with diﬀerent random seeds. Table 1 depicts
the experimental results for Ntr = 1000 and 2000. The table shows that the use ofimportance weights highly contributes to reducing the misclassiﬁcation rate for KLR and
LSPC. Table 2 depicts the computation time for training classiﬁers. The table shows that
the LSPC-based methods are computationally much more eﬃcient than the KLR-based
methods.

Importance-Weighted Least-Squares Probabilistic Classifier

10

Table 3: Mean misclassiﬁcation rates [%] and standard deviation (in parentheses) averaged
over 50 trials for toy data with 10 dimensional input space. A number in bold face indicatesthe fact that the method is the best or comparable to the best one in terms of the mean
misclassiﬁcation rate by the t-test at the signiﬁcance level 5%.
Ntr
1000
2000
4000
6000
8000
10000

LSPC+CV
20.3(2.3)
20.1(2.5)
20.0(1.8)
19.9(1.5)
19.5(1.5)
19.3(1.8)

IWLSPC+IWCV
20.3(3.7)
19.7(3.6)
19.4(2.8)
19.3(1.9)
18.6(2.0)
18.4(1.9)

To evaluate the performance of the importance-weighting approach in high dimensional
input spaces, we added eight dimensions to the above 2-dimensional input space—theextra dimensional data (x(3) , x(4) , . . . , x(10) )⊤ follow independently normal distribution.
Table 3 depicts the misclassiﬁcation rate for LSPC+CV and IWLSPC+IWCV in various
numbers Ntr of training samples. The table shows that IWLSPC+IWCV signiﬁcantly
outperforms LSPC+CV speciﬁcally when the number of training samples is large (Ntr ≥4000). This implies that importance-weighting can perform well even in high dimensional
data.

4.3

Human Activity Recognition using Accelerometric Data

Next, we apply the proposed method to real-world human activity recognition. We use
three-axis accelerometric data collected by iPodTouch available from http://alkan.mns.
kyutech.ac.jp/web/data.html. In the data collection procedure, subjects were asked
to perform a speciﬁc task such as walking, running, and bicycle riding. The durationof each task was arbitrary and the sampling rate was 20 Hz with small variations. An
example of three-axis accelerometric data for “walking” is plotted in Figure 2.
To extract features from the accelerometric data, each data stream was segmented
in a sliding window manner with window width 5 seconds and sliding step 1 second.
Depending on subjects, the position and orientation of iPodTouch was arbitrary—heldby hand or kept in a pocket or a bag. For this reason, we decided to take the ℓ2 -normof the 3-dimensional acceleration vector at each time step, and computed the following 5
orientation-invariant features from each window: mean, standard deviation, ﬂuctuation of
amplitude, average energy and frequency-domain entropy [1, 2].
Let us consider a situation where 2 new users (indicated by u1 and u2) want to use
the activity recognition system. However, since the new users do not want to label theiraccelerometric data, there is no labeled sample for the new users. On the other hand, alarge number of unlabeled samples for the new user and a large number of labeled datatr Ntrobtained from existing users are available. Let labeled training data {(xtrn , yn )}n=1 bethe set of labeled accelerometric data for 20 existing users. Each user has at most 100

Importance-Weighted Least-Squares Probabilistic Classifier

11

2

Acceleration [G]0−20x−axis
5

10

15

20

5

10

15

20

5

10
15
Time [s]

20

25

2
0
−2
0

y−axis
25

2
0
−2
0

z−axis25

Figure 2: An example of three-axis accelerometric data for “walking”.
Ntelabeled samples for each action. Let unlabeled test data {xten }n=1 be Nte = 800 unlabeledaccelerometric data obtained from a new user. For stabilization purposes, we average out
the importance weights over each existing user in IWCV.
The experiment is repeated 50 times with diﬀerent sample choice. Table 4 depicts
the experimental results for each new user (u1 and u2) in three binary classiﬁcation
tasks: walk vs. run, walk vs. riding a bicycle, walk vs. taking a train. The table showsthat IWLSPC+IWCV and IWKLR+IWCV compare favorably with other methods interms of the classiﬁcation accuracy. Table 6 depicts the confusion matrices of threebinary classiﬁcation tasks using IWLSPC+IWCV. The table shows that the number ofcorrected predictions for each task is rather imbalanced between two activities, e.g., there
are more corrected predictions for “walking” than for “taking a train”. Table 5 depicts thecomputation time for training classiﬁers. The table shows that the LSPC-based methods
are computationally much more eﬃcient than the KLR-based methods.
Figure 3 depicts the mean misclassiﬁcation rate for various coverage level, which is
the ratio of test sample size used for evaluating the misclassiﬁcation rate. For example,
the coverage 0.8 means that 80% of test samples with high conﬁdence level (obtainedby an estimated class-posterior probability) are used for evaluating the misclassiﬁcation
rate. The graphs show that, for most of the coverage level, IWLSPC+IWCV outperforms
LSPC+CV and the misclassiﬁcation rate of both IWLSPC+IWCV and LSPC+CV tends
to decrease as the coverage level decreases. This implies that the conﬁdence estimationby (IW)LSPC is reliable since the higher the conﬁdence is, the more accurate the learnedclassiﬁer. This fact leads to a good heuristic to further improve the performance. Thatis, the prediction with low conﬁdence level is rejected and instead the prediction withhigh conﬁdence level obtained in the previous time step is used since an action usuallycontinues for a certain amount of duration.
Table 7 depicts the mean misclassiﬁcation rate for the case that the prediction withlower conﬁdence level than a threshold, i.e., 0.8 or 0.9 is replaced with the previous one
with the highest conﬁdence level in last ﬁve steps. The table shows that the correction
based on the conﬁdence-level can further improve the performance of IWLSPC+IWCV.

Importance-Weighted Least-Squares Probabilistic Classifier

25.6

LSPC+CVIWLSPC+IWCV
Misclassifcation rate (%)

Misclassifcation rate (%)

13.3

11

8.8

LSPC+CVIWLSPC+IWCV

21.6

17.6
0.8

0.85

0.9
Coverage

0.95

1

0.8

(a) Walk vs. Run (u1)

0.85

0.9
Coverage

0.95

1(b) Walk vs. Run (u2)10.9

LSPC+CVIWLSPC+IWCV
Misclassifcation rate (%)

Misclassifcation rate (%)

9.7

8.1

6.5

LSPC+CVIWLSPC+IWCV

8.5

6.2

0.8

0.85

0.9
Coverage

0.95

1

0.8

(c) Walk vs. Bicycle (u1)
1.5

0.85

0.9
Coverage

0.95

1(d) Walk vs. Bicycle (u2)3.5

LSPC+CVIWLSPC+IWCV
Misclassifcation rate (%)

Misclassifcation rate (%)

12

0.8

0.2

LSPC+CVIWLSPC+IWCV

1.9

0.3
0.8

0.85

0.9
Coverage

0.95(e) Walk vs. Train (u1)

1

0.8

0.85

0.9
Coverage

0.95

1(f) Walk vs. Train (u2)Figure 3: Misclassiﬁcation rate as a function of coverage for each new user (u1 and u2)
in human activity recognition.

Importance-Weighted Least-Squares Probabilistic Classifier

13

Table 4: Mean misclassiﬁcation rates [%] and standard deviation (in parentheses) averaged
over 50 trials for each new user (u1 and u2) in human activity recognition. A number inbold face indicates the fact that the method is the best or comparable to the best one interms of the mean misclassiﬁcation rate by the t-test at the signiﬁcance level 5%.
Walk vs.
Run (u1)
Bicycle (u1)Train (u1)
Run (u2)Bicycle (u2)Train (u2)LapRLS+CV
21.2(4.7)
9.9(1.2)
2.2(0.23)
24.0(4.8)
8.6(1.5)
4.0(1.3)

LapRLS
KLR
IWKLR
LSPC
+IWCV
+CV
+IWCV
+CV
11.3(4.7) 15.0(6.7) 8.9(0.8) 13.2(4.0)
12.5(1.4) 9.7(0.8) 8.6(4.5) 9.9(0.9)
2.2(0.3) 1.4(0.4) 1.2(1.5) 1.5(0.4)
19.9(9.4) 24.6(1.4) 21.6(5.8) 24.5(1.0)
9.9(2.5)
6.7(1.4)
6.8(1.7) 6.3(1.3)
3.7(1.0)
3.7(0.7) 2.9(0.7) 3.5(0.6)

IWLSPC+IWCV
8.9(0.6)
8.7(4.7)
1.1(1.5)
21.0(5.6)
6.4(1.8)
3.1(0.5)

Table 5: Mean computation time [s] and standard deviation (in parentheses) averaged
over 50 trials for each new user (u1 and u2) in human activity recognition. A number inbold face indicates the fact that the method is the best or comparable to the best one interms of the mean computation time by the t-test at the signiﬁcance level 5%.
Walk vs.
Run (u1)
Bicycle (u1)Train (u1)
Run (u2)Bicycle (u2)Train (u2)5

LapRLS+CV
14.1(0.7)
38.8(4.8)
5.5(0.6)
12.6(2.1)
16.8(7.0)
5.6(0.7)

LapRLS+IWCV
14.5(0.8)
52.8(8.1)
5.4(0.6)
12.1(2.2)
27.2(5.6)
5.6(0.6)

KLR
IWKLR
LSPC
+CV
+IWCV
+CV
86.8(16.2) 78.8(23.2) 7.3(1.1)
38.8(4.8) 52.8(8.1) 4.2(0.8)
19.8(7.3) 30.9(6.0) 3.9(0.8)
70.1(12.9) 128.5(51.7) 8.2(1.3)
16.8(7.0) 27.2(5.6) 3.7(0.8)
24.9(10.8) 29.4(10.3) 4.1(0.8)

IWLSPC+IWCV
6.6(1.3)
3.7(0.8)
4.0(0.8)
7.8(1.5)
3.1(0.9)
3.9(0.8)

Conclusions

In human activity recognition, there are several practical issues to be taken into account:a new user is not willing to gather labeled data, motion patterns are signiﬁcantly diﬀerent
depending on users, and prediction with conﬁdence is useful. In this paper, we formulated the new user problem in human activity recognition as a covariate shift adaptation
problem [23], and proposed a computationally eﬃcient probabilistic classiﬁcation method.
The proposed method is an importance-weighted variant of the least-squares probabilisticclassiﬁer [26, 33], which is computationally very eﬃcient thanks to the availability of ananalytic-form solution. Experiments on real-world human activity recognition illustrated
the usefulness of the proposed method.
A potential limitation of the proposed method is that it relies on the assumptionthat the class-posterior probability does not change in between training and test phases.
That is, when this assumption does not hold, e.g., an existing user has a diﬀerent decisionboundary between “walking” and “running” from the one of new user, the learned classiﬁer

Importance-Weighted Least-Squares Probabilistic Classifier

14

Table 6: Confusion matrix for three binary-classiﬁcation tasks using IWLSPC+IWCV inhuman activity recognition. There are 80000 test samples (2 users × 50 trials × 800 test
samples) in total for each task. A number in bold face indicates correct predictions.

ActualWalk
Run

Predicted
Walk
Run
31931 8069
3907 36093

Walk Bicycle
Walk 38474 1526
ActualBicycle 4494 35506

ActualWalk
Train

Predicted
Walk Train
39973
271651 38349

Table 7: Mean misclassiﬁcation rates [%] and standard deviation (in parentheses) averaged over 50 trials for each new user (u1 and u2) using IWLSPC+IWCV with/without
correction based on conﬁdence levels in human activity recognition. A number in bold
face indicates the fact that the method is the best or comparable to the best one in termsof the mean misclassiﬁcation rate by the t-test at the signiﬁcance level 5%.
Walk vs.

Without correction

Run (u1)
Bicycle (u1)Train (u1)
Run (u2)Bicycle (u2)Train (u2)8.9(0.6)
8.7(4.7)
1.1(1.5)
21.0(5.6)
6.4(1.8)
3.1(0.5)

With correction
threshold=0.8
4.8(2.1)
8.6(4.6)
0.8(1.4)
23.3(8.2)
5.0(1.7)
0.4(0.6)

With correction
threshold=0.9
4.0(3.8)
8.6(5.8)
0.8(1.3)
21.3(6.1)
5.4(1.7)
0.5(0.7)

Importance-Weighted Least-Squares Probabilistic Classifier15

can be signiﬁcantly biased. This problem can be overcome if we can eliminate training
samples that follow a diﬀerent class-posterior from the test samples. The change of twoclass-posterior densities can be detected using the density-ratio pte (y|x)/ptr (y|x) as inchange-point detection [16] and two-sample test [31]. The ratio of class-posterior densities
can be in principle estimated similarly as the importance-weight estimation (B). Thus,
developing an eﬃcient algorithm for detecting the change of class-posterior would be
important future works.

Acknowledgements
This work was supported by AOARD and the FIRST program.

A

Model Selection by Importance-Weighted CrossValidation

The performance of IWLSPC depends on the choice of the regularization parameter λ,the Gaussian kernel width σ, and the ﬂattening parameter ν. Cross-validation (CV) isa standard method for model selection. However, under covariate shift, ordinary CV ishighly biased due to the diﬀering distributions. To cope with this problem, a variantof CV called importance-weighted CV (IWCV) has been proposed [28]. Here, we brieﬂy
describe the IWCV procedure.
tr NtrLet us randomly divide the training set into D = {(xtrn , yn )}n=1 into K disjoint nonb
empty subsets {Dk }K
k=1 of (approximately) the same size. Let fk (x) be a function learned
from D\Dk (i.e., without Dk ). Then the k-fold IWCV estimate of the generalization error
is given byK∑∑
1bIWCV = 1Gw(xtr )loss(fbk (xtr ), y tr ),K k=1 |Dk | tr tr(x ,y )∈Dk

where w(x) is the importance weight deﬁned by Eq.(1), loss(by , y) is the loss function
which measures the discrepancy between the true output value y and its estimate yb,
and |D| denotes the number of samples in the set D. It was proved that IWCV gives
an almost unbiased estimate of the generalization error even under covariate shift [28].
Finally, we select the model (λ, σ, and ν in the case of IWLSPC) that minimizes theabove generalization error estimator:b σ
bIWCV (λ, σ, ν).
(λ,b, νb) = arg min G(λ,σ,ν)Importance-Weighted Least-Squares Probabilistic ClassifierB

16

Importance-Weight Estimation by Unconstrained
Least-Squares Importance Fitting

Ntr
IWLSPC (and IWCV) requires the values of the importance {w(xtrn )}n=1 , which are unknown in practice. So far, various methods for estimating the importance has been developed [24, 7, 20, 12, 30, 13]. Among them, the method called unconstrained least-squares
importance ﬁtting (uLSIF) [13] was shown to be superior since it achieves the optimal
convergence rate [14], it possesses the optimal numerical stability [15], and its solution
can be computed analytically. Here, we brieﬂy review the uLSIF method.
Ntr
te NteSuppose we are given training and test input points {xtrn }n=1 and {xn }n=1 , which
independently follow ptr (x) and pte (x), respectively. The main idea of uLSIF is to directly estimate the importance weight w(x) = pte (x)/ptr (x) without estimating ptr (x)and pte (x). Let us model the importance w(x) by the following model:w(x; α) =Nte∑

αn L(x, xte
n ),

n=1

where α = (α1 , . . . , αNte )⊤ are parameters to be learned from data samples and L(x, x′ )is a kernel function. Here, we focus on the Gaussian kernel:()∥x − x′ ∥2′
L(x, x ) = exp −,2κ2where κ denotes the Gaussian kernel width. We determine the parameter α so that thefollowing squared error J is minimized:∫)2
1 (J(α) ≡
w(x; α) − w(x) ptr (x)dx
2
∫
∫
1
2
=
w(x; α) ptr (x)dx − w(x; α)pte (x)dx + C ′2
1= α⊤ Hα − h⊤ α + C ′ ,2where C ′ is a constant independent of the parameter α, and H is the Nte × Nte matrix
and h is the Nte -dimensional vector deﬁned as∫teHn,n′ ≡ L(x, xten )L(x, xn′ )ptr (x)dx,∫
hn ≡ L(x, xten )pte (x)dx.
Ntr
The expectations in H and h are approximated by the empirical averages using {xtrn }n=1

Importance-Weighted Least-Squares Probabilistic Classifier17

Nteand {xten }n=1 as
Ntr
∑
te
tr
te
b n,n′ ≡ 1
HL(xtrn′′ , xn )L(xn′′ , xn′ ),Ntr n′′ =1
Nte
1 ∑
te
b
hn ≡
L(xte
n′ , xn ).
Nte n′ =1

Then, we obtain the following optimization problem:
[
]
1 ⊤c
γ ⊤
⊤
b
b ≡ arg min α Hα − h α + α α ,α22αwhere γ2 α⊤ α (γ ≥ 0) is a regularization term. Then the uLSIF solution can be analyticallycomputed asbc + γINte )−1 h,b = (Hαwhere INte denotes the Nte -dimensional identity matrix. Finally, since the importanceweight is non-negative by deﬁnition, we modify the solution as
( N
)
te
∑
w(x)
b
≡ max 0,αbn L(x, xte
n) .
n=1

The performance of uLSIF depends on the choice of the regularization parameter γ
and the Gaussian kernel width κ. These tuning parameters can be determined by crossNtr
Ntetevalidation (CV) as follows. Let us randomly divide X tr = {xtr
= {xten }n=1 and Xn }n=1te K
into K disjoint non-empty subsets {Xktr }Kbk (x) be an
k=1 and {Xk }k=1 , respectively. Let wtrtrte
importance function learned from X \Xk and X \Xkte (i.e., without Xktr and Xkte ). Thenthe k-fold CV estimate of the importance estimation error J is given by

K
∑
∑
1
 1
JbCV =wbk (xtr )2
K k=1 2|Xktr | tr tr
x ∈Xk

∑
1
w
bk (xte ) ,− te
|Xk | te tex ∈Xkwhere |X | denotes the number of samples in the set X . Finally, we select the model (i.e.,
the regularization parameter γ and the Gaussian kernel width κ) that minimizes JbCV :(bγ, κb) = arg min JbCV (γ, κ).
(γ,κ)

Importance-Weighted Least-Squares Probabilistic Classifier

18

References[1] L. Bao and S. S. Intille. Activity recognition from user-annotated acceleration data.
In Proceedings of the 2nd IEEE International Conference on Pervasive Computing,pages 1–17, 2004.
[2] N. B. Bharatula, M. Stager, P. Lukowicz, and G Troster. Empirical study of design choices in multi-sensor context recognition systems. In Proceedings of the 2nd
International Forum on Applied Wearable Computing, pages 79–93, 2005.
[3] J. Blitzer, M. Dredze, and F. Pereira. Biographies, bollywood, boom-boxes andblenders: Domain adaptation for sentiment classiﬁcation. In Proceedings of the 45th
Annual Meeting of the Association of Computational Linguistics, pages 440–447,
2007.
[4] J. Blitzer, R. McDonald, and F. Pereira. Domain adaptation with structural correspodence learning. In Proceedings of the 2006 Conference on Empirical Methods in
Natural Language Processing, pages 120–128, 2006.
[5] O. Chapelle, B. Schölkopf, and A. Zien, editors. Semi-Supervised Learning. MIT
Press, Cambridge, 2006.
[6] C. Cortes, Y. Mansour, and M. Mohri. Learning bounds for importance weighting.
In J. Laﬀerty, C. K. I. Williams, R. Zemel, J. Shawe-Taylor, and A. Culotta, editors,
Advances in Neural Information Processing Systems 23, pages 442–450. 2010.
[7] J. Ćwik and J. Mielniczuk. Estimating density ratio with application to discriminant
analysis. Communications in Statistics: Theory and Methods, 18(8):3057–3069, 1989.
[8] H. Daume III. Frustratingly easy domain adaptation. In Proceedings of the 45th
International Annual Meeting of the Association of Computational Linguistics, pages
256–263, 2007.
[9] H. Daume III, A. Kumar, and A. Saha. Co-regularization based semi-supervised
domain adaptation. In Advances in Neural Information Processing Systems 23, pages
256–263, 2010.
[10] C. Gao, F. Kong, and J. Tan. Healthaware: Tackling obesity with health aware
smart phone systems. In Proceedings of the 2009 IEEE International Conference on
Robotics and Biometics, pages 1549–1554, 2009.
[11] Y. Hattori, S. Inoue, T. Masaki, G. Hirakawa, and O. Sudo. Gathering large scale
human activity information using mobile sensor devices. In Proceedings of the Second International Workshop on Network Traﬃc Control, Analysis and Applications,pages 708–713, 2010.

Importance-Weighted Least-Squares Probabilistic Classifier

19[12] 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. Hoﬀman,
editors, Advances in Neural Information Processing Systems 19, pages 601–608. MIT
Press, Cambridge, MA, USA, 2007.
[13] T. Kanamori, S. Hido, and M. Sugiyama. A least-squares approach to direct importance estimation. Journal of Machine Learning Research, 10:1391–1445, Jul 2009.
[14] T. Kanamori, T. Suzuki, and M. Sugiyama. Kernel-based least-squares density-ratio
estimation i: Statistical analysis. Machine Learning, 2011. submitted.
[15] T. Kanamori, T. Suzuki, and M. Sugiyama. Kernel-based least-squares density-ratio
estimation ii: Condition number analysis. Machine Learning, 2011. submitted.
[16] Y. Kawahara and M. Sugiyama. Sequential change-point detection based on direct
density-ratio estimation. Statistical Analysis and Data Mining, 2011. to appear.
[17] P. Leijdekkers and V. Gay. A self-test to detect a heart attack using a mobile phone
and wearable sensors. In Proceedings of the 21st IEEE International Symposium on
Computer-Based Medical Systems, pages 93–98, 2008.
[18] S. J. Pan, I. W. Tsang, J. T. Kwok, and Q. Yang. Domain adaptation via transfer
component analysis. IEEE Transactions on Neural Networks, 22(2):199–210, 2011.
[19] S. J. Pan and Q. Yang. A survey on transfer learning. IEEE Transactions on
Knowledge and Data Engineering, 22(10):1345–1359, 2010.
[20] J. Qin. Inferences for case-control and semiparametric two-sample density ratio models. Biometrika, 85(3):619–639, 1998.
[21] J. Quiñonero-Candela, M. Sugiyama, A. Schwaighofer, and N. Lawrence, editors.
Dataset Shift in Machine Learning. MIT Press, Cambridge, MA, USA, 2009.
[22] M. Schmidt. minfunc, 2005. http://www.cs.ubc.ca/˜schmidtm/Software/minFunc.
html.
[23] 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.
[24] B. W. Silverman. Density ratios, empirical likelihood and cot death. Journal of theRoyal Statistical Society, Series C, 27(1):26–33, 1978.
[25] E. P. Stuntebeck, J. S. Davis II, G. D. Abowd, and M. Blount. Healthsense: Classiﬁcation of health-related sensor data through user-assisted machine learning. In
Proceedings of the 9th Workshop on Mobile Computing Systems and Aapplications,pages 1–5, 2008.

Importance-Weighted Least-Squares Probabilistic Classifier

20[26] M. Sugiyama. Superfast-trainable multi-class probabilistic classiﬁer by least-squares
posterior ﬁtting. IEICE Transactions on Information and Systems, E93-D:2690–
2701, August 2010.
[27] M. Sugiyama and M. Kawanabe. Machine Learning in Non-Stationary Environments:
Introduction to Covariate Shift Adaptation. MIT Press, Cambridge, MA, USA, 2011.
to appear.
[28] 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.
[29] M. Sugiyama, T. Suzuki, and T. Kanamori. Density Ratio Estimation in Machine
Learning: A Versatile Tool for Statistical Data Processing. Cambridge University
Press, Cambridge, UK, 2012. to appear.
[30] M. Sugiyama, T. Suzuki, S. Nakajima, H. Kashima, P. von Bünau, and M. Kawanabe.
Direct importance estimation for covariate shift adaptation. Annals of the Instituteof Statistical Mathematics, 60(4):699–746, 2008.
[31] M. Sugiyama, M. Yamada, P. von Bünau, T. Suzuki, T. Kanamori, and M. Kawanabe. Direct density-ratio estimation with dimensionality reduction via least-squares
hetero-distributional subspace search. Neural Networks, 24(2):183–198, 2011.
[32] M. Yamada, M. Sugiyama, and T. Matsui. Semi-supervised speaker identiﬁcation
under covariate shift. Signal Processing, 90(8):2353–2361, 2010.
[33] M. Yamada, M. Sugiyama, G. Wichern, and J. Simm. Improving the accuracy ofleast-squares probabilistic classiﬁers. IEICE Transactions on Information and Systems, E94-D(6):1337–1340, 2011.
[34] K. Yamagishi, N. Ito, H. Kosuga, N. Yasuda, K. Isogami, and N. Kozuno. A simpliﬁed
measurement of farm worker’s load using an accelerometer. Journal of the JapaneseSociety of Agricultural Technology Management, 9(2):127–132, 2002.
[35] Y. Zhang, X. Hu, and Y. Fang. Logistic regression for transductive transfer learningfrom multiple sources. In Proceedings of Advanced Data Mining and Applications,pages 175–182, 2010.