# Enhancing Distractor Generation for Multiple-Choice Questions with Retrieval
Augmented Pretraining and Knowledge Graph Integration

Han-Cheng Yu, Yu-An Shih, Kin-Man Law, Kai-Yu Hsieh,
Yu-Chen Cheng, Hsin-Chih Ho, Zih-An Lin, Wen-Chuan Hsu,
Yao-Chung Fan∗
Department of Computer Science and Engineering,
National Chung Hsing University, Taiwan
<EMAIL_ADDRESS>
###### Abstract

In this paper, we tackle the task of distractor generation (DG) for multiple-
choice questions. Our study introduces two key designs. First, we propose
retrieval augmented pretraining, which involves refining the language model
pretraining to align it more closely with the downstream task of DG. Second,
we explore the integration of knowledge graphs to enhance the performance of
DG. Through experiments with benchmarking datasets, we show that our models
significantly outperform the state-of-the-art results. Our best-performing
model advances the F1@3 score from 14.80 to 16.47 in MCQ dataset and from
15.92 to 16.50 in Sciq dataset.

##  1 Introduction

Multiple-Choice Questions (MCQs) are widely used to evaluate a learner’s
knowledge. However, creating them manually requires a significant amount of
time and effort from educators. Well-designed MCQs help in accurately
assessing learners’ abilities. The most challenging part of creating MCQs is
designing appropriate incorrect options, commonly called distractors.
Therefore, researchers have focused on the automatic distractor generation for
MCQs in recent years. In this paper, we explore two directions for improving
DG methods.

Task-Specific Pretraining Current SOTA DG methods, such as utilizing BERT for
DG Chiang et al. (2022) or harnessing T5 for Text2Text DG Wang et al. (2023),
are all based on pre-trained language models (LMs). Existing LMs undergo task-
agnostic pertaining. However, recently, the idea of task-specific pretraining
has gained prominence. The aim is to refine the pretraining process to closely
align with the downstream task. Therefore, our first endeavor in this paper is
to investigate Task-Specific Pretraining for the DG task.

In line with this goal, we propose Retrieval Augmented Pretraining (RAP) for
task-specific pretraining. The main idea involves using MCQ answers to
retrieve relevant sentences/passages from a large corpus, such as Wikipedia,
to create pseudo questions, and then use the generated pseudo question for
task-specific pertaining.

Figure 1 illustrates an example of a create pseudo question. Assume that we
are given a set of MCQ options, the answer kidneys, and three distractors
lungs, pancreas, liver. The idea is to use the answer option kidneys to
retrieve a sentence, i.e., the kidneys are two reddish-brown bean-shaped
organs. and replace the answer with the $\mathtt{[Mask]}$ token to generate a
pseudo question, i.e., the $\mathtt{[Mask]}$ are two reddish-brown bean-shaped
organs. The pseudo question and the distractors are then served as training
data for RAP.

Knowledge Augmented Generation Recent research trends show that leveraging
knowledge graphs (KGs) can enhance the performance of LM-based text generation
tasks, as discussed in Yasunaga et al. (2022) and Zhang et al. (2022). The
perspective is that LMs and KGs should complement each other. KGs go beyond
text by offering structural information, representing entities as nodes and
their relationships as edges. This structured knowledge enhances the ability
for multi-step reasoning. In line with this motivation, we propose knowledge-
augmented generation (KAG), where we build upon the candidate augmentation
strategy proposed by the state-of-the-art DG method Wang et al. (2023). The
idea is to retrieve knowledge triplets from a knowledge graph to serve as
auxiliary information for the text2text DG model.

Figure 1: Retrieved Augmented Pretraining

The contributions of this paper are

  * •

Our methods achieve a remarkable improvement in state-of-the-art DG results.
Our best-performing model elevates the F1@3 score from 14.80 to 16.47 in MCQ
and from 15.92 to 16.50 in Sciq, showcasing the effectiveness of our approach.

  * •

Extensive experimental evaluation with the benchmarking datasets are conducted
and the insights of incorporating task-pretraining and knowledge triplet
provision are discussed. Our study unveils promising directions for further
development in DG by showcasing the efficacy of knowledge augmentation and
task-specific pretraining.

The rest of this paper is organized as follows. Section 2 reviews the works of
automatic distractor generation in the literature. In Section 3 we present the
proposed methods. Section 4 reports the performance evaluation and Section 5
concludes this work and discuss the future work.

##  2 Related Work

###  2.1 Distractor Generation

The current DG research can be divided into two directions:

Generating and Ranking (GR) framework The framework incorporates a general-
purpose knowledge base to effectively create a small distractor candidate set,
and a feature-rich learning-to-rank model to select distractors. Specifically,
the GR architecture consists of two stages.

First, it generates candidate distractors, and then it ranks these candidates
based on semantic rules and linguistic features to select the final
distractor. In the GR framework, there are two approaches for generating
distractor candidates: using a knowledge base Ren and Zhu (2021) or using a
language model (LM) Chiang et al. (2022). These approaches have significantly
improved the quality and diversity of distractors compared to traditional
rule-based methods Liang et al. (2017, 2018), making them the state-of-the-art
in DG.

Text2Text generation architecture The Text2Text generation architecture
differs from the GR architecture by formulating distractor generation as a
Text2Text task. Specifically, it concatenates the question stem with the
answer and inputs it into a generative language model (e.g., T5 or GPT) to
train the model to generate a set of distractors. Currently, research based on
the Text2Text architecture (Wang et al., 2023) represents the state-of-the-art
in distractor generation.

###  2.2 Task-specific Pretraining

In recent related work, researchers have explored the integration of task-
specific priors into BERT language model pretraining to enhance performance in
low-resource finetuning tasks Wang et al. (2020). Traditional pretraining
methods often prioritize generic natural language knowledge, overlooking task-
specific information, which can lead to overfitting in low-resource downstream
tasks. To address this issue, Wang et al. (2020) propose integrating task-
specific label embeddings into the self-attention layers during pretraining.
This integration enables the model to filter out task-irrelevant information
and improve task-specific knowledge during fine-tuning, resulting in reduced
overfitting and improved performance on downstream tasks with limited
resources.

Another related work, Zhang et al. (2020), adopts a task-specific pretraining
approach for text summarization tasks. The authors replace a portion of the
original sentences in the text with mask tokens, allowing the model to learn
to generate masked sentences. Comparing this approach to traditional masked
language modeling (MLM) for pretraining, they find that closer alignment
between the pretraining task and the downstream task leads to improved
performance. Additionally, they experiment with pretraining on various types
of datasets and observe that utilizing a dataset similar to the downstream
task yields better results. For example, when pretraining on a news dataset
and fine-tuning on another news dataset, the performance surpasses that of
fine-tuning on a web article dataset.

Building upon these findings, we draw inspiration from the aforementioned
studies to design our proposed approach, known as RAP (Retrieval-Augmented
Pretraining), aimed at enhancing the performance of distractor generation
(DG). RAP leverages task-specific priors and incorporates them into the
pretraining phase to capture and utilize relevant information specific to the
distractor generation task. By aligning the pretraining task with the
downstream DG task and considering task-specific information, we aim to
improve the quality and effectiveness of distractor generation.

###  2.3 Knowledge Augmented Generation

We have conducted a survey of research that leverages Knowledge Graphs (KGs)
to enhance performance in various Natural Language Processing (NLP) tasks,
including Question Answering, Entity Typing/Relation Classification, Query
Answering, Question Generation, and Distractor Generation (Yasunaga et al.,
2022, 2021; Zhang et al., 2022; Feng et al., 2020; He et al., 2019; Ren et
al., 2020; Fei et al., 2022; Chen et al., 2023; Ren and Zhu, 2021).

Notably, a significant amount of research has focused on using Knowledge
Graphs to improve question-answering systems, particularly for tasks involving
multihop reasoning. These studies utilize Knowledge Graph triplets for
inferencing and have demonstrated the utility of structured background
knowledge in strengthening NLP tasks.

For example, (Yasunaga et al., 2021) proposed an end-to-end question-answering
model that combines language models and Knowledge Graphs to handle reasoning
tasks. (Zhang et al., 2022) introduced a novel model that incorporates joint
information exchange between language models and Knowledge Graphs, achieving
superior performance across multiple domains.

While Knowledge Graph integration has shown promising results in Question-
Answering tasks, its application to Distractor Generation remains relatively
limited (Ren and Zhu, 2021).

Therefore, our goal is to leverage KGs as auxiliary tools to enhance
distractor generation, improving the relevance of generated options to the
question. This approach not only creates more challenging options for
multiple-choice questions but also enhances the model’s efficiency in
utilizing Knowledge Graphs, leading to more effective Knowledge Augmented
Generation.

##  3 Methodology

###  3.1 Retrieval Augmented Pretraining

Our approach involves generating pseudo questions to continuously train a pre-
trained language model (e.g., T5 or BART) before fine-tuning it for downstream
Distractor Generation (DG) tasks.

Here’s how our idea works: Given an MCQ training instance consisting of a
question stem ($q$), an answer option ($a$), and a set of distractors ($D$),
we utilize $a$ to retrieve a single sentence or a short passage from a corpus
(such as Wikipedia). Subsequently, we mask out $a$ from the retrieved
sentence/passage, replacing the answer position with a mask token
($[\mathtt{Mask}]$). This process results in a modified sentence/passage known
as a pseudo question ($\tilde{q}_{\otimes[\mathtt{Mask}]}$).

With $\tilde{q}_{\otimes[\mathtt{Mask}]}$, our goal is to pretrain a LM as
follows.

$L(\theta)=-\sum_{i=1}^{|D|}t_{i}\log
p(\hat{t}_{i}|\hat{t}_{<i},\tilde{q}_{\otimes[\mathtt{Mask}]},a;\theta)$

  * •

$t_{i}$: the token sequence given by the concatenation of the ground truth
distractors $d_{1}||d_{2}||d_{3}$.

##### Alternatives for RAP Training Setting

There are two alternatives for RAP training setting.

  * •

Data Augmentation RAP: We can treat RAP as a data augmentation mechanism by
using the same dataset for RAP and DG.

  * •

Cross-Domain RAP: We can use two different distractor generation datasets
(SciQ and MCQ datasets in this study). One dataset is used for RAP and the
other for DG fine-tuning.

There are different impacts and implications for RAP training adoption. We
provide experimental study and discussion for this part in Subsection 4.6.

##### Boosting RAP with ground-truth distractor

The RAP idea can be extended to using ground-truth distractors to generate
pseudo questions. That is, we can use ground-truth distractors to retrieve a
sentence/passage and set the rest of options (i.e., $a$ and other
distractors). That is,

$L(\theta)=-\sum_{i=1}^{|D|}t_{i}\log
p(\hat{t}_{i}|\hat{t}_{<i},\tilde{q}_{\otimes[\mathtt{Mask}]},d_{1};\theta)$

  * •

$t_{i}$: the token sequence given by the concatenation of the other options
$a||d_{2}||d_{3}$.

###  3.2 Knowledge Augmented Generation

We extend the idea of the candidate augmentation strategy proposed by Wang et
al. (2023). We explore incorporating knowledge triplets for DG. Specifically,
as shown in Figure 2, our KAG proceeds by (1) a knowledge triplet retrieval
stage (Subsection 3.2.1) and (2) a triplet re-ranker stage (Subsection 3.2.2).
The retriever stage is to retrieve triplets with respect to $q$ and $a$, and
the re-ranker stage aims to rank the triplets by their estimated relevancy
with respect to $q$ and $a$

Figure 2: Knowledge Augmented Generation

####  3.2.1 Retrieving Triplet from KG

Our process for obtaining knowledge triplets is as follows. First, for a given
$q$ and answer $a$, we employ an language model trained for distractor
generation (e.g., Chiang et al. (2022)) to generate a set of candidate
distractors $\\{\hat{d}_{1},...,\hat{d}_{k}\\}$. In addition, we conduct
keyword extraction over $q$ and $a$ to extract keywords from them. We then
union the two sets of keywords (denoted by $W$).

As illustrated in Figure 3, with $W$ and a given knowledge graph $G(V,E)$, the
triplet set is given by

