Introduction
Models of ID
Extreme Value Theory
ID Estimation

Estimating Local Intrinsic Dimensionality

S. Girard3

L. Amsaleg1 O. Chelly2 T. Furon1
M. E. Houle2 K. Kawarabayashi2

M. Nett24

1 Equipe TEXMEX, INRIA/IRISA Rennes, France
2 National Institute of Informatics, Chiyoda-ku, Tokyo, Japan
3 Equipe MISTIS, INRIA Grenoble Rhône-Alpes, France
4 Google Japan, Minato-ku, Tokyo, Japan

August 3, 2015

1/28
Estimating Local Intrinsic Dimensionality

Introduction
Models of ID
Extreme Value Theory
ID Estimation

Table of contents
1Introduction

2

Models of IDGlobal vs. local models of ID
Local models of ID

3

Extreme Value Theory
Threshold model
ID in the threshold model4

ID Estimation
Our estimators
Experimental results and interpretation
2/28
Estimating Local Intrinsic Dimensionality

Introduction
Models of ID
Extreme Value Theory
ID Estimation

What is intrinsic dimensionality?

Definition: Intrinsic Dimensionality
Intrinsic dimensionality can be described as the minimum numberof coordinates required to locate a point in the space.
3/28
Estimating Local Intrinsic Dimensionality

Introduction
Models of ID
Extreme Value Theory
ID Estimation

Current applications of ID
Analysis of search indices (Expansion Dimension)
Navigating Nets [Krauthgamer & Lee (2005)]
Cover Tree [Beygelzimer, Kakade, Langford (2006)]
Rank Cover Tree [Houle & Nett (2013)]
Analysis of projection, Outlier detection (Expansion Dimension)
LOF-based PINN outlier detection [de Vries, Chawla, Houle(2010)]
Projection and dimensional reduction
Principal component analysis [Pearson (1901)]
4/28
Estimating Local Intrinsic Dimensionality

Introduction
Models of ID
Extreme Value Theory
ID Estimation

Potential applications of ID
Predictionestimate the target dimension for dimensionality reduction.
predict the difficulty of data sets/subsets/points.
Processing
redesign machine learning algorithms by adapting them to thelocal variation of ID (queries in points with low ID are moretrustworthy).
Evaluation
explain the behavior of algorithms and evaluate them more
fairly by accounting for the disparity in ID.
5/28
Estimating Local Intrinsic Dimensionality

Introduction
Models of ID
Extreme Value Theory
ID Estimation

Global vs. local models of ID
Local models of ID

Global models of ID vs. Local models of ID6/28
Estimating Local Intrinsic Dimensionality

Introduction
Models of ID
Extreme Value Theory
ID Estimation

Global vs. local models of ID
Local models of ID

Global models of ID vs. Local models of ID
Properties of global and local models
measureGlobal models
the dimensinality of thewhole dataset.

requirea set of data points.

examplesTopologicalmodels(PCA), fractal models(Hausdorff Dimension,Correlation Dimension),
Graph-based models,etc.

Local models
the dimensionality inthe neighborhood of apoint.
a set of distances to thenearest neighbors.
Expansion models (ED,
LID).

7/28
Estimating Local Intrinsic Dimensionality

Introduction
Models of ID
Extreme Value Theory
ID Estimation

Global vs. local models of ID
Local models of ID

Expansion models
B2x2
B1x1

Expansion-based methods estimate the intrinsic dimension bycomparing the expansion in distance and the associated expansion
in volume (number of points).
Examples: Expansion Dimension (ED), Minimum Neighborhood
Distance (MiND), Local Intrinsic Dimension (LID).
8/28
Estimating Local Intrinsic Dimensionality

Introduction
Models of ID
Extreme Value Theory
ID Estimation

Global vs. local models of ID
Local models of ID

How to measure the dimension?
Dimensional query
In an Lp -norm space of dimension m, if
V is a measure of volume then :!m
V (B2 )x2
=V (B1 )
x1

B2x2
B1x1

The representational dimension m canbe obtained by :m=ln V (B2 ) − ln V (B1 )ln x2 − ln x1
9/28
Estimating Local Intrinsic Dimensionality

Introduction
Models of ID
Extreme Value Theory
ID Estimation

Global vs. local models of ID
Local models of ID

Expansion Dimension

Expansion dimension
If volume is measured in terms ofnumber of points that are captured,thenED(q, x1 , x2 ) =

