Density-Difference Estimation

Masashi Sugiyama1 Takafumi Kanamori2 Taiji Suzuki3
Marthinus Christoffel du Plessis1 Song Liu1 Ichiro Takeuchi4
1
Tokyo Institute of Technology, Japan 2 Nagoya University, Japan
3
University of Tokyo, Japan 4 Nagoya Institute of Technology, Japan

Abstract
We address the problem of estimating the difference between two probability densities. A naive approach is a two-step procedure of first estimating two densities
separately and then computing their difference. However, such a two-step procedure does not necessarily work well because the first step is performed without regard to the second step and thus a small estimation error incurred in the first stage
can cause a big error in the second stage. In this paper, we propose a single-shotprocedure for directly estimating the density difference without separately estimating two densities. We derive a non-parametric finite-sample error bound forthe proposed single-shot density-difference estimator and show that it achieves the
optimal convergence rate. We then show how the proposed density-difference estimator can be utilized in L2 -distance approximation. Finally, we experimentallydemonstrate the usefulness of the proposed method in robust distribution comparison such as class-prior estimation and change-point detection.

1 Introduction
When estimating a quantity consisting of two elements, a two-stage approach of first estimating
the two elements separately and then approximating the target quantity based on the estimates of
the two elements often performs poorly, because the first stage is carried out without regard to thesecond stage and thus a small estimation error incurred in the first stage can cause a big error in thesecond stage. To cope with this problem, it would be more appropriate to directly estimate the target
quantity in a single-shot process without separately estimating the two elements.
A seminal example that follows this general idea is pattern recognition by the support vector machine [1]: Instead of separately estimating two probability distributions of patterns for positive andnegative classes, the support vector machine directly learns the boundary between the two classes
that is sufficient for pattern recognition. More recently, a problem of estimating the ratio of two
probability densities was tackled in a similar fashion [2, 3]: The ratio of two probability densities is
directly estimated without going through separate estimation of the two probability densities.
In this paper, we further explore this line of research, and propose a method for directly estimating
the difference between two probability densities in a single-shot process. Density differences would
be more desirable than density ratios because density ratios can diverge to infinity even under amild condition (e.g., two Gaussians [4]), whereas density differences are always finite as long as
each density is bounded. Density differences can be used for solving various machine learning tasks
such as class-balance estimation under class-prior change [5] and change-point detection in timeseries [6].
For this density-difference estimation problem, we propose a single-shot method, called the leastsquares density-difference (LSDD) estimator, that directly estimates the density difference without
separately estimating two densities. LSDD is derived with in the framework of kernel regularized
least-squares estimation, and thus it inherits various useful properties: For example, the LSDD
1solution can be computed analytically in a computationally efficient and stable manner, and alltuning parameters such as the kernel width and the regularization parameter can be systematicallyand objectively optimized via cross-validation. We derive a finite-sample error bound for the LSDD
estimator and show that it achieves the optimal convergence rate in a non-parametric setup.
We then apply LSDD to L2 -distance estimation and show that it is more accurate than the difference of KDEs, which tends to severely under-estimate the L2 -distance [7]. Because the L2 -distanceis more robust against outliers than the Kullback-Leibler divergence [8], the proposed L2 -distanceestimator can lead to the paradigm of robust distribution comparison. We experimentally demonstrate the usefulness of LSDD in semi-supervised class-prior estimation and unsupervised change
detection.

2

Density-Difference Estimation

In this section, we propose a single-shot method for estimating the difference between two probability densities from samples, and analyze its theoretical properties.
Problem Formulation and Naive Approach: First, we formulate the problem of densitydifference estimation. Suppose that we are given two sets of independent and identically distributed′
samples X := {xi }ni=1 and X ′ := {x′i′ }ni′ =1 from probability distributions on Rd with densities
p(x) and p′ (x), respectively. Our goal is to estimate the density difference,f (x) := p(x) − p′ (x),from the samples X and X ′ .
A naive approach to density-difference estimation is to use kernel density estimators (KDEs). However, we argue that the KDE-based density-difference estimator is not the best approach becauseof its two-step nature. Intuitively, good density estimators tend to be smooth and thus the difference between such smooth density estimators tends to be over-smoothed as a density-difference
estimator [9]. To overcome this weakness, we give a single-shot procedure of directly estimating thedensity difference f (x) without separately estimating the densities p(x) and p′ (x).
Least-Squares Density-Difference Estimation: In our proposed approach, we fit a densitydifference model g(x) to the true density-difference function f (x) under the squared loss:∫ ()2
argming(x) − f (x) dx.
g