$K=\\{(u,e_{u,v},v)\mid u,v\in W\text{ and }e_{u,v}\in E\\}$

Figure 3: Retrieve Triplet from KG: we extract keyword from a given question,
answer and candidate set as a entity set $W$ and retrieve relevant triplet set
from KG with keyword entities

####  3.2.2 Triplet Ranker

The input to triplet ranker is a triplet set $T$ from KG Retrieval stage and
let $q||a$ be the concatenation of a question $q$ and an answer $a$. We
experiment with the following two alternatives for ranking triplets.

  1. 1.

Unsupervised Sentence Embedding Distance: The ranking process begins by
encoding $q||a$ and each knowledge triplet $\tau_{i}$ into their respective
vector representations. Next, we compute a relevancy score for each triplet by
comparing its vector representation with that of $q||a$. The higher the
relevancy score, the more likely the triplet is deemed relevant to $q||a$.
Specifically,

$\text{{scores}}=[\text{{Cos-Similarity}}(\tau_{i},q||a),\forall\tau_{i}\in
K]$

We select top-$k$ triplets for the later knowledge augmented generation.

  2. 2.

Supervised Triplet Classification: As an alternative, we propose a binary
classification formulation to estimate the relevancy of a knowledge triplet
$\tau_{i}$ with respect to $q||a$. During the training phase, we label a
triplet as relevant if it contains the answer or ground-truth distractors, and
as irrelevant otherwise. Specifically, we concatenate $q||a$ and $\tau_{i}$,
separated by a special token $[\mathtt{SEP}]$ as input and the relevancy as
output. During the inference phase, we utilize the LM to re-sort the top-$k$
triplet set based on the confidence scores.

####  3.2.3 KAG Training

For a given training instance $(q,a,D,K)$, our goal is to train a generation
model conditioned on $q$, $a$, and $K$ by minimizing the negative log-
likelihood of the correct token $t_{i}$ of $D$ given the preceding tokens and
the conditions.

  * •

$K$: the set of knowledge triplet $\\{\tau_{1},...,\tau_{k}\\}$ retrieved from
a KG.

The idea is to retrieve a set of knowledge triplet
$\\{\tau_{1},...,\tau_{k}\\}$ from a KG and concatenate the knowledge triplet
with the original input text as an augmented text input for generation.
Specifically, the loss function is

$L(\theta)=-\sum_{i=1}^{|D|}t_{i}\log
p(\hat{t}_{i}|\hat{t}_{<i},q,a,\\{\tau_{i}\\};\theta)$

The observation behind the knowledge triplet augmentation strategy is to
inject more information for generation through the knowledge graph in hope to
boost the DG performance.

##  4 Experiment

###  4.1 Dataset

We use SciQ (Welbl et al., 2017) and MCQ dataset (the dataset releated by Ren
and Zhu, 2021) for performance evaluation. For the details about the two
benchmark datasets and our dataset setting.

##### Sciq dataset

The Sciq dataset is a multi-domain multiple-choice question dataset consisting
of 13,000 questions in the fields of physics, chemistry, biology, and other
natural sciences. These questions are open-ended and require reading and
understanding relevant scientific knowledge, followed by reasoning and
answering the questions. The questions are presented in a multiple-choice
format, with each question accompanied by an answer and three incorrect
options. According to the Sciq dataset configuration, the 13,000 data points
are split into train/dev/test datasets with a ratio of 11,700/1,000/1,000.

Since the Sciq question sentences do not contain **blanks**, in the candidate
generation method, we utilize generative LM, specifically ChatGPT, to generate
the candidate set.

##### MCQ dataset

MCQ dataset is a cross-domain cloze-style dataset, that includes the domains
of science, vocabulary, common sense, and trivia. Each data is composed of a
sentence containing **blank** of cloze stem, answer, and distractors.
According to the setting reported by Ren and Q. Zhu (2021), MCQ contains 2880
questions and is randomly divided into train/dev/test with a ratio of 8:1:1.

We obtain the MCQ dataset from GitHub link shared by Ren and Q. Zhu (2021).
However, we find there is a slight difference between the numbers in the
shared dataset and reported in the paper. In the shared dataset, it only
contains train and test data (with 2321/258). Thus, we use this data setting
in our experiments. For dev data, we use 9:1 split from train as dev data.

Dataset | MCQ | Sciq
---|---|---
Train | Dev | Test | All | Train | Dev | Test | All
# of Questions | 2088 | 233 | 258 | 2580 | 11700 | 1000 | 1000 | 13700

Table 1:  The statistics of the training, development and test sets of MCQ,
Sciq.

###  4.2 Evaluation Metrics

##### Automatic Metric

Following the SOTA DG by (Wang et al., 2023), we evaluate the DG quality by F1
score (F1@3), precision (P@1, P@3), and recall (R@1, R@3). P@k represents the
ratio of correctly labeled top-k generated distractors, while R@k indicates
the ratio of correctly predicted labels among the ground truth. F1@k is the
harmonic mean of P@k and R@k. Notably, when the label size is 3, P@3 and R@3
will be the same, resulting in the same F1@3 score. Since both the Sciq test
data and MCQ test data contain 3 distractors, we report the scores of P@1 and
F1@3 in the experiments.

##### Human Evaluation Metric

In addition to Automatic Metrics, we also consider human evaluation to assess
the performance of the model on various aspects. During the evaluation
process, we randomly select 14 questions and generate distractor sets using
various models, which are then assessed by five human labelers. For the
evaluation of the Distractor Generation models, we consider the following
criteria for human evaluation:

  1. 1.

Relevance: This metric assesses the relevance of the generated distractors to
the question. This means that the distractors should be related to the theme,
content, or context of the question.

  2. 2.

Distractiveness: This metric evaluates the level of distraction that the
generated distractors bring to the correct answer. The distractors should be
able to divert the answer away from the correct answer, increasing the
difficulty of the question.

  3. 3.

Utility: This is an overall quality assessment of the generated distractors,
considering aspects such as fluency, relevance, duplication, and
distractiveness. This is a comprehensive metric that takes into account all
facets of performance.

We employ a five-point rating system, where each score interval represents
different levels of relevance, ranging from "totally irrelevant" (1 point) to
"completely relevant" (5 points). These evaluation metrics will help us assess
the quality and performance of the distractors generated by the models in a
comprehensive manner.

###  4.3 Implementation Details

See Appendix.

Dataset | Method | P@1 | R@1 | F1@3 | MRR | NDCG@3
---|---|---|---|---|---|---
MCQ | (Ren and Zhu, 2021) | 10.58 | - | 9.19 | 17.51 | -
(Chiang et al., 2022) | 10.81 | 3.60 | 7.72 | 18.15 | 15.39
(Wang et al., 2023) (BART) | 14.28 | 4.76 | 11.45 | 21.49 | 23.70
Text2text (RAP-BART) | 18.14 | 6.04 | 12.35 | 24.06 | 25.78
(Wang et al., 2023) (BART w/ c.a.) | 19.69 | 6.56 | 13.12 | 25.03 | 26.26
KAG (BART) | 20.07 | 6.69 | 14.41 | 27.02 | 29.37
KAG (RAP-BART) | 16.60 | 5.75 | 12.22 | 22.65 | 24.50
KAG (BART) (with only answer triplet) | 14.28 | 4.76 | 12.74 | 21.55 | 24.13
KAG (RAP-BART)(with only answer triplet) | 13.12 | 4.37 | 11.84 | 20.01 | 22.35
(Wang et al., 2023) (T5) | 18.53 | 6.17 | 11.45 | 23.61 | 25.08
Text2text (RAP-T5) | 22.39 | 7.46 | 14.80 | 29.02 | 30.72
(Wang et al., 2023) (T5 w/ c.a.) | 16.60 | 5.53 | 14.80 | 24.90 | 27.61
KAG (T5) | 20.07 | 6.69 | 16.47 | 28.57 | 30.99
KAG (RAP-T5) | 20.07 | 6.69 | 14.92 | 26.44 | 28.23
KAG (T5)(with only answer triplet) | 22.00 | 7.35 | 15.18 | 28.70 | 30.61
KAG (RAP-T5)(with only answer triplet) | 21.62 | 7.20 | 14.41 | 27.22 | 28.60
ChatGPT | 18.91 | 6.30 | 13.38 | 25.86 | 27.97
Sciq |  (Wang et al., 2023) (BART) | 19.30 | 6.46 | 14.94 | 26.40 | 28.36
Text2text (RAP-BART) | 20.10 | 6.73 | 16.32 | 27.56 | 29.68
(Wang et al., 2023) (BART w/ c.a.) | 21.26 | 7.08 | 14.98 | 27.63 | 29.28
KAG (BART) | 16.24 | 5.41 | 13.99 | 23.62 | 25.93
KAG (RAP-BART) | 19.70 | 6.58 | 15.42 | 26.61 | 28.69
KAG (BART) (with only answer triplet) | 17.15 | 5.57 | 14.87 | 25.00 | 27.27
KAG (RAP-BART)(with only answer triplet) | 18.35 | 6.15 | 15.52 | 25.81 | 28.22
(Wang et al., 2023) Text2text (T5) | 24.27 | 8.09 | 15.92 | 30.32 | 31.99
Text2text (RAP-T5) | 24.30 | 8.09 | 16.06 | 29.98 | 31.49
(Wang et al., 2023) (T5 w/ c.a.) | 22.06 | 7.35 | 12.83 | 25.54 | 26.47
KAG (T5) | 22.50 | 7.51 | 15.38 | 29.10 | 31.04
KAG (RAP-T5) | 18.50 | 6.18 | 15.15 | 26.00 | 28.40
KAG (T5)(with only answer triplet) | 23.70 | 7.91 | 16.50 | 30.41 | 32.39
KAG (RAP-T5)(with only answer triplet) | 23.00 | 7.68 | 16.46 | 29.51 | 31.41
ChatGPT | 15.17 | 5.16 | 10.61 | 19.39 | 20.68

Table 2:  DG Results on the Compared Datasets: In this set of experiment, we
mainly compare our designs with the SOTA method Wang et al. (2023). c.a.
represents candidate augmentation strategy introduced by Wang et al. (2023).

Dataset | Method | # of masked Sentences/Passages
---|---|---
MCQ-train | RAP-S | 17,225
RAP-P | 17,362
RAP-P w/ GTD | 69,356
MCQ-all | RAP-S | 10,894
RAP-P | 10,995
RAP-P w/ GTD | 44,294
Sciq-train | RAP-S | 85,463
RAP-P | 86,269
RAP-P w/ GTD | 307,915
Sciq-all | RAP-S | 91,798
RAP-P | 92,731
RAP-P w/ GTD | 327,546

Table 3:  The statistics of the RAP training. Note that our RAP has the
following variations. First, in RAP, we can choose to retrieve a single
sentence or a passage, giving rise to different RAP strategies. Thus, we
denote RAP-S as retrieving sentence for pseudo question generation and RAP-P
for retrieving passage. Second, we have the option to use the answer or the
distractor as the starting point for retrieving the sentence/passage. We
denote the method using distractor as starting point as RAP-S w/GTD or
RAP-S/RAP-P (as using answer as starting point)

