Ricardo Carlini Sperandio

Simon Malinowski

Laurent Amsaleg

Romain Tavenard

Time Series Retrieval using DTW-Preserving Shapelets

Dynamic Time Warping (DTW) is a very popular similarity measure used for time series classification, retrieval or clustering. DTW is, however, a costly measure, and its application on numerous and/or very long time series is difficult in practice. This paper proposes a new approach for time series retrieval: time series are embedded into another space where the search procedure is less computationally demanding, while still accurate. This approach is based on transforming time series into highdimensional vectors using DTW-preserving shapelets. That transform is such that the relative distance between the vectors in the Euclidean transformed space well reflects the corresponding DTW measurements in the original space. We also propose strategies for selecting a subset of shapelets in the transformed space, resulting in a trade-off between the complexity of the transformation and the accuracy of the retrieval. Experimental results using the well known UCR time series demonstrate the importance of this trade-off.

Introduction

Time series data is massively produced * by millions of users, worldwide, in domains such as finance, agronomy, health, earth monitoring, weather forecasting, multimedia, etc. Due to the advances in sensor technology and its proliferation, applications may produce millions to trillions of time series per day, making time series data-mining further challenging.

Most time series data-mining algorithms rely on the Dynamic Time Warping (DTW) [ ] measure at their core, which proves to return high-quality results, but which is also very costly to compute [ ]. Many researchers have attempted to reduce its cost in order to run it at scale. Numerous mart optimizations, diverse lower bounds and other techniques have been applied [ ], however, the quest for processing extremely large collections of time series is still active.

This paper focuses on the task of time series retrieval according to the DTW measure. The classical scenario for this task is the following: let 𝜏 be a test time series (query), retrieval is about finding a time series in a dataset 𝒯 which is the closest one to 𝜏 with respect to the DTW measure. In other words, it is finding 𝑇 * , such that:

𝑇 * = arg min 𝑇𝑖∈𝒯 𝐷𝑇 𝑊 (𝜏, 𝑇 𝑖 ) ( )

A traditional way to identify 𝑇 * relies on the brute force DTW computation between 𝜏 and all series of 𝒯 . This approach is not tractable when dealing with long time series or huge data sets. Hence, approximated methods are preferred, aiming at reducing the retrieval costs while being as accurate as possible.

We propose here an approximate time series retrieval approach based on the shapelet transform. The basic idea of the proposed approach is to transform the time series of the dataset into vectorial representations such that a Euclidean search can then be efficiently applied to retrieve the nearest neighbour of the transformed query. Of course, the transformation needs to be carefully designed so that the approximate search is accurate enough. Another crucial point is related to the computing cost of the transformation. At test time, the query needs to be first transformed before being compared with transformed time series of the dataset. Hence, the transformation should not be too costly.

In this paper, DTW-preserving shapelets [ ] are used to transform time series to a vectorial representation. This transform is such that the relative Euclidean distance in the transformed space well reflects the original DTW measurements. They are hence well adapted to our task. Transforming time series has a cost, but it can be traded-off against the accuracy of the retrieval by selecting a varying number of shapelets for computing the vectorial representations. Three shapelet selection strategies are proposed in this paper.

In addition, we propose a shapelet selection procedure in order to identify and rank shapelets that are more suited to the retrieval task (via a dedicated measure). This step has two purposes: reducing the number of shapelet for the transformation of the query (to save computing time), while keeping a good trade-off with accuracy of the retrieval.

The remainder of this paper is organized as follows: Section presents related work. The proposed Learning DTW-Preserving Shapelet Retrieval (DPSR) method is presented in Section . Section presents experimental results and conclusions and future work are presented in Section .

Related work

Various similarity measures have been used for time series retrieval, and excellent surveys provide a good coverage of their pros and cons [ , ]. In a nutshell, the straightforward Euclidean distance is not robust to distortions and time shifts, and is hence not very appropriate for time series. Approaches based on the DTW are much preferred because it is able to find the optimal alignment between two given time series, thus coping with local distortions along the time-line. DTW, however, is costly to calculate because of its quadratic time complexity.

Several approaches have therefore been proposed in order to speed up the computation of DTW, including restricting to the diagonal of the distance matrix [ , ] The Piecewise Aggregate Approximation (PAA) [ , ] has been used to build iSAX [ ], one of the most famous time series indexing system. PAA is a transformation that divides time series into smaller pieces and create an approximation of each piece. This transformation is at the core of iSAX, which was shown to be very accurate and fast for retrieving time series. However, it is based on the euclidean distance and not the DTW.

We propose a retrieval scheme based on a transformation preserving the DTW. This transformation makes use of shapelets. Shapelets were introduced by Ye and Keogh in [ ] for time series classification. The underlying intuition behind shapelets is that time series belonging to one class are likely to share some common subsequences. Shapelets were therefore originally defined as existing subsequences of time series that best discriminate classes. Hills et al. then build on the idea of shapelets by proposing the Shapelet Transform [ ]. In this approach, each time series is transformed into a vector whose components represent the distances between the time series and the shapelets. Transforming a time series into its vectorial representation requires to slide each shapelet against that time series in order to find the best matching locations and then compute the corresponding distances. The cost of shapelet transform is therefore highly dependant on the number of shapelets that are used to create vectorial representations. Instead of using existing subsequences as shapelets, Grabocka et al. in [ ] propose to rather forge the shapelets by learning the subsequences that minimize a classification loss. Shapelets have also been used for unsupervised tasks and not only for classification. In [ ], Lods et al. learn shapelets such that the resulting vectorial representation preserves as well as possible the DTW distance between raw time series, targeting time series clustering. In [ ], Zakaria et al. extract the shapelets dividing the set of time series into well separated groups.

Time series retrieval with DTW-preserving shapelets

In this section, we detail our approach for time series retrieval under DTW. This approach builds on (i) the shapelet transform paradigm and (ii) the DTWpreserving shapelets that are proposed in [ ]. We first quickly review these building blocks before presenting the design of our retrieval scheme.

.

Background on shapelets and shapelet transform

A shapelet 𝑆 = 𝑠 1 , . . . , 𝑠 𝑙 is a temporal sequence (that can be extracted from existing time series, or learned). The distance between 𝑆 and a time series 𝑇 = 𝑡 1 , . . . , 𝑡 𝐿 is defined as:

𝑑(𝑇, 𝑆) = min 1≤𝑗≤𝐿-𝑙+1 ⎯ ⎸ ⎸ ⎷ 𝑙 ∑ 𝑖=1 (𝑠 𝑖 -𝑡 𝑖+𝑗-1 ) 2 ( )
In .

Learning DTW-preserving shapelets

In [ ], Lods et al. propose to learn a set of shapelets such that the shapelettransform representation preserves as well as possible the original DTW measure.

