Abidi Karima

Kamel Smaïli

Measuring the comparability of multilingual corpora extracted from Twitter and others

Keywords: Twitter, Stemming, comparability measure

Multilingual corpora are widely exploited in several tasks of natural language processing, these corpora are principally of two sorts: comparable and parallel corpora. The comparable corpora gather texts in several languages dealing with analogous subjects but are not translations of each other such as in parallel corpora. In this paper, a comparative study on two stemming techniques is conducted in order to improve the comparability measure based on a bilingual dictionary. These methods are: Buckwalter Arabic Morphological Analyzer (BAMA) and a proposed approach based on Light Stemming (LS) adapted specifically to Twitter, then we combined them. We evaluated and compared these techniques on three different (English -Arabic) corpora: a corpus extracted from the social network Twitter, Euronews and a parallel corpus extracted from newspapers (ANN). The experimental results show that the best comparability measure is achieved for the combination of BAMA with LS which leads to a similarity of 61% for Twitter, 52% for Euronews and 65% for ANN. For a confidence of 40% we aligned 73.8% of Arabic and English tweets.

Introduction

Several applications in natural language processing necessitate parallel corpora. For classical issue of machine translation, this type of data is available: Europarl [START_REF] Koehn | Europarl: A parallel corpus for statistical machine translation[END_REF], Hansard [START_REF] Roukos | Hansard french/english[END_REF] and Hong Kong [START_REF] Tian | Um-corpus: A large englishchinese parallel corpus for statistical machine translation[END_REF]. Unfortunately, this kind of data is not available for all languages and especially for under-resourced ones and those used in social networks where the users allow themselves a certain freedom of writing. That is why nowadays, researchers make efforts to investigate comparable corpora because they are more available than parallel corpora which need a human effort to align corresponding sentences. Comparable corpora require alignment procedure to retrieve parallel segments within these documents. Consequently, we should determine which document is comparable to another one. To achieve this previous task, we need first to define precisely the concept of comparability. Li [START_REF] Li | Measuring and improving comparable corpus quality[END_REF] defines the comparability as follows: Two corpora in two different languages L 1 and L 2 are considered as comparable, if the translation of a part of L 1 respectively L 2 does exist in L 2 respectively L 1 . Comparable corpora can be collected from different Internet sources such as newspapers, Wikipedia dump files and from Social networks, but the alignment of these documents remains a challenge in natural language processing. Nowadays, Twitter has became a popular social network which allows millions of users to share their opinions on various topics. The emergence of this kind of data has led to many research works with the objective to exploit this large quantity of information to build monolingual and multilingual corpora [START_REF] Fraisse | Twitter as a comparable corpus to build multilingual affective lexicons[END_REF], [START_REF] Refaee | An arabic twitter corpus for subjectivity and sentiment analysis[END_REF]. Another research activity that exploits social networks concerns multilingual sentiment analysis and sentiment classification from tweets [START_REF] Balahur | Improving sentiment analysis in twitter using multilingual machine translated data[END_REF], [START_REF] Cui | Emotion tokens: Bridging the gap among multilingual twitter sentiment analysis[END_REF], [START_REF] Bügel | Multilingual analysis of twitter news in support of mass emergency events[END_REF].

Our objective in this paper is to collect comparable data about Syrian war and refugee problems by crawling a social network in Arabic and English. Obviously, we can not just crawl Twitter, we need to compare the retrieved corpora in order to build a real comparable corpus. For that, we have to measure the comparability between the English and the Arabic corpora. The most used methods for this issue are based on a bilingual dictionary. The drawback of this method is that the bilingual dictionaries can not cover the whole existing corpora and especially those extracted from social networks. Consequently, the dictionary should cover largely the processed corpora. Otherwise, the comparability measure will be biased by the weak rate of coverage of the bilingual dictionary. To increase the coverage of the bilingual dictionary, we will use stemming methods in order to rewrite the corpora in terms of lemmas especially for Arabic. For this language, we will be faced, in addition to the classical problems of processing Modern Standard Arabic, to the noisy text which includes misspelled words, Arabic dialects phrases, the stretched or duplicated letters, etc. This paper is organized as follows: in section 2 we summarize some previous work on comparability measures. We describe the collected multilingual corpora and the preprocessing steps applied to each corpus in Section 3. In section 4 we described a stemming method used by the community (BAMA), we propose a light stemming method and then we combine the two previous approaches. In section 5 we present Li and Gaussier comparability measure that we need for retrieving a comparable documents. Several experiments and results are described in section 6. Finally, we conclude and present some future works.

Previous works

The construction of comparable corpora is performed using similarity measures. These measures can be based on three different approaches: vocabulary overlapping, vectors space and Machine translation. Among existing work to align the comparable corpus we can cite the following: Li and Gaussier in [START_REF] Li | Improving corpus comparability for bilingual lexicon extraction from comparable corpora[END_REF] defined the degree of comparability between two corpora as the expectation of finding, for each word of the source corpus, its translation in the target one. They use this definition to propose a measure which estimates the comparability of a parallel corpus, then they showed how the comparability degree has decreased when noises have been added to the parallel corpora. Then this measure has been modified, to take into account the context in order to reduce the issue of polysemy. Li and Gaussier's measure has been improved by Guiyao et al in [START_REF] Ke | Variations on quantitative comparability measures and their evaluations on synthetic french-english comparable corpora[END_REF] by taking into account the occurrence of a word concerned by the comparability and its different translations. Saad et al [START_REF] Saad | Extracting comparable articles from wikipedia and measuring their comparabilities[END_REF] used LSA for measuring the comparability between two corpora. They proved that this approach gives better results than those based on the common vocabulary. Gamallo in [START_REF] Gamallo-Otero | Measuring comparability of multilingual corpora extracted from wikipedia[END_REF] proposed two strategies to build comparable corpora from Wikipedia, they used (binary and TFIDF) Dice to measure the degree of comparability of 30 different comparable corpora. They proved that the Dice score based on TFIDF achieves better results than those based on the binary representation.

Corpora and preprocessing

To study the reliability of the techniques proposed in this work, we use several corpora extracted from: Twitter, Euronews and a parallel corpus (ANN) [START_REF] Saad | Cross-lingual semantic similarity measure for comparable articles[END_REF]. Our objective is to retrieve comparable corpora from Twitter, this could be considered as a difficult task. In this work, we validate the proposed approach on supposed easier corpora Euronews (comparable) and ANN (parallel).

Twitter corpus

The objective is to build an English-Arabic comparable corpus. For that, we extract from Twitter by using Talend Studio and Twitter API the most frequent Hashtags for each language concerning the topics War in Syria and The Syrian Refugees. Table 1 and Table 2 show these Hashtags and the corresponding number of the retrieved tweets. We also used related Hashtags to enlarge our corpus, for example: #Syrianarmy, #freesyrianarmy. Due to the particularity of Arabic, we used different Hashtags such as: # , # , both of them correspond to the word Syria. In fact, this word could be written in two ways in MSA (Modern Standard Arabic) with symbol Ta ( ) and with symbol alif ( ). Table 3 shows the characteristics of all corpora used in this work, where |S| is the number of sentences, and |V | is the vocabulary size.

Preprocessing corpora

Natural Language preprocessing for MSA (Modern Standard Arabic) are available, but the challenge in this work is the nature of the processed data. In fact, tweets are short messages, restricted to 140 characters, these messages often contain misspelled words, abbreviations and dialectal words where the analyzer is unable to produce the morphological form of these messages. Furthermore, Arabic language is morphologically rich because in the majority of cases, a word is composed by the concatenation of a root and affixes. A root in Arabic is considered as a producer of words, that is why from a single root, several words can be composed. For example: the root to write with specific affixes produces different words with different meanings: he writes, library, office,..etc. In the following we will present the different cleaning operations related to English and Arabic.

Preprocessing English

We present below several procedures applied to the English part of Twitter corpora.

-Since Twitter is used by million of users, people take some freedom in writing. That is why we use an SMS dictionary3 which contains abbreviations, acronyms and their literal corresponding text. We use this dictionary to replace abbreviations by their literal forms. For example ppl will be replaced by people. -In order to remove foreign Twitter in the English part of the corpora, we developed a tool based on stop words and ASCII code to filter the foreign phrases. -Contrary to Arabic corpus, the English one contains many Hashtags embedded in the Tweet itself. A Hashtag is composed of several words #SyrianArabArmy, #SyrianCivilians, ...etc which should be split in order to obtain a larger Tweeter vocabulary. In the case where words are separated by capital letters or special characters it is easy to determine the words composing the Hashtag, such as in the examples: #SyrianArabicArmy #Syrian Arabic army. But, when the Hashtag is completely written in lowercase, we use a dictionary of words, sorted alphabetically and by length which allows to find the different words which match best with the content of the Hashtags.

