Olivier Devillers

Marc Glisse

Delaunay triangulation of a random sample of a good sample has linear size

Keywords:

A good sample is a point set such that any ball of radius contains a constant number of points. The Delaunay triangulation of a good sample is proved to have linear size, unfortunately this is not enough to ensure a good time complexity of the randomized incremental construction of the Delaunay triangulation. In this paper we prove that a random Bernoulli sample of a good sample has a triangulation of linear size. This result allows to prove that the randomized incremental construction needs an expected linear size and an expected O(n log n) time.

Part of this work is supported by the Advanced Grant of the European Research Council GUDHI (Geometric Understanding in Higher Dimensions).

La triangulation de Delaunay d'un échantillon aléatoire d'un bon échantillon a une taille linéaire

Résumé :

Un bon échantillon est un ensemble de points tel que toute boule de rayon contienne un nombre constant de points. Il est démontré que la triangulation de Delaunay d'un bon échantillon a une taille linéaire, malheureusement cela ne suffit pas à assurer une bonne complexité à la construction incrémentale randomisée de la triangulation de Delaunay. Dans ce rapport, nous démontrons que la triangulation d'un échantillon aléatoire de Bernoulli d'un bon échantillon a une taille linéaire. Nous en déduisons que la construction incrémentale randomisée peut être faite en temps O(n log n) et espace O(n).

Mots-clés : Analyse probabiliste -Analyse dans le cas le pire -construction incrémentale randomisée 1 Introduction

A good sample of some domain D ⊂ R d is a point set of size n in R d such that any ball centered in D of radius contains a constant number of points. When we enforce a hypothesis of good distribution of the points in space, a volume counting argument ensures that the local complexity of the Delaunay triangulation around a vertex is bounded by a constant (dependent on and d but not on the number of points). Unfortunately, to be able to control the complexity of the usual randomized incremental algorithms [START_REF] Amenta | Incremental constructions con BRIO[END_REF][START_REF] Boissonnat | On the randomized construction of the Delaunay tree[END_REF][START_REF] Clarkson | Applications of random sampling in computational geometry[END_REF][START_REF] Devillers | The Delaunay hierarchy[END_REF], it is not enough to control the final complexity of the triangulation, but also the complexity of the triangulation of a random subset.

One would expect that a random sample of size k of a good sample is also a good sample with high probability. Actually this is not quite true, it may happen with reasonable probability that balls of volume O 1 k may contain log n points or that a ball of volume Ω Ä log k k ä does not contain any point. Thus this approach can transfer the complexity of a good sample to the one of a random sample of a good sample but losing log factors.

In this paper, we study directly the Delaunay triangulation of a random sample of a good sample and deduce results about the complexity of randomized incremental constructions.

Results, Definitions, and Notations

We define several sampling notions, our point set is in T d the flat torus of dimension d to avoid boundary conditions (T = R/Z): Definition 1. A set X of n points in T d is an (ε, κ)-sample if any ball of radius contains at least one point and at most κ points. Definition 2. A subset Y of set X is a Bernoulli sample of X of parameter α if each point of X belongs to Y with probability α independently. Definition 3. A subset Y of set X is a uniform sample of X of size k if Y is any possible subset of X of size k with equal probability. This short note proves the two following theorems: Theorem 4. Given an (ε, κ)-sample X in T d , a Bernoulli sample Y of probability α of X , and a point p, the expected number of faces of dimension i of the Delaunay triangulation of Y ∪ {p} that contain p is at most 72 di+O(d+i(log iκ)) . In particular this number is a constant with respect to n and α. An analogous of Theorem 4 for uniform samples instead of Bernoulli samples is probably true but more difficult to prove. Since Theorem 4 suffices to deduce Theorem 5, we leave the result for uniform sample as a conjecture.

We denote by Σ(p, r) and B(p, r) the sphere and the ball of center p and radius r respectively. (Z) denotes the cardinality of the set Z.

The volume of the unit ball of dimension d is denoted V d , the area of its boundary is denoted

S d-1 , the formulas are V d = π d 2 Γ( d 2 +1
) and S d = 2πV d-1 .

RR n°9082

3 Bernoulli Sample Lemma 6. For any point p, we can construct a set B of balls of radius 1 such that any ball of radius bigger than 3 having p on its boundary encloses a ball of B, and

(B) ≤ A d = 2 √ π Γ d+1 2 Γ d 2 Å 18 √ 35 ã d-1 1 3 3 Σ(p, 3) p √ 35 3 Σ(z, r) z x y ≤ 3 u w Σ(x, 3) ≤ 1 ≤ 1 ≤ 1
Proof. We will build a packing of Σ(p, 3). A ball B of radius 1 centered on Σ(p, 3) verifies:

Σ(p, 3) ∩ B has a (d -1)-volume bigger that the (d -1)-volume of a (d -1) ball of radius √ 35
6 (see Figure above). Now we consider a set of balls B centered on Σ(p, 3) such that the intersections of these balls with Σ(p, 3) are disjoint and B is maximal for this property.

Let Σ(z, r) be a sphere of radius bigger than 3 having p on its boundary (red boundary of blue ball in the figure). Let x be pz ∩ Σ(p, 3), then Σ(x, 3) passes through p and is inside tangent in p to Σ(z, r). Since B is maximal Σ(x, 1) (pink in figure) intersects a unit ball B(y, 1) ∈ B (green on figure) in some point u. For any point w ∈ B(y, 1) we have xw ≤ xu + uy + yw ≤ 3 and thus Σ(x, 3) encloses B(y, 1).

The (d -1)-volume of Σ(p, 3) is S d-1 3 d-1 , the (d -1)-volume of Σ(p, 3) ∩ B is bigger than V d-1 Ä √ 35 6 ä d-1 for all B ∈ B, thus the cardinality of B is bounded by S d-1 V d-1 Ä 18 √ 35 ä d-1
. Plugging the values of V d-1 and S d-1 gives the result. Proof. Consider a maximal set of disjoint balls of radius ρ 2 with center inside the unit ball, the balls with the same centers and radius ρ cover the unit ball (otherwise it contradicts the maximality). By a volume argument we get that the number of balls is bounded from above by

