Dana Lahat

Christian Jutten

JOINT ANALYSIS OF MULTIPLE DATASETS BY CROSS-CUMULANT TENSOR (BLOCK) DIAGONALIZATION †

Keywords: Independent vector analysis, tensor diagonalization, blind source separation, coupled decompositions, data fusion

In this paper, we propose approximate diagonalization of a crosscumulant tensor as a means to achieve independent component analysis (ICA) in several linked datasets. This approach generalizes existing cumulant-based independent vector analysis (IVA). It leads to uniqueness, identifiability and resilience to noise that exceed those in the literature, in certain scenarios. The proposed method can achieve blind identification of underdetermined mixtures when single-dataset cumulant-based methods that use the same order of statistics fall short. In addition, it is possible to analyse more than two datasets in a single tensor factorization. The proposed approach readily extends to independent subspace analysis (ISA), by tensor block-diagonalization. The proposed approach can be used as-is or as an ingredient in various data fusion frameworks, using coupled decompositions. The core idea can be used to generalize existing ICA methods from one dataset to an ensemble.

INTRODUCTION

In this paper, we propose a cumulant-based approach for the joint analysis of an ensemble of datasets that admit the independent vector analysis (IVA) [START_REF] Kim | Independent vector analysis: An extension of ICA to multivariate components[END_REF] model. IVA is a framework that addresses an ensemble of independent component analysis (ICA) [START_REF] Comon | Independent component analysis[END_REF] problems by exploiting not only the statistical independence within each dataset but also dependence among latent sources in different datasets. IVA is further explained in Section 2. An advantage of IVA over analysing each dataset individually is that it aligns the estimated sources in all datasets with the same (arbitrary) permutation, thus obviating the need to resolve the individual arbitrary permutation in each mixture separately. In addition, IVA can generally separate mixtures of Gaussian real stationary sources with spectra identical up to a scaling factor, a problem that does not have a unique solution when each mixture is treated individually. In this paper, we add to the list of useful properties of IVA (i) better resilience to certain types of noise, and (ii) enhanced uniqueness and identifiability in the presence of underdetermined mixtures, for non-Gaussian data.

Most IVA-type methods use cross-correlations, i.e., secondorder cross-cumulants, e.g., [START_REF] Hotelling | Relations between two sets of variates[END_REF][START_REF] Kettenring | Canonical analysis of several sets of variables[END_REF][START_REF] Li | Joint blind source separation by multiset canonical correlation analysis[END_REF][START_REF] Anderson | Joint blind source separation with multivariate Gaussian model: Algorithms and performance analysis[END_REF], or a multivariate contrast with a nonlinear function, e.g., [START_REF] Kim | Independent vector analysis: An extension of ICA to multivariate components[END_REF][START_REF] Anderson | Independent vector analysis, the Kotz distribution, and performance bounds[END_REF]. The idea to explicitly use crosscumulants of higher-order statistics (HOS) for IVA first appeared in [START_REF] Li | Second and higher-order correlation analysis of multiple multidimensional variables by joint diagonalization[END_REF][START_REF] Li | Joint blind source separation by generalized joint diagonalization of cumulant matrices[END_REF]. Their idea is to jointly diagonalize slices of cross-cumulant tensors, where each cross-cumulant involves a pair of datasets. In order to jointly process several sets of (cross) cumulants, the factorizations are coupled in a specific way that was termed generalized joint diagonalization (GJD). IVA via GJD can be applied to secondorder statistics (SOS) and up. When fourth-order statistics are used, GJD can be regarded as a multiset counterpart of joint approximate diagonalisation of eigen-matrices (JADE) [START_REF] Cardoso | Blind beamforming for non-Gaussian signals[END_REF]. The GJD analytical framework in [START_REF] Li | Joint blind source separation by generalized joint diagonalization of cumulant matrices[END_REF] is prewhitening-based and not designed to deal with underdetermined scenarios. When introducing GJD, Li et al. [START_REF] Li | Joint blind source separation by generalized joint diagonalization of cumulant matrices[END_REF] mention that in principle, one may use cross-cumulants taken from more than two datasets. However, they proceed only with pairs of cross-cumulants, explaining that groups of more than two contribute less to the separation than slices involving variables from only two datasets, due to noise and finite sample size. In this paper, we explain, in Section 2, how cross-cumulants that involve K ≥ 2 different datasets can achieve enhanced resilience to noise. We show how methods based on cross-cumulants enjoy uniqueness and identifiability that exceed those of single-dataset cumulant-based methods that use the same order of statistics. Finally, our approach allows to analyse more than two datasets in a single tensor factorization, as opposed to GJD. For SOS, i.e., K = 2, GJD coincides with our approach. For K ≥ 3, our approach is, naturally, not suitable for Gaussian data.

In the following, we denote scalars, vectors, matrices and higher-order arrays (tensors) by a, a, A and A, respectively. The nth column and (m, n)th entry of A are denoted by an and am,n, respectively. (•) and • denote transpose and the Frobenius norm, respectively. The mode-n product ×n between [START_REF] Lathauwer | Blind source separation by higher-order singular value decomposition[END_REF]Definition 4]. The outer product of

C ∈ R I 1 ו••×I N and A ∈ R Jn×In yields an I1 × • • • × In-1 × Jn × In+1 • • • × IN array whose entries are given by [C ×n A]i 1 ,...,i n-1 ,jn,i n+1 ,...,i N = In in=1 ci 1 ,...,in,...,i N aj n ,in
N non-zero vectors an ∈ R In×1 is a rank-1 I1ו • •×IN tensor C = a1 • • • • • aN whose entries are given by ci 1 ,...,i N = a1,i 1 • • • aN,i N .

MODEL AND PROBLEM FORMULATION

Consider K datasets, each admitting an ICA model,

x [k] (t) = A [k] s [k] (t) + n [k] (t) 1 ≤ t ≤ T , 1 ≤ k ≤ K (1)
where

A [k] ∈ K I [k] ×R , x [k] (t) ∈ K I [k] ×1 and s [k] (t) ∈ K R×1
represent a mixing matrix, observations and latent sources, respectively, whose elements are real or complex, K ∈ {C, R}. The elements of s [k] (t) are sampled from random vectors that follow the IVA model. IVA is a generalization of ICA to multiple datasets in which the K elements of random vector sr = [s [START_REF] Kim | Independent vector analysis: An extension of ICA to multivariate components[END_REF] r , . . . , s

[K]
r ] , r = 1, . . . , R, are statistically dependent whereas the pairs (sr, s r ) are statistically independent for any r = r . The noise random processes n [k] ∈ K I [k] ×1 are mutually statistically independent for any k = k , as well as statistically independent of all sources.

A [1] A [2] A [3] cum(s [1] , s [2] , s [3] ) cum(x [1] , x [2] , x [3] ) Fig. 1: Diagonalization of a third-order cross-cumulant tensor. In this example, K = 3 and R = 4.

Given a set of observations X = {x [k] (t)} K ,T k=1,t=1 , the goal of IVA is to separate the sources and/or identify the mixtures by exploiting not only the statistical independence within each set of measurements but also the dependence among sets of measurements. Whenever A [k] is full column rank, the corresponding samples s [k] (t) may be estimated by multiplying x [k] (t) with a left inverse of an estimate of A [k] . Otherwise, the samples cannot be estimated without resorting to additional assumptions (e.g., [START_REF] Comon | Handbook of Blind Source Separation: Independent Component Analysis and Applications[END_REF]Chapter 9.2.1]). The latter often occurs when I [k] < R, i.e., underdetermined. In this case, one has to suffice with "blind identification", i.e., estimating only A [k] . In this paper, we propose to achieve these inferences by factorizing a cross-cumulant tensor, as we now explain.