Preprocessing Arabic

For Arabic, the preprocessing is achieved in order to reduce the ambiguity due to the fact that people write some words differently. In the following we present some rules used for that issue.

-We replace the letter by only at the end of words. This could be very surprising since these two letters are grammatically different, but graphically they are similar except that the first one has two dots above. For convenience, some people use indifferently both of them. This is why we homogenize the script in all the tweets. For almost the same reason, we replace all the forms of symbol Alif with Hamza such as in: , , with a simple Alif . -All the diacritics have been removed since people can read without these vowels.

-In social networks, sometimes users stretch words to accentuate their opinion or just write the words such as they pronounce them, we need to normalize the way of writing these words. The stretched or duplicated letters are removed such as in: → and → .

In opposite to Twitter corpora, Arabic parallel and comparable corpora used in this work do not need all these preprocessing steps, because these corpora are collected from newspapers. Consequently, they do not contain noisy data as in Twitter corpora. Nevertheless, we removed special characters, Latin characters and stops words. We also transform as above all the Alif with Hamza by a simple Alif.

Stemming

For documents such as Twitter, the vocabulary is not large, in order to use statistical methods, in general we segment the words by using lemmatization or stemming. The idea is to replace different words which share the same root by this root itself. These methods consist in reducing inflectional and sometimes derivational forms of a word to a common base form. In Arabic, this task becomes more complex compared to other languages, because, this language has some particularities such as agglutination, using diacritics, etc. In fact, Arabic words can be formed by attaching affixes to a root. Affixes in Arabic are: prefixes, antefixes, suffixes and postfixes. Prefixes and antefixes are attached at the beginning of the words, where suffixes and postfixes are attached at the end. For example the word which means to negotiate with them is composed by the elements shown in Table 4. To improve the dictionary coverage rate, in this work, we applied different techniques to retrieve the most representative form of words. For English corpora, we used TreeTagger4 and for Arabic corpora, we used the two following methods.

Buckwalter Arabic Morphological Analyzer

This analyzer is one of the most referenced in the literature, coded with Perl language by Tim Buckwalter [START_REF] Buckwalter | Buckwalter arabic morphological analyzer version 1.0. Linguistic Data Consortium[END_REF]. It is designed as a main database of 40,648 lemmas supplemented by three morphological compatibility tables used for controlling affix-stem combinations [START_REF] Attia | A lexical database for modern standard arabic interoperable with a finite state morphological transducer[END_REF]. For each word entered, BAMA provides: the different possible lemmas of the word with its diacritics, grammatical label of each lemma and their corresponding translation in English, as shown in Figure 1. Arabic Light stemming consists in removing all affixes attached to the Arabic word. However, this approach may face to several ambiguities. For instance, when a word contains a sequence of letters that seems to be an affixe but which is not. For example, the sequence in the word: two students indicates the dual-representation of the word student. However, the same sequence of letters in the word residents is not an affix but it is a part of this word, its deletion will produce a false lemma. That is why, we proposed a new method of light stemming, which removes all affixes attached to the Arabic word according to a specific order. We start by removing the external affixes of the word then those connected directly to the stem, as shown in Figure 5. Each time an affix is removed the remaining lemma is kept for the further processing steps as described in Algorithm 1 and 2. Using the affix categories shown in table 5, Algorithm 1 removes firstly, only the Antefix ( Fig. 2. Topology of an Arabic word RAntefix(W)) attached to the Arabic word, secondly only the Postfix ( RPostefix(W)) and finally, it removes both of them (RPostfixAntefix(W)). After each removal operation, the achieved lemma is kept. The same procedure is then applied to remove the prefix (RPrefix(l i )), suffix (RSuffix(l i )) and finally, it removes both of them (RPrefixSuffix(l i )) from each lemma kept in the previous step. Consequently, for each word, we get twelve lemmas, they may contain wrong and duplicated segmentation hypotheses. The filtering algorithm will remove the duplicated lemmas and those which are not present in a huge corpus5 as explained in Algorithm 2.

Algorithm 1 Generation of lemmas

Algorithm 2 Filtering(S l )

SOut ← ∅ S l ← RemoveDuplicatedLemma(S l ) for each li in S l do F ← CalculateF requency(li, CA) // CA is a large corpus if F ¿ 0 then SOut ← li end if end for Table 5. Affixes categories most used in Arabic.

Arabic affixes

T Antef ix , , , , , , , , , , , , , , , ,
T P ref ix , , , T Suf f ix , , , , , , , , , , , , , , , , ,
T P ostf ix , , , , , , , , , , , 4.

Combining BAMA and LS

Because BAMA processes a standard Arabic, consequently it fails in analyzing misspelled words which are very frequent especially in Twitter. In the following we give some examples of them:

they do not speak is actually constituted with two words followed by which should be separated by a space. This is not the case that makes BAMA failing in the analysis.

-The word should be written such as . Obviously, BAMA is unable to analyze this misspelled word.

-Other words in Twitter are written in Syrian dialect such as : bombarding. This is not supported in BAMA.

-Some forms of imperative verbs such as:

bomb are not used in BAMA [START_REF] Attia | A lexical database for modern standard arabic interoperable with a finite state morphological transducer[END_REF].

In Figure 3, we present how LS can analyze the word for which BAMA fails. The words I speak and He speaks. LS also has some limitations, for instance, it is unable to analyze correctly the agglutinated words including plural forms. It is able to segment them by identifying the pronoun and the plural form but it fails to identify the root form such as in the example: their heart, where LS provides only and . To overcome the drawbacks of the two methods, we propose to combine them. The limitations of both methods justifies the use of a hybrid method based on BAMA and LS. This justification is strengthened by the fact that BAMA is able to analyze correctly 88% of the content of our Twitter Arabic corpus while LS processes correctly 91%.

In this hybrid method, both approaches cooperate in order to produce all the potential lemmas for each word in order to increase the coverage of the dictionary.

Estimating the comparability

In this work, we used Li and Gaussier measure [START_REF] Li | Improving corpus comparability for bilingual lexicon extraction from comparable corpora[END_REF] to study the impact of the methods of stemming on the comparability measure. This measure defined the similitude between two corpora as follows: Let assume that C is an Arabic-English corpora consisting of an Arabic part C a and an English part C e . The comparability measure can be defined as the expectation of finding, for each English word W e (respectively W a ) in the vocabulary V e of C e (respectively V a of C a ), its translation in the vocabulary V a of C a (respectively V e of C e ).

The comparability measure is estimated as follows:

LG

= w∈Ve∩De σ(w, V a ) + w∈Va∩Da σ(w, V e ) | V e ∩ D e | + | V a ∩ D a | (1)
where D e (respectively D a ) is the English side (respectively Arabic side) of a bilingual dictionary. Let σ a function which indicates whether a translation of a word w represented by a list of potential translations T (w) does exist in the vocabulary V x .

σ(w, V x ) = 1 if T (w) ∩ V x = ∅ 0 else (2)

The coverage rate

We study hereinafter the influence of stemming techniques on the dictionary coverage rate, this parameter is important which influences directly the comparability of corpora as it will be shown in the following experiments. We define the coverage rate of a dictionary D compared to a corpus C represented by a vocabulary V by the quantity:

C v (V, D) = |V ∩ D| |V | (3)
Because, we work in a bilingual context (English-Arabic), we calculated a symmetric coverage rate C vsy as follows:

C vsy (V, D) = C v (V s , D s ) + C v (V t , D t ) 2 (4)
Where: v s (respectively v t ) the source and the target vocabulary and D s (respectively D t ) the source and the target part of the bilingual dictionary. For all experimentation, we calculated the dictionary coverage rate by using OMWN (Open Multilingual WordNet) which contains 17 785 pairs of Arabic and English entries.

Experimental Results

In the following we describe the experiments we conducted. In the first one, no stemming has been used to process the English part of Twitter while for the Arabic part, we used BAMA and LS in order to study the impact of these stemming techniques on the coverage rate.