V d (1+ ρ 2 ) d V d ( ρ 2 ) d ≤ Ä 3 ρ ä d for ρ < 1.
Lemma 8. Any maximal packing of the unit ball in dimension d by balls of radius ρ has a number of balls greater than (2ρ) -d .

Proof. Doubling the radii of the balls gives a covering, then the volume argument gives a lower bound of

V d V d (2ρ) d = (2ρ) -d .
Definition 9. Let F (p, r) be the event than the farthest Delaunay neighbor of p is at distance greater than r from p in the Delaunay triangulation of Y ∪ {p} where Y is a Bernoulli sample of parameter α of an (ε, κ)-sample X of T d .

Lemma 10.

P [F (p, 6r)] ≤ A d exp Ä -αr d (2 ) -d ä .
Proof. We consider B r the set B, defined at Lemma 6, scaled by r around p. If each ball of B r contains at least one point, we know that all Delaunay neighbors of p are inside Σ(p, 6r).

P [F (p, 6r)] ≤ P [∃B ∈ B r , B ∩ Y = ∅] ≤ B∈Br P [B ∩ Y = ∅] ≤ B∈Br (1 -α) (B∩X ) ≤ (B r ) (1 -α) ( r 2 ) d ≤ A d exp Å -α r 2 d ã ,
Inria where the last line uses the lower bound of Lemma 8.

Proof of Theorem 4. If the farthest Delaunay neighbor of p is at distance less than 6r, and k = (Y ∩ B(p, 6r)) then k i is a trivial bound on the number of Delaunay i-faces incident to p. Thus we will compute the following:

E [ (Delaunay i-faces incident to p)] ≤ E î (Y ∩ B(p, 6 )) i ó + ∞ j=1 P F (p, 6 • 2 j-1 ) E î Y ∩ B(p, 6 • 2 j ) i | F (p, 6 • 2 j-1
) ó

On the one hand, we remark that

E [ (Y ∩ B(p, 2r)) | F (p, r)] ≤ E [ (Y ∩ B(p, 2r))] ,
since the knowledge that the farthest neighbor is far implies that there are some points of X that do not belong to the sample Y and biases the probability in the above direction. On the other hand Lemma 2.2 in [START_REF] Devillers | Smoothed complexity of convex hulls by witnesses and collectors[END_REF] allows to deduce for any domain D:

E î (D ∩ Y) i ó ≤ i i E [ (D ∩ Y)] i .
It gives:

E [ (Delaunay i-faces incident to p)] ≤ i i E [ (Y ∩ B(p, 6 ))] i + ∞ j=1 P F (p, 6 • 2 j-1 ) i i E Y ∩ B(p, 6 • 2 j ) i ≤ i i α i (X ∩ B(p, 6 )) i + ∞ j=1 P F (p, 6 • 2 j-1 ) i i α i X ∩ B(p, 6 • 2 j ) i ≤ i i α i κ i 18 di + ∞ j=0
A d exp -α 2 j-2 d i i α i κ i 18 • 2 j di using Lemmas 7 and 10

≤ i i α i κ i 18 di 1 + A d ∞ j=0 2 dij exp -α2 dj-2d .
The function j 2 dij exp -α2 dj-2d is increasing between 0 and j 0 and decreasing between j 0 and ∞, with

j 0 = 2 + 1 d log 2 i α . Notice that the maximum of the function is 2 dij0 exp -α2 dj0-2d = 2 2di+i log 2 ( i α ) exp -α2 log 2 ( i α ) ≤ 4 di i α i . A stan-
dard sum to integral comparison yields:

Sum Integral + maximum RR n°9082 E [ (Delaunay i-faces incident to p)] ≤ i i α i 18 di κ i Ç 1 + A d 2 dij0 exp -α2 dj0-2d + A d ∞ j=0 2 dij exp -α2 dj-2d dj å ≤ i i α i 18 di κ i 1 + A d 4 di i α i + A d ∞ k=α2 -2d Ç k2 2d α å i exp(-k) dk kd ln 2 with k = α2 dj-2d ≤ i i κ i 72 di Å 1 + A d i i + A d ∞ k=0 k i-1 exp(-k) 1 d ln 2 dk ã ≤ i i κ i 72 di Ä 1 + A d i i + A d (i-1)! d ln 2 ä ≤ 3i 2i κ i 72 di A d .
4 From Bernoulli Sample to Uniform Sample of Size k

Proof of Theorem 5. Space complexity. Theorem 4 does not apply directly to the randomized construction of the Delaunay triangulation of X . When the points are inserted in a random order, the k th inserted point p k is a random point in a uniform sample of size k of X , the expected number of simplices of dimension i created by its insertion is

E [ (Delaunay i-faces incident to p k | (Y) = k)] .
To deduce the expected number of simplices created during the randomized incremental construction we have to sum on i and k.

The time complexity can be split in a location part and a construction part. The construction time is of the same order as the space complexity. The location time of an insertion in the usual randomized incremental construction of the Delaunay triangulation of a set X of n points relies on a backward analysis argument. In the classical history graph, the argument is a follows: when locating the n th point p n , we trace the conflicts 1 within the history of the construction of the Delaunay triangulation; the insertion of p k (2 ≤ k < n) creates m conflicts with p n if and only if p k p n is an edge of the triangulation of {p 1 , p 2 , . . . , p k , p n } incident to m simplices. Since p k is a random point q in {p 1 , p 2 , . . . , p k } we get as expected location time:

n-1 k=2 E   q∈Y; (Y)=k P [p k = q] • 1 [qpnedge of DT (Y∪{pn})] • (Delaunay d-simplices incident to edge qp n )   ≤ n-1 k=2 1 k • d • E [ (Delaunay d-simplices incident to p n in DT (Y ∪ {p n }) | (Y) = k)]
Bernoulli to uniform sampling. Thus, the number of simplices incident to a vertex needs to be controlled in the triangulation of a uniform sample of size k and not of a Bernoulli sample of probability α. Let f k and g α be the following random variables:

