Facundo Benavides
email: fbenavid@fing.edu.uy

Pablo Monzón
email: monzon@fing.edu.uy

Caroline P Carvalho
email: caroline.chanel@isae-supaero.fr

Eduardo Grampín
email: grampin@fing.edu.uy

Multi-robot Cooperative Systems for Exploration Advances in dealing with constrained communication environments

Keywords: Multi-robot systems, Cooperative systems, Exploration tasks

In the present document, the authors introduce the Cooperative Exploration problem as well as the most relevant approaches in order to show the most common drawbacks and opportunities to improve the state of art solutions. Subsequently, a preliminary version of a multi-robot exploration proposal is described. The first results obtained in simulated scenarios support the underlying ideas are feasible and promising. They show that is possible to cope with real communication constraints (always present in practice), being more fault tolerant and still having good performance regarding the total exploration time. Next steps to fully implement a more reliable and robust system are discussed.

I. INTRODUCTION

The exploration problem is considered as one of the fundamental problems in autonomous mobile robotics. The exploration task refers to achieve the complete coverage of a previously unknown environment [START_REF] Burgard | Coordinated multi-robot exploration[END_REF]. Currently, there are several real scenarios where achieving the whole exploring of a zone is one of the main parts of the mission. Some of them are: planetary exploration, reconnaissance, rescue, agriculture, cleaning or the exploration of dangerous places as mined lands and radioactive zones [START_REF] Bautin | Stratégie d'exploration multirobot fondée sur le calcul de champs de potentiels[END_REF]. Due to their inner qualities (mainly efficiency and robustness), in many cases a multi-robot system is chosen to carry this task out [START_REF] Yan | A Survey and Analysis of Multi-Robot Coordination[END_REF]. Even so, it is not just concerning to add more and more robots. Therefore, in order to conceive a powerful solution it is necessary to deal with coordination strategies and possibly to consider: the environment characteristics and model, member heterogeneity (shape, size, motor and sensory capabilities, etc), task assignment algorithm, mapping approach and last but not least, the underlying communication system.

Outline

The document is organized as follows. Section II briefly presents a general description of the cooperative exploration problem and the main contribution/drawbacks from a set of surveyed proposals. Next, in Section III a problem formalization is presented as well as the main characteristics of a first version of a dual role based approach. Preliminary experiments and results are shown and discussed in Section IV. Finally, conclusions and future works are presented in Sections V and VI.

II. RELATED WORK

A. General formulation

Schematically, the exploration of an environment can be seen as the composition of Mapping and Motion Planning tasks. As a matter of fact, a map is needed in order to plan new motions. On the other hand, to choose a correct motion sequence is needed to optimally expand the knowledge about the environment -represented by the map. As a consequence, mapping is constantly interleaved with motion planning, and vice versa during the whole process [START_REF] Wurm | Coordinated multi-robot exploration using a segmentation of the environment[END_REF], [START_REF] Burgard | Coordinated multi-robot exploration[END_REF], [START_REF] Simmons | Coordination for Multi-Robot Exploration and Mapping[END_REF]. In Fig. 1 the interaction between Mapping, Motion Planning and Localization tasks can be seen. Additionally, the cooperative exploration problem is commonly defined as the full coverage of a previously unknown environment, using a robot team and regarding some optimal criteria [START_REF] Burgard | Coordinated multi-robot exploration[END_REF]. Typically, the overall exploration time is the most commonly used criterion to measure and to compare the proposals quality.

Thus, in the context of multi-robot systems, both mapping and motion planning imply cooperative actions. Obviously, each robot must be able to solve both of them individually. However, they only will be able to take the advantages of working in group if they are also able to keep coordinated during the process. Due to this, in many approaches explicit communication turns into a very important aspect.

B. Tasks assignment task

When multiple robots are involved in an exploration task, avoiding several of them moving to the same place seems to be clever. The task assignment task concerns the choice of new places 1 to visit in a coordinated way. To reach this purpose, is quite often to split the task up into two steps or faces. The first one, called Task Identification, concerns the points of interest identification and it strongly depends on both the sensory robot capabilities and on the underlying environment representation. The second one, called Task Allocation, concerns the search of a distribution of tasks to robots that maximizes the overall system utility and minimizes the amount of overlapped information obtained by all of them [START_REF] Burgard | Coordinated multi-robot exploration[END_REF].

1) Task Identification methods : The most widely used representation for this purpose is the Occupancy Grid structure. Based on it, in 1998 a method to identify interesting points2 in an environment was proposed by Yamauchi [START_REF] Yamauchi | Frontier-based exploration using multiple robots[END_REF]. Since then, the majority of proposals have adopted this proposal leading to a family of solutions which are well known as Frontier Points or Frontier Region based approaches [START_REF] Yuan | A cooperative approach for multi-robot area exploration[END_REF], [START_REF] Sheng | Distributed multi-robot coordination in area exploration[END_REF].

2) Task Allocation methods: There are a wide variety of essayed solutions. Even so, the majority of methods are centralized and usually compute an objective function in order to estimate the utility of reaching each one of the previously identified targets. This function enables a robot to locally prioritize the targets in its scope and potentially enable the whole team to search for the best global distribution [START_REF] Ayorkor Korsah | A comprehensive taxonomy for multi-robot task allocation[END_REF].

One of the most popular centralized method is based on the notion of Auctions3 . Like in [START_REF] Burgard | Coordinated multi-robot exploration[END_REF], [START_REF] Simmons | Coordination for Multi-Robot Exploration and Mapping[END_REF], the allocation decision is processed centrally by a greedy algorithm which considers the bids made by the robots. Those bids are based on local prioritization of the targets (typically, regarding the distance between the current position and every target). Although, this method owes his popularity to be easy to understand and to implement, falling in local minima is its major shortcoming [START_REF] Cavalcante | Improving combinatorial auctions for multi-robot exploration[END_REF].

Thanks to its well known search properties, other authors have used Genetic Algorithms [START_REF] Ma | Genetic algorithm-based multirobot cooperative exploration[END_REF]. The main purpose was to avoid some drawbacks present in other approaches without loosing performance. However, this is also a centralized approach that additionally requires that the number of robots during the whole exploration process remains invariant.

Far from meta-heuristics, in [START_REF] Wurm | Coordinated multi-robot exploration using a segmentation of the environment[END_REF] an operative research based approach is presented. This method combines an environmental segmentation technique 4 with the centralized task allocation method proposed by Kuhn in 1955 [START_REF] Kuhn | The Hungarian method for the assignment problem[END_REF]. The working hypothesis is that in highly structured environments is more convenient to perform the exploration after having divided the environment into disjoint segments. This way, it is expected to achieve full exploration decreasing the sensory overlapping between agents as much as possible.

Recently, a novel approach was fully presented in [START_REF] Bautin | Stratégie d'exploration multirobot fondée sur le calcul de champs de potentiels[END_REF]. It works in a very simple and decentralized way attempting to distribute the robots over the unexplored locations as much as possible. The underlying idea is that if this could be done over time until the end of exploration, the exploration time would be smaller. In practice, the main contribution of this approach consists in providing a better distribution of robots on the terrain decreasing the overall cost of exploration for a big set of practical scenarios.

C. Cooperative mapping

It concerns the ability to build a single global map from the "local" maps that are built by each of the team members separately. Consequently, as well as having the ability to build a map, in order to share information each robot must also be able to communicate with the other ones. However, this possibility could be not always present or, even if it is, it must be defined which are the appropriate moments to exchange information [START_REF] Vidal-Calleja | Eventdriven loop closure in multi-robot mapping[END_REF].

D. Communication

Despite the lack of realism, most of the proposals assume ideal communication conditions 5 . This way the authors can put all attention on higher level problems. However, the resultant algorithms are often either so theoretic or really applicable just on a few set of controlled environments. On the contrary, the team is forced to be close enough in order to be fully communicated all time (for instance, not spreading further than the limits of communication ranges) [START_REF] Tuna | The effects of exploration strategies and communication models on the performance of cooperative exploration[END_REF], [START_REF] Mosteo | Multi-robot routing under limited communication range[END_REF], [START_REF] Vazquez | Distributed Multirobot Exploration Maintaining a Mobile Network[END_REF]. In real scenarios many things may put the ideal working assumption at risk. In open environmentsor simply large ones-the distances among robots could be easily bigger than the scope of communication devices. Depending on the terrain, the robots could be likely to get stuck. When both conditions are present in one environment, the exploration strategy should take it into account in order to prevent robots moving away from the rest for long periods. If it happens and a robot get stuck, all gathered information had been lost, many resources had been wasted (e.g. time and battery) and the zone will need to be explored again by another robot. Thus, some proposals are starting to tackle the exploration problem without assuming the existence of ideal communication [START_REF] Valentin | Motion strategies for exploration and map building under uncertainty with multiple heterogeneous robots[END_REF], [START_REF] Micael | Darwinian swarm exploration under communication constraints: Initial deployment and fault-tolerance assessment[END_REF], [START_REF] Pham | A multi-robot, cooperative, and active slam algorithm for exploration[END_REF], [START_REF] Martijn | Multi-robot exploration under the constraints of wireless networking[END_REF].

III. PROPOSAL

Taking into account the aspects presented above (described in Section II), a specific instance of the cooperative exploration problem is defined in this section. The main objective of the section is to very well define the boundaries of an instance which permits to work on more realistic scenarios as well as the characteristics of a solution proposal. As a consequence several definitions will be given and some real communication constraints will be considered.

