# Optimal Codeword Construction for DNA-based Finite Automata

Anupam Chattopadhyay  Arnab Chakrabarti

###### Abstract

Biomolecular computation has emerged as an important area of computer science
research due to its high information density, immense parallelism opportunity
along with potential applications in cryptography, genetic engineering and
bioinformatics. Computational frameworks using DNA molecules have been
proposed in the literature to accomplish varied tasks such as simulating
logical operations, performing matrix multiplication, and encoding instances
of NP-hard problems. In one of the key applications, several studies have
proposed construction of finite automata using DNA hybridisation and ligation
[1][2]. The state and symbol encoding of these finite automata are done
manually. In this manuscript, we study the codeword construction problem for
this approach. We derive exact theoretical bounds on the number of symbols and
states in the finite automata and also obtain the complete set of symbols in a
specific case, thereby solving an open problem posed in [1]. For automatic
encoding, two different solutions, based on a heuristic and on Integer Linear
Programming (ILP), are proposed. Furthermore, we propose an early simulation-
based validation of laboratory experiments. Our proposed flow accepts a finite
automaton, automatically encodes the symbols for the actual experiments and
executes the simulation step-by-step.

##  I Introduction

The field of DNA computing was initiated by the landmark work of Adleman [3]
who showed how to solve small instances of the NP-complete Hamiltonian Path
problem by encoding them on DNA strands. DNA, or Deoxyribonucleic Acid, is a
fundamental unit that encodes the genetic information that makes life
possible. It is a polymer whose monomeric units consist of four nucleotides:
Adenine (A), Cytosine (C), Guanine (G) and Thymine (T). The letters of this
alphabet bind according to the well-known Watson-Crick complement condition:
Adenine binds to Thymine (A $\leftrightarrow$ T) and Cytosine binds to Guanine
(C $\leftrightarrow$ G).

Figure 1: Restriction Enzyme Operation

Typically, to use DNA molecules to perform computations, problem instances
have to be encoded onto a set of DNA molecules. These molecules are then
allowed to react with or without the influence of suitable enzymes to form
potential solutions. Finally one uses protocols such as gel electrophoresis to
obtain solutions in molecular form. Some of these biomolecular reactions
include:

Hybridisation: A double-stranded DNA molecule is formed by creating hydrogen
bonds between the complementary bases of two single-stranded molecules that
have opposite orientations.

Polymerase Enzyme: Polymerase are DNA enzymes which help duplicate a DNA
strand. A Polymerase Chain Reaction (PCR) is an oft-used protocol for
detecting or amplifying a specific molecule within a large mix of molecules.

Ligation: If a double stranded DNA molecule contains a broken bond in one of
the strands then it can be glued by a ligase enzyme such as $T4$. The process
is known as ligation.

Restriction Endonuclease/Enzyme: A restriction enzyme recognizes a particular
sequence of nucleotides in a double stranded DNA and cuts it into two pieces
by destroying the phosphodiester bonds at a specific distance from the
recognition site. This is essentially the inverse operation of ligation. The
single strands hanging out of each piece are known as _sticky ends_. The
recognition site as well as the distance from it to the cutting point are
inherent properties of a restriction enzyme [4, 5]. An example of such as a
reaction via the restriction enzyme $FokI$ is shown in Figure 1. $FokI$ cuts
the base strand from its recognition site at a distance of nine nucleotides
and the complementary strand at a distance of thirteen nucleotides producing a
sticky end consisting of four nucleotides. Several restriction enzymes can
also perform blunt cuts which do not produce any sticky end.

Gel Electrophoresis: This technique allows separating the DNA molecules
according to their weight (or length). This is used for controlling the
intermediate steps of a reaction or for reading the final output.

In the original paper by Adleman [3], a number of the aforementioned steps
were employed. The high information density and massive parallelism of DNA
computing sparked major research interest in this field, though it was shown
that DNA computing does not offer any additional power from the perspective of
computability theory. Several NP-hard problems were subsequently encoded into
DNA molecules [6] including the well-known Circuit Satisfiability problem [7,
8]. Several important practical applications followed including the breaking
of the Data Encryption Standard (DES) [9] and the possibility of parallel
algorithms for integer factorization [10], a key step in several public key
cryptography protocols. This initiated the field of DNA-based cryptography
[11]. A detailed survey of DNA computing is presented in [12]. A serious
disadvantage of the encoding approaches proposed in [3, 7] is that the number
of DNA strands required to encode instances grows exponentially with their
size (see Table 1 in [7]). There have been some advances in encoding problem
instances of modest sizes. For instance, Braich et al. [13] show how to solve
a twenty-variable $3$-SAT instance. However encoding large problem instances
so that all potential solutions are simultaneously constructed, as is the
approach in [13], is difficult since, molecular computations are inherently
error-prone and this affects the reliability of the final result [14]. Recent
research in DNA computing has, therefore, focused on the construction of small
nanodevices that can be scaled up for solving practical problems [15, 16].

###  I-A Finite Automata using DNA Computing

The computing power of biomolecular nanodevices that are capable of self-
assembly was studied by Winfree et al. [17]. They showed that there can be
different self-assembly primitives for DNA molecules that can express regular
grammars (finite automata), context-free grammars and unrestricted grammars.
In particular, it was shown that a $2$-dimensional self-assembly of DNA
molecules can simulate a Universal Turing Machine. This study spear-headed
experimental work to validate these models.

Benenson et al. [2] were the first to propose constructing a finite state
automaton with DNA molecules by using restriction enzymes. Their model was
simple enough to be used in a genetic control study [18] with far-reaching
implications in genetic engineering, pharmaceutical experiments and medical
diagnosis. Subsequently, experiments with transducers i.e. finite automata
with outputs, have been reported in [19] and there has been some success in
$2$-dimensional self-assembly of DNA tiles [20]. Based on experimentally
validated finite automata constructions, novel theoretical models for push-
down automata have also been proposed [21, 22, 23].

The simplicity of the finite automata construction using restriction enzymes
motivated researchers to scale up the problem size. Experimental studies with
an autonomous, programmable $3$-symbol, $3$-state finite automata was reported
in [1]. The authors of this paper claimed that their approach can be used to
construct a $37$-symbol, $3$-state finite automata (a bound that we improve in
this paper). This design approach led to interesting applications in molecular
image encryption by using a $2$-state, $2$-symbol state machine [24].

###  I-B Codeword Design for DNA Computing

Codeword construction for DNA is an well-studied topic due to its importance
in tasks like DNA-based information storage, DNA computing or molecular bar
code reading for chemical libraries. A good codeword construction aim towards
increasing information density and/or parallelism in computing without
creating cross-hybridisation between distinct codewords. The goal of
maximizing the information density can be reduced to the problem of finding
large sets of DNA strands maximally separated in a metric space, where strands
with high hybridization affinity are mapped to neighboring points. In this
setting, it is proved that codeword design is an NP-complete problem [25].
Consequently, various heuristics have been proposed for DNA codeword design,
including generic algorithm [26], taboo search [27], stochastic search [28],
and also drew inspiration from the traditional problem of binary codeword
construction [29]. A survey of DNA codeword construction challenges and
approaches is presented in [30].

Often DNA codeword design entails satisfying much stronger constraints than
enforced by pure non-hybridization [31][32]. Such combinatorial constraints
often originate from the use case, e.g., DNA-based self-assembly or finite
automata construction, as we focus in this manuscript. Depending on the
experimental approach, different combinatorial constraints and different
codeword design strategy are needed, as described in, e.g., [33][34].

In this work, we focus on the codeword construction for finite automata using
a single restriction enzyme, as proposed in [1]. To the best of our knowledge,
this has not been attempted before, thus leaving several interesting research
problems unresolved. The problem of codeword construction for a similar
setting, with multiple restriction enzymes, is discussed in [33]. For
recombinase-based state machines (RSMs), the codeword construction problem is
recently proposed in [35].

It is also imperative to prepare a simulation environment before undertaking
the actual experiment. A generic simulation flow for DNA computing was
developed in [36] where one can model and simulate various bio-molecular
reactions. However, the problem of constructing distinguished languages (the
encoding problem) was not addressed there. A design automation environment for
Boolean circuit construction via DNA computing was developed in [37].

In this perspective, our main contributions in this paper are outlined below.

  * •

For arbitrary $p$ and $l$, we identify theoretical bounds on the number of
valid words and the size of a $(p,l)$-distinguished language. This allows us
to determine the maximum number of symbols and $(\text{state},\text{symbol})$
pairs possible for restriction enzymes-based constructions of finite automata.

  * •

We design efficient algorithms that enumerate an optimal or a near-optimal
sized $(p,l)$-distinguished language.

  * •

We also develop a simulation flow to allow _dry_ experiments and validation.

The rest of the paper is organized as follows. Section II introduces the
formal structure of the problem. Section III contains a detailed example of a
finite automaton construction using DNA molecules. The encoding problem is
dealt with in Section IV and we report experimental results about the
efficiency of our automation and the construction of finite automata with a
larger state count than reported in [1] in Section V. Section VI contains some
concluding remarks. Supplementary material with the actual symbol enumeration
is presented in Appendix.

##  II Preliminaries and Motivation

In this section, we briefly state some of the basic definitions and
terminology that are used in this paper.

A _finite state machine (FSM)_ is a quintuple $(\Sigma,S,s_{0},\delta,F)$,
where

  * •

$\Sigma$ is the input alphabet (a finite, non-empty set of symbols);

  * •

$S$ is a finite, non-empty set of states;

  * •

$s_{0}\in S$ is the initial state;

  * •

$\delta\colon S\times\Sigma\rightarrow S$ is the state-transition function;

  * •

$F\subseteq S$ is the set of final states (possibly empty).

To simulate an FSM using DNA molecules, we encode its symbols using the
alphabet $\Sigma=\\{A,C,G,T\\}$ which comprises of the letters representing
the nucleotides that constitute DNA. Note that there are _two_ alphabets under
consideration here: the alphabet of the FSM and the alphabet that we use to
encode the states and symbols of the FSM. To avoid confusion, we use the term
_symbol_ to denote an element of the input alphabet of an FSM and _letter_ to
denote an element of $\Sigma$, the encoding alphabet.

In what follows, fix $\Sigma=\\{A,C,G,T\\}$. Given a positive integer $p$, we
denote by $\Sigma^{p}$ the set of all words of length $p$ from the alphabet
$\Sigma$. The set of all words from $\Sigma$ is denoted by $\Sigma^{*}$. For
$w=a_{1}a_{2}\cdots a_{p}\in\Sigma^{p}$ and $i\leq j$, define $w[i,j]$ to be
the subword of $w$ that starts at index $i$ and ends at index $j$, that is,
$w[i,j]=a_{i}a_{i+1}\ldots a_{j}$. Given an integer $1\leq l\leq p$, we let
$\text{sub}_{l}(w)$ denote the set of $p-l+1$ subwords
$w[1,l],w[2,l+1],\ldots,w[p-l+1,p]$ of length $l$. Given a word $w=a_{1}\cdots
a_{r}\in\Sigma^{*}$, we define its _complement_ to be the word
$\bar{w}=\bar{a}_{1}\cdots\bar{a}_{r}$, where $\bar{a}_{i}$ is the Watson-
Crick complement of the letter $a_{i}$, that is, A and T are complements and
so are C and G. To capture this notion in general, we introduce the notion of
a _paired alphabet_. A _pairing_ $P\subseteq\Sigma\times\Sigma$ of an alphabet
$\Sigma$ is defined as a set of tuples such that every $a\in\Sigma$ appears in
exactly one tuple once. We then call $(\Sigma,P)$ a _paired_ alphabet—in our
settings this will be given by
$(\\{A,C,T,G\\},\\{(A,T),(C,G),(T,A),(G,C)\\})$. For sake of readability and a
slight abuse of notation, we will use $\Sigma$ to denote a paired alphabet in
the following. Under this definition, the notion of complements is easily
extensible by choosing the letter-wise complement as the pairs appearing in
the pairing and using the above extension to words. We then denote by
$\text{comp}_{l}(w)$ the set of complements of the words in the set
$\text{sub}_{l}(w)$. A word $w=a_{1},\ldots,a_{p}\in\Sigma^{p}$ is a
_palindrome_ if for all $1\leq i\leq\lfloor p/2\rfloor$, $a_{i}$ is the
Watson-Crick complement of $a_{p-i+1}$.

