# The maximal running time of hypergraph bootstrap percolation

Ivailo Hartarsky  TU Wien, Faculty of Mathematics and Geoinformation,
Institute of Statistics and Mathematical Methods in Economics, Research Unit
of Mathematical Stochastics, Wiedner Hauptstraße 8-10, A-1040 Vienna, Austria,
<EMAIL_ADDRESS>Lyuben Lichev  Jean Monnet University and
Institut Camille Jordan, Saint-Etienne and Lyon, France, lyuben.lichev@univ-
st-etienne.fr

###### Abstract

We show that for every $r\geq 3$, the maximal running time of the
$K^{r}_{r+1}$-bootstrap percolation in the complete $r$-uniform hypergraph on
$n$ vertices $K_{n}^{r}$ is $\Theta(n^{r})$. This answers a recent question of
Noel and Ranganathan in the affirmative, and disproves a conjecture of theirs.
Moreover, we show that the prefactor is of the form $r^{-r}\mathrm{e}^{O(r)}$
as $r\to\infty$.

MSC2020: 05C35; 05C65; 05D99
Keywords: Bootstrap percolation, maximal running time, complete hypergraph

##  1 Introduction

###  1.1 Background

Bootstrap percolation is a widely studied model for spreading infection or
information on a graph. Given an initial set of infections, this process
iteratively adds infections if a certain local pattern of infections is
already present. While the original statistical physics perspective suggests
selecting initial infections at random, interesting computational and extremal
combinatorial questions arise when considering deterministic instances. The
most classical extremal problems are determining the minimal number of
infections necessary for infecting the entire graph and the maximal time until
stationarity or complete infection.

These maximal times have been studied in several settings, including grids
[Benevides15] and hypercubes [Przykucki12, Hartarsky18]. Bootstrap percolation
in which one infects the edges of a graph when they complete a copy of a fixed
graph is referred to graph bootstrap percolation or weak saturation. In that
setting, the maximal times were studied in [BaloghNan, Bollobas17a, Matzke15].
Finally, our setting of interest is the more general hypergraph bootstrap
percolation, where maximal times were recently investigated by Noel and
Ranganathan [Noel23].

###  1.2 Model and result

For a positive integer $r\geq 2$ and an $r$-uniform hypergraph $H$ (or
$r$-graph for short), we identify $H$ with its edge set and denote by $V(H)$
the set of vertices of $H$. In this paper, we pay particular attention to the
complete $r$-graph on $n$ vertices denoted $K^{r}_{n}$, especially the
$r$-graph $K^{r}_{r+1}$, which we denote $F_{r}$ for short.

For a positive integer $r\geq 2$ and an $r$-graph $F$, the _$F$ -bootstrap
process in $K^{r}_{n}$_ is a monotone cellular automaton described as follows.
At the beginning, a subgraph $G_{0}$ of $K^{r}_{n}$ is infected. At every step
$i\geq 1$, we define

$G_{i}=G_{i-1}\cup\\{e\in K^{r}_{n}\colon\text{there is a copy
}F^{\prime}\subset K^{r}_{n}\text{ of }F\text{ such that
}e=F^{\prime}\setminus G_{i-1}\\}.$ (1)

The _running time_ until stationarity (that is, the first step $i$ at which
$G_{i}=G_{i+1}$) of the $F$-bootstrap percolation with initially infected set
$G_{0}$ is denoted by $T(F,G_{0},n)$. In [Noel23] it was proved that

$\max_{G_{0}\subset K_{n}^{r}}T(K_{m}^{r},G_{0},n)=\Theta(n^{r})$

for all fixed $m\geq r+2\geq 5$. In this paper, we are interested in the
_maximum running time_ of the $F_{r}$-bootstrap percolation $T_{r}(n)$ defined
as

$T_{r}(n)=\max_{G_{0}\subset K^{r}_{n}}T(F_{r},G_{0},n).$

In this case, [Noel23] only established that for all $r\geq 3$, $T_{r}(n)\geq
c_{r}n^{r-1}$ for some $c_{r}>0$. Our work closes the gap between this lower
bound and the trivial upper bound $T_{r}(n)\leq\binom{n}{r}$. More precisely,
we answer Question 5.2 from [Noel23] in a strong sense, and disprove
Conjecture 5.1 from the same paper suggesting that $T_{3}(n)=O(n^{2})$.

######  Question 1 (Question 5.2 from [Noel23]).

Does there exist an integer $r_{0}$ such that, if $r\geq r_{0}$, then
$T_{r}(n)=\Theta(n^{r})$?

Our main result is the following lower bound.

######  Theorem 2.

For every $r\geq 3$ and $n\geq 2r^{2}$, we have

$\frac{n^{r}}{2^{r+3}r^{r}}\leq T_{r}(n)\leq\frac{n^{r}e^{r}}{r^{r}}.$

Let us note that, while our result shows that the constant prefactor is
$r^{-r}\mathrm{e}^{O(r)}$ as $r\to\infty$, our construction has not been
optimised for this purpose, but rather for the clarity of the exposition. We
also observe that the condition $n\geq 2r^{2}$ is imposed mostly for technical
reasons and is only used in (2).

###  1.3 Outline of the proof

Theorem 2 is proved as follows. We start with a simple construction showing
that $T_{3}(2(4k-3)+1)\geq 8k^{2}-12k+4$ for any $k\geq 1$ (see Section 3),
which reproves the corresponding result of [Noel23]. The construction (see
Fig. 2) consists of two vertex-disjoint paths, each containing $4k-3$
vertices, and an additional vertex $v_{1}^{3}$. The edges in the initial graph
are: $v_{1}^{3}$ together with any 2-edge in some of the paths, $v_{1}^{3}$
together with the initial vertices of the two paths, and some $3$-edges that
do not contain $v_{1}^{3}$. This is done so that, firstly, only one edge is
infected per time step, secondly, all edges which become infected contain
$v_{1}^{3}$ and one vertex in each path, and moreover, the process is
reversible in the sense that, if we replace the edge joining the beginnings of
the two paths by the last edge infected by the process, the same edges become
infected but in reverse order.

Based on this construction, we prove Theorem 2 for $r=3$ by gluing $2k-1$
instances of it, as shown in Fig. 1 (see Proposition 4). Namely, using an
auxiliary vertex $v_{2}^{3}$, we propagate the infection from the end of the
process for the vertex $v_{1}^{3}$ to the end of the same process for a new
vertex $v_{3}^{3}$ instead of $v_{1}^{3}$, which will then run the other way
around. Repeating this procedure $2k-2$ times, we obtain a cubic running time.
The key feature of this strategy is that no edges that do not contain
$v_{1}^{3}$ are created in the first construction, so we do not alter the
configuration induced by the first $2(4k-3)$ vertices. Moreover, the same
gluing technique allows us to extend the construction from $r$ to $r+1$ by
adding a vertex to all edges, adding all edges that do not contain this
vertex, and then gluing copies of this construction that differ only in this
special vertex while keeping the remaining ones unchanged.

##  2 Proof of Theorem 2

To start with, we fix a positive integer $k=k(n)$ to be chosen appropriately
later. Then, for all integers $i\geq 1$, we define the vertex sets

$\displaystyle A_{i}$
$\displaystyle{}=\\{v_{1}^{i},v_{2}^{i},\dots,v_{4k-3}^{i}\\},$ $\displaystyle
A^{*}_{i}$ $\displaystyle{}=\bigcup_{j=1}^{i}A_{j}.$

In particular, the sets $(A_{i})_{i\geq 1}$ are disjoint while the sets
$(A_{i}^{*})_{i\geq 1}$ form an increasing sequence with respect to inclusion.
Next, we consider a particular case of $F_{r}$-bootstrap percolation where a
sequence of edges can be infected both in the given and in a reverse order
under a suitable initial condition.

$v_{2k-3}^{1}$$v_{2k-2}^{1}$$v_{2k-1}^{1}$$v_{2k}^{1}$$v_{2k+1}^{1}$$v_{2k-3}^{2}$$v_{2k-2}^{2}$$v_{2k-1}^{2}$$v_{2k}^{2}$$v_{2k+1}^{2}$$v_{1}^{3}$$v_{2}^{3}$$v_{3}^{3}$
Figure 1: Illustration of the transition between the last step of stage $k-1$
for the vertex $v_{1}^{3}$ and the first step of the first stage for the
vertex $v_{3}^{3}$. On this intermediate step, only the edge
$v_{2k-1}^{1}v_{2k-1}^{2}v_{2}^{3}$ is infected. Note that 3-edges are
represented by smaller homothetic copies of the corresponding triangles.

######  Definition 3.

Let $r\geq 3$ be an integer and $H$ be an $r$-graph with vertex set
$V(H)\subset A_{r}^{*}$ and edge set $E(H)$. Given a sequence
$(e_{i})_{i=0}^{T}$ of edges in $E(H)$, we say that $H$ is
_$(e_{i})_{i=0}^{T}$ -sequential_ if the $F_{r}$-bootstrap percolation process
in the complete $r$-graph on $V(H)$ with initially infected $r$-graph:

  1. (i)

$H$ runs for $T$ steps, infecting only the $r$-edge $e_{i}$ at step
$i\in[1,T]$;

  2. (ii)

$H\setminus\\{e_{0}\\}$ is stationary (does not infect any $r$-edge);

  3. (iii)

$(H_{1}\cup\\{e_{T}\\})\setminus\\{e_{0}\\}$ infects only the $r$-edge
$e_{T-i}$ at step $i\in[1,T]$.

Definition 3 is central in the key construction presented in the next
proposition.

######  Proposition 4.

Fix integers $r\geq 3$ and $k\geq 2$. Let $T_{1}\geq 2$ be an integer and
$H_{1}$ be an $r$-graph with vertices $A^{*}_{r-1}\cup\\{v^{r}_{1}\\}$.
Suppose that $H_{1}$ is $(e_{i})_{i=0}^{T_{1}}$-sequential with
$v_{1}^{r}\in\bigcap_{i=0}^{T_{1}}e_{i}$. For all $j\in[1,2k-1]$, let
$H_{2j-1}$ be a copy of $H_{1}\setminus\\{e_{0}\\}$ obtained by replacing
$v^{r}_{1}$ by $v_{2j-1}^{r}$. Moreover, define
$e_{i}^{-}=e_{i}\setminus\\{v_{1}^{r}\\}$, and for all $j\in[1,k-1]$, let

$\displaystyle H_{4j-2}={}$
$\displaystyle\\{e\subset\\{v_{4j-3}^{r},v^{r}_{4j-2},v^{r}_{4j-1}\\}\cup
e_{T_{1}}^{-}\colon|e|=r,\\{v_{4j-3}^{r},v^{r}_{4j-1}\\}\not\subset
e,e_{T_{1}}^{-}\not\subset e\\}$ $\displaystyle H_{4j}={}$
$\displaystyle\\{e\subset\\{v_{4j-1}^{r},v^{r}_{4j},v^{r}_{4j+1}\\}\cup
e_{0}^{-}\colon|e|=r,\\{v_{4j-1}^{r},v^{r}_{4j+1}\\}\not\subset
e,e_{0}^{-}\not\subset e\\}$

