\section{Introduction}
\label{sec:intro}

These guidelines include complete descriptions of the fonts, spacing, and
related information for producing your proceedings manuscripts. Please follow
them and if you have any questions, direct them to Conference Management
Services, Inc.: Phone +1-979-846-6800 or email
to \\\texttt{icip2019@cmsworkshops.com}.

\section{Formatting your paper}
\label{sec:format}

All printed material, including text, illustrations, and charts, must be kept
within a print area of 7 inches (178 mm) wide by 9 inches (229 mm) high. Do
not write or print anything outside the print area. The top margin must be 1
inch (25 mm), except for the title page, and the left margin must be 0.75 inch
(19 mm).  All {\it text} must be in a two-column format. Columns are to be 3.39
inches (86 mm) wide, with a 0.24 inch (6 mm) space between them. Text must be
fully justified.

\section{PAGE TITLE SECTION}
\label{sec:pagestyle}

The paper title (on the first page) should begin 1.38 inches (35 mm) from the
top edge of the page, centered, completely capitalized, and in Times 14-point,
boldface type.  The authors' name(s) and affiliation(s) appear below the title
in capital and lower case letters.  Papers with multiple authors and
affiliations may require two or more lines for this information. Please note
that papers should not be submitted blind; include the authors' names on the
PDF.

\section{TYPE-STYLE AND FONTS}
\label{sec:typestyle}

To achieve the best rendering both in printed proceedings and electronic proceedings, we
strongly encourage you to use Times-Roman font.  In addition, this will give
the proceedings a more uniform look.  Use a font that is no smaller than nine
point type throughout the paper, including figure captions.

In nine point type font, capital letters are 2 mm high.  {\bf If you use the
smallest point size, there should be no more than 3.2 lines/cm (8 lines/inch)
vertically.}  This is a minimum spacing; 2.75 lines/cm (7 lines/inch) will make
the paper much more readable.  Larger type sizes require correspondingly larger
vertical spacing.  Please do not double-space your paper.  TrueType or
Postscript Type 1 fonts are preferred.

The first paragraph in each section should not be indented, but all the
following paragraphs within the section should be indented as these paragraphs
demonstrate.

\section{MAJOR HEADINGS}
\label{sec:majhead}

Major headings, for example, "1. Introduction", should appear in all capital
letters, bold face if possible, centered in the column, with one blank line
before, and one blank line after. Use a period (".") after the heading number,
not a colon.

\subsection{Subheadings}
\label{ssec:subhead}

Subheadings should appear in lower case (initial word capitalized) in
boldface.  They should start at the left margin on a separate line.

\subsubsection{Sub-subheadings}
\label{sssec:subsubhead}

Sub-subheadings, as in this paragraph, are discouraged. However, if you
must use them, they should appear in lower case (initial word
capitalized) and start at the left margin on a separate line, with paragraph
text beginning on the following line.  They should be in italics.

\section{PRINTING YOUR PAPER}
\label{sec:print}

Print your properly formatted text on high-quality, 8.5 x 11-inch white printer
paper. A4 paper is also acceptable, but please leave the extra 0.5 inch (12 mm)
empty at the BOTTOM of the page and follow the top and left margins as
specified.  If the last page of your paper is only partially filled, arrange
the columns so that they are evenly balanced if possible, rather than having
one long column.

In LaTeX, to start a new column (but not a new page) and help balance the
last-page column lengths, you can use the command ``$\backslash$pagebreak'' as
demonstrated on this page (see the LaTeX source below).

\section{PAGE NUMBERING}
\label{sec:page}

Please do {\bf not} paginate your paper.  Page numbers, session numbers, and
conference identification will be inserted when the paper is included in the
proceedings.

\section{ILLUSTRATIONS, GRAPHS, AND PHOTOGRAPHS}
\label{sec:illust}

Illustrations must appear within the designated margins.  They may span the two
columns.  If possible, position illustrations at the top of columns, rather
than in the middle or at the bottom.  Caption and number every illustration.
All halftone illustrations must be clear black and white prints.  Colors may be
used, but they should be selected so as to be readable when printed on a
black-only printer.

Since there are many ways, often incompatible, of including images (e.g., with
experimental results) in a LaTeX document, below is an example of how to do
this \cite{Lamp86}.

\section{FOOTNOTES}
\label{sec:foot}

Use footnotes sparingly (or not at all!) and place them at the bottom of the
column on the page on which they are referenced. Use Times 9-point type,
single-spaced. To help your readers, avoid using footnotes altogether and
include necessary peripheral observations in the text (within parentheses, if
you prefer, as in this sentence).

\begin{figure}[htb]

\begin{minipage}[b]{1.0\linewidth}
  \centering
  \centerline{\includegraphics[width=8.5cm]{image1}}
  \centerline{(a) Result 1}\medskip
\end{minipage}
\begin{minipage}[b]{.48\linewidth}
  \centering
  \centerline{\includegraphics[width=4.0cm]{image3}}
  \centerline{(b) Results 3}\medskip
\end{minipage}
\hfill
\begin{minipage}[b]{0.48\linewidth}
  \centering
  \centerline{\includegraphics[width=4.0cm]{image4}}
  \centerline{(c) Result 4}\medskip
\end{minipage}
\caption{Example of placing a figure with experimental results.}
\label{fig:res}
\end{figure}

\section{COPYRIGHT FORMS}
\label{sec:copyright}

You must include your fully completed, signed IEEE copyright release form when
form when you submit your paper. We {\bf must} have this form before your paper
can be published in the proceedings.

\section{REFERENCES}
\label{sec:ref}

List and number all bibliographical references at the end of the
paper. The references can be numbered in alphabetic order or in
order of appearance in the document. When referring to them in
the text, type the corresponding reference number in square
brackets as shown at the end of this sentence \cite{C2}. An
additional final page (the fifth page, in most cases) is
allowed, but must contain only references to the prior
literature.

\bibliographystyle{IEEEbib}

\section{Introduction}

Human vision is naturally more attracted by some regions within their field of view than others. This natural selectivity mechanism, so-called visual attention, is influenced by both high- and low-level factors; such as the global environment (illumination, background texture, etc.), stimulus  characteristics (color, intensity, orientation, etc.), and some prior visual information \cite{featureIntegration}. It gives the Human Visual System (HVS) an astonishing efficiency for detection and recognition through rapid eye movements called saccades. Predicting visual attention became a staple to improve many image processing and computer vision applications such as indoor localization \cite{VCIP14}, image quality \cite{SPIC20Chetouani,ICIP18Ilyass,PR20Ilyass, EUSIPCO18Chetouani}, image watermarking \cite{info19Hamidi}, image compression, recognition, and captioning. Visual attention is usually depicted using 2D heat maps, often called saliency maps, representing the most spatial-attractive regions in a given stimulus. The sequential representation of the points follows during the exploration of the image, also called scanpath, is used to derive saliency maps.

Researchers put a lot of efforts in predicting such saliency heat maps, starting with the seminal work of Koch and Ulman \cite{KochUllman}, later followed by Itti et al. \cite{Itti} where multi-scale low level features were used. In \cite{GBVS}, the saliency is predicted based on the graph theory where Markov chains is defined over different input  maps. Several other interesting saliency models have been proposed based on heuristic approaches and low level features  \cite{spectral1} \cite{spectral2}.

With the recent success of deep learning, many deep-based saliency models have been developed. Pan et al. \cite{PanDSN} proposed one of the first Convolutional Neural Network (CNN) models where a deep and shallow networks were used. In \cite{salgan}, the authors proposed a deep convolutional Generative Adversarial Network (GAN) based saliency model with adversarial training. In \cite{deepgaze1}, the authors introduced a method called DeepGaze I where they trained an AlexNet \cite{deepgaze1ref} based network on MIT dataset. The authors later introduced a new version, called DeepGazeII \cite{deepgaze2}, where a VGG-19 network \cite{VGG} was exploited. In \cite{MLNet}, the authors proposed a more complex architecture where multi level features extracted from a VGG \cite{VGG} network were employed. In \cite{SAM}, the authors designed a method to predict the saliency by incorporating an attention mechanism based on the combination of Long Short Term Memory (LSTM) and convolutional networks. In \cite{unisal}, the authors proposed a unified model for saliency prediction, called Unisal, that predicts the saliency for images and videos.
\vspace{-3mm}

Contrary to the large number of saliency models proposed in the literature, the studies dedicated to the prediction of scanpath are less extensive. In \cite{lemeur}, the authors proposed a model where visual scanpaths are inferred stochastically from saliency maps as well as saccadic amplitudes and orientation biases derived from several datasets. In \cite{saltinet}, the authors proposed a deep model, called Saltinet, that samples the saccades from a predicted static saliency volume generated by a CNN encoder-decoder network. The authors later proposed a saliency model, called PathGan \cite{pathgan}, that predicts scanpath by using LSTM layers and a VGG network with adversarial training. The underlying idea of using LSTM was to predict the current fixation point according to the previous ones to increase the sequential dependence between fixations. In \cite{G-Eymol}, the authors presented a model of scanpath as a dynamic process simulating the laws of gravitational mechanics. The gaze is considered as traveling mass point in the image space, and salient regions as gravitational fields affecting the mass speed and trajectory. In \cite{DCSM}, the authors proposed a Deep Convolutional Saccadic Model (DCSM) where the fixation points are predicted from foviated saliency maps and temporal duration while modeling the inhibition of return.