The shapelets are learned such that Euclidean distance in the transformed space approximates the DTW. Such shapelets can hence be used for unsupervised tasks, that is, where no labels are available. The approach proposed by Lods et al. relies on minimizing the loss:

ℒ(𝑇 𝑖 , 𝑇 𝑗 ) = 1 2 ( DTW(𝑇 𝑖 , 𝑇 𝑗 ) -𝛽 ⃦ ⃦ 𝑇 𝑖 -𝑇 𝑗 ⃦ ⃦ 2 ) 2 , ( )
where 𝛽 is a scale parameter, learned. The overall loss for a dataset 𝒯 of 𝑁 time series is given by:

ℒ(𝒯 ) = 2 𝑁 (𝑁 -1) 𝑁 ∑ 𝑖=1 𝑁 -1 ∑ 𝑗=𝑖+1 ℒ(𝑇 𝑖 , 𝑇 𝑗 ).
( )

The minimization of this loss is done via a stochastic gradient descent with respect to 𝛽 and 𝒮. Once the shapelets and the parameter 𝛽 are learned, they can be used to transform every time series in a Euclidean vector.

. Transforming times series for retrieval under DTW

In this paper, we propose a retrieval scheme based on transforming time series into high-dimensional vectors. Its offline step transforms all time series of the data set into their vectorial representation, as explained above. Its online step uses a query to probe the dataset. To do so, the vectorial representation of the query is first determined. Then, Euclidean distances to the transformed times series of the dataset are computed. This results in a list of transformed time series that are ranked according to their proximity to the transformed query. The nature of the transformation that is using DTW-preserving shapelets is such that this ranking in the transformed space is an approximation of the ranking that would be produced in the original space according to the DTW measure. However, this approximate ranking is obtained much faster, as Euclidean measurements are cheaper to obtain compared to DTW measurements. Two ways to process that ranked list of time series in the transformed space can be designed: (a) the original time series associated to the top-ranked in this list is considered to be the nearest neighbour of the query, or (b) the true DTW is computed between the original untransformed query and the original version of the first few elements of that list in order to refine the search. (a) puts a lot of pressure on the quality of the shapelet transform because the nearest time series under DTW has also to be the closest in the Euclidean space, and this for any time series in the dataset and any query. Odds of degrading quality in comparison to what the true DTW would determine are high, but this method is extremely fast. In contrast, (b) is more demanding because more DTW are computed, but it is also returns better quality results as more time series are scrutinized. In this case, it matters that the closest time series under DTW belongs to these first few elements, instead of being ranked first.

Overall, two properties are important for an approximate retrieval scheme: (i) the complexity of the transformation should be small to reduce the overhead induced by transforming the query and (ii) the true nearest neighbour has to be as close as possible to the first element of the list of approximate nearest neighbours. In other words, the transformation should preserve the ranking.

The retrieval scheme proposed in this paper focuses on these two important properties. The use of DTW-preserving shapelets ensures that the Euclidean search in the transformed space mimics the search in the original space.

.

Ranking and selecting shapelets

The transformation of the query before searching in the transformed space is costly. Indeed, the computation of one coordinate of the transformed vector requires sliding a shapelet over the query 𝜏 and finding the best match. It is a costly operation for long time series and when the number of learned shapelets is high. We hence focus in this section on selecting and ranking a subset of shapelets most suited to the retrieval task. General considerations about high-dimensional representations suggest that components of vectors might not all be equally useful. This well known observation led to designing dimensionality reduction methods performing feature selection. Feature selection algorithms typically use (i) an evaluation metric to compare different feature subsets, (ii) a strategy for building consecutive subsets and (iii) a stopping criterion [ , , , ]. The characteristics that we use to design our shapelet selection algorithm are described hereafter. Selecting a few appropriate shapelets saves computations at transform time without degrading significantly the quality of the approximation. Algorithm is the corresponding pseudo-code.

Evaluation metric to compare shapelet subsets To compare the performance of different shapelet subsets, we need a groundtruth based on the true DTW between time series. To build that groundtruth, the DTW between all time series pairs in the training set is computed and we record for each time series the identifier of its nearest-neighbour. This is done once only, off-line.

We use a -fold validation setup in order to evaluate the performance of a subset. For one transformed time series in the validation set (query), we rank all the transformed time series in the training set according to their Euclidean distance to the query. It is therefore possible to determine at which rank the true -nearest neighbor time series is. Repeating this operation for all the validation time series and for all the folds amounts to building an histogram of the rank at which the true nearest-neighbour appear. This histogram can also be interpreted as the empirical probability of observing the true -nearest neighbor time series at any particular rank after the transform. This histogram can therefore be considered to be a probability density function (after a proper normalization though). From this PDF, it is straightforward to construct its natural counterpart which is the CDF, the cumulative distribution function, and to compute the associated area under the curve (AUC). We consider this AUC value as the performance measure to evaluate the quality of a shapelet subset. The higher that AUC, the better the shapelet subset. This metric is well adapted to the task of nearest-neighbour retrieval as it favors high ranking of the true nearest neighbor in the approximated list.

Shapelet subset selection

To select the best subset of shapelets, an exhaustive selection method can be applied. However, in this case, the computational cost is prohibitively high. We have chosen a greedy-based forward selection method, that is classically used in the feature selection domain.

Our procedure to select the best shapelet subset begins with an empty list. Then it iteratively adds shapelets that best improve the quality of the subset (by measuring the resulting AUC), one by one, until a stopping criterion is met (the different stopping criterion we used are described in the following).

Stopping criterion

We define three different stopping criterion, that determine when to stop adding shapelets to the current set of selected shapelets:

. Global maximum (𝐷𝑃 𝑆𝑅 𝑔 ): Shapelets are added one by one until no more shapelets are available. At the end, the subset that leads to the best overall AUC is selected. . 𝑡𝑎𝑛(𝑥) < 1 (𝐷𝑃 𝑆𝑅 𝑡 ): We compute the normalized slope between the AUC value of the current selected subset and the one obtained by adding the shapelet that best improves the AUC. If this slope is less than , then the shapelet selection is stopped.

. by the global maximum one (𝐷𝑃 𝑆𝑅 𝑔 ). Note that for the global maximum criterion the selection process cannot be stopped before having ranked and selected all shapelets one by one, contrary to the two other criteria for which the process can be stopped as soon as the criterion is reached. We illustrate in the experiments the trade-off between dimensionality and accuracy induced by these criteria.

Experiments

This section presents an experimental evaluation of our DPSR approach. The trade-off between accuracy and computation complexity is discussed. Performance of DPSR is compared to Piecewise Aggregate Approximation (PAA) [ , ] and LB_Keogh lower bound (LB_Keogh) [ ]. We start with our experimental setup.