f k = (Delaunay i-faces of DT (Y ∪ {p}) incident to p) ,
where p is any point in the plane and Y is a uniform random sample of X of size k, and g α = (Delaunay i-faces of DT (Y ∪ {p}) incident to p) 1 A point is in conflict with a simplex if it belongs to its circumscribing ball.

Inria

where p is any point in the plane and Y is a Bernoulli sample of X of parameter α. Then the classical equation is First, we can prove that the expected number of simplices constructed in a randomized incremental construction is O(n):

E [g α ] = n k=0 Ç n k å α k (1 -α) n-k E [f k ] = n k=1 Ç n k å α k (1 -α) n-k E [f k ] since n k α k (1 -α) n-k (
O(1) = 1 0 E [g α ] dα = n k=1 Ç n k å E [f k ] 1 0 α k (1 -α) n-k dα = n k=1 Ç n k å E [f k ] 1 (n + 1) n k = 1 n+1 n k=1 E [f k ]
Then, we can prove that the expected complexity of localizing the last point in the Delaunay triangulation of a uniform sample of size k is O(log n).

We can write

1 0 E[gα] α dα = n k=1 n Ç n -1 k -1 å E[f k ] k 1 0 α k-1 (1 -α) n-k dα = n k=1 n Ç n -1 k -1 å E[f k ] k (n -k)!(k -1)! n! = n k=1 E[f k ] k .
To compute

Theorem 5 .

 5 Given an (ε, κ)-sample X in T d , the randomized incremental construction of the Delaunay triangulation needs O(n log n) expected time and O(n) expected space.

Lemma 7 .

 7 Let ρ ≤ 1, there exists a covering of the unit ball in dimension d by balls of radius ρ with a number of balls smaller than Ä 3 ρ ä d .

  the binomial distribution) is the probability that a Bernoulli sample of parameter α has size k. Theorem 4 gives E [g α ] = O(1).

αd d- 1 +

 1 dα we can use E [g α ] = O(1) (Theorem 4) except in the neighborhood of 0 where we use a separate, naive boundE [g α ] ≤ E î (Y) d ó ≤ d d E [ (Y)] d = d d (αn) dusing again Lemma 2.2 from[START_REF] Devillers | Smoothed complexity of convex hulls by witnesses and collectors[END_REF]. O(1) • log n = O (log n) .

Acknowledgements. This work follows a question asked by Jean-Daniel Boissonnat and was solved during the 16 th INRIA-McGill-Victoria Workshop on Computational Geometry at the Bellairs Research Institute. The authors wish to thank all the participants for creating a pleasant and stimulating atmosphere.

RR n°9082


Marwa Naili
email: maroua.naili@riadi.rnu.tn

Anja Habacha Chaibi

Henda Ben Ghézala

Arabic topic identification based on empirical studies of topic models

Keywords: Identification thématique, Topic models, Allocation de Dirichlet Latente, hyperparamètres α et β de LDA, lemmatiseurs Arabes Topic identification, Topic models, Latent Dirichlet Allocation, LDA hyperparameters α and β, Arabic stemmers

Cet article met l'accent sur l'identification thématique pour la langue arabe basée sur les topic models. Nous étudions l'Allocation de Dirichlet Latente (LDA) comme une méthode non supervisée pour l'identification thématique. Ainsi, une étude approfondie de LDA a été effectuée à deux niveaux: le processus de lemmatisation et le choix des hyper-paramètres. Pour le premier niveau, nous étudions l'effet des différents lemmatiseurs sur LDA. Pour le deuxième niveau, nous nous focalisons sur les hyper-paramètres α et β de LDA et leurs impacts sur l'identification. Cette étude montre que LDA est une méthode efficace pour l'identification thématique Arabe surtout avec le bon choix des hyper-paramètres. Un autre résultat important est l'impact élevé de l'algorithme de lemmatisation sur l'identification thématique.

Introduction

During the last few years, the number of textual documents has been vastly increasing. Thus, many techniques have been presented to deal with this big number of documents. However, the real challenge is to manage these documents based on their content, especially the thematic one. For this reason, topic identification and classification draw a lot of intention in research fields dealing with different types of documents (text [START_REF] Heinrich | Parameter estimation for text analysis[END_REF], XML [START_REF] Yassine | Réseaux bayésiens jumelés et noyau de Fisher pondéré pour la classification de documents XML[END_REF], etc). In fact, for the English and French languages, several methods and resources have been used for topic identification and classification such as domain ontology [START_REF] Jain | Automatic topic(s) identification from learning material: An ontological approach[END_REF], encyclopedic graph based on Wikipedia [START_REF] Coursey | Using encyclopedic knowledge for automatic topic identification[END_REF], LDA [START_REF] Hindle | Relating requirements to implementation via topic analysis: Do topics extracted from requirements make sense to managers and developers?[END_REF], extended LDA model named DLDA [START_REF] Xu | Web Event Topic Analysis by Topic Feature Clustering and Extended LDA Model[END_REF], and classical techniques such as TF-IDF [START_REF] Bigi | A Fuzzy Decision Strategy for Topic Identification and Dynamic Selection of Language Models[END_REF], Cache Model [START_REF] Bigi | A Fuzzy Decision Strategy for Topic Identification and Dynamic Selection of Language Models[END_REF], Topic unigrams [START_REF] Bigi | A Fuzzy Decision Strategy for Topic Identification and Dynamic Selection of Language Models[END_REF] and SVM [START_REF] Vapnik | The natural of statitical learning theory[END_REF]. However, for the Arabic language, there is a flagrant lack of research in this field. This can be explained by the high complexity of this language and the lack of Arabic resources. In this context, we will focus on Arabic topic identification by presenting an overview of this research field. Moreover, we will study in depth the LDA method as an unsupervised method for Arabic topic identification. In this study, we will focus on LDA's hyper-parameters and the impact of the stemming process on the process of topic identification. This paper is organized as follows: Section 2 presents an overview of Arabic topic identification; Section 3 describes some Arabic stemmers; Section 4 deals with LDA process and its different hyper-parameters; Section 5 is dedicated to the evaluation and the discussion; finally, the conclusion and future works are presented in section 6.

