Jacek Cichoń

Rafał Kapelko

Marek Klonowski

On the Dynamics of Systems of Urns *

Keywords: urn and balls model, mix networks, Coupon Collector Problem

In this paper we present an analysis of some generalization of the classic urn and balls model. In our model each urn has a fixed capacity and initially is filled with white balls. Black balls are added to the system of connected urns and gradually displace white balls. We show a general form of formulas for the expected numbers of black balls in a given urn and we analyze some special cases (parallel and serial configurations). We are mainly interested in a counterpart of the Coupon Collector Problem for the model considered.

The primary motivation for our research is the formal analysis of the mix networks (introduced by D. Chaum) and its immunity to so-called flooding (blending) attacks.

Introduction

In this paper we investigate the following process. We have a finite directed acyclic (i.e. without directed cycles) graph G = (V, E); we also have a family of urns (U a ) a∈V indexed by nodes of G. Each urn contains some number of balls of two kinds -let us say, black and white balls. Initially, each urn contains only white balls. We say that a node a ∈ V is a source node if there is no b ∈ V such that (b, a) ∈ E. Similarly, a node a ∈ V is a sink node if there is no b ∈ V such that (a, b) ∈ E. At each round (enumerated by natural numbers), 1. we choose a random path v 0 , . . . , v k from a source to a sink, 2. we pick randomly balls b 0 , . . . , b k from urns U v0 , . . . , U v k , 3. we remove the ball b k from U v k , 4. for each i < k we move the ball b i to the urn U vi+1 , 5. we put one black ball in the urn U v0 .

Notice that the number of balls in each urn is constant during the evolution of this process. We assume that all random choices during the execution of our process are done independently according to uniform distributions.

Notice that if G = ({v}, ∅), then our model is reduced to the standard, classic "urn model". In our investigations the classic model describes properties of the urns indexed by source nodes. The behavior of remaining urns U b depends on the behavior of all urns from the family {U a : (a, b) ∈ E}.

The first motivation of our research is the analysis of blending attacks on some kinds of mix networks analyzed in e.g., [START_REF] O'connor | On blending attacks for mixes with memory[END_REF], [START_REF] Serjantov | From a trickle to a flood: Active attacks on several mix types[END_REF], [START_REF] Dingledine | Blending different latency traffic with alpha-mixing[END_REF]. Mix networks, introduced by D. L. Chaum in the paper [START_REF] Chaum | Untraceable electronic mail, return addresses, and digital pseudonyms[END_REF], are one of the most popular ways of protecting anonymous communication. More information about mix networks can be found in Section 7.

Organization of this paper

In Section 2 we investigate a general model of a system of urns. In Section 3 we present a special (but most important for applications) model wherein urns are arranged in a row and balls are consecutively moved from one urn to another. We present several results including some asymptotics. In Section 4 we investigate a system of urns arranged in a parallel. We compare some strategies of arranging urns in Section 5. In Section 7 we show how our results can be applied to analysis of so-called flooding (blending) attack against mix networks.

Notations and preliminary facts

In the paper, E [X] denotes the expected value of the random variable X. If f (z) = i a i • z i is a formal power series, then we define the coefficient extractor as [START_REF] Flajolet | Analytic Combinatorics[END_REF], Chapter 1). |A| denotes the cardinality of a set A.

