Comparison Based Learning from Weak Oracles

arXiv:1802.06942v1 [cs.LG] 20 Feb 2018

Ehsan Kazemi1 , Lin Chen1 , Sanjoy Dasgupta2 , and Amin Karbasi1
1

2

Yale Institute for Network Science, Yale University
Jacobs School of Engineering, University of California San Diego

{ehsan.kazemi, lin.chen, amin.karbasi}@yale.edu,
dasgupta@eng.ucsd.edu

Abstract
There is increasing interest in learning algorithms that involve interaction between human and machine. Comparison-based queries are among the most natural ways to get feedback from humans. A challenge in designing comparison-based interactive learning algorithms is coping with noisy answers. The most common fix is to submit a query several
times, but this is not applicable in many situations due to its prohibitive cost and due to the
unrealistic assumption of independent noise in different repetitions of the same query.
In this paper, we introduce a new weak oracle model, where a non-malicious user responds to a pairwise comparison query only when she is quite sure about the answer. This
model is able to mimic the behavior of a human in noise-prone regions. We also consider
the application of this weak oracle model to the problem of content search (a variant of the
nearest neighbor search problem) through comparisons. More specifically, we aim at devising efficient algorithms to locate a target object in a database equipped with a dissimilarity
metric via invocation of the weak comparison oracle. We propose two algorithms termed
W ORCS -I and W ORCS -II (Weak-Oracle Comparison-based Search), which provably locate
the target object in a number of comparisons close to the entropy of the target distribution. While W ORCS -I provides better theoretical guarantees, W ORCS -II is applicable to
more technically challenging scenarios where the algorithm has limited access to the ranking dissimilarity between objects. A series of experiments validate the performance of our
proposed algorithms.

1

Introduction

Interactive machine learning refers to many important applications of machine learning that
involve collaboration of human and machines. The goal of an interactive learning algorithm is
to learn an unknown target hypothesis from input provided by humans1 in the forms of labels,
pairwise comparisons, rankings or numerical evaluations [Huang et al., 2010, Settles, 2010,
Yan et al., 2011]. A good algorithm, in both theory and practice, should be able to efficiently
deal with inconsistent or noisy data because human feedback can be erroneous. For instance,
experimental studies show error rates up to 30% in crowdsourcing platforms such as Amazon
Mechanical Turk [Ipeirotis et al., 2010].
Studies conducted by psychologists and sociologists suggest that humans are bad at assigning meaningful numerical values to distances between objects or at rankings [Stewart et al.,
1 In

this paper, we refer to human, crowd or user interchangeably.

1

2005]. It has been shown that pairwise comparisons are a natural way to collect user feedback [Thurstone, 1927, Salganik and Levy, 2015]: they tend to produce responses that are
most consistent across users, and they are less sensitive to noise and manipulation [Maystre
and Grossglauser, 2015]. Despite many successful applications of pairwise comparison queries
in noise-free environments, little is known on how to design and analyze noise-tolerant algorithms. Furthermore, many active learning methods end up querying points that are the most
noise-prone [Balcan et al., 2009].
In the literature, the most common approach to cope with noisy answers from comparison
based oracles is to make a query several times and use majority voting [Dalvi et al., 2013].
These methods assume that by repeating a question they can reduce the error probability arbitrarily. As an example, this approach has been considered in the context of classic binary
search through different hypotheses and shown to be suboptimal [Karp and Kleinberg, 2007,
Nowak, 2009]. In general, the idea of repeated queries for handling noisy oracles suffers from
three main disadvantages: (i) In many important applications, such as recommender systems
and exploratory searches, the algorithm is interacting with only one human and it is not possible to incorporate feedback from several users. (ii) Many queries are inherently difficult, even
for human experts, to answer. (iii) Massive redundancy significantly increases the total number
of oracle accesses in the learning process. Note that each query information requires significant
cost and effort.
In order to efficiently address the problem of non-perfect and noisy answers from the crowd,
we introduce a new weak oracle model, where a non-malicious user responds to a pairwise
comparison query only when she is quite sure about the answer More specifically, we focus on
the application of this weak oracle model to queries of the form of “is object z more similar
to object x or to object y?”. In this model, a weak oracle gives an answer only if one of the
two objects x or y is substantially more similar to z than the other. We make this important
assumption to cope with difficult and error-prone situations where, to almost the same degree,
the two objects are similar to the target. Since the oracle may decline to answer a query, we
can refer to it as an abstention oracle. This model is one of the very first attempts to somewhat
accurately mimic the behavior of crowd in real world problems. To motivate the main model
and algorithms of this paper consider the following example.
Example 1. Assume Alice is a new user to our movie recommender system platform. In order
to recommend potentially interesting movies to Alice, we plan to figure out an unknown target
movie2 that she likes the most. Our aim is to find her favorite movie by asking her preference
over pairs of movies she has watched already. With each response from Alice, we expect to
get closer to the target movie. For this reason, we are interested in algorithms that find Alice’s
taste by asking a few questions. To achieve this goal, we should (i) present Alice movies that
are different enough from each other to make decision easier for her, and (ii) find her interest
with the minimum number of pairwise comparisons because each query takes some time and
the number of potential queries might be limited.
To elaborate more on the usefulness of our weak oracle model, as a special case of active
learning, we aim at devising an algorithm to locate a target object in a database through comparisons. We model objects in the database as a set of points in a metric space. In this problem,
a user (modeled by a weak oracle) has an object t (e.g., her favorite movie or music) in mind
which is not revealed to the algorithm. At each time, the user is presented with two candidate
objects x and y. Then through the query Ot (x, y) she indicates which of these is closer to the
target object. Previous works assume a strong comparison oracle that always gives the correct
answer [Tschopp et al., 2011, Karbasi et al., 2012a,b]. However, as we discussed earlier, it is
2 The

target movie of Alice is unknown to the platform.

2

