42 233

# Hubness Reduction Improves Sentence-BERT Semantic Spaces

Beatrix M. G. Nielsen Corresponding Author. Technical University of Denmark
Lars Kai Hansen  Technical University of Denmark

###### Abstract

Semantic representations of text, i.e. representations of natural language
which capture meaning by geometry, are essential for areas such as information
retrieval and document grouping. High-dimensional trained dense vectors have
received much attention in recent years as such representations. We
investigate the structure of semantic spaces that arise from embeddings made
with Sentence-BERT and find that the representations suffer from a well-known
problem in high dimensions called hubness. Hubness results in asymmetric
neighborhood relations, such that some texts (the hubs) are neighbours of many
other texts while most texts (so-called anti-hubs), are neighbours of few or
no other texts. We quantify the semantic quality of the embeddings using
hubness scores and error rate of a neighbourhood based classifier. We find
that when hubness is high, we can reduce error rate and hubness using hubness
reduction methods. We identify a combination of two methods as resulting in
the best reduction. For example, on one of the tested pretrained models, this
combined method can reduce hubness by about 75% and error rate by about 9%.
Thus, we argue that mitigating hubness in the embedding space provides better
semantic representations of text.

###  1 Introduction

Large Language Models (LLMs) like BERT [1] have been shown to be effective for
information retrieval (e.g. [2], [3]) and using the siamese network
construction, the Sentence-BERT architecture [4] has made it possible to
create semantically meaningful text embeddings effectively enough to make
large-scale text clustering viable. Sentence-BERT can be viewed as a fine
tuning of a LLM to produce semantically relevant sentence embeddings. We
explore the geometry of the resulting embedding space using the neighbourhoods
of the data points.

For a typical Sentence-BERT setup, embeddings are of dimension $768$. In such
high dimensional data, so-called hubs tend to occur (e.g., [5], [6]). Hubs are
points which are among the $k$ nearest neighbours of many other points even
for small $k$. Antihubs, which are in the nearest neighbours of few or no
other points, also tend to appear in large numbers when the dimension is high
($\gtrsim$ 10). These hubs and antihubs skew the nearest neighbour relation,
since if a point, $x$, is in the ten nearest neighbours of a hundred other
points, most of those points cannot be in the ten nearest neighbours of $x$.
Therefore, if we use the neighbour relation to define semantic similarity, we
get the counter intuitive result, that some texts are semantically similar to
many other texts while many texts are not semantically similar to anything.
Hubness has been found in many different kinds of data and degrades
performance of neighbourhood based algorithms whether they are used for
classification [6], regression [7], clustering (e.g. [8], [9]) or outlier
detection [10]. Hubness has also been found to cause vulnerability in
recommender systems [11]. Naturally, there has been a quest in the cited
literature for means to mitigate the effect of hubness.

Figure 1: Error rate reduction for our models when using non-parametric
standardization of the histogram (f-norm), mutual proximity (MP) as introduced
by [12], and the combination of f-norm + MP. Note that the base error rate
varies for the models. This figure only shows the changes. If we only consider
models where base embeddings have a k-skewness of more than 3, f-norm + MP
reduces error rate in all cases. If we only consider embeddings where
k-skewness is more than 2.5, f-norm + MP reduces error rate in all except 3
cases. Datasets: 20 Newsgroups (20), AG News (AG), 10% of Yahoo Answers (YA).

In this paper, we consider differently trained Sentence-BERT models and
explore the effect on hubness scores and error rates of K-Nearest Neighbours
(knn) classification when using post hoc hubness reduction methods. The
overall picture is that the methods do reduce hubness and in most cases also
reduce error rate, i.e., increase neighbor semantic similarity. For example,
for a medium sized base model trained using cosine similarity and no
normalisation we get a reduction of mean error rate over 12 seeds between
$7\%$ and $13\%$ on the three used datasets. We also consider four pretrained
models, trained on more data than our own and show that for the 20 Newsgroups
data set, we can reduce hubness between $69\%$ and $83\%$ and reduce error
rates between $7\%$ and $9\%$, i.e. training on more data does not solve the
hubness problem.

Our main contributions are:

  * •

Empirical evidence that high hubness can occur in Sentence-BERT embeddings,
even when the model has been trained on large amounts of data.

  * •

A new use for a parameter free transformation of data (f-norm) as a hubness
reduction method. This method forces the dimensions of embeddings to follow a
standard normal distribution and has been used before by [13], but never to
our knowledge for hubness reduction.

  * •

Experimental results which show the benefits of three hubness reduction
methods f-norm, Mutual Proximity (MP) [12] and f-norm + MP and identify f-norm
+ MP as the best method for hubness and error rate reduction on three
datasets. See figure 1 for error rate reduction and figures 3, 4 for hubness
reduction.

Figure 2:  Using 10 neighbours. Data with dimensions a) standard normally
distributed (k-skewness: $-0.10$, $2.32$ and $11.62$, rh: $0.09$, $0.35$ and
$0.61$), b) standard normally distributed with embeddings normalized to unit
length (k-skewness: $0.05$, $0.27$ and $0.37$, rh: $0.08$, $0.11$ and $0.12$),
c) F distributed (k-skewness: $-0.12$, $1.78$ and $19.30$, rh: $0.10$, $0.28$
and $0.74$) and d) F distributed after using f-norm (k-skewness: $0.04$,
$0.34$ and $0.34$, rh: $0.9$, $0.11$ and $0.12$). b and d seem stable to high
dimension.

####  1.1 Related Work

In Radovanovic et al. [14] and [6], they described why hubs appear in high
dimensional data and illustrated the hubness problem on both synthetic and
real data. [15] reviewed hubness reduction methods for a large variety of
datasets. They concluded that e.g. local scaling [16] and mutual proximity
[12] formed state of the art in hubness reduction. Both [6] and [15] included
text datasets in their analyses. However, both works are based on very high
dimensional and sparse bag-of-word-representations. Hubness has also been
found in word embeddings e.g. [17]. [18] used hubness reduction to improve
performance in zero-shot translation and image labelling.

Recently, [19] introduced query bank normalisation to mitigate the hubness
problem when using cross modal embeddings to retrieve images. Z-score
normalisation has been used to reduce hubness of image embeddings [20] and
improve performance for few-shot learning. [21] used the average of the
context embeddings in the last layer of BERT as sentence embeddings, and
showed that when using cosine similarity, accuracy of semantic similarity on
text could be improved by transforming the distribution of the embeddings to a
smooth isotropic normal distribution using normalizing flows. This idea is
similar to our idea of making dimensions standard normally distributed,
however, our method does not require training. [22] consider the problem of
”rogue dimensions”, a few dimensions of an embedding which are far from the
origin, have high variance and dominate the cosine similarity, so that these
few dimensions decide whether two embeddings are similar or not, even though
they do not have much say in model decisions. See section 5 for further
relations to our work.

###  2 Hubness