Note that this definition of a palindrome is different from the usual
definition for words where the letters $a_{i}$ and $a_{p-i+1}$ are required to
be identical. In DNA computing, one is interested in preventing nucleotide
strands to fold and form hairpin loop (alternatively known as stem-loop)
structures [38]. In the domain of microbiology research such palindromic
sequences are also referred to as Inverted Repeat (IR) [39].

Let us fix integers $p$ and $l$ with $1\leq l\leq p$. A word $w\in\Sigma^{p}$
is _$(p,l)$ -valid_ if it satisfies the following conditions:

  1. 1.

$\left|\text{sub}_{l}(w)\cup\text{comp}_{l}(w)\right|=2\cdot(p-l+1)$;

  2. 2.

no word in $\text{sub}_{l}(w)$ is a palindrome.

The first condition says that the length-$l$ subwords of $w$ are distinct and
no two of them are complements of one another. Thus a word is valid if its
subwords are distinct, are not palindromes and no two of them are complements
of one another. Formally, this can be captured with the notion of _$(p,l)$
-distinguished_ language. We call a language $L\subseteq\Sigma^{p}$, _$(p,l)$
-distinguished_ if

  1. 1.

every word of $L$ is $(p,l)$-valid, and,

  2. 2.

for all $w,w^{\prime}\in L$ with $w\neq w^{\prime}$ we have that

$(\text{sub}_{l}(w)\cup\text{comp}_{l}(w))\cap(\text{sub}_{l}(w^{\prime})\cup\text{comp}_{l}(w^{\prime}))=\emptyset.$

In this definition, the second condition states that distinct words in a
distinguished language neither have the same subwords nor their complements.
Intuitively speaking, a _valid word_ in our setting is used to encode a
_single_ input symbol of the finite automaton under construction. Subwords are
used to encode the $(\emph{state},\emph{symbol})$ pairs of the automaton. As
will be clear later on, the restrictions on words and languages that were
described above allow us to encode inputs to the automaton in such a way that
one can use restriction enzymes to simulate its computation on the given
input. While this approach was outlined by Soreni et al. [1], they manually
determined words that encode input symbols.111Further, the symbol table
reported in [1], Table 1 contains overlapping 4-bp sequences between No. 11
and No. 18. Thus all codewords are not valid. This leads to the open problem
that, what is the maximum achievable number of valid words for a _$(p,l)$
-distinguished_ language and how to determine those words. For a better
understanding of the problem scope, we now look closely into an exemplary FSM.

Figure 2: FSM via DNA Operations

##  III An Example FSM

Consider the finite automaton shown in Figure 2 which accepts binary strings
ending with $0$. In this section we revisit the simulation such an automaton
using DNA molecules [2]. As was explained in Section II, we use the alphabet
$\Sigma=\\{A,C,G,T\\}$ to encode input symbols of an automaton.

In this example we set $p=5$ and $l=4$ and encode the input symbols $0,1$ by
valid $(5,4)$-words $w_{0}=\text{ATTGC}$ and $w_{1}=\text{AGTCA}$,
respectively. We also encode a terminating symbol $t$ by the valid
$(5,4)$-word TCGTG making sure that $\\{w_{0},w_{1},t\\}$ is a
$(5,4)$-distinguished language. For $i\in\\{0,1\\}$, the subword $w_{i}[1,4]$
represents the fact that the automaton is in state $S_{0}$ and reading symbol
$i$; and, the subword $w_{i}[2,5]$ denotes that the automaton is in state
$S_{1}$ and reading symbol $i$. In this way, all possible
$(\text{state},\text{symbol})$ pairs are encoded. Since $\\{w_{0},w_{1},t\\}$
is $(5,4)$-distinguished, the subwords
$w_{0}[1,4],w_{0}[2,5],w_{1}[1,4],w_{1}[2,5],t[1,4],t[2,5]$ are all distinct,
are not palindromes and no two of these are complements of one another.

The input to the automaton is encoded on the _base strand_ of a double-
stranded DNA molecule (shown on top in Figure 2). In this instance, the string
$110t$ is encoded in the base strand along with additional information to
guide the action of the restriction enzyme which in this case is $BbvI$. The
second strand, called the _complementary strand_ , consists of complementary
nucleotides that align with their partners in the base strand. Together these
two strands constitute our input tape. The restriction enzyme $BbvI$ has the
property that it recognizes a sequence of nucleotides (the recognition site)
which in this case is the sequence GCAGC. It cuts the base strand eight
nucleotides after the recognition site and the complementary strand twelve
nucleotides after the recognition site. When this happens for the first time,
it exposes the sequence AGTC on the base strand which as discussed above means
that the automaton is in state $S_{0}$ reading the symbol $1$. This exposed
sequence is called the _sticky end_ because it is in the nature of nucleotides
to form bonds with their complementary partners. At this point, the T4 ligase
attaches itself to this exposed end via the complementary sticky end TCAG as
shown in the figure. This operation, in effect, deletes the first input symbol
from the input tape because when the restriction enzyme works on it again, it
cuts the base strand beyond the first input symbol ignoring it in the process.
This sequence of cutting the strands by the restriction enzyme followed by
ligation continues until the whole of the input is “consumed.” When the
terminal symbols are exposed, special nucleotide sequences called _detection
symbols_ attach themselves to them. Depending on which sequence of terminal
symbols were exposed by the restriction enzyme, one can detect whether the
automaton terminated in state $S_{0}$ or $S_{1}$. In an actual experiment, one
determines the termination state by additional biochemical reactions such as
polymerase chain reactions and gel electrophoresis. In the example shown, the
automaton terminates in state $S_{1}$ as it should.

##  IV Automated State Encoding

Having explained how one might construct an FSM using DNA strands and
restriction enzymes, we find it convenient to explain some the requirement on
the words and languages from $\Sigma^{*}$ that we imposed in Section II in
order to be able to encode inputs to the FSM. In the context of
$(p,l)$-distinguished languages, the subwords $\text{sub}_{l}(w)$ are the
sticky ends produced by the restriction enzymes and these represent the
$(\text{state},\text{symbol})$ pairs of the automaton.

_rule 1:_

The sticky ends, produced by the restriction enzymes, cannot be palindromes as
they would stick to one another to form _hairpin loop_ [38, 40].

_rule 2:_

Each sticky end represents a particular $(\text{symbol},\text{state})$ pair.
To uniquely identify a symbol, a sticky end cannot occur more than once within
the symbol itself or within any other symbols.

_rule 3:_

The complement of the sticky end, selected for a state of a symbol, cannot
occur in the same or any other symbol.

_rule 4:_

All the DNA symbols should have a sequence which is unique. So there cannot be
a repetition of similar DNA symbols in the library of valid symbols.

Note that rule 4 is encompassing rule 2. The mapping of valid symbols to the
states are followed by fixed choices for the symbols of state transitions. On
the basis of these constraints, it is possible to identify the theoretical
bounds on the symbol and state count, which is done in the following sub-
section. A specific case of this bound calculation is presented in [1].

###  IV-A An Upper bound for FSM encoding

Assume that $L_{p,l}$ is a $(p,l)$-distinguished language of maximal
cardinality. A simple upper bound for $|L_{p,l}|$ can be obtained as follows:
the total number of non-palindrome $l$-letter subwords is given by
$|\Sigma|^{l}-|\Sigma|^{\lfloor l/2\rfloor}$. Excluding complement subwords,
at most $\frac{1}{2}(|\Sigma|^{l}-|\Sigma|^{\lfloor l/2\rfloor})$ such
$l$-letter words can appear as subwords in $L_{p,l}$.

As every $p$-letter word in a $(p,l)$-distinguished language contains exactly
$p-l+1$ distinct subwords of length $l$, we obtain the bound

$|L_{p,l}|\leq\frac{|\Sigma|^{l}-|\Sigma|^{\lfloor l/2\rfloor}}{2(p-l+1)}.$

Surprisingly, this very simple limit is tight for the range of parameters that
we explored so far (cf. Table LABEL:table:ilp_heu) and we suspect that it is
tight for all $p,l$, except for the case of $l$ being $1$.

For a given FSM $(\Gamma,S,s_{0},\delta,F)$ and parameter $p,l$ we then obtain
the following bounds:

$\displaystyle|\Gamma|$ $\displaystyle\leq|L_{p,l}|-1$ (1) $\displaystyle|S|$
$\displaystyle\leq p-l+1$ (2)

which in turn bounds the number of transitions from above by
$(|L_{p,l}|-1)(l-p+1)$. Note that we cannot use every word of $L_{p,l}$ to
encode symbol-state pairs, as the construction reserves one terminal-symbol to
read out the result of the computation.

###  IV-B Problem Formulation

Let us first formalize the optimization problem of finding a maximal
$(p,l)$-distinguished language over a paired alphabet $\Sigma$.

Max $\Sigma$-Distinguished Language
---
Input: |  Integers $p,l$
Problem: |  Compute a $(p,l)$-distinguished language of maximal cardinality

We suspect that this problem can be solved in time polynomial in
$|\Sigma|^{p}$, but this remains an interesting open question. For the scope
of this application we provide a heuristic that solves this problem with
reasonable solution quality.

The aforementioned constraints for valid symbols can be conveniently
represented in a graphical view, as shown in the Figure 3. In the graph, the
$4$-letter symbols made out of the alphabets $\\{A,T,G,C\\}$ are nodes ($V$).
A node, $V_{1}$ is connected via a directed edge ($E$) with $V_{2}$ only if
the last $3$ letters of $V_{1}$ are exactly same as the first $3$ letters of
$V_{2}$. The graph constructed satisfies following properties.

  * •

The graph contains several cycles. Exact enumeration of cycle count is also
possible but, not required for this work.

  * •

The maximum indegree of any vertex ($V_{i}$) is $\leq$ $4$.

  * •

The maximum outdegree of any vertex ($V_{i}$) is $\leq$ $4$.

Figure 3: FSM Encoding Problem

From Figure 3, the enumeration of all valid symbols can be alternatively
viewed as enumeration of all directed, vertex-disjoint node covers of length
$3$, also known as $P3$-cover. In the general case, the number of nodes to be
covered is dependent on the value of $S_{max}$ identified in subsection IV-A.
For the number of states $S_{max}$ being equal to n, the problem is to
determine maximum, vertex-disjoint $P\textit{n}$-covers.

###  IV-C Heuristic Approach

For the heuristic computation, we transform an instance $(\Sigma,p,l)$ into a
directed auxiliary graph $G_{A}$ as follows: the vertices of $G_{A}$ are
exactly the non-palindrome $l$-letter words of $\Sigma^{l}$ and two words
$w,w^{\prime}\in V(G_{A})$ are connected by an arc $(w,w^{\prime})$ if
$w[2,l]=w^{\prime}[1,l-1]$. Thus, a directed path in $G$ of length $p-l+1$
corresponds to a word in $\Sigma^{p}$ without repeated or palindrome
subwords—note that such a word might be invalid, as it could contain both a
subword and its complement.

