Nhu Cuong Do
email: nhu.do@adelaide.edu.au

Angus R Simpson
email: angus.simpson@adelaide.edu.au

Jochen W Deuerlein
email: deuerlein@3sconsult.de

Olivier Piller
email: olivier.piller@irstea.fr

Particle Filter-Based Model for Online Estimation of Demand Multipliers in Water Distribution Systems under Uncertainty

Keywords: Particle filters, sequential Monte Carlo method, real-time demand estimation, water distribution systems, uncertainty

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Water distribution systems (WDS) are constructed to supply water for domestic, industrial and commercial consumers. The design, operation and management of these distribution systems is usually supported by the application of hydraulic models, which are built to replicate the behavior of real systems. These conventional models simulate flows and pressures of a WDS either under steady state conditions (constant demands and operational conditions) or under a short term extended period simulation (time-varying demands and operational conditions), for example a day or a week (USEPA 2005). The outputs from hydraulic models, therefore, usually represent the distribution system behavior during the sampling period (Preis et al. 2009). This leads to an inadequate understanding of the full range of operational states in the water system.

The installation of sensor devices as well as the Supervisory Control and Data Acquisition (SCADA) systems within the WDS can provide information on the status of some components in the system. However, the use of this additional data is currently limited to computing gross differences between the model outputs and reality [START_REF] Kang | Real-time demand estimation and confidence limit analysis for water distribution systems[END_REF]. Modification of the hydraulic models to maintain the consistency between observed data and simulated data is still a challenge that needs to be dealt with. Estimation of the model states/parameters, hence, is required so that the model is able to represent the real system.

Estimation is the process of fitting the outputs from the computer model, usually the pressures and flow rates at particular locations in the water network, with the field measurements, in order to calculate unknown variables of interest. Initial estimation studies in WDSs were pioneered by [START_REF] Rahal | Parameter tuning for simulation models of water distribution networks[END_REF], [START_REF] Walski | Technique for calibrating network models[END_REF] and [START_REF] Bhave | Calibrating water distribution network models[END_REF] with the proposal of the ad hoc (trial-anderror) calibration schemes, in which an iterative process to update unknown model parameters was implemented. Due to the slow convergence rate, this method is only applicable to small water networks. Later, explicit calibration methods were introduced [START_REF] Ormsbee | Explicit pipe network calibration[END_REF][START_REF] Boulos | Explicit calculation of pipe-network parameters[END_REF][START_REF] Boulos | Explicit network calibration for multiple loading conditions[END_REF]. These methods solved an even-determined set of water network equations where the number of unknown parameters is grouped to be equal to the number of measurements. As the measurement errors were also neglected, these methods usually did not represent real-world practical outputs. Therefore, explicit calibration models were often used to analyse historic events in water systems [START_REF] Savic | Quo vadis water distribution model calibration?[END_REF]. Subsequently, implicit methods were developed using either mathematical techniques or evolutionary optimization techniques, for example: Complex Method [START_REF] Ormsbee | Implicit network calibration[END_REF], Weighted Least Squares approaches [START_REF] Lansey | Parameter estimation for water distribution networks[END_REF][START_REF] Datta | Parameter estimation in water-distribution systems by least squares[END_REF], Singular value decomposition (SVD) method [START_REF] Sanz | Sensitivity analysis for sampling design and demand calibration in water distribution networks using the singular value decomposition[END_REF] or Genetic Algorithms (GA) (Preis et al. 2009;[START_REF] Abe | Epanet Calibrator-An integrated computational tool to calibrate hydraulic models[END_REF][START_REF] Do | Calibration of Water Demand Multipliers in Water Distribution Systems Using Genetic Algorithms[END_REF]).

These methods have drawn a high degree of attention from researchers. However, these models are mostly impractical due to either a requirement for a large quantity of 'good' observation data [START_REF] Savic | Quo vadis water distribution model calibration?[END_REF] or ignoring model uncertainties. Furthermore, few approaches have attempted to estimate model parameters and model states in conjunction with model uncertainties. [START_REF] Bargiela | Pressure and Flow Uncertainty in Water Systems[END_REF] found that a good approximation of pressure uncertainty bounds can be obtained by a linearization of the mathematical network model. [START_REF] Piller | Modeling the behavior of a network-Hydraulic analysis and sampling procedures for parameter estimation[END_REF] and [START_REF] Bush | Sampling design methods for water distribution model calibration[END_REF] used a sampling design method to estimate the model parameters and approximate the uncertainties. [START_REF] Lansey | Calibration assessment and data collection for water distribution networks[END_REF] applied a first-order approximation method to identify pipe roughness uncertainty. [START_REF] Nagar | LFT/SDP approach to the uncertainty analysis for state estimation of water distribution systems[END_REF] applied a linear fractional transformation and semi-definite programming method to estimate the pressure heads and their confidence bounds. In addition, some probabilistic methods [START_REF] Xu | Probabilistic model for water distribution reliability[END_REF][START_REF] Kapelan | Calibration of water distribution hydraulic models using a Bayesian-type procedure[END_REF][START_REF] Hutton | Application of Formal and Informal Bayesian Methods for Water Distribution Hydraulic Model Calibration[END_REF] have also been investigated for the estimation of model parameters. Due to the complexity of the uncertainties, estimation methods associated with uncertainty quantification are still a continuing research area, especially for real-time estimation purposes.

The complexity of uncertainties in WDS modeling has been addressed in Hutton et al. (2012b), in which the uncertainty is divided into three categories: (1) structural uncertainty, (2) parameter uncertainty and (3) measurement/data uncertainty. Structural uncertainty derives from the mathematical representation of the real system, such as network skeletonization and model aggregation. Skeletonized and/or aggregated models are predominantly used instead of all-pipes models to reduce the complexity of the network being analysed as well as to increase computational speed. It has been shown that skeletonized/aggregated network models can closely resemble the behaviour of full sized systems under steady state conditions (e.g. [START_REF] Perelman | Using aggregation/skeletonization network models for water quality simulations in epidemiologic studies[END_REF] and [START_REF] Preis | Efficient Hydraulic State Estimation Technique Using Reduced Models of Urban Water Networks[END_REF]). The second category, parameter uncertainty, refers to the errors of the parameters used to represent system components (e.g. pipe roughnesses, pipe diameters).

According to [START_REF] Kang | Real-time demand estimation and confidence limit analysis for water distribution systems[END_REF], these parameters are time invariant or vary slowly over time. Hence, this source of uncertainty can be neglected for real-time estimation problems. Finally, measurement/data uncertainty is the uncertainty from measurement devices and, more importantly, uncertainty from the inability to capture the temporal and spatial variation of consumer demands.

Because of their high impact on model uncertainty during short periods of time (or in real-time), nodal demands are therefore usually selected as the time varying parameters to be estimated.

The issue of short term demand forecasting and real-time demand estimation under uncertainties can be found in some recent studies. Note that the short-term demand forecasting and demand estimation are two different problems. The former focuses on predicting future demands (e.g. [START_REF] Cutore | Probabilistic prediction of urban water consumption using the SCEM-UA algorithm[END_REF], [START_REF] Hutton | A probabilistic methodology for quantifying, diagnosing and reducing model structural and predictive errors in short term water demand forecasting[END_REF] and [START_REF] Alvisi | Assessment of predictive uncertainty within the framework of water demand forecasting using the Model Conditional Processor (MCP)[END_REF]). The latter focuses on estimation of the current demands, which is also the main interest of this paper. This is useful, as demand estimation can be used at regular time steps to verify the accuracy of the predicted value and update the system operations. The problem of near real-time demand estimation has been studied using different approaches. [START_REF] Shang | Real time water demand estimation in water distribution system[END_REF] applied an extended Kalman filter, an iterative linear algorithm for nonlinear state estimation, to approximate water demand patterns. In that paper, water demand patterns were predicted by an ARIMA time series model and were refined using real-time observations. Similarly, Hutton et al. (2012a) introduced a particle filter method and an ensemble Kalman filter for the estimation of a single district meter area, which was assumed to follow a linear time series model. The particle filter model was implemented with and without measurement error to show its effect on the demand prediction uncertainty. An alternative for the demand estimates can be found in [START_REF] Kang | Real-time demand estimation and confidence limit analysis for water distribution systems[END_REF]. In their paper, two comprehensive methods for the demand estimation problem were introduced, the Kalman filter and the tracking state estimator (TSE). For the Kalman filter model, the water demand patterns were also assumed to follow a linear time series model, while the TSE model involved recursively computing the sensitivity matrix (i.e. the Jacobian matrix of the measurement vector with regards to the change in the state vector). The uncertainties of the demand estimates were suggested to be quantified by applying the first-order second moment formula. The two models were then tested on a case study (116 pipes, 90 nodes, 1 source and 1 tank) with an assumption that 19 flow measurement sites and 5 pressure measurement sites were available. It should be noted that the demand estimation problem is sensitive to the locations and types of the measurements [START_REF] Do | Calibration of Water Demand Multipliers in Water Distribution Systems Using Genetic Algorithms[END_REF]. Demand estimation models usually perform better with flow measurements rather than pressure/head measurements. However, due to the cost and difficulty of installing flow measurement devices compared to pressure measurement devices, flow measurement devices are usually not as commonly used as pressure measurement devices in real WDS networks.

