Cécile Voisset
email: cecile.voisset@univ-brest.fr

Marc Blondel

Gary W Jones

Gaëlle Friocourt

Guillaume Stahl

Stéphane Chédin

Vincent Beringue

Reynald Gillet

The double life of the ribosome: when its protein folding activity supports prion propagation

Keywords: prion, ribosome, PFAR, chaperon, protein folding, RNA

It is no longer necessary to demonstrate that ribosome is the central machinery of protein synthesis. But it is less known that it is also key player of the protein folding process through another conserved function: the protein folding activity of the ribosome (PFAR). This ribozyme activity, discovered more than two decades ago, depends upon the domain V of the large rRNA within the large subunit of the ribosome. Surprisingly, we discovered that anti-prion compounds are also potent PFAR inhibitors, highlighting an unexpected link between PFAR and prion propagation.

In this review, we discuss the ancestral origin of PFAR in the light of the ancient RNA world hypothesis. We also consider how this ribosomal activity fits into the landscape of cellular protein chaperones involved in the appearance and propagation of prions and other amyloids in mammals. Finally, we examine how drugs targeting the protein folding activity of the ribosome could be active against mammalian prion and other protein aggregation-based diseases, making PFAR a promising therapeutic target for various human protein misfolding diseases.

Present in every cell and mitochondria, ribosomes are composed of two subunits, which themselves are made up of ribosomal RNA (rRNA) and proteins. Broadly, the small subunit initiates the translational process and ensures the correct decoding of genetic information, while the large subunit catalyzes the peptidyl transferase activity that covalently links amino acids together. While the central role of the ribosome in protein synthesis is well appreciated, little is known about the second ribozyme activity of the ribosome: its protein folding activity (PFAR).

Since its discovery, the existence of PFAR has been controversial and difficult to gain acceptance within the scientific community. Despite PFAR being first identified in 1994 by the group of C. Das Gupta 1 and this activity being corroborated by several other teams [START_REF] Das | Role of the ribosome in protein folding[END_REF] , PFAR is often overlooked, as illustrated by its absence from reviews on non-coding RNAs. However, once getting over the initial surprise of the existence of such an activity, it seems self-evident that the biological entity that has evolved to synthesize proteins must also aid them achieve a proper three-dimensional functional state prior to their release. In addition, this is fully consistent with the estimation that, apart from spontaneously folded proteins, only a fraction of the total cellular proteins can be folded by classical protein chaperones [START_REF] Pechmann | The ribosome as a hub for protein quality control[END_REF] . Initially, PFAR was described in vitro for bacterial ribosomes and was quickly shown to be a conserved function of any ribosome, whether from bacteria, eubacteria, eukaryotes or even mitochondria [START_REF] Das | Role of the ribosome in protein folding[END_REF] . The conservation of the protein folding capacity of the ribosome among species is not a surprise when considering the high rate of conservation of rRNA in the ribosome core throughout evolution [START_REF] Melnikov | One core, two shells: bacterial and eukaryotic ribosomes[END_REF] . As one may expect, PFAR is a versatile process that has been demonstrated to be able to refold any protein challenged so far in vitro 2 and in vivo 5--8 . This folding activity appears to be inherent to the conserved RNA domain that also harbors the peptidyl transferase activity: domain V of the rRNA of the large subunit of the ribosome (23S for bacteria, 25S for yeast and 28S for mammals). However, the nucleotides of domain V involved in its protein folding activity are different from those involved in its peptidyl transferase activity 9, 10 (Figure 1).

The protein folding mediated by domain V is a two-step post-translational process: the neosynthesized polypeptide is firstly folded by the central loop of domain V (RNA1) and remains associated to it until the intervention of a second part of domain V (RNA2) which is responsible for the release of the folded protein [START_REF] Pal | Complementary role of two fragments of domain V of 23 S ribosomal RNA in protein folding[END_REF] . The nucleotides involved in PFAR are localized at the interface of the ribosome's small and large subunits [START_REF] Pang | The antiprion compound 6-aminophenanthridine inhibits the protein folding activity of the ribosome by direct competition[END_REF] . Ribosomal subunits dissociate in the presence of unfolded polypeptides, making them more accessible to PFAR-involved nucleotides and thus enhancing their folding ability 2 . This is in good agreement with the fact that protein synthesis and protein folding are synchronized: as long as the peptidyl transferase activity continues, the protein folding activity of the ribosome is silenced and only becomes operational when translation is completed [START_REF] Mondal | Impact of P-Site tRNA and antibiotics on ribosome mediated protein folding: studies using the Escherichia coli ribosome[END_REF] .

In the midst of identifying new anti-prion compounds, we identified anti-prion drugs such as 6aminophenanthridine (6AP, [START_REF] Bach | Isolation of drugs active against mammalian prions using a yeast-based screening assay[END_REF] ), guanabenz (GA, [START_REF] Tribouillard-Tanvier | Antihypertensive drug guanabenz is active in vivo against both yeast and mammalian prions[END_REF] ) and imiquimod (IQ, [START_REF] Oumata | The toll-like receptor agonist imiquimod is active against prions[END_REF] ) which are active in vivo against yeast and mammalian prions and that were amazingly identified as PFAR inhibitors.

The discovery that 6AP and GA anti-prion drugs are also anti-PFAR drugs led us naturally to suggest that PFAR may be linked to prion propagation. Although the primary role of protein chaperones is to prevent protein misfolding and aggregation, involvement of protein chaperones like PFAR in the propagation of prion conformation is self-evident, as amyloid-forming proteins exist in several conformations and replication corresponds to propagation of differentially folded states [START_REF] Jones | Chaperoning prions: the cellular machinery for propagating an infectious protein?[END_REF] . This hypothesis has strong support as Hsp104p, a yeast heat shock protein, has been shown for a long time to be involved in yeast prion propagation, together with Hsp70 and Hsp40.

Similarly to Hsp104p, PFAR misregulation leads to a defect in the propagation of the yeast prion [PSI + ] 6 (Figure 2). The anti-PFAR drugs we identified were the first of that kind: all the previous anti-PFAR drugs described so far are antibiotics that also bind to domain V and inhibit its peptidyl transferase activity [START_REF] Basu | Protein folding following synthesis in vitro and in vivo: association of newly synthesized protein with 50S subunit of E. coli ribosome[END_REF][START_REF] Chattopadhyay | Protein folding in Escherichia coli: role of 23S ribosomal RNA[END_REF] . Of note, the fact that some antibiotics specifically target PFAR is a further indication of the central function of this ribozyme activity.

In this review, we consider the ancestral origin of PFAR and the relationship of this emerging ribosomal activity with the global protein folding capacity of the cell. We also discuss PFAR involvement in the propagation of prions and other amyloids in mammals.

PFAR activity: another relic of the ancient RNA world into modern ribosomes?

In current living organisms, the newly synthesized polypeptides undergo several maturation mechanisms in order to be correctly processed and translocated to achieve their functional folded state. These maturation processes are often linked to protein synthesis. They depend on translational speed and on interactions of the nascent polypeptide chain with the peptide exit tunnel and with the nascent chain-interacting protein factors, which are located on and around the ribosomal tunnel exit area. Beyond, a network of other cooperating chaperones acting posttranslationally in a coordinated ballet are also involved during the latter stages of the protein folding process [START_REF] Gloge | Co-translational mechanisms of protein maturation[END_REF] . However, this system brings the endless chicken-and-egg paradox back into play: to get mature and functional proteins, the cell needs… mature and functional chaperoning factors! To address this paradox, one has to consider the evolution of the protein folding process and how the ancient foundations may have developed. In the ancient RNA world hypothesis, earlier forms of life may rely on the dual function of RNA that simultaneously catalyzes enzymatic reactions and store genetic information [START_REF] Woese | The genetic code the molecularbasis for genetic expression[END_REF] . This suggests that RNA could be the main actor that carried out the chemical reactions allowing proteins to gradually emerge and become more complex due to the development of more and more sophisticated protein folding capabilities. Many molecular fossils of the ancient RNA world are still present and sometimes still active in modern organisms. Candidates must be catalytic, ubiquitous, and/or central to some aspect of metabolism [START_REF] Jeffares | Relics from the RNA world[END_REF] . Accordingly, one of the most significant piece of evidence to support that the first peptide bonding machines emerged in an RNA world is the fact that the modern ribosome is a ribozyme, or in other words that only RNA performs its key role in peptide bond formation [START_REF] Nissen | The structural basis of ribosome activity in peptide bond synthesis[END_REF] . The peptidyl-transferase center (PTC) of the modern ribosome is a universal and highly conserved RNA-only structure located in the domain V of 23S rRNA in bacteria or its equivalent parts in eukaryotic ribosome. It forms a symmetrical pocket in the heart of the large ribosomal subunit and probably originated from the dimerization of two stem-elbow-stem motifs [START_REF] Krupkin | A vestige of a prebiotic bonding machine is functioning within the contemporary ribosome[END_REF] . The PTC is considered to be the first proto-ribosome dating from the ancient RNA world since it was certainly capable of triggering catalytic reactions by itself. Strikingly, as supported by the binding sites of its protein substrates or inhibitors, PFAR activity is clustered within the PTC binding pocket, surrounding the core where the catalytic reaction takes place [START_REF] Pang | The antiprion compound 6-aminophenanthridine inhibits the protein folding activity of the ribosome by direct competition[END_REF][START_REF] Reis | Mode of action of the antiprion drugs 6AP and GA on ribosome assisted protein folding[END_REF] (Figure 1). Therefore, PFAR encompasses most criteria for making it a perfect vestige of the ancient RNA world as it is: i) part of another ribozyme, the PTC, ii) as ancient as the PTC, iii) supported by RNA only, iv) conserved from bacteria to eukaryotes and v) capable of playing a key role in modern protein synthesis. In this scenario, the first PTCs (proto-PTCs) were formed by the dimerization of short helical structures that created the first random but fragile peptides aleatory using amino acids. In a process that might be assimilated as "molecular Darwinism" [START_REF] Mace | Origins of tmRNA: the missing link in the birth of protein synthesis?[END_REF] , these proto-PTCs would then have evolved into a stable PTC, able to better favor protection, stability and activity of the peptides they synthesized. While one can assume that the earliest peptides were short, single domain and rapidly selected for robust chaperone-independent folding, the emergence of a primitive PFAR certainly conferred a selective advantage to the peptides. In turn, and resulting from the more and more efficient peptides and proteins being produced, the proto-PTC slowly co-evolved into a proto-ribosome and finally into the modern ribosome we recognize today, likely by progressively integrating multiple small ribonucleoprotein complexes into a much more complex machinery [START_REF] Harish | Ribosomal history reveals origins of modern protein synthesis[END_REF] . The traces of these ancient times remain active RNAs such as domain V harboring PTC and PFAR, still embedded in contemporary ribosomes, and may continue to play a role as part of the global protein folding capability of the cell.

