Stéphane Perrin
email: stephane.perrin@univ-smb.fr

Eric Benoit
email: eric.benoit@univ-smb.fr

Didier Coquin
email: didier.coquin@univ-smb.fr

Decision method choice in a human posture recognition context

Human posture recognition provides a dynamic field that has produced many methods. Using fuzzy subsets based data fusion methods to aggregate the results given by different types of recognition processes is a convenient way to improve recognition methods. Nevertheless, choosing a defuzzification method to implement the decision is a crucial point of this approach. The goal of this paper is to present an approach where the choice of the defuzzification method is driven by the constraints of the final data user, which are expressed as limitations on indicators like confidence or accuracy. A practical experimentation illustrating this approach is presented: from a depth camera sensor, human posture is interpreted and the defuzzification method is selected in accordance with the constraints of the final information consumer. The paper illustrates the interest of the approach in a context of postures based human robot communication.

Introduction

Human posture recognition provides a dynamic field that has produced many methods [Mitra and Acharya 2007] that commonly perform a measurement process in order to convert the physical state of an entity into an information entity. Although numerical values are commonly used to represent measurement results, it is now admitted that some applications manipulate symbolic values or linguistic terms better.

In this paper, we concentrate first on recognizing human posture from upper limb posture detection. The two parts (arm and forearm) are expressed using linguistic terms. The corresponding symbolic values result from numeric angle measurements of the human body provided by a depth camera sensor, in our case an Asus Xtion Pro Live. We also use linguistic terms to express postures from symbolic values of the upper limb parts.

Then we focus on the decision process performed from the symbolic values, which are commonly expressed in terms of mass. Fusion methods are particularly effective here and are used to manipulate mass [Dubois and Prad 1988]. They are generally used in the decision system as they can formalize decision criteria from fuzzy information, especially when evidence theory is used. Finally, we propose to express the needs of the information consumer, which are viewed as constraints on the decision process. This allows to choose and compute the decision, i.e. action to be done, in accordance with the consumer's needs and use.

Posture recognition carried out by a human is complex and the decision process takes into consideration criteria like hesitation between known postures or belief in a recognition posture. Fuzzy logic facilitates the manipulation of these concepts. In the case of automatic and artificial processes for human posture recognition, we show that results of fusion methods associated to the evidence theory are a good way to express consumer criteria, which are finally used to select the defuzzification method.

This approach, illustrated in section 4, is used to give orders to a humanoid NAO robot developed by the Aldebaran Company, from human posture recognition. The system learns a set of reference postures, each one corresponding to an order chosen to be transmitted to the robot. For example: the user wants the robot to execute an order only if the recognition of the corresponding human posture is sure, i.e. with low uncertainty or not ambiguous with other possible reference postures. Another example: a posture corresponds to an emergency action. In this case, if this posture is recognized with enough certainty, the corresponding order is chosen even if another posture is recognized at the same time, but with a greater certainty.

In section 2, we present posture modeling using fuzzy representation. Section 3 details the posture recognition process.

In section 4 the decision process is described using distance criteria from learning reference postures. This approach allows for defining and formalizing user constraints like recognition quality or threshold distance of posture detection. Facilitating the decision process based on mass transfers inside fuzzy representation of human posture is introduced.

User constraints are thrown back to the decision system which is now able to choose the robot order to be applied, in accordance to user expectation.

Fuzzy logic for human posture modeling

This section goes back over the concepts of fuzzy nominal scale and metrical scale presented in [START_REF] Benoit | The role of fuzzy scales in measurement theory[END_REF] that are used to represent postures.

Fuzzy representation: fuzzy nominal scale

This section goes back over the concepts of fuzzy nominal scale and metrical scale presented in [START_REF] Benoit | The role of fuzzy scales in measurement theory[END_REF] that are used to represent postures. A fuzzy nominal scale is defined as the link between a quantity manifestation and its representation by a fuzzy subset of linguistic terms also called Lexical Fuzzy Subset and denoted LFS in this paper. It gives a formal framework to the fuzzy mapping process presented in [START_REF] Mauris | Fuzzy symbolic sensors -from concept to applications[END_REF][START_REF] Benoit | Fuzzy nominal scale[END_REF]. Its has been already shown that the fuzzy nominal scales map an equality relation on lexical term to a fuzzy similarity on LFSs. In [De Baets and Mesiar 2002], De Baets and Mesiar presented multiple possible fuzzy relations that can be used to extend the concept of fuzzy nominal scales. We especially point out the introduction of a new distance between LFSs in [START_REF] Allevard | The transportation distance for fuzzy descriptions of measurement[END_REF]]. This distance, called transportation distance and inspired by the Earth Mover Distance in [START_REF] Rubner | The Earth Mover's Distance as a Metric for Image Retrieval[END_REF], is linked with an arbitrary predefined distance between lexical terms and extends it by the way of a metrical scale as presented in [START_REF] Benoit | The role of fuzzy scales in measurement theory[END_REF].

Let dS be an arbitrary defined distance between lexical terms. This distance reflect a knowledge related to the semantic of the lexical terms. It can be experimentally defined using a calibration process. Another way is to use this distance to include an knowledge on the relation between lexical terms. For example, the distance between two terms representing similar entities is arbitrarily defined as small. The transportation distance d'S between LFSs is then deduced from dS such that the coincidence on singletons is respected.

Working with a metrical scale gives much more possibilities than working with a nominal scale even if this one is a fuzzy nominal scale. Indeed the fuzzy nominal scale preserves only the similarity during the measurement: if 2 entities are similar then their representations (as LFSs) throw a fuzzy nominal scale are similar. A metrical scale preserves also the comparisons of distances between entities. This means that the distance comparison can be used on the set of LFSs.

In this paper, we propose to transpose the concept of tolerance interval to the set of LFSs. The chosen solution to implement this is to create a tolerance volumes defined with the transportation distance.

Fuzzy scale provides a tool to represent a posture with an LFS, but gives no semantic to the membership degree of each term to this fuzzy subset. In this study, we decided to choose a weak semantic by the interpretation of the fuzzy membership degrees as belief masses as defined in the TBM (Transferable Belief Model) [Smets 2000]. According to this semantic, each LFS is termed as Basic Belief Assignment i.e. the membership degree of a LFS is interpreted as a unitary mass distributed on the singletons.

Human posture representation

There has been a lot of focus on the development of natural interfaces using human communication modalities in the human system interaction field. One of these is communication through postures that can be described with words. Fig. 1 (left) illustrates the posture "hello" in a 2D representation of the body detected by the depth sensor and the measured joints. This particularity of postures makes it possible to describe them with fuzzy nominal scales.

The depth camera sensor (the Asus Xtion Pro Live) produces posture detection using NiTE library. The result of this process is a set of 3D joint positions that we call the measured skeleton.

We illustrate our approach with a right upper limb detection posture. To express the human posture representation, we decompose arm and forearm representation into 2 corresponding intermediate high-level representations which are expressed using words. Human posture and high-level representations of arm and forearm measurement are linked by rules as shown below.

Each body part (i.e. the arm and forearm) are expressed using words. The angles pertaining to the arm and forearm are computed from the joint positions of the detected skeleton. Lexical sets are chosen to have simple and easily understandable descriptions. Each part (i.e. the arm and forearm) is characterized by the 2 measured angles from the position of the joints, as illustrated in fig. 1. We also use lexical fuzzy subsets as shown below.

In this section, we present arm forearm modeling from respective angles measurement of skeleton. LFS are used. Arm and forearm posture definition rules are detailed. Then, right limb modeling is detailed using LFS too and corresponding rules are detailed too.

1) Arm modeling

For arm angle measurement, we use a-tetha angle and a-psi angle. The a-tetha angle corresponds to the angle formed from the vertical to the arm, in the plane of the human body. a-psi is the angle formed from the vertical to the arm when the arm is level in front of the human's body. The LFS of a-theta is {down, horizon, up} and the LFS of a-psi angle is {rear, outside, front, inside}. Fig. 2 illustrates the a-theta and a-psi angle lexical posture determination from respective angle measurements. In this step, we present the concept of modal angle values that define representative angles. A modal angle is defined such that the LFS obtained by the fuzzy linguistic description is a singleton. Then, the arm posture is represented by the combination of these 2 lexical subsets, corresponding to the 2 a-tehta and a-psi angles.

The arm corresponding variable takes its values in the lexical set Larm (1):

Larm = {down, front, up, outside, rear, inside} (1)
Table 1 (left) gives the arm position rules from these lexical subsets. 2) Forearm modeling A similar process of arm modeling is done for the forearm part. 2 angles are used: f-tetha which corresponds to the angle formed by the forearm axis and arm axis and f-psi, which corresponds to the position relative to the horizon. The fuzzification process is the same as the arm part and is not detailed in this paper. The forearm corresponding variable takes its values in the lexical set Lforearm (2):

Lforearm = {open, vclose, hclose, vmiddle, hmiddle} (2)
Table 1 (right) represents the position rules from the lexical subset corresponding to f-theta and f-psi.

