\section{Introduction}
Distance metric learning aims at representing data points in a space where proximity accounts for similarity. A recent popular approach in face recognition \cite{schroff:cvpr15}, image retrieval \cite{song:cvpr16} or speaker change detection \cite{bredin:icassp17} formalizes this problem as a triplet loss optimization task, namely minimizing: $L = max(D(a,p) - D(a,n) + \alpha, 0)$ where $D(a,p)$ is the distance between \textit{intra-class} (same label) samples (anchor and positive), $D(a,n)$ is the distance between \textit{inter-class} (different labels) samples (anchor and negative) and $\alpha > 0$ is a margin constant. The main idea is to enforce inter-class pairs to be far away from intra-class pairs at least by a margin $\alpha$. This favors clustering of same class samples. As pointed out in \cite{wang:iccv17, hermans:arxiv17}, minimizing $L$ is not easy as the number of possible triplets grows cubically with the number of identities. Furthermore, a naive uniform sampling strategy would select trivial triplets for which the gradient of $L$ is negligible. As a result, learning may be slow and stuck in a local minima \cite{wu:iccv17}. To address this problem, some works proposed to select only \textit{hard} samples ($D(a,p) > D(a,n)$) for training \cite{simoserra:iccv15, shrivastava:cvpr16}. Hard samples mining, however, selects triplets with noisy (high variance) gradients of $L$. Models may then struggle to effectively push inter-class pairs apart, and end up in a collapsed state \cite{schroff:cvpr15, wu:iccv17}. A relaxed alternative is to mine only \textit{semi-hard} samples \cite{schroff:cvpr15}: triplets in which the negative is not necessarily closer to the anchor than the positive, but which still produce a strictly positive loss. This strategy improves the robustness of training by avoiding overfitting outliers in the training set \cite{harwood:iccv2017}. It typically converges quickly in the first iterations, but eventually runs out of informative samples and stops making progress. In \cite{wu:iccv17} authors attributed this phenomenon to the concentration of the gradient's variance of $L$ for semi-hard samples to a small region. To address this issue, they proposed to select negative samples based on their distances to anchors. They demonstrated that this strategy results in the variance of the gradient of $L$ being spread in a larger range, and thus consistently produces informative triplets \cite{wu:iccv17}.

Its ability to deal with large-scale catalogs and data sparsity \cite{wang:iccv17} makes the triplet loss model suitable for recommendation tasks. It has indeed been recently proposed as the \ac{CML} model \cite{hsieh:www17}, reaching competitive results with traditional \ac{MF} methods \cite{yifan:icdm08, rendle:auai09}. \ac{CML} assumes that users and items can be placed in a joint low dimensional metric-space. Recommendations are then easily done based on their proximity measured by their Euclidean distance. \ac{CML} can achieve competitive accuracy \cite{hsieh:www17} but we show in this paper that it requires large batches to do so, because of it's simplistic uniform negative sampling strategy. Owing to memory limitations, this makes \ac{CML} unable to scale in high-dimensional scenarios, \emph{e.g.}, when building a hybrid multimedia recommender system that learns jointly from interaction data and high-dimensional item contents such as audio spectrograms \cite{lee:arxiv18}. For that reason, following the idea in \cite{wu:iccv17}, we replace the default uniform sampling by a 2-stage strategy, which finds triplets that are consistently informative for learning. This enables \ac{CML} to be competitive with uniform sampling, even with small batches, both in terms of accuracy and popularity bias.

Our contributions are threefold: (1) We study the influence of batch size on the CML's performance. (2) We propose a 2-stage negative sampling that makes CML efficient with small batches. (3) We demonstrate the suitability of our sampling strategy on three real-world datasets, for the Top-N recommendation task, in terms of accuracy and popularity bias. We note especially a significant improvement over standard \ac{CML} on music recommendation. We also provide code to reproduce our results\footnote{Code available at: \href{https://github.com/deezer/sigir2019-2stagesampling}{https://github.com/deezer/sigir2019-2stagesampling}}.
\section{Preliminaries}
\subsection{Problem Formulation}
Consider a dataset with $N$ users, $M$ items and the binary interaction ${M \times N}$ matrix $R$,  where $R_{ij}$ indicates the only positive implicit feedback (\emph{e.g.}, clicks, listens, view histories logs etc.) between the $i$-th user and the $j$-th item. We use $\mathbf{S} = \{(i, j)\text{ }|\text{ }R_{ij} = 1\}$ to denote the set of user-item pairs where there exists implicit interactions. The considered task is to predict the items/users that are likely to interact together.

\subsection{Collaborative Metric Learning}
\ac{CML} \cite{hsieh:www17} learns a joint metric space of users and items to encode $\mathbf{S}$. The idea is to learn a metric that pulls the positive pairs in $\mathbf{S}$ closer while pushing the negative pairs (pairs not in $\mathbf{S}$) relatively further apart compared to the positive ones, based on the following loss:
\begin{equation}
\begin{split}
    L^{\text{triplet}} = \sum_{(i,j) \in B}w_{ij}[D^2(\mathbf{u}_{i},\mathbf{v}_{j})-\min_{k \in N_{ij}}D^2(\mathbf{u}_{i}, \mathbf{v}_{k}) + \alpha]_{+} + \lambda_c L_c\\
    \text{s.t. } \forall p \leq M, q \leq N: ||\mathbf{u}_p||_2 \leq 1, ||\mathbf{v}_{q}||_2 \leq 1
\end{split}
\end{equation}
where $\mathbf{u}_{i}$, $\mathbf{v}_{j}$ are, respectively, user and item latent vectors in $\mathbb R^d$, $B \subset S$ is the set of positive pairs in the considered mini-batch, $N_{ij} \subset \{k | (i, k) \not \in S \}$ is a set of negative samples per triplet, $\alpha > 0$ is a margin constant, $D$ is the Euclidean distance and $w_{ij}$ is a weight based on the number of negatives in $N_{ij}$ falling inside the $\alpha$-ball to penalize items at a lower rank \cite{weston:ml10}, $[.]_+ = max(., 0)$, $L_c$ is regularization term (weighted by the hyper parameter $\lambda_c$) used to de-correlate the dimensions in the learned metric \cite{hsieh:www17}. The recommendation for an user is then made by finding the $k$ nearest items around her/him in the latent space.