For K ≥ 2, the Kth-order I [1]

× • • • × I [K] cross-cumulant of X is given by C K X = cum(x [1] , . . . , x [K] ) = C K S ×1 A [1] ×2 A [2] × • • • ×K A [K] (2)
(holds for K = 1 if the noise has zero mean) where the Kth-order R × • • • × R cross-cumulant C K S = cum(s [1] , . . . , s [K] ) is diagonal. A key assumption is that the main-diagonal elements do not vanish. The right-hand side (RHS) of ( 2) is due to the linearity property of cumulants (e.g., [START_REF] Brillinger | Time Series, Data Analysis and Theory[END_REF]Chapter 2]). The noise term vanishes from the cross-cumulants, even for K = 2, due to its statistical independence properties. We conclude that approximating a sample cross-cumulant of X with the model in (2) yields estimates of all factors A = {A [k] } K k=1 , with the added benefit of (asymptotically) getting rid of the noise at no additional computational cost. Figure 1 illustrates this idea.

Implications

Equation ( 2) can be rewritten as

C K X = R r=1 c K sr a [1] r • a [2] r • • • • • a [K] r (3)
where c K sr denotes the Kth-order cumulant of s

[1] r , . . . , s [K] r , c K sr = cum(s [1] r , . . . , s [K] r ). Equation (3) rewrites C K
X as a sum of R rank-1 terms, where the rth summand represents the contribution of the rth source in all K datasets. For the smallest R for which (3) holds exactly, this factorization amounts to canonical polyadic decomposition (CPD) [START_REF] Hitchcock | The expression of a tensor or a polyadic as a sum of products[END_REF][START_REF] Carroll | Analysis of individual differences in multidimensional scaling via an N -way generalization of "Eckart-Young" decomposition[END_REF]/parallel factor analysis (PARAFAC) [START_REF] Harshman | Foundations of the PARAFAC procedure: models and conditions for an "explanatory" multimodal factor analysis[END_REF]. This fact has the following implications.

Uniqueness: CPD is generically unique under mild conditions (e.g., [START_REF]Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics[END_REF][START_REF] Sidiropoulos | On the uniqueness of multilinear decomposition of N -way arrays[END_REF]). Hence, the proposed approach is naturally suitable for underdetermined ICA. Furthermore, the ensemble may admit a unique decomposition even if some of the underdetermined ICA are not identifiable individually with the same order of statistics. We point out that the cumulant-based GJD framework has a similar uniqueness property. The idea that coupled decompositions can provide uniqueness of the ensemble even when each dataset is not individually unique has already been proved in certain types of coupled tensor decompositions [START_REF] Sørensen | Coupled canonical polyadic decompositions and (coupled) decompositions in multilinear rank-(Lr,n, Lr,n, 1) terms-part I: Uniqueness[END_REF] and SOS-based IVA [START_REF] Vía | Joint blind source separation from second-order statistics: Necessary and sufficient identifiability conditions[END_REF]. Hence, the proposed approach is another demonstration of the enhanced uniqueness capacities of coupled decompositions.

Computation: Basically, we may optimize ( 2) and ( 3) with any general-purpose algorithm that approximates a Kth-order tensor with a sum of R rank-1 terms. A similar observation has previously been made with respect to (w.r.t.) underdetermined ICA [START_REF] Comon | Handbook of Blind Source Separation: Independent Component Analysis and Applications[END_REF]Chapter 9.4.3]. For a discussion of various aspects of CPD optimization for source separation, see, e.g., [START_REF] Comon | Handbook of Blind Source Separation: Independent Component Analysis and Applications[END_REF]Chapter 9.4.3] and references therein. Dedicated tensor diagonalization algorithms such as [START_REF] Sørensen | Approximate tensor diagonalization by invertible transforms[END_REF][START_REF] Tichavský | Non-orthogonal tensor diagonalization, a tool for block tensor decompositions[END_REF][START_REF] Liu | Non-orthogonal tensor diagonalization based on successive rotations and LU decomposition[END_REF] may also be used, whenever the data admits their model assumptions. Constraints such as orthogonality may be imposed as well, e.g., [START_REF] Sørensen | Canonical polyadic decomposition with a columnwise orthonormal factor matrix[END_REF]. Since (2) amounts to a Tucker [START_REF] Tucker | Contributions to Mathematical Psychology[END_REF] format with a diagonal core, then, in principle, one may use any general-purpose Tucker decomposition algorithm for the optimization. However, uniqueness issues inherent to Tucker-type decompositions may result in difficulty attributing factors to specific sources and hence, weaker interpretability.

Generalization to Multidimensional Components

Until now, we discussed only ICA and rank-1 components. However, all previous results are readily generalizable to rank-L

[k]
r ≥ 1 (this variant of IVA is sometimes termed joint independent subspace analysis (JISA) [START_REF] Lahat | Joint independent subspace analysis using second-order statistics[END_REF][START_REF] Silva | Multidataset independent subspace analysis extends independent vector analysis[END_REF]) by replacing the diagonal structure of the tensor with block-diagonal. For example, in the third-order case in Figure 1, the rth block on the diagonal now stands for an

L [1] r × L [2] r × L [3] r cube instead of a 1 × 1 × 1 scalar. The correspond- ing factorization is "decomposition in rank-(L [1] r , L [2] r , . . . , L [K] r )
terms" [START_REF] Lathauwer | Decompositions of a higher-order tensor in block terms. Part II: Definitions and uniqueness[END_REF]. Apart from the block term decomposition (BTD) algorithms in, e.g., [START_REF] Lathauwer | Decompositions of a higherorder tensor in block terms. Part III: Alternating least squares algorithms[END_REF][START_REF] Sorber | Tensorlab v2.0[END_REF], it has been proposed to use tensor diagonalization to uncover the underlying block structure [START_REF] Tichavský | Non-orthogonal tensor diagonalization, a tool for block tensor decompositions[END_REF][START_REF] Liu | Non-orthogonal tensor diagonalization based on successive rotations and LU decomposition[END_REF].

A concluding remark is in order. Whereas ICA has numerous cumulant-based methods, with independent subspace analysis (ISA) the situation is quite different. The first cumulant-based approach to ISA is [START_REF] Lathauwer | Fetal electrocardiogram extraction by source subspace separation[END_REF], which proposes to "partially diagonalize" a fourth-order cumulant tensor. A subspace variant of JADE is proposed in [START_REF] Theis | Towards a general independent subspace analysis[END_REF]. Tichavský et al. [START_REF] Tichavský | Non-orthogonal tensor diagonalization, a tool for block tensor decompositions[END_REF] mention that tensor block-diagonalization can be applied to cumulant-based ISA; however, they do not develop further this idea.

NUMERICAL VALIDATION

In this section, we illustrate by numerical examples the capability of the proposed approach to separate sources and identify mixtures in well-posed and underdetermined scenarios.

Figure of Merit

Whenever A [k] has full column rank, we are interested in the quality of separation of x [k]

(t) = R r=1 x [k] r (t) into R unique rank-1 ele- ments x [k] r (t) = a [k] r s [k]
r (t). The latter are obtained from the obser-vations using x r ), r = r, and can be computed directly from

A [k] [33]. Similarly, x [k] r (t) = P [k] r x [k] (t), via A [k]
, for their estimated counterparts. We choose to quantify the quality of separation using the normalized empirical mean square error (MSE)

MSE [k] r = T t=1 x [k] r (t) -x [k] r (t) 2 / T t=1 x [k] r (t) 2 (4)
The use of scale-invariant projections obviates the need to normalize the source samples in order to find an optimal match with the original samples, in the performance analysis stage. Another motivation is that scale-invariant projections are the natural way to deal with terms of rank larger than one [START_REF] Cardoso | Multidimensional independent component analysis[END_REF], see Section 2.2; scale-dependent objects require normalization, which is not well-defined.