(see Fig. 1 for an illustration of $H_{2}$ with $r=3$, one choice of $H_{1}$
and $e_{T_{1}}^{-}=\\{v_{2k-1}^{1},v_{2k-1}^{2}\\}$, so that
$H_{2}=\\{v_{2k-1}^{1}v_{1}^{3}v_{2}^{3},v_{2k-1}^{2}v_{1}^{3}v_{2}^{3},v_{2k-1}^{1}v_{2}^{3}v_{3}^{3},v_{2k-1}^{2}v_{2}^{3}v_{3}^{3}\\}$).
Let $H=\bigcup_{j=1}^{4k-3}H_{j}$. Then, for $T=(2k-1)T_{1}+4(k-1)$, there
exists a sequence of $r$-edges $(e_{i})_{i=0}^{T}$ extending
$(e_{i})_{i=0}^{T_{1}}$ such that $H$ is $(e_{i})_{i=0}^{T}$-sequential.

We prove Theorem 2 by induction on $r$. The induction step is based on
Proposition 4, leading to the following statement.

######  Proposition 5.

Let $k\geq 2$. There exist $r$-edges $(e_{i})_{i=0}^{T_{1}}$ all containing
$v_{1}^{r}$ and a $(e_{i})_{i=0}^{T_{1}}$-squential $r$-graph $H_{1}$ with
$V(H_{1})=A_{r-1}^{*}\cup\\{v_{1}^{r}\\}$ and
$T_{1}=(2k-1)^{r-3}(8k^{2}-12k+6)-2$.

The base case $r=3$ of Proposition 5 is left to Section 3.

###### Proof of Proposition 5 assuming the case $r=3$.

We argue by induction on $r$, the base being established in Section 3. Assume
the induction hypothesis to be true for some $r\geq 3$. Then, Proposition 4
provides us with an $(e_{i})_{i=0}^{T}$-sequential $r$-graph denoted $H^{r}$
with $V(H^{r})=A_{r}^{*}$ and

$T=(2k-1)T_{1}+4(k-1)=(2k-1)^{r-2}(8k^{2}-12k+6)-2.$

Let $K$ be the complete $(r+1)$-graph with $V(K)=A_{r}^{*}$. Define the
$(r+1)$-graph

$H^{r+1}_{1}=\\{e\cup\\{v^{r+1}_{1}\\}\colon e\in H^{r}\\}\cup K.$

We claim that $H_{1}^{r+1}$ is
$(e_{i}\cup\\{v_{1}^{r+1}\\})_{i=0}^{T}$-sequential. To see this, observe that
$H_{1}^{r+1}\setminus\\{e_{0}\cup\\{v_{1}^{r+1}\\}\\}\supset K$ and proceed as
follows.

Fix any $(r+1)$-graph $H^{\prime}\supset K$ with
$V(H^{\prime})=A_{r}^{*}\cup\\{v_{1}^{r+1}\\}$. Let $H^{\prime}_{i}$ be the
set of $(r+1)$-edges infected in the $F_{r+1}$-bootstrap percolation process
on the complete graph on $V(H^{\prime})$ and initially infected $(r+1)$-graph
$H^{\prime}$ at step $i$. Similarly, let $H^{\prime\prime}_{i}$ be the set of
$r$-edges infected in the $F_{r}$-bootstrap percolation process on the
complete $r$-graph with vertex set $A_{r}^{*}$ with initially infected
$r$-graph $H^{\prime\prime}=\\{e\setminus\\{v_{1}^{r+1}\\}\colon
v_{1}^{r+1}\in e\in H^{\prime}\\}$ at step $i$. Then, by induction on $i$, it
follows from the definition of these processes that

$H^{\prime\prime}_{i}=\\{e\setminus\\{v_{1}^{r+1}\\}\colon e\in
H^{\prime}_{i}\setminus K\\}.$

Applying this to
$H^{\prime}\in\\{H_{1}^{r+1},H_{1}^{r+1}\setminus\\{e_{0}\cup\\{v_{1}^{r+1}\\}\\},(H_{1}^{r+1}\cup\\{e_{T}\cup\\{v_{1}^{r+1}\\}\\})\setminus\\{e_{0}\cup\\{v_{1}^{r+1}\\}\\}\\}$,
it follows from Definition 3 that $H^{r+1}_{1}$ is
$(e_{i}\cup\\{v^{r+1}_{1}\\})_{i=0}^{T}$-sequential, as desired. ∎

We are now ready to conclude the proof of Theorem 2.

###### Proof of Theorem 2.

Fix $r\geq 3$ and set $k=\lfloor(n/r+3)/4\rfloor\geq n/(4r)-1/4$. For the
lower bound, we apply Proposition 5 and then Proposition 4 to obtain an
$r$-graph $H^{r}$ with $|A_{r}^{*}|=(r-1)(4k-3)+(4k-3)\leq n$ vertices such
that the $F_{r}$-bootstrap percolation process on the complete graph on
$A_{r}^{*}$ with initially infected $r$-graph $H^{r}$ runs for

$\displaystyle T$
$\displaystyle{}=(2k-1)^{r-2}(8k^{2}-12k+6)-2\geq(2k-1)^{r}\geq\left(\frac{n}{2r}-\frac{3}{2}\right)^{r}\geq\left(\frac{n}{2r}\right)^{r}\left(1-\frac{3r}{n}\right)^{r}$
$\displaystyle{}\geq\left(\frac{n}{2r}\right)^{r}\left(1-\frac{3}{2r}\right)^{r}\geq\left(\frac{n}{2r}\right)^{r}\left(1-\frac{3}{2\cdot
3}\right)^{3}=\frac{1}{8}\left(\frac{n}{2r}\right)^{r}.$ (2)

steps, since $n\geq 2r^{2}$ and $r\geq 3$. Thus, the lower bound of Theorem 2
is witnessed by the $r$-graph obtained by adding $n-|A_{r}^{*}|\geq 0$
isolated vertices to $H^{r}$. The upper bound simply states that the process
cannot run more than $\binom{n}{r}\leq n^{r}/r!\leq(ne/r)^{r}$ steps. ∎

In the sequel, we call a vertex _odd_ (resp.  _even_) if its subscript is odd
(resp. even).

###### Proof of Proposition 4.

First of all, let us show that the process in $H\setminus\\{e_{0}\\}$ is
stationary. Suppose for contradiction that this is not the case, and suppose
that some $(r+1)$-tuple of vertices $f$ spans exactly $r$ edges. To begin
with, $f$ cannot contain two non-consecutive vertices in $A_{r}$ since they
are not contained in a common $r$-edge of $H$. Moreover, $f$ cannot be
entirely contained in $A_{r-1}^{*}$ since otherwise
$H_{1}\setminus\\{e_{0}\\}$ would not be stationary. Two cases remain:

  * •

Suppose that $|f\cap A_{r}|=1$. Then the vertex in $f\cap A_{r}$ must be even
(otherwise, we obtain a contradiction with the stationarity of
$H_{1}\setminus\\{e_{0}\\}$). However, even vertices in $A_{r}$ are not
contained in edges with $r-1$ other vertices in $A_{r-1}^{*}$, so this case is
impossible.

  * •

Suppose that $f\cap A_{r}=\\{v_{i}^{r},v_{i+1}^{r}\\}$ for some
$i\in[1,4k-4]$. We further assume that $i=4j$ is divisible by 4, the other
cases being treated identically. Since the only edges containing $v_{4j}^{r}$
are those in $H_{4j}$, necessarily $f=\\{v_{4j}^{r},v_{4j+1}^{r}\\}\cup
e_{0}^{-}$. However, in this case the two edges $\\{v_{4j}^{r}\\}\cup
e_{0}^{-}$ and $\\{v_{4j+1}^{r}\\}\cup e_{0}^{-}$ are both missing, so we
obtain the desired contradiction.

Now, for every $j\in[1,2k-1]$ and every $i\in[0,T_{1}]$, denote
$e_{i,j}=e_{i}^{-}\cup\\{v_{2j-1}^{r}\\}$. In particular, $e_{i,1}=e_{i}$.
Further set

$H_{\infty}=H\cup\\{e_{i,j}\colon
i\in[0,T_{1}],j\in[1,2k-1]\\}\cup\\{\\{v_{4j-2}^{r}\\}\cup e_{T_{1}}^{-}\colon
j\in[1,k-1]\\}\cup\\{\\{v_{4j}^{r}\\}\cup e_{0}^{-}\colon j\in[1,k-1]\\}.$

We claim that $H_{\infty}$ is also stationary. As above, the $r+1$ tuple $f$
spanning exactly $r$ edges of $H_{\infty}$ falls in one of the following two
cases.

  * •

Suppose that $|f\cap A_{r}|=1$. Then, the vertex in $f\cap A_{r}$ must be even
as otherwise we obtain a contradiction with the fact that
$H_{1}\cup\\{e_{i,1}\colon i\in[0,T_{1}]\\}$ is stationary (which is true by
the definition of $T_{1}$). However, even vertices in $A_{r}$ are contained in
only one edge with $r-1$ other vertices in $A_{r-1}^{*}$, so this case is
impossible.

  * •

Suppose that $f\cap A_{r}=\\{v_{i}^{r},v_{i+1}^{r}\\}$ for some
$i\in[1,4k-4]$. Again, we assume that $i=4j$. Since the only edges containing
$v^{r}_{4j}$ are those in $H_{4j}\cup\\{\\{v_{4j}^{r}\\}\cup e_{0}^{-}\\}$,
necessarily $f=\\{v_{4j}^{r},v_{4j+1}^{r}\\}\cup e_{0}^{-}$. However, $f$
already spans a copy of $F_{r}$ in $H_{\infty}$, which leads to a
contradiction.

Moreover, since $H\subset H_{\infty}$, all edges infected by $H$ are contained
in $H_{\infty}$.

From Definition 3 one may conclude that for every $i\in[0,T_{1}]$, the only
copies of $F_{r}$ in $H_{1}\cup\\{e_{j}\\}_{j=1}^{T_{1}}$ that $e_{i}$
participates in are spanned by $e_{i-1}\cup e_{i}$ (if $i>0$) and by
$e_{i}\cup e_{i+1}$ (if $i<T_{1}$). Moreover, note that:

  * •

for every $j\in[1,2k-1]$, $v_{2j-1}^{r}$ is contained in a common edge of
$H_{\infty}$ with $v_{2j-2}^{r}$ (if $j\geq 2$) and with $v_{2j}^{r}$ (if
$j\leq 2k-2$), but with no other vertex in $A_{r}$,

  * •

no edge among $(e_{i,j})_{i=1}^{T_{1}-1}$ participates in a copy of $F_{r}$ in
$H_{\infty}$ with any of $v_{2j-2}^{r}$ and $v_{2j}^{r}$,

  * •

for every $j\geq 2$, $e_{0,j}$ spans a copy of $F_{r}$ in $H_{\infty}$
together with $v_{2j-2}^{r}$ and $e_{1}\setminus e_{0}$ (if $j$ is odd) or
$e_{T_{1}-1}\setminus e_{T_{1}}$ (if $j$ is even) only; for every $j\leq
2k-2$, $e_{T_{1},j}$ spans a copy of $F_{r}$ in $H_{\infty}$ together with
$v_{2j}^{r}$ and $e_{T_{1}-1}\setminus e_{T_{1}}$ (if $j$ is odd) or
$e_{1}\setminus e_{0}$ (if $j$ is even) only.

Furthermore, for every odd (resp. even) $j\in[1,2k-2]$, $v_{2j}^{r}\cup
e_{T_{1}}^{-}$ (resp. $v_{2j}^{r}\cup e_{0}^{-}$) spans a copy of $F_{r}$ in
$H_{\infty}$ together with $v_{2j-1}^{r}$ and $v_{2j+1}^{r}$ only. We conclude
that in the sequence of edges

