Parametrizing the easiness ofmachine learning problems
Sanjoy Dasgupta, UC San DiegoOutline• Linear separators• Mixture models• Nonparametric clustering• Nonparametric classification and regression• Nearest neighbor searchLearning linear separators
Finding the best linear separator for a data set is NP-hard.
But this problem is a basic primitive that can be solved easily.
1950s: “margin” is a measure of the easiness of a linear separation task.
1. Separable data (1950s)
Default: linear programming.
With margin: the three-line perceptron algorithm.
2. Non-separable data (1990s)
Notion of soft margin.
Optimize the soft margin: SVM.
Generalization bounds depend on margin.
Progress in algorithms for linear classification and in statistical analysis ofsuch procedures has been driven by the notion of margin.

Learning mixture models
Given data from an unknown mixture of k Gaussians in Rd, determine theparameters of that mixture model.
Studied since 1894.
Statistical literature fixated upon a local search procedure: EM.
Recent progress has been driven by a measure of easiness: the separation.
How many standard deviations apart are the centers of the Gaussians?

Algorithms that assume a certain amount of separation:

pdp4

dEM

p4

kVempala0
Hsu-Kakade

StatisticalNonparametrictheory in clustering clustering
Data points X1 , . . . , Xn are independent random draws from an
unknown density f on Rd! Different random sample ⇒ similar clustering (if n is large)! As n → ∞: approach “natural clusters” of f

0.1
0.05

0.14

2

0.14

1.5

0.12

0.12
0.14

0.1

0.12

0.08

0.1

0.06

0.08

0.04

0.06

0.02

0.04

00.020-2-1.5-1-0.5

00.5

11.5

2 -2

-1.5

-1-0.5

00.5

11.5

2

1

0.1

0.5
0.08
00.06
-0.5
0.04

-10.02-1.5-20-2-1.5-1-0.500.5

11.5

2cluster ≡ connected component of {x : f (x) ≥ λ}, any λ > 0
These clusters form an infinite hierarchy, the cluster tree.

Converging to the cluster tree

Converging to the cluster tree

2 3
14

1 2 3

45

5

6

6

Consistency: Let A, A! be connected components of {f ≥ λ}, forany λ. In the tree constructed from n data points Xn , let An be
the smallest cluster containing A ∩ Xn ; likewise A!n . Then:lim Prob[An is disjoint from A!n ] = 1n→∞Hartigan (1975): Single linkage is consistent for d = 1.
Hartigan (1982): Single linkage is not consistent for d > 1.
Chaudhuri-D (2009): A slight variant of single linkage is consistent for all d.

salience
Which clusters are Cluster
most salient?
Effect 1: thin bridges

A and A! are (σ, ")-separated if:- separated by some set S- max density in Sσ ≤(1 − ")(min density in Aσ , A!σ )For any set Z , let Zσ be all
points within distance σ of it.
Effect 2: density dipA’ASRate of convergence
Rate of convergence
A and A! are (σ, ")-separated if:- separated by some set S- max density in Sσ ≤(1 − ")(min density in Aσ , A!σ )A’AS