In summary, water demands in WDS studies are usually assumed to be known and varied based on a diurnal curve. However, this assumption might lead to large approximations of WDS states in real-time due to the unpredictable variation of the water demands. Some efforts have been focused on the real-time demand estimation. By assuming that the water demand follows a linear time series prediction model, these models approximated the water demand patterns with some linear algorithms such as the Kalman filter or extended Kalman filter. Given the nonlinear stochastic nature of the water demands as well as the need for practical applicability, real-time estimation modeling of WDS still requires much research effort.

This paper presents a model framework for the online (near real-time) demand estimation of a WDS, which is named the DMFLive model. A predictor-corrector methodology is adopted in the DMFLive model to predict the hydraulic behaviors of the water network based on a nonlinear demand prediction sub-model, and to correct the prediction by using online pressure observation data. A particle filter method is applied to implement the predictor-corrector approach. The typical problems of the particle filter approach (particle degeneracy, impoverishment and particle convergence) are investigated by two different resampling schemes: systematic resampling (SR) algorithm and systematic resampling integrated with a genetic algorithm process (SRGA).

Uncertainties of model outputs are quantified and evaluated in terms of confidence intervals.

The paper is structured as follows. First, an explanation of the state estimation problem and its conceptual solution is introduced. Second, the basic concepts of particle filter methods to solve the estimation problem are explained. This is followed by a detailed description of the particle filter methodology applied for water demand state estimation in WDS. Two case studies are then used to evaluate the model. Finally, conclusions and suggestions for future work are given.

State estimation problem and its conceptual solution

The problem of state estimation involves finding a target state vector x k that evolves according to a discrete time stochastic model [START_REF] Ristic | Beyond the Kalman filter : particle filters for tracking applications[END_REF]):

𝑥 " = 𝑓 "&' 𝑥 "&' , 𝜐 "&' ( 1
)
where k is the index of discrete time steps; f k-1 is a known, possibly nonlinear function of the previous state and u is the process noise sequence. The value of x k can be found from measurements z k , which are related to x k via the measurement equation:

𝑧 " = ℎ " 𝑥 " , 𝑤 " (2)
where h is a known implicit or explicit, possibly nonlinear function and w is the measurement noise sequence. The noise terms u k and w k are usually assumed to be white noise and independent.

From a statistical and probabilistic perspectives, the state model can be represented by a probability density function (pdf). where 𝑝(𝑧 " |𝑥 " ) is the likelihood function, defined by the measurement equation (Eq. ( 2)) with the known statistics of w k .

According to [START_REF] Ristic | Beyond the Kalman filter : particle filters for tracking applications[END_REF], the recursive propagation of the posterior pdf shown in Eq. (3) and Eq. ( 4) is only a conceptual solution that cannot be analytically solved. The solution requires the storage of a fully non-Gaussian pdf, corresponding to an infinitive dimensional vector. Since the true solution is too complex and almost impossible to compute, an implementation of approximation techniques or suboptimal Bayesian algorithms is developed. The following section introduces an approximation technique, namely the particle filter, to solve the aforementioned state estimation problem.

Particle filters

Over the last decade, particle filters have been successfully applied to the state and parameter estimation of complex system models in various environmental engineering fields, such as hydrology [START_REF] Moradkhani | Uncertainty assessment of hydrologic model states and parameters: Sequential data assimilation using the particle filter[END_REF], [START_REF] Weerts | Particle filtering and ensemble Kalman filtering for state updating with hydrological conceptual rainfall-runoff models[END_REF]), hydraulic (Hutton et al. 2012a) and geoscience [START_REF] Van Leeuwen | Nonlinear data assimilation in geosciences: an extremely efficient particle filter[END_REF]). Unlike the Kalman filter (for linear problems), extended Kalman filter (which requires a linearization of the nonlinear problems) or the unscented Kalman filter (which uses a small number of deterministically chosen samples), the particle filter can use a large number of Monte Carlo samples to estimate fully nonlinear, possibly non-Gaussian target states. The key concept of a particle filter is to approximate the posterior pdf of states, defined in Eq. ( 4), by an ensemble of samples (N p ), each of which contains an associated weight (𝑤 "

3 ), and to compute estimates based on these samples and weights:

𝑝 𝑥 " 𝑍 " ≈ 𝑤 " 3 5 6 37' 𝛿(𝑥 " -𝑥 " 3 ) (5)
𝑤 " 3 = 𝑤 "&' 3 𝑝(𝑧 " |𝑥 " 3 )𝑝(𝑥 " 3 |𝑥 "&' 3 ) 𝑝(𝑥 " 3 |𝑥 "&' 3 , 𝑧 " ) (6)
where d is the Dirac delta function; i is the particle index; and 𝑝(𝑥 " 3 |𝑥 "&'

3

, 𝑧 " ) is the importance density function. In order to simplify the weight update of the particle, the importance density function is usually chosen as the transitional density function,

𝑝 𝑥 " 3 𝑥 "&' 3 , 𝑧 " = 𝑝 𝑥 " 3 𝑥 "&' 3
, which yields with scaling:

𝑤 " 3 = 𝑝(𝑧 " |𝑥 " 3 ) 𝑝(𝑧 " |𝑥 " 3 ) 5 6 37' (7)
These equations form the basis of most particle filters. However, it has been shown by [START_REF] Doucet | On sequential Monte Carlo sampling methods for Bayesian filtering[END_REF] that the variance of the weights will increase over time if the particle filtering process is limited at executing only these equations. Since the particles drift away from the "truth" as well as obtain negligible weights [START_REF] Moradkhani | Uncertainty assessment of hydrologic model states and parameters: Sequential data assimilation using the particle filter[END_REF], the model will fail to estimate the real states of the system. To avoid this problem, a resampling process, which replaces samples with low importance weights by the samples with high importance weights, is added to the procedure of particle filter models. In this paper, the systematic resampling method, also called the stochastic universal resampling, introduced by [START_REF] Kitagawa | Monte Carlo filter and smoother for non-Gaussian nonlinear state space models[END_REF], is selected for the resampling procedure of the particle filter model. A comprehensive explanation of the systematic resampling and the full review of particle filtering methods are described in (van Leeuwen 2009). In addition, an improved resampling method which integrates the evolutionary scheme from genetic algorithms into the resampling process, is also proposed to improve the efficiency of the particle filter model.

Particle filters applied for water demand state estimation in WDS

In this study, the predictor-corrector approach implemented by a particle filter model for the estimation of water demands in real-time is proposed, namely the DMFLive model. The demand prediction sub-model presented by [START_REF] Van Zyl | Sizing municipal storage tanks based on reliability criteria[END_REF] has been applied to predict the water demand multipliers (DMF) in a WDS. The hydraulic EPANET toolkit [START_REF] Rossman | EPANET 2: users manual[END_REF] which solves the hydraulic equations was used to compute the model equivalent of the measurement data (i.e. the nodal pressures, flow rates at measurement locations or the final tank levels at the end of each time step). These computed values then were integrated with the corresponding field measurements in order to correct/update the particle weights. Particles were, thereafter, resampled (with either SR or SRGA) and subsequently used as input for the prediction model.

Simultaneously, the estimated demand multipliers were computed and selected for uncertainty quantification. The uncertainties of the demand multipliers caused by the errors from measurement devices were computed using the first-order approximation formula. The flowchart of the DMFLive model is shown in Figure 1.

Initialization of particles

The DMFLive model starts with a creation of an ensemble of the particles (N p ). The particles are the demand residuals, driven by the demand prediction model to predict the demand multipliers.

In addition, each particle is assigned an initial weight equal to 1/N p .

Demand prediction sub-model

The initial particles (for the first iteration) or the particles after resampling (from the second iteration onwards) are transferred to the demand prediction sub-model. Demand residual information carried by the particles is used to track the states and predict the demand multipliers via the following equations [START_REF] Van Zyl | Sizing municipal storage tanks based on reliability criteria[END_REF]:

ln 𝑥 " < = 𝜙 3 < > 37' ln 𝑥 "&3 < + ln 𝜐 " < (8)
where 𝑥 " < is the demand residual state at time step k of the j th DMF; i is the lag counter; m is the number of autocorrelation lags (for the state estimation problem m=1 as referred to Eq. ( 1)); f i is the auto-regression coefficient for lag i and u k (0,s h ) is the white noise with mean zero and standard deviation s h .

The j th DMF is calculated as:

𝐷𝑀𝐹 " < = 𝐶 " < 𝑥 " < (9)
where 𝐶 " < is the value at time k of a typical diurnal demand pattern of the j th DMF. The C value can be identified based on meter information of different water users (e.g. in [START_REF] Beal | Identifying Residential Water End Uses Underpinning Peak Day and Peak Hour Demand[END_REF]).

Real-time hydraulic data

In practice, hydraulic data can be captured in real-time via the SCADA system or sensor devices.

For the DMFLive model, two types of real-time hydraulic data are required. First are the tank levels, pump and valve statuses, and second are the nodal heads and pipe flow rates at measurement locations. Tank levels, pump and valve statuses are used as boundary conditions for the hydraulic simulation of the water network model while the observations at measurement locations are used to correct/update the weight of the particles.

In order to validate the performance of the proposed model as well as its practical applicability to real WDS networks, all case studies in this research are assumed to have pressure measurements only. The input data sets to evaluate the DMFLive model are synthetically generated based on deterministic models, where the water network parameters are fully known, as follows: (1) known demand patterns are assigned to nodal demands; (2) EPANET is run to record tank levels, pump statuses, and pressures at selected measurement locations;

(3) to introduce the measurement errors, a normal distributed random error in an allowable range (±D meas ) is added to each nodal pressure.

Simulator

The hydraulic behavior of the water distribution network at each time step is simulated using an EPANET steady state simulation. The inputs are the predicted DMFs, tank levels, and pump and valve statuses. The water network characteristics such as pipe lengths, diameters, roughness coefficients, node elevations, pump curves, etc. are assumed to be known and constant. The outputs from the EPANET hydraulic solver is the model equivalent of the observations, i.e. the simulated nodal heads and pipe flow rates at measurement locations.

Corrector

The weights of the particles are corrected/updated by associating the simulated heads and flows with the actual observations via Eq. ( 7) where the likelihood function is assumed to be Gaussian:

𝑝 𝑧 " 𝑥 " 3 = 1 2𝜋 𝑅 𝑒 & ' I J K &L M K N O P QR J K &L M K N ( 10
)
where ℎ(𝑥 " 3 ) is the model equivalent of the observations z k (simulated nodal heads and flow rates), and R is the covariance matrix of the observation errors, which in general is caused by errors from two main sources: forward model error and measurement device error. The forward model error,

∆ TUVW = 𝑍 TUVW -ℎ(𝑥 TUVW ) (11)
is the difference between the true observation vector, Z true , and the corresponding vector output from the hydraulic simulation model EPANET using the true state x true . The true observation vector is a theoretical vector that represents observations measured by perfect measurement devices. It is linked to the actual measured values via the expression:

𝑍 = 𝑍 TUVW + ∆ >WXY (12)
The observation error covariance matrix, therefore, can be estimated as R = R true +R meas , where R true and R meas denote the covariance of the forward model error and the covariance of measurement error, respectively (see [START_REF] Waller | Using observations at different spatial scales in data assimilation for environmental prediction[END_REF] for a detailed explanation and calculation of the observation error covariance matrix). To produce good estimates of the model state in real case studies, the error covariance matrix must be well understood and properly calibrated. As previously mentioned in this paper, the measured data in all case studies were synthetically generated from the EPANET model based on "true" demand patterns. The forward model error, therefore, equals to zero. The covariance matrix R, as a result, is the diagonal matrix where the diagonal elements are the variances of the measurement errors, since observations are independently measured at different locations of the network by different measurement devices. The measurement errors with specified ranges are assumed to be known so that the covariance matrix R can be identified.

Resampling

Resampling is applied to create new ensembles of particles from the posterior pdf of the previous step. In this paper, two alternatives of resampling are tested: systematic resampling algorithm (SR)

and systematic resampling integrated with the GA operators (SRGA).

The SR algorithm generates a random number u s from the uniform density U[0, 1/Np], and consequently creates N p ordered numbers [START_REF] Hol | On resampling algorithms for particle filters[END_REF]:

𝑢 3 = 𝑖 -1 𝑁 ] + 𝑢 Y (𝑖 = 1, … , 𝑁 ] ) (13)
New particles are then selected that satisfy Eq. ( 14):

𝑥 _W3 = 𝑥(𝐹 &' 𝑢 3 ) (14)
where F -1 denotes the generalized inverse of the cumulative probability distribution of the normalized particle weights.

To reduce the convergence problem of the particles (i.e. all the particle weights are equal to zero) when applying the model for large networks with multiple demand patterns, the SRGA method is also applied. Three GA operators of selection, crossover and mutation are responsible for modifying the predicted demands before computing the weight of a particle by Eq. ( 10). In the selection step, particles are compared to each other through tournament selection and the best particles are selected as parents. Parent particles are then paired and go through crossover and mutation to generate offspring solutions. While the details of GA can be found in Nicklow et al.

(2010), it is important to know that new parameters need to be introduced: the probability of crossover P c , the probability of mutation P m and the number of generations N gen .

Demand multiplier outputs and uncertainty quantification

The estimate of the state x k is obtained by taking the mean of the particle filter sample set [START_REF] Salmond | An introduction to particle filters[END_REF]:

𝑥 " ≈ 1 𝑁 a 𝑥 " 3 * 5 c 37' (15)
where 𝑥 " 3 * is the state updated based on the posterior analysis of the model weights.

For particle filter models, the uncertainty of the model output can be computed by taking the variance of the samples:

𝑣𝑎𝑟 𝑥 " ≈ 1 𝑁 a 𝑥 " 3 * -𝑥 " 𝑥 " 3 * -𝑥 " g 5 c 37' (16)
For the demand multiplier estimation problem, it should be noted that a small change in the demand multiplier can cause a large change in nodal demands (for nodes with large base demands) and consequently result in large variations of nodal pressures, especially at nodes that are sensitive to nodal demands. Most of the demand forecasting models are required to capture both peak-demand hours and off-peak demand hours, with a demand multiplier factor that can vary from 0 to 4 [START_REF] Chin | Water-resources engineering[END_REF]. The weight of the particles via Eq. ( 10) can, therefore, easily approach zero which leads to either particle degeneracy or particle non-convergence. Using a larger number of particles can prevent this problem, however, if the dimension of the state vector increases, the required number of particles increases exponentially. One way to solve these issues is to incorporate the covariance of the forecasting nodal heads/ pipe flow rates into the likelihood function:

𝑝 𝑧 " 𝑥 " 3 = 1 2𝜋 𝑅 * 𝑒 & ' I J K &L M K N O (P * ) QR J K &L M K N ( 17
)
where R* = R+S, S is the covariance matrix of the forecast nodal heads or pipe flow rates, computed based on the forecast demands. This covariance matrix can be estimated by running the demand forecasting model multiple times to obtain the range of forecast demand multipliers, then applying these values into the hydraulic model to compute the variance of simulated nodal heads and pipe flow rates at measurement locations.

Although the method can ensure some of the particles always contain weights to avoid particle non-convergence and degeneracy, this would increase the noise of the output model. The variance of the model output (i.e. the uncertainty of the model output) is required to be computed by a different method instead of using Eq. ( 16).

Another way to overcome the convergence and degeneracy issues is to integrate the GA operators into the resampling process as mentioned in the previous sections. The integrated GA approach can prevent the model from experiencing these problems by exploring the state-space region and selecting the best particles (including the replication of good solutions). However, it might lead to another problem for the particle filter, referred to as particle impoverishment. The distribution of the state model, because of the particle impoverishment, is poorly represented by only one or a few particles which significantly reduces the variance of the model state.

To ensure reliable outputs from the particle filter model, it is proposed to approximate the uncertainty of the model state by an independent method, such as the first-order approximation (FOA) method adopted from [START_REF] Piller | Modeling the behavior of a network-Hydraulic analysis and sampling procedures for parameter estimation[END_REF]. This also has the advantage of significantly decreasing the computational time, as it will be shown in the case studies. The model outputs, therefore, are the estimate of the demand multipliers computed by Eq. ( 15) and the confidence intervals computed by FOA method. For example, the 95% confidence interval of the estimated demand multiplier (i.e. the range in which the true demand multipliers are expected to be 95% of the time) can be obtained by the following expression:

∆𝐷𝑀𝐹 " ≤ 1.96(𝑊 ' I 𝐽) n ∆𝐷𝑀𝐹 " < ≤ 1.96 𝑆 3< > <7' , with 𝑆 = (𝑊 R p 𝐽) n (18)
where J is the Jacobian matrix of flows and heads with respect to the water nodal demand at time k; W is the weight matrix where the diagonal elements are the reciprocals of the variances of measurement errors (W=R -1 ); superscript † represents the pseudo-inverse operator. The derivation of Eq. ( 18) is explained in detail in Appendix A.