The heuristic now greedily chooses directed $(p-l+1)$-paths such that all
vertices on that path have a low out-degree. Every vertex can be used at most
once in this process, thus no $p$-letter subword will appear twice. However,
as a word and its complement could be chosen, we need a post-processing step
to create a valid $(p,l)$-distinguished language.

Input: $p$, $l$

Output: $L$

$L=\emptyset$;

$G_{A}=createGraph(p,l)$;

$degree=0$;

while _$G_{A}$ contains vertices with outdegree $\geq degree$_ do

$v=$ Vertex of minimal outdegree $\geq$ degree;

$P=(v)$;

for _$i=1\to(p-l)$_ do

$w=$ Out-neighbour of $v$ with minimal outdegree;

$P=P+w$;

$v=w$;

end if _$length(P)=p$_ then

$L=L\cup word(G_{A},P)$;

$G_{A}=G_{A}\setminus P$;

else

$degree=degree+1$;

end

end $G_{c}=createConflictGraph(L)$;

while _$G_{c}$ contains node with degree $\geq 1$_ do

$w=$ Vertex of maximum degree in $G_{c}$;

$G_{c}=G_{c}-w$;

$L=L\setminus\\{w\\}$;

end

ALGORITHM 1 Heuristic via Directed Path-cover

At first, the algorithm proceeds by creating an exhaustive non-palindromic
list of symbols with length $l$. The graph is then constructed by creating
directed edges when there is an overlap of literals between $2$ nodes. The
first while-loop combines neighbouring symbols as long as possible. This is
controlled by an increasing outdegree. At the beginning, all nodes are checked
and a symbol is formed by connecting a node with minimal outdegree to its
neighbouring node, which also has minimal outdegree and so on. The nodes are
connected till the valid symbol size ($p$) is reached, which is alternatively
indicated by the maximum state count ($S_{max}$ = $p$ \- $l$ \+ $1$). In case,
the formation of a valid symbol is not possible starting from the indicated
node, the outdegree is increased by one and the iterative search for a valid
symbol begins again. If no such node is found, the outdegree requirement is
increased by $1$ and the While-loop is iterated. This guarantees that the
algorithm is terminated when no more symbol construction is possible. After
every valid symbol generation, the corresponding nodes are removed from the
graph.

The last part of the algorithm enforces the rule 3 mentioned in the section
IV. During symbol construction, complementary sticky ends may become part of
the same or different symbols. This is identified by an exhaustive pairwise
check of all the symbols and then a conflict graph is constructed. In the
conflict graph, a conflict edge denotes that either of the connected nodes
(i.e. symbols) can exist in the valid symbol library. To obtain maximum number
of symbols, repeatedly nodes with maximum degree are removed till no conflict
edge remains.

###  IV-D Algorithmic Complexity

The worst-case execution time for the above heuristic is based on the
assumption that all combinations of $S_{max}$ nodes are tried for constructing
a valid symbol. In practice, this is less since, the choice of the first node
bounds the algorithm to search for a following node within at most $4$
options. This makes the total number of possible combinations as $n\cdot
4^{S_{max}-1}$, where $n$ is the number of nodes in the graph $G_{A}$. For $n$
being $(4^{l}-4^{\lceil l/2\rceil})$, the complexity is
$\mathcal{O}(4^{l}\cdot 4^{S_{max}-1})$. A similar complexity figure of
$\mathcal{O}(4^{l}\cdot 4^{l})$ is obtained for the second part of the
algorithm, where conflict edges are removed. Despite the exponential
complexity, the heuristic turned out to be highly efficient for the currently
used restriction enzymes where, $l$ $\leq$ $4$ as well as several other
scenarios presented in the section V.

###  IV-E ILP Based Approach

Whereas the above heuristic yields a large set of codewords in a reasonable
amount of time, a provable _maximal_ set of codewords could be desirable. To
this end we reduce the problem of finding a maximal set of codewords with word
length $p$ and subword-length $l$ to finding a independent set in a suitable
_conflict graph_. As this problem is NP-hard in general, this approach can
only work for a limited range of parameters. However, using this formulation
we were able to calculate— among other parameters—an optimal number of
codewords for $p=6$ and $l=4$.

Let us describe the construction of the _conflict graph_ $G_{p,l}$ in detail:
the vertices of $G_{p,l}$ are exactly the $(p,l)$-valid words of $\Sigma^{p}$
and we add an edge between $w,w^{\prime}\in V(G_{p,l})$ if

$(\text{sub}_{l}(w)\cup\text{comp}_{l}(w))\cap(\text{sub}_{l}(w^{\prime})\cup\text{comp}_{l}(w^{\prime}))\neq\emptyset$

holds. That is: two words $w,w^{\prime}$ are connected by an edge in the
conflict graph if not both can be in a $(p,l)$-distinguished language
$L\subseteq\Sigma^{p}$ at the same time. Conversely, any set $X\subseteq
V(G_{p,l})$ that is independent, i.e. $G_{p,l}[X]$ contains no edges, is by
definition $(p,l)$-distinguished. Thus a maximal $(p,l)$-distinguished
language can be found by finding a maximum independent set in $G_{p,l}$.

As Maximum Independent Set is a well-established problem, we leave away the
ILP-formulation that can easily be derived from a given conflict graph
$G_{p,l}$. A maximum set of $(6,4)$-distinguished words of cardinality $40$
that was obtained solving Maximum Independent Set on the conflict graph
$G_{6,4}$ can be found in the Appendix.

###  IV-F Transition Encoding

We explain the transition encoding by taking an exemplary transition from
$state_{m}$ to $state_{n}$ with the input symbol being $sym$. The double-
stranded transition molecule has the format of $\\{$recognition$\\_$site $\|$
buffer$\\_$strand $\|$ complementary$\\_$single$\\_$strand$\\}$. The
complementary$\\_$single$\\_$strand is determined from the encoding of the
$state_{m}$, which remains in the sticky end after every cut by restriction
enzyme. The length of the buffer$\\_$strand is allocated in such a way that
the next cut by restriction enzyme consumes the current symbol $sym$ and
reaches the corresponding $state_{n}$ of the next symbol. For every symbol,
the state encodings are done in a regular fashion. Therefore, the $state_{n}$
of next symbol always requires consumption of a fixed amount of literals.
Note, that the encoding for recognition$\\_$site and the buffer$\\_$strand
must be different from the encoding of the symbols.

Figure 4: Tool Flow for FSM Encoding and Simulation

###  IV-G Software Work flow

The algorithms presented in the previous section is packaged in a software
tool flow. The software follows the steps outlined in Figure 4. It accepts as
input a set of restriction enzymes [4] and an FSM. First, it checks if it is
feasible to construct the DNA-automaton. If so, an appropriate encoding of the
FSM is automatically generated using the symbols taken from the restriction
enzymes provided. Finally, the finite automaton is simulated step by step for
a given input tape.

##  V Experimental Evaluation

The complete tool flow reported in this paper is developed using C++,
consisting of about 2600 lines of code. To solve the ILPs the CPLEX solver was
used [41]. The code was tested on a AMD Phenom II X6 1100T 3.3 GHz 6-core
processor with 8GB RAM running 64-bit scientific Linux OS. We will present two
sets of experiments: In the first one, a simulation of a 5-state FSM using our
tool is shown as an example and the second is a benchmark measuring the
efficiency of generating optimal or near-optimal symbols for state encoding.

###  V-A Finite Automata for Checking Divisibility by 5

With the capabilities provided by our tool, that allows efficiently, automated
encoding, it becomes possible to execute FSMs with a higher number of states
and symbols than reported earlier. For example, one can construct a $3$-state,
$39$-symbol FSM using the restriction enzyme $BbvI$ (we actually have $40$
symbols available, but we need to use one to signalize termination). For a
realistic non-trivial example an FSM construction for divisibility check is
chosen. The automata accepts binary strings of $0$ and $1$ that represent
numbers that are multiples of five. The automata, that can be seen in Figure
5, has a total of $5$ states and $2$ symbols. This means we have to use a
symbol length of $8$ for the restriction enzymes with a sticky end of length
$4$. For creating the transition encoding, which can consume the complete
symbol, one needs a restriction enzyme having a distance from recognition site
to the cutting point to be $\geq$ $9$. If this is not the case, then we might
not be able to cut enough to transition between different states. This is
automatically determined by the tool and a matching restriction enzyme $FokI$
is selected. The state encoding and the transition encoding are automatically
determined within $1$ second. The detailed simulation steps for different
binary strings can be found in Appendix. It should also be noted that FSM is a
powerful construction that can be applied to many different problems, two more
cases of which are also presented in the Appendix.

Figure 5: FSM for Divisibility by 5

###  V-B Benchmarking Symbol Generation Efficiency

To determine the efficiency of our proposed algorithms for generating the
state symbols, different values of $p$ and $l$ are fed to the algorithm. The
corresponding theoretical maximum are computed. The generated ILP and
heuristic based symbol counts for different $p$ and $l$ values are presented
in Table LABEL:table:ilp_heu. The ILP-based method could not scale for certain
values due to the increasing number of ILP constraints. But as can be seen
from the theoretical upper bound this is not important, since the number of
possible symbols decreases with growing $p$ for a fixed $l$. This may seem
counter-intuitive at first. The reason is that, with such a small alphabet, it
becomes increasingly difficult to not repeat a subword with increasing word
length. Furthermore, the right enzymes must exist to be able to use certain
$(p,l)$ pairs. To the best of our knowledge, none that would work with larger
DNA strings than the ones for which we present results are known. For the
parameter values with acceptable ILP constraints, the pre-computed maximum
number of symbols is always returned. In contrast, the heuristic approach
scales well and returns symbols, which are quite close to the optimal. The
heuristic approach took less than $1$ second to generate the symbols in all
the presented cases. For ILP, the timeout was set to $1$ hour, within which
several scenarios failed to return the symbols.

TABLE I: Enumeration of State and Symbol Counts $p$ | $l$ | State Count | Symbol Count
---|---|---|---
Upper bound | ILP | Heuristic
6 | 4 | 3 | 40 | 40 | 38
7 | 4 | 4 | 30 | 30 | 26
7 | 5 | 3 | 160 | 160 | 142
8 | 4 | 3 | 24 | — | 20
8 | 6 | 5 | 672 | 672 | 558
9 | 4 | 6 | 20 | — | 18
10 | 4 | 7 | 17 | — | 12

##  VI Conclusion and Future Work

In this paper, an automated and efficient finite state machine encoding
approach is presented. The optimal solutions for the number of achievable
symbol and state were generated to be used in the our tool. To find such
solutions, an efficient heuristic and an ILP-based approach are proposed,
which are verified through simulation.

## Acknowledgement

Authors will like to gratefully acknowledge the help of Felix Reidl, Fernando
Sánchez Villaamil and Somnath Sikdar, who were affiliated with Theoretical
Computer Science, RWTH Aachen University at the time, and helped with the ILP
formulation.

