Päivi Heikkilä

Hanna Lammi

Marketta Niemelä

Kathleen Belhassein

Guillaume Sarthou

Antti Tammela

Aurélie Clodic

Rachid Alami

Keywords: Shopping mall robot, Robot guidance, Design implications, Multi-phased study, Social robots

Providing guidance to customers in a shopping mall is a suitable task for a social service robot. To be useful for customers, the guidance needs to be intuitive and effective. We conducted a four-phase qualitative study to explore what kind of guidance customers need in a shopping mall, which characteristics make human guidance intuitive and effective there, and what aspects of the guidance should be applied to a social robot. We first interviewed staff working at the information booth of a shopping mall and videotaped demonstrated guidance situations. In a human-human guidance study, ten students conducted seven way-finding tasks each to ask guidance from a human guide. We replicated the study setup to study guidance situations with a social service robot with eight students and four tasks. The robot was controlled using Wizard of Oz technique. The characteristics that make human guidance intuitive and effective, such as estimation of the distance to the destination, appropriate use of landmarks and pointing gestures, appear to have the same impact when a humanoid robot gives the guidance. Based on the results, we identified nine design implications for a social guidance robot in a shopping mall.

Should a robot guide like a human? A qualitative four-phase study of a shopping mall robot 1 Introduction

Providing information and guidance is a suitable task to a social service robot in a public place such as a shopping mall [START_REF] Satake | What should we know to develop an information robot[END_REF]. Various robots have been tested in offering guidance to mall or store visitors either by route explanation and pointing, or escorting the customer to the target location [START_REF] Brscic | Do you need help? a robot providing information to people who behave atypically[END_REF], [START_REF] Díaz | A week-long study on robot-visitors spatial relationships during guidance in a sciences museum[END_REF], [START_REF] Gross | TOOMAS: Interactive shopping guide robots in everyday use -final implementation and experiences from long-term field trials[END_REF], [START_REF] Kanda | A Communication Robot in a Shopping Mall[END_REF], [START_REF] Triebel | SPENCER: A Socially Aware Service Robot for Passenger Guidance and Help in Busy Airports[END_REF], [START_REF] Clodic | Rackham: An Interactive Robot-Guide[END_REF]. Guidance is one of the most desired task for a robot among shopping mall customers and even mall managers, who are aware of the customers challenges in way-finding in their malls [START_REF] Niemelä | A social robot in a shopping mall: studies on acceptance and stakeholder expectations[END_REF], [START_REF] Satake | What should we know to develop an information robot[END_REF]. As a guidance facility, compared to mall maps, a robot has some clear advantages. It is a physical device able to move in the same space as humans, and humanoid robots have bodily characteristics that are intuitive to understand by humans: "A robot can naturally explain a route by pointing like a human, looking in the same direction as the person is looking, and using such reference terms as 'this way.' " [START_REF] Kanda | A Communication Robot in a Shopping Mall[END_REF].

Robot guidance as a form of social interaction between a robot and a human has not been studied much. This is related to perceived usefulness and usability of the robot but also to how the robot should behave in its role as a guide. For instance, in our earlier workshop with shopping mall customers one finding was that a mall robot should not behave as if it was in the position of a human. The robot should not refer to itself as human, for instance, saying "in my view" or "personally I think" [START_REF] Niemelä | A social robot in a shopping mall: studies on acceptance and stakeholder expectations[END_REF]. But to what extent a robot guide should mimic a human guide, and how do people perceive a robot as a guide?

In this paper, we report a four-phase study of human guidance and robot guidance. The aim of the study was to understand how a humanoid robot should give guidance in an intuitive and effective way in a shopping mall. We studied this by first gaining understanding of the effective ways to give guidance by human guides and applied the results to guidance behavior of a humanoid robot. Our study questions are:

1. What characteristics of human guidance should be applied to a humanoid robot? 2. What are the design implications for guidance behavior for a social robot?

The study was part of the Multi-Modal Mall Entertainment Robot (MuM-MER) project, which develops a socially interactive shopping mall robot with Softbank Robotics Pepper as the robot platform [START_REF] Foster | The MuMMER Project: Engaging Human-Robot Interaction in Real-World Public Spaces[END_REF]. The robot is intended to provide customer service that complements and extends the current info booth service (i.e. guidance, information and entertainment service). The projects main study site is a large shopping mall Ideapark approximately 30 km from one of the largest cities in Finland. The mall consists of approx. 200 shops and stores of mainly fashion and leisure equipment. The customers are of all ages from families to older adults. In 2018, there were more than 19 000 visitors per day in the mall in average1 .

Related work

In the literature, providing guidance is defined as a particular kind of spatial description called "route description" or "route directions". [START_REF] Kopp | Trading Spaces: How Humans and Humanoids Use Speech and Gesture to Give Directions[END_REF] defined it as a set of routes segment, each connecting two important points and explained in a chronological way. The way in which humans communicate spatial knowledge through the route description has been extensively studied both verbally and textually. This has allowed identifying invariants as well as good practices to ensure the success of the task in both urban and interior environments. Through five experiments, Allen [START_REF] Allen | Principles and practices for communicating route knowledge[END_REF] identified three basic practices as important for communicating knowledge about routes. They can be summarized as follows: a) respect the spatiotemporal order, b) concentrate on the information about the points of choice and c) use landmarks that the listener can easily identify. This use of reference marks has been called critical information by Tversky in [START_REF] Tversky | Pictorial and Verbal Tools for Conveying Routes[END_REF] after highlighting that 91% of the guidance contains additional information (landmarks) to the only actions of reorientation and directions [START_REF] Tversky | How Space Structures Language[END_REF], which confirms the results of [START_REF] Denis | The description of routes: A cognitive approach to the production of spatial discourse[END_REF]. Using the terms of [START_REF] Montello | Scale and multiple psychologies of space[END_REF], guides usually used landmarks when the target places were no longer in the V ista place (being within sight) but in the Environmental space (being reachable through locomotion). In accordance with [START_REF] Tversky | Pictorial and Verbal Tools for Conveying Routes[END_REF], using landmarks typically occurs when the explained action is a change of direction. In addition, the importance of landmarks and their choice based on salient features during a route description is described in [START_REF] Nothegger | Selection of Salient Features for Route Directions[END_REF].

The choice of the route to explain may have an impact on its understanding and memorization: Morales in [START_REF] Morales | Building a Model of the Environment from a Route Perspective for HumanRobot Interaction[END_REF] argued that the choice is based more on its complexity (the number of stages that compose it) than on its length. The types and frequency of gestures used during route descriptions have been studied in [START_REF] Allen | Gestures accompanying verbal route directions: do they point to a new avenue for examining spatial representation?[END_REF]: pointing gestures have been found more frequent than other types of gestures, and their stages to be successful have been highlighted by [START_REF] Wong | Where are you pointing? the accuracy of deictic pointing in CVEs[END_REF] in the context of collaborative virtual environments.

Many robot guides have been developed based on guidance tasks in a shopping mall. [START_REF] Kanda | A Communication Robot in a Shopping Mall[END_REF] focused on aspects of communication, including user recognition and dialogue history. [START_REF] Okuno | Providing route directions: design of robot's utterance, gesture, and timing[END_REF] used a "skeletal" description containing minimal information sets and chose to use only deictic gestures because of their clarity. [START_REF] Satake | What should we know to develop an information robot[END_REF] were interested in the types of questions asked from a robot guide and in the data needed to answer these questions. They also focused on engagement and the reasons why interaction between a human and a robot guide might not start.

Methods and participants

The research consisted of four parts carried out during the research project (2016-2018, Fig. 1): a preliminary interview, a pilot study on human guidance giving, a human-human guidance study and a robot-human guidance study.

First, the preliminary one-hour interview was conducted with a person working at the information booth of the shopping mall to understand what kind of guidance related questions customers ask and how the information workers give guidance. We arranged the interview at the information booth and focused on typical questions from customers and challenging places to guide. We also observed two real situations of guidance giving during the interview. Based on this data, we generated and carried out five example guidance-giving situations and video recorded them.

Second, we carried out a pilot study on human guidance giving in a future location of the mall robot [START_REF] Belhassein | Human-Human Guidance Study[END_REF]. Based on the preliminary interview, we created a list of 15 locations and items to buy that customers typically ask for receiving guidance and which are located in different parts of the mall. Two researchers asked the questions of two persons working at the information booth, who were instructed to give guidance as they would normally do. The situations were video recorded and the guides were briefly interviewed after the sessions.

