# Mining frequency-based sequential trajectory co-clusters

Yuri Santos<EMAIL_ADDRESS>Jônata Tyska  Vania Bogorny  Programa
de Pós-Graduação em Ciência da Computação, Florianópolis  Departamento de
Informática e Estatística, Florianópolis  Universidade Federal de Santa
Cataina, Santa Catarina, Brazil

###### Abstract

Co-clustering is a specific type of clustering that addresses the problem of
finding groups of objects without necessarily considering all attributes. This
technique has shown to have more consistent results in high-dimensional sparse
data than traditional clustering. In trajectory co-clustering, the methods
found in the literature have two main limitations: first, the space and time
dimensions have to be constrained by user-defined thresholds; second,
_elements_ (trajectory points) are clustered ignoring the trajectory sequence,
assuming that the points are independent among them. To address the
limitations above, we propose a new trajectory co-clustering method for mining
semantic trajectory co-clusters. It simultaneously clusters the trajectories
and their _elements_ taking into account account the order in which they
appear. This new method uses the _element_ frequency to identify candidate co-
clusters. Besides, it uses an objective cost function that automatically
drives the co-clustering process, avoiding the need for constraining
dimensions. We evaluate the proposed approach using real-world a publicly
available dataset. The experimental results show that our proposal finds
frequent and meaningful contiguous sequences revealing mobility patterns,
thereby the most relevant _elements_.

###### keywords:

Clustering analysis, Co-clustering, Trajectory analysis, Moving object
trajectory

††journal: Journal of LaTeX Templatesmytitlenotemytitlenotefootnotetext: The
source code will be published if accepted for publication

##  1 Introduction

The recent advances on sensor’s technology, the Internet of Things and mobile
devices have contributed to the explosion in mobility data generation. Such a
data can be collected in different ways such as GPS, wearables and sensor
networks, social networks, which enables trajectory recording of humans,
vehicles, animals, etc [1, 2]. The capability of analysing spatio-temporal
sequences, also called moving object trajectories, benefits a wide range of
applications and services, including traffic planning [3], animal behaviour
analysis [4], location-aware advertising [5], social recommendations [6],
medical diagnosis [7], to name just a few works.

The analysis of these data is the subject of several data mining techniques
as, for instance, classification [8], clustering [9], frequent-pattern mining
[10]. A common challenge when dealing with mobility data is to find useful
patterns while properly considering the sequence information [11, 12]. Cluster
analysis is one of the main categories of data mining tasks. It is a widely
used technique in exploratory data analysis for outlier detection,
summarization, segmentation, etc [13]. Traditional clustering strategies are
well known in the literature for producing a global analysis and considering
all attributes in the clustering process. An example is the well-known
algorithm k-means [14]. Over the years, with the increase of data volume and
heterogeneity, employing clustering methods has become more challenging since
a high number of attributes and sequential data can increase the computational
complexity and affect the cluster results consistency. This well-known problem
is called curse of dimensionality [15].

To overcome this challenge, co-clustering approaches can be used, as they
simultaneously cluster rows and columns of a matrix [16] without exploring all
the possible row-columns combinations. Co-clustering deals with the curse of
dimensionality problem by clustering the main data dimension, the objects
(rows), while applying dimensionality reduction techniques on the other
dimension, the features (columns). The focus relies on finding subsets of
objects and attributes that can represent submatrices (co-clusters) [17]. In
order to accomplish, efficient strategies are needed, since discovering all
significant co-clusters in a given matrix is proved as an NP-hard challenging
problem [18].

Different trajectory co-clustering approaches were proposed to deal with
trajectory data regarding the spatial dimension [19, 4, 3], space and time
[20], or _semantics_ [21, 22, 23]. However, these approaches have two main
limitations. First, the space and time dimensions are constrained using
thresholds, which limits the method’s capacity to find patterns. For instance,
thresholds or grids are used to assess the distance/similarity between spatial
locations as well as using time windows or time-slices to divide the temporal
dimension. Second, elements (trajectory points) are clustered ignoring the
trajectory sequence, assuming that the points are independent among them. This
ignores the fact that the order in which the _elements_ appear on a trajectory
have an important meaning. Noting this gap in the literature, we propose a new
trajectory co-clustering method called SS-OCoClus for mining semantic
trajectory co-clusters dealing with these two limitations. The new method uses
the elements frequency to identify candidate co-clusters, and then checks the
_element_ order in these candidates. Besides, it uses an objective cost
function that automatically drives the co-clustering process, avoiding the
need for thresholds that constrain dimensions.

We hypothesize that the order of visited elements in a sequence, together with
its overall frequency are important to reveal mobility patterns and hidden
user behaviors. In order to make this type of co-clustering analysis
computational feasible, we use the insight of combining overall frequency and
the _elements_ order for efficiently finding order-aware co-clusters.
Sequences composed by low frequency _elements_ are not considered seeking
computational efficiency. We assume that sequences formed by high-frequency
_elements_ are more meaningful, since they often represent the preference for
visiting specific places, or relevant trajectory dynamics repeated over time.
Therefore, we suppose that analyzing only the most visited _elements_ will
provide a higher probability of identifying order-aware co-clusters that
represent relevant patterns. We evaluate SS-OCoClus on a dataset from the
Foursquare social network [24] to demonstrate its validity and efficacy. Once
the trajectory co-clustering methods in the literature do not take into
account the _elements_ order, we show the number of relevant co-clusters,
grouped _elements_ and the overall entropy of our clustering results. In
summary, we make the following contributions:

  * 1.

Address the current trajectory co-clustering limitation that does not consider
the order of the _elements_ in trajectories. So, we propose an incremental
trajectory co-clustering method to find trajectory co-clusters giving their
most similar points. Instead of dealing with sparse and highly-dimensional
matrix, our approach incrementally identifies frequent sequences to form
candidate co-clusters;

  * 2.

Make use of both the _elements_ order and their frequency information to
discover useful mobility patterns that are visualized with the alluvial
diagram;

  * 3.

Identify similar mobility patterns over semantic locations, enabling cluster
objects with the same behaviour even when they pass in different areas and
move at different times.

The remainder of this work is organized as follows. The basic concepts and
related works are presented in Section 2. Section 3 presents the details of
our method. Section 4 presents the clustering results of our proposal.
Finally, the conclusion and further research directions of our work are
presented in Section 5.

##  2 Basic Concepts and Related Works

In this section we present the basic concepts to guide the reader throughout
this paper. We start by providing basic definitions for semantic trajectory ,
defined according to [25], co-clustering, and a comprehensive understanding on
the state-of-art related methods.

###  2.1 Basic Concepts

###### Definition 1

Semantic Trajectory ST: A semantic trajectory ST is a time ordered sequence of
elements $ST=\langle e_{1},e_{2},\ldots e_{n}\rangle$, where each element
$e_{i}$ has a set of attributes {$d_{1}$,$d_{2}$,…,$d_{l}$} characterizing it
according to $l$-dimensions.

Semantics is any type of information associated to mobility data other than
spatial location and time. Several semantic attributes can be added to the
_elements_ such as the activity, the category of the POI, the weather
condition, etc. A dataset with $N$ sequences can be represented as a matrix
$D$ with $N$ rows and $M$ columns, where each entry of $D$ represents an
element of a sequence. An element $t_{ij}$ of $D$ ($1\leq i\leq N$ and $1\leq
j\leq M$) is equal to the number of times that the $j$-th element occurred in
the $i$-th sequence. Co-clustering is the grouping task of finding $K$ co-
clusters in $D$ where each co-cluster is formed by a subset of rows and
columns [17]. A subset of rows $I$ can be represented as a binary vector of
length $N$, where $I_{i}=1$ indicates that the $i$-th row is present in $I$.
Similar to that, a subset of columns $J$ with $J_{j}=1$ indicates that the
$j$-th column is present in $J$. More formally, a co-cluster can be defined as
follows:

###### Definition 2

Co-cluster C: Let $D$ be a matrix, $I$ be the subset of rows, $J$ be the
subset of columns; a co-cluster $C$ is defined as $C=\langle I,J\rangle$. The
entries $c_{ij}$ of co-cluster $C$ are formed by the outer product of its
subsets $I$ and $J$. Thus, a co-cluster $C$ can represent a submatrix of $D$.

We also make use of the overlap coefficient [26]. Formally, it is defined as
follows:

###### Definition 3

Overlap Coefficient Oc: Given two sets $A$ and $B$, the overlap coefficient is
defined as the size of intersection of $A$ and $B$ over the size of the
smaller set between $A$ and $B$.

###  2.2 Related Works

Sankaranarayanan and Davis [19] proposed a mutual information co-clustering
method that simultaneously clusters the start and end locations of the
pedestrian trajectories. This approach is limited to the paired analysis once
it clusters the start and end locations with similar probability in the
matrix. Shahan [4] proposed a co-clustering method to find co-clusters with a
fuzzy strategy that groups objects with a lagged (delay) pattern. This
approach cannot deal with semantic data and cluster the attributes regardless
of the visited order, thereby overlooking hidden mobility patterns. Mohamed et
al. [3] used a co-clustering method to group trajectories and road segments in
the context of the road network. However, this approach focus on identifying
similar trajectories with common road segments regardless of the visited order
in the sequence.

Han et al. [20] proposed a framework designed for criminal investigations by
employing a spectral co-clustering approach on access trajectories in social
networks. This approach does not group the trajectories, and it uses the
spatial and temporal dimensions independently to identify groups of user IDs.
Besides that, it does not deal with semantics, the visited order in the
trajectories, and constrains the temporal dimension using a time window.

Arian et al. [21] used a co-clustering method to group users and activities
from the origin-destination location of moving objects. Once it groups users
instead of trajectories, the approach cannot find movement patterns in the
trajectories. Besides, it groups the _elements_ regardless of the visited
order in the trajectories, therefore, misinterpreting the mobility patterns.
Wang et al. [22] used a sparse bilinear decomposition and a sparse multi-
linear decomposition to find co-clusters in vessel trajectories. The multi-
linear decomposition using tensor groups the regions, time-slices, and ship
type in the set of trajectories. Besides, this method does not consider the
sequence in the trajectories, and it constrains the temporal dimension. Hu et
al. [23] proposed a co-clustering method based on Nonnegative Matrix Tri-
factorization for grouping users and POIs. This method focuses on grouping the
POIs regardless of the visited order in the trajectory. Besides, it constrains
the time dimension, which misinterprets the movement patterns.

##  3 Trajectory Co-clustering Approach

In this section we present SS-OCoClus, a order-aware frequency based co-
clustering method for semantic trajectories. SS-OCoClus finds candidate co-
clusters based on frequent sequential _elements_ that are then evaluated to
keep the most relevant candidates as the semantic co-clusters. Furthermore,
the proposed method uses a cost function and an overlap threshold to evaluate
the candidate co-clusters generated for each frequent sequence found in the
dataset. In the following we present the method definitions in section 3.1 and
the method details in section 3.2.