Let $X=(x_{1},...,x_{m})\subset\mathbb{R}^{D}$ be $m$ points in
$D$-dimensional space. We define $N_{k}(x)$, called the $k$-occurrence, for a
point $x\in X$ as the number of times $x$ occurs in the $k$ nearest neighbours
of all points in $X$, for some distance measure. In this paper we will use
Euclidean distance. We will use the k-occurrence, $N_{k}(x)$, to measure the
hubness of our embedding spaces. However, for comparing several types of
embeddings it is more convenient with a single score, so we will use the
skewness of the $N_{k}(x)$ distribution ($k$-skewness) as proposed in [6] and
the robinhood score (rh) as proposed in [23]. The robinhood score, $H^{k}$, is
given by

$H^{k}=\frac{\sum_{x\in X}\lvert N_{k}(x)-k\rvert}{2k(m-1)}$ (1)

and measures how far the $k$-occurrences of the embeddings are from the
expected $k$. That is, it is a fraction between 0 and 1, which tells us how
large a part of nearest neighbours needs to be changed if all objects are to
be in the k nearest neighbours of the same number of points. We use the
scikit-hubness library by [24] to calculate these scores. In this paper, we
use $k=10$ for measuring $k$-skewness and robinhood score, since the exact
value is not important and $10$ is the value used in much of the literature we
reference.

Algorithm 1 f-norm

$X=\\{x_{i,d}\\}_{i\in\\{1,...,m\\},d\in\\{1,...,D\\}}$

for $d\in\\{1,...,D\\}$ do

$Z\leftarrow(z_{1},...,z_{m})\sim\mathcal{N}(0,1)$

$idxData\leftarrow\text{argsort}_{i\in\\{1,...,m\\}}(x_{i,d})$

$idxNormal\leftarrow\text{argsort}_{i\in\\{1,...,m\\}}(z_{i})$

for $idx_{1},idx_{2}\in(idxData,idxNormal)$ do

$x_{idx_{1},d}\leftarrow z_{idx_{2}}$

end for

end for

for $i\in\\{1,...,m\\}$ do

$x_{i}\leftarrow\frac{x_{i}}{\|x_{i}\|_{2}}$

end for

According to [6], in unimodal data distributions there is a strong correlation
between $N_{k}(x)$ and how close $x$ is to the global data mean. That is,
points close to the center of the data tend to become hubs. Therefore, we
expect hubness to be lower when all points have equal distance to the mean,
which will be the case if for example all points are on the surface of a
hypersphere (more in appendix B). Which means that if our data is standard
normally distributed in each dimension, and we then normalise to unit length,
we should get lower hubness. In figure 2a) and b) we see that this is indeed
the case. In LLM derived embeddings we do not expect the individual dimensions
to be distributed according to the same normal distribution, however, we find
empirically that the distributions of the dimensions of sentence BERT
embeddings do look close to normal distributions (examples in Appendix figure
7). See more motivation in Appendix D. Thus, we explored the idea to force the
dimensions of the data points to follow a standard normal distribution, but
preserving the ranking of the values (we call this method ‘f-norm’, Algorithm
1). Note, when using this method the distribution of the dimensions before the
transformation no longer matters. See figure 2c) and d) for an example with F
distributed dimensions. See figure 3 and appendix figure 6 for how f-norm
affects some real data.

Figure 3: $K$-occurrence distribution (10 neighbours) for embeddings on 20
newsgroups (orange) compared to points coming from a standard normal
distribution in same number of dimensions (blue) with embeddings normalised to
unit length. Using our reduction methods, the $k$-occurrence of the embeddings
come closer to the stable distribution. Note MP still leaves some large hubs.
Embedding $k$-skewness: $8.79$, $2.20$, $20.98$, $0.42$, rh: $0.35$, $0.30$,
$0.20$, $0.16$. Model: distilroberta-base_euclidean_n_seed1.

####  2.1 Methods for hubness reduction of semantic spaces

Normalisations used during training aim to center the data and/or make it lie
on the unit sphere, see Appendix D. In our models we used: No normalisation
(’none’), normalisation of embeddings to unit length (’n’), centering of
embeddings (subtracting the mean value of the embedding from all dimensions in
the embedding) (’c’), a combination of centering and normalisation of
embeddings to unit length (’c,n’) and z-score normalisation of embeddings
(according to [20] this had an effect when doing few shot learning) (’z’).

After training and obtaining embeddings for a dataset using a model, we tested
three different post hoc methods for hubness reduction on the three datasets.

  * •

Forcing standard normal distribution in each dimension of embeddings and then
normalising embeddings to unit length (f-norm) as described in Algorithm 1.

  * •

Mutual proximity (MP) as introduced by [12].

  * •

First forcing a standard normal distribution in each dimension and normalising
embeddings, then using mutual proximity on the result (f-norm + MP).

On the 20 Newsgroups dataset, we tested two additional methods: f-uniform and
local scaling. The latter was introduced by [16] and proposed for hubness
reduction by [12]. More in Appendix C.

MP aims to make the nearest neighbour relation more symmetric by translating
the distance between points $d(x,y)$ to a probability $MP(d_{x,y})$ that $x$
is the nearest neighbour of $y$ and that $y$ is also a nearest neighbour of
$x$ in the following way: Let $p(d_{x})$ be the probability density function
of the probability distribution of distances from $x$ to all other points in
the dataset. Then use $p(d_{x})$ and $d(x,y)$ to find the probability of $y$
being the nearest neighbour of $x$. Then use $p(d_{y})$ and $d(x,y)$ to find
the probability of $x$ being the nearest neighbour of $y$. It is then these
probabilities which are used as the distance in the knn algorithm. [12] showed
that it is enough to calculate distances to a sample of other points. More in
Appendix P.

###  3 Evaluation

We trained Sentence-BERT models using three different base models, which were
not trained on the datasets we use for testing, (microsoft-
MiniLM-L12-H384-uncased111huggingface.co/MiniLM-L12-H384-uncased [25],
distilroberta-base222huggingface.co/distilroberta-base [26], microsoft-mpnet-
base333huggingface.co/microsoft/mpnet-base [27]) and three different distance
measures during training (cosine similarity (’cos’), cosine distance
(’cos_dist’), Euclidean distance (’euclidean’)). For each combination of
model, distance measure and normalisation method from 2.1, we trained with
twelve random seeds (model naming scheme is [base model]_[distance
measure]_[normalisation]_[seed]). This gave us $540$ models in all. On the
large datasets (AG News and Yahoo Answers), we only calculated embeddings and
results for models using the medium and large base models, that is
distilroberta-base and microsoft-mpnet-base, so on these datasets we have
results for $360$ models. We trained our models on the STS benchmark
dataset444sbert.net/datasets/stsbenchmark.tsv.gz for $4$ epochs. More in
Appendix J, K, L.