By considering the Jacobian (sensitivity) matrix, the uncertainty of the output model from FOA method can provide meaningful information about the sensitivity of the pressure with respect to the change in the nodal demand. This information can be used to guide where to place measurement stations. However, the method requires calculation of the sensitivity matrix, which may be time consuming when applied to large and complex networks.

Summary of assumptions and input requirements for the DMFLive model

Several assumptions are made for this study: (1) the model of the water distribution network perfectly represents the real system with known network characteristics (e.g. pipe roughness coefficients, length and diameters, etc.), and only demand multipliers are required to be estimated;

(2) typical demand patterns for different homogeneous demand groups in WDS are assumed to be known. The homogeneous demand groups can be identified based on a multi-criteria demand zones clustering algorithm presented in [START_REF] Preis | On-line hydraulic state estimation in urban water networks using reduced models[END_REF]. There is uncertainty of the model outputs associated with demand groupings, but this is not considered here. Therefore, (3) the source of uncertainty is only from the errors from measurement devices; (4) the errors of the measurement devices are assumed to be known and to follow a Gaussian distribution; [START_REF] Nagar | LFT/SDP approach to the uncertainty analysis for state estimation of water distribution systems[END_REF] the observation data for the online (near real-time) estimation model is available every 10, 15 minutes, 1 hour or larger time steps. The influence of slow transients (mass oscillations) are, therefore, ignored in this context.

The inputs required for the DMFLive model consist of the number of particles, the inputs for the demand prediction sub-model, inputs for the hydraulic simulation model (EPANET), input for the correction step and the parameters for the integrated GA operators (P c , P m and N gen ). The prediction sub-model requires the data of typical demand patterns, the auto-regression coefficient (f i ) and the variance of noise of demand residuals (s h 2 ). These parameters are calibrated independently based on historical demand data for specific networks, for example f I = 0.7 and s h 2 = 0.13 2 as in van [START_REF] Van Zyl | Sizing municipal storage tanks based on reliability criteria[END_REF]. The EPANET model requires the known data of tank levels, pump and valve statuses. The correction step requires the observation data at measurement sites. Note that the particle filter model associated with the GA process can only be applied to networks with multiple demand patterns (e.g. the second case study in this paper). Two-point crossover operator with the probability of crossover P c =0.7, bitwise mutation with the probability of P m = 1/N DM (N DM is the number of demand patterns in the network, N DM = 5, corresponding with P m =0.2 for the second case study) and the number of generations N Gen = 50 were selected for the GA process.

Case study 1

The first case study used to evaluate the model is shown in Figure 2. The network has 9 nodes (8 nodes with demands), 12 pipes, one tank and one reservoir. The network characteristics can be found from the EPANET example, namely the Net1 network. Three pressure measurements (with a precision of D meas =±0.2 m, consistent with a standard deviation of s meas = 0.1 for the measurement error at 95% confidence interval) are assumed to be placed at three random locations (nodes 13, 22 and 31). All nodal demands are assumed to follow a single demand pattern that varies every 15 minutes, (represented by the continuous line in Figure 2.b). The demand pattern is a random daily demand pattern (from a yearly demand pattern) for 100 households obtained from the BESS model [START_REF] Thyer | A behavioural approach to stochastic end use modelling[END_REF]). The DMFLive model is required to track this demand pattern using the three pressure measurements, which are also obtained every 15 minutes.

In this case study, the default demand pattern given in the Net1 example (represented by the dashed line in Figure 2.b) was selected as the typical demand pattern. Different values of the autoregression coefficient (f) as well as variance of noise (s h 2 ) were applied for the demand prediction sub-model.

The accuracy of the demand estimates from the DMFLive model were evaluated in terms of the coefficient of determination (R 2 ) and the root mean squared error (RMSE). For a number of particles N p = 100, the results of the demand estimates from the DMFLive model are presented in Table 1.

The DMFLive model performed very well when the auto-regression coefficient was selected in the range of 0.3 £ f £ 0.9 and the noise variance was selected in the range of 0.25 £ s h 2 < 0. For this best estimated demand pattern, the confidence intervals and the scattergram between actual demand multipliers and estimated demand multipliers are plotted in Figure 3.a.

In Figure 3.a, the estimated demand pattern yields a very good match with the actual demand pattern during the time period (24 hours, corresponding to 96 time steps). The actual demand pattern is entirely covered by the range of the 95% confidence intervals calculated from FOA method. This confidence interval range, which is expected to bracket the "true" demand multipliers in 95% of the cases, represents the uncertainty magnitude of the estimated demand due to the error from measurement devices.

The model has also been run with the number of particles N p =100 and N p =20 to provide a comparison between the FOA method (i.e. Eq. ( 18)) and the posterior analysis (i.e. Eq. ( 16)) for uncertainty quantification, as shown in Figures 3.b

Effects of tank level update on the estimation

In extended period simulations of most hydraulic solvers (including EPANET), the nodal demands are considered to be constant during the time step. The levels of the tanks in the network at the end of the time step are consequently computed based on this assumption and are used as the initial tank level for the next step. Due to continuously unpredictable change of the water demand in practice, the actual tank level at the end of the time step is usually different to the tank level computed by the model. As a result, the estimated total volume of water used during the time step is also different from the actual volume of water used in practice. This issue can be overcome by minimizing the difference between actual tank levels at the beginning of the time step and the final estimated tank level at the end of the previous step. The demand estimation model, however, will be delayed until the information of the tank level at the beginning of the next time step becomes available. In other words, the model outputs will be the estimates of the demand multiplier at the previous time step.

In order to evaluate the effect of including tank level information at the end of every time step, an additional test is conducted. Instead of assuming that the observations are available at every 15 minutes, in this test it is assumed that the data can be obtained every hour and the model is required to estimate the demand pattern at each hour time step (while the actual demand pattern is varied every 15 minutes). compared to RMSE =0.080, respectively). However, the total estimated water usages tabulated in Table 2 shows that the DMF-WTLive model is more accurate in predicting the volume of water delivered to the users.

The total estimated water usage during the 24-hour simulation period from DMFLive model was 5942.43 m 3 /day, 46.81 m 3 /day (or 0.78%) less than the actual water usage. On the other hand, total estimated water usage from DMF-WTLive model was 6007.31 m 3 /day, only 18.07 m 3 /day (or 0.30%) more than the actual value. Therefore, if the estimation can be delayed one time step, the final tank level information should be included into the model to improve the accuracy of the estimated total volume of water used.

Case study 2

In order to evaluate the performance of the proposed model in large networks that contain more than one demand pattern, the C-Town network from Ostfeld et al. ( 2011) is selected as the second case study. The network consists of 429 pipes, 1 reservoir, 7 tanks, 5 pump stations (with a total of 11 pumps), 4 PRV valves and 388 nodes (334 nodes with demands), which are divided into five district demand areas. Each district demand area follows a different hourly demand pattern. As the data of the demand patterns is available for seven days, the first 24 hours of these demand patterns are assumed to be the typical demand patterns for the demand prediction sub-model. The performance of the particle filter model is then evaluated by estimating the remaining 6-day hourly demand patterns.

It is assumed that there are 14 pressure measurement sites (from P1 to P14) that are randomly located at 14 places. These pressure measurements, again, are assumed to have a measurement error of D meas =±0.2 m. The inputs for the real-time demand estimation model are, therefore, the pressures at these locations, the tank levels of seven tanks and the pump statuses of 11 pumps at The predicted DMFs in this case show an average correlation to the actual DMFs with the R 2 ranging from 0.69 to 0.74, while the estimated DMFs are strongly correlated to the actual ones with all R 2 values being close to unity. The estimation for these five DMFs are also reliable during the simulation period (six days), as the spreads of the scattered dots are close to bisector lines.

Improving DMFLive model performance by SRGA and modified likelihood function

The DMFLive-I model can only perform well with a large number of particles (N P ≥ 25,000).

Smaller numbers of particles result in weak estimates of the DMFs due to particle collapse at some steps. Since increasing the number of demand patterns requires an exponentially increasing number of particles, it is necessary to improve the efficiency of particle filter model so that it can be applied to complex systems.

Effect of the locations of measurements on the quantification of demand uncertainty

As discussed in a number of studies such as in [START_REF] Piller | Modeling the behavior of a network-Hydraulic analysis and sampling procedures for parameter estimation[END_REF] and [START_REF] Do | Calibration of Water Demand Multipliers in Water Distribution Systems Using Genetic Algorithms[END_REF], the locations of the measurements have a strong impact on the results of the demand estimation models.

Furthermore, the selection of measurement locations also affects the confidence intervals of the estimation outputs.