[z i ]f (z) = a i (see
The partial exponential function e n (x) is defined by the formula e n (x) = n k=0

x k k! . The sequence (e n (n)/e n ) n≥0 is decreasing and e n (n)

e n = 1 2 + O 1 √ n (1)
(see e.g. [START_REF] Weisstein | From mathworld -A Wolfram Web Resource[END_REF]). The Euler Gamma function for z > 0 is defined by the formula Γ(z) = ∞ 0 x z-1 e -x dx. For natural numbers n we have Γ(n + 1) = n!. The Euler Beta function is defined for a, b > 0 by the formula

B(a, b) = 1 0 x a-1 (1 -x) b-1 dx. It is well known that B(a, b) = (Γ(a)Γ(b))/Γ(a + b).
The incomplete regularized Beta function is defined by he formula

I (z; a, b) = 1 B(a, b) z 0 x a-1 (1 -x) b-1 dx.
We will use the following two recurrences for the incomplete beta function:

I (z; a, b) = zI (z; a -1, b) + (1 -z)I (z; a, b -1) (2)
and

I (z; a, b) = I (z; a -1, b) - Γ(a + b -1) Γ(a)Γ(b) (1 -z) b z a-1 . (3)
Fig. 1: Example of a system of connected urns. Graph G = ({1, 2, 3, 4, 5}, {(1, 2), (2, 3), (2, 4), (3, 5), (4, 5)}) just after round t = 8 (left side) and just after round t = 9 (right side). For each a ∈ {1, 2, 3, 4, 5}, we have na = 4. In this diagram we have

B1(8) = B1(9) = 4, B4(9) = W4(9) = 2.
These formulas may be found in [START_REF] Weisstein | From mathworld -A Wolfram Web Resource[END_REF] and NIST (2013). They can also be proved by checking that derivatives (taken with respect to the variable z) of both sides of these equations are the same. Clearly, the initial values are the same in both sequences. The incomplete beta function admits an analytic continuation for other values of parameters. We have I (z; a, 0) = 0 for a > 0 among others.

General Model

Let us fix a finite directed acyclic graph G = (V, E). Let N = (n a ) a∈V denote capacities of urns (U a ) a∈V , i.e., n a is the initial number of white balls in the urn U a . We call the triple U = (V, E, N ) a system of connected urns. Notice that the number of balls during each process is fixed for each urn. Indeed, each ball is replaced by exactly one ball.

Let us describe more precisely the choice of a random path in the graph G. We start at one of the sources at random (equally likely). Then we take an edge out of it at random (all neighbors are equally likely). We do the same thing with every node we arrive at: choose one of the neighbors randomly. The walk is perpetuated till a sink is reached.

We denote by p a the probability that a randomly chosen path from some source to some sink goes through the node a. For each (a, b) ∈ E, we denote by p ab the probability of the event where the edge (a, b) is on the randomly chosen path. Notice that if a is a source node, then p a = 1 |S| , where S is the set of source nodes in the graph G. Moreover, p ab = pa out(a) , where out(a) = |{c ∈ V : (a, c) ∈ E}| and

p a = (b,a)∈E p ba ,
when a is not a source node.

Let B a (t) denote the number of black balls in the urn U a after the round t. Notice that B a (0) = 0 for each a ∈ V . Our goal is to determine a difference equation for the sequence (E [B a (t)]) t≥0 for each a ∈ V .

For the sake of clarity of presentation, we add one artificial node • to our graph. We consider an extended system with nodes

V • = {•} ∪ V , edges E • = E ∪ ({•} × S)
, where S is the set of source nodes in (V, E). We set capacity n • = 1 and we put initially one black ball to the urn U • . Then B • (t) = 1 for each t and p •s = 1 |S| for each s ∈ S. Let us fix a node a ∈ V , the round number t and suppose that we know E [B b (t)] for each b ∈ V . Then,

• at the (t + 1) st round the number of black urns in the node a may increase by 1 if there is b such that (b, a) is on the chosen path, a black ball is selected from U b and a white ball is selected from U a . This happens with probability

p ba • B b (t) n b • na-Ba(t)
na .

• at the (t + 1) st round the number of black urns in the node a may decrease by 1 if there is b such that (b, a) is on the chosen path, a white ball was selected from U b and a black ball was selected from U a . This happens with probability

p ba • n b -B b (t) n b
• Ba(t) na .

• with the remaining probability the state is not changed. This is the case if a black ball is replaced by another black ball or a white ball by a white one.

Putting these facts together, we deduce that

E [B a (t + 1)] = (b,a)∈E p b,a n b E [B b (t)] + 1 - p a n a E [B a (t)] . (4)
Let W a (t) denote the number of white balls in the urn U a after the round t. Notice that W a (t) = n a -B a (t) for each a ∈ V • . In particular, W • (t) = 0 for each t. More generally, if d(a) denotes the minimal distance of the node a from some source link from V , then for each t ≤ d(a) we have W a (t) = n a .

After a simple transformation we get

E [W a (t + 1)] = (b,a)∈E p b,a n b E [W b (t)] + 1 - p a n a E [W a (t)] . (5)
Notice that recurrences (4) and ( 5) are the same. The solutions of these recurrences differ, as they have different initial conditions. Let

F a (x) = t≥0 E [W a (t)] x t
be the generating function for the sequence (E [W a (t)]) t≥0 . From ( 5) and from the fact that F a (0) = n a , we get the following equation for each a ∈ V :

F a (x) = n a + x (b,a)∈E• p ba n b F b (x) 1 -∆ a x ,
where ∆ a = 1 -pa na .

Let prec(a) denote the set of all nodes from V for which there is some oriented path to the node a (we include the node a in prec(a)). For any real number x and a path σ = (b 1 , . . . , b n ) from some source to node a we define ct function that counts the number of nodes on σ with ∆ parameter equal x:

ct a (x, σ) = |{k ∈ {1, . . . , n} : x = ∆ b k }|
and, finally, we put ct a (x) = max{ct a (x, σ) : σ is a path from some source to a} .

If p(t) is a polynomial, then deg(p) denotes the degree of p. We shall formulate a theorem which reduces the problem of finding closed formulas for E [W a (t)] to problems of linear algebra. This theorem may be treated as a specialized form of a theorem about expansion of rational functions (see e.g. Theorem IV.9 from [START_REF] Flajolet | Analytic Combinatorics[END_REF].

Theorem 1 Let a ∈ V and let D(a) = {∆ b : b ∈ prec(a)}. Then there are polynomials (p ∆ (t)) ∆∈D(a) such that (∀t ≥ 0)   E [W a (t)] = ∆∈D(a) p ∆ (t)∆ t   and deg(p ∆ ) < ct a (∆) for each ∆ ∈ D(a). Proof: We claim that for each a ∈ V there are polynomials (α a ∆ ) ∆∈D(a) and integers (k a ∆ ) ∆∈D(a) such that deg(α a ∆ ) < k a ∆ ≤ ct a (∆) and F a (x) = ∆∈D(a) α a ∆ (x) (1 -∆x) k a ∆ .
Observe that if a is a source node, then F a (x) = na 1-∆s , so the claim is true for any source node. Hence, suppose that the claim is true for all b ∈ prec(a) \ {a}. From the recurrence (5) we get

F a (x) = n a 1 -∆ a x + (b,a)∈E ∆∈D(b) x • α b ∆ (x) (1 -∆x) k b ∆ (1 -∆ a • x)
.

Let us consider a term

τ = x • α(x) (1 -∆x) k (1 -∆ a x)
,

where deg(α) < k. If ∆ a = ∆, then τ = x•α(x) (1-∆x) k+1 and deg(x • α) < k + 1. If ∆ a = ∆,
then we decompose τ into partial fractions and we find a constant B and a polynomial β such that deg(β) < k and

τ = B 1 -∆ a + β(x) (1 -∆x) k .
This proves the claim.

Let us fix ∆ ∈ D(a) and let us consider the term α(x)

(1-∆) k , where α(x) is some polynomial of degree less than k. Then

α(x) (1 -∆) k = k-1 l=0 α l x l (1 -∆) k
for some constants α 0 , . . . , α k-1 . Observe that

x l (1 -∆) k = m≥0 m + k -1 k -1 ∆ m x m+l .
Therefore,

[x t ] x l (1 -∆) k = ∆ t-l t -l + k -1 k -1 = ∆ t t-l+k-1 k-1 ∆ l = ∆ t β(t) ,
where β is a polynomial and deg(β

) = k -1. The term α(x) (1-∆) k is of the same form. 2
Theorem 1 gives us a general form of a solution of the recurrence equation ( 5) for a fixed structure U = (V, E, N ). In order to find required coefficients of polynomials (p ∆ ) ∆∈D we may use the equations W a (0) = . . . = W a (d(a)) = n a and, if d(a) is too small, we may solve explicitly the equation ( 5) for sufficiently many small values of the time parameter t.

Example Let G = ({0, 1, 2}, E, N ), where E={(0, 1), (1, 2)} and N 0 = N 1 = N 2 = n > 1. Then, prec(2) = {0, 1, 2}, p 0 = p 1 = p 2 = 1, so ∆ 0 = ∆ 1 = ∆ 2 = 1 -1 n . Hence, D(2) = {1 -1 n } and deg 2 (1 -1 n ) = 3. From Theorem 1 we deduce that E [W 2 (t)] = p(t)(1 -1 n ) t for some polynomial p(t) of degree less than 3. Let p(t) = a + bt + ct 2 . Notice that E [W 2 (0)] = E [W 2 (1)] = E [W 2 (2)] = n, hence n = p(0)(1 -1 n ) 0 = a, n = p(1)(1 -1 n ) = (a + b + c)(1 -1 n ) and n = p(2)(1 -1 n ) 2 = (a + 2b + 4c)(1 -1 n ) 2 .
The solution of this system of linear equations (in the variables a, b and c) is given by a

= n, b = -3n-2n 2 2(n-1) 2 , c = n 2(n-1) 2 , hence E [W 2 (t)] = n 1 + 2n -3 2(n -1) 2 t + 1 2(n -1) 2 t 2 1 - 1 n t .
In a similar way we may show that

E [W 1 (t)] = n 1 + t n-1 1 -1 n t and, of course, that E [W 0 (t)] = n 1 -1 n t .
It is clear that in a similar way we can analyze any system of urns with the underlying graph of the form ({0, . . . , n + 1}, E) where E = {(k, k + 1) : k = 0, . . . , n}. However, in the next section we show a more uniform approach to this class of graphs. Theorem 1 will be explicitly used in Sections 4 and 6.2.

Serial System of Urns

Let us fix two parameters n and k. Let U k = ({0, . . . , k}, {(a, a + 1) : a < k}, N ), where n a = n for each a ∈ {0, . . . , k}. That is, each urn has the same capacity. Therefore, at each round we move one ball from the urn U a to U a+1 (if a < k), we remove one ball from the k th urn and we add one black ball to the urn U 0 . As before, we assume that we choose the balls independently, using uniform distributions. Notice that this model strictly corresponds to so-called MIX-cascade described in Section 7.

The evolution of this model is described by the vector B(t) = (B 0 (t), . . . , B k (t)) of black balls in consecutive urns. Notice that B(0) = (0, . . . , 0). Let us observe that the random variable B 0 describes the classic urn and balls problem and

E [B 0 (t)] = n 1 -1 -1 n t . Clearly, B 0 (0) ≤ B 0 (1) ≤ B 0 (2) ≤ . . .. But if k > 0, then for 0 < a ≤ k the processes (B a (t)) t≥0 are not monotonic with probability 1 -for example Pr[B 1 (2) = 1, B 1 (3) = 0] = n-1 n 3 > 0.

Difference equations

Since we are going to analyze behavior of the system U k for arbitrary k, instead of using Theorem 1 we shall solve directly the recurrence 4 adapted to this case. Notice that for each a ∈ {0, . . . , k} we have p a = 1 and that p a,a+1 = 1 for each a = 0, . . . , k -1. For a ∈ {1, . . . , k} we obtain the following recurrence from equation 4:

E [B a (t + 1)] = 1 n E [B a-1 (t)] + (1 - 1 n )E [B a (t)] . (6) Let y a (t) = E [B a (t)], δ = 1 n and ∆ = 1 -1 n .
Then the initial observation and the equation ( 6) can be rewritten as

y 0 (t) = n(1 -∆ t ), y a+1 (t + 1) = ∆ • y a+1 (t) + δ • y a (t) . (7)
Let us also recall that y a (0) = 0 for each a. It is also clear that y a (t) = 0 for each t ≤ a.

Closed formula

In this section we will show that there exists a closed formula for the expected value of the random variable B a (t) for arbitrary a and t.

Theorem 2 For each a ≥ 0 and t ≥ 0 we have

E [B a (a + t)] = n • I 1 n ; a + 1, t .
Proof: Let z a (t) = y a (a + t) and ∆ = 1 -1 n and δ = 1 n . Notice that z a (0) = 0 for each a, z

0 (t) = n • (1 -∆ t ) and z a+1 (t + 1) = y a+1 ((a + t + 1) + 1) = ∆ • y a+1 (a + 1 + t) + δ • y a (a + t + 1) = ∆ • z a+1 (t) + δ • z a (t + 1) .
Therefore, the equations (7) may be rewritten as follows:

z 0 (t) = n(1 -∆ t ), z a+1 (t + 1) = ∆ • z a+1 (t) + δ • z a (t + 1) . ( 8
)
Plain calculations show that

n • I 1 n ; 1, t = n Γ(t + 1) Γ(1)Γ(t) 1 n 0 (1 -x) t-1 dx = n 1 -1 - 1 n t , so z 0 (t) = nI 1 n ; 1, t . From equation (2) applied for z = 1 n we get n • I 1 n ; a + 2, t + 1 = ∆ • n • I 1 n ; a + 2, t + δ • n • I 1 n ; a + 1, t + 1 . (9)
Moreover, n • I 1 n ; a + 1, 0 = 0, so the sequences (z a (t)) a,t and (n • I 1 n ; a + 1, t ) a,t satisfy the same recurrence relations.

2

Theorem 2 gives us a closed formula for the expected number of black balls after a given number of steps in a given urn. However, we need another formula for E [B a (a + t + 1)] that is convenient for the investigation of properties of a fixed urn and for various values of t.

Theorem 3 For each a ≥ 0 and t ≥ 0 we have

E [B a (a + t + 1)] = n 1 -1 - 1 n t+1 a k=0 k + t k 1 n k . (10)
Proof: From formula (3) we deduce that

I (z; a + 1, t + 1) = I (z; a, t + 1) - a + t a (1 -z) t+1 z a .
We also know that

I (z; 1, t + 1) = 1 -(1 -z) t+1 = 1 - 0 + t 0 (1 -z) t+1 z 0 ,
so we get

I (z; a + 1, t + 1) = 1 - a k=0 k + t k (1 -z) t+1 z k .
After putting z = 1 n into this formula and using Theorem 2, we get the desired identity. 2

Asymptotic behavior

In this section we investigate asymptotic behavior of the system of urns. In particular, it is important for us when the first black ball appears in a particular urn, when the fixed urn is full of black balls and when a big portion of balls in a given urn is black.

When almost all balls are black

In this section we shall investigate the moment at which almost all balls in a given layer are black. More precisely, we fix the number n of balls in each layer and we want to approximate the moment when n -1 balls in a given urn are black.

Lemma 1 Let t n = n(ln(n) + (a + ν) ln(ln(n)) -ln(a!)) for some ν ≥ 0. If 0 ≤ k < a + ν, then n 1 - 1 n tn k + t n k 1 n k = O 1 (ln n) a+ν-k .
and for k = a and ν = 0 we have

n 1 - 1 n tn a + t n k 1 n a = 1 + O ln ln n ln n .
The proof of this lemma can be instantly deduced from the following equation

ln 1 - 1 n tn = -t n ln 1 1 -1 n = - t n n 1 + O 1 n . ( 11
)
Theorem 4 If a is fixed and

t n = n (ln(n) + a ln(ln(n)) -ln(a!)), then E [B a (a + t n )] = n -1 + O ln ln n ln n
as n approaches infinity.

Proof: The theorem is a consequence of Lemma 1 (with ν = 0) and Theorem 3. 2

Notice that for a = 0 we get E [B 0 (n ln n)] = n -1 + o (n), so our result is consistent with the classic Coupon Collector Problem (see [START_REF] Feller | An Introduction to Probability Theory and Its Applications[END_REF]). We shall come back to this observation in Sec. 6. Below we show that just after the time n(ln n + ln((ln n) a /a!)) all the balls in a th urn are black with high probability.

Theorem 5 If a and ν > 0 are fixed and t n = n(ln(n) + (a + ν) ln(ln(n)) -ln(a!)), then

Pr[B a (a + t n ) = n] = O 1 (ln n) ν .
as n approaches infinity.

Proof: Notice that the number of white balls in the t n -th round in the

a th urn is W a (t n ) = n-B a (a+t n ). Thus, W a (t n ) = 0 is equivalent to B a (a + t n ) = n. However, Pr[W a (t n ) = 0] ≤ E [W a (t n )] = n -E [B a (a + t n )] as W a (t n ) is integer valued, non-negative random variable. To prove our theorem it is sufficient to show that E [B a (a + t n )] = n -O 1 (ln n) ν .
This is the consequence of Lemma 1 for ν > 0 and Theorem 3 . 2

First black ball

Let us recall that B 0 (1) = 1.

Theorem 6 If a is fixed and t n = ((a + 1)!n a ) 1 a+1 , then

lim n→∞ E [B a (a + t n )] = 1 . Proof: Let us observe that for all x ∈ [0, 1 n ] we have x a (1 -1 n ) t ≤ x a (1 -x) t-1 ≤ x a . Hence n B(a + 1, t) 1 - 1 n t-1 1 n 0 x a dx ≤ nI 1 n ; a + 1, t and nI 1 n ; a + 1, t ≤ n B(a + 1, t) 1 n 0 x a dx , so Γ(a + t + 1) Γ(t) 1 - 1 n t-1 1 (a + 1)!n a ≤ nI 1 n ; a + 1, t ≤ Γ(a + t + 1) Γ(t) 1 (a + 1)!n a . Notice that Γ(a + t + 1) Γ(t) = t a+1 a j=0 1 + j t , so Γ(a + t n + 1) Γ(t n ) = (a + 1)! • n a 1 + O 1 n a+1 a
.

Moreover, from equation ( 11) we get

1 - 1 n tn = 1 + O 1 n 1 a+1
, which accomplishes the proof. 2

When nearly half the balls are black

Let us recall that e a (a)/e a is close to 1 2 (see Eq. ( 1)). We will show that at time a • n nearly half of the balls in a th urn are black.

Theorem 7 If a is fixed and

t n = a • n, then E [B a (a + t n + 1)] = n 1 - e a (a) e a + O (1)
.

Proof: Applying equation ( 11) we can easily prove that

1 - 1 n an+1 = e -a (1 + O 1 n ) .
Moreover,

k + an k = 1 k! k-1 j=0 (k + an -j) = a k n k k! k l=1 (1 + l an ) = a k n k k! (1 + O 1 n ) , and
1 - 1 n an+1 k + an k 1 n k = e -a a k k! (1 + O 1 n ) .
From Theorem 3 we get

E [Y a (a + an + 1)] = n 1 - a k=0 e -a a k k! 1 + O 1 n = n 1 -e -a • a k=0 a k k! • 1 + O 1 n = n 1 - e a (a) e a 1 + O 1 n = n 1 - e a (a) e a + O 1 n = n 1 - e a (a) e a + O (1)
, so Theorem 7 is proved. 2

Parallel System of Urns

In the previous section we investigated a serial system of urns. In this section we consider another variant of the system, namely, let G = ({0, . . . , k+1}, E), where E = ({0}×{1, . . . , k})∪({1, . . . , k}×{k+1}).

We assume, as before, that the capacity of all urns is n and that at the beginning of considered process all balls are white. At each step we select one path 0 → i → (k + 1), where i ∈ {1, . . . , k} with the same probability. Next, we choose balls from selected urns, we move the balls according to the arrows and put a black ball in the selected place in the urn U 0 . Observe that p 0 = p k+1 = 1, p 0a = 1 k , p a(k+1) = 1 and p a = 1 k for each a ∈ {1, . . . , k}.

Let W k+1 (t) denote the number of white balls in the urn U k+1 after t th step. From Theorem 1 we know that

E [W k+1 (t)] = a 1 - 1 kn t + (b + ct) 1 - 1 n t for some coefficients a, b and c. Moreover, E [W k+1 (0)] = E [W k+1 (1)] = E [W k+1 (2)] = n, from which we deduce that a = k 2 n (k-1) 2 , b = n-2kn (k-1) 2 , c = - n (k-1)(n-1) , so E [W k+1 (t)] = n k 2 (k -1) 2 1 - 1 kn t + 1 -2k (k -1) 2 + -t (k -1)(n -1) 1 - 1 n t .
Since B k+1 (t) is the number of black balls in corresponding urns after t th step, we get:

E [B k+1 (t)] = n 1 - k 2 (k -1) 2 1 - 1 kn t + 2k -1 (k -1) 2 + t (k -1)(n -1) 1 - 1 n t . (12)
Remark The parallel system considered in this section consisting of k + 2 urns is equivalent, from the point of view of the last urn, to the serial system of three urns: the first urn has capacity n, the second urn has capacity k • n and the third one has capacity n.

Asymptotics

The formula ( 12) is much easier to analyze than the formula (3). We formulate without proofs four results about the parallel system of urns which corresponds to Theorems 4, 5, 6 and 7:

Theorem 8 If a is fixed and n grows to infinity then

1. E B a+1 a • n • (ln n + 2 ln( a a-1 ) = n -1 + O ln n n , 2. Pr[Z a+1 (a • n • (ln n + 2 ln( a a-1 ) + ln(ln(n)))) = n] = O 1 ln n , 3. E B a+1 3 √ 6an 2 = 1 + O 1 n 1 3 , 4. if a ≥ 2 then lim n→∞ E B a+1 n • a • ln 2a 2 (a-1) 2 n = 1 2 + a .
where 2 = 0.1112 . . . and the sequence ( a ) a is decreasing and lim a→∞ a = 0.

Comparison of Serial and Parallel Systems of Urns

In the following table we compare dynamics of the sink node in the parallel system of urns with total k +2 urns and the dynamics of the sink node in the serial system of urns also consisting of k + 2 urns. Let us recall that k ≥ 2.

Expected number Serial Parallel of black balls structure structure 1

((k + 2)!n k+1 ) 1 k+2 (Thm. 6) 3 √ 6kn 2 (Thm. 8.3) ∼ 1 2 n (k + 1)n (Thm. 7) nk ln 2k 2 (k-1) 2 (Thm. 8.4) n -1 n(ln n + (k + 1) ln ln n -ln(k + 1)!) (Thm. 4) kn(ln n + 2 ln k k-1 ) (Thm. 8.1)
This table shows how many black balls have to be put to the system to obtain given expected number of black balls in the sink urn in serial and parallel structures with the same total capacity. Notice that in the serial model the first black ball appears in the sink urn in time θ(n

Final Remarks

We presented results for two classes of urn and bin models with applications to the security analysis of MIX-servers. The results from this paper partially describe properties of systems of urns and some interesting theoretical questions are left unanswered. In the next section we formulate some of our additional observations.

Expected time

Let us consider a serial system of two urns. Let T

(2)

n denote the first round when all balls in the second urn are black. We may model this system as a Markov chain with states M = {(x, y) : x, y ∈ {0, . . . , n}}, where (x, y) corresponds with the situation when there are x black balls in the first urn and there are y black balls in the second urn. Then, T

(2) n is the hitting time of a set A = {0, . . . , n} × {n} for the Markov chain M starting from the state (0, 0). Let h a,b denote the hitting time of A for Markov chain starting from the state (a, b). Then, for (a, b) / ∈ A we have

h a,b = 1 1 -ab nn (n -a)(n -b) n 2 h a+1,b + b(n -a) n 2 h a+1,b-1 + a(n -b) n 2 h a,b+1 + 1 .
The number E T

(2) n = h 0,0 can be evaluated numerically for reasonably small values of the parameter n. Our calculus suggests the following hypothesis:

E T (2) n = n(H n + ln ln n + o(1)) ,
where H n denotes the n th Harmonic number.

System with different capacities

Let us consider a serial system consisting of two urns, where the first urn has capacity n, the second urn has capacity m and m = n. We call such structure the (n, m) system. Let B n,m (t) and Z n,m (t) denote the number of white and black balls in the second urn after t th round. From Theorem 1 we deduce that

E [W n,m (t)] = a 1 - 1 n t + b 1 - 1 m t
for some constants a and b. Taking into account that

E [W n,m (0)] = E [W n,m (1)] = m, we get a = mn n-m , b = m 2 m-n
, so finally we get

E [B n,m (t)] = m 1 - n n -m 1 - 1 n t + m n -m 1 - 1 m t .
Notice that

E[Bn,m(t)] m = E[Bm,m(t)] n . Therefore, if n = a • m and E [B n,m (t)] = m -1, then E [B m,n (t)] = n -a.
Hence, if a 1, then the filling time for the (m, a • m) system is essentially longer than the time required for filling the (a • m, m) system.

Application to Mix Networks

As mentioned in the introduction, the primary motivation for our research comes from security analysis of mix networks. Notice that the idea of mix networks is the essential building block for all anonymity preserving methods used in practice in the network communication (including TOR protocol [START_REF] Dingledine | Tor: The second-generation onion router[END_REF])).

Mix network We consider a system with senders, receivers and a special-purpose unit (called the MIXserver). Messages are not sent directly from senders to receivers but every message is sent to the MIXserver as a ciphertext. Several messages entering MIX-server are collected, cryptographically recoded, randomly permuted and forwarded to respective receivers. Thanks to it, messages leaving the MIX-server become (from the external observer's perspective) indistinguishable. Thus, the sender of a message cannot be linked with the recipient of this message and this should guarantee anonymity (so-called unlinkability of senders and receivers). Substantially different variants of the basic protocol adjusted to particular conditions (acceptable latency, volume of the traffic etc.) appeared in a well-developed body of literature devoted to anonymous communication (see e.g. [START_REF] Danezis | A survey of anonymous communication channels[END_REF]).

MIX cascade Let us notice that the MIX-server knows the correspondence between senders and receivers. That is, if the single MIX-server is corrupted, then the adversary can link senders with receivers. The simplest remedy that improves the security is to use several MIX-servers instead of a single one. The basic realization of this idea called MIX-cascade has already been suggested in the seminal paper [START_REF] Chaum | Untraceable electronic mail, return addresses, and digital pseudonyms[END_REF]). In this protocol, a message, to be delivered to the proper receiver, must be processed (recoded) by a fixed number of consecutive MIX-servers.

In some variants of the protocol working in practice, the new message submitted to the first MIX-server is put in the buffer. Then, if there are more than n messages in the buffer, the new message replaces one of the messages randomly chosen from the buffer. The pushed-out message is submitted to the 2 nd MIX-server. The processing in consecutive MIX-servers is exactly the same. Finally, a single message leaves the last server and is removed from the system and delivered to the receiver.

Other configurations of MIX-servers are considered in literature (eg. parallel MIX-cascade in Klonowski and Kutylowski (2005); Golle and Juels ( 2004)). It is a matter of investigation how to connect existing MIX-servers to obtain the best security/functionality properties.

Blending attacks Blending attacks are based on the following trick: the adversary submits to the MIXserver a number of fake messages. Such fake messages (using a special encoding) can be easily recognized by the adversary in the bunch of messages sent by legitimate users. If all but one messages are fake, the adversary can easily trace its route. This form of the attack is called an (n -1)-attack (see [START_REF] Kesdogan | The hitting set attack on anonymity protocols[END_REF]). Generally, to make the anonymity weaker, the adversary may submit a fraction of all messages and blend fake messages with real ones (i.e. submitted by regular users) to be traced. Depending on particular protocols and implementations of MIX-es, blending attacks may be conducted in different ways. However, the core of the idea is to flush as many real messages as possible to isolate only a small number of target messages and then trace them.

One can easily see that such an attack can be precisely described by the model discussed in our paper. Indeed, MIX-servers are represented by urns filled with white balls (representing messages from legitimate senders). The security problem is how many messages the adversary has to submit to the system to remove significant number of legitimate messages and leave only adversarial messages (represented by black balls).

Up to now, blending type attacks for similar models have been investigated for very important practical settings in several papers, e.g. [START_REF] O'connor | On blending attacks for mixes with memory[END_REF]; [START_REF] Serjantov | From a trickle to a flood: Active attacks on several mix types[END_REF]; [START_REF] Dingledine | Blending different latency traffic with alpha-mixing[END_REF]. However, to the best of our knowledge, none of the previous analyses gives as precise and general results as our paper.

Practical consequences of obtained results

The presented results convince us that the way the MIXservers are connected has a significant influence on the immunity against flooding-type attacks. In particular, if we can construct a mix network of MIX-servers with some overall capacities, the parallel structure gives a better immunity than the serial one. That is, the expected time necessary to flush all white messages from the last MIX-server is greater in the parallel structure. This follows directly from theorems 4 and 8. We find this fact quite surprising and counter-intuitive. On the other hand, one can see that the parallel structure offers inferior security against cryptographic attacks. Indeed, each message has to be processed only by a single server instead of some k ≥ 2.

Another indication for the design of mix network is that if we have a series (cascade) of MIX-servers, they should not be of equal capacity. For example, placing a MIX-server of a bigger capacity at the end

Fig. 2 :

 2 Fig. 2: Graphs of the difference E [S4(t)] -E [P4(t)] for n = 1000. S4(t) is the number of black balls in the serial model and P4(t) is the number of black balls in the parallel model.

). On the other hand, in the serial model the sink urn is almost full at the time ∼ n log n, while in the

Acknowledgements

This paper was supported by Polish National Science Center -decision No. DEC-2013/09/B/ST6/02251. The authors would like to thank the anonymous Reviewer for all valuable comments and suggestions to improve the quality of our paper.

* This paper was supported by Polish National Science Center -decision No. DEC-2013/09/B/ST6/02251 1365-8050

of the cascade can improve the immunity against flooding attacks (see section 6.2).


Salam Khalifa
email: salamkhalifa@nyu.edu

Houda Bouamor
email: hbouamor@cmu.edu

Nizar Habash
email: nizar.habash@nyu.edu

DALILA: The Dialectal Arabic Linguistic Learning Assistant

Keywords: Dialectal Arabic, Computer Assisted Language Learning, Morphology

Introduction

Computer-assisted language learning is an area where researchers study how to make use of computers to support learners of a certain language [START_REF] Chapelle | Computer Assisted Language Learning[END_REF][START_REF] Levy | CALL Dimensions: Options and Issues in Computer-assisted Language Learning[END_REF]. Many software tools were designed to help learners by providing dictionaries, expert feedback, carefully designed "immersive" experiences, etc. However, language learners see little support online especially with real raw materials in the language they are learning. There is no substitute for a language learner to go online and read and understand text written by native speakers.

In the case of Arabic, the situation is more challenging than English and other European languages. The problem that most learners of Arabic face is that the written language is radically different from the various forms of Dialectal Arabic (DA) spoken throughout the Arab World. Hence, even the most advanced learners of Modern Standard Arabic (MSA) or Moroccan Arabic (to pick a dialect randomly) will find themselves confused on the streets of Cairo as well as on microblogging websites. It is also important to note that even "native" speakers have trouble understanding other dialect vocabulary [START_REF] Holes | Modern Arabic: Structures, Functions, and Varieties[END_REF]. Different DAs differ phonologically, lexically, morphologically, and syntactically from one another and from MSA [START_REF] Holes | Variation in the Morphophonology of Arabic Dialects[END_REF][START_REF] Watson | The Phonology and Morphology of Arabic[END_REF][START_REF] Brustad | The Syntax of Spoken Arabic: A Comparative Study of Moroccan, Egyptian, Syrian, and Kuwaiti Dialects[END_REF][START_REF] Habash | MAGEAD: A Morphological Analyzer and Generator for the Arabic Dialects[END_REF][START_REF] Habash | A Morphological Analyzer for Egyptian Arabic[END_REF][START_REF] Bouamor | A Multidialectal Parallel Corpus of Arabic[END_REF]. For example, state-of-the-art MSA morphological analyzers have been shown to have only 60% coverage of Levantine Arabic verbs [START_REF] Habash | MAGEAD: A Morphological Analyzer and Generator for the Arabic Dialects[END_REF] and 64% coverage of Egyptian Arabic words [START_REF] Habash | A Morphological Analyzer for Egyptian Arabic[END_REF].

While MSA is commonly used in formal written contexts, people are increasingly using DA on social media platforms such as Facebook, Twitter or Youtube to share their stories, opinions, post a comment or give a feedback or comment on a video and interact with the community [START_REF] Salama | YouDACC: the Youtube Dialectal Arabic Com-ment Corpus[END_REF][START_REF] Sadat | Automatic Identification of Arabic Dialects in Social Media[END_REF]. In a recent analysis, [START_REF] Huang | Improved Arabic Dialect Classification with Social Media Data[END_REF] showed that 42% of a sample of Facebook Arabic posts are written in DA (most of them in Egyptian).

Using online machine translation systems such as Google Translate to translate the DA sentences into English often produces incorrect or nonsense translations because such systems are trained on MSA-English parallel data. For instance, in the example given in Figure 1., the word mAbtfkrš 'She doesn't think', 1 was considered as an out of vocabulary and was erroneously transliterated instead (mAptvkrh). In order to overcome such issues and provide a continuous online/offline assistance, we present the Dialectal Arabic Linguistic Learning Assistant (DALILA), 2 a Chrome extension that utilizes cutting edge NLP tools targeted towards DA to assist learners and nonnative speakers in understanding different texts written in either DA (and also MSA). DALILA provides word analysis and English gloss corresponding to each word.

Arabic and its Dialects

Arabic processing is challenging for a number of reasons [START_REF] Habash | Introduction to Arabic natural language processing[END_REF]. Arabic is both morphologically rich (with many different affixes and clitics) and very ambiguous because it is written with an orthography that omits short vowels. Furthermore, Arabic has a number of variants (MSA and different DAs). While MSA is the shared official language of culture, media and education from Morocco to the Arabian Gulf countries, it is not the native language of any speakers of Arabic. DA is nowadays emerging as the language of informal communication online; in emails, blogs, discussion forums, chats, etc., as the media which is closer to the spoken form of language. A common breakdown of Arabic varieties into dialect groups identifies five major Arabic dialect regions: Egyptian, Gulf, Maghrebi, Levantine and Iraqi [START_REF] Habash | Introduction to Arabic natural language processing[END_REF]. There are other minor di-1 Arabic transliteration is presented in the Habash-Soudi-Buckwalter scheme [START_REF] Habash | On Arabic Transliteration[END_REF]: (in alphabetical order) Â b t θ j H x d ð r z s š S D T Ď ς γ f q k l m n h w y and the additional symbols: ' , Â , Ǎ , Ā , ŵ , ŷ , h , ý . 2 DALILA dlylh is an Arabic word meaning 'guide[fem]'. alects as well and some can be considered a different class on its own, e.g. Yemeni.

Recently, automatic Arabic dialect processing has attracted a considerable amount of research in NLP [START_REF] Shoufan | Natural Language Processing for Dialectical Arabic: A Survey[END_REF]. Most of these focus on the following:

• Morphological processing tools [START_REF] Pasha | MADAMIRA: A Fast, Comprehensive Tool for Morphological Analysis and Disambiguation of Arabic[END_REF][START_REF] Habash | Morphological Analysis and Disambiguation for Dialectal Arabic[END_REF][START_REF] Habash | A Morphological Analyzer for Egyptian Arabic[END_REF] • Annotation tools (Al-Shargi and Rambow, 2015)

• Resource creation [START_REF] Zaidan | The arabic online commentary dataset: an annotated dataset of informal arabic with high dialectal content[END_REF][START_REF] Bouamor | A Multidialectal Parallel Corpus of Arabic[END_REF][START_REF] Diab | Tharwa: A large scale dialectal arabic-standard arabic-english lexicon[END_REF][START_REF] Khalifa | A Large Scale Corpus of Gulf Arabic[END_REF][START_REF] Al-Shargi | A Morphologically Annotated Corpus and a Morphological Analyzer for Moroccan and San'ani Yemeni Arabic[END_REF], and

• Developing DA to English machine translation systems [START_REF] Salloum | Dialectal to Standard Arabic Paraphrasing to Improve Arabic-English Statistical Machine Translation[END_REF][START_REF] Zbib | Machine Translation of Arabic Dialects[END_REF][START_REF] Sajjad | Translating dialectal arabic to english[END_REF][START_REF] Elfardy | Aida: Identifying code switching in informal arabic text[END_REF][START_REF] Al-Badrashiny | Automatic Transliteration of Romanized Dialectal Arabic[END_REF][START_REF] Huang | Improved Arabic Dialect Classification with Social Media Data[END_REF] Our system makes use of state-of-the-art suite of tools developed to perform a morphological, syntactic and semantic analysis of DA and MSA texts.

The DALILA tool

In this section we talk about the motivation behind building DALILA, we then present our approach to use current research and available technologies to build a simple tool that is accessible and useful to the general public.

Motivation

The different challenges of Arabic dialects as discussed above can be hard for both learners and non-native speakers within a diverse community such as social networks. Given that most available resources are developed for MSA such as Google translate, or the embedded Bing translator inside Facebook and Twitter, it is convenient to have a resource that can fulfill the needs of both learners and non-native speakers to understand DA. Given the differences among different DAs, this is also helpful for Arabic native speakers from different dialects.

Solution

There has been much research done in the area of DA. Such research can be utilized as a backend for tools targeted for the general public. In our work, we opted to develop a browser extension. This will enable the tool to be cross platform, available to all technology users and can be used online and offline. There exist many similar extensions for other languages such as Japanese3 and Korean. 4These tools are simple dictionary entries and lookup tables on the backend, and the front end is a simple graphical user interface that shows the answer to the user.

Ingredients of the Extension

We decided to develop a Google Chrome extension for its simplicity and existing templates and mainly because of the popularity of the Chrome browser. 5 The extension is developed mainly using JavaScript and JSON (JavaScript Object Notation) dictionaries for the actual dictionary entries.

Front End

The front end is the interactive part of the extension. Here, we use the double click on a single word to select it, and then produce a small pop-up displaying the answers. Figure 3. shows an example of the actual interaction taking place.

Backend

The core of the backend is the basic morphological analysis algorithm used in ALMOR [START_REF] Habash | Arabic Morphological Representations for Machine Translation[END_REF] (which is based on the algorithm of BAMA [START_REF] Buckwalter | Buckwalter Arabic Morphological Analyzer Version 2.0[END_REF]). By using the ALMOR algorithm, we have access to any of A) ----------------------------------------------- In this section we the database in the ALMOR suite of Arabic Morphological databases. In the example in Figure 3., we specifically use the Egyptian Arabic morphological analyzer (CALIMA-ARZ)'s database [START_REF] Habash | A Morphological Analyzer for Egyptian Arabic[END_REF]. The database is converted to separate JSON dictionary files for suffix, stem and prefix. We also use two simple unigram language models for part-of-speech (POS) and lemmas (3016 and 12823 unigram entries respectively) based on the Penn Arabic Treebank (PATB parts 1,2 and 3) [START_REF] Maamouri | The Penn Arabic Treebank: Building a Large-Scale Annotated Arabic Corpus[END_REF][START_REF] Maamouri | Diacritization: A challenge to arabic treebank annotation and parsing[END_REF][START_REF] Maamouri | Creating a Methodology for Large-Scale Correction of Treebank Annotation: The Case of the Arabic Treebank[END_REF] with the training data split along the recommendations from [START_REF] Diab | LDC Arabic treebanks and associated corpora: Data divisions manual[END_REF], which is used in the training of Arabic morphological tagger MADAMIRA [START_REF] Pasha | MADAMIRA: A Fast, Comprehensive Tool for Morphological Analysis and Disambiguation of Arabic[END_REF] that we later compare to.

The morphological analysis algorithm is implemented in JavaScript. The main tasks of the algorithm are:

• Word is segmented into every possible 'pre-fix+stem+suffix' sequences, including empty prefixes and suffixes. • Each prefix, stem and suffix is checked against the dictionary to find all possible valid forms. • The combination prefix+stem+suffix analysis with the highest probability (in terms of POS and lemma choices) is selected. • The selected analysis is sent to the front end.

Evaluation

We perform a manual quantitative analysis on 1,000 words of Egyptian Arabic taken from the online blog ςAyzh Atjwz 'I wanna get married'. 6 For every word, we evaluate on the correctness of both the top analysis from MADAMIRA-EGY and the analysis produced by DALILA in terms of POS and English gloss (as a substitute for lemma choice). The results are in Table 1. The results of MADAMIRA-EGY are comparable to the system evaluation by [START_REF] Pasha | MADAMIRA: A Fast, Comprehensive Tool for Morphological Analysis and Disambiguation of Arabic[END_REF] where POS accuracy was 92.4%. However, the lemma accuracy reported by Pasha et al. ( 2014) is higher than our English gloss accuracy (87.8%). This is likely due to the difference in the genre of the training data. The accuracy results of DALILA are lower than MADAMIRA-EGY by 4.8% and 6.8% absolute in terms of POS and English gloss, respectively. This is not unexpected given the simpler disambiguation algorithm used in DALILA. The difference is small given the tradeoff of system complexity.

Feature

Conclusion and Future Work

We presented DALILA, a Chrome extension that utilizes cutting-edge Arabic dialect NLP research to assist learners and non-native speakers in understanding text written in either MSA or DA. DALILA provides dialectal word analysis and English gloss corresponding to each word.

In the future, we plan to cover more dialects as their databases become available. We also plan to use a more advanced algorithm that would take context into account as the current algorithm only works on single words. Finally, we plan to extend the tool's front end to allow different styles of presenting information back to the user including highlighting ambiguity and pronunciation details.

Figure 1 :

 1 Figure 1: Example of a Facebook post written in Egyptian Arabic and its translation obtained using Google Translate Chrome Extension on October, 21 2015. The correct English translation is 'She won't be thinking about marriage until she establishes herself. [lit. she not-she-thinks-not in any marriage now until-when she-builds her-future].'

  Figure 2: (A) Word selected by double clicking. (B) Pop-up balloon with answers.In this section we

Table 1 :

 1 Results on quantitative analysis of the output of DALILA and MADAMIRA-EGY

		DALILA MADAMIRA-EGY
	POS	88.50	93.30
	English Gloss 72.70	79.50

https://code.google.com/p/rikaikun/

http://www.toktogi.com/

http://www.w3schools.com/browsers/

http://wanna-b-a-bride.blogspot.ae

Acknowledgments

We would like to thank all the members of the team that developed the initial version of DALILA during the New York University Abu Dhabi Hackathon for Social Good in the Arab World (2015). The team members are Ayman Awartani, Clair Seager, Ayah Soufan, Maeda Hanafi, Hiba Bejaoui, Fatima Al Neyadi, Sara Al Kendi and the authors of this paper.


Salam Khalifa
email: salamkhalifa@nyu.edu

Nizar Habash
email: nizar.habash@nyu.edu

Dana Abdulrahim

Sara Hassan

A Large Scale Corpus of Gulf Arabic

Keywords: Arabic Dialects, Corpus, Large-Scale, Gulf Arabic

Most Arabic natural language processing tools and resources are developed to serve Modern Standard Arabic (MSA), which is the official written language in the Arab World. Some Dialectal Arabic varieties, notably Egyptian Arabic, have received some attention lately and have a growing collection of resources that include annotated corpora and morphological analyzers and taggers. Gulf Arabic, however, lags behind in that respect. In this paper, we present the Gumar Corpus, a large-scale corpus of Gulf Arabic consisting of 110 million words from 1,200 forum novels. We annotate the corpus for sub-dialect information at the document level. We also present results of a preliminary study in the morphological annotation of Gulf Arabic which includes developing guidelines for a conventional orthography. The text of the corpus is publicly browsable through a web interface we developed for it.

Introduction

Most Arabic natural language processing (NLP) tools and resources are developed to serve Modern Standard Arabic (MSA), the official written language in the Arab World. Using such tools to understand and process Dialectal Arabic (DA) is a challenging task because of the phonological and morphological differences between DA and MSA. In addition, there is no standard orthography for DA, which only complicates matters more. Some DA varieties, notably Egyptian Arabic, have received some attention lately and have a growing collection of resources that include annotated corpora and morphological analyzers and taggers. Gulf Arabic (GA), broadly defined as the variety of Arabic spoken in the countries of the Gulf Cooperation Council (Bahrain, Kuwait, Oman, Qatar, Saudi Arabia, and the United Arab Emirates), however, lags behind in that respect.

In this paper, we present the Gumar Corpus, 1 a large-scale corpus of GA that includes a number of sub-dialects. We also present preliminary results on GA morphological annotation. Building a morphologically annotated GA corpus is a first step towards developing NLP applications, for searching, retrieving, machine-translating, and spellchecking GA text among other applications. The importance of processing and understanding GA text (as with all DA text) is increasing due to the exponential growth of socially generated dialectal content in social media and printed works [START_REF] Sarnākh | Sukayk 1: riwāyah emārātiyya mah . aliyyah sākhirah[END_REF], in addition to existing materials such as folklore and local proverbs that are found scattered on the web. The rest of this paper is structured as follows. We present some related work in Dialectal Arabic NLP in Section 2. This is followed by a background discussion on GA in Section 3. We then discuss the collection of the corpus and describe its genre in Section 4. We present our preliminary annotation study and evaluate it in Section 5. Finally, we present the Gumar Corpus web interface in Section 6. 1 Gumar /gumEr/ is the word for 'moon' in Gulf Arabic.

Related Work

Dialectal Corpora

There have been many notable efforts on the development of annotated Arabic language corpora [START_REF] Maamouri | Resources for Arabic Natural Language Processing[END_REF][START_REF] Maamouri | The Penn Arabic Treebank: Building a Large-Scale Annotated Arabic Corpus[END_REF][START_REF] Smrž | The Other Arabic Treebank: Prague Dependencies and Functions[END_REF][START_REF] Habash | CATiB: The Columbia Arabic Treebank[END_REF][START_REF] Zaghouani | Large scale Arabic error annotation: Guidelines and framework[END_REF].

Most contributions however targeted MSA, developing annotation guidelines and producing large-scale Arabic Treebanks. These resources were instrumental in pushing the state-of-the-art of Arabic NLP. Contributions that are specific to DA are limited in size, more scattered and more recent. Some of the earliest and relatively largest efforts have targeted Egyptian Arabic (EGY). They include CALLHOME Egyptian Arabic (CHE) corpus [START_REF] Gadalla | CALLHOME Egyptian Arabic Transcripts[END_REF] and its associated Egyptian Colloquial Arabic Lexicon (ECAL) [START_REF] Kilany | Egyptian Colloquial Arabic Lexicon[END_REF]. In addition, there is the YADAC corpus (Al-Sabbagh and Girju, 2012), which was based on dialectal content identification and web harvesting of blogs, micro blogs, and forums of EGY content. And most recently, the Linguistic Data Consortium collected and annotated a sizable EGY corpus [START_REF] Maamouri | Egyptian Arabic Morphological Annotation Guidelines[END_REF]Maamouri et al., 2012a;[START_REF] Maamouri | Developing an Egyptian Arabic Treebank: Impact of Dialectal Morphology on Annotation and Tool Development[END_REF]. Levantine Arabic received less attention, with notable efforts including the Levantine Arabic Treebank (LATB) of Jordanian Arabic [START_REF] Maamouri | Developing and Using a Pilot Dialectal Arabic Treebank[END_REF] and the Curras corpus of Palestinian Arabic [START_REF] Jarrar | Building a Corpus for Palestinian Arabic: a Preliminary Study[END_REF]. Efforts on other dialects include corpora for Tunisian Arabic [START_REF] Masmoudi | A corpus and phonetic dictionary for tunisian arabic speech recognition[END_REF] and Algerian Arabic [START_REF] Smaïli | Building resources for Algerian Arabic dialects[END_REF]. There are also some efforts that targeted multiple dialects such as the COLABA project [START_REF] Diab | Colaba: Arabic dialect annotation and processing[END_REF] which annotated dialectal content resources for Egyptian, Iraqi, Levantine, and Moroccan dialects from online weblogs, the Tharwa multi-dialectal lexicon [START_REF] Diab | Tharwa: A large scale dialectal arabic-standard arabic-english lexicon[END_REF], the multidialectal parallel Arabic corpus [START_REF] Bouamor | A multidialectal parallel corpus of arabic[END_REF], and the highly dialectal online commentary corpus [START_REF] Zaidan | The Arabic online commentary dataset: an annotated dataset of informal arabic with high dialectal content[END_REF]. Most recently, in this conference proceedings, [START_REF] Al-Shargi | A Morphologically Annotated Corpus and a Morphological Analyzer for Moroccan and Sanaani Yemeni Arabic[END_REF] present two morphologically annotated corpora for Moroccan Arabic and Sanaani Yemeni Arabic.

As far as Gulf Arabic is concerned, [START_REF] Halefom | A corpus of Emirati Arabic[END_REF] created an Emirati Arabic Corpus (EAC) consisting of 2 million words of transcribed Emirati TV and radio shows.

The corpus was transcribed in broad IPA and translated to English. Morphological and lexical annotations as well as Arabic script annotation was manually done for a small portion of the corpus (around 15,000 words). Furthermore, Ntelitheos and Idrissi (Forthcoming) created an Emirati Arabic Language Acquisition Corpus (EMALAC) consisting of 78,000 words following the style of the widely studied CHILDES collection of corpora [START_REF] Macwhinney | The childes project: Tools for analyzing talk: Volume i: Transcription format and programs, volume ii: The database[END_REF].

Both EAC and EMALAC were created by linguists with the primary purpose of studying the grammatical system of the Emirati Arabic dialect and its development. There is a lot of emphasis in the annotations of these corpora on the phonological and morphosyntactic phenomena of Emirati Arabic. Our Gumar Corpus is differently oriented and designed: text as opposed to speech is the starting point. And computational models of GA is our target. Our corpus only includes language created by adult speakers (unlike EMALAC) and that is a slightly conventionalized novellike form. Finally the Gumar Corpus includes texts from a number of the Gulf countries and is not limited to the UAE. For recent surveys of Arabic resources for NLP, see Zaghouani (2014) and [START_REF] Shoufan | Natural language processing for dialectical arabic: A survey[END_REF].

Dialectal Orthography

Due to the lack of standardized orthography guidelines for DA, along with the phonological differences from MSA, and dialectal variations within the dialects themselves, there are many orthographic variations for written DA content. Writers in DA, regardless of the context, are often inconsistent with others and even with themselves when it comes to the written form of a dialect, writing with MSA driven orthography, or phonologically driven orthography in Arabic script or even Latin script [START_REF] Darwish | Arabizi Detection and Conversion to Arabic[END_REF][START_REF] Al-Badrashiny | Automatic Transliteration of Romanized Dialectal Arabic[END_REF]. These orthographic variations make it difficult for computational models to properly identify and reason about the words of a given dialect [START_REF] Habash | Con-ventional Orthography for Dialectal Arabic[END_REF], hence, a conventional form for the orthographic notations is important. [START_REF] Habash | Con-ventional Orthography for Dialectal Arabic[END_REF] proposed a Conventional Orthography for Dialectal Arabic (CODA). CODA is designed for the purpose of developing conventional computational models of Arabic dialects in general which makes it easy to be extended to other dialects. Initially, the guidelines of CODA were mainly specific to EGY. [START_REF] Jarrar | Building a Corpus for Palestinian Arabic: a Preliminary Study[END_REF] extended the existing CODA to cover Palestinian Arabic. Recent work on Tunisian [START_REF] Zribi | A Conventional Orthography for Tunisian Arabic[END_REF], Algerian [START_REF] Saadane | A Conventional Orthography for Algerian Arabic[END_REF] and Maghrebi Arabic [START_REF] Turki | A Conventional Orthography for Maghrebi Arabic[END_REF] extended the original version of CODA. We extend CODA to cover Gulf Arabic.

Arabic Dialect Morphological Modeling

Most of the work that explored morphology in Arabic focused on MSA [START_REF] Al-Sughaiyer | Arabic morphological analysis techniques: A comprehensive survey[END_REF][START_REF] Buckwalter | Buckwalter Arabic Morphological Analyzer Version 2.0[END_REF][START_REF] Graff | Standard Arabic Morphological Analyzer (SAMA) Version 3.1[END_REF][START_REF] Pasha | MADAMIRA: A Fast, Comprehensive Tool for Morphological Analysis and Disambiguation of Arabic[END_REF] [START_REF] Habash | MAGEAD: A Morphological Analyzer and Generator for the Arabic Dialects[END_REF]. One of the notable recent contributions for Egyptian Arabic morphological analysis is CALIMA (Habash et al., 2012a). The CALIMA analyzer for EGY and the commonly used SAMA analyzer for MSA [START_REF] Graff | Standard Arabic Morphological Analyzer (SAMA) Version 3.1[END_REF] are central in the functioning of the EGY morphological tagger MADA-ARZ [START_REF] Habash | Morphological Analysis and Disambiguation for Dialectal Arabic[END_REF], and its successor MADAMIRA [START_REF] Pasha | MADAMIRA: A Fast, Comprehensive Tool for Morphological Analysis and Disambiguation of Arabic[END_REF] 2013) and build two morphological analyzers for Moroccan Arabic and Sanaani Yemeni Arabic. As for GA, we are aware of a single effort on a rule based stemmer [START_REF] Abuata | A rule-based stemmer for Arabic Gulf Dialect[END_REF] that works on sets of words collected online; they compare their results to other well known MSA stemmers. In this paper we use MADAMIRA-EGY as a starting point for the GA morphological annotation following the approach taken by [START_REF] Jarrar | Building a Corpus for Palestinian Arabic: a Preliminary Study[END_REF].

