# Diet Code Is Healthy: Simplifying Programs for Pre-trained Models of Code

Zhaowei Zhang1, Hongyu Zhang2, Beijun Shen1, Xiaodong Gu1 1School of Software,
Shanghai Jiao Tong University, China2The University of Newcastle, Australia
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
(2022)

###### Abstract.

Pre-trained code representation models such as CodeBERT have demonstrated
superior performance in a variety of software engineering tasks, yet they are
often heavy in complexity, quadratically with the length of the input
sequence. Our empirical analysis of CodeBERT’s attention reveals that CodeBERT
pays more attention to certain types of tokens and statements such as keywords
and data-relevant statements. Based on these findings, we propose DietCode,
which aims at lightweight leverage of large pre-trained models for source
code. DietCode simplifies the input program of CodeBERT with three strategies,
namely, word dropout, frequency filtering, and an attention-based strategy
that selects statements and tokens that receive the most attention weights
during pre-training. Hence, it gives a substantial reduction in the
computational cost without hampering the model performance. Experimental
results on two downstream tasks show that DietCode provides comparable results
to CodeBERT with 40% less computational cost in fine-tuning and testing.

Program simplification, Pre-trained models, Learning program representations,
Code intelligence

††journalyear: 2022††copyright: acmcopyright††conference: Proceedings of the
30th ACM Joint European Software Engineering Conference and Symposium on the
Foundations of Software Engineering; November 14–18, 2022; Singapore,
Singapore††booktitle: Proceedings of the 30th ACM Joint European Software
Engineering Conference and Symposium on the Foundations of Software
Engineering (ESEC/FSE ’22), November 14–18, 2022, Singapore, Singapore††price:
15.00††doi: 10.1145/3540250.3549094††isbn: 978-1-4503-9413-0/22/11††ccs:
Computing methodologies Natural language processing

##  1\. Introduction

Pre-trained models of code such as CodeBERT (Feng et al., 2020) have been the
cutting-edge program representation technology, yielding remarkable
performance on a variety of software engineering tasks such as code completion
(Ciniselli et al., 2021), code search (Feng et al., 2020), and clone detection
(Lu et al., 2021). Having pre-trained on large-scale code corpora, they
demonstrate a better understanding of the semantics of source code than
previous deep learning models such as code2vec (Alon et al., 2019) and ASTNN
(Zhang et al., 2019).

Despite making a giant leap in accuracy, pre-trained models are often heavy in
computation, which significantly hinders their applications in practice. For
example, the standard CodeBERT contains 125 million parameters and takes 28
hours to pre-train on 8.5M code. More critically, pre-trained models usually
need to be fine-tuned before use, which is cost inefficient due to the large
scale of parameters and training data. As such, it is highly desirable to
identify the critical feature learned by pre-trained models and reduce the
required computational cost by focusing only on the important information from
model inputs (Rabin et al., 2021).

To understand critical information learned by pre-trained models, we conduct
an empirical analysis of CodeBERT – a pre-trained model for programming and
natural languages. Our study aims to find out (i) what kinds of tokens
CodeBERT pays the most attention to; and (ii) what kinds of statements are
most important to CodeBERT when learning code representations. To answer these
two questions, we categorize tokens and statements into a few classes and
summarize the attention weights of each class that the pre-trained CodeBERT
assigns to. Our results reveal that keywords and data types are the most
critical tokens that CodeBERT focuses on. In terms of statements, CodeBERT
pays more attention to _method signatures_ and _return statements_ , which
show the overall functionality of a method.

Based on these empirical findings, we propose DietCode, a novel method that
aims at lightweight leverage of large pre-trained models for source code.
DietCode reduces the computational complexity of pre-trained models by pruning
unimportant tokens and statements from the input programs. Three pruning
strategies are proposed, including word dropout, frequency filtering, and
attention-based pruning. In particular, the attention-based pruning strategy
selects tokens and statements that receive the highest attention from pre-
trained models. The program simplification algorithm formulates statement
selection as a 0-1 knapsack problem where statements are regarded as items,
and their attention weights are regarded as values. The algorithm selects
statements (items) under the constraint of a given target length (capacity).

We apply DietCode to two downstream tasks, namely, code search and code
summarization. We measure the performance with relative length, FLOPs, and
time cost, and compare our approach with baseline models, including the
original pre-trained code model and SIVAND (Rabin et al., 2021). Experimental
results show that DietCode provides comparable results as RoBERTa (code), with
nearly 40% less computational cost in fine-tuning and testing.

Our contributions can be summarized as follows:

  * •

We conduct an in-depth empirical analysis of critical tokens and statements
learned by CodeBERT.

  * •

We propose a novel program simplification approach for pre-trained programming
language models that can significantly reduce the computation cost while
retaining comparable performance.

  * •

We extensively evaluate the proposed approach in two downstream tasks and show
the effectiveness of our approach.

##  2\. Background

###  2.1. Pre-Trained Language Models

Pre-trained language models such as BERT (Devlin et al., 2019), GPT-2 (Radford
et al., 2019), and T5 (Raffel et al., 2020) have achieved remarkable success
in a variety of NLP tasks (Yang et al., 2019; Clark et al., 2019; Conneau and
Lample, 2019). They refer to neural network models trained on large text
corpora and can be fine-tuned to low-resource downstream tasks.

State-of-the-art pre-trained models are mainly built upon the Transformer
architecture (Vaswani et al., 2017). The Transformer is a sequence-to-sequence
learning model using the attention mechanism (Bahdanau et al., 2015). It is
based on the encoder-decoder architecture, where a source sequence is encoded
into hidden states and then taken as input to the decoder for generating a
target sequence. Both the encoder and decoder contain multiple identical
layers, and each layer consists of a multi-head self-attention network
followed by a feed-forward network. Both of the outputs will be normalized
before entering the next layer.

The key component of Transformer is the self-attention mechanism that
represents a sequence by relating tokens in different positions (Vaswani et
al., 2017). The goal of self-attention is to learn the important regions in
the input sequence. Unlike traditional recurrent neural networks (Cho et al.,
2014), self-attention networks can learn the dependencies from distant tokens
in parallel. For an input sequence ($x_{1}$,…, $x_{n}$) of length $n$, the
self-attention produces its representation ($z_{1}$, $z_{2}$ … $z_{n}$) as

(1)
$z_{i}=\sum_{j=1}^{n}\mathrm{Softmax}(\frac{(x_{i}W^{Q})\cdot(x_{j}W^{K})^{T}}{\sqrt{d}})\cdot
x_{j}W^{V}$

where $W^{Q}$, $W^{K}$, and $W^{V}$ denote the model’s parameters. $d$ is the
dimension of the input matrix. The model involves several attention heads, and
each head’s output is concatenated into the final result.

Pre-trained models usually involve large-scale parameters and consume huge
computational resources. For example, BERT-base and BERT-large contain 110M
and 340M parameters, respectively. As such, the lightweight leverage of pre-
trained models is greatly desirable for research and practitioners (Sanh et
al., 2019).

###  2.2. CodeBERT

Recently, researchers have adopted BERT for software engineering tasks and
proposed CodeBERT (Feng et al., 2020). CodeBERT is a bimodal pre-trained model
for natural and programming languages, capturing semantic representations from
programming languages (Feng et al., 2020). The program representations learned
by CodeBERT can be further utilized for downstream tasks such as code search
and code summarization.

CodeBERT is built on top of a Transformer encoder (Vaswani et al., 2017). The
optimization involves two tasks: masked language modeling (MLM) and replaced
token detection (RTD). MLM masks two random tokens from the input pair of code
and natural language comments, and aims to predict the original token in an
extensive vocabulary. RTD involves two generators and a discriminator. The
generators predict the original token for the masked token while the
discriminator predicts whether the tokens are original or not. After pre-
training, CodeBERT can be adapted to downstream tasks through fine-tuning on
the target dataset.

##  3\. Empirical Analysis

###  3.1. Study Design

In this section, we describe our study methodology and experimental setup.
There are many levels of granularity for code, such as tokens, statements, and
functions. As an in-depth study, we begin by investigating the atomic unit of
source code, namely, tokens. We next investigate the statement-level knowledge
learned by CodeBERT, which contains basic structures and semantic units. We
finally explore the function-level knowledge learned by CodeBERT through
downstream tasks. In summary, we design our study methodology by addressing
the following research questions:

  * •

RQ1: What critical tokens does CodeBERT learn about? We study the critical
information CodeBERT learned at the token level by analyzing the attention
weights assigned to these tokens and visualizing their relative importance.

  * •

RQ2: What critical statements does CodeBERT learn about? We further study the
statements that CodeBERT assigns the most weights to. We classify code
statements into common categories such as _initialization_ , _assignment_ ,
and _return_ , and present the attention weight of each category assigned by
CodeBERT.

To answer these questions, we first need to know how to represent the key
information learned by CodeBERT. In other words, how to measure the importance
of each token and statement? Since the heart of CodeBERT is the self-attention
network, where hidden states of each token are calculated layer-by-layer
according to the self-attention weights, we measure the importance of each
token using the attention weights in the Transformer layers in CodeBERT after
pre-training. Next, we will present the details of how to measure the
importance of tokens and statements, respectively.

####  3.1.1. Measuring Token Importance Using Attention Weights

As introduced in Section 2.2, CodeBERT takes a sequence of source code tokens
as input and produces a self-attention weight for each input token. Each
weight measures how the corresponding token gains attention from other tokens
in the input sequence. The higher the attention weights, the more attention
that are paid by other tokens. Therefore, in our study, we measure the
importance of each token using the attention weight. CodeBERT has multiple
self-attention layers and heads, each producing an attention weight for the
same token. We average the attention weights of all layers and heads for each
token. In our experiments, we go through the CodeSearchNet corpus (Husain et
al., 2019) and take as input each code snippet to the pre-trained CodeBERT.
Then, we calculate the average attention weight that CodeBERT assigns to each
token.

####  3.1.2. Computing Attentions of Statements

Having obtained the importance of each token, we compute the attention weight
for each statement. Intuitively, the attention weight for a statement can
simply be obtained using the average attention weights of all its tokens.
However, different tokens in a statement have different importance. Without
considering the global importance of each token, statements that consist of
unimportant tokens could obtain even higher attention. Based on this concern,
we regularize statement attention by penalizing unimportant tokens that gain
fewer attention weights across the whole corpus. More specifically, we
calculate the attention weight for a statement $S$ using a weighted average of
attention weights of its tokens:

(2) $a(S)=\sum_{t\in S}w(t)\cdot a(t)$

