Sheheryar Malik
email: sheheryar.malik@inria.fr

Fabrice Huet
email: fabrice.huet@inria.fr

Denis Caromel
email: denis.caromel@inria.fr

Latency based Dynamic Grouping aware Cloud Scheduling

Keywords: Latency grouping, Cloud scheduling, Group partitioning

In a multi-cloud environment, distributed application may need to have minimal inter-node latency to improve their performance. In this paper, We propose a model for the grouping of nodes with respect to network latency. The application scheduling is done on the basis of network latency. This model is a part of our proposed Cloud Scheduler module, which helps the scheduler in scheduling decisions on the basis of different criteria. Network latency and resultant node grouping on the basis of this latency is one of those criteria. The main essence of the paper is that our proposed latency grouping algorithm not only have no additional network traffic for algorithm computation but also works well with incomplete latency information and performs intelligent grouping on the basis of latency. This paper addresses an important problem in cloud computing, which is locating communicating virtual machines for minimum latency between them and group them with respect to inter-node latency.

I. INTRODUCTION

In a multi-cloud environment, processing nodes (i.e. virtual machines) can be geographically co-located in the same cluster or far enough to be in different countries. Even they can belong to different cloud vendors. So there can be more inter-node latencies as compared to a typical cluster. If an application requires coordination among different cloud nodes, then the performance can be degraded due to the high internode latency. Thus there is a high demand to have the internode latency as minimal as possible. In order to have an optimal solution for this situation, we must have a group of nodes which have minimum inter-node latency and also have the minimum number of nodes required for the application.

Here we have come up with a problem statement. The problem statement has a number of requirements to address. First requirement is to group nodes on the basis of nodes connection value (i.e. latency) instead of number of connections to the nodes. The nodes in a group must have minimal inter-node latency. Second requirement is for the algorithm to work on incomplete latency information i.e. we do not have NxN communication instances (connections). And the third requirement is that the groups should be pre-computed, so that the user applications should not need to ask the algorithm to compute the groups every time it needs to run. Fourth requirement is to produce mutually exclusive groups, so a node in one group should not appear in other group. If the node is not-mutually exclusive in groups then a node which has already been assigned to an application can be a candidate to be assigned to another application because of appearing in another group.

As a solution to the above said problem, we propose an algorithm to group the nodes with minimum inter-node latency together. In this solution, the algorithm is quite capable to group the nodes with the minimum available latency information. Latency information is available only for those nodes, which have done some communication with other nodes. It does not rely on broadcasting to calculate the inter-node latency, as broadcasting consumes a lot of bandwidth and put a burden on network traffic. The proposed algorithm does not send special messages to other nodes to calculate latency. It uses the piggy back technique by determining the latency for the nodes which have done some communication. We aim to come up with a prudent solution, which heuristically performs the grouping decision on incomplete latency information. The algorithm produces multiple mutually exclusive groups with variable number of nodes. Thus a node can appear in only one group. It is ideally suitable when a process wants to execute its sub-tasks on multiple groups. Scheduler finds the group or groups with most suitable size for the demanding process. For a process which is not going to demand more resources during its course of execution, it should find a group closer to the minimum number of nodes required. For a process which can demand the scalable resources, scheduler chooses a group which can support execution in peak scalability demanded. The algorithm has different configurations, which differs according to the situation. The algorithm result is normally different for every configuration. The algorithms runs periodically and also when there is some change in cloud, like the process migration to other virtual machine, change of IP address etc. In this paper, we are focused on group discovery and creation. Here we are not addressing the issues related to the latency updates. As the latency update mechanism is not within the scope of our work, we use the already existing force based embedding techniques [START_REF] Dabek | Vivaldi: A Decentralized Network Coordinate System[END_REF], [START_REF] Sharma | Estimating Network Proximity and Latency[END_REF], [START_REF] Francis | IDMaps: A Global Internet Host Distance Estimation Service[END_REF] for latency update.

The rest of the paper is structured as follows. Section 2

gives the background and existing related work done in the area. Then in section 3, we present our proposed model. In Section 4, we describe the results of experimental evaluation of our proposed algorithm. We conclude in Section 5 and discuss the future research directions.

II. RELATED WORK

Grouping of nodes with respect to some certain characteristics has been studied under various names. Most commonly it is referred as community detection. Community, group, or cluster detection have been done for various disciplines and fields, including internet, world wide web, biological network, citation network, social network, complex systems, graph theory etc. Different algorithms have been produced tailored to the needs of the discipline. Most of these algorithms are based on grouping of nodes on the basis of connection count for a particular node. However, in our problem scenario, we are grouping the nodes on the basis of connection value between nodes. The connection value is determined by the latency between the nodes. In general, a network community is a group of nodes with more interactions between its members than the other [START_REF] Leskovec | Empirical Comparison of Algorithms for Network Community Detection[END_REF]. A node in a group or community normally has more interactions inside than outside the group. A community detection algorithm is considered better if its communities' external node connection to internal node connection ratio is lesser. This property is called conductance. Our algorithm produces groups with high conductance.

We have examined some of the existing algorithms for our problem statement. However, none of the existing algorithms fulfill all the requirements of it. As mentioned in our problem statement, every node connection has a value and the node proximity to its neighbor is determined by that value. In most of the existing community detection algorithms, the nodes are grouped with respect to the number of nodes connected to a particular node. Nodes which are far in terms of number of connection count (hop count) normally fall in different groups. Generally these algorithms produce non-mutually exclusive groups. Thus, none of these existing algorithms fulfill all the requirements of our problem statement. Here we list a few of the existing algorithms, which generally produce overlapping groups or communities. Our algorithm produces mutually exclusive groups according to our problem statement and performs well on incomplete latency information with a complexity of O(n 2 ).

A distributed community detection model has been introduced by Hui et al. [START_REF] Hui | Distributed Community Detection in Delay Tolerant Networks[END_REF]. In their work, they have three variations of their algorithm based on SIMPLE, K-CLIQUE and MODULARITY methods. The algorithm performs the community detection in a distributed fashion on mobile devices. It creates groups which are not mutually exclusive and there is no node regrouping. k-CLIQUE and MODULARITY have better performance than SIMPLE, but the SIMPLE is lesser complex i.e. O(n). Whereas, Modularity has a complexity of O(n 4 ) in worst case. k-CLIQUE has a complexity of O(n 2 ).

