Low-dimensional Data Embedding via Robust Ranking
Ehsan Amid

Nikos Vlassis

Manfred K. Warmuth

University of California,
Santa Cruz, CA 95064
eamid@ucsc.edu

Adobe Research
San Jose, CA 95113
vlassis@adobe.com

University of California,
Santa Cruz, CA 95064
manfred@ucsc.edu

arXiv:1611.09957v2 [] 16 May 2017

ABSTRACT
We describe a new method called t-ETE for finding a low-dimensional
embedding of a set of objects in Euclidean space. We formulate the
embedding problem as a joint ranking problem over a set of triplets,
where each triplet captures the relative similarities between three
objects in the set. By exploiting recent advances in robust ranking, t-ETE produces high-quality embeddings even in the presence
of a significant amount of noise and better preserves local scale
than known methods, such as t-STE and t-SNE. In particular, our
method produces significantly better results than t-SNE on signature datasets while also being faster to compute.

KEYWORDS
Ranking, Triplet Embedding, Robust Losses, t-Exponential Distribution, Dimensionality Reduction, t-SNE.

1

INTRODUCTION

Learning a metric embedding for a set of objects based on relative
similarities is a central problem in human computation and crowdsourcing. The application domain includes a variety of different
fields such as recommender systems and psychological questionnaires. The relative similarities are usually provided in the form
of triplets, where a triplet (i, j, k) expresses that “object i is more
similar to object j than to object k”, for which the similarity function may be unknown or not even quantified. The first object i
is referred to as the query object and objects j and k are the test
objects. The triplets are typically gathered by human evaluators via
a data-collecting mechanism such as Amazon Mechanical Turk1 .
These types of constraints have also been used as side information
in semi-supervised metric learning [4, 8] and clustering [2].
Given a set of relative similarity comparisons on a set of objects,
the goal of triplet embedding is to find a representation for the
objects in some metric space such that the constraints induced
by the triplets are satisfied as much as possible. In other words,
the embedding should reflect the underlying similarity function
from which the constraints were generated. Earlier methods for
triplet embedding include Generalized Non-metric Multidimensional Scaling (GNMDS) [1], Crowd Kernel Learning (CKL) [14],
and Stochastic Triplet Embedding (STE) and extension, t-distributed
STE (t-STE) [15].
One major drawback of the previous methods for triplet embedding is that their performance can drop significantly when a small
amount of noise is introduced in the data. The noise may arise due
to different reasons. For instance, each human evaluator may use
a different similarity function when comparing objects [3]. As a
result, there might exist conflicting triplets with reversed test objects. Another type of noise could be due to the insufficient degree
1 https://www.mturk.com

of freedom when mapping an intrinsically (and possibly hidden)
high-dimensional representation to a lower-dimensional embedding. A simple example is mapping uniformly distributed points
on a two-dimensional circle to a one-dimensional line; regardless
of the embedding, the end points of line will always violate some
similarity constraints.
In this paper, we cast the triplet embedding problem as a joint
ranking problem. In any embedding, for each object i, the remaining
object are naturally ranked by their “distance” to i. The triplet
(i, j, k) expresses that the object j should be ranked higher than
object k for the ranking of i. Therefore, triplet embedding can be
viewed as mapping the objects into a Euclidean space so that the
joint rankings belonging to all query objects are as consistent (with
respect to the triplets) as possible. In order to find the embedding,
we define a loss for each triplet and minimize the sum of losses
over all triplets. Initially our triplet loss is unbounded. However in
order to make our method robust to noise, we apply a novel robust
transformation (using the generalized log function), which caps the
triplet loss by a constant. Our new method, t-Exponential Triplet
Embedding (t-ETE)2 , inherits the heavy-tail properties of t-STE
in producing high-quality embeddings, while being significantly
more robust to noise than any other method. Figure 1 illustrates
examples of embeddings of a subset of 6000 data points from the
MNIST dataset using t-STE and our proposed method. The triplets
are synthetically generated by sampling a random point from one
of the 20-nearest neighbors for each point and another point from
those that are located far away (100 triplets for each point). The two
embeddings are very similar when there is no noise in the triplets
(Figures 1(a) and 1(b)). However, after ‘reversing’ 20% of the triplets,
t-STE fails to produce a meaningful embedding (Figure 1(c)) while
t-ETE is almost unaffected by the noise (Figure 1(d)).
We also apply our t-ETE method to dimensionality reduction
and develop a new technique, which samples a subset of triplets in
the high-dimensional space and finds the low-dimensional representation that satisfies the corresponding ranking. We quantify the
importance of each triplet by a non-negative weight. We show that
even a small carefully chosen subset of triplets capture sufficient information about the local as well as the global structure of the data
to produce high-quality embeddings. Our proposed method outperforms the commonly used t-SNE [9] for dimensionality reduction
in many cases while having a much lower complexity.

2

TRIPLET EMBEDDING VIA RANKING

In this section we formally define the triplet embedding problem.
Let I = {1, 2, . . . , N } denote a set of objects. Suppose that the feature (metric) representation of these objects is unknown. However,
2 The

