Sovannara Hak

Nicolas Mansard

Oscar Efrain

Ramos Ponce

Layale Saab

Olivier Stasse

Capture, Recognition and Imitation of Anthropomorphic Motion

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Capture, recognition and imitation of anthropomorphic motion

Sovannara Hak, Nicolas Mansard, Oscar Ramos, Layale Saab and Olivier Stasse I. INTRODUCTION We present an overview of our current research works in generation, recognition and editing of anthropomorphic motion using a unified framework: the stack of tasks [START_REF] Mansard | Task sequencing for high level sensorbased control[END_REF]. It is based on the task function formalism classically used for motion generation [START_REF] Samson | Robot Control: the Task Function Approach[END_REF]. A task function maps the joint space of a robot to a dedicated space which is usually linked to the sensors of the robot: the task space. The task spaces are suitable to perform motion analysis and task recognition because the tasks are described in those spaces [START_REF] Hak | Humanoid robot task recognition from movement analysis[END_REF]. The generation is originally based on inverse kinematics but can be generalized to produce full-dynamic motions [START_REF] Saab | Generation of dynamic motion for anthropomorphic systems under prioritized equality and inequality constraints[END_REF]. The tasks are defined by a tasks space, a reference behavior and a task Jacobian. The reference behaviors are originated from human trajectories. Specific tasks are then integrated to retarget and to edit the reference motion in order to respect the dynamic constraints, the limits of the robot and the general aspect [START_REF] Ramos | Dynamic motion capture and edition using a stack of tasks[END_REF]. In the next section, we quickly introduce the stack of tasks framework. Then we present our methods to perform task recognition, dynamic retargeting and editing based on that framework.

II. STACK OF TASKS

The task-function approach [START_REF] Samson | Robot Control: the Task Function Approach[END_REF] consists in designing the motion to be performed as a control law in a subspace of small dimension, and then back-projecting this control law to the state space of the robot. A task is defined by the triple (e, ė * , G), where e belongs to the task space, ė * is the reference behavior in the tangent space to the task space at e, and G is the differential mapping between the task space and the control space of the robot. The interest of defining the robot motion inside a task space rather than directly at the joint level is double: first, the task space is chosen such that the control law can be easily designed (typically, in visual servoing the task space is the space of measurable visual features), making the link between sensor feedback and control direct [START_REF] Espiau | A new approach to visual servoing in robotics[END_REF]; second, the interference between two task spaces can be easily prevented and then concurrent simultaneous objectives can be decoupled, using a projection operator. Based on the redundancy of the system, this approach can be extended to consider a hierarchical set of tasks [START_REF] Siciliano | A general framework for managing multiple tasks in highly redundant robotic systems[END_REF]. Complex motion can then be constructed from simple tasks seen as atomic bricks of motion. We define a LAAS-CNRS (Laboratoire d'Analyse et d'Architecture des Systèmes), 7 av col Roche, F-31077 Toulouse, France, Université de Toulouse; UPS, INSA, INP, ISAE: sovannara.hak@laas.fr, nicolas.mansard@laas.fr, oscar.ramos@laas.fr, layale.saab@laas.fr, olivier.stasse@laas.fr. The final positions of two similar looking movements. Their purposes are different: in the left picture, the robot has to grab one ball, whereas in the right picture, the robot has to grab two balls. generic task function formulation [START_REF] Saab | Generation of dynamic motion for anthropomorphic systems under prioritized equality and inequality constraints[END_REF] that can be applied in both inverse kinematics and inverse dynamics. A complete implementation of this approach is developed in [START_REF] Mansard | Task sequencing for high level sensorbased control[END_REF] under the name Stack of Tasks. The structure enables to easily add or remove a task. The stack of tasks can be generalized to generate dynamic motions.

III. TASK RECOGNITION

Several approaches for the representation of an action and its recognition are studied in computer vision, robotics and artificial intelligence [START_REF] Krüger | The meaning of action: A review on action recognition and mapping[END_REF]. The action recognition and motion analysis is widely handled using statistic tools [START_REF] Schaal | Computational approaches to motor learning by imitation[END_REF]. The recognition problem is formulated as a classification problem using a Bayesian classifier [START_REF] Drumwright | Generating and recognizing free-space movements in humanoid robots[END_REF], [START_REF] Jenkins | Performance-derived behavior vocabularies: Data-driven acquisition of skills from motion[END_REF]. Generally, for those statistic based method, the main assumption is that the recognition is performed on a temporal sequence of action. The motion recognition is then divided in two steps, motion segmentation and motion classification [START_REF] Nakaoka | Learning from observation paradigm: Leg task models for enabling a biped humanoid robot to imitate human dances[END_REF], [START_REF] Chalodhorn | Humanoid robot motion recognition and reproduction[END_REF]. The analysis of the motion has to be performed in a suitable space to be efficient. These spaces can be chosen arbitrary [START_REF] Nakaoka | Learning from observation paradigm: Leg task models for enabling a biped humanoid robot to imitate human dances[END_REF], automatically selected [START_REF] Mühlig | Automatic selection of task spaces for imitation learning[END_REF] or learned [START_REF] Schaal | Reinforcement learning of motor skills with policy gradients[END_REF].

We rely on the task spaces defined using the task function formalism to perform the motion analysis. Assuming that the analyzed motion has been generated by a stack of tasks involving tasks belonging to a known tasks pool, the recognition problem is handled by applying a reverse engineering of the motion. in order to reconstruct the original stack of tasks. The joint trajectory to analyze is projected in a given set of known task spaces. The projected trajectories are compared with theoretical behaviors to decide which tasks are active. Our method is able to recognize tasks executed in parallel and can handle tasks coupling using task spaces and nullspace projectors. Similar looking motion can then be disambiguated. For example, Fig. 1 illustrates the final positions of two different movements played by the HRP-2 robot. Although they look similar, the purpose of the movements are different. In the first movement, the robot has to grab one ball with its right hand. This task modifies the balance of the robot which consequently moves its left Fig. 2. Inverse Dynamics Cascade Scheme hand to compensate the balance. In the second movement, the robot has to grab two balls. The second ball is placed at the final position of the left hand in the previous movement. This artificially introduces a visual ambiguity between the two movements. This ambiguity can be solved using our method [START_REF] Hak | Humanoid robot task recognition from movement analysis[END_REF].

IV. DYNAMIC RETARGETING AND EDITING

Generating motion from imitation has been adopted widely by researchers in both fields of computer animation and robotics. The starting point is usually the motion acquired from a human expert using a motion capture system [START_REF] Miura | Robot motion remix based on motion capture data towards human-like locomotion of humanoid robots[END_REF].

The easiest way to make a humanoid robot behave like a human, is to simply copy human movements. However, the challenges arise due to the kinematic and dynamic disparity between the human and the humanoid. The original movement has to be modified to enforce the kinematic and dynamic constraints of the robot. This operation is called motion retargeting [START_REF] Gleicher | Retargeting motion to new characters[END_REF], [START_REF] Pollard | Adapting human motion for the control of a humanoid robot[END_REF]. For example, the retargeting can be done by optimization [START_REF] Safonova | Optimizing human motion for the control of a humanoid robot[END_REF]. Typically, previous attempts on dance motion imitation have been realized [START_REF] Riley | Methods for motion generation and interaction with a humanoid robot: Case studies of dancing and catching[END_REF], [START_REF] Nakaoka | Learning from observation paradigm: Leg task models for enabling a biped humanoid robot to imitate human dances[END_REF]. However, the robot dynamics have not been considered.

We propose a method for the imitation of whole-body motion for humanoid robots based on the stack of tasks framework. This method allows to quickly retarget a dynamic motion demonstrated by a human expert and to adapt the dynamics of the human body to the own dynamics of the robot. Then the output motion is modified or edited to rectify the differences with the original motion that were introduced by the previous retargeting. The obtained motion is dynamically consistent, and could be directly applied on the real humanoid robot. The motion generation method relies on an inverse-dynamics solver based on a cascade of quadratic programs [START_REF] Saab | Generation of dynamic motion for anthropomorphic systems under prioritized equality and inequality constraints[END_REF]. Each quadratic program is associated to a desired task. The flexibility of the scheme allows the addition of arbitrary tasks on the joint space and operational space levels to rectify the movements. Fig. 2 illustrates the adopted method that we applied on a dancing motion. This dance motion is performed by a human and recorded with an optical motion capture system. This motion is then retargeted, edited and finally executed on the HRP-2 robot in simulation [START_REF] Ramos | Dynamic motion capture and edition using a stack of tasks[END_REF].

V. CONCLUSION

We presented our works relative to anthropomorphic motions. We performed task recognition, full-dynamic motion generation, motion retargeting and editing in a unified framework: the stack of tasks. Thanks to the genericity of the task function formalism, our works can be further extended. For example, for the recognition, the use of the task function formalism applied to human motion is currently investigated. Also, preliminary results on the real robot for the retargeting and editing method have been obtained.

  This work was supported by the R-Blink Project, Contract ANR-08JCJC-0075-01.

Fig. 1 .

 1 Fig. 1.The final positions of two similar looking movements. Their purposes are different: in the left picture, the robot has to grab one ball, whereas in the right picture, the robot has to grab two balls.