3) Right upper limb modeling

The posture is represented by the combination of an arm and a forearm posture and is also defined by words. Each word represents a human modal posture. Each modal posture of the right upper limb corresponds to a set of modal postures of each part of the limb.

The lexical set of postures is defined by a list of modal postures LP-mod (table 2). Using rules, each modal posture made by upper limb postures is defined in the system. This learning step is based on the sub-posture entries: the arm and forearm values. Table 2 illustrates rules defining modal postures from lexical subsets defined in (1) and (2).

It is noted that the example in table 2 illustrates a 2D dimension case due to the 2 linguistic variables (corresponding to the arm and forearm). It is possible to generate the principle to n dimensions.

The linguistic set of modal postures is given in (3): -modal={front, outside, inside, down, up, rear, frontfolded, outsidefolded, insidefolded, downfolded, upfolded, rearfolded, fronthmiddle, outsidehmiddle, insidehmiddle, downhmiddle, uphmiddle, rearhmiddle, frontvmiddle, outsidevmiddle, insidevmiddle, downvmiddle, upvmiddle, rearvmiddle} (3) The set of all modal postures LP-mod can be directly the set of reference postures i.e. known postures to be detected. This particular situation is presented in [START_REF] Perrin | Fusion method choice driven by user constraints in a human gesture recognition context[END_REF]. In this paper, reference postures are expressed from modal postures. This additional step allows for the application designer to distinguish modal postures from reference postures. Therefore, modal posture definition rules (table 2) are fixed independently from reference postures. In the next sub-section, reference posture modeling is presented based on modal posture representation.

LP

Human reference posture representation

Reference postures are the postures to be detected and are known by the system during the learning process. This section presents their representation from modal postures. Each modal posture is known by a word in the system. Reference postures can be expressed in terms of mass on known modal postures. The mass criterion is computed from the reference posture and each known modal posture. Hence, a reference posture Pref is written as:

Pref = (LP-mod,1, LP-mod,2, LP-mod,3, …, LP-mod,n) (4)
where n is the (maximum) number of modal postures (contained in LP-mod). Note that terms associated with no-neighbor modal postures, if they appear, are set to 0. Table 3 illustrates the "stop" reference posture. In this example, the reference posture is given in table 3 and fig. 3. The next section presents a detection posture process.

Decision process under user constraints

In our application context, the decision process has to choose an action from a human posture recognition result, which is expressed using fuzzy representation. This allows us to express the detection finely: several postures can be detected from one human posture. At the end of the configuration process, posture knowledge is made up of a lexical set, and a set of reference postures. Each reference posture is defined by a fuzzy subset interpreted as a mass distribution on the lexical set [START_REF] Benoit | Body posture measurement in a context of example-based teaching[END_REF][START_REF] Allevard | Dynamic gesture recognition using signal processing based on fuzzy nominal scales[END_REF]. A measurement result is also defined as represented by a fuzzy subset interpreted as another mass distribution on the same lexical set. The decision process then acts as a defuzzification. This fluency of information carried by fuzzy representation is conventionally employed cases using multi-sensor detection. In this paper, we focus on its interests in order to automatize the choice of action to be done from one human posture recognition. The imprecision carries information that represents possible confusion, hesitation or belief of detected postures. The output of the decision process stems from the defuzzification process.

Several reference postures are detected from one human posture detection. In this experiment context, we consider that each reference posture corresponds to an action to be executed by the NAO robot. For each reference posture LP-ref,i is a corresponding action named Ai.

In our first basic approach, the decision is given by the closest reference posture obtained by the computation of the transportation distance on the LFS space, as presented in section II.A., between the measured posture Pdetect and the reference postures. This is the case in case 1 (fig. 4) where the decision result is a nonempty set of reference postures.

Our second approach considers the uncertainty of the measurement process predominantly coming from camera process detection. The uncertainty estimation is complex in this case and is not presented in this paper. In all cases, epistemic uncertainty, i.e. relative to posture definition, is more important and taken into account by the consumer. We consider that the consumer accepts a tolerance volume around each reference posture on the LFS space, as illustrated in fig. 4. This tolerance volume plays the same role for the LFS space as the tolerance interval for numerical spaces. It is defined by the distance between a measured posture and the reference posture, which is recognized for having the measured posture inside its tolerance volume. In case 2 presented in fig. 4, the measured posture is outside the tolerance volumes of all reference postures and the decision result is an empty set. In case 3 the tolerance volume around Pref,3 is large enough to include the measured posture. In this approach the tolerance volumes do not overlap, so the decision result is an empty set or a singleton.

In our third approach, the consumer wants to take into account the possible confusion between several possible postures, which is given by the overlapping of their respective tolerance volume that depends on the distance between the refer-ence postures and on the distance that characterizes the tolerance volume. Case 4 illustrates this situation: set {Pref,1, Pref,2} is chosen as the partial decision.

Another constraint is added in order to perform the decision. The nature of the robot's action associated to the command posture is able to influence the decision process. To illustrate this, we consider two classes of actions (each corresponding to a reference posture): one class contains "classical" actions and the second "emergency" actions, corresponding respectively to a "classical" reference posture and an "emergency" reference posture. So when an "emergency" reference posture is detected even with a lower mass than a classical detected reference posture, the selected decision is the corresponding "emergency" action. From this consideration, either the nearest emergency reference posture is selected -see case 5 of fig. 4; or the consumer constraint reduces the set of possible recognized postures to the emergency related one. This situation is similar to case 2 approach, but with corresponding emergency postures only.

Perspectives

In the future our work will consider several posture recognition sensors and types of sensors. This will illustrate the interest of the multi-modal fusion approach which will make it possible to manage conflicting information. In addition, we will look into how to consider human gesture and its repetition from a temporal point of view, which will also allow us to study how fast it is done.

It would be worth studying the impact quality of the recognition process using modal information (i.e. posture) as reference. Indeed, on the one hand, not using additional reference representations simplifies the system but the learning step is dependent on the amount of known information (postures) to be detected. On the other hand, representing reference information (postures) to be detected facilitates adding new reference information. But fixed modal postures have to be chosen in order for the system to be able to represent new references.

Fig. 1

 1 Fig. 1 2D representation of 3D measurements of joints for the "hello" posture (left) and used angles from skeleton (right).

Fig. 2

 2 Fig. 2 Sub-lexical for arm posture from the a-theta angle value and the a-psi angle value.

Fig. 3

 3 Fig. 3 "stop" reference posture representation.

Fig. 4

 4 Fig. 4 Illustration of tolerance volume and the impact on decision. Let's look at an applicative example on posture recognition: 3 reference postures named pointing, standing and protect are performed and measured, then translated into LFSs on LP-modal. Ppointing, Pstanding and Pprotect to denote the 3 reference postures. These are illustrated in fig 7. A dS distance is defined on the lexical set of modal postures LP-modal . This distance is arbitrarily chosen in order to respect some constraints:  The larger distance between 2 modal terms is arbitrarily fixed to 3.0.  The smaller distance between 2 modal terms related to the same elbow angle, therefore only related to the different shoulder angles, is fixed to 1.0.  The smaller distance between 2 modal terms related to the same shoulder angle, therefore only related to the different elbow angles, is fixed to 0.5. Then dS is extended to a d'S distance on the LFSs on LP-modal, as presented in 2.1. First the distance between reference postures is computed: d'S(Ppointing , Pstanding) = 0.129 d'S(Ppointing , Pprotect) = 1.8695 d'S(Pstanding , Pprotect) = 1.9225As expected the pointing and standing postures are closer to each other than to the protect posture. A new P1 posture to be recognized is acquired then fuzzified to produce an LFS. In this example, we take a stop posture (see fig.6).

Fig. 6

 6 Fig. 6 3 reference postures: pointing, standing and protecting and the detected posture (stop).

Table 1 .

 1 Arm and forearm posture definition rules

Table 2 .

 2 Modal posture definition rules

						arm
			down	front	up	outside	rear	inside
	forearm	open close hmiddle	down downfolded downhmiddle	front frontfolded fronthmiddle	up upfolded uphmiddle	outside outsidefolded outsidehmiddle	rear rearfolded rearhmiddle	inside insidefolded insidehmiddle
		vmiddle	downvmiddle	frontvmiddle	upvmiddle	outsidevmiddle	rearvmiddle	insidevmiddle

Table 3 .

 3 "stop" reference posture determination

						arm
			down	front 0.1653	up 0.7847	outside 0.0501	rear	inside
		open 0.4348	down	front 0.07187	up 0.3411	outside 0.02178	rear	inside
	forearm	close hmiddle 0.2378	downfolded downhmiddle	frontfolded fronthmiddle 0.03930	upfolded uphmiddle 0.1866	outsidefolded outsidehmiddle 0.01191	rearfolded rearhmiddle	insidefolded insidehmiddle
		vmiddle 0.3274	downvmiddle	frontvmiddle 0.05412	upvmiddle 0.2569	outsidevmiddle 0.01640	rearvmiddle	insidevmiddle