acronym t-STE is based on the Student-t distribution. Here, “t” is part of the
name of the distribution. Our method, t -ETE, is based on t -exponential family. Here,
t is a parameter of the model.

Ehsan Amid, Nikos Vlassis, and Manfred K. Warmuth

t-STE - Clean Triplets

t-ETE - Clean Triplets

t-STE - Noisy Triplets

t-ETE - Noisy Triplets

(b)

(c)

(d)

0
1
2
3
4
5
6
7
8
9

(a)

Figure 1: Experiments on the MNIST dataset: noise-free triplets using (a) t-STE, and (b) t-ETE, and triplets with 20% noise using
(c) t-STE, and (d) the proposed t-ETE.
some information about the relative similarities of these objects is
available in the form of triplets. A triplet (i, j, k) is an ordered tuple
which represents a constraint on the relative similarities of the objects i, j, and k, of the type “object i is more similar to object j than
to object k.” Let T = {(i, j, k)} denote the set of triplets available
for the set of objects I.
Given the set of triplets T , the triplet embedding problem amounts
to finding a metric representation of the objects, Y = {y1 , y2 , . . . , yN },
such that the similarity constraints imposed by the triplets are
satisfied as much as possible by a given distance function in the
embedding. For instance, in the case of Euclidean distance, we want
(i, j, k) =⇒ kyi − yj k < kyi − yk k , w.h.p.

(1)

The reason that we may not require all the constraints to be satisfied
in the embedding is that there may exist inconsistent and/or conflicting constraints among the set of triplets. This is a very common
phenomenon when the triplets are collected via human evaluators
via crowdsourcing [3, 16].
We can consider the triplet embedding problem as a ranking
problem imposed by the set of constraints T . More specifically,
each triplet (i, j, k) can be seen as a partial ranking result where for
a query over i, we are given two results, namely j and k, and the
triplet constraint specifies that “the result j should have relatively
higher rank than k”. In this setting, only the order of closeness
of test objects to the query object determines the ranking of the
objects.
Let us define `i jk (Y) ∈ [0, ∞) to be non-negative loss associated
with the triplet constraint (i, j, k). To reflect the ranking constraint,
the loss `i jk (Y) should be a monotonically increasing (decreasing)
function of the pairwise distance kyi − yj k (kyi − yk k). These
properties ensure that `i jk (Y) → 0 whenever kyi − yj k → 0 and
kyi − yk k → ∞. We can now define the triplet embedding problem
as minimizing the sum of the ranking losses of the triplets in T ,
that is,
Õ
min L T ,
Y

`i jk (Y) .

LT =

(2)

(i, j,k)∈ T

In the above formulation, the individual loss of each triplet is unbounded. This means that in cases where a subset of the constraints

are corrupted by noise, the loss of even a single inconsistent triplet
may dominate the total objective (2) and result in a poor performance. In order to avoid such effect, we introduce a new robust
transformation to cap the individual loss of each triplet from above
by a constant. As we will see, the capping helps to avoid the noisy
triplets and produce high-quality embeddings, even in the presence
of a significant amount of noise.

3

ROBUST LOSS TRANSFORMATIONS