###  3.1 Main definitions

SS-OCoClus forms candidate co-clusters by testing each _element_
incrementally. It starts with the most frequent _elements_ and then expands
the sequence size by adding one frequent _element_ at a time. More formally, a
candidate co-cluster is defined as follows:

###### Definition 4

Candidate Co-cluster CC: Let $seq$ be a sequence of elements, $EM$ be the
elements mapping inverted index, and $TM$ be the trajectories mapping inverted
index, a candidate co-cluster $CC$ is a tuple $CC=\langle
S_{TM},S_{seq}\rangle$, where $S_{seq}$ is a sequence of elements that exist
in $TM$ with intersection in $EM$, and $S_{TM}$ is a subset of trajectories
indices that contains the sequence $S_{seq}$.

SS-OCoClus evaluates each candidate co-cluster to keep only the most relevant
ones as the semantic trajectory co-clusters. The candidates relevance can be
defined in terms of the number of trajectories, cost value, or both as the
reference. The measured relevance is compared with a given statistical metric,
that can be the average or the $z$-score. More formally, the semantic co-
cluster is defined as follows:

###### Definition 5

Semantic Co-cluster SC: An order-aware semantic trajectory co-cluster SC is a
candidate co-cluster CC with the relevance not smaller than the used
statistical metric. Thus, the semantic co-cluster SC is a subset of
trajectories (objects) and elements (attributes), where the elements represent
a frequent contiguous (sub) sequence in the dataset.

Supposing that there will be several candidate co-clusters in a dataset, it is
not a trivial task to manually define thresholds, such number of rows or
columns, to generate candidate co-clusters. Besides, the optimality of a
candidate can be expressed as an objective function $\mathcal{F}(I,J)$ that
can rank it. Such common functions when performing co-clustering use the logic
of perimeter $\mathcal{F}(I,J)=|I|+|J|$ or area
$\mathcal{F}(I,J)=|I|\times|J|$ [27]. Similarly, Lucchese et al.[28] proposed
a cost function that combines the perimeter and area into one general function
to mine frequent patterns binary datasets.

Inspired by the work of Lucchese et al.[28], we adapted their cost function
for tackling order-aware co-clustering. We consider the number of overlapped
_elements_ instead of counting the number of false positives (matrix entries
equal to 0 present in a pattern) and false negatives (matrix entries equal to
1 not present in a pattern) as noise data. More formally, the number of
overlapped _elements_ $Cov$ is defined as follows:

###### Definition 6

Overlapped Elements $Cov$: Given the set of candidate co-clusters $\Phi$ and
the candidate co-cluster CC, the number of overlapped elements $Cov$ is
defined as the number of intersected elements between CC and $\Phi$.

SS-OCoClus uses the cost function in order to evaluate the candidate co-
cluster generated by the frequent sequence. Thus, we define the new cost
function $\mathcal{F}$ as follows:

###### Definition 7

Cost Function $\mathcal{F}$: Let $\Phi$ be a set of co-clusters, $CC$ be a
candidate co-cluster, $|CC_{I}|$ be the size of a subset of trajectories,
$|CC_{J}|$ be the length of the co-cluster sequence, and $Cov$ be the number
of overlap elements between $CC$ and $\Phi$; a cost function $\mathcal{F}$ is
defined as follows:

$\mathcal{F}(CC,\Phi)=(|CC_{I}|+|CC_{J}|)-(|CC_{I}|\times|CC_{J}|)+Cov$ (1)

###  3.2 The proposed Method

Algorithm 1 shows the organization of our trajectory co-clustering method. It
receives three inputs: trajectory dataset $D$, maximum number of candidate co-
clusters $K$, an overlap threshold $\epsilon$ between co-clusters, statistical
metric $stat\\_met$, and relevance reference $rel\\_ref$. As output, it
returns a set of co-clusters $\Phi$. It starts by initializing the set of co-
clusters $\Phi$ (line 1), then the elements mapping ($EM$), trajectory mapping
($TM$) and _elements_ frequency ($Els\\_freq$) data structures (line 2) by
preprocessing $D$. Remember that $EM$ and $TM$ are inverted indexes, e.g.,
dictionaries for simplicity. The $EM$ structure stores in each $element_{m}$
the trajectories ID that contain the $element_{m}$, while $TM$ stores the
_elements_ order for each trajectory, and $Els\\_freq$ stores the overall
frequency for each $element_{m}$ in the dataset $D$. These data structures
form the basis for our method to identify frequent contiguous sequences in
$D$. The algorithm iterates at most $K$ times (line 3), as this parameter
determines the maximum number of candidate co-clusters to be extracted. Rather
than testing all the possible $2^{M}$ combinations of elements, these are
sorted by their frequency in descending order (from the most frequent to
least) to maximize the probability of identifying frequent sequences in the
clustering process (line 4). So, we avoid to test all combinations by focusing
on the high frequencies. Next, the subset of trajectories and _elements_ are
initialized as empty (line 5) to form the candidate co-clusters $CC$ and
$CC^{*}$ (line 6). These candidates are used to store the identified frequent
sequence pattern.

1

Input : Trajectory dataset $D$, Max number of candidate co-cluster $K$,
Overlap threshold $\epsilon$, Statistical metric $stat\\_met$, and Relevance
reference $rel\\_ref$

Output : Set of co-clusters $\Phi$

2

3$\Phi\leftarrow\\{\emptyset\\}$

4 $EM,TM,Els\\_freq\leftarrow initializeData(D)$

5 for  _candidate_iter = 0 to K_ do

$sort(Els\\_freq,desc)$

// descending order

$I,J\leftarrow[\emptyset]$

// subset of trajectories and elements

$CC^{*}\leftarrow CC,CC\leftarrow\langle I,J\rangle$

// co-clusters

$sequence\\_cc\leftarrow[\emptyset]$

// cluster sequence

6 $Els\\_queue\leftarrow queue(Els\\_freq)$

/* step to find a candidate */

7 for  _i = 0 to Els_queue.length_ do

8 $el\\_p\leftarrow Els\\_queue.pop()$

9 $sequence\\_cc.append(el\\_p)$

10 $Els\\_queue.append(el\\_p)$

11 $Els\\_to\\_test\leftarrow Els\\_queue.length$

/* step to expand candidate sequence */

12 while  _Els_to_test >0_ do

13 $el\\_q\leftarrow Els\\_queue.pop()$

14 $Els\\_queue.append(el\\_q)$

15 $CC^{*}\leftarrow candidateCC(sequence\\_cc,el\\_q,EM,TM)$

16 if  _$\mathcal{F}$($CC^{*},\Phi$) $\leq$ $\mathcal{F}$($CC,\Phi$) $\And
max(Oc(CC^{*},\Phi))\leq\epsilon$_ then

17 $CC\leftarrow CC^{*}$

18 $Els\\_to\\_test\leftarrow Els\\_queue.length$

19 $sequence\\_cc.append(el\\_q)$

20

21 else

22 $Els\\_to\\_test$ -= 1

23

24

25 if  _$CC==\emptyset$_ then

$sequence\\_cc.pop()$

// test the next el_p

26

27 else

break

// candidate identified

28

29

30 if  _$\mathcal{F}(CC,\Phi)\geq 0$_ then

/* keep the most relevant candidates */

31 $prune(\Phi,stat\\_met,rel\\_ref)$

break

// No relevant candidates anymore

32

33 else

$\Phi.append(CC)$

// store the candidate

$Els\\_freq.update(CC)$

// update frequencies

34

35

36

return _$\Phi$_

Algorithm 1 order-aware co-clustering

SS-OCoClus uses the element frequency to identify frequent sequences, assuming
that for a sequence to be frequent, the _elements_ that belong to the sequence
will also be frequent as a priori principle [29]. The method creates a queue
$Els\\_queue$ using the elements frequency (line 8) aiming to expand the
candidate co-cluster sequence. SS-OCoClus starts adding the _element_ $el\\_p$
in the co-cluster sequence (line 10) to test it with the next _element_ in the
queue ($el\\_q$). The method tries to expand the frequent sequence while the
_elements_ queue does not reach its end, when there is no _element_ to
test(line 14). Then, the element $el\\_q$ is dequeued (line 15) and it is
added to the end of the queue for further analysis (line 16). SS-OCoClus uses
the $candidateCC$ function to identify frequent sequences by expanding the
candidate co-cluster sequence $sequence\\_cc$ with the element $el\\_q$
regarding the intersection of each _element_ in $EM$ and the order-aware of
each trajectory in $TM$ (line 17). If the frequent sequence exits, its pattern
is used as a candidate co-cluster.

The $candidateCC$ function tries to form two frequent sequences: (i) one
sequence in the form of $sequence\\_cc\rightarrow el\\_q$, and (ii) another
sequence in the form of $el\\_q\rightarrow sequence\\_cc$ (we use
$\rightarrow$ to mean from A to B). These sequences can represent a pattern
formed by a subset of trajectories and elements of $D$. From that, given the
$sequence\\_cc$ and $el\\_q$ that form the sequence of elements, the
_elements_ map $EM$, and the trajectories map $TM$, the $candidateCC$ function
returns the frequent sequence pattern with the smallest cost value
representing the candidate co-cluster. Next, it checks if the candidate co-
cluster $CC^{*}$ cost value is smaller than the candidate co-cluster $CC$ and
if its maximum overlap coefficient $Oc$ does not exceed the overlap threshold
$\epsilon$ (line 18). If this condition is respected the method performs as
follows: the candidate co-cluster is accepted, and SS-OCoClus updates $CC$ by
replacing it with $CC^{*}$ (line 19); reassign the counter number with the
queue length (line 20); update the candidate co-cluster sequence (line 21).
Otherwise, it decrements the counter number of _elements_ to test (line 23).

After checking all _elements_ in the queue trying to expand the candidate co-
cluster sequence (line 14), if the candidate $CC$ is empty (line 24) the
method removes the _element_ $el\\_p$ (line 25) and repeats the loop (line 9)
to test the next $el\\_p$ _element_ in the sequence. Otherwise, it stops
searching for new candidates (line 27). Next, the method checks if the
candidate $CC$ does not have the minimum cost value to accept it as a
candidate co-cluster (line 28). The method identifies it automatically thanks
to the cost function $\mathcal{F}$ stated in Definition 7.