Third, the human-human guidance study was conducted with 10 volunteer student participants who were not very familiar with the venue. Each participant completed seven way-finding tasks based on the preliminary interviews. The tasks included only locations (e.g. a pharmacy) or a product to buy (e.g. a suitcase), and the participants asked them with their own words. They were also encouraged to ask clarification or further guidance if needed. The tasks included:

1. an easy warm-up task 2. a complex location to guide 3. a product that can be found in several shops 4. two locations in the same question 5. two persons asking guidance to find a place to have lunch together 6. one participant asking guidance and another one interrupting 7. any location or item that participants wanted to ask (preferably according to their real needs if any).

After asking guidance, the participants went to the actual locations and took a photo of the location. We interviewed the participants briefly between the tasks and checked the photos to validate whether they had found the right place. In addition, they all participated in a short individual interview at the end of the study session. After the session, we had a group discussion and revealed them the purpose of the study. They had an opportunity to ask further questions and share their feelings about having a social robot as a guide in the mall. The same person working at the information booth of the shopping mall acted as a guide in all of the sessions. She was asked to give guidance the same way as in typical customer service situation. The sessions were audio recorded and videotaped. Fourth, the robot-human guidance study replicated the study setting of a human-human guidance study in a slightly smaller scale with 8 volunteer students and 4 guidance tasks for each participant. The tasks were similar to the first four tasks of the human-human study. The findings of the earlier study were used in designing the guidance behavior (dialogues and gestures) for the robot. In addition, as part of the dialogue, we tested how participants reacted to personal greetings, e.g. "How has your morning been?". We chose Wizard of Oz (WOz) technique to control the robot, as an autonomous version that is developed in the research project was not yet stable enough to be used. The wizard was an experienced researcher who stood two meters away from the robot partly behind a pillar and posters covering the computer, not to be too visible to the participants. He controlled the robot to turn, point into appropriate directions and respond with ready-made parts of a dialogue with shortcuts in a WOz interface. In addition, he could write short free-form sentences for the robot to say aloud. Similar to the human-human study, the participants went to the actual locations and took a photo of the location. They were interviewed briefly between the tasks and as a group in the end of the study session. The WOz set-up was revealed to them only after the study. The WOz simulation was found convincing by the participants as none of them had realized the human wizard.

The student participants were recruited through university student email lists and they represented different fields of studies. Most of them had visited the shopping mall a couple of times. Participants who had visited the shopping mall more than once a month were not included. In the human-human study, 6/10 of the participants were female with the mean age of 29 years, ranging from 21 years to 41 years. In the robot-human study 5/8 of the participants were female with the mean age of 34 years, ranging from 24 years to 61 years. The four persons working at the information booth who participated in the first three phases of the study were female and had worked in the mall from a few months to six years.

The study was carried out in compliance with the EU General Data Protection Regulation (GDPR). All participants filled in an informed consent form before participation. The participants were reimbursed with two movie tickets.

The data of the parts of the study were analyzed qualitatively. In this paper, we focus mainly on the data of the interviews. Based on the analysis, we propose design implications for guidance behavior of a social robot.

Results

Effective human guidance

According to preliminary interviews, typical guidance related questions include specific shops, items to buy, type of the shops (e.g. shoe shops) and recommendations, especially for restaurants. The staff giving guidance highlighted that equality between shops is very important for them, and thus they aim at telling the customer all the options (e.g. all four shoe shops and shops including shoes) or asking further questions of the needs or preferences of the customer (e.g. what kind of food would you like to have for lunch). They do not give direct recommendations, even though they had personal favorites. In addition, they never say that they do not know the response, but always try to help the customer.

The human-human guidance study revealed means to give guidance in an intuitive and effective way. Even though we designed the guidance tasks to be challenging locations, the participants found all locations according to the guidance given to them. Only one task was such that one of the participants did not find the place easily and needed to use the information board of the shopping center to get further guidance to the location. He was confused because the guide told him the instructions without emphasizing that the location was very close.

Even though the participants found the places relatively easily, the interviews revealed aspects that helped them recalling the instructions or feeling sure that they are on the right route to the location. This was important especially in cases when the location was far away. In general, the participants appreciated short instructions with clear structure accompanied with gestures for pointing the main directions. When the guide gave an estimation of the distance to the location, such as it locating very near or in the very end of the corridor, the participants felt themselves more confident in finding the place. In the cases when they had received instructions to two locations at once, the pointed directions and rough estimations of the distance helped them to recall the instructions to the second location. The instructions were easier to recall, if the guide had used an expression that connected the places together, such as the other destination being located in the totally opposite direction than the first one.

For the places not in sight, the guides typically used landmarks to make the destination and the turnings needed easier to locate. For example, a particular cafe was regularly used as a landmark because it was located at a crossing of two aisles. These results confirm what was highlighted by [START_REF] Tversky | How Space Structures Language[END_REF]. The most effective landmarks for the participants were familiar brands having clear signs, confirming the salient features as criteria presented by [START_REF] Nothegger | Selection of Salient Features for Route Directions[END_REF]. One or two landmarks in one guidance dialogue seemed to be a maximum number to be easily recalled.

Characteristics of human guidance applied to a social robot

Based on the results related to effective human guidance, we designed the guidance behavior of the robot to include characteristics that helped the participants to recall the guidance instructions and find the places easily. To make the guidance feel intuitive, we followed the typical structure of giving guidance that the guiding personnel used. One of the guides had a pattern to repeat the location that was asked by the customer first, and we adopted the same confirmation for our robot. In case of a robot, it is crucial that the customer knows that the robot has recognized the destination asked. After that, the robot was designed to give a general remark of the destination first (e.g. it is very close). We regarded this as important for the robot, to give a customer an overall image of the destination first and thus a possibility to orientate to the exact directions.

In the robot-human study, the same characteristics that helped the customers when they were interacting with human guide were found effective also with a robot guide. The participants found the pointing gestures particularly helpful. Similar to the interaction with a human guide, they valued short and structured instructions, estimation of the distance to the destination, and appropriate use of landmarks.

The differences to a human guide were not found in the guidance itself, but in the small talk before that. All the participants liked the polite and friendly greetings and way of talking of the robot. They commented that they liked the way the robot looked at them, which made them feel that it is focusing on them and ready to help. However, some felt awkward if the robot asked a personal question in the start of the interaction, such as "How has your morning been?" One participant commented that it feels stupid to tell about your day to a robot, because a robot cannot be truly interested in that.

In general, the participants felt communication with the robot rather natural. The robot initiating the interaction made the situation feel natural and the robot repeating the asked destination confirmed that the robot has understood the questions correctly. The only problems were related to the WOz setup. As the researcher controlling the robot needed to simultaneously manage several aspects of the communication (such as the parts of each guidance dialogue and pointing of directions), the communication was not perfectly smooth and unintentional breaks occurred during the guidance. This made it more difficult for participants to follow the instructions and also know when the interaction ended.

Human-like gestures and way of communication was liked, but a couple of participants commented that besides giving guidance like a human, the robot could use its robotic features and abilities. Unlike a human, a robot could give for example an exact distance to the destination or it could use the tablet in complementing its speech. Naturally, exact distances or tablet use could also confuse users and should be tested before adoption.

Design implications for guidance behavior of a social robot

Based on the results of our multi-phased study, we propose nine implications for designing the guidance behavior of a social robot.

1. Help to start the interaction: Use speech and gaze to receive the attention of the user. Start interaction by friendly greeting and offering help. 2. Confirm the asked location: Before giving guidance, ensure that the request is understood. 3. Give short instructions: Short instructions are easier to understand and recall. 4. Have a clear structure of the instructions with natural rhythm of speech: Clearly structured instructions without long breaks or too fast proceeding help following the instructions and recalling the main points later. 5. Inform distance to the asked location: Give an overall image of the location with an estimation whether it is close or further away. 6. Use gestures (pointing at directions): Helps both initial understanding and recalling the instructions later. 7. Use landmarks when appropriate: Salient landmarks as well as ones located in the crossings of aisles are helpful. However, include only 1-2 landmarks in one guidance case.

8. Ensure equality between retails: Instead of personal recommendation, try finding out the preferences of the customer. 9. Stay flexible: Give the customer a possibility to ask for repeating an instruction or to interrupt the situation. When the response includes several options, the customer should be able to ask further questions (e.g. which is the closest option). If the robot cannot answer a question, it could advice the customer to continue the case with the personnel of the mall.

Discussion