Gulf Arabic Dialect

Strictly speaking, Gulf Arabic refers to the linguistic varieties spoken on the western coast of the Arabian Gulf, in Bahrain, Qatar, and the seven Emirates of the UAE [START_REF] Qafisheh | A Short Reference Grammar of Gulf Arabic[END_REF], as well as in Kuwait and in Al-Hasathe eastern region of Saudi Arabia [START_REF] Holes | Gulf Arabic[END_REF]. Omani, Hijazi, Najdi, and Baharna Arabic, among other additional dialects spoken in the Arabian Peninsula, are usually not included in grammars of Gulf Arabic due to the fact that they considerably vary in their linguistic features from the set of dialects listed above. In this current project, we extend the use of the term 'Gulf Arabic' to include any Arabic variety spoken by the indigenous populations residing the six countries of the Gulf Cooperation Council: Bahrain, Kuwait (KW), Oman (OM), United Arab Emirates (AE), Qatar (QA), and Kingdom of Saudi Arabia (SA).

The cultural homogeneity of the Gulf region does not necessarily entail linguistic homogeneity. Indeed, GA dialects extensively differ in their morpho-phonological and lexical features, reflecting a number of geographical and social factors [START_REF] Holes | Gulf Arabic[END_REF] in addition to being influenced by different contact languages at different time periods. A number of linguistic features set GA dialects apart from other dialects spoken in the Arab world. One of the distinguishing phonological features of most GA dialects includes maintaining the pharyngealized fricative /z Q /,2 as well as the interdental /T/ and /D/, unlike what happens in other Arabic dialects. Among the most prominent phonological features in GA are the variant pronunciations of the sounds /q/, /dZ/, /S/, and /k/. /q/ may be realized in certain dialects as /g/ as in /ga:l/ 'he said', or as /dZ/ as in /dZIdIr/ 'pot'. /dZ/, on the other hand, may be realized in some varieties as /j/, as in /jImEl/ 'camel'. In terms of the morphological features, and as in the case with most spoken Arabic dialects, GA dialects have also lost case inflection (with the exception of some Bedouin dialects, e.g. /bIntIn P@s Q i:lE/ 'respectable girl'). Possession may also be marked by clitics such as /ma:l/ and /èag/ [START_REF] Holes | Gulf Arabic[END_REF]), e.g. /lI-kta:b ma:lEl m2r2h/ 'The book of the lady'. Negation is also marked by the particles /mu:/ (and its variants /mUb/, /mUhUb/, and /hUb/) [START_REF] Holes | Gulf Arabic[END_REF]. The plural and the dual masculine and feminine forms of verbs and nouns are collapsed into one form in most dialects, but some distinctions are still maintained in certain others. For instance, in some varieties of Saudi, Emirati, and Omani Arabic, verbs and possessive pronouns inflected for the 3 rd plural feminine are quite distinct from the masculine forms:

• /ga:mEt/ 'She stood up' -/ga:mEn/ 'They[2FP] stood up'.

• /wEdZhIk/ 'Your[2FS] face' -/w@dZu:hkIn/ 'Your[2FP] faces'.

Additional morphological features include the cliticized /ba/ for future (instead of the standard /sa/ prefix). Alternatively, in some varieties of GA, the motion verb /ra:è/ has grammaticalized into a future marker (e.g. Kuwaiti, Bahraini, and some varieties of Saudi Arabic). Less prominently, yet still a distinctive feature in some GA dialects, is the the epenthetic /n/ found in the active participle in some varieties of Emarati and Baharna Arabic: /ma:Qt Q Inh@m/ 'I've/'d given them'. Finally, the lexicon of GA consists of standard Arabic cognates that may or may not follow the phonotactics of the respective dialects. Unsurprisingly, many cognate expressions that are highly frequent in a given dialect have reduced in form, such as -/liPay SayP/ 'For which thing'→/le:S/ 'Why'. As for lexical borrowings in GA dialects, there is an undoubtedly substantial amount of lexical items that have been borrowed from various contact languages throughout different historical periods, e.g.,

• /QEmbElu:s Q / 'Ambulance' from English.

• /hEst/ 'There is' from Persian.

• /Pa:lu:/ 'Potatoes' from Hindi.