We use the following Gaussian kernel model as g(x):
′
)
(
n+n
∑
∥x − cℓ ∥2g(x) =
θℓ exp −
,
2σ 2

(1)

ℓ=1

where (c1 , . . . , cn , cn+1 , . . . , cn+n′ ) := (x1 , . . . , xn , x′1 , . . . , x′n′ ) are Gaussian kernel centers. If
n + n′ is large, we may use only a subset of {x1 , . . . , xn , x′1 , . . . , x′n′ } as Gaussian kernel centers.
For the model (1), the optimal parameter θ ∗ is given by
∫ (
)2
[
]
θ ∗ := argmin
g(x) − f (x) dx = argmin θ ⊤ Hθ − 2h⊤ θ = H −1 h,θθwhere H is the (n + n′ ) × (n + n′ ) matrix and h is the (n + n′ )-dimensional vector defined as
(
)
(
)
(
)
∫
∥x − cℓ ∥2∥x − cℓ′ ∥2∥cℓ − cℓ′ ∥2
2 d/2
Hℓ,ℓ′ := exp −
exp
−
dx
=
(πσ
)
exp
−
,
2σ 2
2σ 2
4σ 2
(
)
(
)
∫
∫
∥x − cℓ ∥2∥x′ − cℓ ∥2
hℓ := exp −p(x)dx−exp−
p′ (x′ )dx′ .
2σ 2
2σ 2
Replacing the expectations in h by empirical estimators and adding an ℓ2 -regularizer to the objectivefunction, we arrive at the following optimization problem:[]
b := argmin θ ⊤ Hθ − 2hb ⊤ θ + λθ ⊤ θ ,
θ
(2)
θ

2

b is the (n + n′ )-dimensional vector defined aswhere λ (≥ 0) is the regularization parameter and h
(
)
(
)
n
n
1∑
∥xi − cℓ ∥2
1 ∑∥x′i′ − cℓ ∥2
b
hℓ :=
exp −
− ′
exp −
.
n i=1
2σ 2
n ′
2σ 2
′

i =1

Taking the derivative of the objective function in Eq.(2) and equating it to zero, we can obtain thesolution analytically asbb = (H + λI)−1 h,θwhere I denotes the identity matrix.
Finally, a density-difference estimator fb(x), which we call the least-squares density-difference(LSDD) estimator, is given as
fb(x) =

′
n+n
∑

ℓ=1

(
)
∥x − cℓ ∥2
θbℓ exp −.
2σ 2

Non-Parametric Error Bound: Here, we theoretically analyze an estimation error of LSDD.
We assume n′ = n, and let Hγ be the reproducing kernel
Hilbert space() (RKHS) corresponding to
the Gaussian kernel with width γ: kγ (x, x′ ) = exp −∥x − x′ ∥2 /γ 2 . Let us consider a slightly
modified LSDD estimator that is more suitable for non-parametric error analysis1 :
)
]
[
( n
n
∑
∑
1
1
2
′
2
fb := argmin ∥g∥L2 (Rd ) − 2
g(xi ) −g(xi′ ) + λ∥g∥Hγ .
n i=1
n ′
g∈Hγ
i =1

Then we have the following theorem:
Theorem 1. Suppose that there exists a constant M such that ∥p∥∞ ≤ M and ∥p′ ∥∞ ≤ M .
Suppose also that the density difference f = p − p′ is a member of Besov space with regularity α.
ααis the Besov space with regularity α, andwhere B2,∞
That is, f ∈ B2,∞α∥f ∥B2,∞:= ∥f ∥L2 (Rd ) + sup(t−α ωr,L2 (Rd ) (f, t)) < c for r = ⌊α⌋ + 1,

t>0

where ⌊α⌋ denotes the largest integer less than or equal to α and ωr,L2 (Rd ) is the r-th modulus ofsmoothness (see [10] for the definitions). Then, for all ϵ > 0 and p ∈ (0, 1), there exists a constant
K > 0 depending on M , c, ϵ, and p such that for all n ≥ 1, τ ≥ 1, and λ > 0, the LSDD estimator
fb in Hγ satisfies()
2(1−p)d1−pγ −(1−p)(1+ϵ)d γ − 1+p (1+ϵ+ 4 )
τ
τ
−d
2α
2
2
b
b
∥f − f ∥L2 (Rd ) +λ∥f ∥Hγ ≤ K λγ +γ +
+
+ 2 +
3p−p2
2
λp n
n λ n
λ 1+p n 1+pwith probability not less than 1 − 4e−τ .
If we set λ = n− (2α+d)(1+p)+(ϵ−p+ϵp) and γ = n− (2α+d)(1+p)+(ϵ−p+ϵp) , and take ϵ and p sufficiently
small, then we immediately have the following corollary.
2α+d1Corollary 1. Suppose that the same assumptions as Theorem 1 hold. Then, for all ρ, ρ′ > 0, there
exists a constant K > 0 depending on M, c, ρ, and ρ′ such that, for all n ≥ 1 and τ ≥ 1, thedensity-difference estimator fb with appropriate choice of γ and λ satisfies)(′
2α∥fb − f ∥2L2 (Rd ) + λ∥fb∥2Hγ ≤ K n− 2α+d +ρ + τ n−1+ρ
with probability not less than 1 − 4e−τ .
1More specifically, the regularizer is replaced from the squared ℓ2 -norm of parameters to the squared RKHSnorm of a learned function, which is necessary to establish consistency. Nevertheless, we use the squaredℓ2 -norm of parameters in experiments because it is simpler and seems to perform well in practice.

3αNote that n− 2α+d is the optimal learning rate to estimate a function in B2,∞
. Therefore, the densitydifference estimator with a Gaussian kernel achieves the optimal learning rate by appropriately
choosing the regularization parameter and the Gaussian width. Because the learning rate depends
on α, the LSDD estimator has adaptivity to the smoothness of the true function.
2α

It is known that, if the naive KDE with a Gaussian kernel is used for estimating a probability densitywith regularity α > 2, the optimal learning rate cannot be achieved [11, 12]. To achieve the optimalrate by KDE, we should choose a kernel function specifically tailored to each regularity α [13].
However, such a kernel function is not non-negative and it is difficult to implement it in practice.
On the other hand, our LSDD estimator can always achieve the optimal learning rate for a Gaussian
kernel without regard to regularity α.
Model Selection by Cross-Validation: The above theoretical analysis showed the superiority of
LSDD. However, in practice, the performance of LSDD depends on the choice of models (i.e.,
the kernel width σ and the regularization parameter λ). Here, we show that the model can be
optimized by cross-validation (CV). More specifically, we first divide the samples X = {xi }ni=1′
and X ′ = {x′i′ }ni′ =1 into T disjoint subsets {Xt }Tt=1 and {Xt′ }Tt=1 , respectively. Then we obtain adensity-difference estimate fbt (x) from X \Xt and X ′ \Xt′ (i.e., all samples without Xt and Xt′ ), andcompute its hold-out error for Xt and Xt′ as∫
2 ∑ b ′2 ∑b(t)
ft (x) + ′ft (x ),
CV := fbt (x)2 dx −|Xt ||Xt | ′ ′
x∈Xt

x ∈Xt

where |X | denotes the number of elements in the set X . We repeat this hold-out validation procedure for t = 1, . . . , T , and compute the average hold-out error. Finally, we choose the model thatminimizes the average hold-out error.

3 L2 -Distance Estimation by LSDD
In this section, we consider the problem of approximating the L2 -distance between p(x) and p′ (x),∫2
L2 (p, p′ ) := (p(x) − p′ (x)) dx,′

from their independent and identically distributed samples X := {xi }ni=1 and X ′ := {x′i′ }ni′ =1 .
∫∫For an equivalent expression L2 (p, p′ ) = f (x)p(x)dx − f (x′ )p′ (x′ )dx′ , if we replace f (x)with an LSDD estimator fb(x) and approximate the expectations by empirical averages, we obtain∫b ⊤ θ.
b Similarly, for another expression L2 (p, p′ ) = f (x)2 dx, replacing f (x) withL2 (p, p′ ) ≈ hb⊤ H θ.
ban LSDD estimator fb(x) gives L2 (p, p′ ) ≈ θ
⊤

⊤

b θ
b and θb Hθb themselves give approximations to L2 (p, p′ ), we argue that the use of
Although htheir combination, defined byb⊤θb−θb⊤ H θ,bb 2 (X , X ′ ) := 2hL(3)

is more sensible. To explain the reason, let us consider a generalized L2 -distance estimator of theb⊤θb + (1 − β)θ
b⊤ H θ,b where β is a real scalar. If the regularization parameter λ (≥ 0) is
form β hsmall, this can be expressed asb⊤θb + (1 − β)θ
b⊤ H θb=hb ⊤ H −1 hb − λ(2 − β)hb ⊤ H −2 hb + op (λ),βh(4)

where op denotes the probabilistic order. Thus, up to Op (λ), the bias introduced by regularization(i.e., the second term in the right-hand side of Eq.(4) that depends on λ) can be eliminated if β = 2,b⊤θb and θb⊤ H θ
bwhich yields Eq.(3). Note that, if no regularization is imposed (i.e., λ = 0), both h⊤b H −1 h,b the first term in the right-hand side of Eq.(4).
yield h4

Eq.(3) is actually equivalent to the negative of the optimal objective value of the LSDD optimization
problem without regularization (i.e., Eq.(2) with λ = 0). This can be naturally interpreted through alower bound of L2 (p, p′ ) obtained by Legendre-Fenchel convex duality [14]:
[ (∫
) ∫
]
∫
2
′
′ ′
′
′
2
L (p, p ) = sup 2g(x)p(x)dx − g(x )p (x )dx − g(x) dx ,gwhere the supremum is attained at g = f . If the expectations are replaced by empirical estimators and the Gaussian kernel model (1) is used as g, the above optimization problem is reduced
to the LSDD objective function without regularization (see Eq.(2)). Thus, LSDD corresponds toapproximately maximizing the above lower bound and Eq.(3) is its maximum value.
⊤

⊤

⊤

⊤

b θ
b−θ
b Hθ
b ≥ θ
b H θ.
b ≥ hb θbThrough eigenvalue decomposition of H, we can show that 2h
⊤
⊤
b
b
b
b
Thus, our approximator (3) is not less than the plain approximators h θ and θ H θ.

4

Experiments

R
In this section, we experimentally demonstrate the usefulness of LSDD. A MATLAB⃝
implementation of LSDD used for experiments is available from“http://sugiyama-www.cs.titech.ac.jp/˜sugi/software/LSDD/”.
Illustration: Let N (x; µ, Σ) be the multi-dimensional normal density with mean vector µ andvariance-covariance matrix Σ with respect to x, and let
p(x) = N (x; (µ, 0, . . . , 0)⊤ , (4π)−1 I d )andp′ (x) = N (x; (0, 0, . . . , 0)⊤ , (4π)−1 I d ).

We first illustrate how LSDD behaves under d = 1 and n = n′ = 200. We compare LSDD with
KDEi (KDE with two Gaussian widths chosen independently by least-squares cross-validation [15])and KDEj (KDE with two Gaussian widths chosen jointly to minimize the LSDD criterion [9]). The
number of folds in cross-validation is set to 5 for all methods.
Figure 1 depicts density-difference estimation results obtained by LSDD, KDEi, and KDEj for µ = 0(i.e., f (x) = p(x) − p′ (x) = 0). The figure shows that LSDD and KDEj give accurate estimatesof the density difference f (x) = 0. On the other hand, the estimate obtained by KDEi is rather
fluctuated, although both densities are reasonably well approximated by KDEs. This illustrates anadvantage of directly estimating the density difference without going through separate estimation ofeach density. Figure 2 depicts the results for µ = 0.5 (i.e., f (x) ̸= 0), showing again that LSDD
performs well. KDEi and KDEj give the same estimation result for this dataset, which slightly
underestimates the peaks.
Next, we compare the performance of L2 -distance approximation based on LSDD, KDEi, and KDEj.
For µ = 0, 0.2, 0.4, 0.6, 0.8 and d = 1, 5, we draw n = n′ = 200 samples from the above p(x)and p′ (x). Figure 3 depicts the mean and standard error of estimated L2 -distances over 1000 runs
as functions of mean µ. When d = 1 (Figure 3(a)), the LSDD-based L2 -distance estimator gives
the most accurate estimates of the true L2 -distance, whereas the KDEi-based L2 -distance estimatorslightly underestimates the true L2 -distance when µ is large. This is caused by the fact that KDE
tends to provide smooth density estimates (see Figure 2(b) again): Such smooth density estimates
are accurate as density estimates, but the difference of smooth density estimates yields a small L2 distance estimate [7]. The KDEj-based L2 -distance estimator tends to improve this drawback of
KDEi, but it still slightly underestimates the true L2 -distance when µ is large.
When d = 5 (Figure 3(b)), the KDE-based L2 -distance estimators even severely underestimate
the true L2 -distance when µ is large. On the other hand, the LSDD-based L2 -distance estimator
still gives reasonably accurate estimates of the true L2 -distance even when d = 5. However, wenote that LSDD also slightly underestimates the true L2 -distance when µ is large, because slightunderestimation tends to yield smaller variance and thus such stabilized solutions are more accurate
in terms of the bias-variance trade-off.
Semi-Supervised Class-Balance Estimation: In real-world pattern recognition tasks, changes inclass balance between the training and test phases are often observed. In such cases, naive classifier
5

1.6

1.6

1.6

f(x)
f(x)

1.4

^

p(x)−p’(x)^p(x)−p’(x)
p(x)
^
p(x)
p’(x)
^
p’(x)

1.4

1.2

1.2

1.2

1

1

0.8

0.8

0.6

0.6

0.6

0.4

0.4

0.4

0.2

0.2

0.2

0

0

0

−0.2

−0.2

−0.2

−0.4 b

−1

−0.5

0
x

0.5

−0.4 b

1

−1

−0.5

(a) LSDD

0
x

0.5

f(x)
f(x)

^

1.4

^

1
0.8

−0.4 b

1

−1

−0.5

(b) KDEi

0
x

0.5

1

(c) KDEj

Figure 1: Estimation of density difference when µ = 0 (i.e., f (x) = p(x) − p′ (x) = 0).
1.5

b

1.5

1.5
f(x)
f(x)

f(x)
f(x)

^

^

1

1

1

0.5

0.5

0.5

0

0

−0.5

−0.5

−1

−1

−1.5 b

−1

−0.5

0

0.5

1

1.5

−1.5 b0p(x)−p’(x)^p(x)−p’(x)
p(x)
^
p(x)
p’(x)
^
p’(x)

−0.5

^

−1

−0.5

−1

0

0.5

x

1

1.5

−1.5 b

−1

−0.5

0

(a) LSDD

0.5

1

1.5

x

x

(b) KDEi(c) KDEj

Figure 2: Estimation of density difference when µ = 0.5 (i.e., f (x) = p(x) − p′ (x) ̸= 0).
True
LSDD
KDE i
KDE j

1.6
1.4

1.4
1.2
L2 distanceL2 distance

1.2
1
0.8

1
0.8

0.6

0.6

0.4

0.4
0.2

0.2
0b

True
LSDD
KDE i
KDE j

1.6

0

0.1

0.2

0.3

0.4
µ

0.5

0.6

0.7

0b

0.8

(a) d = 1

0

0.1

0.2

0.3

0.4
µ

0.5

0.6

0.7

0.8

(b) d = 5

Figure 3: L2 -distance estimation by LSDD, KDEi, and KDEj for n = n′ = 200 as functions of theGaussian mean µ. Means and standard errors over 1000 runs are plotted.
training produces significant estimation bias because the class balance in the training dataset does
not properly reflect that of the test dataset.
Here, we consider a binary pattern recognition task of classifying pattern x ∈ Rd to class y ∈{+1, −1}. Our goal is to learn the class balance of a test dataset in a semi-supervised learning setup
where unlabeled test samples are provided in addition to labeled training samples [16]. The classbalance in the test set can be estimated by matching a mixture of class-wise training input densities,
qtest (x; π) := πptrain (x|y = +1) + (1 − π)ptrain (x|y = −1),to the test input density ptest (x) [5], where π ∈ [0, 1] is a mixing coefficient to learn. See Figure 4
for schematic illustration. Here, we use the L2 -distance estimated by LSDD and the difference ofKDEs for this distribution matching. Note that, when LSDD is used to estimate the L2 -distance,
separate estimation of ptrain (x|y = ±1) is not involved, but the difference between ptest (x) andqtest (x; π) is directly estimated.
We use four UCI benchmark datasets (http://archive.ics.uci.edu/ml/), where we randomly choose 10 labeled training samples from each class and 50 unlabeled test samples following
true class-prior π ∗ = 0.1, 0.2, . . . , 0.9. Figure 6 plots the mean and standard error of the squared
difference between true and estimated class-balances π and the misclassification error by a weightedℓ2 -regularized least-squares classifier [17] with weighted cross-validation [18] over 1000 runs. The
results show that LSDD tends to provide better class-balance estimates than the KDEi-based, theKDEj-based, and the EM-based methods [5], which are translated into lower classification errors.
6Unsupervised Change Detection: The objective of change detection is to discover abrupt property changes behind time-series data. Let y(t) ∈ Rm be an m-dimensional time-series sample attime t, and let Y (t) := [y(t)⊤ , y(t + 1)⊤ , . . . , y(t + k − 1)⊤ ]⊤ ∈ Rkm be a subsequence of timeseries at time t with length k. We treat the subsequence Y (t) as a sample, instead of a single pointy(t), by which time-dependent information can be incorporated naturally [6]. Let Y(t) be a set of r
retrospective subsequence samples starting at time t: Y(t) := {Y (t), Y (t + 1), . . . , Y (t + r − 1)}.
Our strategy is to compute a certain dissimilarity measure between two consecutive segments Y(t)and Y(t+r), and use it as the plausibility of change points (see Figure 5). As a dissimilarity measure,
we use the L2 -distance estimated by LSDD and the Kullback-Leibler (KL) divergence estimated by
the KL importance estimation procedure (KLIEP) [2, 3]. We set k = 10 and r = 50.
First, we use the IPSJ SIG-SLP Corpora and Environments for Noisy Speech Recognition (CENSREC) dataset (http://research.nii.ac.jp/src/en/CENSREC-1-C.html). Thisdataset is provided by the National Institute of Informatics, Japan that records human voice in anoisy environment such as a restaurant. The top graphs in Figure 7(a) display the original timeseries (true change points were manually annotated) and change scores obtained by KLIEP and
LSDD. The graphs show that the LSDD-based change score indicates the existence of change points
more clearly than the KLIEP-based change score.
Next, we use a dataset taken from the Human Activity Sensing Consortium (HASC) challenge
2011 (http://hasc.jp/hc2011/), which provides human activity information collected byportable three-axis accelerometers. Because the orientation of the accelerometers is not necessarily
fixed, we take the ℓ2 -norm of the 3-dimensional data. The HASC dataset is relatively simple, so
we artificially added zero-mean Gaussian noise with standard deviation 5 at each time point withprobability 0.005. The top graphs in Figure 7(b) display the original time-series for a sequence ofactions “jog”, “stay”, “stair down”, “stay”, and “stair up” (there exists 4 change points at time 540,
1110, 1728, and 2286) and the change scores obtained by KLIEP and LSDD. The graphs show that
the LSDD score is much more stable and interpretable than the KLIEP score.
Finally, we compare the change-detection performance more systematically using the receiver operating characteristic (ROC) curves (i.e., the false positive rate vs. the true positive rate) and thearea under the ROC curve (AUC) values. In addition to LSDD and KLIEP, we test the L2 -distanceestimated by KDEi and KDEj and native change detection methods based on autoregressive models(AR) [19], subspace identification (SI) [20], singular spectrum transformation (SST) [21], one-class
support vector machine (SVM) [22], kernel Fisher discriminant analysis (KFD) [23], and kernelchange-point detection (KCP) [24]. Tuning parameters included in these methods were manually optimized. For 10 datasets taken from each of the CENSREC and HASC data collections, mean ROC
curves and AUC values are displayed at the bottom of Figure 7(b). The results show that LSDD tends
to outperform other methods and is comparable to state-of-the-art native change-detection methods.

5Conclusions

In this paper, we proposed a method for directly estimating the difference between two probability
density functions without density estimation. The proposed method, called the least-squares densitydifference (LSDD), was derived within the framework of kernel least-squares estimation, and its
solution can be computed analytically in a computationally efficient and stable manner. Furthermore,
LSDD is equipped with cross-validation, and thus all tuning parameters such as the kernel width andthe regularization parameter can be systematically and objectively optimized. We derived a finitesample error bound for LSDD in a non-parametric setup, and showed that it achieves the optimal
convergence rate. We also proposed an L2 -distance estimator based on LSDD, which nicely cancels
a bias caused by regularization. Through experiments on class-prior estimation and change-point
detection, the usefulness of the proposed LSDD was demonstrated.
Acknowledgments: We would like to thank Wittawat Jitkrittum for his comments and Zaı̈d Harchaoui for providing us a program code of kernel change-point detection. MS was supported by
MEXT KAKENHI 23300069 and AOARD, TK was supported by MEXT KAKENHI 24500340,
TS was supported by MEXT KAKENHI 22700289, the Aihara Project, the FIRST program from
JSPS initiated by CSTP, and the Global COE Program “The research and training center for new
development in mathematics”, MEXT, Japan, MCdP was supported by MEXT Scholarship, SL wassupported by the JST PRESTO program, and IT was supported by MEXT KAKENHI 23700165.
7

Y (t + 2ry(t + r)Yy(t)ptrain(x|y = +1)

Time
a

b

Y (t) a b
Y (t + 1) b|
ptest (x)

b

f

e

c
c

f
d

KDEj
EM

0.15
0.1
0.05
0

0.2

0.4 π* 0.6

0.8

j

g

h

g

h

−
Y (t + r)i
Y (t + r + 1)

j

0.1

0.05
0.4 π* 0.6

0.8

0.3
0.25
0.2

0.2
0.1

0.2

0.4 π* 0.6

0.4
0.35
0.3
0.25
0.2

0.8

(a) Australian dataset(k +l Y) (t + 2r − 1)Y(t + r)

0.15
0.1
0.05
0

0.2

0.4 π* 0.6

0.8

0.2
0.15
0.1
0.05

0.2

0.4 π* 0.6

Misclassification rate

0.3

l

0

0.2

0.4 π* 0.6

0.8

0.2

0.4 π* 0.6

0.8

0.5
Misclassification rate

0.4

k

0.25

0.45
Misclassification rate

Misclassification rate

0.5

0.15

0.2

i

Figure 5: Change-point detection.
Class balance squared error

Class balance squared error

Class balance squared error

LSDD
KDEi

0.2

h

Y(t)

x

Figure 4: Class-balance estimation.
0.25

g

Y(
r
k
f
g
Y (t + r − 1) e Y

r

train

c

Class balance squared error|
ptrain(x|y = −1)

0.5
0.4
0.3
0.2

0.8

(b) Diabetes dataset

0.2

0.4 π* 0.6

0.4
0.3
0.2
0.1

0.8

(c) German dataset(d) Statlogheart dataset

Figure 6: Results of semi-supervised class-balance estimation. Top: Squared error of class balance
estimation. Bottom: Misclassification error by a weighted ℓ2 -regularized least-squares classifier.
0.1

5

Original data

0

Original
data

0

−0.1
−5

−0.2

0

500

1000

0

1500

KLIEP score

40

1000

1500

2000

2500

3000

2000

2500

3000

2000

2500

3000

KLIEP score

20

20
0

500

40

0

500

1000

0

1500

LSDD score

0

500

1000

1500
LSDD score

2

1
1

0

0

500

1000

0

1500

0

500

1000

1

1

0.9

0.9

0.8

0.8

0.7
0.6

LSDD
KDEi
KDEj
KLIEP
AR
SI
SST
SVM
KFD
KCP

0.5
0.4
0.3
0.2
0.1
0

True positive rate

True positive rate

Time

0

0.2

0.4
0.6
False positive rate

0.8

1500
Time

0.7
0.6

LSDD
KDEi
KDEj
KLIEP
AR
SI
SST
SVM
KFD
KCP

0.5
0.4
0.3
0.2
0.1
0

1

0

0.2

0.4
0.6
False positive rate

0.8

1

AUC LSDD KDEi KDEj KLIEP AR SI SST SVM KFD KCP AUC LSDD KDEi KDEj KLIEP AR SI SST SVM KFD KCP
Mean .879 .755 .705 .635 .749 .756 .580 .773 .905 .913 Mean .843 .764 .751 .638 .799 .762 .764 .815 .856 .730
.013 .029 .036 .020 .026 .020 .016 .018 .023 .032
SESE.014 .016 .023 .030 .013 .012 .023 .032 .013 .024(b) Accelerometer data(a) Speech data

Figure 7: Results of unsupervised change detection. From top to bottom: Original time-series,change scores obtained by KLIEP and LSDD, mean ROC curves over 10 datasets, and AUC values
for 10 datasets. The best method and comparable ones in terms of mean AUC values by the t-test at
the significance level 5% are indicated with boldface. “SE” stands for “Standard error”.
8References[1] V. N. Vapnik. Statistical Learning Theory. Wiley, New York, NY, USA, 1998.
[2] 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 Institute of Statistical
Mathematics, 60(4):699–746, 2008.
[3] X. Nguyen, M. J. Wainwright, and M. I. Jordan. Estimating divergence functionals and thelikelihood ratio by convex risk minimization. IEEE Transactions on Information Theory,56(11):5847–5861, 2010.
[4] C. Cortes, Y. Mansour, and M. Mohri. Learning bounds for importance weighting. In Advancesin Neural Information Processing Systems 23, pages 442–450, 2010.
[5] M. Saerens, P. Latinne, and C. Decaestecker. Adjusting the outputs of a classifier to new apriori probabilities: A simple procedure. Neural Computation, 14(1):21–41, 2002.
[6] Y. Kawahara and M. Sugiyama. Sequential change-point detection based on direct densityratio estimation. Statistical Analysis and Data Mining, 5(2):114–127, 2012.
[7] N. Anderson, P. Hall, and D. Titterington. Two-sample test statistics for measuring discrepancies between two multivariate probability density functions using kernel-based density estimates. Journal of Multivariate Analysis, 50(1):41–54, 1994.
[8] A. Basu, I. R. Harris, N. L. Hjort, and M. C. Jones. Robust and efficient estimation by minimising a density power divergence. Biometrika, 85(3):549–559, 1998.
[9] P. Hall and M. P. Wand. On nonparametric discrimination using density differences.
Biometrika, 75(3):541–547, 1988.
[10] M. Eberts and I. Steinwart. Optimal learning rates for least squares SVMs using Gaussian
kernels. In Advances in Neural Information Processing Systems 24, pages 1539–1547, 2011.
[11] R. H. Farrell. On the best obtainable asymptotic rates of convergence in estimation of a density
function at a point. The Annals of Mathematical Statistics, 43(1):170–180, 1972.
[12] B. W. Silverman. Density Estimation for Statistics and Data Analysis. Chapman and Hall,
London, UK, 1986.
[13] E. Parzen. On the estimation of a probability density function and mode. The Annals of
Mathematical Statistics, 33(3):1065–1076, 1962.
[14] R. T. Rockafellar. Convex Analysis. Princeton University Press, Princeton, NJ, USA, 1970.
[15] W. Härdle, M. Müller, S. Sperlich, and A. Werwatz. Nonparametric and Semiparametric
Models. Springer, Berlin, Germany, 2004.
[16] O. Chapelle, B. Schölkopf, and A. Zien, editors. Semi-Supervised Learning. MIT Press,
Cambridge, MA, USA, 2006.
[17] R. Rifkin, G. Yeo, and T. Poggio. Regularized least-squares classification. In Advances inLearning Theory: Methods, Models and Applications, pages 131–154. IOS Press, Amsterdam,
the Netherlands, 2003.
[18] M. Sugiyama, M. Krauledat, and K.-R. Müller. Covariate shift adaptation by importanceweighted cross validation. Journal of Machine Learning Research, 8:985–1005, May 2007.
[19] Y. Takeuchi and K. Yamanishi. A unifying framework for detecting outliers and change points
from non-stationary time series data. IEEE Transactions on Knowledge and Data Engineering,18(4):482–489, 2006.
[20] Y. Kawahara, T. Yairi, and K. Machida. Change-point detection in time-series data based onsubspace identification. In Proceedings of the 7th IEEE International Conference on Data
Mining, pages 559–564, 2007.
[21] V. Moskvina and A. A. Zhigljavsky. An algorithm based on singular spectrum analysis forchange-point detection. Communication in Statistics: Simulation & Computation, 32(2):319–
352, 2003.
[22] F. Desobry, M. Davy, and C. Doncarli. An online kernel change detection algorithm. IEEE
Transactions on Signal Processing, 53(8):2961–2974, 2005.
[23] Z. Harchaoui, F. Bach, and E. Moulines. Kernel change-point analysis. In Advances in Neural
Information Processing Systems 21, pages 609–616, 2009.
[24] S. Arlot, A. Celisse, and Z. Harchaoui. Kernel change-point detection. Technical Report1202.3878, arXiv, 2012.

9