We also made embeddings using four pretrained Sentence-BERT models, which have
been trained on more data than our own. These models were: all-mpnet-
base-v2555huggingface.co/sentence-transformers/all-mpnet-base-v2, multi-qa-
distilbert-cos-v1666huggingface.co/sentence-transformers/multi-qa-distilbert-
cos-v1, all-distilroberta-v1777huggingface.co/sentence-transformers/all-
distilroberta-v1 and all-MiniLM-L12-v2888huggingface.co/sentence-
transformers/all-MiniLM-L12-v2. Note that all these pretrained models have
been trained on Yahoo Answers in various ways. More in Appendix I.

We used three text classification datasets: 20 Newsgroups, AG News (by Antonio
Gulli) and ten percent of the Yahoo Answers dataset [28]. Details in Appendix
A.

We classify using knn. To identify the number of neighbours to use in knn for
classification, we used stratified 10-fold validation on the training set. We
measured error rate on the test set. More details in Appendix M.

Let the train embeddings be an $m\times d$ matrix and the test embeddings be
an $l\times d$ matrix. When using f-norm at test time, we append the test
embeddings to the train embeddings matrix giving us an $(m+l)\times d$ matrix,
which we then use the algorithm on.

###  4 Results

Trained, models, embeddings and raw result files can be found at DTU
Data999https://doi.org/10.11583/DTU.c.6165561.v1. Code can be found on
GitHub101010https://github.com/bemigini/hubness-reduction-improves-sbert-
semantic-spaces. Overviews of training combinations and post hoc reduction
methods with error rate and hubness scores are in Appendix S. See this
material for results on f-uniform and local scaling. Summary of error rate
changes from the overview tables is in figure 1, summary of the changes in
hubness is in figure 4.

Figure 4: Reduction in hubness using f-norm, MP and f-norm + MP measured with
$k$-skewness ($k$-skew) and robinhood score (rh). Higher is better. Hubness is
reduced in almost all cases, however for MP on 20 Newsgroups hubness increases
as measured with $k$-skewness. Likely induced by the hubs remaining after MP,
see figure 3.

We see that the methods reduce hubness as measured with the robinhood score in
almost all cases (figure 4). However, when using MP, $k$-skewness went up in
all cases on 20 Newsgroups. Inspecting the $k$-occurrence distribution, this
seems to be because while MP makes the knn relation more symmetric for most
data points, there are still some rather large hubs which it does not change.
These hubs are sentences which are either empty or which only contain
whitespace characters. In 20 Newsgroups there are 268 sentences which are
either empty or whitespace. Before hubness reduction, 252 of them have a
$k$-occurrence of 0 and 10 have a $k$-occurrence of more than 100. After using
MP, 191 of them have a $k$-occurrence of 0 and 10 still have a $k$-occurrence
of more than 100. However, when using f-norm + MP there are no longer these
very large hubs (figure 3), in fact after f-norm + MP, all the empty or
whitespace sentences have k-occurrences between 4 and 17. Thus, these
sentences are no longer disconnected with respect to the neighbourhood
relation. Using f-norm + MP also decreases k-skewness in more cases than using
just f-norm.

Figure 5: knn error on 20 Newsgroups before vs after hubness reductions.
Average base $k$-skewness $6.06$. See 3

On all three datasets, when $k$-skewness is more than $3$, error rate is
reduced when using f-norm + MP (figure 1). See figure 5 for examples of
absolute error reduction. More examples in Appendix G. Embeddings on AG News
had lower base hubness and error rate than embeddings on the other two
datasets, however, since f-norm reduces error rate for all embeddings with
$k$-skewness more than 3, we think it likely that the low hubness makes it
difficult for the hubness reduction methods to improve classification
performance on this dataset. We also found that f-norm + MP is more likely to
have a larger effect on error rate, if the base skewness is higher (Appendix
Q). We hypothesize that when hubness is not high enough, the transformation of
the embeddings harms the learned structure of the embeddings more than it
helps.

The lowest mean error rates came from models using the largest base model.
However, using f-norm + MP can in some cases make up for the model size. For
example, distilroberta-base_cos_none base and microsoft-mpnet-base_cos_none
had base mean error of $10.9$% and $9.4$% on AG News. Using f-norm + MP
reduces the error to $8.8$% and $8.4$%. So the smaller model with f-norm + MP
is better than the bigger model without. More about the smallest error rates
in Appendix N.

We found that models which use some kind of embedding length normalisation (n;
c,n; z) tend to have slightly lower hubness measured with robinhood score than
models which do not have this kind of normalisation (none; c). More on
differences between normalisations during training in Appendix O. We found
that which distance measure is used during training is not a good predictor
for error rate or effectiveness of hubness reduction. On AG News, the ten best
mean error rates all came from models which used Euclidean distance for
training, however on 20 Newsgroups, models trained with Euclidean distance had
worse error rate than models trained with cosine similarity or cosine
distance.

Table 1:  Error rate (error) and k-skewness (skew) on 20 Newsgroups (20), AG News (AG) and ten percent of Yahoo Answers (YA) for four pretrained models, base case vs after hubness reduction. Note that all these models have been trained on YA in various ways and their hubness on YA is in general lower than the models we trained. Thus, it seems that training on a specific dataset can make hubness go down for that dataset. However, hubness is still high on 20 which the models have not been trained on. Model | 20 | AG | YA
---|---|---|---
|  | error | skew | error | skew | error | skew
multi-qa-distilbert-cos-v1 | base | 0.318 | 7.58 | 0.081 | 1.90 | 0.271 | 2.12
| f-norm + MP | 0.289 | 1.89 | 0.079 | 1.57 | 0.269 | 1.88
all-MiniLM-L12-v2 | base | 0.324 | 11.45 | 0.088 | 1.91 | 0.268 | 1.98
| f-norm + MP | 0.300 | 1.88 | 0.085 | 1.56 | 0.267 | 1.79
all-mpnet-base-v2 | base | 0.295 | 11.53 | 0.082 | 1.81 | 0.251 | 2.02
| f-norm + MP | 0.272 | 1.98 | 0.082 | 1.54 | 0.250 | 1.78
all-distilroberta-v1 | base | 0.322 | 6.61 | 0.085 | 1.93 | 0.254 | 2.08
| f-norm + MP | 0.296 | 2.05 | 0.085 | 1.59 | 0.253 | 1.82

####  4.1 Pretrained Models

All the tested pretrained models have a high base hubness as measured with
$k$-skewness on 20 Newsgroups (See Table 1). This means that training models
on more data will not necessarily result in low hubness. On the 20 Newsgroup
dataset, the error rate goes down (reduction between $7\%$ and $9\%$.) when
using f-norm + MP for all four models. These reductions are highly
significant, since using McNemar’s test gives p-values smaller than $2.1\cdot
10^{-9}$. However, error rate is not reduced for the other two datasets. We
interpret this as being due to the low base hubness of the pretrained models
on AG News and Yahoo Answers. AG News also had a low base hubness for most of
our own models, so we suppose this is due to the nature of the dataset. Our
own models had higher base hubness on Yahoo Answers than the pretrained
models, however all the pretrained models were also trained on Yahoo Answers
in various ways. Therefore, we assume that training on a specific dataset can
make hubness go down for that dataset. See Table 2 in Appendix I for more
details.