where $a(t)$ represents the attention weight of token $t$ in statement $S$;
$w(t)$ denotes the normalized attention weight of token $t$ in the whole
corpus described in the previous section. The normalization is implemented
using the Softmax function, namely,

(3) $w(t)=\text{Softmax}_{t\in S}(a(t))$

Unlike tokens, statements are often unique in the corpus and cannot be
included in a dictionary. To efficiently analyze statements, we classify
statements into 21 categories such as _method signature_ , _variable
declaration_ , and _if condition_ , and only present the average attention
weight for each category. These categories are mainly guided by Java
specification (Gosling et al., 2000). In particular, the _logger_ category
contains statements with standard logging functionalities such as log4j,
Logger, and println. Table 1 shows the categories of statements we have
summarized and the corresponding quantities in the CodeSearchNet corpus. We
can see that _function invocation_ and _method signature_ are the most common
statements, while _loop_ statements such as _while_ are relatively rare.

Table 1. Statistics of statements. _Arithmetic_ means statements with only mathematical operations. _Function Invocation_ represents statements that invoke other functions. Category | Quantity | Category | Quantity
---|---|---|---
Function Invocation | 16,558 | Throw | 1,460
Method Signature | 11,755 | Catch | 1,309
Variable Declaration | 11,701 | Arithmetic | 628
If Condition | 11,646 | Case | 577
Annotation | 8,980 | While | 459
Return | 8,331 | Break | 341
Getter | 3,092 | Finally | 297
For | 2,190 | Continue | 142
Try | 1,797 | Switch | 210
Logging | 1,763 | Synchronized | 73
Setter | 1,721 |  |

###  3.2. Results and Analysis

In this section, we present the results of our experiments for each research
question.

####  3.2.1. What does CodeBERT learn about code tokens? (RQ1)

Figure 2 highlights the critical tokens in Java that gain the most attention
by CodeBERT. The graph is summarized from the CodeSearchNet (Husain et al.,
2019) corpus which contains more than 100,000 Java functions. For tokens in
each function, we calculate their attention weights and insert them into a
¡token, attention¿ map until the keys of the map are stable. For ease of
visualization, we remove tokens that appear less than 50 times in the corpus.
Among all the Java tokens, coverage gains the lowest attention weight
(5.43$e$-5) while boolean has the highest weight (2.94$e$-2). The standard
deviation of these weights is 5.97$e$-3.

The results show that CodeBERT assigns more attention to Java keywords such as
public and boolean. This is expected since Java keywords frequently appear in
Java code and play a dominant role in representing code semantics. Another
category of tokens that receives high attention is the data-oriented
identifiers such as Map, List, and String, probably because they define key
data structures in a function.

Figure 1. Attention weights of Java keywords learned by CodeBERT Figure 2.
Java tokens highlighted by CodeBERT. The size of each token indicates the
attention weight assigned by CodeBERT. Figure 3. A heatmap of attention
weights for Java statements and tokens. The background color of a token is
proportional to the average attention weight assigned to it).

Motivated by this finding, we further study the attention of Java keywords.
Figure 1 shows the attention weight of each Java keyword. As we can see, the
keyword private obtains the highest attention weight of 1.15$e$-2 among all
keywords, while interface and transient gain the lowest attention weights of
7.14$e$-4 and 9.62$e$-4, respectively. The standard deviation of these weights
is 1.513$e$-3.

Among all Java keywords, method modifiers such as public, private, and static
receive the highest attention weights We conjecture that these modifiers often
denote the beginning of a method signature, which is essential to
understanding the entire code. Next to these modifiers, finally and return
also receive high attention weights. Finally usually represents the end of a
function, and the code inside the finally block will definitely be executed.
Return represents the method’s output, which may show the method’s
functionality. Surprisingly, branching-related keywords such as if and switch
receive lower attention, presumably because CodeBERT considers them
unimportant for program understanding despite their frequent occurrence in
code.

A similar pattern can be observed in Python. For example, CodeBERT prefers
keywords such as return and def that represent the general structure of a
function, just like return and public in Java. In particular, among the
branching and loop keywords, while ranks higher than if and for.

Figure 3 shows a heatmap of attentions for a Java function. The code is about
reading content from a file. The tokens with higher attention weights are
marked in deeper colors. The heatmap shows a similar result as discussed
above. public and finally receive the highest attention weights in this
function, while new and if obtain the lowest attentions. Tokens that are
related to the core functionality, such as File and read, have shown high
attention weights. By contrast, tokens that are auxiliary to the main
functionality, such as null and Exception have received much lower attention.
Another interesting observation is that grammatical symbols such as } and; are
considered necessary by CodeBERT probably because they mark the end of
statements and blocks. Overall, the heatmap shows that CodeBERT mainly pays
attention to functional tokens that reflect the overall functionality and does
not care much about notional tokens about grammar and special branches.

####  3.2.2. What does CodeBERT learn about code statements? (RQ2)

Figure 4 shows the attention weights assigned by CodeBERT for each type of
Java statement. As seen, _method signature_ has gained the highest attention
(4.11$e$-3), while _case statement_ obtains the lowest attention (2.32$e$-3).
The standard deviation of the attention weights over all categories is
4.88$e$-4. Broadly speaking, CodeBERT focuses more on statements indicating
the overall functionality of a method, such as _method signature_ and _return_
, probably because they contain dense information of the whole function, such
as names and targets.

Interestingly, _arithmetic expressions_ (expressions with mathematical
operations) also receive more attention than other statements. Like natural
language, _arithmetic expression_ can be viewed as a sequence of operations
that tell the functionality of a statement. _Function invocations_ has also
been shown to be essential for CodeBERT to understand code. Like _arithmetic
expressions_ , _function invocations_ can be regarded as identifiers of other
method signatures, which can be literally understood through the function
names and parameters.

Surprisingly, CodeBERT does not pay much attention to statements related to
control flow structures, such as _while_ , _for_ and _case_. This indicates
that CodeBERT can effectively learn representations of plain texts while being
limited in learning structures.

Figure 3 also shows the heatmap of statement attentions for a sample function
of Java. Similar to the conclusions above, _method signature_ is the most
important, which provides a general introduction to the method’s
functionality. At the same time, statements about _variable declaration and
initialization_ , such as “String content == null” receive lower attentions,
probably because they only create new variables with initial value null
without actual operations to them. The attention weight of the _if_ statement
in the finally block is also low (2.92$e$-3). This function only closes the
file reader and may have little effect on CodeBERT’s understanding of the
whole method.

We observe a similar trend for Python statements. _Method signatures_ also
receive the highest attention weight (6.86$e$-3), while branching statements
such as _break_ and _continue_ have the lowest weights. The standard deviation
of attention weights for Python statements is 1.66$e$-3, which is a bit larger
than that of Java statements.

Compared to Java, the distributions of Python statements and tokens are a bit
more sparse. For example, the _method signature_ statement which ranks the
first owns a much higher weight than the second category of statements (i.e.,
_return_). The top keyword def also obtains a much higher attention weight
than other keywords.

Figure 4. Attention weights of various types of Java statements learned by
CodeBERT

##  4\. DietCode: Program Simplification for CodeBERT

As Equation 1 indicates, the computational complexity for computing the
attention matrix is $\mathcal{O}(d^{2}n+n^{2}d)$, which quadratically scales
with sequence length. As such, the attention operation becomes a bottleneck
when applied to long sequences such as source code (Kim et al., 2021).

We wonder whether we can remove unimportant tokens or statements from the
input programs of CodeBERT. In this way, the time and space costs for the pre-
trained model can be substantially reduced. Based on this idea, we propose
DietCode, a lightweight pre-trained model for source code. DietCode reduces
the computational complexity of CodeBERT by simplifying input programs.

More specifically, our problem formulation is as follows: given a code snippet
$C=\\{s_{1};\ldots;s_{|C|}\\}$ which consists of $|C|$ statements, we want to
output a pruned code snippet $C_{p}$ which contains a maximum length of $L$
tokens. The goal of program simplification is to prune as many tokens as
possible without a significant impact on the accuracy of downstream tasks.

###  4.1. Word Dropout

One straightforward strategy for program simplification is the word dropout
(Iyyer et al., 2015), namely, randomly dropping tokens from the input code to
meet a specified sequence length. For each token $w\in S$, we define a binary
variable $r_{w}\in\\{0,1\\}$ to indicate whether the token will be kept
($r_{w}=1$) or pruned ($r_{w}=0$):

(4) $\begin{split}&r_{w}\sim\mathrm{Bernoulli}(p)\\\ &C_{p}=\\{w|w\in
C~{}~{}\mathrm{and}~{}~{}r_{w}>0\\}\end{split}$

where $p=L/|C|$ denotes the probability of selecting a token. In addition to
reducing computational complexity, word dropout has also been shown to improve
the robustness of neural networks (Iyyer et al., 2015). Hence, it enhances the
performance of many tasks.

###  4.2. Frequency Filtering

A key concern with the word dropout strategy is that it can also prune
important tokens randomly from the input. Hence, we introduce another
frequency-based token pruning strategy that removes uncommon tokens while
keeping only the most frequently occurred tokens.

Specifically, for each input code snippet $C=\\{w_{1},...,w_{n}\\}$, we keep
tokens if their frequency is among the top $k$ ($k=|C_{p}|$) of all tokens in
the input, namely,

(5) $C_{p}=\\{w|w\in
C,f(w)\in\mathrm{top-}k(f(w_{1}),...,f(w_{n})),k=|C_{p}|)$

where $f(w)$ denotes the frequency of $w$ in the whole code corpora.

###  4.3. Attention-based Code Pruning

The frequency filtering strategy can roughly distinguish important tokens, but
may only bias common tokens. According to our empirical findings above,
CodeBERT pays attention to certain types of tokens and statements. Tokens that
receive high attention do not coincide with common tokens. In order to provide
a more fine-grained selection of important tokens and statements, we propose
an attention-based code pruning strategy that selects tokens and statements
based on their attention weights.

Algorithm 1 The Attention-based Pruning Algorithm

1:

2:C=$s_{1};\ldots;s_{|C|}$: an input code snippet,

3:$\mathbf{A}^{T}$: attention dictionary of tokens,

4:$\mathbf{A}^{S}$: attention dictionary of statements,

5:L: target length

6:

7:Reduced code snippet
$\texttt{C}_{p}=s^{\prime}_{1};\ldots;s^{\prime}_{|C_{p}|}$

8:for s $\in$ C do

9: a(s) = $\mathbf{A}^{S}$(s) $\triangleright$ obtain the statement attention

10: for t $\in$ s do