| DataSet for
---
Traing and
Testing DG model
Method | Pretrain Dataset | P@1 | R@1 | F1@3 | MRR | NDCG@3
MCQ | BART off-shelf | None | 14.28 | 4.76 | 11.45 | 21.49 | 23.70
RAP-S${}_{\text{BART}}$ | MCQ-Train | 16.21 | 5.4 | 11.96 | 22.2 | 23.99
RAP-P${}_{\text{BART}}$ | MCQ-Train | 18.14 | 6.04 | 12.35 | 24.06 | 25.78
RAP-P${}_{\text{BART}}$ /w GTD | MCQ-Train | 15.05 | 5.01 | 11.58 | 20.65 | 22.33
RAP-S${}_{\text{BART}}$ | Sciq-all | 15.05 | 5.01 | 13.25 | 22.77 | 25.44
RAP-P${}_{\text{BART}}$ | Sciq-all | 20.84 | 6.94 | 15.57 | 28.57 | 30.85
RAP-P${}_{\text{BART}}$ /w GTD | Sciq-all | 22.77 | 7.59 | 17.88 | 31.33 | 33.97
T5 off-shelf | None | 18.53 | 6.17 | 11.45 | 23.61 | 25.08
RAP-S${}_{\text{T5}}$ | MCQ-Train | 23.93 | 7.97 | 14.15 | 29.27 | 30.67
RAP-P${}_{\text{T5}}$ | MCQ-Train | 22.39 | 7.46 | 14.8 | 29.02 | 30.72
RAP-P${}_{\text{T5}}$ /w GTD | MCQ-Train | 21.62 | 7.2 | 13.77 | 27.15 | 28.70
RAP-S${}_{\text{T5}}$ | Sciq-all | 25.86 | 8.62 | 15.57 | 31.46 | 33.12
RAP-P${}_{\text{T5}}$ | Sciq-all | 31.66 | 10.55 | 18.91 | 37.7 | 39.43
RAP-P${}_{\text{T5}}$ /w GTD | Sciq-all | 27.79 | 9.26 | 18.66 | 34.42 | 36.31
Sciq | BART off-shelf | None | 19.3 | 6.46 | 14.94 | 26.40 | 28.36
RAP-S${}_{\text{BART}}$ | Sciq-train | 19.3 | 6.45 | 14.66 | 25.61 | 27.45
RAP-P${}_{\text{BART}}$ | Sciq-train | 20.1 | 6.73 | 16.32 | 27.56 | 29.68
RAP-P${}_{\text{BART}}$ /w GTD | Sciq-train | 22.4 | 7.48 | 16.39 | 28.9 | 30.81
RAP-S${}_{\text{BART}}$ | MCQ-all | 20.4 | 6.83 | 15.65 | 27.19 | 29.09
RAP-P${}_{\text{BART}}$ | MCQ-all | 20.2 | 6.75 | 15.58 | 27.41 | 29.5
RAP-P${}_{\text{BART}}$ /w GTD | MCQ-all | 20.7 | 6.91 | 16.06 | 28.16 | 30.32
T5 off-shelf | None | 24.27 | 8.09 | 15.92 | 30.32 | 31.99
RAP-S${}_{\text{T5}}$ | Sciq-train | 23.6 | 7.86 | 15.62 | 29.13 | 30.69
RAP-P${}_{\text{T5}}$ | Sciq-train | 24.3 | 8.09 | 16.06 | 29.98 | 31.49
RAP-P${}_{\text{T5}}$ /w GTD | Sciq-train | 25.0 | 8.34 | 16.46 | 30.18 | 31.54
RAP-S${}_{\text{T5}}$ | MCQ-all | 24.1 | 8.04 | 15.26 | 29.63 | 31.12
RAP-P${}_{\text{T5}}$ | MCQ-all | 23.1 | 7.71 | 16.31 | 29.56 | 31.49
RAP-P${}_{\text{T5}}$ /w GTD | MCQ-all | 23.7 | 7.89 | 16.36 | 29.73 | 31.25

Table 4:  RAP Performance Overview with In-Domain and Cross-Domain Study.

###  4.4 Evaluation Results

Table 2 presents the results of the compared methods on the two benchmarking
datasets. We have the following notes for the results.

RAP indeed improve performance By comparing the performance difference between
Text2Text (T5) and Text2Text (RAP-T5), we can see that the introduction of RAP
elevates the performance of MCQ experiments from 11.45 to 14.80 (F1@3). In the
case of Sciq, it increases from 15.92 to 16.06.

RAP more effective in low resource settings Furthermore, continuing the above
observations, we found that the improvement brought by RAP in the Sciq
experiment is not as significant as in the MCQ experiment. We attribute this
result to the much smaller size of the MCQ dataset compared to Sciq. When the
training data is abundant, the gains from pretraining naturally become
limited. Therefore, in the MCQ setting with only 2088 training examples, the
introduction of RAP has a noticeable impact.

KG also boosts the performance By comparing T5 candidate augmentation with KAG
(T5), we observe that the introduction of KG indeed brings a significant
improvement. In Sciq, we observe an increase in F1@3 from 12.83 to 15.38. In
MCQ, it increases from 14.80 to 16.47.

Our methods outperform ChatGPT We also compare the performance of ChatGPT (in
a zero-shot manner) on both datasets. From the experimental results, it is
evident that our best-performing models consistently outperform ChatGPT. In
the comparison with Sciq, KAG (RAP-T5) achieves an F1@3 score of 15+ compared
to ChatGPT’s 10.61. An interesting observation is that while ChatGPT still
lags behind the KAG+RAP-based approach in the MCQ comparison, the performance
gap is smaller. We attribute this to the fact that some questions in Sciq
require common-sense reasoning in addition to knowledge-based answering. Since
ChatGPT generates responses in a zero-shot learning manner during testing, it
does not fully capture the characteristics of the Sciq dataset. In the case of
the MCQ dataset, due to the limited training data, the differences between
various methods and ChatGPT are not as substantial as in the Sciq comparison.

Combining KAG with RAP did not yield additive effects We also observed that
combining KAG with RAP did not yield additive effects. Taking the comparison
of the T5 model on the Sciq dataset as an example, we found that the
performance did not improve when using both KAG and RAP together (KAG(RAP-T5):
15.15) compared to using RAP alone (Text2Text(RAP-T5): 16.06) or KAG alone
(KAG(T5): 15.38). Similar observations were made in other settings. We
speculate that the additional noise introduced by KAG during the incorporation
of knowledge triplets may be the reason behind this. Although we designed a
reranker to select triplets, the results were not consistently stable. To
validate this hypothesis, we attempted a variation of KAG (RAP-T5) (denote by
with-only-answer triplet) where, instead of using a reranker, we selected
triplets containing the answer to input into the Text2Text generator. We
observed significant improvement with this approach in the Sciq dataset, but
no improvement in the MCQ dataset. This suggests that there is considerable
room for improvement in the design of the triplet ranker. Selecting relevant
triplets for generation is an area that warrants further exploration in future
research.

Method | Relevance | Distractiveness | Utility
---|---|---|---
(Wang et al., 2023) | 3.81 | 3.35 | 3.55
KAG(T5) | 4.05 | 3.25 | 3.77
Text2text(RAP-T5) | 4.45 | 3.87 | 4.07
ChatGPT | 3.14 | 2.67 | 3
ground truth | 3.52 | 3.02 | 3.4

Table 5:  The human evaluation for MCQ dataset.

##### Human Evaluation Results

Table 5 presents the results of various methods in generating distractor sets
for the MCQ cloze tasks. Upon analysis, we observe that in terms of Relevance,
Distractiveness, and Utility, both RAP and KAG scored relatively high and
exceeded the previous soft method, T5 Candidate Augmentation.

Table 5 presents the results of various methods in generating distractor sets
for the MCQ cloze tasks. Upon analysis, we observe that in terms of Relevance,
Distractiveness, and Utility, both RAP and KAG scored high and surpassed or
comparable to the prior SOTA method.

These results suggest that we have successfully guided our model to leverage
additional knowledge to generate higher quality distractors. The reason why
RAP outperforms KAG might be that the KG (ConceptNet) cannot encompass
knowledge from all natural domains, whereas RAP, having access to an extensive
external corpus (Wikipedia), includes a vast array of facts across various
domains. This vastness could potentially explain why KAG scored slightly lower
than RAP.

Furthermore, we noted that the ground truth quality for MCQ questions was not
consistently high. The lowest performance was found in Distractiveness. This
could likely be attributed to the fact that some of MCQ questions are
generally designed for elementary and middle school grade levels, which could
impact the complexity and misdirection quality of the distractors.

Method | F1@3
---|---
T5 KAG | 16.47
w/o c.a | 13.64
w/o c.a (Masked LM) | 15.18
w/o c.a. (Generative LM) | 13.89
w/o reranker | 14.15
Table 6: Ablation-study of our KAG model components using the MCQ Test Dataset

###  4.5 Ablation Study on KAG

We conducted ablation experiments on the MCQ dataset to assess the impact of
different components in our system. The results are summarized in Table 6,
providing insights into the importance and contributions of each component.

##### Candidate Generation

Generating candidate sets using Masked LM or Generative LM is a key component
in our system, enhancing KG retrieval. Removing these sets and relying solely
on sentence and answer-based triplet retrieval significantly reduced the
number of retrievable triplets, potentially introducing irrelevant noise and
resulting in a performance drop (F1@3: 16.47 to 13.64). Using Masked LM or
Generative LM alone also affected F1@3. This emphasizes the value of
incorporating candidate sets, as they provide crucial information for
identifying important triplets in the knowledge graph.

##### Reranker

The Reranker, our second key component, sorts triplets to select those more
relevant to distractors/answers. Without sorting by the Reranker, randomly
selecting triplets for triplet augmentation led to a decrease in F1@3 (16.47
to 14.15). This highlights the Reranker’s importance in identifying important
triplets and improving downstream task performance.

###  4.6 Study on Cross-Domain for RAP

In this subsection, we report our studies on cross-domain and in-domain for
RAP. The experiment results are summarized in Table 4.

We have the following observations: Firstly, in terms of cross-domain effects
(using the MCQ dataset for pretraining and fine-tuning the DG model with the
Sciq dataset, or vice versa), we found that using Sciq-all for pretraining the
language model resulted in a significant improvement in the downstream MCQ
dataset for distractor generation. Specifically, using the T5 model, the RAP-
based approach increased the F1@3 score from 11.45 to 18.91 (almost a 1.5-fold
improvement). This notable improvement was expected, considering that Sciq is
a larger dataset compared to MCQ. However, when we reversed the process and
used MCQ for pretraining, followed by testing with the Sciq dataset, the
improvement in performance was not as significant. Taking the BART model as an
example, the direct use of BART off-shelf achieved a score of 14.94, while
RAP-S${}_{\text{BART}}$) only improved it to 16.06. Although there was some
improvement, it was not as substantial as the effects observed when using Sciq
pretraining.

Regarding in-domain effects (using the same dataset for both pretraining and
fine-tuning), we found consistent improvements in the generated results. For
example, using the T5 model on the Sciq test dataset, the T5 off-shell score
was 15.92, while RAP-P${}_{\text{T5}}$) improved it to 16.46. We also observed
similar improvements in the MCQ dataset.

In conclusion, our proposed RAP approach has shown improved generation
performance from both data augmentation and task-specific pretraining
perspectives. The experiments demonstrate that incorporating RAP into the
training process leads to significant enhancements in distractor generation.

##  5 Conclusion

In this paper, we introduce the utilization of task-specific pretraining and
knowledge base. Our experimental results highlight a significant performance
improvement achieved through the integration. our work represents a novel
contribution to the field of distractor generation for MCQs, showcasing the
potential of combining retrieval augmented pretraining and KGs to achieve
superior results.

##  6 Limitations

We report the following limitations for the KAG method:

  * •

Combining KAG with RAP did not yield additive effects. We believe that the key
factor lies in that the knowledge triplets may introduces additional noise
that interferes with the Text2Text model’s generation process. Thus, there is
significant room for improvement in the current design of the triplet ranker.
Selecting relevant triplets for generation is an aspect that requires further
strengthening in this research.

  * •

The current evaluation and training heavily rely on token scores, which can
only reflect the similarity to the ground truth but cannot fully represent the
quality of the generated output. The research conclusions thus far have also
been established solely based on token scores.

  * •

During the pretraining stage of RAP, when retrieving sentences/passages, if
the answer is a rare or specialized term, the external corpus may fail to find
matching sentences/passages. Therefore, when applying the RAP framework to
other knowledge domains, having an abundant knowledge corpus becomes crucial.

## Acknowledgement

This work is supported by NSTC 112-2634-F-005 -002-project Smart Sustainable
New Agriculture Research Center (SMARTer), NSTC Taiwan Project under grant
112-2221-E-005 -075 -MY3, and Delta Research Center, Delta Electronics, Inc.

