Thierry Gautier
email: thierry.gautier@inrialpes.fr

João V F Lima
email: joao.lima@imag.fr

Nicolas Maillard
email: nicolas@inf.ufrgs.br

Bruno Raffin
email: bruno.raffin@inria.fr

Locality-Aware Work Stealing on Multi-CPU and Multi-GPU Architectures

Most recent HPC platforms have heterogeneous nodes composed of a combination of multi-core CPUs and accelerators, like GPUs. Scheduling on such architectures relies on a static partitioning and cost model. In this paper, we present a locality-aware work stealing scheduler for multi-CPU and multi-GPU architectures, which relies on the XKaapi runtime system. We show performance results on two dense linear algebra kernels, Cholesky (POTRF) and LU (GETRF) factorization, to evaluate our scheduler on a heterogeneous architecture composed of two hexa-core CPUs and eight NVIDIA Fermi GPUs. Our experiments show that an online locality-aware scheduling achieve performance results as good as static strategies, and in most cases outperform them.

Introduction

With the recent evolution of processor design, future generations of processors will contain hundreds of cores. The success of these machines will rely on the ability to schedule the workload at runtime, even for small problem instances.

Several libraries [START_REF] Robison | Optimization via reflection on work stealing in TBB[END_REF][START_REF] Broquedis | libKOMP, an Efficient OpenMP Runtime System for Both Fork-Join and Data Flow Paradigms[END_REF] or languages such as Cilk [START_REF] Frigo | The implementation of the Cilk-5 multithreaded language[END_REF], X10, Fortress, Chapel or OpenMP are designed to improve productivity with parallel constructs, such as for each. The main drawback of a for each construct is the addition of strong synchronization points to enforce the completion of a set of independent tasks, and the associated memory update, before a new task set can be executed. On the other hand, the data-flow model simplifies programming by unfolding parallelism based on data-flow dependencies between tasks. Runtime systems with support to data-flow programming are nowadays de facto standard for parallel linear algebra libraries on multi-cores [START_REF] Buttari | A class of parallel tiled linear algebra algorithms for multicore architectures[END_REF][START_REF] Kurzak | Scheduling dense linear algebra operations on multicore processors[END_REF][START_REF] Quintana-Ortí | Solving dense linear systems on platforms with multiple hardware accelerators[END_REF]. Besides, they can automatically move data between address spaces, such as on multi-CPU or multi-GPU architectures [START_REF] Augonnet | StarPU: a unified platform for task scheduling on heterogeneous multicore architectures[END_REF][START_REF] Ayguadé | An Extension of the StarSs Programming Model for Platforms with Multiple GPUs[END_REF][START_REF] Hermann | Multi-GPU and Multi-CPU Parallelization for Interactive Physics Simulations[END_REF][START_REF] Lima | Exploiting Concurrent GPU Operations for Efficient Work Stealing on Multi-GPUs[END_REF] or clusters [START_REF] Bueno | Productive Programming of GPU Clusters with OmpSs[END_REF][START_REF] Galilée | Athapascan-1: On-line building data flow graph in a parallel language[END_REF][START_REF] Song | A scalable framework for heterogeneous GPU-based clusters[END_REF].

However, the data-flow software cited above have some restrictions for heterogeneous architectures. Since their programming models only consider one level of parallelism, without the capacity to adapt the computation to the resource, their scheduling algorithms rely on static partitioning and cost models to guarantee the performance [START_REF] Augonnet | StarPU: a unified platform for task scheduling on heterogeneous multicore architectures[END_REF][START_REF] Kurzak | Scheduling dense linear algebra operations on multicore processors[END_REF], and none support recursive tasks, except [START_REF] Bueno | Productive Programming of GPU Clusters with OmpSs[END_REF][START_REF] Lima | Exploiting Concurrent GPU Operations for Efficient Work Stealing on Multi-GPUs[END_REF]. For instance, the ETF heuristic [START_REF] Boeres | On the scope of applicability of the ETF algorithm[END_REF] used in [START_REF] Augonnet | StarPU: a unified platform for task scheduling on heterogeneous multicore architectures[END_REF] relies on a cost model to predict performance based on the application's tasks and the hardware resources. The uncertainties related to the cost estimations and a poor worst case when communication costs are high, may impact the overall performance.

In this paper, we introduce a locality-aware work stealing scheduler for multi-CPU and multi-GPU architectures. Our solution relies on XKaapi, a runtime system for data-flow task programming on heterogeneous architectures. XKaapi combines a C++ interface for data-flow programming (Section 2) and a work stealing based scheduler to support multi-CPU and multi-GPU architectures (Section 3). The main contributions we propose are:

-A locality-aware work stealing algorithm based on heuristics to manage data locality and tackle the cache-unfriendly problem of classic work stealing [START_REF] Guo | Slaw: A scalable locality-aware adaptive work-stealing scheduler[END_REF], which is critical on multi-GPU systems; -A fully asynchronous task execution strategy on GPUs to overlap data transfers with GPU kernel executions.

We evaluate the XKaapi runtime with two dense linear algebra algorithms in double precision: Cholesky and LU factorization (Section 5). Our experiments show that XKaapi achieves a speedup of about 6 for Cholesky and 4.54 for LU when using eight GPUs and four CPUs over one GPU and one CPU. In terms of raw performance, with matrices of size 40960 × 40960, we attain about 1.79 TFlop/s on double precision Cholesky (3.92 TFlop/s on single precision), and 816.50 GFlop/s on double precision LU (1.24 TFlop/s on single precision).

Data-Flow Task Programming with XKaapi

The XKaapi4 task model [START_REF] Gautier | KAAPI: A thread scheduling runtime system for data flow computations on cluster of multi-processors[END_REF], as in Cilk [START_REF] Frigo | The implementation of the Cilk-5 multithreaded language[END_REF], Intel TBB [START_REF] Robison | Optimization via reflection on work stealing in TBB[END_REF], OpenMP-3.0 or StarSs [START_REF] Ayguadé | An Extension of the StarSs Programming Model for Platforms with Multiple GPUs[END_REF][START_REF] Bueno | Productive Programming of GPU Clusters with OmpSs[END_REF], enables non-blocking task creation: the caller creates the task and proceeds with the program execution. The semantic remains sequential such as XKaapi's predecessors Athapascan [START_REF] Galilée | Athapascan-1: On-line building data flow graph in a parallel language[END_REF] and KAAPI [START_REF] Gautier | KAAPI: A thread scheduling runtime system for data flow computations on cluster of multi-processors[END_REF], which was specialized for multi-CPU/multi-GPU iterative applications [START_REF] Hermann | Multi-GPU and Multi-CPU Parallelization for Interactive Physics Simulations[END_REF]. Still, in this paper, we introduce a general scheduling algorithm for multi-CPU/multi-GPU systems that enforces a locality-aware work stealing (Section 3).

XKaapi has several APIs (C, Fortran, C++) to program heterogeneous parallel architectures. In this paper, code fragments are presented using the C++ API. A XKaapi program is a sequential code complemented with annotations or runtime calls to create tasks. Parallelism is explicit, while the detection of synchronizations is implicit [START_REF] Gautier | KAAPI: A thread scheduling runtime system for data flow computations on cluster of multi-processors[END_REF]: the dependencies between tasks and the memory transfers are automatically managed by the runtime. A task is a side-effect free function call that returns no value except through its effective parameters. Tasks are created by calling the template function ka::Spawn. The code fragment of Figure 1 illustrates how to program a Cholesky factorization using the C++ API. The ka::Spawn<Task> creates a task of type Task. Each parameter rk,rm,rn corresponds to a range of indexes, and a construction such as A(rm,rk) represents the sub-matrix of elements A(i,j) where i,j are in the range rm,rk. The data type range 2D is an abstraction to view a memory region as a 2D array. Figure 1 also illustrates the definition of a task Signature (TaskSYRK) that includes the task parameters and their access modes (read R and/or write W and/or concurrent write CW). The implementations for CPU and GPU are given by the specialization of the TaskBodyCPU and TaskBodyGPU template class, respectively.