Roland Ortiz
email: roland.ortiz@onera.fr

Folco Casadei
email: casadeifolco@gmail.com

Sylvain Mouton
email: sylvain.mouton@onera.fr

Jean-François Sobry
email: jean-francois.sobry@onera.fr

J-F Sobry

Jean Francois Sobry

using new FSI formulations

Keywords: Blade debris trajectory computation with Aerodynamic effects Fluid-Structure Interaction, mesh adaptivity, blade trajectory, CROR, EUROPLEXUS

come

Introduction

For the aviation industry, reduction of fuel consumption, gas emissions and noise remains an important challenge [START_REF] Brunet | The Clean Sky programme: environmmental benefits at aircraft level[END_REF]. The emerging Counter-Rotating Open Rotor (CROR) engine technology might bring substantial benefits in this respect and several test campaigns in wind tunnel installations are being conducted, often accompanied by numerical simulations.

A lot of work has been done during the initial development of CROR propulsion systems [START_REF] Stuermer | Validation of Aerodynamic and Aeroacoustic Simulations of Contra-Rotating Open Rotors at Low-Speed Flight Conditions[END_REF][START_REF] Vlastuin | Open Rotor Design Strategy: From Wind Tunnel Tests to Full Scale Multi-Disciplinary Design[END_REF][START_REF] Brandvik | Angle-of-Attack Effects on Counter-Rotating Propellers at Take-Off[END_REF][START_REF] Vion | Counter-Rotating Open Rotor (CROR): flow physics and simulation. 20éme Congrés de Mécanique[END_REF][START_REF] Sturmer | Multidisciplinary analysis of CROR propulsion systems: DLR activities in the JTI SFWA project[END_REF]. However, generally, the CFD codes used for aerodynamic analysis can only deal with a rigid-body representation of the structures involved. Recently, ONERA is studying the CROR propeller designed by AIRBUS [START_REF] Negulescu | Airbus AI-PX7 CROR design features and Aerodynamics[END_REF] both experimentally and by numerical simulations, which require multidisciplinary tools and approaches.

In view of the future certification of a CROR-engine powered aircraft, manufacturers should address and assume the event of engine burst, including the release/loss of a fragment of an open rotor blade. To minimize the extent of shielding on the aircraft fuselage, the areas of possible impacts have to be precisely identified [START_REF] Remacha | Large Damage Residual Strength Analysis: Simulations and Tests[END_REF][START_REF] Seng | Dynamic Open-Rotor Composite Shield Impact Test Report[END_REF][START_REF] Carney | Weight Assessment for Fuselage Shielding on Aircraft with Open-Rotor Engines and composite blade loss[END_REF]. The simulation of the fragment trajectory requires accurate capturing of the aerodynamic forces.

The main contribution of the present study is to set up and validate a simulation methodology to predict debris trajectory and possible impact areas, by taking into account the deformability of the structural components and the aerodynamic effects induced by the surrounding fluid environment.

To this end, a detailed Finite Element/Finite Volume (FE/FV) model with Fluid-Structure Interaction (FSI) is developed in the EUROPLEXUS code (EPX) [START_REF]EUROPLEXUS User's Manual[END_REF], an explicit computer program jointly developed by the French Commissariat à l'Energie Nucléaire et aux Energies Alternatives (CEA) and by the Joint Research Centre (JRC) of the European Commission.

The paper is organized as follows. Section 2 presents some key and innovative numerical techniques used in the present study: i) a FSI algorithm to couple the FV fluid model with an embedded (immersed) FE structural model; ii) a fully dynamic mesh adaptivity algorithm to automatically refine the fluid mesh only in the vicinity of the embedded structure, enhancing the accuracy of the FSI algorithm at a reasonable computational cost; and iii) a methodology to drastically reduce the extent of the fluid domain included in the numerical model, so as to further reduce the cost of the simulation without sacrificing the overall accuracy.

Section 3 shows preliminary aerodynamic CFD simulations including only the fluid. The structure (blade) is assumed to be rigid and fixed in space, and is simply represented by a rigid boundary (a solid wall in CFD terms). The scope is to validate EPX's fluid model and aerodynamic force computation against the dedicated purely CFD code elsA developed at ONERA. Finally, Section 4 presents an example of fully coupled FSI simulation where all the above mentioned numerical models are employed to accurately predict the blade trajectory and to identify the zones of impact against the fuselage. Since all structural components are treated as deformable (damageable) bodies in this study, such a type of simulations might also include the detailed study of the mechanical effects of the impact on the fuselage.

Numerical models

EPX is a general computer code for fast transient dynamic analysis of Fluid-Structure systems. The explicit central difference time integration scheme is used to advance the solution in time. This facilitates treatment of geometric non-linearities such as large motions and large strains, and of material nonlinearities such as plasticity and damage.

The structural sub-domain is discretized by FE such as continuum, shells, bars etc. and the governing equation is the conservation of momentum (equilibrium). In the fluid sub-domain, the Euler inviscid compressible equations expressing conservation of mass, momentum and energy are discretized by either FE or, like in the present work, by a cell-centred Finite Volume (CCFV) method.

Fluid-Structure Interaction

The EPX code offers a wide panoply of FSI algorithms, see [START_REF] Casadei | Strong and weak forms of a fully non-conforming FSI algorithm in fast transient dynamics for blast loading of structures[END_REF] for an overview. The optimal algorithm for each application depends upon the chosen fluid formulation (FE or FV) and on the amount of expected nonlinearity in the structure, namely the possibility of large rotations, failure, fragmentation.

Figs. 1(a) and 1(b) compare the FE and the CCFV classical approaches in the simplest possible FSI case, namely for conforming F-S meshes. In the FE formulation the discrete variables are defined at the fluid nodes, which therefore must be kept separated from the structure nodes as shown in Fig. 1(a). In the FV formulation, instead, the variables are discretized at the volume (or cell) centroids, so that fluid and structure nodes may be merged together, see Fig. 1

(b).

If a FE description of the fluid domain is adopted, FSI conditions are typically imposed by enforcing equal fluid and structure velocities at the nodes along the F-S interface, projected along the normal to the interface (while tangential velocity components are left free). In EPX this is typically obtained by a strong formulation, based on Lagrange multipliers.

However, in general the FV method is more accurate than FE for the fluid domain, and results in better pressure values for a given fluid mesh size. Therefore, CFD computer codes for purely fluid applications, such as e.g. the elsA code developed at ONERA, generally use the FV method. In the CCFV formulation used in this work, FSI is achieved by updating the fluid pressure at the cell centroid at each time step and then by applying it directly to the adjacent structure (if present) through equivalent nodal forces. By blocking the numerical fluxes of mass and energy between neighboring fluid cells separated by a solid shell wall and by using the relative (fluid minus structure) velocity in the transport terms of the ALE equations, one ensures a (weak) feedback mechanism by which the fluid "sees" the presence of the structure.

The classical FSI algorithms based on conforming F-S meshes are quite accurate but they are limited to cases of structures which undergo neither failure (with fragmentation) nor large deformations, and in particular also no large rotations which, however, are of primary interest here. The difficulties typically arise from fluid mesh rezoning algorithms being unable to avoid mesh entanglement.

For such extreme conditions a different class of FSI algorithms has been recently implemented in EPX, based upon the concept of immersed (or embedded) structure. The structure and fluid meshes are completely independent at the topological level. The structure is arbitrarily discretized using a Lagrangian description and then it is embedded (superposed) into a (background) fluid mesh. The fluid grid is typically regular (structured) and uses a Eulerian description, thus avoiding by construction the fluid mesh rezoning difficulties typical of ALE formulations.

FSI coupling is realized by searching the fluid entities (fluid nodes in FE, or fluid cell interfaces in CCFV) which are located sufficiently close to the structure, and then writing suitable coupling conditions, in a similar manner to the case of conforming meshes described previously. The candidates for coupling are the fluid entities located within a thin fluid layer (influence domain) around the structure, as shown in Fig. 2. In the case of CCFV fluid formulation used in the simulations of the present work, the embedded coupling algorithm is denoted as FLSW model in EPX, and is further detailed in [START_REF] Casadei | FLSW: A weak, embedded-type Fluid-Structure interaction model with CCFV in EUROPLEXUS[END_REF][START_REF] Beccantini | Improvement of the FLSW model for Cell-Centered Finite Volumes in EUROPLEXUS[END_REF].

Fluid mesh adaptivity

When using an embedded FSI algorithm such as FLSW, the precision of F-S coupling depends very much on the use of a sufficiently fine fluid mesh, typically much finer than the structure mesh if this is discretized by shells. Since uniform refinement of the entire fluid mesh is out if question due to computational cost, the fluid mesh should be refined at least in the vicinity of the (moving and deforming) structure. This is precisely the scope of adaptivity: to refine the fluid mesh only where it is needed, in this case close to the structure (FSI-driven adaptivity). The general strategy adopted in EPX to adaptively refine and un-refine the computational mesh is described in [START_REF] Casadei | An algorithm for mesh refinement and un-refinement in fast transient dynamics[END_REF]. FSI-driven adaptivity is best used in conjunction with an embedded FSI algorithm such as FLSW, see [START_REF] Casadei | Combination of mesh adativity with Fluid-Structure Interaction in EUROPLEXUS[END_REF]. The interacting fluid and structure are discretized in a completely independent way at the topological level. Typically, the fluid is represented by a uniform and regular (even structured) mesh fixed in space (Eulerian description) used as a "background" mesh. The structure is meshed independently and then it is "embedded" or "immersed" in the fluid mesh. The two meshes are therefore simply superposed, see Fig. 2.