A. Robot model

Given a robot team R = {R 1 , R 2 , . . . , R M } consisting of M homogeneous circular rigid differential driven mobile robots, such that every robot is defined by a traditional representation: R i = (x i , y i , θ i , r i , s i , c i ) where i ∈ [1..M ] and x i , y i , θ i represent the configuration of robot over time (position of his center and heading on W ), r i represents the radius of robot body, s i , c i represent the sensory capabilities as maximum radius of sensing and maximum range of communication, respectively.

1) Body model: For each robot a body configuration function is defined as follows bod i : R → R 2 such that:

d i (x, y) = (x -x i (t)) 2 + (y -y i (t)) 2 (1) bod i (t) = {(x, y) | r i ≥ d i (x, y)} (2)
2) Sensory model: For each robot a sensing function is defined as follows sen i : R → R 2 such that:

sen i (t) = {(x, y) | s i ≥ d i (x, y)} (3)
3) Communication model: For each robot a strength signal function is defined as follows com i : R → R such that 6 :

com i (d j ) = -10P Llog 10 (d j /c i ) - nW * W AF nW < C C * W AF nW ≥ C ( 4
)
where PL represents the path loss rate, d j represents the distance between two robot locations: the transmitter (R i ) and receiver (R j ), nW represents the number of walls present between transmitter and receiver, C represents the maximum number of walls considered to model the signal attenuation caused by walls and WAF represents the wall attenuation factor.

In Fig. 2 the shape of the function com i (d j ) can be seen as well as the attenuation effect caused by both the distance between transmitter and receiver and the wall interference. Finally, on W it is possible to define the set of previously unknown static rigid obstacles O j , such that:

O j = {(x, y) ∈ W | state(x, y) = occupied } (5)

C. Global Objective

The objective of exploration will be to achieve the full coverage of an indoor environment, a priori totally unknown, with a team of potentially heterogeneous robots, in minimal time. Equation 6 express the condition that must be reached in order to complete the task.

(Wj O j ) ⊆ i,t sen i (t) (6) where W represents the environment, O j a set of static obstacles and sen i the information sensed by each robot i over time.

D. Utilities and Costs

In order to better adapt the making decision process to real environments, where the system objectives could oppose one another (exploration vs connectivity), a task utility function is defined. This function takes into account both the traveling cost and connectivity utility and its purpose is to find a good balance between them.

1) Path cost: It measures the path cost for a robot to reach a target from its current configuration. A function is defined as follows pathCost i : T → R such that: pathCost i (t j ) = d j (7) where d j is the minimal distance needed to robot R i to travel from its current configuration (x i , y i , θ i ) to the target t j . If d j == ∞ means that the target is unreachable for the robot. This way, the team heterogeneity (regarding size aspect) is taken into account and the system would be able to deal with scenarios where some regions could be inaccessible to some robots.

2) Connectivity Utility: It measures the connectivity utility of a place in terms of how connected would be the robot with the rest of its team members. A function is defined as follows connectivity i : {R} → R such that 7 :

connectivity i ( k =i {R k }) = P p=1 λ p com i (d p ) (8)
where 0 ≤ λ ≤ 1 is a tuning parameter. If λ == 0, then the system does not care about connectivity at all: like in ideal communication scenarios. On the contrary, if λ == 1 then the system would penalize targets that could break the connectivity of the team. Otherwise, the system will consider the connectivity aspect depending on whether λ is closer to 0 or closer to 1. 0 <= P <= | {R k } |, is the amount of robots in a subgroup. {d 1 , d 2 , . . . , d P } is an increasing ordered set of distances between the R i robot location and every other sub-group member R k .

The Fig. 4b shows the result of applying the connectivity i function on the experimental environment shown in Fig. 4a. On it there are three other robots (located in the corresponding peak positions) and several walls. In order to appreciate the behavior of the function, the location of the robot i is set on every single possible position of the environment. 3) Task utility: In order to guide the optimal task distribution search a task utility function is defined as follows utility i : T → [0..1] such that:

utility i (T j ) = -αpathCost i (T j ) + βconnectivity Tj k =i {R k } (9)
where R k represents every potential sub-group member surrounding T j location and α, β ∈ [0..1] are tuning parameters that permit to adjust the kind of solutions the system will search for. If α == β == 0, then the system will behave completely random. Yet, if α == 1 and β == 0 then the system will show a greedy behaviour. On the contrary, if α == 0 and β = 1 then the system will search for solutions according to λ parameter (see Eq. 8). Otherwise, the system will try to balance path costs and connectivity utility depending on the values of α, β and λ.

E. Coordination method

1) Task Identification method: As was mentioned above, a very helpful definition is the notion of task. A task is commonly defined as a location where a robot wants to go to perform his work (in this case, to explore: to sense unknown regions).

Then, a set of tasks T = {T 1 , T 2 , . . . , T N } is defined to represent at each moment, the set of targets that the robot team could be interested in.

Moreover, it is easy to see that in any case, as much closer to the frontier -between known and unknown regions-the tasks are identified as much information the system can gain. Therefore, a task represents a location where there is at least one neighbour point that is unknown yet. Thus, the set of tasks T at any moment is defined as follows:

F P = {(x, y) | (x, y) ∈ W known ∧ (neighbour (x, y) W unknown = ∅)} (10) F R = {(x, y) | (x, y) ∈ F P ∧ is located in the center of FP.} (11) T = {T 1 , T 2 , . . . , T N } = {(x, y) | (x, y) ∈ F R} (12)
As a consequence, free cells (defined in Sec.III-B) could be over labeled as frontier point (FP) or frontier region (FR) depending on whether it represents just a single location or the center of a group of frontier point cells.

2) Task Allocation method: In order to take advantage of the individual computing power of the robots, a decentralized approach is followed. Typically, estimation of costs and utilities as well as local maps building and localization are the tasks chosen to be made by themselves. However, to achieve a cooperative behaviour both the local map and localization information must be shared among teammates. In addition, trying to increase the fault tolerance of the system, loneliness situations will be avoided as much as possible. Thus, every moment the system will intend to explore preserving communication networks as big as possible.

Depending on the relation between |T | and |R| two quite different scenarios could be considered. On the one hand, if |T | < |R|, it will be necessary less robots than the total. To tackle this case a dual role approach is planned but has not been implemented yet. On the other hand, if |T | ≥ |R|, all robots will be necessary in order to reach the maximal amount of targets. In that case, the goal is to choose the distribution of tasks to robots which reports the maximal utility implying the minimal cost. The proposal consists in employing the same allocation criterion as in the minPos approach, but using the task utility function defined in Eq.9 instead of just the path cost. A pseudo-code of the allocation algorithm can be seen in [START_REF] Bautin | Stratégie d'exploration multirobot fondée sur les champs de potentiels artificiels[END_REF].

IV. EXPERIMENTAL RESULTS

In order to have a quantitative measure of the system performance, a comparative study was conducted. The first preliminary experiments concerned the comparison between the results obtained with an own implementation of minPos approach and with this proposal. A team composed by two robots was put to explore a simulated environment with the goal of reaching 95% of coverage. The robots were set up to be 0.25m of radius, having 3m and 6m of sensing radius and communication range, respectively. The total amount of time was measured taking into account the quantity of movements made by the robots. As well as, the connectivity level between team members was measured during the whole process using the function presented in Eq.8. This experiment intents to confirm the hypothesis that introducing the connectivity notion into the making decision process can help to become the system more tolerant to real conditions, particularly nonideal communication conditions. In Fig. 5 the environment 8 used as benchmark is shown. While the red zone represents the free region, dark red zones represent walls and the green cell represents the base from where both robots start the process. In Tab.I some data that describes the overall performance of both approaches are presented. Regarding these data it is possible to notice that exists a conflict of interests between both objectives: minimizing the total amount of exploration time and keeping the connectivity between teammates during the whole process. As long as the minPos approach has been faster, on the other hand, the approach presented here could ensure connectivity during more than 4/5 of the total exploration time.

In Fig. 6 the connectivity level between both teammates during the minPos-based exploration process can be seen. This chart shows that after a first stage where the robots were connected, they loss the connectivity until almost the end. Actually, they stay connected just 43% of the total time. 8 The same environment was used to test the minPos approach in [START_REF] Bautin | MinPos : a Novel Frontier Allocation Algorithm for Multi-robot Exploration[END_REF] In this case is easy to see that if, during the unconnected period, one of them had suffered an irrecoverable failure, the other robot would be forced to explore back a portion of the environment. This would cause the waste of addition resources and the delay on the termination time.

On the other hand, there are two chart where the behavior of this proposal may be analyzed. Firstly, in Fig. 7 the connectivity level reached during the exploration is akin to the one obtained with the minPos approach. This result is totally expected since the alpha value used is very close to 1.0. However, in Fig. 8 the results show a better connected process. Setting the alpha value up to 0.6 caused the balance between objectives was put in favour of connectivity.

V. CONCLUSIONS

The first results obtained in simulated scenarios support the underlying ideas presented in this proposal are feasible and promising. They also show that is possible to cope with real communication constraints (always present in practice), being more fault tolerant and still having good performance regarding the total exploration time.

VI. FUTURE WORK

