Luigi Penco

Enrico Mingo Hoffman

Valerio Modugno

Waldez Gomes

Jean-Baptiste Mouret

Serena Ivaldi
email: serena.ivaldi@inria.fr

Learning Robust Task Priorities and Gains for Control of Redundant Robots

Generating complex movements in redundant robots like humanoids is usually done by means of multitask controllers based on quadratic programming, where a multitude of tasks is organized according to strict or soft priorities. Time-consuming tuning and expertise are required to choose suitable task priorities, and to optimize their gains. Here, we automatically learn the controller configuration (soft and strict task priorities and Convergence Gains), looking for solutions that track a variety of desired task trajectories efficiently while preserving the robot's balance. We use multiobjective optimization to compare and choose among Paretooptimal solutions that represent a trade-off of performance and robustness and can be transferred onto the real robot. We experimentally validate our method by learning a control configuration for the iCub humanoid, to perform different whole-body tasks, such as picking up objects, reaching and opening doors.

I. INTRODUCTION

Redundant robots like humanoids or mobile manipulators can simultaneously perform several tasks, such as reaching for a target while balancing. The usual way to control these robots is to formulate the problem as a multi-task Quadratic Program (QP) [START_REF] Rocchi | Opensot: A whole-body control library for the compliant humanoid robot coman[END_REF], where the tasks are organized according to defined priorities and the goal is to minimize the tasks errors while satisfying a set of constraints, such as joint limits, collisions, etc. Finding the strict task priorities [START_REF] Del Prete | Prioritized motionforce control of constrained fully-actuated robots:"task space inverse dynamics[END_REF], [START_REF] Ott | An overview of null space projections for redundant, torque-controlled robots[END_REF], [START_REF] Khatib | A unified approach for motion and force control of robot manipulators: The operational space formulation[END_REF], i.e. null-space relations, and/or the soft task priorities [START_REF] Salini | Synthesis of complex humanoid whole-body behavior: A focus on sequencing and tasks transitions[END_REF], [START_REF] Liu | Generalized hierarchical control[END_REF], i.e. weighted combinations, together with the task gains is often a time-consuming trial-and-error tuning procedure that requires human expertise and many tests on the robot. Here, we aim at the automated off-line optimization of such parameters for generic multi-task controllers, leveraging multi-objective optimization.

A. Related work

In the literature, many approaches have been proposed to learn soft priorities. In [START_REF] Modugno | Learning soft task priorities for control of redundant robots[END_REF], the authors parameterized the weight of each task by radial basis functions defined over time, allowing a temporal adaptation of the different priorities to the specific motions. A derivative-free stochastic optimization is used to learn the optimal parameters. Lober et al. [START_REF] Lober | Variance modulated task prioritization in whole-body control[END_REF] propose a framework that modifies a set of Fig. 1: Despite being tuned to perform several motions in simulation, a hand-tuned controller can easily fail when transferred on the real humanoid and when performing different tasks that challenge its balance. With our multiobjective optimization approach, the learned controller can work on the real robot iCub, also on different test motions.

initially interfering tasks, via stochastic optimization of their parameters. They use Gaussian kernels to compute variancedependent weights that allow to handle conflicts between tasks. Paraschos et al. [START_REF] Paraschos | Probabilistic prioritization of movement primitives[END_REF] use probabilistic movement primitives to learn the accuracy of different tasks. They exploit the variability of demonstrations given in Cartesian and joint spaces as a prioritization criteria to organize the different tasks. In [START_REF] Dehio | Multiple task optimization with a mixture of controllers for motion generation[END_REF], Dehio et al. use a mixture of controllers for whole-body motion generation and consider the mixture coefficients as policy parameters, optimizing them by means of a derivative-free stochastic optimization algorithm. Their approach allows the transfer of the learned policy to new tasks, but the optimized mixture coefficients are not verified on the real robot.

For strict hierarchies, solutions have been proposed to overcome discontinuities in the control problem [START_REF] Keith | Analysis of the discontinuities in prioritized tasks-space control under discreet task scheduling operations[END_REF], [START_REF] Kim | Continuous task transition approach for robot controller based on hierarchical quadratic programming[END_REF], arising when priorities are continuously rearranged. Dehio and Steil [START_REF] Dehio | Dynamically-consistent generalized hierarchical control[END_REF] proposed a dynamically-consistent generalized hierarchical control that allows choosing, for each pair of tasks, between a soft or a hard priority with one task having null effect on the other one. However, their method is only validated in simulation on a manipulator.

Another combination of soft weighting and hierarchies is proposed in [START_REF] Silvério | Learning task priorities from demonstrations[END_REF], where Silvério et al. introduce an identification of demonstrated priority behaviors, given an initial set of candidate task hierarchies, that allows the robot to reproduce the learned priorities in new situations. The demonstrations are given by implementing an inverse kinematics controller with the desired hierarchies in the simulated robot and making it track moving references. Both [START_REF] Dehio | Dynamically-consistent generalized hierarchical control[END_REF] and [START_REF] Silvério | Learning task priorities from demonstrations[END_REF] limit the number of tasks to three. Overall, the previous works propose interesting solutions for learning simultaneously soft and hard priorities, but for few tasks and in simulation. This is not enough for the wholebody control of real humanoid robots, where we usually have a higher number of tasks to fulfill. On top of that, learning solutions in simulations does not guarantee that such solutions will work on the real robot: this is a known problem caused by the reality gap.

Achieving transferable solutions is the central focus of many recent works in robotics, [START_REF] Antonova | Reinforcement learning for pivoting task[END_REF], [START_REF] Tobin | Domain randomization for transferring deep neural networks from simulation to the real world[END_REF], [START_REF] Clever | Cocomopl: A novel approach for humanoid walking generation combining optimal control, movement primitives and learning and its transfer to the real robot HRP-2[END_REF]. For example, optimal control and movement primitives are combined in [START_REF] Clever | Cocomopl: A novel approach for humanoid walking generation combining optimal control, movement primitives and learning and its transfer to the real robot HRP-2[END_REF] to find solutions which can be easily deployed on the real robot. However, they strongly rely on the accuracy of the simulated model to ensure the transferability of solutions. Another common approach that can help achieving the adaptability of the learned solution on new scenarios is Domain Randomization (DR) [START_REF] Tobin | Domain randomization for transferring deep neural networks from simulation to the real world[END_REF], which consists in randomizing some aspects of the simulation to enrich the range of possible environments experienced by the learner. In [START_REF] Antonova | Reinforcement learning for pivoting task[END_REF], robust policies for pivoting a tool held in the robot's gripper were learned in simulation, given random friction and control delays, such that the learned policies proved to be effective on the real robot as well. In [START_REF] Modugno | Learning soft task priorities for safe control of humanoid robots with constrained stochastic optimization[END_REF], the learning procedure guarantees strict constraints fulfillment, but transferring knowledge from simulation to reality did not fully achieve the desired behavior. This implies that constraints satisfaction can be beneficial, but not enough to achieve transferability. Indeed to achieve a better generalization, solutions which are robust rather than optimal are needed. For instance, Del Prete et al. [START_REF] Del Prete | Robustness to Joint-Torque Tracking Errors in Task-Space Inverse Dynamics[END_REF] proposed to improve the robustness of task space inverse dynamics by modeling uncertainties in the joint torques of humanoid robots. Charbonneau et al. instead, learned the soft priorities that optimize for both task performance and robustness [START_REF] Charbonneau | Learning robust task priorities of QP-based whole-body torque-controllers[END_REF], by applying the idea of DR. However, both [START_REF] Del Prete | Robustness to Joint-Torque Tracking Errors in Task-Space Inverse Dynamics[END_REF] and [START_REF] Charbonneau | Learning robust task priorities of QP-based whole-body torque-controllers[END_REF] lack experimental validation on the real robot.

B. Contributions

Differently from previous work, here we propose to learn both the structure of the controller (i.e., the position of each task in the hierarchy) and all its parameters (i.e., the task weights and Convergence Gains). We optimize for a large number of tasks and introduce a parametrization of the strict priorities that allows us to optimize them as simply as the soft weights. We look for solutions that are both high-performing in executing desired trajectories (low tracking error) and "robust" (reducing the tipping moment of the robot).

Any state-of-the-art motion generator [START_REF] Carpentier | Multi-contact Locomotion of Legged Robots in Complex Environments -The Loco3D project[END_REF] still synthesizes dynamically balanced trajectories for inaccurate robot models, without guarantees that a perfect tracking of these desired trajectories is possible on the real robot. At the same time, reactive whole-body controllers have often a very conservative design in terms of balancing, which prevents the robots to track desired trajectories that are instantaneously challenging for balance. It seems appropriate to reason in terms of compromise between tracking performance and balancing/robustness to look for controllers that can effectively work on real humanoid robots.

Instead of arbitrarily combining the two objectives (performance and robustness) into a single cost function, we follow a multi-objective optimization approach: we seek to obtain in a single optimization run the set of the Pareto-optimal solutions, i.e., the optimal trade-offs between the objectives. This enables the robot user to test candidate controllers from the Pareto front directly on the robot, without requiring further optimization or manual tuning. The proposed method is detailed in Section III.

To summarize, we address the problem of automated learning of controllers for redundant robots with the following contributions: first, we introduce a parametrization of strict task priorities, so to learn simultaneously the hierarchical structure and the parameters of the controller with a multitude of concurrent tasks; second, we use multi-objective optimization algorithm to get a set of Pareto-optimal solutions (controller configurations) to be tested by the user on the real robot.

We validate our optimization process on the humanoid robot iCub, for double support motions. We compare controllers that were automatically optimized on a training sequence of motions against a baseline hand-tuned controller, over different motion sequences (see Figure 1). We further show that our optimized controller can be successfully employed to execute a variety of motions, other than those used in the training, for example for teleoperation, where reference trajectories (unknown a priori) are generated in real-time by the human operator. Section IV details our experiments, which are also shown in the attached video.

II. BACKGROUND: MULTI-TASK QP CONTROL

For a given task T k , the QP control consists in solving the following optimization problem at each control time step:

min u A k u -b k 2 + u 2 s.t. c ≤ Cu ≤ c u min ≤ u ≤ u max ( 1
)
where u is the control input vector, e.g. the joint velocities q for Inverse Kinematics (IK) control, or the joint torques τ for Inverse Dynamics (ID) control; A k is the equivalent Jacobian matrix of the task k, e.g. the Jacobian matrix J k for IK control or J k B -1 for ID control (with B being the inertia matrix); b k the reference value for the task, a regularization factor used to handle singularities, u min and u max the control input limits and c ≤ Cu ≤ c are other equality and inequality constraints, e.g. dynamics, collision avoidance, and contact related constraints.

Fig. 2: Overview of the approach. Top: Optimization process (offline). A training motion sequence is generated. The optimization algorithm searches for the best controller configurations that make the simulated robot execute the reference motion sequence. The algorithm computes a set of Pareto-optimal control configurations, i.e. optimal trade-offs between robustness and performance. Bottom: Testing process (online). The user selects the most appropriate control configuration from the Pareto-optimal solutions for the real robot, getting a valid working solution in few trials.

If we consider n levels of hierarchies, we can solve n QP problems including local equality constraints to ensure the strict priorities between the tasks in each hierarchy i, i.e. A i-1 u i-1 = A i-1 u, ... , A 0 u 0 = A 0 u 1 . At a given level i of the hierarchy, we can also consider a weighted combination of tasks: min

u k w k ( A k u -b k 2 + u 2 ) s.t. c ≤ Cu ≤ c u min ≤ u ≤ u max (2)
For each task T k , a reference is defined, e.g. in IK control b k = ṗd k +λ k e, where ṗd k is a feed-forward velocity term and e is a Cartesian pose error, computed as in [START_REF] Nakanishi | Operational space control: A theoretical and empirical comparison[END_REF], multiplied by the Convergence Gain λ k ; while in Inverse Dynamics control

b k = pd k -Jk q + λ P k e + λ D k ė
, where pd k is the desired task acceleration, ė the Cartesian velocity error, Jk the derivative of the Jacobian of task k, q the derivative of the actual joint and λ P k , λ D k the Convergence Gains. We define as stack S a set of n tasks {T 1 , . . . , T n } organized according to different soft or strict priorities:

S = (w 1 T 1 + ... + w i T i )/ . . . (w j T j + ... + w n T n ); (3)
where T a + T b means that the tasks T a and T b are in a soft priority relation with w a , w b being the corresponding 1 Notice that there are also other ways to solve hierarchical problems using a single QP instead of a cascade of QPs [START_REF] Escande | Hierarchical quadratic programming: Fast online humanoid-robot motion generation[END_REF], however this goes out the scope of the present work.

weights, while T a /T b means that the two tasks are in a strict priority relation (T b acts in the null space projection of T a ).

Definition: We define as "control configuration" of a controller with n tasks {T 1 , . . . , T n }, the set of the Soft Priorities Weights w k , the task Converge Gain λ k and the strict priority relations between the tasks, formalized as the level of each task T k in their stack S.

III. METHOD

The goal of our method is to automatically learn a control configuration of a controller enabling the real robot to execute a variety of different reference motions (for a given category of movements, e.g. double support). We look for a "generic" control configuration that trades-off performance on several motions, rather than a "motion-specific" controller that is highly optimized for a given movement but requires the optimization to be re-run for every other motion. We also want the result of the optimization procedure to be transferable onto the real robot.

Figure 2 is a flowchart of the learning procedure. First, a multi-objective optimization process based on roll-outs performed on a simulated robot model computes off-line a set of Pareto-optimal solutions. Each solution is a control configuration that trades-off different performance criteria (i.e., tracking score and a robustness/balancing score), optimized on a training sequence. Then the user selects candidate solutions from the Pareto front and validates them on the real robot using test motion sequences. Here, the purpose is to find transferable solutions that are high-performing and well- Tt T la T la T ll T rl Tn Tcxy Two T wh T h T lf T rf balanced / "robust", i.e., reducing the tipping moment of the robot. In the following, we detail all the steps of the proposed method.

A. Motion Generation and Task Specification

The Motion Generator is a module generating a sequence of robot movements, defined by reference trajectories b k . Any motion planning algorithm could be used. In this paper, without losing generality, we use our motion retargeting framework [START_REF] Penco | Robust real-time whole-body motion retargeting from human to humanoid[END_REF], which allows us to generate references for the End Effectors (EEs) both in the Cartesian and postural space from the imitation of human movements.

The tasks T k considered for the controller are those for which the motion generator produces the references b k .

B. Control Configuration -parameters to optimize

For each task T k , we want to learn its Soft Priority Weight (SPW) w k , its Convergence Gains (CG) (position error gain λ k and orientation error gain σ k for Cartesian tasks, postural error gain µ k for joint tasks) and its position in the stack/hierarchy. A specific task T k can be either active in one level S i of the stack S or completely deactivated (i.e., not in the stack). The parameter l k called Hierarchy Level Selector (HLS) encodes the activation of the k-th task in S as follows2 :

         T k ⊆ S 1 if (0 ≤ l k ≤ 0.25) T k ⊆ S 2 if (0.25 < l k ≤ 0.5) T k ⊆ S 3 if (0.5 < l k ≤ 0.75) T k deactivated if (0.75 < l k ≤ 1) (4)
Since humanoid robots exhibit bilateral symmetry, we used the same values for the weights w k and the activation levels l k for tasks related to the left and right parts of the robot. The control parameters all consist of real values ∈ [0, 1].

C. Learning Algorithm (offline optimization on simulated robot)

The main features that should characterize our "generic" controller are high-performance (tracking of the reference motions) and robustness (reduction of the tipping moment of the robot during the motion). These two objectives may be antagonistic (e.g., when the desired motions are particularly challenging for the robot balance) hence the problem is naturally posed as a multi-objective optimization problem.

Multi-objective optimization relies on the Pareto dominance concept [START_REF] Deb | Multi-Objective Optimization Using Evolutionary Algorithms[END_REF]: a solution x 1 dominates x 2 if and only if x 1 is better than x 2 for all the objectives; if x 2 is better for at least one objective, then x 1 and x 2 are equally interesting as they represent different trade-offs. Using this definition, optimizing means finding the set of the nondominated solutions of the search space, that is, solutions that cannot be improved with respect to one objective without decreasing their score with respect to the other. This set is called the "Pareto front". Although we select a single solution to be used on the robot, the knowledge of multiple Pareto-optimal solutions, "helps the user to compare, choose a trade-off solution, avoiding multiple optimization runs and artificial fix-ups" [START_REF] Deb | Multi-Objective Optimization Using Evolutionary Algorithms[END_REF].