Which place PFAR could take in the array of protein chaperones?

Prion propagation in yeast has been shown to be intimately linked to the expression and activity of a plethora of protein chaperones. We recently showed that PFAR and Hsp104p partially compensate each other for [PSI + ] propagation in yeast (Figure 2). We indeed observed that PFAR up-modulation can compensate for the partial loss of Hsp104p activity and that PFAR partial down-modulation is also compensated by Hsp104p increase [START_REF] Blondel | Protein Folding Activity of the Ribosome is involved in Yeast Prion Propagation[END_REF] . These results clearly indicate that PFAR is linked to the cellular array of protein chaperones, at least through Hsp104p. To this respect, PFAR participates to the very complex network required for cell proteostasis, i.e. the global protein quality control and the maintenance of proteome homeostasis.

Of note, polynucleotides, and more particularly RNAs, have been shown to exhibit potent chaperone activity in vitro [START_REF] Docter | Do nucleic acids moonlight as molecular chaperones?[END_REF] . Proteostasis involves hundreds of proteins constituting a highly regulated and integrated network.

One of the main challenges of the cellular response to stress is to synthesize, under adverse conditions, correctly folded proteins essential for survival. Since the PTC and PFAR are intimately linked, PFAR activity directly depends upon the synthesis of proteins, thus allowing the cell to establish a proper equilibrium between protein production and folding activities. In this context, the link between the PTC and PFAR can be seen as a strategy to avoid the synthesis of a polypeptide in the absence of efficient cellular folding activities. Remarkably, in situations of cellular stress, translation is strongly reduced, which consequently increases the population of non-translating ribosomes becoming available for protein folding. As a consequence, the corresponding misfolded proteins emerging from the deficient ribosome will be more prone to proteolysis. Thus, PFAR could also participate to proteostasis as a potential proofreading process of the PTC activity.

While Hsp104, and now PFAR, are key players in dictating the appearance and propagation of naturally occurring amyloid-based yeast prions, members of the cytosolic Hsp70 chaperone machinery, and associated co-chaperones, are important modulators of prion propagation, and in some instances de novo prion formation [START_REF] Jones | Chaperoning prions: the cellular machinery for propagating an infectious protein?[END_REF][START_REF] Reidy | Yeast prions help identify and define chaperone interaction networks[END_REF] . The cytosolic Hsp70-Ssa [Stress Seventy Sub-Family A] family members are well characterised as playing an integral role in modulating the propagation of a variety of yeast prions [START_REF] Hines | SWI], the prion formed by the chromatin remodeling factor Swi1, is highly sensitive to alterations in Hsp70 chaperone system activity[END_REF]28 and the ribosome-associated Hsp70-Ssb [Stress Seventy Sub-Family B] family members are anti-prion in their action since they repress the spontaneous appearance of [PSI + ] [START_REF] Chernoff | Evidence for a protein mutator in yeast: role of the Hsp70-related chaperone ssb in formation, stability, and toxicity of the [PSI] prion[END_REF] . Of note, contrary to Hsp104p and Hsp70 which expression is induced by stress, PFAR is a ready-to-use protein folding source immediately available in case of heatshock to supplement Hsp104 or to compensate for its absence, similarly to mammals where there is no HSP104 homolog.

Where could PFAR "sit" amongst these other cellular factors and how may they interact to influence prion propagation, or other protein folding events in vivo? One possibility is that some prion phenotypes consecutive to alterations in PFAR activity could result from indirect effects through alteration of chaperone systems such as the cytosolic Hsp70 machinery. However, such phenotypes are not due to indirect effects on Hsp70 abundance [START_REF] Blondel | Protein Folding Activity of the Ribosome is involved in Yeast Prion Propagation[END_REF] and it is unlikely that alterations in PFAR activity could significantly disturb Hsp70 specific functions, unless through indirect effect on Hsp70 co-chaperone activities. PFAR could possibly work in conjunction or in tandem with Hsp70s or other chaperones and the association of Hsp70-Ssb and the interaction with RAC [Ribosome Associated Complex] in prion formation and propagation [START_REF] Kiktev | Feedback control of prion formation and propagation by the ribosome-associated chaperone complex[END_REF] provides the basis for such interactions to evolve. Chaperones often function as multi-complex machines and it is conceivable that Hsp70 or co-chaperones could be involved into the delivery or processing of substrates acted upon by PFAR, or that PFAR could process substrates acted on by downstream chaperone machinery. The construction and characterisation of yeast cells modified to alter PFAR activity now provides the basis for a thorough genetic assessment of interaction between PFAR and an array of protein chaperone pathways. The involvement of PFAR in protein homeostasis could extend well beyond prion propagation and should it be the case, the integration with other chaperone networks is even more likely.

PFAR: mammalian prion propagation and beyond?

How could drugs targeting the protein folding activity of the ribosome, which mainly lies in the cytoplasm, be active against mammalian prion PrP Sc , which is believed to be modified mostly at the cell surface or on endocytic compartments? Addressing this question emphasizes our lack of precise knowledge regarding the cellular compartments where prion conversion and subsequent accumulation occur. This is partly due to the fact that direct and dynamic visualization in cells remains a highly challenging issue, notably because tagging the cellular form of the prion protein (PrP C ) most often prevents its conversion into the disease-specific isoform PrP Sc . In many differentiated cell types, a major proportion of PrP C is detected in lipid rafts at the cell surface, being anchored by a GPI moiety (for review [START_REF] Linden | Physiology of the prion protein[END_REF] ). PrP C expression at the cell surface is required for conversion into misfolded PrP Sc 32,[START_REF] Paquet | Prion infection of epithelial Rov cells is a polarized event[END_REF] and this process may occur rapidly [START_REF] Goold | Rapid cell-surface prion protein conversion revealed using a novel cell system[END_REF] . Several reports also indicate that a substantial fraction of PrP C cycles constitutively between the plasma membrane and endocytic compartments and that conversion can also occur in several intracellular compartments all along the endocytic pathway 34--36 . A minor proportion of PrP C can be found in the cytosol or in contact with the cytosol, due to retrotranslocation from the endoplasmic reticulum (or escape before translocation) or transmembrane anchoring, respectively (for review [START_REF] Miesbauer | Targeting of the prion protein to the cytosol: mechanisms and consequences[END_REF] ). In physiological conditions, these forms are rapidly cleared by quality control processes (ERAD (Endoplasmic-reticulum-associated protein degradation), aggresomes). However, in the prion disease state, or with mutated PrP mimicking familial forms of prion diseases, the levels of cytosolic PrP are increased [START_REF] Miesbauer | Targeting of the prion protein to the cytosol: mechanisms and consequences[END_REF][START_REF] Hegde | Transmissible and genetic prion diseases share a common pathway of neurodegeneration[END_REF] . The exact contribution of these variants to prion pathology remains unknown. PrP C is also involved in many cellular processes and signaling pathways. These processes include response to oxidative stress, ER stress, apoptosis, proliferation and differentiation (reviewed in 39--41 ). Certain stress can even trigger unusual localization of PrP C into the nucleus [START_REF] Bravard | The prion protein is critical for DNA repair and cell survival after genotoxic stress[END_REF] . Late stages of prion pathogenesis involve overactivation of the PERK (protein kinase RNA-like endoplasmic reticulum kinase) pathway of the unfolded protein response in experimental mouse models [START_REF] Smith | The unfolded protein response: mechanisms and therapy of neurodegeneration[END_REF] . Such pathways and the deregulation of the PrP-dependent physiological pathways, or a yet to discover PFAR-dependent proteostatic pathway in mammals [START_REF] Mays | Prion disease tempo determined by host-dependent substrate reduction[END_REF] , provide plenty of scope for direct or indirect interactions with PFAR to occur.