## References

  * Chen et al. (2023) Yu Chen, Lingfei Wu, and Mohammed J Zaki. 2023.  Toward subgraph-guided knowledge graph question generation with graph neural networks.  _IEEE Transactions on Neural Networks and Learning Systems_.
  * Chiang et al. (2022) Shang-Hsuan Chiang, Ssu-Cheng Wang, and Yao-Chung Fan. 2022.  Cdgp: Automatic cloze distractor generation based on pre-trained language model.  In _Findings of the Association for Computational Linguistics: EMNLP 2022_.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Fei et al. (2022) Zichu Fei, Qi Zhang, Tao Gui, Di Liang, Sirui Wang, Wei Wu, and Xuan-Jing Huang. 2022.  Cqg: A simple and effective controlled generation framework for multi-hop question generation.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 6896–6906.
  * Feng et al. (2020) Yanlin Feng, Xinyue Chen, Bill Yuchen Lin, Peifeng Wang, Jun Yan, and Xiang Ren. 2020.  Scalable multi-hop relational reasoning for knowledge-aware question answering.  _arXiv preprint arXiv:2005.00646_.
  * He et al. (2019) Bin He, Di Zhou, Jinghui Xiao, Qun Liu, Nicholas Jing Yuan, Tong Xu, et al. 2019.  Integrating graph contextualized knowledge into pre-trained language models.  _arXiv preprint arXiv:1912.00147_.
  * Lewis et al. (2019) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Ves Stoyanov, and Luke Zettlemoyer. 2019.  Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  _arXiv preprint arXiv:1910.13461_.
  * Liang et al. (2018) Chen Liang, Xiao Yang, Neisarg Dave, Drew Wham, Bart Pursel, and C Lee Giles. 2018.  Distractor generation for multiple choice questions using learning to rank.  In _Proceedings of the thirteenth workshop on innovative use of NLP for building educational applications_ , pages 284–290.
  * Liang et al. (2017) Chen Liang, Xiao Yang, Drew Wham, Bart Pursel, Rebecca Passonneaur, and C Lee Giles. 2017.  Distractor generation with generative adversarial nets for automatically creating fill-in-the-blank questions.  In _Proceedings of the Knowledge Capture Conference_ , pages 1–4.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, Peter J Liu, et al. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _J. Mach. Learn. Res._ , 21(140):1–67.
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  Sentence-bert: Sentence embeddings using siamese bert-networks.  _arXiv preprint arXiv:1908.10084_.
  * Ren et al. (2020) Hongyu Ren, Weihua Hu, and Jure Leskovec. 2020.  Query2box: Reasoning over knowledge graphs in vector space using box embeddings.  _arXiv preprint arXiv:2002.05969_.
  * Ren and Q. Zhu (2021) Siyu Ren and Kenny Q. Zhu. 2021.  Knowledge-driven distractor generation for cloze-style multiple choice questions.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 35(5):4339–4347.
  * Ren and Zhu (2021) Siyu Ren and Kenny Q Zhu. 2021.  Knowledge-driven distractor generation for cloze-style multiple choice questions.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 4339–4347.
  * Speer et al. (2017) Robyn Speer, Joshua Chin, and Catherine Havasi. 2017.  Conceptnet 5.5: An open multilingual graph of general knowledge.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 31.
  * Wang et al. (2023) Hui-Juan Wang, Kai-Yu, Han-Cheng Yu, and Yao-Chung Fan. 2023.  Distractor generation based on text2text language models with pseudo kullback-leibler divergence regulation.  In _Proceedings of the Findings of ACL 2023_.
  * Wang et al. (2020) Rui Wang, Shijing Si, Guoyin Wang, Lei Zhang, Lawrence Carin, and Ricardo Henao. 2020.  Integrating task specific information into pretrained language models for low resource fine tuning.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 3181–3186.
  * Welbl et al. (2017) Johannes Welbl, Nelson F Liu, and Matt Gardner. 2017.  Crowdsourcing multiple choice science questions.  _arXiv preprint arXiv:1707.06209_.
  * Wolf et al. (2019) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. 2019.  Huggingface’s transformers: State-of-the-art natural language processing.  _arXiv preprint arXiv:1910.03771_.
  * Yasunaga et al. (2022) Michihiro Yasunaga, Antoine Bosselut, Hongyu Ren, Xikun Zhang, Christopher D Manning, Percy S Liang, and Jure Leskovec. 2022.  Deep bidirectional language-knowledge graph pretraining.  _Advances in Neural Information Processing Systems_ , 35:37309–37323.
  * Yasunaga et al. (2021) Michihiro Yasunaga, Hongyu Ren, Antoine Bosselut, Percy Liang, and Jure Leskovec. 2021.  Qa-gnn: Reasoning with language models and knowledge graphs for question answering.  _arXiv preprint arXiv:2104.06378_.
  * Zhang et al. (2020) Jingqing Zhang, Yao Zhao, Mohammad Saleh, and Peter Liu. 2020.  Pegasus: Pre-training with extracted gap-sentences for abstractive summarization.  In _International Conference on Machine Learning_ , pages 11328–11339. PMLR.
  * Zhang et al. (2022) Xikun Zhang, Antoine Bosselut, Michihiro Yasunaga, Hongyu Ren, Percy Liang, Christopher D Manning, and Jure Leskovec. 2022.  Greaselm: Graph reasoning enhanced language models for question answering.  _arXiv preprint arXiv:2201.08860_.

Appendix

##  Appendix A Implementation Details

Our models are implemented based on models from Hugging Face (Wolf et al.,
2019). For generating candidate set, we use an language model trained for
distractor generation from (Chiang et al., 2022) and gpt3.5 turbo through
ChatGPT API with zero-shot prompting. For triplet reranker, we use Sentence-
BERT (Reimers and Gurevych, 2019) to estimate the initial sentence embedding
distance. For triplet classification, we use Sentence-BERT and BERT (Devlin et
al., 2018) as the default PLM. For the triplet augmented generator, we
experiment with BART (Lewis et al., 2019) and T5 (Raffel et al., 2020) as base
generation models.

During training, we use AdamW as the optimizer and an initial learning rate of
2e-5 for BERT, BART and 1e-4 for T5 models. All experiments are conducted
using two NVIDIA TITAN RTX GPUs.

##### BART-based generator

With MCQ data, the maximum number of epochs is set to 40 with a batch size of
on two NVIDIA TITAN RTX GPUs for the distraction generation with triplet
augmentation with a batch size of 32 and a maximum number of triplets is set
to 50. With Sciq data, the maximum number of epochs is set to 50 with a batch
size of 32 on two NVIDIA TITAN RTX GPUs for the distraction generation with
triplet augmentation with a batch size of 32 and a maximum number of triplets
is set to 50. The average running time for BART-based generators is 30 minutes
(1.5 hours) on MCQ (Sciq).

##### T5-based generator

With MCQ data, the maximum number of epochs is set to 40 with a batch size of
on two NVIDIA TITAN RTX GPUs for the distraction generation with triplet
augmentation with a batch size of 32 and a maximum number of triplets is set
to 50. With Sciq data, the maximum number of epochs is set to 50 with a batch
size of 32 on two NVIDIA TITAN RTX GPUs for the distraction generation with
triplet augmentation with a batch size of 32 and a maximum number of triplets
is set to 50. The average running time for BART-based generators is 40 minutes
(3 hours) on MCQ (Sciq).

##### Knowledge Graph

We utilize ConceptNet (Speer et al., 2017) as our KG, which is a graph that
encompasses a wide range of knowledge domains. The KG consists of a total of
800k nodes and 2M edges. For each question’s KG retrieval set, we preprocess
the retrieval subgraph using the approach described in (Feng et al., 2020).
Specifically, we process the textual corpus of each question, including the
question text, answer options, and entities in the candidate set.


plaintop table font = normalsize

#  Massive parallelization and performance enhancement of an immersed boundary
method based unsteady flow solver

Rahul Sundar1, Dipanjan Majumdar1, Chhote Lal Shah1,
and Sunetra Sarkar1

1Department of Aerospace Engineering, IIT Madras, Chennai-600036, India

ABSTRACT

High-fidelity simulations of unsteady fluid flow are now possible with
advancements in high performance computing hardware and software frameworks.
Since computational fluid dynamics (CFD) computations are dominated by linear
algebraic routines, they can be significantly accelerated through massive
parallelization on graphics processing units (GPUs). Thus, GPU implementation
of high-fidelity CFD solvers is essential in reducing the turnaround time for
quicker design space exploration. In the present work, an immersed boundary
method (IBM) based in-house flow solver has been ported to the GPU using
OpenACC, a compiler directive-based heterogeneous parallel programming
framework. Out of various GPU porting pathways available, OpenACC was chosen
because of its minimum code intrusion, low development time, and striking
similarity with OpenMP, a similar directive-based shared memory programming
framework. A detailed validation study and performance analysis of the
parallel solver implementations on the CPU and GPU are presented. The GPU
implementation shows a speedup up to the order $O(10)$ over the CPU parallel
version and up to the order $O(10^{2})$ over the serial code. The GPU
implementation also scales well with increasing mesh size owing to the
efficient utilization of the GPU processor cores.

Keywords: GPU computing, immersed boundary method, unsteady flows

##  1 INTRODUCTION

Unsteady flow past moving solid bodies is characterized by the flow field
having a temporal dependence often manifesting through vortices surrounding
and trailing the moving bodies[1, 2, 3, 4, 5]. These vortices stretch, rotate,
merge, attach, and detach, such that each of these mechanisms have varying
effects on the loads acting on the moving bodies immersed in a fluid[6, 7].
These mechanisms are also in return affected by displacement or deformation of
the solid bodies[4]. To understand fundamental barriers to the optimal design
of mechanical structures in flow, in-depth computational or experimental
investigations are necessary.

Although advancements in high-performance computing have made high-fidelity
CFD simulations of unsteady flow possible, they are still computationally
intensive[8, 9, 10]. This is because the CFD algorithms are dominated by
iterative linear algebra routines[11] for the solution of Navier-Stokes (N-S)
and allied governing equations. IBM [12, 13] forms one class of techniques in
CFD that solves the flow governing equations on a grid non-conformal to the
solid body immersed in the fluid. This avoids repetitive meshing otherwise
necessitated by the traditional techniques such as arbitrary Lagrange eulerian
(ALE) framework[14] which use a conformal grid. Thus, IBM is especially useful
for simulations involving complex geometries[15] and moving bodies[13].

Recently, Majumdar _et al._[7] developed a discrete forcing type IBM[15]
solver to simulate and capture dynamical transitions in unsteady flow past a
sinusoidally plunging rigid elliptic foil in the low Reynolds number
incompressible laminar flow regime. This solver was later parallelized by Shah
et al.[16] using OpenMP, a compiler directive-based shared memory parallel
programming framework, where a speed up of three times over the serial solver
was reported. Although parallelization on CPUs using OpenMP allows for a
reduction in turnaround time, these linear algebra routines can be accelerated
further and significantly by offloading the computations onto GPUs[17]. This
is because GPUs with their large number of processor cores and high throughput
capacity promise massive performance enhancement of parallelizable linear
algebra routines.

Typically, there exist three pathways to port a code to GPU: (i) performance
tuned architecture specific third-party libraries - CuSPARSE and CuBLAS [18]
to name a few, (ii) compiler directive frameworks - OpenACC[19, 20], and (iii)
architecture specific parallel programming language extensions such as
CUDA[21] and OpenCL[22]. Of these pathways, compiler directive frameworks
ensure minimum code intrusion and ease of parallelisation cutting down the
development time[23] as compared to full-fledged parallel programming
extensions like CUDA.

The present work involves parallelization and performance enhancement of an
in-house unsteady flow solver by offloading computationally intensive routines
onto the GPU using the OpenACC framework. The paper outline is as follows: a
discussion on the validation case setup and IBM solver is presented in section
2. In section 3, baseline solvers chosen for validation, the code
parallelization strategy, and the code development cycle are discussed.
Performance analysis of the GPU ported solver in the context of overall
speedup and input scaling is presented and compared with that of the baseline
solvers in section 4. Finally in section 5, conclusions and future work are
discussed.

##  2 METHODOLOGY

###  2.1 Problem setup

A sinusoidally plunging 2D rigid elliptic foil with a thickness-to-chord ratio
of 0.12 immersed in a uniform free stream is considered in the present study
as shown in Fig. 1(a). The non-dimensional plunging displacement
($\bar{y}(\bar{t})$) and velocity ($\dot{\bar{y}}(\bar{t})$) are given by,