$(e_{i,1})_{i=0}^{T_{1}},v_{2}^{r}\cup
e_{T_{1}}^{-},(e_{T_{1}-i,2})_{i=0}^{T_{1}},v_{4}^{r}\cup
e_{0}^{-},(e_{i,3})_{i=0}^{T_{1}},\dots,(e_{T_{1}-i,2k-2})_{i=0}^{T_{1}},v_{4k-4}^{r}\cup
e_{0}^{-},(e_{i,2k-1})_{i=0}^{T_{1}},$ (3)

every edge except the first one and the last one participate in exactly two
copies of $F_{r}$ in $H_{\infty}$, one spanned together with the edge
preceding it and another one with the edge succeeding it. Moreover, the first
and the last edges participate in exactly one copy of $F_{r}$ in $H_{\infty}$,
spanned together with $e_{1,1}$ and with $e_{T_{1}-1,2k-1}$, respectively.
Recalling Definition 3, this completes the proof of Proposition 4 since (3) is
an enumeration of all $T+1$ edges in
$H_{\infty}\setminus(H\setminus\\{e_{0}\\})$. ∎

##  3 The base case—proof of Proposition 5 for $r=3$

$v_{1}^{2}$$v_{2}^{2}$$v_{3}^{2}$$v_{4}^{2}$$v_{5}^{2}$$v_{4k-6}^{2}$$v_{4k-5}^{2}$$v_{4k-4}^{2}$$v_{4k-3}^{2}$$v_{1}^{1}$$v_{2}^{1}$$v_{3}^{1}$$v_{4}^{1}$$v_{5}^{1}$$v_{4k-5}^{1}$$v_{4k-4}^{1}$$v_{4k-3}^{1}$……
Figure 2:  The first stage of the bootstrap percolation process in $H_{1}$,
where all 2-edges depicted are parts of 3-edges including $v_{1}^{3}$. The
edges in $\mathcal{F}$ (defined in (5)) and the ignition edge $e_{0}$ are
represented by black 2-edges. They are infected initially, while red edges are
created one by one by the process. Green triangles represent the 3-edges in
$\mathcal{E}_{1}$ defined in (LABEL:eq_E-s)); they are all infected initially
as well. As in Fig. 1, we draw a 3-edge as a smaller homothetic copy of the
corresponding triangle.

In order to prove Proposition 5 for $r=3$, our goal is to construct a
sequential 3-graph $H_{1}$ with vertices $A_{2}^{*}\cup\\{v_{1}^{3}\\}$ and
running time $8k^{2}-12k+4$. For all $i\in[1,k-1]$, define the disjoint edge
sets

$\begin{split}&\mathcal{E}_{1,i}=\\{v_{2i-1}^{1}v_{j}^{2}v_{j+1}^{2}:j\in[2i-1,4k-2-2i]\\},\\\
&\mathcal{E}_{2,i}=\\{v_{j}^{1}v_{j+1}^{1}v_{4k-1-2i}^{2}:j\in[2i-1,4k-2-2i]\\},\\\
&\mathcal{E}_{3,i}=\\{v_{4k-1-2i}^{1}v_{j}^{2}v_{j+1}^{2}:j\in[2i+1,4k-2-2i]\\},\\\
&\mathcal{E}_{4,i}=\\{v_{j}^{1}v_{j+1}^{1}v_{2i+1}^{2}:j\in[2i+1,4k-2-2i]\\},\\\
&\mathcal{E}_{i}=\mathcal{E}_{1,i}\cup\mathcal{E}_{2,i}\cup\mathcal{E}_{3,i}\cup\mathcal{E}_{4,i}\end{split}$
(4)

(see Fig. 2 for an illustration of $\mathcal{E}_{1}$). Also, denote
$\mathcal{E}=\bigcup_{i=1}^{k-1}\mathcal{E}_{i}$. This is the set of edges
with vertices in $A_{2}^{*}$ that we infect at the beginning.

In addition to $\mathcal{E}$, some edges containing $v_{1}^{3}$ are also
infected initially (see Fig. 2). Denote

$\mathcal{F}=\bigcup_{j=1}^{4k-4}\bigcup_{l=1}^{2}\\{v_{j}^{l}v_{j+1}^{l}v_{1}^{3}\\}.$
(5)

In other words, the set $\mathcal{F}$ consists of all triplets containing the
vertex $v_{1}^{3}$ and a consecutive pair of vertices in one of the paths
$v^{1}_{1}v^{1}_{2}\dots v^{1}_{4k-3}$ and $v^{2}_{1}v^{2}_{2}\dots
v^{2}_{4k-3}$. Finally, we need the _ignition edge_
$e_{0}=v_{1}^{1}v^{2}_{1}v^{3}_{1}$ to start the growth process.

######  Lemma 6.

The set $\mathcal{E}\cup\mathcal{F}$ contains no $3$ edges with a total of $4$
vertices.

###### Proof.

Let us first consider $4$-tuples of vertices in $A_{2}^{*}$. Note that all
edges in $\mathcal{E}$ contain two odd vertices and one even vertex. Hence, a
set of 4 odd vertices in $A_{2}^{*}$ spans no edges, and a set of $4$ vertices
in $A_{2}^{*}$ with at most $2$ of them odd spans at most $2$ edges. Finally,
a set of $4$ vertices in $A_{2}^{*}$ with $3$ of them odd cannot span 3 edges
since at least two of the odd vertices are either both in $A_{1}$, or both in
$A_{2}$, and hence cannot participate in the same edge as they are not
consecutive.

Now, consider $4$-tuples containing the vertex $v_{1}^{3}$. On the one hand,
$A_{1}$ and $A_{2}$ are independent sets in the 3-graph $\mathcal{E}$, and
moreover the graph with edges $\\{e\setminus v_{1}^{3}\colon v_{1}^{3}\in
e\in\mathcal{F}\\}$ contains no triangles. Thus, every $4$-tuple containing
$v_{1}^{3}$ and three vertices in $A_{1}$ (respectively in $A_{2}$) spans no
edges of $\mathcal{E}$ and at most 2 edges of $\mathcal{F}$. It remains to
observe that every 4-tuple containing $v_{1}^{3}$ and at least one vertex from
both $A_{1}$ and $A_{2}$ cannot span more than 1 edge of $\mathcal{F}$ (so 2
edges in total) since $\mathcal{F}$ contains no edges intersecting both
$A_{1}$ and $A_{2}$. ∎

We are now ready to conclude the proof of Proposition 5 for $r=3$ by showing
the following statement, illustrated in Fig. 2 for $s=1$ and in Fig. 1 for
$s=k-1$. The proof is a straightforward but tedious verification.

######  Lemma 7.

The $3$-graph $H_{1}=\mathcal{E}\cup\mathcal{F}\cup\\{e_{0}\\}$ is
$(e_{i})_{i=0}^{T_{1}}$-sequential for

$\sum_{j=1}^{s-1}(16(k-j)-4)<i\leq\sum_{j=1}^{s}(16(k-j)-4)$

(which clearly exists since $T_{1}=\sum_{j=1}^{k-1}(16(k-j)-4)$). Moreover,
define

$\alpha=\alpha(i)=i-\sum_{j=1}^{s-1}(16(k-j)-4)\in[1,16(k-s)-4].$

Then,

  * •

if $\alpha\in[1,4(k-s)]$, then
$e_{i}=v_{2s-1}^{1}v_{2s-1+\alpha}^{2}v_{1}^{3}$;

  * •

if $\alpha\in[4(k-s)+1,8(k-s)]$, then
$e_{i}=v_{6s-4k-1+\alpha}^{1}v_{4k-2s-1}^{2}v_{1}^{3}$;

  * •

if $\alpha\in[8(k-s)+1,12(k-s)-2]$, then
$e_{i}=v_{4k-2s-1}^{1}v_{12k-10s-1-\alpha}^{2}v_{1}^{3}$;

  * •

if $\alpha\in[12(k-s)-1,16(k-s)-4]$, then
$e_{i}=v_{16k-14s-3-\alpha}^{1}v_{2s+1}^{2}v_{1}^{3}$.

Note that the sequence of $3$-edges indicated in Lemma 7 may be alternatively
described in the following more intuitive way (see Fig. 2). At the beginning,
the process first infects the edges $v_{1}^{1}v_{j}^{2}v_{1}^{3}$ for
$j\in[2,4k-3]$, then $v_{j}^{1}v_{4k-3}^{2}v_{1}^{3}$ for $j\in[2,4k-3]$, then
$v_{4k-3}^{1}v_{j}^{2}v_{1}^{3}$ for $j\in[3,4k-4]$ in reverse order, then
$v_{j}^{1}v_{3}^{2}v_{1}^{3}$ for $j\in[3,4k-4]$ in reverse order. At this
point, $s$ increases from 1 to 2. The process continues to propagate in a
similar way except that, every time $s$ increases, the “ends” shift two
vertices towards the middle (so $v_{3}^{1}$ plays the role of $v_{1}^{1}$ when
$s$ is incremented for the first time).

###### Proof.

To begin with, the $F_{3}$-bootstrap percolation process on the complete
$3$-graph with vertices $A_{2}^{*}\cup\\{v_{1}^{3}\\}$ and initially infected
$3$-graph $H_{1}\setminus\\{e_{0}\\}=\mathcal{E}\cup\mathcal{F}$ is stationary
by Lemma 6. Now, set $G_{-1}=\mathcal{E}\cup\mathcal{F}$, $G_{0}=H_{1}$ and
let the sequence $(G_{i})_{i\geq 1}$ be defined as in (1). We will show by
induction on $i\geq 0$ that $G_{i}\setminus G_{i-1}=\\{e_{i}\\}$.

For $i=0$ the statement is clear by construction. Suppose that for some $i\geq
0$, the induction hypothesis is satisfied for $i$. Then, all edges in
$G_{i+1}\setminus G_{i}$ must span 4 vertices with the edge $e_{i}$, and in
particular must intersect $e_{i}$ in 2 vertices. We consider 4 cases according
to the interval containing $\alpha=\alpha(i)$. For convenience, we extend the
notation by setting $s(0)=1$ and $\alpha(0)=0$ (so that $\alpha(i)=0$ only
when $s(i)=1$), which is consistent with
$e_{0}=v^{1}_{2s-1}v^{2}_{2s-1+\alpha}v_{1}^{3}$).

If $\alpha\in[0,4(k-s)]$, then
$e_{i}=v_{2s-1}^{1}v_{2s-1+\alpha}^{2}v_{1}^{3}$. One may easily check that
the vertices in $A_{2}^{*}$ that complete the pair
$v_{2s-1}^{1}v_{2s-1+\alpha}^{2}$ to an edge in $G_{i-1}$ are

$\begin{cases}v_{2s+\alpha}^{2}&\alpha=0,\\\
v_{2s-2+\alpha}^{2},v_{2s+\alpha}^{2}&\alpha\in[1,4(k-s)-1],\\\
v_{2s-2+\alpha}^{2},v_{2s}^{1}&\alpha=4(k-s).\end{cases}$

The vertices that complete the pair $v_{2s-1}^{1}v_{1}^{3}$ to an edge in
$G_{i-1}$ are

$\begin{cases}(v_{2s-1+j}^{2})_{j\in[0,\alpha-1]},v_{2s}^{1}&s=1,\\\
(v_{2s-1+j}^{2})_{j\in[0,\alpha-1]},v_{2s}^{1},v^{1}_{2s-2},(v_{2j-1}^{2})_{j\in[2,s-1]\cup[2k-s+1,2k-1]}&s\geq
2.\end{cases}$