Considering the candidate $CC$, if it does not obtain a minimum cost value
(line 28), SS-OCoClus prunes the set of candidates to keep the most relevant
candidates as the semantic co-clusters $SC$ in $\Phi$ (line 29). For that, SS-
OCoClus allows the user to specify the relevance reference $rel\\_ref$, where
it can consider the number of trajectories, cost value, or both. Besides, the
user can choose between two statistical metrics $stat\\_met$ to prune the
candidate result: first, in terms of the average; and second, in terms of the
number of deviations ($z$-score). After this, the method returns the most
relevant semantic co-clusters (line 34) regarding the relevance reference
$rel\\_ref$ and the statistical metric $stat\\_met$. However, if candidate
$CC$ has a minimum cost value, it is appended to the set of candidates co-
clusters $\Phi$ (line 32), and the $Els\\_freq$ is updated regarding the $CC$
(line 33). SS-OCoClus updates $Els\\_freq$ decrementing the _element_
frequency in the $Els\\_freq$ by counting the times that an _element_ appears
in the co-cluster sequence and multiplies by the number of trajectories in the
candidate. Thus, the process for finding candidate co-clusters is repeated at
most $K$ times, but it also stops when the one last analysed candidate does
not reduce the cost function at a minimum value.

##  4 Experimental Evaluation

In this section we evaluate the proposed method over a real trajectory dataset
with characteristics aiming to demonstrate the efficacy and usefulness of SS-
OCoClus on finding order-aware co-clusters. We use three $z$-score values (-1,
0, and 1) as the minimum threshold to keep the most relevant candidates.
Besides, using $z=1$ keeps candidates with high number of trajectories and
small cost value reducing the number of cluster. Thus, due to space
limitation, we focus on presenting the clustering results considering $z=1$.
The experiments are performed in a machine with a processor Intel i7-7700
3.6GHz, 16 GB of memory, and operational system Windows 10 64bits.

###  4.1 Datasets

Table 1: Datasets description (averages reported in the format avg$\pm$std).

Dataset |  Num. of trajectories |  Num. of unique Elements |  Num. of users |  Avg. # of traj. per user |  Avg. traj. length per user
---|---|---|---|---|---
FS-NYtop193 | 3079 | 491 | 193 | 15.95$\pm$6.33 | 20.52$\pm$8.06
FS-NYtop81 | 1749 | 437 | 81 | 21.59$\pm$6.09 | 22.81$\pm$9.66
FS-NYtop10 | 352 | 310 | 10 | 35.2$\pm$4.4 | 32.23$\pm$15.46

Table 2: Co-clustering result for each dataset over different candidate
reference using $z=1$. Average and coefficient of variation are in the form
AVG[CV%] and we assume the absolute value of CV.

Dataset |  Relevance reference |  Number of co-clusters |  AVG number of trajectories |  AVG cost |  Number of elements |  Sequence length |  AVG number of users |  Overall entropy
---|---|---|---|---|---|---|---|---
FS-NYtop193 | Trajectory | 69 | 67.46 [60] | -41.3 [102.1] | 32 | 2.09 [13.39] | 24.71 [42.65] | 6.31
Cost▲ | 49 | 75.04 [61.55] | -55.37 [78.49] | 28 | 2.29 [26.63] | 25.65 [48.49] | 5.06
Both | 77 | 62.88 [64.67] | -40.3 [99.42] | 36 | 2.21 [23.52] | 22.96 [49.65] | 6.45
FS-NYtop81 | Trajectory | 53 | 54.08 [60.5] | -34.53 [99.32] | 25 | 2.11 [14.99] | 16.68 [39.44] | 5.89
Cost▲ | 34 | 61.97 [63.88] | -47.97 [77.11] | 34 | 2.32 [29] | 15.35 [49.58] | 4.16
Both | 57 | 52.21 [63.54] | -34.35 [96.48] | 29 | 2.21 [25.05] | 15.77 [45.68] | 5.94
FS-NYtop10 | Trajectory | 22 | 22.59 [34.83] | -19.68 [50.15] | 21 | 2.5 [31.2] | 2.18 [47.24] | 1.02
Cost▲ | 27 | 18.22 [53.01] | -21.89 [39.74] | 26 | 3.22 [34.16] | 1.70 [61.76] | 0.83
Both | 33 | 18.39 [48.12] | -19.42 [49.07] | 28 | 3 [36.66] | 1.79 [56.42] | 1.02
Cost▲: It uses the other corresponding side of $z$-score, i.e., -1 when $z$=1 and vice-versa. |  |

SS-CoClus is evaluated over three datasets extracted from the Foursquare NY
dataset [24], as detailed in Table 1. It shows the total number of
trajectories, the number of unique _element_ values, the number of users, the
average number and length of trajectories per user. This dataset contains
check-ins of users collected from April 2008 to October 2010. Furthermore, it
is composed by weekly trajectories of check-ins for each user, given the whole
set of check-ins.The Foursquare API111https://developer.foursquare.com/
provided the semantic information related to the POI: category (root-type),
subcategory (type), place name (poi), and price (a numeric classification);
the Weather Wunderground API222https://www.wunderground.com/weather/api/
provided the weather conditions. We select the POI subcategory (type) to
generate the trajectory sequences for all three datasets which contains 491
unique _elements_. It is an intermediate dimension of semantic POI
information, i.e., it is not too specific as the place name dimension and it
is not too general as the category dimension.

###  4.2 Result and Analysis

We consider that an _element_ is frequent if its frequency is equal or higher
than the average. Therefore, the number of unique _elements_ considered as
frequent are, respectively, 58, 88, and 93 for the datasets FS-NYtop10, FS-
NYtop81, and FS-NYtop193. Table 2 presents the co-clustering results
considering seven characteristics: (i) the relevance reference; (ii) the
number of final co-clusters regarding the candidate reference; (iii) the
average number of trajectories; (iv) the average cost value; (v) the number of
unique clustered _elements_ ; (vi) the average sequence length; (vii) the
average number of unique users in the co-clusters; and (x) the overall entropy
of the set of co-clusters. The number of trajectories and the cost value are
inversely proportional. So, we combine both using the other corresponding side
of the $z$-curve when the reference is the cost value. For example, if $z$
equals 1, it is set to -1 for the cost value reference and vice-versa. Thus,
Table 2 shows the trajectory co-clustering results over different candidate
reference using $z=1$.

In FS-NYtop193, the number of co-clusters are 69, 49, and 77 for trajectory,
cost, and both, respectively. For FS-NYtop81, the number of co-clusters are
53, 34, and 57 for trajectory, cost, and combine, respectively. In FS-NYtop10,
the number of co-clusters are 22, 27, and 33 for trajectory, cost, and both,
respectively. Using the cost as reference identifies the smallest number of
co-clusters in FS-NYtop193 and FS-NYtop81. It means that these co-clusters
have the highest balance between the number of trajectories and the sequence
length. Regarding the clustered _elements_ , we may notice that less than 50%
of the _elements_ are relevant to identify frequent sequences and forming
semantic co-clusters. For example, SS-OCoClus uses 93 _elements_ to identify
the co-cluster in FS-NY193. However, the maximum number of unique _elements_
in the final result was 36 when pruning the candidates using both trajectories
and the cost as reference. Therefore, 36 _elements_ are relevant and
contributes to identify 77 semantic co-clusters. Furthermore, in FS-NYtop81
dataset, considering the trajectory, cost and combine references, the number
of unique clustered _elements_ are 25, 34, and 29, respectively. In the same
way, for the FS-NYtop10 dataset, the number of unique clustered _elements_ are
21, 26, and 28, respectively.

It can be seen in Table 2 that the majority of the average sequence length
values are less than 3 _elements_ , and only in the FS-NYtop10 dataset was
identified an average equal or greater than 3. Using the cost as the co-
cluster reference leads to the discovering of co-clusters with long sequences
without discarding many trajectories. Besides, in this dataset, we may infer
that it is not common to have long frequent mobility patterns. In addition,
the coefficient of variation of the sequence length between co-clusters
considering all datasets spans from 13.39% up to 36.66%. Such variation within
the clustering shows that the co-clusters are heterogeneous regarding the
sequence length. Another observation is the high heterogeneity between co-
clusters regarding the average number of unique users per cluster. It spans
from 39.44% to 61.76%, where the minimum value occurs in FS-NYtop81
considering 34 clusters, while the maximum value occurs in FS-NYtop10 with 27
clusters.

##  5 Conclusion

We proposed SS-OCoClus, a new trajectory co-clustering method that finds
frequent sequences regarding the order and frequency of the _elements_. The
main contribution of the new method is that it groups trajectories containing
a sequence of similar _elements_ that appear in the same order and that are
frequent along different trajectories. This is a novelty compared to available
trajectory co-clustering methods that only find groups of trajectories that
contain similar _elements_. The method is evaluated and validated on a real-
world semantic trajectory dataset. Furthermore, despite these initial results
were limited to analyzing only one semantic dimension, the new method can deal
simultaneously with multiple aspects of trajectories by concatenating
different dimensions. Moreover, SS-OCoClus is driven by a cost function that
allows identifying the number of co-clusters automatically. The experiments
and results quantitatively and qualitatively showed the efficacy and utility
of the proposed method.

It is noteworthy that clustering analysis, a common descriptive data mining
task, is often exploratory in nature[30, chapter 1]. So, based on the
experimental results, three main insights could be discovered: (i) on average,
the trajectory patterns do not have long sequences; (ii) SS-OCoClus shows that
a small number of _elements_ is relevant to identify sequences; and (iii)
using the frequency of the _elements_ allows finding frequent sequences
revealing different mobility patterns. We argue that these results are
interesting because they reveal behaviours that existing co-clustering methods
in the literature are unable to find.

After obtaining these first encouraging results, we envisage some future
directions of investigation. First, the final number of co-clusters depends on
the number of identified candidate co-clusters $K$, used by the cost function
to drive the clustering process. Instead of requiring it to be manually
specified by the user, we intend to test some statistical strategy for
automatically inferring the useful number $K$. Second, SS-OCoClus deals with
any type of sequential data, but when analyzing multiple aspects trajectories,
for dealing with multiple dimensions, it requires manually-defined dimension
concatenation. As another future work we will expand SS-OCoClus to
automatically find relevant dimensions in multiple aspect trajectories. Third,
SS-OCoClus prunes the set of candidates using statistical metrics and
candidate reference. This means that by using different hyperparameters,
different co-clustering results will be generated. Therefore, it might be
interesting to automatically test multiple statistical strategies to keep the
most relevant co-clusters, generating useful results without requiring a
priori user knowledge.

## Acknowledgments

This work was financed by the Brazilian agencies Coordenação de
Aperfeiçoamento de Pessoal de Nivel Superior - CAPES (Finance code 001),
Conselho Nacional de Desenvolvimento Científico e Tecnológico - CNPq, and
supported by the MASTER project that received funding from European
Commission’s Horizon 2020 research and innovation programme under the Marie
Sklodowska-Curie grant agreement N. 777695.

