# Multi hash embeddings in spaCy

Lester James Miranda111Equal contribution and corresponding authors:
<EMAIL_ADDRESS>, Ákos Kádár111Equal contribution and corresponding
authors<EMAIL_ADDRESS>, Adriane Boyd, Sofie Van Landeghem, Anders
Søgaard, Matthew Honnibal

ExplosionAI GmbH

###### Abstract

The distributed representation of symbols is one of the key technologies in
machine learning systems today, playing a pivotal role in modern natural
language processing. Traditional _word embeddings_ associate a separate vector
with each word. While this approach is simple and leads to good performance,
it requires a lot of memory for representing a large vocabulary. To reduce the
memory footprint, the default embedding layer in spaCy is a _hash embeddings_
layer. It is a stochastic approximation of traditional embeddings that
provides unique vectors for a large number of words without explicitly storing
a separate vector for each of them. To be able to compute meaningful
representations for both known and unknown words, hash embeddings represent
each word as a summary of the normalized word form, subword information and
word shape. Together, these features produce a _multi-embedding_ of a word. In
this technical report we lay out a bit of history and introduce the embedding
methods in spaCy in detail. Second, we critically evaluate the hash embedding
architecture with multi-embeddings on Named Entity Recognition datasets from a
variety of domains and languages. The experiments validate most key design
choices behind spaCy’s embedders, but we also uncover a few surprising
results.

##  1 Introduction

The Python package spaCy111https://spacy.io is a popular suite of Natural
Language Processing software, designed for production use-cases. It provides a
selection of well-tuned algorithms and models for common NLP tasks, along with
well optimized data structures. The library also pays careful attention to
stability, usability and documentation.

Early versions of spaCy assumed that users would mostly use the default models
and architectures, and did not offer a fine-grained API for to customize and
control training. This changed with the release of v3, which introduced a new
configuration system and also came with a newly designed and documented
machine learning system, Thinc.222https://thinc.ai Together these give users
full control of the modelling details.

Over the years spaCy has developed its own model architectures and default
hyperparameters, informed by practical considerations that are not only
motivated by scoring well on a single standard benchmark. In particular, spaCy
prioritizes run-time efficiency on CPU, the ability to run efficiently on long
documents, robustness to domain-shift, and the ability to fine-tune the model
after training, without access to the original training data.

In this technical report, we focus on one of the more unusual features of
spaCy’s default model architectures: its strategy for embedding lexical items.
We explain how this layer operates, provide experiments that show its
sensitivity to key hyperparameters, and compare it to a more standard
embedding architecture on a few datasets. Our experiments focus on how the
embedding layer functions in the context of spaCy’s default Named Entity
Recognition architecture.

We these experiments aim to provide useful background information to users who
wish to customize, change or extend spaCy’s default architectures in their own
experiments.

##  2 Background

Figure 1: Illustration of the FGREP architecture. Redrawn from Miikkulainen
and Dyer, (1991)

Natural language processing (NLP) systems take text as input, broken down into
a list of words or subwords. Word embeddings have become a _de facto_ standard
for NLP, enabling us to represent compact tokens that can generalize well.
These embeddings associate words with continuous vectors and are trained such
that functionally similar words have similar representations. The trained
embeddings encode useful syntactic and semantic information. While an
improvement over predecessors such as tf-idf, word embeddings are still memory
intensive: each word in the vocabulary is typically stored as a 300-dimension
vector. As one of our main concerns in spaCy is efficiency, we use the hashing
trick to radically reduce the search space in a lookup table with little to no
degradation in accuracy. To understand how spaCy’s embedding system came to
be, let us go through a brief history of modern embeddings.

Real-valued representations of concepts have a long history. The way we think
about word embeddings today originates from the FGREP architecture of
Miikkulainen and Dyer, (1991): a small neural network with a persistent public
global lexicon available in its input and output is learned end-to-end as
shown in Figure 1. This global lexicon is a matrix where each row vector
represents a single word, and the distance (or angle) between these vectors is
small when words are similar and large when they are different.

Collobert and Weston, (2008) first popularized the idea of using neural
network models with pretrained word embeddings. They trained a convolutional
architecture to perform multiple linguistic tasks—named entity recognition
(NER), chunking, part-of-speech (POS) tagging, and semantic role labeling—with
a single neural network in a multi-task setting. Crucially, they devised an
efficient approach to pretrain word embeddings that leverages large volumes of
unlabeled text. To pretrain the embeddings, they constructed a simpler
architecture than the one used for the downstream task, and rather than
maximizing the likelihood of the next word, as in Bengio et al., (2000), they
only trained the model to distinguish between real samples from Wikipedia and
_contrastive_ examples, i.e., sequences of words sampled from Wikipedia where
a random word replaces the middle word. Their follow-up paper, _Natural
Language Processing (Almost) from Scratch_ (Collobert et al.,, 2011), shows
that cheap _pretraining_ of word embeddings on large corpora closes the gap in
downstream evaluation between neural networks and NLP systems that rely on
feature engineering. Roughly at the same time, Turian et al., (2010) showed
that adding word embeddings—as well as more traditional Brown clusters (Brown
et al.,, 1992)—to linear structured models of chunking and named entity
recognition is a straightforward way to boost performance.

The final key innovation that led to the widespread adoption of word
embeddings in the NLP community came when the pretraining phase was made
cheaper. This was accomplished by Mikolov et al., (2013) who removed the
hidden layers and non-linearities while relying entirely on linear models with
contrastive losses. To improve the coverage of word embeddings the popular
library fastText333https://fasttext.cc computes word representations as the
sum of word and subword vectors (Bojanowski et al.,, 2017).444Since then,
various pretraining objectives have been devised to train _context-sensitive_
word representations by training a transformer encoder together with subword
embeddings. Some make use of masking, i.e., predicting missing words from
surrounding contexts (Devlin et al.,, 2019), while others involve self-
supervision schemes like denoising corrupted documents (Lewis et al.,, 2020).
These architectures are out-of-scope for this report, but are available in
spaCy under https://github.com/explosion/spacy-transformers.

The blueprint has not changed much since then. Today, the idea of pretraining
seems obvious and spaCy models are shipped with _static vectors_ pretrained on
large corpora. As we will show in the results for named entity recognition,
pretrained embeddings have a dramatic impact on the performance of modern NLP
systems. All models in spaCy can make use of pretrained embeddings, but also
learn word embeddings by backpropagating errors from the downstream tasks such
as named entity recognition or coreference resolution all the way down to the
word representations.

Since we value efficiency, we use _hash embeddings_ when initializing task-
specific embeddings rather than storing separate representations for each
word. By applying the hashing trick (Moody,, 1988; Weinberger et al.,, 2009),
we dramatically reduce the vocabulary size to save memory (Tito Svenstrup et
al.,, 2017). Instead of performing a simple lookup operation each word is
hashed multiple times and the hashes are modded into a vector table. Each word
is then represented by a combination of vectors. As such hash embeddings
represent a large number of words using a much smaller number of vectors.
While spaCy models historically use standard static vectors, in the future we
are planning to release pretrained hash embeddings trained with our floret
library555https://github.com/explosion/floret/ that combines fastText with
hash embeddings.

In this report, we describe hash embeddings and compare their performance to
that of standard word embedding lookups. In addition, we fuse subword and word
shape information into the word representations rather than representing each
orthographic form with a vector. This process helps alleviate the issue of
word forms being unseen during training and establish links between words that
are morphologically related. We perform this comparison across multiple named
entity recognition benchmark datasets in multiple languages and domains.

##  3 Embedding layers

Language processing deals with inputs that are made up of discrete symbols. A
word embedding layer $\varepsilon$ is a mapping from entries from a dictionary
to vectors. Task-specific embedding functions are often learned in an end-to-
end fashion, in which case $\varepsilon$ adapts the representation of words to
the downstream task at hand while preserving relevant linguistic regularities.
General-purpose embeddings, on the other hand, are trained in a fully self-
supervised fashion, typically to predict words from contexts or with a
contrastive loss. The simplest representation of input tokens is to encode the
_identity_ of each symbol, and map each $s\in\Sigma$ in our vocabulary
$\Sigma$ to a binary _one-hot_ vector $\mathbf{b}\in\\{0,1\\}^{|\Sigma|}$.
Here $\sum_{j}\mathbf{b}_{j}=1$, meaning that only one element of the vector
is set to 1, and all others are 0. Such a representation disregards any
information about how symbols are used, and its dimensionality grows linearly
with the number of input symbols.

Figure 2:  Diagram of the MultiHashEmbed algorithm. First, from the
orthographic form of “Apple” various features are extracted. Then each feature
is hashed four times and modded to their feature-specific tables. The four
vectors per table summed up and the resulting pooled feature vectors are fed
to a Maxout layer to produce the final embedding.  Algorithm 1 One-hot
encoding

1:$s,\Sigma$ $\triangleright$ Symbol, vocabulary

2:$\mathbf{b}\in\\{0,1\\}^{|\Sigma|}$ $\triangleright$ One-hot vector

3:$N$ $\leftarrow$ $|\Sigma|$

4:$i\leftarrow index(\Sigma,s)$

5:$\mathbf{b}\leftarrow\\{\vec{\scriptstyle 0}\\}$, $|\\{\vec{\scriptstyle
0}\\}|=N$

6:$\mathbf{b}_{i}\leftarrow 1$

It has become the _de facto_ standard in NLP to define a fixed width embedding
matrix $\mathbf{E}_{\ell}\in\mathbb{R}^{|\Sigma|\times d}$ where width $d$ is
a hyperparameter, and embed each symbol as
$\mathbf{E}_{\ell}^{T}\mathbf{b}$.666We use the subscript $\ell$ for the
“lookup” operation performed when indexing into $\mathbf{E}$ Rather than using
a dot-product, this process is implemented as a lookup operation using a
mapping $\texttt{map}:\Sigma\mapsto\mathbb{N}$:

$\varepsilon(s)=\mathbf{E}_{\ell}[\texttt{map}(s)]$ (1)

The embedding layers constitute the input layer, and during training, the
gradients from the loss function are backpropagated all the way down to
$\mathbf{E}_{\ell}$, through all upstream layers. This process adapts
$\mathbf{E}_{\ell}$ to provide representations of symbols that are useful to
solve the downstream task.

Algorithm 2 Create embedding table

1:$d,\texttt{map}$ $\triangleright$ Dimensions, vocabulary

2:$\mathbf{E}_{|\Sigma|\times d}\sim U(0,1)$ $\triangleright$ Uniform random
distribution

3:procedure embed($s$, map)

4: $i\leftarrow\texttt{map}(s)$

5: return $\mathbf{E}_{i}$

6:end procedure

To keep the method tractable, we use the common practice of choosing a
threshold to determine the minimum frequency of a token that is worth
embedding. Another popular criterion is to fix the size $k$ of the embedding
table $\mathbf{E}_{\ell}$ and only learn vectors for the top-$k$ most frequent
symbols. All symbols that are left out of $\mathbf{E}_{\ell}$ get mapped to
the special UNK symbol, and its corresponding vector is used to represent all
unseen words.

###  3.1 Hash Embedding layer

Rather than storing a separate vector for each symbol, hash embeddings apply
the hashing trick in order to reduce the memory footprint. This method is
inspired by Bloom filters (Bloom,, 1970), a simple probabilistic data
structure to solve the membership problem, i.e., to answer the question of
whether we have seen an element $s$ before. Bloom filters only have two
operations: _inserting_ an element and _testing_ whether an element has
already been inserted. They represent a large set $S$ by a compact bit vector
$\mathbf{b}\in\\{0,1\\}^{n}$, where we choose $n$ to be small $|S|\gg n$.
Before an element is inserted, it is hashed by $k$ number of uniform hash
functions: given $n$ buckets, each function maps each symbol $s\in S$ to any
bucket with probability $\frac{1}{n}$. The hash functions are also from a
$k$-independent family to guarantee that they are not correlated. Insertion of
$s$ is performed by hashing it $k$ times and setting the corresponding bits in
$\mathbf{b}$ to 1. Testing whether $s$ is in the filter is done by performing
the hashing and looking up the corresponding values. If all values are 1 then
the element _may exist_ in the filter otherwise it _definitely does not
exist_.

Similarly, hash embeddings are parametrized by the number of rows $n$, the
width $d$ (like usual embedding tables), and by the number of mutually
independent hash functions $\mathcal{H}=\\{h_{1}\ldots h_{k}\\}$ as shown in
Figure 2. Each incoming symbol $s$ is hashed $k$ times and modded into the
embedding table $\mathbf{E}_{h}\in\mathbb{R}^{n\times d}$.777We use the
subscript $h$ for the ”hash” operation performed when indexing into
$\mathbf{E}_{h}$ Given a list of hash functions, the embedding of the symbol
$s$ is:

$\varepsilon(s)=\sum_{h\in\mathcal{H}}\mathbf{E}_{h}[h(s)\,\mathbin{\%}\,n]$
(2)

Algorithm 3 An algorithm for hash embed

1:$\mathbf{E},s,\mathcal{H}$, n $\triangleright$ Embedding table, symbol, hash
functions, number of rows

2:$\mathbf{S}$ $\triangleright$ Pooled feature vector

3:$\mathbf{S}\leftarrow\\{\vec{\scriptstyle 0}\\}$

4:$N$ $\leftarrow$ $|\mathcal{H}|$

5:for $k\leftarrow 1$ to $N$ do

6: $i\leftarrow\mathcal{H}_{k}(s)\mathbin{\%}n$

7: $\mathbf{S}\leftarrow\mathbf{S}+\mathbf{E}_{i}$ $\triangleright$ Vector sum
of $i$-th row

8:end for

Recall that in the regular embedding layer we had a one-hot indicator vector
$\mathbf{b}$. In the case of hash embeddings, the indicator is multi-hot where
$\sum_{j}\mathbf{b}_{j}=k$. Using the multi-hot indicator vector in matrix
form, the multiple selection can be written analogously to the usual embedding
layer $\mathbf{E}_{h}^{T}\mathbf{b}$. Just like traditional embeddings, hash
embeddings produce a single vector for each $s$. However, the main advantage
of hash embeddings is that we do not need to store a separate vector for each
symbol. Since each symbol is represented as a sum of $k$ vectors, a large
number of _signatures_ can be generated as a combination of a small number of
vectors.

###  3.2 Collisions

Hash embeddings just like Bloom filters are prone to collisions. Let’s assume
that due to the uniformity of the hash functions, each symbol $s\in\Sigma$ is
mapped to any row with probability $\frac{1}{n}$. Conversely, the probability
for a specific row _not_ being chosen by a single hash function is
$1-\frac{1}{n}$. The collision probability $p_{c}$ of a hash function with
range $0$ to $n$ over a vocabulary of size $|\Sigma|$ is
$1-(1-\frac{1}{n})^{|\Sigma|-1}$. If we have 50,000 distinct words in our
corpus, a table of 5,000 rows, and a single hash function, then the
probability that some word will be mapped onto the same vector as another is
0.99995. The expected number of tokens that will collide is
$p_{c}\times|\Sigma|$, which in this case is 49,663. We confirm that using a
small table with a single hash function can cause most tokens to collide.
However, by using $k$ independent hash functions with range
$\\{0,\ldots,n\\}$, we approximate a hash function with a greater upper-bound
$n^{k}$. In our case, we set $k=4$, yielding $p_{c}\approx 5\times 10^{-12}$.
This means that in theory, we can use significantly fewer parameters than we
have symbols, with a negligible collision risk.

###  3.3 Multi-embeddings with orthographic features

When talking about word embeddings, it is not always clear which symbols are
embedded by NLP architectures. Sometimes, a _word_ can mean its raw
orthographic form, but at other times, it can also be its lowercase or other
normalized form. The Tokenizer component in spaCy extracts various features
from a token’s orthographic representation for downstream
embedding.888https://spacy.io/api/token#attributes We embed the following
features:

  * •

NORM: Lowercased token with additional normalizations regarding currency
symbols, punctuation and alternate spelling.

  * •

PREFIX: First character.

  * •

SUFFIX: Last three characters.

  * •

SHAPE: Alphabetic characters are replaced by x or X based on casing, numeric
characters are replaced by d and sequences of the same character are truncated
after length 4.

We denote the embedding of NORM, PREFIX, SUFFIX and SHAPE features by
$\mathbf{e}^{\text{norm}}$, $\mathbf{e}^{\text{prefix}}$,
$\mathbf{e}^{\text{suffix}}$ and $\mathbf{e}^{\text{shape}}$, respectively.
The multi-embedding layers take a global _width_ parameter, setting the
dimension $d$ for each embedding. The embeddings are then concatenated
$[\mathbf{e}^{\text{norm}};\mathbf{e}^{\text{prefix}};\mathbf{e}^{\text{suffix}};\mathbf{e}^{\text{shape}}]$,
producing a single embedding of size $4d$. The concatenated vectors are then
projected down to size $d$ by a small neural network
$\mathbf{e}=\Psi([\mathbf{e}^{\text{norm}};\mathbf{e}^{\text{prefix}};\mathbf{e}^{\text{suffix}};\mathbf{e}^{\text{shape}}])$.
In spaCy, we use a Maxout-layer (Goodfellow et al.,, 2013) as represented by
the function $\Psi:\mathbb{R}^{4d}\mapsto\mathbb{R}^{d}$:

$\Psi(\mathbf{x})=\max(\mathbf{W}_{1}^{T}\mathbf{x}+\mathbf{b}_{1},\mathbf{W}_{2}^{T}\mathbf{x}+\mathbf{b}_{2},\mathbf{W}_{3}^{T}\mathbf{x}+\mathbf{b}_{3})$
(3)

Here, the matrices $\mathbf{W}_{1},\mathbf{W}_{2},\mathbf{W}_{3}$ of size
$4d\times d$ and bias terms $\mathbf{b}_{1},\mathbf{b}_{2},\mathbf{b}_{3}$ of
size $d$ are the learnable parameters of the network. The maxout layer is
implemented as a component-wise maximum over multiple linear layers. In spaCy,
we use three pieces for the multi-embedding layers. Our standard embedding
layer, MultiHashEmbed, combines the multi-embedding process described here
with hash embeddings. For this technical report, we additionally implemented
MultiEmbed, which is identical to MultiHashEmbed except that it does not use
the hashing trick.

##  4 Experimental Setup

The main goal of our experiments is to benchmark our hash embedding
implementation, MultiHashEmbed, on different settings and scenarios against
traditional word embeddings. This section outlines the datasets we used as
well as our model architecture. We tested on a variety of named entity
recognition datasets from multiple domains. For word embeddings we used the
vectors distributed with spaCy 3.4.3 (large) models.999Section A.3 in the
Appendix compares these embeddings to fastText vectors.

###  4.1 Named Entity Recognition Datasets

We selected datasets from a variety of domains and languages and that are of
moderate size, which represent realistic use cases for spaCy.

#### CoNLL 2002 (Tjong Kim Sang,, 2002)

Standard benchmark containing news articles. For Spanish the corpus contains
NewsWire articles from May 2000. The Dutch data come from the Belgian
newspaper _De Morgen_ from the months of June to September 2000. We included
this dataset as it is one of the longest standing standard benchmarks in the
field. Entities include: location, person, organization, misc.

#### WNUT 2017 (Derczynski et al.,, 2017)

Standard NER benchmark based on English social media data with the same
training data as the Twitter NER corpus (Derczynski et al.,, 2016) annotated
with tweets from 2010. This dataset is especially challenging, because the
test set contains entities not seen during training. Entities include:
location, person, group, corporation, creative-work, product.

#### AnEM (Ohta et al.,, 2012)

NER dataset focused on anatomical entity extraction. The articles were sourced
from the PubMed Database of publication abstracts and the PubMed Central (PMC)
Open Access subset of full-text publications. This dataset is interesting due
to its specialized domain, where pretrained general-purpose word embeddings
are not expected to provide the same performance boost as for news texts, for
example. Entities include: cell, organism substance, pathological formation,
multi-tissue structure, organism subdivision, organ, cellular component,
anatomical system, tissue, developing anatomical structure, immaterial
anatomical entity.

#### Dutch Archaeology (Brandsen et al.,, 2020)

Contains excavation reports and related documents collected since the 1980s.
The texts were gathered by the Digital Archiving and Networked Services (DANS)
in the Netherlands between 2000 and 2020. This is also a dataset from a
specialized domain and entities include: time period, location, context,
artefact, material, species.

#### OntoNotes 5.0 (Weischedel et al.,, 2013)

A standard NER benchmark that contains text from various genres (e.g., news,
phone conversations, websites, etc.). We included this dataset for its larger
vocabulary size. Entities include: date, geopolitcal entity, ordinal,
organization, quantity, location, cardinal, person, nationalities or religious
or political groups, facility, time, event, money, work of art, law, percent,
product, language.

###  4.2 Dataset processing details

#### Preprocessing

The Dutch CoNLL 2002 data contains document-level segmentation, which we use
in our experiments. This is the only document-level task and for all other
datasets we rely on the provided sentence segmentation. The AnEM dataset only
contains training and test splits. We define a random split of 80% of the
training set for training and 20% for development and use the original test
set for testing. The Dutch Archaeology dataset does not provide canonical
splits, so we create a random split of 80% for training, 10% for development
and 10% for testing. Lastly, we modified the English version of OntoNotes 5.0
by adding raw texts and normalizing punctuation. Table 5 in the Appendix gives
an overview of characteristics of the training sets.

#### Unseen evaluation

To get a better sense of real-world expected performance differences between
MultiEmbed and MultiHashEmbed, we include a separate evaluation for _unseen_
test entities. Since entity IDs are not available for all datasets, we
consider each span as an unseen entity as long as it does not appear verbatim
in the training set. Unseen entities are evaluated by ignoring all known
entity spans during evaluation.

###  4.3 Model architecture and training details

#### Named Entity Recognizer architecture

The named entity recognizer model in spaCy is transition-based (Lample et
al.,, 2016), manipulating an input buffer of tokens and a stack of partially
constructed structures. It relies on the BILUO sequence encoding scheme to
determine whether tokens are at the beginning (Begin), in the middle (In) or
at the end (Last) of an entity, make up single-token entities (Unit) or are
not part of an entity at all (Out). The named entity recognizer makes these
decisions based on the current word as well as the words from the current
entity in the stack if one exists: its first word, its last word, and three
additional context tokens.

Given these state representations, a single-layer Maxout network (Goodfellow
et al.,, 2013) computes a state vector and another feed-forward network with a
Softmax activation computes the action probabilities from that state vector.
To train the model, a dynamic oracle (Goldberg and Nivre,, 2012) is used with
an imitation learning objective that scores how many correct entities are
produced while avoiding the prediction of incorrect entities. Overall, this
algorithm is well suited to named entity recognition problems for languages
similar to English, where named entities generally have distinct boundary
tokens.

#### Training details

For all experiments we use the same model architecture and only vary the
embeddings. We refer to hash embeddings with multiple orthographic features as
MultiHashEmbed.101010https://spacy.io/api/architectures#MultiHashEmbed For
comparison, we implemented MultiEmbed that is the same as MultiHashEmbed, but
using regular lookup instead of the hashing trick. Both embedding layers use
the NORM, PREFIX, SUFFIX and SHAPE features; for MultiHashEmbed we use 5000,
2500, 2500 and 2500 rows for each table respectively and for MultiEmbed we use
the minimum frequency criterion of 10.111111For results on the effect of
minimum frequency see Section A.2 in the Appendix. We use pretrained static
vectors from the large (lg) models distributed with spaCy v3.4.

The embeddings for the orthographic features are concatenated and fed through
a single Maxout layer with three pieces. The token vectors from the embedding
layer are passed to an 8-layer convolutional encoder with residual
connections—all of which have a window size of 3, width of 96, and Maxout
activations. We also use layer normalization (Ba et al.,, 2016) after each
layer.

During training we use dropout (Srivastava et al.,, 2014) with probability
0.1. The training is run for a maximum of 20000 training steps with a patience
of 1600 steps and validation frequency of 200. We use a batch size of 1000
words. For the optimizer we use AdamW (Loshchilov and Hutter,, 2018) with
$\beta_{1}=0.9$ and $\beta_{2}=0.999$ and apply weight decay with coefficient
$0.01$. The starting learning rate is set to $0.001$ and gradient clipping is
applied with norm $1.0$.121212The spaCy config files are shown in Section C in
the Appendix.

##  5 Results

This section reports the results for different benchmarking scenarios for
MultiHashEmbed. For all experiments, we report the average F1-score across
three random seeds. We included the full results in tables in the Appendix.

###  5.1 Comparing MultiEmbed and MultiHashEmbed embedding strategies

Figure 3:  Comparing the MultiHashEmbed and MultiEmbed embedding strategies
with and without pretrained embeddings across a variety of NER datasets.
Evaluated on the test set.  Figure 4:  Comparing the MultiHashEmbed and
MultiEmbed embedding strategies with and without pretrained embeddings across
a variety of NER datasets. Evaluated on unseen test entities.

We compare MultiEmbed and MultiHashEmbed with and without the use of
pretrained embeddings. To level the playing field we also added an _adjusted_
setup for MultiHashEmbed, where we set the number of rows in the lookup tables
equal to that of MultiEmbed. This is because MultiEmbed peeks at the data and
adjusts its size based on the frequencies of symbols in the data and applying
the minimum frequency filtering, whereas the defaults of MultiHashEmbed are
designed to work well without knowing the details of the dataset.

