Analogous to Evolutionary Algorithm: Designing a Unified Sequence Model
Authors: Jiangning Zhang
Chao Xu
Jian Li
Wenzhou Chen
Yabiao Wang
Ying Tai
Shuo Chen
Chengjie Wang
Feiyue Huang
Yong Liu
Venue: NeurIPS 2021 Poster (2021)
Keywords: Evolutionary Algorithm
Vision Transformer
Spatial-Filling Curve
ImageNet Classification

Abstract: Inspired by biological evolution, we explain the rationality of Vision Transformer by analogy with the proven practical Evolutionary Algorithm (EA) and derive that both of them have consistent mathematical representation. Analogous to the dynamic local population in EA, we improve the existing transformer structure and propose a more efficient EAT model, and design task-related heads to deal with different tasks more flexibly. Moreover, we introduce the spatial-filling curve into the current vision transformer to sequence image data into a uniform sequential format. Thus we can design a unified EAT framework to address multi-modal tasks, separating the network architecture from the data format adaptation. Our approach achieves state-of-the-art results on the ImageNet classification task compared with recent vision transformer works while having smaller parameters and greater throughput. We further conduct multi-modal tasks to demonstrate the superiority of the unified EAT, \eg, Text-Based Image Retrieval, and our approach improves the rank-1 by +3.7 points over the baseline on the CSS dataset.