challenging, in practice, for the user to pinpoint the closer object when the two are similar to
the target to almost the same degree.
We therefore propose the problem of comparison-based search via a weak oracle that gives
an answer only if one of the two objects is substantially more similar to the target than the other.
Note that due to the weak oracle assumption, the user cannot choose the closer object if they are
in almost the same distance to the target. Our goal is to find the target by making as few queries
as possible to the weak comparison oracle. We also consider the case in which the demand over
the target objects is heterogeneous, i.e., there are different demands for object in the database.
Analysis of our algorithms relies on a measure of intrinsic dimensionality for the distribution
of demand. These notions of dimension imply, roughly, that the number of points in a ball in
the metric space increases by only a constant factor when the radius of the ball is doubled. This
is known to hold, for instance, under limited curvature and random selection of points from
a manifold (two reasonable assumptions in machine learning applications) [Karger and Ruhl,
2002]. Computing the intrinsic dimension is difficult in general, but we do not need to know its
value; it merely appears in the query bounds for our algorithms.
Contributions In this paper, we make the following contributions:
• We introduce the weak oracle model to handle human behavior, when answering comparison queries, in a more realistic way. We believe that this weak oracle model opens
new avenues for designing algorithms, which handle noisy situations efficiently, for many
machine learning applications.
• As an important example of our weak oracle model, we propose a new adaptive algorithm, called W ORCS -I, to find an object in a database. This algorithm relies on a priori
knowledge of the distance between objects, i.e., it assumes we can compute the distance
between any two objects.
• We prove that, under the weak oracle model, if the search space satisfies certain mild
conditions then our algorithm will find the target in a near-optimal number of queries.
• In many realistic and technically challenging scenarios, it is difficult to compute all the
pairwise distances and we might have access only to a noisy information about relative
distances of points. To address this challenge, we propose W ORCS -II. The main assumption in W ORCS -II is that for all triplets x, y and z we only know if the the distance of
one of x or y is closer to z by a factor of α. Note this is a much less required information
than knowing all the pairwise distances. This kind of information could be obtained, for
example, from an approximation of the distance function.3 We prove that W ORCS -II,
by using only this minimal information, can locate the target in a reasonable number of
queries. We also prove that if W ORCS -II is allowed to learn about the ranking relationships between objects, it provides better theoretical guarantees.
• Finally, we evaluate the performance of our proposed algorithms and several other baseline algorithms over real datasets.
The remainder of this paper is organized as follows. We discuss the related work in Section 2. We overview definitions and preliminaries in Section 3. We present the main algorithms
of this paper in Section 4. In Section 5, we report our experimental evaluations. We conclude
the paper in Section 6.
3 Finding

the partial relative distances between points is not the focus of this paper.

3

2

Related Work

Interactive learning from pairwise comparisons has a range of applications in machine learning,
including exploratory search for objects in a database [Tschopp et al., 2011, Karbasi et al., 2011,
2012a,b], nearest neighbor search [Goyal et al., 2008], ranking or finding the top-k ranked items
[Chen et al., 2013, Wauthier et al., 2013, Eriksson, 2013, Maystre and Grossglauser, 2015,
Heckel et al., 2016, Maystre and Grossglauser, 2017], crowdsourcing entity resolution [Wang
et al., 2012, 2013, Firmani et al., 2016], learning user preferences in a recommender system
[Wang et al., 2014, Qian et al., 2015], estimating an underlying value function [Balcan et al.,
2016], multiclass classification [Hastie and Tibshirani, 1997], embedding visualization [Tamuz
et al., 2011] and image retrieval [Wah et al., 2014].
Comparison-based search, as a form of interactive learning, was first introduced by Goyal
et al. [2008]. Lifshits and Zhang [2009] and Tschopp et al. [2011] explored this problem in
worst-case scenarios, where they assumed demands for the objects are homogeneous.4 Karbasi
et al. [2011] took a Bayesian approach to the problem for heterogeneous demands, i.e, where
the distribution of demands are far from the uniform. It is noteworthy that the two problems
of content search and finding nearest neighbor are closely related [Clarkson, 2006, Indyk and
Motwani, 1998].
Search though comparisons can be formalized as an special case of the Generalized Binary
Search (GBS) or splitting algorithm [Dasgupta, 2004, 2005], where the goal is to learn an
underlying function from pairwise comparisons. In practice GBS performs very well in terms
of required number of queries, but it appears to be difficult to provide tight bounds for its
performance. Furthermore, its computational complexity is prohibitive for large databases. For
this reason, Karbasi et al. [2012a,b] introduced faster algorithms that locate the target in a
database with near-optimal expected query complexities. In their work, they assume a strong
oracle model and a small intrinsic dimension for points in the metric space.
The search process should be robust against erroneous answers. Karp and Kleinberg [2007]
and Nowak [2009] explored the idea of repeated queries for the GBS to cope with noisy oracles.
Also, for the special case of search though comparisons, Karbasi et al. [2012a] propose similar
ideas for handling noise.
The notion of assuming a small intrinsic dimension for points in a metric space is used
in many different problems such as finding the nearest neighbor [Clarkson, 2006, Har-Peled
and Kumar, 2013], routing [Hildrum et al., 2004, Tschopp et al., 2015], and proximity search
[Krauthgamer and Lee, 2004].

3

Definitions and Preliminaries

Let M be a metric space with distance function d(·, ·). Intuitively, M characterizes the database
of objects. An example of a distance function is the Euclidean distance between feature vectors
of items in a database. Given any object x ∈ M, we define the ball centered at x with radius r
as Bx (r) , {y ∈ M : d(x, y) ≤ r}. We define the diameter of a set A ⊆ M as diam(A) =
supx,y∈A d(x, y). We will consider a distribution
P µ over the set M which we call the demand:
it is a non-negative
function
M
→
[0,
1]
with
1. For any set A ⊆ M, we define
x∈M µ(x) =P
P
1
, where
µ(A) = x∈A µ(x). The entropy of µ is given by H(µ) = x∈supp(M) µ(x) log µ(x)
supp(µ) , {x ∈ M : µ(x) > 0} is the support of µ. Next, we define an -cover and an -net
for a set A ⊆ M.
4 Their

distributions are close to uniform.

4

Definition 1 (-cover). An -cover of a subset A ⊆ M is a collection of points {x1 , · · · , xk }
Sk
of A such that A ⊆ i=1 Bxi ().
Definition 2 (-net). An -net of a subset A ⊆ M is a maximal (a set to which no more
objects can be added) collection of points {x1 , · · · , xk } of A such that for any i 6= j we have
d(xi , xj ) > .
An -net can be constructed efficiently via a greedy algorithm in O(k 2 |A|) time, where
k is the size of the -net. We refer interested readers to [Clarkson, 2006]. Our algorithms are
analyzed under natural assumptions on the expansion rate and underlying dimension of datasets,
where we define them next.
Doubling Measures The doubling constant captures the embedding topology of the set of
objects in a metric space when we are generalizing analysis from Euclidean spaces to more
general metric spaces. Such restrictions imply that the volume of a closed ball in the space does
not increase drastically when its radius is increased by a certain factor. Formally, the doubling
constant of the measure µ [Karger and Ruhl, 2002] is given by
c,

µ(Bx (2R))
.
x∈supp(µ),R≥0 µ(Bx (R))
sup

