# Nearest Neighbor Non-autoregressive Text Generation

Ayana Niwa Sho Takase Naoaki Okazaki
Tokyo Institute of Technology
<EMAIL_ADDRESS><EMAIL_ADDRESS>okazaki@} c.titech.ac.jp

###### Abstract

Non-autoregressive (NAR) models can generate sentences with less computation
than autoregressive models but sacrifice generation quality. Previous studies
addressed this issue through iterative decoding. This study proposes using
nearest neighbors as the initial state of an NAR decoder and editing them
iteratively. We present a novel training strategy to learn the edit operations
on neighbors to improve NAR text generation. Experimental results show that
the proposed method (NeighborEdit) achieves higher translation quality (1.69
points higher than the vanilla Transformer) with fewer decoding iterations
(one-eighteenth fewer iterations) on the JRC-Acquis En-De dataset, the common
benchmark dataset for machine translation using nearest neighbors. We also
confirm the effectiveness of the proposed method on a data-to-text task
(WikiBio). In addition, the proposed method outperforms an NAR baseline on the
WMT’14 En-De dataset. We also report analysis on neighbor examples used in the
proposed method.

##  1 Introduction

Non-autoregressive (NAR) models have gained popularity lately Gu et al.
(2018a); Ghazvininejad et al. (2019); Lee et al. (2020); Qian et al. (2021).
Autoregressive (AR) generation models Sutskever et al. (2014) need to iterate
computations of forward propagation from the input to output layers of the
decoder multiple times for all generated tokens, whereas NAR models predict
multiple tokens simultaneously. Hence, NAR decoding is faster as only one
forward propagation computation is required. However, due to the inherent
difficulty in capturing the dependencies between generated tokens, the
generation quality of NAR models is worse than that of AR models.

The primary solution to this problem is to repeat decoding processes including
edit operations, e.g., token substitution Ghazvininejad et al. (2019); Qian et
al. (2021), insertion Stern et al. (2019a), and deletion/insertion Gu et al.
(2019). Repeating generation processes decreases the dependencies between
output tokens by learning the conditional distribution over the generated
tokens Gu and Kong (2021). However, during the inference, the decoder must
start the generation from scratch (or special tokens), which leads to a low-
quality sentence generated in the first iteration. Moreover, Huang et al.
(2022) have demonstrated that if the initial sentence generated is of low
quality, it is difficult to recover even after several iterations. Therefore,
it is preferable to begin the generation process with a high-quality sentence
to improve performance.

Therefore, this paper proposes using the _nearest neighbor_ as the initial
state of the NAR decoder. The proposed method, NeighborEdit, retrieves the
nearest neighbor of an input sentence and edits it to generate the output
sentence. Thus, NeighborEdit can start the generation with a sentence that is
close to that of the output. As generating from a neighbor example is easier
than generating from scratch, we anticipate an improved generation quality
with fewer iterations. Consider the following example where the English
sentence “I have an apple.” is translated into the German sentence “Ich habe
einen Apfel.” NeighborEdit first retrieves the nearest neighbor of the English
sentence from the training data, “I have a banana. – Ich habe eine Banane.”
The method then starts with the retrieved German sentence, deletes the words
‘eine’ and ‘Banane’ and inserts the words ‘einen’ and ‘Apfel,’ to complete the
translation.

Traditionally, nearest neighbors have been utilized in various tasks,
including part-of-speech tagging Daelemans et al. (1996) and example-based
machine translation Nagao (1984). Recently, nearest neighbors have been
successfully applied to AR models, particularly to neural machine translation
Gu et al. (2018b); Xu et al. (2020); Khandelwal et al. (2021), text
summarization Cao et al. (2018); Peng et al. (2019), and data-to-text
generation Wiseman et al. (2021). We adapt the pioneering idea to refine and
improve NAR models.

NeighborEdit is regarded as one of the edit-based NAR models that have been
actively studied in recent years. In reality, it is not always possible to
retrieve a neighbor close to the output sentence, and learning and applying
editing operations to a distant sentence can be challenging. Therefore, we
also propose a training strategy based on the lexical difference between the
neighbor and the output sentences by mixing two policies, neighbor- and
target-centric policies (described in Section 3.1.1). For the base
architecture, we adopt the Levenshtein transformer Gu et al. (2019), which
permits two edit operations on input sentences: token deletion and token
insertion. This model does not require that the output length be fixed,
whereas most NAR models require that the output length be predicted.

Experimental results show that the proposed method (NeighborEdit) achieves
higher translation quality (1.69 points higher than the vanilla Transformer)
with fewer decoding iterations (one-eighteenth fewer iterations) on the JRC-
Acquis En-De dataset, the common benchmark dataset for machine translation
using nearest neighbors. We also confirm the effectiveness of the proposed
method on a data-to-text task (WikiBio). In addition, the proposed method
outperforms an NAR baseline on the WMT’14 En-De dataset. Lastly, we report
analysis on neighbor examples utilized by the proposed method.

##  2 Problem Formulation and Preliminary

Figure 1: An illustration of our proposed method in the machine translation
(MT) task. When translating the English sentence, “Procedures for the
implementation of humanitarian operations” to the German sentence, “Verfahren
für die Durchführung der humanitären Aktionen,” we set the neighbor “Zeitplan
für die Durchführung der Aktionen (Schedule for implementation of measures)”
as the initial state of the decoder and repeat the edit operations.

We consider a translation task for simplicity. A target sentence $\bm{y}^{*}$
is generated from a source sentence $\bm{x}$ and a neighbor example
$\bm{z}_{0}$. Here, we find the sentence $\bm{x}^{\prime}$ that is closest to
the source sentence $\bm{x}$ in the datastore, and let $\bm{z}_{0}$ be the
target sentence paired with $\bm{x}^{\prime}$.

###  2.1 Problem Formulation

We train the model using imitation learning, a type of reinforcement learning,
to mimic the sequence of actions of an expert. We cast the sequence generation
task as a Markov Decision Process defined by the tuple
$(\mathcal{Y},\mathcal{A},\mathcal{E},\mathcal{R},\bm{z}_{0})$. Here,
$\bm{y}\in\mathcal{Y}$ is a partially constructed sequence during the decoding
process, which we refer to as a canvas Stern et al. (2019b); Wiseman et al.
(2021). $\mathcal{A}$ is a set of actions (edit operations), $\mathcal{E}$ is
the environment that receives a canvas $\bm{y}$ and action $\bm{a}$ and yields
an edited sequence, and $\mathcal{R}$ is a reward function.

At the $k$-th iteration of decoding, the model receives canvas $\bm{y}^{k-1}$
(of $n+1$ tokens)111$y_{0}=\mbox{\tt<s>}$ and $y_{n}=\mbox{\tt</s>}$, which
represent the beginning and end of a sequence. The value $n$ may change during
the iteration process via token deletion and insertion. edited at the previous
iteration. The model then selects the action $\bm{a}^{k}$ to generate a new
canvas $\bm{y}^{k}=\mathcal{E}(\bm{y}^{k-1},\bm{a}^{k})$ (of $n+1$ tokens) and
obtains the reward $r^{k}=\mathcal{R}(\bm{y}^{k})$. The policy $\pi$ to select
the action $\bm{a}^{k}$ is defined as the mapping from the decoder output
$(\bm{h}_{0},\bm{h}_{1},...,\bm{h}_{n})$ for the input canvas $\bm{y}^{k-1}$
into action space $\mathcal{A}$. Generally, the policy $\pi$ is approximated
by linear classifiers with parameter $\theta$.

###  2.2 Recap: Levenshtein Transformer

NeighborEdit adopts Levenshtein Transformer Gu et al. (2019), an edit-based
non-autoregressive encoder-decoder model, as the base architecture. More
specifically, policy $\pi$ consists of three parts: (1) token deletion
classifier $\pi_{\theta}^{\mathrm{del}}$, (2) placeholder ([PLH]) insertion
classifier $\pi_{\theta}^{\mathrm{plh}}$, and (3) token classifier
$\pi_{\theta}^{\mathrm{tok}}$.

####  2.2.1 Policy Classifier

(1) Deletion classifier $\pi_{\theta}^{\mathrm{del}}$ predicts whether each
token $y_{i}$ ($i\in\\{1,\dots,n-1\\}$) should be deleted ($d_{i}=0$) or kept
($d_{i}=1$) as a binary classification.

$\displaystyle\pi_{\theta}^{\mathrm{del}}(d_{i}|i,\bm{y})=\mathrm{softmax}(\bm{h}_{i}\bm{A})$
(1) $\displaystyle\bm{A}\in\mathbb{R}^{d_{\mathrm{model}}\times 2},\;\forall
i:i\in\\{1,..,n-1\\}$

(2) Placeholder insertion classifier $\pi_{\theta}^{\mathrm{plh}}$ predicts
the number of placeholders ([PLH]) to be inserted
$p_{i}\in\\{0,\dots,K_{\mathrm{max}}\\}$ at every consecutive pair of
positions. When $p_{i}=0$, the model inserts no placeholder between $y_{i}$
and $y_{i+1}$.

$\displaystyle\pi_{\theta}^{\mathrm{plh}}(p_{i}|i,\bm{y})=\mathrm{softmax}([\bm{h}_{i};\bm{h}_{i+1}])\bm{B})$
(2)
$\displaystyle\bm{B}\in\mathbb{R}^{(2d_{\mathrm{model}})\times(K_{\mathrm{max}}+1)},\;\forall
i:i\in\\{0,..,n-1\\}$

Here, $[\bm{a};\bm{b}]$ represents a concatenation of the vectors ${\bm{a}}$
and ${\bm{b}}$.

(3) Token classifier $\pi_{\theta}^{\mathrm{tok}}$ predicts a token $t_{i}$
for filling the placeholder [PLH].

$\displaystyle\pi_{\theta}^{\mathrm{tok}}(t|i,\bm{y})=\mathrm{softmax}(\bm{h}_{i}\bm{C}),$
(3)
$\displaystyle\bm{C}\in\mathbb{R}^{d_{\mathrm{model}}\times|\mathcal{V}|}\;\forall
i:y_{i}=\texttt{[PLH]}$