B2x2
B1x1

ln k2 − ln k1
ln x2 − ln x1

10/28
Estimating Local Intrinsic Dimensionality

Introduction
Models of ID
Extreme Value Theory
ID Estimation

Global vs. local models of ID
Local models of ID

Distance as a continuous random variable
Main assumption
Data can be seen as a sample generated from a set of continuous
random variables.
Continuous random distance variable
Let X be an absolutely continuous random distance variable thatrepresents the distance from a reference point q withprobability density function fX
cumulative distribution function FX =RfX (t)dt(xi )1≤i<n an ordered sample of X

11/28
Estimating Local Intrinsic Dimensionality

Introduction
Models of ID
Extreme Value Theory
ID Estimation

Global vs. local models of ID
Local models of ID

Intrinsic dimensional query
Definition
When FX (x) > 0, the continuous ID ofX at distance x is defined as
IntrDimFX (x) =lim+ε→0ln FX ((1 + ε)x) − ln FX (x)ln(1 + ε)ε·x!

xRemarks
The volume is measured in termsof expected number of points.
X depends on reference point q.
12/28
Estimating Local Intrinsic Dimensionality

Introduction
Models of ID
Extreme Value Theory
ID Estimation

Global vs. local models of ID
Local models of ID

Intrinsic dimensional query

ε·x

By applying l’Hôpital’s rule:
IDFX (x) =x

x · fX (x)FX (x)

13/28
Estimating Local Intrinsic Dimensionality

Introduction
Models of ID
Extreme Value Theory
ID Estimation

Threshold model
ID in the threshold model

Disaster prevention

14/28
Estimating Local Intrinsic Dimensionality

Introduction
Models of ID
Extreme Value Theory
ID Estimation

Threshold model
ID in the threshold model

Introduction to EVT

Analogy between central and extreme values
Central values → Central limit theorem → Normal distribution
Extreme values → Pickands-Balkema-de Haan theorem →Generalized Pareto Distribution

15/28
Estimating Local Intrinsic Dimensionality

Introduction
Models of ID
Extreme Value Theory
ID Estimation

Threshold model
ID in the threshold model

Generalized Pareto Distribution
Cases of the Generalized ParetoDistribution
ξ = 0 → Gumbel family
ξ > 0 → Fréchet familyξ < 0 → Weibull family (Thedistribution is upper bounded)
Distance distributions are lowerbounded.
We can model distances under athreshold w using Weibull
distribution.

Figure: pdf of the Weibull
distribution

16/28
Estimating Local Intrinsic Dimensionality

Introduction
Models of ID
Extreme Value Theory
ID Estimation

Threshold model
ID in the threshold model

Modeling the tail of a distance distribution
Modeling threshold excesses
As a certain threshold w approaches 0, the excess Y = w − X
follows a GPD with parameters ξ and σ: 1ξy − ξPr[Y ≤ y |Y < w ] ≈ 1 − 1 +σHeuristic
As w → 0, the distribution of X restricted to the tail [0, w )converges to that of a random distance variable X ∗
FX ,w (x) ≈ FX ∗ ,w (x) =xw

− 1

ξ

17/28
Estimating Local Intrinsic Dimensionality

Introduction
Models of ID
Extreme Value Theory
ID Estimation

Threshold model
ID in the threshold model

Modeling the tail of a distance distribution
Modeling threshold excesses
x · fX ∗ ,w (x)1=−x→0 FX ∗ ,w (x)ξIDFX (0) ≈ lim IDFX ∗ (x) = limx→0Remarks
This is an approximation since it holds for the limit
distribution as w → 0.

We can use classical estimation methods to estimate theparameter ξ.
Note: In EVT, −1/ξ is called the index of the distribution.
18/28
Estimating Local Intrinsic Dimensionality

Introduction
Models of ID
Extreme Value Theory
ID Estimation

Our estimators
Experimental results and interpretation

Usual statistical methods
Maximum likelihood estimatornX xi
c F ∗ (0) = − 1lnIDXnxn!−1i=1

Method of moments estimatorc F ∗ (0) = −kIDXµ̂kµ̂k − xnk

whereµ̂k =nX

xik

i=1

Probability weighted moments estimator
nc F ∗ (0) =IDXν̂k1X
where ν̂k =w − (k + 1)ν̂kni=1

i − 0.35nEstimating Local Intrinsic Dimensionality

kxi
19/28