In the second one, we used comparable and parallel corpora collected from newspapers to conduct similar experiments except that in this case we have more clean corpora than Twitter.

For both experiments we calculated the comparability measure between English and Arabic for both categories of corpora. Figure 4 illustrates the impact of using stemming techniques on the coverage rate of the bilingual dictionary on the Arabic Twitter corpus. Obviously, for Arabic and more especially for Twitter, this result is expectable, in fact the stemming procedure is very useful and necessary.

In Figure 5, we introduce the stemming process (by using TreeTagger) on the English part of Twitter. We show that the stemming for English is also important since the results of coverage have been improved respectively for BAMA with 2.6% and for LS with 2.9%.

Since, the coverage rate is important in the calculation of the comparability measure, we decided to estimate the coverage for corpora which are supposed to be more clean than Twitter

62

The dictionary coverage without Steminig BAMA+Treetagger LS+Treetagger Fig. 6. The dictionary coverage rate by using all the stemming techniques on all corpora. The dictionary coverage Twitter corpora Euronews corpora parallel corpora and for which the documents are strongly related. In Figure 6, we illustrate the coverage rate for three different corpora, the previous Twitter corpus, a comparable one (Euronews) and a parallel corpus (ANN). This figure shows that the combination of BAMA, LS and TreeTagger achieves the best results whatever the corpus used. The second conclusion is that the best coverage rate is obtained for the parallel corpus which is not surprising. In the opposite, we were expecting that for Twitter the results would be the worst, but it is not the case since it is extracted from Twitter by fixing the Hashtags. Consequently, both English and Arabic are related to the same topic which leads to the use of a narrow vocabulary. The worst results are achieved for the comparable corpora which is in this case the most difficult corpus for the coverage. In fact, it contains different documents related to several topics. This makes the vocabulary rich and disparate. As presented before, the coverage rate has a serious impact in the calculation of Li and Gaussier comparability measure. That is why all the previous experiments have been presented. In Table 6, we present the comparability measure on the three previous corpora. The achieved results are correlated to the ones presented in the previous experiments. In fact, the best results concern the parallel corpus and the best method is the one which combines BAMA, LS and TreeTagger. The comparability measure is not a final objective, we would like to extract for future work comparable tweets and comparable documents. That is why we conducted an experiment which looks for each tweet in Arabic its best corresponding tweet in English. In Table 7, we give respectively the maximum and the average value of comparability between a tweet in Arabic and the set of English tweets. The corresponding results are given also for a supposedly comparable corpus (Euronews) at respectively a sentence and document level. In this case, globally, the average comparability measure is better, at a document level for Euronews than for Twitter at a tweet level. In table 8, we give a sample of Arabic and their corresponding extracted English tweets ExtTweet by using LG comparability measure. We give also the reference Reference which corresponds to the translation of the original tweet in Arabic. In Figure 7, we give a chart describing the rate of pair of sentences for which the LG measure is greater than a certain threshold α for Twitter, Euronews and a Parallel corpus. This parameter could be considered such as a confidence measure that could be used in a future work to extract the best comparable and correlated tweets. We can notice that for α = 0.6, we extract only 5% of comparable tweets, tweets supposed to handle the same idea. Only 8% from the parallel corpus are supposed to be comparable. This is an aberration, but this could be explained easily, in fact

LG is based only on a bilingual dictionary while in parallel corpus a sentence is not obtained by a word by word translation of the other one. When we relax the constraints by accepting an LG greater than 0.3, we get for Twitter more than 98% of comparable tweets. In this paper, we investigate different multilingual corpora in order to make them comparable for a future work. For that, our experiments have been achieved on three Arabic-English corpora: Twitter, Euronews and ANN. The first one has been extracted by using specific Hashtags, the second one is supposed to be comparable and the third one is parallel. Processing data extracted from Twitter needs a cleaning and a harmonization of the data. That is why, we proposed several rules to make this corpus usable for the ongoing processes. To retrieve related documents from these corpora, we needed to measure their comparability. The similarity measure is the one proposed by Li and Gaussier which is based on a bilingual dictionary. Because, the coverage of the vocabulary is low, the Arabic text has been stemmed by BAMA and by a light stemming method, we proposed. Then we combined these methods in order to have a larger coverage. We applied also a stemming method to English part of Twitter by using TreeTagger. We expected that the coverage and consequently the comparability measure would be higher for Euronews than for Twitter, but it was not the case since the tweets are extracted by using specific Hashtags which makes the Arabic and English tweets close. In addition, with this simple method we retrieved tweets which could be considered as comparable. This result will be used in a future work to retrieve parallel phrases to build a machine translation system based on social network data.

Fig. 1 .

 1 Fig. 1. BAMA output of Arabic word they speak <morphology analysis total words="1" > <word total analysis="1" value=" "w id="1"> <analysis additional info=Lemma: Gloss: prefix : they (people) + stem : speak/talk/discuss + suffix : [masc.pl.] suffix=[ :IV SUFF SUBJ:MP MOOD:I] prefix="[ :IV3MP] type="" impartial=""transitive="" pos=VERB IMPERFECT root="" pattern="" stem= vowled= a id="1"/> </word> </morphology analysis >

Fig. 3 .

 3 Fig. 3. Lemmas produced by LS for incorrect word They do not speak, A: Antefix, Pr: Prefix, S: Suffix, P: Postfix.

Fig. 4 .Fig. 5 .

 45 Fig.4. The dictionary coverage rate by using BAMA and LS stemming techniques only on Arabic part of Twitter corpora.

Fig. 7 .

 7 Fig.7. The dictionary coverage rate by using all the stemming techniques on all corpora.

Table 1 .

 1 Number of English tweets collected for each Hashtag.

	English Hashtag	NT wts
	#SyrianRefugees	10895
	#refugeescrisis	2856
	#Syrianarmy #freesyrianarmy 3760
	#SyriaCrisis	6260
	#syria #syrian	34000
	Total	57771

Table 2 .

 2 Number of Arabic tweets collected for each Hashtag.

	Arabic Hashtag				Translation	textbfNT wts
	#	_				Children of Syria	1599
	#	_				Syrian revolution	10092
	#	_				Syrian refugees	4000
	#	, #				Syria	34000
	#	_	_	, # _	_	Syrian arab army, Free Syrian army	5234
	Total						59452

Table 3 .

 3 Comparable and parallel corpora characteristics.

	Twitter	Euronews	Parallel
	English Arabic English Arabic English Arabic
	|S| 12624 14412 1400 1400	300	300
	|V | 108K 372K 145K 378K 119K 377K

Table 4 .

 4 Example of Arabic Affixes

	Word	Antefixe Prefixe Stem Suffixe Postfixe

  Internal affix by using T P ref ix and T Suf f ix affixes tables: 2: for each li in S l do // i = 1 . . . 3

	1: S l ← ∅
	//Removing External affixes by using T Antef ix and T P ostf ix affixes tables:
	S l ← RAntefix(W );
	S l ← RPostfix(W );
	S l ← RPostfixAntefix(W );
	//Removing S l ← RPrefix(li);
	S l ← RSuffix(li);
	S l ← RPrefixSuffix(li);
	3: end for
	4: Filtering (S l )

Table 6 .

 6 The comparability measure of Li and Gaussier

	Corpus BAMA LS BAMA+ LS
	Twitter	58.8 58.4	61
	Euronews 49.6 49.9	51.6
	Parallel	63.8 63.6	65

Table 7 .

 7 Comparability values between Arabic and English documents

	Corpus	Max Average
	Twitter	66	32.6
	Euronews	60	27.3
	Euronews document 65.8	35.8

Table 8 .

 8 A sample of Arabic and the extracted corresponding English tweets Tweet ExtTweet Syrian army has retaken completely under its control the thermal power plant east aleppo via Reference General Command of the Army announces the control of the thermal station in the countryside of Aleppo Tweet ExtTweet The american russian and iranian strategic triangle in syria Reference US Russian Truce Syria Tweet ExtTweet The american russian and iranian strategic triangle in syria Reference Urgent ceasefire in Syria will not succeed if Damascus and Moscow do not change their behavior in Syrian crisis

http://www.illumasolutions.com/omg-plz-lol-idk-idc-btw-brb-jk.htm

http://www.cis.uni-muenchen.de/ schmid/tools/TreeTagger/