In total, the policy classifier has the parameter
$\theta=(\bm{A},\bm{B},\bm{C})$. The model receives the canvas $\bm{y}$ and
performs three edit operations in the following order: (1) token deletion
$d_{i}\;(i\in\\{0,...,n\\})$, (2) placeholder insertion
$p_{i}\;(i\in\\{0,...,n-1\\})$, and (3) token insertion $t_{i}\;(\forall
i:y_{i}=\texttt{[PLH]})$.

####  2.2.2 Training

We train the model parameters by minimizing the sum of deletion
$\mathcal{L}_{\theta}^{\mathrm{del}}$ and insertion
$\mathcal{L}_{\theta}^{\mathrm{ins}}$ losses.

$\displaystyle\mathcal{L}=$
$\displaystyle\mathcal{L}_{\theta}^{\mathrm{del}}+\mathcal{L}_{\theta}^{\mathrm{ins}}$
(4) $\displaystyle\mathcal{L}_{\theta}^{\mathrm{del}}=$
$\displaystyle-\sum_{y^{i}\in\bm{y}_{\mathrm{del}},\;d_{i}^{*}\sim\bm{d}^{*}}\mathrm{log}\pi_{\theta}^{\mathrm{del}}(d_{i}^{*}|i,\bm{y}_{\mathrm{del}})$
(5) $\displaystyle\mathcal{L}_{\theta}^{\mathrm{ins}}=$
$\displaystyle-\sum_{y^{i}\in\bm{y}_{\mathrm{ins}},\;p^{*}_{i}\in\bm{p}^{*}}\mathrm{log}\pi_{\theta}^{\mathrm{plh}}(p_{i}^{*}|i,\bm{y}_{\mathrm{ins}})$
$\displaystyle-\sum_{t^{*}_{i}\in\bm{t}^{*}}\mathrm{log}\pi_{\theta}^{\mathrm{tok}}(t_{i}^{*}|i,\bm{y}^{\prime}_{\mathrm{ins}})$
(6)

Here, $\bm{y}_{\mathrm{ins}}$ and $\bm{y}_{\mathrm{del}}$ are the canvases of
the insertion target and deletion target, respectively. Also,
$\bm{y}^{\prime}_{\mathrm{ins}}$ represents the canvas after inserting [PLH]
to $\bm{y}_{\mathrm{ins}}$. The expert operations
$\bm{a}^{*}\in\\{\bm{d}^{*},\bm{p}^{*},\bm{t}^{*}\\}$ are chosen to minimize
the Levenshtein distance $\mathcal{D}$ Levenshtein et al. (1966) between
expert $\bm{e}$ and edited canvas $\mathcal{E}(\bm{y},\bm{a})$.