Corpus Description

Corpus Collection Gulf Arabic, just like any other Arabic dialect has no written convention nor is it used as a formal mean of communication in the media, education or official documents. Hence there are no known go-to resources. A unique genre of written materials that is specifically known to GA is online anonymous publicly published long conversational novels. We have found a huge collection of these novels online in one place. 3 We automatically downloaded about 1,200 MS Word documents. Usually, such novels are written in lengthy threads that can be found in online forums. The data we got was collected by volunteering forum members into MS Word documents and then published by another member in an organized matter. 4Corpus Genre The main theme of most of the novels is romantic; but they also include drama and tragedy. The structure of a novel is simple. It starts with a brief introduction that contains the title of the novel, the writer's pen name (no real names are used) and the country of the novel. The introduction is then followed by a prologue that usually contains a small piece of dialectal poetry or a small piece of literary writing usually in MSA. It also contains a brief description of the novel characters, though some writers prefer to introduce the characters as their role appears. Then comes the main body of the novel, which is often a dialogue between the characters. There are also some pieces of narration between conversations in either the dialect or MSA. The last part of the novel usually has some "moral" lessons narrated by the writer. Writers tend to ask the audience for positive criticism and opinions and whether they should continue writing more novels or not. The novels are entirely written in DA except for the parts mentioned above. The dialect of the novel is not necessarily the same as the dialect of the writer. Most of the time the writers remain anonymous under nicknames, though they ask to be credited if the novel is transferred to another forum. Hence some writers are quite famous among the audience. The targeted audience is mainly female teenagers, the nature of publishing the novels is highly interactive and dependent on the activity of the audience. The writer usually ends each "part" in the novel with a teaser and demands participation and encouragement from the audience. Table 1 shows statistics on all the collected text. Words are whitespace tokenized and the counts include punctuation. The number of sentences represents the number of lines. Most of the time, each document represents a single novel; but in few cases a novel may be split into more than one document.