At least one implementation is expected per task signature (TaskSYRK in the example). The implementation can be recursive, calling the task signature and leaving to the scheduler the freedom to choose the more relevant implementation.

Extension for Multi-CPU and Multi-GPU

This section describes the features to support multi-CPU and multi-GPU5 in XKaapi through asynchronous task execution, concurrent GPU operations as provided by recent Fermi GPUs, and software cache memory.

Asynchronous Task Execution

Once a task is selected, the runtime ensures consistency of its input data on the GPU device before the GPU kernel executes. The runtime assumes that the GPU task implementation launches the GPU kernels asynchronously. Once a task implementation has launched computations on a GPU, the scheduler starts the execution of the next selected task by sending its input data in advance. This enables to overlap data transfers with kernel executions.

We empirically found that the best performance gain is obtained when having two tasks being processed per GPU. Starting more tasks do not increase performance significantly and reduce the capacity to balance the work load, because tasks can not be aborted neither reactivated after the start of a GPU transfer.

Data transfers and kernel invocation on a GPU are handled asynchronously as well as the completion of these operations. We have gathered these functionalities in an extension of CUDA streams presented in the next section.

Concurrent GPU Operations

Recent GPUs, such as NVIDIA's Fermi and Kepler, support new features for asynchronism. For instance, Fermi GPUs have one execution engine and two copy engines, enabling to concurrently perform a kernel execution and memory transfers (two-way host-to-device and device-to-host), under the condition that no explicit nor implicit synchronization occurs.

We developed a mechanism to take advantage of this asynchronism for multi-GPU systems. XKaapi splits the execution of a GPU task in two basic operations: host-to-device input transfers (H2D); and TaskBodyGPU execution (i.e. launch of CUDA kernels) (K). Since concurrency between data transfers and kernel launches must use CUDA streams, we defined a new data structure, called kstream, that groups together three CUDA streams: a stream for host-to-device transfer, a stream for kernel execution and a stream for device-to-host transfer. Once the kstream detects the event completion, it calls the callback function with its argument as parameter.

Data Management and Software Cache

XKaapi manages GPU memory through a software cache, based on the Least Recently Used (LRU) replacement policy. Each GPU thread maintains a FIFO queue of allocated memory blocks. When a GPU task requires accessing a host memory block that is not present on the GPU, the runtime will allocate memory and insert it in its own queue. In order to enable asynchronous memory transfers with CUDA, user data is page-locked through specific CUDA library function (cudaHostRegister).

If its memory is full, a GPU tries to evict the least recently used memory block of its own queue (LRU policy). If possible, unused blocks are reused without being freed. This optimization avoids unnecessary CUDA calls.

Consistency is guaranteed by a lazy strategy using a write-back policy. Data transfers to or from the GPU occur only when a task accesses data and when the data is in an invalid state in the target address space. This policy avoids unnecessary transfers, unlike write-through policy [START_REF] Quintana-Ortí | Solving dense linear systems on platforms with multiple hardware accelerators[END_REF][START_REF] Augonnet | StarPU: a unified platform for task scheduling on heterogeneous multicore architectures[END_REF][START_REF] Bueno | Productive Programming of GPU Clusters with OmpSs[END_REF]. All transfer operations are asynchronous and rely on the use of our kstream data structure to signal the completion of operations.

Locality-Aware Work Stealing

We extend each CPU or GPU thread with a local queue named mailbox in which remote threads can push tasks. This is similar to the approach proposed in [START_REF] Acar | The data locality of work stealing[END_REF], but without explicit locality annotation. Our locality-aware work stealing pushes the successors of a task to selected remote resources (CPU or GPU) based on meta-data information attached to each user data.

We developed two heuristics for local optimization, called H1 and H2,using these meta-data: H1 : For each task to be activated, XKaapi first goes through every task input parameter and looks for the resources where the parameter is valid, and its size. The resource which owns the biggest sum of input bytes in valid state is then chosen as the host to run the task. H2 : This second heuristic is based on the data access modes. It tries to reduce the invalidations of the data replicas: the scheduler pushes a newly activated task on the resource's mailbox that has a valid copy of its write or exclusive accessed parameters. If more than one resource is eligible, then the scheduler simply selects a resource at random among the set of eligible ones.

The XKaapi work stealing algorithm polls each time a GPU thread is idle. The callback mechanism enables to compose a sequence of operations and it is typically used by the GPU work stealing algorithm, first to insert data transfers for the input of a task, and then to invoke the kernel launch when the transfer ends. Experiments show that the heuristic H2 usually makes better local decisions, except for embarrassingly parallel applications, such as matrix product, where they both lead to a similar performance.

5E x p e r i m e n t s

All experiments have been conducted on an heterogeneous, multi-GPU system, named "Idgraf". Idgraf is composed of two hexa-core Intel Xeon X5650 CPUs (12 CPU cores total) running at 2.66 GHz with 72 GB of memory. It is enhanced with eight NVIDIA Tesla C2050 GPUs (Fermi architecture) of 448 GPU cores (scalar processors) running at 1.15 GHz each (2688 GPU cores total) with 3 GB GDDR5 per GPU (18 GB total). The machine has four PCIe switches to support up to eight GPUs. When two GPUs share a switch, their aggregated PCIe bandwidth is bounded to the one of a single PCIe 16x. Experiments using up to four GPUs always use one GPU per PCIe switch to avoid this bandwidth constraint. On the other hand, experiments using more than four GPUs have to share some pairs of GPUs through the PCIe switch.

We used as software environment GNU/Linux Debian squeeze x86/64, the compiler GCC 4.4, CUDA 4.1, and the library ATLAS 3.9.39 for the CPU versions of BLAS and LAPACK.

Dense Linear Algebra Benchmarks

Our experiments use the parallel version of the dense linear algebra problems Cholesky and LU factorization, as found in PLASMA [START_REF] Agullo | Lu factorization for accelerator-based systems[END_REF][START_REF] Buttari | A class of parallel tiled linear algebra algorithms for multicore architectures[END_REF]. The algorithms have been re-implemented in XKaapi to use its low overhead task creation. The matrix data layout is the same as in PLASMA (tile data layout). The parallel Cholesky factorization is a two levels parallel algorithm: at the upper level, we use the PLASMA algorithm with 1024 × 1024 tiles; at the lower level the panel Cholesky factorization (DPOTRF or SPOTRF) is parallelized using the same parallel algorithm as at upper level by decomposing one tile in sub-tiles of size 128 × 128. Our LU factorization is based on four PLASMA kernels: GETRF, GESSM, TSTRF, and SSSSM. We implemented the update tasks (GESSM and SSSSM) for GPUs based on PLASMA and MAGMA, and we used the panel tasks (GETRF and TSTRF)C P U kernels from PLASMA. The LU tile size is 1024 × 1024. We have not used autotuning to select the sizes of the tile and sub-tile, but an empirical approach: after a few experiments showing their average good performances, we have decided to use theses values.

Each result is a mean of 30 executions. The 95% confidence interval is represented on the graphs.

Comparison of Work Stealing Heuristics

In this section, we compare the performance of the H1 and H2h e u r i s t i c s( s e e section 4) against the default work stealing algorithm (label default), on the Cholesky (DPOTRF) and LU (DGETRF) factorization. The matrix size is constant (40960 × 40960) while we vary the number of GPUs. In addition to GPUs, we involve in the computations all remaining CPU cores, out of the 12 available, after removing the ones each GPU monopolizes to run its GPU thread.