11: a(t) = $\mathbf{A}^{T}$(t) $\triangleright$ obtain the token attention

12: end for

13:end for

14:$C_{0}$ $\leftarrow$ 0-1 Knapsack (items={s}s∈C, values=$\\{a(s)\\}_{s\in
C}$, weights= {—s—}s∈C, capacity = $L$+$\text{max}_{s\in C}$(—s—)
$\triangleright$ candidate statements

15:for i = 1,…, $\sum_{s\in C_{0}}$(—s—) - L do

16: $s^{\prime}$ $\leftarrow$ $s^{\prime}$ $\setminus$ {t} where
$s^{\prime}=\mathrm{argmin}_{s\in C_{0}}a(s)$,
sp $s^{\prime}$ $\leftarrow$ $s^{\prime}$ $\setminus$ {t} where
$t=\mathrm{argmin}_{t_{0}\in s^{\prime}}a(t_{0})$

17:end for

18:$C_{p}$ $\leftarrow$ $s^{\prime}_{1};\ldots;s^{\prime}_{|C_{0}|}$ where
$C_{0}$ = $\\{s^{\prime}_{1},s^{\prime}_{2},...,s^{\prime}_{|C_{0}|}\\}$
$\triangleright$ concatenate statements

The simplification procedure is summarized in Algorithm 1. We begin by
summarizing the category of statements for a given programming language
according to the methodology in our empirical study. Then, we create attention
dictionaries for both statements and tokens. The algorithm runs code pruning
in two phases: _selecting statements_ and _pruning tokens_.

In the statement selection phase, we select pivot statements that belong to a
category that obtain the highest attention weights in our empirical study.
Meanwhile, we want the selected statements not to exceed the length constraint
(i.e., $L$ tokens). This can be formulated as a 0-1 knapsack problem
(Pisinger, 1995), where statements can be regarded as the items to be
collected into a knapsack, with the attention weights being the values, and
the statement lengths being the weights. The length constraint can be regarded
as the capacity of the knapsack. It is worth noting that we enlarge the
capacity by the maximum length of statements for tolerance of selecting one
more statement so that the algorithm can further perform token pruning in the
next phase.

In the token pruning phase, we greedily remove the tokens that have the lowest
attention weights in the lowest weighed statements iteratively until
satisfying the maximum number of tokens.

One potential problem is the different scales of statement attentions and
token sizes. We find that some shorter sequences are much more likely to be
chosen during our experiments even if they receive low attention weights. This
is probably because the value ratio (the attention weight divided by the
sequence length) of a shorter sequence is much larger than the longer one. We
amplify the attention weights using min-max normalization and multiply with
the number of tokens in the statement, that is,

(6) $a(s)=\frac{a(s)-\mathrm{min}_{s\in S}(a(s))}{\mathrm{max}_{s\in
S}(a(s))-\mathrm{min}_{s\in S}(a(s))}\times N$

where $N$ denotes the number of tokens in the statement.

The time complexity of the simplification algorithm is
$\mathcal{O}$($N\cdot(L_{T}+L_{M})$), where $L_{T}$ denotes the target number
of tokens, and $L_{M}$ denotes the maximum length of statements. The time cost
mainly comes from the 0-1 knapsack algorithm. Furthermore, the knapsack
algorithm requires a two-dimensional array for dynamic programming, which
requires space complexity.

(a) The original source code

(b) Code after statement selection

(c) Code after token pruning

Figure 5. An example of program simplification by DietCode (attention).

Figure 5 shows an example of program simplification by DietCode. The original
code (Figure 5(a)) aims to read content from a file with a given filename. Our
goal is to reduce the code to contain only 60 tokens without considerably
losing the semantics. In the _statement selection_ phase (Figure 5(b)), the
simplification algorithm solves a 0-1 knapsack problem by setting the capacity
to 78 (including the target length of 60 and the longest statement length 18).
Then, DietCode selects trunk statements such as _method signature_ and
_return_ , and removes trivial statements such as _variable assignments_ and
_catch_. The number of tokens in the code is reduced from 118 to 77. In the
_token pruning_ phase, DietCode further removes tokens such as variable
initialization (Figure 5(c)), and reduces the number of tokens from 77 to 60.
Although reduced by around 50%, the main semantic of this function is not
destroyed significantly. CodeBERT can still understand the function through
key statements such as the method name readFile, the key variable content, and
the invoked function read. Although the remaining code is never runnable, the
selected critical information can be used for downstream tasks such as code
search and summarization.

##  5\. Evaluation

This section introduces the evaluation of DietCode in two downstream tasks. We
aim to answer the following research questions through experiments:

  * •

RQ3: How effective is DietCode in program simplification? We evaluate the
performance and computation cost of DietCode in two downstream tasks and
compare it with baseline models.

  * •

RQ4: How effective is DietCode under different relative lengths? We study the
effect of different relative lengths on the evaluation scores. Our goal is to
find the relative length that leads to the best trade-off between model
performance and computational expense.

  * •

RQ5: What is the effect of different pruning strategies? The attention-based
DietCode performs both statement and token pruning. We conduct an ablation
study to identify the effect of pruning each of them.

###  5.1. Downstream Tasks

We test our algorithm in two downstream tasks, namely, code search and code
summarization. They are the most widely used software engineering tasks to
demonstrate the capacity of NL-PL understanding (Kamiya et al., 2002; White et
al., 2016; Haiduc et al., 2010; Jiang et al., 2017; Nie et al., 2016; Stolee
et al., 2014).

_Code Search._ Code search is a typical testbed for pre-trained code models
such as CodeBERT (Feng et al., 2020). The task aims to find code snippets from
a codebase that is most relevant to a given query.

_Code Summarization._ Code summarization aims to generate a natural language
summary for an input code snippet. It has also been widely used for evaluating
pre-trained models for source code (Feng et al., 2020; Wang et al., 2021).
Through this task, we want to verify whether program simplification by
DietCode is effective in generation tasks.

###  5.2. Datasets

Table 2. Statistics of Datasets Corpus | Training | Test
---|---|---
CodeSearchNet (Java) | 908,886 | 1,000,000
CodeSearchNet (Python) | 824,343 | 1,000,000

We use the CodeSearchNet to fine-tune and test our model (Husain et al.,
2019), which contains ¡comment, code¿ pairs collected from open source
projects. _code_ means the code snippet of a method, while _comment_ is the
description of the code that was mainly collected from comments for the whole
functions such as Javadocs or docstrings in Python. The statistics of
CodeSearchNet is shown in Table 2.

The original data of CodeSearchNet are in the format of token sequences. We
preprocess the data by parsing them into statements. We parse statements by
splitting brackets and semicolons according to the common guidance of Java
(Gosling et al., 2000). For Python code, there are no delimiters because the
indentation is missing in the dataset. Besides, Python does not use brackets
and semicolons. Hence, we split statements using other hint symbols such as
“def”, “=”, “:”, and “)”.

To reduce the vocabulary size of code tokens, we delexicalize all string
constants to a generic token string and all numerical constants to the same
token 10. We conserve special numbers such as 0, 1, and -1, which can belong
to boolean values.

###  5.3. Evaluation Metrics

First, we want to measure the maximum extent of code reduction that DietCode
can achieve without losing much accuracy. We define Relative Length (RL) to
measure how much of the code is remained after simplification. It is computed
as the percentage of the length of the simplified code snippet $|C_{p}|$ with
respect to the length of the original code $|C|$:

(7) $RL=\frac{|C_{p}|}{|C|}\times 100\%$

where —$\cdot$— denotes the length of a code snippet (i.e., number of tokens).
The smaller the relative length, the greater the simplification to the
original code.

We also use FLOPs (floating point operations) (Hunger, 2005) to measure the
effect of model reduction. FLOPs is a widely used metric to measure the
complexity of a machine learning model. The higher the FLOPs, the slower the
processing of the model.

The third metric is the time cost, including fine-tuning time (FT Time) and
testing time. We calculate the execution time of DietCode for fine-tuning and
testing, measured by the number of hours from the program starting to the
termination.

Besides the metrics for complexity, we use two standard metrics to evaluate
the effectiveness of DietCode in two downstream tasks respectively. We measure
the performance of code search using MRR (mean reciprocal rank), which refers
to the average of the multiplicative inverse of the position for the first
correct answer for the query (Husain et al., 2019).

We measure the performance of code summarization using the BLEU-4 (bilingual
evaluation understudy) score (Lewis et al., 2020), which calculates the
average of n-gram precision on a couple of sequences with a penalty for short
sequences.

