# Towards Unsupervised Grammatical Error Correction
using Statistical Machine Translation with Synthetic Comparable Corpus

Satoru Katsumata  Mamoru Komachi
Tokyo Metropolitan University
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We introduce unsupervised techniques based on phrase-based statistical machine
translation for grammatical error correction (GEC) trained on a pseudo learner
corpus created by Google Translation. We verified our GEC system through
experiments on various GEC dataset, including a low resource track of the
shared task at Building Educational Applications 2019 (BEA2019). As a result,
we achieved an $\mathrm{F_{0.5}}$ score of 28.31 points with the test data of
the low resource track.

##  1 Introduction

Research on grammatical error correction (GEC) has gained considerable
attention recently. Many studies treat GEC as a task that involves translation
from a grammatically erroneous sentence (source-side) into a correct sentence
(target-side) and thus, leverage methods based on machine translation (MT) for
GEC. For instance, some GEC systems use large parallel corpora and synthetic
data (Ge et al., 2018; Xie et al., 2018).

We introduce an unsupervised method based on MT for GEC that does not almost
use parallel learner data. In particular, we use methods proposed by Marie and
Fujita (2018), Artetxe et al. (2018b), and Lample et al. (2018). These methods
are based on phrase-based statistical machine translation (SMT) and two phrase
table refinements, i.e., forward and backward refinement. Forward refinement
simply arguments a learner corpus with automatic corrections whereas backward
refinement expends both source-side and target-side data to train GEC model
using back-translation (Sennrich et al., 2016a).

Unsupervised MT techniques do not require a parallel but a comparable corpus
as training data. Therefore, we use comparable translated texts using Google
Translation as the source-side data. Specifically, we use News Crawl written
in English as target-side data and News Crawl written in another language
translated into English as source-side data.

We identified the difference between forward and backward refinement with
CoNLL-2014 dataset and JFLEG dataset; the former generates fluent outputs. We
also verified our GEC system through experiments for a low resource track of
the shared task at Building Educational Applications 2019 (BEA2019). The
experimental results show that our system achieved an $\mathrm{F_{0.5}}$ score
of 28.31 points in the low resource track of the shared task at BEA2019.

##  2 Unsupervised GEC

Algorithm 1 shows the pseudocode for unsupervised GEC. This code is derived
from Artetxe et al. (2018b). First, the cross-lingual phrase embeddings are
acquired. Second, a phrase table is created based on these cross-lingual
embeddings. Third, the phrase table is combined with a language model trained
by monolingual data to initialize a phrase-based SMT system. Finally, the SMT
system is updated through iterative forward-translation or back-translation.

#### Cross-lingual embeddings

First, $n$-gram embeddings were created on the source- and target-sides.
Specifically, each monolingual embedding was created based on the source- and
target-sides using a variant of skip-gram (Mikolov et al., 2013) for unigrams,
bigrams, and trigrams with high frequency111We used the most frequent 200K
unigrams, 400K bigrams, and 400K trigrams in the monolingual data. in the
monolingual data. Next, the monolingual embeddings were mapped onto a shared
space to obtain cross-lingual embeddings. The self-learning method of Artetxe
et al. (2018a) was used for unsupervised mapping.

Algorithm 1 Unsupervised GEC

1:language model of the source-side $LM_{s}$

2:language models of the target-side $LM_{t}$

3:source training corpus $C_{s}$

4:target training corpus $C_{t}$

5:tuning data $T$

6:iteration number $N$

7:source-to-target phrase table $P^{(N)}_{s\to t}$

8:source-to-target weights $W^{(N)}_{s\to t}$

9:$W_{s}^{emb}\leftarrow\textsc{train}(C_{s})$

10:$W_{t}^{emb}\leftarrow\textsc{train}(C_{t})$

11:$W_{s}^{cross\\_emb},W_{t}^{cross\\_emb}\leftarrow\textsc{mapping}(W_{s}^{emb},W_{t}^{emb})$

12:if forward_refinement then

13: $P^{(0)}_{s\to t}$ $\leftarrow$
initialize($W_{s}^{cross\\_emb},W_{t}^{cross\\_emb}$)

14: $W^{(0)}_{s\to t}$ $\leftarrow$ tune($P^{(0)}_{s\to t},LM_{t},T$)

15: for $iter=1,\dots,N$ do

16: $\mathrm{synthetic\\_data}_{t}$

17: $\leftarrow$ decode($P^{(iter-1)}_{s\to t}$, $LM_{t}$, $W^{(iter-1)}_{s\to
t}$, $C_{s}$)

18: $P^{(iter)}_{s\to t}$ $\leftarrow$ train($C_{s}$,
$\mathrm{synthetic\\_data}_{t}$)

19: $W^{(iter)}_{s\to t}\leftarrow\textsc{tune}(P^{(iter)}_{s\to t},LM_{t},T)$

20:else if backward_refinement then

21: $P^{(0)}_{t\to s}$ $\leftarrow$
initialize($W_{t}^{cross\\_emb},W_{s}^{cross\\_emb}$)

22: $W^{(0)}_{t\to s}$ $\leftarrow$ tune($P^{(0)}_{t\to s},LM_{s},T$)

23: for $iter=1,\dots,N$ do

24: $\mathrm{synthetic\\_data}_{s}$

25: $\leftarrow$ decode($P^{(iter-1)}_{t\to s}$, $LM_{s}$, $W^{(iter-1)}_{t\to
s}$, $C_{t}$)

26: $P^{(iter)}_{s\to t}$ $\leftarrow$ train($\mathrm{synthetic\\_data}_{s}$,
$C_{t}$)

27: $W^{(iter)}_{s\to t}\leftarrow\textsc{tune}(P^{(iter)}_{s\to t},LM_{t},T)$

28: $\mathrm{synthetic\\_data}_{t}$

29: $\leftarrow$ decode($P^{(iter-1)}_{s\to t}$, $LM_{t}$, $W^{(iter-1)}_{s\to
t}$, $C_{s}$)

30: $P^{(iter)}_{t\to s}$ $\leftarrow$ train($\mathrm{synthetic\\_data}_{t}$,
$C_{s}$)

31: $W^{(iter)}_{t\to s}\leftarrow\textsc{tune}(P^{(iter)}_{t\to s},LM_{s},T)$

#### Phrase table induction

A phrase table was created based on the cross-lingual embeddings. In
particular, this involved the creation of phrase translation models and
lexical translation models.

The translation candidates were limited in the source-to-target phrase
translation model $\phi(\overline{f}|\overline{e})$ for each source phrase
$\overline{e}$ to its 100 nearest neighbor phrases $\overline{f}$ on the
target-side. The score of the phrase translation model was calculated based on
the normalized cosine similarity between the source and target phrases.

$\phi(\overline{f}|\overline{e})=\frac{\exp(\cos(\overline{e},\overline{f})/\tau)}{\sum_{\overline{f}^{\prime}}\exp(\cos(\overline{e},\overline{f}^{\prime})/\tau)}$
$None$

$\overline{f}^{\prime}$ represents each phrase embedding on the target-side
and $\tau$ is a temperature parameter that controls the confidence of
prediction222As in Artetxe et al. (2018b), $\tau$ is estimated by maximizing
the phrase translation probability between an embedding and the nearest
embedding on the opposite side.. The backward phrase translation probability
$\phi(\overline{e}|\overline{f})$ was determined in a similar manner.

The source-to-target lexical translation model
$\mathrm{lex}(\overline{f}|\overline{e})$ considers the word with the highest
translation probability in a target phrase for each word in a source phrase.
The score of the lexical translation model was calculated based on the product
of respective phrase translation probabilities.

$\mathrm{lex}(\overline{f}|\overline{e})=\prod_{i}\max\left(\epsilon,\max_{j}\phi\left(\overline{f}_{i}|\overline{e}_{j}\right)\right)$
$None$

$\epsilon$ is a constant term for the case where no alignments are found. As
in Artetxe et al. (2018b), the term was set to 0.001. The backward lexical
translation probability $\mathrm{lex}(\overline{e}|\overline{f})$ is
calculated in a similar manner.

#### Refinement of SMT system

The phrase table created is considered to include noisy phrase pairs.
Therefore, we update the phrase table using an SMT system. The SMT system
trained on synthetic data eliminates the noisy phrase pairs using language
models trained on the target-side corpus. This process corresponds to lines
4—23 in Algorithm 1. The phrase table can be refined in either of two ways:
forward and backward refinement.

For forward refinement (Marie and Fujita, 2018), target synthetic data were
generated from the source monolingual data using the source-to-target phrase
table $P_{s\to t}^{(0)}$ and target language models $LM_{t}$. A new phrase
table $P_{s\to t}^{(1)}$ was then created with this target synthetic corpus.
This operation was executed $N$ times.

For backward refinement (Artetxe et al., 2018b), source synthetic data were
generated from the target monolingual data using the target to source phrase
table $P_{t\to s}^{(0)}$ and source language model $LM_{s}$. A new source to
target phrase table $P_{s\to t}^{(1)}$ was created with this source synthetic
parallel corpus. Next, target synthetic data were generated from the source
monolingual data using $P_{s\to t}^{(1)}$ and target language model $LM_{t}$.
The target to source phrase table $P_{t\to s}^{(1)}$ was built using this
target synthetic data.

#### Construction of a comparable corpus

This unsupervised method is based on the assumption that the source and target
corpora are comparable. In fact, Lample et al. (2018), Artetxe et al. (2018b)
and Marie and Fujita (2018) use the News Crawl of source and target language
as training data.

To make a comparable corpus for GEC, we use translated texts using Google
Translation as the source-side data. Specifically, we use Finnish News Crawl
translated into English as source-side. English News Crawl is used as the
target-side as is. Finnish data is used because Finnish is not similar to
English.

This translated data does not include misspelled words. To address these
words, we use a spell checker as a preprocessing step before inference.

Corpus | Sent. | Learner
---|---|---
Training data |  |
Fi News Crawl | 1,904,880 | No
En News Crawl | 2,116,249 | No
One-Billion | 24,482,651 | No
for CoNLL-14 |  |
CoNLL-13 | 1,312 | Yes
for JFLEG test |  |
JFLEG dev | 754 | Yes
for W&I+LOCNESS (BEA2019) |
tuning data | 2,191 | Yes
dev data | 2,193 | Yes
Table 1: Data statics: train and dev data size.

##  3 Experiment of low resource GEC

###  3.1 Experimental setting

Table 1 shows the training and development data size. Unless mentioned
otherwise, Finnish News Crawl 2014—2015 translated into English was used as
source training data and English News Crawl 2017 was used as target training
data. To train the extra language model of the target-side ($LM_{t}$), we used
training data of One Billion Word Benchmark (Chelba et al., 2014). We used
`googletrans v2.4.0`333https://github.com/ssut/py-googletrans for Google
Translation and obtained 2,122,714 translated sentences. We sampled the
3,000,000 sentences from English News Crawl 2017 and excluded the sentences
with more than 150 words for either source- and target-side data. Finally, the
synthetic comparable corpus comprises processed News Crawl data listed in
Table 1.

Our system was verified using three GEC datasets, CoNLL-14 (Ng et al., 2014),
JFLEG test set (Napoles et al., 2017) and W&I+LOCNESS (Bryant et al., 2019;
Granger, 1998). We used the CoNLL-13 dataset (Ng et al., 2013) and JFLEG dev
set as tuning data for CoNLL-14 and JFLEG test, respectively. The low resource
track at BEA2019 permitted to use W&I+LOCNESS development set, so we split it
in half; tune data and dev data444Because W&I+LOCNESS data has four types of
learner level, we split it so that each learner level is equal..

These data were tokenized by `spaCy
v1.9.0`555https://github.com/explosion/spaCy and the `en_core_web_sm-1.2.0`
model for W&I+LOCNESS. For CoNLL-14 and JFLEG test set, `NLTK` (Bird, 2006)
tokenizer was used. We used moses truecaser for the training data; this
truecaser model was learned from processed English News Crawl. We used byte-
pair-encoding (Sennrich et al., 2016b) learned from processed English News
Crawl; the number of operations was 50K.

The implementation made by Artetxe et al.
(2018b)666https://github.com/artetxem/monoses was modified to conduct the
experiments. Specifically, some features were added; word-level Levenshtein
distance, word-, and character-level edit operation, operation sequence model
(Durrani et al., 2013)777Operation sequence model was used in the refinement
step., and 9-gram word class language model888 This class language model was
not used when training target to source model., similar to Grundkiewicz and
Junczys-Dowmunt (2018) without sparse features. Word class language model was
trained with One Billion Word Benchmark data; the number of classes is 200,
and the word class was estimated with `fastText` (Bojanowski et al., 2017).
The distortion feature was not used.

`Moses` (Koehn et al., 2007) was used to train the SMT system. `FastAlign`
(Dyer et al., 2013) was used for word alignment and `KenLM` (Heafield, 2011)
was used to train the 5-gram language model over each processed English News
Crawl and One Billion Word Benchmark. MERT (Och, 2003) was used with `M^2
Scorer` (Dahlmeier and Ng, 2012) for the tuning data of CoNLL-13 and
W&I+LOCNESS and with `GLEU` (Napoles et al., 2015) for the tuning data of
JFLEG. Synthetic sentence pairs with a [3, 80] sentence length were used at
the refinement step. The number of iterations $N$ was set to 3 or 5, and the
embedding dimension was set to 300. For the low resource track, we decided
best iteration of forward refinement with the dev data and submitted the
output of the best iteration model.

We used `pyspellchecker`999https://github.com/barrust/pyspellchecker as a
spell checker. This tool uses Levenshtein distance to obtain permutations
within an edit distance of 2 over the words included in a word list. We made
the word list from One Billion Word Benchmark and included words that occur
more than five times.

For comparison, supervised GEC with SMT and neural MT (NMT) were conducted
using the data extracted from Lang-8 (Mizumoto et al., 2011) as for CoNLL-14
and JFLEG. In supervised SMT, the feature weights were tuned and the setting
was the same as that in unsupervised SMT (USMT). In supervised NMT, a
convolutional Encoder–Decoder model (Gehring et al., 2017) was used and the
parameter settings were similar to those in Ge et al. (2018).