Cholesky factorization Figures 2(a

Conclusion

The local optimization decisions made by the heuristics do not ensure global reduction of data transfers. The second heuristic H2triestominimize cache invalidations and seems to be more interesting: its effect is to keep data local to the resources, applying the classical "owner compute rule". The gain here is that the runtime automatically computes the right device to schedule the tasks without any programmer annotation. Besides, it is important to optimize the execution of tasks on the critical path such as the panel tasks in Cholesky and LU. Our Cholesky implementation with two-level parallelism allows the use of all remaining CPU cores for panel tasks and reduces idle time of GPUs with update tasks. On the other hand, our LU version with two panel tasks benefits from more CPUs than GPUs. Hence, in our experiments, LU scales better with up to six CPUs and six GPUs than four CPUs and eight GPUs.

In experiments with more than four GPUs, at least two GPUs share the same PCIe-16x bus. Consequently, a scheduling algorithm that introduces a lot of memory transfer is more penalized on such hardware.

We note that our heuristic allows to obtain very good results. To our knowledge, this is the first time that teraflop performances are reported on a multi-core machine with up to eight GPUs. Moreover, these results were obtained using a purely dynamic work stealing algorithm. that the performance gain between the default work stealing four CPUs and eight GPUs for this experience, and a varying matrix size. With the default work stealing strategy, the overlap enables to increase the performance of up to 160.28 GFlop/s for the largest matrices (40960 × 40960). For small matrices the difference is of course negligible. With the H2 heuristic, the gain reaches 550.48 GFlop/s of difference for 40960 × 40960. and our H2 heuristic is about 431.45 GFlop/s without any overlapping. Hence, it supports the importance of our H2 heuristic even without other GPU optimizations.

Overlapping on Multi-GPU

Scalability of the Cholesky and LU Factorizations

Figure 5 gives an overview of the performances that have been achieved on the Cholesky and LU factorizations for difference matrix sizes on eight GPUs and four CPUs using our two heuristics and default work stealing. Except for matrices of size 4096 × 4096, which results are almost equal, H2 gives the best performance for all matrix sizes and scales as the matrix size grows.

6R e l a t e d W o r k s

OmpSs [START_REF] Bueno | Productive Programming of GPU Clusters with OmpSs[END_REF] is a programming tool that provides a set of OpenMP-like pragmas and a runtime system to schedule tasks while preserving dependencies. OmpSs locality-aware scheduling is similar to our H1 heuristic. To our knowledge, OmpSs has concurrent execution and data transfers in GPUs, but it shows some issues with matrix sizes that can not be entirely stored into the GPU memory.

StarPU is a runtime system for scheduling a DAG of tasks on heterogeneous architecture [START_REF] Augonnet | StarPU: a unified platform for task scheduling on heterogeneous multicore architectures[END_REF]. In a similar way, StarPU provides a programming model for heterogeneous architectures and exposes an API to describe a scheduling policy that allows flexibility in the work distribution. Its scheduler uses the HEFT [START_REF] Boeres | On the scope of applicability of the ETF algorithm[END_REF] algorithm to schedule all ready tasks, thanks to cost models for data transfer and task execution. In a recent work [START_REF] Lima | Exploiting Concurrent GPU Operations for Efficient Work Stealing on Multi-GPUs[END_REF], we show that our dynamic work stealing without heuristic (labelled 'default' in experimental section) reaches the same level of performances as StarPU on the matrix product and Cholesky factorization with a sequential panel factorization.

In the context of dense linear algebra algorithms, PLASMA [START_REF] Buttari | A class of parallel tiled linear algebra algorithms for multicore architectures[END_REF] provides fine-grained parallel linear algebra routines with dynamic scheduling through QUARK, which was conceived specially for numerical algorithms. FLAME [START_REF] Quintana-Ortí | Solving dense linear systems on platforms with multiple hardware accelerators[END_REF] is a high-level notation to express algorithms for dense linear algebra operations on multi-CPU/multi-GPU. MAGMA [START_REF] Tomov | Towards dense linear algebra for hybrid GPU accelerated manycore systems[END_REF] implements static scheduling for linear algebra algorithms on heterogeneous systems composed of GPUs. Recently it has included some methods with dynamic scheduling in multi-CPU and multi-GPU on top of QUARK or StarPU, in addition to the static multi-GPU version.

Our H2 heuristic is inspired from [START_REF] Acar | The data locality of work stealing[END_REF], but with an automatic scheme to (locally) reduce the number of cache invalidations instead of the explicit annotation of the user code. In SLAW [START_REF] Guo | Slaw: A scalable locality-aware adaptive work-stealing scheduler[END_REF] a similar heuristic is experimented. As in [START_REF] Acar | The data locality of work stealing[END_REF], the programmer is responsible to explicitly specify the location where his task need to run.

To the knowledge of the authors, this is the first time that results on classical linear algebra subroutine are reported with more than four GPUs. Moreover, almost all previous reported results with high level of performances on a multi-GPU/multi-CPU are based on static scheduling.

Conclusion

In this paper, we presented a locality-aware work stealing scheduler for multi-CPU and multi-GPU architectures, which relies on XKaapi, a runtime system for data-flow task programming on heterogeneous architectures. XKaapi enables dynamic scheduling based on work stealing for multi-CPU and multi-GPU architectures. The key contributions of this paper include (1) an original localityaware work stealing for multi-GPU systems based on local reduction of cache invalidations, (2) a fully asynchronous task execution strategy on GPUs to overlap transfers with kernel executions.

Our experiments report results up to eight GPUs on two dense linear algebra problems. The performance results obtained are about 1.79 TFlop/s for Cholesky and 816.50 GFlop/s for LU on double precision. As far as the authors know, this is the best performance measured on a heterogeneous architecture with such a large number of GPUs. Previous related works on the same problems only report results up to four GPUs using static scheduling or static data distribution. For an equivalent configuration our dynamic approach obtains similar -or better -r e s u l t s .

Future works include new experimental evaluations on other dense or sparse linear algebra problems such as QR factorization with new incoming accelerators such as the future Intel Xeon Phi (Intel MIC) or the next Kepler GT110 GPU.

/Fig. 1 .

 1 Fig. 1. Example of a XKaapi C++ Cholesky factorization. It shows a task Signature with its parameters and access modes, as well as CPU and GPU implementations. The calls to cblas dsyrk and cublasDsyrk are simplified.

  ) and 2(b) illustrate our performance results. We conclude that: (a) the default heuristic has a bigger communication footprint that explains its poor scalability on more than four GPUs; (b) heuristic Total data transfers (GB).

Fig. 2 .

 2 Fig. 2. Performance results of DPOTRF on eight GPUs and four CPUs for a matrix size of 40960 × 40960.

( a )

 a Performance in GFlop/s. (b) Total data transfers (GB).

Fig. 3 .

 3 Fig. 3. Performance results of DGETRF on eight GPUs and four CPUs for a matrix size of 40960 × 40960.

Figure 4

 4 Figure 4 refines the analysis of the performance impact when data transfers are overlapped with kernel executions, with the default work stealing and the H2 heuristic, on the Cholesky factorization. We have used We can also note

Fig. 4 .

 4 Fig. 4. Gain of overlapping on DPOTRF using 4 CPUs and 8 GPUs.

Fig. 5 .

 5 Fig. 5. Scalability of the two heuristic and default work stealing with DPOTRF (left) and DGETRF (right) on eight GPUs and four CPUs.

http://kaapi.gforge.inria.fr

Our current version supports NVIDIA CUDA.

Acknowledgment

