INFORMATIVE SAMPLE-AWARE
PROXY FOR DEEP METRIC LEARNING
Aoyu Li, Ikuro Sato, Kohta Ishikawa, Rei Kawakami, Rio Yokota

Presenter: Aoyu LiGSIC, Tokyo Institute of Technology

Introduction to Deep (Distance) Metric Learning➤ Deep Metric Learning (DML): supervised representation learning such that

Data from the same class:
Data from diﬀerent class:

Euclidean distanceorcosine similarity

Pull together
Push apart

Embeddings

Poolingxi( ∈ 𝒟)
Batch

xjEmb.
layerE

Backbone network fDij = ∥f (xi ) −D ikf (xj )∥)f (x i∥=f(xi)( ∈ ℝ )∥(x k)
f−xk
Embedding space (visualized with t-SNE [24])xiPositives: yj = yi

Negatives: yk ≠ yi

2

Why Metric Learning ?
➤ Tasks cannot be treated as classification when:•The number of classes is indefinite.

•Images belonging to each class cannot be obtained in advance.

•With DML:

Distance metricFeatures

Images xi, xj, …

Learnedmodel f

⋮

f(xi)
f(xj)

∥f(xi) − f(xj)∥ < δotherwise

The same class

Different class➤ Application:

Image Retrieval, Face Recognition, Few-shot Learning, etc.

3Types of DML Methods➤ Pair-based loss

Contrastive [5] O(N 2)➤ Proxy-based loss

Triplet [18] O(N 3)

N-Pair [21] O(N 3)proxy: centroid of a classsource of global information

Lifted Structure [12] O(N 3)

Positive embeddings
Negative embeddings
Pull together
Push apartProxies

Proxy-NCA [10] O(NC)

Proxy-Anchor [9] O(NC)4General Pair Weighting (X. Wang+, 2019 [11]) for DML LossA DML loss can be formulated as ℒ =∑∑i

L(Sij, yi, yj).

j≠iDLet xi ∈ ℝ be a row data sample, label yi ∈ {1,2,…, C};DE

Encoder f( ⋅ ; θ) : ℝ → ℝ ; Similarity of two samples: Sij = < f(xi; θ), f(xj; θ) > ;negative pairs∂ℒ=∑∂θ
ipositive pairs∂L ∂Sij∂L ∂Sij+:=∑ ∂Sij ∂θ∑ ∂Sij ∂θ
∑
j:y ≠yj:y =yijiji∂Sij−wij∑∂θ
j:yj≠yi∂Sij+−wij∑∂θ
j:yj=yi5

Gradient Weights & Types of Hardness
AnchorPositive embeddings
Negative embeddings

wij+
wij−

Self hardness

Relative hardness

Class hardness

Contrastive [5]Triplet [18]Lifted Structure [12]MS [11]
Norm. SoftMax [23]Proxy-Anchor [9]6Gradient Weights & Types of Hardness
ProxyPositive embeddings
Negative embeddings

Proxy-Anchor [9] O(NC)

Proxy-Anchor [9]Self hardness

Relative hardness

e.g. Binomial Deviance [13]e.g. Lifted Structure [12]α exp{α(λ − Sij)}
1wij+ =Pi 1 + exp{α(λ − Sij)}
1 β exp{β(Sij − λ)}−wij =
Ni 1 + exp{β(Sij − λ)}1LPA =
log 1 +exp{α(δ − Sic)}+∑∑| P | p ∈P +i:y =cci1 C+log 1 +exp{α(Sic + δ)}∑∑C c=1i:y ≠ciClass hardness
e.g. Normalized SoftMax [23]exp{αSiyi}

wiyi = α 1 −∑c exp{αSic} )(α exp{αSic}−wic =∑c′ exp{αSic′}

1∑k:y =y exp{Sij − Sik}
ki
1−
wij =
∑k:y ≠y exp{Sik − Sij}
wij+ =kiα exp{α(δ − Sic)}
1| P + | 1 + ∑j:y =c exp{α(δ − Sjc)}
jα exp{α(Sic + δ)}1−
wic =C 1 + ∑j:y ≠c exp{α(Sjc + δ)}
wic+ =j6Negative Impact of Pair Weighting Without the Class Hardness
11 C
LPA =log 1 +exp{α(δ − Sic)} +log 1 +exp{α(Sic + δ)}+∑∑∑➤| P | p∑C+∈P
i:y =cc=1i:y ≠cci

Proxies form
their own cluster

Proxies

Proxies

Proxies aredistributed toeach classi➤ According to the K.K.T. condition, for the positive terms,α(δ−Sic)++,
log 1 +e= max
α𝒫(i)(δ−S)+H(𝒫)cicc∑∑
𝒫+ci:yi=ci:yi=cα(δ−Sic)e+and the solution is 𝒫c (i) =.
α(δ−Sjc)

Proxy-Anchor [9]Norm. SoftMax [23]1+ ∑ ej:yj=c➤ Only optimizing two data distribution (positives, negatives) related to each proxy.

•∂L(S)
wic =works for all data points but also the proxy pc itself.
∂Sic•

When outlier exists, the distribution would be sub-optimal.

•Proxies form a cluster due to strong repulsive forces in the early learning stage.

Terms contain outlier

Compact at early stage
7

Contributions of This Work➤➤➤Class hardness varies along learning → dynamically estimate the class hardness.
Outliers and less informative samples → class-dependent dynamic weighting based on learned intra/interclass relations.
Informative Sample-Aware Proxy (Proxy-ISA).

8

Estimate the Class Hardness Base on Historical Embeddings•The data learned in recent mini-batches → information about embedding space in last few iterations.

•Define total num. of embeddings from class c in M as Tc, given a hardness scaling factor h, the class hardness

hof class c can be estimated by: Slearned(c) =Sic.
∑Tc (x ,y )∈M,y=ci i•iThreshold of lessinformative samples

After a mini-batch training, filter out outliers and enqueue the rest to M.

9Hardness-Related Thresholds➤ Slearned: when the proxy-data similarity is larger than this threshold (too close/easy),

regard as less informative sample.

➤ Soutlier: when the similarity is smaller than this threshold (too far/hard), regard as outlier.

•(c)
(c)
(c)
Soutlier = Slearned − ηc ∈ (−1,Slearned)

Easy

InlierHardSlearned

Soutlier

Outlier

Dataset10How Can We Estimate the Learned Class ?
➤ Eﬀective Number (Y. Cui+, 2019 [14])•••••γc: volumetric unit of class c

Volume of correctly learned data for a class while the nth sample of this class is selected: En ⋅ γc.

En−1Total volume of embedding space for a class: V ⋅ γc; Random sampling → random covering with p =.
VV−1
En = pEn−1 + (1 − p)(En−1 + 1) = 1 +En−1Vnnoverlapped (p)V−11−βi−1=β .
Let β =, E1 = 1, we can induce En =∑V
1−βi=1nolim En = V.

n→∞

➤ En can be used to estimate how much knowledge about a class is learned.
Total: V…

toverlapped(1−p)

all possible data (V ⋅ γc)previously sampled data

EnEn+mnewly sampled data (γc)
11Definition of Class-Dependent Informative Samples(c)➤ When E
n increases, ηc (range for informative samples) should decrease,the penalties for less informative samples and outliers should be greater.

•(c)
(c)
ηc = (1 + k(1 − Slearned(c)))νn + λ, where νn =•k: sensitivity factor; λ: hardness margin

1(c)1 + log(1 + En )12

Adaptive Weighting Factors
Dynamic weights according to diﬀerent semantic states.
➤For positive pairs:•Sic < Slearned(c) − ηc, ωic = σ(c);•Sic > Slearned(c), ωic = σ(c);•Otherwise, ωic = 1 + σ(c).

Informative(c)
νn =

•

•

Otherwise, ωic = 1.

1(c)max(1,En )(c)) (νn − 1)(c)V−E
1 + e n −τ1(c)1 + log(1 + En )1(c)(c)
lim σn = lim νn =n→∞n→∞
1 + log(1 + V)