Figure 3 shows the results.131313The complete results are presented in Tables
7, 8, 9 and 10 in the Appendix. When comparing the upper row with the lower
row we find a consistent benefit from using pretrained embeddings across all
datasets. Based on these results we recommend to use pretrained embeddings
when possible. Notably, however, the benefit of pretraining is the least
pronounced for the Archeology and OntoNotes datasets. This is probably due to
OntoNotes being a much larger dataset than the others and Archeology having a
comparable vocabulary size to the CoNLL datasets while having 350k tokens in
the training set compared to the 200k and 260k of the Dutch and Spanish CoNLL
respectively.

Comparing the hash embeddings to the traditional embeddings we find strong
evidence (Figure 3) that our hash embeddings with default number of rows
result in the same performance compared to traditional embeddings. When
peeking into the dataset and adjusting the rows we can get only a slight
increase in performance across the board. This is interesting, because on most
datasets the number of vectors in the MultiHashEmbed tables end up being
_more_ than MultiEmbed when using the default minimum frequency criterion of
10. However, on OntoNotes the hash embeddings have half the number of rows for
NORM as MultiEmbed and the performance is still equivalent. This shows that
the defaults work in general, but also points out the memory savings of the
hashing trick in practice.

Lastly, the results on unseen entities as shown in Figure 4 suggest that
MultiEmbed and MultiHashEmbed also perform similarly on unseen
entities.141414The complete results on unseen entities are presented in Tables
11 and 12 in the Appendix. However, it’s worth noting that systems incur a
significant drop in performance when evaluated on entities not seen during
training even when using pretrained embeddings.151515The results in WNUT 2017
are almost the same, because almost all entities are unseen.

We conclude that MultiHashEmbed performs head to head with MultiEmbed,
highlighting the validity of the use of hash embeddings. We also found that
having more or fewer rows as MultiEmbed does not change the conclusion showing
robustness to this parameter and also pointing out the memory benefits of the
hashing trick.

###  5.2 Number of Rows

| Number of rows in MultiHashEmbed
---|---
| Default |  $=$ MultiEmbed |  $=20\%$ MultiEmbed |  $=10\%$ MultiEmbed
CoNLL es | 0.77$\pm$0.00 | 0.79$\pm$0.01 | 0.78$\pm$0.02 | 0.78$\pm$0.01
Archeology | 0.83$\pm$0.01 | 0.83$\pm$0.01 | 0.82$\pm$0.02 | 0.80$\pm$0.01
Table 1: Results reported are F1-scores on the dev sets. Rows are adjusted
based on the lookup table of MultiEmbed. Without pretrained embeddings.

The main motivation behind hash embeddings is to use a small amount of vectors
and still achieve good performance. We have already seen that on OntoNotes:
MultiHashEmbed performs comparably to MultiEmbed even if it only has half of
the number of vectors for NORM.

Here we go one step further and test MultiHashEmbed, when using only 20% or
10% of the number of vectors available to MultiEmbed. Table 1 shows the
results on the development sets of the Spanish CoNLL and Dutch Archeology
datasets without using pretrained vectors. On the Spanish CoNLL dataset we
find no degradation of performance even when using as little as 10% of the
number of rows as MultiEmbed. On the Dutch Archeology dataset using 20% of the
rows available to MultiEmbed causes a 1% drop in performance, while using 10%
leads to a 3% drop. The results show that hash embeddings can achieve
comparable performance to traditional embeddings with significantly less
parameters.

###  5.3 Orthographic Features

Feature Combination | Relative Error (F1-score)
---|---
ORTH | NORM | PREFIX | SUFFIX | SHAPE | All | Seen | Unseen
| $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | - | - | -
| $\checkmark$ | $\checkmark$ | $\checkmark$ |  | +17% | +0% | +15%
| $\checkmark$ | $\checkmark$ |  |  | +30% | +80% | +26%
| $\checkmark$ |  |  |  | +47% | +100% | +68%
$\checkmark$ |  |  |  |  | +50% | +160% | +62%
Table 2: Relative error increase on MultiHashEmbed embedding given various combinations of orthographic features for the CoNLL Dutch dataset. Without pretrained embeddings. Feature Combination | Relative Error (F1-score)
---|---
ORTH | NORM | PREFIX | SUFFIX | SHAPE | All | Seen | Unseen
| $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | - | - | -
| $\checkmark$ | $\checkmark$ | $\checkmark$ |  | +4% | -31% | +3%
| $\checkmark$ | $\checkmark$ |  |  | +10% | -46% | +5%
| $\checkmark$ |  |  |  | +10% | -35% | +12%
$\checkmark$ |  |  |  |  | +20% | -35% | +16%
Table 3: Relative error increase on MultiHashEmbed embedding given various
combinations of orthographic features for the AnEM dataset. Without pretrained
embeddings.

After comparing hash embeddings with traditional embeddings, we turn to
evaluating the contribution of the orthographic features. We start with
spaCy’s default NORM, PREFIX, SUFFIX and SHAPE features, then gradually remove
them one-by-one while measuring their effect on performance. We also included
an ORTH-only configuration, which represents the most common method outside of
spaCy. Tables 2 and 3 report the relative error increase in the F1-score for
Dutch CoNLL 2002 and AnEM. We used these two datasets because CoNLL is a
standard benchmark representing a common choice to tune default parameters and
architectures. In contrast, AnEM is a smaller dataset with a specialized
domain.

Table 2 reports the results for CoNLL Dutch, which are in line with our
expectations: removing any of the features degrades performance and ORTH
performs the worst overall. We do find the same pattern for the AnEM dataset
in Table 3 but only if we consider the global F1 score. However, when engaging
with a more fine-grained analysis we see that the error decreased on seen
entities, but increased on unseen entities. This highlights the need for more
detailed evaluation processes to find emergent differences between systems
even when the standard evaluation seems to support one’s hypotheses and
intuitions.161616We will release a utility for evaluating on seen / unseen
entities in the future. Overall, our results show that subword and word shape
features can be a cheap and effective way to improve performance.

###  5.4 Number of hash functions

Other than the number of rows in the MultiHashEmbed tables the number of
independent hash functions can also be used to control the capacity of the
embedding layer. In spaCy this is currently fixed to four, but to critically
evaluate this choice we tried the model with one, two, three and four hash
functions. The results in Figure 5 indicate that the performance does not vary
too much on most datasets.171717Full results can be found in the Appendix in
Tables 13 and 14.

To understand the findings better, Table 4 shows the number of unique NORM,
PREFIX, SUFFIX and SHAPE features found for each dataset. First, note that
having 2500 rows for the PREFIX feature is too large, especially on datasets
with Latin scripts. In addition, the number of SHAPE rows is also below 500
for most datasets except WNUT 2017. This suggests that the default, 2500, is
more than enough for many use cases. In terms of collisions, we did not see
significant improvements from using multiple hash functions even if for
example the CoNLL datasets contain five times the number of the default 5000
rows for NORM. This is most likely due to the presence of other orthographic
features abating the possibility of collisions.

However, we do see a different pattern for the larger OntoNotes dataset. Here,
we see a 5% increase in F1-score from using three hash functions as opposed to
one, but we do not observe further improvements when using four. This is most
likely due to the much larger vocabulary size of OntoNotes compared to the
rest of the datasets. Based on these results, we will implement a parameter
for MultiHashEmbed to configure the number of hash functions.

| NORM | PREFIX | SUFFIX | SHAPE
---|---|---|---|---
CoNLL es | 26099 | 84 | 4369 | 314
CoNLL nl | 26036 | 85 | 3988 | 328
WNUT2017 | 12837 | 92 | 5867 | 2103
Archeology | 23112 | 139 | 4764 | 486
AnEM | 7924 | 91 | 2359 | 184
OntoNotes | 49397 | 110 | 7507 | 674
Table 4: Counts of the occurrence of orthographic features in the training
sets. Figure 5:  Performance of MultiHashEmbed with different number of hash
functions. Evaluated on the development set.

##  6 Discussion and Conclusion

Word embeddings have a profound effect on the accuracy of modern NLP
pipelines. The choice of embedding architecture in spaCy is based on hash
embeddings, where we use the hashing trick to provide a memory-efficient
alternative to traditional embeddings. In this report, we evaluated the
effectiveness of spaCy’s MultiHashEmbed. We compared it with a traditional
approach to assess our architectural decisions and establish training and
pipeline recommendations for our users. We found that using hash embeddings is
competitive with traditional embeddings in accuracy while being more memory-
efficient, and that our additional orthographic features can improve
performance. These results support the basic architectural choices in spaCy.

However, we also found some surprising results. The benefit of additional
orthographic features is subtle: on the AnEM dataset they improve the overall
performance, but at the same time degrade the F1-scores on entities that were
seen during training. This finding indicates that although the defaults
provide good performance, fine-grained evaluation for each dataset is
important. Additionally, we were surprised to find that using more than one
hash function does not lead to performance gains in most of the datasets we
considered for this report. In the future we will implement a version of
MultiHashEmbed that parametrizes the number of hash functions. We believe that
this parameter can lead to significant improvements in speed and power usage.

Given these findings, we recommend spaCy users to:

  * •

Thoroughly inspect the data before training an NER pipeline. We provide a
utility in spaCy that reports useful entity statistics and problems like
invalid entity annotations or low data labels.181818Read more about debug
data: https://spacy.io/api/cli#debug-data

  * •

Experiment with the use of orthographic features. Based on one’s dataset,
certain features can be relevant or irrelevant. We recommend an investigation
similar to Section 5.3 to determine which features should be included.

  * •

Experiment with the number of rows in the lookup table and the number of hash
functions. We discovered that there are many ways to reduce the memory
footprint of a spaCy pipeline without considerable degradation in performance.
A dataset may benefit from a lower number of rows and a single hash function.

  * •

Make use of pretrained embeddings distributed by spaCy. We provide high
quality pretrained embeddings for multiple languages. They can significantly
boost performance on smaller datasets.

The default configuration in spaCy can deliver good performance out of the
box. However, they are biased towards providing a good performance and
efficiency trade-off for the pretrained pipelines191919https://spacy.io/models
often trained on larger and more diverse corpora such as OntoNotes.

As such, we encourage spaCy users to follow our recommendations and experiment
with various parameters potentially making their production pipelines more
efficient, with little to no cost in performance.