The authors would like to thank Fabien Lementec for providing early implementations on GPU support. This work has been partially supported by the ANR-11-BS02-013 HPAC Project, the ANR 09-COSI-011-05 Project Repdyn and CAPES/Brazil.


Djamé Seddah

Benoit Sagot

Marie Candito

Virginie Mouilleron

Vanessa Combet

The French Social Media Bank: a Treebank of Noisy User Generated Content

Keywords: Treebanking, User Generated Content, Parsing, Social Media

In recent years, statistical parsers have reached high performance levels on well-edited texts. Domain adaptation techniques have improved parsing results on text genres differing from the journalistic data most parsers are trained on. However, such corpora usually comply with standard linguistic, spelling and typographic conventions. In the meantime, the emergence of Web 2.0 communication media has caused the apparition of new types of online textual data. Although valuable, e.g., in terms of data mining and sentiment analysis, such user-generated content rarely complies with standard conventions: they are noisy. This prevents most NLP tools, especially treebank based parsers, from performing well on such data. For this reason, we have developed the French Social Media Bank, the first user-generated content treebank for French, a morphologically rich language (MRL). The first release of this resource contains 1,700 sentences from various Web 2.0 sources, including data specifically chosen for their high noisiness. We describe here how we created this treebank and expose the methodology we used for fully annotating it. We also provide baseline POS tagging and statistical constituency parsing results, which are lower by far than usual results on edited texts. This highlights the high difficulty of automatically processing such noisy data in a MRL.

Introduction