Corpus Dialects and Dialect Annotation

We have annotated the corpus on the level of documents for the dialect, novel name and writer name for each. The dialect of the written text was the most challenging to know. In some documents, the dialect or the country of the writer was explicitly stated; in others, names of cities clearly indicated the origin country. However, in many cases, further investigation was needed. The GA dialects are closely intertwined, yet when thoroughly observed show evident differences. These differences were observed through common trends in relation to each GA dialect. It is important to point that the names given to the characters in each story have shown a trend with the dialect used, for example: SA dialect novels have repeatedly used the names fySl 5 /fe:s Q El/ 'Faisal', ςbd Alςzyz /QEbdIlQEzi:z/ 'Abdulaziz' and trky /tIrkej/ 'Turky' for male characters and lmA /lEmE/ 'Lama', wsn /wEsEn/ 'Wasan' and njwd /ndZu:d/ 'Njood' for female characters. On the other hand the AE dialect novels have used the names hz∼Aς /hEzza:Q/ 'Hazza'', zAyd /za:jId/ 'Zayed' and rAšd /ra:SId/ 'Rashid' as male names and HS∼h /èIs Q s Q E/ 'Hessa', myθA' /me:TE/'Maytha' and šm∼h /SEmmE/ 'Shamma' for female characters. It is worth mentioning that in both SA and AE dialect novels the male names could be related to the leaders of each country and hence this may be a cultural influence that could be related to the author's intuition when selecting character names. The KW dialect novels used the names DAry /d Q a:rej/ 'Dhari', mšAry /mSa:rej/ 'Mshari' and SbAH /s Q Uba:è/ 'Subah' for male characters while the names sbyjh /sIbi:tSE/ 'Sebichah' and fwzy∼h /fozIjjE/ 'Fawziyya' were noticed to be prominent for female characters. The second noticed trend is the use of Hijri dates in SA dialect novels, which is explained by the country's official calendar use of the Hijri date. This trend was only noticed in SA dialect novels. Thirdly, the use of commonly spoken words that could be directly traced to a particular dialect such as hAlHzzh /hElèEzzE/ 'Now' and yA mςw∼d /ja: mQEwwEd/ 'O man' in KW dialect, bzrAn /bIzra:n/ 'Little kids', wrak /wEra:k/ as in wrAk mA tjAwb /wEra:k ma: tdZa:wIb/ 'Why are you[2MS] not answering?' which is traced to SA dialect and AE words such as sydA /si:dE/ 'Straight forward', Aqrb /Igr@b/ 'Come in, please!' and xAšwqh /xa:Su:gE/ 'Spoon'. The above are trends noticed when annotating over a thousand GA novels that helped in adding efficiency to the task. These trends were noticed as the process progressed and selecting a dialect was only completed once parts of the story were read, alongside facts provided by the author, which include providing an insight to the readers that the story will be written in a particular dialect and/or constantly providing details of where events took place (i.e. city and/or country names). Following on the annotation effort, we present the distribution of the dialects across the corpus, see Table 2. We have observed that 92% of the entire corpus is actually written in GA with SA being the most dominant and BH the least. There is also around 10% that is identified as GA (other) which are the cases of a novel containing a combination of several GA dialects that is due to multiple writers with different dialects or due to the existence of different characters in the novel. It was sometimes hard to differentiate through the text between the three dialects of OM, QA and AE even with a native speaker annotating, hence these 5 Arabic transliteration is presented in the Habash-Soudi-Buckwalter scheme [START_REF] Habash | On Arabic Transliteration[END_REF]: (in alphabetical order) Â b t θ j H x d ð r z s š S D T Ď ς γ f q k l m n h w y and the additional symbols: ' , Â , Ǎ , Ā , ŵ , ŷ , h , ý .