PFAR involvement goes most probably further than prion-based diseases such as Creutzfeldt-Jacob disease. There is indeed growing evidence that amyloid-based diseases like OPMD (Oculopharyngeal muscular dystrophy), Alzheimer's, Parkinson's and Huntington's diseases share key biophysical and biochemical characteristics with prionopathies: they involve accumulation of aggregates of misfolded host-encoded proteins through prion-like processes of seeded polymerisation 45--47 . As metazoa have no Hsp104p ortholog, the protein folding activity of domain V of the ribosome might thus correspond to the Hsp104-like activity responsible for amyloid handling that is absent in these organisms. This original hypothesis makes sense in light of our recent findings that some anti-prion compounds with anti-PFAR activity, like 6AP, GA and IQ, are also active in models of other protein aggregation-based diseases like Huntington's disease, Parkinson's disease (unpublished data) and OPMD [START_REF] Barbezier | Antiprion drugs 6-aminophenanthridine and guanabenz reduce PABPN1 toxicity and aggregation in oculopharyngeal muscular dystrophy[END_REF] . Our data thus indicate that PFAR involvement in amyloid handling may be shared by several human protein misfolding-based diseases, hence making PFAR a potential therapeutic target for human protein misfolding diseases. Despite the central role of PFAR in the proteostasis of the cell, it is still a promising therapeutic target to treat this class of diseases, either as a sole target or as part of a collaborative strategy targeting more than one cellular chaperone system. Indeed, its mild inhibition, together with other therapeutics, may help overcome the progression of these invariably fatal pathologies.

Figure 1 .

 1 Figure 1. The sites of major importance for PFAR activity are included within the PTC

Figure 2 .

 2 Figure 2. Interplay between protein folding activities of Hsp104p and ribosome in modulating [PSI + ] propagation (adapted from 6 ). A -Hsp104p and PFAR both participate in [PSI + ] propagation. B -[PSI + ] propagation is affected by enrichment or inhibition of Hsp104p

Acknowledgements

This work was supported by FA29 and défi organization to CV and MB, Agence Nationale pour la Recherche and Direction Générale de l'Armement (ANR-14-ASTR-0001) and Institut Universitaire de France to RG. We thank E. Giudice for generously helping preparing figure 1.

Conflict of interest

The authors declare no competing financial interests in relation to the work described.


Rémy Muller

Remy Muller

Frederic Bevilacqua

Monique Chiollaz Creatis

Human Motion "Following" system using Hidden Markov Models and application to dance performance

This work presents a movement "following" system based on "Hidden Markov Models" and motion descriptors extracted from video. The primary application is in performing arts such as dance but the methodology is general enough to be applied in other fields as long as appropriate descriptors are available.

Different motion features, segmentations, decoding methods and data analysis such as Principal Components analysis have been performed and compared in order to show how they affect the "following" performances. Both contemporary dance performances and synthetic animations have been used in order to evaluate the system.

Chapter 1 Introduction

Performing arts often require a good synchronization between performers, music, video and lighting. The simplest solution is to ask performers to follow the music and technicians to follow the performers. But when a finelyt timed temporal interaction is required and lots of different events have to be generated in response to what's happening on the stage, the task becomes quickly un manageable, even for teams of skilled professionals. Tradeoffs have to be made in order to make the performance realizable.

We aim at using computer vision an machine-learning techniques to delegate to the computer the task of doing human motion following.

Though machine-learning techniques have been used for a long time in applications such as Robotics, Speech recognition or DNA classification, their use for motion and gesture recognition has been made possible only recently because of the memory capacity requirements and CPU power required by the algorithms. Most of the R&D has been focused on hand-sign recognition [START_REF] Wu | Vision-based gesture recognition: A review[END_REF] and gait characterization [START_REF] Troje | Decomposing biological motion: A framework for analysis and synthesis of human gait patterns[END_REF] for applications such as communication, medical rehabilitation and surveillance.

An overview of Human motion analysis and gesture recognition can be found in [START_REF] Aggarwal | Human motion analysis: A review[END_REF], [START_REF] Gavrila | The visual analysis of human movement: A survey[END_REF] and [START_REF] Turk | Gesture recognition[END_REF] where the common problems such as detection, classification, recognition are exposed as well as the tools commonly used to solve them. One can also note that finite-state machines [START_REF] Hong | Gesture modeling and recognition using finite state machines[END_REF], Markov chains [START_REF] Bowden | Learning statistical models of human motion[END_REF], Hidden Markov Model [START_REF] Bobick | activity, and action: The role of knowledge in the perception of motion[END_REF], [START_REF] Wang | Unsupervised analysis of human gestures[END_REF] or their derivatives [START_REF] Brand | Style machines[END_REF], [START_REF] Ge | Deformable markov model templates for timeseries pattern matching[END_REF] are heavily used to model the temporal dimension of motion or, more generally, time series. The use of these techniques for artistic applications is still emergent. One important tool called Eyesweb [START_REF]Analysis of Expressive Gesture: The EyesWeb Expressive Gesture Processing Library[END_REF] has been made available with the European project IRCAM Tutors: Frederic Bevilacqua, Monique Chiollaz CREATIS MEGA 1 with a strong involvement toward multimodal analysis of expressive gestures [START_REF] Volpe | Computational models of expressive gesture in multimedia systems[END_REF]. It has been very helpful to us for extracting the motion descriptors, since all that we needed was already included in it we were thus able to concentrate on the interpretation.

Meanwhile, Ircam has been involved in "following systems" with "score-following" in the works of Barry Vercoe and Miller Puckette [START_REF] Vercoe | The Synthetic Performer in the Context of Live Performance[END_REF], [START_REF] Vercoe | Synthetic Rehearsal: Training the Synthetic Performer[END_REF], [START_REF] Puckette | EXPLODE: A User Interface for Sequencing and Score Following[END_REF]. It was refactored later on by Nicolas Orio who introduced the use of HMM to perform the "following" [START_REF] Orio | Score following using spectral analysis and hidden markov models[END_REF], [START_REF] Orio | Score following: State of the art and new developments[END_REF], and a master thesis [START_REF] Pellegrini | Suivi de voix parlée grace aux modèles de markov cachés[END_REF] has been done last year to evaluate the possibility to extend it to perform text following in the case of theater applications and to help following singing voice.

The work in this paper is part of a new research project being developed at Ircam dedicated to performing Arts whose scope and goals are described in [START_REF] Bevilacqua | Captation et analyse du mouvement pour l'interaction entre danse et musique[END_REF] and we have focused it particulary to dance performance. It has been realized inside the real-time application team.

The works described in [START_REF] Lee | Gesture classification and recognition using principal component analysis and hmm[END_REF] and [START_REF] Chenevière | Compression and recognition of spatio-temporal sequences from contemporary ballet[END_REF] are technically similar to our work with respect to the methods used but differ from ours since we are more concerned by the following-synchronization problem than the classification of elementary gestures for dance notation and because we wanted our system to be able to work in real-time.

Willing to apply this research to artistic context will always impose us the following constraints:

• The number of available examples used to train our model will always be limited and thus the validity of the statistics hypothesis too.

• We won't be able to use non causal or CPU 2 intensive algorithms such as Viterbi or the forward-backward procedure. Please refer to [START_REF] Rabiner | A tutorial on hidden markov models and selected applications in speech recognition[END_REF] for explanations about these methods.

We will first expose the system we have used to perform the "following" with the definition of the motion descriptors, the definition of the Hidden Markov Model, the segmentation methods and the decodingstrategies. Then we will describe different results related to each of these aspects and we will finally present the future directions that might be explored buikding on this work.

1 Multisensory Expressive Gesture Applications. To evaluate our work, we've also generated dance animations based on motion capture from the Vicon optical motion capture system. The animations were generated in order to have different time-lines.

IRCAM

Tutors: Frederic Bevilacqua, Monique Chiollaz CREATIS

Hypothesis

During all this work, we have supposed that:

• We have a 3D motion projected on a 2D surface

• the camera is fixed and the focal plan does not change

• the lighting is constant

• there is a single single dancer in the scene

• the only motion is the human one over a constant background

• the size of the character is comparable with the one of the image.

Motion features

A 300x200 RGB image would represent 180000 parameters/dimensions per frame. Using a dimension reduction technique such as PCA directly on the sequence of images would have been very interesting, but we couldn't try it because of memory limitations. It was thus mandatory upon us to choose a restricted number of parameters to represent the motion occurring in the image and leave the information concerning the rest of the image.

I'll present here the set of motion descriptors we have used during this work that were all provided by Eyesweb [START_REF]Analysis of Expressive Gesture: The EyesWeb Expressive Gesture Processing Library[END_REF] image processing and analysis software.

The blob analysis uses the silhouette which is a binary image divided into background (black 0) and silhouette (white 1). This is the most simple way of computing it.