From the particular formulation of the cooperative exploration problem given in Sec. III, a full development of a Dual Role based approach will be carried out. Two roles will be considered: explorer and relay robots. While explorer robots will be in charge of gathering as much information as they can (and simultaneously serving as communication relay), relay robots must mainly intend to reduce the loss of connectivity among team members (though simultaneously sharing their local maps, they will not be in charge of exploring new places). Another important aspect to be solved is the algorithm to compute the candidates places where the relay-robots could locate itself. Some references have been already found on this matter [START_REF] Stojmenovic | Power-aware localized routing in wireless networks[END_REF], [START_REF] Bose | Routing with guaranteed delivery in ad hoc wireless networks[END_REF]. This way is expected the system might be even more flexible (being more adaptive to a bigger number of scenarios) and for that reason, more efficient (avoiding the presence of idle robots or decreasing the completion time of exploration). After that several new experiments will be conducted. They will consist of both simulated and real environments regarding the metrics suggested in [START_REF] Yan | Metrics for performance benchmarking of multi-robot exploration[END_REF] and comparing the results with other approaches (not only with minPos). The exploration will be carried out in a 2D bounded office-like environment. Robots could be identical or not. The teams could be composed by IRobot or KheperaIII units. Artificial potential field approach could be used in order to conduct motion planning tasks [START_REF] Vallvé | Potential information fields for mobile robot exploration[END_REF], [START_REF] Bautin | Stratégie d'exploration multirobot fondée sur les champs de potentiels artificiels[END_REF], [START_REF] Renzaglia | Potential field based approach for coordinate exploration with a multi-robot team[END_REF]. The connectivity will be limited in range and bandwidth. Additionally, during the simulated experiments information loss could be simulated -under a very strong control-in order to test robustness.

Fig. 1 :

 1 Fig. 1: Sub-problems of exploration.

Fig. 2 :

 2 Fig. 2: Stregth signal model.

Fig. 3 :

 3 Fig. 3: Possible cell states and transitions.

  (a) Experimental environment. (b) Connectivity utility evaluation.

Fig. 4 :

 4 Fig. 4: Connectivity utility function.

Fig. 5 :

 5 Fig. 5: Simulated environment.

Fig. 6 :

 6 Fig. 6: Connectivity level during minPos-based exploration.

Fig. 7 :

 7 Fig. 7: Connectivity level during this-proposal-based exploration.

Fig. 8 :

 8 Fig. 8: Connectivity level during this-proposal-based exploration.

TABLE I :

 I Comparative analysis.

		minPos approach Author's approach
	Duration	89(movs)	149(movs)
	Coverage %	95.409	96.607
	Connection time %	42.697	83.221

Those singular places will be referred along this text as tasks or targets indistinctly.

Points that lies just on the borderline between known and unknown regions.

Although, there is a decentralized version, it is not largely used.

Mostly based on Voronoi diagrams[START_REF] Bhattacharya | Roadmap-Based Path Planning: Using the Voronoi Diagram for a Clearance-Based Shortest Path[END_REF],[START_REF] Wein | The visibility-Voronoi complex and its applications[END_REF],[START_REF] Waldir | Trajectory planning for lab robots based on global vision and Voronoi roadmaps[END_REF].

Without errors nor losses, with unlimited bandwidth and scope.

Adapted from[START_REF] Bahl | RADAR: An In-Building RF-based User Location and Tracking System[END_REF].


Emmanuelle Esperança-Rodier

Johan Didier
email: rodier@univ-grenoble-alpes.fr

Translation Quality Evaluation of MWE from French into English using an SMT system

Nowadays, Statistical Machine Translation (SMT) is widely available. Nevertheless, using Machine Translation at its best is not an easy task. Structures appearing sporadically trigger most of the regular mistakes of SMT systems. We work on one of those structures: the MultiWord Expressions (MWE).

Our study aims at evaluating the quality of MWE translation obtained using SMT.

. Thirdly, we analyse the global results of our quality evaluation before going into details, in our fourth part, on one particular type of MWE, which is the Full Phraseme one. We finally show that most of the French MWE are translated into English MWE, and that we need to implement in further work a collaborative error annotation tool.

Introduction

Machine Translation (MT) nowadays is widely available for a large set of people; professional translators, students, researchers, common people. Nevertheless being able of using MT at its best is not an easy task. Most of the MT systems make regular mistakes, which means that there are typical syntactic structures, lexical items they cannot deal properly with. Therefore, the end user has to be able to detect and to correct those mistakes. The ability of the user to detect and correct the mistakes relies on his/her language skills, which means that some people would have the necessary skill to detect that the sentence is not grammatically correct and would correct it, but some others would not know how to correct it. The language skill level related to the post edition of MT is an interesting topic, which we won't discuss in this paper for a matter of length.

If we go back to the mistakes themselves, some of them are due to the fact that as MT systems use probabilistic algorithm they cannot focus on structures that does not appear very often. In this article, we are going to take this problem into account and thus deal with one of those structures that are the MultiWord Expressions (MWE). MWE are very common but not always in proportions that are sufficient for MT to give successful translations. However, as MWE are typical of the language, if they are mistranslated, the end user would consider the whole translation as a poor one even if it is not the case. Among others, previous work from [START_REF] Ramisch | How hard is it to automatically translate phrasal verbs from English to French?[END_REF] on one type of MWE has already depicted the complexity of MWE translation.

We have to keep in mind that, in this work, only the quality of the MWE translation has been addressed. Consequently, the information of a sentence not being translated correctly is not given.

In order to study the quality of MWE translation, we based our work on the analysis of a corpus.

Our corpus is made of one technical document (12,566 words) written in French on which MWE have been semi-automatically annotated according to their type. As we based our work on a linguistic approach, we used a script to locate the more obvious MWEs, which we validated or not, and then we manually annotated those which were not found automatically or for which the type was not so clear-cut. This way we were able to refine the MWE type definitions as well as work on the inter annotator agreement. We have thus decided on purpose not to use automatic tools such as [START_REF] Ramisch | mwetoolkit: a Framework for Multiword Expression Identification Proceedings of the International Conference on Language Resources and Evaluation[END_REF] proposed.

Methods

MWE annotation

We semi-automatically annotated, as we said, the MWE present in our corpus according to nine types described in [START_REF] Tutin | Annotation of multiword expressions in French[END_REF]. In this previous paper, MWE were addressed as "multiword elements that includes several graphical units, separated by blanks or hyphens, or separated by several other words not included within the MWE".

Out of those nine types, we decided to focus on five of them, which are the following ones:

• Function words (F),

• Full Phrasemes (PH),

• Collocations (C),

• Technical Terms (T) and

• Named Entities (EN). [START_REF] Tutin | Annotation of multiword expressions in French[END_REF] defined those five types in a draft of Annotation guidelines for multi-word expressions. In the interests of brevity, we will just give a rough definition for each of the five types here.

First, Function words are characterized by a vague, and mainly functional, meaning. They include grammatical words such as conjunctions e.g. even if, or among others, prepositions e.g. in front of.

Second, Full Phrasemes include MWEs which are not compositional, e.g. couch potato, and/or are words, mainly nouns, which refer to specific referent, e.g. death penalty.

Collocations include frequent compositional expressions, e.g. heavy smoker. Technical Terms, a subtype of full phrasemes, are mainly nominal full phrasemes typical of specialized corpora.

On top of the type, the MWE annotation also consists of the part of speech of the MWE, the part of speech of the elements of the MWE, and the overlapping of MWE is also annotated… The French annotated document has been translated into English by a MT system created using Moses Toolkit [START_REF] Koehn | Moses: Open source toolkit for statistical machine translation[END_REF]. Furthermore, we have decided that the quality evaluation of the obtained translation, would not be done via automatic metrics but using more linguistics criteria such as those defined in (Vilar et al., 2005), which we are going to describe in the following section.

Error type classification

Actually, the criteria used in Vilar's classification of translation errors, as described in Figure 1, suit pretty well the linguistic evaluation we want to perform.

Five main translation error categories have been identified, namely:

• Missing Words, for words which have not been translated,

• Word Order, for a wrong order of the words in the translated sequence,

• Incorrect Words, for a mistranslation,

• Unknown Words, for words that were not known by the system and thus left in the source language,

• Punctuation, when punctuation rules of the target language were not respected.

As regards to the first two translation-error categories, Missing Words and Word Order, subcategories have been created to refine the error class. For the Missing Words error category, the distinction between Content and Filler words allows to see whether the missing word was meaningful or not. This subcategory illustrates the fact that the full meaning of the sentence was kept or not, which is obviously the aim of a quality translation evaluation. As regards to the Word Order error category, the Word or Phrase level subcategory shows if the translation error entails a reordering of the words themselves, or a reordering of phrases. It is well addressed to SMT evaluation as it permits to locate at which level the system failed, lexical level or syntactic level.

Looking at the third translation error category, Incorrect words, we can see that there are several subcategories aiming at distinguishing the reason of the mistranslation, which can be due to the fact that the system was not able to disambiguate properly the meaning of a source word nor to produce the right form of the word, although the base form of the word was well translated.

For the fourth translation error category, Unknown words, we can distinguish whether the stem of the words was known by the system or not.

And finally, the fifth translation error category, which is Punctuation, did not receive full attention from our part.

In addition, the part of speech of the word linked to the translation error category or subcategories, is also given. Thanks to Vilar's classification we were able to undergo a rich translation error annotation.