Table 3. Performance of various code simplification methods on the code search task ($L_{\mathrm{in}}$=input length; RL=relative length; FT=fine-tuning). | Java |  | Python
---|---|---|---
Model | $L_{\mathrm{in}}$ | RL | FT Time | Test Time | FLOPs | MRR |  | $L_{\mathrm{in}}$ | RL | FT Time | Test Time | FLOPs | MRR
BiRNN (Cho et al., 2014) | 200 | 100% | 9.88h | 1.13h | 8.34G | 0.29 |  | 200 | 100% | 7.07h | 1.25h | 8.34G | 0.32
SelfAttn (Vaswani et al., 2017) | 200 | 100% | 22.83h | 4.00h | 16.99G | 0.59 |  | 200 | 100% | 17.78h | 2.67h | 16.99G | 0.69
RoBERTa (Liu et al., 2019) | 200 | 100% | 23.85h | 4.78h | 16.99G | 0.67 |  | 200 | 100% | 19.32h | 3.53h | 16.99G | 0.81
RoBERTa (code) | 200 | 100% | 21.02h | 4.53h | 16.99G | 0.72 |  | 200 | 100% | 20.78h | 4.07h | 16.99G | 0.84
CodeBERT (Feng et al., 2020) | 200 | 100% | 20.82h | 3.17h | 16.99G | 0.74 |  | 200 | 100% | 17.92h | 2.82h | 16.99G | 0.84
DietCode |  |  |  |  |  |  |  |  |  |  |  |  |
\- Attention | 120 | 60% | 11.08h | 1.83h | 10.19G | 0.71 |  | 120 | 60% | 9.62h | 1.82h | 10.19G | 0.81
\- Dropout | 120 | 60% | 10.73h | 1.95h | 10.19G | 0.68 |  | 120 | 60% | 9.33h | 1.93h | 10.19G | 0.80
\- Frequency | 120 | 60% | 10.32h | 1.8h | 10.19G | 0.66 |  | 120 | 60% | 8.67h | 1.79h | 10.19G | 0.78
CodeT5 (Wang et al., 2021) | 200 | 100% | 16.83h | 2.97h | 16.99G | 0.72 |  | 200 | 100% | 17.61h | 2.83h | 16.99G | 0.837
DietCode |  |  |  |  |  |  |  |  |  |  |  |  |
\- Attention | 120 | 60% | 9.3h | 1.74h | 10.19G | 0.71 |  | 120 | 60% | 8.31h | 1.81h | 10.19G | 0.813
\- Dropout | 120 | 60% | 9.25h | 1.67h | 10.19G | 0.68 |  | 120 | 60% | 9.33h | 1.93h | 10.19G | 0.799
\- Frequency | 120 | 60% | 8.97h | 1.58h | 10.19G | 0.66 |  | 120 | 60% | 8.67h | 1.79h | 10.19G | 0.785
Table 4. Performance of various code simplification methods on the code summarization task. | Java |  | Python
---|---|---|---
Model | $L_{\mathrm{in}}$ | RL | FT Time | Test Time | FLOPs | BLEU-4 |  | $L_{\mathrm{in}}$ | RL | FT Time | Test Time | FLOPs | BLEU-4
Seq2Seq (Cho et al., 2014) | 256 | 100% | 6.26h | 1.26h | 12.750G | 15.09 |  | 256 | 100% | 4.43h | 1.02h | 12.750G | 15.93
Transformer (Vaswani et al., 2017) | 256 | 100% | 13.28h | 5.43h | 24.328G | 16.26 |  | 256 | 100% | 9.70h | 2.43h | 24.328G | 15.81
RoBERTa (Liu et al., 2019) | 256 | 100% | 15.42h | 5.22h | 24.328G | 16.47 |  | 256 | 100% | 10.63h | 1.88h | 24.328G | 18.14
RoBERTa (code) | 256 | 100% | 14.5h | 6.02h | 24.328G | 17.50 |  | 256 | 100% | 10.45h | 2.05h | 24.328G | 18.58
CodeBERT (Feng et al., 2020) | 256 | 100% | 13.82h | 4.8h | 24.328G | 18.95 |  | 256 | 100% | 8.32h | 1.87h | 24.328G | 19.04
DietCode |  |  |  |  |  |  |  |  |  |  |  |  |
\- Attention | 150 | 60% | 8.18h | 1.62h | 15.325G | 17.29 |  | 150 | 60% | 5.35h | 1.16h | 15.325G | 17.08
\- Dropout | 150 | 60% | 7.95h | 1.40h | 15.325G | 15.63 |  | 150 | 60% | 6.81h | 1.15h | 15.325G | 16.04
\- Frequency | 150 | 60% | 8.62h | 1.33h | 15.325G | 16.13 |  | 150 | 60% | 6.12h | 1.42h | 15.325G | 16.55
CodeT5 (Wang et al., 2021) | 256 | 100% | 16.91h | 4.88h | 54.01G | 20.46 |  | 256 | 100% | 9.68h | 1.48h | 54.01G | 20.37
DietCode |  |  |  |  |  |  |  |  |  |  |  |  |
\- Attention | 150 | 60% | 10.25h | 1.63h | 37.81G | 19.25 |  | 150 | 60% | 6.57h | 0.90h | 37.81G | 18.53
\- Dropout | 150 | 60% | 9.95h | 1.68h | 37.81G | 17.65 |  | 150 | 60% | 6.67h | 0.82h | 37.81G | 17.07
\- Frequency | 150 | 60% | 10.23h | 1.35h | 37.81G | 18.74 |  | 150 | 60% | 6.33h | 0.85h | 37.81G | 17.77

###  5.4. Experimental Setup

The demonstrate the strength of our approach, we simplify the input programs
for pre-training based models and compare the performance to that of the
original pre-trained model. Specifically, we compare our technique to the
vanilla versions of three pre-trained models:

  * •

CodeBERT (Feng et al., 2020): the original CodeBERT without code
simplification. We follow the experimental setup in the CodeBERT paper.

  * •

CodeT5 (Wang et al., 2021): a widely used pre-trained programming language
model based on the sequence-to-sequence architecture. CodeT5 has demonstrated
better performance on generative tasks (Wang et al., 2021).

  * •

RoBERTa (Liu et al., 2019): a popular extension of BERT that has demonstrated
significant improvement. The original RoBERTa was pre-trained in natural
languages. So we also report the results of RoBERTa (code) (Feng et al.,
2020), a variant that was pre-trained on source code.

Besides the pre-trained models, we also compare the accuracy of DietCode with
that of traditional deep learning approaches, including BiRNN (Cho et al.,
2014), SelfAttn (Vaswani et al., 2017), Seq2Seq (Cho et al., 2014), and
Transformer (Vaswani et al., 2017). As they are also baseline models for
CodeBERT, we directly take the results from the CodeBERT paper (Feng et al.,
2020).

Finally, we compare DietCode with SIVAND (Rabin et al., 2021), which is also a
program simplification method proposed by Rabin et al. (2021). SIVAND
111https://github.com/mdrafiqulrabin/SIVAND is a machine-learning-based
algorithm that recursively splits source code into fragments and measures its
importance through the method name prediction task. The algorithm selects
important fragments as the reduced code. In our experiments, we directly use
the code provided by the authors.

We implement our model based on the GitHub repository of CodeBERT
222https://github.com/microsoft/CodeBERT and CodeT5
333https://github.com/salesforce/CodeT5 using the default hyperparameter
settings. All models are optimized with the Adam algorithm (Kingma and Ba,
2017) with learning rates of 1$e$-5 and 5$e$-5 for the code search and code
summarization tasks respectively.

We run all models on a machine with a CPU of Intel(R) Xeon(R) Silver 4214R
2.40GHz and a GPU of Nvidia Tesla P40.

###  5.5. Experimental Results (RQ3)

Table 3 and 4 show the performance of DietCode in two downstream tasks.
Overall, DietCode reduces the computational cost by around 40% while keeping a
comparable accuracy to the original pre-trained models. The original CodeBERT
takes nearly one day for fine-tuning and more than 3 hours for code search on
the Java test set to achieve an MRR score of 0.74. In contrast, by reducing
the length of the input code to 60%, the fine-tuning and testing time can be
reduced to 11.08 hours and 1.83 hours, respectively. The FLOPs also drops from
16.99G to 10.19G. At the same time, the accuracy (MRR = 0.71) is comparable to
the original CodeBERT (MRR=0.74). It is worth noting that although the
performance drops slightly, it still significantly outperforms traditional
non-pretraining based methods such as BiRNN (MRR=0.29) and SelfAttn
(MRR=0.59).

DietCode on CodeT5 demonstrates a similar efficacy. The vanilla CodeT5
requires more than 16 hours for fine-tuning and around 3 hours for testing on
the Java code search task. By dropping out 40% input tokens using DietCode,
the fine-tuning and test time is reduced to around 9 and 1.6 hours,
respectively. Meanwhile, DietCode (attention) achieves a comparable
performance (MRR=0.71) to the original CodeT5 (MRR=0.72) with only a reduction
of 1.5%.

DietCode is also effective in the code summarization task. Taking Java as an
example, the vanilla CodeBERT achieves a BLEU-4 score of 18.95 at the expense
of 13.82 hours of fine-tuning and 4.8 hours of testing. When the target length
is set to 150 tokens (i.e., 60% of the original length), the fine-tuning time
is reduced to about 60% and the FLOPs drops from 24.328G to only 15.325G. This
does not sacrifice accuracy (BLEU-4=17.29).

Comparing the three pruning strategies, DietCode with attention shows strength
over the two other strategies. For example, DietCode with attention-based
pruning achieves an MRR of 0.71 in the Java code search task, which is better
than dropout (MRR=0.68) and frequency filtering (MRR=0.66). The results
suggest that by finer-grained pruning of tokens based on attention weights,
DietCode can achieve more effective program simplification. DietCode on the
CodeT5 demonstrates a similar trend in both tasks, where the attention-based
pruning achieves better performance (BLEU=19.25) than dropout (BLEU=17.65) and
frequency filtering (BLEU=18.74). We observe that this strength becomes less
significant in the Python language. We conjecture that the Python language
contains fewer auxiliary tokens (such as brackets), resulting in a more
uniform distribution of attention weights over all tokens. Therefore, removing
tokens with smaller attention is closer to removing random or frequent tokens
in the Python language.

As a noteworthy point, it is inapplicable to test the baseline model SIVAND in
our datasets, as it takes a massive amount of time (¿30,000 hours according to
our estimation) to process more than 1 million functions in the CodeSearchNet
benchmarks. This is mainly because the ddmin algorithm used by SIVAND is based
on backtracking, where each step the algorithm should invoke the deep learning
model for a prediction task. For this reason, we estimate the time cost of
SIVAND by sampling 50 functions from CodeSearchNet. Results show that it costs
104 and 77 minutes respectively in the CodeSearchNet (Java) and CodeSearchNet
(Python) datasets. Based on this observation, we estimate the testing time in
the entire dataset. Since the data we sample is small in size, it is
insufficient to fine-tune the model to validate the accuracy.

###  5.6. Effect of Relative Length (RQ4)

Figure 6 shows the performance of DietCode under different relative lengths
and pruning strategies. We can see that the performance of all pruning
strategies drops sharply as the relative length decreases. In both two tasks,
DietCode with attention performs better than the other two pruning strategies
under all relative lengths. When the relative length is above 70%, the
performance is comparable to that of the original CodeBERT but the reduction
of computational cost can be modest. When the relative length drops below 50%,
the performance is deficient since most of the code has been pruned. A
relative length of around 60% is probably the best trade-off for these two
tasks.

(a) results on code search

(b) results on code summarization

Figure 6. Performance under different relative lengths on Java.

###  5.7. Effect of Token and Statement Pruning (RQ5)

Figure 7 shows the performance of DietCode with token and statement pruning on
the two tasks. In order to verify the effect of statement pruning, we only run
the statement selection phase in Algorithm 1. To test the effect of token
pruning, we drop the lowest attention tokens directly until meeting the target
length. As we can see from the results, a significant drop in performance is
observed for both strategies as the relative length decreases. When 90% code
remains, the MRR scores of the two pruning strategies are close. As the
relative length decreases, the score of the token pruning strategy drops much
faster than that of the statement pruning strategy. When the relative length
decreases further, their MRR scores drop dramatically. The results suggest
that statements are more critical than tokens in learning code representations
by CodeBERT. One possible reason could be that token attention usually
measures local information, while statement attention considers the
relationship between tokens. Therefore, statement attention could keep more
semantic of the functions. The code summarization task shares a similar result
as the code search task.

