# Talk Through It: End User Directed Manipulation Learning

Carl Winge, Adam Imdieke, Bahaa Aldeeb, Dongyeop Kang, Karthik Desingh C.
Winge, A. Imdieke, B. Aldeeb, D. Kang, and K. Desingh are with the Minnesota
Robotics Institute, University of Minnesota, Twin Cities, Minneapolis, USA
{winge134, imdie022, baldeeb, dongyeop<EMAIL_ADDRESS>
###### Abstract

Training generalist robot agents is an immensely difficult feat due to the
requirement to perform a huge range of tasks in many different environments.
We propose selectively training robots based on end-user preferences instead.

Given a factory model that lets an end user instruct a robot to perform lower-
level actions (e.g. ‘Move left’), we show that end users can collect
demonstrations using language to train their home model for higher-level tasks
specific to their needs (e.g. ‘Open the top drawer and put the block inside’).
We demonstrate this hierarchical robot learning framework on robot
manipulation tasks using RLBench environments. Our method results in a 16%
improvement in skill success rates compared to a baseline method.

In further experiments, we explore the use of the large vision-language model
(VLM), Bard, to automatically break down tasks into sequences of lower-level
instructions, aiming to bypass end-user involvement. The VLM is unable to
break tasks down to our lowest level, but does achieve good results breaking
high-level tasks into mid-level skills. We have a supplemental video and
additional results at talk-through-it.github.io.

##  I INTRODUCTION

Interactive devices such as Siri, Alexa, and Google Home have brought AI into
the home, but the prospect of having embodied AI manipulating household
objects remains out of reach. Home robots will require personalization and
adaptation to their specific environments to carry out tasks. We believe that
it will be the end users who actively imbue the domestic robots with skills
and behaviors pertinent to the tasks they intend their robots to assist with,
thus necessitating the development of robot learning frameworks centered
around end users.

We involve end users in robot manipulation learning by decomposing it into two
steps: creating a factory model and creating a home model, as shown in Figure
1. We envision a user receiving a robot programmed with a factory model which
endows it with primitive capabilities, allowing it to follow basic
instructions such as “move right”, “close the gripper”, or “move above the
green jar”. The end user would bootstrap off of these capabilities to direct
the robot’s factory model to evolve into a personalized home model. By
instructing the robot through more complex skills such as “sweep the dust into
the dustpan”, or “open the top drawer”, the user can teach the robot to follow
more complex instructions.

Figure 1: A level-1 factory model is trained with a diverse set of primitive
action commands. End users train the robot in their homes to complete the
tasks they care about by using the level-1 commands to collect demonstrations.
We call this the home model.

Learning from demonstration provides an accessible method of robot training
through behavior cloning. Our work presents a framework to collect
demonstrations by leveraging actions already learned by a robot agent. We show
that we can train a robot to perform primitive actions and then use those
actions to abstract away low-level control. Using natural language, we
instruct our robot through skill and task demonstrations that we use to train
the robot and expand its capabilities.

We include experiments using a large vision-language model (VLM) to see
whether it can replace a human breaking down tasks for a robot. While the VLM
can break a task into skills, it cannot break skills into primitive actions.
We quantitatively show that end user directed robot learning is still
necessary to close the domain gap between low-level reasoning (grounded on the
current scene and task) and high-level reasoning (common knowledge).

Through this work, we present an end user directed hierarchical robot learning
framework, leveraging natural language for communication.

  * •

We present a method for training a robot to respond to observation-dependent
and observation-independent language commands for primitive actions.

  * •

We show language commands for primitive actions can be used in sequence to
collect demonstrations for training higher-level skills and tasks. This
technique allows non-expert end users to train a robot according to their
personal needs.

  * •

Our results prove that our hierarchical training method leads to performance
gains over a state-of-the-art baseline method which doesn’t utilize
hierarchical training.

  * •

We demonstrate a VLM can successfully chain skills learned by our model to
complete longer-horizon tasks.

##  II RELATED WORK

Our work entails robot manipulation learning from end-user demonstrations in a
hierarchical fashion. In this section, we list related work in the areas of
learning from demonstrations, demonstration data acquisition, and reasoning
via large vision-language models.

###  II-A Learning from Demonstrations

Behavior cloning (BC) has garnered significant attention when it comes to
robot manipulation task learning from demonstrations [1, 2, 3, 4]. For our
proposed framework, we require the policy to be both capable of learning
various skills and sample efficient when it comes to training. BC models such
as BC-Z [2] and MOO [5] are designed to output robot end-effector states based
on expert demonstrations. RT-2 [1] leveraged vision language models (VLMs)
that generate text containing end-effector pose. While such methods
demonstrated impressive success rates, they required prohibitively large
amounts of demonstration data.

To address the data collection bottleneck, Wang et al. [6] proposed using
videos of human play to augment the training process. Recording the human play
data is fast, but they still require data collection using robot teleoperation
to transfer the skills to their robot. Shridhar et al. proposed PerAct [3],
which demonstrated high accuracy and sample efficiency. The PerAct
architecture is suitable for our purposes because it is sample efficient and
leverages the RLBench [7] simulation environment, which includes many
benchmark manipulation tasks.

###  II-B Demonstration Data Acquisition

BC models require expert demonstrations. However, the tools used for
interfacing with robots are not particularly user-friendly. Teleoperation
using joysticks or other controllers is commonly used to control the robot’s
end-effector [6], with some leveraging VR [2, 8] to facilitate the data
collection process. ALOHA [9] presented the idea of using a twin robot for the
target robot to mimic. While these teleoperation techniques have become more
intuitive, they still require expensive equipment that can be difficult to set
up. Furthermore, a recent user study from Mahadevan et al. [10] shows that it
is easier for users to control a robot when they can command meaningful
actions instead of directly controlling the robot motion. In our work, we
focus on exposing the robot’s controls to a non-expert end user via natural
language. Specifically, the factory model is trained on expert demonstrations,
and home models are trained using demonstration data collected via natural
language.

With the progress of large language models and large vision-language models,
language is becoming the go-to method for task specification. Language is
mostly used to expose the robot’s learned skills to an end user [3, 11, 12].
Lynch et al. [13] bridge the gap between teleoperation and task execution by
allowing users to control the robot through speech in real-time. However,
unlike our method, their methods do not use language to collect
demonstrations.

###  II-C Reasoning via Large Vision-Language Models:

Pre-trained large language models (LLMs) [14, 15] have demonstrated impressive
reasoning, prompting a new generation of LLM-based Vision-Language Models
(VLMs) that extend LLMs to allow reasoning over visual contexts [12, 1]. These
VLMs demonstrate the ability to describe visual scenes and answer questions
about them, as well as control robots [12]. Given a prompt describing a
situation and intention, these VLMs demonstrated the ability to reason over
tasks [12] and integrate feedback from their environments [11, 16]. We utilize
the publicly available Bard model [17] in our VLM experiments.

##  III Framework

###  III-A Framework Architecture

Our network architecture consists of an observation-dependent, and an
observation-independent model, as shown in Figure 2. The command classifier
determines which model to use for a given text command. Both models take in a
text instruction and output a robot action. The observation-dependent model
takes in RGB-D images in addition to the text instruction. This architecture
applies to the factory model and the home model illustrated in Figure 3. The
home model is a factory model trained on more observation-dependent commands;
there is no change to the model architecture.

(a) If the command classifier determines a command is observation-independent,
the observation-independent model uses the text embedding to output a robot
action, as shown above.

(b) If the command classifier determines a command is observation-dependent,
the observation-dependent model uses the text embedding and the current image
observations to output a robot action, as shown above.

Figure 2: Our architecture includes a command classifier which determines
whether to run an observation-dependent or observation-independent model. The
factory model and home model include both models. The observation-dependent
model is fine-tuned in the home model. Figure 3: The Level-1 factory model is
trained on scripted demonstrations to perform primitive actions from language
commands. An end user trains the robot to perform Level-2 skills in their home
by using the Level-1 action commands to collect demonstrations of desired
skills. They can then train Level-3 tasks by utilizing Level-1 action commands
and Level-2 skill commands to collect demonstrations of desired tasks. These
demonstrations collected by the end user only use natural language; no
programming or special hardware is required. Different end users may choose to
train different skills and tasks according to their needs.

The observation-independent model is a multi-layer perceptron that regresses
$\Delta$x, $\Delta$y, $\Delta$z, $\Delta$roll, $\Delta$pitch, $\Delta$yaw, and
gripper state (open or close) from a CLIP [18] embedding of the text
instruction. The model also takes the previous output as input to maintain the
previous gripper state. We train using a set of labeled commands. For example,
“move left” is a 10cm move in the negative x direction, and “rotate clockwise”
is a 90-degree roll. Some of these commands and labels are shown in Appendix
Table VIII.

The observation-dependent model is PerAct [3] with minor modifications. This
model has a preprocessing stage, which converts the RGB-D images into a voxel
representation. We elected to reduce the voxel dimensions to
50$\times$50$\times$50 from 100$\times$100$\times$100 to save computation,
enabling us to run more experiments in a shorter time. Note that our
architecture is modular and hence any advancements in feature embedding and
efficient observation-dependent models can be integrated easily.

###  III-B Model Levels

The Level-1 model (aka factory model) is trained on primitive motions
demonstrated by a scripted expert. In our experiments, these are scripted
trajectories from the RLBench environment. The primitive motions include both
observation-independent commands (e.g. ‘Move a little right’), and
observation-dependent commands (e.g. ‘Move above the block’). Level-2 and
Level-3 are skill and task models, respectively, trained by end users via
language-commanded demonstrations. The skills model includes things like
picking and placing an object, or pushing an object to a specified location.
The tasks model includes things that require repeating a skill or combining
multiple skills. Tasks include repeating a pick and place to stack multiple
objects or pulling a drawer open, then putting a block in the drawer. Refer to
the Figure 3 where the Level-1 model is the factory model and Level-2 and
beyond are home models.

###  III-C Environments

We selected 14 RLBench tasks, which are a subset of the 18 tasks evaluated in
PerAct. Each voxel in our model is 2cm wide, which makes high precision tasks
more difficult. Therefore, we eliminated the tasks of screwing in a light
bulb, sorting shapes in a shape sorter, placing a ring on a peg, and hanging
mugs on a mug tree because they require very high precision. To avoid
confusion, we refer to the 14 RLBench tasks as environments. Some of the
RLBench tasks are actually skills according to our definitions. Each
environment is used to train Level-1 motions, and Level-2 skills. Some
environments are also used to train Level-3 tasks.

###  III-D Level-1 Factory Model

The basis of our approach is training a Level-1 model on demonstrations of
primitive motions. The demonstrations for Level-1 all consist of a single
robot motion. We created primitive action demonstrations for each RLBench
environment. For example, the open drawer environment has 3 primitive actions:
“move in front of the top handle,” “move in front of the middle handle,” and
“move in front of the bottom handle.” The factory model is trained with 1400
scripted demonstrations covering primitive motions across all the
environments. In practice, these scripted demonstrations will be replaced by
expert demonstrations in the factory setting.

###  III-E Collecting Demonstrations with Language

Once the factory model is trained, we no longer need any scripted
demonstrations. Demonstrations for more complex skills and tasks are collected
using only language instructions typed by the user. Figure 4 shows a
demonstration of the Level-1 language commands used to sweep dirt into a
dustpan. The keyframes are labeled by the user during the language-driven
demonstration so it can be used to train this skill.

Figure 4: Primitive motion (Level-1) commands are used to collect a skill
(Level-2) demonstration of sweeping dust into the large dustpan.

###  III-F Home Model Training

Once the user collects a few demonstrations of a skill or task they desire the
robot to learn, they can have the factory model fine-tune these demonstrations
to create their home models (in our case Level-2 and Level-3). Different users
may care more about different tasks and only fine-tune for a few of the many
possible tasks the robot could learn.

##  IV Experiments & Results

In this section, we discuss the details of our experimental setups, and the
results of each experiment. For all experiments, model weights are saved after
every 5000 steps of training. Every saved weight is evaluated on 25 unseen
rollouts of each skill or task the model was trained on. The evaluation
episodes are seeded so they initialize repeatably. The best weight from the
evaluation is then tested on another set of rollouts. The test episodes are
seeded to ensure they are different than the evaluation episodes.

The first experiment determines how well the factory model learns to complete
primitive actions. We follow that with a language augmentation experiment to
see if we can train a factory model that is robust to paraphrased inputs.

Next, we compare Level-2 home models with a baseline Level-2 model. The home
models include a multi-skill model, and single-skill models. As part of our
Level-2 analysis, we test the Level-2 multi-skill model with Level-1 action
commands. We want to make sure the model doesn’t forget earlier levels.

We then compare Level-3 home models with a baseline Level-3 model. The home
models include a multi-skill model, and single-skill models.

Last, we experiment with a VLM to see if we can avoid having a human collect
demonstrations. We try using the VLM to break down Level-2 skills into Level-1
primitive action commands, and to break down Level-3 tasks into Level-2 skill
commands.

###  IV-A Learning Level-1 Primitive Actions

For primitive actions, success is determined by the robot end effector
reaching within 2.5cm of the target position. The model is given up to 5
action predictions to reach the target position. On average, the robot reaches
the correct location 87% of the time. This Level-1 model is a strong
foundation for collecting demonstrations for higher-level models via language.

###  IV-B Language Augmentation

We can’t expect end users to give commands identical to those we used. In
order to test variations in language, we created 6 total paraphrases of the
Level-1 action instructions. We refer to these as variations
$i={0,1,2,3,4,5}$. We use a Level-1 model that was only trained on variation
$i=0$ as the default model. We compare it to a Level-1 model that was trained
on variations $i=0,1,2,3$. Variations $i=4,5$ were not seen by either model.
Variation $i=4$ uses a novel combination of words, but all the individual
words were seen in variations $i=0,1,2,3$. Variation $i=5$ includes at least
one word that was not seen in any of the other variations.

The augmented model shows an 8% improvement in success rate compared to the
default model on both test variations, shown in Table I. The success rate is
averaged across all the motion commands in all 14 RLBench environments. This
shows a model trained on more language variations is more likely to succeed
when given paraphrased language commands not seen in training.

Model | Variation 4 | Variation 5
---|---|---
Default | 76 | 75
Augmented | 84 | 83
TABLE I: Comparison between a default Level-1 model trained with no language
variation, and an augmented Level-1 model trained with 4 language variations.
Variation 4 and variation 5 were not seen by either model during training.

###  IV-C Baseline Models

We create baseline models for Level-2 and Level-3 using a more traditional
approach. We generate 10 demos for each skill using scripted waypoints in
RLBench. Then we train a model on the scripted demos for 100,000 steps. The
key differences are that our method trains the model with Level-1 demos first,
and our method uses Level-2 demos collected with language instead of using
scripted waypoints. The same is true for the Level-3 baseline; it is trained
on 10 demos for each task using scripted waypoints.

###  IV-D Learning Level-2 Skills from Level-1 Actions

From our 14 RLBench environments, we define 14 Level-2 skills and 4 Level-3
tasks. The skills are listed in Table III. The tasks build on the skills. For
example, put in drawer includes the skills of open drawer, and put in drawer.

We train two types of Level-2 models - a) multi-skill model and b) single-
skill model. We envision that an end user would want to train for a subset of
the possible skills, so we experiment to understand the performance when all
skills are learned at the same time vs. single skills. We use 10 demos for
each skill to train these models. The training starts with the Level-1 weights
and fine-tunes for 100,000 steps. During the fine-tuning, each batch samples
three times from the Level-1 dataset and once from the Level-2 dataset. This
sampling prevents the model from forgetting Level-1 actions. We find that the
Level-2 model achieves an average success rate 7% higher than the Level-1
model when tested on Level-1 actions, as shown in Table II, meaning it
improves rather than forgets.

