Laboratoire d’Informatique Gaspard Monge, Université Gustave Eiffel, LIGM (UMR
8049), CNRS, ENPC, ESIEE Paris, UPEM, F-77454, Marne-la-Vallée, France and
http://igm.univ-mlv.fr/~alabarre/<EMAIL_ADDRESS>https://orcid.org/0000-0002-9945-6774 Anthony Labarre [500]Theory of
computation Design and analysis of algorithms

# Sorting by Prefix Block-Interchanges

Anthony Labarre

###### Abstract

We initiate the study of sorting permutations using _prefix block-
interchanges_ , which exchange any prefix of a permutation with another non-
intersecting interval. The goal is to transform a given permutation into the
identity permutation using as few such operations as possible. We give a
2-approximation algorithm for this problem, show how to obtain improved lower
and upper bounds on the corresponding distance, and determine the largest
possible value for that distance.

###### keywords:

permutations, genome rearrangements, interconnection network, sorting, edit
distance, prefix block-interchange

##  1 Introduction

The problem of transforming two sequences into one another using a specified
set of operations has received a lot of attention in the last decades, with
applications in computational biology as _(genome) rearrangement problems_
[13] as well as interconnection network design [21]. In the context of
permutations, it can be equivalently formulated as follows: given a
permutation $\pi$ of $[n]=\\{1,2,\ldots,n\\}$ and a generating set $S$ (also
consisting of permutations of $[n]$), find a minimum-length sequence of
elements from $S$ that sorts $\pi$. The problem is known to be -hard in
general [15] and [1]-hard when parameterised by the length of a solution [6],
but some families of operations that are important in applications lead to
problems that can be solved in polynomial time (e.g. _exchanges_ [17], _block-
interchanges_ [10] and _signed reversals_ [14]), while other families yield
hard problems that admit good approximations (e.g. 11/8 for _reversals_ [3]
and for _block-transpositions_ [12]).

Several restrictions of these families have also been studied, one of which
stands out in the field of interconnection network design: the so-called
_prefix constraint_ , which forces operations to act on a prefix of the
permutation rather than on an arbitrary interval. Those restrictions were
introduced as a way of reducing the size of the generated network while
maintaining a low value for its _diameter_ , thereby guaranteeing a low
maximum communication delay [21]. The most famous example is perhaps the
restriction of reversals (which reverse the order of elements along an
interval) to _prefix reversals_ , and the corresponding problem known as
_pancake flipping_ , introduced in [16] and whose complexity was only settled
thirty years later [5].

As Table 1 shows (see [13] for undefined terms), although sorting problems
using interval transformations are now fairly well understood, progress on the
corresponding prefix sorting problems has been lacking, with only two families
whose status has been settled and no approximation ratio smaller than $2$ for
those problems not known to be in ¶. As a result, while the topology of the
_Cayley graph_ generated by those operations might present attractive
properties, efficient routing algorithms (which achieve exactly the same task
as the sorting algorithms in genome rearrangements) are still needed for the
network to be of practical interest.

Table 1: Complexity of some sorting problems on permutations in the unrestricted setting and under the prefix constraint. Operation | Unrestricted | Prefix-constrained
---|---|---
reversal |  -hard [7] |  -hard [5]
signed reversal | in ¶ [14] | open
double cut-and-join |  -hard [8] | open
signed double cut-and-join | in ¶ [22] | open
exchange | in ¶ [17] | in ¶ [1]
block-transposition |  -hard [4] | open
block-interchange | in ¶ [10] | open

In this work, we choose to focus on the family of block-interchanges for the
following reasons:

  1. 1.

Along with double cut-and-joins, they constitute one of the most general kind
of operations on permutations, including both exchanges and block-
transpositions as special cases;

  2. 2.

Their behaviour in the unrestricted setting is understood well enough that we
can hope for the corresponding prefix sorting problem to be in ¶;

  3. 3.

Knowledge about these operations in the prefix setting is lacking and will be
needed for more general studies; for instance, rearrangement problems on
strings are usually -hard, and efficient algorithms to solve them exactly or
approximately routinely rely on techniques developed for permutations [13,
part II], which currently do not exist for prefix block-interchanges.

To the best of our knowledge, the only published work on prefix block-
interchanges is by [9], who studied them on strings and showed that binary
strings can be sorted in linear time, whereas transforming two binary strings
into one another using the minimum number of prefix block-interchanges is
-complete. Our contributions are as follows: we prove tight upper and lower
bounds on the so-called _prefix block-interchange distance_ ; we give an
approximation algorithm which we prove to be a 2-approximation with respect to
two different measures; we show how to tighten those bounds; and finally, we
prove that the maximum value of the distance, an important parameter in some
applications [21], is $\lfloor 2n/3\rfloor$.

##  2 Notation and definitions

A _permutation_ is a bijective application of a set (usually
$[n]=\\{1,2,\ldots,n\\}$ in this work) onto itself. The _symmetric group_
$S_{n}$ is the set of all permutations of $[n]$ together with the usual
function composition applied from right to left. We write permutations using
lower case Greek letters, viewing them as sequences $\pi=\langle\pi_{1}\
\pi_{2}\ \cdots\ \pi_{n}\rangle$, where $\pi_{i}=\pi(i)$, and occasionally
rely on the two-line notation to denote them. The permutation $\iota=\langle
1\ 2\ \cdots\ n\rangle$ is the _identity permutation_.

Permutations are well-known to decompose in a single way into _disjoint
cycles_ (up to the ordering of cycles and of elements within each cycle),
leading to another notation for $\pi$ based on its _disjoint cycle
decomposition_. For instance, when $\pi=\langle 7\ 1\ 4\ 5\ 3\ 2\ 6\rangle$,
the disjoint cycle notation is $\pi=(1,7,6,2)(3,4,5)$. The _conjugate_ of a
permutation $\pi$ by a permutation $\sigma$, both in $S_{n}$, is the
permutation $\pi^{\sigma}=\sigma\pi\sigma^{-1}$. All permutations in $S_{n}$
that can be obtained from one another using this operation form a _conjugacy
class_ (of $S_{n}$), and have the same cycle structure.

######  Definition 2.1.

[10] The _block-interchange_ $\beta(i,j,k,\ell)$ with $1\leq i<j\leq
k<\ell\leq n+1$ is the permutation that exchanges the closed intervals
determined respectively by $i$ and $j-1$ and by $k$ and $\ell-1$:

$\left\langle\begin{array}[]{l}1\ \cdots\ i-1\ \framebox{$i\ \cdots\ j-1$}\ j\
j+1\ \cdots\ k-1\ \framebox{$k\ \cdots\ \ell-1$}\ \ell\ \ell+1\ \cdots\ n\\\
\raisebox{-3.61371pt}{$1\ \cdots\ i-1\ \framebox{$k\ \cdots\ \ell-1$}\ j\ j+1\
\cdots\ k-1\ \framebox{$i\ \cdots\ j-1$}\ \ell\ \ell+1\ \cdots\ n$}\\\
\end{array}\right\rangle.$

Block-interchanges generalise several well-studied operations: when $j=k$, the
resulting operation exchanges two adjacent intervals, and is known as a
_(block-)transposition_ [2]; when $j=i+1$ and $\ell=k+1$, the resulting
operation swaps elements in respective positions $i$ and $k$, and is called an
_exchange_ (or _(algebraic) transposition_); finally, when $i=1$, the
resulting operation is called a _prefix block-interchange_ ; prefix block-
transpositions and prefix exchanges are defined analogously. We study the
following problem.

sorting by prefix block-interchanges (sbpbi) Input: a permutation $\pi$ in
$S_{n}$, a number $K\in\mathbb{N}$. Question: is there a sequence of at most
$K$ prefix block-interchanges that sorts $\pi$?

The length of a shortest sorting sequence of prefix block-interchanges for a
permutation $\pi$ is its _(prefix block-interchange) distance_ , which we
denote $pbid(\pi)$. Distances based on other operations are defined similarly.

##  3 A 2-approximation based on the breakpoint graph

We give in this section a 2-approximation algorithm for sbpbi based on the
_breakpoint graph_. We first use this structure in subsection 3.1 to derive an
upper bound on $pbid$ and present our algorithm, then derive a lower bound in
subsection 3.2 which allows us to prove its performance guarantee. The
breakpoint graph is well-known to be equivalent [18] to another structure
known as the _cycle graph_ [2], which allows us to use results based on either
graph indifferently.

######  Definition 3.1.

[14] For any $\pi$ in $S_{n}$, let $\pi^{\prime}$ be the permutation of
$\\{0,1,2,\ldots,2n+1\\}$ defined by $\pi^{\prime}_{0}=0$,
$\pi^{\prime}_{2n+1}=2n+1$, and
$(\pi^{\prime}_{2i-1},\pi^{\prime}_{2i})=(2\pi_{i}-1,2\pi_{i})$ for $1\leq
i\leq n$. The _breakpoint graph_ of $\pi$ is the undirected edge-bicoloured
graph $G(\pi)=(V,E_{b}\cup E_{g})$ whose vertex set is formed by the elements
of $\pi^{\prime}$ ordered by position and whose edge set consists of:

  * •

$E_{b}=\\{\\{\pi^{\prime}_{2i},\pi^{\prime}_{2i+1}\\}\ |\ \forall\ 0\leq i\leq
n\\}$, called the set of _black_ edges;

  * •

$E_{g}=\\{\\{{2i},{2i+1}\\}\ |\ \forall\ 0\leq i\leq n\\}$, called the set of
_grey_ edges.

Figure 1 shows an example of a breakpoint graph. Since $G(\pi)$ is
$2$-regular, it decomposes in a single way into edge-disjoint cycles which
alternate black and grey edges. The _length_ of a cycle in $G(\pi)$ is the
number of black edges it contains, and a _$k$ -cycle_ in $G(\pi)$ is a cycle
of length $k$. We let $c(G(\pi))$ (resp. $c_{k}(G(\pi))$) denote the number of
cycles (resp. $k$-cycles) in $G(\pi)$, and refer to cycles of length one as
_trivial cycles_.

$0$$13$$14$$1$$2$$7$$8$$9$$10$$5$$6$$3$$4$$11$$12$$15$ Figure 1: The
breakpoint graph of $\langle$7 1 4 5 3 2 6$\rangle$.

A crucial insight of strategies based on the breakpoint graph is the
observation that the transformations that we apply never affect grey edges,
whereas they “cut” black edges and replace them with new black edges. This
point of view conveniently allows us to define block-interchanges in terms of
the black edges on which they _act_ : using the notation
$b_{i}=\\{\pi_{2i-2},\pi_{2i-1}\\}$ for a black edge, a quadruplet
$(b_{i},b_{j},b_{k},b_{\ell})$ of black edges with $i<j\leq k<\ell$ naturally
defines the block-interchange $\beta(i,j,k,\ell)$ and conversely.

###  3.1 An upper bound based on the breakpoint graph

The following quantity, defined for any $\pi$ in $S_{n}$, has been shown to be
a tight111Here and in the rest of the text, “tight” means that equality is
achieved by _some_ but _not all_ instances. lower bound on the prefix block-
transposition distance [19] :