Adaptivity in the fluid is activated by adding the ADAP keyword in the FSI directive (FLSW) of the EPX input file. The FLSW directive with adaptivity has been used in the last blade trajectory simulation using CCFV and FSI presented in Section 4. The ADAP sub-directive introduces adaptivity-related data for the concerned FSI model. The only mandatory parameter is L max , the desired maximum fluid mesh refinement level near the structure.

Choosing the influence domain thickness

In the FLSW model for FSI, the structure is coupled with the fluid cell interfaces which are found to be currently located within the structural influence domain. This domain is formed by circles and quadrilaterals in 2D, by spheres, prisms and hexahedra in 3D. The circles or spheres are centred on the structural nodes while the other geometric shapes are built by connecting the circles or spheres, see Fig. 2.

Thus, the thickness of the influence domain at a structural node is the diameter of the associated circle or sphere. The domain thickness at a point of the structure not coinciding with a node is interpolated from the nodal values around it. The user can either specify the thickness by imposing a uniform sphere radius R via the keyword R, or let the code automatically determine R based on the local size of the fluid mesh. In any case, a sphere radius is finally associated with each structural node, so that the local thickness of the influence domain is D = 2R.

In order to ensure tightness, i.e. to avoid spurious fluid passage across a solid structure, the local thickness of the structure influence domain (i.e. the sphere diameter D = 2R) must be greater than the diagonal of the local fluid mesh cell, see Fig. 3. If the fluid mesh is formed by squares in 2D or cubes in 3D, of size h, then in order to ensure tightness it must be:

D > √ dh ( 1
)
where d is the space dimension (2 or 3). This condition ensures that a continuous layer of fluid entities is coupled with the structure, even in the worst possible case that the structure is located exactly in the middle between two fluid entities, and has an oblique direction (not aligned with the global axes). Using a value of D much larger than the one given by eq. ( 1) is not advisable, because too much fluid would be "attached" to the structure. In each practical situation, the minimum value ensuring tightness is the best one.

When mesh adaptivity is adopted in the fluid domain, the size of the fluid mesh varies according to the level of refinement. A binary rule is adopted, whereby the size of each level is half that of the previous level. By convention, the base (ancestor or unrefined) fluid elements are placed at level 1.

Let us therefore denote h 1 the size of the base fluid mesh. At any other level of refinement L > 1, the size of the fluid mesh will be:

h L = h 1 /2 L-1 (2)
i.e., 1/2, 1/4, 1/8 etc. of the base size. The practical convention is adopted that the user always specifies the FLSW data referred to the base fluid mesh, also in the case of an adaptive calculation. Then, if adaptive FSI is desired, the ADAP keyword is added to FLSW and the LMAX keyword is used to introduce the desired maximum refinement level (L max ) of the fluid mesh near the structure. In this way, various levels of refinement can be tried out by changing only the L max value.

Adapting the fluid mesh

To obtain a progressively refined fluid mesh near the (moving) structure, from level 1 (base mesh) to level L max (the chosen maximum), we proceed as illustrated in Fig. 4 where just one structural element is considered for simplicity. Each used fluid element (base or descendent element, in adaptivity) is uniquely identified by the position of its centroid, i.e. the average position of its nodes. Then, a hierarchy of L max structural influence domains, similar to the one used to detect FSI, are built in order to adapt the mesh. Each influence domain is similar to, but has half the thickness as, the previous one in the hierarchy. The first (coarsest) influence domain (for L = 1) coincides exactly with the influence domain that would be used by FLSW in the absence of adaptivity i.e. it has the thickness D 1 declared in the input data set. For example, if a uniform sphere radius R 1 has been specified via the R keyword, then

D 1 = 2R 1 .
The last (finest) influence domain (for L = L max ) has thickness D Lmax = D 1 /2 Lmax-1 . This last domain is the one automatically used to detect FSI.

Therefore, when ADAP LMAX lmax [START_REF]EUROPLEXUS User's Manual[END_REF] is specified the radius actually used for FSI is not R

1 , but R Lmax = R 1 /2 Lmax-1 .
In the simple illustrative example of Fig. 4 we consider refinement up to level 3, i.e. ADAP LMAX 3. We assume that the user has declared in the input file an influence domain radius R = √ 2h/2 (or slightly larger), with h the size, assumed here uniform for simplicity, of the base fluid mesh. We indicate with D 1 = 2R = √ 2h the diameter (thickness) of the base influence domain. This is used to find the base fluid elements that need to be refined, as shown in a). These are all the fluid elements whose centroid falls within the influence domain, and are indicated by a cross. In b) we can see the fluid mesh refined to level 2. Then a scaled-down structure influence domain of thickness D 2 = D 1 /2 is used to identify the fluid elements which need to be further refined. In c) we can see the refined fluid mesh at level 3, which is the final one in this case. Finally, the code uses the finest influence domain D 3 = D 1 /4 to locate the fluid entities which have to be coupled with the structure, as shown in d). In the example of Fig. 4 these entities are the fluid nodes (as is typical with the FE algorithm). In case of FLSW used in the present simulations, the fluid entities considered are rather the cell interfaces.

The complete refinement and un-refinement procedure is as follows. Two loops are performed at the beginning of each time step to adapt the fluid mesh. In the first loop, "coarse" fluid elements which now find themselves "near" the structure are (progressively) refined, while in the second loop "fine" fluid elements which now find themselves "far" from the structure are (progressively) unrefined. Each loop proceeds by examining one level at a time. The refinement loop does this in increasing level order (from level 1 to level L max -1), while the unrefinement loop does this in decreasing level order, from level L max -1 to level 1). Note that elements in level L max are never examined directly. In fact, they need no refinement since they are already at the maximum refinement level.

The ALE GLOB methodology

The simulation of CROR debris trajectory and impact typically involves a huge fluid domain, from the engine to the impact point on the fuselage and possibly beyond. Discretizing this entire domain, even with the help of fluid mesh adaptivity described previously, might be computationally impractical and extremely CPU expensive.

Therefore, during the Clean Sky SFWA project [START_REF] Ortiz | CROR WP1 Blade structure and certification[END_REF][START_REF] Ortiz | 2.2.2.8. PBR-Propeller Blade Kinematics AI-PX4 Blade Trajectory[END_REF][START_REF] Ortiz | Task 2.2.2.8, PBR Propeller Blade Kinematics, AI-PX6 Blade trajectory with ALE GLOB approach[END_REF], ONERA developed into EPX a new methodology (ALE GLOB command) to reduce the air volume actually discretized in the numerical model. Only a relatively small region (a box) of fluid around the moving blade debris is discretized. Thanks to ALE formulation used in EPX, the fluid mesh can be moved arbitrarily. So, the fluid box is set to translate in space by constantly following the center of gravity (CG) of the blade, which thus remains constantly embedded in it. Appropriate inlet and outlet boundary conditions are set on the walls of the fluid box. Of course, in order to improve the accuracy of aerodynamic forces computed on the structure (which in turn controls the accuracy of the trajectory) it is advisable to activate FSI-driven mesh adaptivity (FLSW ADAP) in the fluid box. This is feasible in practice, thanks to the small extent of the meshed fluid domain. An example of application of this methodology to the CROR problematic is given in Section 4.

Wind tunnel tests and numerical simulations

The objective of the wind tunnel test campaign was to build up a static, subsonic aerodynamic database over a large range of angles of attack α and side slip angles β. This database should then be used to validate the numerical simulations. The L2 wind tunnel (ONERA facility) was used, following successful recent testing on light aircrafts [START_REF] Mouton | Combined wind tunnel tests and flow simulations for light aircrafts performance prediction[END_REF]. A 1:1.2 scale model of a blade was built and mounted on a support strut fixed on a six-component balance measuring the forces. Pressure was also measured on the scaled model, equipped with 40 pressure transducers. The repeatability analysis concerning lift and drag coefficients was considered satisfactory.

Configuration and flow conditions

This section sets the definitions and notations concerning the static aerodynamic forces exerted on CROR blade fragments. The geometry of the rear and front blades is shown in Fig. 6. Only the front blade is used for the present study. Some tests in wind tunnel are performed and then numerically simulated. Due to confidential aspects only the numerical results (aerodynamic simulations) are presented. We shall consider the frame shown in Fig. 7(a). The angle of attack and the side-slip will be defined regarding the blade frame # 1, with the standard definitions for an aircraft. All dimensions in this part of the paper are given at the scale 1. Naturally, for the tests in the wind tunnel, the surfaces and the chosen reference lengths are scaled like the model (1/1.2).