➤ For negative pairs:Sic < Slearned(c) − ηc, ωic =(c)σn = 1 +(1 + e−τ;

Informative

13Reform the Optimization Problem of Pair Constraints+++ ++maxα𝒫(i)(δ−S)
+H(𝒫)
→
maxα
ω
𝒬
(i)(δ
−S)
+H(𝒬)
cic
cc
ic
cic++
∑∑
𝒫c
𝒬c
i:yi=ci:yi=c−−− −−maxα𝒫(i)(S+δ)
+
H(𝒫)
→
maxα
ω
𝒬
(i)(S+δ)
+H(𝒬)
cic
cic
cicc∑∑
𝒫−c
𝒬−ci:yi≠ci:yi≠cAccording to the K.K.T. condition, the optimal is

log+1+exp{ωic ⋅ α(δ − Sic)}∑i:yi=c, log−1+exp{ωic ⋅ α(δ + Sic)}∑i:yi≠c, respectively.

Informative area

ProxyOutlier threshold
Subspace threshold
Data embedding
14

Informative Sample-Aware Proxy (Proxy-ISA)
Formally,C

11+−LISA =log
1+exp{ω⋅α(δ−S)}+log
1+exp{ω⋅α(δ+S)}
ic
ic
icic−∑∑+∑∑∑c∈C+ ω̄+c c∈C∑ω̄c c c=1i:y =ci:y ≠ci

ωic+∂LISA=∂Sic∑c′∈C+ ω̄+c′ωic−⋅−∑c′ ω̄c′⋅iα exp{ωic+ ⋅ α(δ − Sic)}
1 + ∑j:y =c exp{ωjc+ ⋅ α(δ − Sjc)}
jα exp{ωic− ⋅ α(δ + Sic)}

1 + ∑j:y ≠c exp{ωjc− ⋅ α(δ + Sjc)},, if yi = c,otherwise .

jInformative area
Proxy
Outlier threshold
Subspace threshold
Data embedding
15

Experiments: Dataset
Datasets

Caltech-UCSD Birds-200-2011(CUB) [25]Cars-196 [26]Stanford Online Products(SOP) [27]In-shop Clothes Retrieval(In-shop) [28]Num. of images

Num. of categories

6,033

200 (the first 100for training)

16,185196 (the first 98 fortraining)

120,053

22,634 (the first11,318 for training)

52,712

7,982 (the first3,997 for training)

Preview

16Experiments: Comparison to SOTA Methods
Method

CUB

Cars

SOP

In-shop

Recall@1

MAP@R

Recall@1

MAP@R

Recall@1

MAP@R

Recall@1

Margin [6]

63.60

23.09

81.16

24.21

70.99

41.82

—

MS [11]

65.04

24.70

85.14

28.07

74.50

45.79

—

Proxy-NCA [10]Norm. SoftMax [23]

65.01
65.65

23.85
25.25

83.56
83.16

25.38
26.00

75.89
75.67

47.2247.13

86.92
—

SoftTriplet [16]

66.17

25.61

84.49

27.08

76.12

47.35

—

CosFace [19]

67.32

26.70

85.52

27.57

75.79

46.92

—

ArcFace [20]

67.50

26.45

85.44

27.22

76.20

47.41

—

Proxy-Anchor [9]

66.34

25.68

83.56

27.09

78.12

51.28

91.18

Proxy-ISA (Ours)

68.05

26.79

86.25

29.29

78.73

51.52

92.33

Pair-based

Proxy-based

Training settings:

Image retrieval tasks evaluated by Recall@K, MAP@R;

batch size = 128; embedding size = 512;

0, if none of the K retrieval(s) is correct,
Recall@K:{1, otherwise.

model: BN-Inception [22];learning rate:
1e-4 for CUB and Cars, 6e-4 for SOP and In-shop;
Hyper-parameters: V=100, T=55,000, λ=0.1, τ=1.5

R1P(i)
Mean Average Precision (MAP@R):R∑
i=1
precision@i, if the i-th retrieval is correct,P(i) ={0,otherwise.

17

Experiments: Impacts of Proxy-ISA on the Embedding Space
Initial stage
Heat map of cosine similarity

Sic

Sij
Norm. SoftMax [23]Class hardness only

Proxy-Anchor [9]Self + relative hardness

Proxy-ISA (Ours)

18

Self + relative + class hardness

Experiments: Embedding Space Visualization➤ t-SNE [24] visualization of Cars-196 [26] (training set)
•Initialization:

C: total num. of classes
Soverlap = [1] × C

Proxy-Anchor [9]Proxy-ISA (Ours)

19

Experiments: Embedding Space Visualization➤ t-SNE [24] visualization of Cars-196 [26] (test set)

Proxy-Anchor [9]Proxy-ISA (Ours)
20

Results of Image Retrieval
query

top-3 retrievals with Proxy-Anchor [9]top-3 retrievals with Proxy-ISA (Ours)

CUB [25]:

Cars [26]:similardissimilar

failure case21INFORMATIVE SAMPLE-AWARE
PROXY FOR DEEP METRIC LEARNING
Aoyu Li, Ikuro Sato, Kohta Ishikawa, Rei Kawakami, Rio Yokota

aoyuli@rio.gsic.titech.ac.jp
Poster #39
Starts at 14:30

Codehttps://github.com/rioyokotalab/ProxyISA

References[1] Kishida I. et al. Empirical Study of Easy and Hard Examples in CNN training. https://arxiv.org/abs/1911.10739[2] Chang H. et al. Active Bias: Training More Accurate Neural Network by Emphasizing High Variance Samples. NIPS 2017.
[3] Lin T. et al. Focal Loss for Dense Object Detection. ICCV 2017.
[4] Li B. et al. Gradient Harmonized Single-Stage Detector. AAAI 2019.
[5] Chopra S. et al. Learning a similarity metric discriminatively, with application to face verification. CVPR 2005.
[6] Wu C. et al. Sampling Matters in Deep Embedding Learning. ICCV 2017.
[7] Duan Y. et al. Deep Embedding Learning with Discriminative Sampling Policy. CVPR 2019.
[8] Katharopoulos A. et al. Not All Samples Are Created Equal-Deep Learning with Importance Sampling. ICML 2018.
[9] Kim S. et al. Proxy Anchor Loss for Deep Metric Learning. CVPR 2020.
[10] Movshovitz-Attias Y. et al. No Fuss Distance Metric Learning using Proxies. ICCV 2017.
[11] Wang X. et al. Multi-Similarity Loss with General Pair Weighting for Deep Metric Learning. CVPR 2019.
[12] Song H. et al. Deep Metric Learning via Lifted Structured Feature Embedding. CVPR 2016.
[13] Opitz M. et al. BIER - Boosting Independent Embeddings Robustly. ICCV 2017.
[14] Cui. Y. et al. Class-Balanced Loss Based on Eﬀective Number of Samples. CVPR 2019.
[15] Wang X. et al. Cross-Batch Memory for Embedding Learning. CVPR 2020.
[16] Qian Q. et al. Softtriple Loss: Deep Metric Learning without Triplet Sampling. ICCV 2019.
[17] Liu C. et al. Noise-resistant Deep Metric Learning with Ranking-based Instance Selection. CVPR 2021.
[18] Hoﬀer E. et al. Deep metric learning using triplet network. In Similarity-Based Pattern Recognition, pages 84–92. Springer International Publishing, 2015.
[19] Wang H. et al. Cosface: Large margin cosine loss for deep face recognition. CVPR 2018.
[20] Deng J. et al. Arcface: Additive angular margin loss for deep face recognition. CVPR 2019.
[21] Sohn K. Improved deep metric learning with multi-class n-pair loss objective. NIPS 2016.
[22] Sergey Ioﬀe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal co- variate shift. ICML 2015.
[23] Wang F. et al. Normface: L2 hypersphere embedding for face verification. ICM 2017.
[24] Laurens van der Maaten and Geoﬀrey Hinton. 2008. Visualizing Data using t-SNE. Journal of Machine Learning Research (2008).
[25] Catherine Wah, Steve Branson, Peter Welinder, Pietro Perona, and Serge J Belongie. 2011. The Caltech-UCSD Birds-200-2011 Dataset. Technical Report CNSTR-2011-001. California Institute of Technology.
[26] Jonathan Krause, Michael Stark, Jia Deng, and Li Fei-Fei. 3D Object Representations for Fine-Grained Categorization. ICCV 2013.
[27] Hyun Oh Song, Yu Xiang, Stefanie Jegelka, and Silvio Savarese. Deep Metric Learning via Lifted Structured Feature Embedding. CVPR 2016.
[28] Ziwei Liu, Ping Luo, Shi Qiu, Xiaogang Wang, and Xiaoou Tang. DeepFashion: Powering Robust Clothes Recognition and Retrieval With Rich Annotations. CVPR 2016.

28