A measure µ is c-doubling if its doubling constant is c < ∞. We define dimm (M) = log c.
To provide guarantees for the performance of algorithms in Sections 4.3 and 4.4, a stronger
notion of doubling measure is required. Intuitively, we need bounds on the expansion rate of all
the possible subsets of support of µ. The strong doubling constant of the measure µ [Ram and
Gray, 2013, Haghiri et al., 2017] is given by
cstrong , sup

sup

A⊆M x∈supp(µ)∩A,R≥0

µ(Bx (2R) ∩ A)
.
µ(Bx (R) ∩ A)

We also say that measure µ is cstrong -doubling if its strong doubling constant is cstrong < ∞.
Note that for a finite space M both c and cstrong are bounded.
Doubling Spaces The doubling dimension of a metric space (M, d) is the smallest k such
that every subset Bx (2R) of M can be covered by at most k balls of radius R. We define
the doubling dimension dims (M) = log2 k. Lemma 1 states that a metric with a bounded
doubling constant has a bounded doubling dimension, i.e., every doubling measure carries a
doubling space.
Lemma 1 (Proposition 1.2. [Gupta et al., 2003]). For any finite metric (M, d), we have
dims (M) ≤ 4dimm (M),
where dimm (M) , log2 c.
Proof. To prove this lemma, we show that any ball Bx (2R) could be covered by at most k ≤ c4
balls of radius R.
Lemma 2. An -net of A is an -cover of A.
Proof. Let {x1 , x2 , · · · , xk } be an -net of A. Suppose that there exists x ∈ A such that
Sk
x∈
/ i=1 Bxi (). Then we know that d(x, xi ) >  for all i. This contradicts the maximality of
the -net.
5

Assume {x1 , x2 , · · · , xk } is an R-net of the ball Bx (2R). We know for all i 6= j, Bxi (R/2)∩
Pk
Bxj (R/2) = ∅. Therefore, we have µ(∪ki=1 Bxi (R/2)) = i=1 µ(Bxi (R/2)). Also,
µ(Bxi (R/2)) ≥ c−3 µ(Bxi (4R)) ≥ c−3 µ(Bx (2R)).
Also, ∪ki=1 Bxi (R/2) ⊆ Bx (4R). To sum-up we have
µ(Bx (2R)) ≥ c−1 µ(Bx (4R)) ≥ c−1 µ(∪ki=1 Bxi (R/2))
≥ c−1

k
X
i=1

µ(Bxi (R/2)) ≥ kc−4 µ(Bx (2R)).