Introduction
Models of ID
Extreme Value Theory
ID Estimation

Our estimators
Experimental results and interpretation

Regularly Varying Functions Estimator

Regularly Varying Functions EstimatorJP
αj ln F̂X ((1 + τj δn )xn )/F̂X (xn )c F ∗ (0) = κ̂ = j=1IDXJP
αj ln(1 + τj δn )j=1

under the assumption that δn → 0+ as n → ∞where : (αj )1≤j<J and (τj )1≤j<J are sequences.

20/28
Estimating Local Intrinsic Dimensionality

Introduction
Models of ID
Extreme Value Theory
ID Estimation

Our estimators
Experimental results and interpretation

LID estimation in artificial distances

3.6

2

Estimated ID

3.2
3Standard Deviation / ID

MLE
MoM
RV (J=1)
RV (J=2)
ID

3.4

2.8
2.6
2.4
2.2
2

MLE
MoM
RV (J=1)
RV (J=2)

1.5
1
0.5

1.8
101001000Number of samples

10000

101001000
Number of samples

10000

Figure: Comparison of ID estimates (ID=2)

21/28
Estimating Local Intrinsic Dimensionality

Introduction
Models of ID
Extreme Value Theory
ID Estimation

Our estimators
Experimental results and interpretation

LID estimation in artificial distances48

2

Estimated ID

4442

Standard Deviation / ID

MLE
MoM
RV (J=1)
RV (J=2)
ID

4640
38
36
34
32

MLE
MoM
RV (J=1)
RV (J=2)

1.5
10.5

30
101001000
Number of samples

10000

101001000
Number of samples

10000

Figure: Comparison of ID estimates (ID=32)

22/28
Estimating Local Intrinsic Dimensionality

Introduction
Models of ID
Extreme Value Theory
ID Estimation

Our estimators
Experimental results and interpretation

ID estimation in artificial datasets
Datasets
manifold
123d1034D
1156456742628336
3

description
Uniformly sampled sphereAffine space
Concentrated figure
confusable with a 3d one
Non-linear manifold
2-d Helix
Non-linear manifold
Swiss-Roll

23/28
Estimating Local Intrinsic Dimensionality

Introduction
Models of ID
Extreme Value Theory
ID Estimation

Our estimators
Experimental results and interpretation

ID estimation in artificial datasets
Datasets
manifold
8910a10b10c111213d1220
1017242201D7220111825
320
13description
Non-linear manifold
Affine space
Uniformly sampled hypercube
Uniformly sampled hypercube
Uniformly sampled hypercube
Möbius band 10-times twisted
Isotropic multivariate Gaussian
Curve

24/28
Estimating Local Intrinsic Dimensionality

Introduction
Models of ID
Extreme Value Theory
ID Estimation

Our estimators
Experimental results and interpretation

What is the Intrinsic Dimension?

Estimateddimensionality

Column 120191817162015
14131211151098761054352
130-1-2-4-5-6-72Column 2-3024620181614
12108-2-8-4-9 -6-8-10-10-10 -9 -8 -7 -6 -5 -4-3 -2 -1 01123456789 10 11 12 13 14 151617 18 19 20 Column 0Figure: Data structures are detected by ID
25/28
Estimating Local Intrinsic Dimensionality

Introduction
Models of ID
Extreme Value Theory
ID Estimation

Our estimators
Experimental results and interpretationID estimation in artificial datasets

Conclusions
Local estimators tend to over-estimate the dimensionality of
non-linear manifolds, and to under-estimate that of linearmanifolds.
For nonlinear manifolds, global estimators have difficulty in
identifying the intrinsic dimension.
The higher the sampling rate, the lower the bias.
Global methods are very affected by noise, while local
methods are more resistant.

26/28
Estimating Local Intrinsic Dimensionality

Introduction
Models of ID
Extreme Value Theory
ID Estimation

Our estimators
Experimental results and interpretationValues of LID in real datasets
Abs. Frequency

ALOI
4K
3K
2K
1K
0K

051015202530

35253035

Estimated ID
Abs. Frequency

MNIST
4K
3K
2K
1K
0K

05

101520Estimated ID

Figure: LID MLE estimates in ALOI and MNIST

27/28
Estimating Local Intrinsic Dimensionality

Introduction
Models of ID
Extreme Value Theory
ID Estimation

Thank you for your attention!

28/28
Estimating Local Intrinsic Dimensionality