## References

  * [1] M. Soreni, S. Yogev, E. Kossoy, Y. Shoham and E. Keinan, “Parallel Biomolecular Computation on Surfaces with Advanced Finite Automata,” _Journal of the American Chemical Society_ , vol. 127, pp. 3935–3943.
  * [2] Y. Benenson, T. Paz-elizur, R. Adar, E. Keinan, Z. Livneh and E. Shapiro, “Programmable and Autonomous Machine made of Biomolecules,” _Nature_ , vol. 414, pp. 430–434.
  * [3] L. M. Adleman, “Molecular Computation of Solutions to Combinatorial Problems,” _Science_ , vol. 266, no. 11, pp. 1021–1024, Nov. 1994. [Online]. Available: http://dl.acm.org/citation.cfm?id=189441.189442
  * [4] “Restriction enzymes.” [Online]. Available: http://www.neb.com/nebecomm/products/category1.asp
  * [5] W. Szybalski, “Universal Restriction Endonucleases: Designing Novel Cleavage Specificities by Combining Adapter Oligodeoxynucleotide and Enzyme Moieties,” _Gene_ , vol. 40, pp. 169–173.
  * [6] R. Lipton, “Using DNA to Solve NP-Complete Problems,” _Science_ , vol. 268, pp. 542–545.
  * [7] D. Boneh, C. Dunworth, R. J. Lipton and J. Sgall, “On The Computational Power of DNA,” _Discrete Applied Mathematics_ , vol. 71, pp. 79–94.
  * [8] Q. Liu, L. Wang, A. G. Frutos, A. E. Condon, R. M. Corn and L. M. Smith, “DNA Computing on Surfaces,” _Nature_ , vol. 403, pp. 175–179.
  * [9] D. Boneh, C. Dunworth and R. J. Lipton, “Breaking DES Using a Molecular Computer,” _Princeton University Press_ , vol. Tech. Rep. CS-TR-489-95.
  * [10] W.-L. Chang, M. Guo, and M. Ho, “Fast Parallel Molecular Algorithms for DNA-Based Computation: Factoring Integers,” _NanoBioscience, IEEE Transactions on_ , vol. 4, no. 2, pp. 149–163, 2005.
  * [11] A. Gehani, T. Labean and J. Reif, “DNA-Based Cryptography,” _5th DIMACS Workshop on DNA Based Computers, MIT_.
  * [12] M. Amos, _Theoretical and Experimental DNA Computation_. Springer, 2005.
  * [13] R. S. Braich, N. Chelyapov, C. Johnson, P. W. K. Rothemund and L. Adleman, “Solution of a 20-variable 3-SAT problem on a DNA computer,” _Science_ , vol. 296, pp. 499–502.
  * [14] D. Boneh, C. Dunworth, R. J. Lipton and J. Sgall, “Making DNA Computers Error Resistant,” _DIMACS Series in Discrete Mathematics and Theoretical Computer Science_.
  * [15] L. Qian and E. Winfree, _Parallel and Scalable Computation and Spatial Dynamics with DNA-Based Chemical Reaction Networks on a Surface_. Cham: Springer International Publishing, 2014, pp. 114–131. [Online]. Available: http://dx.doi.org/10.1007/978-3-319-11295-4_8
  * [16] N. Roquet, A. P. Soleimany, A. C. Ferris, S. Aaronson, and T. K. Lu, “Synthetic recombinase-based state machines in living cells,” _Science_ , vol. 353, no. 6297, 2016. [Online]. Available: http://science.sciencemag.org/content/353/6297/aad8559
  * [17] E. Winfree, X. Yang and N. C. Seeman, “Universal Computation via Self-assembly of DNA: Some Theory and Experiments,” _DIMACS DNA Based Computers II_ , vol. 44, pp. 191–213.
  * [18] Y. Benenson, R. Adar, E. Shapiro, “An Autonomous Molecular Computer for Logical Control of Gene Expression,” _Nature_ , vol. 429, pp. 423–429.
  * [19] B. Chakraborty, N. Jonoska and N. C. Seeman, “A Programmable Transducer Self-assembled from DNA,” _Chemical Science_ , vol. 3, no. 1, pp. 168–176.
  * [20] P. W. K. Rothemund, N. Papadakis and E. Winfree, “Algorithmic Self-assembly of DNA Sierpinsky Triangles,” _PLoS Biology_ , vol. 2.
  * [21] N. Jonoska, “Biomolecular Automata,” _Springer NanoBioTechnology_ , pp. 267–299.
  * [22] T. Krasinski, S. Sakowski and T. Poplawski, “Autonomous Push-Down Automaton built on DNA,” _arXiv_ , vol. abs/1111.5807, pp. 267–299.
  * [23] M. Cavaliere, N. Jonoska, S. Yogev, R. Piran, E. Keinan, and N. C. Seeman, “Biomolecular Implementation of Computing Devices with Unbounded Memory,” in _Proceedings of the 10th International Conference on DNA Computing_ , ser. DNA. Berlin, Heidelberg: Springer-Verlag, 2005, pp. 35–49. [Online]. Available: http://dx.doi.org/10.1007/11493785_4
  * [24] S. Shoshani, R. Piran, Y. Arava and E. Keinan, “A Molecular Cryptosystem for Images by DNA Computing,” _Angewandte Chemie International Edition_ , vol. 51.
  * [25] V. T. Phan and M. H. Garzon, “On codeword design in metric DNA spaces,” _Natural Computing_ , vol. 8, no. 3, pp. 571–588, 2009. [Online]. Available: http://dx.doi.org/10.1007/s11047-008-9088-6
  * [26] Deaton R., Garzon M., Murphy R. C., Franceschetti D. R. and Stevens S. E., “Genetic search of reliable encodings for DNA-based computation,” _1st Genetic Programming Conference_ , pp. 9–15.
  * [27] K. Zhang, J. Xu, X. Geng, J. Xiao, and L. Pan, “Improved taboo search algorithm for designing {DNA} sequences,” _Progress in Natural Science_ , vol. 18, no. 5, pp. 623 – 627, 2008. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S1002007108000725
  * [28] D. C. Tulpan, H. H. Hoos, and A. E. Condon, _Stochastic Local Search Algorithms for DNA Word Design_. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003, pp. 229–241. [Online]. Available: http://dx.doi.org/10.1007/3-540-36440-4_20
  * [29] A. E. Gamal, L. Hemachandra, I. Shperling, and V. Wei, “Using simulated annealing to design good codes,” _IEEE Transactions on Information Theory_ , vol. 33, no. 1, pp. 116–123, Jan 1987.
  * [30] M. H. Garzon, _Theory and Applications of DNA Codeword Design_. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 11–26. [Online]. Available: http://dx.doi.org/10.1007/978-3-642-33860-1_2
  * [31] K. J. Hartemink A. J., Gifford D. K., “Automated constraint-based nucleotide sequence selection for dna computation,” _Biosystems_ , vol. 52, 1999.
  * [32] A. G. Frutos, Q. Liu, A. J. Thiel, A. M. W. Sanner, A. E. Condon, L. M. Smith, and R. M. Corn, “Demonstration of a word design strategy for dna computing on surfaces,” _Nucleic Acids Research_ , vol. 25, no. 23, pp. 4748–4757, 1997. [Online]. Available: http://nar.oxfordjournals.org/content/25/23/4748.abstract
  * [33] T. Krasiński, S. Sakowski, J. Waldmajer and T. Popławski, “Arithmetical Analysis of Biomolecular Finite Automaton,” _Fundamenta Informaticae_ , vol. 128, no. 4, pp. 463–474.
  * [34] B.-T. Zhang and S.-Y. Shin, _Molecular Algorithms for Efficient and Reliable DNA Computing_. Morgan Kaufmann, 1998.
  * [35] N. Roquet, A. P. Soleimany, A. C. Ferris, S. Aaronson, and T. K. Lu, “Synthetic recombinase-based state machines in living cells,” _Science_ , vol. 353, no. 6297, 2016. [Online]. Available: http://science.sciencemag.org/content/353/6297/aad8559
  * [36] Lakin, F. Polo, S. Youssef, K. Gray, R. Petersen, L. Cardelli and A. Phillips, “DNA Strand Displacement Simulator.” [Online]. Available: http://research.microsoft.com/en-us/projects/dna/
  * [37] L. Qian and E. Winfree, “Scaling Up Digital Circuit Computation with DNA Strand Displacement Cascades,” _Science_ , vol. 332, pp. 1196–1201.
  * [38] James D. Watson, Tania A. Baker, Stephen P. Bell, Alexander A. F. Gann, Michael Levine and Richard M. Losick, _Molecular Biology of the Gene_ , 6th ed. Pearson, 2007.
  * [39] David W. Ussery, Trudy Wassenaar and Stefano Borini, _Computing for Comparative Microbial Genomics: Bioinformatics for Microbiologists_ , 1st ed. Springer, 2009.
  * [40] D. Bikard, C. Loot, Z. Baharoglu and D. Mazel, “Folded DNA In Action: Hairpin Formation And Biological Functions In Prokaryotes,” _Microbiol Mol Biol Rev._ , vol. 74, no. 4, pp. 570–588.
  * [41] “CPLEX, ILOG.” [Online]. Available: http://www-03.ibm.com/software/products/us/en/ibmilogcpleoptistud/

## Optimal Set of Symbols for $6$-letter symbol with Enzyme BbvI

CGAAAA | ATGGAA | CCTGAA | TGACAA | TCGTAA
---|---|---|---|---
ACCAGA | CGAGGA | GACGGA | GAACGA | ATCCGA
CTATGA | ATGTGA | TAAACA | TAGCCA | CGCCCA
GATTCA | CAGGTA | GGTGTA | TAACTA | TCCCTA
CCTCTA | GTATTA | TAGTTA | CGGCAG | ACTCAG
AAATAG | CAGTAG | TCTTAG | GCAAGG | AGTGGG
GGTTGG | CGCACG | ACAGCG | GGGGCG | AATGCG
CGACCG | ATCTCG | GTTTCG | GCGATG | CTTCTG
Figure 6: Divisibility by 5: FSM Simulation Steps for Binary Word 1110 Figure
7: FSM for Parity Checker Figure 8: FSM Simulation Steps for Parity Checker
Figure 9: FSM for Regular Expression Matching Figure 10: FSM Simulation Steps
for Regular Expression Matching


# LocalViT: Bringing Locality to Vision Transformers

Yawei Li1 Kai Zhang1 Jiezhang Cao1 Radu Timofte1 Luc Van Gool1,2
1Computer Vision Lab, ETH Zurich, Switzerland 2KU Leuven, Belgium
{yawei.li, kai.zhang, jiezhang.cao, timofter<EMAIL_ADDRESS>
###### Abstract

We study how to introduce locality mechanisms into vision transformers. The
transformer network originates from machine translation and is particularly
good at modelling long-range dependencies within a long sequence. Although the
global interaction between the token embeddings could be well modelled by the
self-attention mechanism of transformers, what is lacking a locality mechanism
for information exchange within a local region. Yet, locality is essential for
images since it pertains to structures like lines, edges, shapes, and even
objects.

We add locality to vision transformers by introducing depth-wise convolution
into the feed-forward network. This seemingly simple solution is inspired by
the comparison between feed-forward networks and inverted residual blocks. The
importance of locality mechanisms is validated in two ways: 1) A wide range of
design choices (activation function, layer placement, expansion ratio) are
available for incorporating locality mechanisms and all proper choices can
lead to a performance gain over the baseline, and 2) The same locality
mechanism is successfully applied to 4 vision transformers, which shows the
generalization of the locality concept. In particular, for ImageNet2012
classification, the locality-enhanced transformers outperform the baselines
DeiT-T [41] and PVT-T [46] by 2.6% and 3.1% with a negligible increase in the
number of parameters and computational effort. Code is available at
https://github.com/ofsoundof/LocalViT.

##  1 Introduction

Figure 1: Comparison between LocalViT and the baseline transformers. The
transformers enhanced by the proposed locality mechanism outperform their
baselines.