In the underdetermined case, when the sources cannot be separated, we quantify the quality of blind identification, i.e., estimation of each factor A [k] , using the relative error, defined as

RelErr [k] = A [k] -A [k] A [k] (5)
In order to correct the arbitrary permutation and scaling within each estimate A [k] , we use Tensorlab [START_REF] Sorber | Tensorlab v2.0[END_REF]'s function cpderr.

Experimental Setup

We compare our approach with two cumulant-based algorithms, JADE [START_REF] Cardoso | Blind beamforming for non-Gaussian signals[END_REF] and GJD [START_REF] Li | Joint blind source separation by generalized joint diagonalization of cumulant matrices[END_REF], both are prewhitening-based. We test our proposed cross-cumulant diagonalization approach in two scenarios.

In the first, the factors are unconstrained. In the second, full column rank factors are constrained to be orthogonal (there is no added value in orthogonality in underdetermined mixtures [START_REF] Lathauwer | Simultaneous matrix diagonalization: the overcomplete case[END_REF]). Both scenarios were implemented using CPD-based algorithms, which were applied to the same whitened samples as the other algorithms. This experimental setup allows us to compare the prewhitening-based algorithms, as well as obtain some further insights about the potential of the CPD for this task.

In order to compute the normalized empirical MSE (4) we first have to align the estimated components w.r.t. their true values. As explained in Section 1, for GJD and our proposed approach, only the arbitrary permutation of the R rank-1 elements needs to be found. For JADE, however, we must find this permutation individually for each dataset. A wrong permutation results in significantly higher MSE. In the following examples, since only K = 4 datasets are involved, we detect this permutation by simple enumeration on all 4 or 4! combinations and picking up the best.

Since JADE uses fourth-order cumulants, our experimental setup involves K = 4 datasets. Each dataset consists of R = 3 sources and T = 2 • 103 sampling points. The entries of A [k] are drawn independently from the standard normal distribution. We generate non-Gaussian samples that follow the IVA model by defining, for each r, two unit-variance independent symmetric Gaussian mixture (GM) processes with peaks centred at ±4/ √ 17, and then combining them using α [START_REF] Kim | Independent vector analysis: An extension of ICA to multivariate components[END_REF], which is drawn independently at each sample: s

[k] r ∼ U [0,
[k] r = α [k] r g1,r + (1 -α [k]
r )g2,r, where g1,r, g2,r ∼ GM. The resulting overall random process is normalized to unit variance. In the following numerical experiments, A [k] are drawn once and kept fixed throughout M C = 200 Monte Carlo (MC) trials, in which source samples are drawn anew. We

r is given at component index [r + (k -1)R].
do not apply additive noise, so estimation error is only due to finite sample size. For JADE and GJD, we use online-available code1 with options "N2" and "whole" for GJD. For CPD, we use a Tensorlab [START_REF] Sorber | Tensorlab v2.0[END_REF] implementation with TolFun= 10 -12 , TolX= 10 -12 . The unconstrained CPD is optimized using cpd_nls, where, for each MC trial, we take the best out of 25 random initializations. CPD with orthogonal factors is optimized using sdf_minf via struct_orth, where the factors are initialized with random values (only once per trial). 1st experiment: Source separation in invertible mixtures. In a first step, we validate proper functionality of our proposed approach in a basic setup of invertible A [k] ∈ R R×R ∀k. Figure 2 depicts the normalized empirical MSE in the estimation of each component. For each pair (k, r), we removed trials for which at least one type of algorithm did not achieve separation 2 . In this experiment, two trials, which corresponds to component #7 in Figure 2, were removed due to large error in unconstrained CPD.

2nd experiment: blind identification. In a second step, we present the capability of the proposed method to achieve blind identification of underdetermined mixtures. Consider the case of

A [k] ∈ R 2×3 , k = 1, 2, 3
. By straightforward counting of degrees of freedom, one can verify that ICA with R = 3 sources and I [k] = 2 detectors is generally not unique and not identifiable if one exploits only statistics up to order four and all data is in the real domain (e.g., [START_REF] Comon | Tensor diagonalization, a useful tool in signal processing[END_REF][START_REF] Lathauwer | ICA algorithms for 3 sources and 2 sensors[END_REF]). With our approach, however, this is possible. We guarantee the uniqueness of the CPD of our fourth-order cross-cumulant tensor by setting A [4] ∈ R 3×3 [START_REF] Sidiropoulos | On the uniqueness of multilinear decomposition of N -way arrays[END_REF]. Hence, this experiment consists of three underdetermined ICA that cannot be identified by any fourth-order method and one ICA that can be solved by ordinary JADE 3 . The GJD algorithm [START_REF] Li | Joint blind source separation by generalized joint diagonalization of cumulant matrices[END_REF] is not suitable for datasets with underdetermined mixtures and is thus excluded from this experiment. JADE can be applied only to the fourth dataset. The relative error [START_REF] Li | Joint blind source separation by multiset canonical correlation analysis[END_REF] for all K = 4 factors using CPD is depicted in Figure 3. The normalized empirical MSE in the estimation of all rank-1 components in the 4th dataset using JADE and CPD is given in Figure 4. ,3] ∈ R 2×3 . A [4] ∈ R 3×3 . Here, we depict the MSE only for k = 4.

Discussion of Numerical Results

The small values of MSE and relative error in Figures 2, 3 and4 imply successful separation and blind identification. JADE is the algorithm that makes an overall most efficient use of the fourth-order statistics within each dataset and indeed, it achieves the best MSE. The fact that GJD performs worse than JADE deserves to be further looked into. We point out that [START_REF] Li | Second and higher-order correlation analysis of multiple multidimensional variables by joint diagonalization[END_REF][START_REF] Li | Joint blind source separation by generalized joint diagonalization of cumulant matrices[END_REF] did not compare with JADE. Orthogonally-constrained CPD consistently performs better than the unconstrained CPD, and pretty close to GJD. Given that CPD uses less statistical information than GJD, this is an encouraging indication to the usefulness of the proposed approach. The rather poor performance of unconstrained CPD cannot be explained just by the difference between non-orthogonal vs. prewhitening-based methods. In fact, when testing unconstrained CPD on non-prewhitened samples, its performance was even worse. A possible explanation may be the larger number of variables to estimate in unconstrained factors, compared with fewer ones when orthogonality is imposed. In addition, the cost function of CPD is different than directly minimizing off-diagonal values, a matter than may be more significant in large sample perturbation. Other algorithms (Section 2.1) may perform better. Therefore, although unconstrained CPD achieves the smallest residual error in estimating the original cumulant tensor, it may not be the best candidate for our approach compared with other tensor diagonalization methods. This matter deserves to be further looked into. The fact that orthogonality constraints are void in the underdetermined scenario explains why the relative error is similar for both of CPD in the first three factors in Figure 3. The performance of the proposed approach may be enhanced by coupling with SOS [START_REF] Cardoso | Blind beamforming for non-Gaussian signals[END_REF]Sec. 4.2] or with other (cross-) cumulants that carry complementary information. It is interesting to observe where the trade-off between different types of combinations of statistics is, both in terms of error and in computational cost.

The overall conclusion from these experiments is that our paradigm is correct, and that our cross-cumulant tensor diagonalization approach indeed successfully exploits statistical links among datasets to achieve blind identification of underdetermined mixtures even in "adverse" scenarios, when the order of statistics is limited and individual ICA is impossible. However, for more conclusive statements about the usefulness of our proposed approach w.r.t. state of the art, these preliminary numerical results serve only as a proof of concept, and require further theoretical and experimental support.

CONCLUSION