Model | Average Success Rate on Level-1 Actions
---|---
Level-1 | 87
Level-2 | 94
TABLE II: We test the Level-2 model on Level-1 actions to determine whether it
is forgetting Level-1 commands. Rather than forgetting, it shows improvement
over the Level-1 model.

The multi-skill and single-skill models are evaluated every 5000 steps on 25
episodes of the skills. The models that perform best on the validation
episodes are used for testing, once again on 25 episodes per skill. Our method
produces a multi-skill model that achieves an average success rate of 39%
compared to the baseline of 23%, as seen in Table III. We believe many
important features for learning a skill are learned from the Level-1 actions
model. In the open drawer skill, the Level-1 model already learned the
concepts of top, middle, and bottom from Level-1. In the push buttons skill,
the Level-1 model already learned the 18 button color variations. Table IV
shows that performance is higher when a model is trained on a single skill
instead of many skills, demonstrating that models trained for specific use
cases are better than more generalist models.

Model | Average | Open Drawer | Slide Block | Sweep to Dustpan | Meat Off Grill | Turn Tap | Put in Drawer Lv2
---|---|---|---|---|---|---|---
Ours 5 demos | 30$\pm$2 | 79$\pm$6 | 24$\pm$8 | 33$\pm$22 | 5$\pm$2 | 52$\pm$8 | 60$\pm$16
Ours 10 demos | 39$\pm$2 | 79$\pm$6 | 40$\pm$4 | 68$\pm$11 | 15$\pm$15 | 51$\pm$14 | 84$\pm$7
Baseline 10 demos | 23$\pm$3 | 49$\pm$9 | 43$\pm$5 | 23$\pm$21 | 41$\pm$2 | 8$\pm$7 | 44$\pm$31
Close Jar | Drag Stick | Stack Blocks Lv2 | Put in Safe | Place Wine | Put in Cupboard | Push Buttons Lv2 | Stack Cups Lv2
13$\pm$2 | 56$\pm$7 | 5$\pm$5 | 3$\pm$2 | 7$\pm$2 | 0 | 73$\pm$6 | 8$\pm$4
28$\pm$7 | 51$\pm$27 | 9$\pm$5 | 16$\pm$7 | 8$\pm$7 | 0 | 79$\pm$10 | 15$\pm$2
3$\pm$2 | 24$\pm$7 | 7$\pm$6 | 21$\pm$6 | 23$\pm$8 | 0 | 24$\pm$11 | 9$\pm$5
TABLE III: Success rates for the multi-skill Level-2 model compared to a baseline. Success rates are the mean and standard deviation from tests on 3 models initialized randomly before training. Average | Open Drawer | Slide Block | Sweep to Dustpan | Meat Off Grill | Turn Tap | Put in Drawer Lv2 | Close Jar
---|---|---|---|---|---|---|---
50 | 84 | 60 | 80 | 36 | 68 | 92 | 32
Drag Stick | Stack Blocks Lv2 | Put in Safe | Place Wine | Put in Cupboard | Push Buttons Lv2 | Stack Cups Lv2 |
80 | 4 | 28 | 32 | 0 | 80 | 20 |
TABLE IV: Success rates for Level-2 models fine-tuned for a single skill

###  IV-E Learning Level-3 Tasks from Level-1 & 2

To learn Level-3 tasks, we fine-tune for 100,000 steps with Level-3 demos on
the best Level-2 models. Fine-tuning here means each batch takes 2 samples
from Level-1, 1 sample from Level-2, and 1 sample from Level-3. We train
single-task and multi-task models, and the results are shown in Tables V and
VI. The baseline multi-task model achieves an average success rate of 10%,
whereas our multi-task model achieves 23% using the same number of Level-3
demos. Even our multi-task model trained on only 5 Level-3 demos achieves a 7%
better success rate than the baseline. Curiously, our model trained on 5 demos
appears to beat the more thoroughly trained models on the stack blocks task,
but we attribute that result to chance and deem it statistically
insignificant.

Model | Average | Put in Drawer | Stack Blocks | Push Buttons | Stack Cups
---|---|---|---|---|---
Ours 5 demos | 17$\pm$2 | 28$\pm$11 | 3$\pm$5 | 39$\pm$6 | 0
Ours 10 demos | 23$\pm$6 | 40$\pm$8 | 0 | 53$\pm$17 | 0
Baseline 10 demos | 10$\pm$2 | 0 | 0 | 39$\pm$9 | 0
TABLE V: Success rates for Level-3 tasks with multi-task models. Success rates are the mean and standard deviation from tests on 3 models initialized randomly before training. Demos | Average | Put in Drawer | Stack Blocks | Push Buttons | Stack Cups
---|---|---|---|---|---
5 demos | 25 | 40 | 4 | 56 | 0
10 demos | 24 | 36 | 0 | 56 | 4
TABLE VI: Success rates for Level-3 models fine-tuned for a single task

###  IV-F Using Large Vision-Language Models

Inspired by PaLM-E [12], which demonstrated the application of pre-trained
LLM-based VLMs to control downstream primitive policies, we explore utilizing
VLM-generated lower-level instructions to complete higher-level skills or
tasks. We use Bard (version 2023.10.30) as it is the most advanced VLM
accessible at the time of this work, but GPT4 [19] or other VLMs could be
substituted. We prompt Google’s Bard [14] with a list of possible actions and
an image containing a front view and a gripper view, as shown in Figure 5. We
prompt the VLM to output a description of the image, a list of past executed
actions, and whether or not the task has been successfully executed. The VLM
is then asked to state the feasibility of each potential next action and
choose the best one. This idea is similar to the idea of inner monologue [16],
where the prompt draws attention to the image and previous actions. The list
of possible actions is reduced to only the relevant actions for a given task.
We observe that an off-the-shelf VLM model which has not been trained on any
manipulation tasks fails at lower-level grounded reasoning, but excels in
higher-level task planning.

In the following sections, we picture the VLM as a reasoning tool and our
Level-1 or Level-2 model as a policy function that the VLM can utilize.