The aim of our research was to find out how we should design a social service robot to give guidance in an intuitive and effective way in a shopping mall. Based on our multi-phased study, we identified design implications and explored whether a humanoid robot should guide like a human. According to our results, the participants felt human-like guidance behavior intuitive and the characteristics used by a human guide were effective in robothuman interaction. Our findings are in line with the principles introduced by Allen [START_REF] Allen | Principles and practices for communicating route knowledge[END_REF], emphasizing the clear structure of guidance as well as a chose of landmarks so that the customer can find the points of interest quickly and easily. Thus, the requirements and expectations of a route description by a robot do not seem to differ from a human-human guidance. However, asking additional personal questions ("How your morning has been?") was felt suitable for a human only. It seems that even though the structure of the communication and the aspects of making the guidance easy to understand and recall, seem to be applicable to humanoid robots, the robot should not pretend to be a human or replicate the human behavior besides functional aspects of it. This supports our earlier findings that a mall robot should not behave as if it were in the position of a human [START_REF] Niemelä | A social robot in a shopping mall: studies on acceptance and stakeholder expectations[END_REF]. However, the result might be different in a study that would focus on e.g. free communication with a robot instead of functional task, such as guidance.

The limitations of this study include a small sample size and practical problems with the WOz setup. External validity is high as the guidance studies were carried out in the field, in an actual shopping mall with realistic way-finding tasks. However, the results cannot be directly generalized to all customer groups or other shopping malls. The participants were students, who do not make a representative sample of the mall customer population. For instance, student participants might have a more positive attitude towards a robot guide than the mall customers in average, which would make them willing to listen to the robots advice more carefully than an average customer would. In some earlier human-robot interaction studies in the MuMMER project, we have recruited participants in the field [START_REF] Niemelä | Monitoring the acceptance of a social service robot in a shopping mall: First results[END_REF]. However, this was not possible for this study due to the study setting, which required the participants to commit for 2-3 hours to the study. Therefore, we have to be cautious when drawing conclusions from the results. Furthermore, we assume the attitudes to the human-like behavior of robots to be strongly dependent on the cultural context, and thus it would be interesting to extend the study also to other cultures.

Our results have been used in developing software components for the robot that will be deployed in the shopping mall in the end of the research project. The components include software for route search and the guidance explanations generation [START_REF] Sarthou | Semantic spatial representation: a unique representation of an environment based on an ontology for robotic applications[END_REF] and planning of the positioning of the human and the robot so that they have a common perspective while pointing [START_REF] Waldhart | Planning Human and Robot Placements for Shared Visual Perspective[END_REF]. During the deployment, we will extend our research to more realistic guidance situations with the autonomous robot.

Conclusions

In this paper, we presented a four-phased qualitative study to explore which means make human guidance intuitive and effective, and whether the means have the same impact in guidance given by a humanoid service robot. We proposed nine design implications and discussed whether a robot should guide like a human. Our results give practical insights to human-robot interaction designers and contribute to the literature of robot guidance as a form of social interaction.

Fig. 1 .

 1 Fig. 1. The study was carried out in four phases during two years.

https://www.kauppakeskusyhdistys.fi/media/kauppakeskusjulkaisu/2018kauppakeskusjulkaisu.pdf (in Finnish).

Acknowledgements

We thank Olivier Canévet for creating a Wizard of Oz user interface which we used in this study and Petri Tikka for giving technical support. We also thank Ideapark for their cooperation and the volunteer participants of the study. This work has been supported by the European Union's Horizon 2020 research and innovation program under grant agreement No. 688147 (MuMMER project).


André Nel

Patrick Roques

Jakub Prokop

A new, extraordinary 'damselfly

Keywords: Odonatoptera, phylogeny, Moscovian, palaeoecology

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Patrick Roques [patrick.roques93@wanadoo.fr] allée des Myosotis, Neuilly sur Marne, F-93330, France.

Jakub Prokop [jprokop@natur.cuni.cz], Charles University, Faculty of Science, Department of Zoology, Viničná 7, Praha 2,Czech Republic. Enigmaptera magnifica gen. nov, sp. nov., type genus and species of the new odonatopteran family Enigmapteridae, is described from the Moscovian of Avion (North of France). It is the sister group of the major clade Neodonatoptera, together in the new clade Paneodonatoptera.

Its wing venation show important unique characters, never found in any other Odonatoptera.

It is a further case of convergent wing petiolation in this superorder. Enigmaptera magnifica, like the protozygopteran Jacquesoudardia magnifica from the same outcrop, was probably living like the extant damselflies along the shores of lakes and rivers, hunting the small insects found in the same layers. These discoveries put a new light on the entomofaunistic diversity and complexity of the Late Carboniferous ecosystems. Key words: Odonatoptera, fam., gen., sp. nov, phylogeny, Moscovian, palaeoecology. THE CARBONIFEROUS represents the first period of well-documented diversification of major lineages of winged insects in the fossil record [START_REF] Engel | Insect wings: the evolutionary development of Nature's first flyers[END_REF]. It is well-known for the numerous very large to 'giant' insects (the popular meganeurids or griffenflies). But small to very small insects were also flourishing during this period. The recently discovered outcrop at Avion in the department of Pas-de-Calais, is especially rich in small to very small wings mixed with thousands of plant fragments. It has led a very diverse entomofauna that comprises Palaeodictyoptera (including larvae), Archaeorthoptera, Caloneurodea, Paoliida, Dictyoptera, and the oldest representatives of the clades Acercaria and Holometabola [START_REF] Nel | The earliest-known holometabolous insects[END_REF], Prokop et al. 2013[START_REF] Prokop | New non-holometabolous insects from Pennsylvanian of Avion locality in Pas-de-Calais, France (Insecta: 'Exopterygota')[END_REF], Coty et al. 2014). It is dated to the Moscovian (Westphalian C/D or equivalent Bolsovian/Asturian). The fossil insects were found in 'Terril N 7', which contains rocks from the slag heap of coal mines 3 and 4 of Liévin, Bolsovian (Westphalian C, 308-311 Ma, 'faisceaux de Ernestine') /Asturian (Westphalian D, 306-308 Ma, 'veines Arago, Dusouich, Marthe';Bruno Vallois 2013 pers. comm.).

Here we describe a further very small wing that represents a new major clade of the superorder Odonatoptera. This wing is characterized by an extraordinary, unique pattern of wing venation. The Odonatoptera from Avion were already known by a Protozygoptera (Jacquesoudardia magnifica [START_REF] Prokop | New non-holometabolous insects from Pennsylvanian of Avion locality in Pas-de-Calais, France (Insecta: 'Exopterygota')[END_REF]) and a Meganeuridae (Gallotupus ourdardi [START_REF] Nel | A new griffenfly genus from the Late Carboniferous of northern France (Odonatoptera: Meganeuridae)[END_REF].

Materials and methods

The material was collected by Patrick Roques. The fossil is provisionally stored in the collection of the Laboratory of Entomology in the Muséum National d'Histoire Naturelle, Paris (MNHN), France. The collection will ultimately be deposited in the Musée Géologique Pierre Vetter, Decazeville, France. The fossil was studied in a dry state using Olympus SZX-9 and Nikon SMZ 1500 stereomicroscopes. Line drawings of the venation pattern was drawn directly with the aid of a camera lucida. Photographs were taken using a Canon D550 digital camera with MP-E 65mm and EF 50mm lenses. Original photographs were processed using the image-editing software Adobe Photoshop CS.

We mainly follow the wing venation nomenclature of Riek & Kukalová-Peck (1984), [START_REF] Nel | Les 'Anisozygoptera' fossiles. Phylogénie et classification (Odonata)[END_REF]Jacquelin et al. (2017). The venational symbols used here are specified as follows: symbols in capitals denote the longitudinal veins (Arc: 'arculus', Ax0: basal primary antenodal crossvein, ScA/ScP: subcostal anterior/posterior, RA/RP: radial anterior/posterior, IR: convex intercalary radial vein, MA/MP: medial anterior/posterior, CuA/CuP: cubital anterior/posterior, AA: anterior anal vein).

Systematic palaeontology

Class INSECTA Linnaeus 1758 Infraclass PALAEOPTERA Martynov 1923 Superorder ODONATOPTERA Martynov 1932 Clade PANEODONATOPTERA taxon nov.

Included taxon. The new family Enigmapteridae, and the Neodonatoptera [START_REF] Bechly | Morphologische Untersuchungen am Flügelgeäder der rezenten Libellen und deren Stammgruppenvertreter (Insecta; Pterygota; Odonata), unter besonderer Berücksichtigung der Phylogenetischen Systematik und des Grundplanes der *Odonata[END_REF] Etymology. Named in reference to the clade Eodonatoptera. Diagnosis. Very small wing, only 2.9 mm wide, and ca. 14 mm long.

Autapomorphies

Etymology. Named after the surprising and enigmatic wing venation of this taxon. Discussion. This small wing is remarkable in the presence of a point of fusion of R, MA and MP 2.3 mm from wing base, with an arculus just distal to this point. Enigmaptera gen. nov. can be attributed to the Odonatoptera Martynov, 1932 because it has the following synapomorphies: wings with relatively undeveloped anal area; MP unbranched; anal brace with a Z-like kink in CuP and in CuA at their points of fusion with AA; ScP fuses with the costal margin distinctly basal of wing apex [START_REF] Bechly | Morphologische Untersuchungen am Flügelgeäder der rezenten Libellen und deren Stammgruppenvertreter (Insecta; Pterygota; Odonata), unter besonderer Berücksichtigung der Phylogenetischen Systematik und des Grundplanes der *Odonata[END_REF]. Enigmaptera shares with the Palaeodonatoptera [START_REF] Petrulevičius | New basal Odonatoptera (Insecta) from the Lower Carboniferous (Serpukhovian) of Argentina[END_REF] Nevertheless, in Enigmaptera, MA is distinctly separated from MP at wing base but still not fused with R, a very particular situation present in Eugeroptera, the Kukaloptera, the Argentinalidae, and the Geropteridae [START_REF] Petrulevičius | New basal Odonatoptera (Insecta) from the Lower Carboniferous (Serpukhovian) of Argentina[END_REF], Jacquelin et al. 2017), but not in the Neodonatoptera in which MA is appressed or fused to R, even in the most 'basal' clade Eomeganisoptera Rohdendorf 1962(viz. Erasipteridae Carpenter 1939). Thus Enigmaptera corresponds to a completely new clade, sister group of the Neodonatoptera Enigmaptera is characterized by several autapomorphies: complete distal fusion of MP with R and MA, the strongly convex MA re-emerging from R in the arculus; very narrow wing, very narrow anal area, and very long RP1/2.