In this paper, we have shown that factorizing a cross-cumulant tensor of several datasets can achieve simultaneous ICA of all involved mixtures, if certain conditions hold. We explained how cumulant-based IVA may achieve uniqueness of the ensemble that exceeds that of individual underlying datasets, extending previous results on SOS-IVA. We have shown analytically that using crosscumulants provides, asymptotically, resilience to dataset-specific noise. The proposed approach relies directly on the strong uniqueness of CPD/BTD. Even stronger uniqueness, identifiability and interpretability may be achieved by coupling several arrays, adding types of diversity (e.g., nonstationarity), various assumptions and constraints within and among datasets. The proposed approach motivates multiset variants of tensor-based ICA methods such as JADE, its higher-order generalizations [START_REF] Lathauwer | Independent component analysis and (simultaneous) third-order tensor diagonalization[END_REF][START_REF] Moreau | A generalization of joint-diagonalization criteria for source separation[END_REF], or methods based on the characteristic function [START_REF] Comon | Blind identification of underdetermined mixtures based on the characteristic function[END_REF] to use this cross-cumulant concept to achieve stronger uniqueness.

  r x[k] (t), where the rank-1I [k] ×I [k] matrices P [k]r are oblique projections onto span(a [k] r ) orthogonally to all span(a [k]

Fig. 2 :

 2 Fig. 2: Normalized MSE in ICA of K = 4 datasets using fourthorder statistics. In each dataset, A [k] ∈ R 3×3 and R = 3 sources. Error bars denote empirical standard deviation. The MSE of component x [k]

Fig. 3 :Fig. 4 :

 34 Fig.3: Relative error in estimating A[k] in K = 4 datasets, each with R = 3 sources. A [k=1,2,3] ∈ R 2×3 . A[4] ∈ R 3×3 . Error bars denote empirical standard deviation.

http://perso.telecom-paristech.fr/∼cardoso/Algo/Jade/jadeR.m, http://mlsp.umbc.edu/codes/jbss cum4.m

With certain draws of A[k] , both orthogonal and unconstrained CPD did often not converge to a desired solution, regardless of initialization. This matter deserves to be further looked into. For the examples in this paper, only data with no estimation issues were selected.

In fact, stronger uniqueness is generally possible. For example, there are enough degrees of freedom already at two underdetermined mixtures and fourth-order statistics. In addition, a mixing matrix that can be estimated individually may be regarded as a known factor in the ensemble.

This work is supported by the project CHESS, 2012-ERC-AdG-320684. GIPSA-Lab is a partner of the LabEx PERSYVAL-Lab (ANR-11-LABX-0025).

† This is very close to the official version, published in Proc. SAM 2016.


Quang -Vinh Dang
email: quang-vinh.dang@inria.fr

Claudia -Lavinia Ignat

Quality Assessment of Wikipedia Articles without Feature Engineering

Keywords: quality assessment, Wikipedia, feature engineering, document representation, deep learning

As Wikipedia became the largest human knowledge repository, quality measurement of its articles received a lot of attention during the last decade. Most research efforts focused on classification of Wikipedia articles quality by using a different feature set. However, so far, no "golden feature set" was proposed. In this paper, we present a novel approach for classifying Wikipedia articles by analysing their content rather than by considering a feature set. Our approach uses recent techniques in natural language processing and deep learning, and achieved a comparable result with the state-of-the-art.

INTRODUCTION

Internet has opened the border of traditional libraries: nowadays everyone can participate and contribute to a common human knowledge repository. Wikipedia is a great example of a knowledge resource receiving contribution from a huge number of authors. At the time of writing, there are more than five millions articles in English Wikipedia, and 38 million articles in all languages 1 , and the size of English Wikipedia is over 60 times compared with Britannica 2 .

However, due to the huge number of contributors 3 and articles, the quality of Wikipedia articles is not equally distributed [START_REF] Warncke-Wang | The success and failure of quality improvement projects in peer production communities[END_REF]. Several research works claimed that the quality of centralized human knowledge resources such as books or Britannica are higher than Wikipedia [START_REF] Dondio | Extracting trust from domain analysis: A case study on the Wikipedia project[END_REF][START_REF] Rector | Comparison of Wikipedia and other encyclopedias for accuracy, breadth, and depth in historical articles[END_REF].

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. In order to improve the quality of Wikipedia, an effective method is needed for quality assessment of its articles. Wikipedia defines quality classes for its articles, including FA, A, GA, B, C, Start, Stub where FA is the highest quality class and Stub the lowest quality class 4 .

JCDL '

Assigning the correct quality class for each Wikipedia article is an important task, as authors and reviewers can be notified to pay more attention for improving the low quality articles, and search engines could promote high quality class articles as query result. However, the high velocity of changes on Wikipedia makes impossible a manual quality assessment of articles by human experts. Therefore, it is important to design an automatic approach for quality assessment of Wikipedia articles.

Existing approaches on this topic [START_REF] Blumenstock | Size matters: word count as a measure of quality on Wikipedia[END_REF][START_REF] De La Robertie | Measuring article quality in Wikipedia using the collaboration network[END_REF][START_REF] Hasan Dalip | Automatic quality assessment of content created collaboratively by web communities: a case study of Wikipedia[END_REF][START_REF] Hu | Measuring article quality in Wikipedia: models and evaluation[END_REF][START_REF] Suzuki | Quality assessment of Wikipedia articles using h-index[END_REF][START_REF] Warncke-Wang | The success and failure of quality improvement projects in peer production communities[END_REF][START_REF] Wu | Classifying Wikipedia articles using network motif counts and ratios[END_REF]] are all based on defining a feature set that is believed to describe in the best way the quality of a Wikipedia article. Certain approaches claim that longer articles are of a better quality, some others consider that discussions and interactions among authors and reviewers of an article increase the quality of an article and others consider that the quality of an article is determined by contributions of highly respected authors.

There is no standard rule for selecting features, which is considered as one of the most difficult tasks in machine learning. Moreover, feature selection is language dependent. In this paper, we present a new approach that avoids feature engineering and that determines the quality of an article based on its content. We build a deep neural network model where the input is the full content of the Wikipedia articles, and the output is the quality class of the articles. The same approach can be defined for different language data sets.

We start by presenting related works in quality assessment of Wikipedia articles. We then present our classification model including article representation and the deep neural networks technique that we used for the classification. We then describe the evaluation we performed and we compare our results with state-of-the-art techniques. Finally, we present our concluding remarks and we provide some directions for future work.

RELATED WORKS

Even though existing research works on automatic quality assessment of Wikipedia articles use a different feature set, they can be classified into two main families: one is analyzing the edit history of an article (for instance, who contributed to the article and the type of their modifications) and the second one is analyzing the article itself (for instance, its length, number of images, presence of an information box).

Belonging to the first family of approaches, [START_REF] Hu | Measuring article quality in Wikipedia: models and evaluation[END_REF] measures the quality of Wikipedia articles based on author authority. Using a similar idea, [START_REF] Suzuki | Quality assessment of Wikipedia articles using h-index[END_REF] applied authors' h-index to measure the quality of articles on Wikipedia. In [START_REF] Suzuki | Mutual evaluation of editors and texts for assessing quality of Wikipedia articles[END_REF], the authors used both metrics of article's content and authors' authority to measure the quality of Wikipedia articles. However, this research work used a manual evaluation by volunteering students which is not very reliable for verifying the classification. Moreover, the accuracy obtained is not very high. [START_REF] Wu | Classifying Wikipedia articles using network motif counts and ratios[END_REF] analyzed the edit network around a Wikipedia article to retrieve the information about the quality of that article. [START_REF] De La Robertie | Measuring article quality in Wikipedia using the collaboration network[END_REF] presented a model that analysed the collaboration between authors and reviewers on Wikipedia to measure the quality of articles.