. Experimental setup

We consider the datasets from the well known UCR-UEA Time Series Archive [ ]. For all these datasets, we use test sets series as queries. Before running any experiment, we built a full DTW-based groundtruth. The true DTW measurements between all time series pairs in each of the families are determined. From these measurements, it is straightforward to derive the nearest-neighbour of each time series.

The feature selection algorithm for DTW-preserving Shapelets that is presented in this paper is evaluated against two solid competitors that are (i) the LB_Keogh lower-bound used to accelerate the computation of the true DTW (used in the UCR Suite framework) and (ii) the PAA approach (on which iSAX is based).

Our experiments are performed on a -core . GHz Intel Xeon ES-with GB of memory. All algorithms and structures are implemented in Python , Cython and NumPy. Although the machine has cores, the only operations using parallelism are the distance computations handled by NumPy during the course of each experiment -no other parallelism is enforced. The tslearn [ ] toolkit was used for the computation of PAA and LB_Keogh.

For each family in the UCR archive, a set of DTW-preserving shapelets is learned using the algorithm proposed in [ ], with default parameters. To learn high-quality shapelets, , iterations of the gradient descent algorithm are performed. In addition, two sets of shapelets are learned for each family of time series, and the one with the smallest overall loss is selected.

. Dimensionality versus accuracy: reaching a plateau

This first experiment aims at comparing the performance of PAA and DPSR for time series retrieval. This comparison is performed in terms of trade-off between AUC and the dimensionality of the transformation. Transformations range from very rough approximations (few shapelets, few pieces for PAA) to finer grain representations. For consistency, we compared PAA and DPSR for the same The results for Beef are more contrasted: when the time series is split into more than pieces, PAA outperforms the shapelet based approach. Please note that these figures show quality measures for the first dimensions only. Considering more than dimensions does not provide any useful extra information for these datasets.

Table compiles the comparison of PAA and the approach based on DPSR for all time series by counting the number of times each method performs better than the other, for dimensionalities , , and . We also report the average AUC values at these dimensionalities for the two different approaches. Overall, this table shows that DPSR consistently outperforms PAA for all dimensionalities. We can also observe that both methods seem to reach an AUC plateau, sooner for PAA than it is for DPSR.

For DPSR, this plateau highlights the importance of selecting shapelets. and that a lot of them do not contribute significantly to enhancing the resulting vectorial representation. Generating so many shapelets is wasting computing resources at transform time because many shapelets have to be slid, some in pure waste. This is particularly important at query time, as reducing the cost of transforming the query time series is paramount.

.

Shapelet selection strategies for DPSR

In Section . , three strategies for stopping aggregating selected features were presented. We now evaluate their effectiveness, which is a trade-off between their accuracy in terms of AUC and the transformation cost they cause. Typically, small subsets allow for very fast transforms (just a few shapelets need to be slid at test time) but quality is typically low, whereas in contrast larger subsets improves AUC performance but cause more expensive transform operations.

To observe this trade-off, we selected by cross-validation on the training sets of each dataset the best shapelet subset for the three different stopping criterion. We then used these subsets at test time for approximate retrieval. The AUC performance of the three stopping strategies has been computed on the considered datasets. The average AUC value is given in Table , together with the average number of selected shapelets. The last column of Table (DPSR 𝑓 ) corresponds to the case where no shapelet selection is performed (i. e., the whole shapelet set learned beforehand is used).

We can observe that the three proposed criteria generate a trade off between accuracy of the retrieval (AUC) and computational time of the transform (linear with the number of shapelets). DPSR 𝑡 , the most aggressive strategy, selects very few shapelets (a little bit more than , on average) for an average AUC of 0.906. DPSR 𝑔 , the most conservative strategy uses on average shapelets, but the corresponding quality improvement is quite small: it goes from .

to . . This is a clear illustration of the trade off, also exemplified by the DPSR 𝑙 strategy, which is in between these two strategies.

We can also observe the importance of the feature selection itself: when no selection is made (DPSR 𝑓 ), the average AUC is slightly lower than for DPSR 𝑔 and the corresponding average number of shapelets used is almost tripled.

.

Feature selection versus constrained feature learning

The previous experiment demonstrated that only a small fraction of the learned shapelets are truly useful because they significantly contribute to the quality of wins, in cases, DPSR needs fewer dimensions than PAA. It means that in cases, DPSR needs more dimensions than PAA to provide better results. The dual point of view is also insightful: PAA outperforms the DPSR 𝑡 method in cases, but all PAA transformations need more pieces than DPSR 𝑡 . Not only DPSR wins more frequently than PAA, but when it wins, it is with shorter representations. This is also true for DPSR 𝑙 and DPSR 𝑔 . The average AUC value for PAA is equal to .

which is worse than the average AUC value of the DPSR approaches. Against LB_Keogh, DPSR is only worse for the DPSR 𝑡 criterion which leads to a very small representation. The average value of AUC for LB_Keogh is .

. It is better than DPSR 𝑡 , but not than DPSR 𝑙 and DPSR 𝑔 .

An important observation is that, unlike LB_Keogh and PAA, DPSR allows comparison between time series of different lengths.

.

Search costs

So far, only quality comparisons have been done. We observe now the computational costs of the approaches discussed here. Additional experiments were performed for recording search times when the dimensionality of the representations for DPSR and PAA gradually increase. Search times for Gun_Point and Beef are plot on Figure (the plots show only results for their first dimensions), and the average search times for the full UCR archive is on Figure c. These figures also show the time it takes to compute only the envelopes of time series for LB_Keogh. That process, coupling LB_Keogh and DTW is guaranteed to find the same time series as the one indicated in the groundtruth. The quality of any approximate search scheme can only be equal or lower. But the time for solely computing the LB_Keogh value on all time series is the absolute minimal cost the real LB_Keogh+DTW could have. These figures show that the time for computing envelopes with LB_Keogh is fixed, which is normal. They also show that PAA is the fastest approach. Its underlying principles are simple and cause light computations, the search times increasing slightly with the dimensionality. The time taken per search for DPSR is also increasing with the number of dimensions: there are more and more shapelets to slide, and distance computations are more demanding. Three remarkable signs are placed on the search time plot for the DPSR approach. They refer to the search times observed when the number of shapelets in use correspond to what DPSR 𝑡 , DPSR 𝑙 and DPSR 𝑔 determined.

Conclusions and future work

In this work, we have presented an approach for time series retrieval based on learning DTW-preserving shapelets (DPSR). This approach first transforms time series into high dimensional vectors such that the Euclidean distance between the vectors in the transformed space well reflects the DTW measurements in the original space. This targets preserving the quality of time series retrieval compared to the DTW. Relying on Euclidean distances is more efficient than computing the costly DTW measures. This targets computational efficiency, facilitating time series retrieval at scale.

