#  Hal: Improved Text-Image Matching by Mitigating Visual Semantic Hubs

Fangyu Liu1, Rongtian Ye2∗, Xun Wang3∗, Shuaipeng Li4
1University of Cambridge, Cambridge, UK
2Aalto University, Espoo, Finland
3Malong Technologies, Shenzhen, China
4SenseTime Research, Beijing, China
Equal contributions.Correspondence to F. Liu<EMAIL_ADDRESS>
###### Abstract

The _hubness problem_ widely exists in high-dimensional embedding space and is
a fundamental source of error for cross-modal matching tasks. In this work, we
study the emergence of hubs in _Visual Semantic Embeddings_ (VSE) with
application to text-image matching. We analyze the pros and cons of two widely
adopted optimization objectives for training VSE and propose a novel hubness-
aware loss function (Hal) that addresses previous methods’ defects. Unlike (?)
which simply takes the hardest sample within a mini-batch, Hal takes all
samples into account, using both local and global statistics to scale up the
weights of “hubs”. We experiment our method with various configurations of
model architectures and datasets. The method exhibits exceptionally good
robustness and brings consistent improvement on the task of text-image
matching across all settings. Specifically, under the same model architectures
as (?) and (?), by switching only the learning objective, we report a maximum
R@1 improvement of 7.4% on MS-COCO and 8.3% on Flickr30k.111Our code is
released at: https://github.com/hardyqr/HAL.

## Introduction

The hubness problem is a general phenomenon in high-dimensional space where a
small set of source vectors, dubbed hubs, appear too frequently in the
neighborhood of target vectors (?). As embedding learning goes deeper, it has
been a concern in various contexts including object classification (?), image
feature matching (?) in Computer Vision and word embedding evaluation (?; ?),
word translation (?; ?) in NLP. It is described as “a new aspect of the
dimensionality curse” (?; ?).

In this work, we study the hubness problem in the task of text-image matching.
In recent years, deep neural models have gained a significant edge over non-
neural methods in cross-modal matching tasks (?). Text-image matching has been
one of the most popular ones among them. Most deep methods involve two phases:
1) training: two neural encoders (one for image and one for text) are learned
end-to-end, mapping texts and images into a joint space, where items (either
texts or images) with similar meanings are close to each other; 2) inference:
for a query vector in modality A, a nearest neighbor search is performed to
match the query vector against all item vectors in modality B. As the
embedding space is learned through jointly modeling vision and language, it is
often referred as _Visual Semantic Embeddings_ (VSE). Recent work on VSE has
shown a clear trend of growing dimensions in order to obtain better embedding
quality (?). With deeper embeddings, visual semantic hubs increase
dramatically. Such property is undesired as the data is structured in the form
of text-image pairs and a one-to-one mapping firmly exists among all text and
image points.

Figure 1: Visualization of our proposed objective, which is to leverage both
local and global negative samples to identify hubs in high-dimensional
embeddings and learn to avoid them. Local negatives are the ones within mini-
batch while global ones are sampled from the whole training set.

However, the hubness problem is neither well noticed nor well addressed by
current methods of training VSE. Since the start of this line of work (?; ?),
VSE models use either sum-margin (Sum, Eq. (2)) or max-margin (Max, Eq. (3))
ranking loss (both are triplet based) to cluster the positive pairs and push
away the negative pairs. Sum is robust across various settings but treats all
triplets equivalently and utilizes no information from hard samples, thus does
not address the hubness problem at all. Max excels at mining hard samples and
achieved state-of-the-art on MS-COCO (?). However, it does not explicitly
consider the hubness problem, nor does it resist noise well. New models on
training VSE have been consistently brought up in recent years. They include
incorporating extra knowledge to augment original data, eg. generating
adversarial samples (?), and designing high-level objective that utilizes pre-
trained models to align salient entities across modalities (?; ?). However,
ever since (?), the basic scheme of training VSE has not been enhanced. In
this work we show that exploiting the data per se has yet reached its limit.

To fully extract the information buried within, we combine robustness with
hard sample mining, proposing a self-adjustable hubness-aware loss called Hal.
Hal takes both global (sampled from the whole training set) and local
statistics (obtained from mini-batch) into account, leveraging information of
hubs to automatically adjust weights of samples. It learns from hard samples
and is robust to noise at the same time by taking multiple samples into
account. Specifically, we exploit a sample’s relationship to 1) other samples
within the mini-batch; 2) its $k$-nearest neighbor queries in a memory bank,
to decide its weight. The larger a hub is, the more it should contribute to
the loss, resulting in a mitigation of hubs and an improvement of embedding
quality. Through a thorough empirical comparison, we show that our method
outperforms Sum and Max loss on various datasets and architectures by large
margins.

The major contribution of this work is a novel training objective (Hal) that
utilizes both local and global statistics to identify hubs in high-dimensional
embeddings. Compared with strong baselines (?) and (?), Hal improves R@$1$ by
a maximum of $7.4\%$ on MS-COCO and $8.3\%$ on Flickr30k.

## Method

We first introduce the basic formulation of VSE model; then review widely-
adopted methods that we will compare to; in the end, propose our intended loss
function.

### Basic Formulation

The bidirectional text-image matching framework consists of a text encoder and
an image encoder. The text encoder is composed of word embeddings, a GRU (?)
(or other sequential models) layer and a temporal pooling layer. The image
encoder is usually a deep CNN and a linear layer. We use ResNet152 (?),
Inception-ResNet-v2 (IRv2) (?) and VGG19 (?) pre-trained on ImageNet (?) in
our models. We denote them as functions $f$ and $g$, which map text and image
to some vectors of size $d$ respectively.

For a text-image pair $(t,i)$, the similarity of $t$ and $i$ is measured by
cosine similarity:

$S_{it}=\bigg{\langle}\frac{f(t)}{\|f(t)\|_{2}},\frac{g(i)}{\|g(i)\|_{2}}\bigg{\rangle}:\mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow\mathbb{R}.$
(1)

During training, a margin based triplet ranking loss is usually adopted to
cluster positive pairs and push negative pairs away from each other. There are
mainly two prevalent choices which are Sum and Max. We introduce them in the
next section along with our newly proposed non-triplet-based loss Hal.

### Revisit Two Triplet-based Loss Functions

In this section we review the two popular loss functions that have been
adopted for training VSE and analyze their pros and cons.

#### Sum-margin Loss (Sum).

Sum is a standard triplet loss adopted from the metric learning literature and
has been used for training VSE since the start of this line of work (?; ?).
Its early form can be found in (?) which was used for training joint word-
image embeddings. Formally, Sum is defined as:

$\begin{split}\mathcal{L_{\textsc{Sum}}}=\sum_{i\in I}\sum_{\bar{t}\in
T\backslash\\{t\\}}[\ \alpha-S_{it}+S_{i\bar{t}}\ ]_{+}\\\ +\sum_{t\in
T}\sum_{\bar{i}\in I\backslash\\{i\\}}[\ \alpha-S_{ti}+S_{t\bar{i}}\
]_{+},\end{split}$ (2)

where $[\cdot]_{+}=\max(0,\cdot)$; $\alpha$ is a preset margin; $T$ and $I$
are text and image encodings in a mini-batch; $t$ is the descriptive text for
image $i$ and vice versa; $\bar{t}$ denotes non-descriptive texts for $i$
while $\bar{i}$ denotes non-descriptive images for $t$.

The major shortcoming of Sum lies in the fact that it views all valid triplets
within a mini-batch as equal and assigns identical weights to all, leading to
a failure of identifying informative pairs. As we will detail in the
following, a simple “hard” weighting by taking only the hardest triplet can
greatly enhance a triplet-based loss’s performance in training VSE.

#### Max-margin Loss (Max).

? (?) proposed Max fairly recently (2018). Max differs from Sum by considering
only the largest violation of margin within the mini-batch instead of summing
over all margins:

$\begin{split}\mathcal{L_{\textsc{Max}}}=\sum_{i\in I}\max_{\bar{t}\in
T\backslash\\{t\\}}[\ \alpha-S_{it}+S_{i\bar{t}}\ ]_{+}\\\ +\sum_{t\in
T}\max_{\bar{i}\in I\backslash\\{i\\}}[\ \alpha-S_{ti}+S_{t\bar{i}}\
]_{+}.\end{split}$ (3)

We refer to Max as a “hard” weighting strategy as it implicitly assigns a
weight of $1$ to the hardest triplet and $0$ to all other triplets. Though Max
was not used in the context of VSE before, it was thoroughly exploited in
other embedding learning tasks (?). As analyzed by (?), a rigid stress on hard
negatives like Max makes its gradient easily dominated by noise, being a
result of either deficiency of the model architecture or data’s structure per
se. Through error analysis, we notice that the existence of _pseudo hardest
negatives_ in training data is a major source of noise for Max. During
training, only the hardest negative in a mini-batch is considered. If that
sample contained happens to be incorrectly labeled or inaccurate, misleading
gradients would be imposed on the network. Notice that Sum eases such noise in
labels by taking all mini-batch’s samples into account. When a small set of
samples are with false labels, their false gradients would be canceled out by
other correct negatives within the mini-batch, preventing the model from an
optimization failure or overfitting to incorrect labels. That being said, Sum
fails to make use of hard samples and does not address the hubness problem at
all. It thus performs poorly on a well-labeled dataset like MS-COCO.

Besides, both Sum and Max are triplet based, considering only one positive
pair and one negative pair at a time. Such sampling manner isolates each
triplet and disregards the overall distribution of data points. What’s more,
the triplet-style heuristics is easy for selected triplets to satisfy after
the early stage of training, leaving very little information in gradients in
the late stage (?). As opposed to triplet loss, our proposed NCA-based loss,
to be introduced in the next section, characterizes the whole local
neighborhood and take the affinities among all pairs into consideration.

### The Hubness-Aware Loss (Hal)

On the one hand, we obtain the greatest possible robustness through
considering multiple samples; on the other hand, we try to make sure the
samples being considered are hard enough - so that the training is effective.
We tackle this problem by leveraging information from visual semantic hubs.
Inspired by Neighborhood Component Analysis (NCA) (?) used for classification
task, we propose a self-adaptive Hubness-Aware Loss (Hal) that weights samples
within a mini-batch according to both local and global statistics. More
specifically, Hal assigns more weights to samples which appear to be hubs
(being close neighbors to multiple queries), judging from both the current
mini-batch and a memory bank sampled from the whole training set.