(a) results on code search

(b) results on code summarization

Figure 7. Ablation results of token and statement pruning on Java.

##  6\. Discussion

###  6.1. How Can Pre-Trained Models Understand Simplified Code?

One debatable question is how can pre-trained models understand simplified
code which is not compilable and runnable. Source code involves two channels
of information: formal & natural (Casalnuovo et al., 2020; Chakraborty et al.,
2020). It can either be considered as programs for computers to execute or as
a specific natural language for humans to communicate (Hindle et al., 2012).
The former requires the source code to be strictly compilable and runnable,
while the latter focuses more on conveying information to humans. We believe
that CodeBERT considers more about the natural channel of source code (Hindle
et al., 2012; Chakraborty et al., 2020). As such, it pays more attention to
keywords without necessarily having to know how the program actually behaves
during execution.

Our empirical findings are in agreement with a previous human study on how
programmers summarize source code (Rodeghero et al., 2014), which shows that
developers usually start by reading the function name. They may skip some
structural information such as For and If conditions while paying special
attention to literal information such as method invocations and variable
names, which literally show the intention of the code (Rodeghero et al.,
2014). The pruning algorithms described in our paper make use of this finding
and simplify source code by only selecting critical information (e.g.,
reflected by the attentions of CodeBERT) in the source code. Therefore, they
do not have much impact on the understanding of source code.

###  6.2. What users may adopt the techniques?

One debatable question is what users may adopt the technique since it has a
precision loss. From the results in Table 3 and 4, although the performance
drops slightly, it still significantly outperforms traditional non-pretraining
based methods such as BiRNN and SelfAttn. Meanwhile, DietCode shows an
advantage of computational efficiency (e.g., saving 40% of fine-tuning time).
Hence, DietCode provides a practical option for users with limited
computational resources but still want quick leverage of large pre-trained
models.

###  6.3. The role of the 0-1 knapsack formulation

One may question whether we really need to transform the problem into the 0-1
knapsack. In our preliminary studies, simply pruning statements often results
in sequences that are either too long or too short. Token pruning provides a
finer-grained pruning to the input program. This amounts to selecting
statements and tokens to obtain the maximum attention while satisfying the
length restriction. Hence, we formulate it as a 0-1 knapsack problem and solve
it using a greedy strategy. According to the experimental results in Figure 7,
a simple statement pruning archives an MRR of around 0.68 on Java code search
when the relative length is 60%, which is evidently lower than that of
DietCode (MRR=0.71). The same comparison can be observed on the Java code
summarization task (i.e., 16.8 vs. 17.3 in terms of BLEU). This suggests the
effectiveness of the 0-1 knapsack formulation.

###  6.4. Implications for Future Research

Through our empirical study, we find that CodeBERT does not recognize grammar
and structural information very well. For example, the if condition, for
condition, and while condition are three typical statements representing code
structures, but they are rarely considered by pre-trained models when learning
program representations. This motivates future research on better
incorporating code structures into pre-trained code models, for example,
converting structural symbols (e.g., the bracket } ) to a more verbal style
(e.g., ‘the end of a for statement’) before feeding into pre-trained models.

Besides DietCode, there is a broader class of techniques, including model
compression (Shen et al., 2020), model distillation (Sanh et al., 2019), and
data reduction (Ye et al., 2021), which aim to reduce the computational
complexity of large pre-trained models at the cost of a slight decrease in
performance. DietCode provides an easy, alternative solution by only pruning
input programs. We believe this is more practical for developers as they only
need to process the data without modifying the model. In the future, we can
investigate more techniques such as model compression and distillation.

###  6.5. Threats to Validity

_Internal Threats._ When calculating the attention weights for statements, we
encounter the out-of-vocabulary (OOV) issue. We resolve this issue by
excluding rare categories of statements in our experiments. Nevertheless, some
categories of statements could still be necessary though having a low quantity
in the corpus. Furthermore, the raw data provided by CodeSearchNet is in the
format of plain text. We parse statements using text processing rules designed
by ourselves. However, there could be irregular patterns that our parser can
not recognize. This could cause noise in our dataset and affect the results of
our research.

_External Threats._ We have just conducted our experiments in Java and Python.
Though the conclusions from both languages are similar, other programming
languages such as LISP and Erlang could have different attention patterns. In
addition, DietCode is evaluated in two downstream tasks: code search and code
summarization. However, these tasks rely much on the literal information
provided in the source code. Thus, it remains to be verified whether or not
the proposed simplification algorithm is applicable to other software
engineering tasks.

##  7\. Related Work

###  7.1. Understanding Pre-trained Models of Code

Besides our work, there have been other studies that also try to explain the
mechanisms of pre-trained models for code (Ahmad et al., 2021; Mastropaolo et
al., 2021; Rogers et al., 2020; Paltenghi and Pradel, 2021). Karmakar and
Robbes (2021) applied four probing tasks on pre-trained code models to
investigate whether pre-trained models can learn different aspects of source
code such as syntactic, structural, surface-level, and semantic information.
Different from our work, they only empirically study the whole pre-trained
model, whereas we focus on more specific (critical tokens and statements)
knowledge learned by pre-trained models.

There have also been many works that investigate the attention weights of pre-
trained models for source code. For example, Wan et al. (2022) performed a
structural analysis of pre-trained language models for source code. They
analyzed the self-attention weights and found that the Transformer attention
can capture high-level structural information of source code. AutoFocus (Bui
et al., 2019) aims to reveal the most relevant part of the code to
programmers. They measure the relevance of statements using attention weights
from a GGNN (Allamanis et al., 2018). Different from our approach, they
capture structural knowledge learned by pre-trained models, while we dig more
into critical statements and tokens learned by pre-trained models.
Furthermore, we propose simplifying programs for pre-trained language models
based on the findings.

###  7.2. Program Simplification

Program simplification has gained increasing attention recently. The state-of-
the-art methods such as SIVAND (Rabin et al., 2021) and P2IM (Suneja et al.,
2021) a based on the delta debugging prototype (Zeller and Hildebrandt, 2002).
The delta debugging mechanism requires an input code snippet and an auxiliary
deep learning model such as the code2vec (Alon et al., 2019). The deep
learning model takes as input the code snippet and splits it into fragments.
Each fragment is then taken as input to the neural network model to perform
testing tasks such as method name prediction and misused variables detection.
If a fragment obtains a satisfying score, the program will split it further.
The process continues until the performance of the subset does not satisfy the
target score. Finally, the algorithm produces the smallest code snippet that
satisfies the objective of the deep model.

Compared to DietCode, their methods are computationally inefficient because
they need to run an auxiliary deep learning model and evaluate the performance
at each iteration. For example, it costs hundreds of hours for SIVAND to
process 10,000 functions, while DietCode can complete it within two minutes.

##  8\. Conclusion

This paper empirically analyzes the critical information learned by CodeBERT,
including important tokens and statements in both Java and Python. Our results
show that CodeBERT focuses on keywords and data-relevant statements such as
method signatures and return statements. Based on our empirical findings, we
propose a novel approach named DietCode for lightweight leverage of pre-
trained models. DietCode simplifies the input code to a target length by
selecting important statements and tokens based on their attention weights
using a 0-1 Knapsack algorithm. Experiments on two tasks have shown that
DietCode provides comparable results as CodeBERT, with the advantage of
computational efficiency.

In the future, we will consider more aspects that CodeBERT learns about code,
such as syntax rules and semantic relations, to further reduce the size of
source code for pre-trained models. We will also investigate model compression
(Cheng et al., 2017, 2018) and distillation (Sanh et al., 2019) techniques to
further reduce the size of pre-trained programming language models.

Our source code and experimental data are publicly available at
https://github.com/zhangzwwww/DietCode

##  9\. Acknowledge

This work was sponsored by NSFC No. 62102244, CCF-Tencent Open Research Fund
(RAGR20220129), and CCF-Baidu Open Fund (NO. 2021PP15002000).