Convolutional neural networks (CNNs) now define the state-of-the-art for
computer vision tasks such as image classification [22, 35, 16, 20], object
detection [11, 33], segmentation [27, 15], low-level vision [7, 53], _etc._
CNNs are based on locality in that convolutional filters only perceive a local
region of the input image, _i.e._ the receptive field. By stacking multiple
layers, the effective receptive fields of a deep neural network can be
enlarged progressively. This design enables the network to learn a hierarchy
of deep features, which is essential for the success of CNNs. Meanwhile, the
local, repetitive connections save many parameters compared with fully
connected layers. Yet, one problem is that a larger receptive field can only
be achieved by combining layers, despite alternative attempts at enlarging the
receptive field [51].

A parallel, thriving research strand incorporates global connectivity into the
network via self-attention [42, 43, 28, 48]. This family of networks, _i.e._
transformer networks, originates from machine translation and is very good at
modelling long-range dependencies in sequences. There also is a rising
interest in applying transformers to vision [2, 8, 41]. Vision transformers
have already achieved performances quite competitive with their CNN
counterparts.

To process 2D images with transformers, the input image is first converted to
a sequence of tokens which correspond to patches in the image. Then the
attention module attends to all tokens and a weighted sum is computed as the
tokens for the next layer. In this way, the effective receptive field is
expanded to the whole image via a single self-attention layer. Yet, the
problem of visual transformers is that global connectivity contradicts the
convolutional idea.

Considering the merits of CNNs vs. transformers, a natural question is whether
we can efficiently combine the locality of CNNs and the global connectivity of
vision transformers to improve performance while not increasing model
complexity.

We try to fill the gap between CNNs and vision transformers. Specifically, we
introduce a locality mechanism to the feed-forward network of transformers,
which is inspired by examining the feed-forward network and inverted residuals
[34, 17]. The feed-forward network of transformers consists of two fully
connected layers and the hidden dimension between them is expanded (usually by
a factor of 4) to extract richer features. Similarly, in inverted residual
blocks, the hidden channel between the two $1\times 1$ convolutions is also
expanded. The major difference between them is the efficient depth-wise
convolution in the inverted residual block. Such depth-wise convolution can
provide precisely the mechanism for local information aggregation which is
missing in the feed-forward network of vision transformers. In addition,
depth-wise convolution is efficient in both parameters and computational
complexity.

To cope with the 2D depth-wise convolution, the image tokens of the sequence
from the self-attention module must be rearranged to a 2D feature map, which
is processed by the feed-forward network. The class token is split out and
bypasses the feed-forward network. The derived new feature map is converted
back to image tokens and concatenated with the bypassed class token. The
concatenated sequence is processed by the next transformer layer.

The effectiveness of the introduced locality mechanism is validated in two
ways. Firstly, its properties are investigated experimentally. We draw four
basic conclusions. i. Depth-wise convolution alone can already improve the
performance of the baseline transformer. ii. A better activation function
after depth-wise convolution can result in a significant performance gain.
iii. The locality mechanism is more important for lower layers. iv. Expanding
the hidden dimension of the feed-forward network leads to a larger model
capacity and a higher classification accuracy. Secondly, as shown in Fig. 1,
the locality mechanism is successfully applied to 4 vision transformers, which
underlines its generality. The contributions of this paper are three-fold:

  1. 1.

We bring a locality mechanism to vision transformers by introducing depth-wise
convolutions. The new transformer architecture combines a self-attention
mechanism for global relationship modelling and a locality mechanism for local
information aggregation.

  2. 2.

We analyze the basic properties of the introduced locality mechanism. The
influence of each component (depth-wise convolution, non-linear activation
function, layer placement, and hidden dimension expansion ratio) is singled
out.

  3. 3.

We apply these ideas to vision transformers incl. DeiT [41], T2T-ViT [52], PVT
[46], and TNT [14]. Experiments show that the simple technique proposed in
this paper generalizes well to various transformer architectures.

##  2 Related Work

###  2.1 Transformers and vision transformers

Transformers were first introduced in [42] for machine translation. The
proposed attention mechanism aggregates information from the whole input
sequence. Thus, transformers are especially good at modelling long-range
dependencies between elements of a sequence. Since then, there have been
several attempts to adapt transformers towards vision tasks including object
detection [2, 56], image classification [8, 41, 52, 46, 14], segmentation
[44], multiple object tracking [37, 29], human pose estimation [50, 55], point
cloud processing [12, 54], video processing [10, 31, 38], image super-
resolution [30, 49, 3], image synthesis [9], etc. An extensive review is out
of the scope of this paper. We focus on the most relevant works.

Carion _et al._ first proposed a detection transformer (DETR) for end-to-end
objection detection [2]. This method regards object detection as a set
prediction problem and removes the hand-crafted designs for objection
detection. DETR reasons about the relationship between the learned object
queries and global image context. Following this work, image classification
was targeted. Dosovitskiy _et al._ showed that a pure transformer can be
directly applied to images and performs quite well compared with CNNs on image
classification [8]. Yet, this network relies heavily on large-scale models and
datasets. Thus, Touvron _et al._ showed that it is possible to train vision
transformers in a data-efficient way [41]. The authors introduced an
additional distillation token to the network and proposed hard-label
distillation for vision transformers. Such transformers are identical to those
for machine translation. Recent works propose to adapt transformers to images.
Yuan _et al._ proposed a progressive tokenization method that can model the
local information of nearby tokens and reduce the number of tokens. Wang _et
al._ propose a pyramid architecture for vision transformers [46]. Han _et al._
introduced an additional transformer block for the image token embeddings
[14].

###  2.2 Locality _vs._ global connectivity

Both local information and global connectivity help to reason about the
relationships between image contents. Thus, they are both important for visual
perception. The convolution operation applies a sliding window to the input
and local information is inherently aggregated to compute new representations.
Thus, locality is an intrinsic property of CNNs [23]. Although CNNs can
extract information from a larger receptive field by stacking layers and
forming deep networks, they still lack global connectivity [22, 35, 16]. To
overcome this problem, some researchers add global connectivity to CNNs with
non-local blocks [47, 25].

By contrast, transformers are especially good at modelling long-range
dependencies within a a sequence owing to their attention mechanism [42, 6, 4,
21]. But, in return, a locality mechanism remains to be added for visual
perception. Some works already contributed towards this goal [52, 26]. Yet,
they mainly focus on improving the tokenization and self-attention part. Other
work introduces hybrid architectures of CNNs and transformers [2, 36, 24]. In
summary, little attention has been paid to the feed-forward network of vision
transformers.

###  2.3 Depth-wise convolution and inverted residuals

Compared with normal convolution, the computations of depth-wise convolution
are only conducted channel-wise. That is, to obtain a channel of the output
feature map, the convolution is only conducted on one input feature map. Thus,
depth-wise convolution is efficient both in terms of parameters and
computation. Thus, Howard _et al._ first proposed the MobileNet architecture
based on depth-wise separable convolutions [18]. This lightweight and
computationally efficient network is quite friendly for mobile devices. Since
then, depth-wise convolution has been widely used to design efficient models.
Inverted residual blocks are based on depth-wise convolution and were first
introduced in MobileNetV2 [34]. The inverted residual blocks are composed of a
sequence of $1\times 1$ \- depth-wise -$1\times 1$ convolutions. The hidden
dimension between the two $1\times 1$ convolutions is expanded. The
utilization of depth-wise convolution avoids the drastic increase of model
complexity brought by normal convolution. Due to the efficiency of this
module, it is widely used to form the search space of neural architecture
search (NAS) [17, 39, 40, 13, 1]. The expansion of the hidden dimension of
inverted residuals is quite similar to the feed-forward network of vision
transformers. This motivates us to think about the connection between them
(See Sec. 3.2).

\begin{overpic}[width=238.48886pt]{fig1.pdf}
\put(3.5,9.2){\color[rgb]{0,0,0}{$d$}}
\put(2.0,37.0){\color[rgb]{0,0,0}{$\gamma d$}}
\put(3.5,62.0){\color[rgb]{0,0,0}{$d$}}
\par\put(23.0,21.0){\color[rgb]{0,0,0}{\footnotesize Fully Connected}}
\put(23.0,51.5){\color[rgb]{0,0,0}{\footnotesize Fully Connected}}
\par\put(76.0,24.0){\color[rgb]{0,0,0}{\footnotesize$1\times 1$ Conv}}
\put(76.0,55.0){\color[rgb]{0,0,0}{\footnotesize$1\times 1$ Conv}}
\par\put(27.0,3.0){\color[rgb]{0,0,0}{\footnotesize(a)}}
\put(73.0,3.0){\color[rgb]{0,0,0}{\footnotesize(b)}} \par\end{overpic} Figure
2: Visualization of the feed-forward network in transformers from different
perspectives. (a) The input is regarded as a sequence of tokens. (b) An
equivalent perspective is to still rearrange the tokens as a 2D lattice.

##  3 Methodology

Transformers are usually composed of encoders and decoders with similar
building blocks. For the image classification task considered here, only the
encoders are included in the network. Thus, we mainly describe the operations
in the encoder layers. The encoders have two components, _i.e._ the self-
attention mechanism that relates a token to all of the tokens and a feed-
forward network that is applied to every token. We specifically explain how to
introduce locality into the feed-forward network.

###  3.1 Input interpretation

Sequence perspective. Inherited from language modelling, transformers regard
the input as a sequence that contains elements of embedded vectors. Consider
an input image $\mathbf{X}\in\mathbb{R}^{C\times H\times W}$, where $C$ and
$H\times W$ denote the channel and spatial dimension of the input image,
respectively. The input image is first converted to a sequence of tokens
$\\{\hat{\mathbf{X}}_{i}\in\mathbb{R}^{d}|i=1,\ldots,N\\}$, where $d=C\times
p^{2}$ is the embedding dimension and $N=\frac{HW}{p^{2}}$. The tokens can be
aggregated into a matrix $\hat{\mathbf{X}}\in\mathbb{R}^{N\times d}$.

Self-attention. In the self-attention mechanism, the relationship between the
tokens is modelled by the similarity between the projected query-key pairs,
yielding the attention score. The new tokens are computed as the weighted sum
of the project values. That is,

$\mathbf{Z}=\mathrm{Softmax}(\mathbf{Q}\mathbf{K}^{T}/\sqrt{d})\mathbf{V},$
(1)

where the $\mathrm{Softmax}$ function is applied to the rows of the similarity
matrix and $d$ provides a normalization. The query, key, and value are a
projection of the tokens, _i.e._ $\mathbf{Q}=\hat{\mathbf{X}}\mathbf{W}_{Q}$,
$\mathbf{K}=\hat{\mathbf{X}}\mathbf{W}_{K}$,
$\mathbf{V}=\hat{\mathbf{X}}\mathbf{W}_{V}$. The projection matrices
$\mathbf{W}_{Q}$ and $\mathbf{W}_{K}$ have the same size while
$\mathbf{W}_{V}$ could have a different size. In practice, the three
projection matrices usually have the same size, _i.e._
$\mathbf{W}_{Q},\mathbf{W}_{K},\mathbf{W}_{V}\in\mathbb{R}^{d\times d}$.

Feed-forward network. After the self-attention layer, a feed-forward network
is appended. The feed-forward network consists of two fully-connected layers
and transforms the features along the embedding dimension. The hidden
dimension between the two fully-connected layers is expanded to learn a richer
feature representation. That is,

$\mathbf{Y}=f(\mathbf{Z}\mathbf{W}_{1})\mathbf{W}_{2},$ (2)