With high probability, for all connected sets A, A0 :if they have minimum density
and are ( , ✏)With high probability,
separated,then they forwillalllie in separate subtrees!:
connectedsets A, Aof
when
the number
samples satisfies
if A, A! are (σ, ")-separated,dλ,and have minimum density.
n2d✏then fordn ≥lower“Matching”
λ"2 σ dbound: there is a distribution
whose clusters require at least this many
there
will tobe distinguish.
some intermediate
samplesgraph Gr such that:! There is no path between
A and A! in Gr
Open! A problem:
and A! are individuallymore general notion of cluster salience, andconnected in Gr
algorithms that are adapted to it.

Nonparametric regression
The traditional bane of nonparametric statistics is the curse of dimension.
Stone (1977): for data in RD, convergence rate 1/n1/D.
Three sources of recent rejuvenation:
1. Manifold learning
Geometry/physics of the underlying domain constrains data to lie near alow-dimensional manifold.
2. Sparse data/models
For instance, text data.
3. Bayesian nonparametrics
Models that are exploit prior knowledge and smoothness to givemeaningful predictions even with limited training data.
Is there a good unifying framework for 1,2, and other similar situations?

Doubling dimension
Set S ⇢ RD has doubling dimension d if for any Euclidean ball B, the subset
S \ B can be covered by 2d balls of half the radius.
S = line
Doubling dimension d = 1B"

S = k-flat
Doubling dimension d = O(k)S = set of N points
Doubling dimension d = O(log N)

S = set of k-sparse points in RD
Doubling dimension d = O(k log D)

S = d-dimensional submanifold of RDwith finite condition number
Doubling dimension d = O(k) in smallenough neighborhoods

Rates of convergence for nonparametrics
A variety of methods that automatically adapt to the doubling dimension d of adata set in RD (much of it due to Kpotufe):
Tree-based regression and classification:

n 1/D =) n 1/(d log d)Kernel regression and classification:

n 1/D =) n 1/d
K-nn regression and classification:

n 1/D =) n 1/dOpen problem: more general notion of intrinsic dimension that captures“degrees of freedom”.

Nearest-neighbor search
Given n data points X:
Build a data structure on X.
Given subsequent query q:
Use the data structure to find NN(q,X) efficiently.
Goals:Data structure size O(n), or maybe a bit more
Query time o(n), hopefully much lessThree fairly common choices:
1. In metric spaces: hierarchical cover of some sort
2. In Euclidean space:
K-d tree (or variants thereof) with defeatist search
Locality-sensitive hashing
Often-quoted conjecture: any scheme for NN search requires either thequery time or the size of the data structure to be exponential in thedimension.

Approximate NN search
For some c > 1, enough to return a point in X that is at most c times as far
away as the true NN.
Locality-sensitive hashing (Indyk, Andoni) for Euclidean data:
1+1/c2

Data structure size n
1/c2
Query time nConstant probability of successSome problems:This is efficient only for fairly large c.
The constant c has very different implications for different data sets.

Low intrinsic dimension
Can we do exact NN search in time exponential in the intrinsic dimension
rather than the apparent dimension?

Distribution P (over a metric space) is a doubling measure of dimension dif for all points x and radii r,P (B(x, 2r))  2d P (B(x, r))Many methods have query time 2O(d) polylog(n) in this setting.
For instance, cover tree (Beygelzimer, Kakade, Langford)

Problem: this is too strong a notion of intrinsic dimension.

Exact NN search using spill trees
Randomized trees for NN search

split

Dasgupta Sinha

Spill tree (Liu, Gray; Mount et al;others): same thing, but withoverlapping cells
random split directions

perturbed split

overlapping split

K-d with defeatist search:
11+↵Ak-dtree,
withaxis-parallel
splits.
Right:
Ain 1whichthe split
2variant+↵
answer a query q by the NN2
directions are chosen randomly from the unit sphere.
in q’s leaf node1
gure 1:2 Left:

Frequently
not the true NN.
Function
MakeRPTree(S) no :The
returnleafrefercontaining
Swithdimension.
typesIfDegradesof|S|
split.
fractionsto probability
mass. ↵ is some constant,
Pick U uniformly at random from the unit sphereis chosen
uniformly at random from [1/4, 3/4].
Pick
uniformly at random from [1/4, 3/4]
Let v be the -fractile point on the projection of S onto U
Rule(x) = (left if x · U < v, otherwise right)

Analysis of spill tree

For any set of n points x1 , . . . , xn 2 Rd and any query q 2 Rd , let x(1) , . . . , x(n)be a reordering of the points by increasing distance from q. Then the probabilityof failing to get the exact NN is proportional ton1 X kq
n i=1 kqx(1) k.
x(i) kOpen problem: a measure of the easiness of a dataset-query configuration.