Enigmaptera magnifica

Palaeoecological inferences

The sub-petiolation of Enigmaptera is remarkable. Few Carboniferous petiolate wings of Odonatoptera are known, viz. the Protozygoptera Bechlyia Jarzembowski & Nel 2002 (Farrington Formation, Upper Westphalian D, Kasimovian, UK) and Jacquesoudardia (Avion), the meganisopteran Bechalidae (Bechala Ilger & Brauckmann 2012, Namurian, Germany) and the Meganeuridae Gallotupus ourdardi (which has a short petiole, also from Avion) (Jarzembowski & Nel 2002[START_REF] Nel | A new griffenfly genus from the Late Carboniferous of northern France (Odonatoptera: Meganeuridae)[END_REF][START_REF] Nel | Revision of Bechala sommeri Ilger and Brauckmann, 2012 from the early Late Carboniferous of Germany (Insecta: Odonatoptera: Bechalidae)[END_REF][START_REF] Prokop | New non-holometabolous insects from Pennsylvanian of Avion locality in Pas-de-Calais, France (Insecta: 'Exopterygota')[END_REF]. Enigmaptera is a further convergent case of 'long' petioles (longer than the width) occurring in Odonatoptera. The others concern the Protozygoptera (Late Carboniferous to Early Such small 'damselfly-like' Odonatoptera were probably living in close environments, hunting the small insects along the rivers or in forests, unlike the large to very large Meganisoptera, with wing span over 60 cm [START_REF] Nel | Revision of Permo-Carboniferous griffenflies (Insecta: Odonatoptera: Meganisoptera) based upon new species and redescription of selected poorly known taxa from Eurasia[END_REF].

  extraordinary 'damselfly-like' Odonatoptera from the Pennsylvanian of the Avion locality in Pas-de-Calais, France (Insecta: 'Exopterygota') ANDRE NEL, PATRICK ROQUES, JAKUB PROKOP and ROMAIN GARROUSTE André Nel, Romain Garrouste [anel@mnhn.fr; garroust@mnhn.fr], Institut Systématique Evolution Biodiversité (ISYEB), Muséum national d'Histoire naturelle, CNRS, Sorbonne Université, EPHE, 57 rue Cuvier, CP 50, 75005 Paris, France.

  sp. nov. (Figs. 1-2) Holotype. Specimen Avion 35 (counterimprint of basal half of a wing), collected by Patrick Roques; provisionally stored in the collection of the Entomological Laboratory, MNHN, Paris, France. The collection will be deposited in the Musée Géologique Pierre Vetter, Decazeville, France. Locality and age. Moscovian (Westphalian C/D equivalent to Bolsovian/Asturian), 'Terril N 7', Avion, Pas-de-Calais, France. Etymology. Named after the wonderful state of preservation of the preserved parts of this wing. Diagnosis. As for the genus. Description. Basal half of a wing, very well preserved, veins being with this normal convexity. Length of fragment 10.5 mm, width of wing 2.9 mm; C making a basal curve, no visible ScA nor Ax0; concave ScP straight, very long, progressively approximating C (width of area between C and ScP near wing base 0.45 mm, at distal part of fragment 0.1 mm), ScP ending on C at ca. 10.2 mm from wing base; six visible crossveins between C and ScP; convex R (distally RA) parallel to ScP, width of area between them 0.41 mm, with seven them; convex RA and concave RP separating at 2.4 mm from wing base (arculus); RP separating into RP1/2 and RP3/4 just distally; base of convex secondary longitudinal vein IR2 just distal of point of separation of RP into RP1/2 and RP3/4; RP1/2, IR2, RP3/4 straight, with few crossveins between them defining long rectangular cells; fork of RP1/2, if present, in a very distal position, distal of apex of ScP; MA convex, but weaker and less convex than R, closely parallel to it, ending in R 2.3 mm from wing base, at the same point with MP; basal free part of concave MP oblique between base of MA and Cu, 0.8 mm long, ending into Cu; basal free part of Cu 0.7 mm long; concave CuP separating from Cu 0.2 mm basal of point of fusion between MP and Cu, and ending into AA, a Z-like kink in CuP at point of fusion with AA; CuA separating from MP 0.3 mm distal of point of fusion of CuA with MP, a Z-like kink in CuA at point of fusion with AA; MP anteriorly curved and ending into R at the same point with MA; MA re-emerging from R at the same point with RP (arculus), very convex, 0.9 mm long before its fusion with CuA+CuP+AA; then MA very straight; convex AA straight, progressively diverging from posterior wing margin and ending into MA; area between AA and posterior wing margin very narrow, 0.4 mm at its maximum width, 0.05 mm wide near wing base.

  2016) divided the clade Palaeodonatoptera into the Kukaloptera Petrulevičius & Gutiérrez 2016 and Plesiodonatoptera Petrulevičius & Gutiérrez 2016 [= (Argentinalidae Petrulevičius & Gutiérrez 2016 (Geropteridae Petrulevičius & Gutiérrez 2016 & Neodonatoptera Bechly 1996))]. Enigmaptera shares with the Neodonatoptera the synapomorphy 'MP fused with Cu for a long distance', while in the Kukaloptera, Argentinalidae, and Geropteridae, MP is only fused for a short distance with CuA.

  the Triadophlebiomorpha (Triassic), Zygoptera (Mesozoic to recent), Stenophlebioptera (Mesozoic), and Epiophlebioptera (Cretaceous to recent). All these previously known cases concerned taxa belonging to the derived clade Discoidalia Bechly 1996 (characterized by the presence of a nodus and of a discoidal cell). Enigmaptera has no nodal structure, but a kind of 'basal complex' sensu Rajabi et al. (2016), viz. a structure composed by the shared point of fusion of MA, MP and R together with bases of RP and distal part of MA; plus the cell defined by CuA, MP ending into R, and distal part of MA (Fig. 2). It is analogous, but not homologous, to the arculus plus discoidal cell of a Discoidalia and probably had the same function for deformations of the basal third of the wing.

  ., Tippeltová, S., Roques, P. & Nel, A., 2013. A new genus and species of Breyeriidae and wings of immature stages from the Upper Carboniferous, Nord-Pas-de-Calais, France (Insecta: Palaeodictyoptera). Insect Systematics & Evolution 44, 117-128. Prokop, J., Roques, P. & Nel, A., 2014. New non-holometabolous insects from Pennsylvanian of Avion locality in Pas-de-Calais, France (Insecta: 'Exopterygota'). Alcheringa 38, 155-169. Rajabi, H., Ghoroubi, N., Malaki, M., Darvizeh, A. & Gorb, S.N., 2016. Basal complex and basal venation of Odonata wings: structural diversity and potential role in the wing deformation. PLoS ONE 11 (8) (e0160610), 1-17. Riek, E.F. & Kukalová-Peck, J., 1984. A new interpretation of dragonfly wing venation based upon Early Carboniferous fossils from Argentina (Insecta: Odonatoidea) and basic characters states in pterygote wings. Canadian Journal of Zoology 62, 1150-1166.

Fig. 1 .

 1 Fig. 1. Enigmaptera magnifica gen. nov, sp. nov., holotype Avion 35, wing photograph and

Fig. 2 .

 2 Fig. 2. Enigmaptera magnifica gen. nov, sp. nov., holotype Avion 35, wing base (scale bar 1

.

  Wings slender and elongate; MP and Cu are at least shortly fused. The autapomorphies of the Neodonatoptera becoming: R and MA basally appressed together. Type species. Enigmaptera magnifica gen. nov, sp. nov. ; very narrow anal area, CuP and CuA reduced to 'crossveins' between MP+Cu and AA, RP1/2 very long.

	Enigmaptera gen. nov.
	Type species. Enigmaptera magnifica sp. nov.
	F o r
	P e
	e r
	R e
	v
	i e
	w
	O
	n l
	y
	Family ENIGMAPTERIDAE fam. nov.
	Diagnosis. Wing characters only: very narrow wing, basal part of MA closely parallel to R
	complete distal fusion of MP with R and MA, strongly convex MA re-emerging from R in

arculus

  the apomorphic fusion of MP with Cu, while the Eugeroptera Petrulevičius & Gutiérrez 2016 (only Eugeropteridae Riek 1983) have a vein M separated from Cu (at least in hind wing, probably in forewing too). Petrulevičius

Acknowledgements

We sincerely thanks Mr. Stéphane Carlier, Eiffage Route Nord Est, for their kind authorization to collect fossil insects in the terril of Avion.

Disclosure statement

No potential conflict of interest was reported by the authors.

Funding

The work of JP was supported by the research project of the Grant Agency of the Czech Republic (No. 18-03118S).

Data access statement

This study did not involve any underlying data. All specimens are available for re-study in the public institute indicated in the text.


Ons Nefla
email: ons.nefla@dauphine.eumeltem.ozturk@dauphine.fr

Meltem Öztürk

Paolo Viappiani
email: paolo.viappiani@lip6.fr

Imène Brigui-Chtioui
email: brigui-chtioui@em-lyon.com

Interactive Elicitation of a Majority Rule Sorting Model with Maximum Margin Optimization

Keywords: preference elicitation, ordinal classification, incremental elicitation, MR-sort, simulations

We consider the problem of eliciting a model for ordered classification. In particular, we consider Majority Rule Sorting (MR-sort), a popular model for multiple criteria decision analysis, based on pairwise comparisons between alternatives and idealized profiles representing the "limit" of each category. Our interactive elicitation protocol asks, at each step, the decision maker to classify an alternative; these assignments are used as training set for learning the model. Since we wish to limit the cognitive burden of elicitation, we aim at asking informative questions in order to find a good approximation of the optimal classification in a limited number of elicitation steps. We propose efficient strategies for computing the next question and show how its computation can be formulated as a linear program. We present experimental results showing the effectiveness of our approach.

Introduction

There are several situations where it is necessary to classify objects, defined on several criteria, into ordered classes (for example, credit ratings, evaluating students, hotel categorization, etc). Such ordinal classification problems, also called multi-criteria sorting, have been considered by ELECTRE TRI [START_REF] Mousseau | A user-oriented implementation of the ELECTRE-TRI method integrating preference elicitation support[END_REF][START_REF] Roy | The outranking approach and the foundations of electre methods[END_REF], a popular method from the field of multi-criteria decision analysis that has been successfully applied to several domains.

Majority Rule Sorting (MR-sort) [START_REF] Leroy | Learning the parameters of a multiple criteria sorting method[END_REF] is a simplified version of ELECTRE TRI belonging to a class of "non compensatory" decision models that have been axiomatized by Bouyssou and Marchant [START_REF] Bouyssou | An axiomatic approach to noncompensatory sorting methods in mcdm, ii: More than two categories[END_REF]. The remarkable characteristic of the MR-sort procedure is that its classifications are readily explainable to the users. In MR-sort an alternative is assigned to a category when it is "at least as good as" an idealized profile describing the category's lower "limit" and "not better" than the category's upper limit. The limit profiles encode the characteristics that an alternative should have in order to be assigned to a particular class according to the decision maker (for example: a 4-stars hotel should have rooms of at least a certain size, it should have a swimming pool, a 5 star hotel should have a classy restaurant, etc). The relation comparing alternatives and limit profiles is based on a weighted majority rule (in Sobrie et al. [START_REF] Sobrie | Learning the parameters of a non compensatory sorting model[END_REF] a non linear model for combining the weights is considered).

In order to use MR-sort in practice, it is necessary to undertake a preference elicitation phase in order to assess the parameters of the model. The "classical" approach to elicitation consists in a fine grained assessment of the model parameters; however since it is often not reasonable to directly ask the decision maker about the values of the parameters of the model, we adopt an incremental elicitation approach and we assume that the decision maker can easily classify one given alternative into one of the categories; the information provided by the user can be used to update the model and provide a better result. The intuition is that, by selectively choosing which items the decision maker could classify, we could retrieve a good approximation of the "correct" model of the decision maker (DM) even with a small number of examples. We also stress that the information provided by the user may be noisy, as she may have made a mistake in assessing the right category for the alternative.

In this paper we adopt max-margin optimization, whose main principle is the following. The currently known assignments of items to categories are encoded by a set of inequalities on the feasible parameters; a shared non-negative margin is introduced as a decision variable that is maximized in the objective function. Noisy feedback is addressed by relaxing the constraints using slack variables and adding a penalty term in the objective function for violated constraints. In this paper, we propose an incremental approach for eliciting the parameters of a MR-sort model; at each step of the elicitation procedure, the system asks a question to the user and the question is specifically chosen in order to be as "informative" as possible. Our main algorithm repeatedly uses the max-margin optimization routine with two goals 1) to make an estimation of the model parameters given the current information 2) to determine a measure of uncertainty associated with a potential question. For the second goal, we consider different strategies based on computing the maximum-margin a posteriori (considering the different answers that the decision maker could give).