How global and local information are used will be detailed shortly. Before
that, we briefly explain NCA and discuss why it is a natural choice for
addressing hubness problem. In the classification context, NCA is formulated
as:

$\begin{split}\mathcal{L_{\textsc{Nca}}}=\sum_{i=1}^{N}\bigg{(}\log\sum_{y_{i}=y_{j}}e^{S_{ij}}-\log\sum_{k=1}^{N}e^{S_{ik}}\bigg{)},\end{split}$
(4)

where $N$ is the number of samples. And the gradient of
$\mathcal{L_{\textsc{Nca}}}$ w.r.t. positive and negative samples are computed
as:

$\begin{split}w^{+}=\bigg{|}\frac{\partial\mathcal{L_{\textsc{Nca}}}}{\partial{S_{ij}}^{+}}\bigg{|}=\frac{e^{S_{ij}}}{\sum_{y_{i}=y_{j}}e^{S_{ij}}}-\frac{e^{S_{ij}}}{\sum_{k=1}^{N}e^{S_{ik}}},\\\
w^{-}=\bigg{|}\frac{\partial\mathcal{L_{\textsc{Nca}}}}{\partial{S_{ij}}^{-}}\bigg{|}=\frac{e^{S_{ij}}}{\sum_{k=1}^{N}e^{S_{ik}}}.\end{split}$
(5)

For a sample $S_{ij}$, when it is a close neighbor to multiple items in the
search space, ie. being a hub, its weight as a positive is reduced and that as
a negative is scaled up, meaning that it receives more attention during
training. This basic philosophy of NCA will be used in both the local and
global weighting schemes in the following.

#### a) Global weighting through Memory Bank (Mb).

One of the most desired property of an NCA-based loss is that it automatically
assigns weights to all samples in one batch of back-propagation through
computing gradients as suggested above. The more data points we have, the more
reliable a hub can be identified. The most ideal approach of leveraging hubs
is utilizing the idea of NCA and searching for hubs across the whole training
set, so that all samples are compared against each other and information is
made fully use of. However, it is computationally infeasible to minimize such
objective function on a global scale - especially when it comes to computing
gradients for all training samples (?). We thus design hand-crafted criteria
that follows the NCA’s idea to explicitly compute weight of samples but does
not require gradient computation. Specifically, at the beginning of each
epoch, we sample all over training set and compute their embeddings to create
a memory bank $M$ that approximates the global distribution of training data.
Then we utilize relationships among mini-batch and memory bank to compute a
global weight for each sample in the batch, highlighting hubs and passing the
weight to the next stage of local weighting.

We define a function $\texttt{kNN}(x,M,k)$ to return the $k$ closest points
(measured by $l_{2}$ distance) in point set $M$ to $x$ and the global
weighting of Hal can be formulated as:

$\begin{split}W_{ii}=1-e^{\alpha(S_{ii}-\epsilon_{1})}/\\\
\bigg{(}e^{\alpha(S_{ii}-\epsilon_{1})}+\sum_{\bar{t}\in
K_{1}}e^{\alpha(S_{i\bar{t}}-\epsilon_{2})}+\sum_{\bar{j}\in
K_{2}}e^{\alpha(S_{\bar{j}i}-\epsilon_{2})}\bigg{)},\\\ W_{it}=\bigg{(}\
\sum_{\bar{t}\in K_{1}}e^{\beta(S_{i\bar{t}}-\epsilon_{2})}+\sum_{\bar{i}\in
K_{2}}e^{\beta(S_{\bar{i}t}-\epsilon_{2})}\bigg{)}/\\\
\bigg{(}e^{\beta(S_{ii}-\epsilon_{1})}+e^{\beta(S_{tt}-\epsilon_{1})}+\sum_{\bar{t}\in
K_{1}}e^{\beta(S_{i\bar{t}}-\epsilon_{2})}+\sum_{\bar{i}\in
K_{2}}e^{\beta(S_{\bar{i}t}-\epsilon_{2})}\bigg{)},\end{split}$ (6)

where $W_{ii},W_{it}$ represent weight of positive and negative samples
respectively;
$K_{1}=\texttt{kNN}(i,M_{T}\backslash\\{t\\},k),K_{2}=\texttt{kNN}(t,M_{I}\backslash\\{i\\},k)$;
$\alpha,\beta$ are temperature scales and $\epsilon_{1},\epsilon_{2}$ are
margins. For positive weighting, when the anchor’s neighborhood is dense, the
denominator of the second term gets larger and so does $W_{ii}$. As will be
shown in gradient computation (Eq. (8)), a large $W_{ii}$ scales up positive
sample’s gradient. Analogously, for negative weighting, a dense neighborhood
leads to a large $W_{it}$ and increases the gradient of that negative sample
in local weighting.

Table 1: Quantitative results on Flickr30k (?). “ours” means our own implementation.  # | architecture |  loss abc | image$\rightarrow$text abc | text$\rightarrow$image |
---|---|---|---|---|---
R@$1$ | R@$5$ | R@$10$ | Med r | Mean r | R@$1$ | R@$5$ | R@$10$ | Med r | Mean r | rsum
1.1 | GRU+VGG19 | Sum | 30.0 | 59.6 | 67.7 | 4.0 | 34.7 | 22.8 | 49.4 | 61.4 | 6.0 | 47.5 | 291.0
1.2 | Max | 30.1 | 56.3 | 67.9 | 4.0 | 30.5 | 21.3 | 47.1 | 58.7 | 6.0 | 40.2 | 281.4
1.3 | Hal | 38.4 | 63.3 | 73.4 | 3.0 | 20.1 | 26.7 | 53.3 | 64.9 | 5.0 | 32.1 | 320.0
1.4 |  Order (VGG19, ours) (?) | Sum | 31.4 | 58.3 | 69.4 | 4.0 | 26.9 | 24.2 | 50.9 | 62.9 | 5.0 | 34.3 | 297.1
1.5 | Max | 32.1 | 58.0 | 69.9 | 4.0 | 23.1 | 22.7 | 49.4 | 61.3 | 6.0 | 32.9 | 293.4
1.6 | Hal | 36.4 | 62.2 | 73.0 | 3.0 | 20.4 | 26.6 | 54.4 | 65.6 | 4.0 | 31.0 | 318.3
1.7 |  SCAN (?) | Max | 67.9 | 89.0 | 94.4 | - | - | 43.9 | 74.2 | 82.8 | - | - | 452.2
1.8 | Hal | 68.6 | 89.9 | 94.7 | 1.0 | 3.3 | 46.0 | 74.0 | 82.3 | 2.0 | 14.3 | 455.5

#### b) Local weighting through loss function.

Here we adapt the NCA loss for classification for our context of producing a
matching among two sets of points:

$\begin{split}\mathcal{L_{\textsc{Hal}}}=\frac{1}{N}\sum_{i=1}^{N}\Big{(}\frac{1}{\gamma}\log(1+\sum_{m\not=i}e^{\gamma
W_{mi}(S_{mi}-\epsilon)})\\\ +\frac{1}{\gamma}\log(1+\sum_{n\not=i}e^{\gamma
W_{in}(S_{in}-\epsilon)})\\\ -\log(1+W_{ii}S_{ii})\Big{)},\\\ \end{split}$ (7)

where $\gamma$ is a temperature scale; $\epsilon$ is a margin; $N$ is number
of samples within the mini-batch. And the gradients with respect to negative
and positive samples are computed as:

$\begin{split}w^{+}=\bigg{|}\frac{\partial\mathcal{L_{\textsc{Hal}}}}{\partial{S_{ij}}^{+}}\bigg{|}=\frac{W_{ij}}{1+W_{ij}S_{ij}}\text{
if }i=j,\\\
w^{-}=\bigg{|}\frac{\partial\mathcal{L_{\textsc{Hal}}}}{\partial{S_{ij}}^{-}}\bigg{|}=\underbrace{\frac{W_{ij}e^{\gamma
W_{ij}(S_{ij}-\epsilon)}}{1+\sum_{m\neq j}e^{\gamma
W_{mj}(S_{mj}-\epsilon)}}}_{\text{weighted by image modality}}\\\
+\underbrace{\frac{W_{ij}e^{\gamma W_{ij}(S_{ij}-\epsilon)}}{1+\sum_{n\neq
i}e^{\gamma W_{in}(S_{in}-\epsilon)}}}_{\text{weighted by text
modality}}.\end{split}$ (8)

Unlike a naive NCA aiming for classifying samples in only one direction, the
first and second term of $\mathcal{L_{\textsc{Hal}}}$ punish mistakes made
during searching targets among the two modalities in both directions. As shown
in gradients, the sample is weighted according to its significance as a hub in
both modalities.

Hal vs Max. As pointed out by (?), Max actually implicitly mitigates the
hubness problem by targeting the hardest triplet only. A hub, by definition,
is a close (potentially nearest) neighbor to multiple queries and would thus
be punished by Max for multiple times (in different batches). (?)’s
experiments also verified such theory empirically. However, it is a risky
choice as the hardest sample within a mini-batch can easily be a pseudo
hardest negative as analyzed above. As we would show in experiments, Hal
prevails in a broader range of data and model configurations while Max only
performs well on some specific circumstances where both training data and
encoders are of ideal quality. Also, Hal is essentially leveraging more
information than Max. In Max, only hub that violates margin the most gets to
impose a gradient on network’s parameters while Hal softly considers all hubs,
big or small, by assigning them weights.

## Experiments

This section is divided into 1) Experimental Setups and 2) Main Results, where
detailed configurations of experiments are introduced in 1) and comparison &
analysis of main results are in 2).

### Experimental Setups

Dataset. We use MS-COCO (?) and Flickr30k (?) as our experimental datasets.
For MS-COCO, there have been several different splitting protocols being used
in the community. We use the same split as (?): 113,287 images for training,
5,000 for validation and 5,000 for testing.222Note that 1 image in MS-COCO and
Flickr30k has 5 captions, so 5 text-image pairs are used for every image.
During testing, scores are computed as the average of 5 folds of 1k images. As
many of the previous works report test results on a 1k test set (a subset of
the 5k one), we would experiment with both protocols. We refer to the 1k test
set as $c1$ and the 5k test set as $c2$. Flickr30k has 30,000 images for
training; 1,000 for validation; 1,000 for testing.