Corpora: Mourad Abbas (14M) and Saad Motaz(15M)http://aracorpus.e3rab.com


Karima Abidi
email: k_abidi@esi.dz

Kamel Smaili
email: kamel.smaili@loria.fr

Kamel

How to match bilingual tweets ?

Keywords: Comparability measure, Arabic stemming, Proper names, Soundex, Twitter

In this paper, we propose a method that aligns comparable bilingual tweets which, not only takes into account the specificity of a Tweet, but treats also proper names, dates and numbers in two different languages. This permits to retrieve more relevant target tweets. The process of matching proper names between Arabic and English is a difficult task, because these two languages use different scripts. For that, we used an approach which projects the sounds of an English proper name into Arabic and aligns it with the most appropriate proper name. We evaluated the method with a classical measure and compared it to the one we developed. The experiments have been achieved on two parallel corpora and shows that our measure outperforms the baseline by 5.6% at R@1 recall.

INTRODUCTION

The parallel corpora are extremely valuable resources for many applications in natural language processing, in particular for machine translation which needs massive corpus to train statistical models. However, this type of data are not always available and especially for certain pairs of languages. An attractive option is to collect data from the web and the social networks for which, nowadays data are abundant. However, this task is not easy to handle because the collected documents have to be aligned in accordance to their topic. When the corpora are aligned, they are considered as comparable. These corpora consist of a set of documents expressed in several languages which are not parallel in the strict sense, but deal with analogous subjects. These last decades this issue has grown considerably [START_REF] Stefan | Improving Machine Translation Performance by Exploiting Non-Parallel Corpora[END_REF] [6] [START_REF] Skadina | A Collection of Comparable Corpora for Underresourced Languages[END_REF] [START_REF] Zhu | Building Comparable Corpora Based on Bilingual LDA Model[END_REF]. The community of Cross-Lingual Information Retrieval contributed significantly to propose different solutions to this issue [START_REF] Saad | Cross-lingual semantic similarity measure for comparable articles[END_REF], [START_REF] Kutuzov | Clustering Comparable Corpora of Russian and Ukrainian Academic Texts:Word Embeddings and Semantic Fingerprints[END_REF] [START_REF] Vulic | Monolingual and Cross-Lingual Information Retrieval Models Based on (Bilingual) Word Embeddings[END_REF].

These last couple of years, a particular attention has been given to harvest data from social networks and particularly from Twitter. This is due to the fact that, so many people through the world adopted this social network to express their opinions. Consequently, it would be useful to investigate this media, in order to collect cross-lingual posts and align them in terms of topics. This will lead to get comparable corpora of Tweets. These documents could be then, used to extract parallel fragments or phrases. In order to have relevant parallel fragments, we need relevant comparable Tweets, to achieve that, we should propose an efficient measure to estimate the comparability. In this work, we will show that the classical dictionary-based measure [START_REF] Li | Improving Corpus Comparability for Bilingual Lexicon Extraction from Comparable Corpora[END_REF] cannot be used directly for this task and especially for Arab Tweets. Specific knowledge related to Arabic will be taken into account in order to tackle, not only, the issue of the specificity of Arabic, but also this free way of writing the posts. This paper is organized as follows: In section 2, we present related works concerning the extraction of comparable corpora. Then, we describe the corpus, we collect, and we give details about the preprocessing steps in sections 3 and 4. In section 5, we present the process we use for matching bilingual Tweets. Several experiments and results are described in section 6. Finally, we conclude and present some future works.

RELATED WORKS

The construction of comparable corpora is performed using similarity measures. These measures can be based on three different approaches: vocabulary overlapping, vector space and Machine translation. Among existing work to align the comparable corpus, we can mention the following: Li and Gaussier in [START_REF] Li | Improving Corpus Comparability for Bilingual Lexicon Extraction from Comparable Corpora[END_REF] defined the degree of comparability between two corpora as the expectation of finding, for each word of the source corpus, its translation in the target one. They use this definition to propose a measure which estimates the comparability of two parallel corpora to which noises have been added. They showed that the comparability degree decreased proportionally with the added noises. A similar approach proposed by Etchegoyhen et al. in [START_REF] Thierry Etchegoyhen | Set-Theoretic Alignment for Comparable Corpora[END_REF] termed STACC, is based on expanded lexical sets and Jaccard similarity coefficient. The idea is to get rid of a manual bilingual dictionary. The bilingual dictionary is built on a large parallel corpus by using Giza ++ [START_REF] Franz | A Systematic Comparison of Various Statistical Alignment Models[END_REF]. Since, it is independent from languages, the approach has been evaluated on a large dataset of ten languages. Zhu et al. in [START_REF] Zhu | Building Comparable Corpora Based on Bilingual LDA Model[END_REF] utilized a bilingual LDA model to match similar documents. They proved that this approach can obtain similar documents with consistent topics. Huang et al. in [START_REF] Huang | Mining Large-scale Comparable Corpora from Chinese-English News Collections[END_REF] describe a method based on techniques inspired from Cross Lingual Information Retrieval. With the translation of the keywords of the source documents, they retrieve the target documents which contain these translated words. Then, the mapping between source and target documents is achieved in accordance to a similarity value. A method based on word embedding has been proposed by Vulic et al in [START_REF] Vulic | Monolingual and Cross-Lingual Information Retrieval Models Based on (Bilingual) Word Embeddings[END_REF]. The model has the possibility to learn bilingual word embeddings from already comparable corpora. The crucial idea in this work is the fact that the method allows to share the cross-lingual embedding space.

Works on comparable corpus containing Arabic are not as popular as those used for English or French, we can mention those proposed in [START_REF] Stefan | Improving Machine Translation Performance by Exploiting Non-Parallel Corpora[END_REF], [START_REF] Abdul-Rauf | On the Use of Comparable Corpora to Improve {SMT} performance[END_REF], [START_REF] Saad | Cross-lingual semantic similarity measure for comparable articles[END_REF]. In this last work, different comparability measures based on bilingual dictionaries or on numerical methods such as Latent Semantic Indexing (LSI) have been proposed.

EXPERIMENTAL MATERIAL

As presented before, we propose to identify comparable corpora by extracting them from Twitter. In the following, we will be interested by two languages: Arabic and English. In order to identify comparable Tweets, we decided to set the topic which will be used to crawl the Tweets: Syria's war. Our objective is to crawl all the Tweets related to this subject and then to align Arabic and English at the Tweet level. For this purpose, we selected the 7th-top English Hashtags concerning the war in Syria (Table 1). The same process has been done on Arabic (Table 2).

Due to the particularity of the free way to write Arabic in Twitter, we used different Hashtags such as: # سوريا # سوريه , both of them correspond to the word Syria. One ending with Ta )ة( and the other with alif .)ا( 1 and Table 2 show that the global number of crawled Tweets is approximatively equivalent. But the number of Tweets concerning the Syrian Refugees is not the same. It is twice much more in English than in Arabic. This could be explained by the fact that this topic has been very popular in the West, since the corresponding countries were directly concerned by the problem. While, the number of Tweets concerning Syria is much more important in Arabic than in English, since the Arab world is very involved in the Syrian issue.

PREPROCESSING TWEETS

In natural language and especially for processing Tweets, one needs to rewrite some words, to clean some of them, to homogeneous the way of writing, to transform digits, proper names, cities and so on. This step is referred as language preprocessing. In the following, we preprocess both Arabic and English by taking into account the linguistic specificity of each of them. This step is very crucial since our objective is to identify comparable Tweets. More the treatments of homogenization of Tweets in both languages are precise, and more the process of identifying comparable Tweets is relevant. Figure 1 illustrates an example of the differences between an English and its equivalent Tweet in Arabic. The fragments on red and green correspond to respectively the way to write the date and the number in Arabic.

English tweet Syria issues decree no 63 the general parliamentary elections will be on

Wednesday april th 13 2016 Arabic tweet

موعد ٢٠١٦ نيسان ١٣ االربعاء يوم بتحديد القاضي ٦٣ رقم المرسوم االسد بشار اصدر االعضاء النتخاب

Preprocessing English Tweets

In the following, we present the main treatments we achieve on the English Tweet corpus. Since Twitter is used by hundred million of users and because a Tweet is limited to 140 characters, people take some freedom in writing their posts, for instance by shortening the words. To handle this issue, we use a SMS dictionary 1 which contains abbreviations, acronyms and their literal corresponding text. We used this dictionary to replace abbreviations by their literal forms. For example, ppl will be replaced by people.