However, we wanted to track some more pieces of information. We have therefore added to the Vilar's classification the four following features. Hereafter, we will describe those additional features by defining them and giving their annotation abbreviation.

Firstly, we added the type of the MWE. The annotation of MWE in the source document was already giving that information, but due to technical difficulties we were not able to recover that information after translation. This is why we have decided to integrate the type of MWE into the translation error categories at the first level that is to say prior to any translation error category. We have used the abbreviation given in paragraph 2.1, e.g. EN for Named Entities…

Secondly, as we wanted to focus tightly to the translation quality evaluation of MWE, we wanted to refer to in-use translations of MWE. Consequently, for the most frequent MWE found in our source corpus, we have extracted from the bilingual concordancer Tradooit (https://www.tradooit.com), the related translations, considering them as the attested translations. We have thus integrated a category showing that the translation of the MWE was an attested one or not. We used the TA abbreviation when the translation was attested and the TNA abbreviation when it was not an attested translation.

Thirdly, we addressed the translation quality criteria by distinguishing four quality levels. When the source MWE was well translated, we used the BT abbreviation. When the source MWE was wrongly translated then we used the abbreviation MT for wrong translation. Then when the translation had to be edited but the meaning of the source sentence was kept, we used the abbreviation RevPres. And when the translation had to be edited but the meaning of the source sentence was not kept, we used the RevNPres abbreviation.

Finally, we wanted to annotate the fact that the translation was also a MWE in the target language, or not. We respectively used the abbreviations MULT and NONMULT. Consequently, Vilar's classification of translation errors has been extended to this scheme, Figure 2:

Evaluation tool

The English translation has then been evaluated using BLAST [START_REF] Stymne | Blast: A tool for error analysis of ma-chine translation output[END_REF], an open source tool for the annotation of translation errors. We have chosen this tool as it has already been used for former MWE translation evaluation; and that it uses as a standard, and among others, the Vilar's Classification of translation errors, even if it can be used with any other hierarchical error classifications. Blast is also highly adapted to any evaluation purposes as it is not linked to the information provided by any specific MT. Furthermore, Blast is easy to use because of its graphical interface. Among all the above, we have seen in the way to add new annotations, edit existing annotations and also to search among the annotations.

Nevertheless we have experienced mainly two kinds of problems with the evaluation criteria. Firstly, we have encountered the borderline case of annotating several MWE in a same sentence. When several MWEs were present in a same sentence, it was impossible for us to link the translation error category respectively to the related MWE.

Secondly, as Blast ignores identical annotation, it seems impossible to have access to several error types at the same time for the same MWE. Also because of the hierarchical structure of the tool, we had to declare all the possible path of translation error annotation, thus having a linear path.

Figure 3. Blast Screenshot

The translation error annotation has thus been difficult. We could also mention that as the annotator has to make a decision, he cannot use the tool to trigger the attention on a difficult MWE to annotate thus asking for some help from another annotator. The possibility of having a collaborative tool would have been greatly appreciated for the MWE quality translation evaluation.

Results

Global results

Once the English translation evaluated, we have been looking at the global results which we have collected in Table 1 andTable 2 As previously mentioned, out of the nine types of MWE, we have only worked on five of them. Those five types of MWE are represented thanks to their abbreviation, see above section 2.1, in the first column of Figure 4.

Back to Table 1, if we look at the total number of occurrences per MWE type, it appears that we have mainly found in our corpus the Collocation type (C), with 308 occurrences. While the type of MWE we have found in the smallest quantity is the Named Entities (EN), 9 occurrences. Nonetheless, the ratio of bad translation over the not attested translation (MT/TNA), given in the eighth column, for EN is the highest with 100%. It means that when a MWE of the Named Entity type has been translated by a non attested translation it was also always a bad translation.

On the contrary, when a MWE of the Technical Term Type (T) was translated by an attested translation, it was always a good translation. The ratio good translation over attested translation, BT/TA, is 100% as mentioned in column number 5.

As a validity control, when an attested translation was given, it has never been a bad translation. The ratio MT/TA, appearing in the seventh column, is 0% for any type of MWE. In the same way, for validity control, we can notice on Table 2 that for an attested translation given, no translation evaluated to be edited with the meaning not being kept were found. For all the MWE types, the ratio RevNPres/TA, given in the seventh column, equals 0.

MWE type

Total number of occurrences

Attested

Detailed results focusing on Full phrasemes

We have decided to focus on the Full Phraseme type as they are the most difficult MWE to understand for non-native speakers. In the following, we are going to cover specific columns of Table 1 andTable 2, explaining the results by giving five examples, made of the French source, and of the English SMT Translation, and also of the related error annotation path for each example.

Actually, referring Table 1, we find that 64%, see third column, of the Full Phrasemes were correctly translated, as we can see in the example 1. We can notice in that first example that the whole translated sentence is not correctly translated. As we already said, we have only processed to the quality evaluation of the MWEs, not to the evaluation of the whole sentence. In the fifth column of Table 1, we can see that more than 96% of Full Phraseme MWEs have been well translated when an attested translation existed. This result corresponds to the trend of the whole study. Nevertheless, roughly 6%, as written in the sixth column, of the Full Phraseme MWEs were well translated while the translation was not one of the attested ones.

If we look at the example 2 below, the Full Phraseme faire état has not been translated in one of its attested translation but even so, it has been well translated by to present. 2, we notice in the fifth column, that 1% of the translations has been evaluated as needing to be edited while the meaning was kept when an attested translation existed. Actually, example 3 shows that the Full Phraseme mis en oeuvre has been correctly translated as regards to its attested translation and meaning, but that its form was incorrect as the passive voice to be implemented was used in the translation while it should not. Going to the next column, it emerges that a bit less that 19% of the translations have been evaluated as needing to be edited while the meaning was kept when the translation was not an attested one. As shown in Example 4, the Full Phraseme MWE pris en charge has not been translated by one of its attested translation, and that the translation proposed, i.e. taken over has taken the wrong lexical choice. 2, only 8% of the translations have to be edited when it was not an attested translation of the Full Phraseme MWE. The Full Phraseme MWE en bout de ligne has been translated into at the end of the line and thus evaluated as needing to be edited with the meaning not being respected because of the use of Incorrect Words due to an Incorrect Disambiguation related to the Sense subcategory. It would have been useful to check if the same MWE appeared several time in the document to verify the translation consistency. Is the MWE always translated in the same way, according to its place in the sentence, or to the syntactic pattern in which the MWE has been found? As Blast only allows to search for error categories, and that it does not permit to search for words or patterns, we could not proceed to such an investigation.

Conclusion

As a first conclusion, we have found that 80% of the MWE found in the French text were translated into MWE in English. As regards to the studied MWE types, the good translation rate is acceptable, showing that work has to be done in order to improve it.

As our corpus is not really big, one text of roughly 12,500 words, we want to draw the reader attention to the fact that this work is a first investigation of the MWE translation quality. Also, for some translation error annotations, the error annotation path was really long and thus some inconsistencies could arise.

Our second conclusion is then, that we would need another tool specifically dedicated to translation error annotations, with the possibility of selecting the source text and its target translation and to assign a translation error type. It will help identifying patterns in which specific translation error categories occur more often.

An extended work will thus consist in specifying a new collaborative tool dedicated to translation error annotation. Finally, a further work will be dedicated to deeply look at the quality translation results of the different MWE types studied.

Figure

  Figure 2. Extended Classification

  Example 1 French: […] leur statut d'embauche plus précaire fait en sorte qu'ils sont soumis à une forte pression […] English SMT Translation: […] their status of employment more precarious done in such a way that they are under pressure […] Error Annotation path: ph-TA-BT-MULT

  …] nous allons ensuite faire état des méthodes […] English SMT Translation: […] then we are going to present the methods […] Error Annotation path: ph-TNA-BT-MULT Going further in Table

  …] et les principales adaptations requises mises en oeuvre […] English SMT Translation: […] and the major adaptations required to be implemented […] Error Annotation path: ph-TA-REV_PRES-MULT-NONM-NONO-INC-FORME-NONU-NONPCT

  …] la mécanisation et l' automatisation des procédés de travail dans l' industrie manufacturière ont été prises en charge par la production à la chaîne […] English SMT Translation: […] the mechanisation and automation of working processes in the manufacturing industry have been taken over by the production of the chain […] Error Annotation path: ph-TNA-REV_PRES-MULT-NONM-NONO-INC-SENS-LEX-NONU-NONPCT In the last example, and referring to the last column of Table

  Example 5 French: mais en bout de ligne […] English SMT Translation: but at the end of the line […] Error Annotation path: ph-TNA-REV_NONPRES-MULT-NONM-NONO-INC-SENS-DESAMB-NONU-NONPCT

Table 1 :

 1 below. Global results for 5 MWE types on Good Translation

	MWE	Total	Attested	Good	Good	Good	Bad	Bad
	type	number of	Translation	Translation	Translation/	Translation/Non	Translation/	Translation/
		occurrences	TA	BT	Attested	Attested	Attested	Non
					Translation	Translation	Translation	Attested
					BT/TA	BT/TNA	MT/TA	Translation
								MT/TNA
	PH	135	64,4	64,4	96,6	6,3	0	66,7
	C	308	63,3	72,1	96,9	29,2	0	22,1
	F	202	78,2	81,2	98,1	20,5	0	36,4
	EN	9	77,8	66,7	85,7	0	0	100
	T	51	58,8	64,7	100	14,3	0	28,6