$\displaystyle\bar{y}(\bar{t})$
$\displaystyle=\bar{h}\sin(k\bar{t}),\;\;\mbox{and}$ (1)
$\displaystyle\dot{\bar{y}}(\bar{t})$ $\displaystyle=k\bar{h}\cos(k\bar{t}).$
(2)

Here, $\displaystyle\bar{t}=\frac{tU_{\infty}}{c}$ is non-dimensional time,
$\displaystyle\bar{h}=\frac{h}{c}$ is non-dimensional plunging amplitude,
where $t$ is dimensional time, $U_{\infty}$ is the free stream velocity, $h$
is the plunging amplitude and $c$ is chord length of the elliptic foil.
Aligning with earlier literature [2, 1, 7], further discussions are based on
the reduced frequency, $\displaystyle k=\frac{2\pi f_{h}c}{U_{\infty}}$ and
the nondimensional plunging amplitude, $\bar{h}$, where, $f_{h}$ is the
plunging frequency.

###  2.2 Immersed Boundary method

The present study assumes the flow to be laminar and governed by the
incompressible N-S equations. These equations are solved on a background
Eulerian grid using discrete forcing IBM[15]. As a result of using an Eulerian
grid with the solid body immersed in it, the non-dimensional N-S equations
take the form as follows,

$\frac{\partial\boldsymbol{u}}{\partial
t}+\nabla.({\boldsymbol{u}}{\boldsymbol{u}})=-{\nabla}{p}+\frac{1}{Re}{\nabla}^{2}{\boldsymbol{u}}+\boldsymbol{f},\;\;\;\;\mbox{and}$
(3) ${\nabla}.{\boldsymbol{u}}-q=0.$ (4)

Here, ${\boldsymbol{u}}$ represents the non-dimensional velocity vector with
$u$ and $v$ being the horizontal and vertical components of
$\boldsymbol{{u}}$. ${p}$ is non-dimensional pressure, and $Re$ is the
Reynolds number given by $\displaystyle Re=\frac{U_{\infty}c}{\nu},$ where,
$\nu$ is the kinematic viscosity.

While handling a non-conformal grid using IBM, the classification of fluid and
solid mesh points is an added procedure at the beginning of every time
marching step. The momentum forcing term $\boldsymbol{f}$ in Eq. (3) ensures
the no-slip boundary condition on the solid boundary, and the source/sink term
$q$ in Eq. (4) satisfies the continuity and minimise spurious force
oscillations near the boundary [15]. The flow equations (Eqs. (3) and (4)) are
solved using finite volume-based semi-implicit fractional step method[24] with
the primitive variables being arranged in a staggered grid. Second-order
spatial and temporal discretizations are achieved using Adams-Bashforth and
Crank-Nicolson schemes respectively. Pressure and velocity correction
equations are iteratively solved using a modified Gauss-Seidel successive
over-relaxation method with red-black tagging as used by Shah _et al._[16]. A
detailed description of the IBM algorithm used in the present study is
presented in Majumdar _et al._[7].

###  2.3 Computational domain and boundary conditions

A rectangular computational domain of size
$[-7.5c,\;24c]\times[-12.5c,\;12.5c]$ is considered, with the elliptic foil
placed at the origin initially. The grid size $\Delta x=\Delta y=0.004$ and
time step $\Delta t=0.0001$ are chosen after performing grid and time
convergence tests.

Figure 1: Computational domain

The eulerian mesh is uniformly spaced in the region of the body movement with
a minimum cell spacing and then gradually stretched following a geometric
progression towards the outer boundaries as seen in Fig. 1(b) with the zoomed
views presented in Figs. 1(c) and 1(d).

##  3 Parallelisation strategy and implementation

###  3.1 Earlier work and baseline solvers

Two earlier versions of the in-house solver written in the C++ language are
considered for validation and speedup analysis. These are, a serial
implementation as in [7], and an OpenMP-based parallel implementation as in
[16], henceforth referred to as SOL0 and SOL1, respectively. SOL1 uses an
improved Gauss-Seidel successive over-relaxation algorithm with red-black
tagging of the mesh points to solve the pressure and velocity correction
equations to avoid race conditions and data dependency. Owing to interspersed
parallel and sequential regions, fork-join-based parallelism was adopted by
Shah _et al._[16]. As a result, a speedup of almost three times over SOL0 was
reported. The simulations using SOL1 were executed on 16 CPU threads. However,
the turnaround time was still high. Hence, there was a pertinent need to
accelerate the solver by offloading already parallel or parallelizable
computations to the GPU. In the current work, using the OpenACC framework, a
GPU-compatible solver henceforth referred as SOL2 is obtained.

###  3.2 System configuration

Development and testing were first carried out on a local system with an Intel
i7 10th Gen processor with 6 processor cores and 12 threads, 16Gb Memory, and
a NVIDIA RTX 2060 Max Q GPU card with 1920 CUDA cores and 6GB memory. All the
validation cases were however run on the AQUA super cluster hosted at the P.G
Senapathy Computing Centre for Computing resource in IIT Madras. With a
multithreaded 20-core Xeon Gold 6248 processor that has a clock speed of
2.6GHz, AQUA’s GPU nodes consist of 2 NVIDIA Tesla V100 GPU cards each with
5120 CUDA cores and 32GB GPU memory.

###  3.3 Software stack

Throughout the present work, NVIDIA’s high performance computing software
development kernel (HPC-SDK) version - 20.7 has been used both on the local
system and AQUA supercluster. Amongst a variety of libraries and tools in HPC-
SDK 20.7, Nsight-Systems and Nsight-Compute were used here for code profiling
and NVTX for code annotation. Portable Batch System (PBS) was used for job
scheduling on the cluster.

###  3.4 GPU implementation

The iterative code development cycle adopted in the present work using OpenACC
to develop SOL2 typically involves four steps: (i) analysis and profiling of
the code for parallelizable hot spots, (ii) parallelization of the identified
code hotspots, (iii) testing and validation of the modification, and (iv)
further optimization of the parallelized loops. Since OpenMP and OpenACC are
both compiler directive-based parallel programming frameworks, the GPU
implementation involved very minimal source code intrusions as shown in the
schematic in Fig. 2.

Once the code sections are ported using appropriate OpenACC pragmas, the
compiler automatically decides how to offload the code sections onto the GPU
at the time of compilation. The implicit decisions made by the compiler can be
inferred from the compiler trace. Further optimizations can also be made from
the suggestions and feedback offered by the compiler trace. This is one reason
why OpenACC has a quick learning curve and cuts down the code development
time[19]. The code development cycle described earlier was followed for each
code block in the parallelizable regions iteratively until a satisfactory
performance was achieved. Details of the incremental GPU implementation are
presented below.

Figure 2: Schematics representing the minimal code changes when using OpenMP
and OpenACC

####  3.4.1 Analysis

Using Nsight-systems, the serial CPU solver SOL0 was initially profiled on the
local system in which the functions: (i) flagging/classification of solid and
fluid points, (ii) iterative solvers for pressure and velocity corrections
were identified to be the most time-consuming regions followed by the code
block involving (iii) body-force interpolation function as seen in Fig. 3 and
Table 1. The remaining regions of the code are executed serially and consume
very little time as compared to the parallelizable sections.

As a preliminary analysis, the theoretical speedup $S_{theory}$ possible
through parallelization of code regions over the serial execution is given by
Amdahl’s law, such that [25]

$S_{theory}=\frac{1}{(1-p)+p/n},$ (5)

where $n$ is the number of processor cores and $p=T_{par}/T_{wall}$ is the
parallel portion of the code in terms of wall time taken for execution of the
code respectively. Here, $T_{ser}$ and $T_{par}$ are the time taken by serial
and parallel sections of the code, respectively. Whereas, total wall time of
the code, $T_{wall}$ is given by, $T_{wall}=T_{ser}+T_{par}.$ In an ideal
scenario, with effective parallelization of the parallel portion, the total
wall time $T_{wall}$ comes down closer to $T_{ser}$, with $T_{par}<<T_{ser}.$
In the present study, potentially parallelizable regions in SOL0 comprise
$99.8\%$ of the total wall time when executed serially, and hence,
$p=T_{par}/T_{wall}=0.998$. Thus, the maximum speedup possible in the limit of
an extremely large number of processor cores (i.e $n\to\infty$, therefore
$p/n\to 0$) would be $S_{theory}=1/((1-0.998)+0)=500$ times the sequential
code. However, the theoretical speedup is not always achievable owing to
various factors such as a finite number of processor cores, hardware latency,
data transfers between CPU and GPU, synchronization of threads, and lower
processor clock speed of GPUs as compared to CPU. Hence, the obtained speedup
is much lesser. But, the effects of these factors can by minimized by
profiling the code to identify the code hot spots needing optimization, and
appropriate OpenACC pragmas can be added.

Table 1: Sequential CPU time for the functions identified to be parallelizable hot spots Function |  Computational time per time step (in seconds)
---|---
P iterative solver |  3.835
Fluid/solid flagging |  2.5515
U-V iterative solver |  0.5518
Body force interpolation |  0.0758

####  3.4.2 Parallelisation of loops

The parallelizable code blocks are often characterized by for loops. In the
OpenMP implementation SOL1, the directive parallel for along with clauses
default(shared) for data sharing of shared variables and schedule(dynamic) for
balancing the workload distribution on the CPU threads were used for the
hotspot regions earlier noted in Fig. 3 and in [16]. In the GPU
implementation, OpenACC directives such as kernels or parallel for can be
added one by one before each potentially parallelizable code block /for
loop/statement in the hotspots identified earlier (see Section 3.4.1). The
kernels directive is more flexible than the parallel for directive as it lets
the compiler decide which regions within the scope of the construct are
parallelizable and the compiler trace sheds more light on the specific
optimizations and degrees of parallelism that can be brought in. To
parallelize for loops with backward data dependencies, temporary variables can
be allocated to swap and update the values. Although this would increase the
memory requirement, it is offset by the improvement in speedup. Also, to avoid
race conditions, selected variables in the scope of the code block that are
offloaded onto GPU need to be appropriately privatized using the
private(variable list) clause.

In the GPU implementation SOL2, classification/flagging of solid-fluid points
function was first ported to GPU and then the pressure/velocity correction
solver functions were ported using appropriate OpenACC directives and clauses.
As mentioned in section 3.4.1, body force interpolation procedure was also
parallelized and offloaded onto the GPU in SOL2.

####  3.4.3 Optimisation of loops

Following the feedback from the compiler trace, appropriate directives/clauses
were further added for optimization. Specifically, routine and seq directives
were added wherever there were sequential user-defined functions that needed
to be executed on the GPU to avoid unnecessary data transfers between the CPU
and the GPU. Also, care was taken to ensure that these offloaded sequential
operations were not computationally intensive. Additionally, collapse and
reduction clauses were added for vectorization and to avoid race conditions
through simultaneous read and write operations respectively. Further
optimizations such as explicit mapping of for loops to the GPU threads and
other intricate data management constructs can also be implemented (for more
details, refer to [19, 17]). However, in the present study, the code
development cycle was stopped when a satisfactory speedup was obtained for
SOL2, and the intricate optimizations were left for future work.

Figure 3: Nsight-systems profiler output for the NVTX annotated serial version
of the IBM solver for a single time marching step.

####  3.4.4 Data management

Data management is crucial in OpenACC implementation as CPUs and GPUs have
different memory architectures. Because of this, variables are first allocated
on the CPU and then copied to GPU where computations are then carried out.
This leads to multiple data transfers between CPU and GPU which gets limited
by latency overheads and the memory bandwidth of GPU, thereby impeding the
solver performance. This can be avoided by minimizing data transfers using
OpenACC’s data management directive[19] appended with appropriate copyin,
copyout or copy clauses. This drastically improves the performance because all
computations can be carried out at once when the required data for all of them
are hosted on the GPU at the time of execution. In the present study, all the
variables were copied to the GPU at the beginning of every time marching step
of the solver. This is because file write operations that need to be carried
out at the end of every few time steps take place only on the CPU. Hence, data
transfers although significantly minimized, were necessary at the beginning
and end of every time step for SOL2 as seen in Fig. 4.