Sometimes, in an English Tweet, we can find some references to foreign languages. This could be a serious problem for the further linguistic treatments. Based on a list of stop words of few languages, we discard all the fragments which contain at least one of these stops words.

Contrary to Arabic Tweets corpus, the English one contains many Hashtags embedded in the Tweet itself. Sometimes they are in the middle of a post, consequently we cannot just remove them, since they are used as any word. In some Tweets, a Hashtag might be composed of several Hashtags #SyrianArabArmy, #SyrianCivilians, ...etc which should be split. In the case where words are separated by capital letters or special characters, it is easy to determine the border of words composing the compound Hashtag. But, when the Hashtag is completely written in lowercase, we need to perform differently. To do so, we decided to use a dictionary sorted alphabetically and by the word's length. We seek a word in the compound Hashtag by looking for it in this dictionary.

Because there are several ways to write a date in English, all of them will be homogenized such as: DD/MM/Year. In Table 3, we give some examples before and after the rewriting process.

In social network, a letter of some words could be duplicated several times to express an emotion or a sentiment, phenomenon known as an elongation such as in: woahhh. These kind of words are transformed by removing the duplicated letters: woah

Preprocessing Arabic Tweets

Arabic is very different from Indo-European languages, that is why specific treatments have to be achieved, in order to make Tweets ready for the further processings.

For reasons of freedom writing in Twitter, users replace the letter ة by ه only at the end of words. This could be very surprising since these two letters have different linguistic roles in Arabic, but graphically they are similar, except that the first one has two dots above. For convenience, some people use indifferent one or the other. This is why we homogenized the script in all the tweets. For almost the same reasons, we replaced all the forms of symbol Alif with Hamza such as in: ,آ ,أ إ with a simple Alif ا . Concerning the diacritics, we removed them since people can read without short vowels.

In Arabic, two sets of digits are used for writing numbers, the first set is the one used around the world, known by Arabic digits and the second is the Indo-Arab digits which are much more used in Middle-East: ٠١٢..٩. For this purpose, we decided to keep only one numeral notation for 1 www.illumasolutions.com/omg-plz-lol-idk-idc-btw-brb-jk.htm numbers by using the English coma for decimal number, for example ١٣ , ٥ will be rewritten as 5.13 .

Concerning the dates, in the Arab world, three types of calendars could be used: Assyrian, Hijri and Gregorian. The first and the second one are much more used in the East than in the West of the Arab world. For example: January could be written:

ا كانون لثاني

, جانفي or يناير depending on the Arab region. That is why each date, whatever its form, is rewritten in accordance to the following pattern DD/MM/Year (see examples in Table 4).

In social networks, sometimes users stretch words to accentuate their opinion or just write the words such as they pronounce them, then it is necessary to normalize the way of writing these words.

Stemming

Arabic language is morphologically rich due to the fundamental rules used for building the words. In fact, often a root is considered as a producer of words, since it is agglutinated to affixes and suffixes to form new words. For example: the root كتب ( to write), with specific affixes produces different words with different meanings: يكتب (he writes), مكتبة ( library), مكتب (office), etc.

To use statistical methods, the words have to be segmented in order to reduce the number of entries in the vocabulary and then to have relevant statistics. That is why, a stemming procedure is run in order to segment the Tweets. The idea is to replace different words which share the same root by the root itself. This will reduce the size of the list of distinct words and leads to a better coverage of the corpus.

In this work, we applied different techniques to retrieve the most representative form of Arabic words. To do so, we combined Buckwalter Arabic Morphological Analyzer with a method based on Light Stemming (LS) presented in previous work [START_REF] Abidi | Measuring the comparability of multilingual corpora extracted from Twitter and others[END_REF].

For English, we also used a morphological analyzer to reduce the flexional forms of English words, for that we used the TreeTagger tool 2 .

Proper names in Arabic

Generally, detection of proper names is a critical task for natural language processing applications especially for Arabic. The problem becomes harder when the processing concerns the Tweets. For Latin languages, proper names start with a capital letter, unfortunately, for 2 http://www.cis.uni-muenchen.de/~schmid/tools/TreeTagger/ Arabic, this notion does not exist. In addition, personal names refer, in general to common words. For example, the first name كريمة means generous.

Another issue is that the proper names could be agglutinated to prefixes and suffixes which requires lemmatization step before performing identification of proper names. For example:

بسوريا ( in syria) must be lemmatized سوريا بـ (Syria).

The majority of research work concerning the extraction proper names have been dedicated to Modern Standard Arabic (MSA) by Pos-tagging, while only little attention has been given to unstructured text like tweets [START_REF] Omnia | Hybrid Approach for Extracting Arabic Persons Names and Resolving their Ambiguity from Twitter[END_REF].

Our goal is how to match the English and Arabic proper names, from two bilingual Tweets. Name matching can be defined such as the process of determining, whether two name strings are instances of the same name [START_REF] Peter | A Comparison of Personal Name Matching: Techniques and Practical Issues[END_REF]. This task is not difficult, if the two languages use the same alphabet. Otherwise, a transliteration of a source proper name has to be performed. Transliteration is the action of representing the signs of an alphabet of the source language by the signs of the target language. Transliterating Arabic is more difficult, because for each proper name, several acceptable transliteration candidates could be proposed depending on how it is pronounced in the target language. For example, for the first name: ,سليمان the following transliterations are possible: Sulayman, Seleiman, Sliman and Selayman.

IDENTIFICATION OF COMPARABLE TWEETS

In general building comparable corpora consists in collecting multilingual documents concerning or not a specific topic, then documents are aligned by estimating the degree of their closeness. When we would like to build a comparable corpus of Tweets, the task is a bit complicated because the shortness of the post which makes the matching process more difficult.

In fact, the matching process is based on the number of common words between two bilingual documents, unfortunately the number of words, in a Tweet, is very weak which makes this task harder. In the following, we propose a method dedicated to the extraction of comparable Tweets. From two Twitter corpus S and T, in two different languages and for a post s i d published at date d, we look for the Tweet t j d ́ published at date d ́ respecting the constraint d-1 ≤d ́≤d+1.

We hope that, with this constraint, we retrieve Tweets which concern the same topic. In order to align Tweets, other processing steps are necessary, they are described in the following.

Number and dates identification

As presented in section 4.2 and 4.1, the processing of dates and numbers is a crucial step allowing to identify similar dates and numbers in Arabic and English Tweets. An homogenization of these items is done in accordance to Tables 3 and4.

Proper names identification

To identify Arabic proper names several treatments have been applied. In Arabic, proper names could be simple such as علي ( Ali) or compounded such as: الرحمان عبد ابن ( ibn Abdul Rahman) or الدين عالء ( Alaa Aldine). These compounded proper names are generally composed with a single proper name preceded or followed by particles given in Table 5. We decided to merge them to facilitate their transliteration. For instance, الرحمان عبد ابن ( ibn Abdul Rahman) is rewritten into ابن_عبد_الرحمان ibn_Abdul_Rahman.

To facilitate the process of matching the proper names, for each Arabic particle, several transliterations are proposed (see Table 5).

Table 5. Particles used in the compound proper names.

Particles Arabic (English Transliteration) Prefix

( ,ابن )بن (ibn, bin, ben), عبد ( 3bd, abd), (ابوabu, abo, abou), بنت (bint, bent), ام (oum) Suffix الدين (eldin, aldin, uldin,eldin)

For the compounded proper names, it is easy to identify them thanks to the previous particles. While, for the single proper names the task is more difficult. That is why we encode them by taking advantage from their phonetic form. The encoding is done in both English and Arabic Tweet. In the English Tweet, all the words which are not in the bilingual dictionary, are encoded. The hypothesis is that we might consider them as proper names. Then all the words of the Arabic Tweet are encoded. If two strings from respectively Arabic and English Tweet have the same code, we can conclude that, one is the transliteration of the other. For that, we used Soundex [START_REF] Syed | On the development of name search techniques for Arabic[END_REF] which proposes to replace each letter by the index of a group of characters. Each group is constituted by the letters corresponding to almost the same sound class (see Table 6).