## References

  * [1] C. A. Ferrero, L. O. Alvares, V. Bogorny, Multiple aspect trajectory data analysis: research challenges and opportunities., in: GeoInfo, 2016, pp. 56–67.
  * [2] M. A. Beber, C. A. Ferrero, R. Fileto, V. Bogorny, Individual and group activity recognition in moving object trajectories, Journal of Information and Data Management 8 (1) (2017) 50–66.
  * [3] K. Mohamed, R. Guigourès, F. Rossi, M. Boullé, Co-clustering network-constrained trajectory data, in: Advances in Knowledge Discovery and Management, Springer, 2016, pp. 19–32.
  * [4] E. Shaham, D. Sarne, B. Ben-Moshe, Co-clustering of fuzzy lagged data, Knowledge and Information Systems 44 (1) (2015) 217–252.
  * [5] L. Guo, D. Zhang, G. Cong, W. Wu, K.-L. Tan, Influence maximization in trajectory databases, IEEE Transactions on Knowledge and Data Engineering 29 (3) (2016) 627–641.
  * [6] J. Bao, Y. Zheng, D. Wilkie, M. Mokbel, Recommendations in location-based social networks: a survey, GeoInformatica 19 (3) (2015) 525–565.
  * [7] S. Bayat, G. M. Babulal, S. E. Schindler, A. M. Fagan, J. C. Morris, A. Mihailidis, C. M. Roe, Gps driving: a digital biomarker for preclinical alzheimer disease, Alzheimer’s Research & Therapy.
  * [8] C. L. da Silva, L. M. Petry, V. Bogorny, A survey and comparison of trajectory classification methods, in: 2019 8th Brazilian Conference on Intelligent Systems (BRACIS), IEEE, 2019, pp. 788–793.
  * [9] G. Yuan, P. Sun, J. Zhao, D. Li, C. Wang, A review of moving object trajectory clustering algorithms, Artificial Intelligence Review 47 (1) (2017) 123–144.
  * [10] D. Wang, T. Miwa, T. Morikawa, Big trajectory data mining: a survey of methods, applications, and services, Sensors.
  * [11] P. Fournier-Viger, J. C.-W. Lin, R. U. Kiran, Y. S. Koh, R. Thomas, A survey of sequential pattern mining, Data Science and Pattern Recognition 1 (1) (2017) 54–77.
  * [12] L. Bermingham, I. Lee, Mining distinct and contiguous sequential patterns from large vehicle trajectories, Knowledge-Based Systems.
  * [13] A. Saxena, M. Prasad, A. Gupta, N. Bharill, O. P. Patel, A. Tiwari, M. J. Er, W. Ding, C.-T. Lin, A review of clustering techniques and developments, Neurocomputing 267 (2017) 664–681.
  * [14] K. Wagstaff, C. Cardie, S. Rogers, S. Schrödl, Constrained k-means clustering with background knowledge, in: Proceedings of the Eighteenth International Conference on Machine Learning, Morgan Kaufmann Publishers Inc., 2001, p. 577–584.
URL https://dl.acm.org/citation.cfm?id=645530.655669

  * [15] R. Xu, D. Wunsch, Survey of clustering algorithms, IEEE Transactions on neural networks 16 (3) (2005) 645–678.
  * [16] A. Salah, M. Nadif, Directional co-clustering, Advances in Data Analysis and Classification.
  * [17] S. C. Madeira, A. L. Oliveira, Biclustering algorithms for biological data analysis: a survey, IEEE/ACM transactions on computational biology and bioinformatics 1 (1) (2004) 24–45.
  * [18] Y. Cheng, G. M. Church, Biclustering of expression data., in: Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, Vol. 8, 2000, pp. 93–103.
  * [19] K. Sankaranarayanan, J. W. Davis, Learning directed intention-driven activities using co-clustering, in: 2010 7th IEEE International Conference on Advanced Video and Signal Based Surveillance, IEEE, 2010, pp. 400–407.
  * [20] X. Han, L. Wang, C. Cui, J. Ma, S. Zhang, Linking multiple online identities in criminal investigations: A spectral co-clustering framework, IEEE Transactions on information forensics and security 12 (9) (2017) 2242–2255.
  * [21] A. Arian, A. Ermagun, Y.-C. Chiu, Characterizing activity patterns using co-clustering and user-activity network, in: 2017 IEEE 20th International Conference on Intelligent Transportation Systems (ITSC), IEEE, 2017, pp. 1–6.
  * [22] J. Wang, C. Zhu, Y. Zhou, W. Zhang, Vessel spatio-temporal knowledge discovery with ais trajectories using co-clustering, The Journal of Navigation 70 (6) (2017) 1383.
  * [23] L. Hu, Y. Xing, Y. Gong, K. Zhao, F. Wang, Nonnegative matrix tri-factorization with user similarity for clustering in point-of-interest, Neurocomputing 363 (2019) 58–65.
  * [24] D. Yang, D. Zhang, V. W. Zheng, Z. Yu, Modeling user activity preference by leveraging user spatial temporal characteristics in lbsns, IEEE Transactions on Systems, Man, and Cybernetics: Systems 45 (1) (2014) 129–142.
  * [25] A. S. Furtado, D. Kopanaki, L. O. Alvares, V. Bogorny, Multidimensional similarity measuring for semantic trajectories, Transactions in GIS 20 (2) (2016) 280–298.
  * [26] M. Vijaymeena, K. Kavitha, A survey on similarity measures in text mining, Machine Learning and Applications: An International Journal 3 (2) (2016) 19–28.
  * [27] A. A. Melkman, E. Shaham, Sleeved coclustering, in: Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’04, Association for Computing Machinery, New York, NY, USA, 2004, p. 635–640.  doi:10.1145/1014052.1014132.
  * [28] C. Lucchese, S. Orlando, R. Perego, A unifying framework for mining approximate top-$k$ binary patterns, IEEE Transactions on Knowledge and Data Engineering 26 (12) (2013) 2900–2913.
  * [29] Y. Bastide, R. Taouil, N. Pasquier, G. Stumme, L. Lakhal, Mining frequent patterns with counting inference, ACM SIGKDD Explorations Newsletter.
  * [30] P.-N. Tan, M. Steinbach, V. Kumar, Introduction to data mining, Pearson Education India, 2016.


# PSViT: Better Vision Transformer via Token Pooling and Attention Sharing

Boyu Chen1, Peixia Li111footnotemark: 1, Baopu Li211footnotemark: 1, Chuming
Li3, Lei Bai1, Chen Lin4,
Ming Sun3, Junjie Yan3, Wanli Ouyang1
1 The University of Sydney, 2 BAIDU USA LLC,
3 SenseTime Group Limited, 4 University of Oxford
Equal contribution

###### Abstract

In this paper, we observe two levels of redundancies when applying vision
transformers (ViT) for image recognition. First, fixing the number of tokens
through the whole network produces redundant features at the spatial level.
Second, the attention maps among different transformer layers are redundant.
Based on the observations above, we propose a PSViT: a ViT with token Pooling
and attention Sharing to reduce the redundancy, effectively enhancing the
feature representation ability, and achieving a better speed-accuracy trade-
off. Specifically, in our PSViT, token pooling can be defined as the operation
that decreases the number of tokens at the spatial level. Besides, attention
sharing will be built between the neighboring transformer layers for reusing
the attention maps having a strong correlation among adjacent layers. Then, a
compact set of the possible combinations for different token pooling and
attention sharing mechanisms are constructed. Based on the proposed compact
set, the number of tokens in each layer and the choices of layers sharing
attention can be treated as hyper-parameters that are learned from data
automatically. Experimental results show that the proposed scheme can achieve
up to $6.6\%$ accuracy improvement in ImageNet classification compared with
the DeiT in [33].

##  1 Introduction

Deep neural network (DNN) has been the core of the recent popular artificial
intelligence (AI) wave. It greatly enhances the state-of-the-art (SOTA) for
many tasks in natural language processing (NLP) and computer vision (CV),
which are two major application fields of AI. Among them, transformer [34, 9,
19, 29] has found its almost ubiquitous applications in the field of NLP due
to its great advantage of long-range capture and parallelism capability
compared to the previous prevalent recurrent neural network (RNN).

Figure 1: Token pooling and attention sharing. (a) The original ViT. (b) Token
pooling (TOKEN POOL in the figure) for ViT, where the number of tokens (input
length) in the next layer can be smaller than the number of tokens in the
current layer, and the token dimension per token can increase. (c) Attention
map (ATT in the figure) sharing for ViT, where the attention at the previous
transformer layer is copied to the current layer.

Recently, transformer is reevaluated by researchers in the field of CV and
applied to solve some typical problems such as image generation [24] and image
classification [11, 33]. The flexible attention mechanism of the transformer
in the whole pipeline intrigued the emergence of many following works such as
object detection [4], image segmentation [36], and video instance segmentation
[37]. The inspiring achievements of the transformer in the above pioneering
works are turning the transformer into a capable alternative to the prevalent
convolutional neural network (CNN) in CV field.

In this paper, we find two redundancies in most vision transformers. Our first
observation is that the fixed number of tokens observed by the model produces
the redundant features at the spatial level. As shown in traditional CNNs
[42], deep neural networks tend to encode low-level information in shallow
layers and high-level information such as semantic features in deep layers. A
fixed number of tokens may be an improper design for this purpose, since the
fixed number of tokens may not be enough for low-level information encoding
and too redundant for high-level information encoding.

To better capture the semantic features as well as reducing the computation,
it is a common practice to downsample feature resolution in CNN as the layers
get deeper. As a counterpart in a transformer, the number of tokens should
have more flexibility to adjust itself based on different levels. To achieve
this, we propose the attention pooling mechanism for adapting token numbers at
different layers.

The second form of redundancy resides in the similarity of the attention maps
between adjacent layers. In ViT models, relations among all tokens are built
in the transformer encoder according to the input feature embeddings. However,
since feature embeddings between the neighboring layers change smoothly, the
learned attention between neighboring layers may be similar as Fig. 2 shows.
The strong similarity between attention at adjacent layers motivates us to
share the attention among adjacent layers. On the other hand, the attention
takes 43% computation and 33% the number of parameters in the transformer
layer. Sharing attention saves the computation required for obtaining
attention.

Figure 2: Attention maps from 6 different transformer layers. The attention
maps of layers 1 and 2 have high normalized correlation, _i.e_. 0.89.
Similarly for layers 6, 7 and layers 10, 11 with the normalized correlation
being 0.91.