\begin{comment}
With the advancement of deep methods, another kind of attention was introduced, one which focuses on improving tasks not related to human perception like classification \cite{CBAM} and segmentation \cite{ChenAtt}, where small separate module were created to mimic the mechanism for separate ends, these module often produce spatial heatmaps or vectors serving to emphasis the most most important features.
\cite{ChenAtt} muti-scale semantic segmentation network, introduced a soft attention  module to  weight multi-scale features at each pixel.
\cite{xu2015show} compared soft and hard attention for directing the decoder attention to  salient objects in his image captioning model.
While, \cite{CBAM} proposed CBAM a module that combines channel and space wise attention, to  improve Resnet classification.
\end{comment}

\begin{figure*}[ht!]
  \centering
  \centerline{\includegraphics[height=50mm]{figures/model_icip_3.jpg}}
\caption{\textbf{SALYPATH:} SALiencY and scanPATH prediction model}
\label{fig:arch}
\end{figure*}
\vspace{-3mm}

In this study, we propose an end-to-end deep-based method, called SALYPATH (SALiencY and scanPATH), that efficiently predicts the scanpath of images by leveraging features from a trained saliency model. The idea is to predict the scanpath of a given image by exploiting the capacity of a deep-based model to predict the saliency. Inspired by SalGan \cite{salgan}, we first construct a saliency model that integrates an attention module. Feature maps are then extracted from the designed saliency model and fed as input to a second CNN model that aims to predict the scanpath of the image.

The rest  of  the  paper  is organized as follows: Section 2 describes the proposed method in details. We then discuss the results obtained in Section 3. Finally, we provide some conclusions in Section 4.

\section{Proposed Method}

\begin{comment}
While visual saliency and scanpath prediction are 2 different tasks, they are still related. And  there have been a lot of proposed methods that use saliency maps for scanpath prediction.

We are presenting a deep end-to-end fully convolutional architecture that leveraged the intermediate features issued by a VGG type encoder, then further refined them through an attention module, to finally predict an adequate scanpath along with  a saliency map.

\end{comment}

As illustrated by Fig. \ref{fig:arch}, we propose a novel fully convolutional neural network architecture for predicting saliency and scanpath of static natural images. Our model is composed of a VGG-based encoder as well as two predictor networks to predict the corresponding saliency and scanpath, respectively. An attention module is also used to adaptively refine the features extracted from the encoder part. Each part of the proposed model is described in this section.

\subsection{Saliency Prediction}

In order to predict the scanpath of a given image, we design a deep-based saliency model. The idea is to predict the scanpath of a given image by exploiting high level features of a deep-based saliency model. The proposed model is constituted by a VGG-based encoder-decoder similar to the generator part of SalGan \cite{salgan}. The encoder part is composed of (3x3) convolutional layers and (2x2) max-pooling layers, while the decoder part is composed of (3x3) convolutions and (2x2) up-sampling layers with a (1x1) final convolutional layer activated by a Sigmoid function. The encoder aims to generate high dimensional feature maps from the input image by aggregating them on multiple levels, while decoder aims to merge the obtained feature maps to a single image that represents the saliency map.

\subsection{Scanpath Prediction}

From the model's bottle-neck, we extract the high level representational features to predict the scanpath through a fully convolutional network. It is composed of 10 convolutional layers while gradually decreasing the depth of the feature maps to 8 channels, corresponding to the length of the predicted scanpath. The latter has been fixed according to a statistical analysis of the lengths of scanpaths provided by the dataset used to train our model (see Section \ref{DATASET}). The central tendency indicates that a length of 8 fixation points is appropriate. The output of our fully convolutional network is then fed to a \textit{Soft-ArgMax} (SAM) \cite{Soft-ArgMax} function which returns the coordinates of the highest activation point for each feature map as follows:

\begin{equation}
  SAM(x) =  \sum_{i=0}^{W} \sum_{j=0}^{H} \frac{e^{\beta x_{i,j}}}{\sum_{i^\prime =0 }^{W} \sum_{j^\prime = 0 }^{H} e^{\beta x_{i^\prime ,j^\prime }}}({\frac{i}{W},\frac{j}{H}})^T
  \label{eq:SAM}
\end{equation}
where ${i,j,i^\prime ,j^\prime}$ iterate over pixel coordinates and ${H,W}$ represent the height and width of the feature map, respectively. $x$ is the input feature map and $\beta$ is a parameter adjusting the distribution of the softmax output.

It is worth noting that unlike the discrete \textit{ArgMax}, the \textit{Soft-ArgMax} function is differentiable. It also allows a sub-pixel regression, thus providing a better prediction even with smaller feature maps passed on the scanpath prediction model.

\vspace{-3mm}

\subsection{Attention Module}

In other fields of computer vision, attention is an approach for attending to different parts of an input vector to capture a global representation of features. It has been proven that adding such modules allows to refine intermediate features and thus improve the global performance \cite{ChenAtt} \cite{xu2015show}. Thanks to this specificity, an attention module has been here incorporated to improve the feature representation used to predict both saliency and scanpath. More precisely, we employed the Convolutional Block Attention Module (CBAM) \cite{CBAM} which is composed of 2 blocks as shown in the attention module box in Fig.\ref{fig:arch}. The channel attention block exploits the interrelations between feature maps and outputs a channel-wise weighted feature vector emphasizing the more important features in relation to the task. While the spatial attention block calculates the importance of features according to their spatial position emphasizing the most important location in each high-level feature. The attention module is used in parallel to the stream between encoder and decoder at the bottle-neck. The output of the module is represented by the following equation:

\begin{equation}
  z = X \otimes Att_S(X \otimes Att_{Ch}(X))
  \label{eq:cbam_out}
\end{equation}
where \textit{z} is the output of the module, \textit{$Att_S$} and \textit{$Att_{Ch}$} are the spatial attention and the channel attention blocks, respectively. $X$ is the input feature maps and $\otimes$ represents the element-wise multiplication.

The input $X^\prime$ of the decoder and the fully convolutional network branches is then computed as follows:
\begin{equation}
  X^\prime = X + z \otimes \gamma
  \label{eq:input_decode}
\end{equation}
where $\gamma$ is a learnable parameter.

\begin{table*}[ht!]
\begin{center}
\scalebox{0.8}{
\begin{tabular}{ c  c  c  c  c  c  c  c c}
\hline
\textbf{Model} & \textbf{Auc Judd $\uparrow$} & \textbf{Auc Borji$\uparrow$} & \textbf{NSS$\uparrow$}& \textbf{CC$\uparrow$}& \textbf{SIM$\uparrow$} & \textbf{KLD $\downarrow$}  \\

\hline
 Salgan\cite{salgan} & 0.8662  & \textbf{0.8443}  & 1.9460  &  0.5836 & 0.4908  & 1.0470         \\
 \hline
 Salicon\cite{opensalicon} &  0.8630 & 0.8135   & 2.1240 &  0.6013  &  0.4923     & 0.9051      \\
 \hline
 MLNet\cite{MLNet} & 0.8509 & 0.7714 & \textbf{2.1678} & 0.5787 & 0.4815 & 1.3083 \\
 \hline
 %
SALYPATH (Our method)  & \textbf{0.8745} & 0.8290 & 2.1152 & \textbf{0.6182} &  \textbf{0.4982}   & \textbf{0.8750}       \\
\hline
 %

\end{tabular}}
\caption{\label{tab:sal_mit_results}Results of saliency prediction on MIT1003.}
\end{center}
\end{table*}
\vspace{-3mm}

\subsection{Training}

Two different loss functions have been used to train each branch of our model. The saliency branch was trained using the following loss function $L_1$:
\begin{equation}
\begin{split}
    \textit{$L_1$} = 0.6 \times  KLdiv(y,\hat{y} ) + 0.3 \times  MSE(y,\hat{y} ) \\ - 0.1 \times NSS(y,\hat{y})
     \label{eq:SAlL}
\end{split}
\end{equation}
where $KLdiv$ is the Kullback-Leibler Divergence, $MSE$ is the Mean Squared Error and $NSS$ is Normalized Scanpath Saliency. $y$ and $\hat{y}$ are the predicted and the ground truth saliency maps, respectively.

Each term of the designed loss function has its own impact on the convergence of our model \cite{Losses}. Indeed, $KLdiv$ function aims to compare the distributions of the output and the corresponding ground truth, while $MSE$ function regularizes the loss by comparing the predicted saliency map and its corresponding ground truth on pixel level \cite{LossesSal}. We also introduced the NSS value which is usually used as metric to evaluate saliency prediction \cite{NSS}. It allows to capture several properties that are specific to saliency maps. This branch was trained with a learning rate of $10^{-7}$ and a step LR scheduler with a multiplicative factor of 0.9 per epoch.

The scanpath branch was trained using only the $MSE$ as loss function $L_2$ (see eq. \ref{eq:SPL}). It was used since scanpath prediction are characterized by the locations of their fixation points and thus their prediction can be seen as a regression problem. It worth noting that the scanpaths are predicted through features of the designed saliency model. To better predict the scanpath, we here focused more on improving the intermediate representational space, optimized through the more complex saliency loss function $L_1$ (see eq. \ref{eq:SAlL}). This branch was trained with a learning rate of $10^{-5}$ and a step LR scheduler with a multiplicative factor of 0.9 per epoch.