We first introduce the generalized logt and expt functions as the
generalization of the standard log and exp functions, respectively.
The generalized logt function with temperature parameter 0 < t < 2
is defined as [10, 12]
(
log(x)
if t = 1
logt (x) =
.
(3)
(x 1−t − 1)/(1 − t) otherwise
Note that logt is concave and non-decreasing and generalizes the
log function which is recovered in the limit t → 1. The expt function is defined as the inverse of logt function.
(
exp(x)
if t = 1
expt (x) =
,
(4)
1/(1−t )
[1 + (1 − t)x]+
otherwise
where [ · ]+ = max(0, ·). Similarly, the standard exp is recovered in
the limit t → 1. Figure 2(a) and 2(b) illustrate the expt and logt
functions for several values of t.
One major difference with the standard exp and log functions
is that the familiar distributive properties do not hold in general:
expt (a b) , expt (a) expt (b) and logt (a b) , logt (a) + logt (b). An
important property of expt is that it decays to zero slower than exp
for values of 1 < t < 2. This motivates defining heavy-tailed distributions using the expt function. More specifically, the t-exponential
family of distributions is defined as a generalization of the exponential family by using the expt function in place of the standard
exp function [11, 13].
Our main focus is the capping property of the logt function: for
values x > 1, the logt function with t > 1 grows slower than the
log function and reaches the constant value 1/(t − 1) in the limit

Low-dimensional Data Embedding via Robust Ranking
expt
t!0
t = 0.5
t=1
t = 1.5

Algorithm 1 Weighted t-ETE Dimensionality Reduction

logt

7
6

Input: high-dimensional data X = {x1 , x2 , . . . , xn },
temperatures t and t 0 , embedding dimension d
Output: Y = {y1 , y2 , . . . , yn }, where yi ∈ Rd

2

5
1

- T ← {}, W ← {}
for i = 1 to n do
for j ∈ {m-nearest neighbors of i} do
- sample k unif. from {k : kxi − xk k > kxi − xj k}
- compute weight ωi jk using (13)
- T ← T ∪ (i, j, k)
- W ← W ∪ ωi jk
end for
end for
- for all ω ∈ W: ω ← maxωω W + γ

4
0

3

-3

-2

-1

2

-1

1

-2

0

1

2

3

1

2

3

4

-3

x

x

(a)

(b)

Figure 2: Generalized exp and log functions: (a) expt function,
and (b) logt function for different values of 0 < t < 2. Note
that for t = 1, the two functions reduce to standard exp and
log functions, respectively.

- initialize Y to n points in Rd
sampled from N (0, 10−3 Id ×d )
for r = 1 to iter# do
- calculate the gradient ∇C W, T of (12)
- update Y ← Y − η∇C W, T
end for

x → ∞. This idea can be used to define the following robust loss
transformation on the non-negative unbounded loss `:
ρ t (`) = logt (1 + `),

1 < t < 2.

(5)

Note that ρ t (0) = 0, as desired. Moreover, the derivative of the
transformed loss ρ t0 (`) → 0 as ` → ∞ along with the additional
property that the loss function converges to a constant as ` → ∞,
i.e., ρ t (`) → 1/(t − 1) ≥ 0. We will use this transformation to
develop a robust ranking approach for the problem of the triplet
embedding in presence of noise in the set of constraints.
Finally, note that setting t = 1 yields the transformation
ρ 1 (`) = log(1 + `) ,

(6)

which has been used for robust binary ranking in [17]. Note that
ρ 1 (`) grows slower than `, but still ρ 1 (`) → ∞ as ` → ∞. In other
words, the transformed loss will not be capped from above. We will
show that this transformation is not sufficient for robustness to
noise.

4 T -EXPONENTIAL TRIPLET EMBEDDING
Building on our discussion on the heavy-tailed properties of generalized exp function (4), we can define the ratio
expt 0 (−kyi − yk k 2 )
`i jk (Y) =
expt 0 (−kyi − yj k 2 )
(t 0 )

(7)

with 1 <
< 2 as the loss of the ranking associated with the
triplet (i, j, k). The loss is non-negative and satisfies the properties
of a valid loss for ranking, as discussed earlier. Note that due to
heavy-tail of expt 0 function with 1 < t 0 < 2, the loss function (7)
encourages relatively higher-satisfaction of the ranking compared
to, e.g., standard exp function.
Defining the loss of each triplet (i, j, k) ∈ T as the ranking loss
in (7), we formulate the objective of the triplet embedding problem
as minimizing the sum of robust transformations of individual
losses, that is,


Õ
0
min C T , C T =
logt 1 + `i(tjk) (Y) ,
(8)

in which, 1 < t < 2. We call our method t-Exponential Triplet
Embedding (t-ETE, for short). Note that the loss of each triplet in the
summation is now capped from above by 1/(t − 1). Additionally, the
gradient of the objective function (8) with respect to the positions
of the objects Y
Õ
0
1
(9)
∇`i(tjk) (Y)
∇C T =
(t 0 )
t
(i, j,k )∈T (1 + `i jk (Y))
includes additional forgetting factors 1/(1 + `i(tjk) (Y))t that damp the
effect of those triplets that are highly-unsatisfied.
0

5

CONNECTION TO PREVIOUS METHODS

Note that by setting t = 1, we can use the property of the log function log(a) = − log(1/a) to write the objective (8) as the following
equivalent maximization problem3
Õ
0
log pi(tjk) ,
(10)
max
Y

where
0

pi(tjk) =

t0

Y

(i, j,k )∈ T

(i, j,k)∈T

expt 0 (−kyi − yj k 2 )
expt 0 (−kyi − yj k 2 ) + expt 0 (−kyi − yk k 2 )

(11)

is defined as the probability that the triplet (i, j, k) is satisfied. Setting t 0 = 1 and t 0 = 2 recovers the STE and t-STE (with α = 1)
formulations, respectively4 . STE (and t-STE) aim to maximize the
joint probability that the triplets T are satisfied in the embedding
Y. The poor performance of STE and t-STE in presence of noise
can be explained by the fact that there is no capping of the logsatisfaction probabilities5 of each triplet (see (6)). Therefore, the
3 Note

that logt (a) , − logt (1/a) in general.
Student-t distribution with α degrees of freedom can be written in form of a
t -exponential distribution with −(α + 1)/2 = 1/(1 − t ) (see [5]).
5 Note that in this case, the probabilities should be capped from below.

4 The

Ehsan Amid, Nikos Vlassis, and Manfred K. Warmuth

0.95

0.7

0.6

0.5

0.4

0.3

0.2

0.9
0.8

Nearest Neighbor Accuracy

0.8

0.1

MNIST Digits

MNIST Digits
1

Generalization Accuracy

Nearest Neighbor Error

MNIST Digits
0.9

0.9
0.85
0.8
0.75
0.7
0.65
0.6

5

10

15

20