VLM Reasoning over Level-1 Policy:  We first provide the VLM with a factory
model (Level-1) and observe that the VLM fails at lower-level grounded
reasoning and thus struggles to perform zero-shot tasks using the factory
model. In this experiment, the VLM is given a list of Level-1 commands to use
to complete the skill. We observe that the VLM fails to perform 3D spatial
reasoning and provides poor justification as to why it elected to perform an
action. We hypothesize that the VLM reasons at a high level, which is
corroborated by the way it describes a scene when prompted. Similarly, the VLM
was not trained to comprehend the robot’s state and tends to predict that the
robot is carrying an object even when the gripper is open. This demonstrates
the need for the user to extend the factory model to a Level-2 skill model
before attempting to leverage a VLM.

VLM Reasoning over Level-2 Policy:  We provide the VLM with a Level-2 multi-
skill model and observe that it is capable of utilizing it to achieve some
success in zero-shot task execution. The VLM is able to complete the put in
drawer and push buttons tasks. We do not attempt stack blocks or stack cups
since the provided Level-2 policy already has low success rates on the
prerequisite skills (9% and 15%, respectively).

Figure 5: The prompt template shown above is used to query the VLM for the next actions. Every action proposed is executed by the policy for 8 steps. The images are updated after every execution. Model | Average | Put in Drawer | Push Buttons
---|---|---|---
Best L3 | 48 | 40 | 56
VLM | 57.5 | 25 | 90
TABLE VII: Success rates of Level-3 single-task models compared to the VLM
using a Level-2 multi-skill policy

On average, the VLM performs better than the trained Level-3 models, as shown
in Table VII. This result suggests that the VLM can reason well over a high-
level task given a prompt. The performance was better on push buttons and
worse on put in drawer. We observe that a primary reason for the VLM’s failure
on put in drawer is that the Level-2 policy fails to open the drawer, and the
VLM fails to recognize that and does not retry.

##  V Conclusion

We present a framework that is designed for end users to train a robot to
perform a variety of skills and tasks. By providing a factory model capable of
following language instructions for primitive actions, we show longer-horizon
demonstrations can be collected using only natural language. Our hierarchical
training method produces home models that achieve a 1.7x improvement on
Level-2 skills, and a 2.3x improvement on Level-3 tasks compared to the
baseline method. We hope that the findings of this work can encourage research
toward end-user directed robot training methods.

We attempt to replace the human in the loop with a VLM, but find the VLM falls
short on low-level reasoning. The VLM lacks the spatial reasoning abilities to
make fine adjustments to the robot position to complete Level-2 skills using
Level-1 primitive action commands. The VLM shows better results using Level-2
skill commands to complete Level-3 tasks. These results show potential
benefits of coupling our system with a VLM.

One limitation of this work is the limited selection of training environments.
The factory model must be trained with data from a wide variety of tasks and
environments to function in homes. Increasing the variety of training
environments is a potential future work.

## Acknowledgements

This project is funded by the MnRI Seed Grant from the Minnesota Robotics
Institute. We thank Chahyon Ku for insightful discussions and proof reading
this paper.

## References

  * [1] A. Brohan, N. Brown, J. Carbajal, Y. Chebotar, X. Chen, K. Choromanski, T. Ding, D. Driess, A. Dubey, C. Finn, P. Florence, C. Fu, M. G. Arenas, K. Gopalakrishnan, K. Han, K. Hausman, A. Herzog, J. Hsu, B. Ichter, A. Irpan, N. Joshi, R. Julian, D. Kalashnikov, Y. Kuang, I. Leal, L. Lee, T.-W. E. Lee, S. Levine, Y. Lu, H. Michalewski, I. Mordatch, K. Pertsch, K. Rao, K. Reymann, M. Ryoo, G. Salazar, P. Sanketi, P. Sermanet, J. Singh, A. Singh, R. Soricut, H. Tran, V. Vanhoucke, Q. Vuong, A. Wahid, S. Welker, P. Wohlhart, J. Wu, F. Xia, T. Xiao, P. Xu, S. Xu, T. Yu, and B. Zitkovich, “Rt-2: Vision-language-action models transfer web knowledge to robotic control,” in arXiv preprint arXiv:2307.15818, 2023.
  * [2] E. Jang, A. Irpan, M. Khansari, D. Kappler, F. Ebert, C. Lynch, S. Levine, and C. Finn, “BC-z: Zero-shot task generalization with robotic imitation learning,” in 5th Annual Conference on Robot Learning, 2021.
  * [3] M. Shridhar, L. Manuelli, and D. Fox, “Perceiver-actor: A multi-task transformer for robotic manipulation,” in Proceedings of the 6th Conference on Robot Learning (CoRL), 2022.
  * [4] T. Gervet, Z. Xian, N. Gkanatsios, and K. Fragkiadaki, “Act3d: Infinite resolution action detection transformer for robotic manipulation,” arXiv preprint arXiv:2306.17817, 2023.
  * [5] A. Stone, T. Xiao, Y. Lu, K. Gopalakrishnan, K.-H. Lee, Q. Vuong, P. Wohlhart, S. Kirmani, B. Zitkovich, F. Xia, C. Finn, and K. Hausman, “Open-world object manipulation using pre-trained vision-language model,” in arXiv preprint, 2023.
  * [6] C. Wang, L. Fan, J. Sun, R. Zhang, L. Fei-Fei, D. Xu, Y. Zhu, and A. Anandkumar, “Mimicplay: Long-horizon imitation learning by watching human play,” arXiv preprint arXiv:2302.12422, 2023.
  * [7] S. James, Z. Ma, D. Rovick Arrojo, and A. J. Davison, “Rlbench: The robot learning benchmark & learning environment,” IEEE Robotics and Automation Letters, 2020.
  * [8] H. M. Clever, A. Handa, H. Mazhar, K. Parker, O. Shapira, Q. Wan, Y. Narang, I. Akinola, M. Cakmak, and D. Fox, “Assistive tele-op: Leveraging transformers to collect robotic task demonstrations,” 2021.
  * [9] T. Z. Zhao, V. Kumar, S. Levine, and C. Finn, “Learning fine-grained bimanual manipulation with low-cost hardware,” 2023.
  * [10] K. Mahadevan, Y. Chen, M. Cakmak, A. Tang, and T. Grossman, “Mimic: In-situ recording and re-use of demonstrations to support robot teleoperation,” in Proceedings of the 35th Annual ACM Symposium on User Interface Software and Technology, UIST ’22, (New York, NY, USA), Association for Computing Machinery, 2022.
  * [11] M. Ahn, A. Brohan, N. Brown, Y. Chebotar, O. Cortes, B. David, C. Finn, C. Fu, K. Gopalakrishnan, K. Hausman, A. Herzog, D. Ho, J. Hsu, J. Ibarz, B. Ichter, A. Irpan, E. Jang, R. J. Ruano, K. Jeffrey, S. Jesmonth, N. J. Joshi, R. Julian, D. Kalashnikov, Y. Kuang, K.-H. Lee, S. Levine, Y. Lu, L. Luu, C. Parada, P. Pastor, J. Quiambao, K. Rao, J. Rettinghouse, D. Reyes, P. Sermanet, N. Sievers, C. Tan, A. Toshev, V. Vanhoucke, F. Xia, T. Xiao, P. Xu, S. Xu, M. Yan, and A. Zeng, “Do as i can, not as i say: Grounding language in robotic affordances,” 2022.
  * [12] D. Driess, F. Xia, M. S. Sajjadi, C. Lynch, A. Chowdhery, B. Ichter, A. Wahid, J. Tompson, Q. Vuong, T. Yu, et al., “Palm-e: An embodied multimodal language model,” arXiv preprint arXiv:2303.03378, 2023.
  * [13] C. Lynch, A. Wahid, J. Tompson, T. Ding, J. Betker, R. Baruch, T. Armstrong, and P. Florence, “Interactive language: Talking to robots in real time,” 2022.
  * [14] R. Anil, A. M. Dai, O. Firat, M. Johnson, D. Lepikhin, A. Passos, S. Shakeri, E. Taropa, P. Bailey, Z. Chen, E. Chu, J. H. Clark, L. E. Shafey, Y. Huang, K. Meier-Hellstern, G. Mishra, E. Moreira, M. Omernick, K. Robinson, S. Ruder, Y. Tay, K. Xiao, Y. Xu, Y. Zhang, G. H. Abrego, J. Ahn, J. Austin, P. Barham, J. Botha, J. Bradbury, S. Brahma, K. Brooks, M. Catasta, Y. Cheng, C. Cherry, C. A. Choquette-Choo, A. Chowdhery, C. Crepy, S. Dave, M. Dehghani, S. Dev, J. Devlin, M. Díaz, N. Du, E. Dyer, V. Feinberg, F. Feng, V. Fienber, M. Freitag, X. Garcia, S. Gehrmann, L. Gonzalez, G. Gur-Ari, S. Hand, H. Hashemi, L. Hou, J. Howland, A. Hu, J. Hui, J. Hurwitz, M. Isard, A. Ittycheriah, M. Jagielski, W. Jia, K. Kenealy, M. Krikun, S. Kudugunta, C. Lan, K. Lee, B. Lee, E. Li, M. Li, W. Li, Y. Li, J. Li, H. Lim, H. Lin, Z. Liu, F. Liu, M. Maggioni, A. Mahendru, J. Maynez, V. Misra, M. Moussalem, Z. Nado, J. Nham, E. Ni, A. Nystrom, A. Parrish, M. Pellat, M. Polacek, A. Polozov, R. Pope, S. Qiao, E. Reif, B. Richter, P. Riley, A. C. Ros, A. Roy, B. Saeta, R. Samuel, R. Shelby, A. Slone, D. Smilkov, D. R. So, D. Sohn, S. Tokumine, D. Valter, V. Vasudevan, K. Vodrahalli, X. Wang, P. Wang, Z. Wang, T. Wang, J. Wieting, Y. Wu, K. Xu, Y. Xu, L. Xue, P. Yin, J. Yu, Q. Zhang, S. Zheng, C. Zheng, W. Zhou, D. Zhou, S. Petrov, and Y. Wu, “Palm 2 technical report,” 2023.
  * [15] T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al., “Language models are few-shot learners,” Advances in neural information processing systems, vol. 33, pp. 1877–1901, 2020.
  * [16] W. Huang, F. Xia, T. Xiao, H. Chan, J. Liang, P. Florence, A. Zeng, J. Tompson, I. Mordatch, Y. Chebotar, P. Sermanet, N. Brown, T. Jackson, L. Luu, S. Levine, K. Hausman, and B. Ichter, “Inner monologue: Embodied reasoning through planning with language models,” 2022.
  * [17] Google AI, “Bard, a large language model developed by Google AI.” https://www.bard.google.com, 2023.  Version 2023.10.30.
  * [18] A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, P. Mishkin, J. Clark, G. Krueger, and I. Sutskever, “Learning transferable visual models from natural language supervision,” in Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event (M. Meila and T. Zhang, eds.), vol. 139 of Proceedings of Machine Learning Research, pp. 8748–8763, PMLR, 2021.
  * [19] OpenAI, “Gpt-4 technical report,” 2023.

## Appendix

###  V-A Training Data

