EATFormer: Improving Vision Transformer Inspired by Evolutionary Algorithm

Evolution algorithm (EA) is a subset of evolutionary computation in computational intelligence that belongs to modern heuristics, and it serves as an essential umbrella term to describe population-based optimization and search techniques in the last 50 years ea1 ; ea2 ; bartz2014evolutionary . Inspired by biological evolution, general EAs mainly contain reproduction, crossover, mutation, and selection steps, which have been proven effective and stable in many application scenarios mea1 ; mea2 , and a series of improved EA approaches have been advanced in succession. Differential Evolution (DE) developed in 1995 dea1 is arguably one of the most competitive improved EA that significantly advances the global modeling capability dea2 ; dea3 . The core idea of DE is introducing a complete differential concept to the conventional EA, which differentiates and scales two individuals in the same population and interacts with the third individual to generate a new individual. In contrast to the category mentioned above, local search-based EAs aim to find a solution that is as good as or better than all other solutions in its neighborhood lea1 ; lea2 ; lea4 . This thought is more efficient than global search in that a solution can quickly be verified as a local optimum without associating the global search space. However, the locality-aware operation will restrict the ability of global modeling that could lead to suboptimal results in some scenarios, so some researchers attempt to fuse both above modeling manners. Moscato et al. mea1 firstly propose the Memetic Evolutionary Algorithm (MEA) in 1989 that applies a local search process to refine solutions for hard problems, which could converge to high-quality solutions more efficiently than conventional evolutionary counterparts. In detail, this variant is a particular global-local search hybrid: the global character is given by the traditional EA, while the local aspect is mainly performed through constructive methods and intelligent local search heuristics mea2 . Analogously, some later works lpea2 ; lpea4 introduce a multi-population evolutionary algorithm to solve the constrained function optimization problems relatively efficiently, which adopts different searching regions to enhance the diversity of individuals that improves the model ability dramatically. This strategy inspires us to design a basic feature extraction module for vision transformer: whether a similar multi-scale manner can be adopted to enhance model expressiveness. Furthermore, Brest et al. alpha1 propose an adaptation mechanism on the control parameters $CR$ and $F$ for crossover and mutation operations associated with DE, where adapted parameters are applied to different optimization processes for obtaining better results. Remarkably, those MEAs mea1 ; mea2 ; mea3 mentioned above own a similar concept of search intensity to balance the global and local calculation. Subsequent work alpha2 investigates jDEdynNP-F algorithm with a dynamic population reduction scheme, where the population size of the next generation is equal to half the previous population size. This strategy significantly improves the effectiveness and accelerates the convergence of the model that is consistently illustrated by works alpha3 ; alpha4 . Furthermore, some literatures bio1 ; bio2 ; bio3 suggest that there are hierarchical structures of V1, V2, V4, and inferotemporal cortex in the evolutionary brain, which have ordered interconnection among them in the form of both feed-forward and feedback connections. Moreover, researchers moea1 ; moea2 ; moea3 study multi-objective EAs to find optimal trade-offs to get a set of solutions for different targets.

Inspired by the aforementioned EA variants that introduce various and valid concepts for optimization, we explain and improve the naive transformer structure by conceptual analogy in the paper, where a novel and potent EATFormer with pyramid architecture, multi-scale region aggregation, and global-local modeling is hand-designed. Furthermore, a plug-and-play task-related head module is developed to solve different targets separately and improve model performance.