S k = threshold(Image k -Background) (2.1)
It's also possible to use a better estimate as defined in [START_REF] Volpe | Computational models of expressive gesture in multimedia systems[END_REF]

S k = threshold(Image k -Background, Background) (2.2)
Where the threshold function uses the histogram of the background.

In the case of a changing background, it would still be possible to update the background with an adaptive low-pass filter or have a more sophisticated and robust segmentation. but this is out of the scope of this work.

IRCAM

Tutors: Frederic Bevilacqua, Monique Chiollaz CREATIS

Skeleton

This is a particular aspect of blob analysis. Eyesweb has a module trying to match a face human skeleton to the image silhouette by dividing the blob in multiple areas and computing the centroid of each area. It gives the following data:

• Bounding rectangle x,y,width,height

• Head x,y

• Center of gravity x,y

• Left-Right Hand x,y

• Left-Right elbow x,y

• Left-Right shoulder x,y

• Left-Right knee x,y

• Left-Right foot x,y

Image moments

Another way of characterizing the silhouette, is to use moments.

Cartesian spatial moments

The first that can be considered are the cartesian moments:

m pq = M x=1 N y=1
x p y q I(x, y)

Eyesweb only provides moments m 00 , m 01 , . . . , m 30 , m 03 . One can note that m 00 gives the surface of the blob, m 01 and m 10 gives its centroid. And m 22 , m 11 and m 02 gives its variance and its orientation.

Normalized moments

they are scale invariant.

IRCAM

Tutors: Frederic Bevilacqua, Monique Chiollaz CREATIS

ν pq = m pq m γ 00 γ = p + q 2 + 1 ∀p, q ≥ 2 (2.4)
Eyesweb only provides ν 00 , ν 01 , . . . , ν 30 , ν 03

Central cartesian moments

µ pq = M x=1 N y=1 (x -x) p (y -y) q I(x, y) (2.5)
This is a variant which is translation invariant. Eyesweb only provides moments µ 00 , µ 01 , . . . , µ 30 , µ 03

Normalized central moments

η pq = µ pq µ γ 00 γ = p + q 2 + 1 ∀p, q ≥ 2 (2.6)
These moments are scale and translation invariant.

Hu moments

I 1 = η 20 + η 02 I 2 = (η 20 -η 02 ) 2 + 4η 2 11 I 3 = (η 30 -3η 12 ) 2 + (3η 21 -η 03 ) 2 I 4 = (η 30 + η 12 ) 2 + (η 21 + η 03 ) 2 I 5 = (η 30 -3η 12 )(η 30 + η 12 ) (η 30 + η 12 ) 2 + 3(η 21 + η 03 ) 2 +(3η 21 -η 03 )(η 21 + η 03 ) 3(η 30 + η 12 ) 2 -(η 21 + η 03 ) 2 I 6 = (η 20 -η 02 ) (η 30 + η 12 ) 2 -(η 21 + η 03 ) 2 +4η 11 (η 30 + η 12 )(η 21 + η 03 ) I 7 = (3η 21 -η 03 )(η 30 + η 12 ) (η 30 + η 12 ) 2 + 3(η 21 + η 03 ) 2 +(η 30 -3η 12 )(η 21 + η 03 ) 3(η 30 + η 12 ) 2 -(η 21 + η 03 ) 2
These moments have the good property (if required by the application) to be scale, translation and rotation invariant and to be orthogonal.

So far, we have described instantaneous motion descriptors but there are many systems using accumulation of images over a time window to recognize gestures [START_REF] Bradski | Motion segmentation and pose recognition with motion history gradients[END_REF] [5]. However we have decided no to show them because they introduce a delay in the "following" system. It's important to keep in mind that 1 frame at a rate of 25 images per second represents 40 milliseconds which is already audibly noticeable, especially if rhythmic musical events have to be synchronized with the dance.

IRCAM

Tutors: Frederic Bevilacqua, Monique Chiollaz CREATIS

Principal Components Analysis