This section provides more information on the training of the Level-1 factory
model. Table VIII shows examples of labels for observation-independent
commands. Table IX gives the success rate breakdown of the primitive actions
in each RLBench environment. The motions for the turn tap environment have a
low success rate because the robot is trying to move directly to a grasp
position. We train a pre-grasp position for most environments, but in the turn
tap environment, the tap handles are at angles difficult to describe with
language. The actions for the put in cupboard environment also have a low
success rate. This is because the grocery items are not easy to distinguish in
our low-resolution voxel space. Some of the box shaped or cylinder shaped
items are easily confused with each other.

Command |  $\Delta$x |  $\Delta$y |  $\Delta$z |  $\Delta$roll |  $\Delta$pitch |  $\Delta$yaw | gripper
---|---|---|---|---|---|---|---
move left | -10 | 0 | 0 | 0 | 0 | 0 | 1
move a little left | -5 | 0 | 0 | 0 | 0 | 0 | 1
move a lot left | -20 | 0 | 0 | 0 | 0 | 0 | 1
move a tiny bit left | -1 | 0 | 0 | 0 | 0 | 0 | 1
move forward | 0 | 10 | 0 | 0 | 0 | 0 | 1
move up | 0 | 0 | 10 | 0 | 0 | 0 | 1
move backward and down | 0 | -10 | -10 | 0 | 0 | 0 | 1
rotate clockwise | 0 | 0 | 0 | 90 | 0 | 0 | 1
turn left | 0 | 0 | 0 | 0 | 0 | -90 | 1
turn up | 0 | 0 | 0 | 0 | -90 | 0 | 1
close the gripper | 0 | 0 | 0 | 0 | 0 | 0 | 0
TABLE VIII: Selected examples of commands and labels used to train the observation-independent model Environment |  Motions | Success Rate
---|---|---
Open Drawer |  move in front of the {top, middle, bottom} handle | 96
Slide Block |  move {in front of, behind, left of, right of} the block | 100
Sweep to Dustpan |  move in front of the broom | 100
Meat Off Grill |  move above the {steak, chicken} | 100
Turn Tap |  move to the {left, right} tap | 36
Put in Drawer |  move above the block | 92
Close Jar |  move above the {color} jar,
move above the lid | 92
Drag Stick |  move above the stick | 100
Put in Safe |  move above the money,
move in front of the {top, middle, bottom} shelf | 96
Place Wine |  move in front of the wine bottle,
move in front of the {near side, middle, far side} of the rack | 96
Put in Cupboard |  move above the {item},
move in front of the cupboard | 48
Push Buttons |  move above the {color} button | 92
Stack Cups |  move above the left edge of the {color} cup | 88
TABLE IX: Level-1 actions model success rates for 25 test episodes in each
environment

###  V-B VLM Experiment Details

This section provides examples and details of our VLM experiments. These
experiments involved prompting the VLM with task objective details, possible
actions to perform, a list of previously performed actions, and a description
of the requested output. Alongside the description, images showing the current
state of the robot are also provided. Figure 8 shows an example of a complete
prompt used in our VLM experiment. Figure 6 shows a successful use of the VLM
whereas Figure 7 shows a failure case.

Figure 6: VLM success for Put in Drawer. The VLM correctly predicts the
sequence of commands (left to right): open the bottom drawer, put the block in
the bottom drawer, move a lot left (irrelevant since the task is complete)
Figure 7: VLM failure for Put in Drawer. The VLM correctly predicts the
sequence of commands, but the Level-2 model fails to execute them correctly.
Predicted commands (left to right): open the middle drawer, put the block in
the middle drawer, move a lot left, put the block in the middle drawer.

Figure 8: Text prompt for VLM tasks. The VLM is given a prompt with the list
of possible actions, and the history of previous actions, along with a task in
each prompt. Each prompt includes the current images from the front view and
gripper view. The output of the VLM is sent to the Level-2 skills model. The
Level-2 skills model is allowed to run for 8 steps, then the VLM is prompted
with the updated images.


11institutetext: The George Washington University, Washington DC 20052
11email<EMAIL_ADDRESS>22institutetext: Saint Louis
University, St. Louis MO 63103
22email<EMAIL_ADDRESS>
# Hard negative examples are hard, but useful

Hong Xuan 11 0000-0002-4951-3363 Abby Stylianou 22 Xiaotong Liu 11 Robert
Pless 11

###### Abstract

Triplet loss is an extremely common approach to distance metric learning.
Representations of images from the same class are optimized to be mapped
closer together in an embedding space than representations of images from
different classes. Much work on triplet losses focuses on selecting the most
useful triplets of images to consider, with strategies that select dissimilar
examples from the same class or similar examples from different classes. The
consensus of previous research is that optimizing with the hardest negative
examples leads to bad training behavior. That’s a problem – these hardest
negatives are literally the cases where the distance metric fails to capture
semantic similarity. In this paper, we characterize the space of triplets and
derive why hard negatives make triplet loss training fail. We offer a simple
fix to the loss function and show that, with this fix, optimizing with hard
negative examples becomes feasible. This leads to more generalizable features,
and image retrieval results that outperform state of the art for datasets with
high intra-class variance. Code is available at:
https://github.com/littleredxh/HardNegative.git

###### Keywords:

Hard Negative, Deep Metric Learning, Triplet Loss

Figure 1: The triplet diagram plots a triplet as a dot defined by the anchor-
positive similarity $S_{ap}$ on the x-axis and the anchor-negative similarity
$S_{an}$ on the y-axis. Dots below the diagonal correspond to triplets that
are “correct”, in the sense that the same class example is closer than the
different class example. Triplets above the diagonal of the diagram are
candidates for the hard negative triplets. They are important because they
indicate locations where the semantic mapping is not yet correct. However,
previous works have typically avoided these triplets because of optimization
challenges.

##  1 Introduction

Deep metric learning optimizes an embedding function that maps semantically
similar images to relatively nearby locations and maps semantically dissimilar
images to distant locations. A number of approaches have been proposed for
this problem [4, 9, 12, 16, 17, 18, 26]. One common way to learn the mapping
is to define a loss function based on triplets of images: an anchor image, a
positive image from the same class, and a negative image from a different
class. The loss penalizes cases where the anchor is mapped closer to the
negative image than it is to the positive image.

In practice, the performance of triplet loss is highly dependent on the
triplet selection strategy. A large number of triplets are possible, but for a
large part of the optimization, most triplet candidates already have the
anchor much closer to the positive than the negative, so they are redundant.
Triplet mining refers to the process of finding useful triplets.

Inspiration comes from Neil DeGrasse Tyson, the famous American Astrophysicist
and science educator who says, while encouraging students, “In whatever you
choose to do, do it because it is hard, not because it is easy”. Directly
mapping this to our case suggests hard negative mining, where triplets include
an anchor image where the positive image from the same class is less similar
than the negative image from a different class.

Optimizing for hard negative triplets is consistent with the actual use of the
network in image retrieval (in fact, hard negative triplets are essentially
errors in the trained image mappings), and considering challenging
combinations of images has proven critical in triplet based distance metric
learning [4, 6, 8, 16, 21]. But challenges in optimizing with the hardest
negative examples are widely reported in work on deep metric learning for face
recognition, people re-identification and fine-grained visual recognition
tasks. A variety of work shows that optimizing with the hardest negative
examples for deep metric learning leads to bad local minima in the early phase
of the optimization [27, 2, 16, 22, 28, 18, 3].

A standard version of deep metric learning uses triplet loss as the
optimization function to learn the weights of a CNN to map images to a feature
vector. Very commonly, these feature vectors are normalized before computing
the similarity because this makes comparison intuitive and efficient, allowing
the similarity between feature vectors to be computed as a simple dot-product.
We consider this network to project points to the hypersphere (even though
that projection only happens during the similarity computation). We show there
are two problems in this implementation.

First, when the gradient of the loss function does not consider the
normalization to a hypersphere during the gradient backward propagation, a
large part of the gradient is lost when points are re-projected back to the
sphere, especially in the cases of triplets including nearby points. Second,
when optimizing the parameters (the weights) of the network for images from
different classes that are already mapped to similar feature points, the
gradient of the loss function may actually pull these points together instead
of separating them (the opposite of the desired behavior).

We give a systematic derivation showing when and where these challenging
triplets arise and diagram the sets of triplets where standard gradient
descent leads to bad local minima, and do a simple modification to the triplet
loss function to avoid bad optimization outcomes.

Briefly, our main contributions are to:

  * •

introduce the triplet diagram as a visualization to help systematically
characterize triplet selection strategies,

  * •

understand optimization failures through analysis of the triplet diagram,

  * •

propose a simple modification to a standard loss function to fix bad
optimization behavior with hard negative examples, and

  * •

demonstrate this modification improves current state of the art results on
datasets with high intra-class variance.

##  2 Background

Triplet loss approaches penalize the relative similarities of three examples –
two from the same class, and a third from a different class. There has been
significant effort in the deep metric learning literature to understand the
most effective sampling of informative triplets during training. Including
challenging examples from different classes (ones that are similar to the
anchor image) is an important technique to speed up the convergence rate, and
improve the clustering performance. Currently, many works are devoted to
finding such challenging examples within datasets. Hierarchical triplet loss
(HTL) [4] seeks informative triplets based on a pre-defined hierarchy of which
classes may be similar. There are also stochastic approaches [21] that sample
triplets judged to be informative based on approximate class signatures that
can be efficiently updated during training.

However, in practice, current approaches cannot focus on the hardest negative
examples, as they lead to bad local minima early on in training as reported in
[27, 16, 2, 3, 18, 22, 28]. The avoid this, authors have developed alternative
approaches, such as semi-hard triplet mining [16], which focuses on triplets
with negative examples that are almost as close to the anchor as positive
examples. Easy positive mining [27] selects only the closest anchor-positive
pairs and ensures that they are closer than nearby negative examples.

Avoiding triplets with hard negative examples remedies the problem that the
optimization often fails for these triplets. But hard negative examples are
important. The hardest negative examples are literally the cases where the
distance metric fails to capture semantic similarity, and would return nearest
neighbors of the incorrect class. Interesting datasets like CUB [24] and CAR
[10] which focus on birds and cars, respectively, have high intra-class
variance – often similar to or even larger than the inter-class variance. For
example, two images of the same species in different lighting and different
viewpoints may look quite different. And two images of different bird species
on similar branches in front of similar backgrounds may look quite similar.
These hard negative examples are the most important examples for the network
to learn discriminative features, and approaches that avoid these examples
because of optimization challenges may never achieve optimal performance.

There has been other attention on ensure that the embedding is more spread
out. A non-parametric approach [25] treats each image as a distinct class of
its own, and trains a classifier to distinguish between individual images in
order to spread feature points across the whole embedding space. In [29], the
authors proposed a spread out regularization to let local feature descriptors
fully utilize the expressive power of the space. The easy positive approach
[27] only optimizes examples that are similar, leading to more spread out
features and feature representations that seem to generalize better to unseen
data.

The next section introduces a diagram to systematically organize these triplet
selection approaches, and to explore why the hardest negative examples lead to
bad local minima.

##  3 Triplet diagram