Figure 4: Final Nsight-systems profiler outputs for the NVTX annotated OpenACC
version of the IBM solver for a single time marching step.

##  4 Results and discussion

###  4.1 Validation studies

A Reynolds number, $Re=500$, non-dimensional plunging velocity $k\bar{h}=1.0$
with $k=2\pi$ and $\bar{h}=0.16$ are chosen for validation. The aerodynamic
force coefficient time histories obtained from the simulations were compared
with that of the baseline solvers SOL0, SOL1 and the work of Khalid _et
al._[2] in Fig. 5. The results are in good agreement with each other for SOL0,
SOL1 and SOL2 solvers with almost no deviations, and also corroborate well
with the results of Khalid _et al._[2]. The small discrepancies observed in
the aerodynamic coefficients between the present numerical studies and the
literature[2], especially in drag coefficient (see Fig. 5(b)), are attributed
to underlying differences in the numerical method used in [2] and [7].

(a)

(b)

Figure 5: Plots comparing the (a) lift and (b) drag coefficient time histories
for serial, OpenMP, OpenACC implementations with the results of Khalid _et
al._[2] for a sinusoidally plunging rigid elliptic foil.

###  4.2 Performance analysis

####  4.2.1 Speedup characterisation

Cases for each solver setting are run thrice to obtain the average wall times
for SOL0, SOL1, and SOL2. To characterize the speedup of the parallel solvers
SOL1 and SOL2, the wall times of SOL0 are considered as references. The
speedup $S$ can be calculated using the wall times as follows

$S_{SOLi}=T_{SOL0}/T_{SOLi}\;\;\mbox{for i = 1,2}$ (6)

The relative speedup obtained by SOL2 over SOL1 is calculated as follows

$S_{relative}=S_{SOL2}/S_{SOL1}$ (7)

Additionally, the evolution of average speedup of SOL2 over SOL0 with the
increasing number of time steps is considered for the first $10,100,1000$ and
$10000$ time steps respectively (see Fig. 6(a)). On considering the overall
speedup for the first 1000 time steps alone, it is observed that a significant
reduction, in turn, around times (see Table 2) is achieved that results in
almost a speedup of the order $O(10^{2})$ and $O(10)$ over SOL0 and SOL1,
respectively.

Mesh Levels | M1 (6L) | M2 (12L) | M3 (18L)
---|---|---|---
Solver version |  |  |
SOL0 | 13140s | 24663s | 39994s
SOL1 | 4232s | 8175s | 11953s
SOL2 | 244.4s | 378s | 368.3s
Table 2: Average wall time for serial CPU, OpenMP and OpenACC GPU solvers
executed for the first 1000 time steps

(a)

(b)

Figure 6: (a) Evolution of speedup as a function of timestep for the GPU
ported IBM solver at various mesh levels, and (b) bar graph depicting the
relative speedup of OpenACC version obtained over serial and openMP versions
at different mesh levels and for the first 1000 time steps

####  4.2.2 Input scaling performance

Along with speedup, given the massive number of GPU cores, it is important
that scaling of speedup concerning increasing mesh levels of the computation
domain is studied. To this effect, three levels of mesh were considered, M1,
M2, and M3 with 6, 12, and 18 Lakh grid cells respectively. In Fig. 6(a), as
the number of time steps are increased, a flattening trend is observed in the
case of meshes M1 and M2 but in the case of M3, the speedup scales linearly
with time up to 1000 time steps and then dips suddenly. The significant
difference in speedup pattern for the mesh M3 compared to M1 and M2 is
attributed to the uncertainty in job allocation on the GPU nodes of AQUA
cluster. The jobs pertaining to M1 and M2 were often run on one GPU node while
those of M3 ran on another GPU nodes with multiple concurrent jobs running
simultaneously.

The overall and relative speedup obtained for SOL2 over SOL1 and SOL0 for the
first 1000 time steps are presented for the three mesh levels in 6(b). The
OpenACC-based solver scales almost linearly with increasing mesh size compared
to the sequential and OpenMP versions. This indicates the effective
utilization of GPU cores with increasing mesh size. This is in contrast to the
OpenMP version of the solver where speedup over serial code is almost constant
across mesh levels.

##  5 Conclusion

To reduce the turnaround time of an IBM-based unsteady flow solver, OpenACC
was chosen as the GPU porting pathway owing to its similarity with OpenMP,
minimal code intrusion, and development time. Computationally intensive
parallel routines were offloaded onto the GPU with minimal data transfers
using appropriate directives and clauses provided in the OpenACC framework by
adopting an incremental code development cycle. Finally, significant speedups
up to the order $O(10)$ and $O(10^{2})$ over the OpenMP and serial solver
versions were obtained, respectively. Improved performance of the GPU ported
solver is a result of (i) parallelized code regions that were otherwise
executed sequentially in the openMP version, (ii) optimized code blocks / for
loops/functions with specific directives and clauses ensuring no data
dependency, data conflicts, and race condition, and (iii) minimized data
transfers between CPU and GPU. With increasing mesh size, the speedup of
OpenACC version scaled almost linearly owing to the effective utilization of
the GPU cores as compared to the constant speedup of the OpenMP version of the
code. Extension of the parallelization strategy followed in the present work
to other in-house IBM-based non-linear fluid-structure interaction solvers
being developed with a similar performance analysis and validation is left for
future work.

ACKNOWLEDGEMENTS
We thank the HPCE team of IIT Madras for providing us with computational
resources of AQUA super cluster. We also thank CDAC-Pune and NVIDIA for the
guidance provided during the CDAC-GPU hackathon 2020, organized under the
aegis of National Super Computing Mission, Govt. of India.

## References

  * [1] Gregory C Lewin and Hossein Haj-Hariri.  Modelling thrust generation of a two-dimensional heaving airfoil in a viscous flow.  Journal of Fluid Mechanics, 492:339, 2003.
  * [2] Muhammad Saif Ullah Khalid, Imran Akhtar, Haibo Dong, Nida Ahsan, Xiaoping Jiang, and Binxin Wu.  Bifurcations and route to chaos for flow over an oscillating airfoil.  Journal of Fluids and Structures, 80:262–274, 2018.
  * [3] JCS Lai and MF Platzer.  Jet characteristics of a plunging airfoil.  AIAA journal, 37(12):1529–1537, 1999.
  * [4] Michael J Shelley and Jun Zhang.  Flapping and bending bodies interacting with fluid flows.  Annual Review of Fluid Mechanics, 43:449–465, 2011.
  * [5] John Young and Joseph CS Lai.  Vortex lock-in phenomenon in the wake of a plunging airfoil.  AIAA journal, 45(2):485–490, 2007.
  * [6] Chandan Bose and Sunetra Sarkar.  Investigating chaotic wake dynamics past a flapping airfoil and the role of vortex interactions behind the chaotic transition.  Physics of fluids, 30(4):047101, 2018.
  * [7] Dipanjan Majumdar, Chandan Bose, and Sunetra Sarkar.  Capturing the dynamical transitions in the flow-field of a flapping foil using immersed boundary method.  Journal of Fluids and Structures, 95:102999, 2020.
  * [8] Xavier Álvarez-Farré, Andrey Gorobets, and F Xavier Trias.  A hierarchical parallel implementation for heterogeneous computing. application to algebra-based cfd simulations on hybrid supercomputers.  Computers & Fluids, 214:104768.
  * [9] Charles A Mader, Gaetan KW Kenway, Anil Yildirim, and Joaquim RRA Martins.  Adflow: an open-source computational fluid dynamics solver for aerodynamic and multidisciplinary optimization.  Journal of Aerospace Information Systems, 17(9):508–527, 2020.
  * [10] István Z Reguly and Gihan R Mudalige.  Productivity, performance, and portability for computational fluid dynamics applications.  Computers & Fluids, 199:104425, 2020.
  * [11] Stephen L Wood, Kevin Jacobson, William T Jones, and William K Anderson.  Sparse linear algebra toolkit for computational aerodynamics.  In AIAA Scitech 2020 Forum, page 0317, 2020.
  * [12] Charles S Peskin.  The immersed boundary method.  Acta numerica, 11:479–517, 2002.
  * [13] Rajat Mittal and Gianluca Iaccarino.  Immersed boundary methods.  Annu. Rev. Fluid Mech., 37:239–261, 2005.
  * [14] Thomas Wick.  Solving monolithic fluid-structure interaction problems in arbitrary lagrangian eulerian coordinates with the deal. ii library.  Archive of Numerical Software, 1(1):1–19, 2013.
  * [15] Jungwoo Kim, Dongjoo Kim, and Haecheon Choi.  An immersed-boundary finite-volume method for simulations of flow in complex geometries.  Journal of computational physics, 171(1):132–150, 2001.
  * [16] Chhote Lal Shah, Dipanjan Majumdar, and Sunetra Sarkar.  Performance enhancement of an immersed boundary method based fsi solver using openmp.  In Annual CFD Symposium. NAL, Bangalore, 2019.
  * [17] Weicheng Xue and Christopher J Roy.  Heterogeneous computing of cfd applications on cpu-gpu platforms using openacc directives.  In AIAA Scitech 2020 Forum, page 1046, 2020.
  * [18] Maxim Naumov.  Incomplete-lu and cholesky preconditioned iterative methods using cusparse and cublas.  Nvidia white paper, 3, 2011.
  * [19] Sunita Chandrasekaran and Guido Juckeland.  OpenACC for Programmers: Concepts and Strategies.  Addison-Wesley Professional, 2017.
  * [20] Rob Farber.  Parallel programming with OpenACC.  Newnes, 2016.
  * [21] Tetsuya Hoshino, Naoya Maruyama, Satoshi Matsuoka, and Ryoji Takaki.  Cuda vs openacc: Performance case studies with kernel benchmarks and a memory-bound cfd application.  In 2013 13th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing, pages 136–143. IEEE, 2013.
  * [22] Makoto Sugawara, Shoichi Hirasawa, Kazuhiko Komatsu, Hiroyuki Takizawa, and Hiroaki Kobayashi.  A comparison of performance tunabilities between opencl and openacc.  In 2013 IEEE 7th International Symposium on Embedded Multicore Socs, pages 147–152. IEEE, 2013.
  * [23] Xuechao Li, Po-Chou Shih, Jeffrey Overbey, Cheryl Seals, and Alvin Lim.  Comparing programmer productivity in openacc and cuda: an empirical investigation.  International Journal of Computer Science, Engineering and Applications (IJCSEA), 6(5):1–15, 2016.
  * [24] Haecheon Choi and Parviz Moin.  Effects of the computational time step on numerical solutions of turbulent flow.  Journal of Computational Physics, 113(1):1–4, 1994.
  * [25] GM Amdahl.  Validity of single-processor approach to achieving large-scale computing capability, proceedings of afips conference, reston, 1967.


Multi-scale information content measurement method based on Shannon
information

Zsolt Pocze

Volgyerdo Nonprofit Kft., Nagybakonak, HUN<EMAIL_ADDRESS>2023

###### Abstract

In this paper, we present a new multi-scale information content calculation
method based on Shannon information (and Shannon entropy). The original method
described by Claude E. Shannon and based on the logarithm of the probability
of elements gives an upper limit to the information content of discrete
patterns, but in many cases (for example, in the case of repeating patterns)
it is inaccurate and does not approximate the true information content of the
pattern well enough. The new mathematical method presented here provides a
more accurate estimate of the (internal) information content of any discrete
pattern based on Shannon’s original function. The method is tested on
different data sets and the results are compared with the results of other
methods like compression algorithms.

##  1 Introduction

Traditionally, Shannon’s information theory [15] has been used to measure the
information content of samples. Shannon information, as defined by Claude E.
Shannon, is the degree of uncertainty or surprise associated with a given
outcome in a set of possible outcomes. Shannon entropy, which is the expected
value of Shannon information, is used to quantify the average information
content of a discrete sample or message. It serves as a basic concept in
information theory and is widely used in communication systems and data
compression.