Most of the features we use are correlated and can be affected by different kinds of perturbations due to variations in the lighting conditions, DV compression and bad silhouette segmentation. We want to evaluate the advantage of using a Principal Components Analysis decomposition both as a dimension reduction technique and as a perturbation reduction tool (supposing that the perturbation's variance is low compared to the variance of the signal). It can also be a powerfull method of visualising the distribution of the data set in the two or three most significant components of the features-space. Please refer to [START_REF] Turk | A random walk trough eigenspace[END_REF] for more information on Principal Components Analysis.

If we have a sequence of parameters {P t } that we can represent by a matrix P where P t is a vector of parameters.

P = [P 1 P 2 . . . P T ] (2.7)
P is of dimension N × T and N is the number of parameters.

To perform PCA, we deduce the mean of the data set for each parameter in order to have centered data.

P = P -P P =    p1 . . . pN   
then we search a reduced set of R orthogonal vectors e i which will best describe the data set in a least-squares sense, i.e. the Euclidian projection of the error is minimized. The common method of computing the principal components is to find the eigenvectors of the covariance matrix C of size N × N such that:

C = P P T (2.8)
and

Ce i = λ i e i (2.9)
It can be done using a singular value decomposition. Then the last step consists to keep the R eigenvectors that have the highest eigenvalues λ i . We can then project our original sequence in the eigensubspace.

P = U T P, U = [e i . . . e R ] (2.10)
We then have the sequence {P t } that we can use as the observations of our "following" system instead of directly using the parameters given by the video analysis.

IRCAM Tutors: Frederic Bevilacqua, Monique Chiollaz CREATIS

We have also considered using Kernel PCA [START_REF] Bengio | Spectral clustering and kernel pca are learning eigenfunctions[END_REF] because it can handle inherent nonlinear variation of the data set and transform it to a linear variation thus making the separation of the classes easier with linear tools, but time was short to do it.

Hidden Markov Model

Hidden Markov Models are probabilistic finite-state automatas, where transitions between states are ruled by probability functions. At each transitions, the new state emits a value with a given probability. Emmissions can be both symbols from a finite alphabet and continuous multidimensional values. In markovian process, transition probabilities are assumed to depend only on a finite number of previous transitions (usually one) and they may be modeled as a Markov chain. The presence of transition with probability equal to zero defines the topology of the model, limiting the number of possible paths. For more in formation on HMM see [START_REF] Rabiner | A tutorial on hidden markov models and selected applications in speech recognition[END_REF]. The graph can be represented by the following transition matrix:

Structure

IRCAM Tutors: Frederic Bevilacqua, Monique Chiollaz CREATIS A =        a 11 a 12 a 22 a 23 . . . . . . a N -1N -1 a N -1N a N N       
With a ij being the probability of going from state i to state j and N the number of states.

a ij = P (q t+1 = S j |q t = S i ) 1 ≤ i, j ≤ N (2.11)
It implicitly models the probability of staying a time t in a given state as an exponential distribution.

p i (d) = (a ii ) d-1 (1 -a ii ) (2.12)
with d being the duration in state i. But we could extend it as in [START_REF] Rabiner | A tutorial on hidden markov models and selected applications in speech recognition[END_REF], [START_REF] Orio | Score following using spectral analysis and hidden markov models[END_REF], [START_REF] Orio | Score following: State of the art and new developments[END_REF] and [START_REF] Pellegrini | Suivi de voix parlée grace aux modèles de markov cachés[END_REF] to multiple states giving more degrees of freedom to model the duration or/and refine the segmentation in subsegments.

Observations

In our model, each state of the model emits a vector of continuous observations per video frame.

O = {o 1 , o 2 . . . , o M } (2.13)
with M being the number of observations per state. The state is characterized by its probability distribution.

b j (O) = ϕ[O, µ j , U j ] 1 ≤ j ≤ N (2.14)
with mean vector µ j and the covariance matrix U j in state j and ϕ being logconcave to ensure the convergence of the re-estimation procedures.

We then have a model λ = [A, B, π] of our dance with B = {b j } and π being the initial state probability distribution.

These observations can be any set taken among the motion features exposed before and we will compare their respective advantages and drawbacks in the next chapter.

Temporal segmentation

Once we have one or several executions of a dance, in order to build a HMM, we have to divide it into several segments that can be associated to states of the HMM. Since we've used a simple left-right model, there is a one-to-one mapping between a segment and a state.

Manual

Most of the temporal segmentation of the dances in this work has been done manually either by looking at some key gestures-postures in the dances, or by looking at the parameters extracted from the video in order to create states well localized in the feature-space.

In the case of the synthetic dances, as we had the information relative to the footsteps for all the variations, we have used them as the markers for the segmentation. Therefore we were able to compare the same segments across the different animations with no error introduced by a bad segmentation.

IRCAM Tutors: Frederic Bevilacqua, Monique Chiollaz CREATIS

Automatic

When drawn in the feature-space, the point distributions generated by the dances seemed hard to cluster using an algorithm such as K-means. They would be better viewed as trajectories with local change of direction.

Therefore we have used a criterion δ based on the directness of the trajectory as defined by Volpe [START_REF] Volpe | Computational models of expressive gesture in multimedia systems[END_REF]. i.e. the ratio between the direct path between the 2 extreme points and the trajectory path.

δ t = P t+N -P t-N 2 t+N -1 i=t-N P i+1 -P i 2 (2.15)
and used the local minima of the directness as markers.

Initialization

Once we have a segmentation for all the dances, we are able to compute the mean vector and the covariance matrix for each state and then model the probability density function per state.

We have used gaussian distributions, but it might be improved since the experimental distribution we have are far from being gaussian, but rather look like trajectories segments in the feature space.

We are also able to compute the mean duration for each state and then create the transition matrix using the following equation.

di = ∞ d=1 dp i (d) = ∞ d=1 d(a ii ) d-1 (1 -a ii ) = 1 1 -a ii (2.16)

"Following"

As for the score-following, we wanted our system to be implemented in real-time thus we have only used the forward procedure which has the advantage of being causal and can be implemented iteratively.

α t (i) = P (O 1 O 2 . . . O t , q t = S i |λ) (2.
(i) = π i b i (O 1 ) 1 ≤ i ≤ N (2.18) α t+1 (j) = N i=1 α t (j)a ij b j (O t+1 ), 1 ≤ t ≤ T -1, 1 ≤ j ≤ N (2.19)
If we follow this procedure we can then compute the probability of the observation sequence until time t given the model:

P (O 1 O 2 . . . O t |λ) = N i=1 α t (i) (2.20)
And if we scale the α i such that

αt (i) = α t (i) P (O 1 O 2 . . . O t |λ) (2.21)
we then have for each t the state distribution probability.

αt (i) = P (q t = S i |O 1 O 2 . . . O t , λ) (2.22)
Now that we are able to have the state distribution for each time instant t, we have to take a decision about the state that we consider the most likely for each t, that is called decoding. We have used two strategies that are described hereunder and will be compared in the next chapter.

Max decoding

In the max decoding, we simply select the most probable state qt so that:

qt = arg max{α t (i)} i (2.23)
and we can use max{α t (i)} as the quality of the estimation.

Barycenter decoding

It is also possible to use the barycenter of {α t (i)}:

qt = 1 N N i=1 iα t (i) (2.24)
IRCAM Tutors: Frederic Bevilacqua, Monique Chiollaz CREATIS which has a smoother behaviour when there is uncertainty among different states.

It would be possible to use other strategies using prior knowledge and restrictions on the possible paths but we've restricted ourselves to these two methods.

In artistic applications, the decoding step could be left to the final application to better adapt to the context.

It's important to note that using the forward procedure, the decoded path can be non-optimal with respect to the path that would be decoded offline by the viterbi algorithm. It can even not be allowed by the HMMs topology.

IRCAM Tutors: Frederic Bevilacqua, Monique Chiollaz CREATIS Chapter 3

Results

In order to clarify the results that are going to be exposed in this chapter, I will define the different measures of error we have used and explain their advantages and drawbacks.

First we have used the mean rms error :

mre mre = 1 T N T t=1 (q t -q t ) 2 (3.1)
and the mean absolute error :

mae mae = 1 T N T t=1 |q t -q t | (3.2)
They both give an average measure of the how much the recognized path differs from the original one.

We have also used the max error :

me me = max |q t -q t | N (3.3)
It gives an idea about what the worse case error can be, which is of extreme importance in live performance.

Since these three errors are normalized by the number of states N they should be treated with care when comparing segmentations with different number of states.

And finally, we have used the mean binary error : mbe

IRCAM Tutors: Frederic Bevilacqua, Monique Chiollaz CREATIS mbe = 1 T T t=1 qt -q t (3.4) with x = 1 if |x| ≥ 0.5 0 otherwise
We could have called it the coincidence rate instead, it gives an idea of how much the recognized path coincides with the original one. It is very sensitive because of the binary threshold and is only useful when the two paths are very close to each other. Otherwise the it quickly becomes very high. For example a perfect recognition associated with a constant delay would lead to a very bad results.

IRCAM

Tutors: Frederic Bevilacqua, Monique Chiollaz CREATIS Though we have tried many kinds of parameters during this work, we have mainly used the skeleton parameters and image moments. We will compare here the skeleton parameters with the Normalized Moments taken on the silhouette image that we will shorten to SNM. We could use the Hu moments or the cartesian moments but the results are quite similar and we won't expose them here because of space. We have used HMM trained on the four examples to follow each example individually and have averaged the results to give a global mark to the feature.

Features

We can see on figure 3.1 that the skeleton gives significantly better results than the SNM for the different kind of errors. That can be explained by the fact that:

• The SNM only goes until order 3, which only conveys low spatial frequency information whereas the skeleton is a kind of multi-resolution description of the silhouette and thus catches more of its spatial frequency contents.

• We have 22 parameters for the skeleton and only 9 for the SNM. If we consider that each parameter brings the same amount of informationwhich is not the case since they are correlated -the skeleton has more chance to give us a discriminant description.

In the rest of the results exposed in this paragraph, we have used either the SNM, the skeleton or both depending on what we wanted to highlight.

Learning

In this chapter, we have tried to evaluate the effect of learning on the "following" performances independently of similarities and dissimilarities between the different examples, we have computed all the possible couples (L, R) where L is the set of examples used for the learning step and R is the set of examples being recognized. For example when learning on 3 examples we have the following possibilities: ({1, 2, 3}, {1, 2, 3, 4}), ({1, 2, 4}, {1, 2, 3, 4}) and ({2, 3, 4}, {1, 2, 3, 4}). Then all the results have been averaged in order to a have a unique error for each learning situation 1 . For figure 3.2 we have used the skeleton parameters on the set of real dances videos.

On the figure 3.2 we can see that the different errors are very high (about 76% for the me!) when the learning is only performed on one example. In fact the model is under-trained, and is totally unable to recognize the other examples 2 . Then the errors quickly fall very low (5.55% for the me and 1.04% for the mbe) giving very 2 In some cases, the α t (i) are so low that they exceed the machine's precision range.

IRCAM

Tutors: Frederic Bevilacqua, Monique Chiollaz CREATIS Note that when learning on three examples and recognizing the remaining one which is the situation we would meet in live performances but that we will not show due to space restriction, the results are slightly lower (between 5% and 15% for the mbe) than when the example belongs to the training set but it is still very usable. However, when the learning is performed on only 2 examples and following an example that is not in the training set, the results are very bad (60% for the mbe) and the error is maximum when the dancers are different.

IRCAM

Tutors: Frederic Bevilacqua, Monique Chiollaz CREATIS We wanted to evaluate how the decoding strategy affects the recognition performance. Optimizing the decoding strategy improves the overall recognition rate. This becomes particularly apparent when using a suboptimal set of features such as the SNM taken on the silhouette, as shown in figure 3.3. We used both the real dances and the animations and only used tests where HMMs where trained with the four examples.

Decoding

We can see in table 3.3 that the barycenter method has lower mre, me and mbe than the max method. The difference is particulary striking with the mbe. However the mae is in favour of the max method. Since the mre penalizes the distance to the original path more than the mae it means that the barycenter method stays closer to the original path.

In the rest of this document, if not mentioned explicitely, the decoding method will always be the barycenter.

IRCAM

Tutors: Frederic We wanted to know how the use of PCA as a preprocessing step would help improve following results and reduce the number of parameters required to perform the computation.

We have used both tests with HMMs being trained with an example and following the same example and tests with HMMs being trained with the four different examples and following these four examples successively. Then the respective errors have been averaged for each dimension in order to give a global result.

We can see in figures 3.4 and 3.4 -as we would have expected -that the errors decrease almost monotonously with the number of dimensions in both animations and real dances. We can also note that there is no real benefit in using more than about eight parameters for the real dances and twelve for the animations, when the original number of parameter for the skeleton is 22. It is easily explained by the fact that most of the skeleton parameters are correlated as it can be seen in figure 2.5.2.

We can also note that in the case of the real dances, which were subject to different kinds of perturbations because of the lighting condition, the DV compression and the silhouette segmentation step, the PCA does not help improve the results. There is no minimum in the error curves for which the perturbations would have been removed while keeping the useful signal.

IRCAM

Tutors: Frederic Bevilacqua, Monique Chiollaz CREATIS

Segmentation

We wanted to evaluate the influence of the segmentation method on "following". Because we couldn't have an automatic segmentation having the same meaning across different dances, we have only used HMMs trained on one example and recognizing the same example. This way we should have the best possible results (since the model is fitted to this example) and only evaluate the influence of the segmentation method.

We have also taken care of the number of states in each segmentation so that they either match or are similar in order to be able to compare the errors.

Animations

For the animations, we already had a kind of manual segmentation given by the footsteps of the character, that had been used to generate the animation. Furthermore, their use can be justified by the fact that they are associated to well defined instants of the movement and can be considered as a "natural" segmentation.

In table 3.5 and figure 3.5 we can see that the error rates are significantly lower when using the footsteps to segment the animation, than when using an automatic segmentation. This shows that the footsteps allows for an effective segmentation IRCAM Tutors: Frederic Bevilacqua, Monique Chiollaz CREATIS

Videos

For the videos, the manual segmentation was made by searching some key instants and postures simultaneously in the different examples, and the automatic segmentation was still made using the the curvature of the trajectory in the feature space.

In table 3.5 and figure 3.5 we can see that in this case the automatic segmentation has better results. It is easily explained by the fact that automatic segmentation is designed to have each state associated to -as much as possible-non overlapping regions of the feature space.

IRCAM Tutors: Frederic Bevilacqua, Monique Chiollaz CREATIS 3.3: segmentation evaluation on real data Furthermore, in this experiment we have forced the automatic segmentation to use the same number of states as the manual one in order to compare them equally. But the natural number of states given by the automatic segmentation was originally about twice the number of states given by the manual one. It means that the manual segmentation is under-specified with respect to the data set.

It would be interesting to investigate a mixed multilevel segmentation with the top layer being defined manually by the choreographer with respect to some key instants in the dance -the ones to be retrieved with precision -and let the system define automatically a finer grained structure inside those states in order to ease the following task.

IRCAM Tutors: Frederic Bevilacqua, Monique Chiollaz CREATIS basis depending on the application, in order to achieve optimal results. IRCAM Tutors: Frederic Bevilacqua, Monique Chiollaz CREATIS

Chapter 2 Methodology 2 . 1

 221 Video MaterialWe have used short 1 dances videos with a 300x200 resolution. These were gathered from choreographer Hervé Robbe and were recorded at the Centre National de Dance du Havre with DV cameras. Each dance has been performed twice by two different dancers, which gives us 4 different examples per dance.

Figure 2 . 1 :Figure 2 . 2 :

 2122 Figure 2.1: snapshots from one of the video dances

Figure 2 . 3 :

 23 Figure 2.3: blob centroids used to compute the skeleton

Figure 2 . 4 :

 24 Figure 2.4: skeleton on a real silhouette

Figure 2 . 5 :

 25 Figure 2.5: left-right HMM

Figure 2 . 6 :

 26 Figure 2.6: skeleton parameters for a dance

Figure 3 . 1 :

 31 Figure 3.1: moments vs skeleton

  Figure 3.2: learning

1 1

 1 example, 2 examples, 3 examples and 4 examples.

Figure 3

 3 Figure 3.3: learning

  Figure 3.4: decoding evaluation

Figure 3 . 5 :Figure 3 . 6 :

 3536 Figure 3.5: trajectories of each video dance projected on the 2 first principal components of the 4 dances data set

Figure 3 . 7 :

 37 Figure 3.7: pca dimension reduction effect on error, real data

Figure 3 . 8 :

 38 Figure 3.8: segmentation evaluation on animation data

  Figure 3.9: segmentation evaluation on real data

  [START_REF] Puckette | EXPLODE: A User Interface for Sequencing and Score Following[END_REF] i.e. the probability of the partial observation sequence O 1 O 2 . . . O t and state S i at time t given the model λ

		α 1
	It can be computed using the following equations:
	IRCAM	Tutors: Frederic Bevilacqua, Monique Chiollaz	CREATIS

Chapter 4

Summary and conclusion

We have presented a general "following" system applied to dance with which we had rather good experimental results on both animations and videos of real dances, using the skeleton features. Our methodology has thus being validated which can let us suppose that it might be transposed successfully in other fields.

We have shown that the system can be exposed to under-learning when there are too few examples, but also that it can converges quickly on good results, even with only 4 examples. This suggests that when there is no possibility of collecting several examples we should find a way to give the system more tolerance. This could be realized by using a variance estimator with its interval of confidence instead of a direct computation.

We have also shown that altough Principal Component Analysis is not required to have good results, it could help reduce the number of required dimensions. As the eigenvectors of the covariance matrix can be pre-computed before launching the "following", it could help reduce the CPU cost of the decoding at the expense of a preprocessing computation. Again, this would need to be investigated in detail.

Though the automatic segmentation of the data which has been used may be better than the manual one, the manual segmentation has nevertheless proven to be effective both for animations and for real dances and to allow easy and accurate training on several examples. Different kinds of automatic segmentation should also be investigated. We could imagine using the HMM as in [START_REF] Raphael | Automatic segmentation of acoustic music signals using hidden markov models[END_REF] to perform the segmentation.

We have also proved that the barycenter decoding resulted in smoother paths than the max decoding in the presence of ambiguities among different states. This is a better choice in the case of live performance because we did not wanted our system to move back and forth between different states. We should recommend that the decoding strategy should be choosen or designed on a case by case IRCAM Tutors: Frederic Bevilacqua, Monique Chiollaz CREATIS


Edouard Ribes
email: edouard.augustin.ribes@gmail.com

Karim Touahri
email: touahrikarim91@gmail.com

Benoît Perthame

Employee turnover prediction and retention policies design: a case study

Keywords: 2010 Mathematics Subject Classification. Keywords and phrases. Churn prediction, Machine learning techniques, Employee Turnover, Classification, Retention Policy, Workforce Planning

This paper illustrates the similarities between the problems of customer churn and employee turnover. An example of employee turnover prediction model leveraging classical machine learning techniques is developed. Model outputs are then discussed to design & test employee retention policies. This type of retention discussion is, to our knowledge, innovative and constitutes the main value of this paper.

Introduction

Machine learning algorithms are often showcased in customer churn study. Applications in fields such as telecommunication or product marketing (gaming, insurance etc..)(see [START_REF] Ngai | Application of data mining techniques in customer relationship management: A literature review and classification[END_REF], [START_REF] Vafeiadis | A comparison of machine learning techniques for customer churn prediction[END_REF] for a recent review) are multiple. The implementation of these methods in Customer Relationship Management is becoming the new norm, as improving customer retention yields superior business results. We argue that this type of techniques can easily be applied to employee turnover. Note that the employee turnover can actually be subdivided in 3 buckets: involuntary turnover (induced by the company), voluntary turnover (employee resignation) and retirements. Retirement and an involuntary turnover are out of the scope of this paper. Retirement is indeed generally legally enforced through specific local schemes and does not require a prediction. As for firing decisions, they are a company decision aiming at achieving the right workforce sizing or productivity levels. Therefore they do not require any anticipation on workers behavior. On the other hand, voluntary turnover is employee dependent. Mitigating it can be of interest to companies. This is even, in our opinion, one of the key workforce dynamic to understand in order to manage a company in a sustainable fashion (see [START_REF] Doumic | Toward an integrated workforce planning framework using structured equations[END_REF] for example). Assume that a company Y has a portion of its workforce in job j that is deemed critical to achieve business results. Assume the job j participates in a critical part of a product manufacturing process and is extremely difficult to source because of the required expertise and associated training time.

Delays and/or failure in the manufacturing process can be extremely costly for the company, so that retention efforts may have to be considered to mitigate production risks. Retention is part of the standard Human Resources [HR] activity which is structured around the "5 Bs", namely : "Buy" and "Borrow"(=hire), "Build"(=train), "Bind"(=retain), "Bounce"(=fire). Retention investments usually factor individual performance, potential to grow in a company and are conjugated with a leave risk assessment. Let's assume that performance and potential are already assessed in a satisfactory fashion but that the leave risk is currently assessed by the employee's manager based on personal intuition. This managerial assessment is in reality a classification problem. The manager will indeed flag each year its employees has having either a "High Risk" (the employee will leave the company this year) or a "Low Risk" (the employee will not leave the company this year) of departure. Assume that the company Y does not trust the managerial assessments because historically, they poorly correlate to the observed voluntary turnover fluxes. The company would therefore be interested in developing a prediction routine to structure its retention efforts. The use of machine learning techniques for turnover prediction purposes has risen lately (see [START_REF] Punnoose | Prediction of employee turnover in organizations using machine learning algorithms[END_REF] and [START_REF] Chang | Employee turnover: a novel prediction solution with effective feature selection[END_REF] for recent examples). Yet, to our knowledge, nothing has been done to design and test retention policies. In this paper, we will therefore leverage HR domain knowledge to build a turnover predictor and test retention policies. This paper will first explain how features can be engineered to feed a machine learning algorithm. In a second part, several machine learning methods and training sample techniques will be discussed and analyzed in terms of performance. Finally a sensitivity analysis will be carried out to design and test specific retention policies. Important Legal Remark. The findings and opinions expressed in this paper are those of the authors and do not reflect the positions from any company or institution. Finally, please bear in mind that for confidentiality reasons numbers have been disguised in a way that preserves the same conclusions as the actual case study.

2 Feature Engineering.

Previous Work.

Turnover is not easy to predict because it results from a combination of elements. So far, no consensus has been reached in terms of key elements to use. For example, an early review of voluntary turnover studies [START_REF] Cotton | Employee turnover: A meta-analysis and review with implications for research[END_REF] has found that the strongest predictors for voluntary turnover were age, tenure, pay, overall job satisfaction, and employees perception of fairness. But other studies have also stressed the importance of job performance [START_REF] Susskind | Customer service employees' behavioral intentions and attitudes: An examination of construct validity and a path model[END_REF], job characteristics (role, seniority in role...) [START_REF] Hasan Zarei Matin | Do demographic variables moderate the relationship between job burnout and its consequences?[END_REF], enhanced individual demographic characteristics (age/experience, gender, ethnicity, education, marital status) ([9], [START_REF] Finkelstein | What do the young (old) people think of me? content and accuracy of age-based metastereotypes[END_REF], [START_REF] Holtom | Turnover and retention research: A glance at the past, a closer review of the present, and a venture into the future[END_REF], [START_REF] Hippel | Stereotype threat among older employees: Relationship with job attitudes and turnover intentions[END_REF], [START_REF] Peterson | Toward a theoretical model of employee turnover: A human resource development perspective[END_REF], [START_REF] Sacco | A dynamic multilevel model of demographic diversity and misfit effects[END_REF]), structural characteristics (i.e. team size and performance) and geographical factors ( [START_REF] Tanova | Using Job Embeddedness Factors to Explain Voluntary Turnover in Five European Countries[END_REF] , [START_REF] Carraher | Turnover prediction using attitudes towards benefits, pay, and pay satisfaction among employees and entrepreneurs in estonia, latvia, and lithuania[END_REF]).Finally some studies have also set an emphasis on salary, working conditions, job satisfaction, supervision, advancement, recognition, growth potential, burnout etc. [START_REF] Allen | Test of a mediated performance turnover relationship highlighting the moderating roles of visibility and reward contingency[END_REF], [START_REF] Liu | When employees are out of step with coworkers: How job satisfaction trajectory and dispersion influence individual-and unit-level voluntary turnover[END_REF], [START_REF] Swider | Born to burnout: A metaanalytic path model of personality, job burnout, and work outcomes[END_REF], [START_REF] Heckert | Turnover intentions of the faculty at a teaching-focused university[END_REF]. And our list is far from being exhaustive... To our understanding, the key to successfully engineer features in machine learning exercises revolves around flexibility. Companies Human Resource Information Systems [HRIS] are famous for data inconsistency and quality issues. The absence of data standards thus calls for company specific engineering tasks.

Turnover Domain Knowledege & Data.

The dataset available for this study was discussed with a pool of peer-trusted experts among our clients group. The purpose of this discussion was to hand pick features that, in light of the previous bibliographical work, would be relevant for the given job j and in the current historical context. Leveraging peer trusted experts was important because it enabled us to infuse domain knowledge to the project while creating buy-in in our client group for this kind of methodology. This was also critical as it helped us remove features that were considered non reliable. The selected features were:

• Localization. Individuals from a given country were selected. This country was described by a categorical feature representing the regional area where the employee was working. This was used to account for local labor market specific dynamics.

• Knowledge. In order to account for specific domain expertise among job category j, the type of business unit in which the individual was working was added to the feature mix.

• Individual data. Several features were suggested as far as individuals are concerned. First, time in the current position and tenure with a given company were added. Demographics in terms of age and gender were also highlighted. Additional elements specific to the dataset, such as performance & potential evaluation, were discussed. Hierarchical level according the dataset grading structure was finally added to the mix.

• Individual managerial data. Managers demographic information such as age and gender were added, as well as managers time in the current position and tenure in a given company. Manager's performance over the last year and average performance over the last 3 years were also integrated.

• Individual team data. Team size and team percentage of high and low performers were added to the prepared mix.

The population under study in the given job category j accounted for about 1000 employees in a given country. 2 years (referred to as year 1 and year 2) of data were available. The problem was of a classification nature as employees were either tagged as "Terminated" or "Active". Note that the dataset was curated of individuals who left involuntarily or because of retirement to respect the scope of the study. The full dataset was heavily unbalanced as the yearly number of people in job j leaving voluntarily was about 20%.It was randomly split in a training and a test set, which were of equal size. Each of the two sets contained the same proportion of year 1 and year 2 information. This choice indeed yielded more robust performances than having the algorithms trained on one year and tested on the other.

Feature Selection.

After this pre-processing, a selection layer was deployed in order to keep only the most relevant elements to the current problem out of the ones mentioned by the experts and the literature. Limiting the number of features used in machine learning problems is indeed crucial to properly manage the complexity of the learning phase and to avoid over fitting. In this paper, the mutual information (MI) criterion was used to assess the information content of each individual feature. This type of feature selection method is indeed well acknowledged and has proven useful for such topics (see [START_REF] Battiti | Using mutual information for selecting features in supervised neural net learning[END_REF] for an early example, [START_REF] Moldovan | Opinion leadership in small groups[END_REF] for a customer churn example and [START_REF] Vergara | A review of feature selection methods based on mutual information[END_REF] for a review.).

Ranking with Mutual Information (MI). Mutual Information (MI) is an essential metric of information and has been widely used for quantifying the mutual dependence of random variables (see [START_REF] Cover | Elements of Information Theory[END_REF] for details).Formally the MI between an output variable Y and an input variable X is defined as:

M I(X; Y ) = x∈X y∈Y
P (x, y). log P (x, y) P (x).P (y) [START_REF] Ngai | Application of data mining techniques in customer relationship management: A literature review and classification[END_REF] where P (x) (resp. P (y)) is the probability associated to X (resp. Y ), and P (x, y) is the joint probability of having both X and Y .

Features Filtering. Several possibilities exist in order to select features. According to a recent survey [START_REF] Chandrashekar | A survey on feature selection methods[END_REF], they can be summed up in three types of methods: filters, wrappers and embedded ones.

Filter methods preprocess and rank features in order to keep only the best ones. In wrapper methods, the feature selection criterion is the performance of the predictor itself. The predictor is indeed wrapped on a search algorithm which will find a subset that gives the best predictor performance. Finally embedded methods include variable selection as part of the training process without splitting the data into training and testing sets.

Fig 1. Features Mutual Information

In this case, a filter method was used based on the previously described mutual information criterion. This choice was motivated by its simplicity and the empirical efficiency of the approach. For each feature X, the mutual information M I(X, Y ) was compiled and only the top 60% features were kept. Mutual information results are displayed below. Among the features of demographic nature, employee's gender and age as well as manager's gender were removed. Company bonus level information and structural hierarchical details proved useful but required granularity to be of use. Team size information disappeared. It is interesting to see that with the current dataset; only employee behavioral assessments relates to the turnover decision. Further investigation would be needed on this aspect of the dataset.

3 Machine Learning Methods.

The analytical techniques deployed rely on well-known standards such as SVM, random forests or KNN that have been proposed to predict turnover (see [START_REF] Esmaieeli Sikaroudi | A data mining approach to employee turnover prediction (case study: Arak automotive parts manufacturing)[END_REF] or [START_REF] Punnoose | Prediction of employee turnover in organizations using machine learning algorithms[END_REF] for examples). They have been adjusted to account for class imbalance and potential associated biases.

Class Imbalance Correction.

Class Imbalance is a common theme on customer churn prediction ( [START_REF] Bowyer | SMOTE: synthetic minority over-sampling technique[END_REF], [START_REF] Amin | A Comparison of Two Oversampling Techniques (SMOTE vs MTDF) for Handling Class Imbalance Problem: A Case Study of Customer Churn Prediction[END_REF]...), which is a topic similar to the one developed in this paper. Standard solutions involve subsampling techniques to smooth the disparities between the observed classes. In this paper, several methods were tested:

• Down-sampling: sample the majority class to make its frequency closer to the rarest class.

• Up-sampling: resample the minority class to increase its frequency.

• Weighting: place a heavier penalty on misclassifying the minority class [START_REF] Chen | Using random forests to learn imbalanced data[END_REF] by assigning a weight to each class, with the minority class being given a larger weight (i.e., higher misclassification cost).

• "SMOTE": over-sample the minority (rarest) class and under-sample the majority class ( [START_REF] Chawla | Smote: Synthetic minority over-sampling technique[END_REF]).

• "ROSE": generate new artificial data from the classes to correct class imbalance according to a smoothed bootstrap approach [START_REF] Menardi | Training and assessing classification rules with imbalanced data[END_REF].

Selected Classification Methods.

The classification problem was approached with the following techniques:

• Naive Bayes (NB) classifiers (see [START_REF] Xia | Model of customer churn prediction on support vector machine[END_REF] for an application) calculate the probability that a given input sample belongs to a certain class. Assuming a number of classes Y = (y1, y2, , yk) and a given a unknown sample X, a Naive Bayes classifier assigns the sample X to the class with the highest probability C = ArgM ax y∈(y1...yk) (p(y|X))

• Linear Discriminant Analysis (LDA) is a generalization of Fisher's linear discriminant analysis.

It can be explained as computing a z-score, which is then used to estimate the probabilities that a particular member or observation belongs to a class.

• Support vector machines (SVMs) achieve class separation by finding (in their linear version) a hyper plane in a high dimensional space. The intuition is that a good separation is achieved by the hyper plane that has the largest distance to the nearest training data points of any class. The larger the margin is, the lower the generalization error of the classifier. For this reason, SVMs are also referred to as maximum margin classifiers. Multiple versions exists (linear, polynomials, gaussian...) (see [START_REF] B-Gent | Churn prediction in subscription services: an application of support vector machines while comparing two parameter-selection techniques[END_REF])

• Random Forests (RFs) [START_REF] Liaw | Classification and regression by random forest[END_REF] result from the combination of tree classifiers. Each tree depends in the values of a random vector sampled independently and with the same distribution for all trees in the forest. The generalization error of a forest of tree classifiers depends on the strength of the individual trees in the forest and the correlation between them. RF has empirically achieved very good classification performance in numerous cases and is robust against over-fitting.

Note that the R Caret package [START_REF] From | caret: Classification and Regression Training[END_REF] was the library used to support the study.

Evaluation & Results.

Cross-Validation. The dataset was split 80:20 into training and hold out sets in a 10-fold cross validation scheme. For each algorithm, a grid-search was performed over the tuning parameters, including regularization or penalty hyper-parameters.

Performance Metric. The Area under the receiver operating characteristic curve (ROC-AUC) was the chosen performance measure. The AUC is a general measure of accuracy. It decouples classifier assessment from operating conditions i.e., class distributions and misclassification costs [START_REF] Lessmann | A reference model for customer-centric data mining with support vector machines[END_REF]. It is better suited to non-balanced classification problems than standard accuracy or error test as it allows a graphical representation of specificity (false positive rate) and selectivity (true positive rate) of the classifiers on the dataset. Note that, in this case, the specificity can be interpreted as the percentage of workers flagged as leavers that really left, while the selectivity represents the percentage of workers appropriately flagged that stayed in their company.

Results. We obtained the following results:

In terms of imbalance correction, we found that up sampling and ROSE sampling yielded the best performance in this case. As expected, when imbalance was not corrected, algorithms tended to favor the majority class to achieve the best performances. As far as the variables of importance are concerned, we saw that the employee behavior and performance (especially when rated low) are important elements to the turnover behavior prediction. Structural elements in terms of compensation schemes and business units specificities were also rated high. The same goes for certain seniority in company and time in position year bands.

According to the graph ??, new joiners in the company are at risk. So are people that have been in their roles for more than 4 years. This last element may relate to a perceived lack of career opportunity. This seems to be corroborated by the importance of managerial time in position. Interestingly managers importance in turnover decisions appears to be mainly related to their seniority in the company or their time on the job. Manager performance or behavior does not rate extremely high. Another interesting element is that remote jobs do not seem to be driving more turnover than other offices location. This would hint to local labor market specificities. In this section, it has been showed that it possible to model voluntary turnover with a couple of standard variables. Even though this may not hold for all types of jobs, the announced performance proved replicable on the prepared test set. A discussion about the model use to deliver insights on retention policies is now in order.

4 Retention Discussion.

According to recent reviews in the field of employee retention (see [START_REF] Das | Employee retention: A review of literature[END_REF], [START_REF] Ramlall | A review of employee motivation theories and their implications for employee retention within organizations[END_REF]), the results from the previous section are not surprising. A number of generic actions to bind people to firms have already been discussed over the years. Compensation topics, including rewards and recognition schemes are among the most popular (see [START_REF] Bryant | Compensation, benefits and employee turnover: Hr strategies for retaining top talent[END_REF] for an example). Other elements such as opportunity for growth & development, accountability and leadership structure have also been stressed. Some further elements regarding the workplace and work life balance have been raised too. But as stressed by the literature reviews retention efforts should be tied to an in depth turnover analysis, which will be the aim of this final part of our study. The previous results motivated us to test five simple possible programs. The first two are about reviewing the job locations: in the program P 1, remote jobs are reassigned to the location 1, while in P 2 jobs in location 3 are reassigned to location 1. The next ones are about the managers for the considered labor categories. In the program P 3, all managers were forced to have a first internal experience prior to their managerial role. This translated in reallocating all managers with company tenure between 0 and 2 years to a 3 to the 7 years band. In the program P 4, managers were assumed to rotate frequently between team so that their time in position would be kept below 2 years. Finally we tested an employee program P 5 that assume that people were bound to the company during their first 2 years in position. Certain parameters of the prediction set were altered to perform the sensitivity analysis required to simulate the retention programs as previously described. Two types of policies were investigated. It is indeed either possible to apply the program P 1 to P 5 to all the people in scope of the study or to target only the individuals flagged as leavers and adopt a policy that suits them best.

Mass Actions. As far as mass actions are concerned, the following table summarizes our findings:

The results displayed above show that programs related to internal mobility are among the most efficient options to reduce turnover. If the program P 5 appears the most efficient, it also is the most difficult to set in place and offers little upside compared to the managerial rotation program. Interestingly location change offers little value from a retention standpoint. This could be explained in this case by the fact that the labor category at stake can work in a remote fashion. This indeed creates a country wide labor market to compete in.

Targeted Actions. According to the algorithm results, about 40 % of the population is likely to leave and requires an action. The investigated course is now to test for each of the supposed leavers which of the programs(P 1 to P 5) is useful. This will limit the amount of effort required while optimizing the employee retention. This leads to a final % of leavers of 24%, which represents a significant mitigation of turnover. The results in terms of actions are summarized in the table below: These results show that to halve the turnover rate, actions only need to be started for 18% of the total population. In the end, about 25% of the population at risk of departure needs a new manager and 11% require an incentive to stay over the first two years of their role. This highlights solutions that the Human Resource organization and notably the talent management centers of expertise could deploy in in order to successfully contribute to ones organization management.

Discussion.

Several limitations to this study exist and are listed below:

• Model Limits. First, we did not have a holistic vision on individual parameters. For instance, detailed compensation parameters were missing. It is completely possible that fed with another set of features, the algorithms would have yielded better performances and different interpretations, for instance in terms of importance ranking. The story developed in this study case results from insights driven discussion between experts. We argue that if advanced analytics are important, the key elements here were the discussions that resulted in a general buy in of the retention policies simulations.

• Emotional Component in the job relationship. The discussions held with our sounding board raised another issue. Turnover may stem from a mix of rational and emotional components. The dataset was mainly organized around standard organizational or labor indicators. Little to no indication regarding people profiles, behaviors or preferences was available.

• Stress Supply vs Demand Approach. The developed approach works well to propose turnover mitigation measures. However we believe that it should not be the first thing to do. Instead we recommend leading the turnover and retention discussion with thorough job level productivity discussion. This indeed helps companies navigate in the supply & demand type of environment that are labor markets and therefore helps them define what an acceptable turnover rate is. Productivity will indeed help defining the cost of the turnover related disruption while the supply demand equilibrium will help finding the right solution mix in terms of staffing vs retention efforts. We personally believe that the human resource function is a key operating body of companies. Yet it needs to tie its activity and services to tangible business outcomes (sales, cost, productivity) to prove its value. This wasn't stress enough in our study and a review of productivity definition across functions appears mandatory to standardize this type of approach.

Conclusion & Next Steps.

In this paper, a method to approach employee retention has been proposed using standard machine learning techniques. In a first part, a literature review has shown how close this problem is from the customer churn one. Yet, to our knowledge, little has been done regarding employee turnover from a quantitative standpoint. This generated a discussion with experts on how to tackle this problem and generatemeaningful features. Those features were then fed to standard machine learning algorithms under various resampling schemes to account for classes imbalance. The best performing algorithm was retained to predict turnover and a sensitivity analysis was led to understand the effects of several retention policies. We found that for the data at hand, the most efficient retention practice was to develop talent mobility across positions. The principal next step to this study would be to include detailed compensation elements to the feature mix. The current model is indeed more around the employee perception of its internal environment than about rational economic tradeoffs. We indeed believe that such models have the potential to mimic an individual job related utility function.

Fig 3 .

 3 Fig 3. Varibale Importance (RF with Rose Resampling)

Table 1 .

 1 Classification Performance among resampling methods.

	Sampling Best Algorithm ROC Spe. Sel.
	None	LDA	0.73 0.94 0.19
	Down	LDA	0.74 0.61 0.67
	Up	RF	0.96 0.82 0.96
	Rose	RF	0.95 0.81 0.96
	Smote	RF	0.87 0.86 0.74

Fig 2. ROC Curves with ROSE resampling

In terms of algorithms, we saw that the tree based ones performed best. The following performances were indeed recorded with ROSE resampling:

Table 2

 2

	. Classification Performance among
		algorithms.
	Algorithm	ROC Specificity Selectivity
	LDA	0.75	0.67	0.74
	SVM (Radial) 0.80	0.69	0.76
	RF	0.95	0.81	0.96
	Treebag	0.94	0.78	0.94

The corresponding ROC Curves have been reported to the left.

Table 1 :

 1 Retention Mass Actions Simulations.The five programs mentioned (P 1 to P 5) were tested on a prediction set, which was built from the current year of data where no turnover indication was available. It was therefore different from both the test and training set mentioned earlier. Size and characteristics of the prediction set were similar.

	Program Type	Program Details	% of leavers
	None	No Retention Policy	41.5%
	P1.Location	Remote Job reassigned to Location 1	40.9%
	P2.Location	Location 3 reassigned to Location 1	41.3%
	P3.Manager	People Managers had 1 role internally	39.7%
	P4.Manager	Manager Rotation Program	32.3%
	P5.Employee	Bind newly assigned people	30%
	4.1 Retention Policy Simulations.

Table 2 :

 2 Retention Targeted Actions Summary.

	Action Type	% of the total	% of the potential
		Population concerned leavers concerned
	None	82,42%	57,67%
	P1.Location	0,88%	2,12%
	P2.Location	0%	0%
	P3.Manager	1,54%	3,70%
	P4.Manager	10,55%	25,40%
	P5.Employee	4,62%	11,11%