There also exist a few graph partitioning algorithms, which divides the graph in groups or communities. Local Spectral Partitioning algorithm [START_REF] Andersen | Local graph partitioning using PageRank vectors[END_REF] and Flow-based Metis+MQI [START_REF] Lang | A Flow-based Method for Improving the Expansion or Conductance of Graph Cuts[END_REF] are widely used. Metis+MQI is better than Local Spectral in terms that its communities' internal connection is more stronger than external. So Metis+MQI has better conductance than Local Spectral. On the other hand, in worst case Metis+MQI can have communities with no inter-community connection. Whereas, in Local Spectral communities are always interconnected, which is a good property. In this situation, Local Spectral is better. Local Spectral is also more compact than Metis+MQI.

There are some hierarchical agglomerative clustering algorithms, which generate clusters or groups. Clauset has proposed an agglomerative algorithm [START_REF] Clauset | Finding Local Community Structure in Networks[END_REF] that greedily maximizes the modularity. The average complexity of the algorithm is O(n 2 ). It generates non-mutually exclusive groups. Zhao devises a mechanism for hierarchical agglomerative clustering with respect to ordering constraint [START_REF] Zhao | Hierarchical Agglomerative Clustering with Ordering Constraint[END_REF]. The complexity of the algorithm is O(n 3 ). It generates overlapping clusters with nodes possibly common in different clusters. Garcia devised a general framework for agglomerative hierarchical clustering algorithms [START_REF] Gil-Garcia | A General Framework for Agglomerative Hierarchical Clustering Algorithms[END_REF], in which he tested and compared different existing algorithms. Newman has proposed an algorithm [START_REF] Newman | Detecting Community Structure in Networks[END_REF], which is based on the edge removal mechanism. In the worst case, it has a complexity of O(n 3 ).

III. PROPOSED MODEL -GROUP DISCOVERY ALGORITHM

The basis of our proposed solution is an algorithm that groups the nodes with respect to their inter-node latency. The cloud scheduler performs the scheduling decision on the basis of grouping information gained from the algorithm. The proposed algorithm targets specifically to the situation, when the latency information is incomplete and only available for the nodes, which have done some communication with other nodes. Thus it has a minimized effect on network traffic load. The produced groups are mutually exclusive, means that a node can only appear in one group.

The algorithm discovers the neighbors within a specified latency and creates the groups. The algorithm has three different phases. The most important and core phase is configuration phase. This algorithm runs for every node and decides for node grouping by finding latency to its neighbor. This latency is compared to a threshold and group threshold value which acts as a mean in deciding for node grouping. The algorithm is iterated for a number of times equals to the number of nodes. Before going further into the algorithm description, we introduce the concepts that we are going to use in the algorithm.

Visit node is a node, which is selected during each iteration to check its latency with it's neighbors and possible grouping of neighbor. Neighbor node is a node, which has done some communication with a particular visit node. Threshold is the maximum latency allowed between two communicating nodes, candidate to be grouped together. Threshold value depends on the threshold policy. Group Threshold is the maximum latency allowed for grouping. It is the distance latency from the visit node to the root node of its neighbor. Group threshold policy also depends upon the group threshold policy. Latency between visit node and neighbor node is compared with threshold and group threshold.

A. Initialization Phase

It is a pre-processing phase of the algorithm. In this phase, the initialization of environment variables is performed, which helps the algorithm to execute. The grouping decision in the next phase is done on the basis of these initial preconfigurations. The pre-configurations are calculated from different policies.

Threshold and Group Threshold Value is one of the most important thing to decide. Threshold and group threshold really play the most significant role in the output of the algorithm.

Threshold can be decided;

• by the scheduler administrator on the basis of his past experiences. In this case, administrator must have knowledge about the network infrastructure.

• on the basis of statistical information of inter-node latency. It can be set either on the basis of median or mean latency. It is more preferred to decide on the basis of mean latency and standard deviation. In normal case, the threshold will be equal to the mean or median latency of all the nodes. Group threshold can be either a combination of mean and standard deviation or median plus some fraction of median. In the first case, the administrator needs to be very experienced in dealing with this type of situation and can do it with highly favorable result. In the second case (i.e. statistical based), mean latency can be affected by the outliers. Median seems to work better than mean latency as it is not affected by outliers. The next difficult decision is to choose a value for Group Threshold. In normal case, we select it as twice as the threshold.

B. Configuration Phase

This is the core phase of the group discovery algorithm. In this phase, we apply the main part of the algorithm. It groups the nodes with respect to their inter-node latency. The algorithm runs for each node and decides for its grouping by finding latency to its neighbor. The input to the algorithm is the latency and configuration information.

Algorithm This algorithm iterates for the number of nodes in the system. In each iteration, it selects a visit node (i.e. node with highest node rank among all the non visited nodes). Then it checks the latency between the visit node and all of its neighbor nodes. If the latency between the visit node and neighbor node is less than or equals to the threshold, then it checks that whether the neighbor is already grouped or not. If the neighbor node is not grouped before, then it adds the neighbor node to a temporary group. After this, it checks that the sum of the latency from the neighbor of visit node to the root of visit node is less than the group threshold or not. If it is not, then it raises the flag that the neighbor cannot be grouped to the root of the visit node. Then it compares the latency of the neighbor node and the visit node with the latency of visit node and it's previous node. If any one of the neighbor nodes has lesser latency to the visit node than the latency from visit node to the previous node, then it removes visit node from the old group and adds it to the temporary group. In the other case, if the neighbor node is already grouped, then it further checks that whether it is also visited or not. If it is not visited, then it groups the node with the temporary group. But if it is already visited, then it checks, whether the latency of neighbor node and visit node is less than latency of neighbor node and it's previous node or not. If so, then it checks if the sum of latencies from the neighbor of visit node to the root of visit node is not less than the group threshold. If so, it raises the flag that neighbor node cannot be grouped with the root of visit node. It also checks that if any one of the neighbor node has lesser latency to the visit node than latency from visit node to the previous node then it removes the visit node from the old group and add to the temporary group.