In some situations, such as repeated patterns, Shannon’s original information
measurement method does not give accurate results enough because it does not
take into account the structure of the patterns, it only looks at certain
statistical characteristics of them. To solve this problem, this paper
presents a new multiscale information content calculation method based on
Shannon’s original principles. By refining the computational approach, our
method offers a more accurate estimate of the internal information content of
discrete samples, regardless of their nature.

There are several other methods for measuring the information content of
patterns, such as Kolmogorov complexity [8], randomness [11], and compression
complexity. The common property of these methods that they are all suitable
for determining and understanding the information content of patterns with
some accuracy, and therefore provide a suitable comparison basis for checking
newer methods.

To verify the effectiveness of our new method, it is applied to various data
sets and compared with compression algorithms. The results show that our
proposed method based on Shannon information closely approximates the results
measured by other methods while taking a completely different approach.

##  2 Patterns

In this study, we deal with the calculation of the internal quantitative
information content of discrete patterns. From the point of view of the
calculation of the information content, the nature of the object of the
measurement is irrelevant. The information content of events, signals, system
states, or data sequences can be calculated since their models (with finite
precision) can all be represented as discrete patterns. By moving along a
spatial pattern, we get a temporal pattern and vice versa. Therefore, we do
not distinguish between spatial and temporal patterns. The basic markings
should be as follows.

Denote$\mathcal{M}(R)$ the set of finite sequences that can be generated from
the set $R$:

$\mathcal{M}(R)=\\{X:\mathbb{N}^{+}\rightarrow R\\}$ (1)

Let us call the finite sequence $X\in\mathcal{M}(R)$ a pattern:

$X=[x_{1},...,x_{N}]$ (2)

Denote the length of the series $X$:

$n(X)=N$ (3)

Denote the set of possible values of the series $X$:

$R=R_{X}=\\{r_{1},r_{2},...,r_{K}\\}$ (4)

Let $f(x)$ denite the number of occurrences of $x\in R_{X}$ in the series of
$X$:

$f(x)=\sum_{i=1}^{K}[r_{i}=x]$ (5)

Let the relative frequency of any $x\in R$ element of the pattern $X$:

$p(x)=f(x)/N$ (6)

Denote the concatenation of $X_{1}X_{2}...X_{K}$ patterns as:

$X_{1}X_{2}...X_{K}=\stackrel{{\scriptstyle[}}{{i}}=1]{K}{\|}X_{i}$ (7)

##  3 Information content

The information content can be interpreted intuitively when only the
interpretable information content is examined [1]. In this study we examine
the amount of the entire internal information content without interpreting it
or considering the context.

The information content of a pattern can be characterized by the improbability
of individual elements of the pattern (Shannon information [15]), the length
of the most concise description of the pattern (Kolmogorov complexity [8]), or
the degree of randomness of the pattern [11].

A fundamental difference between Shannon’s and Kolmogorov’s viewpoints is that
Shannon considered only the probabilistic characteristics of the random source
of information that created the pattern, ignoring the pattern itself. In
contrast, Kolmogorov only focused on the pattern itself [5]. In their
definition, Kolmogorov and Chaitin called (inaccurately) random the pattern
with the maximum information content [12].

Information, complexity and randomness have such similar properties that we
can reasonably assume that they are essentially approaching the same thing
with different methods. It is sufficient to consider that the Shannon
information, Kolmogorov complexity and randomness of a pattern consisting of
identical elements are all minimal, while in the case of a true random pattern
all three values are maximal, and they all assign the highest information
value to data sets with maximum entropy [1].

The concepts of entropy and information are often confused [3], so it is
important to mention that entropy can also be understood as such the average
information content per element.

Approached intuitively, the amount of information is a function for which the
following conditions are met:

  1. 1.

The information content of a pattern with zero length or consisting of
identical elements is zero.

  2. 2.

The information content of the pattern consisting of repeating sections is
(almost) identical to the information content of the repeating section.

  3. 3.

A pattern and its reflection have the same information content.

  4. 4.

The sum of the information content of patterns with disjoint value sets is
smaller than the information content of the concatenated pattern.

  5. 5.

The information content of true random patterns is almost maximal.

Let the information content be the function $I$ that assigns a non-negative
real number to any arbitrary pattern $X\in\mathcal{M}(R)$:

$I:\mathcal{M}_{R}\rightarrow\mathbb{R}^{+}$ (8)

In addition, the following conditions are met:

  1. 1.

$I(X)=0\Leftrightarrow|R_{X}|<2$

  2. 2.

$I(\stackrel{{\scriptstyle[}}{{i}}=1]{K}{\|}X)=I(X)$

  3. 3.

$I(\stackrel{{\scriptstyle[}}{{i}}=1]{K}{\|}X_{i})=I(\stackrel{{\scriptstyle[}}{{i}}=K]{1}{\|}X_{i})$

  4. 4.

$|\stackrel{{\scriptstyle[}}{{i}}=1]{K}{\cap}R_{X_{i}}|=\emptyset\Rightarrow
I(\stackrel{{\scriptstyle[}}{{i}}=1]{K}{\|}X_{i})>\stackrel{{\scriptstyle[}}{{i}}=1]{K}{\sum}I(X_{i})$

  5. 5.

$I(X)\leq I(X_{TR}),\forall X\in\mathcal{M}(R),|X|=|X_{TR}|$, where
$X_{TR}\in\mathcal{M}(R)$ is a real random pattern.

Since any pattern can be described in non-decomposable binary form, the unit
of information content should be the bit.

It can be seen that for any pattern $X\in\mathcal{M}(R)$, if $N=n(X)$ and
$K=|R|$, then the maximum information content of $X$ is:

$I_{MAX}(X)=N\cdot log_{2}(K)$ (9)

That is, $I(X)\leq I_{MAX}(X)$ for any pattern $X\in\mathcal{M}(R)$. In the
case of a binary pattern, $I_{MAX}(X)=N$, the length of the pattern, which
means that a maximum of $N$ bits of information (decision) is required to
describe the pattern.

If the maximum information content is known, the relative information content
can be calculated:

$I^{(rel)}(X)=I(X)/I_{MAX}(X)$ (10)

##  4 Shannon information

In theory, Kolmogorov complexity would provide a better approximation of the
information content of patterns, but it has been proven that it cannot be
calculated [5], in contrast to Shannon information [15], which can be
calculated efficiently, but approximates the actual information content less
well. Shannon information calculates the information content of the pattern
based on the expected probability of occurrence (relative frequency) of the
elements of the pattern.

The Shannon information of an arbitrary pattern $X\in\mathcal{M}(R)$:

$I_{S}(X)=\sum_{i=1}^{N}log_{2}(\frac{1}{p(x_{i})}))$ (11)

Since the relative frequency (expected occurrence) of the elements of the
pattern is only one statistical characteristic of the pattern and does not
take into account the order of the elements. That’s why the Shannon
information often gives a very inaccurate estimate of the information content.

The value of the Shannon information is the same for all patterns of the same
length whose elements have the same relative frequency. If
$X\in\mathcal{M}(R)$, $Y\in\mathcal{M}(Q)$ and $|R|=|Q|=K$ then it holds that:

$I_{S}(X)=I_{S}(Y),\>if\>\\{p(r_{1}),p(r_{2}),...,(r_{K})\\}=\\{p(q_{1}),p(q_{2}),...,(q_{K})\\}$
(12)

Shannon information ignores the structure of the patterns at different scales,
the laws encoded in them, and therefore overestimates the information content
of patterns consisting of repeating sections.

The problem can be illustrated with a simple example. Let’s calculate the
Shannon entropy of the following three patterns:

  1. 1.

$X_{A}:\>001101101010111001110010001001000100001000010000$

  2. 2.

$X_{B}:\>101010101010101010101010101010101010101010101010$

  3. 3.

$X_{C}:\>111111110000000011111111000000001111111100000000$

In all three cases, the set of values is $R={0,1}$, the probability of each
element is $p(0)=0.5$ and $p(1)=0.5$, and the Shannon entropy is
$I_{S}(X)=\stackrel{{\scriptstyle[}}{{i}}=1]{N}{\sum}log_{2}(\frac{1}{p(x_{i})})=16\>bit$,
although it is obvious that the information content of the data series differs
significantly. Due to its randomness, the information content of data line
$X_{A}$ is almost 16 bits, while the information content of the other two data
lines is much smaller, as they contain repeated sections. In the $X_{B}$ data
line, for example, the 2-bit section $[10]$ is repeated, which means that its
information content is closer to 2 bits.

The problem is that in the example above, we are examining the datasets at an
elementary level, and our Shannon entropy function does not take into account
the larger-scale structure of the dataset, such as the presence of repeating
segments longer than 1 signal. Therefore, it is obvious to develop methods
that are based on the Shannon entropy, but the data series are analyzed in the
entire spectrum of the resolution, in the entire frequency range, and thus
provide a more accurate approximation of the information content of the data
series. Countless such solutions have already been published, which can be
read, for example, in the articles [2] and [6]. This article presents an
additional method.

##  5 SSM information

###  5.1 Shannon information spectrum

Let the pattern $X$ be partitioned by sections of length $r$ if $m=[N/r]$:

$X^{(r)}=[x_{1}...x_{r},x_{r+1}...x_{2r},\>...,\>x_{(m-1)\cdot
r+1}...x_{m\cdot r}]$ (13)

Let the following series denoted as Shannon information spectrum (SP) of
pattern $X$:

$I_{SP}^{(r)}(X)=I_{S}(X^{(r)}),\>r=1,...,[N/2]$ (14)

From the sequences $X^{(r)}$, we omit (truncated) partitions shorter than $r$,
those that are shorter than $r$. In the cases $r>[N/2]$, $I_{SP}(X^{(r)})=0$,
so these are also omitted from the spectrum.

Figure 1. Diagram $A$ shows the Shannon information spectrum of the random
pattern $X_{A}$, and diagram $B$ shows the repeating pattern$X_{C}$ (Appendix
I). It can be seen that in case $B$, a lower value appears at certain
frequencies.

###  5.2 Maximal Shannon information spectrum

The Shannon information spectrum will be maximum in the case of random data
sets. Let the following formula denoted as maximum Shannon information
spectrum (SMS):

$I_{SMS}^{(r)}(X)=m\cdot log_{2}(min(K^{r},m)),\>r=1,...,[N/2]$ (15)

$I_{SMS}^{(r)}(X)$ is a supremum for all information spectrum having the same
value set and pattern length. If $K^{r}<m$, then in the case of random
patterns, the value set of the partitioning contains most likely all possible
partitions, so the information content is approximately $m\cdot
log_{2}(K^{r})$. If $K^{r}>m$, then the partitioning cannot contain all
possible partitions, each partition will most likely be unique, so the
information content will be $m\cdot log_{2}(m)$. If $r$ is small enough, then
the series $X^{(r)}$ most likely contains all possible partitions, therefore
by random data sets the measured amount of information will approximately
equal the maximum possible information content of the pattern, i.e. if $r$ is
small, then $I_{SPM}^{(r)}(X^{(r)})\approx I_{MAX}(X^{(r)})=N\cdot
log_{2}(n)$.

Figure 2. Comparison of maximum Shannon information spectrum (ISMS) and
Shannon information spectrum (ISP) of the repeating pattern $X_{C}$.

###  5.3 Shannon normalized information spectrum

If we are interested in how much the information content seems to be relative
to the maximum value in each resolution, we can normalize the spectrum with
the maximum spectrum to the range $[0-N\cdot log_{2}(n)]$. Let the following
sequence denoted as Shannon normalized information spectrum (SNS):

$I_{SNS}^{(r)}(X)=\begin{cases}\frac{I_{SP}^{(r)}(X)}{I_{SMS}^{(r)}(X)}\cdot
I_{MAX}(X),&if\>|R_{X^{(r)}}|>1\\\
r\cdot\frac{I_{SP}^{(1)}(X)}{N},&if\>|R_{X^{(r)}}|=1\end{cases}\quad
where\>r=1,...,[N/2]$ (16)

If the value set of the partitioning has only one element, i.e.
$|R_{X^{(r)}}|=1$, the normalized value would be $0$. In this case the
information content should be the information content of the repeating
partition, and the average Shannon entropy of an element of the elementary
resolution is multiplied by the length of the partition:
$r\cdot\frac{I_{SP}^{(1)}(X)}{N}$.