## References

  * Ba et al., (2016) Ba, J. L., Kiros, J. R., and Hinton, G. E. (2016).  Layer normalization.  arXiv preprint arXiv:1607.06450.
  * Bengio et al., (2000) Bengio, Y., Ducharme, R., and Vincent, P. (2000).  A neural probabilistic language model.  Advances in neural information processing systems, 13.
  * Bloom, (1970) Bloom, B. H. (1970).  Space/time trade-offs in hash coding with allowable errors.  Communications of the ACM, 13(7):422–426.
  * Bojanowski et al., (2017) Bojanowski, P., Grave, E., Joulin, A., and Mikolov, T. (2017).  Enriching word vectors with subword information.  Transactions of the association for computational linguistics, 5:135–146.
  * Brandsen et al., (2020) Brandsen, A., Verberne, S., Wansleeben, M., and Lambers, K. (2020).  Creating a dataset for named entity recognition in the archaeology domain.  In Proceedings of the 12th Language Resources and Evaluation Conference, pages 4573–4577, Marseille, France. European Language Resources Association.
  * Brown et al., (1992) Brown, P. F., Della Pietra, V. J., Desouza, P. V., Lai, J. C., and Mercer, R. L. (1992).  Class-based n-gram models of natural language.  Computational linguistics, 18(4):467–480.
  * Collobert and Weston, (2008) Collobert, R. and Weston, J. (2008).  A unified architecture for natural language processing: Deep neural networks with multitask learning.  In Proceedings of the 25th international conference on Machine learning, pages 160–167.
  * Collobert et al., (2011) Collobert, R., Weston, J., Bottou, L., Karlen, M., Kavukcuoglu, K., and Kuksa, P. (2011).  Natural language processing (almost) from scratch.  Journal of machine learning research, 12(ARTICLE):2493–2537.
  * Derczynski et al., (2016) Derczynski, L., Bontcheva, K., and Roberts, I. (2016).  Broad Twitter corpus: A diverse named entity recognition resource.  In Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers, pages 1169–1179, Osaka, Japan. The COLING 2016 Organizing Committee.
  * Derczynski et al., (2017) Derczynski, L., Nichols, E., van Erp, M., and Limsopatham, N. (2017).  Results of the WNUT2017 shared task on novel and emerging entity recognition.  In Proceedings of the 3rd Workshop on Noisy User-generated Text, pages 140–147, Copenhagen, Denmark. Association for Computational Linguistics.
  * Devlin et al., (2019) Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. (2019).  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), pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Goldberg and Nivre, (2012) Goldberg, Y. and Nivre, J. (2012).  A dynamic oracle for arc-eager dependency parsing.  In Proceedings of COLING 2012, pages 959–976, Mumbai, India. The COLING 2012 Organizing Committee.
  * Goodfellow et al., (2013) Goodfellow, I. J., Warde-Farley, D., Mirza, M., Courville, A., and Bengio, Y. (2013).  Maxout networks.
  * Lample et al., (2016) Lample, G., Ballesteros, M., Subramanian, S., Kawakami, K., and Dyer, C. (2016).  Neural architectures for named entity recognition.  In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 260–270.
  * Lewis et al., (2020) Lewis, M., Liu, Y., Goyal, N., Ghazvininejad, M., Mohamed, A., Levy, O., Stoyanov, V., and Zettlemoyer, L. (2020).  BART: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 7871–7880, Online. Association for Computational Linguistics.
  * Loshchilov and Hutter, (2018) Loshchilov, I. and Hutter, F. (2018).  Decoupled weight decay regularization.  In International Conference on Learning Representations.
  * Miikkulainen and Dyer, (1991) Miikkulainen, R. and Dyer, M. G. (1991).  Natural language processing with modular pdp networks and distributed lexicon.  Cognitive Science, 15(3):343–399.
  * Mikolov et al., (2013) Mikolov, T., Chen, K., Corrado, G., and Dean, J. (2013).  Efficient estimation of word representations in vector space.  arXiv preprint arXiv:1301.3781.
  * Moody, (1988) Moody, J. (1988).  Fast learning in multi-resolution hierarchies.  Advances in neural information processing systems, 1.
  * Ohta et al., (2012) Ohta, T., Pyysalo, S., Tsujii, J., and Ananiadou, S. (2012).  Open-domain anatomical entity mention detection.  In Proceedings of the Workshop on Detecting Structure in Scholarly Discourse, pages 27–36, Jeju Island, Korea. Association for Computational Linguistics.
  * Srivastava et al., (2014) Srivastava, N., Hinton, G., Krizhevsky, A., Sutskever, I., and Salakhutdinov, R. (2014).  Dropout: a simple way to prevent neural networks from overfitting.  The journal of machine learning research, 15(1):1929–1958.
  * Tito Svenstrup et al., (2017) Tito Svenstrup, D., Hansen, J., and Winther, O. (2017).  Hash embeddings for efficient word representations.  Advances in neural information processing systems, 30.
  * Tjong Kim Sang, (2002) Tjong Kim Sang, E. F. (2002).  Introduction to the CoNLL-2002 shared task: Language-independent named entity recognition.  In COLING-02: The 6th Conference on Natural Language Learning 2002 (CoNLL-2002).
  * Turian et al., (2010) Turian, J., Ratinov, L., and Bengio, Y. (2010).  Word representations: a simple and general method for semi-supervised learning.  In Proceedings of the 48th annual meeting of the association for computational linguistics, pages 384–394.
  * Weinberger et al., (2009) Weinberger, K., Dasgupta, A., Langford, J., Smola, A., and Attenberg, J. (2009).  Feature hashing for large scale multitask learning.  In Proceedings of the 26th annual international conference on machine learning, pages 1113–1120.
  * Weischedel et al., (2013) Weischedel, R., Palmer, M., Marcus, M., Hovy, E., Pradhan, S., Ramshaw, L., Xue, N., Taylor, A., Kaufman, J., Franchini, M., El-Bachouti, M., Belvin, R., and Houston, A. (2013).  Ontonotes release 5.0.  Linguistic Data Consortium.

##  Appendix A Appendix

###  A.1 Dataset statistics

Table 5 shows the training set characteristics for each dataset we used in the
experiments whereas Table 6 shows the number of unseen and seen entities for
each split.

| Documents | Tokens | Classes | Entities | Doc length | Ent length | Vocab | Unknown
---|---|---|---|---|---|---|---|---
CoNLL es | 8323 | 264715 | 4 | 2.25 | 31.8 | 1.74 | 26099 | 2819
CoNLL nl | 287 | 202644 | 4 | 46.5 | 706 | 1.4 | 27804 | 4148
WNUT2017 | 3394 | 62730 | 6 | 0.58 | 18.5 | 1.6 | 14878 | 4911
Archeology | 26804 | 351235 | 6 | 0.92 | 13.10 | 1.37 | 25404 | 8921
AnEM | 2252 | 57894 | 11 | 0.66 | 25.7 | 1.5 | 8711 | 1057
OntoNotes | 18127 | 2097259 | 18 | 6.95 | 115.69 | 1.86 | 57131 | 7310
Table 5: Training set characteristics.

For Table 5, the Entities column shows the number of entities per document.
Doc length and Ent length indicate the mean number of tokens within documents
and entity spans respectively. The Vocab column shows the size of the
vocabulary, estimated based on the raw orthographic form of tokens produced by
spaCy’s tokenizer. The Unknown column indicates the number of tokens that are
not in the vocabulary of the pretrained embeddings.

| Dev | Test
---|---|---
| Seen | Unseen | Seen | Unseen
CoNLL es | 2300 | 2052 | 2214 | 1345
CoNLL nl | 1039 | 1577 | 1797 | 2144
WNUT2017 | 0 | 836 | 0 | 1079
Archeology | 2764 | 492 | 2669 | 482
AnEM | 290 | 110 | 548 | 708
OntoNotes | 13964 | 6004 | 8620 | 3517
Table 6: The total number of seen and unseen entities for the development and
test sets for each corpus. Notice that WNUT 2017 only contains unseen
entities.

###  A.2 Minimum frequency

Throughout our experiments, we used a minimum frequency of 10 in MultiEmbed.
We are interested if this choice has biased our comparison. Hence, we compare
MultiHashEmbed with default settings against MultiEmbed using minimum document
frequencies of 10, 5, and 1.

We show the results with and without pretrained embeddings in Figure
6.202020Full results reported in Table 15 and 16. We find that MultiEmbed
performs the best overall with minimum frequency of 10 when used together with
pretrained embeddings.

However, the results are inconsistent when we test without static vectors. On
Spanish ConLL, Archeology, WNUT 2017, and OntoNotes, the performance is not
affected by the minimum frequency threshold—only a $\pm$2 change in the
F1-score. We did not observe this in AnEM: changing the minimum frequency
cutoff from 10 to 1 caused a dramatic increase of 11 points. Something similar
happened in Dutch ConLL, reducing the minimum frequency to 1 caused a 6 point
increase compared to MultiHashEmbed.

When taking these results into consideration, it seems that MultiEmbed has the
potential to outperform MultiHashEmbed (using default settings) on ConLL,
while allowing its lookup table to only have up to 27k rows for the NORM
orthographic feature.

With that said, our choice of 10 as the minimum document frequency cutoff for
MultiEmbed still gives the most consistent results. Hence we maintained the
same value for all benchmarking scenarios.

Figure 6:  Characterizing MultiEmbed performance with and without pretrained
embeddings across different minimum frequency values (i.e., 10, 5, and 1).
Evaluated on the development set.  Figure 7: Comparing large spaCy vectors
(3.4.3) against fastText vectors.

###  A.3 Pretrained embeddings distributed by spaCy vs. fastText

The fastText vectors are another set of commonly-used word embeddings outside
the spaCy ecosystem. They are available for multiple
languages.212121https://fasttext.cc/ In Figure 7, we compare the performance
between spaCy (large) and fastText vectors when used alongside MultiHashEmbed.
We find that there is almost no difference in performance. These results
indicate that the vectors distributed with spaCy provide similar performance
to fastText vectors.222222The complete results are presented in Table 17.

##  Appendix B Tables with complete results