$\displaystyle\bm{d}^{*}$
$\displaystyle=\operatorname*{arg\,min}_{\bm{d}}\mathcal{D}(\bm{e},\mathcal{E}(\bm{y}_{\mathrm{del}},\bm{d}))$
(7) $\displaystyle\bm{p}^{*},\bm{t}^{*}$
$\displaystyle=\operatorname*{arg\,min}_{\bm{p},\bm{t}}\mathcal{D}(\bm{e},\mathcal{E}(\bm{y}_{\mathrm{ins}},\\{\bm{p},\bm{t}\\})$
(8)

Please refer to Gu et al. (2019) for more details of Levenshtein Transformer.

##  3 Proposed Method

As shown in Figure 1, the proposed method first retrieves the nearest
neighbors from the datastore consisting of all parallel sentences in the
training set (Section 3.2). The method then generates a sentence by deleting
and inserting tokens on the retrieved neighbor (Section 3.1).

###  3.1 Edit Operations on Neighbors

NeighborEdit is an NAR model based on Transformer Vaswani et al. (2017). Given
the source sentence $\bm{x}$ as the input and a retrieved neighbor
$\bm{z}_{0}$ as _the initial state of the decoder_ , the proposed model edits
the neighbor by deleting and inserting tokens repeatedly. We focus on
incorporating the retrieved neighbors $\bm{z}_{0}$ into the decoding process.

####  3.1.1 Oracle Policy for NeighborEdit

During imitation learning, the model learns the parameterized policy
$\pi_{\theta}$ to mimic the actions of an oracle policy $\pi^{*}$. We designed
a novel strategy to obtain an oracle policy to edit the neighbor $\bm{z}_{0}$
to a target sentence effectively.

The basic idea of the policy is to reproduce the edit operations on the
intermediate sequence that appears in the iteration during inference (the
partially edited neighbor). Therefore, our policy focuses on the lexical
difference between a neighbor and target sentence. However, if their
similarity is too low, it is necessary to rewrite a sentence into a completely
different sentence. The policy of complete rewriting is too difficult to
learn. To alleviate this issue, we design a policy by mixing the neighbor-
centric policy $\pi^{*}_{\mathrm{n}}$ and target-centric policy
$\pi^{*}_{\mathrm{t}}$. The former utilizes the lexical similarity and
difference between the neighbor $\bm{z}_{0}$ and the target sentence
$\bm{y}^{*}$, whereas the latter uses the target sentence $\bm{y}^{*}$ only.
During training, the model randomly chooses $\pi^{*}_{\mathrm{n}}$ or
$\pi^{*}_{\mathrm{t}}$ for each batch. Furthermore, when the similarity
between the neighbor and target sentence $\mathrm{sim}(\bm{z}_{0},\bm{y}^{*})$
is less than a threshold $\beta$, the policy $\pi^{*}_{\mathrm{n}}$ for the
insertion switches to the $\pi^{*}_{\mathrm{t}}$ for each instance222We do not
set a threshold for the deletion in the $\pi^{*}_{\mathrm{n}}$ because the
model is sure to remove unnecessary tokens from neighbors during inference..
In summary, our policy $\pi^{*}$ mixies the policies $\pi^{*}_{\mathrm{n}}$
and $\pi^{*}_{\mathrm{t}}$ as follows:

$\displaystyle\pi^{*}$ $\displaystyle=(\pi^{*}\text{for
deletion},\pi^{*}\text{for insertion})$ (9)
$\displaystyle=\left\\{\begin{array}[]{ll}(\pi^{*}_{\mathrm{n}},\pi^{*}_{\mathrm{n}})&(u<\alpha\wedge\mathrm{sim}(\bm{z}_{0},\bm{y}^{*})>\beta)\\\
(\pi^{*}_{\mathrm{n}},\pi^{*}_{\mathrm{t}})&(u<\alpha\wedge\mathrm{sim}(\bm{z}_{0},\bm{y}^{*})\leq\beta)\\\
(\pi^{*}_{\mathrm{t}},\pi^{*}_{\mathrm{t}})&(\text{otherwise}),\end{array}\right.$
(13)

where $\alpha\in[0,1]$ is a hyperparameter and $u$ is a value sampled from the
uniform distribution of $[0,1]$. Here, we define
$\mathrm{sim}(\bm{z}_{0},\bm{y}^{*})$ as the token overlap ratio, the number
of overlapped tokens divided by the number of tokens in the neighbor.

By the above training strategy, our policy enables the model to delete
unfavorable tokens from the nearest neighbor and insert necessary tokens.
Given a canvas $\bm{y}$, we define the oracle policy $\pi^{*}$ to generate
expert $\bm{e}$ as follows.

##### Deletion: $\pi^{*}(\bm{y}_{\mathrm{del}})$

This edit operation removes unnecessary tokens from the canvas
$\bm{y}_{\mathrm{del}}$. It is essential to delete all unnecessary tokens from
the retrieved neighbor $\bm{z}_{0}$. Furthermore, unnecessary tokens that the
model inserted in the previous iteration need to be removed. Hence, we train
the model to delete tokens from $\bm{z}_{0}$ that do not appear in the target
sentence $\bm{y}^{*}$ or unnecessarily inserted tokens from
$\mathcal{E}(\bm{y}^{{}^{\prime}},(\tilde{p},\tilde{t}))$.

$\displaystyle\pi^{*}_{\mathrm{n}}(\bm{z}_{0})=\mathrm{M}(\bm{y}^{*},\bm{z}_{0})$
(14)
$\displaystyle\pi^{*}_{\mathrm{t}}(\mathcal{E}(\bm{y}^{{}^{\prime}},(\tilde{p},\tilde{t})))=\mathrm{M}(\bm{y}^{*},\bm{y}_{\mathrm{del}})$
(15)
$\displaystyle\quad\tilde{p}\sim\pi_{\theta}^{\mathrm{plh}},\tilde{t}\sim\pi_{\theta}^{\mathrm{tok}}$

The function $\mathrm{M}(\bm{a},\bm{b})$ yields the common token subsequence
between $\bm{a}$ and $\bm{b}$. For example, $\mathrm{M}$(“ABCDE,” “ARE”)
returns “AE.”

##### Insertion: $\pi^{*}(\bm{y}_{\mathrm{ins}})$

This operation inserts necessary tokens into the canvas
$\bm{y}_{\mathrm{ins}}$ to generate $\bm{y}^{*}$.

$\displaystyle\pi^{*}_{\mathrm{n}}(\mathrm{M}(\bm{y}^{*},\mathcal{E}(\bm{z}_{0},\tilde{d})))=\bm{y}^{*}\;\tilde{d}\sim\pi_{\theta}^{\mathrm{del}}$
(16)
$\displaystyle\pi^{*}_{\mathrm{t}}(\mathcal{E}(\bm{y}^{*},\tilde{d}))=\bm{y}^{*}\;\tilde{d}\sim\pi^{\mathrm{RND}}$
(17)

Here, $\pi^{\mathrm{RND}}$ is a policy of random token deletion.
$\mathcal{E}(\bm{y}^{*},\tilde{d})$ presents a target sequence with some
tokens deleted at random (based on $\pi^{\mathrm{RND}}$). The intention of
$\mathrm{M}(\bm{y}^{*},\mathcal{E}(\bm{z}_{0},\tilde{d}))$ is to delete tokens
in the nearest neighbor based on the policy of $\pi_{\theta}^{\mathrm{del}}$
and insert necessary tokens that appear in $\bm{y}^{*}$ but not in the deleted
sequence.

####  3.1.2 Inference

The model receives the initial state (neighbors) and generates a sentence by
repeatedly selecting and applying the most probable edit operation to the
canvas $\bm{y}$. We terminate the process when we reach the maximum number of
iterations or when the output sequences from two consecutive iterations are
identical.

However, the initial state may hurt the performance if no close example exists
in the datastore. Therefore, this study employs a switching approach as well
as the oracle policy. Specifically, if the similarity of the neighbor on the
source side $\mathrm{sim}(\bm{z}_{0},\bm{x})$ is less than the threshold
$\beta$ (used in Equation (13)), we do not initialize the decoder with the
neighbors but do with special tokens <s></s> instead, similarly to common NAR
models.

###  3.2 Neighbor Retrieval

To obtain the nearest neighbor $\bm{z}_{0}$, we retrieve the most similar
example to a given input sentence from the datastore. The datastore contains
all the parallel sentences in the training data. Existing retrieval methods
for nearest neighbors can be divided into two major types: lexical matching Xu
et al. (2020); Gu et al. (2018b); Bulte and Tezcan (2019) and distributional
similarity Khandelwal et al. (2021); Borgeaud et al. (2021).

##### Lexical matching

Previous studies explored fuzzy matching and n-gram matching Xu et al. (2020);
Gu et al. (2018b); Bulte and Tezcan (2019). This study uses token frequencies,
as in Peng et al. (2019), because this method scales well with large amounts
of data. Specifically, we define a similarity score $S_{\mathrm{TFIDF}}$ for
sentences $s_{i}$ and $s_{j}$ using the cosine similarity of the TFIDF vector
$\text{tfidf}(\cdot)$.

$\displaystyle
S_{\mathrm{TFIDF}}(s_{i},s_{j})=\frac{\text{tfidf}(s_{i})\cdot\text{tfidf}(s_{j})}{\|\text{tfidf}(s_{i})\|\|\text{tfidf}(s_{j})\|}$
(18)

##### Distributional similarity

We use the cosine similarity $S_{\mathrm{SentVec}}$ of the sentence vector
extracted from an off-the-shelf encoder.

$\displaystyle
S_{\mathrm{SentVec}}(s_{i},s_{j})=\frac{\bm{h_{i}}\cdot\bm{h_{j}}}{\|\bm{h_{i}}\|\|\bm{h_{j}}\|}$
(19)

Here, $\bm{h}_{i}$ and $\bm{h}_{j}$ are the sentence vectors obtained by
encoding the sentences $s_{i}$ and $s_{j}$, respectively. Since the proposed
method edits neighbor examples at word level, it is preferable that a neighbor
example has common words with a target sentence. Therefore, we retrieve $k$
candidate neighbors based on $S_{\mathrm{SentVec}}$, and rerank the $k$
candidates by using the lexical matching with
$S_{\mathrm{TFIDF}}(s_{i},s_{j})$.

##  4 Experiment

###  4.1 Experimental Settings

##### Dataset

We used the JRC-Acquis English-German dataset333https://opus.nlpl.eu/JRC-
Acquis.php, which is a corpus of legal documents. Because the corpus includes
quite a few semantically similar sentences, many previous studies utilizing
nearest neighbors regard this corpus as the standard benchmark dataset Li et
al. (2016); Gu et al. (2018b); Xu et al. (2020); Cai et al. (2021). In this
experiment, we preprocessed the data after excluding duplicate translation
pairs, following Gu et al. (2018b).

##### Models

We used Transformer Vaswani et al. (2017) (base setting) as the strong AR
baseline (AR). For the NAR baselines, we adopted Levenshtein Transformer Gu et
al. (2019) (LevenshteinT), GLAT+CTC Qian et al. (2021), NAT-ITR Lee et al.
(2018), NAT-CRF Sun et al. (2019), and CMLM Ghazvininejad et al. (2019). We
used a beam size of four during inference for the AR model. Implementing these
models using fairseq Ott et al. (2019)444https://github.com/pytorch/fairseq,
we trained them with a maximum of 100,000 steps and a total batch size of
approximately 32,768 tokens per step.

##### Neighbor retrieval

We used TFIDF and SentVec+TFIDF ($k$=50) to retrieve neighbors from the
datastore and chose the closest sentence for each input sentence. The encoder
of SentVec+TFIDF is the SBERT model pre-trained on multilingual
corpora555https://huggingface.co/sentence-transformers/distiluse-base-
multilingual-cased-v1 Reimers and Gurevych (2019), which performs well in
information retrieval tasks. We used
faiss666https://github.com/facebookresearch/faiss, a fast library for nearest-
neighbor retrieval.

##### Evaluation

We assessed the quality of the generated sentences using a case-sensitive
detokenized BLEU using SacreBLEU Post (2018) and ChrF Popović (2015). We also
calculated the mean number of iterations and the mean time required to
translate a sentence. The latter measured the mean latency while the model
generated a sequence using a single batch and a single Tesla P100 GPU, similar
to Xu and Carpuat (2021). Latency includes the time for nearest-neighbor
retrieval (for NeighborEdit).

A more detailed description can be found in the Appendix.

###  4.2 Experimental Result

We presented the main results on generation quality and decoding speed in
Table 1 and the translation example in Appendix A.6.

| Model | Initial state | BLEU | ChrF | Number of | Latency [ms]
---|---|---|---|---|---|---
| of decoder | iterations | (retrieval time)
AR | Transformer | [BOS] | 53.90 | 72.51 | 30.69 | 300.8 |
NAR | GLAT+CTC | $\mathrm{Encoder}(\bm{x})$ | 46.75 | 66.53 | 1.00 | 19.8 |
| NAT-ITR | $\bm{x}$ | 38.53 | 60.71 | 3.57 | 46.7 |
| NAT-CRF | $\texttt{[PAD]},...,\texttt{[PAD]},\texttt{[EOS]}$ | 26.94 | 50.39 | 3.25 | 64.7 |
| CMLM | $\texttt{[MASK]},...,\texttt{[MASK]}$ | 47.81 | 67.55 | 10.00 | 137.8 |
| 46.98 | 67.06 | 6.00 | 88.0 |
Iterative | 44.12 | 65.17 | 3.00 | 50.6 |
NAR | LevenshteinT | <s></s> | 48.36 | 69.00 | 2.51 | 93.0 |
| NeighborEdit | TFIDF | 55.40 | 72.59 | 1.66 | 75.4 |  (0.17)
| SentVec+TFIDF | 55.59 | 72.74 | 1.65 | 77.0 |  (0.08)
Table 1: BLEU, the mean number of iterations, and the mean latency [ms] on the
JRC-Acquis dataset. Boldface numbers are the top scores among NAR models. The
underline denotes significant gains over LevenshteinT at $p<0.05$.

NeighborEdit outperformed the NAR baselines significantly (more than +7.04
BLEU score and +3.59 ChrF score). Furthermore, the mean number of iterations
was the lowest among the iterative NAR models. NeighborEdit was not the
fastest in terms of latency because the proposed method decodes three times
(once for deletion and twice for insertion) for one iteration. However, it is
noteworthy that the proposed method significantly improved the generation
quality.

Surprisingly, NeighborEdit outperformed even a strong AR baseline (more than
+1.50 BLEU score) on this dataset. The mean number of iterations were less
than one-eighteenth of the AR baseline, and the latency was reduced by a
quarter.

These results indicate that incorporating neighbors into an NAR model is
effective; NeighborEdit can consistently improve the generation quality
without sacrificing the decoding speed. Furthermore, this finding raises
another question regarding the way in which nearest neighbors are utilized in
the proposed method. Therefore, we investigated the effect of the neighbors in
the oracle policy and the decoder initialization separately. We also explored
a Rand baseline that retrieves an example at random (regardless of input) for
decoder initialization.

Oracle policy | Decoder initialization
---|---
for neighbors | <s></s> | $\bm{z}_{0}$ | Rand
No ($\pi^{*}_{\mathrm{t}}$) | 48.36 |  $42.05$† | 3.00
Yes ($\pi^{*}_{\mathrm{t}}+\pi^{*}_{\mathrm{n}}$) | 45.67 | $55.59$ | 44.09
Table 2: BLEU scores with or without neighbor in the oracle policy and decoder
initialization on JRC-Acquis dataset. ${\dagger}$: We displayed the best-
performing value using SentVec+TFIDF, although the model can be initialized
with TFIDF and SentVec+TFIDF.

Table 2 shows that the performance significantly improved when we incorporate
neighbors from both the oracle policy and decoder initialization. Moreover,
random decoder initialization severely hurt the performance. These results
imply that the key to performance improvement is choosing useful neighbors and
incorporating them effectively to the oracle policy and decoder
initialization.

###  4.3 Experiments on Other Datasets

We also experimented other datasets that have not been well explored in
previous studies using nearest neighbors. In these experiments, we adopted
Levenshtein Transformer as an NAR baseline.

####  4.3.1 Data-to-Text (WikiBio)

We evaluated the effectiveness of NeighborEdit in the task of data-to-text
generation on WikiBio dataset777https://rlebret.github.io/wikipedia-biography-
dataset/ Lebret et al. (2016). In this task, the model receives a fact table
describing a person and generates the biography. Because biographies are
written in a similar manner, we can assume that certain patterns exist in the
target side of this task. To obtain the nearest neighbor, we calculated the
similarity score $S_{\text{TM}}$ between two serialized infoboxes $s_{i}$ and
$s_{j}$, similarly to Wiseman et al. (2021).

$\displaystyle S_{\text{TM}}(s_{i},s_{j})=$ $\displaystyle
F_{1}(\mathrm{fields}(s_{i}),\mathrm{fields}(s_{j}))$ (20)
$\displaystyle+0.1F_{1}(\mathrm{values}(s_{i}),\mathrm{values}(s_{j}))$

Here, $\mathrm{fields}(s)$ extracts the field types (e.g., ‘name’) from the
infobox $s$, $\mathrm{values}(s)$ extracts the unigrams that appear as values
in the infobox $s$ (e.g., ‘Obama’), and $F_{1}$ presents an F1-score. We call
this retrieval TableMatch. We trained the models with a maximum of 300,000
steps and a batch size of approximately 16,384 tokens per step. We evaluated
the models using BLEU, NIST888We used this evaluation script:
https://github.com/tuetschek/e2e-metrics. and the mean number of iterations.

Model | BLEU | NIST | Iteration
---|---|---|---
Transformer | 46.91 | 9.48 | 23.70
LevenshteinT | 43.09 | 8.79 | 2.25
NeighborEdit | 44.96 | 9.24 | 2.08
Table 3: Experimental results on the WikiBio dataset. Boldface numbers are the
top scores among NAR models. The underlined values denote significant gains
over LevenshteinT at $p<0.05$.

Table 3 reports the evaluation result. NeighborEdit improved the BLEU score
compared to the NAR baseline (+1.87 points) and narrowed the performance gap
with the AR baseline with fewer iterations. This demonstrates that the
proposed method was effective on this dataset.

####  4.3.2 Machine Translation (WMT’14)

Thus far, we examined the performance of NeighborEdit on the datasets where
nearest neighbors may be effective. In this section, we investigate the
performance on the popular WMT’14 English-German dataset Bojar et al. (2014).
Unlike JRC-Acquis, this dataset covers a wide range of topics. We downloaded
the dataset and preprocessed it using the fairseq
scripts999https://github.com/pytorch/fairseq/tree/main/examples/translation#WMT’14-english-
to-german-convolutional. We trained the models with a maximum of 300,000 steps
and a batch size of approximately 65,536 tokens per step.

Model | BLEU | Itr.
---|---|---
Transformer |  | 27.06 | 28.10
+Concat |  | 26.91 | 28.02
LevenshteinT |  | 23.98 | 2.83
NeighborEdit | TFIDF | 24.17 | 2.60
SentVec+TFIDF | 24.61 | 3.05
Table 4: BLEU scores and mean number of iterations on the WMT’14 En-De
dataset. Boldface numbers are the top scores among NAR models. The underlined
values denote significant gains over LevenshteinT at $p<0.05$.

Table 4 demonstrates that the proposed method using SentVec+TFIDF outperforms
Levenshtein Transformer (+0.63 points). However, the performance gain of BLEU
scores was smaller than that in the other datasets, and the number of
iterations was larger. Although we also explored an AR model where a source
sentence and its neighbor are concatenated in the Transformer architecture
(+Concat), we could not observe a performance improvement. Therefore, we
suspect that the WMT’14 En-De dataset may have a different characteristic to
JRC-Acquis and WikiBio.

###  4.4 Analysis on Neighbor Examples

Figure 2 displays scatter plots between the similarity of an example and its
neighbor ($x$-axis) and the sentence-BLEU of its translation ($y$-axis). For
JRC-Acquis and WMT’14 datasets, the $x$-axis presents the cosine similarity of
tf-idf vectors between a target sentence and its neighbor. However, the
similarity measures of the source and target sides of the WikiBio dataset are
completely different; therefore, the $x$-axis of Figure 2(c) shows F1 scores
of overlapping field names and values (Equation 20) (source side); and Figure
2(d) shows the cosine similarity of tf-idf vectors between a target sentence
and its neighbor (target side).

(a) JRC-Acquis En-De

(b) WMT’14 En-De

(c) WikiBio (source side)

(d) WikiBio (target side)

Figure 2: Scatter plot depicting the similarity between the example and its
neighbor ($x$-axis) and sentence-BLEU ($y$-axis) in each development set.

Figure 2(a) shows that the JRC-Acquis dataset contains many similar examples;
the mean of cosine similarity is 0.521. We observe the tendency that BLEU
scores are larger when retrieved examples have higher similarity values to
target sentences.

In contrast, Figure 2(b) clearly indicates that the WMT’14 dataset does not
include similar examples; the mean of cosine similarity is 0.105. This implies
that NeighborEdit must edit retrieved examples a lot, beginning with distant
examples. This difficulty has already been observed in the larger number of
iterations in Table 4. In other words, NeighborEdit was not so effective for
WMT’14 because most examples were dissimilar and few examples with a high
similarity were useful.

In the WikiBio dataset, the mean similarity on the source side is as high as
99.15 (Figure 2(c)) because two infobox tables can be similar only if these
tables include the same field names. In contrast, the mean similarity on the
target side is 0.130 (Figure 2(d)). These plots indicate that the similarity
distributions on the source and target sides are quite different because
different similarity metrics are used for infobox tables and sentences. We
followed the previous study to design the similarity metric of the source side
in Section 4.3.1. However, it may be necessary to reconsider the similarity
metric for the source side so that it reflects similar patterns of
biographies, for example, by focusing more on the occupations of entities.

##  5 Related Work

###  5.1 Non-autoregressive Generation

Text generation using NAR decoding has attracted attention in recent years
Ghazvininejad et al. (2019); Lee et al. (2020); Gu et al. (2019); Stern et al.
(2019a); Lee et al. (2018). Common approaches for improving the performance
are iterative decoding and knowledge distillation using AR models. A number of
researchers have proposed non-left-to-right decoding, utilizing parallelism in
NAR models Ghazvininejad et al. (2019); Gu et al. (2019); Stern et al.
(2019a). Inspired by these approaches, we incorporated the nearest neighbor
into the iterative decoding process to guide the generation.

###  5.2 Text Generation using Neighbors

Gu et al. (2018b) were the first to use nearest neighbors in an attention-
based encoder-decoder model. Other studies utilized the neighbors at the
token-level Khandelwal et al. (2021); Zheng et al. (2021), chunk-level
Borgeaud et al. (2021), and sentence-level Peng et al. (2019); Cao et al.
(2018) for text generation. Our approach is motivated primarily by these
successes. While token-level and chunk-level retrieval can obtain less noisy
(i.e., close) neighbors, they need to repeat a retrieval for each time step,
which slows down training and inference. In contrast, our method does not
suffer from the slowdown, retrieving neighbors only once per input. We
adjusted how neighbors were utilized during training and inference to reduce
the influence of noisy neighbors retrieved at sentence level.

Some previous studies concatenated a source sentence and its neighbors as
input or used two encoders for them Xu et al. (2020); Bulte and Tezcan (2019);
Borgeaud et al. (2021). Although these methods are effective, they require
additional mechanisms and parameters. In contrast, we incorporated neighbors
without introducing additional components or parameters but only by changing
the training strategy. To the best of our knowledge, this is the first study
to incorporate neighbors into an NAR model.

##  6 Conclusion

This paper proposes NeighborEdit, which utilizes the nearest neighbors in an
NAR decoder based on edit operations. The experimental results showed that
NeighborEdit could improve the quality of the generated sentences with fewer
iterations than existing NAR models on all datasets. We expect that
NeighborEdit will be beneficial in domains with writing patterns, such as
patents and parliamentary proceedings. Future work will include the design of
improved oracle policies that can reproduce intermediate sequences during
inference as well as the development of improved algorithms for sentence-level
neighbor retrieval.

## Acknowledgments

This work was supported by JSPS KAKENHI Grant Number 21J13602. These research
results were obtained from the commissioned research (No. 225) by National
Institute of Information and Communications Technology (NICT), Japan.

## References

  * Bojar et al. (2014) Ondřej Bojar, Christian Buck, Christian Federmann, Barry Haddow, Philipp Koehn, Johannes Leveling, Christof Monz, Pavel Pecina, Matt Post, Herve Saint-Amand, Radu Soricut, Lucia Specia, and Aleš Tamchyna. 2014.  Findings of the 2014 workshop on statistical machine translation.  In _Proceedings of the Ninth Workshop on Statistical Machine Translation_ , pages 12–58, Baltimore, Maryland, USA. Association for Computational Linguistics.
  * Borgeaud et al. (2021) Sebastian Borgeaud, Arthur Mensch, Jordan Hoffmann, Trevor Cai, Eliza Rutherford, Katie Millican, George van den Driessche, Jean-Baptiste Lespiau, Bogdan Damoc, Aidan Clark, Diego de Las Casas, Aurelia Guy, Jacob Menick, Roman Ring, Tom Hennigan, Saffron Huang, Loren Maggiore, Chris Jones, Albin Cassirer, Andy Brock, Michela Paganini, Geoffrey Irving, Oriol Vinyals, Simon Osindero, Karen Simonyan, Jack W. Rae, Erich Elsen, and Laurent Sifre. 2021\.  Improving language models by retrieving from trillions of tokens.  _CoRR_ , abs/2112.04426.
  * Bulte and Tezcan (2019) Bram Bulte and Arda Tezcan. 2019.  Neural fuzzy repair: Integrating fuzzy matches into neural machine translation.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 1800–1809, Florence, Italy. Association for Computational Linguistics.
  * Cai et al. (2021) Deng Cai, Yan Wang, Huayang Li, Wai Lam, and Lemao Liu. 2021.  Neural machine translation with monolingual translation memory.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 7307–7318, Online. Association for Computational Linguistics.
  * Cao et al. (2018) Ziqiang Cao, Wenjie Li, Sujian Li, and Furu Wei. 2018.  Retrieve, rerank and rewrite: Soft template based neural summarization.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 152–161, Melbourne, Australia. Association for Computational Linguistics.
  * Daelemans et al. (1996) Walter Daelemans, Jakub Zavrel, Peter Berck, and Steven Gillis. 1996.  MBT: A memory-based part of speech tagger-generator.  In _Fourth Workshop on Very Large Corpora_ , Herstmonceux Castle, Sussex, UK. Association for Computational Linguistics.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 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.
  * Dror et al. (2018) Rotem Dror, Gili Baumer, Segev Shlomov, and Roi Reichart. 2018.  The hitchhiker’s guide to testing statistical significance in natural language processing.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1383–1392, Melbourne, Australia. Association for Computational Linguistics.
  * Ghazvininejad et al. (2019) Marjan Ghazvininejad, Omer Levy, Yinhan Liu, and Luke Zettlemoyer. 2019.  Mask-predict: Parallel decoding of conditional masked language models.  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)_ , pages 6112–6121, Hong Kong, China. Association for Computational Linguistics.
  * Gu et al. (2018a) Jiatao Gu, James Bradbury, Caiming Xiong, Victor O.K. Li, and Richard Socher. 2018a.  Non-autoregressive neural machine translation.  In _International Conference on Learning Representations_.
  * Gu and Kong (2021) Jiatao Gu and Xiang Kong. 2021.  Fully non-autoregressive neural machine translation: Tricks of the trade.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 120–133, Online. Association for Computational Linguistics.
  * Gu et al. (2019) Jiatao Gu, Changhan Wang, and Junbo Zhao. 2019.  Levenshtein transformer.  In _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc.
  * Gu et al. (2018b) Jiatao Gu, Yong Wang, Kyunghyun Cho, and Victor OK Li. 2018b.  Search engine guided neural machine translation.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32.
  * Huang et al. (2022) Xiao Shi Huang, Felipe Perez, and Maksims Volkovs. 2022.  Improving non-autoregressive translation models without distillation.  In _International Conference on Learning Representations_.
  * Khandelwal et al. (2021) Urvashi Khandelwal, Angela Fan, Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis. 2021\.  Nearest neighbor machine translation.  In _International Conference on Learning Representations_.
  * Kim and Rush (2016) Yoon Kim and Alexander M. Rush. 2016.  Sequence-level knowledge distillation.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , pages 1317–1327, Austin, Texas. Association for Computational Linguistics.
  * Kingma and Ba (2015) Diederik P. Kingma and Jimmy Ba. 2015.  Adam: A method for stochastic optimization.  In _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_.
  * Lebret et al. (2016) Rémi Lebret, David Grangier, and Michael Auli. 2016.  Neural text generation from structured data with application to the biography domain.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , pages 1203–1213, Austin, Texas. Association for Computational Linguistics.
  * Lee et al. (2018) Jason Lee, Elman Mansimov, and Kyunghyun Cho. 2018.  Deterministic non-autoregressive neural sequence modeling by iterative refinement.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 1173–1182, Brussels, Belgium. Association for Computational Linguistics.
  * Lee et al. (2020) Jason Lee, Raphael Shu, and Kyunghyun Cho. 2020.  Iterative refinement in the continuous space for non-autoregressive neural machine translation.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1006–1015, Online. Association for Computational Linguistics.
  * Levenshtein et al. (1966) Vladimir I Levenshtein et al. 1966.  Binary codes capable of correcting deletions, insertions, and reversals.  In _Soviet physics doklady_ , volume 10, pages 707–710. Soviet Union.
  * Li et al. (2016) Liangyou Li, Andy Way, and Qun Liu. 2016.  Phrase-level combination of SMT and TM using constrained word lattice.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 275–280, Berlin, Germany. Association for Computational Linguistics.
  * Nagao (1984) Makoto Nagao. 1984.  A framework of a mechanical translation between japanese and english by analogy principle.  In _Proceedings of the International NATO Symposium on Artificial and Human Intelligence_ , pages 173–180.
  * Ott et al. (2019) Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. 2019.  fairseq: A fast, extensible toolkit for sequence modeling.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics (Demonstrations)_ , pages 48–53, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Peng et al. (2019) Hao Peng, Ankur Parikh, Manaal Faruqui, Bhuwan Dhingra, and Dipanjan Das. 2019.  Text generation with exemplar-based adaptive decoding.  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 2555–2565, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Popović (2015) Maja Popović. 2015.  chrF: character n-gram F-score for automatic MT evaluation.  In _Proceedings of the Tenth Workshop on Statistical Machine Translation_ , pages 392–395, Lisbon, Portugal. Association for Computational Linguistics.
  * Post (2018) Matt Post. 2018.  A call for clarity in reporting BLEU scores.  In _Proceedings of the Third Conference on Machine Translation: Research Papers_ , pages 186–191, Brussels, Belgium. Association for Computational Linguistics.
  * Qian et al. (2021) Lihua Qian, Hao Zhou, Yu Bao, Mingxuan Wang, Lin Qiu, Weinan Zhang, Yong Yu, and Lei Li. 2021.  Glancing transformer for non-autoregressive neural machine translation.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 1993–2003, Online. Association for Computational Linguistics.
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  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)_ , pages 3982–3992, Hong Kong, China. Association for Computational Linguistics.
  * Sennrich et al. (2016) Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016.  Neural machine translation of rare words with subword units.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1715–1725, Berlin, Germany. Association for Computational Linguistics.
  * Stern et al. (2019a) Mitchell Stern, William Chan, Jamie Kiros, and Jakob Uszkoreit. 2019a.  Insertion transformer: Flexible sequence generation via insertion operations.  In _International Conference on Machine Learning_ , pages 5976–5985. PMLR.
  * Stern et al. (2019b) Mitchell Stern, William Chan, Jamie Kiros, and Jakob Uszkoreit. 2019b.  Insertion transformer: Flexible sequence generation via insertion operations.  In _Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 5976–5985. PMLR.
  * Sun et al. (2019) Zhiqing Sun, Zhuohan Li, Haoqing Wang, Di He, Zi Lin, and Zhihong Deng. 2019.  Fast structured decoding for sequence models.  In _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc.
  * Sutskever et al. (2014) Ilya Sutskever, Oriol Vinyals, and Quoc V Le. 2014.  Sequence to sequence learning with neural networks.  In _Advances in Neural Information Processing Systems_ , volume 27.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in neural information processing systems_ , pages 5998–6008.
  * Wiseman et al. (2021) Sam Wiseman, Arturs Backurs, and Karl Stratos. 2021.  Data-to-text generation by splicing together nearest neighbors.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 4283–4299, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Xu et al. (2020) Jitao Xu, Josep Crego, and Jean Senellart. 2020.  Boosting neural machine translation with similar translations.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 1580–1590, Online. Association for Computational Linguistics.
  * Xu and Carpuat (2021) Weijia Xu and Marine Carpuat. 2021.  EDITOR: An edit-based transformer with repositioning for neural machine translation with soft lexical constraints.  _Transactions of the Association for Computational Linguistics_ , 9:311–328.
  * Zheng et al. (2021) Xin Zheng, Zhirui Zhang, Junliang Guo, Shujian Huang, Boxing Chen, Weihua Luo, and Jiajun Chen. 2021.  Adaptive nearest neighbor machine translation.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 2: Short Papers)_ , pages 368–374, Online. Association for Computational Linguistics.