Figure 3. Comparison of Shannon normalized information spectrum (S of patterns
from very different sources. The vertical axis represents the amounts of bits
of information measured at the given resolution. You can see how different the
spectrum of the different patterns is, but in most cases there is a resolution
where the information content shows a definite minimum. The minima are marked
with an arrow. A: random binary pattern, B: binary pattern with repeating
sections, C: DNA section, D: English text, E: ECG signal, F: audio recording
containing speech, G: evolution of the number of sunspots between 1700-2021,
H: seismogram , I: Lena’s photo.

The figures show that different types of patterns have very different and
characteristic spectra. This suggests that the type or source of the pattern
may be inferred from the nature of the spectrum, but we do not deal with this
in this study.

###  5.4 SSM information

We know that the Shannon information gives an upper estimate in all cases, so
we get the most accurate approximation of the information content from the
normalized spectrum if we take the minimum. Let the information content
calculated from the normalized spectrum denoted as Shannon spectrum minimum
information (SSM information):

$I_{SSM}(X)=\stackrel{{\scriptstyle[}}{{i}}=1]{[N/2]}{min}(I_{SNS}^{(i)}(X))$
(17)

Shannon information, SSM information and compression complexity of different
patterns (Appendix I) in bits:

Pattern | Source | $I_{MAX}(X)$ | $I_{S}(X)$ | $I_{SSM}(X)$ | $I_{ZIP}(X)$ | $I_{7Z}(X)$ | $I_{ZPAQ}(X)$
---|---|---|---|---|---|---|---
XA | Random binary pattern. | 48 | 46 | 40 |  |  |
XB | Repeating binary pattern. | 48 | 48 | 2 |  |  |
XC | Repeating binary pattern. | 48 | 48 | 13 |  |  |
XD | Repeating text. | 362 | 343 | 58 |  |  |
XE | Duplicate text with one character error. | 374 | 347 | 116 |  |  |
XF | Random DNA pattern. | 471 | 422 | 409 |  |  |
XG | DNA segment of COVID virus. | 471 | 405 | 388 |  |  |
XH | Random string (0-9, a-z, A-Z). | 1209 | 1174 | 1174 |  |  |
XI | English text (James Herriot’s Cat Stories). | 1104 | 971 | 971 |  |  |
XJ | Solar activity between 1700-2021 (A-Z). | 1495 | 1349 | 1295 |  |  |
XK | Isaac Asimov: True love. | 50901 | 37266 | 32649 | 30904 | 29968 | 25248
XL | Binary ECG signal. | 80000 | 79491 | 47646 | 52320 | 41032 | 36968
XM | Binary seismic data. | 313664 | 312320 | 171546 | 83920 | 66064 | 45824
XN | Speech recording. | 325472 | 325342 | 277489 | 286760 | 257856 | 251408
XO | Lena. | 524288 | 524216 | 422085 | 443096 | 371360 | 337408

Table 1. Comparison of SSM information and compression complexity of different
patterns.

Relative Shannon information, SSM information, and compression complexity of
different patterns (Appendix I) compared to maximum information:

Pattern | Source |  $I_{S}^{(rel)}(X)$ % |  $I_{SSM}^{(rel)}(X)$ % |  $I_{ZIP}^{(rel)}(X)$ % |  $I_{7Z}^{(rel)}(X)$ % |  $I^{(rel)}{}_{ZPAQ}(X)$ %
---|---|---|---|---|---|---
XK | Isaac Asimov: True love. | 73 | 64 | 61 | 59 | 50
XL | Binary ECG signal. | 99 | 60 | 65 | 51 | 46
XM | Binary seismic data. | 100 | 55 | 27 | 21 | 15
XN | Speech recording. | 100 | 85 | 88 | 79 | 77
XO | Lena. | 100 | 81 | 85 | 71 | 64

Table 2. Comparison of relative SSM information and relative compression
complexity of different patterns.

It can be seen from the table that the SSM information gives similar results
as the compression algorithms. In general, it is true that the more
computationally demanding a compression or information measurement procedure
is, the closer it is to Kolmogorov complexity. In the examined examples, the
results of SSM information are usually located between the results of ZIP and
7Z, so the computational complexity of SSM information must be similar to the
computational complexity of ZIP and 7Z.

Figure 4. Comparison of the results of different information measurement
methods.

Figure 5. Comparison of the average results of different information
measurement methods.

###  5.5 Comparison with computational complexity

If we do not know the signal set of the signal sequence, the first step is to
determine the number of signals occurring in the signal sequence, which has an
asymptotic complexity of $\mathcal{O\mathrm{(}}N\cdot logN)$.

Determining the Shannon information consists of two steps. In the first step,
we determine the frequency of signals, which has a complexity of
$\mathcal{O\mathrm{(}}N)$, and in the second step, we sum up the entropy of
each signal, so the total complexity of the Shannon information is
$\mathcal{O\mathrm{(}}N\cdot
logN)+\mathcal{O\mathrm{(}}N)=\mathcal{O\mathrm{(}}N\cdot logN)$.

For the ZIP, 7Z and ZPAQ algorithms used to calculate the compression
complexity, the complexity is usually between $\mathcal{O\mathrm{(}}N)$ and
$\mathcal{O\mathrm{(}}N\cdot logN)$, but for ZPAQ may be greater [7] [14]
[13].

In the case of SSM information, the first step is also to determine the
frequency of signals, which has a complexity of $\mathcal{O\mathrm{(}}N)$. In
the second step, the Shannon information spectrum is calculated
$\mathcal{O\mathrm{(}}N)+\mathcal{O\mathrm{(}}N/2)+\mathcal{O\mathrm{(}}N/3)+...+\mathcal{O\mathrm{(}}2)=\mathcal{O\mathrm{(}}N\cdot
logN)$ complexity, finally the minimum of the spectrum can be determined
$\mathcal{O\mathrm{(}}N)$ with complexity. The complexity of calculating the
SSM information in the worst case is
$\mathcal{O\mathrm{(}}I_{SSM}(X))=\mathcal{O\mathrm{(}}N\cdot
logN)+\mathcal{O\mathrm{(}}N)+\mathcal{O\mathrm{(}}N\cdot
logN)+\mathcal{O\mathrm{(}}N)=\mathcal{O\mathrm{(}}N\cdot logN)$ , which is
identical to compression algorithms.

###  5.6 Known issues

All methods of calculating the amount of information have inaccuracies. One of
the problems with SSM information is that if the repetition in a repeating
pattern is not perfect, the value of the SSM information is larger than
expected, as shown in the example below.

$X$ |  $I_{SSM}(X)$[bit]
---|---
123456789 123456789 123456789 | 29
223456789 123456789 123456789 | 50

Table 3. One element change can cause a notable difference in SSM information.

##  6 Conclusion

It can be shown SSM information can determine the information content of the
patterns with an accuracy comparable to the compression algorithms, but at the
same time it is simple. In addition information spectrum presented here
provides a useful visual tool for studying the information structure of
patterns in the frequency domain.

## References

  * [1] Pieter Adriaans.  Facticity as the amount of self-descriptive information in a data set.
  * [2] Benjamin Allen, Blake Stacey, and Yaneer Bar-Yam.  Multiscale information theory and the marginal utility of information.  Entropy, 2017.
  * [3] Arieh Ben-Naim.  Entropy and information theory: Uses and misuses.  Entropy, 2019.
  * [4] A. Goldberger, L. Amaral, L. Glass, J. Hausdorff, P. C. Ivanov, R. Mark, and H. E. Stanley.  Physiobank, physiotoolkit, and physionet: Components of a new research resource for complex physiologic signals.  Circulation, 2000.
  * [5] Peter Grunwald and Paul Vitanyi.  Shannon information and kolmogorov complexity.  CoRR, 2004.
  * [6] Anne Humeau-Heurtier.  The multiscale entropy algorithm and its variants: A review.  Entropy, 2015.
  * [7] Juha Karkkainen.  Fast bwt in small space by blockwise suffix sorting.  Theoretical Computer Science, 2007.
  * [8] A. N. Kolmogorov.  On tables of random numbers.  Mathematical Reviews, 1963.
  * [9] Ervin Laszlo.  Introduction to Systems Philosophy.  Routledge, 1972.
  * [10] Olimpia Lombardi, Federico Holik, and Leonardo Vanni.  What is shannon information?  Synthese, 2015.
  * [11] Laszlo Lovasz.  Information and complexity (how to measure them?).  The Emergence of Complexity in Mathematics, Physics, Chemistry and Biology, Pontifical Academy of Sciences, 1996.
  * [12] Laszlo Lovasz.  Complexity of Algorithms.  Boston University, 2020.
  * [13] Enno Ohlebush Markus Mauer, Timo Beller.  A lempel-ziv-style compression method for repetitive texts.  2017\.
  * [14] John Scoville.  Fast autocorrelated context models for data compression.  2013\.
  * [15] Claude E. Shannon.  A mathematical theory of communication.  Bell System Technical Journal, 1948.

Appendix

I. Example patterns

Notation | A pattern or a detail of the pattern | Length | Explanation
---|---|---|---
$X_{A}$ | 001101101010111001110010001001000100001000010000 | 48 bit | Random binary pattern.
$X_{B}$ | 101010101010101010101010101010101010101010101010 | 48 bit | Repeating binary pattern.
$X_{C}$ | 111111110000000011111111000000001111111100000000 | 48 bit | Repeating binary pattern.
$X_{D}$ | The sky is blue. The sky is blue. The sky is blue. | 101 characters | Repeating text.
The sky is blue. The sky is blue. The sky is blue.
$X_{E}$ | The sky is blue. The sky is blue. The sky is blue. | 101 characters | Duplicate text with one character error.
The sky is blue. The sky is glue. The sky is blue.
$X_{F}$ | cagtttctagctatattagcgggcacgactccactgcgcctatgcggaag | 200 characters | Random DNA pattern.
cttgatcaaattttgaccagatcttaggtaacctgaacaagtcagttcgt
aggcgtcgattggccgacgggtgcgaagaaaaaagtgatcgttgtccaac
atctctagtacccaccgttgtgatgtacgttatacggacacgagcatatt
$X_{G}$ | cggcagtgaggacaatcagacaactactattcaaacaattgttgaggttc | 200 characters | DNA segment of COVID virus.
aacctcaattagagatggaacttacaccagttgttcagactattgaagtg
aatagttttagtggttatttaaaacttactgacaatgtatacattaaaaa
tgcagacattgtggaagaagctaaaaaggtaaaaccaacagtggttgtta
$X_{H}$ | EK8Pi5sv2npTfzoaMNp87QtT5kbIUQkTJzHwICCstSmg4aksHT | 200 characters | Random string (0-9, a-z, A-Z).
MwztgHFg3j8AoIobN3FycCLidGeyROiNyG5itB9kxyez1LZjFF
HIBjipE7hidZyiJmilXM0mwnxzlzWSfQ0xP1OuFpWosMwS1cjY
t4nyv4ONx1FceWkAf8SdvDGZVzeVzq2EmOqRF6Im2iudcYRswj
$X_{I}$ | I think it was the beginning of Mrs. Bond’s | 221 characters | English text (James Herriot’s Cat Stories)
unquestioning faith in me when she saw me
quickly enveloping the cat till all you could
see of him was a small black and white head
protruding from an immovable cocoon of cloth.
$X_{J}$ | ABCDFIEDBBAAAABEHJJGEEDBDGMSPLHFBACFKMRPLGDCA[...] | 321 characters | Solar activity between 1700-2021 (A-Z).
$X_{K}$ | My name is Joe. That is what my colleague, | 8391 characters | Isaac Asimov: True love.
Milton Davidson, calls me. He is a programmer and
I am a computer program. [...]
$X_{L}$ | 1011000100110011101110111011001100110011[...] | 80000 bit | Binary ECG signal [4].
$X_{M}$ | 110000101000000011000010100000001100001010000[...] | 313664 bit | Binary seismic data.
$X_{N}$ | 0101001001001001010001100100011011100100[...] | 325472 bit | Speech recording.
$X_{O}$ | 1010001010100001101000001010001010100011[...] | 524288 bit | Lena (256x256 pixel, grayscale).