| MultiHashEmbed | MultiEmbed
---|---|---
| Precision | Recall | F1-score | Precision | Recall | F1-score
CoNLL es | 0.83$\pm$0.01 | 0.82$\pm$0.01 | 0.82$\pm$0.01 | 0.84$\pm$0.01 | 0.84$\pm$0.00 | 0.84$\pm$0.00
CoNLL nl | 0.83$\pm$0.00 | 0.82$\pm$0.01 | 0.83$\pm$0.00 | 0.84$\pm$0.01 | 0.83$\pm$0.01 | 0.83$\pm$0.01
WNUT2017 | 0.53$\pm$0.02 | 0.25$\pm$0.04 | 0.34$\pm$0.03 | 0.53$\pm$0.03 | 0.26$\pm$0.02 | 0.35$\pm$0.02
Archeology | 0.83$\pm$0.01 | 0.82$\pm$0.01 | 0.83$\pm$0.01 | 0.83$\pm$0.01 | 0.82$\pm$0.01 | 0.83$\pm$0.00
AnEM | 0.66$\pm$0.01 | 0.57$\pm$0.02 | 0.61$\pm$0.01 | 0.65$\pm$0.02 | 0.58$\pm$0.02 | 0.61$\pm$0.01
OntoNotes | 0.84$\pm$0.02 | 0.83$\pm$0.03 | 0.84 $\pm$0.01 | 0.83$\pm$0.04 | 0.82 $\pm$ 0.01 | 0.83 $\pm$ 0.02
Table 7: Comparison between MultiHashEmbed with default number of rows and MultiEmbed using pretrained embeddings distributed by spaCy. Results are reported on the test set. | MultiHashEmbed | MultiEmbed
---|---|---
| Precision | Recall | F1-score | Precision | Recall | F1-score
CoNLL es | 0.84$\pm$0.01 | 0.86$\pm$0.03 | 0.85$\pm$0.01 | 0.84$\pm$0.01 | 0.84$\pm$0.00 | 0.84$\pm$0.00
CoNLL nl | 0.84$\pm$0.01 | 0.84$\pm$0.01 | 0.84$\pm$0.02 | 0.84$\pm$0.01 | 0.83$\pm$0.01 | 0.83$\pm$0.01
WNUT2017 | 0.56$\pm$0.01 | 0.27$\pm$0.01 | 0.36$\pm$0.02 | 0.53$\pm$0.03 | 0.26$\pm$0.02 | 0.35$\pm$0.02
Archeology | 0.84$\pm$0.01 | 0.83$\pm$0.01 | 0.83$\pm$0.01 | 0.83$\pm$0.01 | 0.82$\pm$0.01 | 0.83$\pm$0.00
AnEM | 0.67$\pm$0.01 | 0.57$\pm$0.02 | 0.62$\pm$0.01 | 0.65$\pm$0.02 | 0.58$\pm$0.02 | 0.61$\pm$0.01
OntoNotes | 0.85$\pm$0.01 | 0.84$\pm$0.03 | 0.85$\pm$0.02 | 0.83$\pm$0.04 | 0.82$\pm$0.01 | 0.83$\pm$0.02
Table 8: Comparison between MultiHashEmbed with adjusted number of rows and MultiEmbed using pretrained embeddings distributed by spaCy. Results are reported on the test set. Adjusted rows for MultiHashEmbed. | MultiHashEmbed | MultiEmbed
---|---|---
| Precision | Recall | F1-score | Precision | Recall | F1-score
CoNLL es | 0.77$\pm$0.01 | 0.77$\pm$0.01 | 0.77$\pm$0.00 | 0.77$\pm$0.01 | 0.77$\pm$0.01 | 0.77$\pm$0.01
CoNLL nl | 0.75$\pm$0.01 | 0.72$\pm$0.01 | 0.73$\pm$0.01 | 0.77$\pm$0.00 | 0.74$\pm$0.01 | 0.75$\pm$0.00
WNUT2017 | 0.27$\pm$0.03 | 0.12$\pm$0.02 | 0.17$\pm$0.02 | 0.29$\pm$0.00 | 0.14$\pm$0.01 | 0.19$\pm$0.01
Archeology | 0.83$\pm$0.01 | 0.81$\pm$0.00 | 0.82$\pm$0.00 | 0.82$\pm$0.00 | 0.78$\pm$0.01 | 0.80$\pm$0.00
AnEM | 0.60$\pm$0.01 | 0.49$\pm$0.01 | 0.54$\pm$0.01 | 0.56$\pm$0.02 | 0.36$\pm$0.03 | 0.44$\pm$0.01
OntoNotes | 0.82$\pm$0.01 | 0.79$\pm$0.01 | 0.81$\pm$0.02 | 0.81$\pm$0.02 | 0.81$\pm$0.01 | 0.81$\pm$0.01
Table 9: Comparison between MultiHashEmbed with default number of rows and MultiEmbed without pretrained embeddings distributed by spaCy. Results are reported on the test set. | MultiHashEmbed | MultiEmbed
---|---|---
| Precision | Recall | F1-score | Precision | Recall | F1-score
CoNLL es | 0.78$\pm$0.01 | 0.77$\pm$0.02 | 0.78$\pm$0.02 | 0.77$\pm$0.01 | 0.77$\pm$0.01 | 0.77$\pm$0.01
CoNLL nl | 0.77$\pm$0.02 | 0.73$\pm$0.00 | 0.75$\pm$0.03 | 0.77$\pm$0.00 | 0.74$\pm$0.01 | 0.75$\pm$0.00
WNUT2017 | 0.28$\pm$0.03 | 0.15$\pm$0.02 | 0.19$\pm$0.01 | 0.29$\pm$0.00 | 0.14$\pm$0.01 | 0.19$\pm$0.01
Archeology | 0.84$\pm$0.01 | 0.80$\pm$0.00 | 0.81$\pm$0.01 | 0.82$\pm$0.00 | 0.78$\pm$0.01 | 0.80$\pm$0.00
AnEM | 0.62$\pm$0.01 | 0.51$\pm$0.01 | 0.56$\pm$0.01 | 0.56$\pm$0.02 | 0.36$\pm$0.03 | 0.44$\pm$0.01
OntoNotes | 0.82$\pm$0.02 | 0.82$\pm$0.01 | 0.82$\pm$0.01 | 0.81$\pm$0.02 | 0.81$\pm$0.01 | 0.81$\pm$0.01
Table 10: Comparison between MultiHashEmbed with adjusted number of rows and MultiEmbed without pretrained embeddings distributed by spaCy. Results are reported on the test set. | MultiHashEmbed | MultiEmbed
---|---|---
| Precision | Recall | F1-score | Precision | Recall | F1-score
CoNLL es | 0.59$\pm$0.02 | 0.60$\pm$0.01 | 0.60$\pm$0.01 | 0.64$\pm$0.02 | 0.64$\pm$0.02 | 0.65$\pm$0.01
CoNLL nl | 0.61$\pm$0.02 | 0.57$\pm$0.00 | 0.59$\pm$0.02 | 0.63$\pm$0.03 | 0.58$\pm$0.00 | 0.59$\pm$0.01
WNUT2017 | 0.21$\pm$0.04 | 0.10$\pm$0.01 | 0.14$\pm$0.01 | 0.23$\pm$0.02 | 0.13$\pm$0.01 | 0.17$\pm$0.03
Archeology | 0.33$\pm$0.01 | 0.38$\pm$0.00 | 0.35$\pm$0.03 | 0.30$\pm$0.01 | 0.42$\pm$0.04 | 0.35$\pm$0.02
AnEM | 0.26$\pm$0.03 | 0.18$\pm$0.02 | 0.21$\pm$0.02 | 0.32$\pm$0.02 | 0.18$\pm$0.03 | 0.23$\pm$0.03
OntoNotes | 0.54$\pm$0.02 | 0.58$\pm$0.01 | 0.56$\pm$0.01 | 0.62$\pm$0.01 | 0.60$\pm$0.02 | 0.61$\pm$0.01
Table 11: Comparison between MultiHashEmbed with default number of rows and MultiEmbed without pretrained embeddings distributed by spaCy. Results are reported on the unseen test set. | MultiHashEmbed | MultiEmbed
---|---|---
| Precision | Recall | F1-score | Precision | Recall | F1-score
CoNLL es | 0.74$\pm$0.01 | 0.74$\pm$0.02 | 0.74$\pm$0.01 | 0.74$\pm$0.02 | 0.73$\pm$0.03 | 0.73$\pm$0.02
CoNLL nl | 0.72$\pm$0.03 | 0.69$\pm$0.01 | 0.70$\pm$0.02 | 0.74$\pm$0.03 | 0.72$\pm$0.01 | 0.73$\pm$0.03
WNUT2017 | 0.45$\pm$0.01 | 0.28$\pm$0.01 | 0.34$\pm$0.00 | 0.47$\pm$0.01 | 0.24$\pm$0.03 | 0.32$\pm$0.03
Archeology | 0.37$\pm$0.02 | 0.42$\pm$0.01 | 0.40$\pm$0.02 | 0.37$\pm$0.02 | 0.50$\pm$0.02 | 0.43$\pm$0.01
AnEM | 0.42$\pm$0.01 | 0.30$\pm$0.02 | 0.35$\pm$0.03 | 0.36$\pm$0.01 | 0.28$\pm$0.02 | 0.32$\pm$0.01
OntoNotes | 0.64$\pm$0.02 | 0.65$\pm$0.02 | 0.65$\pm$0.01 | 0.64$\pm$0.02 | 0.69$\pm$0.01 | 0.66$\pm$0.02
Table 12: Comparison between MultiHashEmbed with default number of rows and MultiEmbed with pretrained embeddings distributed by spaCy. Results are reported on the unseen test set. | Number of hash functions
---|---
| 1 | 2 | 3 | 4
CoNLL es | 0.75$\pm$0.03 | 0.74$\pm$0.02 | 0.73$\pm$0.02 | 0.74$\pm$0.01
CoNLL nl | 0.70$\pm$0.01 | 0.68$\pm$0.02 | 0.70$\pm$0.02 | 0.69$\pm$0.01
WNUT2017 | 0.22$\pm$0.03 | 0.22$\pm$0.02 | 0.22$\pm$0.01 | 0.23$\pm$0.02
Archeology | 0.82$\pm$0.02 | 0.82$\pm$0.01 | 0.82$\pm$0.02 | 0.82$\pm$0.00
AnEM | 0.77$\pm$0.03 | 0.77$\pm$0.03 | 0.78$\pm$0.02 | 0.78$\pm$0.01
OntoNotes | 0.77$\pm$0.03 | 0.79 $\pm$0.01 | 0.82 $\pm$0.01 | 0.82 $\pm$0.02
Table 13: The effect of changing the number of seeds for MultiHashEmbed on dev set performance (F1-score). Without pretrained embeddings. | Number of hash functions
---|---
| 1 | 2 | 3 | 4
CoNLL es | 0.81$\pm$0.01 | 0.81$\pm$0.02 | 0.81$\pm$0.02 | 0.81$\pm$0.00
CoNLL nl | 0.80$\pm$0.02 | 0.80$\pm$0.02 | 0.81$\pm$0.01 | 0.80$\pm$0.00
WNUT2017 | 0.47$\pm$0.03 | 0.47$\pm$0.03 | 0.47$\pm$0.01 | 0.47$\pm$0.01
Archeology | 0.83$\pm$0.00 | 0.83$\pm$0.01 | 0.84$\pm$0.02 | 0.85$\pm$0.00
AnEM | 0.80$\pm$0.02 | 0.80$\pm$0.02 | 0.80$\pm$0.01 | 0.81$\pm$0.01
OntoNotes | 0.78$\pm$0.03 | 0.81 $\pm$0.01 | 0.83 $\pm$0.01 | 0.83 $\pm$0.01
Table 14: The effect of changing the number of seeds for MultiHashEmbed on dev set performance (F1-score). Using spaCy vectors. | MHE |  ME min-freq=10 |  ME min-freq=5 |  ME min-freq=1
---|---|---|---|---
CoNLL es | 0.74 | 0.76 | 0.75 | 0.75
CoNLL nl | 0.69 | 0.72 | 0.74 | 0.75
WNUT2017 | 0.27 | 0.23 | 0.23 | 0.24
Archeology | 0.83 | 0.80 | 0.81 | 0.82
AnEM | 0.78 | 0.67 | 0.71 | 0.78
OntoNotes | 0.82 | 0.82 | 0.83 | 0.83
Table 15: Results reported are on F1-scores on the dev sets. MHE stands for MultiHashEmbed and ME for MultiEmbed. Without pretrained embeddings. | MHE |  ME min-freq=10 |  ME min-freq=5 |  ME min-freq=1
---|---|---|---|---
CoNLL es | 0.81 | 0.83 | 0.83 | 0.81
CoNLL nl | 0.82 | 0.80 | 0.78 | 0.76
WNUT2017 | 0.47 | 0.47 | 0.46 | 0.46
Archeology | 0.85 | 0.84 | 0.83 | 0.83
AnEM | 0.81 | 0.83 | 0.81 | 0.80
OntoNotes | 0.86 | 0.84 | 0.85 | 0.85
Table 16: Results reported are on F1-scores on the dev sets. MHE stands for MultiHashEmbed and ME for MultiEmbed. Using pretrained embeddings distributed by spaCy. | fastText | spaCy (large)
---|---|---
| Precision | Recall | F1-score | Precision | Recall | F1-score
CoNLL es | 0.80$\pm$0.01 | 0.80$\pm$0.00 | 0.80$\pm$0.01 | 0.82$\pm$0.01 | 0.80$\pm$0.01 | 0.81$\pm$0.01
CoNLL nl | 0.81$\pm$0.01 | 0.80$\pm$0.01 | 0.80$\pm$0.02 | 0.80$\pm$0.00 | 0.80$\pm$0.01 | 0.80$\pm$0.00
WNUT2017 | 0.62$\pm$0.02 | 0.37$\pm$0.01 | 0.47$\pm$0.01 | 0.67$\pm$0.06 | 0.36$\pm$0.01 | 0.47$\pm$0.01
Archeology | 0.84$\pm$0.01 | 0.85$\pm$0.01 | 0.84$\pm$0.00 | 0.85$\pm$0.01 | 0.84$\pm$0.02 | 0.85$\pm$0.00
AnEM | 0.82$\pm$0.02 | 0.80$\pm$0.01 | 0.81$\pm$0.01 | 0.83$\pm$0.10 | 0.79$\pm$0.01 | 0.81$\pm$0.01
OntoNotes | 0.84$\pm$0.02 | 0.86$\pm$0.02 | 0.85 $\pm$0.01 | 0.85$\pm$0.02 | 0.85$\pm$0.01 | 0.86$\pm$0.02
Table 17: Comparison between fastText vectors and pretrained embeddings
distributed by spaCy. for MultiHashEmbed. Default number of rows.

##  Appendix C Configuration

This section shows the partial configuration files we used throughout the
experiments.232323For more information about spaCy configuration files, visit
the documentation: https://spacy.io/usage/training#config To make things more
succinct, we removed unnecessary parameters such as path names and pretraining
arguments. Listing 1 shows the configuration file for MultiHashEmbed.

Listing 1: Partial configuration file for MultiHashEmbed

⬇

1[components]

2

3[components.ner.model]

4@architectures = "spacy.TransitionBasedParser.v2"

5state_type = "ner"

6extra_state_tokens = false

7hidden_width = 64

8maxout_pieces = 2

9use_upper = true

10nO = null

11

12[components.ner.model.tok2vec]

13@architectures = "spacy.Tok2VecListener.v1"

14width = ${components.tok2vec.model.encode.width}

15upstream = "*"

16

17[components.tok2vec]

18factory = "tok2vec"

19

20[components.tok2vec.model]

21@architectures = "spacy.Tok2Vec.v2"

22

23[components.tok2vec.model.embed]

24@architectures = "spacy.MultiHashEmbed.v2"

25width = ${components.tok2vec.model.encode.width}

26attrs = ["NORM","PREFIX","SUFFIX","SHAPE"]

27rows = [5000,2500,2500,2500]

28include_static_vectors = true

29

30[components.tok2vec.model.encode]

31@architectures = "spacy.MaxoutWindowEncoder.v2"

32width = 256

33depth = 8

34window_size = 1

35maxout_pieces = 3

36

37[training]

38dropout = 0.1

39accumulate_gradient = 1

40patience = 1600

41max_epochs = 0

42max_steps = 20000

43eval_frequency = 200

44

45[training.optimizer]

46@optimizers = "Adam.v1"

47beta1 = 0.9

48beta2 = 0.999

49L2_is_weight_decay = true

50L2 = 0.01

51grad_clip = 1.0

52use_averages = false

53eps = 0.00000001

54learn_rate = 0.001

The parameter include_static_vectors refers to whether pretrained embeddings
will be used in the spaCy pipeline. This setting is relevant in our
experiments in Section 5.1 and A.2 where we benchmarked performance with and
without pretrained embeddings.

We also implemented MultiEmbed that is similar to MultiHashEmbed except that
it uses a regular lookup instead of the hashing trick. Here, we only need to
change the components.tok2vec.model.embed section as seen in Listing 2:

Listing 2: Partial configuration file for MultiEmbed

⬇

1[components.tok2vec.model.embed]

2@architectures = "spacy.MultiEmbed.v1"

3attrs = ["NORM","PREFIX","SUFFIX","SHAPE"]

4width = ${components.tok2vec.model.encode.width}

5include_static_vectors = true

6unk = 0