Since Transformer structure achieves significant progress for machine translation task attn , many improved language models attn_elmo ; attn_bert ; attn_gpt1 ; attn_gpt2 ; attn_gpt3 are proposed and obtain great achievements, and some later works attn_improve1 ; attn_improve2 ; attn_improve3 ; attn_improve4 ; attn_improve5 ; wang2021evolving advance the basic transformer module for better efficiency. Inspired by the success of Transformer in NLP and the rapid improvement of computing power, Alexey et al. attn_vit propose a novel ViT that firstly introduces the transformer to vision classification and sparks a new wave of research besides conventional CNN-based vision models. Subsequently, many excellent vision transformer models are proposed, and they can mainly be divided into two categories, i.e., pure and hybrid vision transformers. The former only contains transformer module without CNN-based layers, and early worksattn_deit ; attn_deepvit ; attn_tnt ; attn_cait ; attn_t2tvit ; attn_cpvt ; attn_xcit follow columnar structure of original ViT. Typically, DeiT attn_deit propose an efficient training recipe to moderate the dependence on large datasets, DeepViT attn_deepvit and CaiT attn_cait focus on fast performance saturation when scaling ViT to be deeper, and TNT attn_tnt divide local patches into smaller patches for fine-grained modeling. Furthermore, researchers attn_pvt ; attn_swin ; attn_shuffle ; attn_halonets ; attn_twins ; attn_swin2 ; attn_nat ; attn_dpt ; attn_metaformer ; attn_SSA advance ViT to pyramid structure that is more powerful and suitable for dense prediction. PVT attn_pvt leverages a non-overlapping patch partition to reduce feature size, while Swin attn_swin utilizes a shifted window scheme to alternately model in-window and cross-window connection. The latter incorporates the idea of convolution that owns natural inductive bias of locality and translation invariance, and this kind of combination dramatically improves the model effect. Specifically, Srinivas et al. attn_botnet advance CNN-based models by replacing the convolution of the bottleneck block with the MSA structure. Later researches attn_localvit ; attn_ceit ; attn_convit ; attn_vitae introduce convolution designs into columnar visual transformers, while works attn_lvt ; attn_volo ; attn_crossformer ; attn_container ; attn_uniformer ; attn_coat ; attn_cvt ; attn_pvt2 ; attn_vitae2 fuse convolution structures into pyramid structure or use CNN-based backbone on early stages, which has obvious advantages over pure transformer models. Moreover, some researchers design hybrid models from the parallel perspective of convolution and transformer attn_coat ; attn_mobileformer ; attn_mixformer , while Xia et al. attn_vit introduce a deformable idea dcn1 to MSA module and obtain a boost on Swin attn_swin . Recently, MPViT attn_mpvit explores multi-scale patch embedding and multi-path structure that enable both fine and coarse feature representations simultaneously. Benefiting from advances in basic vision transformer models, many task-specific models are proposed and achieve significant progress in down-stream vision tasks, e.g., object detection down_detr ; down_deformabledetr ; down_YOLOS ; down_pix2seq , semantic segmentation down_setr ; down_transunet ; down_medt ; down_segformer ; down_hrformer ; down_maskformer ; down_mask2former , generative adversarial network down_transgan ; down_fat ; down_gat , low-level vision down_ipt ; down_swinir ; down_restormer , video understanding down_vtn ; down_timesformer ; down_STRM ; down_bevt ; down_LSTR , self-supervised learning down_sit ; down_mocov3 ; down_fdsl ; down_mae ; down_beit ; down_dino ; down_peco ; down_cae ; down_simmim ; down_maskfeat ; down_data2vec ; down_convmae , neural architecture search down_hat ; down_bossnas ; down_glit ; down_autoformer ; down_s3 , etc. Inspired by practical improvements in EA variants, this work migrates them to Transformer improvement and designs a powerful visual model with higher precision and efficiency than contemporary works. Also, thanks to the elaborate analogical design, the proposed EATFormer in this paper is highly explanatory.