Specifically, the number of tokens in each transformer layer and the setting
for attention sharing will affect the performance of transformer. While it is
intuitive for tuning token number and attention sharing to be effective, it is
challenging to reach an optimal design for vision tasks. Instead of relying on
heuristic human design for getting the optimal design, we can resort to a more
principled way by leveraging the recent success of Automated Machine Learning
(AutoML) [18]. Specifically, we first construct a set of possible choices,
called search space in AutoML, which consists of the possible design
combinations for token pooling and attention sharing. For token pooling, we
search its location in the network. Searching the locations of token pooling
is equal to setting the optimal numbers of layers at different stages (we
refer to the layers with the same number of tokens as a stage).

The choice of whether a layer shares the attention with its neighbour forms a
discrete optimization problem. Our objective is to find the optimal
configuration of attention sharing which minimizes the computational cost as
well as maximizing the performance. In this work, we apply Neural Architecture
Search to solve the configuration.

We treat these key factors in the network design as hyper-parameters and learn
these parameters from data with the AutoML method. The two differences between
the original ViT model and our proposed PSViT are shown as Fig. 1.

Our contributions can be summarized as follows:

  * •

We present a PSViT scheme with token pooling and attention sharing to devise a
better vision transformer that can effectively enhance the feature
representation ability and control the computation allocation flexibly

  * •

We propose a compact set of design choices for token pooling and attention
sharing, based on which the optimal design choice is learned by leveraging
off-the-shelf AutoML methods.

  * •

Comprehensive experimental results show that the proposed scheme has up to
6.6% accuracy improvement in ImageNet classification compared with the DeiT in
[33].

Figure 3: Pipeline of our proposed PSViT model. There are three stages in the
model, which are separated from the proposed token pooling layers. The token
pooling layers help to reduce the spatial size (from $L$ to $L/4$ in the
Figure) and increase the dimension of feature embedding. Each stage has
several layers (including the layer with independent or sharing attention).
The attention maps from different layers in the same stage have the same size.
We apply Global Average Pooling (GAP) to the last features and send the
generated vector to a classifier (CLS) for the final classification.

##  2 Related Work

Transformers for Vision. Transformer [34] was originally proposed to overcome
the limited attention range and unsuitability of RNN in NLP. It then quickly
gained popularity in the whole field of NLP. In the past few years, a new
trend of applying transformer in the field of CV is witnessed. And transformer
first found its application for low-level vision problem such as image
generation [24] and image super resolution [41]. Parmar _et al_. [24] advanced
image transformer to generate images through constraining the self-attention
mechanism only to local neighborhoods and achieved promising results. Yang _et
al_. [41] came up with a new texture transformer network for image super-
resolution, where the low resolution and reference images are formulated as
queries and keys in a transformer and obtained new SOTA for image super
resolution.

Later, transformer was extended to high-level vision problems such as object
detection [4, 44], image classification [11, 5] and so on. To overcome the
problem of some hand-designed components such as non-maximum suppression and
anchor generation in the typical object detection, a complete end-to-end
scheme (DETR) [4] based on transformer was proposed with impressive results.
However, DETR still suffers from low convergence. As such, Zhu _et al_. [44]
introduces Deformable DETR, in which attention modules only consider a small
set of key sampling points, leading to much faster training speed and better
performance especially for small objects. Dosovitskiy _et al_. [11] explicitly
defined the concept of Vision Transformer (ViT), and directly applied
transformer to image classification with on-par-with or even better
performance. Chen _et al_. [5] utilized a sequence transformer to auto-
regressively predict pixels with no need of 2D input structure to learn useful
representations for images. The notable results reported by them demonstrate
the attractive potential of transformers for unsupervised representation
learning.

Different from all the previous transformer based works in the field of CV, we
concentrate on the token pooling and attention sharing that are not touched
before. In addition, we apply the AutoML method to achieve this goal, which
makes our work distinct from the manual design of these previous works.

Automated Machine Learning (AutoML). Designing a better and efficient DNN is
worthwhile for all the tasks in CV. Previously, most researchers and engineers
in the field of DNN try to design better models based on heuristics and
experiences. Such a process tends to be very tedious. Fortunately, in the past
few years, a novel methodology of designing a better DNN model, that is,
AutoML, arises quickly. Currently, the AutoML methods for neural network
architecture design can be divided into three categories, reinforcement
learning (RL) based methods [45, 2, 32], neuro-evolutionary based methods [12,
15, 25] and differentiable methods [23, 40, 35].

RL based methods [45, 2] and neuro-evolutionary methods [22, 25] are good at
searching discrete architectures, but generally requires huge computational
cost in searching. To overcome the great computational burdens of RL and
evolutionary methods during the search, differentiable search methods [23, 40,
35] relaxed the discrete search space and applied SGD for searching. Then, it
received a lot of attention due to its great advantage of searching efficiency
[35], and it has been widely used in many computer vision problems such as
segmentation [21, 6] , object detection [7, 13, 14], model compression [10,
38, 28] and so on.

Inspired by the outstanding performance of AutoML for both CV and NLP, we also
utilize AutoML for better ViT models with the aim of boosting its performance
effectively. Specifically, the evolution based method of SPOS [15] is taken as
our hyper-parameters learning method due to its fast efficiency of the single
path in the supernet searching and training. Nevertheless, AutoML has not been
investigated for Transformer in image recognition and our search space of
token pooling and attention sharing has not been studied in AutoML for CV.

##  3 Method

First, we give a brief introduction about transformer in Section 3.1. Then, we
present the two essential mechanisms of our PSViT, including token pooling and
attention sharing, in Section 3.2. Finally, we introduce the enhanced PSViT
with AutoML method in Section 3.3.

###  3.1 Background about Transformer

Transformer [34] is built with stacked self-attention layers and feed-forward
neural networks.

Self-attention Layer. The self-attention layer utilizes the relevance or
interaction of one token to other tokens. The input of self-attention layer is
transformed into three different vectors, _i.e_. the query vector $q$, the key
vector $k$ and the value vector $v$, and their corresponding packing form from
different inputs are $Q$, $K$, $V$ respectively, we can calculate their
attention among different inputs by the following equation:

$\vspace{-4pt}Att(Q,K,V)=Softmax(\frac{Q\cdot(K^{T})}{\sqrt{d_{h}}})\cdot V,$
(1)

where $d_{h}$ is the number of features per token and $\cdot$ denotes matrix
multiplication. The equation above means that the self-attention can be
obtained by first computing the dot product of the query with all the keys,
_i.e_. $Q\cdot(K^{T})$. Then, they are normalized with the softmax function to
get attention scores. Finally, the attention scores are multiplied by the
value vector. As such, the output of each token becomes the weighted sum of
all the tokens in a sequence/image. To boost the performance of vanilla self-
attention, multi-head attention is further proposed by applying multiple
attention functions to the input.

Vision Transformer. Dosovitskiy _et al_. [11] proposed ViT which directly
applied the above transformer from NLP to the image classification task. They
divided an image into a sequence of flattening 2D tokens that are treated as
the inputs to transformer. A trainable linear projection was adopted for token
embeddings with the aim of yielding constant widths for different layers in a
transformer. Then, another learnable embedding is further applied to the
sequence of embedding tokens. In addition, 1D positional encoding is also
attached to the token embeddings to maintain the positional information. When
ViT is trained on large datasets, it can achieve a very impressive
classification accuracy of 88.36%.

Building upon this work, Touvron _et al_. [33] improved the ViT training speed
by introducing a novel teacher-student token distillation strategy specific to
transformers (DeiT), yielding competitive results on ImageNet without external
data as in ViT. We choose DeiT as our baseline model in this work for its
great training efficiency.

Table 1: Preliminary experiments on ImageNet about Token Dimension Settings for Each Stage. ‘Token Dimensions’ denotes the channel number of tokens for the three stages. Similarly for ‘Token Numbers’ and ‘Layer Numbers’. Model | DeiT-Tiny | Token Dimension1 | Token Dimension2
---|---|---|---
w/o Pooling | no Pooling | 2 Poolings | 2 Poolings
Token Dimensions | [192, 192, 192] | [192, 192, 192] | [192, 256, 384]
Token Numbers | [197, 197, 197] | [197, 99, 50] | [197, 99, 50]
Layer Numbers | [4, 4, 4] | [4, 8, 20] | [4, 4, 4]
FLOPS(G) | 1.3 | 1.3 | 1.3
Top1 Acc | 72.2% | 75.0% | 76.3 %

###  3.2 Token Pooling and Sharing for Transformer

Based on the above review and problem analysis for the current ViT, we propose
two mechanisms named token pooling and attention sharing to overcome the above
three issues for the goal of a better ViT.

####  3.2.1 Token Pooling

The token pooling mechanism adjusts the number of tokens for each stage as
Fig. 3 shows. When the network depth increases, we decrease the number of
tokens for removing spatial redundancy and increase the feature dimension for
accommodating more high-level features that should be different from each
other. There are two design options for the token pooling. The first one is
following the network design in [11], treating the image patches as 1D tokens
and utilizing the additional CLS token for the classification task. The other
one is removing the CLS token and keeping the image patches in a 2D array,
which is the same as the pooling strategy in most networks for computer vision
tasks, such as ResNet [17].

For the first design, similar to [43], we achieve token pooling by convolution
and maxpooling for the convenience of implementation. Different from [43] that
only decreases the number of tokens, our goal is to enhance the feature
representation ability. Therefore, the feature dimension is not changed in
[43] but will be changed in ours. Specifically, we first utilize 1D
convolution with a small kernel size to change the feature dimension (i.e.,
dimension of each token) and then decrease the number of tokens via 1D
maxpooling. We name our network with the above pooling strategy as PSViT-1D.
In the second strategy, we adopt a 2D convolutional layer with stride 2 for
token pooling, which is widely applied in many convolutional networks. Here,
we name the network with the second pooling strategy as PSViT-2D.

Simply adding a token pooling layer after each layer will decrease the model’s
representation ability expeditiously. Motivated by the principle of deep
networks in CV, such as VGGNet, ResNet and MobileNet, we add a pooling layer
after several layers and name the layers with the same token numbers as a
stage.

Investigation on Two Choices of Token dimension. To increase the
representation ability of the ViT while maintaining its computational overhead
in terms of FLOPS at the same time, we may have two choices to modify the
network structure: increasing token dimension while decreasing the token
number or keeping the tokens dimension and increasing the transformer layer
number. Based on these two choices, we conducted some preliminary experiments
with the 1D pooling strategy in Table 1, which shows that increasing the
feature dimensions while decreasing the number of tokens is a better choice.
Specifically, in the experiments, the baseline model fixes the feature size
while the ‘Dimension1’ scheme in Table 1 fixes the token dimensions and
decreases the token numbers through the stages. To balance the total
computation, several encoder layers are added. The ‘Dimension2’ scheme in
Table 1 increases the token dimensions while decreasing the token numbers.
These two schemes design the architectures following the principle that the
computation is uniformly distributed across the stages [20]. We can find in
Table 1, these two token dimension designs perform much better than the DeiT-
Tiny model which fixes the feature sizes through the whole network. The method
decreasing the token number while increasing the feature dimension
(‘Dimension2’) achieves the best performance.