Evaluation metrics. We use R@$K$s (recall at $K$), Med r, Mean r and rsum to
evaluate the results. R@$K$: the ratio of “# of queries that the ground-truth
item is ranked in top $K$” to “total # of queries” (we use
$K\in\\{1,5,10\\}$); Med r: the median of the ground-truth ranking; Mean r:
the mean of the ground-truth ranking; rsum: the sum of R@$\\{1,5,10\\}$ for
both text$\rightarrow$image and image$\rightarrow$text. R@$K$s and rsum are
the higher the better while Med r and Mean r are the lower the better. We
compute all metrics for both text$\rightarrow$image and image$\rightarrow$text
retrieval. During training, we follow the convention of taking the model with
the maximum rsum on validation set as the best model for testing.

Model and training details. We use $300$-$d$ word embeddings and $1024$
internal states for GRU text encoder (all randomly initialized with Xavier
init. (?)); all image encodings are obtained from image encoders pre-trained
on ImageNet (for fair comparison, we don’t finetune any image encoders);
$d=1024$ for both text and image embeddings. For more details about
hyperparameters and training configurations please refer to Table 3 and code
release: https://github.com/hardyqr/HAL.

### Main Results

Here we present the major quantitative and qualitative findings with analysis
regarding Hal’s performance, hyperparameters’ choice and hubs’ distributions.

Table 2: Quantitative results on MS-COCO (?). First three blocks (line 2.1-2.12) are using protocol $c2$ (5k test set); the last two blocks (line 2.13-2.24) is using $c1$ (1k test set) in convenience of comparing with results reported in previous works. Mb means memory bank. # | architecture |  lossabc | image$\rightarrow$text abc | text$\rightarrow$image |
---|---|---|---|---|---
R@$1$ | R@$5$ | R@$10$ | Med r | Mean r | R@$1$ | R@$5$ | R@$10$ | Med r | Mean r | rsum
2.1 |  GRU+VGG19 | Sum | 46.9 | 79.7 | 89.5 | 2.0 | 5.9 | 37.0 | 73.1 | 85.3 | 2.0 | 11.1 | 411.5
2.2 | Max | 51.8 | 82.1 | 90.5 | 1.0 | 5.1 | 39.0 | 73.9 | 84.7 | 2.0 | 12.0 | 421.9
2.3 | Hal | 55.5 | 84.3 | 92.3 | 1.0 | 4.2 | 41.9 | 75.6 | 86.7 | 2.0 | 7.8 | 436.1
2.4 |  Hal+Mb | 56.7 | 84.9 | 93.0 | 1.0 | 4.0 | 41.9 | 75.9 | 87.1 | 2.0 | 7.2 | 439.5
2.5 |  GRU+IRv2 | Sum | 50.9 | 82.7 | 92.2 | 1.4 | 4.1 | 39.5 | 75.8 | 87.2 | 2.0 | 9.4 | 428.3
2.6 | Max | 57.0 | 86.2 | 93.8 | 1.0 | 3.5 | 43.3 | 77.9 | 87.9 | 2.0 | 8.6 | 446.0
2.7 | Hal | 60.2 | 87.3 | 94.4 | 1.0 | 3.3 | 44.8 | 78.2 | 88.3 | 2.0 | 7.7 | 453.2
2.8 |  Hal+Mb | 62.7 | 88.0 | 94.6 | 1.0 | 3.1 | 45.3 | 78.8 | 89.0 | 2.0 | 6.3 | 458.5
2.9 |  GRU+ResNet152 | Sum | 53.2 | 85.0 | 93.0 | 1.0 | 3.9 | 41.9 | 77.2 | 88.0 | 2.0 | 8.7 | 438.3
2.10 | Max | 58.7 | 88.2 | 94.8 | 1.0 | 3.2 | 45.0 | 78.9 | 88.6 | 2.0 | 8.6 | 454.2
2.11 | Hal | 64.4 | 89.2 | 94.9 | 1.0 | 3.0 | 46.3 | 78.8 | 88.3 | 2.0 | 7.9 | 462.0
2.12 |  Hal+Mb | 64.0 | 89.9 | 95.7 | 1.0 | 2.8 | 46.9 | 80.4 | 89.9 | 2.0 | 6.1 | 466.7
2.13 | (?) (ours) | 49.9 | 79.4 | 90.1 | 2.0 | 5.2 | 37.3 | 74.3 | 85.9 | 2.0 | 10.8 | 416.8
2.14 | (?) | 46.7 | - | 88.9 | 2.0 | 5.7 | 37.9 | - | 85.9 | 2.0 | 8.1 | -
2.15 | (?) | 53.2 | 83.1 | 91.5 | 1.0 | - | 40.7 | 75.8 | 87.4 | 2.0 | - | 431.8
2.16 | (?) | 56.4 | 85.3 | 91.5 | - | - | 43.9 | 78.1 | 88.6 | - | - | 443.8
2.17 | (?) | 56.3 | 84.4 | 92.2 | 1.0 | - | 45.7 | 81.2 | 90.6 | 2.0 | - | 450.4
2.18 | (?) (d=1024) | 57.8 | 87.9 | 95.6 | 1.0 | 3.3 | 44.2 | 80.4 | 90.7 | 2.0 | 5.4 | 456.6
2.19 | (?) | 58.3 | 86.1 | 93.3 | 1.0 | - | 43.6 | 77.6 | 87.8 | 2.0 | - | 446.7
2.20 | (?) (ours) | 60.5 | 89.6 | 94.9 | 1.0 | 3.1 | 46.1 | 79.5 | 88.7 | 2.0 | 8.5 | 459.3
2.21 | (?) | 58.3 | 89.2 | 95.4 | 1.0 | 3.1 | 45.0 | 80.4 | 89.6 | 2.0 | 7.2 | 457.9
2.22 | (?) | 64.3 | 89.2 | 94.8 | 1.0 | - | 48.3 | 81.7 | 91.2 | 2.0 | - | 469.5
2.23 | GRU+ResNet152 + Hal |  | 65.4 | 90.4 | 96.4 | 1.0 | 2.5 | 47.4 | 80.6 | 89.0 | 2.0 | 7.3 | 469.2
2.24 | GRU+ResNet152 + Hal \+ Mb |  | 66.3 | 91.7 | 97.0 | 1.0 | 2.4 | 48.7 | 82.1 | 90.8 | 2.0 | 5.6 | 476.6
2.25 | (?) (t-i AVG) | 70.9 | 94.5 | 97.8 | - | - | 56.4 | 87.0 | 93.9 | - | - | 500.5
2.26 | (?) (t-i AVG) + Hal | 78.3 | 96.3 | 98.5 | 1.0 | 2.6 | 60.1 | 86.7 | 92.8 | 1.0 | 5.8 | 512.7

Comparing Hal, Sum and Max. Table 1 and 2 present our quantitative results on
Flickr30k and MS-COCO respectively. On Flickr30k, we experiment three models
and Hal achieves significantly better performance than Max and Sum on the
first two configurations.333We do not include Hal+Mb for (?) as it demands GPU
memory exceeding 11GB, which is the limit of our used GTX 2080Ti. Same reason
applies to SCAN+Hal+Mb. On MS-COCO, Hal also beats both triplet loss
functions. Interestingly, while Max fails badly on Flickr30k, it becomes very
competitive on MS-COCO. This serves as an evidence of Max easily overfitting
to small datasets.444(?) showed that data augmentation techniques like random
crop applied on input images can improve Max’s performance over small
datasets. In conclusion, Hal maintains its edge over Max and Sum across
regardless of data and architecture configurations. Even without global
weighting (memory bank), Hal still beats the two triplet losses by a large
margin. The equipment of memory bank can usually further boosts rsum by
another $3-5$. Also, it is worth noticing that Hal converges significantly
faster than Max and Sum. Hal stabilizes after approximately $5$ epochs while
Max and Sum take roughly $10$ epochs.

Figure 2: Plotting epoch against rsum on validation set for comparing
convergence time. All models are using GRU+ResNet152, trained & validated on
MS-COCO.

Hal vs. State-of-the-art. Table 2 line 2.13-2.24 list quantitative results of
both our proposed method (2.23, 2.24) and numbers reported in previous works
(2.13-2.22). For fair comparison with (?), we only use routine encoder
architectures (GRU+ResNet152). Unlike (?; ?), we also do not bring in any
extra information to help training. With a trivial configuration of model &
data, our method is still ahead of the state-of-the-art on MS-COCO (?) by a
decent margin for most metrics. Notice that we are comparing against works
that use frozen image encoder (as we do). For the ones that finetuning image
features, better performance is achievable (?; ?). In Table 2 line 2.25, 2.26,
we list SCAN (?) alone as it incorporates additional knowledge, i.e. bottom-up
attention information, from a Faster R-CNN (?) to refine the visual-semantic
alignment. With such prior, it is a well-established state-of-the-art on the
Text-Image matching task, having much higher rsums than previous works. For
SCAN, we pick configurations with the best rsums on both MS-COCO and Flikr30k,
switching its learning objective from Max to Hal.555An ensemble model is able
to achieve even higher rsum but for clear comparison we do not discuss the
ensemble case. On Flikr30k, Max and Hal deliver comparable results. On MS-
COCO, Hal is significantly stronger - rsum is further improved to 512.7 with
R@$1$ improved by 7.4 and 3.7 for image$\rightarrow$text and
text$\rightarrow$image respectively. We did not experiment with Mb due to GPU
memory limits.

The impact of batch size. In contrast to loss functions that treat each sample
equivalently, batch size does matter to Hal as it defines the neighborhood
size where relative similarity is considered during local weighting. And Hal
does benefit from a larger batch size as it means an expanded neighborhood. As
suggested in Figure 3, on MS-COCO, Hal reaches a maximum rsum with a batch
size of $512$. Note that in the NCA context, batch size is a relative concept.
For Flickr30k, which is only of roughly $\frac{1}{4}$ the size of MS-COCO, we
maintain the original batch size of $128$ to cover roughly the same range of
neighborhood.

Figure 3: Plotting batch size used by Hal against rsum. All models are using
GRU+ResNet152, trained & tested on MS-COCO $c2$.

The impact of size of memory bank. The Mb in Hal has two hyperparameters: 1)
$k$, which characterizes the scope of neighborhood being considered for global
statistics, and 2) memory bank’s size. Their relative scales matter for mining
informative samples in the top-k neighborhood. When $k$ is fixed, we search
the most appropriate memory bank size and find that $5\%$ of training data is
ideal as suggested in Figure 4. The top-k neighborhood of a too large memory
bank might be filled with noisy samples (potentially being incorrectly
labeled).