We report precision, recall, and $\mathrm{F_{0.5}}$ score for CoNLL-14 and
W&I+LOCNESS data and GLEU score for JFLEG test set. The output of CoNLL-14 and
W&I+LOCNESS dev data was evaluated using $\mathrm{M^{2}}$ scorer and ERRANT
scorer (Bryant et al., 2017), respectively.

|  | CoNLL-14 ($\mathrm{M^{2}}$) | JFLEG
---|---|---|---
| iter | P | R | $\mathrm{F_{0.5}}$ | GLEU
No edit | - | - | - | - | 40.54
Supervised NMT | - | 53.11 | 26.47 | 44.21 | 54.04
Supervised SMT | - | 43.02 | 33.18 | 40.61 | 55.93
Unsupervised SMT | 0 | 21.82 | 36.75 | 23.75 | 49.94
w/ forward_refine | 1 | 25.92 | 32.65 | 27.04 | 50.65
| 2 | 25.58 | 31.02 | 26.51 | 50.19
| 3 | 23.95 | 33.13 | 24.54 | 50.40
w/ backward_refine | 1 | 22.39 | 33.39 | 23.97 | 49.02
| 2 | 24.96 | 27.13 | 25.36 | 48.90
| 3 | 26.07 | 21.01 | 24.87 | 48.75

Table 2: $\mathrm{M^{2}}$ and GLEU results. The bold scores represent the best
score in unsupervised SMT. The underlined scores represent the best overall
score.

###  3.2 CoNLL-14 and JFLEG Results

Table 2 shows the results of the GEC experiments for CoNLL-14 and JFLEG. The
$\mathrm{F_{0.5}}$ score for USMTforward in iter 1 is 13.57 points lower than
that of supervised SMT and 17.17 points lower than that of supervised NMT. On
JFLEG, the highest score was achieved with USMTforward in iter 1 among the
unsupervised SMT models; its GLEU scores are 5.28 points and 3.39 points lower
than those of supervised SMT and supervised NMT, respectively.

According to the improvement of iteration from 0 to 1, it is confirmed that
the forward refinement works well. However, it is observed that the system
with forward refinement ceases to improve after iteration 1. In forward
refinement, the source-side data is not changed, and target-side data is
generated from the source-side for each iteration. Therefore, the quality of
the source-side data is important for this refinement method. In this study,
we use the automatically translated text as source-side data; thus, it is
considered that the quality is not high and the refinement after iteration 1
does not work.

Src | Precision | Recall | $\mathrm{F_{0.5}}$
---|---|---|---
Fi News Crawl | 29.17 | 28.52 | 29.04
Ru News Crawl | 27.11 | 29.84 | 27.62
Fr News Crawl | 25.05 | 30.27 | 25.94
De News Crawl | 23.26 | 26.04 | 25.04
Table 3: The effect of source languages for comparable corpus creation. These
News Crawl corpora are as of 2017 version. The number of sentences in each
dataset is approximately 20M, respectively. These results are obtained by
USMTforward in iter 1.

#### Difference between forward and backward refinements

To examine how different the refinement methods are, we counted the number of
corrections predicted by each method. The number of USMTforward in iter 1 and
iter 2 is 3,437 and 3,257, respectively, whereas that of USMTbackward in iter
1 and iter 2 is 4,092 and 2,789. As for USMTbackward, the number of
corrections from iter 1 to iter 2 decreases by 1,303. Artetxe et al. (2018b)
and Lample et al. (2018) reported that the BLEU score (Papineni et al., 2002)
of unsupervised MT with backward-refinement improves with increasing
iterations. In GEC, increasing the iterations of USMTbackward improves the GEC
accuracy by predicting less corrections.

Team | TP | FP | FN | P | R | $\mathrm{F_{0.5}}$
---|---|---|---|---|---|---
UEDIN-MS | 2,312 | 982 | 2,506 | 70.19 | 47.99 | 64.24
Kakao&Brain | 2,412 | 1,413 | 2,797 | 63.06 | 46.30 | 58.80
LAIX | 1,443 | 884 | 3,175 | 62.01 | 31.25 | 51.81
CAMB-CUED | 1,814 | 1,450 | 2,956 | 55.58 | 38.03 | 50.88
UFAL, Charles University, Prague | 1,245 | 1,222 | 2,993 | 50.47 | 29.38 | 44.13
Siteimprove | 1,299 | 1,619 | 3,199 | 44.52 | 28.88 | 40.17
WebSpellChecker.com | 2,363 | 3,719 | 3,031 | 38.85 | 43.81 | 39.75
TMU | 1,638 | 4,314 | 3,486 | 27.52 | 31.97 | 28.31
Buffalo | 446 | 1,243 | 3,556 | 26.41 | 11.14 | 20.73
Table 4: GEC results with W&I+LOCNESS test data.

The GLEU score for USMTforward is considered higher than that for USMTbackward
because the language model makes up for the synthetic target data. To compare
the fluency, the outputs of each best iter on JFLEG were evaluated with the
perplexity based on the Common Crawl language
model101010http://data.statmt.org/romang/gec-emnlp16/cclm.tgz. The perplexity
of USMTforward in iter 1 is 179.23 and that of USMTbackward in iter 1 is
187.49; hence, the perplexity suggests USMTforward produces more likely
outputs than USMTbackward under the language model of Common Crawl text.

#### Effect of the source language

We also examine how source languages of machine translation affect
performance. Table 3 shows the result in changing the source-side data on
CoNLL-14. The outputs using Finnish data is the best score among various
languages; the more similar to English the source-side data is, the lower the
$\mathrm{F_{0.5}}$ score of the output.

| iter | P | R | $\mathrm{F_{0.5}}$
---|---|---|---|---
Unsupervised SMT | 0 | 12.33 | 16.13 | 12.94
w/ forward_refinement | 1 | 17.59 | 14.63 | 16.91
w/o spell check | 2 | 17.30 | 14.15 | 16.56
| 3 | 16.04 | 14.17 | 15.63
| 4 | 17.06 | 14.01 | 16.35
| 5 | 15.88 | 13.88 | 15.44
spell check $\to$ SMT | 1 | 20.58 | 18.04 | 20.01
SMT $\to$ spell check | 1 | 19.42 | 16.86 | 18.85

Table 5: GEC results with dev data. The bold scores represent the best score
without the spell checker.

###  3.3 W&I+LOCNESS Results

Table 4 shows the results of the GEC experiments with official test data for
W&I+LOCNESS. The $\mathrm{F_{0.5}}$ score for our system (TMU) is 28.31; this
score is eighth among the nine teams. In particular, the number of false
positives of our system is 4,314; this is the worst result of all.

Table 5 shows the results of the dev data listed in Table 1. On the dev data,
the system of iteration 1 is the best among all. This tendency is the same as
the CoNLL and JFLEG results.

The results of Table 5 confirm that the spell checker works well. We also
investigate the importance of the order; SMT or spell check, which is suitable
for the first system for a better result? As a result, it is better to use the
SMT system after using the spell checker. That is because the source-side data
does not include the misspelled words as mentioned above.

| P | R | $\mathrm{F_{0.5}}$
---|---|---|---
Easy2 |  |  |
SPELL | 39.93 | 59.24 | 42.71
PUNCT | 28.91 | 38.14 | 30.38
Hard2 |  |  |
NOUN | 0.87 | 1.74 | 0.97
VERB | 2.13 | 0.99 | 1.73
Table 6: Error types for which our best system corrected errors well or badly
on the dev data. Easy2 denotes the easiest two errors, and Hard2 denotes the
hardest two errors in terms of the $\mathrm{F_{0.5}}$111111We investigate the
frequent error types; the errors occur more than one hundred times in the dev
data..

Table 11 shows the error types that our system corrected well or badly on the
dev data. SPELL means the misspell errors; the correction of these errors
depends only on the spell checker. PUNCT means the errors about the
punctuation; e.g., ‘Unfortunately when we…$\to$ Unfortunately, when we…’. It
is considered that our system can correct errors such as these owing to the
n-gram co-occurrence knowledge derived from the language models.

In contrast, our system struggled to correct content word errors. For example,
NOUN includes an error like this; ‘way $\to$ means’ and VERB includes an error
like this; ‘watch $\to$ see’. It is considered that our system is mostly not
able to correct the word usage errors based on the context because the phrase
table is still noisy. Although we observed some usage error examples of
‘watch’ in the synthetic source data, our model was not able to replace
‘watch’ to ‘see’ based on the context.

##  4 Related Work

#### Unsupervised Machine Translation

Studies on unsupervised methods have been conducted for both NMT (Lample et
al., 2018; Marie and Fujita, 2018) and SMT (Artetxe et al., 2018b). In this
study, we apply the USMT method of Artetxe et al. (2018b) and Marie and Fujita
(2018) to GEC. The UNMT method (Lample et al., 2018) was ineffective under the
GEC setting in our preliminary experiments.

#### GEC with NMT/SMT

Several studies that introduce sequence-to-sequence models in GEC heavily rely
on large amounts of training data. Ge et al. (2018), who presented state-of-
the-art results in GEC, proposed a supervised NMT method trained on corpora of
a total 5.4 M sentence pairs. On the other hand, we mainly use the monolingual
corpus and use small learner data as the tuning data.

Despite the success of NMT, many studies on GEC traditionally use SMT (Susanto
et al., 2014; Junczys-Dowmunt and Grundkiewicz, 2014). These studies apply an
off-the-shelf SMT toolkit, Moses, to GEC. Junczys-Dowmunt and Grundkiewicz
(2014) claimed that the SMT system optimized for BLEU learns to not change the
source sentence. Instead of BLEU, they proposed tuning an SMT system using the
$\mathrm{M^{2}}$ score with annotated development data. In this study, we also
tune the weights with an $\mathrm{F_{0.5}}$ score measured by the
$\mathrm{M^{2}}$ scorer.

#### Low-resource GEC

Park and Levy (2011) proposed a GEC system based on a noisy channel model
using an unannotated corpus of learner English. In contrast, our method does
not require an unannotated corpus but requires monolingual corpora. Bryant and
Briscoe (2018) built a GEC system using minimally annotated data. Their model
used LM and confusion sets based on the common English error types. Our method
does not require knowledge about the common error types. Miao et al. (2019)
proposed a language generation method using Metropolis-Hastings sampling. This
method does not require parallel corpora for training, instead, monolingual
data is required. They evaluate it on a variety of tasks including GEC and
report that the GLEU score of 45.5 on JFLEG. Because we used a parallel corpus
for tuning weights, their results cannot be compared with ours. Zhao et al.
(2019) reported that a neural GEC model was improved only with denoising auto-
encoder, which was trained using a synthetic parallel corpus. Their parallel
corpus was generated by adding artificial errors, such as random deletion of a
token, to monolingual data instead of using machine translation.

##  5 Conclusion

In this paper, we described our GEC system with minimally annotated data. We
introduced an unsupervised approach based on SMT for GEC. This method requires
a comparable corpus, so we created a synthetic comparable corpus using Google
Translation. The experimental results demonstrate that our system achieved an
$\mathrm{F_{0.5}}$ score of 28.31 points with the W&I+LOCNESS test data.