0.5

25

0.6
0.5
0.4
0.3
0.2
0.1

0.55

0

0.7

0

0.1

Number of Dimensions

0.2

0.3

0.4

0

0.5

0

0.1

MIT Scenes

MIT Scenes

0.75

0.2

0.3

0.4

0.5

0.4

0.5

Noise Level

Noise Level

MIT Scenes

1

0.6

0.6

0.55

0.5

0.45

Nearest Neighbor Accuracy

Generalization Accuracy

Nearest Neighbor Error

0.7

0.65

0.9

0.8

0.7

0.6

0.5

0.4

0.35

0

5

10

15

20

25

Number of Dimensions

(a)

(b)

30

0.4

0

0.1

0.2

0.3

Noise Level

(c)

0.4

0.5

0.5

0.4

0.3

0.2

0.1

0

0

0.1

0.2

0.3

Noise Level

(d)

Figure 3: Generalization and nearest-neighbor performance: MNIST (top row) and MIT Scenes (bottom row). (a) Generalization
error, (b) nearest-neighbor error, (c) generalization accuracy in presence of noise, and (d) nearest-neighbor accuracy in presence
of noise. For all the experiments, we use t = t 0 . For the generalization and nearest-neighbor error experiments, we start with
t = 2 and use a smaller t as the number of dimensions increases (more degree of freedom). For the noise experiments, we set
t = 1.7. Figures best viewed in color.
low satisfaction probabilities of a the noisy triplet dominates the
objective function (10) and thus, results in poor performance.

6

APPLICATIONS TO DIMENSIONALITY
REDUCTION

Now, consider the case where a high-dimensional representation
n is provided for a set of n objects. Having the t-ETE
X = {xi }i=1
method in hand, one may ask the following question: “given the
high-dimensional representation X for the objects, is it possible
to find a lower-dimensional representation Y for these objects
by satisfying a set of ranking constraints (i.e., triplets), formed
based on their relative similarities in the representation X?”. Note
that the total number of triplets that can be formed on a set of
n objects is O(n 3 ) and trying to satisfy all the possible triplets
is computationally expensive. However, we argue that most of
the these triplets are redundant and contain the same amount of
information about the relative similarity of the objects. For instance,
consider two triplets (i, j, k) and (i, j, k 0 ) in which i and k are located
far away and k and k 0 are neighbors of each other. Given (i, j, k),
having (i, j, k 0 ) provides no extra information on the placements
of i and j, as long as k and k 0 are located close together in the

embedding. In other words, k and k 0 are viewed by i as almost
being the same object.
Note that for each object i, the nearby objects having relatively
short distance to i specify the local structure of the object, whereas
those that are located far away determine the global placement of
i in the space. For that matter, for each query object i, we would
like to consider those triplets (with high probability) that preserve
both local and global structure of the data. Following the discussion
above, we emphasize on preserving the local information by explicitly choosing the first test object among the nearest-neighbors of
the query object i. The global information of the object i is then
preserved by considering a small number of objects, uniformly
sampled from those that are located farther away. This leads to the
following procedure for sampling a set of informative triplets. For
each object i, we choose the first object from the set of m-nearest
neighbors of i and then, sample the outlier object uniformly from
those that are located farther away from i than the first object. This
is equivalent to sampling a triplet uniformly at random conditioned
on that the first test object is chosen among the m-nearest neighbors of i. We use equal number of nearest-neighbors and outliers
for each point, which results in nm2 triplets in total.

Low-dimensional Data Embedding via Robust Ranking

(a)

(b)

Figure 4: Embedding of the Food dataset using (a) t-STE, and t-ETE (t = 2) methods. There appear no clear separation between
the clusters in (a) while in (b), three different clusters of food are evident: “Vegetables and Meals” (top), “Ice creams and Deserts”
(bottom left), and “Breads and Cookies” (bottom right).
The original t-ETE formulation aims to satisfy each triplet equally
likely. This would be reasonable in cases where no side information
about the extent of each constraint is provided. However, given the
high-dimensional representation of the objects X, this assumption
may not be accurate. In other words, the ratio of the pairwise similarities of the objects specified in each triplet may vary significantly
among the triplets. To account for this variation, we can introduce a
notion of weight for each triplet to reflect the extent that the triplet
needs to be satisfied. More formally, let ωi jk ≥ 0 denote the weight
associated with the triplet (i, j, k) and let W = {ωi jk } denote the
set of all triplet weights. The Weighted t-ETE can be formulated as
minimizing the sum of weighted capped losses of triplets, that is,
min C W, T ,
Y

C W, T =

Õ