Translation TA Good Translation BT

					Translation	Translation to	Translation	Translation to
					to be edited	be edited but	to be edited	be edited but
					but source	source meaning	but source	source
					meaning	kept /Non	meaning not	meaning not
					kept/	Attested	kept/Attested	kept/Non
					Attested	Translation	Translation	Attested
					Translation	RevPres/TNA	RevNPres/TA	Translation
					RevPres/TA			RevNpres/TNA
	PH	135	64,4	64,4	1,1	18,8	0	8,3
	C	308	63,3	72,1	1,5	32,7	0	13,3
	F	202	78,2	81,2	1,3	40,9	0	2,3
	EN	9	77,8	66,7	0	0	0	0
	T	51	58,8	64,7	0	47,6	0	9,5

Table 2 :

 2 Global results for 5 MWE types on Translation to be edited

Acknowledgements

This work has benefited from the AIM-WEST project (http://aim-west.imag.fr), which deals with the analysis and integration of MultiWord Expressions (MWEs) in speech and translation.


Mario Levorato
email: mlevorato@ic.uff.br

Lúcia Drummond

Yuri Frota

Rosa Figueiredo
email: rosa.figueiredo@univ-avignon.fr

GPGPU, VND Palavras Chave Cuda

A GPU-accelerated local search algorithm for the Correlation Clustering problem

Keywords: GRASP, ILS, Correlação de Clusters KEYWORDS. CUDA, GPGPU, VND, GRASP, ILS, Correlation Clustering. Main Area: MH -Metaheuristics

como medida do nível de equilíbrio em redes sociais de sinais, onde interações positivas (amizade) e negativas (antagonismo) estão presentes. Metaheurísticas

Introduction

Structural (or social) balance is considered a fundamental social process. It has been used to explain how the feelings, attitudes and beliefs, which the social actors have towards each other, can promote the formation of stable (but not necessarily conflict-free) social groups. The balance of a social system tends to follow the human tendency to preserve a cognitive consistency of hostility and friendship. The principle is simple: "my friend's friend is my friend, my friend's enemy is my enemy, my enemy's friend is my enemy, my enemy's enemy is my friend" [START_REF] Heider | Attitudes and cognitive organization[END_REF]. Absence of balance creates a kind of tension in the group members' minds that can eventually lead to changes in their opinions. Once balance is achieved, it tends to be stable, since no cognitive dissonance could change the state [START_REF] Hummon | Some dynamics of social balance processes: bringing heider back into balance theory[END_REF].

Determining the structural balance of a signed social network has been a key aspect in the study of the structure and origin of tensions and conflicts in a network of individuals whose mutual relationships are characterizable in terms of friendship and hostility. Structural balance theory was first formulated by [START_REF] Heider | Attitudes and cognitive organization[END_REF] with the purpose of describing sentiment relations between people pertaining to a same social group (like/dislike, love/hate, trust/distrust). Signed graphs were then introduced by [START_REF] Cartwright | Structural balance: A generalization of heiders theory[END_REF], who formalized Heider's theory stating that a balanced social group could be partitioned into two mutually hostile subgroups each having internal solidarity. In the last decades, signed graphs have shown to be a very attractive discrete structure for social network researchers [START_REF] Doreian | A partitioning approach to structural balance[END_REF][START_REF] Inohara | On conditions for a meeting not to reach a deadlock[END_REF][START_REF] Yang | Community mining from signed social networks[END_REF][START_REF] Abell | Structural balance: a dynamic perspective[END_REF]Doreian and Mrvar, 2009;Facchetti et al., 2011). Different criteria and solution approaches have been used in the literature so as to quantify and evaluate balance in a signed social network (Doreian and Mrvar, 2009;[START_REF] Leskovec | Signed networks in social media[END_REF]Facchetti et al., 2011;[START_REF] Santos | Local balancing influences global structure in social networks[END_REF].

Clustering is the action of partitioning individual elements into groups based on their similarity. Clustering problems defined on signed graphs arise in many scientific areas [START_REF] Bansal | Correlation clustering[END_REF][START_REF] Gülpinar | Extracting pure network submatrices in linear programs using signed graphs[END_REF][START_REF] Dasgupta | Algorithmic and complexity results for decompositions of biological networks into monotone subsystems[END_REF][START_REF] Traag | Community detection in networks with positive and negative links[END_REF][START_REF] Huffner | Separator-based data reduction for signed graph balancing[END_REF][START_REF] Macon | Community structure in the united nations general assembly[END_REF][START_REF] Levorato | Uma metaheurística iterated local search aplicada ao problema de correlação de clusters[END_REF]. The common element among these applications is the collaborative vs. conflicting environment in which they are defined. The solution of clustering problems defined on signed graphs can be used as a criteria to measure the degree of balance in social networks (Doreian andMrvar, 1996, 2009;Figueiredo and Moura, 2013). By considering the original definition [START_REF] Heider | Attitudes and cognitive organization[END_REF] of structural balance, the optimal solution of the very known Correlation Clustering (CC) Problem [START_REF] Bansal | Correlation clustering[END_REF] arises as a measure for the degree of balance in a social network. Alternative measures to the structural balance and the clustering problems associated with them have also been recently discussed (Doreian and Mrvar, 2009;Figueiredo and Moura, 2013).

From a practical point of view, in solving the clustering problem treated in this paper, heuristic approaches are primarily of interest, since large social networks may have to be analyzed [START_REF] Kunegis | The slashdot zoo: mining a social network with negative edges[END_REF][START_REF] Leskovec | Signed networks in social media[END_REF]Facchetti et al., 2011). For example, online networks with two opposite kinds of relationships are nowadays very common. Slashdot, a technologyrelated news website, includes a feature which allows users to tag each other as friends or foes, thus allowing users to rate other users negatively. On online review websites such as Epinions users can either like or dislike other people's reviews. This behavior can be modeled as a signed network, where edge weights can be either greater or less than 0, representing positive or negative relationships respectively. The definition of a measure to represent the imbalance of a social network adds itself a degree of approximation to the task of evaluating balance in a social network. Thus, it is imperative that the clustering problem associated with this measure be solved efficiently.

To our knowledge, there are three metaheuristic approaches applied to the CC problem. [START_REF] Zhang | Correlation clustering based on genetic algorithm for documents clustering[END_REF] proposes genetic algorithms to the CC problem, with an application to document clustering. This strategy was impossible to reproduce though, for the absence of information about how the genetic operators are applied. Drummond et al. (2013) presents a Greedy Random-ized Adaptive Search Procedure (GRASP) (Feo and Resende, 1995) implementation capable of efficiently solving the problem in networks of up to 800 vertices. Later, based on this work, [START_REF] Levorato | Uma metaheurística iterated local search aplicada ao problema de correlação de clusters[END_REF] introduced an Iterated Local Search (ILS) [START_REF] Lourenço | Iterated local search[END_REF] metaheuristic for the CC problem, which outperformed, in processing time, the GRASP metaheuristic proposed earlier, with similar or improved solution quality. By observing the great amount of time spent on the processing of larger graphs, we saw an opportunity to extend the aforementioned GRASP and ILS algorithms with a new implementation of local search that can solve the problem faster.

In this work, we present a parallel local search procedure for the CC problem, accelerated by General Purpose Graphics Processing Units (GPGPUs). Then, by applying the proposed local seach in the GRASP and ILS metaheuristics, we show the improvements over the existing sequential local search procedure. The paper is organized as follows. Section 2 presents the Correlation Clustering problem, including a mathematical formulation and a literature review of it. Section 3 describes the parallel local search algorithm for the CC problem that runs on the GPU, while Section 4 lists the experimental results of it as well as a comparison with other available solution approaches. Finally, Section 5 presents our concluding remarks.

The CC problem

Correlation Clustering [START_REF] Bansal | Correlation clustering[END_REF] is a clustering technique motivated by the problem of document clustering, in which given a large corpus of documents such as web pages, one wants to find their optimal partition into clusters. The problem consists of minimizing the number of unrelated pairs that are clustered together, plus the number of related pairs that are separate. In this section, we formally describe the CC problem and present a mathematical formulation of it, followed by a literature review.

Mathematical Formulation

Let G = (V, E) be an undirected graph where V is the set of n vertices and E is the set of edges. In this text, a signed graph is allowed to have parallel edges but no loops. Also, we assume that parallel edges always have opposite signs. For a vertex set S ⊆ V , let E[S] = {(i,j) ∈ E | i,j ∈ S} denote the subset of edges induced by S. For two vertex sets S, W ⊆ V , let E[S : W ] = {(i,j) ∈ E | i ∈ S, j ∈ W }. One observes that, by definition, E[S : S] = E[S]. Consider a function s : E → {+, -} that assigns a sign to each edge in E. An undirected graph G together with a function s is called a signed graph. An edge e ∈ E is called negative if s(e) =and positive if s(e) = +. Let E -and E + denote, respectively, the set of negative and positive edges in a signed graph.

A partition of V is a division of V into non-overlapping and non-empty subsets. Consider a partition P = {S 1 ,S 2 , . . . ,S l } of V . The cut edges and the uncut edges related with this partition are defined, respectively, as the edges in sets