## References

  * (1)
  * Ahmad et al. (2021) Wasi Ahmad, Saikat Chakraborty, Baishakhi Ray, and Kai-Wei Chang. 2021.  Unified Pre-training for Program Understanding and Generation. In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_. 2655–2668.
  * Allamanis et al. (2018) Miltiadis Allamanis, Marc Brockschmidt, and Mahmoud Khademi. 2018\.  Learning to Represent Programs with Graphs. In _International Conference on Learning Representations_.
  * Alon et al. (2019) Uri Alon, Meital Zilberstein, Omer Levy, and Eran Yahav. 2019.  code2vec: learning distributed representations of code.  _Proceedings of the ACM on Programming Languages_ 3, POPL (2019), 1–29.
  * Bahdanau et al. (2015) Dzmitry Bahdanau, Kyung Hyun Cho, and Yoshua Bengio. 2015\.  Neural machine translation by jointly learning to align and translate. In _Proceedings of the 3rd International Conference on Learning Representations (ICLR)_.
  * Bui et al. (2019) Nghi DQ Bui, Yijun Yu, and Lingxiao Jiang. 2019.  Autofocus: interpreting attention-based neural networks by code perturbation. In _Proceedings of 34th IEEE/ACM International Conference on Automated Software Engineering (ASE)_. IEEE, 38–41.
  * Casalnuovo et al. (2020) Casey Casalnuovo, E Morgan, and P Devanbu. 2020.  Does surprisal predict code comprehension difficulty. In _Proceedings of the 42nd Annual Meeting of the Cognitive Science Society_. Cognitive Science Society Toronto, Canada.
  * Chakraborty et al. (2020) Saikat Chakraborty, Toufique Ahmed, Yangruibo Ding, Premkumar Devanbu, and Baishakhi Ray. 2020\.  NatGen: Generative pre-training by” Naturalizing” source code. In _Proceedings of the 30th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE)_.
  * Cheng et al. (2017) Yu Cheng, Duo Wang, Pan Zhou, and Tao Zhang. 2017\.  A survey of model compression and acceleration for deep neural networks.  _arXiv preprint arXiv:1710.09282_ (2017).
  * Cheng et al. (2018) Yu Cheng, Duo Wang, Pan Zhou, and Tao Zhang. 2018\.  Model compression and acceleration for deep neural networks: The principles, progress, and challenges.  _IEEE Signal Processing Magazine_ 35, 1 (2018), 126–136.
  * Cho et al. (2014) Kyunghyun Cho, Bart van Merrienboer, Çaglar Gülçehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. 2014\.  Learning phrase representations using RNN encoder-decoder for statistical machine translation. In _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_.
  * Ciniselli et al. (2021) Matteo Ciniselli, Nathan Cooper, Luca Pascarella, Denys Poshyvanyk, Massimiliano Di Penta, and Gabriele Bavota. 2021.  An empirical study on the usage of BERT models for code completion. In _2021 IEEE/ACM 18th International Conference on Mining Software Repositories (MSR)_. IEEE, 108–119.
  * Clark et al. (2019) Kevin Clark, Minh-Thang Luong, Quoc V Le, and Christopher D Manning. 2019.  ELECTRA: Pre-training Text Encoders as Discriminators Rather Than Generators. In _International Conference on Learning Representations_.
  * Conneau and Lample (2019) Alexis Conneau and Guillaume Lample. 2019.  Cross-lingual language model pretraining.  _Advances in neural information processing systems_ 32 (2019).
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_. 4171–4186.
  * Feng et al. (2020) Zhangyin Feng, Daya Guo, Duyu Tang, Nan Duan, Xiaocheng Feng, Ming Gong, Linjun Shou, Bing Qin, Ting Liu, Daxin Jiang, et al. 2020\.  CodeBERT: a pre-Trained model for programming and natural languages. In _Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP): Findings_. 1536–1547.
  * Gosling et al. (2000) James Gosling, Bill Joy, Guy Steele, and Gilad Bracha. 2000\.  _The Java language specification_.  Addison-Wesley Professional.
  * Haiduc et al. (2010) Sonia Haiduc, Jairo Aponte, and Andrian Marcus. 2010\.  Supporting program comprehension with source code summarization. In _Proceedings of ACM/IEEE 32nd international conference on software engineering (ICSE)_ , Vol. 2. IEEE, 223–226.
  * Hindle et al. (2012) Abram Hindle, Earl T Barr, Zhendong Su, Mark Gabel, and Premkumar Devanbu. 2012.  On the naturalness of software. In _2012 34th International Conference on Software Engineering (ICSE)_. IEEE, 837–847.
  * Hunger (2005) Raphael Hunger. 2005\.  _Floating point operations in matrix-vector calculus_.  Munich University of Technology, Inst. for Circuit Theory and Signal.
  * Husain et al. (2019) Hamel Husain, Ho-Hsiang Wu, Tiferet Gazit, Miltiadis Allamanis, and Marc Brockschmidt. 2019.  Codesearchnet challenge: evaluating the state of semantic code search.  _arXiv preprint arXiv:1909.09436_ (2019).
  * Iyyer et al. (2015) Mohit Iyyer, Varun Manjunatha, Jordan Boyd-Graber, and Hal Daumé III. 2015.  Deep unordered composition rivals syntactic methods for text classification. In _Proceedings of the 53rd annual meeting of the association for computational linguistics and the 7th international joint conference on natural language processing (volume 1: Long papers)_. 1681–1691.
  * Jiang et al. (2017) Siyuan Jiang, Ameer Armaly, and Collin McMillan. 2017\.  Automatically generating commit messages from diffs using neural machine translation. In _Proceedings of 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE)_. IEEE, 135–146.
  * Kamiya et al. (2002) Toshihiro Kamiya, Shinji Kusumoto, and Katsuro Inoue. 2002\.  CCFinder: A multilinguistic token-based code clone detection system for large scale source code.  _IEEE Transactions on Software Engineering (TSE)_ 28, 7 (2002), 654–670.
  * Karmakar and Robbes (2021) Anjan Karmakar and Romain Robbes. 2021.  What do pre-trained code models know about code?. In _2021 36th IEEE/ACM International Conference on Automated Software Engineering (ASE)_. IEEE, 1332–1336.
  * Kim et al. (2021) Sehoon Kim, Sheng Shen, David Thorsley, Amir Gholami, Woosuk Kwon, Joseph Hassoun, and Kurt Keutzer. 2021.  Learned token pruning for transformers.  _arXiv preprint arXiv:2107.00910_ (2021).
  * Kingma and Ba (2017) Diederik P. Kingma and Jimmy Ba. 2017.  Adam: a method for stochastic optimization.  arXiv:1412.6980 [cs.LG]
  * Lewis et al. (2020) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. 2020.  BART: Denoising Sequence-to-Sequence Pre-training for Natural Language Generation, Translation, and Comprehension. In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_. 7871–7880.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: a robustly optimized BERT pretraining approach.  _arXiv preprint arXiv:1907.11692_ (2019).
  * Lu et al. (2021) Shuai Lu, Daya Guo, Shuo Ren, Junjie Huang, Alexey Svyatkovskiy, Ambrosio Blanco, Colin Clement, Dawn Drain, Daxin Jiang, Duyu Tang, et al. 2021\.  CodeXGLUE: A Machine Learning Benchmark Dataset for Code Understanding and Generation. In _Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 1)_.
  * Mastropaolo et al. (2021) Antonio Mastropaolo, Simone Scalabrino, Nathan Cooper, David Nader Palacio, Denys Poshyvanyk, Rocco Oliveto, and Gabriele Bavota. 2021\.  Studying the usage of text-to-text transfer transformer to support code-related tasks. In _Proceedings of IEEE/ACM 43rd International Conference on Software Engineering (ICSE)_. IEEE, 336–347.
  * Nie et al. (2016) Liming Nie, He Jiang, Zhilei Ren, Zeyi Sun, and Xiaochen Li. 2016.  Query expansion based on crowd knowledge for code search.  _IEEE Transactions on Services Computing_ 9, 5 (2016), 771–783.
  * Paltenghi and Pradel (2021) Matteo Paltenghi and Michael Pradel. 2021.  Thinking Like a Developer? Comparing the Attention of Humans with Neural Models of Code. In _2021 36th IEEE/ACM International Conference on Automated Software Engineering (ASE)_. IEEE, 867–879.
  * Pisinger (1995) David Pisinger. 1995\.  Algorithms for knapsack problems.  (1995).
  * Rabin et al. (2021) Md Rafiqul Islam Rabin, Vincent J. Hellendoorn, and Mohammad Amin Alipour. 2021.  Understanding neural code intelligence through program simplification. In _Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE)_. Association for Computing Machinery, 441–452.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. 2019\.  Language models are unsupervised multitask learners.  _OpenAI blog_ 1, 8 (2019), 9.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _Journal of Machine Learning Research_ 21 (2020), 1–67.
  * Rodeghero et al. (2014) Paige Rodeghero, Collin McMillan, Paul W McBurney, Nigel Bosch, and Sidney D’Mello. 2014.  Improving automated source code summarization via an eye-tracking study of programmers. In _Proceedings of the 36th international conference on Software engineering_. 390–401.
  * Rogers et al. (2020) Anna Rogers, Olga Kovaleva, and Anna Rumshisky. 2020\.  A primer in bertology: what we know about how BERT works.  _Transactions of the Association for Computational Linguistics_ 8 (2020), 842–866.
  * Sanh et al. (2019) Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. 2019.  DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter.  _arXiv preprint arXiv:1910.01108_ (2019).
  * Shen et al. (2020) Sheng Shen, Zhen Dong, Jiayu Ye, Linjian Ma, Zhewei Yao, Amir Gholami, Michael W Mahoney, and Kurt Keutzer. 2020\.  Q-BERT: Hessian based ultra low precision quantization of BERT. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 34. 8815–8821.
  * Stolee et al. (2014) Kathryn T Stolee, Sebastian Elbaum, and Daniel Dobos. 2014\.  Solving the search for source code.  _ACM Transactions on Software Engineering and Methodology (TOSEM)_ 23, 3 (2014), 1–45.
  * Suneja et al. (2021) Sahil Suneja, Yunhui Zheng, Yufan Zhuang, Jim A Laredo, and Alessandro Morari. 2021.  Probing model signal-awareness via prediction-preserving input minimization. In _Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering_. 945–955.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need. In _Advances in neural information processing systems (NeurlPS 2017)_. 5998–6008.
  * Wan et al. (2022) Yao Wan, Wei Zhao, Hongyu Zhang, Yulei Sui, Guandong Xu, and Hai Jin. 2022\.  What do they capture? – a structural analysis of pre-trained language models for source code. In _In Proceedings of the 44th International Conference on Software Engineering (ICSE)_.
  * Wang et al. (2021) Yue Wang, Weishi Wang, Shafiq Joty, and Steven CH Hoi. 2021\.  CodeT5: Identifier-aware Unified Pre-trained Encoder-Decoder Models for Code Understanding and Generation. In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_. 8696–8708.
  * White et al. (2016) Martin White, Michele Tufano, Christopher Vendome, and Denys Poshyvanyk. 2016.  Deep learning code fragments for code clone detection. In _Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering (ASE)_. IEEE, 87–98.
  * Yang et al. (2019) Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ R Salakhutdinov, and Quoc V Le. 2019\.  Xlnet: generalized autoregressive pretraining for language understanding.  _Advances in neural information processing systems_ 32 (2019).
  * Ye et al. (2021) Deming Ye, Yankai Lin, Yufei Huang, and Maosong Sun. 2021\.  TR-BERT: Dynamic Token Reduction for Accelerating BERT Inference. In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_. 5798–5809.
  * Zeller and Hildebrandt (2002) Andreas Zeller and Ralf Hildebrandt. 2002.  Simplifying and isolating failure-inducing input.  _IEEE Transactions on Software Engineering_ 28, 2 (2002), 183–200.
  * Zhang et al. (2019) Jian Zhang, Xu Wang, Hongyu Zhang, Hailong Sun, Kaixuan Wang, and Xudong Liu. 2019\.  A novel neural source code representation based on abstract syntax tree. In _Proceedings of IEEE/ACM 41st International Conference on Software Engineering (ICSE)_. IEEE, 783–794.


# Multi-Mosaics: Corpus Summarizing and Exploration using multiple Concordance
Mosaic Visualisations

Shane Sheehan<EMAIL_ADDRESS>University of EdinburghUnited Kingdom ,
Saturnino Luz<EMAIL_ADDRESS>University of EdinburghUnited Kingdom and
Masood Masoodian<EMAIL_ADDRESS>Aalto UniversityFinland

###### Abstract.

Researchers working in areas such as lexicography, translation studies, and
computational linguistics, use a combination of automated and semi-automated
tools to analyze the content of text corpora. Keywords, named entities, and
events are often extracted automatically as the first step in the analysis.
Concordancing – or the arranging of passages of a textual corpus in
alphabetical order according to user-defined keywords – is one of the oldest
and still most widely used forms of text analysis. This paper describes Multi-
Mosaics, a tool for corpus analysis using multiple implicitly linked
Concordance Mosaic visualisations. Multi-Mosaics supports examining linguistic
relationships within the context windows surrounding extracted keywords.