$g(\pi)=\frac{n+1+c(G(\pi))}{2}-c_{1}(G(\pi))-\left\\{\begin{array}[]{ll}0&\mbox{if
}\pi_{1}=1,\\\ 1&\mbox{otherwise.}\end{array}\right.$ (1)

We prove in Theorem 3.5 that this quantity is also an _upper_ bound on the
prefix block-interchange distance. To that end, we use the following notation,
based on the one introduced in [2]; for any two permutations $\pi$ and
$\sigma$, define:

  * •

$\Delta c(\pi,\sigma)=c(G(\sigma))-c(G(\pi))$,

  * •

$\Delta c_{1}(\pi,\sigma)=c_{1}(G(\sigma))-c_{1}(G(\pi))$,

  * •

$\Delta f(\pi,\sigma)=f(\sigma)-f(\pi)$, where $f(\pi)=0$ if $\pi$ _fixes_ 1
(i.e. $\pi_{1}=1$) and $1$ otherwise, and

  * •

$\Delta g(\pi,\sigma)=g(\sigma)-g(\pi)$.

These parameters allow us to obtain the following expression, which will be
useful in our proofs:

$\Delta g(\pi,\sigma)=\Delta c(\pi,\sigma)/2-\Delta c_{1}(\pi,\sigma)-\Delta
f(\pi,\sigma).$ (2)

We start by proving in 3.3 the existence of a prefix block-interchange that
decreases $g(\pi)$ by at least one if $\pi_{1}\neq 1$. The proof uses the
following structural result, where grey edges
$\\{\pi^{\prime}_{a},\pi^{\prime}_{b}\\}$ and
$\\{\pi^{\prime}_{c},\pi^{\prime}_{d}\\}$ (with $a<b$ and $c<d$) are said to
_intersect_ if $a<c<b<d$ or $c<a<d<b$.

######  Lemma 3.2.

[14] For every permutation $\pi$, let $e$ be a grey edge in a nontrivial cycle
of $G(\pi)$; then there exists another grey edge $e^{\prime}$ in $G(\pi)$ that
intersects $e$.

We refer to the grey edge of $G(\pi)$ that contains $\pi^{\prime}_{1}$ as the
_first_ grey edge, and to the cycle that contains $0$ as the _leftmost cycle_.
Our figures represent alternating subpaths (i.e., paths that alternate black
and grey edges) as dotted edges; therefore, such a dotted edge might
correspond to a single grey edge, or to a black edge framed by two grey edges,
and so on.

######  Lemma 3.3.

For any $\pi$ in $S_{n}$: if $\pi_{1}\neq 1$, then there exists a prefix
block-interchange $\beta$ such that $\Delta c(\pi,\pi\beta)=2$, $\Delta
c_{1}(\pi,\pi\beta)\geq 2$, and $\Delta g(\pi,\pi\beta)\leq-1$.

######  Proof 3.4.

3.2 guarantees the existence of a grey edge $e^{\prime}$ that intersects the
first grey edge; moreover, the endpoints of $e^{\prime}$ ordered by position
connect elements whose values are either in decreasing (case 1 below) or
increasing (case 2 below) order. In both cases, if $e^{\prime}$ belongs to the
leftmost cycle, then there exists a prefix block-interchange that extracts two
$1$-cycles (we distinguish an additional third case where $e^{\prime}$ and the
first grey edge share the endpoints of a black edge):

  1. 1.

$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$

  2. 2.

$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$

  3. 3.

$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$

Otherwise, all edges that intersect the first grey edge belong to cycles other
than the leftmost cycle. One of those edges, which belongs to some cycle $C$,
must be in the same configuration as in case 1 above: indeed, if $C$ contains
a grey edge that takes us from the interval covered by the first grey edge
$(1,y)$ to a vertex located after $y$, then $C$ must also contain a grey edge
that takes us back before $y$. Without loss of generality, we thus assume that
$e^{\prime}$ is such an edge, and therefore a prefix block-interchange that
extracts two new $1$-cycles can also be applied:

  1. 4.

$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$

In all four cases, we have $\Delta c(\pi,\pi\beta)=2$ and $\Delta
c_{1}(\pi,\pi\beta)\geq 2$. The exact value of $\Delta g(\pi,\pi\beta)$ will
vary depending on the above configurations and is computed using Equation 2:

  1. 1.

the leftmost cycle in $G(\pi\beta)$ is nontrivial, so $\Delta
c_{1}(\pi,\pi\beta)=2$, $\Delta f(\pi,\pi\beta)=0$ and $\Delta
g(\pi,\pi\beta)=-1$;

  2. 2.

for exactly the same reasons as case 1, we obtain $\Delta g(\pi,\pi\beta)=-1$;

  3. 3.

we have two possible subcases:

    1. (a)

if the leftmost cycle in $G(\pi\beta)$ is nontrivial, then $\Delta
c(\pi,\pi\beta)=2$ and $\Delta f(\pi,\pi\beta)=0$, so $\Delta
g(\pi,\pi\beta)=-1$;

    2. (b)

otherwise, $\Delta c_{1}(\pi,\pi\beta)=3$ and $\Delta f(\pi,\pi\beta)=-1$,
which in turn implies $\Delta g(\pi,\pi\beta)=-1$.

  4. 4.

we have three possible subcases:

    1. (a)

$\Delta c_{1}(\pi,\pi\beta)=2$: the leftmost cycle in $G(\pi\beta)$ is
nontrivial, so $\Delta f(\pi,\pi\beta)=0$ and $\Delta g(\pi,\pi\beta)=-1$;

    2. (b)

$\Delta c_{1}(\pi,\pi\beta)=3$: the leftmost cycle in $G(\pi\beta)$ may or may
not be trivial, so $\Delta f(\pi,\pi\beta)\leq 0$ and $\Delta
g(\pi,\pi\beta)\leq-1$;

    3. (c)

$\Delta c_{1}(\pi,\pi\beta)=4$: the leftmost cycle in $G(\pi\beta)$ is
trivial, so $\Delta f(\pi,\pi\beta)=-1$ and $\Delta g(\pi,\pi\beta)=-2$.

We handle the case where $\pi_{1}=1$ in the proof of our upper bound below.

######  Theorem 3.5.

For any $\pi$ in $S_{n}$, we have $pbid(\pi)\leq g(\pi)$.

######  Proof 3.6.

If $\pi_{1}\neq 1$, then we apply 3.3 to decrease $g(\pi)$ by at least $1$.
Otherwise, $\\{\pi^{\prime}_{0},\pi^{\prime}_{1}\\}$ is a $1$-cycle in
$G(\pi)$ and $f(\pi)=0$. Assume $\pi\neq\iota$ to avoid triviality; then
$G(\pi)$ contains a nontrivial cycle, from which we select a grey edge
$\\{\pi^{\prime}_{2i-2},\pi^{\prime}_{2j-1}\\}$ with $j>i$. Applying the
prefix block-interchange $\beta(1,i,i,j)$ then makes $\pi_{i}$ and $\pi_{i}+1$
contiguous in $\pi\beta$, and that pair corresponds to a new $1$-cycle in
$G(\pi\beta)$. On the other hand, $\beta$ merges the $1$-cycle
$\\{\pi^{\prime}_{0},\pi^{\prime}_{1}\\}$ in $G(\pi)$ with the cycle that
contains $\\{\pi^{\prime}_{2i-2},\pi^{\prime}_{2j-1}\\}$, so $\Delta
c(\pi,\pi\beta)=0=\Delta c_{1}(\pi,\pi\beta)$, $\Delta f(\pi,\pi\beta)=1$ and
Equation 2 yields $\Delta g(\pi,\pi\beta)=0/2-0-1=-1$.

The smallest example of a permutation for which the inequality in Theorem 3.5
is strict is $\pi=\langle 3\ 2\ 1\rangle$, with $pbid(\pi)=1<g(\pi)=2$.
algorithm 1 implements the strategy described in Theorem 3.5. We prove in the
next subsection that algorithm 1 is a 2-approximation.

Input: A permutation $\pi$ of $[n]$.

Output: A sorting sequence of prefix block-interchanges for $\pi$.

1 $S\leftarrow$ empty sequence;

2 while  _$\pi\neq\iota$_ do

3 if  _$\pi_{1}\neq 1$_ then

4 $j\leftarrow$ the position of $\pi_{1}-1$;

5 if  _there exists a pair $(\pi_{i},\pi_{k}=\pi_{i}+1)$ such that $i\leq
j\leq k$ and the corresponding grey arc belongs to the leftmost cycle of
$G(\pi)$_ then

$\sigma\leftarrow\beta(1,i,j,k)$;

// 3.3 cases 1--3

6

7 else

8 $i,k\leftarrow$ positions such that $i\leq j\leq k$ and $\pi_{k}=\pi_{i}-1$;

$\sigma\leftarrow\beta(1,i,j,k)$;

// 3.3 case 4

9

10 else // Theorem 3.5

11 $i\leftarrow$ smallest index such that $\pi_{i+1}\neq\pi_{i}+1$;

12 $j\leftarrow$ the position of $\pi_{i}+1$;

13 $\sigma\leftarrow\beta(1,i,i,j)$;

14

15 $\pi\leftarrow\pi\sigma$;

16 $S$.append($\sigma$);

17

18return $S$;

Algorithm 1 ApproximateSbpbi($\pi$)

###  3.2 A lower bound based on the breakpoint graph

We now prove a lower bound on $pbid$ that allows us to show that algorithm 1
is a 2-approximation for sbpbi. To that end, we use a framework introduced in
[19]. The starting point is the following mapping, in which the symmetric
group on $[n+1]$ is identified with the symmetric group on $\\{0\\}\cup[n]$
and where $A_{n}$ is the subgroup of $S_{n}$ formed by the set of all _even_
permutations, i.e. permutations with an even number of even cycles:

$\psi:S_{n}\rightarrow
A_{n+1}:\pi\mapsto\overline{\pi}=(0,1,2,\ldots,n)(0,\pi_{n},\pi_{n-1},\ldots,\pi_{1}).$
(3)

This mapping associates to every permutation $\pi$ another permutation
$\overline{\pi}$ whose disjoint cycles are in one-to-one correspondence with
the cycles of $G(\pi)$. As a result, terminology based on the disjoint cycle
decomposition of $\overline{\pi}$ or on the alternating cycle decomposition of
$G(\pi)$ can conveniently be used indifferently, including the notation
introduced at the beginning of section 3 (e.g. $c(\overline{\pi})=c(G(\pi))$,
and therefore $\Delta
c(\overline{\pi},\overline{\pi\sigma})=c(\overline{\pi\sigma})-c(\overline{\pi})=c(G(\pi\sigma))-c(G(\pi))=\Delta
c(\pi,\pi\sigma)$). The following result will be our main tool for proving our
lower bound.

######  Theorem 3.7.

[19] Let $S$ be a subset of $S_{n}$ whose elements are mapped by $\psi(\cdot)$
onto $S^{\prime}\subseteq A_{n+1}$. Moreover, let $\mathscr{C}$ be the union
of the conjugacy classes (of $S_{n+1}$) that intersect with $S^{\prime}$; then
for any $\pi$ in $S_{n}$, any factorisation of $\pi$ into $t$ elements of $S$
yields a factorisation of $\overline{\pi}$ into $t$ elements of $\mathscr{C}$.

Consequently, if we let $d_{S}(\sigma)$ denote the length of a shortest
sorting sequence for $\sigma$ consisting solely of elements from $S$, then
Theorem 3.7 implies that for any $\pi$ in $S_{n}$ and any choice of
$S\subseteq S_{n}$, we have $d_{S}(\pi)\geq d_{S^{\prime}}(\overline{\pi})$.
In order to use Theorem 3.7, we need a translation of the effect of an
operation on $\pi$ in terms of a transformation on $\overline{\pi}$, as well
as a precise characterisation of the image of a prefix block-interchange under
the mapping $\psi$. Both are provided, respectively, by the following results.

######  Lemma 3.8.

[19] For all $\pi$, $\sigma$ in $S_{n}$, we have
$\overline{\pi\sigma}=\overline{\pi}(\overline{\sigma}^{\pi})$.

######  Lemma 3.9.

[19] For any block-interchange $\beta(i,j,k,\ell)$ in $S_{n}$, we have
$\overline{\beta(i,j,k,\ell)}=(j,\ell)(i,k)$.

As is well-known, a $2$-cycle in a permutation $\sigma$ containing elements
from different cycles in a permutation $\pi$ merges those cycles in
$\pi\sigma$, while a $2$-cycle in $\sigma$ containing elements from the same
cycle in $\pi$ splits that cycle into two cycles in $\pi\sigma$. 3.8 and 3.9
therefore provide us with a very simple way of analysing the effects of a
block-interchange: the effect of $\beta$ on the cycles of $G(\pi)$ is the same
as the effect of $\overline{\beta}^{\pi}$ on the cycles of $\overline{\pi}$,
and therefore bounds on the (prefix) block-interchange distance of $\pi$ can
be obtained by studying the effects of pairs of $2$-cycles on
$\overline{\pi}$. The following lemma will be useful in restricting the number
of cases in the proof of our lower bound (Theorem 3.14).

######  Lemma 3.10.

For any $\pi$ in $S_{n}$ and any block-interchange $\beta$, we have $\Delta
c(\pi,\pi\beta)\in\\{-2,0,2\\}$.

######  Proof 3.11.

By 3.9, $\overline{\beta}$ consists of two $2$-cycles, each of which might
split a cycle into two cycles or merge two cycles into one (3.8). Combining
all possible cases yields the set $\\{-2,0,2\\}$ as possible values for
$\Delta c(\overline{\pi},\overline{\pi\beta})=\Delta c(\pi,\pi\beta)$.

Finally, the following technical observation will be useful in ruling out
impossible values for $\Delta f(\pi,\sigma)$, whose set of possible values is
$\\{-1,0,1\\}$ when no restrictions apply.

######  Lemma 3.12.

For any $\pi$ in $S_{n}$ and every prefix block-interchange $\beta$: if
$\Delta c_{1}(\pi,\pi\beta)\geq 2$, then $\Delta f(\pi,\pi\beta)\neq 1$.

######  Proof 3.13.

If $\Delta c_{1}(\pi,\pi\beta)\geq 2$, then the new $1$-cycles are obtained in
one of the following ways:

  1. 1.

if at least one of them is the result of a split of the leftmost cycle of
$G(\pi)$, then that cycle is nontrivial and therefore $f(\pi)=1$, thereby
forbidding the value $\Delta f(\pi,\pi\beta)=1$;

  2. 2.

otherwise, all new $1$-cycles are extracted from a cycle in $G(\pi)$ other
than the leftmost cycle; since that cycle can only be split into at most two
new cycles (3.8 and 3.9), we have $\Delta c_{1}(\pi,\pi\beta)\leq 2$ in this
case. Moreover, we also have $\pi_{1}=1$, otherwise the $1$-cycle containing
$\pi_{1}$ would vanish in $G(\pi\beta)$ and contradict our assumption that
$\Delta c_{1}(\pi,\pi\beta)\geq 2$. Therefore, the value $\Delta
f(\pi,\pi\beta)=1$ is also excluded in this case.

We now have everything we need to prove our lower bound on $pbid$.

######  Theorem 3.14.

For any $\pi$ in $S_{n}$, we have $pbid(\pi)\geq g(\pi)/2$.

######  Proof 3.15.

By Theorem 3.7 and 3.9, we have $pbid(\pi)\geq d(\overline{\pi})$, where
$d(\overline{\pi})$ is the length of a shortest sorting sequence for
$\overline{\pi}$ where the only nontrivial cycles of each transformation in
the sequence are two $2$-cycles, exactly one of which contains $1$. As a
result, any lower bound on $d(\overline{\pi})$ is a lower bound on
$pbid(\pi)$, and therefore we only need to show that a transformation of the
kind we have just described can decrease the value of $g(\pi)$ by at most $2$.

Let $\overline{\beta}=(1,a)(b,c)$ be the image of a prefix block-interchange
under the mapping $\psi(\cdot)$. By 3.10, we only need to distinguish between
the following three cases; in each situation, we aim to minimise the value of
$\Delta g(\overline{\pi},\overline{\pi\beta})$.

  1. 1.

If $\Delta c(\overline{\pi},\overline{\pi\beta})=-2$, then clearly $\Delta
c_{1}(\overline{\pi},\overline{\pi\beta})\leq 0$, and Equation 2 allows us to
conclude that $\Delta g(\overline{\pi},\overline{\pi\beta})\geq-1-0-1=-2$.

  2. 2.

If $\Delta c(\overline{\pi},\overline{\pi\beta})=0$, then either $2$-cycle of
$\beta$ merges two cycles while the other splits a cycle into two. The lengths
of the involved cycles in $\overline{\pi}$ and in $\overline{\pi\beta}$ may
vary, but this observation is enough to deduce that $\Delta
c_{1}(\overline{\pi},\overline{\pi\beta})\leq 2$. The lowest value of $\Delta
g(\overline{\pi},\overline{\pi\beta})$ is obtained when $\Delta
c_{1}(\overline{\pi},\overline{\pi\beta})=2$, in which case Equation 2 and
3.12 yield $\Delta g(\overline{\pi},\overline{\pi\beta})\geq 0-2-0=-2$, or
when $\Delta c_{1}(\overline{\pi},\overline{\pi\beta})=1$, in which case
Equation 2 yields $\Delta g(\overline{\pi},\overline{\pi\beta})\geq 0-1-1=-2$.

  3. 3.

If $\Delta c(\overline{\pi},\overline{\pi\beta})=2$, then both elements of
$\beta$ each split one cycle into two cycles. As in the previous case, the
lengths of the involved cycles in $\overline{\pi}$ and in
$\overline{\pi\beta}$ may vary, but this observation is enough to deduce that
$\Delta c_{1}(\overline{\pi},\overline{\pi\beta})\leq 4$, and as a result
$\Delta f(\overline{\pi},\overline{\pi\beta})\in\\{-1,0\\}$ (3.12). The lowest
value of $\Delta g(\overline{\pi},\overline{\pi\beta})$ is obtained in two
cases:

    1. (a)

when $\Delta c_{1}(\overline{\pi},\overline{\pi\beta})=4$, in which case the
leftmost cycle of $\overline{\pi}$ splits into two $1$-cycles; therefore
$\Delta f(\overline{\pi},\overline{\pi\beta})=-1$ and Equation 2 yields
$\Delta g(\overline{\pi},\overline{\pi\beta})\geq 1-4+1=-2$;

    2. (b)

or when $\Delta c_{1}(\overline{\pi},\overline{\pi\beta})=3$, in which case
Equation 2 and 3.12 yield $\Delta g(\overline{\pi},\overline{\pi\beta})\geq
1-3+0=-2$.

Theorem 3.14 implies that algorithm 1 is a 2-approximation for sbpbi.

##  4 Tightening the bounds

Although obtaining better approximation guarantees for sbpbi seems as
nontrivial as for other prefix sorting problems, the bounds obtained in the
previous section can be improved. We show in this section how to tighten them,
and then use those improved results in section 5 to compute the maximal value
that the distance can reach.

###  4.1 A tighter upper bound

By Theorem 3.14, the largest value by which the upper bound of Theorem 3.5 can
decrease with a single prefix block-interchange is $2$. In this section, we
characterise all permutations which admit such a prefix block-interchange.
Other nontight permutations exist (see e.g. 4.5), but they do not admit such
an operation as the first step of an optimal sorting sequence. As a
consequence, we obtain an improved upper bound on $pbid$ in Theorem 4.7.

######  Lemma 4.1.

For any $\pi$ in $S_{n}$: if $G(\pi)$ contains a $2$-cycle that intersects the
first grey edge, then there exists a prefix block-interchange $\beta$ such
that $\Delta g(\pi,\pi\beta)=-2$.

######  Proof 4.2.

Follows from cases 4b and 4c of the proof of 3.3, when the cycle that contains
grey edge $f$ has length $2$.

Following [2], we say that a cycle $C$ with $b_{i}$ and $b_{k}$ as black edges
of minimum and maximum indices, respectively, _spans_ a black edge $b_{j}$ if
$i<j<k$.

######  Lemma 4.3.

For any $\pi$ in $S_{n}$: if $G(\pi)$ contains a $2$-cycle which is not the
leftmost cycle and which spans a black edge that belongs to a nontrivial cycle
different from the leftmost cycle, then there exists a prefix block-
interchange $\beta$ such that $\Delta g(\pi,\pi\beta)=-2$.

######  Proof 4.4.

We apply a prefix block-interchange defined by the first black edge, both
black edges of the $2$-cycle, and any black edge spanned by the $2$-cycle:

$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$

The number of cycles does not change, so $\Delta c(\pi,\pi\beta)=0$. Either
$\pi_{1}=1$, and then $\Delta c_{1}(\pi,\pi\beta)=1$ and $\Delta
f(\pi,\pi\beta)=1$; or $\pi_{1}\neq 1$, and then $\Delta
c_{1}(\pi,\pi\beta)=2$ and $\Delta f(\pi,\pi\beta)=0$. In both cases, Equation
2 yields $\Delta g(\pi,\pi\beta)=-2$.

$2$-cycles other than the leftmost cycle and in a different configuration from
our characterisations are still helpful. We show that even though they do not
allow a prefix block-interchange that decreases $g(\cdot)$ by $2$ right away,
they make it possible to obtain such an operation _eventually_.

######  Proposition 4.5.

For any $\pi$ in $S_{n}$: if $G(\pi)$ contains a $2$-cycle which is not the
leftmost cycle, then $\pi$ admits a sequence $S$ of prefix-block interchanges
that turns $\pi$ into a permutation $\sigma$ with $\Delta g(\pi,\sigma)=|S|$
and which admits a prefix block-interchange $\beta$ such that $\Delta
g(\sigma,\sigma\beta)=-2$.

######  Proof 4.6.

Let $C$ denote the $2$-cycle of interest. If $C$ intersects the first grey
edge or a cycle different from the leftmost cycle, then we are done (see
respectively 4.1 and 4.3). Otherwise, $C$ intersects another grey edge of the
leftmost cycle, and 3.3 allows us to reduce $g(\pi)$ by one while reducing the
length of the leftmost cycle without affecting $C$. Repeated applications of
3.3 eventually yield a permutation $\sigma$ which satisfies one of the
following conditions:

  1. 1.

$\sigma_{1}=1$, in which case $C$ necessarily spans a black edge that does not
belong to the leftmost cycle and therefore we can apply 4.3;

  2. 2.

$\sigma_{1}\neq 1$ and $C$ intersects another cycle than the leftmost cycle,
in which case we can again apply 4.3; or

  3. 3.

$\sigma_{1}\neq 1$ and $C$ intersects the first grey edge, in which case we
can apply 4.1.

The above results allow us to easily identify other nontight permutations
(with respect to Theorem 3.5) whose breakpoint graph contains no $2$-cycle.
For instance, if the first grey edge intersects a $3$-cycle $C$, then applying
a prefix-block interchange selected according to 4.1 decreases the lengths of
both the leftmost cycle and $C$, which becomes a $2$-cycle and which therefore
eventually allows for a prefix block-interchange that decreases $g(\cdot)$ by
$2$ according to 4.5.

The interactions between $2$-cycles prevent us from simply reducing the upper
bound of Theorem 3.5 by the number of $2$-cycles in $G(\pi)$: indeed, the
black edge spanned by the $2$-cycle described in 4.3 may belong to a $2$-cycle
whose length will increase in the resulting permutation. Therefore, we can
only conclude the following.

######  Theorem 4.7.

For any $\pi$ in $S_{n}$, we have $pbid(\pi)\leq g(\pi)-\lceil
c_{2}^{\emptyset}(G(\pi))/2\rceil$, where $c_{2}^{\emptyset}(G(\pi))$ denotes
the number of $2$-cycles in $G(\pi)$ excluding the leftmost cycle.

######  Proof 4.8.

We repeatedly apply 4.5 to take advantage of suitable $2$-cycles. Each prefix
block-interchange we use transforms a $2$-cycle into two $1$-cycles without
affecting the other $2$-cycles, except possibly in the case of 4.3 when the
edge spanned by the $2$-cycle we focus on belongs to another $2$-cycle. In the
worst case, every $2$-cycle we try to split forces us to increase the length
of a $2$-cycle it intersects, hence the improvement of only $\lceil
c_{2}^{\emptyset}(G(\pi))/2\rceil$ over Theorem 3.5.

Theorem 4.7 again yields a tight upper bound, as shown by the permutation
$\langle 1\ 4\ 3\ 2\rangle$ for which the value of the improved upper bound
matches its distance.

###  4.2 A tighter lower bound

A trivial lower bound on $pbid$ is given by the value of the block-interchange
distance (denoted by $bid(\pi)$), which can be computed in $O(n)$ time thanks
to the following result.

######  Theorem 4.9.

[10] For any $\pi$ in $S_{n}$, we have $bid(\pi)=(n+1-c(G(\pi)))/2$.

This lower bound often outperforms that of Theorem 3.14, but cases exist where
the opposite holds ($\langle 1\ 4\ 3\ 2\rangle$ is the smallest example). As
we show below, it is possible to build on this trivial lower bound to obtain a
much better and useful lower bound. The resulting lower bound also allows us
to compute the maximum value that the prefix block-interchange can reach, a
problem we address in section 5.

######  Definition 4.10.

[14] Let $\pi$ be a permutation. Two cycles $C$ and $D$ of $G(\pi)$
_intersect_ if $C$ contains a grey edge $e$ that intersects with a grey edge
$f$ of $D$. A _component_ of $G(\pi)$ is a connected component of the
intersection graph of the nontrivial cycles of $G(\pi)$.

For instance, the breakpoint graph of Figure 1 page 1 has two components: the
leftmost cycle, and the pair of intersecting $2$-cycles. Let $CC(G(\pi))$
denote the number of components of $G(\pi)$. We first show that prefix block-
interchanges that merge components of the breakpoint graph cannot decrease the
number of cycles it contains222See Appendix A for the proof..

######  Lemma 4.11.

For any $\pi$ in $S_{n}$, let $\beta$ be a prefix block-interchange with
$CC(G(\pi\beta))<CC(G(\pi))$; then $\Delta c(G(\pi,\pi\beta))\in\\{-2,0\\}$.

######  Theorem 4.12.

For any $\pi$ in $S_{n}$, we have $pbid(\pi)\geq
bid(\pi)+CC(G(\pi))-\left\\{\begin{array}[]{ll}0&\mbox{if }\pi_{1}=1,\\\
1&\mbox{otherwise}.\end{array}\right.$

######  Proof 4.13.

The expression for the lower bound corresponds to the following strategy: for
each component $C$ of $G(\pi)$, sort the corresponding subpermutation if $C$
contains $0$, or use a prefix block-interchange to make it contain $0$ and
then sort it. Trivially, the number of steps in the sorting stage cannot be
lower than the number or unrestricted block-interchanges it would require. Any
other strategy would have to merge components; however, by 4.11, a prefix
block-interchange $\beta$ that merges connected components cannot increase the
number of cycles, and therefore $bid(\pi\beta)\geq bid(\pi)$ for any
permutation $\pi$ and any such prefix block-interchange.

##  5 The maximum value of the prefix block-interchange distance

The _diameter_ of $S_{n}$ is the maximum value that a distance can reach for a
particular family of operations. In this section, we use our results to
compute its exact value in the case of prefix block-interchanges, and show
along the way that our 2-approximation algorithm based on the breakpoint graph
is also a 2-approximation with respect to the following notion.

######  Definition 5.1.

[11] Let $\pi$ be a permutation of $\\{0,1,2,\ldots,n+1\\}$ with $\pi_{0}=0$
and $\pi_{n+1}=n+1$. The pair $(\pi_{i},\pi_{i+1})$ with $0\leq i\leq n$ is a
_breakpoint_ if $i=0$ or $\pi_{i+1}-\pi_{i}\neq 1$, and an _adjacency_
otherwise. The number of breakpoints in a permutation $\pi$ is denoted by
$b(\pi)$.

For readability, we slightly abuse notation by using $b(\pi)$ for $\pi$ in
$S_{n}$, with the understanding that it refers to $b(\langle 0\ \pi_{1}\
\pi_{2}\ \cdots\ \pi_{n}\ n+1\rangle)$. We let $\Delta
b(\pi,\sigma)=b(\sigma)-b(\pi)$, and say that a prefix block-interchange
$\beta$ with $\Delta b(\pi,\pi\beta)<0$ _removes_ breakpoints, or _creates_
adjacencies.

######  Lemma 5.2.

For any $\pi$ in $S_{n}$ and any prefix block-interchange $\beta$, we have
$|\Delta b(\pi,\pi\beta)|\leq 3$.

######  Proof 5.3.

A prefix block-interchange $\beta$ acts on at most four pairs of adjacent
elements, including the pair $(0,\pi_{1})$ which always counts as a
breakpoint. Therefore, the number of breakpoints that $\beta$ can remove or
create lies in the set $\\{0,1,2,3\\}$.

Since $\iota$ is the only permutation with exactly one breakpoint, 5.2
immediately implies the following corollary.

######  Corollary 5.4.

For any $\pi$ in
$S_{n}:pbid(\pi)\geq\left\lceil\frac{b(\pi)-1}{3}\right\rceil.$

######  Lemma 5.5.

For any $\pi$ in $S_{n}$, we have $pbid(\pi)\leq
2\left\lceil\frac{b(\pi)-1}{3}\right\rceil$.

######  Proof 5.6.

Assume $\pi\neq\iota$ to avoid triviality, and observe that adjacencies in
$\langle 0\ \pi_{1}\ \pi_{2}\ \cdots\ \pi_{n}\ n+1\rangle$ are in one-to-one
correspondence with trivial cycles in $G(\pi)$ (except for the pair
$(0,\pi_{1})$ which by 5.1 is always a breakpoint). If $\pi_{1}\neq 1$, then
3.3 guarantees the existence of a prefix block-interchange $\beta$ with
$\Delta c_{1}(\pi,\pi\beta)\geq 2$ and in turn implies $\Delta
b(\pi,\pi\beta)\geq 2$. If $\pi_{1}=1$, then we select $\beta$ as in the proof
of Theorem 3.5, which creates a new trivial cycle in $G(\pi\beta)$ that
corresponds to a new adjacency in $\pi\beta$. Since $\pi\beta_{1}\neq 1$, the
previous case provides the next operation, and the number of breakpoints
decreases by at least three using two prefix block-interchanges.

Since $b(\pi)\leq n+1$ for all $\pi$ in $S_{n}$, we immediately obtain the
following.

######  Corollary 5.7.

For any $\pi\in S_{n}$, we have $pbid(\pi)\leq 2n/3$.

######  Theorem 5.8.

The diameter of $S_{n}$ under prefix block-interchanges is $\lfloor
2n/3\rfloor$.

######  Proof 5.9.

The cases where $n\leq 2$ are easily verified. We build tight families of
permutations for any $n\geq 3$, starting with permutations $\pi=\langle 1\ 3\
2\rangle$, $\sigma=\langle 1\ 4\ 3\ 2\rangle$, and $\tau=\langle 1\ 3\ 2\ 5\
4\rangle$ as base cases for the values of $n$, $n-1$ and $n-2$ that are
multiples of $3$, respectively. Theorem 4.12 yields $pbid(\pi)\geq 2$,
$pbid(\sigma)\geq 2$ and $pbid(\tau)\geq 3$, while 5.7 yields $pbid(\pi)\leq
2$, $pbid(\sigma)<3$ and $pbid(\tau)<4$, thereby matching the lower bounds.

To obtain tight permutations for larger values of $n$, we concatenate the
sequence $\langle n+1\ n+3\ n+2\rangle$ to $\pi$, $\sigma$ or $\tau$, and
repeat the process as many times as needed. Each concatenation preserves the
congruence of $n$ and adds a new component to $G(\cdot)$ which consists of an
isolated $3$-cycle. The lower bound of Theorem 4.12 thereby increases by $2$
with each concatenation, as does the upper bound of 5.7. As a result, a
permutation with prefix block-interchange distance $\lfloor 2n/3\rfloor$
exists for every value of $n$ in $\mathbb{N}$.

While many permutations reach the diameter when $n\not\equiv 0\pmod{3}$, the
permutation $\langle 1\ 3\ 2\ 4\ 6\ 5\ \cdots\ n-2\ n\ n-1\rangle$ seems to be
the only tight permutation when $n\equiv 0\pmod{3}$.

##  6 Conclusions and future work

We initiated in this work the study of sorting permutations by prefix block-
interchanges, an operation that generalises several well-studied operations in
genome rearrangements and interconnection network design. We gave tight upper
and lower bounds on the corresponding distance, and derived a 2-approximation
algorithm for the problem. We then showed how to obtain better bounds on the
distance using a finer analysis of cycles and components of the breakpoint
graph, and determined the maximum value that the distance can reach.

Several questions remain open, most notably the complexity of sbpbi, and its
approximability if it turns out to be -complete. We note that improving the
ratio of 2 will require improved lower bounds, since for all three upper
bounds we have obtained (Theorem 3.5, Theorem 4.7 and 5.5) there are
permutations whose actual distance match those bounds. A number of leads seem
promising in that regard, the most obvious one being the computation of the
exact value of the “special purpose distance” introduced in the proof of
Theorem 3.14, as well as a more intricate analysis of the cycles of the
breakpoint graph as well as their interactions as initiated in section 4.
Given how helpful $2$-cycles are in decreasing the upper bound of Theorem 3.5,
it would seem natural to focus on _simple permutations_ (i.e. permutations
whose breakpoint graph contains no cycle of length $>2$). This strategy
eventually led to a polynomial-time algorithm for sorting by signed reversals
[14], but we do not expect such an outcome for prefix block-interchanges since
the simplification process does not preserve the prefix block-interchange
distance (whereas it did preserve the signed reversal distance): the smallest
counterexample is $\pi=\langle 3\ 1\ 4\ 2\rangle$, which simplifies to
$\sigma=\langle 5\ 2\ 7\ 4\ 1\ 6\ 3\rangle$, and for which $pbid(\pi)=2\neq
pbid(\sigma)=3$.

In a broader context, we also hope that our results and the strategies we
designed to tackle sbpbi can be applied to other prefix sorting problems (for
instance, a generalisation of the lower bounding strategy of Theorem 4.12 to
any distance would be of interest). The breakpoint graph approach provides a
clear strategy for unrestricted sorting problems, which, informally, usually
consists in increasing the number of cycles in as few steps as possible. As
our bounds show, and as has been observed for most prefix sorting problems [1,
19, 20], this no longer works under the prefix constraint since operations
that _decrease_ or do not affect the number of cycles can also decrease the
value of our bounds. Nevertheless, bounds obtained for prefix exchanges,
prefix block-transpositions, prefix block-interchanges and prefix signed
reversals are all based on $g(\cdot)$, which seems to indicate common
underlying features that could be taken advantage of, and possibly lead to a
common framework for approximating these problems or solving them exactly.

## References

  * [1] Sheldon B. Akers, Balakrishnan Krishnamurthy, and Dov Harel.  The star graph: An attractive alternative to the $n$-cube.  In Proceedings of the Fourth International Conference on Parallel Processing, pages 393–400. Pennsylvania State University Press, August 1987.  doi:10.5555/201173.201191.
  * [2] Vineet Bafna and Pavel A. Pevzner.  Sorting by transpositions.  SIAM Journal on Discrete Mathematics, 11(2):224–240 (electronic), May 1998.  doi:10.1137/S089548019528280X.
  * [3] Piotr Berman, Sridhar Hannenhalli, and Marek Karpinski.  1.375-approximation algorithm for sorting by reversals.  In Rolf H. Möhring and Rajeev Raman, editors, Proceedings of the 10th Annual European Symposium on Algorithms, volume 2461 of Lecture Notes in Computer Science, pages 200–210, Rome, Italy, September 2002\. Springer.  doi:10.1007/3-540-45749-6_21.
  * [4] Laurent Bulteau, Guillaume Fertin, and Irena Rusu.  Sorting by transpositions is difficult.  SIAM Journal on Discrete Mathematics, 26(3):1148–1180, 2012.  doi:10.1137/110851390.
  * [5] Laurent Bulteau, Guillaume Fertin, and Irena Rusu.  Pancake flipping is hard.  Journal of Computer and System Sciences, 81(8):1556–1574, 2015\.  doi:10.1016/j.jcss.2015.02.003.
  * [6] Liming Cai, Jianer Chen, Rodney G. Downey, and Michael R. Fellows.  On the parameterized complexity of short computation and factorization.  Archive for Mathematical Logic, 36(4-5):321–337, 1997.  doi:10.1007/s001530050069.
  * [7] Alberto Caprara.  Sorting permutations by reversals and Eulerian cycle decompositions.  SIAM Journal on Discrete Mathematics, 12(1):91–110 (electronic), January 1999.  doi:10.1137/S089548019731994X.
  * [8] Xin Chen.  On sorting unsigned permutations by double-cut-and-joins.  Journal of Combinatorial Optimization, 25(3):339–351, 2013.  doi:10.1007/s10878-010-9369-8.
  * [9] Shih-Wen Chou, Chung-Han Yang, Kun-Tze Chen, and Chin Lung Lu.  Prefix block-interchanges on binary strings.  In William Cheng-Chung Chu, Han-Chieh Chao, and Stephen Jenn-Hwa Yang, editors, Proceedings of the International Computer Symposium on Intelligent Systems and Applications, volume 274 of Frontiers in Artificial Intelligence and Applications, pages 1960–1969, Taichung, Taiwan, December 2014. IOS Press.  doi:10.3233/978-1-61499-484-8-1960.
  * [10] David A. Christie.  Sorting permutations by block-interchanges.  Information Processing Letters, 60(4):165–169, 1996.  doi:10.1016/S0020-0190(96)00155-X.
  * [11] Zanoni Dias and João Meidanis.  Sorting by prefix transpositions.  In Alberto H. F. Laender and Arlindo L. Oliveira, editors, Proceedings of the Ninth International Symposium on String Processing and Information Retrieval, volume 2476 of Lecture Notes in Computer Science, pages 65–76, Lisbon, Portugal, September 2002. Springer-Verlag.  doi:10.1007/3-540-45735-6_7.
  * [12] Isaac Elias and Tzvika Hartman.  A 1.375-approximation algorithm for sorting by transpositions.  IEEE/ACM Transactions on Computational Biology and Bioinformatics, 3(4):369–379, 2006.  doi:10.1109/TCBB.2006.44.
  * [13] Guillaume Fertin, Anthony Labarre, Irena Rusu, Eric Tannier, and Stéphane Vialette.  Combinatorics of Genome Rearrangements.  Computational Molecular Biology. The MIT Press, 2009.  URL: https://mitpress.mit.edu/books/combinatorics-genome-rearrangements.
  * [14] Sridhar Hannenhalli and Pavel A. Pevzner.  Transforming cabbage into turnip: Polynomial algorithm for sorting signed permutations by reversals.  Journal of the ACM, 46(1):1–27, 1999.  doi:10.1145/300515.300516.
  * [15] Mark R. Jerrum.  The complexity of finding minimum-length generator sequences.  Theoretical Computer Science, 36(2-3):265–289, June 1985.  doi:10.1016/0304-3975(85)90047-7.
  * [16] D. J. Kleitman, Edvard Kramer, J. H. Conway, Stroughton Bell, and Harry Dweighter.  Elementary problems: E2564-E2569.  The American Mathematical Monthly, 82(10):1009–1010, 1975.  doi:10.2307/2318260.
  * [17] Donald E. Knuth.  Sorting and Searching, volume 3 of The art of Computer Programming.  Addison-Wesley, 1995.
  * [18] Anthony Labarre.  New bounds and tractable instances for the transposition distance.  IEEE/ACM Transactions on Computational Biology and Bioinformatics, 3(4):380–394, October 2006.  doi:10.1109/TCBB.2006.56.
  * [19] Anthony Labarre.  Lower bounding edit distances between permutations.  SIAM Journal on Discrete Mathematics, 27(3):1410–1428, 2013.  doi:10.1137/13090897X.
  * [20] Anthony Labarre and Josef Cibulka.  Polynomial-time sortable stacks of burnt pancakes.  Theoretical Computer Science, 412(8-10):695–702, March 2011.  doi:10.1016/j.tcs.2010.11.004.
  * [21] S. Lakshmivarahan, Jung-Sing Jwo, and S. K. Dhall.  Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey.  Parallel Computing, 19(4):361–407, April 1993.  doi:10.1016/0167-8191(93)90054-O.
  * [22] Sophia Yancopoulos, Oliver Attie, and Richard Friedberg.  Efficient sorting of genomic permutations by translocation, inversion and block interchange.  Bioinformatics, 21(16):3340–3346, 2005.  doi:10.1093/bioinformatics/bti535.

##  Appendix A Proof of 4.11

A prefix block-interchange $\beta$ acts on one, two, three or four cycles. We
first show that if $\beta$ reduces the number of connected components of
$G(\pi)$, then it cannot act on a single cycle of $G(\pi)$. This is important
for the proof of 4.11, because some prefix block-interchanges acting on a
single cycle increase the number of cycles and therefore may decrease the
value of $bid(\pi)$ regardless of their effect on $pbid(\pi)$ or $g(\pi)$. The
following concepts will be helpful.

######  Definition A.1.

For any permutation $\pi$, let $e=(e_{1},e_{2})$ and $f=(f_{1},f_{2})$ be two
grey edges in $G(\pi)$, with $e_{1}<e_{2}$ and $f_{1}<f_{2}$. We say that $e$
and $f$ are _independent_ if they are:

  * •

_nested_ , i.e. $e_{1}<f_{1}<f_{2}<e_{2}$ (written $f\subset_{\pi}e$) or
$f_{1}<e_{1}<e_{2}<f_{2}$ (written $e\subset_{\pi}f$); or

  * •

_ordered_ , i.e. $e_{1}<e_{2}<f_{1}<f_{2}$, in which case we say that $e$
_precedes_ $f$ (written $e<_{\pi}f$), or $f_{1}<f_{2}<e_{1}<e_{2}$ (i.e. $f$
precedes $e$).

Grey edges naturally define intervals in $\pi^{\prime}$, so we use the same
notation to compare intervals, or grey edges with intervals. We will sometimes
need to distinguish _proper_ block-interchanges, i.e. of the form
$\beta(i,j,k,\ell)$ with $j<k$, from prefix block-transpositions, which are of
the form $\beta(i,j,j,\ell)$.

######  Lemma A.2.

For any $\pi$ in $S_{n}$, let $\beta$ be a prefix block-interchange with
$CC(G(\pi\beta))<CC(G(\pi))$; then $\beta$ cannot act on a single cycle of
$G(\pi)$.

######  Proof A.3.

Let $e=(e_{1},e_{2})$ and $f=(f_{1},f_{2})$ with $e_{1}<e_{2}$ and
$f_{1}<f_{2}$ be two grey edges of $G(\pi)$. We show that if $e$ and $f$ are
independent in $G(\pi)$, then they remain independent in $G(\pi\beta)$. For
readability, we assume that the indices of $e$ and $f$ correspond to positions
in $\pi$ rather than $\pi^{\prime}$. The connections between the black edges
of $G(\pi)$ on which $\beta(1,i,j,k)$ acts imply the following:

  * •

both $e_{1}$ and $f_{1}$ lie in the interval $[1,k]$, otherwise $\beta$ would
not affect $e$ or $f$;

  * •

at least $e$ or $f$ has both endpoints in $[1,i]$, $[i,j]$ (which is empty if
$\beta$ is not proper) or $[j,k]$, otherwise they both intersect the cycle on
which $\beta$ acts and therefore $CC(G(\pi\beta))\geq CC(G(\pi))$;

  * •

if $x\subset_{\pi}I$ holds for all possible combinations of $x$ in $\\{e,f\\}$
and $I$ in $\\{[1,i],[i,j],[j,k]\\}$, then $\beta$ trivially preserves the
order of endpoints and therefore the interactions between $e$ and $f$ as well,
so that their independence in $G(\pi)$ is preserved in $G(\pi\beta)$.

Without loss of generality, the only cases left to examine are those where
$e\subset_{\pi}f$ and $e\subset_{\pi}[1,i]$, $e\subset_{\pi}[i,j]$, or
$e\subset_{\pi}[j,k]$. The only two ways of making $e$ and $f$ intersect in
$G(\pi\beta)$ are therefore either to exchange $e_{2}$ and $f_{2}$ without
moving $e_{1}$ and $f_{1}$, which is impossible because $\beta$ is a _prefix_
block-interchange; or to exchange $f_{1}$ and $e_{1}$ without moving $e_{2}$
and $f_{2}$, which is impossible as well since $\beta$ must act on the four
black edges of the cycle.

We can now prove 4.11.

######  Proof A.4 (Proof of 4.11).

By A.2, we have the following three cases to analyse:

  1. 1.

if $\beta$ acts on two cycles from different components, then two or three of
the black edges on which $\beta$ acts belong to the same cycle. In all
resulting cases, we have $\Delta c(\pi,\pi\beta)=0$; omitted cases are
symmetric, and only proper block-interchanges are considered since the
property we seek to prove is already known to hold for block-transpositions
(see [2, Lemma 3.2 page 228]):

    1. (a)

$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$

    2. (b)

$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$

    3. (c)

$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$

    4. (d)

$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$

    5. (e)

$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$

    6. (f)

$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$

  2. 2.

if $\beta$ acts on three cycles, then exactly two of the black edges on which
$\beta$ acts belong to the same cycle. In all cases, we have $\Delta
c(\pi,\pi\beta)\in\\{-2,0\\}$; again, omitted cases are symmetric, and only
proper block-interchanges are considered since block-transpositions acting on
three cycles decrease the number of cycles by two [2, Lemma 2.1 page 227]:

    1. (a)

$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$

    2. (b)

$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$

    3. (c)

$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$

    4. (d)

$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$

    5. (e)

$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$

  3. 3.

if $\beta$ acts on four cycles, then all black edges on which $\beta$ acts
belong to their own distinct cycle and $\Delta c(\pi,\pi\beta)=-2$:

$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$$0$$\pi^{\prime}_{1}$$\pi^{\prime}_{2i-2}$$\pi^{\prime}_{2i-1}$$\pi^{\prime}_{2j-2}$$\pi^{\prime}_{2j-1}$$\pi^{\prime}_{2k-2}$$\pi^{\prime}_{2k-1}$


#  Confidence-Nets: A Step Towards better Prediction Intervals for regression
Neural Networks on small datasets

Mohamedelmujtaba Altayeb
Key Laboratory of C & PC Structures Ministry of Education
Southeast University, Nanjing, 210096, China
<EMAIL_ADDRESS>
& Abdelrahman M. Elamin
Structural and Geotechnical Engineering Department
University of Naples Federico II, Napoli, Italy
<EMAIL_ADDRESS>
& Hozaifa Ahmed
Structural and Geotechnical Engineering Department
University of Naples Federico II, Napoli, Italy
<EMAIL_ADDRESS>
& Eithar Elfatih Elfadil Ibrahim
Department of Statistics & Computer Science
Faculty of Mathematical Sciences and Informatics
University of Khartoum, Khartoum, Sudan
<EMAIL_ADDRESS>
& Omer Haydar
Department of Electrical and Electronic Engineering
University of Khartoum, Khartoum, Sudan
<EMAIL_ADDRESS>
&Saba Abdulaziz
Department of Electrical and Electronic Engineering
University of Khartoum, Khartoum, Sudan
<EMAIL_ADDRESS>
&Najlaa H. M. Mohamed
Department of Electrical and Electronic Engineering
University of Khartoum, Khartoum, Sudan
<EMAIL_ADDRESS>
Corresponding Author

###### Abstract

The recent decade has seen an enormous rise in the popularity of deep learning
and neural networks. These algorithms have broken many previous records and
achieved remarkable results. Their outstanding performance has significantly
sped up the progress of AI, and so far various milestones have been achieved
earlier than expected. However, in the case of relatively small datasets, the
performance of Deep Neural Networks (DNN) may suffer from reduced accuracy
compared to other Machine Learning models. Furthermore, it is difficult to
construct prediction intervals or evaluate the uncertainty of predictions when
dealing with regression tasks. In this paper, we propose an ensemble method
that attempts to estimate the uncertainty of predictions, increase their
accuracy and provide an interval for the expected variation. Compared with
traditional DNNs that only provide a prediction, our proposed method can
output a prediction interval by combining DNNs, extreme gradient boosting
(XGBoost) and dissimilarity computation techniques. Albeit the simple design,
this approach significantly increases accuracy on small datasets and does not
introduce much complexity to the architecture of the neural network. The
proposed method is tested on various datasets, and a significant improvement
in the performance of the neural network model is seen. The model’s prediction
interval can include the ground truth value at an average rate of 71% and 78%
across training sizes of 90% and 55%, respectively. Finally, we highlight
other aspects and applications of the approach in experimental error
estimation, and the application of transfer learning.

_Keywords_ Neural Networks $\cdot$ Ensemble Learning $\cdot$ Regression
Prediction Intervals

##  1 1\. Introduction

Deep neural networks are the algorithms at the core of the deep learning
field. These algorithms have allowed us to make significant advances in the
field of AI, from achieving super-human level performance on atari games and
beating humans at the game of GO (Mnih et al. (2015); Géron (2017)) to
autonomous driving (Wang et al. (2020)) and protein folding (Jumper et al.
(2021)). While many other machine learning algorithms focus on learning only
one or two layers of representation, deep neural networks can automatically
learn tens or hundreds of successive layers of representations from exposure
to training data (Chollet (2018)). These representations are primarily learned
through the hidden layers of neural networks, which are usually stacked on top
of each other in the sense that each layer’s output is the input of the next
layer. Adding more layers stacked on top of each other allows the neural
network to learn more representations, providing more accurate predictions.
A large number of scientists are devoted to the study of interpreting models
that are considered black-box models (Fan et al. (2021)). A small portion of
this research focuses on uncertainty quantification (UQ) and Prediction
Intervals (PI) construction. This is an incredibly challenging task, as
reviewed in studies such as (Tsuji and Suzuki (2021)), who discussed the
difficulty of error estimation of deep learning models. (Minakowski and
Richter (2023)) developed a posteriori error estimator for neural network
approximations of partial differential equations. (Lai et al. (2022)) Explored
the uncertainty in regression neural networks and then proposed a prediction
interval construction method from the statistics perspective. A large-scale
evaluation of empirical frequentist coverage properties was also provided by
(Kompa et al. (2021)). Their evaluation focused on well-known uncertainty
quantification techniques on a suite of regression and classification tasks.
Furthermore, (Hirschfeld et al. (2020)) examined several methods on five
regression datasets and concluded that existing UQ methods are inadequate for
all common-use cases and further research is needed. A recently published
study by (Abdar et al. (2021)) reviewed the recent advances in uncertainty
quantification methods used in deep learning, highlighting the fundamental
research challenges and directions associated with UQ. Most of these studies
eventually demonstrate the difficulty of uncertainty quantification and
building prediction intervals in regression neural networks. Despite the
various attempts at uncertainty quantification, the current methods are
challenging to implement. Each method introduces more steps to the already
complicated nature of how neural networks arrive at a prediction.
Moreover, introducing more complexity into the deep neural network can affect
its structure and thus hinder the application of transfer learning, an
essential feature of neural networks. In cases such as in extensive
experimentation, transfer learning plays an essential role as it can be
applied to scenarios of experimental conditions change, such as changes in
Spatio-temporal variables, changes in material characteristics, or the
presence of a consistent source of error unknown to the practitioner (un-
noticeable minor machine faults). This further applies to fields such as the
study of construction materials, where small datasets belonging to the
cementitious composite family are usually available and share many
similarities. Even in the case of the development of systems that can fully
explain the inner workings of neural network prediction, there will remain the
question of how this understanding can help improve accuracy.
In the meantime, we believe it’s convenient to sacrifice the complete
understanding of deep neural networks and settle for the estimation of error
as an approach to uncertainty quantification and constructing prediction
intervals. The ability to estimate the prediction errors can allow us to
improve accuracy by directly correcting errors, as well as maintain some of
the neural network’s core features, such as transfer learning. In this paper,
we aim to develop a simple ensemble method that indirectly combines an
artificial neural network with an extreme gradient boosted trees (XGBoost)
algorithm and dissimilarity equations for improving the predictions of a
neural network. Previous research has shown that ensemble techniques that
combine neural networks and tree-based methods are highly effective with small
datasets (Altayeb et al. (2021)). The proposed method allows the improvement
of prediction accuracy without disturbing the main dynamics of the neural
network, therefore allowing the efficient scaling and application of transfer
learning. Hereafter, we will refer to our method as “confidence-nets”.
In section 2 of the paper, we present the datasets, algorithms, and the
combination method, followed by the training process for the ensemble
approach. The paper focuses mainly on presenting the application of error
correction to improve accuracy, estimation, and the method’s robustness.
Section 3 introduces error correction results and shows how the ensemble
method is much more effective than a similar neural network model for small
datasets.

##  2 Methods

###  2.1 Data collection

The datasets used in this work and their corresponding details are specified
in the table (1). Big data and massive datasets are rare in some fields, such
as the study of construction and building materials, mainly concrete. This may
be due to the considerable cost of experiments to collect such datasets. For
these reasons, we thought that construction and building materials datasets
represent a good test bed for our proposed concept. We will mainly consider
small datasets found online for the approach proposed in this paper. All
datasets are normalized using min-max normalization, then split at different
train: test ratios to evaluate the model’s performance compared with the base
neural network model.

Table 1: Datasets used in this study. # |  Dataset name |  Publishing date |  # Features (columns) |  # Instances (rows)
---|---|---|---|---
1 |  Concrete Slump Test (Yeh (2007)) |  2009-04-30 |  10 |  103
2 |  Concrete Compressive Strength (Yeh (2007)) |  2007-08-03 |  9 |  1030
3 |  Dataset of 622 Rectangular Concrete-filled steel tube columns (Nguyen Thi Mai (2021)) |  2021-06-08 |  7 |  623
4 |  Strain Hardening Cementitious Composites Data for FDNN ensemble predictive model (Altayeb, Mohamedelmujtaba; Wang, Xin; Musa (2021)) |  2021-03-03 |  29 |  241
5 |  Compressive strength dataset of foamednormal concrete for prediction model (NGUYEN, TUAN; NGO (2018)) |  2018-11-20 |  9 |  1133
6 |  Compressive strength of alkali-activated binder concrete cured at ambient temperature (Ramagiri, Kruthi Kiran; Boindala, Sriman Pankaj; Zaid (2021)) |  2021-03-03 |  11 |  372
7 |  A Dataset of Compressive Strength of FRCM-confined Concrete Columns (Irandegani, Mohammad Ali; Zhang, Daxu; Shadabfar (2021)) |  2021-08-17 |  5 |  76
8 |  Fake transfer length data generated using generative adversarial networks (Jeong, Hoseong ; Han, Sun-Jin; Choi, Seung-Ho; Kim, Jae Hyun ; Kim (2020)) |  2020-08-25 |  5 |  10002
9 |  Experimental dataset (Chen, Huaicheng; Qian, Chunxiang; Liang, Chengyao; Kang ) |  2018-01-18 |  10 |  639

###  2.2 Model development

The confidence nets model comprises three components, the primary prediction
model (a neural network model), an error estimation model (XGBoost model), and
a memory component. The memory component is responsible for storing some
information about training, which is used in later stages to estimate standard
errors and build the prediction interval. Both the neural network model and
error estimation model have the same inputs; however, the output of the neural
network is the prediction ($\hat{y}$) The target parameter and the output of
the error estimation model are an estimation of the expected variations
($\hat{y}_{e}$) between the prediction and the actual experimental result.
This means that the neural network model is responsible for predicting the
outputs. However, the error estimation model is responsible for predicting the
difference between the output and the actual experimentally obtained values.
The expected variation ($\hat{y}_{e}$) then becomes an indicator of how
confident the neural network thinks that it will get the prediction right,
hence the term c̈onfidenceïn the name of the model, while the n̈ets̈tands for
the base neural network. By sharing the same inputs as the neural network
model, the error estimation model must learn the relationship between a set of
inputs and the error produced, subsequently understanding the weakness of the
neural network model. The two models work synchronously to provide a
prediction in the form ($\hat{y}\pm\hat{y}_{e}$) therefore, the final
prediction and an indication of experimental success are given through an
informative prediction of the confidence nets model. Fig. 1 illustrates the
training and prediction process of the confidence nets model.

Figure 1: Illustration of the training procedure and prediction process of the
confidence nets model.

The main difference in the approach is in the training of the model. The
training of the model takes two stages. In the first training phase, the
neural network model (i.e., neural network) is usually fitted on the dataset.
The confidence nets model implemented in this study comprises three layers, a
convolution layer for extracting information and a hidden layer for improving
the modelling capabilities of the model. Here it is important to note that
this would be considered a complex model for a small task and would result in
overfitting. Still, as will be shown later, the confidence nets architecture
takes several measures to address this issue, for one the model uses an error
correction mechanism that corrects the model’s predictions when they are off
by a large margin, as will be explained in more detail in the following
sections.
If implemented correctly, a convolutional layer can significantly boost the
feature extraction capabilities of a deep neural network model. Instead of the
typical 2D convolution algorithm used for image-based tasks, we use a 1D
convolution operation. The convolutional layers receive the input ($X^{m}$) as
a tensor of channels ($K_{m}$) and compute a new output ($X^{m+1}$) composed
of ($O_{m}$) channels. The output of each channel is called a feature map and
can be computed as

$X^{(m)}_{o}=\sum_{k}^{n}W^{(m)}_{ok}*X^{(m-1)}_{k}+b^{(m)}_{o}$ (1)

Where (*) denotes the (1D) convolutional operation. The matrix
($W^{(m)}_{ok}$) parameterizes a spatial filter that the layer can use to
detect or enhance some features in the incoming input. The specific action of
this filter is automatically learnt from data during the model’s training.
For training the neural network model, the Adam optimizer is used. The Huber
loss is the neural network’s primary loss function. Although the most common
loss function used for most regression tasks (such as this task) is the mean
squared error, Huber loss provides more flexibility to outliers, as seen in
equation (2). This equation essentially says that for loss values less than
$\delta$, the mean squared error is used; for loss values greater than
$\delta$, the mean absolute error is used. This effectively combines the best
properties of the two loss functions. The equations of the three losses are
given below.

$L(y,\hat{y})_{huber}=\begin{cases}\frac{1}{2}(y-\hat{y})^{2}&for\left|y-\hat{y}\right|\leq\delta\\\
\delta\bullet(\left|y-\hat{y}\right|-\frac{1}{2}\delta)&for\left|y-\hat{y}\right|>\delta\\\
\end{cases}$ (2)

$L(y,\hat{y})_{mse}=\frac{1}{n}\sum_{i=1}^{n}(y-\hat{y})^{2}$ (3)

$L(y,\hat{y})_{mae}=\frac{1}{n}\sum_{i=1}^{n}\left|y-\hat{y}\right|$ (4)

A portion of the input training data is stored within the model’s memory
without including any information about the output targets. This memory is
used later to compute a similarity score between a new input and previously
trained inputs. Some wild errors may occur from overfitting the neural
network; thus, the confidence nets use an error correction mechanism. The
error correction mechanism is a dynamic value that is added to the prediction
(similar to the bias term) based on the estimated weakness of the neural
network model.
Although machine learning, in general, can model the relationships in data
with satisfying performance. In actual experiments, obtaining the same values
predicted by machine learning or a deep learning model can be complicated. The
success of experimental trials relies upon several factors that are difficult
to account for. However, our proposed method makes several precautions to
provide safer predictions. After the first phase, once a trained neural
network is obtained, it is used to create the error estimation dataset. The
error estimation dataset comprises the original inputs and the error between
the prediction and the obtained experimental result. This measured error is
then slightly scaled up/down by multiplying the prediction with the parameter
$\omega$. The factor ($\omega$) can be obtained by averaging a sample of the
predictions and experimental values to determine if the network tends to
mostly overestimate or underestimate its predictions. In case of
overestimation, it forces the correction of the predictions to be lower and
vice versa. This ensures a more inclusive error estimation property, a safer
error margin, and less dependence on the neural network if its predictions are
wildly off. After obtaining a dataset for the adjusted error measurements, and
inputs, the XGBoost model is then trained using the inputs and targets in
$X_{e}$.

$\omega_{opt}=1-\frac{\sum_{i=1}^{N}(\hat{y}-y)}{N}$ (5)

$E=\omega*\hat{y}-y$ (6)

$X_{e}=[X;E]$ (7)

Although multiplication with $\omega$ results in an artificially induced
measure of safety for the predictions, it is necessary to produce a reliable
performance, as will be seen later. The parameter $\omega$ is calculated
automatically by the confidence nets model during training using equation (5).
Then an error estimation dataset composed of the errors of predictions is
created ($X_{e}$) using the trained neural network models predictions. Next,
the neural network model is combined with the error estimation model to give
the final prediction ($\hat{y_{f}}$). The final prediction is provided by
subtracting the estimated error from the original prediction, as shown in
equation (12).

$h_{1}=ELU(\forall^{100}_{j=1}\sum_{i=1}^{n_{x}}X_{O_{i}}w_{1,i,j}+b_{1,j})$
(8)

$h_{2}=ELU(\forall^{100}_{j=1}\sum_{i=1}^{100}h_{1,i}w_{2,i,j}+b_{2,j})$ (9)

$\hat{y}=ELU(\forall^{100}_{j=1}\sum_{i=1}^{100}h_{2,i}w_{3,i,j}+b_{3,j})\\\ $
(10)

$\hat{y_{c}}=XGBoost(X_{e})=\sum_{i=1}^{500}f_{t}(X_{e_{i}})\\\ $ (11)

$\hat{y_{f}}=\hat{y}-\hat{y_{c}}\\\ $ (12)

The second major component that allows for dynamic estimations of error is the
dissimilarity factor ($d_{e}$). This factor is based on the Euclidean distance
equation and is a computation of the amount of difference between the inputs
of the current sample and the samples in the memory. Since a small amount of
data is usually used to train a confidence nets model, The model’s memory
component can store this training data. The dissimilarity factor establishes a
relationship between a new input and the trained data and computes a
normalized dissimilarity value, as shown in equation (13). This factor
provides an additional measure of safety in the estimation of error. If a
sample is closely related to samples in the memory, then this factor
approaches zero; when the sample is very strange to the confidence nets
memory, this factor increases, increasing the estimated error. Finally, the
average loss during training is stored in the model’s memory as a constant
$l_{n}$ and is used to adjust the bias in experimental error estimation.

$D=d(x_{p},x_{t})=\forall^{N}_{j=1}\sqrt{\sum_{i=1}^{n_{x}}(x_{p_{i}}-x_{t_{i}})}\\\
$ (13)

$d_{e}=min([D])\\\ $ (14)

$\hat{y_{e}}=\hat{y_{c}}+d_{e}-l_{n}\\\ $ (15)

$\hat{y_{e}}=\hat{y_{c}}+d_{e}-l_{n}\\\ $ (16)

$\hat{y}_{experimental}=\hat{y_{f}}\pm\hat{y_{e}}\\\ $ (17)

To evaluate the ability to capture the estimate of errors using the prediction
interval ($\hat{y}_{experimental}$), the results of the predictions of the
confidence nets model are compared to a base neural network model on the
datasets introduced previously in table 1. Throughout this study, the
hyperparameters used were kept constant for both models. For comparison, both
models were built using Pytorch (Paszke, Adam and Gross, Sam and Massa,
Francisco and Lerer, Adam and Bradbury, James and Chanan, Gregory and Killeen,
Trevor and Lin, Zeming and Gimelshein, Natalia and Antiga, Luca and Desmaison,
Alban and Kopf, Andreas and Yang, Edward and DeVito, Zacha (2019)), and for
the error estimation model, the extreme boosting gradient from XGBoost was
used (Chen and Guestrin (2016)).

##  3 Results

###  3.1 Error prediction

Figures 2 \- 10 show the results of the error estimation component of the
confidence net on the test data of each dataset. Although the training size
has been reduced to almost half of the dataset, the confidence nets model
maintains robust error prediction performance on most test datasets.
As seen in the results, the confidence nets error estimation component can
estimate several weaknesses of the neural network’s predictions; in some
cases, the error can be reduced to less than 0.05. It is interesting to note
that the error estimates are incredibly accurate for the rectangular concrete
columns dataset, foamed concrete dataset and Experimental dataset, which have
dataset sizes of 623, 1133, and 639, respectively. We deduce that the reason
may be due to the high-quality data in these datasets, resulting in reasonable
estimations. In other datasets such as (Yeh (1998); Altayeb, Mohamedelmujtaba;
Wang, Xin; Musa (2021); Ramagiri, Kruthi Kiran; Boindala, Sriman Pankaj; Zaid
(2021); Jeong, Hoseong ; Han, Sun-Jin; Choi, Seung-Ho; Kim, Jae Hyun ; Kim
(2020), the confidence nets error estimation model performance is satisfying,
but the accuracy is reduced slightly. On a few occasions, the confidence nets
model makes drastic mistakes, and the error is estimated as a positive error
when it is a negative error (i.e. the correction makes the prediction worse).
However, this is seen rarely and can be due to human error in these data
points. For the time being, the confidence nets model is incapable of
modelling a probability of human error and does not take any measures to
quantify it. The worst performance is seen in the predictions performed on the
Concrete Slump Test dataset (Yeh (2007)) and (Irandegani, Mohammad Ali; Zhang,
Daxu; Shadabfar (2021)). This is expected as these two datasets have the
smallest number of samples; thus, training data is minimal and may not provide
proper weight updates to reach an excellent local optimum. This further
deteriorates the performance of the test dataset.

(a) Training Size (90%)

(b) Training Size (55%)

Figure 2: Dataset: Concrete Slump Test

(a) Training Size (90%)

(b) Training Size (55%)

Figure 3: Dataset: Concrete Compressive Strength

(a) Training Size (90%)

(b) Training Size (55%)

Figure 4: Dataset: 622 Rectangular Concrete-filled steel tube columns

(a) Training Size (90%)

(b) Training Size (55%)

Figure 5: Dataset: Strain Hardening Cementitious Composites Data for FDNN
ensemble predictive model

(a) Training Size (90%)

(b) Training Size (55%)

Figure 6: Dataset: Compressive strength dataset of foamednormal concrete for
prediction model

(a) Training Size (90%)

(b) Training Size (55%)

Figure 7: Dataset: Compressive strength of alkali-activated binder concrete
cured at ambient temperature

(a) Training Size (90%)

(b) Training Size (55%)

Figure 8: Dataset: A Dataset of Compressive Strength of FRCM-confined Concrete
Columns

(a) Training Size (90%)

(b) Training Size (55%)

Figure 9: Dataset: Fake transfer length data generated using generative
adversarial networks

(a) Training Size (90%)

(b) Training Size (55%)

Figure 10: Dataset: Experimental dataset

###  3.2 Error Inclusion

Table 2 shows the results of the comparison between ANNs and the Confidence
nets model. As expected, ANNs without any modifications performed poorly on
small datasets. The only exception is the 622 samples dataset of RCFST
columns, where all the predictions were correctly within the average training
error. The confidence-nets model provides much more robust and consistent
performance on small datasets than the base ANN model. In the case of
experimental data, the results are significantly improved compared to the base
ANN.

Table 2: The calculations of error inclusion for two training sets sizes are shown (90% and 55%). The higher performance is highlighted in bold font. # |  Dataset Name | Training Size (90%) | Training Size (55%)
---|---|---|---
. |  . |  ANN |  Confidence-net |  ANN |  Confidence-net
1 |  Concrete Slump Test (Yeh (2007)) |  0% |  72% |  0% |  42.5%
2 |  Concrete Compressive Strength (Yeh (1998)) |  0% |  83% |  0% |  77%
3 |  Dataset of 622 Rectangular Concrete-filled steel tube columns (Nguyen Thi Mai (2021)) |  100% |  84% |  100% |  79%
4 |  Strain Hardening Cementitious Composites Data for FDNN ensemble predictive model (Altayeb, Mohamedelmujtaba; Wang, Xin; Musa (2021)) |  0% |  63% |  0% |  63%
5 |  Compressive strength dataset of foamed/normal concrete for prediction model (NGUYEN, TUAN; NGO (2018)) |  0% |  83% |  0% |  79%
6 |  Compressive strength of alkali-activated binder concrete cured at ambient temperature (Ramagiri, Kruthi Kiran; Boindala, Sriman Pankaj; Zaid (2021)) |  0% |  68% |  0% |  61%
7 |  A Dataset of Compressive Strength of FRCM-confined Concrete Columns (Irandegani, Mohammad Ali; Zhang, Daxu; Shadabfar (2021)) |  0% |  68% |  0% |  61%
8 |  Fake transfer length data generated using generative adversarial networks (Jeong, Hoseong ; Han, Sun-Jin; Choi, Seung-Ho; Kim, Jae Hyun ; Kim (2020)) |  0% |  75% |  0% |  74%
9 |  Experimental dataset (Chen, Huaicheng; Qian, Chunxiang; Liang, Chengyao; Kang ) |  0% |  97% |  0% |  95%

##  4 Discussion

Although the Confidence nets provide higher performance on smaller datasets,
it is still in their infant stages of development, and the concept is far from
perfect. However, as seen from the results in section 3, the concept can work
reliably with datasets of size $\geq$ 241 (the smallest dataset that provided
good results). Not only this, but the results of the inclusion test show that
although the confidence nets concept is reasonably simple, it is more
efficient than traditional neural network models. Furthermore, it provides a
more informative prediction and is a step towards constructing a reliable
prediction interval. It must be taken into account that the prediction
interval of the confident nets is always trying to detect weaknesses of the
neural network instead of just providing general estimates. The dataset sizes
demonstrated are possible to collect in research, and the confidence nets
model has proven that it can make the most of small datasets. The error
estimation model provides significant assistance in improving the neural
network model predictions, and we expect this to provide more robust
performance for more complex neural network architectures. The model is
expected to generally increase in size per the properties of the XGBoost model
when trained against large datasets. As the decision trees grow with training
data, the model will correspondingly increase in size. For this reason, we
used the XGBoost algorithm, which may be much more efficient than other tree-
based methods. Perhaps, this increase in size is one main disadvantage that
must be overcome in the future. However, in the meantime, the Confidence nets
model can be used as a solution for conducting experiments where an expected
error interval is needed. In its current form, the concept of the confidence
nets model can be implemented in fields where conducting experiments is
expensive, such as civil engineering, material design, etc…

##  5 Conclusion

In this paper, we proposed a simple idea for providing reliable predictions
while estimating errors using an ensemble learning technique named confidence
net. The confidence nets model is a step towards constructing prediction
intervals for regression neural networks. This approach has proven to
significantly increase accuracy on small datasets without adding further
complexity to the neural network’s architecture or affecting the application
of transfer learning. Moreover, the constructed Prediction Interval gives an
informative indicator of the model’s confidence in a prediction. The proposed
method is tested on various datasets, and a significant improvement in the
performance of the neural network model is seen.

  * •

The confidence nets model could reliably predict errors even when the training
dataset size was decreased from 90% to 55%. The performance of the confidence
nets largely remained the same.

  * •

The robustness of the model is also tested by increasing the test dataset size
up to 45% of the available data. Still, the model can provide reliable
predictions on an average of 83% of the time.

  * •

The model’s performance indicates that it is possible to use the current
confidence nets model on small datasets of sizes $\geq$241 (the smallest
dataset that provided good results).

  * •

Finally, the overview of the estimates shows that the confidence nets model
does not tend to provide the largest error margins to include errors. Instead,
the model attempts to provide smaller prediction intervals, but this interval
is increased by introducing the factors $\omega$ and the dissimilarity factor
$d_{e}$.

The above finding shows that the confidence nets ensemble currently applies to
many problems and can provide reliable results. However, further studies are
needed to confirm the reliability of this concept. We expect that with more
developments, the next versions of confidence nets may become more suitable
and stable over time, thus providing higher accuracy and reliability for
estimating experimental success.

##  6 Acknowledgements

The authors thank everyone involved in the preparation of this preprint.

## References

  * Mnih et al. [2015] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis.  Human-level control through deep reinforcement learning.  _Nature_ , 518(7540):529–533, 2015.  ISSN 14764687.  doi:10.1038/nature14236.  URL http://dx.doi.org/10.1038/nature14236.
  * Géron [2017] Aurélien Géron.  _Hands-on Machine Learning with Scikit-Learn, Keras, and TensorFlow (2019, O’reilly)_.  O’Reilly Media, 2017.  ISBN 9781492032649.
  * Wang et al. [2020] Yipei Wang, Shuaikun Hou, and Xin Wang.  Reinforcement learning-based bird-view automated vehicle control to avoid crossing traffic.  _Computer-Aided Civil and Infrastructure Engineering_ , (2018):1–12, 2020.  ISSN 14678667.  doi:10.1111/mice.12572.
  * Jumper et al. [2021] John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Žídek, Anna Potapenko, Alex Bridgland, Clemens Meyer, Simon A.A. Kohl, Andrew J. Ballard, Andrew Cowie, Bernardino Romera-Paredes, Stanislav Nikolov, Rishub Jain, Jonas Adler, Trevor Back, Stig Petersen, David Reiman, Ellen Clancy, Michal Zielinski, Martin Steinegger, Michalina Pacholska, Tamas Berghammer, Sebastian Bodenstein, David Silver, Oriol Vinyals, Andrew W. Senior, Koray Kavukcuoglu, Pushmeet Kohli, and Demis Hassabis.  Highly accurate protein structure prediction with AlphaFold.  _Nature_ , 596(May), 2021.  ISSN 14764687.  doi:10.1038/s41586-021-03819-2.  URL http://dx.doi.org/10.1038/s41586-021-03819-2.
  * Chollet [2018] François Chollet.  _Deep Learning with Phyton_.  Manning Publications, 2018.  ISBN 9781617294433.
  * Fan et al. [2021] Feng Lei Fan, Jinjun Xiong, Mengzhou Li, and Ge Wang.  On Interpretability of Artificial Neural Networks: A Survey.  _IEEE Transactions on Radiation and Plasma Medical Sciences_ , 5(6):741–760, 2021.  ISSN 24697311.  doi:10.1109/TRPMS.2021.3066428.
  * Tsuji and Suzuki [2021] Kazuma Tsuji and Taiji Suzuki.  Estimation error analysis of deep learning on the regression problem on the variable exponent Besov space.  _Electronic Journal of Statistics_ , 15(1), jan 2021.  ISSN 1935-7524.  doi:10.1214/21-EJS1828.  URL https://projecteuclid.org/journals/electronic-journal-of-statistics/volume-15/issue-1/Estimation-error-analysis-of-deep-learning-on-the-regression-problem/10.1214/21-EJS1828.full.
  * Minakowski and Richter [2023] P. Minakowski and T. Richter.  A priori and a posteriori error estimates for the Deep Ritz method applied to the Laplace and Stokes problem.  _Journal of Computational and Applied Mathematics_ , 421:114845, mar 2023.  ISSN 03770427.  doi:10.1016/j.cam.2022.114845.  URL https://linkinghub.elsevier.com/retrieve/pii/S0377042722004435.
  * Lai et al. [2022] Yuandu Lai, Yucheng Shi, Yahong Han, Yunfeng Shao, Meiyu Qi, and Bingshuai Li.  Exploring uncertainty in regression neural networks for construction of prediction intervals.  _Neurocomputing_ , 481:249–257, apr 2022.  ISSN 09252312.  doi:10.1016/j.neucom.2022.01.084.  URL https://linkinghub.elsevier.com/retrieve/pii/S0925231222001102.
  * Kompa et al. [2021] Benjamin Kompa, Jasper Snoek, and Andrew L. Beam.  Empirical Frequentist Coverage of Deep Learning Uncertainty Quantification Procedures.  _Entropy_ , 23(12):1608, nov 2021.  ISSN 1099-4300.  doi:10.3390/e23121608.  URL https://www.mdpi.com/1099-4300/23/12/1608.
  * Hirschfeld et al. [2020] Lior Hirschfeld, Kyle Swanson, Kevin Yang, Regina Barzilay, and Connor W. Coley.  Uncertainty Quantification Using Neural Networks for Molecular Property Prediction.  _Journal of Chemical Information and Modeling_ , 60(8):3770–3780, 2020.  ISSN 1549960X.  doi:10.1021/acs.jcim.0c00502.
  * Abdar et al. [2021] Moloud Abdar, Farhad Pourpanah, Sadiq Hussain, Dana Rezazadegan, Li Liu, Mohammad Ghavamzadeh, Paul Fieguth, Xiaochun Cao, Abbas Khosravi, U. Rajendra Acharya, Vladimir Makarenkov, and Saeid Nahavandi.  A review of uncertainty quantification in deep learning: Techniques, applications and challenges.  _Information Fusion_ , 76:243–297, dec 2021.  ISSN 15662535.  doi:10.1016/j.inffus.2021.05.008.  URL https://linkinghub.elsevier.com/retrieve/pii/S1566253521001081.
  * Altayeb et al. [2021] Mohamedelmujtaba Altayeb, Xin Wang, and Taha Hussein Musa.  An ensemble method for predicting the mechanical properties of strain hardening cementitious composites.  _Construction and Building Materials_ , 286:122807, 2021\.  ISSN 09500618.  doi:10.1016/j.conbuildmat.2021.122807.  URL https://doi.org/10.1016/j.conbuildmat.2021.122807.
  * Yeh [2007] I-Cheng Yeh.  Modeling slump flow of concrete using second-order regressions and artificial neural networks.  _Cement and Concrete Composites_ , 29(6):474–480, 2007.  URL http://archive.ics.uci.edu/ml/datasets/Concrete+Slump+Test.
  * Nguyen Thi Mai [2021] Suong Nguyen Thi Mai.  Dataset of 622 Rectangular Concrete-filled steel tube columns.  _Mendeley Data_ , 1, 2021.  doi:10.17632/thssskwntd.1.
  * Altayeb, Mohamedelmujtaba; Wang, Xin; Musa [2021] Taha Altayeb, Mohamedelmujtaba; Wang, Xin; Musa.  Engineered Cementitious Composites Dataset / Strain Hardening Cementitious Composites Data for FDNN ensemble predictive model.  _Mendeley Data_ , 1, 2021.  doi:10.17632/584ydjx3xm.1.
  * NGUYEN, TUAN; NGO [2018] TUAN NGUYEN, TUAN; NGO.  Compressive strength dataset of foamed/normal concrete for prediction model.  _University of Melbourne. Dataset_ , 2018.  doi:https://doi.org/10.26188/5bf33d0980a11.
  * Ramagiri, Kruthi Kiran; Boindala, Sriman Pankaj; Zaid [2021] Md Ramagiri, Kruthi Kiran; Boindala, Sriman Pankaj; Zaid.  Compressive strength of alkali-activated binder concrete cured at ambient temperature.  _Mendeley Data_ , 1, 2021.  doi:10.17632/zpdnn2gh4m.1.
  * Irandegani, Mohammad Ali; Zhang, Daxu; Shadabfar [2021] Mahdi Irandegani, Mohammad Ali; Zhang, Daxu; Shadabfar.  A Dataset of Compressive Strength of FRCM-confined Concrete Columns.  _Mendeley Data_ , 1, 2021.  doi:10.17632/f3xrpg8b27.1.
  * Jeong, Hoseong ; Han, Sun-Jin; Choi, Seung-Ho; Kim, Jae Hyun ; Kim [2020] Kang Su Jeong, Hoseong ; Han, Sun-Jin; Choi, Seung-Ho; Kim, Jae Hyun ; Kim.  Fake transfer length data generated using generative adversarial networks.  _Mendeley Data_ , 1, 2020.  doi:10.17632/d3y4kbd7hd.1.
  * [21] Wence Chen, Huaicheng; Qian, Chunxiang; Liang, Chengyao; Kang.  Experimental dataset.. PLOS ONE Dataset.  doi:https://doi.org/10.1371/journal.pone.0191370.s001.
  * Paszke, Adam and Gross, Sam and Massa, Francisco and Lerer, Adam and Bradbury, James and Chanan, Gregory and Killeen, Trevor and Lin, Zeming and Gimelshein, Natalia and Antiga, Luca and Desmaison, Alban and Kopf, Andreas and Yang, Edward and DeVito, Zacha [2019] Soumith Paszke, Adam and Gross, Sam and Massa, Francisco and Lerer, Adam and Bradbury, James and Chanan, Gregory and Killeen, Trevor and Lin, Zeming and Gimelshein, Natalia and Antiga, Luca and Desmaison, Alban and Kopf, Andreas and Yang, Edward and DeVito, Zacha.  PyTorch: An Imperative Style, High-Performance Deep Learning Library.  In _Advances in Neural Information Processing Systems 32_ , pages 8024–8035. Curran Associates, Inc., 2019.  URL http://papers.neurips.cc/paper/9015-pytorch-an-imperative-style-high-performance-deep-learning-library.pdf.
  * Chen and Guestrin [2016] Tianqi Chen and Carlos Guestrin.  XGBoost.  In _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , pages 785–794, New York, NY, USA, aug 2016. ACM.  ISBN 9781450342322.  doi:10.1145/2939672.2939785.  URL https://dl.acm.org/doi/10.1145/2939672.2939785.
  * Yeh [1998] Cheng Yeh.  Modeling of strength of high performance concrete using artificial neural networks.  _Cement and Concrete Research_ , 28(12):1797–1808, 1998.  URL https://archive.ics.uci.edu/ml/datasets/concrete+compressive+strength.