Lastly, in order to perform the experiments found in Section 5.4, we modified
MultiHashEmbed to accept a variable number of hash functions. We call this
MultiFewerHashEmbed. The configuration is again similar to MultiHashEmbed with
only a change to the components.tok2vec.model.embed parameter:

Listing 3: Partial configuration file for MultiFewerHashEmbed

⬇

1[components.tok2vec.model.embed]

2@architectures = "spacy.MultiFewerHashEmbed.v1"

3num_hashes = 1

4width = ${components.tok2vec.model.encode.width}

5attrs = ["NORM","PREFIX","SUFFIX","SHAPE"]

6rows = [5000,2500,2500,2500]

7include_static_vectors = true


# G3Ms: Generalized Mean Market Makers

Daniel Z. Zanger
MarketX LLC
<EMAIL_ADDRESS>
Abstract: In the Decentralized Finance (DeFi) setting, we present a new
parametrized family of Constant Function Market Makers (CFMMs) which we call
the Generalized Mean Market Makers (G3Ms), based on the generalized means. The
G3Ms are intermediate between the Arithmetic Mean and Geometric Mean CFMM
models, which G3Ms incorporate as special cases. We also present an extension
of the G3Ms, based on the so-called Generalized f-Means, called Generalized
f-Mean Market Makers (Gf3Ms). We show in addition that the G3Ms possess
certain properties preferable to those exhibited by either the Arithmetic Mean
CFMM or the Geometric Mean CFMM alone.

##  1 Introduction

Gaining wider use and broader popularity in recent years, Decentralized
Finance (DeFi) involves innovative, emerging financial technologies intended
to facilitate a wide range of peer-to-peer transactions. DeFi critically
relies in its design on blockchain and related distributed ledger
technologies, and one of DeFi’s core application domains is the Decentralized
Exchange (DEX) (see [9]). Indeed, a principal use case for the DEX platform
concept is as a medium for buying and selling cryptocurrencies in which market
participants do not require a trusted third party to execute transactions.

Among the the most widely-applied types of DEX architectures are those
employing Automated Market Maker (AMM) protocols [9]. AMMs utilize liquidity
pools instead of a traditional market of buyers and sellers to enable trading
of digital assets without intermediaries. The operation of an AMM relies on a
trading function, the nature of which governs the trading dynamics of the
exchange. Examples of AMM models are the so-called Constant Function Market
Makers (CFMMs) [1],[2],[9], which employ a suitable invariant mapping as the
trading function. The well-known Uniswap [3] is in turn an example of a CFMM
AMM for which a constant-product formula is used to define valid transactions
for the model. Each trade must be executed in such a way that the quantity
removed with respect to one asset in a trade is compensated for by the
quantity of the other asset added. Moreover, a trading function defined by
means of a (weighted) geometric mean gives rise to a CFMM [7] closely related
to the constant product CFMM. Alternately, instead of exploiting a constant
product or geometric mean trading function, constant sum or arithmetic mean
trading functions can also be used to define a CFMM, resulting in a constant
sum or arithmetic mean CFMM [6].

In this article, we describe new forms of CFMMs we call the Generalized Mean
Market Makers (G3Ms). We note that the G3Ms were presented (by the author of
this article) in the 2021 US patent filing [5]. The trading functions of these
G3Ms will respectively correspond to what are known in mathematics as the
Generalized Means [4] – a parametrized family of averages that extends and
generalizes the conventional geometric mean as well as the standard arithmetic
mean. Let $x_{1},...,x_{n}$ be $n$ given nonnegative real numbers, and assume
that $n$ nonnegative weights $w_{1},...,w_{n}$ satisfying

$w_{1}+...+w_{n}=1$ (1)

are also given. Then define the Generalized Mean with respect to a given real
number $p\neq 0$ via

$\mu_{p}(\mbox{\boldmath$x$})=\mu_{p,\mbox{\boldmath$w$}}(\mbox{\boldmath$x$})=\left(\sum_{i=1}^{n}w_{i}x_{i}^{p}\right)^{\frac{1}{p}}.$
(2)

where $\mbox{\boldmath$w$}=(w_{1},...,w_{m})$ and
$\mbox{\boldmath$x$}=(x_{1},...,x_{n})$. Moreover, at $p=0$, define

$\mu_{0}(\mbox{\boldmath$x$})=\mu_{0,\mbox{\boldmath$w$}}(\mbox{\boldmath$x$})=\Pi^{n}_{i=1}x_{i}^{w_{i}}.$
(3)

Hence the Generalized Mean $\mu_{0}(\mbox{\boldmath$x$})$ at $p=0$ coincides
with the (weighted) geometric mean, and, at $p=1$, the Generalized Mean
$\mu_{1}(\mbox{\boldmath$x$})$ coincides with the (weighted) arithmetic mean.
We also extend, in this paper, the concept of a Generalized Mean Market Maker
by introducing the Generalized f-Mean Market Makers (Gf3Ms) as we explain
below.

We expect G3Ms for the intermediate values of $p$ with $0<p<1,$ for example,
to exhibit properties intermediate between the geometric and arithmetic means
and hence to potentially exhibit more favorable behavior as AMMs in at least
some cases than either of the two end point models independently can. In fact,
this intuition appears to be strongly supported by the following

Key Fact.We have

$\mbox{\rm lim}_{p\rightarrow
0}\mu_{p,\mbox{\boldmath$w$}}(\mbox{\boldmath$x$})=\mu_{0,\mbox{\boldmath$w$}}(\mbox{\boldmath$x$}).$
(4)

Thus we see in (4) that, for any vector $x$ and set of weights $w$, the
corresponding generalized means at $p$ actually converge as $p\rightarrow 0$
to the associated generalized mean at $0$ (i.e., the corresponding geometric
mean value). This is a well-known result, stated for example in [4] in the
uniform-weight case (indeed the proof, which can be based on L’Hopital’s rule,
is standard so that we refrain from repeating it here).

A key metric (i.e., figure of merit) to consider when assessing the
effectiveness of different AMM (CFMM) models is the slippage, which may be
defined as the difference between the expected cost of an order to trade a
given asset and the cost actually incurred at the time the order executes (see
§3 below for a formal definition). Generally speaking, a slippage relatively
low in absolute value is considered more favorable. As is well-known (again
see, for example, our own §3), the Arithmetic Mean CFMM is easily shown to
exhibit $0$ slippage in principle, but, by virtue of the way it is defined
mathematically, can only support trades whose total cost is bounded above by a
fixed value – a serious limitation. The geometric mean CFMM, on the other
hand, can in fact support trades of arbitrarily high value but unfortunately
features non-zero slippage. In this article, we also present and prove Theorem
1, in §3. This theorem demonstrates the significance of extending the
Arithmetic Mean and Geometric Mean CFMMs as we do in this paper to
intermediate G3M models with $p$-values in the range $0<p<1.$ It demonstrates
this by showing that, somewhat loosely speaking, there exists a sequence of
G3M models for certain values of $p,0<p<1,$ such that, respectively, valid
(buy) trades of arbitrarily large size can be supported but for which the
respective slippage values for these models grow in absolute value
significantly more slowly than the corresponding slippage values for the
Geometric Mean CFMM model (that is, for the G3M model at $p=0$). Thus, the G3M
model for intermediate values of $p,0<p<1,$ offers a significant advantage
over the G3M model at $p=1$ because trades of aribtrarily large size can be
supported, yet, at the same, also offers an advantage over the G3M model at
$p=0$ as well due to significantly slower slippage growth.

The rest of the paper is organized as follows. In §2.1 we formally introduce
the Generalized Mean Market Maker (G3M) models and prove that they satisfy a
concavity property (see Lemma 1) that valid CFMMs are expected to possess
[1],[9]. In §2.2, we introduce the Generalized f-Mean Market Makers (Gf3Ms).
Finally, in §3, we formally present and prove Theorem 1.

##  2 Generalized Mean and Generalized f-Mean
Market Makers

###  2.1 Generalized Mean Market Makers

In this subsection we formally present the parametrized family of Constant
Function Market Makers (CFMMs) we call the Generalized Mean Market Makers
(G3Ms). Our exposition here in §2 as well as in the rest of the paper – in
terms of the basic underlying definitions and concepts – is based on those in
[1], [2], [9].

To define G3Ms, we will first need to introduce the fundamental concept of a
trading function of a CFMM. We begin, however, with a few requisite
definitions. For any positive integer $n$, consider a basket of $n$
cryptocurrencies, intended for trading, to which is associated a vector
$\mbox{\boldmath$\cal{R}$}=(R_{1},...,R_{n})\in(\mbox{\boldmath$R$}_{+}\cup\\{0\\})^{n}$,
where, here, $\mbox{\boldmath$R$}_{+}$ denotes the set of positive real
numbers. $\cal{R}$ is called the (cryptocurrency) reserves, and each quantity
$R_{i}$ is the reserve amount – which we think of as being a fixed value – in
the exchange of currency $i,i=1,...,n,$ respectively. We denote by
$\mbox{\boldmath$\Delta$}=(\Delta_{1},...,\Delta_{n})\in(\mbox{\boldmath$R$}_{+}\cup\\{0\\})^{n}$
the (cryptocurrency) input trade, so that $\Delta_{i}$ is the amount of
currency $i$ that a trader or market participant proposes to tender or offer
to the DEX in exchange for another currency or currencies. Furthermore, denote
by
$\mbox{\boldmath$\Lambda$}=(\Lambda_{1},...,\Lambda_{n})\in(\mbox{\boldmath$R$}_{+}\cup\\{0\\})^{n}$
the output trade, with $\Lambda_{i}$ being the respective amount of the output
trade in currency $i,i=1,...,n,$ so that $\Lambda_{i}$ will be the amount of
currency $i$ that is proposed to be received by the trader from the DEX in
return should the trade be executed. We call
$(\mbox{\boldmath$\Delta$},\mbox{\boldmath$\Lambda$})$ a trade or proposed
trade.

A trading function, denoted by $\tau$, is defined by

$\displaystyle\tau:(\mbox{\boldmath$R$}_{+}\cup\\{0\\})^{n}\times(\mbox{\boldmath$R$}_{+}\cup\\{0\\})^{n}\times(\mbox{\boldmath$R$}_{+}\cup\\{0\\})^{n}\rightarrow\mbox{\boldmath$R$}$
(5)
$\displaystyle\tau(\mbox{\boldmath$\cal{R}$},\mbox{\boldmath$\Delta$},\mbox{\boldmath$\Lambda$})=\mu(R_{1}+\Delta_{1}-\Lambda_{1},...,R_{n}+\Delta_{n}-\Lambda_{n}),$
(6)

for some given function
$\mu:(\mbox{\boldmath$R$}_{+}\cup\\{0\\})^{n}\rightarrow\mbox{\boldmath$R$}$
(whose properties we will have more to say about below in this section).

The trading function $\tau$ specifies whether a trade is regarded as
legitimate and hence may be executed. Indeed, in the CFMM setting a proposed
trade $(\mbox{\boldmath$\Delta$},\mbox{\boldmath$\Lambda$})$ is legitimate and
may be executed if it satisfies

$\tau(\mbox{\boldmath$\cal{R}$},\mbox{\boldmath$\Delta$},\mbox{\boldmath$\Lambda$})=\tau(\mbox{\boldmath$\cal{R}$},\mbox{\boldmath$0$},\mbox{\boldmath$0$})=C.$
(7)

where $C>0$. In other words, the trade is accepted only if the trading
function is maintained at the constant value
$\tau(\mbox{\boldmath$\cal{R}$},\mbox{\boldmath$0$},\mbox{\boldmath$0$})=C$.
Indeed we can regard a CFMM as defined by its trading function along with its
reserves $\cal{R}$.

A standard example within the AMM/CFMM context here of a trading function as
given by (5)-(6) is the geometric mean CFMM trading function

$\tau(\mbox{\boldmath$\cal{R}$},\mbox{\boldmath$\Delta$},\mbox{\boldmath$\Lambda$})=\sqrt[n]{\Pi^{n}_{i=1}(R_{i}+\Delta_{i}-\Lambda_{i})},$
(8)

so that with respect to (8) the definition of the function $\tau$ is based on
that of the geometric mean as given by (3) with $w_{i}=1/n,i=1,...,n$. Another
such example is the arithmetic mean CFMM defined by

$\tau(\mbox{\boldmath$\cal{R}$},\mbox{\boldmath$\Delta$},\mbox{\boldmath$\Lambda$})=\frac{1}{n}\sum^{n}_{i=1}R_{i}+\Delta_{i}-\Lambda_{i},$
(9)

so that with respect to (9) the definition of the function $\tau$ is now based
on that of the arithmetic mean as given by (2) with $p=1$ and
$w_{i}=1/n,i=1,...,n.$

