\section{Introduction}
Fine-Grained Image Retrieval (FGIR)~\cite{fgis_tmm,crl,towardscrl,scda,part_based_fgir,adversarial_fgir} is a practical but challenging computer vision task. It aims to retrieve images belonging to various sub-categories of a certain meta-category (\text{e.g.}, birds, cars and aircrafts) and return images with the same sub-category as the query image.
In real FGIR applications, previous methods could suffer from slow query speed and redundant storage costs due to both the explosive growth of massive fine-grained data and high-dimensional real-valued features.

In the literature, learning to hash~\cite{LSH:conf/compgeom/DatarIIM04,ITQ:conf/cvpr/GongL11,SH:conf/nips/WeissTF08,CNNH:conf/aaai/XiaPLLY14,DH:conf/cvpr/LiongLWMZ15,DPSH:conf/ijcai/LiWK16,DSH:conf/cvpr/Liu0SC16,DSDH:conf/nips/LiSHT17,DCH:conf/cvpr/CaoLL018,ADSH:conf/aaai/JiangL18,HashGAN:conf/cvpr/DizajiZSYDH18} has proven to be a promising solution for large-scale image retrieval because it can greatly reduce the storage costs and increase the query speeds. As a representative research area of approximate nearest neighbor~(ANN) search~\cite{LSH:conf/compgeom/DatarIIM04,PQ:journals/pami/JegouDS11,KDTree:journals/cacm/Bentley75}, hashing aims to embed data points as \mbox{similarity-preserving} binary codes. Recently, hashing has been successfully applied in a wide range of image retrieval tasks, e.g., face image retrieval~\cite{DDH:conf/ijcai/LinLT17}, person re-identification~\cite{PDH:journals/tip/ZhuKZFT17,CSBT:conf/cvpr/ChenWQLS17}, etc. We hereby explore the effectiveness of hashing for \textit{fine-grained} image retrieval.

\begin{figure*}[t]
\centering
\includegraphics[scale=0.34]{figs/fg_hashing.pdf}
\caption{Illustration of the fine-grained hashing task. Fine-grained images could share large intra-class variances but small inter-class variances. Fine-grained hashing aims to generate compact binary codes with tiny Hamming distances for images of the same sub-category, as well as distinct codes for images from different sub-categories.}
\label{fig:fg_hashing}
\end{figure*}

To the best of our knowledge, this is the first work to study the fine-grained hashing problem, which refers to the problem of designing hashing for fine-grained objects. As shown in Figure~\ref{fig:fg_hashing}, the task is desirable to generate compact binary codes for fine-grained images sharing both large intra-class variances and small inter-class variances. To deal with the challenging task, we propose a unified end-to-end trainable network ExchNet to first learn fine-grained tailored features and then generate the final binary hash codes.

In concretely, our ExchNet consists of three main modules, including representation learning, local feature alignment and hash code learning, as shown in Figure~\ref{fig:framework}. In the representation learning module, beyond obtaining the holistic image representation (i.e., global features), we also employ the attention mechanism to capture the part-level features (i.e., local features) for representing fine-grained objects' parts. Localizing parts and embedding part-level cues are crucial for fine-grained tasks, since these discriminative but subtle parts (e.g., bird heads or tails) play a major role to distinguish different sub-categories. Moreover, we also develop two kinds of attention constraints, i.e., spatial and channel constraints, to collaboratively work together for further improving the discriminative ability of these local features. In the following, to ensure that these part-level features can correspond to their own corresponding parts across different fine-grained images, we design an anchor based feature alignment approach to align these local features. Specifically, in the local feature alignment module, we treat the anchored local features as the ``prototype'' w.r.t. its sub-category by averaging all the local features of that part across images. Once local features are well aligned for their own parts, even if we exchange one specific part's local feature of an input image with the same part's local feature of the prototype, the image meanings derived from the image representations and also the final hash codes should be both extremely similar. Inspired by this motivation, we perform a feature exchanging operation upon the anchored local features and other learned local features, which is illustrated in Figure~\ref{fig:keyidea}. After that, for effectively training the network with our feature alignment fashion, we utilize an alternating algorithm to solve the hashing learning problem and update anchor features simultaneously.

\begin{figure*}[t]
\centering
\includegraphics[width=1.0\textwidth]{figs/framework.pdf}
\caption{Framework of our proposed ExchNet, which consists of three modules. 1) The representation learning module, as well as the attention mechanism with spatial and channel diversity learning constraints, is designed to obtain both local and global features of fine-grained objects. 2) The local feature alignment module is used to align obtained local features w.r.t. object parts across different fine-grained images. 3) The hash codes learning module is performed to generate the compact binary codes.}
\label{fig:framework}
\end{figure*}

To quantitatively prove both effectiveness and efficiency of our ExchNet, we conduct comprehensive experiments on five fine-grained benchmark datasets, including the large-scale ones, i.e., {\textit{NABirds}}\xspace~\cite{NABirds:conf/cvpr/HornBFHBIPB15}, {\textit{VegFru}}\xspace~\cite{VegFru:conf/iccv/HouFW17} and {\textit{Food101}}\xspace~\cite{Food101:conf/eccv/BossardGG14}. Particularly, compared with competing approximate nearest neighbor methods, our ExchNet achieves up to hundreds times speedup for large-scale fine-grained image retrieval without significant accuracy drops. Meanwhile, compared with state-of-the-art generic hashing methods, ExchNet could consistently outperform these methods by a large margin on all the fine-grained datasets. Additionally, ablation studies and visualization results justify the effectiveness of our tailored model designs like local feature alignment and proposed attention approach.

The contributions of this paper are summarized as follows:
\begin{itemize}
	\item We study the novel fine-grained hashing topic to leverage the search and storage efficiency of hash codes for solving the challenging large-scale fine-grained image retrieval problem.

	\item We propose a unified end-to-end trainable network, i.e., ExchNet, to first learn fine-grained tailored features and then generate the final binary hash codes. Particularly, the proposed attention constraints, local feature alignment and anchor-based learning fashion contribute well to obtain discriminative fine-grained representations.

	\item We conduct extensive experiments on five fine-grained datasets to validate both effectiveness and efficiency of our proposed ExchNet. Especially for the results on large-scale datasets, ExchNet exhibits its outperforming retrieval performance on either speedup, memory usages and retrieval accuracy.

\end{itemize}

\section{Related Work}

\subsubsection{Fine-Grained Image Retrieval}
Fine-Grained Image Retrieval (FGIR) is an active research topic emerged in recent years, where the database and query images could share small inter-class variance but large intra-class variance.
In previous works~\cite{fgis_tmm}, handcrafted features were initially utilized to tackle the FGIR problem. Powered by deep learning techniques, more and more deep learning based FGIR methods~\cite{fgis_tmm,crl,maskcnn,towardscrl,scda,part_based_fgir,adversarial_fgir,piecewise} were proposed. These deep methods can be roughly divided into two parts, \text{i.e.}, supervised and unsupervised methods.
In supervised methods, FGIR is defined as a metric learning problem. Zheng et al.~\cite{crl} designed a novel ranking loss and a weakly-supervised attractive feature extraction strategy to facilitate the retrieval performance. Zheng et al.~\cite{towardscrl} improved their former work~\cite{crl} with a normalize-scale layer and de-correlated ranking loss.
As to unsupervised methods, Selective Convolutional Descriptor Aggregation (SCDA)~\cite{scda} was proposed to localize the main object in fine-grained images firstly, and then discard the noisy background and keep useful deep descriptors for fine-grained image retrieval.

\subsubsection{Deep Hashing}
Hashing methods can be divided into two categories, i.e., data-independent methods~\cite{LSH:conf/compgeom/DatarIIM04} and data-dependent methods~\cite{ITQ:conf/cvpr/GongL11,DPSH:conf/ijcai/LiWK16}, based on whether training points are used to learn hash functions. Generally speaking, data-dependent methods, also named as Learning to Hash~(L2H) methods, can achieve better retrieval performance with the help of the learning on training data. With the rise of deep learning, some L2H methods integrate deep feature learning into hash frameworks and achieve promising performance. As previous work, many deep hashing methods~\cite{CNNH:conf/aaai/XiaPLLY14,DH:conf/cvpr/LiongLWMZ15,DPSH:conf/ijcai/LiWK16,DSH:conf/cvpr/Liu0SC16,DSDH:conf/nips/LiSHT17,DCH:conf/cvpr/CaoLL018,ADSH:conf/aaai/JiangL18,HashGAN:conf/cvpr/DizajiZSYDH18,eccv:hashing1,eccv:hashing2,eccv:hashing3,eccv:hashing4,eccv:hashing5} for large-scale image retrieval have been proposed. Compared with deep unsupervised hashing methods~\cite{DH:conf/cvpr/LiongLWMZ15,HashGAN:conf/cvpr/DizajiZSYDH18,ADSH:conf/aaai/JiangL18}, deep supervised hashing methods~\cite{CNNH:conf/aaai/XiaPLLY14,DPSH:conf/ijcai/LiWK16,DSDH:conf/nips/LiSHT17,ADSH:conf/aaai/JiangL18} can achieve superior retrieval accuracy as they can fully explore the semantic information. Specifically, the previous work~\cite{CNNH:conf/aaai/XiaPLLY14} was essentially a two-stage method which tried to learn binary codes in the first stage and employed feature learning guided by the learned binary codes in the second stage. Then, there appeared numerous one-stage deep supervised hashing methods, including Deep Pairwise Supervised Hashing~(DPSH)~\cite{DPSH:conf/ijcai/LiWK16}, Deep Supervised Hashing~(DSH)~\cite{DSH:conf/cvpr/Liu0SC16}, and Deep Cauchy Hashing~(DCH)~\cite{DCH:conf/cvpr/CaoLL018}, which aimed to integrate feature learning and hash code learning into an end-to-end framework. Hashing Network~(HashNet)~\cite{HashGAN:conf/cvpr/DizajiZSYDH18} utilized $\mathtt{tanh}(\beta x)$ to approximate $\mathtt{sign}(x)$ by increasing $\beta$. Asymmetric Deep Supervised Hashing~(ADSH)~\cite{ADSH:conf/aaai/JiangL18} tried to use asymmetric hashing improve the training efficiency and retrieval performance.

\section{Methodology}