Benjamin Lévy
email: benjamin.levy@ircam.fr

Georges Bloch
email: gbloch@cnsmdp.fr

Gérard Assayag
email: gerard.assayag@ircam.fr

OMaxist Dialectics: Capturing, Visualizing and Expanding Improvisations

Keywords: OMax, Improvisation, Machine Learning, Machine Listening, Visualization, Sequence Model, Software Architecture

OMax is an improvisation software based on a graph representation encoding the pattern repetitions and structures of a sequence, built incrementally and in real-time from a live Midi or Audio source. We present in this paper a totally rewritten version of the software. The new design leads to refine the spectral listening of OMax and to consider different methods to build the symbolic alphabet labeling our symbolic units. The very modular and versatile architecture makes possible new musical configurations and we tried the software with different styles and musical situations. A novel visualization is proposed, which displays the current state of the learnt knowledge and allows to notice, both on the fly and a posteriori, points of musical interest and higher level structures.

PRINCIPLES

OMax [START_REF] Assayag | Navigating the oracle: a heuristic approach[END_REF][4] [START_REF] Bloch | Introducing video features and spectral descriptors in the omax improvisation system[END_REF] is a software environment oriented towards human-machine interaction for musical improvisation. It learns in real-time by listening to an acoustic musician and extracting symbolic units from this stream. It then builds a sequence model on these units constituting an internal knowledge. The internal model of OMax (named Factor Oracle [START_REF] Allauzen | Factor oracle: a new structure for pattern matching[END_REF] [START_REF] Assayag | Using factor oracles for machine improvisation[END_REF]) is a graph which incrementally recognizes the repeated factors (patterns and subpatterns) of any symbolic string. Factor Oracle only needs strict on the symbolic units to be built. They can be called letters over a formal alphabet.

OMax is able to navigate through this model to create one or several "clones" of the musician feeding the system [START_REF] Assayag | Navigating the oracle: a heuristic approach[END_REF]. These "clones" are recombinations of the original discourse justified by the model and realized by cutting and pasting the original material in real-time (audio editing or MIDI deslicing, see 2.1 and [START_REF] Assayag | Omax brothers : a dynamic topology of agents for improvization learning[END_REF]).This stylistic reinjection [START_REF] Assayag | Omax brothers : a dynamic topology of agents for improvization learning[END_REF] creates a specific musical interaction in which the musician is constantly confronted to a reinterpreted version of his own playing. It emphasize the memory effects and usage of (self-)reference found in improvisation contexts such as collective free improvisation or jazz. This technique, close to concatenative synthesis, has been extended in a video version of OMax [START_REF] Bloch | Introducing video features and spectral descriptors in the omax improvisation system[END_REF]. The video of the musician (or any other visual material) is aligned and recombined as a slave synchronization with audio.

Previous versions of OMax made use of two very different software environment, Max/MSP and OpenMusic (hence its name "OMax") respectively for real-time signal processing and abstract model construction and navigation processes. In this paper we will present a new version of OMax we developed solely based on Max5. We will describe the material it is now able to "understand" and how it achieves this. Then we will explain the architecture of this new version and its novel visualization and interactions possibilities. Finally we will discuss a few situations we encountered testing with musicians.

MATERIAL

Historically, OMax emerged from studies on stylistic simulation by Shlomo Dubnov and Gérard Assayag and Marc Chemillier's research on improvisation modeling. It has since gained considerable attention from improvising musicians worldwide through dozen of concerts, workshops and master-classes.

Audio vs. MIDI

Both audio and MIDI streams can constitute a source for OMax learning. Though MIDI is already a flow of abstract data, it still needs to be segmented into consistent units to be learnt. In the case of a monophonic MIDI input , segmentation is trivial: a unit for a note. However a polyphonic MIDI input feeds a continuous and overlapping flow of notes to be separated into polyphonic chord-like slices (Figure 1). This slicing happens with the birth and death of significant events and has been described in [START_REF] Assayag | Omax brothers : a dynamic topology of agents for improvization learning[END_REF]. It does not imply any specific labeling (or lettering) to tag the symbolic units to be compared and learnt.

In the case of an audio input, prior to any kind of grouping, information needs to be extracted from samples. We have in OMax two very different types of audio analysis which infer two different kind of listening. The first type of analysis is pitch extraction. For now, we are able to deal only with monophonic pitch extraction and use the YIN algorithm [START_REF] De Cheveigné | a fundamental frequency estimator for speech and music[END_REF]. To make the output of yin more consistent and stable, we use a statistical analysis with concurrent voting agents gathering pitches over fixed windows [START_REF] Assayag | Sound and Music Computing (SMC) 2006[END_REF]. Stable pitches are gathered and grouped into units when equal and consecutive to form notes. At this point, we are brought back to the simpler case of monophonic MIDI-like data.

We summarize the different steps to form consistent units for the different type of analysis in Figure 1. From an audio stream, micro-units are constituted with an initial framing and the extraction of a descriptor of the signal. Depending The boundaries are defined by different criteria depending on the type of units. Then, to achieve the segmentation, we time-stamp these units linking them with the chunk of signal they encode -and we take into account the latency and time specific parameters of each methods.

Spectral Segmentation

The second type of audio analysis in OMax uses spectral descriptors. They allow the system to listen and play with wider types of sound including noises, percussions or different instrumental playing modes. Mel Frequency Cepstral Coefficients has been proven (for example in [START_REF] Brown | Feature dependence in the automatic identification of musical woodwind instruments[END_REF]) to be easily computable, very compact and reliable for recognition tasks. It is suitable to constitute our micro-units. However, MFCCs are vectors of floating-point multi-scale coefficients. It is thus necessary to have a clustering algorithm to put together consistent and meaningful macro-units.

Rather than using a rough quantization as in [START_REF] Bloch | Introducing video features and spectral descriptors in the omax improvisation system[END_REF], we designed a weighted Euclidean clustering algorithm. This algorithm achieves both the macro-grouping and the symbolic labeling at once. For every incoming MFCC vector, dropping the first coefficient (which represent the overall energy of the slice), we weight the remaining coefficients according to profiles to help enhancing the differences we want to discriminate. These profiles have been adjusted empirically along experiments with several instruments and playing styles. Then we compare the vector to the clusters already encountered by computing the Euclidean distance with their centroids and we determine (with an adjustable threshold) if it can be identified or if it constitute a new letter in our spectral alphabet.

Alphabets

This incremental clustering mechanism creates a growing alphabet of spectral letters in a multidimensional Euclidean space, meaning that the system is able to discover the symbolic units along the musicians playing. It allows us to have an ad-hoc definition of the clusters depending on the input material. Regions of the timbre space thoroughly explored by the musician will have therefore more clusters than other regions, less brought into play. On the other hand, pitch classes and quantized spectral vectors constitute a fixed and predetermined alphabet. Another effect of this classification is the possibility of mutations according to the past of the learning. Depending on the material already encountered and known in the system -which means in our MFCC space, depending on the clusters already defined -, the same (or close) spectral vectors can be identified differently. An example of such a mutation is given in 2D Figure 2: vectors framed in red, although very close, are recognize differently depending on the moment they appear. The first vector (Figure 2a) is considered in the "blue" class while the second occurrence is closer to a more recently defined "yellow" cluster (Figure 2b). The appearance of the "yellow" cluster in between did not change the class of the previously encountered vector but it modifies the classification of forthcoming material. This also has a musical meaning: a specific playing mode can be considered as an accident and identified as close to an already heard mode if encountered only once. But the same playing mode, if developed by the musician may be rightfully creating one or more new cluster(s) -letter(s) in our spectral alphabet -to describe its slighter differences. Thus the mapping between signal units and symbols has become adaptive instead of being rigid, which reflects an important aspect of implicit learning in human interaction.

ARCHITECTURE

Further than being able to use different segmentations and alphabets, the whole software has been reprogrammed to adopt a very flexible and versatile architecture presented Figure 3.

Modularity

First of all, a modular approach has been taken to develop the different functions needed (Figure 3). The audio input is split in two streams. One is directly recorded into a buffer while the other enters a two stage process to constitute macro-units. The detection stage regroups both the framing of the signal and the extraction of a descriptor to get micro-units. Then the segmentation stage is in charge of the grouping and the time-stamping to define macro-units and date them (see 2.1 and Figure 1). Thanks to a fixed delay, the analysis chain described in the previous paragraph has a retro-action on the recording to start and stop it consistently (mainly avoiding to record long silences).

Once labelled (see 2.3), the symbolic units are fed incrementally to the model which will be read and navigated by improvising agents. To create a new "clone", the improviser is in charge of reading and jumping in the graph to create a new coherent path -a musical variation on what the acoustic musician played until now. The scheduler reading this path puts it back "in time" with the possibility of time-stretching or backward reading. Finally, the renderer effectively reads and crossfades the different buffer chunks corresponding to this new musical discourse.

Parallelism