From the mathematical point of view, the uncertainty of estimated demands depends on the sensitivity of the flows/heads at measurement locations in relation to the change in the water nodal demands. This sensitivity is represented by the sensitivity matrix J (Eq. ( 18)), which is, in this case study, the Jacobian matrix of the heads with respect to the demand multipliers. The sensitivity of the heads with respect to the change of the demand multipliers depends on two factors: (1) the position of the nodes in the network and (2) the base demands at the nodes. In fact, the nodes close to fixed-head nodes (tanks or reservoirs) are less sensitive than the ones far from the fixed-head nodes. This is because of a change in nodal demands will result in a smaller change in the pressures of the closer nodes than the farther nodes. In a similar way, small base demands in the same pattern will result in small friction losses and consequently small changes in pressures. Therefore, nodes selected in these regions may cause large uncertainty in demand multiplier estimation. The for the estimation of the demand multipliers, as has been addressed in [START_REF] Sanz | Comparison of demand pattern calibration in water distribution networks with geographic and non-geographic parameterization[END_REF].

The relocation of the pressure measurements also improves the estimation of DMF 4, with a RMSE = 0.028 for the modified test, compared to a RMSE =0.036 of the original test. The placement of the two new measurement sites also causes a slight difference in the results of other estimated DMFs due to the change in the particle weights. However, the results of the four remaining DMFs are still very good and similar to the estimated values of the original test.

To sum up, the uncertainty of estimated demand multipliers caused by the errors of measurement devices is influenced by the measurement locations. It is suggested to choose the locations that are more sensitive to the demand multipliers (see [START_REF] Do | Calibration of Water Demand Multipliers in Water Distribution Systems Using Genetic Algorithms[END_REF] for an example of optimal measurement location). However, it has also been shown that the DMFLive model can be used to estimate the demand multipliers even when the measurement devices are located at some less sensitive places. The uncertainty of the estimated demand multipliers can be used to identify which measurement locations need to be improved. This is another advantage of the DMFLive model.

Conclusions and recommendations

Real-time demand estimation under uncertainties is exceptionally difficult due to the unpredictable stochastic behavior of the water demand as well as the nonlinearities of hydraulic systems. In this paper, the DMFLive model framework has been introduced, which can be used to estimate the demand multipliers of a WDS in near real-time. A predictor-corrector approach has been adopted and solved by a particle filter method. A nonlinear demand prediction model is applied to predict water demand multipliers at each time step, while the online pressure observations are used to correct the prediction. Output uncertainty caused by the measurement errors has also been assumed to be Gaussian with mean of zero and standard deviation of 𝜎 3 ; 𝑦 3 |WXY is the i th measurement site in the data set.

The demand calibration can be formulated as a box-constrained Least Squares problem that minimizes the differentiable criterion at each time step: where m is the number of measurement sites, 𝜀 P is the reduced residual, which is the residual divided by the corresponding standard deviation, 𝜀 P ~𝑁 0,1 .

𝑓
The gradient of f at x 0 is: ∇𝑓 w = 𝐽 𝑥 w g 𝑊(𝑦 𝑥 w -𝑦 |WXY ) (A3) where W is the weight matrix where the diagonal elements are the reciprocals of the variances of measurement errors; 𝐽 𝑥 w g = 𝜕 M 𝑦 𝑥 w g is the transposed Jacobian matrix of the prediction function at x = x 0 .

The Hessian approximation takes the simple form of the symmetrical, positive semi-definite matrix:

𝐻 w = 𝐽(𝑥 w ) g 𝑊𝐽(𝑥 w ) (A4) It is essential for the Jacobian to be full rank of the size of x, so that H 0 is invertible and a definite matrix.

An approximation of function f to minimize Eq. (A2) by a quadratic function at x 0 leads to the approximation of x: 𝑥 = 𝑥 w -(𝐻 w ) &' ∇𝑓 w (A5) By replacing Eq. (A2) and Eq. (A3) into Eq. (A5), the approximation of x can be expressed as: 𝑥 = 𝑥 w -𝐽(𝑥 w ) g 𝑊𝐽(𝑥 w ) &' 𝐽 𝑥 w g 𝑊(𝑦 𝑥 w -𝑦 |WXY ) Using Eq. (A1):

  64. Due to the large difference between the typical demand value and the actual demand value at each time step (Figure 2.b), the selection of small values of the auto-regression coefficient and noise variance resulted in relatively poorer performance of the model (e.g. R 2 = 0.465 and RMSE =0.198 for f=0.3 and s h 2 =0.04). The best output of the DMFLive model was obtained at f=0.7 and s h 2 =0.25, with R 2 = 0.988 and RMSE =0.028, respectively.

  , 3.c and 3.d. Figures 3.a and 3.c show the uncertainty quantified by the FOA method while Figures 3.b and 3.d shown the uncertainty quantified by the variance of particles. For N p = 100 particles, the 95% confidence intervals from both methods are comparable to each other, which demonstrates that the FOA method can provide reliable results compared to the variance of the particle filter samples. A good estimate of the demand multipliers (RMSE=0.047) is obtained by the DMFLive model even when the number of particles is reduced by a factor of five (N p =20), as seen in Figures 3.c, and 3.d. The uncertainty boundary calculated by the FOA method in Figure 3.c has a similar range to the case with N P =100 particles and covers most of the actual values. On the other hand, the uncertainty bounds calculated by Eq. (16) in Figure3.d are collapsed into single value at some time steps due to an insufficient number of the particles. Application of Eq. (16) for uncertainty quantification, therefore, requires an in-depth evaluation of the number of particles in the model if it is selected for the uncertainty quantification.The range of demand multipliers predicted in time according to the evolution of the particles is presented in Figure4.a. The predicted values range from DMF min = 0.1 to DMFmax = 7.0, indicating that the demand prediction sub-model can predict a large range of demand multipliers, and cover the range 0 £ DMF £ 4 suggested by[START_REF] Chin | Water-resources engineering[END_REF].

  Figure 4.b plots the scattergrams of the actual demand multipliers versus the predicted demand multipliers (i.e. the mean of the prediction) and actual demand multipliers versus estimated demand multipliers. The scattergram shows a constant and strong correlation between actual demand multipliers and estimated demand multipliers over time with R 2 being close to unity. Due to large difference between the typical demand pattern and the actual demand pattern, the forecasting model does not provide good prediction, resulting in weak and skewed correlation between the actual values and the predicted values. Despite this, the DMFLive model is still capable to provide very good estimates of the demand multipliers.

Figure 5

 5 Figure 5 plots the two estimated demand patterns with and without tank level information (herein

  each hour time step. The topology and measurement locations of the C-Town network are shown in Figure 6. Five different demand prediction sub-models were used to predict the five demand patterns. The parameters of the five demand prediction sub-models were assumed to have the same values of 𝜙 = 0.7 for the auto-regression coefficients and 𝜎 L I = 0.16 for the variances of noise. The standard particle filter model (i.e. using systematic resampling), herein referred as the DMFLive-I model, provides good results only if N P ≥ 25,000 particles. The estimates of five different demand patterns for 6 days (from 25h to 168h) are shown in Figure 7. It is seen that the estimated demand patterns closely match the actual demand patterns, especially for DMF 2 (RMSE = 0.021), DMF 3 (RMSE = 0.024), DMF 1 (RMSE = 0.029) and DMF 4 (RMSE= 0.036). The estimated demand pattern DMF 5 is less accurate, with the root mean squared error of RMSE = 0.061.

Figure 7

 7 Figure 7 also plots the 95% confidence intervals for calculated by the FOA formula. The intervals

Figure 8

 8 Figure 8 displays the scattergrams and coefficients of determination of the five predicted demand

  Two methods have been investigated as mentioned previously in the paper: (1) incorporating the variance of the forecasting nodal heads into the likelihood function. The weights of particles in the model, referred as DMFLive-II model, are then calculated by the modified likelihood function (Eq. (17)); and (2) by the integration of a GA process into the systematic resampling of the model, herein referred as DMFLive-III model.Table3presents results (in terms of the RMSE of each demand pattern) of running these models with N P =1000 and N P =5000 for DMFLive-I, II and with 𝑁 ] tu = 20 and 𝑁 ] tu = 100 for DMFLive-III. It may be seen that for both N P values, the DMFLive-I gives very poor estimates of the DMFs.On the other hand, the DMFLive-II model only requires N P =1000 (corresponding to 1.43*10 5 evaluations for 143 hours) to provide fairly good results, while the DMFLive-III performs wellwhen 𝑁 ] tu = 100. The results of DMFLive-II (N P =5000) and DMFLive-III (𝑁 ] tu = 100) give similar to the results of DMFLive-I running at N P =25,000 (corresponding to total evaluations of 3.575*10 6 ). This means the computation can be reduced by approximately a factor of five times.