\begin{equation}
    L_2 = \frac{1}{N} \sum_i (p - \hat{p} )^2
    \label{eq:SPL}
\end{equation}
where $p$ is the predicted scanpath and $\hat{p}$ is the ground truth scanpath, while $N$ is the number of the fixation points.
\vspace{-3mm}

\section{Experimental Results}
In this section, we evaluate the capacity of our method to predict the scanpath of a given image. After presenting the datasets used, the saliency prediction branch as well as the scanpath prediction branch are evaluated. Both are also compared to a set of representative state-of-the-art methods.

\subsection{Datasets}
\label{DATASET}
In order to evaluate of our method, two widely used datasets have been employed: Salicon \cite{Salicon} and MIT1003 \cite{MIT1003}. Salicon dataset is the largest natural image saliency dataset and it was built for the Salicon challenge. More precisely, we used a subset of 15000 images from the dataset for training (i.e. 9000), validation (i.e. 1000) and testing (i.e. 5000). MIT1003 dataset is one of the most used natural image saliency datasets and it was employed during the MIT300 challenge\cite{MIT300}. It is composed of 1003 natural images with their corresponding saliency maps and scanpaths. The whole dataset has been considered in this study for cross-dataset testing.

\subsection{Saliency Prediction}

In this section, we evaluate the saliency prediction branch using common metrics \cite{salMetrics_Bylinskii}: Area Under Curve Judd ($Auc\_Judd$), $Auc\_Borji$, NSS, Correlation coefficient ($CC$), Similarity ($SIM$) and kullback Leibler Divergence ($KLD$). Table \ref{tab:sal_mit_results} shows the results obtained on the MIT1003 dataset. The results obtained are also compared to some state-of-the-art saliency models (i.e. Salgan \cite{salgan}, Salicon \cite{Salicon} and MLNet \cite{MLNet}). As can be seen, our model achieves the best results compared to the other models in 4 different metrics including $Auc\_Judd$, $CC$, $SIM$, and $KLD$. In particular, we obtain a significant improvement in terms of $KLD$ compared to Salgan and MLNet
We reach close second place to SalGan in terms of $Auc\_Borji$ metric, while the obtained $NSS$ values are close to Salicon and MLNet.

\subsection{Scanpath Prediction}

\begin{table*}[h]
\begin{center}
\scalebox{0.8}{
\begin{tabular}{ c  c  c  c  c  c  c c}
\hline
\textbf{Model} & \textbf{MM Shape } & \textbf{MM Dir}   & \textbf{MM Len} & \textbf{MM Pos}& \textbf{MM Mean}& \textbf{NSS} & \textbf{Congruency}  \\
\hline
 PathGan\cite{pathgan} & 0.9608  &  0.5698   &   \textbf{0.9530} &     0.8172  &    0.8252 & -0.2904  &  0.0825        \\
 \hline
 Le Meur\cite{lemeur} & 0.9505  & 0.6231   &  0.9488 & 0.8605  &   0.8457  &  \textbf{0.8780} &   \textbf{0.4784}        \\
 \hline
 G-Eymol\cite{G-Eymol} & 0.9338 & 0.6271 & 0.9521 & \textbf{0.8967} &  0,8524 & 0.8727 & 0.3449\\

 \hline
 SALYPATH (Our method) & \textbf{0.9659}  & \textbf{0.6275} & 0.9521 & 0.8965  &   \textbf{0,8605} &   0.3472 &  0.4572     \\
 \hline
\end{tabular}}
\caption{\label{tab:salicon_results}Results of scanpath prediction on Salicon.}
\end{center}
\end{table*}

\begin{table*}[htp!]
\begin{center}
\scalebox{0.8}{
\begin{tabular}{ c  c  c  c  c  c  c c}
\hline
\textbf{Model} & \textbf{MM Shape } & \textbf{MM Dir}   & \textbf{MM Len} & \textbf{MM Pos}& \textbf{MM Mean}& \textbf{NSS} & \textbf{Congruency}  \\
\hline
 PathGan\cite{pathgan} & 0.9237  & 0.5630   & 0.8929   &  0.8124    &   0.7561  & -0.2750  &  0.0209        \\
 \hline
 DCSM (VGG)\cite{DCSM}  & 0.8720 & 0.6420 & 0.8730 & 0.8160 & 0,8007 & - & - \\
 \hline
 DCSM (ResNet)\cite{DCSM} & 0.8780 & 0.5890 & 0.8580 & \textbf{0.8220} &  0,7868 & - & -\\
 \hline
 Le Meur\cite{lemeur} & 0.9241  &  0.6378  & \textbf{0.9171}  &  0.7749 &  0,8135  & 0.8508   &  \textbf{0.1974}    \\
 \hline
 G-Eymol\cite{G-Eymol} & 0.8885 & 0.5954 & 0.8580 & 0.7800 &  0,7805 & \textbf{0.8700} & 0.1105\\

 \hline
 SALYPATH (Our method) & \textbf{0.9363}  & \textbf{0.6507} & 0.9046 & 0.7983  &   \textbf{0,8225} &  0.1595  &   0.0916    \\
 \hline

\end{tabular}}
\caption{\label{tab:mit1003_results}Results of scanpath prediction on MIT1003.}
\end{center}
\end{table*}

\begin{figure*}[htp!]
\center
\scalebox{0.7}{
\begin{tabular}{ccccc}
\includegraphics[height = 20mm,width = 30mm]{figures/viz/GT/i1049420118.jpeg} &
\includegraphics[height = 20mm,width = 30mm]{figures/viz/GT/i1049420118_fixMap.jpg} &
\includegraphics[height = 20mm,width = 30mm]{figures/viz/sal_i1049420118.png} &
\includegraphics[height = 20mm,width = 30mm]{figures/scapathviz_gt/jcw.png}&
\includegraphics[height = 20mm,width = 30mm]{figures/viz/wimg_i1049420118.png} \\

\includegraphics[height = 20mm,width = 30mm]{figures/viz/GT/i1260655983.jpeg} &
\includegraphics[height = 20mm,width = 30mm]{figures/viz/GT/i1260655983_fixMap.jpg} &
\includegraphics[height = 20mm,width = 30mm]{figures/viz/sal_i1260655983.png} &
\includegraphics[height = 20mm,width = 30mm]{figures/scapathviz_gt/ya.png}&
\includegraphics[height = 20mm,width = 30mm]{figures/viz/wimg_i1260655983.png}\\

Stimuli &
Ground truth saliency map &
Predicted saliency map &
Ground truth scanpath &
Predicted scanpath \\

\end{tabular}}
\caption{\label{fig:mit1003_viz}Results of scanpath and saliency maps on MIT1003.}
\end{figure*}
\vspace{-3mm}

In order to evaluate the performance of the scanpath prediction branch, three metrics have been used:
\begin{itemize}
    \item MultiMatch (MM) \cite{Multimatch}: It compares the scanpaths through multiple criteria scores  (i.e. shape of the vectors, the difference in direction and angles between saccades, the length of the saccades, the position of the fixation points and duration between fixation points). In this study, only the first four criteria have been considered since the temporal aspect has not been yet integrated.
    \item NSS \cite{NSS}: It compares a fixation map generated from the predicted fixation points with the ground truth saliency map.
    \item Congruency \cite{congruency}: It measures the percentage of predicted fixation points within a thresholded saliency map.
\end{itemize}

Table \ref{tab:salicon_results} shows the results obtained on Salicon dataset. Our results are also compared to a set of representative state-of-the-art methods, including handcrafted-based models (i.e. Le Meur\cite{lemeur} and G-Eymol \cite{G-Eymol}) and deep learning-based models (i.e. PathGan \cite{pathgan}, DCSM-VGG and DCSM-ResNet \cite{DCSM}). As can be seen, our model achieves the highest values for the shape and direction criteria of the MultiMatch metric. It obtains a very close score to PathGan and G-Eymol on the length and the position criteria, respectively. However, our model obtains the state-of-art results on the mean score. For NSS, our model achieves the third place behind Le Meur and G-Eymol. However, this result can be justified by the fact that models like Le Meur use a predicted saliency map to predict fixation points and thus the fixation points are generally within the salient regions. For the Congruency, our model obtains the second best result close to Le Meur.

Table \ref{tab:mit1003_results} shows the results obtained on MIT1003 dataset which is used as a neutral comparison dataset (i.e. we did not fine-tune our model on it). For MultiMatch metrics, our model scores the highest on the shape and direction criteria, while it achieves a very close second place on the length criterion just behind Le Meur. For the position criterion, our model achieves a better score than Le Meur and G-Eymol, and reasonably close score to PathGan and DSCM-VGG. We still obtain the best overall score for the mean MultiMatch metric. For NSS and Congurency, our method obtains a lower score than Le Meur and G-Eymol but still outperforms PathGan.

In Fig \ref{fig:mit1003_viz}, we present scanpaths and saliency maps generated by our model as well as their corresponding ground truth scanpaths and saliency maps for two natural images of the MIT1003 dataset. As can be seen, the visualization demonstrates the efficiency of our model for both branches.
\vspace{-3mm}

\section{Conclusion}