The algorithm we opted for is the Non-dominated Sorting Genetic Algorithm II (NSGA II) [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: Nsga-ii[END_REF], one of the most efficient stochastic multi-objective optimization methods. The objective functions are the accumulated tracking error f 1 , and a robustness score f 2 , i.e. a measure of the ZMP position inside the Support Polygon (SP). We additionally considered a third objective function f 3 , consisting of a fall avoidance score. f 3 is not strictly necessary since this information is already encoded by f 1 and f 2 , but we included it to avoid getting initially stuck in some local optimum, as we explain later on. The goal of the algorithm is to minimize f 1 and f 2 while maximizing f 3 Minimize (f 1 (x), f 2 (x), -f 3 (x)), where x are the control parameters. These objectives are never combined together, since we use Pareto-based multiobjective optimization. The objective functions are initialized at zero and change at each time step i as follows:

           f 1i = f 1i-1 + ( k Φ k i -Φ k i ) f 2i = f 2i-1 + x SP + y SP if (robot fallen) f 2i = f 2i-1 + |x cz i | + |y cz i | if (robot not fallen) f 3i = f 3i-1 -α 3 if (robot fallen) (5)
where Φ k i and Φ k i are respectively the reference and the actual value measured on the simulated robot of task k at time step i; x cz i is the distance in the frontal direction of the ZMP from the center of the SP at time step i, while y cz i is the distance in the horizontal direction of the ZMP from the line connecting the feet; x SP ,y SP are the dimensions of the SP and α 3 an arbitrary positive value. The cost function f 1 includes both position, orientation and postural tracking errors, which have to be properly combined. The Cartesian positions are computed in cm; for postural and orientation tasks, we consider for each angle the arc length in cm of the circle having as radius the child link of the joint (for postural tasks) or the distance from the global frame to the link frame (for Cartesian orientation tasks). In this way, each task error in f 1 has approximately the same relative impact in the Cartesian space.

When the algorithm generates some parameters that correspond to an unfeasible stack (e.g. empty level in the hierarchy that is not the last) the controller fails, i.e. it cannot be initialized. It can also fail when the solver cannot find a solution for the QP problem without violating its constraints. In such cases, we add the following penalties:

                   f 1 = f 1i-1 + α F 1 (I -i) if (i = 0) f 2 = f 2i-1 + α F 2 (I -i) if (i = 0) f 3 = f 3i-1 -α F 3 (I -i) if (i = 0) f 1 = F max if (i = 0) f 2 = F max if (i = 0) f 3 = -F max if (i = 0) (6)
where I is the total number of steps in the recorded sequence, i is the time step when the solver fails, F max is the largest value a floating-point variable can hold, α F 3 can be set to any arbitrary value greater than α 3 and lower than F max /I and α F 1 , α F 2 to arbitrary values that are lower than F max /I and respectively greater than the largest increment (∆ 1 , ∆ 2 ) that f 1 , f 2 could get in a time step when the controller does not fail. Since it might be difficult for the user to determine in advance the lower bound values of α F 1 , α F 2 , we consider also f 3 in the optimization to help the algorithm even for a wrong guess by the user of this lower bound of α F 1 , α F 2 . If the first generations indeed have large f 1 , f 2 scores with α F 1 , α F 2 lower than ∆ 1 , ∆ 2 , it may happen that the algorithm prefers failing solutions to bad performing solutions that do not fail, hence the controller fails very often and the algorithm struggles to converge to a stable configuration. In such cases, even a solution that ends up in falling represents a temporary dominant solution and can help the algorithm progress toward better solutions. Also, f 3 drives the search toward "not falling" solutions. With the adopted cost functions design, the penalty factors α F 1 , α F 2 , α F 3 , α 3 can be set to arbitrary values comprised in between lower and upper bounds that are known, with the exception of the lower bounds of α F 1 , α F 2 which can be easily guessed from the problem setting, since the first is related to the maximum tracking error and the second to the maximum robustness score in a single time step 3 .

D. Solution Selection (online tests, on the real robot)

From ( 5), ( 6) we can never get simultaneously a bad score for f 3 and a good score on f 1 and f 2 , hence all the final dominant solutions composing the Pareto front have f 3 = 0, i.e. the robot does not fall. We can then analyze the 2D Pareto front related to f 1 and f 2 (Figure 3). We start from the most high-performing solution (i.e. lowest f 1 and highest f 2 ) and try if the solution works on the real robot. If not, we move progressively to solutions that are less high-performing and more "robust" until we get to a solution that achieves balance on the real robot.

IV. EXPERIMENTS

Robot control: Experiments were performed with the iCub robot, using 32 DoFs for whole-body control. The whole-body controller is developed using the control software library OpenSoT [START_REF] Rocchi | Opensot: A whole-body control library for the compliant humanoid robot coman[END_REF], [START_REF] Hoffman | Multi-priority cartesian impedance control based on quadratic programming optimization[END_REF]. We tested our approach on an IK-based implementation of the multi-task QP controller (Section II). For the experiments on the real robot, the constraints considered in the QP are joint position and velocity limits, and the center of mass (CoM) kept inside the support polygon. To learn the control parameters, the robot is simulated using the open-source simulator Dart [START_REF] Lee | Dart: Dynamic animation and robotics toolkit[END_REF].

Motion generator, training and testing sequences: To generate the training and testing motion sequences for the optimization and validation of the controller, we used our motion retargeting framework [START_REF] Penco | Robust real-time whole-body motion retargeting from human to humanoid[END_REF]. We recorded the movements of a human equipped with the XSens MVN motion tracking suit, and then we retargeted the motions onto the robot model. For the training set, we recorded a 68-seconds sequence, consisting of a different series of whole-body movements that solicit as many body parts as possible, so to generalize well to other motions. For the validation, we recorded three different sequences: S1: a squat motion; S2: a movement where the robot has to shift completely its weight on the left foot and reach a high position with the left hand; S3: a complex movement where the robot has to simultaneously rotate and incline its torso while shifting its weight on the right foot and moving the arms.

Controllers C1 and C2 to be optimized: To show that our approach does not depend on the number or type of tasks (e.g., Cartesian, postural), we seek solutions for two different types of controllers, namely C1 and C2. They are specified by the set of tasks considered for their control configuration, reported in TABLE I. C1 takes as references (from the motion generator) mainly Cartesian tasks, while C2 mostly postural trajectories. Both controllers can be used by the humanoid to realize double support motions, but C2 replicates the controller that we have been using for teleoperating the iCub robot to perform human-like motions in our previous work [START_REF] Penco | Robust real-time whole-body motion retargeting from human to humanoid[END_REF], where the postural tasks are critical for imitating the human. For this reason, we will validate both controllers on the real robot with the aforementioned sequences S1, S2 and S3, but only C2 will be further validated for the robot teleoperation.

Optimization on training sequences (offline):

The parameters of the two controllers C1 and C2 are learnt by the algorithm NSGA-II implemented in Sferes v2 [START_REF] Mouret | Sferesv2: Evolvin' in the multi-core world[END_REF], a C++ framework for multi-core optimization. We set a population p of 100 individuals with 300 generations g (for a total of 30100 evaluations). To provide statistically significant results, we executed in parallel 20 runs on an Intel R Xeon TM E5-2620 with 32 cores at 2.1 GHz. The parallel optimization takes about 15 hours4 . The duration of the optimization mainly depends on the length of the learning sequence that has to be simulated for a number of p • g times. We opted for a long learning sequence to find a control configuration that can generalize well to many tasks and that can be found by running the optimization just once. For the penalties in the cost functions we used α F 1 , α F 2 , α F 3 = 0.5 and α 3 = 0.1 (see Section III-C). The algorithm converges to a set of Pareto-optimal trade-offs among f 1 and f 2 (see Figure 3).

Validation on the test sequences and selection of the solutions (online, on real robot): Once the Pareto-optimal trade-off solutions are found, we follow the testing procedure of Section III-D to select the final transferable solutions for C1 and C2 on the real robot. We use the three test sequences S1, S2, S3. We tried on the real robot different solutions from the Pareto front starting from those associated to the lowest tracking error (III-D). In the attached video, we show on the learned (median) controller C1 with a squat motion with straight torso reference, that these solutions are not robust enough to be transferred onto the real robot, which falls. After trying those with f 2 = 37, f 2 = 32 and f 2 = 27 we found that the median solution with associated robustness score f 2 = 22 is transferable to the real robot (see attached video). We report here the structure of the stack of C1 that represents the most frequent solution, given f 2 = 22 (see

while for C2 we have:

S C2 = (w f (T lf + T rf ) + w o T wo + w n T n )/ (w cxy T cxy + w wh T wh + w t T t + w a (T la + T ra ))/ (w c T c ); (8)
The corresponding median gains and soft weights are reported in TABLE II and III, along with the interquartile range (IQR) of these parameters in the 20 learned configurations. TABLE IV indicates the frequency of each task in the different levels of the hierarchy in the 20 runs 5 .

Comparison with a baseline hand-tuned controller: We compare the performance of the learned controller for C1 with respect to a baseline solution that was manually tuned by an expert. The test is performed on the three different sequences S1, S2, S3.

The baseline is the following Hand-Tuned controller (HT ):

S HT = (w ht (T lf + T rf ) + T cxy + T h )/ (T cz + T t + (T lh + T rh ))/ ((T lla + T rla )); (9)
where the the tasks concerning the feet contacts T lf , T rf and the center of mass T cxy are reasonably considered at the highest level of priority, being the most relevant for balance.The HT solution is validated on the robot for double support motions. Soft priorities are all set to 1. The CG are all set to 0.1 except for λ f eet , σ f eet , λ com that are set to 1 as done in previous work where our optimization approach

was not yet available [START_REF] Penco | Robust real-time whole-body motion retargeting from human to humanoid[END_REF], [START_REF] Rocchi | Opensot: A whole-body control library for the compliant humanoid robot coman[END_REF], [START_REF] Hoffman | Multi-priority cartesian impedance control based on quadratic programming optimization[END_REF]. Figure 4 and the video show respectively in simulation and on the real robot, how the median learned controller C1 outperforms HT in tracking the sequence S1. Since simultaneous mastering of multiple tasks during motion can be challenging (especially if these references are computed on approximate models that do not match reality), some tasks can be tracked with less precision than others. Indeed, the optimization algorithm found that penalizing the tracking of a not optimal reference for the x position of the CoM, can then lead to a better overall whole-body tracking performance, especially a better tracking of the height of the CoM (see Figure 4). In S2, by setting w ht = 0.7, we can get with HT , a performance that is comparable to the median learned controller C1 in simulation (see Figure 5). However, when transferring the result onto the real robot, HT makes the robot fall (due to a not robust enough choice of the priorities and CG) while C1 does not, as shown in the attached video. In S3, HT fails to find a solution, for both w ht = 0.7, 1. We then consider the same structure of the stack and the same soft weights of C1 in HT to see how only the CG can affect the tracking performance (Figure 6). Also in this case, with the gains set manually (that are not "robust") the real robot falls, while with the optimized gains it keeps the balance (attached video).

Validation of C2 for teleoperation: To show how a controller optimized through our approach can be used for generic motions -not previously encountered in the learning sequence, though from the same category (i.e., double support) -we used the optimized controller of C2 in our teleoperation framework [START_REF] Penco | A multimode teleoperation framework for humanoid loco-manipulation: A demonstration using the icub robot[END_REF]. We teleoperate the iCub to perform several actions: spacing the legs and picking up a box, pushing a ball in a box, pushing aside a box, opening and closing the door of a container, dancing and hitting a ball (see Figure 7). The human operator generates the movements in real-time, his movement being tracked by the Xsens MVN suit and retargeted to the robot. The teleoperated sequence, lasting more than 2 minutes of continuous movements, is reported in the video attachment. Generality w.r.t. to other robots: Our approach is not robot-specific. To show that it can be applied to other robots with a different kinematics, we optimize the C1 controller for the COMAN robot. The solution is shown in simulation for a short squat motion, in the video attachment.

V. CONCLUSIONS

We proposed a framework to automatically learn both the structure and the parameters of a "generic" whole-body controller. We used multi-objective optimization to look for solutions on the Pareto front, representing optimal tradeoffs of performance (tracking the reference trajectories) and robustness (limiting the tipping moment of the robot). This allowed us to efficiently find a set of Pareto-optimal trade-off solutions in simulation. The user can conveniently choose from the Pareto-front a pre-optimized solution to test on the real robot: this reduces considerably the number of test trials on the real robot and improves the parameters tuning. To give the reader an example, to find a suitable controller configuration for humanoid teleoperation it only took us 3 test trials on the real robot. Before our method, tuning such a controller was a time consuming trial-and-error procedure.

In this work we limited our approach to double support motions with a simple QP controller structure that does not include friction cones, contact wrenches and centroidal dynamics in the constraints [START_REF] Kuindersma | Optimization-based locomotion planning, estimation, and control design for the atlas humanoid robot[END_REF]. Those will be added in future work, to deal with more complex and dynamics motions. For example, we are automatically optimizing the parameters of a controller suitable for walking, where a model predictive controller is used as motion generator for the gait and footstep trajectories.

Fig. 3 :

 3 Fig. 3: Median Pareto front (thick line) and associated IQR (colored region) computed by NSGA-II in 20 runs with a population of 100 individuals and 300 generations for the controllers C1 (blue) and C2 (green).

Fig. 4 :

 4 Fig. 4: Comparison of the tracking performance of the median learned controller C1 and the hand-tuned controller HT (with w ht = 1) in sequence S1, on some significant tasks (in simulation).

Fig. 5 :

 5 Fig. 5: Comparison of the tracking performance of the median learned controller C1 and the hand-tuned controller HT (with w ht = 0.7, since the controller cannot find a solution for w ht = 1) in sequence S2, on some significant tasks (in simulation).

Fig. 6 :

 6 Fig. 6: Comparison of the tracking performance of the median learned controller C1 and the hand-tuned controller HT (with the same task priorities of C1) in sequence S3, on some significant tasks (in simulation).

Fig. 7 :

 7 Fig. 7: The iCub robot controlled with the learned configuration C2 while performing different teleoperated tasks.

TABLE I :

 I Considered tasks, associated symbols and control parameters (Soft Priority Weight (SPW), Hierarchy Level Selector (HLS) and Converge Gain (CG)) for the controllers C1 and C2

	Task		Control Parameters
	Description	Symbol	SPW	HLS	CG
	left foot pose	T lf	w f	l f	λ f eet , σ f eet
	right foot pose	T rf	w f	l f	λ f eet , σ f eet
	left hand position	T lh	w ha	l ha	λ hand
	right hand position	T rh	w ha	l ha	λ hand
	com height	Tcz	wcz	lcz	λcom
	com (x,y)	Tcxy	wcxy	lcxy	λcom
	waist orientation	Two	wwo	lwo	σ waist
	waist height	T wh	w wh	l wh	λ waist
	head orientation	T h	w h	l h	σ head
	chest orientation	Tc	wc	lc	σ chest
	neck posture	Tn	wn	ln	µposture
	torso posture	Tt	wt	lt	µposture
	left arm posture	T la	wa	la	µposture
	right arm posture	Tra	wa	la	µposture
	left lower arm posture	T lla	w la	l la	µposture
	right lower arm posture	T rla	w la	l la	µposture
	left leg posture	T ll	w l	l l	µposture
	right leg posture	T rl	w l	l l	µposture
	Controller	Considered tasks
	C1	Tt T

lla T rla Tn Tcxy Tcz Two T lf T rf T lh T rh T h C2

TABLE II :

 II Convergence Gains (CG) associated to the 20 learned configurations given f 2 = 22

		C1			C2
	CG	Median	IQR	CG	Median	IQR
	λ hand	0.0191	0.033	λ waist	0.5491	0.3791
	λ f eet	0.0577	0.064	λ f eet	0.2486	0.0983
	σ f eet	0.0051	0.0059	σ f eet	0.0983	0.1231
	λcom	0.4426	0.1664	λcom	0.5911	0.1946
	σ waist	0.0591	0.042	σ waist	0.0652	0.0472
	σ head	0.0796	0.0234	σ head	0.2778	0.2560
	µposture	0.5605	0.2145	µposture	0.5162	0.0821
				σ chest	0.6052	0.4009

TABLE III :

 III Soft Priority Weights (SPW) associated to the 20 learned configurations given f 2 = 22

		C1			C2
	SFW	Median	IQR	SFW	Median	IQR
	w ha	0.639	0.2131	wa	0.8406	0.296
	w f	0.5357	0.1786	w f	0.5835	0.2144
	wcxy	0.8368	0.1941	wcxy	0.9519	0.1984
	wwo	0.8674	0.4832	wwo	0.1613	0.2337
	w h	0.3343	0.3101	w h	0.5357	0.2465
	wn	0.3256	0.2893	wn	0.406	0.2419
	wt	0.9258	0.245	wt	0.0656	0.2138
	w la	0.3599	0.3133	w l	0.1145	0.3756
	wcz	0.7684	0.2191	w wh	0.1879	0.1785
				wc	0.9902	0.091

TABLE IV )

 IV :S C1 = (w f (T lf + T rf ) + w h T h )/(w cxy T cxy + w cz T cz + w t T t + +w wo T wo + w ha (T lh + T rh ))/ (w la (T lla + T rla ));

TABLE IV :

 IV Task frequency in each level of the hierarchy in the 20 learned configurations, given f 2 = 22. (Most frequent solution in bold)

		C1				C2
	Task	S 1	S 2	S 3	Task	S 1	S 2	S 3
	T lh , T rh	2	18	0	T la , Tra	3	17	0
	T lf , T rf	18	2	0	T lf , T rf	19	1	0
	Tcxy	4	16	0	Tcxy	3	17	0
	Two	6	8	0	Two	6	14	0
	T h	11	0	1	T h	6	1	0
	Tn	9	1	1	Tn	9	4	0
	Tt	3	17	0	Tt	1	17	2
	T lla , T rla	1	3	16	T ll , T rl	0	0	5
	Tcz	4	16	0	T wh	3	17	0
					Tc	0	1	9

In this work we consider only three levels of priorities, which is a reasonable assumption in humanoids' controllers, especially when dealing with a large number of tasks (TABLEI). However, one could optimize for as many levels as they wish.

If the user chooses values that are too small, the inclusion of f 3 allows the algorithm to converge to a solution anyways, as explained before. At any rate these parameters do not need an iterative tuning.

Note that the optimization is not trajectory-specific and is only run once to get a controller that can achieve many trajectories.

The purpose of the 20 runs is to provide statistical evidence about the convergence of the multi-objective optimization algorithm. We can notice that the variability of the Pareto front is small (see IQR region in Figure3), meaning that for a real use-case only one run is sufficient to compute the Pareto front and to find the Pareto-optimal solutions.

*This work was supported by the European Union's Horizon 2020 Research and Innovation Programme under Grant Agreement No. 731540 (project AnDy) and from the European Research Council (ERC) under Grant Agreement No. 637972 (project ResiBots).


Abdelouahab Attia
email: attia.abdelouahab@gmail.com

Abdelouahab Moussaoui
email: moussaoui.abdel@gmail.com

Youssef Chahir
email: youssef.chahir@unicaen.fr

Epileptic seizures identification with autoregressive model and firefly optimization based classification

Keywords: Epileptic seizures classification, AR model, Firefly algorithm, SVM, Akaike information criterion

Epileptic seizures identification with autoregressive model and firefly optimization based classification

Introduction

Epilepsy is a chronic brain disorder marked by sudden recurrent episodes of sensory disturbance, loss of consciousness, or convulsions, associated with abnormal electrical activity in the brain. Diagnosis of epileptic disease using electroencephalogram (EEG) is a challenge task in the field of biomedical science, which is mainly performed by a very skilled neurophysiologist [START_REF] Chiarelli | Simultaneous functional near-infrared spectroscopy and electroencephalography for monitoring of human brain activity and oxygenation: a review[END_REF][START_REF] Attia | An EEG-fMRI fusion analysis based on symmetric techniques using dempster shafer theory[END_REF]. The EEG signals are the electrical activity recorded from the scalp of the human brain to be analyzed by neurophysiologists for predicting and identifying epileptic diseases; especially detecting and classifying epileptic seizures. The EEG analysis for epileptic seizures has received considerable attention in the biomedical research field in the past decade (Belhadj et al. 2016a;Übeyli 2008a;[START_REF] Amorim | Electroencephalogram signal classification based on shearlet and contourlet transforms[END_REF]. In addition, diagnosis of epileptic based on automated and intelligent systems detection have become vital of brain analysis, which involves high classification schemes [START_REF] Angelov | Evolving intelligent systems, eIS[END_REF][START_REF] Angelov | On line learning fuzzy rule-based system structure from data streams[END_REF]Belhadj et al. 2016b).

In recent years, several machine learning-based methods have been proposed in the literature to classify EEG signals for identification of epileptic seizures. For instance, Tezel et al. [START_REF] Tezel | A new approach for epileptic seizure detection using adaptive neural network[END_REF]) introduced a framework using artificial neural network (ANN) and relative wavelet energy. [START_REF] Swami | A novel robust diagnostic model to detect seizures in electroencephalography[END_REF] used hand-crafted features including Shannon entropy, standard deviation, and energy, which are considered a result of extraction. The general regression neural network (GRNN) classifier has been employed in classification step. [START_REF] Guo | Automatic epileptic seizure detection in EEGs based on line length feature and artificial neural networks[END_REF] have proposed a framework based on line length feature and ANN method in order to identifying automatic epileptic seizure. [START_REF] Wang | Best basis-based wavelet packet entropy feature extraction and hierarchical EEG classification for epileptic detection[END_REF] proposed a scheme based on wavelet packet and K-Nearest Neighbor (KNN) as well as support vector machine (SVM) classifiers for epileptic seizures classification. [START_REF] Chandaka | Cross-correlation aided support vector machine classifier for classification of EEG signals[END_REF] have been used Cross-correlation with SVM classifier in classification of EEG signals. The Authors in Übeyli (2008b) presented a method that employed the multiclass support vector machine (SVM) for EEG signal classification. Few works have also exploited dimensionality reduction techniques such as Linear discriminant analysis (LDA), Principle Component Analysis (PCA), Singular value decomposition (SVD), and Independent Component Analysis (ICA) before classification of EEG signals [START_REF] Subasi | EEG signal classification using PCA, ICA, LDA and support vector machines[END_REF]. [START_REF] Nicolaou | Detection of epileptic electroencephalogram based on permutation entropy and support vector machines[END_REF] have been proposed a scheme based on the permutation entropy and SVM used to detect epileptic seizures.