On the other hand, if the latency between visit node and neighbor node is greater than the threshold, then it checks whether the neighbor node is already grouped or not. If it is already grouped, then it does not do anything. But if the neighbor node is not grouped before, then it creates a new group and adds the neighbor node to the new group. Then it checks that the temporary group is group-able to the root or not. It is checked by comparing the threshold-counter with the regrouping index (normally half of the number of neighbors within threshold). If threshold-Counter results in a number more than or equals to the regroupingIndex then it copies all the elements of the temporary group to the group of visit node. But if threshold-counter is less than regroupingIndex then it creates a new group. Then it checks whether the visit node can be removed from old group or not (if the latency between any neighbor node and visit node is less than latency between visit node and previous of visit node then the visit node is removable from old group). If so, then it removes visit node from old group and add it in the new group. Then it copies all the nodes from the temporary group to the new group. Then it ranks the visit node as 0 to indicate that it has been visited. It repeats all the above steps starting from finding of visit node till here.

C. Reconfiguration Phase

In this phase the algorithm creates new groups and adds the existing leaders of the old groups to each one of the new groups. Now each node checks its distance from the node leader. This phase of the algorithm tries to group the nodes which belong to a single node group. These nodes are candidate nodes to be grouped with some other nodes. In this phase, every candidate node probes for latency to the leaders of all the groups. It tries to find a leader node with minimum latency among all and within threshold. If it finds that the minimum latency is less than the threshold then it groups the candidate node with the group of leader node having minimum inter-node latency. If it fails to find a leader node with latency less than threshold then it does not group it with any one and appears as an independent group with one node.

IV. EXPERIMENTS AND RESULTS

We have implemented our algorithm and experimented it with different configurations in different environments on clusters, grids and cloud. We have The results obtained from these experiments reflect the algorithm efficiency with different configurations in different conditions. In this paper, due to the space limitation, we have included only the experiments performed on Grid5000 [11]. There are multiple sites in Grid5000, which are geographically located far from each other at variable distances as shown in Figure -1. In this type of network, the algorithm works better for the configuration value set by administrator, whereas configurations based on mean and median normally does not behave well. All of the following experiments were performed with spiral ranking policy.

We have selected multiple sites for our experiments. Here, we list a few of the experiments. All the time values shown in the experiments are in micro seconds. The experiments from 1 to 3 were conducted on 6 sites of Grid5000 with 8 nodes on each site. The node distribution was like this. Node 00-07: Grenoble Node 08-15: Lyon Node 16-23: Bordeaux Node 24-31: Toulouse Node 32-39: Sophia Node 40-47: Nancy in the case where automated threshold calculation has to be performed. Table IV is same for reconfiguration phase as there is no change in reconfiguration phase from the configuration phase. All the nodes were grouped in one single group and there was no group with a single node.

Experiment # 4: This experiment is conducted on 4 sites of Grid5000 with 10 nodes on 3 sites and 8 nodes on the last site. The node distribution was like this. Node 00-09: Grenoble Node 10-19: Lyon Node 20-29: Bordeaux Node 30-37: Toulouse In this experiment, we have set the threshold value equals to mean latency i.e. 7524 microseconds. The group threshold value is set as mean plus standard deviation. In this experiment the nodes has communicated randomly with others. Some nodes have communicated more and some have less. During the experiment, we have 324 inter-node communication instances. It has a median latency value of 8843 microsecond. The mean latency is 7524 microsecond with a standard deviation of 2574 microsecond. Initially, the configuration phase has created 7 groups, as shown in Table V. This is quite closer to the real. In this situation, two sites Grenoble and Lyon has lesser inter site latencies as compare to the others. So we can see that the nodes from both these sites are grouped together as the threshold value is quite higher than their average inter-site latency. Nodes 34, 37 and 39 on Toulouse site have done communication between them, and also with the nodes with which they have latency higher than threshold. Thus they are grouped together. After the reconfiguration phase we came up with 5 groups as shown in Table VI. In this phase, node 30 found the group 4 to be grouped with and node 6 found group 0 to be grouped with.

V. C ONCLUSIONS

Our proposed algorithm provides a viable solution for grouping of nodes with respect to their inter-node latency. It specifically targets the situation when we do not have complete information about all the inter-node latencies. It works well on the latency information for the nodes who have communicated. It does not introduce any additional network traffic for the algorithm. It is very simple to understand and use. Algorithm complexity O(n 2 ) is quite low as compare to its counterparts. During the execution of the algorithm a node can be regrouped. Importantly it produces mutually exclusive groups according to the problem statement, whereas most of the existing grouping algorithms produce overlapping groups or communities. It can also produce overlapping groups by making small changes in the algorithm. This can be done by removing the regrouping steps in the configuration phase of the algorithm. There is no false positive, but there exist a few chances of false negative. In case of false negative, a node will fail to join a group with whom it should be grouped.

Figure 1 .

 1 Figure 1. Sites of Grid5000 across France [11]

978-0-7695-4652-0/12 $26.00 © 2012 IEEE DOI 10.1109/WAINA.2012.91

Experiment # 1: In the first experiment, we have set the threshold value at 1 millisecond (1000 microseconds). The group threshold value is set as its twice, i.e. 2 milliseconds. In this experiment, the nodes have communicated randomly with others. Some nodes have communicated more and some have less. The maximum number of nodes that can be contacted by a particular node is fifteen. During the experiment, we have 830 inter-node communication instances. It has a median latency value of 11112 microseconds. The mean latency is 10978 microsecond with a standard deviation of 1608 microsecond. The result of configuration phase is shown in Table I. Here we can see that the configuration phase of the algorithm has generated 9 groups. Most of the groups are complete. Nodes in group 1 and group 2 belongs to the same site (i.e. Lyon), but they are not grouped together. There can be many reasons for this type of situation, either the nodes in both groups does not have communicated at all or either some of them have latency higher than threshold. In case of this experiment, none of the nodes in group 1 has done communication with the nodes in group 2. And none of the nodes in group 2 has done communication with the nodes in group 1. So completely lacking in information between these two resulted in the formation of two distinct groups from the same site. In case of node 42 in group 7, it has not done any communication with any node in the system. So it cannot be grouped with any other in this phase. Node 20 has done some communication with 4 other nodes, but the latency between them was more than the threshold. So it also cannot be grouped with any other node. In this experiment, we can see that despite having very less latency information, the algorithm has performed well and has come up with good groups formation. Table II shows the result of the reconfiguration phase. In this phase, both the single node groups (i.e. 7, 8) are processed. Node 42 and node 20 both find a leader node within the latency and they are grouped with them. Node 20 is grouped in group 3 and node 42 is grouped with group 6. Experiment # 2: We have also tested the algorithm for the case when we do have complete latency information. i.e. Nx N-1 communication is done, where N is the number of nodes. In this case we set the value of threshold at 1 millisecond (1000 microsecond) and group threshold value as its twice. During this experiment, we have N x N-1 (i.e. 2256) inter-node communication instances. It has a median latency value of 11099 microseconds. The mean latency is 11124 microseconds with a standard deviation of 975 microseconds. The algorithm resulted in the 100% correct result after the configuration phase as shown in Table III. In the reconfiguration phase of algorithm, it has nothing to do except to simply remove the empty groups if any. The result of reconfiguration is the same as shown in Table III, as the configuration phase has already produced the correct results. Experiment # 3: In the next experiment we tested the broadcast communication scenario by setting the threshold value to statistical based instead of administrator heuristic. The groups that were formed are given below. The groups formed are identical for both mean and median based threshold. Table IV shows that the algorithm has grouped all the nodes in one group. It is due to the fact that the statistical based threshold gives poor results in this type of situation. Because there is much more communication outside the clusters than the inside. Every node is communicating to 40 nodes out of its cluster which are geographically far away, whereas intracluster communication is done with only 7 nodes. Latency to the nodes of the other cluster is much higher, thus resulting in a higher value of mean and median threshold. This mechanism is well suited to the situation when there is more communication within a cluster. Therefore, we recommend using the administrator heuristics to determine the threshold value, except