Finally, the vertices that complete the pair $v_{2s-1+\alpha}^{2}v_{1}^{3}$ to
an edge in $G_{i-1}$ are

$\begin{cases}v_{2s+\alpha}^{2}&\alpha=0,\\\
(v_{2j-1}^{1})_{j\in[1,s-1]\cup[2k-s+1,2k-1]},v^{2}_{2s-2+\alpha},v_{2s+\alpha}^{2}&\alpha\in[1,4k-5],\\\
v^{2}_{2s-2+\alpha}&\alpha=4k-4.\end{cases}$

Then, the only vertices that complete at least two pairs are

$\begin{cases}v^{2}_{2}&\alpha=0,\\\
v^{2}_{2s+\alpha},v^{2}_{2s+\alpha}&\alpha\in[1,4(k-s)-1],\\\
v^{2}_{2s+\alpha},v^{1}_{2s}&\alpha=4(k-s).\end{cases}$

However, for $\alpha\neq 0$, $\\{v^{2}_{2s-2+\alpha}\\}\cup e_{i}$ already
spans a copy of $F_{3}$ in $G_{i}$, so the only edge that is generated from
$G_{i}$ is $e_{i+1}$.

If $\alpha\in[4(k-s)+1,8(k-s)]$, then
$e_{i}=v_{6s-4k-1+\alpha}^{1}v_{4k-2s-1}^{2}v_{1}^{3}$. One may easily check
that the vertices in $A_{2}^{*}$ that complete the pair
$v_{6s-4k-1+\alpha}^{1}v_{4k-2s-1}^{2}$ to an edge in $G_{i-1}$ are

$\begin{cases}v_{6s-4k-2+\alpha}^{1},v_{6s-4k+\alpha}^{1}&\alpha\neq
8(k-s),\\\ v_{4k-2s-2}^{1},v_{4k-2s-2}^{2}&\alpha=8(k-s).\end{cases}$

The vertices that complete the pair $v_{6s-4k-1+\alpha}^{1}v_{1}^{3}$ to an
edge in $G_{i-1}$ are

$\begin{cases}v^{1}_{4k-4}&\alpha=8k-8,\\\
(v_{2j-1}^{2})_{j\in[2,s-1]\cup[2k-s+1,2k-1]},v_{6s-4k-2+\alpha}^{1},v_{6s-4k+\alpha}^{1}&\text{otherwise.}\end{cases}$

Finally, the vertices that complete the pair $v_{4k-2s-1}^{2}v_{1}^{3}$ to an
edge in $G_{i-1}$ are

$\begin{cases}(v_{5-4k+j}^{1})_{j\in[4(k-1),\alpha-1]},v_{4k-4}^{2},&s=1,\\\
(v_{6s-4k-1+j}^{1})_{j\in[4(k-s),\alpha-1]},(v_{2j-1}^{1})_{j\in[1,s-1]\cup[2k-s+1,2k-1]},v_{4k-2s-2}^{2},v_{4k-2s}^{2}&s\neq
1.\end{cases}$

Then, the only vertices that complete at least two pairs are

$\begin{cases}v^{1}_{4k-2s-2},v^{2}_{4k-2s-2}&\alpha=8(k-s),\\\
v^{1}_{6s-4k-2+\alpha},v^{1}_{6s-4k+\alpha}&\alpha\neq 8(k-s).\end{cases}$

However, $\\{v_{6s-4k-2+\alpha}^{1}\\}\cup e_{i}$ already spans a copy of
$F_{3}$ in $G_{i}$, so the only edge that is generated from $G_{i}$ is
$e_{i+1}$.

If $\alpha\in[8(k-s)+1,12(k-s)-2]$, then
$e_{i}=v_{4k-2s-1}^{1}v_{12k-10s-1-\alpha}^{2}v_{1}^{3}$. One may easily check
that the vertices in $A_{2}^{*}$ that complete the pair
$v_{4k-2s-1}^{1}v_{12k-10s-1-\alpha}^{2}$ to an edge in $G_{i-1}$ are

$\begin{cases}v_{4k-2s-2}^{1},v_{2s+2}^{2}&\alpha=12(k-s)-2,\\\
v_{12k-10s-2-\alpha}^{2},v_{12k-10s-\alpha}^{2}&\alpha\neq
12(k-s)-2.\end{cases}$

The vertices that complete the pair $v_{4k-2s-1}^{1}v_{1}^{3}$ to an edge in
$G_{i-1}$ are

$\begin{cases}(v_{12k-11-j}^{2})_{j\in[8k-8,\alpha-1]},v_{4k-3}^{2},v_{4k-4}^{1},&s=1,\\\
(v_{12k-10s-1-j}^{2})_{j\in[8(k-s),\alpha-1]},(v_{2j-1}^{2})_{j\in[2,s]\cup[2k-s,2k-1]},v_{4k-2s-2}^{1},v_{4k-2s}^{1}&s\neq
1.\end{cases}$

The vertices that complete the pair $v_{12k-10s-1-\alpha}^{2}v_{1}^{3}$ to an
edge in $G_{i-1}$ are

$(v_{2j-1}^{1})_{j\in[1,s]\cup[2k-s+1,2k-1]},v_{12k-10s-2-\alpha}^{2},v_{12k-10s-\alpha}^{2}.$

Then, the only vertices that complete at least two pairs are

$\begin{cases}v_{4k-2s-2}^{1},v_{2s+2}^{2}&\alpha=12(k-s)-2\\\
v_{12k-10s-2-\alpha}^{2},v_{12k-10s-\alpha}^{2}&\alpha\neq
12(k-s)-2.\end{cases}$

However, $\\{v_{12k-10s-\alpha}^{2}\\}\cup e_{i}$ already spans a copy of
$F_{3}$ in $G_{i}$, so the only edge that is generated from $G_{i}$ is
$e_{i+1}$.

If $\alpha\in[12(k-s)-1,16(k-s)-4]$, then
$e_{i}=v_{16k-14s-3-\alpha}^{1}v_{2s+1}^{2}v_{1}^{3}$. One may easily check
that the vertices in $A_{2}^{*}$ that complete the pair
$v_{16k-14s-3-\alpha}^{1}v_{2s+1}^{2}$ to an edge in $G_{i-1}$ are

$\begin{cases}v^{1}_{2k}&\alpha=16(k-s)-4,s=k-1,\\\
v_{2s+2}^{1},v_{2s+2}^{2}&\alpha=16(k-s)-4,s\neq k-1\\\
v_{16k-14s-4-\alpha}^{1},v_{16k-14s-2-\alpha}^{1}&\alpha\neq
16(k-s)-4.\end{cases}$

The vertices that complete the pair $v_{16k-14s-3-\alpha}^{1}v_{1}^{3}$ to an
edge in $G_{i-1}$ are

$(v_{2j-1}^{2})_{j\in[2,s]\cup[2k-s,2k-1]},v_{16k-14s-4-\alpha}^{1},v_{16k-14s-2-\alpha}^{1}.$

Finally, the vertices that complete the pair $v_{2s+1}^{2}v_{1}^{3}$ to an
edge in $G_{i-1}$ are

$(v_{16k-14s-3-j}^{1})_{j\in[12(k-s)-2,\alpha-1]},(v_{2j-1}^{1})_{j\in[1,s]\cup[2k-s+1,2k-1]},v_{2s}^{2},v_{2s+2}^{2}.$

Then, the only vertices that complete at least two pairs are

$\begin{cases}v^{1}_{2k}&\alpha=16(k-s)-4,s=k-1,\\\
v_{2s+2}^{1},v_{2s+2}^{2}&\alpha=16(k-s)-4,s\neq k-1,\\\
v_{16k-14s-4-\alpha}^{1},v_{16k-14s-2-\alpha}^{1}&\alpha\neq
16(k-s)-4.\end{cases}$

However, $\\{v_{16k-14s-2-\alpha}^{1}\\}\cup e_{i}$ already spans a copy of
$F_{3}$ in $G_{i}$, so the only edge that is generated from $G_{i}$ is
$e_{i+1}$, and the process stops when it infects $e_{T_{1}}$.

It remains to show that the $F_{3}$-bootstrap percolation process on the
complete $3$-graph with vertices $A_{2}^{*}\cup\\{v_{1}^{3}\\}$ and initially
infected $3$-graph $\mathcal{E}\cup\mathcal{F}\cup\\{e_{T_{1}}\\}$ infects the
edges $(e_{i})_{i=0}^{T_{1}-1}$ in reverse order. Notice that in the process
started from $G_{0}$, every copy of $F_{3}$ that becomes completely infected
contains two edges in $\mathcal{E}\cup\mathcal{F}$ and the edges $e_{i}$ and
$e_{i+1}$ for some $i\geq 0$. Therefore, starting from
$\mathcal{E}\cup\mathcal{F}\cup\\{e_{T_{1}}\\}$, the edges that do become
infected are exactly $(e_{i})_{i=0}^{T_{1}}$. Moreover, all copies of $F_{3}$
in $G_{T_{1}}$ are spanned by some of the vertex sets $(e_{i-1}\cup
e_{i})_{i=1}^{T_{1}}$, which implies that the bootstrap percolation with
initial condition $\mathcal{E}\cup\mathcal{F}\cup\\{e_{T_{1}}\\}$ infects the
edges $(e_{i})_{i=0}^{T_{1}-1}$ in the reverse order. ∎

#### Acknowledgements.

The authors are grateful to the ‘Minu Balkanski’ foundation, where the current
project was initiated, and to the anonymous referees for useful comments and
remarks. IH was supported by the Austria Science Fund (FWF): P35428-N.

#### Note.

A few days after the current article appeared on arxiv, an independent proof
of a version of Theorem 2 was found by Espuny Díaz, Janzer, Kronenberg and
Lada [EspunyDiaz24].

## References


# UnibucKernel Reloaded: First Place in Arabic Dialect Identification for the
Second Year in a Row

Andrei M. Butnaru  Radu Tudor Ionescu
Department of Computer Science, University of Bucharest
14 Academiei, Bucharest, Romania
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

We present a machine learning approach that ranked on the first place in the
Arabic Dialect Identification (ADI) Closed Shared Tasks of the 2018 VarDial
Evaluation Campaign. The proposed approach combines several kernels using
multiple kernel learning. While most of our kernels are based on character
$p$-grams (also known as $n$-grams) extracted from speech or phonetic
transcripts, we also use a kernel based on dialectal embeddings generated from
audio recordings by the organizers. In the learning stage, we independently
employ Kernel Discriminant Analysis (KDA) and Kernel Ridge Regression (KRR).
Preliminary experiments indicate that KRR provides better classification
results. Our approach is shallow and simple, but the empirical results
obtained in the 2018 ADI Closed Shared Task prove that it achieves the best
performance. Furthermore, our top macro-$F_{1}$ score ($58.92\%$) is
significantly better than the second best score ($57.59\%$) in the 2018 ADI
Shared Task, according to the statistical significance test performed by the
organizers. Nevertheless, we obtain even better post-competition results (a
macro-$F_{1}$ score of $62.28\%$) using the audio embeddings released by the
organizers after the competition. With a very similar approach (that did not
include phonetic features), we also ranked first in the ADI Closed Shared
Tasks of the 2017 VarDial Evaluation Campaign, surpassing the second best
method by $4.62\%$. We therefore conclude that our multiple kernel learning
method is the best approach to date for Arabic dialect identification.