On the other hand, as the most simple approach, [START_REF] Blumenstock | Size matters: word count as a measure of quality on Wikipedia[END_REF] proposed to use simple word count to evaluate the quality of Wikipedia. Dalip et al [START_REF] Hasan Dalip | Automatic quality assessment of content created collaboratively by web communities: a case study of Wikipedia[END_REF] analyzed the effect of different feature sets including structure, length, style, review, network and readability in a regression model for measuring the quality of Wikipedia articles and they discussed about a minimal feature set [START_REF] Dalip | Quality assessment of collaborative content with minimal information[END_REF]. More recently, [START_REF] Warncke-Wang | The success and failure of quality improvement projects in peer production communities[END_REF] used a machine learning model for quality prediction of Wikipedia articles including format-based features such as the number of headings of level 2 of a particular article. Based on the work of [START_REF] Warncke-Wang | The success and failure of quality improvement projects in peer production communities[END_REF][START_REF] Warncke-Wang | Tell me more: An actionable quality model for Wikipedia[END_REF], Wikimedia Foundation built an online service called ORES to classify the quality class of Wikipedia articles [START_REF] Halfaker | Artificial intelligence service gives Wikipedians 'x-ray specs' to see through bad edits[END_REF], using a set of 24 features for English Wikipedia. This set of features is slightly different for other languages Wikipedia.

Each research work selected and used a different feature set to measure and classify the quality of Wikipedia articles. However, feature selection is mostly based on the heuristic of researchers and so far, there is no "gold -standard" feature set to classify and measure the quality of Wikipedia articles.

In this paper, we claim that the quality of a Wikipedia article should depend on its own content. Certain features can be derived from the article content. Using the full content of Wikipedia articles as the input of training model should avoid missing an important feature that was not manually recognized.

We use the technique Doc2Vec [START_REF] Le | Distributed representations of sentences and documents[END_REF] to represent Wikipedia articles and a deep neural network to classify their quality. Deep learning is an emerging research field today and, to our knowledge, our work is the first one that applied deep learning for assessing quality of Wikipedia articles. Our approach provides a novel point of view to Wikipedia quality classification.

CLASSIFICATION MODEL

In this section, we present how to design and feed the content of Wikipedia articles into a neural network.

Article representation

Most machine learning algorithms including neural networks require the input to be represented as a fixed-length feature vector. As Wikipedia articles have different lengths, we need an approach that maps Wikipedia articles to fixedlength feature vectors. The most common fixed-length vector representation for documents is the bag-of-words [START_REF] Harris | Distributional structure[END_REF] where a document is represented as the bag of its words. However, this approach disregards semantics and even word order.

In this paper, we applied the unsupervised learning algorithm called Paragraph Vector, recently known as Doc2Vec [START_REF] Le | Distributed representations of sentences and documents[END_REF] that learns vector representations for variable-length pieces of texts and overcomes the disadvantages of bag-ofwords by taking into account the order and semantics of words. In this approach every word and every paragraph are mapped to a unique vector. The paragraph vector is concatenated with several word vectors from the paragraph and trained in order to predict the next word in a text window. While word vectors are shared among paragraphs, paragraph vectors are unique among paragraphs.

We applied the Doc2Vec approach where each Wikipedia document corresponds to a paragraph in the above description. While the generated word vectors are not further used, the document vector is given as input for our deep neural network.

Deep neural networks

Deep learning has been successfully applied for several text classification tasks such as Reuters news or sentiment analysis [START_REF] Lee | Predicting the helpfulness of online reviews using multilayer perceptron neural networks[END_REF].

Neural networks, or artificial neural networks (ANN), are machine learning models inspired by biological neural networks for the estimation of generally unknown functions that depend on a large number of parameters. Neural networks are typically organized in layers made up of a number of interconnected nodes which contain an activation function. Patterns are presented to the network via the input layer, which communicates to one or more hidden layers. The hidden layers perform the actual processing via a system of weighted connections. The hidden layers then transmit the answer to an output layer. A deep neural network (DNN) [START_REF] Bengio | Learning deep architectures for AI[END_REF] is defined as an artificial neural network with multiple hidden layers that allows learning abstraction from data.

In our approach, we used a DNN with four hidden layers to learn and classify the representation vectors of Wikipedia articles computed by Doc2Vec.

IMPLEMENTATION AND RESULTS

Implementation

We used the data set contained in around 30,000 English Wikipedia articles which are classified to six quality classes FA, GA, B, C, Start, Stub already by Wikipedia reviewers. The data set is provided by Wikimedia Foundations5 . We separated the data set to training and testing set with the ratio 80/20, similarly to [START_REF] Warncke-Wang | The success and failure of quality improvement projects in peer production communities[END_REF] and ORES [START_REF] Halfaker | Artificial intelligence service gives Wikipedians 'x-ray specs' to see through bad edits[END_REF].

We transformed all Wikipedia articles on both training and testing set to Doc2Vec vectors by using the library gensim 67 . The output of the first phase is the collection of vectors for Wikipedia articles in the training and testing set. Therefore, we have a dataset of 30,000 same length vectors. In the second phase, we trained the DNN model on the training set by using tensorflow 8 , the deep learning library from Google. Our DNN has four hidden layers, with 2000, 1000, 500 and 200 neurons respectively 9 . The number of neurons is selected as a rule of thumb. The final task is to apply the trained DNN model on the testing vector set, and compare the predicting quality labels with correct values assigned by human judgements.

Currently, no standard methodology exists for constructing an optimal neural network with the right number of layers and number of neurons for each layer. An optimal neural network can be built uniquely empirically [START_REF] Lewis | Build Your Own Neural Network Today[END_REF]. However, randomly choosing a structure for a deep neural network is not a good solution as it leads to performances of a random guess, i.e. a low accuracy of 16.7%.

Results

The predictions obtained by our model are displayed by the confusion matrix in Table 1. The training loss graph in Fig. 1 illustrates the training loss value, i.e. the difference between predicted quality labels and their correct values in the training set, as a function of the number of iterations during the training phase. The graph shows that no local minima is found when the number of training steps reaches a high value (25,000), as the decreasing trend is observed throughout the entire training process.

As the data set we used is balanced, i.e. the number of articles in each class is very close, the accuracy metric is suitable to evaluate the classification. Accuracy is defined as a ratio between the number of correct predictions and the total number of articles in the testing data set. The accuracy of our DNN classifier is 55%.

We compare our approach with other popular classification approaches on the same data set. Using the 24 features of ORES as the feature set, k-Nearest Neighbor (k-NN) [START_REF] Altman | An introduction to kernel and nearest-neighbor nonparametric regression[END_REF], Classification And Regression Tree (CART) [START_REF] Breiman | Classification and regression trees[END_REF] and Random Forest(RF) implemented by ORES, achieved the accuracy of 51%, 48% and 60% respectively. Using the feature set composed of 11 features presented in [START_REF] Warncke-Wang | The success and failure of quality improvement projects in peer production communities[END_REF] which is a subset of the 24 features set used in ORES, Random Forest algorithm achieved the accuracy of 58%. The performance of classifiers is summarized in Table 2.

The accuracy of DNN is higher than the one obtained by the k-NN and CART approaches. The lower accuracy of DNN classifier with respect to the RF approach can be explained by the parameter of Doc2Vec transformation. Due to our computation power, the size of the vectors was limited to 500, which may lead to the consequence that Doc2Vec vectors did not capture all the structure of the Wikipedia articles. Moreover, the low accuracy is also due to our unoptimized DNN, as no standard way exists for constructing a DNN. We can see the improvement from [START_REF] Warncke-Wang | The success and failure of quality improvement projects in peer production communities[END_REF] to ORES when more features are added.