Figure 1. Top left Concordance Mosaic displaying the primary keyword gold.
Three secondary keywords (iron, bronze and silver) are presented and colored
to highlight the most frequent context words from the primary Mosaic.

##  1\. Introduction

In many academic fields, corpus analysis is central to the study of texts.
Computational tools have long been used for lexicography, corpus linguistics,
and corpus-based translation studies (Svartvik, 2011; Bernardini and Kenny,
2020; Baker, 1993), and new methods motivated by such tools have been more
broadly applied to the study of policy in areas such as medicine (Buts et al.,
2021) and politics (Buts, 2020). One of the most popular techniques supported
by computation is the indexing, retrieval and display of keyword-in-context.
This technique dates back to at least the 1950’s with Luhn’s work on
concordance indexing (Luhn, 1960).

Corpus analysis using concordance and collocation provides a data-driven
approach for corpus analysis – contrasting with more traditional scholarly
work in these fields which requires close reading, researchers’ prior
knowledge, and theoretical frameworks to interpret texts. Data-driven corpus
analysis techniques are heavily influenced by the work of John Sinclair and
Michael Halliday (Léon, 2007; Sinclair, 1991), in which one usually starts by
obtaining an overview of the data and exploring a much larger volume of text
than would be practical to do by close reading of the texts. Visualization
tools can aid this process by providing effective overviews and helping to
identify patterns in the texts, as well as visual explanation of the analysis
outputs (Tufte, 1990).

Concordance Mosaic (Luz and Sheehan, 2014) is a visualisation tool which has
been adopted by members of the corpus linguistic community for corpus
analysis, and the presentation of their scholarly work (Baker, 2020; Buts,
2020) . The visualisation provides an overview of the context words within a
window of the selected keyword. Quantitative information – most often word
frequency – is encoded using tile height allowing the analyst to identify
positional collocation patterns around a single keyword.

This paper presents Multi-Mosaics, as an extension of Concordance Mosaic, to
enable comparison of collocation patterns for multiple keywords. The design of
Multi-Mosaics has been informed by observations, and requirements gathered
using Concordance Mosaic. This paper also presents a user study where the
Concordance Mosaic is compared to a traditional keyword-in-context textual
display.

##  2\. Related Work

Keyword visualisations often take the form of networks or clusters of
keywords(Isenberg et al., 2017; Li et al., 2016; Choi and Hwang, 2014). While
these visualisations are useful for identifying similar or connected keywords
in a corpus, they do not provide any insight into the collocations of the
keywords, and as such, they are not directly usefully for comparing the
contexts in which these keywords appear.

Corpus Clouds (Culy and Lyding, 2011) is a frequency-focused corpus analysis
tool. A word cloud, based on the tag cloud visualisation (Viégas and
Wattenberg, 2008), is used to encode the frequencies of all words returned by
a corpus query. For quantitative tasks involving frequency estimation or
comparison, the use of font size to encode value in cloud-based visualisations
is a limitation (Felix et al., 2018). Also, since positional collocations are
not encoded in Corpus Clouds, the visualisation is of an entire context
window.

TagSpheres (Jänicke and Scheuermann, 2017) are word cloud based visualisation
where keyword co-occurrences are encoded using an integral combination of
color and radial position from the central keyword. The cloud layout places
the same word from different positions close together to help identify strong
collocation patterns. However, the linear structure of the text is removed
making it difficult to identify multi-word collocation patterns.

Tree-based visualisations of keyword-in-context have therefore been proposed
as a technique for encoding quantitative information while maintaining the
linear structure of the text (Culy and Lyding, 2010; Luz and Sheehan, 2014;
Wattenberg and Viégas, 2008). In practice, however, displaying a large number
of concordance lines, where font size is used to encode represent positional
frequency, requires a trade off between frequency estimation and readability.
The variable length of words also makes encoding frequency using font size
challenging – since area is not as perceptually efficient as length for
visualising quantitative information.

##  3\. Multi-Mosaics

Figure 2. Textual keyword-in-context linked to Multi-Mosaics. The Mosaic for
the keyword silver is selected and the word talents at position keyword minus
2 was chosen using the Mosaic.

concordance

Multi-Mosaics was designed in collaboration with language scholars who work
predominantly using corpus analysis techniques. During this co-design process
two of the researchers were asked to compile a list 20 questions which they
would like to be able to answer about a corpus. They were asked to list them
in order of importance, and after the lists were compiled they were used to
discuss requirements for a potential visualisation prototype. This technique
is a common means of requirements elicitation in human-computer interaction
(Marai, 2018).

This process revealed a need for a tool which facilitated quantitative
analysis of the words surrounding a keyword (Luz and Sheehan, 2020).
Concordance Mosaic was developed to address this need, where each mosaic
visualization displays quantitative information – such as word frequency or
collocation strength – in tiles representing words at positions relative to a
keyword. The height of each word tile encodes the quantity, and the horizontal
position of the columns represents word position relative to the keyword. In
Figure 1 (top left) we see that the most frequent word occurring directly to
the left of the keyword gold is the word of.

The language scholars also mentioned the need to investigate multiple keywords
for similar patterns or to investigate lists of suggested keywords for a
corpus. The following suggests that investigating collocation patterns of
multiple words simultaneously would be useful “…if the keyword is a label used
to describe a particular kind of political agent, we might be interested to
look at what collective nouns are used to group and characterize these
political agents (e.g. a mob of citizens, a tribe of politicians: LEFT +2). ”.
Similarly it was suggested that automatically extracting related keywords
would be useful to expand the analysis to include the collocations of these
keywords “Are there other related keywords we might study in order to expand
our investigation? Can the software suggest keywords that are important to
these texts but which we might not otherwise have thought of?”. Using these
observations the concept of multiple mosaics displayed together with linked
contexts was presented to the corpus linguists and the design was refined to
produce Multi-Mosaics.

###  3.1. Implementation

Multi-Mosaics111The code and example file format can be found at
https://github.com/sfermoy/MultiMosaic is implemented as a single-page web
application using the _D3.js_ framework (Bostock et al., 2011). The interface
displays a grid of Concordance Mosaics, generated from JSON files containing
keyword-in-context data, and a single textual keyword in context window.

There is no theoretical limit to the number of Concordance Mosaic
visualisations which can be displayed in Multi-Mosaics, as the interface is
scrollable. Each mosaic displays a single keyword and four word positions to
either side of the keyword. The Mosaic displayed in the top left position of
Multi-Mosaics is considered the primary Mosaic, and all others are secondary
Mosaics. Right clicking on a secondary Mosaic makes it the primary, and
updates Multi-Mosaics. In Figure 1 the primary Mosaic for the keyword gold is
selected.

Each mosaic is colored according to the 20 most frequent words in the 4-word
context window of the primary mosaic. This colouring allows the corpus analyst
to investigate each of the secondary Mosaics contexts in relation to the high
frequency context words from the primary Mosaic. Words not in the 20 most
frequent context words of the primary Mosaic are colored grey. When looking at
the contexts of secondary Mosaics, grey word tiles with high positional
frequencies are also likely to be of interest, since they represent words
which have high secondary keyword positional frequency, and low primary
keyword positional frequency. In Figure 1, looking at the secondary mosaic for
the keyword silver (bottom right), in relation to the primary Mosaic for the
keyword gold, we can identify interesting collocation patterns. For instance,
we can see that the word gold is a frequent collocate at position $keyword-2$,
and we can find silver in position $keyword+2$ for the Mosaic of gold. The
second most frequent word at position $keyword-2$ is the word talents – this
word is is not in the 20 most frequent words in the context of the primary
keyword gold so it is coloured grey.

In addition to the grid of Mosaics, a single textual keyword-in-context
concordance window is also available, as shown in Figure 2. Initially this
window displays the concordance lines from the primary keyword Mosaic.
However, left clicking on any tile, in any of the Mosaics, switches the
textual keyword-in-context window to display the concordance lines for the
clicked keyword. The keyword from the selected Mosaic is displayed centrally
and colored Blue – in Figure 2 the Mosaic for the keyword silver was clicked.
The tile which was clicked represented the word talents at the position
$keyword-2$, the concordance window is sorted alphabetically at this position
and the lines containing the clicked word at the chosen position are
highlighted in Cyan, the work which was clicked is coloured Pink. This enables
quick investigation of the lines from the corpus which form the identified
collocation pattern, in an overview and detail-on-demand interaction
(Shneiderman, 1996). In addition the Concordance Mosaic which was clicked will
have all words connection to the keyword highlighted in white, this helps with
identifying multi-word patterns of collocation.

##  4\. User study

This study was designed to compare the performance of the two visualisation
tools, the Concordance Mosaic and a textual Keyword-in-Context interface
(KWIC). A third option was also tested, in which both the Concordance Mosaic
and KWIC were available side-by-side. The evaluation was performed on
concordance analysis tasks for which the Concordance Mosaic was designed.
These tasks have been identified from analysis of the corpus methodology (Luz
and Sheehan, 2020), described by John Sinclair (Sinclair, 2003).

An initial heuristic evaluation and a pilot study were used to refine the
visualization tools and test their usability prior to the main user study.
During this study we found that tasks requiring analysis of multiple context
words or positions were difficult for non-expert users to understand. Based on
this we limited the evaluation to five simple quantitative analysis tasks,
only one of which required looking at multiple positions.

Each participant attempted to answer five questions using each of the 3
visualisation options – the order in which the options were presented was
randomised and balanced across participants for every possible combination of
option orderings. Similarly, for each visualisation option a different keyword
was required per question, and the keyword per option was balanced.

Question 1 was, for example, “For the keyword KEYWORD, what is the most
frequent word at position keyword - 1?”. The three possible keywords chosen
for this question were Wealthy, Daylight and Massive. These were chosen to
ensure a consistent number of concordance lines were returned from the corpus
used for this study, and that the difficulty level of the questions was
consistent. For question one these keywords all returned a concordance with
approximately 300 concordance lines – the most frequent word at position
$keyword-1$ occurs with a frequency of between 26–27%, and the second most
frequent word at position $keyword-1$ occurs with a frequency of 20–22%.
Question 2 was the same as the first one, but the frequencies of the most
common and second most common words at position $keyword-1$ were approximately
40% and between 5–10%, respectively – thus making this task more difficult.

The remaining three task questions were, Question 3: “For the keyword KEYWORD,
what is the most frequent descriptive adjective at position $keyword-1$?”,
Question 4: “For the keyword KEYWORD, focusing only on concordances that
contain the word CONTEXT-WORD at position $keyword-1$, what word is most
frequent at position $keyword-2$?”, Question 5: “Estimate which word has the
highest collocation strength at position $keyword-1$”. For the last question,
collocation strength was described as high frequency at a position but low
frequency in the corpus.