Analysis on the Design Choices. In CV tasks, there are two characteristics.
_First_ , as discussed in Section 1, high-level features have redundancy at
spatial level. Therefore, it is reasonable to reduce the redundancy at the
spatial level by token pooling. This is supported by the results in Table 1,
where two token pooling design performs much better than the DeiT-Tiny model
without token pooling. _Second_ , low-level features could be few but high-
level features should be more. Different layers in a deep network encode
information of different levels. Low-level features, e.g. edges and textures,
at shallow layers can be few and can be shared for representing high-level
features. In contrast, high-level features, e.g. attributes or objects of
different viewpoints, at deeper layers are more difficult to be shared.
Therefore, most of the CNN designs, such as VGGNet [30], ResNet [17] and
MobileNet [26], follow the rule that deeper layers have higher feature
dimensions. This is also validated by the results in Table 1, where increasing
the feature dimension at the deeper layer in ‘Dimension2’ performs better than
fixing the feature dimension in ‘Dimension1’.

####  3.2.2 Attention Sharing

As shown in Fig. 2, the attention maps in continuous multi-attention layers
are similar. As one of the reasons, identity mapping is used in the
transformer, making a transformer layer function as the residual. In this
case, the main features, though changed by the residual, will not drastically
change. Therefore, the features in adjacent layers will be similar to each
other, leading to the attention maps among features similar to each other.
This similarity leads to redundancy. Hence, it is beneficial to apply some
sharing mechanisms so as to reduce redundancy and, at the same time, decrease
the computation.

Specifically, we achieve the goal of attention sharing through reusing the
attention calculation process between adjacent layers as shown in Fig. 1(c).
If a layer reuses the attention scores from its preceding layer, then we do
not calculate the attention scores as well as the $Q$ and $K$ in Eqn. (1). The
attention calculated at the preceding layer is used as the input attention of
this layer and the whole process of attention calculation in Eqn. (1) is
simplified to the dot product between $V$ and input attention scores.

Attention sharing can help to remove the redundancy of the attention map among
adjacent transformer layers. On the other hand, some adjacent layers might
have very different features and sharing their attention maps becomes not so
effective. Taking this into consideration, we should provide the flexibility
so that the whole ViT still has the choice of using the original multi-head
attention module without sharing attention maps. As such, we take the sharing
attention module as an optional choice to the original independent multi-head
attention module in designing the overall transformer architecture.

###  3.3 AutoML Enhanced Transformer

Recently, AutoML has greatly boosted the SOTA for many models in CV and NLP.
In this section, we also turn to AutoML for the goal of a better ViT.

####  3.3.1 Search Space for PSViT

As mentioned before, token pooling refers to the operation that decreases the
number of tokens at the spatial level and increases the channel number of
features per token, and such an operation may greatly affect the feature
representation ability. Hence, we specifically consider its different forms in
ViT. The design choices of each stage mainly include three factors: the number
of tokens $N_{t}$, the token dimension $N_{f}$, and the number of layers for
each stage $N_{b}$. To get an optimal choice for these three factors, we
construct a search space that has multiple choices for them. Each element in
the search space would lead to a new candidate network architecture for the
transformer.

In each layer, there are $S_{t}$ possible choices for the number of tokens,
$S_{f}$ possible choices for the token dimension, and $S_{s}$ possible choices
for using the attention maps for each map. For $L$ layers, the search space
considering only the token pooling would contain $(S_{t}\cdot S_{f}\cdot
S_{s})^{L}$ candidate designs. For example, when $S_{t}=4$, $S_{f}=4$,
$S_{s}=4$, and $L=36$, then there are about $1.1*10^{65}$ choices, about
$9.6*10^{52}$ times the size of SPOS method [15]. In comparison, SPOS has 4
choices in each layer, while this search space has 64 in each layer. This
search space is too large and has too many choices in each layer. It costs too
much time when searching algorithms are used for obtaining the best
architecture from this search space. Besides, too many choices in each layer
may make the existing fast searching algorithm not effective, as found in [8].
Therefore, we need to reduce the search space.

Our designs of the search space and reasons are as follows:

  * •

According to the analysis in Section 3.2.1, we increase the token dimension
but decrease the token numbers as the depth increases. This helps to reduce
the search space by removing the network architectures that do not fit this
rule.

  * •

Following the mature design of CNN, we constrain that multiple layers within a
stage have the same number of tokens and the same token dimension. To reduce
the search space and computation required by the searching algorithm, we only
use three stages of token pooling.

  * •

For the number of layers at each stage, we only consider the limited number of
layers to further reduce the search space and computation.

  * •

We provide flexibility to apply attention sharing or not for different layers.

Our supernet design for Representing the Search Space. If we consider the
number of layers and the setting for attention map sharing in each stage as
hyper-parameters for a network, then a natural choice for learning them is the
RL or EA based approaches, which are very slow in searching. Therefore, we
employ weight sharing based methods [3, 1] as our searching algorithm, which
requires defining a supernet to subsume all candidate architectures in the
search space. A possible design of supernet is shown in Fig. 4. There are
three stages in the supernet. A token pooling layer is placed between stages
to change the token number and features dimension. Each stage has six cells,
where a cell has three choices of paths, a basic transformer layer, two
sharing layers with the attention map of the first transformer layer being
copied to the second layer, and identity mapping. A candidate architecture
could choose one path out of three choices for each cell independently. With
the inclusion of identity mapping, the candidate network can have 0 (all cells
choosing the identity layer) to 36 (all cells choosing the sharing layers)
transformer layers. Such supernet design provides more feasibility to the
transformer architecture. For example, a candidate could only select basic
layers for all layers, which is equivalent to the transformer enhanced by two
token pooling layers. As another example, a candidate architecture could
select the sharing layers path for all the first 6 cells at the first stage
and select identity for the remaining cells, which has 12 transformer layers
with every two layers sharing attention map but without token pooling.

####  3.3.2 AutoML for the Searching

With the search space and supernet defined in section 3.3.1, we find the
optimal network architecture for the transformer using the SPOS [15], which is
briefly introduced below.

Training the supernet. The built supernet in section 3.3.1 includes all the
candidate networks. For each cell of the supernet, there are multiple choices.
By activating only one choice in each cell, a candidate network can be
constructed. During training, SPOS only selects one candidate network by
uniform sampling for each training iteration and updates the parameters of the
selected candidate network in the supernet. The candidate network will inherit
the trained parameters from the supernet and keep updating these parameters.
Once the supernet is trained, all the candidate networks can inherit the
weights from it without being trained from scratch for searching.

Searching from the trained supernet. After the supernet is trained, the best
candidate network architecture can be obtained by further applying the
evolutionary method to all the candidate networks in the supernet. More
details could be found in [15].

Figure 4: The architecture of our supernet. There are three stages, each stage
containing 6 cells. A cell has three choices of paths, a basic transformer
layer, sharing layers, and an identity layer. A candidate network has a single
path for each cell.

##  4 Experiments

In this section, we elaborate on the dataset, implementation details, and
experimental results to evaluate the performance of the proposed PSViT.

###  4.1 Datasets and Implementation Details

Experimental Dataset. To validate the effectiveness of the proposed PSViT, we
conduct experiments on image classification. We conduct all classification
experiments on the ImageNet 1000-class image classification dataset, which is
a widely used benchmark for validating network architecture design. This
dataset has about 1 million training data. Part of the training data is used
as the validation data. The training data without the validation data is used
for training the supernet. The validation data is used by the AutoML for
searching from the trained supernet.

Implementation Details. We choose the DeiT [33] mentioned before as our
baseline since it is the current SOTA for vision transformer in image
classification. DeiT has two major different versions, that is, the Small one
and the Tiny one, for efficient training, which are derived from the basic
version of DeiT-B that has 12 transformer layers, a fixed token dimension of
768, 12 heads, and feature dimension of each head $d_{h}$ being 64. The
differences between the Small one and the Tiny one are feature dimension and
head number. More details about the other related details for DeiT can be
found in [33]. We follow the framework of DeiT [33] to obtain the feature
embeddings, which are sent to transformer encoders for further processing. We
implemented our model based on PyTorch.

Training settings.  For the supernet training, mini-batch Nesterov SGD
optimizer with a momentum of 0.9 is adopted. The initial learning rate is set
to 0.2 and adjusted to 0 gradually by the cosine annealing learning rate
decay. We train the network with a batch size of 1024 and L2 regularization of
1e-4 for 100 epochs. Besides, the label smoothing is applied with a 0.1 smooth
ratio. For subnet searching, we use the same setting for the evolutionary
algorithm as that in [15] under the FLOPS constraint. Specifically, the
evolutionary algorithm samples $N_{s}=1000$ subnets with population size 50,
max iterations 20, and retaining top-10 models during the evolutionary search.
After the optimal subnet is found, we retrain the subnet. For retraining the
subnet, we utilize the same training setting as that in [33] due to its
efficiency.

Table 2: Comparison of ImageNet classification performance between different models. ‘Acc’ denotes the Top-1 accuracy and ‘*’ denotes the performance under our training setting, which is the same as that in DeiT [33]. Model | FLOPS(G) | Acc(%)
---|---|---
ResNet18 | 1.8 | 69.8
ResNet18∗ | 1.8 | 68.5
DeiT-Tiny | 1.3 | 72.2
PSViT-1D-Tiny | 1.4 | 77.4
PSViT-2D-Tiny | 1.3 | 78.8
ResNet50 | 4.1 | 76.1
ResNet50∗ | 4.1 | 78.5
X50-32x4d | 4.3 | 77.6
X50-32x4d∗ | 4.3 | 79.1
DeiT-Small | 4.6 | 79.6
PSViT-1D-Small | 4.9 | 80.7
PSViT-2D-Small | 4.4 | 81.6
X101-64x4d | 15.6 | 79.6
X101-64x4d∗ | 15.6 | 81.5
ViT-Base | 17.6 | 77.9
DeiT-Base | 17.6 | 81.8
PSViT-1D-Base | 18.9 | 82.6
PSViT-2D-Base | 15.5 | 82.9

###  4.2 Classification Results

For the classification task, we compare our two type searched models, PSViT-1D
and PSViT-2D with two widely applied models, ResNet [17] and ResNext [39], and
the SOTA pure transformer vision model DeiT [33]. More specifically, ResNet18
and ResNet 50 are shown in Table 2 since they are provided in [33] and they
have similar FLOPs as DeiT-Tiny and DeiT-Small respectively, as pointed out in
[33]. Moreover, ResNetXt50-32x4d and ResNetXt101-64x4d that improved ResNet by
aggregating the residual module are also included for comparison due to their
outstanding performance in image classifications. For a fair comparison, the
above corresponding models trained on our machine using our training settings
(the same as DeiT) are further represented with a symbol of * in the table.
The results for ViT-Base in Table 2 is copied from [11]. Note that using the
training setting of DeiT for both ViT and DeiT will make ViT and DeiT having
the same accuracy because the only difference between DeiT and ViT is the
training setting.