##  Appendix A Appendix

Dataset | Train | Validation | Evaluation
---|---|---|---
JRC-Acquis | 475,330 | 2,945 | 2,937
WikiBio | 582,659 | 72,831 | 72,831
WMT’14 | 3,961,179 | 3,000 | 3,003
Table 5: Dataset statistics

###  A.1 Dataset Details

Table 5 lists the statistics of the datasets in the experiments. We did not
use the distilled dataset Kim and Rush (2016) in this study.

###  A.2 Model Details and Hyperparameters

For Neighboredit, we set $d_{\mathrm{model}}=512$, $d_{\mathrm{hidden}}=2048$,
$n_{\mathrm{head}}=8$, and $n_{\mathrm{layer}}=6$. In the proposed oracle
policy in Section 3.1.1, we set the hyperparameter $\alpha$ to $0.6$ for all
settings. In addition, we set $\beta$ to $0.3$ for all retrieval methods in
JRC-Acquis, TableMatch in WikiBio, and TFIDF in the WMT’14. For SentVec+TFIDF
in the WMT’14, we set to $1.0$. These are the values automatically determined
by the development data as well as other hyperparameters. A threshold value of
1.0 means that special tokens are used for initialization instead of neighbors
for all data during inference. However, during training, Neighboredit uses the
neighbors to learn the deletion operation, which led to improved performance
in Table 4. For the policy classifier, we set $K_{\mathrm{max}}$ to 255.
Embeddings of the source and target sides are shared. Furthermore, the
parameters of the three edit operations in the decoder are shared.