In order to cope with with larger scales, we also propose different shapelet selection strategies to trade complexity of the retrieval against accuracy. Even the most aggressive strategy (that select very few shapelets) provides reasonable accuracy. Experimental results show the importance of this feature selection.

This work is a first step into the design of a time series indexing system. At very large scale, the many high dimensional vectors representing time series could be inserted into an index, avoiding the exhaustive Euclidean distance calculations, further improving performance. Such an approach can be advantageously used for anytime indexing of time series.

  or the design of lower bounds. The most popular lower bound is the LB_Keogh lower bound (LB_Keogh) [ ]. It first needs to rescale each time series to the same length and then it builds their envelopes by accounting for their maximum and minimum values inside a sliding window. The distance between two time series returned by LB_Keogh corresponds to the areas of their envelopes that do not overlap. In [ ], Rakthanmanon et al. proposed the UCR Suite framework which includes several acceleration approaches that can be combined in order to index time series under the DTW measure. Recently, Tan et al. in [ ] proposed an adaptation of Priority Search K-means to index time series embedded in a space induced by DTW. Interested readers should read three comprehensive reviews [ , , ].

Figure

  Figure shows the AUC values at each iteration of the shapelet selection algorithm on the Ham dataset (from the UCR-UEA archive [ ]). For this dataset, it has been learned shapelets using Lods et al. approach (𝐷𝑃 𝑆𝑅 𝑓 ). We can see on this figure the impact of the different criteria. If the tangent criterion (𝐷𝑃 𝑆𝑅 𝑡 ) is used, then the selection process would end with shapelets (Fig. b, which zooms on the first dimensions), while would be selected by the local maximum criterion (𝐷𝑃 𝑆𝑅 𝑙 ) andby the global maximum one (𝐷𝑃 𝑆𝑅 𝑔 ). Note that for the global maximum criterion the selection process cannot be stopped before having ranked and selected all shapelets one by one, contrary to the two other criteria for which the process can be stopped as soon as the criterion is reached. We illustrate in the experiments the trade-off between dimensionality and accuracy induced by these criteria.

  Fig. : (a) Impact of the three different stopping criterion in terms of number of selected shapelets for the Ham dataset. (b) Zoom on the first dimensions of (a).

Fig

  Fig. : Comparing DPSR and PAA for two specific time series. The ability to retrieve the correct time series from the groundtruth is represented by the resulting AUC.

Fig. :

 : Fig. : Average Search Times for two specific time series and for the full UCR Archive. Varying dimensionality.

  other words, Euclidean distances between 𝑆 and every subsequence of 𝑇 (of length 𝑙) are computed and only the best match (minimum distance) is kept. The shapelet transform of a time series was proposed in [ ] for time series classification. It is a two step process: (i) selecting an appropriate set of shapelets 𝒮 = {𝑆 1 , . . . , 𝑆 𝐾 } and (ii) transforming time series into Euclidean vectors. During the second step, each time series 𝑇 is transformed into a vector 𝑣

1 , . . . , 𝑣 𝐾 such that 𝑣 𝑖 = 𝑑(𝑇, 𝑆 𝑖 ), 1 ≤ 𝑖 ≤ 𝐾, where 𝑆 1 , . . . , 𝑆 𝐾 are the shapelets that were selected during the first step. The dimensions of 𝑣 represent the distance between 𝑇 and the shapelets of 𝒮. Such representations of time series are then used to feed a classifier, when the targeted application is classification.

  Local maximum (𝐷𝑃 𝑆𝑅 𝑙 ): The shapelet selection is stopped as soon as adding a shapelet does not improve the AUC value.

	Algorithm Shapelet ranking and selection

: input: 𝒮 {Set of learned shapelets}, 𝒯 {Time series train set} : output: 𝒮𝑠 {Ranked list of selected shapelets} : 𝒮𝑎 ← 𝒮 {Shapelets available to evaluate, initially all} : 𝒮𝑠 ← ∅ {Shapelets selected, initially empty} : 𝑠𝑡𝑜𝑝 ← FALSE : repeat : 𝑠𝑐𝑜𝑟𝑒 𝑏 ← -1 : for all 𝑆 ∈ 𝒮𝑎 do : 𝒮𝑡 ← 𝒮𝑠 ∪ 𝑆, 𝑠𝑐𝑜𝑟𝑒 ← AUC value of the set 𝒮𝑡 : if 𝑠𝑐𝑜𝑟𝑒 > 𝑠𝑐𝑜𝑟𝑒 𝑏 then 𝑠𝑐𝑜𝑟𝑒 𝑏 ← 𝑠𝑐𝑜𝑟𝑒, 𝑆 𝑏 ← 𝑆 : end for : 𝒮𝑠 ← 𝒮𝑠 ∪ 𝑆 𝑏 , 𝒮𝑎 ← 𝒮𝑎 ∖ 𝑆 𝑏 : if Stopping criterion is met then 𝑠𝑡𝑜𝑝 ← TRUE : until 𝑠𝑡𝑜𝑝 = TRUE

Table :

 : Comparing DPSR and PAA for the full UCR Archive at different dimensionalities. Number of times each method outperforms the other in terms of AUC is reported together with the average AUC values over the datasets.

dimensionality. Figure illustrates the resulting AUC values for two specific data sets, Gun_Point and Beef. With Gun_Point, DPSR outperforms PAA for all dimensionalities.

  It indicates that the original approach by Lods et al. creates far too many shapelets,

	DPSR𝑡 DPSR 𝑙 DPSR𝑔 DPSR 𝑓
	Avg. AUC .	.	.	.
	Avg. Dim.	.	.	.	.
	Table : Average AUC and dimensionalities for feature subset selection strategies.

Acknowledgments

The current work has been performed with the support of CNPq (Conselho Nacional de Desenvolvimento Científico e Tecnológico), Brazil (Process number / -). The authors are grateful to the TRANSFORM project funded by STIC-AMSUD ( -STIC-) for the partial financial support to this work.

DPSR vs. PAA DPSR vs. LB_Keogh # wins for DPSR # wins for PAA # wins for DPSR # wins for LB_Keogh DPSR𝑡 DPSR 𝑙 DPSR𝑔 Table : Comparing DPSR, PAA and LB_Keogh with their best parameters (learned by cross-validation). We report here the number of times each method outperforms the other in terms of AUC. the retrieval. We show here that it is the combination of the learning stage and the feature selection strategy that leads to such behaviour. For that purpose, we compare the AUC performance of the proposed retrieval scheme (DPSR 𝑡 and DPSR 𝑙 ) with a method where the same number of shapelets is directly learned using the algorithm presented in [ ].