Figure 4: Plotting rsum against Hal’s memory bank size. Hal without memory bank is also provided as a baseline. All data points are produced with GRU+IRv2 as the base model and are trained & tested on MS-COCO $c2$. Table 3: Experiment configurations.  # | Datasets | models | hyperparameters
---|---|---|---
3.1 | MS-COCO | 2.1, 2.5, 2.9, 2.13 | margin=0.2, lr=0.001, lr_update=10, bs=128, epoch=30
3.2 | 2.2, 2.6, 2.10, 2.20 | margin=0.2, lr=0.0002, lr_update=10, bs=128, epoch=30
3.3 | 2.11, 2.23 |  $\gamma$=30, $\epsilon$=0.3, lr=0.001, lr_update=10, bs=512, epoch=15
3.4 | 2.12, 2.24 |  $\gamma$=30, $\epsilon$=0.3, $\alpha$=40, $\beta$=40, $\epsilon_{1}$=0.2, $\epsilon_{2}$=0.1
lr=0.001, lr_update=10, bs=512, epoch=15
3.5 | 2.26 |  $\gamma$=100, $\epsilon$=1.0, lr=0.0005, lr_update=10, bs=256, epoch=20
3.6 |  Flickr30k | 1.1, 1.4 | margin=0.05, lr=0.001, lr_update=10, bs=128, epoch=30
3.7 | 1.2, 1.5 | margin=0.05, lr=0.0002, lr_update=15, bs=128, epoch=30
3.8 | 1.3 |  $\gamma$=60, $\epsilon$=0.7, lr=0.001, lr_update=10, bs=128, epoch=15
3.9 | 1.8 |  $\gamma$=70, $\epsilon$=0.6, lr=0.0005, lr_update=10, bs=128, epoch=30

## Related Work

In this section, we introduce works from three fields that are highly-related
to our work: 1) text-image matching and VSE; 2) deep metric learning; 3)
tackling the hubness problem in various contexts.

#### Text-image Matching and VSE.

Since the dawn of deep learning, works have emerged using a two-branch
architecture to connect language and vision. ? (?) trained a _shallow_ neural
network to map word-image pairs into a joint space for image annotation. In
2013, ? (?) brought up the term VSE and trained joint embeddings for sentence-
image pairs. Later works extended VSE for the task of text-image matching (?;
?; ?; ?; ?; ?; ?), which is also our task of interest. Notice that text-image
matching is different from generating novel captions for images (?; ?) but is
to retrieve existing descriptive texts or images in a database.

While many of these works improve model architectures for training VSE, few
have tackled the shortcomings in learning objectives. ? (?) made the latest
attempt to reform the long being used Sum loss. Their proposed Max loss is
indeed a much stronger baseline than Sum in most data and model
configurations. But it fails significantly when the dataset is small or noise
is contained. ? (?) eased such deficiency by relaxing Max into a top-K triplet
loss. ?; ? (?; ?) raised similar concerns. They mainly focused on creating
better training data while we target the training objective itself.

#### Deep Metric Learning.

Text-image matching is an open-set task where matching results are identified
based on similarity of pairs, instead of assigning probabilities to specific
labels in a closed set. Such property coincides with the idea of metric
learning, which utilizes relative similarities among pairs to cluster samples
of same class in embedding space. Entering the deep learning age, deep neural
net based metric learning is widely applied in various tasks including image
retrieval (?; ?), face recognition (?), person re-identification (?), etc.. We
use kindred philosophy in our context of matching two sets of data points.
Works on deep metric learning that inspired our model are discussed here.

Neighborhood Component Analysis (NCA) (?) introduced the foundational
philosophy for metric learning where a stochastic variant of K-Nearest-
Neighbor score is directly maximized. (?; ?; ?; ?) further developed the idea,
leveraging the gradient of NCA-based loss to discriminatively learn from
samples of different importance. (?) proposed a method that computes only part
of NCA-based loss’s gradient, so that NCA on a large scale is computationally
feasible.

#### Tackling the Hubness Problem.

We have stated what the hubness problem is in the introduction. Now we
introduce several efforts tackling the hubness problem in various contexts.
(?) pointed out the wide existence of hubs in text-image embeddings but did
not address them. Though not receiving enough attention in VSE literature,
hubness problem has recently been extensively explored in Bilingual Lexicon
Induction (BLI). BLI is the task of inducing word translations from
monolingual corpora in two languages (?). In terms of finding correspondence
between two sets of vectors, it is analogous to our task of interest. (?; ?)
proposed to first conduct a direct Procrustes Analysis and then use criteria
that heavily punish hubs during inference to reduce the hubness problem. While
it is indeed efficient in finding a better matching, the actual quality of
embedding is not improved. ? (?) integrated the inference criterion Csls from
(?) into a least-square loss and trained a transformation matrix end-to-end to
mitigate hubness problem. Though this work has a similar philosophy to ours,
it is specifically designed for BLI and only trains one linear layer over two
sets of word vectors. When Csls is appended to a triplet loss, it is merely a
resampling of hard samples, making it non-special in terms of both form and
intuition.

## Conclusion

We introduce a novel loss Hal for mitigating visual semantic hubs during
training text-image matching models. The self-adaptive loss Hal leverages the
inherit nature of Neighborhood Component Analysis (NCA) to identify
information of hubs, from both a global and local perspective, giving
considerations to robustness and hard sample mining at the same time. Our
method beats two prevalent triplet-based objectives across different datasets
and model architectures by large margins. Though our methods have only
experimented on the task of text-image matching, there remains to be other
cross-modal mapping tasks requiring obtaining a matching, e.g. content-based
image retrieval, document retrieval, document semantic relevance, Bilingual
Lexicon Induction, etc.. Hal can presumably be used in such settings as well.

## Acknowledgments

We thank anonymous reviewers for their careful feedbacks, based on which we
were able to enhance the work. We thank our family members for unconditionally
supporting our independent research. The author Fangyu Liu gives special
thanks to 1) Prof. Lili Mou, who voluntarily spent time reading and discussing
the rough ideas with him at the very beginning; 2) his aunt Qiu Wang who
supplied him with GPU machines; 3) his labmates Yi Zhu and Qianchu Liu from
Language Technology Lab for proofreading the camera-ready version.