In this paper, we proposed a novel fully convolutional neural network architecture for predicting saliency and scanpaths of natural images. Our model is composed of an encoder-decoder to predict the saliency and a second branch from which the scanpath is predicted. The latter takes advantage of the features provided at the bottle-neck of the designed saliency model. An attention module was also used to refine the image encoded feature space, improving thus the saliency and scanpath prediction.
The proposed model outperformed a good representative set of state-of-the-art models for saliency and scanpath prediction on both MIT1003 and Salicon datasets. Besides the quantitative comparison, the qualitative results prove the effectiveness of our model.

As future work, we plan to integrate the temporal dimension. We will also modify the loss function used to train the scanpath prediction branch in order to consider the saliency and the interdependence between both saliency and fixation points. Finally, we will test more advanced architectures instead of VGG.

\begin{comment}
\begin{figure}[htp!]
\center
\begin{tabular}{cccc}
\includegraphics[height = 25mm]{figures/viz/img_i1049420118.png}  &
\includegraphics[height = 25mm]{figures/viz/sal_i1049420118.png} \\
\includegraphics[height = 25mm]{figures/viz/img_i1260655983.png}&
\includegraphics[height = 25mm]{figures/viz/sal_i1260655983.png}
\end{tabular}
\caption{\label{fig:mit1003_viz}Results of scanpath and saliency maps on MIT1003.}
\end{figure}

\end{comment}

{\small
\bibliographystyle{IEEEbib}


\section{Introduction}
\begin{figure}
    \centering
\includegraphics[width=0.95\columnwidth,height=0.7\columnwidth]{modelACC.pdf}
    \caption{The comparison between AutoFormers and transformer-based, convolution-based and architecture-searched models, such as DeiT \cite{DeiT}, and ResNet \cite{he2016deep}.}
    \label{fig:acc}
    \vspace{-5mm}
\end{figure}
Vision transformer recently has drawn significant attention in computer vision because of its high model capability and superior potentials in capturing long-range dependencies.
Building on top of transformers~\cite{vaswani2017attention}, modern state-of-the-art models, such as ViT~\cite{dosovitskiy2020vit} and DeiT~\cite{DeiT}, are
able to learn powerful visual representations from images and achieve very competitive performance compared to previous convolutional neural network models~\cite{Survey1, Survey2}.

\begin{figure*}[th]
\centering
\begin{minipage}[t]{0.246\textwidth}
\centering
\includegraphics[width=1\textwidth]{depth.pdf}
\end{minipage}
\begin{minipage}[t]{0.246\textwidth}
\centering
\includegraphics[width=1\textwidth]{width.pdf}
\end{minipage}
\begin{minipage}[t]{0.246\textwidth}
\centering
\includegraphics[width=1\textwidth]{mlp_ratio.pdf}
\end{minipage}
\begin{minipage}[t]{0.246\textwidth}
\centering
\includegraphics[width=1\textwidth]{heads.pdf}
\end{minipage}
\caption{Adjust a baseline model with different embedding dimension ($e$), depth ($d$), MLP ratio ($r$), and number of heads ($h$) coefficients under the same training recipe, where MLP ratio( the ratio of hidden dimension to the embedding dimension in the multi-layer perceptron). We set the baseline model with $d=12, r=4, e=384, h=6$. \textbf{Note:} number of heads does not affect the model size and complexity if we fix the $Q$-$K$-$V$ dimension.
}

\label{fig:motivation}
\vspace{-4mm}
\end{figure*}

However, the design of transformer neural architectures is nontrivial. For example, how to choose the best network depth, embedding dimension and/or head number? These factors are all critical for elevating model capacity, yet finding a good combination of them is difficult.
As seen in Fig.~\ref{fig:motivation}, increasing the depth, head number and MLP ratio (the ratio of hidden dimension to the embedding dimension in the multi-layer perceptron) of transformers helps achieve higher accuracy at first but get overfit after hitting the peak value. Scaling up the embedding dimension can improve model capability, but the accuracy gain plateaus for larger models. These phenomenons demonstrate the challenge of designing optimal transformer architectures.

Previous works on designing vision transformers are based upon manual crafting, which heavily relies on human expertise and typically requires a deal of trial-and-error~\cite{dosovitskiy2020vit,DeiT,T2TViT}. There are a few works on automating transformer design using neural architecture search (NAS)~\cite{EvolvedTrans,HAT}.
However, they are all concentrated on natural language tasks, such as machine translation,
which are quite different from computer vision tasks. As a result, it is hard to generalize prior automatic search algorithms to find effective vision transformer architectures.

In this work, we present a new architecture search algorithm, named \emph{AutoFormer}, dedicated to finding pure vision transformer models. Our approach mainly addresses two challenges in transformer search. 1) How to strike a good combination of the key factors in transformers, such as network depth, embedding dimension and head number? 2)
How to efficiently find out various transformer models that fit different resource constraints and application scenarios?

To tackle the challenges, we construct a large search space covering the main changeable dimensions of transformer, including embedding dimension, number of heads, query/key/value dimension, MLP ratio, and network depth. This space contains a vast number of transformers with diverse structures and model complexities. In particular, it allows the construction of transformers to use different structures of building blocks, thus breaking the convention that all blocks share an identical structure in transformer design.

To address the efficiency issue, inspired by BigNAS \cite{bignas} and slimmable networks \cite{bignas, yu2018slimmable}, we propose a supernet training strategy called \emph{weight entanglement} dedicated to transformer architecture.
The central idea is to enable different transformer blocks to share weights for their common parts in each layer. An update of weights in one block will affect all other ones as a whole, such that the weights of different blocks are maximally entangled during training. This strategy is different from most one-shot NAS methods \cite{spos, fairnas, wu2019fbnet}, in which the weights of different blocks are independent for the same layer, as visualized in Fig.~\ref{fig:Difference}.

We observe a surprising phenomenon when using the proposed weight entanglement for transformer supernet training: \emph{it allows a large number of subnets in the supernet to be very well-trained, such that the performance of these subnets with weights inherited from the supernet are comparable to those retrained from scratch.}
This advantage allows our method to obtain thousands of architectures that can meet different resource constraints while maintaining the same level of accuracy as training from scratch independently. We give a detailed discussion in Section \ref{discussion} exploring the underlying reasons of weight entanglement.

We perform a evolutionary search with a model size constraint over the well-trained supernets to find promising transformers.
Experiments on ImageNet \cite{deng2009imagenet} demonstrate that our method achieves superior performance to the handcrafted state-of-the-art transformer models. For instance, as shown in Fig.~\ref{fig:acc}, with 22.9M parameters, Autoformer achieves a top-1 accuracy of 81.7\%, being 1.8\% and 2.9\% better than DeiT-S~\cite{DeiT} and ViT-S/16~\cite{dosovitskiy2020vit}, respectively. In addition, when transferred to downstream vision classification datasets, our AutoFormer also performs well with fewer parameters, achieving better or comparable results to the best convolutional models, such as EfficientNet~\cite{EfficientNet}.

In summary, we make three major contributions in this paper. 1) To our best knowledge, this work is the first effort to design an automatic search algorithm for finding vision transformer models. 2) We propose a simple yet effective framework for efficient training of transformer supernets. Without extra finetuning or retraining, the trained supernet is able to produce thousands of high quality transformers by inheriting weights from it directly. Such merit allows our method to search diverse models to fit different resource constraints. 3) Our searched models, \ie, AutoFormers, achieve the state-of-the-art results on ImageNet among the vision transformers, and demonstrate promising transferability on downstream tasks.

\begin{figure*}[!t]
    \centering
    \includegraphics[width=0.9\textwidth]{overview.pdf}
    \caption{\textbf{Left:}  The overall architecture of the AutoFormer supernet. Note that transformer blocks in each layer and depth are dynamic. The parts in solid lines mean they are chosen while those in dashed lines are not. \textbf{Right:} The detailed transformer block in an AutoFormer. We search for the best block of optimal embedding dimension, number of heads, MLP ratio, $Q$-$K$-$V$ dim in a layer. For more details about the search space, please refer to section \ref{search space}.}
    \label{fig:overview}
    \vspace{-5mm}
\end{figure*}

\section{Background}
Before presenting our method, we first briefly review the background of the vision transformer and one-shot NAS.

\subsection{Vision Transformer}

Transformer is originally designed for natural language tasks \cite{vaswani2017attention, Albert, devlin2019bert}. Recent works, such as ViT and DeiT \cite{dosovitskiy2020vit, DeiT}, show its great potential for visual recognition. In the following, we give the basic pipeline of the vision transformer, which serves as a base architecture of AutoFormer.

Given a 2D image, we first uniformly split it into a sequence of 2D patches just like tokens in natural language processing. We then flatten and transform the patches to $D$-dimension vectors, named patch embeddings, by either linear projection \cite{dosovitskiy2020vit} or several CNN layers \cite{T2TViT}. A learnable [class] embedding is injected into the head of the sequence to represent the whole picture. Position embeddings are added to the patch embeddings to retain positional information. The combined embeddings are then
fed to a \textit{transformer encoder} described below. At last, a linear layer is used for the final classification.

A transformer encoder consists of alternating blocks of \textit{multihead self-attention} (MSA) and \textit{multi-layer perceptron} (MLP) blocks. LayerNorm (LN) \cite{layernorm} is applied before every block, and residual connections after every block. The details of MSA and MLP are given below.