Gerard Lynch
email: gplynch@scss.tcd.ie

Erwan Moreau
email: moreaue@scss.tcd.ie

Carl Vogel
email: vogel@scss.tcd.ie

A Naive Bayes classifier for automatic correction of preposition and determiner errors in ESL text

This is the report for the CNGL ILT3 team entry to the HOO shared task. A Naive-Bayes-based classifier was used in the task which involved error detection and correction in ESL exam scripts. Our system placed 11th out of 14 teams for the detection and recognition tasks and 11th out of 13 teams for the correction task on the based on f-score for both preposition and determiner errors.

Introduction

The 2012 HOO shared task seeks to apply computational methods to the correction of certain types of errors in non-native English texts. The previous year's task, [START_REF] Dale | Helping our own: The hoo 2011 pilot shared task[END_REF], focused on a larger scale of errors and a corpus of academic articles. This year's task focuses on six error types in a corpus of nonnative speaker text.

Error types

The scope of the errors are as follows:

Training data

The training data for this shared task has been provided by Cambridge University Press and consists of scripts from students sitting the Cambridge ESOL First Certificate in English (FCE) exams. The topics of the texts are comparable as they have been drawn from two consecutive exam years. The data is provided in XML format and contains 1000 original exam scripts, together with a standoff file containing edits of the type described in Section 1 above, also in XML format. These edits consist of offset information, edit type information and before and after text for correction. The results for the shared task were presented in this format.

The test data consists of 100 exam scripts drawn from a new corpus of exam scripts. Some extra metadata is present in the source files, including information about the student's mother tongue and the age-range of the student, however the mother tongue data is not present in the test set.

Approach

The approach we have chosen for this task involves the use of machine-learning algorithms in a four-part classification task.

The first part of the task involves identification of edits in the training data, perhaps the most challenging given the large imbalance of edits vs non-edits in the data.

The next step concerns classification of edits into the six types described above, and the final task involves correction of edits, replacing or adding prepositions and determiners, and possibly in some cases removal of same.

There is a fourth step involved which reassesses the classification and correction based on some simple heuristics, using POS tags of the head word of each instance. If the headword is not a preposition and the system has marked a replace preposition error at that position, this error will be removed from the system. Likewise when the headword is not a determiner and a replace determiner error has been marked. If the replacement suggested is the same as the original text(in some cases this occurs), the edit is also removed. Another case for removal in this fashion includes an error type involving a missing determiner error where the head word is neither a noun or an adjective. In some cases the system reported and corrected an error suggesting the same text as was originally there, i.e no change. These cases are also removed from the end result.

We utilise the freely available Weka machine learning toolkit, [START_REF] Hall | [END_REF] and the algorithm used for classification in each step is Naive Bayes.

We represent each word in the training data as a vector of features. There are 39 basic features used in the detection process, and 42 in the classification and training step. The first 7 features contain information which are not used for classification but are used to create the edit structures, such as start offset, end offset, native language, age group and source filename and part information. These features include the current word plus the four preceeding and following words, POS and spellchecked versions of each, together with bigrams of the two following and two preceeding words with spellchecked and POS versions for these.

Information on speaker age and native language is also included although native language information is not present in the test set.

All tokens have been lower-cased and punctuation has been removed. POS information for each token has been added. The open-source POS tagger from the OpenNLP tools package (OpenNLP, 2012) has been used to this end. Spell correction facility has been provided using the basic spellchecker in the Lucene information retrieval API [START_REF] Gospodnetic | [END_REF] and the top match string as provided by this spell correcting software is used in addition to each feature. The basic maximum entropy model for English is used for the POS tagger.

We had also planned to include features based on the Google Books ngram corpus, (Michel et al., 2011) which is freely available on the web, but unfortunately did not get to include them in the version submitted due to errors which were found in the scripts for generating the features late in the process.

Google N-grams Features

Motivation

The Google Books N-Grams2 is a collection of datasets which consist of all the sequences of words (n-grams) extracted from millions of books (Michel et al., 2011). The "English Million" dataset contains more more than 500 millions distinct n-grams3 , from size 1 to 5. for every n-gram, its frequency, page frequency (number of pages containing it) and book frequency are (number of books containing it) are provided.

In this Shared Task, we aim to use the Google N-grams as a reference corpus to help detecting the errors in the input. The intuition is the following: if an error occurs, comparing the frequency of the input n-grams against the frequency of other possibilities in the Google N-grams data might provide useful indication on the location/type of the error. For example, given the input "I had to go in a library", The Google N-grams contain only 36,716 occurrences of the trigram "go in a", but 244,098 occurrences of "go to a" , which indicates that the latter is more likely.

However there are several difficulties in using such a dataset:

• Technical limitations. Extracting information from the dataset can take a lot of time because of the size of the data, thus the range of approaches is restricited by effficiency constraints.