where $\mathbf{W}_{1}\in\mathbb{R}^{d\times\gamma d}$,
$\mathbf{W}_{2}\in\mathbb{R}^{\gamma d\times d}$, and $f(\cdot)$ denotes a
non-linear activation function. For the sake of simplicity, the bias term is
omitted. The dimension expansion ratio $\gamma$ is usually set to 4. As shown
in Fig. 2 (a), the input to the feed-forward network is regarded as a sequence
of embedding vectors.

Lattice perspective. Since the feed-forward network is applied position-wise
to a sequence of tokens $\mathbf{Z}\in\mathbb{R}^{N\times d}$, an exactly
equivalent representation is to rearrange the sequence of tokens into a 2D
lattice as shown in Fig. 2 (b). Then the reshaped feature representation is

$\mathbf{Z}^{r}=\mathrm{Seq2Img}(\mathbf{Z}),\mathbf{Z}^{r}\in\mathbb{R}^{h\times
w\times d},$ (3)

where $h=H/p$ and $w=W/p$. The operation $\mathrm{Seq2Img}$ converts a
sequence to a 2D feature map. Each token is placed to a pixel location of the
feature map. The benefit of this perspective is that the proximity between
tokens is recovered, which provides the chance to introduce locality into the
network. The fully-connected layers could be replaced by $1\times 1$
convolutions, _i.e._

$\displaystyle\mathbf{Y}^{r}$
$\displaystyle=f(\mathbf{Z}^{r}\circledast\mathbf{W}_{1}^{r})\circledast\mathbf{W}_{2}^{r},$
(4) $\displaystyle\mathbf{Y}$
$\displaystyle=\mathrm{Img2Seq}(\mathbf{Y}^{r}),$ (5)

where $\mathbf{W}_{1}^{r}\in\mathbb{R}^{d\times\gamma d\times 1\times 1}$ and
$\mathbf{W}_{2}^{r}\in\mathbb{R}^{\gamma d\times d\times 1\times 1}$ are
reshaped from $\mathbf{W}_{1}$ and $\mathbf{W}_{2}$ and represent the
convolutional kernels. The operation $\mathrm{Img2Seq}$ converts the image
feature map back to a token sequence which is used by the next self-attention
layer.

###  3.2 Locality

Since only $1\times 1$ convolution is applied to the feature map, there is a
lack of information interaction between adjacent pixels. Besides, the self-
attention part of the transformer only captures global dependencies between
all of the tokens. Thus, the transformer block does not have a mechanism to
model the local dependencies between nearby pixels. It would be interesting if
locality could be brought to transformers in an efficient way.

The expansion of the hidden dimension between fully-connected layers and the
lattice perspective of the feed-forward network remind us of the inverted
residual block proposed in MobileNets [34, 17]. As shown in Fig. 3, both of
the feed-forward network and the inverted residual expand and squeeze the
hidden dimension by $1\times 1$ convolution. The only difference is that there
is a depth-wise convolution in the inverted residual block. Depth-wise
convolution applies a $k\times k$ ($k>1$) convolution kernel per channel. The
features inside the $k\times k$ kernel is aggregated to compute a new feature.
Thus, depth-wise convolution is an efficient way of introducing locality into
the network. Considering that, we reintroduce depth-wise convolution into the
feed-forward network of transformers. And the computation could be represented
as

$\mathbf{Y}^{r}=f\big{(}f(\mathbf{Z}^{r}\circledast\mathbf{W}_{1}^{r})\circledast\mathbf{W}_{d}\big{)}\circledast\mathbf{W}_{2}^{r},$
(6)

where $\mathbf{W}_{d}\in\mathbb{R}^{\gamma d\times 1\times k\times k}$ is the
kernel of the depth-wise convolution. The finally used network is shown in
Fig. 3 (c). The input, _i.e._ a sequence of tokens is first reshaped to a
feature map rearranged on a 2D lattice. Then two $1\times 1$ convolutions
along with a depth-wise convolution are applied to the feature map. After
that, the feature map is reshaped to a sequence of tokens which are used as by
the self-attention of the network transformer layer.

Note that the non-linear activation functions are not visualized in Fig. 3.
Yet, they play a quite important role in enhancing the network capacity,
especially for efficient networks. In particular, we try ReLU6, h-swish [17],
squeeze-and-excitation (SE) module [19], efficient channel attention (ECA)
module [45], and their combinations. A thorough analysis of the activation
function is discussed in the experiments section.

\begin{overpic}[width=238.48886pt]{fig2.pdf}
\put(10.0,20.0){\color[rgb]{0,0,0}{\footnotesize$1\times 1$ Conv}}
\put(10.0,40.0){\color[rgb]{0,0,0}{\footnotesize$1\times 1$ Conv}}
\par\put(43.0,20.0){\color[rgb]{0,0,0}{\footnotesize$1\times 1$ Conv}}
\put(40.0,29.2){\color[rgb]{0,0,0}{\footnotesize$3\times 3$ DW Conv}}
\put(43.0,40.0){\color[rgb]{0,0,0}{\footnotesize$1\times 1$ Conv}}
\par\put(78.5,10.2){\color[rgb]{0,0,0}{\footnotesize Seq2Img}}
\put(76.5,20.0){\color[rgb]{0,0,0}{\footnotesize$1\times 1$ Conv}}
\put(73.0,29.2){\color[rgb]{0,0,0}{\footnotesize$3\times 3$ DW Conv}}
\put(76.5,40.0){\color[rgb]{0,0,0}{\footnotesize$1\times 1$ Conv}}
\put(78.5,49.2){\color[rgb]{0,0,0}{\footnotesize Img2Seq}}
\par\put(16.4,0.3){\color[rgb]{0,0,0}{\footnotesize(a)}}
\put(49.0,0.3){\color[rgb]{0,0,0}{\footnotesize(b)}}
\put(82.8,0.3){\color[rgb]{0,0,0}{\footnotesize(c)}} \par\end{overpic} Figure
3: Comparison between the (a) convolutional version of the feed-forward
network in vision transformers, the (b) inverted residual blocks, and (c) the
finally utilized network that brings locality mechanism into transformers.
“DW” denotes depth-wise convolution. To cope with the convolution operation,
the conversion between sequence and image feature map is added by “Seq2Img”
and “Img2Seq” in (c).

###  3.3 Class token

To apply vision transformers to image classification, a trainable class token
is added and inserted into the token embedding, _i.e._

$\hat{\mathbf{X}}\leftarrow\mathrm{Concat}(\mathbf{X}_{cls},\hat{\mathbf{X}}),$
(7)

where $\leftarrow$ denotes the assignment operation,
$\mathbf{X}_{cls}\in\mathbb{R}^{1\times d}$ is the class token. The new matrix
has the dimension of $(N+1)\times d$ and $N+1=\frac{HW}{p^{2}}+1$ tokens. In
the self-attention module, the class token exchanges information with all
other image tokens and gathers information for the final classification. In
the feed-forward network, the same transformation is applied to the class
token and the image tokens.

When depth-wise convolution is introduced into the feed-forward network, the
sequence of tokens needs to be rearranged into an image feature map. Yet, the
additional dimension brought by the class token makes the exact rearrangement
impossible. To circumvent this problem, we split the $N+1$ tokens in Eqn. (1)
into a class token and image tokens again, _i.e._

$(\mathbf{Z}_{cls},\mathbf{Z})\leftarrow\mathrm{Split}(\mathbf{Z}).$ (8)

Then the new image token is passed through the feed-forward network according
to Eqns. (3), (6), and (5), leading to $\mathbf{Y}$. The class token is not
passed through the feed-forward network. Instead, it is directly concatenated
with $\mathbf{Y}$, _i.e._

$\mathbf{Y}\leftarrow\mathrm{Concat}(\mathbf{Z}_{cls},\mathbf{Y}).$ (9)

The split and concatenation of the class token is done for every transformer
layer. Although the class token $\mathbf{Z}_{cls}$ is not passed through the
feed-forward network, the performance of the overall network is not adversely
affected. This is because the information exchange and aggregation is done
only in the self-attention part. A feed-forward network like Eqn. (2) only
enforces a transformation within each token.

Network | $\gamma$ | DW | Params | FLOPs | Top-1
---|---|---|---|---|---
(M) | (G) | Acc. (%)
DeiT-T [41] | 4 | No | 5.7 | 1.3 | 72.2
LocalViT-T | 4 | No | 5.7 | 1.3 |  72.5 (0.3$\uparrow$)
LocalViT-T* | 4 | Yes | 5.8 | 1.3 |  73.7 (1.5$\uparrow$)
DeiT-T [41] | 6 | No | 7.5 | 1.6 | 73.1†
LocalViT-T | 6 | No | 7.5 | 1.6 |  74.3 (1.2$\uparrow$)
LocalViT-T* | 6 | Yes | 7.7 | 1.6 |  76.1 (3.0$\uparrow$)
Table 1: Investigation of the locality brought by depth-wise convolution. A
comparison is made with DeiT. “DW” denotes depth-wise convolution. “Params”
denotes the number of parameters in the network. “FLOPs” denotes the number of
floating-point operations. Top-1 accuracy is reported. The other tables use
the same evaluation metric. *ReLU6 is used as the activation function after
depth-wise convolution. †Results derived by modifying the DeiT architecture
and training the network with the same training protocol.

##  4 Experimental Results

This section gives the experimental results for image classification. We first
study how the locality brought by depth-wise convolution can improve the
performance of transformers. Then we show the influence of a non-linear
activation function placed after the depth-wise convolution. The layers that
are equipped with locality also influence the network capacity and this is
also studied. An ablation study of the hidden dimension expansion ratio
$\gamma$ is also made. All those experiments are based on DeiT-T [41].
Finally, the study on the generalization to other vision transformers
including T2T-ViT [52], PVT [46], TNT [14] for image classification and the
comparison with CNNs are made. The transformers that are equipped with
locality are denoted as LocalViT followed by the suffix that denotes the basic
architecture.

###  4.1 Implementation details

In order to introduce locality into transformers, we only adapt the feed-
forward network of vision transformers while the other parts such as self-
attention, and position encoding are not changed. The implementation is based
on the inverted residual blocks [34, 17]. A batch normalization layer is
appended to the 2D convolutions. The layer normalization before the feed-
forward network is removed. Path drop after the feed-forward network is also
removed. The same modification is also applied to the T2T module of T2T-ViT
[52]. The feed-forward network of the inner transformer block in TNT [14] is
not adapted. For PVT [46], the class token is only introduced in the final
stage of the pyramid. Thus, the split and concatenation of the class token for
the feed-forward network is only applied in the final stage.

Experimental setup. The ImageNet2012 dataset [5] is used in this paper. The
dataset contains 1.28M training images and 50K validation images from one
thousand classes. We follow the same training protocol as DeiT [41]. The input
image is randomly cropped with size $224\times 224$. Cross-entropy is used as
the loss function. Label smoothing is used. The weight decay factor is set to
0.05. The AdamW optimizer is used with a momentum of 0.9. The training
continues for 300 epochs. The batch size is set to 1024. The initial learning
rate is set to $1\times 10^{-3}$ and decreases to $1\times 10^{-5}$ following
a cosine learning rate scheduler. During validation, a center crop of the
validation images is conducted. In the following sections, we study different
aspects that could influence the performance of the introduced locality.