###  5 Discussion and Conclusion

Since f-norm also reduces the rogue dimensions problem [22], the reductions in
error might not be solely due to reduced hubness. However, in cases where MP
reduces error rate, we hypothesize that hubness reduction does contribute to
the error reduction.

We measured hubness with both $k$-skewness and the robinhood score. The
robinhood score is less sensitive to outliers, so it can detect when a method
reduces the overall hubness even though it leaves some outliers, while
$k$-skewness might grow in such cases. However, $k$-skewness is a better
predictor for whether hubness reduction methods using f-norm will have a
positive effect on the error rate. The robinhood score has a different
baseline scale for each dataset, hampering its interpretation.

We have only looked at how hubness reduction methods affect knn. Since we used
Euclidean distance in our knn, the error rates on our datasets tell us how
well the Euclidean distances between datapoints correspond to class structure.
Thus, when searching for other methods which might benefit from these hubness
reduction methods, we should look for models which use distances between the
datapoints for classification. Other clustering or classification techniques
might not be improved using these methods (Note on SVM in Appendix R). When
using f-norm for $m$ train embeddings and $l$ test embeddings of dimension
$d$, one will have to sort $(m+l)\cdot 2d$ numbers. However, for very large
training datasets, it should not be necessary to use all the training data. It
would be an interesting direction for further research to find out how many
and which training points to keep to get good performance.

In conclusion, when using neighbourhood based approaches and high dimensional
text embeddings, one should always check for hubness. For a broad set of
training choices, if there is high hubness in embeddings (k-skewness of more
than $3$ seems to be useful as a rule of thumb), then hubness reduction
techniques (especially f-norm + MP) will produce better text representations
as shown by more symmetric nearest neighbour relation and improved
classification.

### Acknowledgements

This work was supported by the Danish Pioneer Centre for AI, DNRF grant number
P1 and by the Novo Nordisk Foundation grant NNF22OC0076907 ”Cognitive spaces -
Next generation explainability”. Thanks to Mikkel N. Schmidt for helpful
comments on the abstract and introduction.