###  A.3 Neighbor Retrieval Details

For TFIDF, we first created high-dimensional sparse TFIDF vectors and reduced
the dimension to 512 by using singular value decomposition (SVD). After the
neighbors are retrieved by faiss, we reranked the Top-50 neighbor candidates
by calculating the exact cosine similarity of the uncompressed TFIDF vectors
between the candidates and source sentences to reduce information loss for the
TFIDF. For SentVec, we use the vectors (512 dimensions) computed by the pre-
trained encoder as they are. Nearest neighbor retrieval was much faster than
the decoding process of the NAR model; thus, the decoding overhead by nearest-
neighbor retrieval is negligible.

###  A.4 Training Details

We trained BPE Sennrich et al. (2016) to construct a vocabulary with 20,000
joint operations for the JRC-Acquis and 40,000 joint operations for the
WMT’14. For the WikiBio, we did not use the subword tokenization.

We followed the weight initialization scheme of BERT Devlin et al. (2019). We
used Adam Kingma and Ba (2015) optimizer with $\beta=(0.9,0.98)$. For
regulation, we set the dropout rate of 0.3 and the weight decay of 0.01. We
linearly increased the learning rate from $1\times 10^{-7}$ to $5\times
10^{-4}$ in the initial 10,000 steps and then used the learning rate decay of
square root. All models were trained on 4 NVIDIA Tesla P100 GPUs for the JRC-
Acquis and WikiBio, and 16 NVIDIA V100 GPUs for the WMT’14.

###  A.5 Evaluation Details

We selected the checkpoints according to the BLEU scores of the development
set. SacreBLEU hash is
BLEU+case.mixed+numrefs.1+smooth.exp+tok.13a+version.1.5.1. For a statistical
significance test, we adopted a paired bootstrap resampling Dror et al.
(2018).

###  A.6 Output examples

Figure 3 shows output examples of Levenshtein Transformer and NeighborEdit.
The proposed method could generate correct sentences with fewer iterations by
removing unnecessary words from the neighbor examples and filling the
placeholders.