We now formally introduce the family of CFMMs we call the Generalized Mean
Market Makers (G3Ms) by defining their respective trading functions
$\tau=\tau_{p}$ at each $p,0<p\leq 1$, in the following way:

$\tau_{p}(\mbox{\boldmath$\cal{R}$},\mbox{\boldmath$\Delta$},\mbox{\boldmath$\Lambda$})=\left(\sum_{i=1}^{n}w_{i}(R_{i}+\Delta_{i}-\Lambda_{i})^{p}\right)^{\frac{1}{p}}.$
(10)

for any given, fixed set of weights $w_{1},...,w_{n}$, so that $\mu=\mu_{p}$,
where the function $\mu$ is as in (6) and $\mu_{p}$ is as in (2). In addition,
the G3M trading function $\tau=\tau_{0}$ at $p=0$ is defined by

$\tau_{0}(\mbox{\boldmath$\cal{R}$},\mbox{\boldmath$\Delta$},\mbox{\boldmath$\Lambda$})=\Pi_{i=1}^{n}(R_{i}+\Delta_{i}-\Lambda_{i})^{w_{i}}$
(11)

again for any given, fixed set of weights $w_{1},...,w_{n}$, so that, in this
case in (11), $\mu=\mu_{0}$, where $\mu_{0}$ is as in (3).

Hence within the G3M model, for any $p,0<p\leq 1$, equations (7) become

$\left(\sum_{i=1}^{n}w_{i}(R_{i}+\Delta_{i}-\Lambda_{i})^{p}\right)^{\frac{1}{p}}=\left(\sum_{i=1}^{n}w_{i}R_{i}^{p}\right)^{\frac{1}{p}}=C,$
(12)

and, at $p=0,$

$\Pi_{i=1}^{n}(R_{i}+\Delta_{i}-\Lambda_{i})^{w_{i}}=\Pi_{i=1}^{n}R_{i}^{w_{i}}=C.$
(13)

According to [1] and [9], the properties of being concave, nondecreasing,
nonnegative, and differentiable characterize the (multivariate) function $\mu$
in (6) as defining a suitable CFMM trading function $\tau$. Now it is clear
that the function $\mu=\mu_{p,\mbox{\boldmath$w$}}$ as in (2)-(3), for a fixed
set of weights $\mbox{\boldmath$w$}=(w_{1},...,w_{n})$, and any given $p,0\leq
p\leq 1$ is in fact nonnegative and nondecreasing on
$(\mbox{\boldmath$R$}_{+}\cup\\{0\\})^{n}$ (given any reasonable extension to
several variables of the definition of a nondecreaing function, such as that
the function is nondecreasing in any one variable whenever all of the others
are held constant). Next, by a standard result $\mu_{p,\mbox{\boldmath$w$}}$
is also differentiable on $\mbox{\boldmath$R$}_{+}^{n}$ since all of its
(first-order) partial derivatives exist and are continuous.

As for concavity of the function $\mu=\mu_{p,\mbox{\boldmath$w$}}$ for any
fixed set of weights $\mbox{\boldmath$w$}=(w_{1},...,w_{n})$, let’s first
recall the definition of a concave function. A function
$f:D\rightarrow\mbox{\boldmath$R$}$, defined on the convex set
$D\subseteq\mbox{\boldmath$R$}^{n}$ is said to be a concave function if, for
all $t\in[0,1]$ and $\mbox{\boldmath$x$},\mbox{\boldmath$y$}\in D$,

$f((1-t)\mbox{\boldmath$x$}+t\mbox{\boldmath$y$})\geq(1-t)f(\mbox{\boldmath$x$})+tf(\mbox{\boldmath$y$}).$
(14)

The following lemma establishes concavity of the functions
$\mu_{p}=\mu_{p,\mbox{\boldmath$w$}},0\leq p\leq 1.$

Lemma 1. For each $p,0\leq p\leq 1,$ the function
$\mu_{p}=\mu_{p,\mbox{\boldmath$w$}}:(\mbox{\boldmath$R$}_{+}\cup\\{0\\})^{n}\rightarrow\mbox{\boldmath$R$}$
as in (2)-(3) is a concave function for any fixed set of weights
$\mbox{\boldmath$w$}=(w_{1},...,w_{n})$ as in (1).

Proof. First let’s show this for all $p,0<p\leq 1.$ Define, for any
$\mbox{\boldmath$x$}=(x_{1},...,x_{n})\in(\mbox{\boldmath$R$}_{+}\cup\\{0\\})^{n}$

$\overline{\mu}_{p}(\mbox{\boldmath$x$})=\left(\sum_{i=1}^{n}x_{i}^{p}\right)^{\frac{1}{p}}.$
(15)

Since

$\left(\sum_{i=1}^{n}w_{i}x_{i}^{p}\right)^{\frac{1}{p}}=\left(\sum_{i=1}^{n}(w_{i}^{1/p}x_{i})^{p}\right)^{\frac{1}{p}}$
(16)

and

$\overline{\mu}_{p}(t\mbox{\boldmath$x$})=t\overline{\mu}_{p}(\mbox{\boldmath$x$}),\mbox{\rm
for any}\,t\geq 0,$ (17)

it follows that, in order to establish the lemma, we need only prove that

$\overline{\mu}_{p}(\mbox{\boldmath$x$})+\overline{\mu}_{p}(\mbox{\boldmath$y$})\leq\overline{\mu}_{p}(\mbox{\boldmath$x$}+\mbox{\boldmath$y$})$
(18)

for any
$\mbox{\boldmath$x$},\mbox{\boldmath$y$}\in(\mbox{\boldmath$R$}_{+}\cup\\{0\\})^{n}$,
where $\mbox{\boldmath$x$}=(x_{1},...,x_{n})$ and
$\mbox{\boldmath$y$}=(y_{1},...,y_{n}).$ Let $a_{i}=x_{i}^{p},$ and
$b_{i}=y_{i}^{p}$ and raise both sides of (18) to the $p$ power to obtain

$\left(\left(\sum^{n}_{i=1}a_{i}\right)^{1/p}+\left(\sum^{n}_{i=1}b_{i}\right)^{1/p}\right)^{p}\leq\sum^{n}_{i=1}(a^{1/p}_{i}+b^{1/p}_{i})^{p}.$
(19)

But, (19) is equivalent to the following:

$||(\sum^{n}_{i=1}a_{i},\sum^{n}_{i=1}b_{i})||_{1/p}=||\sum^{n}_{i=1}(a_{i},b_{i})||_{1/p}\leq\sum^{n}_{i=1}||(a_{i},b_{i})||_{1/p}.$
(20)

Now note that (20) is clearly true applying the triangle inequality for the
$(1/p)$-norm in order to obtain the inequality in (20), so the lemma for all
$p,0<p\leq 1,$ follows.

Finally we extend our concavity proof for the functions $\mu_{p},0<p\leq 1,$
to the function $\mu_{0}$. For this, assume that $\mu_{0}$ is not concave.
Then there exist vectors
$\mbox{\boldmath$w$},\mbox{\boldmath$x$},\mbox{\boldmath$y$}\in\mbox{\boldmath$R$}^{n}$
as well as $t\in[0,1]$ for which

$\mu_{0}((1-t)\mbox{\boldmath$x$}+t\mbox{\boldmath$y$})<(1-t)\mu_{0}(\mbox{\boldmath$x$})+t\mu_{0}(\mbox{\boldmath$y$}).$
(21)

But by the Key Fact (4) we could choose a $p,0<p\leq 1,$ small enough that
(21) would also imply that

$\mu_{p}((1-t)\mbox{\boldmath$x$}+t\mbox{\boldmath$y$})<(1-t)\mu_{p}(\mbox{\boldmath$x$})+t\mu_{p}(\mbox{\boldmath$y$}).$
(22)

But this violates the concavity of $\mu_{p}$ that we just established above,
completing our proof of the lemma in its entirety. $\Box$

Additionally, according to [1], homogeneity is also a common property of the
function $\mu$ defining the trading function. In fact, we call a function
$f:(\mbox{\boldmath$R$}_{+}\cup\\{0\\})^{n}\rightarrow\mbox{\boldmath$R$}$
homogeneous (of first order) if it satisfies

$f(tx_{1},...,tx_{n})=tf(x_{1},...,x_{n}),\,\,\mbox{\rm for
any}\,\,\mbox{\boldmath$x$}=(x_{1},...,x_{n})\in(\mbox{\boldmath$R$}_{+}\cup\\{0\\})^{n},\,t\in\mbox{\boldmath$R$}_{+}.$
(23)

It is clear from the definition (23) that each function
$\mu_{p,\mbox{\boldmath$w$}},0\leq p\leq 1$, is homogeneous of first order as
well.

###  2.2 Generalized f-Mean Market Makers (Gf3Ms)

We can even generalize the G3M model as described above to the case of CFMMs
characterized by trading functions defined by means of a class of functions
that extends the Generalized Means. This class of functions extending the
Generalized Means is the so-called set of (weighted) Generalized f-Means
(GfMs) (see for example [8]), which are defined by

$M_{f,\mbox{\boldmath$w$}}(\mbox{\boldmath$x$})=f^{-1}(w_{1}f(x_{1})+...+w_{n}f(x_{n}))$

for
$\mbox{\boldmath$x$}=(x_{1},...,x_{n})\in(\mbox{\boldmath$R$}_{+}\cup\\{0\\})^{n}$
and
$\mbox{\boldmath$w$}=(w_{1},...,w_{m})\in(\mbox{\boldmath$R$}_{+}\cup\\{0\\})^{n}$
(with (1) holding as before), as well as a chosen continuous and injective
function $f$ mapping some interval $I\subseteq\mbox{\boldmath$R$}$ into $R$.
Here, in the definition of $M_{f,\mbox{\boldmath$w$}}$ above, “$f^{-1}$”
refers to the inverse function with respect to $f$, so that $f\circ
f^{-1}=f^{-1}\circ f=$Id. The GfMs give rise to a corresponding class of CFMMs
which we call the Generalized f-Mean Market Makers (Gf3Ms), in particular if
$M_{f,\mbox{\boldmath$w$}}$ satisfies the conditions of being concave,
nondecreasing, nonnegative, and differentiable as discussed in §2.1.

The Generalized Means are special cases of the Generalized f-Means, and hence
the G3Ms are special cases of Gf3Ms. Indeed the Generalized Mean at each
$p\in\mbox{\boldmath$R$},p\neq 0$, clearly coincides with the GfM for $f\equiv
x^{p}$, respectively. It is moreover easy to see that the Generalized Mean at
$p=0$ (that is, the geometric mean) coincides with the GfM with
$f\equiv\mbox{\rm log}_{e}(x)$. We note that the Generalized f-Mean is also
called the Quasi-Arithmetic Mean as well as the Kolmogorov Mean in the
literature.

##  3 Balancing Slippage and Trade Size for G3Ms

In this section, we work within the notational and conceptual framework of §2
but specialize to the case of G3Ms for which $n=2,\Lambda_{1}=\Delta_{2}=0$,
and $w_{1}=w_{2}=1/2$. We show – see in particular our Theorem 1 as well as
Remark 1 below – how our G3M models, by taking on intermediate values of $p$
for which $0<p<1,$ can balance slippage (the formal definition of which
follows below) against admissible trade size in such a way that these models
can be superior to both the geometric mean (constant product) and the
arithmetic mean (constant sum) CFMMs with respect to both of these two metrics
(i.e., slippage and admissible trade size) simultaneously. Indeed, we see from
(12) that

$\Delta_{1}=\left(2C^{p}-(R_{2}-\Lambda_{2})^{p}\right)^{1/p}-R_{1}$ (24)

Since $C,R_{1},$ and $R_{2}$ are considered fixed in the CFMM framework and
$0\leq\Lambda_{2}\leq R_{2}$ as well, we see in turn from (24) that, for all
$p,0<p\leq 1,$ the G3M model at $p$ can only support an input trade
$\Delta_{1}$ of bounded size, seriously limiting liquidity of the exchange. On
the other hand, it is clear from the nature of the product operation that the
geometric mean CFMM as in (11) or (13) can support such trades of arbitrary
size (i.e., arbitrarily large value or price), offering a key advantage.
However, as we shall see in Theorem 1 below (and in any case one might already
expect given (4)), the G3M models with $0<p<1$ can also support trades of
arbitrarily large size as $p\rightarrow 0$.

So, in the setting of this section within which we presuppose that
$n=2,\Lambda_{1}=\Delta_{2}=0$, and $w_{1}=w_{2}=1/2$ as stated above, (10)
becomes

$\tau_{p}(\mbox{\boldmath$\cal{R}$},\Delta_{1},\Lambda_{2})=\left(\frac{(R_{1}+\Delta_{1})^{p}}{2}+\frac{(R_{2}-\Lambda_{2})^{p}}{2}\right)^{1/p},$
(25)