## References

  * Artetxe et al. (2018a) Mikel Artetxe, Gorka Labaka, and Eneko Agirre. 2018a.  A robust self-learning method for fully unsupervised cross-lingual mappings of word embeddings.  In _Proc. of ACL_ , pages 789–798.
  * Artetxe et al. (2018b) Mikel Artetxe, Gorka Labaka, and Eneko Agirre. 2018b.  Unsupervised statistical machine translation.  In _Proc. of EMNLP_ , pages 3632–3642.
  * Bird (2006) Steven Bird. 2006.  NLTK: The natural language toolkit.  In _Proc. of COLING/ACL Interactive Presentation Sessions_ , pages 69–72.
  * Bojanowski et al. (2017) Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomas Mikolov. 2017.  Enriching word vectors with subword information.  _Transactions of the Association for Computational Linguistics_ , 5:135–146.
  * Bryant and Briscoe (2018) Christopher Bryant and Ted Briscoe. 2018.  Language model based grammatical error correction without annotated training data.  In _Proc. of BEA_ , pages 247–253, New Orleans, Louisiana.
  * Bryant et al. (2019) Christopher Bryant, Mariano Felice, Øistein E. Andersen, and Ted Briscoe. 2019\.  The BEA-2019 Shared Task on Grammatical Error Correction.  In _Proc. of BEA_.
  * Bryant et al. (2017) Christopher Bryant, Mariano Felice, and Ted Briscoe. 2017.  Automatic annotation and evaluation of error types for grammatical error correction.  In _Proc. of ACL_ , pages 793–805.
  * Chelba et al. (2014) Ciprian Chelba, Tomas Mikolov, Mike Schuster, Qi Ge, Thorsten Brants, Phillipp Koehn, and Tony Robinson. 2014.  One billion word benchmark for measuring progress in statistical language modeling.  In _Proc. of INTERSPEECH_ , pages 2635–2639.
  * Dahlmeier and Ng (2012) Daniel Dahlmeier and Hwee Tou Ng. 2012.  Better evaluation for grammatical error correction.  In _Proc. of NAACL-HLT_ , pages 568–572.
  * Durrani et al. (2013) Nadir Durrani, Alexander Fraser, Helmut Schmid, Hieu Hoang, and Philipp Koehn. 2013\.  Can Markov models over minimal translation units help phrase-based smt?  In _Proc. of ACL_ , pages 399–405.
  * Dyer et al. (2013) Chris Dyer, Victor Chahuneau, and Noah A. Smith. 2013.  A simple, fast, and effective reparameterization of IBM model 2.  In _Proc. of NAACL-HLT_ , pages 644–648.
  * Ge et al. (2018) Tao Ge, Furu Wei, and Ming Zhou. 2018.  Reaching human-level performance in automatic grammatical error correction: An empirical study.  _arXiv preprint arXiv:1807.01270_.
  * Gehring et al. (2017) Jonas Gehring, Michael Auli, David Grangier, Denis Yarats, and Yann N Dauphin. 2017\.  Convolutional sequence to sequence learning.  In _Proc. of ICML_ , pages 1243–1252.
  * Granger (1998) Sylviane Granger. 1998.  The computer learner corpus: A versatile new source of data for SLA research.  In Sylviane Granger, editor, _Learner English on Computer_ , pages 3–18. Addison Wesley Longman, London and New York.
  * Grundkiewicz and Junczys-Dowmunt (2018) Roman Grundkiewicz and Marcin Junczys-Dowmunt. 2018.  Near human-level performance in grammatical error correction with hybrid machine translation.  In _Proc. of NAACL-HLT_ , pages 284–290.
  * Heafield (2011) Kenneth Heafield. 2011.  KenLM: Faster and smaller language model queries.  In _Proc. of WMT_ , pages 187–197.
  * Junczys-Dowmunt and Grundkiewicz (2014) Marcin Junczys-Dowmunt and Roman Grundkiewicz. 2014.  The AMU system in the CoNLL-2014 shared task: Grammatical error correction by data-intensive and feature-rich statistical machine translation.  In _Proc. of CoNLL_ , pages 25–33.
  * Koehn et al. (2007) Philipp Koehn, Hieu Hoang, Alexandra Birch, Chris Callison-Burch, Marcello Federico, Nicola Bertoldi, Brooke Cowan, Wade Shen, Christine Moran, Richard Zens, Chris Dyer, Ondrej Bojar, Alexandra Constantin, and Evan Herbst. 2007.  Moses: Open source toolkit for statistical machine translation.  In _Proc. of ACL Demo Sessions_ , pages 177–180.
  * Lample et al. (2018) Guillaume Lample, Myle Ott, Alexis Conneau, Ludovic Denoyer, and Marc’Aurelio Ranzato. 2018.  Phrase-based & neural unsupervised machine translation.  In _Proc. of EMNLP_ , pages 5039–5049.
  * Marie and Fujita (2018) Benjamin Marie and Atsushi Fujita. 2018.  Unsupervised neural machine translation initialized by unsupervised statistical machine translation.  _arXiv preprint arXiv:1810.12703_.
  * Miao et al. (2019) Ning Miao, Hao Zhou, Lili Mou, Rui Yan, and Lei Li. 2019.  CGMH: Constrained sentence generation by metropolis-hastings sampling.  In _Proc. of AAAI_.
  * Mikolov et al. (2013) Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013.  Efficient estimation of word representations in vector space.  In _ICLR Workshop_.
  * Mizumoto et al. (2011) Tomoya Mizumoto, Mamoru Komachi, Masaaki Nagata, and Yuji Matsumoto. 2011.  Mining revision log of language learning SNS for automated Japanese error correction of second language learners.  In _Proc. of IJCNLP_ , pages 147–155.
  * Napoles et al. (2015) Courtney Napoles, Keisuke Sakaguchi, Matt Post, and Joel Tetreault. 2015.  Ground truth for grammatical error correction metrics.  In _Proc. of ACL-IJCNLP_ , pages 588–593.
  * Napoles et al. (2017) Courtney Napoles, Keisuke Sakaguchi, and Joel Tetreault. 2017.  JFLEG: A fluency corpus and benchmark for grammatical error correction.  In _Proc. of EACL_ , pages 229–234.
  * Ng et al. (2014) Hwee Tou Ng, Siew Mei Wu, Ted Briscoe, Christian Hadiwinoto, Raymond Hendy Susanto, and Christopher Bryant. 2014.  The CoNLL-2014 shared task on grammatical error correction.  In _Proc. of CoNLL Shared Task_ , pages 1–14.
  * Ng et al. (2013) Hwee Tou Ng, Siew Mei Wu, Yuanbin Wu, Christian Hadiwinoto, and Joel Tetreault. 2013\.  The CoNLL-2013 shared task on grammatical error correction.  In _Proc. of CoNLL_ , pages 1–12.
  * Och (2003) Franz Josef Och. 2003.  Minimum error rate training in statistical machine translation.  In _Proc. of ACL_ , pages 160–167.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  BLEU: a method for automatic evaluation of machine translation.  In _Proc. of ACL_ , pages 311–318.
  * Park and Levy (2011) Y. Albert Park and Roger Levy. 2011.  Automated whole sentence grammar correction using a noisy channel model.  In _Proc. of ACL_ , pages 934–944, Portland, Oregon, USA.
  * Sennrich et al. (2016a) Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016a.  Improving neural machine translation models with monolingual data.  In _Proc. of ACL_ , pages 86–96.
  * Sennrich et al. (2016b) Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016b.  Neural machine translation of rare words with subword units.  In _Proc. of ACL_ , pages 1715–1725.
  * Susanto et al. (2014) Raymond Hendy Susanto, Peter Phandi, and Hwee Tou Ng. 2014.  System combination for grammatical error correction.  In _Proc. of EMNLP_ , pages 951–962.
  * Xie et al. (2018) Ziang Xie, Guillaume Genthial, Stanley Xie, Andrew Ng, and Dan Jurafsky. 2018.  Noising and denoising natural language: Diverse backtranslation for grammar correction.  In _Proc. of NAACL-HLT_ , pages 619–628.
  * Zhao et al. (2019) Wei Zhao, Liang Wang, Kewei Shen, Ruoyu Jia, and Jingming Liu. 2019.  Improving grammatical error correction via pre-training a copy-augmented architecture with unlabeled data.  In _Proc. of NAACL-HLT_ , pages 156–165.


# Total Positivity of Almost-Riordan Arrays

Tian-Xiao He  Department of Mathematics, Illinois Wesleyan University,
Bloomington, IL 61702-2900, Indiana, USA  Roksana Słowik  Faculty of Applied
Mathematics, Silesian University of Technology, Kaszubska 23, 44-100 Gliwice,
Poland

###### Abstract

In this paper we study the total positivity of almost-Riordan arrays
$(d(t)|\,g(t),f(t))$ and establish its necessary conditions and sufficient
conditions, particularly, for some well used formal power series $d(t)$. We
present a semidirect product of an almost-array and use it to transfer a total
positivity problem for an almost-Riordan array to the total positivity problem
for a quasi-Riordan array. We find the sequence characterization of total
positivity of the almost-Riordan arrays. The production matrix $J$ of an
almost-Riordan array $(d|\,g,f)$ is presented so that $J$ is totally positive
implies the total positivity of both the almost-Riordan array $(d|\,g,f)$ and
the Riordan array $(g,f)$. We also present a counterexample to illustrate that
this sufficient condition is not necessary. If the production matrix $J$ is
tridiagonal, then the expressions of its principal minors are given. By using
expressions, we find a sufficient and necessary condition of the total
positivity of almost-Riordan arrays with tridiagonal production matrices. A
numerous examples are given to demonstrate our results.

AMS Subject Classification: 05A15, 05A05, 15B36, 15A06, 05A19, 11B83.

Key Words and Phrases: Riordan array, Riordan group, almost-Riordan array,
almost-Riordan group, quasi-Riordan array.

##  1 Introduction

Following Karlin [11] and Pinkus [13], an infinite matrix is called totally
positive (abbreviately, TP), if its minors of all orders are nonnegative. An
infinite nonnegative sequence $(a_{n})_{n\geq 0}$ is called a Pólya frequency
sequence (abbreviately, PF), if its Toeplitz matrix

$\left[a_{i-j}\right]_{i,j\geq 0}=\left[\begin{array}[]{lllll}a_{0}&&&&\\\
a_{1}&a_{0}&&&\\\ a_{2}&a_{1}&a_{0}&&\\\ a_{3}&a_{2}&a_{1}&a_{0}&\\\
\vdots&\vdots&\vdots&\vdots&\ddots\end{array}\right]$

is TP. We say that a finite sequence $(a_{0},a_{1},\ldots,a_{n})$ is PF if the
corresponding infinite sequence $(a_{0},a_{1},\ldots,a_{n},0,\ldots)$ is PF.
Denote by ${{\mathbb{N}}}$ the set of all nonnegative integers. A fundamental
characterization for PF sequences is given by Schoenberg et al.[1, 2, 11],
which states that a sequence $(a_{n})_{n\geq 0}$ is PF if and only if its
generating function can be written as

$\sum_{n\geq 0}a_{n}t^{n}=Ct^{k}e^{\gamma t}\frac{\Pi_{j\geq
0}(1+\alpha_{j}t)}{\Pi_{j\geq 0}(1-\beta_{j}t)},$ (1)

where $C>0$, $k\in{{\mathbb{N}}}$, $\alpha_{j}$, $\beta_{j}$, $\gamma\geq 0$,
and $\sum_{j\geq 0}(\alpha_{j}+\beta_{j})<\infty$. In this case, the above
generating function is called a Pólya frequency formal power series. For some
relevant results, see, for example, Brenti [10] and Pinkus [13].

Let us denote by $\mbox{$\mathcal{F}$}_{k}$ the set of all formal power series
of the form $\sum_{n=k}^{\infty}a_{n}t^{n}$ with $a_{k}\neq 0$.

######  Definition 1.1.

[4] Let $d,g\in\mbox{$\mathcal{F}$}_{0}$ with $d(0),g(0)=1$ and
$f\in\mbox{$\mathcal{F}$}_{1}$ with $f^{\prime}(0)=1$. We call the following
matrix an almost-Riordan array with respect to $d,g,$ and $f$ and denote it by
$(d|\,g,f)$:

$(d|\,g,f)=(d,tg,tgf,tgf^{2},\cdots),$ (2)

where $d$, $tg$, $tgf$, $t^{2}gf\cdots$, are the generating functions of the
$0$th, $1$st, $2$nd, $3$rd, $\cdots$, columns of the matrix $(d|\,g,f)$,
respectively.

It is clear that $(d|\,g,f)$ can be written as

$(d|\,g,f)=\left(\begin{matrix}d(0)&0\\\ (d-d(0))/t&(g,f)\end{matrix}\right),$
(3)

where $(g,f)=(g,gf,gf^{2},\ldots)$, a Riordan array. Particularly, if $d=g$
and $f=t$, then the almost-Riordan array $(d|\,g,f)$ reduces to the Appell-
type Riordan array $(g,t)$.

Barry, Pantelidis, and one of the authors [5] present the following analogy
for the almost-Riordan arrays.

######  Theorem 1.2.

[5] The set of all almost-Riordan arrays defined by (2) forms a group, denoted
by $a{{\cal R}}$, with respect to the multiplication defined by

$(a|\,g,f)(b|\,d,h)=\left(\left.a+\frac{tg}{f}(b(f)-1)\right|\,gd(f),h(f)\right),$
(4)

where $a,g,b,d\in\mbox{$\mathcal{F}$}_{0}$ with $a(0),g(0),b(0),d(0)=1$ and
$f,h\in\mbox{$\mathcal{F}$}_{1}$ with $f^{\prime}(0)=1$ and $h^{\prime}(0)=1$,
respectively, and $(a|\,g,f)$ and $(b|\,d,h)$ are the almost-Riordan arrays
defined by (2) or (3).

Let us introduce one more group that is closely related to the groups of
Riordan and almost-Riordan arrays.

######  Definition 1.3.

[8] Let $g\in\mbox{$\mathcal{F}$}_{0}$ with $g(0)=1$ and
$f\in\mbox{$\mathcal{F}$}_{1}$. We call the following matrix a quasi-Riordan
array and denote it by $[g,f]$.

$[g,f]:=(g,f,tf,t^{2}f,\ldots),$ (5)

where $g$, $f$, $tf$, $t^{2}f\cdots$ are the generating functions of the
$0$th, $1$st, $2$nd, $3$rd, $\cdots$, columns of the matrix $[g,f]$,
respectively. It is clear that $[g,f]$ can be written as

$[g,f]=\left(\begin{matrix}g(0)&0\\\ (g-g(0))/t&(f/t,t)\end{matrix}\right),$
(6)

where $(f,t)=(f,tf,t^{2}f,t^{3}f,\ldots)$ and $(f/t,t)$ is an Appell Riordan
array. Particularly, if $f=tg$, then the quasi-Riordan array $[g,tg]=(g,t)$, a
Appell-type Riordan array.

Clearly, $[g,f]=(g|f/t,t)$.

Let $A$ and $B$ be $m\times m$ and $n\times n$ matrices, respectively. Then we
define the direct sum of $A$ and $B$ by

$A\oplus B=\left[\begin{matrix}A&0\\\
0&B\end{matrix}\right]_{(m+n)\times(m+n)}.$ (7)

In this notation the Riordan array $(g,f)$ satisfies (see for instance [12])

$(g,f)=[g,f]([1]\oplus(g,f)).$ (8)

Denote by $q{{\cal R}}$ the set of all quasi-Riordan arrays defined by (5). In
[8] it is shown that $q{{\cal R}}$ is a group with respect to regular matrix
multiplication. More precisely, there is the following result.

######  Theorem 1.4.

[8] The set of all quasi-Riordan arrays $q{{\cal R}}$ is a group, called the
quasi-Riordan group, with respect to the multiplication represented in

$[g,f][d,h]=\left[g+\frac{f}{t}(d-1),\frac{fh}{t}\right],$ (9)

which is derived from the first fundamental theorem for quasi-Riordan arrays
(FFTQRA),

$[g,f]u=gu(0)+\frac{f}{t}(u-u(0)).$ (10)

Hence, $[1,t]$ is the identity of $q{{\cal R}}$.

In [5], it has been shown that the quasi-Riordan group is a normal subgroup of
the almost-Riordan group. In authors’ paper [9], we discussed the total
positivity of quasi-Riordan arrays. For instance, let $(g(t),f(t))$ be a
Riordan array, where $g(t)=\sum_{n\geq 0}g_{n}t^{n}$ and $f(t)=\sum_{n\geq
1}f_{n}t^{n}$. If the lower triangular matrix