Figure 9

 9 Figure9shows the DMF 1 uncertainty ranges from 25 to 49 hours of the three models DMFLive

  sensitivity matrix takes into account these two factors. Small values in the sensitivity matrix values mean that the nodes are less sensitive to the demands and the estimation might have large uncertainty. Therefore, the uncertainty of the estimated DMFs can be reduced by selecting the more sensitive locations in the network.Let us conduct an additional test to evaluate the effect of the measurement locations on the uncertainty of the estimated demand multipliers, for example the uncertainty of the estimated DMF 4. For this test, the locations of measurements P7 (with the base demand of 𝐷 v w = 0.50 L/s) and P9(𝐷 x w = 0.59 L/s) are relocated to P7A (𝐷 vu w = 1.33 L/s) and P9A (𝐷 xu w = 1.13 L/s). The DMFLive model was implemented with the same conditions and the other measurement locations are fixed at the same places as the original test.

Figure 10

 10 Figure10shows the sensitivity matrixes J 0 (for the original test) and J A 0 (for the modified test)

Table 1 :

 1 Coefficient of determination (R 2 ) and root mean squared error (RMSE) of demand estimates corresponding to different parameter values of the demand prediction model for case study 1

	No	Auto-regression coefficient (f)	Variance of demand residual (s h 2 )	R 2	RMSE
	1		0.04	0.465	0.198
	2	0.3	0.25	0.986	0.030
	3		0.64	0.983	0.033
	4		0.04	0.528	0.189
	5	0.5	0.25	0.986	0.030
	6		0.64	0.987	0.029
	7		0.04	0.982	0.033
	8	0.7	0.25	0.988	0.028
	9		0.64	0.986	0.031
	10		0.04	0.987	0.029
	11	0.9	0.25	0.986	0.031
	12		0.64	0.985	0.031

*Bold -Best estimated result

Table 2 :

 2 Actual and estimated total volume of water usage during calculated period

	Cases	Total (m 3 /day)	Difference (m 3 /day)	% Difference (%)
	Actual daily water usage	5989.25
	Estimated water usage with DMFLive	5942.43	46.81	0.78
	Estimated water usage with DMF-WTLive	6007.31	18.07	0.30

Table 3 :

 3 Performance of DMFLive model with SR (I), modified likelihood function (II) and SRGA (III)

	Model type	DMFLive-I	DMFLive-II	DMFLive-III (N Gen =50)
	No. Particles	N P =1000	N P =5000	N P =1000	N P =5000	N P	GA =20	N P	GA =100
	No. Eval.	1.43* 10 5	7.15*10 5	1.43* 10 5	7.15* 10 5	1.08*10 5	5.43*10 5
	RMSE DMF1	0.386	0.405	0.050	0.027	0.107	0.030
	RMSE DMF2	0.365	0.422	0.026	0.021	0.067	0.025
	RMSE DMF3	0.416	0.237	0.029	0.027	0.068	0.023
	RMSE DMF4	0.385	0.229	0.043	0.038	0.086	0.032
	RMSE DMF5	0.366	0.246	0.074	0.049	0.190	0.050

Author-produced version of the article published in : Journal of Water ResourcesPlanning and Management, vol 143, n°11, 2017

quantified by the first-order approximation formula. The performance of the DMFLive model is evaluated by two WDS case studies. The results showed that the nonlinear demand prediction model combined with the particle filter method used in the paper are well suited for the near realtime demand estimation problem.

Within the first case study, the benefits of having additional information about the tank level of the next time step have been explored. If the estimation of the demand multipliers can be delayed one time step, the tank level at the beginning of the next time step can be used by the model to improve the estimation of the total volume of water used.

Within the second case study, three versions of the DMFLive model were developed to be used in large networks with multiple demand patterns. All versions provided good results, showing that the models are capable to be used in large networks. Finally, the effect of the measurement locations on the uncertainty of the estimated demand multipliers has been explored. Results

showed that the uncertainty can be used to identify which measurement locations need to be improved. Future work involves considering adding additional uncertainties into the DMFLive model. Moreover, testing the model for non-geographically distributed demand networks is also necessary to show its capability when applied in practice.

Appendix

The problem of demand calibration involves finding the demands of the network hydraulic model to best fit the data set. Consider the nonlinear regression equation:

where x is the n d by 1 vector of parameters to calibrate (the demand multiplier factors that depend on time); y i (x) is the scalar multivariate function of predictions from the network hydraulic model, given the parameter x; 𝜀 3 is the residual between model prediction and observation, which is

The influence of the measurement errors with regards to the parameter estimates, therefore, can be obtained at the first-order of Eq. (A6): The uncertainty in term of confidence limits can be expressed as:

-For 99% confidence intervals ( 𝜀 3 ≤ 2.58𝜎 3 ):

∆𝑥 ≤ 2.58 𝐽 𝑥 w g 𝑊𝐽 𝑥 , with 𝑆 = (𝑊 R p 𝐽) n (A9)


Laurent Prévot

Matthieu Stali

Shu-Chuan Tseng

Grouping conversational markers across languages by exploiting large comparable corpora and unsupervised segmentation

This work approaches Conversational and Discourse Markers (hereafter DM) from a radical data-driven perspective grounded in large comparable corpora of French, English and Taiwan Mandarin conversations. The key features of our approach are (i) to account for lexicalization as a by-product of unsupervised segmentation applied to our corpora, (ii) to exploit simple metrics for clustering DM (both within a language and within multilingual clusters). We explore the benefits and the drawbacks of such a radical approach to DM. In particular we compare the DM clusters obtained from traditional segmentation into tokens (as given by manual transcription of the corpora) vs. unsupervised segmentation. The metrics on which we ground the clustering experiments are based on contrast between (i) short vs. longer utterances distribution and (ii) position within longer utterances.

Introduction

Leaving aside some interesting descriptive studies, there are not many attempts to perform systematic and quantitative comparative analysis of social interactions (such as conversations and task-oriented dialogues) from a linguistic perspective. Language resources and natural language processing tools still rely on written canonical data. In the context of studying, comparing and exploiting social interactions; in which speech is fiercely spontaneous and exhibits its own patterns; appears to be a major handicap. Once situated within a multilingual or translational task, it becomes even more difficult to handle by adding the bias towards written canonical data of each language before being able to consider the multilingual or translational aspects themselves. Thus, we propose here to adopt a relatively shallow and data-intensive approach to consider directly the spoken data without passing through resources and tools created for canonical written data.

Comparable corpora are extremely useful for a range of Human Language Technology tasks but also for exploring phenomena across languages. In this paper we are developing a data-driven approach to study discourse and interactional markers (hereafter DM) in a comparative way thanks to large conversational comparable corpora. Our work aims at identifying and grouping discourse markers into homogeneous classes through a purely bottom-up approach carried out on large corpora. Studying discourse markers has a long history in linguistics and corpus linguistics (see Section 2.) but our approach combine some methodological choices that makes it original. This approach relies on rather large comparable conversational corpora across the languages scrutinized (introduced in section 3.). Moreover those corpora have to be transcribed. More precisely the two key ingredients are (i) to explore unsupervised segmentation of our data sets as explained in 4.1. ; (ii) to explore a set of distributional measures of the word-like units for characterizing them (See 4.2.). Finally, in our experiments, standard clustering techniques are used to obtain groups of clusters that we try to label with categories in section 5..

Discourse Markers

Discourse markers, such as like and well in English to quote a few, are key elements in conversations which help speakers build their speech's structure. The main issue when studying DMs lies in the lack of consensus and thus in the various definitions and denominations that can be found among works in the literature related to conversational speech. We can mention the following terms, being the most frequently used: discourse markers [START_REF] Schiffrin | Discourse markers[END_REF][START_REF] Fraser | What are discourse markers?[END_REF]; pragmatic markers [START_REF] Furko | The pragmatic marker -discourse marker dichotomy reconsidered -the case of 'well' and 'of course[END_REF][START_REF] Garric | Introduction à la pragmatique[END_REF], discourse particles [START_REF] Schourup | Common discourse particles in English conversation[END_REF][START_REF] Fischer | Approaches to Discourse Particles[END_REF], spoken particles [START_REF] Fernandez | Les particules énonciatives dans la construction du discours[END_REF][START_REF] Fernandez-Vest | Detachments for cohesion: toward an information grammar of oral languages[END_REF] and discourse connectives [START_REF] Roze | Lexconn: A french lexicon of discourse connectives[END_REF][START_REF] Lenk | Marking discourse coherence -Functions of discourse markers in Spoken English[END_REF].