The participants were shown how to access the corpus frequency lists prior to
the study. It was possible to switch the Mosaic to collocation strength mode,
in which the tiles were scaled according to this metric.

The null hypothesis in this study was that: there is no significant difference
in performance between the three visualisation options, on concordance
analysis tasks. Performance was measured using the speed and accuracy with
which participants completed tasks.

For this study we recruited 36 participants from the student population
through our online university noticeboard and a mailing list. Since the study
evaluated performance on quantitative tasks, we decided that previous
experience with concordance tools or corpus analysis would not be a
prerequisite for participation.

###  4.1. Results

Table 1 shows the results of an ANOVA for the dependant variable t, time to
complete a task (in seconds), with respect to the categorical variables: the
question being answered (q), the visualisation being used (i), the
participants assigned visualisation option ordering (iOrder), the participants
assigned keyword set ordering (qOrder) and a binary variable representing a
correct or incorrect answer (isCorrect). The results of the ANOVA where a
significant difference ($p<.05$) was found are also shown.

Table 1. ANOVA results for the dependant variable time t, where p $<$ .05  Independent Variable | F Value | P Value
---|---|---
q | 26.9388 | $<2.2e^{-16}$
i | 135.5089 | $<2.2e^{-16}$
isCorrect | 4.3170 | 0.038894
q:i | 8.0946 | $1.428e^{-9}$
i:iOrder | 2.8620 | 0.002261
i:qOrder | 3.5232 | 0.008239
q:isCorrect | 2.4258 | 0.048970

Since the main effects q, i and isCorrect all feature in significant
interactions, we have focused our post-hoc analysis on these interactions
instead of the main effects. We conducted Tukey’s post-hoc tests (HSD) to
analyse the different groupings of each interaction effect, again using p $<$
.05 to test for significance.

The result of the HSD test for the i and qOrder interaction (i:qOrder) showed
a significant difference between two groupings. In this case, the data set was
split into 9 groups by the combinations of the 3 visualisation options and the
3 circularly shifted keyword set orderings. The HSD groupings simply combined
these groups into data points where the KWIC option was being used, and a
grouping of all data points where either the Mosaics or combined
visualisations were being used. This indicates that the interaction can be
interpreted as i, and that qOrder can be safely ignored, as it does not
feature in any other significant interactions or as a main effect. This result
shows, as expected, that our choice of keywords has not had a major effect on
time to complete within each question.

The mean response times of the i:qOrder groups in which the KWIC option was
used were all greater than 67 seconds, while the remaining groups containing
the Mosaic and combined option all had mean response times under 30 seconds.
This is evidence of visualisation options having a large effect on response
time.

The discovery of an interaction between q and i (q:i) is of great interest
since our null hypothesis states: there are no significant differences between
the interfaces on a per question basis. Analysing the groups created by
splitting the data by visualisation options and questions, the Tukey HSD test
found a number of significant groupings. For each question there is a
significant difference in response time between the KWIC and both the Mosaics
and combined options. This is enough evidence to reject our null hypothesis
for each question.

##  5\. Conclusions

In this paper, we introduced Multi-Mosaics, a visualisation tool consisting of
multiple linked Concordance Mosaics and a textual keyword-in-context window.
Multi-Mosaics is designed to support the analysis of collocation patterns for
multiple keywords simultaneously. By encoding the most frequent collocations
from the primary keyword Mosaic onto all secondary Mosaics similar and
differing patterns of collocation can be identified in the secondary keywords.
In addition, linking the Mosaics to a textual Keyword-in-Context concordance
display allows for quick investigation of the lines of text making up the
identified collocation pattern. Our user study evaluating the effectiveness of
the visualisation tool shows that Concordance Mosaics perform better than a
textual keyword-in-context tool on a selection of quantitative corpus analysis
tasks.

###### Acknowledgements.

## References

  * (1)
  * Baker (1993) Mona Baker. 1993\.  Corpus linguistics and translation studies: Implications and applications.  _Text and technology: In honour of John Sinclair_ 233 (1993), 250\.
  * Baker (2020) Mona Baker. 2020\.  Rehumanizing the migrant: the translated past as a resource for refashioning the contemporary discourse of the (radical) left.  _Palgrave Communications_ 6, 1 (2020), 1–16.
  * Bernardini and Kenny (2020) S. Bernardini and D. Kenny. 2020.  Corpora.  In _The Routledge Handbook of Translation Studies_ , M. Bake and G. Saldanha (Eds.). Routledge, 110–115.  In press.
  * Bostock et al. (2011) Michael Bostock, Vadim Ogievetsky, and Jeffrey Heer. 2011\.  D3 Data-Driven Documents.  _IEEE Transactions on Visualization and Computer Graphics_ 17, 12 (Dec. 2011), 2301–2309.
  * Buts (2020) Jan Buts. 2020.  Community and authority in ROAR Magazine.  _Palgrave Communications_ 6, 1 (2020), 1–12.
  * Buts et al. (2021) Jan Buts, Mona Baker, Saturnino Luz, and Eivind Engebretsen. 2021\.  Epistemologies of evidence-based medicine: a plea for corpus-based conceptual research in the medical humanities.  _Medicine, Health Care and Philosophy_ (2021), 1–12.
  * Choi and Hwang (2014) Jinho Choi and Yong-Sik Hwang. 2014.  Patent keyword network analysis for improving technology development efficiency.  _Technological Forecasting and Social Change_ 83 (2014), 170–182.  https://doi.org/10.1016/j.techfore.2013.07.004
  * Culy and Lyding (2010) C. Culy and V. Lyding. 2010\.  Double Tree: An Advanced KWIC Visualization for Expert Users. In _Information Visualisation (IV), 2010 14th International Conference_. 98–103.  https://doi.org/10.1109/IV.2010.24
  * Culy and Lyding (2011) Chris Culy and Verena Lyding. 2011.  Corpus Clouds - Facilitating Text Analysis by Means of Visualizations.  In _Human Language Technology. Challenges for Computer Science and Linguistics_. Lecture Notes in Computer Science, Vol. 6562. Springer Berlin Heidelberg, 351–360.  https://doi.org/10.1007/978-3-642-20095-3_32
  * Felix et al. (2018) Cristian Felix, Steven Franconeri, and Enrico Bertini. 2018\.  Taking Word Clouds Apart: An Empirical Investigation of the Design Space for Keyword Summaries.  _IEEE Transactions on Visualization and Computer Graphics_ 24, 1 (2018), 657–666.  https://doi.org/10.1109/TVCG.2017.2746018
  * Isenberg et al. (2017) Petra Isenberg, Tobias Isenberg, Michael Sedlmair, Jian Chen, and Torsten Möller. 2017.  Visualization as Seen through its Research Paper Keywords.  _IEEE Transactions on Visualization and Computer Graphics_ 23, 1 (2017), 771–780.  https://doi.org/10.1109/TVCG.2016.2598827
  * Jänicke and Scheuermann (2017) Stefan Jänicke and Gerik Scheuermann. 2017.  On the Visualization of Hierarchical Relations and Tree Structures with TagSpheres. In _Computer Vision, Imaging and Computer Graphics Theory and Applications_ , José Braz, Nadia Magnenat-Thalmann, Paul Richard, Lars Linsen, Alexandru Telea, Sebastiano Battiato, and Francisco Imai (Eds.). Springer International Publishing, 199–219.
  * Léon (2007) Jacqueline Léon. 2007\.  Meaning by collocation.  In _History of Linguistics 2005_. John Benjamins, 404–415.
  * Li et al. (2016) Huajiao Li, Haizhong An, Yue Wang, Jiachen Huang, and Xiangyun Gao. 2016.  Evolutionary features of academic articles co-keyword network and keywords co-occurrence network: Based on two-mode affiliation network.  _Physica A: Statistical Mechanics and its Applications_ 450 (2016), 657–669.  https://doi.org/10.1016/j.physa.2016.01.017
  * Luhn (1960) H. P. Luhn. 1960\.  Key word-in-context index for technical literature (kwic index).  _American Documentation_ 11, 4 (1960), 288–295.  https://doi.org/10.1002/asi.5090110403
  * Luz and Sheehan (2014) S. Luz and S. Sheehan. 2014\.  A Graph Based Abstraction of Textual Concordances and Two Renderings for their Interactive Visualisation. In _Proceedings of the International Working Conference on Advanced Visual Interfaces_ (Como, Italy) _(AVI ’14)_. ACM, New York, NY, USA, 293–296.  https://doi.org/10.1145/2598153.2598187
  * Luz and Sheehan (2020) Saturnino Luz and Shane Sheehan. 2020.  Methods and visualization tools for the analysis of medical, political and scientific concepts in Genealogies of Knowledge.  _Palgrave Communications_ 6, 1 (2020), 1–20.
  * Marai (2018) G. E. Marai. 2018\.  Activity-Centered Domain Characterization for Problem-Driven Scientific Visualization.  _IEEE Transactions on Visualization and Computer Graphics_ 24, 1 (Jan 2018), 913–922.  https://doi.org/10.1109/TVCG.2017.2744459
  * Shneiderman (1996) Ben Shneiderman. 1996\.  The eyes have it: a task by data type taxonomy for information visualizations. In _Proceedings the IEEE Symposium on Visual Languages_. 336–343.  https://doi.org/10.1109/VL.1996.545307
  * Sinclair (1991) John Sinclair. 1991\.  _Corpus, Concordance, Collocation_.  Oxford University Press.
  * Sinclair (2003) John Sinclair. 2003\.  _Reading concordances: an introduction_.  Pearson/Longman.
  * Svartvik (2011) Jan Svartvik. 2011\.  _Directions in corpus linguistics: proceedings of Nobel Symposium 82 Stockholm, 4-8 August 1991_. Vol. 65.  Walter de Gruyter.
  * Tufte (1990) Edward R. Tufte. 1990\.  _Envisioning information_.  Graphics Press, Cheshire, CT, USA.
  * Viégas and Wattenberg (2008) F.B. Viégas and M. Wattenberg. 2008.  Tag clouds and the case for vernacular visualization.  _Interactions_ 15, 4 (2008), 49–52.
  * Wattenberg and Viégas (2008) Martin Wattenberg and Fernanda B Viégas. 2008.  The word tree, an interactive visual concordance.  _IEEE Transactions on Visualization and Computer Graphics_ 14, 6 (2008), 1221–1228.