$\begin{array}[]{rl}Q&=[g,f]=(g|f/t,t)=\left[\begin{array}[]{llllll}g_{0}&0&0&0&0&\cdots\\\
g_{1}&f_{1}&0&0&0&\cdots\\\ g_{2}&f_{2}&f_{1}&0&0&\cdots\\\
g_{3}&f_{3}&f_{2}&f_{1}&0&\cdots\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\ddots\end{array}\right]\\\
&=\left(g(t),f(t),tf(t),t^{2}f(t),\ldots\right)\\\ \end{array}$ (11)

is totally positive (TP), then so is $R=(g,f)$ (cf. [12] or [8, 9]). Other
interesting criteria for total positivity of Riordan arrays can be found in
[6, 7].

In this paper we are going to focus on total positivity of almost-Riordan
arrays and its connections with total positivity of Riordan and almost-Riordan
arrays.

According to the definition of the almost-Riordan array, if an almost-Riordan
array $(d|\,g,f)$ is TP, then the corresponding Riordan array $(g,f)$ shown in
(3) must be TP. In other words, a necessary condition for the total positivity
of an almost- Riordan array is that its corresponding Riordan array is TP.
Therefore, the discussion of total positivity covers the discussion of total
positivity of Riordan arrays, noting that research on the latter is still
ongoing and attracts many researchers. However, in this paper we are
interested in two questions regarding the total positivity of almost-Riordan
arrays. The first is the conditions for finding $d$ in an almost Riordan array
$(d|\,g,f)$ that has a corresponding TP Riordan array $(g,f)$ such that
$(d|\,g,f)$ is TP. The second is to determine the sequence characteristics of
the TP almost-Riordan array. Let $(d|\,g,f)$ be the almost-Riordan array of
$d_{0}=1$, then the generating function of its $A$-, $Z$\- and $W$\- sequences
is given by the following formula (see [3])

$\displaystyle A(t)=\frac{t}{\overline{f}(t)},$ (12) $\displaystyle
Z(t)=\frac{t(g(\overline{f}(t))-z_{0}d(\overline{f}(t))}{\overline{f}(t)g(\overline{f}(t)))}+z_{0},$
(13) $\displaystyle
W(t)=\frac{t(d(\overline{f}(t))-d_{0}-w_{0}\overline{f}(t)d(\overline{f}(t)))}{(\overline{f}(t))^{2}g(\overline{f}(t))}+w_{0},$
(14)

where $z_{0}=g_{0}$ and $w_{0}=d_{1}$.

In particular, for the quasi-Riordan array $[d,g]=(d|\,g/t,t)$, the generating
functions of its $A$-, $Z$-, and $W$-sequences are reduced to

$\displaystyle A(t)=1,$ (15) $\displaystyle
Z(t)=\frac{g(t)-z_{0}td(t)}{g(t)}+z_{0},$ (16) $\displaystyle
W(t)=\frac{(1-w_{0}t)d(t)-1}{g(t)}+w_{0},,$ (17)

For instance, for quasi-Riordan array $[1/(1-t),t/(1-t)]$, $A(t)=Z(t)=W(t)=1$.

The first problem will be discussed in Section $2$ is about the total
positivity of almost-Riordan arrays $(d|\,g,f)$ for some special power series
$d$ when the Riordan array $(g,f)$ is TP. More precisely, we give a necessary
condition for the total positivity of an almost-Riordan array $(d|\,g,f)$ and
sufficient conditions for the the total positivity of an almost-Riordan arrays
$(d|\,g,f)$ when $d(t)=1,tg(t)+\alpha$, and $d_{0}+d_{1}t$,
$\alpha,d_{0},d_{1}\in{{\mathbb{R}}}$, respectively. We also present a
semidirect product of an almost-array and use it to transfer a total
positivity problem of an almost-Riordan array to the total positivity problem
of a quasi-Riordan array. In Section 3, we study the sequence characterization
of TP almost-Riordan arrays. The production matrix $J$ of an almost-Riordan
array $(d|\,g,f)$ is presented and the following general result is claimed:
The $J$ is TP implies the total positivity of both the almost-Riordan array
$(d|\,g,f)$ and the Riordan array $(g,f)$. We also use a counterexample to
illustrate that $J$ being TP does not necessarily mean that its corresponding
almost-Riordan array is TP. If the production matrix $J$ is tridiagonal, then
the expressions of its principal minors can be obtained. By using the
expressions, we find a sufficient and necessary condition of the total
positivity of almost-Riordan arrays with tridiagonal production matrices. In
the remaining of Section 3, numerous example are given to demonstrate our
results.

##  2 Total positivity of certain almost-Riordan arrays

Let us consider two special cases for $d$ in a Riordan array and discuss its
TP and the TP for the corresponding almost-Riordan array.

Based on the discussion in the Introduction, we have

######  Proposition 2.1.

If the almost-Riordan array $(d|\,g,f)$ is $TP$, then the Riordan array
$(g,f)$ is $TP$.

If $d(t)=1$, then from (6) we have

$(d|\,g,f)=\left(\begin{matrix}1&0\\\ 0&(g,f)\end{matrix}\right).$

Hence, one can observe

######  Proposition 2.2.

The almost-Riordan array $(1|\,g,f)$ is $TP$ if and only if the Riordan array
$(g,f)$ is $TP$.

In particular, if $g$ and $f$ are Pólya frequency power series, then the
matrix $(g,f)$ is TP, which implies that $(1|\,g,f)$ is TP [7].

The following example shows there exists a non-TP almost-Riordan array
$(d|\,g,f)$, in which $d$, $g$ and $f$ are Pólya frequency.

######  Example 2.3.

Let $d(t)=(1+t)^{2}$, $g(t)=1/(1-t)$, and $f(t)=t$. Then $d(t)$, $g(t)$ and
$f(t)$ are Pólya frequency, and

$(g,f)=\begin{bmatrix}1&&&&&\\\ 1&1&&&&\\\ 1&1&1&&&\\\ 1&1&1&1&&\\\
1&1&1&1&1&\\\ \vdots&&&&&\ddots\\\ \end{bmatrix}$

is TP. However, we have

$(d|\,g,f)=[(1+t)^{2},t/(1-t)]=\begin{bmatrix}1&&&&&\\\ 2&1&&&&\\\ 1&1&1&&&\\\
0&1&1&1&&\\\ 0&&1&1&1&\\\ \vdots&&&&&\ddots\\\ \end{bmatrix}$

whose minor

$M^{1,2,3}_{0,1,2}=\det\left(\begin{array}[]{lll}2&1&0\\\ 1&1&1\\\
0&1&1\end{array}\right)=-1<0.$

Hence, $(d|\,g,f)$ is not TP although $(g,f)$ is TP and $d$ is Pólya
frequency.

The following example shows there exists a class of TP almost-Riordan arrays
$(d|\,g,f)$, which $d=1+d_{1}t$ is Pólya frequency, $g(t)=f(t)/t$, and
$f(t)=f_{1}t+f_{2}t^{2}$. Since

$(d|\,f/t,f)=[d,f]=\left[\begin{array}[]{llll}1&0&&\\\ d_{1}&f_{1}&0&\\\
&f_{2}&f_{1}&\\\ &&f_{2}&\\\ &\ddots&\ddots&\ddots\end{array}\right].$

Hence, from Proposition 2.6 of [6, Proposition 2.6], $(d|\,f/t,t)$is TP if and
only if $f_{1}\geq 0$, which implies that $[1+d_{1}t,f_{1}t+f_{2}t^{2}]$ is TP
if $d_{1},f_{1},f_{2}\geq 0$.

From the above examples, we may see quasi-Riordan arrays as the elements of
the normal subgroup of almost-Riordan group make important rule in our
discussion.

As we have seen, the most interesting question here is whether having fixed
$(g,f)$ can we choose $d$ in such way to ensure total positivity of $(d|g,f)$
and what, in such case, is the connection between $d$ and the pair $(g,f)$.

For every Riordan array $(g,f)$ there exists $d$ such that the almost- Riordan
array $(d|g,f)$ is TP. In fact, we have

######  Theorem 2.4.

Suppose $g\in\mbox{$\mathcal{F}$}_{0}$, $f\in\mbox{$\mathcal{F}$}_{1}$ such
that the Riordan array $(g,f)$ is TP. Then the almost-Riordan array
$\left(t\cdot g+\alpha|\,g,f\right)$ is also TP for every $\alpha>0$.

###### Proof.

Observe that the Riordan array $\left(t\cdot g+\alpha|\,g,f\right)=R$ can be
written in the partitioned form

$R=\left[\begin{array}[]{c|c}\alpha&0\\\ \hline\cr g&(g,f)\\\
\end{array}\right].$

We now consider its minors.

  1. 1.

If a minor of $R$ does not contain the column $0$, then it is simply a minor
of $(g,f)$, so it is nonnegative.

  2. 2.

Suppose now that a minor of $R$ contains the column $0$.

    1. (a)

If it contains the row $0$, then expanding along it, we get a minor of $(g,f)$
multiplied by $\alpha$ which is a nonnegative number.

    2. (b)

If this minor does not contain the row $0$, then it is a minor of the
partitioned matrix

$\tilde{R}=\left[\begin{array}[]{c|c|c}g_{0}&g_{0}&0\\\
\hline\cr\frac{g-g_{0}}{t}&\frac{g-g_{0}}{t}&\left(\frac{gf}{t},f\right)\\\
\end{array}\right].$

      1. i.

Now, if minor contains both the two first columns of $\tilde{R}$, then it is
equal to $0$.

      2. ii.

If the minor contains one or none of the first two columns of $\tilde{R}$,
then it is simply one of the minors of $(g,f)$, so it is nonnegative.

∎

Moreover, for every TP array $(g,f)$ there exist $d$ that does not depend on
$g$ and $f$ such that $(d|g,f)$ is TP.

######  Theorem 2.5.

Let $g\in\mbox{$\mathcal{F}$}_{0}$, $f\in\mbox{$\mathcal{F}$}_{1}$ and let
$d=d_{0}+d_{1}t$ with $d_{0},d_{1}\geqslant 0$. If the Riordan array $(g,f)$
is TP, then $(d_{0}+d_{1}t|\,g,f)$ is also TP.

###### Proof.

Let

$R=(d_{0}+d_{1}t|\,g,f)=\left[\begin{array}[]{c|c}d_{0}&0\\\ \hline\cr
d_{1}&\\\ 0&(g,f)\\\ \vdots&\\\ \end{array}\right].$

Consider the minors of $R$.

  1. 1.

If a minor does not contain the column $0$, then it is a minor of $(g,f)$
that, by the assumption, is nonnegative.

  2. 2.

Suppose now that a minor contains the column $0$.

    1. (a)

If it contains the row $0$, then, after expansion along this row, one gets a
minor of $(g,f)$ multiplied by $d_{0}$ which is a nonnegative number.

    2. (b)

If it does not contain the row $0$, but it contains the first row, then it is
a minor of

$\tilde{R}=\left[\begin{array}[]{c|c|c}d_{1}&g_{0}&0\\\ \hline\cr
0&\frac{g-g_{0}}{t}&\left(\frac{gf}{t},f\right)\\\ \end{array}\right].$

Thus, expanding now along the column $0$, we get a minor of $(g,f)$ multiplied
by $d_{1}$ that is nonnegative.

    3. (c)

If it does not contain neither the zeroth nor the first row, then it is a
minor of

$\tilde{R}=\left[\begin{array}[]{c|c|c}0&\frac{g-g_{0}}{t}&\left(\frac{gf}{t},f\right)\\\
\end{array}\right]$

and it is equal to $0$.

∎

It is known that every Riordan array $(g,f)$ can be written as the semidirect
product

$(g,f)=(g,t)(1,f).$

Consequently, we have the following result.

######  Proposition 2.6.

Every almost-Riordan array $(d|\,g,f)$ can be written as the semidirect
product

$(d|\,g,f)=[d,tg](1|\,1,f),$ (18)

or equivalently,

$(d|\,g,f)=\left[\begin{array}[]{c|c}d_{0}&0\\\
\hline\cr\frac{d-d_{0}}{t}&(g,t)\\\
\end{array}\right]\left[\begin{array}[]{c|c}1&0\\\ \hline\cr 0&(1,f)\\\
\end{array}\right].$ (19)

###### Proof.

From the factorization of Riordan arrays shown above, we may prove the
theorem. ∎

Clearly, the total positivity of the two matrices from the above decomposition
ensures the total positivity of $R$. Suppose that both $g$ and $f$ are Pólya
frequency formal power series. Then, from [7], we know that $(g,f)$ is TP.
Thus, to obtain $d$ from $(\ref{eq:R_factoriz})$ such that $(d|\,g,f)$ is TP,
we only need to focus on $d$.

Summing up, we get the following

######  Corollary 2.7.

Let $d,g\in\mbox{$\mathcal{F}$}_{0}$, $f\in\mbox{$\mathcal{F}$}_{1}$. If $f$
is a Pólya frequency formal power series and the quasi-Riordan array $[d,tg]$
is TP, then the almost-Riordan array $(d|\,g,f)$ is also TP.

Thus, if $f$ is an arbitrary Pólya frequency formal power series, then in
order to construct totally positive almost-Riordan array $(d|\,g,f)$ it
suffices to discuss the total positivity of the quasi-Riordan array $[d,tg]$.

######  Example 2.8.

Let us consider $g(t)=\frac{1}{1-\alpha t}$ and
$d(t)=\displaystyle\sum_{n=0}^{\infty}d_{n}t^{n}$ in $[d,tg]$, where $tg(t)$
is a Pólya frequency formal power series. The quasi-Riordan array $[d,tg]$ is
a special case of an almost-Riordan array. From [9] we know that if its
production matrix

$J=\left[\begin{array}[]{llllll}w_{0}&z_{0}&&&&\\\ w_{1}&z_{1}&1&&&\\\
w_{2}&z_{2}&0&1&&\\\ w_{3}&z_{3}&0&0&1&\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\ddots\end{array}\right]$

is TP, where $Z(t)=\sum_{n\geq 0}z_{n}t^{n}$ and $W(t)=\sum_{n\geq
0}w_{n}t^{n}$ are represented in (16) and (17), then $[d,g]$ is also TP.