Triplet loss is trained with triplets of images, $(x_{a},x_{p},x_{n})$, where
$x_{a}$ is an anchor image, $x_{p}$ is a positive image of the same class as
the anchor, and $x_{n}$ is a negative image of a different class. We consider
a convolution neural network, $f(\cdot)$, that embeds the images on a unit
hypersphere, $(\mathbf{f(x_{a})},\mathbf{f(x_{p})},\mathbf{f(x_{n})})$. We use
$(\mathbf{f_{a}},\mathbf{f_{p}},\mathbf{f_{n}})$ to simplify the
representation of the normalized feature vectors. When embedded on a
hypersphere, the cosine similarity is a convenient metric to measure the
similarity between anchor-positive pair
$S_{ap}=\mathbf{f_{a}^{\intercal}}\mathbf{f_{p}}$ and anchor-negative pair
$S_{an}=\mathbf{f_{a}^{\intercal}}\mathbf{f_{n}}$, and this similarity is
bounded in the range $[-1,1]$.

The triplet diagram is an approach to characterizing a given set of triplets.
Figure 1 represents each triplet as a 2D dot ($S_{ap},S_{an}$), describing how
similar the positive and negative examples are to the anchor. This diagram is
useful because the location on the diagram describes important features of the
triplet:

  * •

Hard triplets: Triplets that are not in the correct configuration, where the
anchor-positive similarity is less than the anchor-negative similarity (dots
above the $S_{an}=S_{ap}$ diagonal). Dots representing triplets in the wrong
configuration are drawn in red. Triplets that are not hard triplets we call
Easy Triplets, and are drawn in blue.

  * •

Hard negative mining: A triplet selection strategy that seeks hard triplets,
by selecting for an anchor, the most similar negative example. They are on the
top of the diagram. We circle these red dots with a blue ring and call them
hard negative triplets in the following discussion.

  * •

Semi-hard negative mining[16]: A triplet selection strategy that selects, for
an anchor, the most similar negative example which is less similar than the
corresponding positive example. In all cases, they are under $S_{an}=S_{ap}$
diagonal. We circle these blue dots with a red dashed ring.

  * •

Easy positive mining[27]: A triplet selection strategy that selects, for an
anchor, the most similar positive example. They tend to be on the right side
of the diagram because the anchor-positive similarity tends to be close to 1.
We circle these blue dots with a red ring.

  * •

Easy positive, Hard negative mining[27]: A related triplet selection strategy
that selects, for an anchor, the most similar positive example and most
similar negative example. The pink dot surrounded by a blue dashed circle
represents one such example.

##  4 Why some triplets are hard to optimize

The triplet diagram offers the ability to understand when the gradient-based
optimization of the network parameters is effective and when it fails. The
triplets are used to train a network whose loss function encourages the anchor
to be more similar to its positive example (drawn from the same class) than to
its negative example (drawn from a different class). While there are several
possible choices, we consider NCA [5] as the loss function:

$L(S_{ap},S_{an})=-log\frac{\exp{(S_{ap})}}{\exp{(S_{ap})}+\exp{(S_{an})}}$
(1)

All of the following derivations can also be done for the margin-based triplet
loss formulation used in [16]. We use the NCA-based of triplet loss because
the following gradient derivation is clear and simple. Analysis of the margin-
based loss is similar and is derived in the Appendix.

The gradient of this NCA-based triplet loss $L(S_{ap},S_{an})$ can be
decomposed into two parts: a single gradient with respect to feature vectors
$\mathbf{f_{a}}$, $\mathbf{f_{p}}$, $\mathbf{f_{n}}$:

$\Delta L=(\frac{\partial L}{\partial S_{ap}}\frac{\partial
S_{ap}}{\partial\mathbf{f_{a}}}+\frac{\partial L}{\partial
S_{an}}\frac{\partial
S_{an}}{\partial\mathbf{f_{a}}})\Delta\mathbf{f_{a}}+\frac{\partial
L}{\partial S_{ap}}\frac{\partial
S_{ap}}{\partial\mathbf{f_{p}}}\Delta\mathbf{f_{p}}+\frac{\partial L}{\partial
S_{an}}\frac{\partial S_{an}}{\partial\mathbf{f_{n}}}\Delta\mathbf{f_{n}}$ (2)

and subsequently being clear that these feature vectors respond to changes in
the model parameters (the CNN network weights), $\theta$:

$\Delta L=(\frac{\partial L}{\partial S_{ap}}\frac{\partial
S_{ap}}{\partial\mathbf{f_{a}}}+\frac{\partial L}{\partial
S_{an}}\frac{\partial
S_{an}}{\partial\mathbf{f_{a}}})\frac{\partial\mathbf{f_{a}}}{\partial\theta}\Delta\theta+\frac{\partial
L}{\partial S_{ap}}\frac{\partial
S_{ap}}{\partial\mathbf{f_{p}}}\frac{\partial\mathbf{f_{p}}}{\partial\theta}\Delta\theta+\frac{\partial
L}{\partial S_{an}}\frac{\partial
S_{an}}{\partial\mathbf{f_{n}}}\frac{\partial\mathbf{f_{n}}}{\partial\theta}\Delta\theta$
(3)

The gradient optimization only affects the feature embedding through
variations in $\theta$, but we first highlight problems with hypersphere
embedding assuming that the optimization could directly affect the embedding
locations without considering the gradient effect caused by $\theta$. To do
this, we derive the loss gradient, $\mathbf{g_{a}}$, $\mathbf{g_{p}}$,
$\mathbf{g_{n}}$, with respect to the feature vectors, $\mathbf{f_{a}}$,
$\mathbf{f_{p}}$, $\mathbf{f_{n}}$, and use this gradient to update the
feature locations where the error should decrease:

$\displaystyle\mathbf{f_{p}}^{new}$
$\displaystyle=\mathbf{f_{p}}-\alpha\mathbf{g_{p}}$
$\displaystyle=\mathbf{f_{p}}-\alpha\frac{\partial
L}{\partial\mathbf{f_{p}}}=\mathbf{f_{p}}+\beta\mathbf{f_{a}}$ (4)
$\displaystyle\mathbf{f_{n}}^{new}$
$\displaystyle=\mathbf{f_{n}}-\alpha\mathbf{g_{n}}$
$\displaystyle=\mathbf{f_{n}}-\alpha\frac{\partial
L}{\partial\mathbf{f_{n}}}=\mathbf{f_{n}}-\beta\mathbf{f_{a}}$ (5)
$\displaystyle\mathbf{f_{a}}^{new}$
$\displaystyle=\mathbf{f_{a}}-\alpha\mathbf{g_{a}}$
$\displaystyle=\mathbf{f_{a}}-\alpha\frac{\partial
L}{\partial\mathbf{f_{a}}}=\mathbf{f_{a}}-\beta\mathbf{f_{n}}+\beta\mathbf{f_{p}}$
(6)

where $\beta=\alpha\frac{\exp{(S_{an})}}{\exp{(S_{ap})}+\exp{(S_{an})}}$ and
$\alpha$ is the learning rate.

This gradient update has a clear geometric meaning: the positive point
$\mathbf{f_{p}}$ is encouraged to move along the direction of the vector
$\mathbf{f_{a}}$; the negative point $\mathbf{f_{n}}$ is encouraged to move
along the opposite direction of the vector $\mathbf{f_{a}}$; the anchor point
$\mathbf{f_{a}}$ is encouraged to move along the direction of the sum of
$\mathbf{f_{p}}$ and $\mathbf{-f_{n}}$. All of these are weighted by the same
weighting factor $\beta$. Then we can get the new anchor-positive similarity
and anchor-negative similarity (the complete derivation is given in the
Appendix):

$\displaystyle S_{ap}^{new}=(1+\beta^{2})S_{ap}+2\beta-\beta
S_{pn}-\beta^{2}S_{an}$ (7) $\displaystyle
S_{an}^{new}=(1+\beta^{2})S_{an}-2\beta+\beta S_{pn}-\beta^{2}S_{ap}$ (8)

The first problem is these gradients, $\mathbf{g_{a}}$, $\mathbf{g_{p}}$,
$\mathbf{g_{n}}$, have components that move them off the sphere; computing the
cosine similarity requires that we compute the norm of $\mathbf{f_{a}}^{new}$,
$\mathbf{f_{p}}^{new}$ and $\mathbf{f_{n}}^{new}$ (the derivation for these is
shown in Appendix). Given the norm of the updated feature vector, we can
calculate the similarity change after the gradient update:

$\displaystyle\Delta S_{ap}$
$\displaystyle=\frac{S_{ap}^{new}}{\|\mathbf{f_{a}}^{new}\|\|\mathbf{f_{p}}^{new}\|}-S_{ap}$
(9) $\displaystyle\Delta S_{an}$
$\displaystyle=\frac{S_{an}^{new}}{\|\mathbf{f_{a}}^{new}\|\|\mathbf{f_{n}}^{new}\|}-S_{an}$
(10)

Figure 2: Numerical simulation of how the optimization changes triplets, with
0 entanglement (left), some entanglement (middle) and complete entanglement
(right). The top row shows effects on anchor-positive similarity the bottom
row shows effects on anchor-negative similarity. The scale of the arrows
indicates the gradient strength. The top region of the bottom-middle and
bottom-right plots highlight that the hard negative triplets regions are not
well optimized with standard triplet loss.

Figure 2(left column) shows calculations of the change in the anchor-positive
similarity and the change in the anchor-negative similarity. There is an area
along the right side of the $\Delta S_{ap}$ plot (top row, left column)
highlighting locations where the anchor and positive are not strongly pulled
together. There is also a region along the top side of the $\Delta S_{an}$
plot (bottom row, left column) highlighting locations where the anchor and
negative can not be strongly separated. This behavior arises because the
gradient is pushing the feature off the hypersphere and therefore, after
normalization, the effect is lost when anchor-positive pairs or anchor-
negative pairs are close to each other.

The second problem is that the optimization can only control the feature
vectors based on the network parameters, $\theta$. Changes to $\theta$ are
likely to affect nearby points in similar ways. For example, if there is a
hard negative triplet, as defined in Section 3, where the anchor is very close
to a negative example, then changing $\theta$ to move the anchor closer to the
positive example is likely to pull the negative example along with it. We call
this effect “entanglement” and propose a simple model to capture its effect on
how the gradient update affects the similarities.

We use a scalar, $p$, and a similarity related factor $q=S_{ap}S_{an}$, to
quantify this entanglement effect. When all three examples in a triplet are
nearby to each other, both $S_{ap}$ and $S_{an}$ will be large, and therefore
$q$ will increase the entanglement effect; when either the positive or the
negative example is far away from the anchor, one of $S_{ap}$ and $S_{an}$
will be small and $q$ will reduce the entanglement effect.

The total similarity changes with entanglement will be modeled as follows:

$\displaystyle\Delta S_{ap}^{total}$ $\displaystyle=\Delta S_{ap}+pq\Delta
S_{an}$ (11) $\displaystyle\Delta S_{an}^{total}$ $\displaystyle=\Delta
S_{an}+pq\Delta S_{ap}$ (12)