Preliminary Investigation into GA Annotation

We describe next a pilot study in semi-automatic annotation of GA. We use the MADAMIRA [START_REF] Pasha | MADAMIRA: A Fast, Comprehensive Tool for Morphological Analysis and Disambiguation of Arabic[END_REF] morphological tagger (which works in two modes: MSA and EGY) and manually change its output in accordance to the orthography and morphology guidelines that are discussed next in this section.

Orthography Guidelines GA speakers who write in the dialect produce spontaneous inconsistent spellings that sometimes reflect the phonology of the GA, and other times the word's cognate relationship with MSA. We follow the work of [START_REF] Habash | Con-ventional Orthography for Dialectal Arabic[END_REF] for CODA in order to overcome these inconsistencies. There are the general CODA rules that apply for every dialect, among which is affix spelling. Affix spelling includes the spelling of the Ta Marbuta; if the Ta Marbuta is at the end of the word it will always be h and not h regardless of the pronunciation. When inside a word (before a clitic) Ta Marbuta will become , (e.g. syArh HSh jdydh /sEjja:rEt èis Q s Q ah jIdi:dEh/ 'Hissa's car is new', syArthA /sajja:retha:/ 'her car'). Following on the discussion about GA dialect properties in section 3., we extend several aspects of the original CODA. The root consonant mapping rules are extended to cover the GA pronunciations that are unseen in other dialects, see Table 3. Another aspect is the spelling of the 2nd person singular feminine pronominal clitic; if spelled differently than the k /kI/ equivalent in MSA, it is mapped to j /dZ/, (e.g. ktAbš /kta:bIS/, ktAbts /kta:bIts/, and ktAbj /kta:bItS/ 'Your [FS] book', becomes ktAbj /kta:bItS/ but not ktAbik /kta:bIk/) in CODA. As with the original CODA for EGY, we also maintain a list of exceptional spellings for uniquely dialectal words. One example in GA is the spelling of the perfective verb kAn /ka:n/ 'was' and its variant jAn /tSa:n/: the perfective verb form is used as in MSA, however the other variant is considered a modal auxiliary [START_REF] Brustad | The Syntax of Spoken Arabic: A Comparative Study of Moroccan, Egyptian, Syrian, and Kuwaiti Dialects[END_REF]. Both spellings are kept due to the difference in their usage despite the fact that they share the same origin. Another example is the the negation particles mb /mUb/ CODA Pron. variation Example q /q/ or /g/ or /dZ/ qid∼Am /dZIdda:m/ 'Front' elm /gEl Q Em/ 'pen(cil)' k /k/ or /tS/ or /ts/ kbd /tSEbd/ 'Liver' j /dZ/ or /j/ jls /jIlas/ 'He sat' š /S/ or /tS/ šAy /tSa:j/ 'Tea'