The modularity of the new design allows now OMax to run in parallel different analysis and labeling and to acquire this way a multi-description model on a single input. The most typical setup making use of this is to run both the pitch and spectral analysis on a single audio input, building thus two Factor Oracles which refer to the same buffer and timestamping. Another very common option the new architecture allows, is to have several independent "clones" improvising on the same model. For that, we duplicate the whole generation chain, improviser -scheduler -renderer. Each improviser is able to have its own path on the common model of the input.

Besides these simple configurations, more sophisticated schemes are possible to create different musical linkage inside OMax. An example of these configurations is to have two "clones" playing the same computer-based improvisation -possibly at different speed or with transpositionie. the same path in the model.

Versatility

and combining at will the modules -the only limit being the power of the computer -we can shape and adapt our OMax setup to very diversified musical situations. From one to several inputs in parallels with one or more descriptions and models built on each of them and one to several "clones" improvising together or independently, the variety of arrangement allows us to start playing OMax almost as an instrument. We will see in 5 how OMax can now take its own musical in different musical ensemble.

VISUALIZATION

On top of the redesign of the architecture, OMax 4.x adds to the software a whole new interface (thanks to Jitter, the graphical part of Max5). This interface is based on a visualization of the current state of one or two models being built. It takes the simple form of a growing horizontal and linear timeline representing what has already been learnt -time "flows" from left to right: left is farther in the past, right is the most recent element. Above and below this timeline can be shown some links of the Factor Oracle graph indicating the occurrences of repeated patterns. An example is presented Figure 4.

Live

Although unadorned, this feedback constantly given on the current state of the model revealed itself to be very efficient to locate and memorize on the fly musically interesting points. Seeing patterns of links appearing on the screen related to what the musician is currently playing allows to associate musical passages with particular sections of the graph. And retrieve them easily later on. Figure 4: "Clones" and regions on the sequence visualization While playing with OMax, the visualization is also a new interface to interact with the software. Indeed, as introduced Figure 4, the different "clones" OMax is able to play are also pictured on the display with moving arrows above and below the timeline. These arrows reflect the current position of each "clone" in the model and jump along the links when improvising new paths (see [START_REF] Assayag | Navigating the oracle: a heuristic approach[END_REF]). With the mouse, regions of the graph can be selected (green and blue sections on Figure 4) to constrain "clones" to specific sections of what has been learnt.

Many other features and functions that can not be detailed here have also been implemented to make the visualization as intuitive, interactive and useful as possible.

A Posteriori

Following the same visualization principles with different musical materials and visuals, we noticed that examining our model, a posteriori, could reveal important higher level structures. Moreover, this analysis may show, in real-time, these higher level formal structures with little graphical processing. For example, with colors to identify patterns and thickness to stress the durations, we can enhance certain aspects of the analysis and help discover interrelations of parts. Figure 5 shows the analysis of a saxophone improvisation. On the bottom half (below the horizontal timeline, which correspond to the model built on pitch), we can see with the important number of arches, that the material introduced at the beginning of the session is developed for about a third of the total duration then the rest of the improvisation is very different (few links/arches connecting it with the beginning). Finally a short but strong recapitulation of the first material is played: many arches connecting the last moments of the improvisation with the beginning.

This way, the new interface of OMax may open possibilities for a simple yet efficient musicology tool to study pieces or improvisations and compare them.Automatic segmentation of formal high level structures in musical sequences has been experimented as a derivation from this visualization but is not presented in this paper.

OMAX IN ACTION

In the last two years, we had the opportunity to play with OMax in numerous and various situation. Here are some of the rough observations we could empirically make. We encountered mainly two kinds of musical ensembles. The first is a duet between an acoustic musician improvising and feeding the system and an electronic musician controlling the software. The second common situation is to include OMax (and the person controlling it) into a small musical group (usually up to ten musicians).

Duets

Naturally, the first idea to try out a software like OMax is to ask a musician to feed the system with an improvisation and play along with the computer based "clones". This allows us to test at the same time how the system understands the musicians playing and how they musically interact. Multiplying this kind of experiments with very different instruments helped us refine the different analysis stages of the software. While multiplying the different styles showed us the musical possibilities and limits of such a dialog.

It soon appeared in this situation that the choices made by the person controlling OMax strongly influence the course of the session. Thus, the acoustic musician could notice very fast the interventions and the character of the electronic musician, and often referred to this partner as a mixed entity constituted of OMax and the person controlling it, rather than as the software by itself. Duets of short duration work very well most of the time and some characteristics of purely acoustic improvised duets can be found. However, when musicians want to make it longer (and confront it with a public), they usually feel more confident (pre)setting narrative elements. They frequently start to predefine the type of interaction with the system, mostly in terms of when to play and what part of the learning to use (which could be identified to a music score for OMax player). Or they feed OMax with some prepared material (pre-composed and/or pre-recorded) and improvise with these. Some previous experiments have been done in this last direction such as in Peking Duck Soup (Bloch 2008 [6]).

Groups

The other kind of musical situation OMax has regularly been involved in could be qualified as "collective free improvisation" or "band", that is a small group of musicians playing together, either improvising freely or with strong predetermined structuresIn this cases, one or two instances of OMax were used and each of them could listen and learn from one or two of the acoustic musicians. Technically, the question of feedback of other musicians and OMax into the microphones gets really serious in these situations.

Despite the difference of nature between the acoustic instruments and OMax -which usually does not have its own sound source -the computer and its player could really find a place comparable to the other musicians in the group. And the work to build a whole concert program was in almost every aspects similar to the work with an ensemble of only acoustic instruments.

FURTHER DIRECTIONS

Both the entire renovation and the musical testing feed the research around the musical aptness of OMax.

The explorations already started around the notion of alphabet in OMax constitute a strong direction of our future work. It puts up questions about the consistency of these alphabets and ways to build finer and even more meaningful alphabets. On-going research about information geometry or other content-oriented machine learning techniques may nourish our reflexion. Multiplying the alphabets and models built in parallel gives opportunities to exploit more or differently the knowledge of the system. The various descriptions of an input sequence may be queried concurrently or jointly to help drive the system towards more expressive and speaking musical paths. This database oriented approach could use some reinforcement learning technique in order to make interesting solutions emerge.

Finally, numerous musical situation suggested we should investigate the relation of OMax with the rhythm both in a broad (phrase leading, endings. . . ) and in a strict (pulse, time signature. . . ) sense. A strong anticipation mechanism may be a relevant approach to these problems.

Figure 1 :

 1 Figure 1: Analysis chain of the input

Figure 2 :

 2 Figure 2: Example of mutation in spectral clustering

Figure 3 :

 3 Figure 3: Functional diagram of OMax 4.x

Figure 5 :

 5 Figure 5: Visualization with colors and thickness


B Robl Ès

M Avila

F Duculty

P Vrignat
email: pascal.vrignat@univ-orleans.fr

F Kratz

S B Égot

"Performance, interoperability and safety for sustainable development" Methods to choose the best Hidden Markov Model topology for improving maintenance policy

Keywords: Hidden Markov Models, model selection, learning algorithms, statistical test, uncertainties, predictive maintenance. * Computerized Maintenance Management System

Prediction of physical particular phenomenon is based on partial knowledge of this phenomenon. Theses knowledges help us to conceptualize this phenomenon according to different models. Hidden Markov Models (HMM) can be used for modeling complex processes. We use this kind of models as tool for fault diagnosis systems. Nowadays, industrial robots living in stochastic environment need faults detection to prevent any breakdown. In this paper, we wish to find the best Hidden Markov Model topologies to be used in predictive maintenance system. To this end, we use a synthetic Hidden Markov Model in order to simulate a real industrial CMMS * . In a stochastic way, we evaluate relevance of Hidden Markov Models parameters, without a priori knowledges. After a brief presentation of a Hidden Markov Model, we present the most used selection criteria of models in current literature. We support our study by an example of simulated industrial process by using our synthetic model. Therefore, we evaluate output parameters of the various tested models on this process: topologies, learning algorithms, observations distributions, epistemic uncertainties. Finally, we come up with the best model which will be used to improve maintenance policy and worker safety.

INTRODUCTION

According to the Global Energy Statistical Yearbook 2011, Enerdata 1 gives alarming conclusions: after the 1% decrease observed in 2009, energy consumption soared by 5.5% in 2010, and results in a growth in CO 2 energy emissions close to 6%, to their highest level ever. Despite heavy investment to remain competitive, most industry are not concerned with the green thinking, whereas implementing energy reducing measures such as having an efficient maintenance policy, is not so expensive and can save in energy costs. Obviously, fault diagnostics techniques can reduce maintenance downtime and thus reduce consumption of energy. According to (Vrignat, Avila, Duculty & Kratz 2010), we find two keywords in maintenance definition: maintain and restore. The first one refers to preventive action. The second refers to corrective action. Thus, maintenance optimization for reliability determines "optimal" preventive maintenance. Events preceding a problem in maintenance activities are often recurrent. Special events series should inform us on next failure. For example, in mechanical systems, noises, vibrations precede a failure. The loss of performances reflects failure or technical faults. We also show in [START_REF] Vrignat | Use of HMM for evaluation of maintenance activities[END_REF]) that our model provides a good failure prediction. We make a reference model, named synthetic model, which fits to real industrial processes. Our research consists in evaluating different Hidden Markov Models topologies, with parameters outcoming from this industrial synthetic model. In this work, the emphasis is on measuring relevance of Hidden Markov Models parameters, based on several criteria used in current literature. Then, we try to give the best HMM topology. The structure of this paper is as follows: in section 2, we outline MOSIM'12 -June 06-08, 2012 -Bordeaux -France hidden Markov model and define its parameters. After determining the stochastic nature of our synthetic model, we present criteria used to evaluate relevance and uncertainties of HMM, in section 3. We show the evaluation process in section 4. Finally, we use our synthetic model to compare several HMM topologies, from among a candidate set with previous criterion and try to give the best one, in section 5.