Figure 2(middle and right column) shows vector fields on the diagram where
$S_{ap}$ and $S_{an}$ will move based on the gradient of their loss function.
It highlights the region along right side of the plots where that anchor and
positive examples become less similar ($\Delta S_{ap}^{total}<0$), and the
region along top side of the plots where that anchor and negative examples
become more similar ($\Delta S_{an}^{total}>0$) for different parameters of
the entanglement.

When the entanglement increases, the problem gets worse; more anchor-negative
pairs are in a region where they are pushed to be more similar, and more
anchor-positive pairs are in a region where they are pushed to be less
similar. The anchor-positive behavior is less problematic because the effect
stops while the triplet is still in a good configuration (with the positive
closer to the anchor than the negative), while the anchor-negative has not
limit and pushes the anchor and negative to be completely similar.

The plots predict the potential movement for triplets on the triplet diagram.
We will verify this prediction in the Section 6.

#### Local minima caused by hard negative triplets

In Figure 2, the top region indicates that hard negative triplets with very
high anchor-negative similarity get pushed towards (1,1). Because, in that
region, $S_{an}$ will move upward to 1 and $S_{ap}$ will move right to 1. The
result of the motion is that a network cannot effectively separate the anchor-
negative pairs and instead pushes all features together. This problem was
described in [27, 16, 2, 3, 18, 22, 28] as bad local minima of the
optimization.

#### When will hard triplets appear

During triplet loss training, a mini-batch of images is samples random
examples from numerous classes. This means that for every image in a batch,
there are many possible negative examples, but a smaller number of possible
positive examples. In datasets with low intra-class variance and high inter-
class variance, an anchor image is less likely to be more similar to its
hardest negative example than its random positive example, resulting in more
easy triplets.

However, in datasets with relatively higher intra-class variance and lower
inter-class variance, an anchor image is more likely to be more similar to its
hardest negative example than its random positive example, and form hard
triplets. Even after several epochs of training, it’s difficult to cluster
instances from same class with extremely high intra-class variance tightly.

##  5 Modification to triplet loss

Our solution for the challenge with hard negative triplets is to decouple them
into anchor-positive pairs and anchor-negative pairs, and ignore the anchor-
positive pairs, and introduce a contrastive loss that penalizes the anchor-
negative similarity. We call this Selectively Contrastive Triplet loss
$L_{SC}$, and define this as follows:

$\displaystyle L_{SC}(S_{ap},S_{an})=\begin{cases}\lambda S_{an}&\text{if
$S_{an}>S_{ap}$}\\\ L(S_{ap},S_{an})&\text{others}\end{cases}$ (13)

In most triplet loss training, anchor-positive pairs from the same class will
be always pulled to be tightly clustered. With our new loss function, the
anchor-positive pairs in triplets will not be updated, resulting in less tight
clusters for a class of instances (we discuss later how this results in more
generalizable features that are less over-fit to the training data). The
network can then ‘focus’ on directly pushing apart the hard negative examples.

We denote triplet loss with a Hard Negative mining strategy (HN), triplet loss
trained with Semi-Hard Negative mining strategy (SHN), and our Selectively
Contrastive Triplet loss with hard negative mining strategy (SCT) in the
following discussion.

Figure 3 shows four examples of triplets from the CUB200(CUB) [24] and
CAR196(CAR) [10] datasets at the very start of training, and Figure 4 shows
four examples of triplets at the end of training. The CUB dataset consists of
various classes of birds, while the CAR196 dataset consists of different
classes of cars. In both of the example triplet figures, the left column shows
a positive example, the second column shows the anchor image, and then we show
the hard negative example selected with SCT and SHN approach.

At the beginning of training (Figure 3), both the positive and negative
examples appear somewhat random, with little semantic similarity. This is
consistent with its initialization from a pretrained model trained on
ImageNet, which contains classes such as birds and cars – images of birds all
produce feature vectors that point in generally the same direction in the
embedding space, and likewise for images of cars.

Figure 4 shows that the model trained with SCT approach has truly hard
negative examples – ones that even as humans are difficult to distinguish. The
negative examples in the model trained with SHN approach, on the other hand,
remain quite random. This may be because when the network was initialized,
these anchor-negative pairs were accidentally very similar (very hard
negatives) and were never included in the semi-hard negative (SHN)
optimization.

+ | Anchor | SCT Hard - | SHN Hard -
---|---|---|---
|  |  |
|  |  |
|  |  |
|  |  |
Figure 3: Example triplets from the CAR and CUB datasets at the start of training. The positive example is randomly selected from a batch, and we show the hard negative example selected by SCT and SHN approach. + | Anchor | SCT Hard - | SHN Hard -
---|---|---|---
|  |  |
|  |  |
|  |  |
|  |  |
Figure 4: Example triplets from the CAR and CUB datasets at the end of
training. The positive example is randomly selected from a batch, and we show
the hard negative example selected by SCT and SHN approach.

##  6 Experiments and Results

We run a set of experiments on the CUB200 (CUB) [24], CAR196 (CAR) [10],
Stanford Online Products (SOP) [18], In-shop Cloth (In-shop) [11] and
Hotels-50K(Hotel) [20] datasets. All tests are run on the PyTorch platform
[14], using ResNet50 [7] architectures, pre-trained on ILSVRC 2012-CLS data
[15]. Training images are re-sized to 256 by 256 pixels. We adopt a standard
data augmentation scheme (random horizontal flip and random crops padded by 10
pixels on each side). For pre-processing, we normalize the images using the
channel means and standard deviations. All networks are trained using
stochastic gradient descent (SGD) with momentum 0. The batch size is 128 for
CUB and CAR, 512 for SOP, In-shop and Hotel50k. In a batch of images, each
class contains 2 examples and all classes are randomly selected from the
training data. Empirically, we set $\lambda=1$ for all datasets tested.

We calculate Recall@K as the measurement for retrieval quality. On the CUB and
CAR datasets, both the query set and gallery set refer to the testing set.
During the query process, the top-K retrieved images exclude the query image
itself. In the Hotels-50K dataset, the training set is used as the gallery for
all query images in the test set, as per the protocol described by the authors
in [20].

Figure 5: Hard negative triplets of a batch in training iterations 0, 4, 8,
12. 1st row: Triplet loss with hard negative mining (HN); 2nd row: Triplet
loss with semi hard negative mining (SHN). Although the hard negative triplets
are not selected for training, their position may still change as the network
weights are updated; 3rd row: Selectively Contrastive Triplet loss with hard
negative mining (SCT). In each case we show where a set of triplets move
before an after the iteration, with the starting triplet location shown in red
and the ending location in blue.

###  6.1 Hard negative triplets during training

Figure 5 helps to visualize what happens with hard negative triplets as the
network trains using the triplet diagram described in Section 3. We show the
triplet diagram over several iterations, for the HN approach (top), SHN
approach (middle), and the SCT approach introduced in this paper (bottom).

In the HN approach (top row), most of the movements of hard negative triplets
coincide with the movement prediction of the vector field in the Figure 2 –
all of the triplets are pushed towards the bad minima at the location (1,1).

During the training of SHN approach (middle row), it can avoid this local
minima problem, but the approach does not do a good job of separating the hard
negative pairs. The motion from the red starting point to the blue point after
the gradient update is small, and the points are not being pushed below the
diagonal line (where the positive example is closer than the negative
example).

SCT approach (bottom) does not have any of these problems, because the hard
negative examples are more effectively separated early on in the optimization,
and the blue points after the gradient update are being pushed towards or
below the diagonal line.

Figure 6: Left: the percentage of hard triplets in a batch for SOP, In-shop
Cloth and Hotels-50K datasets. Right: Recall@1 performance comparison between
HN, SHN and SCT approaches.

In Figure 6, we display the percentage of hard triplets as defined in Section
3 in a batch of each training iteration on CUB, CAR, SOP, In-shop Cloth and
Hotels-50k datasets (left), and compare the Recall@1 performance of HN, SHN
and SCT approaches (right). In the initial training phase, if a high ratio of
hard triplets appear in a batch such as CUB, CAR and Hotels-50K dataset, the
HN approach converges to the local minima seen in Figure 5.

We find the improvement is related to the percentage of hard triplets when it
drops to a stable level. At this stage, there is few hard triplets in In-shop
Cloth dataset, and a small portion of hard triplets in CUB, CAR and SOP
datasets, a large portion of hard triplets in Hotels-50K dataset. In Figure 6,
the model trained with SCT approach improves R@1 accuracy relatively small
improvement on CUB, CAR, SOP and In-shop datasets but large improvement on
Hotels-50K datasets with respect to the model trained with the SHN approach in
Table 1, we show the new state-of-the-art result on Hotels-50K dataset, and
tables of the other datasets are shown in Appendix (this data is visualized in
Figure 6 (right)).

| Hotel Instance | Hotel Chain
---|---|---
Method | R@1 | R@10 | R@100 | R@1 | R@3 | R@5
BATCH-ALL [20]256 | 8.1 | 17.6 | 34.8 | 42.5 | 56.4 | 62.8
Easy Positive [27]256 | 16.3 | 30.5 | 49.9 | - | - | -
SHN256 | 18.78 | 32.90 | 52.19 | 54.17 | 64.99 | 69.90
SCT256 | 29.24 | 44.38 | 61.53 | 60.78 | 70.39 | 74.35

Table 1: Retrieval performance on the Hotels-50K dataset. All methods are
trained with Resnet-50 and embedding size is 256.

###  6.2 Generalizability of SCT Features

Improving the recall accuracy on unseen classes indicates that the SCT
features are more generalizable – the features learned from the training data
transfer well to the new unseen classes, rather than overfitting on the
training data. The intuition for why the SCT approach would allow us to learn
more generalizable features is because

forcing the network to give the same feature representation to very different
examples from the same class is essentially memorizing that class, and that is
not likely to translate to new classes. Because SCT uses a contrastive
approach on hard negative triplets, and only works to decrease the anchor-
negative similarity, there is less work to push dis-similar anchor-positive
pairs together. This effectively results in training data being more spread
out in embedding space which previous works have suggested leads to
generalizable features [25, 27].

We observe this spread out embedding property in the triplet diagrams seen in
Figure 7. On training data, a network trained with SCT approach has anchor-
positive pairs that are more spread out than a network trained with SHN
approach (this is visible in the greater variability of where points are along
the x-axis), because the SCT approach sometimes removes the gradient that
pulls anchor-positive pairs together. However, the triplet diagrams on test
set show that in new classes the triplets have similar distributions, with SCT
creating features that are overall slightly higher anchor-positive similarity.

A different qualitative visualization in Figure 8, shows the embedding
similarity visualization from [19], which highlights the regions of one image
that make it look similar to another image. In the top set of figures from the
SHN approach, the blue regions that indicate similarity are diffuse, spreading
over the entire car, while in the bottom visualization from the SCT approach,
the blue regions are focused on specific features (like the headlights). These
specific features are more likely to generalize to new, unseen data, while the
features that represent the entire car are less likely to generalize well.