The characters of Group 0, are ignored unless they appear in the first position of the supposed proper name. Encoding consists in keeping the first character without any change and the following are encoded in accordance to Table 6. Any supposed proper name will be represented by a letter followed by three digits. For example, encoding the proper name ,جميلة will give three codes (Figure 2) corresponding to the possible transliterations: Djamila, Jamila or Gamila. The weakness of Soundex is that, it encodes only the first four consonants. This constitutes a serious problem for the compound proper names. For example, Abdel Aziz will have the same code (A134) as Abdel Rahman. To overcome this constraint, we decided to encode each item of a compounded proper name. That is why, Abdel Aziz will be encoded by: A134A220 and Abdel Rahman will be encoded by A134R550.

Comparing codes is not enough, in fact the encoding process does not produce a unique code for each proper name. So when an English word is encoded, it is then transformed into an Arabic word thanks to a transliteration table. Then the transliterated word is compared to those in the Arabic Tweet which have the same code as the English encoded word.

The comparability measure

In order to find similar Tweets, we used an adapted version of Li and Gaussier measure which is based on a bilingual dictionary [START_REF] Li | Improving Corpus Comparability for Bilingual Lexicon Extraction from Comparable Corpora[END_REF]. The similitude between two Tweets is defined as follows:

Let assume that T is an Arabic-English Tweet corpus consisting of an Arabic part T a and an English par𝑡 𝑇 𝑒 . The comparability measure can be defined as the maximum score between an Arabic Tweet 𝑇 𝑎 and all the Tweets 𝑇 𝑖 for 1≤ i ≤ 𝑁 𝑇𝑒 Where 𝑁 𝑇𝑒 is the size of 𝑇 𝑒 .

For each Arabic Tweet, Score is calculated as follows:

𝑆𝑐𝑜𝑟𝑒(𝑡 𝑎 , 𝑡 𝑒 ) =

The adapted comparability measure of Li and Gaussier referred as LGT is calculated as follows:

𝐿𝐺𝑇(𝑡 𝑎 ) = max 1≤𝑖≤𝑁 𝑇𝑒 𝑆𝑐𝑜𝑟𝑒(𝑡 𝑎 , 𝑡 𝑒 𝑖 )

The size and quality of dictionary may heavily affect the result of comparability measure. In this work, we used the Open Multilingual WordNet (OMW) which contains 17 785 pairs of Arabic and English word. In the previous sections, we proposed several procedures in order to take into account the specificities of Arabic and particularities of the Tweets. In other words, when we identify a number, a date or a proper name, this has to be taken into account in the comparability measure. That is why, we modified the score mentioned in (1) as follows: 𝜎 returns 1 if w has a translation in the target Tweet or if it has been identified such as a number, a date, a proper name, etc. (see section 5). And the new comparability measure is calculates as follows:

𝑀𝐿𝐺𝑇(𝑡 𝑎 ) = max 1≤𝑖≤𝑁 𝑇𝑒 𝑀𝑆𝑐𝑜𝑟𝑒(𝑡 𝑎 , 𝑡 𝑒 𝑖 )

(5)

Figure 1 .

 1 Figure 1. Example of comparable Tweets.

Figure 1 .

 1 Figure 1. Encoding the proper name جميلة .