∪ 1≤i<j≤l E[S i : S j ] and ∪ 1≤i≤l E[S i ].
Let w e be a nonnegative edge weight associated with edge e ∈ E. Also, for 1 ≤ i, j ≤ l, let

Ω + (S i ,S j ) = e∈E + ∩E[S i :S j ] w e and Ω -(S i ,S j ) = e∈E -∩E[S i :S j ] w e .
The imbalance I(P ) of a partition P is defined as the total weight of negative uncut edges and positive cut edges, i.e.,

I(P ) = 1≤i≤l Ω -(S i ,S i ) + 1≤i<j≤l Ω + (S i ,S j ).
(1)

Likewise, the balance B(P ) of a partition P can be defined as the total weight of positive uncut edges and negative cut edges. Clearly, B(P ) + I(P ) = e∈E w e . That being said, we are ready to give a formal definition to the CC problem.

Problem 2.1 (CC problem) Let G = (V,E,s) be a signed graph and w e be a nonnegative edge weight associated with each edge e ∈ E. The correlation clustering problem is the problem of finding a partition P of V such that the imbalance I(P ) is minimized or, equivalently, the balance B(P ) is maximized.

Observe that the given definition comprises a weighted version of the problem. To obtain a nonweighted version, it suffices to make w e = 1, for each e ∈ E.

The classical mathematical formulation for the CC problem is an integer linear programming (ILP) model proposed to uncapacitated clustering problems [START_REF] Mehrotra | Cliques and clustering: A combinatorial approach[END_REF]. In this formulation a binary decision variable x ij is assigned to each pair of vertices i,j ∈ V , i = j, and defined as follows: x ij = 0 if i and j are in a common set; x ij = 1 otherwise. The model minimizes the total imbalance.

minimize (i,j)∈E - w ij (1 -x ij ) + (i,j)∈E + w ij x ij
(2)

subject to x ip + x pj ≥ x ij , ∀ i,p,j ∈ V, (3)
x ij = x ji , ∀ i,j ∈ V, (4) x ij ∈ {0,1}, ∀ i,j ∈ V. (5)
The triangle inequalities (3) say that if i and p are in a same cluster as well as p and j, then vertices i and j are also in a same cluster. Constraint (4) written to i,j ∈ V establishes that variables x ij and x ji assume always the same value in this formulation. Constraints (5) impose binary restrictions to the variables while the objective function (2) minimizes the total imbalance defined by equation ( 1).

Even though this formulation is polynomial-sized, having n(n-1) variables and n 3 +n 2 constraints, notice that, according to constraints (4), half of the variables can be eliminated, which reduces both the number of variables and constraints of the formulation. A set partitioning formulation [START_REF] Mehrotra | Cliques and clustering: A combinatorial approach[END_REF] is proposed in the literature to uncapacitated clustering problems and could also be used in the solution of the CC problem. As we can expect, these two formulations are not appropriate solution approaches when time limit is a constraint in the solution process. The authors in Figueiredo and Moura (2013) report that the classical formulation starts to fail (time limit set to 1h) with random instances of 40 vertices and negative density equal to 0.5.

Literature Review