\textit{Multihead Self-Attention (MSA).}
In a standard self-attention module, the input sequence $z \in \mathbb{R}^{N \times D}$ will be first linearly transformed to queries $Q \in \mathbb{R}^{N \times D_h}$, keys $K \in \mathbb{R}^{N \times D_h}$ and values $V \in \mathbb{R}^{N \times D_h}$, where $N$ is the number of tokens, $D$ is the embedding dimension, $D_h$ is the $Q$-$K$-$V$ dimension. Then we compute the weighted sum over all values for each element in the sequence. The weights or attention are based on the pairwise similarity between two elements of the sequence:
	\begin{equation}
	\mathrm{Attention} (Q, K, V) = \mathrm{softmax}\Big(\frac{QK^T}{\sqrt{d_h}}\Big)V,
	\label{SA}
	\end{equation}
where $\frac{1}{\sqrt{d_h}}$ is the scaling factor.
Lastly, a fully connected layer is applied. Multihead self-attention splits the queries, keys and values into different heads and performs self-attention in parallel and projects their concatenated outputs.

\textit{Multi-Layer Perceptron (MLP).} The MLP block consists two fully connected layers with an activation function, usually GELU \cite{hendrycks2016gaussian}. In this work, we focus on finding optimal choices of the MLP ratios in each layer.

\subsection{One-Shot NAS}
\label{review}
One-shot NAS typically adopts a weight sharing strategy to avoid training each subnet from scratch~\cite{spos, Cream}. The architecture search space $\mathcal{A}$ is encoded in a supernet, denoted as $\mathcal{N}(\mathcal{A}, W)$, where $W$ is the weight of the supernet. $W$ is shared across all the architecture candidates, \ie, subnets ${\alpha\in \mathcal{A}}$ in $\mathcal{N}$.
The search of the optimal architecture $\alpha^{*}$ in one-shot NAS is usually formulated as a two-stage optimization problem. The first-stage is to optimize the weight $W$ by
\begin{equation}
    W_\mathcal{A} = \mathop{ \argmin_{W} } \mathcal{L}_{\emph{train}}(\mathcal{N}(\mathcal{A}, W)),
	\label{eq1}
\end{equation}
where $\mathcal{L}_\emph{train}$ represents the loss function on the training dataset. To reduce memory usage, one-shot methods usually sample subnets from $\mathcal{N}$ for optimization. The second-stage is to search architectures via ranking the performance of subnets ${\alpha\in \mathcal{A}}$ based on the learned weights in $W_\mathcal{A}$:
\begin{equation}
	\alpha^* = \mathop{\argmax}_{\alpha\in \mathcal{A}} \  \mathrm{Acc}_\emph{val} \left( \mathcal{N}(\alpha, w) \right),
	\label{eq2}
\end{equation}
where the sampled subnet $\alpha$ inherits weight $w$ from $W_\mathcal{A}$, and $\mathrm{Acc}_\emph{val}$ indicates the top-1 accuracy of the architecture $\alpha$ on the validation dataset. Since it is impossible to enumerate all the architectures ${\alpha\in \mathcal{A}}$ for evaluation, prior works resort to random search~\cite{randomNAS,understand_os}, evolution algorithms~\cite{real2019regularized,spos} or reinforcement learning~\cite{ENAS,tan2019mnasnet} to find the most promising one.%

\begin{figure}[!t]
\centering
\begin{minipage}[t]{0.49\columnwidth}
\centering
\includegraphics[width=1\textwidth]{spos_versus_auto.pdf}
\end{minipage}
\begin{minipage}[t]{0.49\columnwidth}
\centering
\includegraphics[width=1\textwidth]{val_spos_versus_auto.pdf}
\end{minipage}
\caption{\textbf{Left:} Comparison of training loss of supernet between weight entanglement and {classical weight sharing on ImageNet}. \textbf{Right:} Comparison of Top-1 Accuracy on ImageNet of subnets between weight entanglement and classical weight sharing during supernet training.}
\label{Fig:SPOS training}
\vspace{-3mm}
\end{figure}

\section{AutoFormer}

In this section, we first demonstrate that it is impractical to directly apply one-shot NAS for transformer search following classical weight sharing strategy \cite{spos}, using different weights for different blocks in each layer, because of the slow convergence and unsatisfactory performance. Then we propose the weight entanglement strategy for vision transformer to address the issues.
Finally, we present the search space and search pipeline.

\subsection{One-Shot NAS with Weight Entanglement}
\label{Weight Entanglement}

Prior one-shot NAS methods commonly share weights across architectures during supernet training while decoupling the weights of different operators at the same layer.
Such strategy performs well when used to search architectures over convolutional neural networks space~\cite{spos, ofa, fairnas, mobilenetv3, EfficientNet}.
However, in transformer search space, this classical strategy encounters difficulties.
1) Slow convergence. As shown in the Fig.~\ref{Fig:SPOS training} (left), the training loss of the supernet converges slowly.
The reason might be that the independent training of transformer blocks results in the weights being updated by limited times.
2) Low performance. The performances of subnets inheriting weights from the one-shot supernet, trained under classical weight sharing strategy, are far below their true performances of training from scratch (see the right part of Fig.~\ref{Fig:SPOS training}). This limits the ranking capacities of supernet. Furthermore, after the search, it is still necessary to perform additional retraining for the searched architectures since the weights are not fully optimized.
Inspried by BigNAS \cite{bignas} and slimmable networks \cite{yu2018slimmable, yu2019universally},
we propose the weight entanglement training strategy dedicated to vision transformer architecture search. The central idea is to enable different transformer blocks to share weights for their common parts in each layer. More concretely, for a subnet $\alpha\in\mathcal{A}$ with a stack of $l$ layers, we represent its structure and weights as
\begin{equation}
 \left\{
\begin{aligned}
	\alpha & = (\alpha^{(1)}, ... \alpha^{(i)}, ... \alpha^{(l)}), \\
	w & = (w^{(1)}, ... w^{(i)}, ... w^{(l)}), \\
\end{aligned}
\right.
\end{equation}
where $\alpha^{(i)}$ denotes the sampled block in the $i$-th layer and $w^{(i)}$ is the block weights. During architecture search, there are multiple choices of blocks in each layer. Hence, $\alpha^{(i)}$ and $w^{(i)}$ are actually selected from a set of $n$ block candidates belonging to the search space, which is formulated as
\begin{equation}
 \left\{
\begin{aligned}
	\alpha^{(i)} & \in \{ b^{(i)}_1, ... b^{(i)}_j, ... b^{(i)}_n \}, \\
	w^{(i)} & \in \{ w^{(i)}_{1}, ... w^{(i)}_{j}, ... w^{(i)}_{n} \}, \\
\end{aligned}
\right.
\end{equation}
where $b^{(i)}_j$ is a candidate block in the search space and $w^{(i)}_{j}$ is its weights.
The weight entanglement strategy enforces that different candidate blocks in the same layer to share as many weights as possible. This requires that, for any two blocks $b^{(i)}_j$ and $b^{(i)}_k$ in the same layer, we have
\begin{equation}
w^{(i)}_{j} \subseteq w^{(i)}_{k} \ \ \mathrm{or} \ \
w^{(i)}_{k} \subseteq w^{(i)}_{j}.
\end{equation}
Such within layer weight sharing makes the weight updates of $w^{(i)}_{j}$ and $w^{(i)}_{k}$ entangled with each other. The training of any block will affect the weights of others for their intersected portion, as demonstrated in Fig.~\ref{fig:Difference}. This is different from the classical weight sharing strategy in one-shot NAS, where the building blocks in the same layer are isolated. In other words, in classical weight sharing, for any two blocks $b^{(i)}_j$ and $b^{(i)}_k$, we have $w^{(i)}_{j} \cap w^{(i)}_{k} = \emptyset$.

\begin{figure}[!t]
    \centering
    \includegraphics[width=0.45\textwidth]{Difference.pdf}
    \caption{Classical weight sharing versus weight entanglement.}
    \label{fig:Difference}
    \vspace{-4.6mm}

\end{figure}

Note that the proposed weight entanglement strategy is dedicated to work on homogeneous building blocks, such as self-attention modules with different numbers of heads, and multi-layer perceptron with different hidden dimensions.
The underlying reason is that homogeneous blocks are structurally compatible, such that the weights can share with each other.
During implementation, for each layer, we need to store only the weights of the largest block among the $n$ homogeneous candidates. The remaining smaller building blocks can directly extract weights from the largest one.

Equipped with weight entanglement, one-shot NAS is capable of searching transformer architectures in an efficient and effective fashion, as demonstrated in Fig.~\ref{Fig:SPOS training}.

Compared with classical weight sharing methods, our weight entanglement strategy has three advantages. 1) \textit{Faster convergence}. Weight entanglement allows each block to be updated more times than the previous independent training strategy. 2) \textit{Low memory cost}. We now only need to store the largest building blocks' parameters for each layer, instead of all the candidates in the space. 3) \textit{Better subnets performance}. We found that the subnets trained with weight entanglement could achieve performance on par with those of training from scratch.

