Partitioned K-nearest neighbor local depth for scalable comparison-based learning

Abstract: A triplet comparison oracle on a set

S

takes an object

x i n S

and for any pair

y, z s u b s e t S s e t m i n u s x

declares which of

y

and

z

is more similar to

x

. Partitioned Local Depth (PaLD) supplies a principled non-parametric partitioning of

S

under such triplet comparisons but needs

O (n^{2} l o g n)

oracle calls and

O (n^{3})

post-processing steps. We introduce Partitioned Nearest Neighbors Local Depth (PaNNLD), a computationally tractable variant of PaLD leveraging the

K

-nearest neighbors digraph on

S

. PaNNLD needs only

O (n K l o g n)

oracle calls, by replacing an oracle call by a coin flip when neither

y

nor

z

is adjacent to

x

in the undirected version of the

K

-nearest neighbors digraph. By averaging over randomizations, PaNNLD subsequently requires (at best) only

O (n K^{2})

post-processing steps. Concentration of measure shows that the probability of randomization-induced error

d e l t a

in PaNNLD is no more than

2 e^{- d e l t a^{2} K^{2}}

.

This page was built for publication: Partitioned K-nearest neighbor local depth for scalable comparison-based learning