We used the previous experiment to record for each dataset how many shapelets the DPSR 𝑡 and DPSR 𝑙 selected. Then, we ran the shapelet learning algorithm of [ ] using that number of shapelets (for each dataset and for each DPSR strategy). We know from the previous experiments that the average AUC for DPSR 𝑡 over all the datasets is 0.906, with using . shapelets on average. When directly learning that same number of shapelets, then the average AUC over all datasets is 0.866. Furthermore, considering individually the families of time series, the DPSR 𝑡 strategy performs better than the one directly learning the appropriate number of shapelets in cases (out of ). Same conclusions can be drawn with DPSR 𝑙 . The average AUC of DPSR 𝑙 is .

, whereas the AUC obtained when directly learning the same number of shapelets is equal to 0.905. The DPSR 𝑙 strategy wins times out of in that case. These results indicate that it is worth spending more time offline to learn a huge set of shapelets and then selecting the more appropriate. This is better than trying to save computational time by learning less shapelets. Also, our feature selection strategy allows to decide on the number of shapelets in a data driven fashion, contrary to a purely heuristic approach.

.

Comparing methods at their best

In this experiment, we compare the respective performance of DPSR, PAA and LB_Keogh when their parameters (number of segments for PAA, subset of shapelets for DPSR and window length for LB_Keogh) are cross-validated on the train set. The results comparing the performance of (i) DPSR and PAA methods and (ii) DPSR and LB_Keogh are given in the


Taoufik Gouma

The Impact of the Phonological System of some European Languages on Arabic

Keywords: Arabic, phonology, phonetics, colonial languages, name transcription, Latin alphabet

In this article I show one of the important linguistic impacts of some foreign languages on Arabic. Besides the setting up of many linguistic systems such as the second official language of the country, bilingualism, etc. colonialism had also affected the way Arabic countries transcribe Arabic names using the Latin alphabetical system. We are going to show here some of the most important aspects of this impact and also some related problematic issues. The countries concerned with this study are those of the Maghreb; Morocco, Algeria and Tunisia (French Speaking Countries or FSC henceforth) and the countries of the Golf; Saudi Arabia and the United Arab Emirates, including Egypt (English Speaking Countries or ESC henceforth).

A Brief History about Colonialism in the Arabic Countries.

Colonialism is the building and maintaining of colonies in one territory by people from another territory. It is something which has always existed through history, but its reasons are different. People in the first era of existence used to move from one area to another looking for shelter, food, water, etc. Later, by the development of life and its needs, the reasons changed. From the 14 th century, powerful countries, such as Spain and England, started to look for other lands in order to acquire more lands, more power and more richness. This process had of course different impacts (social, political, economic, religious, etc.) on the native people of the settled countries. The most important impact which is of concern here is the linguistic one during the colonial period of some Arabic countries.

In order to facilitate their settlement, the colonial countries had, of course, the obligation to acquire the language of the countries they were planning to colonize. One of the most important methods which helped to do this is what is known as the orientalist expeditions in the 18 th century. These expeditions, according to some historians (Edward, S. 1978), in addition to the will to understand the Arabic world, its culture, religion, language (more particularly the Arabic dialects spoken in those countries) and its grammar, were also used to facilitate the colonization process.

2 The Fields of the Linguistic Impact.

One of the most important linguistic impacts of colonization is the establishment of many systems using the colonial languages. Two of these systems are of concern here: a) the establishment of administrations and b) the modern educational system.

a) The Administrations.

After their settlement, the colonial forces (France and England) established many administrations. In Morocco for example, the French constructed town halls and other official buildings. They also established the birth certificate, in which the information had to be written in Arabic end French. The problem which rose here is that some sounds of Arabic had no matching symbols in the Latin alphabet. So, alternatives had to be found to solve this problem.

b) The Educational System.

Before the colonization period, most of the Arabic countries used for education what is called Kuranic 1 school (or kuttaab in Arabic). This latter was, in fact, a kind of traditional school in which children (girls and boys) came to acquire Kuran and other religious sciences at their very young ages. During and after the colonial period, this system had almost disappeared in some countries, letting place to the modern educational systems known nowadays. This is one of the reasons, why the colonial languages became in all the Arabic countries the second official languages that all native people had to acquire at their youth in the modern schools.

3 The Linguistic Impact.

In this section we get into the main goal of this study. I first give some examples showing in what sense the alphabetical system of the colonial languages did have an impact on that of Arabic. Then, I analyze the data starting by consonants and moving then to vowels in order to show the divergences between the FSC and the ESC in transcribing Arabic names. Finally, I try to explain why do we find these divergences and what are the reasons behind them. Some of the differences in which we are interested, between the FSC and the ESC, as far as the transcription of Arabic names is concerned, are listed below:

FSC ESC IPA taoufik taoufiq [tawfi…q] taoufik tawfiq [tawfi…q] rachid rasheed [raSi…d] chaikh sheikh [Sajx] talal thalal [t≥ala…l] najib najeeb [naZi…b] karim kareem [kari…m] mounir muneer [muni…r]
As these examples show, some identical sounds, in these proper Arabic names, have different representations. For instance, the uvular stop [q] is represented as k and q, the palatal fricative [S] is represented as ch and sh and the high front vowel [i] is represented as i and ee. This depends primarily, as was noted before, on the second language of the Arabic countries involved here. Before getting into my analysis, I want to bring the attention of the readers to a very important idea. The cases raised here are not systematic, i. e. we can find sometimes names transcribed in the same way whether the country is a FSC or an ESC. But, the examples I am raising here are a kind of standards that we find in almost all the Arabic names, as far as each group of Arabic countries is concerned. In the section below, I am going to start by the analysis of consonants and move then to that of the vowels.

3.1 The Consonantal System of Arabic.

It is well known that the Arabic language, with all its dialects, is different phonetically from the Indo-European languages by the presence of some special consonants. These last named fall into two groups: a) the emphatics, known generally as the pharyngealized consonants and b) the gutturals, which are consonants articulated in the back region of the vocal tract. I will start this analysis with the emphatics and move then to the gutturals.

The Emphatics.