In the present paper, only the PORBR 100 (no-root blade, Fig. 6) is studied to compare numerical methods. The reference surfaces and lengths are defined as follows (see Fig. With the definitions of Fig. 8, the normalized vector coordinates which give the direction of the wind are, in the blade referential B 1 : (cos α cos β, sin β, sin α cos β) (see also [START_REF] Mouton | CFD simulations of the flow over open rotor blade fragments[END_REF]). The wind referential A (O B1 ,X A ,Y A ,Z A ) is defined Table 1 Forces and moments notation.

Referential -→ F -→ M Wind referential A F XA , F Y A , F ZA -M XA , +M Y A , -M ZA Blade referential B 1 F XB1 , F Y B1 , F ZB1 -M XB1 , +M Y B1 , M ZB1
from the blade referential B 1 with a rotation of α (angle of attack) around the Y axis, and a rotation of β (side slip angle) around the Z axis, so that the direction X A gives the direction of the wind. The incident flow, whose far-field velocity and density are V ∞ and ρ ∞ , produces a force -→ F and a moment -→ M around the point O B1 on the blade fragment. The components of -→ F and -→ M are noted as indicated in Table 1.

Table 2 Force coefficients notation. The minus signs on the rolling and yawing moments allow to retrieve the standard aircraft conventions: the rolling moment is positive when the right wing goes down, the pitching moment is positive when the nose goes up, and the yawing moment is positive when the nose goes to the right. The force coefficients are defined in Table 2.

Referential

-→ C F --→ C M Wind referential A C XA , C Y A , C ZA C LA , C M A , C N A Blade referential B 1 C XB1 , C Y B1 , C ZB1 C LB1 , C M B1 , C N B1
C XA = 2F XA ρ ∞ V 2 ∞ S ref C Y A = 2F Y A ρ ∞ V 2 ∞ S ref C ZA = 2F ZA ρ ∞ V 2 ∞ S ref (3)
C LA = 2M XA ρ ∞ V 2 ∞ S ref L ref C M A = 2M Y A ρ ∞ V 2 ∞ S ref L ref C N A = 2M ZA ρ ∞ V 2 ∞ S ref L ref (4)
Similar notations are used also for C XB1 , C Y B1 etc. The variation of force coefficients is due to the non-dimensional numbers which characterize the aerodynamic conditions: -Angle of attack α and side-slip angle β.

-Far-field Mach number M ∞ = V ∞ /a ∞ with V ∞ the incoming fluid speed and a ∞ the incoming sound speed. -Reynolds number Re = ρ ∞ V ∞ L Re /µ ∞ where L Re is a reference length and ρ ∞ , µ ∞ are the incoming fluid density and viscosity, respectively. For this study, the length L Re is the chord value, so L Re = 0.417 m. The quantities S ref and L ref appearing in eqs. ( 3) and ( 4) are a reference surface and length, respectively, previously defined in Section 3.1. Sets of elsA simulations are performed at M ∞ = 0.490 and M ∞ = 0.853, respectively, by varying α and β and are then compared with the experimental results in [START_REF] Mouton | CFD simulations of the flow over open rotor blade fragments[END_REF].

Numerical models for wind tunnel simulations

Fig. 9 shows the computational model used for the wind tunnel simulation. In the elsA CFD simulations, only the fluid was included and therefore the presence of the structure was treated as a rigid boundary. The EPX simulations, instead, included both the fluid and the structure, treated as a deformable body. Brick volumes (FV) are used to represent the air and 4-node shells (FE) for the structure (in EPX). The structure material characteristics are very close to AIRBUS data (mass, position of the center of gravity, modal analysis). Due to confidential aspects these data are not included in this paper. The following conditions are used at fluid boundaries: -At the inlet, flux is defined by imposing the velocity measured in the wind tunnel. Density and energy are imposed as constants, while continuity is imposed for pressure. -At the outlet, continuity is assumed for all variables except pressure, which is imposed. This results in an absorbing boundary condition, which avoids (or greatly reduces) spurious pressure wave reflections at the outlet. A value for sound speed and a typical relaxation length are provided, which must be greater than the largest wave length of interest. -The lateral walls are treated as infinite-volume boundaries. The correctness of flow conditions around the structure (no perturbation at the fluid boundaries) is checked a posteriori against the experimental observations.

A regular uniform fluid mesh of 50 mm cell size is used for the air domain. For the structure used in the EPX model, the element sizes are between 50 mm and 80 mm. Recall in fact that the FLSW model used for FSI in these EPX simulations requires a fluid mesh finer than the structure mesh. No adaptivity is used in the EPX simulations of this experiment. The elsA code was validated in [START_REF] Mouton | Wind tunnel testing of open rotor blade fragments[END_REF][START_REF] Ortiz | Open Rotor Blade Fragment Trajectory Testing and simulation synthesis Report[END_REF], where it was shown that the elsA simulations are accurate in predicting force and pressure within 10 % of the experimental data (Fig. 10), and even better at low and high angles of attack. Overall, good accuracy is obtained from the EPX simulations compared with elsA simulations. We can observe that a refinement of the fluid mesh is necessary to obtain sufficiently accurate results. Unfortunately, in many practical applications it is not realistic to uniformly refine the mesh over the entire fluid domain. Precisely for this reason, adaptivity was introduced into EPX to automatically refine the fluid mesh only where necessary, i.e. near the structure, as detailed in Section 2.2.

Blade trajectory simulation

Some sample EPX blade trajectory simulations are finally performed by combining all the key models (FSI, fluid mesh adaptivity, ALE GLOB) recently implemented in the code and presented in Section 2. We assume that:

-The blade loss is due to an instantaneous rupture near the blade root.

-The blade loss occurs after a stable thrust of the CROR (in good agreement with AIRBUS data) has been reached. -Only the front PORBR 100 blade is released for the cruise and take off configurations, which are shown in Fig. 14.

For the following discussion of results we consider the reference frame shown in Fig. 14: the positive X axis points from the engine towards the fuselage, the positive Y axis is directed vertically upwards and the positive Z axis is pointing forwards, i.e. in the direction of the flight. The simulations are performed up to 2.5 m of CG X-translational displacement.

Fig. 15 shows the computed longitudinal (Z) displacement of the blade center of gravity (CG) vs. the lateral (X) displacement of the CG as computed for the cruise and take off configurations, without and with fluid mesh adaptivity. One would expect that, immediately after being detached from the root, the blade debris initially tends to move forward (positive Z displacement) with respect to the engine and the more so, the higher is the engine thrust. Only somewhat later would the blade be "overtaken" by the advancing aircraft (negative Z displacement).

We saw in Section 3.3 that the largest inaccuracy in the EPX polar curves for uniform and relatively coarse fluid mesh (Figs. 11 and12) is essentially observed in the first instants of the blade-off event, in particular for the cruise con-dition, due to the initial pitch angle (small angle of attack α). If activated, the automatic fluid mesh refinement provides more accurate aerodynamic forces and it should better describe the initial motion of the blade debris just after release.

In fact, in Fig. 15 we can observe that the predicted Z-motion of the blade debris CG is inaccurate (initially negative dZ/dX derivative), if the aerodynamic forces are not sufficiently precise (too coarse fluid mesh). The pink curve CG FLSW CRUISE is obtained for a coarse uniform fluid mesh of 50 mm. The black curve CG ADAP CRUISE corresponds to a mesh with adaptivity up to a minimum fluid mesh size of about 2 mm near the structure.

The same kind of curves is plotted also for the take-off configuration. One can see that with the important engine thrust typical of take off, an initial forward displacement (along the positive Z-axis) is indeed predicted, in agreement with physical intuition, but this phenomenon is not caught by the coarse mesh. The same effect is observed for the cruise configuration, albeit to a lesser extent due to the lower engine thrust characterizing this configuration. These simulations have been carried out to study possible impacts in the fuselage during take off and cruise. See for example Fig. 16 where, howeverer, no values are shown due to confidentiality of results. This type of calculations opens the possibility of studying shielding solutions, thanks to an accurate knowledge of possible impact locations on the fuselage and to the possibility of modelling mechanical effects (deformation, damage, failure) on the impacted structure with EPX in a fully coupled FSI simulation.

Conclusions

The paper focused on some key computational aspects to obtain accurate yet computationally efficient numerical simulations of blade debris trajectory after a postulated CROR engine failure, up to impact against the aircraft fuselage. An embedded-type FSI algorithm (FLSW) was used to couple the structure with the surrounding fluid and to compute the resulting aerodynamic forces. Automatic refinement (adaptivity) of the fluid mesh only near the structure (ADAP) was used to increase FSI accuracy. Finally, a technique to limit the extent of the actually discretized fluid domain to a box constantly following the embedded blade debris (ALE GLOB) drastically reduced the CPU cost.

The first results obtained show clearly that these approaches are well suited to the class of problems of interest. The error in computed blade deviation just after blade release in cruise conditions (when the angle of attack is small and the drag force is overestimated) is dramatically reduced. Thus one can expect a better prediction of the blade trajectory, in particular during the first instants after blade loss, as well as of the impact locations with the surrounding structure (the engine itself, the front and rear blades, the fuselage).

Finally, another advantage of the EPX code is to allow performing such FSI simulations with a deformable structure, which is generally not possible with purely CFD codes. Future work will focus on the blade debris trajectory taking into account the initial release conditions due for example to bird strikes. In parallel, new investigations of shielding materials (experimental tests and impact simulations) will be performed taking into account the initial impact conditions obtained in the present work.

Fig. 1

 1 Fig. 1 FE and FV discretizations with a nodally conforming F-S mesh.

Fig. 2 FLSW

 2 Fig.2FLSW : a FSI algorithm for a fully non-conforming mesh (embedded structure).

Fig. 3

 3 Fig. 3 Structural influence domain ensuring tightness.

Fig. 4

 4 Fig. 4 FSI-driven fluid mesh adaptivity.

Fig. 5

 5 Fig.5shows an example of this methodology using a relatively coarse fluid mesh in the moving box. The center of the fluid box constantly tracks the CG of the structure. Thus one is able to simulate large translation and a complete rotation of the blade within the moving fluid box at a relatively low computational cost, much lower than by discretizing the entire fluid domain along the trajectory of the blade.

Fig. 5

 5 Fig. 5 ALE GLOB approach for a blade embedded into a moving fluid volume (with FSI).

Fig. 6

 6 Fig. 6 Rear and front blades.

  7(b)): -The reference surface S ref is the projection of the area of the full blade in the X B1 -Y B1 plane, that is 0.543974 m 2 at full scale. -The reference length L ref is the radius of the front propeller: 2.1336 m. -The moment is calculated at the point O B1 .