0
ωi jk logt 1 + `i(tjk) (Y) .

(12)

(i, j,k )∈ T

The t-ETE method can be seen as a special case of the weighted
triplet embedding formulation where all the triplets have unit
weights.
Finally, to assign weights to the sampled triplets, we note that
the loss ratio in (7) is inversely proportional to how well the triplet
is satisfied in the embedding. This suggests using the inverse loss
ratios of the triplets in the high-dimensional space as the weights
associated with the triplets. More formally, we set
ωi jk =

exp(−kxi − xj k 2 /σi2j )
2 )
exp(−kxi − xk k 2 /σik

,

(13)

where σi2j = σi σ j is a constant scaling factor for the pair (i, j).
We set σi to the distance of i to its 10-th nearest neighbor. This
choice of scaling adaptively handles the dense as well as the sparse
regions of data distribution. Finally, the choice of exp function
rather than using expt 0 with 1 < t 0 < 2 is to have more emphasis
on the distances of the objects in the high-dimensional space. The
pseudo-code for the algorithm is shown in Algorithm 1. In practice,
dividing each weight at the end by the maximum weight in W and
adding a constant positive bias γ > 0 to all weight improves the
results.
Note that both sampling and weighting the triplets using (13) and
calculating the gradient of loss requires calculating the pairwise distances only between O(nm2 ) objects in the high-dimensional space
(for instance, by using efficient methods to calculate m-nearest
neighbors such as [7]) or the low-dimensional embedding. In many
cases, m 2  n, which results in a huge computational advantage
over O(n 2 ) complexity of t-SNE.

7

EXPERIMENTS

In this section, we conduct experiments to evaluate the performance
of t-ETE for triplet embedding as well the application of Weighted
t-ETE for non-linear dimensionality reduction. In the first set of
experiments, we compare t-ETE to the following triplet embedding
methods: 1) GNMDS, 2) CKL, 3) STE, and 4) t-STE. We evaluate the
generalization performance of the different methods by means of
satisfying unseen triplets and the nearest-neighbor error, as well as
their robustness to constraint noise. We also provide visualization

Ehsan Amid, Nikos Vlassis, and Manfred K. Warmuth

Backstreet Boys

rock
metal
pop
dance
hiphop
jazz
country
reggae
other

*NSync

LFO

112

Britney Spears
Big Star

Christina
Aguilera
Jessica Simpson
Mya
Jennifer Paige
Toni Braxton

Violent Femmes

Eric ClaptonMark Knopfler
Dire Straits
Nazareth

Billy Joel

Bette
Cher Midler
Alanis Morissette
Bonnie Tyler
Stevie Nicks
Sarah McLachlan
Fleetwood
Mac
Alan Jackson
Dido Toby Keith
Billy Ray Cyrus
The Corrs
Lifehouse
Luniz
Fiona
Apple
Kenny Chesney
Whiskeytown
Pretenders
Cranberries
Nelly
Furtado
SixpenceGarden
None the Richer
LeAnn Rimes
Olivia Newton-John
Savage
DebelahDeana
Morgan
Shania
TwainCarter
ABBA Ace of Base
Dixie
Chicks
Miles Davis
Aqua
Faith Hill
Vertical
Horizon
Supertramp
Chumbawamba
Dave Matthews Band
Chicago
Beeand
Gees
KC
TheRafferty
Sunshine Band
Gerry
S Club
7
Samantha
Mumba
Santana
Huey LewisBBMak
& The News
Culture Club
Everclear
Roxette
Third
Eye Blind
Rednex
The
Cardigans
Spin
Doctors
Our
Lady Peace
Barenaked
Ben Folds Five
Oleander
Sly & The Family Stone
Edwin
McCainLadies
3 Doors Down
Wheatus
Enya
Men at Work
Eiffel 65O-Town
Jessica
Andrews
Vengaboys Sade
Mr. Big
Enigma
Marc Anthony
Twista
D'Angelo
New Radicals
3LW
La Bouche
Milli
VanilliIce
Tracy Chapman
Xzibit
Vanilla
Eros Ramazzotti
Mike Oldfield
Ricky Martin
Counting Crows
Sugar Ray
Clash
Lou Bega Enrique Iglesias
Brian
Wilson
Sting
The
Beach BoysThe Police
Liz Phair
Smash
Mouth
"Weird
Al" Yankovic
Rick Astley
Neil Young
Rockapella
CAKE
Bob Dylan
Aaron Carter
Moby
Sugar
Q-Tip
Dr. Octagon
Anouk
Ani DiFranco
Michael
OutKast
George
Michael
Prince Jackson
Wu-Tang
Clan
Spineshank
Marvin
StevieGaye
Wonder
Bryan Adams
Blackstreet
DMX
Busta
Rhymes
Coolio
Hill
Everything but the Girl
Bloodhound
GangCypress
Al Green
The
Offspring
Seal
Steve
Winwood
Chemical
Brothers
Van
Morrison
Uriah
Heep
Lenny Kravitz
Daft
Punk
Propellerheads
Prodigy
Basement
Jaxx
Rancid
Paul van
Dyk
Ice Dre
Cube
Dr.
Richard
Marx Barry White
Beck
Mystikal
Rod
Stewart
Gorillaz Alice DeeJay
Blind Melon
Coal Chamber
LLMatthew
Cool
JDMC
The
Presidents
of the United States of America
Madison
Avenue
Sweet
Fatboy
Slim
Run
Pennywise
Beastie
Boys
blink-182
Elvis
Costello
Goldfinger
MxPx
Nine Days
Green Day
Paul
Simon
311
Incubus
Simon
& Garfunkel
Lionel
Richie
House of Pain
The
Kids
Don McLean
Nick Drake
MeGet
FirstUp
and
the Gimme Gimmes
Crowded House
Live
John Lennon
Everlast
The Beatles
Fuel
Tubby
Portishead
Blessid Union of Souls
Carly
Simon Cross
Sneaker King
Pimps
Christopher
Phil
Collins
Genesis
Peter
Gabriel
Stereophonics
Seven Mary No
Three
Ludacris Juvenile
Doubt
PJ
Harvey
Garbage
Neil Diamond

Cat Stevens
Elton John

Paula
AbdulCarey
Mariah
Madonna
Janet
Jackson
Selena
Cyndi Lauper
Tricky
Belinda Carlisle
Bangles
Pat Benatar
Blondie
Heart
Wilson Phillips
Whitney Houston
CélineG
Dion
Kenny
Natalie Imbruglia
Sheryl Crow
Garth Brooks
Tim McGraw

New
Order
Erasure
Depeche
Mode

Westlife

Melissa Etheridge
Bruce Springsteen

Eurythmics
Annie Lennox

The
Human
League
Fine
Young
Cannibals
Soft
Cell
Spandau
Ballet

Joe Cocker
Tom Petty
Melissa Etheridge
Bruce Springsteen Ron Sexsmith
Aretha
Franklin
Donna
Summer

Joe Cocker
Tom Petty

En Vogue
Lucy
Pearl

Culture Beat
Alphaville Twins
Thompson
Simple
Minds
a-ha
Pet Shop Boys
Billy Idol

Spice Girls
Melanie C
Mark Knopfler
Eric Clapton
Dire Straits
Nazareth

Gary Wright U2 INXS

Sublime
Ja Rule
Joe
Nelly
UB40
Shaggy
Bob Marley

Bobby Vee
Neil Sedaka

Kenny
Loggins
John
Denver

Weezer
Fastball

Pink Floyd
R.E.M.

Tears for Fears
Duran Duran

Led Zeppelin

The Rolling Stones

The Verve
Oasis

Blur
New Found Glory
The Cure
Craig
David

Missy Elliott

Coldplay

Tina Turner
Janis Joplin
The Jimi Hendrix
The Doors Cream
Experience

Aaliyah
TLC

Pink
Placebo

AllGabrielle
Saints

Lauryn
Hill Sisqó
Wyclef
FugeesJean
Usher
Montell
Dru
Hill Jordan

Stroke 9
Bob Seger
Semisonic
Alice
in Chains
Les Rythmes
Digitales
Temple
of the
Dog
Goo
Goo Dolls
The Smashing Pumpkins
Soul Asylum
Stone Evan
Temple
Pilots
and
Jaron
Faith No More
Collective Soul
Nine
Inch Nails
Nirvana
Soundgarden
Foo
FilterFighters
LoveDeftones
Rage Against the Machine
Chris Isaak
Roy Orbison
Everly Brothers
Elvis Presley
Frank Sinatra

R.Air
Kelly
Supply
Keith Sweat

Nick Cave & The Bad Seeds

Bad
Brains
ToolEleven
Finger
Staind
Mudvayne Linkin Park
Talking Heads
Deep Purple Metallica
BlackOzzy
Sabbath
Osbourne
Alice
Cooper
Disturbed
Marilyn Manson
Iron Maiden
Orgy
Creedence Clearwater Revival
Papa
Roach
White
Zombie
Steppenwolf
Rammstein
Limp
Bizkit
Kid Rock
Velvet
Underground
Lynyrd Skynyrd Skid Row
Robert
Palmer
David
Bowie
Bad Company
Steve Miller Band
Procol Harum
Cheap Trick
Kiss
War
Blood, Sweat & Tears
Chic
Boston

Bad Brains
Finger Eleven

Tina Turner
Janis Joplin
The Doors

The Jimi Hendrix
Experience

Cream

Pink Floyd
R.E.M.
Radiohead
Led Zeppelin

Muse
Moody Blues
Queen
Kansas
REO
Speedwagon
Survivor
Styx

Tool

Toto
Foreigner

Ugly Kid Joe
Queensrÿche
Def Leppard
Extreme
Bon Jovi
Poison
Tesla

Scorpions
ZZ Top
AC/DC
VanAerosmith
Halen

Scorpions

Metallica
Black Sabbath

OzzyAlice
Osbourne
Cooper

ZZ Top
AC/DC

Van Halen

Aerosmith

Iron Maiden

Figure 5: Results of the t-ETE algorithm (t = 2) on the Music dataset: compare the result with the one in [15]. The neighborhood
structure is more meaningful in some regions than the one with t-STE.
results on two real-world datasets. Next, we apply the Weighted tETE method for non-linear dimensionality reduction and compare
the result to the t-SNE method. The code for the (Weighted) t-ETE
method as well as all the experiments will be publicly available
upon acceptance.

7.1

Generalization and Nearest-Neighbor Error

We first evaluate the performance of different methods by means of
generalization to unseen triplets as well as preserving the nearestneighbor similarity. For this part of experiments, we consider the
MNIST Digits 6 (1000 subsamples) and MIT Scenes 7 (800 subsamples) datasets. The synthetic triplets are generated as mentioned
earlier (100 triplets per point). To evaluate the generalization performance, we perform a 10-fold cross validation and report the fraction
of held-out triplets that are unsatisfied as a function of number of
dimension. This quantity indicates how well the method learns
the underlying structure of the data. Additionally, we calculate the
nearest-neighbor error as a function of number of dimensions. The
nearest-neighbor error is a measure of how well the embedding
captures the pairwise similarity of the objects based on relative
6 http://yann.lecun.com/exdb/mnist/
7 http://people.csail.mit.edu/torralba/code/spatialenvelope/

comparisons. The results are shown in Figure 3(a)-3(b). As can be
seen, t-ETE performs as good as the best performing method or
even better on both generalization and nearest-neighbor error. This
indicates that t-ETE successfully captures the underlying structure
of the data and scales properly with the number of dimensions.

7.2

Robustness to Noise

Next, we evaluate the robustness of the different methods to triplet
noise. To evaluate the performance, we generate a different test set
for both datasets with the same number of triplets as the training set.
For each noise level, we randomly subsample a subset of training
triplets and reverse the order of the objects. After generating the
embedding, we evaluate the performance on the test set and report
the fraction of the test triplets that are satisfied as well as the nearestneighbor accuracy. The results are shown in Figure 3(c)-3(d). As
can be seen, the performance of all the other methods starts to drop
immediately when only a small amount of noise is added to the data.
On the other hand, t-ETE is very robust to triplet noise such that
the performance is almost unaffected for up to 15% of noise. This
verifies that t-ETE can be effectively applied to real-world datasets
where a large portion of the triplets may have been corrupted by
noise.

Low-dimensional Data Embedding via Robust Ranking

(a)

(b)

(c)

0
1
2
3
4
5
6
7
8
9

(e)

(d)

0
1
2
3
4
5
6
7
8
9

(f)

(g)

a
b
c
d
e

(h)

Figure 6: Dimensionality reduction results using t-SNE (top figure) and Weighted t-ETE (bottom figure) on: a) Wine, b) Sphere,
c) Swiss Roll, d) Faces, e) COIL-20, f) MNIST, g) USPS, and h) Letters datasets. We use t = t 0 = 2 in all experiments. Figures best
viewed in color.

7.3

Visualization Results

We provide visualization results on the Food [16] and Music [6]
datasets. Figures 4(a) and 4(b) illustrate the results on the Food
dataset using t-STE and t-ETE (t = 2), respectively. The same
initialization for the data points is used for the both methods. As
can be seen, no clear clusters are evident using the t-STE method.
On the other hand, t-ETE reveals three main clusters in the data:

“Vegetables and Meals” (top), “Ice creams and Deserts” (bottom left),
and “Breads and Cookies” (bottom right).
The visualization of the Music dataset using the t-ETE method
(t = 2) is shown in Figure 5. The result can be compared with the
one using the t-STE method8 . The distribution of the artists and
the neighborhood structure are similar for both methods, but more
8 Available

on homepage.tudelft.nl/19j49/ste

Ehsan Amid, Nikos Vlassis, and Manfred K. Warmuth
meaningful in some regions using the t-ETE method. This can be
due to the noise in the triplets that have been collected via human
evaluators. Additionally, t-ETE results in 0.52 nearest-neighbor
error on the data points compared to 0.63 error using t-STE.

7.4

Dimensionality Reduction Results

We apply the weighted triplet embedding method to find a 2dimensional visualization of the following datasets: 1) Wine9 , 2)
Sphere (1000 uniform samples from a surface of a three-dimensional
sphere10 ), 3) Swiss Roll (3000 sub-samples11 ), 4) Faces (400 synthetic faces with different pose and lighting11 ), 5) COIL-2012 , 6)
MNIST (10,000 sub-samples), and 7) USPS (11,000 images of handwritten digits13 ). We compare our results with those obtained using
the t-SNE method. In all experiments, we use m = 20 for our method
(for COIL-20, we use m = 10) and bias γ = 0.01. The results are
shown in Figure 6.
As can be seen, our method successfully preserves the underlying
structure of the data and produces high-quality embedding on all
datasets, both having an underlying low-dimensional manifold (e.g.,
Swiss Roll), or clusters of points (e.g., USPS). On the other hand, in
most cases, t-SNE over-emphasizes the separation of the points and
therefore, tears up the manifold. The same effect happens for the
clusters, e.g., in the USPS dataset. The embedding forms multiple
separated sub-clusters (for instance, the clusters of points ‘3’s, ‘7’s,
and ‘8’s are divided into several smaller sub-clusters). Our objective
function also enjoys better convergence properties and converges
to a good solution using simple gradient descent. This eliminates
the need for more complex optimization tricks such as momentum
and early over-emphasis, used in t-SNE.

8

CONCLUSION

We introduced a ranking approach for embedding a set of objects
in a low-dimensional space, given a set of relative similarity constraints in the form of triplets. We showed that our method, t-ETE,
is robust to high level of noise in the triplets. We generalized our
method to a weighted version to incorporate the importance of
each triplet. We applied our weighted triplet embedding method
to develop a new dimensionality reduction technique, which outperforms the commonly used t-SNE method in many cases while
having a lower complexity and better convergence behavior.

REFERENCES
[1] Sameer Agarwal, Josh Wills, Lawrence Cayton, Gert Lanckriet, David Kriegman,
and Serge Belongie. 2007. Generalized Non-metric Multidimensional Scaling. In
Proceedings of the Eleventh International Conference on Artificial Intelligence and
Statistics. San Juan, Puerto Rico.
[2] Ehsan Amid, Aristides Gionis, and Antti Ukkonen. 2015. A kernel-learning
approach to semi-supervised clustering with relative distance comparisons. In
Joint European Conference on Machine Learning and Knowledge Discovery in
Databases. Springer, 219–234.
[3] Ehsan Amid and Antti Ukkonen. 2015. Multiview Triplet Embedding: Learning
Attributes in Multiple Maps. In Proceedings of the 32nd International Conference
on Machine Learning (ICML-15). 1472–1480. http://jmlr.org/proceedings/papers/
v37/amid15.pdf
9 UCI

repository.

10 research.cs.aalto.fi/pml/software/dredviz/
11 web.mit.edu/cocosci/isomap/datasets.html
12 www1.cs.columbia.edu/CAVE/software/softlib/coil-20.php
13 www.cs.nyu.edu/~roweis/data.html

[4] Jason V Davis, Brian Kulis, Prateek Jain, Suvrit Sra, and Inderjit S Dhillon. 2007.
Information-theoretic metric learning. In Proceedings of the 24th international
conference on Machine learning. ACM, 209–216.
[5] Nan Ding and S. V. N. Vishwanathan. 2010. t -Logistic Regression. In Proceedings
of the 23th International Conference on Neural Information Processing Systems
(NIPS’10). Cambridge, MA, USA, 514–522.
[6] Daniel P. W. Ellis, Brian Whitman, Adam Berenzweig, and Steve Lawrence. 2002.
The Quest for Ground Truth in Musical Artist Similarity. In Proceedings of the
3rd International Conference on Music Information Retrieval (ISMIR ’02). Paris,
France, 170–177.
[7] Ville Hyvönen, Teemu Pitkänen, Sotiris Tasoulis, Elias Jääsaari, Risto Tuomainen,
Liang Wang, Jukka Corander, and Teemu Roos. 2015. Fast k-nn search. arXiv
preprint arXiv:1509.06957 (2015).
[8] Eric Yi Liu, Zhishan Guo, Xiang Zhang, Vladimir Jojic, and Wei Wang. 2012.
Metric learning from relative comparisons by minimizing squared residual. In
2012 IEEE 12th International Conference on Data Mining. IEEE, 978–983.
[9] Laurens van der Maaten and Geoffrey Hinton. 2008. Visualizing data using t-SNE.
Journal of Machine Learning Research 9, Nov (2008), 2579–2605.
[10] Jan Naudts. 2002. Deformed exponentials and logarithms in generalized thermostatistics. Physica A 316 (2002), 323–334. http://arxiv.org/pdf/cond-mat/0203489
[11] Jan Naudts. 2004. Estimators, escort probabilities, and phi-exponential families
in statistical physics. Journal of Inequalities in Pure and Applied Mathematics 5, 4
(2004), 102.
[12] Jan Naudts. 2004. Generalized thermostatistics based on deformed exponential
and logarithmic functions. Physica A 340 (2004), 32–40.
[13] Timothy Sears. 2010. Generalized Maximum Entropy, Convexity and Machine
Learning. Ph.D. Dissertation. The Australian National University.
[14] Omer Tamuz, Ce Liu, Serge Belongie, Ohad Shamir, and Adam T. Kalai. 2011.
Adaptively Learning the Crowd Kernel. In Proceedings of the 28th International
Conference on Machine Learning (ICML-11).
[15] L. van der Maaten and K. Weinberger. 2012. Stochastic triplet embedding. In
2012 IEEE International Workshop on Machine Learning for Signal Processing. 1–6.
DOI:http://dx.doi.org/10.1109/MLSP.2012.6349720
[16] Michael Wilber, Sam Kwak, and Serge Belongie. 2014. Cost-Effective HITs for
Relative Similarity Comparisons. In Human Computation and Crowdsourcing
(HCOMP). Pittsburgh.
[17] Hyokun Yun, Parameswaran Raman, and S. V. N. Vishwanathan. 2014. Ranking
via Robust Binary Classification. In Proceedings of the 27th International Conference on Neural Information Processing Systems (NIPS’14). Cambridge, MA, USA,
2582–2590. http://dl.acm.org/citation.cfm?id=2969033.2969115