00footnotetext: This work is licensed under a Creative Commons Attribution 4.0
International License. License details:
http://creativecommons.org/licenses/by/4.0/.

##  1 Introduction

The 2016 and 2017 VarDial Evaluation Campaigns [Malmasi et al., 2016, Zampieri
et al., 2017] indicate that dialect identification is a challenging NLP task,
actively studied by researchers in nowadays. Based solely on speech
transcripts, the top two Arabic dialect identification (ADI) systems [Ionescu
and Popescu, 2016b, Malmasi and Zampieri, 2016] that participated in the 2016
ADI Shared Task [Malmasi et al., 2016] attained weighted $F_{1}$ scores just
over $50\%$, in a 5-way classification setting. For the 2017 ADI Shared Task
[Zampieri et al., 2017], the organizers provided audio features along with
speech transcripts. The top two systems [Ionescu and Butnaru, 2017, Malmasi
and Zampieri, 2017] were able to reach weighted $F_{1}$ scores above $70\%$ by
using audio features and by including the samples from the development set
into the training set. For the 2018 ADI Shared Task [Zampieri et al., 2018],
the organizers have added phonetic features along with audio features and
speech transcripts. To this end, we present our approach to the 2018 ADI
Shared Task, which is based on adding string kernels computed on phonetic
transcripts to the multiple kernel learning model [Ionescu and Butnaru, 2017]
that we previously designed for the 2017 ADI Shared Task. In the 2018 ADI
Shared Task, the participants had to discriminate between Modern Standard
Arabic (MSA) and four Arabic dialects, in a 5-way classification setting. A
number of $6$ teams have submitted their results on the test set, and our team
(UnibucKernel) ranked on the first place with an accuracy of $58.65\%$ and a
macro-$F_{1}$ score of $58.92\%$.

Our best scoring system in the ADI Shared Task combines several kernels using
multiple kernel learning. The first kernel that we considered is the $p$-grams
presence bits kernel111We computed the $p$-grams presence bits kernel using
the code available at http://string-kernels.herokuapp.com., which takes into
account only the presence of $p$-grams instead of their frequency. The second
kernel is the (histogram) intersection string kernel222We computed the
intersection string kernel using the code available at http://string-
kernels.herokuapp.com., which was first used in a text mining task by ?). The
third kernel is derived from Local Rank Distance (LRD)333We computed the Local
Rank Distance using the code available at http://lrd.herokuapp.com., a
distance measure that was first introduced in computational biology [Ionescu,
2013, Dinu et al., 2014], but it has also shown its application in NLP
[Popescu and Ionescu, 2013, Ionescu, 2015]. These string kernels have been
previously used for Arabic dialect identification from speech transcripts by
?), and they obtained very good results, taking the second place in the 2016
ADI Shared Task [Malmasi et al., 2016]. In this paper, we apply string kernels
on speech transcripts as well as phonetic transcripts, obtaining better
results. While most of our kernels are based on character $p$-grams from
speech or phonetic transcripts, we also use an RBF kernel [Shawe-Taylor and
Cristianini, 2004] based on dialectal embeddings automatically generated from
audio recordings using the approach described in [Shon et al., 2018]. In our
previous work [Ionescu and Butnaru, 2017], we have successfully combined
string kernels computed on speech transcripts with an RBF kernel computed on
audio features and we ranked on the first place in the 2017 ADI Shared Task
[Zampieri et al., 2017]. For the 2018 ADI Shared Task, our multiple kernel
learning method includes string kernels computed on phonetic transcripts along
with the other kernels.

We considered two kernel classifiers [Shawe-Taylor and Cristianini, 2004] for
the learning task, namely Kernel Ridge Regression (KRR) and Kernel
Discriminant Analysis (KDA). In a set of preliminary experiments performed on
the ADI development set, we found that KRR gives slightly better results than
KDA. In the end, we decided to submit results using only KRR. Before
submitting our results, we have also tuned our string kernels for the task.
First of all, we tried out $p$-grams of various lengths, including blended
variants of string kernels as well. Second of all, we evaluated the individual
kernels and various kernel combinations. The empirical results indicate that
string kernels computed on speech transcripts attain significantly better
performance than string kernels computed on phonetic transcripts. When we
combined the string kernels computed on speech transcripts with the kernel
base on audio embeddings, we found that the performance improves by nearly
$5\%$. We obtained another improvement of almost $1\%$ when we included the
string kernels computed on phonetic transcripts. All these choices played an
important role in obtaining the first place in the final ranking of the 2018
ADI Shared Task.

The paper is organized as follows. Work related to Arabic dialect
identification and to methods based on string kernels is presented in Section
2. Section 3 presents the kernels that we used in our approach. The learning
methods employed in the experiments are described in Section 4. Details about
the Arabic dialect identification experiments are provided in Sections 5.
Finally, we draw our conclusion in Section 6.

##  2 Related Work

###  2.1 Arabic Dialect Identification

Arabic dialect identification is a relatively new NLP task with only a handful
of works [Biadsy et al., 2009, Zaidan and Callison-Burch, 2011, Elfardy and
Diab, 2013, Darwish et al., 2014, Zaidan and Callison-Burch, 2014, Malmasi et
al., 2015] to address it before the 2016 VarDial Evaluation Campaign [Malmasi
et al., 2016]. Although it did not received too much attention before 2016,
the task is very important for Arabic NLP tools, as most of these tools have
only been design for Modern Standard Arabic. ?) describe a phonotactic
approach that automatically identifies the Arabic dialect of a speaker given a
sample of speech. While ?) focus on spoken Arabic dialect identification,
others have tried to identify the Arabic dialect of given texts [Zaidan and
Callison-Burch, 2011, Elfardy and Diab, 2013, Darwish et al., 2014, Malmasi et
al., 2015]. ?) introduce the Arabic Online Commentary (AOC) data set of 108K
labeled sentences, $41\%$ of them having dialectal content. They employ a
language model for automatic dialect identification on their collected data. A
supervised approach for sentence-level dialect identification between Egyptian
and MSA is proposed by ?). Their system outperforms the approach presented by
?) on the same data set. ?) extend their previous work [Zaidan and Callison-
Burch, 2011] and conduct several ADI experiments using word and character
$p$-grams. Different from most of the previous work, ?) have found that word
unigram models do not generalize well to unseen topics. They suggest that
lexical, morphological and phonological features can capture more relevant
information for discriminating dialects. As the AOC corpus is not controlled
for topical bias, ?) also state that the models trained on this corpus may not
generalize to other data as they implicitly capture topical cues. They perform
ADI experiments on the Multidialectal Parallel Corpus of Arabic (MPCA)
[Bouamor et al., 2014] using various word and character $p$-grams models in
order to assess the influence of topical bias. Interestingly, ?) find that
character $p$-grams are “in most scenarios the best single feature for this
task”, even in a cross-corpus setting. Their findings are consistent with the
results of ?) in the 2016 ADI Shared Task [Malmasi et al., 2016], as ?) ranked
on the second place using solely character $p$-grams from Automatic Speech
Recognition (ASR) transcripts. The 2017 ADI Shared Task data set [Ali et al.,
2016] contains the original audio files and some low-level audio features,
called i-vectors, along with the ASR transcripts of Arabic speech collected
from the Broadcast News domain. The results of the top systems [Ionescu and
Butnaru, 2017, Malmasi and Zampieri, 2017] in the 2017 ADI Shared Task
[Zampieri et al., 2017] indicate that the audio features produce a much better
performance, probably because there are many ASR errors (perhaps more in the
dialectal speech segments) that make Arabic dialect identification from ASR
transcripts much more difficult. In 2017, ADI has attracted a higher attention
in the scientific community, since researchers have organized three
independent shared tasks [Ali et al., 2017, Rangel et al., 2017, Zampieri et
al., 2017], with $32$ participants in total. For a comprehensive and complete
survey on ADI, we refer the reader to the work of [Jauhiainen et al., 2018].

###  2.2 String Kernels

From the beginning of the 21st century to the present days, methods of
handling text at the character level have demonstrated impressive performance
levels in various text analysis tasks [Lodhi et al., 2002, Sanderson and
Guenter, 2006, Kate and Mooney, 2006, Escalante et al., 2011, Popescu and
Grozea, 2012, Ionescu et al., 2014, Ionescu et al., 2016, Giménez-Pérez et
al., 2017, Popescu et al., 2017, Cozma et al., 2018]. String kernels are a
common form of using information at the character level. They are a particular
case of the more general convolution kernels [Haussler, 1999]. ?) used string
kernels for document categorization with very good results. String kernels
were also successfully used in authorship identification [Sanderson and
Guenter, 2006, Popescu and Grozea, 2012]. For example, the system described by
?) ranked first in most problems and overall in the PAN 2012 Traditional
Authorship Attribution tasks. More recently, various blended string kernels
reached state-of-the-art accuracy rates for native language identification
[Ionescu et al., 2016, Ionescu and Popescu, 2017], Arabic dialect
identification [Ionescu and Popescu, 2016b, Ionescu and Butnaru, 2017],
polarity classification [Giménez-Pérez et al., 2017, Popescu et al., 2017] and
automatic essay scoring [Cozma et al., 2018].

##  3 Kernels for Arabic Dialect Identification

###  3.1 String Kernels

Kernel functions [Shawe-Taylor and Cristianini, 2004] capture the intuitive
notion of similarity between objects in a specific domain. For strings, many
such kernel functions exist with various applications in computational biology
and computational linguistics. String kernels embed the texts in a very large
feature space, given by all the substrings of length $p$, and leave the job of
selecting important (discriminative) features for the specific classification
task to the learning algorithm, which assigns higher weights to the important
features (character $p$-grams). Perhaps one of the most natural ways to
measure the similarity of two strings is to count how many substrings of
length $p$ the two strings have in common. This gives rise to the $p$-spectrum
kernel. Formally, for two strings over an alphabet $\Sigma$,
$s,t\in\Sigma^{*}$, the $p$-spectrum kernel is defined as:

$\begin{split}k_{p}(s,t)=\sum\limits_{v\in\Sigma^{p}}\mbox{num}_{v}(s)\cdot\mbox{num}_{v}(t),\end{split}$

where $\mbox{num}_{v}(s)$ is the number of occurrences of string $v$ as a
substring in $s$.444The notion of substring requires contiguity. ?) discuss
the ambiguity between the terms _substring_ and _subsequence_ across different
domains: biology, computer science. The feature map defined by this kernel
associates to each string a vector of dimension $|\Sigma|^{p}$ containing the
histogram of frequencies of all its substrings of length $p$ ($p$-grams). A
variant of this kernel can be obtained if the embedding feature map is
modified to associate to each string a vector of dimension $|\Sigma|^{p}$
containing the presence bits (instead of frequencies) of all its substrings of
length $p$. Thus, the character $p$-grams presence bits kernel is obtained:

$\begin{split}k^{0/1}_{p}(s,t)=\sum\limits_{v\in\Sigma^{p}}\mbox{in}_{v}(s)\cdot\mbox{in}_{v}(t),\end{split}$

where $\mbox{in}_{v}(s)$ is $1$ if string $v$ occurs as a substring in $s$,
and $0$ otherwise.

In computer vision, the (histogram) intersection kernel has successfully been
used for object class recognition from images [Maji et al., 2008, Vedaldi and
Zisserman, 2010]. ?) have used the intersection kernel as a kernel for
strings, in the context of native language identification. The intersection
string kernel is defined as follows:

$\begin{split}k^{\cap}_{p}(s,t)=\sum\limits_{v\in\Sigma^{p}}\min\\{\mbox{num}_{v}(s),\mbox{num}_{v}(t)\\}.\end{split}$

For the $p$-spectrum kernel, the frequency of a $p$-gram has a very
significant contribution to the kernel, since it considers the product of such
frequencies. On the other hand, the frequency of a $p$-gram is completely
disregarded in the $p$-grams presence bits kernel. The intersection kernel
lies somewhere in the middle between the $p$-grams presence bits kernel and
the $p$-spectrum kernel, in the sense that the frequency of a $p$-gram has a
moderate contribution to the intersection kernel. In other words, the
intersection kernel assigns a high score to a $p$-gram only if it has a high
frequency in both strings, since it considers the minimum of the two
frequencies. The $p$-spectrum kernel assigns a high score even when the
$p$-gram has a high frequency in only one of the two strings. Thus, the
intersection kernel captures something more about the correlation between the
$p$-gram frequencies in the two strings. Based on these comments, we decided
to use only the $p$-grams presence bits kernel and the intersection string
kernel in the ADI experiments.

Data normalization helps to improve machine learning performance for various
applications. Since the value range of raw data can have large variations,
classifier objective functions will not work properly without normalization.
After normalization, each feature has an approximately equal contribution to
the similarity between two samples. To obtain a normalized kernel matrix of
pairwise similarities between samples, each component is divided by the square
root of the product of the two corresponding diagonal components:

$\begin{split}\hat{K}_{ij}=\frac{K_{ij}}{\sqrt{K_{ii}\cdot
K_{jj}}}.\end{split}$

To ensure a fair comparison among strings of different lengths, we use
normalized versions of the $p$-grams presence bits kernel and the intersection
kernel in our experiments. Taking into account $p$-grams of different lengths
and summing up the corresponding kernels, new kernels, termed _blended
spectrum kernels_ , can be obtained. We have used various blended spectrum
kernels in the ADI experiments in order to find the best combination. It is
important to mention that we applied the blended $p$-grams presence bits
kernel and the blended intersection kernel on both speech transcripts and
phonetic transcripts.

###  3.2 Kernel based on Local Rank Distance

Local Rank Distance [Ionescu, 2013] is a recently introduced distance that
measures the non-alignment score between two strings. It has already shown
promising results in computational biology [Ionescu, 2013, Dinu et al., 2014]
and native language identification [Popescu and Ionescu, 2013, Ionescu, 2015].

In order to describe LRD, we use the following notations. Given a string $x$
over an alphabet $\Sigma$, the length of $x$ is denoted by $|x|$. Strings are
considered to be indexed starting from position $1$, that is $x=x[1]x[2]\cdots
x[|x|]$. Moreover, $x[i:j]$ denotes its substring $x[i]x[i+1]\cdots x[j-1]$.
Given a fixed integer $p\geq 1$, a threshold $m\geq 1$, and two strings $x$
and $y$ over $\Sigma$, the _Local Rank Distance_ between $x$ and $y$, denoted
by $\Delta_{LRD}(x,y)$, is defined through the following algorithmic process.
For each position $i$ in $x$ ($1\leq i\leq|x|-p+1$), the algorithm searches
for that position $j$ in $y$ ($1\leq j\leq|y|-p+1$) such that
$x[i:i+p]=y[j:j+p]$ and $|i-j|$ is minimized. If $j$ exists and $|i-j|<m$,
then the offset $|i-j|$ is added to the Local Rank Distance. Otherwise, the
maximal offset $m$ is added to the Local Rank Distance. LRD is focused on the
local phenomenon, and tries to pair identical $p$-grams at a minimum offset.
To ensure that LRD is a (symmetric) distance function, the algorithm also has
to sum up the offsets obtained from the above process by exchanging $x$ and
$y$. LRD is formally defined in [Ionescu, 2013, Dinu et al., 2014, Ionescu and
Popescu, 2016a].

The search for matching $p$-grams is limited within a window of fixed size.
The size of this window is determined by the maximum offset parameter $m$. We
set $m=300$ in our experiments, which is larger than the maximum length of the
ASR transcripts provided in the training set. In the experiments, the
efficient algorithm of ?) is used to compute LRD. However, LRD needs to be
used as a kernel function. We use the RBF kernel [Shawe-Taylor and
Cristianini, 2004] to transform LRD into a similarity measure:

$\hat{k}^{LRD}_{p}(s,t)=exp\left(-\frac{\displaystyle\Delta_{LRD}(s,t)}{\displaystyle
2\sigma^{2}}\right),$

where $s$ and $t$ are two strings and $p$ is the $p$-grams length. The
parameter $\sigma$ is usually chosen so that values of $\hat{k}(s,t)$ are well
scaled. We have tuned $\sigma$ in a set of preliminary experiments. In the
above equation, $\Delta_{LRD}$ is already normalized to a value in the $[0,1]$
interval to ensure a fair comparison of strings of different length. The
resulted similarity matrix is then squared, i.e. $K=K\cdot K^{\prime}$, to
ensure that it becomes a symmetric and positive definite kernel matrix. Due to
time constraints, we applied the kernel based on Local Rank Distance only on
speech transcripts.

###  3.3 Kernel based on Audio Features

Along with the string kernels, we also build a kernel from the audio
embeddings provided with the data set [Shon et al., 2018]. The dialectal
embeddings are generated by training convolutional neural networks on audio
recordings, as described in [Shon et al., 2018, Najafian et al., 2018]. The
provided embeddings have $600$ dimensions. In order to build a kernel from the
audio embeddings, we first compute the Euclidean distance between each pair of
embedding vectors. We then employ the RBF kernel to transform the distance
into a similarity measure:

$\hat{k}_{\textit{audio}}(x,y)=exp\left(-\frac{\sqrt{\sum^{m}_{j=1}(x_{j}-y_{j})^{2}}}{2\sigma^{2}}\right),$

where $x$ and $y$ are two audio embedding vectors and $m$ represents the size
of the two embedding vectors, $600$ in our case. For optimal results, we have
tuned the parameter $\sigma$ in a set of preliminary experiments. As for the
LRD kernel, we square the kernel matrix of the kernel based on audio
embeddings.

##  4 Learning Methods

Kernel-based learning algorithms work by embedding the data into a Hilbert
feature space and by searching for linear relations in that space. The
embedding is performed implicitly, by specifying the inner product between
each pair of points rather than by giving their coordinates explicitly. More
precisely, a kernel matrix that contains the pairwise similarities between
every pair of training samples is used in the learning stage to assign a
vector of weights to the training samples. Let $\alpha$ denote this weight
vector. In the test stage, the pairwise similarities between a test sample $x$
and all the training samples are computed. Then, the following binary
classification function assigns a positive or a negative label to the test
sample:

$\begin{split}g(x)=\sum_{i=1}^{n}\alpha_{i}\cdot k(x,x_{i}),\end{split}$

where $x$ is the test sample, $n$ is the number of training samples,
$X=\\{x_{1},x_{2},...,x_{n}\\}$ is the set of training samples, $k$ is a
kernel function, and $\alpha_{i}$ is the weight assigned to the training
sample $x_{i}$.

The advantage of using the dual representation induced by the kernel function
becomes clear if the dimension of the feature space $m$ is taken into
consideration. Since string kernels are based on character $p$-grams, the
feature space is indeed very high. For instance, using $5$-grams based only on
the $28$ letters of the basic Arabic alphabet will result in a feature space
of $28^{5}=17,210,368$ features. However, our best kernels are based on a
feature space that includes $3$-grams, $4$-grams, $5$-grams and $6$-grams. As
long as the number of samples $n$ is much lower than the number of features
$m$, it can be more efficient to use the dual representation given by the
kernel matrix. This fact is also known as the _kernel trick_ [Shawe-Taylor and
Cristianini, 2004].

Various kernel methods differ in the way they learn to separate the samples.
In the case of binary classification problems, kernel-based learning
algorithms look for a discriminant function, a function that assigns $+1$ to
examples belonging to one class and $-1$ to examples belonging to the other
class. In the ADI experiments, we used the Kernel Ridge Regression (KRR)
binary classifier. Kernel Ridge Regression selects the vector of weights that
simultaneously has small empirical error and small norm in the Reproducing
Kernel Hilbert Space generated by the kernel function. KRR is a binary
classifier, but Arabic dialect identification is a multi-class classification
problem. There are many approaches for combining binary classifiers to solve
multi-class problems. Typically, the multi-class problem is broken down into
multiple binary classification problems using common decomposition schemes
such as: one-versus-all and one-versus-one. We considered the one-versus-all
scheme for our Arabic dialect classification task. There are also kernel
methods that take the multi-class nature of the problem directly into account,
for instance Kernel Discriminant Analysis. The KDA classifier is sometimes
able to improve accuracy by avoiding the masking problem [Hastie and
Tibshirani, 2003]. More details about KRR and KDA are given in [Shawe-Taylor
and Cristianini, 2004].

##  5 Experiments on Arabic Dialects

###  5.1 Data Set

The 2018 ADI Shared Task data set [Ali et al., 2016] contains audio
recordings, ASR transcripts and phonetic transcripts of Arabic speech
collected from the Broadcast News domain. The task is to discriminate between
Modern Standard Arabic (MSA) and four Arabic dialects, namely Egyptian (EGY),
Gulf (GLF), Levantine (LAV), and North-African or Maghrebi (NOR). Although the
data set is similar to those used in the 2016 and the 2017 ADI Shared Tasks
[Malmasi et al., 2016, Zampieri et al., 2017], this year the organizers
provided phonetic transcripts produced by four non-Arabic automatic phoneme
recognizers (Czech, English, Hungarian and Russian), which perform long
temporal phoneme recognition and have been previously shown to be useful for
discriminating between the dialects of various languages.

###  5.2 Parameter and System Choices

In our approach, we treat both ASR transcripts and phonetic transcripts as
strings. Because the approach works at the character level, there is no need
to split the texts into tokens, or to do any NLP-specific processing before
computing the string kernels. The only editing done to the transcripts was the
replacing of sequences of consecutive space characters (space, tab, and so on)
with a single space character. This normalization was needed in order to
prevent the artificial increase or decrease of the similarity between texts,
as a result of different spacing.

Kernel | Input | Range of $\mathbf{p}$-grams | Accuracy | Macro-$\mathbf{F_{1}}$
---|---|---|---|---
$\hat{k}^{0/1}$ | Speech transcripts |  $3$-$6$ | $54.85\%$ | $53.94\%$
$\hat{k}^{\cap}$ | Speech transcripts |  $3$-$6$ | $54.53\%$ | $53.77\%$
$\hat{k}^{LRD}$ | Speech transcripts |  $3$-$6$ | $51.09\%$ | $50.15\%$
$\hat{k}^{0/1}$ | Czech phonetic transcripts |  $3$-$6$ | $39.14\%$ | $39.43\%$
$\hat{k}^{\cap}$ | Czech phonetic transcripts |  $3$-$4$ | $39.08\%$ | $38.52\%$
$\hat{k}^{0/1}$ | English phonetic transcripts |  $9$-$10$ | $31.42\%$ | $30.49\%$
$\hat{k}^{\cap}$ | English phonetic transcripts |  $9$-$11$ | $31.36\%$ | $30.47\%$
$\hat{k}^{0/1}$ | Hungarian phonetic transcripts |  $3$-$5$ | $39.78\%$ | $39.40\%$
$\hat{k}^{\cap}$ | Hungarian phonetic transcripts |  $3$-$5$ | $40.36\%$ | $40.39\%$
$\hat{k}^{0/1}$ | Russian phonetic transcripts |  $3$-$5$ | $36.08\%$ | $36.28\%$
$\hat{k}^{\cap}$ | Russian phonetic transcripts |  $3$-$4$ | $38.19\%$ | $38.04\%$
Table 1: Optimal ranges of $p$-grams and corresponding results for each string
kernel and each input type on the development set of the ADI Shared Task. All
results are obtained using KRR as classifier.