### References

  * [1] Jacob Devlin, Ming-Wei Chang, Kenton Lee and Kristina Toutanova  “BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding”  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ Minneapolis, Minnesota: Association for Computational Linguistics, 2019, pp. 4171–4186  DOI: 10.18653/v1/N19-1423
  * [2] Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen and Wen-tau Yih  “Dense Passage Retrieval for Open-Domain Question Answering”  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ Online: Association for Computational Linguistics, 2020, pp. 6769–6781  DOI: 10.18653/v1/2020.emnlp-main.550
  * [3] Zhuolin Jiang, Amro El-Jaroudi, William Hartmann, Damianos Karakos and Lingjun Zhao  “Cross-lingual Information Retrieval with BERT”  In _Proceedings of the workshop on Cross-Language Search and Summarization of Text and Speech (CLSSTS2020)_ Marseille, France: European Language Resources Association, 2020, pp. 26–31  URL: https://aclanthology.org/2020.clssts-1.5
  * [4] Nils Reimers and Iryna Gurevych  “Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks”  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ Hong Kong, China: Association for Computational Linguistics, 2019, pp. 3982–3992  DOI: 10.18653/v1/D19-1410
  * [5] Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan and Uri Shaft  “When Is “Nearest Neighbor” Meaningful?”  In _Database Theory — ICDT’99_ Berlin, Heidelberg: Springer Berlin Heidelberg, 1999, pp. 217–235  URL: https://www.researchgate.net/publication/2845566_When_Is_Nearest_Neighbor_Meaningful
  * [6] Milos Radovanovic, Alexandros Nanopoulos and Mirjana Ivanovic  “Hubs in space: Popular nearest neighbors in high-dimensional data”  In _Journal of Machine Learning Research_ 11.sept, 2010, pp. 2487–2531  URL: https://dl.acm.org/doi/10.5555/1756006.1953015
  * [7] Krisztian Buza, Alexandros Nanopoulos and Gábor Nagy  “Nearest neighbor regression in the presence of bad hubs”  In _Knowledge-Based Systems_ 86 Elsevier, 2015, pp. 250–260  DOI: https://doi.org/10.1016/j.knosys.2015.06.010
  * [8] Dominik Schnitzer and Arthur Flexer  “The unbalancing effect of hubs on k-medoids clustering in high-dimensional spaces”  In _2015 International Joint Conference on Neural Networks (IJCNN)_ , 2015, pp. 1–8  IEEE  DOI: 10.1109/IJCNN.2015.7280303
  * [9] Nenad Tomasev, Milos Radovanovic, Dunja Mladenic and Mirjana Ivanovic  “The role of hubness in clustering high-dimensional data”  In _IEEE transactions on knowledge and data engineering_ 26.3 IEEE, 2013, pp. 739–751  DOI: 10.1109/TKDE.2013.25
  * [10] Miloš Radovanović, Alexandros Nanopoulos and Mirjana Ivanović  “Reverse nearest neighbors in unsupervised distance-based outlier detection”  In _IEEE transactions on knowledge and data engineering_ 27.5 IEEE, 2014, pp. 1369–1382  DOI: 10.1109/TKDE.2014.2365790
  * [11] Kazuo Hara, Ikumi Suzuki, Kei Kobayashi and Kenji Fukumizu  “Reducing hubness: A cause of vulnerability in recommender systems”  In _Proceedings of the 38th international ACM SIGIR conference on research and development in information retrieval_ , 2015, pp. 815–818
  * [12] Dominik Schnitzer, Arthur Flexer, Markus Schedl and Gerhard Widmer  “Local and global scaling reduce hubs in space”  In _Journal of Machine Learning Research_ 13.10, 2012  URL: https://jmlr.csail.mit.edu/papers/volume13/schnitzer12a/schnitzer12a.pdf
  * [13] Trine Julie Abrahamsen and Lars Kai Hansen  “A Cure for Variance Inflation in High Dimensional Kernel Principal Component Analysis”  In _Journal of Machine Learning Research_ 12.6, 2011  URL: https://www.jmlr.org/papers/volume12/abrahamsen11a/abrahamsen11a.pdf
  * [14] Miloš Radovanović, Alexandros Nanopoulos and Mirjana Ivanović  “Nearest neighbors in high-dimensional data: The emergence and influence of hubs”  In _Proceedings of the 26th Annual International Conference on Machine Learning_ , 2009, pp. 865–872  DOI: https://doi.org/10.1145/1553374.1553485
  * [15] Roman Feldbauer and Arthur Flexer  “A comprehensive empirical comparison of hubness reduction in high-dimensional spaces”  In _Knowledge and Information Systems_ 59.1 Springer, 2019, pp. 137–166  DOI: https://doi.org/10.1007/s10115-018-1205-y
  * [16] Lihi Zelnik-Manor and Pietro Perona  “Self-tuning spectral clustering”  In _Advances in neural information processing systems_ 17, 2004  URL: https://proceedings.neurips.cc/paper/2004/file/40173ea48d9567f1f393b20c855bb40b-Paper.pdf
  * [17] Aitor Ormazabal, Mikel Artetxe, Gorka Labaka, Aitor Soroa and Eneko Agirre  “Analyzing the Limitations of Cross-lingual Word Embedding Mappings”  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ Florence, Italy: Association for Computational Linguistics, 2019, pp. 4990–4995  DOI: 10.18653/v1/P19-1492
  * [18] Angeliki Lazaridou, Georgiana Dinu and Marco Baroni  “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)_ Beijing, China: Association for Computational Linguistics, 2015, pp. 270–280  DOI: 10.3115/v1/P15-1027
  * [19] Simion-Vlad Bogolin, Ioana Croitoru, Hailin Jin, Yang Liu and Samuel Albanie  “Cross Modal Retrieval with Querybank Normalisation”  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 5194–5205  DOI: https://doi.org/10.48550/arXiv.2112.12777
  * [20] Nanyi Fei, Yizhao Gao, Zhiwu Lu and Tao Xiang  “Z-score normalization, hubness, and few-shot learning”  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 142–151  URL: https://openaccess.thecvf.com/content/ICCV2021/papers/Fei_Z-Score_Normalization_Hubness_and_Few-Shot_Learning_ICCV_2021_paper.pdf
  * [21] Bohan Li, Hao Zhou, Junxian He, Mingxuan Wang, Yiming Yang and Lei Li  “On the Sentence Embeddings from Pre-trained Language Models”  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ Online: Association for Computational Linguistics, 2020, pp. 9119–9130  DOI: 10.18653/v1/2020.emnlp-main.733
  * [22] William Timkey and Marten Schijndel  “All Bark and No Bite: Rogue Dimensions in Transformer Language Models Obscure Representational Quality”  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ OnlinePunta Cana, Dominican Republic: Association for Computational Linguistics, 2021, pp. 4527–4546  DOI: 10.18653/v1/2021.emnlp-main.372
  * [23] Roman Feldbauer, Maximilian Leodolter, Claudia Plant and Arthur Flexer  “Fast approximate hubness reduction for large high-dimensional data”  In _2018 IEEE International Conference on Big Knowledge (ICBK)_ , 2018, pp. 358–367  IEEE  DOI: 10.1109/ICBK.2018.00055
  * [24] Roman Feldbauer, Thomas Rattei and Arthur Flexer  “scikit-hubness: Hubness Reduction and Approximate Neighbor Search”  In _Journal of Open Source Software_ 5.45, 2020, pp. 1957  DOI: 10.21105/joss.01957
  * [25] Wenhui Wang, Furu Wei, Li Dong, Hangbo Bao, Nan Yang and Ming Zhou  “Minilm: Deep self-attention distillation for task-agnostic compression of pre-trained transformers”  In _Advances in Neural Information Processing Systems_ 33, 2020, pp. 5776–5788  DOI: https://doi.org/10.48550/arXiv.2002.10957
  * [26] Victor Sanh, Lysandre Debut, Julien Chaumond and Thomas Wolf  “DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter”  In _5th Workshop on Energy Efficient Machine Learning and Cognitive Computing @ NeurIPS 2019_ , 2019  DOI: https://doi.org/10.48550/arXiv.1910.01108
  * [27] Kaitao Song, Xu Tan, Tao Qin, Jianfeng Lu and Tie-Yan Liu  “Mpnet: Masked and permuted pre-training for language understanding”  In _Advances in Neural Information Processing Systems_ 33, 2020, pp. 16857–16867  URL: https://proceedings.neurips.cc/paper/2020/file/c3a690be93aa602ee2dc0ccab5b7b67e-Paper.pdf
  * [28] Xiang Zhang, Junbo Zhao and Yann LeCun  “Character-level convolutional networks for text classification”  In _Advances in neural information processing systems_ 28, 2015  DOI: https://doi.org/10.48550/arXiv.1509.01626
  * [29] Thomas Low, Christian Borgelt, Sebastian Stober and Andreas Nürnberger  “The hubness phenomenon: Fact or artifact?”  In _Towards Advanced Data Analysis by Combining Soft Computing and Statistics_ Springer, 2013, pp. 267–278  DOI: 10.1007/978-3-642-30278-7˙21
  * [30] Leonid Boytsov and Bilegsaikhan Naidan  “Engineering efficient and effective non-metric space library”  In _International Conference on Similarity Search and Applications_ , 2013, pp. 280–293  Springer  URL: http://boytsov.info/pubs/sisap2013.pdf
  * [31] Yury A. Malkov and Dmitry A. Yashunin  “Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs”  In _CoRR_ abs/1603.09320, 2016  DOI: https://doi.org/10.48550/arXiv.1603.09320

## Appendix

###  Appendix A Datasets

We used text classification datasets, where we expect the classes to be
related to the semantic meaning of the texts.

  * •

20 Newsgroups as can be fetched through scikit-learn which fetches data from
the 20 newsgroups website111111http://qwone.com/~jason/20Newsgroups/.
Originally collected by Ken Lang. It consists of 18846 newsgroup posts with 20
different topics split into a train set of 11314 samples and a test set of
7532 samples. Embeddings were made on the posts as given by the scikit-learn
library with no additional preprocessing. License: Unknown.

  * •

AG News fetched from Kaggle121212www.kaggle.com/datasets/amananandrai/ag-news-
classification-dataset. Originally made by Antonio Gulli
131313groups.di.unipi.it/~gulli/AG_corpus_of_news_articles.html. News stories
divided into four classes each with 30,000 training samples and 1,900 testing
samples. So in all we have 120,000 training samples and 7,600 test samples.
Embeddings were made on the title concatenated with the description with line
breaks replaced by spaces. License: Custom. Any non-commercial use allowed.

  * •

Yahoo Answers fetched from Kaggle141414www.kaggle.com/datasets/yacharki/yahoo-
answers-10-categories-for-nlp-csv made by [28]. Questions and best answers
from Yahoo Answers from 10 categories. We use 10 percent of this dataset, so
for each category we have 14,000 training samples and 600 test samples, which
means we have 140,000 training samples and 6000 test samples in all. Indexes
of used samples can be found in the code
repository151515https://github.com/bemigini/hubness-reduction-sentence-bert.
Embeddings were made on the question title concatenated with the question
content and the best answer with line breaks replaced by spaces. License:
Unknown.

###  Appendix B K-occurrence and the Mean of the Data