In this work, we set $w_{ij}$ to 1 for fair comparison between different sampling strategies. Furthermore, we do not use $L_c$ for all models because we have inferior results for the uniform sampling with this regularization (with the code provided by authors on github\footnote{Original CML \href{https://github.com/changun/CollMetric}{https://github.com/changun/CollMetric}}). Additionally, all user and item vectors are normalized to the unit sphere: $\forall p \leq M, q \leq N: ||\mathbf{u}_p||_2 = 1, ||\mathbf{v}_{q}||_2 = 1$ (by adding a $L_2$-normalization step after the user/item embedding layer) instead of being bound within the unit ball.

\section{Sampling Strategy}
\subsection{Spread-out Regularization}
In \cite{zhang:iccv17}, the authors argued that in order to fully exploit the expressive power of the embedding, latent vectors should be sufficiently "spread-out" over the space. Intuitively, two randomly sampled non-matching vectors are "spread-out" if they are orthogonal with high probability. To this end, they proved that if $\mathbf{p}_{1}, \mathbf{p}_{2}$ are two vectors independently and uniformly sampled from the unit sphere in $\mathbb{R}^d$, the probability density of $\mathbf{p}_{1}^{T}\mathbf{p}_{2}$ satisfies
  \begin{displaymath}
    p(\mathbf{p}_{1}^{T}\mathbf{p}_{2} = s) = \begin{cases}
        \frac{(1 - s^{2})^{\frac{d-1}{2}-1}}{\text{Beta}(\frac{d-1}{2}, \frac{1}{2})} & \text{if} \, -1 \leq s \leq 1 \\
    0 & \text{otherwise}
    \end{cases}
  \end{displaymath}
  where $\text{Beta}(a, b)$ is the beta distribution function.
From this distribution, they further found that $\mathbb{E}\left[\mathbf{p}_{1}^{T}\mathbf{p}_{2}\right] = 0 \text{ and } \mathbb{E}\left[(\mathbf{p}_{1}^{T}\mathbf{p}_{2})^2\right] = \frac{1}{d}$, and proposed the \ac{GOR} to enforce the spread of latent vectors. The application of \ac{GOR} for \ac{CML} is thus:

\begin{align}
    L &= L^{\text{triplet}} + \lambda_g L^{\text{GOR}} \\
    L^{\text{GOR}} &= \Big(\frac{1}{Q}\sum_{(i,j) \in B}\sum_{k \in N_{ij}}\mathbf{v}_{j}^{T}\mathbf{v}_{k}\Big)^{2} + \Big[ \frac{1}{Q}\sum_{(i,j) \in B}\sum_{k \in N_{ij}}(\mathbf{v}_{j}^{T}\mathbf{v}_{k})^2 - \frac{1}{d}\Big]_+
\end{align}
where $\lambda_g$ is an hyperparameter, $Q = |B| \times |N_{ij}|$ and $d$ is the dimension of the latent space.
\subsection{2-stage negative sampling}
\label{2_stage_negative_sampling}
To construct a batch, we first randomly sample pairs in $S$ as in \cite{hsieh:www17} to get the anchor users and the positive items. Our strategy aims at replacing the uniform sampling for the set $N_{ij}$ negative items in a triplet by a 2-stage setting as described below.

In the first stage, we sample $C$ negative candidates from all items in the dataset based on their frequencies as proposed in the popular Word2Vec algorithm in natural language processing \cite{mikolov:nips12} and its application for the recommendation task \cite{barkan:mlsp2016, dupre:recsys17, musto:recsys15}:
\begin{equation}
\label{w2vsampling}
    \Pr(j)=\frac{f(j)^\beta}{\sum_{j'}f(j')^\beta} \,,
\end{equation}

\noindent where $f(j)$ is the interaction frequency of item $j$ and the parameter $\beta$ plays a role in sharpening or smoothing the distribution. A positive $\beta$ leads to a sampling that favors popular items, a $\beta$ equal to 0 leads to items being sampled uniformly, while a negative $\beta$ makes unpopular items being more likely sampled. In this work, we use a positive $\beta$ to favor popular items as negative samples. The motivation is that due to the popularity bias in interaction data \cite{steck:recsys11}, popular items tend to be close together. A challenge is thus to push non-matching popular items farther away in the latent space. Spreading popular items apart could then help to reduce the popularity bias often witnessed in recommendation.

In the second stage, we select informative negative items from the $C$ previous candidates in a similar manner as in \cite{wu:iccv17}.
Given the latent vector of a positive item $\mathbf{v}_{j}$, we sample a negative item index $n$, with corresponding latent factor $\mathbf{v}_{n}$ as follows:
\begin{displaymath}
    \Pr(n|\mathbf{v}_{j}) \propto \begin{cases}
    \frac{1}{p(\mathbf{v}_{j}^{T}\mathbf{v}_{n}=s)}, & 0 \leq s \leq 1 \\
    0, & \text{otherwise}
    \end{cases}
\end{displaymath}
This strategy has two objectives: first, the choice of this probability function offers triplets with a larger range of gradient's variance than what would be obtained with semi-hard triplet sampling \cite{wu:iccv17}. Second, it puts high probability on items $n$ that produce high positive value for $\mathbf{v}_{j}^{T}\mathbf{v}_{n}$, hence inducing positive values for $L^{\text{triplet}}$ and large values for $L^{\text{GOR}}$. Indeed, it's obvious that with positive $\mathbf{v}_{j}^{T}\mathbf{v}_{n}$, $L^{\text{GOR}}$ increases as $\mathbf{v}_{j}^{T}\mathbf{v}_{n}$ gets higher. At the same time, for each positive-negative pair $(\mathbf{v}_{j}, \mathbf{v}_{n})$, we have $||\mathbf{v}_{j} - \mathbf{v}_{n}||_{2}^{2} = ||\mathbf{v}_{j}||_{2}^{2} + ||\mathbf{v}_{n}||_{2}^{2} - 2\mathbf{v}_{j}^{T}\mathbf{v}_{n} = 2 - 2\mathbf{v}_{j}^{T}\mathbf{v}_{n}$, so the greater the value of $\mathbf{v}_{j}^{T}\mathbf{v}_{n}$ is, the closer the positive-negative points are. This leads to a smaller difference between $D^2(\mathbf{u}_{i}, \mathbf{v}_{j})$ and $D^2(\mathbf{u}_{i}, \mathbf{v}_{n})$, making $L^{\text{triplet}}$ more likely to be positive. It thus induces higher loss values compared to the uniform sampling case, and hopefully results in gradients more suitable for training.
\section{Experiments}

\subsection{Experimental Settings}
\subsubsection{Datasets}
We experiment with three datasets covering different domains: namely movie, book and music recommendations.

\textit{Amazon movies} \cite{he:www16}: The \textit{Amazon} dataset is the consumption records with reviews from \textit{Amazon.com}. We use the user-movie rating from \textit{the movies and tv category 5-core}. The data is binarized by keeping only ratings greater than 4 as implicit feedback. Users with less than 20 positive interactions are filtered out.

\textit{Book crossing} \cite{ziegler:www05}: The dataset contains book ratings which scale from 0 to 10 with the higher score indicating preference. Again, explicit ratings are binarized by keeping values of five or higher as implicit feedback. Only users with more than 10 interactions are then kept.

\textit{Echonest} \cite{mcfee:www12}: The EchoNest Taste Profile dataset contains user playcounts for songs of the \ac{MSD}. After deduplicating songs, playcount data is binarized by considering values of five or higher as implicit feedback. Finally, only users with more than 20 interactions and items with which at least 5 users interacted.

The characteristics of these three datasets after filtering are summarized in Table~\ref{tab:commands}.

\subsubsection{Evaluation Methodology}
We divide user interactions into 4-fold for cross-validation where three folds are used to train the model and the remaining fold is used for testing. Based on the ranked preference scores, we adopt \ac{MAP} and \ac{NDCG} to measure whether ground-truth items are present on the ranked list of preferences truncated at 50 items and their positions. In addition, we calculate the \ac{MMR} of recommended items to assess the popularity bias of the model.

\subsubsection{Parameters setting}
The parameter $C$ should be chosen in order to retain a sufficient number of candidates while limiting the amount of computations occurring in the second stage. We set it to 2000 and leave its optimization to future work. Besides that, the latent dimension $d$ is set to 128 and the margin $\alpha$ to 1.
For the other parameters, the 4-fold cross-validation mentioned above is used to choose the best values using grid-search. Adam optimizer \cite{kingma:arxiv14} is used for all models. The learning rate is 0.0001, the parameter $\beta$ for the first stage is 1.0 for Amazon movies and Echonest and 0.8 for Book crossing. Finally, $\lambda_g$ is 0.01 when the number of negatives is 1 and 2 and to 0.001 as the number of negatives is 5.

\begin{table}
  \caption{Statistics of the datasets}
  \label{tab:commands}
  \begin{tabular}{ccccl}
    \toprule
    Dataset & User\# &Item\# & Rating\# & Density \\
    \midrule
    \texttt{Amazon Movies} & 11181 & 94661 & 620059 & 0.058\% \\
    \texttt{Book Crossing} & 3593 & 127339 & 240020 & 0.052\% \\
    \texttt{Echonest} & 31521 & 159063 & 1405671 & 0.028\% \\
    \bottomrule
  \end{tabular}
  \vspace{-4mm}
\end{table}

\subsection{Comparison Results}
\subsubsection{Uniform sampling}
Performance of \ac{CML} with uniform sampling \cite{hsieh:www17} is summarized in Table \ref{all_results} (\textit{Uni} sub-table). We discuss results for the Amazon movies dataset as the same trend can be observed on the two others. We see that the performance of \ac{CML} in terms of MAP and NDCG heavily decreases when using small batches, especially when $|N_{ij}|=1$. For example, when the batch size is an order of magnitude smaller (256 vs 4096), \ac{MAP} relatively decreases by 19\% (2.26 $\rightarrow$ 1.82) and NDCG by 14\% (7.55 $\rightarrow$ 6.47). This drop supports the idea that the number of informative triplets is low in small batches with the uniform sampling setup. With more negatives per triplet ($|N_{ij}|=5$), this decrease is alleviated, about 7\% relative drop against 19\% for \ac{MAP} (2.48 $\rightarrow$ 2.31) and 5\% relative drop against 14\% for NDCG (8.06 $\rightarrow$ 7.68). Additionally, another issue of \ac{CML} is being prone to a strong popularity bias (\ac{MMR}). As shown in Table \ref{all_results} this bias increases with the batch size: e.g., from 256 to 4096, with 1 negative per triplet, MMR raises relatively by 29\% (86.4 $\rightarrow$ 111.8).

\begin{table*}[h]
  \caption{\ac{CML}'s performance with different sampling strategies, number of negatives per triplet and batch sizes. The format is $mean \pm std$ obtained from 4 runs on cross-validation splits. The italic bold face shows the best values for uniform strategy while bold face shows the best overall values}.
  \label{all_results}
  \resizebox{\textwidth}{!}{
  \begin{tabular}{|c|c|c|ccc|ccc|ccc|}
        \toprule
        \multirow{2}{*}{Sam} & \multirow{2}{*}{$|N_{ij}|$} & \multirow{2}{*}{Batch} & \multicolumn{3}{c}{Amazon Movies} & \multicolumn{3}{c}{Book Crossing} & \multicolumn{3}{c}{Echonest} \\
        \cline{4-12}
        {} & {} & {} & MAP(\%) & NDCG(\%) & MMR & MAP(\%) & NDCG(\%) & MMR & MAP(\%) & NDCG(\%) & MMR \\
        \midrule
        \multirow{6}{*}{Uni} & \multirow{3}{*}{1} & {4096} & {2.26 $\pm$ 0.06} & {7.55 $\pm$ 0.12} & {111.8 $\pm$ 0.1} & {1.12 $\pm$ 0.07} & {3.98 $\pm$ 0.11} & {55.2 $\pm$ 0.4} & {4.88 $\pm$ 0.02} & {12.78 $\pm$ 0.01} & {241.8 $\pm$ 1.4} \\
        {} & {} & {1024} & {2.13 $\pm$ 0.08} & {7.19 $\pm$ 0.16} & {101.7 $\pm$ 1.5} & {1.08 $\pm$ 0.08} & {3.86 $\pm$ 0.14} & {53.2 $\pm$ 0.4} & {4.41 $\pm$ 0.01} & {11.70 $\pm$ 0.04} & {196.5 $\pm$ 0.6} \\
        {} & {} & {256} & {1.82 $\pm$ 0.04} & {6.47 $\pm$ 0.10} & {\textbf{\textit{86.4 $\pm$ 2.4}}} & {0.93 $\pm$ 0.04} & {3.50 $\pm$ 0.06} & {\textbf{\textit{44.5 $\pm$ 1.2}}} & {3.66 $\pm$ 0.03} & {9.90 $\pm$ 0.12} & {\textbf{\textit{146.7 $\pm$ 2.2}}} \\
        \cline{2-12}
        {} & \multirow{3}{*}{2} & {4096} & {2.34 $\pm$ 0.06} & {7.72 $\pm$ 0.10} & {114.5 $\pm$ 0.2} & {1.15 $\pm$ 0.08} & {4.06 $\pm$ 0.12} & {54.9 $\pm$ 0.9} & {5.16 $\pm$ 0.04} & {13.39 $\pm$ 0.05} & {265.5 $\pm$ 1.1} \\
        {} & {} & {1024} & {2.23 $\pm$ 0.04} & {7.49 $\pm$ 0.10} & {109.5 $\pm$ 0.2} & {1.13 $\pm$ 0.06} & {3.97 $\pm$ 0.13} & {54.5 $\pm$ 1.2} & {4.85 $\pm$ 0.08} & {12.60 $\pm$ 0.09} & {231.7 $\pm$ 3.0} \\
        {} & {} &  {256} & {2.04 $\pm$ 0.07} & {6.98 $\pm$ 0.12} & {96.0 $\pm$ 1.9} & {1.04 $\pm$ 0.10} & {3.74 $\pm$ 0.17} & {49.5 $\pm$ 0.8} & {4.18 $\pm$ 0.06} & {11.14 $\pm$ 0.09} & {175.0 $\pm$ 5.3} \\
        \cline{2-12}
        {} & \multirow{3}{*}{5} & {4096} & {\textbf{\textit{2.48 $\pm$ 0.05}}} & {\textbf{\textit{8.06 $\pm$ 0.13}}} & {118.5 $\pm$ 0.4} & {\textbf{\textit{1.15 $\pm$ 0.08}}} & {\textbf{\textit{4.13 $\pm$ 0.14}}} & {53.7 $\pm$ 0.8} & {\textbf{\textit{5.71 $\pm$ 0.04}}} & {\textbf{\textit{14.50 $\pm$ 0.09}}} & {315.5 $\pm$ 1.4} \\
        {} & {} &  {1024} & {2.45 $\pm$ 0.06} & {8.01 $\pm$ 0.13} & {115.2 $\pm$ 0.6} & {1.15 $\pm$ 0.08} & {4.07 $\pm$ 0.09} & {55.2 $\pm$ 0.6} & {5.56 $\pm$ 0.05} & {14.17 $\pm$ 0.04} & {287.5 $\pm$ 2.5} \\
        {} & {} &  {256} & {2.31 $\pm$ 0.02} & {7.68 $\pm$ 0.04} & {107.2 $\pm$ 0.2} & {1.12 $\pm$ 0.09} & {3.94 $\pm$ 0.16} & {53.5 $\pm$ 1.0} & {5.11 $\pm$ 0.01} & {13.10 $\pm$ 0.04} & {229.1 $\pm$ 1.0} \\
        \hlinewd{0.9pt}
        \multirow{3}{*}{Pop} & {1} & \multirow{3}{*}{256} & {2.12 $\pm$ 0.02} & {7.14 $\pm$ 0.01} & {26.2 $\pm$ 0.3} & {1.04 $\pm$ 0.07} & {3.54 $\pm$ 0.06} & {8.3 $\pm$ 0.04} & {6.48 $\pm$ 0.11} & {15.55 $\pm$ 0.17} & {54.3 $\pm$ 1.6} \\
        {} & {2} & {} & {2.43 $\pm$ 0.04} & {7.83 $\pm$ 0.12} & {24.3 $\pm$ 0.02} & {1.22 $\pm$ 0.07} & {3.87 $\pm$ 0.14} & {6.9 $\pm$ 0.13} & {7.26 $\pm$ 0.06} & {17.0 $\pm$ 0.03} & {46.1 $\pm$ 0.2} \\
        {} & {5} & {} & {2.57 $\pm$ 0.07} & {7.89 $\pm$ 0.06} & {\textbf{17.2 $\pm$ 0.04}} & {1.25 $\pm$ 0.04} & {3.75 $\pm$ 0.06} & \textbf{{4.1 $\pm$ 0.01}} & {8.0 $\pm$ 0.01} & {18.44 $\pm$ 0.08} & {\textbf{33.8 $\pm$ 0.3}} \\
        \hlinewd{0.9pt}
        \multirow{3}{*}{2st} & {1} & \multirow{3}{*}{256} & {2.32 $\pm$ 0.06} & {7.78 $\pm$ 0.14} & {32.9 $\pm$ 0.1} & {1.26 $\pm$ 0.08} & {\textbf{4.13 $\pm$ 0.13}} & {10.1 $\pm$ 0.1} & {6.99 $\pm$ 0.03} & {16.69 $\pm$ 0.05} & {96.1 $\pm$ 0.2} \\
        {} & {2} & {} & {2.57 $\pm$ 0.03} & {8.14 $\pm$ 0.04} & {27.9 $\pm$ 0.1} & {1.3 $\pm$ 0.08} & {4.12 $\pm$ 0.11} & {7.6 $\pm$ 0.1} & {7.91 $\pm$ 0.14} & {18.32 $\pm$ 0.13} & {78.9 $\pm$ 0.2} \\
        {} & {5} & {} & {\textbf{2.73 $\pm$ 0.03}} & {\textbf{8.23 $\pm$ 0.02}} & {19.6 $\pm$ 0.1} & {\textbf{1.38 $\pm$ 0.09}} & {4.12 $\pm$ 0.15} & {4.5 $\pm$ 0.01} & {\textbf{8.70 $\pm$ 0.07}} & {\textbf{19.37 $\pm$ 0.06}} & {48.4 $\pm$ 0.8} \\
        \bottomrule
      \end{tabular}
    }
\vspace{-2mm}
\end{table*}
\subsubsection{Popularity-based sampling}
To confirm our intuition on the necessity of pushing non-matching popular items farther away (as discussed in the Section \ref{2_stage_negative_sampling}), we study the popularity-based negative sampling method of Equation \eqref{w2vsampling}. Table \ref{all_results} (\textit{Pop} sub-table) reveals a high impact of this strategy on the performance of \ac{CML} in terms of \ac{MAP} \& \ac{NDCG}. Specifically, with smaller batch size (256 vs 4096), the \ac{MAP} with popularity-based sampling already surpasses the best result of the uniform sampling, by 3.6\% for movies (2.26 $\rightarrow$ 2.57), 8.7\% for books (1.15 $\rightarrow$ 1.25) and 40\% for music (5.71 $\rightarrow$ 8.0) respectively. As expected, the recommendations are less biased towards popular items: \ac{MMR} decreases by 80\%  on Amazon movies (86.4 $\rightarrow$ 17.2), 90.8\% on Book crossing (44.5 $\rightarrow$ 4.1) and 77\% on Echonest (146.7 $\rightarrow$ 33.8).
\subsubsection{2-stage sampling}
 While popular-based negative sampling is efficient with small batches, the reported \ac{NDCG} of this strategy is slightly worse than what can be obtained by uniform sampling on large batches (except for the Echonest). In book recommendation, the gap is quite significant with a 6.3\% decrease (4.13 $\rightarrow$ 3.87). To further improve the performances of the \ac{CML} model on small batches, we add on top of the popularity strategy a second stage based on dot product weighted sampling as described in Section \ref{2_stage_negative_sampling}. This enables \ac{CML} with small batches to have a competitive \ac{NDCG} w.r.t the best result using the uniform sampling strategy. In detail, with 16 times smaller batch size, 2-stage sampling yields the same \ac{NDCG} for book recommendation and reaches a 2.1\% increase for movie recommendation (8.06 $\rightarrow$ 8.23), 33.6\% increase for music recommendation (14.5 $\rightarrow$ 19.37). Meanwhile \ac{MAP} is remarkably enhanced for all datasets, 10\% (2.48 $\rightarrow$ 2.73), 20\% (1.15 $\rightarrow$ 1.38) and 52\% (5.71 $\rightarrow$ 8.7) for movie, book and music recommendation respectively. Note that 2-stage sampling makes the \ac{MMR} slightly higher than that of the popularity-based strategy, but it is still significantly lower than the one with uniform sampling.

\section{Conclusions}
We proposed a 2-stage sampling strategy that enables the \ac{CML} model to perform efficiently with batch size an order of magnitude smaller than what would be needed with the default uniform sampling. At its heart, a set of samples is first selected based on their popularity. Then, informative ones are drawn from this set based on their inner product weights with anchors. Experiments demonstrate positive results across various datasets, especially for music recommendation for which the proposed approach increased very significantly the performance of the system. In future work, we will leverage this sampling strategy to jointly learn from multimedia content and collaborative data where huge batches are prohibitive due to memory limitations.


\section{Prepare your repository}
\label{sec:orgdaa7897}
\label{sec:prepare}

We assume that your source code is hosted on a repository publicly accessible
(Github, Bitbucket, a GitLab instance, an institutional software forge, etc.)
using one of the version control systems supported by Software Heritage,
currently Subversion, Mercurial and Git
\footnote{For up to date information, see \url{https://archive.softwareheritage.org/browse/origin/save/}}.\\

It is highly recommended that you provide, in your source code repository,
appropriate information on your research artifact: it will make it more
appealing and useful to future users (which might actually be \emph{you} in a few
months).

Well established best practice is to include, at the toplevel of your
source code tree, three \emph{key files}, README, AUTHORS and LICENSE, with
the information described below.

\begin{description}
\item[{README}] : A description of the software.\\
This file should contain \emph{at least}
\begin{itemize}
\item the name of the software/project
\item a brief description of the project.
\end{itemize}
It is also \emph{highly recommended} to add the following information
\begin{itemize}
\item pointers to the project website and documentation,
\item pointer to the project development platform,
\item license for the project (if not in a separate LICENSE file),
\item contact and support information,
\item build/installation instructions or a pointer to a file containing them (usually INSTALL)
\end{itemize}
In could be useful to provide here also some information for the users, like a list of features or informations on how to use the source code
\end{description}

\begin{description}
\item[{AUTHORS}] : The list of all authors that need to be credited for the current version.\\
If you want to specify the role of each contributor in this list, we suggest
to use the taxonomy of contributors presented in \cite{gtinria2009}, which distinguishes
the following roles: \emph{Design, Architecture, Coding, Testing, Debugging, Documentation, Maintenance, Support, Management}.
\item[{LICENSE}] : The project license terms.\\
For Open Source Licenses, it is strongly recommended to use the standard names that can be found on the \url{https://spdx.org/licenses/} website.
\end{description}

Future users that find your artifact useful might want to give you credit by
citing it.  To this end, you might want to provide instructions on how you
prefer your artifact to be cited. There are many possibilities for doing
that, and you might want to also provide structured citation information
in specific formats, like CodeMeta (usually in a file named \textbf{Codemeta.json2})
or CFF (usually in a file named \textbf{CITATION.cff3}).

\subsection{Learning more}
\label{sec:orgf518040}
The seminal article \emph{Software Release Practice HOWTO} by E. S. Raymond
\cite{raymond2013} documents best practices and conventions for releasing
software that have been well established for decades, and form the basis
of most current recommendations. Interesting more recent resources include
the REUSE website \cite{reuse}, which provides detailed guidance
and tools to verify compliance with the guidelines, as well as \cite{SSI2018}, which focuses more on research software.

\section{Save your code}
\label{sec:org4782bbf}
\label{sec:save}

\noindent Once your code repository has been properly prepared, you only need to:

\begin{itemize}
\item go to \url{https://archive.softwareheritage.org/browse/origin/save/},
\item pick your version control system in the drop-down list, enter the code repository url
\footnote{Make sure to use the clone/checkout url as given by the development platform hosting your code. It can easily be found in the web interface of the development platform.},
\item click on the Submit button (see Figure \ref{fig:savecodenow}).
\end{itemize}

\begin{figure}[h!]
\begin{center}
\includegraphics[width=\textwidth]{SaveCodeNow}
\end{center}
\caption{The Save Code Now form}\label{fig:savecodenow}
\end{figure}

\noindent \textbf{That's it, it's all done!} No need to create an account or to provide
personal information of any kind. If the url you provided is correct, Software
Heritage will archive your repository, with its full development history,
shortly after. If your repository is hosted on one of the major forges we
already know, this process will take just a few hours; if you point to a
location we never saw before, it can take longer, as we will need to manually
approve it.\\

\noindent \textbf{For hackers:} you can also request archival programmatically, using the
Software Heritage API
\footnote{For details, see \url{https://archive.softwareheritage.org/api/1/origin/save/}};
this can be quite handy to integrate, for example, into a Makefile.

\section{Reference your work}
\label{sec:org1ac9e49}
\label{sec:walkthrough}

Once your source code has been archived, there are many ways to reference it in
your article. We present here three common use cases:
\begin{itemize}
\item link to the \emph{full repository} archived in Software Heritage,
\item link to a \emph{precise version of the software project},
\item link to a \emph{precise version of a source code file}, down to the level of the line of code.
\end{itemize}

To make this concrete, in what follows we use as a running example the article
\emph{A ``minimal disruption'' skeleton experiment: seamless map and reduce embedding
in OCaml} by Marco Danelutto and Roberto Di Cosmo \cite{Parmap2012} published
in 2012. This article introduced a nifty library for multicore parallel
programming that was distributed via the \url{gitorious.org} collaborative
development platform, at \url{gitorious.org/parmap}. Since Gitorious has been
shut down a few years ago, like Google Code and CodePlex, this example is
particularly fit to show why pointing to an \emph{archive} that has your code is
better than pointing to the collaborative development platform where you
developed it.

\subsection{Full repository}
\label{sec:org3fb889d}
In Software Heritage, we keep track of all the \emph{origins} from which source
code has been retrieved, and finding a given \texttt{origin} is as easy as
adding in front of it the prefix
\url{https://archive.softwareheritage.org/browse/origin}

These origins are the exact \emph{URLs of the version control system} that a
developer would use to clone a working repository, and are the same urls that
you pass to the \emph{Save Code Now} form described in Section \ref{sec:save}.

In our running example, for the Parmap code on \emph{gitorious.org}, this origin
is \url{https://gitorious.org/parmap/parmap.git}, so the URL of the \emph{persistently
archived full repository} is the following:

\url{https://archive.softwareheritage.org/browse/origin/https://gitorious.org/parmap/parmap.git}

Just add this link to your article, and your readers will be able to get hold of
the archived copy of your repository even if/when the original development
platform goes away (as it has actually happened for \texttt{gitorious.org} that
has been shut down in 2015).

Your readers can then browse the contents of your repository extensively,
delving into its development history, and/or directory structure, down to each
single source code file
\footnote{For a guided tour see \url{https://www.softwareheritage.org/2018/09/22/browsing-the-software-heritage-archive-a-guided-tour/}}.

\textbf{N.B.}: if you are unsure about what is the actual origin URL of your
repository, you can look it up using the search box that is available at
\url{https://archive.softwareheritage.org/browse/search/}

\subsection{Specific version}
\label{sec:org56af571}

Pointing to the full archived repository is nice, but a version controlled
repository usually contains all the history of development of the source code,
whiche records different states of the project, usually called \emph{revisions}.

In order to support reproducibility of scientific results, we need to be able to
pinpoint precisely the state(s) of the source code used in the article.
Software Heritage provides a very easy means of pointing to a precise
\emph{revision}, via a standard identifier schema, called SWH-ID, which is
\href{https://docs.softwareheritage.org/devel/swh-model/persistent-identifiers.html}{fully documented online} and is discussed in the article \cite{swhipres2018}.

In our running example, the Parmap article, the exact revision of the source
code of the library used therein has the following SWH-ID:

\begin{tcolorbox}
swh:1:rev:0064fbd0ad69de205ea6ec6999f3d3895e9442c2;\\
origin=https://gitorious.org/parmap/parmap.git;
\end{tcolorbox}

And you can turn this identifier into a clickable URL by prepending to it
the prefix \url{https://archive.softwareheritage.org/}: you can try it
live right now by clicking on \href{https://archive.softwareheritage.org/swh:1:rev:0064fbd0ad69de205ea6ec6999f3d3895e9442c2;origin=https://gitorious.org/parmap/parmap.git}{this link}.

\subsubsection{Getting your SWH-ID}
\label{sec:org4092446}
\label{ssec:getswhid}
 A very simple way of getting the right SWH-ID is to browse your archived code in
 Software Heritage, and to navigate to the revision you are interested in. Click
 then on the \emph{permalinks vertical red tab} that is present on all pages of the
 archive, and in the tab that opens up you select the \emph{revision} identifier:
 an example is shown in Figure \ref{fig:permalink}.

\begin{figure}[h]
  \centering
  \includegraphics[width=\linewidth]{permalink-box-rev}
  \caption{Obtaining a Software Heritage identifier using the permalink box on
    the archive Web user interface}
  \label{fig:permalink}
\end{figure}

The two convenient buttons on the botton right allow you to copy the identifiers or the full permalink
in the clipboard, to insert in your article as you see fit.

\subsubsection{Generating and verifying SWH-IDs (for the geeks)}
\label{sec:org6680ada}
Version 1 of the SWH-IDs uses git-compatible hashes, so if you are using git as
a version control system, you can create the right SWH-ID by just prepending
\texttt{swh:1:rev:} to your commit hash. This might come pretty handy if you
plan to automate the generation of the identifiers to be included in your
article: you will always have your code and your article in sync!

Software Heritage identifiers can also be generated and verified independently
by anyone using \texttt{swh-identify}, an open source tool developed
by Software Heritage, and distributed via PyPI as \texttt{swh.model} (stable
version at
\swhidref{swh:1:rev:6cab1cc81118877e2105c32b08653509475f3eaa;\\
origin=https://pypi.org/project/swh.model/}).

\subsection{Code fragment}
\label{sec:org9c64b98}
A particularly nifty feature of the SWH-IDs supported by Software Heritage is the
ability to pinpoint a fragment of code inside a specific version of a file, by
using the \texttt{lines=} qualifier available for identifiers that point to
files.

Let's see this feature at work in our running example, which shows clearly
how an article can be greatly enhanced by providing pointers to
code fragments.

In Figure 1 of \cite{Parmap2012}, which is shown here as Figure
\ref{fig:parmappaper}, the authors want to present the core part of the code
implementing the parallel functionality that constitutes the main contribution
of their article. The usual approach is to typeset in the article itself \emph{an
excerpt of the source code}, and let the reader try to find it by delving
into the code repository, which may have evolved in the mean time.
Finding the exact matching code can be quite difficult, as the code excerpt
is \emph{often edited} a bit with respect to the original, sometimes to drop
details that are not relevant for the discussion, and sometimes due to
space limitations.

In our case, the article presented 29 lines of code, slightly edited from the
43 actual lines of code in the Parmap library: looking at
\ref{fig:parmappaper}, one can easily see that some lines have been dropped
(102-103, 118-121), one line has been split (117) and several lines simplified
(127, 132-133, 137-142).\\

\begin{figure}[t]
\centering
    \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \includegraphics[scale=0.5]{article-parmap-code}
        \caption{as presented in the article \cite{Parmap2012}}\label{fig:parmappaper}
    \end{subfigure}
    \vspace{1em}
    \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \includegraphics[scale=0.48]{parmap-cnt}
        \caption{as archived in Software Heritage}\label{fig:parmapswh}
    \end{subfigure}
    \caption{Code fragment from the published article compared to the content
      in the Software Heritage archive}
  \label{fig:parmap}
\end{figure}

Using Software Heritage, the authors can do a much better job, because the original
code fragment can now be precisely identified by the following Software Heritage identifier:
\begin{tcolorbox}
swh:1:cnt:d5214ff9562a1fe78db51944506ba48c20de3379;\\
origin=https://gitorious.org/parmap/parmap.git;\\
lines=101-143
\end{tcolorbox}
This identifier can also be easily obtained using the permalink box shown in Section \ref{ssec:getswhid} above, and it
will \textbf{always} point to the code fragment shown in Figure \ref{fig:parmapswh}.\\

The caption of the original article shown in Figure \ref{fig:parmappaper} can
then be significantly enhanced by incorporating all the clickable links needed
to point to the exact source code fragment that has been edited for inclusion
in the article, as shown in Figure \ref{fig:swhall}.

\begin{figure}[h!]
\begin{tcolorbox}
Simple implementation of the distribution, fork, and recollection phases in \texttt{Parmap} (slightly simplified from the \href{https://archive.softwareheritage.org/swh:1:cnt:d5214ff9562a1fe78db51944506ba48c20de3379;origin=https://gitorious.org/parmap/parmap.git;lines=101-143}{actual code} present in \href{https://archive.softwareheritage.org/swh:1:rev:0064fbd0ad69de205ea6ec6999f3d3895e9442c2;origin=https://gitorious.org/parmap/parmap.git}{the version of Parmap used for this article})
\end{tcolorbox}
\caption{A caption text with links to code fragment and revision}\label{fig:swhall}
\end{figure}

When clicking on the hyperlinked text in the caption shown above, the reader is
brought seamlessly to the Software Heritage archive on a page showing the
corresponding source code archived in Software Heritage, with the relevant
lines highlighted (see Figure \ref{fig:parmapswh}).\\

For \LaTeX{} users, the caption of \ref{fig:swhall} can be written using a few
convenient auxiliary macros, as shown in Figure \ref{fig:swhref}.

\begin{figure}[h!]
\begin{tcolorbox}
\begin{lstlisting}
\newcommand{\swhurl}[1]{https://archive.softwareheritage.org/#1}
\newcommand{\swhref}[2]{\href{\swhurl{#1}}{#2}}

...

 \caption{Simple implementation of the distribution,
 fork, and recollection phases in \texttt{Parmap}
 (slightly simplified from the
 \swhref{swh:1:cnt:d5214ff9562a1fe78db51944506ba48c20de3379;
         origin=https://gitorious.org/parmap/parmap.git;
         lines=101-143}
        {actual code})
 presented in
 \swhref{swh:1:rev:0064fbd0ad69de205ea6ec6999f3d3895e9442c2;
         origin=https://gitorious.org/parmap/parmap.git}
        {the version of Parmap used in this article}
\end{lstlisting}
\end{tcolorbox}
\caption{Adding clickable hyperlinks to Software Heritage in \LaTeX}\label{fig:swhref}
\end{figure}

\section{Acknowledgements}
\label{sec:orgf6044d3}
These guidelines result from extensive discussions that took place over several
years. Special thanks to Alain Girault, Morane Gruenpeter, Julia Lawall, Arnaud
Legrand and Nicolas Rougier for their precious feedback on earlier versions of this document.

\clearpage


\section{introduction}
Unmanned arieal vehicle (UAV) object tracking has many applications such as target tracing~\cite{Chen2016IROS}, robot localization~\cite{Coltin2016IROS}, mid-air tracking~\cite{Fu2014ICRA} and aerial cinematography~\cite{Bonatti2019IROS}. It aims to locate the object in the following frames given the initial location, in sometimes difficult situations such as fast motion, appearance variation (occlusion, illumination and viewpoint change, etc.), scale changes, and limited power capacity.

In UAV tracking tasks, the speed has been a key issue besides its performance. It was because of its ability to track objects at hundreds of frames per second (FPS) that discriminative correlation filter (DCF) is widely applied to perform UAV tracking in the first place. Unfortunately, the pioneering works~\cite{Bolme2010CVPR,Henriques2012ECCV,Henriques2015TPAMI}, despite their incredible speed, have inferior tracking performances. Therefore, strategies like part-based methods~\cite{Liu2015CVPR,Fu2018ROBIO}, spatial punishment~\cite{Danelljan2015ICCV,Danelljan2016ECCV, Luke2017CVPR} and robust appearance representation~\cite{Danelljan2015ICCVW,Ma2015ICCV,Li2017ICCVW} are used to improve their precision and accuracy. However, speed of DCF is sacrificed in pursuit of better performances.

In order to adapt to appearance changes of tracked objects, an appearance model is maintained and updated at each frame for most DCF trackers. Due to its updating scheme, historical appearance decays exponentially with the number of subsequent frames. The appearance in latest 2 seconds in a 60 FPS video has a similar weight to all appearances before these 2 seconds in the model. This makes the trackers prone to forget objects' early appearances and focus on more recent ones. Therefore, when the tracker has a false result, when the object is occluded, or when it is out of the view, it is very likely that the tracker learns appearances of the background using this scheme, which will further lead to lost of object in the following frames.

\begin{figure}[t]
	\label{fig:scene}
	\includegraphics[width=\columnwidth]{fig1.pdf}
	\caption{Comparison between traditional DCF with appearance models and DCF with the proposed augmented memory. Multiple historical views are selected and stored to be used in training so that it contains more historical appearance information. Traditional DCF uses an gradually decaying appearance model and is prone to drift when drastic appearance variation happens. Red and blue boxes denote the tracking results of our tracker and others respectively. Ground truth is displayed as green box.}
\end{figure}
Additionally, traditional DCF framework has a low discriminative power because of the lack of negative training samples. Spatial regularization~\cite{Danelljan2015ICCV,Danelljan2016ECCV, Luke2017CVPR} and target cropping~\cite{Galoogahi2015CVPR,Galoogahi2017ICCV,Huang2019ICCV,Fu2019IROS} were used to expand search region and extract background patches as negative samples. Introducing context and repressing response to it can also help discriminate objects from complex scenes~\cite{Mueller2017CVPR}. These methods all propose effective ways to solve the problem, but not efficient ones.

This work proposes an augmented memory for correlation filters (AMCF) to perform efficient object tracking with strong discriminative power, which can easily be implemented on UAVs with only one CPU. Augmented memory is used to better memorize previous appearances of objects, with a novel application of image similarity criteria pHash~\cite{Kozat2001ICIP} to carefully select what to memorize. Views in the memory and current view are simultaneously used in training the correlation filter so that it has suitable responses to both previous and current object appearances. Compressed context learning is proposed to rapidly learn the background so that discriminative power is efficiently raised. AMCF is evaluated extensively on the authoritative UAVDT and UAV123 datasets. The results show its competitive performance on CPU at over 40 FPS compared with top trackers.
\section{related works}\label{sec:RELATEDWORK}
\subsection{Real-time tracking for UAV using DCF}
UAV object tracking has flourishing applications \cite{Fu2014ICUAS,2016YinTrans,Cheng2017IROS,Leira2017ICUAS,Bonatti2019IROS2}. Different from generic object tracking operating in videos shot by stationary cameras, tracking for UAV requires trackers to perform robustly even with the drastic motion of on-board camera. Motion of drone camera combined with that of objects makes precise and robust tracking difficult. Since in most cases, the movement of the drone is going to take largely depends on its perception result, tracking for UAV also requires a high processing speed of the tracker.

Generative and discriminative methods have been applied to visual object tracking. One of the discriminative methods, DCF, has been widely adopted to perform the task. Although the original works~\cite{Bolme2010CVPR,Henriques2012ECCV,Henriques2015TPAMI} showed its exceeding performance in speed, they can hardly meet the requirement for accurate as well as robust tracking, and most current trackers have sacrificed their speed for better performances. A novel tracker that can balance the speed and performance is therefore called for.
\subsection{Model update scheme of DCF framework}
One significant difference between DCF and deep-learning based tracking methods is that DCF can track objects online without any pre-training on appearances of the objects. This is achieved because DCF framework usually maintains an appearance model that is updated on a frame-to-frame basis~\cite{Henriques2015TPAMI, Danelljan2015ICCV, Galoogahi2017ICCV, Li2018CVPR, Fu2019IROS, Huang2019ICCV}. To do that, mostly adopted scheme is that a new model in the new frame is composed of around 99\% of the previous model and around 1\% of the new appearance. This 1\% is treated as the learning rate. Some trackers use only new appearance as the new model~\cite{Li2018CVPR}. Unfortunately, the updating scheme causes a model decay, which means the appearance in early frames only takes up a small weight in this model. Therefore, when occlusion, out-of-view, or lost track of object happens, trackers tend to learn appearances of the background. This is not robust enough.
\subsection{Negative samples and background noise in DCF}
The efficiency of DCF stems from its transformation of correlation operations into frequency domain. To do that, object image is cyclically shifted and extracted as samples implicitly. For traditional DCF framework, the search area is limited to prevent the correlation filter to learn too much from the background. However, only positive sample is essentially exploited in this manner. Several measures are taken to expand search region and feed background patches to training as negative samples~\cite{Galoogahi2017ICCV, Danelljan2015ICCV, Mueller2017CVPR, Fu2019IROS, Huang2019ICCV}. Typically, \cite{Danelljan2015ICCV} uses spatial punishment to suppress background learning, and \cite{Galoogahi2017ICCV} crops the target and background separately. \cite{Mueller2017CVPR} proposes to introduce context of the object and suppress the response to it. Despite their effectiveness, in order to be applied in UAV tracking, the efficiency of these methods is not sufficient.

\subsection{Tracking by deep learning}
Deep learning is demonstrating its outstanding performance in various tasks. In DCF-based tracking, deep features are extracted by convolutional neural networks (CNN) in~\cite{Danelljan2015ICCVW,Ma2015ICCV,Li2017ICCVW} to further improve performance by strengthening object appearance representation. In addition to DCF-based tracking methods, end-to-end learning\cite{Valmadre2017CVPR}, deep reinforcement learning~\cite{Yun2017CVPR}, multi-domain network~\cite{Nam2016CVPR} and recurrent neural networks (RNNs)~\cite{Cui2016CVPR} directly use deep learning to perform tracking tasks. Despite their slightly superior performance, a high-end GPU is required for them to be trained and implemented. Even with that condition, most of them still run at low FPS. Therefore, deep-learning is not as suitable as DCF for aerial tracking tasks.
\begin{figure*}[!t]
	\centering
	\includegraphics[width=0.95\textwidth]{Mainstructure.pdf}
	\caption{\textbf{Overall structure of AMCF.} Several historical views are stored in the memory queue and assigned with different desired responses according to its distance to the current frame. The selection of view is based on a difference score calculated by perceptual hashing algorithm. Along with views in the memory queue, context is also used in training. Context of the current frame is first compressed and given a weight before it is fed into training process. Tracking code and video can be seen respectively: \url{https://github.com/vision4robotics/AMCF-tracker} and \url{https://youtu.be/CGH5o2J1ohI}. }
	\label{fig:mainstructure}
\end{figure*}
\section{review of traditional dcf}\label{sec:DCF}
Learning traditional discriminative correlation filters~\cite{Galoogahi2017ICCV} is to optimize the following function:
	\begin{equation}\label{eq:dcfobjective}
	f(\mathbf{w}) = \Vert \mathbf { X }\mathbf { w }-\mathbf{y}\Vert _2^2 +\lambda \Vert \mathbf { w } \Vert _2^2 \ ,
	\end{equation}

\noindent where $\mathbf{X}$ is the sample matrix produced by circulating feature vector $\mathbf{x}\in\mathbb{R}^{M\times N}$, $\mathbf{w}$ is the trained filter and $\lambda$ is for regularization. It uses a model update scheme as follows:
\begin{equation}
\mathbf{m_t} = (1-\alpha )\mathbf{m_{t-1}} + \alpha \mathbf{x_t}\ ,
\end{equation}
\noindent where $\mathbf{m_t}$ and $\mathbf{ x_t }$ denotes the model and object appearance feature in the $t$-th frame respectively, $\alpha$ is the fixed learning rate.  Early appearances of the object are decaying exponentially.
\section{augmented memory for dcf}\label{sec:METHOD}
In this section, learning augmented memory correlation filters for real-time UAV tracking is presented. The main structure of AMCF tracker is illustrated in Fig.~\ref{fig:mainstructure}, and the objective function is as follows:
\begin{equation}
\begin{aligned}
f_t(\mathbf{w})=&\Vert\mathbf{X}_{c}\mathbf{w}-\mathbf{y}_{c}\Vert_2^2+\lambda_2\sum_{k=0}^{K}\Vert\mathbf{X}_{k}\mathbf{w}-\mathbf{y}_{k}\Vert_2^2\\
&+\lambda_3\Vert (\mathbf{H}\odot \mathbf{X}_b) \mathbf{w}\Vert_2^2+\lambda_1\Vert \mathbf{w}\Vert_2^2
\end{aligned} \ ,
\end{equation}

\noindent where $\mathbf{X}_c$, $\mathbf{X}_k$ and $\mathbf{X}_b$ presents the sample matrix generated by circulating feature maps $\mathbf{x}_c$, $\mathbf{x}_k$ and $\mathbf{x}_b$. $\mathbf{x}_{c}$ represents the extracted patch in current frame, $\mathbf{x}_0$ is the training patch sampled at the first frame, $\mathbf{x}_{k} \ (k\in \{1,2, ... ,$K$\}, K<<M)$ is the $k$-th view from the memory queue introduced in \ref{subsec:Selection}, where $M$ is the length of the sequence. $\mathbf{y}_{c}$ and $\mathbf{y}_{k}$ are distinct desired response of current frame and the ones in the memory (explained in \ref{subsec:Response}). $\mathbf{x}_b$ denotes compressed context patch, $\mathbf{H}$ refers to a suppression matrix generated by circulating $\mathbf{h} \in \mathbb{R}^{M\times N} $ and its function is to remove the object from the compressed context (explained in \ref{subsec:Context}). $\lambda_k \ (k=1,2,3)$ are adjustable parameters that determines the importance of corresponding patch.
\subsection{Augmented memory}\label{subsec:Selection}
\subsubsection{Memory queue}
Basically, a first-in first-out queue is maintained with a total length of $K$ to store $K$ historical views, so that they can be exploited by the training of a correlation filter in each frame. Before the memory queue is full, i.e., $L<K$ (with $L$ being the number of views currently stored), only $L$ views are fed in the training process. Otherwise, all $K$ historical views are used to train the correlation filter. For efficiency reasons, the value of $K$ is significantly smaller than the total number of the sequence.
\subsubsection{View selection}
Since the number of views that can be stored is limited, it is important that different views contain different appearance details. Therefore, only when the appearance of object is significantly different than the last selected view is this appearance allowed into the memory queue. Perceptual hashing algorithm (PHA)~\cite{Kozat2001ICIP} is adopted to determine the level of difference between two appearances. Specifically, the gray images are firstly transformed to frequency domain by discrete cosine transform (DCT). Only the low frequency region with high energy density is retained, denoted as $\mathbf{B} \in \mathbb{R}^{S\times S}$. Every element $b_{ij}$ ($i$ and $j$ denote the index of the element) in $\mathbf{B}$ is then compared with the average value of $\mathbf{B}$ to generate respective element of $p_{ij}$ in image's hashing matrix $\mathbf{P}\in \mathbb{R}^{S\times S}$:
\begin{equation}
if \ b_{ij}> \sum_{i=1}^{S}\sum_{j=1}^{S} b_{ij}/S^2 \ then \ p_{ij}=1; \ else \  p_{ij}=0.
\end{equation}

Difference score of the last view and the current view is calculated using respective hashing matrices $\mathbf{P}^l$ and $\mathbf{P}^c$:
\begin{equation}
score=\frac{\sum_{i=1}^{S}\sum_{j=1}^{S}(p_{ij}^c\oplus p_{ij}^l)}{S^2} \ ,
\end{equation}
where $p_{ij}^c$ and $p_{ij}^l$ respectively denote the element of hashing matrix $\mathbf{P}^c$ and $\mathbf{P}^l$. And $\oplus$ is the XOR operator.
If the score is more than threshold $\tau$, two appearances are considered different and current one is selected into the memory queue.
\subsection{Different desired responses}\label{subsec:Response}
Earlier selected views generally have a lower similarity to the current appearance than the later selected ones. Therefore, different desired responses are assigned to different views in the memory queue. By altering the maximum and the variance of Gaussian function, lower maximum and larger variance of desired responses are generated for early views:
\begin{equation}
\begin{aligned}
&\mathbf{y}_{K}(\sigma_{K})=\nu \mathbf{y}_{c}(\mu\sigma_c)\\
& \mathbf{y}_{k}(\sigma_{k})=\nu \mathbf{y}_{k+1}(\mu\sigma_{k+1}) \ (k=1,2,...,K-1)
\end{aligned}\ ,
\end{equation}
\noindent  where $\mathbf{y}_c(\mu\sigma_c)$ denotes the desired response of the current frame with the maximum of $max(\mathbf{y}_c(\mu\sigma_c))$ and the variance of $\sigma_c$. The subscript of $\mathbf{y}$ represents the index value of response target in memory queue (lower values corresponds to earlier views). Parameters $\nu<1$ and $\mu>1$ make sure that maximum is decreasing and variance is increasing with the index decreasing. For the first frame of the sequence, the desired response is calculated as follows:
\begin{equation}
\mathbf{y}_0(\sigma_1)=\phi \mathbf{y}_c(\varphi\sigma_c) \ ,
\end{equation}
\noindent where $\phi<1$ and $\varphi>1$ are used to adjust the maximum and variance of the Gaussian distribution of the desired response.
\subsection{Compressed context learning}\label{subsec:Context}
In order to increase discriminative power of DCF, compressed context learning is proposed. Unlike traditional context learning, the enlarged search region is compressed to the size of the correlation filter. Then the pixel value where the object is located is lowered by applying a quadratic suppressing function, so as to remove the object from this patch. This compressed context is assigned zero response so that the response to the surrounding area of the object can be minimized and discriminative power can thus be enhanced.
\subsection{Learning and detection in AMCF}\label{subsec:solution}
\subsubsection{Learning process}
The optimization result of $f_t(\mathbf{w})$ for the $d$-th $(d\in \{1,...,D\})$ channel is calculated as follows:

\begin{equation}\label{eq:8}
\hat{\mathbf{w}}^d=\frac{\hat{\mathbf{M}}_{c}^d+\lambda_2\sum_{k=0}^{K}\hat{\mathbf{M}}_k^d}{\sum_{d=1}^{D}(\hat{\mathbf{A}}_{c}^d+\lambda_2\sum_{k=0}^{K}\hat{\mathbf{A}}_k^d+\lambda_3\hat{\mathbf{E}}^d)+\lambda_1} \ ,
\end{equation}
\noindent where $\hat{\mathbf{M}}=\hat{\mathbf{x}}^*\odot \hat{\mathbf{y}}$, $\hat{\mathbf{A}}=\hat{\mathbf{x}}^*\odot \hat{\mathbf{x}}$ and  $\hat{\mathbf{E}}=\hat{\mathbf{m}}^*_b\odot \hat{\mathbf{m}}_b$.
$\mathbf{m}_b=\mathbf{h}\odot \mathbf{x}_b$. $\mathbf{x}^*$ denotes the complex-conjugate of $\mathbf{x}$ and the operator $\odot$ stands for the element-wise product. Hat mark is the discrete Fourier transform (DFT) value.

A learning rate $\gamma$ is used to update the numerator $\hat{\mathbf{N}}_t^d$ and the denominator $\hat{\mathbf{D}}_t^d$ of the filter $\hat{\mathbf{w}}_t^d$ in the $t$-th frame:
\begin{small}
	\begin{equation}\label{eq:9}
	\begin{aligned}
	&\hat{\mathbf{w}}^d_t=\frac{\hat{\mathbf{N}}_t^d}{\sum_{d=1}^{D}\hat{\mathbf{D}}_t^d+\lambda_1}\\
	&\hat{\mathbf{N}}_t^d=(1-\gamma)\hat{\mathbf{N}}_{t-1}^d+\gamma\ ( \hat{\mathbf{M}}_{tc}^d+\lambda_2\sum_{k=0}^{K}\hat{\mathbf{M}}_{tk}^d)\\
	&\hat{\mathbf{D}}_t^d=(1-\gamma)\hat{\mathbf{D}}_{t-1}^d+\gamma\ (
	\hat{\mathbf{A}}_{tc}^d+\lambda_2\sum_{k=0}^{K}\hat{\mathbf{A}}_{tk}^d+\lambda_3\hat{\mathbf{E}}_{t}^d)
	\end{aligned}\ .
	\end{equation}
\end{small}

In order to make sure reliable channels contribute more to the final result, a channel weight $\mathbf{C}=\{c^d\}(d\in\{ 1,...,D\})$ is assigned to each channel and updated as follows:
\begin{equation}\label{eq:10}
	c^d_t=(1-\eta) c^d_{t-1}+\eta \frac{max(\hat{\mathbf{w}}^{d*}_t \odot \hat{\mathbf{x}}^d_{tc})}{\sum_{d=1}^{D}max(\hat{\mathbf{w}}^{d*}_t \odot \hat{\mathbf{x}}^d_{tc})}\ .
\end{equation}
\subsubsection{Detection in AMCF}
In detection phase, the following formula is used to generate the final response map $\mathbf{R}_t$ and update the position by searching the maximum value:
\begin{equation}
	\mathbf{R}_t=\mathscr{F}^{-1}(\sum_{d=1}^{D}{c}^d_t\hat{\mathbf{w}}^{d*}_{t-1} \odot \hat{\mathbf{z}}^d_t),
\end{equation}
\noindent where $\hat{\mathbf{w}}^{d*}$ and $\hat{\mathbf{z}}^d_t$ are respectively learned filter and current feature of search region in frequency domain, and $\mathscr{F}^{-1}$ denotes the inverse discrete Fourier transformation (IDFT).

\begin{algorithm}[h]

	\caption{AMCF tracker}
	\KwIn{	Groundtruth  in the first frame\\
		Subsequent frames
	}
	\KwOut{	Predicted position of target in $t>1$ frame}
	\label{alg:KAOTtrackerflow}
	\eIf{$t=1$}{
		Extract $\mathbf{x}_{f}$ and $\mathbf{x}_b$ centered at the groundtruth\\
		Use Eq.~(\ref{eq:8}) to initialize the filters $\mathbf{w}_1$\\
		Initialize channel weight model $\{c^d\}=1/D$
	}
	{
		Extract $\mathbf{z}_t$ centered at location on frame $t-1$\\
		Use Eq.~(\ref{eq:10}) to generate the response map\\
		Find the peak position of map and output\\
		Extract $\mathbf{x}_{t}$ and $\mathbf{x}_b$ centered at location on frame $t$\\
		Calculate the $score$  between $\mathbf{P}_L$ and $\mathbf{P}_t$\\
		\If{score>$\tau$}
		{
				Update FIFO memory queue
		}
		Use Eq.~(\ref{eq:8}) to update the filters $\mathbf{w}_t$ \\
		Use Eq.~(\ref{eq:9}) to update channel weight $\mathbf{C}_t$\\
	}
\end{algorithm}
\section{EXPERIMENTS}\label{sec:EXPERIMENT}
In this section, the presented AMCF tracker is comprehensively evaluated on two difficult datasets, i.e., UAVDT~\cite{Du2018ECCV} and UAV123~\cite{Mueller2016ECCV}, with 173 image sequences covering over 140,000 frames captured by UAV in various challenging scenarios. It is noted that the videos from both datasets are recorded at 30 FPS. 11 real-time trackers (CPU based) are used to compare with AMCF, i.e., ECO\_HC~\cite{Danelljan2017CVPR}, STRCF~\cite{Li2018CVPR}, MCCT\_H~\cite{Wang2018CVPR}, STAPLE\_CA~\cite{Mueller2017CVPR}, BACF~\cite{Galoogahi2017ICCV}, DSST~\cite{Danelljan2014BMVA}, fDSST~\cite{Danelljan2017TPAMI}, STAPLE~\cite{Bertinetto2016TPAMI}, KCC~\cite{wang2018kernel}, KCF~\cite{Henriques2015TPAMI}, DCF~\cite{Henriques2015TPAMI}. Furthermore, 15 deep-based trackers are compared with AMCF to further demonstrate its performance, i.e., ASRCF~\cite{Kenan2019CVPR}, ECO~\cite{Danelljan2017CVPR}, C-COT~\cite{Danelljan2016ECCV}, MCCT~\cite{Wang2018CVPR}, DeepSRTCF~\cite{Li2018CVPR}, ADNet~\cite{Yun2017CVPR}, CFNet~\cite{Valmadre2017CVPR},  MCPF~\cite{Zhang2017CVPR}, IBCCF~\cite{Li2017ICCVW}, CF2~\cite{Ma2015ICCV}, CREST~\cite{Song2017ICCV}, HDT~\cite{Qi2016CVPR}, FCNT~\cite{Wang2015ICCV}, PTAV~\cite{Fan2017ICCV}, TADT~\cite{Xin2019CVPR}. The evaluation criteria are strictly according to the protocol in two benchmarks~\cite{Du2018ECCV,Mueller2016ECCV}.
\begin{table}[!b]
	\setlength{\tabcolsep}{2mm}
	\centering
	\caption{Effectiveness study of AMCF on UAV123 and UAVDT. Module name displayed in abbreviations are CW (channel weight), AM (augmented memory) and CC (compressed context). }
	\begin{tabular}{l|c|c|c|c|c|c}
		\hline
		Dateset&\multicolumn{3}{c|}{UAV123}&\multicolumn{3}{c}{UAVDT}\\
		\hline
		Evaluation&PREC.&AUC&FPS&PREC.&AUC&FPS\\
		\hline
		AMCF&69.5&49.3&38.1&70.1 & 44.5&46.7 \\
		Baseline+CW+CC&68.5&48.3&42.6&67.3&44.0&53.1\\
		Baseline+CC+AM&67.4&47.8&42.6 &69.0&44.4&52.1\\
		Baseline+CW&66.8&46.8& 50.4 &67.9&44.0&65.5 \\
		Baseline&65.5&46.8& 59.1 &66.4&42.9&73.5 \\
		\hline
	\end{tabular}%
	\label{tab:effectivenssstudy}%
\end{table}%
\begin{figure*}[!t]
	\centering
	\includegraphics[width=0.49\linewidth]{uavdt_error_OPE.pdf}
	\includegraphics[width=0.49\linewidth]{uavdt_overlap_OPE.pdf}
	\\
	\includegraphics[width=0.49\linewidth]{uav123_error_OPE.pdf}
	\includegraphics[width=0.49\linewidth]{uav123_overlap_OPE.pdf}
	\caption{\textbf{Overall performance evaluation.} Precision and success plots of our tracker and other ten top real-time trackers on UAVDT and UAV123 datasets.}
	\label{fig:overall}
\end{figure*}
\begin{table*}[!t]
	\footnotesize
	\setlength{\tabcolsep}{2mm}
	\centering
	\caption{Average frame per second (FPS) and average precision as well as AUC of top real-time trackers on 173 image sequences. \textcolor[rgb]{ 1,  0,  0}{\textbf{Red}}, \textcolor[rgb]{ 0,  1,  0}{\textbf{green}} and \textcolor[rgb]{ 0,  0,  1}{\textbf{blue}} fonts indicate the first, second and third place, respectively. All results are obtained solely on CPU.}
	\begin{tabular}{l c c c c c c c c c c c c}
		\hline
		\multirow{2}{*}{\textbf{Tracker}}&\multirow{2}{*}{\textbf{AMCF}}&{ECO\_HC}&{MCCT\_H}&{STAPLE\_CA}&{KCC}&{BACF}&{STRCF}&{STAPLE}&{DSST}&{fDSST}&{KCF}&{DCF} \\
		&&\cite{Danelljan2017CVPR}&\cite{Wang2018CVPR}&\cite{Mueller2017CVPR}&\cite{wang2018kernel}&{\cite{Galoogahi2017ICCV}}&{\cite{Li2018CVPR}}&{\cite{Bertinetto2016TPAMI}}&{\cite{Danelljan2014BMVA}}&{\cite{Danelljan2017CVPR}}&{\cite{Henriques2015TPAMI}}&{\cite{Henriques2015TPAMI}} \\
		\hline
		\textbf{FPS} & {42.4} & {77.4} & {59.9} & {60.2} &{48.9}&{58.8}&{29.8}&{84.5}&{124.1}&\textbf{\textcolor[rgb]{0 0 1}{186.1}}&\textbf{\textcolor[rgb]{0 1 0}{795.7}}&\textbf{\textcolor[rgb]{1  0  0}{1120.7}}\\
		\textbf{Precision} & \textbf{\textcolor[rgb]{1  0  0}{69.8}} & \textbf{\textcolor[rgb]{1  0  0}{69.8}} & {66.1} & \textbf{\textcolor[rgb]{0 1 0}{67.7}} &{62.6}&{66.6}&\textbf{\textcolor[rgb]{0 0 1}{67.0}}&{66.6}&{60.7}&{60.1}&{53.3}&{54.2}\\
		\textbf{AUC} & \textbf{\textcolor[rgb]{1  0  0}{46.9}} & \textbf{\textcolor[rgb]{0  1  0}{45.3}} & {43.0} & {42.4} & {40.6} & \textbf{\textcolor[rgb]{0  0  1}{44.6}} & \textbf{\textcolor[rgb]{0  0  1}{44.6}} & {41.7} & {38.2} & {39.4} & {31.1} & {34.4}\\
		\hline
	\end{tabular}%
	\label{tab:fps}%
\end{table*}%
\subsection{Implementation details}
\label{subsec:EvaCri}
All the experiments of all trackers compared as well as AMCF are conducted on a computer with an CPU of i7-8700K (3.7GHz), 48GB RAM and NVIDIA GTX 2080. All trackers are implemented in MATLAB R2018a platform, and their original codes without modification are used for comparison. Memory length $K=5$, and the threshold for memory view selection is set to $\tau = 0.5$.

\subsection{Quantitative study}
\subsubsection{Effectiveness study}
AMCF tracker is firstly compared with itself with different modules enabled. The effectiveness evaluation result can be seen in Table~\ref{tab:effectivenssstudy}. With each module (channel weight CW, augmented memory AM, and compressed context CC) added to the baseline, the performance is steadily being improved.

\subsubsection{Overall performance}
In comparison with other top real-time trackers, AMCF has shown a superiority in terms of precision and accuracy on both benchmarks. Fig.~\ref{fig:overall} shows separate performance evaluation of AMCF on two benchmarks. AMCF has achieved satisfactory performances on both benchmarks. Specifically, AMCF performs the best on UAVDT, with improvement of 0.6\% and 1.2\% on precision and AUC score respectively. On UAV123, AMCF has achieved the second best performance. Since the object size in UAV123 is generally much larger than that in UAVDT because of the flying height of UAVs, many trackers with good performance on one benchmark can rank low on the other. One typical example is ECO\_HC. It ranks first on UAV123 but only come out at fifth place on UAVDT. AMCF, on the other hand, has a better generalization ability compared to most trackers. Overall evaluation for both benchmarks combined can be seen in Table~\ref{tab:fps}. AMCF has a slightly better overall performance than ECO\_HC, ranking the first place. But ECO\_HC has a relatively large variance. Therefore, it can be concluded that in terms of overall performance, AMCF performs favorably against other top real-time trackers. In terms of speed, AMCF, soly running on CPU, can also meet the requirement of real-time tracking (>30 FPS on a image sequence captured at 30 FPS).
\begin{figure*}[t]
	\centering
	\includegraphics[width=0.245\linewidth]{uavdt_Camera_motion_overlap_OPE.pdf}
	\includegraphics[width=0.245\linewidth]{uavdt_Background_clutter_overlap_OPE.pdf}
	\includegraphics[width=0.245\linewidth]{uav123_Viewpoint_change_overlap_OPE.pdf}
	\includegraphics[width=0.245\linewidth]{uav123_Aspect_ratio_change_overlap_OPE.pdf}
	\caption{\textbf{Attribute-based evaluation.} Success plots of four attributes. The first two attributes are from UAVDT and the rest of them are from UAV123. }
	\label{fig:attribute}
\end{figure*}
\subsubsection{Attribute-based performance}
\label{subsec:attr}
Attribute-based evaluation results on both benchmarks are shown in Fig.~\ref{fig:attribute}. It can be seen that the reason behind our satisfactory generalization ability originates from the combination of two of our core modules, i.e., augmented memory and compressed context learning. On UAVDT, when object is small, feature of objects decreases and positive samples are thus not enough for robust tracking. Compressed context learning simultaneously expands search region and brings more negative samples. Therefore, when there is camera motion and background clutter, AMCF performs satisfactorily. On UAV123, object is significantly closer, so viewpoint change and aspect ratio change can result in more drastic appearance changes. Augmented memory provides more appearance information on previous objects so that a desired response can be obtained when current view has some resemblance to previous views. Therefore, thanks to both modules, ARCF can handle both near objects with large viewpoint changes and distant objects with a small size on the image.
\begin{figure}[!t]
	\centering
	\includegraphics[width=0.93\columnwidth]{deep-uavdt_error_OPE.pdf}
	\\
	\includegraphics[width=0.93\columnwidth]{deep-uavdt_overlap_OPE.pdf}
	\caption{\textbf{Deep-based tracker comparison.} Top deep-based trackers are compared with AMCF on UAVDT. Tracking speeds other than AMCF are obtained on GPU.}
	\label{fig:deepcomparision}
\end{figure}
\subsection{Comparison with deep-based trackers}
On UAVDT, extra 15 deep-based trackers (trackers using deep learning methods or DCF-based trackers using deep features) are compared with AMCF. Precision and success plots can be seen in Fig.~\ref{fig:deepcomparision}. Surprisingly, AMCF still succeeds to exceed most of deep-based trackers in terms of precision and AUC scores. More specifically, AMCF achieved the best performance in precision, with 0.1\% slightly better than the second place ASRCF, while in AUC evaluation, AMCF achieved the second, falling behind ECO by only 0.9\%. In terms of tracking speed, AMCF is the fastest among the evaluated deep-based trackers. To sum up, in tracking distant objects, AMCF demonstrates superior tracking performance against both real-time trackers and deep-based trackers.

\begin{figure}[t]
	\centering
	\includegraphics[width=0.95\columnwidth]{comp.pdf}
	\caption{\textbf{Qualitative evaluation.} Top real-time trackers are compared with AMCF on \textit{S1001} and \textit{S1201} on UAVDT, as well as \textit{wakeboard5}, \textit{car16\_1}, \textit{car7}, and \textit{car1\_s} on UAV123. }
	\label{fig:comp}
\end{figure}
\subsection{Qualitative study}
Figure~\ref{fig:comp} intuitively demonstrates the aforementioned results. The first two sequences show the ability to track distant objects and adapt to view changes on UAVDT respectively. The third and fourth sequences show those abilities of AMCF on UAV123. Capability of resisting occlusion is demonstrated in the fifth sequence. The last one shows two modules can work smoothly together.

\section{CONCLUSIONS}\label{sec:CONCLUSIONS}
In this work, augmented memory for correlation filters is proposed. Essentially, augmented memory maintains a FIFO queue to store distinct previous views. Each stored view in the memory will be assigned a desired response. Along with the feature of the object in the current frame, all views are simultaneously used to train a correlation filter that can adapt to new appearances and has response to previous views at the same time. Compressed context learning provides more negative samples and suppresses responses to surrounding areas of the tracked object. Extensive experiment results proved that AMCF has competitive performance and tracking speed compared to top real-time trackers. AMCF also demonstrates an outstanding generalization power that can track both near objects with large view change and distant objects with small size in the image. Future work can include introducing a confidence check to prevent false tracking results to be selected as a view. This method can also be applied to more powerful baselines in replacement of model update.

\section*{ACKNOWLEDGMENT}
This work is supported by the National Natural Science Foundation of China (No. 61806148) and the Fundamental Research Funds for the Central Universities (No. 22120180009).

\bibliographystyle{IEEEtran}