\subsection{Search Space}
\label{search space}
We design a large transformer search space that includes five variable factors in transformer building blocks: embedding dimension, $Q$-$K$-$V$ dimension, number of heads, MLP ratio, and network depth, as detailed in Tab.~\ref{tab:Search Space} and Fig.~\ref{fig:overview}.
All these factors are important for model capacities. For example, in attention layers, different heads are used to capture various dependencies. However, recent works \cite{sixheads, voita2019analyzing, bertlook} show that many heads are redundant.
We thereby make the attention head number elastic so that each attention module can decide its necessary number of heads. On the other hand, since different layers have different capacities on feature representation, the varying hidden dimensions in layers might be better than the fixed sizes when used for constructing new models. Moreover, AutoFormer adds new $Q$-$K$-$V$ dimension into the search space and fixes the ratio of the $Q$-$K$-$V$ dimension to the number of heads in each block. This setting makes the scaling factor $\frac{1}{\sqrt{d_h}}$ in attention calculation invariant to the number of heads, stabilizing the gradients, and decouples the meaning of different heads. Besides, we use MLP ratio and embedding dimension together to decide the hidden dimension in each block, which enlarges the search space than using fixed values.

Following one-shot NAS methods, we encode the search space into a supernet.
That is, every model in the space is a part/subset of the supernet.
All subnets share the weights of their common parts. The supernet is the largest model in the space, and its architecture is shown in Fig.~\ref{fig:overview}.
In particular, the supernet stacks the maximum number of transformer blocks with the largest embedding dimension, $Q$-$K$-$V$ dimension and MLP ratio as defined in the space.
During training, all possible subnets are uniformly sampled, and the corresponding weights are updated.

According to the constraints on model parameters, we partition the large-scale search space in to three parts and encode them into three independent supernets, as elaborated in Tab.~\ref{tab:Search Space}.
Such partition allows the search algorithm to concentrate on finding models within a specific parameter range, which can be specialized by users according to their available resources and application requirements.

Overall, our supernets contains more than $1.7 \times 10^{16}$ candidate architectures  covering a wide range of model size.

\begin{table}[!t]
	\centering
	\small
	\resizebox{\columnwidth}{!}
	{
		\begin{tabular}{l|ccc}
			\toprule[1pt]
			&  Supernet-tiny & Supernet-small &  Supernet-base \\
			\midrule[1pt]
			Embed Dim & (192, 240, 24) & (320, 448, 64)  & (528, 624, 48)\\
			$Q$-$K$-$V$ Dim & (192, 256, 64) & (320, 448, 64) & (512, 640, 64) \\
			MLP Ratio  & (3.5, 4, 0.5)  & (3, 4, 0.5)  & (3, 4, 0.5)  \\
			Head Num & (3, 4, 1) & (5, 7, 1) & (8, 10, 1)\\
			Depth Num & (12, 14, 1) & (12, 14, 1) & (14, 16, 1) \\
			\midrule[1pt]
			Params Range & 4 -- 9M & 14 -- 34M & 42 -- 75M\\
			\bottomrule[1pt]
		\end{tabular}
	}
		\vspace{1mm}
	\caption{The search space of AutoFormer. We set up three supernets to satisfy different resource constraints. Tuples of three values in parentheses represent the lowest
		value, highest, and steps. \textbf{Note:} the $Q$-$K$-$V$ dimensions, numbers of head  and MLP ratios are varied across layers.}
	\label{tab:Search Space}
	\vspace{-5mm}

\end{table}

\subsection{Search Pipeline}
\label{pipeline}

Our search pipeline includes two sequential phases.

\textit{Phase 1: Supernet Training with Weight Entanglement.}
In each training iteration, we uniformly sample a subnet $\alpha = (\alpha^{(1)}, ... \alpha^{(i)}, ... \alpha^{(l)})$ from the per-defined search space and update its corresponding weights $w = (w^{(1)}, ... w^{(i)}, ... w^{(l)})$ in the supernet's weight $W_\mathcal{A}$ while freezing the rest. Detailed algorithm is given in supplementary materials, Appendix A.

\textit{Phase 2: Evolution Search under Resource Constraints.}
After obtaining the trained supernet, we perform an evolution search on it to obtain the optimal subnets. Subnets are evaluated and picked according to the manager of the evolution algorithm. Our objective here is to maximize the classification accuracy while minimizing the model size. At the beginning of the evolution search, we pick $N$ random architecture as seeds. The top $k$ architectures are picked as parents to generate the next generation by crossover and mutation. For a crossover, two randomly selected candidates are picked and crossed to produce a new one during each generation.
For mutation, a candidate mutates its depth with probability $P_d$ first. Then it mutates each block with a probability of $P_m$ to produce a new architecture.

\begin{table*}[!t]
\begin{minipage}[b]{0.55\linewidth}
\centering
	\resizebox{\columnwidth}{!}
{
		\begin{tabular}{l|c c | c }
			\toprule[1pt]
			Search Method & Inherited & Retrain & Params \\
			\midrule[1pt]
			Random Search   & - & 79.4\% & 23.0M  \\
			Classical Weight Sharing + Random Search  & 69.7\% & 80.1\%  & 22.9M \\
			Weight Entanglement ~~~~~~+ Random Search    & 81.3\% & 81.4\%  & 22.8M \\
			Classical Weight Sharing + Evolution Search (SPOS\cite{spos}) & 71.5\%   & 80.4\% & 22.9M \\
			Weight Entanglement ~~~~~~+ Evolution Search (Ours)    &81.7\%   & 81.7\% & 22.9M \\
			\bottomrule[1pt]
		\end{tabular}
    }
    \vspace{5mm}
        \caption{Comparison of different search methods. The supernets are trained for 500 epochs, while the subnets are retrained for 300 epochs. Random search are performed three times and the best performance is reported.}
    \label{tab:Effctiveness}
\end{minipage}\hfill
\begin{minipage}[b]{0.43\linewidth}
\centering
\includegraphics[width=\textwidth]{random_vs_evo.pdf}
\captionof{figure}{The performance of subnets inheriting weights from supernet during search. Top 50 candidates until the current iteration are depicted at each search iteration.}
\label{fig:random_vs_evo}
\end{minipage}
\end{table*}

\subsection{Discussion}
\label{discussion}
\textit{Why does weight entanglement work?}
We conjecture that there are two underlying reasons. 1) Regularization in training. Different from convolution neural networks, transformer has no convolution operations at all. Its two basic components, MSA and MLP, employ only fully connected layers. Weight entanglement could be viewed a regularization training strategy for transformer, to some extent, similar to the effects of dropout \cite{dropout, dropconnect, li2020block}. When sampling the small subnets, corresponding units cannot rely on other hidden units for classification, which hence reduces the reliance of units. 2) Optimization of deep thin subnets. Recent works \cite{bapna2018training, wang2019learning} show that deep transformer is hard to train, which coincides with our observation in Fig.~\ref{fig:motivation}. This is because the gradients might explode or vanish in deep thin networks during backpropagation. Increasing the width of or “overparameterizing” the network will help the optimization \cite{li2017visualizing, du2018gradient, allen2019convergence, zhou2020go}. Our weight entanglement training strategy helps to optimize the thin subnets in a similar way. The gradients backwarded by wide subnets will help to update the weights of thin subnets. Besides, the elastic depth severs
similar effects to stochastics depth \cite{stochasticdepth} and deep supervision \cite{deepsupervised}, which supervise the shallow layers as well.

\section{Experiments}

In this section, we first present the implementation details and evolution search settings. We then analyze the proposed weight entanglement strategy and provide a large number of well-trained subnets sampled from supernets to demonstrate its efficacy. At last, we present the performance of AutoFormer evaluated on several benchmarks with comparisons with state-of-the-art models designed manually or automatically.

\subsection{Implementation Details}

\textit{Supernet Training}. We train the supernets using a similar recipe as DeiT \cite{DeiT}. The details are presented in Tab.~\ref{tab: Training settings}. Data augmentation techniques, including RandAugment \cite{cubuk2020randaugment}, Cutmix \cite{yun2019cutmix}, Mixup \cite{zhang2017mixup} and random erasing, are adopted with the same hyperparameters as in DeiT \cite{DeiT} except the repeated augmentation \cite{hoffer2019augment}. Images are split into patches of size 16x16.
All the models are implemented using PyTorch 1.7 and trained on Nvidia Tesla V100 GPUs.

\begin{table}[!t]
	\vspace{-2mm}

	\centering
	\footnotesize

	{
		\begin{tabular}{ccccc}
			\toprule[1pt]
			Epochs & Optimizer & Batch Size & LR & LR scheduler \\
			\midrule[.5pt]
			500 & AdamW & 1024 & 1{\emph e}-3 & cosine \\
			\midrule[1pt]
			Weight & Warmup  & Label  & Drop  & Repeated \\
			Decay & Epochs & Smoothing   &  Path & Augmentation \\
			\midrule[.5pt]
			5{\emph e}-2 & 20 & 0.1 & 0.1 & \ding{55}\\
			\bottomrule[1pt]
		\end{tabular}
	}
	\vspace{2mm}
	\caption{Supernet training settings. LR refers to learning rate.
	}
	\label{tab: Training settings}
    \vspace{-1mm}