According to [6], in unimodal data distributions there is a strong correlation
between $N_{k}(x)$ and how close $x$ is to the global data mean. That is,
points close to the center of the data tend to become hubs. While for
multimodal distributions [6] found that points close to local cluster means
tend to become hubs. [6] also argue that hubness depends on the intrinsic
dimension of data and not the dimension of the embedding. [29] points out that
high intrinsic dimension does not in itself produce high hubness. They argue
that high density gradients, e.g., introduced by support boundaries can lead
to formation of hubs.

###  Appendix C Additional Hubness Reduction Methods

On the 20 Newsgroups dataset we tested two additional hubness reduction
methods:

  * •

Forcing uniform distribution centered at 0 in each dimension of embeddings and
then normalising embeddings to unit length (f-uniform) same way as described
in section 2.1 ”Illustration on Synthetic Data”.

  * •

Local scaling as introduced by [16] (Proposed for hubness reduction by [12]).

We tested f-uniform, since it might not be the distribution which is
important, but only that the center of the data is the zero vector and that
the variance of the dimensions is the same. However, we did expect that
f-uniform would destroy the learned structure of the embeddings, since it
seems the distribution of the dimensions of the embeddings before hubness
reduction is close to normal. We were suprised to find that f-uniform
decreased error rate in almost as many cases as f-norm, but we still decided
to only continue with f-norm on the two other datasets, because of the
observed distribution of the embeddings.

Local scaling introduces a secondary distance measure $LS(d_{x,y})$ between
points $x,y$, which uses a local scaling parameter $\sigma_{x}$ \- the
distance between $x$ and the m’th nearest neighbour of $x$ for a chosen
$m\in\mathbb{N}$.

$LS(d_{x,y})=1-\exp\left(-\frac{d_{x,y}^{2}}{\sigma_{x}\sigma_{y}}\right)$ (2)

We used $m=5$.

We decided not to continue with local scaling on the two other datasets, since
it did not decrease error rate in as many cases as the other hubness reduction
methods.

###  Appendix D Illustration on Synthetic Data

Figure 2a) shows the distribution of the $k$-occurrence for $10,000$ data
points drawn from a standard normal distribution in $3$, $20$ and $768$
dimensions ($768$ is the dimensionality of Sentence-BERT embeddings). Recall
that the density function for a $D$ dimensional standard normal distribution
is

$(2\pi)^{-D/2}e^{-\frac{1}{2}\sum_{i=1}^{D}x_{i}^{2}}=(2\pi)^{-D/2}e^{-\frac{1}{2}\lVert
x\rVert^{2}}.$ (3)

So the distribution is a function of the length of the vector. Hence, by
normalising data points to unit length, we obtain a uniform distribution on
the hypersphere. Because of [6] we expect hubness to be lower when all points
have equal distance to the mean, see appendix B. Note, the distribution of the
$k$-occurrence is symmetric with this normalization even in 768 dimensions,
see figure 2b), thus for normal distributed data normalization reduces
hubness.

Drawing data points from a normal distribution with a nonzero mean vector,
makes the $k$-occurrence skewed as before even if we normalise embeddings to
unit length. However, if we center the data before normalising, we get again a
symmetric $k$-occurrence distribution. If we instead use a uniform
distribution (e.g., the interval $[-1,1]$) for each dimension and again
normalise embeddings to unit length, then this $k$-occurrence will also become
symmetric.

However, in LLM derived embeddings we do not expect the individual dimensions
to be distributed according to the same normal distribution although
empirically, the distributions of the dimensions do look like normal
distributions (examples in Appendix figure 7).

###  Appendix E Spyplot of before and after f-norm

Figure 6 shows how the number of other sentences a sentence is in the 10
nearest neighbours of is reduced by f-norm.

Figure 6:  The model microsoft-MiniLM-L12-H384-uncased_cos_n with seed 1 on 20
Newsgroups test split. Column samples in the 10 nearest neighbours of the row
sample are marked with a blue dot, otherwise they are unmarked. Samples are
sorted by category. Hubs can be seen as vertical lines especially in the left
side of the before plot. These become much less pronounced after having used
f-norm.

###  Appendix F Example of Distribution of Dimensions

See figure 7.

Figure 7: Values in the dimensions are roughly normally distributed, but do
not have the same mean or variance.

###  Appendix G Error rate - Base vs reductions

Figures 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 show examples of
how the error rate changes from the base case to cases where hubness reduction
methods have been used.

Figure 8: 20 Newsgroups. Average base k-skewness 8.15. Figure 9: 20
Newsgroups. Average base k-skewness 5.60. Figure 10: 20 Newsgroups. Average
base k-skewness 4.79. Figure 11: 20 Newsgroups. Average base k-skewness 10.06.
Figure 12: 20 Newsgroups. Average base k-skewness 5.92. Figure 13: 20
Newsgroups. Average base k-skewness 5.50. Figure 14: AG News. Average base
k-skewness 3.64. Figure 15: AG News. Average base k-skewness 4.98. Figure 16:
AG News. Average base k-skewness 2.40. Figure 17: AG News. Average base
k-skewness 2.22. Figure 18: Ten percent of Yahoo Answers. Average base
k-skewness 8.41. Figure 19: Ten percent of Yahoo Answers. Average base
k-skewness 5.54. Figure 20: Ten percent of Yahoo Answers. Average base
k-skewness 3.29. Figure 21: Ten percent of Yahoo Answers. Average base
k-skewness 3.05.

###  Appendix H Error rate - Without vs with Normalisation

Figures 22, 23, 24, 25, 26, 27, 28 show error rate differences for models
which have been trained without and with normalisation to unit length before
and after using f-norm + MP.

Figure 22: 20 Newsgroups. Figure 23: 20 Newsgroups. Figure 24: 20 Newsgroups.
One model (euclidean) with greatly deviating values (base error rate about
80%) has been removed to better show the variance in the remaining models.
Figure 25: AG News. Figure 26: AG News. One model (euclidean) with greatly
deviating values (base error rate about 14%) has been removed to better show
the variance in the remaining models. Figure 27: Ten percent of Yahoo Answers.
Figure 28: Ten percent of Yahoo Answers. One model (euclidean) with greatly
deviating values (base error rate about 55%) has been removed to better show
the variance in the remaining models.

###  Appendix I Pretrained Models Results and Intended Use

All pretrained models were made during ”Community week using JAX/Flax for NLP
& CV”161616discuss.huggingface.co/t/train-the-best-sentence-embedding-model-
ever-with-1b-training-pairs, organized by Hugging Face. All pretrained models
used have Euclidean distance as a suitable score function, and they are all
supposed to give semantic embeddings of sentences or short paragraphs. Table 2
shows effects on error rate and hubness when using f-norm, MP and f-norm + MP.