The framework of our ExchNet is presented in Figure~\ref{fig:framework}, which contains three key modules, i.e., the representation learning module, local feature alignment module, and hash code learning module.

\begin{figure*}[t]
\centering
\includegraphics[scale=0.35]{figs/key_idea.pdf}
\caption{Key idea of our local feature alignment approach: Given an image pair of a fine-grained category, exchanging their local features of the same object parts should not change their corresponding hash codes, \text{i.e.}, these hash codes should be the same as those generated without local feature exchanging and their Hamming distance should be still close also.}
\label{fig:keyidea}
\end{figure*}

\subsection{Representation Learning}

The learning of discriminative and meaningful local features is mutually correlated with fine-grained tasks~\cite{bcnn,isqrt,navigate,macnn,racnn}, since these local features can greatly benefit the distinguishing of sub-categories with subtle visual differences deriving from the discriminative fine-grained parts ({e.g.}, bird heads or tails) .
In consequence, as shown in Figure~\ref{fig:framework}, beyond the global feature extractor, we also introduce a local feature extractor in the representation learning module. Specifically, by considering model efficiency,  we hereby propose to learn local features with the attention mechanism, rather than other fine-grained techniques with tremendous computation cost, \text{e.g.}, second-order representations~\cite{bcnn,isqrt} or complicated network architectures~\cite{navigate,macnn,racnn}

Given an input image ${\boldsymbol x}_i$, a backbone CNN is utilized to extract a holistic deep feature ${\boldsymbol E}_i\in{\mathbb R}^{H\times W\times C}$, which serves as the appetizer for both the local feature extractor and the global feature extractor.

It is worth mentioning that the attention is engaged in the middle of the feature extractor. Since, in the shallow layers of deep neural networks, low-level context information~(\text{e.g.}, colors and edges, etc.) are well preserved, which is crucial for distinguish subtle visual differences of fine-grained objects. Then, by feeding ${\boldsymbol E}_i$ into the attention generation module, $M$ pieces of attention maps ${\boldsymbol A}_i\in{\mathbb R}^{M\times H\times W}$ are generated and we use ${\boldsymbol A}^j_i\in{\mathbb R}^{H\times W}$ to denote the attentive region of the $j$-th~($j\in\{1,\ldots,M\}$) part cues for ${\boldsymbol x}_i$. After that, the obtained part-level attention map ${\boldsymbol A}^j_i$ is element-wisely multiplied on ${\boldsymbol E}_i$ to select the attentive local feature corresponding to the $j$-th part, which is formulated as:
\begin{align}
\hat{\boldsymbol E}^j_i={\boldsymbol E}_i\otimes{\boldsymbol A}^j_i,
\end{align}
where $\hat{\boldsymbol E}^j_i\in{\mathbb R}^{H\times W\times C}$ represents the $j$-th attentive local feature of ${\boldsymbol x}_i$, and ``$\otimes$'' denotes the Hadamard product on each channel. For simplification, we use $\hat{\mathcal E}_i=\{\hat{\boldsymbol E}^1_i,\dots,\hat{\boldsymbol E}^M_i\}$ to denote a set of local features and, subsequently, $\hat{\mathcal E}_i$ is fed into the later Local Features Refinement~(LFR) network composed of a stack of convolution layers to embed these attentive local features into higher-level semantic meanings:
\begin{align}
{\mathcal F}_i = f_{\LFR}(\hat{\mathcal E}_i),
\end{align}
where the output of the network is denoted as ${\mathcal F}_i=\{{\boldsymbol F}_i^1,\dots,{\boldsymbol F}_i^M\}$, which represents the final local feature maps w.r.t. high-level semantics. We denote ${\boldsymbol f}_i^j\in{\mathbb R}^{C'}$ as the local feature vector after applying global average pooling~(GAP) on ${\boldsymbol F}_i^j\in{\mathbb R}^{H'\times W'\times C'}$ as:
\begin{align}
{\boldsymbol f}_i^j = f_\gap({\boldsymbol F}_i^j)\,.
\end{align}

On the other side, as to the global feature extractor, for ${\boldsymbol x}_i$, we directly adopt a Global Features Refinement~(GFR) network composed of conventional convolutional operations to embed ${\boldsymbol E}_i$, which is presented by:
\begin{align}
{\boldsymbol F}^{\rm global}_i = f_{\GFR}({\boldsymbol E}_i)\,.
\end{align}
We use ${\boldsymbol F}^{\rm global}_i\in{\mathbb R}^{H'\times W'\times C'}$ and ${\boldsymbol f}^{\rm global}_i\in{\mathbb R}^{C'}$ to denote the learned global feature and the corresponding holistic feature vector after GAP, respectively.

Furthermore, to facilitate the learning of localizing local feature cues (i.e., capturing fine-grained parts), we impose the spatial diversity and channel diversity constraints over the local features in ${\mathcal F}_i$.

Specifically, it is a natural choice to increase the diversity of local features by differentiating the distributions of attention maps~\cite{macnn}. However, it might cause a problem that the holistic feature can not be activated in some spatial positions, while the attention map has large activation values on them due to over-applied constraints upon the learned attention maps. Instead, in our method, we design and apply constraints on the local features. In concretely, for the local feature ${\boldsymbol F}^j_i$, we obtain its ``aggregation map'' $\hat{\boldsymbol A}_i^j\in{\mathbb R}^{H'\times W'}$ by adding all $C'$ feature maps through the channel dimension and apply the softmax function on it for converting it into a valid distribution, then flat it into a vector $\hat{\boldsymbol a}_i^j$. Based on the Hellinger distance, we propose a spatial diversity induced loss as:
\begin{align}
{\mathcal L}_{\mathtt{sp}}({\boldsymbol x}_i)=1-\frac{1}{\sqrt{2}\binom{M}{2}}\sum_{l,k=1}^M\left\Vert\sqrt{\hat{\boldsymbol a}_i^l}-\sqrt{\hat{\boldsymbol a}_i^k}\right\Vert_2	,\label{eq:sp-loss}
\end{align}
where $\binom{M}{2}$ is used to denote the combinatorial number of ways to pick $2$ unordered outcomes from $M$ possibilities. The spatial diversity constraint drives the aggregation maps to be activated in spatial positions as diverse as possible.
As to the channel diversity constraint, we first convert the local feature vector ${\boldsymbol f}_i^j$ into a valid distribution, which can be formulated by
\begin{align}
&{\boldsymbol p}_i^j=\softmax({\boldsymbol f}_i^j),\;\forall j\in\{1,\dots,M\}.
\end{align}
Subsequently, we propose a constraint loss over $\{{\boldsymbol p}_i^j\}_{j=1}^M$ as:
\begin{align}
{\mathcal L}_{\mathtt{cp}}({\boldsymbol x}_i)=\left[t-\frac{1}{\sqrt{2}\binom{M}{2}}\sum_{l,k=1}^M\left\Vert\sqrt{{\boldsymbol p}_i^l}-\sqrt{{\boldsymbol p}_i^k}\right\Vert_2\right]_+	,\label{eq:cp-loss}
\end{align}
where $t\in[0,1]$ is a hyper-parameter to adjust the diversity and $[\cdot]_+$ denotes $max(\cdot, 0)$. Equipping with the channel diversity constraint could benefit the network to depress redundancies in features through channel dimensions. Overall, our spatial diversity and channel diversity constraints can work in a collaborative way to obtain discriminative local features.

\begin{figure*}[t]
\centering
\includegraphics[scale=0.35]{figs/exchange.pdf}
\caption{Our feature exchanging and hash codes learning in the training phase. According to the class indices~(\text{i.e.}, $y_{i}$ and $y_{j}$), we first select categorical anchor features ${\mathcal C}_{y_i}$ and ${\mathcal C}_{y_j}$ for samples ${\boldsymbol x}_i$ and ${\boldsymbol x}_j$, respectively. Then, for each input image, the feature exchanging operation is conducted between its learned and anchored local features. After that, hash codes are generated with exchanged features and the learning is driven by preserving pairwise similarities of hash codes ${\boldsymbol u}_i$ and ${\boldsymbol v}_j$.}
\label{fig:exchange}
\end{figure*}

\subsection{Learning to Align by Local Feature Exchanging}\label{sec:learning_to_align}

Upon the representation learning module, the alignment on local features is necessary for confirming that they represent and more importantly correspond to common fine-grained parts across images, which are essential to fine-grained tasks.
Hence, we propose an anchor-based local features alignment approach assisted with our feature exchanging operation.