Overview of Arabic topic identification

Topic identification is the process of identifying the topic of a textual unity which can be a paragraph, a segment or an entire text document. According to most researchers, a topic is a cluster of words which are closely related to the topic. Clusters depend on the stemming process that specifies the type of words (root, stem, etc). For the Arabic language, there is a flagrant lack of research in the field of topic identification. In fact, few works dealing which the Arabic topic identification have been presented such as the works of Abbas et al. [START_REF] Berkani | A TOPIC IDENTIFICATION TASK FOR MODERN STANDARD ARABIC[END_REF][START_REF] Abbas | MULTI-CATEGORY SUPPORT VECTOR MACHINES FOR IDENTIFYING ARABIC TOPICS[END_REF][START_REF] Abbas | TR-CLASSIFIER AND KNN EVALUATION FOR TOPIC IDENTIFICATION TASKS[END_REF][START_REF] Abbas | Evaluation of Topic Identification Methods on Arabic Corpora[END_REF], Zrigui et al [START_REF] Zrigui | Arabic text classification framework based on latent dirichlet allocation[END_REF], Kelaiaia and Merouani [START_REF] Kelaiaia | Clustering with Probabilistic Topic Models on Arabic Texts[END_REF], Koulali et al. [START_REF] Koulali | Arabic Topic Detection using automatic text summarisation[END_REF], Koulali and Meziane [START_REF] Koulali | Feature Selection for Arabic Topic Detection Using Named Entities[END_REF] and Alsaad et Abbod [START_REF] Alsaad | Enhanced Topic Identification Algorithm for Arabic Corpora[END_REF].

In 2005, Abbas et al. [START_REF] Berkani | A TOPIC IDENTIFICATION TASK FOR MODERN STANDARD ARABIC[END_REF] have evaluated TF-IDF and SVM in the field of Arabic topic identification. In fact, TF-IDF allows the construction of a vector space. Each vector represents a document by the combination between TF(w,d) and IDF(w). The topic with the highest similarity with the document will be considered as the document's topic. On the other hand, SVM is a supervised method which classifies documents into two classes by constructing a hyperplane separator in the 𝑅 𝑁 vector space. As result, Abbas et al. [START_REF] Berkani | A TOPIC IDENTIFICATION TASK FOR MODERN STANDARD ARABIC[END_REF] proved that SVM outperforms TF-IDF by having the best values of precision and F-measure. In 2009, Abbas et al. [START_REF] Abbas | MULTI-CATEGORY SUPPORT VECTOR MACHINES FOR IDENTIFYING ARABIC TOPICS[END_REF] used the MSVM method to resolve the problem of multi-category classification. In fact, when the number of categories is superior than 2, the MSVM method is used. The idea of this method is to find n hyperplanes with n corresponds to the number of categories. Later, Abbas et al. [START_REF] Abbas | TR-CLASSIFIER AND KNN EVALUATION FOR TOPIC IDENTIFICATION TASKS[END_REF][START_REF] Abbas | Evaluation of Topic Identification Methods on Arabic Corpora[END_REF] proposed their own technique for topic identification named TR-Classifier. It is based on triggers which are identified by using the Average Mutual Information. In fact, topics and documents are presented by triggers which are a set of words that have the highest degree of correlation. Then, based on the TR-distance, the similarity is calculated between triggers to identify the document's topic.

Zrigui et al [START_REF] Zrigui | Arabic text classification framework based on latent dirichlet allocation[END_REF] have proposed a new hybrid algorithm for Arabic topic identification named LDA-SVM. This algorithm is based on the combination of LDA and SVM. The LDA method is used to classify documents. Then the SVM method is employed to attach class label. The idea of this combination is to reduce the feature dimension by LDA before applying the SVM method.

Kelaiaia and Merouani [START_REF] Kelaiaia | Clustering with Probabilistic Topic Models on Arabic Texts[END_REF] proposed another way of using LDA in topic identification. In fact, they employed topic models more directly by using the documents distribution over topics for Arabic topic identification.

Koulali et al. [START_REF] Koulali | Arabic Topic Detection using automatic text summarisation[END_REF] proposed to use automatic text summarization for Arabic topic identification. In fact, they used Gen-Summ to generate documents summaries. Then they used the cosine measure to calculate the similarity between the corresponding vectors of topics and documents summaries which are represented by TF-IDF. Moreover, Koulali and Meziane [START_REF] Koulali | Feature Selection for Arabic Topic Detection Using Named Entities[END_REF] have used named entities for Arabic topic identification. The idea of this approach is to reduce the dimension of vectors by using only the segments bounded by named entities pairs. Then, the mutual information is used to calculate similarity between topics and documents.

Alsaad and Abbod [3] also used the TF-IDF for Arabic topic identification. In this work, more attention has been given to the pre-processing step. Alsaad and Abbod [START_REF] Alsaad | Enhanced Topic Identification Algorithm for Arabic Corpora[END_REF] proposed their own root-based Stemmer named Alsaad Stemmer. Then they compared it to the Light Stemmer which is a lemmatization algorithm. As result, they proved that Alsaad Stemmer outperforms Light Stemmer. In fact, it leads to a smaller index size and more important better topics representations by avoiding term repetition of similar words or words which have the same root.

The major limit of these different methods is that a training step is necessary to identify the topics and to construct a vocabulary for each topic. Thus, we opted to use the unsupervised method LDA. That means that there is no need to a training step because topics are identified in the process of topic identification. Moreover, promising results have been obtained by using LDA for both English and Arabic topic identification [START_REF] Hindle | Relating requirements to implementation via topic analysis: Do topics extracted from requirements make sense to managers and developers?[END_REF][START_REF] Kelaiaia | Clustering with Probabilistic Topic Models on Arabic Texts[END_REF][START_REF] Zrigui | Arabic text classification framework based on latent dirichlet allocation[END_REF][START_REF] Xu | Web Event Topic Analysis by Topic Feature Clustering and Extended LDA Model[END_REF].