To our knowledge, Wikimedia ORES API, which is based on the work of [START_REF] Warncke-Wang | The success and failure of quality improvement projects in peer production communities[END_REF][START_REF] Warncke-Wang | Tell me more: An actionable quality model for Wikipedia[END_REF] is the only existing approach for classification into all six quality classes. Other works only classified between a subset of classes, such as between FA and Start [START_REF] Xu | Measuring article quality in Wikipedia: Lexical clue model[END_REF] with an accuracy of 84%, or between FA-GA as a class and the set of (B, C, Start, Stub) as another class [START_REF] Lex | Measuring the quality of web content using factual information[END_REF] with an accuracy of 84%, or between FA-GA and C-Start [START_REF] Wu | Classifying Wikipedia articles using network motif counts and ratios[END_REF] with an accuracy of 66%. For these binary classification tasks, the DNN approach achieved a very high accuracy compared with previous approaches: 99% to classify We observe that the quality class of a Wikipedia article could be determined by only analyzing its content, so the approach of training the prediction model based on the content and not on feature sets is a promising and interesting approach to be improved in the future. As Doc2Vec approach is language independent we expect that our approach can be generally applied to any language Wikipedia.

CONCLUSIONS AND FUTURE WORKS

Feature selection is one of the most difficult task in machine learning. Existing research works proposed different feature sets for measuring quality of Wikipedia articles. Each feature set has its own pros and cons, and there is no "golden feature set". As feature selection process is mostly a manual work, we may never know what feature set is the best for assessing quality of Wikipedia articles.

In this paper, we presented an approach to avoid feature selection process. Our approach follows the process of Wikipedia reviewers: first they read the article and then decide what quality class this article should belong to. Using this approach, no feature selection is required to describe a Wikipedia article. We achieved very high accuracy scores for classification into binary quality classes and an accuracy score comparable with the state-of-the-art Wikimedia ORES service for classification between all quality classes.

As a future work we plan to improve performances of our approach by optimizing the deep neural network's structure.

ACKNOWLEDGMENTS

Experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific inter-

Figure 1 :

 1 Figure 1: DNN training loss

Table 1 :

 1 Confusion matrix of classifying quality classes. Gray cells are correct predictions. Rows (italic) are actual quality class. Columns are predicted values of the model. For instance, there are 778 articles correctly predicted as FA, and 160 articles which are GA and are predicted as FA.

		FA	GA	B	C Start Stub Total
	FA	778	148	64	17	6	7 1020
	GA	160	554	128	88	23	4	957
	B	87	187	373	237	143	17 1044
	C	28	112	236	376	181	23	956
	Start	6	38	119	216	453	133	965
	Stub	7	6	20	36	179	701	949
	Total 1066 1045	940	970	985 1006 5891
			Classifier	Accuracy
			CART [4]		48%
			kNN [1]		51%
			Doc2Vec & DNN		55%
		Warncke et al. [19]		58%
		Wikimedia ORES [8]		60%

Table 2 :

 2 Accuracy scores of different classifiers on English Wikipedia.

between FA and Start, 86% to classify between FA-GA and the other classes and 90% to classify between FA-GA and C-Start.

The description of each quality class is available at https: //en.wikipedia.org/wiki/Template:Grading scheme.

The data set is available at http://datasets.wikimedia.org/ public-datasets/enwiki/.

http://radimrehurek.com/gensim/

Our hypothesis is that the labeled articles in the training set and the unlabeled articles in the testing set are all completed and available.

[START_REF] Halfaker | Artificial intelligence service gives Wikipedians 'x-ray specs' to see through bad edits[END_REF] https://www.tensorflow.org

The implementation is available at https://github.com/ vinhqdang/doc2vec dnn wikipedia


Quang-Vinh Dang
email: quang-vinh.dang@inria.fr

Claudia-Lavinia Ignat

Performance of real-time collaborative editors at large scale: user perspective

Real-time collaborative editing allows multiple users to edit a shared document at the same time. It received a lot of attention from both industry and academia and gained in popularity due to the wide availability of free services such as Google Docs. While these collaborative editing systems were initially used in scenarios involving only a small set of users such as for writing a research article, nowadays we notice a change in the scale from several users to communities of users. Group note taking during lectures or conferences is an emerging practice.

An important measure of performance of real-time collaborative editing systems is delay. Delays exist between the execution of one user modification and the visibility of this modification to the other users. They can be caused by network physical communication media, complexity of consistency maintenance algorithms and system architecture. Some user studies have shown that delay affects group performance in collaborative editing. In this paper, we measure delays in popular real-time collaborative editing systems such as Google Docs and Etherpad and we study whether these systems could cope with large scale settings from a user perspective. Our results show that these systems are not yet ready for large-scale collaborative activities as either they reject new users connection or a high delay appears when facing an increasing number of users or their typing speeds in the same shared document.

I. INTRODUCTION

Today team working is a key role of success in companies or organizations. Very often members within an organisation or between different collaborating organisations are located at different geographical places and can work at different times. For an effective collaboration, team members usually need to use collaborative tools in order to overcome the geographical distance. Real-time collaborative editing systems are commonly used as they allow multiple users to edit a shared document at the same time.

Benefits of real time on-line collaborative editors are multiple. Firstly, they provide a ready-to-use platform for all users to view and modify documents on their web browsers, without installing heavy software bundle such as Microsoft Office or Libre Office. Secondly, they provide an environment where multiple users can contribute to shared documents in a fast and easy manner. While sharing documents by emails or physical mediums such as USB sticks would require to manually deal with multiple concurrent revisions and using version control systems such as git and svn would require trained users, in real-time collaborative editing merging is automatically performed without any user intervention.

Business analysis showed that new cloud collaborative editing systems such as Google Drive are taking the market share from the traditional document software provider such as Microsoft Office [START_REF] Covert | Will google docs kill off microsoft office?[END_REF]. The number of users of Google Drive service increased from 10 millions on 2012 [START_REF] Crook | Google drive now has 10 million users: Available on ios and chrome os[END_REF] to 240 millions on October 2014 [START_REF] Protalinski | Google announces 10% price cut for all compute engine instances, google drive has passed 240m active users[END_REF]. On September 2015 Google Drive announced that there are one million paying customers using their service [START_REF] Darrow | Google drive claims one million paying customers, er, organizations[END_REF].

Initially, real-time collaborative editing systems were used in scenarios involving a small number of concurrent editing users (e.g, up to ten) such as writing a research article or a brainstorming session. However, scenarios involving a large number of concurrent editing users are emerging, such as students of a class or participants in a conference that collaboratively take notes. A recent example is a MOOC (Massive Open Online Course) where the 40,000 participants were asked to access to parts of the Google Docs documents created for the course. Due to the high number of concurrent edits to the same documents, the system crashed and finally the lecture was cancelled [START_REF] Jaschik | Mooc mess[END_REF].

Various quality aspects should be taken into consideration in the design phase of large-scale collaborative editing systems. One of the important requirements of these systems is delay [START_REF] Ignat | How do user groups cope with delay in real-time collaborative note taking[END_REF], [START_REF] Vaghi | Coping with inconsistency due to network delays in collaborative virtual environments[END_REF]. Delays exist between the execution of one user's modification and the visibility of this modification to the other users. Delays can be caused by different reasons: network delay due to physical communication technology be it copper wire, optical fiber or radio transmission; complexity of various algorithms for ensuring consistency, where most of them depend on the number of users and number of operations that users performed; the type of architectures: For thin client architectures the computation for algorithms for maintaining consistency is done mainly on the server, which becomes a bottleneck in the case of a large number of users and operations, and therefore causes an increased delay for seeing operations of other users. For thick client architectures the computation is done mainly on the client side and delays are lower in this case.