Intuitively, local features from the same object part (e.g., bird heads of a bird species) should be embedded with almost the same semantic meaning. As illustrated by Figure~\ref{fig:keyidea}, our key idea is that, if local features were well aligned, exchanging the features of identical parts for two input images belonging to the same sub-category should not change the generated hash codes. Inspired by that, we propose a local feature alignment strategy by leveraging the feature exchanging operation, which happens between learned local features and anchored local features.
As a foundation for feature exchanging, a set of dynamic anchored local features ${\mathcal C}_{y_i}=\{{\boldsymbol c}^1_{y_i},\dots,{\boldsymbol c}^M_{y_i}\}$ for class $y_i$ should be maintained, in which the $j$-th anchored local feature ${\boldsymbol c}^j_{y_i}$ is obtained by averaging all $j$-th part's local features of training samples from class $y_i$. At the end of each training epoch, anchored local features will be recalculated and updated.
Subsequently, as shown in Figure~\ref{fig:exchange}, for a sample ${\boldsymbol x}_i$ whose category is $y_i$, we exchange a half of the learned local features in ${\mathcal G}_i=\{{\boldsymbol f}_i^1,\dots,{\boldsymbol f}_i^M\}$ with its corresponding anchored local features in ${\mathcal C}_{y_i}=\{{\boldsymbol c}^1_{y_i},\dots,{\boldsymbol c}^M_{y_i}\}$. The exchanging process can be formulated as:
\begin{align}
\forall j\in\{1,\dots,M\},\hat{\boldsymbol f}_i^j\triangleq
\left\{
\begin{aligned}
{\boldsymbol f}_i^j,\quad\text{if }\xi_j\ge 0.5,\\
{\boldsymbol c}^j_{y_i},\quad\text{otherwise,}
\end{aligned}
\right.
\end{align}
where $\xi_j\sim{\mathcal B}(0.5)$ is a random variable following the Bernoulli distribution for the $j$-th part. The local features after exchanging are denoted as $\hat{\mathcal G}_i=\{\hat{\boldsymbol f}_i^1,\dots,\hat{\boldsymbol f}_i^M\}$ and fed into the hashing learning module for generating binary codes and computing similarity preservation losses.

\subsection{Hash Code Learning}

After obtaining both global features and local features, we concatenate them together and feed them into the hashing learning module. Specifically, the hashing network contains a fully connected layer and a $\mathtt{sign}(\cdot)$ activation function layer. In our method, we choose an asymmetric hashing for ExchNet for its flexibility~\cite{powerofasym}. Concretely, we utilize two hash functions, defined as $g(\cdot)$ and $h(\cdot)$, to learn two different binary codes for the same training sample. The learning procedure is as follows:
\begin{align}
{\boldsymbol u}_i=g([\hat{\mathcal G}_{i};{\boldsymbol f}^{\rm global}_i]_{\cat})=\mathtt{sign}({\boldsymbol W}^{(g)}[\hat{\mathcal G}_{i};{\boldsymbol f}^{\rm global}_i]_{\cat}),\\
{\boldsymbol v}_i=h([\hat{\mathcal G}_{i};{\boldsymbol f}^{\rm global}_i]_{\cat})=\mathtt{sign}({\boldsymbol W}^{(h)}[\hat{\mathcal G}_{i};{\boldsymbol f}^{\rm global}_i]_{\cat}),
\end{align}
where $[;]_{\rm{cat}}$ denotes the concatenation operator, and ${\boldsymbol u}_i,{\boldsymbol v}_i\in\{-1,+1\}^{q}$ denote the two different binary codes of the $i$-th sample. $q$ represents the code length. ${\boldsymbol W}^{(g)}$ and ${\boldsymbol W}^{(h)}$ present the parameters of hash functions $g(\cdot)$ and $h(\cdot)$\footnote{\scriptsize We omit the bias term for simplicity.}, respectively. We denote ${\boldsymbol U}=\{{\boldsymbol u}_i\}_{i=1}^{n}$ and ${\boldsymbol V}=\{{\boldsymbol v}_i\}_{i=1}^{n}$ as learned binary codes. Inspired by~\cite{ADSH:conf/aaai/JiangL18}, we only keep binary codes ${\boldsymbol v}_i$ and set hash function $h(\cdot)$ implicitly. Hence, we can perform feature learning and binary codes learning simultaneously.

To preserve the pairwise similarity, we adopt the squared loss and define the following objective function:
\begin{align}
{\mathcal L}_{\sq}({\boldsymbol u}_i,{\boldsymbol v}_j,\bm{{\mathcal C}})=\big({\boldsymbol u}_i^\top{\boldsymbol v}_j-qS_{ij}\big)^2,
\end{align}
where ${\boldsymbol u}_i=g([\hat{\mathcal G}_{i};{\boldsymbol f}^{\rm global}_i]_\cat)$, $S_{ij}$ is the pairwise similarity label and $\bm{{\mathcal C}}=\{{\mathcal C}_i\}_{i=1}^M$. We use $\Theta$ to denote the parameters of deep neural network and hash layer. The aforementioned process is generally illustrated by Figure~\ref{fig:exchange}.

Due to the zero-gradient problem caused by the $\mathtt{sign}(\cdot)$ function, $L_\sq(\cdot,\cdot,\cdot)$ becomes intractable to optimize. In this paper, we relax $g(\cdot) = \mathtt{sign}(\cdot)$ into $\tilde g (\cdot)=\mathtt{tanh}(\cdot)$ to alleviate this problem. Then, we can derive the following loss function:
\begin{align}
\tilde {\mathcal L}_\sq(\tilde{\boldsymbol u}_i,{\boldsymbol v}_j,\bm{{\mathcal C}})=\big(\tilde{\boldsymbol u}_i^\top{\boldsymbol v}_j-qS_{ij}\big)^2,\label{eq:sq-loss}
\end{align}
where $\tilde{\boldsymbol u}_i=\tilde g([\hat{\mathcal G}_i;{\boldsymbol f}^{\rm global}_i]_\cat)$ and ${\boldsymbol U}$ becomes $\tilde{\boldsymbol U}=\{\tilde{\boldsymbol u}_i\}_{i=1}^n$.

Then, given a set of image samples ${\mathcal X}=\{{\boldsymbol x}_1,\dots,{\boldsymbol x}_n\}$ and their pairwise labels ${\boldsymbol S}=\{S_{ij}\}_{i,j=1}^n$, we can get the following objective function by combining Equation~(\ref{eq:sp-loss}),~(\ref{eq:cp-loss}) and~(\ref{eq:sq-loss}):
\begin{align}\label{pro:obj}
\min_{{\boldsymbol V},\Theta,\bm{{\mathcal C}}}&\;{\mathcal L}({\mathcal X})=\sum_{i,j=1}^n\tilde {\mathcal L}_{\sq}(\tilde{\boldsymbol u}_i,{\boldsymbol v}_j;S_{ij})+\lambda\sum_{i=1}^n{\mathcal L}_{\sp}({\boldsymbol x}_i)+\gamma\sum_{i=1}^n{\mathcal L}_{\cp}({\boldsymbol x}_i)\\
\mathtt{s.t.}\ &\forall i\in\{1,\dots,n\},\hat{\boldsymbol u}_i=\hat g([\hat{\mathcal G}_{i};{\boldsymbol f}^{\rm global}_i]_\cat),{\boldsymbol v}_j\in\{-1,+1\}^q,\nonumber
\end{align}
where $S_{ij}$ represents the similarity between the $i$-th and $j$-th samples, $q$ denotes the code length, $\lambda$ and $\gamma$ are hyper-parameters.

\iffalse
\begin{algorithm}[t]
\DontPrintSemicolon
\caption{Learning algorithm for our proposed method.}
\label{algo:ours}
\SetAlgoLined
\KwIn{${\boldsymbol X}$: image set; ${\boldsymbol y}$: image labels.}
\KwOut{$\Theta$: parameters of DNN; ${\boldsymbol V}$: binary codes.}
{\bf Initialization}: initialize $\Theta$, mini-batch size $M$.\;
\For{$t=1\mapsto T_{max}$}{
	\tcc{Update parameter $\Theta$.}
	\For{$k=1\mapsto \#epochs$}{
		\For{$m=1\mapsto M$}{
			Sample a mini-batch samples from ${\boldsymbol X}$.\;
			Calculate $\hat{\boldsymbol u}_i$ by forward propagation.\;
			Calculate the gradient according to Equation~(\ref{sol:graident}).\;
			Update parameter $\Theta$ by back-propagation.\;
	    }
    }
    \tcc{Update parameter ${\boldsymbol V}$.}
	\For{$k=1\mapsto q$}{
		Update ${\boldsymbol V}_{*k}$ according to update rule in Equation~(\ref{sol:Vk}).\;
    }
    \tcc{Update parameter $\bm{{\mathcal C}}$.}
	\For{$\forall {\mathcal C}_i\in\bm{{\mathcal C}}$}{
		Update ${\boldsymbol C}_i$ according to update rule in Equation~(\ref{sol:Ci}).\;
    }
}
\end{algorithm}
\fi

\subsection{Learning Algorithm}

To solve the optimization problem in Equation~(\ref{pro:obj}), we design an alternating algorithm to learn ${\boldsymbol V}$, $\Theta$, and $\bm{{\mathcal C}}$. Specifically, we learn one parameter with the others fixed.

\subsubsection{Learn $\Theta$ with ${\boldsymbol V}$ and ${\mathcal C}$ fixed}
When ${\boldsymbol V}$, ${\mathcal C}$ fixed, we use back-propagation~(BP) to update the parameters $\Theta$. In particular, for input sample ${\boldsymbol x}_i$, we first calculate the following gradient:
\begin{align}
\nabla_\Theta{\mathcal L}({\boldsymbol X})=	\sum_{i,j=1}^n\nabla_\Theta {\mathcal L}_\sq(\hat{\boldsymbol u}_i,{\boldsymbol v}_j)+\lambda\sum_{i=1}^n\nabla_\Theta {\mathcal L}_\sp({\boldsymbol x}_i)+\gamma\sum_{i=1}^n\nabla_\Theta {\mathcal L}_\cp({\boldsymbol x}_i).\label{sol:graident}
\end{align}
Then, we use the back-propagation algorithm to update $\Theta$.

\subsubsection{Learn ${\boldsymbol V}$ with $\Theta$ and ${\mathcal C}$ fixed}
When $\Theta$, ${\mathcal C}$ are fixed, we rewrite ${\mathcal L}({\boldsymbol V})$ as follows:
\begin{align}
{\mathcal L}({\boldsymbol V})
&=\sum_{i,j=1}^n\big(\hat{\boldsymbol u}_i^\top{\boldsymbol v}_j-qS_{ij}\big)^2=\Vert\widetilde{\boldsymbol U}{\boldsymbol V}^\top-q{\boldsymbol S}\Vert^2_F\\
&=\Vert\widetilde{\boldsymbol U}{\boldsymbol V}^\top\Vert^2_F-2q\mathrm{tr}({\boldsymbol S}^\top\widetilde{\boldsymbol U}{\boldsymbol V}^\top)+\const.
\end{align}

Because ${\boldsymbol V}$ is defined over $\{-1,+1\}^{n\times q}$, we learn ${\boldsymbol V}$ column by columns as that in ADSH~\cite{ADSH:conf/aaai/JiangL18}. Specifically, we can get the closed-form solution for the $k$-th column ${\boldsymbol V}_{*k}$ as follows:
\begin{align}
{\boldsymbol V}_{*k}=\mathtt{sign}({\boldsymbol V}_{/k}\widetilde{\boldsymbol U}_{/k}^\top\widetilde{\boldsymbol U}_{*k}-2q{\boldsymbol Q}_{*k}),\label{sol:Vk}
\end{align}
where ${\boldsymbol Q}={\boldsymbol S}^\top\widetilde{\boldsymbol U}$.

\subsubsection{Learn $\bm{{\mathcal C}}$ with ${\boldsymbol V}$ and $\Theta$ fixed}
When $\Theta$, ${\boldsymbol V}$ fixed, we use the following equation to update each ${\mathcal C}_i\in\bm{{\mathcal C}}$:
\begin{align}
\forall k,{\boldsymbol c}^k_i=\frac{1}{n_i}\sum_{i=1}^{n_{i}}{\boldsymbol f}^k_i,\label{sol:Ci}
\end{align}
where $n_i$ denotes the number of samples in class $y_i$.

\subsection{Out-of-Sample Extension}
When we finish the training phase, we can generate the binary code for the sample ${\boldsymbol x}_i$ by ${\boldsymbol u}_i=\mathtt{sign}({\boldsymbol W}^{(g)}[{\mathcal G}_{i};{\boldsymbol f}^{\rm global}_i]_\cat)$.

\section{Experiments}

\subsection{Datasets}
For comparisons, we select two widely used fine-grained datasets, \text{i.e.}, {\textit{CUB}}\xspace~\cite{CUB:journals/CalTech/WBSWPB2011} and {\textit{Aircraft}}\xspace~\cite{AirCraft:journals/corr/MajiRKBV13}, as well as three popular large-scale fine-grained datasets, \text{i.e.}, {\textit{NABirds}}\xspace~\cite{NABirds:conf/cvpr/HornBFHBIPB15}, {\textit{VegFru}}\xspace~\cite{VegFru:conf/iccv/HouFW17}, and {\textit{Food101}}\xspace~\cite{Food101:conf/eccv/BossardGG14}, to conduct experiments.

Specifically, {\textit{CUB}}\xspace is a bird classification benchmark dataset containing $11,788$ images from 200 bird species. It is officially split into $5,994$ for training and $5,794$ for test.
{\textit{Aircraft}}\xspace contains $10,000$ images from $100$ kinds of aircraft model variants with $6667$ for training and $3333$ for test.
Moreover, for large-scale datasets, {\textit{NABirds}}\xspace has $555$ common species of birds in North America with $23,929$ training images and $24,633$ test images.
{\textit{VegFru}}\xspace is a large-scale fine-grained dataset covering vegetables and fruits from $292$ categories with $29,200$ for training and $116,931$ for test
{\textit{Food101}}\xspace contains $101$ kinds of foods with $101,000$ images. For each class, $250$ test images are manually reviewed for correctness while $750$ training images still contain some amount of noises.

\subsection{Baselines and Implementation Details}
\subsubsection{Baselines}
For comparisons with other ANN algorithms, we select two tree-based ANN methods, i.e., BallTree~\cite{BallTree:journals/corr/DolatshahHM15} and KDTree~\cite{KDTree:journals/cacm/Bentley75}, and one production quantization based ANN method, i.e., Product Quantization~(PQ)~\cite{PQ:journals/pami/JegouDS11}. The linear scan means that we directly perform exhaustive search based on the learned real-valued features.
For comparisons with other hashing baselines, we choose eight state-of-the-art generic hashing methods. They are LSH~\cite{LSH:conf/compgeom/DatarIIM04}, SH~\cite{SH:conf/nips/WeissTF08}, ITQ~\cite{ITQ:conf/cvpr/GongL11}, SDH~\cite{SDH:conf/cvpr/ShenSLS15}, DPSH~\cite{DPSH:conf/ijcai/LiWK16}, DSH~\cite{DSH:conf/cvpr/Liu0SC16}, HashNet~\cite{Hashnet:conf/iccv/CaoLWY17}, and ADSH~\cite{ADSH:conf/aaai/JiangL18}. Among these methods, DPSH, DSH, HashNet and ADSH are based on deep learning and others are not.

\subsubsection{Implementation Details}
For comparisons with other ANN algorithms, we carry out experiments on {\textit{Food101}}\xspace in which the database is the largest. We first utilize the triplet loss~\cite{tripletloss} to learn $512$-D and $1024$-D feature embeddings for its frequent usages in fine-grained retrieval tasks. Then, the performance of linear scan is tested on the learned features. More experimental settings about BallTree~\cite{BallTree:journals/corr/DolatshahHM15}, KDTree~\cite{KDTree:journals/cacm/Bentley75} and PQ~\cite{PQ:journals/pami/JegouDS11} can be found in the supplementary materials.
For our ExchNet, the retrieval procedure is divided into coarse ranking to select top~$N$ as candidates and re-ranking to return top~$K$~($K<N$) from top~$N$ candidates. We adopt the real-valued features learned with the triplet loss directly.
As presented in Table~\ref{tab:retrieval}, we report results including precision at top~$K$~(P@K), wall clock time~(WC time), speed up ratio, and memory cost.

Our backbone employs the first three stages of ResNet50 and the attention generation module is the fourth stage of ResNet50 without downsample convolutions. The LFR and GFR of ExchNet are independent networks, sharing the same architecture with the fourth stage of ResNet50. The optimizer is standard mini-batch stochastic gradient descent with weight decay $1\times 10^{-4}$. The mini-batch size $M$ is set to 64 and the iteration times $T_{max}$ is 100. Learning rate is set to 0.001, which is divided by 10 at the 60-th and 80-th iteration, respectively. The hyper-parameter $t$ is set to $0.4$. The number of training epochs is 20. For efficient training, we randomly sample a subset of the training set in each epoch. Specifically, for {\textit{CUB}}\xspace, {\textit{Aircraft}}\xspace, {\textit{Food101}}\xspace, we sample 2,000 samples per epoch, while 4,000 samples are randomly selected for other datasets. To provide reliable local features for our local feature alignment strategy, in the first 50 iterations, since both local and global features are not well learned, the part-level feature exchanging operation is disabled for avoiding aligning meaningless local features.

\subsection{Comparisons with other ANN Methods} \label{sec:speedup}

To prove the practicality and effectiveness of our proposed method, comparisons with other ANN methods are presented in this section. All experiments are conducted based on hash codes of $32$bits generated by our model.

In Table~\ref{tab:retrieval}, we present the retrieval performance on the {\textit{Food101}}\xspace dataset. Specifically, we present the P@10, WC time, speedup, and memory cost for all methods.
We can observe that, compared with the linear search, our method can achieve up to $233\times$ and $395\times$ acceleration on features of $512$-D and $1024$-D, respectively. The memory cost of our method is also much less than tree-based methods.
The best speed-up and the lowest storage usage prove the practicality of our proposed method.
Meanwhile, our method can achieve state-of-the-art retrieval accuracies, which demonstrates that our ExchNet is the most effective one compared with other ANN methods.
Above results illustrate our ExchNet deserves to be the optimal choice for fine-grained image retrieval.

\begin{table}[t]
\scriptsize
\centering
\caption{Retrieval performance comparisons on the {\textit{Food101}}\xspace dataset.}
\setlength{\tabcolsep}{1pt}
\label{tab:retrieval}
\begin{tabular}{l|cccc|cccc}
\hline
\multirow{2}{*}{Method} &  \multicolumn{4}{c|}{512-dim}&  \multicolumn{4}{c}{1024-dim}\\\cline{2-9}
            &P@10($\uparrow$)           & WCtime($\downarrow$)         & Speedup($\uparrow$)              & Memory($\downarrow$) &P@10($\uparrow$)           & WCtime($\downarrow$)         & Speedup($\uparrow$)              & Memory($\downarrow$) \\ \hline
Linear & 80.05\%        &9,481.03       & $1\times$            &  207.2MB    & 80.28\%        &22,377.96      & $1\times$            &  414.1MB    \\ \hline
BallTree   & 77.22\%        &236.23         & $40.13\times$        &  28.1MB     & 77.74\%        &213.88         & $104.62\times$     &  28.1MB     \\
KDTree     & 77.42\%        &70.16          & $135.13\times$       &  28.8MB     & 77.73\%        &73.57          & $304.14\times$     &  28.7MB     \\
PQ          & 77.12\%        &43.49          & $217.99\times$       &  524.5KB    & 77.18\%        &72.47          & $308.74\times$     &  1.0MB      \\\hline
\textbf{Ours}         & \textbf{77.69\%}        &\textbf{40.54}          & $\bm{233.85}\times$       &  \textbf{404.0KB}    & \textbf{78.06\%}        &\textbf{56.57}          & $\bm{395.53}\times$     &  \textbf{404.0KB}    \\
\hline
\end{tabular}
\end{table}

\begin{table*}[t]
\scriptsize
\centering
\caption{Comparisons of retrieval accuracy~(MAP) on all the fine-grained datasets.}
\label{tab:acc-hash}
\begin{tabular}{C{1.3cm}|R{0.9cm}|R{0.9cm}|R{0.9cm}|R{0.9cm}|R{0.9cm}|R{0.9cm}|R{0.9cm}|R{1.1cm}|R{0.9cm}|R{0.9cm}}
\hline
Method    & \makecell[c]{\#Bits}  & \makecell[c]{LSH}& \makecell[c]{SH}&  \makecell[c]{ITQ}&  \makecell[c]{SDH}&  \makecell[c]{DPSH}&  \makecell[c]{DSH}& \makecell[c]{HashNet}& \makecell[c]{ADSH}& \makecell[c]{\textbf{Ours}}\\
\hline
\multirow{4}*{{\textit{CUB}}\xspace}
          & 12bits  & 2.26\%  & 5.55\%  & 6.80\%  & 10.52\%  & 8.68\%  & 4.48\% 	& 12.03\%  & 20.03\%  &{\bf 25.14\%}\\
          & 24bits  & 3.59\%  & 6.72\%  & 9.42\%  & 16.95\%  & 12.51\%  & 7.97\%  & 17.77\%  & 50.33\%  &{\bf 58.98\%}\\
          & 32bits  & 5.01\%  & 7.63\%  & 11.19\%  & 20.43\%  & 12.74\%  & 7.72\% 	& 19.93\%  & 61.68\%  &{\bf 67.74\%}\\
          & 48bits  & 6.16\%  & 8.32\%  & 12.45\%  & 22.23\%  & 15.58\%  & 11.81\%  & 22.13\%  & 65.43\%  &{\bf 71.05\%}\\
\hline
\multirow{4}*{{\textit{Aircraft}}\xspace}
          & 12bits  & 1.69\%  & 3.28\% 	& 4.38\%  & 4.89\% 	& 8.74\%  & 8.14\% 	& 14.91\%  & 15.54\% 	&{\bf 33.27\%}\\
          & 24bits  & 2.19\%  &	3.85\% 	& 5.28\%  &	6.36\% 	& 10.87\%  &	10.66\% 	& 17.75\%  &	23.09\% 	&{\bf 45.83\%}\\
          & 32bits  & 2.38\%  &	4.04\% 	& 5.82\%  &	6.90\% 	& 13.54\%  &	12.21\% 	& 19.42\%  &	30.37\% 	&{\bf 51.83\%}\\
          & 48bits  & 2.82\%  &	4.28\%	& 6.05\%  &	7.65\%  & 13.94\%  &	14.45\%  & 20.32\%  &	50.65\%  &{\bf 59.05\%}\\
\hline
\multirow{4}*{{\textit{NABirds}}\xspace}
          & 12bits  & 0.90\%  & 2.12\%  & 2.53\%  & 3.10\% 	& 2.17\%  & 1.56\% 	& 2.34\%  & 2.53\% 	&{\bf 5.22\%}\\
          & 24bits  & 1.68\%  & 3.14\% 	& 4.22\%  &	6.72\% 	& 4.08\%  &	2.33\% 	& 3.29\%  &	8.23\% 	&{\bf 15.69\%}\\
          & 32bits  & 2.43\%  & 3.71\% 	& 5.38\%  &	8.86\% 	& 3.61\%  &	2.44\% 	& 4.52\%  &	14.71\% 	&{\bf 21.94\%}\\
          & 48bits  & 3.09\%  &	4.05\% 	& 6.10\%  &	10.38\% 	& 3.20\%  &	3.42\% 	& 4.97\%  &	25.34\% 	&{\bf 34.81\%}\\
\hline
\multirow{4}*{{\textit{VegFru}}\xspace}
          & 12bits  & 1.28\%  & 2.36\% 	& 3.05\%  & 5.92\% 	& 6.33\%  & 4.60\% 	& 3.70\%  & 8.24\% 	&{\bf 23.55\%}\\
          & 24bits  & 2.21\%  &	4.04\% 	& 5.51\%  &	11.55\% 	& 9.05\%  &	8.91\% 	& 6.24\%  &	24.90\% 	&{\bf 35.93\%}\\
          & 32bits  & 3.39\%  &	5.65\% 	& 7.48\%  &	14.55\% 	& 10.28\%  &	11.23\% 	& 7.83\%  &	36.53\% 	&{\bf 48.27\%}\\
          & 48bits  & 4.51\%  &	6.56\% 	& 8.74\%  &	16.45\% 	& 9.11\%  &	17.12\% 	& 10.29\%  &	55.15\% 	&{\bf 69.30\%}\\
\hline
\multirow{4}*{{\textit{Food101}}\xspace}
          & 12bits  & 1.57\%  & 4.51\% 	& 6.46\%  & 10.21\%  & 11.82\%  &	6.51\%  & 24.42\%  &	35.64\% 	&{\bf 45.63\%}\\
          & 24bits  & 2.48\%  &	5.79\%	& 8.20\%  &	11.44\% 	& 13.05\%  & 8.97\% 	& 34.48\%  &	40.93\% 	&{\bf 55.48\%}\\
          & 32bits  & 2.64\%  &	5.91\% 	& 9.70\%  &	13.36\% 	& 16.41\%  &	13.10\% 	& 35.90\%  &	42.89\% 	&{\bf 56.39\%}\\
          & 48bits  & 3.07\%  &	6.63\%  & 10.07\%  &	15.55\%  & 20.06\%  &	17.18\%  & 39.65\%  &	48.81\%  &{\bf 64.19\%}\\
\hline
\end{tabular}
\end{table*}

\subsection{Comparisons with State-of-the-art Hashing Methods}
In Table~\ref{tab:acc-hash}, we present the mean average precision~(MAP) results for comparisons with state-of-the-art hashing methods on all datasets. From Table~\ref{tab:acc-hash}, we can observe that our method can achieve the best retrieval performance in all cases.
On fine-grained datasets~({\textit{CUB}}\xspace and {\textit{Aircraft}}\xspace) of relatively small size, almost all the generic hashing methods (except for ADSH) can not achieve a satisfactory performance, \text{i.e.}, a relatively low MAP. Also, our ExchNet outperforms the most powerful baseline ADSH considerably.
It can verify that given limited training data, our proposed method could still perform well.
As to large-scale fine-grained datasets, the improvements become more significant.
Particularly, comparing with the most powerful baselines, we achieve $12\%$ and $14\%$ MAP improvements on the 32 bits and 48 bits evaluation experiments of the large-scale {\textit{VegFru}}\xspace dataset. Meanwhile, we achieve $14\%$ and $16\%$ MAP improvements on the 32 bits and 48 bits experiments of the {\textit{Food101}}\xspace dataset.
It shows that, with sufficient training data, we can get better retrieval results with our ExchNet on large-scale fine-grained datasets.

\subsection{Ablation Studies}
\subsubsection{Effectiveness of the Exchanging-based Feature Alignment}
We verify the effectiveness of the local feature alignment approach~(cf. Section~\ref{sec:learning_to_align}) in this section. The retrieval accuracy are present in Figure~\ref{fig:ablation}, where ``Ours w/o Exchange'' means that we do not perform the feature exchanging operation (\text{i.e.}, the local feature alignment) during training. Note that ``Ours w/o Exchange'' is degenerated to the ADSH~\cite{ADSH:conf/aaai/JiangL18} learned with our proposed representation learning architecture instead of ResNet50. Hence, we also present the results of ADSH.

It can be observed that our method can achieve the best accuracy thanks to the feature exchanging operation. Specifically, on {\textit{CUB}}\xspace and {\textit{Aircraft}}\xspace datasets, our proposed method with the exchanging operation performs considerably better than that without exchanging.
The performance improvement on the large-scale fine-grained datasets~(\text{e.g.}, {\textit{Food101}}\xspace) becomes more significant.
Above results illustrate that our proposed local features alignment strategy is effective, especially on large-scale datasets. Moreover, even if bits of hash codes are limited, our feature alignment strategy could still benefit fine-grained retrieval greatly.

\begin{figure*}[t]
\centering
\begin{tabular}{c@{ }@{ }c@{ }@{ }c@{ }@{ }c}
\begin{minipage}{0.32\linewidth}\centering
    \includegraphics[width=1\textwidth]{figs/param/cub-exchange.pdf}\\%\vspace{-5pt}
    {\scriptsize(a) {\textit{CUB}}\xspace}
\end{minipage} &
\begin{minipage}{0.32\linewidth}\centering
    \includegraphics[width=1\textwidth]{figs/param/aircraft-exchange.pdf}\\%\vspace{-5pt}
    {\scriptsize(b) {\textit{Aircraft}}\xspace}
\end{minipage}&
\begin{minipage}{0.32\linewidth}\centering
    \includegraphics[width=1\textwidth]{figs/param/food-exchange.pdf}\\%\vspace{-5pt}
    {\scriptsize(c) {\textit{Food101}}\xspace}
\end{minipage}
\end{tabular}
\caption{Effectiveness of our feature exchanging operation.}
\label{fig:ablation}
\end{figure*}

\begin{figure*}[t]
\centering
\begin{tabular}{c@{ }@{ }c@{ }@{ }c@{ }@{ }c}
\begin{minipage}{0.32\linewidth}\centering
    \includegraphics[width=1\textwidth]{figs/param/cub-M.pdf}\\%\vspace{-5pt}
    {\scriptsize(a) {\textit{CUB}}\xspace}
\end{minipage} &
\begin{minipage}{0.32\linewidth}\centering
    \includegraphics[width=1\textwidth]{figs/param/aircraft-M.pdf}\\%\vspace{-5pt}
    {\scriptsize(b) {\textit{Aircraft}}\xspace}
\end{minipage}&
\begin{minipage}{0.32\linewidth}\centering
    \includegraphics[width=1\textwidth]{figs/param/food-M.pdf}\\%\vspace{-5pt}
    {\scriptsize(c) {\textit{Food101}}\xspace}
\end{minipage}
\end{tabular}
\caption{Influence of hyper parameter $M$ which denotes the number of local features.}
\label{fig:M}
\end{figure*}

\subsubsection{Sensitivity to Hyper Parameter $M$}
In our ExchNet, we use $M$ to denote the number of local features, which is also the number of attention maps. In this section, we present the influence of the hyper-parameter $M$ by ablation studies.

As presented in Figure~\ref{fig:M}, we vary $M$ as $2$, $4$ and $6$. From that figure, it is observed that satisfactory retrieval accuracies are achieved regardless of different $M$ values, and the best fine-grained retrieval accuracy is obtained when $M=4$. As analyzed, redundant local features~(\text{i.e.}, overmuch object parts when $M$ is large) might cause redundancies in local feature representations, while the lack of local features~(\text{i.e.}, scant object parts when $M$ is small) may result in that fine-grained images are under-represented for distinguishing subtle visual differences. Those might be the reasons why $M$ is too small or large will cause slightly accuracy drops. Moreover, comparable retrieval results of different $M$ values show that our ExchNet is not sensitive to $M$.

\iffalse
\begin{figure*}[tb]
\centering
\begin{tabular}{c@{ }@{ }c@{ }@{ }c@{ }@{ }c}
\begin{minipage}{0.22\linewidth}\centering
    \includegraphics[width=1\textwidth]{figs/cub.pdf}\\%\vspace{-5pt}
    {\scriptsize(a) {\textit{CUB}}\xspace}
\end{minipage} &
\begin{minipage}{0.22\linewidth}\centering
    \includegraphics[width=1\textwidth]{figs/aircraft.pdf}\\%\vspace{-5pt}
    {\scriptsize(b) {\textit{Aircraft}}\xspace}
\end{minipage}&
\begin{minipage}{0.22\linewidth}\centering
    \includegraphics[width=1\textwidth]{figs/vegfru.pdf}\\%\vspace{-5pt}
    {\scriptsize(c) {\textit{VegFru}}\xspace}
\end{minipage}&
\begin{minipage}{0.22\linewidth}\centering
    \includegraphics[width=1\textwidth]{figs/food.pdf}\\%\vspace{-5pt}
    {\scriptsize (d) {\textit{Food101}}\xspace}
\end{minipage}
\end{tabular}
\caption{Visualization results. In each subfigure, each row is an image of a category and each column presents learned attentive parts~(highlighted by red) by our ExchNet.}
\label{fig:visual}
\end{figure*}
\fi

\section{Conclusions}

In this paper, we studied the practical but challenging fine-grained hashing task, which aims to solve large-scale FGIR problems by leveraging the search and storage efficiency of compact hash codes. Specifically, we proposed a unified network ExchNet to obtain representative fine-grained local and global features by performing our attention approach equipped with the tailored attention constraints. Then, ExchNet utilized its local feature alignment to align these local features to their corresponding object parts across images. Later, an alternating learning algorithm was employed to return the final fine-grained binary codes. Compared with ANN methods and competing generic hash methods, experiments validated both effectiveness and efficiency of our ExchNet. In the future, we would like to explore a more challenging unsupervised fine-grained hashing topic. \\

\noindent\textbf{Acknowledgements} Q. Cui's contribution was made when he was an intern at Megvii Research Nanjing. This research was supported by the National Key Research and Development Program of China under Grant 2017YFA0700800 and ``111'' Program B13022.

\clearpage
\bibliographystyle{splncs04}


\section{Introduction}
\label{intro}
\blfootnote{
    %

    %

    %

    %

    \hspace{-0.65cm}
    This work is licensed under a Creative Commons
    Attribution 4.0 International License.
    License details:
    \url{http://creativecommons.org/licenses/by/4.0/}.\\
    $\ast$ The first three authors contributed equally.
}

Online social media has become one of the most important means of communication. Unfortunately, the discourse is often laden with abusive language that can have damaging effects on social media users \cite{zampieri2019predicting}.
As online abuse grows as a serious social problem, many social media platforms are employing human moderators to track inappropriate contents and comments.
However, such human moderation comes at the cost of additional operation and the mental suffering of the workers \cite{roberts2014behind,dosono2019moderation}.
In response, the automatic identification of offensive language has been a rising area of interest to both academia and industry.
Computational methods presented in several prior studies  \cite{park-fung-2017-one,DBLP:journals/corr/abs-1801-04433,wulczyn2017ex,founta2018large} have shown promising results on how we can automatically detect a large number of offensive contents with minimal human intervention.

As an effort to promote this line of research, OffensEval was organized at SemEval-2019 \cite{zampieri2019semeval}.
The organizers released a dataset, Offensive Language Identification dataset (OLID), that contains English tweets with human annotations over three sub-tasks: 1) whether a tweet is offensive or not, 2) whether an offensive tweet is targeted or not, and if so 3) whether the target is an individual or a group.
The second edition of OffensEval, OffensEval 2020 : Multilingual Offensive Language Identification in Social Media, holds the same task but extends the OLID to multiple languages (English, Arabic, Danish, Greek, and Turkish) \cite{zampieri-etal-2020-semeval}.