• Quality of the data. The Google N-grams were extracted automatically using OCR, which means that the dataset can contain errors or unexpected data (for example, the This is why the Google N-grams must be used cautiously, and only as an indication among others.

Method

Our goal is to add features extracted from the Google N-grams dataset to the general features extracted from the input data itself, and feed the supervised classification process with these. Before computing the features, a list L of "target expressions" is extracted from the training data, which contains all the words or sequences of words (determiners and prepositions) which occur in a correction. Then, given an input sentence A 1 . . . A m and a position n in this sentence, two types of information are extracted from the Google data:

• Specific indications of whether an error exists at this position:

1. No change: the frequency of the input sequence A n-1 A n and A n-1 A n A n+1 ; 2. Unnecessary word(s): the frequency of the sequence A n-1 A n+1 if A ∈ L; 3. Missing word(s): the frequency of the sequence XA n (resp. A n-1 XA n for trigrams) for any target expression X ∈ L;

4. Replacement: if A ∈ L, the frequency of XA n+1 (resp. A n-1 XA n+1 for trigrams) for any target expression X ∈ L;

• Generic indications taking the context into account: for length N from 1 to 5 in a window A n-4 . . . A n+4 , 16 combinations are computed based only on the fact the Ngrams appear in the Google data; for example, one of these combinations is the normalized sum for the 4 5-grams in this window of 0 or 1 (the N-gram occurs or does not).

Additionally, several variants are considered:

• bigrams or trigrams for "specific" features;

• binary values for "specific" features: 1 if the n-gram appears, 0 otherwise;

• keep only the "generic" features and the first three features.

5 Some detailed results (detection)

The results reported here were experimented on the training data only, using 5 folds crossvalidation, and only for the detection task. We have studied various settings for the parameters; figure 1 shows a global overview of the performance depending on several parameters (we show only a few different values in order to keep the graph readable).

The results show that the Google features contribute positively to the performance, but only slightly: the F1 score is 0.0055 better in average. This overview also hides the fact that some combinations of values work better together; for instance, contrary to the fact that not filtering the POS trigrams performs better in average, the best performances are obtained when filtering, as shown on figure 2.

• Minimum frequency 4 (preprocessing, see REF). As shown on figure 2, using a high 4 Remark: the values used as "minimum frequencies" reported in this paper can seem unusually high. This is due to the fact that, for technical reasons, the thresholds were applied globally to the data after it has been formatted as individual instances, each instance containing 9 words. As a consequence a threshold of N means that a given word must occur at least N/9 times in the original input data. threshold helps the classifier building a better model.

• POS trigrams filter (see REF). Even if not filtering at all performs better on average, the best cases are obtained with a low threshold. Additionally, this parameter can be used to balance between recall an precision (when one wants to favor one or the other).

• Size of the context window. Results can show important differences depending on the size of the window, but no best configuration was found in general for this parameter.

• Google features (see REF).

The Google features slightly help in general, and are used in the best cases that we have obtained. However there is no significantly better approach between using the original frequencies, simplfying these to binary values, or even not using the list of target expressions.

Breakdown of run configurations

Ten runs were submitted to the organisers based on different configurations. Modification of the data was carried out using both instance reduction and feature selection techniques. The system facilitated the use of different training data for each of the three main classification steps. Before classification, the data is preprocessed by replacing all the least frequent words with a default value (actually treated as missing values by the classifier). This is intended to help the classifier focus on the most relevant indications and to prevent over-specification of the classification model.

Instance reduction filters

POSTrigrams filter

The POS trigrams filter works as follows: during the training stage, the sequences of POS tags for the words current-1.current.current+1 are extracted for each instance, together with its corresponding class. Every POS trigram is then associated with the following ratio:

Frequency of true instances Frequency of false instances Then, when predicting the class, the filter is applied before running the classifier: the sequences of trigrams are extracted for each instance, and are compared against the corresponding ratio observed during the training stage; the instance is filtered out if the ratio is lower than some threshold N%. In Table 2, the label RN refers to the percentage (N) used as cut-off in the experiments. This filter is intended to reduce the impact of the fact that the classes are strongly unbalanced. It permits discarding a high number of false instances, while removing only a small number of true instances. However, as a side effect, it can cause the classifier to miss some clues which were in the discarded instances.

CurrentPlusOrMinusOne filter

The current plusorminus one filter works as follows: A list of all current.current+1 word bigrams is made from the error instances in the training data, along with all current-1.current bigrams. The non-error instances in the training data are then filtered based on whether an instance contains an occurrence of any current.current+1 or current-1.current bigram in the list. During preliminary experiments, selecting a subset of 12 features produced classification accuracy gains in the detection and classification steps of the process using ten-fold cross validation on the training set. These twelve features were: current, current+1.current+2, current-1.current-2,currentSC,currentPOS, current-1,current-2,current+1,current+2,current+1SC, and current-1SC. The SC appendix refers to the spell-corrected token, with POS referring to the part-of-speech tag. The F12 configuration filter removes all other features except these.

Results

Table 3 displays the results for both preposition and determiner errors which were obtained by the system on the preliminary test set before teams submitted their queries. Table 4 refers to the results obtained by the system after the queried errors were removed/edited.

Conclusions

The task of automated error correction is a highly difficult one, with the best-performing systems managing a score of approx. 40 for F-value for the detection, recognition and correction, [START_REF] Dale | [END_REF]. There are several areas where our system's performance might be improved. The spellcheck dictionary which was used was a general one and this resulted in many spelling corrections which were out of context. A more tailored dictionary employing contextual awareness information could be beneficial for the preprocessing step. Multi-word corrections were not supported by the system due to how the instances were constructed and these cases were simply ignored, to the detriment of the results.

In the basic feature set, mostly single word features were used, however more n-gram features could be another possibility towards improving results as these were found to perform well during classification. The Naive Bayes algorithm was used primarily because of its lightweight nature and fast and efficient performance however other algorithms such as SVM's and decision trees might also give good, albeit slower, performance.

There were many different options to tune the Google-Ngrams features and it may be the case that better combinations of features are available.

Finally, very little time was spent tuning the datasets for the classification and correction step as opposed to the detection phase, this is another part of the system where fine-tuning parameters could pay dividends.

FigureFigure 2 :

 2 Figure 1: Average F1 score depending on several parameters.

Table 1 :

 1 Error types for HOO 2012 Shared Task

	1
	1 http://clt.mq.edu.au/research/projects/hoo/hoo2012/errortypes.html
	last verified, May 4, 2012

Table 3 :

 3 Overall results on original data: TC

	Task	Rank Run Precision Recall	F-Score
	Detection	11	8	6.56	26.0	10.48
	Recognition	11	8	4.91	19.45	7.84
	Correction	11	8	3.09	12.26	4.94

Table 4 :

 4 Overall results on corrected data: TC

	Run3	Recall	Precision	F
	Detection	0.0905	0.0742	0.0815
	Correction	0.0419	0.0344	0.0378
	Recognition	0.0905	0.0742	0.0815
	Run8	Recall	Precision	F
	Detection	0.2251	0.0544	0.0876
	Correction	0.1125	0.0272	0.0438
	Recognition	0.2251	0.0544	0.0876
	Run9	Recall	Precision	F
	Detection	0.2560	0.0532	0.0881
	Correction	0.1280	0.0266	0.0441
	Recognition	0.2560	0.0532	0.0882

Table 5 :

 5 Top results on original test data

http://books.google.com/ngrams/ datasets

The least frequent n-grams were discarded.English dataset contains a significant number of non English words).