Even though we can understand why a categorization task for DMs remain difficult given their poly-functionality and the various stages of functional multi-word expressions' lexicalization, scholars would usually agree on several main aspects. DMs' primary functions are described as being related to a relatively defined set of functions: turn-taking system, discourse relations cuing, discourse structuring, interpersonal relationships marking, speech management or politeness [START_REF] Fischer | Approaches to Discourse Particles[END_REF].

Recently, linguists have been interested in automatically identifying DMs for translation purposes. Some results have shown there were discrepancies between bilingual dictionaries translations and the semi-manual annotation ones for a given pair of DMs from two different languages [START_REF] Danlos | Traduction (automatique) des connecteurs de discours[END_REF]. Other works include The TextLink project 1 which is specifi-cally analyzing this aspect, by focusing on discourseannotated corpora to allow cross-linguistic studies of discourse. The corpus based method seems an adequate tool for caterorizing DMs as it unites a theoretical task consisting in setting parameters of definition variables with an empirical study on spontaneous speech corpora [START_REF] Crible | Mdma: un modèle pour l'identification et l'annotation des marqueurs discursifs "potentiels" en contexte[END_REF].

Data

The comparable corpora we used for this experiment were : the CoFee collection of corpora [START_REF] Prévot | A cup of cofee: A large collection of feedback utterances provided with communicative function annotations[END_REF] (made of CID [START_REF] Blache | Creating and exploiting multimodal annotated corpora: the toma project[END_REF], Map-Task [START_REF] Gorisch | Aix map task corpus: The french multimodal corpus of task-oriented dialogue[END_REF] and DVD [START_REF] Prévot | A cup of cofee: A large collection of feedback utterances provided with communicative function annotations[END_REF]) together with DECODA corpus for French ; Switchoard transcripts for English [START_REF] Godfrey | Switchboard: Telephone speech corpus for research and development[END_REF] ; and Academia Sinica conversational corpora (MCDC, MTCC, MMTC) for Taiwan Mandarin [START_REF] Tseng | Lexical coverage in Taiwan Mandarin conversation[END_REF]. We experimented with various subcorpora and across languages as illustrated in table 1 and with different potentials base units: syllables and letters for French; Characters, Pinyin (with and without tone) for Mandarin and only letters for English. . However, we add criterion during the extraction to try to avoid too many corpus specificities in a given language. Overall, all those corpora are truly conversational ones exhibiting the usual range of phenomena involved in fiercely spontaneous and interactional speech data. For all these corpora, the transcripts have been force-aligned at the word level.

Corpus

Concerning the transcription, a standard orthographic transcription had been adopted for thes corpora. The spokenb particles do have standardized written forms in French (euh, mh,...) and English (uh, um, mh...). In the Taiwan Mandarin corpora, discourse particles, discourse markers, and fillers were transcribed with capital letters to distinguish themselves from foreign words such as English. Fillers are transcribed according to their phonetic forms. For instance, UHN is equivalent to uhn in English; MHM is something that is frequently observed in Mandarin, but not in English. In particular, multi-syllabic fillers are transcribed in one single unit, separated by H, e.g. UHNHN. See [START_REF] Tseng | Lexical coverage in Taiwan Mandarin conversation[END_REF] for more details.

Methodology

Segmentation

We use non-supervised machine learning algorithms (based on Branching Entropy, already applied to written Mandarin [START_REF] Magistry | Unsupervized word segmentation: the case for Mandarin Chinese[END_REF][START_REF] Magistry | Unsupervised Word Segmentation and Wordhood Assessment[END_REF]) for segmenting our sequence of characters coming from the conversational transcripts into our base units (spoken tokens). There are currently better methods for segmentation, especially for Chinese Word Segmentation, but they require extremely large corpus that are not available for spoken language. Moreover, we were interesting in using the very same methodology on Mandarin, French and English with the idea in mind that the data set segmented in this same way across the languages could exhibit less divergence than being biased by the written form tradition of each language.