for $p,0<p\leq 1,$ and (12) becomes

$\left(\frac{(R_{1}+\Delta_{1})^{p}}{2}+\frac{(R_{2}-\Lambda_{2})^{p}}{2}\right)^{1/p}=\left(\frac{R_{1}^{p}}{2}+\frac{R_{2}^{p}}{2}\right)^{1/p}=C.$
(26)

At $p=0,$ we have

$\tau_{0}(\mbox{\boldmath$\cal{R}$},\Delta_{1},\Lambda_{2})=\sqrt{(R_{1}+\Delta_{1})(R_{2}-\Lambda_{2})},$
(27)

and (13) becomes

$\sqrt{(R_{1}+\Delta_{1})(R_{2}-\Lambda_{2})}=\sqrt{R_{1}R_{2}}=C.$ (28)

Now, following [9], define the spot exchange rate with respect to the trading
function $\tau=\tau_{p},0\leq p\leq 1,$ via

$E_{p}=E_{p,12}=E_{p,12}(\mbox{\boldmath$\cal{R}$},0,0)=\frac{\frac{\partial\tau_{p}}{\partial
R_{2}}(\mbox{\boldmath$\cal{R}$},0,0)}{\frac{\partial\tau_{p}}{\partial
R_{1}}(\mbox{\boldmath$\cal{R}$},0,0)}.$ (29)

We then define, again following [9], the slippage – with respect to the
variables $\Delta_{1}$ and $\Lambda_{2}$ – as

$S_{p}=S_{p,12}=\frac{\Delta_{1}}{\Lambda_{2}}E_{p}^{-1}-1,$ (30)

for $p,0\leq p\leq 1$ (provided of course $|E_{p}|>0$). So, at $p=0$, we can
calculate that

$S_{0}=\frac{R_{2}}{R_{1}}\frac{\Delta_{1}}{\Lambda_{2}}-1.$ (31)

Hence, considering (28) as well,

$S_{0}=\frac{\left(\frac{C^{2}}{(R_{2}-\Lambda_{2})}-R_{1}\right)}{\Lambda_{2}}\frac{R_{2}}{R_{1}}-1$
(32)

For $p,0<p\leq 1,$ we have

$\displaystyle S_{p}$ $\displaystyle=$
$\displaystyle\frac{R_{1}^{p-1}}{R_{2}^{p-1}}\frac{\Delta_{1}}{\Lambda_{2}}-1$
(33) $\displaystyle=$
$\displaystyle\frac{R_{1}^{p-1}}{R_{2}^{p-1}}\frac{(2C^{p}-(R_{2}-\Lambda_{2})^{p})^{1/p}-R_{1}}{\Lambda_{2}}-1$

In the rest of the paper, we will often write

$\epsilon=R_{2}-\Lambda_{2}.$ (34)

That is,

$\Lambda_{2}=\Lambda_{2}(\epsilon)=R_{2}-\epsilon>0.$ (35)

for any $\epsilon,0<\epsilon<R_{2}$. We think of the most interesting cases in
this context to be the ones for which $\epsilon>0$ is small, which enables, by
(24), the corresponding quantity $R_{1}+\Delta_{1}=R_{1}+\Delta_{1}(\epsilon)$
and hence also the quantity $\Delta_{1}=\Delta_{1}(\epsilon)$ to be large (or
at least relatively large), where $\Delta_{1}=\Delta_{1}(\epsilon)$ satisfies

$\left(\frac{(R_{1}+\Delta_{1}(\epsilon))^{p}}{2}+\frac{\epsilon^{p}}{2}\right)^{1/p}=C$
(36)

for given $p,0<p\leq 1$. That is, for this range of $p$,

$\Delta_{1}(\epsilon)=(2C^{p}-\epsilon^{p})^{1/p}-R_{1}.$ (37)

So, with these definitions we can rewrite (32) and (33) in the form:

$\displaystyle S_{0}=S_{0}(\epsilon)$ $\displaystyle=$
$\displaystyle\frac{\left(\frac{C^{2}}{\epsilon}-R_{1}\right)}{\Lambda_{2}(\epsilon)}\frac{R_{2}}{R_{1}}-1$
(38) $\displaystyle S_{p}=S_{p}(\epsilon)$ $\displaystyle=$
$\displaystyle\frac{R_{1}^{p-1}}{R_{2}^{p-1}}\frac{(2C^{p}-\epsilon^{p})^{1/p}-R_{1}}{\Lambda_{2}(\epsilon)}-1.$
(39)

Note that, at $p=1$, we must have $\Delta_{1}=\Lambda_{2}$, so it is easy to
see from (39) that $S_{1}=0$.

Before stating Theorem 1, we recall that a function
$f:\mbox{\boldmath$R$}_{+}\rightarrow\mbox{\boldmath$R$}$ is $f(t)=O(g(t))$
for $t\rightarrow 0$ for some function
$g:\mbox{\boldmath$R$}_{+}\rightarrow\mbox{\boldmath$R$}_{+}$ if there exist
numbers $k>0$ and $t_{0}>0$ for which $|f(t)|\leq kg(t)$ for all $t,0<t\leq
t_{0}$. Furthermore, we say that a function
$f:\mbox{\boldmath$R$}_{+}\rightarrow\mbox{\boldmath$R$}$ is
$f(t)=\Omega(g(t))$ for $t\rightarrow 0$ for some function
$g:\mbox{\boldmath$R$}_{+}\rightarrow\mbox{\boldmath$R$}_{+}$ if there exist
numbers $k>0$ and $t_{0}>0$ for which $|f(t)|\geq kg(t)$ for all $t,0<t\leq
t_{0}$.

Theorem 1. Suppose that $C$ is such that $2<C<\infty$, and, define, for any
desired $s,1<s<\frac{C}{2}$, the function
$p:(0,1)\rightarrow\mbox{\boldmath$R$}_{+}$ via

$p(\epsilon)=p_{s}(\epsilon)=\frac{\mbox{\rm log}(s+\sqrt{s^{2}-s})}{\mbox{\rm
log}\left(\frac{C}{\epsilon}\right)}\in(0,1]\,\,\,\mbox{\rm
for}\,\,\,0<\epsilon<1.$ (40)

Then, we have, with the slippage $S_{p}(\epsilon)=S_{p(\epsilon)}(\epsilon)$
at $p=p(\epsilon)$ defined as in (39),

$|S_{p(\epsilon)}(\epsilon)|=O(\epsilon^{-c})$ (41)

as $\epsilon\rightarrow 0$, where $c$ satisfies $0<c<1$ and we can in fact
take

$c=c(s)=1-\frac{\mbox{\rm log}(s)}{\mbox{\rm log}(s+\sqrt{s^{2}-s})}.$ (42)

Moreover, defining $\Delta_{1}=\Delta_{1}(\epsilon)$ as in (37) with
$p=p(\epsilon)$ there defined once again as in (40), we have

$\Delta_{1}(\epsilon)=\Omega(\epsilon^{-c})$ (43)

as $\epsilon\rightarrow 0$, where, in (43), c=c(s) is defined once again as in
(42) above.

Remark 1. Before we move on to the proof of Theorem 1, we note that, with
slippage $S_{0}(\epsilon)$ at $p=0$ defined as in (38), we have from (38) that

$|S_{0}(\epsilon)|=\Omega(\epsilon^{-1}).$ (44)

as $\epsilon\rightarrow 0$. Hence, based on (41), the intermediate G3M models
with $p=p_{s}(\epsilon)$, for any $s,1<s<\frac{C}{2},$ are seen to offer
superior slippage properties in this case as $\epsilon\rightarrow 0$ relative
to the G3M model in this setting at $p=0$ (that is, the Constant
Product/Geometric Mean CFMM). Meanwhile, (43) implies that, furthermore, these
intermediate G3M models with $p=p_{s}(\epsilon)$ as $\epsilon\rightarrow 0$
support aribitrarily large trade sizes also as $\epsilon\rightarrow 0$, making
them superior as well in this respect to the G3M model at $p=1$ (that is, the
Constant Sum/Arithmetic Mean CFMM).

Proof of Theorem 1. Given $s,1<s<\frac{C}{2},$ as in the theorem’s statement,
to establish the theorem we will determine $p,0<p\leq 1,$ for which

$(2C^{p}-\epsilon^{p})^{1/p}=\frac{C^{2}}{s^{1/p}\epsilon}.$ (45)

Hence we want to solve

$2C^{p}-\epsilon^{p}=\frac{C^{2p}}{s\epsilon^{p}}.$ (46)

That is, we want to solve

$x^{2}-2sx+s=0,$ (47)

where $x=\frac{C^{p}}{\epsilon^{p}}$, So, solving the quadratic equation (47)
for $x$, we obtain

$x=s\pm\sqrt{s^{2}-s}.$ (48)

Hence if we choose $p>0$ such that

$\frac{C^{p}}{\epsilon^{p}}=x=s+\sqrt{s^{2}-s},$ (49)

then (46) will be satisfied. So, we can take $p=p(\epsilon)$ to be

$p=p(\epsilon)=\frac{\mbox{\rm log}(x)}{\mbox{\rm
log}(\frac{C}{\epsilon})}=\frac{\mbox{\rm log}(s+\sqrt{s^{2}-s})}{\mbox{\rm
log}(\frac{C}{\epsilon})}$ (50)

and then (45) will be satisfied for $p=p(\epsilon)$ as in (50). So, from (45),
we get

$\displaystyle(2C^{p}-\epsilon^{p})^{1/p}$ $\displaystyle=$
$\displaystyle\frac{C^{2}}{s^{1/p}\epsilon}$ (51) $\displaystyle=$
$\displaystyle\frac{C^{2}}{\left(s^{\frac{\mbox{\rm
log}(\frac{C}{\epsilon})}{\mbox{\rm log}(s+\sqrt{s^{2}-s})}}\right)\epsilon}$
$\displaystyle=$
$\displaystyle\frac{C^{2}}{\left((\frac{C}{\epsilon})^{\frac{\mbox{\rm
log}(s)}{\mbox{\rm log}(s+\sqrt{s^{2}-s})}}\right)\epsilon^{\frac{\mbox{\rm
log}(s+\sqrt{s^{2}-s})}{\mbox{\rm log}(s+\sqrt{s^{2}-s})}}}$ $\displaystyle=$
$\displaystyle\frac{C^{(2-\mbox{log}(s))}}{\epsilon^{\left(1-\frac{\mbox{\rm
log}(s)}{\mbox{\rm log}(s+\sqrt{s^{2}-s})}\right)}},$

for any desired $s$ as in the statement of the theorem. This establishes (43).
Finally, (41) follows directly from (51) as well since, writing
$R_{2}/R_{1}=R$, it is the case that, for fixed $s$,

$R^{p(\epsilon)-1}=O(1).$ (52)

as $\epsilon\rightarrow 0$. $\Box$

References

[1] Angeris, G. Agrawal, A., Evans, A., Chitra, T., and Boyd, S. (2021)
Constant function market makers: Multi-asset trades via convex optimization.
arXiv preprint arXiv:2107.12484.

[2] Angeris, G. and Chitra, T. (2020) Improved price oracles: Constant
function market makers. In it Proceedings of the 2nd ACM Conference on
Advances in Financial Technologies,80–91.

[3] Angeris, G., Kao, H.T., Chiang, R., Noyes, C., and Chitra, T. (2019) An
analysis of Uniswap markets. arXiv preprint arXiv:1911.03380.

[4] Berger, R. and Casella, G. (1992) Deriving Generalized Means as Least
Squares and Maximum Likelihood Estimates The American Statistician,Vol. 46,
No. 4, pp. 279-282.

[5] Karlin, M., Zanger, D., and Katz, A. (2021) (US patent filing) U.S. App.
No. 17/818,847, “Systems and Methods for Automated Staking Models” as
originally-filed as U.S. Provisional App. No. 63/283,885 (November 29, 2021).

[6] Krishnamachari, B., Feng, Q., and Grippo, E. (2021) Dynamic Curves for
Decentralized Autonomous Cryptocurrency Exchanges. arXiv preprint
arXiv:2101.02778

[7] Martinelli, F. and Mushegian, N. (2019) Balancer: A non-custodial
portfolio manager, liquidity provider, and price sensor.

[8] Matkowski, J. and Pales, Z. (2015) Characterization of generalized quasi-
arithmetic means. Acta Scientiarum Mathematicarum, 81(3-4):447–456.

[9] Xu, J., Paruch, K., Cousaert, S., and Feng, Y. (2021) “SoK: Decentralized
Exchanges (DEX) with Automated Market Maker (AMM) protocols.”
http://arxiv.org/abs/2103.12732