Arabic stemmers

Arabic language is one of the most complex and ambiguous language because of its wide variety of grammatical forms and its complex morphology. Thus, the stemming process is more difficult for the Arabic language than other languages. The stemming process aims to find the lexical root or lemma of words by removing prefixes and suffixes which are attached to its root. As an example of Arabic stemmers we mention:

-Khoja Stemmer [START_REF] Khoja | Stemming Arabic text[END_REF]: it extracts the root of a word by removing the longest suffix and prefix and then by matching the rest with verbal and nouns patterns.

-ISRI Arabic Stemmer [START_REF] Taghva | Arabic stemming without a root dictionary[END_REF]: it extracts the root of a word. But, unlike Khoja Stemmer, it doesn't use any root dictionary or lexicon.

-The Buckwalter Arabic Morphological Analyzer [START_REF] Buckwalter | Buckwalter Arabic morphological analyser version 2.0[END_REF]: it returns the stems of words based on lexicons of stems, prefixes, suffixes and morphological compatibility tables.

-Light Stemmer [START_REF] Larkey | Light stemming for Arabic information retrieval[END_REF]: Unlike Khoja Stemmer, it removes some defined prefixes and suffixes instead of extracting the original root words.

According to different studies [START_REF] Taghva | Arabic stemming without a root dictionary[END_REF][START_REF] Larkey | Light stemming for Arabic information retrieval[END_REF] the most efficient stemmers are Khoja and Light Stemmers. These two stemmers are available freely on the web and might be the only available Open Source ones. Thus, we will study Khoja and Light Stemmers to evaluate the effect of the stemming process on the topic identification.

Latent dirichlet allocation (LDA)

LDA [START_REF] Blei | Latent dirichlet allocation[END_REF] is a generative model in which documents are represented as a mixture of topic. Each topic is a multinomial distribution over words that depend on the stemming process. Therefore, for each document w in the corpus D, the generative process is:

1. We choose N (a document is a sequence of N words) according to Poisson distribution (N ~ Poisson(𝜉)) 2. We choose 𝜃 ( 𝜃 𝑑 is the distribution over the topic of the document d) according to dirichlet allocation (𝜃 ~ 𝐷𝑖𝑟𝑖𝑐ℎ𝑙𝑒𝑡(𝛼))

3. For each of the N words 𝑤 𝑛 : Choose a latent topic 𝑧 𝑛 according to a multinomial distribution and choose a word 𝑤 𝑛 from 𝑝 (𝑤 𝑛 |𝑧 𝑛 , 𝛽) The 𝜃 variable takes values in the (k-1) simplex and its density is equal to:

p(𝜃|𝛼) = Γ(∑ 𝛼 i k i=1 ) ∏ Γ(𝛼 i ) 𝑘 𝑖=1 𝜃 1 𝛼 1 -1 … 𝜃 𝑘 𝛼 k -1 (1)
Where 𝛼 ∈ ℝ 𝑘 , α i > 0, k is the number of topics and Γ(x) is the Gamma function.

According to Griffiths and Steyvers [START_REF] Griffiths | FINDING SCIENTIFIC TOPICS[END_REF] the choice of 𝛼 and 𝛽 can have important implications on LDA results. In their first study, they [START_REF] Griffiths | FINDING SCIENTIFIC TOPICS[END_REF] used 𝛼 𝑒𝑞𝑢𝑎𝑙 𝑡𝑜 50/𝑘 and 𝛽 𝑒𝑞𝑢𝑎𝑙 𝑡𝑜 0.1 where k is the number of topics. In fact, they used a small value of β to produce more topics that address specific areas of research. Yet in 2007, Steyvers and Griffiths [START_REF] Steyvers | Probabilistic topic models[END_REF] proved that hyper-parameters 𝛼 and 𝛽 depend on the number of topics and the vocabulary size. Moreover, Steyvers and Griffiths [START_REF] Steyvers | Probabilistic topic models[END_REF] recommended to use a different value of 𝛽 which is equal to 0.01 and the same value of 𝛼 which is equal to 50/k. However, Lu et al. [START_REF] Lu | Investigating task performance of probabilistic topic models: an empirical study of PLSA and LDA[END_REF] conduct an in-depth analysis of the choice of 𝛼 with 𝛽 = 0.01. According to this analysis, the performance of LDA is influenced by the initializing choice of 𝛼. This choice also depends on the field of application such as topic classification and information retrieval which are tested in this study. As result, they found that, for the topic classification, the optimal performance is obtained by 𝛼 between 0.1 and 0.5. Yet, for information retrieval, the optimal performance is obtained by 𝛼 between 0.5 and 2. However, according to Lu et al. [START_REF] Lu | Investigating task performance of probabilistic topic models: an empirical study of PLSA and LDA[END_REF], the best value of 𝛼 is not stable and it depends on the collection of documents used for tests. On the other hand, Heinrich [START_REF] Heinrich | Parameter estimation for text analysis[END_REF] estimated the values of 𝛼 and 𝛽 by using the information available from the Gibbs sampler. In fact, Heinrich [START_REF] Heinrich | Parameter estimation for text analysis[END_REF] showed that hyper-parameters are best estimated as parameters of the Dirichlet-multinomial distribution. Recently, Zhao et al. [START_REF] Zhao | BEST PRACTICES IN BUILDING TOPIC MODELS WITH LDA FOR MINING REGULATORY TEXTUAL DOCUMENTS[END_REF] studied LDA's hyper-parameters α and β. They proved that the best spot of α is between 0.01 and 0.1. Besides, β equal to 0.01 drives the best topic models. They also studied the impact of topics number. As result Despite the high performance of LDA, few works dealing with LDA were presented in the field of Arabic topic identification [START_REF] Zrigui | Arabic text classification framework based on latent dirichlet allocation[END_REF][START_REF] Kelaiaia | Clustering with Probabilistic Topic Models on Arabic Texts[END_REF]. According to these works, promising results have been obtained by LDA. However, we note that no one has studied LDA parameters in the field of topic identification. Therefore, in this paper, we will study in depth the LDA by studding the choice of hyper-parameters 𝛼 and β and more important the effect of different stemming algorithms to enhance the quality of topic identification.