\end{table}
\begin{table}[!t]

	\centering
	\resizebox{\columnwidth}{!}
    {
		\begin{tabular}{c|c c c c}
			\toprule[1pt]
			Model & Model Size & Inherited  & Finetune & Retrain \\
			\midrule[1pt]
		    AutoFormer-T  & 5.7M & 74.7\%  & 74.9\%  & 74.9\% \\
		    AutoFormer-S  & 22.9M & 81.7\%  & 81.8\%  & 81.7\% \\
		    AutoFormer-B  & 53.7M & 82.4\%  & 82.6\%  & 82.6\% \\

		    \bottomrule[1pt]
		\end{tabular}
	}
	\vspace{0.5mm}
	\caption{Comparison of subnets with inherited weights, fine-tuned (40 epochs) and trained from-scratch (300 epochs).}
	\label{tab:subtransformer}
    \vspace{-3mm}
\end{table}

\textit{Evolutionary Search.} The implementation of evolution search follows the same protocol as in SPOS \cite{spos}.
For a fair comparison, we reserve the ImageNet validation set for \textit{testing} and subsample 10,000 training examples (100 images per class) as the validation dataset.
We set the population size to 50 and number of generations to 20. Each generation we pick the top 10 architectures as the parents to generate child networks by mutation and crossover. The mutation probability $P_d$ and $P_m$ are set to 0.2 and 0.4.

\subsection{Ablation Study and Analysis}

\begin{table*}[!t]
	\caption{AutoFormer performance on ImageNet with comparisons to state-of-the-arts. We group the models according to their parameter sizes. Our AutoFormer consistently outperforms existing transformer-based visual models, being comparable to CNN models.$\dagger$: reported by \cite{DeiT}, $\star$: reported by \cite{xu2021coscale}.}
	\vspace{0.1cm}
	\centering
	\small
    {%
		\begin{tabular}{cc||cc||ccc||cc}
			\toprule[1.5pt]
			\multicolumn{2}{c||}{Models} & Top-1 Acc. & Top-5 Acc. &\#Parameters & FLOPs  & Resolution & Model Type & Design Type \\

			\midrule[1.5pt]

		    \multicolumn{2}{l||}{$\text{MobileNetV3}_{Large1.0}$ \cite{mobilenetv3}} & 75.2\% & - & 5.4M & 0.22G  &  $224^2$ & CNN & Auto \\
		    \multicolumn{2}{l||}{EfficietNet-B0\cite{EfficientNet}} & 77.1\% & 93.3\% & 5.4M & 0.39G &  $224^2$ & CNN & Auto \\
		    \multicolumn{2}{l||}{DeiT-tiny \cite{DeiT}} & 72.2\% & 91.1\% & 5.7M & 1.2G & $224^2$ & Transformer & Manual \\
		    \multicolumn{2}{l||}{\textbf{AutoFormer-tiny (Ours)}} & \textbf{74.7\%} & \textbf{92.6\%} &  \textbf{5.7M} & \textbf{1.3G}  & $224^2$ & Transformer & Auto \\

			\midrule[1.0pt]

		    \multicolumn{2}{l||}{$\text{ResNet50}^\star$ \cite{he2016deep}} & 79.1\% & - & 25.5M & 4.1G &  $224^2$ & CNN & Manual\\
		    \multicolumn{2}{l||}{$\text{RegNetY-4GF}^\dagger$ \cite{radosavovic2020designing}} & 80.0\% & - & 21.4M & 4.0G  & $224^2$ & CNN & Auto \\
		    \multicolumn{2}{l||}{EfficietNet-B4 \cite{EfficientNet}} & 82.9\% & 95.7\% & 19.3M & 4.2G & $380^2$ & CNN & Auto \\
		    \multicolumn{2}{l||}{BoTNet-S1-59 \cite{srinivas2021bottleneck}} & 81.7\% & 95.8\% & 33.5M  & 7.3G &  $224^2$ & CNN + Trans & Manual\\
		    \multicolumn{2}{l||}{T2T-ViT-14 \cite{T2TViT}} & 81.7\% & - & 21.5M  & 6.1G &  $224^2$ & Transformer & Manual\\
		    \multicolumn{2}{l||}{DeiT-S \cite{DeiT}} & 79.9\% & 95.0\% & 22.1M & 4.7G &  $224^2$ & Transformer & Manual\\
		    \multicolumn{2}{l||}{ViT-S/16 \cite{dosovitskiy2020vit}} & 78.8\% & - & 22.1M  & 4.7G &  $384^2$ & Transformer & Manual\\

			\multicolumn{2}{l||}{\textbf{AutoFormer-small (Ours)}} & \textbf{81.7\% }& \textbf{95.7\%} & \textbf{22.9M} & \textbf{5.1G}  &  $224^2$ & Transformer & Auto\\

			\midrule[1.0pt]

		    \multicolumn{2}{l||}{$\text{ResNet152}^\star$ \cite{he2016deep}} & 80.8\% & - & 60M & 11G  &  $224^2$ & CNN & Manual \\
		    \multicolumn{2}{l||}{EfficietNet-B7 \cite{EfficientNet}} & 84.3\% & 97.0\% & 66M & 37G  &  $600^2$ & CNN & Auto \\
		    \multicolumn{2}{l||}{ViT-B/16 \cite{dosovitskiy2020vit}} & 79.7\% & - & 86M & 18G &  $384^2$ & Transformer & Manual \\
		    \multicolumn{2}{l||}{Deit-B \cite{DeiT}} & 81.8\% & 95.6\% & 86M & 18G  &  $224^2$ & Transformer & Manual  \\
		    \multicolumn{2}{l||}{\textbf{AutoFormer-base (Ours)}} & \textbf{82.4\%}& \textbf{95.7\%} & \textbf{54M} & \textbf{11G}  &  $224^2$ & Transformer & Auto\\

		    \bottomrule[1.5pt]

		\end{tabular}
	}
	\vspace{-0.2cm}
	\label{tab:sota}
\end{table*}

\textit{The Efficacy of Weight Entanglement. }
We compare AutoFormer with random search and SPOS \cite{spos} (classical weight sharing) baselines to demonstrate the effectiveness of weight entanglement. For random search, we randomly pick up architectures from the search space to meet the model size constraints. For SPOS \cite{spos}, we adapt it to the transformer search space defined in Tab.~\ref{tab:Search Space} and keep the remaining configurations to be consistent with the original method.
In other words, in each layer of the SPOS supernet, the transformer blocks with different architecture arguments do not share weights. For example, in an MLP block, there are multiple choices of hidden dimensions. Each MLP choice has its own weights, being independent of each other.
After training the SPOS supernet, we apply the same evolution process to find the most promising architecture candidate and retrain it using the same setting as our AutoFormer.

\begin{figure}[t!]
    \vspace{-5mm}

    \centering
    \includegraphics[width=0.95\columnwidth]{Many_Points.pdf}
    \caption{Top-1 accuracy on ImageNet of AutoFormer and 1000 sampled high-performing architectures from the supernet-small with weight inherited from the supernet.}
    \label{fig:many points}
    \vspace{-5mm}

\end{figure}
Table~\ref{tab:Effctiveness} presents the comparisons on ImageNet. We can observe that:
1) After retraining,random search and SPOS are 2.3\% and 1.3\% inferior to our methods indicating the superiority of the proposed methods.
2) Without retraining, \emph{i.e.}, inheriting weights directly from the supernet, the weight entanglement training strategy can produce significantly better results than the classical weight sharing. The entangled weight can produce well-trained subnets, which are very close to the ones retrained from scratch. We conjecture the relatively inferior performance of SPOS in transformer space is mainly due to insufficient training. We also observe that if we train the supernet in SPOS for more epochs, the performance can be slowly improved. However, its training cost is largely higher than our proposed weight entanglement strategy.
Fig.~\ref{fig:random_vs_evo} plots the accuracy over the number of architectures sampled from the trained supernet during search. Top 50 candidates are depicted at each generation. It is clear that the evolution search on the supernet is more effective than the random search baseline.

\definecolor{brilliantrose}{rgb}{1.0, 0.33, 0.64}
\textit{Subnet Performance without Retraining}. We surprisingly observe that \emph{there are a large number of subnets achieving very good performance when inheriting weights from the supernets, without extra finetuning or retraining}. The \textcolor{blue}{blue} points shown in Fig.~\ref{fig:many points} represents the 1000 high-performing subsets sampled from the supernet-S. All these subsets can achieve top-1 accuracies ranging from 80.1\% to 82.0\%, exceeding the recent DeiT \cite{DeiT} and RegNetY \cite{radosavovic2020designing}. Such results amply demonstrate the effectiveness of the proposed weight entanglement strategy for one-shot supernet training.
Tab.~\ref{tab:subtransformer} shows that if we further finetune or retrain the searched subnets on ImageNet, the performance gains are very small, even negligible.
This phenomenon illustrates the weight entanglement strategy allows the subsets to be well-trained in supernets, leading to the facts that searched transformers do not require any retraining or finetuning and the supernet itself serves good indicator of subnets' ranking.