Source | ( 48 ) Capacity utilisation increased by 56 % between 1996 and the IP.
---|---
Target | ( 48 ) Die Kapazitätsauslastung stieg von 1996 bis zum UZ um 56 %.
Levenshtein Transformer
Deletion 1 |
Insertion 1 | [PLH][PLH][PLH][PLH][PLH][PLH][PLH][PLH][PLH][PLH][PLH][PLH][PLH][PLH][PLH][PLH]
( 48 ) Die Kapazitätsauslastung stieg von 1996 bis dem UZ UZ um 56 %.
Deletion 2 | ( 48 ) Die Kapazitätsauslastung stieg von 1996 bis dem UZ um 56 %.
Insertion 2 | ( 48 ) Die Kapazitätsauslastung stieg von 1996 bis [PLH] dem UZ um 56 %.
( 48 ) Die Kapazitätsauslastung stieg von 1996 bis zu dem UZ um 56 %.
NeighborEdit
Neighbor (En) | ( 56 ) Export prices of the two cooperating Thai producers have increased by 6 % between 1996 and the IP.
Neighbor (De) | ( 56 ) Die Ausfuhrpreise der beiden kooperierenden thailänd@@ ischen Hersteller stiegen
|  von 1996 bis zum Untersuchungszeitraum um 6 %
Deletion 1 | ( ) Die von 1996 bis zum um %.
Insertion 1 | ( [PLH] ) Die [PLH] [PLH] von 1996 bis zum [PLH] um [PLH] %.
( 48 ) Die Kapazitätsauslastung stieg von 1996 bis zum UZ um 56 %.
Figure 3: An example of JRC-Acquis En-De translation by Levenshtein
Transformer and NeighborEdit (proposed). We present inserted tokens in red
color and deleted tokens in blue color. The proposed method could generate the
correct sentence with a single iteration.


# An Affine moment invariant for multi-component shapes

Joviša Žunić111Mathematical Institute, Serbian Academy of Sciences, Belgrade,
Serbia
e-mail<EMAIL_ADDRESS>Miloš Stojmenović222Department of
Informatics and Computing, Singidunum University, Belgrade, Serbia
email<EMAIL_ADDRESS>
###### Abstract

We introduce an image based algorithmic tool for analyzing multi-component
shapes here. Due to the generic concept of multi-component shapes, our method
can be applied to the analysis of a wide spectrum of applications where real
objects are analyzed based on their shapes - i.e. on their corresponded black
and white images. The method allocates a number to a shape, herein called a
multi-component shapes measure. This number/measure is invariant with respect
to affine transformations and is established based on the theoretical frame
developed in this paper. In addition, the method is easy to implement and is
robust (e.g. with respect to noise).

We provide two small but illustrative examples related to aerial image
analysis and galaxy image analysis. Also, we provide some synthetic examples
for a better understanding of the measure behavior.

###### keywords:

Measuring shapes, multi-component shapes, pattern recognition, image
processing.

††journal: Fundamenta Informaticae

##  1 Introduction

A shape is an object characteristic that can be described by several numerical
characteristics. These numerical characteristics, herein called shape
measures, are employed in many computer vision, image processing, and pattern
recognition tasks [2, 4]. Shape measures are often designed to evaluate
certain shape properties, like elongation [1, 25], convexity [14, 16],
tortuosity [7], and many more. Some of these measures are generic, and aim to
satisfy some specific properties such as rotational [8, 23] or affine [12, 5]
invariance, for example. It is worth mentioning that a range of popular shape
descriptors exist, and are extensively applied: algebraic [8], geometric [24],
logical [19], fractal ones [10], and so on. In most cases the shape measures
are combined and used together to achieve a better performance [3].

In this paper we define a measure applicable to multi-component shapes, which
is invariant with respect to Affine transformations. We examine multi-
component shapes in detail since they are not yet intensively studied in
literature, whereas there exists a lot of the work related to Affine
invariants, both in theory and practice.

###  1.1 Multi-component shapes

The concept of multi-component shapes has been presented in [27]. This is a
very generic concept that allows us to segment a single object onto
components, to group objects into a multi-component shape to suit a particular
application. Some examples are given in Fig.1 and in the Experimental
illustration section. Notice that some shape segmentation results can be
natural (Fig.1(c)), while some can be more artificial (e.g. Fig.1(d,e)); some
components can be connected, some not ((e.g. Fig.1(d,e))). Basically, there
are no real restrictions on categorizing a shape as a being multi-component.
Of course, a common requirement is that the selected segmentation well suits
the desired application.

Examples (a) and (b), in Fig.1 are real images of a school of fish and an
embryonic tissue, each of which have recognizable components. Their extracted
components are in Fig.2. Shape (c) in Fig.1 represents a natural
”decomposition” of a palm print while shapes (d) and (e), in the same figure
represent an artificial or inaccurate decomposition of a leaf shape [15] and a
galaxy shape, respectively, obtained using a thresholding method.

|  |  |
---|---|---|---
(a) | (b) | (c) | (d)

|
---|---
(e) |  (f)

Figure 1: (a) School of Fish (b) Embryonic tissue with indistinct cell
boundaries (c) Palm-print (d) leaf shape decomposed by concentric circles (e)
galaxy shape obtained with a thresholding method [13] (f) Human gait –
considered as a 13-component shape, whose components are the appearances of a
walking person in a sequence of 13 consecutive frames.

As expected, multi-component shapes are expected to have some properties that
are not typical of single shapes. An example of such a property is the
orientation of multi-component shapes. Indeed, in the case of relatively large
numbers of components, it is expected that the orientation of a multi-
component shape does not depend much on a ”window” used for the orientation
computation [27, 17]. Two examples are in found in Fig.2. The computed
orientations of both halves, as well as the shape as a whole almost coincide
for both (a) and (c) in Fig.2.

Figure 2: Orientations computed for (a) the separate left and right halves of
the image, and also for (b) the complete image. The shorter dark blue arrows
correspond to the shape orientations computed for the three sets of data
according to our multi-component approach. In comparison, the long light red
arrows correspond to the traditional method for computing orientation, in
which each of the three sets of data are considered as representing single-
component shapes (each containing multiple fish).

There already exist shape descriptors whose measures are only applicable for
multiple component shapes. Some examples are anisotropy and dis-connectedness
of multi-component shapes [17, 28].

##  2 Preliminaries

Here we define the basic terms and introduce the notation used in this paper.
We also give some well-known facts used for our derivations.
$\bullet$ The shape is a basic object property (like color or texture, for
example). As such, shape does not need a formal definition. Shape is
represented by a planar region, usually displayed as a binary (black-white)
image.

$\bullet$ A multi-component shape $S=S_{1}\cup S_{2}\cup\ldots\cup S_{n}$,
having components $S_{1},\;S_{2},\;\ldots,\;\makebox{and},\;S_{n}$, is
represented by $n$ regions, corresponding to its components.

Note that the regions representing a component $S_{i}$ do not need to be
connected, in a topological sense. 333Formally, an $n$-component shape
$S=S_{1}\cup S_{2}\cup\ldots\cup S_{n}$, can be defined formally as a mapping
$F((x,y))$: $S\ \rightarrow\ \\{1,2,\ldots,n\\}$. All of the points $(x,y)$
with the same assigned value $F((x,y))$, belong to the same component, i.e.
the $k$-th component $S_{k}$, where $1\leq k\leq n,$ is defined as $S_{k}\ =\
\\{(x,y)\ |\ F((x,y))=k\\}\ =\ F^{-1}(k).$ There is no formal restriction on
how a given shape can be decomposed and presented as a multi-component shape.
From a practical view-point such a decomposition should be meaningful in order
to be beneficial for the desired application.

$\bullet$ Two shapes are considered equal if their set difference has an area
equal to zero.

$\bullet$ The geometric moment, or simply moment, $m_{p,q}(S)$ of a given
planar shape $S$ is defined as

$m_{p,q}(S)=\int\limits_{S}\\!\\!\\!\\!\int x^{p}y^{q}dx\,dy.$ (1)

The moment $m_{p,q}(S)$ has the order equal to $p+q$. Obviously, $m_{0,0}(S),$
equals the area of $S$, while the moments $m_{1,0}(S)$ and $m_{0,1}(S)$ are
used to define the shape centroid, denoted as $\ \left(x_{c}(S),\
y_{c}(S)\right)\ $ and formally defined as

$\left(x_{c}(S),\ y_{c}(S)\right)\;=\;\left(\frac{m_{1,0}(S)}{m_{0,0}(S)},\
\frac{m_{0,1}(S)}{m_{0,0}(S)}\right).$ (2)

$\bullet$ The normalized moments $\mu_{p,q}(S)$ are defined as

$\mu_{p,q}(S)\ =\
\frac{1}{m_{0,0}(S)^{(p+q+2)/2}}\cdot\int\limits_{S}\\!\\!\\!\int\left(x-x_{c}(S)\right)^{p}\left(y-y_{c}(S)\right)^{q}dxdy$
(3)

$\bullet$ Normalized moments $\mu_{p,q}(S)$ are translation and scaling
invariant by definition. Both invariances are required in shape based tasks
because shape properties do change under scaling and translation
transformations.

$\bullet$ Many more moment invariants are used in shape based image analysis
tasks. In his seminal work [8], Hu introduced seven quantities which are
rotational invariants. Hu used algebraic reasoning, but later on Xu and Li
[24] showed that Hu invariants are actually geometric invariants, and can be
derived by considering certain geometric primitives defined by the shape
points. Geometric reasoning will be applied here as well.

$\bullet$ Affine moment invariants are quantities computed from a set of
moments that do not change under Affine transformation [5, 21]. The following
Affine invariant will be exploited here

${\cal A}(S)=\mu_{2,0}(S)\cdot\mu_{0,2}(S)-\mu_{1,1}(S)^{2}.$ (4)

$\bullet$ The Affine invariant ${\cal A}(S)$ has a simple geometric
interpretation. Indeed, the squared area of the triangle whose vertices are
points $(0,0),$ $(x,y)$, and $(u,v)$ is

$\frac{1}{4}\cdot(x\cdot v-y\cdot u)^{2}.$ (5)

So, for a given shape $S$, having an area equal to $1$, and all the triangles
$\Delta ABC$ such that $A=(x,y)\in S$ and $B(u,v)\in S$ we easily obtain that
a half of ${\cal A}(S)$ equals the total integral of the squared areas of
triangles $\Delta ABC$:

$\displaystyle\iint\limits_{(x,y)\in S}\ \ \iint\limits_{(u,v)\in S}\ \
\frac{1}{4}\cdot(x\cdot v-y\cdot u)^{2}dx\ dy\ du\ dv$ (6) $\displaystyle=$
$\displaystyle\frac{1}{2}\cdot\left(\mu_{2,0}(S)\cdot\mu_{0,2}(S)-\mu_{1,1}(S)^{2}\right)=\frac{1}{2}\cdot{\cal
A}(S).$

Such a simple geometric interpretation [29, 24] has been used in [29] to
establish a shape interpretation of ${\cal P}(S)$. This interpretation of
${\cal P}(S)$ does not allow a simple extension to multi-component shapes. In
the next section we will give a modified interpretation of ${\cal P}(S)$,
which is extendable to multi-component shapes.

##  3 A new Affine invariant for multi-component shapes

As mentioned, we aim to develop a multi-component shape measure that is
invariant with respect to Affine transformations. Our first idea was to
exploit an existing Affine moment invariant ${\cal A}(S)$, as given in (6),
defined for single-component shapes [5]. Such a measure has a nice geometric
interpretation [24, 29] but is not easily extendable to measure multi-
component shapes.444To the best of our knowledge, this interpretation is
novel, never before mentioned in literature. Since the idea is natural, it is
still possible that it has been used and observed by others already. So, we
had to modify the equality in (6) and derive another geometric interpretation
of the measure ${\cal A}(S).$ We show that ${\cal A}(S)$ (as given in (4))
equals the integral of the squared triangle areas, i.e. the integral of
$Area\\_(\Delta ABC)^{2}$, where $A,$ $B,$ and $C$ vary through a given shape
$S$ whose area is $1.$ We give the following theorem.

###### Theorem 1

Let $A=(x,y),$ $B=(u,v),$ and $C=(z,\omega)$, be points belonging to a given
shape $S$, having an area equal to $1,$. The integral of all squared areas of
triangles $\Delta ABC$ equals a quarter of ${\cal A}(S),$ or formally

$\displaystyle\frac{1}{6}\iint\limits_{(x,y)\in S}\ \ \iint\limits_{(u,v)\in
S}\ \ \iint\limits_{(z,\omega)\in S}(Area\\_of\\_\Delta
ABC)^{2}dxdydudvdzd\omega$ (7) $\displaystyle\frac{1}{6}\ \cdot\
\iint\limits_{(x,y)\in S}\ \ \iint\limits_{(u,v)\in S}\ \
\iint\limits_{(z,\omega)\in
S}\frac{1}{4}\cdot\left((x-z)(v-\omega)-(y-\omega)(u-z)\right)^{2}dxdydudvdzd\omega$
$\displaystyle=$
$\displaystyle\frac{1}{4}\cdot\left(\mu_{2,0}(S)\cdot\mu_{0,2}(S)-\mu_{1,1}(S)^{2}\right)\
=\ \frac{1}{4}\cdot{\cal A}(S).$

Proof. We do not give a complete proof here. Even though the derivation might
be seen as a long and messy one, it is still trivial. Here are some hints to
support the derivations.

  * 1.

The formula in (5) for the points $(x-z,y-\omega),$ $(u-z,v-\omega),$ and
$(z-z,\omega-\omega)=(0,0)$, should be used.

  * 2.

The identity $\iint\limits_{(x,y)\in S}\ \ \iint\limits_{(u,v)\in S}\ \
\iint\limits_{(z,\omega)\in
S}x^{a}y^{b}u^{c}v^{d}z^{e}\omega^{f}dxdydudvdzd\omega=\mu_{a,b}(S)\cdot\mu_{c,d}(S)\cdot\mu_{e,f}(S)$
should be applied.

  * 3.

The factor $\frac{1}{6}$ comes from the fact that three points $(x,y),$
$(u,v),$ and $(z,\omega),$ determine the same triangle, independently on order
they have been selected. $\blacksquare$

Now, we have the idea and necessary theoretical framework regarding how to
define the affine moment invariant for multi-component shapes. Briefly, we
observe all points that do not belong to a single shape component and the
integral of the squared areas of the triangles determined by these points.
Rather than manipulate with all three points (i.e. observed triangle vertices)
that do not belong to the same component, we observe the squared triangle
areas determined by all of the triplets of points that do belong to the
n-component shape $S=S_{1}\cup S_{2}\cup\ldots\cup S_{n}$ and take the areas
of all the triangles whose vertices belong to the same component. This is just
for the sake of a simpler computation.

Since the shape $S$ and all of the components of $S$ should play a role in the
computation of its new Affine invariant measure, the size of all of these
appearing shapes should be taken into account. We have the following identity
(see (3)), for the shapes whose area is not equal to $1$:

$\displaystyle m_{2,0}(S)\cdot m_{0,2}(S)-m_{1,1}(S)^{2}\ =$
$\displaystyle\mu_{0,0}(S)^{4}\cdot\left(\mu_{2,0}(S)\cdot\mu_{0,2}(S)-\mu_{1,1}(S)^{2}\right)\
=\ \mu_{0,0}(S)^{4}\cdot{\cal A}(S).$ (8)

As mentioned, we observe the integral of squared areas of all triangles whose
vertices do belong to the same component of the n-component shape $S$ from the
integral of squared areas of all triangles whose vertices belong to the shapes
$S$. This quantity can be computed as

$\left(m_{2,0}(S)\cdot m_{0,2}(S)-m_{1,1}(S)^{2}\right)\ -\
\sum_{i=1}^{i=n}\left(m_{2,0}(S_{i})\cdot
m_{0,2}(S_{i})-m_{1,1}(S_{i})^{2}\right)$ (9)

or equivalently in the following form

$\displaystyle m_{0,0}(S_{1}\cup\ldots\cup
S_{n})^{4}\cdot\left(\mu_{2,0}(S)\cdot\mu_{0,2}(S)-\mu_{1,1}(S)^{2}\right)$
$\displaystyle\qquad-\sum_{i=1}^{i=n}m_{0,0}(S_{i})^{4}\cdot\left(\mu_{2,0}(S_{i})\cdot\mu_{0,2}(S_{i})-\mu_{1,1}(S_{i})^{2}\right).$
(10)

If we normalize the above form, i.e. divide both summands with
$\left(m_{0,0}(S_{1}\cup\ldots\cup S_{n})\right)^{4}$ we get the quantity

${\cal A}(S_{1}\cup\ldots\cup S_{n})-\frac{1}{m_{0,0}(S_{1}\cup\ldots\cup
S_{n})^{4}}\cdot\sum_{i=1}^{i=n}m_{0,0}(S_{i})^{4}\cdot{\cal A}(S_{i}).$ (11)

that will be used to define a new Affine measure ${\cal M}(S)$ for multi-
component shapes. We give the following definition.

###### Definition 1

Let an $n$-component shape $S$ be given. We define the multi-component shape
measure ${\cal M}(S)$, for such a shape $S$, by the following equality

$\displaystyle{\cal M}(S)={\cal M}(S_{1}\cup\ldots\cup S_{n})$ (12)
$\displaystyle=$ $\displaystyle{\cal A}(S_{1}\cup\ldots\cup
S_{n})-\frac{1}{m_{0,0}(S_{1}\cup\ldots\cup
S_{n})^{4}}\cdot\sum_{i=1}^{i=n}m_{0,0}(S_{i})^{4}\cdot{\cal A}(S_{i}).$

##  4 Experimental Illustrations

Several experimental illustration are given in this section in order to enable
an easier understanding of the behavior of the new measure ${\cal M}(S)$.
First experiment. In this experiment we illustrate the diversities in
representing a shape as being multi-component. We use a hand shape, displayed
in Fig.3(a). In the first instance, the shape in Fig.3(a) can be treated as a
6-component shape, whose components are the palm and five fingers, each taken
as a separate component. In such a case the computed measure value is ${\cal
M}_{6-comp.}(S)=0.0109.$

The hand shape in Fig.3(a) can also be observed as a 2-component shape. It is
possible to select the palm (as displayed in Fig.3(b)) as one component and
all five fingers as the other component (S displayed in Fig.3(c)). In this
case the computed measure is ${\cal M}_{2-comp.}(S)=0.0177.$

To complete this discussion, it is worth mentioning that if the palm is
considered as a 1-component shape, then ${\cal M}_{1-comp.}(S)=0,$ which is in
accordance with the Definition 1, i.e. the computed measure ${\cal
M}_{1-comp.}(S)$ of all 1-component shapes is equal to zero. If the shape
consists of five fingers, as displayed in Fig.3(c), then the computed measure
is ${\cal M}_{5-comp.}(S)=0.1972$.

|  |
---|---|---
(a): A whole hand shape |  (b): The palm |  (c): The fingers
${\cal M}_{6-comp.}(S)=0.0162$ | —– | —–
${\cal M}_{2-comp.}(S)=0.0177$ | —– | —–
—– | ${\cal M}_{1-comp.}(S)=0$ | ${\cal M}_{5-comp.}(S)=0.1972$
Figure 3: The shape on the left is treated as being 2-component (five fingers
as one components and the palm as the second component) and its computed
measure is ${\cal M}_{2-comp.}(S)=0.0177$. Treating the same shape as being
6-component (five fingers, each a separate component, and the palm, as the
final component), the computed measure is ${\cal M}_{6-comp.}(S)=0.0162$. The
measure values for the 1-component shape and the 5-component shape in
Fig.3(b)&(c) are $0$ and $0.1972,$ respectively.

Second experiment. In this experiment we illustrate that ${\cal M}(S)$ depends
on the distances between shape components. Precisely, as such distances
increase, the ${\cal M}(S)$ values increase as well. In each sub-figure in
Fig.4, there are four identical squares, but with varying distances between
each other. As the distance between these squares increases, the measured
values ${\cal M}(S)$ increase as well. Notice that this is in accordance with
the definition of ${\cal M}(S)$.

(a) $0.0626$

(b) $0.2726$

(c) $0.7748$

(d) $1.8433$