Analogous to Evolutionary Algorithm: Designing a Unified Sequence Model
Jiangning Zhang
Chao Xu Jian Li Wenzhou Chen
Yabiao Wang Yong Liu
Ying Tai
Shuo Chen Chengjie Wang
Feiyue Huang?
1 APRIL Lab, Zhejiang University YYoutu Lab, Tencent
RRIKEN Center for Advanced Intelligence Project
(186368, 21832066, wenzhouchen)@z.)) edu. en, yongliu@iipe zju edu. (swordli, caseywang, yingtai, jasonejuare feiyuechang)@tten Stenheennnneeeennntttee eteceett com shuo chen, ya@riken.jp
Abstract
Inspired by biological evolution, explain the rationality of Vision Transformer by analogy with the proven practical Evolutionary Algorithm (EA) and derive that both of them have consistent mathematical representation. Analogous the dynamic local population in EA, we improve the existing transformer structure and propose a more efficient EAT model, and design task-related heads deal with different tasks more flexibly. Moreover, we introduce the spatial-filling curve into the current vision transformer sequence image data into uniform sequential format. Thus we can design unified EAT framework to address multi- modal tasks, separating the network architecture from the data format adaptation. Our approach achieves state-of-the-an results on the ImageNet classification task compared with recent vision transformer works while having smaller parameters and greater throughput. We further conduct multi-modal tasks to demonstrate the superiority the unified EAT, e,g., Text-Based Image Retrieval, and our approach improves the rank-1 by +3.7 points over the baseline the CSS dataset
1
Introduction
Since Vaswani el al. (69 introduce the Transformer that achieves outstanding success in the machine translation task, many improvements have been made to this method [5 38 21). Recent works [64]
82 43
led by VIT 23 have achieved great success in the field of many vision tasks by replacing CNN with transformer structure. general, these works are experimentally conducted to verify the effectiveness of modules improvements, but they may lack other forms of supporting evidence.
Inspired by biological population evolution, we explain the rationality of Vision Transformer by analogy with the proven effective, stable, and robust Evolutionary Algorithm (EA), which has been widely used in practical applications. Through analogical analysis, we observe that the training procedure of the transformer has similar attributes to the naive EA, as shown in Figure Take the one- tier transformer (abbr., TR) as an example. 1) TR processes sequence of patch embeddings while EA evolutes individuals, both of which have the same vector formats and necessary initialization. 2) The Multi-heas Self-Attention (MSA) among patch embeddings TR compared with that of (sparse) global individual crossover among all individuals in EA, in which local and dynamic population concepts are introduced to increase running speed and optimize results 63 59 3) SreedForwwar
Work done during an intership at Tencent Youtu Lab.
I Conrespnniing author:
Cooee is available at http:///sssh.oooooeeerrooeoeeees
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Individual Initialization
Crossover
Mutation
Selection 5 Fitness
IBF Result
Initielization
Pattch Enhed
MSA
FFN
Loss Baciward
Cls Token
Figure 1: Analogy of EA (top) and Transformer (bottom) pipelines. For simplicity, only layer of the Transformer structure is displayed here.
(a)
Swoep
(b)
Scan
(c) 2-Order
(4) Hilbert
16
28
30
36
52
Figure 2: Different SFC indexing methods, taking 2D images with side length of 8 as example.
Network (FFN) in TR enhances embedding features that is similar to the individual mutation in EA. 4) During training, TR optimizes the network through backpropagation while EA optimizes individuals through selection and fitness calculation. 5) TR chooses the enhanced Classification Token (CIs Token) as the target output, while EA chooses Individual with the Best Fitness (IBF). Meanwhile, we deduce the mathematical characterization of crossover and mutation operators in EA (c.f., Equations 5 and find that they have the same mathematical representation as MSA and FFN in TR (c.f., Equations 1 respectively. Inspired by the characteristics in the crossover step of EA, we propose novel EA based Transformer (EAT) that intuitively designs a local operator in parallel with global MSA operation, in which the local operator can be instantiated MSA, efc. Subsequent experiments demonstrate the effectiveness of this design in that it could reduce parameters and improve the running speed and boost the network performance, which is consistent with the results of EAs in turn. Current TR-based models would initialize different tokens for different tasks, and they participate in every level of calculation that is somewhat incompatible with other tokens for internal operations. Therefore, we design task-related heads docked with transformer backbone complete final information fusion, which is more flexible for different tasks learning and suitable for the transfer learning of downstream tasks.
ID convolution, local
Our designed local operator receives the same data format as the global MSA branch, i.e., se- quence that is conform to NLP. Therefore, the generally used high dimension operations such as 2D reshape 779 77 80] are not required, which brings the possibility to standardize multi-modal data (e.g., 1D sentence, 2D image, and 3D video) of input into consistent sequence data one unified model. To accomplish this target, introduce the space-filling curve (SFC) concept standardize the multi-modal data format and design an SFC module. As shown in Figure 2 taking 2D image as an example, the top half represents four kinds of SFCs: Sweep, Scan, Z-Order, and Hilbert, while the bottom two lines represent the sequenced image by Z-Order SFC. Thus the image (E [xx8833 is specifically re-indexed and arranged (E 364 by the predefined SFC before feeding the network, realizing uniform sequence input. The difference between SFCs mainly reflects how the ID sequence preserves the 2D spatial structure, and the SFC can be extended 3D and higher dimensions.
Specifically, we make the following four contributions:
In theory, we explain the rationality of Vision Transformer (TR) by analogy with Evolution- ary Algorithm (EA) and derive that they have consistent mathematical representation.
For the method, we improve a unified EAT model by analogy with dynamic local population concept in EA and design Task-related Head to deal with various tasks more flexibly.

---

On framework, we introduce Space-Filling Curve (SFC) module as a bridge between rasterized 2D image data and serialized 1D sequence data. This makes it possible to integrate the unified paradigm that uses unified model to solve multi-modal tasks, keeping the network architecture and data structure independent of the data dimensionality. Note that only several 1D operators are required for our method, meaning that it is very friendly to the underlying optimization workload of different platforms.
Massive experiments on classification and multi-modal tasks demonstrate the superiority and flexibility of our approach.
2 Related Work
2.1 Evolution Algorithms
Evolution algorithm subset of evolutionary computation in computational intelligence, and it belongs to modern heuristics [60 70] Inspired by biological evolution, general EA contains reproduction, crossover, mutation, and selection steps, and has been proven to be effective and stable in many application scenarios [29]. Moscato et al. [47] propose the Memetic Algorithm (MA) for the first time in 1989, which applies a local search process to refine solutions. Later Differential Evolution (DE) appears in 1995 [62] is arguably one of the most competitive improved variant 08
49 52 24]
The core of DE is a differential mutation operator. which differentiates and scales two individuals in the same population and interacts with the third individual to generate new individual. In contrast to the aforementioned global optimization, Local Search Procedures (LSPs) aim to find a solution that is good or better than all other solutions in its "ncighborhood" [44] [4] 9 41 (28). LSP is more efficient than global search in that a solution can be verified as a local optimum quickly without associating the global search space. Also, some works [4 14] 41) apply the Multi-Population Evolutionary Algorithm (MPEA) to solve the constrained function optimization problems relatively efficiently. Recently, Li et al. [4I] point out that the ecological and evolutionary history of each population is unique, and the capacity of Xylella fastidiosa varies among subspecies and potentially among populations. Therefore, we argue that the local population as a complement to the global population can speed up the EA convergence and obtain better results. In this paper, we explain and improve the naive transformer structure by analogy with the validated evolutionary algorithms, where parallel local path is designed inspired by the local population concept in EA.
2.2
Vision Transformers
Since Transformer structure is proposed for the machine translation task (69, many improved language models [1
21
53
54 7 follow it and achieve great results. Some later works [32
74
3 improve the basic transformer structure for better efficiency. Inspired by the high performance of transformer in NLP and benefitted from abundant computation, recent ViT [23)
13 38
introduces the transformer to vision classification for the first time and sparks a new wave of excitement for many vision tasks, e.g., detection g 85). segmentation [8] I1 66), generative adversarial network [36] 72), low-level tasks [00. video processing 4 general backbone (76] 75 43 self-supervision 12
13
neural architecture search 77
40 etc. Many researchers have 80
focused on improving the basic transformer structure [64] 82
777
26
65
79
19
16
68
61 17 42)
which is more challenging than other application- orienntd works. Among these methods, DeiT 644 undoubtedly a star job that makes the transformer performance better and training more data-efficient. Based on DeiT, this work focuses on improving the hasic structure of the vision transformer, making perform better considering both accuracy and efficiency. Besides, our approach supports multi-modal tasks using only one unified model while other transformer- bbaseed methods such as DeiT do not.
2.3 Space Filling Curve
space-filling curve maps the multi-dimensional space into the ID space, and we mainly deal with 2D SFCs in this paper. SFC acts as a thread that passes through all the points in the space while visiting each point only once, i.e,, every point except the starting and ending points is connected to two adjacent line segments. There are numerous kinds of SFCs, and the difference among them is in their ways of mapping to the 1D space. Peano [50] first introduces a mapping from the unit interval to the unit square in 1890. Hilbert (33] generalizes the idea to mapping of the whole space. G.M.Morton [66] proposes Z-order for file sequencing of a static two-dimensional geographical database. Subsequently, many SFCs are proposed [45] 67 56), egg., Sweep, Scan, Sierpinski, Lebesgue, Schoenberg, etc. Some researchers further apply SFC methods to practical applications [5 83 6), such data mining and bandwidth reduction, but so far, almost none has been
3

---

applied to computer vision. By introducing SFC in our EAT, this paper aims to provide systematic and scalable paradigm that uses unified model to deal with mulli-modal data, keeping the network architecture and data structure independent of the data dimensionality.
Preliminary Transformer
The Transformer structure in vision tasks usually refers to the encoder and mainly builds upon the MSA layer, along with FFN, Layer Normalization (LN), and Residual Connection (RC) operations.
MSA equivalent the fusion of several SA operations that jointly attend to information from different representation subspaces, formulated as:
MultiHead (Q, K, V) Concat Head, 1, Head 2,...., Head h)) W
here Head Attention (QW?, KW,, .VW))
(1)
QW? (KW*)" ddk
=sotmmax
VWY AVWY,
where W E Rd.. Xd,, W.K E Xd,, W. E Rdm.xd, W E RR, Xdm are parameter matrices; dm is the input dimension, while dę and de are hidden dimensions of each projection subspace; is the head number; A E ( is the attention matrix and I is the sequence length.
FFN consists of two cascaded linear transformations with ReLU activation in between:
(FN max (0, + b2) W2 b2, where W1 and 22 are weights of two linear layers, while b, and b2 are corresponding biases. LN is applied before each layer of MSA and FFN, and the transformed å is calculated by:
f = + MSA FFN (LN(x)).
4 EA-based Transformer
In this section, firstly expand the association between operators in EA and modules in Transformer, and derive a unified mathematical representation for each set of corresponding pairs, expecting an evolutionary explanation for why Transformer architecture works. Then we introduce the SFC module to sequence 2D image that conforms to standard NLP format. Thus we may only focus on designing one unified model solve multi-modal data. Finally, an EA-based Transformer only containing ID operators is proposed for vision tasks, and we argue that this property is more suitable for hardware optimization in different scenarios.
4.1 EA Interpretation of Transformer Structure
Analogous to EA, the transformer structure has conceptually similar sub-modules, as shown in Fig- ure 3. For both of methods, we define the individual (patch embedding) as æ; [ T1,2;- ... Fi.d). where d indicates sequence depth. Denoting / as the sequence length, the population (patch embed- dings) can be defined as
[1,, x2. ... xz1²".
Crossover Operator vs. SA Module. In EA, the crossover operator aims at creating new individuals by combining parts of other individuals. In detail, for an individual 21 [x1,1 T1,2. .......... ... Ti,a), the operator will randomly pick another individual population, and then randomly replaces features x1 with x; form the new individual t1:
[Tr,1, #4,2.... ........ Fr.al (1 < i in the global
Fijj æi,j
if randb(j) < CR s.l. j 1, 1,,,...,d
(4)
otherwise
where randb(j) is the j-th evaluation of uniform random number generator with outcome [0, 1]. CR is the crossover constant E [0, 1] that is determined by the user. We re-formulate this process as:
i w 2 w: E;
wh æ + 0 D2
w. E; + 1...-00 0 mi
(5)
W X1 + OX2
W X; 0Xi,
where un and w, are vectors filled with zeros or ones, representing the selection of different features of æi and v, Wer and Wir are corresponding diagonal matrix representations.

---

Tank dind
XN
Selection
Fitness
Mutation
Gicbal Path
Local Path
Cureet spiit
Seg
SBC
Palrt-ibie
Figure 3: Structure of the proposed EAT. The right part illustrates the detailed procedure inspired by the left evolutionary algorithm. The blue and green lines in EA represent information interactions among individuals local paths in our EAT. P1, Pa represent biological evolution inside each local population. The proposed SFC module maps the 2D image into ID sequence so that only ID operators are required.
global and local populations, which feeds back the design for global and
For the SA module transformer (MSA degenerates to SA when there only one head), each patch embedding interacts with all embeddings. Without loss of generality, æ [21,1, 21,2, 21,4 interacts with the whole population, i.e., X, as follows:
i = A + A2V2 + AM
= AW X; +AW + A,
where A₁(i 1.2.... .I) are attention weights of all patch embedding tokens that are calculated from queries and keys, W is the parameter metric for the value projection. By comparing Equations 5 [6 we find that they share the same formula representation, and the crossover operation is sparse global interaction while SA has more complex computing and modeling capabilities.
Mutation Operator FFN Module. In EA, the mutation operator injects randomness into the population by stochastically changing specific features of individuals. For an individual æ; [ ... xi,a] (1 < in the global population, goes through the mutation operation form the new individual i;,, formulated as follows:
rand(off (o// ) if randb(j) & MU Ti.j
8.1. =,,.
otherwise
where the MU is the mutation constant E [0, 1] that the user determines, v/ and v. are lower and upper scale bounds of the j-th feature. Similarly, re-formulate this process
+, w; x; [u,,1 21.27 W.,
(
W/m X,.
where w, is randomly generated vector that represents weights on different characteristic depths, while Wmma the corresponding diagonal matrix representation.
For the FFN module in transformer, each patch embedding carries on directional feature trans- formation through cascaded linear layers (c.f., Equation 2). Take one-layer linear example:
c WFFN X.,
where WFFN is the weight of the first linear layer the FFN module, and it is applied to each position separately and identically. By comparing Equations g and 9 also find that they have the

---

same formula representation. FFN module is more expressive because it contains cascaded linear layers and non-linear ReLU activation layers in between, as depicted in Equation 2
Population Succession vs. Residual Connection. In the evolution of the biological population, individuals at the previous stage have certain probability of inheriting to the next stage. This phenomenon is expressed in the transformer in the form of residual connection, i.e., patch embeddings of the previous layer are directly mapped to the next layer.
Best Individual vs. Task- Related Token. EAT chooses the enhanced task-related token (e.g., classification token) associated with all patch embeddings as the target output, while EA chooses the individual with the best fitness score among the population as the object.
Necessity of Modules in Transformer. As described in the work 33), the absence of the Crossover operator or Mutation operator will significantly damage the model's performance. Similarly, Dong er al. (22) explore the effect of MLP in Transformer and find that MIP stops the output from degenera- tion. Furthermore, removing MSA in Transformer would also greatly damage the effectiveness of the model. Thus we can conclude that global information interaction and individual evolution are necessary for Transformer, just like the global Crossover and individual Mutation in EA.
4.2 Detailed Architecture of EAT
63 59 that introduce local and dynamic population concept to the evolutionary algorithm, we analogically introduce a local operator into the naive transformer structure in parallel with global MSA operation. As shown in Figure [ the input features are divided into global features (marked blue) and local features (marked green) at the channel level with ratio p. which are then fed into global and local paths to conduct feature interaction, respectively. The outputs of the two paths recover the original data dimension by concatenation operation. Thus plug-and-play module for the current
Local Path. Inspired by works 44 14
the improved module is very flexible and can be viewed transformer structure. This structure also implicitly introduces the design of multi-modal fusion, analogous to grouping convolution with the group equaling two. Specifically, the local operator can be ID convolution, local MSA, 1D DCN [84), etc. In this paper, we adopt ID convolution as the local operator that is more efficient and parameter friendly, and the improved transformer structure owns constant number of sequentially executed operations and (1) maximum path length between any two positions, c.f Appendix A Therefore, the proposed structure maintains the same parallelism and efficiency as the original vision transformer structure. And p is set to 0.5 for containing the minimal network parameters and FLOPs, proved by Proposition I and Proposition 2 in Appendix [B]
Proposition 1. The numbers of global and local branches in the i - th mixed attention layer (M A') di and d2. For the th input sequence F E iRlxd, the parameter of AA is minimum when dj = =d2 = d/2, where I and d are sequence length and dimension, respectively.
Proposition 2. The numbers of global and local branches the i- th mixed attention layer (M A+) is d1 and dz. For the i 3- th input sequence F E Rlxxd the FLOPs of M is minimum when di = d/2 + 1/8, d2 = d/2 - 1/8, where and are sequence length and dimension, respectively.
RelstRelated Head. Furthermore, we remove the Cls token that has been used since ViT 23 and propose a new paradigm to vision transformer that uses the task-related Head to obtain the corresponding task output through the final features. In this way, the transformer-baut based backbone can be separated from specific tasks. Each transformer layer does not need to interact with the Cls token, so the computation amount reduces ) to Onn²). Specifically, we use cross-attention
Head
MLPP
Nore
slightly from O((n + 1)?) to implement this head module. As shown in Figure 4 K and V are output features extracted by the transformer backbone, while Q is the task-related token that integrates information through cross-attention. AM indicates that each Head contains M layers and is set to 2 in the paper. This design is flexible, with a negligible computation amount compared to the backbone.
Figure 4: Structure of the proposed task- related Head.
Convergence Analysis. The convergence of Adam has been well studied in previous work [55]. can be verified that global path and local path are both Lipschitz-smooth and gradient-bounddd. as long as the transformer embedding is Lipschitz-smooth and seddient-bounded In this case, the iteration sequence of the training algorithm converges to a stationary point of the learning objective with convergence rate (LL/sgrt(2 where T is the number of iterations.

---

4.3 Space-Filling Curve Module
In this subsection, we mainly deal with two-dimensional SFCs. The mathematical definition of SFC is a surjective function that continuously maps a closed unit interval:
w { 0 f s 1 [0. 1]. where &
(10)
as the domain of the function and is mapped onto the unit square:
{ v)
S x L 0 0 y S 1}, where (x, y) E Ω
(11)
which is our range of the function. One can easily define a surjective mapping from onto 22, but it is not injective [67], i.e., not bijective. Nevertheless, for finite ID sequence that maps 2D pixels, it contains bijective property.
Remark 1. According to the definition SFC, it must be surjective. For finite ID to 2D mapping, there is bound to be an intersection if the SFC is not injective, where there are at least two ID points mapping one same 2D point, i.e., 21 = SFC(s, y) and 22 SFC(r, y). This is in contradiction to the finite SFC filling definition. Therefore, a finite SFC is bijective, and we can carry out two-way data lossless transformation through the pre-defined SFC.
We propose an SFC module to map 2D images to the uniform 1D se- quential format based on the above content. Therefore, we can address sequence inputs to handle multi-modal tasks in one unified model, e.g. TIR and VLN. Taking image sequence an example, As shown in the right bottom of Figure 3. the input image I E R R Wx3 x3 goes through the SFC module to be Seg E IR HW x3, formulated as:
13
10:
21
24 25
26
27
28
8
28
31
32 23
34 35
36
37
28
29
Seg Ieg, where = SFC(x, k
(12)
48
41
42
45
45
46
48
49
50
5x
53
54
where 1 iSiS H. W. 1 < k HW, and SFC can be any mamually specified space-fillingg curve. The difference among SFCs mainly reflects how the 1D) sequence preserves the 2D spatial structure. As an extension, SFC can be defined to three or higher dimensional data space and can also serialize the intermediate network features, e-g., the output feature maps of stage 3 in ResNet [3I. In this paper, we use Embedded Slices instead of Embedded Patches as the input of backbone that is consistent with NLP input format. As shown in Figure we further propose new SFC named SweepInSweep (SIS) that methods, e.g., ViT and DeiT, where
58
58
86
68
81
62
Figure 5: Indexing illus- tration of the proposed SweepInSweep SFC.
equivalent the input mode of the existing transformer-basee the slice size equaling 16 is equivalent to that patch size equaling 4. The paper uses this mode for SFC by default. More visualizations of different SFCs are presented in Appendix C
5
Experiments
5.1 Implementation Details.
We choose SOTA DeiT 644 as the baseline and follow the same experimental setting. By default, we train each model for 300 epoch from scratch without pre- pre-training and distillation. The classification task evaluated in ImageNet- 1k dataset (20). and we conduct all experiments on a single node with
8 V100 GPUs TIR is conducted on Fashion200k (27), MIT-States [34], and CSS [71] datasets, while VIN is performed on the R2R navigation dataset [1. Detailed EAT variants can be viewed in Appendix D and we supply the train and test codes in the supplementary material.
5.2 Comparison with SOTA Methods
The classification task is conducted on the ImageNet- 1k dataset without external data. As noted in Table [ we list four kinds of EAT of different magnitudes with backbone + head format, i.e.. Tiny, Small, Middle, and Base. They have comparable parameters with SOTA DeiT, but a higher accuracy, a lower inference memory occupancy, and more throughput in both GPU (tested with batch size equaling 256 in single V V100) and CPU (tested with batch size equaling 16 in i7-8700K @3.70GHz). Our method trained in 224 resolution for 300 epochs without distillation, so our result is slightly lower than large CNN-based EfficientNet in terms of Top- Moreover, we visualize comprehensive Top-1 results of different methods under various evaluation indexes in Figure 6 and present the results of series of EAT models with different model sizes. 1) Left two subgraphs show that our EAT outperforms the strong baseline DeiT, and even obtains better results than EfficientNet in both GPU and CPU throughput, e.g., EAT-M. 2) Besides, our approach is very competitive for
7

---

Table 1: Comparison with SOTA CNN-based and Transformer- based methods on ImageNet- Ik dataset. Reported results are from corresponding papers. a: Distillation; lke: Training 1000 epochs.
Network
Params. (M)
GFlops 4
Images/s f
Image Size
Top-1
Inference
GPU
CPU
Memory
CNN-Basce Nets
ResNet-18
11.7M
1.8
4729
77.9
224
69.8
1728
ResNet-50
25.6M
4.1
1041
21.1
224
76.2
2424
ResNet-101
44.5M
7.8
620
13.2
224
77.4
2574
ResNet-152
60.2M
11.5
431
9.4
224²
78.3
2694
RegNetY-1GF
20.6M
4.0
976
22.1
224
80.0
2828
RegNerY-8GF
39.2M
8.0
532
12.9
224
81.7
3134
RegNetY-16GF
83.6M
15.9
316
8.4
224
82.9
4240
EfficientNNt-BOO
5.3M
0.4
2456
49.4
224
77.1
2158
EfficientNet-B B2
9.1M
1.0
1074
22.6
2602
80.1
2522
EfficientNet-BB B4
19.3M
4.5
313
6.1
380
82.9
5280
EfficientNet-BB
30.4M
10.4
145
3.0
456
83.6
7082
EfficienNNctBB7
66.3M
38.2
48
1.0
6002
84.3
14650
NENet-FO
71.5M
9.6
574
12.5
256
83.6
2967
Transformer Based Nets
VIT-B/16
86.6M
17.6 61.6
291
10.3
384
77.9
2760
VIT-L/16
304M
92
2.7
384
76.5
4618
DeiT-Ti
5.7M
1.3
2437
89.8
224
72.2
1478
DeiT-S
22
4.6
927
31.4
224
79.8
1804
DeiT-B
86.6M
17.6
290
10.2
224
81.8
2760
EAT-Ti
5.7M 4.8M 0.9M)
1.0
2442
95.4
224
72.7
1448
EAT-S
22.1M
(18.5M + 3.6M)
3.8
1001
34.4
224
80.4
1708
EAT-M
49.0M
(41.0M + 8.0M)
8.4
519
18.4
224
82.1
2114
EAT-B
86.6M
(72.4M +14.2M)
14.8
329
11.7
224
82.0
2508
DeiT-Ti DeiT-Ti/ 1ke m
5.9M
1.3
2406
87.1
224
74.5
1476
5.9M
1.3
2406
87.1
224
76.6
1476
EAT-Ti m
5.7M
4.8M + 0.9M)
1.0
2442
95.4
224
74.8
1448
EAT-Ti lke a
5.7M 4.8M + 0.9M)
1.0
2442
95.4
224
77.0
1448
resource-restrained scenarios, e.g., having a lower inference memory occupancy and parameters while obtaining considerable accuracy. 3) Also, we find accuracy saturation in transformer structure that is also mentioned in recent works [65 [2), and we look forward to follow-up works to solve this problem. Furthermore, some techniques to help improve the accuracy of the model are applied, and our EAT model obtains a better accuracy.
ESTH
84
1000 134
VE&
82
EAT-S
2x4 Params
DeTT5
R152
4x1 Params & 2x1 Memory
62
Trgoio KCM
Top@1
80
R101
VIT-B
76
EAT-TT
DaiTsS
Deit-Ti
EfficientNet
VIT
70
R18
DeIT
EAT
C2
10
30
40
60
80
90
Params((M)
Figure 6: Comparison of different methods under different evaluation indexes. From left to right are GPU throughput, CPU throughput, and model parameters. The smaller the circle in the right sub-figure, the smaller the inference memory occupancy. Please zoom for a better visual effect.

---

Table 2: Retrieval performance three datasets rank-1. The vision and language models replaced by other nets, marked in the lower right footnote as and L. ": Our reproduction; -: No corresponding sult. The best number in bold.
Table 3: VLN experiment the R2R dataset. ": Our reproduction with suggested parameters by authors. NE: Navigation Er- ror; SPL: Success weighted by (normalized inverse) Path Length; nDTW: normalized Dynamic Time Warping.
Method
MIT-States
Fashion200k
Method
NE
SPL
TIRG /11
12.2
14.1
PTA
TIRG'
70.1
13.1
14.0
EAT
3,84
0.62
0.72
EATV
3.95
0.6
0.71
70.7
14.3
EATV
3.95
0.61
0.71
EATZ
71.0
13.4
14.9
PTA"
6.61
0.28
0.48
R1Oly
73.0
14.3
19.0
EAT
6.41
0.33
0.51
EATY
73.5
14.9
19.9
EATT
6.63
0.29
0.49
EATV
73.8
15.0
20.1
EATVIZ
6.43
0.32
0.51
Table Ablation study for several items on ImageNet- Default represents the baseline method based on EAT-B. The gray font indicates that the corresponding parameter is not be modified.
Ablation
Head Layers
Local
FFN Ratio
Top-1
Ahlation liems
Kernel
Local
SFC
Image
Top-1
Size
Operator
Mode
Size
Default
3
ID Conv
SIS
80.264
0.50
79.692
1
ID Conv
SIS
224"
79.128
Kernel
Head
0.50
80.422
Size
5
ID Conv
SIS
224"
80.256
Layer
0.50
80.435
7
ID Conv
SIS
224
80.052
4
0.50
80.454
Local
3
Local MSA
SIS
221"
79,940
5
0.50
80.446
Operator
3
DCN
SIS
224
68.070
Local
0.25
80,280
3
ID Conv
Sweep
256*
71,280
Ratio
0.75
79.518
SFC
3
ID Conv
Scan
256
74.164
FFN
0.50
77.422
Mode
3
ID Conv
Hilbert
256
79.842
Ratio
0.50
79.176
3
ID Conv
Z-Order SIS
256
80.438
5.3 Multi-Modal Experiments
Text-based Image Retrieval. TIR is the task of searching for semantically matched images large image gallery according to the given search query, i.e., an image and text string. Table 2 illustrates the quantitative results. Naive transformer and EAT, z. have the same number of layers, and EATy has similar parameters as Ri0ly. The results show that EAT brings positive benefits by replacing either original sub-network, even though vision and language models share one structure. Vision Language Navigation. We further assess our approach by VLN experiments, where an agent needs to follow a Language-specfffie path to reach target destination with the step-by-step visual observation. We choose the PTA [39 the base method, and Table 3 shows results under the same experimental setting. Our unified EAT obtains comparable results with PTA the seen mode but achieves greater improvement in the unseen mode, meaning better robustness. When only replacing the vision EAT, the result changes very little. We analyze the reason that the used visual feature dimension of EAT-B is smaller than the original ResNet-152 (from 2048 384), and reinforcement learning is sensitive to this. Overall, our unified EAT still contributes to the PTA method.
5.4 Ablation Study
shows ablation results for several items on ImageNet- 1k. 1) Head Layer. Within a certain range, the model performance increases with the increase the head layer, and equals 2 in the paper for trading off model effectiveness and parameters. 2) Local Ratio. Large local ratio causes performance falling and increases the parameters (c.f., f. Section 4.2)). so equaling 0.5 is a better choice. 3) FFN Ratio. Similar to the conclusion of work [69] lower FFN ratio results in drop in accuracy. 4) Kernel Size. Large kernel can lead to accuracy saturation, so we set it to 3 in the paper. 5) Local Operator. We replace the local operator with local MSA and ID DCN. The former slightly reduces the accuracy (a structure similar to the global path may result in learning redundancy), while latter greatly reduces the accuracy (possibly papee-earsmeters are not adapted). 6) SFC Mode. Since some SFCs, e.g., Hilbert and 7-Order, only deal with images with the power of side lengths, we set the image size to 256 here. Results show that the images serialized by Z-Order or SIS get better results because they can better preserve 2D spatial information that is important for ID-convolution.
Table 4

---

5.5 Model Interpretation by Attention Visualization
Input
GradCAN
We average attention maps of each head layer and visualize them to illustrate which parts of the image the model is focusing on. As shown in Figure / Headl pays more attention subjects that are meaningful to the classification results, while the deeper Head2 integrates features of Headl to form the final vector for classification that focuses on more comprehensive areas. Also, Grad-CAM [58] applied to highlight concerning regions by our model and results consistently demonstrate the effectiveness of our proposed Head module. Note that the Cls Head contains two head layers, denoted as Headl and Head2 in the figure. We also visualize attention maps of middle layers in Appendix [F] and find that the global path prefers to model long-diin distance over DeiT.
Figure 7: Visualization of atten- tion maps for head layers and Grad-CAM results.
6 Conclusions
This paper explains the rationality of vision transformer by analogy with EA, which brings inspiration for the neural architecture design. Besides, the introduced SFC module serializes the data into a sequential format, and we achieve the paradigm of using one unified model to address multi-modal tasks. Abundant experimental results demonstrate the effectiveness and flexibility of our approach. We hope this work may bring some enlightenment to network interpretabilityy and thinking design the unified model for multi-modal tasks. Recently, we observe that EA has been successfully used in other areas, e.g., RL (PES (57] ERL (37)), NAS (SPOS (25), CARS (78), Hyperparameter Adjustment (PBT (35)), etc. Nevertheless, how combine heuristic algorithms such as EA with other fields is still a difficult problem, and we will further explore potential possibilities in the future.
Acknowledgment We thank all authors for their excellent contributions as well as anonymous reviewers and chairs for their constructive comments. This work is partially supported by the National Natural Science Foundation of China (NSFC) under Grant No. 61836015.
References
[1] Peter Anderson, Qi Wu, Damien Teney, Jake Bruce, Mark Johnson, Niko Sünderhauf, Ian Reid, Stephen Gould, and Anton Van Den Hengel. Vision-and-languagg navigation: Interpreting visually-grounded navigation instructions in real environments. In Proceedingy of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3674-3683, 2018.
[2] Sara Atito, Muhammad Awais, and Josef Kittler. Sit: Self-supervised vision transformer. arXiv preprint
2021.
[3] Irwan Bello. Lambdanetworks: Modeling long-range interactions without attention. In Interna- tional Conference on Learning Representations, 2021.
[4] Gedas Bertasius, Heng Wang. and Lorenzo Torresani. Is space-time attention all you need for video understanding? arXiv preprint arXiv:2102.05095, 2021.
[5] T. Bially. Space-fillingg curves: Their generation and their application to bandwidth reduction. IEEE Transactions on Information Theory, 15(6):658 6644 1969.
[6] Christian Böhm. Space-filling curves for high-performance data mining. arXiv preprint 20Xi::2008.01684 2020.
[7] Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot leamners. arXiv preprint arXiv:2005. 14165, 2020.
[8] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. End-to-end object detection with transformers. European Conference on Computer Vision, pages 213-229. Springer, 2020.
10

---

[9] Andreina I Castillo, Carlos SiacónnDiizz Neysa Rodríguez-Muriln Helvecio D Coletta-Filla and Rodrigo PP Almeida. Impacts of local population history and ecology on the evolution of globally dispersed pathogen. BMC genomics, 21:1-20, 2020.
[10] 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.00:64 2020.
[11] Jieneng Chen, Yongyi Lu, Qihang Yu, Xiangde Luo, Ehsan Adeli, Yan Wang, Le Lu, Alan L Yuille, and Yuyin Zhou. Transunet: Transformers make strong encoders for medical image segmentation. arXiv preprint 1xXiv:2102.043006 2021.
[12] Mark Chen, Alec Radford, Rewon Child, Jeffrey Wu, Heewoo Jun, David Luan, and Ilya Sutskever. Generative pretraining from pixels. In International Conference on Machine Learning, pages 1691-1703. PMLR, 2020.
[13] Xinlei Chen, Saining Xie, and Kaiming He. An empirical study of training self-supervised visual transformers. arXiv preprint 2.Xiv:2104002053 2021.
[14] Ziyi Chen and Lishan Kang. Multi-populatie evolutionary algorithm for solving constrained optimization problems. In IFIP International Conference on Artificial Intelligence Applications and Innovations, pages 381-395, Springer, 2005.
[15] Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Benjamin Belanger, Lucy Colwell, and Adrian Weller. Rethinking attention with performers. In International Conference on Learning Representations, 2021.
[16] Xiangxiang Chu, Zhi Tian, Bo Zhang. Xinlong Wang, Xiaolin Wei, Huaxia Xia, and Chunhua Shen. Conditional positional encodings for vision transformers. Arxiv preprint 10822, 2021.
[17] Zihang Dai, Hanxiao Liu, Quoc V Le, and Mingxing Tan. Coatnet: Marrying convolution and attention for all data sizes. arXiv preprint arXiv:2106. 04803, 2021.
[18] Swagatam Das and Ponnuthurai Nagaratnam Suganthan. Differential evolution: A survey of the state-of-the-art. IEEE transactions on evolutionary computation, 15(1):4-31, 2010
[19] Stéphane d' Ascoli, Hugo Touvron, Matthew Leavitt, Ari Morcos, Giulio Biroli, and Levent Sagun. Convit: Improving vision transformers with soft convolutional inductive biases. arXiv preprint arXiv:2/03. 10697, 2021.
[20] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. 2009 IEEE conference on computer vision and puttern recognition, pages 248-255 leee, 2009.
[21] Jacob Devlin, Ming- Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805, 2018.
[22] Yihe Dong, Jean-Baptist Cordonnier, and Andreas Loukas. Attention is not all you need: Pure attention loses rank doubly exponentially with depth. arXiv preprint arXiv:2103.0344 2021.
[23] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021.
[24] Manolis Georgioudakis and Vagelis Plevris. A comparative study of differential evolution variants in constrained structural optimization. Frontiers in Built Environment, 6:102, 2020.
[25] 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.

---

[26] Kai Han, An Xiao, Enhua Wu. Jianyuan Guo, Chunjing Xu, and Yunhe Wang. Transformer in transformer. arXiv preprint arXiv:2103.00122 2021.
[27] Xintong Han, Zuxuan Wu, Phoenix X Huang, Xiao Zhang, Menglong Zhu, Yuan Li, Yang Zhao, and Larry S Davis. Automatic spatially-aware fashion concept discovery. In Proceedings of the IEEE Interaational Conference on Computer Vision, pages 1973-141, 2017.
[28] Phan Thi Hong Hanh, Pham Dinh Thanh, and Huynh Thi Thanh Binh. Evolutionary algorithm and multifactorial evolutionary algorithm on clustered shortest-path tree problem. Information Sciences, 553:280-304, 2021.
[29]
William Eugene Hart, Natalio Krasnogor, and James E Smith. Memetic evolutionary algorithms. In Recent advances memetic algorithms,, pages 3-27. Springer, 2005.
[30] Ahmad Hassanat, Khalid Almohammadi, Esra' Alkafaween, Eman Abunawas, Awni Hammouri, and VB Prasath. Choosing mutation and crossover ratios for genetic algorithms a review with a new dynamic approach. Information, 10(12):390, 2019.
[31] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[32] Ruining He, Anirudh Ravula, Bhargav Kanagal, and Joshua Ainslie. Realformer: Transformer likes residual attention. arXiv e-prints, pages arXiv-2012, 2020.
[33] David Hilbert. Über die stetige abbildung einer linie auf ein flächenstück. Dritter Band: Analysis- Grundlagen der Mathematik Physik Verschiedenes, pages 1-2. Springer, 1935.
[34] Phillip Isola, Joseph Lim, and Edward H Adelson. Discovering states and transformations in image collections. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages
2015.
[35] Max Jaderberg. Valentin Dalibard, Simon Osindero, Wojeiech M Czamecki, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, lain Dunning, Karen Simonyan, et al. Population based training of neural networks. arXiv preprint 1.X10:171..09866, 2017.
[36] Yifan Jiang, Shiyu Chang, and Zhangyang Wang. Transgan: Two transformers can make one strong gan. arXiv preprint arXiv:2102.07074 2021.
[37] Shauharda Khadka and Kagan Tumer. Evolution-guidd guided policy gradient in reinforcement learning. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 1196-12000 2018.
[38] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In International Conference on Learning Representations, 2020.
[39] Federico Landi, Lorenzo Baraldi, Marcella Cornia, Massimiliano Corsini, and Rita Cucchiara. Perceive, transform, and act: Multi-modal attention networks for vision-and-land and-lanuuage naviga- tion. arXiv preprint arXiv: 12377, 2019.
[40] 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 urXiv:2103.12443 2021.
[41] Xiaoyu Li, Lei Wang, Qiaoyong Jiang, and Ning Li. Differential evolution algorithm with multi-poppuation cooperation and multi-strategy integration. Neurocomputing, 421:285-302, 2021.
[42] Yawei Li, Kai Zhang, Jiezhang Cao, Radu Timofte, and Luc Van Gool. Localvit: Bringing locality to vision transformers. arXiv preprint arXiv:2104.0577 2021.
[43] 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. 2021.
12

---

[44] David E McCauley. Genetic consequences of local population extinction and recolonization. Trends in Ecology Evolution, 6(1):5-8, 1991.
[45] Mohamed F Mokbel, Walid G Aref, and Ibrahim Kamel. Analysis of multi-dimensional space-filling curves. Geohnformatica, 7(3):179-209, 2003.
[46] Guy M Morton, A computer oriented geodetic data base and new technique in file sequencing. empry, 1966.
[47] Pablo Moscato et On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Caltech concurrent computation program, C3P Repori, 826: 1989, 1989.
[48] Kodai Nakashima, Hirokatsu Kataoka, Asato Matsumoto, Kenji Iwata, and Nakamasa Inoue. Can vision transformers learn without natural images? arXiv preprint arXiv:2103. 13023, 2021.
[49] Nikhil Padhye, Pulkit Mittal, and Kalyanmoy Deb. Differential evolution: Performances and analyses. In 2013 IEEE Congress on Evolutionary Computation, pages 1960-1967. IEEE, 2013.
[50] Giuseppe Peano. Sur une courbe, qui remplit toute une aire plane. Mathematische Annalen, 36(1):157-160, 1890.
[51] Matthew Peters, Mark Neumann, Mohit lyyer, Matt Gardner, Christopher Clark, Ken- ton Lee, and Luke Zettlemoyer. Deep contextualized word representations. arXiv preprint arXiv: 2018.
[52] Adam P Piotrowski and Jaroslaw J Napiórkowski. The grouping differennial evolution algorithm for multi-dimensional optimization problems. Control and Cybernetics, 39:527-550, 2010.
[53] Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language understanding by generative pre-training. empty, 2018.
[54] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
[55] S Reddi, Manzil Zaheer, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive meth- ods for nonconvex optimization. In Proceeding of 32nd Conference on Neural Information Processing Systems (NIPS 2018), 2018.
[56] Hans Sagan. Space-filling curves. Springer Science & Business Media, 2012.
[57] Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies as scalable alternative to reinforcement learning. arXiv preprint arXiv: [ttv:/703: /700.033664 2017.
[58] Ramprasaath Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient-based localization. In Proceedings of the IEEE international conference on computer vision, pages 618-626, 2017.
[59] Anabela Simões and Ernesto Costa. The influence of population and memory sizes the evolutionary algorithm's 's performance for dynamic environments. In Workshops on Applications of Evolutionary Computation, pages 705-714. Springer, 2009.
[60] Andrew N Sloss and Steven Gustafson. 2019 evolutionary algorithms review. arXiv preprint arXiv: 196.887906 2019.
[61] Aravind Srinivas, Tsung- Yi Lin, Niki Parmar, Jonathon Shlens, Pieter Abbeel, and Ashish Vaswani. Bottleneck transformers for visual recognition. arXiv preprint arXiv:2001.11605 2021.
[62] Rainer Storn and Kenneth Price. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. Journal of global optimization, 11(4)331-359, 1997.
13

---

[63] Kay Chen Tan, Tong Heng Lee, and Eik Fun Khor. Evolutionary algorithms with dynamic population size and local exploration for multiobjective optimization. IEEE Transactions on Evolutionary Computation, 5(6):565-588 2001.
[64] 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: 12877, 2020.
[65] Hugo Touvron, Matthieu Cord, Alexandre Sablayrolles, Gabriel Synnaeve, and Hervé Jégou. Going deeper with image transformers. arXiv preprint arXiv:2103. 2021.
[66] Jeya Maria Jose Valanarasu, Poojan Oza, Ilker Hacihaliloglu, and Vishal M Patel. Medical trans- former: Gated axial-attention for medical image segmentation. arXiv preprint arXiv:2102.10000 2021.
[67] Levi Valgaerts. Space-filling curves an introduction. Technical University Munich, 2005.
[68] Ashish Vaswani, Prajit Ramachandran, Aravind Srinivas, Niki Parmar, Blake Hechtman, and Jonathon Shlens. Scaling local self-attention for parameter efficient visual backbones. arXiv preprint arXiv:2103. 2021.
[69] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. Attention is all you need. Guyon, U. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[70] Pradnya A Vikhar. Evolutionary algorithms: A critical review and its future prospects. In 2016 International conference global trends in signal processing. information computing and communication (ICGTSPICC), pages 261-265. IEEE, 2016.
[71] Nam Vo, Lu Jiang, Chen Sun, Kevin Murphy, Li-Jia Li, Li Fei-Fei, and James Hays. Composing text and image for image retrieval-an empirical odyssey. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages
2019.
[72] Zhaoyi Wan, Haoran Chen, Jielei Zhang, Wentao Jiang, Cong Yao, and Jiebo Luo. Facial attribute transformers for precise and robust makeup transfer. arXiv preprint XXiv:2104.0289, 2021.
[73] 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. 14/87, 2020.
[74] Sinong Wang, Belinda Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint urXiv:2006.04766. 2020.
[75] 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 1IXX::2202.11122.. 2021.
[76] Bichen Wu, Chenfeng Xu, Xiaoliang Dai, Alvin Wan, Peizhao Zhang, Zhicheng Yan, Masayoshi Tomizuka, Joseph Gonzalez, Kurt Keutzer, and Peter Vajda. Visual transformers: Token-based image representation and processing for computer vision. arXiv preprint arXiv:2006.03677, 2020.
[77] Haiping Wu, Bin Xiao, Noel Codella, Mengchen Liu, Xiyang Dai, Lu Yuan, and Lei Zhang. Cvt: Introducing convolutions to vision transformers. arXiv preprint (rXiv:2103.1500 2021.
[78] Zhaohui Yang, Yunhe Wang, Xinghao Chen, Boxin Shi. Chao Xu, Chunjing Xu, Qi Tian, and Chang Xu. Cars: Continuous evolution for efficient neural architecture search. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1829-1838. 2020.
[79] Kun Yuan, Shaopeng Guo, Ziwei Liu, Aojun Zhou, Fengwei Yu, and Wei Wu. Incorporating convolution designs into visual transformers. arXiv preprint 2:Xiv:2103.11816 2021.
14

---

[80] Li Yuan, Yunpeng Chen, Tao Wang. Weihao Yu, Yujun Shi. Francis EH Tay. Jiashi Feng, and Shuicheng Yan. Tokene-to-token Training vision transformers from scratch on imagenet. arXiv preprini arXiv:2 1986, 2021.
[81] Sixiao Zheng, Jiachen Lu, Hengshuang Zhao, Xiatian Zhu, Zekun Luo, Yabiao Wang, Yanwei Fu, Jianfeng Feng, Tao Xiang. Philip HS Torr, et al. Rethinking semantic segmentation from a sequence-to-sequenee perspective with transformers. arXiv preprint arXiv:2012.15840 2020.
[82] Daquan Zhou, Bingyi Kang, Xiaojie Jin, Linjie Yang, Xiaochen Lian, Qibin Hou, and Jiashi Reng. Deepvit: Towards deeper vision transformer. arXiv preprint 100:21003.11886 2021.
[83] Liang Zhou, Chris R Johnson, and Daniel Weiskopf. Data-driven space-filling curves. IEEE Transactions on Visualization and Computer Graphics, 2020.
[84] Xizhou Zhu, Han Hu, Stephen Lin, and Jifeng Dai. Deformable convnets v2: More deformable, better results. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9308-9316, 2019.
[85] 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.
15


Reviews:
[{"review_id": "qdpmwjytagJ", "reviewer": "Reviewer_EQ9b", "summary": "This paper presents a novel perspective to explains the rationality of vision transformer by analogy with a heuristic evolutionary algorithm and proposes an improved EAT model borrowing the dynamic local population concept from EA. Authors introduce the spatial-filling curve to serialize the input image, so only one unified model is required to handle multi-modal tasks. The extensive classification and multi-modal experiments show that the proposed method is effective and efficient.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strong Points \n- The perspective between Transformer and EA is interesting, and the improved EAT is reasonable and effective. The introduced spatial-filling curve makes it possible to deal with multi-modal tasks by one unified model.\n- The paper is easy to follow, and its organization is sound. The authors provide the training code, and the reported results are convincing.\n- The experiments for classification and multi-modal tasks are extensive, and detailed ablation experiments are carried out.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "- Task-related head looks the same as the cross-attention structure in Transformer Decoder[61], and a similar structure is mentioned in Cait[57], so this contribution is optional.\n- Spatial-filling curve does not seem to improve the performance, and the SIS mode stated in the paper is equivalent to the current token embedding in ViT.\n- EAT increases by 0.5 points on average compared to the baseline in Table 1, but the reported highest Top-1 is 82.4 that is lower than current methods, e.g., SwinTransformer[36] and Cait[57]. Authors should compare with these methods or explain why it is not being compared.\n- Why do authors claim that \"... so that only 1D operators are required\" in Figure 3? Adding 2D operations, such as 2D-convolution in CPVT[16], CeiT[70], and PVTv2[a], has been shown to improve the performance of Transformer in image classification tasks.\n- Grammatical errors and typo issues lower the paper quality that can be seen in the following section.  \n\n[a] Wang W, Xie E, Li X, et al. PVTv2:\n\nMoreover, Here are more suggestions. \n\n- Some quantitative results in Appendix E should be presented in Table 1\n- Why does DCN dramatically damage performance in Table 4?\n- Figure 6 should be rearranged\n- How to integrate CV and NLP features is unclear in multi-modal experiments, and more details should be displayed.\n- Some grammar/typo issues.\n    - L12, L51: multi-modal \n    - L102: their ways\n    - L116: the definition of \"h\"\n    - L161: the weight\n    - L174: concepts\n    - L314: remove the comma after \"format\"\n\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "kF9Z4WdSYDQ", "reviewer": "Reviewer_NvRs", "summary": "The authors first explain the analogy between Transformer and the classic Evolutionary Algorithm (EA). Then, inspired by the dynamic local population in EA, the authors propose the EAT model, which integrates local operations (e.g., convolution, local attention, etc.) in the Transformer model. Besides, the authors design spatial-filling curve and task-related heads to improve the performance and generalization of the EAT model. Experiments on three tasks, including image classification, image retrieval and vision language navigation, demonstrate the effectiveness of the proposed EAT model.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper explains the rationality of Vision Transformer by the analogy between Transformer and the classic Evolutionary Algorithm (EA). Based on this analogy, the authors improve the Transformer model by three modules, including the integration of local operations in the attention layer, spatial-filling curve, and the task-related heads.\n\nFirst, the analogy between Transformer (TR) and Evolutionary Algorithm (EA) is not much convincing. Convolution, attention, and fully-connected layers are just common operations to integrate low-level representations to form high-level semantics. These three operations share the same mathematical representation of X’ = WX. I didn’t see that the analogy between TR and EA could extend the explainability of TR.\n\nSecond, as for the local path and global path in EAT, this design is essentially a way to fuse global and local representations. For a representation, some channels are used for global operations (i.e., MSA), other channels are used for local operations (i.e., CNN or local attention). However, the fusion of global and local information has been discussed in many papers like [1,2,3,4]. And the novelty in this paper is limited.\n\nThird, the ablation studies in Table 4 shows the effectiveness of spatial-filling curve and task-related heads. However, the improvements of EAT over the state-of-the-art methods on ImageNet in Table 1 are not significant (e.g., EAT-B obtains 82.0 while DeiT-B obtains 81.8 under the same number of parameters).\nThe quality of paper writing is good. It is easy for readers to understand the ideas of this paper. All the figures and tables are well illustrated. And the whole paper is well organized.\n\n[1] Wang, Xiaolong, et al. \"Non-local neural networks.\" Proceedings of the IEEE conference on computer vision and pattern recognition. 2018.\n[2] Cao, Yue, et al. \"Gcnet: Non-local networks meet squeeze-excitation networks and beyond.\" Proceedings of the IEEE/CVF International Conference on Computer Vision Workshops. 2019.\n[3] Qiu, Zhaofan, et al. \"Learning spatio-temporal representation with local and global diffusion.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2019.\n[4] Srinivas, Aravind, et al. \"Bottleneck transformers for visual recognition.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2021.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Overall, the contribution of this paper to the research community is not significant enough. The analogy between Transformer (TR) and Evolutionary Algorithm (EA) could not promote the explainability of TR. The integration of local and global representations is not novel in the literature of deep learning. The spatial-filling curve and the task-related heads do not show significant improvements in the experiments on ImageNet.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "II5S9m7djtf", "reviewer": "Reviewer_TDFa", "summary": "In this article, the author\n1. explain the transformer from the EA algorithm perspective\n2. uses the dynamic local population strategy used in EA algorithm and transfer the strategy into the transformer\n3. introduces the spatial filling curve to transform the image data\n4. achieves SOTA results on a number of tasks.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "pros:\n1. This article has a certain degree of innovation\n2. The result of this article is good\n\ncons:\n\nQ1. The writing of this article is not clear\n\nQ1.1 This article contains too much information, the author has too many things to say. But the main contribution is not described clearly. I suggest the author use a few sentences to describe the core contribution of this article and write it in the first part. List by points.\n\nQ1.2 The framework of this method seems complex. It is suggested to insert a diagram on the second page and highlight the core contribution.\n\nQ2. The necessity of introducing EA\n\nQ2.1 What is the meaning of introducing EA algorithm? What are the unique advantages of local population strategy in EA algorithm? Why is it useful to introduce local information because EA is similar to transformer? In my opinion, the introduction of EA algorithm has some over packaging.\n\nQ2.2 Again local? The purpose of introducing transformer into CV task is to deal with the image information directly in a uniform way, without considering the sequence relationship between the image patches, and deal with the problem of CV from a global perspective. This article seems to reuse some features of images, such as local information and sequence to transformer? This sounds like considering some special features of the image and used in the transformer. I don't think it's bad, but I think it might be contrary to the original intention of the transformer.\n\nQ3. Method & Experiments\n\nQ3.1 Please report the FLOPs.\n\nQ3.2 Please add all the Efficientnet models in Fig. 6. It seems that the improvement is incremental.\n\nQ3.3 About local. It actually introduces some priors of CNN's local information into transformer to a certain extent. The idea of local is not new and needs to quote more relevant papers.\n\nQ3.4 About SFC. If the input image is not a regular rectangle, what is the impact? Is the strategy adopted by the author the optimal one for 2D image arrangement?\n\n========== post rebuttal ============\n\nI have read the rebuttal and the rebuttal addresses most of my concerns. I will change my score from 4 to 6.\n\nThe rebuttal should be merged into main paper in the next version.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please see the main review part.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4h"}, "extra_text": {}}, {"review_id": "D4muHcQHT-g", "reviewer": "Reviewer_Ppg5", "summary": "This paper attempts to explain the rationality of Vision Transformer by the proven practical Evolutionary Algorithm and finds that both of them have consistent mathematical representation. Besides, for separating the architecture of transformer-based network from the data format adaptation, the authors introduce the spatial-filling curve into the vision transformer to sequence multiple dimensional data (e.g., image or video) into a uniform sequential format. Thereby the proposed transformer-based network can deal with multi-modal tasks.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "It is interesting that the theory of EA is introduced to explain the rationality of Vision Transformer. The authors give the comparison of the basic operator in EA with the module in transformer. It is concluded that the mathematical representations of Mutation operator with FFN Module, Crossover Operator with SA Module are consistent. Based on those observations, it is better to give readers more insightful explanations on the success of transformer instead of only stating those phenomenon.\n\nSerializing the multiple dimensional data into sequence with a consistent algorithm is indeed an elegant solution to adapt multi-modal data for transformer. Many algorithms like those in Figure 2 can competent this task, and Hilbert algorithm is selected for serializing the input data. So, what is the reason behind for the authors to make this choice. It would be more convincing if those space filling curve algorithms are compared in the experiment section.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper is easy to understand for me, but the writing should be checked carefully, such as “Imeges” in Table 1.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "15.0 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides a view on the Transformer architecture as being related to that of an Evolutionary Algorithm. Based on this, the authors propose some improvements to the architecture and show convincing empirical results to demonstrate their efficacy and efficiency. The reviewers and discussion subsequent to the rebuttal support this view and I trust the authors will incorporate the reviewers' comments into the final manuscript.
Decision: Accept (Poster)