Complaining about the lack of robustness of statistical parsers whenever they are applied on out-of-domain text has almost became an overused cliché over the last few years. It remains true that such parsers only perform well on texts that are comparable to their training corpus, especially in terms of genre. As noted by [START_REF] Foster | cba to check the spelling": Investigating parser performance on discussion forum posts[END_REF] and [START_REF] Foster | From news to comment: Resources and benchmarks for parsing the language of web 2.0[END_REF], most studies on out-of-domain statistical parsing have been focusing mainly on slightly different newspaper texts [START_REF] Gildea | Corpus variation and parser performance[END_REF]McClosky et al., 2006a,b), biomedical data [START_REF] Lease | Parsing biomedical literature[END_REF]Mc-Closky and Charniak, 2008) or balanced corpora mixing different genres [START_REF] Foster | Adapting wsj-trained parsers to the british national corpus using in-domain self-training[END_REF]. The common point between these corpora is that they are edited texts. This means that their underlying syntax, spelling, tokenization and typography remain standard, even if they slightly depart from the newspaper genre. Therefore, standard NLP tools can be used on such corpora. Now, new forms of electronic communication have emerged in the last few years,namely social media and Web 2.0 communication media, either synchronous (micro-blogging) or asynchronous (forums), and the need for comprehensive ways of coping with the new languages types carried by those media is becoming of crucial importance. In fact, the main consequence of the Web 2.0 revolution is that what was formerly restricted to one's inner circle of relations has now became widely available and is furthermore seen as containing potentially the same informativeness as written broadcast productions, that have undergone a full editorial chain, and that serve, most of the time, as the basis of our treebanks. Anyway, if those unlimited stream of texts were all written with the same level of proficiency as our canonical data source, the problem would be simply1 a matter of domain adaptation. Yet, this is far from being the case as shown by [START_REF] Foster | cba to check the spelling": Investigating parser performance on discussion forum posts[END_REF]. Indeed, in her seminal work on parsing web data, different issues preventing reasonably good parsing performance were highlighted; most of them were tied to lexical differences (coming from either genuine unknown words, typographical divergences, bad segmentation, etc.) or syntactic structures absent from training data (imperative usage, direct discourse, slang, etc.). This suboptimal parsing behavior on web data was in turn confirmed in follow-up works on Twitter and IRC chat (Foster et al., 2011a;[START_REF] Gimpel | Part-of-speech tagging for twitter: Annotation, features, and experiments[END_REF][START_REF] Elsner | Disentangling chat with local coherence models[END_REF]. They were again confirmed during the SANCL shared task, organized by Google, aimed at assessing the performances of parsers on various genres of Web texts [START_REF] Petrov | Overview of the 2012 Shared Task on Parsing the Web[END_REF]. Needless to say, such observations are likely to be even more true on web data written in morphologically rich languages (MRLS). These languages are already known to be arguably harder to parse than English for a variety of reasons (e.g., small treebank size, rich inflexion, free word order, etc.) exposed in details in [START_REF] Tsarfaty | Statistical parsing of morphologically rich languages (spmrl) what, how and whither[END_REF]. However, a lot of progress has been made in parsing MRLS using, for examples, techniques built on richer syntactic models, lexical data sparseness reduction or rich feature set. See [START_REF] Tsarfaty | Relational-realizational parsing[END_REF][START_REF] Versley | Scalable discriminative parsing for german[END_REF]Candito and Crabbé, 2009;[START_REF] Green | Better arabic parsing: Baselines, evaluations, and analysis[END_REF] to name but a few. The questions are thus to know: (1) to what extend MRL user generated content is parsable? and (2) more importantly, what is needed to fill that performance gap?

To answer question 1, we introduce the first release of the French Social Media Treebank, a representative gold standard treebank for French user-generated data. This treebank consists in around 1,700 sentences extracted from various types of French Web 2.0 user generated content (Facebook, Twitter, video games and medical board). This treebank was developed independently from the Google Web Treebank [START_REF] Bies | English web treebank. Technical report, Linguistic Data Consortium[END_REF], the treebank used as development and test data for the above-mentioned SANCL shared task. In order to get first insights into question 2, we provide a first set of POS tagging and parsing results using state-of-the-art systems trained on the French Treebank (FTB, [START_REF] Abeillé | Building a Treebank for French[END_REF]), using our treebank as an evaluation corpus. These results show how difficult it is to process French user-generated data: for example, parsing results range from an astoundingly low 39.11% of labeled brackets F-score for the noisiest type of texts to 71-72% for better edited web parts -to be compared with the 86-89% regularly obtained on the FTB.

In the remaining of this paper, we first describe how we built the French Social Media Bank and the underlying motivations; we then introduce our annotation scheme which is based on the French Treebank [START_REF] Abeillé | Building a Treebank for French[END_REF] guidelines but extends it in many ways, due to the specificities of user-generated content. Next, we describe our annotation methodology, including the pre-processing tools that we developed and used, which were specifically adapted to deal with noisy texts. Finally, we discuss the results of baseline evaluation experiments on POS tagging, including results when using a dedicated wrapper for dealing with noisy texts, and constituency parsing. Since our tools were only trained on the FTB, which means that our results are baselines for future work based on our new French Social Media Bank.

Motivation and Corpus

As its English counterpart, the French web 2.0 generates a virtually unlimited stream of textual data. This term covers a wide range of practices, among which we decided to focus on microblogging (FACEBOOK and TWITTER) and on two types of web forums: one dedicated to general health issues for a wide public audience, DOCTISSIMO and one centered around video games issues (platform, help centers), JEUXVIDEOS.COM. 2 As we said in the introduction, we want to use these corpora to evaluate how difficult it is to parse raw user generated content in French and establish a realistic baseline using techniques we have successfully applied on well-written French texts.

To this end, we selected our corpora by direct examination through various search queries and ranked the texts according to our perception of how far they were from the French Treebank style (see below for details). We further added some very noisy texts to serve as a stress test for French statistical parsing.

Measuring noisiness

In order to quantitatively corroborate our intuitions concerning the level of noise in our corpora, and for measuring their various levels of divergence compared to the French Treebank [START_REF] Abeillé | Building a Treebank for French[END_REF], we defined an ad-hoc noisiness metrics. It is simply defined as a variant of the Kullback-Leibler divergence 3 between the distribution of trigrams of characters in a given corpus and the distribution of trigrams of characters in a reference corpus. 4 As can be seen from Table 2, to which we added scores for the FTB dev and test sets for comparison purposes, our intuitions are confirmed by this metric. It shows that we cover various levels of noisiness, and that our reference corpus actually diverges more from the subcorpora that we have tagged as particularly noisy. As we shall see below, we have used this information for deciding for each subcorpus whether to pre-annotate it in a standard way or using a dedicated noise-tolerant architecture described in section in Section 5.1.

Corpus Overview

In this section we briefly introduce our corpora. All but the JEUXVIDEOS.COM corpus were collected in two phases: A first one dedicated to a light study of their contents (lexical differences, required level of preprocessing, etc.). At first glance, they seemed almost too edited and almost too easy for our parser. So in a second phase, we decided to look explicitly for texts harder to read and understand for average French speakers. We used French slang words in our search queries, including verlan 5 words, as well as urban youth idiomatic constructions such as grave 6 or sa race 7 . This lead to subcorpora that we found noisier, as was confirmed by the above-described metrics (see Table 2). In the case of the DOCTISSIMO part, we gathered texts from a forum dedicated to sexual intercourse problems between young adults. This choice was not without causing ethical concerns but given the fact that all private mentions were of course anonymized and all explicit references were filtered out, we ended up with 50 extremely noisy sentences, but greatly diverging from the newswire genre, and thus extremely 3 It differs from a standard Kullback-Leibler distance because we apply a preliminary pre-processing to the corpora involved: (i) URLs, e-mail addresses, Twitter hashtags and mentions are removed, (ii) all characters that do not belong to an extensive list of characters that might be used in French sentences are replaced by a unique "non-standard character," (iii) non-content sentences are ignored (e.g., tweet headers such as Firstname Lastname @firstnamelastname).

4 Preliminary experiments on character bigrams and 4-grams have shown that the former are not informative enough and the latter lead to similar results than with trigrams. We also tried comparing distributions of tokens. Correlation with both intuition and parsing accuracy prove similar to that obtained with character 3-grams. However, token-based distribution divergences are less adequate for several reasons, among which: (i) correctly spelled unknown words affect more heavily token distributions than character-based distributions, whereas they should not affect the noisiness measure (e.g., they have a limited impact on tagging and parsing accuracy); (ii) character trigram distributions are less sparse than token distributions; (iii) there are more character trigrams than tokens in a sentence. Put together, the two last reasons show that a sound noisiness score on small corpora, or even at the sentence level, is more likely to be sound when working on character trigrams than on tokens.

5 Very common French slang words where syllables are inverted to form new words which can in turn be verlanized. For instance, arabe 'arabic' is turned into beur which has been inverted again into rebeu.

6 Post or pre-verbal intensifier adverb. J'ai adoré grave!, similar in meaning and style to I totally enjoyed it!.

7 Post-verbal intensifier adverbial phrase, with the same usage as "one's a.. off."

interesting to evaluate our parsing chain.

Let us now describe and give examples for the various extracted subcorpora.

JEUXVIDEOS.COM 8

We collected data from 4 threads: Call of Duty: Modern Warfare 3 c , PC, Xbox 360 c , Wii c and Linux. Apart from spelling errors often involving phonetic spelling, which is found in all our corpora, this corpus is interesting because of the frequent use of English words, if not phrases, and a highly specialized lexicon.

In the examples below, the first line reproduces the original text, the second line is a standardized French version and the third line, an English translation attempt.

( DOCTISSIMO This corpus is made of two parts, each focusing on a different subtopic concerning birth control: patch birth control and pregnancy test related questions. These topics are populated by women of different ages and with different writing styles. The latter one being filled by younger women, the writing style is somewhat more sloppy. Moreover, as mentioned above, we added 50 extremely noisy sentences from the sexual intercourse section.

(2) a. pt que les choses ont changé depuis ? Peut-être que les choses ont changé depuis ? Maybe things have changed since then?

b. lol vu que 2-3 smaine apres qd jai su que j'etai enceinte jetai de 3 semaine..... lol, vu que 2-3 semaines après, quand j'ai su que j'étais enceinte, je l'étais de 3 semaines.... Lol, given that 2-3 weeks later, when I learned I was pregnant, I was for 3 weeks... c. car je ne me senté pa desiré, pa aimé, pa bel du cou, g t pa grd chose en fet.

Car je ne me sentais pas désirée, pas aimée, pas belle du coup, je n'étais pas grand chose en fait.

Because I didn't feel desired, nor loved, thus not beautiful, I wasn't much actually.

TWITTER This corpus is made of two parts: the first one focuses on news events of late November 2011. 9 Because all these tweets seemed to originate from semi-professional writers (mostly bloggers, journalists, politically engaged people), we built a second part with genuine non edited text. We used a list of keywords to gather such tweets and selected a balanced subset of those, as far as the style of writing is concerned.

(3) a. Je soupçonnes que "l'enfarineuse" était en faite une cocaineuse vu la pêche de #Hollande ce soir à #Rouen.

Je soupçonne que l'enfarineuse était en faite une cocaïneuse vu la pêche de #Hollande ce soir à #Rouen. I suspect that the "flouring-lady" was actually a cocaïn-lady given the energy of #Hollande this night at #Rouen.

b. @IziiBabe C mm pa élégant wsh tpx mm pa marshé a coté dsa d meufs ki fnt les thugs c mm pa leur rôle wsh Ce n'est même pas élégant voyons, tu ne peux même pas marcher à coté de sa petite amie qu'ils font les voyous, ce n'est même pas leur rôle voyons. It is not even elegant. One cannot even walk besides his girl friend, they already start bullying people. It is not even their role.10 FACEBOOK This corpus was built using publicly available comment threads on public profiles, with a focus on relatively known reality TV pseudo-artists known for their personal usage of French mixed with English. More texts were added using queries based on common first names (Sophie, Romain) and some French public personalities . One of the difficulties of FACEBOOK lies in the varying usage of the displayed login name in comments: it can either be part of the sentence (e.g., "[Spiderman] is tired") or not (e.g., "[Spiderman] I'm tired"). We decided to systematically keep these logins. We leave it to a post-processing step to remove them if appropriate. Note that the noisiest part of this corpus was not taken into account while adapting our POS tagger as described below.

(

Linguistics of user generated content

It is important to note that the aim of our work is to provide a sample of user-generated texts that are particularly difficult to parse for any parser based on an edited text treebank. It does not correspond to an single homogenous domain, although some specificities of user-generated content are found across various types of web data. Moreover, in some cases, and most notably TWITTER, such data include both linguistic content and media-specific meta-language. This meta-language (such as TWITTER's "RT" ("Retweet"), at-mentions and hashtags) is to be extracted before parsing per se or other types of linguistic processing. In this work, we focused on the linguistic content. Therefore, we deal with meta-language tokens only when they are embedded within or adjacent to purely linguistic content (e.g., the tweet itself, provided it consists of one or several sentences).

Prevalent idiosyncrasies in user generated content can be characterized on two axes: one which can be roughly describe as "the encoding simplification axis" which covers ergographic (1) and transverse phenomena (2) and the other "sentiment expression axis" which cover phenomena, qualified below as marks of expressiveness (3), emulating the same goal as sentiment expressed through prosody and gesture in direct interaction.

1. Ergographic phenomena, that is phenomenon aiming at reducing the writing effort, perceived as first glance as genuine misspell errors, cover in fact such a various set of strategies it can be seen as a simplification of the encoding. Besides obvious typos, such as letter inversion 11 , errors in letter doubling 12 , wrong present participle 13 and so on, misspellings can be hard to categorize as such if they result in simpler word forms. This is why we include this category in the following list of phenomenon even if its intentionality is not always attested. To this list we can also note the somewhat frequent omission of copula verbs and more generally different forms of elision (the subject pronoun, the negative adverb "ne"). Although not strictly lexical, this omission results also in less writing efforts. This is also noted in the Google Web Treebank where they compare this tendency in user generated content English to pro-drop languages' clitic elision.

2. Transverse phenomenon: Contractions and typographic diaeresis. Some phenomena can affect the number of tokens, compared to standard French, either by replacing several standard language tokens by only one, which we shall call a contraction, or conversely by splitting one standard language token into several tokens, called typographic diaeresis. Such phenomena are frequent in our corpora, and they need a specific annotation scheme (cf. Section 4). Note that the resulting non-standard tokens might be homographs of existing words, bringing more ambiguities if not properly analyzed.

Contractions are way more diverse than in standard French (as instanced in the FTB).

The only contractions that exist in standard French involve the prepositions à and de when followed by the definite article le(s) or the (rare) relative pronoun le(s)quel(s). For instance, à les 'to the PLUR ' mandatorily becomes au.

Within the FRENCH SOCIAL MEDIA BANK, we found sequences such as: (i) contraction between a subject clitic, a verbal form and a negation particle (e.g., lapa for elle n'a pas, 'she has not') ; (ii) contraction of interrogative verbal forms (e.g., atu for as-tu, 'have you') ; (iii) contraction and apocope of word compounds (e.g., nimp for n'importe quoi, 'rubbish'); (iv) contraction of determiners and nouns (e.g., lesprit for l'esprit, 'the spirit') and (v) contraction of object relative pronouns (or subordinate conjunction) and subject clitic (e.g., qil for qu'il, literally 'that he').

Typographic diaeresis can be illustrated by c a dire, where these three tokens stand for the standard one-token conjunction c'est-à-dire (standing for "that is" or "namely"). It can also happen on top of a presumably already contracted token (e.g., c t for ct/c'était,'it was'). Note that many contractions and typographic diaeresis are built around a verb which is prefixed by a clitic. Therefore such contractions can project function labels and most of the time are the head of the sentence. Their mishandling can therefore propagate errors way beyond their immediate morpho-syntactic context and thus impacts parser performance very strongly.

Marks of expressiveness

Our treebank focuses in providing a sample of French Social Media web data, therefore most of its content describe dialogs and various forms of interaction between users through social media interface. Lacking ways of expressing sentiments, irony or anger through prosody and gesture, users deploy a wide range of strategy to add another dimension to their text stream. Most of them are evident, like graphical stretching, overuse of strong punctuation marks (as in "BEST. MOVIE. EVER." or "!!!!Greaaat!!!), abuse of emoticons, sometimes used as a verb (e.g., Je t'<3 for Je t'aime,'I love you') or inside usernames, mixing between lowercase and uppercase and so on. Some are more anecdotal and tied to the particular type of software used to support a web forum, which allows the inclusion of url pointing to an animated picture, itself used to replace an emoticon. Needless to say that such urls add a considerable amount of noise in web forum texts. We list the main cases of such phenomenon in the table below. Obviously the main effect of those different writing artifacts is to considerably increase the level of unknown words (compared to a treebank). More importantly, the new morphology brought by the those phenomenon complicates any processing based on regular unknown word identification through suffix analysis. However, our general annotation strategy consists in staying as close as possible from the French Treebank guidelines [START_REF] Abeillé | Building a Treebank for French[END_REF] in order to have a data set as compatible, as much as possible, with existing resources.

Annotation scheme

In order to obtain evaluation treebanks compatible with parsers trained on the FTB, we have used as basis the FTB annotation scheme and followed as much as possible the corresponding annotation guidelines for morphology, syntagmatic structure and functional annotation [START_REF] Abeillé | Building a Treebank for French[END_REF]. More precisely, we started from a slight modification of this annotation scheme, referred to as the FTB-UC and added specific guidelines for handling idiosyncrasies user-generated content corpora.

FTB-UC vs. FTB

We targeted the annotation scheme of the FTB-UC (Candito and Crabbé, 2009), that was obtained by automatic modification of the FTB. The modifications with respect to the orignal FTB concern the tagset, the standardization of preposition and complementizer projections, and multi-word units:

• Multi-word units are very frequent in the FTB: 17% of the tokens belong to a compound. Compounds range from very frozen multi-word expressions like y compris 'including' (literally 'there included') to named entities. They include syntactically regular compounds with compositional semantics, such as loi agraire 'land law', that are encoded as compounds because of a non-free lexical selection. These syntactically regular compounds tend to be inconsistently encoded in the FTB. 14 Further, the FTB includes "verbal compounds" that are potentially discontinuous, which provoke variable annotations. In the FTB-UC, these syntactically regular compounds are automatically mapped to a regular syntagmatic representation. We followed this rule for the annotation of the French Social Media Treebank. This has the virtue of uniformity, but clearly requires further treatment to spot clear cases of compounds (with non compositional semantics). • Tagset: the tagset includes 28 POS tags -originally tuned by [START_REF] Crabbé | Expériences d'analyse syntaxique statistique du français[END_REF] to optimize parsing-, which are a combination of one of the 13 coarse-grained categories and other information that is encoded in the FTB as features, such as verbal mood information, proper versus common noun distinction, wh-feature, etc. • Complementizers and prepositions: we annotate so that prepositions project a PP independently of the category of their object, contrary to the FTB's guidelines, in which prepositions with nominal objects project a PP, but those with infinitival objects don't. Further, we systematically use a sentential phrase as sister node to complementizers, contrary to the flat structure of the FTB.

Other notable additions to the annotation scheme concern the non-terminal tagset to which we added the FRAG label. It concerns phrases that cannot be syntactically attached to the main clause of a syntactic unit, e.g., mostly salutations, time stamp, meta sentential marks of emotion (emoticons, strong interjections). It also covers the case of usernames, at-mentions, and URL appended to a post/sentence (cf. FACEBOOK sentence 4a).

Additional extensions

A first extension needed for dealing with our data was to add two new POS tags, namely HT for TWITTER hashtags and META for meta-textual tokens, such as TWITTER's "RT". Note that TWITTER at-mentions as well as URLs and e-mail addresses have been tagged NPP. The rationale for this is to remain consistent with our tagging and parsing models trained on the FTB, which do not contain such tokens. This constitutes the main difference with other works on user-generated data.

However, the main extensions we added to the FTB annotation scheme are related to contraction and typographic diaeresis phenomena described in Section 3. The way we annotate (and automatically preannotate) such sequences is illustrated in Table 4. Let us now provide a few more details on each of these two cases.

Contracted tokens are associated with a combined POS tag which lists the sequence of each underlying words' tag. Let us illustrate this on qil, a non-standard contraction for qu' il. At least in some contexts, the tokens in the standard version qu' il would have been tagged respectively CS and CLS. In such contexts, the non-standard contracted token qil is tagged CS+CLS. Table 3 lists all such compound tags occurring more than twice in the treebank (37 more remaining).In some cases, such contractions involve two underlying forms, one being a verb and the other an argument of the verb (e.g., jai for j' ai 'I have'). In such cases, function labels are associated directly with the contracted token.

On the other hand, in cases of typographic diaeresis, the category of the multi-token standard counterpart is given to the last token, all others receive the special tag Y. Taking c a dire as an Note that both phenomena can appear together. This is the case for example with c t instead of c' était 'it was' (tag sequence: CLS V): both letters c and t are used phonetically -as in using U for you in English -and sound like the two syllables of c'é and tait. Therefore, mapping c to c' and t to était is not adequate. In this case, we consider that a contraction followed by an typographic diaeresis has occurred, and associate c with the tag Y and t with CLS+V.

Annotation Methodology

We built manually validated treebank following a now well established methodology: we first defined a sequence of annotation layers, namely (i) sentence splitting, tokenization and POS tagging, (ii) syntagmatic parsing, (iii) functional annotation. Each layer is annotated by an automatic preprocessing that relies on previously annotated layers, followed by validation and correction by human annotators. At each step, annotators were able modify the choices made at previous stages. Our methodology is summarized as follows and detailed section 5.1:

• Segmentation, tokenization and POS tagging followed by manual validation and correction by one expert annotator. • Constituency parsing followed by manual validation and correction by two annotators followed by an adjudication step. • Functional annotation followed by manual validation and correction by two annotators followed by and adjudication step.

Pre-annotation strategies for the tokenization and POS layers

As mentioned above, we used two different strategies for tokenization and POS pre-annotation, depending on the noisiness score.

For less noisy corpora (those with a noisiness score below 1), we used a slightly extended version of the tokenization and sentence splitting tools from our standard FTB-based parsing architecture, Bonsai (Candito et al., 2010). This is because we want to have a tokenization that is as close as possible from the principles underlying the FTB's tokenization. Next, we used the POS-tagger MORFETTE [START_REF] Chrupała | Learning morphology with morfette[END_REF] as a pre-annotator.

For corpora with a high noisiness score, we used a specifically developed pre-annotation process. This is because in such corpora, spelling errors are even more frequent, but also because the original tokens rarely match sound linguistic units, as can be seen on the example in Table 4 taken from the DOCTISSIMO file with the highest noisiness score. The idea underlying this pre-processing is to wrap the POS tagger (in this case, MElt) in such a way that it actually has to tag a sequence of tokens that is as close as possible to standard French, or, rather, to its training corpus (in this case, the FTB). Hence the following process, illustrated on a real example in Table 4: 1. We first apply several regular-expression-based grammars taken from the SxPipe preprocessing chain [START_REF] Sagot | SXPipe 2 : architecture pour le traitement présyntaxique de corpus bruts[END_REF] for detecting smileys, URLs, e-mail addresses, Twitter hashtags and similar entities, in order to consider them as one token even if they contain whitespaces. 2. Next, we use the same tokenizer as for less noisy corpora. 3. We apply a set of 327 rewriting rules that were forged as follows: first, we extracted from our development corpus (all subcorpora but for the noisy Facebook subcorpus) n-gram sequences involving unknown tokens or occurring at an unexpectedly high frequency; then we manually selected the relevant ones and provided them manually with a corresponding "correction". The number of "corrected tokens" obtained by applying these rules might be different from the number of original tokens. In such cases, we use 1-to-n or n-to-1 mappings. For example, the rule ni a pa → n' y a pas explicitely states that ni is an amalgam for n' and y, whereas pas is the correction of pa. 4. We use the MElt tagger [START_REF] Denis | Coupling an annotated corpus and a morphosyntactic lexicon for state-of-the-art pos tagging with less human effort[END_REF], trained on the FTB-UC and the Lefff lexicon [START_REF] Sagot | The Lefff, a freely available and large-coverage morphological and syntactic lexicon for french[END_REF], for POS-tagging the sequence of corrected "tokens". 5. We apply a set of 15 generic and almost language-independent manually crafted rewriting rules, originally developed for English data (see below), that aim at assigning the correct POS to tokens that belong to categories not found in MElt's training corpus, i.e., the FTB; for example, all URLs and e-mail addresses are post-tagged as proper nouns whatever the tag provided by MElt; likewise, all smileys get the POS for interjections. 6. We assign POS tags to the original tokens based on the mappings between corrected POStagged tokens and original ones, and following the guidelines given in section 4.2. If a unique corrected token is mapped to more than one original tokens, all tokens but the last one are assigned the tag Y, and the last one receives the tag of the unique corrected token. If more than one corrected tokens are mapped to one original token, it is assigned a tag obtained by concatenating the tags of all corrected tokens, separated by the '+' sign.

If the mapping is one-to-one, the POS tag provided by MElt for the corrected token is assigned to the corresponding original token.

This architecture is now available as part of the MElt distribution. It was also applied on English web data in the context of the SANCL shared task on parsing web data [START_REF] Petrov | Overview of the 2012 Shared Task on Parsing the Web[END_REF], with state-of-the-art results [START_REF] Seddah | The Alpage Architecture at the SANCL 2012 Shared Task: Robust Preprocessing and Lexical bridging for user-generated content parsing[END_REF].

Annotation strategy for constituency and functional annotation

Parse pre-annotation was achieved using a state-of-the-art statistical parser trained on the FTB-UC, provided with the manually validated tagging. The parser we used was the Berkeley parser [START_REF] Petrov | Improved inference for unlexicalized parsing[END_REF] adapted to French [START_REF] Crabbé | Expériences d'analyse syntaxique statistique du français[END_REF]. Note that when the validated pos tags were discarded by the parser, in case of too many unknown word-pos pairs, those were reinserted.

To assess the quality of annotation, we calculated the inter annotator agreement using the Parseval F-measure metric between two functionally annotated set of parses. Agreements range between 93.4 for FACEBOOK data and 97.44 for JEUXVIDEOS.COM (Table 5) and are on the same range than the DCU's Twitter corpus agreement score (Foster et al., 2011a). Similarly to that corpus, the disagreements involve fragments, interjections and the syntactic status to assign to meta-tokens elements. We note that our agreement scores are higher than those reported in other out-of-domain initiatives for French [START_REF] Candito | Le corpus sequoia : annotation syntaxique et exploitation pour l'adaptation d'analyseur par pont lexical[END_REF]. This small annotation error rate comes from the fact that the same team annotated both treebanks and was thus highly trained for that task. Maybe more importantly, social media sentences tend to be shorter than their edited counterparts so once POS tagging errors are solved, the annotation task is made relatively easier.

Preliminary experiments

Experimental Protocol In the following experiments, we used the FTB-UC as training data set, in its classical settings (test set: first 10%, dev set: next 10% and train set: the remaining.), see (Candito et al., 2009;[START_REF] Seddah | Cross parser evaluation and tagset variation: A French Treebank study[END_REF] for details.

POS tagging experiments

We have conducted preliminary evaluation experiments on the MElt POS-tagger [START_REF] Denis | Coupling an annotated corpus and a morphosyntactic lexicon for state-of-the-art pos tagging with less human effort[END_REF], used as such or within the normalization and correction wrapper described in the previous section. In

Baseline statistical parsing experiments

In addition to the POS tagging experiments which showed that performance could greatly be improved using our normalization and correction wrapper, we performed a set of baseline experiments on the raw (tokenized) corpora using the PCFG-LA parser of [START_REF] Petrov | Learning accurate, compact, and interpretable tree annotation[END_REF] adapted to handle French morphology by [START_REF] Crabbé | Expériences d'analyse syntaxique statistique du français[END_REF]. We used the PARSEVAL metrics applied to all sentences. Note that full scale experiments aimed at getting optimum parsing performance on this data set are out of the scope of this paper. We instead insist on providing baseline results, setting out a lower bound which assesses the difficulty of French User generated content parsing. As expected, the results 17 provided in Table 7 show that there exists a large room for improvements. Interestingly, our user generated content data set seems even more difficult to parse than French biomedical data (67.79% vs 81.25% of F 1 score, on the Emea French test set for sentences of length lesser than 41), known to contain a high amount of unknown words and unusual phrase structures [START_REF] Candito | A word clustering approach to domain adaptation: Effective parsing of biomedical texts[END_REF]. Surprisingly, our parser performs poorly on FACEBOOK data, more than it does on TWITTER. In order to test their similarity, we can compare the respective noisiness scores of their subcorpora (FACEBOOK with respect to TWITTER = 1.42, TWITTER with respect to FACEBOOK 0.85). This shows that TWITTER data are more homogeneous than their FACEBOOK counterparts. Part of the reason lies in the inner nature of those social media: TWITTER is a live micro blogging platform, meaning that the content for a given trending topic shows fewer lexical divergences in a very short amount of time, whereas FACEBOOK public post are more distributed over time and posters.

The next step will involve collecting large unlabeled corpora to perform experiments with selftraining techniques [START_REF] Mcclosky | Self-training for biomedical parsing[END_REF][START_REF] Foster | From news to comment: Resources and benchmarks for parsing the language of web 2.0[END_REF] and unsupervised Table 7: Baseline parsing results split by sub corpora and noisiness level word clustering within a PCFG-LA framework. Indeed, we have successfully applied these techniques for French out-of-domain parsing [START_REF] Candito | A word clustering approach to domain adaptation: Effective parsing of biomedical texts[END_REF], as well as for parsing noisy English web data [START_REF] Seddah | The Alpage Architecture at the SANCL 2012 Shared Task: Robust Preprocessing and Lexical bridging for user-generated content parsing[END_REF]. On the longer term we intend to apply our normalization and correction module before parsing. The parser will then be provided with corrected tokens, closely matching our regular training data, instead of unedited ones. This will compensate the lack of user generated content large unlabeled corpora, still lacking for French.

Conclusion

As mentioned earlier, the French Social Media Bank shares with the Google web bank a common will to extend the traditional treebank domain towards user generated content. Although of a smaller scale, it constitutes one of the very first usable resources to validate social media parsing and POS tagging, among the DCU TWITTER and football BBC forums treebank (Foster et al., 2011a,b) and the TWITTER data set from [START_REF] Gimpel | Part-of-speech tagging for twitter: Annotation, features, and experiments[END_REF]. Moreover, it is the first set of syntactically annotated data for FACEBOOK public web text.

Regarding the Google web bank, the way annotation guidelines had to be extended to deal with user generated content is largely consistent between both treebanks. However, our treebank differs from the Google Web Treebank in several aspects. First, French not only has a morphology richer than English, entailing a tedious disambiguation process when facing noisy data. Although the first version of our treebank is smaller than the Google Web Treebank, it includes richer annotations (compound POS, corrected token form of contractions) and includes subcorpora exhibiting a very high level of noise.

To conclude, we presented a new data set devoted on French user generated content. We proposed a first round of evaluation showing that simple techniques could be used to improve POS tagging performance. We presented baseline statistical parsing results, showing that performance on French user generated data were lying far behind those on newspaper in-domain texts. The take home message is that despite what is commonly said, parsing and POS tagging are far from being solved and that working on real text from real users is of crucial importance.

  ) a. Ces pas possible déjà que battelfield a un passe online Ce n'est pas possible, Battlefield a déjà un pass en ligne It's not possible, Battlefield already has an online pass b. Si y'a que Juliet &Zayn qui sont co' sur le RPG,et qui font leur vie tranquilles Si, il n'y a que Juliet et Zayn qui sont connectés sur le jeux de rôle et qui font leur vie tranquilles Only Juliet and Zayn are connected on the RPG and are quiet doing their own business

Table 1 :

 1 Table 1 presents some properties of our main corpora. Corpus properties

		# sent.	# tokens	avg. Length	std dev.
	DOCTISSIMO	771	10834	14.05	10.28
	high noisiness subcorpora	36	640	17.78	17.63
	other subcorpora	735	10194	13.87	9.74
	JEUXVIDEOS.COM	199	3058	15.37	14.44
	TWITTER	216	2465	11.41	7.81
	high noisiness subcorpora	93	1126	12.11	8.51
	other subcorpora	123	1339	10.89	7.20
	FACEBOOK	452	4200	9.29	8.17
	high noisiness subcorpora	120	1012	8.43	7.12
	other subcorpora	332	3188	9.60	8.49

Table 2 :

 2 Noisiness scores computed on tokenized version of the various sub-corpora. The (tokenized) FTB training set is used as a reference.

Table 3 :

 3 Non-standard compound tags occurring at least 3 times. example, which stands for the coordination conjunct c'est-à-dire, the first two tokens is tagged Y and dire is tagged CC. Note that this is consistent with the way such cases are annotated in the Google Web Treebank.15

Table 4 :

 4 Gold and automatic correction and POS tags for the following sentence extracted from the DOCTISSIMO file with the highest noisiness score 'Forplay have disappeared for at least 6 months, that is there is almost none.'

Table 5 :

 5 Inter Annotator agreement

	DOCTISSIMO 95.05	JEUXVIDEOS.COM 97.44
	TWITTER	95.40	FACEBOOK	93.40
	DCU'S TWITTERBANK	95.8	-	-

Table 6

 6 One can note that our accuracy results on standard TWITTER subcorpora are similar to the figures reported byFoster et al. (2011a) on English TWITTER data, although these figures are obviously not directly comparable, as they concern different languages using different tagsets. Another interesting observation is that these accuracy results are correlated with the noisiness metrics defined above.16

			DEV	TEST
		MElt-corr	MElt+corr	MElt-corr	MElt+corr
	DOCTISSIMO
	high noisiness subc.	56.41	80.78	-	-
	other subcorpora	86.57	88.42	87.78	89.18
	JEUXVIDEOS.COM	81.20	82.41	82.64	83.63
	TWITTER
	high noisiness subc.	80.21	84.51	74.50	81.65
	other subcorpora	84.09	89.00	86.23	88.24
	FACEBOOK
	high noisiness subc.	-	-	67.00	70.75
	other subcorpora	71.75	76.87	78.66	82.00
	all	80.64	84.72	83.10	85.28
	FTB (edited Text)	97.42	97.42	97.79	97.78

, we provide POS-tagging accuracy results over the various subcorpora, following the DEV/TEST split described above. The results indicate that using the normalization and correction wrapper leads to significant improve-ments in POS tagging accuracy.

Table 6 :

 6 Accuracy results for the MElt POS-tagger, embedded or not within the normalization and correction wrapper ("MElt+corr" and "MElt-corr" respectively). See text for details.

Cf. (McClosky et al.,

2010) for numerous evidences of the non-triviality of that task.

http://facebook.fr, https://twitter.com (automatically configured to provide French tweets first based on IP address geo-localization), http://forum.doctissimo.fr/ and http://www.jeuxvideo.com/

Collected on November

9, 2011.9 An incident involving the left-wing candidate to the French presidency election, a so-called French hidden son of Adolf Hitler, and the then new right-wing election motto.

The translation is most certainly not accurate as even the original text is barely understandable for us.

As in J'ia instead of J'ai/'I have'. e.g., Dévelloppement instead of développement/development e.g., "-ent" instead of "-ant"/ing, which are pronounced the same.

For instance pays industrialisés (industrialized countries) appears twice as a compound and 41 times as two words; taux d'intérêt (interest rate) appears 80 times as a compound and 25 times as two words.

In the Google Web Treebank, the counterpart of our tag Y is the tag GW.

Simple linear regressions lead to the following results: without the normalization and correction wrapper, the slope is -4.8 and the correlation coefficient is 0.77; with the wrapper, the slope is -7.2 with a correlation coefficient as high as 0.88 (coefficients of determination are thus respectively 0.59 and 0.77).

Acknowledgments

We thank the reviewers for their insightful comments and Yoav Goldberg, Reut Tsarfaty and Jennifer Foster for their remarks on an earlier version of this work. This work was partly funded by the French ANR project EDyLex (ANR-09-CORD-008).