Figure 7: We train a network on the CAR dataset with the SHN and SCT approach
for 80 epochs. Testing data comes from object classes not seen in training. We
make a triplet for every image in the training and testing data set, based on
its easiest positive (most similar same class image) and hardest negative
(most similar different class image), and plot these on the triplet diagram.
We see the SHN (left) have a more similar anchor-positive than SCT (right) on
the training data, but the SCT distribution of anchor-positive similarities is
greater on images from unseen testing classes, indicating improved
generalization performance.

(a) SHN

(b) SHN

(c) SCT

(d) SCT

Figure 8: The above figures show two query images from the CAR dataset (middle
left in each set of images) , and the top five results returned by our model
trained with hard negative examples. The Similarity Visualization approach
from [19] show what makes the query image similar to these result images (blue
regions contribute more to similarity than red regions). In all figures, the
visualization of what makes the query image look like the result image is on
top, and the visualization of what makes the result image look like the query
image is on the bottom. The top two visualizations (a) and (b) show the
visualization obtained from the network trained with SHN approach, while the
bottom two visualizations (c) and (d) show the visualization obtained from the
network trained with SCT approach. The heatmaps in the SCT approach
visualizations are significantly more concentrated on individual features, as
opposed to being more diffuse over the entire car. This suggests the SCT
approach learns specific semantic features rather than overfitting and
memorizing entire vehicles.

##  7 Discussion

Substantial literature has highlighted that hard negative triplets are the
most informative for deep metric learning – they are the examples where the
distance metric fails to accurately capture semantic similarity. But most
approaches have avoided directly optimizing these hard negative triplets, and
reported challenges in optimizing with them.

This paper introduces the triplet diagram as a way to characterize the effect
of different triplet selection strategies. We use the triplet diagram to
explore the behavior of the gradient descent optimization, and how it changes
the anchor-positive and anchor-negative similarities within triplet. We find
that hard negative triplets have gradients that (incorrectly) force negative
examples closer to the anchor, and situations that encourage triplets of
images that are all similar to become even more similar. This explains
previously observed bad behavior when trying to optimize with hard negative
triplets.

We suggest a simple modification to the desired gradients, and derive a loss
function that yields those gradients. Experimentally we show that this
improves the convergence for triplets with hard negative mining strategy. With
this modification, we no longer observe challenges in optimization leading to
bad local minima and show that hard-negative mining gives results that exceed
or are competitive with state of the art approaches. We additionally provide
visualizations that explore the improved generalization of features learned by
a network trained with hard negative triplets.

#### Acknowledgements:

This research was partially funded by the Department of Energy, ARPA-E award
#DE-AR0000594, and NIJ award 2018-75-CX-0038. Work was partially completed
while the first author was an intern with Microsoft Bing Multimedia team.

## References

  * [1] Cakir, F., He, K., Xia, X., Kulis, B., Sclaroff, S.: Deep metric learning to rank. In: The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (June 2019)
  * [2] Faghri, F., Fleet, D.J., Kiros, J.R., Fidler, S.: Vse++: Improving visual-semantic embeddings with hard negatives. In: Proceedings of the British Machine Vision Conference (BMVC) (2018)
  * [3] Ge, J., Gao, G., Liu, Z.: Visual-textual association with hardest and semi-hard negative pairs mining for person search. arXiv preprint arXiv:1912.03083 (2019)
  * [4] Ge, W.: Deep metric learning with hierarchical triplet loss. In: Proc. European Conference on Computer Vision (ECCV) (September 2018)
  * [5] Goldberger, J., Hinton, G.E., Roweis, S.T., Salakhutdinov, R.R.: Neighbourhood components analysis. In: Saul, L.K., Weiss, Y., Bottou, L. (eds.) Advances in Neural Information Processing Systems 17, pp. 513–520. MIT Press (2005)
  * [6] Harwood, B., Kumar, B., Carneiro, G., Reid, I., Drummond, T., et al.: Smart mining for deep metric learning. In: Proceedings of the IEEE International Conference on Computer Vision. pp. 2821–2829 (2017)
  * [7] He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition. In: Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (June 2016)
  * [8] Hermans*, A., Beyer*, L., Leibe, B.: In Defense of the Triplet Loss for Person Re-Identification. arXiv preprint arXiv:1703.07737 (2017)
  * [9] Kim, W., Goyal, B., Chawla, K., Lee, J., Kwon, K.: Attention-based ensemble for deep metric learning. In: Proc. European Conference on Computer Vision (ECCV) (September 2018)
  * [10] Krause, J., Stark, M., Deng, J., Fei-Fei, L.: 3d object representations for fine-grained categorization. In: 4th International IEEE Workshop on 3D Representation and Recognition (3dRR-13). Sydney, Australia (2013)
  * [11] Liu, Z., Luo, P., Qiu, S., Wang, X., Tang, X.: Deepfashion: Powering robust clothes recognition and retrieval with rich annotations. In: Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (June 2016)
  * [12] Movshovitz-Attias, Y., Toshev, A., Leung, T.K., Ioffe, S., Singh, S.: No fuss distance metric learning using proxies. In: Proc. International Conference on Computer Vision (ICCV) (Oct 2017)
  * [13] Opitz, M., Waltner, G., Possegger, H., Bischof, H.: Bier - boosting independent embeddings robustly. In: Proc. International Conference on Computer Vision (ICCV) (Oct 2017)
  * [14] Paszke, A., Gross, S., Chintala, S., Chanan, G., Yang, E., DeVito, Z., Lin, Z., Desmaison, A., Antiga, L., Lerer, A.: Automatic differentiation in pytorch. In: NIPS-W (2017)
  * [15] Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M., Berg, A.C., Fei-Fei, L.: ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV) 115(3), 211–252 (2015)
  * [16] Schroff, F., Kalenichenko, D., Philbin, J.: Facenet: A unified embedding for face recognition and clustering. In: Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (June 2015)
  * [17] Sohn, K.: Improved deep metric learning with multi-class n-pair loss objective. In: Advances in Neural Information Processing Systems. pp. 1857–1865 (2016)
  * [18] Song, H.O., Xiang, Y., Jegelka, S., Savarese, S.: Deep metric learning via lifted structured feature embedding. In: Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2016)
  * [19] Stylianou, A., Souvenir, R., Pless, R.: Visualizing deep similarity networks. In: IEEE Winter Conference on Applications of Computer Vision (WACV) (January 2019)
  * [20] Stylianou, A., Xuan, H., Shende, M., Brandt, J., Souvenir, R., Pless, R.: Hotels-50k: A global hotel recognition dataset. In: AAAI Conference on Artificial Intelligence (2019)
  * [21] Suh, Y., Han, B., Kim, W., Lee, K.M.: Stochastic class-based hard example mining for deep metric learning. In: The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (June 2019)
  * [22] Wang, C., Zhang, X., Lan, X.: How to train triplet networks with 100k identities? In: Proceedings of the IEEE International Conference on Computer Vision Workshops. pp. 1907–1915 (2017)
  * [23] Wang, X., Han, X., Huang, W., Dong, D., Scott, M.R.: Multi-similarity loss with general pair weighting for deep metric learning. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. pp. 5022–5030 (2019)
  * [24] Welinder, P., Branson, S., Mita, T., Wah, C., Schroff, F., Belongie, S., Perona, P.: Caltech-UCSD Birds 200. Tech. Rep. CNS-TR-2010-001, California Institute of Technology (2010)
  * [25] Wu, Z., Xiong, Y., Yu, S.X., Lin, D.: Unsupervised feature learning via non-parametric instance discrimination. In: The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (June 2018)
  * [26] Xuan, H., Souvenir, R., Pless, R.: Deep randomized ensembles for metric learning. In: Proc. European Conference on Computer Vision (ECCV) (September 2018)
  * [27] Xuan, H., Stylianou, A., Pless, R.: Improved embeddings with easy positive triplet mining. In: The IEEE Winter Conference on Applications of Computer Vision (WACV) (March 2020)
  * [28] Yu, B., Liu, T., Gong, M., Ding, C., Tao, D.: Correcting the triplet selection bias for triplet loss. In: Proceedings of the European Conference on Computer Vision (ECCV). pp. 71–87 (2018)
  * [29] Zhang, X., Yu, F.X., Kumar, S., Chang, S.F.: Learning spread-out local feature descriptors. In: The IEEE International Conference on Computer Vision (ICCV) (Oct 2017)

## Appendix

###  0..1 Similarity after gradient updating(NCA-based triplet loss)

The following derivations show how to get $S_{ap}^{new}$ and $S_{an}^{new}$ in
equation 7 and 8 with updated and unnormalized
$\mathbf{f_{a}}^{new},\mathbf{f_{p}}^{new},\mathbf{f_{n}}^{new}$ in equation
4, 5 and 6.

$\begin{split}S_{ap}^{new}=&{\mathbf{f_{a}}^{new}}^{\intercal}\mathbf{f_{p}}^{new}\\\
=&(1+\beta^{2})\mathbf{f_{a}}^{\intercal}\mathbf{f_{p}}+\beta\mathbf{f_{a}}^{\intercal}\mathbf{f_{a}}+\beta\mathbf{f_{p}}^{\intercal}\mathbf{f_{p}}-\beta\mathbf{f_{n}}^{\intercal}\mathbf{f_{p}}-\beta^{2}\mathbf{f_{n}}^{\intercal}\mathbf{f_{a}}\\\
=&(1+\beta^{2})S_{ap}+2\beta-\beta S_{pn}-\beta^{2}S_{an}\\\ \end{split}$ (14)

$\begin{split}S_{an}^{new}=&{\mathbf{f_{a}}^{new}}^{\intercal}\mathbf{f_{n}}^{new}\\\
=&(1+\beta^{2})\mathbf{f_{a}}^{\intercal}\mathbf{f_{n}}-\beta\mathbf{f_{a}}^{\intercal}\mathbf{f_{a}}-\beta\mathbf{f_{n}}^{\intercal}\mathbf{f_{n}}+\beta\mathbf{f_{p}}^{\intercal}\mathbf{f_{n}}-\beta^{2}\mathbf{f_{p}}^{\intercal}\mathbf{f_{a}}\\\
=&(1+\beta^{2})S_{ap}-2\beta+\beta S_{pn}-\beta^{2}S_{ap}\\\ \end{split}$ (15)

For the calculation of $S_{ap}^{new}$, we construct two hyper-planes: $P_{ap}$
spanned by $\mathbf{f_{a}}$ and $\mathbf{f_{p}}$, and $P_{an}$ spanned by
$\mathbf{f_{a}}$ and $\mathbf{f_{n}}$. On $P_{ap}$, $\mathbf{f_{p}}$ can be
decomposed into two components: $\mathbf{f_{p}^{a\parallel}}$(the direction
along $\mathbf{f_{a}}$) and $\mathbf{f_{p}^{a\bot}}$(the direction vertical to
$\mathbf{f_{a}}$). On $P_{an}$, $\mathbf{f_{n}}$ can be decomposed into two
components: $\mathbf{f_{n}^{a\parallel}}$(the direction along
$\mathbf{f_{a}}$) and $\mathbf{f_{n}^{a\bot}}$(the direction vertical to
$\mathbf{f_{a}}$). Then the $S_{pn}$ should be:

$\begin{split}S_{pn}=&\mathbf{f_{p}}^{\intercal}\mathbf{f_{n}}\\\
=&(\mathbf{f_{p}^{a\parallel}}+\mathbf{f_{p}^{a\bot}})(\mathbf{f_{n}^{a\parallel}}+\mathbf{f_{n}^{a\bot}})\\\
=&S_{ap}S_{an}+\gamma\sqrt{1-S_{ap}^{2}}\sqrt{1-S_{an}^{2}}\\\ \end{split}$
(16)

where
$\gamma=\frac{\mathbf{f_{p}^{a\bot}}\mathbf{f_{n}^{a\bot}}}{\|\mathbf{f_{p}^{a\bot}}\|\|\mathbf{f_{n}^{a\bot}}\|}$,
which represents the projection factor between $P_{ap}$ and $P_{an}$. When
$\mathbf{f_{a}}$, $\mathbf{f_{n}}$, and $\mathbf{f_{p}}$ are close enough so
that locally the hypersphere is a plane, then $\gamma$ is the dot-product of
normalized vector from $\mathbf{f_{a}}$ to $\mathbf{f_{p}}$ and
$\mathbf{f_{a}}$ to $\mathbf{f_{n}}$. If
$\mathbf{f_{p}},\mathbf{f_{a}},\mathbf{f_{n}}$ are co-planer then $\gamma=1$,
and if moving from $\mathbf{f_{a}}$ to $\mathbf{f_{p}}$ is orthogonal to the
direction from $\mathbf{f_{a}}$ to $\mathbf{f_{n}}$, then $\gamma=0$.

###  0..2 Norm of updated features(NCA-based triplet loss)

The following derivation shows how to derive $\|\mathbf{f_{a}}^{new}\|$,
$\|\mathbf{f_{p}}^{new}\|$ and $\|\mathbf{f_{n}}^{new}\|$ in equation 9 and
10. On $P_{ap}$, $\mathbf{g_{p}}$ can be decomposed into the direction along
$\mathbf{f_{p}}$ and the direction vertical to $\mathbf{f_{p}}$. On $P_{an}$,
$\mathbf{g_{n}}$ can be decomposed into the direction along $\mathbf{f_{n}}$
and the direction vertical to $\mathbf{f_{n}}$. Then,

$\displaystyle\|\mathbf{f_{p}}^{new}\|^{2}$ $\displaystyle=(1+\beta
S_{ap})^{2}+\beta^{2}(1-S_{ap}^{2})$ (17)
$\displaystyle\|\mathbf{f_{n}}^{new}\|^{2}$ $\displaystyle=(1-\beta
S_{an})^{2}+\beta^{2}(1-S_{an}^{2})$ (18)

On $P_{ap}$, $\mathbf{g_{a}}$ can be decomposed into 3 components: component
in the plane and along $\mathbf{f_{a}}$, component in the plane and vertical
$\mathbf{f_{a}}$, and component vertical to $P_{ap}$. Then,

$\begin{split}\|\mathbf{f_{a}}^{new}\|^{2}&=(1+\beta S_{ap}-\beta
S_{an})^{2}\\\
&+(\beta\sqrt{1-S_{ap}^{2}}-\gamma\beta\sqrt{1-S_{an}^{2}})^{2}\\\
&+(\beta\sqrt{1-\gamma^{2}}\sqrt{1-S_{an}^{2}})^{2}\\\ \end{split}$ (19)

###  0..3 Gradient updates(margin-based triplet loss)

Dataset | CUB | CAR
---|---|---
Method | R@1 | R@2 | R@4 | R@8 | R@1 | R@2 | R@4 | R@8
Triplet-Semihard64 | 42.6 | 55.0 | 66.4 | 77.2 | 51.5 | 63.8 | 73.5 | 82.4
Lifted64 | 43.6 | 56.6 | 68.6 | 79.6 | 53.0 | 65.7 | 76.0 | 84.3
Clustering64 | 49.8 | 61.4 | 71.8 | 81.9 | 58.1 | 70.6 | 80.3 | 87.8
SmartMining64 | 49.8 | 62.3 | 74.1 | 83.3 | 64.7 | 76.2 | 84.2 | 90.2
ProxyNCA64 | 49.2 | 61.9 | 67.9 | 72.4 | 73.2 | 82.4 | 86.4 | 88.7
N-pair64 | 51.9 | 64.3 | 74.9 | 83.2 | 71.1 | 79.7 | 86.5 | 91.6
SHN64 | 56.7 | 68.6 | 78.6 | 86.6 | 67.9 | 77.8 | 85.3 | 90.7
SCT64 | 57.7 | 69.8 | 79.6 | 87.0 | 73.4 | 82.0 | 88.0 | 92.4

Table 2: Retrieval Performance on the CUB and CAR datasets comparing to the
best reported results with embedding dimension 64 trained on ResNet50.

Dataset | SOP | In-shop
---|---|---
Method | R@1 | R@10 | R@100 | R@1 | R@10 | R@20
BIER [13]512 | 72.7 | 86.5 | 94.0 | 76.9 | 92.8 | 95.2
ABE [9]512 | 76.3 | 88.4 | 94.8 | 87.3 | 96.7 | 97.9
FastAP [1]512 | 76.4 | 89.0 | 95.1 | 90.9 | 97.7 | 98.5
MS [23]512 | 78.2 | 90.5 | 96.0 | 89.7 | 97.9 | 98.5
EasyPositive [27]512 | 78.3 | 90.7 | 96.3 | 87.8 | 95.7 | 96.8
SHN512 | 81.0 | 92.3 | 96.8 | 90.6 | 97.4 | 98.1
SCT512 | 81.9 | 92.6 | 96.8 | 90.9 | 97.5 | 98.1

Table 3: Retrieval Performance on the SOP and In-shop datasets comparing to
the best reported results with embedding dimension 512 trained on ResNet50

The main paper uses NCA-based triplet loss. Another margin-based triplet-loss
function is derived to guarantee a specific margin. This can be expressed in
terms of $\mathbf{f_{a}}$,$\mathbf{f_{p}}$,$\mathbf{f_{n}}$ as:

$L=\max(\|\mathbf{f_{a}}-\mathbf{f_{p}}\|^{2}-\|\mathbf{f_{a}}-\mathbf{f_{n}}\|^{2}+\alpha,0)=\max(D,0)$
(20) $\displaystyle\mathbf{g_{p}}=$ $\displaystyle\frac{\partial
L}{\partial\mathbf{\mathbf{f_{p}}}}=\begin{cases}-\beta(\mathbf{f_{a}}-\mathbf{f_{p}})&\text{if
$D>0$}\\\ 0&\text{otherwise}\end{cases}$ (21) $\displaystyle\mathbf{g_{n}}=$
$\displaystyle\frac{\partial
L}{\partial\mathbf{\mathbf{f_{n}}}}=\begin{cases}\beta(\mathbf{f_{a}}-\mathbf{f_{n}})&\text{if
$D>0$}\\\ 0&\text{otherwise}\end{cases}$ (22) $\displaystyle\mathbf{g_{a}}=$
$\displaystyle\frac{\partial
L}{\partial\mathbf{\mathbf{f_{a}}}}=\begin{cases}\beta(\mathbf{f_{n}}-\mathbf{f_{p}})&\text{if
$D>0$}\\\ 0&\text{otherwise}\end{cases}$ (23)

where
$D=(\|\mathbf{f_{a}}-\mathbf{f_{p}}\|^{2}-\|\mathbf{f_{a}}-\mathbf{f_{n}}\|^{2}+\alpha)$
and $\beta=2$. For simplicity, in the following discussion, we set $D>0$ for
margin-based triplet loss. Then we can get the $\mathbf{f_{a}}^{new}$,
$\mathbf{f_{p}}^{new}$ and $\mathbf{f_{n}}^{new}$ and their norm:

$\displaystyle\mathbf{f_{p}}^{new}=$
$\displaystyle\mathbf{f_{p}}+\beta(\mathbf{f_{a}}-\mathbf{f_{p}})$
$\displaystyle=(1-\beta)\mathbf{f_{p}}+\beta\mathbf{f_{a}}$ (24)
$\displaystyle\mathbf{f_{n}}^{new}=$
$\displaystyle\mathbf{f_{n}}-\beta(\mathbf{f_{a}}-\mathbf{f_{n}})$
$\displaystyle=(1+\beta)\mathbf{f_{n}}-\beta\mathbf{f_{a}}$ (25)
$\displaystyle\mathbf{f_{a}}^{new}=$
$\displaystyle\mathbf{f_{a}}-\beta\mathbf{f_{n}}+\beta\mathbf{f_{p}}$ (26)
$\displaystyle\|\mathbf{f_{p}}^{new}\|^{2}$ $\displaystyle=(1-\beta+\beta
S_{ap})^{2}+\beta^{2}(1-S_{ap}^{2})$ (27)
$\displaystyle\|\mathbf{f_{n}}^{new}\|^{2}$ $\displaystyle=(1+\beta-\beta
S_{an})^{2}+\beta^{2}(1-S_{an}^{2})$ (28)
$\begin{split}\|\mathbf{f_{a}}^{new}\|^{2}&=(1+\beta S_{ap}-\beta
S_{an})^{2}\\\
&+(\beta\sqrt{1-S_{ap}^{2}}-\gamma\beta\sqrt{1-S_{an}^{2}})^{2}\\\
&+(\beta\sqrt{1-\gamma^{2}}\sqrt{1-S_{an}^{2}})^{2}\\\ \end{split}$ (29)

The updated similarity $S_{ap}^{new}$ and $S_{an}^{new}$ will be:

$\begin{split}S_{ap}^{new}=(1-\beta+\beta^{2})S_{ap}+2\beta-\beta^{2}-\beta(1-\beta)S_{pn}-\beta^{2}S_{an}\end{split}$
(30)
$\begin{split}S_{an}^{new}=(1+\beta+\beta^{2})S_{an}-2\beta-\beta^{2}+\beta(1+\beta)S_{pn}-\beta^{2}S_{ap}\end{split}$
(31)

Comparing to the $S_{ap}^{new}$ and $S_{an}^{new}$ in equation 7 and 8 of main
paper, margin-based triplet loss behavior is similar to the NCA-based triplet
loss. And we simulate the $\Delta S_{ap}$ and $\Delta S_{an}$ with the margin-
based triplet loss in figure 9. These plots show that the behavior of
problematic regions are qualitatively similar for both methods with different
values of entanglement strength $p$.

$L^{nca}$ | $L^{margin}$
---|---
|
|
|
Figure 9: Numerical simulation for $\Delta S_{ap}$, $\Delta S_{an}$, $\Delta
S_{ap}^{total}$ and $\Delta S_{an}^{total}$ change of $L^{nca}$ and
$L^{margin}$ with $p=0.5,1.0$.

###  0..4 More Results on other dataset

We also compare our results with state-of-the-art embedding approaches such as
BIER [13],ABE [9],FaseAP [1] Multi-Similarity [23] and Easy Positive [27] on
SOP [18] and In-shop [11] dataset. Tables 3 shows the SC-triplet loss
outperforms the best previously reported results on the SOP dataset.