In order to tune the parameters and find the best system choices, we used the
development set. We first carried out a set of preliminary experiments to
determine the optimal range of $p$-grams for each string kernel and each type
of input, i.e. speech transcripts or phonetic transcripts in four languages.
We fixed the learning method to KRR and we evaluated all the $p$-grams in the
range $2$-$12$. The optimal range of $p$-grams and the associated accuracy and
macro-$F_{1}$ score for each kernel and each input is presented in Table 1. In
most cases, it seems that the optimal range of $p$-grams is $3$-$5$ or
$3$-$6$. An exception is the range of $p$-grams that provides the best results
on English phonetic transcripts. Regarding the input type, it is clear that
string kernels provide better results when they are applied on speech
transcripts. With an accuracy of $54.85\%$ and a macro-$F_{1}$ score of
$53.94\%$, the best individual kernel on the development set is the blended
presence bits kernel ($\hat{k}^{0/1}$) computed on speech transcripts. On the
other hand, the best kernel computed on (Hungarian) phonetic transcripts is
the blended intersection kernel ($\hat{k}^{\cap}$), which obtains an accuracy
of $40.36\%$ and a macro-$F_{1}$ score of $40.39\%$.

Kernels | Input | Accuracy | Macro-$\mathbf{F_{1}}$
---|---|---|---
$\hat{k}_{speech}=\hat{k}^{0/1}_{3-6}+\hat{k}^{\cap}_{3-6}+\hat{k}^{LRD}_{3-6}$ | Speech transcripts | $55.17\%$ | $54.72\%$
$\hat{k}_{CZ}=\hat{k}^{0/1}_{3-6}+\hat{k}^{\cap}_{3-4}$ | Czech phonetic transcripts | $39.72\%$ | $39.71\%$
$\hat{k}_{EN}=\hat{k}^{0/1}_{9-10}+\hat{k}^{\cap}_{9-11}$ | English phonetic transcripts | $31.42\%$ | $30.54\%$
$\hat{k}_{HU}=\hat{k}^{0/1}_{3-5}+\hat{k}^{\cap}_{3-5}$ | Hungarian phonetic transcripts | $41.06\%$ | $40.85\%$
$\hat{k}_{RU}=\hat{k}^{0/1}_{3-5}+\hat{k}^{\cap}_{3-4}$ | Russian phonetic transcripts | $38.38\%$ | $37.75\%$
$\hat{k}_{phonetic}=\hat{k}_{CZ}+\hat{k}_{EN}+\hat{k}_{HU}+\hat{k}_{RU}$ | All phonetic transcripts | $45.02\%$ | $45.06\%$
$\hat{k}_{\textit{audio}}$ | Audio embeddings | $52.87\%$ | $52.72\%$
Table 2: Results of best kernel combinations for each input type on the
development set of the ADI Shared Task. All results are obtained using KRR as
classifier.

After determining the optimal range of $p$-grams for each kernel and input
pair, we conducted further experiments by combining the kernels for each type
of input. When multiple kernels are combined, the features are actually
embedded in a higher-dimensional space. As a consequence, the search space of
linear patterns grows, which helps the classifier to select a better
discriminant function. We adopt the most natural way of combining two or more
kernels, namely we simply sum up the corresponding kernels. The process of
summing up kernels or kernel matrices is equivalent to feature vector
concatenation. The results of kernel combinations for each input type are
presented in Table 2. For the phonetic transcripts, we tried out kernel
combinations for each non-Arabic phoneme recognizer, as well as a kernel
combination on all phonetic transcripts. Compared to the individual
components, we observed the highest improvement when we combined all string
kernels based on phonetic transcripts. Indeed, the best combination (presented
in Table 2) using only phonetic transcripts as input reaches an accuracy of
$45.02\%$ and a macro-$F_{1}$ score of $45.06\%$, while the best individual
kernel (presented in Table 1) applied over phonetic transcripts reaches an
accuracy of $40.36\%$ and a macro-$F_{1}$ score of $40.39\%$. For the speech
transcripts, the kernel combination is better than each individual component,
but the performance gain is not as high as in the case of phonetic
transcripts. For the audio recordings, we used only a single kernel based on
audio embeddings ($\hat{k}_{\textit{audio}}$). We tuned the parameter $\sigma$
of the RBF kernel based on audio embeddings, and the best option seems to be
$\sigma=1$, which produces an accuracy of $52.87\%$ and a macro-$F_{1}$ score
of $52.72\%$.

Kernels | KRR | KDA
---|---|---
| Accuracy | Macro-$\mathbf{F_{1}}$ | Accuracy | Macro-$\mathbf{F_{1}}$
$\hat{k}_{speech}+\hat{k}_{\textit{audio}}$ [Ionescu and Butnaru, 2017] | $59.52\%$ | $59.12\%$ | $58.05\%$ | $58.13\%$
$\hat{k}_{speech}+\hat{k}_{\textit{audio}}+\hat{k}_{phonetic}$ | $60.66\%$ | $60.46\%$ | $58.94\%$ | $59.20\%$
Table 3: Accuracy rates and macro-$F_{1}$ scores of various kernels combined
across different input types: audio recordings, speech transcripts and
phonetic transcripts. Both KRR and KDA are alternatively employed for the
learning task. The results are obtained on the ADI development set.

Since we obtained different kernel representations from speech transcripts,
phonetic transcripts and audio recordings, a good approach for improving the
performance is to further combine the best kernel combinations in order to
obtain a multiple kernel learning approach that benefits from all three types
of input formats (audio embeddings, speech transcripts and phonetic
transcripts). The results of our multiple kernel learning method on the
development set are reported in Table 3. It is important to note that, in
Table 3, we included the results of the multiple kernel learning approach
[Ionescu and Butnaru, 2017] that ranked first the 2017 ADI Shared Task, as
reference. We notice that the string kernels computed on phonetic features
help to improve the performance over the last year’s winning approach by
almost $1\%$. We also note that the combination of string kernels computed on
speech transcripts ($\hat{k}_{speech}$) and the kernel based on audio
embeddings ($\hat{k}_{\textit{audio}}$) improves the accuracy of the
individual components by more than $4\%$. Indeed, the kernel combination that
includes $\hat{k}_{speech}$ and $\hat{k}_{\textit{audio}}$ attains an accuracy
of $59.52\%$ and a macro-$F_{1}$ score of $59.12\%$ when KRR is employed for
the learning task, while the better kernel component ($\hat{k}_{speech}$)
reaches an accuracy of $55.17\%$ and a macro-$F_{1}$ score of $54.72\%$. Among
the two kernel classifiers, it seems that KRR attains slightly better results
than KDA. In fact, KRR is the only classifier that surpasses the $60\%$
performance threshold on the development set. This happens when the string
kernels computed on phonetic features ($\hat{k}_{phonetic}$) are included in
the multiple kernel learning framework. We note that, in all the experiments
performed on the development set, KRR yields the best results when we use a
regularization parameter of $10^{-3}$. In the end, we decided to submit three
runs for final evaluation on the test set. All submissions are based on the
KRR classifier. The first submission (run 1) is based on the sum of
$\hat{k}_{speech}$, $\hat{k}_{\textit{audio}}$ and $\hat{k}_{phonetic}$. The
second submission (run 2) is almost identical to the first submission, except
that we replaced the squared versions of $\hat{k}^{LRD}_{3-6}$ and
$\hat{k}_{\textit{audio}}$ with non-squared versions. Since all the submitted
models are trained on both the provided training and development sets, we
considered that KRR might provide better results if we choose a lower
regularization parameter. Hence, the third submission (run 3) is also similar
to the first submission, the only difference being that we changed the
regularization parameter of KRR from $10^{-3}$ to $10^{-4}$.

###  5.3 Results on the 2018 ADI Test Set

System | Accuracy | Macro-$\mathbf{F_{1}}$
---|---|---
Random Baseline | - | $19.95\%$
Run 1 | $\mathbf{58.65\%}$ | $\mathbf{58.92\%}$
Run 2 | $54.50\%$ | $54.91\%$
Run 3 | $58.36\%$ | $58.55\%$
Run 4 (post-competition) | $62.15\%$ | $62.02\%$
Run 5 (post-competition) | $\mathbf{62.22\%}$ | $\mathbf{62.28\%}$
Table 4: Results on the test set of the 2018 ADI Shared Task (closed training)
of our multiple kernel learning method based on KRR versus a random baseline.
The best results during and after the competition are highlighted in bold.

Table 4 presents our results for the Arabic Dialect Identification Closed
Shared Task of the 2018 VarDial Evaluation Campaign. Among the submitted
systems, the best performance is obtained when the KRR regularization
parameter is set to $10^{-3}$ and the kernel combination includes squared
versions of $\hat{k}^{LRD}_{3-6}$ and $\hat{k}_{\textit{audio}}$. The
submitted systems were ranked by their macro-$F_{1}$ scores, and among the $6$
participants, our best model obtained the first place with a macro-$F_{1}$
score of $58.92\%$. Remarkably, the statistical significance tests performed
by the organizers indicate that our best system is significantly better than
the system that ranked on the second place with a macro-$F_{1}$ score of
$57.59\%$.

Figure 1: Confusion matrix (on the test set) of KRR based on the sum of
$\hat{k}_{speech}$, $\hat{k}_{\textit{audio}}$ and $\hat{k}_{phonetic}$ (run
1). Best viewed in color.

The confusion matrix for our best model is presented in Figure 1. The
confusion matrix reveals that our system wrongly predicted more than $400$
examples of the Levantine dialect as part of the Maghrebi dialect.
Furthermore, it has some difficulties in distinguishing the Levantine dialect
from the Egyptian dialect on one hand, and the Egyptian dialect from the
Maghrebi dialect on the other hand. Overall, the results look good, as the
main diagonal scores dominate the other matrix components.

After the competition ended, the organizers released a new set of audio
embeddings that are computed on both the training and the development sets. By
replacing the audio embeddings released during the competition with the new
embeddings (run 4), we obtained results that are more than $3\%$ better than
out top system (run 1) during the competition. We also tried to include both
embeddings based on audio features (run 5) into our multiple kernel learning
approach, resulting in a slight improvement. The results of our post-
competition runs 4 and 5 are reported in Table 4. Our best post-competition
results are an accuracy of $62.22\%$ and a macro-$F_{1}$ score of $62.28\%$,
obtained by run 5.

##  6 Conclusion

In this paper, we presented an approach based on learning with multiple
kernels for the ADI Shared Tasks of the 2018 VarDial Evaluation Campaign
[Zampieri et al., 2018]. Our approach attained very good results, as our team
(UnibucKernel) ranked on the first place in the 2018 ADI Shared Task. The fact
that we obtained the first place for the second year in a row indicates that
our multiple kernel learning method did not reach the top performance simply
by chance. We therefore conclude that the approach of combining multiple
kernels based on different kinds of input, i.e. audio recordings, speech
transcripts and phonetic transcripts, provides state-of-the-art performance in
Arabic dialect identification. Since most of our kernels are based on
character $p$-grams, we can also conclude that character $p$-grams represent
the best feature set for the ADI task.