More precisely we use Eleve2 (Extraction de LExique par Variation d'Entropie -Lexicon extraction based on the variation of entropy) toolkit. This method is helpful for our study because it allows us to get units grounded on the same principles and therefore not being biased by written processing techniques or conventions employed in different languages. Such an approach results in a new starting point for the type of lexical experiments we will perform later. An illustration of new units for French and English created by our approach are illustrated by Table 2. A benefit of such an approach is that we do not have to define what an individual word or multi-word expression is. We have done our experiments both with traditional segmentation (space-based) and with the output of unsupervised segmentation (in which, for example, 'you-know', turned out to be a unit). For a related work see [START_REF] Dobrovoljc | Multi-word discourse markers and their corpus-driven identification[END_REF] which compare different association measures applied to discourse marker items.

While our unsupervised segmentation is very interesting to gather functional multi-words expressions into one unit as a result of the segmentation, it also presents some issues. For example, in French and English, it tends to split bound morphemes such as plural and gender marks as well as some verbal inflections. However, for our purpose of studying DM this feature should not be an issue.

French English Mandarin tu-vois you-know mh-mh uh-huh MHMHM ah-ouais oh-yeah 對 A c-est-vrai that-s-right,that-s-true et-euh , donc-euh and-uh, and-um et-puis, mais bon and-then comme-ça like-that dans-le, sur-le in-the il-y-a there-is Table 2: Examples of word like units created at segmentation stage ('-' in the units correspond to spaces in a traditional transcription) In these corpora, we approximate the notion of utterance by using Inter-Pausal Units defined by continuous stretches of speech in between pauses of at least 200 milliseconds. Therefore, both our lexical units and our utterances are objective as possible, only relying on speech timoing and on the transcript.

Quantitative measures

Scores We argue that conversationally speaking, words distribution -Discourse Markers in particularvaries significantly depending on the type of utterances they occur in. A first relevant method being easy to apply in the study of conversation consists in separating the shortest sentences from the longer ones. Besides, it is a known fact that DMs can be found at specific positions in utterances (initial, median, final) with the initial and final ones being the most frequent [START_REF] Aijmer | Understanding pragmatic markers: a variational pragmatic approach[END_REF][START_REF] Filippi-Deswelle | La relation dite de concession -Etude de Though, Although, Even Though et Even If antéposés en anglais contemporain[END_REF][START_REF] Fraser | Contrastive discourse markers in english? Discourse markers: Descriptions and theory[END_REF][START_REF] Muller | Discourse markers in native and non-native English discourse[END_REF][START_REF] Stali | A corpus driven study: the use of dis-course markers during Twitch's streams[END_REF][START_REF] Stali | Les marqueurs discursifs genre et du coup: une étude comparative de corpus[END_REF]. We propose to cross the two parameters mentioned above (type of utterance vs position in the utterance) to chart DMs.

Based on those two principles, we define a series of values aiming at characterizing quantitatively any form of the corpus (N : corpus size, S: number of tokens in short utterances, L: number of tokens in longer utterances, F all : frequency of the token, We also use some of those scores to filter the set of items under consideration. More precisely we tested different thresholds for relative frequency and dm-hood scores. For French and Mandarin, we made sure that the relative frequency threshold was met for at least two-subcorpora in order to avoid domain-based items that could come from Maptask or DECODA corpora. This was both impossible and unnecessary to do on Switchboard corpus which is a lot larger and already more diverse thematically.

Experiments

In the context of this work, we were interested in comparing the clustering (and its implicit discourse marker characterization) in two approaches: traditional tokenisation and unsupervised segmentation. After segmenting the data sets and computing the scores as described in the previous sections we processed as follows.

We filtered for relative frequency (threshold= 0.0005) and dm-hood (threshold= 0.3). Since we are at an exploratory stage of our work, those thresholds were chosen after inspection of results for a range of values for the both of them. We normalized all the resulting values, then applied PCA to the output and checked the explained variance ratio for deciding a number of principal components. The way DM are spread into the dimensions is illustrated for English DM in Figures 2 and3 for traditional and unsupervised segmentation It is not straightforward to label the resulting clusters. However, it is possible to identify some known groups of markers in the clusters. We attempted to use the same color for similar clusters in both tradition and unsupervised results. Concerning traditional segmentation, the green and the yellow clusters host typical feedback items and a relative good match across languages. The division into two clusters is probably due to the fact that the items in the green cluster, in addition to be used frequently isolated as feedback items, may also occur in initial position (which is less the case for the 'yellow' items). Similar structure is observed for the unsupervised segmentation. The 'blue' cluster corresponds to more evaluative and attitudinal items, at least for French and English. It is interesting to note that our very rough distributional measures are able to discriminate those items from the previous yellow and green clusters. We can see there is an adequate match between French and English but Finally the red cluster includes at least two kinds of items: discourse connectives but also filled pauses and even interactional management items (French 'hein' in the unsupervised case). This is probably due to a lack of discrimination capacity for forms occurring within longer utterances at different places. For example, we know that 'hein' tends to be more final but it is not enough to generate a specific cluster. Another explanation can be found in abandoned utterances. Those abandoned utterances typically end with a filled pause marker (French 'euh', English 'um,uh', Mandarin 'NEGE', 'NA'. This (frequent) phenomenon therefore tends to make those items more distributionally similar to final particles like hein. Similarly, it may be rather surprising to see contrast connectives ( mais / but / 可是) in those clusters. As mentioned above, this is probably due to unfinished utterances or utterance segmentation (based on pauses). However, in this cluster, there is a very satisfying match across the three languages.

Conclusion and Future Work

The exploration of DM spaces based on comparable corpora allowed us to show it remains possible to identify DM clusters, even through a cross-linguistic approach. The benefits of the unsupervised segmentation are not clear at this stage, specially for Mandarin data. However, the method and approach adopted tend to demonstrate that the traditional segmentation already benefits from adapted transcription convention which includes rules for grouping specific words together. However, we believe it might be interesting to dig further in how much can be achieved without too many supervisions and bias from written resources. In the future, our first objective is to deeper scrutinize the elements in the structure of the Mandarin utterances which prevents DMs to be better clustered correctly with French and Mandarin items.

Figure 1 :

 1 Figure 1: Comparative lexical growth (French) between traditional segmentation and Branching-entropy (x-axis : Coverage of the lexicon ; y-axis: Coverage of the corpus) segmentation

  F short : frequency of the form in short utterances;F long :frequency of the form in non-short utterances, F ini :frequency of the form in initial position of longer utterances, F f in :frequency of the form in final position of longer utterances • F all N : relative frequency • F short S : relative frequency of the form within short utterance forms • F long L : relative frequency of the form within longer utterance forms • F short

  F all : tendency to occur in short utterances• F short +Fini+F f in F all: a sort of "dm-hood" of the form (tendency to occur in all canonical DM and interactional markers positions)• Fini F long : tendency to occur in initial position within longer utterances• F f in

F

  long : tendency to occur in final position within longer utterances

Figure 2 :

 2 Figure 2: English DM plotted on the 2 principal components, based on traditional segmentation

Figure 4 :

 4 Figure 4: Cluster (one per color) grounded on traditional segmentation

Figure 5 :

 5 Figure 5: Cluster (one per color) grounded on unsupervised segmentation

Table 1 :

 1 Corpora used in the study Some of those corpora are truly comparable while it is more debatable for others. MTR + MTX on French and MTCC for Mandarin are perfectly comparable since they have been recorded using the same protocol. CID for French and MCDC + MMTC are also very similar by nature. English Switchboard is perhaps a bit different in principle but in practice, it shares most of the features present in the previous corpora. The less similar of the set is French DECODA since it is recorded in a specific context (call center of Paris public transportation enquiries number)

		# Tokens # pseudo-Utterances
	CID	125 619	13 134
	MTR	42 016	6 425
	MTX	36 923	5 830
	DVD	64 023	7 989
	DECODA (part)	580298	88 982
	French	851202	122 360
	MCDC	316 422	61 000
	MTCC	122 200	26 000
	MMTC	34 500	8 300
	Mandarin	472 000	95 000
	SWBD (English) 2 967 028	391 592

http://textlinkcost.wixsite.com/textlink

https://github.com/kodexlab/eleve


Pierre Dragicevic

Alejandro Ribes

C Hurter

Image-Based Information Visualization Techniques

Keywords: CCS Concepts, Human-centered computing → Human computer interaction (HCI), Interaction techniques, Interactive systems and tools

While many data exploration techniques are based on automatic knowledge extraction, other tools exist where the user plays the central role. This presentation will report actual use-cases where the user interactively explores datasets and extracts relevant information. These techniques must be interactive enough to insure flexibility data exploration, therefore image-based algorithms propose a suitable solution. These algorithms, processed in parallel by the graphic card, are fast and scalable enough to support interactive big data exploration requirements.

Introduction

Our society has entered a data-driven era, in which not only enormous amounts of data are being generated every day, but also growing expectations are placed on their analysis [TC05]. Analyzing these massive and complex datasets is essential for making new discoveries and creating benefits for people, but this remains a difficult task; most data have become simply too large to be displayed and often have too short lifespan, i.e. they change too rapidly for a classical visualization or analysis methods to handle them. This is particularly important for movement data, such as traffic data on roads or in airspace, because of their intrinsic time-dependent nature. Machine learning with distributed systems heralds the solution to address the big data issues and efficient knowledge extraction. Nevertheless, alternatives do exist where humans play a central role with the usage of interactive visualization systems [HK12]. With regards to this data deluge, what remains relatively constant is our own cognitive ability to make sense of the data and take reliable and informed decisions. Information Visualization (InfoVis) is defined as 'the use of computer-supported, interactive, visual representations of abstract data to amplify cognition' [START_REF]Readings in Information Visualization: Using Vision to Think[END_REF]. InfoVis provides the scientific support to leverage user analytical capabilities with interactive visualization.

The presentation relies on a new generation of high-performance visualization paradigms, such as Image-Based visualizations (fast parallel GPU computation) to gain new insights from multidimensional data sets. The graphic card is not only used to display information but also to support interaction [Hur15]. This data exploration paradigm is at the crossroads of Information Visualization, Visual Analytics, Computer Graphics and Human-Computer Interaction. the following questions. How to depict large data (data visualization), how to do so in an efficient way? How to interact efficiently with large data sets, and how to do it in a way that fosters discoveries?

As scientific challenges, image based techniques try to answer

As Technical challenges, Image-Based techniques focus on algorithms working in the graphic space (Pixel-Based). This consists of two steps: first, a data representation is built using existing visualization and interaction techniques; then the resulting image undergoes only graphical transformations using image processing techniques, mostly performed by the graphic card so called GPGPU techniques (General-Purpose computing on Graphics Processing Units) [OLG * ] . These techniques will be applied at every stage of the data processing pipeline: data collection, cleaning, wrangling, sorting, exploring, knowledge extraction. This presentation will depict this innovative approach with Image/Pixel-Based Techniques.

Presentation outlines

Every section will be illustrated with numerous demos and videos to make the presentation as concrete and as practical as possible.

Introduction of Image-Based techniques

The Image-Based approach takes advantage of changes in the bottlenecks of computer graphics: since data storage and memory limitation is becoming less and less of an issue [Sut12], we can plan to reduce computation time by using memory as a new tool to solve computationally challenging problems. Furthermore, even if graphic cards were initially developed to produce 2D/3D views close to photo-realistic images, their power has also been used to perform parallel computations (so called GPGPU techniques).

Principle of this new data exploration principle was introduced by McDonnel et al. [ME09] and further extended by Hurter [Hur15].

Part II : focus on Image-Based visualization techniques to address scalability issues

This part of the presentation will mostly focus on clutter removal in dense visualizations. Many improvement have been recently done with visual aggregation techniques also called edge bundling [LHT17]. While these techniques mostly apply on graph or trail sets, they open interesting opportunities to gain a better understanding of dense and complex visualizations.

Part III : focus on interactive Image-Based technique to address scalability issues

During this presentation, we will investigate how to build a system with low latency to foster big data exploration. GPU usage and astute memory management with Image-Based techniques will address these latency issues (e.g. response time to a query). As such, Image-Based techniques will go beyond the interactive data exploration paradigm [START_REF]The Fourth Paradigm: Data-Intensive Scientific Discovery[END_REF] by investigating the association of interactions and visualizations to support direct manipulation of datasets [Shn83].

Part IV : Application domain examples

During this presentation, we will present a review of exiting Image-Based interactive visualization techniques and algorithms with concrete application domain use-cases. We will show and explain how to interactively explore large dataset (one day of recorded aircraft trajectories [HTC09] (figure 2

Figure 1 :

 1 Figure 1: Mixed reality data visualization and manipulation.

Figure 2 :

 2 Figure 2: This image shows air traffic visualization with edge bundling simplification technique [HPNT18].

  2.5. Part V : Conclusion and Research perspectives This section will conclude the presentation with an open discussion of future research direction and opportunities for Image-Based algorithms. Bio: Christophe Hurter is professor at the Interactive Data Visualization group (part of the DEVI team) of the French Civil Aviation University (ENAC) in Toulouse, France. He is also an associate researcher at the research center for the French Military Air Force Test Center (CReA). In 2010, he received his PhD in Computer Science from the Toulouse university and in 2014 he got his HDR (Habilitation a Diriger des Recherche). His research covers information visualization (InfoVis) and human-computer interaction (HCI), especially the visualization of multivariate data in space and time. He also investigate the design of scalable visual interfaces and the development of pixel/image-based rendering techniques. Throughout his career he have been involved with several projects including: large data exploration tools, graph simplifications (edge bundling), paper based interactions, augmented reality, 3D visualization...