HIDDEN MARKOV MODEL

Hidden Markov Model ( [START_REF] Rabiner | A tutorial on hidden markov models and selected applications in speech recognition[END_REF], [START_REF] Fox | Robot introspection through learned hidden markov models[END_REF]) is an automaton with hidden states which consists of unobservable variable. This one represents the system status to be modeled. Only output variable is observable. Moreover, we get observations sequence from output of the automaton. From now, we rename observations sequence as symbols, representing these observations (see an example of model topology in figure 1). This is precisely relevance of these symbols that we attempt to evaluate. Hidden Markov Model is characterized by:

• State number;

• Number of distinct observation symbols per state, observation symbols corresponding to the physical output of the system being modeled;

• Distribution probability of state transitions;

• Distribution probability of observation symbols;

• Initial states distribution.

S1 S2 S3 S4

Symbols production 1: SEC 2: OT 3: NTR 4: OBS 5: . . .

Symbols production HMM π

Figure 1: Four states Hidden Markov Model.

Markov Assumption

States prediction is not made more accurate by additional a priori knowledge information, i.e. all useful information for future prediction is contained in present state of the process.

P (X n+1 = j|X 0 , X 1 , . . . , X n = i) = P (X n+1 = j|X n = i).
(1)

Definitions for discrete Hidden Markov Model

Let us describe variables for HMM:

• Let N , the number of workable hidden states and S = {s 1 , s 2 , . . . , s N }, the set of this variable. Let q t , the value of this variable at time t;

• Modeled process, must match to first-order Markov assumption (see §2.1);

• Let T , the full number of observation symbols and let X = {x 1 , x 2 , . . . , x T }, observations sequence of the modeled process;

• Let A = {a ij }, distribution probability of state transitions with:

a ij = P (q t+1 = s j |q t = s i ) 1 ≤ i, j ≤ N, (2)
• Let B = {b j (m)}, distribution probability of observation symbols in j state, with:

b j (m) = P (X t = x m |q t = s j ) 1 ≤ j ≤ N 1 ≤ m ≤ T, (3)
with X t , value of observation variable at time t.

• Let π = {π i }, initial states distribution with:

π = P (q 1 = s i ) 1 ≤ i ≤ N, (4)
• Hidden Markov Model will be set as: (A, B, π).

Learning algorithms and decoding algorithms

To achieve learning models, we use two different algorithms:

• Baum-Welch learning [START_REF] Baum | A maximization technique occurring in the statistical analysis of probabilistic functions of markov chains[END_REF], decoding by Forward Variable [START_REF] Rabiner | A tutorial on hidden markov models and selected applications in speech recognition[END_REF].

Estimate iteratively η = (A, B, π), with an observation sequence of X = {x 1 , x 2 , . . . , x T },

Maximize → P (U = X|η), (5)
• Segmental K-means learning [START_REF] Juang | The segmental k-means algorithm for estimating parameters of hidden markov models, Acoustics, Speech and Signal Processing[END_REF], decoding by Viterbi [START_REF] Vrignat | Maintenance policy: degradation laws versus hidden markov model availability indicator[END_REF].

Optimizing probability → P (X, S = Q * |η). (6)

Q * : Sequence of hidden states that most likely generated the sequence as calculated by the Viterbi algorithm. S = (S 1 , . . . , S T ) is a T tuple of random values defined on S MOSIM'12 -June 06-08, 2012 -Bordeaux -France

• Decoding algorithm by Forward Variable:

α t (j) = P (x 1 , x 2 , . . . , x t , Q t = s j |η). (7)
• Viterbi decoding algorithm:

δ t (j) = max (q1,...,qt-1∈S t-1 ) {P (S 1 = q 1 , . . . , S t-1 = q t-1 , S t = s j ), U 1 = x 1 , . . . , U t = x t |η}.

(8)

EVALUATION METHODS

A lot of criteria in model selection are proposed in literature. We try to evaluate the best Hidden Markov Model topology proposed in [START_REF] Vrignat | Use of HMM for evaluation of maintenance activities[END_REF], by using Shannon's entropy [START_REF] Hocker | Shannon entropy based time-dependent deterministic sampling for efficient on-the-fly quantum dynamics and electronic structure[END_REF], especially maximum entropy principle used in [START_REF] Chandrasekaran | Maximum entropy relaxation for graphical model selection given inconsistent statistics, Laboratory for Information and Decision Systems[END_REF]. Calculation is made with states and observations: symbols productions of synthetic HMM. To emphasize our analysis, we also use some criteria which penalize likelihood value, in order to overcome over-parameterization models, like Akaike (AIC) [START_REF] Shang | Bootstrap variants of the akaike information criterion for mixed model selection[END_REF] and Bayes (BIC) [START_REF] Chen | Speaker, environment and channel change detection and clustering via the bayesian information criterion[END_REF] criteria. We begin to determine the stochastic nature of our given symbols.

NIST 2 Tests

First of all, we have to establish that we use stochastic density of probability

Shannon's entropy

We now study notions of Shannon's entropy. It is a function which calculate the information rate con-tained in an information source. This source can be a text written in any language, an electrical signal or an unspecified electronic file. . .

Entropy Definition

Shannon's entropy is defined in [START_REF] Cover | Elements of information theory[END_REF] as follows:

H(S) = - n i=1 P i log b P i , (9)
P i is the average probability to find the i symbol in S.

Maximum entropy principles

The two principles of entropy's maximization in [START_REF] Agouzal | On the relation between the maximum entropy principle and the principle of least effort: The continuous case[END_REF] are the following:

• Principle of probabilities assignment to a distribution when we haven't enough informations on it;

• For all probability distributions that satisfy the constraints, we choose the one which has the maximum entropy according to Shannon. [START_REF] Chandrasekaran | Maximum entropy relaxation for graphical model selection given inconsistent statistics, Laboratory for Information and Decision Systems[END_REF]) use this 2 nd principle for models selection, and [START_REF] Arminjon | Maximum entropy principle and texture formation[END_REF] for building even more accurate models, by adding information. Our step consists in comparing the average entropies for various models. Value of average entropy would be then maximum for the most relevant model.

Entropic Filter

We now introduce "Entropic Filter" concept. According to the 2 nd principle of entropy stated in §3.2.2, we choose the model whose average entropy is maximum.

On the other side, outliers values can generate miscalculation in real entropy value of the model. Especially N T R symbols (Nothing To Report) which are not useful for evaluation (entropy is maximum). SP (Stop Production) symbols have likewise been eliminated (entropy is null). Indeed, they are totally discriminated for S1 state of HMM. To improve calculation of entropy, it is therefore better to eliminate these values. This approach is used through ID3 and C4.5 [START_REF] Quinlan | C4.5: Programs for Machine Learning[END_REF]) algorithm when creating decision tree, removing recursively attribute with zero entropy. In order to improve the calculation of entropy, we propose to eliminate discriminated symbols of zero entropy and the most representative symbols, where entropy is maximum. This operation will be MOSIM'12 -June 06-08, 2012 -Bordeaux -France named "Entropic Filter". We then calculate the average entropy of models to assess relevance of observation sequences. The best model is the one which has the best average entropy, after entropic filtering.

Maximum likelihood

Let us now turn to studying maximum likelihood principle. Let P α , a statistical model, and X, an observation sequence, the probability to see X according to P can be measured by f (X, α) function which represents the density of X when α appears. Since α is unknown, it seems natural to promote values of α where f (X, α) is maximum: it is the notion of likelihood of α for observation X.

-Expression of likelihood V :

V (x 1 , . . . , x n ; α) = n i=1 f (x i ; α), (10)
α is mathematical expectation.

A strictly increasing transformation does not change a maximum. Maximum likelihood can also be written as:

log(V (x 1 , . . . , x n ; α)), (11)
Then

log(V (x 1 , . . . , x n ; α)) = n i=1 log(f (x i ; α)). (12)
-For a discrete sample:

f (X; α) = P α (X = x i ), (13)
P α (X = x i ) represents discrete probability where α appears.

-Maximum likelihood for a discrete sample P α (x i ) representing the discrete probability where α appears:

log(V (x 1 , . . . , x n ; α)) = n i=1 log(P α (x i )). ( 14
)
Actually, we maximize the logarithm of likelihood function to compare several models. According to [START_REF] Olivier | Prediction with vague prior knowledge[END_REF], principle of maximum likelihood results in overparameterization of the model to have good performances. Penalization of likelihood value can overcome this disadvantage. Most famous penalized loglikelihood criterion is the AIC [START_REF] Shang | Bootstrap variants of the akaike information criterion for mixed model selection[END_REF], even if it is not completely satisfactory: it improves maximum likelihood principle but also led to an over-parameterization. Other traditional criteria, BIC and HQC, ensure a better estimation by penalizing oversizing models.

Akaike Information Criterion

According to [START_REF] Ash | Information theory[END_REF]), entropy of a random variable is a regularity measurement. We can easily extend this concept to a model having several random variables. In their report, [START_REF] Lebarbier | Le critère bic : fondements théoriques et interprétation[END_REF]) describe all assumptions necessary to its implementation.

AIC = -2 ln V + 2k, (15)
k is the number of free parameters, 2k is the penalty, V is the likelihood.

The best model is the one which has the weakest AIC. This criterion uses maximum likelihood principle seen in ( 14). It penalizes models with too many variables, and avoids over-learning models. In the literature, Akaike Information Criterion (AIC) is often associated with another known criterion, called Bayes Information Criterion (BIC).

Bayesian Information Criterion

BIC penalizes more over-parameterized models. It was introduced in [START_REF] Schwarz | Estimating the dimension of a model[END_REF] and is different for the correction term:

BIC = -2 ln V + k ln(n), (16)
k is the number of free parameters of Markov Model [START_REF] Avila | Optimisation de modèles Markoviens pour la reconnaissance de l'écrit[END_REF], n is the number of data, k ln(n) is the penalty term.

Like AIC, the best model is the one which gets the minimum value of BIC. Choosing between these two criteria is to choose between a predictive model and an explanatory model [START_REF] Lebarbier | Le critère bic : fondements théoriques et interprétation[END_REF]. It checks the validity of a particular model but it is mainly used to compare several models together. AIC criterion is less relevant than BIC for over-learning models.

Statical tests

Most statistical tests assume that samples are taken at random to achieve [START_REF] Steinebach | romano: Testing statistical hypotheses[END_REF]). This sounds easy but is actually quite difficult to achieve.

Kolmogorov-Smirnov test

Kolmogorov-Smirnov test is a statistical test that may be used to determine if a set of data comes from a particular probability distribution [START_REF] Roblès | A statistical test suite for random and pseudorandom number generators for cryptographic applications[END_REF], [START_REF] Bercu | Modélisation stochastique et simulation -Cours et applications[END_REF]).

Empirical distribution function F n (x) for X 1 , . . . , X n MOSIM'12 -June 06-08, 2012 -Bordeaux -France sample is defined by:

F n (x) = 1 n n i=1 δ Xi≤x , (17)
δ Xi≤x = 1 si X i ≤ x, 0 sinon .
The Kolmogorov-Smirnov test statistic is defined as follows:

D n = sup x |F n (x) -F (x)|. ( 18
)

Aspin-Welch test

Aspin-Welch's test [START_REF] Welch | Welch's k-sample test[END_REF], is defined by t statistic in the following formula:

t = x 1 -x 2 σ 2 ( 1 n 1 + 1 n 2 ) , (19)
σ 2 = n 1 σ 2 1 + n 2 σ 2 2 n 1 + n 2 -2 . ( 20
)
• x i : the i th sample mean,

• σ: an estimator of the common standard deviation of the two samples,

• σ i : samples standard deviation,

• n i : sample size.

Epistemic uncertainties

This uncertainty is explicitly due to the design of the mathematical model. It is related to the human interpretation of the phenomenon which leads to imperfections in the design. We examine epistemic errors on our synthetic model and determine elements with the lowest uncertainty.

For a n measures series of x 1 , x 2 , . . . , x i , . . . , x n , the uncertainty on the average according to [START_REF] Pibouleau | Assimiler et utiliser les statistiques, Ellipses Marketing, technosup[END_REF] is:

∆x = σ √ n = 1 n(n -1) n i=1 (x i -x) 2 . ( 21
)
• σ: samples standard deviation.

Evaluation process

We try to evaluate the best Hidden Markov Model topologies presented in figure 2, by using all criteria shown above.

EVALUATION PROCESS

We use synthetic model to produce about 1000 data events. These simulated symbols, according to real maintenance by using synthetic model ( §4.2) to simulate real industrial environnement. We choose "λ i " (failure rate) and "µ i " (repair rate) of HMM parameters [START_REF] Vrignat | Use of HMM for evaluation of maintenance activities[END_REF], to match as possible, with maintenance recording (table 1).

Synthetic model

We make our synthetic model with Matlab by using four states oriented topology 2 presented in figure 2(b). We use this model feature because it has good performance in maintenance activities [START_REF] Vrignat | Use of HMM for evaluation of maintenance activities[END_REF]. Then, we build sequences of data (also named "signature") using this model as the reference model, by injecting stochastic symbols in this HMM.