\begin{table*}[tp]
	\caption{AutoFormer results on downstream classification datasets. $\uparrow$ 384 denotes fine-tuning with 384×384 resolution.}
    \small
    \centering
	\resizebox{\textwidth}{!}
		{
		\begin{tabular}{l|cc|c|ccccc|cc}
				\toprule[1pt]
				Model & \#Param & FLOPs & ImageNet  & CIFAR-10 & CIFAR-100 & Flowers & Cars & Pets & Model Type & Design Type\\
				\midrule[0.75pt]
				$\text{Grafit ResNet-50}$ \cite{touvron2020grafit}& 25M & 12.1G & 79.6 & - & - & 98.2 & 92.5 & - & CNN & Manual\\
				$\text{Grafit RegNetY-8GF}$ \cite{touvron2020grafit}& 39M & 23.4G & 79.6  & - & - & 99.0 & 94.0 & - & CNN & Manual\\
				$\text{EfficientNet-B5}$ \cite{EfficientNet}& 30M & 9.5G & 83.6 & 98.7 & 91.1 & 98.5 & - & - & CNN & Auto\\
				\midrule[0.75pt]
				$\text{ViT-B/16}$  \cite{dosovitskiy2020vit} & 86M & 55.4G & 77.9 & 98.1 & 87.1 & 89.5 & - & 93.8 & Trans & Manual\\
				$\text{DeiT-B $\uparrow$ 384}$ \cite{DeiT}& 86M & 55.4G & 83.1 & 99.1 & 90.8 &  98.5 & 93.3 & - & Trans & Manual\\
				$\textbf{AutoFormer-S $\uparrow$ 384}$ & 23M & 16.5G & 83.4 & 99.1 & 91.1 & 98.8 & 93.4 & 94.9 & Trans & Auto \\

				\bottomrule[1pt]
			\end{tabular}
		}
	\label{tab:transfer}
\vspace{-0.2cm}
\end{table*}
\subsection{Results on ImageNet}
We perform the search of AutoFormer on ImageNet and find multiple transformer models with diverse parameter sizes. All these models inherit weights from supernets directly, without extra retraining and other postprocessing. The performance are reported in Tab.~\ref{tab:sota} and Fig.~\ref{fig:acc}. It is clear that our AutoFormer model families achieve higher accuracies than the recent handcrafted state-of-the-art transformer models such as ViT~\cite{dosovitskiy2020vit} and DeiT \cite{DeiT}. In particular, using $\sim$23M parameters, our small model, \emph{i.e.} AutoFormer-S, achieves a top-1 accuracy of 81.7\%, being 1.8\% and 2.9\% better than DeiT-S and ViT-S/16, respectively.

Compared to vanilla CNN models, AutoFormer is also competitive. As visualized in Fig.~\ref{fig:acc}, our AutoFormers perform better than the manually-designed ResNet \cite{he2016deep}, ResNeXt \cite{xie2017aggregated} and DenseNet \cite{huang2017densely}, demonstrating the potentials of pure transformer models for visual representation.

However, transformer-based vision models, including AutoFormer, now are still inferior to the models based on inverted residual blocks \cite{sandler2018mobilenetv2}, such as MobileNetV3 \cite{mobilenetv3} and EfficientNet \cite{EfficientNet}. The reason is that inverted residuals are optimized for edge devices, so the model sizes and FLOPs are much smaller than vision transformers.

\subsection{Transfer Learning Results}

\textbf{Classification.} We transfer Autoformer to a list of commonly used recognition datasets: 1) general classification: CIFAR-10 and CIFAR-100 \cite{cifar}; 2) fine-grained classification: Stanford Car~\cite{cars}, FLowers~\cite{flowers} and Oxford-III Pets~\cite{pets}. We follow the same training settings as DeiT~\cite{DeiT}, which take ImageNet pretrained checkpoints and finetune on new datasets.
Tab.~\ref{tab:transfer} shows the results in terms of top-1 accuracy: 1) Compared to state-of-the-art ConvNets, AutoFormer is close to the best results with a negligible gap with fewer parameters; 2) Compared to transformer-based models, AutoFormer achieves better or comparable results on all datasets, with much fewer parameters ($\sim$4x). In general, our AutoFormer consistently achieve comparable or better accuracy with an order of magnitude fewer parameters than existing models, including ResNet~\cite{touvron2020grafit}, RegNet~\cite{touvron2020grafit}, EfficientNet~\cite{EfficientNet}, ViT~\cite{dosovitskiy2020vit}, and DeiT~\cite{DeiT} .

\textbf{Distillation.} AutoFormer is also orthogonal to knowledge distillation (KD) since we focus on searching for an efficient architecture while KD focuses on better training a given architecture. Combining KD with AutoFormers by distilling hard labels from a RegNetY-32GF \cite{radosavovic2020designing} teacher could further improve the performance from 74.7\%/81.7\%/82.4\% to 75.7\%/82.4\%/82.9\%, respectively.

\section{Related Work}

\textit{Vision Transformer.}
Transformer is originally proposed for language modeling \cite{vaswani2017attention}, and recently applied in computer vision. It has shown promising potentials on a variety of tasks, such as recognition, detection and segmentation~\cite{DETR, dosovitskiy2020vit, liang2020polytransform}. A straightforward approach for using transformer in vision is to combine convolutional layers with the self-attention module~\cite{vaswani2017attention,wang2018non}. There has been progress in this direction in recent works, such as~\cite{ramachandran2019stand, zhao2020exploring, wang2020axial,huang2019ccnet}.

Most recently, Dosovitskiy \emph{et al.} introduce Vision Transformer (ViT) \cite{dosovitskiy2020vit}, a pure transformer architecture for visual recognition, without using any convolutions.
ViT stacks transformer blocks on linear projections of non-overlapping image patches.
It presents promising results when trained with an extensive image dataset (JFT-300M, 300 million images) that is not publicly available. The most recent DeiT~\cite{DeiT, T2TViT} models verify that large-scale data is not required.
Using only Imagenet can also produce a competitive convolution-free transformer.
However, existing visions of transformer models are all built upon manual design, which is engineering-expensive and error-prone. In this work, we present the first effort on automating the design of vision transformer with neural architecture search.

\textit{Neural Architecture Search.} There has been an increasing interest in NAS for automating network design~\cite{Survey,Survey2}. Early approaches search a network using either reinforcement learning~\cite{NASNet,zoph2016neural} or evolution algorithms~\cite{xie2017genetic,real2019regularized}. Most recent works resort to the one-shot weight sharing strategy to amortize the searching cost~\cite{randomNAS,ENAS,SMASH,spos}.
The key idea is to train a over-parameterized supernet model, and then share the weights across subnets. Among them, SPOS is simple and representative~\cite{spos}. In each iteration, it only samples one random path and trains the path using one batch data.
Once the training process is finished, the subnets can be ranked by inheriting the shared weights. However, most weight-sharing methods need an additional \emph{retraining} step after the best architecture is identified \cite{spos, blockwise, wu2019fbnet}.

Recent works, OFA~\cite{ofa}, BigNAS \cite{bignas} and slimmable networks \cite{yu2018slimmable, yu2019universally} alleviate this issue by training a once-for-all supernet. Despite the fact that AutoFormer shares similarities with these methods in the concept of training a one-for-all supernet, these methods are designed to search for convolutional networks rather than vision transformers, which have very different architecture characteristics. Specifically, AutoFormer considers the design of multihead self-attention and MLP, which is unique to transformer models, and gives dedicated design of search dimensions as elaborated in Sec.~\ref{search space}. Moreover, BigNAS adopts several well-crafted techniques, such as sandwich training, inplace distillation, regularization, \textit{etc}. OFA proposes a progressively shrinking approach by progressively distilling the full network to obtain the smaller subnets.  By contrast, AutoFormer is simple and efficient, achieving once-for-all training without these techniques, and could be easily extended to search for other vision transformer variants.

For transformers, there are few studies applying NAS to improve their architectures~\cite{EvolvedTrans,HAT}. These approaches mainly focus on natural language processing tasks. Among them, the most similar one to us is HAT \cite{HAT}. In addition to the difference between tasks, HAT requires an additional \emph{retraining} or \emph{finetuning} step after the search, while AutoFormer does not, which is the key difference. Another difference is the search space. HAT searches for an encoder-decoder Transformer structure, while ours is a pure encoder one. There are two concurrent works, \emph{i.e.}, BossNAS \cite{li2021bossnas} and CvT \cite{wu2021cvt}, exploring different search space from ours. BossNAS searches for CNN-transformer hybrids, while ours for pure transformers. CvT proposes a new architecture family and searches for the strides and kernel size of them. Due to the difference of search space, we do not compare them in this work.

In summary, our work differs from previous works in two main aspects. First, we propose a simple and efficient search methodology dedicated to the structure of vision transformers, which has not been well studied.
Second, the proposed weight entanglement training strategy enables the subnets in the supernet to be well trained, such that the subnets can inherit weights from the one-shot supernet directly, without extra finetuning or retraining.
To our best knowledge, this is the first work to train a once-for-all transformer in architecture search.

\section{Conclusion}
In this work, we propose a new one-shot architecture search method, AutoFormer, dedicated to transformer search. AutoFormer is equipped with the training strategy, \textit{Weight Entanglement}. Under this strategy, the subnets in the search space are almost fully trained. Extensive experiments demonstrate the proposed algorithm can improve the training of supernet and find promising architectures. Our searched AutoFormers achieve state-of-the-art results on ImageNet among vision transformers. Moreover, AutoFormers transfer well to several downstream classification tasks and could be further improved by distillation. In future work, we are interested in further enriching the search space by including convolutions as new candidate operators. Applying weight entanglement to convolution network search or giving the theoretical analysis of the weight entanglement are other potential research directions.

{\small
\bibliographystyle{ieee_fullname}