Nowadays, Autoregressive model (AR) alongside machine learning methods have been used in analyzing times series (Padmavathi and Ramakrishna 2015a;[START_REF] Ansari | Analysing the accuracy of machine learning techniques to develop an integrated influent time series model: case study of a sewage treatment plant, Malaysia[END_REF][START_REF] Ordóñez | A hybrid ARIMA-SVM model for the study of the remaining useful life of aircraft engines[END_REF]). More recently, AR model has been used to generate features for the EEG signals [START_REF] Shiman | EEG feature extraction using parametric and non-parametric models[END_REF][START_REF] Zhang | Classification of EEG signals based on autoregressive model and wavelet packet decomposition[END_REF]). The AR model provided parameters that are directly useable by classifier algorithms. The AR is used owing to its ability to effectively process the high frequency resolution and the smoother spectra when the signals are divided into set of segments; especially the EEG signal that are considered as a no stationary signal [START_REF] Sharma | Classification of epileptic seizures in EEG signals based on phase space representation of intrinsic mode functions[END_REF]. However, to extract significant features of the signals using AR model, two types of feature extraction methods have been practiced: parametric method and non-parametric method [START_REF] Fabri | Parametric modelling of EEG data for the identification of mental tasks[END_REF]. Also, Evolutionary based approaches have been utilized in the classification of epileptic seizure [START_REF] Atyabi | The impact of PSO based dimension reduction on EEG classification[END_REF]. Representative examples of studies that have applied the evolutionary methods are Genetic Algorithm (GA) [START_REF] Erguzel | Feature selection and classification of electroencephalographic signals: an artificial neural network and genetic algorithm based approach[END_REF], Ant Colony Optimization (ACO), [START_REF] Khushaba | A hybrid nonlinear-discriminant analysis feature projection technique[END_REF], Particle Swarm Optimization (PSO) [START_REF] Yalcin | Epilepsy diagnosis using artificial neural network learned by PSO[END_REF] and firefly optimization (FA).