Moreover, also from [9, Theorem 3.4], we know that $J$ is TP if and only if
$Z(t)=z_{0}+z_{1}t$, $W(t)=w_{0}+w_{1}t$, and $w_{0}z_{1}-w_{1}z_{0}\geqslant
0$. For the given $g=1/(1-\alpha t)$, from (13) and (14), we have

$\displaystyle Z(t)=z_{0}+z_{1}t=\frac{\frac{t}{1-\alpha
t}-z_{0}td(t)}{\frac{t}{1-\alpha t}}+z_{0},\quad\textrm{and}$ $\displaystyle
W(t)=w_{0}+w_{1}t=\frac{(1-w_{0}t)d(t)-1}{\frac{t}{1-\alpha t}}+w_{0}.$

Assume $z_{0}=1$. The above system has solution

$d(t)=\frac{1-z_{1}t}{1-\alpha t}$

if

$w_{0}=\alpha-z_{1}\quad\textrm{and}\quad w_{1}=z_{1}(\alpha-z_{1}).$

Denote $z_{1}=\beta$, those conditions come down to

$Z(t)=1+\beta
t,\,\,W(t)=\alpha-\beta+(\alpha\beta-\beta^{2})t,\,\,\mbox{and}\,\,d(t)=\frac{1-\beta
t}{1-\alpha t}$

Since $w_{0},w_{1}\geq 0$, we obtain $0\leq\beta\leq\alpha$. Note that the
necessary and sufficient condition of the total positivity of quasi-Riordan
array shown in [9, Theorem 3.4] is satisfied, i.e.

$w_{0}z_{1}-w_{1}z_{0}=w_{0}\beta-
w_{1}=(\alpha-\beta)\beta-(\alpha\beta-\beta^{2})=0\,\,\textrm{for all
}\alpha,\beta.$

Consequently, for any $\beta\in\left[0,\alpha\right]$ and any Pólya frequency
formal power series $f$, the almost-Riordan array $\left(\frac{1-\beta
t}{1-\alpha t}|\frac{1}{1-\alpha t},f(t)\right)$ is TP.

Similarly as in the previous example, if we replace $g(t)$ to be $\alpha$,
then $J$ is TP only if $w_{0}=z_{1}=w_{1}=0$, and $\alpha=d(t)=1$ when
$z_{0}=1$.

##  3 Sequence Characterization of the TP Almost-Riordan Arrays

We now discuss the sequence characterization of the TP almost-Riordan arrays.
We start from a general case of the characteristic sequence with the
generating functions shown in (12)-(14).

###  3.1 General result

We call the following matrix the production matrix of the almost-Riordan
matrix $[g,f]$:

$J=\left[\begin{array}[]{llllll}w_{0}&z_{0}&&&&\\\ w_{1}&z_{1}&a_{0}&&&\\\
w_{2}&z_{2}&a_{1}&a_{0}&&\\\ w_{3}&z_{3}&a_{2}&a_{1}&a_{0}&\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\ddots\end{array}\right]$ (20)

It can be checked that

$(d|g,f)J=\overline{(d|g,f)},$ (21)

where $\overline{(d|\,g,f)}$ is the matrix by deleting the first row of
$(d|\,g,f)$.

######  Proposition 3.1.

Let $(d|\,g,f)$ and $J$ be two matrices defined by (5) and (20), respectively.
If $J$ is TP, then so are $(d|\,g,f)$ and $(g,f)$.

###### Proof.

It can be proved by using (21) and mathematical induction. ∎

###  3.2 The tridiagonal case

Let us consider some special form of $J$. As from Thm.4.3 [13] we know that a
Jacobi matrix

$\left[\begin{matrix}a_{1}&b_{1}&&&&\\\ c_{1}&a_{2}&b_{2}&&&\\\
&c_{2}&a_{3}&b_{3}&&\\\ &&\ddots&\ddots&\ddots&\\\ &&&&c_{n-1}&a_{n}\\\
\end{matrix}\right]$

is TP if and only if its all elements and its all principal minors containing
consecutive rows and columns are nonnegative, we conclude that in order to
check total positivity of production matrix of the tridiagonal form

$J=\left[\begin{matrix}w_{0}&z_{0}&&&&&\\\ w_{1}&z_{1}&a_{0}&&&&\\\
&z_{2}&a_{1}&a_{0}&&&\\\ &&a_{2}&a_{1}&a_{0}&&\\\ &&&a_{2}&a_{1}&a_{0}&\\\
&&&&\ddots&\ddots&\ddots\\\ \end{matrix}\right]$

it suffices to check the principal minors. Principal minor $J_{n}$ of degree
$n$ of the above $J$ is equal to

$\det(J_{n})=\begin{cases}w_{0}&\textrm{for }n=1\\\
w_{0}z_{1}-z_{0}w_{1}&\textrm{for }n=2\\\
w_{0}z_{1}a_{1}-w_{0}z_{2}a_{0}-w_{1}z_{0}a_{1}&\textrm{for }n=3\\\
(w_{0}z_{1}-w_{1}z_{0})\det(T_{n-2})-w_{0}z_{2}a_{0}\det(T_{n-3})&\textrm{for
}n>3,\\\ \end{cases}$ (22)

where $T_{n}$ stands for the $n\times n$ Toeplitz matrix

$T_{n}=\left[\begin{matrix}a_{1}&a_{0}&&&&\\\ a_{2}&a_{1}&a_{0}&&&\\\
&a_{2}&a_{1}&a_{0}&&\\\ &&\ddots&\ddots&\ddots&\\\ &&&a_{2}&a_{1}&a_{0}\\\
&&&&a_{2}&a_{1}\\\ \end{matrix}\right],$ (23)

whose determinant can be found by using its expansion along the first column:

$\begin{array}[]{rl}\det(T_{n})&=a_{1}\det(T_{n-1})-a_{0}a_{2}\det(T_{n-2})\\\
&=\begin{cases}\frac{1}{\sqrt{a_{1}^{2}-4a_{0}a_{2}}}\left[\left(\frac{a_{1}+\sqrt{a_{1}^{2}-4a_{0}a_{2}}}{2}\right)^{n+1}-\left(\frac{a_{1}-\sqrt{a_{1}^{2}-4a_{0}a_{2}}}{2}\right)^{n+1}\right]\\\
\hskip 170.71652pt\textrm{ if }a_{1}^{2}-4a_{0}a_{2}\neq 0\\\
(n+1)\left(\frac{a_{1}}{2}\right)^{n}\\\ \hskip 170.71652pt\textrm{ if
}a_{1}^{2}-4a_{0}a_{2}=0,\\\ \end{cases}\\\ \end{array}$ (24)

where the numbers $\frac{a_{1}+\sqrt{a_{1}^{2}-4a_{0}a_{2}}}{2}$,
$\frac{a_{1}-\sqrt{a_{1}^{2}-4a_{0}a_{2}}}{2}$, and $\frac{a_{1}}{2}$ are, in
fact, the roots of the characteristic equation

$x^{2}-a_{1}x+a_{0}a_{2}=0$

of the determinant of $T_{n}$. We assume here that
$\sqrt{a_{1}^{2}-4a_{0}a_{2}}$ is the principal root of
$a_{1}^{2}-4a_{0}a_{2}$. Note that, from the recurrence relation, it follows
that the determinant given by $(\ref{eq:det(T_n)})$ is always real.

Let us discuss first the case when the characteristic equation has a single
root.

######  Theorem 3.2.

Suppose that $a_{0},a_{1},a_{2},z_{0},z_{1},z_{2},w_{0},w_{1}\geqslant 0$ and
$a_{1}^{2}=4a_{0}a_{2}$. If the numbers

$w_{0}z_{1}-w_{1}z_{0},\quad\mbox{and}\quad
w_{0}z_{1}a_{1}-w_{1}z_{0}a_{1}-2w_{0}z_{2}a_{0}$

are nonnegative, then the almost-Riordan array $(d|g,f)$ defined by its
sequence characterization shown in Eqs. (12)-(14) is TP.

###### Proof.

By the assumptions $a_{1}^{2}=4a_{0}a_{2}$, $a_{1}\geqslant 0$, and
$(\ref{eq:det(T_n)})$, we get that $\det(T_{n})\geqslant 0$. To show
$det(J_{n})\geqslant 0$, by $(\ref{eq:det(J_n)})$, it suffices to check the
signs of the expressions

$\begin{array}[]{l}w_{0}z_{1}-z_{0}w_{1},\quad
w_{0}z_{1}a_{1}-w_{0}z_{2}a_{0}-w_{1}z_{0}a_{1}=(w_{0}z_{1}-w_{1}z_{0})a_{1}-w_{0}z_{2}a_{0},\\\
(w_{0}z_{1}-w_{1}z_{0})(n-1)\left(\frac{a_{1}}{2}\right)^{n-2}-w_{0}z_{2}a_{0}(n-2)\left(\frac{a_{1}}{2}\right)^{n-3}\textrm{
for }n>3.\\\ \end{array}$

The last expression is nonnegative due to

$\frac{a_{1}(w_{0}z_{1}-w_{1}z_{0})}{2w_{0}z_{2}a_{0}}\geqslant\frac{n-2}{n-1}\quad\textrm{for
all }n>3,$

and $\sup_{n>3}\left\\{\frac{n-2}{n-1}\right\\}=1$. Therefore, we need to have

$w_{0}z_{1}-z_{0}w_{1},(w_{0}z_{1}-z_{0}w_{1})a_{1}-w_{0}a_{0}z_{2},(w_{0}z_{1}-z_{0}w_{1})a_{1}-2w_{0}a_{0}z_{2}\geqslant
0,$

which are guaranteed by the conditions given by the theorem and the following
inequality:

$(w_{0}z_{1}-w_{1}z_{0})a_{1}-w_{0}z_{2}a_{0}\geqslant(w_{0}z_{1}-w_{1}z_{0})a_{1}-2w_{0}z_{2}a_{0}.$

∎

Case when the characteristic equation has two roots, requires considering two
more cases. First, consider the situation of the two real roots.

######  Theorem 3.3.

Suppose that $a_{0},a_{1},a_{2},z_{0},z_{1},z_{2},w_{0},w_{1}\geqslant 0$ and
$a_{1}^{2}-4a_{0}a_{2}>0$. If the numbers

$w_{0}z_{1}-z_{0}w_{1},\quad w_{0}z_{1}a_{1}-w_{0}z_{2}a_{0}-w_{1}z_{0}a_{1}$

are nonnegative, then the almost-Riordan array $(d|\,g,f)$ defined by its
sequence characterization shown in (12)-(14) is TP.

###### Proof.

Clearly, the two numbers from the claim come from Eq.$(\ref{eq:det(J_n)})$,
whereas nonnegativity of $a_{0}$, $a_{1}$, $a_{2}$ and positivity of
$a_{1}^{2}-4a_{0}a_{2}$ ensure the positivity of roots of the characteristic
equation and consequently of the difference
$\left(\frac{a_{1}+\sqrt{a_{1}^{2}-4a_{0}a_{2}}}{2}\right)^{n+1}-\left(\frac{a_{1}-\sqrt{a_{1}^{2}-4a_{0}a_{2}}}{2}\right)^{n+1}$.
∎

For two complex roots we have the following.

######  Theorem 3.4.

Let $a_{0},a_{1},a_{2},z_{0},z_{1},z_{2},w_{0},w_{1}\geqslant 0$. If
$a_{1}^{2}-4a_{0}a_{2}<0$, then there exists $n\in\mathbb{N}$ such that
$\det(T_{n})<0$.

###### Proof.

Let us shortly write $r$ for the modulus of
$\frac{a_{1}+i\sqrt{4a_{0}a_{2}-a_{1}^{2}}}{2}$ (note that since
$a_{1}^{2}-4a_{0}a_{2}<0$, we can treat $\sqrt{4a_{0}a_{2}-a_{1}^{2}}$ as the
arithmetic root) and $\theta$ for its argument. Since
$4a_{0}a_{2}-a_{1}^{2}>0$, $\theta\in\left(0,\frac{\pi}{2}\right]$. With this
notation we have

$\begin{array}[]{rl}\det(T_{n})&=\frac{1}{i\sqrt{4a_{0}a_{2}-a_{1}^{2}}}\cdot
r^{n+1}\left(e^{(n+1)i\theta}-e^{-(n+1)i\theta}\right)\\\
&=\frac{2r^{n+1}}{\sqrt{4a_{0}a_{2}-a_{1}^{2}}}\sin\left((n+1)\theta\right).\\\
\end{array}$

If $\theta=\frac{\pi}{2}$, then for $n=2$, we obtain $\sin\frac{3\pi}{2}=-1$
in the above expression, so $\det(T_{2})<0$.

If $\theta<\frac{\pi}{2}$, then there exists a number $n$, $n\geqslant 2$,
such that $\frac{\pi}{n+1}<\theta<\frac{2\pi}{n+1}$. Then
$\pi<(n+1)\theta<2\pi$, so the corresponding sine function value in the above
expression is negative, and so is $\det(T_{n+1})$. ∎

######  Example 3.5.

As Theorem 3.4 indicates, the negativity of $\det(T_{n})$ is only a “matter of
time” in the sense that the sign of $\det(T_{n})$ depends on the index. For
instance, choosing $a_{0}=2$, $a_{1}=3$, $a_{2}=5$, we have
$\arg(3+\sqrt{31}i)\approx 0.343\pi$, and $\det(T_{2})=-4$. Yet, choosing
$a_{0}=a_{2}=3$, $a_{1}=5$, we have $\arg(5+\sqrt{11}i)\approx 0.186\pi$. In
this case $\det(T_{2})$, $\det(T_{3})$, $\det(T_{4})$ are positive and only
$\det(T_{5})$ is the first one to be negative.

Theorems 3.3 and 3.4 sum up in the following.

######  Theorem 3.6.

Suppose that $a_{0},a_{1},a_{2},z_{0},z_{1},z_{2},w_{0},w_{1}\geqslant 0$ and
$a_{1}^{2}-4a_{0}a_{2}\neq 0$. The production matrix $J$ is TP if and only if