In the context of collaborative editing, the delay is a critical ISBN 978-3-901882-83-8 c 2016 IFIP concern and it has a great influence on the performance and behavior of users [START_REF] Vaghi | Coping with inconsistency due to network delays in collaborative virtual environments[END_REF]. By studying users' behavior in realtime collaborative note taking with artificial added delay, Ignat et al [START_REF] Ignat | How do user groups cope with delay in real-time collaborative note taking[END_REF] claimed that "delay increases grammatical errors and redundancy, resulting in a decreased quality of the task content". However, delay has not been addressed at its desired level in the development of real-time collaborative editing systems.

In this paper, we aim at measuring the performance of realtime collaborative editing systems from users point of view. More precisely, we measure the perceived delay by users in online real-time collaborative editing systems in their normal working environment, i.e. using web browsers.

Setting up an experiment with numerous real users that edit concurrently a shared document would not be possible with current tools. Existing tools restrict the number of users editing a document and most of them are not open-source in order to allow code instrumentation for delay measurement. We instead simulated user behavior by means of agents that use popular web-based real-time collaborative editing services currently available in the market: Google Docs1 and Etherpad2 .

The paper is structured as follows. We start by describing the set-up of our experiments: how we modeled and simulated user behavior and how we measured delays. We next present the performance evaluation of Google Docs and Etherpad and discuss the results obtained. We finally provide concluding remarks.

II. EVALUATION SETTINGS A. User Behavior

We define user behavior as a set of the following actions, which can be further extended:

• Start a web browser instance (Firefox, Chrome, Internet Explorer, Safari, Edge, etc.). • Surf to the dedicated web page of a collaborative editor.

• Load a shared document.

• Perform modifications by inserting and/or deleting characters in the document. • Interact with buttons on the web page by using mouse / pointing system. • Close the web browser, since current collaborative editors automatically save user changes.

B. Simulation Settings

In order to simulate the real user behavior on web browsers, we selected Selenium [START_REF] Holmes | Automating functional tests using selenium[END_REF], which has been widely accepted in web-based testing community [START_REF] Angmo | Performance evaluation of web based automation testing tools[END_REF].

The simulation is distributed on multiple computers 3 . Three types of simulated users have been defined:

1) Writer: writes a specific string to the shared document.

2) Reader: waits and reads the specific string from the writer.

3) DummyWriter: writes random strings to the shared document. Random strings are different from the specific string. DummyWriters are used to simulate concurrent users.

Each simulator (Writer, Reader, DummyWriter) performs its task on different Google Chrome browser window. The delay is measured by the time period between the moment the specific string is written by the Writer and the moment when the specific string is read by the Reader. In order to avoid clock synchronisation issues, both Reader and Writer are executed on the same computer.

C. Experiment Settings

For each real-time collaborative editing system, i.e. Google Docs and Etherpad, we measured the performance (delay) in different settings by varying the number of users who modify the document at the same time, and their typing speed, i.e. the number of characters each user types to the document in one second.

As the number of users that can concurrently modify a document in Google Docs4 is limited to 50, we varied the number of users from one to 50. The usual range of user typing speed is 2-4 characters per second [START_REF] Soukoreff | Theoretical upper and lower bounds on typing speed using a stylus and a soft keyboard[END_REF]. We also considered that higher speeds could be achieved by performing cut and paste operations on large blocks of text. We therefore varied the typing speed from one to 8 characters per second.

We created five shared documents and then evaluated the delays in turn on each of these documents and for each combination of settings (number of users and typing speed). In order to further eliminate random effects on the performance achieved, for each of the shared document and for each combination of settings, we repeated the experiment four times.

We used five local computers located at Inria Grand-Est, Nancy, France with the corresponding configuration features described in Table I. Clients simulating user behavior were executed on one of these computers: the Writer and Reader are executed by the first computer (with CPU Intel i7 720QM), and the DummyWriters are executed by other computers. DummyWriters are assigned to computers in a load balancing fashion: during the experiment when the number of clients, i.e. DummyWriters, is increased, each new DummyWriter is executed on the computer running the minimum number of clients with respect to its capacity, i.e. CPU and memory. We report the maximum number of DummyWriter which are executed on each computer in the third column of Table I.

III. RESULTS

In this section, we present and discuss the performance evaluation results of two popular real-time collaborative editing systems: Google Docs and Etherpad.

A. Google Docs

Google Docs is the most popular real-time collaborative editing system today. The service was introduced in 2007, and quickly attracted over one million users [START_REF] Covert | Will google docs kill off microsoft office?[END_REF], [START_REF] Crook | Google drive now has 10 million users: Available on ios and chrome os[END_REF].

The results of performance evaluation of Google Docs are displayed in Figures 12345for different typing speeds. The delays mean value line depicted in each figure shows the increasing trend of delay with an increasing number of users that join and modify the shared documents at the same time.

The above graphs show a very interesting feature of Google Docs. When the number of users is less than ten, Google Docs provides a very good and stable performance. The delays are very small and stable meaning that the performance of the system has not been affected when the number of users increases from one to ten. However, when the number of users exceeds ten, the performance of Google Docs decreases quickly, meaning that the delay increases significantly. This might be an explanation for the limit of 50 concurrent users specified by the Google Docs documentation.

The results also show us another interesting property of Google Docs: a higher typing speed leads to a higher dependency of delay on number of users. In other words, a higher typing speed will lead to a higher delay, and the delay also increases faster with the number of users.

We notice that it is very common to observe delays over ten seconds with Google Docs. Moreover, even if Google Docs documentation claimed that up to 50 users can modify a shared document at the same time, it is not always the case. We only can simulate 50 users if the typing speed of users is one character per second. Otherwise, if we increase the typing speed, a maximum of 38 users can log in and use the service. Additional users cannot use the system as they are repeatedly displayed the following message at login "Wow this file is really popular! Some tools might be unavailable until the crowd clears".

B. Etherpad

Etherpad is a popular open-source web based collaborative platform, with the first version being released in 2008. Etherpad is currently being used by many open-source and nonprofit organizations, such as Wikimedia 5 .

In order to evaluate the performance of Etherpad, we installed the source code provided by Etherpad development team 6 on our own server (Intel Xeon W3550) and performed the same evaluation method that we previously described for Google Docs. We applied all default settings of Etherpad (i.e. we used dirtyDB as the underlying database), and maintained the same evaluation settings as in the case of Google Docs. When the number of users is less than ten, we observe a similar phenomenon as Google Docs: Etherpad responds quickly to users' modifications, and delays are small and stable. However, when the number of users exceeds ten, Etherpad starts rejecting connections from new users, as it can be seen in the screenshot in Figure 6.

We can conclude that, Etherpad cannot be used by more than ten users that concurrently modify the shared document at the same time.

IV. DISCUSSION

A. Source of delay

As previously mentioned, in real-time collaborative editing, delays can appear because of network due to the structure and configuration of the Internet, which basically operates on the "best effort" principle, trying to deliver data from a computer to other ones as fast as possible but without any guarantee of time bound. Delays are also due to the collaborative editing systems architecture such as client-server, peer-to-peer, thin or In this paper, we measured the delay with different number of users and typing speeds. The delay the real users observe depends on how many users are modifying the sharing document at the same time, and how fast they are typing. However, we could not perform a more in-depth analysis on the reasons of delay as information about the inside architecture and algorithms used in Google Docs is not available and we could not take into account all the network infrastructure from our computers to Google Docs server.

During the experiments, we monitored the network bandwidth and CPU usage on our experimental computers 7 . The monitoring logs showed that our computers never consume more than 30% of CPU usage, and the incoming/outgoing network bandwidth is always less than 100 Kilobytes per second, which can be easily satisfied with the Internet connection today [START_REF] Akamai | State of the internet report[END_REF].

B. Sharing limit