Despite the latest progress in detecting epileptic seizures, the error rates are not low enough (Padmavathi and Ramakrishna 2015b). Moreover, majority of prior works have fewer efficacies for short EEG episodes [START_REF] Burg | A new analysis technique for time series data[END_REF]). There is ample room to devise novel framework to classify epileptic seizures using EEG signals. Therefore, in this paper, we propose a scheme to classify epileptic seizure more accurately from EEG signals. In the feature extraction stage, Burg AR model and FA algorithm have been employed to obtain the best model order P to obtain the best autoregressive coefficients with minimum noise variance. The features are then fed to the SVM method for final classification. It is worth noticing that one of the common problems in AR methods is the choice of an adequate AR model order known as (P model order) [START_REF] Krusienski | An evaluation of autoregressive spectral estimation model order for brain-computer interface applications[END_REF]. To address this issue, in this work, the AR parameters have been generated using Burg algorithm with evaluation of the residual modelling error with FA method selecting P model order, such that Akaike Information Criterion (AIC) function [START_REF] Akaike | A new look at the statistical model identification[END_REF] has been used as an objective function by FA algorithm. Experimental analysis on publicly available Bonn dataset collected from healthy no-epileptic and epileptic volunteers (interictal/ictal) with eyes' tasks (closed/open) demonstrate the effectiveness of the proposed framework with high accuracy.

The remainder of this paper is organized as follows. Section 2 presents the proposed approach. Experimental protocol, dataset, figures of merit, experimental results are presented in Sect. 3. Finally, conclusions are drawn in Sect. 4.

Proposed methodology

Figure 1 shows the schematic diagram of the proposed framework for epileptic seizures classification using EEG signals.

The framework is composed of following steps: feature extraction using Burg method (AR-B) hybrid technique with firefly method to get the adequate model order P that is used in selecting the best coefficients provided from AR model, and finally an SVM classification method. Below, we give details of autoregressive modeling for EEG, Burg algorithm, Akaike information criterion, optimization AR model order P by firefly algorithm (AR-FA) and support vector machines.

Autoregressive modelling for EEG

AR model has become one of the prominent parametric methods that have been applied in many studies to model EEG signals. AR model permits describing the EEG signal as a linear representation. The regression model of the EEG signal has been accomplished by using the following formula [START_REF] Zhang | Classification of EEG signals based on autoregressive model and wavelet packet decomposition[END_REF][START_REF] Akaike | A new look at the statistical model identification[END_REF]:

where a k represents the AR parameters, P stands for the given model order and e(n) denotes the error term independent of previous samples assumed to be white Gaussian noise with zero mean and variance σ 2 .

Burg algorithm

The Burg Algorithm has been utilized to estimate the parameters of an AR model because it is different for other

(1) X(n) = - p ∑ k=1 a k x(n -k) + e(n)

SVM classification

Evaluation of performance

methods that guarantee to generate a stable model. Assume that the input signal EEG X(n); n = 1,2,3,…., N, where N refer to the size of EEG signal. The algorithm is a recursive method based on the lattice filter structure in order to minimize the forward and backward prediction error and it is executed in four steps as follows [START_REF] Burg | A new analysis technique for time series data[END_REF]):

Step 1. Calculate the initial values of error variance, i.e., computing forward error and backward error by the following equations, respectively:

Step 2. Calculate reflection coefficient and error variance by the given equations, respectively:

Step 3. Update Error and AR coefficients:

Forward error:

Backward error:

Step 4. Repeat steps 2 and 3 (with m incremented by one) until the selected model order p is reached.

The Akaike information criterion

Recently, The Akaike information criterion (AIC) [START_REF] Akaike | A new look at the statistical model identification[END_REF] has been employed in evaluation of the AR model coefficients. However, the AIC method permits selecting an adequate AR model order P [START_REF] Ouelli | Epilepsy seizure detection using autoregressive modelling and multiple layer perceptron neural network[END_REF]. Assuming that the input has Gaussian statistics, the AIC for an AR process is defined by:

(2)

2 (0) = 1 N N-1 ∑ 0 (X(n)) 2 (3) e n (0) = X(n) (4) b n-1 (0) = X(n -1) (5) m = ∑ N-1 n= m b n-1 (m -1) e n (m -1) ∑ N-1 n= m ( e 2 n (m -1) + b 2 n-1 (m -1) ) (6) 2 (m) = ( 1 -| | m | | 2 ) 2 (m -1) (7) { a k (m) = a k (m -1) + m a m-k (m -1) if m > 1 a m (m) = 1 if m = 1 (8) e n (m) = e n (m -1) + m b n-1 (m -1) (9) b n (m) = b n-1 (m -1) + m e n (m -1)
where 2 is white noise variance. P is model order and N represents the length of EEG signal.

Optimization AR model order P by firefly algorithm (AR-FA)

One of the main objectives in this study is identifying an adequate model order P, which is also one of the common problems in AR methods [START_REF] Krusienski | An evaluation of autoregressive spectral estimation model order for brain-computer interface applications[END_REF]). Hence, the AR Burg algorithm has been used to generate the coefficients and evaluation of the residual modelling error by the (AIC) metric [START_REF] Akaike | A new look at the statistical model identification[END_REF]). The optimal model order P that gives the minimum of AIC(P) has been calculated by (Eq. 10). For that reason, Firefly Optimization method has been employed in order to get the optimal model order P.

In order to generate the AR coefficients (a i ) using EEG signal X(n), n = 1,2,3,…., N, we need to fix the model order P, where P belong in {4,5,…., N/3.}. Then, AR method computes the (a i ) coefficients with 2 white noise variance. However, the major issue is the choice of model order P that permits achieving an optimal value of AIC (P). For this reason, FA method has been employed with the AIC (P) as an objective function to find the best model order P. The mathematical formulation of the optimization problem that has been focused in this work is given as follows:

where AIC(P) is a continuous nonlinear objective function.

FA algorithm

To construct the mathematical model of the algorithm, the Firefly algorithm is based on three basic rules [START_REF] Yang | Firefly algorithms for multimodal optimization[END_REF]):

1. All fireflies are unisex, involving that all fireflies can attract each other regardless of their sex. 2. The attractiveness between fireflies is proportional to their brightness. The firefly with less bright will move towards the brighter one. If no one is brighter than a particular firefly, it moves randomly. Attractiveness is relative to the brightness that reduces with rising distance between fireflies. 3. The brightness known as light intensity of a firefly is relying on the objective function. In application (simulation), the brightness of every firefly is directly relative to the value of the objective function.

The FA algorithm is based on two principals' ideas, the light intensity emitted and the degree of attractiveness.

Author's personal copy

Evolving Systems 1 3

The light intensity Ii varies with the distance r ij mono- tonically and exponentially. That is given as: where γ stand for the light absorption coefficient generally in practice taken as 1and the distance r ij between two fireflies i and j given as:

The attractiveness ij of the firefly depends on both the light intensity seen by an adjacent firefly and its distance, that may be represented by: where 0 is the attractiveness at r ij = 0.

The amount of movement of firefly i towards to another more attractive firefly j is given by: where ij is a random parameter generated by a uniform distribution and is a parameter of scale. ( 12)

I i = e -r ij (13) r ij = x i -x j2 (14) ij = 0 e -r 2 ij (15) x i = x i + ij ( x j -x i ) + ij
The pseudo code of the firefly algorithm can be summarized as below:

Model order FA algorithm

This subsection describes the use of Firefly method in the step of feature extraction. The AR-FA selects an optimal model order that chooses best parameters. The scheme and pseudo code of AR-FO are illustrated in the following::

Author's personal copy

Evolving Systems 1 3

Support vector machines (SVM)

Support vector machines is a supervised learning method introduced by [START_REF] Cortes | Support-vector networks[END_REF]. SVM is a powerful classifier algorithm that has been used in different areas, including speech disorder detection, face recognition, cancer identification, seizure prediction and EEG signal classification (Übeyli 2008a). There are three types of support vector machine techniques [START_REF] Byun | Applications of support vector machines for pattern recognition: A survey[END_REF]: (i) Linearly separable, (ii) Linearly Inseparable and (iii) Non-linearly separable.

The basic idea of SVM algorithm is based on kernel functions via a quadratic optimization problem in separating data into different groups. As a result, SVM method generates the optimal hyperplane with the largest margin. In other words, SVM projects data into another higherdimensional space. Then, SVM traces the optimal hyperplane in the projection space (Übeyli 2010). For the problem being studied in this paper, single hyperplane is sufficient to split the data into two classes, i.e., (+ 1) represents the first class and (-1) stands for the second class. Furthermore, the choice of kernel function and parameters of SVM plays an important role in the classification performance. Thus, in this work, radial basis functions (RBF) have been used as kernel functions of SVM classifier that achieved acceptable results. The RBF is expressed by:

Experiments

Here, we provide an experimental evaluation of the proposed epileptic seizures detection framework.

Dataset