$a_{1}^{2}-4a_{0}a_{2}>0,\quad w_{0}z_{1}-w_{1}z_{0},\quad
w_{0}z_{1}a_{1}-w_{0}z_{2}a_{0}-w_{1}z_{0}a_{1}\geqslant 0.$

From (12)-(14) we have

$\displaystyle d(t)=\frac{d_{0}(1-z_{1}t-z_{2}tf(t))}{F(t)}$ (25)
$\displaystyle g(t)=\frac{d_{0}z_{0}}{F(t)}$ (26) $\displaystyle
f(t)=\frac{1-a_{1}t-\sqrt{(a_{1}^{2}-4a_{2}a_{0})t^{2}-2a_{1}t+1}}{2a_{2}t},$
(27)

where

$F(t)=1-(w_{0}+z_{1})t+(w_{0}z_{1}-w_{1}z_{0})t^{2}-z_{2}(1-w_{0}t)tf(t).$
(28)

The above formulas can be used to find out the TP almost-Riordan array
$(d|\,g,f)$ from the characteristic sequences of a TP almost-Riordan array.

###  3.3 Examples of TP almost-Riordan arrays

Using the results presented at the start of this section, we can provide some
examples of TP almost-Riordan arrays.

######  Example 3.7.

Defining the family of the sequences $A$, $Z$, $W$ as

$A(t)=1+\alpha t+\frac{\alpha^{2}}{4}t^{2},\quad Z(t)=1+t+t^{2},\quad
W(t)=1+\beta t,$

and denoting the family of the sequences $A$, $Z$, and $W$ by
$AZW_{1}(\alpha,\beta)$, from Theorem 3.6 we conclude that the production
matrix $J$ (20) is TP if and only if

$\alpha,\beta\geqslant 0,\quad\alpha(1-\beta)\geqslant 2,$

what is depicted on Fig.1.

Figure 1: Figure of Ex.3.7$2$$1$$\alpha$$\beta$$\beta=1-\frac{2}{\alpha}$

Consequently, by Proposition 3.1 and above calculations, we obtain the almost-
Riordan arrays with their characterized sequences in the family

$\\{AZW_{1}(\alpha,\beta):\alpha,\beta\geqslant 0,\beta\leqslant
1-2/\alpha\\}.$

For instance, for $(\alpha,\beta)=(2,0)$, that is

$A(t)=1+2t+t^{2},\quad Z(t)=1+t+t^{2},\quad W(t)=1,$

Assuming that $d_{0}=1$, we obtain TP almost-Riordan array

$R=\left(d(t)|g(t),h(t)\right)=\left[\begin{array}[]{ccccccc}1&&&&&&\\\
1&1&&&&&\\\ 1&2&1&&&&\\\ 1&4&4&1&&&\\\ 1&9&13&6&1&&\\\ 1&23&41&26&8&1&\\\
\vdots&&&&&&\ddots\\\ \end{array}\right]$

where from (25)-(28) we have $F(t)=(1-t)(1-t-tf(t))$ and

$\begin{array}[]{l}d(t)=\frac{1}{1-t},\\\
g(t)=\frac{d(t)}{1-t-tf(t)}=\frac{2}{(1-t)(1+\sqrt{1-4t})},\\\
f(t)=\frac{1-2t-\sqrt{1-4t}}{2t}.\\\ \end{array}$

For $(\alpha,\beta)=\left(4,\frac{1}{3}\right)$ we obtain another TP almot-
Riordan array

$R=\left(d(t)|g(t),h(t)\right)=\left[\begin{array}[]{ccccccc}1&&&&&&\\\
1&1&&&&&\\\ \frac{4}{3}&2&1&&&&\\\ 2&\frac{13}{3}&6&1&&&\\\
\frac{31}{9}&\frac{37}{3}&\frac{97}{3}&10&1&&\\\
\frac{68}{9}&\frac{433}{9}&\frac{545}{3}&\frac{229}{3}&14&1&\\\
\vdots&&&&&&\ddots\\\ \end{array}\right]$

with

$\begin{array}[]{l}d(t)=\frac{3\left[1-t-tf(t)\right]}{3-6t+2t^{2}+(3t^{2}-3t)f(t)}=\frac{3\left(7-4t+\sqrt{1-8t}\right)}{24-48t+16t^{2}+(3t-3)\left(1-4t-\sqrt{1-8t}\right)},\\\
g(t)=\frac{3}{3-6t+2t^{2}+(3t^{2}-3t)f(t)}=\frac{24}{24-48t+16t^{2}+(3t-3)\left(1-4t-\sqrt{1-8t}\right)},\\\
f(t)=\frac{1-4t-\sqrt{1-8t}}{8t}.\\\ \end{array}$

######  Example 3.8.

Putting now

$A(t)=1+\alpha t+\frac{\alpha^{2}}{4}t^{2},\quad Z(t)=1+t+\beta t^{2},\quad
W(t)=1+\frac{1}{2}t,$

denoting the family of the above sequences by $AZW_{2}(\alpha,\beta)$, and
using Theorem 3.6 we derive this time that the corresponding production matrix
$J$ (20) is TP if and only if

$0\leqslant\beta\leqslant\frac{\alpha}{4}.$

Figure 2: Figure of Ex.3.8$2$$1$$\alpha$$\beta$$\beta=\frac{\alpha}{4}$

We denote the family of the characterized sequences by
$\\{AZW_{2}(\alpha,\beta):0\leq\beta\leq\alpha/4\\}$, which feasible region is
shown in Figure 2. Hence, the almost-Riordan arrays with their characterized
sequences in this family, for instance, $(\alpha,\beta)=(1,1/4)$,
$(1/2,1/16)$, etc., are TP.

For instance for $(\alpha,\beta)=\left(1,\frac{1}{4}\right)$, we obtain TP
almost-Riordan array

$R=\left(d(t)|g(t),h(t)\right)=\left[\begin{array}[]{ccccccc}1&&&&&&\\\
1&1&&&&&\\\ \frac{3}{2}&2&1&&&&\\\ \frac{5}{2}&\frac{15}{4}&3&1&&&\\\
\frac{35}{8}&7&7&4&1&&\\\ \frac{63}{8}&\frac{105}{8}&15&\frac{45}{4}&5&1&\\\
\vdots&&&&&&\\\ \end{array}\right]$

with

$\begin{array}[]{l}d(t)=\frac{1-t+\sqrt{1-2t}}{1-2t+(1-t)\sqrt{1-2t}},\\\
g(t)=\frac{2}{1-2t+(1-t)\sqrt{1-2t}},\\\ f(t)=\frac{2(1-t-\sqrt{1-2t})}{t}.\\\
\end{array}$

Another example can be

$R=\left[\begin{array}[]{ccccccc}1&&&&&&\\\ 1&1&&&&&\\\ \frac{3}{2}&2&1&&&&\\\
\frac{5}{2}&\frac{57}{16}&\frac{5}{2}&1&&&\\\
\frac{137}{32}&\frac{199}{32}&\frac{39}{8}&3&1&&\\\
\frac{473}{64}&\frac{1383}{128}&\frac{283}{32}&\frac{103}{16}&\frac{7}{2}&1&\\\
\vdots&&&&&&\ddots\\\ \end{array}\right]$

for $(\alpha,\beta)=\left(\frac{1}{2},\frac{1}{16}\right)$, with

$\begin{array}[]{l}d(t)=\frac{3t-2-2\sqrt{1-t}}{-t^{2}+5t-2+2(t-1)\sqrt{1-t}},\\\
g(t)=\frac{4}{2(1-t)\sqrt{1-t}+t^{2}-5t+2},\\\
f(t)=\frac{8-4t-8\sqrt{1-t}}{t}.\\\ \end{array}$

######  Example 3.9.

Let

$A(t)=1+\alpha t+t^{2},\quad Z(t)=1+t+t^{2},\quad W(t)=1+\beta t,$

with $\alpha>2$. Denote by $AZW_{3}(\alpha,\beta)$ the family of the sequences
$A$, $Z$, $W$ defined above. Then, by Theorem 3.6, the production matrix $J$
(20) is TP if and only if

$0\leqslant\beta\leqslant 1-\frac{1}{\alpha}.$

For instance, if
$(\alpha,\beta)\in\\{AZW_{3}(\alpha,\beta):\alpha>2,0\leqslant\beta\leqslant
1-\frac{1}{\alpha}\\}$ (see its feasible region in Figure 3), say
$(\alpha,\beta)=(2,0)->(3,0)$ and $(4,1/3)$, the corresponding almost-Riordan
arrays with the characteristic sequences $AZW_{3}(2,0)$ and $AZW_{3}(4,1/3)$
are TP.

Figure 3: Figure of Ex.3.9$2$$1$$\alpha$$\beta$$\beta=1-\frac{1}{\alpha}$

For $(\alpha,\beta)=(3,0)$ we obtain TP almost-Riordan array

$R=\left(d(t)|g(t),f(t)\right)=\left[\begin{array}[]{ccccccc}1&&&&&&\\\
1&1&&&&&\\\ 1&2&1&&&&\\\ 1&4&5&1&&&\\\ 1&10&20&8&1&&\\\ 1&421&78&45&11&1&\\\
\vdots&&&&&&\ddots\\\ \end{array}\right]$

with

$\begin{array}[]{l}d(t)=\frac{1}{1-t},\\\
g(t)=\frac{2}{(1-t)(1+t+\sqrt{5t^{2}-6t+1})},\\\
f(t)=\frac{1-3t-\sqrt{5t^{2}-6t+1}}{2t},\\\ \end{array}$

whereas for $(\alpha,\beta)=\left(4,\frac{1}{3}\right)$

$R=\left(d(t)|g(t),f(t)\right)=\left[\begin{array}[]{ccccccc}1&&&&&&\\\
1&1&&&&&\\\ \frac{4}{3}&3&1&&&&\\\ 2&\frac{28}{3}&7&1&&&\\\
\frac{31}{9}&32&\frac{115}{3}&11&1&&\\\
\frac{68}{9}&\frac{1090}{9}&\frac{589}{3}&\frac{250}{3}&15&1&\\\
\vdots&&&&&&\ddots\\\ \end{array}\right]$

where

$\begin{array}[]{l}d(t)=\frac{-6t-3-3\sqrt{12t^{2}-8t+1}}{8t^{2}-3t-3+(3t-3)\sqrt{12t^{2}-8t+1}},\\\
g(t)=\frac{6}{3(1-t)\sqrt{12t^{2}-8t+1}-8t^{2}-3t+3},\\\
f(t)=\frac{1-4t-\sqrt{12t^{2}-8t+1}}{2t}.\\\ \end{array}$

######  Example 3.10.

Let this time

$A(t)=1+\alpha t+t^{2},\quad Z(t)=1+t+\beta t^{2},\quad W(t)=1+\frac{1}{3}t,$

with $2<\alpha\leqslant 3$. Denote by $AZW_{4}(\alpha,\beta)$ the family of
the sequences defined above. By Theorem 3.6, the production matrix $J$ (20) is
TP if and only if

$0\leqslant\beta\leqslant 1-\frac{\alpha}{3}.$

For instance, if
$(\alpha,\beta)\in\\{AZW_{4}(\alpha,\beta):3\geq\alpha>2,0\leq
0\leq\beta\leq\frac{1}{2}-\frac{\alpha}{6}\\}$ (see its feasible region in
Figure 4).

Figure 4: Figure of Ex.3.10$2$$1$$\alpha$$\beta$$\beta=1-\frac{\alpha}{3}$

The corresponding almost-Riordan array

$R=\left(d(t)|g(t),f(t)\right)=\left[\begin{array}[]{ccccccc}1&&&&&&\\\
1&1&&&&&\\\ \frac{4}{3}&2&1&&&&\\\ 2&\frac{10}{3}&5&1&&&\\\
\frac{28}{9}&\frac{16}{3}&\frac{58}{3}&8&1&&\\\
\frac{44}{9}&\frac{76}{9}&\frac{214}{3}&\frac{133}{3}&11&1&\\\
\vdots&&&&&&\ddots\\\ \end{array}\right]$

with the characteristic sequences $AZW_{4}(3,0)$ and

$\begin{array}[]{l}d(t)=\frac{3-3t}{2t^{2}-6t+3},\\\
g(t)=\frac{3}{2t^{2}-6t+3},\\\ f(t)=\frac{1-3t-\sqrt{5t^{2}-6t+1}}{2t},\\\
\end{array}$

is TP, as well as the array

$R=\left(d(t)|g(t),f(t)\right)=\left[\begin{array}[]{ccccccc}1&&&&&&\\\
1&1&&&&&\\\ \frac{17}{12}&2&1&&&&\\\
\frac{19}{8}&\frac{27}{8}&\frac{9}{2}&1&&&\\\
\frac{425}{96}&\frac{89}{16}&\frac{125}{8}&7&1&&\\\
\frac{297}{32}&\frac{1793}{192}&\frac{413}{8}&\frac{273}{8}&\frac{19}{2}&1&\\\
\vdots&&&&&&\ddots\\\ \end{array}\right]$

with the characteristic sequences
$AZW_{4}\left(2\frac{1}{2},\frac{1}{24}\right)$ and

$\begin{array}[]{l}d(t)=\frac{101t-98+\sqrt{9t^{2}-20t+4}}{(t-1)\sqrt{9t^{2}-20t+4}-59t^{2}+185t-94},\\\
g(t)=\frac{96}{(1-t)\sqrt{9t^{2}-20t+4}+59t^{2}-185t+94},\\\
f(t)=\frac{2-5t-\sqrt{9t^{2}-20t+4}}{4t}.\\\ \end{array}$

###  3.4 Counterexample

Proposition 3.1 raises a natural question: does the converse theorem also
hold? Specifically, is the production matrix $J$ TP for every TP almost-
Riordan array $R$? According to [14], since the direct sum of any Riordan
array with the matrix $\left[1\right]$ results in an almost-Riordan array, the
answer is negative. Nevertheless, we will present more example in our
discussion.

######  Example 3.11.

