Density-Difference Estimation
December 3-6, 2012
Lake Tahoe, Nevada, USA

Masashi Sugiyama (Tokyo Institute of Technology, Japan), Takafumi Kanamori (Nagoya University, Japan), Taiji Suzuki (University of Tokyo, Japan)
Marthinus Christoffel du Plessis (Tokyo Institute of Technology, Japan), Song Liu (Tokyo Institute of Technology, Japan), Ichiro Takeuchi (Nagoya Institute of Technology, Japan)

1. This Work in A NutshellTarget problem: Estimate the difference between
two densities.
Approach: Avoid density estimation and directly
estimate the difference in a single-shot process.
Theory: Parametric and non-parametric optimality
in terms of the approximation accuracy.
Usage: L2-distance approximation.
Applications: Semi-supervised class-priorestimation and unsupervised change detection.

3.1 Least-Squares Density-Difference(LSDD) Estimation
For

2.1 Target Problem & Motivations, we have(c1 , . . . , cn , cn+1 , . . . , cn+n0 ) = (x1 , . . . , xn , x01 , . . . , x0n0 ): LSDD estimatorJ(θ) =g(x)2 dx − 2g(x)f (x)dx +estimate the difference between two densities:

Consider their linear combination:f (x)2 dx

Non-parametric case: Gaussian RKHSz Compare probability distributions.
z Approximate the L2-distance.

zFor small , Taylor expansion gives

ptrain (x|y = −1)

ptrain (x|y = +1)
ptest (x)Safelyignorable

Class-balance estimation error

ZFor all, there exists a constantsuch that, for appropriately chosen,
the following inequality holds withprobability
for all:0g(x)f (x)dx ≈nn1 X
1Xg(xi ) − 0g(x0i0 )n i=1n 0i =1

Regularized training criterion:: True test class-balance

GermanAustralianz

Via density-difference estimation, we want toWhen test class-balance is unknown, fit
mixture of training class-wise input densities
Du Plessis & Sugiyama (ICML2012)
to test input density:

Optimal convergence rate is achieved.

Z

Analytically Consistently estimablecomputablefrom samples

5.1 Class-Balance Estimation
Pattern recognition when class balances aredifferent in training and test phases.
If test class-balance is known, weighted
learning eliminates estimation bias.

z: Optimal parameterZNaïve approximators via LSDD:zLeast-squares estimation:

Z

4.1 L2-Distance Approximation

Parametric case:Density-difference model:

Sample approximation:
From two sets of i.i.d. samples

3.2 Theoretical Analyses

HeartBias caused by regularization can beeliminated by.
Classification accuracy:

4.2 Numerical Examples
L2-Distance Approximation

2.2 Naïve Approach2-step method of first estimating two densities
separately and then computing their difference.
Kernel density estimation (KDE):z A smoother function is obtained.

Difference of smooth functionstends to be too smooth.
z L2-distance is under-estimated.
Cf. Anderson, Hall & Titterington (J. Multivariate Analysis 1994)

2.3 Vapnik’s Principle
Vladimir N. Vapnik (1998)
Statistical Learning Theory, Wiley.

: Regularity of Besov space that contains truebh` =n1X

n i=1

µexp −

kxi − c` k2σ22¶0−n1 Xn0 0i =1expµkx0 0 − c` k2− i 22σ¶Optimal convergence rate is achieved.

5.2 Change Detection

Solution can be computed analytically:
Cross-validation is available for objectively tuning
Gaussian width and regularization parameter .
MATLAB code is available:

Regularized kernel least-squares classifier with class-balance weighting is used.

Cf. Eberts & Steinwart (NIPS2011)

3.3 Numerical Examples

Goal: Find change points in time-series.
Use L2-distance between past and current dataKawahara& Sugiyama (SADM2012)as change score:(Difference of KDEs

LSDDTimea

L2-Distance vs. KL-Divergence

http://sugiyama-www.cs.titech.ac.jp/~sugi/software/LSDD/c

Y (t) a b
Y (t + 1) bc

Related Work: Density Ratio Estimation
Sugiyama, Suzuki & Kanamori (2012)
Density Ratio Estimation in Machine Learning
Cambridge University Press Density ratio is a versatile tool:

0LSDDz Conditional probability estimation:

fghi

fghgh

Y (t + r)
iY (t + r + 1)

d(kY (t + r − 1) e

fg

jj

Y(t)

klkl Y (t + 2r − 1)Y(t + r)

HASC Accelerometer Data

Noise

Pause

Pause

Noise
Runµ¶
p(x)
p (x)fdx
z Divergence estimation:p0 (x)ZZ
p(x, y)p(x, y) logdxdyz Mutual information estimation:p(x)p(y)ZeOutlier
Difference of KDEsz Importance sampling:cb

CENSREC Speech DataSpeechSpeech

NoiseIf you possess a restricted amount of information
for solving some problem, try to solve theproblem directly and never solve a more general
problem as an intermediate step. It is possiblethat the available information is sufficient for a
direct solution but is insufficient for solving a moregeneral intermediate problem.

br

p(x)
r(x) = 0p (x)y(t + r)y(t)Outlier mean μ

L2-distance is more robust than KL-divergence.
Cf. Basu, Harris, Hjort & Jones (Biometrika1998)

Stair-up

Stair-down