Evaluation and discussion

In this section, we evaluated LDA with different stemmers. Thus, we presented three different versions: LDA-WS (Without Stemmer), LDA-KS (

Identified topics based on different stemmers

To study the impact of the stemming algorithm on LDA results, we fixed α to 0.1 and β to 0.01 based on the work of Zhao et al. [START_REF] Zhao | BEST PRACTICES IN BUILDING TOPIC MODELS WITH LDA FOR MINING REGULATORY TEXTUAL DOCUMENTS[END_REF]. These latter claimed that these values drive meaningful topics. Based on these values of hyer-parameters, we conducted the three versions of LDA on AL-Watan corpus. Table .2 shows the six identified topics by presenting only ten words for each topic. Based on table.2, we can note that the identified topics depend on the used stemmer. In fact, without using any stemming algorithms, the different topics were successfully identified by LDA-WS. However, the problem is that some words can figure more than once with different affix or suffix such as العام and العامة which mean public and such as قال and فقال which mean said.

Table 2. Identified topics based on LDA-WS, LDA-KS and LDA-LS with β=0.01 and α=0.1.

This problem is resolved by using Khoja stemmer which extracts the root of words. Thus, by employing LDA-KS, the topics are present by roots. The limit of this method is that a root can have several meaning such as علم which has many meaning like: knowledge, flag, aware. Therefore, by using Khoja Stemmer, we might lose the meaning. Yet, Light Stemmer removes only the prefix to maintain the meaning such as the word المنتخب (the team) without stemming, نخب (pledge) with Khoja Stemmer and منتخب (team) with Light Stemmer. As conclusion, all the six topics have been successfully identified by LDA. Moreover, Light Stemmer is the most efficient stemmer because it solves the problem of repetition (which is caused by the absence of stemmer: LDA-WS) and the loss of meaning (which is caused by Khoja Stemmer LDA-KS).

Study of the Dirichlet hyper-parameters α and β

In this section, we present an in-depth study of LDA hyper-parameters α and β.

 Hyper-parameter β:

The hyper-parameter β control the topic-word matrix. Thus, any change of β has an impact on the identified topics. In this work, we will study β based on two values: 0.1 and 0.01. Best to our knowledge, these values are the most used ones on the literature [START_REF] Steyvers | Probabilistic topic models[END_REF][START_REF] Griffiths | FINDING SCIENTIFIC TOPICS[END_REF][START_REF] Zhao | BEST PRACTICES IN BUILDING TOPIC MODELS WITH LDA FOR MINING REGULATORY TEXTUAL DOCUMENTS[END_REF][START_REF] Lu | Investigating task performance of probabilistic topic models: an empirical study of PLSA and LDA[END_REF]. Moreover, to test the impact of the hyper-parameter β, we fixed α to 0.1 such as in the work of Zhao et al. [START_REF] Zhao | BEST PRACTICES IN BUILDING TOPIC MODELS WITH LDA FOR MINING REGULATORY TEXTUAL DOCUMENTS[END_REF]. Table .3 shows the six identified topics by presenting only ten words for each topic for β equal to 0.1. Yet the identified topics for β equal to 0.01 are shown in table.2. For β equal to 0.01, all topics are well described for each version of LDA and each topic has it is own vocabulary. For β equal to 0.1, some topics are well identified such as the sport topic. However, for LDA-WS, we failed to identify the economy topic. As shown in table .3, the identified vocabulary to describe this topic is more related to the religion topic such as god, pray and Quran. Besides, some vocabulary is used for more than one topic such as the words الناس (people), يقول (said) and هللا (god) which are used to describe three different topics: culture, economy and religion. The same problem is detected for LDA-LS. In fact, the vocabulary used to describe local news topic is more related to the religion topic such as اسالم (Islam) and دين (religion) and to the culture topic such as كتب (write) and فكر (thought). As a conclusion, we can claim that for β equal to 0.01, best topic models can derived which is also proved by Zhao et al. [START_REF] Zhao | BEST PRACTICES IN BUILDING TOPIC MODELS WITH LDA FOR MINING REGULATORY TEXTUAL DOCUMENTS[END_REF], Steyvers and Griffiths [START_REF] Steyvers | Probabilistic topic models[END_REF] and Lu et al. [START_REF] Lu | Investigating task performance of probabilistic topic models: an empirical study of PLSA and LDA[END_REF]. choice of 𝛼. Yet, LDA-WS and LDA-KS are strongly influenced by 𝛼 and the best results are obtained by 𝛼 = 0.5. Furthermore, for 𝛼 = 0.5, the results of LDA-LS and LDA-KS are very close. Based on this result and the results of the stemming process for the topic identification, Light Stemmer is the most efficient stemmer to use with LDA. In the other hand, regardless of the value of 𝛼 and the stemming algorithm, the well identified topics are: sport (F = 91.86%), religion (F = 82.75%), economy (F = 75.13%). Yet, for the other topics, especially the culture topic, the performance of LDA is not stable. This can be explained by the fact that the vocabularies of these topics (culture, international and local news) are very close. But the vocabularies of sport, religion and economy are more representative and unique for each topic which leads to an efficient topic identification.

Beta=0

LDA-WS

LDA-KS

LDA-LS

 Comparison with related works dealing with LDA's hyper-parameters: If we compare our results with those of Steyvers and Griffiths [START_REF] Steyvers | Probabilistic topic models[END_REF], Lu et al. [START_REF] Lu | Investigating task performance of probabilistic topic models: an empirical study of PLSA and LDA[END_REF] and Zhao et al. [START_REF] Zhao | BEST PRACTICES IN BUILDING TOPIC MODELS WITH LDA FOR MINING REGULATORY TEXTUAL DOCUMENTS[END_REF], we can say that the field of application and the test corpus have an impact on the initialization of LDA hyper-parameter α as shown in table.5. For example Steyvers and Griffiths [START_REF] Steyvers | Probabilistic topic models[END_REF] and Lu et al. [START_REF] Lu | Investigating task performance of probabilistic topic models: an empirical study of PLSA and LDA[END_REF] used LDA for topic classification yet each one found a different value of α. This can be explained by the fact that they used different test corpora: TASA corpus which consists of text passages from educational materials and TDT2 corpus which consists of news stories. Another example is detected in Zhao et al. [START_REF] Zhao | BEST PRACTICES IN BUILDING TOPIC MODELS WITH LDA FOR MINING REGULATORY TEXTUAL DOCUMENTS[END_REF] and our work. In fact, for the same field of application, which is topic identification, Zhao et al. [START_REF] Zhao | BEST PRACTICES IN BUILDING TOPIC MODELS WITH LDA FOR MINING REGULATORY TEXTUAL DOCUMENTS[END_REF] found that the best spot of α is between 0.01 and 0.1based on MeSH corpus which is a medical corpus. Yet, in our case, we used articles from Al-Watan journal and we have found that α equal to 0.5 drives the best topic model. On the other hand, Lu et al. [START_REF] Lu | Investigating task performance of probabilistic topic models: an empirical study of PLSA and LDA[END_REF] used LDA for two different fields (topic classification and information retriveal). As results, they proved that the value of α varies according to the field of application. However, the β value 0.01 drives the best topic model independent from the used test corpus and the field of application.

Work

Field

Comparison between topic identification methods

To evaluate our work and as shown in figure.1, we choose to compare our methods (LDA-KS and LDA-LS) with the works of Abbas et al. [START_REF] Abbas | Evaluation of Topic Identification Methods on Arabic Corpora[END_REF] and Koulali and Meziane [START_REF] Koulali | Feature Selection for Arabic Topic Detection Using Named Entities[END_REF]. The reason for this choice is that we used the same test corpus for the evaluation. Yet, we note that in these works [START_REF] Abbas | Evaluation of Topic Identification Methods on Arabic Corpora[END_REF][START_REF] Koulali | Feature Selection for Arabic Topic Detection Using Named Entities[END_REF], 90% of the corpus is used for the training step and only 10% for the test. This can explain the high performance of TF-IDF [START_REF] Abbas | Evaluation of Topic Identification Methods on Arabic Corpora[END_REF], MSVM [START_REF] Abbas | Evaluation of Topic Identification Methods on Arabic Corpora[END_REF], TR-Classifier [START_REF] Abbas | Evaluation of Topic Identification Methods on Arabic Corpora[END_REF] and the Named Entities approach (NE) [START_REF] Koulali | Feature Selection for Arabic Topic Detection Using Named Entities[END_REF]. However, as an unsupervised method which does not need any kind of training step, the results of LDA-KS and LDA-LS are promising. In fact, dispute culture and economy topics, the result for the rest of topics are comparable and even better some times. For example, for the international news topic, LDA-KS and LDA-LS are better than TF-IDF, MSVM and TR-classifier.

Conclusion

In this paper, we presented a deep study of LDA in the field of Arabic topic identification. In fact, we studied the effect of the stemming process on topic identification by using Arabic stemmers (Khoja and Light Stemmers). Based on our evaluation, LDA depends on the stemming algorithms and Light Stemmer is the best choice to use. Besides, we studied in depth the two hyper-parameters of LDA. The first one is β which has an impact on the identified topics. The second one is α which influences the distribution of documents over topics. As result, we showed that the choice of these hyper-parameters influences the performance of LDA and the best result are obtained by α equal to 0.5 and β equal to 0.01. Thus, based on the best choice of hyper-parameters and the stemming algorithm, the result of LDA is very promising in the field of topic identification. For further studies, we will use LDA for topic segmentation to realize a complete topic analysis of Arabic documents. Moreover, it will be interesting to use other Arabic stemmers in order to be more confident in the stemming process. Furthermore, it will be interesting to conduct a complete topic analysis based on topic models (LDA) and word embeddings (LSA, GloVe and Word2Vec).

Figure 1 .

 1 Figure 1. Comparison with topic identification's related works.

  Therefore, given 𝛼 and 𝛽, the joint distribution of 𝜃, z and w is equal to:

	𝑝(𝜃, 𝑧, 𝑤|𝛼, 𝛽) = p(𝜃|𝛼) ∏ 𝑁 𝑛=1	p(𝑧 𝑛 |𝜃)	p(𝑤 𝑛 |𝑧 𝑛 , 𝛽)	(2)
	Finally, by integrating over 𝜃 and summing over z, the marginal distribution of a
	document is as follow (equation 3):
	𝑝(𝑤|𝛼, 𝛽) = ∫ p(𝜃|𝛼)( ∏ 𝑁 𝑛=1	∑ p(𝑧 𝑛 |𝜃)p(𝑤 𝑛 |𝑧 𝑛 , 𝛽) 𝑧 𝑛	) d𝜃

Table 1 . Al-Watan Corpus.

 1 Khoja Stemmer) and LDA-LS (Light Stemmer). For this evaluation, we use the Arabic benchmark Al-Watan 1 which contains articles from Watan newspaper and it covers six topics as shown in table 1. To report the evaluation results, we use three metrics: Recall (equation 4), Precision (equation 5) and F-measure (equation 6).

	Topic	Number of		Category	Average	Maximum	Minimum
		documents		size (Mo)	size (Ko)	size (Ko)	size (Ko)
	Culture	2782			17.1	6.1	54	2
	Economy	3468			18.7	5.4	59	2
	International news	2035			10.4	5.1	53	2
	Local news	3596			19.5	5.4	50	2
	Religion	3860			35.1	9.1	58	2
	Sport	4550			17.3	3.8	23	2
	Total	20291			118.1	-	-	-
		𝑹𝑒𝑐𝑎𝑙𝑙 =	𝑁𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑑𝑜𝑐𝑢𝑚𝑒𝑛𝑡𝑠 𝑐𝑜𝑟𝑟𝑒𝑐𝑡𝑙𝑦 𝑙𝑎𝑏𝑒𝑙𝑙𝑒𝑑 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑡𝑜𝑝𝑖𝑐 ′ 𝑠 𝑑𝑜𝑐𝑢𝑚𝑒𝑛𝑡𝑠	(4)
		𝑷𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 =	𝑁𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑑𝑜𝑐𝑢𝑚𝑒𝑛𝑡𝑠 𝑐𝑜𝑟𝑟𝑒𝑐𝑡𝑙𝑦 𝑙𝑎𝑏𝑒𝑙𝑙𝑒𝑑 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑙𝑎𝑏𝑒𝑙𝑙𝑒𝑑 𝑑𝑜𝑐𝑢𝑚𝑒𝑛𝑡𝑠	(5)
		𝑭 -𝑚𝑒𝑎𝑠𝑢𝑟𝑒 =	2 * 𝑅𝑒𝑐𝑎𝑙𝑙 * 𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 𝑅𝑒𝑐𝑎𝑙𝑙+𝑝𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛

Table 4 . LDA-WS, LSA-KS and LDA-LS results with

 4 𝜶 = 𝟎. 𝟏, 𝜶 = 𝟎. 𝟓 and 𝜶 = 𝟓𝟎/𝒌.

	.01		Culture	Economy	Intern News Local News Religion	Sport Average
		R	9.09%	70.10%	95.23%	84.73%	50.34%	85.25%	65.79%
	𝜶 = 𝟎. 𝟏	P	12.02%	80.95%	47.53%	58.73%	96.00%	99.59%	65.80%
		F	10.36%	75.13%	63.42%	69.38%	66.04%	91.86%	62.70%
		R	48.56%	70.30%	97.49%	81.01%	61.11%	84.13%	73.77%
	𝜶 = 𝟎. 𝟓	P	46.73%	79.72%	67.21%	56.98%	97.16%	99.43%	74.54%
		F	47.63%	74.72%	79.57%	66.90%	75.03%	91.14%	72.50%
		R	46.62%	69.49%	97.59%	80.70%	60.18%	84.28%	73.14%
	𝜶 = 𝟓𝟎/𝒌	P	45.40%	79.04%	66.22%	56.47%	97.11%	99.48%	73.95%
		F	46.00%	73.96%	78.90%	66.44%	74.31%	91.25%	71.81%
		R	68.40%	64.27%	78.52%	50.08%	71.35%	75.82%	68.07%
	𝜶 = 𝟎. 𝟏	P	55.53%	57.72%	52.62%	50.75%	93.58%	99.34%	68.26%
		F	61.30%	60.82%	63.01%	50.41%	80.96%	86.00%	67.08%
		R	69.55%	54.67%	95.92%	78.28%	73.70%	79.98%	75.35%
	𝜶 = 𝟎. 𝟓	P	55.76%	82.87%	76.28%	53.18%	94.33%	99.29%	76.95%
		F	61.90%	65.88%	84.98%	63.34%	82.75%	88.59% 74.59%
		R	68.44%	63.98%	90.47%	50.78%	70.72%	75.54%	69.99%
	𝜶 = 𝟓𝟎/𝒌	P	54.84%	57.79%	61.02%	50.79%	93.85%	99.39%	69.61%
		F	60.89%	60.73%	72.88%	50.78%	80.66%	85.84%	68.63%
		R	60.71%	63.32%	97.00%	77.11%	59.09%	83.49%	73.45%
	𝜶 = 𝟎. 𝟏	P 49.38%	75.88%	74.18%	54.20%	96.24%	99.19%	74.84%
		F 54.47%	69.03%	84.07%	63.66%	73.23%	90.67%	72.52%
		R	63.73%	62.51%	96.36%	77.14%	65.72%	83.54%	74.83%
	𝜶 = 𝟎. 𝟓	P 54.19%	75.54%	75.60%	54.57%	96.10%	99.19% 75.86%
		F 58.57%	68.41%	84.73%	63.92%	78.06%	90.69% 74.06%
		R	62.98%	62.92%	96.46%	76.42%	65.78%	83.36%	74.65%
	𝜶 = 𝟓𝟎/𝒌	P 54.12%	75.47%	75.50%	53.97%	96.10%	99.06%	75.70%
		F 58.21%	68.63%	84.70%	63.26%	78.10%	90.53%	73.90%

Table 5 . Related works about LDA's hyper-parameters.

 5

		of application	Test corpus	α	β
	Steyvers and	Topic classification	TASA corpus	50/k	0.01
	Griffiths [15]
	Lu et al. [28]	Topic classification	TDT2 corpus	[0.1,0.5]	0.01
		Information retrieval	Reuters-21578	[0.5,2]
	Zhao et al. [27]	Topic identification	MeSH corpus	[0.01, 0.1]	0.01
	Our work	Topic identification	Al-Watan corpus	0.5	0.01

Arabic Corpora. https://sites.google.com/site/mouradabbas9/corpora.

Culture

 Hyper-parameter α:

We study in depth the hyper-parameter 𝛼 by using three values 0.1, 0.5 and 50/k (k is number of topics which is 6 in our study). These values are proposed by [START_REF] Steyvers | Probabilistic topic models[END_REF][START_REF] Griffiths | FINDING SCIENTIFIC TOPICS[END_REF]. For 𝛽, we fixed it to 0.01 which is the most appropriate value to use based on section 5.2.

For each value of 𝛼, the obtained results of LDA-WS, LDA-KS and LDA-LS are illustrates in table.4. First of all, we remark that LDA-LS is independent from the

Culture