## References

  * [Ali et al., 2016]  Ahmed Ali, Najim Dehak, Patrick Cardinal, Sameer Khurana, Sree Harsha Yella, James Glass, Peter Bell, and Steve Renals.  2016\.  Automatic dialect detection in arabic broadcast speech.  In Proceedings of Interspeech, pages 2934–2938.
  * [Ali et al., 2017]  Ahmed Ali, Stephan Vogel, and Steve Renals.  2017\.  Speech Recognition Challenge in the Wild: Arabic MGB-3.  arXiv preprint arXiv:1709.07276.
  * [Biadsy et al., 2009]  Fadi Biadsy, Julia Hirschberg, and Nizar Habash.  2009\.  Spoken Arabic Dialect Identification Using Phonotactic Modeling.  In Proceedings of the EACL 2009 Workshop on Computational Approaches to Semitic Languages, pages 53–61, Stroudsburg, PA, USA. Association for Computational Linguistics.
  * [Bouamor et al., 2014]  Houda Bouamor, Nizar Habash, and Kemal Oflazer.  2014\.  A Multidialectal Parallel Corpus of Arabic.  In Proceedings of LREC, pages 1240–1245. European Language Resources Association (ELRA), May.
  * [Cozma et al., 2018]  Mădălina Cozma, Andrei Butnaru, and Radu Tudor Ionescu.  2018\.  Automated essay scoring with string kernels and word embeddings.  In Proceedings of ACL.
  * [Darwish et al., 2014]  Kareem Darwish, Hassan Sajjad, and Hamdy Mubarak.  2014\.  Verifiably Effective Arabic Dialect Identification.  In Proceedings of EMNLP, pages 1465–1468. ACL.
  * [Dinu et al., 2014]  Liviu P. Dinu, Radu Tudor Ionescu, and Alexandru I. Tomescu.  2014\.  A rank-based sequence aligner with applications in phylogenetic analysis.  PLoS ONE, 9(8):e104006, 08.
  * [Elfardy and Diab, 2013]  Heba Elfardy and Mona T. Diab.  2013\.  Sentence Level Dialect Identification in Arabic.  In Proceedings of ACL, pages 456–461. Association for Computer Linguistics.
  * [Escalante et al., 2011]  Hugo Jair Escalante, Thamar Solorio, and Manuel Montes-y-Gómez.  2011\.  Local Histograms of Character N-grams for Authorship Attribution.  In Proceedings of ACL: HLT, volume 1, pages 288–298.
  * [Giménez-Pérez et al., 2017]  Rosa M. Giménez-Pérez, Marc Franco-Salvador, and Paolo Rosso.  2017\.  Single and Cross-domain Polarity Classification using String Kernels.  In Proceedings of EACL, pages 558–563, April.
  * [Hastie and Tibshirani, 2003]  Trevor Hastie and Robert Tibshirani.  2003\.  The Elements of Statistical Learning.  Springer, corrected edition, July.
  * [Haussler, 1999]  David Haussler.  1999\.  Convolution Kernels on Discrete Structures.  Technical Report UCS-CRL-99-10, University of California at Santa Cruz, Santa Cruz, CA, USA.
  * [Ionescu and Butnaru, 2017]  Radu Tudor Ionescu and Andrei Butnaru.  2017\.  Learning to Identify Arabic and German Dialects using Multiple Kernels.  In Proceedings of VarDial Workshop of EACL, pages 200–209.
  * [Ionescu and Popescu, 2016a]  Radu Tudor Ionescu and Marius Popescu.  2016a.  Knowledge Transfer between Computer Vision and Text Mining.  Advances in Computer Vision and Pattern Recognition. Springer International Publishing.
  * [Ionescu and Popescu, 2016b]  Radu Tudor Ionescu and Marius Popescu.  2016b.  UnibucKernel: An Approach for Arabic Dialect Identification based on Multiple String Kernels.  In Proceedings of VarDial Workshop of COLING, pages 135–144.
  * [Ionescu and Popescu, 2017]  Radu Tudor Ionescu and Marius Popescu.  2017\.  Can string kernels pass the test of time in native language identification?  In Proceedings of BEA-12 Workshop of EMNLP, pages 224–234.
  * [Ionescu et al., 2014]  Radu Tudor Ionescu, Marius Popescu, and Aoife Cahill.  2014\.  Can characters reveal your native language? A language-independent approach to native language identification.  In Proceedings of EMNLP, pages 1363–1373. Association for Computational Linguistics, October.
  * [Ionescu et al., 2016]  Radu Tudor Ionescu, Marius Popescu, and Aoife Cahill.  2016\.  String kernels for native language identification: Insights from behind the curtains.  Computational Linguistics, 42(3):491–525.
  * [Ionescu, 2013]  Radu Tudor Ionescu.  2013\.  Local Rank Distance.  In Proceedings of SYNASC, pages 221–228, Timisoara, Romania. IEEE Computer Society.
  * [Ionescu, 2015]  Radu Tudor Ionescu.  2015\.  A Fast Algorithm for Local Rank Distance: Application to Arabic Native Language Identification.  In Proceedings of ICONIP, volume 9490, pages 390–400. Springer LNCS.
  * [Jauhiainen et al., 2018]  Tommi Jauhiainen, Marco Lui, Marcos Zampieri, Timothy Baldwin, and Krister Lindén.  2018\.  Automatic language identification in texts: A survey.  arXiv preprint arXiv:1804.08186.
  * [Kate and Mooney, 2006]  Rohit J. Kate and Raymond J. Mooney.  2006\.  Using String-kernels for Learning Semantic Parsers.  In Proceedings of ACL, pages 913–920, Stroudsburg, PA, USA. Association for Computational Linguistics.
  * [Lodhi et al., 2002]  Huma Lodhi, Craig Saunders, John Shawe-Taylor, Nello Cristianini, and Christopher J. C. H. Watkins.  2002\.  Text Classification using String Kernels.  Journal of Machine Learning Research, 2:419–444.
  * [Maji et al., 2008]  Subhransu Maji, Alexander C. Berg, and Jitendra Malik.  2008\.  Classification using intersection kernel support vector machines is efficient.  In Proceedings of CVPR, pages 1–8. IEEE Computer Society.
  * [Malmasi and Zampieri, 2016]  Shervin Malmasi and Marcos Zampieri.  2016\.  Arabic Dialect Identification in Speech Transcripts.  In Proceedings of VarDial Workshop of COLING, pages 106–113. ACL Anthology.
  * [Malmasi and Zampieri, 2017]  Shervin Malmasi and Marcos Zampieri.  2017\.  Arabic Dialect Identification Using iVectors and ASR Transcripts.  In Proceedings of VarDial Workshop of EACL, pages 178–183, Valencia, Spain, April.
  * [Malmasi et al., 2015]  Shervin Malmasi, Eshrag Refaee, and Mark Dras.  2015\.  Arabic Dialect Identification using a Parallel Multidialectal Corpus.  In Proceedings of PACLING, pages 209–217, Bali, Indonesia, May.
  * [Malmasi et al., 2016]  Shervin Malmasi, Marcos Zampieri, Nikola Ljubešić, Preslav Nakov, Ahmed Ali, and Jörg Tiedemann.  2016\.  Discriminating between Similar Languages and Arabic Dialect Identification: A Report on the Third DSL Shared Task.  In Proceedings of VarDial Workshop of COLING, Osaka, Japan.
  * [Najafian et al., 2018]  Maryam Najafian, Sameer Khurana, Suwon Shon, Ahmed Ali, and James Glass.  2018\.  Exploiting convolutional neural networks for phonotactic based dialect identification.  In Proceedings of ICASSP, pages 5174–5175.
  * [Popescu and Grozea, 2012]  Marius Popescu and Cristian Grozea.  2012\.  Kernel methods and string kernels for authorship analysis.  In Pamela Forner, Jussi Karlgren, and Christa Womser-Hacker, editors, CLEF (Online Working Notes/Labs/Workshop), Rome, Italy, September.
  * [Popescu and Ionescu, 2013]  Marius Popescu and Radu Tudor Ionescu.  2013\.  The Story of the Characters, the DNA and the Native Language.  In Proceedings of BEA-8 Workshop of NAACL, pages 270–278, Atlanta, Georgia, June. Association for Computational Linguistics.
  * [Popescu et al., 2017]  Marius Popescu, Cristian Grozea, and Radu Tudor Ionescu.  2017\.  HASKER: An efficient algorithm for string kernels. Application to polarity classification in various languages.  In Proceedings of KES, pages 1755–1763.
  * [Rangel et al., 2017]  Francisco Rangel, Paolo Rosso, Martin Potthast, and Benno Stein.  2017\.  Overview of the 5th author profiling task at pan 2017: Gender and language variety identification in twitter.  Working Notes Papers of the CLEF.
  * [Sanderson and Guenter, 2006]  Conrad Sanderson and Simon Guenter.  2006\.  Short text authorship attribution via sequence kernels, markov chains and author unmasking: An investigation.  In Proceedings of EMNLP, pages 482–491, Sydney, Australia, July. Association for Computational Linguistics.
  * [Shawe-Taylor and Cristianini, 2004]  John Shawe-Taylor and Nello Cristianini.  2004\.  Kernel Methods for Pattern Analysis.  Cambridge University Press.
  * [Shon et al., 2018]  Suwon Shon, Ahmed Ali, and James Glass.  2018\.  Convolutional Neural Networks and Language Embeddings for End-to-End Dialect Recognition.  In Proceedings of Odyssey.
  * [Vedaldi and Zisserman, 2010]  Andrea Vedaldi and Andrew Zisserman.  2010\.  Efficient additive kernels via explicit feature maps.  In Proceedings of CVPR, pages 3539–3546, San Francisco, CA, USA. IEEE Computer Society.
  * [Zaidan and Callison-Burch, 2011]  Omar F. Zaidan and Chris Callison-Burch.  2011\.  The Arabic Online Commentary Dataset: An Annotated Dataset of Informal Arabic with High Dialectal Content.  In Proceedings of ACL: HLT, volume 2, pages 37–41, Stroudsburg, PA, USA. Association for Computational Linguistics.
  * [Zaidan and Callison-Burch, 2014]  Omar F. Zaidan and Chris Callison-Burch.  2014\.  Arabic dialect identification.  Computational Linguistics, 40(1):171–202.
  * [Zampieri et al., 2017]  Marcos Zampieri, Shervin Malmasi, Nikola Ljubešić, Preslav Nakov, Ahmed Ali, Jörg Tiedemann, Yves Scherrer, and Noëmi Aepli.  2017\.  Findings of the VarDial Evaluation Campaign 2017.  In Proceedings of VarDial Workshop of EACL, Valencia, Spain.
  * [Zampieri et al., 2018]  Marcos Zampieri, Shervin Malmasi, Preslav Nakov, Ahmed Ali, Suwon Shon, James Glass, Yves Scherrer, Tanja Samardžić, Nikola Ljubešić, Jörg Tiedemann, Chris van der Lee, Stefan Grondelaers, Nelleke Oostdijk, Antal van den Bosch, Ritesh Kumar, Bornini Lahiri, and Mayank Jain.  2018\.  Language Identification and Morphosyntactic Tagging: The Second VarDial Evaluation Campaign.  In Proceedings of VarDial Workshop of COLING, Santa Fe, USA.