Weak Comparison Oracle The strong comparison oracle Ozstrong (x, y) [Goyal et al., 2008]
takes three objects x, y, z as input and returns which one of x and y is closer to z; formally,
(
x, if d(x, z) ≤ d(y, z),
strong
Oz
(x, y) =
y, otherwise.
In this paper, we propose the weak comparison oracle5 as a more realistic and practical
model. This oracle gives an answer for sure only if one of d(x, z) and d(y, z) is substantially
smaller than the other. Formally,

x,
if αd(x, z) ≤ d(y, z),



y,
if αd(y, z) ≤ d(x, z),
Oz (x, y) =

?
or
x,
if d(x, z) ≤ d(y, z) < αd(x, z),



? or y, if d(y, z) < d(x, z) < αd(y, z).
where α ≥ 1 is a constant that characterizes the approximate equidistance of x and y. More
precisely, the answers to a query Oz (x, y) has the following interpretation: (i) if it is x, then
d(x, z) ≤ d(y, z). (ii) if it is y, d(x, z) > d(y, z). (iii) if it is ?, d(x, z) and d(y, z) are within
a multiplicative factor α of each other. In our model, an answer of x or y does not provide any
information about the relative distances of x and y from the target other than stating that one
of them is closer to t. Given x, y ∈ A ⊆ M, the α-weighted Voronoi cell of x is defined as
V or(x, y, A) = {v ∈ A : αd(x, v) ≤ d(y, v)}, where α ≥ 1. Similarly, we can define the
α-weighted Voronoi cell of y as V or(y, x, A). Note that the two Voronoi cells V or(x, y, A)
and V or(y, x, A) contain the set of points which we are sure about the answers we get from the
oracle. Fig. 1 shows answers we get from a weak oracle to the query Oz (x, y) for points z in
different regions of a 2-dimensional Euclidean space.

4

Main Results

Our main goal is to design an algorithm that can locate an unknown target t ∈ M by making
only f (c)H(µ) queries in expectation, where f (c) is polynomial in the doubling constant c. In
addition, we are interested in algorithms with a low computational complexity for deciding on
the next query which we are going to make. Note that identifying a target having access to the
5 We

refer to it as an abstention oracle interchangeably.

6

Oz (x, y) = x or ?

Oz (x, y) = y or ?

2d(x,y)
3

µ1

x

d(x, y)

Oz (x, y) = x

y

µ2

Oz (x, y) = y

Figure 1: Voronoi cells with a multiplicative distance α = 2 for a two dimensional Euclidean
space. This figure partition the space into three parts based on the potential answers from the
oracle.
very powerful membership oracle6 in average needs at least H(µ) queries [Cover and Thomas,
2012]. Also, Karbasi et al. [2011] proved that a strong oracle needs Ω(cH(µ)) queries to find an
object via a strong oracle. To sum-up, we conclude that an algorithm with a query complexity
f (c)H(µ) is near-optimal (in terms of number of queries) for a weak oracle model.

4.1

Generalized Ternary Search

In this section, we first take a greedy approach to the content search problem as a baseline.
Let the version space Vi be the set of points (hypotheses) consistent with the answers received
from the oracle so far (at time i). After each query Ot (x, y) there are three possible outcomes
of “x”, “y” or “?”. The Generalized Ternary Search algorithm (G TS), as a generalization of
GBS [Dasgupta, 2004], greedily selects the query Ot (x, y) that results in the largest reduction
in mass of the version space based on the potential outcomes. More rigorously, the next query
to be asked by G TS is found through
X
X
X
arg min max(
µ(z),
µ(z),
µ(z)).
(1)
(x,y)∈Vi2

z∈Vi ,Oz (x,y)=x

z∈Vi ,Oz (x,y)=y

z∈Vi ,Oz (x,y)=?

3

The computational complexity of GTS is Θ(n ) and thus makes it prohibitive for large databases.
Also, while this type of greedy algorithms performs well in practice (in terms of number of
queries), it is difficult (or even impossible) to provide tight bounds for their performances [Dasgupta, 2004, Golovin and Krause, 2011]. Furthermore, the noisy oracle model makes analysis
even harder. For this reason, we need more efficient algorithms with provable guarantees. The
key ingredient of our methods is how to choose queries in order to find the target in a near
optimal number of queries.

4.2

Full Knowledge of the Metric Space

The first algorithm we present (W ORCS -I) relies on a priori knowledge of the distribution µ
and the pairwise distances between all the points. We prove that W ORCS -I (see Algorithm 1)
6 An

oracle such that for any A ⊆ M identifies if t ∈ A or not.

7

locates the target t, where its query complexity is within a constant factor from the optimum.
W ORCS -I uses two main ideas: (i) it guarantees that, by carefully covering the version space,
in each iteration the target t remains in the ball (which is found in line 11 of Algorithm 1), and
(ii) the volume of version space decreases by a constant factor at each iteration. These two facts
ensure that in a few iterations we can locate the target. We should mention that while W ORCS -I
relies on knowing all the pairwise distances, but we guarantee bounds for a c-doubling measure
µ in the metric space M.7 Later in this section, we devise two other algorithms that relax the
assumption of having access to the pairwise distances.
Theorem 1. The average number of queries required by W ORCS -I to locate an object is
bounded from above by
i
h
H(µ)
,
f (c) · 1 + log(1/(1−c
−2 ))
where c is the doubling constant of the measure µ in the metric space M and f (c) is a polynomial function in c.
Proof. To prove this theorem, we show: (a) In each iteration the target t remains in the next
version space. Therefore, W ORCS -I always find the target t. (b) The µ-mass of the version
space shrinks by a factor of at least 1 − c−2 in each iteration, which results in the total number
H(µ)
of 1+ log(1/(1−c
−2 )) iterations. (c) The number of queries to find the next version space is upper
bounded by a polynomial function of the doubling constant c.
∆
(a) Assume ct is the center of a ball which contains t, i.e., t ∈ Bct ( 8(α+1)
). For all cj 6= ct
∆
∆
and
such that d(ct , cj ) > 8 , we have Ot (ct , cj ) = ct . This is because d(ct , t) ≤ 8(α+1)
∆
∆
d(cj , t) > 8 − 8(α+1) , and thus αd(ct , t) < d(cj , t). On the other hand, consider an i such that
∆(α+2)
for all j 6= i with d(ci , cj ) > ∆
8 , we have Ot (ci , cj ) = ci . We claim t ∈ Bci ( 8(α+1) ). Assume
∆
this in not true. Then for ct we have d(ci , ct ) > d(ci , t) − 8(α+1)
≥ ∆
8 . Therefore, following
the same lines of reasoning as the fist part of the proof, we should have Ot (ci , ct ) = ct . This
contradicts our assumption.
(b) We have µ(Vi+1 ) ≤ (1 − c−2 )µ(Vi ). To prove this, we first state the following lemma.

Lemma 3. Assume ∆ = maxx,y∈Vi d(x, y). ∀x ∈ Vi we have maxy∈Vi d(x, y) ≥

∆
2.

Proof. Assume x∗ , y ∗ = arg maxx,y∈Vi d(x, y). By using triangle inequality we have d(x, x∗ )+
d(x, y ∗ ) ≥ d(x∗ , y ∗ ) = ∆. We conclude that at least one of d(x, x∗ ) or d(x, y ∗ ) is larger than
∆
∗
∗
or equal to ∆
2 . This results in maxy∈Vi d(x, y) ≥ max{d(x, x ), d(x, y )} ≥ 2 .
Let’s assume ci is the center of µ(Vi+1 ) and point c∗i is the furthest point from ci . From
∆(α+2)
Lemma 3 we know that d(ci , c∗i ) ≥ ∆
2 . Also, it is straightforward to see Bci ( 8(α+1) ) ∩
∆
−2
∗
Bc∗i ( ∆
µ(Bc∗i (∆)) ≥
4 ) = ∅. From the definition of expansion rate we have µ(Bci ( 4 )) ≥ c
−2
c µ(Vi ).
(c) Let’s consider t ∈ supp M as the target. W ORCS -I locates the target t, provided
log µ(t)
log(µ(t)
µ(Vi ) ≤ (1 − c−2 )i µ(V0 ) ≤ µ(t) or equivalently i ≥ 1 + log(1−c
−2 ) ≥ d log(1−c−2 ) e. The


P
log µ(t)
=
expected number of iterations is then upper bounded by t∈supp(M) µ(t) 1 + log(1−c
−2 )
1+

H(µ)
log(1/(1−c−2 )) . Finally,
4dlog 8(α+1)e

from Lemma 1, we know that we can cover the version space Vi

∆
with at most c
balls of radius 8(α+1)
. Note that in the worst case we should query
the center of each ball versus centers of all the other balls in each iteration.
7 This

is a fairly loose condition for a metric space.

8

In order to find a

∆
8(α+1) -cover

in line 8 of Algorithm 1, we can generate a (∆/2l )-net of

Vi , where l = dlog2 8(α + 1)e. The size of such a net is at most cdlog2 8(α+1)e+3 by Lemma 1
in [Karbasi et al., 2012b]. Also, since we assume the value of c is constant, f (c) is independent
of the size of database; it remains constant and our bound depends on the size of database only
through H(µ), which is growing with a factor of at most O(log |M |).
Algorithm 1 W ORCS -I
Input: Metric space M and oracle Ot (·, ·)
Output: Target t
1: V0 ← M
2: i ← 0
3: loop
4:
if |Vi | ≤ 2 then
5:
Invoke Ot (x, y) and halt
6:
end if
7:
∆ ← diameter of Vi
∆
-cover of Vi
8:
Let C be a 8(α+1)
9:
for each ci ∈ C do
10:
if for all cj such that d(ci , cj ) >
11:
Vi+1 ← Bci ( ∆(α+2)
8(α+1) )
12:
end if
13:
end for
14:
i←i+1
15: end loop

4.3

∆
8:

Ot (ci , cj ) = ci then

Partial Knowledge of the Metric Space

Despite the theoretical importance of W ORCS -I, it suffers from two disadvantages: (i) First, it
needs to know the pairwise distances between all points a priori, which makes it impractical in
many applications. (ii) Second, experimental evaluations show that, due to the high degree of
the polynomial function f (c) (see proof of Theorem 1), the query complexity of W ORCS -I is
worse than baseline algorithms for small datasets. To overcome these limitations, we present
another algorithm called W ORCS -II.
W ORCS -II allows us to relax the assumption of having access to all the pairwise distances.
Indeed, the W ORCS -II algorithm can work by knowing only relative distances of points, i.e.,
for each triplets x, y and z, it needs to know only if αd(x, y) ≤ d(x, z) or αd(x, z) ≤ d(x, y).
Note that this is enough to find V or(x, y, Vi ) and V or(y, x, Vi ) for all points x and y. We refer
to this information as F1 . Information of F1 is applied to find the resulting version space after
each query. Theorem 2 guarantees that W ORCS -II, by using F1 and choosing a pair with a β
approximation of the largest distance in each iteration, will lead to a very competitive algorithm.
l

m
Theorem 2. Let l , log2 α+1
. The average number of required queries by W ORCS -II
β
to locate an object is bounded from above by 1 +

H(µ)
,
log(1/(1−c−l
strong ))

where cstrong is the strong

doubling constant of the measure µ in the metric space M.

Proof. Let S1 , Vi \ V or(y, x, Vi ), S2 , Vi \ V or(x, y, Vi ) and S3 , Vi \ (V or(x, y, Vi ) ∪
V or(y, x, Vi )). We denote the distance between x and y by r , d(x, y). Assume ∆ is the
9

Algorithm 2 W ORCS -II
Input: Oracle Ot (·, ·), F1 and F2 . F1 is used for finding the next version space after each
query. Auxiliary information F2 is used for finding points with larger β.
Output: Target t
1: V0 ← M and i ← 0
2: loop
3:
if |Vi | ≤ 2 then
4:
Invoke Ot (x, y) and halt
5:
end if
6:
Find x, y ∈ Vi such that d(x, y) ≥ β diam(Vi )
7:
if Ot (x, y) = x then
8:
Vi+1 = Vi \ V or(y, x, Vi )
9:
else if Ot (x, y) = y then
10:
Vi+1 = Vi \ V or(x, y, Vi )}
11:
else
12:
Vi+1 = Vi \ (V or(x, y, Vi ) ∪ V or(y, x, Vi ))
13:
end if
14:
i←i+1
15: end loop

largest distance between any two pints in Vi , i.e., ∆ , diam(Vi ). We have β = ∆/r for
0 ≤ β ≤ 1. We condition on the target element t ∈ supp(M).
−l
i
i
We first prove that µ(Vi ) ≤ (1 − c−l
strong ) µ(V0 ) = (1 − cstrong ) . Note that we have
r
r
r
2l · α+1
≥ α+1
β · α+1 ≥ ∆. The first step is to show that V or(x, y, Vi ) ⊇ Bx ( α+1 ). For any
r
αr
r
element v ∈ Bx ( α+1 ), we have d(x, v) ≤ α+1 . Therefore, αd(x, v) ≤ α+1 ≤ r − d(x, v) =
d(x, y) − d(x, v) ≤ d(y, v), which yields immediately that v ∈ V or(x, y, Vi ). As a result,
µ(V or(x, y, Vi )) ≥ µ(Bx (

r
r
l
)) ≥ c−l
))
strong µ(Bx (2 ·
α+1
α+1
−l
≥ c−l
strong µ(Bx (D)) ≥ cstrong µ(Vi ).

We deduce that µ(S2 ) = µ(Vi ) − µ(V or(x, y, Vi )) ≤ (1 − c−l
strong )µ(Vi ). Similarly, we
−l
−l
have µ(V or(y, x, Vi )) ≥ cstrong µ(Vi ) and µ(S1 ) ≤ (1 − cstrong )µ(Vi ). In addition, µ(S3 ) ≤
−l
(1 − c−l
strong )µ(Vi ). To sum up, we have max1≤j≤3 µ(Sj ) ≤ (1 − cstrong )µ(Vi ).
i
The search process ends after at most i iterations provided µ(Vi ) ≤ (1 − c−l
strong ) V0 ≤ µ(t),
log µ(t)
or equivalently i ≥ 1 + log(1−c−l ) . The average number of iterations is then bounded from
strong

above by

log µ(t)
µ(t) 1 +
log(1 − c−l
strong )
t∈supp(M)
X

!
≤1+

H(µ)
.
log(1/(1 − c−l
strong ))

Also, in each iteration we need to query only one pair of objects.
From Theorem 2, we observe that the performance of W ORCS -II improves by larger values
of β. Generally, we can assume there is auxiliary information (called F2 ) that could be applied
to find points with larger distances in each iteration. For example, W ORCS -II-R ANK refers
to a version of W ORCS -II where the ranking relationships between objects is provided as side

10

information (it is used for F2 ). By knowing the rankings, we can easily find the farthest points
from x. From the triangle inequality, we can ensure this results in a β of at least 1/2. Also,
W ORCS -II by knowing all the pairwise distances (similar to W ORCS -I), can always find a
query with β = 1. For the detailed explanation of W ORCS -II see Algorithm 2.
Although the theoretical guarantee for W ORCS -II depends on the assumption that the underlying metric space is cstrong -doubling, the dependence in cstrong is through a polynomial
function with a degree much smaller than f (c). Note that the W ORCS -II algorithm finds the
next query much faster than G TS. Indeed, G TS needs O(|Vi |3 ) operations in order to find the
next query at each iteration. It is easy to see, for example, W ORCS -II-R ANK finds the next
query in only O(|Vi |) steps. In the following, we present a version of W ORCS -II that needs
much less information in order to find an acceptable query.

4.4

Algorithm with Minimalistic Information

In this section, we present W ORCS -II-W EAK which needs only partial information about the
relative distances. This is exactly the information from F1 . W ORCS -II-W EAK, in each iteration, instead of picking two points with distance diam(Vi ) or diam(Vi )/2 (which is possible
only with information provided from F2 ), uses Algorithm 3 to find the next query. From the
result of Lemma 4, we guarantee that Algorithm 3 finds a pair of points with distance at least
∆
2
2α . The computational complexity to find such a pair is O(|Vi | ).
Lemma 4. Assume for x and y there exist no z 6= y such that Ox (y, z) = y, then d(x, y) ≥

∆
2α .

Proof. We first prove that we can always find at least one point with this property. Define
x∗ = arg maxz∈Vi d(x, z). From Lemma 3, we know that d(x, x∗ ) ≥ ∆
2 . We claim there is no
z 6= x∗ such that x ∈ V or(x∗ , z, Vi ). Assume there is a z. This means αd(x, x∗ ) ≤ d(x, z),
where it contradicts with the choice of x∗ . This means that the set of points with this property is
∆
not empty. If y = z ∗ then we are done with the proof, because d(x, x∗ ) ≥ ∆
2 ≥ 2α . Next, we
∆
. Assume y 6= x∗ . We know
prove that for any y 6= x∗ with this property, we have d(x, y) ≥ 2α
∆
∆
∗
∗
x∈
/ V or(y, x , Vi ). Therefore, we have αd(x, y) ≥ d(x, x ) ≥ 2 and d(x, y) ≥ 2α
.
Corollary 1. From the results of Theorem 2 and Lemma 4, we conclude that the expected
H(µ)
query complexity of W ORCS -II-W EAK is bounded from above by 1 + log(1/(1−c
with
−l
))
strong

l = 1 + dlog2 α(α + 1)e.
The bounds in Theorem 2 and Corollary 1 depend on the value of cstrong through the required number of iterations because the reduction in the size of version space is lower bounded
by a function of cstrong . In W ORCS -II at each iteration we only ask one question, therefore we
do not have any dependence on a polynomial function of cstrong . Also, note that our algorithms
do need to know the value of α.
Algorithm 3 Find x and y
Input: Vi and F1
1
Output: (x, y) with d(x, y) ≥ 2α
diam(Vi )
1: Uniformly at random pick x ∈ Vi
2: for y ∈ Vi \ {x} do
3:
if ∀z ∈ Vi \ {x, y} : x ∈
/ V or(y, z, Vi ) then
4:
return (x, y)
5:
end if
6: end for

11

Table 1: Comparison between algorithms
Algorithm

Input information

Constraint

G TS
W ORCS -I
W ORCS -II-R ANK
W ORCS -II-W EAK

Weak rank information
Pairwise distances
Rank information
Weak rank information

No guarantees
Doubling constant
Strong doubling constant
Strong doubling constant

In this section, we presented four different algorithms to locate an object in a database
by using a weak oracle model. These algorithms use different types of information as input.
To provide guarantees for their performances, we need to make different assumptions on the
structure of the underlying metric space (see Table 1).
W ORCS -I provides better theoretical results; The guarantee for W ORCS -I depends on constant values of c which is a looser assumption than having a constant cstrong . In the next section, we will show that although the theoretical guarantee of W ORCS -II is based on a stronger
assumption over the metric space (cstrong vs c), in all of our experiments it shows better performances in comparison to W ORCS -I. It finds the target with fewer queries and the computational
complexity of choosing the next query is much less. We believe that for most real datasets both
c and cstrong are small and close to each other. Therefore, the polynomial term f (c) (defined in
Theorem 1) plays a very important role in practice. Finally, providing guarantees for the performance of G TS or similar algorithms seems impossible [Dasgupta, 2004, Golovin and Krause,
2011].

5

Experiments

We compare W ORCS -I and W ORCS -II (W ORCS -II-W EAK and W ORCS -II-R ANK)8 with several baseline methods. Recall that W ORCS -I needs to know the pairwise distances between
objects, and W ORCS -II-R ANK and W ORCS -II-W EAK need only information about ranking
and partial ordering obtained from the weak oracle, respectively. For choosing the baselines,
we followed the same approach as Karbasi et al. [2012a]. Our baseline methods are:
• G TS which is explained in Section 4.1.
• R ANDOM: The general framework of R ANDOM is the same as Algorithm 2 except that in
Line 6, R ANDOM randomly samples a pair of points x and y in the current version space.
• FAST-G TS: In light of the computationally prohibitive nature of G TS, FAST-G TS is an
approximate alternative to G TS. Rather than finding the exact minimizer, it randomly
samples k pairs of points and finds the minimizer of Eq. (1) only in the sampled pairs.
R ANDOM and GTS can be viewed as a special case of FAST-G TS with parameter k =
1 and k = |V2i | (sampling without repetition), respectively. We take k = 10 in the
experiments.
• M IN D IST: In contrast to W ORCS -II, M IN D IST selects a pair of points that reside closest
to each other. We use this baseline to highlight the importance of choosing a pair that
attain the approximate maximum distance.
8 In

this section, W ORCS -II-R and W ORCS -II-W stand for W ORCS -II-R ANK and W ORCS -II-W EAK.

12

Table 2: Expected Query Complexity on Each Dataset
MovieLens
Wine
Music
Iris

R AND

W ORCS -I

W-II-R9

W-II-W

M IN D IST

G TS

FAST-G TS

11.46
7.03
14.31
7.86

594.97
55.68
648.12
164.42

10.86
6.47
12.71
7.56

10.79
6.11
12.67
6.98

49.45
35.16
143.61
19.85

9.01
22.82
36.90
9.81

9.79
10.46
27.78
9.54

We evaluate the performance of algorithms through two metrics: (i) query complexity: the
expected number of queries to locate an object, and (ii) computational complexity: the total
time-complexity of determining which queries to submit to the oracle. We conduct experiments
over the following datasets: MovieLens [Harper and Konstan, 2016], Wine [Forina et al., 1991],
Music [Zhou et al., 2014], and Fisher’s Iris dataset. The demand distribution µ is set to the
power law with exponent 0.4. In order to model uncertain answers from the oracle Ot (x, y),
i.e., for points t that are almost equidistant from both x and y, we use the following model: if
d(x, t) ≤ d(y, t) < αd(x, t), the oracle outputs x with probability log(d(y,t)/d(x,t))
and outputs
log α
“?” otherwise; similarly if d(y, t) ≤ d(x, t) < αd(y, t), the oracle outputs y with probability
log(d(x,t)/d(y,t)
and outputs “?” otherwise.
log α
We present expected query complexity of all seven algorithms on each dataset in Table 2
(we have to use a table rather than a bar chart since the data are highly skewed). The corresponding computational complexity is shown in Fig. 2(a). It can be observed that W ORCS II-W EAK outperforms all other algorithms in terms of query complexity. W ORCS -II-R ANK
is only second to W ORCS -II-W EAK. Intuitively, selecting two distant items for a query leads
into two large Voronoi cells around them, which partially explains the good performance of
W ORCS -II-R ANK. However, it could leave the rest of the version space relatively small; therefore, it may not reduce the version space substantially when a “?” response is received from
the oracle. Unlike W ORCS -II-R ANK, W ORCS -II-W EAK is only guaranteed to find a pair that
1
attain a β-approximation of the diameter of the current version space, where β ≥ 2α
as shown
in Lemma 4, thereby resulting in a relatively more balanced division of the version space. This
explains the slightly better performance of W ORCS -II-W EAK versus W ORCS -II-R ANK. With
respect to the computational complexity, R ANDOM costs the smallest amount of computational
resources since it does not need to algorithmically decide which pair of items to query. W ORCS II-W EAK is only second to R ANDOM.
Scalability In this set of experiments, in order to study the scalability of algorithms, we use
the Music dataset and sub-sampled 10 to 1000 items from the dataset. Query and computational complexity of different algorithms is shown in Figs. 2(b) and 2(c). We see the positive
correlation between query/computational complexity and the dataset size. Since the curves
are approximately linear in a log-log plot, the complexity of algorithms scales approximately
polynomially in the dataset size. Specifically,
√ the query complexity of W ORCS -II-R ANK and
W ORCS -II-W EAK scales approximately O( N ), where N is the dataset size. In Fig. 2(b), the
curves of W ORCS -II-R ANK and W ORCS -II-W EAK are the two lowest curves, which represent
lowest query complexity.
Impact of α The performance of algorithms for different values of α is another important
aspect to study. We used the Iris dataset and varied α from 1 to 100. Query and computational
complexity of different algorithms is shown in Figs. 2(d) and 2(e). A general upward tendency

13

103
Random
WORCS-I
WORCS-II-R
WORCS-II-W
MinDist
GTS
Fast-GTS

# of operations

10 8

10

6

10

Random
WORCS-I
WORCS-II-R
WORCS-II-W
MinDist
GTS
Fast-GTS

102

101

100
101

10 2

MovieLens

Wine

Music

104

102

3

10 7

102

10 2

10

1

10 2

10

GTS

3

Random
WORCS-I
WORCS-II-R
WORCS-II-W
MinDist
GTS
Fast-GTS

MinDist
WORCS-I

WORCS-II-R

10 5
10 4

2

10 1

(c)

6

10 3

103

Dataset size

# of queries

Random
WORCS-I
WORCS-II-R
WORCS-II-W
MinDist
GBS
Fast-GBS

10 0 0
10

100
101

103

(b)

# of operations

# of queries

6

Dataset size

Iris

(a)

10

10

Random
WORCS-I
WORCS-II-R
WORCS-II-W
MinDist
GTS
Fast-GTS

102

10 4

10

10

108

# of operations

10

# of queries

10

10 2

10

1

Fast-GBS

10 0
10

WORCS-II-W
10

1

Random
10

2

10 0 -1
10

10 0

10 1

10 2

Power law exponent

(d)

(e)

(f)

Figure 2: Fig. 2(a) shows the expected computational complexity, per search, of all seven algorithms applied to each dataset. Figs. 2(d) and 2(e) show the expected query and computational
complexity as a function of the dataset size. We present how the expected query and computational complexity vary with α in Figs. 2(d) and 2(e). In Fig. 2(f), we present how the query
complexity scales as a function of the power law exponent of the demand distribution.
in computational complexity as α increases is observed in Fig. 2(e). With respect to the query
complexity shown in Fig. 2(d), W ORCS -I exhibits a unimodal curve. In fact, while a large α
∆
leads to a greater number of balls in the 8(α+1)
-cover (increases the query complexity in line 8
of Algorithm 1), it results in smaller balls and therefore a smaller version space in the next iteration (reduces the query complexity as in line 11 of Algorithm 1). This explains the unimodal
behavior of the curve of W ORCS -I. Other algorithms exhibit a general positive correlation with
α, as a larger α tends to induce a more unbalanced division of the version space.
Impact of Demand Distribution Finally, we explore impact of demand distribution. We
used the Iris dataset and varied the exponent of the power law distribution from 10−1 to 102 .
Query complexity of different algorithms is shown in Fig. 2(f). We observe that algorithms are
generally robust to the change of the parameter of the power law demand distribution.

6

Conclusion

In this paper, we studied the problem of interactive learning though pairwise comparisons. We
introduced a new weak oracle model to handle noisy situations, under which the oracle answers
only when it is sure of the answer. We also considered the problem of comparison-based search
via our weak oracle. We proposed two algorithms where they require different levels of knowledge about the distances or rankings between objects. We guaranteed the performance of these
algorithms based on a measure of intrinsic dimensionality for the distribution of points in the
underling metric space. Finally, we compared our algorithms with several baseline algorithms

14

on real datasets. Note that we assumed the oracle is non-malicious and when it is not confident,
it answers with “?”. Although this model is robust to high levels of uncertainty, but considering
the effect of erroneous answers from the weak oracle is interesting for future work.
Acknowledgement Amin Karbasi is supported by DARPA Young Faculty Award (D16AP00046)
and AFOSR Young Investigator Award (FA9550-18-1-0160). Ehsan Kazemi is supported by
Swiss National Science Foundation (Early Postdoc.Mobility) under grant number 168574.

References
Maria-Florina Balcan, Alina Beygelzimer, and John Langford. Agnostic active learning. J.
Comput. Syst. Sci., 75(1):78–89, 2009.
Maria-Florina Balcan, Ellen Vitercik, and Colin White. Learning combinatorial functions from
pairwise comparisons. In Proceedings of the 29th Conference on Learning Theory, COLT
2016, New York, USA, June 23-26, 2016, pages 310–335, 2016.
Xi Chen, Paul N Bennett, Kevyn Collins-Thompson, and Eric Horvitz. Pairwise ranking aggregation in a crowdsourced setting. In Proceedings of the sixth ACM international conference
on Web search and data mining, pages 193–202. ACM, 2013.
Kenneth L Clarkson. Nearest-neighbor searching and metric space dimensions. Nearestneighbor methods for learning and vision: theory and practice, pages 15–59, 2006.
Thomas M Cover and Joy A Thomas. Elements of information theory. John Wiley & Sons,
2012.
Nilesh Dalvi, Anirban Dasgupta, Ravi Kumar, and Vibhor Rastogi. Aggregating crowdsourced
binary ratings. In Proceedings of the 22nd international conference on World Wide Web,
pages 285–294. ACM, 2013.
Sanjoy Dasgupta. Analysis of a greedy active learning strategy. In NIPS, volume 17, pages
337–344, 2004.
Sanjoy Dasgupta. Coarse sample complexity bounds for active learning. In Advances in Neural Information Processing Systems, December 5-8, 2005, Vancouver, British Columbia,
Canada], pages 235–242, 2005.
Brian Eriksson. Learning to top-k search using pairwise comparisons. In Proceedings of the
Sixteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2013,
Scottsdale, AZ, USA, April 29 - May 1, 2013, pages 265–273, 2013.
Donatella Firmani, Barna Saha, and Divesh Srivastava. Online entity resolution using an oracle.
Proceedings of the VLDB Endowment, 9(5):384–395, 2016.
M Forina et al. An extendible package for data exploration, classification and correlation.
Institute of Pharmaceutical and Food Analisys and Technologies, Via Brigata Salerno, 16147,
1991.
Daniel Golovin and Andreas Krause. Adaptive submodularity: Theory and applications in
active learning and stochastic optimization. J. Artif. Intell. Res. (JAIR), 42:427–486, 2011.

15

Navin Goyal, Yury Lifshits, and Hinrich Schütze. Disorder inequality: A combinatorial approach to nearest neighbor search. In Proceedings of the 2008 International Conference on
Web Search and Data Mining, WSDM ’08, pages 25–32, New York, NY, USA, 2008. ACM.
Anupam Gupta, Robert Krauthgamer, and James R Lee. Bounded geometries, fractals, and
low-distortion embeddings. In Foundations of Computer Science, 2003. Proceedings. 44th
Annual IEEE Symposium on, pages 534–543. IEEE, 2003.
Siavash Haghiri, Debarghya Ghoshdastidar, and Ulrike von Luxburg. Comparison-based nearest neighbor search. In Artificial Intelligence and Statistics, 2017.
Sariel Har-Peled and Nirman Kumar. Approximate nearest neighbor search for low-dimensional
queries. SIAM Journal on Computing, 42(1):138–159, 2013.
F Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. ACM
Transactions on Interactive Intelligent Systems (TiiS), 5(4):19, 2016.
Trevor Hastie and Robert Tibshirani. Classification by pairwise coupling. In Advances in Neural Information Processing Systems 10, [NIPS Conference, Denver, Colorado, USA, 1997],
pages 507–513, 1997.
Reinhard Heckel, Nihar B Shah, Kannan Ramchandran, and Martin J Wainwright. Active ranking from pairwise comparisons and the futility of parametric assumptions. arXiv preprint
arXiv:1606.08842, 2016.
Kirsten Hildrum, John D Kubiatowicz, Satish Rao, and Ben Y Zhao. Distributed object location
in a dynamic network. Theory of Computing Systems, 37(3):405–440, 2004.
Sheng-Jun Huang, Rong Jin, and Zhi-Hua Zhou. Active learning by querying informative and
representative examples. In Advances in neural information processing systems, pages 892–
900, 2010.
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse
of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of
computing, pages 604–613. ACM, 1998.
Panagiotis G Ipeirotis, Foster Provost, and Jing Wang. Quality management on amazon mechanical turk. In Proceedings of the ACM SIGKDD workshop on human computation, pages
64–67. ACM, 2010.
Amin Karbasi, Stratis Ioannidis, and Laurent Massoulié. Content search through comparisons.
In Automata, Languages and Programming - 38th International Colloquium, ICALP 2011,
Zurich, Switzerland, July 4-8, 2011, Proceedings, Part II, pages 601–612, 2011.
Amin Karbasi, Stratis Ioannidis, and Laurent Massoulié. Comparison-Based Learning with
Rank Nets. In Proceedings of the 29th International Conference on Machine Learning, ICML
2012, Edinburgh, Scotland, UK, June 26 - July 1, 2012, 2012a.
Amin Karbasi, Stratis Ioannidis, and Laurent Massoulié. Hot or not: Interactive content search
using comparisons. In Information Theory and Applications Workshop (ITA), 2012, pages
291–297. IEEE, 2012b.
David R Karger and Matthias Ruhl. Finding nearest neighbors in growth-restricted metrics.
In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages
741–750. ACM, 2002.
16

Richard M Karp and Robert Kleinberg. Noisy binary search and its applications. In Proceedings
of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 881–890.
Society for Industrial and Applied Mathematics, 2007.
Robert Krauthgamer and James R Lee. Navigating nets: simple algorithms for proximity search.
In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages
798–807. Society for Industrial and Applied Mathematics, 2004.
Yury Lifshits and Shengyu Zhang. Combinatorial algorithms for nearest neighbors, nearduplicates and small-world design. In Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 318–326. Society for Industrial and Applied Mathematics, 2009.
Lucas Maystre and Matthias Grossglauser. Fast and accurate inference of plackett–luce models.
In Advances in Neural Information Processing Systems, pages 172–180, 2015.
Lucas Maystre and Matthias Grossglauser. Just Sort It! A Simple and Effective Approach to
Active Preference Learning. In Proceedings of the 34th International Conference on Machine
Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, pages 2344–2353, 2017.
Robert D. Nowak. Noisy generalized binary search. In Advances in Neural Information Processing Systems, pages 1366–1374, 2009.
Li Qian, Jinyang Gao, and HV Jagadish. Learning user preferences by adaptive pairwise comparison. Proceedings of the VLDB Endowment, 8(11):1322–1333, 2015.
P. Ram and A. G. Gray. Which space partitioning tree to use for search? In Proceedings of the
26th International Conference on Neural Information Processing Systems, NIPS’13, pages
656–664, USA, 2013.
Matthew J Salganik and Karen EC Levy. Wiki surveys: Open and quantifiable social data
collection. PloS one, 10(5):e0123483, 2015.
Burr Settles. Active learning literature survey. University of Wisconsin, Madison, 52(55-66):
11, 2010.
Neil Stewart, Gordon DA Brown, and Nick Chater. Absolute identification by relative judgment.
Psychological review, 112(4):881, 2005.
Omer Tamuz, Ce Liu, Serge J. Belongie, Ohad Shamir, and Adam Kalai. Adaptively learning
the crowd kernel. In Proceedings of the 28th International Conference on Machine Learning,
ICML 2011, Bellevue, Washington, USA, June 28 - July 2, 2011, pages 673–680, 2011.
Louis L Thurstone. The method of paired comparisons for social values. The Journal of Abnormal and Social Psychology, 21(4):384, 1927.
Dominique Tschopp, Suhas Diggavi, Payam Delgosha, and Soheil Mohajer. Randomized algorithms for comparison-based search. In Advances in Neural Information Processing Systems,
pages 2231–2239, 2011.
Dominique Tschopp, Suhas Diggavi, and Matthias Grossglauser. Hierarchical routing over
dynamic wireless networks. Random Structures & Algorithms, 47(4):669–709, 2015.

17

Catherine Wah, Grant Van Horn, Steve Branson, Subhransu Maji, Pietro Perona, and Serge
Belongie. Similarity comparisons for interactive fine-grained categorization. In Proceedings
of the IEEE Conference on Computer Vision and Pattern Recognition, pages 859–866, 2014.
Jialei Wang, Nathan Srebro, and James Evans. Active collaborative permutation learning. In
Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery
and data mining, pages 502–511. ACM, 2014.
Jiannan Wang, Tim Kraska, Michael J Franklin, and Jianhua Feng. Crowder: Crowdsourcing
entity resolution. Proceedings of the VLDB Endowment, 5(11):1483–1494, 2012.
Jiannan Wang, Guoliang Li, Tim Kraska, Michael J Franklin, and Jianhua Feng. Leveraging
transitive relations for crowdsourced joins. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pages 229–240. ACM, 2013.
Fabian L Wauthier, Michael I Jordan, and Nebojsa Jojic. Efficient ranking from pairwise comparisons. ICML (3), 28:109–117, 2013.
Yan Yan, Glenn M Fung, Rómer Rosales, and Jennifer G Dy. Active learning from crowds.
In Proceedings of the 28th international conference on machine learning (ICML-11), pages
1161–1168, 2011.
Fang Zhou, Q Claire, and Ross D King. Predicting the geographical origin of music. In Data
Mining (ICDM), 2014 IEEE International Conference on, pages 1115–1120. IEEE, 2014.

18