The emphatic consonants of Arabic have been dealt with by many linguists [START_REF] Cantineau | Le consonantisme du sémitique[END_REF], Jakobson. 1957[START_REF] Cohen | Sur le Statut Phonologique de l'Emphase en Arabe[END_REF], Ghazali. 1977[START_REF] Ghazali | La Coarticulation de l'Emphase en Arabe[END_REF], to name but a few). In regard of their complex articulately realization, they are said to be generally characterized by a double articulation, i. e. one which is principle and proper to each consonant2 , and one which is secondary and common to all. This secondary articulation is realized in general, according to many linguists (Cantineau, 1951. Ali andDaniloff, 1972b), in modern Arabic dialects as pharyngealization3 ; that is, a retraction of the tongue root towards the pharyngeal wall, which makes the pharyngeal cavity narrower and the oral cavity larger. This configuration of the vocal tract turns the concerned consonants grave or flat (according to Jakobson's terminology, 1957. p 161-163).

There are four emphatic consonants4 in classical Arabic [t≥, d≥, s≥ and D≥ 5 ] which have as non-emphatic variants [t, d, s, D ]. In some Arabic modern dialects, we find additional emphatics like [z≥, r≥ and l≥ ]. The problem with this category of sounds, as far as our analysis is concerned, is that each pair is represented by the same consonant in the Latin alphabet. For instance, if we take s/s≥, t/t≥ or d/d≥ in some Arabic names, they will be represented by s, t and d respectively. Let's consider the following names:

IPA Alphabet IPA Alphabet [/abu s≥a…li©] 'abou salih' [sa?i…d] 'said' [s≥aber] 'saber' [sami…r] 'samir' [/ins≥af ] 'insaf' [ya…sir] 'yassir' [s≥aba…©] 'sabah' [sama…©] 'samah' [t≥a…riq] 'tarik' [tawfi…q] 'taoufik' [t≥ahira] 'tahira' [taha…ni] 'tahani' [d≥awja] 'daouia' [dawd] 'daoud' [d≥ija…/] 'diyaa' [fari…d] 'farid'
As we can see from these examples, the emphatic and non emphatic consonants of Arabic are both represented in the Latin alphabet by the same letter [s/s≥] -s, [t/t≥] -t and [d/d≥] -d. This is not actually a serious problem, because we cannot be mistaken in reading these nouns. But, the problem arises when we deal with minimal pairs; that is, when we have two nouns in which the only difference is at the level the emphatic consonant (e.g. [sVC] compared to [s≥VC]), here the need to make a distinction becomes more important. The following proper names illustrate this idea:

IPA Alphabet IPA Alphabet [s≥a?e:d] '(the) said' 6 [sa?i:d] 'said' 7 [s≥an?a:/] 'sanaa' 8 [sana:/] 'sanaa'
In some ESC the emphatic [D≥]/[d≥] and [t≥] are sometimes represented as [dh] and [th] respectively, such as 'Arriadh'9 , 'Abu Dhabi'10 and 'thalal'.

We notice here that the graphemes 'd' and 't' are combined with 'h' to represent the emphatic sound [D≥], [d≥] and [t≥]. In these cases we can consider that the 'h' points out the emphatic status of these sounds.

The Gutturals.

The term guttural refers, as I said above, to a set of consonants articulated far back in the vocal tract. Among this class we find the velars [x, V], the uvular [q], the pharyngeals [©, ? ] and the laryngeals [h, /]. This class was very often related to that of the emphatics [START_REF] Jakobson | Mufaxxama-the 'Emphatic' Phonemes in Arabic[END_REF], Angoujard. 1996), but since our interest is devoted to the representation of these consonants, we are not going to take this issue into consideration 11 . These consonants will be divided into two groups; a) consonants whose sounds are present in the foreign languages (French and English), and b) consonants whose sounds are not present in those languages. In the next section we are going to deal with the former and in the following, with the latter.

a) The Case of [x], [V].
The gutturals that will be dealt with in this section are [x and V]. These consonants are from a phonological point of view present in almost all the languages of the world. But, graphically speaking, there are few languages in which, these consonants, have graphical characters in their alphabetical inventories. Arabic is particularly one of these languages which have them.

The graphemes corresponding to these sounds in Arabic are: x ]خ[ and V .]غ[ If we take a language, like French for example, in which these two sounds exist as allophones of the same phoneme 12 , we expect that the proper names, in the FSC, containing one of these sound will be represented in the Latin alphabet by the grapheme 'r'. What we find actually is that the two sounds are represented differently. The sound [x] is represented by the grapheme 'kh' and the sound [V] by the grapheme 'gh'. This is shown by the following examples of Arabic nouns transcribed into Latin alphabet following the French modal: 11 For more information about this subject, the readers are referred to Angoujard (1997a) and [START_REF] Jakobson | Mufaxxama-the 'Emphatic' Phonemes in Arabic[END_REF]. 12 In this language when the [r] is preceded by a voiceless sound it is realized as [x] and when it is preceded by a voiced sound it is realized as [V].As examples we have 'prendre' as [pXa) dÂ] and 'tracteur' as [tXakt{Â] for [X] and 'bruit' as [bÂwi] and 'arbre' as [aÂbÂ] for [Â].

IPA

Arabic French

[?abdelVani] الغني د عب abdelghani [Va:lja] غالية ghalia [Vizloen] ن غز ghizlaine [xalid] خالد khalid [baxta] ﺑختة bakhta [xali:l] خليل khalil
The choice of the two graphemes 'kh' and 'gh' to represent the sounds [x] and [V] of Arabic instead of the grapheme 'r' is not arbitrary. In fact, this can be explained by the following reason: the grapheme 'r' represents in many languages the alveolar trill, like in the Spanish word perro 'dog'. As the same sound exists in Arabic, it is this grapheme 'r' which is used to represent it. Here are some examples showing this:

IPA Arabic French [rabi:?] رﺑيع rabiï [muni:r] منير mounir [raSida] رشيدة rachida [/ikram] إكرام ikrame
But, what about the choice of the graphemes k, g followed by h? This is not also arbitrary. From a phonetic point of view, the two sounds [x] and [V] are velars and the consonants k, g are also velars. The only difference between the two categories concerns their manner of articulation; k, g are stops and x, V are fricatives. In general, x and V are obtained (in certain languages) from k and g by a phonological process called spirantization, which turns à stop [-continuant] into a fricative [+ continuant] without changing its place of articulation. The task then is to find a way to refer to this process. The grapheme h is undoubtedly the best one, among all the graphemes, which can refer to this process, because of the phonetic features (fricative voiced or voiceless) it represents. We can then consider that the h in 'kh' and 'gh' works like a diacritic symbol indicating the fricative status of the two consonants.

In the case of [V] we find sometimes another grapheme which is 'rh'. This latter is less widespread than 'gh' and we find it more particularly in the FSC. The reason is, according to me, due to the representation of this sound ([V]) by the letter 'r' in French such as rue 'street' or bruit 'noise'.

b) The Case of [q]. The uvular stop q is certainly one of the most important characteristics of the Arabic language. There exist some non Semitic languages which have it, like Haida, Wintu, South-eastern Pomo and also some Caucasian languages like Georgian and Kabardian (Ladefoged & Maddieson 1996, p. 78). The difference is that, in these languages, this segment is realized as an ejective 13 .