Acknowledgments

This material is based upon works supported by the Science Foundation Ireland under Grant No.[SFI 07/CE/I 1142.].


Erwan Moreau
email: moreaue@cs.tcd.ie

Carl Vogel
email: vogel@cs.tcd.ie

Quality Estimation: an experimental study using unsupervised similarity measures

We present the approach we took for our participation to the WMT12 Quality Estimation Shared Task: our main goal is to achieve reasonably good results without appeal to supervised learning. We have used various similarity measures and also an external resource (Google N -grams). Details of results clarify the interest of such an approach.

Introduction

Quality Estimation (or Confidence Estimation) refers here to the task of evaluating the quality of the output produced by a Machine Translation (MT) system. More precisely it consists in evaluating the quality of every individual sentence, in order (for instance) to decide whether a given sentence can be published as it is, should be post-edited, or is so bad that it should be manually re-translated.

To our knowledge, most approaches so far [START_REF] Specia | [END_REF][START_REF] Soricut | Trustrank: Inducing trust in automatic translations via ranking[END_REF]He et al., 2010;[START_REF] Specia | [END_REF] use several features combined together using supervised learning in order to predict quality scores. These features belong to two categories: black box features which can be extracted given only the input sentence and its translated version, and glass box features which rely on various intermediate steps of the internal MT engine (thus require access to this internal data). For the features they studied, [START_REF] Specia | [END_REF] have shown that black box features are informative enough and glass box features do not significantly contribute to the accuracy of the predicted scores.

In this study, we use only black box features, and further, eschew supervised learning except in the broadest sense. Our method requires some reference data, all taken to be equally good exemplars of a positive reference category, against which the experimental sentences are compared automatically. This is the extent of broader-sense supervision. The method does not require a training set of items each annotated by human experts with quality scores (except for the purpose of evaluation of course).

Successful unsupervised learning averts risks of the alternative: supervised learning necessarily makes the predicting system dependent on the annotated training data, i.e. less generic, and requires a costly human evalution stage to obtain a reliable model. Of course, our approach is likely not to perform as well as supervised approaches: here the goal is to find a rather generic robust way to measure quality, not to achieve the best accuracy. Nevertheless, in the context of this Quality Evaluation Shared task (see (Callison-Burch et al., 2012) for a detailed description) we have also used supervised learning as a final stage, in order to submit results which can be compared to other methods (see §4).

We investigate the use of various similarity measures for evaluating the quality of machine translated sentences. These measures compare the sentence to be evaluated against a reference text, providing a similarity score result. The reference data is supposed to represent standard (well-formed) language, so that the score is expected to reflect how complex (source side) or how fluent (target side) the given sentence is.

After presenting the similarity measures in sec-tion 2, we will show in section 3 how they perform individually on the ranking task; finally we will explain in section 4 how the results that we submitted were obtained using supervised learning.

Approach

Our method consists in trying to find the best measure(s) to estimate the quality of machine translated sentences, i.e. the ones which show the highest correlation with the human annotators scores. The measures we have tested work always as follows.

Given a sentence to evaluate (source or target), a score is computed by comparing the sentence against a reference dataset (usually a big set of sentences). This dataset is assumed to represent standard and/or well-formed language.1 This score represents either the quality (similarity measure) or the faultiness (distance measure) of the sentence. It is not necessarily normalized, and in general cannot be interpreted straightforwardly (for example like the 1 to 5 scale used for this Shared Task, in which every value 1, 2, 3, 4, 5 has a precise meaning). In the context of the Shared task, this means that we focus on the "ranking" evaluation measures provided rather than the "scoring" measures. These scores are rather intended to compare sentences relatively to one another: for instance, they can be used to discard the N% lowest quality sentences from post-editing.

The main interest in such an approach is in avoiding dependence on costly-to-annotate training data-correspondingly costly to obtain and which risk over-tuning the predicting system to the articulated features of the training items. Our method still depends on the dataset used as reference, but this kind of dependency is much less constraining, because the reference dataset can be any text data. To obtain the best possible results, the reference data has to be representative enough of what the evaluated sentences should be (if they were of perfect quality), which implies that:

• a high coverage (common words or n-grams) is preferable; this also means that the size of this dataset is important;

• the quality (grammaticality, language register, etc.) must be very good: errors in the reference data will infect the predicted scores.

It is rather easy to use different reference datasets with our approach (as opposed to obtain new human scores and training a new model on this data), since nowadays numerous textual resources are available (at least for the most common languages).

Similarity measures

All the measures we have used compare (in different ways) the n-grams of the tested sentence against the reference data (represented as a big bag of n-grams).

There is a variety of parameters for each measure; here are the parameters which are common to all:

Length of n-grams: from unigrams to 6-grams;

Punctuation: with or without punctuation marks;

Case sensitivity: binary;

Sentence boundaries: binary signal of whether special tokens should be added to mark the start and the end of sentences.2 This permits:

• that there is the same number of n-grams containing a token w, for every w in the sentence; • to match n-grams starting/ending a sentence only against n-grams which start/end a sentence.

Most configurations of parameters presented in this paper are empirical (i.e. only the parameter settings which performed better during our tests were retained). Below are the main measures explored.3

Okapi BM25 similarity (TF-IDF)

Term Frequency-Inverse Document Frequency (TF-IDF) is a widely used similarity measure in Information Retrieval(IR). It has also been shown to perform significantly better than only term frequency in tasks like matching coreferent named entities (see e.g. [START_REF] Cohen | [END_REF]), which is technically not very different from comparing sentences. The general idea is to compare two documents4 using their bags of n-grams representations, but weighting the frequency of every n-gram with the IDF weight, which represents "how meaningful" the n-gram is over all documents based on its inverse frequency (because the n-grams which are very common are not very meaningful in general).