Transformer-based models have achieved remarkable results on CV tasks, leading us to question why Transformer works so well, even better than Convolutional Neural Networks (CNN). Many efforts have done to answer this question. Goyal et al. theory_more_inductive_bias point out that studying the kind of inductive biases that humans and animals exploit could help inspire AI research and neuroscience theories. Pan et al. theory_more1 show a strong underlying relation between convolution and self-attention operations. Jean-Baptiste et al. theory1 prove that a multi-head self-attention layer with a sufficient number of heads is at least as expressive as any convolutional layer, while Raghu et al. theory2 find striking differences between ViT and CNN on image classification. Kunchang et al. attn_uniformer seamlessly integrate the merits of convolution and self-attention in a concise transformer format, while ConVit attn_convit combines the strengths of both CNN/Transformer architectures to introduce gated positional self-attention. Introducing local CNN into Transformer is followed by many subsequent works attn_cpvt ; attn_uniformer ; cmt ; attn_vitae2 ; mobilevit ; edgenext . Furthermore, Juhong et al. theory3 take a biologically inspired approach and explore modeling peripheral vision by incorporating peripheral position encoding to the multi-head self-attention layers in Transformer. Besides, some works explore the relation between Transformer and other models, e.g., Katharopoulos et al. theory_more_rnn reveals their relationship of Transformer to recurrent neural networks, and Kim et al. theory_more_gnn prove that Transformer is theoretically at least as expressive as an invariant graph network composed of equivariant linear layers. Moreover, Bhojanapalli et al. theory_more2 find that ViT models are at least as robust as the ResNet counterparts on a broad range of perturbations when pre-trained with a sufficient amount of data. Hao et al. attattr propose a self-attention attribution method to interpret the information interactions inside Transformer, while Liu et al. theory_more3 propose an actionable diagnostic methodology to measure the consistency between explanation weights and the impact polarity for attention-based models. Dong et al. attn_notattention find that MLP stops the output from degeneration, and removing MSA in Transformer would also significantly damage the performance. Recently, Qiang et al. theory_more4 propose a novel Transformer explanation technique via attentive class activation tokens by leveraging encoded features, gradients, and attention weights to generate a faithful and confident explanation. Xu et al. theory_more5 propose a new way to visualize the model by firstly computing attention scores based on attribution and then propagating these attention scores through the layers. Works attn_metaformer ; zhang2023rethinking demonstrate that the general architecture of the Transformers is more essential to performance rather than the specific token mixer module. The above work explores the interpretation of Transformer from a variety of perspectives. At the same time, we will provide another explanation from the perspective of evolutionary algorithms and design a robust model to perform multiple CV tasks.

As aforementioned in Figure 1, the Transformer block has conceptually similar sub-modules analogously to evolutionary algorithm. Basically, Transformer inputs a sequence of patch tokens while EA evolutes a population that consists of many individuals. Both of which have the consistent vector format and necessary initialization. In order to facilitate the subsequent analogy and formula derivation, we symbolize the patch token (individual) as $\boldsymbol{x}_{i}=[x_{i,1},x_{i,2},\dots,x_{i,D}]$, where $i$ and $D$ indicate data order and dimension, respectively. Define $L$ as the sequence length, the sequence (population) can be denoted as $\boldsymbol{X}=[\boldsymbol{x}_{1},\boldsymbol{x}_{2},\dots,\boldsymbol{x}_{L}]^{\mathrm{T}}$. The specific relationship analyses of different components are as follows:

✰

Crossover Operator vs. MSA Module.
For the crossover operator of EA, it aims at creating new individuals by combining parts of other individuals. For an individual $\boldsymbol{x}_{i}$ specifically, the operator will randomly pick another individual $\boldsymbol{x}_{j}=[x_{j,1},x_{j,2},\dots,x_{j,D}](1\leq j\leq L)$ in the global population and randomly replaces features of $\boldsymbol{x}_{i}$ with $\boldsymbol{x}_{j}$ to form the new individual $\hat{\boldsymbol{x}}_{i}$:

		$\displaystyle\hat{\boldsymbol{x}}_{i,d}=\begin{cases}\boldsymbol{x}_{j,d}\text{, if }\operatorname{randb}(d)\leqslant CR\\ \boldsymbol{x}_{i,d}\text{, otherwise }\end{cases}$		(4)
		$\displaystyle\text{s.t.}~{}~{}i\neq j,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}d\in\{1,2,\ldots,D\}}\text{, }$

where $\operatorname{randb}(d)$ is the $d$-th evaluation of a uniform random number generator with outcome in $[0,1]$, and $CR$ is the crossover constant in $[0,1]$ that is determined by the user. We re-formulate this process as:

$\begin{aligned} \hat{\boldsymbol{x}}_{i}&=boldsymbol{x}_{i,1}\boldsymbol{w}_{i,1},\dots,\boldsymbol{x}_{i,D}\boldsymbol{w}_{i,D}]+[\boldsymbol{x}_{j,1}\boldsymbol{w}_{j,1},\dots,\boldsymbol{x}_{j,D}\boldsymbol{w}_{j,D}]\\ &=\boldsymbol{x}_{1}\odot\boldsymbol{0}+\dots\boldsymbol{x}_{i}\odot\boldsymbol{w}_{i}+\dots\boldsymbol{x}_{j}\odot\boldsymbol{w}_{j}+\dots\boldsymbol{x}_{L}\odot\boldsymbol{0}\\ &=\boldsymbol{x}_{1}\boldsymbol{0}+\dots\boldsymbol{x}_{i}\boldsymbol{W}^{cr}_{i}+\dots\boldsymbol{x}_{j}\boldsymbol{W}^{cr}_{j}+\dots\boldsymbol{x}_{L}\boldsymbol{0}\\ &=\sum_{l=1}^{L}\left(\boldsymbol{x}_{l}\boldsymbol{W}^{cr}_{l}\right),\\ &~{}\text{s.t.}~{}~{}\boldsymbol{w}_{i}+\boldsymbol{w}_{j}=\boldsymbol{1}~{}\text{, }\\ &~{}~{}~{}~{}~{}~{}~{}\boldsymbol{w}_{i,d}\in[0,1],~{}\boldsymbol{w}_{j,d}\in[0,1],~{}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}d\in\{1,2,\ldots,D\}}~{}\text{, }\end{aligned}$

(5)

where $\boldsymbol{w}_{i}$ and $\boldsymbol{w}_{j}$ are vectors filled with zeros or ones, indicating the feature selections of $\boldsymbol{x}_{i}$ and $\boldsymbol{x}_{j}$, while $\boldsymbol{W}^{cr}_{i}$ and $\boldsymbol{W}^{cr}_{j}$ are corresponding diagonal matrix representations. $\odot$ means the point-wise multiplication operation for each position. $\boldsymbol{0}$ represents that corresponding individual has no contribution, i.e., $\boldsymbol{W}^{cr}_{l}(l\neq i,j)$ fulls of zeros. As can be seen above, crossover operator is actually a sparse global feature interaction process.

For the MSA module of Transformer, each patch embedding interacts with all embeddings in dense communications. Without loss of generality, $\boldsymbol{x}_{i}$ interacts with the whole population $\boldsymbol{X}$ as follows:

	$\displaystyle\hat{\boldsymbol{x}}_{i}$	$\displaystyle=\bigoplus_{h=1}^{H}\hat{\boldsymbol{x}}_{i,h}$		(6)
		$\displaystyle=\bigoplus_{h=1}^{H}\sum_{l=1}^{L}\boldsymbol{A}_{l,h}\boldsymbol{V}_{l,h}$
		$\displaystyle=\bigoplus_{h=1}^{H}\sum_{l=1}^{L}\boldsymbol{A}_{l,h}\boldsymbol{x}_{l}\boldsymbol{W}_{h}^{V}$
		$\displaystyle=\bigoplus_{h=1}^{H}\sum_{l=1}^{L}\left(\boldsymbol{A}_{l,h}\boldsymbol{x}_{l}\boldsymbol{W}_{h}^{V}\right)$
		$\displaystyle=\sum_{l=1}^{L}\left(\boldsymbol{x}_{l}\bigoplus_{h=1}^{H}\left(\boldsymbol{A}_{l,h}\boldsymbol{W}_{h}^{V}\right)\right)$
		$\displaystyle=\sum_{l=1}^{L}\left(\boldsymbol{x}_{l}\left(\boldsymbol{A}_{l}\boldsymbol{W}^{V}\right)\right),$