Table 2:  Error rate (error), k-skewness (skew) and robinhood score (rh) on 20 Newsgroups (20), AG News (AG) and ten percent of Yahoo Answers (YA) for four pretrained models, base case vs after hubness reduction. Note that all these models have been trained on YA in various ways and their hubness on YA is in general lower than the models we trained. Thus, it seems that training on a specific dataset can make hubness go down for that dataset. However, hubness is still high on 20 which the models have not been trained on. | 20 | AG | YA
---|---|---|---
| error | skew | rh | error | skew | rh | error | skew | rh
multi-qa-distilbert-cos-v1 |  |  |  |  |  |
base | 0.318 | 7.58 | 0.37 | 0.081 | 1.90 | 0.59 | 0.271 | 2.12 | 0.69
f-norm | 0.316 | 2.15 | 0.34 | 0.082 | 1.88 | 0.58 | 0.268 | 2.16 | 0.69
MP | 0.292 | 13.06 | 0.28 | 0.081 | 1.55 | 0.55 | 0.271 | 1.77 | 0.66
f-norm + MP | 0.289 | 1.89 | 0.30 | 0.079 | 1.57 | 0.56 | 0.269 | 1.88 | 0.67
all-MiniLM-L12-v2 |  |  |  |  |  |
base | 0.324 | 11.45 | 0.35 | 0.088 | 1.91 | 0.58 | 0.268 | 1.98 | 0.68
f-norm | 0.324 | 2.22 | 0.33 | 0.086 | 1.88 | 0.58 | 0.269 | 1.97 | 0.68
MP | 0.302 | 16.24 | 0.28 | 0.086 | 1.55 | 0.55 | 0.270 | 1.78 | 0.66
f-norm + MP | 0.300 | 1.88 | 0.29 | 0.085 | 1.56 | 0.56 | 0.267 | 1.79 | 0.67
all-mpnet-base-v2 |  |  |  |  |  |
base | 0.295 | 11.53 | 0.37 | 0.082 | 1.81 | 0.58 | 0.251 | 2.02 | 0.68
f-norm | 0.293 | 2.32 | 0.34 | 0.080 | 1.80 | 0.58 | 0.256 | 1.96 | 0.68
MP | 0.272 | 15.80 | 0.30 | 0.085 | 1.57 | 0.55 | 0.250 | 1.73 | 0.66
f-norm + MP | 0.272 | 1.98 | 0.30 | 0.082 | 1.54 | 0.56 | 0.250 | 1.78 | 0.67
all-distilroberta-v1 |  |  |  |  |  |
base | 0.322 | 6.61 | 0.39 | 0.085 | 1.93 | 0.59 | 0.254 | 2.08 | 0.68
f-norm | 0.315 | 2.53 | 0.35 | 0.084 | 1.90 | 0.58 | 0.257 | 2.07 | 0.68
MP | 0.291 | 11.20 | 0.29 | 0.087 | 1.57 | 0.55 | 0.254 | 1.72 | 0.66
f-norm + MP | 0.296 | 2.05 | 0.31 | 0.085 | 1.59 | 0.56 | 0.253 | 1.82 | 0.67

###  Appendix J Computational Experiment Details

####  J.1 Hyperparameters

When training our models, we kept the default hyperparameters for the
SentenceTransformer object as can be found at github.com/UKPLab/sentence-
transformers/blob/master/sentence_transformers/SentenceTransformer.py. Thus,
the optimizer was AdamW with a learning rate of $2\cdot 10^{-5}$, weight decay
was $0.01$, and the learning rate schedular was set to WarmupLinear. We did
not do a hyperparameter search, since that was not the point of our
experiment.

####  J.2 GPU and CPU Types

Training of the models and making embeddings was done on the following GPU
types: NVIDIA TITAN Xp, GeForce GTX 1080 Ti, NVIDIA TITAN V and NVIDIA TITAN
X.

The knn and hubness measures were done on CPU on either AMD Ryzen 7 PRO 5850U
or Xeon E5-2620 v4.

####  J.3 Computation Time

Training and generating embeddings times reported for running on an NVIDIA
TITAN Xp GPU.

The total training time of the 540 models was about 28.5 hours. Of this, the
models using microsoft-mpnet-base as base model took about 12 hours, the
models using distilroberta-base as base model took about 6 hours and the
models using microsoft-MiniLM-L12-H384-uncased as base model took about 10.5
hours. Note that a single model takes 4 minutes or less to train.

Total time generating embeddings for our own models was about 11.50 hours for
20 Newsgroups for all 540 models, about 21 hours for AG News for the 360
models using microsoft-mpnet-base or distilroberta-base as base model, and
about 46.5 hours for the ten percent of Yahoo Answers for the 360 models using
microsoft-mpnet-base or distilroberta-base as base model.

Generating embeddings for the four pretrained models took about an hour. This
gives us a total of 108.5 hours of GPU time for training and embeddings.

Times for knn and hubness measures reported for running on an AMD Ryzen 7 PRO
5850U CPU.

Getting knn results for our own models took about 69 hours for 20 Newsgroups
for all 540 models, about 267 hours for AG News for the 360 models using
microsoft-mpnet-base or distilroberta-base as base model, and about 306 hours
for the ten percent of Yahoo Answers for the 360 models using microsoft-mpnet-
base or distilroberta-base as base model.

Getting knn results from the pretrained models for all datasets took about 7
hours.

Getting the hubness results for our own models took about 7.5 hours for 20
Newsgroups for all 540 models, about 46.5 hours for AG News for the 360 models
using microsoft-mpnet-base or distilroberta-base as base model, and about 60
hours for the ten percent of Yahoo Answers for the 360 models using microsoft-
mpnet-base or distilroberta-base as base model.

Getting hubness results from the pretrained models for all datasts took about
1.5 hours.

Thus, in total we used 764.5 hours of CPU time for knn and hubness measures.

###  Appendix K Package Versions

Important packages: h5py 3.7.0, hdf5 1.10.6, nltk 3.7, numpy 1.21.5, python
3.9.7, pytorch 1.12.0, sci-kit-hubness 0.30.0a1, scikit-learn 1.1.1, sentence-
transformers 2.2.2, transformers 4.20.1. Complete environment description can
be found on github171717https://github.com/bemigini/hubness-reduction-
sentence-bert.

###  Appendix L Training on STS benchmark

The STS benchmark dataset has pairs of sentences annotated with a semantic
similarity score from 0 (not similar) to 5 (semantically equal). It is split
into a train, a dev, and a test set with $7251$, $1500$, and $2886$ sentence
pairs, respectively. We trained our models on the train split. License:
Unknown.

When training the models, we had to decide what distances these scores should
correspond to. There were two natural choices: The maximum distance between
embeddings should be the distance between orthogonal unit vectors, $\sqrt{2}$
when using Euclidean distance, $1$ when using cosine distance. Or, the maximum
distance between embeddings should be the distance between opposite unit
vectors, $2$ when using Euclidean distance or cosine distance. In some
preliminary experiments we trained both orthogonal and opposite, but there did
not seem to be much difference, so we went ahead using only orthogonal.

###  Appendix M Evaluation Details