There are several variants of TF-IDF comparison measures. The most recent "Okapi BM25" version was shown to perform better in general than the original (more basic) definition [START_REF] Jones | [END_REF]. Moreover, there are different ways to actually combine the vectors together (e.g. L1 or L2 distance). In these experiments we have only used the Cosine distance, with Okapi BM25 weights. The weights are computed as usual (using the number of sentences containing X for any n-gram X), but are based only on the reference data.

Multi-level matching

For a given N, "simple matching" is defined as follows: for every N -gram in the sentence, the score is incremented if this N -gram appears at least once in the reference data. The score is then relativized to the sentence N -gram length.

"Multi-level matching" (MLM) is similar but with different lengths of n-grams. For (maximum) length N , the algorithm is as follows (for every n-gram): if the n-gram appears in the reference data the score is incremented; otherwise, for all n-grams of length N -1 in this n-gram, apply recursively the same method, but apply a penalty factor p (p < 1) to the result.5 This is intended to overcome the binary behaviour of the "simple matching". This way short sentences can always be assigned a score, and more importantly the score is smoothed according to the similarity of shorter n-grams (which is the behaviour one wants to obtain intuitively).

Two main variants have been tested. The first one consists in using skip-grams. 6 Different sizes and configurations were tested (combining skip-grams and standard sequential n-grams), but none gave better results than using only sequential n-grams. The second variant consists in assigning a more finegrained value, based on different parameters, instead of always assigning 1 to the score when n-gram occurs in the reference data. An optimal solution is not obvious, so we tried different strategies, as follows.

Firstly, using the global frequency of the ngram in the reference data: intuitively, this could be interpreted as "the more an n-gram appears (in the reference data), the more likely it is well-formed". However there are obviously n-grams which appear a lot more than others (especially for short n-grams). This is why we also tried using the logarithm of the frequency, in order to smooth discrepancies.

Secondly, using the inverse frequency: this is the opposite idea, thinking that the common ngrams are easy to translate, whereas the rare ngrams are harder. Consequently, the critical parts of the sentence are the rare n-grams: assigning them more weight focuses on these. This works in both cases (if the n-gram is actually translated correctly or not), because the weight assigned to the n-gram is taken into account in the normalization factor.

Finally, using the Inverse Document Frequency (IDF): this is a similar idea as the previous one, except that instead of considering the global frequency the number of sentences containing the n-gram is taken into account. In most cases (and in all cases for long n-grams), this is very similar to the previous option because the cases where an n-gram (at least with n > 1) appears several times in the same sentence are not common.

Resources used as reference data

The reference data against which the sentences are compared is crucial to the success of our approach. As the simplest option, we have used the Europarl data on which the MT model was trained (source/target side for source/target sentences). Separately we tested a very different kind of data, namely the Google Books N -grams (Michel et al., 2011): it is no obstacle that the reference sentences themselves are unavailable, since our measures only need the set of n-grams and possibly their frequency (Google Books N -gram data contains both).

Individual measures only

In this section we study how our similarity measures and the baseline features (when used individually) perform on the ranking task. This evaluation can only be done by means of DeltaAvg and Spearman correlation, since the values assigned to sentences are not comparable to quality scores. We have tested numerous combinations of parameters, but show below only the best ones (for every case). Table 1 shows the best results that every method achieved on the whole training data with different resources, as well as the results of the best baseline features. 7 Firstly, one can observe that the language model probability (baseline features 4 and 5) performs as good or slightly better than our best measure. Then the best measure is the one which combines different lengths of n-grams (multi-level matching, combining unigrams to 5-grams), followed by baseline feature 12 (percentage of bigrams 7 Baseline 1,2: length of the source/target sentence; Baseline features 4,5: LM probability of source/target sentence; Baseline feature 8: average number of translations per source word with threshold 0.01, weighted by inverse frequency; Baseline feature 12: percentage of bigrams in quartile 4 of frequency of source words in a corpus of the source language.

General observations

in quartile 4 of frequency), and then Okapi BM25 applied to bigrams. It is worth noticing that comparing either the source sentence or the target sentence (against the source/target training data) gives very similar results. However, using Google Ngrams as reference data shows a significantly lower correlation. Also using skip-grams or any of our "finedgrained" scoring techniques (see §2.1.2) did not improve the correlation, even if in most cases these were as good as the standard version.

Detailed analysis: how measures differ

Even when methods yield strongly correlated results, differences can be significant. For example, the correlation between the rankings obtained with the two best methods (baseline 4 and MLM Eng.) is 0.53. The methods do not make the same errors.8 A method may tend to make a lot of small errors, or on the contrary, very few but big errors. For every measure, the X axis represents the sentences sorted by the difference between the predicted rank and the actual rank ("rank error"), in such a way that for any (relative) number of sentences x, the y value represents the maximum (relative) rank error for all prior sentences: for instance, 80% of the ranks predicted by these three measures are at most 40% from the actual rank.

D = |R -R ′ |; then relativize to the total number of sentences (the upper bound for D): D ′ = D/N . D ′ is the relative rank error. On ascending sort by D ′ , the predicted ranks for the first sentences are closest to their actual rank. Taking the relative rank error D ′ j for the sentence at position M j , one knows that all "lower" sentences (∀M i , M i ≤ M j ) are more accurately assigned (D ′ i ≤ D ′ j ). Thus, if the position is also relativized to the total number sentences:

M ′ k = M k /N , M ′
k is the proportion of sentences for which the predicted rank is at worst D ′ k % from the real rank. Figure 1 shows the percentage of sentences withing a rank error range for three good methods: 10 the error distributions are surprisingly similar. A baseline ranking is also represented, which shows the same if all sentences are assigned the same rank (i.e. all sentences are considered of equal quality) 11 .

We have also studied effects of some parameters:

• Taking punctuation into account helps a little;

• Ignoring case gives slightly better results;

• Sentences boundaries significantly improve the performance;

• Most of the refinements of the local score (frequency, IDF, etc.) do not perform better than the basic binary approach.

Individual measures as features

In this section we explain how we obtained the submitted results using supervised learning.

Approach