We now provide a brief discussion about related works. Reasoning with preferences [START_REF] Domshlak | Preferences in AI: An overview[END_REF] is an important issue in artificial intelligence. Several researchers have dealt with the problem of dealing with an incompletely specified preference model and with the issue of preference elicitation [START_REF] Boutilier | Computational decision support: Regret-based models for optimization and preference elicitation[END_REF][START_REF] Conitzer | Vote elicitation: Complexity and strategyproofness[END_REF][START_REF] Azari Soufiani | Preference elicitation for general random utility models[END_REF][START_REF] Zhao | A cost-effective framework for preference elicitation and aggregation[END_REF]. In the machine learning community, approaches for preference learning have been proposed [START_REF] Fürnkranz | Preference Learning[END_REF], including approaches for ordinal classification (see Chapter 8 in [START_REF] Murphy | Machine Learning: A Probabilistic Perspective[END_REF], and, for instance [START_REF] Frank | A simple approach to ordinal classification[END_REF] and [START_REF] Fürnkranz | Multilabel classification via calibrated label ranking[END_REF]).

Our work is stimulated by recently proposed approaches for eliciting multi-attribute utility functions using maximum-margin optimization [START_REF] Teso | Constructive preference elicitation by setwise max-margin learning[END_REF][START_REF] Teso | Constructive preference elicitation for multiple users with setwise max-margin[END_REF] in configuration problems. The maximum-margin optimization that we adopt has been used (with some variations) in previous works [START_REF] Sobrie | Learning the parameters of a non compensatory sorting model[END_REF][START_REF] Sobrie | A population-based algorithm for learning a majority rule sorting model with coalitional veto[END_REF] that tackled the problem of learning the weights of a MR-sort model; these works, however, did not consider incremental elicitation. Bennabou et al. [START_REF] Benabbou | A regret-based preference elicitation approach for sorting with multicriteria reference profiles[END_REF][START_REF] Benabbou | Incremental elicitation of choquet capacities for multicriteria choice, ranking and sorting problems[END_REF] recently proposed interactive elicitation methods based on minimax regret for ordinal classification problems (with a related but different model); these methods however have the inconvenience that they are not tolerant to errors in the responses of the decision maker.