Table 3: GA root consonants mapping rules 'not' and mAnyb /mEni:b/ 'I'm not', both of which have a number of non-CODA variants such as mwb and mnyb, respectively. The complete guidelines for the GA CODA will be available separately as a technical report. An example of the application of several CODA rules is presented in Table 4 Morphology Guidelines For every input word MADAMIRA produces a list of analyses specifying every possible morphological interpretation of that word, covering all morphological features of the word (diacritization, part-of-speech (POS), lemma, and 13 inflectional and clitic features). MADAMIRA then applies a set of models (support vector machines and N-gram language models) to produce a prediction, per word in-context, for different morphological features, such as POS, lemma, gender, number or person. A ranking component scores the analyses produced by the morphological analyzer using a tuned weighted sum of matches with the predicted features. The top-scoring analysis is chosen as the predicted interpretation for that word in context [START_REF] Pasha | MADAMIRA: A Fast, Comprehensive Tool for Morphological Analysis and Disambiguation of Arabic[END_REF]. We follow a similar approach that was used to morphologically annotate both the EGY and LEV corpora. We select the following set of features with their initial values from the output of MADAMIRA-EGY on a given GA text to annotate:

• Word orthography We follow the previously discussed orthography guidelines.

• Morphemic tokenization A word is split into its morphemes and stem.

• Part of Speech We use the MADAMIRA POS tag set

• CATiB 6 POS Except the tag for passive verbs [START_REF] Habash | CATiB: The Columbia Arabic Treebank[END_REF].

• Lemma Diacritized form of the lemma.

• English gloss The English translation of the lemma Beside the above guidelines, there exist cases of erroneous merging and splitting of words that gets no analysis from the automatic annotation. For merged words, we place a '#' symbol where a split should happen, this fix aggregate through all the other annotated features. In the case where there is a split, we place the '#' symbol at the end of the first split part to indicate the merging position.

Table 5 shows an annotation example following the above guidelines. Where green and red shaded cells indicates a change.

Evaluation We conduct an evaluation of the quality of automatic morphological annotation tools (taggers) on this corpus to assess the amount of effort needed to manually annotate it. Following the annotation guidelines discussed above, we manually annotated around 4K words from four different novels with a goal to capture different dialects, styles of writing, . . . etc. An example of an annotated sentence is shown in Table 5. As a preliminary experiment, we investigated the frequency of out-of-vocabulary (OOV) words in both systems of MADAMIRA: MSA and EGY. The Egyptian model OOV (5.6%) was almost half that of MSA (9.3%), suggesting it is better to work with Egyptian as the base system for manual annotation.

Feature We evaluated using the accuracy measure for word orthography, morphemic tokenization, POS, CATiB POS and lemma against the output of both models of MADAMIRA: MSA and EGY. Table 6 shows the results of the the evaluation for all words. These numbers allow us to assess the basic quality of the these tools on GA. As expected, MADAMIRA-EGY outperforms MADAMIRA-MSA between 4 and 13% absolute on different metrics, confirming that it is better to use it as a baseline. This is similar to results reported by [START_REF] Jarrar | Building a Corpus for Palestinian Arabic: a Preliminary Study[END_REF] on Palestinian Arabic.

Error Analysis We manually investigated the four sets of 100 words from different parts of the MADAMIRA-EGY annotated sub-corpus (total 400 words, with an average of 30 words containing at least one error). 52.1% of the errors are likely due the wrong assignment of POS especially in proper nouns that look like nouns or adjectives. Another major source of error is the lemma 18.2% and out of vocabulary related errors are 16.5% and this happens for two main reasons, either the word is never seen before or because of a typo. Finally, errors that come from a mistake in merging or splitting word tokens, typos and tokenization words combine around 13%.

Gumar Interface

Following the collection of the corpus, we created a simple online interface that is specific for searching the corpus. 6 The entire text of the corpus is stored in a relational database in an optimized manner. The lookup of the data is a simple search query that matches the user input to either a word token, lemma or stem form. Through the website interface, the rows of results are displayed to the user including the full context, word analysis that includes the POS, lemma, stem and gloss entries in addition to the information about the novel the word belongs to. See Figure 1.

Conclusion and Future Work

We collected the Gumar Corpus that consists of 100 million words from 1200 forum novels. We annotated the corpus for sub-dialect information at the document level of the novels in addition to the informations about the name and the writer's name of the novel. We also performed a preliminary investigation on the annotation of GA text.

As an initial experiment we annotated around 4K words from four different novels using proposed orthography and morphology guidelines that followed previous efforts. We compared our gold annotations to the automatic annotations provided by MADAMIRA on its both MSA and EGY modes. The evaluation of the accuracy suggests that using MADAMIRA-EGY automatic annotations as a starting point for manual annotation of GA speeds up the process. We plan to semi-automatically annotate the corpus and include a careful manual check at a large portion of it (1M words). We are also looking forward to building a morphological analyzer for GA. We also plan to use the Gumar Corpus dialect annotations for some NLP tasks such as dialect identification. We will make this corpus and its annotations publicly available.

Acknowledgments

We would like to thank Dimitrios Ntelitheos for helpful discussions. We would also like to thank Mustafa Jarrar and

Figure 1 :

 1 Figure 1: Online web interface for browsing Gumar

  , which supports both MSA and EGY. Eskander et al. (2013) describe a technique for automatic extraction of morphological lexicons from morphologically annotated corpora and demonstrate it on EGY. Al-Shargi et al. (2016) apply the technique of Eskander et al. (

Table 1 :

 1 Statistics on the Gumar Corpus in certain dialects (e.g. some Saudi dialects) but is realized in some other dialects as /tS/, /S/, or /ts/.

	Gumar Corpus
	Words	112,410,688
	Sentences	9,335,224
	Documents	1,236

The palatal /tS/ and the velar /k/ may both turn into the alveopalatal /tS/ as in /tSa:j/ 'tea', and /tSEf/ 'palm'. Moreover, The 2 nd singular feminine possessive and object pronoun /kI/ retains its phonological form

Table 2 :

 2 Distribution of Dialects across the Gumar Corpus cases we marked as GA (other) also. The rest of the corpus (7.93%) is mostly MSA (original text or translation attempts of existing non Arabic text) and other DA such as Egyptian, Iraqi, Levantine, ... etc.

	Dialect	Percentage
	SA	60.52
	AE	13.35
	KW	5.91
	OM	1.13
	QA	0.65
	BH	0.49
	GA (other)	10.03
	Arabic (other)	7.93

Table 6 :

 6 Results on evaluation of our Gold annotation against the output of MADAMIRA in both modes: MSA and EGY

		MADAMIRA-MSA MADAMIRA-EGY
	CODA	83.81	88.34
	Morph	76.16	83.62
	POS	72.37	80.39
	CATiB	76.28	81.51
	Lemma	64.03	77.02

Table 4 :

 4 Example of application of CODA rules

				MADAMIRA-EGY
	Raw		CODA	Morph	POS	CATiB 6	Lemma	Gloss
		zyAd	zyAd	zyAd	noun_prop	PROP	ziyAd	Ziad
	:	:	:	:	punc	PNX	:	:
		lysA'	lysA'	lysA'	noun	NOM	Âaloyas	valiant
		mysA'	mAysA'	mA+y+sA'	verb	VRB	ÂasA'	be_harmed
		AntwlAzm	NOAN	NOAN	NOAN	NOAN	NOAN	NOAN
		tjAbwn	tjAbwn	t+jAb+wn	verb	VRB	ÂajAb	be_answered
		ς	ςlY	ςlY	prep	PRT	ςalaY	on
		kl	kl	kl	noun_quant	NOM	kul∼	all
		Aly	Ally	Ally	pron_rel	NOM	All∼iy	which
		yqwlkm	yqwlkm	y+qwl+km	verb	VRB	qAl	said
				Manual Annotation
	Raw		CODA	Morph	POS	CATiB 6	Lemma	Gloss
		zyAd	zyAd	zyAd	noun_prop	PROP	ziyAd	Ziad
	:	:	:	:	punc	PNX	:	:
		lysA'	lysA'	lysA'	noun_prop	PROP	laysaA'	Laysaa
		mysA'	mysA'	mysA'	noun_prop	PROP	MayosaA'	Maysaa
		AntwlAzm	Antw#lAzm	Antw#lAzm	pron#noun	NOM#NOM	Antw#lAzim	you#necessary
		tjAbwn	tjAwbwn	t+jAwb+wn	verb	VRB	jAwab	comply
		ς	ςlY	ςlY	prep	PRT	ςalaY	on
		kl	kl	kl	noun_quant	NOM	kul∼	all
		Aly	Ally	Ally	pron_rel	NOM	All∼iy	which
		yqwlkm	yqwlh#lkm	y+qwl+h#l+km	verb#prep	VRB#PRT	qAl#la	said#to

Table 5 :

 5 Example of manual annotation following the orthography and morphology guidelines. Columns represent features to be annotated and rows represent words. NOAN means that no analysis was given automatically.

Phonetic transcription is presented in IPA.

www.graaam.com

There are no copyright claims by the anonymous writers or organizers; and we do not claim any copyrights to the text. We will make the cleaned up and extended versions of the data fully publicly available.