Since $f(t)=2t+t^{2}$ is a Pólya frequency formal power series, by Theorem
2.5, for every Pólya frequency formal power series $g(t)$ and any
$d(t)=d_{0}+d_{1}t$ with $d_{0},d_{1}>0$, the almost-Riordan array
$\left(d|g,f\right)$ is TP. Yet, since $\overline{f}(t)=\sqrt{t+1}-1$, we have

$A(t)=\sqrt{t+1}+1=2+\frac{t}{2}-\frac{t^{2}}{8}+\frac{t^{3}}{16}-\frac{5t^{4}}{128}+\frac{7t^{5}}{256}-\cdots$

Since $A$ has some negative coefficients, the production matrix $J$ is,
definitely, not TP.

For instance

$\displaystyle R=$
$\displaystyle(d(t)|\,g(t),f(t))=\left(1+3t|\,1+t,2t+t^{2}\right)$
$\displaystyle=$ $\displaystyle\left[\begin{matrix}1&&&&&&\\\ 3&1&&&&&\\\
0&1&2&&&&\\\ 0&0&3&4&&&\\\ 0&0&1&10&8&&\\\ 0&0&0&5&24&16&\\\
\vdots&&&&&&\ddots\\\ \end{matrix}\right]$

is TP, but its production matrix generated by

$\displaystyle A(t)=\sqrt{t+1}+1,$ $\displaystyle
Z(t)=\frac{\sqrt{t+1}-2t}{\sqrt{t+1}},\quad z_{0}=g_{0}/d_{0}=1$
$\displaystyle W(t)=\frac{3\sqrt{t+1}-9t}{\sqrt{t+1}},\quad
w_{0}=d_{1}/d_{0}=3,$

begins

$J=\left[\begin{matrix}3&1&&&&&\\\ -9&-2&2&&&&\\\
\frac{9}{2}&1&\frac{1}{2}&2&&&\\\
-\frac{27}{8}&-\frac{3}{4}&-\frac{1}{8}&\frac{1}{2}&2&&\\\
\frac{45}{16}&\frac{5}{8}&\frac{1}{16}&-\frac{1}{8}&\frac{1}{2}&2&\\\
\vdots&&&&&&\ddots\\\ \end{matrix}\right],$

which is not TP.

## References

  * [1] M. Aissen, A. Edrei, I.J. Schoenberg and A.M. Whitney, On the generating functions of totally positive sequences, Proc. Nat. Acad. Sci. U.S.A. 37 (1951), 303–307.
  * [2] M. Aissen, I.J. Schoenberg and A.M. Whitney, On the generating functions of totally positive sequences I, J. Analyse Math. 2 (1952), 93–103.
  * [3] Y. Alp and E. G. Kocer, Sequence characterization of almost-Riordan arrays, Linear Algebra Appl. 664 (2023), 1–23.
  * [4] P. Barry, On the Group of Almost-Riordan Arrays (2016), arXiv:1606.05077.
  * [5] P. Barry, T.-X. He, and N. Pantelidis, The quasi-Riordan group and the almost-Riordan group, manuscript in preparation.
  * [6] X. Chen, H. Liang and Y. Wang, Total positivity of Riordan arrays, European J. Combin. 46 (2015) 68–74.
  * [7] X. Chen and Y. Wang, Notes on the total positivity of Riordan arrays, Linear Algebra Appl. 569 (2019) 156–161.
  * [8] T.-X. He, The vertical recursive relation of Riordan arrays and its matrix representation, J. Integer Seq. 25 (2022), no. 9, Art. 22.9.5, 22 pp.
  * [9] T.-X. He and R. Slowik, Total positivity of quasi-Riordan arrays and Riordan arrays, submitted.
  * [10] F. Brenti, Combinatorics and total positivity, J. Combin. Theory Ser. A, 71 (1995) 175–218.
  * [11] S. Karlin, Total Positivity, Vol.1, Stanford University Press, 1968.
  * [12] J. Mao, L. Mu, and Y. Wang, Yet another criterion for the total positivity of Riordan arrays, Linear Algebra Appl. 634 (2022), 106–111.
  * [13] A. Pinkus, Totally Positive Matrices, Cambridge University Press, Cambridge, 2010.
  * [14] R. Slowik, Some (counter)examples on totally positive Riordan arrays, Linear Algebra Appl. 594 (2020), 117–123.


# On Difficulties of Attention Factorization through Shared Memory

Uladzislau Yorsh1, Ondřej Bojar1, Martin Holeňa2, David Herel2
1Charles University in Prague, 2Czech Technical University in Prague
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Transformers have revolutionized deep learning in numerous fields, including
natural language processing, computer vision, and audio processing. Their
strength lies in their attention mechanism, which allows for the discovering
of complex input relationships. However, this mechanism’s quadratic time and
memory complexity poses challenges for larger inputs. Researchers are now
investigating models like Linear Unified Nested Attention (Luna) or Memory
Augmented Transformer, which leverage external learnable memory to either
reduce the attention computation complexity down to linear, or to propagate
information between chunks in chunk-wise processing. Our findings challenge
the conventional thinking on these models, revealing that interfacing with the
memory directly through an attention operation is suboptimal, and that the
performance may be considerably improved by filtering the input signal before
communicating with memory.

††footnotetext: Code: https://github.com/vladyorsh/lra_efficient_transformers

##  1 Introduction & Related Work

In the era of big data and natural language processing, handling long-form
text is crucial. Transformers (Vaswani et al., 2017) have shown promise in
some tasks, but they do not scale well with longer inputs due to their
quadratic time and memory complexity inherent in their attention framework.
This challenge has given rise to multiple approaches designed to handle
sequences exceeding typical input lengths, including attention reformulation
for efficient computing (Rabe & Staats, 2021; Dao et al., 2022), exploration
of weight sharing techniques (Dehghani et al., 2018; Raffel et al., 2019),
heavy use of quantization (Shen et al., 2019) or replacing the attention
operation itself with a faster alternative.

In the present work, we focus on designs that alter the Transformer
architecture to lower the computational demands by leveraging an external
memory in the form of a set of learnable vectors. Models like Linear Unified
Nested Attention (Luna; Ma et al., 2021) or Perceiver (Jaegle et al., 2021)
use it to factorize an attention operation into a sequence of attentions with
a linear complexity, while the Memory Augmented Transformer (Wu et al., 2022)
processes long inputs chunk-by-chunk using the memory as a hidden state to
carry information between chunks. While these models adopt different
perspectives on long input processing, they all leverage the attention
mechanism as an interface for communication between the input and memory. The
latter can be used as a convenient fixed-length dense representation of sparse
inputs such as texts.

Given the properties of the attention operation, we discover the phenomenon
which does not allow to utilize multiple memory cells properly, which we call
memory degradation. Overcoming it may significantly improve the performance of
the named models, and we propose several tweaks which lead to noticeable
performance gains on the considered benchmarks.

##  2 Methodology and Experimental Setup

After inspecting the Luna and Set Transformer (Lee et al., 2019) memory states
during training, we have found out that they tend to converge to a single or a
small number of points. That means that the memory is not being used
completely, and this conclusion is being supported by the experimental results
from the Luna paper (Ma et al., 2021), where the differences in performance
between memory of sizes 16 and 256 are marginal. Unlike in vanilla
Transformers, the attention logits of an input-memory attention matrix remain
at relatively high entropy during training—the attention scores are
distributed almost uniformly, and the resulting value vectors are similar for
all input tokens.

(a) Luna memory

(b) Luna memory grad

(c) Set Transformer memory

(d) Set Transformer memory grad

Figure 1: Memory degradation illustrated. The horizontal axis is the feature
dimension, the vertical one is the memory vector index, and the color
indicates element values. Despite that memory matrices (learned parameters fed
to the first model block as a memory input $P$ on the Figure 3) were randomly
initialized, during training they converge to a small number of unique
vectors, see the vertical stripes on a) and b) and similar blocks on c) and
d).

As an attempt to counter the issue of the memory degradation, we experiment
with two techniques: filtering input before attending to the memory and
lowering the softmax temperature (see Appendices B and C for the detailed
description). The first technique consists in applying a convolution or a
pooling on the keys and values in the “packing” attention, leaving only the
relevant signal which can form a better new memory representation after the
attention. The second technique consists in replacing the $d^{-\frac{1}{2}}$
normalizing term in the attention equation with its learnable logarithm,
initialized at zero. We apply both techniques only on “packing” attention, and
refer to our model as ConvLuna.

We test our findings on the subset of the Long Range Arena (LRA; Tay et al.,
2020) benchmark. We do not report the score for the Pathfinding task, because
we have not managed to replicate the results of Ma et al. (2021). We provide a
more detailed description of the experimental setup in Appendix D and an
ablation study results in Appendix E.

Model | Classification $\uparrow$ | Matching $\uparrow$ | ListOps $\uparrow$ | CIFAR-10 $\uparrow$ | Average $\uparrow$
---|---|---|---|---|---
Transformer | 64.27 | 57.46 | 36.37 | 42.44 | 50.14
Luna-1 | 65.67 $\pm$ 0.18 | 75.46 $\pm$ 1.36 | 37.02 $\pm$ 0.12 | 49.06 $\pm$ 0.64 | 56.81
Luna-16 | 65.53 $\pm$ 0.08 | 75.93 $\pm$ 0.89 | 36.98 $\pm$ 0.30 | 50.36 $\pm$ 0.43 | 57.20
Luna-256 | 65.65 $\pm$ 0.35 | 79.44 $\pm$ 0.76 | 37.21 $\pm$ 0.22 | 50.90 $\pm$ 0.51 | 58.30
ConvLuna-1 | 82.10 $\pm$ 0.45 |  81.76 $\pm$ 0.73 | 43.95 $\pm$ 1.75 | 56.66 $\pm$ 0.44 | 66.12
ConvLuna-16 |  84.25 $\pm$ 0.16 | 80.47 $\pm$ 1.03 |  44.14 $\pm$ 0.69 |  56.93 $\pm$ 0.59 | 66.45
ConvLuna-256 | 83.29 $\pm$ 0.15 | 80.74 $\pm$ 1.08 | 43.56 $\pm$ 2.55 | 56.69 $\pm$ 0.64 | 65.90

Table 1: Vanilla Transformer and Luna compared with ConvLuna. We report
accuracy mean and standard deviation across five training runs for each setup.
Values for the vanilla Transformer are taken from (Tay et al., 2020), other
results are by us. Numbers in names indicate memory size.

##  3 Results and Conclusion

Our work demonstrates notable performance improvements on several kinds of
classification tasks through our proposed methods. We also find out that
models with even a single memory cell outperform the standard Transformer
model. These results highlight the inefficiency of the traditional direct
input-memory interfacing through attention, and suggest that pre-filtering
inputs before interacting with memory can lead to significant gains. However,
throughout our experiments we were not able to achieve statistically
significant impact of the memory size on the performance, which may indicate a
substantial scope for future enhancements in efficiency and effectiveness of
the architectures leveraging the external memory in a form of learnable
vectors.

### URM Statement

The authors acknowledge that at least one key author of this work meets the
URM criteria of ICLR 2024 Tiny Papers Track.

### Acknowledgments

Uladzislau Yorsh was supported by the grant №290223 of the Charles University
Grant Agency. Ondřej Bojar was supported by the grant 19-26934X (NEUREM3) of
the Czech Science Foundation.

## References

  * Dao et al. (2022) Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, and Christopher Ré.  Flashattention: Fast and memory-efficient exact attention with io-awareness, 2022.
  * Dehghani et al. (2018) Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser.  Universal transformers.  _CoRR_ , abs/1807.03819, 2018.  URL http://arxiv.org/abs/1807.03819.
  * García & Herrera (2008) Salvador García and Francisco Herrera.  An extension on “statistical comparisons of classifiers over multiple data sets” for all pairwise comparisons.  _Journal of Machine Learning Research_ , 9(89):2677–2694, 2008.  URL http://jmlr.org/papers/v9/garcia08a.html.
  * Jaegle et al. (2021) Andrew Jaegle, Felix Gimeno, Andrew Brock, Andrew Zisserman, Oriol Vinyals, and João Carreira.  Perceiver: General perception with iterative attention.  _CoRR_ , abs/2103.03206, 2021.  URL https://arxiv.org/abs/2103.03206.
  * Krizhevsky (2009) Alex Krizhevsky.  Learning multiple layers of features from tiny images.  Technical report, University of Toronto, Toronto, Ontario, 2009.  URL https://www.cs.toronto.edu/~kriz/learning-features-2009-TR.pdf.
  * Lee et al. (2019) Juho Lee, Yoonho Lee, et al.  Set transformer: A framework for attention-based permutation-invariant neural networks.  In _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pp. 3744–3753. PMLR, 09–15 Jun 2019.  URL https://proceedings.mlr.press/v97/lee19d.html.
  * Ma et al. (2021) Xuezhe Ma, Xiang Kong, Sinong Wang, Chunting Zhou, Jonathan May, Hao Ma, and Luke Zettlemoyer.  Luna: Linear unified nested attention, 2021.
  * Rabe & Staats (2021) Markus N. Rabe and Charles Staats.  Self-attention does not need o(n${}^{\mbox{2}}$) memory.  _CoRR_ , abs/2112.05682, 2021.  URL https://arxiv.org/abs/2112.05682.
  * Radev et al. (2009) Dragomir R. Radev, Pradeep Muthukrishnan, and Vahed Qazvinian.  The ACL Anthology network corpus.  In _Proceedings of the 2009 Workshop on Text and Citation Analysis for Scholarly Digital Libraries (NLPIR4DL)_ , pp. 54–61, Suntec City, Singapore, August 2009. Association for Computational Linguistics.  URL https://aclanthology.org/W09-3607.
  * Raffel et al. (2019) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _CoRR_ , abs/1910.10683, 2019.  URL http://arxiv.org/abs/1910.10683.
  * Shen et al. (2019) Sheng Shen, Zhen Dong, et al.  Q-BERT: hessian based ultra low precision quantization of BERT.  _CoRR_ , abs/1909.05840, 2019.  URL http://arxiv.org/abs/1909.05840.
  * Tay et al. (2020) Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler.  Long range arena: A benchmark for efficient transformers.  _CoRR_ , abs/2011.04006, 2020.  URL https://arxiv.org/abs/2011.04006.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, et al.  Attention is all you need.  In _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.  URL https://proceedings.neurips.cc/paper_files/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf.
  * Wu et al. (2022) Qingyang Wu, Zhenzhong Lan, et al.  Memformer: A memory-augmented transformer for sequence modeling.  In _Findings of the Association for Computational Linguistics: AACL-IJCNLP 2022_ , pp. 308–318, Online only, November 2022. Association for Computational Linguistics.  URL https://aclanthology.org/2022.findings-aacl.29.