where $\boldsymbol{A}_{l,h}$ (l $\in$ $\{$1,2,$\cdots$,L$\}$) is the attention weight of $h$-th head from embedding token $\boldsymbol{x}_{l}$ to $\boldsymbol{x}_{i}$, which is calculated between the query value of $\boldsymbol{x}_{i,h}$ and the key value of $\boldsymbol{x}_{l,h}$ of $h$-th head followed with a $\operatorname{Softmax}(\cdot)$ postprocessing; $\boldsymbol{V}_{l,h}$ (l $\in$ $\{$1,2,$\cdots$,L$\}$) is the projected Value feature for $\boldsymbol{x}_{l}$ with corresponding weights $\boldsymbol{W}_{h}^{V}$; $\hat{\boldsymbol{x}}_{i,h}$ is the sum of all weighted $\boldsymbol{V}_{l,h}$ (l $\in$ $\{$1,2,$\cdots$,L$\}$) by $\boldsymbol{A}_{l,h}$ (l $\in$ $\{$1,2,$\cdots$,L$\}$), i.e., $\hat{\boldsymbol{x}}_{i,h}=\sum_{l=1}^{L}\boldsymbol{A}_{l,h}\boldsymbol{V}_{l,h}$, (c.f., Eq. 1 in Section 3) for more details. $\boldsymbol{W}^{V}$ is the parameter matrix for the value projection and $\oplus$ means the concatenation operation. By comparing Equation 5 with Equation 6, we find that both above components have the same formula representation, and the crossover operation is a sparse global interaction while densely-modeling MSA has more complex computing and modeling capabilities.

✰

Mutation Operator vs. FFN Module.
For the mutation operator in EA, it brings random evolutions into the population by stochastically changing specific features of individuals. Specifically, an individual $\boldsymbol{x}_{i}$ in the population goes through Mutation operation to form the new individual $\hat{\boldsymbol{x}}_{i}$, formulated as follows:

		$\displaystyle\hat{\boldsymbol{x}}_{i,d}=\begin{cases}\operatorname{rand}(v_{d}^{L},v_{d}^{H})\cdot x_{i,d}\text{, if }\operatorname{randb}(d)\leqslant MU\\ 1\cdot x_{i,d}\text{, otherwise }\end{cases}$		(7)
		$\displaystyle\text{s.t.}~{}~{}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}d\in\{1,2,\ldots,D\}}\text{, }$

where $\operatorname{randb}(d)$ is the $d$-th evaluation of a uniform random number generator with outcome in $[0,1]$, and $MU$ is the mutation constant in $[0,1]$ that user determines. $v_{j}^{L}$ and $v_{j}^{H}$ are lower and upper scale bounds of the $j$-th feature relative to $x_{i,d}$. Similarly, we re-formulate this process as:

	$\displaystyle\hat{\boldsymbol{x}}_{i}$	$\displaystyle=\boldsymbol{x}_{i}\odot\boldsymbol{w}_{i}$		(8)
		$\displaystyle=\boldsymbol{x}_{i}\boldsymbol{W}^{mu}_{i},$

where $\boldsymbol{w}_{i}$ is a randomly generated vector that represents weights of each feature value, while $\boldsymbol{W}^{mu}_{i}$ is the corresponding diagonal matrix representation; $\odot$ means the point-wise multiplication operation for each position.

For the FFN module in Transformer, each patch embedding carries on directional feature transformation through cascaded linear layers (c.f., Equation 2). Getting rid of complex nonlinear transformations, we only take one linear layer as an example:

$\displaystyle\hat{\boldsymbol{x}}_{i}$

$\displaystyle=\boldsymbol{x}_{i}\boldsymbol{W}^{FFN},$

(9)

where $\boldsymbol{W}^{FFN}$ is the weight of the linear layer, and it is applied to each embedding separately and identically.

By analyzing the calculation process of Equation 8 and Equation 9, Mutation and FFN operations share a unified form of matrix multiplication, so they are supposed to own a consistent function essentially. Besides, at the microcosmic level, the weight of FFN change dynamically during the training process, so the output of the individual differs among different iterations (similar to the random process of mutation). At the macroscopic objective of the algorithm, the mutation in EA is optimized into one potential direction under the constraint of the objective function (statistically speaking, only partial mutation individuals are retained, that is, the mutation also has a determinate meaning in the whole training process). In comparison, the trained FFN can be regarded as a directional mutation under the constraint of loss functions. Finally, note that we are only discussing the comparison with the mutation on one linear layer of FFN, and $\boldsymbol{W}^{FFN}$ is more expressive than diagonal $\boldsymbol{W}^{mu}_{i}$ in fact because it contains cascaded linear layers and the non-linear ReLU activation is interspersed between adjacent linear layers, as depicted in Equation 2.

✰