We have tested a wide range of regression algorithms in order to predict the scores, using the Weka 12 toolkit [START_REF] Hall | [END_REF]. All tests were sentences which are assigned the same score are given the same rank. The ranking sum is preserved by assigning the average rank; for instance if s1 > s2 = s3 > s4 the corresponding ranks are 1, 2.5, 2.5, 4). 10 Some are not shown, because the curves were too close.

11 Remark: the plateaus are due to the ties in the actual ranks: there is one plateau for each score level. This is not visible on the predicted rankings because it is less likely that an important number of sentences have both the same actual rank and the same predicted rank (whereas they all have the same "predicted" rank in the baseline ranking, by definition).

12 www.cs.waikato.ac.nz/ml/weka -l.v., 04/2012.

done using the whole training data in a 10 folds cross-validation setting. The main methods were:

• Linear regression

• Pace regression (Wang and [START_REF] Wang | Modeling for optimal probability prediction[END_REF] • SVM for regression [START_REF] Shevade | [END_REF] (SMOreg in Weka)

• Decision Trees for regression [START_REF] Quinlan | Learning with continuous classes[END_REF] (M5P in Weka)

We have tested several combinations of features among the features provided as baseline and our measures. The measures were primarily selected on their individual performance (worst measures were discarded). However we also had to take the time constraint into account, because some measures require a fair amount of computing power and/or memory and some were not finished early enough. Finally we have also tested several attributes selection methods before applying the learning method, but they did not achieve a better performance.

Results

Table 2 shows the best results among the configurations we have tested (expressed using the official evaluation measures, see (Callison-Burch et al., 2012) for details). These results were obtained using the default Weka parameters.In this table, the different features sets are abbreviated as follows:

• B: Baseline (17 features);

• M1: All measures scores (45 features);

• M2: Only scores obtained using the provided resources (33 features);

• L: Lengths (of source and target sentence, 2 features).

For every method, the best results were obtained using all possible features (baseline and our measures). The following results can also be observed:

• our measures increase the performance over use of baseline features only (B+M1 vs. B);

• using an external resource (here Google ngrams) with some of our measures increases the performance (B+M1 vs. B+M2); Contrary to previous observations using the training data, these results show a better performance without our measures. We think that this is mainly due to the high variability of the results depending on the data, and that the first experiments are more significant because cross-validation was used.

Conclusion

In conclusion, we have shown that the robust approach that we have presented can achieve good results: the best DeltaAvg score reaches 0.40 on the training data, when the best supervised approach is at 0.45. We think that this robust approach complements the more fine-grained approach with supervised learning: the former is useful in the cases where the cost to use the latter is prohibitive.

Additionally, it is interesting to see that using external data (here the Google N -grams) improves the performance (when using supervised learning). As future work, we plan to investigate this question more precisely: when does the external data help? What are the differences between using the training data (used to produce the MT engine) and another dataset? How to select such an external data in order to maximize the performance? In our unsupervised framework, is it possible to combine the score obtained with the external data with the score obtained from the training data? Similarly, can we combine scores obtained by comparing the source side and the target side?

Figure 1 :

 1 Figure1: Percentage of best segments within an error range. For every measure, the X axis represents the sentences sorted by the difference between the predicted rank and the actual rank ("rank error"), in such a way that for any (relative) number of sentences x, the y value represents the maximum (relative) rank error for all prior sentences: for instance, 80% of the ranks predicted by these three measures are at most 40% from the actual rank.

Table 1 :

 1

	Method	Ref. data	DeltaAvg Spearman
	MLM,1-4	Google, eng	0.26	0.22
	Baseline feature 1	0.29	0.29
	Baseline feature 2	0.29	0.29
	MLM,1-3,lf Google, spa	0.32	0.28
	Okapi,3,b	EP, spa	0.33	0.27
	Baseline feature 8	0.33	0.32
	Okapi,2,b	EP, eng	0.34	0.30
	Baseline feature 12	0.34	0.32
	Baseline feature 5	0.39	0.39
	MLM,1-5,b	EP, spa	0.39	0.39
	MLM,1-5,b	EP, eng	0.39	0.40
	Baseline feature 4	0.40	0.40

Best results by method and by resource on training data. b = sentence boundaries ; lf = log frequency (Google) ; EP = Europarl.

We use this definition of "reference" in this article. Please notice that this differs from the sense "human translation of a source sentence", which is more common in the MT literature.

With trigrams, "Hello World !" (1 trigram) becomes "# # Hello World ! # #" (5 trigrams).

One of the measures is not addressed in this paper for IP reasons (this measure obtained good results but was not best).

In this case every sentence is compared against the reference data; from an IR viewpoint, one can see the reference data as the request and each sentence as one of the possible docu-

ments. 5 This method is equivalent to computing the "simple matching" for different lengths N of N -grams, and then combine the scores sN in the following way: if sN < sN-1, then add p × (sN-1 -sN ) to the score, and so on. However this "external" combination of scores can not take into account some of the extensions (e.g. weights).

The true-false-true skip-grams in "There is no such thing": There no, is such and no thing.

This motivates use of supervised learning (but see §1).

It is worth noticing that ties are taken into account here: two

In four cases in which Google n-grams formed the reference data, the scores were computed using the wrong language (Spanish instead of English) as the reference. Since this error occured only for the test data (not the training data used to compute the model), it made the predictions totally meaningless.

Acknowledgments

This research is supported by Science Foundation Ireland (Grant 07/CE/I1142) as part of the Centre for Next Generation Localisation (www.cngl.ie) funding at Trinity College, University of Dublin. We thank the organizers who have accepted to apply a bug-fix (wrong numbering of the sentences) in the official results, and for organizing the Shared task.

• the baseline features contribute positively to the performance (B+M1 vs. L+M1);

• The M5P (Decision trees) method works best in almost all cases (3 out of 4).

Based on these training results, the two systems that we used to submit the test data scores were:

• TCD-M5P-resources-only, where scores were predicted from a model trained using M5P on the whole training data, taking only the baseline features (B) into account;

• TCD-M5P-all, where scores were predicted from a model trained using M5P on the whole training data, using all features (B+M1).

The TCD-M5P-resources-only submission ranked 5th (among 17) in the ranking task, and 5th among 19 (tied with two other systems) in the scoring task (Callison-Burch et al., 2012). Unfortunately the TCD-M5P-all submission contained an error. 13 Below are the official results for TCD-M5P-resources-only and the corrected results for TCD-M5P-all :