∑

  𝜎(𝑤,𝑇 𝑎 )+∑ 𝜎(𝑤,𝑇 𝑒 ) 𝑤∈𝑇 𝑎 ∩ 𝐷 𝑎 𝑤∈𝑇 𝑒 ∩ 𝐷 𝑒 |𝑇 𝑒 ∩𝐷 𝑒 |+|𝑇 𝑎 ∩𝐷 𝑎 |(1)where 𝐷 𝑒 (respectively 𝐷 𝑎 ) is the English side (respectively Arabic side) of a bilingual dictionary. 𝜎 is a function which indicates if one of the potential translations T(w) of the word w does exist in the vocabulary 𝑉 𝑥 .𝜎(𝑤, 𝑉 𝑥 ) = {1 𝑖𝑓 𝑇(𝑤) ∩ 𝑉 𝑥 ≠ ∅ 0 𝑒𝑙𝑠𝑒

Table 1 .

 1 Number of English tweets collected for each Hashtag.

	English Hashtag N Twts
	#SyrianRefugees	10895
	#refugeescrisis	2856
	#Syrianarmy	3211
	#freesyrianarmy

Table 2 .

 2 Number of Arabic tweets collected for each Hashtag.

			English Hashtag	N Twts
	# سورية -	اطفال	Children of Syria	1599
	# السورية -	الثورة	Syrian revolution	10092
	# السوريين -	الالجئيين	Syrian refugees	4000
	سوريا#				Syria	17000
	سورية#				Syria	17000
	# السوري -	-العربي	الجيش	Syrian Arab army	916
	# الحر -	-السوري	الجيش	Free Syrian army	4318
	Total					59452

Table

Table 3 .

 3 Examples of rewritten dates.

	Before	After
	April 13,2016	13/4/2016
	february 1,2016	1/2/2016
	22 feb 2016	22/2/2016
	2.2.2016	2/2/2016

Table 4 .

 4 The stretched or duplicated letters are removed such as in the following Arabic examples: عاااااجل → عاجل and ياااااارب → يارب . Examples of date before and after the rewriting treatment.

				After
	2016	شباط من االول	1/2/2016
	2016	فبراير	22	22/2/2016
	2.2.2016		2/2/2016
	13,5			13.5

Table 6 .

 6 Encoding Table of Soundex.

EXPERIMENTAL RESULTS

The idea of identifying comparable corpora is an intermediate milestone, the final goal is to look for the best matched Tweets, in order to retrieve parallel phrases which could be used in machine translation. First of all, we need to measure the comparability of the collected bilingual corpus of Tweets by using the measures presented in Section 5.3. To evaluate the reliability of this measure we run an experiment on two parallel corpora: The first extracted from Twitter [START_REF] Ling | Microblogs as Parallel Corpora[END_REF] which is available at 3 referred in the following as 𝐶 Ling . This corpus contains just 2006 parallel tweets. To our knowledge, it is the only available parallel corpus Arabic-English. Since this corpus is small, we decided to test on a parallel newspaper corpus which contains 11942 sentences extracted from ANN 4 , referred in the following as 𝐶 ANN .

Concerning the Twitter corpus of Ling et al., unfortunately when we investigated its content, we discovered that the data are not really parallel. Consequently, we cannot used it as a reference corpus for our tests. To illustrate the problems we encountered, we give in Table 7, few examples of what has been considered by the authors as parallel Tweets.

Table 7. Example of parallel tweets extracted by [START_REF] Ling | Microblogs as Parallel Corpora[END_REF] . In this corpus some tweets are considered as parallel, though they contain only characters such as in the 2 th and 3 th examples. This is due to the absence of preprocessing before alignment.

To identify the language of tweets, the authors used a binary function which yields 1 if a word w contains characters of a specific language L, and 0 otherwise. This function is useful if we would like to differentiate Mandarin from English, but not English from French. From a subset of 1000 Tweets, 0.6% of tweet are different from the desired language such as in the 4 th and 5 th examples.

We found in this parallel corpus, a Tweet in a language which is aligned with itself in the same language which is unacceptable for our purpose (see the 6 th).

3 http://www.cs.cmu.edu/~lingwang/microtopia/ 4 www.annahar.com Due to all these problems, we decided to select 1000 multilingual tweets considered by the authors as parallel and we extracted the real parallel Tweets. Only 34% are strictly parallel. The following tests have been achieved on this subset of parallel Tweets calledC Ling34 .

We run several experiments with the two comparability measures described in Section 5.3 We calculated the classical Recall (R@1, R@5 and R@10). Results are presented in Table 8.

Table 8.

LGT and MLGT results for parallel corpora. This table shows that the modified LGT achieves better results than LGT since it takes into account the treatment of proper names, dates and numbers. For Twitter corpus, the recall is 56% at R@1 and grows up to 83% at R@10. This result is interesting, it allows to retrieve in the top-10 the right target Tweet.

Corpora

Concerning the newspaper corpus which is larger, the results are more crucial since at Top-10, we get a recall of 92%. In Table 9, we give some examples of matched tweets.

CONCLUSION

In order to obtain a parallel Twitter corpus for which further NLP process could be considered, we developed a method which allows to align the Tweets of a same topic. The experiments achieved showed that for a Tweet, the proposed method can retrieve the corresponding target Tweet with a recall of 83% at R@10. This result has been achieved by a series of preprocessing which permits to align more easily two bilingual Tweets (Arabic and English). Preprocessing is a crucial step, when the data are extracted from social networks and more particularly from those which are written in Arabic. Specific treatments of dates, numbers and transliteration of proper names have been proposed to overcome the issues relates to this specificity. This preprocessing allowed to improve the results by 5.6% in comparison to the baseline model. This result is very encouraging and will permit in a future work to consider the extraction of parallel phrases.

Author

Photo


Stefano Ortolani
email: ortolani@few.vu.nl

Mauro Conti
email: mconti@few.vu.nl

Bruno Crispo
email: crispo@disi.unitn.it

Roberto Di

Event Handoff Unobservability in WSN

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Due to the open nature of communications in Wireless Sensor Networks (WSNs), it is fairly easy for an adversary to trace all the communications within the network. If techniques such as encryption may be employed to protect data privacy (i.e. the content of a message), countermeasures to deceive context privacy (e.g. the source of a message) are much less straightforward. The research community has recently started addressing this issue in the unique context of WSNs [START_REF] Shao | Towards statistically strong source anonymity for sensor networks[END_REF]. The resource constrained environment, together with the enhanced adversary capabilities-e.g. the adversary can be mobile and eavesdrop all the communications-, have no correspondence in the wired setting, hence calling for novel solutions to address context privacy issues in WSNs [START_REF] Li | Privacy preservation in wireless sensor networks: A state-of-the-art survey[END_REF].

In many applications (e.g., sensing and reporting the location of a convoy) the source of a message itself reveals the events a WSN is sensing. In order to protect these events, and thus assuring context privacy, we need to conceal that an event took place.

In this paper we identify the following open issues for the current research in this area:

-Open Issue 1. If bogus traffic is used to hide the real one, the adversary success (in capturing a node that routed a real event) might not be just linear with the amount of real event.

• Open Issue 2. Solving the Open Issue 1 might imply losing the unobservability property. -Open Issue 3. An enhanced privacy property, k-anonymity, could be defined to describe the fact that an event cannot be distinguished between k-1 other events, but also requiring the other k-1 event to be not real events. -Open Issue 4. Hiding the trajectory of an event should take into consideration the anatomy of the trajectory itself. -Open Issue 5. The need for a common metric for privacy and energy consumption.

Organization. In Section 2 we revise the state of the art in the context of privacy preservation in WSN. In Section 3 we introduce the system model and the adversary model considered in this paper. In sections 4, 4.

Related Work

Providing privacy to WSNs would allow a wider application of this technology. WSNs privacy has been first addressed from the point of view of communication confidentiality. Recently, also the context privacy has been investigated-a survey can be found in [START_REF] Li | Privacy preservation in wireless sensor networks: A state-of-the-art survey[END_REF]. WSNs privacy also depends on the specific use of the network. E.g. [START_REF] He | Pda: Privacypreserving data aggregation in wireless sensor networks[END_REF][START_REF] Conti | Privacypreserving robust data aggregation in wireless sensor networks[END_REF] addressed the problem of privacy preserving data aggregation [START_REF] Xi | Preserving source location privacy in monitoringbased wireless sensor networks[END_REF].

The problem of guaranteeing the privacy of a node sending data to the BS (not throughout the aggregation process) has been initially addressed leveraging how the messages are routed. In [START_REF] Kamat | Enhancing source-location privacy in sensor network routing[END_REF][START_REF] Ozturk | Source-location privacy in energy-constrained sensor network routing[END_REF], the authors aim at hiding the source of a message, forwarding messages to the BS using random walks and dummy traffic. In [START_REF] Conner | Using data aggregation to prevent traffic analysis in wireless sensor networks[END_REF][START_REF] Jian | Protecting receiver-location privacy in wireless sensor networks[END_REF] the BS location is protected by letting the nodes send messages to a random node, instead of the BS. This random node will then aggregate the traffic and communicate to the BS. This work consider a local adversary. In [START_REF] Mehta | Location privacy in sensor networks against a global eavesdropper[END_REF], the authors propose a partial k-anonymity solution for event source. While they also consider mobile events, the solution is quite energy demanding-property not desirable in WSNs.

In [START_REF] Yang | Towards event source unobservability with minimum network traffic in sensor networks[END_REF] the energy aspect has been taken more into consideration. The authors used carefully chosen dummy traffic to conceal the event source location and formalized the concept of unobservability for wireless communication. Nodes acting as aggregator proxies are used to reduce the communication overhead. Another solution involving dummy traffic but not proxies has been proposed in [START_REF] Ouyang | Source location privacy against laptop-class attacks in sensor networks[END_REF]. In [START_REF] Shao | Towards statistically strong source anonymity for sensor networks[END_REF] the authors demonstrate that to achieve perfect global privacy performance benefit must be sacrificed. They also introduce the notion of strong source anonymity. We observe that the solutions in [START_REF] Shao | Towards statistically strong source anonymity for sensor networks[END_REF][START_REF] Yang | Towards event source unobservability with minimum network traffic in sensor networks[END_REF] introduce a delay in the message reaching the BS. The solution proposed in [START_REF] Yang | An active global attack model for sensor source location privacy: Analysis and countermeasures[END_REF] switches on demand from a statistically-strong source anonymity scheme (i.e. [START_REF] Shao | Towards statistically strong source anonymity for sensor networks[END_REF]) to a k-anonymity scheme (i.e. [START_REF] Mehta | Location privacy in sensor networks against a global eavesdropper[END_REF]). How to solve the handoff problem in a secure and distributed manner is left as future work.

Finally, randomizing the node ID has also been proposed [START_REF] Ouyang | Providing anonymity in wireless sensor networks[END_REF]. However, the adversary model considered does not leverage techniques such as traffic and rate analysis.

System and Adversary Model

While previous solutions consider mainly static events, in this work we deal with mobile events. A mobile event involves a set of sensing nodes, in a way that is dependent upon time and location: the set of nodes sensing a mobile events define a handoff trajectory. Hiding the handoff trajectory of mobile events is not yet well investigated [START_REF] Yang | An active global attack model for sensor source location privacy: Analysis and countermeasures[END_REF]. In particular, we deal with a specific type of mobile events: the ones originating on the WSN perimeter (i.e. its border) and eventually ending inside the WSN area.

The adversary is assumed to be global, passive, and external. Furthermore, we take into account the possibility that, once the traffic is analyzed, the adversary is willing to verify the gathered information. This means that the adversary physically checks the locations of both real and dummy events. Constrained by a given time interval T a , the adversary inspects a subset of the nodes believed accountable for the traffic he previously gathered-the adversary's revenue is proportional to how many checked locations previously corresponded to a real event.

Open Issue 1: A non-linear adversary gain

We want to guarantee the privacy of a real event being sensed by the WSN, considering the models described in Section 3. In particular, we aim to conceal which nodes sensed a real event. In order to this, we constrain other nodes to act as they sensed a real event too, thus sensing a dummy event. The property we want to guarantee can be summarized by the following definition. Definition 1. (Real event (T ,k)-unobservability). We define a real event unobservability over the variables T and k. In particular, consider the observation O for a time interval T . The probability of a real event e entering the network with a rate following a Poisson distribution of parameter l, 0 ≤ l ≤ k, is equal to the probability of e given O. If this holds for each possible choice of l, then e is called (T ,k)-unobservable. Formally: if ∀O, P (e) = P (e|O) then e is (T ,k)-unobservable.

In other words, just observing the network does not give any information on the Poisson parameter l, 0 ≤ l ≤ k at which real events actually enter into the network.

Furthermore, we have the following aim. Let us assume that the adversary becomes active in tampering nodes-to check if these nodes sensed real events. We want to keep constant the adversary's success probability. In particular, we want to reach this target even if the rate of real events l varies.

A possible approach In the literature real events are modeled as Poisson processes of a given ratio l [START_REF] Diaz | Towards measuring anonymity[END_REF]. Given this, a possible solution could leverage a self-adaptive scheme that, given real events taking place with rate l, carefully produces dummy events with rate k-l. The parameter k is the rate of the overall events (i.e. real and dummy ones) we assume the WSN can deal with. Hence, we select k such that the rate of real events l is ≤ k.

If the overall rate k is fixed, the adversary is not able anymore to distinguish whenever a message corresponded to a real event. However, since the scheme would need to adapt to the ratio of real events, an additional parameter T is needed: this parameter defines the time interval in which every node "learns" the actual amount of real events. According to that, each node tunes the rate of dummy events. We call the so defined privacy property (T, k)-unobservability.

In this setting, with the growth of l, the success ratio of the adversary, that checks the event source location, grows as well since there are less dummy events. Given φ = k -l dummy events and l real events, a naïve solution would be to increase φ accordingly. In other words, we may want to keep a fixed ratio between φ and l. However, such a solution presents two different concerns: (1) the amount of events a WSN can generate is limited; (2) given a fixed displacement of the network, the more events there are, the more likely is that the adversary may discover a real event.

A node that sensed a dummy event.

The attacker.

A node that sensed a real event.

The path induced by a real event.

A node that did not sense anything.

The path induced by a dummy event.

(a) Legend.

(b) Low events density de. (c) High events density de. The former concern represents also the upper bound of real events the WSN is able to cope with. Since concealing real events requires us to generate additional dummy events, it is our interest to keep this quantity to a minimum. The latter concern is, in turn, depicted in Figure 1 (the legend is reported in Figure 1a). Figure 1b shows a WSN where two dummy events (dark arrows) and one real event (light arrow) takes place, i.e. φ = 2 and l = 1 (light arrow). The adversary, identified by the star, is able to inspect some of the nodes generating dummy traffic within the light circle. We remind that the adversary is constrained by a time interval T a , therefore he may miss to find the depicted real event.

Let us analyze the following case now: we want to increase the dummy events (φ = 4) in order to deal with a growth of real events (l = 2). Figure 1c shows this scenario: the area available to the adversary includes two different real events now. The probability that the adversary chooses the real event location intuitively increases: previously only one node out of eight would have been a successful choice (the node sending a real event). Merely increasing the amount of dummy events in a proportional manner is not the desired solution.

To address these concerns, we have to take into account the density d e of the nodes relaying these events. Less events trivially correspond to a lower d e . If we increase the events, the attacker has more nodes to check (i.e. higher d e ).

Open Issue 2: Proportional adversary gain means losing unobservability

The solution reported in the previous section strongly relied on the concept of k-anonymity; since the amount of events was kept constant (k), l real events were concealed among k -l dummy events. As long as k was not changing, real events hitting the network were made unobservable. However, the more the real events were increasing, the higher was the probability of success of our adversary. To cope with that behavior we proposed to increase the rate of dummy events in a more than proportional manner. Unfortunately this countermeasure also enjoys a side-effect: a passive and global adversary has all the means to infer whether the overall amount of events k changes. This piece of information trivially discloses whether a WSN sensed more or less real events, hence real events do not enjoy the unobservability property anymore. Is it then possible to keep the adversary probability of success proportional while keeping real events unobservable? Is losing unobservability in favor of k-anonymity the right path to provide context privacy w.r.t. a WSN?

Open Issue 3: An enhanced privacy property k-anonymity

A subject is considered k-anonymous whenever it is concealed among k -1 other subjects. This concept has often be applied to solve the problem of releasing sensitive data-sets [START_REF] Sweeney | k-anonymity: A model for protecting privacy[END_REF]: a record was appointed as k-anonymous if the information for each person contained in the release (i.e. quasi-identifier) cannot be distinguished from at least k -1 individuals whose information also appears in the release. Other work (e.g. [START_REF] Ahn | k-anonymous message transmission[END_REF]) applied the same idea to anonymous communication networks: a sender was considered k-anonymous in case an external observer was not able to distinguish which of the k peers was the actual sender.

However, since the adversary physically checks the locations of both dummy and real events, one might desire that not only one event cannot be identified within k possible events, but also that all the others k-1 events are bogus ones. We call this privacy property k-anonymity. It holds if and only if a real event is concealed among k -1 dummy events.

Open Issue 4: Trajectory's anatomy

In order to conceal to an adversary the location of nodes sensing an event, we outlined in Section 4 an approach that generates dummy events. These dummy events are generated by sending to the sink node the same type of message used whether a real event is sensed. A global adversary, in fact, can not distinguish between messages corresponding to real events and those referred to dummy events. The context privacy of a real event is therefore assured.

The path induced by a real event.

The path induced by a dummy event.

(a) Legend.

(b) The trajectory induced by a vehicle (the real event) is continuous and never visits the same location multiple times. However, since we deal with mobile events, we need to take into account which nodes are cooperating to build a dummy mobile event. In other words, since a mobile event is supposed to span across different nodes, a real event is expected to exhibit a trajectory. Therefore, whenever we generate a dummy event, a proper set of nodes must be chosen in order to produce a trajectory that resembles a real one.

This problem can be exemplified in Figure 2 by analyzing the trajectories produced by an endangered panda and by a vehicle. We do not expect a vehicle to visit multiple times the same locations; a panda instead is more prone to visit locations, such as source of water, which have already been visited. Trying to anonymize a vehicle with trajectories produced by a panda splits the set of sensed events in two different subsets: the subset of dummy events and the one of real events. Once the adversary obtains the opportunity to correctly label these two subsets, the privacy of real events can not be any longer assured. The type of events a WSN is supposed to deal with is therefore an important piece of information for any sound and secure solution.

Open Issue 5: A metric for privacy and energy consumption

Wireless Sensor Network is a novel field where the consumption of energy is often a system requirement. Moreover, since all the nodes have a physical location, the initiator and the recipient of any communication may become sensitive assets.

A typical scenario is a WSN sensing a panda threatened by poachers: the node that initiates the communication trivially discloses the location of the panda; likewise, the recipient discloses where all the information is eventually collected.

In both cases an adversary can be interested in the disclosed information.

A Privacy Enhancing Technology (PET) has an immediate impact on the battery life of any type of device. Data privacy, for instance, is often provided by means of some security primitives to encrypt and decrypt the exchanged data. No matter which primitives are chosen, the node's CPU becomes accountable of any additional computation. This means that any node sending or receiving encrypted messages will suffer from a reduced battery life.

However, as mentioned before, applications relying on WSNs advise for novel solution in the field of contextual privacy. Since what has to be concealed are the nodes taking part in a communication, any PET has to generate additional traffic to somehow anonymize the real communication. In case of an active adversary, we point out the following trade-off: the more dummy traffic is generated, the more private the real communication is; consequently the more energy must be consumed in the process.

Providing any sort of PET is therefore a rather expensive task. Existing works [START_REF] Potlapally | A study of the energy consumption characteristics of cryptographic algorithms and security protocols[END_REF] proposed approaches to model the consumption of energy in terms of the adopted security primitive. What has not been yet proposed is a general model able to provide some reasoning to evaluate the proposed PETs. In particular, given a PET, we shall be able to assess the level of privacy the proposed solution provides, and the overhead produced in terms of energy consumption.

The latter is a rather interesting problem: since all the messages are eventually delivered to the sink node, we shall not expect an evenly distributed energy consumption. Instead, we may expect nodes close to the sink node to handle a higher rate of messages if compared to nodes lying on the perimeter. Figure 3 depicts exactly this behavior: nodes in the red circle are supposed to send more messages than nodes lying in a more external area. This kind of behavior creates what are known to be hot spots, i.e. areas where consumption of energy is A node that sensed a dummy event.

The sink node A node that sensed a real event.

The path induced by a real event.

A node that did not sense anything.

The path induced by a dummy event.

A message forwarded to the sink node. expected to be higher. We believe a PET shall take into the existence of these special ares, and mitigate their rate of occurrence.

Conclusion

In this paper we described different open issues in context privacy of Wireless Sensor Networks (WSNs). In particular, we considered the problem of hiding mobile events-e.g. presence of animal or vehicles-that are sensed by the network itself. We observed how current solutions designed to hide static events either (i) are not able to hide mobile events, or (ii) are not efficient. We think that the solution of the open issues presented in this paper would remove barriers for a wide adoption of WSNs. Our future works aim to solve these issues.

Fig. 1 .

 1 Fig. 1. The same WSN with two different events densities. The light circle represents the area the attacker may inspect in a given time interval Ta.

Fig. 2 .

 2 Fig. 2. Two different type of trajectories: a panda and a vehicle.

  (a) Legend. (b) Light-red area indicates a lower rate of messages. Dark-red area depicts the induced hotspot.

Fig. 3 .

 3 Fig. 3. Hot spot induced by the sink node being the ultimate recipient of any message.