As far as the representation of this sound is concerned, we also find a difference between the FSC and the ESC. In the FSC for example, the [q] is generally represented as 'k' whereas in the ESC, it is the grapheme 'q' which is favoured (the 'k' being used for the Arabic sound [k]). We can interpret this difference as showing that English is more faithful to the phonetic aspect of the sound [q] and gives it then the phonetic symbol it corresponds to. On the contrary, the French language gives more importance to normative considerations. That is to say; for the majority of the native speakers of French, the graphemes 'k', 'q' and in some contexts 'c' 14 , refer to the same sound/entity [k].

IPA Arabic FSC ESC [tari:q] طارق tarik tariq [Sawqi] شوقي chaouki chaouqi [jaqu:t] ياقوت yakout yaqout [?ati:qa] عتيقة atika atiqa c) The Case of [©], [?].
The pharyngeal fricatives of Arabic are also one of the main characteristics of this language. Their phonetic status is very problematic; if some consider them as pharyngeal fricatives, others like [START_REF] Catford | Pharyngeal and Laryngeal Sounds in Caucasian Languages[END_REF], 13 Ejectives are segments produced by the action of the closed glottis, while there is an occlusion in the oral cavity. They are present in 18 percent of the languages of the world (Maddieson 1984a). 14 followed by a back vowel u, o or a. [START_REF] Ladefoged | The Sounds of the World's Languages[END_REF] and Laufer & Codax (1979[START_REF] Ghazali | La Coarticulation de l'Emphase en Arabe[END_REF] consider them as approximants. In the Burkikhan dialect of Agul (a Caucasian language) there is a real contrast between the pharyngeal fricatives [©, ?] and the epiglottal fricative [Ì]. [START_REF] Ladefoged | The Sounds of the World's Languages[END_REF] propose then that these consonants might more be properly described as epiglottal approximants rather than pharyngeal fricatives in Arabic.

We are going to let this problem aside and concentrate on the representation of these sounds using the Latin alphabet. In general, there is no difference between the FSC and the ESC as far as the representation of these sounds is concerned. The only difference lies in the stability of the graphemes used for each of the two. In the case of [©], the grapheme used is always the same; 'h' which is a laryngeal fricative, such as:

IPA Arabic FSC ESC [©alima] ة حليم halima halima [mu©ammad] محمد mohammed muhammad 15 [s≥aba©] باح ص sabah sabah
This choice depends simply on the phonetic features of the two sounds, i. e. both of them are fricatives and their points of articulation are adjacent. As far as the [?] is concerned, here we find many graphemes. In fact, according to our remarks, the representation of this sound depends on the vowel following it. The question we should ask now is: why do we substitute the [©] by 'h' and the [?] by the vowel following it? Can't we make the same thing with the [©]? i. e. substituting it by the vowel following it: e. g. [©alima] → [Palima] → 'alima'. In the FSC, this is what we exactly find but, only on the level of pronunciation only. French native speakers do not realize the 'h' of 'halima', they pronounce this name as if it started with a vowel: 'alima'. This is undoubtly due to the status of the 'h' in French which is often referred to as dark 'h' (h muet). On the contrary, in English the 'h' has a phonetic realization which is between the Arabic [h] and [©]. Hence, most of the English native speakers realize the [©] as a [h] like fricative.

d) The palatal fricative [S].

The palatal fricative [S] is simply one of the clearest examples which illustrate the focus of this subject. In Arabic, the grapheme corresponding to this sound is .'ش' In French and English, we have to associate two graphemes in order to obtain it; 'ch' in French and English and 'sh' in the latter only. The form 'ch' is realized differently in the two languages, i. e. as a real fricative [S] in French and as an affricate [tS] in English. It is the form 'sh' which is realized as a fricative in English.

In what concerns the Arabic names having this segment, the impact of the second languages of the country is more than obvious. In the FSC, all palatal fricatives are represented by the grapheme 'ch' while in the ESC; they are represented by the grapheme 'sh'. The examples below confirm this claim:

IPA Arabic FSC ESC [buSra] رى ﺑش bouchra bushra [/aSraf] رف أش achraf ashraf [/al ?ara…/iS] رائش الع larache _____ [/al Sa…riqa] ارقة الش _____ sharjah
After having analyzed the treatment of the consonantal system of Arabic, we turn now to the vocalic system, in order to see how this latter works.

3.2 The Vocalic System of Arabic.

The vocalic system of Arabic is one of the poorest systems in the world languages. It is composed of the three cardinal vowels: i, u and a, present in approximately all the languages and which can be either short or long. In the modern Arabic dialects other vowels can be added to this triangle such as; e and o. Our concern in this section is to show how are the vocalic sounds of Arabic represented in the transcription of Arabic names.

The vowel [i].

This vowel is transcribed, in general, in two different ways. In the FSC, it is the grapheme 'i' which represents it, whereas in the ESC, it is the grapheme 'ee' which is used. This is clearly related to the phonetic realization of both letters in French and English. In French, for instance, the [i] sound is realized in the alphabetic system as i. By way of contrast, in English, it is the e which corresponds to this sound, the letter i being associated to the diphthong [ai]. Here are some examples illustrating this point:

IPA Arabic FSC ESC [/alZazi…ra] زيرة الج aljazira aljazeera [maZi…d] د مجي majid majeed [©aki…m] م حكي hakim hakeem [naZi…b] ب نجي najib najeeb
In the FSC, we find sometimes the grapheme 'e' for the vowel [i]. This happens basically when two conditions are encountered: a) the name should contain either an emphatic or a guttural consonant and b) the vowel 'i' of the Arabic name should be brief (©araka or kasra) such as: 'saleh' [s≥a…le©], 'nasser ' [na…s≥er] and 'reda' [red≥a].

The vowel [u].

The sound [u] is also affected by this phenomenon. In French, this rounded back vowel is represented graphically by 'ou', whereas in English, we find two representations: 'u' and 'oo'. In relation with the treatment of the vocalic sound [i], we expect that the [u] in the FSC be represented by the grapheme 'ou' and in the ESC by one of the two graphemes; 'u' or 'oo'. This is what we generally find, with a small exception in English.

In the FSC, the vocalic sound [u] is always graphically represented by 'ou' (see the corpus below). However, in some cases it is the grapheme 'o' which is favoured. The two conditions cited before should also be met: a) the name should contain either an emphatic or a guttural consonant and b) the vowel 'u' of the Arabic name should be brief (©araka or damma) such as: 'doha' [d≥o©a], 'soltana ' [s≥olt≥ana] or 'lotfi' [lot≥fi].