The paper is structured as follows. After some background in Section 2, we present MR-sort model in Section 3 and the interactive elicitation in Section 4. We then discuss our experimental results in Section 5 and provide some final comments and directions for future work in Section 6.

Background

We consider a set X of m items that are evaluated with respect to a set of criteria C = {criterion 1 , . . . , criterion n }. Criteria associate items with a performance evaluation; (with little abuse of notation, we use x to refer to both the item and its evaluation vector). The evaluation of x is a vector (x 1 , x 2 , . . . , x n ) ∈ E 1 × . . . E n . The sets E 1 , . . . , E n are totally ordered and represent the space of criteria evaluations. Indeed we are interested in ordinal classification methods that allow the criteria evaluations to be defined on scales not necessarily numerical, and that can differ among the criteria. We use [m] to denote the set {1, . . . , m}.

MR-sort [START_REF] Leroy | Learning the parameters of a multiple criteria sorting method[END_REF] is a multi-criteria ordinal classification method allowing to assign alternatives to ordered categories. The set of categories is denoted by C = {C 1 , C 2 , . . . , C p }. Categories are ordinal, C 1 being the worst and C p the best one. Each category C h is characterized by two "fictitious" items b

h = (b h 1 , ..., b h n ) ∈ E 1 × . . . E n and b h+1 = (b h+1 1 , ..., b h+1 n ) ∈ E 1 × .
. . E n ; these are called the limit profiles of C h and we denote by B = {b 1 , b 2 . . . , b p+1 } the set of such limit profiles. Limit profiles play the role of the lower and the upper bounds of the category C h ; limit profiles of higher categories dominate the lower ones:

∀k = 1, . . . , n, b i+1 k ≥ k b i k and ∃j, b i+1 j > k b i j
, where ≥ k is the binary relation on the evaluations on the criterion k . There are two special limit profiles, b 1 and b p+1 that are defined as the minimum and the maximum values:

b 1 = (b 1 1 , ..., b 1 n ), such that ∀i, b 1 i = min x∈X (x i ) (resp. b p+1 = (b p+1 1 , ..., b p+1 n ), such that b p+1 i = max x∈X (x i )).
To fully specify a MR-sort model we need to associate each criterion cr i with a numerical weight w i , that intuitively represents its importance. A parameter λ is called the majority threshold, whose role will become clear below.

The procedure for making assignments is based on pairwise comparisons between objects of X and limit profiles. An alternative x is assigned to the category C h if it is "at least as good as" the lower limit profile b h and it is not "at least as good as" the upper limit profile b h+1 according to a binary relation . Indifference : x ∼ y ⇐⇒ x y and y x.

x → C h ⇐⇒ x b h and x b h+1 (1)
where x → C h means that alternative x is assigned to category C h . An item x that is indifferent to the upper limit profile of the best category (x ∼ b p+1 , meaning x b p+1 and x b p+1 ) is assigned to C p . The binary relation

⊆ (E 1 × . . . E n ) × (E 1 × . . . E n )
is based on the weighted majority principle:

x b h ⇐⇒ i:xi≥ib h i w i ≥ λ (2)
Example. Assume that we have 5 hotels (x, y, z, t, u) defined on n = 3 criteria (cost, comfort, quality of the restaurant). Our aim is to assign our hotels into p = 3 categories (C 1 : 1 star, C 2 : 2 stars, C 3 : 3 stars). The MR-sort model parameters are: λ = 0.55, w = (0.2, 0.5, 0.3). The criteria evaluation scale is between 0 and 5 (5 being the best score) for criterion 1 and criterion 2 ; the scale for criterion 3 is between 0 and 10. Table 1 presents the performances of the limit profiles and the alternatives; Table 2 their comparisons using and the assignments of alternatives.

criterion1 criterion2 criterion3 b 1 0 0 0 b 2 2 2 4 b 3 4 4 8 b 4 5 5 10
x 1 2 3 y 3 3 8 z 1 5 8 t 1 3 10 u 1 2 1 Table 1. Performance of limit profiles b 1 , b 2 , b 3 , b 4 and alternatives x, y, z, t, u b 1 b 2 b 3 b 4 Assignment x C1 y C2 z C3 t C2 u C1 Table 2.
Comparison between alternatives and profiles and final assignments.

Note that the MR-sort method allows the use of heterogeneous scales since the only information being useful for the relation is an ordinal one. Hence, a problem with only ordinal scales or with different types of scales (interval one, ratio one and ordinal one) can be handled without difficulty by an MR-sort model.

Learning a MR-sort model from assignments

We assume that we are given some assignments of alternatives to categories. In this work we assume that limit profiles are given. In the following, we first introduce the notion of possible and necessary categories, and then we present a maximum-margin optimization for learning the parameters of a MR-sort model.

Possible Categories

Let A be the set of alternatives whose category is known and LS the "learning set" (pairs of alternatives and categories):

LS = {(x, C h ), x ∈ A, x → C h }.
From LS, assuming an underlying MR-sort model, we can reason about the weights that are consistent with the current knowledge. According to Equation ( 1) and ( 2), an assignment of the type x DM --→ C h (made by the decision maker) corresponds to imposing the linear constraints:

i:xi≥b h i w i ≥ λ (3) i:xi≥b h+1 i w i < λ (4)
Let Θ(LS) be set of parameters that are compatible with the learning set LS, satisfying constraints ( 3) and ( 4) for all pairs in LS, and the requirements that the weights are non negative and normalized.

When dealing with partially specified preference models, it is typical to reason about possible and necessary preference information [START_REF] Greco | Ordinal regression revisited: Multiple criteria ranking using a set of additive value functions[END_REF]. In our context, given an alternative and its performance evaluation we can reason about the parameters that are consistent with the current knowledge. Now, given an item x ∈ A, we define the set of possible categories PC(x; LS) as the set of categories such that there is an instantiation of the parameters θ = {w 1 , . . . , w n , λ} consistent with the assignment given the previously known assignments LS.

PC(x; LS

) = {C i ∈ C | ∃θ ∈ Θ(LS) : x θ -→ C i }
where we write x θ -→ C i to emphasize the dependency between the parameters θ and the assignment. If there is only one possible category, i.e. | PC(x)| = 1, then it means that the alternative has to be necessarily assigned to the only category in PC (assuming that the model is consistent with the learning set; in Section 3.2 we discuss how to handle inconsistencies). In practice it is possible that a partial knowledge about the parameters allows us to determine in which categories we have to place several alternatives. We anticipate that the concept of possible categories plays an important role in our elicitation strategies (see Section 4.2).

Maximum margin optimization

We now address the problem of learning the parameters θ = {w 1 , . . . , w n , λ} of a MRsort model (given a set of learning assignments) with a linear program. We assume that we are given as input the following values: the number of criteria n, the number of categories p, and the limit profiles b h for each h ∈ [p]. Our goal is to assess the weights w and the majority threshold λ, that are decision variables for the optimization problem. In order to discriminate between different choices for the parameters, the first step is to introduce a shared margin µ as an additional decision variable. The first linear program (LP) assumes that the data in LS is perfectly consistent with the MR-sort model.

µ * = max µ (5) s.t. i:xi,≥b h i w i ≥ λ + µ ∀(x, C h ) ∈ LS (6) i:xi≥b h+1 i w i ≤ λ -µ ∀(x, C h ) ∈ LS (7) n i=1 w i = 1 (8) µ ∈ R (9) w i ≥ 0 ∀i ∈ [n] (10)
Constraints ( 6) and ( 7) correspond to Equations ( 3) and ( 4) with the inclusion of the shared margin µ. Note that later in Section 4.2 we will use µ * (LS) to denote the application of the LP above to find the value of the best compatible margin. We observe that in general there may be occasional inconsistencies in user feedback, or simply the data may not be compatible with a MR-sort model. The "typical" way to handle this is to introduce slack variables (whose sum we aim at minimizing); this idea goes back to the UTA approach [START_REF] Jacquet-Lagrèze | Assessing a set of additive utility functions for multicriteria decision making: the UTA method[END_REF] and several later models [START_REF] Gajos | Preference elicitation for interface optimization[END_REF][START_REF] Ah-Pine | Identification of a 2-additive bi-capacity by using mathematical programming[END_REF]. We formalize the problem of finding the weights of a MR-sort model (given a set of learning assignments) with the following linear program.

m * = max µ -α (x,C h )∈LS ξ i,j (11)
s.t.