This paper describes our system, NLPDove, submitted to OffensEval 2020 . We present two different data augmentation strategies. First, for English, we augment the training set with reliable samples filtered out from the provided semi-supervised dataset. Second, we use samples from languages other than the target language to enhance performance in the target language, namely cross-lingual transfer. Specifically, we propose a new metric, Translation Embedding Distance(\texttt{TED}), to measure the data transferability of each example in the data.
We use the metric to effectively select additional training data samples from other available transfer languages.
We also introduce various preprocessing steps to extract meaningful information from user-generated texts despite their inherently noisy nature. Our model is based on the multilingual pre-trained language model, particularly multilingual BERT (mBERT) \cite{devlin-etal-2019-bert}. Our final submitted model is an ensemble of multiple mBERT models with different pooling mechanisms, representation layers and randoms seeds.
Our submission achieved macro F1 of 0.85 in Greek (1st/38), 0.79 in Danish (3rd/40), 0.80 in Turkish (5th/47), 0.91 in English (15th/86), and 0.80 in Arabic (20th/54).
\footnote{The code for our system can be found at \url{https://github.com/hwijeen/OffensEval2020}}

In the remainder of this paper, we first describe the dataset and the task of OffensEval 2020  (\Sref{sec:data}).
We then present our method, including the data augmentation strategies, preprocessing pipeline, and model architecture (\Sref{sec:method}).
The evaluation results of our final submission are reported along with other experiments to further investigate the effectiveness of our method (\Sref{sec:results}).
We then discuss our findings and negative results to shed light on the limitations and remaining challenges in the current offensive language identification models (\Sref{sec:analysis_discussion}).
Finally, we review related work (\Sref{sec:rw}) and conclude (\Sref{sec:conclusion}).

\section{Data}
\label{sec:data}
The most noticeable update in OffensEval 2020  is the extension of the task to four additional languages other than English: Arabic \cite{mubarak2020arabic}, Danish \cite{sigurbergsson2020offensive}, Greek \cite{pitenis2020}, and Turkish \cite{coltekikin2020}.
This change facilitates the research of offensive language identification in multiple languages, and also enables researchers to explore the feasibility of cross-lingual approaches of the task.
One thing to note is that unlike English tweets which had annotations for all three sub-tasks, the four new languages do not have all of them; they are only annotated on the first sub-task, which tells whether they are offensive or not.

In the case of English, in addition to the manually annotated tweets from the previous workshop \cite{zampieri2019predicting}, OffensEval 2020  released a large semi-supervised dataset where samples are labeled by a set of trained models, not by human annotators \cite{rosenthal2020}.
Therefore, the labels are not binary but given as floating-point numbers between 0 and 1 (i.e. the average score of multiple models), with their standard deviation indicating the confidence level among classifiers. For further details regarding the data, we refer to the original paper \cite{rosenthal2020}. The summary statistics of the dataset are presented in \Tref{tab:data_stat}.

\section{Method}
\label{sec:method}
There are three important components in our system: training data augmentation, extensive preprocessing, and model ensembling. The following subsections describe each part in detail.

\begin{table}[t]
\begin{minipage}{.5\linewidth}
\centering
\begin{tabular}{@{}lccc@{}}
\toprule
Language    & Train size & Valid size  & OFF:NOT    \\ \midrule
Arabic      &    7202    &   800       &    0.25  \\
Danish      &   2666     &    296      &    0.15 \\
English     &   12691    &     1411    &    0.49  \\
Greek       &   7871     &      874    &    0.40     \\
Turkish     &   28582    &     3176    &    0.24  \\
English-semi & 9M & - & - \\
\bottomrule
\end{tabular}
\caption{Summary statistics of the dataset. English-semi denotes the semi-supervised English dataset. For English, we also used the OLID from OffensEval 2019 \cite{zampieri2019predicting}. We randomly split the provided data into train and validation set by 9:1. }
\label{tab:data_stat}
\end{minipage}\quad
\begin{minipage}{.47\linewidth}
\centering
\begin{tabular}{@{}lcc@{}}
\toprule
Preprocessing               & \# of Cases  \\ \midrule
Emoji substitution          &    1454               \\
Hashtag segmentation        &             2290      \\
Letter casing normalization &             12665      \\
URL replacement             &             2140      \\
Punctuation trimming        &            504       \\ \bottomrule
\end{tabular}
\caption{Preprocessing methods and the number of examples modified by each method in the English training data.}
\label{tab:preprocessing}
\end{minipage}
\end{table}

\subsection{Data Augmentation}
mBERT and other large-scale pre-trained language models are known for their massive number of parameters \cite{conneau2019cross}.
Thus, they require a substantial amount of data to be fine-tuned sufficiently to the downstream task.
And yet, the dataset in hand may not be large enough, especially for some languages due to the expensive annotation process.
To alleviate this data sparsity issue, we propose two data augmentation approaches to make most of the provided semi-supervised labels and multilingual data.

\paragraph{Semi-supervised Labels}
It has become a common practice to augment training data with machine annotated or synthetic labels when the training data is insufficient \cite{sennrich-etal-2016-improving}.
There is almost an infinite number of unlabeled Twitter data available, many of which contain offensive languages.
One way to obtain a substantial amount of pseudo-labels is to predict unlabeled tweets with models trained with existing labeled data.
OffensEval 2020  released over nine million English tweets labeled in this semi-supervised manner \cite{rosenthal2020}.
Each sample was given with its average label probability from several trained models and the standard deviation of the probabilities which indicates the confidence level.
One practical question lies in how to utilize this data while reducing the effect of noisy labels and controlling the data quality.
One straightforward approach is to set certain thresholds to filter out the uncertain examples.
We investigate different thresholding strategies with respect to the two measures, the average probability and the standard deviation.

\paragraph{Cross-lingual Data Selection}
Multilingual pre-trained language models allow seamless cross-lingual transfer; they map texts in different languages into the same representation space without introducing extra costs.
Cross-lingual transfer can be especially helpful when the training data is limited for the target language, i.e., low-resource settings.
Transferring examples from high-resource languages to low-resource languages often results in great improvements \cite{DBLP:journals/corr/ChenASWC16,DBLP:journals/corr/XuY17a}.

Although it is clear that cross-lingual transfer can be of help, the question of which data to additionally use remains an open problem.
Should we use the entire dataset, or is there a subset better than the entire dataset?
We hypothesize that not all samples in the same transfer language will be equally helpful to the target language task, leading to the conclusion that a carefully selected subset will give higher performance gain than using the whole dataset.

To address the \textit{how} part of data selection, we propose a new metric, translation embedding distance (\texttt{TED}), to quantify the \textit{transferability} of a data sample or a language.
We first define a sample's transferability as how useful the transfer language sample is when transferred to the target language task.
Here, we hypothesize that transferability as a concept correlates with \textit{translatability};
if a sentence is easily translated to the target language, it is more likely to be a useful training sample.
To measure \texttt{TED}, we follow the three steps: first, we (machine) translate the training samples in transfer languages into the target language.\footnote{We used Google Translate in our experiments.}
Then, we extract sentence embeddings for both the original sentence and its translation using mBERT. More specifically, we applied mean pooling over the second-to-last (penultimate) layer of mBERT and used it as the sentence embedding.
Finally, we measure the L2 distance between the two representations and refer to it as the \texttt{TED} of the instance.
The transferability of a \emph{language}, which we define as language-level \texttt{TED}, is simply the average of instance-level \texttt{TED} of samples in the transfer language.

We can then rank transfer samples according to their \texttt{TED} scores and choose top-$k$ samples with the lowest distance.
Likewise, to find the most transferable languages, we can select the top-$k$ languages based on their language-level \texttt{TED} scores.
To verify our hypothesis that adding samples in other languages can enhance performance in the target language task, we investigate the effectiveness of both language-level and instance-level data selection in \Sref{sec:dataaug}.

\subsection{Preprocessing}
User-generated contents are inherently noisy, whereas the pre-trained language models that we use throughout our system are mostly trained with clean texts such as Wikipedia articles and BookCorpus \cite{devlin-etal-2019-bert}.
To minimize the discrepancy, we applied various preprocessing steps to normalize the noisy tweets provided in our dataset.
In particular, we focus on normalizing the unique conventions of tweets (e.g. hashtags, mentions, emojis) and their irregular usage of punctuation and capitalization.
\Tref{tab:preprocessing} lists all of the considered methodologies and the number of cases found for each method in the English data.
Each item is explained in more detail below.

\paragraph{Emoji Substitution}
Although emojis are effective means of expressing sentiments, learning a good representation of emojis with neural models can be challenging due to their low frequency.
Another challenge is that the most pre-trained language models are not acquainted with the use of emojis as the texts used to train them did not contain emojis.
To fully benefit from the knowledge embedded in pre-trained language models, we replaced all emojis with their plain text descriptions (e.g. \smiley{} $\rightarrow$ smiley face) using an off-the-shelf library\footnote{\url{https://github.com/carpedm20/emoji}}.

\paragraph{Hashtag Segmentation}
Hashtags are prevalent in tweets, and they often contain essential information and keywords.
Conventionally, hashtags are prefixed with the \# symbol followed by phrases concatenated without whitespaces.
In order to extract all relevant information from hashtags, we split them into words using a word segmentation toolkit\footnote{\url{http://www.grantjenks.com/docs/wordsegment/}}.
We preserved the \# symbol in the beginning of segmented words to help the model differentiate hashtags from plain texts.

\paragraph{Letter Casing Normalization}
In social media texts, people often use capitalization to express the intensity of their emotions.
For example, ``GET OUT!'' sounds much more intense than ``get out!''.
Although ``GET'' and ``get'', in this case, possess the same meaning and only differ in the degree of emphasis, they will be assigned to completely different tokens if we do not use a canonical form representing both variants.
Keeping the original form may be useful to preserve the richness in expressing emotional intensity, but the embedding quality of the less frequent variants cannot be assured. In this case, ``GET'' would occur much infrequently than ``get'' in the training corpus.
Therefore, we first normalized these casing variations by lowercasing all words. But at the same time, we prepended a special token \texttt{<has\_cap>} when the word contains an uppercase alphabet and \texttt{<all\_cap>} when the entire word was uppercased.

\paragraph{URL Replacement}
Tweets often include raw urls that redirect users to a reference page.
In the provided data, most of the urls were already replaced with two special tokens, \texttt{HTTP} and \texttt{URL}.
We unified them into \texttt{HTTP}, since \texttt{HTTP} is the token used during the pre-training stage of mBERT.

\paragraph{Punctuation Trimming}
One characteristic of social media text is the irregular usage of punctuation marks. For instance, the two sentences ``I am sad.." and ``I am sad........" differ slightly in their use of punctuation marks.
The difference between the two sentences is negligible for a human reader in terms of sentiment. However, their sentence representations may differ significantly since the latter's representation would be diluted with its repeated use of periods. Hence, we limit the maximum number of consecutive punctuation marks to three occurrences.

\subsection{Model}
\label{sec:model}
In our final submission, we used an ensemble of several different mBERT models.
Here, we explain how we selected and ensembled the models.

\paragraph{mBERT}
mBERT is a multilingual extension of BERT which shares the same architecture with BERT  \cite{devlin-etal-2019-bert}.
The main difference is that mBERT was trained on the monolingual corpora in multiple languages with an extended vocabulary, which enables seamless cross-lingual transfer. The model can take inputs in various languages, and we can either jointly train a model with both the transfer and target language or perform zero-shot transfer where the model is trained only with the transfer language.
mBERT is shown to be highly effective in both settings \cite{Pires2019HowMI}, implying the model's ability to learn a universal representation space that is shared across languages.

We took advantage of the multilinguality of mBERT and used it as the main model for our system for all languages.
We added a pooling layer and a linear classifier on top of mBERT for the classification task.
The pooling layer takes mBERT representations of each word and combines them into a fixed-size vector. \footnote{We experimented with mean pooling, max pooling, concatenation of both, and CNN pooling.}
We used the same hyperparameters values provided in \newcite{Wolf2019HuggingFacesTS} except for the learning rate, random seed, and dropout probability.
For the three hyperparameters we tuned, we ran a grid-search to select the best configuration based on the validation set performance.
We note that tuning the random seed, as found in \newcite{Dodge2020FineTuningPL}, resulted in a significant performance gain.

\paragraph{Ensemble}
Model ensemble methods are widely employed to improve a model's robustness and generalization performance.
With this motivation in mind, we developed a pipeline for model ensembling.
We trained multiple BERT-based models for each task that differ by which BERT layer is used for the word representation (last, second-to-last)\footnote{It has been reported that BERT outputs from different layers encode different kinds of information \cite{kovaleva-etal-2019-revealing}. }, pooling mechanism (mean, max, concatenation of both, and CNN), learning rate (1e-5, 1e-6), and also random seeds. We then chose the top three models according to the validation performance. In the case of English, we additionally considered an mBERT model trained with the augmented dataset that incorporates the semi-supervised dataset as described in \Sref{semi-data}. We used majority voting to aggregate the prediction of the selected models for the final prediction.

\section{Experiment Results}
\label{sec:results}

\begin{table}[]
    \centering
    \begin{tabular}{c|c|c|c|c|c}
        \toprule
        \multirow{2}{*}{Model}&\multicolumn{5}{|c}{Language}\\
         & Arabic & Danish & English & Greek & Turkish \\
        \midrule
        mBERT (Single model) & 0.8722 & \textbf{0.7837} & 0.7770 & \textbf{0.8349} & 0.7835\\
        Ensemble & \textbf{0.8775} & 0.7514 & \textbf{0.7822} & 0.8343 & \textbf{0.7970} \\
        \bottomrule
    \end{tabular}
    \caption{Performance of our system on development data. The ensemble model was used for final submission for all languages.}
    \label{tab:main_result}
\end{table}

\subsection{Main Results}
We used a macro-averaged F1 score as our main evaluation metric as in OffensEval 2020.
Table~\ref{tab:main_result} summarizes the performance of our models in the validation data for each target language.
We also report the best performance of a single mBERT model for comparison.
As explained in \Sref{sec:model}, our final submission models used a majority vote ensemble of several mBERT models.

\subsection{Data Augmentation Experiment}
\label{sec:dataaug}

\paragraph{Semi-supervised Labels}
\label{semi-data}
For the English task, we used the human-annotated dataset from OffensEval 2019 as the primary data source and augmented it with the subset of the semi-supervised dataset from OffensEval 2020.
As explained in Section \ref{sec:data}, the semi-supervised labels are the averaged prediction scores of various trained models accompanied by the standard deviation of these scores.

One way to control the quality of the additional data is to filter out noisy data using the prediction confidence score of classifiers and their standard deviation.
For instance, setting the minimum value of the offensive class confidence as 0.9 rather than 0.6 would result in a smaller but more reliable subset.
Similarly, a sample with a lower standard deviation indicates a higher likelihood of multiple models agreeing to its predicted label, thereby more reliable.
We performed a grid search over combinations of threshold values for offensive and non-offensive tweets as well as the standard deviation. In particular, we set the grid with three different threshold parameters:  $t_{\mathrm{off}} \in \{0.8, 0.9\}, t_{\mathrm{not}} \in \{0.2, 0.3\}, t_{\mathrm{std}} \in \{0.1, 0.125\}$.
Data samples are selected when the standard deviation is lower than $t_{\mathrm{std}}$, and its score is either higher than $t_{\mathrm{off}}$ or lower than $t_{\mathrm{not}}$.

The results are summarized in Table~\ref{tab:dist_aug}.
Although varying the threshold resulted in additional data of different qualities and sizes, the difference in results was marginal.
When about 30K samples were added with cut-off values of $t_{\mathrm{off}}=0.8, t_{\mathrm{not}}=0.2, t_{\mathrm{std}}=0.125$, we observed a small performance gain compared to others.
In our final ensemble model, we included the models that performed better than the baseline which was trained solely on the human-annotated dataset.

\paragraph{Cross-lingual Data Transfer}
We first consider language-level cross-lingual transfer strategies. That is, we seek the most effective transfer language for the given target language. To this end, we measure language-level \texttt{TED} for each transfer and target language pair. We then pick top-\textit{k} languages that have high language-level \texttt{TED} score for each target language.

Cross-lingual transfer has been shown to be effective especially when the target language dataset is not sufficient. Our experiments focus on the setting where Danish is the target language as it has the least number of training samples. $k$ was set to 1 for language selection. Results showed that English (9.83) is the most useful transfer language to Danish, followed by Arabic (10.85), Greek (22.02) and Turkish (23.08). The high transferability from English to Danish is probably due to the two languages' surface-level resemblance, which comes from the shared orthography. We note that English turned out to be the most effective language to Danish even in terms of zero-shot transfer performance (trained only on the source language and tested on the target language).

Next, we consider the transfer strategy on a more fine-grained instance-level. We construct a subset of the dataset of the most transferable language based on each sample's transferability.
Specifically, we sort the English samples based on their \texttt{TED} to Danish, and choose the samples with the lowest \texttt{TED}.
We investigate three different ways to build the subset: taking top/bottom/random-\textit{k} English samples ($\mathrm{en}_{\mathrm{top}}$, $\mathrm{en}_{\mathrm{bottom}}$, $\mathrm{en}_{\mathrm{rand}}$).
In our experiment, we set \textit{k} to 1300, which is about half the size of the Danish dataset.
We compare the results with two baselines, one trained only with Danish data ($\mathrm{da}$) and another one trained with the aggregated dataset of Danish and \emph{all} English samples ($\mathrm{da}+\mathrm{en}_{\mathrm{all}}$). The results are in Table \ref{tab:cross_aug}.

Results confirmed our hypothesis that we can further improve cross-lingual transfer by selecting samples that are more transferable than others.
 $\mathrm{da}+\mathrm{en}_{\mathrm{top}}$ showed the best performance, while $\mathrm{da}+\mathrm{en}_{\mathrm{bottom}}$ and $\mathrm{da}+\mathrm{en}_{\mathrm{rand}}$ performed worse than $\mathrm{da}+\mathrm{en}_{\mathrm{all}}$.
This shows that na\"ively using all samples in the transfer language (English) is not necessarily the best way to conduct cross-lingual transfer.

\begin{table}[]
    \centering

            \begin{tabular}{c|c|c|c|c}
        \toprule
        \multicolumn{3}{c|} {Threshold} & \multirow{1}{*}{Additional} & \multirow{1}{*}{Macro} \\
         \multicolumn{1}{c}{OFF} & \multicolumn{1}{c}{NOT} & \multicolumn{1}{c|}{std} & data size & F1 \\
        \midrule
        0.8 & 0.2 & 0.1 & 3533 & 0.7693\\
        0.8 & 0.2 & 0.125 & 29681 & \textbf{0.7793}\\
        0.8 & 0.3 & 0.1 & 7956 & 0.7716\\
        0.8 & 0.3 & 0.125 & 83782 & 0.7738\\
        0.9 & 0.2 & 0.1 & 2769 & 0.7741\\
        0.9 & 0.2 & 0.125 & 19590 & 0.7709 \\
        0.9 & 0.3 & 0.1 & 7192 & 0.7707 \\
        0.9 & 0.3 & 0.125 & 73691 & 0.7453\\
        \midrule
        \multicolumn{3}{c|} {Baseline} & 0 & 0.7754\\
        \bottomrule
    \end{tabular}
    \caption{Results of data augmentation from semi-supervised labels. F1 scores are measured over the validation split of English data.}
    \label{tab:dist_aug}

\end{table}

\begin{table}[]
    \centering
    \begin{tabular}{c|c|c|c|c|c}
        \toprule
         Train data & $da$ & $da+en_{all}$ & $da+en_{top}$ & $da+en_{bottom}$ & $da+en_{rand}$ \\
        \midrule
        Macro F1 & 0.77 & 0.78 & \textbf{0.84} & 0.72 & 0.72 \\ \bottomrule
    \end{tabular}
    \caption{Results of cross-lingual data augmentation on the Danish validation data. $da$ refers to the original Danish training data, and $\mathrm{en}_{\mathrm{all}}$ is the entire English training dataset. $\mathrm{en}_{\mathrm{top}}$, $\mathrm{en}_{\mathrm{bottom}}$, $\mathrm{en}_{\mathrm{rand}}$ are the subsets of samples according to the \texttt{TED}.}
    \label{tab:cross_aug}
\end{table}

\section{Analysis and Discussion}
\label{sec:analysis_discussion}
In this section, we analyze how cross-lingual data selection could help improve performance. In addition, we discuss limitations of the proposed metric, \texttt{TED}, and some negative results with masking offensive words with a hope to provide insights for future work.
\label{sec:discussion}

\subsection{How Does Cross-lingual Data Selection Help?}
We showed that our data augmentation strategy using data from other languages helps improve the target task performance in Section \ref{sec:dataaug}.
Here, we investigate why cross-lingual data selection was helpful.

\begin{figure*}
    \centering
    \includegraphics[width=0.45\textwidth]{./figures/tsne-all.pdf}
    \caption{tSNE visualization of mBERT sentence embeddings of OLID samples. Samples are color coded according to their language (ar:Arabic, da:Danish, en:English, el:Greek, and tr:Turkish).}
    \label{fig:tsne_all}
\end{figure*}

We first take a look at the embedding space of mBERT to understand why language-level data selection, according to language-level \texttt{TED}, was beneficial. We randomly sampled a thousand samples from each language and visualized their sentence embeddings using tSNE \cite{maaten2008visualizing} in \Fref{fig:tsne_all}.
From the visualization, we observed that the examples formed rough clusters based on their language. Interestingly, English and Danish clusters are placed near one another. This aligns with our experimental result in the previous section, where we found English to be the most transferable language to Danish by language-level \texttt{TED}. We speculate that this proximity in the embedding space may be related to the improvement yielded when English samples with low \texttt{TED} were added to the Danish dataset. mBERT might have benefited from the additional English data even while training a Danish classifier because the examples were relatively close to each other in the shared embedding space.

In addition, we manually inspect the examples with low \texttt{TED} scores which we assumed to be more transferable. Examples in \Tref{tab:transf-sample} reveal that the samples with low \texttt{TED} are the ones that did not change significantly after the translation procedure. These samples often contain words used in both languages colloquially (e.g., creepy, fool), and tend to be short with a rather simple grammatical structure.
We posit that this simplistic nature of the samples with low \texttt{TED} made themselves more translatable, thus more transferable, and led to improvements via cross-lingual transfer.

\subsection{Limitations of \texttt{TED}}
\texttt{TED} measures the transferability of an example with the help of a machine translation system. Incorporating an external off-the-shelf translator is convenient in that we do not need to build an additional translation system for multiple pairs of languages. However, still, the computation of \texttt{TED} comes with a cost of translating all samples for all possible transfer-target language pairs.
Another limitation of our method is that the quality of data selection relies on the performance of the employed machine translation system.
This dependency may lead to the misrepresentation of transferability in low-resource language samples because the quality of translation systems in these languages are generally deficient.
We believe that the different approaches commonly used for cross-lingual transfer (e.g., alignment methods) may pave the way for building a transferability metric that does not rely on external translation modules.

\subsection{Offensive Words in Inoffensive Contexts}
In our pilot experiment, we fine-tuned BERT with the OLID from OffensEval 2019 \cite{zampieri2019semeval}. The model's initial performance was around 0.80 macro F1, which is comparable considering that the best performance from OffensEval 2019 was 0.82 \cite{liu-etal-2019-nuli}. Qualitative analysis on the false-positive cases, however, showed that the model tends to classify tweets that include offensive words as offensive, regardless of the context. For example, \textit{``@USER And the fact he called you a b*tch after you respectfully told him your preference.."} was classified as offensive although the term ``b*tch" was not used to express any aggression toward the listener. Offensive words are also often used for alternative motives: as a topic of the statement or even to emphasize a positive sentiment.
We have found many cases in the dataset where offensive terms have not been used in a despicable manner (e.g., \textit{``f*cking awesome"}). However, since most offensive words are paired with aggressive intentions, the model's prediction seemed to be dictated by the presence of these words, ignoring the subtle context.

Our attempt to help the model focus more on the context and differentiate these subtle cases was to randomly mask some of the offensive words during training. The intuition was to encourage the model to attend to the context instead of specific terms by partially removing the dependency on certain words.
During model training, when an input tweet contained words in the offensive word list\footnote{https://www.cs.cmu.edu/~biglou/resources/, https://www.freewebheaders.com/full-list-of-bad-words-banned-by-google, https://github.com/LDNOOBW/List-of-Dirty-Naughty-Obscene-and-Otherwise-Bad-Words}, we randomly replaced them with a \texttt{[PAD]} token. We used the unmasked, original sample at inference time. We expected this procedure to help the model become more robust against different contexts of offensive word usage. Unfortunately, the masking strategy did not result in quantitative gains. A possible explanation for the performance decline could be that the na\"ive masking excessively deleted offensive words that were actually used offensively. A more balanced approach would be required to address this limitation in future work.

\begin{table}[]
\centering
\begin{tabular}{p{20em}|p{20em}}
\toprule
     Original (English) & Translated (Danish) \\
     \midrule
    @USER Creepy & @USER Creepy \\
    \midrule
    @USER Fool! & @USER Fool! \\
    \midrule
    \#RestoreHumanity \#AntiFa September 22: Stop the fascist NVU in \#Amsterdam: URL HT @USER & \#RestoreHumanity \#AntiFa September 22: Stop det fascistiske NVU in \#Amsterdam: URL HT @USER\\
    \midrule
    @USER I'M SO FU*KING READY &  @USER I'M SO FU*KING KLAR\\
    \midrule
    @USER @USER so sad \#taketworeferenceswithmoniqueandchloe x & @USER @USER så trist \#taketworeferenceswithmoniqueandchloe x \\
\bottomrule
\end{tabular}
\caption{English samples with low \texttt{TED} when transferred to Danish. Most examples were not changed significantly after the translation.}
\label{tab:transf-sample}
\end{table}

\section{Related Work}
\label{sec:rw}
Computational methods to identify offensive language have been studied in many different aspects \cite{davidson2017automated,schmidt2017survey}. Researchers have focused on a variety of categories of offensive language such as sexism, racism, and hate speech in general. \newcite{sap-etal-2019-risk} identified a racial bias in hate speech detection datasets and proposed better annotation methods to address the problem. \newcite{park-fung-2017-one} pointed out the gender bias in abusive language detection models and suggested a de-biasing algorithm. \newcite{qian-etal-2018-hierarchical} introduced a more fine-grained hate speech identification task than binary classification, and presented an architecture that leverages Conditional Variational Autoencoder (CVAE).

Large-scale pre-trained models like BERT have achieved state-of-the-art results in various NLP tasks \cite{devlin-etal-2019-bert,yang2019xlnet}. \newcite{wu-dredze-2019-beto}, \newcite{K2020Cross-Lingual}, and \newcite{Pires2019HowMI} explored the multilinguality of mBERT and confirmed the model's effectiveness in cross-lingual transfer.
In the task of offensive language detection,  \cite{liu-etal-2019-nuli} has adopted BERT to solve the problem.
In our work, we also use mBERT but improve the method's ability under a multilingual setting by leveraging cross-lingual transfer.

\section{Conclusion}
\label{sec:conclusion}
In this paper, we describe NLPDove's approach to SemEval-2020 Task 12: Multilingual Offensive Language Identification in Social Media. The system yielded significant results in the competition for multiple languages, confirming the strength of large-scale pre-trained language models and the importance of various preprocessing schemes and model ensembling. We examine two data augmentation strategies and propose a new metric, \texttt{TED}, to quantify cross-lingual transferability. In qualitative analysis, we inspect factors why data selection with \texttt{TED} increased performance.
We also present the limitations of our system, mainly failing to detect the speaker's intention expressed subtly in the context, hoping to offer valuable insights and elicit future work in the field.

\bibliographystyle{coling}