Table 2 shows the experimental results comparing our searched models with
other methods under different computation budgets. We can find that under
similar FLOPS, our models achieve better classification accuracy. For example,
the accuracy of our searched 1D/2D model under 1.3 GFLOPS is more than 5% / 6%
higher (we use absolute accuracy improvement instead of relative improvement
in this paper) than DeiT-Tiny with similar FLOPS and more than 7% / 8% higher
than the ResNet18, whose FLOPS is 1.4 times of ours. Such huge improvements in
terms of better classification accuracy and fewer FLOPS make the proposed
PSViT a more attractive and powerful competitor to the recent ViT and DeiT.

For ResNet50, ResNetXt, and DeiT-Small, our corresponding improved model
obtained by the PSViT-1D also outperforms them respectively by a significant
margin of 2.2%, 1.6%, and 1.1%. The PSViT-2D is 0.9% better than the PSViT-1D
with fewer FLOPS. While for the large model comparisons among ResNetXt-101,
DeiT-Base, and our base one, our respective classification gain is more than
1% for the PSViT-2D-Base model.

All the above three results for image classification show the effectiveness of
the proposed PSViT scheme. We attribute the gain of our searched models to the
two key parts advanced in this work: the proposed token pooling module that
can more effectively capture different levels of image features, and the
attention sharing mechanism that flexibly adapts the computational cost for
different transformer layers, achieving a better trade-off between accuracy
and model redundancy.

Table 3: ImageNet top-1 classification accuracy for models with different mechanisms, _i.e_. attention sharing, token pooling, and using AutoML or manual design for these two factors. Attention | Token | AutoML | FLOPS | acc-1D | acc-2D
---|---|---|---|---|---
Sharing | Pooling |  | (G) | % | %
|  |  | 1.3 | 72.2 | 72.2
✓ |  |  | 1.3 | 73.8 | -
| ✓ |  | 1.3 | 76.3 | 76.7
✓ | ✓ | ✓ | 1.3 | 77.4 | 78.8
Table 4: Token Number Setting based on PSViT-1D. Tiny/8 and Tiny/16 have differences in the input token numbers. To ensure Tiny/8 and Tiny/16 have similar FLOPs, token dimension and number of heads in the multi-head attention are adjusted correspondingly. Similarly for Small/8 and Small/16. ‘Token Dimensions’ denotes numbers of features per token for the three stages, similarly for ‘Token numbers’. ‘Num. heads’ denotes the number of heads in the multi-head attention for the three stages. Model | Tiny/8 | Tiny/16 | Small/8 | Small/16
---|---|---|---|---
Token Dimensions | [64, 144, 192] | [192, 288, 384] | [144, 256, 384] | [288, 512, 768]
Num. heads | [1, 3, 3] | [3, 6, 6] | [3, 4, 6] | [6, 8, 12]
Token Numbers | [785, 393, 197] | [197, 99, 50] | [785, 393, 197] | [197, 99, 50]
Params(M) | 3.8 | 15.6 | 13.9 | 53.8
FLOPS(G) | 1.5 | 1.3 | 4.9 | 4.0
Top1 Acc | 72.71% | 77.40% | 80.70 % | 78.32 %

###  4.3 Ablation Study

To have a better understanding of the proposed PSViT, we carry out some
ablation studies in this section, which are detailed as follows. All
experimental results are conducted on ImageNet using the same training setting
mentioned in Section 4.1.

Effectiveness of Token Pooling, Attention Sharing, and AutoML. First of all,
we evaluate our proposed mechanism through simple manually designed models as
in Table 3. We first devise the ViT model with attention sharing between two
adjacent layers. To balance the computation, we add additional layers at the
end of the original model to reach similar FLOPS. The attention sharing
improves the accuracy by 1.6%. Then, we evaluate the proposed token pooling
with the setting of ‘Token Dimension2’ described in Table 1. Token pooling
improves the performance of the model significantly, that is, from 72.2% to
76.3% for PSViT-1D and to 76.7% for PSViT-2D.

Moreover, we study the effectiveness of AutoML. We utilize SPOS method to
search for an optimal architecture under the FLOPS constraint, considering
both token pooling and attention sharing. The supernet for the SPOS is shown
in Fig. 4. As shown in Table 3, there is obvious performance improvement of
1.1%/2.1% for PSViT-1D/PSViT-2D, which demonstrates the efficacy of the
utilized AutoML method of SPOS.

Token Number Settings. As we mentioned before, the hyper-parameters about
attention pooling have multiple choices. We evaluate the different settings as
in Table 4. Since we follow the principle of increasing token dimensions while
decreasing token numbers, the only hyper-parameters should be the
initial/final token numbers. We evaluate two types of token numbers based on
PSViT-1D, corresponding to the way that input images are split. For a model
with input token having size $16\times 16$ (models with ‘/16’), the
initial/final tokens number is 197/50 while the model with input token size
being $8\times 8$ (models with ‘/8’) has 785/197 initial/final tokens. The
model Tiny/16 is our searched model as mentioned and other models are obtained
through scaling up (Small/16) or tuning the initial token numbers (Tiny/8,
Small/16). For the Tiny models, the model with fewer token numbers performs
much better. The Tiny model with more tokens has too many tokens with lower
feature dimension in the final stage which leads to poor representation
ability. Different from Tiny model, the Small model with more tokens achieves
better performance. The reason is that the token dimensions are enough for the
small model and the performance of the small model with few tokens drops due
to the possible overfitting caused by the superfluous parameters.

Attention Sharing Settings. We further study different attention sharing
paradigms. And the experimental results based on 1D pooling are shown in Table
5. In the table, ‘sharing 2’ means every 2 adjacent layers share the same
attention. ‘sharing 3’ denotes every 3 adjacent layers share the same
attention, _i.e_. more layers sharing the same attention. We can clearly see
that applying sharing can yield obvious improvements in classification
accuracy compared to the vanilla ViT that does not share attention (‘no
sharing’ in Table 5), with a promising margin of 1.6%, and 0.9% respectively
for sharing in 2 layers and 3 layers. Sharing between 2 layers achieves better
performance than sharing among 3 because features will change more when going
through 3 layers and the attention may be different in 3 layers. For a better
performance, we select sharing within 2 layers as our network design element
in the supernet.

Figure 5: Visualization of features for DeiT and our PSViT. Images in the 1st and 4th columns are from ImageNet.  Table 5: ImageNet top-1 classification accuracy for different sharing settings. ‘no sharing’ denotes the network without sharing attention. ‘sharing 2’ and ‘sharing 3’ respectively denote every 2 and 3 adjacent transformer layers share the same attention map. model | FLOPS (G) | acc-1D (%)
---|---|---
no sharing | 1.3 | 72.2
sharing 2 | 1.3 | 73.8
sharing 3 | 1.3 | 73.1

###  4.4 Visualization

Visualization. In Fig. 5, we show the visualization of learned features from
DeiT (the 2nd and 5th columns) and our PSViT (the 3rd and 6th columns). We
utilize the Grad-CAM in [27] to show where is ‘important’ for predictions. We
can find that our PSViT can focus on a more complete region-of-interests than
DeiT. In addition, our model has larger feature dimensions which can capture
more information than the baseline model, leading to possible better
classification or recognition results.

Figure 6: Searched architectures of PSViT-1D-Tiny and PSViT-2D-Tiny. The
feature size does not change in the same stage.

###  4.5 Searched Architectures

Fig. 6 shows the searched architectures of PSViT-1D and PSViT-2D. There are
about 50% layers sharing the attention, which shows that the proposed
attention sharing mechanism can achieve a great trade-off between accuracy and
computation costs. For the computation allocation among the three stages, both
models allocate less computation in the first stage and more computation in
the last stage. The features in the first stage have a larger spatial size.
Applying self-attention to these features leads to a heavy computation burden.
We think that is why the first stage tends to adopt attention sharing more
times or has fewer total layers. It is a good strategy to reduce unnecessary
computation. Differently, applying self-attention on deeper layers which have
less tokens is better. The saved computation allows us to increase the feature
dimension or layer number properly for a stronger feature representation. For
the last layer of the two models, there is no attention sharing. The last
layer deserves an independent self-attention operation because its output is
directly used for the final classification. More computation on the last layer
will produce more accurate classification results.

Table 6: Performance comparison between different backbones on the object detection and instance segmentation tasks. Backbone | Object Detection | Instance Segmentation
---|---|---
$AP$ | $AP50$ | $AP75$ | $AP_{s}$ | $AP_{m}$ | $AP_{l}$ | $AP$ | $AP50$ | $AP75$ | $AP_{s}$ | $AP_{m}$ | $AP_{l}$
ResNet18 | 34.8 | 56.3 | 37.5 | 20.1 | 37.0 | 45.2 | 32.8 | 53.4 | 34.8 | 17.4 | 25.1 | 44.7
PSViT-2D-Tiny | 40.8 | 64.7 | 44.0 | 25.3 | 43.8 | 53.9 | 37.7 | 60.1 | 39.9 | 21.2 | 40.6 | 52.8
ResNet50 | 38.3 | 60.4 | 41.4 | 23.3 | 41.6 | 48.9 | 35.5 | 57.2 | 37.8 | 19.6 | 38.6 | 47.7
ResNet101 | 39.5 | 61.3 | 43.0 | 23.4 | 42.7 | 51.1 | 36.5 | 58.2 | 39.1 | 19.6 | 39.7 | 49.4

###  4.6 Comparison between PSViT-1D and PSViT-2D

Our PSViT-1D and PSViT-2D have different searched architectures as shown in
Fig. 6. For PSViT-1D, we set the output token number as 50 (with the CLS
token). Similarly, the spatial size of the output feature in PSViT-2D is
$7\times 7$. Both models have token pooling layers with a stride of 2, which
means token number will reduce 50% in PSViT-1D and 75% for the PSViT-2D. In
PSViT-1D, the token pooling is applied to 1D features. The token number is 197
for the first stage and 99 for the second stage. For PSViT-2D, the token
number of the first stage and the second stage are $28\times 28$ and $14\times
14$, respectively. As the Table 2 shows, our PSViT-2D models achieve better
performance than PSViT-1D models. We think the main reason is that 2D token
pooling can keep the structure information of 2D images while the 1D token
pooling only considers the neighbouring tokens on the x-axis but ignores those
on the y-axis. Besides, 2D features from PSViT-2D is more suitable for
downstream tasks.