When working on the large datasets, AG News and Yahoo Answers, we used the
nmslib library [30] and the Hierarchical Navigable World graph (HNSW) method
[31] for approximate nearest neighbours, which builds a slightly different
index each time it is run.

When using f-norm at test time, for each dimension in the embeddings, we draw
samples from a standard normal distribution for all training and test
embeddings and replace values in the embeddings with the samples which
preserve the ranking within the dimension. This procedure will also work if
there is only one test point we want to classify.

###  Appendix N Best error rates

We consider which models with which hubness reduction methods give us the
lowest error rate when taking the mean over the twelve random seeds.

Models using the largest base model (microsoft-mpnet-base) have the lowest
mean error rate. If we take the three best error rates from the three
datasets, they are all from models using the largest base model. On 20
Newsgroups using f-norm + MP gives the lowest mean error rate. On AG News,
using Euclidean distance during training seemed the best predictor for a low
error rate. On Yahoo Answers, using the largest base model, Euclidean distance
and z-score normalisation during training gave the four lowest error rates
with f-norm + MP being the lowest one. More details below.

On 20 Newsgroups, we find that the ten best mean error rates all used f-norm +
MP. This is still true if we only look at models using the medium base model
(distilroberta-base) or the small base model (microsoft-
MiniLM-L12-H384-uncased). So on this dataset, using the f-norm + MP gives the
best mean error rate.

On AG News, the ten best mean error rates all used Euclidean distance for
training. The best three also used z-score normalisation. The best three and
the seventh best use the largest base model, the rest all use the medium base
model. If we only look at models using the medium base model, the best ten
still all used Euclidean distance for training, however the best four are no
longer z-score normalisation. So on this dataset, using Euclidean distance for
training the model seems to be the best predictor for a low mean error rate.

On the Yahoo Answers dataset, the best four all used the largest base model,
Euclidean distance and z-score normalisation and with the reductions in order:
f-norm + MP, MP, f-norm, none. The numbers four to ten all used the f-norm +
MP. If we restrict to the medium base model, the best seven mean error rates
are all from models which used Euclidean distance. The best three are after
using f-norm + MP, four to six used f-norm, seven used MP and eight to ten
used f-norm + MP. So on this dataset, f-norm + MP still gives the best mean
error rate, but using the largest base model, Euclidean distance and z-score
normalisation gave better error rate than using anything else and then f-norm
+ MP.

###  Appendix O Differences Between Normalisations During Training

Models which use some kind of embedding length normalisation (n; c,n; z) tend
to have slightly lower hubness measured with robinhood score than models which
do not have this kind of normalisation (none; c). However, there is also a
difference between the base models used. On 20 Newsgroups, if we take any two
models using microsoft-mpnet-base as base model where one uses some kind of
length normalisation (n; c,n; z) and the other does not (none; c), then in
about 97.2% of cases the model not using length normalisation will have the
higher robinhood score. If we do the same for two models using microsoft-
MiniLM-L12-H384-uncased as base model, the same will be true in about 70.5%
cases. It is still a majority and it is still safe to assume it is a different
distribution (Mann-Whitney U test gives a p-value of $3.3\cdot 10^{-6}$), but
it is not as overwhelming.

On 20 Newsgroups for the models using the small and medium base models, the
base error rate is worse when using Euclidean distance without than it is with
normalisation to unit length. However, for the models using the largest base
model (except for one which seems to have failed training), error rates are
slightly better for the models without normalisation than with. On AG News and
Yahoo Answers, models (medium and large) using Euclidean distance and no
normalisation have lower error rates than models with normalisation to unit
length and also lower than models using cosine or cosine distance both with
and without unit length normalisation. See Appendix H for figures.

###  Appendix P Mutual Proximity Implementation

[12] showed that instead of calculating distances from $x,y$ to all other
points in the dataset, it is enough to take a sample of other points, and, if
further assuming that distances are approximately normally distributed, stable
results can be obtained with as few as 30 samples.
We used an implementation of mutual proximity which assumes a normal
distribution of distances, since it is faster to compute than the one which
allows arbitrary distribution of distances. This is reasonable, since [12]
showed that mutual proximity assuming a normal distribution of distances, had
a similar performance to the type without the assumption.

###  Appendix Q More Skewness Gives Larger Effect of Reduction

On AG News, for the $65$ cases where error rate does not improve when using
f-norm + MP, the maximum skewness is $2.58$ and the mean skewness is $2.27$,
compared to $9.80$ and $2.80$ for models where error rate improved and $9.80$
and $3.41$ for models where error rate was reduced with at least half a
percentage point. There are $96$ models which have a base skewness score of
more than $3$ and of these, $91$ cases have an error rate reduction of more
than half a percentage point. So the method is more likely to have a larger
effect if the base skewness is higher.

###  Appendix R Note on SVM

Using SVM on our trained embeddings for classification on 20 Newsgroups, we
saw that in 539 or 506 cases out of 540 when using an rbf or linear kernel,
error rate improved from the base case when using f-norm on the embeddings
before SVM. Error rate also went down in 455 or 540 cases out of 540 when
using an rbf or linear kernel when using f-norm compared to Z-score
normalisation before SVM. Exploring this further would be a good direction for
future research.

###  Appendix S Overview Tables

Figures 29, 30, 31, 32, 33, 34, 35 show tables with min, max and mean of error
rate(error), k-skewness(skew) and robinhood score(rh) for the 12 random seeds
of all our trained model types on the test splits of our datasets.

Figure 29: Error rate and hubness on the test split of the 20 Newsgroups
dataset for the smallest base model tested. Means are over the 12 random
seeds. error: Error rate, skew: K-skewness, rh: Robinhood score. Figure 30:
Error rate and hubness on the test split of the 20 Newsgroups dataset for the
medium base model. Means are over the 12 random seeds. error: Error rate,
skew: K-skewness, rh: Robinhood score. Figure 31: Error rate and hubness on
the test split of the 20 Newsgroups dataset for the largest base model tested.
Means are over the 12 random seeds. error: Error rate, skew: K-skewness, rh:
Robinhood score. Figure 32: Error rate and hubness on the test split of the AG
News dataset for the medium base model tested. Means are over the 12 random
seeds. error: Error rate, skew: K-skewness, rh: Robinhood score. Figure 33:
Error rate and hubness on the test split of the AG News dataset for the
largest base model tested. Means are over the 12 random seeds. error: Error
rate, skew: K-skewness, rh: Robinhood score. Figure 34: Error rate and hubness
on the test split of the ten percent of the Yahoo Answers dataset for the
medium base model tested. Means are over the 12 random seeds. error: Error
rate, skew: K-skewness, rh: Robinhood score. Figure 35: Error rate and hubness
on the test split of the ten percent of the Yahoo Answers dataset for the
largest base model tested. Means are over the 12 random seeds. error: Error
rate, skew: K-skewness, rh: Robinhood score.