Activation | Params | FLOPs | Top-1
---|---|---|---
(M) | (G) | Acc. (%)
Deit-T [41] | 5.7 | 1.3 | 72.2
ReLU6 | 5.8 | 1.3 |  73.7 (1.5$\uparrow$)
h-swish | 5.8 | 1.3 |  74.4 (2.2$\uparrow$)
h-swish + ECA | 5.8 | 1.3 |  74.5 (2.3$\uparrow$)
h-swish + SE-192 | 5.9 | 1.3 |  74.8 (2.6$\uparrow$)
h-swish + SE-96 | 6.0 | 1.3 |  74.8 (2.6$\uparrow$)
h-swish + SE-48 | 6.1 | 1.3 |  75.0 (2.8$\uparrow$)
h-swish + SE-4 | 9.4 | 1.3 |  75.8 (3.6$\uparrow$)
Table 2: Investigation of the non-linear activation function. The combination of h-swish, ECA [45], and SE [19] is studied. “SE-**” means the reduction ratio in the squeeze-and-excitation module. The study is based on LocalViT-T. DW Placement | Layer | Params | FLOPs | Top-1
---|---|---|---|---
(M) | (G) | Acc. (%)
High |  9$\sim$12 | 5.78 | 1.26 | 69.1
Mid |  5$\sim$8 | 5.78 | 1.26 | 72.1
Low |  1$\sim$4 | 5.78 | 1.26 | 73.1
Low |  1$\sim$8 | 5.84 | 1.27 | 74.0
All |  1$\sim$12 | 5.91 | 1.28 | 74.8
Table 3: Influence of the placement of locality. “All” means all of the
transformer layers are enhanced by depth-wise convolution. “Low”, “Mid”, and
“High” mean the lower, middle, and higher transformer layers are equipped with
depth-wise convolution, respectively. The study is based on LocalViT-T.

###  4.2 Influence of the locality

We first study how the local information could help to improve the performance
of vision transformers. Different hidden dimension expansion ratios $\gamma$
are investigated. First of all, due to the change of the operations in the
feed-forward network (Sec. 4.1), the Top-1 accuracy of LocalViT-T is slightly
increased even without the depth-wise convolution. The performance gain is
0.3% for $\gamma=4$ and is increased to 1.2% for $\gamma=6$. Note that
compared with DeiT-T, no additional parameters and computation are introduced
for the improvement. When locality is incorporated into the feed-forward
network, there is a significant improvement of the model accuracy, _i.e._ 1.5%
for $\gamma=4$ and 3.0% for $\gamma=6$. Compared with the baseline, there only
is a marginal increase in the number of parameters and a negligible increase
in the amount of computation. Thus, the performance of vision transformers can
be significantly improved by the incorporation of a locality mechanism and the
adaptation of the operation in the feed-forward network.

Expansion | SE | Params | FLOPs | Top-1
---|---|---|---|---
Ratio $\gamma$ | (M) | (G) | Acc. (%)
1 | No | 3.1 | 0.7 | 65.9
Yes | 3.1 | 0.7 | 66.2
2 | No | 4.0 | 0.9 | 70.1
Yes | 4.0 | 0.9 | 70.6
3 | No | 4.9 | 1.1 | 72.9
Yes | 5.0 | 1.1 | 73.1
4 | No | 5.8 | 1.3 | 74.4
Yes | 5.9 | 1.3 | 74.8
Table 4: Investigating the expansion ratio of hidden layers in the feed-
forward network.

###  4.3 Activation functions

The non-linear activation function after depth-wise convolution used in the
above experiments is simply ReLU6. The benefit of using other non-linear
activation functions is also studied. First of all, by replacing the
activation function from ReLU6 to h-swish, the gain of Top-1 accuracy over the
baseline is increased from 1.5% to 2.2%. This shows the benefit of h-swish
activation functions can be easily extended from CNNs to vision transformers.
Next, the h-swish activation function is combined with other channel attention
modules including ECA [45] and SE [19]. By adding ECA, the performance is
further improved by 0.1%. Considering that only 60 parameters are introduced,
this improvement is still considerable under a harsh parameter budget.

Network | Image Size | Params (M) | FLOPs (G) | Top-1 Acc. (%) | Top-5 Acc. (%)
---|---|---|---|---|---
CNNs |  |
ResNet-18 [16] | $224\times 224$ | 11.7 | 1.8 | 69.8 | 89.1
ResNet-50 [16] | $224\times 224$ | 25.6 | 4.1 | 76.1 | 92.9
DenseNet-169 [20] | $224\times 224$ | 14.2 | 3.4 | 75.6 | 92.8
RegNet-4GF [32] | $224\times 224$ | 20.7 | 4.0 | 80.0 | –
MobileNetV1 [18] | $224\times 224$ | 4.2 | 0.6 | 70.6 | –
MobileNetV2 (1.4) [34] | $224\times 224$ | 6.9 | 0.6 | 74.7 | –
EfficientNet-B0 [40] | $224\times 224$ | 5.3 | 0.4 | 77.1 | 93.3
EfficientNet-B4 [40] | $380\times 380$ | 19.3 | 4.5 | 82.9 | 96.4
Transformers |  |
DeiT-T [41] | $224\times 224$ | 5.7 | 1.3 | 72.2 | 91.1
LocalViT-T | $224\times 224$ | 5.9 | 1.3 |  74.8 (2.6$\uparrow$) | 92.6
DeiT-T [41] | $224\times 224$ | 5.9 | 1.3 | 74.5 | –
DeiT-S [41] | $224\times 224$ | 22.1 | 4.6 | 79.8 | 95.1
LocalViT-S | $224\times 224$ | 22.4 | 4.6 |  80.8 (1.0$\uparrow$) | 95.4
DeiT-S [41] | $224\times 224$ | 22.4 | 4.6 | 81.2 | –
T2T-ViT-7 [52] | $224\times 224$ | 4.3 | 1.2 | 71.7 | –
LocalViT-T2T | $224\times 224$ | 4.3 | 1.2 |  72.5 (0.8$\uparrow$) | –
TNT-T [14] | $224\times 224$ | 6.1 | 1.4 | 73.6 | 91.9
LocalViT-TNT | $224\times 224$ | 6.3 | 1.4 |  75.9 (2.3$\uparrow$) | 93.0
PVT-T [46] | $224\times 224$ | 13.2 | 4.7 | 75.1 | 92.3
LocalViT-PVT | $224\times 224$ | 13.5 | 4.8 |  78.2 (3.1$\uparrow$) | 94.2
Table 5: Image classification results for different CNNs and vision
transformers. The locality functionality is enabled for four different vision
transformers.

Another significant improvement is brought by a squeeze-and-excitation module.
When the reduction ratio in the squeeze-and-excitation module is reduced from
192 to 4, the gain of Top-1 accuracy is gradually increased from 2.6% to 3.6%.
The number of parameters is also increased accordingly. Note that, for all of
the networks, the computational complexity is almost the same. This implies
that if there is no strict limitation on the number of parameters, advanced
non-linear activation functions could be used. In the following experiments,
we use the combination of h-swish and SE as the non-linear activation function
after depth-wise convolution. Additionally, the reduction ratio of the
squeeze-and-excitation module is chosen such that only 4 channels are kept
after the squeeze operation. This choice of design achieves a good balance
between the number of parameters and the model accuracy. Thus, local
information is also important in vision transformers. A wide range of
efficient modules could be introduced into the feed-forward network of vision
transformers to expand the network capacity.

###  4.4 Placement of locality

The transformer layers where the locality is introduced can also influence the
performance of the network. Thus, an ablation study based on LocalViT-T is
conducted to study their effect. The results is reported in Table 3. There are
in total 12 transformer layers in the network. We divide the 12 layers into 3
groups corresponding to “Low”, “Mid”, and “High” stages. For the former 3 rows
of Table 3, we independently insert locality into the three stages. As the
locality is moved gradually from lower stages to the higher stages, the
accuracy of the network is decreased. This shows that local information is
especially important for the lower layers. This is also consistent with our
intuition. That is, when the depth-wise convolution is applied to the lower
layers, the local information aggregated there could also be propagated to the
higher layers, which is important to improve the overall performance of the
network.

When the locality is introduced only in the higher stage, the Top-1 accuracy
is even lower than DeiT-T. To investigate whether locality in the higher
layers always has an adverse effect, we progressively allow more lower layers
to have depth-wise convolution until locality is enabled for all layers. This
corresponds to the last three rows of Table 3. The observation is that
starting from the lower layers, the performance of the network could be
gradually improved as locality is enabled for more layers. Thus, introducing
the locality to the lower layers is more advantageous compared with higher
layers.

(a) DeiT-T _vs._ LocalViT-T. Accuracy.

(b) PVT-T _vs._ LocalViT-PVT. Accuracy.

(c) TNT-T _vs._ LocalViT-TNT. Accuracy.

(d) DeiT-T _vs._ LocalViT-T. Training loss.

(e) PVT-T _vs._ LocalViT-PVT. Training loss.

(f) TNT-T _vs._ LocalViT-TNT. Training loss.

Figure 4: Comparison of Top-1 accuracy, Top-5 accuracy, and training loss
between the baseline transformers and the locality enhanced LocalViT.

###  4.5 Expansion ratio $\gamma$

The effect of the expansion ratio of the hidden dimension of the feed-forward
network is also investigated. The results are shown in Table 4. Expanding the
hidden dimension of the feed-forward network can have a significant effect on
the performance of the transformers. As the expansion ratio is increased from
1 to 4, the Top-1 accuracy is increased from less than 70% to nearly 75%. The
model complexity is also almost doubled. Thus, the network performance and
model complexity can be balanced by the hidden dimension expansion ratio
$\gamma$. Squeeze-and-excitation can be more beneficial for smaller $\gamma$.

###  4.6 Generalization and comparison

Finally, we try to generalize the knowledge derived above to more vision
transformers including DeiT-S [41], T2T-ViT [52], TNT [14], PVT [46] and
compare their performance with CNNs. The result is shown in Table 5.

We draw two major conclusions from Table 5. Firstly, the effectiveness of
locality can be generalized to a wide range of vision transformers based on
the following observations. I. Compared with DeiT, LocalViT can yield a higher
classification accuracy for both the tiny and small version of the network.
The increase of Top-1 accuracy is 2.6% and 1.0%, resp. LocalViT-T even
outperforms DeiT-T which is enhanced by knowledge distillation from
RegNetY-160 [32]. The small version LocalViT-S is slightly worse than DeiT-S
by 0.4%. II. LocalViT-T2T outperforms T2T-ViT-7 by 0.8%. Note that T2T-ViT
already tries to model the local structure information in the tokens-to-token
module. III. In TNT, an additional transformer block is used to extract local
features for the image tokens. Thus, the locality is also considered in TNT.
The modified network, _i.e._ LocalViT-TNT could still improve the
classification accuracy by a large margin of 2.3%. IV. The biggest improvement
comes from PVT. Introducing the locality module leads to a gain of 3.1% over
PVT-T. V. The comparison of the training log between the baseline transformers
and LocalViT is shown in Fig. 4. During the training phase, LocalViT
consistently leads to a lower training loss and higher validation accuracy
than the baseline transformers.

Secondly, some versions of the enhanced vision transformer LocalViT are
already quite comparable or even outperform CNNs. This conclusion can be drawn
by making the pairwise comparison, _i.e._ LocalViT-T _vs._ MobileNetV2 (1.4),
LocalViT-S _vs._ ResNet-50, LocalViT-T2T _vs._ MobileNetV1, LocalViT-PVT _vs._
DenseNet-169 _etc._

##  5 Conclusion