There is another way to explain this lowering of the vowels 'i' and 'u' if we take into consideration the effect of emphatics and gutturals on adjacent vowels. It is well known that the two last categories of consonants have a lowering phonological impact on vowels; i. e. /i/ lowers to [e] and /u/ to [o]. This is due to the articulately configuration of the tongue, during the realisation of an emphatic or a guttural, which is lower than that of the other consonants.

In the ESC as we said we have two forms; 'u' and 'oo'. What we noticed is that the form 'u' corresponds either to the brief vowel (damma) or appears at the beginning of names starting by a glottal stop followed by 'u'. Whereas the form 'oo ' corresponds, in general, to We have shown here some of the general graphic tendencies that we found in the FSC and the ESC as far as the transcription of Arabic names, using the Latin alphabet, is concerned. In short, the choice of one form or the other, as was shown in the examples, depends sometimes on the phonetic value of the sound and sometimes on its phonological value. The former was attested basically in the FSC whereas the latter was attested in the ESC. This is, in general, due to the value of the sound concerned in the alphabetical system of the second language of the country. To put the point another way, in the FSC the choice of the graphemes depends on their phonetic realisation in the alphabetical system itself. On the contrary, in the ESC the choice depends on the phonological realisation of the sound in Arabic. The examples on the high front vowel [i] are the best way to illustrate this claim. In fact, in the FSC there is no difference between a long or a brief [i], while in the ESC, this difference is marked by either the 'i' or 'ee' for brief and long [i] respectively. This difference can be also explained by the linguistic history of each foreign language. The French language became officially the second language of the countries of the Maghreb through colonisation in the beginning of the 19 th century. This process was accomplished by the military forces that had no special knowledge in linguistics. The assimilation of the Arabic names was done on the basis of perception only and the choice of the transcriptions, then, was a matter of appreciation. However, in the ESC, the contact with the English language has taken place a century before. It started by what we called the 'orientalist's expeditions' in the beginning of the 18 th century. This process was accomplished by many scientists among which we find many linguists, such as Wallin, Brükce, Rosenmüller to name but a few. Their purpose, among others, was to describe and understand the Arabic language and its varieties in the best possible way. This may explain why we find, in the ESC, transcriptions referring basically to the phonological realization of the sound concerned.

We have seen also that the grapheme 'h' has a special status in Arabic transcription in the sense that we combine it with many other letters. For instance, we may combine it (as was seen) with c or s to represent the sound [S], like 'chakir ' and 'Al Sharjah' 20 or with p for the sound [f]21 , like 'moustapha'. As far as ch/sh are concerned, we noticed that the FSC use more the form ch for the sound [S], where as the ESC, represent the same sound by the form sh (cf. Section 3.1.2.d).

The conclusion we got about the 'h' is that the fact to combine it with c/s for [S], with p for [f] and with k/g for [x, V] is phonetically motivated. Its voiceless/fricative features are well adapted to the sounds concerned. But, we don't understand why the same grapheme (h) is also combined with d and t for [D≥]/[d≥] and [t≥] respectively. In what concerns [D≥], its only common feature with [h] is the frication. So why do we use the letter h as a sort of diacritic for emphaticness and frication at the same time?

Finally and in spite of all what was said and shown about the transcription of Arabic names, there exists many cases which do not correspond to the results found in this work. We find, for example, in the ESC some names with the vowel [u] being represented by the grapheme 'ou' as in the FSC, such as the name of the city 'al mansouriyah' in Saudi Arabia or that of 'al maamoura' in Qatar. A more detailed study is undoubtedly needed to explain these controversies.

  Let's consider the following examples:As we can see, the pharyngeal fricative [?] is always represented by the vowel following it. We can say that we simply omit this pharyngeal from the word keeping all the other segments: e. g. [?ali] → [Pali] → 'ali', [sa?ud] → [saPu…d] → 'saoud' or 'saud'.

	IPA	Arabic	FSC	ESC
	[?ali]	ي عل	ali	ali
	[sa?i…d]	عيد س	said	said/ saeed
	[sa?u…d]	عود س	saoud 16	saud 17

  the long vowel [u…] or 'waw', though it is less used, as the examples below show.

	[um /al quwajn]	وين الق ام	________ umm al quwain 18
	[/unajzah]	يزة عن	________ unayzah 19
	4 Results and Conclusions.
	IPA	Arabic	FSC	ESC
	[dunja]	ا دني	dounia	dunia
	[mu©sin]	ن محس	mouhssine	muhssine
	[da…wu…d]	داوود	dawoud	dawood/dawuud
	[mu©ammad]	محمد	mohammed muhammad

The word Kuranic refers to the holly book of Muslims 'Kuran', whose graphic form is one of the problematic examples that will be dealt with in section (3.1.2.b), because this sound has three symbols representing it, in Latin alphabet. These symbols are: k for Koran, c for Coran and q for Quran.

This principal articulation is said to be coronal in general. But, some linguists[START_REF] Cohen | Sur le Statut Phonologique de l'Emphase en Arabe[END_REF] for example) speak about other emphatics which are bilabial such as [b≥] and [m≥] for 'b≥ab≥a' and 'm≥am≥a' respectively.

For more details about this subject, the readers are referred to,[START_REF] Jakobson | Mufaxxama-the 'Emphatic' Phonemes in Arabic[END_REF],[START_REF] Cantineau | Le consonantisme du sémitique[END_REF][START_REF] Laufer | The Emphatic and Pharyngeal Sounds in Hebrew and Arabic[END_REF],[START_REF] Ali | A Cinefluorographic-Phonologic Investigation of Emphatic Sound Assimilation in Arabic[END_REF] Daniloff (1972b) and Ghazeli (1976).

The number of these consonants changes from one Arabic variety to another. Sometimes, we find a difference even inside one variety. For instance, in classical Arabic we have four consonants, whereas in Moroccan Arabic we have six[START_REF] Gouma | L'emphase en Arabe Marocain: le Parler de Kénitra comme example[END_REF][START_REF] Gouma | L'Emphase en Arabe Marocain: Théorie et Syllabation[END_REF](Gouma , 2010 (in preparation) (in preparation)).

In approximatively all modern Arabic dialects, this emphatic consonant is whether substituted by, or merged with another, consonant. For instance, in MA it merged with the emphatic[d≥] whereas in EA, it was substituted by the emphatic[z≥].

A region in the north of Egypt.

The pharyngeal fricative sound [?] is also a problematic case which will be dealt with in the next section.

The capital of Yemen.

The capital of Saudi Arabia.

An emirate of the United Arab Emirates.

As one might see, the vowels in[mu©ammad] are not represented in the same way. This will be analyzed in the next sections which are about the vowels.

Less common in the countries of the Maghreb.

As Al Saud the royal family of Saudi Arabia.

A city of the UAE.

A city in Saudi Arabia.

This combination is also found in Indo-European languages