To the best of our knowledge, the CC problem, as defined in the previous section, was addressed for the first time in [START_REF] Doreian | A partitioning approach to structural balance[END_REF] (not under this name) where its heuristic solution was used as a criteria for analyzing structural balance in social networks. The heuristic approach proposed by the authors is a simple greedy neighborhood search procedure that assumes a prior knowledge of the number of clusters in the solution. This heuristic is implemented in software Pajek [START_REF] Batagelj | Pajek wiki[END_REF]. Lately, motivated by the solution of a document clustering problem, the unweighted version of the CC problem was formalized in [START_REF] Bansal | Correlation clustering[END_REF]. The weighted version of the problem was addressed in [START_REF] Demaine | Correlation clustering in general weighted graphs[END_REF]. The CC problem has been largely investigated from the point of view of constant factor approximation algorithms and has been applied in the solution of many applications, including portfolio analysis in risk management [START_REF] Huffner | Separator-based data reduction for signed graph balancing[END_REF]), biological systems (DasGupta et al., 2007;[START_REF] Huffner | Separator-based data reduction for signed graph balancing[END_REF], efficient document classification [START_REF] Bansal | Correlation clustering[END_REF], detection of embedded matrix structures [START_REF] Gülpinar | Extracting pure network submatrices in linear programs using signed graphs[END_REF] and community structure [START_REF] Traag | Community detection in networks with positive and negative links[END_REF][START_REF] Macon | Community structure in the united nations general assembly[END_REF].

A comparison of several heuristic strategies (greedy and local search methods) for the problem is presented in Elsner and Schudy ( 2009) and applied to document clustering and natural language processing (instances of n = 1000), to which ILP does not scale. In this context, the authors' recommended strategy for solving the CC Problem is a greedy algorithm called V OT E/BOEM , which can quickly achieve good objective values with tight bounds.

In [START_REF] Yang | Community mining from signed social networks[END_REF], the CC problem is called community mining and an agent-based heuristic is proposed to its solution. As far as we know, there are three metaheuristic approaches applied to the CC problem. A solution based on genetic algorithms has been proposed in [START_REF] Zhang | Correlation clustering based on genetic algorithm for documents clustering[END_REF] for the CC problem and applied to document clustering, but unfortunately there is no explanation about how the genetic operators are applied, making it difficult to understand and reproduce the proposed algorithm. Recently, Drummond et al. ( 2013) presented a GRASP (Feo and Resende, 1995) implementation that provides an efficient solution to the CC problem in networks of up to 8000 vertices. Later on, [START_REF] Levorato | Uma metaheurística iterated local search aplicada ao problema de correlação de clusters[END_REF] introduced an ILS [START_REF] Lourenço | Iterated local search[END_REF] metaheuristic for the CC problem, which outperformed, in processing time, the GRASP metaheuristic proposed earlier, with similar or improved solution quality.

Parallelizing local search for the CC problem in the GPU

Our work started with an analysis of two existing metaheuristics for the CC problem. Drummond et al. ( 2013) report the results obtained with sequential and parallel GRASP procedures. The algorithm was implemented in C++ with MPI for message passing (Gropp et al., 1999). Then, based on this work, [START_REF] Levorato | Uma metaheurística iterated local search aplicada ao problema de correlação de clusters[END_REF] later introduced an ILS metaheuristic for the CC problem, which outperformed, in processing time, the GRASP algorithm proposed earlier, with similar or improved solution quality.

By observing the great amount of time spent on the local search phase of the aforementioned algorithms (Figure 1), we saw an opportunity to improve their performance by extending both of them with a new implementation of local search, which is capable of solving the problem faster, without altering the behavior of the metaheuristic. In this section we present a local search procedure for the CC problem that uses the parallelism offered by GPGPUs.

Using General Purpose GPUs to solve optimization problems

The use of Graphics Processing Units (GPUs) has been extended to a wide range of application domains (e.g. computational science) thanks to the publication of the CUDA (Compute Unified Device Architecture) development toolkit (NVIDIA, 2015), which allows GPU programming in C-like language. When used as general-purpose computing devices, GPUs can efficiently accelerate many non-graphics programs, especially vector-and matrix-based codes that exhibit lots of parallelism with low synchronization requirements. Because their hardware is primarily designed to perform complex computations on blocks of pixels at high speed and with wide parallelism, GPU architectures differ substantially from conventional CPU hardware. Therefore, writing efficient programs to solve combinatorial optimization problems on GPUs is not a straightforward task and requires a huge effort not only at design but also at implementation level. Indeed, several challenges mainly related to the hierarchical memory management have to be dealt with. The major issues consist of efficient distribution of data processing between CPU and GPU, thread synchronization, optimization of data transfer between the different memories, as well as the capacity constraints of these memories [START_REF] Van Luong | Gpu computing for parallel local search metaheuristic algorithms[END_REF].

Whenever parallel algorithms are applied to solve optimization problems, it is worth noticing that, in general, for distributed architectures (like MPI), the global performance in metaheuristics is limited by high communication latencies. However, in GPU architectures, performance is bounded by memory access latencies. This being said, several works have already demonstrated the potential speedups when using GPUs to accelerate metaheuristics. For example, GRASP, ILS and EA algorithms have been already adapted to use local search procedures implemented in GPGPU. 3.2. GPGPU architecture and the CUDA programming model CUDA has made possible the development of algorithms to solve time-consuming problems using the large number of parallel multiprocessors as well as the high memory bandwidth provided by GPUs. To accomplish high-performance computing, it is necessary to develop parallel algorithms that are partially or totally executed on the GPU. The CUDA-enabled graphics cards are composed of multiple processors, more specifically, Single Instruction Multiple Data (SIMD) processors called Stream Multiprocessors (SMs), which allow the execution of multiple parallel threads. Thus, GPU processors can efficiently execute instructions involving operations with data parallelism, when the same operation is applied to different data.

Depending on the algorithm, GPUs can provide greater processing power than CPUs because they are specialized in performing parallel tasks involving many calculations. On the other hand, the CPUs are designed to perform tasks involving execution flow control and data cache. The physical difference between both architectures can be visualized in Figure 2: GPUs dedicate most of their area for processing units (in green), while CPUs dedicate most of their area for execution control and data cache (in yellow and orange, respectively).

A CUDA application consists in code that is executed on CPU and functions (called kernels) that are executed on GPU. The GPU is able to do parallel processing by creating threads such that each thread may execute the kernel operations on different data. This way, the GPU is used as a coprocessor to perform certain tasks more efficiently than the CPU.

In CUDA, the processing units (cores) are grouped to share a single instruction unit, so that threads mapped on these cores execute the same instruction each cycle, but on different data. Each logical group of threads sharing instructions is called a warp. Moreover, threads belonging to different warps can execute different instructions on the same cores, but in a different time slot. In practice, CUDA cores are time-shared between warps, and a group of threads in a warp performs as a SIMD unit.

That said, modern GPU architectures relax SIMD constraints by allowing threads in a given warp to execute different instructions. However, these varying instructions cannot be executed concurrently, since each SIMD unit must execute the same instruction on all cores. This way, the instructions are serialized in time, which severely degrades performance. This advanced feature is called SIMT (Single Instruction Multiple Threads) and provides increased programming flexibility by deviating from SIMD at the cost of performance. Threads executing different instructions in a warp are said to diverge; if-then-else statements and loop-termination conditions are common sources of divergence.

Another major concern about CUDA implementation which greatly impacts performance is memory access. Bottlenecks can appear not only during data transfer between host (CPU) and device (GPU) memory, but also during memory access on the device; namely, data locality is very important. Depending on the accessed addresses, concurrent memory requests from multiple threads from a warp can exhibit three possible behaviors:

• Requests targeting the same address are merged to be one unless they are atomic operations.

In the case of write operations, the value actually written to memory is nondeterministically chosen from among merged requests;

• Requests exhibiting spatial locality are maximally coalesced. For example, accesses to addresses i and i + 1 are served by a single memory fetch, as long as they are aligned;

• All other memory requests (including atomic ones) are serialized in a nondeterministic order.

This last behavior, often called the scattering access pattern, greatly reduces memory throughput, since each memory request utilizes only a few bytes from each memory fetch.

The CUDA programming model includes the notion of shared memory and thread blocks, a reflection of the underlying hardware architecture as shown in Figure 2. All threads in a thread block can access the same shared memory, which provides lower latency and higher bandwidth access than global GPU memory but is limited in size. Threads in a thread block may also communicate with each other via this shared memory.

Modifying the search algorithm to run in the GPU

Our approach to parallelize the local search procedure followed the Iteration-level Parallel Model [START_REF] Van Luong | Gpu computing for parallel local search metaheuristic algorithms[END_REF]. As can be seen on Figure 3, the evaluation of the neighborhood is made in parallel. At the beginning of each iteration, the master thread, that runs on the CPU, duplicates the current solution, which is made available to all threads of the GPU. Each of them evaluates a specific movement in the neighborhood of candidates, and the results are returned back to the master.

At this point, it is important to list some optimizations in the Correlation Clustering local search algorithm that have been applied for the code to run efficiently in the GPU. First of all, the graph had to be stored in Compressed Sparse Row format (Figure 4), in order to save space and avoid unnecessary data transfers between host (CPU) and device (GPU) memory. This representation consists of two arrays: column indices and row offsets. The column indices array is a concatenation of each vertex's adjacency list into an array of m elements. The row offsets array is an n + 1 element array that points at where each vertex's adjacency list begins and ends within the column indices array. For example, the adjacency list of vertex v starts at C[R [v]] and

[R[v]] to E[R[v + 1] -1].
Also, since it is impossible to store the graph in shared memory (graph is big, shared memory is too small), the graph was copied to the (slower) GPU global memory. It was then used to calculate matrices that contain the sum of edge weights between vertex i and every cluster k in the current solution. As we are processing a signed graph, there are 2 sum matrices: one for positive edges and the other for negative edges, following the layout depicted in Figure 5. These matrices, also stored in GPU global memory, contain all the information needed to evaluate the imbalance of a new clustering configuration, without the need to traverse the graph, thus saving GPU memory accesses and execution time.

Our parallel approach, although fast, is limited by the GPU's shared memory size. Access to the shared memory is very fast, therefore data stored in shared memory can be accessed with very low latency. However, due to the limitations of GPU architecture, avilable shared memory is limited to 48kB per MultiProcessor (NVIDIA, 2015)[Appendix G]. Since our local search algorithm stores the current clustering solution array (to which cluster number a vertex belongs) in shared memory, it is unable to solve graph instances larger than 12,888 vertices (48 kB/ 4 Bytes [int type]).

v 1 v 2 v n k 1 0 7 4 k 2 1 0 2 k c 3 1 9 v 1 v 2 v n v 1 v 2 v n 0 7 4 3 1 9 k 1 k c
Figure 5: Layout of the matrices that store the sum of positive and negative edge weights between vertex vi and each cluster kc (positiveSumArray and negativeSumArray, respectively).

CUDA local search kernel implementation

Algorithm 1: 1OptLocalSearchKernel

1 Input: positiveSumArray, negativeSumArray, currentImbalance, clusterArray, number of clusters (c) 2 Output: destImbArray 3 idx = blockIdx.x * blockDim.x + threadIdx.x;

4 i = idx mod n; → Vertex i is in cluster k1 5 k2 = idx div n; → Vertex i is being moved to cluster k2 6 if (i ≤ n and k2 ≤ c + 1) { 7 k1 = clusterArray[ i ];
→ obtains the cluster number of vertex i Algorithm 1 presents the kernel pseudocode for CUDA CC 1 -opt local search kernel and Figure 6 summarizes the work executed. Each thread running in the GPU (uniquely identified by idx) is responsible for calculating the delta of imbalance caused by moving a specific vertex i to a different cluster, for example, in the range k 1 to k c . Afterwards, another kernel performs a reduction of the results, also in parallel, returning the best move for this specific local search.

Finally, whenever a vertex move is applied due to an improvement in imbalance, a third CUDA kernel is invoked to update the clustering configuration and the vertex-cluster edge-weightsum arrays (positiveSumArray and negativeSumArray) after a change in the clustering. This update is a necessary step to allow the execution of the variable neighborhood descent procedure, that is, invoking the 1 -opt local search procedure again (new local search iteration), as long as the obtained clustering solution brings an improvement in imbalance.

Our initial implementation approach consisted of running only the local search algorithm (1OptLocalSearchKernel) inside the GPU, keeping the reduction of best result and update of the auxiliary matrices in the CPU. However, poor performance was obtained due to the overhead of memory transfers between host and device memory: 95% of time spent by local search procedure did not involve computation, only memory copies between host (CPU) and device (GPU) (memcpy operation). In the final version of the algorithm, solution reduction and updates of data structures between local search iterations are also performed in the GPU, which led to the computational results that shall be presented in the next section.

Experimental results

The algorithms described in the previous section were implemented in ANSI C++ and CUDA. All experiments were performed (with exclusive access) on a workstation with an Intel Core i7 QuadCore processor @2.66GHz and 32Gb of RAM under Linux Mint 16 operating system. The workstation is also equipped with NVIDIA Fermi C2050 GPU containing 14 SMs, 32 SPs per SM and 48 KB of shared memory per SM. CUDA code was written in the "C for CUDA V6.5" (NVIDIA, 2015) programming environment.

All heuristic outcomes are average results of 5 independent executions. Speedups are computed by dividing the sequential CPU time with the parallel time, which is obtained with the same CPU and the GPU acting as a co-processor. The following configuration was used to run the local search CUDA kernels: (a) Block size of 256; (b) (c + 1) × n threads in 1 -opt search, where n is the number of vertices of the graph and c is the number of clusters of the current solution.

Computational experiments were carried out on (i) a set of 24 random instances, and (ii) a set of 5 social networks from the literature. Next, we describe briefly these instances 1 . et al., 2010; Facchetti et al., 2011), containing the first n vertices, with n ∈ {1000, 2000, 4000, 8000, 10000}.

Sequential GRASP vs. Sequential GRASP with CUDA local search

In this section, we present the experiments performed with the sequential GRASP algorithm (SeqGRASP) available in Drummond et al. (2013) and the sequential GRASP with CUDA parallel Variable Neighborhood Descent (SeqGRASP/CUDAVND), when solving random instances (Table 2) and Slashdot instances (Table 4). Both experiments used the following set of GRASP parameters: [START_REF] Levorato | Uma metaheurística iterated local search aplicada ao problema de correlação de clusters[END_REF] and the sequential ILS with CUDA parallel Variable Neighborhood Descent (SeqILS/CUDAVND), when solving random instances (Table 3) and Slashdot instances (Table 5). The following configuration was used in the ILS procedure:

Concluding remarks

The aim of this paper was to design an efficient parallelization strategy for the implementation of a parallel local search procedure for the Correlation Clustering problem on GPU. After applying the procedure, known as CUDAVND, in existing GRASP and ILS metaheuristics for the CC problem, our experimental results showed significant speedups, outperforming, in processing time, the local search available in the literature.

The GRASP/CUDAVND algorithm presented an average speedup of x43 (up to x121) on random instances and x2.9 (up to x4.21) on Slashdot instances, while the ILS/CUDAVND showed an average speedup of x14 (up to x33) on random instances and x3.5 (up to x5.6) on Slashdot instances. In both algorithms, the solution quality was equal or close to their sequential counterparts.

The next step of our work will focus on improving the analysis of larger signed social networks. The numerical experience indicates that, in order to handle instances like Epinions (131,828 vertices and 841,372 edges) or Slashdot (82,144 vertices and 549,202 edges) networks, we need to implement better parallelization strategies. One possible approach is implementing a hybrid application, using the parallelism available both in CPU (multicore) and GPU (CUDA).

Figure 1 :

 1 Figure 1: Time spent by GRASP and ILS algorithms on sequential 1-opt local search on Slashdot-based signed graphs.

FigureFigure 4 :

 4 Figure 2: GPU Memory Hierarchy

8/

  * calculates only the difference in positive and negative imbalance */ 9 positiveSum = -positiveSumArray[ i + k2 * n ] + positiveSumArray[ i + k1 * n ]; 10 negativeSum = -negativeSumArray[ i + k1 * n ] + negativeSumArray[ i + k2 * n ]; 11 destImbArray[ idx ] = currentImbalance + positiveSum + negativeSum; 12 }