Fig. 7 Fig. 8

 78 Fig. 7 Definition of the standard and Airbus frame and of the blade referential B 1 .

Fig. 9

 9 Fig. 9 Numerical model for the wind tunnel simulation.

3. 3

 3 Numerical results and comparison between EPX and elsA For different angles of attack α and a chosen side-slip angle (β = 0), so-called polar curves are obtained. A comparison of force vs. angle of attack at fixed side-slip angle β and Mach number M (polar curves) as computed by the elsA and EPX codes is presented in Figs. 11 to 13. For confidentiality reasons the numerical values of force coefficients are not shown.

Fig. 10

 10 Fig. 10 PORBR 100 (no-root blade) model during wind tunnel tests.

Fig. 11

 11 Fig. 11 Comparison between EPX and elsA for β = 0, M = 0.490.

Fig. 12

 12 Fig. 12 Comparison between EPX and elsA for β = 0, M = 0.853.

Fig. 13

 13 Fig. 13 Influence of EPX fluid mesh refinement on the force coefficients: β = 0, M = 0.853.

Fig. 14

 14 Fig. 14 CROS model: different pitch angles for the cruise and take off configurations.

Fig. 15

 15 Fig. 15 Blade CG longitudinal vs. lateral displacement.

Fig. 16

 16 Fig.[START_REF] Casadei | Combination of mesh adativity with Fluid-Structure Interaction in EUROPLEXUS[END_REF] Envelope trajectory with upper and lower possible impact on fuselage for two different configurations.

Table 3

 3 Flight configurations for comparison between tests, elsA and EPX.

					Static	Dynamic	Sound
	Mach	Reynolds	Density	Temperature	pressure	viscosity	speed	Velocity
	M∞	Re	ρ∞	T∞	p∞	µ∞	a∞	V∞
			[kg/m 3 ]	[K]	[Pa]	[Pa•s]	[m/s]	[m/s]
	0.490 4.4 × 10 6	1.164	303.2	101 315 18.7 × 10 -6	349	171
	0.853 2.8 × 10 6	0.380	218.8	23 843	14.4 × 10 -6	297	253

Acknowledgements The authors would like to thank Clean Sky for trust and support in this project.


Jakub Waszczuk Heinrich
email: waszczuk@phil.hhu.de

TRAVERSAL at PARSEME Shared Task 2018: Identification of Verbal Multiword Expressions Using a Discriminative Tree-Structured Model

This paper describes a system submitted to the closed track of the PARSEME shared task (edition 1.1) on automatic identification of verbal multiword expressions (VMWEs). The system represents VMWE identification as a labeling task where one of two labels (MWE or not-MWE) must be predicted for each node in the dependency tree based on local context, including adjacent nodes and their labels. The system relies on multiclass logistic regression to determine the globally optimal labeling of a tree. The system ranked 1st in the general cross-lingual ranking of the closed track systems, according to both official evaluation measures: MWE-based F 1 and token-based F 1 .

Introduction

In this paper we give a description of TRAVERSAL, 1 a system submitted to the edition 1.1 of the PARSEME shared task on automatic identification of VMWEs [START_REF] Ramisch | Edition 1.1 of the PARSEME Shared Task on Automatic Identification of Verbal Multiword Expressions[END_REF]. The task was multilingual (treebanks annotated with VMWEs were provided for 20 languages) and its aim was to automatically identify VMWEs of several categories: light-verb constructions, idioms, inherently reflexive verbs, verb-particle constructions, multi-verb constructions, and inherently adpositional verbs.

TRAVERSAL relies on the assumption that MWEs form connected syntactic components, i.e., that lexical elements of a single MWE occurrence should be adjacent in the dependency analysis of the underlying sentence. Based on this assumption, TRAVERSAL represents the task of MWE identification as a labeling task where one of two labels (MWE or not-MWE) must be predicted for each node in the dependency tree based on local contextual information: dependency labels, word forms, lemmas, POS tags, etc., as well as the MWE/not-MWE labels assigned to adjacent nodes.

In order to capture such properties, our system encodes labelings of dependency trees as tree traversals such that each traversal corresponds to a distinct labeling of the input dependency tree. The task of MWE labeling is then reduced to finding the best traversal of the dependency tree. TRAVERSAL relies on multiclass logistic regression to discriminate between plausible and implausible traversals.

Labeling alone is not sufficient to predict MWEs since it doesn't tell us where the individual MWE occurrences start and end, a sub-task which we refer to as MWE segmentation. TRAVERSAL relies on a rather rudimentary solution to this problem -by default, all adjacent dependency nodes marked as MWEs of the same category are assumed to form a single MWE occurrence.

This paper is structured as follows. In Sec. 2 we give information about related work. In Sec. 3 we describe our system. In Sec. 4 we describe the experiments performed to determine an optimal setup for the shared task, and in Sec. 5 we summarize the results obtained by our system with this setup. Finally, we conclude in Sec. 6 and outline the possible directions for future work.

Related work

A notable example of a dependency treebank in which MWEs are annotated as connected syntactic components (subtrees) is the Prague Dependency Treebank [START_REF] Bejček | Prague dependency treebank 2.5 -a revisited version of pdt 2.0[END_REF], in which named entities and VMWEs are both annotated on top of the tectogrammatical (deep syntactic/shallow semantic) layer. Treatment of MWEs as connected syntactic components is also adopted by [START_REF] Abeillé | Parsing Idioms in Lexicalized TAGs[END_REF] within the framework of tree-adjoining grammars [START_REF] Aravind | Tree-Adjoining Grammars[END_REF]. In their approach, MWEs are modeled as families of multi-anchored elementary trees.

Two broad strategies of identifying verbal MWEs can be distinguished depending on whether MWE identification takes place during [START_REF] Vincze | Learning to Detect English and Hungarian Light Verb Constructions[END_REF][START_REF] Green | Parsing Models for Identifying Multiword Expressions[END_REF][START_REF] Candito | Strategies for Contiguous Multiword Expression Analysis and Dependency Parsing[END_REF][START_REF] Le Roux | Syntactic Parsing and Compound Recognition via Dual Decomposition: Application to French[END_REF][START_REF] Nasr | Joint Dependency Parsing and Multiword Expression Tokenization[END_REF][START_REF] Waszczuk | Promoting multiword expressions in A* TAG parsing[END_REF][START_REF] Constant | A Transition-Based System for Joint Lexical and Syntactic Analysis[END_REF] or after [START_REF] Constant | Discriminative Strategies to Integrate Multiword Expression Recognition and Parsing[END_REF][START_REF] Nagy | VPCTagger: Detecting Verb-Particle Constructions With Syntax-Based Methods[END_REF] syntactic parsing. 2 The former approach is based on the intuition that both tasks can benefit from each other and, therefore, should be performed jointly. The latter approach is simpler conceptually and can benefit from the significantly restricted solution space in comparison with the joint methods. TRAVERSAL requires that dependency trees are already constructed and, thus, adopts the latter strategy.