We use these symbols sequences as Markov chain (see These simulated symbols, according to real industrial process [START_REF] Vrignat | Use of HMM for evaluation of maintenance activities[END_REF], are obtained by using uniform and Normal (Gaussian) distribution (see fig- ures 5 and6). We use these symbols to train three different HMM topologies, described in figure 2

RESULTS AND DISCUSSION

We first discuss the choice of synthetic model reference as the oriented model 2. Knowing transition probabilities of states/symbols, we tested several different topologies on different learning algorithms. At the end of the comparatives tests, we concluded that the best topology, according to failure detection, among different learning algorithms, was the topology 2 [START_REF] Vrignat | Use of HMM for evaluation of maintenance activities[END_REF].

× × Kolmogorov-Smirnov × × × Best uncertainty × × ×
Table 5: General results for some criteria.

CONCLUSION

After testing randomness of our synthetic model generator, we have applied all criteria studied above on three different HMM topologies. We have successfully applied this method to three different models. The first one, uses Shannon's entropy and entropic filter. Given a set of observations sequences simulated by our synthetic model, we verified that the

Symbols generated by HMM reference (Normal distribution)

Average entropy -states / symbols q q q q q q Topology1 Topology2 Topology3 Uncertainties on the average q q q q q q Topology1 Topology2 Topology3 We gave heterogeneous methods to help expert of maintenance to choose and select the best way to optimize his maintenance policy. Indeed, when HMM output will indicate an orange level (S2), the expert would decide for a preventive maintenance before the breakdown. Good relevance and good errors rate for topology N • 2, Baum-Welch algorithm / decoding by Forward Variable and a Gaussian distribution of observation sequences, allow us to apply these results as part of preventive maintenance applications. Indeed, in our work on industrial breakdown prediction, determining the best model is expected to reduce significantly failure rate in production. Minimizing failure rate, will reduce dangerous human intervention in maintenance, especially in an unsafe working environment. Decreasing machines failures will furthermore reduce power consumption and thus reduce release of CO 2 .

In further work, we will try to test robustness of our synthetic model with different noises. Our research goals are to validate a real choice of a model: topology, symbol,. . . without a priori knowledge on results.

Figure 2 :

 2 Figure 2: Four states Hidden Markov Models.

Figure 4 :

 4 Figure 4: Degradation of process.

FigureFigure 6 :

 6 Figure 5: HMM sequences example, Normal distribution.

  learning, with entropy filter Segmental K-means learning, with entropy filter HMM-reference, without entropy filter Baum-Welch learning, without entropy filter Segmental K-means learning, without entropy filter → best entropy (a) Average entropy, Gaussian distribution Kolmogorov-Smirnov test B.W. HMM1 S.K. HMM1 B.W. HMM2 S.K. HMM2 B.W. HMM3 S.

Figure 9 :

 9 Figure 9: Evaluation results.

Table 1 :

 1 MOSIM'12 -June 06-08, 2012 -Bordeaux -France Example of recorded events from a maintenance database.

	Synthetic model		Name Dupond	Date 11/01/2007	Ope. Lubrication	Cd PM	IT 20	N 1	Code 9
	Hidden Markov		Dupond Dupond	11/01/2007 12/01/2007	Lubrication Lubrication	PM SEC	20 30	2 3	9 5
		Model 2		Dupond Dupond	12/01/2007 13/01/2007	Lubrication Padlock	PM PM	30 10	4 5	5 6
		(reference)		Dupond Dupond	13/01/2007 13/01/2007	Padlock Padlock	NTR NTR	30 30	6 7	5 5
					Dupond	16/01/2007	Lubrication	SP	90	8	1
					Dupond	19/01/2007	Padlock	OT	10	9	3
	Symbols generated Symbols generated	Symbols generated Symbols generated
	by Uniform by Uniform		by Normal by Normal
	distribution distribution		distribution distribution
					carried out on industrial process. We recall the mean-
					ing of selected symbols resulting from observations, in
	Topologies 1, 2 & 3		table 2. "SP" symbol corresponds to a stop of produc-
					tion units: process state = "STOP" in table 2. It is a
	Estimation of HMM	Decoding sequences	critical condition that our research tries to minimize.
	Baum-Welch Baum-Welch		Forward Variable	Process state = "RUN" when production units are running without failure. We study here this kind of
								Process states
								RUN
	Segmental K-means Segmental K-means		Viterbi	1	STOP (Troubleshooting / Stop Production) Interventions type SP
					2	SM	(Setting Machine)
					3	OT	(Other)
					4	OBS	(Observation)
					5	PM	(Preventive Maintenance, Production not stopped)
					6	SEC	(Security)
	Sequence analysis of 3 Topologies	7 8	PUP CM	(Planified Upgrading) (Cleaning Machine)
	-Shannon's entropy,			9 10	PMV NTR	(Preventive Maintenance Visit) (Nothing to report)
	-Maximum likelihood, AIC, BIC,
	-Kolmogorov-Smirnov & Aspin-Welch.
	Uncertainty Analysis
	-Epistemic uncertainties.
	Give the most
	relevant model
	Figure 3: Matching model method, using synthetic
	model.
	industrial process, are obtained by using uniform
	and normal distribution. Correlatively, we produce
	states for others topologies by using the same pro-
	cess. Afterwards, these states are used to compare
	states models. Insofar as states are obtained by dif-
	ferent learning and decoding algorithms (diagram of
	this process is given in figure 3): Baum-Welch learn-
	ing, decoding by Forward Variable and Segmental K-
	means learning, decoding by Viterbi.
	4.1 Simulated	industrial	Computerized
	Maintenance Management System
	Nowadays, every industrial factory uses preventive
	maintenance. Maintenance agents can consign their
	actions and observations in a centralized database
	(see table 1). For example, symbols "PM, OT,
	SP, . . . " could characterize maintenance activities

Table 2 :

 2 Symbolic coding system of maintenance interventions.

table 3

 3

	), to model degradation level of a process (ex-

Table 3 :

 3 Sequence of a message from maintenance database.

  MOSIM'12 -June 06-08, 2012 -Bordeaux -France most relevant model obtained a good "entropic" score. That corroborates[START_REF] Vrignat | Use of HMM for evaluation of maintenance activities[END_REF]) results which showed that topology N • 2 was the one which came closest to real industrial process. This criterion also showed that Baum-Welch learning algorithm with Forward Variable decoding gave best results. Moreover Shannon's entropy showed that Normal distribution was the best one to simulate industrial observations. Maximum likelihood and BIC emphasized that HMM 2 was the best topology. Unfortunately, these criteria were too near each other to make conclusions about learning algorithm. With Aspin-Welch and Kolmogorov-Smirnov test, we could verify that the most relevant model had the "goodness of fit" i.e. how well model fits the set of observations sequences. The statistical way told us the same conclusions than entropic results (topology, learning algorithm and distribution). Same goes for errors of epistemic uncertainties: topology N • 2, Baum-Welch learning algorithm with Forward Variable decoding and normal distribution of stochastic symbols gave the lowest error rate. Thus, we specified our analysis from[START_REF] Roblès | A statistical test suite for random and pseudorandom number generators for cryptographic applications[END_REF] paper.

National Institute of Standards and Technology

The probability (under the null hypothesis of randomness) that the chosen test statistic will assume values that are equal to or worse than the observed test statistic value when considering the null hypothesis. The p-value is frequently called the "tail probability".


Diana Moise

Gabriel Antoniu

Luc Bougé

On-the-fly Task Execution for Speeding Up Pipelined MapReduce

Keywords: MapReduce, pipeline MapReduce applications, intermediate data management, task scheduling, Hadoop, HDFS

The MapReduce programming model is widely acclaimed as a key solution to designing data-intensive applications. However, many of the computations that fit this model cannot be expressed as a single MapReduce execution, but require a more complex design. Such applications consisting of multiple jobs chained into a long-running execution are called pipeline MapReduce applications. Standard MapReduce frameworks are not optimized for the specific requirements of pipeline applications, yielding performance issues. In order to optimize the execution on pipelined MapReduce, we propose a mechanism for creating map tasks along the pipeline, as soon as their input data becomes available. We implemented our approach in the Hadoop MapReduce framework. The benefits of our dynamic task scheduling are twofold: reducing job-completion time and increasing cluster utilization by involving more resources in the computation. Experimental evaluation performed on the Grid'5000 testbed, shows that our approach delivers performance gains between 9% and 32%.

Introduction

The MapReduce abstraction has revolutionized the data-intensive community and has rapidly spread to various research and production areas. Google introduced MapReduce [START_REF] Dean | MapReduce: simplified data processing on large clusters[END_REF] as a solution to the need to process datasets up to multiple terabytes in size on a daily basis. The goal of the MapReduce programming model is to provide an abstraction that enables users to perform computations on large amounts of data.

The MapReduce abstraction is inspired by the "map" and "reduce" primitives commonly used in functional programming. When designing an application using the MapReduce paradigm, the user has to specify two functions: map and reduce that are executed in parallel on multiple machines. Applications that can be modeled by the means of MapReduce, mostly consist of two computations: the "map" step, that applies a filter on the input data, selecting only the data that satisfies a given condition, and the "reduce" step, that collects and aggregates all the data produced by the first phase. The MapReduce model exposes a simple interface, that can be easily manipulated by users without any experience with parallel and distributed systems. However, the interface is versatile enough so that it can be employed to suit a wide range of data-intensive applications. These are the main reasons for which MapReduce has known an increasing popularity ever since it was introduced.

An open-source implementation of Google's abstraction was provided by Yahoo! through the Hadoop [START_REF]The Hadoop MapReduce Framework[END_REF] project. This framework is considered the reference MapReduce implementation and is currently heavily used for various purposes and on several infrastructures. The MapReduce paradigm has also been adopted by the cloud computing community as a support to those cloud-based applications that are data-intensive. Cloud providers support MapReduce computations so as to take advantage of the huge processing and storage capabilities the cloud holds, but at the same time, to provide the user with a clean and easy-to-use interface. Amazon released ElasticMapReduce [START_REF]Amazon Elastic MapReduce[END_REF], a web service that enables users to easily and cost-effectively process large amounts of data. The service consists of a hosted Hadoop framework running on Amazon's Elastic Compute Cloud (EC2) [START_REF]Amazon Elastic Compute Cloud (EC2)[END_REF]. Amazon's Simple Storage Service (S3) [START_REF]Amazon Simple Storage Service (S3[END_REF] serves as storage layer for Hadoop. AzureMapReduce [START_REF] Gunarathne | MapReduce in the Clouds for Science[END_REF] is an implementation of the MapReduce programming model, based on the infrastructure services the Azure cloud [START_REF]The Windows Azure Platform[END_REF] offers. Azure's infrastructure services are built to provide scalability, high throughput and data availability. These features are used by the AzureMapReduce runtime as mechanisms for achieving fault tolerance and efficient data processing at large scale.

MapReduce is used to model a wide variety of applications, belonging to numerous domains such as analytics (data processing), image processing, machine learning, bioinformatics, astrophysics, etc. There are many scenarios in which designing an application with MapReduce requires the users to employ several MapReduce processing. These applications that consist of multiple MapReduce jobs chained into a long-running execution, are called pipeline MapReduce applications. In this paper, we study the characteristics of pipeline MapReduce applications, and we focus on optimizing their execution. Existing MapReduce frameworks manage pipeline MapReduce applications as a sequence of MapReduce jobs. Whether they are employed directly by users or through higher-level tools, MapReduce frameworks are not optimized for executing pipeline applications. A major drawback comes from the fact that the jobs in the pipeline have to be executed sequentially: a job cannot start until all the input data it processes has been generated by the previous job in the pipeline.

In order to speed up the execution of pipelined MapReduce, we propose a new mechanism for creating "map" tasks along the pipeline, as soon as their input data becomes available. Our approach allows successive jobs in the pipeline to overlap the execution of "reduce" tasks with that of "map" tasks. In this manner, by dynamically creating and scheduling tasks, the framework is able to complete the execution of the pipeline faster. In addition, our approach ensures a more efficient cluster utilization, with respect to the amount of resources that are involved in the computation. We implemented the proposed mechanisms in the Hadoop MapReduce framework [START_REF]The Hadoop MapReduce Framework[END_REF] and evaluated the benefits of our approach through extensive experimental evaluation.

In section 2 we present an overview of pipelined MapReduce as well as the scenarios in which this type of processing is employed. Section 3 introduces the mechanisms we propose and shows their implementation in Hadoop. Section 4 is dedicated to the experiments we performed; we detail the environmental setup and the scenarios we selected for execution in order to measure the impact of our approach. Section 5 summarizes the contributions of this work and presents directions for future work.

Pipeline MapReduce applications: overview and related work

Many of the computations that fit the MapReduce model, cannot be expressed as a single MapReduce execution, but require a more complex design. These applications that consist of multiple MapReduce jobs chained into a long-running execution, are called pipeline MapReduce applications. Each stage in the pipeline is a MapReduce job (with 2 phases, "map" and "reduce"), and the output data produced by one stage is fed as input to the next stage in the pipeline. Usually, pipeline MapReduce applications are long-running tasks that generate large amounts of intermediate data (the data produced between stages). This type of data is transferred between stages and has different characteristics from the meaningful data (the input and output of an application). While the input and output data are expected to be persistent and are likely to be read multiple times (during and after the execution of the application), intermediate data is transient data that is usually written once, by one stage, and read once, by the next stage.

However, there are few scenarios in which users directly design their application as a pipeline of MapReduce jobs. Most of the use cases of MapReduce pipelines come from applications that translate into a chain of MapReduce jobs. One of the drawbacks of the extreme simplicity of the MapReduce model is that it cannot be straightforwardly used in more complex scenarios. For instance, in order to use MapReduce for higher-level computations (for example, the operations performed in the database domain) one has to deal with issues like multi-stage execution plan, branching data-flows, etc. The trend of using MapReduce for database-like operations led to the development of high-level query languages that are executed as MapReduce jobs, such as Hive [START_REF] Thusoo | Hive: A warehousing solution over a MapReduce framework[END_REF], Pig [START_REF] Olston | Pig Latin: a not-so-foreign language for data processing[END_REF], and Sawzall [START_REF] Pike | Interpreting the data: Parallel analysis with Sawzall[END_REF]. Pig is a distributed infrastructure for performing high-level analysis on large data sets. The Pig platform consists of a high-level query language called PigLatin and the framework for running computations expressed in PigLatin. PigLatin programs comprise SQL-like high-level constructs for manipulating data that are interleaved with MapReduce-style processing. The Pig framework compiles these programs into a pipeline of MapReduce jobs that are executed within the Hadoop environment.

The scenarios in which users actually devise their applications as MapReduce pipelines, involve binary data whose format does not fit the high-level structures of the aforementioned frameworks. In order to facilitate the design of pipeline MapReduce applications, Cloudera recently released Crunch [START_REF] Crunch | [END_REF], a tool that generates a pipeline of MapReduce jobs and manages their execution. While there are several frameworks that generate pipeline MapReduce applications, few works focus on optimizing the actual execution of this type of applications. In [START_REF] Morton | Estimating the progress of MapReduce pipelines[END_REF], the authors propose a tool for estimating the progress of MapReduce pipelines generated by Pig queries. The Hadoop Online Prototype (HOP) [START_REF] Condie | Mapreduce online[END_REF] is a modified version of the Hadoop MapReduce framework that supports online aggregation, allowing users to get snapshots from a job as it is being computed. HOP employs pipelining of data between MapReduce jobs, i.e., the reduce tasks of one job can optionally pipeline their output directly to the map tasks of the next job. However, by circumventing the storing of data in a distributed file system (DFS) between the jobs, fault tolerance cannot be guaranteed by the system. Furthermore, as the computation of the reduce function from the previous job and the map function of the next job cannot be overlapped, the jobs in the pipeline are executed sequentially.

3 Introducing dynamic scheduling of map tasks in Hadoop

Motivation

In a pipeline of MapReduce applications, the intermediate data generated between the stages represents the output data of one stage and the input data for the next stage. The intermediate data is produced by one job and consumed by the next job in the pipeline. When running this kind of applications in a dedicated framework, the intermediate data is usually stored in the distributed file system that also stores the user input data and the output result. This approach ensures intermediate data availability, and thus, provides fault tolerance, a very important factor when executing pipeline applications. However, using MapReduce frameworks to execute pipeline applications raises performance issues, since MapReduce frameworks are not optimized for the specific features of intermediate data. The main performance issue comes from the fact that the jobs in the pipeline have to be executed sequentially: a job cannot start until all the input data it processes has been generated by the job in the previous stage of the pipeline. Consequently, the framework runs only one job at a time, which results in inefficient cluster utilization and basically, a waste of resources.

Executing pipeline MapReduce applications with Hadoop

The Hadoop project provides an open-source implementation of Google's MapReduce paradigm through the Hadoop MapReduce framework [START_REF]The Hadoop MapReduce Framework[END_REF][START_REF] White | Hadoop: The Definitive Guide[END_REF]. The framework was designed following Google's architectural model and has become the reference MapReduce implementation. The architecture is tailored in a master-slave manner, consisting of a single master jobtracker and multiple slave tasktrackers. The jobtracker's main role is to act as the task scheduler of the system, by assigning work to the tasktrackers. Each tasktracker disposes of a number of available slots for running tasks. Every active map or reduce task takes up one slot, thus a tasktracker usually executes several tasks simultaneously. When dispatching "map" tasks to tasktrackers, the jobtracker strives at keeping the computation as close to the data as possible. This technique is enabled by the data-layout information previously acquired by the jobtracker. If the work cannot be hosted on the actual node where the data resides, priority is given to nodes closer to the data (belonging to the same network rack). The jobtracker first schedules "map" tasks, as the reducers must wait for the "map" execution to generate the intermediate data.

Hadoop executes the jobs of a pipeline MapReduce application in a sequential manner. Each job in the pipeline consists of a "map" and a "reduce" phase. The "map" computation is executed by Hadoop tasktrackers only when all the data it processes is available in the underlying DFS. Thus, the mappers are scheduled to run only after all the reducers from the preceding job have completed their execution. This scenario is also representative for a Pig processing: the jobs in the logical plan generated by the Pig framework are submitted to Hadoop sequentially. In consequence, at each step of the pipeline, at most the "map" and "reduce" tasks of the same job are being executed. Running the mappers and the reducers of a single job involves only a part of the cluster nodes. The rest of the computational and storage cluster capabilities remains idle.

Our approach

In order to speed-up the execution of pipeline MapReduce applications, and also to improve cluster utilization, we propose an optimized Hadoop MapReduce framework, in which the scheduling is done in a dynamic manner. For a better understanding of our approach, we first detail the process through which "map" and "reduce" tasks are created and scheduled in the original Hadoop MapReduce framework. Figure 1 displays the job submission process. The first step is for the user to specify the "map" and "reduce" computations of the application. The Hadoop client generates all the job-related information (input and output directories, data placement, etc.) and then submits the job for execution to the jobtracker. On the jobtracker's side, the list of "map" and "reduce" tasks for the submitted job is created. The number of "map" tasks is equal to the number of chunks in the input data, while the number of "reduce" tasks is computed by taking into account various factors, such as the cluster capacity, the user specification, etc. The list of tasks is added to the job queue that holds the jobs to be scheduled for execution on tasktrackers. In the Hadoop MapReduce framework, the "map" and "reduce" tasks are created by the jobtracker when the job is submitted for execution. When they are created, the "map" tasks require to know the location of the chunks they will work on.

In the context of multiple jobs executed in a pipeline, the jobs are submitted by the client to the jobtracker sequentially, as the chunk-location information is available only when the previous job completes. Our approach is based on the remark that a "map" task is created for a single input chunk. It only needs to be aware of this very chunk location. Furthermore, when it is created, the only information that the "map" task requires, is the list of nodes that store the data in its associated chunk. We modified the Hadoop MapReduce framework to create "map" tasks dynamically, that is, as soon as a chunk is available for processing. This approach can bring substantial benefits to the execution of pipeline MapReduce applications. Since the execution of a job can start as soon as the first chunk of data is generated by the previous job, the total runtime is significantly reduced. Additionally, the tasks belonging to several jobs in the pipeline can be executed at the same time, which leads to a more efficient cluster utilization.

The modifications and extensions of the Hadoop MapReduce framework that we propose, are further presented and summarized on Figure 2. (size, f iles) ← tasktracker.writeReduceOutputData() 3:

jobtracker.transmitOutputInf o(size, f iles) 4: end procedure Job-submission process Client side. On the client side, we modified the submission process between the Hadoop client and the jobtracker. Instead of waiting for the execution to complete, the client launches a job monitor that reports the execution progress to the user. With this approach, a pipeline MapReduce application employs a single Hadoop client to run the application. The client submits all the jobs in the pipeline from the beginning, instead of submitting them sequentially, i.e., the modified Hadoop client submits the whole set of jobs job 1 ...job n for execution. Jobtracker side. The job-submission protocol is similar to the one displayed on Figure 1. However, at submission time, only the input data for job 1 is available in the DFS. Regarding job 2 ...job n , the input data has to be generated throughout the pipeline. Thus, the jobtracker creates the set of "map" and "reduce" tasks only for job 1 . For the rest of the jobs, the jobtracker creates only "reduce" tasks, while "map" tasks will be created along the pipeline, as the data is being generated.

Job scheduling

Tasktracker side: For a job i in the pipeline, the data produced by the job's "reduce" phase (reduce i ) represents the input data of job i+1 's "map" task (map i+1 ). When reduce i is completed, the tasktracker writes the output data to the backend storage. We modified the tasktracker code to notify the jobtracker whenever it successfully completes the execution of a "reduce" function: the tasktracker informs the jobtracker about the size of the data produced by the "reduce" task.

Algorithm 2 Update job (on jobtracker) end for 23: end procedure Jobtracker side: In our modified framework, the jobtracker keeps track of the output data generated by reducers in the DFS. This information is important for the scheduling of the jobs in the pipeline, as the output directory of job i is the input directory of job i+1 . Each time data is produced in job i 's output directory, the jobtracker checks to see if it can create new "map" tasks for job i+1 . If the data accumulated in job i+1 's input directory is at least of the size of a chunk, the jobtracker creates "map" tasks for the newly generated data. For each new chunk, the jobtracker creates a "map" task to process it. All the "map" tasks are added to the scheduling queue and then dispatched to idle tasktrackers for execution.

The modifications on the tasktracker side are described in Algorithm 1. We extended the code with a primitive that sends to the jobtracker the information about the "reduce" output data: the files written to the DFS and the total size of the data. Algorithm 2 shows the process of updating a job with information received from tasktrackers. The algorithm is integrated in the jobtracker code, mainly in the scheduling phase. The jobtracker also plays the role of task scheduler. It keeps a list of data written to the input directory of each job. For each received update, the jobtracker checks if the data in the job's input directory reaches at least a chunk in size (64 MB default). If it is the case, "map" tasks will be created, one per each new data chunk. Otherwise, the job's information is stored for subsequent processing. The mechanism of creating "map" tasks is presented in Algorithm 3, executed by the jobtracker, and integrated into the job Algorithm 3 Create map tasks (on job) return splitBytes 19: end function code. We extended the code so that each job holds the list of files that were generated so far in the job's input directory. When the jobtracker computes that at least a chunk of input data has been generated, new "map" tasks are created for the job. The data in the files is split into chunks. A "map" task is created for each chunk and the newly launched tasks are added to the scheduling queue. The jobtracker also informs the "reduce" tasks that the number of "map" tasks has changed. The reducers need to be aware of the number of mappers of the same job, as they have to transfer their assigned part of the output data from all the mappers to their local disk.

Evaluation

We validate the proposed approach through a series of experiments that compare the original Hadoop framework with our modified version, when running pipeline applications.

Environmental setup

The experiments were carried out on the Grid'5000 [START_REF] Jégou | Grid'5000: a large scale and highly reconfigurable experimental Grid testbed[END_REF] testbed. The Grid'5000 project is a widely-distributed infrastructure devoted to providing an experimental platform for the research community. The platform is spread over 10 geographical sites located through on French territory and 1 in Luxembourg. For our experiments, we employed nodes from the Orsay cluster of the Grid'5000. The nodes are outfitted with dual-core x86 64 CPUs and 2 GB of RAM. Intra-cluster communication is done through a 1 Gbps Ethernet network. We performed an initial test at a small scale, i.e., 20 nodes, in order to assess the impact of our approach. The second set of tests involves 50 nodes belonging to the Orsay cluster. The evaluation presented here focuses on assessing the performance gains of the optimized MapReduce framework we propose, over the original one. To this end, we developed a benchmark that creates a pipeline of n MapReduce jobs and submits them to Hadoop for execution. Each job in the pipeline simulates a load that parses keyvalue pairs from the input data and outputs 90% of them as final result. In this manner, we manage to obtain a long-running application that generates a large amount of data, allowing our dynamic scheduling mechanism to optimize the execution of the pipeline. The computation itself is not relevant in this case, as our goal is to create a scenario in which enough data chunks are generated along the pipeline so that "map" tasks can be dynamically created. We run this type of application first with the original Hadoop framework, then with our optimized version of Hadoop. In both cases, we measure the pipeline completion-time and compare the results.

Results

Short-running pipeline applications

In a first set of experiments, we run the benchmark in a small setup involving 20 nodes, on top of which HDFS and Hadoop MapReduce are deployed as follows: a dedicated machine is allocated for each centralized entity (namenode, jobtracker), a node serves as the Hadoop client that submits the jobs, and the rest of 17 nodes represent both datanodes and tasktrackers. At each step, we keep the same deployment setup and we increase the number of jobs in the pipeline to be executed. The first test consists in running a single job, while the last one runs a pipeline of 9 MapReduce jobs. The application's input data, i.e., job 1 's input data, consists of 5 data chunks (a total of 320 MB). Job i keeps 90% of the input data it received from job i-1 . In the case of the 9-job pipeline, this data-generation mechanism leads to a total of 2 GB of data produced throughout the pipeline, out of which 1.6 GB account for intermediate data.

Figure 3 shows the execution time of pipeline applications consisting of an increasing number of jobs (from 1 to 9), in two scenarios: when running on top of the original Hadoop, and with the pipeline-optimized version we proposed. In the first case, the client sequentially submits the jobs in the pipeline to Hadoop's jobtracker, i.e., waits for the completion of job i before submitting job i+1 . When using our version of Hadoop, the client submits all the jobs in the pipeline from the beginning, and then waits for the completion of the whole application. As expected, the completion time in both cases increases proportionally to the number of jobs to be executed. However, our framework manages to run the jobs faster, as it creates and schedules "map" tasks as soon as a chunk of data is generated during the execution. This mechanism speeds-up the execution of the entire pipeline, and also exhibits a more efficient cluster utilization. Compared to the original Hadoop, we obtain a performance gain between 26% and 32%.

Long-running pipeline applications

The first experiment we presented was focused on pipeline applications that consist of a small up to a medium number of jobs (1 to 9). Due to the long-running nature of pipeline applications and considering the significant size of the intermediate data our benchmark generates, we performed experiments with larger applications and larger datasets in a different setup, including 50 nodes. HDFS and Hadoop MapReduce are deployed as for the previous experiment, employing thus 47 tasktrackers. The size of the input data for each pipeline application amounts to 2.4 GB (40 data chunks). We vary the number of jobs to be executed in each pipeline, from 10 to 35. For the longestrunning application, the generated data add up to a total of 24.4 GB.

The results for this setup are displayed on Figure 4. Consistently with the previous results, our approach proves to be more efficient for long-running applications as well. The performance gains vary between 9% and 19% in this scenario. The benefits of our optimized framework have a smaller impact in this case, because of the data size involved in the experiment. Since more chunks are used as input, and substantially more chunks are being generated throughout the pipeline, a large part of the tasktrackers is involved in the current computation, leaving a smaller number of resources available for dynamically running created "map" tasks.

Scaling out

In the context of pipeline applications, the number of nodes involved in the Hadoop deployment can have a substantial impact on completion time. Furthermore, considering our approach of dynamic scheduling "map" tasks, the scale of the deployment is an important factor to take into account. Thus, we performed an experiment in which we vary the number of nodes employed by the Hadoop framework. At each step, we increase the number of nodes used for the deployment, such that the number of tasktrackers that execute "map" and "reduce" tasks is varied from 10 to 45. In each setup, we run the aforementioned benchmark with a fixed number of 7 jobs in the pipeline. The input data is also fixed, consisting of 25 chunks of data, i.e., 1.5 GB.

Figure 5 shows the completion time of the 7-job pipeline when running with both original Hadoop and modified Hadoop, while increasing the deployment setup. As the previous experiments also showed, our improved framework manages to execute the jobs faster than the original Hadoop. In both cases, as more nodes are added to the deployment, the application is executed faster, as more tasktrackers can be used for running the jobs. However, increasing the number of nodes yields performance gains up to a point, which corresponds to 25 tasktrackers for the original Hadoop. This number is strongly related to the number of chunks in the input data, since the jobtracker schedules a tasktracker to run the "map" computation on each chunk. For the modified Hadoop, the point after which expanding the deployment does not prove to be profitable any longer, is higher than for the original Hadoop. The reason for this behavior lies in the scheduling approach of both frameworks: in original Hadoop, the scheduling of jobs is done sequentially, while in modified Hadoop, the "map" tasks of each job are scheduled as soon as the data is generated. The completion time starts to increase in both cases after a certain point, as the overhead of launching and managing a larger number of tasktrackers overcomes the advantage of having more nodes in the deployment.

Conclusions

In this paper we address a special class of MapReduce applications, i.e., applications that consist of multiple jobs executed in a pipeline. In this context, we focus on improving the performance of the Hadoop MapReduce framework when executing pipelines. Our proposal consists mainly of a new mechanism for creating tasks along the pipeline, as soon as their input data become available. This dynamic task scheduling leads to an improved performance of the framework, in terms of job completion time. In addition, our approach ensures a more efficient cluster utilization, with respect to the amount of resources involved in the computation. The approach presented in this paper can be further extended so as to allow the overlapping of several jobs in the pipeline. However, this aspect would require careful tuning of the scheduling of tasks in MapReduce frameworks. Deciding whether to execute reducers for the current job or to start mappers for the next jobs is a crucial aspect that requires complex metrics. As future direction, we also plan to validate the proposed approach through experiments with higher-level frameworks in the context of pipelined MapReduce, such as Pig.

Fig. 1 .

 1 Fig. 1. Job submission process in Hadoop.

Fig. 2 .

 2 Fig. 2. Dynamic creation of "map" tasks.

Fig. 3 .

 3 Fig. 3. Completion time for short-running pipeline applications.

Fig. 4 .

 4 Fig. 4. Completion time for long-running pipeline applications.

Fig. 5 .

 5 Fig. 5. Impact of deployment setup on performance.

Acknowledgments

This work was supported in part by the Agence Nationale de la Recherche (ANR) under Contract ANR-10-SEGI-01 (MapReduce Project). The experiments presented in this paper were carried out using the Grid'5000 testbed, an initiative of the French Ministry of Research through the ACI GRID incentive action, INRIA, CNRS and RENATER and other contributing partners (see http://www.grid5000.org/).