Figure 4: $4$-component shapes and their assigned ${\cal M}_{4-comp.}(S)$
values (given below each shape)

Third experiment. An aerial image (Cardiff, U.K.) is in Fig.5, on the right.
The extracted edges of the buildings are in the image in the middle. The
obtained edges are skewed such that the rectilinearity measure (for detail see
[18]) of the building contours is maximized. The obtained values for the two
5-component shapes are almost identical (${\cal M}(middle-image)=0.0324$ and
${\cal M}(image-on-the-right)$), as expected. There is a small difference
caused by the numerical calculation.

|  |
---|---|---
Original image |  ${\cal M}$(S) = 0.0466 |  ${\cal M}$(S) = 0.0467
Figure 5: The images are taken from [18]: The original aerial image is on the
left. The extracted contours (from the original images) are in the middle. The
skewed contours, such that the rectilinearity measure is maximized, are on the
right.

Fourth experiment. In this experiment we illustrate the potential of the new
measure to be used in a galaxy shape analysis task. Elliptical and spiral
galaxies, listed in the popular Nearby Galaxy Catalog [6], are selected to
illustrate a discriminative capacity of ${\cal M}_{3-comp.}(S)$. The results
for spiral galaxies are in Fig.6, while the results for elliptical galaxies
are in Fig.7.

|  |
---|---|---
|  | ${\cal M}_{3-comp.}(S)=0.000679$
Original image | Filtered image | Multicomponent image
|  |
|  | ${\cal M}_{3-comp.}(S)=0.000593$
Original image | Thresholded image | Multicomponent image
|  |
|  | ${\cal M}_{3-comp.}(S)=0.001883$
Original image | Filtered image | Multi-component image
Figure 6: The original images of the three spiral galaxies, from [6], are
displayed on the left, in each row. The images in the second column, are
obtained by applying a median filter, to the original galaxy images. The
images on the right are 4-component images, obtained by a thresholding method.
Three components are used for the ${\cal M}_{3-comp}(S)$ computation, while
the fourth component corresponds to the galaxy background.

The original galaxy images are on the left, in each row, in both Fig.6 and
Fig.7. A median filter has been applied to these original images. The filtered
images are in the second column, in both related images. Multi-components of
the filtered images are obtained by applying a multi threshold method. These
images are on the right. Four components were obtained for each galaxy
filtered image. Three of them are used as galaxy image components, and the
fourth component corresponds to the galaxy background. The computed ${\cal
M}_{3-comp.}(S)$ measure is immediately below the thresholded images.

|  |
---|---|---
|  | ${\cal M}_{3-comp.}(S)=0.000443$
Original image | Filtered image | Multicomponent image
|  |
|  | ${\cal M}_{3-comp.}(S)=0.000545$
Original image | Thresholded image | Multicomponent image
|  |
|  | ${\cal M}_{3-comp.}(S)=0.000341$
Original image | Filtered image | Multicomponent image
Figure 7: The original images of the three elliptical galaxies, from [6], are
displayed on the left, in each row. The images in the second column, are
obtained by applying a median filter, to the original images. The images on
the right are 4-component shapes, obtained by a thresholding method. Three
components are used for the ${\cal M}_{3-comp}(S)$ computation, while the
fourth component corresponds to the galaxy background.

The measure ${\cal M}_{3-comp.}(S)$ distinguishes between spiral and
elliptical galaxies very well. The values for ${\cal M}_{3-comp.}(S)$ are
$0.000679$ (for the galaxy image in the first row), $0.000593$ for the galaxy
image in the second row, and $0.001883$ for the galaxy image in the third row
(see Fig.6). The computed ${\cal M}_{3-comp.}(S)$ values are smaller for the
three selected elliptical galaxies. They are $0.000545,$ $0.000341,$ and
$0.000341$, respectively.

##  5 Conclusion

A new shape measure ${\cal M}(S)$ has been introduced. The new measure is
Affine invariant and is designed to be applicable to multi-component shapes.
The measure is developed by exploiting a new geometric interpretation of the
well-known Affine invariant [5]: $\ {\cal
A}(S)=\mu_{2,0}(S)\cdot\mu_{0,2}(S)-\mu_{1,1}(S)^{2}\ $ (see (4)). This new
interpretation of ${\cal A}(S)$ says that ${\cal A}(S)$ is proportional to the
total integral of the squared areas of all the triangles whose vertices belong
to $S$. Another interpretation of ${\cal A}(S)$ can be found in [24], but this
interpretation does not allow an easy application to the multi-components
shapes measurement. The new interpretation of ${\cal A}(S)$ enables an easy
and natural extension of ${\cal A}(S)$ to multi-component shapes. As such, the
new measure ${\cal M}(S)$ is very flexible, because the concept of multi-
component shapes is very generic. Indeed, a given shape can be decomposed into
components in various ways. Also, the number of components can be selected in
different ways. All this has been illustrated on illustrative experimental
examples.

The new measure ${\cal M}(S)$ is an Affine invariant. The suitability of the
Affine invariance property for multi-component shape analysis is also
illustrated. The task of matching aerial photos of objects on the ground
(please see the third experiment) was given as an illustration.

Being an area based measure, i.e. a measure that uses all of the shape points
for its computation, it is efficient to compute [9, 11]. This is not a case
for boundary based shape measures, e.g. [17, 20, 25].

## References

## References

  * [1] M. A. Aktas, J. Žunić: A family of shape ellipticity measures for galaxy classification. SIAM Journal on Imaging Sciences, 6:765–782, 2013.
  * [2] F. Cao, J.-L. Lisani, J.-M. Morel, P. Musé, F. Sur. A theory of shape identification, Springer, 2008.
  * [3] J. B. de Carvalho, G.J.A. do Amaral: Classification methods for planar shapes. Expert Systems with Applications, 151 paper 113320, 2020.
  * [4] L. d. F. Costa, R. M. Cesar Jr.: Shape classification and analysis: theory and practice, CRC Press, 2009.
  * [5] J. Flusser and T. Suk: Pattern recognition by Affine moment invariants. Pattern Recognition, 26:167–174, 1993.
  * [6] Z. Frei, P. Guhathakurta, J. E. Gunn, and J. A. Tyson: A catalog of digital images of 113 nearby galaxies. Astronom. J., 111:174–181, 1996.
  * [7] E. Grisan, M. Foracchia, A. Ruggeri: A novel method for the automatic grading of retinal vessel tortuosity. IEEE Transactions on Medical Images, 27:310–319, 2008.
  * [8] M. K. Hu: Visual pattern recognition by moment invariants. IRE Transactions on Information Theory, 8:179–187, 1962.
  * [9] M.N. Huxley, R. Klette, J. Žunić: ‘Precision of geometric moments in picture analysis,’ chapter in Geometric Properties from Incomplete Data, editors: R. Klette, R. Kozera, L. Noakes, J. Weickert, pp. 221-235, Springer, 2006.
  * [10] A. R. Imre: Fractal dimension of time-indexed paths, Applied Mathematics and Computation, 207:221–229, 2009.
  * [11] R. Klette, J. Žunić: Multigrid Convergence of Calculated Features in Image Analysis, J. Math. Imaging Vis., 13:173-191, 2000.
  * [12] Y. Mei, D. Androutsos: Robust affine invariant region-based shape descriptors: The ICA Zernike moment shape descriptor and the whitening Zernike moment shape descriptor, IEEE Signal Processing Letters, 16:877-880, 2009.
  * [13] N. Otsu: A threshold selection method from gray-level histograms. IEEE Transactions on Systems, Man, and Cybernetics, 9:62–66, 1979.
  * [14] E. Rahtu, M. Salo, J. Heikkilä: A new convexity measure based on a probabilistic interpretation of images. IEEE T. Pattern Analysis Mach. Intell. 28:1501–1512, 2006.
  * [15] M. B. H. Rhouma, J. Žunić, M. C. Younis: Moment invariants for multi-component shapes with applications to leaf classification. Computers and Electronics in Agriculture, 142:326–337, 2017.
  * [16] P. L. Rosin, C. L. Mumford: A symmetric convexity measure. Computer Vision and Image Understanding, 103:101–111, 2006.
  * [17] P. L. Rosin, J. Žunić: Orientation and anisotropy of multi-component shapes from boundary information. Pattern Recognit., 44: 2147–2160, 2011.
  * [18] P. L. Rosin, J. Žunić: Measuring rectilinearity. Comput. Vis. Image Underst., 99:175–188, 2005.
  * [19] H. Schweitzer, J. Straach: Utilizing moment invariants and Gröbner bases to reason about shapes, Computational Intelligence, 14:461–474, 1998.
  * [20] M. Stojmenović, J. Žunić: Measuring Elongation from Shape Boundary. J. Math. Imaging Vis., 30:73–85, 2008.
  * [21] T. Suk and J. Flusser: Affine moment invariants generated by graph method. Pattern Recognition, 44:2047–2056, 2011.
  * [22] A. Q. Tool: A method for measuring ellipticity and the determination of optical constants of metals. Physical Review (Series I), 31:1–25, 1910
  * [23] B. Wang: Shape retrieval using combined Fourier features. Optics Communications, 284:3504–3508, 2011.
  * [24] D. Xu, H. Li: Geometric moment invariants. Pattern Recognition, 41:240–249, 2008.
  * [25] A. Žunić: Shape diameter for object analysis. Inf. Procc. Letters, 136:76–79, 2018.
  * [26] J. Žunić, P. L. Rosin: Rectilinearity measurements for polygons. IEEE Trans. Pattern Anal. Mach. Intell., 25:1193–1200, 2003.
  * [27] J. Žunić, P. L. Rosin: An Alternative Approach to Computing Shape Orientation with an Application to Compound Shapes. Int. J. Comput. Vis., 81: 138–154, 2009.
  * [28] J. Žunić, P. L. Rosin, V. Ilić: Disconnectedness: A new moment invariant for multi-component shapes. Pattern Recognition, 78:91–102, 2018.
  * [29] J. Žunić, D. Žunić: Shape interpretation of second moment invariants. Journal of Mathematical Imaging and Vision, 56:125–136, 2016.