The method implemented in TRAVERSAL can be seen as an extension of sequential conditional random fields (CRFs) to tree structures. CRFs were applied to the task of MWE identification by [START_REF] Constant | Discriminative Strategies to Integrate Multiword Expression Recognition and Parsing[END_REF], [START_REF] Scholivet | Identification of Ambiguous Multiword Expressions Using Sequence Models and Lexical Resources[END_REF], and [START_REF] Maldonado | Detection of Verbal Multi-Word Expressions via Conditional Random Fields with Syntactic Dependency Features and Semantic Re-Ranking[END_REF], among others. However, sequential CRFs are best applied to identification of continuous entities, while verbal MWEs are often discontinuous. The issue of discontinuity is handled in TRAVERSAL transparently since it assumes that input takes the form of a (dependency) tree and not a sequence. Otherwise, it relies on the same statistical backbone as CRFs -multiclass logistic regression [START_REF] Sutton | An introduction to conditional random fields[END_REF].

Another family of approaches related to the method used in TRAVERSAL is that of the graph-based approaches to dependency parsing [START_REF] Kübler | Dependency parsing[END_REF]. The 2-order extension of Eisner's algorithm, for instance, adopts similar factorization as TRAVERSAL in that it captures relations between the nodes, their parents, and their siblings [START_REF] Mcdonald | Online learning of approximate dependency parsing algorithms[END_REF]. This algorithm, however, is restricted to projective dependency trees only. Exact non-projective parsing with such a 2-order model is intractable [START_REF] Mcdonald | On the complexity of non-projective data-driven dependency parsing[END_REF]. The method implemented in TRAVERSAL (which is already 2-order) can be extended to capture higher-order relations without becoming intractable and can be used in combination with non-projective trees. This is possible because TRAVERSAL labels the nodes but considers the input dependency structure as fixed.

System description

In this section, we describe the details of the implemented system. In Sec. 3.1, we summarize the types of features the system is able to incorporate. In Sec. 3.2, we explain how to encode the possible tree labelings as tree traversals, and we formalize the notion of traversals themselves. In Sec. 3.3, we describe the multiclass logistic regression model used to score the traversals.

Feature types

In order to discriminate the "good" from the "bad" labelings, TRAVERSAL relies on the following types of features, restricted in their scope to adjacent nodes and their labels:

• Unary features, restricted to the context of a single node • Binary parent-child features, restricted to the context of a node and its parent • Binary sibling features, restricted to the context of a node and its closest sibling3 on the left • Ternary features, giving access to the node, its parent, and its closest left sibling node

In our experiments we only relied on unary and binary features, assuming that ternary features might lead to overfitting. Using ternary features is nevertheless a feasible option as it does not change the computational cost of labeling in this model.

Encoding

Encoding consists in constructing a compact representation of all traversals of the given dependency tree. Formally, the resulting structure is a hypergraph [START_REF] Gallo | Directed Hypergraphs and Applications[END_REF][START_REF] Klein | Parsing and Hypergraphs[END_REF], and each traversal of the dependency tree is represented by a distinct hyperpath in this hypergraph.

Consider the dependency tree depicted in Fig. 1 (a). Its hypergraph encoding contains two hypernodes for each node in the dependency tree, one labeled with 0 (not-MWE), the other labeled with 1 (MWE). Furthermore, the hypergraph is populated with hyperarcs in such a way that it contains one hyperpath per each possible labeling of the nodes. For instance, the hyperpath shown in Fig. 1 (b) represents the labeling where v 2 and v 3 are both considered as MWEs (the hyperpath traverses these nodes via hypernodes labeled with 1), while the other nodes are not-MWEs.

Hyperacs determine the scope of the features we can define. However, certain relations we want to capture are not available in this hypergraph representation yet. For instance, there is no hyperarc between v 3 and v 1 in Fig. 1 (b), which prevents us from using binary parent/child features. To solve this issue, we copy the labels of parents to their children, as shown in Fig. 1 (c). Namely, each node is now represented by 4 hypernodes encoding the node's label as well as the label of its parent: 00 means that both nodes are not-MWEs, 10 that the node is a MWE but the parent is not, 01 that the parent is a MWE but the node is not, and 11 that both are MWEs. When populating the hypergraph with hyperarcs, we make sure that only valid combinations of hypernodes are connected -invalid hyperpaths such as the one shown in Fig. 1 (d) are thus not encoded.

Model

Let H(d) be the set of hyperpaths encoded in the hypergraph for a given dependency tree d. The task of labeling is reduced to the task of finding the best-score hyperpath h ∈ H(d). To solve the latter problem, we rely on a multiclass logistic regression model in which each hyperpath h is reduced to a vector of features f h of a fixed length n, where n is the number of features. More precisely, (i) each hyperarc a is represented as a binary feature vector f a such that f a k = 1 iff the k-th feature of the model holds within the context of a, and (ii)

f h = a∈h f a .
Let θ be a vector of real-valued model parameters of length n. The conditional probability of a particular hyperpath h ∈ H(d) given dependency tree d is defined as:

p θ (h|d) = exp(θ • f h ) / h ∈H(d) exp(θ • f h ), (1)
where • is a dot product. Determining the highest-probability hyperpath, as well as determining the marginal probabilities of the individual hyperarcs (important for parameter estimation), can be performed efficiently using the inside-outside algorithm. For parameter learning, we rely on the maximum likelihood estimates (w.r.t. training data T ) with normal priors over θ. The log-likelihood takes the form:

(θ) = (d,h)∈T log p θ (h|d) - n k=1 θ 2 k 2σ 2 , (2)
where the regularization parameter 1/2σ 2 determines the strength of the penalty on high parameter values. The maximum likelihood estimates are then approximated using stochastic gradient descent with momentum [START_REF] Ning Qian | On the momentum term in gradient descent learning algorithms[END_REF][START_REF] Ruder | An overview of gradient descent optimization algorithms[END_REF].

Experimental setup

In this section we describe how the system detailed in Sec. 3 was adapted to the shared task. In Sec. 4.1, we explain the process used to determine the set of feature templates. In Sec. 4.2 we describe the preprocessing steps used to facilitate MWE prediction for the individual languages. In Sec. 4.3 we return to the problem of MWE segmentation and outline the heuristics used to solve it. Finally, in Sec. 4.4, we give some details on how training of our system was performed.

Features templates

We used the Polish and French DEV datasets to determine a reasonable set of feature templates for our system. We started with a small set and incrementally augmented it with new templates as long as this led to better results on one or both languages. After a couple of iterations we ended up with the following set of templates, where v is the current node, w is its sibling or parent, l u is the u's lemma, m u is the u's MWE label, p u is the u's universal POS tag, d u is the dependency label of the arc incoming to u, Sibprefixed templates apply to sibling relations, Par-prefixed templates apply to parent-child relations, and Bin-prefixed templates apply to both types of binary relations:

• Lem: (l v , m v )
• SibMwe and ParMwe: (m v , m w )

• SibLem and ParLem: (l v , l w , m v , m w )

• BinLem: unordered pair {(l v , m v ), (l w , m w )}

• ParMweDep: (m v , m w , d v ) • SibMweDep: (m v , m w , d v , d w ) • ParLemPosDep: (l v , p w , m v , m w , d v )
• SibLemPos: (l v , p w , m v , m w )

• ParPosLemDep: (p v , l w , m v , m w , d v ) • SibPosLem: (p v , l w , m v , m w )
We used the above set of templates consistently for all languages and for all VMWE categories, except for Lithuanian -dependency trees were not available for this language. We therefore converted each sentence in the LT dataset to a pseudo-dependency tree in which (i) the first token is the root, (ii) every other token is the child of the preceding token, thus obtaining a model equivalent to a 2-order sequential CRF. We also adapted the default set of templates to Lithuanian by replacing the sibling templates with selected grandparent-related templates (possible due to the structure of pseudo-dependency trees).

Pre-processing

We applied various pre-processing procedures to 9 datasets in order to facilitate prediction of MWE labels. The pre-processing method most often applied, case lifting, consisted in reattaching case dependents to their grandparents so as to make MWEs of certain categories -notably, inherently adpositional verbs -connected. 4 We applied it to BG, DE, EN, ES, HI, HR, PL, and SL datasets. For Turkish, we removed tokens marked as DERIVs (with unspecified word form, and never marked as MWEs in training data) and copied word forms to lemmas where the latter were not present. In case of Slovak, we relied on language-specific POS tags rather than universal tags, since the latter were not provided, and assumed that tokens with an unspecified dependency head are attached to the artificial root node (with ID=0). The same pre-processing steps were applied to TRAIN, DEV, and (blind) TEST data.

Segmentation

Once the labeling of a given dependency tree is determined, we need to determine the boundaries of the detected MWEs. To this end, we considered two heuristics: (i) all adjacent nodes marked as MWEs of the same category are considered as a single MWE occurrence, and (ii) if a group of adjacent nodes is marked as MWEs but it contains two (or more) verbs, the group is divided into two (or more) distinct MWEs. We applied the first heuristic for all languages except Farsi, where the second heuristic yielded better results, notably due to a relatively high frequency of neighboring MWEs in the FA dataset.

Training

We trained the models over the combined TRAIN+DEV datasets with σ 2 = 10 (see Sec. 3.3). For a given language, we trained one model per MWE category so as to handle the phenomenon of overlapping MWEs of different categories, often occurring in the provided annotated datasets.