Figure 6 :

 6 Figure 6: GPU thread work representation for 1-opt local search. Each thread idx is responsible for moving vertex i to a different cluster, from k1 to kc, and to a new cluster (kc + 1).

Table 1 :

 1 Table 1 lists some results available in the literature. Speedups obtained when using GPGPUs to accelerate metaheuristics.

	Author	Title			Speedup
	Fujimoto and Tsutsui (2011)	A highly-parallel TSP solver	Up to x24.2
		for a GPU computing plat-
		form
	Rocki and Suda (2012)	Accelerating 2-opt and 3-opt	From x3 to x26 speedup com-
		local search using GPU in the	pared to parallel CPU w/ 32
		travelling salesman problem	cores in ILS for TSP
	Van Luong et al. (2013)	GPU computing for parallel	From x0.5 up to x73.3 in local
		local search metaheuristic al-	search metaheuristics in GPU
		gorithms
	Krüger et al. (2010)	Generic	local	search	Between x70 and x120
		(memetic) algorithm on a
		single GPGPU chip
	Pena et al.	Local search for the observer	?
		positioning over terrain prob-
		lem
	Santos et al.	Parallel GRASP for the p-	Between x1.14 and x13.89
		median problem

Table 2 :

 2 SeqGRASP and SeqGRASP/CUDAVND results for random instances in (i). Number of vertices: n; Avg I(P): average value of the best solution found within time limit; AvgTime: average time spent (in seconds) on 5 independent executions of each algorithm. Gap %I(P) is the % gap between SeqGRASP and SeqGRASP/CUDAVND solutions. Speedup measures the acceleration of the parallel algorithm over its sequential counterpart. On the Move to Meaningful Internet Systems: OTM 2013 Workshops, volume 8186 of Lecture Notes in Computer Science, pages 674-683. Springer Berlin Heidelberg. Elsner, M. and Schudy, W. (2009). Bounding and comparing methods for correlation clustering beyond ilp. In ILP'09 Proceedings of the Workshop on Integer Linear Programming for Natural Language Processing, pages 19-27. Facchetti, G., Iacono, G., and Altafini, C. (2011). Computing global structural balance in largescale signed social networks. In Proceedings of the National Academy of Sciences of the United States of America, volume 108, pages 20953-20958. Figueiredo, R. and Moura, G. (2013). Mixed integer programming formulations for clustering problems related to structural balance. Social Networks, 35(4):639-651.Fujimoto, N. and Tsutsui, S. (2011). A highly-parallel tsp solver for a gpu computing platform.In Numerical Methods and Applications, pages 264-271. Springer. Gropp, W.,Lusk, E., and Skjellum, A. (1999). Using MPI: Portable Parallel Programming with

	n	e	e+	e-	d	d-	SeqGRASP		SeqGRASP/CUDAVND
							Avg I(P) Avg Time Avg I(P) Gap %I(P) Avg Time Speedup
	400	15960	12768	3192	0.1 0.2	3192	100.67	3192.0	0.00%	2.99	33.70
	400	15960	7980	7980	0.1 0.5	5803.6	565.66	5796.7	-0.12%	21.86	25.88
	400	15960	3192	12768 0.1 0.8	2338	1409.42	2357.0	0.81%	33.69	41.84
	400	31920	25536	6384	0.2 0.2	6384	132.25	6384.0	0.00%	2.81	47.07
	400	31920	15960	15960 0.2 0.5	12840.4	656.99	12833.2	-0.06%	28.46	23.08
	400	31920	6384	25536 0.2 0.8	5324.4	3254.87	5355.6	0.59%	53.40	60.96
	400	79800	63840	15960 0.5 0.2	15960	232.70	15960.0	0.00%	3.64	63.87
	400	79800	39900	39900 0.5 0.5	34862.4	1219.75	34829.6	-0.09%	68.51	17.80
	400	79800	15960	63840 0.5 0.8	14636	3606.43	14667.6	0.22%	100.32	35.95
	400	127680 102144 25536 0.8 0.2	25536	346.12	25536.0	0.00%	4.71	73.49
	400	127680 63840	63840 0.8 0.5	57466.8	2535.17	57437.0	-0.05%	132.01	19.20
	400	127680 25536 102144 0.8 0.8	24086.8	3608.31	24122.0	0.15%	157.46	22.92
	600	35940	28752	7188	0.1 0.2	7188	334.64	7188.0	0.00%	4.65	71.89
	600	35940	17970	17970 0.1 0.5	13915.2	1414.86	13914.8	0.00%	44.62	31.71
	600	35940	7188	28752 0.1 0.8	5730.4	3601.82	5771.6	0.72%	77.31	46.59
	600	71880	57504	14376 0.2 0.2	14376	447.66	14376.0	0.00%	5.07	88.28
	600	71880	35940	35940 0.2 0.5	30149.2	2670.39	30123.3	-0.09%	89.50	29.84
	600	71880	14376	57504 0.2 0.8	12613.6	3605.18	12642.3	0.23%	139.35	25.87
	600	179700 143760 35940 0.5 0.2	35940	905.51	35940.0	0.00%	8.13	111.39
	600	179700 89850	89850 0.5 0.5	80670.8	3602.54	80654.4	-0.02%	198.65	18.13
	600	179700 35940 143760 0.5 0.8	33808.8	3629.47	33854.7	0.14%	293.85	12.35
	600	287520 230016 57504 0.8 0.2	57504	1423.95	57504.0	0.00%	11.68	121.95
	600	287520 143760 143760 0.8 0.5 132176.8	3603.92 132108.4	-0.05%	304.84	11.82
	600	287520 57504 230016 0.8 0.8	55182	3656.96	55203.2	0.04%	427.06	8.56
	Average						-	1940.22	-	0.10%	92.27	43.51

Doreian, P. and Mrvar, A. (2009)

. Partitioning signed social networks. Social Networks, 31:1-11. Drummond, L., Figueiredo, R., Frota, Y., and

Levorato, M. (2013)

. Efficient solution of the correlation clustering problem: An application to structural balance. In Demey, Y. and Panetto, H., editors,

Table 3 :

 3 SeqILS and SeqILS/VND results for random instances in (i).

			Instance			SeqGRASP		SeqGRASP/CUDAVND
	n	|E -|	|E + |	w(E -)	w(E + )	AvgI(P ) AvgT ime AvgI(P ) Gap%I(P ) AvgT ime Speedup
	1000	859	5132	859	5132	600.0	23.69	600.0	0.00%	18.75	1.26
	2000	3217	17598	3217	17598	2186.0	232.48	2187.4	0.06%	73.93	3.14
	4000	8664	40868	8664	40868	6202.6	1415.45	6206.2	0.06%	335.88	4.21
	8000	22789	86916	22789	86916	16082.6	7030.32	16087.2	0.03%	2189.18	3.21
	10000	29805 109266	29805	109266	20594.6	7200.49	20596.6	0.01%	2680.88	2.69
	Average						3180.49		0.03%	1059.72	2.90

Table 4 :

 4 SeqGRASP and SeqGRASP/VND results for Slashdot instances in (ii).

			Instance			SeqILS		SeqILS/CUDAVND
	n	|E -|	|E + |	w(E -)	w(E + )	AvgI(P ) AvgT ime AvgI(P ) Gap%I(P ) AvgT ime Speedup
	1000	859	5132	859	5132	600.2	33.64	600.2	0.00%	15.71	2.14
	2000	3217	17598	3217	17598	2187.5	107.42	2201.6	0.64%	38.15	2.82
	4000	8664	40868	8664	40868	6218.6	591.84	6213.2	-0.09%	105.96	5.59
	8000	22789	86916	22789	86916	16072.1	2229.04	16082.6	0.07%	604.51	3.69
	10000	29805 109266	29805	109266	20595.1	3618.14	20600.6	0.03%	1087.89	3.33
	Average						1316.01		0.13%	370.44	3.51

Table 5 :

 5 SeqILS and SeqILS/VND results for Slashdot instances in (ii).

(i) We generated random social networks with n ∈ {400, 600}, varying network density d = 2 × |E|/(n 2 -n) and negative graph density defined here as d -= |E -|/|E|. For each value of n, we considered a set of 12 random instances having d and d -ranging, respectively, in sets {0.1, 0.2, 0.5, 0.8} and {0.2, 0.5, 0.8}. (ii) This set of instances is composed by 5 signed networks extracted from the large scale social network representing the technology-related news website Slashdot (Leskovec 1 all instances are available in http://www.ic.uff.br/∼ yuri/files/CCinst.zip.