## References

  * [Bellman 1961] Bellman, R.  1961\.  Adaptive control processes: a guided tour princeton university press.  Princeton, New Jersey, USA.
  * [Chung et al. 2014] Chung, J.; Gulcehre, C.; Cho, K.; and Bengio, Y.  2014\.  Empirical evaluation of gated recurrent neural networks on sequence modeling.  arXiv preprint arXiv:1412.3555.
  * [Deng et al. 2009] Deng, J.; Dong, W.; Socher, R.; Li, L.-J.; Li, K.; and Fei-Fei, L.  2009\.  Imagenet: A large-scale hierarchical image database.  In Proceedings of the IEEE conference on computer vision and pattern recognition (CVPR), 248–255.  IEEE.
  * [Dinu, Lazaridou, and Baroni 2015] Dinu, G.; Lazaridou, A.; and Baroni, M.  2015\.  Improving zero-shot learning by mitigating the hubness problem.  ICLR worshop.
  * [Faghri et al. 2018] Faghri, F.; Fleet, D. J.; Kiros, J. R.; and Fidler, S.  2018\.  Vse++: Improving visual-semantic embeddings with hard negatives.
  * [Faruqui et al. 2016] Faruqui, M.; Tsvetkov, Y.; Rastogi, P.; and Dyer, C.  2016\.  Problems with evaluation of word embeddings using word similarity tasks.  In Proceedings of the 1st Workshop on Evaluating Vector-Space Representations for NLP, 30–35.
  * [Frome et al. 2013] Frome, A.; Corrado, G. S.; Shlens, J.; Bengio, S.; Dean, J.; and Mikolov, T.  2013\.  Devise: A deep visual-semantic embedding model.  In NIPS, 2121–2129.
  * [Glorot and Bengio 2010] Glorot, X., and Bengio, Y.  2010\.  Understanding the difficulty of training deep feedforward neural networks.  In Proceedings of the thirteenth international conference on artificial intelligence and statistics, 249–256.
  * [Goldberger et al. 2005] Goldberger, J.; Hinton, G. E.; Roweis, S. T.; and Salakhutdinov, R. R.  2005\.  Neighbourhood components analysis.  In Advances in neural information processing systems, 513–520.
  * [Gong et al. 2014] Gong, Y.; Wang, L.; Hodosh, M.; Hockenmaier, J.; and Lazebnik, S.  2014\.  Improving image-sentence embeddings using large weakly annotated photo collections.  In European Conference on Computer Vision (ECCV), 529–545.  Springer.
  * [He et al. 2016] He, K.; Zhang, X.; Ren, S.; and Sun, J.  2016\.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, 770–778.
  * [Hodosh, Young, and Hockenmaier 2013] Hodosh, M.; Young, P.; and Hockenmaier, J.  2013\.  Framing image description as a ranking task: Data, models and evaluation metrics.  Journal of Artificial Intelligence Research 47:853–899.
  * [Huang, Wang, and Wang 2017] Huang, Y.; Wang, W.; and Wang, L.  2017\.  Instance-aware image and sentence matching with selective multimodal lstm.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2310–2318.
  * [Hubert Tsai, Huang, and Salakhutdinov 2017] Hubert Tsai, Y.-H.; Huang, L.-K.; and Salakhutdinov, R.  2017\.  Learning robust visual-semantic embeddings.  In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 3571–3580.
  * [Irvine and Callison-Burch 2017] Irvine, A., and Callison-Burch, C.  2017\.  A comprehensive analysis of bilingual lexicon induction.  Computational Linguistics 43(2):273–310.
  * [Jegou et al. 2008] Jegou, H.; Schmid, C.; Harzallah, H.; and Verbeek, J.  2008\.  Accurate image search using the contextual dissimilarity measure.  IEEE Transactions on Pattern Analysis and Machine Intelligence 32(1):2–11.
  * [Joulin et al. 2018] Joulin, A.; Bojanowski, P.; Mikolov, T.; and Grave, E.  2018\.  Loss in translation: Learning bilingual word mapping with a retrieval criterion.  EMNLP (short paper).
  * [Karpathy and Fei-Fei 2015] Karpathy, A., and Fei-Fei, L.  2015\.  Deep visual-semantic alignments for generating image descriptions.  In Proceedings of the IEEE conference on computer vision and pattern recognition, 3128–3137.
  * [Kiros, Salakhutdinov, and Zemel 2015] Kiros, R.; Salakhutdinov, R.; and Zemel, R. S.  2015\.  Unifying visual-semantic embeddings with multimodal neural language models.  Transactions of the Association for Computational Linguistics (TACL).
  * [Lample et al. 2018] Lample, G.; Conneau, A.; Ranzato, M.; Denoyer, L.; and Jégou, H.  2018\.  Word translation without parallel data.  In International Conference on Learning Representations.
  * [Lazaridou, Dinu, and Baroni 2015] Lazaridou, A.; Dinu, G.; and Baroni, M.  2015\.  Hubness and pollution: Delving into cross-space mapping for zero-shot learning.  In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), volume 1, 270–280.
  * [Lebret, Pinheiro, and Collobert 2015] Lebret, R.; Pinheiro, P. O.; and Collobert, R.  2015\.  Phrase-based image captioning.  In Proceedings of the 32nd International Conference on International Conference on Machine Learning-Volume 37 (ICML), 2085–2094.  JMLR. org.
  * [Lee et al. 2018] Lee, K.-H.; Chen, X.; Hua, G.; Hu, H.; and He, X.  2018\.  Stacked cross attention for image-text matching.  In Proceedings of the European Conference on Computer Vision (ECCV), 201–216.
  * [Lin et al. 2014] Lin, T.-Y.; Maire, M.; Belongie, S.; Hays, J.; Perona, P.; Ramanan, D.; Dollár, P.; and Zitnick, L.  2014\.  Microsoft coco: Common objects in context.  In European conference on computer vision (ECCV), 740–755.  Springer.
  * [Liu and Ye 2019] Liu, F., and Ye, R.  2019\.  A strong and robust baseline for text-image matching.  In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics: Student Research Workshop, 169–176.  Florence, Italy: Association for Computational Linguistics.
  * [Liu et al. 2017] Liu, Y.; Guo, Y.; Bakker, E. M.; and Lew, M. S.  2017\.  Learning a recurrent residual fusion network for multimodal matching.  In Proceedings of the IEEE International Conference on Computer Vision, 4107–4116.
  * [Oh Song et al. 2016] Oh Song, H.; Xiang, Y.; Jegelka, S.; and Savarese, S.  2016\.  Deep metric learning via lifted structured feature embedding.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 4004–4012.
  * [Radovanović, Nanopoulos, and Ivanović 2010] Radovanović, M.; Nanopoulos, A.; and Ivanović, M.  2010\.  Hubs in space: Popular nearest neighbors in high-dimensional data.  Journal of Machine Learning Research 11(Sep):2487–2531.
  * [Ren et al. 2015] Ren, S.; He, K.; Girshick, R.; and Sun, J.  2015\.  Faster r-cnn: Towards real-time object detection with region proposal networks.  In Advances in neural information processing systems, 91–99.
  * [Schnabel et al. 2015] Schnabel, T.; Labutov, I.; Mimno, D.; and Joachims, T.  2015\.  Evaluation methods for unsupervised word embeddings.  In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, 298–307.
  * [Schnitzer et al. 2012] Schnitzer, D.; Flexer, A.; Schedl, M.; and Widmer, G.  2012\.  Local and global scaling reduce hubs in space.  Journal of Machine Learning Research 13(Oct):2871–2902.
  * [Schroff, Kalenichenko, and Philbin 2015] Schroff, F.; Kalenichenko, D.; and Philbin, J.  2015\.  Facenet: A unified embedding for face recognition and clustering.  In Proceedings of the IEEE conference on computer vision and pattern recognition, 815–823.
  * [Shekhar et al. 2017] Shekhar, R.; Pezzelle, S.; Klimovich, Y.; Herbelot, A.; Nabi, M.; Sangineto, E.; and Bernardi, R.  2017\.  Foil it! find one mismatch between image and language caption.  In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 255–265.
  * [Shi et al. 2018] Shi, H.; Mao, J.; Xiao, T.; Jiang, Y.; and Sun, J.  2018\.  Learning visually-grounded semantics from contrastive adversarial samples.  In Proceedings of the 27th International Conference on Computational Linguistics, 3715–3727.
  * [Shuster et al. 2019] Shuster, K.; Humeau, S.; Hu, H.; Bordes, A.; and Weston, J.  2019\.  Engaging image captioning via personality.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 12516–12526.
  * [Simonyan and Zisserman 2014] Simonyan, K., and Zisserman, A.  2014\.  Very deep convolutional networks for large-scale image recognition.  arXiv preprint arXiv:1409.1556.
  * [Smith et al. 2017] Smith, S. L.; Turban, D. H.; Hamblin, S.; and Hammerla, N. Y.  2017\.  Offline bilingual word vectors, orthogonal transformations and the inverted softmax.  ICLR.
  * [Sohn 2016] Sohn, K.  2016\.  Improved deep metric learning with multi-class n-pair loss objective.  In Advances in Neural Information Processing Systems, 1857–1865.
  * [Song and Soleymani 2019] Song, Y., and Soleymani, M.  2019\.  Polysemous visual-semantic embedding for cross-modal retrieval.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 1979–1988.
  * [Szegedy et al. 2017] Szegedy, C.; Ioffe, S.; Vanhoucke, V.; and Alemi, A. A.  2017\.  Inception-v4, inception-resnet and the impact of residual connections on learning.  In Thirty-First AAAI Conference on Artificial Intelligence.
  * [Tomašev et al. 2011] Tomašev, N.; Brehar, R.; Mladenić, D.; and Nedevschi, S.  2011\.  The influence of hubness on nearest-neighbor methods in object recognition.  In 2011 IEEE 7th International Conference on Intelligent Computer Communication and Processing, 367–374.  IEEE.
  * [Vendrov et al. 2016] Vendrov, I.; Kiros, R.; Fidler, S.; and Urtasun, R.  2016\.  Order-embeddings of images and language.  ICLR.
  * [Wang et al. 2016] Wang, K.; Yin, Q.; Wang, W.; Wu, S.; and Wang, L.  2016\.  A comprehensive survey on cross-modal retrieval.  arXiv preprint arXiv:1607.06215.
  * [Wang et al. 2019a] Wang, L.; Li, Y.; Huang, J.; and Lazebnik, S.  2019a.  Learning two-branch neural networks for image-text matching tasks.  IEEE Transactions on Pattern Analysis and Machine Intelligence 41(2):394–407.
  * [Wang et al. 2019b] Wang, X.; Han, X.; Huang, W.; Dong, D.; and Scott, M. R.  2019b.  Multi-similarity loss with general pair weighting for deep metric learning.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 5022–5030.
  * [Wehrmann 2018] Wehrmann, Jônatas, B.-R. C.  2018\.  Bidirectional retrieval made simple.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 7718–7726.
  * [Weston, Bengio, and Usunier 2010] Weston, J.; Bengio, S.; and Usunier, N.  2010\.  Large scale image annotation: learning to rank with joint word-image embeddings.  Machine learning 81(1):21–35.
  * [Wu et al. 2017] Wu, C.-Y.; Manmatha, R.; Smola, A. J.; and Krähenbühl, P.  2017\.  Sampling matters in deep embedding learning.  In Proc. IEEE International Conference on Computer Vision (ICCV).
  * [Wu et al. 2019] Wu, H.; Mao, J.; Zhang, Y.; Jiang, Y.; Li, L.; Sun, W.; and Ma, W.-Y.  2019\.  Unified visual-semantic embeddings: Bridging vision and language with structured meaning representations.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 6609–6618.
  * [Wu, Efros, and Yu 2018] Wu, Z.; Efros, A. A.; and Yu, S. X.  2018\.  Improving generalization via scalable neighborhood component analysis.  In Proceedings of the European Conference on Computer Vision (ECCV), 685–701.
  * [Yi et al. 2014] Yi, D.; Lei, Z.; Liao, S.; and Li, S. Z.  2014\.  Deep metric learning for person re-identification.  In 2014 22nd International Conference on Pattern Recognition, 34–39.
  * [You, Zhang, and Luo 2018] You, Q.; Zhang, Z.; and Luo, J.  2018\.  End-to-end convolutional semantic embeddings.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 5735–5744.
  * [Young et al. 2014] Young, P.; Lai, A.; Hodosh, M.; and Hockenmaier, J.  2014\.  From image descriptions to visual denotations: New similarity metrics for semantic inference over event descriptions.  Transactions of the Association for Computational Linguistics 2:67–78.
  * [Yu et al. 2018] Yu, R.; Dou, Z.; Bai, S.; Zhang, Z.; Xu, Y.; and Bai, X.  2018\.  Hard-aware point-to-set deep metric for person re-identification.  In Proceedings of the European Conference on Computer Vision (ECCV), 188–204.
  * [Zhang, Xiang, and Gong 2017] Zhang, L.; Xiang, T.; and Gong, S.  2017\.  Learning a deep embedding model for zero-shot learning.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2021–2030.


# Multi-Objective Deep Reinforcement Learning for 5G Base Station Placement to
Support Localisation for Future Sustainable Traffic

Ahmed Al-Tahmeesschi  School of Physics Engineering and Technology, University
of York, United Kingdom  Jukka Talvitie  Unit of Electrical Engineering,
Tampere University, Tampere, Finland  Miguel López-Benítez  Dept. of
Electrical Engineering and Electronics, University of Liverpool, United
Kingdom  ARIES Research Centre, Antonio de Nebrija University, Spain  Hamed
Ahmadi  School of Physics Engineering and Technology, University of York,
United Kingdom  Laura Ruotsalainen  Dept. of Computer Science, University of
Helsinki, Helsinki, Finland

###### Abstract

Millimeter-wave (mmWave) is a key enabler for next-generation transportation
systems. However, in an urban city scenario, mmWave is highly susceptible to
blockages and shadowing. Therefore, base station (BS) placement is a crucial
task in the infrastructure design where coverage requirements need to be met
while simultaneously supporting localisation. This work assumes a pre-deployed
BS and another BS is required to be added to support both localisation
accuracy and coverage rate in an urban city scenario. To solve this complex
multi-objective optimisation problem, we utilise deep reinforcement learning
(DRL). Concretely, this work proposes: 1) a three-layered grid for state
representation as the input of the DRL, which enables it to adapt to the
changes in the wireless environment represented by changing the position of
the pre-deployed BS, and 2) the design of a suitable reward function for the
DRL agent to solve the multi-objective problem. Numerical analysis shows that
the proposed deep Q-network (DQN) model can learn/adapt from the complex radio
environment represented by the terrain map and provides the same/similar
solution to the exhaustive search, which is used as a benchmark. In addition,
we show that an exclusive optimisation of coverage rate does not result in
improved localisation accuracy, and thus there is a trade-off between the two
solutions.

###### Index Terms:

5G, deep Q-learning, deep reinforcement learning, multi-objective optimisation

##  I Introduction

At present, road transport contributes a significant amount to the total
carbon dioxide (CO2) emissions in the EU [1]. Thus, cities are looking for
practical strategies to make their transport systems more intelligent,
efficient and sustainable. One promising solution is in the form of connected
automated vehicles (AV). Next-generation transportation systems represented by
AVs will require Vehicle-to-Infrastructure (V2I) wireless connectivity [2].
Such connection should be able to satisfy the required high-data rates, low
latency and decimeter localisation accuracy [3].

5G networks have already adopted millimetre wave (mmWave) along with massive
multiple-input-multiple-output (MIMO) technologies to provide extremely high
data rates, low latency and localisation. However, due to unfavourable
propagation conditions at high frequencies, mmWave signals experience higher
path-loss and are more susceptible to building blockages than sub-6 GHz bands
in urban scenarios [4, 5]. Therefore, careful planning of the base station
(BS) locations is essential to reduce infrastructure costs while maintaining
the quality of service and localisation accuracy [6].

Reinforcement learning (RL) is a promising technique that can be employed to
address this problem. RL deals with sequential decision-making problems. The
goal of a sequential decision-making problem is to select actions to maximize
long-term rewards [7]. RL and the deep RL (DRL) variant have been used in the
literature to optimise various wireless communications systems, for example,
relay nodes selection [8] and dynamic spectrum access channel selection [9].
More details on RL application to wireless communications can be found in
[10]. In this work, we propose the utilisation of DRL to jointly optimise the
coverage rate and localisation accuracy.

The problem of BS location optimisation has already been addressed by several
studies [11, 12, 13] utilising genetic algorithms or computational geometry
combined with optimisation tools. In addition, DRL algorithms have been mainly
used for aerial BS placement to operate alone or to support terrestrial
network infrastructure to improve users coverage and throughput. For instance,
a single deep Q-network (DQN) agent is used to control either a single aerial
BS [14, 15] or multiple aerial BSs [16]. A multi-agent RL (MARL) approach is
utilised to control multiple aerial BSs [17]. In the aforementioned works, the
DRL has been mainly used for aerial BS location placement, while our work
considers street level base stations. In addition, our work assumes a pre-
deployed BS in the service region, and the proposed algorithm is capable to
adapt for changes in the pre-deployed BS location. The contributions of this
work are outlined as follows:

  1. 1.

We investigate the BS placement with the objective of jointly optimising the
coverage rate and localisation accuracy, particularly in the presence of a
pre-deployed BS. This addresses the challenge of achieving both coverage
requirements and accurate localisation in urban city scenarios using mmWave
technology.

  2. 2.

We propose a solution based on DQN to tackle the multi-objective problem. The
DQN framework incorporates a novel state representation approach, using a
three-layered grid, which enhances the adaptation to the dynamic radio
environment. Additionally, we design a suitable reward function to guide the
DQN agent towards finding solutions that balance between coverage rate and
localisation accuracy.

  3. 3.

We demonstrate the effectiveness the DQN framework in adapting to changes in
the radio environment, as represented by the repositioning of the pre-deployed
BS. The DQN model, utilising the proposed state representation approach,
showcases the capability to learn and adjust in complex radio environments.

##  II 5G new radio network model

In this section, the 5G radio network model is described. In order to generate
a realistic wireless simulation environment, the mmWave signals are generated
using a ray-tracing-based approach, as recommended by 3GPP [18]. Furthermore,
as our city model we select the Madrid grid, developed by the METIS project
[19], to represent a generic European city layout. The realizations of the
ray-tracing-based radio channel are evaluated by using Wireless
InSite®software [20]. A similar environment has been considered in the
literature [21, 22].

For this work, a specific segment of the Madrid grid is selected with BSs
operating at 28 GHz. The BSs height are set to 9 m and each BS includes 4
sectors, where each sector includes a uniform linear array with 32 half-
wavelength-separated patch antenna elements. The azimuth orientations of the
sectors are set to 45∘, 135∘, 225∘ and 315∘. The utilised beamforming
technique is implemented following the phased-array principle with a total of
64 beams per BS. The transmit power is set to 10 dBm. Fig. 1 shows the
considered Madrid grid segment along with the candidate BSs locations. In this
work, the received signal strengths (RSSs) are utilised for the estimation of
the area coverage rate and localisation accuracy. In practice, the RSS
measurements are obtained by the UE based on 3GPP-specified synchronisation
signal blocks (SSBs) transmitted by each BS over the 64 beams [23]. One of the
clear benefits of the considered approach is that the SSBs are continuously
available in all 5G NR networks as part of standard network operation, and
thus there is no need for dedicated positioning reference signals whose
availability can considerably vary in practical deployments. Moreover, RSS
measurements are preferred, as they are available in the user device during
both the connected mode and the idle mode as part of underlying mobility
management procedures.

Figure 1: Madrid grid segment with candidate BS locations.

##  III Problem formulation

Knowing the system setup, we present the BS placement strategy to jointly
optimise the localisation accuracy and the coverage rate. After that we also
discuss traditional exhaustive search algorithms.

###  III-A Optimisation problem

We have a multi-objective optimisation problem where we need to find the
optimal location of the BSs to minimise the average error in localisation and
maximise the coverage rate. The optimisation problem can be formulated as:

$\displaystyle\max\\{f_{1}(x,y)\\}\hskip 2.84526pt\land$ $\displaystyle\hskip
2.84526pt\min\\{f_{2}(x,y)\\}$ (1) s.t. $\displaystyle x\in X$ $\displaystyle
y\in Y$

where $X$ and $Y$ represent the sets of potential coordinates for the BS,
$f_{1}(x,y)$ is the average coverage rate (in percent) of the area and
$f_{2}(x,y)$ is the average localisation error (in meters). The average
coverage rate $f_{1}(x,y)$ is given as

$f_{1}(x,y)=\dfrac{1}{N}\sum_{n=1}^{N}{C_{n}},\vspace{-1mm}$ (2)

where $N$ is the number of positions to be covered and $C_{n}$ is the coverage
rate and is given as

$C_{n}=\begin{cases}1\text{ if RSS $\geq$ $\delta$,}\\\ 0\text{
otherwise}.\end{cases}\vspace{-1mm}$ (3)

where RSS is the received signal strength from one of the BS beams and
$\delta$ is the threshold for the minimum power required for a correct signal
reception. The average localisation error $f_{2}(x,y)$ is computed as

$f_{2}(x,y)=\dfrac{1}{N}\sum_{n=1}^{N}{z_{n}},\vspace{-1mm}$ (4)

where $z_{n}$ is the Euclidean distance between the estimated user equipment
(UE) horizontal plane position and the actual position and is given as

$z_{n}=\sqrt{({x_{n}^{ue}}-\hat{x}_{n}^{ue})^{2}+(y_{n}^{ue}-\hat{y}_{n}^{ue})^{2}},\vspace{-1mm}$
(5)

where $x_{n}^{ue}$ and $y_{n}^{ue}$ are the user x-coordinate and
y-coordinate, respectively. Moreover $\hat{x}_{n}^{ue}$ and $\hat{y}_{n}^{ue}$
are the estimated x-coordinate and y-coordinate of the user, respectively.

For the estimation of the user position, fingerprinting with the traditional
K-nearest neighbour algorithm (KNN) is considered as it is one of the most
utilised algorithms for RSS-based fingerprinting [24]. In KNN, the position of
the UE is estimated based on the mean of $K$ nearest neighbours locations. The
Euclidean distance is used to find the nearest neighbours from the accumulated
database. After a brief optimisation of localization performance, in this
work, we have defined $K=2$. For more details on the $K$ value estimation,
please refer to [22].

Figure 2: BS placement optimisation with DQN.

###  III-B Brute force algorithm (BF)

A brute force (BF) algorithm performs an exhaustive search through all the
possible solutions and selects the solution that provides the best answer for
the given optimisation problem. In this work, three different BF approaches
are considered as a reference:

  1. 1.

BF coverage (BFC), to maximise the coverage rate (i.e., max $f_{1}(x,y)$) for
the given area of interest.

  2. 2.

BF localisation (BFL), selects the solution that minimises the localisation
error (i.e., min $f_{2}(x,y)$) for the area of interest.

  3. 3.

BF joint (BFJ), selects the solution that maximises the coverage rate and
minimises localisation error for the area of interest. There are multiple ways
to address the general optimisation problem in (1). In this work, we chose to
maximise the ratio $f_{1}(x,y)/f_{2}(x,y)$ as both $f_{1}(x,y)$ and
$f_{2}(x,y)$ have different numerical ranges [25].

These BF approaches are considered in this work in order to provide a point of
reference to which the performance of the proposed DQN algorithm can be
compared. This is possible due to the discretisation of the space of candidate
BS locations.

##  IV Placement optimisation with DRL

In this section, we introduce the DRL model, which incorporates the proposed
state representations and reward signal shaping, aimed at optimising the BS
placement for the given multi-objective problem. This problem involves jointly
optimising the coverage rate and localisation accuracy, under the condition
that one BS has already been deployed. This represents a simplified and
tractable version of a scenario where some BSs may have already been deployed,
perhaps only bearing in mind the coverage rate, and new BSs are added to also
include the localisation accuracy as a relevant aspect in the infrastructure
design.

###  IV-A DRL Algorithm

In RL, the agent continuously learns according to the rewards or punishments
obtained from interacting with the environment. The agent aims to optimise the
location of BSs based on coverage area and localisation accuracy. At each time
step $t$, the agent observes the state $s_{t}$, executes an action $a_{t}$
following a policy $\pi$, then receives instant reward $r_{t}$, and transits
to the next state $s_{t+1}$, which together form a sequence
$(s_{t},a_{t},r_{t},s_{t+1})$ of Markov Decision Process (MDP) [7].

The goal of an MDP is to find the optimum policy that maximises the long term
discounted rewards, given by

$G_{t}=r_{t}+\gamma
r_{t+1}+\gamma^{2}r_{t+2}+\dots=\sum_{l=1}^{\infty}{\gamma^{l}r_{t+l}},\vspace{-1mm}$
(6)

where $\gamma\in[0,1)$ denotes the discount factor for weighting the future
rewards. If $\gamma$ is close to 0, the RL agent will focus on actions that
maximise the short-term rewards, whereas if $\gamma$ is close to 1, the agent
favours actions with long-term rewards. The policy $\pi$ is defined as the
mapping from states to actions. In Q-learning [7], the agent optimises the
policy to maximise the action-value function $Q$, which is the expectation of
the rewards $G_{t}$ at the current state $s_{t}$ and action $a_{t}$ under
policy $\pi$ and can be described as