i:xi,≥b h i w i + ξ x,h ≥ λ + µ ∀(x, C h ) ∈ LS (12) i:xi≥b h+1 i w i -ξ x,h ≤ λ -µ ∀(x, C h ) ∈ LS (13) n i=1 w i = 1 (14) µ ∈ R (15) ξ x,h ≥ 0 ∀(x, C h ) ∈ LS ( 16
)
w i ≥ 0 ∀i ∈ [n] (17)
The variables are the following:

λ ∈ [0, 1], w i ∈ [0, 1]∀i ∈ [n], µ ∈ [0, 1] and ξ x,h ∈ [0, 1]
∀x ∈ LS such that x assigned to C h . We use a parameter α to express the "cost" of violating a constraint representing assignments from the learning set. The objective (Equation 11) is to maximize the shared margin µ (that we want to maximize) minus the sum of the constraints violations ξ i,j (that we want to minimize). In order to be able to handle the inconsistency in the user's answers we add a slack variable (ξ x,h ) for each x ∈ A and for each h ∈ {1, . . . , p}. Constraint 12 and constraint 13 handle the conditions related to the assignments of the alternatives in the learning set LS. Constraint 14 enforces that the weights are normalized.

Incremental MR-sort

Algorithm 1 The MR-sort-Inc algorithm. K is the number of questions, X the set of alternatives, C the set of categories, LS (LS = {(x, C h ), x ∈ A, x → C h }) learning assignments, s the strategy. In this section, we provide an elicitation method for an ordinal classification problem assuming that the preferences can be modeled by MR-sort.

Main Framework

Our elicitation procedure starts with a small learning set LS to which we add one-byone new assignment examples. We ask questions of the type "In which category should x be assigned to?"; it is crucial to select "informative" items to ask about, in order to quickly converge (in few interaction cycles) to a good classification model.

We remind that a MR-sort model is defined by the following parameters: the weights (w 1 , . . . , w n ), the limit profiles (b 1 , . . . , b p+1 ) and majority threshold λ. We fix the limit profiles before the beginning of the elicitation. In the experiments below the limit profiles are chosen in a way to evenly partition the criteria scale. The main steps of our approach are presented in Algorithm 1. Briefly, we start with some data from the learning set LS (learning alternatives A and their classification) and we include them as constraints in our linear program (LP). Given the learning set, we can estimate the weights w * and λ * using the linear program; in simulations we can also evaluate the classification error. After that, we test the assignment of each unassigned item to each category and retrieve the margin values obtained when using the optimization routine with each of the additional assignments. This gives us a vector of margins "a posteriori", that are aggregated differently depending on the "strategy" (different strategies will be discussed in the following section), giving a score for each item. The item having the highest score is chosen: the user is asked about the assignment of that item and the learning set is augmented. This procedure continues until a stopping condition (in our experiments when we reach a fixed number of questions, but in real applications termination may be left to the user). The last linear program contains all the assignments of the computed learning set, hence it provides the weights that we are looking for.

Example. We apply our incremental elicitation algorithm to the running example. Suppose that we only know the assignment of alternative x (LS = {(x, C 1 )}) and we want to ask just one question to the user. We first set the limit profiles: b 1 = (0, 0, 0), b 2 = ( 53 , 5 3 , 10 3 ), b 3 = ( 10 3 , 10 3 , 20 3 ), b4 = (5, 5, 10). Our goal is to learn λ and a weight vector w which will assign the remaining alternatives to categories as close as possible to the ones presented in Example 2. For this, according to our algorithm, we compute the score of alternatives y, z, t, u (S s (y), S s (z), S s (t), S s (u)) and ask the assignment of the alternative having the highest score. We add this new constraint to LS and find the weight vector w * corresponding to the largest margin. Using w * , we can find the current best assignment of the remaining alternatives and compute 4 an error measure using the assignments of Example 1 and the one that we find using w * .

Question selection strategies

In the following we present several strategies to select the next question to ask to the user. These strategies are used within our interactive elicitation paradigm described in Algorithm 1. The proposed strategies makes use of the max-margin optimization programs (discussed above in Subsection 3.2) to identify informative questions.

Most Uncertain With this strategy, we aim to ask the DM to classify the most uncertain item in X \ A, that is the item that is compatible (according to the constraints derived from the known assignments of the learning set) with the highest number of categories. The score that this strategy assigns to an alternative x is given by the cardinality of the set of possible categories:

S MU (x) = | PC(x; LS)|.
The computation of the set PC(x) for an item x makes use of the linear program for learning the parameters of a MR-sort without the slack variables (Equations 5-10). For each category C i , we then constrain the item x to be assigned to C i and simply check whether the margin is non negative; indeed µ * (LS ∪(x, C i )) > 0 if and only if C i is a possible category (C i ∈ PC(x; LS)). The score of this strategy can be compactly written as:

S MU (x) = | PC(x; LS)| = p i=1 H[µ * (LS ∪(x, C i ))]
where H(•) is the step function.