Population Succession vs. RC Operation.
In the evolution of the biological population, individuals at the current iteration have a certain probability of inheriting to the next iteration, where a partial population of the current iteration will be combined with the selected individuals. Similarly, the above pattern is expressed by Transformer structure in the form of Residual Connection (RC), i.e., patch embeddings of the previous layer are directly mapped to the next layer. Specifically, partial-selection can be viewed as a dropout technique in Transformer, while population succession can be formulated as a concatenation operation that has a consistent mathematical expression with residual concatenation, whereas addition operation can be regarded as a particular case of the concatenation operation that shares some partial weights.

✰

Best Individual vs. Task-Related Token.
Generally speaking, the Transformer-based model chooses an enhanced task-related token (e.g., classification token) that combines information of all patch embeddings as the output feature, while the EA-based method chooses the individual with the best fitness score among the population as the output.

✰

Necessity of Modules in Transformer.
As described in the work s16 , the absence of the crossover operator or mutation operator will significantly damage the model’s performance. Similarly, Dong et al. attn_notattention explore the effect of MLP in the Transformer and find that MLP stops the output from degeneration, and removing MSA in Transformer would also significantly 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.

We explore the relationship among operators in naive EA and modules in naive Transformer in the previous NeurIPS’21 conferenceeat and analogically improve a columnar EAT based on ViT model. Figure 4-(a) shows the structure of EAT model that is stacked of with N improved Transformer blocks inspired by local population concept in some EA works lea1 ; lea2 ; mea1 , where a local path is introduced in parallel with global MSA operation. Also, this work designs a Task-Related Head to deal with various tasks more flexibly, i.e., classification and distillation.

However, the columnar structure is naturally inadequate for downstream dense prediction tasks, and it is inferior in terms of accuracy compared with contemporaneous works attn_pvt ; attn_swin , which limits the usefulness of the model in some scenarios. To address the above weaknesses, this paper further explores analogies between EA and Transformer and improves the previous work to a pyramid EATFormer, consisting of the newly designed EAT block inspired by the effective EA variants.

Architecture of the improved EATFormer is illustrated in Figure 4-(b), which contains four stages of different resolutions following PVT attn_pvt . Specifically, the model is made up of EAT blocks that contains three mixed-paradigm $y=f(x)+x$ residuals: (a) Multi-Scale Region Aggregation (MSRA), (b) Global and Local Interaction (GLI), and (c) Feed-Forward Network (FFN) modules, and the down-sampling procedure between two stages is realized by MSRA with stride greater than 1. Besides, we propose a novel Modulated Deformable MSA (MD-MSA) to advance global modeling and a Task-Related Head (TRH) to complete different tasks more elegantly and flexibly.

In the former conference version eat , we improve the columnar ViT by introducing a local path in parallel with global MSA operation, denoted as EAT-Ti, EAT-S, and EAT-B in the top part of Table 3. In this paper, we extend the columnar structure to a pyramid architecture and carefully re-design a novel EATFormer model, which has a series of scales for different practical applications, and these variants can be viewed in the bottom part of Table 3. Except for the depth and dimension of the model, other parameters remain consistent for all models: the head dimension of MSA is 32; window size is set to 7; kernel size of all convolution is $3\times 3$; dilations of the MSRA module for four stages are [1], [1], [1,2,3], and [1,2], respectively; low-level stage1-2 only use local path while high-level stage3-4 employ hybrid GLI module for efficiency. More detailed structures and implementations can be viewed in the attached source code.

Compared with EAT in the former conference version, the improved EATFormer has better inspirations, finer analogical designs, and more sufficient experiments. And we prove the effectiveness and integrity of the proposed method through a series of following experiments, such as comparison with SOTA methods, downstream task transferring, ablation studies, and explanatory experiments. It is worth noting that the backbone of EATFormer in this paper only contains one unified EAT block, which fully considers three aspects of modeling: 1) multi-scale information aggregation, 2) feature interactions among tokens, and 3) individual enhancement. Also, the architecture recipes of EATFormer variants in this paper are mainly given by our intuition and proved by experiments, but the alterable configure parameters can be used as the search space for NAS that is worth further exploration in our future works, e.g., embedding dimension, dilations of MSRA, kernel size of MSRA, fusion function of MSRA, down-sampling mode of MSRA, separation ratio of GLI, normalization types, window size, operation combinations of GLI, etc.