$Q(s,a|\pi)=E_{\pi}[G_{t}|s_{t}=s,a_{t}=a].\vspace{-1mm}$ (7)

However, traditional RL can only work with problems that have a limited number
of states and actions, which is not applicable in our case. Therefore, deep
neural network is used as an approximator to the $Q$ function. In addition, we
apply experience replay which samples the data offline, prevents catastrophic
forgetting and utilises the target network. At the start of training, the
target network is identical to the Q-network. As training progresses, the
target network’s parameters are updated less frequently than those of the
Q-network. This approach is adopted to provide stability to the learning
process [26].

The DQN is trained to minimise the loss function given as

$L(\theta)=\mathbb{E}[(y_{t}-Q(s_{t},a_{t};\theta))^{2}],\vspace{-1mm}$ (8)

where $\theta$ is a vector and represents the DQN weights that determines the
policy $\pi$. The target function $y_{t}$ is given as

$y_{t}=r_{t}+\gamma\underset{a}{\text{max}}\
Q(s_{t+1},a_{t};\theta_{\text{target}}),\vspace{-1mm}$ (9)

where $\theta_{\text{target}}$ is the target network weights and is copied
from $\theta$ every fixed number steps.

###  IV-B DRL Agent and actions space

In the proposed DRL algorithm, the agent is the BS (we will refer to the agent
BS as ABS) who is trying to find the best deployment position to improve both
localisation accuracy and coverage rate given that a BS has already been
deployed. The agent’s actions controls the location of the ABS. Therefore, we
have 5 actions taken from discrete space $A=\\{up,down,left,right,stay\\}$,
which represents moving the current ABS location to one of the directions (in
the 2D domain) or to keep the ABS in the same position.

###  IV-C Proposed state representation

A typical approach for the DRL state is to have the coordinates of the pre-
deployed BS and ABS as the input state. However, such approach is not suitable
as it cannot adapt to changes in the starting location of the pre-deployed BS
and a new training should be performed to incorporate the change in the
wireless environment. Therefore, we aim to have a single algorithm that is
capable to adapt for the changes in the location of the pre-deployed BS and
capturing the signal propagation characteristics due to building shadowing. In
the context of our work, we propose the state to be represented as a three-
layered grid. The first layer represents the location of buildings. The second
layer represents the location of pre-deployed BS and the third layer
represents the location of the ABS. Thus, for the considered Madrid grid
segment, the states are represented by a 3$\times$19$\times$24 tensor (i.e.,
composed of 3 layers of a 19$\times$24 grid). The grid resolution could be
varied depending on the separation between the BS candidate positions, in our
case 19$\times$24 is a good trade-off between complexity and performance. Each
grid layer represents the position of each individual object and defined as

  * •

Building layer: 1 for buildings, 0 otherwise.

  * •

Static BS layer: 1 for already deployed BSs, 0 otherwise.

  * •

Agent BS layer: 1 for agent BS, 0 otherwise.

Algorithm 1 summarises the states extraction process.

Input: Pre-deployed BS and ABS locations

Input: The Madrid grid city layout.

Output: Tensor 3 $\times$ x $\times$ y.

1

2Construct the 2D grid ($x\times y$)

3

4Construct the Building layer: give 1 for buildings, 0 otherwise.

5

6Construct the Pre-deployed BS layer: give 1 for already deployed BSs, 0
otherwise.

7

8Construct the Agent BS layer: give 1 for agent BS, 0 otherwise.

9

Algorithm 1 Obtaining the states from city layout

###  IV-D Reward signal shaping

In our scenario, where the objective is to maximise the coverage rate and
minimise the localisation error, it is important that the reward $r_{t}$ at
each time step $t$ reflects the joint optimisation problem. To achieve this,
we have chosen to maximise the ratio $f_{1}(x,y)/f_{2}(x,y)$. Therefore, our
reward function $r_{t}$ is a scalar and is given as

$\vspace{-1mm}r_{t}=\dfrac{f_{1}(x,y)}{f_{2}(x,y)}+p,\vspace{-1mm}$ (10)

where $f_{1}(x,y)$ represents the coverage area percentage obtained from (2)
and $f_{2}(x,y)$ represents the localisation error obtained from (4). The term
$p$ corresponds to a penalty to discourage illegal actions taken by the agent,
such as colliding with a building or moving outside the simulation
environment. To reduce the reward when an illegal action is chosen we set
$p$=-0.1, and define $p$=0 otherwise.

###  IV-E Proposed DQN training and application

The training for the proposed DQN algorithm for the ABS placement is given by
Algorithm 2. The algorithm starts by initialising the parameters (Lines
1$\sim$3), followed by $M$ episodes. Each episode includes $T$ steps and
starts with resetting the states (Line 5). For the actions selection (Lines 7
and 8), we utilise the $\epsilon$-greedy approach to balance exploration and
exploitation from previous experience. After an action $a_{t}$ is performed a
reward $r_{t}$ is received and transit to a new state $s_{t+1}$. The
transition tuple $\\{s_{t},a_{t},r_{t},s_{t+1}\\}$ is stored in experience
replay memory $D$, which stores experiences in a first-in-first-out manner
(Line 10). Once $D$ is larger than the mini-batch size, the network training
starts (Lines 11$\sim$15). Random transition tuples of mini-batch size are
sampled from $D$ to train the DQN from past experiences. The target network is
used to estimate the target value $y_{t}$ (Line 13), which is used to evaluate
the actions selected by the main Q-network. The loss function is found from
(8), which is used to update the main Q-network parameters $\theta$ (Line 14).
The target network parameters $\theta_{target}$ are updated every fixed number
$\tau$ of training steps (Line 15).

Once the training is finished, the proposed DQN learns the placement of the
ABS. During application, the trained DQN observes the environment state
$s_{t}$ at each step and selects an action that maximises
$f_{1}(x,y)/f_{2}(x,y)$. This is repeated multiple times (50 in our case)
until the optimum ABS location is found.

Input: Tensor representation of the environment obtained form Algorithm 1

Output: Final ABS location.

1 Initialise the replay memory $D$ to a maximum capacity

2 Initialise Q-network with random weights $\theta$

3 Initialise target network with weights $\theta_{target}$ = $\theta$

4 for  _episode = 1, …, M_ do

5 Initialise the environment and receive initial state $s_{t}$

6

7 for  _step t = 1, …, T_ do

8 with probability $\epsilon$ select random action $a_{t}$

9 otherwise select $a_{t}=$ $\max_{a}Q(s_{t},a_{t};\theta)$

10 observe $r_{t}$ and new state $s_{t+1}$

11 store transition $\\{s_{t},a_{t},r_{t},s_{t+1}\\}$ in $D$

12 if  _memory is full_ then

13 sample mini-batch randomly of transitions $\\{s_{t},a_{t},r_{t},s_{t+1}\\}$
in $D$

14 set $y_{t}=\begin{cases}r_{t}&\text{$t=T$}\\\
r_{t}+\gamma\max_{a}Q(s_{t},a_{t};\theta)&$\text{$t$} <
\text{$T$}$\end{cases}$

15 update weights for $\theta$ of the main Q-network by minimising the loss
function ((8))

16 set $\theta_{target}$ = $\theta$ every $\tau$ steps

17

18

Algorithm 2 DRL-based solution for BS placement (training phase)

Figure 3: 2D visualization for the BS locations. 3 Case 1, 3 Case 2, 3 Case 3.
TABLE I: Coverage rate and localisation error (in meter).

| Pre-deployed
---
BS
BFC | BFL | BFJ |  | Traditional DQN
---
| Proposed DQN
---
Case |  | Cov rate
---
| Loc error
---
| Cov rate /
---
Loc error
| Cov rate
---
| Loc error
---
| Cov rate /
---
Loc error
| Cov rate
---
| Loc error
---
| Cov rate /
---
Loc error
| Cov rate
---
| Loc error
---
| Cov rate /
---
Loc error
| Cov rate
---
| Loc error
---
| Cov rate /
---
Loc error
1 | 0.98 | 2.45 | 0.40 | 0.90 | 1.46 | 0.61 | 0.90 | 1.46 | 0.61 | 0.88 | 2.19 | 0.40 | 0.92 | 1.73 | 0.53
2 | 0.95 | 3.37 | 0.28 | 0.86 | 1.97 | 0.43 | 0.87 | 1.97 | 0.44 | 0.90 | 3.21 | 0.28 | 0.87 | 1.97 | 0.44
3 | 0.98 | 2.17 | 0.45 | 0.95 | 1.71 | 0.55 | 0.95 | 1.71 | 0.55 | 0.95 | 2.35 | 0.40 | 0.98 | 1.87 | 0.52

##  V Performance analysis

###  V-A Evaluation scenario

In the DRL training stage, the DQN model is trained for 3000 episodes with 200
steps per episode. Adam optimiser with adaptive learning rate ($L_{r}$) was
used for the training with $L_{r}$=$10^{-3}$ for the first 500 episodes,
$L_{r}$=$10^{-4}$ for the following 500 episodes and $L_{r}$=$10^{-5}$ for the
rest of episodes. Reducing $L_{r}$ allows the optimiser to find the minimum in
the loss more efficiently [27]. Parameter $\gamma$ is set to 0.9, the mini-
batch size is set to 64, the memory buffer is set to 20000, the target network
update frequency $\tau$ is set to 50 and the Mean Squared Error loss function
is used. In our study, we compare two DQNs: our proposed version with a grid-
based state representation and the traditional version that uses a coordinate-
based state representation for both pre-deployed and new Base Stations (BS).
The traditional DQN model is structured with a Q-network that consists of two
hidden layers containing 50 and 25 neurons, respectively. These layers utilize
the ReLU activation function for the hidden layers and a Linear activation
function for the output layer. In contrast, our proposed DQN model integrates
two CNN layers on top of these hidden layers. The kernel size of these CNN
layers is $4\times 5$, and there is a $2\times 2$ max pooling layer following
the first CNN layer. Additionally, the starting location of our ABS is
randomly determined at the start of each training episode. To evaluate the
model’s effectiveness, 70% of the available pre-deployed BSs are used for
training, and the remaining 30% are utilized for testing. We set the threshold
for the received signal strength ($\delta$) to -80 dBm.

###  V-B Numerical results