Both Google Docs and Etherpad, the two popular real-time collaborative editing systems today, do not support a large number of users. Etherpad stops to accept new incoming users when the number of current users is more than ten. Google Docs claims that the service can support up to 50 users that can modify the shared document at the same time. However, this is true only if these users type at slow speed (1 character / second). Otherwise, the service cannot support more than 38 users that modify the shared document at the same time.

Therefore, Google Docs and Etherpad are not suitable for large-scale collaborative editing activities today, where hundreds of persons can share and modify a document such as a notes in events, meetings, conferences or MOOCs.

C. Effect on users

The effect of delay on users' behavior in collaborative editing has been studied in [START_REF] Ignat | How do user groups cope with delay in real-time collaborative note taking[END_REF], [START_REF] Ignat | Studying the effect of delay on group performance in collaborative editing[END_REF]. Twenty groups of four students from a French university have been recruited to perform an experiment including several tasks in collaborative editing. Users were asked to perform each collaborative task using the Etherpad collaborative editor under instructions that demanded interleaved work. Users were allowed to coordinate themselves by using the chat available in Etherpad. Without informing participants, delays were intentionally added, i.e. the server has been programmed to wait a certain amount of time before sending data to clients. The artificial delay levels included two, four, six, eight and ten seconds, which are realistic as we discussed in Section III. Each group had to perform the required tasks under a constant but undeclared delay in the propagation of changes between group members. Software recorded each user's desktop activity, including task performance as well as chat for coordination.

The task where users were provided with a list of movies and asked to search for the release date of those movies and then sort them in an ascending order according to the release date was analysed in [START_REF] Ignat | Studying the effect of delay on group performance in collaborative editing[END_REF]. For the analysis of the collected data outcome metrics for measuring the quality of the realised task but also process metrics for analysing user behaviour during achievement of the tasks were introduced: a sorting accuracy based on the insertion sort algorithm, average time per entry, strategies (tightly coupled or loosely coupled task decomposition of the task), chat behavior and collisions between users. It has been found that delay slows down participants which decrements the outcome metric of sorting accuracy. Tightly coupled task decomposition enhances outcome at minimal delay, but participants slow down with higher delays. A loosely coupled task decomposition at the beginning leaves a poorly coordinated tightly coupled sorting at the end, requiring more coordination as delay increases.

The note taking task where users listened to an interview about cloud computing and took notes during this time was analysed in [START_REF] Ignat | How do user groups cope with delay in real-time collaborative note taking[END_REF]. It has been noticed that due to delay, notes about the same topic were taken two, three and even four times. What happened is that when two users want to take notes on the same topic, in the presence of delay, changes of one user are not immediately visible to the other user, so a user thinks that the other user is not taking notes, so he/she is taking the notes. In that way, finally, the notes are in double. If more than two users try to take notes simultaneously, finally the same idea will appear three or even four times. It was found that the error rate is higher for groups that experienced a higher level of delay and redundancy is higher for groups in higher delay condition. Moreover, as delay increases the keywords depicted by users decreases. Groups were classified into two categories according to their declared experience in the domain of collaborative editing. For high experienced groups redundancy increases with the delay, but for low experienced groups the same tendency could not be observed. Chat behavior by means of number of accord words and definite determiners which together provides a common ground knowledge was considered as a measure of coordination. Low experienced groups used more coordination to manage redundancy. High experienced groups did not adjust their collaboration effort to manage redundancy.

A general hindrance of delay was observed in all analysed tasks. Delay destroys the value of collaborative editing and forces independent, redundant work.

Delays measured in GoogleDocs when the number of users exceeds ten are largely superior to the artificial delays experienced in [START_REF] Ignat | How do user groups cope with delay in real-time collaborative note taking[END_REF], [START_REF] Ignat | Studying the effect of delay on group performance in collaborative editing[END_REF]. We therefore expect that a high hindrance of delay will be experienced in Google Docs in scenarios of collaborative editing that involve a large number of users that concurrently modify a shared document.

D. Implications for design

Our primary purpose is to demonstrate the delay users could observe in popular real-time collaborative editing systems available in the market, and we showed that delay is a fact in current real-time collaborative editing systems. In the scale of more than ten users to modify the sharing document at the same time, delay can come up to 50 seconds.

Usually, in distributed computing, delays could appear due to traffic congestion when the amount of data transferred between nodes overcomes the capability of the network [START_REF] Kurose | Computer networking: a top-down approach[END_REF]. However, as we presented in Section IV-A, we did not observe the traffic congestion during our experiments. Therefore, we could suggest that the delay mostly comes from the architecture and implementation of the services.

As claimed in the official blog of Google Drive development team [START_REF] Blog | What's different about the new google docs: Making collaboration fast[END_REF], Google Docs is relying on the Jupiter algorithm [START_REF] Nichols | High-latency, Low-bandwidth Windowing in the Jupiter Collaboration System[END_REF] for synchronization between nodes. This might not be the best choice of algorithm to be used in collaborative editing at large scale, because the Jupiter algorithm, which belongs to Operational Transformation family of synchronisation solutions [START_REF] Ellis | Concurrency control in groupware systems[END_REF] requires a lot of computation on the server side, which increases the delay users observe in large-scale settings. Different algorithms such as CRDT [START_REF] Weiss | Logoot : A Scalable Optimistic Replication Algorithm for Collaborative Editing on P2P Networks[END_REF], [START_REF] Preguic ¸a | A Commutative Replicated Data Type for Cooperative Editing[END_REF], standing for Conflict-free Replicated Data Type should achieve a better performance in large-scale collaborative editing and feature smaller delays [START_REF] Ahmed-Nacer | Evaluating crdts for real-time document editing[END_REF]. Moreover, CRDT-based algorithms on strings should achieve better performance than character-based CRDT algorithms [START_REF] André | Supporting Adaptable Granularity of Changes for Massive-scale Collaborative Editing[END_REF], [START_REF] Yu | A CRDT Supporting Selective Undo for Collaborative Text Editing[END_REF].

Notifying delay to users could be implemented in realtime collaborative editing services. As suggested by several researches [START_REF] Ignat | How do user groups cope with delay in real-time collaborative note taking[END_REF], [START_REF] Vaghi | Coping with inconsistency due to network delays in collaborative virtual environments[END_REF], notified delay could let the users adapt their behaviors for the context. However, the delay notification has not been implemented yet in the real-time collaborative editing systems.

V. CONCLUSIONS

In this paper, we presented the performance measurement in term of delay in popular real-time editing services in the market. We demonstrated that, delay is a fact and high delay will appear and increase if there are more users joining to modify the shared document at the same time, or the users increase their typing speed. We demonstrated that the existing real-time collaborative systems are not yet ready for largescale collaborative activities, as they reject the new users' connection if the number of users in the system increases a certain limit.

Delay destroys the value of collaborative editing and forces independent, redundant work. Therefore, delay should be avoided and needs more attention from development team. We discussed several strategies to tackle the problem such as using suitable consistency maintenance algorithms or notifying delay to users.

Fig. 5 .

 5 Fig. 5. Performance of Google Docs with a typing speed of eight characters / second

Fig. 6 .

 6 Fig. 6. Etherpad rejects users' connection when the number of users exceeds ten

https://docs.google.com

http://etherpad.org

The implementation is available at https://github.com/vinhqdang/ collaborative editing measurement

https://support.google.com/docs/answer/2494827?hl=en as on 15-Feb-2016.

CPU usage and network bandwidth were monitored by using multiload indicator, which is available at https://launchpad.net/indicator-multiload

VI. ACKNOWLEDGEMENTS This work has been carried out thanks to the support of the PSPC OpenPaaS::NG project funded by the "Investissements d'Avenir" French government program managed by the "Commissariat général à l'investissement" (CGI).