###  4.7 Object detection and instance segmentation results

To evaluate the transferability of our models, we contrast our PSViT-2D model
to ResNet on the downstream tasks, _i.e_. object detection and instance
segmentation. We apply the Mask-RCNN-FPN [16] as our framework. We conduct
experiments on MSCOCO 2017 dataset, which consists of 118K training images and
5K validation images. We report the performance on the validation set.

For the network training, we first initialize the backbone parameters with our
pre-trained weights on ImageNet and adopt Xavier initialization on other
layers in the neck and heads. Our models are trained with the batch size of 16
on 8 V100 GPUs and optimized by AdamW with the initial learning rate of
0.0001, 0.05 weight decay. We follow the standard common 1x training setting
(12 epochs) to train the whole Mask R-CNN models with our searched models and
ResNet as the backbone. During the training stage, we follow the multi-scale
training setting in [31]: resizing the shorter side of input between 480 and
800 while the longer side is at most 1333. During testing, the shorter side of
the input is fixed as 800 pixels.

The results are shown in Table 6. Our PSViT-2D-Tiny achieves 40.8% mAP on the
object detection task and 37.7% mAP on the instance segmentation task, which
is 6 and 4.9 points higher than that of ResNet18, respectively. Our
PSViT-2D-Tiny even achieves better performance than ResNet101. The much better
performance than ResNets on both object detection and instance segmentation
shows the great transferability of our models.

##  5 Conclusions

In this paper, we have introduced a new PSViT by making use of token pooling
and attention sharing. To effectively enhance the performance of current ViT,
token pooling and attention sharing are first designed. Then, the search space
for a PSViT stage is designed. Based on the search space, we further apply an
efficient AutoML method, SPOS, to obtain the optimal module design. Extensive
comparison experiments on the ImageNet image classification dataset show the
effectiveness of the proposed PSViT since it can increase the classification
accuracy a lot. The great performance on object detection and instance
segmentation also validates the transferability of our models.

## References

  * [1] Gabriel Bender, Pieter-Jan Kindermans, Barret Zoph, Vijay Vasudevan, and Quoc Le.  Understanding and simplifying one-shot architecture search.  In International Conference on Machine Learning, pages 550–559, 2018.
  * [2] Han Cai, Tianyao Chen, Weinan Zhang, Yong Yu, and Jun Wang.  Efficient architecture search by network transformation.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
  * [3] Han Cai, Ligeng Zhu, and Song Han.  Proxylessnas: Direct neural architecture search on target task and hardware.  arXiv preprint arXiv:1812.00332, 2018.
  * [4] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko.  End-to-end object detection with transformers.  In European Conference on Computer Vision, pages 213–229, 2020\.
  * [5] Mark Chen, Alec Radford, Rewon Child, Jeffrey Wu, Heewoo Jun, David Luan, and Ilya Sutskever.  Generative pretraining from pixels.  In International Conference on Machine Learning, pages 1691–1703, 2020.
  * [6] Wuyang Chen, Xinyu Gong, Xianming Liu, Qian Zhang, Yuan Li, and Zhangyang Wang.  Fasterseg: Searching for faster real-time semantic segmentation.  arXiv preprint arXiv:1912.10917, 2019.
  * [7] Yukang Chen, Tong Yang, Xiangyu Zhang, Gaofeng Meng, Xinyu Xiao, and Jian Sun.  Detnas: Backbone search for object detection.  Advances in Neural Information Processing Systems, 32:6642–6652, 2019.
  * [8] Yuanzheng Ci, Chen Lin, Ming Sun, Boyu Chen, Hongwen Zhang, and Wanli Ouyang.  Evolving search space for neural architecture search.  arXiv preprint arXiv:2011.10904, 2020.
  * [9] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805, 2018.
  * [10] Xuanyi Dong and Yi Yang.  Network pruning via transformable architecture search.  In The Conference on Neural Information Processing Systems (NeurIPS), pages 760–771, 2019.
  * [11] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  arXiv preprint arXiv:2010.11929, 2020.
  * [12] Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter.  Efficient multi-objective neural architecture search via lamarckian evolution.  arXiv preprint arXiv:1804.09081, 2018.
  * [13] Golnaz Ghiasi, Tsung-Yi Lin, and Quoc V Le.  Nas-fpn: Learning scalable feature pyramid architecture for object detection.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7036–7045, 2019.
  * [14] Jianyuan Guo, Kai Han, Yunhe Wang, Chao Zhang, Zhaohui Yang, Han Wu, Xinghao Chen, and Chang Xu.  Hit-detector: Hierarchical trinity architecture search for object detection.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11405–11414, 2020.
  * [15] Zichao Guo, Xiangyu Zhang, Haoyuan Mu, Wen Heng, Zechun Liu, Yichen Wei, and Jian Sun.  Single path one-shot neural architecture search with uniform sampling.  In European Conference on Computer Vision, pages 544–560, 2020\.
  * [16] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick.  Mask r-cnn.  In Proceedings of the IEEE international conference on computer vision, pages 2961–2969, 2017.
  * [17] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [18] Xin He, Kaiyong Zhao, and Xiaowen Chu.  Automl: A survey of the state-of-the-art.  Knowledge-Based Systems, 212:106622, 2021.
  * [19] Xian Li, Asa Cooper Stickland, Yuqing Tang, and Xiang Kong.  Deep transformers with latent depth.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1736–1746. Curran Associates, Inc., 2020.
  * [20] Feng Liang, Chen Lin, Ronghao Guo, Ming Sun, Wei Wu, Junjie Yan, and Wanli Ouyang.  Computation reallocation for object detection.  In International Conference on Learning Representations, 2020.
  * [21] Chenxi Liu, Liang-Chieh Chen, Florian Schroff, Hartwig Adam, Wei Hua, Alan L Yuille, and Li Fei-Fei.  Auto-deeplab: Hierarchical neural architecture search for semantic image segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 82–92, 2019.
  * [22] Hanxiao Liu, Karen Simonyan, Oriol Vinyals, Chrisantha Fernando, and Koray Kavukcuoglu.  Hierarchical representations for efficient architecture search.  arXiv preprint arXiv:1711.00436, 2017.
  * [23] Hanxiao Liu, Karen Simonyan, and Yiming Yang.  Darts: Differentiable architecture search.  arXiv preprint arXiv:1806.09055, 2018.
  * [24] Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz Kaiser, Noam Shazeer, Alexander Ku, and Dustin Tran.  Image transformer.  In International Conference on Machine Learning, pages 4055–4064, 2018.
  * [25] Esteban Real, Chen Liang, David So, and Quoc Le.  Automl-zero: Evolving machine learning algorithms from scratch.  In International Conference on Machine Learning, pages 8007–8019, 2020.
  * [26] Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen.  Mobilenetv2: Inverted residuals and linear bottlenecks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4510–4520, 2018.
  * [27] Ramprasaath R. Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra.  Grad-cam: Visual explanations from deep networks via gradient-based localization.  In ICCV 2017, Venice, Italy, October 22-29, 2017, pages 618–626, 2017.
  * [28] Guo Shaopeng, Wang Yujie, Li Quanquan, and Junjie Yan.  Dmcp: Differentiable markov channel pruning for neural networks.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
  * [29] Han Shi, Jiahui Gao, Xiaozhe Ren, Hang Xu, Xiaodan Liang, Zhenguo Li, and James T Kwok.  Sparsebert: Rethinking the importance analysis in self-attention.  arXiv preprint arXiv:2102.12871, 2021.
  * [30] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  arXiv preprint arXiv:1409.1556, 2014.
  * [31] Peize Sun, Rufeng Zhang, Yi Jiang, Tao Kong, Chenfeng Xu, Wei Zhan, Masayoshi Tomizuka, Lei Li, Zehuan Yuan, Changhu Wang, et al.  Sparse r-cnn: End-to-end object detection with learnable proposals.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 14454–14463, 2021.
  * [32] Yuan Tian, Qin Wang, Zhiwu Huang, Wen Li, Dengxin Dai, Minghao Yang, Jun Wang, and Olga Fink.  Off-policy reinforcement learning for efficient and effective gan architecture search.  In European Conference on Computer Vision, pages 175–192, 2020\.
  * [33] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou.  Training data-efficient image transformers & distillation through attention.  In International Conference on Machine Learning, pages 10347–10357, 2021.
  * [34] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In Advances in neural information processing systems, pages 5998–6008, 2017.
  * [35] Alvin Wan, Xiaoliang Dai, Peizhao Zhang, Zijian He, Yuandong Tian, Saining Xie, Bichen Wu, Matthew Yu, Tao Xu, Kan Chen, et al.  Fbnetv2: Differentiable neural architecture search for spatial and channel dimensions.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12965–12974, 2020.
  * [36] Huiyu Wang, Yukun Zhu, Hartwig Adam, Alan Yuille, and Liang-Chieh Chen.  Max-deeplab: End-to-end panoptic segmentation with mask transformers.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5463–5474, 2021.
  * [37] Yuqing Wang, Zhaoliang Xu, Xinlong Wang, Chunhua Shen, Baoshan Cheng, Hao Shen, and Huaxia Xia.  End-to-end video instance segmentation with transformers.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8741–8750, 2021.
  * [38] Bichen Wu, Yanghan Wang, Peizhao Zhang, Yuandong Tian, Peter Vajda, and Kurt Keutzer.  Mixed precision quantization of convnets via differentiable neural architecture search.  arXiv preprint arXiv:1812.00090, 2018.
  * [39] Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He.  Aggregated residual transformations for deep neural networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1492–1500, 2017.
  * [40] Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin.  Snas: stochastic neural architecture search.  arXiv preprint arXiv:1812.09926, 2018.
  * [41] Fuzhi Yang, Huan Yang, Jianlong Fu, Hongtao Lu, and Baining Guo.  Learning texture transformer network for image super-resolution.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5791–5800, 2020.
  * [42] Matthew D Zeiler and Rob Fergus.  Visualizing and understanding convolutional networks.  In European conference on computer vision, pages 818–833, 2014\.
  * [43] Haoyi Zhou, Shanghang Zhang, Jieqi Peng, Shuai Zhang, Jianxin Li, Hui Xiong, and Wancai Zhang.  Informer: Beyond efficient transformer for long sequence time-series forecasting.  In Proceedings of AAAI, 2021.
  * [44] Xizhou Zhu, Weijie Su, Lewei Lu, Bin Li, Xiaogang Wang, and Jifeng Dai.  Deformable detr: Deformable transformers for end-to-end object detection.  arXiv preprint arXiv:2010.04159, 2020.
  * [45] Barret Zoph and Quoc V Le.  Neural architecture search with reinforcement learning.  arXiv preprint arXiv:1611.01578, 2016.