The Bonn EEG dataset collected by [START_REF] Andrzejak | Indications of nonlinear deterministic and finite-dimensional structures in time series of brain electrical activity: dependence on recording region and brain state[END_REF] was used in this work. It has been widely used in epilepsy study and seizure detection and classification and is available online: (http://epile ptolo gie-bonn.de/cms/uploa d/workg roup/lehne rtz/eegda ta.html).

The complete data consists of five sets (Z, O, N, F, S). Each set has 100 single channel EEG segment of 23.6 s duration. These collections are composed of three groups. The first one is presented by the two sets Z and O recorded from five subjects with healthy volunteers (nonepileptic), whereas the set Z are recorded with condition eyes open. The set O recorded with eyes closed by using the standard 10-20 electrode placement scheme. The second one interictal group is given by the sets N, F originated from the EEG archive of pre-surgical diagnosis set N recorded from the hippocampal ( 16)

K(x, y) = exp ( -|x-y| 2 2 2
) formation of the opposite hemisphere. The set F is recorded from epileptogenic zone while the third ictal group is represented by the set S (seizure activity) (see Fig. 2).

All these EEG signals are digitized at 173.61 samples per second using 12-bit resolution. Band-pass filter settings were 0.53-40 Hz (12 dB/oct). Thus, the length of each recording is 173.61 × 23.6 ≈ 4097 samples. Figure 3 presents an example for each set.

Experimental protocol and figures-of-merit

This study followed the same protocol used in Übeyli (Übeyli 2008a), [START_REF] Subasi | EEG signal classification using PCA, ICA, LDA and support vector machines[END_REF], [START_REF] Nicolaou | Detection of epileptic electroencephalogram based on permutation entropy and support vector machines[END_REF], [START_REF] Yalcin | Epilepsy diagnosis using artificial neural network learned by PSO[END_REF] such that data sets have been divided into three classes: (i) healthy (nonepileptic)-Z, O; (ii) Interictal-N, F; and (iii) Ictal-S. Two directions of experiments have been applied. The first direction followed below steps: EEG the features extraction using AR model without AR-FA method then SVM classifier. The second direction is as follows: the FA has been employed in the step of features extraction with AR model. The AR-FA has been used to get the best AR coefficient that is followed by SVM classifier.

The performance was evaluated via Accuracy (ACC), sensitivity (SEN) and specificity (SPE). The sensitivity describes the true positive ratio, specificity is referred to as true negative ratio, while the accuracy is the ratio of true positive and negative divided by the total number of cases. In particular, TP is true positive results of a classifier; it refers to the number of EEG signals that have epileptic seizure. TN is true negative results denote the number of EEG samples in normal cases. FP is false positive results represent incorrect classifications of the negative cases into positive class. FN is false negative results denote incorrect classifications of positive cases into negative class. They ACC, SEN, SPE have been calculated as follow: Every signal has been divided onset of segments 23.6 s. The notation A,B,C,D,E have been employed for the classes Z, O, N, F, S, respectively, in order to make comparison with other works. In the experiments, the best model order P has been selected by using the AIC metric for Burg AR model. The final classification has been studied as follows: (i) healthy no-epileptic (Normal) to Interictal (sets A, B) to (sets C, D), (ii) healthy no-epileptic (Normal) to Ictal (sets A, B) to (set E), (iii) Interictal To Ictal (sets C, D) to (set E) (see Fig. 4). classification accuracies for the rest of the pairs of Sets are between 94.00% and 96.00%. It is also easy to see that the proposed method can achieve an average classification of 98.0%, 100.00% and 96.00% of accuracy, sensitivity and specificity, respectively, for healthy no-epileptic (Normal) to Interictal.

Experimental results

EEG the features extraction using AR model without FA method

EEG the features extraction using AR model with FA method

In this experiment, the feature extraction has been selected by the optimal model order P given by FA method, which permits identifying the best AR coefficients with minimum residual variance. These coefficients have been used by the SVM classifier. The AR-FA has been applied separately for each set. Figure 5 shows some examples of changes of fitness for the best element that show the convergence of objective function. The classification has followed the same paradigm as in the first experiment. The results are depicted in Table 3, while the average of performance measure is presented in Table 4. We can observe in Table 3 that the highest classification accuracies of Sets (A and E) and (B and E) are 100.00%, 100.00%, respectively. The classification accuracies for the rest of the set pairs are between 93.00% and 96.00%. An average classification of 100.00%, 100.00% and 100.00% is achieved for accuracy, sensitivity and specificity, respectively for healthy no-epileptic (Normal) to Interictal sets(A and E).

Comparison with prior methods

Here, we compare the performance of proposed method with the previous studies reported in the literature. The results are reported in Table 5. The classification results obtained by the first experiment (Sect. 3.3.1) of the proposed method (Burg AR model and SVM classifier) have achieved an impressive performance of 98.00%, 100%, and 96.00% for accuracy, sensitivity, specificity respectively, in the sets (A and E). Also, in the second experiment (Burg with AR-FA and SVM), the proposed framework attained an excellent performance of 100.00% 100.00% 100.00% for accuracy, sensitivity, specificity, respectively, in the sets (A and E). In Table 5 we can notice that the best reported result is 100% of this work on the data set (A and E) and also 97.00% on (A and D).All in all, the presented technique outperformed previously proposed methods for epileptic seizures data classification.

Conclusion

In this paper, an automated framework has been proposed to classify and detect epileptic seizures from EEG signals by combining autoregressive model (AR) and Firefly Optimization to produce an optimal model order (P) with support vector machines for high performances. Two experimental directions were followed on public Bonn dataset. In first direction, the features were extracted using AR burg model then SVM classifier. While in the second direction, the model order P is selected by FA method to be input to the AR burg model to generate the best coefficients then SVM classifier. Proposed method is able to achieve a good average of classifications accuracies between 94.50 and 100%. Moreover, proposed framework outperformed previous studies reported in literatures. The focus of the future work is to integrate other AR model with burg method such as ARIMA algorithm to fuse these AR models in the features extraction in order to enhance the accuracy of classification and diagnosis of epilepsy.

AIC fitness value

Author's personal copy

Fig. 1

 1 Fig. 1 Scheme of the proposed framework

  EEG signal, [minp,maxp] range of order p, np: number of fireflies, it_max: max_iteration Output: The model order with AIC and minimum noise variance (NSV) is given as:[P, AIC NSV] begin for r=1 to np initialize the fireflies with random model order value end for while not stop criterion do for i=1 to np do for j=1 to np do compute ( , ) value using AR burg model and AIC functions (provided by Matlab known as arburg(x,p) AIC(pRank the fireflies and update velocity and position of the fireflies and find the current best firefly with min(AIC(P)) end while

Fig. 2

 2 Fig. 2 Flowchart for AR model order P with FA algorithm

Fig. 3 Fig. 4

 34 Fig. 3 Exemplary typical EEG signals of the sets. Class (Z, O), class (N, F), and class(S)

Fig. 5

 5 Fig. 5 Some examples of the changes of AIC fitness value with FA algorithm: a for the changes of AIC fitness value set A; b for the changes of AIC fitness value set C; c for the changes of AIC fitness value set E

  Rank the fireflies and find the current best firefly best value fitness end while

	Algorithm 1: Algorithm Initialize population of n fireflies, xi i=1..n Compute Light intensity ( ), for all .i=1..n While (stopping criteria is not met) do for i=1 to n for j=1 to n if ( )> ( ) then
	end for Update Light intensity ( end for	Move firefly itowards j using (4) end if ) for all i=1..n

  Table 1 summarized this classification. The average of performance measure is given in Table 2. It can be seen from Table 1 that the highest classification accuracies of Sets (A and E)and (B and E) are 98.00% for both. Moreover, the

	SEN = TP∕(TP + FN)	(18)
	SPE = TN∕(TN + FP)	(19)

Table 1

 1

	Results of classification using (Burg and SVM))	Healthy no-epileptic (Normal) set A To interictal (sets C, D) To Ictal set E	Healthy no-epileptic (Normal) set B To Interictal (sets C,D) To Ictal set E	Interictal (sets C, D) to ictal (set E)
		AC	AD	AE	BC	BD	BE		CE	DE
	ACC	0.9600	0.9500	0.9800	0.9400	0.9600	0.9800		0.9500	0.9500
	SEN	0.9400	0.9800	1.0000	0.9000	0.9600	1.0000		0.9400	0.9400
	SPE	0.9800	0.9200	0.9600	0.9800	0.9600	0.9600		0.9600	0.9600
	Table 2 The average of performance measure of the first experiment (AR burg SVM)	Healthy no-epileptic (Normal) to interictal (%)	Healthy no-epileptic (Normal) to ictal (%)	Interictal (sets C, D) to ictal (set E) (%)
	ACC	95.25			98.00			95.00
	SEN	94.50			100.00			94.00
	SPE	96.00			96.00			96.00

Table 3

 3 The obtained classification results by the second experiment (AR-FA SVM)

			Healthy no-epileptic (Normal) (set A) to interictal (sets C, D) and to Ictal (set E)	Healthy no-epileptic (Normal) (set B) to Interictal (sets C, D) and to Ictal (set E)	Interictal (sets C, D) To Ictal (set E)
			AC	AD	AE	BC	BD	BE	CE	DE
		ACC	0.9600	0.9700	1.0000	0.9400	0.9700	0.9900	0.9900	0.9500
		SEN	1.0000	0.9400	1.0000	0.9200	0.9400	1.0000	1.0000	0.9400
		SPE	0.9200	1.0000	1.0000	0.9600	1.0000	1.0000	0.9800	0.9600
	Table 4 The average of performance measure of the second experiment (AR-FA SVM)	ACC	Healthy no-epileptic (Normal) to Interictal (%) 96,00	Healthy no-epileptic (Normal) to Ictal (%) 99.50	Interictal to Ictal (%) 97.00
		SEN	96.50			100.00			97.00
		SPE	96.50			100.00			97.00
	Table 5 Accuracies comparison between the introduced methods with other methods given in the literature	Authors This work			Dataset A and E	Methods Burg + SVM AR-FA + SVM			Accuracy (%) 98.00 100
					A and D	Burg + SVM			95.00
						AR-FA + SVM			97.00
					(C and D) and (E) Burg + SVM			95.00
						AR-FA + SVM			97.00
		Swami et al. (2016)		A and E	GRNN				100
		Guo et al. (2010)		A and E	ANN				99.66
		Subasi and Gursoy (2010)	A and E	SVM + PCA			98.75
						SVM + ICA			99.50
						SVM + LDA			100
		Chandaka et al. (2009)		A and E	Cross-correlation aided SVM classifier signal	95.96
		Nicolaou and Georgiou (2012) A and E	Permutation Entropy (PE) and SVM	93.55
					A and D					88.83
		Yalcin et al. (2015)		A and E	PSO-based neural network PSONN3	99.67
						PSO-based neural network PSONN4	98.75

Publisher's Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.


Gael De Chalendar

Brigitte Grau

Request Expansion by a Contextual Use of Classes of Nouns

We developed a system, SVETLAN', dedicated to the acquisition of classes of semantically close nouns from texts. We aim at constructing a structured lexicon for the general language, that is not for representing a specialized domain. Thus, texts are open-domain newspaper articles. The acquisition is based on a distributional method that groups the nouns that are related to a same verb with a same functional role. However, in order to deal with polysemy, classes are learned in context: they are built from text segments related to a same semantic domain. For that, we use results of ROSA, a system that clusters automatically segmented text thematic units in order to build semantic domain defined by sets of weighted words. We will show how these classes can be used to expand requests, in comparison with an expansion realized by using WordNet.

Introduction

Information Retrieval systems often requires semantic knowledge to improve their results. However, one can ask, "what type of semantics?". According to the application, it may differ. It can be only synonymous, or semantically close words, or words belonging to a same domain, either specific or general. One conclusion is that it is necessary to be able to bring together words with close signification. Moreover this gathering has to be done in a well defined context in order to take into account multiple meanings of words. For example, in the context of nuclear plants, one confronted to the sentences: "… started to replace the fuel rods…", "… started to replace the combustible of the reactor…" and "… to replace the films and the batteries of the camera… ", should join together the words combustible and rods but should put aside the word film. We are interested in robust applications aimed to cope with every domains, opposed to domain specialized systems. Those systems often use preexistent knowledge to find synonyms or related words but it remains difficult to select the right information. For instance, the noun care has 6 registered meanings in WordNet 1.6 [START_REF] Fellbaum | WordNet: an electronic lexical database[END_REF]. If we are interested in medicine practice, we do not want to retrieve documents that use the word care with its 4th sense ("a cause to feeling concerned"), but maybe only those that use it with its first sense: "the work of caring for […] someone […]". Our conclusion after these statements is that a general ontology or classification seeking for universality is an utopia and principally because of the word polysemy. So, the terminological aspect of general language has to be modeled by multiple overlapping classifications. The question we have to ask is then: "how can these classifications be acquired". We make three hypotheses. Firstly, at least a part of the semantic knowledge is encoded in the texts. Secondly, a part of this text-encoded knowledge can be automatically extracted and lastly, this extraction will be feasible only if semantics is considered in fine-grained contexts. Work has been done during previous decades on general language but the encoding was mainly manual, as for scripts of Schank (Schank, 1982) that were defined for storing semantico-pragmatic representations of everyday situations. It has been proved very difficult to extend the scripts beyond the first few ones. Another example of manually encoded semantic knowledge is CYC (Lenat, 1986) that is supposed to be a universal semantic knowledge base. In reality, CYC has to be manually tuned in each application it is used in. On the contrary, various methods have been used with success to acquire semantic knowledge on specialized domains: cooccurrences statistics [START_REF] Zernik | TRAIN2: Tagging Word Senses in Corpus[END_REF], distributional approaches following Harris ideas [START_REF] Harris | Mathematical Structures of Language[END_REF], classification techniques [START_REF] Grau | Semantic feature extraction from technical texts with limited human intervention[END_REF], linguistic indices [START_REF] Roark | Noun-phrase co-occurrence statistics for semi-automatic semantic lexicon construction[END_REF], etc. Our interrogation was on the possibility of adapting these successful techniques to general language. Our proposition is to determinate automatically thematic domains and to apply a classical distributional method on texts belonging to a same domain. This approach allows our system to form classes of semantically close words. The idea behind the distributional method is that the usage of a verb is directed by its sub-categorization frame. This frame specifies for example that the subject of the verb should be an instance of a particular concept. The set of real objects referred to by the words that are subjects of the verb in a particular domain represent this concept by extension. Thus, a description of this extension is the set of words used to refer to these objects. These sets of words are the semantic classes made by our system, SVETLAN'. We will show how these classes can be used to expand requests, in comparison with an expansion realized by using WordNet.

Overview of the system

Input data of SVETLAN' (see Fig. 1) are semantic domains with the thematic units (TUs) that have given birth to them. Domains are sets of weighted words, relevant to represent a same specific topic. These domains are automatically learned by ROSA that aggregates similar thematic units, made of sets of words. TUs are built by a topic segmentation process relying on lexical cohesion. It processes texts such as newspaper articles. The first step of SVETLAN' consists of a syntactic parsing of the corpus in order to produce the structured thematic units (STUs) corresponding to each TU. STUs are constituted by a set of triples -a verb, the head noun of a phrase and its syntactic role -extracted from the parser results. The STUs related to a same semantic domain are aggregated altogether to learn a structured domain. Aggregation leads to group nouns playing the same syntactic role with a verb in order to form classes. As these aggregations are made within STUs belonging to a same domain, classes are context sensitive, which ensures a better homogeneity. A filtering step, based on the weights of the words in their domain allows the system to eliminate nouns from classes when they are not very relevant in this context. We only give here a brief overview of the system that is made of two modules, SEGCOHLEX and SEGAPSITH. It is described more precisely in [START_REF] Ferret | A Thematic Segmentation Procedure for Extracting Semantic Domains from Texts[END_REF]. ROSA incrementally builds topic representations, made of weighted words, from discourse segments delimited by SEGCOHLEX [START_REF] Ferret | How to thematically segment texts by using lexical cohesion[END_REF]. It works without any a priori classification or hand-coded pieces of knowledge. Processed texts are typically newspaper articles coming from the Los Angeles Times. They are pre-processed to only keep their lemmatized content words (adjectives, single or compound nouns and verbs). The topic segmentation implemented by SEGCOHLEX is based on a large collocation network, built from 24 months of the Los Angeles Times newspaper, where a link between two words aims at capturing semantic and pragmatic relations between them. The strength of such a link is evaluated by the mutual information between its two words. The segmentation process relies on these links for computing a cohesion value for each position of a text. It assumes that a discourse segment is a part of text whose words refer to the same topic, that is, words are strongly linked to each other in the collocation network and yield a high cohesion value. On the contrary, low cohesion values indicate topic shifts. After delimiting segments by an automatic analysis of the cohesion graph, only highly cohesive segments, named thematic units (TUs), are kept to learn topic representations. This segmentation method entails a text to be decomposed in small thematic units, whose size is equivalent to a paragraph. As discourse segments, even related to the same topic, often develop different points of view of this topic, we enrich the particular description given by a text. We add to the TUs those words of the collocation network that are particularly linked to the words found in the corresponding segment. Learning a complete description of a topic consists of merging all successive points of view, i.e. similar TUs, into a single memorized thematic unit, called a semantic domain. Each aggregation of a new TU increases the system's knowledge about one topic by reinforcing recurrent words and adding new ones. Weights on words represent the importance of each word relative to the topic and are computed from the number of occurrences of these words in the TUs (see Figure 2 for an example of domain). This method, implemented in SEGAPSITH, leads to learn specific topic representations as opposed to [START_REF] Lin | Robust Automated Topic Identification[END_REF] for example whose method builds general topic descriptions as for economy, sport, etc.

Semantic Domain Structuring

Semantic domains are similar to classes formed by [START_REF] Zernik | TRAIN2: Tagging Word Senses in Corpus[END_REF]. SVETLAN' purpose is then to delimit small classes inside these domains, and to associate them to the verbs they define, as it is made in distributional approaches [START_REF] Faure | Learning subcategorization frames and restrictions of selection[END_REF]) [START_REF] Pereira | Distributional clustering of english words[END_REF]. A class is defined by those nouns which play a same role relative to a same verb and that are supposed to be connected by a strong semantic link. Thus, even if they do not denote a same object, the objects denoted by them play a similar role in the tight context defined by the semantic domain.

Formation of The Structured Thematic Units

A syntactic parser processes texts in order to find the verbs and their arguments. For English, we used the link grammar [START_REF] Grinberg | A robust parsing algorithm for link grammars[END_REF]. The system extracts all the triples found by the analyzer, constituted by a verb, a syntactic relation and the head noun of the noun phrase.

Relations are subject, direct and indirect objects, the preposition that introduces a prepositional phrase. The link grammar only gives one interpretation of the sentence.

After parsing the texts, SVETLAN' groups the triples relatively to the delimited thematic units. So, we define a structured thematic unit as a set of <Verb syntactic relation Noun> structures, i.e. a syntactic relation instantiated with a verb and a noun. We will refer to these structures as instantiated syntactic relations.

Aggregation

Structured thematic units related to a same domain are aggregated altogether to form the structured domains. Aggregating a structured thematic unit within a structured domain consists of: aggregating the instantiated syntactic relations that contain the same relation and the same verb, i. e. associating a set of words to an argument of a verb; adding new instantiated syntactic relations, i.e. adding new verbs with their arguments made of a syntactic relation and the lemmatized form of a noun. Nouns are not weighted inside a class; they only keep the weight they had in their semantic domain. Thus, the criterion to define a class is that words appear with a same verb, in similar contexts. The similarity of contexts is a lexical similarity computed on the whole domain.

Results

Classes are built according to two levels of contextual use of the words: a global similarity of the thematic contexts and a local relevance inside a domain we added to discard irrelevant words. In order to illustrate the effect of topic similarity when building classes, we show in figure 3 a class regrouping all the direct objects found for the verb to replace in the whole corpus. We can see that there is no semantic proximity between those nouns. When the class is formed inside a nuclear domain for the same verb, the class is then homogeneous. So, even general verbs, as to replace (it is possible to replace a lot of things), are relevant criteria to group nouns when their appear in similar thematic units. However, classes of nouns contain a lot of words that disturb their homogeneity. These words often belong to parts of the different TUs at the origin of the semantic domain that are not very related to the described topic.

They correspond to meanings of words scarcely used in the current context. As these words are weekly weighted in the corresponding domains, the data can be filtered: each noun that possesses a weight lower than a threshold is removed from the class. By this selection, we reinforce learning classes of words according to their contextual use. Figure 4 shows two aggregated links obtained without filtering in its upper part and the filtered counterparts in its lower part. The link for the verb 'to establish' has been completely removed while the link of the verb 'to answer' with the preposition 'to' has been reduced by the removing of 'list'.

Figure 5 shows some examples of classes obtained by SVETLAN'. Even when verbs are polysemous, which is the case for several verbs in the examples, the domain membership constraint leads the system to build relevant classes. We also can see that all the syntactic relations are relevant criteria to gather semantically linked words. This kind of knowledge is a first step towards schema representation of pragmatic knowledge. Such an example is given in Figure 6.

Experiments

Corpus Characteristics

We conducted an experiment with a corpus of English newspaper articles composed of 3 months of the "Los Angeles Times" newspaper. We used the following experimental settings: segmentation of the corpus and creation of the thematic memory (i.e. the set of semantic domains); syntactic analysis and syntactic links extraction; structured memory creation (i.e. the set of structured domains); and lastly, an evaluation of the results. We first counted the number of correct classes. A correct class is one that contains words sharing a direct semantic link. For the wrong classes, we counted the number of errors due to parse errors.

For our experiment, we only keep the TUs that lead to build stable domains, i.e. domains grouping at least 10 TUs.

The corpus we worked on is unanalyzed and SGML encoded. Its language level is high with a journalistic style and it tackles various topics. The size of corpus is 7.3 million words.

Results

The thematic memory created contains 138 stable domains. Figure 9 shows some examples of the classes contained in a structured domain whose topic is medicine.

Verb Rel on Class

To take Under Home, residence In such a case, it would be difficult to obtain a correct expansion by using only WordNet. However, one can imagine using SVETLAN' knowledge to select a meaning in WordNet.

Related Works

There is a lot of works dedicated to the formation of classes of words. These classes have very various statuses. They can contain words belonging to the same semantic field or near synonymous. Automatic systems apply different criteria to group words, but all make use of a context notion or a proximity measure. IMToolset, by Uri Zernik [START_REF] Zernik | TRAIN2: Tagging Word Senses in Corpus[END_REF], cluster local contexts of a studied word that is defined by the 10 words surrounding it in the texts. The proximity between words is evaluated by using the mutual information measure, as we do when segmenting the text. The result is groups of words that are similar to our domains but more focused on the sense of a word alone. Faure and Nedellec [START_REF] Faure | Learning subcategorization frames and restrictions of selection[END_REF] with Asium, or Lin [START_REF] Lin | Automatic retrieval and clustering of similar words[END_REF] apply distributional approaches to learn classes. Asium was designed to build ontology of specialized domains, so there is not a context restriction. Its basic classes are clustered to create ontology by the mean of a cooperative learning algorithm. This manual cooperative part is a step analogous to our filtering step. Lin does not apply a contextual selection of the words before regrouping them; he defined a similarity measure between words of a same class to order them according to their similarity degree, This kind of method also lead to build large classes, analogous to our semantic domains.

Conclusion and Future Work

The system SVETLAN' we propose, in conjunction with SEGAPSITH and a syntactic parser, extracts classes of words from raw texts and structures domains made of bags of words. These classes are created by the gathering of nouns appearing with the same syntactic role after the same verb inside a context. This context is made by the aggregation of text segments referring to similar subjects. Our experiments on different corpus give good enough results, but they also confirm that a great volume of data is necessary in order to extract a large quantity of lexical knowledge by the analysis of syntactic distributions.

In order to show the interest of building small classes inside larger domains, we made some request expansions that comfort the real proximity between words in the classes and their interest for specializing a request. We are now studying how this expansion can be used in a question-answering system [START_REF] Ferret | Terminological variants for document selection and Question/Answer matching[END_REF]) developed in the group that participated to the TREC evaluations.

This task is open domain and when the answer is not expressed with the same words as the question, it requires finding exact synonyms in text sentences. A first step consists of augmenting our base, then trying to use WordNet in conjunction with SVETLAN': a synonym in WordNet would be selected if it occurs in a class of SVETLAN' or in classes very close each others. As SVETLAN' classes do not only contain synonyms, the classes are not sufficient in this case, while with WordNet it would be a very sure criterion to obtain synonyms in a specified context We have to verify that it will be applicable on a large scale. Another possible evaluation is to use expansion in a more classical information retrieval task.

  Figure 1. Schemata of Structured Domain learning

Figure 3 .

 3 Figure 3. The effect of the thematic context on the kind of classes

Figure 4 .

 4 Figure 4. Two filtered classes in a domain about nuclear weapons

Figure 6 .

 6 Figure 6. Example of verbs with classes defining their arguments in a domain about justice However results of SVETLAN' are not only the constitution of classes, but also the structuring of semantic domain. Instead of bag of words, they are now described by verbs associated to classes defining their arguments.This kind of knowledge is a first step towards schema representation of pragmatic knowledge. Such an example is given in Figure6.

  Meanwhile, in the same structured domain, there were other classes containing the word care, some of them carrying the same meaning as care considered as a treatment. So classes do not partition the words of the domains, and they also do not partition the meanings of the words. In a further step, we will study if it is possible and suitable to merge the closest classes.We were interested in knowing which effects are produced by using different sorts of knowledge in request expansion. Thus, we did some preliminary experiments. Given a request made of words, we tried two kinds of expansion. One kind exploited the acquired classes and the other WordNet. WordNet is a lexical database made by lexicographers. It aims at representing the sense of the bigger part of the lexicon. It is composed of Synsets. A Synset is a set of words that are synonymous. These Synsets are linked by IS-A relations. First, we selected the closest domain from the request words. Different expansions where computed by adding the words that were belonging to the class of a word of the initial request, and this for each word of the request belonging to a class in the selected domain. By this way, expansion is done relatively to the domain of reference. Another expansion might be done from a same word, as soon as the other words of the request differ and refer to another context. The requests were sent on Google, that only considers the first 10 words.We can see that expansions along the WordNet synonyms of some words do not lead to a successful research, as for deliberation and obstruction. Another point concerns the number of documents that are returned. By WordNet expansions, there are much less relevant documents than by SVETLAN' expansions. An explication of this result comes from the fact that SVETLAN's added words are much more related to the request than those added via WordNet. It is due to the contextual construction of the classes and also to the fact that the context is explicitly represented by domains and so can be used to guide the choice of words, contrarily to a general database as WordNet. WordNet coverage is large but this quality is, in a sense, its default. Indeed, the generality of its contents makes it difficult to use in real sized applications that are often centered on a domain. It rarely can be used without a lot of manual adaptation. We are now showing another example, in the sport domain. SVETLAN' added words that all belong to the baseball domain.

	4 senses of obstruction
	Sense 1 :obstruction, impediment, impedimenta
	=> structure, construction
	Sense 2: obstacle, obstruction
	=> hindrance, deterrent, impediment, handicap
	Sense 3: obstruction
	=> hindrance, interference, interfering
	Sense 4: obstruction	Number	Correct Syntactic Parser Errors Other
	=> maneuver, manoeuvre, play	149	58 %	7 %	35 %
	Initial request : prosecutor obstruction deliberation jury	Figure 10. Results on English with a 0.1 threshold
	WordNet expansion 2: prosecutor obstruction
	deliberation jury, impediment, impedimenta, structure, construction, obstacle, hindrance, deterrent, handicap,		7 Request Expansion
	interference, interfering
	=> No answer
	WordNet expansion 2bis: prosecutor obstruction
	deliberation jury, impediment, impedimenta, obstacle	Initial request: starter hitter batter : 14900 answers
	=> No answer	Svetlan'A expansion: starter hitter batter run hit game
		inning pitch season home
	5 senses of deliberation	=> 7660 answers
	Sense 1: deliberation
	=> discussion, give-and-take, word	In WordNet, starter and batter are very polysemous words.
	Sense 2: deliberation, weighing, advisement
	=> consideration	5 senses of starter
	Sense 3: calculation, deliberation	Sense 1: starter
	=> planning, preparation, provision	=> electric motor
	Sense 4: slowness, deliberation, deliberateness,	Sense 2: starter
	unhurriedness	=> contestant
	=> pace, rate	Sense 3: starter, dispatcher
	Sense 5: deliberation, deliberateness	=> official
	=> thoughtfulness	Sense 4: newcomer, fledgling, fledgeling, starter,
		neophyte, freshman, entrant
	Initial request : prosecutor obstruction deliberation jury	=> novice, beginner, tyro, tiro, initiate
	WordNet expansion 3: prosecutor obstruction	Sense 5: crank, starter
	deliberation jury, discussion, give-and-take, word, weighing, advisement, consideration, calculation, planning, preparation, provision, slowness, deliberateness, unhurriedness, thoughtfulness => No answer WordNet expansion 3bis: prosecutor obstruction deliberation jury, weighing, advisement, calculation, slowness, deliberateness, unhurriedness	=> hand tool Initial request : prosecutor obstruction deliberation jury SVETLAN' request expansion 1: prosecutor obstruction 1 sense of hitter deliberation jury charge case court trial attorney count Sense 1: batter, hitter, slugger, batsman => 141 answers => ballplayer, baseball player SVETLAN' request expansion 2: prosecutor obstruction deliberation jury charge case court trial attorney sentence => 222 answers 2 senses of batter Sense 1: batter, hitter, slugger, batsman
	To meet To carry To get Figure 9. Examples of classes in a structured domain on Object Care, physician Object Virus, antibody English These examples show two classes with the word care. commission deliberation jury, discussion, body, committee, WordNet expansion 4: prosecutor obstruction Initial request : prosecutor obstruction deliberation jury Subject Treatment, care => No answer => committee, commission Sense 2: jury, panel => body Sense 1: jury 2 senses of jury	=> lawyer, attorney attorney Sense 1: prosecutor, prosecuting officer, prosecuting 1 sense of prosecutor => ballplayer, baseball player When using WordNet, we retrieved the different meanings Sense 2: batter of each word -first, all its synonyms and its hypernyms the following request expansions. to a class. Thus for the same initial request, we obtained sets to the initial request. A set was considered equivalent and second, only the synonyms -and add each of these => concoction, mixture, intermixture
	=> 84 answers	Initial request : prosecutor obstruction deliberation jury
		WordNet expansion 1: prosecutor obstruction
		deliberation jury, prosecuting officer, prosecuting
		attorney, lawyer, attorney
		=> 65 answers

They instantiate two different kinds of semantic relation: in the class <care, treatment> we see an instrument link between the two terms of the class (a treatment is a means to take care of a patient) and in the class <care, physician>, the link is an agent one (the physician take care of his patients).