Results

TRAVERSAL ranked 1st in the general ranking among the systems submitted to the closed track, according to both official evaluation measures: MWE-based F 1 and token-based F 1 . Table 1 summarizes the performance of our system across 19 languages of the shared task (all except Arabic). For each language, the MWE-based and token-based precision (P), recall (R), and F 1 (F1) scores are reported, as well as the rank (Rank) of our system, and the difference (Delta) between the TRAVERSAL's F 1 score and the score of the other best closed-track system. The datasets with dependencies annotated manually, partially manually, or not at all, are marked with , , or † , respectively. For the other datasets/sentences, dependencies were obtained automatically. Con is the % of connected (via parental or sibling relation) VMWEs in the TRAIN+DEV dataset (no value =⇒ Con=Con p ), and Con p is the same measure after pre-processing. Finally, Iso p is the % of connected and isolated (with no adjacent VMWEs of the same category) VMWEs after pre-processing, for which the baseline segmentation heuristic is sufficient. Language-wise, our system performed particularly well for Slavic and Romance languages, which is likely related to our choice of Polish and French for feature template engineering. FA was the most 2), TRAVERSAL performed particularly well on discontinuous MWEs. This might be related to the view on MWEs adopted in our system, where continuous and discontinuous MWEs are not really distinguished -both are "continuous" in dependency trees. TRAVERSAL proved better in handling multi-token VMWEs than single-token (e.g. to pretty-print) VMWEs (outperformed by TRAPACC and TRAPACC S in case of the latter) and exhibited certain preference for VMWEs already seen during training (outperformed by GBD-NER-standard and GBD-NER-resplit in case of unseen VMWEs). Besides, TRAVESAL turned out less efficient in identifying identical VMWEs and variants of VMWEs seen during trainig than TRAPACC and GBD-NER-resplit, respectively, even though it outperformed the two systems for the class of seen VMWEs in general.

Category-wise (see Table 3), TRAVERSAL was quite successful in identifying inherently adpositional verbs (IAV), which suggests that the pre-processing strategy of re-attaching case markers was effective. It also performed very well for inherently reflexive verbs (IRV), verbal idioms (VID), light-verb constructions (LVC.full), and inherently clitic verbs (LS.ICV, occurring only in the IT dataset). In case of "causative" LVCs (LVC.cause), TRAVERSAL was outperformed by varIDE, and in case of multi-verb constructions (MVC) -by TRAPACC and CRF-DepTree-categs.

Conclusions and future work

This paper presents a system dedicated to identification of verbal MWEs based on the explicit assumption that MWEs form connected components in dependency trees. It divides the task of MWE identification into two subsequent sub-tasks: (i) tree labeling (with two possible labels: MWE and not-MWE), and (ii) MWE segmentation (determining the boundaries of MWEs). For the former task, it relies on the multiclass logistic regression model in order to find the globally optimal labeling for a given tree. The system ranked 1st in the closed track of the PARSEME shared task, thus showing the viability of applying CRF-like models to identification of verbal -in particular, discontinuous -MWEs.

For future work, we consider improving the MWE segmentation component of our system. In particular, we would like to explore the idea of enriching labels with information about MWE boundaries so as to perform MWE segmentation jointly with MWE labeling. Another direction for future work would be to see to what extent external resources (MWE dictionaries, word embeddings) could be incorporated in our system. We could also explore usefulness of ternary features, so far ignored in our experiments. Finally, we plan to perform a more fine-grained error analysis, so as to get better insight into the advantages and limitations of the implemented method.

Figure 1 :

 1 Figure 1: (a) Dependency tree with five lexical nodes. (b) A hyperpath corresponding to the labeling where only v 2 and v 3 are considered as MWEs. (c) A hyperpath with copying of parent labels, corresponding the same labeling as (b). (d) An invalid hyperpath, not encoded in the hypergraph (because of the red dashed hyperarcs -for instance, the hyperarc between v 5 and v 4 connects two hypernodes with different parent labels, even though v 5 and v 4 are siblings).

Table 1 :

 1 Detailed results of TRAVERSAL for 19 languages (identified by their ISO 639-1 codes)

			Corpus			TRAVERSAL results
		#VMWE	%VMWE(train+dev)			MWE-based	Token-based
		Train Dev Test Con Conp Isop	P	R	F1 Rank Delta	P	R	F1 Rank Delta
	BG	5364 670 670 95.0 97.34 93.42 75.59 47.61 58.42 4/11 -4.1 82.36 49.79 62.06 3/11 -1.8
	DE	2820 503 500 90.76 93.17 87.69 62.93 32.73 43.06 3/11 -2.21 76.17 38.36 51.02 2/11 -0.64
	EL	1404 500 501	92.86 84.66 65.7 46.79 2/11 -2.97 82.16 42.01 55.59 1/11 1.89
	EN	331	0 501 91.84 98.19 95.17 55.5 21.16 30.64 2/10 -2.24 58.31 20.33 30.15 3/10 -4.22
	ES	1739 500 500 76.55 90.13 84.59 28.84 33.4 30.95 4/11 -3.03 39.91 40.26 40.09 1/11 0.34
	EU	2823 500 500	95.28 84.38 78.28 58.4 66.9 4/10 -8.9 83.42 65.01 73.07 4/10 -3.76
	FA	2451 501 501	94.48 57.83 73.8 58.48 65.26 7/10 -12.57 90.19 65.23 75.7 6/10 -5.58
	FR	4550 629 498	98.17 92.62 77.19 44.18 56.19 1/13 5.65 84.72 48.76 61.9 1/13 6.18
	HE	1236 501 502	76.45 73.69 50.33 15.14 23.28 1/10 0.59 74.64 18.1 29.13 2/10 -0.52
	HI	534	0 500 98.5 98.88 85.58 66.3 60.6 63.32 5/10 -9.66 73.15 67.12 70 4/10 -3.35
	HR	1450 500 501 63.38 96.56 87.03 68.04 46.59 55.3 1/10 11.03 78.14 50.73 61.52 1/10 11.55
	HU	6205 779 776	99.53 90.35 88.01 74.74 80.84 4/10 -9.47 89.91 79.61 84.45 4/10 -3.55
	IT	3254 500 503	94.62 88.12 63.09 40.32 49.2 1/12 10.68 74.42 42.11 53.78 1/12 7.27
	LT †	312	0 500	58.33 58.33 29.61 13.8 18.83 3/10 -13.34 55.56 16.92 25.94 3/10 -8.49
	PL	4122 515 515 80.87 86.09 82.42 77.02 59.22 66.96 1/11 6.42 81.85 59.03 68.59 1/11 3.67
	PT	4430 553 553	95.54 90.01 76.8 52.08 62.07 1/13 1.23 85.14 54.69 66.6 1/13 4.22
	RO	4713 589 589	98.64 95.38 86.06 79.63 82.72 3/10 -2.56 88.84 82.26 85.42 2/10 -0.27
	SL	2378 500 500 71.61 88.12 86.14 79.41 54 64.29 1/10 21.95 83.61 54.54 66.01 1/10 14.04
	TR	6125 510 506 55.54 98.21 91.08 81.48 26.09 39.52 5/10 -5.72 88.38 27.66 42.13 5/10 -10.89
	AVG				67.58 44.97 54 1/13 4.26 77.41 48.55 59.67 1/13 5.04

Table 2 :

 2 Macro-average MWE-based F 1 -scores for different specialized phenomena

		IAV	IRV	LVC.cause LVC.full	MVC	VID	VPC.full VPC.semi LS.ICV
	F1	44.31 68.07	23.81	46.03	17.65	34.45	34.84	42.70	30.77
	Delta	8.89	8.51	-8.34	6.30	-11.39	8.01	2.07	2.2	10.77

Table 3 :

 3 Macro-average MWE-based F 1 -scores for different MWE categories 5 challenging dataset for our system, which is clearly due to the low % of isolated VMWEs in this dataset and, consequently, low effectiveness of the implemented segmentation heuristics. TRAVERSAL performed well on datasets with both manually annotated (FR) and automatically obtained (IT, HR, EL) dependencies, thus showing robustness w.r.t. the quality of dependency annotations.Concerning specialized phenomena (see Table

Another approach would be to identify MWEs before parsing, but we posit it is not very well adapted to verbal MWEs.

We say that node v is a sibling of node w if both have the same parent in the dependency tree.

Consider the expression based on data, with the underlined words annotated as an inherently adpositional verb in the EN dataset. Case lifting changes the set of its internal dependency arcs from {based → data, on ← data} to {based → on, based → data}, thus making based and on adjacent in the resulting dependency structure.

In Tab. 1 and Tab. 2, macro-average F1 is calculated based on macro-average precision and recall. In Tab. 3, macro-average F1 is calculated directly as the mean of the relevant F1-scores obtained for the individual languages.

Acknowledgements

The author thanks Behrang QasemiZadeh and the anonymous reviewers for their valuable comments.