Example. Consider the problem presented in Example 2. We suppose that we know the performance of each alternative, and the assignment of x, while the other assignments are unknown. Assume that we want to ask just one question. As before, we fix b 1 = (0, 0, 0), b 2 = ( As a result we ask the assignment of alternative t to the user. The user will answer C 2 to this question (coherent with Example 2) and the constraint related to t → C 2 will be added to the LP. After the inclusion of the constraint t → C 2 in LS, we find our final weight vector w * , such as w * = (0.266, 0.366, 0.366). Even if w is different from the weight vector of Example 2 (w = (0.2, 0.5, 0.3)), after our incremental elicitation we find the same assignments for y, z, u (i.e. y → C 2 , z → C 3 and u → C 1 ).

Sum-of-margin strategy

The problem of the most-uncertain strategy is that, roughly speaking, it is agnostic to whether a potential assignment is consistent with large portions of the parameter space or just with small area. The intuition of sum-of-margin is to use the value of the objective function of the LP as a surrogate measure of the "degree" of satisfaction of an assignment x → C h . Intuitively, we should ask about items that may fit well into several different categories. We also include the possibility that some constraints can be violated, therefore make use of the second LP (Equations 11-17), with the penalty variables ξ for violated assignments of the learning set.

Considering an alternative x ∈ X \ A, we evaluate the penalized margin m * adding the assignment x → C i for all i ∈ [p] and construct the following vector:

v(x) = (m * (LS ∪(x, C 1 )), . . . , m * (LS ∪(x, C p ))).
In order to aggregate this vector into a single numerical measure, we adopt the sum. Hence, the score of the alternative x is computed as 4. The score obtained by the different items in the hotel categorization example using the heuristics sum-of-maring (left) and entropy (right)

S Σ (x) = p i=1 v i (x) = p i=1 m * (LS ∪(x, C i )). Assignment vi(•) S Σ y → C1 -0.45 0.45 y → C2 0.45 y → C3 0.45 z → C1 0.45 0.90 z → C2 0 z → C3 0.45 t → C1 0.45 1.08 t → C2 0.18 t → C3 0.45 u → C1 0.49 -0.10 u → C2 0 u → C3 -0.55 Assignment v SE y → C1 0 0.30 y → C2 0.5 y → C3 0.5 z → C1 0.5 0.30 z → C2 0 z → C3 0.5 t → C1 0.43 0.44 t → C2 0.15 t → C3 0.42 u → C1 1 0.00 u → C2 0 u → C3 0 Table
Example. Consider again the running example. Table 4 (in the left) presents the S of alternatives {y, z, t, u}. As the example shows, the best question is to ask about t, the second best question is to ask about z, then y, and finally u. We note a disagreement of MU and sum-of-margin about the ranking of z and y.

Entropy This strategy adopts the notion of entropy to assess the uncertainty for a given alternative. As the strategy sum-of-margin, we calculate m * which represents the maximum penalized margin if we assign the alternative x to the category C i , for all i ∈ [p]. We then combine these values in an evaluation vector v that filters out negative values (assigning them a zero value) and we normalize so that the values sum up to one:

v i (x) = R(m * (LS ∪(x, C i )) p j=1 R(m * (LS ∪(x, C j ))
where R(•) is the ramp function. We then apply the entropy to calculate the final score of the alternative.

S E (x) = - i∈[p]:v i (x)>0 v i (x) log(v i (x))
Intuitively this method should favour asking about items whose uncertainty is the greatest in an information-theoretic sense, considering the vector v (composed of normalized non-negative margin values) as a surrogate measure for the probability distribution of the category of x (i.e. how likely is x to be in each of the categories).

Example. We consider again our example on hotel categorization. We now apply the entropy strategy; Table 4 (on the right) presents the score S E of all the alternatives. Item t has the highest score, then z and y are tied in the second position; u is last.

Random strategy As a baseline, we consider the random selection of an object x from X \ A. Utilizing this strategy is equivalent to use a non incremental elicitation procedure with |LS| + K (LS being the initial learning set of Algorithm 1 and K being the number of questions) alternatives in the learning set.

Note that all our strategies have the same computational complexity : O(Kmp) (resp. number of questions, alternatives, categories).

Experiments

We implemented our incremental MR-sort algorithm using Java API of CPLEX for solving the LP. 5 We performed simulations aimed at evaluating the effectiveness of the proposed elicitation strategies with two data-sets: a synthetic data-set fully represented by a MR-sort model, and a data-set from the UCI machine learning repository [START_REF] Dua | UCI machine learning repository[END_REF].

Synthetic data-set For the first part of our experiments, the input data was generated randomly using a uniform distribution on the space of evaluations.

We include only one assignment, chosen at random in LS. The steps of the simulation are as follows:

i. Using a uniform distribution for each of the parameters, we generate the performance table of alternatives, a vector of weight w, the majority threshold λ. The limit profiles are chosen to evenly partition the range of evaluation values. These parameters fully specify the decision maker; we call this model M . We then apply the MR-sort method in order to find the assignments of the generated alternatives; these assignments constitute the "ground truth". ii. We apply our incremental elicitation Algorithm 1 using the assignments of some alternatives of M as learning assignments. We apply incremental MR-sort by asking questions to the user based on the proposed strategies, simulating a decision maker who answers according to the results of the M . We generate as output a vector of weight w * representing the DM's preferences. iii. Using the assumed limit profiles and the learned weight vector w * and the majority threshold λ * , we obtain our learned model M that provides the assignments of the remaining alternatives. iv. At the end we calculate an error rate based on the difference between the assignments of the true model M and the learned model M .

We iterate these steps 50 times and we evaluate the classifications obtained with the different methods according to the average classification error AE k = x∈X err k (x)/m where m is the number of alternatives and k ∈ {1, 2}. The value

err k (x) = d(C i , C j )
is the magnitude of error when x M -→ C i and x M -→ C j (the true model assigns x to C i while the learned model M assigns it to C j ). err 1 adopts a 0/1 loss as distance, while err 2 considers the displacement between the assignments, that is d(C i , C j ) = |i-j|.

Figure 1 presents the results of our simulations (for more results see figures 4 -6 in the appendix ). Note that the random strategy performs very poorly, while all three strategies (maximum uncertainty, sum of margin, entropy) have reasonably good performance. Not surprisingly, the higher the number of categories, the quicker we converge, since there is more uncertainty with more categories. Conversely, the higher the number of criteria the less quickly the interaction converges. The results with respect to AE 2 are quite satisfying since they show that, after few questions have been answered, our procedure makes few assignment mistakes and these mistakes concern consecutive categories most of the times.

UCI Car

We performed simulations based on Car data-set. There are 1728 items defined on 6 categorical attributes (that we interpret as ordinal); the items are partitioned in 4 categories: unacceptable (65 items), acceptable (1210), good (384) and very good (69). We converted the qualitative (ordinal) attributes to numeric attributes and we set the criteria rating scale between 1 and 4. The steps of the simulation are : i.) We first compute the best error rate that we could have if all the data was included in LS. ii.) We ask questions until we reach this error percentage. We started to test on 300 alternatives chosen randomly and we start by including in the learning set only one assignment taken randomly.

In order to find the best error percentage, we call it P * , we include all the data in LS and we vary the value of λ. We obtain P * when λ is between 0.7 and 0.75. In this case the err 1 = 18.86% ( err 2 being 0.24). So we aim to reach this percentage by asking the minimum number of questions. Our simulations showed that fixing the value of λ makes faster the convergence, we show in Figures 23the comparison between the 4 strategies where λ is fixed to 0.7.

With the random strategy we observe that the variation of error according to number of questions is not monotonous and we don't approach to P * by asking 10 questions. On the other hand, the strategies maximum uncertainty and sum of margin are closer to P * starting from 6 th question. The strategy maximum uncertainty stops after the 7 th question because it hangs in case of inconsistency. We notice that the assignments errors are almost always between consecutive categories; Figure 3 shows the performance with respect to the second metric. MR-sort is an attractive method for ordinal classification that offers the advantage of allowing the use of heterogeneous scales (mixing ordinal and cardinal scales). In this paper we presented an incremental elicitation procedure for the parameters (weights and threshold) of MR-sort. Our approach relies on a maximum-margin optimization that aims at satisfy as well as possible the known assignments, following approaches proposed in the literature for non-interactive learning of MR-sort and variations [START_REF] Leroy | Learning the parameters of a multiple criteria sorting method[END_REF][START_REF] Sobrie | Learning the parameters of a non compensatory sorting model[END_REF][START_REF] Sobrie | A population-based algorithm for learning a majority rule sorting model with coalitional veto[END_REF]. The novelty of this paper consists in showing how the optimization can be used to evaluate the uncertainty associated to the items whose category is not known yet; the choice of the next question is based on evaluating the margin a posteriori (the value of maximum-margin optimization when adding a possible response to a question). Based on this intuition we proposed several strategies for selecting the next question to ask. We evaluated the proposed interactive elicitation procedure comparing the performance of the different strategies showing that the procedure quickly converges to the real optimal classification in very few interaction cycles.

We highlight that one important limitation of our framework is that we expect the decision maker to provide us with the limit profiles of the different categories. In future works we will relax this assumption considering techniques to elicit as well the limit profiles (either in a preliminary step or in an integrated approach), therefore providing a complete method for interactive elicitation of a MR-sort model. This task will be challenging, since previous works on (non incremental) elicitation of MR-sort have shown that, while it is possible to introduce integer variables [START_REF] Leroy | Learning the parameters of a multiple criteria sorting method[END_REF] the resulting optimization is computationally very demanding and not scalable; therefore randomized heuristics [START_REF] Sobrie | Learning a majority rule model from large sets of assignment examples[END_REF][START_REF] Sobrie | Learning monotone preferences using a majority rule sorting model[END_REF] have been proposed.

We are also interested in performing simulation to compare our approach to other elicitation frameworks, as the recent work of Olteanu [START_REF] Liviu | Strategies for the incremental inference of majority-rule sorting models[END_REF], and the approaches based on minimax regret [START_REF] Benabbou | A regret-based preference elicitation approach for sorting with multicriteria reference profiles[END_REF][START_REF] Benabbou | Incremental elicitation of choquet capacities for multicriteria choice, ranking and sorting problems[END_REF], in realistic settings. We plan to investigate the connection between our approach and the field of machine learning. First, maximum-margin bears much similarity to Support Vector Machines (SVM). Second, ordinal classification has also been studied in machine learning. Third, there is strong similarity between incremental elicitation and active learning.

Finally, another important direction is to elicit the preferences of several users, providing methods that can exploit the similarity between users, as in Teso et al. [START_REF] Teso | Constructive preference elicitation for multiple users with setwise max-margin[END_REF].

  b 4 = (5, 5, 10).

Fig. 1 .

 1 Fig. 1. AE2 based on number of questions with m = 100, n = 5, p = 2, p = 3, p = 4,|LS| = 1 and 50 iterations

Fig. 2 .Fig. 3 .

 23 Fig. 2. AE1 based on number of questions with m = 300, n = 6, p = 4,|LS|=1 and 50 iterations

Fig. 4 .

 4 Fig. 4. Classification error AE1 based on number of questions with m = 100, n = 4, p = 2, p = 3, p = 4, |LS| = 1 and 50 iterations

Fig. 5 .

 5 Fig. 5. AE2 based on number of questions with m = 100, n = 4, p = 2, p = 3, p = 4, |LS| = 1 and 50 iterations

Fig. 6 .

 6 Fig. 6. AE1 based on number of questions with m = 100,n = 5, p = 2, p = 3,p = 4, |LS| = 1 and 50 iterations

Table 3 .

 3 Table 3 presents the S MU of all the remaining alternatives (step 3). Number of possible categories for the example of hotel categorization.

	Alternatives PC(x; LS) SMU
	y	{C2, C3}	2
	z	{C1, C3}	2
	t	{C1, C2, C3}	3
	u	{C1}	1

This step is of course only to be performed in simulations, in real use of the procedure the classification error will not be known

All experiments were run on a 2.9 GHz Intel, Core i7 and 16 Giga of RAM.