##  Appendix A Statistical Comparison of Different Memory Sizes

Figure 2: Achieved significances (p-values) of the Friedman test across all
considered memory sizes with the H0 = “expected accuracies are equal”. Color
codes and numbers correspond to the p-values, corrected using the Holm metod
(García & Herrera, 2008). We could not reject the null hypothesis on the 5%
level of significance for any setup.

To find out whether the increasing memory actually provides statistically
significant performance gains, we conduct the Friedman test (Figure 2) over
accuracy score samples for memory sizes {1, 16, 256} for each combination of
the model and the task. As mentioned before, each sample thus contains five
experiments.

##  Appendix B Attention and Luna Definition

The attention (Vaswani et al., 2017) performs the following calculation over
the three matrix inputs $Q,K$ and $V$:

$\displaystyle\text{MultiHeadAttention}(Q,K,V)$
$\displaystyle=[\text{head}_{1},\text{head}_{2},\dots,\text{head}_{h}]W^{O}$
$\displaystyle\text{head}_{h}$
$\displaystyle=\text{Att}(QW^{Q}_{h},KW^{K}_{h},VW^{V}_{h})~{}$ where
$\displaystyle~{}\text{Att}(Q,K,V)$
$\displaystyle=\text{softmax}\left(\frac{QK^{T}}{\sqrt{d_{h}}}\right)V$

and where $W_{h}$ is the corresponding weight matrix vertical slice for a
particular attention head. For simplicity, most of Transformer implementations
keep input sizes $Q\in\mathbf{R}^{L\times d}$, $K,V\in\mathbf{R}^{H\times d}$
and weight matrices
$W^{Q}_{h},W^{K}_{h},W^{V}_{h},W^{O}_{h}\in\mathbf{R}^{d\times d_{h}}$,
$d_{h}=d/h$. The matrix
$\text{softmax}(QK^{T}d_{h}^{-1/2})\in\mathbf{R}^{L\times H}$ is often being
referred to as the attention matrix, and may be interpreted as a matrix of
relevance scores between $Q$ and $K$ vectors. The Transformer encoder
module††To avoid the overloaded term “layer”, by “module” we denote the whole
encoder/decoder block, consisting of attentions, FFNs and skip connections,
see Figure 3. equation is thus (see Figure 3(a)):

$\displaystyle X_{\text{norm}}$ $\displaystyle=\text{LayerNorm}(X)$
$\displaystyle I$
$\displaystyle=X+\text{MultiHeadAttention}(X_{\text{norm}},X_{\text{norm}},X_{\text{norm}})$
$\displaystyle X^{\prime}$ $\displaystyle=I+\text{FFN}(\text{LayerNorm}(I))$

(a) Vanilla Transformer

(b) Luna

(c) ConvLuna

Figure 3: Comparison of the ordinary Transformer, Luna and the proposed
ConvLuna encoder blocks (we refer to them as modules). “Packing” and
“unpacking” attention layers in Luna are analogous to the attentions in the
vanilla Transformer, while the Rescaled Attention additionally multiplies
attention logits with a learnable parameter. The “unpacking” attention of
ConvLuna is also denoted as rescalable; however, in our experiments we keep
the normalization fixed and identical to the vanilla Transformer.

Since the computation of the $L\times H$ attention matrix may be expensive
(e.g. quadratic when $Q=K=V$), Luna (Ma et al., 2021) factorizes the
computation into two attentions (Figure 3(b)): one (“packing”) with $Q$ given
as a memory of a fixed length (we denote it as $P$ in the figure) and $K,V$
being module inputs (we denote them as $X$); and the second one (“unpacking”)
with the $Q$ given as the module input and $K,V$ as packing attention outputs
(Figure 3(b)):

$\displaystyle P_{\text{packed}}$
$\displaystyle=\text{MultiHeadAttention}(P,X,X)$ $\displaystyle
X_{\text{unpacked}}$
$\displaystyle=\text{MultiHeadAttention}(X,P_{\text{packed}},P_{\text{packed}})$
$\displaystyle I$ $\displaystyle=\text{LayerNorm}(X+X_{\text{unpacked}})$
$\displaystyle P^{\prime},X^{\prime}$
$\displaystyle=\text{LayerNorm}(P+P_{\text{packed}}),\text{LayerNorm}(\text{FFN}(I)+I)$

The packing attention output serves as the memory input into the next module
after applying a skip connection, while the unpacking attention output
proceeds to summation with the module input and the residual FFN as in the
original Transformer model. Since the $P$ length is constant and typically
significantly lower than the length of $X$, the computation of both the
packing and unpacking attentions has linear complexity in $H$, which
considerably accelerates the computation for longer inputs compared to vanilla
Transformer.

##  Appendix C ConvLuna Description

The proposed model differs from the Luna in the packing attention
implementation. We change the following:

  * •

Convolution/MaxPooling layers, which we apply on keys and values to filter
input signal.

  * •

Learnable softmax temperature, which we use to rescale attention logits.

The main change we introduce into the model is applying either a convolution
or pooling on the input in the “packing” attention. In particular, we apply it
on the keys and values (which represent an input text), and not on the queries
(which come from the memory); both operations only affect the length
dimension, and there is no depthwise interaction in convolutions. The
computation flow is similar to the Luna; however, we employ a slightly changed
attention module for “packing” attention:

$\displaystyle\text{RescaledAttention}(Q,K,V)$
$\displaystyle=[\text{head}_{1},\text{head}_{2},\dots,\text{head}_{h}]W^{O}$
$\displaystyle\text{head}_{h}$
$\displaystyle=\text{RescaledAtt}(QW^{Q}_{h},KW^{K}_{h},VW^{V}_{h})$
$\displaystyle\text{RescaledAtt}(Q,K,V)$
$\displaystyle=\text{softmax}\left(\frac{Q\tilde{K}^{T}}{\exp(\tau)}\right)\tilde{V}$
$\displaystyle\tilde{K},\tilde{V}$
$\displaystyle=\text{FilterOp}(K),\text{FilterOp}(V)$

where FilterOp is either a convolution or max pooling. The hyperparameters of
the FilterOp are kernel size $K$ and stride $S$; given the input sequence of
size $L\times d$ (where $L$ is input length and $d$ is the hidden dimension),
we apply a kernel of size ($K$, 1) on it with a stride ($S$, 1). We leverage
the computer vision interpretation of the operations as filtering the input
signal, and leaving only a relevant fraction of it.

Another change we made in the model is the learnable softmax temperature. The
original attention formulation (Appendix B) contains the $d^{-\frac{1}{2}}$
multiplier of the query-key product to avoid the softmax saturation; however,
during preliminary experiments we have found memory-input product
demonstrating less variance than input-input product in the vanilla
Transformer. To alleviate this, we have replaced the $d^{-\frac{1}{2}}$
normalizer with $\exp(\tau)$, where $\tau$ is a learnable scalar which we
initialize with zero. This does not increase the model flexibility per se,
since the term may be absorbed either into $W^{Q}$ or $W^{K}$ matrix, but it
allows to accelerate the training by increasing the variance of value vectors
at the beginning, and imposes only a negligible computational overhead.

##  Appendix D Experimental Setup and Hyperparameters

We examine our models on the subset of the Long Range Arena (LRA; Tay et al.,
2020) benchmark, which consists of four classification tasks:

  * •

Byte pair-encoded (BPE) text classification. This task consists in binary
sentiment classification of the IMDB dataset texts encoded as byte pairs. This
creates input sequences up to $4k$ tokens long with relatively short subword
units.

  * •

BPE text matching. The dataset is the ACL Anthology Network (Radev et al.,
2009), encoded in a way similar to the previous task with sequences up to $4k$
tokens long. The model needs to process two inputs and to use the concatenated
hidden representations as an input to the final layer to classify, whether
there is a citation link between the documents.

  * •

ListOps. This task consists in processing nested arrays of digits, coupled
with aggregation operations such as max, min, median and sum modulo, up to
$2k$ tokens long. The model has to predict the correct answer out of ten, and
this task tests the ability of the model to process hierarchical inputs. An
example input looks like:
[MED 9 [MAX 4 [MIN 6 3 7 8 9 X 1 2 …

  * •

CIFAR-10 image classification. This task is an image classification, but the
input is represented as a sequence of pixel values. The data are CIFAR-10
dataset images (Krizhevsky, 2009), converted to 8-bit grayscale and flattened
inputs 1024 tokens long.

The benchmark suggests training from scratch and limiting the additional
parametrization, which allows for a fairer comparison with other models.

Table 2 lists the values of hyperparameters for our experiments. All the
ConvLuna models share projection matrices between packing and unpacking
attention, and share the $W^{K}$ and $W^{V}=\mathbf{I}_{d}$ weights within a
module to increase throughput. We have found the filtering (convolution or
pooling) operations hyperparameters relatively shareable across tasks, with
only ListOps benefiting from another configuration. We apply both operations
length-wise, with the stride being the main hyperparameter to trade the
throughput for performance. To better see how memory is being utilized by the
model, we use averaged memory cells instead of the [CLS] token as an input
embedding before the final layer.

Parameter | Classif. | Matching | ListOps | CIFAR
---|---|---|---|---
Seq. Length | 4000 | 4000 | 2000 | 1024
Batch Size | 32 | 32 | 32 | 64
Training Steps | 25 000 | 30 000 | 50 000 | 30 000
Optimizer | AdamW ($\beta_{1}=0.9$, $\beta_{2}=0.999$)
Base LR | 0.005 | 0.015 | 0.005 | 0.01
Weight Decay | 0.01 | 0.04 | 0.01 | 0.01
Warmup Steps | 8000 | 8000 | 1000 | 700
Schedule | Base LR * Warmup * Sqrt Decay
Warmup Mul. | $min(1,\text{Current Step}/\text{Warmup Steps})$
Sqrt Decay Mul. | $1/\sqrt{max(\text{CurrentStep},\text{WarmupSteps})}$
Loss | CCE
Blocks | 4 | 4 | 6 | 8
Heads | 4
Hidden dim. | 128
QKV dim. | 128
MLP dim. | 512
Filter Op. | MaxPool | MaxPool | Conv | MaxPool
Kernel Size | 4 | 4 | 32 | 4
Stride | 1
Dropout | 0.1 | 0.1 | 0.1 | 0.0
Activation | GELU
Pooling | Memory Cells Average
Pos. encoding | Learnable Absolute

Table 2: Hyperparameters used for the LRA experiments.

##  Appendix E Ablation Study

Model | Classification $\uparrow$ | Matching $\uparrow$ | ListOps $\uparrow$ | CIFAR-10 $\uparrow$ | Average $\uparrow$
---|---|---|---|---|---
OnlyScaling-1 | 65.45 $\pm$ 0.30 | 72.46 $\pm$ 0.68 | 37.12 $\pm$ 0.47 | 49.23 $\pm$ 1.35 | 56.07
OnlyScaling-16 | 66.81 $\pm$ 0.21 | 74.99 $\pm$ 1.67 | 37.08 $\pm$ 0.18 | 48.67 $\pm$ 0.65 | 56.89
OnlyScaling-256 | 66.95 $\pm$ 0.20 | 75.55 $\pm$ 0.61 | 37.52 $\pm$ 0.33 | 48.90 $\pm$ 1.01 | 57.23
OnlyFiltering-1 |  82.39 $\pm$ 0.62 | 82.38 $\pm$ 0.73 | 40.44 $\pm$ 2.31 |  58.69 $\pm$ 1.13 | 65.98
OnlyFiltering-16 | 80.89 $\pm$ 0.44 |  82.66 $\pm$ 1.46 |  41.48 $\pm$ 1.74 | 58.06 $\pm$ 0.59 | 65.77
OnlyFiltering-256 | 80.27 $\pm$ 0.97 | 82.10 $\pm$ 1.68 | 41.24 $\pm$ 1.42 | 58.12 $\pm$ 0.66 | 65.43

Table 3: Results of the ablation experiments. OnlyScaling denotes the setup
where we apply no filtering operations in packing attention, while
OnlyFiltering means that we do not use the learnable softmax temperature
there. Following the Table 1, we report accuracy score mean and standard
deviation across five runs for each setup, and highlight the best result for
each task with bold.

During the ablation experiments, we run the training of our models again, but
now applying only one change at a time. The Table 3 reveals that the applying
convolution or pooling indeed leads to significant performance improvements on
the considered tasks. However, a straighforward improvement is not the case
when we apply the learnable logit scaling; in some setups it can improve the
accuracy on its own or in combination with the convolution/pooling, but in
some setups (CIFAR-10) it degrades the performance.

Although the effect of the learnable logit scaling is not the same for all the
considered tasks, the combination of both methods yields the best average
accuracy across the all setups (Table 1). We also refer to the fact that the
initial value of the scalar is lower than the fixed $d^{-\frac{1}{2}}$ of the
vanilla attention, which in some cases may be the more important factor than
the trainable parameter itself. Dividing the attention logits with a lower
value leads to more saturated and varied attention scores at the training
start compared to the nearly uniform distribution of the vanilla attention,
which results in a better result and a faster convergence in some tasks.

We provide the following interpretation: for the setups such as ListOps, where
the models demonstrate very slow convergence, or Classification, where we
hypothesize that the model operates similarly to the Bag-of-Words and thus
needs to focus more on particular tokens, such behavior that forces more
attention to a smaller subset of tokens may be beneficial. At the same time,
within the CIFAR-10 and Matching tasks the answer is unlikely to be dependent
only on a small subset of input tokens, so a more focused attention at the
beginning stops being a benefit and the additional parameter may contribute to
the overfitting.