The achieved localisation error and coverage rate are shown in Table I for the
considered algorithms (i.e., BFC, BFL, BFJ, traditional DQN and proposed DQN)
for three different pre-deployed BS scenarios. Fig. 3 shows a 2D visualization
of the BS placement for the different approaches. The BSs deployment scenarios
order in Table I matches what is shown in Fig. 3. As it can be appreciated
from Table I, BFC finds the best location to maximise the coverage rate, but
it has a significant impact on the localisation accuracy. Taking Case 2 as an
example, the BFC coverage rate is 95% while the localisation error is more
than 3.37 m. On the other hand, the smallest localisation error given by BFL
is 1.97 m at the expense of reducing the coverage rate to 86%.

The aim of the traditional and proposed DQN algorithm is to provide a solution
that is similar to the one obtained from BFJ. Therefore, we also investigate
the Cov rate/Loc error ratio. The three shown cases are taken from the test
data (locations of pre-deployed BS that are not used while training the DQN).
As it can be seen from Table I, the proposed DQN performance either matches
(Case 2) or provides a similar (Cases 1 and 3) coverage and localisation error
as BFJ. Therefore, the capability of the proposed DQN to adapt to the changes
in the location of the deployed BS is demonstrated, while the traditional DQN
approach fails to adapt. The reason why the results for the proposed DQN are
not identical to BFJ is as we only trained for 70$\%$ of the possible pre-
deployed BSs and the shown results come from the testing (i.e., not seen by
the model during training). Moreover, the proposed DQN model needs to be
trained only once while BFJ needs to be trained for each scenario. Note that
the coverage rate and localisation error achievable by the proposed DQN are
not higher than those of BFC and BFL, respectively, as they represent the
optimal solutions for coverage rate and localisation error when considered
independently. In contrast, the DQN aims for a solution that is jointly
optimized.

Finally, Fig. 4 shows the effect of selecting different ABS locations and its
effect on both localisation error and coverage rate. The pre-deployed BS
location is the same as shown in Fig. 33. The localisation error and coverage
rate have different optimal locations and the ABS location to optimise the
coverage rate is not the same for optimising the localisation error. In other
words, there is a trade-off between the two optimisation problems in BS
location selection that needs to be addressed through network planning,
depending on which parameter is more significant in each specific scenario.

Figure 4: Localisation error vs coverage rate.

##  VI Conclusions

This work has investigated the placement optimisation of mmWave BS in the
presence of a pre-deployed BS to simultaneously optimise the coverage rate and
localisation accuracy in an urban city layout. We presented a DRL algorithm
that is capable to solve the multi-objective problem and adapt to the changes
in the location of the pre-deployed BS by proposing a three-layered state
representation that is capable to capture spatial properties of the radio
environment. Numerical results have demonstrated that the proposed algorithm
provides similar results as the optimum exhaustive search algorithms. The
reason why the results for the proposed DQN are not identical to BFJ is as we
only trained for 70$\%$ of the possible pre-deployed BSs and the shown results
come from the testing. Nevertheless, the proposed DQN model needs to be
trained only once while BFJ needs to be trained for each scenario. In
addition, this work has demonstrated that there is a trade-off between
localisation accuracy and coverage rate. Future work will extend the current
work to a multi-agent scenario.

## Acknowledgment

This work was supported by the Academy of Finland Flagship program: Finnish
Center for Artificial Intelligence FCAI and the Academy of Finland project
347197 Artificial Intelligence for Urban Low-Emission Autonomous Traffic
(AIforLEssAuto).

## References

  * [1] A. Ajanovic, R. Haas, and F. Wirl, “Reducing CO2 emissions of cars in the EU: analyzing the underlying mechanisms of standards, registration taxes and fuel taxes,” _Energy Efficiency_ , vol. 9, 08 2016.
  * [2] P. Belanovic, D. Valerio, A. Paier, T. Zemen, F. Ricciato, and C. F. Mecklenbrauker, “On wireless links for vehicle-to-infrastructure communications,” _IEEE Transactions on Vehicular Technology_ , vol. 59, no. 1, pp. 269–282, 2010.
  * [3] 3GPP, _Service requirements for the 5G system_. 3rd Generation Partnership Project (3GPP), Technical Specifications (TS) 22.261, 12, version 18.1.0., 2016.
  * [4] S. Hur, T. Kim, D. J. Love, J. V. Krogmeier, T. A. Thomas, and A. Ghosh, “Millimeter wave beamforming for wireless backhaul and access in small cell networks,” _IEEE Transactions on Communications_ , vol. 61, no. 10, pp. 4391–4403, 2013.
  * [5] W. K. Alsaedi, H. Ahmadi, Z. Khan, and D. Grace, “Spectrum options and allocations for 6G: A regulatory and standardization review,” _IEEE Open Journal of the Communications Society_ , vol. 4, pp. 1787–1812, 2023.
  * [6] J. A. del Peral-Rosado, R. Raulefs, J. A. López-Salcedo, and G. Seco-Granados, “Survey of cellular mobile radio localization methods: From 1G to 5G,” _IEEE Communications Surveys Tutorials_ , vol. 20, no. 2, pp. 1124–1148, 2018.
  * [7] R. S. Sutton and A. G. Barto, _Reinforcement Learning: An Introduction_ , 2nd ed. The MIT Press, 2018. [Online]. Available: http://incompleteideas.net/book/the-book-2nd.html
  * [8] H. Kim, T. Fujii, and K. Umebayashi, “Relay nodes selection using reinforcement learning,” in _2021 International Conference on Artificial Intelligence in Information and Communication (ICAIIC)_ , 2021, pp. 329–334.
  * [9] S. S. Oyewobi, G. P. Hancke, A. M. Abu-Mahfouz, and A. J. Onumanyi, “An effective spectrum handoff based on reinforcement learning for target channel selection in the industrial internet of things,” _Sensors_ , vol. 19, no. 6, 2019.
  * [10] M. S. Frikha, S. M. Gammar, A. Lahmadi, and L. Andrey, “Reinforcement and deep reinforcement learning for wireless internet of things: A survey,” _Computer Communications_ , vol. 178, pp. 98–113, 2021.
  * [11] S. S. Szyszkowicz, A. Lou, and H. Yanikomeroglu, “Automated placement of individual millimeter-wave wall-mounted base stations for line-of-sight coverage of outdoor urban areas,” _IEEE Wireless Communications Letters_ , vol. 5, no. 3, pp. 316–319, 2016.
  * [12] I. Mavromatis, A. Tassi, R. J. Piechocki, and A. Nix, “Efficient millimeter-wave infrastructure placement for city-scale ITS,” in _2019 IEEE 89th Vehicular Technology Conference (VTC2019-Spring)_ , 2019, pp. 1–5.
  * [13] J. Zhang, Q. Wang, and H. Ahmadi, “An integrated access and backhaul approach to sustainable dense small cell network planning,” _Information_ , vol. 15, no. 1, 2024. [Online]. Available: https://www.mdpi.com/2078-2489/15/1/19
  * [14] J. Wu, P. Yu, L. Feng, F. Zhou, W. Li, and X. Qiu, “3D aerial base station position planning based on deep Q-network for capacity enhancement,” in _2019 IFIP/IEEE Symposium on Integrated Network and Service Management (IM)_ , 2019, pp. 482–487.
  * [15] G. B. Tarekegn, R.-T. Juang, H.-P. Lin, Y. Y. Munaye, L.-C. Wang, and M. A. Bitew, “Deep-reinforcement-learning-based drone base station deployment for wireless communication services,” _IEEE Internet of Things Journal_ , vol. 9, no. 21, pp. 21 899–21 915, 2022.
  * [16] S. P. Gopi and M. Magarini, “Reinforcement learning aided UAV base station location optimization for rate maximization,” _Electronics_ , vol. 10, no. 23, 2021.
  * [17] J. Qiu, J. Lyu, and L. Fu, “Placement optimization of aerial base stations with deep reinforcement learning,” in _ICC 2020 - 2020 IEEE International Conference on Communications (ICC)_ , 2020, pp. 1–6.
  * [18] 3GPP, “Study on channel model for frequencies from 0.5 to 100 GHz,” 3rd Generation Partnership Project (3GPP), Technical Specification (TS) TS 38.901, 01 2020, version 16.1.0. [Online]. Available: https://portal.3gpp.org/desktopmodules/Specifications/SpecificationDetails.aspx?specificationId=3173
  * [19] V. Nurmela _et al._ , “Deliverable D1.4: METIS channel models.” Proc. Mobile Wireless Commun. Enablers Twenty-Twenty Inf. Soc. (METIS), 2015, p. 1.
  * [20] Remcom. Wireless InSite - 3D wireless prediction software. Accessed: Jan 27, 2021). [Online]. Available: https://www.remcom.com/wireless-insite-em-propagation-software
  * [21] R. Klus, L. Klus, D. Solomitckii, J. Talvitie, and M. Valkama, “Deep learning-based cell-level and beam-level mobility management system,” _Sensors_ , vol. 20, no. 24, 2020. [Online]. Available: https://www.mdpi.com/1424-8220/20/24/7124
  * [22] A. Al-Tahmeesschi, J. Talvitie, M. López–Benítez, and L. Ruotsalainen, “Deep learning-based fingerprinting for outdoor UE positioning utilising spatially correlated RSSs of 5G networks,” in _2022 International Conference on Localization and GNSS (ICL-GNSS)_ , 2022, pp. 1–7.
  * [23] 3GPP, “NR; Physical layer measurements,” 3rd Generation Partnership Project (3GPP), Technical Specification (TS) 38.215, 07 2020, version 15.7.0. [Online]. Available: https://portal.3gpp.org/desktopmodules/Specifications/SpecificationDetails.aspx?specificationId=3217
  * [24] M. Y. Umair, K. V. Ramana, and Y. Dongkai, “An enhanced K-Nearest Neighbor algorithm for indoor positioning systems in a WLAN,” in _2014 IEEE Computers, Communications and IT Applications Conference_ , 2014, pp. 19–23.
  * [25] E. Björnson, E. A. Jorswieck, M. Debbah, and B. Ottersten, “Multiobjective signal processing optimization: The way to balance conflicting metrics in 5G systems,” _IEEE Signal Processing Magazine_ , vol. 31, no. 6, pp. 14–23, 2014.
  * [26] B. Brown and A. Zai, _Deep Reinforcement Learning in Action_. Manning Publications, 2020.
  * [27] K. He, R. Girshick, and P. Dollar, “Rethinking ImageNet pre-training,” in _2019 IEEE/CVF International Conference on Computer Vision (ICCV)_ , 2019, pp. 4917–4926.