In this paper, we proposed to incorporate a locality mechanism into vision
transformers. This is done by incorporating 2D depth-wise convolutions
followed by a non-linear activation function into the feed-forward network of
vision transformers. The idea is motivated by the comparison between the feed-
forward network of transformers and the inverted residuals of MobileNets. In
previous works, the input to the feed-forward network is a sequence of tokens
embedding converted from an image. To cope with the locality mechanism, the
sequence of tokens embedding is rearranged into a lattice as a 2D feature map,
which is used as the input to the enhanced feed-forward network. To enable the
rearrangement, the class token is split before the feed-forward network and
concatenated with other image embeddings after the feed-forward network. A
series of studies were made to investigate various factors (activation
function, layer placement, and expansion ratio) that might influence of
performance of the locality mechanism. The proposed locality mechanism is
successfully applied to four different vision transformers, which validates
its generality.

Acknowledgements: This work was partly supported by the ETH Zürich Fund (OK),
a Huawei Technologies Oy (Finland) project, and an Amazon AWS grant.

## References

  * [1] Han Cai, Ligeng Zhu, and Song Han.  Proxylessnas: Direct neural architecture search on target task and hardware.  arXiv preprint arXiv:1812.00332, 2018.
  * [2] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko.  End-to-end object detection with transformers.  In European Conference on Computer Vision, pages 213–229. Springer, 2020.
  * [3] Hanting Chen, Yunhe Wang, Tianyu Guo, Chang Xu, Yiping Deng, Zhenhua Liu, Siwei Ma, Chunjing Xu, Chao Xu, and Wen Gao.  Pre-trained image processing transformer.  arXiv preprint arXiv:2012.00364, 2020.
  * [4] Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al.  Rethinking attention with performers.  arXiv preprint arXiv:2009.14794, 2020.
  * [5] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  ImageNet: A large-scale hierarchical image database.  In Proc. CVPR, pages 248–255. IEEE, 2009.
  * [6] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805, 2018.
  * [7] Chao Dong, Chen Change Loy, Kaiming He, and Xiaoou Tang.  Learning a deep convolutional network for image super-resolution.  In Proc. ECCV, pages 184–199. Springer, 2014.
  * [8] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  arXiv preprint arXiv:2010.11929, 2020.
  * [9] Patrick Esser, Robin Rombach, and Björn Ommer.  Taming transformers for high-resolution image synthesis.  arXiv preprint arXiv:2012.09841, 2020.
  * [10] Rohit Girdhar, Joao Carreira, Carl Doersch, and Andrew Zisserman.  Video action transformer network.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 244–253, 2019.
  * [11] Ross Girshick, Jeff Donahue, Trevor Darrell, and Jitendra Malik.  Rich feature hierarchies for accurate object detection and semantic segmentation.  In Proc. CVPR, pages 580–587, 2014.
  * [12] Meng-Hao Guo, Jun-Xiong Cai, Zheng-Ning Liu, Tai-Jiang Mu, Ralph R Martin, and Shi-Min Hu.  Pct: Point cloud transformer.  arXiv preprint arXiv:2012.09688, 2020.
  * [13] Zichao Guo, Xiangyu Zhang, Haoyuan Mu, Wen Heng, Zechun Liu, Yichen Wei, and Jian Sun.  Single path one-shot neural architecture search with uniform sampling.  In European Conference on Computer Vision, pages 544–560. Springer, 2020.
  * [14] Kai Han, An Xiao, Enhua Wu, Jianyuan Guo, Chunjing Xu, and Yunhe Wang.  Transformer in transformer.  arXiv preprint arXiv:2103.00112, 2021.
  * [15] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick.  Mask r-cnn.  In Proceedings of the IEEE international conference on computer vision, pages 2961–2969, 2017.
  * [16] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proc. CVPR, pages 770–778, 2016.
  * [17] Andrew Howard, Mark Sandler, Grace Chu, Liang-Chieh Chen, Bo Chen, Mingxing Tan, Weijun Wang, Yukun Zhu, Ruoming Pang, Vijay Vasudevan, et al.  Searching for mobilenetv3.  In Proc. ICCV, pages 1314–1324, 2019.
  * [18] Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam.  MobileNets: Efficient convolutional neural networks for mobile vision applications.  arXiv preprint arXiv:1704.04861, 2017.
  * [19] Jie Hu, Li Shen, and Gang Sun.  Squeeze-and-excitation networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 7132–7141, 2018.
  * [20] Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q Weinberger.  Densely connected convolutional networks.  In Proc. CVPR, pages 2261–2269, 2017.
  * [21] Nikita Kitaev, Łukasz Kaiser, and Anselm Levskaya.  Reformer: The efficient transformer.  arXiv preprint arXiv:2001.04451, 2020.
  * [22] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In Proc. NeurIPS, pages 1097–1105, 2012.
  * [23] Yann LeCun, Yoshua Bengio, et al.  Convolutional networks for images, speech, and time series.  The handbook of brain theory and neural networks, 3361(10):1995, 1995.
  * [24] Changlin Li, Tao Tang, Guangrun Wang, Jiefeng Peng, Bing Wang, Xiaodan Liang, and Xiaojun Chang.  Bossnas: Exploring hybrid cnn-transformers with block-wisely self-supervised neural architecture search.  arXiv preprint arXiv:2103.12424, 2021.
  * [25] Ding Liu, Bihan Wen, Yuchen Fan, Chen Change Loy, and Thomas S Huang.  Non-local recurrent network for image restoration.  arXiv preprint arXiv:1806.02919, 2018.
  * [26] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  arXiv preprint arXiv:2103.14030, 2021.
  * [27] Jonathan Long, Evan Shelhamer, and Trevor Darrell.  Fully convolutional networks for semantic segmentation.  In Proc. CVPR, pages 3431–3440, 2015.
  * [28] Sachin Mehta, Marjan Ghazvininejad, Srinivasan Iyer, Luke Zettlemoyer, and Hannaneh Hajishirzi.  Delight: Very deep and light-weight transformer.  arXiv preprint arXiv:2008.00623, 2020.
  * [29] Tim Meinhardt, Alexander Kirillov, Laura Leal-Taixe, and Christoph Feichtenhofer.  Trackformer: Multi-object tracking with transformers.  arXiv preprint arXiv:2101.02702, 2021.
  * [30] Chong Mou, Jian Zhang, Xiaopeng Fan, Hangfan Liu, and Ronggang Wang.  Cola-net: Collaborative attention network for image restoration.  arXiv preprint arXiv:2103.05961, 2021.
  * [31] Daniel Neimark, Omri Bar, Maya Zohar, and Dotan Asselmann.  Video transformer network.  arXiv preprint arXiv:2102.00719, 2021.
  * [32] Ilija Radosavovic, Raj Prateek Kosaraju, Ross Girshick, Kaiming He, and Piotr Dollár.  Designing network design spaces.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10428–10436, 2020.
  * [33] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster R-CNN: Towards real-time object detection with region proposal networks.  In Proc. NeurIPS, pages 91–99, 2015.
  * [34] Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen.  MobileNetV2: Inverted residuals and linear bottlenecks.  In Proc. CVPR, pages 4510–4520, 2018.
  * [35] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  arXiv preprint arXiv:1409.1556, 2014.
  * [36] Aravind Srinivas, Tsung-Yi Lin, Niki Parmar, Jonathon Shlens, Pieter Abbeel, and Ashish Vaswani.  Bottleneck transformers for visual recognition.  arXiv preprint arXiv:2101.11605, 2021.
  * [37] Peize Sun, Yi Jiang, Rufeng Zhang, Enze Xie, Jinkun Cao, Xinting Hu, Tao Kong, Zehuan Yuan, Changhu Wang, and Ping Luo.  Transtrack: Multiple-object tracking with transformer.  arXiv preprint arXiv:2012.15460, 2020.
  * [38] Jing Tan, Jiaqi Tang, Limin Wang, and Gangshan Wu.  Relaxed transformer decoders for direct action proposal generation.  arXiv preprint arXiv:2102.01894, 2021.
  * [39] Mingxing Tan, Bo Chen, Ruoming Pang, Vijay Vasudevan, Mark Sandler, Andrew Howard, and Quoc V Le.  Mnasnet: Platform-aware neural architecture search for mobile.  In Proc. CVPR, pages 2820–2828, 2019.
  * [40] Mingxing Tan and Quoc V Le.  Efficientnet: Rethinking model scaling for convolutional neural networks.  arXiv preprint arXiv:1905.11946, 2019.
  * [41] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou.  Training data-efficient image transformers & distillation through attention.  arXiv preprint arXiv:2012.12877, 2020.
  * [42] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  arXiv preprint arXiv:1706.03762, 2017.
  * [43] Hanrui Wang, Zhanghao Wu, Zhijian Liu, Han Cai, Ligeng Zhu, Chuang Gan, and Song Han.  Hat: Hardware-aware transformers for efficient natural language processing.  arXiv preprint arXiv:2005.14187, 2020.
  * [44] Huiyu Wang, Yukun Zhu, Bradley Green, Hartwig Adam, Alan Yuille, and Liang-Chieh Chen.  Axial-deeplab: Stand-alone axial-attention for panoptic segmentation.  In European Conference on Computer Vision, pages 108–126. Springer, 2020.
  * [45] Qilong Wang, Banggu Wu, Pengfei Zhu, Peihua Li, Wangmeng Zuo, and Qinghua Hu.  Eca-net: Efficient channel attention for deep convolutional neural networks.  In CVPR, 2020.
  * [46] Wenhai Wang, Enze Xie, Xiang Li, Deng-Ping Fan, Kaitao Song, Ding Liang, Tong Lu, Ping Luo, and Ling Shao.  Pyramid vision transformer: A versatile backbone for dense prediction without convolutions.  arXiv preprint arXiv:2102.12122, 2021.
  * [47] Xiaolong Wang, Ross Girshick, Abhinav Gupta, and Kaiming He.  Non-local neural networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 7794–7803, 2018.
  * [48] Zhanghao Wu, Zhijian Liu, Ji Lin, Yujun Lin, and Song Han.  Lite transformer with long-short range attention.  arXiv preprint arXiv:2004.11886, 2020.
  * [49] Fuzhi Yang, Huan Yang, Jianlong Fu, Hongtao Lu, and Baining Guo.  Learning texture transformer network for image super-resolution.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5791–5800, 2020.
  * [50] Sen Yang, Zhibin Quan, Mu Nie, and Wankou Yang.  Transpose: Towards explainable human pose estimation by transformer.  arXiv preprint arXiv:2012.14214, 2020.
  * [51] Fisher Yu and Vladlen Koltun.  Multi-scale context aggregation by dilated convolutions.  arXiv preprint arXiv:1511.07122, 2015.
  * [52] Li Yuan, Yunpeng Chen, Tao Wang, Weihao Yu, Yujun Shi, Francis EH Tay, Jiashi Feng, and Shuicheng Yan.  Tokens-to-token vit: Training vision transformers from scratch on imagenet.  arXiv preprint arXiv:2101.11986, 2021.
  * [53] Kai Zhang, Wangmeng Zuo, Yunjin Chen, Deyu Meng, and Lei Zhang.  Beyond a Gaussian denoiser: residual learning of deep CNN for image denoising.  IEEE TIP, 26(7):3142–3155, 2017.
  * [54] Hengshuang Zhao, Li Jiang, Jiaya Jia, Philip Torr, and Vladlen Koltun.  Point transformer.  arXiv preprint arXiv:2012.09164, 2020.
  * [55] Ce Zheng, Sijie Zhu, Matias Mendieta, Taojiannan Yang, Chen Chen, and Zhengming Ding.  3d human pose estimation with spatial and temporal transformers.  arXiv preprint arXiv:2103.10455, 2021.
  * [56] Xizhou Zhu, Weijie Su, Lewei Lu, Bin Li, Xiaogang Wang, and Jifeng Dai.  Deformable detr: Deformable transformers for end-to-end object detection.  arXiv preprint arXiv:2010.04159, 2020.